Point Cloud Library (PCL) 1.13.0
octree_poisson.h
1/*
2Copyright (c) 2006, Michael Kazhdan and Matthew Bolitho
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without modification,
6are permitted provided that the following conditions are met:
7
8Redistributions of source code must retain the above copyright notice, this list of
9conditions and the following disclaimer. Redistributions in binary form must reproduce
10the above copyright notice, this list of conditions and the following disclaimer
11in the documentation and/or other materials provided with the distribution.
12
13Neither the name of the Johns Hopkins University nor the names of its contributors
14may be used to endorse or promote products derived from this software without specific
15prior written permission.
16
17THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
18EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO THE IMPLIED WARRANTIES
19OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
20SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
21INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
22TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
23BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
25ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
26DAMAGE.
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
42namespace 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:
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:
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 );
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 & setNeighbors(OctNode *node, bool flags[3][3][3])
Neighbors3 & setNeighbors(OctNode *node)
Neighbors3 & getNeighbors(OctNode *node)
Neighbors3 & getNeighbors(OctNode *root, Point3D< Real > p, int d)
Neighbors3 & setNeighbors(OctNode *root, Point3D< Real > p, int d)
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)
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)
OctNode & operator=(const OctNode< NodeData2, Real > &node)
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)