0024739: TKOpenGl - port ray-tracing from OpenCL to GLSL for better integration and...
[occt.git] / src / BVH / BVH_SweepPlaneBuilder.lxx
CommitLineData
3c4e78f2 1// Created on: 2014-01-09
2// Created by: Denis BOGOLEPOV
d5f74e42 3// Copyright (c) 2013-2014 OPEN CASCADE SAS
3c4e78f2 4//
5// This file is part of Open CASCADE Technology software library.
6//
d5f74e42 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
3c4e78f2 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_Sorter.hxx>
17
18// =======================================================================
19// function : BVH_SweepPlaneBuilder
20// purpose :
21// =======================================================================
22template<class T, int N>
23BVH_SweepPlaneBuilder<T, N>::BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize,
24 const Standard_Integer theMaxTreeDepth)
25: BVH_Builder<T, N> (theLeafNodeSize,
26 theMaxTreeDepth)
27{
28 //
29}
30
31// =======================================================================
32// function : ~BVH_SweepPlaneBuilder
33// purpose :
34// =======================================================================
35template<class T, int N>
36BVH_SweepPlaneBuilder<T, N>::~BVH_SweepPlaneBuilder()
37{
38 //
39}
40
41// =======================================================================
42// function : BuildNode
43// purpose :
44// =======================================================================
45template<class T, int N>
46void BVH_SweepPlaneBuilder<T, N>::BuildNode (BVH_Set<T, N>* theSet,
47 BVH_Tree<T, N>* theBVH,
48 const Standard_Integer theNode)
49{
50 const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
51 const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
52 const Standard_Integer aNodeNbPrimitives = theBVH->NbPrimitives (theNode);
53
228de226 54 if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
55 {
56 return; // node does not require partitioning
57 }
58
3c4e78f2 59 // Parameters for storing best split
60 Standard_Integer aMinSplitAxis = -1;
61 Standard_Integer aMinSplitIndex = 0;
62
63 Standard_Real* aLftSet = new Standard_Real[aNodeNbPrimitives];
64 Standard_Real* aRghSet = new Standard_Real[aNodeNbPrimitives];
65
66 Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
67
68 // Find best split
69 for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
70 {
71 const T aNodeSize = BVHTools::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), anAxis) -
72 BVHTools::VecComp<T, N>::Get (theBVH->MinPoint (theNode), anAxis);
73 if (aNodeSize <= THE_NODE_MIN_SIZE)
74 {
75 continue;
76 }
77
78 BVH_Sorter<T, N>::Perform (theSet, anAxis, aNodeBegPrimitive, aNodeEndPrimitive);
79
80 BVH_Box<T, N> aLftBox;
81 BVH_Box<T, N> aRghBox;
82
83 *aLftSet = std::numeric_limits<T>::max();
84 *aRghSet = std::numeric_limits<T>::max();
85
86 // Sweep from left
87 for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
88 {
89 aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1));
90
91 aLftSet[anIndex] = static_cast<Standard_Real> (aLftBox.Area());
92 }
93
94 // Sweep from right
95 for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
96 {
97 aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1));
98
99 aRghSet[anIndex] = static_cast<Standard_Real> (aRghBox.Area());
100 }
101
102 // Find best split using simplified SAH
103 for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh)
104 {
105 Standard_Real aCost = (aLftSet[aNbLft] /* / aNodeArea */) * aNbLft +
106 (aRghSet[aNbRgh] /* / aNodeArea */) * aNbRgh;
107
108 if (aCost < aMinSplitCost)
109 {
110 aMinSplitCost = aCost;
111 aMinSplitAxis = anAxis;
112 aMinSplitIndex = aNbLft;
113 }
114 }
115 }
116
117 if (aMinSplitAxis == -1)
118 {
119 return;
120 }
121
122 theBVH->SetInner (theNode);
123
124 if (aMinSplitAxis != (N < 4 ? N - 1 : 2))
125 {
126 BVH_Sorter<T, N>::Perform (theSet, aMinSplitAxis, aNodeBegPrimitive, aNodeEndPrimitive);
127 }
128
129 BVH_Box<T, N> aMinSplitBoxLft;
130 BVH_Box<T, N> aMinSplitBoxRgh;
131
132 // Compute bounding boxes for selected split plane
133 for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex)
134 {
135 aMinSplitBoxLft.Combine (theSet->Box (anIndex));
136 }
137
138 for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex)
139 {
140 aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
141 }
142
143 const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex;
144
145 static const Standard_Integer aLftNode = 1;
146 static const Standard_Integer aRghNode = 2;
147
148 // Setting up tasks for child nodes
149 for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide)
150 {
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();
157
158 Standard_Integer aChildBegPrimitive = (aSide == aLftNode)
159 ? aNodeBegPrimitive
160 : aMiddle;
161 Standard_Integer aChildEndPrimitive = (aSide == aLftNode)
162 ? aMiddle - 1
163 : aNodeEndPrimitive;
164
165 Standard_Integer aChildIndex = theBVH->AddLeafNode (aChildMinPoint, aChildMaxPoint,
166 aChildBegPrimitive, aChildEndPrimitive);
167
168 theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
169
170 // Check to see if child node must be split
171 const Standard_Integer aChildNbPimitives = (aSide == aLftNode)
172 ? aMiddle - aNodeBegPrimitive
173 : aNodeEndPrimitive - aMiddle + 1;
174
175 if (aSide == aLftNode)
176 theBVH->LeftChild (theNode) = aChildIndex;
177 else
178 theBVH->RightChild (theNode) = aChildIndex;
179
180 const Standard_Boolean isLeaf = aChildNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
181 || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
182
183 if (!isLeaf)
184 {
185 BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
186 }
fc73a202 187
188 BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex));
3c4e78f2 189 }
190}