// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen // SPDX-License-Identifier: BSD-3-Clause /** * @class vtkIncrementalOctreePointLocator * @brief Incremental octree in support * of both point location and point insertion. * * * As opposed to the uniform bin-based search structure (adopted in class * vtkPointLocator) with a fixed spatial resolution, an octree mechanism * employs a hierarchy of tree-like sub-division of the 3D data domain. Thus * it enables data-aware multi-resolution and accordingly accelerated point * location as well as insertion, particularly when handling a radically * imbalanced layout of points as not uncommon in datasets defined on * adaptive meshes. Compared to a static point locator supporting pure * location functionalities through some search structure established from * a fixed set of points, an incremental point locator allows for, in addition, * point insertion capabilities, with the search structure maintaining a * dynamically increasing number of points. * Class vtkIncrementalOctreePointLocator is an octree-based accelerated * implementation of the functionalities of the uniform bin-based incremental * point locator vtkPointLocator. For point location, an octree is built by * accessing a vtkDataSet, specifically a vtkPointSet. For point insertion, * an empty octree is inited and then incrementally populated as points are * inserted. Three increasingly complex point insertion modes, i.e., direct * check-free insertion, zero tolerance insertion, and non-zero tolerance * insertion, are supported. In fact, the octree used in the point location * mode is actually constructed via direct check-free point insertion. This * class also provides a polygonal representation of the octree boundary. * * @sa * vtkAbstractPointLocator, vtkIncrementalPointLocator, vtkPointLocator, * vtkMergePoints */ #ifndef vtkIncrementalOctreePointLocator_h #define vtkIncrementalOctreePointLocator_h #include "vtkCommonDataModelModule.h" // For export macro #include "vtkIncrementalPointLocator.h" VTK_ABI_NAMESPACE_BEGIN class vtkPoints; class vtkIdList; class vtkIntArray; class vtkPolyData; class vtkCellArray; class vtkIncrementalOctreeNode; class VTKCOMMONDATAMODEL_EXPORT vtkIncrementalOctreePointLocator : public vtkIncrementalPointLocator { public: vtkTypeMacro(vtkIncrementalOctreePointLocator, vtkIncrementalPointLocator); void PrintSelf(ostream& os, vtkIndent indent) override; static vtkIncrementalOctreePointLocator* New(); ///@{ /** * Set/Get the maximum number of points that a leaf node may maintain. * Note that the actual number of points maintained by a leaf node might * exceed this threshold if there is a large number (equal to or greater * than the threshold) of exactly duplicate points (with zero distance) * to be inserted (e.g., to construct an octree for subsequent point * location) in extreme cases. Respecting this threshold in such scenarios * would cause endless node sub-division. Thus this threshold is broken, but * only in case of such situations. */ vtkSetMacro(MaxPointsPerLeaf, int); vtkGetMacro(MaxPointsPerLeaf, int); ///@} ///@{ /** * Set/Get whether the search octree is built as a cubic shape or not. */ vtkSetMacro(BuildCubicOctree, vtkTypeBool); vtkGetMacro(BuildCubicOctree, vtkTypeBool); vtkBooleanMacro(BuildCubicOctree, vtkTypeBool); ///@} ///@{ /** * Get access to the vtkPoints object in which point coordinates are stored * for either point location or point insertion. */ vtkGetObjectMacro(LocatorPoints, vtkPoints); ///@} /** * Delete the octree search structure. */ void Initialize() override { this->FreeSearchStructure(); } /** * Delete the octree search structure. */ void FreeSearchStructure() override; /** * Get the spatial bounding box of the octree. */ void GetBounds(double* bounds) override; /** * Get the spatial bounding box of the octree. */ double* GetBounds() override { this->GetBounds(this->Bounds); return this->Bounds; } /** * Get the number of points maintained by the octree. */ int GetNumberOfPoints(); /** * Get number of nodes in the tree. */ vtkGetMacro(NumberOfNodes, int); /** * Given a point x assumed to be covered by the octree, return the index of * the closest in-octree point regardless of the associated minimum squared * distance relative to the squared insertion-tolerance distance. This method * is used when performing incremental point insertion. Note -1 indicates that * no point is found. InitPointInsertion() should have been called in advance. */ vtkIdType FindClosestInsertedPoint(const double x[3]) override; ///@{ /** * Create a polygonal representation of the octree 'level': for each node * on the specified level we generate six faces for the bounding box of the node. * We also include a cell attribute that specifies the Index of the node. * The second version of this function, generates user defined boundaries * provided by 'GetBounds'. This function takes as parameters a user defined * opaque 'data', the current node, and a pointer to where to write the 'bounds'. * The function returns true if we want to generate the representation for this node, * and false otherwise. A user can store data associated with a node using * the node index. * @see vtkIncrementalOctreeNode::GetIndex */ void GenerateRepresentation(int level, vtkPolyData* polysData) override; void GenerateRepresentation(int level, vtkPolyData* polysData, bool (*UserGetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data); ///@} // ------------------------------------------------------------------------- // ---------------------------- Point Location ---------------------------- // ------------------------------------------------------------------------- /** * Load points from a dataset to construct an octree for point location. * This function resorts to InitPointInsertion() to fulfill some of the work. * This will NOT do anything if UseExistingSearchStructure is on. */ void BuildLocator() override; /** * Build the locator from the input dataset (even if UseExistingSearchStructure is on). */ void ForceBuildLocator() override; /** * Given a point x, return the id of the closest point. BuildLocator() should * have been called prior to this function. This method is thread safe if * BuildLocator() is directly or indirectly called from a single thread first. */ vtkIdType FindClosestPoint(const double x[3]) override; /** * Given a point (x, y, z), return the id of the closest point. Note that * BuildLocator() should have been called prior to this function. This method * is thread safe if BuildLocator() is directly or indirectly called from a * single thread first. */ virtual vtkIdType FindClosestPoint(double x, double y, double z); /** * Given a point x, return the id of the closest point and the associated * minimum squared distance (via miniDist2). Note BuildLocator() should have * been called prior to this function. This method is thread safe if * BuildLocator() is directly or indirectly called from a single thread first. */ virtual vtkIdType FindClosestPoint(const double x[3], double* miniDist2); /** * Given a point (x, y, z), return the id of the closest point and the * associated minimum squared distance (via miniDist2). BuildLocator() should * have been called prior to this function. This method is thread safe if * BuildLocator() is directly or indirectly called from a single thread first. */ virtual vtkIdType FindClosestPoint(double x, double y, double z, double* miniDist2); /** * Given a point x and a radius, return the id of the closest point within * the radius and the associated minimum squared distance (via dist2, this * returned distance is valid only if the point id is not -1). Note that * BuildLocator() should have been called prior to this function. This method * is thread safe if BuildLocator() is directly or indirectly called from a * single thread first. */ vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override; /** * Given a point x and a squared radius radius2, return the id of the closest * point within the radius and the associated minimum squared distance (via * dist2, note this returned distance is valid only if the point id is not * -1). BuildLocator() should have been called prior to this function.This * method is thread safe if BuildLocator() is directly or indirectly called * from a single thread first. */ vtkIdType FindClosestPointWithinSquaredRadius(double radius2, const double x[3], double& dist2); /** * Find all points within a radius R relative to a given point x. The returned * point ids (stored in result) are not sorted in any way. BuildLocator() should * have been called prior to this function. This method is thread safe if * BuildLocator() is directly or indirectly called from a single thread first. */ void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override; /** * Find all points within a squared radius R2 relative to a given point x. The * returned point ids (stored in result) are not sorted in any way. BuildLocator() * should have been called prior to this function. This method is thread safe if * BuildLocator() is directly or indirectly called from a single thread first. */ void FindPointsWithinSquaredRadius(double R2, const double x[3], vtkIdList* result); /** * Find the closest N points to a given point. The returned point ids (via * result) are sorted from closest to farthest. BuildLocator() should have * been called prior to this function. This method is thread safe if * BuildLocator() is directly or indirectly called from a single thread first. */ void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override; // ------------------------------------------------------------------------- // ---------------------------- Point Insertion ---------------------------- // ------------------------------------------------------------------------- /** * Initialize the point insertion process. points is an object, storing 3D * point coordinates, to which incremental point insertion put coordinates. * It is created and provided by an external VTK class. Argument bounds * represents the spatial bounding box, into which the points fall. In fact, * an adjusted version of the bounding box is used to build the octree to * make sure no any point (to be inserted) falls outside the octree. This * function is not thread safe. */ int InitPointInsertion(vtkPoints* points, const double bounds[6]) override; /** * Initialize the point insertion process. points is an object, storing 3D * point coordinates, to which incremental point insertion put coordinates. * It is created and provided by an external VTK class. Argument bounds * represents the spatial bounding box, into which the points fall. In fact, * an adjusted version of the bounding box is used to build the octree to * make sure no any point (to be inserted) falls outside the octree. Argument * estSize specifies the initial estimated size of the vtkPoints object. This * function is not thread safe. */ int InitPointInsertion(vtkPoints* points, const double bounds[6], vtkIdType estSize) override; /** * Determine whether or not a given point has been inserted into the octree. * Return the id of the already inserted point if true, otherwise return -1. * InitPointInsertion() should have been called in advance. */ vtkIdType IsInsertedPoint(const double x[3]) override; /** * Determine whether or not a given point has been inserted into the octree. * Return the id of the already inserted point if true, otherwise return -1. * InitPointInsertion() should have been called in advance. */ vtkIdType IsInsertedPoint(double x, double y, double z) override; /** * Insert a point to the octree unless there has been a duplicate point. * Whether the point is actually inserted (return 1) or not (return 0 upon a * rejection by an existing duplicate), the index of the point (either new * or the duplicate) is returned via pntId. Note that InitPointInsertion() * should have been called prior to this function. vtkPoints::InsertNextPoint() * is invoked. This method is not thread safe. */ int InsertUniquePoint(const double point[3], vtkIdType& pntId) override; /** * Insert a given point into the octree with a specified point index ptId. * InitPointInsertion() should have been called prior to this function. In * addition, IsInsertedPoint() should have been called in advance to ensure * that the given point has not been inserted unless point duplication is * allowed (Note that in this case, this function involves a repeated leaf * container location). vtkPoints::InsertPoint() is invoked. */ void InsertPoint(vtkIdType ptId, const double x[3]) override; /** * Insert a given point into the octree and return the point index. Note that * InitPointInsertion() should have been called prior to this function. In * addition, IsInsertedPoint() should have been called in advance to ensure * that the given point has not been inserted unless point duplication is * allowed (in this case, this function involves a repeated leaf container * location). vtkPoints::InsertNextPoint() is invoked. */ vtkIdType InsertNextPoint(const double x[3]) override; /** * "Insert" a point to the octree without any checking. Argument insert means * whether vtkPoints::InsertNextPoint() upon 1 is called or the point itself * is not inserted to the vtkPoints at all but instead only the point index is * inserted to a vtkIdList upon 0. For case 0, the point index needs to be * specified via pntId. For case 1, the actual point index is returned via * pntId. InitPointInsertion() should have been called. */ void InsertPointWithoutChecking(const double point[3], vtkIdType& pntId, int insert); vtkIncrementalOctreeNode* GetRoot() const { return OctreeRootNode; } /** * Returns the maximum level of the tree. If a tree has one node it returns 1 * else it returns the maximum level of its children plus 1. */ int GetNumberOfLevels(); protected: vtkIncrementalOctreePointLocator(); ~vtkIncrementalOctreePointLocator() override; private: vtkTypeBool BuildCubicOctree; int MaxPointsPerLeaf; double InsertTolerance2; double OctreeMaxDimSize; double FudgeFactor; vtkPoints* LocatorPoints; vtkIncrementalOctreeNode* OctreeRootNode; int NumberOfNodes; void BuildLocatorInternal() override; /** * Delete all descendants of a node. */ static void DeleteAllDescendants(vtkIncrementalOctreeNode* node); /** * Add the polygonal representation of a given node to the allocated vtkPoints * and vtkCellArray objects. */ static void AddPolys(vtkIncrementalOctreeNode* node, vtkPoints* points, vtkCellArray* polygs, vtkIntArray* nodeIndexes, vtkIdType& cellIndex, bool (*GetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data); /** * Given a point and a reference node, find the leaf containing the point. * Note the point is assumed to be inside or under the reference node. */ vtkIncrementalOctreeNode* GetLeafContainer(vtkIncrementalOctreeNode* node, const double pnt[3]); /** * Given a point (under check, either inside or outside the octree) and a leaf * node (not necessarily the container of this point), find the closest point * (possibly a duplicate of the point under check) within the node and return * the point index as well as the associated minimum squared distance (via dist2). * InitPointInsertion() or BuildLocator() should have been called. */ vtkIdType FindClosestPointInLeafNode( vtkIncrementalOctreeNode* leafNode, const double point[3], double* dist2); /** * This function may not be directly called. Please use the following two ones: * FindClosestPointInSphereWithTolerance() for point insertion and * FindClosestPointInSphereWithoutTolerance() for point location. Arguments * refDist2 and the initialization of minDist2 determine which version is used. * Given a point (under check) and an already-checked node (possibly nullptr), * find the closest point across a set of neighboring nodes within a specified * squared radius to the given point --- to perform an extended within-radius * inter-node search. The leaf (mask) node itself is excluded from the search * scope. Returned are the point index and the associated minimum squared * distance. InitPointInsertion() or BuildLocator() should have been called. */ vtkIdType FindClosestPointInSphere(const double point[3], double radius2, vtkIncrementalOctreeNode* maskNode, double* minDist2, const double* refDist2); // ------------------------------------------------------------------------- // ---------------------------- Point Location ---------------------------- // ------------------------------------------------------------------------- /** * This function is intended for point location, excluding point insertion. * Given a point (under check, covered or uncovered by the octree) and an * already-checked leaf node (maskNode, possibly nullptr), find the closest point * across a set of neighboring nodes within a specified squared radius to the * given point --- to perform an extended within-radius inter-node search. The * leaf (mask) node itself is excluded from the search scope. Returned are the * point index and the associated minimum squared distance (via minDist2). Note * that BuildLocator() should have been called. */ vtkIdType FindClosestPointInSphereWithoutTolerance( const double point[3], double radius2, vtkIncrementalOctreeNode* maskNode, double* minDist2); /** * Find all points, inside a given node, within a squared radius relative to * a given point. Returned are the associated un-sorted point indices (idList). * Note that BuildLocator() should have been called prior to this function. */ void FindPointsWithinSquaredRadius( vtkIncrementalOctreeNode* node, double radius2, const double point[3], vtkIdList* idList); // ------------------------------------------------------------------------- // ---------------------------- Point Insertion ---------------------------- // ------------------------------------------------------------------------- /** * This function is intended for point insertion, excluding point location. * Given a point (under check for insertion, must be covered by the octree) * and an already-checked node (maskNode, the container leaf node, possibly * nullptr if no any node has been checked), find the closest point across a set * of neighbor nodes within a specified squared radius radius2 to the given * point --- to perform an extended within-radius inter-node search. The leaf * (mask) node itself is excluded from the search scope. Returned are the point * index and the associated minimum squared distance (via minDist2). Note that * InitPointInsertion() should have been called. */ vtkIdType FindClosestPointInSphereWithTolerance( const double point[3], double radius2, vtkIncrementalOctreeNode* maskNode, double* minDist2); /** * Determine whether or not a given point has been inserted into the octree. * Return the id of the already inserted point if true, otherwise return -1. * Argument leafContainer is useful for access only if -1 is returned. This * returned parameter indicates the leaf node that contains the given point. * This function resorts to IsInsertedPointForZeroTolerance() for zero * tolerance insertion or IsInsertedPointForNonZeroTolerance() for non-zero * tolerance insertion. InitPointInsertion() should have been called. */ vtkIdType IsInsertedPoint(const double x[3], vtkIncrementalOctreeNode** leafContainer); /** * Determine whether or not a given point has been inserted into the octree. * Return the id of the already inserted point if true, otherwise return -1. * Argument leafContainer is useful for access only if -1 is returned. This * returned parameter indicates the leaf node that contains the given point. * This variant is invoked by IsInsertedPoint(x, vtkIncrementalOctreeNode **) * for zero tolerance insertion. InitPointInsertion() should have been called. */ vtkIdType IsInsertedPointForZeroTolerance( const double x[3], vtkIncrementalOctreeNode** leafContainer); /** * Determine whether or not a given point has been inserted into the octree. * Return the id of the already inserted point if true, otherwise return -1. * Argument leafContainer is useful for access only if -1 is returned. This * returned parameter indicates the leaf node that contains the given point. * This variant is invoked by IsInsertedPoint(x, vtkIncrementalOctreeNode **) * for non-zero tolerance insertion. InitPointInsertion() should have been * called in advance. */ vtkIdType IsInsertedPointForNonZeroTolerance( const double x[3], vtkIncrementalOctreeNode** leafContainer); /** * Given a point (under check for zero tolerance insertion) and a leaf node, * find its duplicate, if any, in the node and return the point index (-1 if * no duplicate is found). Note that the leaf node, already with at least one * point, is the container of the point under check. InitPointInsertion() * should have been called. */ vtkIdType FindDuplicatePointInLeafNode(vtkIncrementalOctreeNode* leafNode, const double point[3]); /** * Given a point (under check for zero tolerance insertion) and a leaf node, * find its duplicate, if any, in the node and return the point index (-1 if * no duplicate is found). Note that the leaf node, already with at least one * point, is the container of the point under check. This function is invoked * for type VTK_FLOAT. InitPointInsertion() should have been called. */ vtkIdType FindDuplicateFloatTypePointInVisitedLeafNode( vtkIncrementalOctreeNode* leafNode, const double point[3]); /** * Given a point (under check for zero tolerance insertion) and a leaf node, * find its duplicate, if any, in the node and return the point index (-1 if * no duplicate is found). Note that the leaf node, already with at least one * point, is the container of the point under check. This function is invoked * for type VTK_DOUBLE. InitPointInsertion() should have been called. */ vtkIdType FindDuplicateDoubleTypePointInVisitedLeafNode( vtkIncrementalOctreeNode* leafNode, const double point[3]); vtkIncrementalOctreePointLocator(const vtkIncrementalOctreePointLocator&) = delete; void operator=(const vtkIncrementalOctreePointLocator&) = delete; }; VTK_ABI_NAMESPACE_END #endif