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 }