# Volumetric Trace vs. Triangle Approach?

This topic is 3271 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### 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 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 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 maxbentering 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 * tp_collision = pb + vb * ttherefore 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 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.

1. 1
2. 2
3. 3
Rutin
12
4. 4
5. 5

• 26
• 10
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633695
• Total Posts
3013382
×