Home | Gaming | Programming | Play Online | Contact | Keyword Query
Games++ Games & Game Programming

GAMES++
Games++ Home
Games++ Gaming
Games++ Programming
Beta Testing Games
Free Online Games
Hints & Cheats

BROWSER UTILITIES
E-mail This Page
Add to Favorites

SITE SEARCH

Web Games++

AFFILIATES
Cheat Codes
Trickster Wiki
Game Ratings
Gameboy Cheats
PlayStation Cheats
BlackBerry Games
Photoshop Tutorials
Illustrator Tutorials
ImageReady Tutorials

ADVERTISEMENT

ADVERTISEMENT

Collision Detection

Vertex-in-Triangle Check

Collision Detection Tutorial

:: Vertex-in-triangle check

The last tutorial thought you how to check if a ray intersect with a plane and what's the distance to that plane (as long as there is any intersection).

Since we only use triangles (which aren't inifinite), we need to check if that ray intersects also with a triangle that is ON the plane.

To do that, you need to find out first the interesction point on the plane.

If we mark the distance as t, then the intersection point's math-expression would something like -

intersection point = Ray.Origin + Ray.nVector * t


Makes sense right? :-)

Now we need to check if that point is inside the triangle.


what's this mess?



As you can see, the figure has 3 vertices (vtx0, vtx1, and vtx2) which belong to the triangle, and a vertex - vtxPoint which is the intersection point.

The simplest way to check if this vertex is inside the triangle would like that -- construct 3 vectors from the intersection poit to each vertex of the triangle (that's vec0, vec1, and vec2), and normalize them.

If the sum of the angles between the vectors ( 0 and 1 , 1 and 2 , 2 and 0 ) is 360 degrees (or two pi radians), then the vertex is inside the triangle, otherwise.. it's not.

Well, that's 100% right, but it won't work. It will never be exactly 2pi, it will be close it. (because of floating point precision mistakes).
The solution for that problem is quite straightforward - as long as it is close enough to 2pi we'll call it inside.
- Close enough? "0.1f close" is ok.

inline bool VertexInTriangle(vec3 vtxPoint,
†††††††††††††††††††††††††††† vec3 vtx0,
†††††††††††††††††††††††††††† vec3 vtx1,
†††††††††††††††††††††††††††† vec3 vtx2)
{
††† double dAngle;
††† vec3 vec0 = Normalize( vtxPoint - vtx0 );
††† vec3 vec1 = Normalize( vtxPoint - vtx1 );
††† vec3 vec2 = Normalize( vtxPoint - vtx2 );
††† dAngle =
††††††† acos( DotProduct(vec0,vec1) ) + 
††††††††acos( DotProduct(vec1,vec2) ) + 
††††††††acos( DotProduct(vec2,vec0) ) ;
††† if( fabs( dAngle - 2*pi ) < epsilon )
††††††† return true;
††† else
††††††† return false;
}


Different values of epsilon

0.001

0.01

0.5

These images were ray traced using the above code for intersection checks.

don't use this method for ray tracing




Notes:

1) This point-in-triangle algorithm isn't the best there is (actually it's pretty bad :), though you probably have guessed that already. There are better ways to do that, but this one is the simplest IMHO.

2) This algorithm with slight modifications should work with other convex primitive types (quads for instance)


Ray - Triangle intersection.

Copyright © 1998-2007, Games++ All rights reserved. | Privacy Policy