Point Cloud Library (PCL)  1.14.1-dev
octree_poisson.h
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 #if defined __GNUC__
33 # pragma GCC system_header
34 #endif
35 
36 #include "allocator.h"
37 #include "binary_node.h"
38 #include "marching_cubes_poisson.h"
39 
40 #define DIMENSION 3
41 
42 namespace pcl
43 {
44  namespace poisson
45  {
46 
47  template< class NodeData , class Real=float >
48  class OctNode
49  {
50  private:
51  static int UseAlloc;
52 
53  class AdjacencyCountFunction
54  {
55  public:
56  int count;
57  void Function( const OctNode<NodeData,Real>* node1 , const OctNode<NodeData,Real>* node2 );
58  };
59  template<class NodeAdjacencyFunction>
60  void __processNodeFaces(OctNode* node,NodeAdjacencyFunction* F,int cIndex1,int cIndex2,int cIndex3,int cIndex4);
61  template<class NodeAdjacencyFunction>
62  void __processNodeEdges(OctNode* node,NodeAdjacencyFunction* F,int cIndex1,int cIndex2);
63  template<class NodeAdjacencyFunction>
64  void __processNodeNodes(OctNode* node,NodeAdjacencyFunction* F);
65  template<class NodeAdjacencyFunction>
66  static void __ProcessNodeAdjacentNodes(int dx,int dy,int dz,OctNode* node1,int radius1,OctNode* node2,int radius2,int cWidth2,NodeAdjacencyFunction* F);
67  template<class TerminatingNodeAdjacencyFunction>
68  static void __ProcessTerminatingNodeAdjacentNodes(int dx,int dy,int dz,OctNode* node1,int radius1,OctNode* node2,int radius2,int cWidth2,TerminatingNodeAdjacencyFunction* F);
69  template<class PointAdjacencyFunction>
70  static void __ProcessPointAdjacentNodes(int dx,int dy,int dz,OctNode* node2,int radius2,int cWidth2,PointAdjacencyFunction* F);
71  template<class NodeAdjacencyFunction>
72  static void __ProcessFixedDepthNodeAdjacentNodes(int dx,int dy,int dz,OctNode* node1,int radius1,OctNode* node2,int radius2,int cWidth2,int depth,NodeAdjacencyFunction* F);
73  template<class NodeAdjacencyFunction>
74  static void __ProcessMaxDepthNodeAdjacentNodes(int dx,int dy,int dz,OctNode* node1,int radius1,OctNode* node2,int radius2,int cWidth2,int depth,NodeAdjacencyFunction* F);
75 
76  // This is made private because the division by two has been pulled out.
77  static inline int Overlap(int c1,int c2,int c3,int dWidth);
78  inline static int ChildOverlap(int dx,int dy,int dz,int d,int cRadius2);
79 
80  const OctNode* __faceNeighbor(int dir,int off) const;
81  const OctNode* __edgeNeighbor(int o,const int i[2],const int idx[2]) const;
82  OctNode* __faceNeighbor(int dir,int off,int forceChildren);
83  OctNode* __edgeNeighbor(int o,const int i[2],const int idx[2],int forceChildren);
84  public:
86  static const int DepthMask,OffsetMask;
87 
89  static int UseAllocator(void);
90  static void SetAllocator(int blockSize);
91 
94  short d , off[DIMENSION];
95  NodeData nodeData;
96 
97  OctNode(void);
98  ~OctNode(void);
99  int initChildren(void);
100 
101  void depthAndOffset(int& depth,int offset[DIMENSION]) const;
102  int depth(void) const;
103  static inline void DepthAndOffset(const long long& index,int& depth,int offset[DIMENSION]);
104  static inline void CenterAndWidth(const long long& index,Point3D<Real>& center,Real& width);
105  static inline int Depth(const long long& index);
106  static inline void Index(int depth,const int offset[3],short& d,short off[DIMENSION]);
107  void centerAndWidth( Point3D<Real>& center , Real& width ) const;
108  bool isInside( Point3D< Real > p ) const;
109 
110  int leaves(void) const;
111  int maxDepthLeaves(int maxDepth) const;
112  int nodes(void) const;
113  int maxDepth(void) const;
114 
115  const OctNode* root(void) const;
116 
117  const OctNode* nextLeaf(const OctNode* currentLeaf=NULL) const;
118  OctNode* nextLeaf(OctNode* currentLeaf=NULL);
119  const OctNode* nextNode(const OctNode* currentNode=NULL) const;
120  OctNode* nextNode(OctNode* currentNode=NULL);
121  const OctNode* nextBranch(const OctNode* current) const;
122  OctNode* nextBranch(OctNode* current);
123  const OctNode* prevBranch(const OctNode* current) const;
124  OctNode* prevBranch(OctNode* current);
125 
126  void setFullDepth(int maxDepth);
127 
128  void printLeaves(void) const;
129  void printRange(void) const;
130 
131  template<class NodeAdjacencyFunction>
132  void processNodeFaces(OctNode* node,NodeAdjacencyFunction* F,int fIndex,int processCurrent=1);
133  template<class NodeAdjacencyFunction>
134  void processNodeEdges(OctNode* node,NodeAdjacencyFunction* F,int eIndex,int processCurrent=1);
135  template<class NodeAdjacencyFunction>
136  void processNodeCorners(OctNode* node,NodeAdjacencyFunction* F,int cIndex,int processCurrent=1);
137  template<class NodeAdjacencyFunction>
138  void processNodeNodes(OctNode* node,NodeAdjacencyFunction* F,int processCurrent=1);
139 
140  template<class NodeAdjacencyFunction>
141  static void ProcessNodeAdjacentNodes(int maxDepth,OctNode* node1,int width1,OctNode* node2,int width2,NodeAdjacencyFunction* F,int processCurrent=1);
142  template<class NodeAdjacencyFunction>
143  static void ProcessNodeAdjacentNodes(int dx,int dy,int dz,OctNode* node1,int radius1,OctNode* node2,int radius2,int width2,NodeAdjacencyFunction* F,int processCurrent=1);
144  template<class TerminatingNodeAdjacencyFunction>
145  static void ProcessTerminatingNodeAdjacentNodes(int maxDepth,OctNode* node1,int width1,OctNode* node2,int width2,TerminatingNodeAdjacencyFunction* F,int processCurrent=1);
146  template<class TerminatingNodeAdjacencyFunction>
147  static void ProcessTerminatingNodeAdjacentNodes(int dx,int dy,int dz,OctNode* node1,int radius1,OctNode* node2,int radius2,int width2,TerminatingNodeAdjacencyFunction* F,int processCurrent=1);
148  template<class PointAdjacencyFunction>
149  static void ProcessPointAdjacentNodes(int maxDepth,const int center1[3],OctNode* node2,int width2,PointAdjacencyFunction* F,int processCurrent=1);
150  template<class PointAdjacencyFunction>
151  static void ProcessPointAdjacentNodes(int dx,int dy,int dz,OctNode* node2,int radius2,int width2,PointAdjacencyFunction* F,int processCurrent=1);
152  template<class NodeAdjacencyFunction>
153  static void ProcessFixedDepthNodeAdjacentNodes(int maxDepth,OctNode* node1,int width1,OctNode* node2,int width2,int depth,NodeAdjacencyFunction* F,int processCurrent=1);
154  template<class NodeAdjacencyFunction>
155  static void ProcessFixedDepthNodeAdjacentNodes(int dx,int dy,int dz,OctNode* node1,int radius1,OctNode* node2,int radius2,int width2,int depth,NodeAdjacencyFunction* F,int processCurrent=1);
156  template<class NodeAdjacencyFunction>
157  static void ProcessMaxDepthNodeAdjacentNodes(int maxDepth,OctNode* node1,int width1,OctNode* node2,int width2,int depth,NodeAdjacencyFunction* F,int processCurrent=1);
158  template<class NodeAdjacencyFunction>
159  static void ProcessMaxDepthNodeAdjacentNodes(int dx,int dy,int dz,OctNode* node1,int radius1,OctNode* node2,int radius2,int width2,int depth,NodeAdjacencyFunction* F,int processCurrent=1);
160 
161  static int CornerIndex(const Point3D<Real>& center,const Point3D<Real> &p);
162 
163  OctNode* faceNeighbor(int faceIndex,int forceChildren=0);
164  const OctNode* faceNeighbor(int faceIndex) const;
165  OctNode* edgeNeighbor(int edgeIndex,int forceChildren=0);
166  const OctNode* edgeNeighbor(int edgeIndex) const;
167  OctNode* cornerNeighbor(int cornerIndex,int forceChildren=0);
168  const OctNode* cornerNeighbor(int cornerIndex) const;
169 
171  const OctNode* getNearestLeaf(const Point3D<Real>& p) const;
172 
173  static int CommonEdge(const OctNode* node1,int eIndex1,const OctNode* node2,int eIndex2);
174  static int CompareForwardDepths(const void* v1,const void* v2);
175  static int CompareByDepthAndXYZ( const void* v1 , const void* v2 );
176  static int CompareByDepthAndZIndex( const void* v1 , const void* v2 );
177  static int CompareForwardPointerDepths(const void* v1,const void* v2);
178  static int CompareBackwardDepths(const void* v1,const void* v2);
179  static int CompareBackwardPointerDepths(const void* v1,const void* v2);
180 
181 
182  template<class NodeData2>
184 
185  static inline int Overlap2(const int &depth1,const int offSet1[DIMENSION],const Real& multiplier1,const int &depth2,const int offSet2[DIMENSION],const Real& multiplier2);
186 
187 
188  int write(const char* fileName) const;
189  int write(FILE* fp) const;
190  int read(const char* fileName);
191  int read(FILE* fp);
192 
194  {
195  public:
196  OctNode* neighbors[3][3][3];
197  Neighbors3( void );
198  void clear( void );
199  };
201  {
202  public:
204 
205  NeighborKey3( void );
206  ~NeighborKey3( void );
207 
208  void set( int depth );
211  Neighbors3& setNeighbors( OctNode* node , bool flags[3][3][3] );
214  };
216  {
217  public:
218  const OctNode* neighbors[3][3][3];
219  ConstNeighbors3( void );
220  void clear( void );
221  };
223  {
224  public:
226 
227  ConstNeighborKey3(void);
228  ~ConstNeighborKey3(void);
229 
230  void set(int depth);
232  ConstNeighbors3& getNeighbors( const OctNode* node , int minDepth );
233  };
235  {
236  public:
237  OctNode* neighbors[5][5][5];
238  Neighbors5( void );
239  void clear( void );
240  };
242  {
243  public:
244  const OctNode* neighbors[5][5][5];
245  ConstNeighbors5( void );
246  void clear( void );
247  };
248 
250  {
251  int _depth;
252  public:
254 
255  NeighborKey5( void );
256  ~NeighborKey5( void );
257 
258  void set( int depth );
259  Neighbors5& getNeighbors( OctNode* node );
260  Neighbors5& setNeighbors( OctNode* node , int xStart=0 , int xEnd=5 , int yStart=0 , int yEnd=5 , int zStart=0 , int zEnd=5 );
261  };
263  {
264  int _depth;
265  public:
267 
268  ConstNeighborKey5( void );
269  ~ConstNeighborKey5( void );
270 
271  void set( int depth );
272  ConstNeighbors5& getNeighbors( const OctNode* node );
273  };
274 
275  void centerIndex(int maxDepth,int index[DIMENSION]) const;
276  int width(int maxDepth) const;
277  };
278 
279 
280  }
281 }
282 
283 #include "octree_poisson.hpp"
284 
285 
286 
287 #endif // OCT_NODE
This templated class assists in memory allocation and is well suited for instances when it is known t...
Definition: allocator.h:50
ConstNeighbors3 & getNeighbors(const OctNode *node)
ConstNeighbors3 & getNeighbors(const OctNode *node, int minDepth)
ConstNeighbors5 & getNeighbors(const OctNode *node)
const OctNode * neighbors[3][3][3]
const OctNode * neighbors[5][5][5]
Neighbors3 & getNeighbors(OctNode *root, Point3D< Real > p, int d)
Neighbors3 & getNeighbors(OctNode *node)
Neighbors3 & setNeighbors(OctNode *root, Point3D< Real > p, int d)
Neighbors3 & setNeighbors(OctNode *node)
Neighbors3 & setNeighbors(OctNode *node, bool flags[3][3][3])
Neighbors5 & setNeighbors(OctNode *node, int xStart=0, int xEnd=5, int yStart=0, int yEnd=5, int zStart=0, int zEnd=5)
Neighbors5 & getNeighbors(OctNode *node)
int maxDepthLeaves(int maxDepth) const
static const int OffsetShift1
void depthAndOffset(int &depth, int offset[DIMENSION]) const
int maxDepth(void) const
static void ProcessNodeAdjacentNodes(int dx, int dy, int dz, OctNode *node1, int radius1, OctNode *node2, int radius2, int width2, NodeAdjacencyFunction *F, int processCurrent=1)
static void ProcessNodeAdjacentNodes(int maxDepth, OctNode *node1, int width1, OctNode *node2, int width2, NodeAdjacencyFunction *F, int processCurrent=1)
static void ProcessMaxDepthNodeAdjacentNodes(int dx, int dy, int dz, OctNode *node1, int radius1, OctNode *node2, int radius2, int width2, int depth, NodeAdjacencyFunction *F, int processCurrent=1)
static const int OffsetShift2
static int CompareBackwardDepths(const void *v1, const void *v2)
static int CompareForwardDepths(const void *v1, const void *v2)
const OctNode * prevBranch(const OctNode *current) const
int write(const char *fileName) const
static const int OffsetMask
int leaves(void) const
void processNodeNodes(OctNode *node, NodeAdjacencyFunction *F, int processCurrent=1)
bool isInside(Point3D< Real > p) const
static void ProcessMaxDepthNodeAdjacentNodes(int maxDepth, OctNode *node1, int width1, OctNode *node2, int width2, int depth, NodeAdjacencyFunction *F, int processCurrent=1)
static void DepthAndOffset(const long long &index, int &depth, int offset[DIMENSION])
static void ProcessFixedDepthNodeAdjacentNodes(int dx, int dy, int dz, OctNode *node1, int radius1, OctNode *node2, int radius2, int width2, int depth, NodeAdjacencyFunction *F, int processCurrent=1)
static void CenterAndWidth(const long long &index, Point3D< Real > &center, Real &width)
static Allocator< OctNode > internalAllocator
void processNodeEdges(OctNode *node, NodeAdjacencyFunction *F, int eIndex, int processCurrent=1)
static void ProcessTerminatingNodeAdjacentNodes(int dx, int dy, int dz, OctNode *node1, int radius1, OctNode *node2, int radius2, int width2, TerminatingNodeAdjacencyFunction *F, int processCurrent=1)
int read(const char *fileName)
static int Depth(const long long &index)
static int CompareForwardPointerDepths(const void *v1, const void *v2)
OctNode * getNearestLeaf(const Point3D< Real > &p)
static int CornerIndex(const Point3D< Real > &center, const Point3D< Real > &p)
static int Overlap2(const int &depth1, const int offSet1[DIMENSION], const Real &multiplier1, const int &depth2, const int offSet2[DIMENSION], const Real &multiplier2)
OctNode * edgeNeighbor(int edgeIndex, int forceChildren=0)
static const int OffsetShift
const OctNode * nextBranch(const OctNode *current) const
short off[DIMENSION]
static void ProcessPointAdjacentNodes(int maxDepth, const int center1[3], OctNode *node2, int width2, PointAdjacencyFunction *F, int processCurrent=1)
void setFullDepth(int maxDepth)
static void ProcessTerminatingNodeAdjacentNodes(int maxDepth, OctNode *node1, int width1, OctNode *node2, int width2, TerminatingNodeAdjacencyFunction *F, int processCurrent=1)
OctNode & operator=(const OctNode< NodeData2, Real > &node)
const OctNode * nextNode(const OctNode *currentNode=NULL) const
OctNode * cornerNeighbor(int cornerIndex, int forceChildren=0)
static void ProcessPointAdjacentNodes(int dx, int dy, int dz, OctNode *node2, int radius2, int width2, PointAdjacencyFunction *F, int processCurrent=1)
int width(int maxDepth) const
void printLeaves(void) const
void processNodeFaces(OctNode *node, NodeAdjacencyFunction *F, int fIndex, int processCurrent=1)
static int CommonEdge(const OctNode *node1, int eIndex1, const OctNode *node2, int eIndex2)
static void SetAllocator(int blockSize)
const OctNode * root(void) const
static int CompareByDepthAndZIndex(const void *v1, const void *v2)
void centerAndWidth(Point3D< Real > &center, Real &width) const
void centerIndex(int maxDepth, int index[DIMENSION]) const
const OctNode * nextLeaf(const OctNode *currentLeaf=NULL) const
static int CompareByDepthAndXYZ(const void *v1, const void *v2)
static void ProcessFixedDepthNodeAdjacentNodes(int maxDepth, OctNode *node1, int width1, OctNode *node2, int width2, int depth, NodeAdjacencyFunction *F, int processCurrent=1)
static int CompareBackwardPointerDepths(const void *v1, const void *v2)
static const int OffsetShift3
static int UseAllocator(void)
static void Index(int depth, const int offset[3], short &d, short off[DIMENSION])
void printRange(void) const
static const int DepthShift
static const int DepthMask
OctNode * faceNeighbor(int faceIndex, int forceChildren=0)
void processNodeCorners(OctNode *node, NodeAdjacencyFunction *F, int cIndex, int processCurrent=1)