BSP-Trees

Psst: Front-to-back is what the latest apps use nowadays. The Z-buffer will automatically prevent the polygon overdraw. But a BSP will do either for you (front-back or back-front) depending on how you parse it.

Sorry, I don't have a link.

Are you looking for code that builds the BSP tree or the code that uses it for rendering?

Pseudo C code for rendering (one possible way using recursion):

void RenderBSPLevel(CBSPTreeNode *p_Node)  // a class, actually C++!
{
   // If left pointer is NULL, this node contains a polygon set to be rendered (right pointer would be NULL, too)
   if ( p_Node->lpLeft == NULL )
   {
      RenderNodePolygons(p_Node->polygonset);
      return;
   }

   // This is a branch.  Test partition.
   if (ViewpointOnFrontSideOfPartition(p_Node->partition))
   {
      RenderBSPLevel(p_Node->lpLeft);
      RenderBSPLevel(p_Node->lpRight);
   }
   else
   {
      RenderBSPLevel(p_Node->lpRight);
      RenderBSPLevel(p_Node->lpLeft);
   }
}
      

Sorry if my conventions for containment in classes aren't, uh, conventional.
For example, some programmers might instead set up a p_Node->polygonset.Render() function.

The code for building a BSP tree is a "tad" more complex

BSP nodes can also include the limits of the geomtery for all children beneath them, such that if you can determine that this geometric volume is not in your view frustum at all, you can ignore that node altogether, and don't parse down it. But that isn't demonstrated above.


[edited by - Waverider on September 27, 2002 7:20:14 AM]

BSP Tree FAQ...

http://www.gamers.org/dhs/helpdocs/bsp_faq.html

The Joy of BSP Trees...

http://www.gamedev.net/reference/articles/article799.asp

botman

Thanks guys.

-CProgrammer

http://www.flipcode.com/misc/SamuelRanta-Eskola_BSPTrees.pdf

The above is by far the best explanation of BSPs I have found on the net. It is especially useful if you already know a bit about BSPs. It explains how you can create a LEAFY BSP (I always used to use a node based BSP which really isn''t as good.) It then explains how to generate portals and Possible Visibility Sets (PVS) to really improve performance. There is lots of pesudo code which I''ve found quite useful.

It also covers topics like Radiosity and Collision Detection using BSPs.

I especially like this paper, since I''ve found that good material on advanced BSP techniques are really hard to come by on the net. It''s like a big secret or something

Hope that helps.