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