Quote:Original post by Anonymous Poster
[...]
I have the level in an OcTree (will change to another tree soon) and I need to find out which polygons might intersect the model. How can I find that? I could extend the AABB to fit the model during the whole movement, but I feel that I might end up with too many polygons. Am I right or that's how it's usually done? Anyway, that's why I thought of an OBB with one of the axes in the direction of movement. I could limit the number of polygons.
[...]

I use an AABB encompassing the previous and current position of a given body in my simulator. It's really not perfect but bodies rarely move very fast so it stays good enough.

An octree might give you too much candidate polygons tho. I use a KD-Tree and simply clamp the query AABB to the node being traversed. An OBB would be much better but would require a significantly more expensive clipping against each plane. It would also only be of benefit with moderatly fast bodies.

Quote:
Now, for narrow phase, I'm actually using the SAT theorem, but static, moving the model in small steps. And then my precision is limited to the size of that step (the object might end up almost one full step away from the collision point). Most engines deal with that precision problem (mine is related to the size of the moving object) or they get really, really close to the collision point?

I mean, once a collision is found for sure during the collision detection phase, is the distance to the collision found, in order to move the object as close as possible to the colliding point, or we just stop the algorithm one iteration before it happens?

I assume you are not talking of a physic engine, but simply collision detection and response. You cannot just stop where you stand when a collision is detected.

In case of a sphere/poly with a old and new position.
On collision you get a hit point, you would then project the new position point along the normal of the polygon to get a temporary destination (wich might lie outside of the polygon boundaries that's no problem).

You then rerun a detection from the hit point to the temporary destination... Repeat that until the distance from hit point to temp dest is small enough. At this point your destination is temp dest.

That works real well, you can implement friction and all that kind of stuff aswell (by scaling the vector from hit point to tmp dest).
There's a minor issue with jittering in specific configurations but that simply cannot be taken out to my knowledge.
I might even have an old exe for that somewhere... :) let me check...

Quote:
I'm sorry but I didn't understand. I guess I'm missing something. When you find a collision, you get the hit point (which takes me to the question: how??)? I have the static polygon that hits the moving one (in my case, it's an AABB moving). Would you mind explaining it again? I'm really interested.

(edit: See my next post for how to find that hit point wich is not a point of intersection in your case but a position at wich the AABB and the polygon are in contact.)

Ok, if you are not doing any physics you don't really care about the hit point. What you really care is: given a start and an end position for the AABB, what is the contact position. That is, the position for wich the penetration depth is 0. The separating axis theorem gives you a way to determine that contact position pretty easily using the axis with the minimal penetration.

So, you test all the polygons potentially colliding with your AABB and select the one giving you the contact position the closest to your start position. That sounds like a lot of work but it's not, honestly.

Let's take a practical example: A is your AABB starting position, B is its end position.

1) You feed that to your AABBCollideWorld(Vec &a, Vec &b, etc...); function.
This function determine the set of polygons potentially colliding with your AABB, perform a SAT test for each polygon and keep track of the polygon leading to a contact position the closest to the start position, let's call that final contact position I and the polygon leading to that position P. Note that P is simply the first polygon hit by the AABB on the path from A to B.

2) You now know that you can move freely from A to I. You also know that B results in a penetration between the AABB and P. In order to get a nice sliding effect proportional to the polygon slope you can "slide" B along P's normal N to a position that brings the AABB back in contact with P's plane (again it may well be outside of P boundaries, that doesn't matter). Let's call that position B'.

Some hints on how you may find B': B' lies on the line L of direction N and B is a point of this line. Intersect P with L you get a point of intersection that you simply need to offset by K/2 where K is the size of the interval of your AABB projected onto N.

3) You can simply take B' as a valid position but usually you will want to make sure there's no potential colliders on the path from I to B' so you simply call AABBCollideWorld(I, B', ...); to retest the new trajectory for collision.
Do that a few times or until [I;B'] length gets below a given threshold and you have a fairly safe destination position B' to move to.

Hope that makes it clearer :).

As a side note: If all you want is AABB/polysoup then you are much better off with a simple AABB/Poly SAT test (edit: forget that I understand you indeed use AABB/Poly tests). Breaking the AABB into polygons will only make it harder imho. Friction could be implemented by simply scaling [I;B'] by a friction factor before feeding it back to the AABBCollideWorld() function.

[Edited by - b34r on July 30, 2005 1:12:46 PM]

Quote:Original post by S41NT
I'm sorry but I didn't understand. I guess I'm missing something. When you find a collision, you get the hit point (which takes me to the question: how??)? I have the static polygon that hits the moving one (in my case, it's an AABB moving). Would you mind explaining it again? I'm really interested.

Oh, I see, your problem may be how to make a continuous SAT test?

Real easy way, one primitive moving A, the other static B.
Compute A's projected interval both at the start position and the end position. Combine both these intervals to get the swept interval of A, then check that against B interval just as you do now. When you got an overlap, to determine t, the time of contact, simply use the distance from A's starting interval end point to B's interval start point and divide by the length of A's motion vector (end pos - start pos) projected onto the overlapping axis.

edit: Just to make it clear, C the position of contact would be, C = startpos + (endpos - startpos) * t;.

edit2: Of course if you want to consider rotation as well that's another thing :).

[Edited by - b34r on July 30, 2005 1:24:02 PM]