0031875: Draw Harness, ViewerTest - command vaspects -mostContinuity lacks g1 and...
[occt.git] / src / IntPolyh / IntPolyh_Intersection.cxx
1 // Created on: 1999-03-03
2 // Created by: Fabrice SERVANT
3 // Copyright (c) 1999-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17
18 #include <IntPolyh_Intersection.hxx>
19
20 #include <Adaptor3d_HSurface.hxx>
21
22 #include <IntPolyh_Couple.hxx>
23 #include <IntPolyh_CoupleMapHasher.hxx>
24 #include <IntPolyh_MaillageAffinage.hxx>
25 #include <IntPolyh_SectionLine.hxx>
26 #include <IntPolyh_StartPoint.hxx>
27 #include <IntPolyh_Tools.hxx>
28 #include <IntPolyh_Triangle.hxx>
29
30 #include <NCollection_Map.hxx>
31
32 static Standard_Boolean IsAdvRequired(IntPolyh_PMaillageAffinage& theMaillage);
33
34 static Standard_Integer ComputeIntersection(IntPolyh_PMaillageAffinage& theMaillage);
35
36 static Standard_Boolean AnalyzeIntersection(IntPolyh_PMaillageAffinage& theMaillage);
37
38 //=======================================================================
39 //function : IntPolyh_Intersection
40 //purpose  : 
41 //=======================================================================
42 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_HSurface)& theS1,
43                                              const Handle(Adaptor3d_HSurface)& theS2)
44 {
45   mySurf1 = theS1;
46   mySurf2 = theS2;
47   myNbSU1 = 10;
48   myNbSV1 = 10;
49   myNbSU2 = 10;
50   myNbSV2 = 10;
51   myIsDone = Standard_False;
52   mySectionLines.Init(1000);
53   myTangentZones.Init(10000);
54   Perform();
55 }
56
57 //=======================================================================
58 //function : IntPolyh_Intersection
59 //purpose  : 
60 //=======================================================================
61 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_HSurface)& theS1,
62                                              const Standard_Integer            theNbSU1,
63                                              const Standard_Integer            theNbSV1,
64                                              const Handle(Adaptor3d_HSurface)& theS2,
65                                              const Standard_Integer            theNbSU2,
66                                              const Standard_Integer            theNbSV2)
67 {
68   mySurf1 = theS1;
69   mySurf2 = theS2;
70   myNbSU1 = theNbSU1;
71   myNbSV1 = theNbSV1;
72   myNbSU2 = theNbSU2;
73   myNbSV2 = theNbSV2;
74   myIsDone = Standard_False;
75   mySectionLines.Init(1000);
76   myTangentZones.Init(10000);
77   Perform();
78 }
79
80 //=======================================================================
81 //function : IntPolyh_Intersection
82 //purpose  : 
83 //=======================================================================
84 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_HSurface)& theS1,
85                                              const TColStd_Array1OfReal&       theUPars1,
86                                              const TColStd_Array1OfReal&       theVPars1,
87                                              const Handle(Adaptor3d_HSurface)& theS2,
88                                              const TColStd_Array1OfReal&       theUPars2,
89                                              const TColStd_Array1OfReal&       theVPars2)
90 {
91   mySurf1 = theS1;
92   mySurf2 = theS2;
93   myNbSU1 = theUPars1.Length();
94   myNbSV1 = theVPars1.Length();
95   myNbSU2 = theUPars2.Length();
96   myNbSV2 = theVPars2.Length();
97   myIsDone = Standard_False;
98   mySectionLines.Init(1000);
99   myTangentZones.Init(10000);
100   Perform(theUPars1, theVPars1, theUPars2, theVPars2);
101 }
102
103 //=======================================================================
104 //function : GetLinePoint
105 //purpose  : 
106 //=======================================================================
107 void IntPolyh_Intersection::GetLinePoint(const Standard_Integer Indexl,
108                                          const Standard_Integer Indexp,
109                                          Standard_Real &x,
110                                          Standard_Real &y,
111                                          Standard_Real &z,
112                                          Standard_Real &u1,
113                                          Standard_Real &v1,
114                                          Standard_Real &u2,
115                                          Standard_Real &v2,
116                                          Standard_Real &incidence) const
117 {
118   const IntPolyh_SectionLine  &msl = mySectionLines[Indexl - 1];
119   const IntPolyh_StartPoint   &sp = msl[Indexp - 1];
120   x = sp.X();
121   y = sp.Y();
122   z = sp.Z();
123   u1 = sp.U1();
124   v1 = sp.V1();
125   u2 = sp.U2();
126   v2 = sp.V2();
127   incidence = sp.GetAngle();
128 }
129
130 //=======================================================================
131 //function : GetTangentZonePoint
132 //purpose  : 
133 //=======================================================================
134 void IntPolyh_Intersection::GetTangentZonePoint(const Standard_Integer Indexz,
135                                                 const Standard_Integer /*Indexp*/,
136                                                 Standard_Real &x,
137                                                 Standard_Real &y,
138                                                 Standard_Real &z,
139                                                 Standard_Real &u1,
140                                                 Standard_Real &v1,
141                                                 Standard_Real &u2,
142                                                 Standard_Real &v2) const
143 {
144   const IntPolyh_StartPoint   &sp = myTangentZones[Indexz - 1];
145   x = sp.X();
146   y = sp.Y();
147   z = sp.Z();
148   u1 = sp.U1();
149   v1 = sp.V1();
150   u2 = sp.U2();
151   v2 = sp.V2();
152 }
153
154 //=======================================================================
155 //function : Perform
156 //purpose  : 
157 //=======================================================================
158 void IntPolyh_Intersection::Perform()
159 {
160   // Prepare the sampling of the surfaces - UV parameters of the triangulation nodes
161   TColStd_Array1OfReal UPars1, VPars1, UPars2, VPars2;
162   IntPolyh_Tools::MakeSampling(mySurf1, myNbSU1, myNbSV1, Standard_False, UPars1, VPars1);
163   IntPolyh_Tools::MakeSampling(mySurf2, myNbSU2, myNbSV2, Standard_False, UPars2, VPars2);
164
165   // Perform intersection
166   Perform(UPars1, VPars1, UPars2, VPars2);
167 }
168
169 //=======================================================================
170 //function : Perform
171 //purpose  : 
172 //=======================================================================
173 void IntPolyh_Intersection::Perform(const TColStd_Array1OfReal& theUPars1,
174                                     const TColStd_Array1OfReal& theVPars1,
175                                     const TColStd_Array1OfReal& theUPars2,
176                                     const TColStd_Array1OfReal& theVPars2)
177 {
178   myIsDone = Standard_True;
179
180   // Compute the deflection of the given sampling if it is not set
181   Standard_Real aDeflTol1 = IntPolyh_Tools::ComputeDeflection(mySurf1, theUPars1, theVPars1);
182   Standard_Real aDeflTol2 = IntPolyh_Tools::ComputeDeflection(mySurf2, theUPars2, theVPars2);
183
184   // Perform standard intersection
185   IntPolyh_PMaillageAffinage pMaillageStd = 0;
186   Standard_Integer           nbCouplesStd = 0;
187   Standard_Boolean isStdDone = PerformStd(theUPars1, theVPars1,
188                                           theUPars2, theVPars2,
189                                           aDeflTol1, aDeflTol2,
190                                           pMaillageStd, nbCouplesStd);
191
192   if (!isStdDone)
193   {
194     // Intersection not done
195     myIsDone = Standard_False;
196     if (pMaillageStd) delete pMaillageStd;
197     return;
198   }
199
200   if (!IsAdvRequired(pMaillageStd))
201   {
202     // Default interference done well, use it
203     pMaillageStd->StartPointsChain(mySectionLines, myTangentZones);
204   }
205   else
206   {
207     // Default intersection is done, but too few interferences found.
208     // Perform advanced intersection - perform intersection four times with different shifts.
209     IntPolyh_PMaillageAffinage pMaillageFF = 0;
210     IntPolyh_PMaillageAffinage pMaillageFR = 0;
211     IntPolyh_PMaillageAffinage pMaillageRF = 0;
212     IntPolyh_PMaillageAffinage pMaillageRR = 0;
213     Standard_Integer           nbCouplesAdv = 0;
214
215     Standard_Boolean isAdvDone = PerformAdv(theUPars1, theVPars1,
216                                               theUPars2, theVPars2,
217                                               aDeflTol1, aDeflTol2,
218                                               pMaillageFF,
219                                               pMaillageFR,
220                                               pMaillageRF,
221                                               pMaillageRR,
222                                               nbCouplesAdv);
223
224     if (isAdvDone && nbCouplesAdv > 0)
225     {
226       // Advanced interference found
227       pMaillageFF->StartPointsChain(mySectionLines, myTangentZones);
228       pMaillageFR->StartPointsChain(mySectionLines, myTangentZones);
229       pMaillageRF->StartPointsChain(mySectionLines, myTangentZones);
230       pMaillageRR->StartPointsChain(mySectionLines, myTangentZones);
231     }
232     else
233     {
234       // Advanced intersection not done or no intersection is found -> use standard intersection
235       if (nbCouplesStd > 0)
236         pMaillageStd->StartPointsChain(mySectionLines, myTangentZones);
237     }
238
239     // Clean up
240     if (pMaillageFF) delete pMaillageFF;
241     if (pMaillageFR) delete pMaillageFR;
242     if (pMaillageRF) delete pMaillageRF;
243     if (pMaillageRR) delete pMaillageRR;
244   }
245
246   // clean up
247   if (pMaillageStd) delete pMaillageStd;
248 }
249
250 //=======================================================================
251 //function : PerformStd
252 //purpose  : 
253 //=======================================================================
254 Standard_Boolean IntPolyh_Intersection::PerformStd(const TColStd_Array1OfReal& theUPars1,
255                                                    const TColStd_Array1OfReal& theVPars1,
256                                                    const TColStd_Array1OfReal& theUPars2,
257                                                    const TColStd_Array1OfReal& theVPars2,
258                                                    const Standard_Real         theDeflTol1,
259                                                    const Standard_Real         theDeflTol2,
260                                                    IntPolyh_PMaillageAffinage& theMaillageS,
261                                                    Standard_Integer&           theNbCouples)
262 {
263   Standard_Boolean isDone = PerformMaillage(theUPars1, theVPars1,
264                                             theUPars2, theVPars2,
265                                             theDeflTol1, theDeflTol2,
266                                             theMaillageS);
267   theNbCouples = (isDone) ? (theMaillageS->GetCouples().Extent()) : 0;
268   return isDone;
269 }
270
271 //=======================================================================
272 //function : PerformAdv
273 //purpose  : 
274 //=======================================================================
275 Standard_Boolean IntPolyh_Intersection::PerformAdv(const TColStd_Array1OfReal& theUPars1,
276                                                    const TColStd_Array1OfReal& theVPars1,
277                                                    const TColStd_Array1OfReal& theUPars2,
278                                                    const TColStd_Array1OfReal& theVPars2,
279                                                    const Standard_Real         theDeflTol1,
280                                                    const Standard_Real         theDeflTol2,
281                                                    IntPolyh_PMaillageAffinage& theMaillageFF,
282                                                    IntPolyh_PMaillageAffinage& theMaillageFR,
283                                                    IntPolyh_PMaillageAffinage& theMaillageRF,
284                                                    IntPolyh_PMaillageAffinage& theMaillageRR,
285                                                    Standard_Integer&           theNbCouples)
286 {
287   // Compute the points on the surface and normal directions in these points
288   IntPolyh_ArrayOfPointNormal aPoints1, aPoints2;
289   IntPolyh_Tools::FillArrayOfPointNormal(mySurf1, theUPars1, theVPars1, aPoints1);
290   IntPolyh_Tools::FillArrayOfPointNormal(mySurf2, theUPars2, theVPars2, aPoints2);
291
292   // Perform intersection with the different shifts of the triangles
293   Standard_Boolean isDone =
294     PerformMaillage(theUPars1, theVPars1, theUPars2, theVPars2, // sampling
295                     theDeflTol1, theDeflTol2,                   // deflection tolerance
296                     aPoints1, aPoints2,                         // points and normals
297                     Standard_True , Standard_False,             // shift
298                     theMaillageFR)
299                     &&
300     PerformMaillage(theUPars1, theVPars1, theUPars2, theVPars2, // sampling
301                     theDeflTol1, theDeflTol2,                   // deflection tolerance
302                     aPoints1, aPoints2,                         // points and normals
303                     Standard_False, Standard_True,              // shift
304                     theMaillageRF)
305                     &&
306     PerformMaillage(theUPars1, theVPars1, theUPars2, theVPars2, // sampling
307                     theDeflTol1, theDeflTol2,                   // deflection tolerance
308                     aPoints1, aPoints2,                         // points and normals
309                     Standard_True, Standard_True,               // shift
310                     theMaillageFF)
311                     &&
312     PerformMaillage(theUPars1, theVPars1, theUPars2, theVPars2, // sampling
313                     theDeflTol1, theDeflTol2,                   // deflection tolerance
314                     aPoints1, aPoints2,                         // points and normals
315                     Standard_False, Standard_False,             // shift
316                     theMaillageRR);
317
318   if (isDone)
319   {
320     theNbCouples = theMaillageFF->GetCouples().Extent() +
321                    theMaillageFR->GetCouples().Extent() +
322                    theMaillageRF->GetCouples().Extent() +
323                    theMaillageRR->GetCouples().Extent();
324
325     // Merge couples
326     if(theNbCouples > 0)
327       MergeCouples(theMaillageFF->GetCouples(),
328                    theMaillageFR->GetCouples(),
329                    theMaillageRF->GetCouples(),
330                    theMaillageRR->GetCouples());
331   }
332
333   return isDone;
334 }
335
336 //=======================================================================
337 //function : PerformMaillage
338 //purpose  : Computes standard MaillageAffinage (without shift)
339 //=======================================================================
340 Standard_Boolean IntPolyh_Intersection::PerformMaillage(const TColStd_Array1OfReal& theUPars1,
341                                                         const TColStd_Array1OfReal& theVPars1,
342                                                         const TColStd_Array1OfReal& theUPars2,
343                                                         const TColStd_Array1OfReal& theVPars2,
344                                                         const Standard_Real         theDeflTol1,
345                                                         const Standard_Real         theDeflTol2,
346                                                         IntPolyh_PMaillageAffinage& theMaillage)
347 {
348   theMaillage =
349     new IntPolyh_MaillageAffinage(mySurf1, theUPars1.Length(), theVPars1.Length(),
350                                   mySurf2, theUPars2.Length(), theVPars2.Length(),
351                                   0);
352
353   theMaillage->FillArrayOfPnt(1, theUPars1, theVPars1, &theDeflTol1);
354   theMaillage->FillArrayOfPnt(2, theUPars2, theVPars2, &theDeflTol2);
355
356   Standard_Integer FinTTC = ComputeIntersection(theMaillage);
357
358   // If no intersecting triangles are found, try enlarged surfaces
359   if (FinTTC == 0)
360   {
361     // Check if enlarge for the surfaces is possible
362     Standard_Boolean isEnlargeU1, isEnlargeV1, isEnlargeU2, isEnlargeV2;
363     IntPolyh_Tools::IsEnlargePossible(mySurf1, isEnlargeU1, isEnlargeV1);
364     IntPolyh_Tools::IsEnlargePossible(mySurf2, isEnlargeU2, isEnlargeV2);
365
366     if (isEnlargeU1 || isEnlargeV1 || isEnlargeU2 || isEnlargeV2)
367     {
368       theMaillage->SetEnlargeZone(Standard_True);
369       // Make new points on the enlarged surface
370       theMaillage->FillArrayOfPnt(1);
371       theMaillage->FillArrayOfPnt(2);
372       // Compute intersection
373       ComputeIntersection(theMaillage);
374       theMaillage->SetEnlargeZone(Standard_False);
375     }
376   }
377
378   // if too many intersections, consider surfaces parallel
379   return AnalyzeIntersection(theMaillage);
380 }
381
382 //=======================================================================
383 //function : PerformMaillage
384 //purpose  : Computes MaillageAffinage
385 //=======================================================================
386 Standard_Boolean IntPolyh_Intersection::PerformMaillage(const TColStd_Array1OfReal& theUPars1,
387                                                         const TColStd_Array1OfReal& theVPars1,
388                                                         const TColStd_Array1OfReal& theUPars2,
389                                                         const TColStd_Array1OfReal& theVPars2,
390                                                         const Standard_Real         theDeflTol1,
391                                                         const Standard_Real         theDeflTol2,
392                                                         const IntPolyh_ArrayOfPointNormal& thePoints1,
393                                                         const IntPolyh_ArrayOfPointNormal& thePoints2,
394                                                         const Standard_Boolean      theIsFirstFwd,
395                                                         const Standard_Boolean      theIsSecondFwd,
396                                                         IntPolyh_PMaillageAffinage& theMaillage)
397 {
398   theMaillage =
399     new IntPolyh_MaillageAffinage(mySurf1, theUPars1.Length(), theVPars1.Length(),
400                                   mySurf2, theUPars2.Length(), theVPars2.Length(),
401                                   0);
402
403   theMaillage->FillArrayOfPnt(1, theIsFirstFwd , thePoints1, theUPars1, theVPars1, theDeflTol1);
404   theMaillage->FillArrayOfPnt(2, theIsSecondFwd, thePoints2, theUPars2, theVPars2, theDeflTol2);
405
406   ComputeIntersection(theMaillage);
407
408   return AnalyzeIntersection(theMaillage);
409 }
410
411 //=======================================================================
412 //function : MergeCouples
413 //purpose  : This method analyzes the lists to find same couples.
414 //           If some are detected it leaves the couple in only one list
415 //           deleting from others.
416 //=======================================================================
417 void IntPolyh_Intersection::MergeCouples(IntPolyh_ListOfCouples &anArrayFF,
418                                          IntPolyh_ListOfCouples &anArrayFR,
419                                          IntPolyh_ListOfCouples &anArrayRF,
420                                          IntPolyh_ListOfCouples &anArrayRR) const
421 {
422   // Fence map to remove from the lists the duplicating elements.
423   NCollection_Map<IntPolyh_Couple, IntPolyh_CoupleMapHasher> aFenceMap;
424   //
425   IntPolyh_ListOfCouples* pLists[4] = {&anArrayFF, &anArrayFR, &anArrayRF, &anArrayRR};
426   for (Standard_Integer i = 0; i < 4; ++i) {
427     IntPolyh_ListIteratorOfListOfCouples aIt(*pLists[i]);
428     for (; aIt.More();) {
429       if (!aFenceMap.Add(aIt.Value())) {
430         pLists[i]->Remove(aIt);
431         continue;
432       }
433       aIt.Next();
434     }
435   }
436 }
437
438 //=======================================================================
439 //function : IsAdvRequired
440 //purpose  : Analyzes the standard intersection on the angles between triangles.
441 //           If the angle between some of the interfering triangles is
442 //           too small (less than 5 deg), the advanced intersection is required.
443 //           Otherwise, the standard intersection is considered satisfactory.
444 //=======================================================================
445 Standard_Boolean IsAdvRequired(IntPolyh_PMaillageAffinage& theMaillage)
446 {
447   if (!theMaillage)
448     return Standard_True;
449
450   // Interfering triangles
451   IntPolyh_ListOfCouples& Couples = theMaillage->GetCouples();
452   // Number of interfering pairs
453   Standard_Integer aNbCouples = Couples.Extent();
454   // Flag to define whether advanced intersection is required or not
455   Standard_Boolean isAdvReq = (aNbCouples == 0);
456   if (isAdvReq)
457     // No interfering triangles are found -> perform advanced intersection
458     return isAdvReq;
459
460   if (aNbCouples > 10)
461     // Enough interfering triangles are found -> no need to perform advanced intersection
462     return isAdvReq;
463
464   const Standard_Real anEps = .996; //~ cos of 5 deg
465   IntPolyh_ListIteratorOfListOfCouples aIt(Couples);
466   for(; aIt.More(); aIt.Next())
467   {
468     if (Abs(aIt.Value().Angle()) > anEps)
469     {
470       // The angle between interfering triangles is small -> perform advanced
471       // intersection to make intersection more precise
472       isAdvReq = Standard_True;
473       break;
474     }
475   }
476
477   return isAdvReq;
478 }
479
480 //=======================================================================
481 //function : ComputeIntersection
482 //purpose  : Computes the intersection of the triangles
483 //=======================================================================
484 Standard_Integer ComputeIntersection(IntPolyh_PMaillageAffinage& theMaillage)
485 {
486   if (!theMaillage)
487     return 0;
488
489   // Compute common box and mark the points inside that box
490   theMaillage->CommonBox();
491
492   // Make triangles
493   theMaillage->FillArrayOfTriangles(1);
494   theMaillage->FillArrayOfTriangles(2);
495
496   // Make edges
497   theMaillage->FillArrayOfEdges(1);
498   theMaillage->FillArrayOfEdges(2);
499
500   // Deflection refinement
501   theMaillage->TrianglesDeflectionsRefinementBSB();
502
503   return theMaillage->TriangleCompare();
504 }
505
506 //=======================================================================
507 //function : AnalyzeIntersection
508 //purpose  : Analyzes the intersection on the number of interfering triangles
509 //=======================================================================
510 Standard_Boolean AnalyzeIntersection(IntPolyh_PMaillageAffinage& theMaillage)
511 {
512   if (!theMaillage)
513     return Standard_False;
514
515   IntPolyh_ListOfCouples& Couples = theMaillage->GetCouples();
516   Standard_Integer FinTTC = Couples.Extent();
517   if(FinTTC > 200)
518   {
519     const Standard_Real eps = .996; //~ cos of 5deg.
520     Standard_Integer npara = 0;
521     IntPolyh_ListIteratorOfListOfCouples aIt(Couples);
522     for(; aIt.More(); aIt.Next())
523     {
524       Standard_Real cosa = Abs(aIt.Value().Angle());
525       if(cosa > eps) ++npara;
526     }
527
528     if (npara >= theMaillage->GetArrayOfTriangles(1).NbItems() ||
529         npara >= theMaillage->GetArrayOfTriangles(2).NbItems())
530     {
531       return Standard_False;
532     }
533   }
534   return Standard_True;
535 }