find the collision of a particle with a swept triangle. Given there is triangle: V in 3D space that transforms over time t -> t1 to V1, and a static point P is somewhere in 3d space, how can I determine if P ever collides with V, and if so at what value of t?
The transformation of the triangle from V -> V1 over time means the vertices Va,Vb,Vc each move linearly and independently in three dimensions to new vertex positions V1a,V1b,V1c. (Sorry about my notation). There are no constraints on the transformation of the vertices with respect to each other. The triangles at V and V1 representing the transformation may be any 2 triangles in 3d space.
 A: This type of problem is usually called "continuous collision detection". There is a substantial literature on this subject as you'll discover if you try a google search on those key words. It's rare that someone wants to do this for one triangle at a time. The literature has techniques for checking against large sets of triangles as well as generalisations to alternative shapes and more complex motion such as quadratic motion wrt time.
A: Consider the (mostly nontrivial) tetrahedron formed by the three moving points and P.  There is a determinantal formula for the volume of the tetrahedron, as well as one for the area of the triangle formed by the three moving points.  Now you have two formulas depending on t, one measuring signed tetrahedral volume, the other the signed area of the moving triangle.  If the area is nonzero at time t while the volume is 0 at time t, then you have a time when point P is in the plane of the triangle.  Then you can do some calculations to see if P is inside the triangle or not.  Otherwise, either the volume is nonzero (and thus no intersection between P and the triangle), or the triangle has zero area, and you have to check to see if P is collinear at that time with the other points, and also lies within the segment determined by the three points.
If you have more information about the trajectories, I may have more suggestions on how to find time t, if it exists.
Gerhard "Ask Me About System Design" Paseman, 2010.01.23
A: While this old question has been bumped to the front page, let me make a few remarks
that might help focus future searches.
First, in the specific problem posed (fixed point, moving triangle), it might be
simpler to fix the plane of the (morphing) triangle and transform the point accordingly.
Second, independent of that, there are very sophisticated software libraries available
for a variety of collision detection scenarios. The one maintained at UNC (Univ North Carolina) is among
the most robust:
see this link.
In particular, I-Collide might be the most appropriate software, because it exploits convexity.

 
 
 
 
 


 
 
 
 
 
Image from "I-COLLIDE: An Interactive and Exact Collision Detection System
for Large-Scale Environments"

 
 
 
 
 
(PDF download)

