# Realtime Collision Detection Code

This topic is 2977 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Just a few questions regarding the following code : ( Im not entirly sure if actually allowed to post this code, so i apologise if im not )
// Given segment pq and triangle abc, returns whether segment intersects
// triangle and if so, also returns the barycentric coordinates (u,v,w)
// of the intersection point
int IntersectSegmentTriangle(Point p, Point q, Point a, Point b, Point c,
float &u, float &v, float &w, float &t)
{
Vector ab = b - a;
Vector ac = c - a;
Vector qp = p - q;

// Compute triangle normal. Can be precalculated or cached if
// intersecting multiple segments against the same triangle
Vector n = Cross(ab, ac);

// Compute denominator d. If d <= 0, segment is parallel to or points
// away from triangle, so exit early
float d = Dot(qp, n);
if (d <= 0.0f) return 0;

// Compute intersection t value of pq with plane of triangle. A ray
// intersects iff 0 <= t. Segment intersects iff 0 <= t <= 1. Delay
// dividing by d until intersection has been found to pierce triangle
Vector ap = p - a;
t = Dot(ap, n);
if (t < 0.0f) return 0;
if (t > d) return 0; // For segment; exclude this code line for a ray test

// Compute barycentric coordinate components and test if within bounds
Vector e = Cross(qp, ap);
v = Dot(ac, e);
if (v < 0.0f || v > d) return 0;
w = -Dot(ab, e);
if (w < 0.0f || v + w > d) return 0;

// Segment/ray intersects triangle. Perform delayed division and
// compute the last barycentric coordinate component
float ood = 1.0f / d;
t *= ood;
v *= ood;
w *= ood;
u = 1.0f - v - w;
return 1;
}


// Compute intersection t value of pq with plane of triangle. A ray
// intersects iff 0 <= t. Segment intersects iff 0 <= t <= 1. Delay
// dividing by d until intersection has been found to pierce triangle
Vector ap = p - a;
t = Dot(ap, n);
if (t < 0.0f) return 0;


Why does he get the vector from a triangle point to the ray origin? The only reason i can think of is for returning a false intersection if we are intersecting a reverse facing triangle, (back face culling). If so, surely its still an intersection whether its back facing or not. The comments say its a ray/plane test. But i dont see how it is. Im not really understanding the purpose of this test.
// Compute barycentric coordinate components and test if within bounds
Vector e = Cross(qp, ap);
v = Dot(ac, e);
if (v < 0.0f || v > d) return 0;
w = -Dot(ab, e);
if (w < 0.0f || v + w > d) return 0;


Here, is he testing v and w against d due to the fact that they will be divided by d later on. So if they are more than d, then dividing them by d will result in a value more than 1.0f, which for barycentric coordinates, meaning the point is outside the triangle.

##### Share on other sites
Just about every line of this code is explained in detail in the book, across several pages.

##### Share on other sites
ah, ok. I havent read the whole chapter, ive just been reading bits that were relevant to my current problem, such as the above. I shall read through chapter 5 from the beginning to see where those bits i mentioned are explained.

##### Share on other sites
Hi.
I want to do this:
http://screamengine.extra.hu/rpi.jpg
I writed a custom CollisionPlane class, what has four (3d) point and normal vector. How can I know, a ray/line intersect this plane? (maybe two ray-triangle intersection? I think, it's too slow)

thanks,
csisy