src/BVH/BVH_SweepPlaneBuilder.lxx

   1 // Created on: 2014-01-09
   2 // Created by: Denis BOGOLEPOV
   3 // Copyright (c) 2013-2014 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 #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   if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
  55   {
  56     return; // node does not require partitioning
  57   }
  58
  59   // Parameters for storing best split
  60   Standard_Integer aMinSplitAxis = -1;
  61   Standard_Integer aMinSplitIndex = 0;
  62
  63   Standard_Real* aLftSet = new Standard_Real[aNodeNbPrimitives];
  64   Standard_Real* aRghSet = new Standard_Real[aNodeNbPrimitives];
  65
  66   Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
  67
  68   // Find best split
  69   for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
  70   {
  71     const T aNodeSize = BVHTools::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), anAxis) -
  72                         BVHTools::VecComp<T, N>::Get (theBVH->MinPoint (theNode), anAxis);
  73     if (aNodeSize <= THE_NODE_MIN_SIZE)
  74     {
  75       continue;
  76     }
  77
  78     BVH_Sorter<T, N>::Perform (theSet, anAxis, aNodeBegPrimitive, aNodeEndPrimitive);
  79
  80     BVH_Box<T, N> aLftBox;
  81     BVH_Box<T, N> aRghBox;
  82
  83     *aLftSet = std::numeric_limits<T>::max();
  84     *aRghSet = std::numeric_limits<T>::max();
  85
  86     // Sweep from left
  87     for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
  88     {
  89       aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1));
  90
  91       aLftSet[anIndex] = static_cast<Standard_Real> (aLftBox.Area());
  92     }
  93
  94     // Sweep from right
  95     for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
  96     {
  97       aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1));
  98
  99       aRghSet[anIndex] = static_cast<Standard_Real> (aRghBox.Area());
 100     }
 101
 102     // Find best split using simplified SAH
 103     for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh)
 104     {
 105       Standard_Real aCost = (aLftSet[aNbLft] /* / aNodeArea */) * aNbLft +
 106                             (aRghSet[aNbRgh] /* / aNodeArea */) * aNbRgh;
 107
 108       if (aCost < aMinSplitCost)
 109       {
 110         aMinSplitCost = aCost;
 111         aMinSplitAxis = anAxis;
 112         aMinSplitIndex = aNbLft;
 113       }
 114     }
 115   }
 116
 117   if (aMinSplitAxis == -1)
 118   {
 119     return;
 120   }
 121
 122   theBVH->SetInner (theNode);
 123
 124   if (aMinSplitAxis != (N < 4 ? N - 1 : 2))
 125   {
 126     BVH_Sorter<T, N>::Perform (theSet, aMinSplitAxis, aNodeBegPrimitive, aNodeEndPrimitive);
 127   }
 128
 129   BVH_Box<T, N> aMinSplitBoxLft;
 130   BVH_Box<T, N> aMinSplitBoxRgh;
 131
 132   // Compute bounding boxes for selected split plane
 133   for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex)
 134   {
 135     aMinSplitBoxLft.Combine (theSet->Box (anIndex));
 136   }
 137
 138   for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex)
 139   {
 140     aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
 141   }
 142
 143   const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex;
 144
 145   static const Standard_Integer aLftNode = 1;
 146   static const Standard_Integer aRghNode = 2;
 147
 148   // Setting up tasks for child nodes
 149   for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide)
 150   {
 151     typename BVH_Box<T, N>::BVH_VecNt aChildMinPoint = (aSide == aLftNode)
 152                                                      ? aMinSplitBoxLft.CornerMin()
 153                                                      : aMinSplitBoxRgh.CornerMin();
 154     typename BVH_Box<T, N>::BVH_VecNt aChildMaxPoint = (aSide == aLftNode)
 155                                                      ? aMinSplitBoxLft.CornerMax()
 156                                                      : aMinSplitBoxRgh.CornerMax();
 157
 158     Standard_Integer aChildBegPrimitive = (aSide == aLftNode)
 159                                         ? aNodeBegPrimitive
 160                                         : aMiddle;
 161     Standard_Integer aChildEndPrimitive = (aSide == aLftNode)
 162                                         ? aMiddle - 1
 163                                         : aNodeEndPrimitive;
 164
 165     Standard_Integer aChildIndex = theBVH->AddLeafNode (aChildMinPoint, aChildMaxPoint,
 166                                                         aChildBegPrimitive, aChildEndPrimitive);
 167
 168     theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
 169
 170     // Check to see if child node must be split
 171     const Standard_Integer aChildNbPimitives = (aSide == aLftNode)
 172                                              ? aMiddle - aNodeBegPrimitive
 173                                              : aNodeEndPrimitive - aMiddle + 1;
 174
 175     if (aSide == aLftNode)
 176       theBVH->LeftChild (theNode) = aChildIndex;
 177     else
 178       theBVH->RightChild (theNode) = aChildIndex;
 179
 180     const Standard_Boolean isLeaf = aChildNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
 181                                  || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
 182
 183     if (!isLeaf)
 184     {
 185       BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
 186     }
 187
 188     BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex));
 189   }
 190 }