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 namespace
0017 {
0018 //! Auxiliary structure for keeping the nodes to process
0019 template <class MetricType>
0020 struct BVH_NodeInStack
0021 {
0022 //! Constructor
0023 BVH_NodeInStack(const Standard_Integer theNodeID = 0, const MetricType& theMetric = MetricType())
0024 : NodeID(theNodeID),
0025 Metric(theMetric)
0026 {
0027 }
0028
0029 // Fields
0030 Standard_Integer NodeID; //!< Id of the node in the BVH tree
0031 MetricType Metric; //!< Metric computed for the node
0032 };
0033 } // namespace
0034
0035 // =======================================================================
0036 // function : BVH_Traverse::Select
0037 // purpose :
0038 // =======================================================================
0039 template <class NumType, int Dimension, class BVHSetType, class MetricType>
0040 Standard_Integer BVH_Traverse<NumType, Dimension, BVHSetType, MetricType>::Select(
0041 const opencascade::handle<BVH_Tree<NumType, Dimension>>& theBVH)
0042 {
0043 if (theBVH.IsNull())
0044 return 0;
0045
0046 if (theBVH->NodeInfoBuffer().empty())
0047 return 0;
0048
0049 // Create stack
0050 BVH_NodeInStack<MetricType> aStack[BVH_Constants_MaxTreeDepth];
0051
0052 // clang-format off
0053 BVH_NodeInStack<MetricType> aNode (0); // Currently processed node, starting with the root node
0054 // clang-format on
0055 BVH_NodeInStack<MetricType> aPrevNode = aNode; // Previously processed node
0056
0057 Standard_Integer aHead = -1; // End of the stack
0058 Standard_Integer aNbAccepted = 0; // Counter for accepted elements
0059
0060 for (;;)
0061 {
0062 const BVH_Vec4i& aData = theBVH->NodeInfoBuffer()[aNode.NodeID];
0063
0064 if (aData.x() == 0)
0065 {
0066 // Inner node:
0067 // - check the metric of the node
0068 // - test the children of the node
0069
0070 if (!this->AcceptMetric(aNode.Metric))
0071 {
0072 // Test the left branch
0073 MetricType aMetricLft;
0074 Standard_Boolean isGoodLft =
0075 !RejectNode(theBVH->MinPoint(aData.y()), theBVH->MaxPoint(aData.y()), aMetricLft);
0076 if (this->Stop())
0077 return aNbAccepted;
0078
0079 // Test the right branch
0080 MetricType aMetricRgh;
0081 Standard_Boolean isGoodRgh =
0082 !RejectNode(theBVH->MinPoint(aData.z()), theBVH->MaxPoint(aData.z()), aMetricRgh);
0083 if (this->Stop())
0084 return aNbAccepted;
0085
0086 if (isGoodLft && isGoodRgh)
0087 {
0088 // Chose the branch with the best metric to be processed next,
0089 // put the other branch in the stack
0090 if (this->IsMetricBetter(aMetricLft, aMetricRgh))
0091 {
0092 aNode = BVH_NodeInStack<MetricType>(aData.y(), aMetricLft);
0093 aStack[++aHead] = BVH_NodeInStack<MetricType>(aData.z(), aMetricRgh);
0094 }
0095 else
0096 {
0097 aNode = BVH_NodeInStack<MetricType>(aData.z(), aMetricRgh);
0098 aStack[++aHead] = BVH_NodeInStack<MetricType>(aData.y(), aMetricLft);
0099 }
0100 }
0101 else if (isGoodLft || isGoodRgh)
0102 {
0103 aNode = isGoodLft ? BVH_NodeInStack<MetricType>(aData.y(), aMetricLft)
0104 : BVH_NodeInStack<MetricType>(aData.z(), aMetricRgh);
0105 }
0106 }
0107 else
0108 {
0109 // Both children will be accepted
0110 // Take one for processing, put the other into stack
0111 aNode = BVH_NodeInStack<MetricType>(aData.y(), aNode.Metric);
0112 aStack[++aHead] = BVH_NodeInStack<MetricType>(aData.z(), aNode.Metric);
0113 }
0114 }
0115 else
0116 {
0117 // Leaf node - apply the leaf node operation to each element
0118 for (Standard_Integer iN = aData.y(); iN <= aData.z(); ++iN)
0119 {
0120 if (Accept(iN, aNode.Metric))
0121 ++aNbAccepted;
0122
0123 if (this->Stop())
0124 return aNbAccepted;
0125 }
0126 }
0127
0128 if (aNode.NodeID == aPrevNode.NodeID)
0129 {
0130 if (aHead < 0)
0131 return aNbAccepted;
0132
0133 // Remove the nodes with bad metric from the stack
0134 aNode = aStack[aHead--];
0135 while (this->RejectMetric(aNode.Metric))
0136 {
0137 if (aHead < 0)
0138 return aNbAccepted;
0139 aNode = aStack[aHead--];
0140 }
0141 }
0142
0143 aPrevNode = aNode;
0144 }
0145 }
0146
0147 namespace
0148 {
0149 //! Auxiliary structure for keeping the pair of nodes to process
0150 template <class MetricType>
0151 struct BVH_PairNodesInStack
0152 {
0153 //! Constructor
0154 BVH_PairNodesInStack(const Standard_Integer theNodeID1 = 0,
0155 const Standard_Integer theNodeID2 = 0,
0156 const MetricType& theMetric = MetricType())
0157 : NodeID1(theNodeID1),
0158 NodeID2(theNodeID2),
0159 Metric(theMetric)
0160 {
0161 }
0162
0163 // Fields
0164 Standard_Integer NodeID1; //!< Id of the node in the first BVH tree
0165 Standard_Integer NodeID2; //!< Id of the node in the second BVH tree
0166 MetricType Metric; //!< Metric computed for the pair of nodes
0167 };
0168 } // namespace
0169
0170 // =======================================================================
0171 // function : BVH_PairTraverse::Select
0172 // purpose :
0173 // =======================================================================
0174 template <class NumType, int Dimension, class BVHSetType, class MetricType>
0175 Standard_Integer BVH_PairTraverse<NumType, Dimension, BVHSetType, MetricType>::Select(
0176 const opencascade::handle<BVH_Tree<NumType, Dimension>>& theBVH1,
0177 const opencascade::handle<BVH_Tree<NumType, Dimension>>& theBVH2)
0178 {
0179 if (theBVH1.IsNull() || theBVH2.IsNull())
0180 return 0;
0181
0182 const BVH_Array4i& aBVHNodes1 = theBVH1->NodeInfoBuffer();
0183 const BVH_Array4i& aBVHNodes2 = theBVH2->NodeInfoBuffer();
0184 if (aBVHNodes1.empty() || aBVHNodes2.empty())
0185 return 0;
0186
0187 // On each iteration we can add max four new pairs of nodes to process.
0188 // One of these pairs goes directly to processing, while others
0189 // are put in the stack. So the max number of pairs in the stack is
0190 // the max tree depth multiplied by 3.
0191 const Standard_Integer aMaxNbPairsInStack = 3 * BVH_Constants_MaxTreeDepth;
0192
0193 // Stack of pairs of nodes to process
0194 BVH_PairNodesInStack<MetricType> aStack[aMaxNbPairsInStack];
0195
0196 // Currently processed pair, starting with the root nodes
0197 BVH_PairNodesInStack<MetricType> aNode(0, 0);
0198 // Previously processed pair
0199 BVH_PairNodesInStack<MetricType> aPrevNode = aNode;
0200 // End of the stack
0201 Standard_Integer aHead = -1;
0202 // Counter for accepted elements
0203 Standard_Integer aNbAccepted = 0;
0204
0205 for (;;)
0206 {
0207 const BVH_Vec4i& aData1 = aBVHNodes1[aNode.NodeID1];
0208 const BVH_Vec4i& aData2 = aBVHNodes2[aNode.NodeID2];
0209
0210 if (aData1.x() != 0 && aData2.x() != 0)
0211 {
0212 // Outer/Outer
0213 for (Standard_Integer iN1 = aData1.y(); iN1 <= aData1.z(); ++iN1)
0214 {
0215 for (Standard_Integer iN2 = aData2.y(); iN2 <= aData2.z(); ++iN2)
0216 {
0217 if (Accept(iN1, iN2))
0218 ++aNbAccepted;
0219
0220 if (this->Stop())
0221 return aNbAccepted;
0222 }
0223 }
0224 }
0225 else
0226 {
0227 BVH_PairNodesInStack<MetricType> aPairs[4];
0228 Standard_Integer aNbPairs = 0;
0229
0230 if (aData1.x() == 0 && aData2.x() == 0)
0231 {
0232 // Inner/Inner
0233 aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType>(aData1.y(), aData2.y());
0234 aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType>(aData1.y(), aData2.z());
0235 aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType>(aData1.z(), aData2.y());
0236 aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType>(aData1.z(), aData2.z());
0237 }
0238 else if (aData1.x() == 0)
0239 {
0240 // Inner/Outer
0241 aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType>(aData1.y(), aNode.NodeID2);
0242 aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType>(aData1.z(), aNode.NodeID2);
0243 }
0244 else if (aData2.x() == 0)
0245 {
0246 // Outer/Inner
0247 aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType>(aNode.NodeID1, aData2.y());
0248 aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType>(aNode.NodeID1, aData2.z());
0249 }
0250
0251 BVH_PairNodesInStack<MetricType> aKeptPairs[4];
0252 Standard_Integer aNbKept = 0;
0253 // Compute metrics for the nodes
0254 for (Standard_Integer iPair = 0; iPair < aNbPairs; ++iPair)
0255 {
0256 const Standard_Boolean isPairRejected = RejectNode(theBVH1->MinPoint(aPairs[iPair].NodeID1),
0257 theBVH1->MaxPoint(aPairs[iPair].NodeID1),
0258 theBVH2->MinPoint(aPairs[iPair].NodeID2),
0259 theBVH2->MaxPoint(aPairs[iPair].NodeID2),
0260 aPairs[iPair].Metric);
0261 if (!isPairRejected)
0262 {
0263 // Put the item into the sorted array of pairs
0264 Standard_Integer iSort = aNbKept;
0265 while (iSort > 0
0266 && this->IsMetricBetter(aPairs[iPair].Metric, aKeptPairs[iSort - 1].Metric))
0267 {
0268 aKeptPairs[iSort] = aKeptPairs[iSort - 1];
0269 --iSort;
0270 }
0271 aKeptPairs[iSort] = aPairs[iPair];
0272 aNbKept++;
0273 }
0274 }
0275
0276 if (aNbKept > 0)
0277 {
0278 aNode = aKeptPairs[0];
0279
0280 for (Standard_Integer iPair = 1; iPair < aNbKept; ++iPair)
0281 {
0282 aStack[++aHead] = aKeptPairs[iPair];
0283 }
0284 }
0285 }
0286
0287 if (aNode.NodeID1 == aPrevNode.NodeID1 && aNode.NodeID2 == aPrevNode.NodeID2)
0288 {
0289 // No pairs to add
0290 if (aHead < 0)
0291 return aNbAccepted;
0292
0293 // Remove the pairs of nodes with bad metric from the stack
0294 aNode = aStack[aHead--];
0295 while (this->RejectMetric(aNode.Metric))
0296 {
0297 if (aHead < 0)
0298 return aNbAccepted;
0299 aNode = aStack[aHead--];
0300 }
0301 }
0302
0303 aPrevNode = aNode;
0304 }
0305 }
