--- /dev/null
+// Created on: 2016-06-20
+// Created by: Denis BOGOLEPOV
+// Copyright (c) 2016 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 License 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 <deque>
+#include <tuple>
+
+// =======================================================================
+// function : Child
+// purpose : Returns index of the K-th child of the given inner node
+// =======================================================================
+template<class T, int N> template<int K>
+int& BVH_Tree<T, N, BVH_BinaryTree>::Child (const int theNodeIndex)
+{
+ return BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex)[K + 1];
+}
+
+// =======================================================================
+// function : Child
+// purpose : Returns index of the K-th child of the given inner node
+// =======================================================================
+template<class T, int N> template<int K>
+int BVH_Tree<T, N, BVH_BinaryTree>::Child (const int theNodeIndex) const
+{
+ return BVH::Array<int, 4>::Value (this->myNodeInfoBuffer, theNodeIndex)[K + 1];
+}
+
+// =======================================================================
+// function : SetOuter
+// purpose : Sets node type to 'outer'
+// =======================================================================
+template<class T, int N>
+void BVH_Tree<T, N, BVH_BinaryTree>::SetOuter (const int theNodeIndex)
+{
+ BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex).x() = 1;
+}
+
+// =======================================================================
+// function : SetOuter
+// purpose : Sets node type to 'inner'
+// =======================================================================
+template<class T, int N>
+void BVH_Tree<T, N, BVH_BinaryTree>::SetInner (const int theNodeIndex)
+{
+ BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex).x() = 0;
+}
+
+// =======================================================================
+// function : Clear
+// purpose : Removes all BVH nodes
+// =======================================================================
+template<class T, int N>
+void BVH_Tree<T, N, BVH_BinaryTree>::Clear()
+{
+ this->myDepth = 0;
+
+ BVH::Array<T, N>::Clear (this->myMinPointBuffer);
+ BVH::Array<T, N>::Clear (this->myMaxPointBuffer);
+
+ BVH::Array<int, 4>::Clear (this->myNodeInfoBuffer);
+}
+
+// =======================================================================
+// function : AddLeafNode
+// purpose : Adds new leaf node to the BVH
+// =======================================================================
+template<class T, int N>
+int BVH_Tree<T, N, BVH_BinaryTree>::AddLeafNode (const int theBegElem,
+ const int theEndElem)
+{
+ BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0));
+
+ return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1;
+}
+
+// =======================================================================
+// function : AddInnerNode
+// purpose : Adds new inner node to the BVH
+// =======================================================================
+template<class T, int N>
+int BVH_Tree<T, N, BVH_BinaryTree>::AddInnerNode (const int theLftChild,
+ const int theRghChild)
+{
+ BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0));
+
+ return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1;
+}
+
+// =======================================================================
+// function : AddLeafNode
+// purpose : Adds new leaf node to the BVH
+// =======================================================================
+template<class T, int N>
+int BVH_Tree<T, N, BVH_BinaryTree>::AddLeafNode (const BVH_VecNt& theMinPoint,
+ const BVH_VecNt& theMaxPoint,
+ const int theBegElem,
+ const int theEndElem)
+{
+ BVH::Array<T, N>::Append (this->myMinPointBuffer, theMinPoint);
+ BVH::Array<T, N>::Append (this->myMaxPointBuffer, theMaxPoint);
+
+ BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0));
+
+ return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1;
+}
+
+// =======================================================================
+// function : AddInnerNode
+// purpose : Adds new inner node to the BVH
+// =======================================================================
+template<class T, int N>
+int BVH_Tree<T, N, BVH_BinaryTree>::AddInnerNode (const BVH_VecNt& theMinPoint,
+ const BVH_VecNt& theMaxPoint,
+ const int theLftChild,
+ const int theRghChild)
+{
+ BVH::Array<T, N>::Append (this->myMinPointBuffer, theMinPoint);
+ BVH::Array<T, N>::Append (this->myMaxPointBuffer, theMaxPoint);
+
+ BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0));
+
+ return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1;
+}
+
+// =======================================================================
+// function : AddLeafNode
+// purpose : Adds new leaf node to the BVH
+// =======================================================================
+template<class T, int N>
+int BVH_Tree<T, N, BVH_BinaryTree>::AddLeafNode (const BVH_Box<T, N>& theAABB,
+ const int theBegElem,
+ const int theEndElem)
+{
+ return AddLeafNode (theAABB.CornerMin(),
+ theAABB.CornerMax(),
+ theBegElem,
+ theEndElem);
+}
+
+// =======================================================================
+// function : AddInnerNode
+// purpose : Adds new inner node to the BVH
+// =======================================================================
+template<class T, int N>
+int BVH_Tree<T, N, BVH_BinaryTree>::AddInnerNode (const BVH_Box<T, N>& theAABB,
+ const int theLftChild,
+ const int theRghChild)
+{
+ return AddInnerNode (theAABB.CornerMin(),
+ theAABB.CornerMax(),
+ theLftChild,
+ theRghChild);
+}
+
+namespace BVH
+{
+ //! Internal function for recursive calculation of
+ //! surface area heuristic (SAH) of the given tree.
+ template<class T, int N>
+ void EstimateSAH (const BVH_Tree<T, N, BVH_BinaryTree>* theTree, const int theNode, T theProb, T& theSAH)
+ {
+ BVH_Box<T, N> aBox (theTree->MinPoint (theNode),
+ theTree->MaxPoint (theNode));
+
+ if (theTree->IsOuter (theNode))
+ {
+ theSAH += theProb * (theTree->EndPrimitive (theNode) - theTree->BegPrimitive (theNode) + 1);
+ }
+ else
+ {
+ theSAH += theProb * static_cast<T> (2.0);
+
+ BVH_Box<T, N> aLftBox (theTree->MinPoint (theTree->template Child<0> (theNode)),
+ theTree->MaxPoint (theTree->template Child<0> (theNode)));
+
+ if (theProb > 0.0)
+ {
+ EstimateSAH (theTree, theTree->template Child<0> (theNode),
+ theProb * aLftBox.Area() / aBox.Area(), theSAH);
+ }
+
+ BVH_Box<T, N> aRghBox (theTree->MinPoint (theTree->template Child<1> (theNode)),
+ theTree->MaxPoint (theTree->template Child<1> (theNode)));
+
+ if (theProb > 0.0)
+ {
+ EstimateSAH (theTree, theTree->template Child<1> (theNode),
+ theProb * aRghBox.Area() / aBox.Area(), theSAH);
+ }
+ }
+ }
+}
+
+// =======================================================================
+// function : EstimateSAH
+// purpose :
+// =======================================================================
+template<class T, int N>
+T BVH_Tree<T, N, BVH_BinaryTree>::EstimateSAH() const
+{
+ T aSAH = static_cast<T> (0.0);
+
+ BVH::EstimateSAH<T, N> (this, 0, static_cast<T> (1.0), aSAH);
+
+ return aSAH;
+}
+
+// =======================================================================
+// function : Reserve
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_Tree<T, N, BVH_BinaryTree>::Reserve (const int theNbNodes)
+{
+ BVH::Array<T, N>::Reserve (this->myMinPointBuffer, theNbNodes);
+ BVH::Array<T, N>::Reserve (this->myMaxPointBuffer, theNbNodes);
+ BVH::Array<int, 4>::Reserve (this->myNodeInfoBuffer, theNbNodes);
+}
+
+// =======================================================================
+// function : CollapseToQuadTree
+// purpose :
+// =======================================================================
+template<class T, int N>
+BVH_Tree<T, N, BVH_QuadTree>* BVH_Tree<T, N, BVH_BinaryTree>::CollapseToQuadTree() const
+{
+ BVH_Tree<T, N, BVH_QuadTree>* aQBVH = new BVH_Tree<T, N, BVH_QuadTree>;
+
+ if (this->Length() == 0)
+ {
+ return aQBVH;
+ }
+
+ std::deque<std::pair<int, int> > aQueue (1, std::make_pair (0, 0));
+
+ for (int aNbNodes = 1; !aQueue.empty();)
+ {
+ const std::pair<int, int> aNode = aQueue.front();
+
+ BVH::Array<T, N>::Append (aQBVH->myMinPointBuffer, BVH::Array<T, N>::Value (this->myMinPointBuffer, std::get<0> (aNode)));
+ BVH::Array<T, N>::Append (aQBVH->myMaxPointBuffer, BVH::Array<T, N>::Value (this->myMaxPointBuffer, std::get<0> (aNode)));
+
+ BVH_Vec4i aNodeInfo;
+
+ if (this->IsOuter (std::get<0> (aNode))) // is leaf node
+ {
+ aNodeInfo = BVH_Vec4i (1 /* leaf flag */,
+ this->BegPrimitive (std::get<0> (aNode)), this->EndPrimitive (std::get<0> (aNode)), std::get<1> (aNode) /* level */);
+ }
+ else
+ {
+ NCollection_Vector<int> aGrandChildNodes;
+
+ const int aLftChild = Child<0> (std::get<0> (aNode));
+ const int aRghChild = Child<1> (std::get<0> (aNode));
+
+ if (this->IsOuter (aLftChild)) // is leaf node
+ {
+ aGrandChildNodes.Append (aLftChild);
+ }
+ else
+ {
+ aGrandChildNodes.Append (Child<0> (aLftChild));
+ aGrandChildNodes.Append (Child<1> (aLftChild));
+ }
+
+ if (this->IsOuter (aRghChild)) // is leaf node
+ {
+ aGrandChildNodes.Append (aRghChild);
+ }
+ else
+ {
+ aGrandChildNodes.Append (Child<0> (aRghChild));
+ aGrandChildNodes.Append (Child<1> (aRghChild));
+ }
+
+ for (int aNodeIdx = 0; aNodeIdx < aGrandChildNodes.Size(); ++aNodeIdx)
+ {
+ aQueue.push_back (std::make_pair (aGrandChildNodes (aNodeIdx), std::get<1> (aNode) + 1));
+ }
+
+ aNodeInfo = BVH_Vec4i (0 /* inner flag */,
+ aNbNodes, aGrandChildNodes.Size() - 1, std::get<1> (aNode) /* level */);
+
+ aQBVH->myDepth = Max (aQBVH->myDepth, std::get<1> (aNode));
+
+ aNbNodes += aGrandChildNodes.Size();
+ }
+
+ BVH::Array<int, 4>::Append (aQBVH->myNodeInfoBuffer, aNodeInfo);
+
+ aQueue.pop_front(); // node processing completed
+ }
+
+ return aQBVH;
+}
projects / occt.git / blobdiff