From f2474958ef13011d06629ba30a808dd72697eab6 Mon Sep 17 00:00:00 2001 From: dbp Date: Mon, 20 Jun 2016 19:43:44 +0300 Subject: [PATCH] 0027590: Visualization, Ray Tracing - port to quad BVH trees (QBVH) 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%. --- src/BVH/BVH_BinaryTree.hxx | 104 +++++++ src/BVH/BVH_BinaryTree.lxx | 307 ++++++++++++++++++++ src/BVH/BVH_Builder.hxx | 2 +- src/BVH/BVH_DistanceField.lxx | 4 +- src/BVH/BVH_QuadTree.hxx | 39 +++ src/BVH/BVH_QuadTree.lxx | 24 ++ src/BVH/BVH_QueueBuilder.lxx | 3 +- src/BVH/BVH_Tree.hxx | 219 +++++---------- src/BVH/BVH_Tree.lxx | 173 +----------- src/BVH/FILES | 4 + src/OpenGl/OpenGl_Layer.cxx | 4 +- src/OpenGl/OpenGl_SceneGeometry.cxx | 112 +++++--- src/OpenGl/OpenGl_SceneGeometry.hxx | 66 +++-- src/OpenGl/OpenGl_View.hxx | 2 +- src/OpenGl/OpenGl_View_Raytrace.cxx | 62 ++-- src/Select3D/Select3D_SensitiveSet.cxx | 2 +- src/SelectMgr/SelectMgr_ViewerSelector.cxx | 8 +- src/Shaders/RaytraceBase.fs | 311 ++++++++++++++------- src/Shaders/RaytraceRender.fs | 2 +- 19 files changed, 922 insertions(+), 526 deletions(-) create mode 100644 src/BVH/BVH_BinaryTree.hxx create mode 100644 src/BVH/BVH_BinaryTree.lxx create mode 100644 src/BVH/BVH_QuadTree.hxx create mode 100644 src/BVH/BVH_QuadTree.lxx diff --git a/src/BVH/BVH_BinaryTree.hxx b/src/BVH/BVH_BinaryTree.hxx new file mode 100644 index 0000000000..52b898434c --- /dev/null +++ b/src/BVH/BVH_BinaryTree.hxx @@ -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 + +//! Specialization of binary BVH tree. +template +class BVH_Tree : public BVH_TreeBase +{ +public: //! @name custom data types + + typedef typename BVH_TreeBase::BVH_VecNt BVH_VecNt; + +public: //! @name methods for accessing individual nodes + + //! Creates new empty BVH tree. + BVH_Tree() : BVH_TreeBase() { } + + //! 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 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& 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& theAABB, + const int theBegElem, + const int theEndElem); + + //! Adds new inner node to the BVH. + int AddInnerNode (const BVH_Box& 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* CollapseToQuadTree() const; + +}; + +#include + +#endif // _BVH_BinaryTree_Header diff --git a/src/BVH/BVH_BinaryTree.lxx b/src/BVH/BVH_BinaryTree.lxx new file mode 100644 index 0000000000..343288ebc7 --- /dev/null +++ b/src/BVH/BVH_BinaryTree.lxx @@ -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 +#include + +// ======================================================================= +// function : Child +// purpose : Returns index of the K-th child of the given inner node +// ======================================================================= +template template +int& BVH_Tree::Child (const int theNodeIndex) +{ + return BVH::Array::ChangeValue (this->myNodeInfoBuffer, theNodeIndex)[K + 1]; +} + +// ======================================================================= +// function : Child +// purpose : Returns index of the K-th child of the given inner node +// ======================================================================= +template template +int BVH_Tree::Child (const int theNodeIndex) const +{ + return BVH::Array::Value (this->myNodeInfoBuffer, theNodeIndex)[K + 1]; +} + +// ======================================================================= +// function : SetOuter +// purpose : Sets node type to 'outer' +// ======================================================================= +template +void BVH_Tree::SetOuter (const int theNodeIndex) +{ + BVH::Array::ChangeValue (this->myNodeInfoBuffer, theNodeIndex).x() = 1; +} + +// ======================================================================= +// function : SetOuter +// purpose : Sets node type to 'inner' +// ======================================================================= +template +void BVH_Tree::SetInner (const int theNodeIndex) +{ + BVH::Array::ChangeValue (this->myNodeInfoBuffer, theNodeIndex).x() = 0; +} + +// ======================================================================= +// function : Clear +// purpose : Removes all BVH nodes +// ======================================================================= +template +void BVH_Tree::Clear() +{ + this->myDepth = 0; + + BVH::Array::Clear (this->myMinPointBuffer); + BVH::Array::Clear (this->myMaxPointBuffer); + + BVH::Array::Clear (this->myNodeInfoBuffer); +} + +// ======================================================================= +// function : AddLeafNode +// purpose : Adds new leaf node to the BVH +// ======================================================================= +template +int BVH_Tree::AddLeafNode (const int theBegElem, + const int theEndElem) +{ + BVH::Array::Append (this->myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0)); + + return BVH::Array::Size (this->myNodeInfoBuffer) - 1; +} + +// ======================================================================= +// function : AddInnerNode +// purpose : Adds new inner node to the BVH +// ======================================================================= +template +int BVH_Tree::AddInnerNode (const int theLftChild, + const int theRghChild) +{ + BVH::Array::Append (this->myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0)); + + return BVH::Array::Size (this->myNodeInfoBuffer) - 1; +} + +// ======================================================================= +// function : AddLeafNode +// purpose : Adds new leaf node to the BVH +// ======================================================================= +template +int BVH_Tree::AddLeafNode (const BVH_VecNt& theMinPoint, + const BVH_VecNt& theMaxPoint, + const int theBegElem, + const int theEndElem) +{ + BVH::Array::Append (this->myMinPointBuffer, theMinPoint); + BVH::Array::Append (this->myMaxPointBuffer, theMaxPoint); + + BVH::Array::Append (this->myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0)); + + return BVH::Array::Size (this->myNodeInfoBuffer) - 1; +} + +// ======================================================================= +// function : AddInnerNode +// purpose : Adds new inner node to the BVH +// ======================================================================= +template +int BVH_Tree::AddInnerNode (const BVH_VecNt& theMinPoint, + const BVH_VecNt& theMaxPoint, + const int theLftChild, + const int theRghChild) +{ + BVH::Array::Append (this->myMinPointBuffer, theMinPoint); + BVH::Array::Append (this->myMaxPointBuffer, theMaxPoint); + + BVH::Array::Append (this->myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0)); + + return BVH::Array::Size (this->myNodeInfoBuffer) - 1; +} + +// ======================================================================= +// function : AddLeafNode +// purpose : Adds new leaf node to the BVH +// ======================================================================= +template +int BVH_Tree::AddLeafNode (const BVH_Box& 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 +int BVH_Tree::AddInnerNode (const BVH_Box& 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 + void EstimateSAH (const BVH_Tree* theTree, const int theNode, T theProb, T& theSAH) + { + BVH_Box 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 (2.0); + + BVH_Box 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 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 +T BVH_Tree::EstimateSAH() const +{ + T aSAH = static_cast (0.0); + + BVH::EstimateSAH (this, 0, static_cast (1.0), aSAH); + + return aSAH; +} + +// ======================================================================= +// function : Reserve +// purpose : +// ======================================================================= +template +void BVH_Tree::Reserve (const int theNbNodes) +{ + BVH::Array::Reserve (this->myMinPointBuffer, theNbNodes); + BVH::Array::Reserve (this->myMaxPointBuffer, theNbNodes); + BVH::Array::Reserve (this->myNodeInfoBuffer, theNbNodes); +} + +// ======================================================================= +// function : CollapseToQuadTree +// purpose : +// ======================================================================= +template +BVH_Tree* BVH_Tree::CollapseToQuadTree() const +{ + BVH_Tree* aQBVH = new BVH_Tree; + + if (this->Length() == 0) + { + return aQBVH; + } + + std::deque > aQueue (1, std::make_pair (0, 0)); + + for (int aNbNodes = 1; !aQueue.empty();) + { + const std::pair aNode = aQueue.front(); + + BVH::Array::Append (aQBVH->myMinPointBuffer, BVH::Array::Value (this->myMinPointBuffer, std::get<0> (aNode))); + BVH::Array::Append (aQBVH->myMaxPointBuffer, BVH::Array::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 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::Append (aQBVH->myNodeInfoBuffer, aNodeInfo); + + aQueue.pop_front(); // node processing completed + } + + return aQBVH; +} diff --git a/src/BVH/BVH_Builder.hxx b/src/BVH/BVH_Builder.hxx index d42ff32b54..27fbc83e39 100644 --- a/src/BVH/BVH_Builder.hxx +++ b/src/BVH/BVH_Builder.hxx @@ -17,7 +17,7 @@ #define _BVH_Builder_Header #include -#include +#include namespace BVH { diff --git a/src/BVH/BVH_DistanceField.lxx b/src/BVH/BVH_DistanceField.lxx index 9d183a991b..c3678bcecf 100644 --- a/src/BVH/BVH_DistanceField.lxx +++ b/src/BVH/BVH_DistanceField.lxx @@ -311,9 +311,9 @@ namespace BVH { Standard_STATIC_ASSERT (N == 3 || N == 4); - const NCollection_Handle >& aBVH = theGeometry.BVH(); + const BVH_Tree* 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 index 0000000000..e49ede6d32 --- /dev/null +++ b/src/BVH/BVH_QuadTree.hxx @@ -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 + +//! Specialization of quad BVH (QBVH) tree. +template +class BVH_Tree : public BVH_TreeBase +{ +public: //! @name general methods + + //! Creates new empty BVH tree. + BVH_Tree() : BVH_TreeBase() { } + + //! 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 Child (const int theNodeIndex) const; + +}; + +#include + +#endif // _BVH_QuadTree_Header diff --git a/src/BVH/BVH_QuadTree.lxx b/src/BVH/BVH_QuadTree.lxx new file mode 100644 index 0000000000..82adbef034 --- /dev/null +++ b/src/BVH/BVH_QuadTree.lxx @@ -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 template +int BVH_Tree::Child (const int theNodeIndex) const +{ + return BVH::Array::Value (this->myNodeInfoBuffer, theNodeIndex).y() + K; +} diff --git a/src/BVH/BVH_QueueBuilder.lxx b/src/BVH/BVH_QueueBuilder.lxx index dadf482c58..07cc2a84dd 100644 --- a/src/BVH/BVH_QueueBuilder.lxx +++ b/src/BVH/BVH_QueueBuilder.lxx @@ -77,7 +77,8 @@ void BVH_QueueBuilder::AddChildren (BVH_Tree* 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::myLeafNodeSize diff --git a/src/BVH/BVH_Tree.hxx b/src/BVH/BVH_Tree.hxx index 25095a95eb..bf59c635fe 100644 --- a/src/BVH/BVH_Tree.hxx +++ b/src/BVH/BVH_Tree.hxx @@ -13,10 +13,8 @@ // 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 +#ifndef _BVH_TreeBase_Header +#define _BVH_TreeBase_Header #include @@ -31,225 +29,150 @@ template class BVH_Builder; //! such as collision detection, ray-tracing, searching of nearest //! objects, and view frustum culling. template -class BVH_Tree +class BVH_TreeBase { friend class BVH_Builder; -public: +public: //! @name custom data types typedef typename BVH_Box::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::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::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::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::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::Value (myMaxPointBuffer, theNodeIndex); } - //! Returns index of left child of the given inner node. - Standard_Integer& LeftChild (const Standard_Integer theNodeIndex) - { - return BVH::Array::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::Value (myNodeInfoBuffer, theNodeIndex).y(); - } - - //! Returns index of right child of the given inner node. - Standard_Integer& RightChild (const Standard_Integer theNodeIndex) - { - return BVH::Array::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::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::ChangeValue (myNodeInfoBuffer, theNodeIndex).y(); + return BVH::Array::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::Value (myNodeInfoBuffer, theNodeIndex).y(); + return BVH::Array::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::ChangeValue (myNodeInfoBuffer, theNodeIndex).z(); + return BVH::Array::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::Value (myNodeInfoBuffer, theNodeIndex).z(); + return BVH::Array::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::ChangeValue (myNodeInfoBuffer, theNodeIndex).w(); + return BVH::Array::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::Value (myNodeInfoBuffer, theNodeIndex).w(); + return BVH::Array::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::Value (myNodeInfoBuffer, theNodeIndex).x() != 0; + return BVH::Array::Value (myNodeInfoBuffer, theNodeIndex).x() != 0; } - //! Sets node type to 'outer'. - void SetOuter (const Standard_Integer theNodeIndex) - { - BVH::Array::ChangeValue (myNodeInfoBuffer, theNodeIndex).x() = 1; - } - - //! Sets node type to 'inner'. - void SetInner (const Standard_Integer theNodeIndex) - { - BVH::Array::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::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& theAABB, - const Standard_Integer theBegElem, - const Standard_Integer theEndElem); - - //! Adds new inner node to the BVH. - Standard_Integer AddInnerNode (const BVH_Box& 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::Type& MinPointBuffer() { return myMinPointBuffer; } - //! Returns array of node min points. - const typename BVH::ArrayType::Type& MinPointBuffer() const - { - return myMinPointBuffer; - } - - //! Returns array of node max points. + //! Returns array of node maximum points. typename BVH::ArrayType::Type& MaxPointBuffer() { return myMaxPointBuffer; } - //! Returns array of node max points. - const typename BVH::ArrayType::Type& MaxPointBuffer() const + //! Returns array of node minimum points. + const typename BVH::ArrayType::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::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::Type myMinPointBuffer; @@ -257,14 +180,24 @@ protected: //! Array of node maximum points. typename BVH::ArrayType::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 BVH_Tree +{ + // Invalid type }; #include -#endif // _BVH_Tree_Header +#endif // _BVH_TreeBase_Header diff --git a/src/BVH/BVH_Tree.lxx b/src/BVH/BVH_Tree.lxx index 549c6893a1..ec6473db34 100644 --- a/src/BVH/BVH_Tree.lxx +++ b/src/BVH/BVH_Tree.lxx @@ -14,174 +14,11 @@ // commercial license or contractual agreement. // ======================================================================= -// function : Clear -// purpose : +// function : ~BVH_TreeBase +// purpose : Releases resources of BVH tree // ======================================================================= template -void BVH_Tree::Clear() +BVH_TreeBase::~BVH_TreeBase() { - myDepth = 0; - - BVH::Array::Clear (myMinPointBuffer); - BVH::Array::Clear (myMaxPointBuffer); - - BVH::Array::Clear (myNodeInfoBuffer); -} - -// ======================================================================= -// function : AddLeafNode -// purpose : -// ======================================================================= -template -Standard_Integer BVH_Tree::AddLeafNode (const Standard_Integer theBegElem, - const Standard_Integer theEndElem) -{ - BVH::Array::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0)); - - return static_cast (BVH::Array::Size (myNodeInfoBuffer) - 1); -} - -// ======================================================================= -// function : AddInnerNode -// purpose : -// ======================================================================= -template -Standard_Integer BVH_Tree::AddInnerNode (const Standard_Integer theLftChild, - const Standard_Integer theRghChild) -{ - BVH::Array::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0)); - - return static_cast (BVH::Array::Size (myNodeInfoBuffer) - 1); -} - -// ======================================================================= -// function : AddLeafNode -// purpose : -// ======================================================================= -template -Standard_Integer BVH_Tree::AddLeafNode (const BVH_VecNt& theMinPoint, - const BVH_VecNt& theMaxPoint, - const Standard_Integer theBegElem, - const Standard_Integer theEndElem) -{ - BVH::Array::Append (myMinPointBuffer, theMinPoint); - BVH::Array::Append (myMaxPointBuffer, theMaxPoint); - - BVH::Array::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0)); - - return static_cast (BVH::Array::Size (myNodeInfoBuffer) - 1); -} - -// ======================================================================= -// function : AddInnerNode -// purpose : -// ======================================================================= -template -Standard_Integer BVH_Tree::AddInnerNode (const BVH_VecNt& theMinPoint, - const BVH_VecNt& theMaxPoint, - const Standard_Integer theLftChild, - const Standard_Integer theRghChild) -{ - BVH::Array::Append (myMinPointBuffer, theMinPoint); - BVH::Array::Append (myMaxPointBuffer, theMaxPoint); - - BVH::Array::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0)); - - return static_cast (BVH::Array::Size (myNodeInfoBuffer) - 1); -} - -// ======================================================================= -// function : AddLeafNode -// purpose : -// ======================================================================= -template -Standard_Integer BVH_Tree::AddLeafNode (const BVH_Box& theAABB, - const Standard_Integer theBegElem, - const Standard_Integer theEndElem) -{ - return AddLeafNode (theAABB.CornerMin(), - theAABB.CornerMax(), - theBegElem, - theEndElem); -} - -// ======================================================================= -// function : AddInnerNode -// purpose : -// ======================================================================= -template -Standard_Integer BVH_Tree::AddInnerNode (const BVH_Box& 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 - void EstimateSAH (const BVH_Tree* theTree, - const Standard_Integer theNode, - T theProb, - T& theSAH) - { - BVH_Box 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 (2.0); - - BVH_Box 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 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 -T BVH_Tree::EstimateSAH() const -{ - T aSAH = static_cast (0.0); - BVH::EstimateSAH (this, 0, static_cast (1.0), aSAH); - return aSAH; -} - -// ======================================================================= -// function : Reserve -// purpose : -// ======================================================================= -template -void BVH_Tree::Reserve (const Standard_Integer theNbNodes) -{ - BVH::Array::Reserve (myMinPointBuffer, theNbNodes); - BVH::Array::Reserve (myMaxPointBuffer, theNbNodes); - BVH::Array::Reserve (myNodeInfoBuffer, theNbNodes); -} + // +} \ No newline at end of file diff --git a/src/BVH/FILES b/src/BVH/FILES index cb4d59b524..88ff44dca1 100644 --- a/src/BVH/FILES +++ b/src/BVH/FILES @@ -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 diff --git a/src/OpenGl/OpenGl_Layer.cxx b/src/OpenGl/OpenGl_Layer.cxx index 8b420d76d4..a1ec6162e4 100644 --- a/src/OpenGl/OpenGl_Layer.cxx +++ b/src/OpenGl/OpenGl_Layer.cxx @@ -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), diff --git a/src/OpenGl/OpenGl_SceneGeometry.cxx b/src/OpenGl/OpenGl_SceneGeometry.cxx index cbdb7d035a..b3d7de271f 100755 --- a/src/OpenGl/OpenGl_SceneGeometry.cxx +++ b/src/OpenGl/OpenGl_SceneGeometry.cxx @@ -117,6 +117,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 (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 > 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 > 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 (myObjects (anObjectIdx).get()); - OpenGl_TriangleSet* aTriangleSet = dynamic_cast ( - 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 (aTriangleSet->Vertices.size()); + aElementsOffset += static_cast (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 >& 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 >& 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 >& 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 >& 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 (myObjects.ChangeValue ( - aBVH->NodeInfoBuffer().at (theNodeIdx).x() - 1).operator->()); + return dynamic_cast ( + myObjects (aBVH->NodeInfoBuffer().at (theNodeIdx).x() - 1).get()); } // ======================================================================= diff --git a/src/OpenGl/OpenGl_SceneGeometry.hxx b/src/OpenGl/OpenGl_SceneGeometry.hxx index d64bfbf27a..9cde62964a 100755 --- a/src/OpenGl/OpenGl_SceneGeometry.hxx +++ b/src/OpenGl/OpenGl_SceneGeometry.hxx @@ -157,6 +157,9 @@ public: } }; +//! Shared pointer to quad BVH (QBVH) tree. +typedef NCollection_Handle > QuadBvhHandle; + //! Triangulation of single OpenGL primitive array. class OpenGl_TriangleSet : public BVH_Triangulation { @@ -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::Box; - //! Returns AABB of primitive set. BVH_BoxNt Box() const; + //! Returns AABB of the given object. + using BVH_Triangulation::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(), - 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 myTextures; //!< Array of texture maps shared between rendered objects - Handle(OpenGl_Sampler) myTextureSampler; //!< Sampler object providing fixed sampling params for texures - std::vector 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 myTextures; //!< Array of texture maps shared between rendered objects + Handle(OpenGl_Sampler) myTextureSampler; //!< Sampler object providing fixed sampling params for texures + std::vector 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. }; diff --git a/src/OpenGl/OpenGl_View.hxx b/src/OpenGl/OpenGl_View.hxx index 3005cd1190..0b713c0195 100644 --- a/src/OpenGl/OpenGl_View.hxx +++ b/src/OpenGl/OpenGl_View.hxx @@ -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 diff --git a/src/OpenGl/OpenGl_View_Raytrace.cxx b/src/OpenGl/OpenGl_View_Raytrace.cxx index 5b2585c985..37ad4d9347 100644 --- a/src/OpenGl/OpenGl_View_Raytrace.cxx +++ b/src/OpenGl/OpenGl_View_Raytrace.cxx @@ -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 >& 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 (&aTriangleSet->BVH()->NodeInfoBuffer().front())); + reinterpret_cast (&aTriangleSet->QuadBVH()->NodeInfoBuffer().front())); aResult &= mySceneMinPointTexture->SubData (theGlContext, aBVHOffset, aBvhBuffersSize, - reinterpret_cast (&aTriangleSet->BVH()->MinPointBuffer().front())); + reinterpret_cast (&aTriangleSet->QuadBVH()->MinPointBuffer().front())); aResult &= mySceneMaxPointTexture->SubData (theGlContext, aBVHOffset, aBvhBuffersSize, - reinterpret_cast (&aTriangleSet->BVH()->MaxPointBuffer().front())); + reinterpret_cast (&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 ( - myRaytraceGeometry.Objects().ChangeValue (anElemIdx).operator->()); + OpenGl_TriangleSet* aTriangleSet = dynamic_cast (myRaytraceGeometry.Objects()(anElemIdx).get()); - aMemUsed += static_cast ( + aMemTrgUsed += static_cast ( aTriangleSet->Vertices.size() * sizeof (BVH_Vec3f)); - aMemUsed += static_cast ( + aMemTrgUsed += static_cast ( aTriangleSet->Normals.size() * sizeof (BVH_Vec3f)); - aMemUsed += static_cast ( + aMemTrgUsed += static_cast ( aTriangleSet->TexCrds.size() * sizeof (BVH_Vec2f)); - aMemUsed += static_cast ( + aMemTrgUsed += static_cast ( aTriangleSet->Elements.size() * sizeof (BVH_Vec4i)); - aMemUsed += static_cast ( - aTriangleSet->BVH()->NodeInfoBuffer().size() * sizeof (BVH_Vec4i)); - aMemUsed += static_cast ( - aTriangleSet->BVH()->MinPointBuffer().size() * sizeof (BVH_Vec3f)); - aMemUsed += static_cast ( - aTriangleSet->BVH()->MaxPointBuffer().size() * sizeof (BVH_Vec3f)); + aMemBvhUsed += static_cast ( + aTriangleSet->QuadBVH()->NodeInfoBuffer().size() * sizeof (BVH_Vec4i)); + aMemBvhUsed += static_cast ( + aTriangleSet->QuadBVH()->MinPointBuffer().size() * sizeof (BVH_Vec3f)); + aMemBvhUsed += static_cast ( + aTriangleSet->QuadBVH()->MaxPointBuffer().size() * sizeof (BVH_Vec3f)); } - aMemUsed += static_cast ( - myRaytraceGeometry.BVH()->NodeInfoBuffer().size() * sizeof (BVH_Vec4i)); - aMemUsed += static_cast ( - myRaytraceGeometry.BVH()->MinPointBuffer().size() * sizeof (BVH_Vec3f)); - aMemUsed += static_cast ( - myRaytraceGeometry.BVH()->MaxPointBuffer().size() * sizeof (BVH_Vec3f)); + aMemBvhUsed += static_cast ( + myRaytraceGeometry.QuadBVH()->NodeInfoBuffer().size() * sizeof (BVH_Vec4i)); + aMemBvhUsed += static_cast ( + myRaytraceGeometry.QuadBVH()->MinPointBuffer().size() * sizeof (BVH_Vec3f)); + aMemBvhUsed += static_cast ( + 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 diff --git a/src/Select3D/Select3D_SensitiveSet.cxx b/src/Select3D/Select3D_SensitiveSet.cxx index f726c73c82..fabd0238ec 100644 --- a/src/Select3D/Select3D_SensitiveSet.cxx +++ b/src/Select3D/Select3D_SensitiveSet.cxx @@ -49,7 +49,7 @@ void Select3D_SensitiveSet::BVH() Standard_Boolean Select3D_SensitiveSet::Matches (SelectBasics_SelectingVolumeManager& theMgr, SelectBasics_PickResult& thePickResult) { - const NCollection_Handle >& aBVH = myContent->GetBVH(); + const BVH_Tree* aBVH = myContent->GetBVH().get(); thePickResult = SelectBasics_PickResult (RealLast(), RealLast()); diff --git a/src/SelectMgr/SelectMgr_ViewerSelector.cxx b/src/SelectMgr/SelectMgr_ViewerSelector.cxx index ecc735b004..ddf9ba5a2d 100644 --- a/src/SelectMgr/SelectMgr_ViewerSelector.cxx +++ b/src/SelectMgr/SelectMgr_ViewerSelector.cxx @@ -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)); diff --git a/src/Shaders/RaytraceBase.fs b/src/Shaders/RaytraceBase.fs index 23569063a5..e7a3e3df4f 100644 --- a/src/Shaders/RaytraceBase.fs +++ b/src/Shaders/RaytraceBase.fs @@ -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 { diff --git a/src/Shaders/RaytraceRender.fs b/src/Shaders/RaytraceRender.fs index 25c9bbec19..d75e962a78 100644 --- a/src/Shaders/RaytraceRender.fs +++ b/src/Shaders/RaytraceRender.fs @@ -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)); -- 2.20.1