🔒 Locked

Moving point/triangle intersection

Started by Chicktopus Apr 25, 2011 at 12:04 AM 1 replies 2.6k views

Original Post

Apr 25, 2011 at 12:04 AM

Hey guys. I've been having a little difficulty getting my head around collision detection. I thinking perhaps moving point/triangle intersection would be the most appropriate method to use to test if a sphere is intersecting with what is essentially a plane with square holes in it. The holes are 2cm by 2cm and the spheres are 3cm by 3cm, so the idea is that a sphere can only partially sink in to the hole if it's resting on it. The spheres are also going to have to collide with each other and a bounding cube that surrounds the environment.

As the title suggests, I'm thinking moving point/triangle intersection might be a good idea for this as I have some notes on how that works, I've been looking through the maths and I'm having some difficulty understanding what's going on.

Basically, I have this to contend with:

Where the triangle is defined by points p1, p2, p3

The sphere starts at q0, moving to q1 in the time interval [0,1], i.e. assume unit time step, dt=1

q(t) = (1 - t)q0 + tq1 //ok, I get that. It's the path of the point

p(u,v) = p1 + u(p2 - p1) + v(p3 - p1) (1) //what the hell are u and v in this context? (they're actually alpha and beta in the source I'm using) . I'm aware I'm supposed to plug in t from later to get them, but how?
simultaneous equations?
u, v >= 0
u + v <= 1

and

(1 - t)q0 + tq1 = p1 + u(p2 - p1) + v(p3 - p1) //ok, so if the result of this is in the range of 0 - 1, there's a collision

n = (p2 - p1) x (p3 - p1) //I can only assume 'n' is the normal to the triangle
:.
((1 - t)q0 + tq1).n = p1.n //and plugging the result of t from thisin to (1) is supposed to give these mystery u and v values. Great!

So basically my question is; what the hell are u and v?

Zakwayda

Apr 25, 2011 at 8:53 AM

First, I'm not entirely sure that moving-point-vs.-triangle intersection testing is the optimal solution here. What you describe (specifically the part about spheres coming to rest in recessed areas) will likely require a somewhat more involved approach. It might be that using an existing physics engine would be preferable for something like this.

As for your question though, u and v are the parameters for a parametric representation of the triangle. If you think of the triangle as having a single vertex a and two edges touching that vertex, e1 and e2, then the parametric form for the triangle is:

p(u, v) = a + u*e1 + v*e2
Any point for which u, v >= 0 and u + v <= 1 will lie on the triangle. (Note that the above form is simply a rearrangement of the barycentric form.)

The above is of course just another way of writing what you posted above. If you're still unsure of the geometric significance of u and v, try drawing a picture of a triangle and labeling the vertex and two edges. Basically, the above equation says, 'start at a, move along e1 by the fraction u, and then move along the vector e2 by the fraction v'. Wherever you end up, that's the point corresponding to (u, v).

(That's an informal explanation of course, but perhaps it'll help clarify things somewhat.)

The problem you're trying to solve is essentially a linear component vs. triangle intersection test, which is pretty well-documented online and elsewhere. If you need some more references, try searching for 'raycast triangle' or 'ray triangle intersection' and you should be able to find some more examples to work from.

wildbunny

Apr 25, 2011 at 1:21 PM

It sounds like what you actually want is moving sphere vs triangle?

I would turn to the Minkowski Difference to solve this problem: Inflate the triangle by the sphere, sphere reduces down to a point and then you're dealing with ray vs inflated triangle, which is easy to solve via an iterative method:

You will need a function to give you distance from point to the inflated triangle and the normal at that point, then you can iterate using Gino Van Den Bergen's iterative ray-cast technique... Please check my blog article for more details - in the Continuous Linear section

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

Of course, if you don't want to iterate you can solve this by ray-casting at the inflated triangle assembled from spheres and flat triangles, but in all honesty it's much, much easier to catch all the special cases using the iterative solution, because there is less code to write

Cheers, Paul.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.