BASIC

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

Offline r0ber7

  • Prof. Inline
  • *****
  • Posts: 526
    • 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: 526
    • 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: 1542
    • 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: 526
    • 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