Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

415 lines (354 sloc) 18.639 kB
/*=========================================================================
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
Jump to Line
Something went wrong with that request. Please try again.