Jump to content
  • Advertisement
Sign in to follow this  
CadeF

[Resolved, source code posted]Sliding collision (camera) against a BSP tree

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Advertisement
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. :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
The tutorial is using brushes, I'm not sure how that would work out, scince my tree structure is a leafy bsp.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
BTW, for the sliding itself,

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;
}


Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!