Warning, /include/opencascade/BVH_Traverse.lxx is written in an unsupported language. File is not indexed.
0001 // Created by: Eugeny MALTCHIKOV
0002 // Created on: 2019-04-17
0003 // Copyright (c) 2019 OPEN CASCADE SAS
0004 //
0005 // This file is part of Open CASCADE Technology software library.
0006 //
0007 // This library is free software; you can redistribute it and/or modify it under
0008 // the terms of the GNU Lesser General Public License version 2.1 as published
0009 // by the Free Software Foundation, with special exception defined in the file
0010 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
0011 // distribution for complete text of the license and disclaimer of any warranty.
0012 //
0013 // Alternatively, this file may be used under the terms of Open CASCADE
0014 // commercial license or contractual agreement.
0015
0016 #include <Standard_Assert.hxx>
0017
0018 //=================================================================================================
0019
0020 template <class NumType, int Dimension, class BVHSetType, class MetricType>
0021 int BVH_Traverse<NumType, Dimension, BVHSetType, MetricType>::Select(
0022 const opencascade::handle<BVH_Tree<NumType, Dimension>>& theBVH)
0023 {
0024 if (theBVH.IsNull())
0025 return 0;
0026
0027 const BVH_Array4i& aBVHNodes = theBVH->NodeInfoBuffer();
0028 if (aBVHNodes.IsEmpty())
0029 return 0;
0030
0031 // Create stack
0032 BVH_NodeInStack aStack[BVH_Constants_MaxTreeDepth];
0033
0034 // clang-format off
0035 BVH_NodeInStack aNode (0); // Currently processed node, starting with the root node
0036 // clang-format on
0037 BVH_NodeInStack aPrevNode = aNode; // Previously processed node
0038
0039 int aHead = -1; // End of the stack
0040 int aNbAccepted = 0; // Counter for accepted elements
0041
0042 for (;;)
0043 {
0044 const BVH_Vec4i& aData = aBVHNodes[aNode.NodeID];
0045
0046 if (aData.x() == 0)
0047 {
0048 // Inner node:
0049 // - check the metric of the node
0050 // - test the children of the node
0051
0052 if (!this->AcceptMetric(aNode.Metric))
0053 {
0054 // Test the left branch
0055 MetricType aMetricLft;
0056 bool isGoodLft =
0057 !RejectNode(theBVH->MinPoint(aData.y()), theBVH->MaxPoint(aData.y()), aMetricLft);
0058 if (this->Stop())
0059 return aNbAccepted;
0060
0061 // Test the right branch
0062 MetricType aMetricRgh;
0063 bool isGoodRgh =
0064 !RejectNode(theBVH->MinPoint(aData.z()), theBVH->MaxPoint(aData.z()), aMetricRgh);
0065 if (this->Stop())
0066 return aNbAccepted;
0067
0068 if (isGoodLft && isGoodRgh)
0069 {
0070 // Chose the branch with the best metric to be processed next,
0071 // put the other branch in the stack
0072 Standard_ASSERT_RAISE(aHead < BVH_Constants_MaxTreeDepth - 1,
0073 "Error! BVH stack overflow");
0074 if (this->IsMetricBetter(aMetricLft, aMetricRgh))
0075 {
0076 aNode = BVH_NodeInStack(aData.y(), aMetricLft);
0077 aStack[++aHead] = BVH_NodeInStack(aData.z(), aMetricRgh);
0078 }
0079 else
0080 {
0081 aNode = BVH_NodeInStack(aData.z(), aMetricRgh);
0082 aStack[++aHead] = BVH_NodeInStack(aData.y(), aMetricLft);
0083 }
0084 }
0085 else if (isGoodLft || isGoodRgh)
0086 {
0087 aNode = isGoodLft ? BVH_NodeInStack(aData.y(), aMetricLft)
0088 : BVH_NodeInStack(aData.z(), aMetricRgh);
0089 }
0090 }
0091 else
0092 {
0093 // Both children will be accepted
0094 // Take one for processing, put the other into stack
0095 Standard_ASSERT_RAISE(aHead < BVH_Constants_MaxTreeDepth - 1, "Error! BVH stack overflow");
0096 aNode = BVH_NodeInStack(aData.y(), aNode.Metric);
0097 aStack[++aHead] = BVH_NodeInStack(aData.z(), aNode.Metric);
0098 }
0099 }
0100 else
0101 {
0102 // Leaf node - apply the leaf node operation to each element
0103 for (int iN = aData.y(); iN <= aData.z(); ++iN)
0104 {
0105 if (Accept(iN, aNode.Metric))
0106 ++aNbAccepted;
0107
0108 if (this->Stop())
0109 return aNbAccepted;
0110 }
0111 }
0112
0113 if (aNode.NodeID == aPrevNode.NodeID)
0114 {
0115 if (aHead < 0)
0116 return aNbAccepted;
0117
0118 // Remove the nodes with bad metric from the stack
0119 aNode = aStack[aHead--];
0120 while (this->RejectMetric(aNode.Metric))
0121 {
0122 if (aHead < 0)
0123 return aNbAccepted;
0124 aNode = aStack[aHead--];
0125 }
0126 }
0127
0128 aPrevNode = aNode;
0129 }
0130 }
0131
0132 //=================================================================================================
0133
0134 template <class NumType, int Dimension, class BVHSetType, class MetricType>
0135 int BVH_PairTraverse<NumType, Dimension, BVHSetType, MetricType>::Select(
0136 const opencascade::handle<BVH_Tree<NumType, Dimension>>& theBVH1,
0137 const opencascade::handle<BVH_Tree<NumType, Dimension>>& theBVH2)
0138 {
0139 if (theBVH1.IsNull() || theBVH2.IsNull())
0140 return 0;
0141
0142 const BVH_Array4i& aBVHNodes1 = theBVH1->NodeInfoBuffer();
0143 const BVH_Array4i& aBVHNodes2 = theBVH2->NodeInfoBuffer();
0144 if (aBVHNodes1.IsEmpty() || aBVHNodes2.IsEmpty())
0145 return 0;
0146
0147 // On each iteration we can add max four new pairs of nodes to process.
0148 // One of these pairs goes directly to processing, while others
0149 // are put in the stack. So the max number of pairs in the stack is
0150 // the max tree depth multiplied by 3.
0151 const int aMaxNbPairsInStack = 3 * BVH_Constants_MaxTreeDepth;
0152
0153 // Stack of pairs of nodes to process
0154 BVH_PairNodesInStack aStack[aMaxNbPairsInStack];
0155
0156 // Currently processed pair, starting with the root nodes
0157 BVH_PairNodesInStack aNode(0, 0);
0158 // Previously processed pair
0159 BVH_PairNodesInStack aPrevNode = aNode;
0160 // End of the stack
0161 int aHead = -1;
0162 // Counter for accepted elements
0163 int aNbAccepted = 0;
0164
0165 for (;;)
0166 {
0167 const BVH_Vec4i& aData1 = aBVHNodes1[aNode.NodeID1];
0168 const BVH_Vec4i& aData2 = aBVHNodes2[aNode.NodeID2];
0169
0170 if (aData1.x() != 0 && aData2.x() != 0)
0171 {
0172 // Outer/Outer - both nodes are leaves
0173 // Check if the leaf node bounding boxes overlap before testing elements
0174 MetricType aMetric;
0175 bool isRejected = RejectNode(theBVH1->MinPoint(aNode.NodeID1),
0176 theBVH1->MaxPoint(aNode.NodeID1),
0177 theBVH2->MinPoint(aNode.NodeID2),
0178 theBVH2->MaxPoint(aNode.NodeID2),
0179 aMetric);
0180
0181 if (!isRejected)
0182 {
0183 // Bounding boxes overlap, test all element pairs
0184 for (int iN1 = aData1.y(); iN1 <= aData1.z(); ++iN1)
0185 {
0186 for (int iN2 = aData2.y(); iN2 <= aData2.z(); ++iN2)
0187 {
0188 if (Accept(iN1, iN2))
0189 ++aNbAccepted;
0190
0191 if (this->Stop())
0192 return aNbAccepted;
0193 }
0194 }
0195 }
0196 }
0197 else
0198 {
0199 BVH_PairNodesInStack aPairs[4];
0200 int aNbPairs = 0;
0201
0202 if (aData1.x() == 0 && aData2.x() == 0)
0203 {
0204 // Inner/Inner
0205 aPairs[aNbPairs++] = BVH_PairNodesInStack(aData1.y(), aData2.y());
0206 aPairs[aNbPairs++] = BVH_PairNodesInStack(aData1.y(), aData2.z());
0207 aPairs[aNbPairs++] = BVH_PairNodesInStack(aData1.z(), aData2.y());
0208 aPairs[aNbPairs++] = BVH_PairNodesInStack(aData1.z(), aData2.z());
0209 }
0210 else if (aData1.x() == 0)
0211 {
0212 // Inner/Outer
0213 aPairs[aNbPairs++] = BVH_PairNodesInStack(aData1.y(), aNode.NodeID2);
0214 aPairs[aNbPairs++] = BVH_PairNodesInStack(aData1.z(), aNode.NodeID2);
0215 }
0216 else if (aData2.x() == 0)
0217 {
0218 // Outer/Inner
0219 aPairs[aNbPairs++] = BVH_PairNodesInStack(aNode.NodeID1, aData2.y());
0220 aPairs[aNbPairs++] = BVH_PairNodesInStack(aNode.NodeID1, aData2.z());
0221 }
0222
0223 BVH_PairNodesInStack aKeptPairs[4];
0224 int aNbKept = 0;
0225 // Compute metrics for the nodes
0226 for (int iPair = 0; iPair < aNbPairs; ++iPair)
0227 {
0228 const bool isPairRejected = RejectNode(theBVH1->MinPoint(aPairs[iPair].NodeID1),
0229 theBVH1->MaxPoint(aPairs[iPair].NodeID1),
0230 theBVH2->MinPoint(aPairs[iPair].NodeID2),
0231 theBVH2->MaxPoint(aPairs[iPair].NodeID2),
0232 aPairs[iPair].Metric);
0233 if (!isPairRejected)
0234 {
0235 // Put the item into the sorted array of pairs
0236 int iSort = aNbKept;
0237 while (iSort > 0
0238 && this->IsMetricBetter(aPairs[iPair].Metric, aKeptPairs[iSort - 1].Metric))
0239 {
0240 aKeptPairs[iSort] = aKeptPairs[iSort - 1];
0241 --iSort;
0242 }
0243 aKeptPairs[iSort] = aPairs[iPair];
0244 ++aNbKept;
0245 }
0246 }
0247
0248 if (aNbKept > 0)
0249 {
0250 aNode = aKeptPairs[0];
0251
0252 for (int iPair = 1; iPair < aNbKept; ++iPair)
0253 {
0254 Standard_ASSERT_RAISE(aHead < aMaxNbPairsInStack - 1, "Error! BVH pair stack overflow");
0255 aStack[++aHead] = aKeptPairs[iPair];
0256 }
0257 }
0258 }
0259
0260 if (aNode.NodeID1 == aPrevNode.NodeID1 && aNode.NodeID2 == aPrevNode.NodeID2)
0261 {
0262 // No pairs to add
0263 if (aHead < 0)
0264 return aNbAccepted;
0265
0266 // Remove the pairs of nodes with bad metric from the stack
0267 aNode = aStack[aHead--];
0268 while (this->RejectMetric(aNode.Metric))
0269 {
0270 if (aHead < 0)
0271 return aNbAccepted;
0272 aNode = aStack[aHead--];
0273 }
0274 }
0275
0276 aPrevNode = aNode;
0277 }
0278 }
