0028760: Visualization, TKOpenGl - avoid excessive frustum culling traverse within...
[occt.git] / src / OpenGl / OpenGl_BVHTreeSelector.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 _OpenGl_BVHTreeSelector_HeaderFile
17 #define _OpenGl_BVHTreeSelector_HeaderFile
18
19 #include <Graphic3d_Camera.hxx>
20 #include <Graphic3d_WorldViewProjState.hxx>
21 #include <OpenGl_Vec.hxx>
22
23 //! BVHTreeSelector 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
25 //! view volume.
26 class OpenGl_BVHTreeSelector
27 {
28 public:
29   //! Auxiliary structure holding non-persistent culling options.
30   struct CullingContext
31   {
32     Standard_Real DistCull;  //!< culling distance
33     Standard_Real SizeCull2; //!< squared culling size
34
35     //! Empty constructor.
36     CullingContext() : DistCull (-1.0), SizeCull2 (-1.0) {}
37   };
38 public:
39
40   //! Creates an empty selector object with parallel projection type by default.
41   Standard_EXPORT OpenGl_BVHTreeSelector();
42
43   //! Retrieves view volume's planes equations and its vertices from projection and world-view matrices.
44   Standard_EXPORT void SetViewVolume (const Handle(Graphic3d_Camera)& theCamera);
45
46   Standard_EXPORT void SetViewportSize (Standard_Integer theViewportWidth,
47                                         Standard_Integer theViewportHeight,
48                                         Standard_Real theResolutionRatio);
49
50   //! Setup distance culling.
51   Standard_EXPORT void SetCullingDistance (CullingContext& theCtx,
52                                            Standard_Real theDistance) const;
53
54   //! Setup size culling.
55   Standard_EXPORT void SetCullingSize (CullingContext& theCtx,
56                                        Standard_Real theSize) const;
57
58   //! Caches view volume's vertices projections along its normals and AABBs dimensions.
59   //! Must be called at the beginning of each BVH tree traverse loop.
60   Standard_EXPORT void CacheClipPtsProjections();
61
62   //! Checks whether given AABB should be entirely culled or not.
63   //! @param theCtx   [in] culling properties
64   //! @param theMinPt [in] maximum point of AABB
65   //! @param theMaxPt [in] minimum point of AABB
66   //! @return Standard_True, if AABB is in viewing area, Standard_False otherwise
67   bool IsCulled (const CullingContext& theCtx,
68                  const OpenGl_Vec3d& theMinPt,
69                  const OpenGl_Vec3d& theMaxPt) const
70   {
71     return isFullOut   (theMinPt, theMaxPt)
72         || isTooDistant(theCtx, theMinPt, theMaxPt)
73         || isTooSmall  (theCtx, theMinPt, theMaxPt);
74   }
75
76   //! Return the camera definition.
77   const Handle(Graphic3d_Camera)& Camera() const { return myCamera; }
78
79   //! Returns current projection matrix.
80   const OpenGl_Mat4d& ProjectionMatrix() const
81   {
82     return myProjectionMat;
83   }
84
85   //! Returns current world view transformation matrix.
86   const OpenGl_Mat4d& WorldViewMatrix() const
87   {
88     return myWorldViewMat;
89   }
90
91   Standard_Integer ViewportWidth() const
92   {
93     return myViewportWidth;
94   }
95
96   Standard_Integer ViewportHeight() const
97   {
98     return myViewportHeight;
99   }
100
101   //! Returns state of current world view projection transformation matrices.
102   const Graphic3d_WorldViewProjState& WorldViewProjState() const
103   {
104     return myWorldViewProjState;
105   }
106
107 protected:
108
109   //! Calculates signed distance from plane to point.
110   //! @param theNormal [in] the plane's normal.
111   //! @param thePnt    [in]
112   Standard_EXPORT Standard_Real SignedPlanePointDistance (const OpenGl_Vec4d& theNormal,
113                                                           const OpenGl_Vec4d& thePnt);
114
115   //! Detects if AABB overlaps view volume using separating axis theorem (SAT).
116   //! @param theMinPt [in] maximum point of AABB.
117   //! @param theMaxPt [in] minimum point of AABB.
118   //! @return FALSE, if AABB is in viewing area, TRUE otherwise.
119   bool isFullOut (const OpenGl_Vec3d& theMinPt,
120                   const OpenGl_Vec3d& theMaxPt) const
121   {
122     //     E1
123     //    |_ E0
124     //   /
125     //    E2
126
127     // E0 test
128     if (theMinPt.x() > myMaxOrthoProjectionPts[0]
129      || theMaxPt.x() < myMinOrthoProjectionPts[0])
130     {
131       return true;
132     }
133
134     // E1 test
135     if (theMinPt.y() > myMaxOrthoProjectionPts[1]
136      || theMaxPt.y() < myMinOrthoProjectionPts[1])
137     {
138       return true;
139     }
140
141     // E2 test
142     if (theMinPt.z() > myMaxOrthoProjectionPts[2]
143      || theMaxPt.z() < myMinOrthoProjectionPts[2])
144     {
145       return true;
146     }
147
148     Standard_Real aBoxProjMax = 0.0, aBoxProjMin = 0.0;
149     const Standard_Integer anIncFactor = myIsProjectionParallel ? 2 : 1;
150     for (Standard_Integer aPlaneIter = 0; aPlaneIter < 5; aPlaneIter += anIncFactor)
151     {
152       OpenGl_Vec4d aPlane = myClipPlanes[aPlaneIter];
153       aBoxProjMax = (aPlane.x() > 0.0 ? (aPlane.x() * theMaxPt.x()) : aPlane.x() * theMinPt.x())
154                   + (aPlane.y() > 0.0 ? (aPlane.y() * theMaxPt.y()) : aPlane.y() * theMinPt.y())
155                   + (aPlane.z() > 0.0 ? (aPlane.z() * theMaxPt.z()) : aPlane.z() * theMinPt.z());
156       if (aBoxProjMax > myMinClipProjectionPts[aPlaneIter]
157        && aBoxProjMax < myMaxClipProjectionPts[aPlaneIter])
158       {
159         continue;
160       }
161
162       aBoxProjMin = (aPlane.x() < 0.0 ? aPlane.x() * theMaxPt.x() : aPlane.x() * theMinPt.x())
163                   + (aPlane.y() < 0.0 ? aPlane.y() * theMaxPt.y() : aPlane.y() * theMinPt.y())
164                   + (aPlane.z() < 0.0 ? aPlane.z() * theMaxPt.z() : aPlane.z() * theMinPt.z());
165       if (aBoxProjMin > myMaxClipProjectionPts[aPlaneIter]
166        || aBoxProjMax < myMinClipProjectionPts[aPlaneIter])
167       {
168         return true;
169       }
170     }
171     return false;
172   }
173
174   //! Returns TRUE if given AABB should be discarded by distance culling criterion.
175   bool isTooDistant (const CullingContext& theCtx,
176                      const OpenGl_Vec3d& theMinPt,
177                      const OpenGl_Vec3d& theMaxPt) const
178   {
179     if (theCtx.DistCull <= 0.0)
180     {
181       return false;
182     }
183
184     // check distance to the bounding sphere as fast approximation
185     const Graphic3d_Vec3d aSphereCenter = (theMinPt + theMaxPt) * 0.5;
186     const Standard_Real   aSphereRadius = (theMaxPt - theMinPt).maxComp() * 0.5;
187     return (aSphereCenter - myCamEye).Modulus() - aSphereRadius > theCtx.DistCull;
188   }
189
190   //! Returns TRUE if given AABB should be discarded by size culling criterion.
191   bool isTooSmall (const CullingContext& theCtx,
192                    const OpenGl_Vec3d& theMinPt,
193                    const OpenGl_Vec3d& theMaxPt) const
194   {
195     if (theCtx.SizeCull2 <= 0.0)
196     {
197       return false;
198     }
199     return (theMaxPt - theMinPt).SquareModulus() < theCtx.SizeCull2;
200   }
201
202 protected:
203
204   //! Enumerates planes of view volume.
205   enum
206   {
207     Plane_Top,
208     Plane_Bottom,
209     Plane_Left,
210     Plane_Right,
211     Plane_Near,
212     Plane_Far,
213     PlanesNB
214   };
215
216   //! Enumerates vertices of view volume.
217   enum
218   {
219     ClipVert_LeftTopNear,
220     ClipVert_LeftBottomNear,
221     ClipVert_RightTopNear,
222     ClipVert_RightBottomNear,
223     ClipVert_LeftTopFar,
224     ClipVert_LeftBottomFar,
225     ClipVert_RightTopFar,
226     ClipVert_RightBottomFar,
227     ClipVerticesNB
228   };
229
230 protected:
231
232   OpenGl_Vec4d myClipPlanes[PlanesNB];      //!< Plane equations
233   OpenGl_Vec4d myClipVerts[ClipVerticesNB]; //!< Vertices
234
235   Handle(Graphic3d_Camera) myCamera; //!< camera definition
236
237   // for caching clip points projections onto viewing area normals once per traverse
238   // ORDER: TOP, BOTTOM, LEFT, RIGHT, NEAR, FAR
239   Standard_Real myMaxClipProjectionPts[PlanesNB]; //!< Max view volume's vertices projections onto its normals
240   Standard_Real myMinClipProjectionPts[PlanesNB]; //!< Min view volume's vertices projections onto its normals
241
242   // for caching clip points projections onto AABB normals once per traverse
243   // ORDER: E0, E1, E2
244   Standard_Real myMaxOrthoProjectionPts[3]; //!< Max view volume's vertices projections onto normalized dimensions of AABB
245   Standard_Real myMinOrthoProjectionPts[3]; //!< Min view volume's vertices projections onto normalized dimensions of AABB
246
247   Standard_Boolean myIsProjectionParallel;
248
249   OpenGl_Mat4d myProjectionMat;
250   OpenGl_Mat4d myWorldViewMat;
251
252   Standard_Integer myViewportWidth;
253   Standard_Integer myViewportHeight;
254
255   Graphic3d_WorldViewProjState myWorldViewProjState; //!< State of world view projection matrices.
256
257   Graphic3d_Vec3d myCamEye;      //!< camera eye position for distance culling
258   Standard_Real   myCamScaleInv; //!< inverted camera scale for size culling
259   Standard_Real   myPixelSize;   //!< pixel size for size culling
260
261 };
262
263 #endif // _OpenGl_BVHTreeSelector_HeaderFile