Same side collison detection and the cross product formula

ID:161380
 
May 13 2008, 2:53 pm
Each triangle has 3 points, T, R, and L (Top, Right, and Left respectively). To read the variable names in the code below here are some hints:
CP = cross product
A = target
src = object bumping
srcT2aT2aL = src's T to a's T to a's L

TriangleCollide(var/atom/A,var/BUMPED=FALSE,var/Dir2Move)
            if(istype(src,/turf/Collision/Triangle/)) return FALSE //leave until finished debuging
            
            var/a_p1_x = abs(A.true_x - (A.maxWidth - A.GetPoint("T",TRUE)))
            var/a_p1_y = abs(A.true_y - (A.maxHeight - A.GetPoint("T",FALSE)))
            var/a_p2_x = abs(A.true_x - (A.maxWidth - A.GetPoint("L",TRUE)))
            var/a_p2_y = abs(A.true_y - (A.maxHeight - A.GetPoint("L",FALSE)))
            var/a_p3_x = abs(A.true_x - (A.maxWidth - A.GetPoint("R",TRUE)))
            var/a_p3_y = abs(A.true_y - (A.maxHeight - A.GetPoint("R",FALSE)))
            var/src_p1_x = abs(src.true_x - (src.maxWidth - src.GetPoint("T",TRUE)))
            var/src_p1_y = abs(src.true_y - (src.maxHeight - src.GetPoint("T",FALSE)))
            var/src_p2_x = abs(src.true_x - (src.maxWidth - src.GetPoint("L",TRUE)))
            var/src_p2_y = abs(src.true_y - (src.maxHeight - src.GetPoint("L",FALSE)))
            var/src_p3_x = abs(src.true_x - (src.maxWidth - src.GetPoint("R",TRUE)))
            var/src_p3_y = abs(src.true_y - (src.maxHeight - src.GetPoint("R",FALSE)))

            //get the vectors, find the length of the vectors, normalize the vectors, then take their cross product
            //if the cross product signs are equal, then the point is inside the triangle

            var/srcT2aT_X=src_p1_x-a_p1_x //srcT to aT (X)
            var/srcT2aT_Y=src_p1_y-a_p1_y
            var/srcT2aL_X=src_p1_x-a_p2_x
            var/srcT2aL_Y=src_p1_y-a_p2_y
            var/srcT2aR_X=src_p1_x-a_p3_x
            var/srcT2aR_Y=src_p1_y-a_p3_y
            var/aT2aL_X=a_p1_x-a_p2_x
            var/aT2aL_Y=a_p1_y-a_p2_y
            var/aT2aR_X=a_p1_x-a_p3_x
            var/aT2aR_Y=a_p1_y-a_p3_y
            var/aL2aR_X=a_p2_x-a_p3_x
            var/aL2aR_Y=a_p2_y-a_p3_y

            //srcT vars
            var/magSrcT2aT = sqrt((srcT2aT_X * srcT2aT_X) + (srcT2aT_Y * srcT2aT_Y) + 1) //sqrt((ax * ax) + (ay * ay) + (az * az))
            var/magSrcT2aL = sqrt((srcT2aL_X * srcT2aL_X) + (srcT2aL_Y * srcT2aL_Y) + 1)
            var/magSrcT2aR = sqrt((srcT2aR_X * srcT2aR_X) + (srcT2aR_Y * srcT2aR_Y) + 1)
            var/magAT2aL = sqrt((aT2aL_X * aT2aL_X) + (aT2aL_Y * aT2aL_Y) + 1)
            var/magAT2aR = sqrt((aT2aR_X * aT2aR_X) + (aT2aR_Y * aT2aR_Y) + 1)
            var/magAL2aR = sqrt((aL2aR_X * aL2aR_X) + (aL2aR_Y * aL2aR_Y) + 1)

            var/normSrcT2aT_X = srcT2aT_X/magSrcT2aT   // a/|a|
            var/normSrcT2aT_Y = srcT2aT_Y/magSrcT2aT
            var/normSrcT2aL_X = srcT2aL_X/magSrcT2aL
            var/normSrcT2aL_Y = srcT2aL_Y/magSrcT2aL
            var/normSrcT2aR_X = srcT2aR_X/magSrcT2aR
            var/normSrcT2aR_Y = srcT2aR_Y/magSrcT2aR
            var/normAT2aL_X = aT2aL_X/magAT2aL
            var/normAT2aL_Y = aT2aL_Y/magAT2aL
            var/normAT2aR_X = aT2aR_X/magAT2aR
            var/normAT2aR_Y = aT2aR_Y/magAT2aR
            var/normAL2aR_X = aL2aR_X/magAL2aR
            var/normAL2aR_Y = aL2aR_Y/magAL2aR
            //srcT cross product vars
            var/CP_srcT2aT2aL = (((normSrcT2aT_Y - normAT2aL_Y) - (normSrcT2aT_X - normAT2aL_X)) + ((normSrcT2aT_X*normAT2aL_Y) - (normSrcT2aT_Y*normAT2aL_X)))               //(AyBz-AzBy)i -(AxBz-AzBx)j +(AxBy-AyBx)k  //cross product with srcT to aT (using normalized vectors)
            world<<"CP_srcT2aT2aL=[CP_srcT2aT2aL]"
            var/CP_srcT2aT2aR = (((normSrcT2aT_Y - normAT2aR_Y) - (normSrcT2aT_X - normAT2aR_X)) + ((normSrcT2aT_X*normAT2aR_Y) - (normSrcT2aT_Y*normAT2aR_X)))
            world<<"CP_srcT2aT2aR=[CP_srcT2aT2aR]"
            var/CP_srcT2aL2aR = (((normSrcT2aT_Y - normAL2aR_Y) - (normSrcT2aT_X - normAL2aR_X)) + ((normSrcT2aT_X*normAL2aR_Y) - (normSrcT2aT_Y*normAL2aR_X)))
            world<<"CP_srcT2aL2aR=[CP_srcT2aL2aR]"
            //end srcT cross product vars
            //end srcT vars


I've found that most explanations for the cross product available on the internet are fairly scant in terms of accurate depiction of its components. As for the same side method, I'm supposing that I have to check if each cross product has the same sign in order for the the collision to return true. I could be completely wrong on this though, as it's been hard to dig up solid information on the subject.

I can't seem to get the sign of the cross-products to be the same at the correct time, if I drop below A with src the cross products tend to go negative, if I go above they tend to go positive.

I've been trying to figure out a triangle collision detection system using only 3 vertices and avoiding the sum of angles method for a very long time now, and would really appreciate some help.

I'll upload the executable or email it on request.
May 13 2008, 3:19 pm (Edited on May 13 2008, 3:29 pm)
I'm not exactly sure what you're trying to do here, but I assume at least part of it is trying to test whether a point is inside a triangle.

It helps if you consider the points of the triangle around in a clockwise motion; so we take points T, R and L in that order in your scheme.

Call the point you want to test "P". We denote a vector from "T" to "P" as TP, etc.

We can calculate the components of TP thus:
TP.x = P.x - T.x
TP.y = P.y - T.y


To test if P is inside the triangle TRL, we calculate the cross product of the vector for each side with the vector from the triangle vertex to P.

To calculate the cross products:
cT = TRxTP
cR = RLxRP
cL = LTxLP

Since these vectors are planar (z=0), the x- and y- components of the cross product will be zero, and we need only calculate the z-component in each case. Also, there is no need to normalize the vectors:

For example:
cT = (R.x-T.x)*(P.y-T.y) - (R.y-T.y)*(P.x-T.x)
is the z-component of the first cross product.

Now, if cT and cR and cL are all positive, the point P is inside the triangle TRL. If any are negative, the point is outside the triangle. If zero, the point is inline with one of the sided.
May 13 2008, 4:20 pm
In response to Hobnob
Hobnob wrote:
I'm not exactly sure what you're trying to do here, but I assume at least part of it is trying to test whether a point is inside a triangle.

Yep. I was trying to test src's T, but I knew I would have to test src's other 2 points after src's T checked out okay.

It helps if you consider the points of the triangle around in a clockwise motion; so we take points T, R and L in that order in your scheme.

So, since I was trying to use L to R, T to R, and T to L, that would screw up everything? It has to be T to R, R to L, and L to T?


Call the point you want to test "P". We denote a vector from "T" to "P" as TP, etc.


We can calculate the components of TP thus:
TP.x = P.x - T.x
TP.y = P.y - T.y

Do I still need the magnitude of the vector?

ex:

 
magSrcT2aT = sqrt((srcT2aT_X * srcT2aT_X) + (srcT2aT_Y * srcT2aT_Y) + 1)


To test if P is inside the triangle TRL, we calculate the cross product of the vector for each side with the vector from the triangle vertex to P.

To calculate the cross products:
cT = TRxTP
cR = RLxRP
cL = LTxLP

Since these vectors are planar (z=0), the x- and y- components of the cross product will be zero, and we need only calculate the z-component in each case. Also, there is no need to normalize the vectors:

For example:
cT = (R.x-T.x)*(P.y-T.y) - (R.y-T.y)*(P.x-T.x)
is the z-component of the first cross product.

I simply figured if the they were all on the same plane, 1 for instance, then x and y would remain unchanged in the formula. Is this what you're saying? I apologize for how stupid this must sound, but I actually have a writing background (yet I love to code).

Now, if cT and cR and cL are all positive, the point P is inside the triangle TRL. If any are negative, the point is outside the triangle. If zero, the point is inline with one of the sided.

If zero, P is inline with one of A's sides? So I should just include 0 in my checks?
May 13 2008, 6:11 pm
In response to Rockinawsome
Rockinawsome wrote:
Hobnob wrote:
It helps if you consider the points of the triangle around in a clockwise motion; so we take points T, R and L in that order in your scheme.

So, since I was trying to use L to R, T to R, and T to L, that would screw up everything? It has to be T to R, R to L, and L to T?

It doesn't matter what order you do the checks, just so long as the vectors you are defining point clockwise around the triangle. So R->L, T->R, L->T would work.

Do I still need the magnitude of the vector?

No.

I simply figured if the they were all on the same plane, 1 for instance, then x and y would remain unchanged in the formula. Is this what you're saying? I apologize for how stupid this must sound, but I actually have a writing background (yet I love to code).

The cross product of two vectors in the same plane is always a vector pointing directly into (or out of) that plane. For this case (with all points in the z=1 plane, say), it means that it's only worth calculating the z-component of the cross product, since its x- and y-components are always zero.

If zero, P is inline with one of A's sides? So I should just include 0 in my checks?

Best just to check it this way: if any of cT, cR or CL is <0, you have no collision. Otherwise, you have a collision. That way, there's no need to check explicitly if they're zero.


May 13 2008, 7:44 pm
In response to Hobnob
Here's the semi-final product of the advice you gave me. It works, but the odd thing is that when the point is inside the object the cross product returns all negatives instead of positives. Oh well, it works.

TriangleCollide(var/atom/A,var/BUMPED=FALSE,var/Dir2Move,var/INSIDEONLY=FALSE) 
            //if(istype(src,/turf/Collision/Triangle/)) return FALSE //leave until finished debugging
            
            var/pyAdd=0
            var/pxAdd=0
            
            if(!BUMPED)
                if(Dir2Move == NORTH) pyAdd += INSIDEONLY ? src.step_size : src.step_size + src.step_size
                if(Dir2Move == SOUTH) pyAdd -= INSIDEONLY ? src.step_size : src.step_size + src.step_size
                if(Dir2Move == WEST) pxAdd -= INSIDEONLY ? src.step_size : src.step_size + src.step_size
                if(Dir2Move == EAST) pxAdd += INSIDEONLY ? src.step_size : src.step_size + src.step_size
                
            var/a_p1_x = abs(A.true_x - (A.maxWidth - A.GetPoint("T",TRUE)))
            var/a_p1_y = abs(A.true_y - (A.maxHeight - A.GetPoint("T",FALSE)))
            var/a_p2_x = abs(A.true_x - (A.maxWidth - A.GetPoint("L",TRUE))) 
            var/a_p2_y = abs(A.true_y - (A.maxHeight - A.GetPoint("L",FALSE))) 
            var/a_p3_x = abs(A.true_x - (A.maxWidth - A.GetPoint("R",TRUE))) 
            var/a_p3_y = abs(A.true_y - (A.maxHeight - A.GetPoint("R",FALSE))) 
            var/src_p1_x = abs(src.true_x - (src.maxWidth - src.GetPoint("T",TRUE))) + pxAdd
            var/src_p1_y = abs(src.true_y - (src.maxHeight - src.GetPoint("T",FALSE))) + pyAdd
            var/src_p2_x = abs(src.true_x - (src.maxWidth - src.GetPoint("L",TRUE))) + pxAdd
            var/src_p2_y = abs(src.true_y - (src.maxHeight - src.GetPoint("L",FALSE))) + pyAdd
            var/src_p3_x = abs(src.true_x - (src.maxWidth - src.GetPoint("R",TRUE))) + pxAdd
            var/src_p3_y = abs(src.true_y - (src.maxHeight - src.GetPoint("R",FALSE))) + pyAdd


            //if the cross product signs are equal or one is 0, then the point is inside the triangle
            

            var/Px = 0
            var/Py = 0
            var/cT=0
            var/cR=0
            var/cL=0
            var/i=3
            while(i>0)
                switch(i)
                    if(1)
                        Px = src_p1_x //top
                        Py = src_p1_y
                    if(2)
                        Px = src_p3_x //right
                        Py = src_p3_y
                    if(3)
                        Px = src_p2_x //left
                        Py = src_p2_y   
                //cross products
                cT = ((a_p3_x-a_p1_x)*(Py-a_p1_y)) - ((a_p3_y-a_p1_y)*(Px-a_p1_x)) //cT = (R.x-T.x)*(P.y-T.y) - (R.y-T.y)*(P.x-T.x) //cT = TRxTP //rtpt rtpt
                cR = ((a_p2_x-a_p3_x)*(Py-a_p3_y)) - ((a_p3_y-a_p2_y)*(Px-a_p3_x)) //cR = RLxRP //lrpr lrpr
                cL = ((a_p1_x-a_p2_x)*(Py-a_p2_y)) - ((a_p1_y-a_p2_y)*(Px-a_p2_x)) //cL = LTxLP //tlpl tlpl
                world<<"cT=[cT] cR=[cR] cL=[cL]"
                i--
                if(cT<=0&&cR<=0&&cL<=0) return TRUE
            return FALSE