src/BVH/BVH_SweepPlaneBuilder.lxx

   1 // Created on: 2014-01-09
   2 // Created by: Denis BOGOLEPOV
   3 // Copyright (c) 2013 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
   8 // under the terms of the GNU Lesser General Public 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 #include <BVH_Sorter.hxx>
  17
  18 // =======================================================================
  19 // function : BVH_SweepPlaneBuilder
  20 // purpose  :
  21 // =======================================================================
  22 template<class T, int N>
  23 BVH_SweepPlaneBuilder<T, N>::BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize,
  24                                                     const Standard_Integer theMaxTreeDepth)
  25 : BVH_Builder<T, N> (theLeafNodeSize,
  26                      theMaxTreeDepth)
  27 {
  28   //
  29 }
  30
  31 // =======================================================================
  32 // function : ~BVH_SweepPlaneBuilder
  33 // purpose  :
  34 // =======================================================================
  35 template<class T, int N>
  36 BVH_SweepPlaneBuilder<T, N>::~BVH_SweepPlaneBuilder()
  37 {
  38   //
  39 }
  40
  41 // =======================================================================
  42 // function : BuildNode
  43 // purpose  :
  44 // =======================================================================
  45 template<class T, int N>
  46 void BVH_SweepPlaneBuilder<T, N>::BuildNode (BVH_Set<T, N>*         theSet,
  47                                              BVH_Tree<T, N>*        theBVH,
  48                                              const Standard_Integer theNode)
  49 {
  50   const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
  51   const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
  52   const Standard_Integer aNodeNbPrimitives = theBVH->NbPrimitives (theNode);
  53
  54   // Parameters for storing best split
  55   Standard_Integer aMinSplitAxis = -1;
  56   Standard_Integer aMinSplitIndex = 0;
  57
  58   Standard_Real* aLftSet = new Standard_Real[aNodeNbPrimitives];
  59   Standard_Real* aRghSet = new Standard_Real[aNodeNbPrimitives];
  60
  61   Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
  62
  63   // Find best split
  64   for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
  65   {
  66     const T aNodeSize = BVHTools::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), anAxis) -
  67                         BVHTools::VecComp<T, N>::Get (theBVH->MinPoint (theNode), anAxis);
  68     if (aNodeSize <= THE_NODE_MIN_SIZE)
  69     {
  70       continue;
  71     }
  72
  73     BVH_Sorter<T, N>::Perform (theSet, anAxis, aNodeBegPrimitive, aNodeEndPrimitive);
  74
  75     BVH_Box<T, N> aLftBox;
  76     BVH_Box<T, N> aRghBox;
  77
  78     *aLftSet = std::numeric_limits<T>::max();
  79     *aRghSet = std::numeric_limits<T>::max();
  80
  81     // Sweep from left
  82     for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
  83     {
  84       aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1));
  85
  86       aLftSet[anIndex] = static_cast<Standard_Real> (aLftBox.Area());
  87     }
  88
  89     // Sweep from right
  90     for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
  91     {
  92       aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1));
  93
  94       aRghSet[anIndex] = static_cast<Standard_Real> (aRghBox.Area());
  95     }
  96
  97     // Find best split using simplified SAH
  98     for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh)
  99     {
 100       Standard_Real aCost = (aLftSet[aNbLft] /* / aNodeArea */) * aNbLft +
 101                             (aRghSet[aNbRgh] /* / aNodeArea */) * aNbRgh;
 102
 103       if (aCost < aMinSplitCost)
 104       {
 105         aMinSplitCost = aCost;
 106         aMinSplitAxis = anAxis;
 107         aMinSplitIndex = aNbLft;
 108       }
 109     }
 110   }
 111
 112   if (aMinSplitAxis == -1)
 113   {
 114     return;
 115   }
 116
 117   theBVH->SetInner (theNode);
 118
 119   if (aMinSplitAxis != (N < 4 ? N - 1 : 2))
 120   {
 121     BVH_Sorter<T, N>::Perform (theSet, aMinSplitAxis, aNodeBegPrimitive, aNodeEndPrimitive);
 122   }
 123
 124   BVH_Box<T, N> aMinSplitBoxLft;
 125   BVH_Box<T, N> aMinSplitBoxRgh;
 126
 127   // Compute bounding boxes for selected split plane
 128   for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex)
 129   {
 130     aMinSplitBoxLft.Combine (theSet->Box (anIndex));
 131   }
 132
 133   for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex)
 134   {
 135     aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
 136   }
 137
 138   const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex;
 139
 140   static const Standard_Integer aLftNode = 1;
 141   static const Standard_Integer aRghNode = 2;
 142
 143   // Setting up tasks for child nodes
 144   for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide)
 145   {
 146     typename BVH_Box<T, N>::BVH_VecNt aChildMinPoint = (aSide == aLftNode)
 147                                                      ? aMinSplitBoxLft.CornerMin()
 148                                                      : aMinSplitBoxRgh.CornerMin();
 149     typename BVH_Box<T, N>::BVH_VecNt aChildMaxPoint = (aSide == aLftNode)
 150                                                      ? aMinSplitBoxLft.CornerMax()
 151                                                      : aMinSplitBoxRgh.CornerMax();
 152
 153     Standard_Integer aChildBegPrimitive = (aSide == aLftNode)
 154                                         ? aNodeBegPrimitive
 155                                         : aMiddle;
 156     Standard_Integer aChildEndPrimitive = (aSide == aLftNode)
 157                                         ? aMiddle - 1
 158                                         : aNodeEndPrimitive;
 159
 160     Standard_Integer aChildIndex = theBVH->AddLeafNode (aChildMinPoint, aChildMaxPoint,
 161                                                         aChildBegPrimitive, aChildEndPrimitive);
 162
 163     theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
 164
 165     // Check to see if child node must be split
 166     const Standard_Integer aChildNbPimitives = (aSide == aLftNode)
 167                                              ? aMiddle - aNodeBegPrimitive
 168                                              : aNodeEndPrimitive - aMiddle + 1;
 169
 170     if (aSide == aLftNode)
 171       theBVH->LeftChild (theNode) = aChildIndex;
 172     else
 173       theBVH->RightChild (theNode) = aChildIndex;
 174
 175     const Standard_Boolean isLeaf = aChildNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
 176                                  || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
 177
 178     if (!isLeaf)
 179     {
 180       BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
 181     }
 182   }
 183 }