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