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