portal engine collision detection

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

Recommended Posts

I was thinking this over.... if we have convex sectors only or as in my case, 6 sided, cubelike sectors then collision detection for a particle should be pretty simple... track the last known sector that a particle was in then after moving, draw the vector from the particle to one of the sides of the last known sector do a dot product of that vector with the surface normal it is positve, youre still on the right side of that wall if its negative, you either bounce back in, or the wall was a portal and you stepped into a new sector shoudl work as long as you never move past more than one sector per physics loop update and perhaps a solution to that problem is to do recursive checks every time the particle has been found to enter a different sector... heres what bugs me though the object im simulating, is going to be made up of more than one particle, for better collision accuracy what happens when you are half in one sector and half in another? i suppose this demmands that every single particle track its own current sector, and each one do a seperate recursive collision check that sounds like it might be slow tho..... are there better ways? ok, how about this, i have a bounding sphere on my player and track his current sector based on center of mass then do the same dot product strategy on his center, if his sphere hit a wall, switch to the detailed per particle mode as above if he hit a portal, let him thru and recurse this at least means the per-particle checks recurse at most once, and only for half of them, (assuming the player isnt fatter than a sector) i guess thats a good improv.... oh crap, that might go out the window entirely for the case where you hit a wall, swap the detailed per-particle mode then they all manage to bounce out into another sector..... i guess thats rare tho... so in practice you dont recurse too much.... anyone have even better ideas? [Edited by - haphazardlynamed on September 15, 2004 2:46:45 AM]

Share on other sites
You have convex sectors (rooms) and convex openings (doors) only. Think your collision detection and response as a succession of events that you must always treat in chronological order.

The convexity implies that you only have to deal with :

- plane equations only as long as you are (fully) inside the sector. Sphere/plane is as easy as point/plane (the dot prooduct plus the plane constant : signed distance to origin), just add the radius. An easy collision response (à la Quake) is sliding : stop at the time of collision. Then cut the normal part of the displacement vector (velocity*delta_time), this makes it parallel, the movement will be sliding. After the collision event, don't forget to test the nearest plane again for the remainining displacement vector. Thus your sphere can eventually be blocked at the inner edges.

When your displacement crosses the plane that supports the door, you know that you have to deal with one of these 3 types of events :

e) collision with an edge of the door
f) collision with the wall
g) pass through the door without colliding

This can be solved by the Voronoi partition around the door. To simplify, here is a 2D scheme. You see two plain lines which represent the wall in you first sector and a wall in your corridor (next sector). Edge e, their instersection is one of the door edges. Firstly, let's only consider this single edge.

E, F, G are infinite convex volumes. If your sphere center is in F, then the closest d-facet is the wall f (a 2d-facet). If E, it's the edge e (a 1d-facet). If G, it's the wall g (a 2d-facet)

         /        g        /  G---f--e.  F   :E .      : C  .

Earlier you have stopped where your sphere center C was at distance R from the support plane of wall f. Now check on which sides of separating planes F/E and E/G you are. You should precompute F/E and E/G and store it as the Voronoi volume attached to E. You know that while the center is in this volume, your sphere can not collide with the (finite) walls g or f before edge segment e. This volume is very important because you can pass through the (infinite) PLANE of f, it does not mean that you collide with the WALL f if you are in E or G.

When you are in F, then it's the common plane sliding case. Clamp the displacement and slide, maybe you'll enter E next.

When you are in E, check whichever event comes first, enter F, enter G or collide with e.

When you are in G, check whichever comes first, collide with g or enter E,

Now I let you see how can deal with processing all the edges in parallel. The goal is always treat the 'predicted' potential events one by one, and update your displacement after each event.

BTW how to 'slide' on an edge E ? At the moment you hit, compute the normal to E that passes by C (normal of contact) do as if it was locally flat, same as wall sliding. A sphere is a collection of infinitesimal planes.

Share on other sites

a single sphere or point is easy
i already know the physics response part

my models are much more complex than spheres
so i represent them as multiple point samples

What im asking, is if anyone can think of a better scheme to lower the cpu work even more than my first bounding sphere idea

focus on optimization schemes for Multiple spheres/particles

im pretty sure my solution is going to be as good as it gets for this situation...
but you never know, maybe someone knows an even better trick

Share on other sites
These claims you made, let me think you did not totally master the difficult cases :

"or the wall was a portal and you stepped into a new sector"
This will work if your portals are just 'plain open walls' and your particles punctual (not spheres). How would you handle the case of a portal that is a window fixed to a wall, in an engine that copes with 6 degrees of liberty ?

 -------|   __  ||  |__| | -------

"should work as long as you never move past more than one sector per physics loop update"
There you missed the principle of ordering potential events, with possibly several actual contact events processed per frame.

But I was probably wrong if you say it.

Else there is no other clean way. You can probably hack and have your models visible on both parts of the walls, as in Tomb Raider for instance. But a collection of sphere, is just a collection of primitives ... spheres. You can not escape the rules of boolean geometry if your collision models are just collections of particles.

The idea of using a sphere tree (discussed elsewhere) is totally OK. Hierarchical early rejections schemes is the most common optimization.

Now last point. Such collision handling is not CPU intensive at all. Unless your code is dreadful, in the simplified context you expose, you will not spend more than 1% of the CPU power at 100FPS for 1000 such objects.

Share on other sites
Hmmm
you have a good point
the 'window' style portals are a hard case

with my engine setup though, all portals are open walls
the only way to get a 'window' style is to make a degenerated sector thats completely flat
to make the transition between the large 'room' and the small 'window'

which means all of its walls will be in the same plane, and potentially any of 5 - 4 side walls or center portal can be colliding at the same time using the normals/dot product method

i guess one way to deal with that might be to make a special case...
if more than one side is coplanar, and theyve all collided
{then check to see if one of them is a portal,
see if the particle collides with any of the side walls of that sector on the other side of the portal
if it hits none,{ then the particle probably succesfully entered the center 'window' portal
}but if it has even more collisions on the other side{ the particle most likely didnt' go straight through and we can use any of the coplanar sides' normals to bounce against
}
}

thanks for pointing that out

im not too worried about the exact ordering of events, since the time step is assmued to be small, so usually one collision would be detected before another..

and the only time this potentially becomes visible is when you have a portal on adjacent walls making a sharp fork in the hallway
but thats a rare case, and since my objects are multiparticle the majority rule should pull the object in the right direction even if a few go down the wrong portal

[Edited by - haphazardlynamed on September 17, 2004 5:08:06 PM]

Share on other sites
Well do as you want once it works more or less, whichever looks easier to you. But then try to solidify. Sorting the events is really straightforward in your case : convex rooms, exact prediction.

Something like :
t0 = tStartOfFrame;do{// Start of Frame is 0.t = tEndOfFrame;    for(iWall=0; iWall<nWalls; iWall++)    {        ti = timeOfCollision(iWall, &pContact);       if( ti < t ){ t=ti; Contact=*pContact;    }    AdvanceTo(ti); // P+=V*(t-t0); t0=ti; V=...; // response}while( t < tEndOfFrame );

1. 1
2. 2
Rutin
22
3. 3
JoeJ
20
4. 4
5. 5
gaxio
13

• 27
• 40
• 23
• 13
• 13
• Forum Statistics

• Total Topics
631735
• Total Posts
3001939
×