From 2b5a58a33cf42ab3d995e63dde8c1ff7278cb4d0 Mon Sep 17 00:00:00 2001 From: osa Date: Fri, 22 Nov 2019 16:02:02 +0300 Subject: [PATCH] 0031186: Foundation Classes - add additional useful methods to BVH_Box. Add Transform() and Transformed() methods by Mat4 for BVH_Box (only for 3D dimension). Add PointBoxProjection() method to project point to box and RayBoxIntersection() method to compute hit time of ray-box intersection to BVH_Tools. Add BVH_Ray class to define ray object. --- src/BVH/BVH_Box.hxx | 75 ++++++++++++++++++++++++++- src/BVH/BVH_Ray.hxx | 39 ++++++++++++++ src/BVH/BVH_Tools.hxx | 118 ++++++++++++++++++++++++++++++++++++++++++ src/BVH/FILES | 1 + 4 files changed, 232 insertions(+), 1 deletion(-) create mode 100644 src/BVH/BVH_Ray.hxx diff --git a/src/BVH/BVH_Box.hxx b/src/BVH/BVH_Box.hxx index a5388232a1..52ab9bb8a2 100644 --- a/src/BVH/BVH_Box.hxx +++ b/src/BVH/BVH_Box.hxx @@ -23,11 +23,84 @@ #include +//! Base class for BVH_Box (CRTP idiom is used). +//! @tparam T Numeric data type +//! @tparam N Vector dimension +//! @tparam TheDerivedBox Template of derived class that defined axis aligned bounding box. +template class TheDerivedBox> +class BVH_BaseBox {}; + +// forward declaration +template class BVH_Box; + +//! Partial template specialization for BVH_Box when N = 3. +template +class BVH_BaseBox +{ +public: + + //! Transforms this box with given transformation. + void Transform (const NCollection_Mat4& theTransform) + { + if (theTransform.IsIdentity()) + { + return; + } + + BVH_Box *aThis = static_cast*>(this); + if (!aThis->IsValid()) + { + return; + } + + BVH_Box aBox = Transformed (theTransform); + + aThis->CornerMin() = aBox.CornerMin(); + aThis->CornerMax() = aBox.CornerMax(); + } + + //! Returns a box which is the result of applying the + //! given transformation to this box. + BVH_Box Transformed (const NCollection_Mat4& theTransform) const + { + BVH_Box aResultBox; + + if (theTransform.IsIdentity()) + { + return aResultBox; + } + + const BVH_Box *aThis = static_cast*>(this); + if (!aThis->IsValid()) + { + return aResultBox; + } + + for (size_t aX = 0; aX <= 1; ++aX) + { + for (size_t aY = 0; aY <= 1; ++aY) + { + for (size_t aZ = 0; aZ <= 1; ++aZ) + { + typename BVH::VectorType::Type aPnt = + theTransform * typename BVH::VectorType::Type (aX ? aThis->CornerMax().x() : aThis->CornerMin().x(), + aY ? aThis->CornerMax().y() : aThis->CornerMin().y(), + aZ ? aThis->CornerMax().z() : aThis->CornerMin().z(), + static_cast (1.0)); + + aResultBox.Add (aPnt.xyz()); + } + } + } + return aResultBox; + } +}; + //! Defines axis aligned bounding box (AABB) based on BVH vectors. //! \tparam T Numeric data type //! \tparam N Vector dimension template -class BVH_Box +class BVH_Box : public BVH_BaseBox { public: diff --git a/src/BVH/BVH_Ray.hxx b/src/BVH/BVH_Ray.hxx new file mode 100644 index 0000000000..9c4600d0b0 --- /dev/null +++ b/src/BVH/BVH_Ray.hxx @@ -0,0 +1,39 @@ +// Created by: Olga Suryaninova +// Created on: 2019-11-25 +// Copyright (c) 2019 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_Ray_Header +#define _BVH_Ray_Header + +//! Describes a ray based on BVH vectors. +template +class BVH_Ray +{ +public: + + typedef typename BVH::VectorType::Type BVH_VecNt; + +public: + + BVH_VecNt Origin; + BVH_VecNt Direct; + +public: + + BVH_Ray (const BVH_VecNt& theOrigin, + const BVH_VecNt& theDirect) : Origin (theOrigin), + Direct (theDirect) { } +}; + +#endif // _BVH_Ray_Header diff --git a/src/BVH/BVH_Tools.hxx b/src/BVH/BVH_Tools.hxx index 24d16b58a8..ad5b6099cc 100644 --- a/src/BVH/BVH_Tools.hxx +++ b/src/BVH/BVH_Tools.hxx @@ -17,6 +17,7 @@ #define _BVH_Tools_Header #include +#include #include //! Defines a set of static methods operating with points and bounding boxes. @@ -35,6 +36,10 @@ public: //! @name Box-Box Square distance static T BoxBoxSquareDistance (const BVH_Box& theBox1, const BVH_Box& theBox2) { + if (!theBox1.IsValid() || !theBox2.IsValid()) + { + return static_cast(0); + } return BoxBoxSquareDistance (theBox1.CornerMin(), theBox1.CornerMax(), theBox2.CornerMin(), theBox2.CornerMax()); } @@ -60,6 +65,10 @@ public: //! @name Point-Box Square distance static T PointBoxSquareDistance (const BVH_VecNt& thePoint, const BVH_Box& theBox) { + if (!theBox.IsValid()) + { + return static_cast(0); + } return PointBoxSquareDistance (thePoint, theBox.CornerMin(), theBox.CornerMax()); @@ -79,6 +88,29 @@ public: //! @name Point-Box Square distance return aDist; } +public: //! @name Point-Box projection + + //! Computes projection of point on bounding box + static BVH_VecNt PointBoxProjection (const BVH_VecNt& thePoint, + const BVH_Box& theBox) + { + if (!theBox.IsValid()) + { + return thePoint; + } + return PointBoxProjection (thePoint, + theBox.CornerMin(), + theBox.CornerMax()); + } + + //! Computes projection of point on bounding box + static BVH_VecNt PointBoxProjection (const BVH_VecNt& thePoint, + const BVH_VecNt& theCMin, + const BVH_VecNt& theCMax) + { + return thePoint.cwiseMax (theCMin).cwiseMin (theCMax); + } + public: //! @name Point-Triangle Square distance //! Computes square distance between point and triangle @@ -160,6 +192,92 @@ public: //! @name Point-Triangle Square distance return (aDirect.Dot(aDirect)); } +public: //! @name Ray-Box Intersection + + //! Computes hit time of ray-box intersection + static Standard_Boolean RayBoxIntersection (const BVH_Ray& theRay, + const BVH_Box& theBox, + T& theTimeEnter, + T& theTimeLeave) + { + if (!theBox.IsValid()) + { + return Standard_False; + } + return RayBoxIntersection (theRay, theBox.CornerMin(), theBox.CornerMax(), theTimeEnter, theTimeLeave); + } + + //! Computes hit time of ray-box intersection + static Standard_Boolean RayBoxIntersection (const BVH_Ray& theRay, + const BVH_VecNt& theBoxCMin, + const BVH_VecNt& theBoxCMax, + T& theTimeEnter, + T& theTimeLeave) + { + return RayBoxIntersection (theRay.Origin, theRay.Direct, + theBoxCMin, theBoxCMax, theTimeEnter, theTimeLeave); + } + + //! Computes hit time of ray-box intersection + static Standard_Boolean RayBoxIntersection (const BVH_VecNt& theRayOrigin, + const BVH_VecNt& theRayDirection, + const BVH_Box& theBox, + T& theTimeEnter, + T& theTimeLeave) + { + if (!theBox.IsValid()) + { + return Standard_False; + } + return RayBoxIntersection (theRayOrigin, theRayDirection, + theBox.CornerMin(), theBox.CornerMax(), + theTimeEnter, theTimeLeave); + } + + //! Computes hit time of ray-box intersection + static Standard_Boolean RayBoxIntersection (const BVH_VecNt& theRayOrigin, + const BVH_VecNt& theRayDirection, + const BVH_VecNt& theBoxCMin, + const BVH_VecNt& theBoxCMax, + T& theTimeEnter, + T& theTimeLeave) + { + BVH_VecNt aNodeMin, aNodeMax; + for (int i = 0; i < N; ++i) + { + if (theRayDirection[i] == 0) + { + aNodeMin[i] = (theBoxCMin[i] - theRayOrigin[i]) < 0 ? + (std::numeric_limits::min)() : (std::numeric_limits::max)(); + aNodeMax[i] = (theBoxCMax[i] - theRayOrigin[i]) < 0 ? + (std::numeric_limits::min)() : (std::numeric_limits::max)(); + } + else + { + aNodeMin[i] = (theBoxCMin[i] - theRayOrigin[i]) / theRayDirection[i]; + aNodeMax[i] = (theBoxCMax[i] - theRayOrigin[i]) / theRayDirection[i]; + } + } + + BVH_VecNt aTimeMin, aTimeMax; + for (int i = 0; i < N; ++i) + { + aTimeMin[i] = Min (aNodeMin[i], aNodeMax[i]); + aTimeMax[i] = Max (aNodeMin[i], aNodeMax[i]); + } + + T aTimeEnter = Max (aTimeMin[0], Max (aTimeMin[1], aTimeMin[2])); + T aTimeLeave = Min (aTimeMax[0], Min (aTimeMax[1], aTimeMax[2])); + + Standard_Boolean hasIntersection = aTimeEnter < aTimeLeave && aTimeLeave > 0; + if (hasIntersection) + { + theTimeEnter = aTimeEnter; + theTimeLeave = aTimeLeave; + } + + return hasIntersection; + } }; #endif \ No newline at end of file diff --git a/src/BVH/FILES b/src/BVH/FILES index 90535a2098..dd7b34e837 100644 --- a/src/BVH/FILES +++ b/src/BVH/FILES @@ -22,6 +22,7 @@ BVH_PrimitiveSet3d.hxx BVH_Properties.cxx BVH_Properties.hxx BVH_QueueBuilder.hxx +BVH_Ray.hxx BVH_Set.hxx BVH_Sorter.hxx BVH_QuickSorter.hxx -- 2.20.1