0032337: Visualization - rename Overlaps() method in selection to more self-describab...
[occt.git] / src / SelectMgr / SelectMgr_TriangularFrustumSet.cxx
1 // Created on: 2014-11-21
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 <BRepMesh_DataStructureOfDelaun.hxx>
17 #include <BRepMesh_Delaun.hxx>
18 #include <NCollection_IncAllocator.hxx>
19 #include <SelectMgr_FrustumBuilder.hxx>
20
21 #include <SelectMgr_TriangularFrustumSet.hxx>
22
23 #define MEMORY_BLOCK_SIZE 512 * 7
24
25 // =======================================================================
26 // function : SelectMgr_TriangularFrustumSet
27 // purpose  :
28 // =======================================================================
29 SelectMgr_TriangularFrustumSet::SelectMgr_TriangularFrustumSet()
30 :  myToAllowOverlap (Standard_False)
31 {
32 }
33
34 // =======================================================================
35 // function : Init
36 // purpose  :
37 // =======================================================================
38 void SelectMgr_TriangularFrustumSet::Init (const TColgp_Array1OfPnt2d& thePoints)
39 {
40   if (mySelPolyline.Points.IsNull())
41   {
42     mySelPolyline.Points = new TColgp_HArray1OfPnt2d (thePoints.Lower(), thePoints.Upper());
43   }
44   mySelPolyline.Points->Resize (thePoints.Lower(), thePoints.Upper(), false);
45   *mySelPolyline.Points = thePoints;
46   mySelectionType = SelectMgr_SelectionType_Polyline;
47 }
48
49 // =======================================================================
50 // function : Build
51 // purpose  : Meshes polygon bounded by polyline. Than organizes a set of
52 //            triangular frustums, where each triangle's projection onto
53 //            near and far view frustum planes is considered as a frustum
54 //            base
55 // =======================================================================
56 void SelectMgr_TriangularFrustumSet::Build()
57 {
58   Standard_ASSERT_RAISE (mySelectionType == SelectMgr_SelectionType_Polyline || !mySelPolyline.Points.IsNull(),
59     "Error! SelectMgr_TriangularFrustumSet::Build() should be called after selection frustum initialization");
60
61   myFrustums.Clear();
62
63   Handle(NCollection_IncAllocator) anAllocator = new NCollection_IncAllocator (MEMORY_BLOCK_SIZE);
64   Handle(BRepMesh_DataStructureOfDelaun) aMeshStructure = new BRepMesh_DataStructureOfDelaun (anAllocator);
65   Standard_Integer aPtsLower = mySelPolyline.Points->Lower();
66   Standard_Integer aPtsUpper = mySelPolyline.Points->Upper();
67   IMeshData::VectorOfInteger anIndexes (mySelPolyline.Points->Size(), anAllocator);
68   myBoundaryPoints.Resize (aPtsLower, aPtsLower + 2 * (mySelPolyline.Points->Size()) - 1, Standard_False);
69
70   for (Standard_Integer aPtIdx = aPtsLower; aPtIdx <= aPtsUpper; ++aPtIdx)
71   {
72     BRepMesh_Vertex aVertex (mySelPolyline.Points->Value (aPtIdx).XY(), aPtIdx, BRepMesh_Frontier);
73     anIndexes.Append (aMeshStructure->AddNode (aVertex));
74     const gp_Pnt aNearPnt = myBuilder->ProjectPntOnViewPlane (aVertex.Coord().X(), aVertex.Coord().Y(), 0.0);
75     const gp_Pnt aFarPnt  = myBuilder->ProjectPntOnViewPlane (aVertex.Coord().X(), aVertex.Coord().Y(), 1.0);
76     myBoundaryPoints.SetValue (aPtIdx, aNearPnt);
77     myBoundaryPoints.SetValue (aPtIdx + mySelPolyline.Points->Size(), aFarPnt);
78   }
79
80   Standard_Real aPtSum = 0;
81   for (Standard_Integer aIdx = aPtsLower; aIdx <= aPtsUpper; ++aIdx)
82   {
83     Standard_Integer aNextIdx = (aIdx % mySelPolyline.Points->Length()) + 1;
84     aPtSum += (mySelPolyline.Points->Value (aNextIdx).Coord().X() - mySelPolyline.Points->Value (aIdx).Coord().X())
85             * (mySelPolyline.Points->Value (aNextIdx).Coord().Y() + mySelPolyline.Points->Value (aIdx).Coord().Y());
86   }
87   Standard_Boolean isClockwiseOrdered = aPtSum < 0;
88
89   for (Standard_Integer aIdx = 0; aIdx < anIndexes.Length(); ++aIdx)
90   {
91     Standard_Integer aPtIdx = isClockwiseOrdered ? aIdx : (aIdx + 1) % anIndexes.Length();
92     Standard_Integer aNextPtIdx = isClockwiseOrdered ? (aIdx + 1) % anIndexes.Length() : aIdx;
93     BRepMesh_Edge anEdge (anIndexes.Value (aPtIdx),
94                           anIndexes.Value (aNextPtIdx),
95                           BRepMesh_Frontier);
96     aMeshStructure->AddLink (anEdge);
97   }
98
99   BRepMesh_Delaun aTriangulation (aMeshStructure, anIndexes);
100   const IMeshData::MapOfInteger& aTriangles = aMeshStructure->ElementsOfDomain();
101   if (aTriangles.Extent() < 1)
102     return;
103
104   IMeshData::IteratorOfMapOfInteger aTriangleIt (aTriangles);
105   for (; aTriangleIt.More(); aTriangleIt.Next())
106   {
107     const Standard_Integer aTriangleId = aTriangleIt.Key();
108     const BRepMesh_Triangle& aCurrentTriangle = aMeshStructure->GetElement (aTriangleId);
109
110     if (aCurrentTriangle.Movability() == BRepMesh_Deleted)
111       continue;
112
113     Standard_Integer aTriangleVerts[3];
114     aMeshStructure->ElementNodes (aCurrentTriangle, aTriangleVerts);
115
116     gp_Pnt2d aPts[3];
117     for (Standard_Integer aVertIdx = 0; aVertIdx < 3; ++aVertIdx)
118     {
119       const BRepMesh_Vertex& aVertex = aMeshStructure->GetNode (aTriangleVerts[aVertIdx]);
120       aPts[aVertIdx] = aVertex.Coord();
121     }
122
123     Handle(SelectMgr_TriangularFrustum) aTrFrustum = new SelectMgr_TriangularFrustum();
124     aTrFrustum->Init (aPts[0], aPts[1], aPts[2]);
125     aTrFrustum->SetBuilder (myBuilder);
126     aTrFrustum->Build();
127     myFrustums.Append (aTrFrustum);
128   }
129
130   aMeshStructure.Nullify();
131   anAllocator.Nullify();
132 }
133
134 // =======================================================================
135 // function : ScaleAndTransform
136 // purpose  : IMPORTANT: Scaling makes sense only for frustum built on a single point!
137 //            Note that this method does not perform any checks on type of the frustum.
138 //            Returns a copy of the frustum resized according to the scale factor given
139 //            and transforms it using the matrix given.
140 //            There are no default parameters, but in case if:
141 //                - transformation only is needed: @theScaleFactor must be initialized
142 //                  as any negative value;
143 //                - scale only is needed: @theTrsf must be set to gp_Identity.
144 // =======================================================================
145 Handle(SelectMgr_BaseIntersector) SelectMgr_TriangularFrustumSet::ScaleAndTransform (const Standard_Integer theScale,
146                                                                                      const gp_GTrsf& theTrsf,
147                                                                                      const Handle(SelectMgr_FrustumBuilder)& theBuilder) const
148 {
149   Standard_ASSERT_RAISE (mySelectionType == SelectMgr_SelectionType_Polyline,
150     "Error! SelectMgr_TriangularFrustumSet::ScaleAndTransform() should be called after selection frustum initialization");
151
152   Handle(SelectMgr_TriangularFrustumSet) aRes = new SelectMgr_TriangularFrustumSet();
153
154   for (SelectMgr_TriangFrustumsIter anIter (myFrustums); anIter.More(); anIter.Next())
155   {
156     aRes->myFrustums.Append (Handle(SelectMgr_TriangularFrustum)::DownCast (anIter.Value()->ScaleAndTransform (theScale, theTrsf, theBuilder)));
157   }
158
159   aRes->myBoundaryPoints.Resize (myBoundaryPoints.Lower(), myBoundaryPoints.Upper(), Standard_False);
160   for (Standard_Integer anIdx = myBoundaryPoints.Lower(); anIdx <= myBoundaryPoints.Upper(); anIdx++)
161   {
162     gp_Pnt aPoint = myBoundaryPoints.Value (anIdx);
163     theTrsf.Transforms (aPoint.ChangeCoord());
164     aRes->myBoundaryPoints.SetValue (anIdx, aPoint);
165   }
166
167   aRes->mySelectionType = mySelectionType;
168   aRes->mySelPolyline.Points = mySelPolyline.Points;
169   aRes->SetBuilder (theBuilder);
170   return aRes;
171 }
172
173 // =======================================================================
174 // function : OverlapsBox
175 // purpose  :
176 // =======================================================================
177 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsBox (const SelectMgr_Vec3& theMinPnt,
178                                                               const SelectMgr_Vec3& theMaxPnt,
179                                                               const SelectMgr_ViewClipRange& theClipRange,
180                                                               SelectBasics_PickResult& thePickResult) const
181 {
182   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
183     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
184
185   for (SelectMgr_TriangFrustumsIter anIter (myFrustums); anIter.More(); anIter.Next())
186   {
187     if (anIter.Value()->OverlapsBox (theMinPnt, theMaxPnt, theClipRange, thePickResult))
188       return Standard_True;
189   }
190
191   return Standard_False;
192 }
193
194 // =======================================================================
195 // function : OverlapsBox
196 // purpose  :
197 // =======================================================================
198 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsBox (const SelectMgr_Vec3& theMinPnt,
199                                                               const SelectMgr_Vec3& theMaxPnt,
200                                                               Standard_Boolean* theInside) const
201 {
202   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
203     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
204
205   for (SelectMgr_TriangFrustumsIter anIter (myFrustums); anIter.More(); anIter.Next())
206   {
207     if (anIter.Value()->OverlapsBox (theMinPnt, theMaxPnt, NULL))
208     {
209       if (myToAllowOverlap || theInside == NULL)
210       {
211         return Standard_True;
212       }
213       else
214       {
215         gp_Pnt aMinMaxPnts[2] = { gp_Pnt (theMinPnt.x(), theMinPnt.y(), theMinPnt.z()),
216                                   gp_Pnt (theMaxPnt.x(), theMaxPnt.y(), theMaxPnt.z())};
217
218         gp_Pnt anOffset[3] = { gp_Pnt (aMinMaxPnts[1].X() - aMinMaxPnts[0].X(), 0.0, 0.0),
219                                gp_Pnt (0.0, aMinMaxPnts[1].Y() - aMinMaxPnts[0].Y(), 0.0),
220                                gp_Pnt (0.0, 0.0, aMinMaxPnts[1].Z() - aMinMaxPnts[0].Z()) };
221
222         Standard_Integer aSign = 1;
223         for (Standard_Integer aPntsIdx = 0; aPntsIdx < 2; aPntsIdx++)
224         {
225           for (Standard_Integer aCoordIdx = 0; aCoordIdx < 3; aCoordIdx++)
226           {
227             gp_Pnt anOffsetPnt = aMinMaxPnts [aPntsIdx].XYZ() + aSign * anOffset [aCoordIdx].XYZ();
228             if (isIntersectBoundary (aMinMaxPnts [aPntsIdx], anOffsetPnt)
229              || isIntersectBoundary (anOffsetPnt, anOffsetPnt.XYZ() + aSign * anOffset [(aCoordIdx + 1) % 3].XYZ()))
230             {
231               *theInside &= Standard_False;
232               return Standard_True;
233             }
234           }
235           aSign = -aSign;
236         }
237         return Standard_True;
238       }
239     }
240   }
241
242   return Standard_False;
243 }
244
245 // =======================================================================
246 // function : OverlapsPoint
247 // purpose  :
248 // =======================================================================
249 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsPoint (const gp_Pnt& thePnt,
250                                                                 const SelectMgr_ViewClipRange& theClipRange,
251                                                                 SelectBasics_PickResult& thePickResult) const
252 {
253   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
254     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
255
256   for (SelectMgr_TriangFrustumsIter anIter (myFrustums); anIter.More(); anIter.Next())
257   {
258     if (anIter.Value()->OverlapsPoint (thePnt, theClipRange, thePickResult))
259       return Standard_True;
260   }
261
262   return Standard_False;
263 }
264
265 // =======================================================================
266 // function : OverlapsPolygon
267 // purpose  :
268 // =======================================================================
269 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsPolygon (const TColgp_Array1OfPnt& theArrayOfPts,
270                                                                   Select3D_TypeOfSensitivity theSensType,
271                                                                   const SelectMgr_ViewClipRange& theClipRange,
272                                                                   SelectBasics_PickResult& thePickResult) const
273 {
274   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
275     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
276
277   for (SelectMgr_TriangFrustumsIter anIter (myFrustums); anIter.More(); anIter.Next())
278   {
279     if (anIter.Value()->OverlapsPolygon (theArrayOfPts, theSensType, theClipRange, thePickResult))
280     {
281       if (myToAllowOverlap)
282       {
283         return Standard_True;
284       }
285       else
286       {
287         Standard_Integer aPtsLower = theArrayOfPts.Lower();
288         Standard_Integer aPtsUpper = theArrayOfPts.Upper();
289         for (Standard_Integer anIdx = aPtsLower; anIdx <= aPtsUpper; anIdx++)
290         {
291           if (isIntersectBoundary (theArrayOfPts.Value (anIdx), theArrayOfPts.Value (anIdx < aPtsUpper ? anIdx + 1 : aPtsLower)))
292           {
293             return Standard_False;
294           }
295         }
296         return Standard_True;
297       }
298     }
299   }
300
301   return Standard_False;
302 }
303
304 // =======================================================================
305 // function : OverlapsSegment
306 // purpose  :
307 // =======================================================================
308 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsSegment (const gp_Pnt& thePnt1,
309                                                                   const gp_Pnt& thePnt2,
310                                                                   const SelectMgr_ViewClipRange& theClipRange,
311                                                                   SelectBasics_PickResult& thePickResult) const
312 {
313   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
314     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
315
316   for (SelectMgr_TriangFrustumsIter anIter (myFrustums); anIter.More(); anIter.Next())
317   {
318     if (anIter.Value()->OverlapsSegment (thePnt1, thePnt2, theClipRange, thePickResult))
319     {
320       if (myToAllowOverlap)
321       {
322         return Standard_True;
323       }
324       else
325       {
326         if (isIntersectBoundary (thePnt1, thePnt2))
327         {
328           return Standard_False;
329         }
330         return Standard_True;
331       }
332     }
333   }
334
335   return Standard_False;
336 }
337
338 // =======================================================================
339 // function : OverlapsTriangle
340 // purpose  :
341 // =======================================================================
342 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsTriangle (const gp_Pnt& thePnt1,
343                                                                    const gp_Pnt& thePnt2,
344                                                                    const gp_Pnt& thePnt3,
345                                                                    Select3D_TypeOfSensitivity theSensType,
346                                                                    const SelectMgr_ViewClipRange& theClipRange,
347                                                                    SelectBasics_PickResult& thePickResult) const
348 {
349   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
350     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
351
352   for (SelectMgr_TriangFrustumsIter anIter (myFrustums); anIter.More(); anIter.Next())
353   {
354     if (anIter.Value()->OverlapsTriangle (thePnt1, thePnt2, thePnt3, theSensType, theClipRange, thePickResult))
355     {
356       if (myToAllowOverlap)
357       {
358         return Standard_True;
359       }
360       else
361       {
362         if (isIntersectBoundary (thePnt1, thePnt2)
363          || isIntersectBoundary (thePnt2, thePnt3)
364          || isIntersectBoundary (thePnt3, thePnt1))
365         {
366           return Standard_False;
367         }
368         return Standard_True;
369       }
370     }
371   }
372
373   return Standard_False;
374 }
375
376 // =======================================================================
377 // function : GetPlanes
378 // purpose  :
379 // =======================================================================
380 void SelectMgr_TriangularFrustumSet::GetPlanes (NCollection_Vector<SelectMgr_Vec4>& thePlaneEquations) const
381 {
382   thePlaneEquations.Clear();
383
384   for (SelectMgr_TriangFrustumsIter anIter (myFrustums); anIter.More(); anIter.Next())
385   {
386     anIter.Value()->GetPlanes (thePlaneEquations);
387   }
388 }
389
390 //=======================================================================
391 // function : SetAllowOverlapDetection
392 // purpose  :
393 //=======================================================================
394 void SelectMgr_TriangularFrustumSet::SetAllowOverlapDetection (const Standard_Boolean theIsToAllow)
395 {
396   myToAllowOverlap = theIsToAllow;
397 }
398
399 //=======================================================================
400 // function : isIntersectBoundary
401 // purpose  :
402 //=======================================================================
403 Standard_Boolean SelectMgr_TriangularFrustumSet::isIntersectBoundary (const gp_Pnt& thePnt1, const gp_Pnt& thePnt2) const
404 {
405   Standard_Integer aFacesNb = myBoundaryPoints.Size() / 2;
406   gp_Vec aDir = thePnt2.XYZ() - thePnt1.XYZ();
407   gp_Pnt anOrig = thePnt1;
408
409   for (Standard_Integer anIdx = myBoundaryPoints.Lower(); anIdx < aFacesNb + myBoundaryPoints.Lower(); anIdx++)
410   {
411     gp_Pnt aFace[4] = { myBoundaryPoints.Value (anIdx),
412                         myBoundaryPoints.Value (anIdx + aFacesNb),
413                         myBoundaryPoints.Value (anIdx % aFacesNb + 1 + aFacesNb),
414                         myBoundaryPoints.Value (anIdx % aFacesNb + 1) };
415
416     if (segmentTriangleIntersection (anOrig, aDir, aFace[0], aFace[1], aFace[2])
417      || segmentTriangleIntersection (anOrig, aDir, aFace[0], aFace[2], aFace[3]))
418     {
419       return Standard_True;
420     }
421   }
422   return Standard_False;
423 }
424
425 //=======================================================================
426 // function : segmentTriangleIntersection
427 // purpose  : Moller-Trumbore ray-triangle intersection test
428 //=======================================================================
429 Standard_Boolean SelectMgr_TriangularFrustumSet::segmentTriangleIntersection (const gp_Pnt& theOrig, const gp_Vec& theDir,
430                                                                               const gp_Pnt& theV1, const gp_Pnt& theV2, const gp_Pnt& theV3) const
431 {
432   gp_Vec        aPVec, aTVec, aQVec;
433   Standard_Real aD, aInvD, anU, aV, aT;
434
435   gp_Vec anEdge1 = theV2.XYZ() - theV1.XYZ();
436   gp_Vec anEdge2 = theV3.XYZ() - theV1.XYZ();
437
438   aPVec = theDir.Crossed (anEdge2);
439   aD = anEdge1.Dot (aPVec);
440   if (fabs (aD) < gp::Resolution())
441   {
442     return Standard_False;
443   }
444
445   aInvD = 1.0 / aD;
446   aTVec = theOrig.XYZ() - theV1.XYZ();
447   anU = aInvD * aTVec.Dot (aPVec);
448   if (anU < 0.0 || anU > 1.0)
449   {
450     return Standard_False;
451   }
452
453   aQVec = aTVec.Crossed (anEdge1);
454   aV = aInvD * theDir.Dot (aQVec);
455   if (aV < 0.0 || anU + aV > 1.0)
456   {
457     return Standard_False;
458   }
459
460   aT = aInvD * anEdge2.Dot (aQVec);
461   if (aT < 0 || aT > 1)
462   {
463     return Standard_False;
464   }
465
466   return Standard_True;
467 }
468
469 // =======================================================================
470 // function : DetectedPoint
471 // purpose  :
472 // =======================================================================
473 gp_Pnt SelectMgr_TriangularFrustumSet::DetectedPoint (const Standard_Real theDepth) const
474 {
475   (void )theDepth;
476   throw Standard_ProgramError ("SelectMgr_TriangularFrustumSet::DetectedPoint() should not be called for Polyline selection type");
477 }
478
479 //=======================================================================
480 //function : DumpJson
481 //purpose  : 
482 //=======================================================================
483 void SelectMgr_TriangularFrustumSet::DumpJson (Standard_OStream& theOStream, Standard_Integer theDepth) const
484 {
485   OCCT_DUMP_CLASS_BEGIN (theOStream, SelectMgr_TriangularFrustumSet)
486   OCCT_DUMP_BASE_CLASS (theOStream, theDepth, SelectMgr_BaseFrustum)
487
488   for (SelectMgr_TriangFrustumsIter anIter (myFrustums); anIter.More(); anIter.Next())
489   {
490     const Handle(SelectMgr_TriangularFrustum)& aFrustum = anIter.Value();
491     OCCT_DUMP_FIELD_VALUES_DUMPED (theOStream, theDepth, aFrustum.get())
492   }
493 }
494
495 #undef MEMORY_BLOCK_SIZE