Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
I've deleted some old comments that were only relevant to previous versions of the question. –  Scott Morrison Jan 23 '10 at 23:01
    
Julian, thanks for clarifying your question. However, you completely removed the background motivation. We generally like having that... –  Darsh Ranjan Jan 24 '10 at 2:40
    
Thanks Darsh. I removed the background it because I thought it was clouding the question a bit. Briefly, I want to write an algorithm that will apply a force to a particle if it is in the envelope between 2 topologically identical meshes. I'm simulating the behavior of fishes navigating their way around rocks in murky water. For clarity, I re-stated it as a collision with a moving triangle. Originally I was looking for computer code, but I would love to understand the mathematics too. Many thanks to yourself and Scott for coaxing me to think more clearly about it. –  Julian Mann Jan 24 '10 at 3:26

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
Thanks for this. The terminology definitely helps, I will try to find some code in the literature. –  Julian Mann Jan 24 '10 at 4:39
    
Also search on "continuous-time collision detection". –  Dan Piponi Jan 24 '10 at 16:07

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

share|improve this answer
    
Gerhard "has 5 unregistered accounts" Paseman? –  Harry Gindi Jan 23 '10 at 23:34
    
Yes. I am weighing the advantages against the disadvantages of registering. If you want to lobby me personally about registering, you can check a sci.math post header I made recently for contact info. –  Gerhard Paseman Jan 23 '10 at 23:39
    
If you're interested, please tell us your reasons for not registering over at meta. I'm bamboozled! –  Scott Morrison Jan 24 '10 at 1:12
    
Thanks Gerhard, I understand your description pretty well. I can visualize the tetrahedron and triangle and the conditions under which the P is on the triangle. I'm trying to find t if it exists, algorithmically and I'm not sure what other specific information I can give regarding trajectories. –  Julian Mann Jan 24 '10 at 4:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.