[Resolved, source code posted]Sliding collision (camera) against a BSP tree
Author
The source code is in my last post.
Hey everyone,
In my game engine, I have implemented a leafy BSP tree. Currently, I just test the camera (a 3d point) and see if it lands in a solid leaf (outside) or a non-solid leaf (inside). If it lands in a solid leaf, it moves back to it's last good position.
Does anyone have a good tutorial about sliding collisions against a BSP tree?
Thanks,
Cade
[Edited by - CadeF on February 11, 2006 6:31:20 AM]
Author
Thanks, but I already have ray tracing and intersection. I'm looking for collision response, sliding collision as the object I'm testing is a floating/flying camera. :)
Wish I could help more, but the best tutorial I can think of is the Quake engines source itself (and digging through that code is no small task). You might also try Stan Melax's article on dynamic plane shifting. Take out the 'dynamic' part, and I'm pretty sure this is how the Quake engines do it (could be wrong about that - haven't looked at the coldet code in a while).
The idea (I haven't implemented this myself) is to, for the purpose of collision detection, make extra copies of the bsp planes that are 'pushed out' along their normals by the radius of your object. You then perform all collision detection using simple raytracing; the plane displacements take care of keeping your object a certain distance away from obstacles.
As for the sliding, there are various issues to deal with, but the basic idea is:
1. Intersect the movement vector with the bsp tree
2. If it clips to a plane, move the object to (or near) the intersection point and...
3. Restrict the velocity to lie in the collision plane (vel -= normal*dot(vel,normal))
4. Repeat recursively until the step is 'used up', or no collisions are found
This is explained well in Kasper Fauerby's ellipsoid coldet paper. Although it deals with ellipsoid vs. polygon soup rather than object vs. bsp, many of the concepts are the same.
The idea (I haven't implemented this myself) is to, for the purpose of collision detection, make extra copies of the bsp planes that are 'pushed out' along their normals by the radius of your object. You then perform all collision detection using simple raytracing; the plane displacements take care of keeping your object a certain distance away from obstacles.
As for the sliding, there are various issues to deal with, but the basic idea is:
1. Intersect the movement vector with the bsp tree
2. If it clips to a plane, move the object to (or near) the intersection point and...
3. Restrict the velocity to lie in the collision plane (vel -= normal*dot(vel,normal))
4. Repeat recursively until the step is 'used up', or no collisions are found
This is explained well in Kasper Fauerby's ellipsoid coldet paper. Although it deals with ellipsoid vs. polygon soup rather than object vs. bsp, many of the concepts are the same.
That tutorial has stuff about sliding collisions (Spheres, AxisBoxes, ...).
... or maybe not. Not the sliding part though.
Sliding is easy enough. When you hit a wall,
1) move the object to the collision time
Pos += TraceDir * time_of_collision;
2) then change your trace direction to
TraceDir -= (TraceDir.DotProduct(WallNormal)) * WallNormal;
3) then run trace again, until no more collisions are found, or you run too many iterations (like an object stuck in a drain).
watch out for FP problems, which might make you go through walls when the trace is very small), or if you move too close to the walls.
... or maybe not. Not the sliding part though.
Sliding is easy enough. When you hit a wall,
1) move the object to the collision time
Pos += TraceDir * time_of_collision;
2) then change your trace direction to
TraceDir -= (TraceDir.DotProduct(WallNormal)) * WallNormal;
3) then run trace again, until no more collisions are found, or you run too many iterations (like an object stuck in a drain).
watch out for FP problems, which might make you go through walls when the trace is very small), or if you move too close to the walls.
Author
The tutorial is using brushes, I'm not sure how that would work out, scince my tree structure is a leafy bsp.
the system is quite similar. First thing to do is getting ray-tracing working. Then use point-particles and test them colliding and sliding. Then using the dynamic plane shifting, test solid objects with the tree. Then introduce the extra virtual planes required at the leaves to make the collision work with sharp angles.
[google] for Stan Melax's Dynamic Plane Shifting Solid BSP Collision System, ect... [grin]
[google] for Stan Melax's Dynamic Plane Shifting Solid BSP Collision System, ect... [grin]
BTW, for the sliding itself,
say Camera has [vStart, vVel, fDt]
You have a function that raytrace through the BSP tree
this function returns if the ray intersected the BSP tree, and returns the distance to the intersected surface fron the start position, and the normal of the intersected surface.
then you have the function...
say Camera has [vStart, vVel, fDt]
You have a function that raytrace through the BSP tree
bool RayIntersect(const BSPTree* pxBSPTree, const Vector& vRayStart, const Vector& vRayDir, const float fRayLength, float &fDistColl, Vector& vNormalColl);this function returns if the ray intersected the BSP tree, and returns the distance to the intersected surface fron the start position, and the normal of the intersected surface.
then you have the function...
bool ParticleCollidesWithBSP(Vector& vParticlePos, Vector& vParticleVel, float dt, const BSPTree* pxBSPTree){ const float fCoeffOfRestitution = 0.0f; // 0.0f = pure sliding, ->0.5f = soft bounce, ->1.0f = hard bounce bool bTrace = true; bool bCollided = false; while (bTrace) { Vector vNcoll; float ftcoll; bool bIntersect = RayIntersect(pxBSPTree, vParticlePos, vParticleVel, dt, ftcoll, vNcoll); if(bIntersect) { dt -= ftcoll; vParticlePos += vParticleVel * ftcoll; vParticleVel -= (1.0f + fCoeffOfRestitution) * (vParticleVel.DotProduct(vNcoll)) * vNcoll; bTrace = true; // continue tracing bCollided = true; // yep, we've collided at least once } else { bTrace = false; // no need to continue tracing } } // move particle to end of trace vParticlePos += vParticleVel * dt; return bCollided; }
Author
Thanks. My current method is to add to the camera position, the plane normal * (1-IntersectionPercentage). It works perfectly if the camera is colliding with one wall. If the camera is in a corner, colliding with two walls or more, it slides against one of the walls only, ignoring the other wall/walls completely.
Right now, I think I'll try this
-Insert a sphere into the BSP, see what faces it collides with
-Sort the faces (if more than one) in ascending order of dot(FaceNormal,CamMovementDirection)
-Run the current test on each face
Right now, I think I'll try this
-Insert a sphere into the BSP, see what faces it collides with
-Sort the faces (if more than one) in ascending order of dot(FaceNormal,CamMovementDirection)
-Run the current test on each face
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
