Author Topic: Object collision based on vectors & spheres  (Read 2222 times)

Offline r0ber7

  • Prof. Inline
  • *****
  • Posts: 542
    • View Profile
Consider this.



To check collision between two spheres, I calculate the distance between the two centers of those spheres. If that distance is smaller than the sum of the radiuses plus the velocity of the objects (r + r + xs), collision = true.

My question is about collision with the ground. I have an array with x&y locations for the ground. I know the position of a, I know the position of b, I know the length of r, I know the velocity of the object along the vector, so I know point c too.

How do I check if b,c intersects with d,e? I've read about the dot product, but I don't really understand how I would implement that. I'm fairly new to vectors, and I hope someone here can help me.

I've based this on this article, which I only understand somewhat.
http://www.wildbunny.co.uk/blog/2011/04/06/physics-engines-for-dummies/

Cheers.
« Last Edit: 2013-Jun-07 by r0ber7 »

Offline Slydog

  • Prof. Inline
  • *****
  • Posts: 930
  • KodeSource
    • View Profile
    • KodeSource
Re: Object collision based on vectors & spheres
« Reply #1 on: 2013-Jun-07 »
I'm not too familiar with vectors myself, but found this generic collision / intersection library (in C++?):
http://pastebin.com/f2d380dd3

I have my own vector TYPE I have pieced together from other vector routines I found while surfing, if you're interested.
It does have a Dot Product function, but my problem is I don't know what that means, or when / why to use it! I should have paid more attention is school, but back then I thought "When will I ever need to know this crap?!"  :zzz:

Code: (glbasic) [Select]
//------------------------------------------------------------------ V e c t o r
TYPE TVector
x
y
z

FUNCTION Set%: x, y, z
self.x = x
self.y = y
self.z = z
ENDFUNCTION

FUNCTION Clear:
self.x = 0
self.y = 0
self.z = 0
ENDFUNCTION

FUNCTION Copy: v_from AS TVector
self.x = v_from.x
self.y = v_from.y
self.z = v_from.z
ENDFUNCTION

FUNCTION Add: v AS TVector
INC self.x, v.x
INC self.y, v.y
INC self.z, v.z
ENDFUNCTION

FUNCTION Subtract AS TVector: v1 AS TVector
LOCAL v AS TVector
v.x = self.x - v1.x
v.y = self.y - v1.y
v.z = self.z - v1.z
RETURN v
ENDFUNCTION

FUNCTION MidPoint: v1 AS TVector, v2 AS TVector
self.x = (v2.x - v1.x) / 2.0 + v1.x
self.y = (v2.y - v1.y) / 2.0 + v1.y
self.z = (v2.z - v1.z) / 2.0 + v1.z
ENDFUNCTION

FUNCTION IsEqual%: v AS TVector
IF self.x <> v.x THEN RETURN FALSE
IF self.y <> v.y THEN RETURN FALSE
IF self.z <> v.z THEN RETURN FALSE
RETURN TRUE
ENDFUNCTION

// Calc the magnitude of a vector
FUNCTION Magnitude:
RETURN SQR((self.x * self.x) + (self.y * self.y) + (self.z * self.z))
ENDFUNCTION

FUNCTION Distance: v1 AS TVector
LOCAL delta AS TVector
delta = v1.Subtract(self)
RETURN ABS(delta.Magnitude())
ENDFUNCTION

FUNCTION Normalize:
LOCAL TOLLERANCE = 0.0001
LOCAL m
//normalize a vector so it's length = 1 AND apply tolerance based on our constant tolerance value
//m = SQR(self.x * self.x + self.y * self.y + self.z * self.z)
m = self.Magnitude()
IF m <= TOLLERANCE THEN m = 1.0
self.x = self.x / m
self.y = self.y / m
self.z = self.z / m
IF ABS(self.x) < TOLLERANCE THEN self.x = 0
IF ABS(self.y) < TOLLERANCE THEN self.y = 0
IF ABS(self.z) < TOLLERANCE THEN self.z = 0
ENDFUNCTION

// Reverse a vector
FUNCTION Reverse AS TVector:
LOCAL v AS TVector
v.x = -self.x
v.y = -self.y
v.z = -self.z
RETURN v
ENDFUNCTION

// Vector : Scalar Multiply -> used TO scale a vector by 'scale'
FUNCTION ScaleSet: x#, y#=0, z#=0
   IF y = 0 THEN y = x
   IF z = 0 THEN z = x
   self.x = self.x * x
   self.y = self.y * y
   self.z = self.z * z
ENDFUNCTION

// Vector : Scalar Divide
FUNCTION ScalarDivide: amount#
self.x = self.x / amount
self.y = self.y / amount
self.z = self.z / amount
ENDFUNCTION

// Takes v1 AND v2 AND returns the cross product v1 X v2.
// The cross product is a vector perpendicular TO both v1 AND v2
// This is the normal of 2 vectors
// Applications: Finding normal vectors, finding turn directions, calculating torque
FUNCTION CrossProduct AS TVector: v2 AS TVector
LOCAL v AS TVector
v.x = (self.y * v2.z) - (self.z * v2.y)
v.y = (self.z * v2.x) - (self.x * v2.z)
v.z = (self.x * v2.y) - (self.y * v2.x)
RETURN v
ENDFUNCTION

// Calculate AND RETURN the dot product of 2 vectors (distance)
// Applications: finding angles between vectors, projecting vectors into specific axes, determining whether a vector is facing the right direction, neutralizing a vector along a given axis
FUNCTION DotProduct#: v AS TVector
   LOCAL dp
   dp = (self.x * v.x) + (self.y * v.y) + (self.z * v.z)
   RETURN dp
ENDFUNCTION

// Calculate the triple scalar FUNCTION AND RETURN it
FUNCTION TripleScalarProduct: v2 AS TVector, v3 AS TVector
   LOCAL v
   v =       self.x * ( ( v2.y * v3.z) - (v2.z * v3.y) )
   v = v + ( self.y * ( (-v2.x * v3.z) + (v2.z * v3.x) ) )
   v = v + ( self.z * ( ( v2.x * v3.y) + (v2.y * v3.x) ) )
   RETURN v
ENDFUNCTION


FUNCTION RotateAroundPointX: pivot AS TVector, angle#
LOCAL v AS TVector
LOCAL y, z, length
v.y = self.y - pivot.y
v.z = self.z - pivot.z
length = v.Magnitude()
angle = ATAN(v.z, v.y) + angle
self.y = QCOS(angle) * length + pivot.y
self.z = QSIN(angle) * length + pivot.z
ENDFUNCTION

FUNCTION RotateAroundPointY: pivot AS TVector, angle#
LOCAL v AS TVector
LOCAL x, z, length
v.x = self.x - pivot.x
v.z = self.z - pivot.z
length = v.Magnitude()
angle = ATAN(v.z, v.x) + angle
self.x = QCOS(angle) * length + pivot.x
self.z = QSIN(angle) * length + pivot.z
ENDFUNCTION

FUNCTION RotateAroundPointZ: pivot AS TVector, angle#
LOCAL v AS TVector
LOCAL x, y, length
v.x = self.x - pivot.x
v.y = self.y - pivot.y
length = v.Magnitude()
angle = ATAN(v.y, v.x) + angle
self.x = QCOS(angle) * length + pivot.x
self.y = QSIN(angle) * length + pivot.y
ENDFUNCTION

FUNCTION RotateAroundVec AS TVector: v2 AS TVector, angle
LOCAL v AS TVector
LOCAL cosa, sina, ecosa
cosa = QCOS(angle)
sina = QSIN(angle)
ecosa = 1.0 - cosa
v.x = self.x * (cosa + v2.x * v2.x * ecosa) + self.y * (v2.x * v2.y * ecosa - v2.z * sina) + self.z * (v2.x * v2.z * ecosa + v2.y * sina)
v.y = self.x * (v2.y * v2.x * ecosa + v2.z * sina) + self.y * (cosa + v2.y * v2.y * ecosa) + self.z * (v2.y * v2.z * ecosa - v2.x * sina)
v.z = self.x * (v2.z * v2.x * ecosa - v2.y * sina) + self.y * (v2.z * v2.y * ecosa + v2.x * sina) + self.z * (cosa + v2.z * v2.z * ecosa)
RETURN v
ENDFUNCTION


FUNCTION ToString$: width%=8
IF width <= 0 THEN RETURN "[" + self.x + "," + self.y + "," + self.z + "]"
LOCAL rv$
rv$ = "[" + FORMAT$(width, 2, self.x) + ","
rv$ = rv$ + FORMAT$(width, 2, self.y) + ","
rv$ = rv$ + FORMAT$(width, 2, self.z) + "]"
RETURN rv$
ENDFUNCTION

ENDTYPE
My current project (WIP) :: TwistedMaze <<  [Updated: 2015-11-25]

Offline r0ber7

  • Prof. Inline
  • *****
  • Posts: 542
    • View Profile
Re: Object collision based on vectors & spheres
« Reply #2 on: 2013-Jun-07 »
Thanks for your reply. However, I found someone on TIGSource who knew the way to do this. Basically what i now do is I find the nearest point along the ground vector, to the center of the sphere. Then I compare the distance to the nearest point with the sphere's radius. In pseudo-code:

From http://stackoverflow.com/questions/3120357/get-closest-point-to-a-line

Code: (glbasic) [Select]
def GetClosestPoint(A, B, P)

  a_to_p = [P.x - A.x, P.y - A.y]     # Storing vector A->P
  a_to_b = [B.x - A.x, B.y - A.y]     # Storing vector A->B

  atb2 = a_to_b[0]**2 + a_to_b[1]**2  # **2 means "squared"
                                      #   Basically finding the squared magnitude
                                      #   of a_to_b

  atp_dot_atb = a_to_p[0]*a_to_b[0] + a_to_p[1]*a_to_b[1]
                                      # The dot product of a_to_p and a_to_b

  t = atp_dot_atb / atb2              # The normalized "distance" from a to
                                      #   your closest point

  return Point.new( :x => A.x + a_to_b[0]*t,
                    :y => A.y + a_to_b[1]*t )
                                      # Add the distance to A, moving
                                      #   towards B

end

Offline matchy

  • Prof. Inline
  • *****
  • Posts: 1544
    • View Profile
Re: Object collision based on vectors & spheres
« Reply #3 on: 2013-Jun-07 »
Very nice lib Slydog. :)

Here's my rebuilt one function solution:
Code: (glbasic) [Select]
FUNCTION intersect_vertex AS _vertex: ver_a AS _vertex, ver_b AS _vertex, ver_c AS _vertex, ver_d AS _vertex
// a,b - line 1    c,d - line 2
LOCAL Ua, Ub, Ud
LOCAL ret AS _vertex

Ua = (ver_d.x - ver_c.x) * (ver_a.y - ver_c.y) - (ver_d.y - ver_c.y) * (ver_a.x - ver_c.x)
Ub = (ver_b.x - ver_a.x) * (ver_a.y - ver_c.y) - (ver_b.y - ver_a.y) * (ver_a.x - ver_c.x)
Ud = (ver_d.y - ver_c.y) * (ver_b.x - ver_a.x) - (ver_d.x - ver_c.x) * (ver_b.y - ver_a.y)
    IF Ud = 0
        IF Ua = 0 AND Ub = 0
            ret.x = (ver_a.x + ver_b.x) / 2
            ret.y = (ver_a.y + ver_b.y) / 2
        ENDIF
    ENDIF
    Ua = Ua / Ud
    Ub = Ub / Ud
    IF Ua > 0 AND Ua < 1 AND Ub > 0 AND Ub < 1
        ret.x = ver_a.x + Ua * (ver_b.x - ver_a.x)
        ret.y = ver_a.y + Ua * (ver_b.y - ver_a.y)
    ENDIF
    RETURN ret
ENDFUNCTION

Offline kanonet

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 1142
    • View Profile
    • My GLBasic code archiv
Re: Object collision based on vectors & spheres
« Reply #4 on: 2013-Jun-07 »
Rober7 talking about your image in 1st post, you also know points D and E right? Assuming D and E are always the points of ground that your object is above (its easy to get the right D and E for each position of your object, i guess you already do this right now?). When you have D and E its very easy to know if B is above them, does not need any real vector math at all:

assuming D.x < B.x < E.x:
Code: (glbasic) [Select]
IF B.y > D.y + (B.x-D.x)/(E.x-D.x) * (E.y-D.y) THEN COLLISION!If you use integers for .x and .y you need to use this:
Code: (glbasic) [Select]
IF B.y > D.y + (B.x-D.x)*1.0/(E.x-D.x) * (E.y-D.y) THEN COLLISION!
« Last Edit: 2013-Jun-07 by kanonet »
Lenovo Thinkpad T430u: Intel i5-3317U, 8GB DDR3, NVidia GeForce 620M, Micron RealSSD C400 @Win7 x64

Offline r0ber7

  • Prof. Inline
  • *****
  • Posts: 542
    • View Profile
Re: Object collision based on vectors & spheres
« Reply #5 on: 2013-Jun-07 »
Well yes, but I want to do it with walls, ceilings, basically everything which has a line. And I want to calculate the angle of the impact, so I can respond appropriately.

Offline kanonet

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 1142
    • View Profile
    • My GLBasic code archiv
Re: Object collision based on vectors & spheres
« Reply #6 on: 2013-Jun-07 »
Yes in this case a proper vec lib may be a bigger help.
Lenovo Thinkpad T430u: Intel i5-3317U, 8GB DDR3, NVidia GeForce 620M, Micron RealSSD C400 @Win7 x64