0025890: Intersection algorithm produces curves overlaped
[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 //  modified by Edward AGAPOV (eap) Tue Jan 22 12:29:55 2002 (occ53)
18 //  Modified by skv - Thu Sep 25 18:24:29 2003 OCC567
19
20 #include <IntPolyh_Intersection.ixx>
21 #include <IntPolyh_SectionLine.hxx>
22 #include <IntPolyh_StartPoint.hxx>
23 #include <IntPolyh_MaillageAffinage.hxx>
24 #include <IntPolyh_Couple.hxx>
25 #include <IntPolyh_Triangle.hxx>
26
27 Standard_Integer MYDISPLAY = 0;
28 Standard_Integer MYPRINT   = 0;
29
30 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_HSurface)& S1,
31                                              const Handle(Adaptor3d_HSurface)& S2)
32 {
33   myNbSU1 = -1;
34   myNbSV1 = -1;
35   myNbSU2 = -1; 
36   myNbSV2 = -1; 
37   mySurf1 = S1;
38   mySurf2 = S2;
39   done = Standard_False;
40   TSectionLines.Init(1000);
41   TTangentZones.Init(10000);
42   Perform();
43 }
44
45 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_HSurface)& S1,
46                                              const Standard_Integer NbSU1,
47                                              const Standard_Integer NbSV1,
48                                              const Handle(Adaptor3d_HSurface)& S2,
49                                              const Standard_Integer NbSU2,
50                                              const Standard_Integer NbSV2)
51 {
52   myNbSU1 = NbSU1;
53   myNbSV1 = NbSV1;
54   myNbSU2 = NbSU2; 
55   myNbSV2 = NbSV2; 
56   mySurf1 = S1;
57   mySurf2 = S2;
58   done = Standard_False;
59   TSectionLines.Init(1000);
60   TTangentZones.Init(10000);
61   Perform();
62 }
63
64 void IntPolyh_Intersection::Perform() { 
65
66   done = Standard_True;
67
68   Standard_Boolean startFromAdvanced = Standard_False;
69   Standard_Boolean isStdDone = Standard_False;
70   Standard_Boolean isAdvDone = Standard_False;
71   Standard_Integer nbCouplesStd = 0;
72   Standard_Integer nbCouplesAdv = 0;
73   
74   //GeomAbs_SurfaceType ST1 = mySurf1->GetType();
75   //GeomAbs_SurfaceType ST2 = mySurf2->GetType();
76
77 //   if(ST1 == GeomAbs_Torus || ST2 == GeomAbs_Torus)
78 //     startFromAdvanced = Standard_True;
79   
80   IntPolyh_PMaillageAffinage aPMaillageStd = 0;
81   IntPolyh_PMaillageAffinage aPMaillageFF = 0;
82   IntPolyh_PMaillageAffinage aPMaillageFR = 0;
83   IntPolyh_PMaillageAffinage aPMaillageRF = 0;
84   IntPolyh_PMaillageAffinage aPMaillageRR = 0;
85
86
87   if(!startFromAdvanced) {
88
89     isStdDone = PerformStd(aPMaillageStd,nbCouplesStd);
90
91     // default interference done well, use it
92     if(isStdDone && nbCouplesStd > 10) {
93       aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
94     }
95     // default interference done, but too few interferences foud;
96     // use advanced interference
97     else if(isStdDone && nbCouplesStd <= 10) {
98       isAdvDone = PerformAdv(aPMaillageFF,aPMaillageFR,aPMaillageRF,aPMaillageRR,nbCouplesAdv);
99       
100       // advanced interference found
101       if(isAdvDone && nbCouplesAdv > 10) {
102         aPMaillageFF->StartPointsChain(TSectionLines,TTangentZones);
103         aPMaillageFR->StartPointsChain(TSectionLines,TTangentZones);
104         aPMaillageRF->StartPointsChain(TSectionLines,TTangentZones);
105         aPMaillageRR->StartPointsChain(TSectionLines,TTangentZones);
106       }
107       else {
108         // use result of default
109         if(nbCouplesStd > 0)
110           aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
111       }
112     }
113     // default interference faild, use advanced
114     else {
115 //       isAdvDone = PerformAdv(aPMaillageFF,aPMaillageFR,aPMaillageRF,aPMaillageRR,nbCouplesAdv);
116       
117 //       if(isAdvDone && nbCouplesAdv > 0) {cout << "4adv done, nbc: " << nbCouplesAdv << endl;
118 //      aPMaillageFF->StartPointsChain(TSectionLines,TTangentZones);
119 //      aPMaillageFR->StartPointsChain(TSectionLines,TTangentZones);
120 //      aPMaillageRF->StartPointsChain(TSectionLines,TTangentZones);
121 //      aPMaillageRR->StartPointsChain(TSectionLines,TTangentZones);
122 //       }
123     }
124   }// start from default
125   else {
126     
127     isAdvDone = PerformAdv(aPMaillageFF,aPMaillageFR,aPMaillageRF,aPMaillageRR,nbCouplesAdv);
128
129     // advanced done, interference found; use it
130     if(isAdvDone) {
131
132       if(nbCouplesAdv > 0) {
133         aPMaillageFF->StartPointsChain(TSectionLines,TTangentZones);
134         aPMaillageFR->StartPointsChain(TSectionLines,TTangentZones);
135         aPMaillageRF->StartPointsChain(TSectionLines,TTangentZones);
136         aPMaillageRR->StartPointsChain(TSectionLines,TTangentZones);
137       }
138       else {
139         isStdDone = PerformStd(aPMaillageStd,nbCouplesStd);
140         if(isStdDone && nbCouplesStd > 0)
141           aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
142       }
143     }
144     else {
145       isStdDone = PerformStd(aPMaillageStd,nbCouplesStd);
146       if(isStdDone && nbCouplesStd > 0)
147         aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
148     }
149   } // start from advanced
150
151   // accept result
152   nbsectionlines = TSectionLines.NbItems();
153   nbtangentzones = TTangentZones.NbItems();
154
155   // clean up
156   if(aPMaillageStd) delete aPMaillageStd;
157   if(aPMaillageFF) delete aPMaillageFF;
158   if(aPMaillageFR) delete aPMaillageFR;
159   if(aPMaillageRF) delete aPMaillageRF;
160   if(aPMaillageRR) delete aPMaillageRR;
161
162   // verify
163   if(!isStdDone && !isAdvDone)
164     done = Standard_False;
165 }
166
167
168 Standard_Boolean IntPolyh_Intersection::IsDone() const {
169   return(done);
170 }
171
172
173 Standard_Integer IntPolyh_Intersection::NbSectionLines() const { 
174   return(nbsectionlines);
175 }
176
177
178 Standard_Integer IntPolyh_Intersection::NbPointsInLine(const Standard_Integer IndexLine) const { 
179   
180   return(TSectionLines[IndexLine-1].NbStartPoints());
181 }
182
183
184 Standard_Integer IntPolyh_Intersection::NbPointsInTangentZone(const Standard_Integer) const {   
185   //-- IndexLine--;     (pas implemente) Attention : Tableaux de 0 a n-1 
186   // eap
187   // return(TTangentZones.NbTangentZones());
188   return 1;
189 }
190
191
192 Standard_Integer IntPolyh_Intersection::NbTangentZones() const { 
193   return(nbtangentzones);
194 }
195
196
197 void IntPolyh_Intersection::GetLinePoint(const Standard_Integer Indexl,
198                                  const Standard_Integer Indexp,
199                                  Standard_Real &x,
200                                  Standard_Real &y,
201                                  Standard_Real &z,
202                                  Standard_Real &u1,
203                                  Standard_Real &v1,
204                                  Standard_Real &u2,
205                                  Standard_Real &v2,
206                                  Standard_Real &incidence) const { 
207   const IntPolyh_SectionLine  &msl=TSectionLines[Indexl-1];
208   const IntPolyh_StartPoint   &sp=msl[Indexp-1];
209   x=sp.X();
210   y=sp.Y();
211   z=sp.Z();
212   u1=sp.U1();
213   v1=sp.V1();
214   u2=sp.U2();
215   v2=sp.V2();
216   incidence=sp.GetAngle();
217 }
218
219
220 void IntPolyh_Intersection::GetTangentZonePoint(const Standard_Integer Indexz,
221                                         const Standard_Integer /*Indexp*/,
222                                         Standard_Real &x,
223                                         Standard_Real &y,
224                                         Standard_Real &z,
225                                         Standard_Real &u1,
226                                         Standard_Real &v1,
227                                         Standard_Real &u2,
228                                         Standard_Real &v2) const { 
229   //--   Indexz--;    tableaux C
230   // eap
231   //const IntPolyh_StartPoint   &sp=TTangentZones[Indexp-1];
232   const IntPolyh_StartPoint   &sp=TTangentZones[Indexz-1];
233   x=sp.X();
234   y=sp.Y();
235   z=sp.Z();
236   u1=sp.U1();
237   v1=sp.V1();
238   u2=sp.U2();
239   v2=sp.V2();
240 }
241
242 //  Modified by skv - Thu Sep 25 18:07:41 2003 OCC567 Begin
243 //=======================================================================
244 //function : PerformMaillage
245 //purpose  : Computes MaillageAffinage
246 //=======================================================================
247 Standard_Boolean IntPolyh_Intersection::PerformMaillage
248                  (const Standard_Boolean            isFirstFwd,
249                   const Standard_Boolean            isSecondFwd,
250                         IntPolyh_PMaillageAffinage &theMaillageS)
251 {
252   if (myNbSU1 == -1)
253     theMaillageS = new IntPolyh_MaillageAffinage(mySurf1, mySurf2, MYPRINT);
254   else
255     theMaillageS = new IntPolyh_MaillageAffinage(mySurf1, myNbSU1, myNbSV1,
256                                                  mySurf2, myNbSU2, myNbSV2,
257                                                  MYPRINT);
258
259   theMaillageS->FillArrayOfPnt(1, isFirstFwd);
260   theMaillageS->FillArrayOfPnt(2, isSecondFwd);
261   
262   
263   Standard_Real xx0,yy0,zz0,xx1,yy1,zz1;
264   theMaillageS->CommonBox(theMaillageS->GetBox(1), theMaillageS->GetBox(2),
265                           xx0, yy0, zz0, xx1, yy1, zz1);
266   
267   theMaillageS->FillArrayOfEdges(1);
268   theMaillageS->FillArrayOfEdges(2);
269
270   theMaillageS->FillArrayOfTriangles(1);
271   theMaillageS->FillArrayOfTriangles(2);
272   
273   theMaillageS->LinkEdges2Triangles();
274   
275   theMaillageS->TrianglesDeflectionsRefinementBSB();
276
277   Standard_Integer FinTTC = theMaillageS->TriangleCompare();
278
279   // if too many intersections, consider surfaces parallel (eap)
280   if(FinTTC > 200 &&
281      (FinTTC >= theMaillageS->GetArrayOfTriangles(1).NbItems() ||
282       FinTTC >= theMaillageS->GetArrayOfTriangles(2).NbItems()) ) {
283     return Standard_False;
284   }
285
286   return Standard_True;
287 }
288
289 //=======================================================================
290 //function : PerformMaillage
291 //purpose  : Computes MaillageAffinage
292 //=======================================================================
293 Standard_Boolean IntPolyh_Intersection::PerformMaillage(IntPolyh_PMaillageAffinage &theMaillageS)
294 {
295   if (myNbSU1 == -1)
296     theMaillageS = new IntPolyh_MaillageAffinage(mySurf1, mySurf2, MYPRINT);
297   else
298     theMaillageS = new IntPolyh_MaillageAffinage(mySurf1, myNbSU1, myNbSV1,
299                                                  mySurf2, myNbSU2, myNbSV2,
300                                                  MYPRINT);
301
302   theMaillageS->FillArrayOfPnt(1);
303   theMaillageS->FillArrayOfPnt(2);
304   
305   
306   Standard_Real xx0,yy0,zz0,xx1,yy1,zz1;
307   theMaillageS->CommonBox(theMaillageS->GetBox(1), theMaillageS->GetBox(2),
308                           xx0, yy0, zz0, xx1, yy1, zz1);
309   
310   theMaillageS->FillArrayOfEdges(1);
311   theMaillageS->FillArrayOfEdges(2);
312
313   theMaillageS->FillArrayOfTriangles(1);
314   theMaillageS->FillArrayOfTriangles(2);
315   
316   theMaillageS->LinkEdges2Triangles();
317   
318   theMaillageS->TrianglesDeflectionsRefinementBSB();
319
320   Standard_Integer FinTTC = theMaillageS->TriangleCompare();
321
322   if( FinTTC == 0 ) {
323     Standard_Boolean myZone = Standard_True;
324     theMaillageS->SetEnlargeZone( myZone );
325     theMaillageS->FillArrayOfPnt(1);
326     theMaillageS->FillArrayOfPnt(2);
327     theMaillageS->CommonBox(theMaillageS->GetBox(1), theMaillageS->GetBox(2),
328                             xx0, yy0, zz0, xx1, yy1, zz1);
329     theMaillageS->FillArrayOfEdges(1);
330     theMaillageS->FillArrayOfEdges(2);
331     theMaillageS->FillArrayOfTriangles(1);
332     theMaillageS->FillArrayOfTriangles(2);
333     theMaillageS->LinkEdges2Triangles();
334     theMaillageS->TrianglesDeflectionsRefinementBSB();
335     FinTTC = theMaillageS->TriangleCompare();
336     myZone = Standard_False;
337     theMaillageS->SetEnlargeZone( myZone );
338   }
339
340   /*
341   // if too many intersections, consider surfaces parallel (eap)
342   if(FinTTC > 200 &&
343      (FinTTC >= theMaillageS->GetArrayOfTriangles(1).NbTriangles() ||
344       FinTTC >= theMaillageS->GetArrayOfTriangles(2).NbTriangles()) ) {
345     return Standard_False;
346   }
347   */
348   
349   return Standard_True;
350 }
351
352 //=======================================================================
353 //function : MergeCouples
354 //purpose  : This method analyzes arrays to find same couples. If some 
355 //           are detected it leaves the couple in only one array 
356 //           deleting from others.
357 //=======================================================================
358
359 void IntPolyh_Intersection::MergeCouples
360                             (IntPolyh_ArrayOfCouples &anArrayFF,
361                              IntPolyh_ArrayOfCouples &anArrayFR,
362                              IntPolyh_ArrayOfCouples &anArrayRF,
363                              IntPolyh_ArrayOfCouples &anArrayRR) const
364 {
365   // Step 1: Sorting arrays.
366   IntPolyh_ArrayOfCouples *anArrays[4];
367   Standard_Integer         aNbCouples[4];
368   Standard_Integer         i;
369   IntPolyh_ArrayOfCouples *aTmpPtr;
370   Standard_Integer         aTmpNbr;
371
372   anArrays[0] = &anArrayFF;
373   anArrays[1] = &anArrayFR;
374   anArrays[2] = &anArrayRF;
375   anArrays[3] = &anArrayRR;
376
377   for (i = 0; i < 4; i++)
378     aNbCouples[i] = anArrays[i]->NbItems();
379
380   Standard_Boolean isChanged = Standard_True;
381
382   while (isChanged) {
383     isChanged = Standard_False;
384
385     for (i = 0; i < 3; i++) {
386       if (aNbCouples[i] < aNbCouples[i + 1]) {
387         aTmpPtr           = anArrays[i];
388         anArrays[i]       = anArrays[i + 1];
389         anArrays[i + 1]   = aTmpPtr;
390         aTmpNbr           = aNbCouples[i];
391         aNbCouples[i]     = aNbCouples[i + 1];
392         aNbCouples[i + 1] = aTmpNbr;
393         isChanged         = Standard_True;
394       }
395     }
396   }
397
398   // Step 2: Searching for same couples.
399   Standard_Integer j;
400   Standard_Integer indC1;
401   Standard_Integer indC2;
402
403   for (i = 0; i < 3; i++) {
404     for (j = i + 1; j < 4; j++) {
405       for (indC1 = 1; indC1 <= aNbCouples[i]; indC1++) {
406         IntPolyh_Couple &aCouple1 = anArrays[i]->ChangeValue(indC1);
407
408         if (aCouple1.AnalyseFlagValue() == 1)
409           continue;
410
411         for (indC2 = 1; indC2 <= aNbCouples[j]; indC2++) {
412           IntPolyh_Couple &aCouple2 = anArrays[j]->ChangeValue(indC2);
413
414           if (aCouple2.AnalyseFlagValue() == 1)
415             continue;
416
417           if (aCouple1.FirstValue()  == aCouple2.FirstValue() &&
418               aCouple1.SecondValue() == aCouple2.SecondValue()) {
419             aCouple2.SetAnalyseFlag(1);
420           }
421         }
422       }
423     }
424   }
425 }
426 //  Modified by skv - Thu Sep 25 18:07:42 2003 OCC567 End
427
428 Standard_Boolean IntPolyh_Intersection::PerformStd(IntPolyh_PMaillageAffinage& MaillageS,
429                                                    Standard_Integer&           NbCouples)
430 {
431   Standard_Boolean isdone = PerformMaillage(MaillageS);
432   NbCouples = (isdone) ? (MaillageS->GetArrayOfCouples().NbItems()) : 0;
433   return isdone;
434 }
435
436 Standard_Boolean IntPolyh_Intersection::PerformAdv(IntPolyh_PMaillageAffinage& MaillageFF,
437                                                    IntPolyh_PMaillageAffinage& MaillageFR,
438                                                    IntPolyh_PMaillageAffinage& MaillageRF,
439                                                    IntPolyh_PMaillageAffinage& MaillageRR,
440                                                    Standard_Integer&           NbCouples)
441 {
442   Standard_Boolean isdone = Standard_True;
443   NbCouples = 0;
444
445   if(!PerformMaillage(Standard_True,Standard_False,MaillageFR) ||
446      !PerformMaillage(Standard_False,Standard_True,MaillageRF) ||
447      !PerformMaillage(Standard_True,Standard_True,MaillageFF)  ||
448      !PerformMaillage(Standard_False,Standard_False,MaillageRR) )
449     isdone = Standard_False; 
450
451   if(isdone) {
452     NbCouples = MaillageFF->GetArrayOfCouples().NbItems() +
453       MaillageFR->GetArrayOfCouples().NbItems() +
454         MaillageRF->GetArrayOfCouples().NbItems() +
455           MaillageRR->GetArrayOfCouples().NbItems();
456
457     if(NbCouples > 0)
458       MergeCouples(MaillageFF->GetArrayOfCouples(),MaillageFR->GetArrayOfCouples(),
459                    MaillageRF->GetArrayOfCouples(),MaillageRR->GetArrayOfCouples());
460   }
461   return isdone;
462 }