Go to the documentation of this file.
62 #include "vtkCommonDataModelModule.h"
99 vtkSetMacro(MinCells,
int);
100 vtkGetMacro(MinCells,
int);
110 vtkGetMacro(NumberOfRegionsOrLess,
int);
111 vtkSetMacro(NumberOfRegionsOrLess,
int);
120 vtkGetMacro(NumberOfRegionsOrMore,
int);
121 vtkSetMacro(NumberOfRegionsOrMore,
int);
130 vtkGetMacro(FudgeFactor,
double);
131 vtkSetMacro(FudgeFactor,
double);
269 vtkGetMacro(NumberOfRegions,
int);
428 double **convexRegionBounds);
448 const double directionOfProjection[3],
469 const double directionOfProjection[3],
533 double radius,
const double x[3],
double& dist2);
596 vtkBooleanMacro(GenerateRepresentationUsingDataBounds,
vtkTypeBool);
753 vtkSetClampMacro(Progress,
double,0.0,1.0);
754 vtkGetMacro(Progress,
double);
822 int **pointsSoFar,
int *len,
823 float tolerance,
float tolerance2);
826 int len,
float tolerance2);
829 double x,
double y,
double z,
double &dist2);
832 int skipRegion,
double &dist2);
840 const double dir[3],
int nextId);
848 const double pos[3],
int nextId);
854 int dims[3],
double origin[3],
double spacing[3]);
856 int dims[3],
double origin[3],
double spacing[3]);
861 static int MidValue(
int dim,
float *c1,
int nvals,
double &coord);
863 static int Select(
int dim,
float *c1,
int *ids,
int nvals,
double &coord);
865 static void _Select(
int dim,
float *X,
int *ids,
int L,
int R,
int K);
876 int midpt,
int dim,
double coord);
884 double CellBoundsCache[6];
static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from)
represent and manipulate 3D points
void GetBounds(double *bounds)
Get the spatial bounds of the entire k-d tree space.
void CreateCellLists(vtkDataSet *set, int *regionReqList, int reqListSize)
This class represents a single spatial region in an 3D axis aligned binary spatial partitioning.
vtkIdList * GetList(int regionId, vtkIdList **which)
void OmitYPartitioning()
Omit partitions along the Y axis, yielding shafts in the Y direction.
vtkIdType GetCellLists(vtkIntArray *regions, int set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
For a list of regions, get two cell lists.
void AddPolys(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys)
int GetNumberOfCells()
Returns the total number of cells in all the data sets.
virtual void RemoveAllDataSets()
virtual void PrintTiming(ostream &os, vtkIndent indent)
Print timing of k-d tree build.
void OmitZXPartitioning()
Omit partitions along the Z and X axes, yielding slabs along Y.
void OmitXPartitioning()
Omit partitions along the X axis, yielding shafts in the X direction.
void NewPartitioningRequest(int req)
void _generateRepresentationWholeSpace(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys, int level)
int GetDataSetIndex(vtkDataSet *set)
Return the index of the given data set.
virtual void AddDataSet(vtkDataSet *set)
This class can compute a spatial decomposition based on the cells in a list of one or more input data...
void ComputeCellCenter(vtkDataSet *set, int cellId, float *center)
Get or compute the center of one cell.
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result)
Find all points within a specified radius R of position x.
int GetRegionContainingCell(vtkDataSet *set, vtkIdType cellID)
Get the id of the region containing the cell centroid.
vtkIdType FindPoint(double *x)
Find the Id of the point that was previously supplied to BuildLocatorFromPoints().
vtkIdTypeArray * BuildMapForDuplicatePoints(float tolerance)
This call returns a mapping from the original point IDs supplied to BuildLocatorFromPoints to a subse...
static void _SetNewBounds(vtkKdNode *kd, double *b, int *fixDim)
virtual void InvalidateGeometry()
Forget about the last geometry used.
void SetDataSet(vtkDataSet *set) override
This class can compute a spatial decomposition based on the cells in a list of one or more input data...
void FindPointsInArea(vtkKdNode *node, double *area, vtkIdTypeArray *ids)
int ViewOrderAllRegionsInDirection(const double directionOfProjection[3], vtkIntArray *orderedList)
Given a direction of projection (typically obtained with vtkCamera::GetDirectionOfProjection()),...
static int FoundId(vtkIntArray *idArray, int id)
int ViewOrderAllRegionsFromPosition(const double directionOfProjection[3], vtkIntArray *orderedList)
Given a camera position (typically obtained with vtkCamera::GetPosition()), this method,...
static void __printTree(vtkKdNode *kd, int depth, int verbose)
static void AddNewRegions(vtkKdNode *kd, float *c1, int midpt, int dim, double coord)
int FindClosestPointInSphere(double x, double y, double z, double radius, int skipRegion, double &dist2)
double * LastInputDataInfo
void PrintTree()
Print out nodes of kd tree.
static int Select(int dim, float *c1, int *ids, int nvals, double &coord)
vtkIdType * LastNumPoints
int SearchNeighborsForDuplicate(int regionId, float *point, int **pointsSoFar, int *len, float tolerance, float tolerance2)
static int findRegion(vtkKdNode *node, float x, float y, float z)
void GenerateRepresentation(int *regionList, int len, vtkPolyData *pd)
Generate a polygonal representation of a list of regions.
static int __ViewOrderRegionsFromPosition(vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double pos[3], int nextId)
vtkDataSet * GetDataSet(int n)
Get the nth defined data set in the spatial partitioning.
vtkIdType FindClosestPoint(double x, double y, double z, double &dist2)
virtual void RemoveDataSet(int index)
Remove the given data set.
vtkIdType FindPoint(double x, double y, double z)
int DivideTest(int numberOfPoints, int level)
Prior to dividing a region at level "level", of size "numberOfPoints", apply the tests implied by Min...
void ClearLastBuildCache()
int _ViewOrderRegionsFromPosition(vtkIntArray *IdsOfInterest, const double pos[3], vtkIntArray *orderedList)
void GetRegionsAtLevel(int level, vtkKdNode **nodes)
Get back a list of the nodes at a specified level, nodes must be preallocated to hold 2^^(level) node...
void ComputeCellCenter(vtkCell *cell, double *center, double *weights)
void FreeSearchStructure() override
Delete the k-d tree data structure.
int * AllGetRegionContainingCell()
Get a list (in order by data set by cell id) of the region IDs of the region containing the centroid ...
static vtkKdNode ** _GetRegionsAtLevel(int level, vtkKdNode **nodes, vtkKdNode *kd)
void GetRegionDataBounds(int regionID, double bounds[6])
Get the bounds of the data within the k-d tree region.
abstract base class for objects that accelerate spatial searches
void GenerateRepresentation(int level, vtkPolyData *pd) override
Create a polydata representation of the boundaries of the k-d tree regions.
void FindPointsInArea(double *area, vtkIdTypeArray *ids, bool clearArray=true)
Fill ids with points found in area.
void CreateCellLists(int dataSetIndex, int *regionReqList, int reqListSize)
Create a list for each of the requested regions, listing the IDs of all cells whose centroid falls in...
vtkIdType GetCellLists(vtkIntArray *regions, vtkDataSet *set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
void BuildLocator() override
Create the k-d tree decomposition of the cells of the data set or data sets.
Perform calculations (mostly intersection calculations) on regions of a 3D binary spatial partitionin...
virtual int SelectCutDirection(vtkKdNode *kd)
float * ComputeCellCenters()
Compute and return a pointer to a list of all cell centers, in order by data set by cell Id.
static float FindMaxLeftHalf(int dim, float *c1, int K)
int NumberOfRegionsOrMore
void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3])
void BuildLocatorFromPoints(vtkPoints **ptArray, int numPtArrays)
vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double &dist2)
Given a position x and a radius r, return the id of the point closest to the point in that radius.
void CreateCellLists(int *regionReqList, int listSize)
void InitializeCellLists()
int ProcessUserDefinedCuts(double *bounds)
int GetRegionContainingCell(int set, vtkIdType cellID)
vtkKdTree(const vtkKdTree &)=delete
vtkIdList * GetCellList(int regionID)
Get the cell list for a region.
int _FindClosestPointInRegion(int regionId, double x, double y, double z, double &dist2)
vtkIdList ** boundaryCells
void DoMedianFind(vtkKdNode *kd, float *c1, int *ids, int d1, int d2, int d3)
vtkBSPIntersections * BSPCalculator
abstract class to specify cell behavior
static int SelfOrder(int id, vtkKdNode *kd)
static vtkKdNode * CopyTree(vtkKdNode *kd)
Create a copy of the binary tree representation of the k-d tree spatial partitioning provided.
a simple class to control print indentation
static int ComputeLevel(vtkKdNode *kd)
object to represent cell connectivity
void SelfRegister(vtkKdNode *kd)
dynamic, self-adjusting array of int
unsigned long * LastDataSetObserverTags
static void SetDataBoundsToSpatialBounds(vtkKdNode *kd)
int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels)
void UpdateProgress(double amount)
Modelled on vtkAlgorithm::UpdateProgress().
vtkTypeBool GenerateRepresentationUsingDataBounds
This class represents an axis-aligned Binary Spatial Partitioning of a 3D space.
list of point or cell ids
void UpdateBuildTime()
Save enough state so NewGeometry() can work, and update the BuildTime time stamp.
void BuildLocatorFromPoints(vtkPoints *ptArray)
void OmitXYPartitioning()
Omit partitions along the X and Y axes, yielding slabs along Z.
vtkDataSet * GetDataSet() override
Return the 0'th data set.
int SearchRegionForDuplicate(float *point, int *pointsSoFar, int len, float tolerance2)
void GenerateRepresentationDataBounds(int level, vtkPolyData *pd)
void BuildLocatorFromPoints(vtkPointSet *pointset)
This is a special purpose locator that builds a k-d tree to find duplicate and near-by points.
void FindClosestNPoints(int N, const double x[3], vtkIdList *result)
Find the closest N points to a position.
vtkDataSet ** LastInputDataSets
void OmitZPartitioning()
Omit partitions along the Z axis, yielding shafts in the Z direction.
static void CopyKdNode(vtkKdNode *to, vtkKdNode *from)
int * LocatorRegionLocation
vtkIdList * GetBoundaryCellList(int regionID)
The cell list obtained with GetCellList is the list of all cells such that their centroid is containe...
void OmitNoPartitioning()
Partition along all three axes - this is the default.
virtual void RemoveDataSet(vtkDataSet *set)
vtkIdType GetCellLists(vtkIntArray *regions, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
vtkDataSetCollection * DataSets
void SetCuts(vtkBSPCuts *cuts)
Normally the k-d tree is computed from the dataset(s) provided in SetDataSet.
abstract class to specify dataset behavior
virtual int NewGeometry(vtkDataSet **sets, int numDataSets)
Return 1 if the geometry of these data sets differs for the geometry of the last data sets used to bu...
void UpdateSubOperationProgress(double amount)
Timer support and logging.
void PrintRegion(int id)
Print out leaf node data for given id.
dynamic, self-adjusting array of vtkIdType
int GetDataSetsNumberOfCells(int set1, int set2)
Returns the total number of cells in data set 1 through data set 2.
vtkTypeBool IncludeRegionBoundaryCells
void FindPointsWithinRadius(vtkKdNode *node, double R2, const double x[3], vtkIdList *ids)
void SetCuts(vtkBSPCuts *cuts, int userDefined)
void _generateRepresentationDataBounds(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys, int level)
abstract class for specifying dataset behavior
int NumberOfLocatorPoints
void SetNewBounds(double *bounds)
There are certain applications where you want the bounds of the k-d tree space to be at least as larg...
vtkIdType FindClosestPointInRegion(int regionId, double *x, double &dist2)
Find the Id of the point in the given region which is closest to the given point.
int MinimalNumberOfConvexSubRegions(vtkIntArray *regionIdList, double **convexRegionBounds)
Given a list of region IDs, determine the decomposition of these regions into the minimal number of c...
void AddAllPointsInRegion(vtkKdNode *node, vtkIdList *ids)
concrete dataset represents vertices, lines, polygons, and triangle strips
static void _Select(int dim, float *X, int *ids, int L, int R, int K)
void AddAllPointsInRegion(vtkKdNode *node, vtkIdTypeArray *ids)
void GetRegionBounds(int regionID, double bounds[6])
Get the spatial bounds of k-d tree region.
void ComputeCellCenter(vtkDataSet *set, int cellId, double *center)
a Kd-tree spatial decomposition of a set of points
int NumberOfRegionsOrLess
int GetRegionContainingPoint(double x, double y, double z)
Get the id of the region containing the specified location.
maintain an unordered list of dataset objects
int _ViewOrderRegionsInDirection(vtkIntArray *IdsOfInterest, const double dop[3], vtkIntArray *orderedList)
static int __ViewOrderRegionsInDirection(vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double dir[3], int nextId)
static int __ConvexSubRegions(int *ids, int len, vtkKdNode *tree, vtkKdNode **nodes)
float * ComputeCellCenters(int set)
vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double &dist2)
void DeleteCellLists()
Free the memory used by the cell lists.
static int findRegion(vtkKdNode *node, double x, double y, double z)
int GetRegionContainingCell(vtkIdType cellID)
int ViewOrderRegionsFromPosition(vtkIntArray *regionIds, const double directionOfProjection[3], vtkIntArray *orderedList)
Given a camera position and a list of k-d tree region IDs, this method, creates a list of the k-d tre...
void operator=(const vtkKdTree &)=delete
virtual int NewGeometry()
Return 1 if the geometry of the input data sets has changed since the last time the k-d tree was buil...
void OmitYZPartitioning()
Omit partitions along the Y and Z axes, yielding slabs along X.
int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3])
void SetCalculator(vtkKdNode *kd)
vtkIdTypeArray * GetPointsInRegion(int regionId)
Get a list of the original IDs of all points in a region.
void _printTree(int verbose)
int GetNumberOfDataSets()
Get the number of data sets included in spatial partitioning.
vtkIdType FindClosestPoint(double *x, double &dist2)
Find the Id of the point that was previously supplied to BuildLocatorFromPoints() which is closest to...
int ViewOrderRegionsInDirection(vtkIntArray *regionIds, const double directionOfProjection[3], vtkIntArray *orderedList)
Given a direction of projection and a list of k-d tree region IDs, this method, creates a list of the...
static void ZeroNumberOfPoints(vtkKdNode *kd)
float * ComputeCellCenters(vtkDataSet *set)
void GenerateRepresentationWholeSpace(int level, vtkPolyData *pd)
static void GetLeafNodeIds(vtkKdNode *node, vtkIntArray *ids)
Adds to the vtkIntArray the list of region IDs of all leaf nodes in the given node.
static int MidValue(int dim, float *c1, int nvals, double &coord)
static void DeleteAllDescendants(vtkKdNode *nd)