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

This topic is 4355 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

##### Share on other sites
you'll find many problems with that approach. The Quake3 / DPS (Dynamic Plane Shifting) approach should be a lot more reliable, but you need to construct a solid-leaf BSP tree, which can be a problem.

I don't know... see what works for you.

##### Share on other sites
            Dim HitFace() As Integer = Nothing            Dim HitFaceCount As Integer = 0            World.BSP.Node(0).CollisionFace(Camera.CamPos, , 0.25, HitFace, HitFaceCount)            frmMain.Text = HitFaceCount            Dim iHit As Integer = 0            For iHit = 0 To HitFaceCount - 1                Dim cFace As clsFace = World.Face(HitFace(iHit))                cFace.Normal.Normalize()                Camera.CamPos.Subtract(Vector3.Scale(cFace.Normal, 0.1))            Next

CollisionFace returns all the faces intersected by a sphere around the camera.
Right now, to test collision response and sliding, I'm pushing the camera away from the wall by normal * 0.1. The next thing for me to do is to replace 0.1 with the intersection distance and then I'm done. :)

##### Share on other sites
            Dim HitFace() As Integer = Nothing            Dim HitFaceCount As Integer = 0            World.BSP.Node(0).CollisionFace(Camera.CamPos, , 0.25, HitFace, HitFaceCount)            Dim SlidingVel As Vector3 = Vector3.Empty            Dim iHit As Integer = 0            For iHit = 0 To HitFaceCount - 1                Dim cFace As clsFace = World.Face(HitFace(iHit))                cFace.Normal.Normalize()                Dim SlideAmount As Single = Vector3.Dot(cFace.Normal, Camera.CamMoveDir)                SlidingVel.Subtract(Vector3.Scale(cFace.Normal, 1 - SlideAmount))                SlidingVel.Add(Vector3.Scale(Camera.CamMoveDir, 1 - SlideAmount))            Next            Camera.CamPos = Camera.LastCamPos            Camera.CamPos.Add(SlidingVel)

What I need to do is to project the end point onto the wall, not add the scaled movement direction. Any ideas how would I do that?

[Edited by - CadeF on January 26, 2006 6:32:42 AM]

##### Share on other sites
EndPoint -= Face.Normal * (((EndPoint - Face.Vertex[0]).DotProduct(Face.Normal));

##### Share on other sites
            Dim iHit As Integer = 0            For iHit = 0 To HitFaceCount - 1                Dim cFace As clsFace = World.Face(HitFace(iHit))                cFace.Normal.Normalize()                Camera.CamMoveDir.Normalize()                SlidingVel.Subtract(Vector3.Scale(cFace.Normal, Vector3.Dot(cFace.Normal, cFace.ptCenter - Camera.CamPos)))            Next            Camera.CamPos.Add(SlidingVel)

It pushes me too far away from the wall.

##### Share on other sites
you're mixing up sliding vel, and end points, and it's all generally wrong anyway...

SlidingVel.Subtract(Vector3.Scale(cFace.Normal, Vector3.Dot(cFace.Normal, SlidingVel)))

maybe?

##### Share on other sites
I'm going to take a look at this
http://www.gamedev.net/reference/articles/article1026.asp

But isn't all I need to do just push the sphere infront of the wall, from it's end point?

##### Share on other sites
How would I use the following code?
bool BTri::isAbove(const vec3 &pos) const {/*	return (edgeNormals[0].x * pos.x + edgeNormals[0].y * pos.y + edgeNormals[0].z * pos.z >= edgeOffsets[0] &&			edgeNormals[1].x * pos.x + edgeNormals[1].y * pos.y + edgeNormals[1].z * pos.z >= edgeOffsets[1] &&			edgeNormals[2].x * pos.x + edgeNormals[2].y * pos.y + edgeNormals[2].z * pos.z >= edgeOffsets[2]);*//*	return (edgePlanes[0].x * pos.x + edgePlanes[0].y * pos.y + edgePlanes[0].z * pos.z >= -edgePlanes[0].w &&			edgePlanes[1].x * pos.x + edgePlanes[1].y * pos.y + edgePlanes[1].z * pos.z >= -edgePlanes[1].w &&			edgePlanes[2].x * pos.x + edgePlanes[2].y * pos.y + edgePlanes[2].z * pos.z >= -edgePlanes[2].w);*/	return (planeDistance(edgePlanes[0], pos) >= 0 && planeDistance(edgePlanes[1], pos) >= 0 && planeDistance(edgePlanes[2], pos) >= 0);}bool BNode::pushSphere(vec3 &pos, const float radius) const {	float d = planeDistance(tri.plane, pos);	bool pushed = false;	if (fabsf(d) < radius){		if (tri.isAbove(pos)){//			pos += (radius - d) * tri.normal; 			pos += (radius - d) * (vec3 &) tri.plane; 			pushed = true;		}	}	if (front != NULL && d > -radius) pushed |= front->pushSphere(pos, radius);	if (back  != NULL && d <  radius) pushed |= back ->pushSphere(pos, radius);	return pushed;}

It pushes a sphere away from the collision planes in a perfectly closed map. Humus uses it in his demos for camera sliding BSP collisions.

Bump

Anyone?

##### Share on other sites
I think I've got it. Works fine, even with multiple planes sticking out at odd angles.

 Dim cFaceCount As Integer = 0        Dim cFace() As Integer = Nothing        World.BSP.Node(0).CheckSphereIntersection(Camera.CamPos, 1, cFace, cFaceCount)        For I = 0 To cFaceCount - 1            Dim tFace As clsFace = World.Face(cFace(I))            Dim d As Single = Math.Abs(modPlane.PointPlaneLocalityDot(Camera.CamPos, tFace.ptCenter, tFace.Normal))            If d < 1 Then                Camera.CamPos.Subtract(Vector3.Scale(tFace.Normal, (1 - d) + (1 / 32)))            End If        Next Public Sub CheckSphereIntersection(ByVal pt As Vector3, ByVal Radius As Single, ByRef cList() As Integer, ByRef cListCount As Integer)        If Abs(PointPlaneLocalityDot(pt, Center, Normal)) < Radius Then            If World.BSP.Node(0).TestPointWorldLocality(pt + Vector3.Scale(Normal, Radius)) <> World.BSP.Node(0).TestPointWorldLocality(pt - Vector3.Scale(Normal, Radius)) Then                Dim bIsRepeat As Boolean = False                If cListCount > 0 Then                    Dim I As Integer = 0                    For I = 0 To cListCount - 1                        If cList(I) = Face Then                            bIsRepeat = True                        End If                    Next                End If                If Not bIsRepeat Then                    ReDim Preserve cList(cListCount)                    cList(cListCount) = Face                    cListCount += 1                End If            End If        End If        If Front > -1 Then World.BSP.Node(Front).CheckSphereIntersection(pt, Radius, cList, cListCount)        If Back > -1 Then World.BSP.Node(Back).CheckSphereIntersection(pt, Radius, cList, cListCount)    End Sub

##### Share on other sites
hi "CadeF" i was working with 3D collision detection in C# and i got some result not perfect but it is ok and it needs some corrections i didn't have time to correct it , what i did in my collision detection algorithm is that i gave my function the mesh i want to detect collision against it and i calculated the nearest collision point and make my responce to it "which i think is wrong because i am ignoring the other collision points" so that's what i want to correct , if u want we can exchange our 3d collison detection algorithms and work together to obtain a good result , what u say ????????

##### Share on other sites
And, code for pushing a sphere, converted to use a node-based bsp

    Public Function TestPointWorldLocality(ByVal pt As Vector3, Optional ByVal Prev As Integer = -1) As Boolean        Select Case PointPlaneLocality(pt, Center, Normal, 0)            Case Enum_PointPlaneLocality.Front                If Front > -1 Then                    Return World.BSP.Node(Front).TestPointWorldLocality(pt, Front)                Else                    Return True                End If            Case Enum_PointPlaneLocality.Back                If Back > -1 Then                    Return World.BSP.Node(Back).TestPointWorldLocality(pt, Back)                Else                    Return False                End If            Case Enum_PointPlaneLocality.Split                Return False        End Select        Return False    End Function    Public Sub PushSphere(ByRef Pos As Vector3, ByVal Radius As Single)        Dim d As Single = Abs(PointPlaneLocalityDot(Pos, Center, Normal))        If d <= Radius Then            If World.BSP.Node(0).TestPointWorldLocality(Pos + Vector3.Scale(Normal, Radius)) <> World.BSP.Node(0).TestPointWorldLocality(Pos - Vector3.Scale(Normal, Radius - d)) Then                Pos.Subtract(Vector3.Scale(Normal, Radius - d))            End If        End If        If Front > -1 Then World.BSP.Node(Front).PushSphere(Pos, Radius)        If Back > -1 Then World.BSP.Node(Back).PushSphere(Pos, Radius)    End Sub

This code works perfectly, it is all I am using for sliding collision detection. :)

[Edited by - CadeF on February 11, 2006 6:21:02 AM]

Class clsFace    Public Function IsAbove(ByVal Pos As Vector3) As Boolean        Dim I As Integer = 0        Dim J As Integer = Points.Length - 1        For I = 0 To Points.Length - 1            Dim EdgeNorm As Vector3 = Vector3.Cross(Normal, Points(I) - Points(J))            If Vector3.Dot(EdgeNorm, Pos) - Vector3.Dot(EdgeNorm, Points(I)) < 0 Then                Return False            End If            J = I        Next        Return True    End FunctionClass clsBSPNode    Public Sub PushSphere(ByRef Pos As Vector3, ByVal Radius As Single)        Dim d As Single = Abs(PointPlaneLocalityDot(Pos, Center, Normal))        If d < Radius Then            If World.Face(Face).IsAbove(Pos) Then                Pos.Subtract(Vector3.Scale(Vector3.Normalize(Normal), Radius - d))            End If        End If        If Front > -1 Then World.BSP.Node(Front).PushSphere(Pos, Radius)        If Back > -1 Then World.BSP.Node(Back).PushSphere(Pos, Radius)    End Sub