0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm
[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 <Adaptor3d_HSurface.hxx>
21 #include <IntPolyh_Couple.hxx>
22 #include <IntPolyh_Intersection.hxx>
23 #include <IntPolyh_MaillageAffinage.hxx>
24 #include <IntPolyh_SectionLine.hxx>
25 #include <IntPolyh_StartPoint.hxx>
26 #include <IntPolyh_Triangle.hxx>
27 #include <NCollection_Map.hxx>
28 #include <IntPolyh_CoupleMapHasher.hxx>
29
30 Standard_Integer MYDISPLAY = 0;
31 Standard_Integer MYPRINT   = 0;
32
33 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_HSurface)& S1,
34                                              const Handle(Adaptor3d_HSurface)& S2)
35 {
36   myNbSU1 = -1;
37   myNbSV1 = -1;
38   myNbSU2 = -1; 
39   myNbSV2 = -1; 
40   mySurf1 = S1;
41   mySurf2 = S2;
42   done = Standard_False;
43   TSectionLines.Init(1000);
44   TTangentZones.Init(10000);
45   Perform();
46 }
47
48 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_HSurface)& S1,
49                                              const Standard_Integer NbSU1,
50                                              const Standard_Integer NbSV1,
51                                              const Handle(Adaptor3d_HSurface)& S2,
52                                              const Standard_Integer NbSU2,
53                                              const Standard_Integer NbSV2)
54 {
55   myNbSU1 = NbSU1;
56   myNbSV1 = NbSV1;
57   myNbSU2 = NbSU2; 
58   myNbSV2 = NbSV2; 
59   mySurf1 = S1;
60   mySurf2 = S2;
61   done = Standard_False;
62   TSectionLines.Init(1000);
63   TTangentZones.Init(10000);
64   Perform();
65 }
66
67 void IntPolyh_Intersection::Perform() { 
68
69   done = Standard_True;
70
71   Standard_Boolean isStdDone = Standard_False;
72   Standard_Boolean isAdvDone = Standard_False;
73   Standard_Integer nbCouplesStd = 0;
74   Standard_Integer nbCouplesAdv = 0;
75   
76   IntPolyh_PMaillageAffinage aPMaillageStd = 0;
77   IntPolyh_PMaillageAffinage aPMaillageFF = 0;
78   IntPolyh_PMaillageAffinage aPMaillageFR = 0;
79   IntPolyh_PMaillageAffinage aPMaillageRF = 0;
80   IntPolyh_PMaillageAffinage aPMaillageRR = 0;
81
82   isStdDone = PerformStd(aPMaillageStd,nbCouplesStd);
83
84   // default interference done well, use it
85   if(isStdDone && nbCouplesStd > 10) {
86     aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
87   }
88   // default interference done, but too few interferences foud;
89   // use advanced interference
90   else if(isStdDone && nbCouplesStd <= 10) {
91     isAdvDone = PerformAdv(aPMaillageFF,aPMaillageFR,aPMaillageRF,aPMaillageRR,nbCouplesAdv);
92
93     // advanced interference found
94     if(isAdvDone && nbCouplesAdv > 0) {
95       aPMaillageFF->StartPointsChain(TSectionLines,TTangentZones);
96       aPMaillageFR->StartPointsChain(TSectionLines,TTangentZones);
97       aPMaillageRF->StartPointsChain(TSectionLines,TTangentZones);
98       aPMaillageRR->StartPointsChain(TSectionLines,TTangentZones);
99     }
100     else {
101       // use result of default
102       if(nbCouplesStd > 0)
103         aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
104     }
105   }
106   // default interference faild, use advanced
107   else {
108     //       isAdvDone = PerformAdv(aPMaillageFF,aPMaillageFR,aPMaillageRF,aPMaillageRR,nbCouplesAdv);
109
110     //       if(isAdvDone && nbCouplesAdv > 0) {cout << "4adv done, nbc: " << nbCouplesAdv << endl;
111     //  aPMaillageFF->StartPointsChain(TSectionLines,TTangentZones);
112     //  aPMaillageFR->StartPointsChain(TSectionLines,TTangentZones);
113     //  aPMaillageRF->StartPointsChain(TSectionLines,TTangentZones);
114     //  aPMaillageRR->StartPointsChain(TSectionLines,TTangentZones);
115     //       }
116   }
117
118   // accept result
119   nbsectionlines = TSectionLines.NbItems();
120   nbtangentzones = TTangentZones.NbItems();
121
122   // clean up
123   if(aPMaillageStd) delete aPMaillageStd;
124   if(aPMaillageFF) delete aPMaillageFF;
125   if(aPMaillageFR) delete aPMaillageFR;
126   if(aPMaillageRF) delete aPMaillageRF;
127   if(aPMaillageRR) delete aPMaillageRR;
128
129   // verify
130   if(!isStdDone && !isAdvDone)
131     done = Standard_False;
132 }
133
134
135 Standard_Boolean IntPolyh_Intersection::IsDone() const {
136   return(done);
137 }
138
139
140 Standard_Integer IntPolyh_Intersection::NbSectionLines() const { 
141   return(nbsectionlines);
142 }
143
144
145 Standard_Integer IntPolyh_Intersection::NbPointsInLine(const Standard_Integer IndexLine) const { 
146   
147   return(TSectionLines[IndexLine-1].NbStartPoints());
148 }
149
150
151 Standard_Integer IntPolyh_Intersection::NbPointsInTangentZone(const Standard_Integer) const {   
152   //-- IndexLine--;     (pas implemente) Attention : Tableaux de 0 a n-1 
153   // eap
154   // return(TTangentZones.NbTangentZones());
155   return 1;
156 }
157
158
159 Standard_Integer IntPolyh_Intersection::NbTangentZones() const { 
160   return(nbtangentzones);
161 }
162
163
164 void IntPolyh_Intersection::GetLinePoint(const Standard_Integer Indexl,
165                                  const Standard_Integer Indexp,
166                                  Standard_Real &x,
167                                  Standard_Real &y,
168                                  Standard_Real &z,
169                                  Standard_Real &u1,
170                                  Standard_Real &v1,
171                                  Standard_Real &u2,
172                                  Standard_Real &v2,
173                                  Standard_Real &incidence) const { 
174   const IntPolyh_SectionLine  &msl=TSectionLines[Indexl-1];
175   const IntPolyh_StartPoint   &sp=msl[Indexp-1];
176   x=sp.X();
177   y=sp.Y();
178   z=sp.Z();
179   u1=sp.U1();
180   v1=sp.V1();
181   u2=sp.U2();
182   v2=sp.V2();
183   incidence=sp.GetAngle();
184 }
185
186
187 void IntPolyh_Intersection::GetTangentZonePoint(const Standard_Integer Indexz,
188                                         const Standard_Integer /*Indexp*/,
189                                         Standard_Real &x,
190                                         Standard_Real &y,
191                                         Standard_Real &z,
192                                         Standard_Real &u1,
193                                         Standard_Real &v1,
194                                         Standard_Real &u2,
195                                         Standard_Real &v2) const { 
196   //--   Indexz--;    tableaux C
197   // eap
198   //const IntPolyh_StartPoint   &sp=TTangentZones[Indexp-1];
199   const IntPolyh_StartPoint   &sp=TTangentZones[Indexz-1];
200   x=sp.X();
201   y=sp.Y();
202   z=sp.Z();
203   u1=sp.U1();
204   v1=sp.V1();
205   u2=sp.U2();
206   v2=sp.V2();
207 }
208
209 //  Modified by skv - Thu Sep 25 18:07:41 2003 OCC567 Begin
210 //=======================================================================
211 //function : PerformMaillage
212 //purpose  : Computes MaillageAffinage
213 //=======================================================================
214 Standard_Boolean IntPolyh_Intersection::PerformMaillage
215                  (const Standard_Boolean            isFirstFwd,
216                   const Standard_Boolean            isSecondFwd,
217                         IntPolyh_PMaillageAffinage &theMaillageS)
218 {
219   if (myNbSU1 == -1)
220     theMaillageS = new IntPolyh_MaillageAffinage(mySurf1, mySurf2, MYPRINT);
221   else
222     theMaillageS = new IntPolyh_MaillageAffinage(mySurf1, myNbSU1, myNbSV1,
223                                                  mySurf2, myNbSU2, myNbSV2,
224                                                  MYPRINT);
225
226   theMaillageS->FillArrayOfPnt(1, isFirstFwd);
227   theMaillageS->FillArrayOfPnt(2, isSecondFwd);
228   
229   
230   Standard_Real xx0,yy0,zz0,xx1,yy1,zz1;
231   theMaillageS->CommonBox(theMaillageS->GetBox(1), theMaillageS->GetBox(2),
232                           xx0, yy0, zz0, xx1, yy1, zz1);
233   
234   theMaillageS->FillArrayOfTriangles(1);
235   theMaillageS->FillArrayOfTriangles(2);
236   
237   theMaillageS->FillArrayOfEdges(1);
238   theMaillageS->FillArrayOfEdges(2);
239
240   theMaillageS->TrianglesDeflectionsRefinementBSB();
241
242   Standard_Integer FinTTC = theMaillageS->TriangleCompare();
243
244   // if too many intersections, consider surfaces parallel (eap)
245   if(FinTTC > 200 &&
246      (FinTTC >= theMaillageS->GetArrayOfTriangles(1).NbItems() ||
247       FinTTC >= theMaillageS->GetArrayOfTriangles(2).NbItems()) ) {
248     return Standard_False;
249   }
250
251   return Standard_True;
252 }
253
254 //=======================================================================
255 //function : PerformMaillage
256 //purpose  : Computes MaillageAffinage
257 //=======================================================================
258 Standard_Boolean IntPolyh_Intersection::PerformMaillage(IntPolyh_PMaillageAffinage &theMaillageS)
259 {
260   if (myNbSU1 == -1)
261     theMaillageS = new IntPolyh_MaillageAffinage(mySurf1, mySurf2, MYPRINT);
262   else
263     theMaillageS = new IntPolyh_MaillageAffinage(mySurf1, myNbSU1, myNbSV1,
264                                                  mySurf2, myNbSU2, myNbSV2,
265                                                  MYPRINT);
266
267   theMaillageS->FillArrayOfPnt(1);
268   theMaillageS->FillArrayOfPnt(2);
269   
270   
271   Standard_Real xx0,yy0,zz0,xx1,yy1,zz1;
272   theMaillageS->CommonBox(theMaillageS->GetBox(1), theMaillageS->GetBox(2),
273                           xx0, yy0, zz0, xx1, yy1, zz1);
274   
275   theMaillageS->FillArrayOfTriangles(1);
276   theMaillageS->FillArrayOfTriangles(2);
277   
278   theMaillageS->FillArrayOfEdges(1);
279   theMaillageS->FillArrayOfEdges(2);
280
281   theMaillageS->TrianglesDeflectionsRefinementBSB();
282
283   Standard_Integer FinTTC = theMaillageS->TriangleCompare();
284
285   if( FinTTC == 0 ) {
286     Standard_Boolean myZone = Standard_True;
287     theMaillageS->SetEnlargeZone( myZone );
288     theMaillageS->FillArrayOfPnt(1);
289     theMaillageS->FillArrayOfPnt(2);
290     theMaillageS->CommonBox(theMaillageS->GetBox(1), theMaillageS->GetBox(2),
291                             xx0, yy0, zz0, xx1, yy1, zz1);
292     theMaillageS->FillArrayOfTriangles(1);
293     theMaillageS->FillArrayOfTriangles(2);
294     theMaillageS->FillArrayOfEdges(1);
295     theMaillageS->FillArrayOfEdges(2);
296     theMaillageS->TrianglesDeflectionsRefinementBSB();
297     FinTTC = theMaillageS->TriangleCompare();
298     myZone = Standard_False;
299     theMaillageS->SetEnlargeZone( myZone );
300   }
301
302   return Standard_True;
303 }
304
305 //=======================================================================
306 //function : MergeCouples
307 //purpose  : This method analyzes the lists to find same couples.
308 //           If some are detected it leaves the couple in only one list
309 //           deleting from others.
310 //=======================================================================
311
312 void IntPolyh_Intersection::MergeCouples(IntPolyh_ListOfCouples &anArrayFF,
313                                          IntPolyh_ListOfCouples &anArrayFR,
314                                          IntPolyh_ListOfCouples &anArrayRF,
315                                          IntPolyh_ListOfCouples &anArrayRR) const
316 {
317   // Fence map to remove from the lists the duplicating elements.
318   NCollection_Map<IntPolyh_Couple, IntPolyh_CoupleMapHasher> aFenceMap;
319   //
320   IntPolyh_ListOfCouples* pLists[4] = {&anArrayFF, &anArrayFR, &anArrayRF, &anArrayRR};
321   for (Standard_Integer i = 0; i < 4; ++i) {
322     IntPolyh_ListIteratorOfListOfCouples aIt(*pLists[i]);
323     for (; aIt.More();) {
324       if (!aFenceMap.Add(aIt.Value())) {
325         pLists[i]->Remove(aIt);
326         continue;
327       }
328       aIt.Next();
329     }
330   }
331 }
332
333 //=======================================================================
334 //function : PerformStd
335 //purpose  : 
336 //=======================================================================
337 Standard_Boolean IntPolyh_Intersection::PerformStd(IntPolyh_PMaillageAffinage& MaillageS,
338                                                    Standard_Integer&           NbCouples)
339 {
340   Standard_Boolean isdone = PerformMaillage(MaillageS);
341   NbCouples = (isdone) ? (MaillageS->GetCouples().Extent()) : 0;
342   return isdone;
343 }
344
345 //=======================================================================
346 //function : PerformAdv
347 //purpose  : 
348 //=======================================================================
349 Standard_Boolean IntPolyh_Intersection::PerformAdv(IntPolyh_PMaillageAffinage& MaillageFF,
350                                                    IntPolyh_PMaillageAffinage& MaillageFR,
351                                                    IntPolyh_PMaillageAffinage& MaillageRF,
352                                                    IntPolyh_PMaillageAffinage& MaillageRR,
353                                                    Standard_Integer&           NbCouples)
354 {
355   Standard_Boolean isdone = Standard_True;
356   NbCouples = 0;
357
358   if(!PerformMaillage(Standard_True,Standard_False,MaillageFR) ||
359      !PerformMaillage(Standard_False,Standard_True,MaillageRF) ||
360      !PerformMaillage(Standard_True,Standard_True,MaillageFF)  ||
361      !PerformMaillage(Standard_False,Standard_False,MaillageRR) )
362     isdone = Standard_False; 
363
364   if(isdone) {
365     NbCouples = MaillageFF->GetCouples().Extent() +
366       MaillageFR->GetCouples().Extent() +
367         MaillageRF->GetCouples().Extent() +
368           MaillageRR->GetCouples().Extent();
369
370     if(NbCouples > 0)
371       MergeCouples(MaillageFF->GetCouples(),MaillageFR->GetCouples(),
372                    MaillageRF->GetCouples(),MaillageRR->GetCouples());
373   }
374   return isdone;
375 }