/usr/include/vtk-5.8/vtkIncrementalOctreeNode.h is in libvtk5-dev 5.8.0-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 | /*=========================================================================
Program: Visualization Toolkit
Module: vtkIncrementalOctreeNode.h
Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
All rights reserved.
See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
This software is distributed WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the above copyright notice for more information.
=========================================================================*/
// .NAME vtkIncrementalOctreeNode - Octree node constituting incremental
// octree (in support of both point location and point insertion)
//
// .SECTION Description
// Octree nodes serve as spatial sub-division primitives to build the search
// structure of an incremental octree in a recursive top-down manner. The
// hierarchy takes the form of a tree-like representation by which a parent
// node contains eight mutually non-overlapping child nodes. Each child is
// assigned with an axis-aligned rectangular volume (Spatial Bounding Box)
// and the eight children together cover exactly the same region as governed
// by their parent. The eight child nodes / octants are ordered as
//
// { (xBBoxMin, xBBoxMid] & (yBBoxMin, yBBoxMid] & (zBBoxMin, zBBoxMid] },
// { (xBBoxMid, xBBoxMax] & (yBBoxMin, yBBoxMid] & (zBBoxMin, zBBoxMid] },
// { (xBBoxMin, xBBoxMid] & (yBBoxMid, yBBoxMax] & (zBBoxMin, zBBoxMid] },
// { (xBBoxMid, xBBoxMax] & (yBBoxMid, yBBoxMax] & (zBBoxMin, zBBoxMid] },
// { (xBBoxMin, xBBoxMid] & (yBBoxMin, yBBoxMid] & (zBBoxMid, zBBoxMax] },
// { (xBBoxMid, xBBoxMax] & (yBBoxMin, yBBoxMid] & (zBBoxMid, zBBoxMax] },
// { (xBBoxMin, xBBoxMid] & (yBBoxMid, yBBoxMax] & (zBBoxMid, zBBoxMax] },
// { (xBBoxMid, xBBoxMax] & (yBBoxMid, yBBoxMax] & (zBBoxMid, zBBoxMax] },
//
// where { xrange & yRange & zRange } defines the region of each 3D octant.
// In addition, the points falling within and registered, by means of point
// indices, in the parent node are distributed to the child nodes for delegated
// maintenance. In fact, only leaf nodes, i.e., those without any descendants,
// actually store point indices while each node, regardless of a leaf or non-
// leaf node, keeps a dynamically updated Data Bounding Box of the inhabitant
// points, if any. Given a maximum number of points per leaf node, an octree
// is initialized with an empty leaf node that is then recursively sub-divided,
// but only on demand as points are incrementally inserted, to construct a
// populated tree.
//
// Please note that this octree node class is able to handle a large number
// of EXACTLY duplicate points that is greater than the specified maximum
// number of points per leaf node. In other words, as an exception, a leaf
// node may maintain an arbitrary number of exactly duplicate points to deal
// with possible extreme cases.
//
// .SECTION See Also
// vtkIncrementalOctreePointLocator
#ifndef __vtkIncrementalOctreeNode_h
#define __vtkIncrementalOctreeNode_h
#include "vtkObject.h"
class vtkPoints;
class vtkIdList;
class VTK_FILTERING_EXPORT vtkIncrementalOctreeNode : public vtkObject
{
public:
vtkTypeMacro( vtkIncrementalOctreeNode, vtkObject );
void PrintSelf( ostream & os, vtkIndent indent );
static vtkIncrementalOctreeNode * New();
// Description:
// Get the number of points inside or under this node.
vtkGetMacro( NumberOfPoints, int );
// Description:
// Get the list of point indices, NULL for a non-leaf node.
vtkGetObjectMacro( PointIdSet, vtkIdList );
// Description:
// Delete the eight child nodes.
void DeleteChildNodes();
// Description:
// Set the spatial bounding box of the node. This function sets a default
// data bounding box.
void SetBounds( double x1, double x2, double y1,
double y2, double z1, double z2 );
// Description:
// Get the spatial bounding box of the node. The values are returned via
// an array in order of: x_min, x_max, y_min, y_max, z_min, z_max.
void GetBounds( double bounds[6] ) const;
// Description:
// Get access to MinBounds. Do not free this pointer.
vtkGetVector3Macro( MinBounds, double );
// Description:
// Get access to MaxBounds. Do not free this pointer.
vtkGetVector3Macro( MaxBounds, double );
// Description:
// Get access to MinDataBounds. Note that MinDataBounds is not valid until
// point insertion.
double * GetMinDataBounds()
{ return this->NumberOfPoints ? this->MinDataBounds : this->MinBounds; }
// Description:
// Get access to MaxDataBounds. Note that MaxDataBounds is not valid until
// point insertion.
double * GetMaxDataBounds()
{ return this->NumberOfPoints ? this->MaxDataBounds : this->MaxBounds; }
// Description:
// Determine whether or not this node is a leaf.
int IsLeaf() { return ( this->Children == NULL ) ? 1 : 0; }
// Description:
// Determine which specific child / octant contains a given point. Note that
// the point is assumed to be inside this node and no checking is performed
// on the inside issue.
int GetChildIndex( const double point[3] );
// Description:
// Get quick access to a child of this node. Note that this node is assumed
// to be a non-leaf one and no checking is performed on the node type.
vtkIncrementalOctreeNode * GetChild( int i ) { return this->Children[i]; }
// Description:
// A point is in a node if and only if MinBounds[i] < p[i] <= MaxBounds[i],
// which allows a node to be divided into eight non-overlapping children.
int ContainsPoint( const double pnt[3] );
// Description:
// A point is in a node, in terms of data, if and only if MinDataBounds[i]
// <= p[i] <= MaxDataBounds[i].
int ContainsPointByData( const double pnt[3] );
// Description:
// This function is called after a successful point-insertion check and
// only applies to a leaf node. Prior to a call to this function, the
// octree should have been retrieved top-down to find the specific leaf
// node in which this new point (newPt) will be inserted. The actual index
// of the new point (to be inserted to points) is stored in pntId. Argument
// ptMode specifies whether the point is not inserted at all but instead only
// the point index is provided upon 0, the point is inserted via vtkPoints::
// InsertPoint() upon 1, or it is inserted via vtkPoints::InsertNextPoint()
// upon 2. For case 0, pntId needs to be specified. For cases 1 and 2, the
// actual point index is returned via pntId. Note that this function always
// returns 1 to indicate the success of point insertion.
int InsertPoint( vtkPoints * points, const double newPnt[3],
int maxPts, vtkIdType * pntId, int ptMode );
// Description:
// Given a point inside this node, get the minimum squared distance to all
// inner boundaries. An inner boundary is a node's face that is shared by
// another non-root node.
double GetDistance2ToInnerBoundary( const double point[3],
vtkIncrementalOctreeNode * rootNode );
// Description:
// Compute the minimum squared distance from a point to this node, with all
// six boundaries considered. The data bounding box is checked if checkData
// is non-zero.
double GetDistance2ToBoundary( const double point[3],
vtkIncrementalOctreeNode * rootNode, int checkData );
// Description:
// Compute the minimum squared distance from a point to this node, with all
// six boundaries considered. The data bounding box is checked if checkData
// is non-zero. The closest on-boundary point is returned via closest.
double GetDistance2ToBoundary( const double point[3], double closest[3],
vtkIncrementalOctreeNode * rootNode, int checkData );
// Description:
// Export all the indices of the points (contained in or under this node) by
// inserting them to an allocated vtkIdList via vtkIdList::InsertNextId().
void ExportAllPointIdsByInsertion( vtkIdList * idList );
// Description:
// Export all the indices of the points (contained in or under this node) by
// directly setting them in an allocated vtkIdList object. pntIdx indicates
// the starting location (in terms of vtkIdList) from which new point indices
// are added to vtkIdList by vtkIdList::SetId().
void ExportAllPointIdsByDirectSet( vtkIdType * pntIdx, vtkIdList * idList );
//BTX
protected:
vtkIncrementalOctreeNode();
~vtkIncrementalOctreeNode();
private:
// Description:
// Number of points inside or under this node.
int NumberOfPoints;
// Description:
// The minimum coordinate of this node's spatial bounding box.
double MinBounds[3];
// Description:
// The maximum coordinate of this node's spatial bounding box.
double MaxBounds[3];
// Description:
// The minimum coordinate of the data bounding box that encompasses the
// points inserted, by means of the point index, to this node. Note this
// information is invalid if no any point has been inserted to this node.
double MinDataBounds[3];
// Description:
// The maximum coordinate of the data bounding box that encompasses the
// points inserted, by means of the point index, to this node. Note this
// information is invalid if no any point has been inserted to this node.
double MaxDataBounds[3];
// Description:
// The list of indices of the points maintained by this LEAF node. It is
// NULL if this is a non-leaf node.
vtkIdList * PointIdSet;
// Description:
// The parent of this node, NULL for the root node of an octree.
vtkIncrementalOctreeNode * Parent;
// Description:
// A pointer to the eight children of this node.
vtkIncrementalOctreeNode ** Children;
// Description:
// Set the parent of this node, NULL for the root node of an octree.
virtual void SetParent( vtkIncrementalOctreeNode * );
// Description:
// Set the list of point indices, NULL for a non-leaf node.
virtual void SetPointIdSet( vtkIdList * );
// Description:
// Divide this LEAF node into eight child nodes as the number of points
// maintained by this leaf node has reached the threshold maxPts while
// another point newPnt is just going to be inserted to it. The available
// point-indices pntIds are distributed to the child nodes based on the
// point coordinates (available through points). Note that this function
// can incur recursive node-division to determine the specific leaf node
// for accepting the new point (with pntIdx storing the index in points)
// because the existing maxPts points may fall within only one of the eight
// child nodes to make a radically imbalanced layout within the node (to
// be divided). Argument ptMode specifies whether the point is not inserted
// at all but instead only the point index is provided upon 0, the point is
// inserted via vtkPoints::InsertPoint() upon 1, or the point is inserted by
// vtkPoints::InsertNextPoint() upon 2. The returned value of this function
// indicates whether pntIds needs to be destroyed (1) or just unregistered
// from this node as it has been attached to another node (0).
int CreateChildNodes( vtkPoints * points, vtkIdList * pntIds,
const double newPnt[3], vtkIdType * pntIdx, int maxPts, int ptMode );
// Description:
// Create a vtkIdList object for storing point indices. Two arguments
// specifies the initial and growing sizes, respectively, of the object.
void CreatePointIdSet( int initSize, int growSize );
// Description:
// Delete the list of point indices.
void DeletePointIdSet();
// Description:
// Given a point inserted to either this node (a leaf node) or a descendant
// leaf (of this node --- when this node is a non-leaf node), update the
// counter and the data bounding box for this node only.
void UpdateCounterAndDataBounds( const double point[3] );
// Description:
// Given a point inserted to either this node (a leaf node) or a descendant
// leaf (of this node --- when this node is a non-leaf node), update the
// counter and the data bounding box for this node only. The data bounding box
// is considered only if updateData is non-zero. The returned value indicates
// whether (1) or not (0) the data bounding box is actually updated. Note that
// argument nHits must be 1 unless this node is updated with a number (nHits)
// of exactly duplicate points as a whole via a single call to this function.
int UpdateCounterAndDataBounds
( const double point[3], int nHits, int updateData );
// Description:
// Given a point inserted to either this node (a leaf node) or a descendant
// leaf (of this node --- when this node is a non-leaf node), update the
// counter and the data bounding box recursively bottom-up until a specified
// node. The data bounding box is considered only if updateData is non-zero.
// The returned value indicates whether (1) or not (0) the data bounding box
// is actually updated. Note that argument nHits must be 1 unless this node
// is updated with a number (nHits) of exactly duplicate points as a whole
// via a single call to this function.
int UpdateCounterAndDataBoundsRecursively( const double point[3], int nHits,
int updateData, vtkIncrementalOctreeNode * endNode );
// Description:
// Given a point, determine whether (1) or not (0) it is an exact duplicate
// of all the points, if any, maintained in this node. In other words, to
// check if this given point and all existing points, if any, of this node
// are exactly duplicate with one another.
int ContainsDuplicatePointsOnly( const double pnt[3] );
// Description:
// Given a number (>= threshold) of all exactly duplicate points (accessable
// via points and pntIds, but with exactly the same 3D coordinate) maintained
// in this leaf node and a point (absolutely not a duplicate any more, with
// pntIdx storing the index in points)) to be inserted to this node, separate
// all the duplicate points from this new point by means of usually recursive
// node sub-division such that the former points are inserted to a descendant
// leaf while the new point is inserted to a sibling of this descendant leaf.
// Argument ptMode specifies whether the point is not inserted at all but only
// the point index is provided upon 0, the point is inserted via vtkPoints::
// InsertPoint() upon 1, or this point is instead inserted through vtkPoints::
// InsertNextPoint() upon 2.
void SeperateExactlyDuplicatePointsFromNewInsertion( vtkPoints * points,
vtkIdList * pntIds, const double newPnt[3],
vtkIdType * pntIdx, int maxPts, int ptMode );
// Description:
// Given a point, obtain the minimum squared distance to the closest point
// on a boundary of this node. As two options, the outer boundaries may be
// excluded (by comparing them against those of the root node) from
// consideration and the data bounding box may be checked in place of the
// spatial bounding box.
double GetDistance2ToBoundary( const double point[3], double closest[3],
int innerOnly, vtkIncrementalOctreeNode* rootNode, int checkData = 0 );
vtkIncrementalOctreeNode( const vtkIncrementalOctreeNode & );// Not implemented
void operator = ( const vtkIncrementalOctreeNode & ); // Not implemented
//ETX
};
// In-lined for performance
inline int vtkIncrementalOctreeNode::GetChildIndex( const double point[3] )
{
// Children[0]->MaxBounds[] is exactly the center point of this node.
return int( point[0] > this->Children[0]->MaxBounds[0] ) +
( ( int( point[1] > this->Children[0]->MaxBounds[1] ) ) << 1 ) +
( ( int( point[2] > this->Children[0]->MaxBounds[2] ) ) << 2 );
}
// In-lined for performance
inline int vtkIncrementalOctreeNode::ContainsPoint( const double pnt[3] )
{
return (
( this->MinBounds[0] < pnt[0] && pnt[0] <= this->MaxBounds[0] &&
this->MinBounds[1] < pnt[1] && pnt[1] <= this->MaxBounds[1] &&
this->MinBounds[2] < pnt[2] && pnt[2] <= this->MaxBounds[2]
) ? 1 : 0
);
}
// In-lined for performance
inline int vtkIncrementalOctreeNode::ContainsPointByData( const double pnt[3] )
{
return
(
( this->MinDataBounds[0] <= pnt[0] && pnt[0] <= this->MaxDataBounds[0] &&
this->MinDataBounds[1] <= pnt[1] && pnt[1] <= this->MaxDataBounds[1] &&
this->MinDataBounds[2] <= pnt[2] && pnt[2] <= this->MaxDataBounds[2]
) ? 1 : 0
);
}
// In-lined for performance
inline int vtkIncrementalOctreeNode::ContainsDuplicatePointsOnly
( const double pnt[3] )
{
return
(
( this->MinDataBounds[0] == pnt[0] && pnt[0] == this->MaxDataBounds[0] &&
this->MinDataBounds[1] == pnt[1] && pnt[1] == this->MaxDataBounds[1] &&
this->MinDataBounds[2] == pnt[2] && pnt[2] == this->MaxDataBounds[2]
) ? 1 : 0
);
}
// In-lined for performance
inline void vtkIncrementalOctreeNode::UpdateCounterAndDataBounds
( const double point[3] )
{
this->NumberOfPoints ++;
this->MinDataBounds[0] = ( point[0] < this->MinDataBounds[0] )
? point[0] : this->MinDataBounds[0];
this->MinDataBounds[1] = ( point[1] < this->MinDataBounds[1] )
? point[1] : this->MinDataBounds[1];
this->MinDataBounds[2] = ( point[2] < this->MinDataBounds[2] )
? point[2] : this->MinDataBounds[2];
this->MaxDataBounds[0] = ( point[0] > this->MaxDataBounds[0] )
? point[0] : this->MaxDataBounds[0];
this->MaxDataBounds[1] = ( point[1] > this->MaxDataBounds[1] )
? point[1] : this->MaxDataBounds[1];
this->MaxDataBounds[2] = ( point[2] > this->MaxDataBounds[2] )
? point[2] : this->MaxDataBounds[2];
}
// In-lined for performance
inline int vtkIncrementalOctreeNode::UpdateCounterAndDataBoundsRecursively
( const double point[3], int nHits, int updateData,
vtkIncrementalOctreeNode * endNode )
{
int updated = this->UpdateCounterAndDataBounds
( point, nHits, updateData );
return ( ( this->Parent == endNode )
? updated
: this->Parent->UpdateCounterAndDataBoundsRecursively
( point, nHits, updated, endNode )
);
}
#endif
|