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