0031511: Point Cloud Rendering, Volume Rendering - reuse Graphic3d_CullingTool
authorkgv <kgv@opencascade.com>
Sun, 19 Apr 2020 18:42:42 +0000 (21:42 +0300)
committerbugmaster <bugmaster@opencascade.com>
Fri, 24 Apr 2020 17:03:50 +0000 (20:03 +0300)
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
src/Graphic3d/Graphic3d_Camera.hxx
src/Graphic3d/Graphic3d_CullingTool.cxx
src/Graphic3d/Graphic3d_CullingTool.hxx
src/Graphic3d/Graphic3d_Layer.cxx

index a251811..854ec60 100644 (file)
@@ -1475,7 +1475,8 @@ Standard_EXPORT void NCollection_Lerp<Handle(Graphic3d_Camera)>::Interpolate (co
 //function : FrustumPoints
 //purpose  :
 //=======================================================================
-void Graphic3d_Camera::FrustumPoints (NCollection_Array1<Graphic3d_Vec3d>& thePoints) const
+void Graphic3d_Camera::FrustumPoints (NCollection_Array1<Graphic3d_Vec3d>& thePoints,
+                                      const Graphic3d_Mat4d& theModelWorld) const
 {
   if (thePoints.Length() != FrustumVerticesNB)
   {
@@ -1483,7 +1484,7 @@ void Graphic3d_Camera::FrustumPoints (NCollection_Array1<Graphic3d_Vec3d>& 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;
index e2f3fbe..f4b5246 100644 (file)
@@ -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<Graphic3d_Vec3d>& thePoints) const;
+  Standard_EXPORT void FrustumPoints (NCollection_Array1<Graphic3d_Vec3d>& thePoints,
+                                      const Graphic3d_Mat4d& theModelWorld = Graphic3d_Mat4d()) const;
 
 private:
 
index c2a11be..d86007e 100644 (file)
@@ -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);
-      }
+    }
   }
 }
 
index f76a72b..ce92e0e 100644 (file)
@@ -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;
   }
index 2fb67ab..6b723c8 100644 (file)
@@ -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