2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I've deleted some old comments that were only relevant to previous versions of the question. $\endgroup$
    – Kim Morrison
    Commented Jan 23, 2010 at 23:01
  • $\begingroup$ Julian, thanks for clarifying your question. However, you completely removed the background motivation. We generally like having that... $\endgroup$
    – Darsh Ranjan
    Commented Jan 24, 2010 at 2:40
  • $\begingroup$ 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. $\endgroup$
    – Julian Mann
    Commented Jan 24, 2010 at 3:26

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for this. The terminology definitely helps, I will try to find some code in the literature. $\endgroup$
    – Julian Mann
    Commented Jan 24, 2010 at 4:39
  • $\begingroup$ Also search on "continuous-time collision detection". $\endgroup$
    – Dan Piponi
    Commented Jan 24, 2010 at 16:07
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Gerhard "has 5 unregistered accounts" Paseman? $\endgroup$
    – Harry Gindi
    Commented Jan 23, 2010 at 23:34
  • $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Commented Jan 23, 2010 at 23:39
  • $\begingroup$ If you're interested, please tell us your reasons for not registering over at meta. I'm bamboozled! $\endgroup$
    – Kim Morrison
    Commented Jan 24, 2010 at 1:12
  • $\begingroup$ 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. $\endgroup$
    – Julian Mann
    Commented Jan 24, 2010 at 4:36
2
$\begingroup$

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.

          Frame2
          Image from "I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments"
          (PDF download)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .