#### Archived

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

# BSP collision detection in DX9

This topic is 5358 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)
{
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 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

• 38
• 12
• 10
• 10
• 9
• ### Forum Statistics

• Total Topics
631365
• Total Posts
2999585
×