# Ray->triangle collision math seems to not work?

First time asking, pardon any mistakes I make :)

I am programming a game from scratch, and the collision detection is giving me issues. I have AABB in place to check proximity, and if that reacts, the two models are checked by having each vertex in the moving model be a line going from the vertex' current position to its intended position. That line then gets checked against each triangle polygon in the 'obstacle' model.

My (current...) problem is that the math seems to react wrongly in the early part of that ray-triangle check (code below). I try simply to see if the two ends of the ray (vertex origin and vertex destination) are on opposite sides of the polygon plane (if they are not, the ray could not possibly be going through the polygon). I do this by getting a (not yet normalized) normal from the polygon via cross product. Then I dot the ray ends' positions with that. If it's one positive and one negative dot product, they should be on either side. Problem is, that never happens, even when i run models right through each other in tests. Never a 'positive & negative' result.

Can anyone spot my mistake(s)??

Code:

double Dot(Vec3 *a, Vec3 *b)
{
double d = a->v[0] * b->v[0] + a->v[1] * b->v[1] + a->v[2] * b->v[2];
return d;
}

Vec3 CrossProduct(Vec3 *a, Vec3 *b)
{
Vec3 v;
v.set(
a->v[1]*b->v[2] - a->v[2]*b->v[1],
a->v[2]*b->v[0] - a->v[0]*b->v[2],
a->v[0]*b->v[1] - a->v[1]*b->v[0]
);
return v;
}

bool Collide(Vec3 *a, Vec3 *b, int target, int p)
{
// a and b are the ray points in global space
// target is the index number of the obstacle model
/// p is the triangle polygon being checked (in a loop not included here)
Vec3 poly_vert[3] = {entities[target].vertex[entities[target].poly[p].vertex[0]].pos
,entities[target].vertex[entities[target].poly[p].vertex[1]].pos
,entities[target].vertex[entities[target].poly[p].vertex[2]].pos};
// poly_vert is the three vertices of the triangle polygon
// Subtractions so poly_vert[0] essentially becomes the 0,0,0 center of the universe
Subtract(&poly_vert[2],&poly_vert[0]);// Essentially, the vector from
polyvertex 0 to polyvertex 2
Subtract(&poly_vert[1],&poly_vert[0]);// Essentially, the vector from
polyvertex 0 to polyvertex 2
Subtract(a,&poly_vert[0]);
Subtract(a,&entities[target].pos);// Make it relative to the obstacle model
Subtract(b,&poly_vert[0]);
Subtract(b,&entities[target].pos);// Make it relative to the obstacle model

Vec3 poly_cross;
poly_cross = CrossProduct(&poly_vert[1],&poly_vert[2]);
double da = Dot(a,&poly_cross);
double db = Dot(b,&poly_cross);

if (da*db >= 0){return false;}
return true;
}

• I am currently DESPERATELY trying to find out how I edit the question to make the code slip-up go away, pleeeaaaase be patient! Jan 27, 2015 at 10:57
• What algorithm are you using? (source) Jan 27, 2015 at 11:07
• I am using what you see above. It is not a straight copy of any algorithm, because I prefer to know every angle of what I use, and no other algorithm provided that, so I am making my own. This is "from scratch" collision math. Or it's supposed to be, anyway :-( Jan 27, 2015 at 11:10
• First of all: A and B are ray points? Ray points what? There should be origin and (normalized)direction. Second, you seem to be modifying input data rather than calculating something from it. Didnt you mean Vec3 edge1_dir = poly_vert[2] - poly_vert[0]; ? Jan 27, 2015 at 11:13
• A is the starting point of the ray, B is the end point of it. I have tried normalizations across the board, but they seem to do nothing. A and B should be dotted to the normal of the plane, and I only need to know if they are positive or negative, not their exact size. But I do suspect that there is a very specific set of values that need normalization, it's just that none that I have tried have changed anything. At all. And this is not a full collision test, it only tests whether the ray penetrates the plane of the triangle polygon. That's all it is expected to do. Jan 27, 2015 at 11:16

I think these two lines are not needed:

Subtract(a,&entities[target].pos);// Make it relative to the obstacle model
...
Subtract(b,&entities[target].pos);// Make it relative to the obstacle model


I don't see why are you adding them. I think that if you remove them it should work as intended.

EDIT:

when you calculate the normal to the triangle (poly_cross), this vector is also the normal to the plane containing this triangle (you have to normalize it). So, as dot product of the plane normal and some point is the distance to the origin of a parallel plane passing through this point, what you can do is:

Vec3 n = poly_cross.normalized(); // you have to create this function

Vec3 poly_vertex = Add( poly_vert[ 0 ], entities[ target ].pos ); // I am using a new function Add to add two vector2 here

double D = dot( n, poly_vertex );
double D1 = dot( n, a );
double D2 = dot( n, b );


where D, D1 and D2 are distances to the origin of parallel planes passing through triangle vertex and a and b points.

So after that just check the sign of:

D1 - D

D2 - D

if both are same sign then a and b are in the same side of the triangle

• I tried removing them, and now at least it reacts. It just reacts... wrong. It stops at the wrong moments and changes entirely when I turn. Hmm... In any event, the two lines are there because all vertices (end hence, the polygons made of them) are positioned relative to the model's position in global space. Whether or not I'm doing it right... well... it ain't right yet, but at least it -reacted- :-/ Jan 27, 2015 at 14:27
• I have just edited my answer with a possible solution. Jan 27, 2015 at 16:23
• It does better now, but it still goes all wonky half the time, hitting things that aren't there or going through stuff. I do agree with the idea you propose, though, and to me it should also have worked. But somehow, it doesn't. [insert desperate cursing and cussing, then sulking] Jan 28, 2015 at 16:05
• Forget that! It.... seems to work!! And even better, your solution makes complete mathematical sense to me (i.e. I get what you're doing, which is golden in this work :-D ). I did have to remove the Subtractions of poly_vert[0] from a and b, as well, which gave some 'interesting' test results, but it seeeeeems to work now! Thanks!! Jan 28, 2015 at 16:21