1 /*========================================================================= 2 3 Program: Visualization Toolkit 4 Module: vtkOverlappingCellsDetector.h 5 6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen 7 All rights reserved. 8 See Copyright.txt or http://www.kitware.com/Copyright.htm for details. 9 10 This software is distributed WITHOUT ANY WARRANTY; without even 11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 12 PURPOSE. See the above copyright notice for more information. 13 14 =========================================================================*/ 15 /** 16 * @class vtkOverlappingCellsDetector 17 * @brief Exposes how many cells each cell of the input collide. 18 * 19 * This filter performs a cell collision detection between the cells of the input. 20 * This detection takes the form of a cell array of double. Its name can be 21 * reached from the static string attribute 22 * vtkOverlappingCellsDetector::NumberOfOverlapsPerCell. 23 * 24 * To detect collisions, coarse bounding spheres are estimated for each cell of the input. 25 * The center of those spheres is stored in a point cloud which is used to find potential 26 * colliding cells candidates, querying with twice the bounding sphere radius to ensure 27 * we do not miss other bouding sphere centers. Duplicate intersections might appear during 28 * this process, so a sphere id map is stored to avoid adding already added overlapping cell ids. 29 * 30 * This filter works in a multi-process environment. When so, each cell of the input 31 * whose bounding sphere and bounding box intersects another process is added in 32 * a temporary `vtkUnstructuredGrid` being sent to this process. Cell collision 33 * is then performed, and the collision id map is sent back. This map is then 34 * read to look if any of those cells were not already counted (local process 35 * could have spotted the same collision from 36 * the cells sent by the other process indeed). One cell id collision map is stored 37 * per neighbor process to avoid cell id collision. 38 * 39 * The user can set a `Tolerance` parameter. It is set by default to zero. When 40 * it is equal to zero or is lower to floating point precision, 41 * then floating point precision is used to compute cell 42 * overlaps. If it is not set to zero, then each cells are deflated by `0.5 * 43 * Tolerance` before the overlaps are computed. The deflation is computed using 44 * `vtkCell::Inflate` with a negative parameter. 45 */ 46 47 #ifndef vtkOverlappingCellsDetector_h 48 #define vtkOverlappingCellsDetector_h 49 50 #include "vtkFiltersParallelDIY2Module.h" // for export macros 51 #include "vtkPassInputTypeAlgorithm.h" 52 53 #include "vtkBoundingBox.h" // For DetectOverlappingCells 54 55 #include <set> // For DetectOverlappingCells 56 #include <unordered_map> // For DetectOverlappingCells 57 #include <vector> // For DetectOverlappingCells 58 59 class vtkDataSet; 60 class vtkMultiProcessController; 61 class vtkPointSet; 62 63 class VTKFILTERSPARALLELDIY2_EXPORT vtkOverlappingCellsDetector : public vtkPassInputTypeAlgorithm 64 { 65 public: 66 static vtkOverlappingCellsDetector* New(); 67 vtkTypeMacro(vtkOverlappingCellsDetector, vtkPassInputTypeAlgorithm); 68 void PrintSelf(ostream& os, vtkIndent indent) override; 69 70 ///@{ 71 /** 72 * Get/Set the controller to use. By default 73 * vtkMultiProcessController::GlobalController will be used. 74 */ 75 void SetController(vtkMultiProcessController*); 76 vtkGetObjectMacro(Controller, vtkMultiProcessController); 77 ///@} 78 79 ///@{ 80 /** 81 * Getter / Setter for the Tolerance parameter. 82 */ 83 vtkGetMacro(Tolerance, double); 84 vtkSetMacro(Tolerance, double); 85 ///@} 86 87 ///@{ 88 /** 89 * Getter / Setter for the name of the output array counting cell collisions. 90 * This array is a cell array. 91 */ 92 vtkGetStringMacro(NumberOfOverlapsPerCellArrayName); 93 vtkSetStringMacro(NumberOfOverlapsPerCellArrayName); 94 ///@} 95 96 protected: 97 vtkOverlappingCellsDetector(); 98 ~vtkOverlappingCellsDetector() override; 99 100 int FillInputPortInformation(int port, vtkInformation* info) override; 101 102 int RequestData(vtkInformation*, vtkInformationVector**, vtkInformationVector*) override; 103 104 /** 105 * Main pipeline. Performs cell collision detection in a MPI aware environment. 106 */ 107 int ExposeOverlappingCellsAmongBlocks(std::vector<vtkPointSet*>& outputs); 108 109 /** 110 * Method performing the cell detection. 111 * There are 2 main types of inputs: query inputs, as well as inputs where to search. 112 * Points in point clouds represent bounding spheres of corresponding cell data set. 113 * Each point is associated with a radius. 114 * Bounding boxes must match the bounding boxes of corresponding cells in data sets. 115 * 116 * The algorithm goes as follows: 117 * - For each query point in queryPointCloud, a neighborhood is searched in pointCloud 118 * - For each neighbor found, a collision test is performed between query cell associated 119 * to query point and each cells associated with points found in the neighborhood. 120 * - If the test is positive, arrays of double associated with both datasets are 121 * incremented 122 * 123 * Last input CollisionListMaps is here to store the list of intersected cell ids from the query, 124 * mapped to the id of input cellDataSet. This object is used to avoid double counting 125 * collisions when sending back collision information to every block. 126 * 127 * This function can be called with queryCellDataSet and queryDataSet pointing to the same 128 * object in memory. 129 * 130 * Precondition: cellDataSet MUST have the cell array named NumberOfOverlapsPerCellArrayName() 131 */ 132 bool DetectOverlappingCells(vtkDataSet* queryCellDataSet, vtkPointSet* queryPointCloud, 133 const std::vector<vtkBoundingBox>& queryCellBoundingBoxes, vtkDataSet* cellDataSet, 134 vtkPointSet* pointCloud, const std::vector<vtkBoundingBox>& cellBoundingBoxes, 135 std::unordered_map<vtkIdType, std::set<vtkIdType>>& collisionListMap, 136 bool updateProgress = false); 137 138 /** 139 * Local controller. 140 */ 141 vtkMultiProcessController* Controller; 142 143 /** 144 * Output cell scalar field counting the number of cells that each cell was found to collide. 145 */ 146 char* NumberOfOverlapsPerCellArrayName; 147 148 /** 149 * Tolerance for overlap detections. If its value is lower than floating point 150 * precision, then floating point 151 * precision is used as bound error for overlaps. If not, then cells are 152 * deflated by 0.5 * Tolerance before checking the overlaps. Deflating a cell 153 * by `x` means translating inward its edges / faces by a distance `x` following 154 * the edge's / face's normal direction. `vtkCell::Inflate` is used with a 155 * negative parameter. 156 */ 157 double Tolerance; 158 159 private: 160 vtkOverlappingCellsDetector(const vtkOverlappingCellsDetector&) = delete; 161 void operator=(const vtkOverlappingCellsDetector&) = delete; 162 }; 163 164 #endif 165