title: Binary Space Partitioning - Error in space partitioning logic
body: <p>So I've been implementing my first BSP Tree, and I think I found a flaw in my logic. I'm pretty lost as to how I could actually refactor this properly to work the way it should.</p>
  
  <p>Here's the constructor (an explanation follows):</p>
  
  <pre><code>BSPTree::BSPTree( const polygonList_t&amp; list )
      : mRoot( nullptr )
  {
      polygonList_t front, back;
  
      auto eol = list.end();
      Polygon* rootSplitter = list[ 0 ];
  
      vec3 rootSplitPos;
      rootSplitter-&gt;GetPosition( rootSplitPos );
  
      for( auto iPoly = list.begin() + 1; iPoly != eol; ++iPoly )
      {
          vec3 resolvePos;
          ( *iPoly )-&gt;GetPosition( resolvePos );
  
          switch( ResolvePosition( rootSplitPos, resolvePos ) )
          {
              case POSITION_FRONT:
                  front.push_back( *iPoly );
                  break;
  
              case POSITION_BACK:
                  back.push_back( *iPoly );
                  break;
  
              case POSITION_SPLIT:
              {
                  Polygon* toSplit = *iPoly;
                  list.erase( iPoly );
  
                  Polygon* outFront = new Polygon;
                  Polygon* outBack  = new Polygon;
  
                  SplitPolygon( resolvePos, toSplit, outFront, outBack );
  
                  front.push_back( outFront );
                  back.push_back( outBack );
  
                  // finally we kill this one off
                  delete toSplit;
                  toSplit = nullptr;
              }
                  break;
          }
      }
  
      mRoot = BSP_MakeNode();
  
      mRoot-&gt;splitter = rootSplitter;
  
      SplitSpace( mRoot, front );
      SplitSpace( mRoot, back );
  }
  </code></pre>
  
  <p>In a nutshell, we receive a typedeffed <code>std::vector&lt; Polygon* &gt;</code> with an arbitrary number of heap-allocated Polygon objects. We then want to separate them into two categories: those in front of a certain center element, and those behind. Naturally, we declare two lists of the same typedef and call them <code>front</code> and <code>back</code>, respectively.</p>
  
  <p>First, we select a Polygon (eventually I'd like to find a polygon which appears to be the best fit for a root partitioning plane), and then we iterate through our original list, checking for one of 3 cases:</p>
  
  <p>(<strong>NOTE -</strong> for brevity's sake, I'm just going to dub our root partition polygon as <strong>root</strong>)</p>
  
  <ul>
  <li><p><code>POSITION_FRONT</code>: We know our current polygon within the list is in front of <em>root</em>, so we naturally add this polygon to our front list.</p></li>
  <li><p><code>POSITION_BACK</code>: Same as position, the only difference being that this polygon is behind <em>root</em>.</p></li>
  <li><p><code>POSITION_SPLIT</code>: We can't determine whether or not this polygon is in front of <em>root</em> or behind it, so we split it into two pieces and insert the front and back portions of it into their respective lists.</p></li>
  </ul>
  
  <p>Finally, once we've divided our polygons into their front and back lists, we further subdivide our space, using the root as a basis for the initial subdividing.</p>
  
  <pre><code>void BSPTree::SplitSpace( bspNode_t* node, polygonList_t&amp; polygons )
  {
      if ( polygons.size() == 0 ) return;
  
      // grab the first polygon within the list,
      // and then subtract it from the list itself.
      Polygon* next = polygons[ 0 ];
      polygons.pop_back();
  
      vec3 splitPos;
      node-&gt;splitter-&gt;GetPosition( splitPos );
  
      vec3 toResolve;
      next-&gt;GetPosition( toResolve );
  
      switch( ResolvePosition( splitPos, toResolve ) )
      {
          case POSITION_FRONT:
              node-&gt;front = BSP_MakeNode();
              node-&gt;front-&gt;splitter = next;
              SplitSpace( node-&gt;front, polygons );
              break;
  
          case POSITION_BACK:
              node-&gt;back = BSP_MakeNode();
              node-&gt;back-&gt;splitter = next;
              SplitSpace( node-&gt;back, polygons );
              break;
  
          case POSITION_SPLIT:
          {
              Polygon* outFront = new Polygon;
              Polygon* outBack  = new Polygon;
  
              SplitPolygon( toResolve, next, outFront, outBack );
  
              node-&gt;front = BSP_MakeNode();
              node-&gt;back  = BSP_MakeNode();
  
              node-&gt;front-&gt;splitter = outFront;
              node-&gt;back-&gt;splitter = outBack;
  
              SplitSpace( node-&gt;front, polygons );
              SplitSpace( node-&gt;back, polygons );
          }
              break;
      }
  }
  </code></pre>
  
  <p>Now, we perform a very similar sequence of operations, the key difference being that we are <em>further subdividing an already partitioned space until each polygon has a given position within the node tree, which is either in front of or behind its parent node</em>. Of course, we do this recursively. </p>
  
  <p>The problem I'm currently seeing lies in the <code>POSITION_SPLIT</code> case evaluation within the switch statement above:</p>
  
  <pre><code>        case POSITION_SPLIT:
          {
              Polygon* outFront = new Polygon;
              Polygon* outBack  = new Polygon;
  
              SplitPolygon( toResolve, next, outFront, outBack );
  
              node-&gt;front = BSP_MakeNode();
              node-&gt;back  = BSP_MakeNode();
  
              node-&gt;front-&gt;splitter = outFront;
              node-&gt;back-&gt;splitter = outBack;
  
              SplitSpace( node-&gt;front, polygons ); // here
              SplitSpace( node-&gt;back, polygons );  // and here
          }
  </code></pre>
  
  <p>In conjunction with two other factors:</p>
  
  <ul>
  <li><p>For every polygon obtained from the given reference parameter <code>polygons</code>, we <code>pop_back()</code> the pointer which holds that polygon within the list after assigning it to a temporary.</p></li>
  <li><p>Tying in with the aforementioned, every call to <code>SplitSpace(...)</code> yields a check to see if its received list is empty. If so, nothing is done, and the recursive subdivision has been completed for that list.</p></li>
  </ul>
  
  <p><strong>Because of these two factors, I cannot help but think that, in the <code>POSITION_SPLIT</code> case evaluation, the second call to <code>SplitSpace(...)</code> is useless: the list will be exhausted before the second call (to accomodate for the <em>back</em> portion of the split) is made.</strong></p>
  
  <p><strong>Question</strong></p>
  
  <p>So, what is a solution to this problem that will at least get me headed back on the right track?</p>