0030655: Modeling Data - Provide interfaces for selection of the elements from BVH...
[occt.git] / src / BVH / BVH_Traverse.lxx
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 namespace
17 {
18   //! Auxiliary structure for keeping the nodes to process
19   template<class MetricType> struct BVH_NodeInStack
20   {
21     //! Constructor
22     BVH_NodeInStack (const Standard_Integer theNodeID = 0,
23                      const MetricType& theMetric = MetricType())
24       : NodeID (theNodeID), Metric (theMetric)
25     {}
26
27     // Fields
28     Standard_Integer NodeID; //!< Id of the node in the BVH tree
29     MetricType Metric;       //!< Metric computed for the node
30   };
31 }
32
33 // =======================================================================
34 // function : BVH_Traverse::Select
35 // purpose  :
36 // =======================================================================
37 template <class NumType, int Dimension, class BVHSetType, class MetricType>
38 Standard_Integer BVH_Traverse <NumType, Dimension, BVHSetType, MetricType>::Select
39   (const opencascade::handle<BVH_Tree <NumType, Dimension>>& theBVH)
40 {
41   if (theBVH.IsNull())
42     return 0;
43
44   if (theBVH->NodeInfoBuffer().empty())
45     return 0;
46
47   // Create stack
48   BVH_NodeInStack<MetricType> aStack[BVH_Constants_MaxTreeDepth];
49
50   BVH_NodeInStack<MetricType> aNode (0);         // Currently processed node, starting with the root node
51   BVH_NodeInStack<MetricType> aPrevNode = aNode; // Previously processed node
52
53   Standard_Integer aHead = -1;      // End of the stack
54   Standard_Integer aNbAccepted = 0; // Counter for accepted elements
55
56   for (;;)
57   {
58     const BVH_Vec4i& aData = theBVH->NodeInfoBuffer()[aNode.NodeID];
59
60     if (aData.x() == 0)
61     {
62       // Inner node:
63       // - check the metric of the node
64       // - test the children of the node
65
66       if (!this->AcceptMetric (aNode.Metric))
67       {
68         // Test the left branch
69         MetricType aMetricLft;
70         Standard_Boolean isGoodLft = !RejectNode (theBVH->MinPoint (aData.y()),
71                                                   theBVH->MaxPoint (aData.y()),
72                                                   aMetricLft);
73         if (this->Stop())
74           return aNbAccepted;
75
76         // Test the right branch
77         MetricType aMetricRgh;
78         Standard_Boolean isGoodRgh = !RejectNode (theBVH->MinPoint (aData.z()),
79                                                   theBVH->MaxPoint (aData.z()),
80                                                   aMetricRgh);
81         if (this->Stop())
82           return aNbAccepted;
83
84         if (isGoodLft && isGoodRgh)
85         {
86           // Chose the branch with the best metric to be processed next,
87           // put the other branch in the stack
88           if (this->IsMetricBetter (aMetricLft, aMetricRgh))
89           {
90             aNode           = BVH_NodeInStack<MetricType> (aData.y(), aMetricLft);
91             aStack[++aHead] = BVH_NodeInStack<MetricType> (aData.z(), aMetricRgh);
92           }
93           else
94           {
95             aNode           = BVH_NodeInStack<MetricType> (aData.z(), aMetricRgh);
96             aStack[++aHead] = BVH_NodeInStack<MetricType> (aData.y(), aMetricLft);
97           }
98         }
99         else if (isGoodLft || isGoodRgh)
100         {
101           aNode = isGoodLft ?
102             BVH_NodeInStack<MetricType> (aData.y(), aMetricLft) :
103             BVH_NodeInStack<MetricType> (aData.z(), aMetricRgh);
104         }
105       }
106       else
107       {
108         // Both children will be accepted
109         // Take one for processing, put the other into stack
110         aNode           = BVH_NodeInStack<MetricType> (aData.y(), aNode.Metric);
111         aStack[++aHead] = BVH_NodeInStack<MetricType> (aData.z(), aNode.Metric);
112       }
113     }
114     else
115     {
116       // Leaf node - apply the leaf node operation to each element
117       for (Standard_Integer iN = aData.y(); iN <= aData.z(); ++iN)
118       {
119         if (Accept (iN, aNode.Metric))
120           ++aNbAccepted;
121
122         if (this->Stop())
123           return aNbAccepted;
124       }
125     }
126
127     if (aNode.NodeID == aPrevNode.NodeID)
128     {
129       if (aHead < 0)
130         return aNbAccepted;
131
132       // Remove the nodes with bad metric from the stack
133       aNode = aStack[aHead--];
134       while (this->RejectMetric (aNode.Metric))
135       {
136         if (aHead < 0)
137           return aNbAccepted;
138         aNode = aStack[aHead--];
139       }
140     }
141
142     aPrevNode = aNode;
143   }
144 }
145
146 namespace
147 {
148   //! Auxiliary structure for keeping the pair of nodes to process
149   template<class MetricType> struct BVH_PairNodesInStack
150   {
151     //! Constructor
152     BVH_PairNodesInStack (const Standard_Integer theNodeID1 = 0,
153                           const Standard_Integer theNodeID2 = 0,
154                           const MetricType& theMetric = MetricType())
155       : NodeID1 (theNodeID1), NodeID2 (theNodeID2), Metric (theMetric)
156     {}
157
158     // Fields
159     Standard_Integer NodeID1; //!< Id of the node in the first BVH tree
160     Standard_Integer NodeID2; //!< Id of the node in the second BVH tree
161     MetricType Metric;        //!< Metric computed for the pair of nodes
162   };
163 }
164
165 // =======================================================================
166 // function : BVH_PairTraverse::Select
167 // purpose  :
168 // =======================================================================
169 template <class NumType, int Dimension, class BVHSetType, class MetricType>
170 Standard_Integer BVH_PairTraverse<NumType, Dimension, BVHSetType, MetricType>::Select
171   (const opencascade::handle<BVH_Tree <NumType, Dimension>>& theBVH1,
172    const opencascade::handle<BVH_Tree <NumType, Dimension>>& theBVH2)
173 {
174   if (theBVH1.IsNull() || theBVH2.IsNull())
175     return 0;
176
177   const BVH_Array4i& aBVHNodes1 = theBVH1->NodeInfoBuffer();
178   const BVH_Array4i& aBVHNodes2 = theBVH2->NodeInfoBuffer();
179   if (aBVHNodes1.empty() || aBVHNodes2.empty())
180     return 0;
181
182   // On each iteration we can add max four new pairs of nodes to process.
183   // One of these pairs goes directly to processing, while others
184   // are put in the stack. So the max number of pairs in the stack is
185   // the max tree depth multiplied by 3.
186   const Standard_Integer aMaxNbPairsInStack = 3 * BVH_Constants_MaxTreeDepth;
187
188   // Stack of pairs of nodes to process
189   BVH_PairNodesInStack<MetricType> aStack[aMaxNbPairsInStack];
190
191   // Currently processed pair, starting with the root nodes
192   BVH_PairNodesInStack<MetricType> aNode (0, 0);
193   // Previously processed pair
194   BVH_PairNodesInStack<MetricType> aPrevNode = aNode;
195   // End of the stack
196   Standard_Integer aHead = -1;
197   // Counter for accepted elements
198   Standard_Integer aNbAccepted = 0;
199
200   for (;;)
201   {
202     const BVH_Vec4i& aData1 = aBVHNodes1[aNode.NodeID1];
203     const BVH_Vec4i& aData2 = aBVHNodes2[aNode.NodeID2];
204
205     if (aData1.x() != 0 && aData2.x() != 0)
206     {
207       // Outer/Outer
208       for (Standard_Integer iN1 = aData1.y(); iN1 <= aData1.z(); ++iN1)
209       {
210         for (Standard_Integer iN2 = aData2.y(); iN2 <= aData2.z(); ++iN2)
211         {
212           if (Accept (iN1, iN2))
213             ++aNbAccepted;
214
215           if (this->Stop())
216             return aNbAccepted;
217         }
218       }
219     }
220     else
221     {
222       BVH_PairNodesInStack<MetricType> aPairs[4];
223       Standard_Integer aNbPairs = 0;
224
225       if (aData1.x() == 0 && aData2.x() == 0)
226       {
227         // Inner/Inner
228         aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.y(), aData2.y());
229         aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.y(), aData2.z());
230         aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.z(), aData2.y());
231         aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.z(), aData2.z());
232       }
233       else if (aData1.x() == 0)
234       {
235         // Inner/Outer
236         aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.y(), aNode.NodeID2);
237         aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.z(), aNode.NodeID2);
238       }
239       else if (aData2.x() == 0)
240       {
241         // Outer/Inner
242         aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aNode.NodeID1, aData2.y());
243         aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aNode.NodeID1, aData2.z());
244       }
245
246       BVH_PairNodesInStack<MetricType> aKeptPairs[4];
247       Standard_Integer aNbKept = 0;
248       // Compute metrics for the nodes
249       for (Standard_Integer iPair = 0; iPair < aNbPairs; ++iPair)
250       {
251         const Standard_Boolean isPairRejected =
252           RejectNode (theBVH1->MinPoint (aPairs[iPair].NodeID1), theBVH1->MaxPoint (aPairs[iPair].NodeID1),
253                       theBVH2->MinPoint (aPairs[iPair].NodeID2), theBVH2->MaxPoint (aPairs[iPair].NodeID2),
254                       aPairs[iPair].Metric);
255         if (!isPairRejected)
256         {
257           // Put the item into the sorted array of pairs
258           Standard_Integer iSort = aNbKept;
259           while (iSort > 0 && this->IsMetricBetter (aPairs[iPair].Metric, aKeptPairs[iSort - 1].Metric))
260           {
261             aKeptPairs[iSort] = aKeptPairs[iSort - 1];
262             --iSort;
263           }
264           aKeptPairs[iSort] = aPairs[iPair];
265           aNbKept++;
266         }
267       }
268
269       if (aNbKept > 0)
270       {
271         aNode = aKeptPairs[0];
272
273         for (Standard_Integer iPair = 1; iPair < aNbKept; ++iPair)
274         {
275           aStack[++aHead] = aKeptPairs[iPair];
276         }
277       }
278     }
279
280     if (aNode.NodeID1 == aPrevNode.NodeID1 &&
281         aNode.NodeID2 == aPrevNode.NodeID2)
282     {
283       // No pairs to add
284       if (aHead < 0)
285         return aNbAccepted;
286
287       // Remove the pairs of nodes with bad metric from the stack
288       aNode = aStack[aHead--];
289       while (this->RejectMetric (aNode.Metric))
290       {
291         if (aHead < 0)
292           return aNbAccepted;
293         aNode = aStack[aHead--];
294       }
295     }
296
297     aPrevNode = aNode;
298   }
299 }