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