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