1 /* 2 Copyright (c) 2006, Michael Kazhdan and Matthew Bolitho 3 All rights reserved. 4 5 Redistribution and use in source and binary forms, with or without modification, 6 are permitted provided that the following conditions are met: 7 8 Redistributions of source code must retain the above copyright notice, this list of 9 conditions and the following disclaimer. Redistributions in binary form must reproduce 10 the above copyright notice, this list of conditions and the following disclaimer 11 in the documentation and/or other materials provided with the distribution. 12 13 Neither the name of the Johns Hopkins University nor the names of its contributors 14 may be used to endorse or promote products derived from this software without specific 15 prior written permission. 16 17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY 18 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO THE IMPLIED WARRANTIES 19 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT 20 SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 21 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 22 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 23 BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 25 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 26 DAMAGE. 27 */ 28 29 #ifndef OCT_NODE_INCLUDED 30 #define OCT_NODE_INCLUDED 31 32 #include "Allocator.h" 33 #include "BinaryNode.h" 34 #include "MarchingCubes.h" 35 36 #define NEW_OCTNODE_CODE 1 37 38 #define DIMENSION 3 39 40 template< class NodeData > 41 class OctNode 42 { 43 private: 44 static int UseAlloc; 45 unsigned long long _depthAndOffset; 46 47 const OctNode* __faceNeighbor( int dir , int off ) const; 48 const OctNode* __edgeNeighbor( int o , const int i[2] , const int idx[2] ) const; 49 OctNode* __faceNeighbor( int dir , int off , int forceChildren ); 50 OctNode* __edgeNeighbor( int o , const int i[2] , const int idx[2] , int forceChildren); 51 public: 52 static const int DepthShift , OffsetShift , OffsetShift1 , OffsetShift2 , OffsetShift3; 53 static const int DepthMask , OffsetMask; 54 55 static Allocator< OctNode > NodeAllocator; 56 static int UseAllocator( void ); 57 static void SetAllocator( int blockSize ); 58 59 OctNode* parent; 60 OctNode* children; 61 NodeData nodeData; 62 63 OctNode( void ); 64 ~OctNode( void ); 65 int initChildren( void ); 66 67 void depthAndOffset( int& depth , int offset[DIMENSION] ) const; 68 void centerIndex( int index[DIMENSION] ) const; 69 int depth( void ) const; 70 static inline void DepthAndOffset( const long long& index , int& depth , int offset[DIMENSION] ); 71 template< class Real > static inline void CenterAndWidth( const long long& index , Point3D< Real >& center , Real& width ); 72 template< class Real > static inline void StartAndWidth( const long long& index , Point3D< Real >& start , Real& width ); 73 static inline int Depth( const long long& index ); 74 static inline void Index( int depth , const int offset[3] , short& d , short off[DIMENSION] ); 75 static inline unsigned long long Index( int depth , const int offset[3] ); 76 template< class Real > void centerAndWidth( Point3D<Real>& center , Real& width ) const; 77 template< class Real > void startAndWidth( Point3D< Real >& start , Real& width ) const; 78 template< class Real > bool isInside( Point3D< Real > p ) const; 79 80 size_t leaves( void ) const; 81 size_t maxDepthLeaves( int maxDepth ) const; 82 size_t nodes( void ) const; 83 int maxDepth( void ) const; 84 85 const OctNode* root( void ) const; 86 87 const OctNode* nextLeaf( const OctNode* currentLeaf=NULL ) const; 88 OctNode* nextLeaf( OctNode* currentLeaf=NULL ); 89 const OctNode* nextNode( const OctNode* currentNode=NULL ) const; 90 OctNode* nextNode( OctNode* currentNode=NULL ); 91 const OctNode* nextBranch( const OctNode* current ) const; 92 OctNode* nextBranch( OctNode* current ); 93 const OctNode* prevBranch( const OctNode* current ) const; 94 OctNode* prevBranch( OctNode* current ); 95 96 void setFullDepth( int maxDepth ); 97 98 void printLeaves( void ) const; 99 void printRange( void ) const; 100 101 template< class Real > static int CornerIndex( const Point3D<Real>& center , const Point3D<Real> &p ); 102 103 OctNode* faceNeighbor( int faceIndex , int forceChildren=0 ); 104 const OctNode* faceNeighbor( int faceIndex ) const; 105 OctNode* edgeNeighbor( int edgeIndex , int forceChildren=0 ); 106 const OctNode* edgeNeighbor( int edgeIndex ) const; 107 OctNode* cornerNeighbor( int cornerIndex , int forceChildren=0 ); 108 const OctNode* cornerNeighbor( int cornerIndex ) const; 109 110 int write( const char* fileName ) const; 111 int write( FILE* fp ) const; 112 int read( const char* fileName ); 113 int read( FILE* fp ); 114 115 template< unsigned int Width > 116 struct Neighbors 117 { 118 OctNode* neighbors[Width][Width][Width]; 119 Neighbors( void ); 120 void clear( void ); 121 }; 122 template< unsigned int Width > 123 struct ConstNeighbors 124 { 125 const OctNode* neighbors[Width][Width][Width]; 126 ConstNeighbors( void ); 127 void clear( void ); 128 }; 129 130 template< unsigned int LeftRadius , unsigned int RightRadius > 131 class NeighborKey 132 { 133 int _depth; 134 public: 135 static const int Width = LeftRadius + RightRadius + 1; 136 Neighbors< Width >* neighbors; 137 138 NeighborKey( void ); 139 NeighborKey( const NeighborKey& key ); 140 ~NeighborKey( void ); depth(void)141 int depth( void ) const { return _depth; } 142 143 void set( int depth ); 144 template< bool CreateNodes > typename OctNode< NodeData >::template Neighbors< LeftRadius+RightRadius+1 >& getNeighbors( OctNode* node ); 145 template< bool CreateNodes , unsigned int _LeftRadius , unsigned int _RightRadius > void getNeighbors( OctNode* node , Neighbors< _LeftRadius + _RightRadius + 1 >& neighbors ); 146 template< bool CreateNodes > bool getChildNeighbors( int cIdx , int d , Neighbors< Width >& childNeighbors ) const; 147 template< bool CreateNodes , class Real > bool getChildNeighbors( Point3D< Real > p , int d , Neighbors< Width >& childNeighbors ) const; 148 }; 149 150 template< unsigned int LeftRadius , unsigned int RightRadius > 151 class ConstNeighborKey 152 { 153 int _depth; 154 public: 155 static const int Width = LeftRadius + RightRadius + 1; 156 ConstNeighbors<Width>* neighbors; 157 158 ConstNeighborKey( void ); 159 ConstNeighborKey( const ConstNeighborKey& key ); 160 ~ConstNeighborKey( void ); depth(void)161 int depth( void ) const { return _depth; } 162 163 void set( int depth ); 164 typename OctNode< NodeData >::template ConstNeighbors< LeftRadius+RightRadius+1 >& getNeighbors( const OctNode* node ); 165 template< unsigned int _LeftRadius , unsigned int _RightRadius > void getNeighbors( const OctNode* node , ConstNeighbors< _LeftRadius + _RightRadius + 1 >& neighbors ); 166 }; 167 168 void centerIndex( int maxDepth , int index[DIMENSION] ) const; 169 int width( int maxDepth ) const; 170 }; 171 172 173 #include "Octree.inl" 174 175 #endif // OCT_NODE_INCLUDED 176