Using a Binary Space Partition Tree

Sometimes in games we work with a lot of geometry and huge 3D worlds. If our game camera was to render all of it all the time, then it would be extremely expensive and the game would not be able to run smoothly at higher frame rates. Hence we need to write intelligent algorithms so that the world is divided into more manageable chunks that can be traversed easily using a tree structure.

Getting ready

You need to have a working Windows machine and a working copy of Visual Studio.

How to do it…

Add a source file called Source.cpp. Then add the following code to it:

sNode(elemVec& toProcess, const T_treeAdaptor& adap)
      : m_pFront(NULL)
      , m_pBack(NULL)
    {
      // Setup
      elemVec frontVec, backVec;
      frontVec.reserve(toProcess.size());
      backVec.reserve(toProcess.size());

      // Choose which node we're going to use.
      adap.ChooseHyperplane(toProcess, &m_hp);

      // Iterate across the rest of the polygons
      elemVec...