From 9ad4ff93a03daf951ec773b676c47f7c849cc35c Mon Sep 17 00:00:00 2001 From: kgv Date: Sun, 19 Apr 2020 21:42:42 +0300 Subject: [PATCH] 0031511: Point Cloud Rendering, Volume Rendering - reuse Graphic3d_CullingTool Graphic3d_CullingTool::IsCulled() has been extended with theIsInside argument for full inclusion test. Graphic3d_Layer::UpdateCulling() now avoids frustum culling tests for BVH children for parent nodes completely included into frustum. Graphic3d_CullingTool::SetViewVolume() has been extended by optional model-world matrix. --- src/Graphic3d/Graphic3d_Camera.cxx | 5 +- src/Graphic3d/Graphic3d_Camera.hxx | 3 +- src/Graphic3d/Graphic3d_CullingTool.cxx | 22 +++- src/Graphic3d/Graphic3d_CullingTool.hxx | 159 +++++++++++++++--------- src/Graphic3d/Graphic3d_Layer.cxx | 60 +++++++-- 5 files changed, 167 insertions(+), 82 deletions(-) diff --git a/src/Graphic3d/Graphic3d_Camera.cxx b/src/Graphic3d/Graphic3d_Camera.cxx index a251811e33..854ec60cf2 100644 --- a/src/Graphic3d/Graphic3d_Camera.cxx +++ b/src/Graphic3d/Graphic3d_Camera.cxx @@ -1475,7 +1475,8 @@ Standard_EXPORT void NCollection_Lerp::Interpolate (co //function : FrustumPoints //purpose : //======================================================================= -void Graphic3d_Camera::FrustumPoints (NCollection_Array1& thePoints) const +void Graphic3d_Camera::FrustumPoints (NCollection_Array1& thePoints, + const Graphic3d_Mat4d& theModelWorld) const { if (thePoints.Length() != FrustumVerticesNB) { @@ -1483,7 +1484,7 @@ void Graphic3d_Camera::FrustumPoints (NCollection_Array1& thePo } const Graphic3d_Mat4d& aProjectionMat = ProjectionMatrix(); - const Graphic3d_Mat4d& aWorldViewMat = OrientationMatrix(); + const Graphic3d_Mat4d aWorldViewMat = OrientationMatrix() * theModelWorld; Standard_Real nLeft = 0.0, nRight = 0.0, nTop = 0.0, nBottom = 0.0; Standard_Real fLeft = 0.0, fRight = 0.0, fTop = 0.0, fBottom = 0.0; diff --git a/src/Graphic3d/Graphic3d_Camera.hxx b/src/Graphic3d/Graphic3d_Camera.hxx index e2f3fbef0e..f4b52461c4 100644 --- a/src/Graphic3d/Graphic3d_Camera.hxx +++ b/src/Graphic3d/Graphic3d_Camera.hxx @@ -670,7 +670,8 @@ public: //! Fill array of current view frustum corners. //! The size of this array is equal to FrustumVerticesNB. //! The order of vertices is as defined in FrustumVert_* enumeration. - Standard_EXPORT void FrustumPoints (NCollection_Array1& thePoints) const; + Standard_EXPORT void FrustumPoints (NCollection_Array1& thePoints, + const Graphic3d_Mat4d& theModelWorld = Graphic3d_Mat4d()) const; private: diff --git a/src/Graphic3d/Graphic3d_CullingTool.cxx b/src/Graphic3d/Graphic3d_CullingTool.cxx index c2a11be66a..d86007eeb0 100644 --- a/src/Graphic3d/Graphic3d_CullingTool.cxx +++ b/src/Graphic3d/Graphic3d_CullingTool.cxx @@ -34,12 +34,17 @@ Graphic3d_CullingTool::Graphic3d_CullingTool() // ======================================================================= // function : SetViewVolume -// purpose : Retrieves view volume's planes equations and its vertices from projection and world-view matrices. +// purpose : // ======================================================================= -void Graphic3d_CullingTool::SetViewVolume (const Handle(Graphic3d_Camera)& theCamera) +void Graphic3d_CullingTool::SetViewVolume (const Handle(Graphic3d_Camera)& theCamera, + const Graphic3d_Mat4d& theModelWorld) { - if (!myWorldViewProjState.IsChanged (theCamera->WorldViewProjState())) + const bool hasModelTrsf = !theModelWorld.IsIdentity(); + if (!myWorldViewProjState.IsChanged (theCamera->WorldViewProjState()) + && !hasModelTrsf) + { return; + } myIsProjectionParallel = theCamera->IsOrthographic(); const gp_Dir aCamDir = theCamera->Direction(); @@ -50,12 +55,19 @@ void Graphic3d_CullingTool::SetViewVolume (const Handle(Graphic3d_Camera)& theCa myWorldViewProjState = theCamera->WorldViewProjState(); myCamEye.SetValues (theCamera->Eye().X(), theCamera->Eye().Y(), theCamera->Eye().Z()); myCamDir.SetValues (aCamDir.X(), aCamDir.Y(), aCamDir.Z()); + if (hasModelTrsf) + { + Graphic3d_Mat4d aModelInv; + theModelWorld.Inverted (aModelInv); + myCamEye = (aModelInv * Graphic3d_Vec4d (myCamEye, 1.0)).xyz(); + myCamDir = (aModelInv * Graphic3d_Vec4d (myCamDir, 0.0)).xyz(); + } myCamScale = theCamera->IsOrthographic() ? theCamera->Scale() : 2.0 * Tan (theCamera->FOVy() * M_PI / 360.0); // same as theCamera->Scale()/theCamera->Distance() // Compute frustum points - theCamera->FrustumPoints (myClipVerts); + theCamera->FrustumPoints (myClipVerts, theModelWorld); // Compute frustum planes // Vertices go in order: @@ -84,7 +96,7 @@ void Graphic3d_CullingTool::SetViewVolume (const Handle(Graphic3d_Camera)& theCa myClipPlanes[aFaceIdx * 2 + i].Normal = Graphic3d_Vec3d::Cross (aPlanePnts[1] - aPlanePnts[0], aPlanePnts[2] - aPlanePnts[0]).Normalized() * (i == 0 ? -1.f : 1.f); - } + } } } diff --git a/src/Graphic3d/Graphic3d_CullingTool.hxx b/src/Graphic3d/Graphic3d_CullingTool.hxx index f76a72b9a6..ce92e0edb0 100644 --- a/src/Graphic3d/Graphic3d_CullingTool.hxx +++ b/src/Graphic3d/Graphic3d_CullingTool.hxx @@ -59,7 +59,10 @@ public: Standard_EXPORT Graphic3d_CullingTool(); //! Retrieves view volume's planes equations and its vertices from projection and world-view matrices. - Standard_EXPORT void SetViewVolume (const Handle(Graphic3d_Camera)& theCamera); + //! @param theCamera [in] camera definition + //! @param theModelWorld [in] optional object transformation for computing frustum in object local coordinate system + Standard_EXPORT void SetViewVolume (const Handle(Graphic3d_Camera)& theCamera, + const Graphic3d_Mat4d& theModelWorld = Graphic3d_Mat4d()); Standard_EXPORT void SetViewportSize (Standard_Integer theViewportWidth, Standard_Integer theViewportHeight, @@ -78,17 +81,20 @@ public: Standard_EXPORT void CacheClipPtsProjections(); //! Checks whether given AABB should be entirely culled or not. - //! @param theCtx [in] culling properties - //! @param theMinPt [in] maximum point of AABB - //! @param theMaxPt [in] minimum point of AABB - //! @return Standard_True, if AABB is in viewing area, Standard_False otherwise + //! @param theCtx [in] culling properties + //! @param theMinPnt [in] maximum point of AABB + //! @param theMaxPnt [in] minimum point of AABB + //! @param theIsInside [out] flag indicating if AABB is fully inside; initial value should be set to TRUE + //! @return TRUE if AABB is completely outside of view frustum or culled by size/distance; + //! FALSE in case of partial or complete overlap (use theIsInside to distinguish) bool IsCulled (const CullingContext& theCtx, - const Graphic3d_Vec3d& theMinPt, - const Graphic3d_Vec3d& theMaxPt) const + const Graphic3d_Vec3d& theMinPnt, + const Graphic3d_Vec3d& theMaxPnt, + Standard_Boolean* theIsInside = NULL) const { - return isFullOut (theMinPt, theMaxPt) - || isTooDistant(theCtx, theMinPt, theMaxPt) - || isTooSmall (theCtx, theMinPt, theMaxPt); + return IsOutFrustum(theMinPnt, theMaxPnt, theIsInside) + || IsTooDistant(theCtx, theMinPnt, theMaxPnt, theIsInside) + || IsTooSmall (theCtx, theMinPnt, theMaxPnt); } //! Return the camera definition. @@ -122,7 +128,13 @@ public: return myWorldViewProjState; } -protected: + //! Returns camera eye position. + const Graphic3d_Vec3d& CameraEye() const { return myCamEye; } + + //! Returns camera direction. + const Graphic3d_Vec3d& CameraDirection() const { return myCamDir; } + +public: //! Calculates signed distance from plane to point. //! @param theNormal [in] the plane's normal. @@ -131,76 +143,89 @@ protected: const Graphic3d_Vec4d& thePnt); //! Detects if AABB overlaps view volume using separating axis theorem (SAT). - //! @param theMinPt [in] maximum point of AABB. - //! @param theMaxPt [in] minimum point of AABB. - //! @return FALSE, if AABB is in viewing area, TRUE otherwise. - bool isFullOut (const Graphic3d_Vec3d& theMinPt, - const Graphic3d_Vec3d& theMaxPt) const + //! @param theMinPnt [in] maximum point of AABB + //! @param theMaxPnt [in] minimum point of AABB + //! @param theIsInside [out] flag indicating if AABB is fully inside; initial value should be set to TRUE + //! @return TRUE if AABB is completely outside of view frustum; + //! FALSE in case of partial or complete overlap (use theIsInside to distinguish) + //! @sa SelectMgr_Frustum::hasOverlap() + bool IsOutFrustum (const Graphic3d_Vec3d& theMinPnt, + const Graphic3d_Vec3d& theMaxPnt, + Standard_Boolean* theIsInside = NULL) const { // E1 // |_ E0 // / // E2 - - // E0 test (x axis) - if (theMinPt.x() > myMaxOrthoProjectionPts[0] - || theMaxPt.x() < myMinOrthoProjectionPts[0]) - { - return true; - } - - // E1 test (y axis) - if (theMinPt.y() > myMaxOrthoProjectionPts[1] - || theMaxPt.y() < myMinOrthoProjectionPts[1]) + if (theMinPnt[0] > myMaxOrthoProjectionPts[0] // E0 test (x axis) + || theMaxPnt[0] < myMinOrthoProjectionPts[0] + || theMinPnt[1] > myMaxOrthoProjectionPts[1] // E1 test (y axis) + || theMaxPnt[1] < myMinOrthoProjectionPts[1] + || theMinPnt[2] > myMaxOrthoProjectionPts[2] // E2 test (z axis) + || theMaxPnt[2] < myMinOrthoProjectionPts[2]) { return true; } - - // E2 test (z axis) - if (theMinPt.z() > myMaxOrthoProjectionPts[2] - || theMaxPt.z() < myMinOrthoProjectionPts[2]) + if (theIsInside != NULL + && *theIsInside) { - return true; + *theIsInside = theMinPnt[0] >= myMinOrthoProjectionPts[0] // E0 test (x axis) + && theMaxPnt[0] <= myMaxOrthoProjectionPts[0] + && theMinPnt[1] >= myMinOrthoProjectionPts[1] // E1 test (y axis) + && theMaxPnt[1] <= myMaxOrthoProjectionPts[1] + && theMinPnt[1] >= myMinOrthoProjectionPts[2] // E2 test (z axis) + && theMaxPnt[1] <= myMaxOrthoProjectionPts[2]; } const Standard_Integer anIncFactor = myIsProjectionParallel ? 2 : 1; for (Standard_Integer aPlaneIter = 0; aPlaneIter < PlanesNB - 1; aPlaneIter += anIncFactor) { // frustum normals - const Graphic3d_Vec3d anAxis = myClipPlanes[aPlaneIter].Normal; - - const Graphic3d_Vec3d aPVertex (anAxis.x() > 0.0 ? theMaxPt.x() : theMinPt.x(), - anAxis.y() > 0.0 ? theMaxPt.y() : theMinPt.y(), - anAxis.z() > 0.0 ? theMaxPt.z() : theMinPt.z()); - Standard_Real aPnt0 = aPVertex.Dot (anAxis); - - if (aPnt0 >= myMinClipProjectionPts[aPlaneIter] + const Graphic3d_Vec3d& anAxis = myClipPlanes[aPlaneIter].Normal; + const Graphic3d_Vec3d aPVertex (anAxis.x() > 0.0 ? theMaxPnt.x() : theMinPnt.x(), + anAxis.y() > 0.0 ? theMaxPnt.y() : theMinPnt.y(), + anAxis.z() > 0.0 ? theMaxPnt.z() : theMinPnt.z()); + const Standard_Real aPnt0 = aPVertex.Dot (anAxis); + if (theIsInside == NULL + && aPnt0 >= myMinClipProjectionPts[aPlaneIter] && aPnt0 <= myMaxClipProjectionPts[aPlaneIter]) { continue; } - const Graphic3d_Vec3d aNVertex (anAxis.x() > 0.0 ? theMinPt.x() : theMaxPt.x(), - anAxis.y() > 0.0 ? theMinPt.y() : theMaxPt.y(), - anAxis.z() > 0.0 ? theMinPt.z() : theMaxPt.z()); - Standard_Real aPnt1 = aNVertex.Dot (anAxis); - - const Standard_Real aMin = aPnt0 < aPnt1 ? aPnt0 : aPnt1; - const Standard_Real aMax = aPnt0 > aPnt1 ? aPnt0 : aPnt1; - - if (aMin > myMaxClipProjectionPts[aPlaneIter] - || aMax < myMinClipProjectionPts[aPlaneIter]) + const Graphic3d_Vec3d aNVertex (anAxis.x() > 0.0 ? theMinPnt.x() : theMaxPnt.x(), + anAxis.y() > 0.0 ? theMinPnt.y() : theMaxPnt.y(), + anAxis.z() > 0.0 ? theMinPnt.z() : theMaxPnt.z()); + const Standard_Real aPnt1 = aNVertex.Dot (anAxis); + + const Standard_Real aBoxProjMin = aPnt0 < aPnt1 ? aPnt0 : aPnt1; + const Standard_Real aBoxProjMax = aPnt0 > aPnt1 ? aPnt0 : aPnt1; + if (aBoxProjMin > myMaxClipProjectionPts[aPlaneIter] + || aBoxProjMax < myMinClipProjectionPts[aPlaneIter]) { return true; } + + if (theIsInside != NULL + && *theIsInside) + { + *theIsInside = aBoxProjMin >= myMinClipProjectionPts[aPlaneIter] + && aBoxProjMax <= myMaxClipProjectionPts[aPlaneIter]; + } } return false; } //! Returns TRUE if given AABB should be discarded by distance culling criterion. - bool isTooDistant (const CullingContext& theCtx, - const Graphic3d_Vec3d& theMinPt, - const Graphic3d_Vec3d& theMaxPt) const + //! @param theMinPnt [in] maximum point of AABB + //! @param theMaxPnt [in] minimum point of AABB + //! @param theIsInside [out] flag indicating if AABB is fully inside; initial value should be set to TRUE + //! @return TRUE if AABB is completely behind culling distance; + //! FALSE in case of partial or complete overlap (use theIsInside to distinguish) + bool IsTooDistant (const CullingContext& theCtx, + const Graphic3d_Vec3d& theMinPnt, + const Graphic3d_Vec3d& theMaxPnt, + Standard_Boolean* theIsInside = NULL) const { if (theCtx.DistCull <= 0.0) { @@ -208,22 +233,34 @@ protected: } // check distance to the bounding sphere as fast approximation - const Graphic3d_Vec3d aSphereCenter = (theMinPt + theMaxPt) * 0.5; - const Standard_Real aSphereRadius = (theMaxPt - theMinPt).maxComp() * 0.5; - return (aSphereCenter - myCamEye).Modulus() - aSphereRadius > theCtx.DistCull; + const Graphic3d_Vec3d aSphereCenter = (theMinPnt + theMaxPnt) * 0.5; + const Standard_Real aSphereRadius = (theMaxPnt - theMinPnt).maxComp() * 0.5; + const Standard_Real aDistToCenter = (aSphereCenter - myCamEye).Modulus(); + if ((aDistToCenter - aSphereRadius) > theCtx.DistCull) + { + // clip if closest point is behind culling distance + return true; + } + if (theIsInside != NULL + && *theIsInside) + { + // check if farthest point is before culling distance + *theIsInside = (aDistToCenter + aSphereRadius) <= theCtx.DistCull; + } + return false; } //! Returns TRUE if given AABB should be discarded by size culling criterion. - bool isTooSmall (const CullingContext& theCtx, - const Graphic3d_Vec3d& theMinPt, - const Graphic3d_Vec3d& theMaxPt) const + bool IsTooSmall (const CullingContext& theCtx, + const Graphic3d_Vec3d& theMinPnt, + const Graphic3d_Vec3d& theMaxPnt) const { if (theCtx.SizeCull2 <= 0.0) { return false; } - const Standard_Real aBoxDiag2 = (theMaxPt - theMinPt).SquareModulus(); + const Standard_Real aBoxDiag2 = (theMaxPnt - theMinPnt).SquareModulus(); if (myIsProjectionParallel) { return aBoxDiag2 < theCtx.SizeCull2; @@ -231,7 +268,7 @@ protected: // note that distances behind the Eye (aBndDist < 0) are not scaled correctly here, // but majority of such objects should be culled by frustum - const Graphic3d_Vec3d aBndCenter = (theMinPt + theMaxPt) * 0.5; + const Graphic3d_Vec3d aBndCenter = (theMinPnt + theMaxPnt) * 0.5; const Standard_Real aBndDist = (aBndCenter - myCamEye).Dot (myCamDir); return aBoxDiag2 < theCtx.SizeCull2 * aBndDist * aBndDist; } diff --git a/src/Graphic3d/Graphic3d_Layer.cxx b/src/Graphic3d/Graphic3d_Layer.cxx index 2fb67ab20e..6b723c8f31 100644 --- a/src/Graphic3d/Graphic3d_Layer.cxx +++ b/src/Graphic3d/Graphic3d_Layer.cxx @@ -452,6 +452,19 @@ void Graphic3d_Layer::updateBVH() const } } +namespace +{ + //! This structure describes the node in BVH + struct NodeInStack + { + NodeInStack (Standard_Integer theId = 0, + Standard_Boolean theIsFullInside = false) : Id (theId), IsFullInside (theIsFullInside) {} + + Standard_Integer Id; //!< node identifier + Standard_Boolean IsFullInside; //!< if the node is completely inside + }; +} + // ======================================================================= // function : UpdateCulling // purpose : @@ -517,33 +530,54 @@ void Graphic3d_Layer::UpdateCulling (Standard_Integer theViewId, aBVHTree = myBVHPrimitives.BVH(); } - if (theSelector.IsCulled (aCullCtx, aBVHTree->MinPoint (0), aBVHTree->MaxPoint (0))) + const bool toCheckFullInside = true; + NodeInStack aNode (0, toCheckFullInside); // a root node + if (theSelector.IsCulled (aCullCtx, aBVHTree->MinPoint (0), aBVHTree->MaxPoint (0), toCheckFullInside ? &aNode.IsFullInside : NULL)) { continue; } - Standard_Integer aStack[BVH_Constants_MaxTreeDepth]; + NodeInStack aStack[BVH_Constants_MaxTreeDepth]; Standard_Integer aHead = -1; - Standard_Integer aNode = 0; // a root node for (;;) { - if (!aBVHTree->IsOuter (aNode)) + if (!aBVHTree->IsOuter (aNode.Id)) { - const Standard_Integer aLeftChildIdx = aBVHTree->Child<0> (aNode); - const Standard_Integer aRightChildIdx = aBVHTree->Child<1> (aNode); - const Standard_Boolean isLeftChildIn = !theSelector.IsCulled (aCullCtx, aBVHTree->MinPoint (aLeftChildIdx), aBVHTree->MaxPoint (aLeftChildIdx)); - const Standard_Boolean isRightChildIn = !theSelector.IsCulled (aCullCtx, aBVHTree->MinPoint (aRightChildIdx), aBVHTree->MaxPoint (aRightChildIdx)); + NodeInStack aLeft (aBVHTree->Child<0> (aNode.Id), toCheckFullInside); + NodeInStack aRight(aBVHTree->Child<1> (aNode.Id), toCheckFullInside); + bool isLeftChildIn = true, isRightChildIn = true; + if (aNode.IsFullInside) + { + // small size should be always checked + isLeftChildIn = !theSelector.IsTooSmall (aCullCtx, aBVHTree->MinPoint (aLeft.Id), aBVHTree->MaxPoint (aLeft.Id)); + isRightChildIn = !theSelector.IsTooSmall (aCullCtx, aBVHTree->MinPoint (aRight.Id), aBVHTree->MaxPoint (aRight.Id)); + } + else + { + isLeftChildIn = !theSelector.IsCulled (aCullCtx, aBVHTree->MinPoint (aLeft.Id), aBVHTree->MaxPoint (aLeft.Id), toCheckFullInside ? &aLeft.IsFullInside : NULL); + if (!isLeftChildIn) + { + aLeft.IsFullInside = false; + } + + isRightChildIn = !theSelector.IsCulled (aCullCtx, aBVHTree->MinPoint (aRight.Id), aBVHTree->MaxPoint (aRight.Id), toCheckFullInside ? &aRight.IsFullInside : NULL); + if (!isRightChildIn) + { + aRight.IsFullInside = false; + } + } + if (isLeftChildIn && isRightChildIn) { - aNode = myBVHIsLeftChildQueuedFirst ? aLeftChildIdx : aRightChildIdx; - aStack[++aHead] = myBVHIsLeftChildQueuedFirst ? aRightChildIdx : aLeftChildIdx; + aNode = myBVHIsLeftChildQueuedFirst ? aLeft : aRight; + aStack[++aHead] = myBVHIsLeftChildQueuedFirst ? aRight : aLeft; myBVHIsLeftChildQueuedFirst = !myBVHIsLeftChildQueuedFirst; } else if (isLeftChildIn || isRightChildIn) { - aNode = isLeftChildIn ? aLeftChildIdx : aRightChildIdx; + aNode = isLeftChildIn ? aLeft : aRight; } else { @@ -557,8 +591,8 @@ void Graphic3d_Layer::UpdateCulling (Standard_Integer theViewId, } else { - const Standard_Integer aStartIdx = aBVHTree->BegPrimitive (aNode); - const Standard_Integer anEndIdx = aBVHTree->EndPrimitive (aNode); + const Standard_Integer aStartIdx = aBVHTree->BegPrimitive (aNode.Id); + const Standard_Integer anEndIdx = aBVHTree->EndPrimitive (aNode.Id); for (Standard_Integer anIdx = aStartIdx; anIdx <= anEndIdx; ++anIdx) { const Graphic3d_CStructure* aStruct = isTrsfPers -- 2.20.1