0027590: Visualization, Ray Tracing - port to quad BVH trees (QBVH)
authordbp <dbp@opencascade.com>
Mon, 20 Jun 2016 16:43:44 +0000 (19:43 +0300)
committerbugmaster <bugmaster@opencascade.com>
Thu, 23 Jun 2016 15:15:13 +0000 (18:15 +0300)
In frames of this issue binary BVH tree produced by building algorithms was collapsed into 4-ary BVH (QBVH).
The BVH traversal code in GLSL was modified to process such trees correctly.
This allows to implore thread coherence, decrease BVH memory consumption (~2 times), and use traversal stack of the half size.
As a result, ray tracing scalability is improved, as well as rendering performance. For various setups, speedup is 12-18%.

19 files changed:
src/BVH/BVH_BinaryTree.hxx [new file with mode: 0644]
src/BVH/BVH_BinaryTree.lxx [new file with mode: 0644]
src/BVH/BVH_Builder.hxx
src/BVH/BVH_DistanceField.lxx
src/BVH/BVH_QuadTree.hxx [new file with mode: 0644]
src/BVH/BVH_QuadTree.lxx [new file with mode: 0644]
src/BVH/BVH_QueueBuilder.lxx
src/BVH/BVH_Tree.hxx
src/BVH/BVH_Tree.lxx
src/BVH/FILES
src/OpenGl/OpenGl_Layer.cxx
src/OpenGl/OpenGl_SceneGeometry.cxx
src/OpenGl/OpenGl_SceneGeometry.hxx
src/OpenGl/OpenGl_View.hxx
src/OpenGl/OpenGl_View_Raytrace.cxx
src/Select3D/Select3D_SensitiveSet.cxx
src/SelectMgr/SelectMgr_ViewerSelector.cxx
src/Shaders/RaytraceBase.fs
src/Shaders/RaytraceRender.fs

diff --git a/src/BVH/BVH_BinaryTree.hxx b/src/BVH/BVH_BinaryTree.hxx
new file mode 100644 (file)
index 0000000..52b8984
--- /dev/null
@@ -0,0 +1,104 @@
+// 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.
+
+#ifndef _BVH_BinaryTree_Header
+#define _BVH_BinaryTree_Header
+
+#include <BVH_QuadTree.hxx>
+
+//! Specialization of binary BVH tree.
+template<class T, int N>
+class BVH_Tree<T, N, BVH_BinaryTree> : public BVH_TreeBase<T, N>
+{
+public: //! @name custom data types
+
+  typedef typename BVH_TreeBase<T, N>::BVH_VecNt BVH_VecNt;
+
+public: //! @name methods for accessing individual nodes
+
+  //! Creates new empty BVH tree.
+  BVH_Tree() : BVH_TreeBase<T, N>() { }
+
+  //! Sets node type to 'outer'.
+  void SetOuter (const int theNodeIndex);
+
+  //! Sets node type to 'inner'.
+  void SetInner (const int theNodeIndex);
+
+  //! Returns index of the K-th child of the given inner node.
+  //! \tparam K the index of node child (0 or 1)
+  template<int K>
+  int Child (const int theNodeIndex) const;
+
+  //! Returns index of the K-th child of the given inner node.
+  //! \tparam K the index of node child (0 or 1)
+  template<int K>
+  int& Child (const int theNodeIndex);
+
+public: //! @name methods for adding/removing tree nodes
+
+  //! Removes all nodes from the tree.
+  void Clear();
+
+  //! Reserves internal BVH storage, so that it
+  //! can contain the given number of BVH nodes.
+  void Reserve (const int theNbNodes);
+
+  //! Adds new leaf node to the BVH.
+  int AddLeafNode (const BVH_VecNt& theMinPoint,
+                   const BVH_VecNt& theMaxPoint,
+                   const int        theBegElem,
+                   const int        theEndElem);
+
+  //! Adds new inner node to the BVH.
+  int AddInnerNode (const BVH_VecNt& theMinPoint,
+                    const BVH_VecNt& theMaxPoint,
+                    const int        theLftChild,
+                    const int        theRghChild);
+
+  //! Adds new leaf node to the BVH.
+  int AddLeafNode (const BVH_Box<T, N>& theAABB,
+                   const int            theBegElem,
+                   const int            theEndElem);
+
+  //! Adds new inner node to the BVH.
+  int AddInnerNode (const BVH_Box<T, N>& theAABB,
+                    const int            theLftChild,
+                    const int            theRghChild);
+
+  //! Adds new leaf node to the BVH with UNINITIALIZED bounds.
+  int AddLeafNode (const int theBegElem,
+                   const int theEndElem);
+
+  //! Adds new inner node to the BVH with UNINITIALIZED bounds.
+  int AddInnerNode (const int theLftChild,
+                    const int theRghChild);
+
+public: //! @name methods specific to binary BVH
+
+  //! 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;
+
+  //! Collapses the tree into QBVH an returns it. As a result, each
+  //! 2-nd level of current tree is kept and the rest are discarded.
+  BVH_Tree<T, N, BVH_QuadTree>* CollapseToQuadTree() const;
+
+};
+
+#include <BVH_BinaryTree.lxx>
+
+#endif // _BVH_BinaryTree_Header
diff --git a/src/BVH/BVH_BinaryTree.lxx b/src/BVH/BVH_BinaryTree.lxx
new file mode 100644 (file)
index 0000000..343288e
--- /dev/null
@@ -0,0 +1,307 @@
+// 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;
+}
index d42ff32..27fbc83 100644 (file)
@@ -17,7 +17,7 @@
 #define _BVH_Builder_Header
 
 #include <BVH_Set.hxx>
-#include <BVH_Tree.hxx>
+#include <BVH_BinaryTree.hxx>
 
 namespace BVH
 {
index 9d183a9..c3678bc 100644 (file)
@@ -311,9 +311,9 @@ namespace BVH
   {
     Standard_STATIC_ASSERT (N == 3 || N == 4);
 
-    const NCollection_Handle<BVH_Tree<T, N> >& aBVH = theGeometry.BVH();
+    const BVH_Tree<T, N, BVH_BinaryTree>* aBVH = theGeometry.BVH().get();
 
-    if (aBVH.IsNull())
+    if (aBVH == NULL)
     {
       return Standard_False;
     }
diff --git a/src/BVH/BVH_QuadTree.hxx b/src/BVH/BVH_QuadTree.hxx
new file mode 100644 (file)
index 0000000..e49ede6
--- /dev/null
@@ -0,0 +1,39 @@
+// 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.
+
+#ifndef _BVH_QuadTree_Header
+#define _BVH_QuadTree_Header
+
+#include <BVH_Tree.hxx>
+
+//! Specialization of quad BVH (QBVH) tree.
+template<class T, int N>
+class BVH_Tree<T, N, BVH_QuadTree> : public BVH_TreeBase<T, N>
+{
+public: //! @name general methods
+
+  //! Creates new empty BVH tree.
+  BVH_Tree() : BVH_TreeBase<T, N>() { }
+
+  //! Returns index of the K-th child of the given inner node.
+  //! \tparam K the index of node child (from 0 to 3)
+  template<int K>
+  int Child (const int theNodeIndex) const;
+
+};
+
+#include <BVH_QuadTree.lxx>
+
+#endif // _BVH_QuadTree_Header
diff --git a/src/BVH/BVH_QuadTree.lxx b/src/BVH/BVH_QuadTree.lxx
new file mode 100644 (file)
index 0000000..82adbef
--- /dev/null
@@ -0,0 +1,24 @@
+// 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.
+
+// =======================================================================
+// 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_QuadTree>::Child (const int theNodeIndex) const
+{
+  return BVH::Array<int, 4>::Value (this->myNodeInfoBuffer, theNodeIndex).y() + K;
+}
index dadf482..07cc2a8 100644 (file)
@@ -77,7 +77,8 @@ void BVH_QueueBuilder<T, N>::AddChildren (BVH_Tree<T, N>*
 
     theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
 
-    (anIdx == 0 ? theBVH->LeftChild (theNode) : theBVH->RightChild (theNode)) = aChildIndex;
+    (anIdx == 0 ? theBVH->template Child<0> (theNode)
+                : theBVH->template Child<1> (theNode)) = aChildIndex;
 
     // Check to see if the child node must be split
     const Standard_Boolean isLeaf = theSubNodes.NbPrims (anIdx) <= BVH_Builder<T, N>::myLeafNodeSize
index 25095a9..bf59c63 100644 (file)
 // 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>
+#ifndef _BVH_TreeBase_Header
+#define _BVH_TreeBase_Header
 
 #include <BVH_Box.hxx>
 
@@ -31,225 +29,150 @@ template<class T, int N> class BVH_Builder;
 //! such as collision detection, ray-tracing, searching of nearest
 //! objects, and view frustum culling.
 template<class T, int N>
-class BVH_Tree
+class BVH_TreeBase
 {
   friend class BVH_Builder<T, N>;
 
-public:
+public: //! @name custom data types
 
   typedef typename BVH_Box<T, N>::BVH_VecNt BVH_VecNt;
 
-public:
+public: //! @name general methods
 
   //! Creates new empty BVH tree.
-  BVH_Tree() : myDepth (0)
+  BVH_TreeBase() : myDepth (0) { }
+
+  //! Releases resources of BVH tree.
+  virtual ~BVH_TreeBase();
+
+  //! Returns depth (height) of BVH tree.
+  int Depth() const
+  {
+    return myDepth;
+  }
+
+  //! Returns total number of BVH tree nodes.
+  int Length() const
   {
-    //
+    return BVH::Array<int, 4>::Size (myNodeInfoBuffer);
   }
 
-  //! Reserves internal BVH storage, so that it
-  //! can contain specified number of tree nodes.
-  void Reserve (const Standard_Integer theNbNodes);
+public: //! @name methods for accessing individual nodes
 
   //! Returns minimum point of the given node.
-  BVH_VecNt& MinPoint (const Standard_Integer theNodeIndex)
+  BVH_VecNt& MinPoint (const int theNodeIndex)
   {
     return BVH::Array<T, N>::ChangeValue (myMinPointBuffer, theNodeIndex);
   }
 
   //! Returns maximum point of the given node.
-  BVH_VecNt& MaxPoint (const Standard_Integer theNodeIndex)
+  BVH_VecNt& MaxPoint (const int theNodeIndex)
   {
     return BVH::Array<T, N>::ChangeValue (myMaxPointBuffer, theNodeIndex);
   }
 
   //! Returns minimum point of the given node.
-  const BVH_VecNt& MinPoint (const Standard_Integer theNodeIndex) const
+  const BVH_VecNt& MinPoint (const int theNodeIndex) const
   {
     return BVH::Array<T, N>::Value (myMinPointBuffer, theNodeIndex);
   }
 
   //! Returns maximum point of the given node.
-  const BVH_VecNt& MaxPoint (const Standard_Integer theNodeIndex) const
+  const BVH_VecNt& MaxPoint (const int theNodeIndex) const
   {
     return BVH::Array<T, N>::Value (myMaxPointBuffer, theNodeIndex);
   }
 
-  //! Returns index of left child of the given inner node.
-  Standard_Integer& LeftChild (const Standard_Integer theNodeIndex)
-  {
-    return BVH::Array<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 BVH::Array<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 BVH::Array<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 BVH::Array<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).z();
-  }
-
   //! Returns index of first primitive of the given leaf node.
-  Standard_Integer& BegPrimitive (const Standard_Integer theNodeIndex)
+  int& BegPrimitive (const int theNodeIndex)
   {
-    return BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y();
+    return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y();
   }
 
-  //! Returns index of first primitive of the given leaf node.
-  Standard_Integer BegPrimitive (const Standard_Integer theNodeIndex) const
+  //! Returns index of last primitive of the given leaf node.
+  int& EndPrimitive (const int theNodeIndex)
   {
-    return BVH::Array<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).y();
+    return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z();
   }
 
-  //! Returns index of last primitive of the given leaf node.
-  Standard_Integer& EndPrimitive (const Standard_Integer theNodeIndex)
+  //! Returns index of first primitive of the given leaf node.
+  int BegPrimitive (const int theNodeIndex) const
   {
-    return BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z();
+    return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).y();
   }
 
   //! Returns index of last primitive of the given leaf node.
-  Standard_Integer EndPrimitive (const Standard_Integer theNodeIndex) const
+  int EndPrimitive (const int theNodeIndex) const
   {
-    return BVH::Array<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).z();
+    return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).z();
   }
 
-  //! Returns number of primitives for the given tree node.
-  Standard_Integer NbPrimitives (const Standard_Integer theNodeIndex) const
+  //! Returns number of primitives in the given leaf node.
+  int NbPrimitives (const int theNodeIndex) const
   {
     return EndPrimitive (theNodeIndex) - BegPrimitive (theNodeIndex) + 1;
   }
 
   //! Returns level (depth) of the given node.
-  Standard_Integer& Level (const Standard_Integer theNodeIndex)
+  int& Level (const int theNodeIndex)
   {
-    return BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).w();
+    return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).w();
   }
 
   //! Returns level (depth) of the given node.
-  Standard_Integer Level (const Standard_Integer theNodeIndex) const
+  int Level (const int theNodeIndex) const
   {
-    return BVH::Array<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).w();
+    return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).w();
   }
 
-  //! Is node a leaf (outer)?
-  Standard_Boolean IsOuter (const Standard_Integer theNodeIndex) const
+  //! Checks whether the given node is outer.
+  bool IsOuter (const int theNodeIndex) const
   {
-    return BVH::Array<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).x() != 0;
+    return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).x() != 0;
   }
 
-  //! Sets node type to 'outer'.
-  void SetOuter (const Standard_Integer theNodeIndex)
-  {
-    BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).x() = 1;
-  }
-
-  //! Sets node type to 'inner'.
-  void SetInner (const Standard_Integer theNodeIndex)
-  {
-    BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).x() = 0;
-  }
+public: //! @name methods for accessing serialized tree data
 
-  //! Returns total number of BVH nodes.
-  Standard_Integer Length() const
+  //! Returns array of node data records.
+  BVH_Array4i& NodeInfoBuffer()
   {
-    return BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer);
+    return myNodeInfoBuffer;
   }
 
-  //! Returns depth of BVH tree from last build.
-  Standard_Integer Depth() const
+  //! Returns array of node data records.
+  const BVH_Array4i& NodeInfoBuffer() const
   {
-    return myDepth;
+    return 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);
-
-  //! Adds new leaf node to the BVH with UNINITIALIZED bounds.
-  Standard_Integer AddLeafNode (const Standard_Integer theBegElem,
-                                const Standard_Integer theEndElem);
-
-  //! Adds new inner node to the BVH with UNINITIALIZED bounds.
-  Standard_Integer AddInnerNode (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.
+  //! Returns array of node minimum points.
   typename BVH::ArrayType<T, N>::Type& MinPointBuffer()
   {
     return myMinPointBuffer;
   }
 
-  //! Returns array of node min points.
-  const typename BVH::ArrayType<T, N>::Type& MinPointBuffer() const
-  {
-    return myMinPointBuffer;
-  }
-
-  //! Returns array of node max points.
+  //! Returns array of node maximum points.
   typename BVH::ArrayType<T, N>::Type& MaxPointBuffer()
   {
     return myMaxPointBuffer;
   }
 
-  //! Returns array of node max points.
-  const typename BVH::ArrayType<T, N>::Type& MaxPointBuffer() const
+  //! Returns array of node minimum points.
+  const typename BVH::ArrayType<T, N>::Type& MinPointBuffer() const
   {
-    return myMaxPointBuffer;
+    return myMinPointBuffer;
   }
 
-  //! Returns array of node data records.
-  BVH_Array4i& NodeInfoBuffer()
+  //! Returns array of node maximum points.
+  const typename BVH::ArrayType<T, N>::Type& MaxPointBuffer() const
   {
-    return myNodeInfoBuffer;
+    return myMaxPointBuffer;
   }
 
-  //! Returns array of node data records.
-  const BVH_Array4i& NodeInfoBuffer() const
-  {
-    return myNodeInfoBuffer;
-  }
+public: //! @name protected fields
 
-protected:
+  //! Array of node data records.
+  BVH_Array4i myNodeInfoBuffer;
 
   //! Array of node minimum points.
   typename BVH::ArrayType<T, N>::Type myMinPointBuffer;
@@ -257,14 +180,24 @@ protected:
   //! Array of node maximum points.
   typename BVH::ArrayType<T, N>::Type myMaxPointBuffer;
 
-  //! Array of node data records.
-  BVH_Array4i myNodeInfoBuffer;
+  //! Current depth of BVH tree (set by builder).
+  int myDepth;
 
-  //! Current depth of BVH tree.
-  Standard_Integer myDepth;
+};
 
+//! Type corresponding to quad BVH.
+struct BVH_QuadTree { };
+
+//! Type corresponding to binary BVH.
+struct BVH_BinaryTree { };
+
+//! BVH tree with given arity (2 or 4).
+template<class T, int N, class Arity = BVH_BinaryTree>
+class BVH_Tree
+{
+  // Invalid type
 };
 
 #include <BVH_Tree.lxx>
 
-#endif // _BVH_Tree_Header
+#endif // _BVH_TreeBase_Header
index 549c689..ec6473d 100644 (file)
 // commercial license or contractual agreement.
 
 // =======================================================================
-// function : Clear
-// purpose  :
+// function : ~BVH_TreeBase
+// purpose  : Releases resources of BVH tree
 // =======================================================================
 template<class T, int N>
-void BVH_Tree<T, N>::Clear()
+BVH_TreeBase<T, N>::~BVH_TreeBase()
 {
-  myDepth = 0;
-
-  BVH::Array<T, N>::Clear (myMinPointBuffer);
-  BVH::Array<T, N>::Clear (myMaxPointBuffer);
-
-  BVH::Array<Standard_Integer, 4>::Clear (myNodeInfoBuffer);
-}
-
-// =======================================================================
-// function : AddLeafNode
-// purpose  :
-// =======================================================================
-template<class T, int N>
-Standard_Integer BVH_Tree<T, N>::AddLeafNode (const Standard_Integer theBegElem,
-                                              const Standard_Integer theEndElem)
-{
-  BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0));
-
-  return static_cast<Standard_Integer> (BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1);
-}
-
-// =======================================================================
-// function : AddInnerNode
-// purpose  :
-// =======================================================================
-template<class T, int N>
-Standard_Integer BVH_Tree<T, N>::AddInnerNode (const Standard_Integer theLftChild,
-                                               const Standard_Integer theRghChild)
-{
-  BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0));
-
-  return static_cast<Standard_Integer> (BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer)  - 1);
-}
-
-// =======================================================================
-// 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)
-{
-  BVH::Array<T, N>::Append (myMinPointBuffer, theMinPoint);
-  BVH::Array<T, N>::Append (myMaxPointBuffer, theMaxPoint);
-
-  BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0));
-
-  return static_cast<Standard_Integer> (BVH::Array<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)
-{
-  BVH::Array<T, N>::Append (myMinPointBuffer, theMinPoint);
-  BVH::Array<T, N>::Append (myMaxPointBuffer, theMaxPoint);
-
-  BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0));
-
-  return static_cast<Standard_Integer> (BVH::Array<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 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>*  theTree,
-                    const Standard_Integer 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->LeftChild (theNode)),
-                             theTree->MaxPoint (theTree->LeftChild (theNode)));
-
-      if (theProb > 0.0)
-      {
-        EstimateSAH (theTree, theTree->LeftChild (theNode),
-                     theProb * aLftBox.Area() / aBox.Area(), theSAH);
-      }
-
-      BVH_Box<T, N> aRghBox (theTree->MinPoint (theTree->RightChild (theNode)),
-                             theTree->MaxPoint (theTree->RightChild (theNode)));
-
-      if (theProb > 0.0)
-      {
-        EstimateSAH (theTree, theTree->RightChild (theNode),
-                     theProb * 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);
-  BVH::EstimateSAH (this, 0, static_cast<T> (1.0), aSAH);
-  return aSAH;
-}
-
-// =======================================================================
-// function : Reserve
-// purpose  :
-// =======================================================================
-template<class T, int N>
-void BVH_Tree<T, N>::Reserve (const Standard_Integer theNbNodes)
-{
-  BVH::Array<T,                N>::Reserve (myMinPointBuffer, theNbNodes);
-  BVH::Array<T,                N>::Reserve (myMaxPointBuffer, theNbNodes);
-  BVH::Array<Standard_Integer, 4>::Reserve (myNodeInfoBuffer, theNbNodes);
-}
+  //
+}
\ No newline at end of file
index cb4d59b..88ff44d 100644 (file)
@@ -39,6 +39,10 @@ BVH_SweepPlaneBuilder.hxx
 BVH_SweepPlaneBuilder.lxx
 BVH_Tree.hxx
 BVH_Tree.lxx
+BVH_BinaryTree.hxx
+BVH_BinaryTree.lxx
+BVH_QuadTree.hxx
+BVH_QuadTree.lxx
 BVH_Triangulation.hxx
 BVH_Triangulation.lxx
 BVH_Types.hxx
index 8b420d7..a1ec616 100644 (file)
@@ -516,8 +516,8 @@ void OpenGl_Layer::traverse (OpenGl_BVHTreeSelector& theSelector) const
     {
       if (!aBVHTree->IsOuter (aNode))
       {
-        const Standard_Integer aLeftChildIdx  = aBVHTree->LeftChild  (aNode);
-        const Standard_Integer aRightChildIdx = aBVHTree->RightChild (aNode);
+        const Standard_Integer aLeftChildIdx  = aBVHTree->Child<0> (aNode);
+        const Standard_Integer aRightChildIdx = aBVHTree->Child<1> (aNode);
         const Standard_Boolean isLeftChildIn  = theSelector.Intersect (aBVHTree->MinPoint (aLeftChildIdx),
                                                                        aBVHTree->MaxPoint (aLeftChildIdx));
         const Standard_Boolean isRightChildIn = theSelector.Intersect (aBVHTree->MinPoint (aRightChildIdx),
index cbdb7d0..b3d7de2 100755 (executable)
@@ -118,6 +118,26 @@ OpenGl_RaytraceLight::OpenGl_RaytraceLight (const BVH_Vec4f& theDiffuse,
 }
 
 // =======================================================================
+// function : QuadBVH
+// purpose  : Returns quad BVH (QBVH) tree produced from binary BVH
+// =======================================================================
+const QuadBvhHandle& OpenGl_TriangleSet::QuadBVH()
+{
+  if (!myIsDirty)
+  {
+    Standard_ASSERT_RAISE (!myQuadBVH.IsNull(), "Error! BVH was not collapsed into QBVH");
+  }
+  else
+  {
+    myQuadBVH = BVH()->CollapseToQuadTree(); // build binary BVH and collapse it
+
+    myBVH->Clear(); // erase binary BVH
+  }
+
+  return myQuadBVH;
+}
+
+// =======================================================================
 // function : Center
 // purpose  : Returns centroid position along the given axis
 // =======================================================================
@@ -225,7 +245,7 @@ struct OpenGL_BVHParallelBuilder
       Set->Objects().ChangeValue (static_cast<Standard_Integer> (theObjectIdx)).operator->());
 
     if (aTriangleSet != NULL)
-      aTriangleSet->BVH();
+      aTriangleSet->QuadBVH();
   }
 };
 
@@ -246,9 +266,9 @@ Standard_Boolean OpenGl_RaytraceGeometry::ProcessAcceleration()
   aTimer.Start();
 #endif
 
-  OSD_Parallel::For(0, Size(), OpenGL_BVHParallelBuilder(this));
+  OSD_Parallel::For (0, Size(), OpenGL_BVHParallelBuilder (this));
 
-  myBottomLevelTreeDepth = 0;
+  myBotLevelTreeDepth = 1;
 
   for (Standard_Integer anObjectIdx = 0; anObjectIdx < Size(); ++anObjectIdx)
   {
@@ -258,10 +278,10 @@ Standard_Boolean OpenGl_RaytraceGeometry::ProcessAcceleration()
     Standard_ASSERT_RETURN (aTriangleSet != NULL,
       "Error! Failed to get triangulation of OpenGL element", Standard_False);
 
-    Standard_ASSERT_RETURN (!aTriangleSet->BVH().IsNull(),
+    Standard_ASSERT_RETURN (!aTriangleSet->QuadBVH().IsNull(),
       "Error! Failed to update bottom-level BVH of OpenGL element", Standard_False);
 
-    NCollection_Handle<BVH_Tree<Standard_ShortReal, 3> > aBVH = aTriangleSet->BVH();
+    QuadBvhHandle aBVH = aTriangleSet->QuadBVH();
 
     // correct data array of bottom-level BVH to set special flag for outer
     // nodes in order to distinguish them from outer nodes of top-level BVH
@@ -273,7 +293,7 @@ Standard_Boolean OpenGl_RaytraceGeometry::ProcessAcceleration()
       }
     }
 
-    myBottomLevelTreeDepth = Max (myBottomLevelTreeDepth, aTriangleSet->BVH()->Depth());
+    myBotLevelTreeDepth = Max (myBotLevelTreeDepth, aTriangleSet->QuadBVH()->Depth());
   }
 
 #ifdef RAY_TRACE_PRINT_INFO
@@ -288,7 +308,12 @@ Standard_Boolean OpenGl_RaytraceGeometry::ProcessAcceleration()
   aTimer.Start();
 #endif
 
-  NCollection_Handle<BVH_Tree<Standard_ShortReal, 3> > aBVH = BVH();
+  QuadBvhHandle aBVH = QuadBVH();
+
+  Standard_ASSERT_RETURN (!aBVH.IsNull(),
+    "Error! Failed to update high-level BVH of ray-tracing scene", Standard_False);
+
+  myTopLevelTreeDepth = aBVH->Depth();
 
 #ifdef RAY_TRACE_PRINT_INFO
   aTimer.Stop();
@@ -297,52 +322,69 @@ Standard_Boolean OpenGl_RaytraceGeometry::ProcessAcceleration()
     aTimer.ElapsedTime() << std::endl;
 #endif
 
-  Standard_ASSERT_RETURN (!aBVH.IsNull(),
-    "Error! Failed to update high-level BVH of ray-tracing scene", Standard_False);
-
-  myHighLevelTreeDepth = aBVH->Depth();
-
   Standard_Integer aVerticesOffset = 0;
   Standard_Integer aElementsOffset = 0;
-  Standard_Integer aBVHNodesOffset = BVH()->Length();
+  Standard_Integer aBvhNodesOffset = QuadBVH()->Length();
 
   for (Standard_Integer aNodeIdx = 0; aNodeIdx < aBVH->Length(); ++aNodeIdx)
   {
-    if (!aBVH->IsOuter (aNodeIdx))
-      continue;
+    if (aBVH->IsOuter (aNodeIdx))
+    {
+      Standard_ASSERT_RETURN (aBVH->BegPrimitive (aNodeIdx) == aBVH->EndPrimitive (aNodeIdx),
+        "Error! Invalid leaf node in high-level BVH (contains several objects)", Standard_False);
 
-    Standard_ASSERT_RETURN (aBVH->BegPrimitive (aNodeIdx) == aBVH->EndPrimitive (aNodeIdx),
-      "Error! Invalid leaf node in high-level BVH (contains several objects)", Standard_False);
+      const Standard_Integer anObjectIdx = aBVH->BegPrimitive (aNodeIdx);
 
-    Standard_Integer anObjectIdx = aBVH->BegPrimitive (aNodeIdx);
+      Standard_ASSERT_RETURN (anObjectIdx < myObjects.Size(),
+        "Error! Invalid leaf node in high-level BVH (contains out-of-range object)", Standard_False);
 
-    Standard_ASSERT_RETURN (anObjectIdx < myObjects.Size(),
-      "Error! Invalid leaf node in high-level BVH (contains out-of-range object)", Standard_False);
+      OpenGl_TriangleSet* aTriangleSet = dynamic_cast<OpenGl_TriangleSet*> (myObjects (anObjectIdx).get());
 
-    OpenGl_TriangleSet* aTriangleSet = dynamic_cast<OpenGl_TriangleSet*> (
-      myObjects.ChangeValue (anObjectIdx).operator->());
+      // Note: We overwrite node info record to store parameters
+      // of bottom-level BVH and triangulation of OpenGL element
 
-    // Note: We overwrite node info record to store parameters
-    // of bottom-level BVH and triangulation of OpenGL element
+      aBVH->NodeInfoBuffer()[aNodeIdx] = BVH_Vec4i (anObjectIdx + 1, // to keep leaf flag
+                                                    aBvhNodesOffset,
+                                                    aVerticesOffset,
+                                                    aElementsOffset);
 
-    aBVH->NodeInfoBuffer().at (aNodeIdx) = BVH_Vec4i (
-      anObjectIdx + 1 /* to keep leaf flag */, aBVHNodesOffset, aVerticesOffset, aElementsOffset);
+      aVerticesOffset += static_cast<Standard_Integer> (aTriangleSet->Vertices.size());
+      aElementsOffset += static_cast<Standard_Integer> (aTriangleSet->Elements.size());
 
-    aVerticesOffset += (int)aTriangleSet->Vertices.size();
-    aElementsOffset += (int)aTriangleSet->Elements.size();
-    aBVHNodesOffset += aTriangleSet->BVH()->Length();
+      aBvhNodesOffset += aTriangleSet->QuadBVH()->Length();
+    }
   }
 
   return Standard_True;
 }
 
 // =======================================================================
+// function : QuadBVH
+// purpose  : Returns quad BVH (QBVH) tree produced from binary BVH
+// =======================================================================
+const QuadBvhHandle& OpenGl_RaytraceGeometry::QuadBVH()
+{
+  if (!myIsDirty)
+  {
+    Standard_ASSERT_RAISE (!myQuadBVH.IsNull(), "Error! BVH was not collapsed into QBVH");
+  }
+  else
+  {
+    myQuadBVH = BVH()->CollapseToQuadTree(); // build binary BVH and collapse it
+
+    myBVH->Clear(); // erase binary BVH
+  }
+
+  return myQuadBVH;
+}
+
+// =======================================================================
 // function : AccelerationOffset
 // purpose  : Returns offset of bottom-level BVH for given leaf node
 // =======================================================================
 Standard_Integer OpenGl_RaytraceGeometry::AccelerationOffset (Standard_Integer theNodeIdx)
 {
-  const NCollection_Handle<BVH_Tree<Standard_ShortReal, 3> >& aBVH = BVH();
+  const QuadBvhHandle& aBVH = QuadBVH();
 
   if (theNodeIdx >= aBVH->Length() || !aBVH->IsOuter (theNodeIdx))
     return INVALID_OFFSET;
@@ -356,7 +398,7 @@ Standard_Integer OpenGl_RaytraceGeometry::AccelerationOffset (Standard_Integer t
 // =======================================================================
 Standard_Integer OpenGl_RaytraceGeometry::VerticesOffset (Standard_Integer theNodeIdx)
 {
-  const NCollection_Handle<BVH_Tree<Standard_ShortReal, 3> >& aBVH = BVH();
+  const QuadBvhHandle& aBVH = QuadBVH();
 
   if (theNodeIdx >= aBVH->Length() || !aBVH->IsOuter (theNodeIdx))
     return INVALID_OFFSET;
@@ -370,7 +412,7 @@ Standard_Integer OpenGl_RaytraceGeometry::VerticesOffset (Standard_Integer theNo
 // =======================================================================
 Standard_Integer OpenGl_RaytraceGeometry::ElementsOffset (Standard_Integer theNodeIdx)
 {
-  const NCollection_Handle<BVH_Tree<Standard_ShortReal, 3> >& aBVH = BVH();
+  const QuadBvhHandle& aBVH = QuadBVH();
 
   if (theNodeIdx >= aBVH->Length() || !aBVH->IsOuter (theNodeIdx))
     return INVALID_OFFSET;
@@ -384,7 +426,7 @@ Standard_Integer OpenGl_RaytraceGeometry::ElementsOffset (Standard_Integer theNo
 // =======================================================================
 OpenGl_TriangleSet* OpenGl_RaytraceGeometry::TriangleSet (Standard_Integer theNodeIdx)
 {
-  const NCollection_Handle<BVH_Tree<Standard_ShortReal, 3> >& aBVH = BVH();
+  const QuadBvhHandle& aBVH = QuadBVH();
 
   if (theNodeIdx >= aBVH->Length() || !aBVH->IsOuter (theNodeIdx))
     return NULL;
@@ -392,8 +434,8 @@ OpenGl_TriangleSet* OpenGl_RaytraceGeometry::TriangleSet (Standard_Integer theNo
   if (aBVH->NodeInfoBuffer().at (theNodeIdx).x() > myObjects.Size())
     return NULL;
 
-  return dynamic_cast<OpenGl_TriangleSet*> (myObjects.ChangeValue (
-    aBVH->NodeInfoBuffer().at (theNodeIdx).x() - 1).operator->());
+  return dynamic_cast<OpenGl_TriangleSet*> (
+    myObjects (aBVH->NodeInfoBuffer().at (theNodeIdx).x() - 1).get());
 }
 
 // =======================================================================
index d64bfbf..9cde629 100755 (executable)
@@ -157,6 +157,9 @@ public:
   }
 };
 
+//! Shared pointer to quad BVH (QBVH) tree.
+typedef NCollection_Handle<BVH_Tree<Standard_ShortReal, 3, BVH_QuadTree> > QuadBvhHandle;
+
 //! Triangulation of single OpenGL primitive array.
 class OpenGl_TriangleSet : public BVH_Triangulation<Standard_ShortReal, 3>
 {
@@ -170,13 +173,7 @@ public:
   //! Creates new OpenGL element triangulation.
   OpenGl_TriangleSet (const Standard_Size theArrayID);
 
-  //! Releases resources of OpenGL element triangulation.
-  ~OpenGl_TriangleSet()
-  {
-    //
-  }
-
-  //! Returns Id of associated primitive array.
+  //! Returns ID of associated primitive array.
   Standard_Size AssociatedPArrayID() const
   {
     return myArrayID;
@@ -202,25 +199,29 @@ public:
     }
   }
 
-  //! Returns AABB of the given object.
-  using BVH_Triangulation<Standard_ShortReal, 3>::Box;
-
   //! Returns AABB of primitive set.
   BVH_BoxNt Box() const;
 
+  //! Returns AABB of the given object.
+  using BVH_Triangulation<Standard_ShortReal, 3>::Box;
+
   //! Returns centroid position along the given axis.
   Standard_ShortReal Center (const Standard_Integer theIndex, const Standard_Integer theAxis) const;
 
+  //! Returns quad BVH (QBVH) tree produced from binary BVH.
+  const QuadBvhHandle& QuadBVH();
+
 public:
 
   BVH_Array3f Normals; //!< Array of vertex normals.
-
-  BVH_Array2f TexCrds; //!< Array of vertex UV coords.
+  BVH_Array2f TexCrds; //!< Array of texture coords.
 
 private:
 
   Standard_Size myArrayID; //!< ID of associated primitive array.
 
+  QuadBvhHandle myQuadBVH; //!< QBVH produced from binary BVH tree.
+
 };
 
 //! Stores geometry of ray-tracing scene.
@@ -255,8 +256,8 @@ public:
   //! Creates uninitialized ray-tracing geometry.
   OpenGl_RaytraceGeometry()
   : BVH_Geometry<Standard_ShortReal, 3>(),
-    myHighLevelTreeDepth (0),
-    myBottomLevelTreeDepth (0)
+    myTopLevelTreeDepth (0),
+    myBotLevelTreeDepth (0)
   {
     //
   }
@@ -306,8 +307,17 @@ public: //! @name methods related to acceleration structure
   //! @note Can be used after processing acceleration structure.
   OpenGl_TriangleSet* TriangleSet (Standard_Integer theNodeIdx);
 
+  //! Returns quad BVH (QBVH) tree produced from binary BVH.
+  const QuadBvhHandle& QuadBVH();
+
 public: //! @name methods related to texture management
 
+  //! Checks if scene contains textured objects.
+  Standard_Boolean HasTextures() const
+  {
+    return !myTextures.IsEmpty();
+  }
+
   //! Adds new OpenGL texture to the scene and returns its index.
   Standard_Integer AddTexture (const Handle(OpenGl_Texture)& theTexture);
 
@@ -326,12 +336,6 @@ public: //! @name methods related to texture management
     return myTextureHandles;
   }
 
-  //! Checks if scene contains textured objects.
-  Standard_Boolean HasTextures() const
-  {
-    return !myTextures.IsEmpty();
-  }
-
   //! Releases OpenGL resources.
   void ReleaseResources (const Handle(OpenGl_Context)& theContext)
   {
@@ -344,25 +348,27 @@ public: //! @name methods related to texture management
 
 public: //! @name auxiliary methods
 
-  //! Returns depth of high-level scene BVH from last build.
-  Standard_Integer HighLevelTreeDepth() const
+  //! Returns depth of top-level scene BVH from last build.
+  Standard_Integer TopLevelTreeDepth() const
   {
-    return myHighLevelTreeDepth;
+    return myTopLevelTreeDepth;
   }
 
   //! Returns maximum depth of bottom-level scene BVHs from last build.
-  Standard_Integer BottomLevelTreeDepth() const
+  Standard_Integer BotLevelTreeDepth() const
   {
-    return myBottomLevelTreeDepth;
+    return myBotLevelTreeDepth;
   }
 
 protected:
 
-  NCollection_Vector<Handle(OpenGl_Texture)> myTextures;             //!< Array of texture maps shared between rendered objects
-  Handle(OpenGl_Sampler)                     myTextureSampler;       //!< Sampler object providing fixed sampling params for texures
-  std::vector<GLuint64>                      myTextureHandles;       //!< Array of unique 64-bit texture handles obtained from OpenGL
-  Standard_Integer                           myHighLevelTreeDepth;   //!< Depth of high-level scene BVH from last build
-  Standard_Integer                           myBottomLevelTreeDepth; //!< Maximum depth of bottom-level scene BVHs from last build
+  NCollection_Vector<Handle(OpenGl_Texture)> myTextures;           //!< Array of texture maps shared between rendered objects
+  Handle(OpenGl_Sampler)                     myTextureSampler;     //!< Sampler object providing fixed sampling params for texures
+  std::vector<GLuint64>                      myTextureHandles;     //!< Array of unique 64-bit texture handles obtained from OpenGL
+  Standard_Integer                           myTopLevelTreeDepth;  //!< Depth of high-level scene BVH from last build
+  Standard_Integer                           myBotLevelTreeDepth;  //!< Maximum depth of bottom-level scene BVHs from last build
+
+  QuadBvhHandle myQuadBVH; //!< QBVH produced from binary BVH tree.
 
 };
 
index 3005cd1..0b713c0 100644 (file)
@@ -771,7 +771,7 @@ protected: //! @name data types related to ray-tracing
   static const Standard_Integer THE_DEFAULT_NB_BOUNCES = 3;
 
   //! Default size of traversal stack.
-  static const Standard_Integer THE_DEFAULT_STACK_SIZE = 24;
+  static const Standard_Integer THE_DEFAULT_STACK_SIZE = 10;
 
   //! Compile-time ray-tracing parameters.
   struct RaytracingParams
index 5b2585c..37ad4d9 100644 (file)
@@ -1225,7 +1225,7 @@ Standard_Boolean OpenGl_View::initRaytraceResources (const Handle(OpenGl_Context
       return Standard_True;
 
     const Standard_Integer aRequiredStackSize =
-      myRaytraceGeometry.HighLevelTreeDepth() + myRaytraceGeometry.BottomLevelTreeDepth();
+      myRaytraceGeometry.TopLevelTreeDepth() + myRaytraceGeometry.BotLevelTreeDepth();
 
     if (myRaytraceParameters.StackSize < aRequiredStackSize)
     {
@@ -1335,7 +1335,7 @@ Standard_Boolean OpenGl_View::initRaytraceResources (const Handle(OpenGl_Context
     if (myIsRaytraceDataValid)
     {
       myRaytraceParameters.StackSize = Max (THE_DEFAULT_STACK_SIZE,
-        myRaytraceGeometry.HighLevelTreeDepth() + myRaytraceGeometry.BottomLevelTreeDepth());
+        myRaytraceGeometry.TopLevelTreeDepth() + myRaytraceGeometry.BotLevelTreeDepth());
     }
 
     TCollection_AsciiString aPrefixString  = generateShaderPrefix (theGlContext);
@@ -1861,13 +1861,13 @@ Standard_Boolean OpenGl_View::uploadRaytraceData (const Handle(OpenGl_Context)&
     aTotalVerticesNb += aTriangleSet->Vertices.size();
     aTotalElementsNb += aTriangleSet->Elements.size();
 
-    Standard_ASSERT_RETURN (!aTriangleSet->BVH().IsNull(),
+    Standard_ASSERT_RETURN (!aTriangleSet->QuadBVH().IsNull(),
       "Error: Failed to get bottom-level BVH of OpenGL element", Standard_False);
 
-    aTotalBVHNodesNb += aTriangleSet->BVH()->NodeInfoBuffer().size();
+    aTotalBVHNodesNb += aTriangleSet->QuadBVH()->NodeInfoBuffer().size();
   }
 
-  aTotalBVHNodesNb += myRaytraceGeometry.BVH()->NodeInfoBuffer().size();
+  aTotalBVHNodesNb += myRaytraceGeometry.QuadBVH()->NodeInfoBuffer().size();
 
   if (aTotalBVHNodesNb != 0)
   {
@@ -1911,7 +1911,7 @@ Standard_Boolean OpenGl_View::uploadRaytraceData (const Handle(OpenGl_Context)&
     return Standard_False;
   }
 
-  const NCollection_Handle<BVH_Tree<Standard_ShortReal, 3> >& aBVH = myRaytraceGeometry.BVH();
+  const QuadBvhHandle& aBVH = myRaytraceGeometry.QuadBVH();
 
   if (aBVH->Length() > 0)
   {
@@ -1938,16 +1938,16 @@ Standard_Boolean OpenGl_View::uploadRaytraceData (const Handle(OpenGl_Context)&
     Standard_ASSERT_RETURN (aBVHOffset != OpenGl_RaytraceGeometry::INVALID_OFFSET,
       "Error: Failed to get offset for bottom-level BVH", Standard_False);
 
-    const Standard_Integer aBvhBuffersSize = aTriangleSet->BVH()->Length();
+    const Standard_Integer aBvhBuffersSize = aTriangleSet->QuadBVH()->Length();
 
     if (aBvhBuffersSize != 0)
     {
       aResult &= mySceneNodeInfoTexture->SubData (theGlContext, aBVHOffset, aBvhBuffersSize,
-        reinterpret_cast<const GLuint*> (&aTriangleSet->BVH()->NodeInfoBuffer().front()));
+        reinterpret_cast<const GLuint*> (&aTriangleSet->QuadBVH()->NodeInfoBuffer().front()));
       aResult &= mySceneMinPointTexture->SubData (theGlContext, aBVHOffset, aBvhBuffersSize,
-        reinterpret_cast<const GLfloat*> (&aTriangleSet->BVH()->MinPointBuffer().front()));
+        reinterpret_cast<const GLfloat*> (&aTriangleSet->QuadBVH()->MinPointBuffer().front()));
       aResult &= mySceneMaxPointTexture->SubData (theGlContext, aBVHOffset, aBvhBuffersSize,
-        reinterpret_cast<const GLfloat*> (&aTriangleSet->BVH()->MaxPointBuffer().front()));
+        reinterpret_cast<const GLfloat*> (&aTriangleSet->QuadBVH()->MaxPointBuffer().front()));
 
       if (!aResult)
       {
@@ -2014,38 +2014,40 @@ Standard_Boolean OpenGl_View::uploadRaytraceData (const Handle(OpenGl_Context)&
 
 #ifdef RAY_TRACE_PRINT_INFO
 
-  Standard_ShortReal aMemUsed = 0.f;
+  Standard_ShortReal aMemTrgUsed = 0.f;
+  Standard_ShortReal aMemBvhUsed = 0.f;
 
   for (Standard_Integer anElemIdx = 0; anElemIdx < myRaytraceGeometry.Size(); ++anElemIdx)
   {
-    OpenGl_TriangleSet* aTriangleSet = dynamic_cast<OpenGl_TriangleSet*> (
-      myRaytraceGeometry.Objects().ChangeValue (anElemIdx).operator->());
+    OpenGl_TriangleSet* aTriangleSet = dynamic_cast<OpenGl_TriangleSet*> (myRaytraceGeometry.Objects()(anElemIdx).get());
 
-    aMemUsed += static_cast<Standard_ShortReal> (
+    aMemTrgUsed += static_cast<Standard_ShortReal> (
       aTriangleSet->Vertices.size() * sizeof (BVH_Vec3f));
-    aMemUsed += static_cast<Standard_ShortReal> (
+    aMemTrgUsed += static_cast<Standard_ShortReal> (
       aTriangleSet->Normals.size() * sizeof (BVH_Vec3f));
-    aMemUsed += static_cast<Standard_ShortReal> (
+    aMemTrgUsed += static_cast<Standard_ShortReal> (
       aTriangleSet->TexCrds.size() * sizeof (BVH_Vec2f));
-    aMemUsed += static_cast<Standard_ShortReal> (
+    aMemTrgUsed += static_cast<Standard_ShortReal> (
       aTriangleSet->Elements.size() * sizeof (BVH_Vec4i));
 
-    aMemUsed += static_cast<Standard_ShortReal> (
-      aTriangleSet->BVH()->NodeInfoBuffer().size() * sizeof (BVH_Vec4i));
-    aMemUsed += static_cast<Standard_ShortReal> (
-      aTriangleSet->BVH()->MinPointBuffer().size() * sizeof (BVH_Vec3f));
-    aMemUsed += static_cast<Standard_ShortReal> (
-      aTriangleSet->BVH()->MaxPointBuffer().size() * sizeof (BVH_Vec3f));
+    aMemBvhUsed += static_cast<Standard_ShortReal> (
+      aTriangleSet->QuadBVH()->NodeInfoBuffer().size() * sizeof (BVH_Vec4i));
+    aMemBvhUsed += static_cast<Standard_ShortReal> (
+      aTriangleSet->QuadBVH()->MinPointBuffer().size() * sizeof (BVH_Vec3f));
+    aMemBvhUsed += static_cast<Standard_ShortReal> (
+      aTriangleSet->QuadBVH()->MaxPointBuffer().size() * sizeof (BVH_Vec3f));
   }
 
-  aMemUsed += static_cast<Standard_ShortReal> (
-    myRaytraceGeometry.BVH()->NodeInfoBuffer().size() * sizeof (BVH_Vec4i));
-  aMemUsed += static_cast<Standard_ShortReal> (
-    myRaytraceGeometry.BVH()->MinPointBuffer().size() * sizeof (BVH_Vec3f));
-  aMemUsed += static_cast<Standard_ShortReal> (
-    myRaytraceGeometry.BVH()->MaxPointBuffer().size() * sizeof (BVH_Vec3f));
+  aMemBvhUsed += static_cast<Standard_ShortReal> (
+    myRaytraceGeometry.QuadBVH()->NodeInfoBuffer().size() * sizeof (BVH_Vec4i));
+  aMemBvhUsed += static_cast<Standard_ShortReal> (
+    myRaytraceGeometry.QuadBVH()->MinPointBuffer().size() * sizeof (BVH_Vec3f));
+  aMemBvhUsed += static_cast<Standard_ShortReal> (
+    myRaytraceGeometry.QuadBVH()->MaxPointBuffer().size() * sizeof (BVH_Vec3f));
 
-  std::cout << "GPU Memory Used (MB): ~" << aMemUsed / 1048576 << std::endl;
+  std::cout << "GPU Memory Used (Mb):\n"
+    << "\tFor mesh: " << aMemTrgUsed / 1048576 << "\n"
+    << "\tFor BVHs: " << aMemBvhUsed / 1048576 << "\n";
 
 #endif
 
index f726c73..fabd023 100644 (file)
@@ -49,7 +49,7 @@ void Select3D_SensitiveSet::BVH()
 Standard_Boolean Select3D_SensitiveSet::Matches (SelectBasics_SelectingVolumeManager& theMgr,
                                                  SelectBasics_PickResult& thePickResult)
 {
-  const NCollection_Handle<BVH_Tree<Standard_Real, 3> >& aBVH = myContent->GetBVH();
+  const BVH_Tree<Standard_Real, 3, BVH_BinaryTree>* aBVH = myContent->GetBVH().get();
 
   thePickResult = SelectBasics_PickResult (RealLast(), RealLast());
 
index ecc735b..ddf9ba5 100644 (file)
@@ -361,8 +361,8 @@ void SelectMgr_ViewerSelector::traverseObject (const Handle(SelectMgr_Selectable
   {
     if (!aSensitivesTree->IsOuter (aNode))
     {
-      const Standard_Integer aLeftChildIdx  = aSensitivesTree->LeftChild  (aNode);
-      const Standard_Integer aRightChildIdx = aSensitivesTree->RightChild (aNode);
+      const Standard_Integer aLeftChildIdx  = aSensitivesTree->Child<0> (aNode);
+      const Standard_Integer aRightChildIdx = aSensitivesTree->Child<1> (aNode);
       const Standard_Boolean isLeftChildIn  =  aMgr.Overlaps (aSensitivesTree->MinPoint (aLeftChildIdx),
                                                               aSensitivesTree->MaxPoint (aLeftChildIdx));
       const Standard_Boolean isRightChildIn = aMgr.Overlaps (aSensitivesTree->MinPoint (aRightChildIdx),
@@ -467,8 +467,8 @@ void SelectMgr_ViewerSelector::TraverseSensitives()
     {
       if (!aBVHTree->IsOuter (aNode))
       {
-        const Standard_Integer aLeftChildIdx  = aBVHTree->LeftChild  (aNode);
-        const Standard_Integer aRightChildIdx = aBVHTree->RightChild (aNode);
+        const Standard_Integer aLeftChildIdx  = aBVHTree->Child<0> (aNode);
+        const Standard_Integer aRightChildIdx = aBVHTree->Child<1> (aNode);
         const Standard_Boolean isLeftChildIn  =
           mySelectingVolumeMgr.Overlaps (aBVHTree->MinPoint (aLeftChildIdx),
                                          aBVHTree->MaxPoint (aLeftChildIdx));
index 2356906..e7a3e3d 100644 (file)
@@ -322,38 +322,44 @@ float IntersectSphere (in SRay theRay, in float theRadius)
 // function : IntersectTriangle
 // purpose  : Computes ray-triangle intersection (branchless version)
 // =======================================================================
-float IntersectTriangle (in SRay theRay,
-                         in vec3 thePnt0,
-                         in vec3 thePnt1,
-                         in vec3 thePnt2,
-                         out vec2 theUV,
-                         out vec3 theNorm)
+void IntersectTriangle (in SRay theRay,
+                        in vec3 thePnt0,
+                        in vec3 thePnt1,
+                        in vec3 thePnt2,
+                        out vec3 theUVT,
+                        out vec3 theNorm)
 {
+  vec3 aToTrg = thePnt0 - theRay.Origin;
+
   vec3 aEdge0 = thePnt1 - thePnt0;
   vec3 aEdge1 = thePnt0 - thePnt2;
 
   theNorm = cross (aEdge1, aEdge0);
 
-  vec3 aEdge2 = (1.0f / dot (theNorm, theRay.Direct)) * (thePnt0 - theRay.Origin);
+  vec3 theVect = cross (theRay.Direct, aToTrg);
 
-  float aTime = dot (theNorm, aEdge2);
+  theUVT = vec3 (dot (theNorm, aToTrg),
+                 dot (theVect, aEdge1),
+                 dot (theVect, aEdge0)) * (1.f / dot (theNorm, theRay.Direct));
 
-  vec3 theVec = cross (theRay.Direct, aEdge2);
+  theUVT.x = any (lessThan (theUVT, ZERO)) || (theUVT.y + theUVT.z) > 1.f ? MAXFLOAT : theUVT.x;
+}
 
-  theUV.x = dot (theVec, aEdge1);
-  theUV.y = dot (theVec, aEdge0);
+#define EMPTY_ROOT ivec4(0)
 
-  return bool (int(aTime >= 0.0f) &
-               int(theUV.x >= 0.0f) &
-               int(theUV.y >= 0.0f) &
-               int(theUV.x + theUV.y <= 1.0f)) ? aTime : MAXFLOAT;
-}
+//! Utility structure containing information about
+//! currently traversing sub-tree of scene's BVH.
+struct SSubTree
+{
+  //! Transformed ray.
+  SRay  TrsfRay;
 
-//! Identifies the absence of intersection.
-#define INALID_HIT ivec4 (-1)
+  //! Inversed ray direction.
+  vec3  Inverse;
 
-//! Global stack shared between traversal functions.
-int Stack[STACK_SIZE];
+  //! Parameters of sub-root node.
+  ivec4 SubData;
+};
 
 #define MATERIAL_AMBN(index) (18 * index + 0)
 #define MATERIAL_DIFF(index) (18 * index + 1)
@@ -366,24 +372,43 @@ int Stack[STACK_SIZE];
 #define MATERIAL_TRS2(index) (18 * index + 8)
 #define MATERIAL_TRS3(index) (18 * index + 9)
 
-struct SSubTree
-{
-  //! Transformed ray.
-  SRay  TrsfRay;
-
-  //! Inversed ray direction.
-  vec3  Inverse;
-
-  //! Parameters of sub-root node.
-  ivec4 SubData;
-};
-
 #define TRS_OFFSET(treelet) treelet.SubData.x
 #define BVH_OFFSET(treelet) treelet.SubData.y
 #define VRT_OFFSET(treelet) treelet.SubData.z
 #define TRG_OFFSET(treelet) treelet.SubData.w
 
-#define EMPTY_ROOT ivec4(0)
+//! Identifies the absence of intersection.
+#define INALID_HIT ivec4 (-1)
+
+//! Global stack shared between traversal functions.
+int Stack[STACK_SIZE];
+
+// =======================================================================
+// function : pop
+// purpose  :
+// =======================================================================
+int pop (inout int theHead)
+{
+  int aData = Stack[theHead];
+
+  int aMask = aData >> 26;
+  int aNode = aMask & 0x3;
+
+  aMask >>= 2;
+
+  if ((aMask & 0x3) == aNode)
+  {
+    --theHead;
+  }
+  else
+  {
+    aMask |= (aMask << 2) & 0x30;
+
+    Stack[theHead] = (aData & 0x03FFFFFF) | (aMask << 26);
+  }
+
+  return (aData & 0x03FFFFFF) + aNode;
+}
 
 // =======================================================================
 // function : SceneNearestHit
@@ -399,55 +424,90 @@ ivec4 SceneNearestHit (in SRay theRay, in vec3 theInverse, inout SIntersect theH
 
   SSubTree aSubTree = SSubTree (theRay, theInverse, EMPTY_ROOT);
 
-  for (bool toContinue = true; toContinue;)
+  for (bool toContinue = true; toContinue; /* none */)
   {
     ivec4 aData = texelFetch (uSceneNodeInfoTexture, aNode);
 
     if (aData.x == 0) // if inner node
     {
-      float aTimeOut;
-      float aTimeLft;
-      float aTimeRgh;
-
       aData.y += BVH_OFFSET (aSubTree);
-      aData.z += BVH_OFFSET (aSubTree);
 
-      vec3 aNodeMinLft = texelFetch (uSceneMinPointTexture, aData.y).xyz;
-      vec3 aNodeMinRgh = texelFetch (uSceneMinPointTexture, aData.z).xyz;
-      vec3 aNodeMaxLft = texelFetch (uSceneMaxPointTexture, aData.y).xyz;
-      vec3 aNodeMaxRgh = texelFetch (uSceneMaxPointTexture, aData.z).xyz;
+      vec4 aHitTimes = vec4 (MAXFLOAT,
+                             MAXFLOAT,
+                             MAXFLOAT,
+                             MAXFLOAT);
+
+      vec3 aRayOriginInverse = -aSubTree.TrsfRay.Origin * aSubTree.Inverse;
+
+      vec3 aNodeMin0 = texelFetch (uSceneMinPointTexture, aData.y +                0).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMin1 = texelFetch (uSceneMinPointTexture, aData.y +                1).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMin2 = texelFetch (uSceneMinPointTexture, aData.y + min (2, aData.z)).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMin3 = texelFetch (uSceneMinPointTexture, aData.y + min (3, aData.z)).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMax0 = texelFetch (uSceneMaxPointTexture, aData.y +                0).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMax1 = texelFetch (uSceneMaxPointTexture, aData.y +                1).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMax2 = texelFetch (uSceneMaxPointTexture, aData.y + min (2, aData.z)).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMax3 = texelFetch (uSceneMaxPointTexture, aData.y + min (3, aData.z)).xyz * aSubTree.Inverse + aRayOriginInverse;
+
+      vec3 aTimeMax = max (aNodeMin0, aNodeMax0);
+      vec3 aTimeMin = min (aNodeMin0, aNodeMax0);
 
-      vec3 aTime0 = (aNodeMinLft - aSubTree.TrsfRay.Origin) * aSubTree.Inverse;
-      vec3 aTime1 = (aNodeMaxLft - aSubTree.TrsfRay.Origin) * aSubTree.Inverse;
+      float aTimeLeave = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
+      float aTimeEnter = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
 
-      vec3 aTimeMax = max (aTime0, aTime1);
-      vec3 aTimeMin = min (aTime0, aTime1);
+      aHitTimes.x = mix (MAXFLOAT, aTimeEnter,
+        aTimeEnter <= aTimeLeave && aTimeEnter <= theHit.Time && aTimeLeave >= 0.f);
 
-      aTime0 = (aNodeMinRgh - aSubTree.TrsfRay.Origin) * aSubTree.Inverse;
-      aTime1 = (aNodeMaxRgh - aSubTree.TrsfRay.Origin) * aSubTree.Inverse;
+      aTimeMax = max (aNodeMin1, aNodeMax1);
+      aTimeMin = min (aNodeMin1, aNodeMax1);
 
-      aTimeOut = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
-      aTimeLft = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
+      aTimeLeave = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
+      aTimeEnter = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
 
-      int aHitLft = int(aTimeLft <= aTimeOut) & int(aTimeOut >= 0.0f) & int(aTimeLft <= theHit.Time);
+      aHitTimes.y = mix (MAXFLOAT, aTimeEnter,
+        aTimeEnter <= aTimeLeave && aTimeEnter <= theHit.Time && aTimeLeave >= 0.f);
 
-      aTimeMax = max (aTime0, aTime1);
-      aTimeMin = min (aTime0, aTime1);
+      aTimeMax = max (aNodeMin2, aNodeMax2);
+      aTimeMin = min (aNodeMin2, aNodeMax2);
 
-      aTimeOut = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
-      aTimeRgh = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
+      aTimeLeave = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
+      aTimeEnter = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
 
-      int aHitRgh = int(aTimeRgh <= aTimeOut) & int(aTimeOut >= 0.0f) & int(aTimeRgh <= theHit.Time);
+      aHitTimes.z = mix (MAXFLOAT, aTimeEnter,
+        aTimeEnter <= aTimeLeave && aTimeEnter <= theHit.Time && aTimeLeave >= 0.f && aData.z > 1);
 
-      aNode = (aHitLft != 0) ? aData.y : aData.z;
+      aTimeMax = max (aNodeMin3, aNodeMax3);
+      aTimeMin = min (aNodeMin3, aNodeMax3);
 
-      if (aHitLft + aHitRgh == 2) // hit both children
+      aTimeLeave = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
+      aTimeEnter = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
+
+      aHitTimes.w = mix (MAXFLOAT, aTimeEnter,
+        aTimeEnter <= aTimeLeave && aTimeEnter <= theHit.Time && aTimeLeave >= 0.f && aData.z > 2);
+
+      ivec4 aChildren = ivec4 (0, 1, 2, 3);
+
+      aChildren.xy = aHitTimes.y < aHitTimes.x ? aChildren.yx : aChildren.xy;
+      aHitTimes.xy = aHitTimes.y < aHitTimes.x ? aHitTimes.yx : aHitTimes.xy;
+      aChildren.zw = aHitTimes.w < aHitTimes.z ? aChildren.wz : aChildren.zw;
+      aHitTimes.zw = aHitTimes.w < aHitTimes.z ? aHitTimes.wz : aHitTimes.zw;
+      aChildren.xz = aHitTimes.z < aHitTimes.x ? aChildren.zx : aChildren.xz;
+      aHitTimes.xz = aHitTimes.z < aHitTimes.x ? aHitTimes.zx : aHitTimes.xz;
+      aChildren.yw = aHitTimes.w < aHitTimes.y ? aChildren.wy : aChildren.yw;
+      aHitTimes.yw = aHitTimes.w < aHitTimes.y ? aHitTimes.wy : aHitTimes.yw;
+      aChildren.yz = aHitTimes.z < aHitTimes.y ? aChildren.zy : aChildren.yz;
+      aHitTimes.yz = aHitTimes.z < aHitTimes.y ? aHitTimes.zy : aHitTimes.yz;
+
+      if (aHitTimes.x != MAXFLOAT)
       {
-        aNode = (aTimeLft < aTimeRgh) ? aData.y : aData.z;
+        int aHitMask = (aHitTimes.w != MAXFLOAT ? aChildren.w : aChildren.z) << 2
+                     | (aHitTimes.z != MAXFLOAT ? aChildren.z : aChildren.y);
+
+        if (aHitTimes.y != MAXFLOAT)
+          Stack[++aHead] = aData.y | (aHitMask << 2 | aChildren.y) << 26;
 
-        Stack[++aHead] = (aTimeLft < aTimeRgh) ? aData.z : aData.y;
+        aNode = aData.y + aChildren.x;
       }
-      else if (aHitLft == aHitRgh) // no hit
+      else
       {
         toContinue = (aHead >= 0);
 
@@ -456,13 +516,14 @@ ivec4 SceneNearestHit (in SRay theRay, in vec3 theInverse, inout SIntersect theH
           aStop = -1; aSubTree = SSubTree (theRay, theInverse, EMPTY_ROOT);
         }
 
-        aNode = Stack[abs (aHead)]; --aHead;
+        if (aHead >= 0)
+          aNode = pop (aHead);
       }
     }
-    else if (aData.x < 0) // leaf node (containg triangles)
+    else if (aData.x < 0) // leaf node (contains triangles)
     {
       vec3 aNormal;
-      vec2 aParams;
+      vec3 aTimeUV;
 
       for (int anIdx = aData.y; anIdx <= aData.z; ++anIdx)
       {
@@ -472,16 +533,15 @@ ivec4 SceneNearestHit (in SRay theRay, in vec3 theInverse, inout SIntersect theH
         vec3 aPoint1 = texelFetch (uGeometryVertexTexture, aTriangle.y += VRT_OFFSET (aSubTree)).xyz;
         vec3 aPoint2 = texelFetch (uGeometryVertexTexture, aTriangle.z += VRT_OFFSET (aSubTree)).xyz;
 
-        float aTime = IntersectTriangle (aSubTree.TrsfRay,
-          aPoint0, aPoint1, aPoint2, aParams, aNormal);
+        IntersectTriangle (aSubTree.TrsfRay, aPoint0, aPoint1, aPoint2, aTimeUV, aNormal);
 
-        if (aTime < theHit.Time)
+        if (aTimeUV.x < theHit.Time)
         {
           aTriIndex = aTriangle;
 
           theTrsfId = TRS_OFFSET (aSubTree);
 
-          theHit = SIntersect (aTime, aParams, aNormal);
+          theHit = SIntersect (aTimeUV.x, aTimeUV.yz, aNormal);
         }
       }
 
@@ -492,7 +552,8 @@ ivec4 SceneNearestHit (in SRay theRay, in vec3 theInverse, inout SIntersect theH
         aStop = -1; aSubTree = SSubTree (theRay, theInverse, EMPTY_ROOT);
       }
 
-      aNode = Stack[abs (aHead)]; --aHead;
+      if (aHead >= 0)
+        aNode = pop (aHead);
     }
     else if (aData.x > 0) // switch node
     {
@@ -540,55 +601,90 @@ float SceneAnyHit (in SRay theRay, in vec3 theInverse, in float theDistance)
 
   SSubTree aSubTree = SSubTree (theRay, theInverse, EMPTY_ROOT);
 
-  for (bool toContinue = true; toContinue;)
+  for (bool toContinue = true; toContinue; /* none */)
   {
     ivec4 aData = texelFetch (uSceneNodeInfoTexture, aNode);
 
     if (aData.x == 0) // if inner node
     {
-      float aTimeOut;
-      float aTimeLft;
-      float aTimeRgh;
-
       aData.y += BVH_OFFSET (aSubTree);
-      aData.z += BVH_OFFSET (aSubTree);
 
-      vec3 aNodeMinLft = texelFetch (uSceneMinPointTexture, aData.y).xyz;
-      vec3 aNodeMinRgh = texelFetch (uSceneMinPointTexture, aData.z).xyz;
-      vec3 aNodeMaxLft = texelFetch (uSceneMaxPointTexture, aData.y).xyz;
-      vec3 aNodeMaxRgh = texelFetch (uSceneMaxPointTexture, aData.z).xyz;
+      vec4 aHitTimes = vec4 (MAXFLOAT,
+                             MAXFLOAT,
+                             MAXFLOAT,
+                             MAXFLOAT);
+
+      vec3 aRayOriginInverse = -aSubTree.TrsfRay.Origin * aSubTree.Inverse;
+
+      vec3 aNodeMin0 = texelFetch (uSceneMinPointTexture, aData.y +                0).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMin1 = texelFetch (uSceneMinPointTexture, aData.y +                1).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMin2 = texelFetch (uSceneMinPointTexture, aData.y + min (2, aData.z)).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMin3 = texelFetch (uSceneMinPointTexture, aData.y + min (3, aData.z)).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMax0 = texelFetch (uSceneMaxPointTexture, aData.y +                0).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMax1 = texelFetch (uSceneMaxPointTexture, aData.y +                1).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMax2 = texelFetch (uSceneMaxPointTexture, aData.y + min (2, aData.z)).xyz * aSubTree.Inverse + aRayOriginInverse;
+      vec3 aNodeMax3 = texelFetch (uSceneMaxPointTexture, aData.y + min (3, aData.z)).xyz * aSubTree.Inverse + aRayOriginInverse;
 
-      vec3 aTime0 = (aNodeMinLft - aSubTree.TrsfRay.Origin) * aSubTree.Inverse;
-      vec3 aTime1 = (aNodeMaxLft - aSubTree.TrsfRay.Origin) * aSubTree.Inverse;
+      vec3 aTimeMax = max (aNodeMin0, aNodeMax0);
+      vec3 aTimeMin = min (aNodeMin0, aNodeMax0);
 
-      vec3 aTimeMax = max (aTime0, aTime1);
-      vec3 aTimeMin = min (aTime0, aTime1);
+      float aTimeLeave = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
+      float aTimeEnter = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
 
-      aTime0 = (aNodeMinRgh - aSubTree.TrsfRay.Origin) * aSubTree.Inverse;
-      aTime1 = (aNodeMaxRgh - aSubTree.TrsfRay.Origin) * aSubTree.Inverse;
+      aHitTimes.x = mix (MAXFLOAT, aTimeEnter,
+        aTimeEnter <= aTimeLeave && aTimeEnter <= theDistance && aTimeLeave >= 0.f);
 
-      aTimeOut = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
-      aTimeLft = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
+      aTimeMax = max (aNodeMin1, aNodeMax1);
+      aTimeMin = min (aNodeMin1, aNodeMax1);
 
-      int aHitLft = int(aTimeLft <= aTimeOut) & int(aTimeOut >= 0.0f) & int(aTimeLft <= theDistance);
+      aTimeLeave = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
+      aTimeEnter = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
 
-      aTimeMax = max (aTime0, aTime1);
-      aTimeMin = min (aTime0, aTime1);
+      aHitTimes.y = mix (MAXFLOAT, aTimeEnter,
+        aTimeEnter <= aTimeLeave && aTimeEnter <= theDistance && aTimeLeave >= 0.f);
 
-      aTimeOut = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
-      aTimeRgh = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
+      aTimeMax = max (aNodeMin2, aNodeMax2);
+      aTimeMin = min (aNodeMin2, aNodeMax2);
 
-      int aHitRgh = int(aTimeRgh <= aTimeOut) & int(aTimeOut >= 0.0f) & int(aTimeRgh <= theDistance);
+      aTimeLeave = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
+      aTimeEnter = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
 
-      aNode = (aHitLft != 0) ? aData.y : aData.z;
+      aHitTimes.z = mix (MAXFLOAT, aTimeEnter,
+        aTimeEnter <= aTimeLeave && aTimeEnter <= theDistance && aTimeLeave >= 0.f && aData.z > 1);
 
-      if (aHitLft + aHitRgh == 2) // hit both children
+      aTimeMax = max (aNodeMin3, aNodeMax3);
+      aTimeMin = min (aNodeMin3, aNodeMax3);
+
+      aTimeLeave = min (aTimeMax.x, min (aTimeMax.y, aTimeMax.z));
+      aTimeEnter = max (aTimeMin.x, max (aTimeMin.y, aTimeMin.z));
+
+      aHitTimes.w = mix (MAXFLOAT, aTimeEnter,
+        aTimeEnter <= aTimeLeave && aTimeEnter <= theDistance && aTimeLeave >= 0.f && aData.z > 2);
+
+      ivec4 aChildren = ivec4 (0, 1, 2, 3);
+
+      aChildren.xy = aHitTimes.y < aHitTimes.x ? aChildren.yx : aChildren.xy;
+      aHitTimes.xy = aHitTimes.y < aHitTimes.x ? aHitTimes.yx : aHitTimes.xy;
+      aChildren.zw = aHitTimes.w < aHitTimes.z ? aChildren.wz : aChildren.zw;
+      aHitTimes.zw = aHitTimes.w < aHitTimes.z ? aHitTimes.wz : aHitTimes.zw;
+      aChildren.xz = aHitTimes.z < aHitTimes.x ? aChildren.zx : aChildren.xz;
+      aHitTimes.xz = aHitTimes.z < aHitTimes.x ? aHitTimes.zx : aHitTimes.xz;
+      aChildren.yw = aHitTimes.w < aHitTimes.y ? aChildren.wy : aChildren.yw;
+      aHitTimes.yw = aHitTimes.w < aHitTimes.y ? aHitTimes.wy : aHitTimes.yw;
+      aChildren.yz = aHitTimes.z < aHitTimes.y ? aChildren.zy : aChildren.yz;
+      aHitTimes.yz = aHitTimes.z < aHitTimes.y ? aHitTimes.zy : aHitTimes.yz;
+
+      if (aHitTimes.x != MAXFLOAT)
       {
-        aNode = (aTimeLft < aTimeRgh) ? aData.y : aData.z;
+        int aHitMask = (aHitTimes.w != MAXFLOAT ? aChildren.w : aChildren.z) << 2
+                     | (aHitTimes.z != MAXFLOAT ? aChildren.z : aChildren.y);
+
+        if (aHitTimes.y != MAXFLOAT)
+          Stack[++aHead] = aData.y | (aHitMask << 2 | aChildren.y) << 26;
 
-        Stack[++aHead] = (aTimeLft < aTimeRgh) ? aData.z : aData.y;
+        aNode = aData.y + aChildren.x;
       }
-      else if (aHitLft == aHitRgh) // no hit
+      else
       {
         toContinue = (aHead >= 0);
 
@@ -597,13 +693,14 @@ float SceneAnyHit (in SRay theRay, in vec3 theInverse, in float theDistance)
           aStop = -1; aSubTree = SSubTree (theRay, theInverse, EMPTY_ROOT);
         }
 
-        aNode = Stack[abs (aHead)]; --aHead;
+        if (aHead >= 0)
+          aNode = pop (aHead);
       }
     }
     else if (aData.x < 0) // leaf node
     {
       vec3 aNormal;
-      vec2 aParams;
+      vec3 aTimeUV;
 
       for (int anIdx = aData.y; anIdx <= aData.z; ++anIdx)
       {
@@ -613,30 +710,30 @@ float SceneAnyHit (in SRay theRay, in vec3 theInverse, in float theDistance)
         vec3 aPoint1 = texelFetch (uGeometryVertexTexture, aTriangle.y += VRT_OFFSET (aSubTree)).xyz;
         vec3 aPoint2 = texelFetch (uGeometryVertexTexture, aTriangle.z += VRT_OFFSET (aSubTree)).xyz;
 
-        float aTime = IntersectTriangle (aSubTree.TrsfRay,
-          aPoint0, aPoint1, aPoint2, aParams, aNormal);
+        IntersectTriangle (aSubTree.TrsfRay, aPoint0, aPoint1, aPoint2, aTimeUV, aNormal);
 
 #ifdef TRANSPARENT_SHADOWS
-        if (aTime < theDistance)
+        if (aTimeUV.x < theDistance)
         {
           aFactor *= 1.f - texelFetch (uRaytraceMaterialTexture, MATERIAL_TRAN (aTriangle.w)).x;
         }
 #else
-        if (aTime < theDistance)
+        if (aTimeUV.x < theDistance)
         {
           aFactor = 0.f;
         }
 #endif
       }
 
-      toContinue = (aHead >= 0) && (aFactor > 0.1f);
+      toContinue = (aHead >= 0);
 
       if (aHead == aStop) // go to top-level BVH
       {
         aStop = -1; aSubTree = SSubTree (theRay, theInverse, EMPTY_ROOT);
       }
 
-      aNode = Stack[abs (aHead)]; --aHead;
+      if (aHead >= 0)
+        aNode = pop (aHead);
     }
     else if (aData.x > 0) // switch node
     {
index 25c9bbe..d75e962 100644 (file)
@@ -26,7 +26,7 @@ void main (void)
 #else
   ivec2 aWinSize = textureSize (uAccumTexture, 0);
 
-  SeedRand (uFrameRndSeed, aWinSize.x, uBlockedRngEnabled == 0 ? 1 : 16);
+  SeedRand (uFrameRndSeed, aWinSize.x, uBlockedRngEnabled == 0 ? 1 : 8);
 
   SRay aRay = GenerateRay (vPixel +
     vec2 (RandFloat() + 1.f, RandFloat() + 1.f) / vec2 (aWinSize));