engine03.shtml

3D游戏开发领域专家撰写的经典游戏启迪文章

 of tree is a <I>leaf-based</I> tree and looks like this:<BR>
<BR>
<p align="center">
<IMG SRC="0307.jpg" WIDTH="200" HEIGHT="150" ALT="a leaf-based world" BORDER="0">
 &nbsp; <IMG SRC="0308.jpg" WIDTH="200" HEIGHT="150" ALT="a leaf-based tree" BORDER="0">
</p><BR>
Notice a few important things:<BR>
<UL>
<LI>In both cases every node obtained a plane from a polygon.  This isn't
 strictly crucial, but it's a lot faster than trying to find an arbitrary plane.
<LI>The area in front of and behind every node is a convex space.  This will come in handy later.
<LI>The front portion of every LEAF NODE is of a finite volume.  This too, will be very useful later.
<LI>If the best dividing plane cuts through a polygon, the polygon is cut in half and each half is then
 used in the appropriate recursion.
</UL>
Now that's all well and good, but how do you code it?  Tsk tsk.  That will be your homework for the
 weekend, which is about how long it took me to write my first BSP building METHOD.  No, I Jest.  here's
 some code for building the node-based BSP tree from a set of polygons.<br>
</FONT>
<pre>
<FONT COLOR="Green">/* BuildTree( cPolygon *pList )
 * Given a linked list of polygons BuildTree finds the
 * best dividing plane and then cuts the entire set
 * based on that plane.  If there is anything left in
 * either half, the function recurses "down" that
 * branch of the tree.  Returns a success code.
 */</FONT>
eNodeReturn cNode<FONT COLOR="Navy">::</FONT>BuildTree<FONT COLOR="Navy">(</FONT> cPolygon <FONT COLOR="Navy">*</FONT>pList <FONT COLOR="Navy">) {</FONT>
  cPolygon <FONT COLOR="Navy">*</FONT>pBestDivider<FONT COLOR="Navy">,</FONT> <FONT COLOR="Navy">*</FONT>pTest<FONT COLOR="Navy">,</FONT>
           <FONT COLOR="Navy">*</FONT>pInsideList<FONT COLOR="Navy">,</FONT> <FONT COLOR="Navy">*</FONT>pOutsideList<FONT COLOR="Navy">;</FONT>

  pInsideList <FONT COLOR="Navy">=</FONT> NULL<FONT COLOR="Navy">;</FONT>
  pOutsideList <FONT COLOR="Navy">=</FONT> NULL<FONT COLOR="Navy">;</FONT>
  pBestDivider <FONT COLOR="Navy">=</FONT> FindBestDivider<FONT COLOR="Navy">(</FONT> pList <FONT COLOR="Navy">);</FONT>
  <FONT COLOR="Green">// pPlane is a member of cNode.</FONT>
  pPlane <FONT COLOR="Navy">=</FONT> pBestDivider<FONT COLOR="Navy">-></FONT>GetPlane<FONT COLOR="Navy">();</FONT>
  for<FONT COLOR="Navy">(</FONT> pTest <FONT COLOR="Navy">=</FONT> pList<FONT COLOR="Navy">;</FONT> pTest<FONT COLOR="Navy">;</FONT> pTest <FONT COLOR="Navy">=</FONT> pTest<FONT COLOR="Navy">-></FONT>Next<FONT COLOR="Navy">() ) {</FONT>
    <FONT COLOR="Green">// Test each polygon against the plane
    // and put them in the appropriate list.</FONT>
    <FONT COLOR="blue">switch</FONT><FONT COLOR="Navy">(</FONT> pTest<FONT COLOR="Navy">-></FONT>TestAgainstPlane<FONT COLOR="Navy">(</FONT> pPlane <FONT COLOR="Navy">) ) {</FONT>
      <FONT COLOR="blue">case</FONT> ZV_PLANE_BACK<FONT COLOR="Navy">:</FONT>
        <FONT COLOR="blue">if</FONT><FONT COLOR="Navy">(</FONT> !pInsideList <FONT COLOR="Navy">)</FONT> pInsideList <FONT COLOR="Navy">=</FONT> pTest<FONT COLOR="Navy">;</FONT>
        <FONT COLOR="blue">else</FONT> pTest<FONT COLOR="Navy">-></FONT>Link<FONT COLOR="Navy">(</FONT> pInsideList <FONT COLOR="Navy">);</FONT>
        <FONT COLOR="blue">break</FONT><FONT COLOR="Navy">;</FONT>
      <FONT COLOR="blue">case</FONT> ZV_PLANE_FRONT<FONT COLOR="Navy">:</FONT>
        <FONT COLOR="blue">if</FONT><FONT COLOR="Navy">(</FONT> !pOutsideList <FONT COLOR="Navy">)</FONT> pOutsideList <FONT COLOR="Navy">=</FONT> pTest<FONT COLOR="Navy">;</FONT>
        <FONT COLOR="blue">else</FONT> pTest<FONT COLOR="Navy">-></FONT>Link<FONT COLOR="Navy">(</FONT> pOutsideList <FONT COLOR="Navy">);</FONT>
        <FONT COLOR="blue">break</FONT><FONT COLOR="Navy">;</FONT>
      <FONT COLOR="blue">case</FONT> ZV_PLANE_ON<FONT COLOR="Navy">:</FONT>
        <FONT COLOR="Green">// pPolygons is a member of cNode.</FONT>
        <FONT COLOR="blue">if</FONT><FONT COLOR="Navy">(</FONT> !pPolygons <FONT COLOR="Navy">)</FONT> pPolygons <FONT COLOR="Navy">=</FONT> pTest<FONT COLOR="Navy">;</FONT>
        <FONT COLOR="blue">else</FONT> pTest<FONT COLOR="Navy">-></FONT>Link<FONT COLOR="Navy">(</FONT> pPolygons <FONT COLOR="Navy">);</FONT>
        <FONT COLOR="blue">break</FONT><FONT COLOR="Navy">;</FONT>
      <FONT COLOR="blue">case</FONT> ZV_PLANE_SPLIT<FONT COLOR="Navy">:</FONT>
        cPolygon <FONT COLOR="Navy">*</FONT>pIn<FONT COLOR="Navy">,</FONT> <FONT COLOR="Navy">*</FONT>pOut<FONT COLOR="Navy">;</FONT>

        pTest<FONT COLOR="Navy">-></FONT>Split<FONT COLOR="Navy">(</FONT> pPlane<FONT COLOR="Navy">, & </FONT>pIn<FONT COLOR="Navy">, & </FONT>pOut <FONT COLOR="Navy">);</FONT>
        <FONT COLOR="Green">// check to make sure Split succeeded</FONT>
        <FONT COLOR="blue">delete</FONT> pTest<FONT COLOR="Navy">;</FONT>
        <FONT COLOR="blue">if</FONT><FONT COLOR="Navy">(</FONT> !pInsideList <FONT COLOR="Navy">)</FONT> pInsideList <FONT COLOR="Navy">=</FONT> pIn<FONT COLOR="Navy">;</FONT>
        <FONT COLOR="blue">else</FONT> pIn<FONT COLOR="Navy">-></FONT>Link<FONT COLOR="Navy">(</FONT> pInsideList <FONT COLOR="Navy">);</FONT>
        <FONT COLOR="blue">if</FONT><FONT COLOR="Navy">(</FONT> !pOutsideList <FONT COLOR="Navy">)</FONT> pOutsideList <FONT COLOR="Navy">=</FONT> pOut<FONT COLOR="Navy">;</FONT>
        <FONT COLOR="blue">else</FONT> pOut<FONT COLOR="Navy">-></FONT>Link<FONT COLOR="Navy">(</FONT> pOutsideList <FONT COLOR="Navy">);</FONT>
        <FONT COLOR="blue">break</FONT><FONT COLOR="Navy">;</FONT>
    <FONT COLOR="Navy">}</FONT>
  <FONT COLOR="Navy">}</FONT>

  <FONT COLOR="Green">// Recurse, if necessary.
  // pInside and pOutside are members of cNode.</FONT>
  <FONT COLOR="blue">if</FONT><FONT COLOR="Navy">(</FONT> pInsideList <FONT COLOR="Navy">) {</FONT>
    pInside = <FONT COLOR="blue">new</FONT> cNode<FONT COLOR="Navy">();</FONT>
    <FONT COLOR="Green">// check to see if pInside exists</FONT>
    pInside->BuildTree<FONT COLOR="Navy">(</FONT> pInsideList <FONT COLOR="Navy">);</FONT>
    <FONT COLOR="Green">// check to make sure BuildTree succeeded</FONT>
  <FONT COLOR="Navy">}</FONT>
  <FONT COLOR="blue">if</FONT><FONT COLOR="Navy">(</FONT> pOutsideList <FONT COLOR="Navy">) {</FONT>
    pOutside = <FONT COLOR="blue">new</FONT> cNode<FONT COLOR="Navy">();</FONT>
    <FONT COLOR="Green">// check to see if pOutside exists</FONT>
    pOutside>BuildTree<FONT COLOR="Navy">(</FONT> pOutsideList <FONT COLOR="Navy">);</FONT>
    <FONT COLOR="Green">// check to make sure BuildTree succeeded</FONT>
  <FONT COLOR="Navy">}</FONT>
  <FONT COLOR="blue">return</FONT> ZV_NODE_OK<FONT COLOR="Navy">;</FONT>
<FONT COLOR="Navy">}</FONT>
</pre>
<FONT face="arial" size="-1">Thought that was rough?  The first time is always the worst.  Nowadays I
 can do this in my sleep and I'm sure you will too in no time at all.  Of course, you still have to
 fill in the blanks and that, as they say, is another story.  But it's going to be worth it, oh yes!
 Let me show you just how easy it is to render using BSPs.<BR>
</FONT>
<PRE>
<FONT COLOR="Green">/* RenderTree( pCamera *pCam )
 * Recursively calls all the nodes in the tree
 * and renders them.  The tree is "walked" from
 * back to front to ensure proper polygon ordering.
 * This method will work with both leaf and node
 * based trees.
 */</FONT>
<FONT COLOR="blue">void</FONT> cNode<FONT COLOR="Navy">::</FONT>RenderTree<FONT COLOR="Navy">(</FONT> cCamera <FONT COLOR="Navy">*</FONT>pCam <FONT COLOR="Navy">) {</FONT>
  <FONT COLOR="blue">int</FONT> result<FONT COLOR="Navy">;</FONT>
  
  result <FONT COLOR="Navy">=</FONT> ClipToCamera<FONT COLOR="Navy">(</FONT> pCam <FONT COLOR="Navy">);</FONT>
  <FONT COLOR="blue">if</FONT><FONT COLOR="Navy">(</FONT> result <FONT COLOR="Navy">==</FONT> ZV_NODE_CULLED <FONT COLOR="Navy">)</FONT> <FONT COLOR="blue">return</FONT><FONT COLOR="Navy">;</FONT>

  <FONT COLOR="blue">switch</FONT><FONT COLOR="Navy">(</FONT> result </FONT>pCam <FONT COLOR="Navy">) {</FONT>
    <FONT COLOR="blue">case</FONT> ZV_NODE_FRONT<FONT COLOR="Navy">:</FONT>
      <FONT COLOR="Green">// Camera is in front of this node's plane</FONT>
      pOutside<FONT COLOR="Navy">-></FONT>RenderTree<FONT COLOR="Navy">(</FONT> pCam <FONT COLOR="Navy">);</FONT>
      RenderNode<FONT COLOR="Navy">(</FONT> pCam <FONT COLOR="Navy">);</FONT>  <FONT COLOR="Green">// render this node's polygons</FONT>
      pInside<FONT COLOR="Navy">-></FONT>RenderTree<FONT COLOR="Navy">(</FONT> pCam <FONT COLOR="Navy">);</FONT>
      <FONT COLOR="blue">break</FONT><FONT COLOR="Navy">;</FONT>
    <FONT COLOR="blue">case</FONT> ZV_NODE_BACK<FONT COLOR="Navy">:</FONT>
      <FONT COLOR="Green">// Camera is behind this node's plane</FONT>
      pInside<FONT COLOR="Navy">-></FONT>RenderTree<FONT COLOR="Navy">(</FONT> pCam <FONT COLOR="Navy">);</FONT>
      RenderNode<FONT COLOR="Navy">(</FONT> pCam <FONT COLOR="Navy">);</FONT>  <FONT COLOR="Green">// render this node's polygons</FONT>
      pOutside<FONT COLOR="Navy">-></FONT>RenderTree<FONT COLOR="Navy">(</FONT> pCam <FONT COLOR="Navy">);</FONT>
      <FONT COLOR="blue">break</FONT><FONT COLOR="Navy">;</FONT>
  <FONT COLOR="Navy">}</FONT>
<FONT COLOR="Navy">}</FONT>
</PRE>
<FONT FACE="arial" SIZE="-1">
Now let's just say that you've got a <i>really</i> big tree somewhere in the hundreds of nodes and the
 thousands of polygons.  BSPs will be great for drawing everything in the right order, but isn't there
 any way to save us from trying to draw a whole bunch of stuff that won't be seen anyhow?  The answer
 is yes, there are many.  For now let's start with something basic, node boundings.<br>
<br>
Bounding boxes and bounding spheres have been in use for ages.  The simplest bounding is a sphere that
 encompasses a certain amount of stuff.  Four or Five really quick tests are all that you need to
 determine if your camera can see the sphere and that tells you if you can see any of the stuff inside.
 So how about a recursive function that walks through every node in the BSP tree and calculates the
 smallest sphere needed to contain every part of the current node <b>and</b> it's leaves?  That way the
 instant you discover that a node is outside the camera view you can stop walking that branch because
 you know that none of it's leaves are visible, either.<br>
<br>
<hr>
<br>
Some tips for debugging your BSP building algorithm:<br>
<ul>
<li><b>Limit the depth of recursion</b> by using a static or global counter.  increment it every time
 you descend the tree and subtract when you go back.  If the value gets to high, return immediately.
 However, you have to be careful with this because the number of function calls is NOT linear with
 the maximum value.  what I mean is this:  because every branch of the tree has two leaves it is very
 possible that you have O(n<sup>2</sup>) calls to make.  So if you pick a depth of 5 as your maximum
 there will be 25 function calls.  If you pick 10 you'll have a hundred function calls.
<li><b>Don't bite off more than you can chew.</b> In other words, start with the simplest possible
 model and work your way up.  I recommend the following sets:<br>
 <ol>
 <li>two parallel polygons, each in front of the other.
 <li>two parallel polygons, each behind the other.
 <li>two polygons that are coplanar
 <li>two square polygons that intersect each other
 <li>two polygons that share one edge but are NOT coplanar.
 </ol>
If all those cases work, every case should work.
<li><b>If many polygons reference a single plane class</b> be sure when splitting to use the polygon
 normal or everything will be <i>backwards</i> and (especially in the case of leaf-based trees) all
 hell will break loose.
</ul>
<br>
<hr>
<br>
So we've managed to cover how BSPs are built, how BSPs are rendered and a very quick way of clipping at
 least some of the tree to save us CPU time.  But there's more still to come!  We're going to take a
 look at Constructive Solid Geometry, Possible Visible Set and then get into some even cooler stuff like
 mirrors and radiosity lighting.  BSPs - the tree with a million uses.<br>
<br>
<a href="#top">Back to the top</a>
<hr>
<b>PREV: <a href="Engine02.shtml">Overall structure</a></b><br>
<b>NEXT: <a href="Engine04.shtml">Constructive Solid Geometry</a></b><br>
<BR><BR></FONT>
</TD></TR></TABLE>
</TD>
</TR>

</TABLE>

<HR ALIGN="CENTER" SIZE="1" WIDTH="700" NOSHADE>
<FONT FACE="arial" SIZE="-2">All photos copyright of their respective owners.  All other content of this website is &copy; 1997-1999 Dan Royer.<BR>
Designed for IE 5.0+, 800x600x16 or greater.  Some pages use style sheets.<br>
<A HREF="http://members.home.com/droyer/index.html"
   TITLE="Dan's Homepage">http://members.home.com/droyer/index.html</A><br>
</FONT>

</CENTER>
<BR>
<BR>

</BODY>
</HTML>
</HTML>