1 // Created on: 2014-01-09
2 // Created by: Denis BOGOLEPOV
3 // Copyright (c) 2013-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #include <BVH_Sorter.hxx>
18 // =======================================================================
19 // function : BVH_SweepPlaneBuilder
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_QueueBuilder<T, N> (theLeafNodeSize,
31 // =======================================================================
32 // function : ~BVH_SweepPlaneBuilder
34 // =======================================================================
35 template<class T, int N>
36 BVH_SweepPlaneBuilder<T, N>::~BVH_SweepPlaneBuilder()
41 // =======================================================================
42 // function : BuildNode
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)
50 const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
51 const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
52 const Standard_Integer aNodeNbPrimitives = theBVH->NbPrimitives (theNode);
54 if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
56 return; // node does not require partitioning
59 // Parameters for storing best split
60 Standard_Integer aMinSplitAxis = -1;
61 Standard_Integer aMinSplitIndex = 0;
63 Standard_Real* aLftSet = new Standard_Real[aNodeNbPrimitives];
64 Standard_Real* aRghSet = new Standard_Real[aNodeNbPrimitives];
66 Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
69 for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
71 const T aNodeSize = BVH::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), anAxis) -
72 BVH::VecComp<T, N>::Get (theBVH->MinPoint (theNode), anAxis);
73 if (aNodeSize <= THE_NODE_MIN_SIZE)
78 BVH_Sorter<T, N>::Perform (theSet, anAxis, aNodeBegPrimitive, aNodeEndPrimitive);
80 BVH_Box<T, N> aLftBox;
81 BVH_Box<T, N> aRghBox;
83 *aLftSet = std::numeric_limits<T>::max();
84 *aRghSet = std::numeric_limits<T>::max();
87 for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
89 aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1));
91 aLftSet[anIndex] = static_cast<Standard_Real> (aLftBox.Area());
95 for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
97 aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1));
99 aRghSet[anIndex] = static_cast<Standard_Real> (aRghBox.Area());
102 // Find best split using simplified SAH
103 for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh)
105 Standard_Real aCost = (aLftSet[aNbLft] /* / aNodeArea */) * aNbLft +
106 (aRghSet[aNbRgh] /* / aNodeArea */) * aNbRgh;
108 if (aCost < aMinSplitCost)
110 aMinSplitCost = aCost;
111 aMinSplitAxis = anAxis;
112 aMinSplitIndex = aNbLft;
117 if (aMinSplitAxis == -1)
122 theBVH->SetInner (theNode);
124 if (aMinSplitAxis != (N < 4 ? N - 1 : 2))
126 BVH_Sorter<T, N>::Perform (theSet, aMinSplitAxis, aNodeBegPrimitive, aNodeEndPrimitive);
129 BVH_Box<T, N> aMinSplitBoxLft;
130 BVH_Box<T, N> aMinSplitBoxRgh;
132 // Compute bounding boxes for selected split plane
133 for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex)
135 aMinSplitBoxLft.Combine (theSet->Box (anIndex));
138 for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex)
140 aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
143 const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex;
145 static const Standard_Integer aLftNode = 1;
146 static const Standard_Integer aRghNode = 2;
148 // Setting up tasks for child nodes
149 for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide)
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();
158 Standard_Integer aChildBegPrimitive = (aSide == aLftNode)
161 Standard_Integer aChildEndPrimitive = (aSide == aLftNode)
165 Standard_Integer aChildIndex = theBVH->AddLeafNode (aChildMinPoint, aChildMaxPoint,
166 aChildBegPrimitive, aChildEndPrimitive);
168 theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
170 // Check to see if child node must be split
171 const Standard_Integer aChildNbPimitives = (aSide == aLftNode)
172 ? aMiddle - aNodeBegPrimitive
173 : aNodeEndPrimitive - aMiddle + 1;
175 if (aSide == aLftNode)
176 theBVH->LeftChild (theNode) = aChildIndex;
178 theBVH->RightChild (theNode) = aChildIndex;
180 const Standard_Boolean isLeaf = aChildNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
181 || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
185 BVH_QueueBuilder<T, N>::myTasksQueue.Append (aChildIndex);
188 BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex));