Monthly Archive for September, 2009

I’m using point vs level collision for OpenGTA2 maps, and it is implemented by tracing few rays to where pedestrian may go, as I said in previous post. In this post I will try to describe how this ray tracing is actually implemented – it’s a very simple algorithm, really.

First, we will need this illustration (this is the situation we’re having, with our segment we’re tracing against that triangle):

Before even attempting to check if this line collides with the triangle, let’s just compute our triangle parameters (two vectors that define it, and triangles normal):
V1 = p2 - p1;
V2 = p3 - p2;
triNormal = Vector3f::Cross(V1,V2); //cross product: V1 x V2

Also we should compute vector for our line (let’s not normalize it… you’ll see why later):
lineVector = (lineEnd - lineStart);

Now, there’s instantly first thing we can do – let’s check if our segment (line) is parallel to our triangle. This would mean 90 degree angle between triangle normal and line vector (they are perpendicular). If this happens, then their dot product (Vector3f::Dot(triNormal,lineVector) in OpenGTA2) will return value of zero. If that is so, we return false, because there is no collision for sure.

Also, if their dot product is higher than zero, they are facing different direction (cosine of angle is higher than zero, that means angle between them is less than 90). That means we return false as well.

Now, if triangle normal and line vector are facing different directions, the triangles plane and the line collide for sure – let’s find the collision point. Now through some math we can solve equation for point position on the plane. Warning vector math ahead.

1. Any point on line can be written as lineStart + lineDirection * t, where t is some scalar constant. lineDirection vector must have length of 1. t is the distance from lineStart to this point.
2. For our case lineVector = lineDirection * |lineStart - lineEnd|, because its direction is same as our line direction, and its length matches length of entire segment.
3. This means we can write collision point position as lineStart + lineVector * distance, where distance is equal to T / |lineStart - lineEnd|.
4. This means that distance will be 0 in lineStart, it will be 1 in lineEnd. It will be over 1 if collision point is beyond this segment, and under 0 if this collision point is before this segment (but we will never occur the latter).
5. Now let’s find vector from P1 to our collision point (basically it’s location of this point on our plane, sort of): lineStart + lineVector * distance - P1
6. Now we use simple equation that tells us whether point lies on triangle – if the point lies on triangle, angle between the vector to the point we found in earlier step, and triangle normal will be 90 degrees. Cosine will be zero, so we can use dot product to find this out: triNormal . (lineStart + lineVector * distance - P1) = 0

Now let’s just perform a series of transforms on it:
triNormal . (lineStart + lineVector * distance – P1) = 0
triNormal . (lineStart – P1) + triNormal . (lineVector * distance) = 0 (we opened the parentheses)
triNormal . (lineStart – P1) + distance * triNormal . lineVector = 0 (got the distance out of the dot product, it’s a scalar, we can do it)
distance * triNormal . lineVector = -triNormal . (lineStart – P1) (just moving some junk to the right…)
distance = -(triNormal . (lineStart – P1))/(triNormal . lineVector) (it’s a scalar, so we divide by it… oh wait, that’s an answer! yay!)

This is the result of our mathematical ramblings:
float distance = -Vector3f::Dot(triNormal,lineStart-p1)/Vector3f::Dot(triNormal,lineVector);

Okay, so as I said before, to check if our segment collides we just need to check if this distance is in range of 0 to 1.

But wait! There’s more! You noticed we didn’t check if our point actually lies inside the triangle. To perform that we will do what they call a clockness test. This test tells you if three vectors are listed clockwise, or counter-clockwise (if you start with vector 1, then you move on to vector 2, and then you move on to vector 3).

Clockness test for a triangle is this:

1. Compute normal for triangle that is defined by P1, P2 and our collision point.
2. Check if normal is same direction as triNormal (this means ((P2 - P1) x (CollisionPoint - P1)) . triNormal is larger than zero)
3. Also repeat for these pairs: P2, P3, and P3, P1. If clockness on all of these is same, then our point lies within our triangle.

Okay, well, if you don’t understand that, don’t worry, I’ll just give you the function that performs clockness test (look below).

Well, all this should suffice for a ray/segment collision check. To summarize: check if ray is parallel (note: don’t forget to actually check if ray lies within triangle, I forgot to do this, I’ll fix this and will post a new post later), check if ray aims at triangle plane, check if collision point lies within triangle.

Continue reading ‘OpenGTA2 segment tracing’