0030655: Modeling Data - Provide interfaces for selection of the elements from BVH...
[occt.git] / src / BVH / BVH_Traverse.hxx
1 // Created by: Eugeny MALTCHIKOV
2 // Created on: 2019-04-17
3 // Copyright (c) 2019 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #ifndef _BVH_Traverse_Header
17 #define _BVH_Traverse_Header
18
19 #include <BVH_Box.hxx>
20 #include <BVH_Tree.hxx>
21
22 //! The classes implement the traverse of the BVH tree.
23 //!
24 //! There are two traverse methods implemented:
25 //! - Traverse of the single tree
26 //! - Parallel traverse of two trees
27 //!
28 //! To perform Selection of the elements from BVH_Tree using
29 //! the traverse methods implemented here it is
30 //! required to define Acceptance/Rejection rules in the
31 //! following methods:
32 //! - *RejectNode* - Node rejection by its bounding box.
33 //!   It is applied to both inner and outer nodes of the BVH tree.
34 //!   Optionally, the method should compute the metric for the node
35 //!   which will allow performing traverse faster by descending by the
36 //!   best branches.
37 //! - *Accept* - Element acceptance. It takes the index of the element
38 //!   of BVH tree. The access to the element itself should be performed
39 //!   through the set on which BVH is built.
40 //!   The *Accept* method implements the leaf node operation and usually
41 //!   defines the logic of the whole operation.
42 //! - *IsMetricBetter* - Compares the metrics of the nodes and returns
43 //!   true if the left metric is better than the right one.
44 //! - *RejectMetric* - Node rejection by the metric. It should compare
45 //!   the metric of the node with the global one and return true
46 //!   if the global metric is better than the given one.
47 //! - *Stop* - implements conditions to stop the tree descend if the necessary
48 //!   elements are already found.
49 //!
50 //! The selector of a single tree has an extra method which allows
51 //! accepting the whole branches without any further checks
52 //! (e.g. full inclusion test):
53 //! - *AcceptMetric* - basing on the metric of the node decides if the
54 //!   node may be accepted without any further checks.
55 //!
56 //! Two ways of selection are possible:
57 //! 1. Set the BVH set containing the tree and use the method Select()
58 //!    which allows using common interface for setting the BVH Set for accessing
59 //!    the BVH tree and elements in the Accept method.
60 //! 2. Keep the BVHSetType void, do not set the BVH set and use the
61 //!    method Select (const BVH_Tree<>&) which allows performing selection
62 //!    on the arbitrary BVH tree.
63 //!
64 //! Here is the example of usage of the traverse to find the point-triangulation
65 //! minimal distance.
66 //! ~~~~
67 //! // Structure to contain points of the triangle
68 //! struct Triangle
69 //! {
70 //!   Triangle() {}
71 //!   Triangle(const BVH_Vec3d& theNode1, 
72 //!            const BVH_Vec3d& theNode2,
73 //!            const BVH_Vec3d& theNode3)
74 //!     : Node1 (theNode1), Node2 (theNode2), Node3 (theNode3)
75 //!   {}
76 //!
77 //!   BVH_Vec3d Node1;
78 //!   BVH_Vec3d Node2;
79 //!   BVH_Vec3d Node3;
80 //! };
81 //!
82 //! // Selector for min point-triangulation distance
83 //! class BVH_PointTriangulationSqDist :
84 //!   public BVH_Distance<Standard_Real, 3, BVH_Vec3d, BVH_BoxSet<Standard_Real, 3, Triangle>>
85 //! {
86 //! public:
87 //!
88 //!   // Computes the distance from the point to bounding box 
89 //!   virtual Standard_Boolean RejectNode (const BVH_Vec3d& theCMin,
90 //!                                        const BVH_Vec3d& theCMax,
91 //!                                        Standard_Real& theDistance) const Standard_OVERRIDE
92 //!   {
93 //!     theDistance = BVH_Tools<Standard_Real, 3>::PointBoxSquareDistance (myObject, theCMin, theCMax);
94 //!     return RejectMetric (theDistance);
95 //!   }
96 //!
97 //!   // Computes the distance from the point to triangle
98 //!   virtual Standard_Boolean Accept (const Standard_Integer theIndex,
99 //!                                    const Standard_Real&) Standard_OVERRIDE
100 //!   {
101 //!     const Triangle& aTri = myBVHSet->Element (theIndex);
102 //!     Standard_Real aDist = BVH_Tools<Standard_Real, 3>::PointTriangleSquareDistance (myObject, aTri.Node1, aTri.Node2, aTri.Node3);
103 //!     if (aDist < myDistance)
104 //!     {
105 //!       myDistance = aDist;
106 //!       return Standard_True;
107 //!     }
108 //!     return Standard_False;
109 //!   }
110 //! };
111 //!
112 //! // Point to which the distance is required
113 //! BVH_Vec3d aPoint = ...;
114 //! // BVH Set containing triangulation
115 //! opencascade::handle<BVH_BoxSet<Standard_Real, 3, Triangle>> aTriangulationSet = ...;
116 //!
117 //! BVH_PointTriangulationSqDist aDistTool;
118 //! aDistTool.SetObject (aPoint);
119 //! aDistTool.SetBVHSet (aTriangulationSet.get());
120 //! aDistTool.ComputeDistance();
121 //! if (aDistTool.IsDone())
122 //! {
123 //!   Standard_Real aPointTriSqDist = aDistTool.Distance();
124 //! }
125 //!
126 //! ~~~~
127 //!
128
129 //! Abstract class implementing the base Traverse interface
130 //! required for selection of the elements from BVH tree.
131 //!
132 //! \tparam MetricType Type of metric to perform more optimal tree descend
133 template <class MetricType>
134 class BVH_BaseTraverse
135 {
136 public: //! @name Metrics comparison for choosing the best branch
137
138   //! Compares the two metrics and chooses the best one.
139   //! Returns true if the first metric is better than the second,
140   //! false otherwise.
141   virtual Standard_Boolean IsMetricBetter (const MetricType&,
142                                            const MetricType&) const
143   {
144     // Keep the left to right tree descend by default
145     return Standard_True;
146   }
147
148 public: //! @name Rejection of the node by metric
149
150   //! Rejects the node by the metric
151   virtual Standard_Boolean RejectMetric (const MetricType&) const
152   {
153     // Do not reject any nodes by metric by default
154     return Standard_False;
155   }
156
157 public: //! @name Condition to stop the descend
158
159   //! Returns the flag controlling the tree descend.
160   //! Returns true if the tree descend should be stopped.
161   virtual Standard_Boolean Stop() const
162   {
163     // Do not stop tree descend by default
164     return Standard_False;
165   }
166
167 protected: //! @name Constructors
168
169   //! Constructor
170   BVH_BaseTraverse() {}
171
172   //! Destructor
173   virtual ~BVH_BaseTraverse() {}
174 };
175
176 //! Abstract class implementing the traverse of the single binary tree.
177 //! Selection of the data from the tree is performed by the
178 //! rules defined in the Accept/Reject methods.
179 //! See description of the required methods in the comments above.
180 //!
181 //! \tparam NumType Numeric data type
182 //! \tparam Dimension Vector dimension
183 //! \tparam BVHSetType Type of set containing the BVH tree (required to access the elements by the index)
184 //! \tparam MetricType Type of metric to perform more optimal tree descend
185 template <class NumType, int Dimension, class BVHSetType = void, class MetricType = NumType>
186 class BVH_Traverse : public BVH_BaseTraverse<MetricType>
187 {
188 public: //! @name public types
189
190   typedef typename BVH_Box<NumType, Dimension>::BVH_VecNt BVH_VecNt;
191
192 public: //! @name Constructor
193
194   //! Constructor
195   BVH_Traverse()
196     : BVH_BaseTraverse<MetricType>(),
197       myBVHSet (NULL)
198   {}
199
200 public: //! @name Setting the set to access the elements and BVH tree
201
202   //! Sets the BVH Set containing the BVH tree
203   void SetBVHSet (BVHSetType* theBVHSet)
204   {
205     myBVHSet = theBVHSet;
206   }
207
208 public: //! @name Rules for Accept/Reject
209
210   //! Basing on the given metric, checks if the whole branch may be
211   //! accepted without any further checks.
212   //! Returns true if the metric is accepted, false otherwise.
213   virtual Standard_Boolean AcceptMetric (const MetricType&) const
214   {
215     // Do not accept the whole branch by default
216     return Standard_False;
217   }
218
219   //! Rejection of the node by bounding box.
220   //! Metric is computed to choose the best branch.
221   //! Returns true if the node should be rejected, false otherwise.
222   virtual Standard_Boolean RejectNode (const BVH_VecNt& theCornerMin,
223                                        const BVH_VecNt& theCornerMax,
224                                        MetricType& theMetric) const = 0;
225
226   //! Leaf element acceptance.
227   //! Metric of the parent leaf-node is passed to avoid the check on the
228   //! element and accept it unconditionally.
229   //! Returns true if the element has been accepted, false otherwise.
230   virtual Standard_Boolean Accept (const Standard_Integer theIndex,
231                                    const MetricType& theMetric) = 0;
232
233 public: //! @name Selection
234
235   //! Selection of the elements from the BVH tree by the
236   //! rules defined in Accept/Reject methods.
237   //! The method requires the BVHSet containing BVH tree to be set.
238   //! Returns the number of accepted elements.
239   Standard_Integer Select()
240   {
241     if (myBVHSet)
242     {
243       const opencascade::handle<BVH_Tree <NumType, Dimension>>& aBVH = myBVHSet->BVH();
244       return Select (aBVH);
245     }
246     return 0;
247   }
248
249   //! Performs selection of the elements from the BVH tree by the
250   //! rules defined in Accept/Reject methods.
251   //! Returns the number of accepted elements.
252   Standard_Integer Select (const opencascade::handle<BVH_Tree <NumType, Dimension>>& theBVH);
253
254 protected: //! @name Fields
255
256   BVHSetType* myBVHSet;
257 };
258
259 //! Abstract class implementing the parallel traverse of two binary trees.
260 //! Selection of the data from the trees is performed by the
261 //! rules defined in the Accept/Reject methods.
262 //! See description of the required methods in the comments above.
263 //!
264 //! \tparam NumType Numeric data type
265 //! \tparam Dimension Vector dimension
266 //! \tparam BVHSetType Type of set containing the BVH tree (required to access the elements by the index)
267 //! \tparam MetricType Type of metric to perform more optimal tree descend
268 template <class NumType, int Dimension, class BVHSetType = void, class MetricType = NumType>
269 class BVH_PairTraverse : public BVH_BaseTraverse<MetricType>
270 {
271 public: //! @name public types
272
273   typedef typename BVH_Box<NumType, Dimension>::BVH_VecNt BVH_VecNt;
274
275 public: //! @name Constructor
276
277   //! Constructor
278   BVH_PairTraverse()
279     : BVH_BaseTraverse<MetricType>(),
280       myBVHSet1 (NULL),
281       myBVHSet2 (NULL)
282   {
283   }
284
285 public: //! @name Setting the sets to access the elements and BVH trees
286
287   //! Sets the BVH Sets containing the BVH trees
288   void SetBVHSets (BVHSetType* theBVHSet1,
289                    BVHSetType* theBVHSet2)
290   {
291     myBVHSet1 = theBVHSet1;
292     myBVHSet2 = theBVHSet2;
293   }
294
295 public: //! @name Rules for Accept/Reject
296
297   //! Rejection of the pair of nodes by bounding boxes.
298   //! Metric is computed to choose the best branch.
299   //! Returns true if the pair of nodes should be rejected, false otherwise.
300   virtual Standard_Boolean RejectNode (const BVH_VecNt& theCornerMin1,
301                                        const BVH_VecNt& theCornerMax1,
302                                        const BVH_VecNt& theCornerMin2,
303                                        const BVH_VecNt& theCornerMax2,
304                                        MetricType& theMetric) const = 0;
305
306   //! Leaf element acceptance.
307   //! Returns true if the pair of elements is accepted, false otherwise.
308   virtual Standard_Boolean Accept (const Standard_Integer theIndex1,
309                                    const Standard_Integer theIndex2) = 0;
310
311 public: //! @name Selection
312
313   //! Selection of the pairs of elements of two BVH trees by the
314   //! rules defined in Accept/Reject methods.
315   //! The method requires the BVHSets containing BVH trees to be set.
316   //! Returns the number of accepted pairs of elements.
317   Standard_Integer Select()
318   {
319     if (myBVHSet1 && myBVHSet2)
320     {
321       const opencascade::handle <BVH_Tree <NumType, Dimension> >& aBVH1 = myBVHSet1->BVH();
322       const opencascade::handle <BVH_Tree <NumType, Dimension> >& aBVH2 = myBVHSet2->BVH();
323       return Select (aBVH1, aBVH2);
324     }
325     return 0;
326   }
327
328   //! Performs selection of the elements from two BVH trees by the
329   //! rules defined in Accept/Reject methods.
330   //! Returns the number of accepted pairs of elements.
331   Standard_Integer Select (const opencascade::handle<BVH_Tree <NumType, Dimension>>& theBVH1,
332                            const opencascade::handle<BVH_Tree <NumType, Dimension>>& theBVH2);
333
334 protected: //! @name Fields
335
336   BVHSetType* myBVHSet1;
337   BVHSetType* myBVHSet2;
338
339 };
340
341 #include <BVH_Traverse.lxx>
342
343 #endif // _BVH_Traverse_Header