0029938: Visualization - SelectMgr_ViewerSelector::PickedPoint() should return point...
[occt.git] / 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.ChangeMain().Add (Bnd_Range (aDistToPln, RealLast()));
714         }
715         else
716         {
717           theRange.ChangeMain().Add (Bnd_Range (RealFirst(), 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.AddSubRange (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 }