| 1 | // Created on: 2013-12-20 |
| 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 | // ======================================================================= |
| 17 | // function : BVH_BinnedBuilder |
| 18 | // purpose : |
| 19 | // ======================================================================= |
| 20 | template<class T, int N, int Bins> |
| 21 | BVH_BinnedBuilder<T, N, Bins>::BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize, |
| 22 | const Standard_Integer theMaxTreeDepth) |
| 23 | : BVH_Builder<T, N> (theLeafNodeSize, |
| 24 | theMaxTreeDepth) |
| 25 | { |
| 26 | // |
| 27 | } |
| 28 | |
| 29 | // ======================================================================= |
| 30 | // function : ~BVH_BinnedBuilder |
| 31 | // purpose : |
| 32 | // ======================================================================= |
| 33 | template<class T, int N, int Bins> |
| 34 | BVH_BinnedBuilder<T, N, Bins>::~BVH_BinnedBuilder() |
| 35 | { |
| 36 | // |
| 37 | } |
| 38 | |
| 39 | // ======================================================================= |
| 40 | // function : GetSubVolumes |
| 41 | // purpose : |
| 42 | // ======================================================================= |
| 43 | template<class T, int N, int Bins> |
| 44 | void BVH_BinnedBuilder<T, N, Bins>::GetSubVolumes (BVH_Set<T, N>* theSet, |
| 45 | BVH_Tree<T, N>* theBVH, |
| 46 | const Standard_Integer theNode, |
| 47 | BVH_BinVector& theBins, |
| 48 | const Standard_Integer theAxis) |
| 49 | { |
| 50 | const T aMin = BVHTools::VecComp<T, N>::Get (theBVH->MinPoint (theNode), theAxis); |
| 51 | const T aMax = BVHTools::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), theAxis); |
| 52 | |
| 53 | const T anInvStep = static_cast<T> (Bins) / (aMax - aMin); |
| 54 | |
| 55 | for (Standard_Integer anIdx = theBVH->BegPrimitive (theNode); anIdx <= theBVH->EndPrimitive (theNode); ++anIdx) |
| 56 | { |
| 57 | typename BVH_Set<T, N>::BVH_BoxNt aBox = theSet->Box (anIdx); |
| 58 | |
| 59 | Standard_Integer aBinIndex = static_cast<Standard_Integer> (std::floor ((theSet->Center (anIdx, theAxis) - aMin) * anInvStep)); |
| 60 | if (aBinIndex < 0) |
| 61 | { |
| 62 | aBinIndex = 0; |
| 63 | } |
| 64 | else if (aBinIndex >= Bins) |
| 65 | { |
| 66 | aBinIndex = Bins - 1; |
| 67 | } |
| 68 | |
| 69 | theBins[aBinIndex].Count++; |
| 70 | theBins[aBinIndex].Box.Combine (aBox); |
| 71 | } |
| 72 | } |
| 73 | |
| 74 | namespace BVHTools |
| 75 | { |
| 76 | // ======================================================================= |
| 77 | // function : SplitPrimitives |
| 78 | // purpose : |
| 79 | // ======================================================================= |
| 80 | template<class T, int N> |
| 81 | Standard_Integer SplitPrimitives (BVH_Set<T, N>* theSet, |
| 82 | const BVH_Box<T, N>& theBox, |
| 83 | const Standard_Integer theBeg, |
| 84 | const Standard_Integer theEnd, |
| 85 | const Standard_Integer theBin, |
| 86 | const Standard_Integer theAxis, |
| 87 | const Standard_Integer theBins) |
| 88 | { |
| 89 | const T aMin = BVHTools::VecComp<T, N>::Get (theBox.CornerMin(), theAxis); |
| 90 | const T aMax = BVHTools::VecComp<T, N>::Get (theBox.CornerMax(), theAxis); |
| 91 | |
| 92 | const T anInvStep = static_cast<T> (theBins) / (aMax - aMin); |
| 93 | |
| 94 | Standard_Integer aLftIdx (theBeg); |
| 95 | Standard_Integer aRghIdx (theEnd); |
| 96 | |
| 97 | do |
| 98 | { |
| 99 | while ((Standard_Integer) std::floor ((theSet->Center (aLftIdx, theAxis) - aMin) * anInvStep) <= theBin && aLftIdx < theEnd) |
| 100 | { |
| 101 | ++aLftIdx; |
| 102 | } |
| 103 | while ((Standard_Integer) std::floor ((theSet->Center (aRghIdx, theAxis) - aMin) * anInvStep) > theBin && aRghIdx > theBeg) |
| 104 | { |
| 105 | --aRghIdx; |
| 106 | } |
| 107 | |
| 108 | if (aLftIdx <= aRghIdx) |
| 109 | { |
| 110 | if (aLftIdx != aRghIdx) |
| 111 | { |
| 112 | theSet->Swap (aLftIdx, aRghIdx); |
| 113 | } |
| 114 | |
| 115 | ++aLftIdx; |
| 116 | --aRghIdx; |
| 117 | } |
| 118 | } while (aLftIdx <= aRghIdx); |
| 119 | |
| 120 | return aLftIdx; |
| 121 | } |
| 122 | } |
| 123 | |
| 124 | #if defined (_WIN32) && defined (max) |
| 125 | #undef max |
| 126 | #endif |
| 127 | |
| 128 | #include <limits> |
| 129 | |
| 130 | // ======================================================================= |
| 131 | // function : BuildNode |
| 132 | // purpose : |
| 133 | // ======================================================================= |
| 134 | template<class T, int N, int Bins> |
| 135 | void BVH_BinnedBuilder<T, N, Bins>::BuildNode (BVH_Set<T, N>* theSet, |
| 136 | BVH_Tree<T, N>* theBVH, |
| 137 | const Standard_Integer theNode) |
| 138 | { |
| 139 | const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode); |
| 140 | const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode); |
| 141 | |
| 142 | if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize) |
| 143 | { |
| 144 | return; // node does not require partitioning |
| 145 | } |
| 146 | |
| 147 | const BVH_Box<T, N> anAABB (theBVH->MinPoint (theNode), |
| 148 | theBVH->MaxPoint (theNode)); |
| 149 | |
| 150 | const typename BVH_Box<T, N>::BVH_VecNt aSize = anAABB.Size(); |
| 151 | |
| 152 | // Parameters for storing best split |
| 153 | Standard_Integer aMinSplitAxis = -1; |
| 154 | Standard_Integer aMinSplitIndex = 0; |
| 155 | Standard_Integer aMinSplitNumLft = 0; |
| 156 | Standard_Integer aMinSplitNumRgh = 0; |
| 157 | |
| 158 | BVH_Box<T, N> aMinSplitBoxLft; |
| 159 | BVH_Box<T, N> aMinSplitBoxRgh; |
| 160 | |
| 161 | Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max(); |
| 162 | |
| 163 | // Find best split |
| 164 | for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis) |
| 165 | { |
| 166 | if (BVHTools::VecComp<T, N>::Get (aSize, anAxis) <= THE_NODE_MIN_SIZE) |
| 167 | continue; |
| 168 | |
| 169 | BVH_BinVector aBins; |
| 170 | GetSubVolumes (theSet, theBVH, theNode, aBins, anAxis); |
| 171 | |
| 172 | // Choose the best split (with minimum SAH cost) |
| 173 | for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit) |
| 174 | { |
| 175 | Standard_Integer aLftCount = 0; |
| 176 | Standard_Integer aRghCount = 0; |
| 177 | |
| 178 | BVH_Box<T, N> aLftAABB; |
| 179 | BVH_Box<T, N> aRghAABB; |
| 180 | |
| 181 | for (Standard_Integer anIndex = 0; anIndex < aSplit; ++anIndex) |
| 182 | { |
| 183 | aLftCount += aBins[anIndex].Count; |
| 184 | aLftAABB.Combine (aBins[anIndex].Box); |
| 185 | } |
| 186 | |
| 187 | for (Standard_Integer anIndex = aSplit; anIndex < Bins; ++anIndex) |
| 188 | { |
| 189 | aRghCount += aBins[anIndex].Count; |
| 190 | aRghAABB.Combine (aBins[anIndex].Box); |
| 191 | } |
| 192 | |
| 193 | // Simple SAH evaluation |
| 194 | Standard_Real aCost = (static_cast<Standard_Real> (aLftAABB.Area()) /* / aNodeArea */) * aLftCount |
| 195 | + (static_cast<Standard_Real> (aRghAABB.Area()) /* / aNodeArea */) * aRghCount; |
| 196 | |
| 197 | if (aCost <= aMinSplitCost) |
| 198 | { |
| 199 | aMinSplitCost = aCost; |
| 200 | aMinSplitAxis = anAxis; |
| 201 | aMinSplitIndex = aSplit; |
| 202 | aMinSplitBoxLft = aLftAABB; |
| 203 | aMinSplitBoxRgh = aRghAABB; |
| 204 | aMinSplitNumLft = aLftCount; |
| 205 | aMinSplitNumRgh = aRghCount; |
| 206 | } |
| 207 | } |
| 208 | } |
| 209 | |
| 210 | if (aMinSplitAxis == -1) |
| 211 | { |
| 212 | return; |
| 213 | } |
| 214 | |
| 215 | theBVH->SetInner (theNode); |
| 216 | |
| 217 | Standard_Integer aMiddle = -1; |
| 218 | |
| 219 | if (aMinSplitNumLft == 0 || aMinSplitNumRgh == 0) // case of objects with the same center |
| 220 | { |
| 221 | aMinSplitBoxLft.Clear(); |
| 222 | aMinSplitBoxRgh.Clear(); |
| 223 | |
| 224 | aMiddle = std::max (aNodeBegPrimitive + 1, |
| 225 | static_cast<Standard_Integer> ((aNodeBegPrimitive + aNodeEndPrimitive) / 2.f)); |
| 226 | |
| 227 | aMinSplitNumLft = aMiddle - aNodeBegPrimitive; |
| 228 | |
| 229 | for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMiddle; ++anIndex) |
| 230 | { |
| 231 | aMinSplitBoxLft.Combine (theSet->Box (anIndex)); |
| 232 | } |
| 233 | |
| 234 | aMinSplitNumRgh = aNodeEndPrimitive - aMiddle + 1; |
| 235 | |
| 236 | for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMiddle; --anIndex) |
| 237 | { |
| 238 | aMinSplitBoxRgh.Combine (theSet->Box (anIndex)); |
| 239 | } |
| 240 | } |
| 241 | else |
| 242 | { |
| 243 | aMiddle = BVHTools::SplitPrimitives<T, N> (theSet, anAABB, |
| 244 | aNodeBegPrimitive, aNodeEndPrimitive, aMinSplitIndex - 1, aMinSplitAxis, Bins); |
| 245 | } |
| 246 | |
| 247 | static const Standard_Integer aLftNode = 1; |
| 248 | static const Standard_Integer aRghNode = 2; |
| 249 | |
| 250 | // Setting up tasks for child nodes |
| 251 | for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide) |
| 252 | { |
| 253 | typename BVH_Box<T, N>::BVH_VecNt aMinPoint = (aSide == aLftNode) |
| 254 | ? aMinSplitBoxLft.CornerMin() |
| 255 | : aMinSplitBoxRgh.CornerMin(); |
| 256 | typename BVH_Box<T, N>::BVH_VecNt aMaxPoint = (aSide == aLftNode) |
| 257 | ? aMinSplitBoxLft.CornerMax() |
| 258 | : aMinSplitBoxRgh.CornerMax(); |
| 259 | |
| 260 | Standard_Integer aBegPrimitive = (aSide == aLftNode) |
| 261 | ? aNodeBegPrimitive |
| 262 | : aMiddle; |
| 263 | Standard_Integer aEndPrimitive = (aSide == aLftNode) |
| 264 | ? aMiddle - 1 |
| 265 | : aNodeEndPrimitive; |
| 266 | |
| 267 | Standard_Integer aChildIndex = theBVH->AddLeafNode (aMinPoint, aMaxPoint, aBegPrimitive, aEndPrimitive); |
| 268 | |
| 269 | theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1; |
| 270 | |
| 271 | // Check to see if child node must be split |
| 272 | const Standard_Integer aNbPimitives = (aSide == aLftNode) |
| 273 | ? aMinSplitNumLft |
| 274 | : aMinSplitNumRgh; |
| 275 | |
| 276 | if (aSide == aLftNode) |
| 277 | theBVH->LeftChild (theNode) = aChildIndex; |
| 278 | else |
| 279 | theBVH->RightChild (theNode) = aChildIndex; |
| 280 | |
| 281 | const Standard_Boolean isLeaf = aNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize |
| 282 | || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth; |
| 283 | |
| 284 | if (!isLeaf) |
| 285 | { |
| 286 | BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex); |
| 287 | } |
| 288 | |
| 289 | BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex)); |
| 290 | } |
| 291 | } |