12 replies to this topic

[Nyx]

Just for fun, I'm tinkering with collision detection. I'd like to implement collision detection between two OBBs and between OBBs and convex polygons.

So far, all the helpful documentation I found is this:
http://www.gamasutra...018/Gomez_5.htm

This page details how to implement the separating axis theorem intersection test. It's quite helpful, but it leaves quite a few holes to be filled, in my opinion... Such as:

1) This is only an *intersection test*. If I'm doing this every frame, and objects are moving very fast, I could potentially have two objects going through each other, and no collision being detected. Nobody seems to be addressing this problem in any amount of detail anywhere on the web. People mention it, but provide no useful solution.

So far, my best idea is to construct an AABB around the whole space both objects could span and test those for intersection. This tells me if the two objects could "possibly intersect". If so, I could then go and subdivide the time frame into smaller intervals to test more thoroughly for collisions... This is not bulletproof, but reduces the likelihood of missing collisions a fair bit.

2) This intersection test only gives me boolean information (yes or no). It doesn't give me an intersection point. This seems problematic because it seems to me like if you want to have the objects properly react in terms of rotation when they collide, you'd want to know where they touch, relative to their center of mass.

3) I'm guessing you can use the separating axis theorem for testing polygons vs. OBBs, but I'm not sure how. Do you just take the two axes of the polygon to be two orthogonal vectors on its plane? Will that work?

------------------------------------------------------------------

As a second problem, I'm not quite sure how to implement collision reaction to take rotation into account. If we ignore rotation, what I did in the past was to just cancel component of a moving object's velocity that goes in the direction of the surface normal of the other object that was collided with.

In more realistic physical terms, it seems like energy has to be conserved. If two moving objects collide, the motion of both should be altered, but they might also acquire a rotational component. However, I'm not sure how to distribute the energy here. Clearly, making an object rotate faster requires energy, and so does making it move... So how should the energy be distributed between rotation and movement?

I'm guessing I also need to make my objects somewhat "bouncy" if I want my simulation to look anywhere near realistic.

[imerso]

there are some solutions for the fast moving case, like "swept obb", "swept ellipsoid" and "swept sphere"...

[Reedbeta]

The usual solution for #1 is to construct a larger volume that encloses the volume of space "swept out" by the object during a timestep. For a convex polytope moving linearly this is easy; find the "silhouette edges" (so to speak) with respect to the direction of motion, and extrude them along the direction of motion - much like constructing a shadow volume, with the caps formed by the object's actual polygons at its initial and final locations. For nonlinear motion (in particular rotational motion) the swept volume is no longer polygonal, but people usually just approximate the motion as linear in this case.

This isn't bulletproof; it's possible to get false positives
if two fast-moving objects cross paths, but it does eliminate the problem of objects "phasing" through walls and so forth.

For #2, I'm sure there's some clever way to extract a heuristic collision location and normal from the separating axis test, but unfortunately I've never seen this discussed online. If you use the method of doing a bisection search through the timestep to identify the precise moment of collision, you can probably identify a particular vertex and face or edge and edge that are "responsible" for the collision and get the collision point and normal from those.

[karligula]

I'm no math whizz but is it possible to generalise nurbs surfaces into 3d? By which I mean having a nurbs volume? You could then create a nurbs volume for each face of the moving box, so imagine extruding each face into a nurbs volume representing how the box face moves over time. These volumes would have an intrinsic s,t,u space. Then, possibly you could transform every other surface in the world into the nurbs volume intrinsic space (alright anything that is close enough to be worth bothering with). This woud give you lots of twisted faces to compare with a nice axis aligned box. Then you could calculate the precise time of intersection by calculating the smallest u, assuming u is the dimension extruded along.

A very brute force method but I reckon it would work, assuming someone could work out the maths. It might also be able to take into account accelerating objects, you'd maybe use different tangents for the two ends of the nurbs volume?

[Nyx]

Reedbeta said:

The usual solution for #1 is to construct a larger volume that encloses the volume of space "swept out" by the object during a timestep. For a convex polytope moving linearly this is easy; find the "silhouette edges" (so to speak) with respect to the direction of motion, and extrude them along the direction of motion - much like constructing a shadow volume, with the caps formed by the object's actual polygons at its initial and final locations. For nonlinear motion (in particular rotational motion) the swept volume is no longer polygonal, but people usually just approximate the motion as linear in this case.

Seems easier said than done. Constructing the volume could be challenging in itself. What kinds of assumptions can we make here? And then how do we test for collisions between two such volumes? This seems to be more difficult than OBB-OBB intersection testing. However, if you know how to solve this problem, then #3 is solved as well, since a moving polygon sweeps a convex volume as well.

[Reedbeta]

Nyx said:

Constructing the volume could be challenging in itself. What kinds of assumptions can we make here?

Well, as I mentioned earlier, a common assumption is that the motion is purely linear during a single timestep. If your objects are already broken into convex pieces, you can make a volume for each piece and then ignore self-collisions. Another approach is to take the convex hull of the object's initial and final locations (meaning, the convex hull includes the initial and final location of each vertex).

Another thing to bear in mind is that this extended handling is probably unnecessary most of the time, so it can be a good performance-improvement heuristic to turn it on only when an object is moving fast enough that it travels more than its own size during a single time step.

Quote

And then how do we test for collisions between two such volumes? This seems to be more difficult than OBB-OBB intersection testing.

Actually, the separating axis test works for any pair of convex polytopes, not just for OBBs. So it is no more difficult, just involves a greater number of edges and faces.

[Nyx]

Reedbeta said:

Well, as I mentioned earlier, a common assumption is that the motion is purely linear during a single timestep. If your objects are already broken into convex pieces, you can make a volume for each piece and then ignore self-collisions.

Yeah, but how do you even "make a volume". If I take a cube, move it along a random vector, how do I know what convex polytope it traces? I could draw it, but I would need an algorithm to tell me all the vertices, edges, faces, etc.

Quote

Another thing to bear in mind is that this extended handling is probably unnecessary most of the time, so it can be a good performance-improvement heuristic to turn it on only when an object is moving fast enough that it travels more than its own size during a single time step.

I don't think that's true. Think of the "corner case" where two cubes travel in opposite directions such that their corners would collide. The corners have less thickness than the thickness of the whole object, and the collision could still be missed.

I think I can reduce the performance hit by using AABBs as an initial encompassing volume, as an early escape test... Then I would need the full collision handling only between objects I know have a fair chance of colliding.

Furthermore, I will probably avoid doing any collision detection for pairs of objects that are at rest. For example, if a cup rests on a table, I wouldn't need to test the cable and the cup for collisions, not until either the cup or the cable moves.

Quote

Actually, the separating axis test works for any pair of convex polytopes, not just for OBBs. So it is no more difficult, just involves a greater number of edges and faces.

But, what are the possible separating axes, in the general case? For OBBs, it's just the 3 axes of each, plus all the possible cross products of axes of both. What about general polytopes? Do we take all the surface normals + the cross product of the surface normals of each?

[Reedbeta]

Nyx said:

Yeah, but how do you even "make a volume". If I take a cube, move it along a random vector, how do I know what convex polytope it traces? I could draw it, but I would need an algorithm to tell me all the vertices, edges, faces, etc.

It's actually not too difficult to construct the verts/edges/faces of this polytope. The crucial insight is that you can split the cube's faces into ones that face along the direction of motion and ones that face oppositely to it (based on their normal). I'll call these the "front" and "back" faces, respectively. Then, clearly the envelope of the cube's motion includes the front faces at the cube's final position, and the back faces at the cube's initial position. Then all we have to do is connect the two by creating a face for each cube edge that separates a front from a back face. These faces will be perpendicular to the direction of motion.

As mentioned before, it's very similar to constructing a shadow volume, in case you're familiar with that algorithm.

Nyx said:

What about general polytopes? Do we take all the surface normals + the cross product of the surface normals of each?

Yes, that's correct.

[Nyx]

I just read a powerpoint presentation about this topic and it gave me an idea that might work...

When doing the separating axis algorithm... Perhaps one could project the motion vector of each object on the axes, and "grow" the interval of each object according to this scalar projection, and then test for overlap.

Any chance this would work correctly? If so, it could spare the time of constructing the polytopes, and might just be faster in the end, seeing intersection testing for abitrary polytopes is quite a bit more time consuming than OBB-OBB.

[Reedbeta]

Hmm, interesting idea. It's not clear to me how well that would work. You could try it and find out!

[Nyx]

Well, I don't know how well it would work, but I just thought of an obvious flaw. This assumes the object has no rotational velocity.

If the object has a rotational velocity, I'm going to want the end position of the OBB to be not only displaced, but also rotated. Seems that could also complicate the construction of the polytope a fair bit.... Perhaps I should just run the convex hull algorithm at that point.

[.oisyn]

Nyx said:

3) I'm guessing you can use the separating axis theorem for testing polygons vs. OBBs, but I'm not sure how. Do you just take the two axes of the polygon to be two orthogonal vectors on its plane? Will that work?

You can test any combination of convex polytopes with the separating axis theorem. Even points, lines and line segments. So yes, also polygons . Of course, if you're interested in things like intersecting line segments or something then I wouldn't suggest using SAT, but if at least one of the objects is a polyhedron you're good to go.

Btw you can easily do the SAT for objects with lineair (but no angular) movement by simply using the movement vector as an extra edge for both objects.

[Nyx]

I'm thinking the simplest thing to do about rotational movement is to simply ignore it, or separate it from linear movement. Move the object as far as possible, and then in a second phase try to rotate it.