src/SelectMgr/SelectMgr_RectangularFrustum.cxx

   1 // Created on: 2014-05-22
   2 // Created by: Varvara POSKONINA
   3 // Copyright (c) 2005-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 <NCollection_Vector.hxx>
  17 #include <Poly_Array1OfTriangle.hxx>
  18
  19 #include <SelectMgr_RectangularFrustum.hxx>
  20
  21 // =======================================================================
  22 // function : segmentSegmentDistance
  23 // purpose  :
  24 // =======================================================================
  25 void SelectMgr_RectangularFrustum::segmentSegmentDistance (const gp_Pnt& theSegPnt1,
  26                                                            const gp_Pnt& theSegPnt2,
  27                                                            SelectBasics_PickResult& thePickResult) const
  28 {
  29   gp_XYZ anU = theSegPnt2.XYZ() - theSegPnt1.XYZ();
  30   gp_XYZ aV = myViewRayDir.XYZ();
  31   gp_XYZ aW = theSegPnt1.XYZ() - myNearPickedPnt.XYZ();
  32
  33   Standard_Real anA = anU.Dot (anU);
  34   Standard_Real aB = anU.Dot (aV);
  35   Standard_Real aC = aV.Dot (aV);
  36   Standard_Real aD = anU.Dot (aW);
  37   Standard_Real anE = aV.Dot (aW);
  38   Standard_Real aCoef = anA * aC - aB * aB;
  39   Standard_Real aSn = aCoef;
  40   Standard_Real aTc, aTn, aTd = aCoef;
  41
  42   if (aCoef < gp::Resolution())
  43   {
  44     aTn = anE;
  45     aTd = aC;
  46   }
  47   else
  48   {
  49     aSn = (aB * anE - aC * aD);
  50     aTn = (anA * anE - aB * aD);
  51     if (aSn < 0.0)
  52     {
  53       aTn = anE;
  54       aTd = aC;
  55     }
  56     else if (aSn > aCoef)
  57     {
  58       aTn = anE + aB;
  59       aTd = aC;
  60     }
  61   }
  62
  63   if (aTn < 0.0)
  64   {
  65     aTn = 0.0;
  66   }
  67   else if (aTn > aTd)
  68   {
  69     aTn = aTd;
  70   }
  71   aTc = (Abs (aTd) < gp::Resolution() ? 0.0 : aTn / aTd);
  72
  73   const gp_Pnt aClosestPnt = myNearPickedPnt.XYZ() + myViewRayDir.XYZ() * aTc;
  74   thePickResult.SetDepth (myNearPickedPnt.Distance (aClosestPnt) * myScale);
  75
  76   const gp_Vec aPickedVec = aClosestPnt.XYZ() - theSegPnt1.XYZ();
  77   const gp_Vec aFigureVec = theSegPnt2.XYZ()  - theSegPnt1.XYZ();
  78   const Standard_Real aPickedVecMod = aPickedVec.Magnitude();
  79   const Standard_Real aFigureVecMod = aFigureVec.Magnitude();
  80   if (aPickedVecMod <= gp::Resolution()
  81    || aFigureVecMod <= gp::Resolution())
  82   {
  83     thePickResult.SetPickedPoint (aClosestPnt);
  84     return;
  85   }
  86
  87   const Standard_Real aCosOfAngle = aFigureVec.Dot (aPickedVec) / (aPickedVecMod * aFigureVecMod);
  88   const Standard_Real aSegPntShift = Min(aFigureVecMod, Max(0.0, aCosOfAngle * aPickedVecMod));
  89   thePickResult.SetPickedPoint (theSegPnt1.XYZ() + aFigureVec.XYZ() * (aSegPntShift / aFigureVecMod));
  90 }
  91
  92 // =======================================================================
  93 // function : segmentPlaneIntersection
  94 // purpose  :
  95 // =======================================================================
  96 bool SelectMgr_RectangularFrustum::segmentPlaneIntersection (const gp_Vec& thePlane,
  97                                                              const gp_Pnt& thePntOnPlane,
  98                                                              SelectBasics_PickResult& thePickResult) const
  99 {
 100   gp_XYZ anU = myViewRayDir.XYZ();
 101   gp_XYZ aW = myNearPickedPnt.XYZ() - thePntOnPlane.XYZ();
 102   Standard_Real aD = thePlane.Dot (anU);
 103   Standard_Real aN = -thePlane.Dot (aW);
 104
 105   if (Abs (aD) < Precision::Confusion())
 106   {
 107     if (Abs (aN) < Precision::Angular())
 108     {
 109       thePickResult.Invalidate();
 110       return false;
 111     }
 112     else
 113     {
 114       thePickResult.Invalidate();
 115       return false;
 116     }
 117   }
 118
 119   Standard_Real aParam = aN / aD;
 120   if (aParam < 0.0 || aParam > 1.0)
 121   {
 122     thePickResult.Invalidate();
 123     return false;
 124   }
 125
 126   gp_Pnt aClosestPnt = myNearPickedPnt.XYZ() + anU * aParam;
 127   thePickResult.SetDepth (myNearPickedPnt.Distance (aClosestPnt) * myScale);
 128   return true;
 129 }
 130
 131 namespace
 132 {
 133   // =======================================================================
 134   // function : computeFrustum
 135   // purpose  : Computes base frustum data: its vertices and edge directions
 136   // =======================================================================
 137   void computeFrustum (const gp_Pnt2d theMinPnt, const gp_Pnt2d& theMaxPnt,
 138                        const Handle(SelectMgr_FrustumBuilder)& theBuilder,
 139                        gp_Pnt* theVertices, gp_Vec* theEdges)
 140   {
 141     // LeftTopNear
 142     theVertices[0] = theBuilder->ProjectPntOnViewPlane (theMinPnt.X(),
 143                                                         theMaxPnt.Y(),
 144                                                         0.0);
 145     // LeftTopFar
 146     theVertices[1] = theBuilder->ProjectPntOnViewPlane (theMinPnt.X(),
 147                                                         theMaxPnt.Y(),
 148                                                         1.0);
 149     // LeftBottomNear
 150     theVertices[2] = theBuilder->ProjectPntOnViewPlane (theMinPnt.X(),
 151                                                         theMinPnt.Y(),
 152                                                         0.0);
 153     // LeftBottomFar
 154     theVertices[3] = theBuilder->ProjectPntOnViewPlane (theMinPnt.X(),
 155                                                         theMinPnt.Y(),
 156                                                         1.0);
 157     // RightTopNear
 158     theVertices[4] = theBuilder->ProjectPntOnViewPlane (theMaxPnt.X(),
 159                                                         theMaxPnt.Y(),
 160                                                         0.0);
 161     // RightTopFar
 162     theVertices[5] = theBuilder->ProjectPntOnViewPlane (theMaxPnt.X(),
 163                                                         theMaxPnt.Y(),
 164                                                         1.0);
 165     // RightBottomNear
 166     theVertices[6] = theBuilder->ProjectPntOnViewPlane (theMaxPnt.X(),
 167                                                         theMinPnt.Y(),
 168                                                         0.0);
 169     // RightBottomFar
 170     theVertices[7] = theBuilder->ProjectPntOnViewPlane (theMaxPnt.X(),
 171                                                         theMinPnt.Y(),
 172                                                         1.0);
 173
 174     // Horizontal
 175     theEdges[0] = theVertices[4].XYZ() - theVertices[0].XYZ();
 176     // Vertical
 177     theEdges[1] = theVertices[2].XYZ() - theVertices[0].XYZ();
 178     // LeftLower
 179     theEdges[2] = theVertices[2].XYZ() - theVertices[3].XYZ();
 180     // RightLower
 181     theEdges[3] = theVertices[6].XYZ() - theVertices[7].XYZ();
 182     // LeftUpper
 183     theEdges[4] = theVertices[0].XYZ() - theVertices[1].XYZ();
 184     // RightUpper
 185     theEdges[5] = theVertices[4].XYZ() - theVertices[5].XYZ();
 186   }
 187
 188   // =======================================================================
 189   // function : computeNormals
 190   // purpose  : Computes normals to frustum faces
 191   // =======================================================================
 192   void computeNormals (const gp_Vec* theEdges, gp_Vec* theNormals)
 193   {
 194     // Top
 195     theNormals[0] = theEdges[0].Crossed (theEdges[4]);
 196     // Bottom
 197     theNormals[1] = theEdges[2].Crossed (theEdges[0]);
 198     // Left
 199     theNormals[2] = theEdges[4].Crossed (theEdges[1]);
 200     // Right
 201     theNormals[3] = theEdges[1].Crossed (theEdges[5]);
 202     // Near
 203     theNormals[4] = theEdges[0].Crossed (theEdges[1]);
 204     // Far
 205     theNormals[5] = -theNormals[4];
 206   }
 207
 208   // =======================================================================
 209   // function : rayBoxIntersection
 210   // purpose  : Computes an intersection of ray with box
 211   //            Returns distances to the first (or 0.0 if the ray origin is inside the box) and second intersection
 212   //            If the ray has no intersection with the box returns DBL_MAX
 213   // =======================================================================
 214   Bnd_Range rayBoxIntersection (const gp_Ax1& theRay, const gp_Pnt& theBoxMin, const gp_Pnt& theBoxMax)
 215   {
 216     Standard_Real aTimeMinX = -DBL_MAX;
 217     Standard_Real aTimeMinY = -DBL_MAX;
 218     Standard_Real aTimeMinZ = -DBL_MAX;
 219     Standard_Real aTimeMaxX = DBL_MAX;
 220     Standard_Real aTimeMaxY = DBL_MAX;
 221     Standard_Real aTimeMaxZ = DBL_MAX;
 222
 223     Standard_Real aTime1;
 224     Standard_Real aTime2;
 225
 226     if (Abs (theRay.Direction().X()) > DBL_EPSILON)
 227     {
 228       aTime1 = (theBoxMin.X() - theRay.Location().X()) / theRay.Direction().X();
 229       aTime2 = (theBoxMax.X() - theRay.Location().X()) / theRay.Direction().X();
 230
 231       aTimeMinX = Min (aTime1, aTime2);
 232       aTimeMaxX = Max (aTime1, aTime2);
 233     }
 234     if (Abs (theRay.Direction().Y()) > DBL_EPSILON)
 235     {
 236       aTime1 = (theBoxMin.Y() - theRay.Location().Y()) / theRay.Direction().Y();
 237       aTime2 = (theBoxMax.Y() - theRay.Location().Y()) / theRay.Direction().Y();
 238
 239       aTimeMinY = Min (aTime1, aTime2);
 240       aTimeMaxY = Max (aTime1, aTime2);
 241     }
 242     if (Abs (theRay.Direction().Z()) > DBL_EPSILON)
 243     {
 244       aTime1 = (theBoxMin.Z() - theRay.Location().Z()) / theRay.Direction().Z();
 245       aTime2 = (theBoxMax.Z() - theRay.Location().Z()) / theRay.Direction().Z();
 246
 247       aTimeMinZ = Min (aTime1, aTime2);
 248       aTimeMaxZ = Max (aTime1, aTime2);
 249     }
 250
 251     Standard_Real aTimeMin = Max (aTimeMinX, Max (aTimeMinY, aTimeMinZ));
 252     Standard_Real aTimeMax = Min (aTimeMaxX, Min (aTimeMaxY, aTimeMaxZ));
 253
 254     return aTimeMin > aTimeMax || aTimeMax < 0.0 ? Bnd_Range (DBL_MAX, DBL_MAX)
 255       : Bnd_Range (Max (aTimeMin, 0.0), aTimeMax);
 256   }
 257 }
 258
 259 // =======================================================================
 260 // function : cacheVertexProjections
 261 // purpose  : Caches projection of frustum's vertices onto its plane directions
 262 //            and {i, j, k}
 263 // =======================================================================
 264 void SelectMgr_RectangularFrustum::cacheVertexProjections (SelectMgr_RectangularFrustum* theFrustum) const
 265 {
 266   if (theFrustum->myIsOrthographic)
 267   {
 268     // project vertices onto frustum normals
 269     // Since orthographic view volume's faces are always a pairwise translation of
 270     // one another, only 2 vertices that belong to opposite faces can be projected
 271     // to simplify calculations.
 272     Standard_Integer aVertIdxs[6] = { LeftTopNear, LeftBottomNear,       // opposite planes in height direction
 273                                       LeftBottomNear, RightBottomNear,   // opposite planes in width direcion
 274                                       LeftBottomFar, RightBottomNear };  // opposite planes in depth direction
 275     for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < 5; aPlaneIdx += 2)
 276     {
 277       Standard_Real aProj1 = theFrustum->myPlanes[aPlaneIdx].XYZ().Dot (theFrustum->myVertices[aVertIdxs[aPlaneIdx]].XYZ());
 278       Standard_Real aProj2 = theFrustum->myPlanes[aPlaneIdx].XYZ().Dot (theFrustum->myVertices[aVertIdxs[aPlaneIdx + 1]].XYZ());
 279       theFrustum->myMinVertsProjections[aPlaneIdx] = Min (aProj1, aProj2);
 280       theFrustum->myMaxVertsProjections[aPlaneIdx] = Max (aProj1, aProj2);
 281     }
 282   }
 283   else
 284   {
 285     // project all vertices onto frustum normals
 286     for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < 6; ++aPlaneIdx)
 287     {
 288       Standard_Real aMax = -DBL_MAX;
 289       Standard_Real aMin = DBL_MAX;
 290       const gp_XYZ& aPlane = theFrustum->myPlanes[aPlaneIdx].XYZ();
 291       for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
 292       {
 293         Standard_Real aProjection = aPlane.Dot (theFrustum->myVertices[aVertIdx].XYZ());
 294         aMin = Min (aMin, aProjection);
 295         aMax = Max (aMax, aProjection);
 296       }
 297       theFrustum->myMinVertsProjections[aPlaneIdx] = aMin;
 298       theFrustum->myMaxVertsProjections[aPlaneIdx] = aMax;
 299     }
 300   }
 301
 302   // project vertices onto {i, j, k}
 303   for (Standard_Integer aDim = 0; aDim < 3; ++aDim)
 304   {
 305     Standard_Real aMax = -DBL_MAX;
 306     Standard_Real aMin = DBL_MAX;
 307     for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
 308     {
 309       const gp_XYZ& aVert = theFrustum->myVertices[aVertIdx].XYZ();
 310       aMax = Max (aVert.GetData()[aDim], aMax);
 311       aMin = Min (aVert.GetData()[aDim], aMin);
 312     }
 313     theFrustum->myMaxOrthoVertsProjections[aDim] = aMax;
 314     theFrustum->myMinOrthoVertsProjections[aDim] = aMin;
 315   }
 316 }
 317
 318 // =======================================================================
 319 // function : Build
 320 // purpose  : Build volume according to the point and given pixel
 321 //            tolerance
 322 // =======================================================================
 323 void SelectMgr_RectangularFrustum::Build (const gp_Pnt2d &thePoint)
 324 {
 325   myNearPickedPnt = myBuilder->ProjectPntOnViewPlane (thePoint.X(), thePoint.Y(), 0.0);
 326   myFarPickedPnt = myBuilder->ProjectPntOnViewPlane (thePoint.X(), thePoint.Y(), 1.0);
 327   myViewRayDir = myFarPickedPnt.XYZ() - myNearPickedPnt.XYZ();
 328   myMousePos = thePoint;
 329
 330   gp_Pnt2d aMinPnt (thePoint.X() - myPixelTolerance * 0.5,
 331                     thePoint.Y() - myPixelTolerance * 0.5);
 332   gp_Pnt2d aMaxPnt (thePoint.X() + myPixelTolerance * 0.5,
 333                     thePoint.Y() + myPixelTolerance * 0.5);
 334
 335   // calculate base frustum characteristics: vertices and edge directions
 336   computeFrustum (aMinPnt, aMaxPnt, myBuilder, myVertices, myEdgeDirs);
 337
 338   // compute frustum normals
 339   computeNormals (myEdgeDirs, myPlanes);
 340
 341   // compute vertices projections onto frustum normals and
 342   // {i, j, k} vectors and store them to corresponding class fields
 343   cacheVertexProjections (this);
 344
 345   myViewClipRange.SetVoid();
 346
 347   myScale = 1.0;
 348 }
 349
 350 // =======================================================================
 351 // function : Build
 352 // purpose  : Build volume according to the selected rectangle
 353 // =======================================================================
 354 void SelectMgr_RectangularFrustum::Build (const gp_Pnt2d& theMinPnt,
 355                                           const gp_Pnt2d& theMaxPnt)
 356 {
 357   myNearPickedPnt = myBuilder->ProjectPntOnViewPlane ((theMinPnt.X() + theMaxPnt.X()) * 0.5,
 358                                                       (theMinPnt.Y() + theMaxPnt.Y()) * 0.5,
 359                                                       0.0);
 360   myFarPickedPnt = myBuilder->ProjectPntOnViewPlane ((theMinPnt.X() + theMaxPnt.X()) * 0.5,
 361                                                      (theMinPnt.Y() + theMaxPnt.Y()) * 0.5,
 362                                                      1.0);
 363   myViewRayDir = myFarPickedPnt.XYZ() - myNearPickedPnt.XYZ();
 364
 365   // calculate base frustum characteristics: vertices and edge directions
 366   computeFrustum (theMinPnt, theMaxPnt, myBuilder, myVertices, myEdgeDirs);
 367
 368   // compute frustum normals
 369   computeNormals (myEdgeDirs, myPlanes);
 370
 371   // compute vertices projections onto frustum normals and
 372   // {i, j, k} vectors and store them to corresponding class fields
 373   cacheVertexProjections (this);
 374
 375   myViewClipRange.SetVoid();
 376
 377   myScale = 1.0;
 378 }
 379
 380 // =======================================================================
 381 // function : ScaleAndTransform
 382 // purpose  : IMPORTANT: Scaling makes sense only for frustum built on a single point!
 383 //            Note that this method does not perform any checks on type of the frustum.
 384 //            Returns a copy of the frustum resized according to the scale factor given
 385 //            and transforms it using the matrix given.
 386 //            There are no default parameters, but in case if:
 387 //                - transformation only is needed: @theScaleFactor must be initialized
 388 //                  as any negative value;
 389 //                - scale only is needed: @theTrsf must be set to gp_Identity.
 390 // =======================================================================
 391 Handle(SelectMgr_BaseFrustum) SelectMgr_RectangularFrustum::ScaleAndTransform (const Standard_Integer theScaleFactor,
 392                                                                                const gp_GTrsf& theTrsf) const
 393 {
 394   Standard_ASSERT_RAISE (theScaleFactor > 0,
 395     "Error! Pixel tolerance for selection should be greater than zero");
 396
 397   Handle(SelectMgr_RectangularFrustum) aRes = new SelectMgr_RectangularFrustum();
 398   const Standard_Boolean isToScale = theScaleFactor != 1;
 399   const Standard_Boolean isToTrsf  = theTrsf.Form() != gp_Identity;
 400
 401   if (!isToScale && !isToTrsf)
 402     return aRes;
 403
 404   aRes->myIsOrthographic = myIsOrthographic;
 405   const SelectMgr_RectangularFrustum* aRef = this;
 406
 407   if (isToScale)
 408   {
 409     aRes->myNearPickedPnt = myNearPickedPnt;
 410     aRes->myFarPickedPnt  = myFarPickedPnt;
 411     aRes->myViewRayDir    = myViewRayDir;
 412
 413     const gp_Pnt2d aMinPnt (myMousePos.X() - theScaleFactor * 0.5,
 414                             myMousePos.Y() - theScaleFactor * 0.5);
 415     const gp_Pnt2d aMaxPnt (myMousePos.X() + theScaleFactor * 0.5,
 416                             myMousePos.Y() + theScaleFactor * 0.5);
 417
 418     // recompute base frustum characteristics from scratch
 419     computeFrustum (aMinPnt, aMaxPnt, myBuilder, aRes->myVertices, aRes->myEdgeDirs);
 420
 421     aRef = aRes.get();
 422   }
 423
 424   if (isToTrsf)
 425   {
 426     const Standard_Real aRefScale = aRef->myFarPickedPnt.SquareDistance (aRef->myNearPickedPnt);
 427
 428     gp_Pnt aPoint = aRef->myNearPickedPnt;
 429     theTrsf.Transforms (aPoint.ChangeCoord());
 430     aRes->myNearPickedPnt = aPoint;
 431
 432     aPoint.SetXYZ (aRef->myFarPickedPnt.XYZ());
 433     theTrsf.Transforms (aPoint.ChangeCoord());
 434     aRes->myFarPickedPnt = aPoint;
 435
 436     aRes->myViewRayDir    = aRes->myFarPickedPnt.XYZ() - aRes->myNearPickedPnt.XYZ();
 437
 438     for (Standard_Integer anIt = 0; anIt < 8; anIt++)
 439     {
 440       aPoint = aRef->myVertices[anIt];
 441       theTrsf.Transforms (aPoint.ChangeCoord());
 442       aRes->myVertices[anIt] = aPoint;
 443     }
 444
 445     // Horizontal
 446     aRes->myEdgeDirs[0] = aRes->myVertices[4].XYZ() - aRes->myVertices[0].XYZ();
 447     // Vertical
 448     aRes->myEdgeDirs[1] = aRes->myVertices[2].XYZ() - aRes->myVertices[0].XYZ();
 449     // LeftLower
 450     aRes->myEdgeDirs[2] = aRes->myVertices[2].XYZ() - aRes->myVertices[3].XYZ();
 451     // RightLower
 452     aRes->myEdgeDirs[3] = aRes->myVertices[6].XYZ() - aRes->myVertices[7].XYZ();
 453     // LeftUpper
 454     aRes->myEdgeDirs[4] = aRes->myVertices[0].XYZ() - aRes->myVertices[1].XYZ();
 455     // RightUpper
 456     aRes->myEdgeDirs[5] = aRes->myVertices[4].XYZ() - aRes->myVertices[5].XYZ();
 457
 458     // Compute scale to transform depth from local coordinate system to world coordinate system
 459     aRes->myScale = Sqrt (aRefScale / aRes->myFarPickedPnt.SquareDistance (aRes->myNearPickedPnt));
 460   }
 461
 462   // compute frustum normals
 463   computeNormals (aRes->myEdgeDirs, aRes->myPlanes);
 464
 465   cacheVertexProjections (aRes.get());
 466
 467   aRes->myViewClipRange = myViewClipRange;
 468   aRes->myMousePos      = myMousePos;
 469
 470   return aRes;
 471 }
 472
 473 // =======================================================================
 474 // function : Overlaps
 475 // purpose  : Returns true if selecting volume is overlapped by
 476 //            axis-aligned bounding box with minimum corner at point
 477 //            theMinPnt and maximum at point theMaxPnt
 478 // =======================================================================
 479 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const SelectMgr_Vec3& theBoxMin,
 480                                                          const SelectMgr_Vec3& theBoxMax,
 481                                                          Standard_Boolean*     theInside) const
 482 {
 483   return hasOverlap (theBoxMin, theBoxMax, theInside);
 484 }
 485
 486 // =======================================================================
 487 // function : Overlaps
 488 // purpose  : SAT intersection test between defined volume and
 489 //            given axis-aligned box
 490 // =======================================================================
 491 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const SelectMgr_Vec3& theBoxMin,
 492                                                          const SelectMgr_Vec3& theBoxMax,
 493                                                          SelectBasics_PickResult& thePickResult) const
 494 {
 495   if (!hasOverlap (theBoxMin, theBoxMax))
 496     return Standard_False;
 497
 498   gp_Ax1 aRay (myNearPickedPnt, myViewRayDir);
 499   Bnd_Range aRange = rayBoxIntersection (aRay,
 500                                          gp_Pnt (theBoxMin.x(), theBoxMin.y(), theBoxMin.z()),
 501                                          gp_Pnt (theBoxMax.x(), theBoxMax.y(), theBoxMax.z()));
 502
 503   Standard_Real aDepth = 0.0;
 504   aRange.GetMin (aDepth);
 505
 506   if (aDepth == DBL_MAX)
 507   {
 508     gp_Pnt aNearestPnt (RealLast(), RealLast(), RealLast());
 509     aNearestPnt.SetX (Max (Min (myNearPickedPnt.X(), theBoxMax.x()), theBoxMin.x()));
 510     aNearestPnt.SetY (Max (Min (myNearPickedPnt.Y(), theBoxMax.y()), theBoxMin.y()));
 511     aNearestPnt.SetZ (Max (Min (myNearPickedPnt.Z(), theBoxMax.z()), theBoxMin.z()));
 512
 513     aDepth = aNearestPnt.Distance (myNearPickedPnt);
 514     thePickResult.SetDepth (aDepth);
 515     return isViewClippingOk (thePickResult);
 516   }
 517
 518   if (!myViewClipRange.GetNearestDepth (aRange, aDepth))
 519   {
 520     return Standard_False;
 521   }
 522
 523   thePickResult.SetDepth (aDepth);
 524
 525   return Standard_True;
 526 }
 527
 528 // =======================================================================
 529 // function : Overlaps
 530 // purpose  : Intersection test between defined volume and given point
 531 // =======================================================================
 532 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt,
 533                                                          SelectBasics_PickResult& thePickResult) const
 534 {
 535   if (!hasOverlap (thePnt))
 536     return Standard_False;
 537
 538   gp_XYZ aV = thePnt.XYZ() - myNearPickedPnt.XYZ();
 539   gp_Pnt aDetectedPnt =
 540     myNearPickedPnt.XYZ() + myViewRayDir.XYZ() * (aV.Dot (myViewRayDir.XYZ()) / myViewRayDir.Dot (myViewRayDir));
 541
 542   thePickResult.SetDepth (aDetectedPnt.Distance (myNearPickedPnt) * myScale);
 543   thePickResult.SetPickedPoint (thePnt);
 544
 545   return isViewClippingOk (thePickResult);
 546 }
 547
 548 // =======================================================================
 549 // function : Overlaps
 550 // purpose  : Intersection test between defined volume and given point
 551 // =======================================================================
 552 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt) const
 553 {
 554   return hasOverlap (thePnt);
 555 }
 556
 557 // =======================================================================
 558 // function : Overlaps
 559 // purpose  : Checks if line segment overlaps selecting frustum
 560 // =======================================================================
 561 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt1,
 562                                                          const gp_Pnt& thePnt2,
 563                                                          SelectBasics_PickResult& thePickResult) const
 564 {
 565   if (!hasOverlap (thePnt1, thePnt2))
 566     return Standard_False;
 567
 568   segmentSegmentDistance (thePnt1, thePnt2, thePickResult);
 569
 570   return isViewClippingOk (thePickResult);
 571 }
 572
 573 // =======================================================================
 574 // function : Overlaps
 575 // purpose  : SAT intersection test between defined volume and given
 576 //            ordered set of points, representing line segments. The test
 577 //            may be considered of interior part or boundary line defined
 578 //            by segments depending on given sensitivity type
 579 // =======================================================================
 580 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const TColgp_Array1OfPnt& theArrayOfPnts,
 581                                                          Select3D_TypeOfSensitivity theSensType,
 582                                                          SelectBasics_PickResult& thePickResult) const
 583 {
 584   if (theSensType == Select3D_TOS_BOUNDARY)
 585   {
 586     Standard_Integer aMatchingSegmentsNb = -1;
 587     SelectBasics_PickResult aPickResult;
 588     thePickResult.Invalidate();
 589     const Standard_Integer aLower  = theArrayOfPnts.Lower();
 590     const Standard_Integer anUpper = theArrayOfPnts.Upper();
 591     for (Standard_Integer aPntIter = aLower; aPntIter <= anUpper; ++aPntIter)
 592     {
 593       const gp_Pnt& aStartPnt = theArrayOfPnts.Value (aPntIter);
 594       const gp_Pnt& aEndPnt   = theArrayOfPnts.Value (aPntIter == anUpper ? aLower : (aPntIter + 1));
 595       if (hasOverlap (aStartPnt, aEndPnt))
 596       {
 597         aMatchingSegmentsNb++;
 598         segmentSegmentDistance (aStartPnt, aEndPnt, aPickResult);
 599         thePickResult = SelectBasics_PickResult::Min (thePickResult, aPickResult);
 600       }
 601     }
 602
 603     if (aMatchingSegmentsNb == -1)
 604       return Standard_False;
 605   }
 606   else if (theSensType == Select3D_TOS_INTERIOR)
 607   {
 608     gp_Vec aPolyNorm (gp_XYZ (RealLast(), RealLast(), RealLast()));
 609     if (!hasOverlap (theArrayOfPnts, aPolyNorm))
 610     {
 611       return Standard_False;
 612     }
 613
 614     if (aPolyNorm.Magnitude() <= Precision::Confusion())
 615     {
 616       // treat degenerated polygon as point
 617       return Overlaps (theArrayOfPnts.First(), thePickResult);
 618     }
 619     else if (!segmentPlaneIntersection (aPolyNorm, theArrayOfPnts.First(), thePickResult))
 620     {
 621       return Standard_False;
 622     }
 623   }
 624
 625   return isViewClippingOk (thePickResult);
 626 }
 627
 628 // =======================================================================
 629 // function : Overlaps
 630 // purpose  : SAT intersection test between defined volume and given
 631 //            triangle. The test may be considered of interior part or
 632 //            boundary line defined by triangle vertices depending on
 633 //            given sensitivity type
 634 // =======================================================================
 635 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt1,
 636                                                          const gp_Pnt& thePnt2,
 637                                                          const gp_Pnt& thePnt3,
 638                                                          Select3D_TypeOfSensitivity theSensType,
 639                                                          SelectBasics_PickResult& thePickResult) const
 640 {
 641   if (theSensType == Select3D_TOS_BOUNDARY)
 642   {
 643     const gp_Pnt aPntsArrayBuf[4] = { thePnt1, thePnt2, thePnt3, thePnt1 };
 644     const TColgp_Array1OfPnt aPntsArray (aPntsArrayBuf[0], 1, 4);
 645     return Overlaps (aPntsArray, Select3D_TOS_BOUNDARY, thePickResult);
 646   }
 647   else if (theSensType == Select3D_TOS_INTERIOR)
 648   {
 649     gp_Vec aTriangleNormal (gp_XYZ (RealLast(), RealLast(), RealLast()));
 650     if (!hasOverlap (thePnt1, thePnt2, thePnt3, aTriangleNormal))
 651       return Standard_False;
 652
 653     // check if intersection point belongs to triangle's interior part
 654     gp_XYZ aTrEdges[3] = { thePnt2.XYZ() - thePnt1.XYZ(),
 655                            thePnt3.XYZ() - thePnt2.XYZ(),
 656                            thePnt1.XYZ() - thePnt3.XYZ() };
 657
 658     Standard_Real anAlpha = aTriangleNormal.Dot (myViewRayDir);
 659     if (Abs (anAlpha) < gp::Resolution())
 660     {
 661       // handle degenerated triangles: in this case, there is no possible way to detect overlap correctly.
 662       if (aTriangleNormal.SquareMagnitude() < gp::Resolution())
 663       {
 664         return Standard_False;
 665       }
 666
 667       // handle the case when triangle normal and selecting frustum direction are orthogonal: for this case, overlap
 668       // is detected correctly, and distance to triangle's plane can be measured as distance to its arbitrary vertex.
 669       const gp_XYZ aDiff = myNearPickedPnt.XYZ() - thePnt1.XYZ();
 670       thePickResult.SetDepth (aTriangleNormal.Dot (aDiff) * myScale);
 671       thePickResult.SetPickedPoint (thePnt1);
 672       return isViewClippingOk (thePickResult);
 673     }
 674
 675     gp_XYZ anEdge = (thePnt1.XYZ() - myNearPickedPnt.XYZ()) * (1.0 / anAlpha);
 676
 677     Standard_Real aTime = aTriangleNormal.Dot (anEdge);
 678
 679     gp_XYZ aVec = myViewRayDir.XYZ().Crossed (anEdge);
 680
 681     Standard_Real anU = aVec.Dot (aTrEdges[2]);
 682     Standard_Real aV  = aVec.Dot (aTrEdges[0]);
 683
 684     const Standard_Boolean isInterior = (aTime >= 0.0) && (anU >= 0.0) && (aV >= 0.0) && (anU + aV <= 1.0);
 685     const gp_Pnt aPtOnPlane = myNearPickedPnt.XYZ() + myViewRayDir.XYZ() * aTime;
 686     if (isInterior)
 687     {
 688       thePickResult.SetDepth (myNearPickedPnt.Distance (aPtOnPlane) * myScale);
 689       thePickResult.SetPickedPoint (aPtOnPlane);
 690       return isViewClippingOk (thePickResult);
 691     }
 692
 693     gp_Pnt aPnts[3] = {thePnt1, thePnt2, thePnt3};
 694     Standard_Real aMinDist = RealLast();
 695     Standard_Integer aNearestEdgeIdx = -1;
 696     for (Standard_Integer anEdgeIdx = 0; anEdgeIdx < 3; ++anEdgeIdx)
 697     {
 698       gp_XYZ aW = aPtOnPlane.XYZ() - aPnts[anEdgeIdx].XYZ();
 699       Standard_Real aCoef = aTrEdges[anEdgeIdx].Dot (aW) / aTrEdges[anEdgeIdx].Dot (aTrEdges[anEdgeIdx]);
 700       Standard_Real aDist = aPtOnPlane.Distance (aPnts[anEdgeIdx].XYZ() + aCoef * aTrEdges[anEdgeIdx]);
 701       if (aMinDist > aDist)
 702       {
 703         aMinDist = aDist;
 704         aNearestEdgeIdx = anEdgeIdx;
 705       }
 706     }
 707     segmentSegmentDistance (aPnts[aNearestEdgeIdx], aPnts[(aNearestEdgeIdx + 1) % 3], thePickResult);
 708   }
 709
 710   return isViewClippingOk (thePickResult);
 711 }
 712
 713 // =======================================================================
 714 // function : DistToGeometryCenter
 715 // purpose  : Measures distance between 3d projection of user-picked
 716 //            screen point and given point theCOG
 717 // =======================================================================
 718 Standard_Real SelectMgr_RectangularFrustum::DistToGeometryCenter (const gp_Pnt& theCOG) const
 719 {
 720   return theCOG.Distance (myNearPickedPnt) * myScale;
 721 }
 722
 723 // =======================================================================
 724 // function : DetectedPoint
 725 // purpose  : Calculates the point on a view ray that was detected during
 726 //            the run of selection algo by given depth
 727 // =======================================================================
 728 gp_Pnt SelectMgr_RectangularFrustum::DetectedPoint (const Standard_Real theDepth) const
 729 {
 730   return myNearPickedPnt.XYZ() + myViewRayDir.Normalized().XYZ() * theDepth / myScale;
 731 }
 732
 733 // =======================================================================
 734 // function : computeClippingRange
 735 // purpose  :
 736 // =======================================================================
 737 void SelectMgr_RectangularFrustum::computeClippingRange (const Graphic3d_SequenceOfHClipPlane& thePlanes,
 738                                                          SelectMgr_ViewClipRange& theRange) const
 739 {
 740   Standard_Real aPlaneA, aPlaneB, aPlaneC, aPlaneD;
 741   for (Graphic3d_SequenceOfHClipPlane::Iterator aPlaneIt (thePlanes); aPlaneIt.More(); aPlaneIt.Next())
 742   {
 743     const Handle(Graphic3d_ClipPlane)& aClipPlane = aPlaneIt.Value();
 744     if (!aClipPlane->IsOn())
 745     {
 746       continue;
 747     }
 748
 749     Bnd_Range aSubRange (RealFirst(), RealLast());
 750     for (const Graphic3d_ClipPlane* aSubPlaneIter = aClipPlane.get(); aSubPlaneIter != NULL; aSubPlaneIter = aSubPlaneIter->ChainNextPlane().get())
 751     {
 752       const gp_Pln aGeomPlane = aSubPlaneIter->ToPlane();
 753       aGeomPlane.Coefficients (aPlaneA, aPlaneB, aPlaneC, aPlaneD);
 754
 755       const gp_XYZ& aPlaneDirXYZ = aGeomPlane.Axis().Direction().XYZ();
 756       Standard_Real aDotProduct = myViewRayDir.XYZ().Dot (aPlaneDirXYZ);
 757       Standard_Real aDistance   = -myNearPickedPnt.XYZ().Dot (aPlaneDirXYZ) - aPlaneD;
 758       Standard_Real aDistToPln  = 0.0;
 759
 760       // check whether the pick line is parallel to clip plane
 761       if (Abs (aDotProduct) < Precision::Angular())
 762       {
 763         if (aDistance < 0.0)
 764         {
 765           continue;
 766         }
 767         aDistToPln  = RealLast();
 768         aDotProduct = 1.0;
 769       }
 770       else
 771       {
 772         // compute distance to point of pick line intersection with the plane
 773         const Standard_Real aParam = aDistance / aDotProduct;
 774
 775         const gp_Pnt anIntersectionPnt = myNearPickedPnt.XYZ() + myViewRayDir.XYZ() * aParam;
 776         aDistToPln = anIntersectionPnt.Distance (myNearPickedPnt);
 777         if (aParam < 0.0)
 778         {
 779           // the plane is "behind" the ray
 780           aDistToPln = -aDistToPln;
 781         }
 782       }
 783
 784       // change depth limits for case of opposite and directed planes
 785       if (!aClipPlane->IsChain())
 786       {
 787         if (aDotProduct < 0.0)
 788         {
 789           theRange.ChangeUnclipRange().TrimTo (aDistToPln);
 790         }
 791         else
 792         {
 793           theRange.ChangeUnclipRange().TrimFrom (aDistToPln);
 794         }
 795       }
 796       else
 797       {
 798         if (aDotProduct < 0.0)
 799         {
 800           aSubRange.TrimFrom (aDistToPln);
 801         }
 802         else
 803         {
 804           aSubRange.TrimTo (aDistToPln);
 805         }
 806       }
 807     }
 808
 809     if (!aSubRange.IsVoid()
 810       && aClipPlane->IsChain())
 811     {
 812       theRange.AddClipSubRange (aSubRange);
 813     }
 814   }
 815 }
 816
 817 // =======================================================================
 818 // function : SetViewClipping
 819 // purpose  :
 820 // =======================================================================
 821 void SelectMgr_RectangularFrustum::SetViewClipping (const Handle(Graphic3d_SequenceOfHClipPlane)& theViewPlanes,
 822                                                     const Handle(Graphic3d_SequenceOfHClipPlane)& theObjPlanes)
 823 {
 824   myViewClipRange.SetVoid();
 825   if (!theViewPlanes.IsNull()
 826    && !theViewPlanes->IsEmpty())
 827   {
 828     computeClippingRange (*theViewPlanes, myViewClipRange);
 829   }
 830   if (!theObjPlanes.IsNull()
 831    && !theObjPlanes->IsEmpty())
 832   {
 833     computeClippingRange (*theObjPlanes, myViewClipRange);
 834   }
 835 }
 836
 837 // =======================================================================
 838 // function : isViewClippingOk
 839 // purpose  :
 840 // =======================================================================
 841 Standard_Boolean SelectMgr_RectangularFrustum::isViewClippingOk (const SelectBasics_PickResult& thePickResult) const
 842 {
 843   return !myViewClipRange.IsClipped (thePickResult.Depth());
 844 }
 845
 846 // =======================================================================
 847 // function : GetPlanes
 848 // purpose  :
 849 // =======================================================================
 850 void SelectMgr_RectangularFrustum::GetPlanes (NCollection_Vector<SelectMgr_Vec4>& thePlaneEquations) const
 851 {
 852   thePlaneEquations.Clear();
 853
 854   SelectMgr_Vec4 anEquation;
 855   for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < 6; ++aPlaneIdx)
 856   {
 857     const gp_Vec& aPlaneNorm = myIsOrthographic && aPlaneIdx % 2 == 1 ?
 858       myPlanes[aPlaneIdx - 1].Reversed() : myPlanes[aPlaneIdx];
 859     anEquation.x() = aPlaneNorm.X();
 860     anEquation.y() = aPlaneNorm.Y();
 861     anEquation.z() = aPlaneNorm.Z();
 862     anEquation.w() = - (aPlaneNorm.XYZ().Dot (myVertices[aPlaneIdx % 2 == 0 ? aPlaneIdx : aPlaneIdx + 2].XYZ()));
 863     thePlaneEquations.Append (anEquation);
 864   }
 865 }