Clouds3D crashes because there is no Light

[simgear.git] / simgear / scene / sky / clouds3d / SkyBVTree.hpp

//------------------------------------------------------------------------------
// File : SkyBVTree.hpp
//------------------------------------------------------------------------------
// Empyrean / SkyWorks : Copyright 2002 Mark J. Harris
//------------------------------------------------------------------------------
/**
* @file SkyBVTree.hpp
* 
* This source was written by Wesley Hunt.  Many thanks to him for providing it.
*/
//-----------------------------------------------------------------------------
// SkyBVTree.hpp
//
// Author:      Wesley Hunt (hunt@cs.unc.edu)
// Date:        2000/12/19
//-----------------------------------------------------------------------------
//      Overview
//      --------
//              declare an SkyBVTree with whatever object type and bounding volume type you
//              want. The hard part is to pass in a NodeSplitter class that determines how
//              to split a node up. See below for a description of its requirements.
//              Finally, use that tree like so:
//                      * BeginTree()
//                      *   AddObject(Object, ObjectBV)
//                      *   ...
//                      * EndTree()
//                      < Do whatever you want with GetRoot() >
//                      < Use GetLeftChild() and GetRightChild() to traverse the nodes >
//
//              The class hierarchy is designed for a flexible, simple public interface.
//              This pushes some extra complexity into the class hierarchy, but there are two
//              main advantages to the final approach:
//                      1. There are no interface requirements for the Object and BoundingVolume
//                         template parameters. This means you don't have to modify your existing
//                         class interfaces to use them with the tree. 
//                      2. All the dependent logic for dealing with the bounding volumes is pushed 
//                         into the NodeSplitter class. So there is one centralized location for 
//                         adapting your bounding volume classes to work with the tree. See the 
//                         description of the NodeSplitter template requirements for more details.
//
//      Class Descriptions
//      ------------------
//
//              SkyBaseBVTree
//              -------------
//              declares the node class that the tree holds. It exposes
//              the public functions of the nodes and defines protected accessors that
//              the derived tree class can use to manipulate nodes and build the tree.
//
//                      Node
//                      ----
//                      This is the class that gives access to the tree. You can access each
//                      object and bounding volume owned by a node, along with that node's
//                      children.
//
//                      NodeObject
//                      ----------------
//                      An aggregation of an object and its associated bounding volume.
//                      Each node in the tree essentially owns an array of NodeObjects. This
//                      array is passed to the NodeSplitter class to allow it to examine a 
//                      node's contained objects before making a decision on how to split the 
//                      node up.
//
//              SkyBVTree
//              ---------
//              The main tree class. To use it, supply and object type, a bounding volume
//              type, and a NodeSplitter class that is used to split the nodes up during
//              tree construction.
//
//      Template class requirements
//      ---------------------------
//
//              Object
//              ------
//              None
//
//              BoundingVolume
//              --------------
//              None
//
//              NodeSplitter
//              ------------
//              This is the user-supplied class that decides how to split a node during
//              tree construction. It is given an array of NodeObjects that the node owns and 
//              is responsible for determining the node's bounding volume as well as how to 
//              split the node up into left and right children.
//              The required API is as follows:
//              
//                      * a constructor that takes an array of NodeObject and an unsigned int giving 
//                        the size of the array. These are the objects owned by the node to be split.
//                      * a method GetNodeBV() that returns the BoundingVolume of the  node. 
//                        Typically this is the union of the bounding volumes of the objects owned 
//                        by the node.
//                      * A unary function operator used to partition the objects in the node. The
//                        operator must take a single NodeObject as a parameter and return as
//                        a bool whether to place the NodeObject in the left or right child. 
//                        Basically, it should be compatible with std::partition using NodeObjects.
//                      * A binary function operator used to sort the objects. If a partition fails, 
//                        the nodes are then sorted based on this function and half are sent to each child.
//                        This operator must define a total ordering of the NodeObjects.
//                        Basically, it should be compatible with std::sort using NodeObjects.
//                        
//              Example:
//                      struct NodeSplitter
//                      {
//                              NodeSplitter(const NodeObject* objs, unsigned int numObjs);
//                              BoundingVolume& GetNodeBV() const;
//                              // Partition predicate
//                              bool operator()(const NodeObject& obj) const;
//                              // Sort predicate
//                              bool operator()(const NodeObject& obj1, const NodeObject& obj2) const;
//                      };
//
//-----------------------------------------------------------------------------
#ifndef __SKYBVTREE_HPP__
#define __SKYBVTREE_HPP__

#include <algorithm>
#include <vector>

//-----------------------------------------------------------------------------
// SkyBaseBVTree<Object, BoundingVolume>
//-----------------------------------------------------------------------------
// See header description for details.
//-----------------------------------------------------------------------------
template <class Object, class BoundingVolume>
class SkyBaseBVTree
{
public:
  typedef BoundingVolume BV;
  class NodeObject;
  
public:
  class Node
  {
    friend class SkyBaseBVTree<Object, BoundingVolume>;
  public:
    Node() : _pObjs(NULL), _iNumObjs(0) {}
    Node(NodeObject* pObjs, unsigned int iNumObjs) : _pObjs(pObjs), _iNumObjs(iNumObjs)  {}
  
    // Public interface
    const Object& GetObj(unsigned int index) const { assert(_iNumObjs != 0 && _pObjs != NULL && index < _iNumObjs); return _pObjs[index].GetObj(); }
    const BV&     GetBV(unsigned int index) const  { assert(_iNumObjs != 0 && _pObjs != NULL && index < _iNumObjs); return _pObjs[index].GetBV(); }
    unsigned int  GetNumObjs() const      { assert(_iNumObjs != 0 && _pObjs != NULL); return _iNumObjs; }
    const BV&     GetNodeBV() const       { assert(_iNumObjs != 0 && _pObjs != NULL); return _volume; }
    const Node*   GetLeftChild() const    { assert(_iNumObjs != 0 && _pObjs != NULL); return this+1; }
    const Node*   GetRightChild() const   { assert(_iNumObjs != 0 && _pObjs != NULL); return this+(GetLeftChild()->GetNumObjs()<<1); }
    bool          IsLeaf() const          { assert(_iNumObjs != 0 && _pObjs != NULL); return _iNumObjs == 1; }
  
  private:
    // List of Objects owned by the node
    NodeObject    *_pObjs;
    unsigned int  _iNumObjs;
    BV            _volume;
  };

public:
  class NodeObject
  {
  public:
    NodeObject(const Object& o, const BV& v) : _obj(o), _volume(v) {}
  
    const Object& GetObj() const { return _obj;    }
    const BV&     GetBV() const  { return _volume; }
  private:
    Object _obj;
    BV     _volume;
  };
      
protected:
  // Give non-const access to the node for descendant classes to build the tree
  BV& GetNodeBV(Node* pNode)          { assert(pNode->_iNumObjs != 0 && pNode->_pObjs != NULL); return pNode->_volume; }
  Node* GetLeftChild(Node* pNode)                 { assert(pNode->_iNumObjs != 0 && pNode->_pObjs != NULL); return pNode+1; }
  Node* GetRightChild(Node* pNode)              { assert(pNode->_iNumObjs != 0 && pNode->_pObjs != NULL); return pNode+(GetLeftChild(pNode)->GetNumObjs()<<1); }
  NodeObject* GetObjs(Node* pNode)    { assert(pNode->_iNumObjs != 0 && pNode->_pObjs != NULL); return pNode->_pObjs; }
  
  // Links a node's children by assigning the given number of objects to each child
  // assumes the node has already had it's objects partitioned
  void LinkNodeChildren(Node* pNode, unsigned int iLeftNumObjs)
  {
    assert(pNode->_iNumObjs != 0 && pNode->_pObjs != NULL); 
    GetLeftChild(pNode)->_pObjs     = pNode->_pObjs;
    GetLeftChild(pNode)->_iNumObjs  = iLeftNumObjs;
    GetRightChild(pNode)->_pObjs    = pNode->_pObjs + iLeftNumObjs;
    GetRightChild(pNode)->_iNumObjs = pNode->_iNumObjs - iLeftNumObjs;
  }        
};


//------------------------------------------------------------------------------
// Function               : ClearVector
// Description      : 
//------------------------------------------------------------------------------
/**
 * @fn ClearVector(std::vector<T>& vec)
 * @brief This utility function uses the std::vector::swap trick to free the memory of a vector
 *
 * This is necessary since clear() doesn't actually free anything.
 */ 
template<class T>
void ClearVector(std::vector<T>& vec)
{
  std::vector<T>().swap(vec);
}


//-----------------------------------------------------------------------------
// SkyBVTree<Object, BoundingVolume, NodeSplitter>
//-----------------------------------------------------------------------------
// See header description for details.
//-----------------------------------------------------------------------------
template <class Object, class BoundingVolume, class NodeSplitter>
class SkyBVTree : public SkyBaseBVTree<Object, BoundingVolume>
{
public:
  typedef SkyBaseBVTree<Object, BoundingVolume> BaseTree;
  typedef BaseTree::BV BV;
  typedef BaseTree::NodeObject NodeObject;
  typedef BaseTree::Node Node;
  
  void Clear()
  {
    BeginTree();
  }
  
  void BeginTree(unsigned int iNumObjs = 0)
  {
    ClearVector(_objList);
    ClearVector(_nodes);
    if (iNumObjs > 0) _objList.reserve(iNumObjs);
  }
  
  void AddObject(const Object &obj, const BV& volume)
  {
    _objList.push_back(NodeObject(obj, volume));
  }
  
  void EndTree()
  {
    if (_objList.size() == 0) return;
    // Initialize the root node with all the objects
    _nodes.push_back(Node(&_objList[0], _objList.size()));
    // create room for the other nodes. They are initialized in BuildTree().
    _nodes.reserve(_objList.size()*2-1);
    _nodes.resize(_objList.size()*2-1);
    BuildTree(&_nodes[0]);
  }
  
  const Node *GetRoot() const { return _nodes.empty() ? NULL : &_nodes[0]; }
  
  // Memory usage info
  unsigned int CalcMemUsage() const
  {
    unsigned int usage = 0;
    usage += sizeof(*this);
    usage += _objList.capacity() * sizeof(_objList[0]);
    usage += _nodes.capacity() * sizeof(_nodes[0]);
    return usage;
  }
  
public:
private:
  // Does the real work
  void BuildTree(Node *pCurNode)
  {
    int iLeftNumObjs;
    {
      // Initialize the node splitter with the current node
      NodeSplitter splitter(GetObjs(pCurNode), pCurNode->GetNumObjs());
      
      // set the node's bounding volume using the splitter
      GetNodeBV(pCurNode) = splitter.GetNodeBV();
      
      // When a node has one object we can stop
      if (pCurNode->GetNumObjs() == 1) return;
      
      // Try and partition the objects
      iLeftNumObjs = std::partition(GetObjs(pCurNode), &GetObjs(pCurNode)[pCurNode->GetNumObjs()], splitter) - GetObjs(pCurNode);
      
      if ((iLeftNumObjs == 0) || (iLeftNumObjs == pCurNode->GetNumObjs()))
      {
        // Partition failed. Sort and split again to force a complete tree
        std::sort(GetObjs(pCurNode), &GetObjs(pCurNode)[pCurNode->GetNumObjs()], splitter);
        iLeftNumObjs = pCurNode->GetNumObjs() / 2;
      }
    }
    
    LinkNodeChildren(pCurNode, iLeftNumObjs);
    BuildTree(GetLeftChild(pCurNode));
    BuildTree(GetRightChild(pCurNode));
  }
  
  std::vector<Node>       _nodes;
  std::vector<NodeObject> _objList;
};

#endif //__SKYBVTREE_HPP__