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
0029   //! Creates sweep plane SAH BVH builder.
0030   BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault,
0031                          const Standard_Integer theMaxTreeDepth = BVH_Constants_MaxTreeDepth,
0032                          const Standard_Integer theNumOfThreads = 1)
0033   : BVH_QueueBuilder<T, N> (theLeafNodeSize,
0034                             theMaxTreeDepth,
0035                             theNumOfThreads) {}
0036
0037   //! Releases resources of sweep plane SAH BVH builder.
0038   virtual ~BVH_SweepPlaneBuilder() {}
0039
0040 protected:
0041
0042   //! Performs splitting of the given BVH node.
0043   typename BVH_QueueBuilder<T, N>::BVH_ChildNodes buildNode (BVH_Set<T, N>*         theSet,
0044                                                              BVH_Tree<T, N>*        theBVH,
0045                                                              const Standard_Integer theNode) const Standard_OVERRIDE
0046   {
0047     const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
0048     const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
0049     const Standard_Integer aNodeNbPrimitives = theBVH->NbPrimitives (theNode);
0050     if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
0051     {
0052       return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // node does not require partitioning
0053     }
0054
0055     // Parameters for storing best split
0056     Standard_Integer aMinSplitAxis = -1;
0057     Standard_Integer aMinSplitIndex = 0;
0058
0059     NCollection_Array1<Standard_Real> aLftSet (0, aNodeNbPrimitives - 1);
0060     NCollection_Array1<Standard_Real> aRghSet (0, aNodeNbPrimitives - 1);
0061     Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
0062
0063     // Find best split
0064     for (Standard_Integer 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       aLftSet.ChangeFirst() = std::numeric_limits<T>::max();
0077       aRghSet.ChangeFirst() = std::numeric_limits<T>::max();
0078
0079       // Sweep from left
0080       for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
0081       {
0082         aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1));
0083         aLftSet (anIndex) = static_cast<Standard_Real> (aLftBox.Area());
0084       }
0085
0086       // Sweep from right
0087       for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
0088       {
0089         aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1));
0090         aRghSet (anIndex) = static_cast<Standard_Real> (aRghBox.Area());
0091       }
0092
0093       // Find best split using simplified SAH
0094       for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh)
0095       {
0096         Standard_Real aCost = (aLftSet (aNbLft) /* / aNodeArea */) * aNbLft +
0097                               (aRghSet (aNbRgh) /* / aNodeArea */) * aNbRgh;
0098         if (aCost < aMinSplitCost)
0099         {
0100           aMinSplitCost = aCost;
0101           aMinSplitAxis = anAxis;
0102           aMinSplitIndex = aNbLft;
0103         }
0104       }
0105     }
0106
0107     if (aMinSplitAxis == -1)
0108     {
0109       return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // failed to find split axis
0110     }
0111
0112     theBVH->SetInner (theNode);
0113     if (aMinSplitAxis != (N < 4 ? N - 1 : 2))
0114     {
0115       BVH_QuickSorter<T, N> (aMinSplitAxis).Perform (theSet, aNodeBegPrimitive, aNodeEndPrimitive);
0116     }
0117
0118     BVH_Box<T, N> aMinSplitBoxLft;
0119     BVH_Box<T, N> aMinSplitBoxRgh;
0120
0121     // Compute bounding boxes for selected split plane
0122     for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex)
0123     {
0124       aMinSplitBoxLft.Combine (theSet->Box (anIndex));
0125     }
0126
0127     for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex)
0128     {
0129       aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
0130     }
0131
0132     const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex;
0133     typedef typename BVH_QueueBuilder<T, N>::BVH_PrimitiveRange Range;
0134     return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes (aMinSplitBoxLft,
0135                                                             aMinSplitBoxRgh,
0136                                                             Range (aNodeBegPrimitive, aMiddle - 1),
0137                                                             Range (aMiddle,     aNodeEndPrimitive));
0138   }
0139
0140 };
0141
0142 #endif // _BVH_SweepPlaneBuilder_Header