X-Git-Url: http://git.dev.opencascade.org/gitweb/?p=occt.git;a=blobdiff_plain;f=src%2FBVH%2FBVH_BinnedBuilder.lxx;h=0cf105d33577245321e8eeb587f0779c214ed8dc;hb=3c4e78f24f6e0f275808832ac7d828cb978ef2e6;hpb=68333c8f16e01c5252dbebd4c9fcd6680f3941ba diff --git a/src/BVH/BVH_BinnedBuilder.lxx b/src/BVH/BVH_BinnedBuilder.lxx new file mode 100644 index 0000000000..0cf105d335 --- /dev/null +++ b/src/BVH/BVH_BinnedBuilder.lxx @@ -0,0 +1,256 @@ +// Created on: 2013-12-20 +// Created by: Denis BOGOLEPOV +// Copyright (c) 2013 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and / or modify it +// under the terms of the GNU Lesser General Public version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +// ======================================================================= +// function : BVH_BinnedBuilder +// purpose : +// ======================================================================= +template +BVH_BinnedBuilder::BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize, + const Standard_Integer theMaxTreeDepth) +: BVH_Builder (theLeafNodeSize, + theMaxTreeDepth) +{ + // +} + +// ======================================================================= +// function : ~BVH_BinnedBuilder +// purpose : +// ======================================================================= +template +BVH_BinnedBuilder::~BVH_BinnedBuilder() +{ + // +} + +// ======================================================================= +// function : GetSubVolumes +// purpose : +// ======================================================================= +template +void BVH_BinnedBuilder::GetSubVolumes (BVH_Set* theSet, + BVH_Tree* theBVH, + const Standard_Integer theNode, + BVH_BinVector& theBins, + const Standard_Integer theAxis) +{ + const T aMin = BVHTools::VecComp::Get (theBVH->MinPoint (theNode), theAxis); + const T aMax = BVHTools::VecComp::Get (theBVH->MaxPoint (theNode), theAxis); + + const T anInvStep = static_cast (Bins) / (aMax - aMin); + + for (Standard_Integer anIdx = theBVH->BegPrimitive (theNode); anIdx <= theBVH->EndPrimitive (theNode); ++anIdx) + { + typename BVH_Set::BVH_BoxNt aBox = theSet->Box (anIdx); + + Standard_Integer aBinIndex = static_cast (std::floor ((theSet->Center (anIdx, theAxis) - aMin) * anInvStep)); + if (aBinIndex < 0) + { + aBinIndex = 0; + } + else if (aBinIndex >= Bins) + { + aBinIndex = Bins - 1; + } + + theBins[aBinIndex].Count++; + theBins[aBinIndex].Box.Combine (aBox); + } +} + +namespace BVHTools +{ + // ======================================================================= + // function : SplitPrimitives + // purpose : + // ======================================================================= + template + Standard_Integer SplitPrimitives (BVH_Set* theSet, + const BVH_Box& theBox, + const Standard_Integer theBeg, + const Standard_Integer theEnd, + const Standard_Integer theBin, + const Standard_Integer theAxis, + const Standard_Integer theBins) + { + const T aMin = BVHTools::VecComp::Get (theBox.CornerMin(), theAxis); + const T aMax = BVHTools::VecComp::Get (theBox.CornerMax(), theAxis); + + const T anInvStep = static_cast (theBins) / (aMax - aMin); + + Standard_Integer aLftIdx (theBeg); + Standard_Integer aRghIdx (theEnd); + + do + { + while ((Standard_Integer) std::floor ((theSet->Center (aLftIdx, theAxis) - aMin) * anInvStep) <= theBin && aLftIdx < theEnd) + { + ++aLftIdx; + } + while ((Standard_Integer) std::floor ((theSet->Center (aRghIdx, theAxis) - aMin) * anInvStep) > theBin && aRghIdx > theBeg) + { + --aRghIdx; + } + + if (aLftIdx <= aRghIdx) + { + if (aLftIdx != aRghIdx) + { + theSet->Swap (aLftIdx, aRghIdx); + } + + ++aLftIdx; + --aRghIdx; + } + } while (aLftIdx <= aRghIdx); + + return aLftIdx; + } +} + +#if defined (_WIN32) && defined (max) + #undef max +#endif + +#include + +// ======================================================================= +// function : BuildNode +// purpose : +// ======================================================================= +template +void BVH_BinnedBuilder::BuildNode (BVH_Set* theSet, + BVH_Tree* theBVH, + const Standard_Integer theNode) +{ + const BVH_Box aBox (theBVH->MinPoint (theNode), + theBVH->MaxPoint (theNode)); + + const typename BVH_Box::BVH_VecNt aSize = aBox.Size(); + + // Parameters for storing best split + Standard_Integer aMinSplitAxis = -1; + Standard_Integer aMinSplitIndex = 0; + Standard_Integer aMinSplitNumLft = 0; + Standard_Integer aMinSplitNumRgh = 0; + + BVH_Box aMinSplitBoxLft; + BVH_Box aMinSplitBoxRgh; + + Standard_Real aMinSplitCost = std::numeric_limits::max(); + + // Find best split + for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis) + { + if (BVHTools::VecComp::Get (aSize, anAxis) <= THE_NODE_MIN_SIZE) + continue; + + BVH_BinVector aBins; + GetSubVolumes (theSet, theBVH, theNode, aBins, anAxis); + + // Choose the best split (with minimum SAH cost) + for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit) + { + Standard_Integer aLftCount = 0; + Standard_Integer aRghCount = 0; + + BVH_Box aLftAABB; + BVH_Box aRghAABB; + + for (Standard_Integer anIndex = 0; anIndex < aSplit; ++anIndex) + { + aLftCount += aBins[anIndex].Count; + aLftAABB.Combine (aBins[anIndex].Box); + } + + for (Standard_Integer anIndex = aSplit; anIndex < Bins; ++anIndex) + { + aRghCount += aBins[anIndex].Count; + aRghAABB.Combine (aBins[anIndex].Box); + } + + // Simple SAH evaluation + Standard_Real aCost = (static_cast (aLftAABB.Area()) /* / aNodeArea */) * aLftCount + + (static_cast (aRghAABB.Area()) /* / aNodeArea */) * aRghCount; + + if (aCost <= aMinSplitCost) + { + aMinSplitCost = aCost; + aMinSplitAxis = anAxis; + aMinSplitIndex = aSplit; + aMinSplitBoxLft = aLftAABB; + aMinSplitBoxRgh = aRghAABB; + aMinSplitNumLft = aLftCount; + aMinSplitNumRgh = aRghCount; + } + } + } + + if (aMinSplitAxis == -1) + { + return; + } + + theBVH->SetInner (theNode); + + const Standard_Integer aMiddle = BVHTools::SplitPrimitives (theSet, aBox, + theBVH->BegPrimitive (theNode), + theBVH->EndPrimitive (theNode), + aMinSplitIndex - 1, + aMinSplitAxis, + Bins); + + static const Standard_Integer aLftNode = 1; + static const Standard_Integer aRghNode = 2; + + // Setting up tasks for child nodes + for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide) + { + typename BVH_Box::BVH_VecNt aMinPoint = (aSide == aLftNode) + ? aMinSplitBoxLft.CornerMin() + : aMinSplitBoxRgh.CornerMin(); + typename BVH_Box::BVH_VecNt aMaxPoint = (aSide == aLftNode) + ? aMinSplitBoxLft.CornerMax() + : aMinSplitBoxRgh.CornerMax(); + + Standard_Integer aBegPrimitive = (aSide == aLftNode) + ? theBVH->BegPrimitive (theNode) + : aMiddle; + Standard_Integer aEndPrimitive = (aSide == aLftNode) + ? aMiddle - 1 + : theBVH->EndPrimitive (theNode); + + Standard_Integer aChildIndex = theBVH->AddLeafNode (aMinPoint, aMaxPoint, aBegPrimitive, aEndPrimitive); + + theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1; + + // Check to see if child node must be split + const Standard_Integer aNbPimitives = (aSide == aLftNode) + ? aMinSplitNumLft + : aMinSplitNumRgh; + + if (aSide == aLftNode) + theBVH->LeftChild (theNode) = aChildIndex; + else + theBVH->RightChild (theNode) = aChildIndex; + + const Standard_Boolean isLeaf = aNbPimitives <= BVH_Builder::myLeafNodeSize + || theBVH->Level (aChildIndex) >= BVH_Builder::myMaxTreeDepth; + + if (!isLeaf) + BVH_Builder::myTasksQueue.Append (aChildIndex); + } +}