0024023: Revamp the OCCT Handle -- general
[occt.git] / src / OpenGl / OpenGl_BVHTreeSelector.cxx
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 #include <limits>
17
18 #include <OpenGl_BVHTreeSelector.hxx>
19 #include <OpenGl_BVHClipPrimitiveSet.hxx>
20 #include <Graphic3d_GraphicDriver.hxx>
21
22 // =======================================================================
23 // function : OpenGl_BVHTreeSelector
24 // purpose  :
25 // =======================================================================
26 OpenGl_BVHTreeSelector::OpenGl_BVHTreeSelector()
27 : myIsProjectionParallel (Standard_True),
28   myProjectionState      (0),
29   myModelViewState       (0)
30 {
31   //
32 }
33
34 // =======================================================================
35 // function : SetClipVolume
36 // purpose  : Retrieves view volume's planes equations and its vertices from projection and modelview matrices.
37 // =======================================================================
38 void OpenGl_BVHTreeSelector::SetViewVolume (const Handle(Graphic3d_Camera)& theCamera)
39 {
40   myIsProjectionParallel = theCamera->IsOrthographic();
41   const OpenGl_Mat4& aProjMat  = theCamera->ProjectionMatrixF();
42   const OpenGl_Mat4& aModelMat = theCamera->OrientationMatrixF();
43
44   Standard_ShortReal nLeft = 0.0f, nRight = 0.0f, nTop = 0.0f, nBottom = 0.0f;
45   Standard_ShortReal fLeft = 0.0f, fRight = 0.0f, fTop = 0.0f, fBottom = 0.0f;
46   Standard_ShortReal aNear = 0.0f, aFar   = 0.0f;
47   if (!myIsProjectionParallel)
48   {
49     // handle perspective projection
50     aNear   = aProjMat.GetValue (2, 3) / (- 1.0f + aProjMat.GetValue (2, 2));
51     aFar    = aProjMat.GetValue (2, 3) / (  1.0f + aProjMat.GetValue (2, 2));
52     // Near plane
53     nLeft   = aNear * (aProjMat.GetValue (0, 2) - 1.0f) / aProjMat.GetValue (0, 0);
54     nRight  = aNear * (aProjMat.GetValue (0, 2) + 1.0f) / aProjMat.GetValue (0, 0);
55     nTop    = aNear * (aProjMat.GetValue (1, 2) + 1.0f) / aProjMat.GetValue (1, 1);
56     nBottom = aNear * (aProjMat.GetValue (1, 2) - 1.0f) / aProjMat.GetValue (1, 1);
57     // Far plane
58     fLeft   = aFar  * (aProjMat.GetValue (0, 2) - 1.0f) / aProjMat.GetValue (0, 0);
59     fRight  = aFar  * (aProjMat.GetValue (0, 2) + 1.0f) / aProjMat.GetValue (0, 0);
60     fTop    = aFar  * (aProjMat.GetValue (1, 2) + 1.0f) / aProjMat.GetValue (1, 1);
61     fBottom = aFar  * (aProjMat.GetValue (1, 2) - 1.0f) / aProjMat.GetValue (1, 1);
62   }
63   else
64   {
65     // handle orthographic projection
66     aNear   = (1.0f / aProjMat.GetValue (2, 2)) * (aProjMat.GetValue (2, 3) + 1.0f);
67     aFar    = (1.0f / aProjMat.GetValue (2, 2)) * (aProjMat.GetValue (2, 3) - 1.0f);
68     // Near plane
69     nLeft   = ( 1.0f + aProjMat.GetValue (0, 3)) / (-aProjMat.GetValue (0, 0));
70     fLeft   = nLeft;
71     nRight  = ( 1.0f - aProjMat.GetValue (0, 3)) /   aProjMat.GetValue (0, 0);
72     fRight  = nRight;
73     nTop    = ( 1.0f - aProjMat.GetValue (1, 3)) /   aProjMat.GetValue (1, 1);
74     fTop    = nTop;
75     nBottom = (-1.0f - aProjMat.GetValue (1, 3)) /   aProjMat.GetValue (1, 1);
76     fBottom = nBottom;
77   }
78
79   OpenGl_Vec4 aLeftTopNear     (nLeft,  nTop,    -aNear, 1.0f), aRightBottomFar (fRight, fBottom, -aFar, 1.0f);
80   OpenGl_Vec4 aLeftBottomNear  (nLeft,  nBottom, -aNear, 1.0f), aRightTopFar    (fRight, fTop,    -aFar, 1.0f);
81   OpenGl_Vec4 aRightBottomNear (nRight, nBottom, -aNear, 1.0f), aLeftTopFar     (fLeft,  fTop,    -aFar, 1.0f);
82   OpenGl_Vec4 aRightTopNear    (nRight, nTop,    -aNear, 1.0f), aLeftBottomFar  (fLeft,  fBottom, -aFar, 1.0f);
83
84   const OpenGl_Mat4 aViewProj = aModelMat * aProjMat;
85   OpenGl_Mat4 anInvModelView;
86   aModelMat.Inverted(anInvModelView);
87
88   myClipVerts[ClipVert_LeftTopNear]     = anInvModelView * aLeftTopNear;
89   myClipVerts[ClipVert_RightBottomFar]  = anInvModelView * aRightBottomFar;
90   myClipVerts[ClipVert_LeftBottomNear]  = anInvModelView * aLeftBottomNear;
91   myClipVerts[ClipVert_RightTopFar]     = anInvModelView * aRightTopFar;
92   myClipVerts[ClipVert_RightBottomNear] = anInvModelView * aRightBottomNear;
93   myClipVerts[ClipVert_LeftTopFar]      = anInvModelView * aLeftTopFar;
94   myClipVerts[ClipVert_RightTopNear]    = anInvModelView * aRightTopNear;
95   myClipVerts[ClipVert_LeftBottomFar]   = anInvModelView * aLeftBottomFar;
96
97   // UNNORMALIZED!
98   myClipPlanes[Plane_Left]   = aViewProj.GetRow (3) + aViewProj.GetRow (0);
99   myClipPlanes[Plane_Right]  = aViewProj.GetRow (3) - aViewProj.GetRow (0);
100   myClipPlanes[Plane_Top]    = aViewProj.GetRow (3) - aViewProj.GetRow (1);
101   myClipPlanes[Plane_Bottom] = aViewProj.GetRow (3) + aViewProj.GetRow (1);
102   myClipPlanes[Plane_Near]   = aViewProj.GetRow (3) + aViewProj.GetRow (2);
103   myClipPlanes[Plane_Far]    = aViewProj.GetRow (3) - aViewProj.GetRow (2);
104
105   gp_Pnt aPtCenter = theCamera->Center();
106   OpenGl_Vec4 aCenter (static_cast<Standard_ShortReal> (aPtCenter.X()),
107                        static_cast<Standard_ShortReal> (aPtCenter.Y()),
108                        static_cast<Standard_ShortReal> (aPtCenter.Z()),
109                        1.0f);
110
111   for (Standard_Integer aPlaneIter = 0; aPlaneIter < PlanesNB; ++aPlaneIter)
112   {
113     OpenGl_Vec4 anEq = myClipPlanes[aPlaneIter];
114     if (SignedPlanePointDistance (anEq, aCenter) > 0)
115     {
116       anEq *= -1.0f;
117       myClipPlanes[aPlaneIter] = anEq;
118     }
119   }
120 }
121
122 // =======================================================================
123 // function : SignedPlanePointDistance
124 // purpose  :
125 // =======================================================================
126 Standard_ShortReal OpenGl_BVHTreeSelector::SignedPlanePointDistance (const OpenGl_Vec4& theNormal,
127                                                                      const OpenGl_Vec4& thePnt)
128 {
129   const Standard_ShortReal aNormLength = std::sqrt (theNormal.x() * theNormal.x()
130                                                   + theNormal.y() * theNormal.y()
131                                                   + theNormal.z() * theNormal.z());
132
133   if (aNormLength < FLT_EPSILON)
134     return 0.0f;
135
136   const Standard_ShortReal anInvNormLength = 1.0f / aNormLength;
137   const Standard_ShortReal aD  = theNormal.w() * anInvNormLength;
138   const Standard_ShortReal anA = theNormal.x() * anInvNormLength;
139   const Standard_ShortReal aB  = theNormal.y() * anInvNormLength;
140   const Standard_ShortReal aC  = theNormal.z() * anInvNormLength;
141   return aD + (anA * thePnt.x() + aB * thePnt.y() + aC * thePnt.z());
142 }
143
144 // =======================================================================
145 // function : CacheClipPtsProjections
146 // purpose  : Caches view volume's vertices projections along its normals and AABBs dimensions
147 //            Must be called at the beginning of each BVH tree traverse loop
148 // =======================================================================
149 void OpenGl_BVHTreeSelector::CacheClipPtsProjections()
150 {
151   const Standard_Integer anIncFactor = myIsProjectionParallel ? 2 : 1;
152   for (Standard_Integer aPlaneIter = 0; aPlaneIter < 5; aPlaneIter += anIncFactor)
153   {
154     const OpenGl_Vec4 aPlane = myClipPlanes[aPlaneIter];
155     Standard_ShortReal aMaxProj = -std::numeric_limits<Standard_ShortReal>::max();
156     Standard_ShortReal aMinProj =  std::numeric_limits<Standard_ShortReal>::max();
157     for (Standard_Integer aCornerIter = 0; aCornerIter < ClipVerticesNB; ++aCornerIter)
158     {
159       Standard_ShortReal aProjection = aPlane.x() * myClipVerts[aCornerIter].x() +
160                                        aPlane.y() * myClipVerts[aCornerIter].y() +
161                                        aPlane.z() * myClipVerts[aCornerIter].z();
162       aMaxProj = Max (aProjection, aMaxProj);
163       aMinProj = Min (aProjection, aMinProj);
164     }
165     myMaxClipProjectionPts[aPlaneIter] = aMaxProj;
166     myMinClipProjectionPts[aPlaneIter] = aMinProj;
167   }
168
169   for (Standard_Integer aDim = 0; aDim < 3; ++aDim)
170   {
171     Standard_ShortReal aMaxProj = -std::numeric_limits<Standard_ShortReal>::max();
172     Standard_ShortReal aMinProj =  std::numeric_limits<Standard_ShortReal>::max();
173     for (Standard_Integer aCornerIter = 0; aCornerIter < ClipVerticesNB; ++aCornerIter)
174     {
175       Standard_ShortReal aProjection = aDim == 0 ? myClipVerts[aCornerIter].x()
176         : (aDim == 1 ? myClipVerts[aCornerIter].y() : myClipVerts[aCornerIter].z());
177       aMaxProj = Max (aProjection, aMaxProj);
178       aMinProj = Min (aProjection, aMinProj);
179     }
180     myMaxOrthoProjectionPts[aDim] = aMaxProj;
181     myMinOrthoProjectionPts[aDim] = aMinProj;
182   }
183 }
184
185 // =======================================================================
186 // function : Intersect
187 // purpose  : Detects if AABB overlaps view volume using separating axis theorem (SAT)
188 // =======================================================================
189 Standard_Boolean OpenGl_BVHTreeSelector::Intersect (const OpenGl_Vec4& theMinPt,
190                                                     const OpenGl_Vec4& theMaxPt) const
191 {
192   //     E1
193   //    |_ E0
194   //   /
195   //    E2
196
197   // E0 test
198   if (theMinPt.x() > myMaxOrthoProjectionPts[0]
199    || theMaxPt.x() < myMinOrthoProjectionPts[0])
200   {
201     return Standard_False;
202   }
203
204   // E1 test
205   if (theMinPt.y() > myMaxOrthoProjectionPts[1]
206    || theMaxPt.y() < myMinOrthoProjectionPts[1])
207   {
208     return Standard_False;
209   }
210
211   // E2 test
212   if (theMinPt.z() > myMaxOrthoProjectionPts[2]
213    || theMaxPt.z() < myMinOrthoProjectionPts[2])
214   {
215     return Standard_False;
216   }
217
218   Standard_ShortReal aBoxProjMax = 0.0f, aBoxProjMin = 0.0f;
219   const Standard_Integer anIncFactor = myIsProjectionParallel ? 2 : 1;
220   for (Standard_Integer aPlaneIter = 0; aPlaneIter < 5; aPlaneIter += anIncFactor)
221   {
222     OpenGl_Vec4 aPlane = myClipPlanes[aPlaneIter];
223     aBoxProjMax = (aPlane.x() > 0.f ? (aPlane.x() * theMaxPt.x()) : aPlane.x() * theMinPt.x()) +
224                   (aPlane.y() > 0.f ? (aPlane.y() * theMaxPt.y()) : aPlane.y() * theMinPt.y()) +
225                   (aPlane.z() > 0.f ? (aPlane.z() * theMaxPt.z()) : aPlane.z() * theMinPt.z());
226     if (aBoxProjMax > myMinClipProjectionPts[aPlaneIter]
227      && aBoxProjMax < myMaxClipProjectionPts[aPlaneIter])
228     {
229       continue;
230     }
231
232     aBoxProjMin = (aPlane.x() < 0.f ? aPlane.x() * theMaxPt.x() : aPlane.x() * theMinPt.x()) +
233                   (aPlane.y() < 0.f ? aPlane.y() * theMaxPt.y() : aPlane.y() * theMinPt.y()) +
234                   (aPlane.z() < 0.f ? aPlane.z() * theMaxPt.z() : aPlane.z() * theMinPt.z());
235     if (aBoxProjMin > myMaxClipProjectionPts[aPlaneIter]
236      || aBoxProjMax < myMinClipProjectionPts[aPlaneIter])
237     {
238       return Standard_False;
239     }
240   }
241
242   return Standard_True;
243 }