portal engine collision detection
Author
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]
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)
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.
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.
Author
I already know that
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
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
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.
"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.
Author
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]
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]
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 :
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 );This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
