• Advertisement
Sign in to follow this  

[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.

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
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 this post


Link to post
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 this post


Link to post
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 this post


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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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]

Share this post


Link to post
Share on other sites
Discovered the odd bug in that code. This code fixes that bug, seems to work flawlessly now.

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 Function

Class 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



Not doing it all wrong now, am I? :)

Share this post


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

  • Advertisement