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