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

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

## 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 on other sites
You might take a look at this, if you haven't already.

##### Share on other sites
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. :)

Anyone?

##### 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 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 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 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 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 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

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633704
• Total Posts
3013457
×