src/Graphic3d/Graphic3d_CullingTool.hxx

   1 // Created on: 2013-12-25
   2 // Created by: Varvara POSKONINA
   3 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #ifndef _Graphic3d_CullingTool_HeaderFile
  17 #define _Graphic3d_CullingTool_HeaderFile
  18
  19 #include <Graphic3d_Camera.hxx>
  20 #include <Graphic3d_Vec4.hxx>
  21 #include <Graphic3d_WorldViewProjState.hxx>
  22
  23 //! Graphic3d_CullingTool class provides a possibility to store parameters of view volume,
  24 //! such as its vertices and equations, and contains methods detecting if given AABB overlaps view volume.
  25 class Graphic3d_CullingTool
  26 {
  27 public:
  28   //! Auxiliary structure holding non-persistent culling options.
  29   struct CullingContext
  30   {
  31     Standard_Real DistCull;  //!< culling distance
  32     Standard_Real SizeCull2; //!< squared culling size
  33
  34     //! Empty constructor.
  35     CullingContext() : DistCull (-1.0), SizeCull2 (-1.0) {}
  36   };
  37
  38   //! Auxiliary structure representing 3D plane.
  39   struct Plane
  40   {
  41     //! Creates default plane.
  42     Plane()
  43     : Origin (0.0, 0.0, 0.0),
  44       Normal (0.0, 0.0, 1.0) {}
  45
  46     //! Creates plane with specific parameters.
  47     Plane (const Graphic3d_Vec3d& theOrigin,
  48            const Graphic3d_Vec3d& theNormal)
  49     : Origin (theOrigin),
  50       Normal (theNormal) {}
  51
  52     Graphic3d_Vec3d Origin;
  53     Graphic3d_Vec3d Normal;
  54   };
  55
  56 public:
  57
  58   //! Creates an empty selector object with parallel projection type by default.
  59   Standard_EXPORT Graphic3d_CullingTool();
  60
  61   //! Retrieves view volume's planes equations and its vertices from projection and world-view matrices.
  62   //! @param theCamera [in] camera definition
  63   //! @param theModelWorld [in] optional object transformation for computing frustum in object local coordinate system
  64   Standard_EXPORT void SetViewVolume (const Handle(Graphic3d_Camera)& theCamera,
  65                                       const Graphic3d_Mat4d& theModelWorld = Graphic3d_Mat4d());
  66
  67   Standard_EXPORT void SetViewportSize (Standard_Integer theViewportWidth,
  68                                         Standard_Integer theViewportHeight,
  69                                         Standard_Real theResolutionRatio);
  70
  71   //! Setup distance culling.
  72   Standard_EXPORT void SetCullingDistance (CullingContext& theCtx,
  73                                            Standard_Real theDistance) const;
  74
  75   //! Setup size culling.
  76   Standard_EXPORT void SetCullingSize (CullingContext& theCtx,
  77                                        Standard_Real theSize) const;
  78
  79   //! Caches view volume's vertices projections along its normals and AABBs dimensions.
  80   //! Must be called at the beginning of each BVH tree traverse loop.
  81   Standard_EXPORT void CacheClipPtsProjections();
  82
  83   //! Checks whether given AABB should be entirely culled or not.
  84   //! @param theCtx    [in] culling properties
  85   //! @param theMinPnt [in] maximum point of AABB
  86   //! @param theMaxPnt [in] minimum point of AABB
  87   //! @param theIsInside [out] flag indicating if AABB is fully inside; initial value should be set to TRUE
  88   //! @return TRUE if AABB is completely outside of view frustum or culled by size/distance;
  89   //!         FALSE in case of partial or complete overlap (use theIsInside to distinguish)
  90   bool IsCulled (const CullingContext& theCtx,
  91                  const Graphic3d_Vec3d& theMinPnt,
  92                  const Graphic3d_Vec3d& theMaxPnt,
  93                  Standard_Boolean*      theIsInside = NULL) const
  94   {
  95     return IsOutFrustum(theMinPnt, theMaxPnt, theIsInside)
  96         || IsTooDistant(theCtx, theMinPnt, theMaxPnt, theIsInside)
  97         || IsTooSmall  (theCtx, theMinPnt, theMaxPnt);
  98   }
  99
 100   //! Return the camera definition.
 101   const Handle(Graphic3d_Camera)& Camera() const { return myCamera; }
 102
 103   //! Returns current projection matrix.
 104   const Graphic3d_Mat4d& ProjectionMatrix() const
 105   {
 106     return myProjectionMat;
 107   }
 108
 109   //! Returns current world view transformation matrix.
 110   const Graphic3d_Mat4d& WorldViewMatrix() const
 111   {
 112     return myWorldViewMat;
 113   }
 114
 115   Standard_Integer ViewportWidth() const
 116   {
 117     return myViewportWidth;
 118   }
 119
 120   Standard_Integer ViewportHeight() const
 121   {
 122     return myViewportHeight;
 123   }
 124
 125   //! Returns state of current world view projection transformation matrices.
 126   const Graphic3d_WorldViewProjState& WorldViewProjState() const
 127   {
 128     return myWorldViewProjState;
 129   }
 130
 131   //! Returns camera eye position.
 132   const Graphic3d_Vec3d& CameraEye() const { return myCamEye; }
 133
 134   //! Returns camera direction.
 135   const Graphic3d_Vec3d& CameraDirection() const { return myCamDir; }
 136
 137 public:
 138
 139   //! Calculates signed distance from plane to point.
 140   //! @param theNormal [in] the plane's normal.
 141   //! @param thePnt    [in]
 142   Standard_EXPORT Standard_Real SignedPlanePointDistance (const Graphic3d_Vec4d& theNormal,
 143                                                           const Graphic3d_Vec4d& thePnt);
 144
 145   //! Detects if AABB overlaps view volume using separating axis theorem (SAT).
 146   //! @param theMinPnt   [in] maximum point of AABB
 147   //! @param theMaxPnt   [in] minimum point of AABB
 148   //! @param theIsInside [out] flag indicating if AABB is fully inside; initial value should be set to TRUE
 149   //! @return TRUE if AABB is completely outside of view frustum;
 150   //!         FALSE in case of partial or complete overlap (use theIsInside to distinguish)
 151   //! @sa SelectMgr_Frustum::hasOverlap()
 152   bool IsOutFrustum (const Graphic3d_Vec3d& theMinPnt,
 153                      const Graphic3d_Vec3d& theMaxPnt,
 154                      Standard_Boolean*      theIsInside = NULL) const
 155   {
 156     //     E1
 157     //    |_ E0
 158     //   /
 159     //    E2
 160     if (theMinPnt[0] > myMaxOrthoProjectionPts[0] // E0 test (x axis)
 161      || theMaxPnt[0] < myMinOrthoProjectionPts[0]
 162      || theMinPnt[1] > myMaxOrthoProjectionPts[1] // E1 test (y axis)
 163      || theMaxPnt[1] < myMinOrthoProjectionPts[1]
 164      || theMinPnt[2] > myMaxOrthoProjectionPts[2] // E2 test (z axis)
 165      || theMaxPnt[2] < myMinOrthoProjectionPts[2])
 166     {
 167       return true;
 168     }
 169     if (theIsInside != NULL
 170     && *theIsInside)
 171     {
 172       *theIsInside = theMinPnt[0] >= myMinOrthoProjectionPts[0] // E0 test (x axis)
 173                   && theMaxPnt[0] <= myMaxOrthoProjectionPts[0]
 174                   && theMinPnt[1] >= myMinOrthoProjectionPts[1] // E1 test (y axis)
 175                   && theMaxPnt[1] <= myMaxOrthoProjectionPts[1]
 176                   && theMinPnt[1] >= myMinOrthoProjectionPts[2] // E2 test (z axis)
 177                   && theMaxPnt[1] <= myMaxOrthoProjectionPts[2];
 178     }
 179
 180     const Standard_Integer anIncFactor = myIsProjectionParallel ? 2 : 1;
 181     for (Standard_Integer aPlaneIter = 0; aPlaneIter < PlanesNB - 1; aPlaneIter += anIncFactor)
 182     {
 183       // frustum normals
 184       const Graphic3d_Vec3d& anAxis = myClipPlanes[aPlaneIter].Normal;
 185       const Graphic3d_Vec3d aPVertex (anAxis.x() > 0.0 ? theMaxPnt.x() : theMinPnt.x(),
 186                                       anAxis.y() > 0.0 ? theMaxPnt.y() : theMinPnt.y(),
 187                                       anAxis.z() > 0.0 ? theMaxPnt.z() : theMinPnt.z());
 188       const Standard_Real aPnt0 = aPVertex.Dot (anAxis);
 189       if (theIsInside == NULL
 190        && aPnt0 >= myMinClipProjectionPts[aPlaneIter]
 191        && aPnt0 <= myMaxClipProjectionPts[aPlaneIter])
 192       {
 193         continue;
 194       }
 195
 196       const Graphic3d_Vec3d aNVertex (anAxis.x() > 0.0 ? theMinPnt.x() : theMaxPnt.x(),
 197                                       anAxis.y() > 0.0 ? theMinPnt.y() : theMaxPnt.y(),
 198                                       anAxis.z() > 0.0 ? theMinPnt.z() : theMaxPnt.z());
 199       const Standard_Real aPnt1 = aNVertex.Dot (anAxis);
 200
 201       const Standard_Real aBoxProjMin = aPnt0 < aPnt1 ? aPnt0 : aPnt1;
 202       const Standard_Real aBoxProjMax = aPnt0 > aPnt1 ? aPnt0 : aPnt1;
 203       if (aBoxProjMin > myMaxClipProjectionPts[aPlaneIter]
 204        || aBoxProjMax < myMinClipProjectionPts[aPlaneIter])
 205       {
 206         return true;
 207       }
 208
 209       if (theIsInside != NULL
 210       && *theIsInside)
 211       {
 212         *theIsInside = aBoxProjMin >= myMinClipProjectionPts[aPlaneIter]
 213                     && aBoxProjMax <= myMaxClipProjectionPts[aPlaneIter];
 214       }
 215     }
 216     return false;
 217   }
 218
 219   //! Returns TRUE if given AABB should be discarded by distance culling criterion.
 220   //! @param theMinPnt   [in] maximum point of AABB
 221   //! @param theMaxPnt   [in] minimum point of AABB
 222   //! @param theIsInside [out] flag indicating if AABB is fully inside; initial value should be set to TRUE
 223   //! @return TRUE if AABB is completely behind culling distance;
 224   //!         FALSE in case of partial or complete overlap (use theIsInside to distinguish)
 225   bool IsTooDistant (const CullingContext&  theCtx,
 226                      const Graphic3d_Vec3d& theMinPnt,
 227                      const Graphic3d_Vec3d& theMaxPnt,
 228                      Standard_Boolean*      theIsInside = NULL) const
 229   {
 230     if (theCtx.DistCull <= 0.0)
 231     {
 232       return false;
 233     }
 234
 235     // check distance to the bounding sphere as fast approximation
 236     const Graphic3d_Vec3d aSphereCenter = (theMinPnt + theMaxPnt) * 0.5;
 237     const Standard_Real   aSphereRadius = (theMaxPnt - theMinPnt).maxComp() * 0.5;
 238     const Standard_Real   aDistToCenter = (aSphereCenter - myCamEye).Modulus();
 239     if ((aDistToCenter - aSphereRadius) > theCtx.DistCull)
 240     {
 241       // clip if closest point is behind culling distance
 242       return true;
 243     }
 244     if (theIsInside != NULL
 245     && *theIsInside)
 246     {
 247       // check if farthest point is before culling distance
 248       *theIsInside = (aDistToCenter + aSphereRadius) <= theCtx.DistCull;
 249     }
 250     return false;
 251   }
 252
 253   //! Returns TRUE if given AABB should be discarded by size culling criterion.
 254   bool IsTooSmall (const CullingContext&  theCtx,
 255                    const Graphic3d_Vec3d& theMinPnt,
 256                    const Graphic3d_Vec3d& theMaxPnt) const
 257   {
 258     if (theCtx.SizeCull2 <= 0.0)
 259     {
 260       return false;
 261     }
 262
 263     const Standard_Real aBoxDiag2 = (theMaxPnt - theMinPnt).SquareModulus();
 264     if (myIsProjectionParallel)
 265     {
 266       return aBoxDiag2 < theCtx.SizeCull2;
 267     }
 268
 269     // note that distances behind the Eye (aBndDist < 0) are not scaled correctly here,
 270     // but majority of such objects should be culled by frustum
 271     const Graphic3d_Vec3d aBndCenter = (theMinPnt + theMaxPnt) * 0.5;
 272     const Standard_Real   aBndDist   = (aBndCenter - myCamEye).Dot (myCamDir);
 273     return aBoxDiag2 < theCtx.SizeCull2 * aBndDist * aBndDist;
 274   }
 275
 276 protected:
 277
 278   //! Enumerates planes of view volume.
 279   enum
 280   {
 281     Plane_Left,
 282     Plane_Right,
 283     Plane_Bottom,
 284     Plane_Top,
 285     Plane_Near,
 286     Plane_Far,
 287     PlanesNB
 288   };
 289
 290 protected:
 291
 292   Plane                               myClipPlanes[PlanesNB]; //!< Planes
 293   NCollection_Array1<Graphic3d_Vec3d> myClipVerts;            //!< Vertices
 294
 295   Handle(Graphic3d_Camera) myCamera; //!< camera definition
 296
 297   // for caching clip points projections onto viewing area normals once per traverse
 298   // ORDER: LEFT, RIGHT, BOTTOM, TOP, NEAR, FAR
 299   Standard_Real myMaxClipProjectionPts[PlanesNB]; //!< Max view volume's vertices projections onto its normals
 300   Standard_Real myMinClipProjectionPts[PlanesNB]; //!< Min view volume's vertices projections onto its normals
 301
 302   // for caching clip points projections onto AABB normals once per traverse
 303   // ORDER: E0, E1, E2
 304   Standard_Real myMaxOrthoProjectionPts[3]; //!< Max view volume's vertices projections onto normalized dimensions of AABB
 305   Standard_Real myMinOrthoProjectionPts[3]; //!< Min view volume's vertices projections onto normalized dimensions of AABB
 306
 307   Standard_Boolean myIsProjectionParallel;
 308
 309   Graphic3d_Mat4d myProjectionMat;
 310   Graphic3d_Mat4d myWorldViewMat;
 311
 312   Standard_Integer myViewportWidth;
 313   Standard_Integer myViewportHeight;
 314
 315   Graphic3d_WorldViewProjState myWorldViewProjState; //!< State of world view projection matrices.
 316
 317   Graphic3d_Vec3d myCamEye;      //!< camera eye position for distance culling
 318   Graphic3d_Vec3d myCamDir;      //!< camera direction for size culling
 319   Standard_Real   myCamScale;    //!< camera scale for size culling
 320   Standard_Real   myPixelSize;   //!< pixel size for size culling
 321
 322 };
 323
 324 #endif // _Graphic3d_CullingTool_HeaderFile