include/opencascade/BVH_SweepPlaneBuilder.hxx

0001 // Created on: 2014-01-09
0002 // Created by: Denis BOGOLEPOV
0003 // Copyright (c) 2013-2014 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 #ifndef BVH_SweepPlaneBuilder_HeaderFile
0017 #define BVH_SweepPlaneBuilder_HeaderFile
0018
0019 #include <BVH_QueueBuilder.hxx>
0020 #include <BVH_QuickSorter.hxx>
0021 #include <NCollection_Array1.hxx>
0022
0023 //! Performs building of BVH tree using sweep plane SAH algorithm.
0024 template <class T, int N>
0025 class BVH_SweepPlaneBuilder : public BVH_QueueBuilder<T, N>
0026 {
0027 public:
0028   //! Creates sweep plane SAH BVH builder.
0029   BVH_SweepPlaneBuilder(const int theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault,
0030                         const int theMaxTreeDepth = BVH_Constants_MaxTreeDepth,
0031                         const int theNumOfThreads = 1)
0032       : BVH_QueueBuilder<T, N>(theLeafNodeSize, theMaxTreeDepth, theNumOfThreads)
0033   {
0034   }
0035
0036   //! Releases resources of sweep plane SAH BVH builder.
0037   ~BVH_SweepPlaneBuilder() override = default;
0038
0039 protected:
0040   //! Performs splitting of the given BVH node.
0041   typename BVH_QueueBuilder<T, N>::BVH_ChildNodes buildNode(BVH_Set<T, N>*  theSet,
0042                                                             BVH_Tree<T, N>* theBVH,
0043                                                             const int       theNode) const override
0044   {
0045     const int aNodeBegPrimitive = theBVH->BegPrimitive(theNode);
0046     const int aNodeEndPrimitive = theBVH->EndPrimitive(theNode);
0047     const int aNodeNbPrimitives = theBVH->NbPrimitives(theNode);
0048     if (aNodeNbPrimitives <= BVH_Builder<T, N>::myLeafNodeSize)
0049     {
0050       // clang-format off
0051       return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // node does not require partitioning
0052       // clang-format on
0053     }
0054
0055     // Parameters for storing best split
0056     int aMinSplitAxis  = -1;
0057     int aMinSplitIndex = 0;
0058
0059     NCollection_Array1<double> aLftSet(1, aNodeNbPrimitives - 1);
0060     NCollection_Array1<double> aRghSet(1, aNodeNbPrimitives - 1);
0061     double                     aMinSplitCost = std::numeric_limits<double>::max();
0062
0063     // Find best split
0064     for (int anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
0065     {
0066       const T aNodeSize = BVH::VecComp<T, N>::Get(theBVH->MaxPoint(theNode), anAxis)
0067                           - BVH::VecComp<T, N>::Get(theBVH->MinPoint(theNode), anAxis);
0068       if (aNodeSize <= BVH::THE_NODE_MIN_SIZE)
0069       {
0070         continue;
0071       }
0072
0073       BVH_QuickSorter<T, N>(anAxis).Perform(theSet, aNodeBegPrimitive, aNodeEndPrimitive);
0074       BVH_Box<T, N> aLftBox;
0075       BVH_Box<T, N> aRghBox;
0076
0077       // Sweep from left
0078       for (int anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
0079       {
0080         aLftBox.Combine(theSet->Box(anIndex + aNodeBegPrimitive - 1));
0081         aLftSet(anIndex) = static_cast<double>(aLftBox.Area());
0082       }
0083
0084       // Sweep from right
0085       for (int anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
0086       {
0087         aRghBox.Combine(theSet->Box(aNodeEndPrimitive - anIndex + 1));
0088         aRghSet(anIndex) = static_cast<double>(aRghBox.Area());
0089       }
0090
0091       // Find best split using simplified SAH
0092       for (int aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives;
0093            ++aNbLft, --aNbRgh)
0094       {
0095         double aCost = (aLftSet(aNbLft) /* / aNodeArea */) * aNbLft
0096                        + (aRghSet(aNbRgh) /* / aNodeArea */) * aNbRgh;
0097         if (aCost < aMinSplitCost)
0098         {
0099           aMinSplitCost  = aCost;
0100           aMinSplitAxis  = anAxis;
0101           aMinSplitIndex = aNbLft;
0102         }
0103       }
0104     }
0105
0106     if (aMinSplitAxis == -1)
0107     {
0108       return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // failed to find split axis
0109     }
0110
0111     theBVH->SetInner(theNode);
0112     if (aMinSplitAxis != (N < 4 ? N - 1 : 2))
0113     {
0114       BVH_QuickSorter<T, N>(aMinSplitAxis).Perform(theSet, aNodeBegPrimitive, aNodeEndPrimitive);
0115     }
0116
0117     BVH_Box<T, N> aMinSplitBoxLft;
0118     BVH_Box<T, N> aMinSplitBoxRgh;
0119
0120     // Compute bounding boxes for selected split plane
0121     for (int anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex)
0122     {
0123       aMinSplitBoxLft.Combine(theSet->Box(anIndex));
0124     }
0125
0126     for (int anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex)
0127     {
0128       aMinSplitBoxRgh.Combine(theSet->Box(anIndex));
0129     }
0130
0131     const int aMiddle = aNodeBegPrimitive + aMinSplitIndex;
0132     typedef typename BVH_QueueBuilder<T, N>::BVH_PrimitiveRange Range;
0133     return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(aMinSplitBoxLft,
0134                                                            aMinSplitBoxRgh,
0135                                                            Range(aNodeBegPrimitive, aMiddle - 1),
0136                                                            Range(aMiddle, aNodeEndPrimitive));
0137   }
0138 };
0139
0140 #endif // _BVH_SweepPlaneBuilder_Header