Sign in to follow this  
Pcube

Volumetric Trace vs. Triangle Approach?

Recommended Posts

Hi, I didn't see any other topics related to a question such as this, and I'd like some insight on a volumetric trace method I've been working on. The collision detection system I have in place is apriori and requires swept volumes to find the instances of collision, and lately I've been requested to work on a volumetric trace. I'm not sure if my terminology is correct, so, if I'm butchering the concept, by volumetric trace all I mean is a non-zero extent raytrace, such as tracing out a prism instead of a ray. Basically, the goal is to get the point of first contact when sweeping a convex face (for simplicity, always a quad) through 3d space into a triangle. My current algorithm is... not very elegant, but gets the job done. The way I think of tracing a face through space is by thinking of the extruding face as forming an OBB, so the question is, after finding points of contact between the OBB and triangle, which point of contact is "closest" to the sweeping face? My algorithm is basically the dumb approach, which is the following: There are three cases for finding a point of intersection between the sweeping quad and the triangle. First, a vertex of the triangle is a candidate if it is contained within the sweeping OBB. Second, a collision with one of the triangle's legs may occur, so to find this, find the intersections (if any) between the triangle's legs and the 6 planar polygons of the sweeping OBB. Finally, there is the corner case where the triangle is being pierced, such that none of the points of the triangle are in the sweeping OBB, and none of the triangle's legs are penetrating one of the sides of the OBB, BUT rather one of the line segments of the OBB are piercing the triangle... All in all, a real mess just to obtain a set of potential colliders. First I check all points of the triangle being in the prism (18 checks), then check every leg of the triangle against every face of the OBB (24 traces/checks), then finally check every line segment of the OBB against the triangle (10 traces/checks). As you can proably guess, not very efficient or elegant! :) Oh yeah, then I finally take each candidate point and trace back with the negation of the sweeping vector to the sweeping face of the OBB, and check the distance. I then see which candidate point is closest to the sweeping face, and the process is complete. I've read about how to use the SAT to determine points of intersection, but I'm not sure how useful it will be here, since I'm looking for which collision has the soonest "time", and (to my knowledge) SAT provides Boolean information about collisions (though with modification can provide penetrations, but I don't think that will help here.. correct me if I'm wrong!). Oh, and when I talk about optimization, I mean of the trace function itself... my surrounding routines that call it will first use early out tests such as back-face culling, SAT, bounding volumes, etc. before resorting to the brute force check; I was just wondering if there's another approach to the brute force check itself... I've got more info on my site and am willing to provide a demo executable to anyone who would care to check it out, here's a link to an image displaying what I'm talking about: http://udhq.host22.com/pics/VolumetricTrace.JPG Thanks in advance for any insights!! -Pravin

Share this post


Link to post
Share on other sites
I'd recommend you look into the swept SAT algorithm. Should be much simpler.

this is an approach specific to AABBs although it can be adapted to regular convex shapes.

here is a demo for 2D polygon, again, that can be re-shaped for regular 3D convex shapes.

and here is an example for spheres versus polygons. Spheres are particular, you cannot apply the SAT for them, as they have no faces or edges.

Share this post


Link to post
Share on other sites
Thank you very much! The swept SAT seems intriguing, though at the moment I'm still trying to understand the concept. I'm still not sure if I can extract the exact point of collision, which is a requirement, though I do see how I could extract the time of the collision. I'll analyze these examples too, I'm sure anything is better than the brute force method I'm currently employing. :)

EDIT: Now that I think about it, if anything, the swept SAT test will at least provide quick boolean information for a nice early-out test.

EDIT 2: I think I've got it! I read your (very well written) paper on the swept SAT algorithm, and I see that it is indeed what would be required for this trace.

My logic is that all I have to do is sweep the slab of the quad (a plane) forward by means of a ray, while expanding the triangle's slab appropriately to keep the difference in space between the two constant. Now it is just a simple ray->slab intersection test, from which I can get the time. Now, with this time, for the initial contact point, I can just advance the quad forward in time until it is at the frame of first contact with the triangle. Finally, I'd have to do some point in triangle or edge in triangle checks to get the actual intersection point (or line segment) shared between the quad and triangle.

My only concern at the moment is how to get a slab representation of a single triangle... Intuitively, it is just a plane, but I'm still trying to convince myself that it will fit the algorithm. There are probably a lot of special case optimizations as well with this in mind.

-Pravin

[Edited by - Pcube on December 29, 2009 4:21:25 AM]

Share this post


Link to post
Share on other sites
I think it's probably better to take a step back.

The SAT works by reducing a 2D / 3D collision test into a set of 1D tests.

You do that by cherry-picking lines of projections, and calculating the intervals of the shapes on those axes. So, you will end up with two intervals, one for each object [mina, maxa] and [minb, maxb]. Finding intervals can be as simple as doing a dot product of the axis against all the vertices of each shape, but there are shortcuts (for AABBs, OBBs and so on), and taking the min and max value.

For the swept test, and for each axis, you will need the projection of the velocities on the axis, and you will get a time interval defining where the objects start intersecting (the enter time), and stop intersecting (the exit time). each axis would have a pair [t_enter, t_leave].

Example :
Quote:


mina maxa va
|--------------|------>
<----|--------------|
vb minb maxb


entering collision :
---------------------

mina maxa va
|--------------|------>
<----|--------------|
vb minb maxb


exitinging collision :
-----------------------

mina maxa va
|--------------|------>
<----|--------------|
vb minb maxb


the equation to detect when maxa == minb (the time the two intervals start intersecing), and the time when mina == maxb (the time the two intervals stop intersecing) is relatively easy.

Considering the 1D case where two points pa and pb move along the same direction at speed va and vb.

Quote:

at time of collision (t)
p_collision = pa + va * t
p_collision = pb + vb * t

therefore
t = (pb - pa) / (va - vb)


so, detecting when the point (mina, va) and (maxb, vb) collide, and points (maxa, va) and (minb, vb) collide is straight forward.

But because the interval A could be on either side of interval B, and that the signs of va and vb could be anything, you need to re-order those time so that t_enter is always <= t_leave. So finally...

Quote:

t0 = (maxb - mina) / (va - vb);
t1 = (minb - maxa) / (va - vb);
t_enter = min(t0, t1);
t_leave = max(t0, t1);


t_enter and t_leave tells you when the two 1D intervals [mina, maxa] and [minb, maxb] enter and exit an intersection state.


Now, if you take two axis aligned boxes in 3D, the axes of interest would be the cardinal axes (X, Y and Z). On each of these axes, you will have those time intervals describing when the boxes enter and exit a collision along these axes.

Quote:

[tx_enter, tx_leave].
[ty_enter, ty_leave].
[tz_enter, tz_leave].


If all these three intervals do not overlap, the boxes miss the collision.

Else, the time the two boxes enter and exit a collision would be the intersection of the three time intervals, on the X, Y, and Z. In essence, the time of entering a collision would be the maximum of the enter time of all the axes.

in short you can reduce the logic to :

Quote:

t_enter = max(max(tx_enter, ty_enter), tz_enter);
t_leave = min(min(tx_leave, ty_leave), tz_leave);
if(t_enter > t_leave) return NO_COLLISION;


In my code, the logic is the same, but shuffled around so that I get early exits. To to the logic above, you need to do the calculation on the tree intervals first before detecting that a collision is missed. In most cases, a collision will be rejected after one or two tests.

The difference between two AABBs test and any other convex shapes, is the axes of projection and the number of axes.

In 2D, the axes you cherry-pick are basically the normal of the edges of the two shapes. If you have two AABBs, you have only two axes to consider, since the each normal, for each box, is along going the X and Y axis. The sign doesn't matter, you just need to consider a unique direction. If you don't, you will just get redundant tests, and less efficiency.

In 3D, you will need to consider the face normals, and the cross products of every edges of A against every edges of B. Again, if your two shapes have discernable properties (such as AABBs, OBBs, quads), you don't need to introduce redundant tests.

For example, two AABBs in 3D only require three tests (the X, Y and Z axis, as all edges and faces have normals aligned with these axes).

Two OBBs require 3 face normals + 3 face nromals + (3 edge directions * 3 edge directions) = 15 tests.

A quad against a triangle, you will need 1 + 1 + (2 * 3) axes of projection.

Note that polygons that are coplanar would require a slightly different test in 3D(a 2D version where you take the normals of the edges of the polygons), but these are usually not very useful in 3D collision detection (you usually sweep at least one volume).

Hope I haven't confused things.

Share this post


Link to post
Share on other sites
And to find the point of contacts, it's a little bit more complicated. [grin]

Once you found the time of collision, and the direction of the collision, you can use the axis to find the 'footprint' of each shape along the collision path, the support features, which in 3D, could be a single vertex, an edge, or a convex face.

To do that first, you need to find out what the normal of collision is. This is not difficult, if instead of considering your collision intervals [t_enter, t_leave], you consider [(t_enter, n_enter), (t_leave, n_leave)], where n_enter and n_leave are the direction of the axis of projection.

As you reject and accept each pairs (in the min() and max() sorting test), you will have the normal of the features when entering the intersection state, and when exiting the intersection state.

In collision detection, only the enter time is useful (you don't really care when objects stop intersecting, only when they start intersecting).

The footprint of each objects at the start of the intersection is basically the set of vertices that are either the 'farthest' along the normal of collision, of the 'nearest'. If you consider a box sitting on a table, the feature of the box would be the face at the bottom, the feature of the table would be the top surface of the table.

Once you have the two features that are colliding, you will get one of these potential cases.

vertex-face
edge-edge
edge-face
face-vertex
face-edge
face-face

The other case are not likely (vertex-vertex, vertex-edge, ...), due to the way the SAT works, but you can consider them for completion.

Vertex-face and face-vertex are the simplest and most common. The contact point is simply the vertex itself.

edge-edge is a bit trickier to compute, but it is basically the point where the edges are touching.

the face-edge case is a bit more tricky. But if you look down on the face and see the edge, the solution is obvious. You just need to clip the edge with the sides of the face (which will be convex, so the clipping is very easy).

the face-face case is a bit more complicated, but not much. Looking down the two faces (they will have colinear normals and be coplanar at the time of collision), you can see that the resulting contact points can be found by clipping one face with the other face.

this is in fact relatively easy to compute, especially since your faces are both convex.

All that should give you the time of collision, as well as the contact points. You can also consider intersections, in the collision detection sense, using the SAT and finding the MTD.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this