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)
  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)
  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 // =======================================================================
 210 // function : cacheVertexProjections
 211 // purpose  : Caches projection of frustum's vertices onto its plane directions
 212 //            and {i, j, k}
 213 // =======================================================================
 214 void SelectMgr_RectangularFrustum::cacheVertexProjections (SelectMgr_RectangularFrustum* theFrustum) const
 215 {
 216   if (theFrustum->myIsOrthographic)
 217   {
 218     // project vertices onto frustum normals
 219     // Since orthographic view volume's faces are always a pairwise translation of
 220     // one another, only 2 vertices that belong to opposite faces can be projected
 221     // to simplify calculations.
 222     Standard_Integer aVertIdxs[6] = { LeftTopNear, LeftBottomNear,       // opposite planes in height direction
 223                                       LeftBottomNear, RightBottomNear,   // opposite planes in width direcion
 224                                       LeftBottomFar, RightBottomNear };  // opposite planes in depth direction
 225     for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < 5; aPlaneIdx += 2)
 226     {
 227       Standard_Real aProj1 = theFrustum->myPlanes[aPlaneIdx].XYZ().Dot (theFrustum->myVertices[aVertIdxs[aPlaneIdx]].XYZ());
 228       Standard_Real aProj2 = theFrustum->myPlanes[aPlaneIdx].XYZ().Dot (theFrustum->myVertices[aVertIdxs[aPlaneIdx + 1]].XYZ());
 229       theFrustum->myMinVertsProjections[aPlaneIdx] = Min (aProj1, aProj2);
 230       theFrustum->myMaxVertsProjections[aPlaneIdx] = Max (aProj1, aProj2);
 231     }
 232   }
 233   else
 234   {
 235     // project all vertices onto frustum normals
 236     for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < 6; ++aPlaneIdx)
 237     {
 238       Standard_Real aMax = -DBL_MAX;
 239       Standard_Real aMin = DBL_MAX;
 240       const gp_XYZ& aPlane = theFrustum->myPlanes[aPlaneIdx].XYZ();
 241       for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
 242       {
 243         Standard_Real aProjection = aPlane.Dot (theFrustum->myVertices[aVertIdx].XYZ());
 244         aMin = Min (aMin, aProjection);
 245         aMax = Max (aMax, aProjection);
 246       }
 247       theFrustum->myMinVertsProjections[aPlaneIdx] = aMin;
 248       theFrustum->myMaxVertsProjections[aPlaneIdx] = aMax;
 249     }
 250   }
 251
 252   // project vertices onto {i, j, k}
 253   for (Standard_Integer aDim = 0; aDim < 3; ++aDim)
 254   {
 255     Standard_Real aMax = -DBL_MAX;
 256     Standard_Real aMin = DBL_MAX;
 257     for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
 258     {
 259       const gp_XYZ& aVert = theFrustum->myVertices[aVertIdx].XYZ();
 260       aMax = Max (aVert.GetData()[aDim], aMax);
 261       aMin = Min (aVert.GetData()[aDim], aMin);
 262     }
 263     theFrustum->myMaxOrthoVertsProjections[aDim] = aMax;
 264     theFrustum->myMinOrthoVertsProjections[aDim] = aMin;
 265   }
 266 }
 267
 268 // =======================================================================
 269 // function : Build
 270 // purpose  : Build volume according to the point and given pixel
 271 //            tolerance
 272 // =======================================================================
 273 void SelectMgr_RectangularFrustum::Build (const gp_Pnt2d &thePoint)
 274 {
 275   myNearPickedPnt = myBuilder->ProjectPntOnViewPlane (thePoint.X(), thePoint.Y(), 0.0);
 276   myFarPickedPnt = myBuilder->ProjectPntOnViewPlane (thePoint.X(), thePoint.Y(), 1.0);
 277   myViewRayDir = myFarPickedPnt.XYZ() - myNearPickedPnt.XYZ();
 278   myMousePos = thePoint;
 279
 280   gp_Pnt2d aMinPnt (thePoint.X() - myPixelTolerance * 0.5,
 281                     thePoint.Y() - myPixelTolerance * 0.5);
 282   gp_Pnt2d aMaxPnt (thePoint.X() + myPixelTolerance * 0.5,
 283                     thePoint.Y() + myPixelTolerance * 0.5);
 284
 285   // calculate base frustum characteristics: vertices and edge directions
 286   computeFrustum (aMinPnt, aMaxPnt, myBuilder, myVertices, myEdgeDirs);
 287
 288   // compute frustum normals
 289   computeNormals (myEdgeDirs, myPlanes);
 290
 291   // compute vertices projections onto frustum normals and
 292   // {i, j, k} vectors and store them to corresponding class fields
 293   cacheVertexProjections (this);
 294
 295   myViewClipRange.SetVoid();
 296
 297   myScale = 1.0;
 298 }
 299
 300 // =======================================================================
 301 // function : Build
 302 // purpose  : Build volume according to the selected rectangle
 303 // =======================================================================
 304 void SelectMgr_RectangularFrustum::Build (const gp_Pnt2d& theMinPnt,
 305                                           const gp_Pnt2d& theMaxPnt)
 306 {
 307   myNearPickedPnt = myBuilder->ProjectPntOnViewPlane ((theMinPnt.X() + theMaxPnt.X()) * 0.5,
 308                                                       (theMinPnt.Y() + theMaxPnt.Y()) * 0.5,
 309                                                       0.0);
 310   myFarPickedPnt = myBuilder->ProjectPntOnViewPlane ((theMinPnt.X() + theMaxPnt.X()) * 0.5,
 311                                                      (theMinPnt.Y() + theMaxPnt.Y()) * 0.5,
 312                                                      1.0);
 313   myViewRayDir = myFarPickedPnt.XYZ() - myNearPickedPnt.XYZ();
 314
 315   // calculate base frustum characteristics: vertices and edge directions
 316   computeFrustum (theMinPnt, theMaxPnt, myBuilder, myVertices, myEdgeDirs);
 317
 318   // compute frustum normals
 319   computeNormals (myEdgeDirs, myPlanes);
 320
 321   // compute vertices projections onto frustum normals and
 322   // {i, j, k} vectors and store them to corresponding class fields
 323   cacheVertexProjections (this);
 324
 325   myViewClipRange.SetVoid();
 326
 327   myScale = 1.0;
 328 }
 329
 330 // =======================================================================
 331 // function : ScaleAndTransform
 332 // purpose  : IMPORTANT: Scaling makes sense only for frustum built on a single point!
 333 //            Note that this method does not perform any checks on type of the frustum.
 334 //            Returns a copy of the frustum resized according to the scale factor given
 335 //            and transforms it using the matrix given.
 336 //            There are no default parameters, but in case if:
 337 //                - transformation only is needed: @theScaleFactor must be initialized
 338 //                  as any negative value;
 339 //                - scale only is needed: @theTrsf must be set to gp_Identity.
 340 // =======================================================================
 341 Handle(SelectMgr_BaseFrustum) SelectMgr_RectangularFrustum::ScaleAndTransform (const Standard_Integer theScaleFactor,
 342                                                                                const gp_GTrsf& theTrsf) const
 343 {
 344   Standard_ASSERT_RAISE (theScaleFactor > 0,
 345     "Error! Pixel tolerance for selection should be greater than zero");
 346
 347   Handle(SelectMgr_RectangularFrustum) aRes = new SelectMgr_RectangularFrustum();
 348   const Standard_Boolean isToScale = theScaleFactor != 1;
 349   const Standard_Boolean isToTrsf  = theTrsf.Form() != gp_Identity;
 350
 351   if (!isToScale && !isToTrsf)
 352     return aRes;
 353
 354   aRes->myIsOrthographic = myIsOrthographic;
 355   const SelectMgr_RectangularFrustum* aRef = this;
 356
 357   if (isToScale)
 358   {
 359     aRes->myNearPickedPnt = myNearPickedPnt;
 360     aRes->myFarPickedPnt  = myFarPickedPnt;
 361     aRes->myViewRayDir    = myViewRayDir;
 362
 363     const gp_Pnt2d aMinPnt (myMousePos.X() - theScaleFactor * 0.5,
 364                             myMousePos.Y() - theScaleFactor * 0.5);
 365     const gp_Pnt2d aMaxPnt (myMousePos.X() + theScaleFactor * 0.5,
 366                             myMousePos.Y() + theScaleFactor * 0.5);
 367
 368     // recompute base frustum characteristics from scratch
 369     computeFrustum (aMinPnt, aMaxPnt, myBuilder, aRes->myVertices, aRes->myEdgeDirs);
 370
 371     aRef = aRes.get();
 372   }
 373
 374   if (isToTrsf)
 375   {
 376     const Standard_Real aRefScale = aRef->myFarPickedPnt.SquareDistance (aRef->myNearPickedPnt);
 377
 378     gp_Pnt aPoint = aRef->myNearPickedPnt;
 379     theTrsf.Transforms (aPoint.ChangeCoord());
 380     aRes->myNearPickedPnt = aPoint;
 381
 382     aPoint.SetXYZ (aRef->myFarPickedPnt.XYZ());
 383     theTrsf.Transforms (aPoint.ChangeCoord());
 384     aRes->myFarPickedPnt = aPoint;
 385
 386     aRes->myViewRayDir    = aRes->myFarPickedPnt.XYZ() - aRes->myNearPickedPnt.XYZ();
 387
 388     for (Standard_Integer anIt = 0; anIt < 8; anIt++)
 389     {
 390       aPoint = aRef->myVertices[anIt];
 391       theTrsf.Transforms (aPoint.ChangeCoord());
 392       aRes->myVertices[anIt] = aPoint;
 393     }
 394
 395     // Horizontal
 396     aRes->myEdgeDirs[0] = aRes->myVertices[4].XYZ() - aRes->myVertices[0].XYZ();
 397     // Vertical
 398     aRes->myEdgeDirs[1] = aRes->myVertices[2].XYZ() - aRes->myVertices[0].XYZ();
 399     // LeftLower
 400     aRes->myEdgeDirs[2] = aRes->myVertices[2].XYZ() - aRes->myVertices[3].XYZ();
 401     // RightLower
 402     aRes->myEdgeDirs[3] = aRes->myVertices[6].XYZ() - aRes->myVertices[7].XYZ();
 403     // LeftUpper
 404     aRes->myEdgeDirs[4] = aRes->myVertices[0].XYZ() - aRes->myVertices[1].XYZ();
 405     // RightUpper
 406     aRes->myEdgeDirs[5] = aRes->myVertices[4].XYZ() - aRes->myVertices[5].XYZ();
 407
 408     // Compute scale to transform depth from local coordinate system to world coordinate system
 409     aRes->myScale = Sqrt (aRefScale / aRes->myFarPickedPnt.SquareDistance (aRes->myNearPickedPnt));
 410   }
 411
 412   // compute frustum normals
 413   computeNormals (aRes->myEdgeDirs, aRes->myPlanes);
 414
 415   cacheVertexProjections (aRes.get());
 416
 417   aRes->myViewClipRange = myViewClipRange;
 418   aRes->myIsViewClipEnabled = myIsViewClipEnabled;
 419   aRes->myMousePos      = myMousePos;
 420
 421   return aRes;
 422 }
 423
 424 // =======================================================================
 425 // function : Overlaps
 426 // purpose  : Returns true if selecting volume is overlapped by
 427 //            axis-aligned bounding box with minimum corner at point
 428 //            theMinPnt and maximum at point theMaxPnt
 429 // =======================================================================
 430 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const SelectMgr_Vec3& theBoxMin,
 431                                                          const SelectMgr_Vec3& theBoxMax,
 432                                                          Standard_Boolean*     theInside)
 433 {
 434   return hasOverlap (theBoxMin, theBoxMax, theInside);
 435 }
 436
 437 // =======================================================================
 438 // function : Overlaps
 439 // purpose  : SAT intersection test between defined volume and
 440 //            given axis-aligned box
 441 // =======================================================================
 442 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const SelectMgr_Vec3& theBoxMin,
 443                                                          const SelectMgr_Vec3& theBoxMax,
 444                                                          SelectBasics_PickResult& thePickResult)
 445 {
 446   if (!hasOverlap (theBoxMin, theBoxMax))
 447     return Standard_False;
 448
 449   gp_Pnt aNearestPnt (RealLast(), RealLast(), RealLast());
 450   aNearestPnt.SetX (Max (Min (myNearPickedPnt.X(), theBoxMax.x()), theBoxMin.x()));
 451   aNearestPnt.SetY (Max (Min (myNearPickedPnt.Y(), theBoxMax.y()), theBoxMin.y()));
 452   aNearestPnt.SetZ (Max (Min (myNearPickedPnt.Z(), theBoxMax.z()), theBoxMin.z()));
 453
 454   thePickResult.SetDepth (aNearestPnt.Distance (myNearPickedPnt));
 455
 456   return isViewClippingOk (thePickResult);
 457 }
 458
 459 // =======================================================================
 460 // function : Overlaps
 461 // purpose  : Intersection test between defined volume and given point
 462 // =======================================================================
 463 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt,
 464                                                          SelectBasics_PickResult& thePickResult)
 465 {
 466   if (!hasOverlap (thePnt))
 467     return Standard_False;
 468
 469   gp_XYZ aV = thePnt.XYZ() - myNearPickedPnt.XYZ();
 470   gp_Pnt aDetectedPnt =
 471     myNearPickedPnt.XYZ() + myViewRayDir.XYZ() * (aV.Dot (myViewRayDir.XYZ()) / myViewRayDir.Dot (myViewRayDir));
 472
 473   thePickResult.SetDepth (aDetectedPnt.Distance (myNearPickedPnt) * myScale);
 474   thePickResult.SetPickedPoint (thePnt);
 475
 476   return isViewClippingOk (thePickResult);
 477 }
 478
 479 // =======================================================================
 480 // function : Overlaps
 481 // purpose  : Intersection test between defined volume and given point
 482 // =======================================================================
 483 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt)
 484 {
 485   return hasOverlap (thePnt);
 486 }
 487
 488 // =======================================================================
 489 // function : Overlaps
 490 // purpose  : Checks if line segment overlaps selecting frustum
 491 // =======================================================================
 492 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt1,
 493                                                          const gp_Pnt& thePnt2,
 494                                                          SelectBasics_PickResult& thePickResult)
 495 {
 496   if (!hasOverlap (thePnt1, thePnt2))
 497     return Standard_False;
 498
 499   segmentSegmentDistance (thePnt1, thePnt2, thePickResult);
 500
 501   return isViewClippingOk (thePickResult);
 502 }
 503
 504 // =======================================================================
 505 // function : Overlaps
 506 // purpose  : SAT intersection test between defined volume and given
 507 //            ordered set of points, representing line segments. The test
 508 //            may be considered of interior part or boundary line defined
 509 //            by segments depending on given sensitivity type
 510 // =======================================================================
 511 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const TColgp_Array1OfPnt& theArrayOfPnts,
 512                                                          Select3D_TypeOfSensitivity theSensType,
 513                                                          SelectBasics_PickResult& thePickResult)
 514 {
 515   if (theSensType == Select3D_TOS_BOUNDARY)
 516   {
 517     Standard_Integer aMatchingSegmentsNb = -1;
 518     SelectBasics_PickResult aPickResult;
 519     thePickResult.Invalidate();
 520     const Standard_Integer aLower  = theArrayOfPnts.Lower();
 521     const Standard_Integer anUpper = theArrayOfPnts.Upper();
 522     for (Standard_Integer aPntIter = aLower; aPntIter <= anUpper; ++aPntIter)
 523     {
 524       const gp_Pnt& aStartPnt = theArrayOfPnts.Value (aPntIter);
 525       const gp_Pnt& aEndPnt   = theArrayOfPnts.Value (aPntIter == anUpper ? aLower : (aPntIter + 1));
 526       if (hasOverlap (aStartPnt, aEndPnt))
 527       {
 528         aMatchingSegmentsNb++;
 529         segmentSegmentDistance (aStartPnt, aEndPnt, aPickResult);
 530         thePickResult = SelectBasics_PickResult::Min (thePickResult, aPickResult);
 531       }
 532     }
 533
 534     if (aMatchingSegmentsNb == -1)
 535       return Standard_False;
 536   }
 537   else if (theSensType == Select3D_TOS_INTERIOR)
 538   {
 539     gp_Vec aPolyNorm (gp_XYZ (RealLast(), RealLast(), RealLast()));
 540     if (!hasOverlap (theArrayOfPnts, aPolyNorm)
 541      || !segmentPlaneIntersection (aPolyNorm,
 542                                    theArrayOfPnts.First(),
 543                                    thePickResult))
 544     {
 545       return Standard_False;
 546     }
 547   }
 548
 549   return isViewClippingOk (thePickResult);
 550 }
 551
 552 // =======================================================================
 553 // function : Overlaps
 554 // purpose  : SAT intersection test between defined volume and given
 555 //            triangle. The test may be considered of interior part or
 556 //            boundary line defined by triangle vertices depending on
 557 //            given sensitivity type
 558 // =======================================================================
 559 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt1,
 560                                                          const gp_Pnt& thePnt2,
 561                                                          const gp_Pnt& thePnt3,
 562                                                          Select3D_TypeOfSensitivity theSensType,
 563                                                          SelectBasics_PickResult& thePickResult)
 564 {
 565   if (theSensType == Select3D_TOS_BOUNDARY)
 566   {
 567     const gp_Pnt aPntsArrayBuf[4] = { thePnt1, thePnt2, thePnt3, thePnt1 };
 568     const TColgp_Array1OfPnt aPntsArray (aPntsArrayBuf[0], 1, 4);
 569     return Overlaps (aPntsArray, Select3D_TOS_BOUNDARY, thePickResult);
 570   }
 571   else if (theSensType == Select3D_TOS_INTERIOR)
 572   {
 573     gp_Vec aTriangleNormal (gp_XYZ (RealLast(), RealLast(), RealLast()));
 574     if (!hasOverlap (thePnt1, thePnt2, thePnt3, aTriangleNormal))
 575       return Standard_False;
 576
 577     // check if intersection point belongs to triangle's interior part
 578     gp_XYZ aTrEdges[3] = { thePnt2.XYZ() - thePnt1.XYZ(),
 579                            thePnt3.XYZ() - thePnt2.XYZ(),
 580                            thePnt1.XYZ() - thePnt3.XYZ() };
 581
 582     Standard_Real anAlpha = aTriangleNormal.Dot (myViewRayDir);
 583     if (Abs (anAlpha) < gp::Resolution())
 584     {
 585       // handle degenerated triangles: in this case, there is no possible way to detect overlap correctly.
 586       if (aTriangleNormal.SquareMagnitude() < gp::Resolution())
 587       {
 588         return Standard_False;
 589       }
 590
 591       // handle the case when triangle normal and selecting frustum direction are orthogonal: for this case, overlap
 592       // is detected correctly, and distance to triangle's plane can be measured as distance to its arbitrary vertex.
 593       const gp_XYZ aDiff = myNearPickedPnt.XYZ() - thePnt1.XYZ();
 594       thePickResult.SetDepth (aTriangleNormal.Dot (aDiff) * myScale);
 595       thePickResult.SetPickedPoint (thePnt1);
 596       return isViewClippingOk (thePickResult);
 597     }
 598
 599     gp_XYZ anEdge = (thePnt1.XYZ() - myNearPickedPnt.XYZ()) * (1.0 / anAlpha);
 600
 601     Standard_Real aTime = aTriangleNormal.Dot (anEdge);
 602
 603     gp_XYZ aVec = myViewRayDir.XYZ().Crossed (anEdge);
 604
 605     Standard_Real anU = aVec.Dot (aTrEdges[2]);
 606     Standard_Real aV  = aVec.Dot (aTrEdges[0]);
 607
 608     const Standard_Boolean isInterior = (aTime >= 0.0) && (anU >= 0.0) && (aV >= 0.0) && (anU + aV <= 1.0);
 609     const gp_Pnt aPtOnPlane = myNearPickedPnt.XYZ() + myViewRayDir.XYZ() * aTime;
 610     if (isInterior)
 611     {
 612       thePickResult.SetDepth (myNearPickedPnt.Distance (aPtOnPlane) * myScale);
 613       thePickResult.SetPickedPoint (aPtOnPlane);
 614       return isViewClippingOk (thePickResult);
 615     }
 616
 617     gp_Pnt aPnts[3] = {thePnt1, thePnt2, thePnt3};
 618     Standard_Real aMinDist = RealLast();
 619     Standard_Integer aNearestEdgeIdx = -1;
 620     for (Standard_Integer anEdgeIdx = 0; anEdgeIdx < 3; ++anEdgeIdx)
 621     {
 622       gp_XYZ aW = aPtOnPlane.XYZ() - aPnts[anEdgeIdx].XYZ();
 623       Standard_Real aCoef = aTrEdges[anEdgeIdx].Dot (aW) / aTrEdges[anEdgeIdx].Dot (aTrEdges[anEdgeIdx]);
 624       Standard_Real aDist = aPtOnPlane.Distance (aPnts[anEdgeIdx].XYZ() + aCoef * aTrEdges[anEdgeIdx]);
 625       if (aMinDist > aDist)
 626       {
 627         aMinDist = aDist;
 628         aNearestEdgeIdx = anEdgeIdx;
 629       }
 630     }
 631     segmentSegmentDistance (aPnts[aNearestEdgeIdx], aPnts[(aNearestEdgeIdx + 1) % 3], thePickResult);
 632   }
 633
 634   return isViewClippingOk (thePickResult);
 635 }
 636
 637 // =======================================================================
 638 // function : DistToGeometryCenter
 639 // purpose  : Measures distance between 3d projection of user-picked
 640 //            screen point and given point theCOG
 641 // =======================================================================
 642 Standard_Real SelectMgr_RectangularFrustum::DistToGeometryCenter (const gp_Pnt& theCOG)
 643 {
 644   return theCOG.Distance (myNearPickedPnt) * myScale;
 645 }
 646
 647 // =======================================================================
 648 // function : DetectedPoint
 649 // purpose  : Calculates the point on a view ray that was detected during
 650 //            the run of selection algo by given depth
 651 // =======================================================================
 652 gp_Pnt SelectMgr_RectangularFrustum::DetectedPoint (const Standard_Real theDepth) const
 653 {
 654   return myNearPickedPnt.XYZ() + myViewRayDir.Normalized().XYZ() * theDepth / myScale;
 655 }
 656
 657 // =======================================================================
 658 // function : computeClippingRange
 659 // purpose  :
 660 // =======================================================================
 661 void SelectMgr_RectangularFrustum::computeClippingRange (const Graphic3d_SequenceOfHClipPlane& thePlanes,
 662                                                          SelectMgr_ViewClipRange& theRange)
 663 {
 664   Standard_Real aPlaneA, aPlaneB, aPlaneC, aPlaneD;
 665   for (Graphic3d_SequenceOfHClipPlane::Iterator aPlaneIt (thePlanes); aPlaneIt.More(); aPlaneIt.Next())
 666   {
 667     const Handle(Graphic3d_ClipPlane)& aClipPlane = aPlaneIt.Value();
 668     if (!aClipPlane->IsOn())
 669     {
 670       continue;
 671     }
 672
 673     Bnd_Range aSubRange (RealFirst(), RealLast());
 674     for (const Graphic3d_ClipPlane* aSubPlaneIter = aClipPlane.get(); aSubPlaneIter != NULL; aSubPlaneIter = aSubPlaneIter->ChainNextPlane().get())
 675     {
 676       const gp_Pln aGeomPlane = aSubPlaneIter->ToPlane();
 677       aGeomPlane.Coefficients (aPlaneA, aPlaneB, aPlaneC, aPlaneD);
 678
 679       const gp_XYZ& aPlaneDirXYZ = aGeomPlane.Axis().Direction().XYZ();
 680       Standard_Real aDotProduct = myViewRayDir.XYZ().Dot (aPlaneDirXYZ);
 681       Standard_Real aDistance   = -myNearPickedPnt.XYZ().Dot (aPlaneDirXYZ) - aPlaneD;
 682       Standard_Real aDistToPln  = 0.0;
 683
 684       // check whether the pick line is parallel to clip plane
 685       if (Abs (aDotProduct) < Precision::Angular())
 686       {
 687         if (aDistance < 0.0)
 688         {
 689           continue;
 690         }
 691         aDistToPln  = RealLast();
 692         aDotProduct = 1.0;
 693       }
 694       else
 695       {
 696         // compute distance to point of pick line intersection with the plane
 697         const Standard_Real aParam = aDistance / aDotProduct;
 698
 699         const gp_Pnt anIntersectionPnt = myNearPickedPnt.XYZ() + myViewRayDir.XYZ() * aParam;
 700         aDistToPln = anIntersectionPnt.Distance (myNearPickedPnt);
 701         if (aParam < 0.0)
 702         {
 703           // the plane is "behind" the ray
 704           aDistToPln = -aDistToPln;
 705         }
 706       }
 707
 708       // change depth limits for case of opposite and directed planes
 709       if (!aClipPlane->IsChain())
 710       {
 711         if (aDotProduct < 0.0)
 712         {
 713           theRange.ChangeUnclipRange().TrimTo (aDistToPln);
 714         }
 715         else
 716         {
 717           theRange.ChangeUnclipRange().TrimFrom (aDistToPln);
 718         }
 719       }
 720       else
 721       {
 722         if (aDotProduct < 0.0)
 723         {
 724           aSubRange.TrimFrom (aDistToPln);
 725         }
 726         else
 727         {
 728           aSubRange.TrimTo (aDistToPln);
 729         }
 730       }
 731     }
 732
 733     if (!aSubRange.IsVoid()
 734       && aClipPlane->IsChain())
 735     {
 736       theRange.AddClipSubRange (aSubRange);
 737     }
 738   }
 739 }
 740
 741 // =======================================================================
 742 // function : IsClipped
 743 // purpose  : Checks if the point of sensitive in which selection was
 744 //            detected belongs to the region defined by clipping planes
 745 // =======================================================================
 746 Standard_Boolean SelectMgr_RectangularFrustum::IsClipped (const Graphic3d_SequenceOfHClipPlane& thePlanes,
 747                                                           const Standard_Real theDepth)
 748 {
 749   SelectMgr_ViewClipRange aRange;
 750   computeClippingRange (thePlanes, aRange);
 751   return aRange.IsClipped (theDepth);
 752 }
 753
 754 // =======================================================================
 755 // function : SetViewClipping
 756 // purpose  :
 757 // =======================================================================
 758 void SelectMgr_RectangularFrustum::SetViewClipping (const Handle(Graphic3d_SequenceOfHClipPlane)& thePlanes)
 759 {
 760   if (thePlanes.IsNull()
 761    || thePlanes->IsEmpty())
 762   {
 763     myViewClipRange.SetVoid();
 764     return;
 765   }
 766
 767   computeClippingRange (*thePlanes, myViewClipRange);
 768 }
 769
 770 // =======================================================================
 771 // function : isViewClippingOk
 772 // purpose  :
 773 // =======================================================================
 774 Standard_Boolean SelectMgr_RectangularFrustum::isViewClippingOk (const SelectBasics_PickResult& thePickResult) const
 775 {
 776   return !myIsViewClipEnabled
 777       || !myViewClipRange.IsClipped (thePickResult.Depth());
 778 }
 779
 780 // =======================================================================
 781 // function : GetPlanes
 782 // purpose  :
 783 // =======================================================================
 784 void SelectMgr_RectangularFrustum::GetPlanes (NCollection_Vector<SelectMgr_Vec4>& thePlaneEquations) const
 785 {
 786   thePlaneEquations.Clear();
 787
 788   SelectMgr_Vec4 anEquation;
 789   for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < 6; ++aPlaneIdx)
 790   {
 791     const gp_Vec& aPlaneNorm = myIsOrthographic && aPlaneIdx % 2 == 1 ?
 792       myPlanes[aPlaneIdx - 1].Reversed() : myPlanes[aPlaneIdx];
 793     anEquation.x() = aPlaneNorm.X();
 794     anEquation.y() = aPlaneNorm.Y();
 795     anEquation.z() = aPlaneNorm.Z();
 796     anEquation.w() = - (aPlaneNorm.XYZ().Dot (myVertices[aPlaneIdx % 2 == 0 ? aPlaneIdx : aPlaneIdx + 2].XYZ()));
 797     thePlaneEquations.Append (anEquation);
 798   }
 799 }