Ive really just got the idea to take a look at how bsp algorithm works a little while ago, and did some light searching on the topic, but I was curious if you guys new of any good sights that explain how to actually take a lump of verts, polys etc and turn it into a bsp tree. Ive read before that the actuall algorithm isn''t that hard to implement, hmm. Any comments?

I''ve tried to implement that yesterday - but my rendering function doesn''t render so I couldn''t test it...

You need :

- a function to slice a polygon along a plane : if the polygon intersect the plane it returns the two sliced polygons, if not it returns the side of the plane the polygon lies on -> "slice"
- a function to extract the plane of a polygon -> "plane"

Once you have that, your recursive insertion function will look like this : (sorry for the language but it''s much shorter like that).

let rec rinsert bsp pol =	match bsp with	| Leaf ->		Node (Leaf,( { plane = make_plane pol; polygon = pol } ),Leaf) 	| Node (front,node,back) -> (			match slice node.plane pol with		| Front -> Node ((rinsert front pol),node, back )		| Back -> Node (front, node,( rinsert back pol ) )		| Sliced (f,b) -> Node ((rinsert front f),node,(rinsert back b) )  				);;

I hope this helps

yah it helps, the language is a bit strange though
Im thinking about downloading the q3radiant source since it has the code for building a bsp tree as well as csg and such. maybe that would help you as well?

[edited by - no one on December 30, 2003 12:44:00 PM]

this might help i ripped it from the tree i have been programming

/************************************************************************************ *	Generation and Subdivision Functions for the CQuadTree class					* ************************************************************************************//*	GeneratTree		  this function Sets up the tree to be generated by the SubDivide function */void CQuadTree::GeneratTree(float tsize,CViewPort* Camera){	m_TerrainSize = tsize;		m_HeadNode = new CTreeNode;	// setup the head of the tree	m_CurrentNode = m_HeadNode;	// Current node equal to the head of the tree	m_Camera = Camera;			// set the pointer to the Camera Viewportclass	m_PatchSize = 32.0f;		Load8bitRAW(2.0f,2.0f,2.0f,"terrain.raw";	// load the vertex data for this terrain	// Load the textures to be used by this terrain	m_TextureManager.Load("ground.bmp";	m_TextureManager.Load("tile0.bmp";	SubDivide(0.0f,0.0f,m_TerrainSize);}/*	SubDivide		This function subdivides the area each patch will store the index buffers for */void CQuadTree::SubDivide(float cx,float cy,float tsize){	float nx = 0,ny = 0;	CTreeNode *Current = m_CurrentNode;	if(tsize <= (m_PatchSize))	{		// get data for this patch		m_CurrentNode->m_Patch = new CPatch(&m_TextureManager);		m_CurrentPatch = m_CurrentNode->m_Patch;		FillPatch(cx,cy,tsize);			}	else	{		// need to further subdivide				if((m_CurrentNode = m_CurrentNode->Child[0]) == NULL)		{			m_CurrentNode = new CTreeNode;			Current->Child[0] = m_CurrentNode;			m_MemoryUsed += sizeof(CTreeNode);		};		nx = (cx - (tsize / 2));		ny = (cy + (tsize / 2));		SubDivide(nx,ny,tsize / 2);		m_CurrentNode = Current;		if((m_CurrentNode = m_CurrentNode->Child[1]) == NULL)		{			m_CurrentNode = new CTreeNode;			Current->Child[1] = m_CurrentNode;			m_MemoryUsed += sizeof(CTreeNode);		};		nx = (cx + (tsize / 2));		ny = (cy + (tsize / 2));		SubDivide(nx,ny,tsize / 2);		m_CurrentNode = Current;		if((m_CurrentNode = m_CurrentNode->Child[2]) == NULL)		{			m_CurrentNode = new CTreeNode;			Current->Child[2] = m_CurrentNode;			m_MemoryUsed += sizeof(CTreeNode);		};		nx = (cx + (tsize / 2));		ny = (cy - (tsize / 2));		SubDivide(nx,ny,tsize / 2);		m_CurrentNode = Current;		if((m_CurrentNode = m_CurrentNode->Child[3]) == NULL)		{			m_CurrentNode = new CTreeNode;			Current->Child[3] = m_CurrentNode;			m_MemoryUsed += sizeof(CTreeNode);		};		nx = (cx - (tsize / 2));		ny = (cy - (tsize / 2));		SubDivide(nx,ny,tsize / 2);	};}