#### Archived

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

# BSP collision detection in DX9

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

## 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 on other sites
Quake1 and 2 sources would be a great place to look in.

##### Share on other sites
I have the same problem, I got some source code, but I didn''t get it working

I''ll send you an e-mail with some source if you want

##### 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 on other sites
Isn''t there a dot product collision detection algo? Do the dot product test agisnt the leafs on that branch?

##### 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)
{
}
}
}

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

##### Share on other sites
yeah, lupin, that sounds great. i''ll see what i can make of it

##### 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 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 on other sites
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 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 on other sites
One thing I am a little confused about, BSP is not a file format, it stands for "Binary Space Partitioning" It is a method.

Is there a BSP file format aside from BSP?

Are they 2 different things?

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