Find file
Fetching contributors…
Cannot retrieve contributors at this time
261 lines (209 sloc) 9.33 KB
/*=========================================================================
Program: Visualization Toolkit
Module: vtkKdNode.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.
=========================================================================*/
/*----------------------------------------------------------------------------
Copyright (c) Sandia Corporation
See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
----------------------------------------------------------------------------*/
// .NAME vtkKdNode - This class represents a single spatial region
// in an 3D axis aligned binary spatial partitioning. It is assumed
// the region bounds some set of points. Regions are represented
// as nodes in a binary tree.
//
// .SECTION Description
//
// .SECTION See Also
// vtkKdTree vtkOBSPCuts
#ifndef __vtkKdNode_h
#define __vtkKdNode_h
#include "vtkObject.h"
class vtkCell;
class vtkPlanesIntersection;
class VTK_FILTERING_EXPORT vtkKdNode : public vtkObject
{
public:
vtkTypeMacro(vtkKdNode, vtkObject);
void PrintSelf(ostream& os, vtkIndent indent);
static vtkKdNode *New();
// Description:
// Set/Get the dimension along which this region is divided.
// (0 - x, 1 - y, 2 - z, 3 - leaf node (default)).
vtkSetMacro(Dim, int);
vtkGetMacro(Dim, int);
// Description:
// Get the location of the division plane along the axis the region
// is divided. See also GetDim(). The result is undertermined if
// this node is not divided (a leaf node).
virtual double GetDivisionPosition();
// Description:
// Set/Get the number of points contained in this region.
vtkSetMacro(NumberOfPoints, int);
vtkGetMacro(NumberOfPoints, int);
// Description:
// Set/Get the bounds of the spatial region represented by this node.
// Caller allocates storage for 6-vector in GetBounds.
void SetBounds(double x1,double x2,double y1,double y2,double z1,double z2);
void SetBounds(double b[6])
{
this->SetBounds(b[0], b[1], b[2], b[3], b[4], b[5]);
}
void GetBounds(double *b) const;
// Description:
// Set/Get the bounds of the points contained in this spatial region.
// This may be smaller than the bounds of the region itself.
// Caller allocates storage for 6-vector in GetDataBounds.
void SetDataBounds(double x1,double x2,double y1,double y2,double z1,double z2);
void GetDataBounds(double *b) const;
// Description:
// Given a pointer to NumberOfPoints points, set the DataBounds of this
// node to the bounds of these points.
void SetDataBounds(float *v);
// Description:
// Get a pointer to the 3 bound minima (xmin, ymin and zmin) or the
// 3 bound maxima (xmax, ymax, zmax). Don't free this pointer.
double *GetMinBounds() {return this->Min;}
double *GetMaxBounds() {return this->Max;}
// Description:
// Set the xmin, ymin and zmin value of the bounds of this region
void SetMinBounds(double *mb);
// Description:
// Set the xmax, ymax and zmax value of the bounds of this region
void SetMaxBounds(double *mb);
// Description:
// Get a pointer to the 3 data bound minima (xmin, ymin and zmin) or the
// 3 data bound maxima (xmax, ymax, zmax). Don't free this pointer.
double *GetMinDataBounds() {return this->MinVal;}
double *GetMaxDataBounds() {return this->MaxVal;}
// Description:
// Set the xmin, ymin and zmin value of the bounds of this
// data within this region
void SetMinDataBounds(double *mb);
// Description:
// Set the xmax, ymax and zmax value of the bounds of this
// data within this region
void SetMaxDataBounds(double *mb);
// Description:
// Set/Get the ID associated with the region described by this node. If
// this is not a leaf node, this value should be -1.
vtkSetMacro(ID, int);
vtkGetMacro(ID, int);
// Description:
// If this node is not a leaf node, there are leaf nodes below it whose
// regions represent a partitioning of this region. The IDs of these
// leaf nodes form a contigous set. Set/Get the range of the IDs of
// the leaf nodes below this node. If this is already a leaf node, these
// values should be the same as the ID.
vtkGetMacro(MinID, int);
vtkGetMacro(MaxID, int);
vtkSetMacro(MinID, int);
vtkSetMacro(MaxID, int);
// Description:
// Add the left and right children.
void AddChildNodes(vtkKdNode *left, vtkKdNode *right);
// Description:
// Delete the left and right children.
void DeleteChildNodes();
// Description:
// Set/Get a pointer to the left child of this node.
vtkGetObjectMacro(Left, vtkKdNode);
void SetLeft(vtkKdNode* left);
// Description:
// Set/Get a pointer to the right child of this node.
vtkGetObjectMacro(Right, vtkKdNode);
void SetRight(vtkKdNode *right);
// Description:
// Set/Get a pointer to the parent of this node.
vtkGetObjectMacro(Up, vtkKdNode);
void SetUp(vtkKdNode* up);
// Description:
// Return 1 if this spatial region intersects the axis-aligned box given
// by the bounds passed in. Use the possibly smaller bounds of the points
// within the region if useDataBounds is non-zero.
int IntersectsBox(double x1,double x2,double y1,double y2,double z1,double z2,
int useDataBounds);
// Description:
// Return 1 if this spatial region intersects a sphere described by
// it's center and the square of it's radius. Use the possibly smaller
// bounds of the points within the region if useDataBounds is non-zero.
int IntersectsSphere2(double x, double y, double z, double rSquared,
int useDataBounds);
// Description:
// A vtkPlanesIntersection object represents a convex 3D region bounded
// by planes, and it is capable of computing intersections of
// boxes with itself. Return 1 if this spatial region intersects
// the spatial region described by the vtkPlanesIntersection object.
// Use the possibly smaller bounds of the points within the region
// if useDataBounds is non-zero.
int IntersectsRegion(vtkPlanesIntersection *pi, int useDataBounds);
// Description:
// Return 1 if the cell specified intersects this region. If you
// already know the ID of the region containing the cell's centroid,
// provide that as an argument. If you already know the bounds of the
// cell, provide that as well, in the form of xmin,xmax,ymin,ymax,zmin,
// zmax. Either of these may speed the calculation.
// Use the possibly smaller bounds of the points within the region
// if useDataBounds is non-zero.
int IntersectsCell(vtkCell *cell, int useDataBounds,
int cellRegion=-1, double *cellBounds=NULL);
// Description:
// Return 1 if this spatial region entirely contains a box specified
// by it's bounds. Use the possibly smaller
// bounds of the points within the region if useDataBounds is non-zero.
int ContainsBox(double x1,double x2,double y1,double y2,double z1,double z2,
int useDataBounds);
// Description:
// Return 1 if this spatial region entirely contains the given point.
// Use the possibly smaller bounds of the points within the region
// if useDataBounds is non-zero.
int ContainsPoint(double x, double y, double z, int useDataBounds);
// Description:
// Calculate the distance squared from any point to the boundary of this
// region. Use the boundary of the points within the region if useDataBounds
// is non-zero.
double GetDistance2ToBoundary(double x, double y, double z, int useDataBounds);
// Description:
// Calculate the distance squared from any point to the boundary of this
// region. Use the boundary of the points within the region if useDataBounds
// is non-zero. Set boundaryPt to the point on the boundary.
double GetDistance2ToBoundary(double x, double y, double z, double *boundaryPt,
int useDataBounds);
// Description:
// Calculate the distance from the specified point (which is required to
// be inside this spatial region) to an interior boundary. An interior
// boundary is one that is not also an boundary of the entire space
// partitioned by the tree of vtkKdNode's.
double GetDistance2ToInnerBoundary(double x, double y, double z);
// Description:
// For debugging purposes, print out this node.
void PrintNode(int depth);
void PrintVerboseNode(int depth);
protected:
vtkKdNode();
~vtkKdNode();
private:
double _GetDistance2ToBoundary(
double x, double y, double z, double *boundaryPt,
int innerBoundaryOnly, int useDataBounds);
double Min[3]; // spatial bounds of node
double Max[3]; // spatial bounds of node
double MinVal[3]; // spatial bounds of data within node
double MaxVal[3]; // spatial bounds of data within node
int NumberOfPoints;
vtkKdNode *Up;
vtkKdNode *Left;
vtkKdNode *Right;
int Dim;
int ID; // region id
int MinID;
int MaxID;
vtkKdNode(const vtkKdNode&); // Not implemented
void operator=(const vtkKdNode&); // Not implemented
};
#endif