Archived

This topic is now archived and is closed to further replies.

madman_k

BSP collision detection in DX9

Recommended Posts

i have a BSP rendering engine up and running, written completely in directx. i have been trying to implement some type of collision detection, so the camera can no longer pass through walls. However, i can not seem to get the collisions to register properly. i was wondering if anyone knew of a good place to get some information on this, if possible, specifically on BSP tree collisions with the camera. thanks Kendall

Share this post


Link to post
Share on other sites
I''ve only dealt with BSP trees within the confines of ray tracing, but here''s a thought. Could you just put a small bounding sphere/box around your camera and treat it like any other object in your scene?

neneboricua

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Isn''t there a dot product collision detection algo? Do the dot product test agisnt the leafs on that branch?

Share this post


Link to post
Share on other sites
i have found several peoples explanation for the basic collision detection algorithm in OpenGL, and i have tried these methods. However, i get really goofy results. Here is the pseudocode for what i''m doing, including the d3dxfunctions im using.

for(all polys in node)
{
D3DXPlaneFromPointNormal(...) //get the plane
D3DXPlaneIntersectLine(plane, start, end) //get the intersection point
if(the intersection point is valid)
{
use the sum of angle technique to determine if it is the poly
if(point is in poly)
{
adjust destination point appropriately
}
}
}

the problem i have noticed is that this does not register any collisions at all. all i get is walking through walls.

Share this post


Link to post
Share on other sites
bsp LOS collision detection is very simple. LOS - Line Of Sight -- basically tracing a line.

you start with the line you want to trace, represented in world space by P1 and P2. you recurisvly call a trace function on your line, that goes something like this:

(btw, this is my own code that i''ve found to work rather well)


bool BSP::LineOfSight(CVector3 &start, CVector3 &end, BSPNode *node)
{
if(!node)
node = m_pNodes; // root node, so can be called LineOfSight(start,end,NULL);


CVector3 intersect;

if(node->m_bLeaf)
{
return !node->m_bSolid;
}

CLASSIFY a = m_vFaces[node->m_dFaceIndex].ClassifyPoint(start.x,start.y,start.z);
CLASSIFY b = m_vFaces[node->m_dFaceIndex].ClassifyPoint(end.x,end.y,end.z);

if(a == CP_COPLANAR && b == CP_COPLANAR)
return LineOfSight(start,end,node->m_pFront);

if(a == CP_INFRONT && b == CP_BEHIND)
{
m_vFaces[node->m_dFaceIndex].m_pPlane.GetIntersection(start,end,&intersect,NULL);
return LineOfSight(start,intersect,node->m_pFront) && LineOfSight(intersect,end,node->m_pBack);
}

if(a == CP_BEHIND && b == CP_INFRONT)
{
m_vFaces[node->m_dFaceIndex].m_pPlane.GetIntersection(start,end,&intersect,NULL);
return LineOfSight(start,intersect,node->m_pBack) && LineOfSight(intersect,end,node->m_pFront);
}

if(a == CP_INFRONT || b == CP_INFRONT)
{
return LineOfSight(start,end,node->m_pFront);
}
else
return LineOfSight(start,end,node->m_pBack);

// should never actually reach here
return true;
}


i have the original Mr. Gamemaker bsp articles (probably the most definitive source BSP''s and implementation) that i by chance downloaded off the net right before they were taken down and turned into a commercial article. i''d be glad to send them to you, but i''d need to be reassured if thats legal. i don''t think there was a copy right on them when i downloaded them, but im still unsure.

feel free to ask questions on the code

Share this post


Link to post
Share on other sites
yeah, that would help. i think your code is for a node based tree (where the polys are stored in the individual nodes). i am using a leaf based tree, where convex groups of polys are stored in each leaf and only split plane info is stored in the nodes.

If thats so, it might explain why that made very little sense to me. Also, you seem to be using a solid node tree. I am not using that method either.

thanks anyway

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Can you make your BSP a leaf based tree, where you can just traverse it and tell whether the next point will be inside a solid node or not? Then all you need to do is classify the point you are moving into. If the point is inside a solid section of the BSP, don''t allow the move.

SpaceCowboy

Share this post


Link to post
Share on other sites
LOS in leaf based trees is very simillar. you send the line down the bsp tree the same as you would the node tree (using the planes stored in the bsp node), then when it reaches a leaf, check if the two points against all the polygons in the leaf. both of them are either in front or behind all the polygons, no intersection has occured at that point. if one is in front and the other behind, then you have an intersection. find the plane that actually seperates the two points, and find where the line intersects the plane. you can then see if that point is inside the polygon (i dont think you need this step if its a convex hull, but im not the best at non-solid leaf bsp trees)

Share this post


Link to post
Share on other sites
quote:
Original post by madman_k
i was wondering if anyone knew of a good place to get some information on this, if possible, specifically on BSP tree collisions with the camera.



Using a line of site algo, you can clearly test where the camera will hit.

Share this post


Link to post
Share on other sites
I would recommend if you start this whole camera hitting a wall thing you just work on your entire collision detection system. I have some really good source for Dx9 I might be able to share. It uses sphere-triangle (actually cylinder-triangle so you can have object move great distances at a time and still pick up on it if it was inbetween frames - such as a bullet) collision. So your camera is a sphere and check it against the triangles in the world. The problem with line of sight is, you can run through a wall by reversing into it. This way you can''t go into any wall or object for that matter.

There is many forms to use with collision decection.
Box-Sphere
Sphere-Box
Cylinder-Trianlge

I find Sphere-Sphere Sphere-Triangle to be where it is at
Although, I don''t deal with vehicles yet. Which some sort of Box-Box method might produce more desirable results.

Share this post


Link to post
Share on other sites
Madman, did you implement an working collision detection? I think I sent you an email with some source code, were you able to implement it? I had some problems getting it work :/

Share this post


Link to post
Share on other sites
I use D3DXIntersect to see where my camera ray intersects with the terrain, works great, tells you the exact place of intersection, then you can move the camera in a bit and you are all set

Share this post


Link to post
Share on other sites