BSP - Nathan Dobbs

I found an example of BSP tree by Mr. Nathan from Dr. dobbs journal site, and seems it has some bugs as it crashes one of my same input file. The other bug i found is in the Split procedure

  NewPoly1 = new CPoint[ PntCnt ];
  NewPoly2 = new CPoint[ PntCnt ];
  for( ushort i=0; i<PntCnt; i++ )
  	// Handle split points
  	if( Splits & ( 1 << i ) )
  		NewPoly1[ Poly1Index++ ] = SplitPnts[ i ];
  		NewPoly2[ Poly2Index++ ] = SplitPnts[ i ];
  		Destination ^= 1;

  	if( Destination )
  		NewPoly1[ Poly1Index++ ] = PntList[ i ];
  		NewPoly2[ Poly2Index++ ] = PntList[ i ];

If there are 4 points and 1 split was occured, newpoly1 will have 5 points but memory was allocated for 4 points only.
Is there something missing after “if( Splits & ( 1 << i ) )” part.

Please help me in writing or fixing a good BSP tree. I am stuck at transparency.



what do you want? you want to do a bsp tree in order to include in your file format ?

To render the transparent stuff you could do something like this for every frame:

  • Create a empty linked list of tree nodes
  • Do a rendering traversal of your tree like you normally would except whenever you hit a ‘transparent’ node you don’t render it in place, instead you insert it at the end of your linked list
  • When you’re done traversing, enable blending and render your linked list in order.

Hope it helps


As far as splitting, I think you need to be able to handle more than just 4 points after a split. Even if your input is all triangles you could end up with polygons that have many vertices after splitting.