3646f50dc2f6a9768361f87552bac98f7c05de41
[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 #define DOT(A, B) (A.x() * B.x() + A.y() * B.y() + A.z() * B.z())
22 #define DOTp(A, B) (A.x() * B.X() + A.y() * B.Y() + A.z() * B.Z())
23 #define DISTANCE(A, B) (std::sqrt ((A.x() - B.x()) * (A.x() - B.x()) + (A.y() - B.y()) * (A.y() - B.y()) + (A.z() - B.z()) * (A.z() - B.z())))
24 #define DISTANCEp(A, B) (std::sqrt ((A.x() - B.X()) * (A.x() - B.X()) + (A.y() - B.Y()) * (A.y() - B.Y()) + (A.z() - B.Z()) * (A.z() - B.Z())))
25
26 // =======================================================================
27 // function : segmentSegmentDistance
28 // purpose  :
29 // =======================================================================
30 void SelectMgr_RectangularFrustum::segmentSegmentDistance (const gp_Pnt& theSegPnt1,
31                                                            const gp_Pnt& theSegPnt2,
32                                                            Standard_Real& theDepth)
33 {
34   SelectMgr_Vec3 anU = SelectMgr_Vec3 (theSegPnt2.X() - theSegPnt1.X(),
35                                        theSegPnt2.Y() - theSegPnt1.Y(),
36                                        theSegPnt2.Z() - theSegPnt1.Z());
37   SelectMgr_Vec3 aV = myViewRayDir;
38   SelectMgr_Vec3 aW = SelectMgr_Vec3 (theSegPnt1.X() - myNearPickedPnt.x(),
39                                       theSegPnt1.Y() - myNearPickedPnt.y(),
40                                       theSegPnt1.Z() - myNearPickedPnt.z());
41   Standard_Real anA = DOT (anU, anU);
42   Standard_Real aB = DOT (anU, aV);
43   Standard_Real aC = DOT (aV, aV);
44   Standard_Real aD = DOT (anU, aW);
45   Standard_Real anE = DOT (aV, aW);
46   Standard_Real aCoef = anA * aC - aB * aB;
47   Standard_Real aSc, aSn, aSd = aCoef;
48   Standard_Real aTc, aTn, aTd = aCoef;
49
50   if (aCoef < Precision::Confusion())
51   {
52     aSn = 0.0;
53     aSd = 1.0;
54     aTn = anE;
55     aTd = aC;
56   }
57   else
58   {
59     aSn = (aB * anE - aC * aD);
60     aTn = (anA * anE - aB * aD);
61     if (aSn < 0.0)
62     {
63       aSn = 0.0;
64       aTn = anE;
65       aTd = aC;
66     }
67     else if (aSn > aSd)
68     {
69       aSn = aSd;
70       aTn = anE + aB;
71       aTd = aC;
72     }
73   }
74
75   if (aTn < 0.0)
76   {
77     aTn = 0.0;
78     if (-aD < 0.0)
79       aSn = 0.0;
80     else if (-aD > anA)
81       aSn = aSd;
82     else {
83       aSn = -aD;
84       aSd = anA;
85     }
86   }
87   else if (aTn > aTd)
88   {
89     aTn = aTd;
90     if ((-aD + aB) < 0.0)
91       aSn = 0;
92     else if ((-aD + aB) > anA)
93       aSn = aSd;
94     else {
95       aSn = (-aD +  aB);
96       aSd = anA;
97     }
98   }
99   aSc = (Abs (aSn) < Precision::Confusion() ? 0.0 : aSn / aSd);
100   aTc = (Abs (aTn) < Precision::Confusion() ? 0.0 : aTn / aTd);
101
102   SelectMgr_Vec3 aDiff = aW + (anU * aSc) - (aV * aTc);
103   SelectMgr_Vec3 aClosestPnt = myNearPickedPnt + myViewRayDir * aTc;
104   theDepth = DISTANCE (myNearPickedPnt, aClosestPnt);
105 }
106
107 // =======================================================================
108 // function : segmentPlaneIntersection
109 // purpose  :
110 // =======================================================================
111 void SelectMgr_RectangularFrustum::segmentPlaneIntersection (const SelectMgr_Vec3& thePlane,
112                                                              const gp_Pnt& thePntOnPlane,
113                                                              Standard_Real& theDepth)
114 {
115   SelectMgr_Vec3 anU = myViewRayDir;
116   SelectMgr_Vec3 aW = SelectMgr_Vec3 (myNearPickedPnt.x() - thePntOnPlane.X(),
117                                       myNearPickedPnt.y() - thePntOnPlane.Y(),
118                                       myNearPickedPnt.z() - thePntOnPlane.Z());
119   Standard_Real aD = DOT (thePlane, anU);
120   Standard_Real aN = -DOT (thePlane, aW);
121
122   if (Abs (aD) < Precision::Confusion())
123   {
124     if (Abs (aN) < Precision::Angular())
125     {
126       theDepth = DBL_MAX;
127       return;
128     }
129     else
130     {
131       theDepth = DBL_MAX;
132       return;
133     }
134   }
135
136   Standard_Real aParam = aN / aD;
137   if (aParam < 0.0 || aParam > 1.0)
138   {
139     theDepth = DBL_MAX;
140     return;
141   }
142
143   SelectMgr_Vec3 aClosestPnt = myNearPickedPnt + anU * aParam;
144   theDepth = DISTANCE (myNearPickedPnt, aClosestPnt);
145 }
146
147 // =======================================================================
148 // function : Build
149 // purpose  : Build volume according to the point and given pixel
150 //            tolerance
151 // =======================================================================
152 void SelectMgr_RectangularFrustum::Build (const gp_Pnt2d &thePoint)
153 {
154   myNearPickedPnt = myBuilder->ProjectPntOnViewPlane (thePoint.X(), thePoint.Y(), 0.0);
155   myFarPickedPnt  = myBuilder->ProjectPntOnViewPlane (thePoint.X(), thePoint.Y(), 1.0);
156   myViewRayDir = myFarPickedPnt - myNearPickedPnt;
157
158   // LeftTopNear
159   myVertices[0] = myBuilder->ProjectPntOnViewPlane (thePoint.X() - myPixelTolerance / 2.0,
160                                                     thePoint.Y() + myPixelTolerance / 2.0,
161                                                     0.0);
162   // LeftTopFar
163   myVertices[1] = myBuilder->ProjectPntOnViewPlane (thePoint.X() - myPixelTolerance / 2.0,
164                                                     thePoint.Y() + myPixelTolerance / 2.0,
165                                                     1.0);
166   // LeftBottomNear
167   myVertices[2] = myBuilder->ProjectPntOnViewPlane (thePoint.X() - myPixelTolerance / 2.0,
168                                                     thePoint.Y() - myPixelTolerance / 2.0,
169                                                     0.0);
170   // LeftBottomFar
171   myVertices[3] = myBuilder->ProjectPntOnViewPlane (thePoint.X() - myPixelTolerance / 2.0,
172                                                     thePoint.Y() - myPixelTolerance / 2.0,
173                                                     1.0);
174   // RightTopNear
175   myVertices[4] = myBuilder->ProjectPntOnViewPlane (thePoint.X() + myPixelTolerance / 2.0,
176                                                     thePoint.Y() + myPixelTolerance / 2.0,
177                                                     0.0);
178   // RightTopFar
179   myVertices[5] = myBuilder->ProjectPntOnViewPlane (thePoint.X() + myPixelTolerance / 2.0,
180                                                     thePoint.Y() + myPixelTolerance / 2.0,
181                                                     1.0);
182   // RightBottomNear
183   myVertices[6] = myBuilder->ProjectPntOnViewPlane (thePoint.X() + myPixelTolerance / 2.0,
184                                                     thePoint.Y() - myPixelTolerance / 2.0,
185                                                     0.0);
186   // RightBottomFar
187   myVertices[7] = myBuilder->ProjectPntOnViewPlane (thePoint.X() + myPixelTolerance / 2.0,
188                                                     thePoint.Y() - myPixelTolerance / 2.0,
189                                                     1.0);
190   // Top
191   myPlanes[0] = myBuilder->PlaneEquation (myVertices[1],
192                                           myVertices[0],
193                                           myVertices[5],
194                                           myVertices[6]);
195   // Bottom
196   myPlanes[1] = myBuilder->PlaneEquation (myVertices[3],
197                                           myVertices[2],
198                                           myVertices[7],
199                                           myVertices[4]);
200   // Left
201   myPlanes[2] = myBuilder->PlaneEquation (myVertices[1],
202                                           myVertices[0],
203                                           myVertices[2],
204                                           myVertices[6]);
205   // Right
206   myPlanes[3] = myBuilder->PlaneEquation (myVertices[5],
207                                           myVertices[4],
208                                           myVertices[6],
209                                           myVertices[2]);
210   // Near
211   myPlanes[4] = myBuilder->PlaneEquation (myVertices[4],
212                                           myVertices[6],
213                                           myVertices[2],
214                                           myVertices[3]);
215   // Far
216   myPlanes[5] = myBuilder->PlaneEquation (myVertices[5],
217                                           myVertices[7],
218                                           myVertices[3],
219                                           myVertices[2]);
220
221   for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < 6; ++aPlaneIdx)
222   {
223     Standard_Real aMax = -DBL_MAX;
224     Standard_Real aMin =  DBL_MAX;
225     const SelectMgr_Vec3 aPlane = myPlanes[aPlaneIdx];
226     for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
227     {
228       Standard_Real aProjection = DOT (aPlane, myVertices[aVertIdx]);
229       aMax = Max (aMax, aProjection);
230       aMin = Min (aMin, aProjection);
231     }
232     myMaxVertsProjections[aPlaneIdx] = aMax;
233     myMinVertsProjections[aPlaneIdx] = aMin;
234   }
235
236   SelectMgr_Vec3 aDimensions[3] =
237   {
238     SelectMgr_Vec3 (1.0, 0.0, 0.0),
239     SelectMgr_Vec3 (0.0, 1.0, 0.0),
240     SelectMgr_Vec3 (0.0, 0.0, 1.0)
241   };
242
243   for (Standard_Integer aDim = 0; aDim < 3; ++aDim)
244   {
245     Standard_Real aMax = -DBL_MAX;
246     Standard_Real aMin =  DBL_MAX;
247     for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
248     {
249       Standard_Real aProjection = DOT (aDimensions[aDim], myVertices[aVertIdx]);
250       aMax = Max (aProjection, aMax);
251       aMin = Min (aProjection, aMin);
252     }
253     myMaxOrthoVertsProjections[aDim] = aMax;
254     myMinOrthoVertsProjections[aDim] = aMin;
255   }
256
257   // Horizontal
258   myEdgeDirs[0] = myVertices[4] - myVertices[0];
259   // Vertical
260   myEdgeDirs[1] = myVertices[2] - myVertices[0];
261   // LeftLower
262   myEdgeDirs[2] = myVertices[2] - myVertices[3];
263   // RightLower
264   myEdgeDirs[3] = myVertices[6] - myVertices[7];
265   // LeftUpper
266   myEdgeDirs[4] = myVertices[0] - myVertices[1];
267   // RightUpper
268   myEdgeDirs[5] = myVertices[4] - myVertices[5];
269 }
270
271 // =======================================================================
272 // function : Build
273 // purpose  : Build volume according to the selected rectangle
274 // =======================================================================
275 void SelectMgr_RectangularFrustum::Build (const gp_Pnt2d& theMinPnt,
276                                           const gp_Pnt2d& theMaxPnt)
277 {
278   myNearPickedPnt = myBuilder->ProjectPntOnViewPlane ((theMinPnt.X() + theMaxPnt.X()) * 0.5,
279                                                       (theMinPnt.Y() + theMaxPnt.Y()) * 0.5,
280                                                       0.0);
281   myFarPickedPnt = myBuilder->ProjectPntOnViewPlane ((theMinPnt.X() + theMaxPnt.X()) * 0.5,
282                                                      (theMinPnt.Y() + theMaxPnt.Y()) * 0.5,
283                                                      1.0);
284   myViewRayDir = myFarPickedPnt - myNearPickedPnt;
285
286   // LeftTopNear
287   myVertices[0] = myBuilder->ProjectPntOnViewPlane (theMinPnt.X(),
288                                                     theMaxPnt.Y(),
289                                                     0.0);
290   // LeftTopFar
291   myVertices[1] = myBuilder->ProjectPntOnViewPlane (theMinPnt.X(),
292                                                     theMaxPnt.Y(),
293                                                     1.0);
294   // LeftBottomNear
295   myVertices[2] = myBuilder->ProjectPntOnViewPlane (theMinPnt.X(),
296                                                     theMinPnt.Y(),
297                                                     0.0);
298   // LeftBottomFar
299   myVertices[3] = myBuilder->ProjectPntOnViewPlane (theMinPnt.X(),
300                                                     theMinPnt.Y(),
301                                                     1.0);
302   // RightTopNear
303   myVertices[4] = myBuilder->ProjectPntOnViewPlane (theMaxPnt.X(),
304                                                     theMaxPnt.Y(),
305                                                     0.0);
306   // RightTopFar
307   myVertices[5] = myBuilder->ProjectPntOnViewPlane (theMaxPnt.X(),
308                                                     theMaxPnt.Y(),
309                                                     1.0);
310   // RightBottomNear
311   myVertices[6] = myBuilder->ProjectPntOnViewPlane (theMaxPnt.X(),
312                                                     theMinPnt.Y(),
313                                                     0.0);
314   // RightBottomFar
315   myVertices[7] = myBuilder->ProjectPntOnViewPlane (theMaxPnt.X() ,
316                                                     theMinPnt.Y(),
317                                                     1.0);
318
319   // Top
320   myPlanes[0] = myBuilder->PlaneEquation (myVertices[1],
321                                           myVertices[0],
322                                           myVertices[5],
323                                           myVertices[6]);
324   // Bottom
325   myPlanes[1] = myBuilder->PlaneEquation (myVertices[3],
326                                           myVertices[2],
327                                           myVertices[7],
328                                           myVertices[4]);
329   // Left
330   myPlanes[2] = myBuilder->PlaneEquation (myVertices[1],
331                                           myVertices[0],
332                                           myVertices[2],
333                                           myVertices[6]);
334   // Right
335   myPlanes[3] = myBuilder->PlaneEquation (myVertices[5],
336                                           myVertices[4],
337                                           myVertices[6],
338                                           myVertices[2]);
339   // Near
340   myPlanes[4] = myBuilder->PlaneEquation (myVertices[4],
341                                           myVertices[6],
342                                           myVertices[2],
343                                           myVertices[3]);
344   // Far
345   myPlanes[5] = myBuilder->PlaneEquation (myVertices[5],
346                                           myVertices[7],
347                                           myVertices[3],
348                                           myVertices[2]);
349
350   for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < 6; ++aPlaneIdx)
351   {
352     Standard_Real aMax = -DBL_MAX;
353     Standard_Real aMin =  DBL_MAX;
354     const SelectMgr_Vec3 aPlane = myPlanes[aPlaneIdx];
355     for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
356     {
357       Standard_Real aProjection = DOT (aPlane, myVertices[aVertIdx]);
358       aMax = Max (aMax, aProjection);
359       aMin = Min (aMin, aProjection);
360     }
361     myMaxVertsProjections[aPlaneIdx] = aMax;
362     myMinVertsProjections[aPlaneIdx] = aMin;
363   }
364
365   SelectMgr_Vec3 aDimensions[3] =
366   {
367     SelectMgr_Vec3 (1.0, 0.0, 0.0),
368     SelectMgr_Vec3 (0.0, 1.0, 0.0),
369     SelectMgr_Vec3 (0.0, 0.0, 1.0)
370   };
371
372   for (Standard_Integer aDim = 0; aDim < 3; ++aDim)
373   {
374     Standard_Real aMax = -DBL_MAX;
375     Standard_Real aMin =  DBL_MAX;
376     for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
377     {
378       Standard_Real aProjection = DOT (aDimensions[aDim], myVertices[aVertIdx]);
379       aMax = Max (aMax, aProjection);
380       aMin = Min (aMin, aProjection);
381     }
382     myMaxOrthoVertsProjections[aDim] = aMax;
383     myMinOrthoVertsProjections[aDim] = aMin;
384   }
385
386   // Horizontal
387   myEdgeDirs[0] = myVertices[4] - myVertices[0];
388   // Vertical
389   myEdgeDirs[1] = myVertices[2] - myVertices[0];
390   // LeftLower
391   myEdgeDirs[2] = myVertices[2] - myVertices[3];
392   // RightLower
393   myEdgeDirs[3] = myVertices[6] - myVertices[7];
394   // LeftUpper
395   myEdgeDirs[4] = myVertices[0] - myVertices[1];
396   // RightUpper
397   myEdgeDirs[5] = myVertices[4] - myVertices[5];
398 }
399
400 // =======================================================================
401 // function : Transform
402 // purpose  : Returns a copy of the frustum transformed according to the matrix given
403 // =======================================================================
404 NCollection_Handle<SelectMgr_BaseFrustum> SelectMgr_RectangularFrustum::Transform (const gp_Trsf& theTrsf)
405 {
406   SelectMgr_RectangularFrustum* aRes = new SelectMgr_RectangularFrustum();
407
408   aRes->myNearPickedPnt = SelectMgr_MatOp::Transform (theTrsf, myNearPickedPnt);
409   aRes->myFarPickedPnt  = SelectMgr_MatOp::Transform (theTrsf, myFarPickedPnt);
410   aRes->myViewRayDir    = aRes->myFarPickedPnt - aRes->myNearPickedPnt;
411
412   aRes->myIsOrthographic = myIsOrthographic;
413
414   // LeftTopNear
415   aRes->myVertices[0] = SelectMgr_MatOp::Transform (theTrsf, myVertices[0]);
416   // LeftTopFar
417   aRes->myVertices[1] = SelectMgr_MatOp::Transform (theTrsf, myVertices[1]);
418   // LeftBottomNear
419   aRes->myVertices[2] = SelectMgr_MatOp::Transform (theTrsf, myVertices[2]);
420   // LeftBottomFar
421   aRes->myVertices[3] = SelectMgr_MatOp::Transform (theTrsf, myVertices[3]);
422   // RightTopNear
423   aRes->myVertices[4] = SelectMgr_MatOp::Transform (theTrsf, myVertices[4]);
424   // RightTopFar
425   aRes->myVertices[5] = SelectMgr_MatOp::Transform (theTrsf, myVertices[5]);
426   // RightBottomNear
427   aRes->myVertices[6] = SelectMgr_MatOp::Transform (theTrsf, myVertices[6]);
428   // RightBottomFar
429   aRes->myVertices[7] = SelectMgr_MatOp::Transform (theTrsf, myVertices[7]);
430
431   // Top
432   aRes->myPlanes[0] = myBuilder->PlaneEquation (aRes->myVertices[1],
433                                                 aRes->myVertices[0],
434                                                 aRes->myVertices[5],
435                                                 aRes->myVertices[6]);
436   // Bottom
437   aRes->myPlanes[1] = myBuilder->PlaneEquation (aRes->myVertices[3],
438                                                 aRes->myVertices[2],
439                                                 aRes->myVertices[7],
440                                                 aRes->myVertices[4]);
441   // Left
442   aRes->myPlanes[2] = myBuilder->PlaneEquation (aRes->myVertices[1],
443                                                 aRes->myVertices[0],
444                                                 aRes->myVertices[2],
445                                                 aRes->myVertices[6]);
446   // Right
447   aRes->myPlanes[3] = myBuilder->PlaneEquation (aRes->myVertices[5],
448                                                 aRes->myVertices[4],
449                                                 aRes->myVertices[6],
450                                                 aRes->myVertices[2]);
451   // Near
452   aRes->myPlanes[4] = myBuilder->PlaneEquation (aRes->myVertices[4],
453                                                 aRes->myVertices[6],
454                                                 aRes->myVertices[2],
455                                                 aRes->myVertices[3]);
456   // Far
457   aRes->myPlanes[5] = myBuilder->PlaneEquation (aRes->myVertices[5],
458                                                 aRes->myVertices[7],
459                                                 aRes->myVertices[3],
460                                                 aRes->myVertices[2]);
461
462   for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < 6; ++aPlaneIdx)
463   {
464     Standard_Real aMax = -DBL_MAX;
465     Standard_Real aMin =  DBL_MAX;
466     const SelectMgr_Vec3 aPlane = aRes->myPlanes[aPlaneIdx];
467     for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
468     {
469       Standard_Real aProjection = DOT (aPlane, aRes->myVertices[aVertIdx]);
470       aMax = Max (aMax, aProjection);
471       aMin = Min (aMin, aProjection);
472     }
473     aRes->myMaxVertsProjections[aPlaneIdx] = aMax;
474     aRes->myMinVertsProjections[aPlaneIdx] = aMin;
475   }
476
477   SelectMgr_Vec3 aDimensions[3] =
478   {
479     SelectMgr_Vec3 (1.0, 0.0, 0.0),
480     SelectMgr_Vec3 (0.0, 1.0, 0.0),
481     SelectMgr_Vec3 (0.0, 0.0, 1.0)
482   };
483
484   for (Standard_Integer aDim = 0; aDim < 3; ++aDim)
485   {
486     Standard_Real aMax = -DBL_MAX;
487     Standard_Real aMin =  DBL_MAX;
488     for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
489     {
490       Standard_Real aProjection = DOT (aDimensions[aDim], aRes->myVertices[aVertIdx]);
491       aMax = Max (aMax, aProjection);
492       aMin = Min (aMin, aProjection);
493     }
494     aRes->myMaxOrthoVertsProjections[aDim] = aMax;
495     aRes->myMinOrthoVertsProjections[aDim] = aMin;
496   }
497
498   // Horizontal
499   aRes->myEdgeDirs[0] = aRes->myVertices[4] - aRes->myVertices[0];
500   // Vertical
501   aRes->myEdgeDirs[1] = aRes->myVertices[2] - aRes->myVertices[0];
502   // LeftLower
503   aRes->myEdgeDirs[2] = aRes->myVertices[2] - aRes->myVertices[3];
504   // RightLower
505   aRes->myEdgeDirs[3] = aRes->myVertices[6] - aRes->myVertices[7];
506   // LeftUpper
507   aRes->myEdgeDirs[4] = aRes->myVertices[0] - aRes->myVertices[1];
508   // RightUpper
509   aRes->myEdgeDirs[5] = aRes->myVertices[4] - aRes->myVertices[5];
510
511   return NCollection_Handle<SelectMgr_BaseFrustum> (aRes);
512 }
513
514 // =======================================================================
515 // function : Overlaps
516 // purpose  : Returns true if selecting volume is overlapped by
517 //            axis-aligned bounding box with minimum corner at point
518 //            theMinPnt and maximum at point theMaxPnt
519 // =======================================================================
520 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const SelectMgr_Vec3& theMinPnt,
521                                                          const SelectMgr_Vec3& theMaxPnt)
522 {
523   return hasOverlap (theMinPnt, theMaxPnt);
524 }
525
526 // =======================================================================
527 // function : Overlaps
528 // purpose  : SAT intersection test between defined volume and
529 //            given axis-aligned box
530 // =======================================================================
531 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const BVH_Box<Standard_Real, 3>& theBox,
532                                                          Standard_Real& theDepth)
533 {
534   const SelectMgr_Vec3& aMinPnt = theBox.CornerMin();
535   const SelectMgr_Vec3& aMaxPnt = theBox.CornerMax();
536   if (!hasOverlap (aMinPnt, aMaxPnt))
537     return Standard_False;
538
539   SelectMgr_Vec3 aNearestPnt = SelectMgr_Vec3 (RealLast(), RealLast(), RealLast());
540   aNearestPnt.x() = Max (Min (myNearPickedPnt.x(), aMaxPnt.x()), aMinPnt.x());
541   aNearestPnt.y() = Max (Min (myNearPickedPnt.y(), aMaxPnt.y()), aMinPnt.y());
542   aNearestPnt.z() = Max (Min (myNearPickedPnt.z(), aMaxPnt.z()), aMinPnt.z());
543
544   theDepth = DISTANCE (aNearestPnt, myNearPickedPnt);
545
546   return Standard_True;
547 }
548
549 // =======================================================================
550 // function : Overlaps
551 // purpose  : Intersection test between defined volume and given point
552 // =======================================================================
553 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt,
554                                                          Standard_Real& theDepth)
555 {
556   if (!hasOverlap (thePnt))
557     return Standard_False;
558
559   SelectMgr_Vec3 aPnt (thePnt.X(), thePnt.Y(), thePnt.Z());
560   SelectMgr_Vec3 aV = aPnt - myNearPickedPnt;
561   SelectMgr_Vec3 aDetectedPnt = myNearPickedPnt + myViewRayDir * (DOT (aV, myViewRayDir) / DOT (myViewRayDir, myViewRayDir));
562
563   theDepth = DISTANCE (aDetectedPnt, myNearPickedPnt);
564
565   return Standard_True;
566 }
567
568 // =======================================================================
569 // function : Overlaps
570 // purpose  : Checks if line segment overlaps selecting frustum
571 // =======================================================================
572 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt1,
573                                                          const gp_Pnt& thePnt2,
574                                                          Standard_Real& theDepth)
575 {
576   theDepth = -DBL_MAX;
577   if (!hasOverlap (thePnt1, thePnt2))
578     return Standard_False;
579
580   segmentSegmentDistance (thePnt1, thePnt2, theDepth);
581   return Standard_True;
582 }
583
584 // =======================================================================
585 // function : Overlaps
586 // purpose  : SAT intersection test between defined volume and given
587 //            ordered set of points, representing line segments. The test
588 //            may be considered of interior part or boundary line defined
589 //            by segments depending on given sensitivity type
590 // =======================================================================
591 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const Handle(TColgp_HArray1OfPnt)& theArrayOfPnts,
592                                                          Select3D_TypeOfSensitivity theSensType,
593                                                          Standard_Real& theDepth)
594 {
595   if (theSensType == Select3D_TOS_BOUNDARY)
596   {
597     Standard_Integer aMatchingSegmentsNb = -1;
598     theDepth = DBL_MAX;
599     Standard_Integer aLower = theArrayOfPnts->Lower();
600     Standard_Integer anUpper = theArrayOfPnts->Upper();
601
602     for (Standard_Integer aPntIter = aLower; aPntIter <= anUpper; ++aPntIter)
603     {
604       const gp_Pnt& aStartPnt = theArrayOfPnts->Value (aPntIter);
605       const gp_Pnt& aEndPnt = aPntIter == anUpper ? theArrayOfPnts->Value (aLower)
606         : theArrayOfPnts->Value (aPntIter + 1);
607
608       if (hasOverlap (aStartPnt, aEndPnt))
609       {
610         aMatchingSegmentsNb++;
611         Standard_Real aSegmentDepth = RealLast();
612         segmentSegmentDistance (aStartPnt, aEndPnt, aSegmentDepth);
613         theDepth = Min (theDepth, aSegmentDepth);
614       }
615     }
616
617     if (aMatchingSegmentsNb == -1)
618       return Standard_False;
619   }
620   else if (theSensType == Select3D_TOS_INTERIOR)
621   {
622     SelectMgr_Vec3 aPolyNorm (RealLast());
623     if (!hasOverlap (theArrayOfPnts, aPolyNorm))
624       return Standard_False;
625
626     segmentPlaneIntersection (aPolyNorm,
627                               theArrayOfPnts->Value (theArrayOfPnts->Lower()),
628                               theDepth);
629   }
630
631   return Standard_True;
632 }
633
634 // =======================================================================
635 // function : Overlaps
636 // purpose  : SAT intersection test between defined volume and given
637 //            triangle. The test may be considered of interior part or
638 //            boundary line defined by triangle vertices depending on
639 //            given sensitivity type
640 // =======================================================================
641 Standard_Boolean SelectMgr_RectangularFrustum::Overlaps (const gp_Pnt& thePnt1,
642                                                          const gp_Pnt& thePnt2,
643                                                          const gp_Pnt& thePnt3,
644                                                          Select3D_TypeOfSensitivity theSensType,
645                                                          Standard_Real& theDepth)
646 {
647   if (theSensType == Select3D_TOS_BOUNDARY)
648   {
649     Handle(TColgp_HArray1OfPnt) aPntsArray = new TColgp_HArray1OfPnt(1, 4);
650     aPntsArray->SetValue (1, thePnt1);
651     aPntsArray->SetValue (2, thePnt2);
652     aPntsArray->SetValue (3, thePnt3);
653     aPntsArray->SetValue (4, thePnt1);
654     return Overlaps (aPntsArray, Select3D_TOS_BOUNDARY, theDepth);
655   }
656   else if (theSensType == Select3D_TOS_INTERIOR)
657   {
658     SelectMgr_Vec3 aTriangleNormal (RealLast());
659     if (!hasOverlap (thePnt1, thePnt2, thePnt3, aTriangleNormal))
660       return Standard_False;
661
662     // check if intersection point belongs to triangle's interior part
663     SelectMgr_Vec3 aPnt1 (thePnt1.X(), thePnt1.Y(), thePnt1.Z());
664     SelectMgr_Vec3 aTrEdges[3] = { SelectMgr_Vec3 (thePnt2.X() - thePnt1.X(), thePnt2.Y() - thePnt1.Y(), thePnt2.Z() - thePnt1.Z()),
665                                    SelectMgr_Vec3 (thePnt3.X() - thePnt2.X(), thePnt3.Y() - thePnt2.Y(), thePnt3.Z() - thePnt2.Z()),
666                                    SelectMgr_Vec3 (thePnt1.X() - thePnt3.X(), thePnt1.Y() - thePnt3.Y(), thePnt1.Z() - thePnt3.Z()) };
667     SelectMgr_Vec3 anEdge = (aPnt1 - myNearPickedPnt) * (1.0 / DOT (aTriangleNormal, myViewRayDir));
668
669     Standard_Real aTime = DOT (aTriangleNormal, anEdge);
670
671     SelectMgr_Vec3 aVec = SelectMgr_Vec3 (myViewRayDir.y() * anEdge.z() - myViewRayDir.z() * anEdge.y(),
672                                           myViewRayDir.z() * anEdge.x() - myViewRayDir.x() * anEdge.z(),
673                                           myViewRayDir.x() * anEdge.y() - myViewRayDir.y() * anEdge.x());
674
675     Standard_Real anU = DOT (aVec, aTrEdges[2]);
676     Standard_Real aV  = DOT (aVec, aTrEdges[0]);
677
678     Standard_Boolean isInterior = (aTime >= 0.0) && (anU >= 0.0) && (aV >= 0.0) && (anU + aV <= 1.0);
679
680     if (isInterior)
681     {
682       SelectMgr_Vec3 aDetectedPnt = myNearPickedPnt + myViewRayDir * aTime;
683       theDepth = DISTANCE (myNearPickedPnt, aDetectedPnt);
684       return Standard_True;
685     }
686
687     gp_Pnt aPnts[3] = {thePnt1, thePnt2, thePnt3};
688     Standard_Real aMinDist = RealLast();
689     Standard_Integer aNearestEdgeIdx = -1;
690     SelectMgr_Vec3 aPtOnPlane = myNearPickedPnt + myViewRayDir * aTime;
691     for (Standard_Integer anEdgeIdx = 0; anEdgeIdx < 3; ++anEdgeIdx)
692     {
693       SelectMgr_Vec3 aW = SelectMgr_Vec3 (aPtOnPlane.x() - aPnts[anEdgeIdx].X(),
694                                           aPtOnPlane.y() - aPnts[anEdgeIdx].Y(),
695                                           aPtOnPlane.z() - aPnts[anEdgeIdx].Z());
696       Standard_Real aCoef = DOT (aTrEdges[anEdgeIdx], aW) / DOT (aTrEdges[anEdgeIdx], aTrEdges[anEdgeIdx]);
697       Standard_Real aDist = DISTANCE (aPtOnPlane, SelectMgr_Vec3 (aPnts[anEdgeIdx].X() + aCoef * aTrEdges[anEdgeIdx].x(),
698                                                                   aPnts[anEdgeIdx].Y() + aCoef * aTrEdges[anEdgeIdx].y(),
699                                                                   aPnts[anEdgeIdx].Z() + aCoef * aTrEdges[anEdgeIdx].z()));
700       if (aMinDist > aDist)
701       {
702         aMinDist = aDist;
703         aNearestEdgeIdx = anEdgeIdx;
704       }
705     }
706     segmentSegmentDistance (aPnts[aNearestEdgeIdx], aPnts[(aNearestEdgeIdx + 1) % 3], theDepth);
707   }
708
709   return Standard_True;
710 }
711
712 // =======================================================================
713 // function : DistToGeometryCenter
714 // purpose  : Measures distance between 3d projection of user-picked
715 //            screen point and given point theCOG
716 // =======================================================================
717 Standard_Real SelectMgr_RectangularFrustum::DistToGeometryCenter (const gp_Pnt& theCOG)
718 {
719   const SelectMgr_Vec3& aCOG = SelectMgr_Vec3 (theCOG.X(), theCOG.Y(), theCOG.Z());
720   return DISTANCE (aCOG, myNearPickedPnt);
721 }
722
723 // =======================================================================
724 // function : DetectedPoint
725 // purpose  : Calculates the point on a view ray that was detected during
726 //            the run of selection algo by given depth
727 // =======================================================================
728 SelectMgr_Vec3 SelectMgr_RectangularFrustum::DetectedPoint (const Standard_Real theDepth) const
729 {
730   return myNearPickedPnt + myViewRayDir * theDepth;
731 }
732
733 // =======================================================================
734 // function : IsClipped
735 // purpose  : Checks if the point of sensitive in which selection was
736 //            detected belongs to the region defined by clipping planes
737 // =======================================================================
738 Standard_Boolean SelectMgr_RectangularFrustum::IsClipped (const Graphic3d_SequenceOfHClipPlane& thePlanes,
739                                                           const Standard_Real theDepth)
740 {
741   Graphic3d_SequenceOfHClipPlane::Iterator aPlaneIt (thePlanes);
742   Standard_Real aMaxDepth = DBL_MAX;
743   Standard_Real aMinDepth = -DBL_MAX;
744   Standard_Real aPlaneA, aPlaneB, aPlaneC, aPlaneD;
745   for ( ; aPlaneIt.More(); aPlaneIt.Next())
746   {
747     const Handle(Graphic3d_ClipPlane)& aClipPlane = aPlaneIt.Value();
748     if (!aClipPlane->IsOn())
749       continue;
750
751     gp_Pln aGeomPlane = aClipPlane->ToPlane();
752
753     aGeomPlane.Coefficients (aPlaneA, aPlaneB, aPlaneC, aPlaneD);
754
755     const gp_XYZ& aPlaneDirXYZ = aGeomPlane.Axis().Direction().XYZ();
756
757     Standard_Real aDotProduct = DOTp (myViewRayDir, aPlaneDirXYZ);
758     Standard_Real aDistance = - (DOTp (myNearPickedPnt, aPlaneDirXYZ) + aPlaneD);
759
760     // check whether the pick line is parallel to clip plane
761     if (Abs (aDotProduct) < Precision::Angular())
762     {
763       // line lies below the plane and is not clipped, skip
764       continue;
765     }
766
767     // compute distance to point of pick line intersection with the plane
768     Standard_Real aParam = aDistance / aDotProduct;
769
770     // check if ray intersects the plane, in case aIntDist < 0
771     // the plane is "behind" the ray
772     if (aParam < 0.0)
773     {
774       continue;
775     }
776
777     const SelectMgr_Vec3 anIntersectionPt = myNearPickedPnt + myViewRayDir * aParam;
778     const Standard_Real aDistToPln = DISTANCE (anIntersectionPt, myNearPickedPnt);
779
780     // change depth limits for case of opposite and directed planes
781     if (aDotProduct < 0.0)
782     {
783       aMaxDepth = Min (aDistToPln, aMaxDepth);
784     }
785     else if (aDistToPln > aMinDepth)
786     {
787       aMinDepth = Max (aDistToPln, aMinDepth);
788     }
789   }
790
791   return (theDepth <= aMinDepth || theDepth >= aMaxDepth);
792 }