OBB Collision Detection & Reaction with Rotation...
Posted 22 December 2008 - 07:12 PM
So far, all the helpful documentation I found is this:
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.
Posted 22 December 2008 - 07:40 PM
Posted 22 December 2008 - 07:49 PM
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.
Posted 22 December 2008 - 08:23 PM
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?
Posted 22 December 2008 - 10:38 PM
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.
Posted 23 December 2008 - 03:41 AM
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.
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.
Posted 23 December 2008 - 04:14 AM
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.
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.
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?
Posted 23 December 2008 - 05:06 AM
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.
Yes, that's correct.
Posted 23 December 2008 - 05:16 AM
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.
Posted 23 December 2008 - 06:28 AM
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.
Posted 23 December 2008 - 02:09 PM
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.
Currently working on: the 3D engine for Tomb Raider.
Posted 23 December 2008 - 03:54 PM
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users