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 = myFarPickedPnt.XYZ() - myNearPickedPnt.XYZ(); // use unnormalized vector instead of myViewRayDir to clip solutions behind Far plane
  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() + aV * 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 = myFarPickedPnt.XYZ() - myNearPickedPnt.XYZ(); // use unnormalized vector instead of myViewRayDir to clip solutions behind Far plane by > 1.0 check
 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) // > 1.0 check could be removed for an infinite ray and anU=myViewRayDir
 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   myScale = 1.0;
 346 }
 347
 348 // =======================================================================
 349 // function : Build
 350 // purpose  : Build volume according to the selected rectangle
 351 // =======================================================================
 352 void SelectMgr_RectangularFrustum::Build (const gp_Pnt2d& theMinPnt,
 353                                           const gp_Pnt2d& theMaxPnt)
 354 {
 355   myNearPickedPnt = myBuilder->ProjectPntOnViewPlane ((theMinPnt.X() + theMaxPnt.X()) * 0.5,
 356                                                       (theMinPnt.Y() + theMaxPnt.Y()) * 0.5,
 357                                                       0.0);
 358   myFarPickedPnt = myBuilder->ProjectPntOnViewPlane ((theMinPnt.X() + theMaxPnt.X()) * 0.5,
 359                                                      (theMinPnt.Y() + theMaxPnt.Y()) * 0.5,
 360                                                      1.0);
 361   myViewRayDir = myFarPickedPnt.XYZ() - myNearPickedPnt.XYZ();
 362
 363   // calculate base frustum characteristics: vertices and edge directions
 364   computeFrustum (theMinPnt, theMaxPnt, myBuilder, myVertices, myEdgeDirs);
 365
 366   // compute frustum normals
 367   computeNormals (myEdgeDirs, myPlanes);
 368
 369   // compute vertices projections onto frustum normals and
 370   // {i, j, k} vectors and store them to corresponding class fields
 371   cacheVertexProjections (this);
 372
 373   myScale = 1.0;
 374 }
 375
 376 // =======================================================================
 377 // function : ScaleAndTransform
 378 // purpose  : IMPORTANT: Scaling makes sense only for frustum built on a single point!
 379 //            Note that this method does not perform any checks on type of the frustum.
 380 //            Returns a copy of the frustum resized according to the scale factor given
 381 //            and transforms it using the matrix given.
 382 //            There are no default parameters, but in case if:
 383 //                - transformation only is needed: @theScaleFactor must be initialized
 384 //                  as any negative value;
 385 //                - scale only is needed: @theTrsf must be set to gp_Identity.
 386 // =======================================================================
 387 Handle(SelectMgr_BaseFrustum) SelectMgr_RectangularFrustum::ScaleAndTransform (const Standard_Integer theScaleFactor,
 388                                                                                const gp_GTrsf& theTrsf) const
 389 {
 390   Standard_ASSERT_RAISE (theScaleFactor > 0,
 391     "Error! Pixel tolerance for selection should be greater than zero");
 392
 393   Handle(SelectMgr_RectangularFrustum) aRes = new SelectMgr_RectangularFrustum();
 394   const Standard_Boolean isToScale = theScaleFactor != 1;
 395   const Standard_Boolean isToTrsf  = theTrsf.Form() != gp_Identity;
 396
 397   if (!isToScale && !isToTrsf)
 398     return aRes;
 399
 400   aRes->myIsOrthographic = myIsOrthographic;
 401   const SelectMgr_RectangularFrustum* aRef = this;
 402
 403   if (isToScale)
 404   {
 405     aRes->myNearPickedPnt = myNearPickedPnt;
 406     aRes->myFarPickedPnt  = myFarPickedPnt;
 407     aRes->myViewRayDir    = myViewRayDir;
 408
 409     const gp_Pnt2d aMinPnt (myMousePos.X() - theScaleFactor * 0.5,
 410                             myMousePos.Y() - theScaleFactor * 0.5);
 411     const gp_Pnt2d aMaxPnt (myMousePos.X() + theScaleFactor * 0.5,
 412                             myMousePos.Y() + theScaleFactor * 0.5);
 413
 414     // recompute base frustum characteristics from scratch
 415     computeFrustum (aMinPnt, aMaxPnt, myBuilder, aRes->myVertices, aRes->myEdgeDirs);
 416
 417     aRef = aRes.get();
 418   }
 419
 420   if (isToTrsf)
 421   {
 422     const Standard_Real aRefScale = aRef->myFarPickedPnt.SquareDistance (aRef->myNearPickedPnt);
 423
 424     gp_Pnt aPoint = aRef->myNearPickedPnt;
 425     theTrsf.Transforms (aPoint.ChangeCoord());
 426     aRes->myNearPickedPnt = aPoint;
 427
 428     aPoint.SetXYZ (aRef->myFarPickedPnt.XYZ());
 429     theTrsf.Transforms (aPoint.ChangeCoord());
 430     aRes->myFarPickedPnt = aPoint;
 431
 432     aRes->myViewRayDir = aRes->myFarPickedPnt.XYZ() - aRes->myNearPickedPnt.XYZ();
 433
 434     for (Standard_Integer anIt = 0; anIt < 8; anIt++)
 435     {
 436       aPoint = aRef->myVertices[anIt];
 437       theTrsf.Transforms (aPoint.ChangeCoord());
 438       aRes->myVertices[anIt] = aPoint;
 439     }
 440
 441     // Horizontal
 442     aRes->myEdgeDirs[0] = aRes->myVertices[4].XYZ() - aRes->myVertices[0].XYZ();
 443     // Vertical
 444     aRes->myEdgeDirs[1] = aRes->myVertices[2].XYZ() - aRes->myVertices[0].XYZ();
 445     // LeftLower
 446     aRes->myEdgeDirs[2] = aRes->myVertices[2].XYZ() - aRes->myVertices[3].XYZ();
 447     // RightLower
 448     aRes->myEdgeDirs[3] = aRes->myVertices[6].XYZ() - aRes->myVertices[7].XYZ();
 449     // LeftUpper
 450     aRes->myEdgeDirs[4] = aRes->myVertices[0].XYZ() - aRes->myVertices[1].XYZ();
 451     // RightUpper
 452     aRes->myEdgeDirs[5] = aRes->myVertices[4].XYZ() - aRes->myVertices[5].XYZ();
 453
 454     // Compute scale to transform depth from local coordinate system to world coordinate system
 455     aRes->myScale = Sqrt (aRefScale / aRes->myFarPickedPnt.SquareDistance (aRes->myNearPickedPnt));
 456   }
 457
 458   // compute frustum normals
 459   computeNormals (aRes->myEdgeDirs, aRes->myPlanes);
 460
 461   cacheVertexProjections (aRes.get());
 462
 463   aRes->myMousePos = myMousePos;
 464
 465   return aRes;
 466 }
 467
 468 // =======================================================================
 469 // function : Overlaps
 470 // purpose  : Returns true if selecting volume is overlapped by
 471 //            axis-aligned bounding box with minimum corner at point
 472 //            theMinPnt and maximum at point theMaxPnt
 473 // =======================================================================
 474 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const SelectMgr_Vec3& theBoxMin,
 475                                                          const SelectMgr_Vec3& theBoxMax,
 476                                                          Standard_Boolean*     theInside) const
 477 {
 478   return hasOverlap (theBoxMin, theBoxMax, theInside);
 479 }
 480
 481 // =======================================================================
 482 // function : Overlaps
 483 // purpose  : SAT intersection test between defined volume and
 484 //            given axis-aligned box
 485 // =======================================================================
 486 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const SelectMgr_Vec3& theBoxMin,
 487                                                          const SelectMgr_Vec3& theBoxMax,
 488                                                          const SelectMgr_ViewClipRange& theClipRange,
 489                                                          SelectBasics_PickResult& thePickResult) const
 490 {
 491   if (!hasOverlap (theBoxMin, theBoxMax))
 492     return Standard_False;
 493
 494   gp_Ax1 aRay (myNearPickedPnt, myViewRayDir);
 495   Bnd_Range aRange = rayBoxIntersection (aRay,
 496                                          gp_Pnt (theBoxMin.x(), theBoxMin.y(), theBoxMin.z()),
 497                                          gp_Pnt (theBoxMax.x(), theBoxMax.y(), theBoxMax.z()));
 498
 499   Standard_Real aDepth = 0.0;
 500   aRange.GetMin (aDepth);
 501
 502   if (aDepth == DBL_MAX)
 503   {
 504     gp_Pnt aNearestPnt (RealLast(), RealLast(), RealLast());
 505     aNearestPnt.SetX (Max (Min (myNearPickedPnt.X(), theBoxMax.x()), theBoxMin.x()));
 506     aNearestPnt.SetY (Max (Min (myNearPickedPnt.Y(), theBoxMax.y()), theBoxMin.y()));
 507     aNearestPnt.SetZ (Max (Min (myNearPickedPnt.Z(), theBoxMax.z()), theBoxMin.z()));
 508
 509     aDepth = aNearestPnt.Distance (myNearPickedPnt);
 510     thePickResult.SetDepth (aDepth);
 511     return !theClipRange.IsClipped (thePickResult.Depth());
 512   }
 513
 514   if (!theClipRange.GetNearestDepth (aRange, aDepth))
 515   {
 516     return Standard_False;
 517   }
 518
 519   thePickResult.SetDepth (aDepth);
 520
 521   return Standard_True;
 522 }
 523
 524 // =======================================================================
 525 // function : Overlaps
 526 // purpose  : Intersection test between defined volume and given point
 527 // =======================================================================
 528 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt,
 529                                                          const SelectMgr_ViewClipRange& theClipRange,
 530                                                          SelectBasics_PickResult& thePickResult) const
 531 {
 532   if (!hasOverlap (thePnt))
 533     return Standard_False;
 534
 535   gp_XYZ aV = thePnt.XYZ() - myNearPickedPnt.XYZ();
 536   const Standard_Real aDepth = aV.Dot (myViewRayDir.XYZ());
 537
 538   thePickResult.SetDepth (Abs (aDepth) * myScale);
 539   thePickResult.SetPickedPoint (thePnt);
 540
 541   return !theClipRange.IsClipped (thePickResult.Depth());
 542 }
 543
 544 // =======================================================================
 545 // function : Overlaps
 546 // purpose  : Intersection test between defined volume and given point
 547 // =======================================================================
 548 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt) const
 549 {
 550   return hasOverlap (thePnt);
 551 }
 552
 553 // =======================================================================
 554 // function : Overlaps
 555 // purpose  : Checks if line segment overlaps selecting frustum
 556 // =======================================================================
 557 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt1,
 558                                                          const gp_Pnt& thePnt2,
 559                                                          const SelectMgr_ViewClipRange& theClipRange,
 560                                                          SelectBasics_PickResult& thePickResult) const
 561 {
 562   if (!hasOverlap (thePnt1, thePnt2))
 563     return Standard_False;
 564
 565   segmentSegmentDistance (thePnt1, thePnt2, thePickResult);
 566
 567   return !theClipRange.IsClipped (thePickResult.Depth());
 568 }
 569
 570 // =======================================================================
 571 // function : Overlaps
 572 // purpose  : SAT intersection test between defined volume and given
 573 //            ordered set of points, representing line segments. The test
 574 //            may be considered of interior part or boundary line defined
 575 //            by segments depending on given sensitivity type
 576 // =======================================================================
 577 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const TColgp_Array1OfPnt& theArrayOfPnts,
 578                                                          Select3D_TypeOfSensitivity theSensType,
 579                                                          const SelectMgr_ViewClipRange& theClipRange,
 580                                                          SelectBasics_PickResult& thePickResult) const
 581 {
 582   if (theSensType == Select3D_TOS_BOUNDARY)
 583   {
 584     Standard_Integer aMatchingSegmentsNb = -1;
 585     SelectBasics_PickResult aPickResult;
 586     thePickResult.Invalidate();
 587     const Standard_Integer aLower  = theArrayOfPnts.Lower();
 588     const Standard_Integer anUpper = theArrayOfPnts.Upper();
 589     for (Standard_Integer aPntIter = aLower; aPntIter <= anUpper; ++aPntIter)
 590     {
 591       const gp_Pnt& aStartPnt = theArrayOfPnts.Value (aPntIter);
 592       const gp_Pnt& aEndPnt   = theArrayOfPnts.Value (aPntIter == anUpper ? aLower : (aPntIter + 1));
 593       if (hasOverlap (aStartPnt, aEndPnt))
 594       {
 595         aMatchingSegmentsNb++;
 596         segmentSegmentDistance (aStartPnt, aEndPnt, aPickResult);
 597         thePickResult = SelectBasics_PickResult::Min (thePickResult, aPickResult);
 598       }
 599     }
 600
 601     if (aMatchingSegmentsNb == -1)
 602       return Standard_False;
 603   }
 604   else if (theSensType == Select3D_TOS_INTERIOR)
 605   {
 606     gp_Vec aPolyNorm (gp_XYZ (RealLast(), RealLast(), RealLast()));
 607     if (!hasOverlap (theArrayOfPnts, aPolyNorm))
 608     {
 609       return Standard_False;
 610     }
 611
 612     if (aPolyNorm.Magnitude() <= Precision::Confusion())
 613     {
 614       // treat degenerated polygon as point
 615       return Overlaps (theArrayOfPnts.First(), theClipRange, thePickResult);
 616     }
 617     else if (!segmentPlaneIntersection (aPolyNorm, theArrayOfPnts.First(), thePickResult))
 618     {
 619       return Standard_False;
 620     }
 621   }
 622
 623   return !theClipRange.IsClipped (thePickResult.Depth());
 624 }
 625
 626 // =======================================================================
 627 // function : Overlaps
 628 // purpose  : SAT intersection test between defined volume and given
 629 //            triangle. The test may be considered of interior part or
 630 //            boundary line defined by triangle vertices depending on
 631 //            given sensitivity type
 632 // =======================================================================
 633 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt1,
 634                                                          const gp_Pnt& thePnt2,
 635                                                          const gp_Pnt& thePnt3,
 636                                                          Select3D_TypeOfSensitivity theSensType,
 637                                                          const SelectMgr_ViewClipRange& theClipRange,
 638                                                          SelectBasics_PickResult& thePickResult) const
 639 {
 640   if (theSensType == Select3D_TOS_BOUNDARY)
 641   {
 642     const gp_Pnt aPntsArrayBuf[4] = { thePnt1, thePnt2, thePnt3, thePnt1 };
 643     const TColgp_Array1OfPnt aPntsArray (aPntsArrayBuf[0], 1, 4);
 644     return Overlaps (aPntsArray, Select3D_TOS_BOUNDARY, theClipRange, thePickResult);
 645   }
 646   else if (theSensType == Select3D_TOS_INTERIOR)
 647   {
 648     gp_Vec aTriangleNormal (gp_XYZ (RealLast(), RealLast(), RealLast()));
 649     if (!hasOverlap (thePnt1, thePnt2, thePnt3, aTriangleNormal))
 650     {
 651       return Standard_False;
 652     }
 653
 654     const gp_XYZ aTrEdges[3] = { thePnt2.XYZ() - thePnt1.XYZ(),
 655                                  thePnt3.XYZ() - thePnt2.XYZ(),
 656                                  thePnt1.XYZ() - thePnt3.XYZ() };
 657           if (aTriangleNormal.SquareMagnitude() < gp::Resolution())
 658     {
 659       // consider degenerated triangle as point or segment
 660       return aTrEdges[0].SquareModulus() > gp::Resolution()
 661            ? Overlaps (thePnt1, thePnt2, theClipRange, thePickResult)
 662            : (aTrEdges[1].SquareModulus() > gp::Resolution()
 663             ? Overlaps (thePnt2, thePnt3, theClipRange, thePickResult)
 664             : Overlaps (thePnt1, theClipRange, thePickResult));
 665     }
 666
 667     const gp_Pnt aPnts[3] = {thePnt1, thePnt2, thePnt3};
 668     const Standard_Real anAlpha = aTriangleNormal.XYZ().Dot (myViewRayDir.XYZ());
 669     if (Abs (anAlpha) < gp::Resolution())
 670     {
 671       // handle the case when triangle normal and selecting frustum direction are orthogonal
 672       SelectBasics_PickResult aPickResult;
 673       thePickResult.Invalidate();
 674       for (Standard_Integer anEdgeIter = 0; anEdgeIter < 3; ++anEdgeIter)
 675       {
 676         const gp_Pnt& aStartPnt = aPnts[anEdgeIter];
 677         const gp_Pnt& anEndPnt  = aPnts[anEdgeIter < 2 ? anEdgeIter + 1 : 0];
 678         segmentSegmentDistance (aStartPnt, anEndPnt, aPickResult);
 679         thePickResult = SelectBasics_PickResult::Min (thePickResult, aPickResult);
 680       }
 681       return !theClipRange.IsClipped (thePickResult.Depth());
 682     }
 683
 684     // check if intersection point belongs to triangle's interior part
 685     const gp_XYZ anEdge = (thePnt1.XYZ() - myNearPickedPnt.XYZ()) * (1.0 / anAlpha);
 686
 687     const Standard_Real aTime = aTriangleNormal.Dot (anEdge);
 688     const gp_XYZ aVec = myViewRayDir.XYZ().Crossed (anEdge);
 689     const Standard_Real anU = aVec.Dot (aTrEdges[2]);
 690     const Standard_Real aV  = aVec.Dot (aTrEdges[0]);
 691
 692     const Standard_Boolean isInterior = (aTime >= 0.0) && (anU >= 0.0) && (aV >= 0.0) && (anU + aV <= 1.0);
 693     const gp_Pnt aPtOnPlane = myNearPickedPnt.XYZ() + myViewRayDir.XYZ() * aTime;
 694     if (isInterior)
 695     {
 696       thePickResult.SetDepth (myNearPickedPnt.Distance (aPtOnPlane) * myScale);
 697       thePickResult.SetPickedPoint (aPtOnPlane);
 698       thePickResult.SetSurfaceNormal (aTriangleNormal);
 699       return !theClipRange.IsClipped (thePickResult.Depth());
 700     }
 701
 702     Standard_Real aMinDist = RealLast();
 703     Standard_Integer aNearestEdgeIdx1 = -1;
 704     for (Standard_Integer anEdgeIdx = 0; anEdgeIdx < 3; ++anEdgeIdx)
 705     {
 706       gp_XYZ aW = aPtOnPlane.XYZ() - aPnts[anEdgeIdx].XYZ();
 707       Standard_Real aCoef = aTrEdges[anEdgeIdx].Dot (aW) / aTrEdges[anEdgeIdx].Dot (aTrEdges[anEdgeIdx]);
 708       Standard_Real aDist = aPtOnPlane.Distance (aPnts[anEdgeIdx].XYZ() + aCoef * aTrEdges[anEdgeIdx]);
 709       if (aDist < aMinDist)
 710       {
 711         aMinDist = aDist;
 712         aNearestEdgeIdx1 = anEdgeIdx;
 713       }
 714     }
 715     Standard_Integer aNearestEdgeIdx2 = (aNearestEdgeIdx1 + 1) % 3;
 716     if (myViewRayDir.IsParallel (gp_Vec (aPnts[aNearestEdgeIdx1], aPnts[aNearestEdgeIdx2]), Precision::Angular()))
 717     {
 718       aNearestEdgeIdx2 = aNearestEdgeIdx1 == 0 ? 2 : aNearestEdgeIdx1 - 1;
 719     }
 720     segmentSegmentDistance (aPnts[aNearestEdgeIdx1], aPnts[aNearestEdgeIdx2], thePickResult);
 721   }
 722
 723   return !theClipRange.IsClipped (thePickResult.Depth());
 724 }
 725
 726 // =======================================================================
 727 // function : DistToGeometryCenter
 728 // purpose  : Measures distance between 3d projection of user-picked
 729 //            screen point and given point theCOG
 730 // =======================================================================
 731 Standard_Real SelectMgr_RectangularFrustum::DistToGeometryCenter (const gp_Pnt& theCOG) const
 732 {
 733   return theCOG.Distance (myNearPickedPnt) * myScale;
 734 }
 735
 736 // =======================================================================
 737 // function : DetectedPoint
 738 // purpose  : Calculates the point on a view ray that was detected during
 739 //            the run of selection algo by given depth
 740 // =======================================================================
 741 gp_Pnt SelectMgr_RectangularFrustum::DetectedPoint (const Standard_Real theDepth) const
 742 {
 743   return myNearPickedPnt.XYZ() + myViewRayDir.XYZ() * theDepth / myScale;
 744 }
 745
 746 // =======================================================================
 747 // function : GetPlanes
 748 // purpose  :
 749 // =======================================================================
 750 void SelectMgr_RectangularFrustum::GetPlanes (NCollection_Vector<SelectMgr_Vec4>& thePlaneEquations) const
 751 {
 752   thePlaneEquations.Clear();
 753
 754   SelectMgr_Vec4 anEquation;
 755   for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < 6; ++aPlaneIdx)
 756   {
 757     const gp_Vec& aPlaneNorm = myIsOrthographic && aPlaneIdx % 2 == 1 ?
 758       myPlanes[aPlaneIdx - 1].Reversed() : myPlanes[aPlaneIdx];
 759     anEquation.x() = aPlaneNorm.X();
 760     anEquation.y() = aPlaneNorm.Y();
 761     anEquation.z() = aPlaneNorm.Z();
 762     anEquation.w() = - (aPlaneNorm.XYZ().Dot (myVertices[aPlaneIdx % 2 == 0 ? aPlaneIdx : aPlaneIdx + 2].XYZ()));
 763     thePlaneEquations.Append (anEquation);
 764   }
 765 }