simgear/scene/sky/clouds3d/SkyBVTreeSplitter.hpp

   1 //============================================================================
   2 // File          : SkyBVTreeSplitter.hpp
   3 //
   4 // Author        : Wesley Hunt
   5 //
   6 // Content       : NodeSplitter classes for SkyBVTrees using SkyBoundingBox or
   7 //                 SkyBoundingSphere (not implemented).
   8 //
   9 //============================================================================
  10 #ifndef __SKYBVTREESPLITTER_HPP__
  11 #define __SKYBVTREESPLITTER_HPP__
  12
  13 //----------------------------------------------------------------------------
  14 //-- Includes ----------------------------------------------------------------
  15 //----------------------------------------------------------------------------
  16 #include "SkyBVTree.hpp"
  17 #include "SkyMinMaxBox.hpp"
  18 //#include <Mlx/MlxBoundingSphere.hpp>
  19 //#if _MSC_VER == 1200
  20 //#include <Auxlib/AuxCompileTimeChecker.hpp>
  21 //#endif
  22 //----------------------------------------------------------------------------
  23 //-- Forward Declarations ----------------------------------------------------
  24 //----------------------------------------------------------------------------
  25 // A strategy for splitting nodes compatible with bounding boxes and spheres.
  26 template<class Object> class SkyBoundingBoxSplitter;
  27 // SkyBVTree compatible node splitters implemented using the above strategy.
  28 template<class Object> class SkyAABBTreeSplitter;
  29 //template<class Object> class SkySphereTreeSplitter;
  30
  31 //----------------------------------------------------------------------------
  32 //-- Defines, Constants, Enumerated Types ------------------------------------
  33 //----------------------------------------------------------------------------
  34 const float rLongObjectPercentageTolerance = 0.75f;
  35
  36 //----------------------------------------------------------------------------
  37 //      SkyBoundingBoxSplitter
  38 //----------------------------------------------------------------------------
  39 //      This class defines a NodeSplitter strategy that has the functionality
  40 //      required by SkyBVTree's NodeSplitter template class. Can be used with
  41 //      SkyMinMaxBox and SkyBoundingSphere.
  42 //
  43 //      It defines a two-tiered split strategy:
  44 //
  45 //      * First it tries to separate large objects from any smaller objects.
  46 //      * If there are no large objects, it splits along the midpoint of the longest
  47 //        axis defined by the objects.
  48 //      * Finally, if all else fails, it defines a total ordering along the longest
  49 //        axis based on the center of each node.
  50 //----------------------------------------------------------------------------
  51 template<class Object>
  52 class SkyBoundingBoxSplitter
  53 {
  54 public:
  55         typedef SkyBaseBVTree<Object, SkyMinMaxBox>::NodeObject NodeObjectBox;
  56         //typedef SkyBaseBVTree<Object, SkyBoundingSphere>::NodeObject NodeObjectSphere;
  57
  58 #if _MSC_VER == 1200
  59         // !!! WRH HACK MSVC++6 SP5 Workaround.
  60         // VC6 can't disambiguate this constructor because it doesn't consider the two
  61         // NodeObject templates to be different classes for the purposes of
  62         // overloading. It won't recognize that the second template parameters are
  63         // different. Forcing them to be explicit template specializations fixes
  64         // the problem.
  65         template<class BV>
  66         SkyBoundingBoxSplitter(const SkyBaseBVTree<Object, BV>::NodeObject*, unsigned int)
  67         {
  68                 //AUX_STATIC_CHECK(false, VisualC_6_WorkAround); ???
  69         }
  70         template<>
  71 #endif
  72         SkyBoundingBoxSplitter(const NodeObjectBox* pObjs, unsigned int iNumObjs)
  73         {
  74                 for (unsigned int i = 0; i < iNumObjs; ++i)
  75                 {
  76                         _nodeBBox.Union(pObjs[i].GetBV());
  77                 }
  78                 Init(pObjs, iNumObjs);
  79         }
  80 /*#if _MSC_VER == 1200
  81         template<>
  82 #endif
  83 SkyBoundingBoxSplitter(const NodeObjectSphere* objs,
  84 #ifdef _PLATFORM_XBOX
  85         Int32
  86 #else
  87         UInt32
  88 #endif
  89         numObjs)
  90         {
  91                 for (int i=0; i<numObjs; ++i)
  92                 {
  93                         SkyMinMaxBox box;
  94                         box.AddPoint(objs[i].GetBV().GetCenter());
  95                         box.Bloat(objs[i].GetBV().GetRadius());
  96                         _nodeBBox.Union(box);
  97                 }
  98                 Init(objs, numObjs);
  99         }*/
 100
 101         template<class nodeObj>
 102         bool SplitLeft(const nodeObj& obj) const
 103         {
 104                 if (_bIsolateLongObjects)
 105                         return GetSplitAxisLength(obj.GetBV()) < _rMaxObjectLength;
 106                 else
 107                         return GetSplitAxisCenter(obj.GetBV()) < _rSplitValue;
 108         }
 109
 110         template<class nodeObj>
 111         bool LessThan(const nodeObj& obj1, const nodeObj& obj2) const
 112         {
 113                 return GetSplitAxisCenter(obj1.GetBV()) < GetSplitAxisCenter(obj2.GetBV());
 114         }
 115
 116         const SkyMinMaxBox& GetNodeBBox() const { return _nodeBBox; }
 117
 118 private:
 119         template<class nodeObj>
 120         void Init(const nodeObj* pObjs, unsigned int iNumObjs)
 121         {
 122                 _iSplitAxis       = FindSplitAxis(_nodeBBox);
 123                 _rSplitValue      = FindSplitValue(_nodeBBox, _iSplitAxis);
 124                 _rMaxObjectLength = GetSplitAxisLength(_nodeBBox) * rLongObjectPercentageTolerance;
 125
 126                 _bIsolateLongObjects = false;
 127                 for (unsigned int i = 0; i < iNumObjs; ++i)
 128                 {
 129                         if (GetSplitAxisLength(pObjs[i].GetBV()) > _rMaxObjectLength)
 130                         {
 131                                 _bIsolateLongObjects = true;
 132                                 break;
 133                         }
 134                 }
 135         }
 136
 137         int FindSplitAxis(const SkyMinMaxBox& bbox)
 138         {
 139                 int iAxis = 0, i;
 140                 Vec3f vecExt = bbox.GetMax() - bbox.GetMin();
 141                 for (i = 1; i < 3; ++i)  if (vecExt[i] > vecExt[iAxis]) iAxis = i;
 142                 return iAxis;
 143         }
 144         float FindSplitValue(const SkyMinMaxBox& bbox, int iSplitAxis)
 145         {
 146                 return (bbox.GetMin()[iSplitAxis] + bbox.GetMax()[iSplitAxis])*0.5f;
 147         }
 148
 149         /*float GetSplitAxisLength(const SkyBoundingSphere& sphere) const
 150         {
 151                 return 2.f*sphere.GetRadius();
 152         }*/
 153         float GetSplitAxisLength(const SkyMinMaxBox& bbox) const
 154         {
 155                 return bbox.GetMax()[_iSplitAxis] - bbox.GetMin()[_iSplitAxis];
 156         }
 157
 158         float GetSplitAxisCenter(const SkyMinMaxBox& bbox) const
 159         {
 160                 return (bbox.GetMin()[_iSplitAxis] + bbox.GetMax()[_iSplitAxis]) * 0.5f;
 161         }
 162         /*float GetSplitAxisCenter(const SkyBoundingSphere& sphere) const
 163         {
 164                 return sphere.GetCenter()[SplitAxis];
 165         }*/
 166
 167         int   _iSplitAxis;
 168         float _rSplitValue;
 169         bool  _bIsolateLongObjects;
 170         float _rMaxObjectLength;
 171
 172         SkyMinMaxBox _nodeBBox;
 173 };
 174
 175 //----------------------------------------------------------------------------
 176 //      SkyAABBTreeSplitter
 177 //----------------------------------------------------------------------------
 178 //      A NodeSplitter that is compatible with SkyBVTree for SkyMinMaxBox.
 179 //      Implemented using the SkyBoundingBoxSplitter strategy.
 180 //----------------------------------------------------------------------------
 181 template<class Object>
 182 class SkyAABBTreeSplitter
 183 {
 184 public:
 185         typedef SkyMinMaxBox BV;
 186         typedef SkyBaseBVTree<Object, BV>::NodeObject NodeObject;
 187
 188         SkyAABBTreeSplitter(const NodeObject* pObjs, unsigned int iNumObjs) : _splitter(pObjs, iNumObjs) {}
 189
 190         const BV& GetNodeBV() const                             { return _splitter.GetNodeBBox(); }
 191
 192         bool operator()(const NodeObject& obj) const
 193         {
 194                 return _splitter.SplitLeft(obj);
 195         }
 196
 197         bool operator()(const NodeObject& obj1, const NodeObject& obj2) const
 198         {
 199                 return _splitter.LessThan(obj1, obj2);
 200         }
 201
 202 private:
 203         SkyBoundingBoxSplitter<Object> _splitter;
 204 };
 205
 206 //----------------------------------------------------------------------------
 207 //      SkySphereTreeSplitter
 208 //----------------------------------------------------------------------------
 209 //      A NodeSplitter that is compatible with SkyBVTree for SkyBoundingSphere.
 210 //      Implemented using the SkyBoundingBoxSplitter strategy.
 211 //----------------------------------------------------------------------------
 212 /*template<class Object>
 213 class SkySphereTreeSplitter
 214 {
 215 public:
 216         typedef SkyBoundingSphere BV;
 217         typedef SkyBaseBVTree<Object, BV>::NodeObject NodeObject;
 218
 219         MlxSphereTreeSplitter(const NodeObject* pObjs, unsigned int iNumObjs) : _splitter(pObjs, iNumObjs)
 220         {
 221                 _nodeBV = pObjs[0].GetBV();
 222                 for (unsigned int i = 1; i < iNumObjs; ++i) _nodeBV.Union(pObjs[i].GetBV());
 223         }
 224
 225         const BV& GetNodeBV() const                             { return _nodeBV; }
 226
 227         bool operator()(const NodeObject& obj) const
 228         {
 229                 return _splitter.SplitLeft(obj);
 230         }
 231
 232         bool operator()(const NodeObject& obj1, const NodeObject& obj2) const
 233         {
 234                 return _splitter.LessThan(obj1, obj2);
 235         }
 236
 237 private:
 238         BV _nodeBV;
 239         SkyBoundingBoxSplitter<Object> _splitter;
 240 };*/
 241
 242 #endif //__SKYBVTREESPLITTER_HPP__