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_QuickSorter.hxx>
  17
  18 #include <NCollection_Array1.hxx>
  19
  20 // =======================================================================
  21 // function : BVH_SweepPlaneBuilder
  22 // purpose  :
  23 // =======================================================================
  24 template<class T, int N>
  25 BVH_SweepPlaneBuilder<T, N>::BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize,
  26                                                     const Standard_Integer theMaxTreeDepth,
  27                                                     const Standard_Integer theNumOfThreads)
  28 : BVH_QueueBuilder<T, N> (theLeafNodeSize,
  29                           theMaxTreeDepth,
  30                           theNumOfThreads)
  31 {
  32   //
  33 }
  34
  35 // =======================================================================
  36 // function : ~BVH_SweepPlaneBuilder
  37 // purpose  :
  38 // =======================================================================
  39 template<class T, int N>
  40 BVH_SweepPlaneBuilder<T, N>::~BVH_SweepPlaneBuilder()
  41 {
  42   //
  43 }
  44
  45 // =======================================================================
  46 // function : BuildNode
  47 // purpose  :
  48 // =======================================================================
  49 template<class T, int N>
  50 typename BVH_QueueBuilder<T, N>::BVH_ChildNodes BVH_SweepPlaneBuilder<T, N>::BuildNode (BVH_Set<T, N>*         theSet,
  51                                                                                         BVH_Tree<T, N>*        theBVH,
  52                                                                                         const Standard_Integer theNode)
  53 {
  54   const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
  55   const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
  56   const Standard_Integer aNodeNbPrimitives = theBVH->NbPrimitives (theNode);
  57
  58   if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
  59   {
  60     return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // node does not require partitioning
  61   }
  62
  63   // Parameters for storing best split
  64   Standard_Integer aMinSplitAxis = -1;
  65   Standard_Integer aMinSplitIndex = 0;
  66
  67   NCollection_Array1<Standard_Real> aLftSet (0, aNodeNbPrimitives - 1);
  68   NCollection_Array1<Standard_Real> aRghSet (0, aNodeNbPrimitives - 1);
  69
  70   Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
  71
  72   // Find best split
  73   for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
  74   {
  75     const T aNodeSize = BVH::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), anAxis) -
  76                         BVH::VecComp<T, N>::Get (theBVH->MinPoint (theNode), anAxis);
  77     if (aNodeSize <= BVH::THE_NODE_MIN_SIZE)
  78     {
  79       continue;
  80     }
  81
  82     BVH_QuickSorter<T, N> (anAxis).Perform (theSet, aNodeBegPrimitive, aNodeEndPrimitive);
  83
  84     BVH_Box<T, N> aLftBox;
  85     BVH_Box<T, N> aRghBox;
  86
  87     aLftSet.ChangeFirst() = std::numeric_limits<T>::max();
  88     aRghSet.ChangeFirst() = std::numeric_limits<T>::max();
  89
  90     // Sweep from left
  91     for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
  92     {
  93       aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1));
  94
  95       aLftSet (anIndex) = static_cast<Standard_Real> (aLftBox.Area());
  96     }
  97
  98     // Sweep from right
  99     for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
 100     {
 101       aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1));
 102
 103       aRghSet (anIndex) = static_cast<Standard_Real> (aRghBox.Area());
 104     }
 105
 106     // Find best split using simplified SAH
 107     for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh)
 108     {
 109       Standard_Real aCost = (aLftSet (aNbLft) /* / aNodeArea */) * aNbLft +
 110                             (aRghSet (aNbRgh) /* / aNodeArea */) * aNbRgh;
 111
 112       if (aCost < aMinSplitCost)
 113       {
 114         aMinSplitCost = aCost;
 115         aMinSplitAxis = anAxis;
 116         aMinSplitIndex = aNbLft;
 117       }
 118     }
 119   }
 120
 121   if (aMinSplitAxis == -1)
 122   {
 123     return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // failed to find split axis
 124   }
 125
 126   theBVH->SetInner (theNode);
 127
 128   if (aMinSplitAxis != (N < 4 ? N - 1 : 2))
 129   {
 130     BVH_QuickSorter<T, N> (aMinSplitAxis).Perform (theSet, aNodeBegPrimitive, aNodeEndPrimitive);
 131   }
 132
 133   BVH_Box<T, N> aMinSplitBoxLft;
 134   BVH_Box<T, N> aMinSplitBoxRgh;
 135
 136   // Compute bounding boxes for selected split plane
 137   for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex)
 138   {
 139     aMinSplitBoxLft.Combine (theSet->Box (anIndex));
 140   }
 141
 142   for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex)
 143   {
 144     aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
 145   }
 146
 147   const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex;
 148
 149   typedef typename BVH_QueueBuilder<T, N>::BVH_PrimitiveRange Range;
 150
 151   return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes (aMinSplitBoxLft,
 152                                                           aMinSplitBoxRgh,
 153                                                           Range (aNodeBegPrimitive, aMiddle - 1),
 154                                                           Range (aMiddle,     aNodeEndPrimitive));
 155 }