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

#### r0ber7

• Prof. Inline
•     • • Posts: 542 ##### Object collision based on vectors & spheres
« on: 2013-Jun-07 »
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.

http://www.wildbunny.co.uk/blog/2011/04/06/physics-engines-for-dummies/

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

#### Slydog

• Prof. Inline
•     • • Posts: 930
• 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?!" Code: (glbasic) [Select]
`//------------------------------------------------------------------ V e c t o rTYPE 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\$ ENDFUNCTIONENDTYPE`
My current project (WIP) :: TwistedMaze <<  [Updated: 2015-11-25]

#### r0ber7

• Prof. Inline
•     • • Posts: 542 ##### 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**2 + a_to_b**2  # **2 means "squared"                                      #   Basically finding the squared magnitude                                      #   of a_to_b  atp_dot_atb = a_to_p*a_to_b + a_to_p*a_to_b                                      # 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*t,                    :y => A.y + a_to_b*t )                                      # Add the distance to A, moving                                      #   towards Bend`

#### matchy

• Prof. Inline
•     • • Posts: 1544 ##### 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 retENDFUNCTION`

#### kanonet

• Prof. Inline
•       • Posts: 1142 ##### 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

#### r0ber7

• Prof. Inline
•     • • Posts: 542 ##### 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.

#### kanonet

•        