p BSplCLib
p BSplSLib
p Bnd
+p BVH
p CSLib
p Convert
p Dico
--- /dev/null
+// 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.
+
+#include <BVH_Geometry.hxx>
+#include <BVH_Triangulation.hxx>
+#include <BVH_BinnedBuilder.hxx>
+#include <BVH_SweepPlaneBuilder.hxx>
+#include <BVH_SpatialMedianBuilder.hxx>
+
+// Specific instantiations of struct templates to avoid compilation warnings
+
+template class BVH_Box<Standard_Real, 2>;
+template class BVH_Box<Standard_Real, 3>;
+template class BVH_Box<Standard_Real, 4>;
+
+template class BVH_Box<Standard_ShortReal, 2>;
+template class BVH_Box<Standard_ShortReal, 3>;
+template class BVH_Box<Standard_ShortReal, 4>;
+
+template class BVH_Set<Standard_Real, 2>;
+template class BVH_Set<Standard_Real, 3>;
+template class BVH_Set<Standard_Real, 4>;
+
+template class BVH_Set<Standard_ShortReal, 2>;
+template class BVH_Set<Standard_ShortReal, 3>;
+template class BVH_Set<Standard_ShortReal, 4>;
+
+template class BVH_Object<Standard_Real, 2>;
+template class BVH_Object<Standard_Real, 3>;
+template class BVH_Object<Standard_Real, 4>;
+
+template class BVH_Object<Standard_ShortReal, 2>;
+template class BVH_Object<Standard_ShortReal, 3>;
+template class BVH_Object<Standard_ShortReal, 4>;
+
+template class BVH_ObjectSet<Standard_Real, 2>;
+template class BVH_ObjectSet<Standard_Real, 3>;
+template class BVH_ObjectSet<Standard_Real, 4>;
+
+template class BVH_ObjectSet<Standard_ShortReal, 2>;
+template class BVH_ObjectSet<Standard_ShortReal, 3>;
+template class BVH_ObjectSet<Standard_ShortReal, 4>;
+
+template class BVH_Geometry<Standard_Real, 2>;
+template class BVH_Geometry<Standard_Real, 3>;
+template class BVH_Geometry<Standard_Real, 4>;
+
+template class BVH_Geometry<Standard_ShortReal, 2>;
+template class BVH_Geometry<Standard_ShortReal, 3>;
+template class BVH_Geometry<Standard_ShortReal, 4>;
+
+template class BVH_Tree<Standard_Real, 2>;
+template class BVH_Tree<Standard_Real, 3>;
+template class BVH_Tree<Standard_Real, 4>;
+
+template class BVH_Tree<Standard_ShortReal, 2>;
+template class BVH_Tree<Standard_ShortReal, 3>;
+template class BVH_Tree<Standard_ShortReal, 4>;
+
+template class BVH_Builder<Standard_Real, 2>;
+template class BVH_Builder<Standard_Real, 3>;
+template class BVH_Builder<Standard_Real, 4>;
+
+template class BVH_Builder<Standard_ShortReal, 2>;
+template class BVH_Builder<Standard_ShortReal, 3>;
+template class BVH_Builder<Standard_ShortReal, 4>;
+
+template class BVH_BinnedBuilder<Standard_Real, 2>;
+template class BVH_BinnedBuilder<Standard_Real, 3>;
+template class BVH_BinnedBuilder<Standard_Real, 4>;
+
+template class BVH_BinnedBuilder<Standard_ShortReal, 2>;
+template class BVH_BinnedBuilder<Standard_ShortReal, 3>;
+template class BVH_BinnedBuilder<Standard_ShortReal, 4>;
+
+template class BVH_SweepPlaneBuilder<Standard_Real, 2>;
+template class BVH_SweepPlaneBuilder<Standard_Real, 3>;
+template class BVH_SweepPlaneBuilder<Standard_Real, 4>;
+
+template class BVH_SweepPlaneBuilder<Standard_ShortReal, 2>;
+template class BVH_SweepPlaneBuilder<Standard_ShortReal, 3>;
+template class BVH_SweepPlaneBuilder<Standard_ShortReal, 4>;
+
+template class BVH_SpatialMedianBuilder<Standard_Real, 2>;
+template class BVH_SpatialMedianBuilder<Standard_Real, 3>;
+template class BVH_SpatialMedianBuilder<Standard_Real, 4>;
+
+template class BVH_SpatialMedianBuilder<Standard_ShortReal, 2>;
+template class BVH_SpatialMedianBuilder<Standard_ShortReal, 3>;
+template class BVH_SpatialMedianBuilder<Standard_ShortReal, 4>;
+
+template class BVH_PrimitiveSet<Standard_Real, 2>;
+template class BVH_PrimitiveSet<Standard_Real, 3>;
+template class BVH_PrimitiveSet<Standard_Real, 4>;
+
+template class BVH_PrimitiveSet<Standard_ShortReal, 2>;
+template class BVH_PrimitiveSet<Standard_ShortReal, 3>;
+template class BVH_PrimitiveSet<Standard_ShortReal, 4>;
+
+template class BVH_Triangulation<Standard_Real, 2>;
+template class BVH_Triangulation<Standard_Real, 3>;
+template class BVH_Triangulation<Standard_Real, 4>;
+
+template class BVH_Triangulation<Standard_ShortReal, 2>;
+template class BVH_Triangulation<Standard_ShortReal, 3>;
+template class BVH_Triangulation<Standard_ShortReal, 4>;
+
+template class BVH_Transform<Standard_Real, 4>;
+template class BVH_Transform<Standard_ShortReal, 4>;
--- /dev/null
+// 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.
+
+#ifndef _BVH_BinnedBuilder_Header
+#define _BVH_BinnedBuilder_Header
+
+#include <BVH_Builder.hxx>
+
+//! Stores parameters of single node bin (slice of AABB).
+template<class T, int N>
+struct BVH_Bin
+{
+ //! Creates new node bin.
+ BVH_Bin() : Count (0) {}
+
+ Standard_Integer Count; //!< Number of primitives in the bin
+ BVH_Box<T, N> Box; //!< AABB of the bin
+};
+
+//! Performs building of BVH tree using binned SAH algorithm.
+//! Number of Bins controls tree's quality (greater - better) in cost of construction time.
+template<class T, int N, int Bins = 32>
+class BVH_BinnedBuilder : public BVH_Builder<T, N>
+{
+public:
+
+ //! Type for the array of bins of BVH tree node.
+ typedef BVH_Bin<T, N> BVH_BinVector[Bins];
+
+public:
+
+ //! Creates binned SAH BVH builder.
+ BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize = 5,
+ const Standard_Integer theMaxTreeDepth = 32);
+
+ //! Releases resources of binned SAH BVH builder.
+ virtual ~BVH_BinnedBuilder();
+
+protected:
+
+ //! Builds BVH node for specified task info.
+ virtual void BuildNode (BVH_Set<T, N>* theSet,
+ BVH_Tree<T, N>* theBVH,
+ const Standard_Integer theNode);
+
+ //! Arranges node primitives into bins.
+ virtual void GetSubVolumes (BVH_Set<T, N>* theSet,
+ BVH_Tree<T, N>* theBVH,
+ const Standard_Integer theNode,
+ BVH_BinVector& theBins,
+ const Standard_Integer theAxis);
+
+};
+
+#include <BVH_BinnedBuilder.lxx>
+
+#endif // _BVH_BinnedBuilder_Header
--- /dev/null
+// 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<class T, int N, int Bins>
+BVH_BinnedBuilder<T, N, Bins>::BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize,
+ const Standard_Integer theMaxTreeDepth)
+: BVH_Builder<T, N> (theLeafNodeSize,
+ theMaxTreeDepth)
+{
+ //
+}
+
+// =======================================================================
+// function : ~BVH_BinnedBuilder
+// purpose :
+// =======================================================================
+template<class T, int N, int Bins>
+BVH_BinnedBuilder<T, N, Bins>::~BVH_BinnedBuilder()
+{
+ //
+}
+
+// =======================================================================
+// function : GetSubVolumes
+// purpose :
+// =======================================================================
+template<class T, int N, int Bins>
+void BVH_BinnedBuilder<T, N, Bins>::GetSubVolumes (BVH_Set<T, N>* theSet,
+ BVH_Tree<T, N>* theBVH,
+ const Standard_Integer theNode,
+ BVH_BinVector& theBins,
+ const Standard_Integer theAxis)
+{
+ const T aMin = BVHTools::VecComp<T, N>::Get (theBVH->MinPoint (theNode), theAxis);
+ const T aMax = BVHTools::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), theAxis);
+
+ const T anInvStep = static_cast<T> (Bins) / (aMax - aMin);
+
+ for (Standard_Integer anIdx = theBVH->BegPrimitive (theNode); anIdx <= theBVH->EndPrimitive (theNode); ++anIdx)
+ {
+ typename BVH_Set<T, N>::BVH_BoxNt aBox = theSet->Box (anIdx);
+
+ Standard_Integer aBinIndex = static_cast<Standard_Integer> (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<class T, int N>
+ Standard_Integer SplitPrimitives (BVH_Set<T, N>* theSet,
+ const BVH_Box<T, N>& 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<T, N>::Get (theBox.CornerMin(), theAxis);
+ const T aMax = BVHTools::VecComp<T, N>::Get (theBox.CornerMax(), theAxis);
+
+ const T anInvStep = static_cast<T> (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 <limits>
+
+// =======================================================================
+// function : BuildNode
+// purpose :
+// =======================================================================
+template<class T, int N, int Bins>
+void BVH_BinnedBuilder<T, N, Bins>::BuildNode (BVH_Set<T, N>* theSet,
+ BVH_Tree<T, N>* theBVH,
+ const Standard_Integer theNode)
+{
+ const BVH_Box<T, N> aBox (theBVH->MinPoint (theNode),
+ theBVH->MaxPoint (theNode));
+
+ const typename BVH_Box<T, N>::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<T, N> aMinSplitBoxLft;
+ BVH_Box<T, N> aMinSplitBoxRgh;
+
+ Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
+
+ // Find best split
+ for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
+ {
+ if (BVHTools::VecComp<T, N>::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<T, N> aLftAABB;
+ BVH_Box<T, N> 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<Standard_Real> (aLftAABB.Area()) /* / aNodeArea */) * aLftCount
+ + (static_cast<Standard_Real> (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<T, N> (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<T, N>::BVH_VecNt aMinPoint = (aSide == aLftNode)
+ ? aMinSplitBoxLft.CornerMin()
+ : aMinSplitBoxRgh.CornerMin();
+ typename BVH_Box<T, N>::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<T, N>::myLeafNodeSize
+ || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
+
+ if (!isLeaf)
+ BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
+ }
+}
--- /dev/null
+// 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.
+
+#ifndef _BVH_Box_Header
+#define _BVH_Box_Header
+
+#include <BVH_Types.hxx>
+
+//! Axis aligned bounding box (AABB).
+template<class T, int N>
+class BVH_Box
+{
+public:
+
+ typedef typename BVHTools::VectorType<T, N>::Type BVH_VecNt;
+
+public:
+
+ //! Creates uninitialized bounding box.
+ BVH_Box() : myInitialized (Standard_False) {}
+
+ //! Creates bounding box of given point.
+ BVH_Box (const BVH_VecNt& thePoint)
+ : myMinPoint (thePoint),
+ myMaxPoint (thePoint),
+ myInitialized (Standard_True) {}
+
+ //! Creates copy of another bounding box.
+ BVH_Box (const BVH_Box& theBox)
+ : myMinPoint (theBox.myMinPoint),
+ myMaxPoint (theBox.myMaxPoint),
+ myInitialized (theBox.myInitialized) {}
+
+ //! Creates bounding box from corner points.
+ BVH_Box (const BVH_VecNt& theMinPoint,
+ const BVH_VecNt& theMaxPoint)
+ : myMinPoint (theMinPoint),
+ myMaxPoint (theMaxPoint),
+ myInitialized (Standard_True) {}
+
+public:
+
+ //! Clears bounding box.
+ void Clear();
+
+ //! Is bounding box valid?
+ Standard_Boolean IsValid() const;
+
+ //! Appends new point to the bounding box.
+ void Add (const BVH_VecNt& thePoint);
+
+ //! Combines bounding box with another one.
+ void Combine (const BVH_Box& theVolume);
+
+ //! Returns minimum point of bounding box.
+ const BVH_VecNt& CornerMin() const;
+
+ //! Returns maximum point of bounding box.
+ const BVH_VecNt& CornerMax() const;
+
+ //! Returns minimum point of bounding box.
+ BVH_VecNt& CornerMin();
+
+ //! Returns maximum point of bounding box.
+ BVH_VecNt& CornerMax();
+
+ //! Returns surface area of bounding box.
+ T Area() const;
+
+ //! Returns diagonal of bounding box.
+ BVH_VecNt Size() const;
+
+ //! Returns center of bounding box.
+ BVH_VecNt Center() const;
+
+protected:
+
+ BVH_VecNt myMinPoint; //!< Minimum point of bounding box
+ BVH_VecNt myMaxPoint; //!< Maximum point of bounding box
+ Standard_Boolean myInitialized; //!< Is bounding box valid?
+
+};
+
+#include <BVH_Box.lxx>
+
+#endif // _BVH_Box_Header
--- /dev/null
+// 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.
+
+#include <Standard_ShortReal.hxx>
+
+namespace BVHTools
+{
+ template<class T, int N>
+ struct CenterAxis {
+ // Not implemented
+ };
+
+ template<class T>
+ struct CenterAxis<T, 2>
+ {
+ static T Center (const BVH_Box<T, 2>& theBox,
+ const Standard_Integer theAxis)
+ {
+ if (theAxis == 0)
+ {
+ return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
+ }
+ else if (theAxis == 1)
+ {
+ return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
+ }
+ return static_cast<T> (0.0);
+ }
+ };
+
+ template<class T>
+ struct CenterAxis<T, 3>
+ {
+ static T Center (const BVH_Box<T, 3>& theBox,
+ const Standard_Integer theAxis)
+ {
+ if (theAxis == 0)
+ {
+ return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
+ }
+ else if (theAxis == 1)
+ {
+ return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
+ }
+ else if (theAxis == 2)
+ {
+ return (theBox.CornerMin().z() + theBox.CornerMax().z()) * static_cast<T> (0.5);
+ }
+ return static_cast<T> (0.0);
+ }
+ };
+
+ template<class T>
+ struct CenterAxis<T, 4>
+ {
+ static T Center (const BVH_Box<T, 4>& theBox,
+ const Standard_Integer theAxis)
+ {
+ if (theAxis == 0)
+ {
+ return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
+ }
+ else if (theAxis == 1)
+ {
+ return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
+ }
+ else if (theAxis == 2)
+ {
+ return (theBox.CornerMin().z() + theBox.CornerMax().z()) * static_cast<T> (0.5);
+ }
+ return static_cast<T> (0.0);
+ }
+ };
+}
+
+// =======================================================================
+// function : Clear
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Box<T, N>::Clear()
+{
+ myInitialized = Standard_False;
+}
+
+// =======================================================================
+// function : Clear
+// purpose :
+// =======================================================================
+template<class T, int N>
+Standard_Boolean BVH_Box<T, N>::IsValid() const
+{
+ return myInitialized;
+}
+
+// =======================================================================
+// function : Add
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Box<T, N>::Add (const BVH_VecNt& thePoint)
+{
+ if (!myInitialized)
+ {
+ myMinPoint = thePoint;
+ myMaxPoint = thePoint;
+
+ myInitialized = Standard_True;
+ }
+ else
+ {
+ myMinPoint = myMinPoint.cwiseMin (thePoint);
+ myMaxPoint = myMaxPoint.cwiseMax (thePoint);
+ }
+}
+
+// =======================================================================
+// function : Combine
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Box<T, N>::Combine (const BVH_Box& theBox)
+{
+ if (!theBox.myInitialized)
+ {
+ return;
+ }
+
+ if (!myInitialized)
+ {
+ myMinPoint = theBox.myMinPoint;
+ myMaxPoint = theBox.myMaxPoint;
+
+ myInitialized = Standard_True;
+ }
+ else
+ {
+ myMinPoint = myMinPoint.cwiseMin (theBox.myMinPoint);
+ myMaxPoint = myMaxPoint.cwiseMax (theBox.myMaxPoint);
+ }
+}
+
+namespace BVHTools
+{
+ template<class T, int N>
+ struct SurfaceCalculator
+ {
+ // Not implemented
+ };
+
+ template<class T>
+ struct SurfaceCalculator<T, 2>
+ {
+ static T Area (const typename BVH_Box<T, 2>::BVH_VecNt& theSize)
+ {
+ return theSize.x() * theSize.y();
+ }
+ };
+
+ template<class T>
+ struct SurfaceCalculator<T, 3>
+ {
+ static T Area (const typename BVH_Box<T, 3>::BVH_VecNt& theSize)
+ {
+ return ( theSize.x() * theSize.y() +
+ theSize.x() * theSize.z() +
+ theSize.z() * theSize.y() ) * static_cast<T> (2.0);
+ }
+ };
+
+ template<class T>
+ struct SurfaceCalculator<T, 4>
+ {
+ static T Area (const typename BVH_Box<T, 4>::BVH_VecNt& theSize)
+ {
+ return ( theSize.x() * theSize.y() +
+ theSize.x() * theSize.z() +
+ theSize.z() * theSize.y() ) * static_cast<T> (2.0);
+ }
+ };
+}
+
+// =======================================================================
+// function : Area
+// purpose :
+// =======================================================================
+template<class T, int N>
+T BVH_Box<T, N>::Area() const
+{
+ return BVHTools::SurfaceCalculator<T, N>::Area (myMaxPoint - myMinPoint);
+}
+
+// =======================================================================
+// function : CornerMin
+// purpose :
+// =======================================================================
+template<class T, int N>
+const typename BVH_Box<T, N>::BVH_VecNt& BVH_Box<T, N>::CornerMin() const
+{
+ return myMinPoint;
+}
+
+// =======================================================================
+// function : CornerMax
+// purpose :
+// =======================================================================
+template<class T, int N>
+const typename BVH_Box<T, N>::BVH_VecNt& BVH_Box<T, N>::CornerMax() const
+{
+ return myMaxPoint;
+}
+
+// =======================================================================
+// function : CornerMin
+// purpose :
+// =======================================================================
+template<class T, int N>
+typename BVH_Box<T, N>::BVH_VecNt& BVH_Box<T, N>::CornerMin()
+{
+ return myMinPoint;
+}
+
+// =======================================================================
+// function : CornerMax
+// purpose :
+// =======================================================================
+template<class T, int N>
+typename BVH_Box<T, N>::BVH_VecNt& BVH_Box<T, N>::CornerMax()
+{
+ return myMaxPoint;
+}
+
+// =======================================================================
+// function : Size
+// purpose :
+// =======================================================================
+template<class T, int N>
+typename BVH_Box<T, N>::BVH_VecNt BVH_Box<T, N>::Size() const
+{
+ return myMaxPoint - myMinPoint;
+}
+
+// =======================================================================
+// function : Center
+// purpose :
+// =======================================================================
+template<class T, int N>
+typename BVH_Box<T, N>::BVH_VecNt BVH_Box<T, N>::Center() const
+{
+ return (myMinPoint + myMaxPoint) * static_cast<T> (0.5);
+}
--- /dev/null
+// 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.
+
+#ifndef _BVH_Builder_Header
+#define _BVH_Builder_Header
+
+#include <BVH_Set.hxx>
+#include <BVH_Tree.hxx>
+
+#include <NCollection_Vector.hxx>
+
+namespace
+{
+ //! Minimum node size to split.
+ const Standard_Real THE_NODE_MIN_SIZE = 1e-5;
+}
+
+//! Performs building of BVH tree.
+template<class T, int N>
+class BVH_Builder
+{
+public:
+
+ //! Creates abstract BVH builder.
+ BVH_Builder (const Standard_Integer theLeafNodeSize,
+ const Standard_Integer theMaxTreeDepth);
+
+ //! Releases resources of BVH builder.
+ virtual ~BVH_Builder() = 0;
+
+public:
+
+ //! Builds BVH using specified algorithm.
+ void Build (BVH_Set<T, N>* theSet,
+ BVH_Tree<T, N>* theBVH,
+ const BVH_Box<T, N>& theBox);
+
+protected:
+
+ //! Builds BVH node for specified task info.
+ virtual void BuildNode (BVH_Set<T, N>* theSet,
+ BVH_Tree<T, N>* theBVH,
+ const Standard_Integer theTask);
+
+protected:
+
+ Standard_Integer myMaxTreeDepth; //!< Maximum depth of constructed BVH
+ Standard_Integer myLeafNodeSize; //!< Maximum number of primitives per leaf
+ NCollection_Vector<Standard_Integer> myTasksQueue; //!< Queue to manage BVH node building tasks
+
+};
+
+#include <BVH_Builder.lxx>
+
+#endif // _BVH_Builder_Header
--- /dev/null
+// 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_Builder
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Builder<T, N>::BVH_Builder (const Standard_Integer theLeafNodeSize,
+ const Standard_Integer theMaxTreeDepth)
+: myMaxTreeDepth (theMaxTreeDepth),
+ myLeafNodeSize (theLeafNodeSize)
+{
+ //
+}
+
+// =======================================================================
+// function : ~BVH_Builder
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Builder<T, N>::~BVH_Builder()
+{
+ //
+}
+
+// =======================================================================
+// function : Build
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Builder<T, N>::Build (BVH_Set<T, N>* theSet,
+ BVH_Tree<T, N>* theBVH,
+ const BVH_Box<T, N>& theBox)
+{
+ if (theBVH == NULL)
+ {
+ return;
+ }
+
+ theBVH->Clear();
+ if (theSet->Size() == 0)
+ {
+ return;
+ }
+
+ const Standard_Integer aRoot = theBVH->AddLeafNode (theBox, 0, theSet->Size() - 1);
+ if (theSet->Size() == 1)
+ {
+ return;
+ }
+
+ myTasksQueue.Append (aRoot);
+ for (Standard_Integer aTask = 0; aTask < myTasksQueue.Size(); ++aTask)
+ {
+ BuildNode (theSet, theBVH, myTasksQueue.Value (aTask));
+ }
+
+ myTasksQueue.Clear();
+}
+
+// =======================================================================
+// function : BuildNode
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Builder<T, N>::BuildNode (BVH_Set<T, N>* ,
+ BVH_Tree<T, N>* ,
+ const Standard_Integer )
+{
+ // need to disable compile warnings
+}
--- /dev/null
+// 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.
+
+#ifndef _BVH_Geometry_Header
+#define _BVH_Geometry_Header
+
+#include <BVH_ObjectSet.hxx>
+#include <BVH_Builder.hxx>
+
+//! BVH geometry as a set of abstract geometric objects.
+template<class T, int N>
+class BVH_Geometry : public BVH_ObjectSet<T, N>
+{
+public:
+
+ //! Creates uninitialized BVH geometry.
+ BVH_Geometry();
+
+ //! Releases resources of BVH geometry.
+ virtual ~BVH_Geometry();
+
+public:
+
+ //! Marks geometry as outdated.
+ virtual void MarkDirty();
+
+ //! Returns AABB of whole geometry.
+ virtual BVH_Box<T, N> Box() const;
+
+ //! Returns constructed BVH tree.
+ virtual const NCollection_Handle<BVH_Tree<T, N> >& BVH();
+
+ //! Returns the method (builder) to construct BVH.
+ virtual const NCollection_Handle<BVH_Builder<T, N> >& Builder() const;
+
+ //! Sets the method (builder) to construct BVH.
+ virtual void SetBuilder (NCollection_Handle<BVH_Builder<T, N> >& theBuilder);
+
+protected:
+
+ //! Updates internal geometry state.
+ virtual void Update();
+
+protected:
+
+ Standard_Boolean myIsDirty; //!< Is geometry state outdated?
+ NCollection_Handle<BVH_Tree<T, N> > myBVH; //!< Constructed hight-level BVH
+ NCollection_Handle<BVH_Builder<T, N> > myBuilder; //!< Builder for hight-level BVH
+
+ mutable BVH_Box<T, N> myBox; //!< Cached bounding box of geometric objects
+
+};
+
+#include <BVH_Geometry.lxx>
+
+#endif // _BVH_Geometry_Header
--- /dev/null
+// 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.
+
+#include <BVH_BinnedBuilder.hxx>
+
+// =======================================================================
+// function : BVH_Geometry
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Geometry<T, N>::BVH_Geometry()
+: myIsDirty (Standard_False),
+ myBVH (new BVH_Tree<T, N>())
+{
+ // Set default builder - binned SAH split
+ myBuilder = new BVH_BinnedBuilder<T, N, 32> (1 /* primitive per leaf */);
+}
+
+// =======================================================================
+// function : ~BVH_Geometry
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Geometry<T, N>::~BVH_Geometry()
+{
+ myBVH.Nullify();
+ myBuilder.Nullify();
+}
+
+// =======================================================================
+// function : MarkDirty
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Geometry<T, N>::MarkDirty()
+{
+ myIsDirty = Standard_True;
+}
+
+// =======================================================================
+// function : Box
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Box<T, N> BVH_Geometry<T, N>::Box() const
+{
+ if (!myIsDirty)
+ {
+ return myBox;
+ }
+
+ myBox = BVH_Set<T, N>::Box();
+ return myBox;
+}
+
+// =======================================================================
+// function : BVH
+// purpose :
+// =======================================================================
+template<class T, int N>
+const NCollection_Handle<BVH_Tree<T, N> >& BVH_Geometry<T, N>::BVH()
+{
+ if (myIsDirty)
+ {
+ Update();
+ }
+
+ return myBVH;
+}
+
+// =======================================================================
+// function : Update
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Geometry<T, N>::Update()
+{
+ if (!myIsDirty)
+ {
+ return;
+ }
+
+ BVH_Box<T, N> aBox;
+ for (Standard_Integer anIndex = 0; anIndex < BVH_ObjectSet<T, N>::myObjects.Size(); ++anIndex)
+ {
+ aBox.Combine (BVH_ObjectSet<T, N>::myObjects.Value (anIndex)->Box());
+ }
+
+ myBuilder->Build (this, myBVH.operator->(), aBox);
+ myIsDirty = Standard_False;
+}
+
+// =======================================================================
+// function : Builder
+// purpose :
+// =======================================================================
+template<class T, int N>
+const NCollection_Handle<BVH_Builder<T, N> >& BVH_Geometry<T, N>::Builder() const
+{
+ return myBuilder;
+}
+
+// =======================================================================
+// function : SetBuilder
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Geometry<T, N>::SetBuilder (NCollection_Handle<BVH_Builder<T, N> >& theBuilder)
+{
+ myBuilder = theBuilder;
+}
--- /dev/null
+// 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.
+
+#ifndef _BVH_Object_Header
+#define _BVH_Object_Header
+
+#include <BVH_Box.hxx>
+#include <BVH_Properties.hxx>
+
+#include <NCollection_Handle.hxx>
+
+//! Abstract geometric object.
+template<class T, int N>
+class BVH_Object
+{
+public:
+
+ //! Creates new abstract geometric object.
+ BVH_Object();
+
+ //! Releases resources of geometric object.
+ virtual ~BVH_Object() = 0;
+
+public:
+
+ //! Returns AABB of geometric object.
+ virtual BVH_Box<T, N> Box() const = 0;
+
+ //! Returns properties of geometric object.
+ virtual const NCollection_Handle<BVH_Properties>& Properties() const;
+
+ //! Sets properties of geometric object.
+ virtual void SetProperties (const NCollection_Handle<BVH_Properties>& theProperties);
+
+ //! Marks object state as outdated.
+ virtual void MarkDirty();
+
+protected:
+
+ Standard_Boolean myIsDirty; //!< Marks that internal object state need to be updated
+ NCollection_Handle<BVH_Properties> myProperties; //!< Generic properties assigned to the object
+
+};
+
+#include <BVH_Object.lxx>
+
+#endif // _BVH_Object_Header
--- /dev/null
+// 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_Object
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Object<T, N>::BVH_Object()
+: myIsDirty (Standard_False)
+{
+ //
+}
+
+// =======================================================================
+// function : ~BVH_Object
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Object<T, N>::~BVH_Object()
+{
+ //
+}
+
+// =======================================================================
+// function : Properties
+// purpose :
+// =======================================================================
+template<class T, int N>
+const NCollection_Handle<BVH_Properties>& BVH_Object<T, N>::Properties() const
+{
+ return myProperties;
+}
+
+// =======================================================================
+// function : SetProperties
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Object<T, N>::SetProperties (const NCollection_Handle<BVH_Properties>& theProperties)
+{
+ myProperties = theProperties;
+}
+
+// =======================================================================
+// function : MarkDirty
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Object<T, N>::MarkDirty()
+{
+ myIsDirty = Standard_True;
+}
--- /dev/null
+// 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.
+
+#ifndef _BVH_ObjectSet_Header
+#define _BVH_ObjectSet_Header
+
+#include <BVH_Set.hxx>
+#include <BVH_Object.hxx>
+
+#include <NCollection_Vector.hxx>
+
+//! Set of abstract geometric objects to build BVH.
+template<class T, int N>
+class BVH_ObjectSet : public BVH_Set<T, N>
+{
+public:
+
+ //! Type for array of geometric objects.
+ typedef NCollection_Vector<NCollection_Handle<BVH_Object<T, N> > > BVH_ObjectList;
+
+public:
+
+ //! Creates set of geometric objects.
+ BVH_ObjectSet();
+
+ //! Releases resources of set of geometric objects.
+ virtual ~BVH_ObjectSet();
+
+public:
+
+ //! Clears all geometric objects.
+ virtual void Clear();
+
+ //! Returns array of geometric objects.
+ BVH_ObjectList& Objects();
+
+ //! Returns array of geometric objects.
+ const BVH_ObjectList& Objects() const;
+
+public:
+
+ //! Return total number of objects.
+ virtual Standard_Integer Size() const;
+
+ //! Returns AABB of specified object.
+ virtual BVH_Box<T, N> Box (const Standard_Integer theIndex) const;
+
+ //! Returns centroid position in specified axis.
+ virtual T Center (const Standard_Integer theIndex, const Standard_Integer theAxis) const;
+
+ //! Swaps indices of two specified objects in the set.
+ virtual void Swap (const Standard_Integer theIndex1, const Standard_Integer theIndex2);
+
+protected:
+
+ BVH_ObjectList myObjects; //!< Array of geometric objects
+
+};
+
+#include <BVH_ObjectSet.lxx>
+
+#endif // _BVH_ObjectSet_Header
--- /dev/null
+// 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_ObjectSet
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_ObjectSet<T, N>::BVH_ObjectSet()
+{
+ //
+}
+
+// =======================================================================
+// function : ~BVH_ObjectSet
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_ObjectSet<T, N>::~BVH_ObjectSet()
+{
+ //
+}
+
+// =======================================================================
+// function : Clears all geometric objects
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_ObjectSet<T, N>::Clear()
+{
+ for (Standard_Integer anObjectIdx = 0; anObjectIdx < myObjects.Size(); ++anObjectIdx)
+ {
+ myObjects.ChangeValue (anObjectIdx).Nullify();
+ }
+ myObjects.Clear();
+}
+
+// =======================================================================
+// function : Objects
+// purpose :
+// =======================================================================
+template<class T, int N>
+typename BVH_ObjectSet<T, N>::BVH_ObjectList& BVH_ObjectSet<T, N>::Objects()
+{
+ return myObjects;
+}
+
+// =======================================================================
+// function : Objects
+// purpose :
+// =======================================================================
+template<class T, int N>
+const typename BVH_ObjectSet<T, N>::BVH_ObjectList& BVH_ObjectSet<T, N>::Objects() const
+{
+ return myObjects;
+}
+
+// =======================================================================
+// function : Size
+// purpose :
+// =======================================================================
+template<class T, int N>
+Standard_Integer BVH_ObjectSet<T, N>::Size() const
+{
+ return myObjects.Size();
+}
+
+// =======================================================================
+// function : Box
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Box<T, N> BVH_ObjectSet<T, N>::Box (const Standard_Integer theIndex) const
+{
+ return myObjects.Value (theIndex)->Box();
+}
+
+// =======================================================================
+// function : Center
+// purpose :
+// =======================================================================
+template<class T, int N>
+T BVH_ObjectSet<T, N>::Center (const Standard_Integer theIndex,
+ const Standard_Integer theAxis) const
+{
+ typename BVH_Set<T, N>::BVH_BoxNt aBox = myObjects.Value (theIndex)->Box();
+ return BVHTools::CenterAxis<T, N>::Center (aBox, theAxis);
+}
+
+// =======================================================================
+// function : Swap
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_ObjectSet<T, N>::Swap (const Standard_Integer theIndex1,
+ const Standard_Integer theIndex2)
+{
+ NCollection_Handle<BVH_Object<T, N> > anObject1 = myObjects.Value (theIndex1);
+ NCollection_Handle<BVH_Object<T, N> > anObject2 = myObjects.Value (theIndex2);
+
+ myObjects.ChangeValue (theIndex1) = anObject2;
+ myObjects.ChangeValue (theIndex2) = anObject1;
+}
--- /dev/null
+// 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.
+
+#ifndef _BVH_PrimitiveSet_Header
+#define _BVH_PrimitiveSet_Header
+
+#include <BVH_Object.hxx>
+#include <BVH_Builder.hxx>
+
+//! Set of abstract geometric primitives.
+template<class T, int N>
+class BVH_PrimitiveSet : public BVH_Object<T, N>, public BVH_Set<T, N>
+{
+ using BVH_Set<T, N>::Box;
+
+public:
+
+ //! Creates set of abstract primitives.
+ BVH_PrimitiveSet();
+
+ //! Releases resources of set of abstract primitives.
+ virtual ~BVH_PrimitiveSet();
+
+public:
+
+ //! Returns AABB of primitive set.
+ virtual BVH_Box<T, N> Box() const;
+
+ //! Returns constructed BVH tree.
+ virtual const NCollection_Handle<BVH_Tree<T, N> >& BVH();
+
+ //! Returns the method (builder) to construct BVH.
+ virtual const NCollection_Handle<BVH_Builder<T, N> >& Builder() const;
+
+ //! Sets the method (builder) to construct BVH.
+ virtual void SetBuilder (NCollection_Handle<BVH_Builder<T, N> >& theBuilder);
+
+protected:
+
+ //! Updates BVH of primitive set.
+ virtual void Update();
+
+protected:
+
+ NCollection_Handle<BVH_Tree<T, N> > myBVH; //!< Constructed bottom-level BVH
+ NCollection_Handle<BVH_Builder<T, N> > myBuilder; //!< Builder for bottom-level BVH
+
+ mutable BVH_Box<T, N> myBox; //!< Cached bounding box of geometric primitives
+
+};
+
+#include <BVH_PrimitiveSet.lxx>
+
+#endif // _BVH_PrimitiveSet_Header
--- /dev/null
+// 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.
+
+#include <BVH_BinnedBuilder.hxx>
+
+// =======================================================================
+// function : BVH_PrimitiveSet
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_PrimitiveSet<T, N>::BVH_PrimitiveSet()
+: myBVH (new BVH_Tree<T, N>())
+{
+ // Set default builder - binned SAH split
+ myBuilder = new BVH_BinnedBuilder<T, N, 48> (5, 32);
+}
+
+// =======================================================================
+// function : ~BVH_PrimitiveSet
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_PrimitiveSet<T, N>::~BVH_PrimitiveSet()
+{
+ myBVH.Nullify();
+ myBuilder.Nullify();
+}
+
+// =======================================================================
+// function : BVH
+// purpose :
+// =======================================================================
+template<class T, int N>
+const NCollection_Handle<BVH_Tree<T, N> >& BVH_PrimitiveSet<T, N>::BVH()
+{
+ if (BVH_Object<T, N>::myIsDirty)
+ {
+ Update();
+ }
+
+ return myBVH;
+}
+
+// =======================================================================
+// function : Box
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Box<T, N> BVH_PrimitiveSet<T, N>::Box() const
+{
+ if (!BVH_Object<T, N>::myIsDirty)
+ {
+ return myBox;
+ }
+
+ myBox = BVH_Set<T, N>::Box();
+ return myBox;
+}
+
+// =======================================================================
+// function : Update
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_PrimitiveSet<T, N>::Update()
+{
+ if (!BVH_Object<T, N>::myIsDirty)
+ {
+ return;
+ }
+
+ myBuilder->Build (this, myBVH.operator->(), Box());
+ BVH_Object<T, N>::myIsDirty = Standard_False;
+}
+
+// =======================================================================
+// function : Builder
+// purpose :
+// =======================================================================
+template<class T, int N>
+const NCollection_Handle<BVH_Builder<T, N> >& BVH_PrimitiveSet<T, N>::Builder() const
+{
+ return myBuilder;
+}
+
+// =======================================================================
+// function : SetBuilder
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_PrimitiveSet<T, N>::SetBuilder (NCollection_Handle<BVH_Builder<T, N> >& theBuilder)
+{
+ myBuilder = theBuilder;
+}
--- /dev/null
+// 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.
+
+#include <BVH_Properties.hxx>
+
+//! Abstract properties of geometric object.
+BVH_Properties::~BVH_Properties()
+{
+ //
+}
\ No newline at end of file
--- /dev/null
+// 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.
+
+#ifndef _BVH_Properties_Header
+#define _BVH_Properties_Header
+
+#include <BVH_Box.hxx>
+
+#include <Standard_Macro.hxx>
+
+//! Abstract properties of geometric object.
+class BVH_Properties
+{
+public:
+
+ //! Releases resources of object properties.
+ Standard_EXPORT virtual ~BVH_Properties() = 0;
+
+};
+
+//! Stores transform properties of geometric object.
+template<class T, int N>
+class BVH_Transform : public BVH_Properties
+{
+public:
+
+ //! Type of transformation matrix.
+ typedef typename BVHTools::MatrixType<T, N>::Type BVH_MatNt;
+
+public:
+
+ //! Creates new identity transformation.
+ BVH_Transform();
+
+ //! Creates new transformation with specified matrix.
+ BVH_Transform (const BVH_MatNt& theTransform);
+
+ //! Releases resources of transformation properties.
+ virtual ~BVH_Transform();
+
+ //! Returns transformation matrix.
+ const BVH_MatNt& Transform() const;
+
+ //! Sets new transformation matrix.
+ void SetTransform (const BVH_MatNt& theTransform);
+
+ //! Returns inversed transformation matrix.
+ const BVH_MatNt& Inversed() const;
+
+ //! Applies transformation matrix to bounding box.
+ BVH_Box<T, N> Apply (const BVH_Box<T, N>& theBox) const;
+
+protected:
+
+ BVH_MatNt myTransform; //!< Transformation matrix
+ BVH_MatNt myTransformInversed; //!< Inversed transformation matrix
+
+};
+
+#include <BVH_Properties.lxx>
+
+#endif // _BVH_Properties_Header
--- /dev/null
+// 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_Transform
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Transform<T, N>::BVH_Transform()
+{
+ //
+}
+
+// =======================================================================
+// function : BVH_Transform
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Transform<T, N>::BVH_Transform (const BVH_MatNt& theTransform)
+: myTransform (theTransform)
+{
+ //
+}
+
+// =======================================================================
+// function : ~BVH_Transform
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Transform<T, N>::~BVH_Transform()
+{
+ //
+}
+
+// =======================================================================
+// function : Transform
+// purpose :
+// =======================================================================
+template<class T, int N>
+const typename BVH_Transform<T, N>::BVH_MatNt& BVH_Transform<T, N>::Transform() const
+{
+ return myTransform;
+}
+
+namespace BVHTools
+{
+ template<class T, int N> struct MatrixOp
+ {
+ // Not implemented
+ };
+
+ template<class T> struct MatrixOp<T, 4>
+ {
+ typedef typename BVHTools::MatrixType<T, 4>::Type BVH_Mat4t;
+
+ static void Inverse (const BVH_Mat4t& theIn,
+ BVH_Mat4t& theOut)
+ {
+ theIn.Inverted (theOut);
+ }
+
+ typedef typename BVHTools::VectorType<T, 4>::Type BVH_Vec4t;
+
+ static BVH_Vec4t Multiply (const BVH_Mat4t& theMat,
+ const BVH_Vec4t& theVec)
+ {
+ BVH_Vec4t aOut = theMat * theVec;
+ return aOut * static_cast<T> (1.0 / aOut.w());
+ }
+ };
+}
+
+// =======================================================================
+// function : SetTransform
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Transform<T, N>::SetTransform (const BVH_MatNt& theTransform)
+{
+ myTransform = theTransform;
+ BVHTools::MatrixOp<T, N>::Inverse (myTransform, myTransformInversed);
+}
+
+// =======================================================================
+// function : Inversed
+// purpose :
+// =======================================================================
+template<class T, int N>
+const typename BVH_Transform<T, N>::BVH_MatNt& BVH_Transform<T, N>::Inversed() const
+{
+ return myTransformInversed;
+}
+
+namespace BVHTools
+{
+ template<class T, int N>
+ struct UnitVector
+ {
+ // Not implemented
+ };
+
+ template<class T>
+ struct UnitVector<T, 2>
+ {
+ typedef typename BVHTools::VectorType<T, 2>::Type BVH_Vec2t;
+
+ static BVH_Vec2t DX()
+ {
+ return BVH_Vec2t (static_cast<T> (1.0),
+ static_cast<T> (0.0));
+ }
+
+ static BVH_Vec2t DY()
+ {
+ return BVH_Vec2t (static_cast<T> (0.0),
+ static_cast<T> (1.0));
+ }
+
+ static BVH_Vec2t DZ()
+ {
+ return BVH_Vec2t (static_cast<T> (0.0),
+ static_cast<T> (0.0));
+ }
+ };
+
+ template<class T>
+ struct UnitVector<T, 3>
+ {
+ typedef typename BVHTools::VectorType<T, 3>::Type BVH_Vec3t;
+
+ static BVH_Vec3t DX()
+ {
+ return BVH_Vec3t (static_cast<T> (1.0),
+ static_cast<T> (0.0),
+ static_cast<T> (0.0));
+ }
+
+ static BVH_Vec3t DY()
+ {
+ return BVH_Vec3t (static_cast<T> (0.0),
+ static_cast<T> (1.0),
+ static_cast<T> (0.0));
+ }
+
+ static BVH_Vec3t DZ()
+ {
+ return BVH_Vec3t (static_cast<T> (0.0),
+ static_cast<T> (0.0),
+ static_cast<T> (1.0));
+ }
+ };
+
+ template<class T>
+ struct UnitVector<T, 4>
+ {
+ typedef typename BVHTools::VectorType<T, 4>::Type BVH_Vec4t;
+
+ static BVH_Vec4t DX()
+ {
+ return BVH_Vec4t (static_cast<T> (1.0),
+ static_cast<T> (0.0),
+ static_cast<T> (0.0),
+ static_cast<T> (0.0));
+ }
+
+ static BVH_Vec4t DY()
+ {
+ return BVH_Vec4t (static_cast<T> (0.0),
+ static_cast<T> (1.0),
+ static_cast<T> (0.0),
+ static_cast<T> (0.0));
+ }
+
+ static BVH_Vec4t DZ()
+ {
+ return BVH_Vec4t (static_cast<T> (0.0),
+ static_cast<T> (0.0),
+ static_cast<T> (1.0),
+ static_cast<T> (0.0));
+ }
+ };
+}
+
+// =======================================================================
+// function : Apply
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Box<T, N> BVH_Transform<T, N>::Apply (const BVH_Box<T, N>& theBox) const
+{
+ typename BVH_Box<T, N>::BVH_VecNt aSize = theBox.Size();
+
+ BVH_Box<T, N> aBox;
+ for (Standard_Integer aX = 0; aX <= 1; ++aX)
+ {
+ for (Standard_Integer aY = 0; aY <= 1; ++aY)
+ {
+ for (Standard_Integer aZ = 0; aZ <= 1; ++aZ)
+ {
+ typename BVH_Box<T, N>::BVH_VecNt aCorner = theBox.CornerMin() +
+ BVHTools::UnitVector<T, N>::DX() * aSize * static_cast<T> (aX) +
+ BVHTools::UnitVector<T, N>::DY() * aSize * static_cast<T> (aY) +
+ BVHTools::UnitVector<T, N>::DZ() * aSize * static_cast<T> (aZ);
+
+ aBox.Add (BVHTools::MatrixOp<T, N>::Multiply (myTransform, aCorner));
+ }
+ }
+ }
+
+ return aBox;
+}
--- /dev/null
+// 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.
+
+#ifndef _BVH_Set_Header
+#define _BVH_Set_Header
+
+#include <BVH_Box.hxx>
+
+//! Set of abstract entities to build BVH.
+template<class T, int N>
+class BVH_Set
+{
+public:
+
+ typedef BVH_Box<T, N> BVH_BoxNt;
+
+public:
+
+ //! Creates new abstract set of objects.
+ BVH_Set();
+
+ //! Releases resources of set of objects.
+ virtual ~BVH_Set() = 0;
+
+ //! Returns AABB of entire set of objects.
+ virtual BVH_Box<T, N> Box() const;
+
+public:
+
+ //! Return total number of objects.
+ virtual Standard_Integer Size() const = 0;
+
+ //! Returns AABB of specified object.
+ virtual BVH_Box<T, N> Box (const Standard_Integer theIndex) const = 0;
+
+ //! Returns centroid position in specified axis.
+ virtual T Center (const Standard_Integer theIndex,
+ const Standard_Integer theAxis) const = 0;
+
+ //! Swaps indices of two specified objects in the set.
+ virtual void Swap (const Standard_Integer theIndex1,
+ const Standard_Integer theIndex2) = 0;
+
+};
+
+#include <BVH_Set.lxx>
+
+#endif // _BVH_Set_Header
--- /dev/null
+// 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_Set
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Set<T, N>::BVH_Set()
+{
+ //
+}
+
+// =======================================================================
+// function : ~BVH_Set
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Set<T, N>::~BVH_Set()
+{
+ //
+}
+
+// =======================================================================
+// function : Box
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Box<T, N> BVH_Set<T, N>::Box() const
+{
+ BVH_Box<T, N> aBox;
+ for (Standard_Integer anIndex = 0; anIndex < Size(); ++anIndex)
+ {
+ aBox.Combine (Box (anIndex));
+ }
+ return aBox;
+}
--- /dev/null
+// Created on: 2014-01-10
+// 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.
+
+#ifndef _BVH_Sorter_Header
+#define _BVH_Sorter_Header
+
+#include <BVH_Set.hxx>
+
+//! Performs centroid-based sorting of abstract set.
+template<class T, int N>
+class BVH_Sorter
+{
+public:
+
+ //! Sorts the set by centroids coordinates in specified axis.
+ static void Perform (BVH_Set<T, N>* theSet,
+ const Standard_Integer theAxis);
+
+ //! Sorts the set by centroids coordinates in specified axis.
+ static void Perform (BVH_Set<T, N>* theSet,
+ const Standard_Integer theAxis,
+ const Standard_Integer theBegElement,
+ const Standard_Integer theEndElement);
+
+};
+
+#include <BVH_Sorter.lxx>
+
+#endif // _BVH_Sorter_Header
--- /dev/null
+// Created on: 2014-01-10
+// 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 : Perform
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Sorter<T, N>::Perform (BVH_Set<T, N>* theSet,
+ const Standard_Integer theAxis)
+{
+ Perform (theSet, theAxis, 0, theSet->Size() - 1);
+}
+
+// =======================================================================
+// function : Perform
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Sorter<T, N>::Perform (BVH_Set<T, N>* theSet,
+ const Standard_Integer theAxis,
+ const Standard_Integer theBegElement,
+ const Standard_Integer theEndElement)
+{
+ Standard_Integer aLft = theBegElement;
+ Standard_Integer aRgh = theEndElement;
+
+ T aPivot = theSet->Center ((aRgh + aLft) / 2, theAxis);
+
+ while (aLft < aRgh)
+ {
+ while (theSet->Center (aLft, theAxis) < aPivot && aLft < theEndElement)
+ {
+ ++aLft;
+ }
+
+ while (theSet->Center (aRgh, theAxis) > aPivot && aRgh > theBegElement)
+ {
+ --aRgh;
+ }
+
+ if (aLft <= aRgh)
+ {
+ if (aLft != aRgh)
+ {
+ theSet->Swap (aLft, aRgh);
+ }
+
+ ++aLft;
+ --aRgh;
+ }
+ }
+
+ if (aRgh > theBegElement)
+ {
+ Perform (theSet, theAxis, theBegElement, aRgh);
+ }
+
+ if (aLft < theEndElement)
+ {
+ Perform (theSet, theAxis, aLft, theEndElement);
+ }
+}
--- /dev/null
+// 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.
+
+#ifndef _BVH_SpatialMedianBuilder_Header
+#define _BVH_SpatialMedianBuilder_Header
+
+#include <BVH_BinnedBuilder.hxx>
+
+//! Performs building of BVH tree using spatial median split algorithm.
+template<class T, int N>
+class BVH_SpatialMedianBuilder : public BVH_BinnedBuilder<T, N, 2>
+{
+public:
+
+ //! Creates spatial median split builder.
+ BVH_SpatialMedianBuilder (const Standard_Integer theLeafNodeSize = 5,
+ const Standard_Integer theMaxTreeDepth = 32);
+
+ //! Releases resources of spatial median split builder.
+ virtual ~BVH_SpatialMedianBuilder();
+
+};
+
+#include <BVH_SpatialMedianBuilder.lxx>
+
+#endif // _BVH_SpatialMedianBuilder_Header
--- /dev/null
+// 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.
+
+#include <BVH_Box.hxx>
+
+// =======================================================================
+// function : BVH_SpatialMedianBuilder
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_SpatialMedianBuilder<T, N>::BVH_SpatialMedianBuilder (const Standard_Integer theLeafNodeSize,
+ const Standard_Integer theMaxTreeDepth)
+: BVH_BinnedBuilder<T, N, 2> (theLeafNodeSize,
+ theMaxTreeDepth)
+{
+ //
+}
+
+// =======================================================================
+// function : ~BVH_SpatialMedianBuilder
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_SpatialMedianBuilder<T, N>::~BVH_SpatialMedianBuilder()
+{
+ //
+}
--- /dev/null
+// Created on: 2014-01-09
+// 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.
+
+#ifndef _BVH_SweepPlaneBuilder_Header
+#define _BVH_SweepPlaneBuilder_Header
+
+#include <BVH_Builder.hxx>
+
+//! Performs building of BVH tree using sweep plane SAH algorithm.
+template<class T, int N>
+class BVH_SweepPlaneBuilder : public BVH_Builder<T, N>
+{
+public:
+
+ //! Creates sweep plane SAH BVH builder.
+ BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize = 5,
+ const Standard_Integer theMaxTreeDepth = 32);
+
+ //! Releases resources of sweep plane SAH BVH builder.
+ virtual ~BVH_SweepPlaneBuilder();
+
+protected:
+
+ //! Builds specified BVH node.
+ virtual void BuildNode (BVH_Set<T, N>* theSet,
+ BVH_Tree<T, N>* theBVH,
+ const Standard_Integer theNode);
+
+};
+
+#include <BVH_SweepPlaneBuilder.lxx>
+
+#endif // _BVH_SweepPlaneBuilder_Header
--- /dev/null
+// Created on: 2014-01-09
+// 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.
+
+#include <BVH_Sorter.hxx>
+
+// =======================================================================
+// function : BVH_SweepPlaneBuilder
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_SweepPlaneBuilder<T, N>::BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize,
+ const Standard_Integer theMaxTreeDepth)
+: BVH_Builder<T, N> (theLeafNodeSize,
+ theMaxTreeDepth)
+{
+ //
+}
+
+// =======================================================================
+// function : ~BVH_SweepPlaneBuilder
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_SweepPlaneBuilder<T, N>::~BVH_SweepPlaneBuilder()
+{
+ //
+}
+
+// =======================================================================
+// function : BuildNode
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_SweepPlaneBuilder<T, N>::BuildNode (BVH_Set<T, N>* theSet,
+ BVH_Tree<T, N>* theBVH,
+ const Standard_Integer theNode)
+{
+ const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
+ const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
+ const Standard_Integer aNodeNbPrimitives = theBVH->NbPrimitives (theNode);
+
+ // Parameters for storing best split
+ Standard_Integer aMinSplitAxis = -1;
+ Standard_Integer aMinSplitIndex = 0;
+
+ Standard_Real* aLftSet = new Standard_Real[aNodeNbPrimitives];
+ Standard_Real* aRghSet = new Standard_Real[aNodeNbPrimitives];
+
+ Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
+
+ // Find best split
+ for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
+ {
+ const T aNodeSize = BVHTools::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), anAxis) -
+ BVHTools::VecComp<T, N>::Get (theBVH->MinPoint (theNode), anAxis);
+ if (aNodeSize <= THE_NODE_MIN_SIZE)
+ {
+ continue;
+ }
+
+ BVH_Sorter<T, N>::Perform (theSet, anAxis, aNodeBegPrimitive, aNodeEndPrimitive);
+
+ BVH_Box<T, N> aLftBox;
+ BVH_Box<T, N> aRghBox;
+
+ *aLftSet = std::numeric_limits<T>::max();
+ *aRghSet = std::numeric_limits<T>::max();
+
+ // Sweep from left
+ for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
+ {
+ aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1));
+
+ aLftSet[anIndex] = static_cast<Standard_Real> (aLftBox.Area());
+ }
+
+ // Sweep from right
+ for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
+ {
+ aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1));
+
+ aRghSet[anIndex] = static_cast<Standard_Real> (aRghBox.Area());
+ }
+
+ // Find best split using simplified SAH
+ for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh)
+ {
+ Standard_Real aCost = (aLftSet[aNbLft] /* / aNodeArea */) * aNbLft +
+ (aRghSet[aNbRgh] /* / aNodeArea */) * aNbRgh;
+
+ if (aCost < aMinSplitCost)
+ {
+ aMinSplitCost = aCost;
+ aMinSplitAxis = anAxis;
+ aMinSplitIndex = aNbLft;
+ }
+ }
+ }
+
+ if (aMinSplitAxis == -1)
+ {
+ return;
+ }
+
+ theBVH->SetInner (theNode);
+
+ if (aMinSplitAxis != (N < 4 ? N - 1 : 2))
+ {
+ BVH_Sorter<T, N>::Perform (theSet, aMinSplitAxis, aNodeBegPrimitive, aNodeEndPrimitive);
+ }
+
+ BVH_Box<T, N> aMinSplitBoxLft;
+ BVH_Box<T, N> aMinSplitBoxRgh;
+
+ // Compute bounding boxes for selected split plane
+ for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex)
+ {
+ aMinSplitBoxLft.Combine (theSet->Box (anIndex));
+ }
+
+ for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex)
+ {
+ aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
+ }
+
+ const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex;
+
+ 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<T, N>::BVH_VecNt aChildMinPoint = (aSide == aLftNode)
+ ? aMinSplitBoxLft.CornerMin()
+ : aMinSplitBoxRgh.CornerMin();
+ typename BVH_Box<T, N>::BVH_VecNt aChildMaxPoint = (aSide == aLftNode)
+ ? aMinSplitBoxLft.CornerMax()
+ : aMinSplitBoxRgh.CornerMax();
+
+ Standard_Integer aChildBegPrimitive = (aSide == aLftNode)
+ ? aNodeBegPrimitive
+ : aMiddle;
+ Standard_Integer aChildEndPrimitive = (aSide == aLftNode)
+ ? aMiddle - 1
+ : aNodeEndPrimitive;
+
+ Standard_Integer aChildIndex = theBVH->AddLeafNode (aChildMinPoint, aChildMaxPoint,
+ aChildBegPrimitive, aChildEndPrimitive);
+
+ theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
+
+ // Check to see if child node must be split
+ const Standard_Integer aChildNbPimitives = (aSide == aLftNode)
+ ? aMiddle - aNodeBegPrimitive
+ : aNodeEndPrimitive - aMiddle + 1;
+
+ if (aSide == aLftNode)
+ theBVH->LeftChild (theNode) = aChildIndex;
+ else
+ theBVH->RightChild (theNode) = aChildIndex;
+
+ const Standard_Boolean isLeaf = aChildNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
+ || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
+
+ if (!isLeaf)
+ {
+ BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
+ }
+ }
+}
--- /dev/null
+// 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.
+
+#ifndef _BVH_Tree_Header
+#define _BVH_Tree_Header
+
+#include <Standard_Type.hxx>
+
+#include <BVH_Box.hxx>
+
+//! Stores parameters of bounding volume hierarchy (BVH).
+//! Bounding volume hierarchy (BVH) organizes geometric objects in
+//! the tree based on spatial relationships. Each node in the tree
+//! contains an axis-aligned bounding box of all the objects below
+//! it. Bounding volume hierarchies are used in many algorithms to
+//! support efficient operations on the sets of geometric objects,
+//! such as collision detection, ray-tracing, searching of nearest
+//! objects, and view frustum culling.
+template<class T, int N>
+class BVH_Tree
+{
+public:
+
+ typedef typename BVH_Box<T, N>::BVH_VecNt BVH_VecNt;
+
+public:
+
+ //! Returns minimum point of the given node.
+ BVH_VecNt& MinPoint (const Standard_Integer theNodeIndex)
+ {
+ return BVHTools::ArrayOp<T, N>::ChangeValue (myMinPointBuffer, theNodeIndex);
+ }
+
+ //! Returns maximum point of the given node.
+ BVH_VecNt& MaxPoint (const Standard_Integer theNodeIndex)
+ {
+ return BVHTools::ArrayOp<T, N>::ChangeValue (myMaxPointBuffer, theNodeIndex);
+ }
+
+ //! Returns minimum point of the given node.
+ const BVH_VecNt& MinPoint (const Standard_Integer theNodeIndex) const
+ {
+ return BVHTools::ArrayOp<T, N>::Value (myMinPointBuffer, theNodeIndex);
+ }
+
+ //! Returns maximum point of the given node.
+ const BVH_VecNt& MaxPoint (const Standard_Integer theNodeIndex) const
+ {
+ return BVHTools::ArrayOp<T, N>::Value (myMaxPointBuffer, theNodeIndex);
+ }
+
+ //! Returns index of left child of the given inner node.
+ Standard_Integer& LeftChild (const Standard_Integer theNodeIndex)
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y();
+ }
+
+ //! Returns index of left child of the given inner node.
+ Standard_Integer LeftChild (const Standard_Integer theNodeIndex) const
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).y();
+ }
+
+ //! Returns index of right child of the given inner node.
+ Standard_Integer& RightChild (const Standard_Integer theNodeIndex)
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z();
+ }
+
+ //! Returns index of right child of the given inner node.
+ Standard_Integer RightChild (const Standard_Integer theNodeIndex) const
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).z();
+ }
+
+ //! Returns index of first primitive of the given leaf node.
+ Standard_Integer& BegPrimitive (const Standard_Integer theNodeIndex)
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y();
+ }
+
+ //! Returns index of first primitive of the given leaf node.
+ Standard_Integer BegPrimitive (const Standard_Integer theNodeIndex) const
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).y();
+ }
+
+ //! Returns index of last primitive of the given leaf node.
+ Standard_Integer& EndPrimitive (const Standard_Integer theNodeIndex)
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z();
+ }
+
+ //! Returns index of last primitive of the given leaf node.
+ Standard_Integer EndPrimitive (const Standard_Integer theNodeIndex) const
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).z();
+ }
+
+ //! Returns number of primitives for the given tree node.
+ Standard_Integer NbPrimitives (const Standard_Integer theNodeIndex) const
+ {
+ return EndPrimitive (theNodeIndex) - BegPrimitive (theNodeIndex) + 1;
+ }
+
+ //! Returns level (depth) of the given node.
+ Standard_Integer& Level (const Standard_Integer theNodeIndex)
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).w();
+ }
+
+ //! Returns level (depth) of the given node.
+ Standard_Integer Level (const Standard_Integer theNodeIndex) const
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).w();
+ }
+
+ //! Is node a leaf (outer)?
+ Standard_Boolean IsOuter (const Standard_Integer theNodeIndex) const
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).x() > 0;
+ }
+
+ //! Sets node type to 'outer'.
+ void SetOuter (const Standard_Integer theNodeIndex)
+ {
+ BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).x() = 1;
+ }
+
+ //! Sets node type to 'inner'.
+ void SetInner (const Standard_Integer theNodeIndex)
+ {
+ BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).x() = 0;
+ }
+
+ //! Returns total number of BVH nodes.
+ Standard_Integer Length() const
+ {
+ return BVHTools::ArrayOp<Standard_Integer, 4>::Size (myNodeInfoBuffer);
+ }
+
+public:
+
+ //! Removes all BVH nodes.
+ void Clear();
+
+ //! Adds new leaf node to the BVH.
+ Standard_Integer AddLeafNode (const BVH_VecNt& theMinPoint,
+ const BVH_VecNt& theMaxPoint,
+ const Standard_Integer theBegElem,
+ const Standard_Integer theEndElem);
+
+ //! Adds new inner node to the BVH.
+ Standard_Integer AddInnerNode (const BVH_VecNt& theMinPoint,
+ const BVH_VecNt& theMaxPoint,
+ const Standard_Integer theLftChild,
+ const Standard_Integer theRghChild);
+
+ //! Adds new leaf node to the BVH.
+ Standard_Integer AddLeafNode (const BVH_Box<T, N>& theAABB,
+ const Standard_Integer theBegElem,
+ const Standard_Integer theEndElem);
+
+ //! Adds new inner node to the BVH.
+ Standard_Integer AddInnerNode (const BVH_Box<T, N>& theAABB,
+ const Standard_Integer theLftChild,
+ const Standard_Integer theRghChild);
+
+ //! Returns value of SAH (surface area heuristic).
+ //! Allows to compare the quality of BVH trees constructed for
+ //! the same sets of geometric objects with different methods.
+ T EstimateSAH() const;
+
+public:
+
+ //! Returns array of node min points.
+ typename BVHTools::ArrayType<T, N>::Type& MinPointBuffer()
+ {
+ return myMinPointBuffer;
+ }
+
+ //! Returns array of node min points.
+ const typename BVHTools::ArrayType<T, N>::Type& MinPointBuffer() const
+ {
+ return myMinPointBuffer;
+ }
+
+ //! Returns array of node max points.
+ typename BVHTools::ArrayType<T, N>::Type& MaxPointBuffer()
+ {
+ return myMaxPointBuffer;
+ }
+
+ //! Returns array of node max points.
+ const typename BVHTools::ArrayType<T, N>::Type& MaxPointBuffer() const
+ {
+ return myMaxPointBuffer;
+ }
+
+ //! Returns array of node data records.
+ BVH_Array4i& NodeInfoBuffer()
+ {
+ return myNodeInfoBuffer;
+ }
+
+ //! Returns array of node data records.
+ const BVH_Array4i& NodeInfoBuffer() const
+ {
+ return myNodeInfoBuffer;
+ }
+
+protected:
+
+ //! Array of node minimum points.
+ typename BVHTools::ArrayType<T, N>::Type myMinPointBuffer;
+
+ //! Array of node maximum points.
+ typename BVHTools::ArrayType<T, N>::Type myMaxPointBuffer;
+
+ //! Array of node data records.
+ BVH_Array4i myNodeInfoBuffer;
+
+};
+
+#include <BVH_Tree.lxx>
+
+#endif // _BVH_Tree_Header
--- /dev/null
+// 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 : Clear
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Tree<T, N>::Clear()
+{
+ BVHTools::ArrayOp<T, N>::Clear (myMinPointBuffer);
+ BVHTools::ArrayOp<T, N>::Clear (myMaxPointBuffer);
+
+ BVHTools::ArrayOp<Standard_Integer, 4>::Clear (myNodeInfoBuffer);
+}
+
+// =======================================================================
+// function : AddLeafNode
+// purpose :
+// =======================================================================
+template<class T, int N>
+Standard_Integer BVH_Tree<T, N>::AddLeafNode (const BVH_VecNt& theMinPoint,
+ const BVH_VecNt& theMaxPoint,
+ const Standard_Integer theBegElem,
+ const Standard_Integer theEndElem)
+{
+ BVHTools::ArrayOp<T, N>::Append (myMinPointBuffer, theMinPoint);
+ BVHTools::ArrayOp<T, N>::Append (myMaxPointBuffer, theMaxPoint);
+
+ BVHTools::ArrayOp<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0));
+
+ return static_cast<Standard_Integer> (BVHTools::ArrayOp<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1);
+}
+
+// =======================================================================
+// function : AddInnerNode
+// purpose :
+// =======================================================================
+template<class T, int N>
+Standard_Integer BVH_Tree<T, N>::AddInnerNode (const BVH_VecNt& theMinPoint,
+ const BVH_VecNt& theMaxPoint,
+ const Standard_Integer theLftChild,
+ const Standard_Integer theRghChild)
+{
+ BVHTools::ArrayOp<T, N>::Append (myMinPointBuffer, theMinPoint);
+ BVHTools::ArrayOp<T, N>::Append (myMaxPointBuffer, theMaxPoint);
+
+ BVHTools::ArrayOp<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0));
+
+ return static_cast<Standard_Integer> (BVHTools::ArrayOp<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1);
+}
+
+// =======================================================================
+// function : AddLeafNode
+// purpose :
+// =======================================================================
+template<class T, int N>
+Standard_Integer BVH_Tree<T, N>::AddLeafNode (const BVH_Box<T, N>& theAABB,
+ const Standard_Integer theBegElem,
+ const Standard_Integer theEndElem)
+{
+ return AddLeafNode (theAABB.CornerMin(), theAABB.CornerMax(), theBegElem, theEndElem);
+}
+
+// =======================================================================
+// function : AddInnerNode
+// purpose :
+// =======================================================================
+template<class T, int N>
+Standard_Integer BVH_Tree<T, N>::AddInnerNode (const BVH_Box<T, N>& theAABB,
+ const Standard_Integer theLftChild,
+ const Standard_Integer theRghChild)
+{
+ return AddInnerNode (theAABB.CornerMin(), theAABB.CornerMax(), theLftChild, theRghChild);
+}
+
+namespace BVHTools
+{
+ template<class T, int N>
+ void EstimateSAH (const BVH_Tree<T, N>* theTree,
+ const Standard_Integer theNode,
+ T theProbability,
+ T& theSAH)
+ {
+ BVH_Box<T, N> aBox (theTree->MinPoint (theNode),
+ theTree->MaxPoint (theNode));
+
+ if (theTree->IsOuter (theNode))
+ {
+ theSAH += theProbability * (theTree->EndPrimitive (theNode) - theTree->BegPrimitive (theNode) + 1);
+ }
+ else
+ {
+ theSAH += theProbability * static_cast<T> (2.0);
+
+ BVH_Box<T, N> aLftBox (theTree->MinPoint (theTree->LeftChild (theNode)),
+ theTree->MaxPoint (theTree->LeftChild (theNode)));
+
+ if (theProbability > 0.0)
+ {
+ EstimateSAH (theTree, theTree->LeftChild (theNode),
+ theProbability * aLftBox.Area() / aBox.Area(), theSAH);
+ }
+
+ BVH_Box<T, N> aRghBox (theTree->MinPoint (theTree->RightChild (theNode)),
+ theTree->MaxPoint (theTree->RightChild (theNode)));
+
+ if (theProbability > 0.0)
+ {
+ EstimateSAH (theTree, theTree->RightChild (theNode),
+ theProbability * aRghBox.Area() / aBox.Area(), theSAH);
+ }
+ }
+ }
+}
+
+// =======================================================================
+// function : EstimateSAH
+// purpose :
+// =======================================================================
+template<class T, int N>
+T BVH_Tree<T, N>::EstimateSAH() const
+{
+ T aSAH = static_cast<T> (0.0);
+ BVHTools::EstimateSAH (this, 0, static_cast<T> (1.0), aSAH);
+ return aSAH;
+}
--- /dev/null
+// 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.
+
+#ifndef _BVH_Triangulation_Header
+#define _BVH_Triangulation_Header
+
+#include <BVH_PrimitiveSet.hxx>
+
+//! Triangulation as an example of primitive set.
+template<class T, int N>
+class BVH_Triangulation : public BVH_PrimitiveSet<T, N>
+{
+public:
+
+ typedef typename BVHTools::VectorType<T, N>::Type BVH_VecNt;
+
+public:
+
+ //! Creates new triangulation.
+ BVH_Triangulation();
+
+ //! Releases resources of geometric object.
+ virtual ~BVH_Triangulation();
+
+public:
+
+ //! Array of vertex coordinates.
+ typename BVHTools::ArrayType<T, N>::Type Vertices;
+
+ //! Array of indices of triangle indicies vertices.
+ BVH_Array4i Elements;
+
+public:
+
+ //! Return total number of triangles.
+ virtual Standard_Integer Size() const;
+
+ //! Returns AABB of specified triangle.
+ virtual BVH_Box<T, N> Box (const Standard_Integer theIndex) const;
+
+ //! Returns centroid position in specified axis.
+ virtual T Center (const Standard_Integer theIndex,
+ const Standard_Integer theAxis) const;
+
+ //! Swaps indices of two specified triangles.
+ virtual void Swap (const Standard_Integer theIndex1,
+ const Standard_Integer theIndex2);
+
+};
+
+#include <BVH_Triangulation.lxx>
+
+#endif // _BVH_Triangulation_Header
--- /dev/null
+// 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_Triangulation
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Triangulation<T, N>::BVH_Triangulation()
+{
+ //
+}
+
+// =======================================================================
+// function : ~BVH_Triangulation
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Triangulation<T, N>::~BVH_Triangulation()
+{
+ //
+}
+
+// =======================================================================
+// function : Size
+// purpose :
+// =======================================================================
+template<class T, int N>
+Standard_Integer BVH_Triangulation<T, N>::Size() const
+{
+ return BVHTools::ArrayOp<Standard_Integer, 4>::Size (Elements);
+}
+
+// =======================================================================
+// function : Box
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Box<T, N> BVH_Triangulation<T, N>::Box (const Standard_Integer theIndex) const
+{
+ const BVH_Vec4i& anIndex = BVHTools::ArrayOp<Standard_Integer, 4>::Value (Elements, theIndex);
+
+ const BVH_VecNt& aPoint0 = BVHTools::ArrayOp<T, N>::Value (Vertices, anIndex.x());
+ const BVH_VecNt& aPoint1 = BVHTools::ArrayOp<T, N>::Value (Vertices, anIndex.y());
+ const BVH_VecNt& aPoint2 = BVHTools::ArrayOp<T, N>::Value (Vertices, anIndex.z());
+
+ const BVH_VecNt aMinPoint = aPoint0.cwiseMin (aPoint1.cwiseMin (aPoint2));
+ const BVH_VecNt aMaxPoint = aPoint0.cwiseMax (aPoint1.cwiseMax (aPoint2));
+
+ return BVH_Box<T, N> (aMinPoint, aMaxPoint);
+}
+
+// =======================================================================
+// function : Center
+// purpose :
+// =======================================================================
+template<class T, int N>
+T BVH_Triangulation<T, N>::Center (const Standard_Integer theIndex,
+ const Standard_Integer theAxis) const
+{
+ const BVH_Vec4i& anIndex = BVHTools::ArrayOp<Standard_Integer, 4>::Value (Elements, theIndex);
+
+ const BVH_VecNt& aPoint0 = BVHTools::ArrayOp<T, N>::Value (Vertices, anIndex.x());
+ const BVH_VecNt& aPoint1 = BVHTools::ArrayOp<T, N>::Value (Vertices, anIndex.y());
+ const BVH_VecNt& aPoint2 = BVHTools::ArrayOp<T, N>::Value (Vertices, anIndex.z());
+
+ return ( BVHTools::VecComp<T, N>::Get (aPoint0, theAxis) +
+ BVHTools::VecComp<T, N>::Get (aPoint1, theAxis) +
+ BVHTools::VecComp<T, N>::Get (aPoint2, theAxis) ) * static_cast<T> (1.0 / 3.0);
+}
+
+// =======================================================================
+// function : Swap
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Triangulation<T, N>::Swap (const Standard_Integer theIndex1,
+ const Standard_Integer theIndex2)
+{
+ BVH_Vec4i anIndices1 = BVHTools::ArrayOp<Standard_Integer, 4>::Value (Elements, theIndex1);
+ BVH_Vec4i anIndices2 = BVHTools::ArrayOp<Standard_Integer, 4>::Value (Elements, theIndex2);
+
+ BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (Elements, theIndex1) = anIndices2;
+ BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (Elements, theIndex2) = anIndices1;
+}
--- /dev/null
+// 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.
+
+#ifndef _BVH_Types_Header
+#define _BVH_Types_Header
+
+// Use this macro to switch between STL and OCCT vector types
+#define _BVH_USE_STD_VECTOR_
+
+#include <NCollection_Vec2.hxx>
+#include <NCollection_Vec3.hxx>
+#include <NCollection_Vec4.hxx>
+#include <NCollection_Vector.hxx>
+#include <NCollection_Mat4.hxx>
+#include <Standard_Type.hxx>
+
+#include <vector>
+
+namespace BVHTools
+{
+ //! Allows to fast switching between Eigen and NCollection vectors.
+ template<class T, int N> struct VectorType
+ {
+ // Not implemented
+ };
+
+ template<class T> struct VectorType<T, 1>
+ {
+ typedef T Type;
+ };
+
+ template<class T> struct VectorType<T, 2>
+ {
+ typedef NCollection_Vec2<T> Type;
+ };
+
+ template<class T> struct VectorType<T, 3>
+ {
+ typedef NCollection_Vec3<T> Type;
+ };
+
+ template<class T> struct VectorType<T, 4>
+ {
+ typedef NCollection_Vec4<T> Type;
+ };
+
+ template<class T, int N = 1> struct ArrayType
+ {
+ #ifndef _BVH_USE_STD_VECTOR_
+ typedef NCollection_Vector<typename VectorType<T, N>::Type> Type;
+ #else
+ typedef std::vector<typename VectorType<T, N>::Type> Type;
+ #endif
+ };
+
+ //! Allows to fast switching between Eigen and NCollection matrices.
+ template<class T, int N> struct MatrixType
+ {
+ // Not implemented
+ };
+
+ template<class T> struct MatrixType<T, 4>
+ {
+ typedef NCollection_Mat4<T> Type;
+ };
+}
+
+//! 2D vector of integers.
+typedef BVHTools::VectorType<Standard_Integer, 2>::Type BVH_Vec2i;
+//! 3D vector of integers.
+typedef BVHTools::VectorType<Standard_Integer, 3>::Type BVH_Vec3i;
+//! 4D vector of integers.
+typedef BVHTools::VectorType<Standard_Integer, 4>::Type BVH_Vec4i;
+
+//! Array of 2D vectors of integers.
+typedef BVHTools::ArrayType<Standard_Integer, 2>::Type BVH_Array2i;
+//! Array of 3D vectors of integers.
+typedef BVHTools::ArrayType<Standard_Integer, 3>::Type BVH_Array3i;
+//! Array of 4D vectors of integers.
+typedef BVHTools::ArrayType<Standard_Integer, 4>::Type BVH_Array4i;
+
+//! 2D vector of single precision reals.
+typedef BVHTools::VectorType<Standard_ShortReal, 2>::Type BVH_Vec2f;
+//! 3D vector of single precision reals.
+typedef BVHTools::VectorType<Standard_ShortReal, 3>::Type BVH_Vec3f;
+//! 4D vector of single precision reals.
+typedef BVHTools::VectorType<Standard_ShortReal, 4>::Type BVH_Vec4f;
+
+//! Array of 2D vectors of single precision reals.
+typedef BVHTools::ArrayType<Standard_ShortReal, 2>::Type BVH_Array2f;
+//! Array of 3D vectors of single precision reals.
+typedef BVHTools::ArrayType<Standard_ShortReal, 3>::Type BVH_Array3f;
+//! Array of 4D vectors of single precision reals.
+typedef BVHTools::ArrayType<Standard_ShortReal, 4>::Type BVH_Array4f;
+
+//! 2D vector of double precision reals.
+typedef BVHTools::VectorType<Standard_Real, 2>::Type BVH_Vec2d;
+//! 3D vector of double precision reals.
+typedef BVHTools::VectorType<Standard_Real, 3>::Type BVH_Vec3d;
+//! 4D vector of double precision reals.
+typedef BVHTools::VectorType<Standard_Real, 4>::Type BVH_Vec4d;
+
+//! Array of 2D vectors of double precision reals.
+typedef BVHTools::ArrayType<Standard_Real, 2>::Type BVH_Array2d;
+//! Array of 3D vectors of double precision reals.
+typedef BVHTools::ArrayType<Standard_Real, 3>::Type BVH_Array3d;
+//! Array of 4D vectors of double precision reals.
+typedef BVHTools::ArrayType<Standard_Real, 4>::Type BVH_Array4d;
+
+//! 4x4 matrix of single precision reals.
+typedef BVHTools::MatrixType<Standard_ShortReal, 4>::Type BVH_Mat4f;
+
+//! 4x4 matrix of double precision reals.
+typedef BVHTools::MatrixType<Standard_Real, 4>::Type BVH_Mat4d;
+
+#include <BVH_Types.lxx>
+
+#endif // _BVH_Types_Header
--- /dev/null
+// 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.
+
+namespace BVHTools
+{
+ template<class T, int N> struct VecComp
+ {
+ // Not implemented
+ };
+
+ template<class T> struct VecComp<T, 2>
+ {
+ typedef typename BVHTools::VectorType<T, 2>::Type BVH_Vec2t;
+
+ static T Get (const BVH_Vec2t& theVec,
+ const Standard_Integer theAxis)
+ {
+ return theAxis == 0 ? theVec.x() : theVec.y();
+ }
+ };
+
+ template<class T> struct VecComp<T, 3>
+ {
+ typedef typename BVHTools::VectorType<T, 3>::Type BVH_Vec3t;
+
+ static T Get (const BVH_Vec3t& theVec,
+ const Standard_Integer theAxis)
+ {
+ return theAxis == 0 ? theVec.x() : ( theAxis == 1 ? theVec.y() : theVec.z() );
+ }
+ };
+
+ template<class T> struct VecComp<T, 4>
+ {
+ typedef typename BVHTools::VectorType<T, 4>::Type BVH_Vec4t;
+
+ static T Get (const BVH_Vec4t& theVec,
+ const Standard_Integer theAxis)
+ {
+ return theAxis == 0
+ ? theVec.x()
+ : (theAxis == 1 ? theVec.y() : ( theAxis == 2 ? theVec.z() : theVec.w() ));
+ }
+ };
+
+ template<class T, int N = 1> struct ArrayOp
+ {
+ typedef typename BVHTools::ArrayType<T, N>::Type BVH_ArrayNt;
+
+ static inline
+ const typename BVHTools::VectorType<T, N>::Type& Value (const BVH_ArrayNt& theArray,
+ const Standard_Integer theIndex)
+ {
+ #ifdef _BVH_USE_STD_VECTOR_
+ return theArray.at (theIndex);
+ #else
+ return theArray.Value (theIndex);
+ #endif
+ }
+
+ static inline
+ typename BVHTools::VectorType<T, N>::Type& ChangeValue (BVH_ArrayNt& theArray,
+ const Standard_Integer theIndex)
+ {
+ #ifdef _BVH_USE_STD_VECTOR_
+ return theArray.at (theIndex);
+ #else
+ return theArray.ChangeValue (theIndex);
+ #endif
+ }
+
+ static inline void Append (BVH_ArrayNt& theArray,
+ const typename BVHTools::VectorType<T, N>::Type& theElement)
+ {
+ #ifdef _BVH_USE_STD_VECTOR_
+ theArray.push_back (theElement);
+ #else
+ theArray.Append (theElement);
+ #endif
+ }
+
+ static inline Standard_Integer Size (const BVH_ArrayNt& theArray)
+ {
+ #ifdef _BVH_USE_STD_VECTOR_
+ return static_cast<Standard_Integer> (theArray.size());
+ #else
+ return static_cast<Standard_Integer> (theArray.Size());
+ #endif
+ }
+
+ static inline void Clear (BVH_ArrayNt& theArray)
+ {
+ #ifdef _BVH_USE_STD_VECTOR_
+ theArray.clear();
+ #else
+ theArray.Clear();
+ #endif
+ }
+ };
+}
--- /dev/null
+BVH.cxx
+BVH_BinnedBuilder.hxx
+BVH_BinnedBuilder.lxx
+BVH_Box.hxx
+BVH_Box.lxx
+BVH_Builder.hxx
+BVH_Builder.lxx
+BVH_Geometry.hxx
+BVH_Geometry.lxx
+BVH_Object.hxx
+BVH_Object.lxx
+BVH_ObjectSet.hxx
+BVH_ObjectSet.lxx
+BVH_PrimitiveSet.hxx
+BVH_PrimitiveSet.lxx
+BVH_Properties.hxx
+BVH_Properties.lxx
+BVH_Properties.cxx
+BVH_Set.hxx
+BVH_Set.lxx
+BVH_Sorter.hxx
+BVH_Sorter.lxx
+BVH_SpatialMedianBuilder.hxx
+BVH_SpatialMedianBuilder.lxx
+BVH_SweepPlaneBuilder.hxx
+BVH_SweepPlaneBuilder.lxx
+BVH_Tree.hxx
+BVH_Tree.lxx
+BVH_Triangulation.hxx
+BVH_Triangulation.lxx
+BVH_Types.hxx
+BVH_Types.lxx
v[1] * theFactor);
}
+ //! Compute component-wise minimum of two vectors.
+ NCollection_Vec2 cwiseMin (const NCollection_Vec2& theVec) const
+ {
+ return NCollection_Vec2 (Min (v[0], theVec.v[0]),
+ Min (v[1], theVec.v[1]));
+ }
+
+ //! Compute component-wise maximum of two vectors.
+ NCollection_Vec2 cwiseMax (const NCollection_Vec2& theVec) const
+ {
+ return NCollection_Vec2 (Max (v[0], theVec.v[0]),
+ Max (v[1], theVec.v[1]));
+ }
+
//! Compute per-component multiplication by scale factor.
NCollection_Vec2& operator*= (const Element_t theFactor)
{
return aCopyVec3;
}
+ //! Compute component-wise minimum of two vectors.
+ NCollection_Vec3 cwiseMin (const NCollection_Vec3& theVec) const
+ {
+ return NCollection_Vec3 (Min (v[0], theVec.v[0]),
+ Min (v[1], theVec.v[1]),
+ Min (v[2], theVec.v[2]));
+ }
+
+ //! Compute component-wise maximum of two vectors.
+ NCollection_Vec3 cwiseMax (const NCollection_Vec3& theVec) const
+ {
+ return NCollection_Vec3 (Max (v[0], theVec.v[0]),
+ Max (v[1], theVec.v[1]),
+ Max (v[2], theVec.v[2]));
+ }
+
//! Compute per-component division by scale factor.
NCollection_Vec3& operator/= (const Element_t theInvFactor)
{
return aCopyVec4;
}
+ //! Compute component-wise minimum of two vectors.
+ NCollection_Vec4 cwiseMin (const NCollection_Vec4& theVec) const
+ {
+ return NCollection_Vec4 (Min (v[0], theVec.v[0]),
+ Min (v[1], theVec.v[1]),
+ Min (v[2], theVec.v[2]),
+ Min (v[3], theVec.v[3]));
+ }
+
+ //! Compute component-wise maximum of two vectors.
+ NCollection_Vec4 cwiseMax (const NCollection_Vec4& theVec) const
+ {
+ return NCollection_Vec4 (Max (v[0], theVec.v[0]),
+ Max (v[1], theVec.v[1]),
+ Max (v[2], theVec.v[2]),
+ Max (v[3], theVec.v[3]));
+ }
+
//! Compute per-component division by scale factor.
NCollection_Vec4& operator/= (const Element_t theInvFactor)
{
CSLib
Convert
Bnd
+BVH
gp
TColgp
TopLoc
projects / occt.git / commitdiff