[2582] | 1 | // ===================================================================
|
---|
| 2 | // $Id: $
|
---|
| 3 | //
|
---|
| 4 | // ktb.h
|
---|
| 5 | // definition of classes for CKTB tree building up and traversal
|
---|
| 6 | //
|
---|
| 7 | // Class: CKTBNodeAbstract, SKTBNode, CKTBAllocMan, CKTBNodeIterator
|
---|
| 8 | //
|
---|
| 9 | // REPLACEMENT_STRING
|
---|
| 10 | //
|
---|
| 11 | // Copyright by Vlastimil Havran, 2007 - email to "vhavran AT seznam.cz"
|
---|
| 12 | // Initial coding by Vlasta Havran, February 2007
|
---|
| 13 |
|
---|
| 14 | #ifndef __KTB_H__
|
---|
| 15 | #define __KTB_H__
|
---|
| 16 |
|
---|
| 17 | // GOLEM headers
|
---|
| 18 | #include "configh.h"
|
---|
| 19 | #include "AxisAlignedBox3.h"
|
---|
| 20 | #include "Intersectable.h"
|
---|
| 21 | #include "Containers.h"
|
---|
| 22 | #include "allocgo2.h"
|
---|
| 23 | #include "ktbconf.h"
|
---|
| 24 | #include "sbbox.h"
|
---|
| 25 | #include "Vector3.h"
|
---|
| 26 |
|
---|
| 27 | // standard headers
|
---|
| 28 | #include <vector>
|
---|
| 29 |
|
---|
| 30 | namespace GtpVisibilityPreprocessor {
|
---|
| 31 |
|
---|
| 32 | // Forward declarations
|
---|
| 33 | class CRayPacket2x2;
|
---|
| 34 |
|
---|
| 35 | // 12 Bytes representation of the node
|
---|
| 36 | // This is only due to writing simplification
|
---|
| 37 | #undef SKTBNodeT
|
---|
| 38 | #define SKTBNodeT CKTBNodeAbstract::SKTBNode
|
---|
| 39 |
|
---|
| 40 | //===============================================
|
---|
| 41 | // Representation of one node of CKTB
|
---|
| 42 | class CKTBNodeAbstract
|
---|
| 43 | {
|
---|
| 44 | public:
|
---|
| 45 | // maximal height of the CKTB tree
|
---|
| 46 | enum { MAX_HEIGHT = 32 };
|
---|
| 47 |
|
---|
| 48 | // the basic element of CKTB tree .. node of tree
|
---|
| 49 | // it must be accessible by more classes
|
---|
| 50 |
|
---|
| 51 | // but must be declared because of compilation
|
---|
| 52 | struct SKTBNode {
|
---|
| 53 | // the axis, where cut is performed or type of node in general
|
---|
| 54 | CKTBAxes::Axes nodeType;
|
---|
| 55 |
|
---|
| 56 | union {
|
---|
| 57 | float splitPlane; // the position of splitting plane
|
---|
| 58 | ObjectContainer *objlist; // object list for a leaf or tagged interior node
|
---|
| 59 | SKTBNodeT *parentBoxNode; // the pointer to the same node type
|
---|
| 60 | int depth; // the depth of the node (useful only for minBoxes)
|
---|
| 61 | };
|
---|
| 62 |
|
---|
| 63 | // SKTBNode *left; // pointer to the left child is implict in DFS order
|
---|
| 64 | union {
|
---|
| 65 | Intersectable *object; // the pointer to the object, if only one object
|
---|
| 66 | SKTBNodeT *right; // pointer to the right child
|
---|
| 67 | SBBox *encbox; // enclosing bounding box for this node
|
---|
| 68 | SBBox *minbox; // minimum bounding box for this node
|
---|
| 69 | };
|
---|
| 70 |
|
---|
| 71 | bool IsLeaf() const {
|
---|
| 72 | return ( nodeType == CKTBAxes::EE_Leaf);
|
---|
| 73 | }
|
---|
| 74 | bool IsEmptyLeaf() const {
|
---|
| 75 | return (this == 0);
|
---|
| 76 | }
|
---|
| 77 | }; // struct SKTBNode
|
---|
| 78 |
|
---|
| 79 | public:
|
---|
| 80 |
|
---|
| 81 | // It was _KTB_R2
|
---|
| 82 | // default constructor
|
---|
| 83 | CKTBNodeAbstract() { }
|
---|
| 84 | // default destructor
|
---|
| 85 | virtual ~CKTBNodeAbstract() { }
|
---|
| 86 |
|
---|
| 87 | bool IsEmptyLeaf_(const SKTBNode *p) const {
|
---|
| 88 | assert(p->nodeType == CKTBAxes::EE_Leaf);
|
---|
| 89 | return (p->objlist == NULL);
|
---|
| 90 | }
|
---|
| 91 |
|
---|
| 92 | bool IsFullLeaf_(const SKTBNode *p) const {
|
---|
| 93 | return ((p->nodeType == CKTBAxes::EE_Leaf) &&
|
---|
| 94 | (p->objlist != NULL));
|
---|
| 95 | }
|
---|
| 96 |
|
---|
| 97 | bool IsLeaf_(const SKTBNode *p) const
|
---|
| 98 | { return (p->nodeType == CKTBAxes::EE_Leaf); }
|
---|
| 99 |
|
---|
| 100 | bool HasMinBox_(const SKTBNode *p) const
|
---|
| 101 | { return ( p->nodeType >= CKTBAxes::EE_X_axisBox); }
|
---|
| 102 |
|
---|
| 103 | // ------------------------------------------------------
|
---|
| 104 | // Common functions for iterator and allocator
|
---|
| 105 |
|
---|
| 106 | CKTBAxes::Axes GetNodeType(const SKTBNode *nodep) const {
|
---|
| 107 | return nodep->nodeType;
|
---|
| 108 | }
|
---|
| 109 | SKTBNode* GetLeft(const SKTBNode *nodep) const {
|
---|
| 110 | return (SKTBNode*)(nodep+1); // We assume linking in DFS order
|
---|
| 111 | }
|
---|
| 112 | // We assume linking in DFS order, this is for EncBox
|
---|
| 113 | SKTBNode* GetLeftLong(const SKTBNode *nodep) const {
|
---|
| 114 | return (SKTBNode*)(((char*)nodep) + 3*sizeof(SKTBNode));
|
---|
| 115 | }
|
---|
| 116 | SKTBNode* GetRight(const SKTBNode *nodep) const {
|
---|
| 117 | return nodep->right;
|
---|
| 118 | }
|
---|
| 119 | SKTBNodeT* GetLinkNode(const SKTBNodeT *nodep) const {
|
---|
| 120 | return nodep->right;
|
---|
| 121 | }
|
---|
| 122 | ObjectContainer* GetObjList(const SKTBNode *nodep) const {
|
---|
| 123 | return nodep->objlist;
|
---|
| 124 | }
|
---|
| 125 |
|
---|
| 126 | SKTBNode* GetParentBoxNode(const SKTBNode *nodep) const {
|
---|
| 127 | return (SKTBNode*)(nodep+1)->parentBoxNode;
|
---|
| 128 | }
|
---|
| 129 |
|
---|
| 130 | // This can be used only for nodes X_AxisBox, Y_AxisBox, Z_AxisBox
|
---|
| 131 | int GetDepth(const SKTBNode *nodep) const {
|
---|
| 132 | return (int)((nodep+1)->nodeType);
|
---|
| 133 | }
|
---|
| 134 | #ifdef _SHORT_FORM_MINBOX
|
---|
| 135 | SKTBNode* GetLeftMinBox(const SKTBNode *nodep) const {
|
---|
| 136 | return (SKTBNode*)(nodep+2);
|
---|
| 137 | }
|
---|
| 138 | #else
|
---|
| 139 | SKTBNode* GetLeftMinBox(const SKTBNode *nodep) const {
|
---|
| 140 | return (SKTBNode*)(((char*)nodep) + 4*sizeof(SKTBNode));
|
---|
| 141 | }
|
---|
| 142 | #endif // _SHORT_FORM_MINBOX
|
---|
| 143 |
|
---|
| 144 | }; // CKTBNodeAbstract
|
---|
| 145 |
|
---|
| 146 | //----------------------------------------------------------------
|
---|
| 147 | // this class should be used as the base class for allocating
|
---|
| 148 | // and connecting the nodes in the CKTB tree and for
|
---|
| 149 | // for manipulating the nodes during building up
|
---|
| 150 | class CKTBAllocMan:
|
---|
| 151 | public CKTBNodeAbstract
|
---|
| 152 | {
|
---|
| 153 | protected:
|
---|
| 154 | #ifdef LEAVES_ARRAYS
|
---|
| 155 | CObjectArray arrayAlloc;
|
---|
| 156 | #endif
|
---|
| 157 |
|
---|
| 158 | // the direction of traversal through CKTB tree
|
---|
| 159 | enum EDirection { LEFT = 0, RIGHT = 1, NOWHERE = 2 };
|
---|
| 160 |
|
---|
| 161 | //#ifdef _KTB_R2
|
---|
| 162 | SKTBNode* _AllocEmptyLeaf() {
|
---|
| 163 | #ifdef _KTB_CONSTR_STATS
|
---|
| 164 | _stats_emptyLeftNodeCount++;
|
---|
| 165 | #endif
|
---|
| 166 | return (SKTBNode*)0;
|
---|
| 167 | }
|
---|
| 168 | protected:
|
---|
| 169 | // data required as the input parameter for construction of CKTB tree
|
---|
| 170 | int maxDepthAllowed; // maximal depth of CKTB tree
|
---|
| 171 | int maxListLength; // maximal list length of CKTB tree
|
---|
| 172 | public:
|
---|
| 173 | // default constructor
|
---|
| 174 | CKTBAllocMan() { InitForConstructor(); }
|
---|
| 175 |
|
---|
| 176 | // default destructor
|
---|
| 177 | virtual ~CKTBAllocMan() { }
|
---|
| 178 |
|
---|
[2592] | 179 | // init the stack of auxiliary variables from min to max
|
---|
| 180 | virtual void InitAux(int min, int max, int maxItemsAtOnce);
|
---|
| 181 |
|
---|
[2582] | 182 | // forget the content that is created by previous kd-tree construction
|
---|
| 183 | // or just init for the first use.
|
---|
| 184 | void InitForConstructor();
|
---|
| 185 |
|
---|
| 186 | // the function, which reads the parameters from envinroment/commandline
|
---|
| 187 | virtual void InitPars();
|
---|
| 188 |
|
---|
| 189 | // -------------------------------------------------------
|
---|
| 190 | // allocate and free functions for SKTBNode
|
---|
| 191 | CAllocContinuous *alloc2; // the allocator saving space
|
---|
| 192 | SKTBNodeT *root; // this is the root node of the whole tree
|
---|
| 193 |
|
---|
| 194 | // This is the node to return from the allocation functions
|
---|
| 195 | // Here it can be implemented some linking when DFS order allocation,
|
---|
| 196 | // so the node can be different than the representation of the real
|
---|
| 197 | // node with the information
|
---|
| 198 | SKTBNodeT *nodeToLink;
|
---|
| 199 |
|
---|
| 200 | // Create the representation of the interior node
|
---|
| 201 | SKTBNodeT* AllocInteriorNode(int axis, float position,
|
---|
| 202 | int cntLeft, int cntRight);
|
---|
| 203 |
|
---|
| 204 | // Create the representation of the interior node with box, where box
|
---|
| 205 | // can be used during the traversal
|
---|
| 206 | SKTBNodeT* AllocInteriorNodeWithBox(int axis, float position,
|
---|
| 207 | int cntLeft, int cntRight,
|
---|
| 208 | const SBBox &tsbox,
|
---|
| 209 | SKTBNodeT* prevMinBoxNode,
|
---|
| 210 | int depthStore);
|
---|
| 211 |
|
---|
| 212 | // Create the representation of the node with the bounding box
|
---|
| 213 | SKTBNodeT* AllocEncBoxNode(const SBBox &sbox);
|
---|
| 214 |
|
---|
| 215 | // Create the representation of the leaf. Note that possibly there
|
---|
| 216 | // can be special cases, such as 0, 1, 2, or 3 objects, or in general
|
---|
| 217 | // N objects.
|
---|
| 218 | SKTBNodeT* AllocLeaf(int cntObjects);
|
---|
| 219 |
|
---|
| 220 | // -------------------------------------------------------
|
---|
| 221 | // linking and setting functions for CKTB tree
|
---|
| 222 |
|
---|
| 223 | // Set the pointers to children for the interior node
|
---|
| 224 | void SetInteriorNodeLinks(SKTBNodeT *node,
|
---|
| 225 | SKTBNodeT *leftChild,
|
---|
| 226 | SKTBNodeT *rightChild);
|
---|
[2592] | 227 | void SetInteriorNodeLeft(SKTBNodeT *node,
|
---|
| 228 | SKTBNodeT *leftChild);
|
---|
| 229 | void SetInteriorNodeRight(SKTBNodeT *node,
|
---|
| 230 | SKTBNodeT *rightChild);
|
---|
[2582] | 231 |
|
---|
| 232 | // Set the objects list to the leaf. The object list is used as it is
|
---|
| 233 | // ... it is not copied !!
|
---|
| 234 | virtual int SetFullLeaf(SKTBNodeT *node, const ObjectContainer *objlist);
|
---|
| 235 |
|
---|
| 236 | // -------------------------------------------------------
|
---|
| 237 | // inquiry functions for CKTB tree nodes for current node
|
---|
| 238 |
|
---|
| 239 | // returns the pointer to the root node of tree
|
---|
| 240 | virtual SKTBNode *GetRootNode() { return root;}
|
---|
| 241 |
|
---|
| 242 | // postprocessing of CKTB tree after its initial construction
|
---|
| 243 | virtual void PostBuild();
|
---|
| 244 |
|
---|
| 245 | // provides the information on the method used for CKTB tree
|
---|
| 246 | // and some setting parameters to given stream
|
---|
| 247 | virtual void ProvideID(ostream &app) = 0;
|
---|
| 248 |
|
---|
| 249 | // ---- Get Statistical Data ---------------------------------
|
---|
| 250 | void GetKTBTreeStats(int &nodes, int &leaves, int &emptyLeaves)
|
---|
| 251 | {
|
---|
| 252 | #ifdef _KTB_CONSTR_STATS
|
---|
| 253 | nodes = _stats_interiorCount + _stats_bboxCount + _stats_minbboxCount
|
---|
| 254 | + _stats_leafNodeCount + _stats_emptyLeftNodeCount;
|
---|
| 255 | leaves = _stats_leafNodeCount + _stats_emptyLeftNodeCount;
|
---|
| 256 | emptyLeaves = _stats_emptyLeftNodeCount;
|
---|
| 257 | #endif
|
---|
| 258 | }
|
---|
| 259 |
|
---|
| 260 | // constructs the CKTB tree for given objectlist and given bounding box
|
---|
| 261 | virtual SKTBNodeT* BuildUp(ObjectContainer &objlist,
|
---|
| 262 | const AxisAlignedBox3 &box,
|
---|
| 263 | bool verbose = true) = 0;
|
---|
| 264 |
|
---|
| 265 | // deletes all the structure starting from the root node
|
---|
| 266 | virtual void Remove();
|
---|
| 267 |
|
---|
| 268 | // The current depth in the tree
|
---|
| 269 | inline int GetDepth() const {return _currDepth;}
|
---|
| 270 | void IncDepth() {_currDepth++;}
|
---|
| 271 | void DecDepth() {_currDepth--;}
|
---|
| 272 |
|
---|
| 273 | // --------------------------------------------------------------
|
---|
| 274 | // Statistics
|
---|
| 275 | public:
|
---|
| 276 | #ifdef _KTB_CONSTR_STATS
|
---|
| 277 | int _stats_interiorCount;
|
---|
| 278 | int _stats_bboxCount;
|
---|
| 279 | int _stats_minbboxCount;
|
---|
| 280 | int _stats_leafNodeCount;
|
---|
| 281 | int _stats_emptyLeftNodeCount;
|
---|
| 282 |
|
---|
| 283 | // maximal depth of the currently built path during building up
|
---|
| 284 | int _maxDepth;
|
---|
| 285 | // Sum of depths of leaf nodes (empty + full)
|
---|
| 286 | unsigned long int _sumLeafDepth;
|
---|
| 287 | // Sum of depths of empty leaves
|
---|
| 288 | unsigned long int _sumFullLeafDepth;
|
---|
| 289 | // The count of object references in leaves
|
---|
| 290 | unsigned long int _sumObjectRefCount;
|
---|
| 291 | // The maximum number of object references in a leaf
|
---|
| 292 | unsigned long int _maxObjectRefInLeaf;
|
---|
| 293 | // Surface area of leaves and interior nodes
|
---|
| 294 | float _sumSurfaceAreaLeaves;
|
---|
| 295 | float _sumSurfaceAreaMULcntLeaves;
|
---|
| 296 | float _sumSurfaceAreaInteriorNodes;
|
---|
| 297 | #endif // _KTB_CONSTR_STATS
|
---|
| 298 |
|
---|
| 299 | // General statistics on the depth of current node
|
---|
| 300 | // the depth of the currently accessed node during building up
|
---|
| 301 | int _currDepth;
|
---|
| 302 | };
|
---|
| 303 |
|
---|
| 304 | //------------------------------------------------------
|
---|
| 305 | // class which enables to use some functions with direct
|
---|
| 306 | // access to the members of the tree
|
---|
| 307 | // traversal classes should be derived from this class
|
---|
| 308 | class CKTBNodeIterator:
|
---|
| 309 | public CKTBNodeAbstract
|
---|
| 310 | {
|
---|
| 311 | protected:
|
---|
| 312 | int rayOffset;
|
---|
| 313 | public:
|
---|
| 314 | // default constructor
|
---|
| 315 | CKTBNodeIterator() { }
|
---|
| 316 | // default destructor
|
---|
| 317 | ~CKTBNodeIterator() { }
|
---|
| 318 |
|
---|
| 319 | ObjectContainer* GetObjList(const SKTBNode *nodep) const {
|
---|
| 320 | return nodep->objlist;
|
---|
| 321 | }
|
---|
| 322 |
|
---|
| 323 | float GetSplitValue(const SKTBNode *nodep) const {
|
---|
| 324 | return nodep->splitPlane;
|
---|
| 325 | }
|
---|
| 326 |
|
---|
| 327 | #ifdef _SHORT_FORM_MINBOX
|
---|
| 328 | SBBox* GetMinBox(const SKTBNodeT *nodep) const {
|
---|
| 329 | return (nodep+1)->minbox;
|
---|
| 330 | }
|
---|
| 331 | #else // _SHORT_FORM_MINBOX
|
---|
| 332 | SBBox* GetMinBox(const SKTBNodeT *nodep) const {
|
---|
| 333 | // Here is the overlapping to save some memory !!!
|
---|
| 334 | return (SBBox*)(((char*)nodep)+24);
|
---|
| 335 | }
|
---|
| 336 | #endif // _SHORT_FORM_MINBOX
|
---|
| 337 |
|
---|
| 338 | ObjectContainer* GetTagObjList(const SKTBNode *node) const {
|
---|
| 339 | return node->objlist;
|
---|
| 340 | }
|
---|
| 341 |
|
---|
| 342 | // test the objects in the full leaf p and if finds the closest intersection
|
---|
| 343 | // with object so tmin<= t <= tmax, returns the pointer to that
|
---|
| 344 | // object, t is returned in tmax
|
---|
| 345 | int TestFullLeaf(const SimpleRay &ray, const SKTBNode *p);
|
---|
| 346 | int TestFullLeaf(const SimpleRay &ray, const SKTBNode *p, int rayIndex);
|
---|
| 347 |
|
---|
| 348 | // test the objects in the full leaf and finds out any intersection
|
---|
| 349 | // in this case returns the pointer to the object, otherwise NULL
|
---|
| 350 | int HitAnyObj(const SimpleRay &ray, const SKTBNode *p);
|
---|
| 351 |
|
---|
| 352 | // ------------------------------------------------------------------------
|
---|
| 353 | // Only abstract functions to simplify the interface
|
---|
| 354 |
|
---|
| 355 | // this resets the nesting to start from the zero depth (root)
|
---|
| 356 | virtual void ResetTraversalDepth() = 0;
|
---|
| 357 |
|
---|
| 358 | // sets the bbox and the root node for this traversal class
|
---|
| 359 | virtual void Setup(const AxisAlignedBox3 &box, SKTBNodeT *Nroot) = 0;
|
---|
| 360 |
|
---|
| 361 | // Find the minimum box on containg a point or leaf, if there are
|
---|
| 362 | // no boxes on the way from a point to the leaf containing the point
|
---|
| 363 | virtual const SKTBNode* Locate(const Vector3 &point);
|
---|
| 364 | }; // class CKTBNodeIterator
|
---|
| 365 |
|
---|
| 366 | }
|
---|
| 367 |
|
---|
| 368 | #endif // __KTB_H__
|
---|