0028599: Replacement of old Boolean operations with new ones in BRepProj_Projection...
[occt.git] / src / IntPolyh / IntPolyh_Intersection.cxx
CommitLineData
b311480e 1// Created on: 1999-03-03
2// Created by: Fabrice SERVANT
3// Copyright (c) 1999-1999 Matra Datavision
973c2be1 4// Copyright (c) 1999-2014 OPEN CASCADE SAS
b311480e 5//
973c2be1 6// This file is part of Open CASCADE Technology software library.
b311480e 7//
d5f74e42 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
973c2be1 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.
b311480e 13//
973c2be1 14// Alternatively, this file may be used under the terms of Open CASCADE
15// commercial license or contractual agreement.
7fd59977 16
03cca6f7 17
18#include <IntPolyh_Intersection.hxx>
7fd59977 19
42cf5bc1 20#include <Adaptor3d_HSurface.hxx>
03cca6f7 21
42cf5bc1 22#include <IntPolyh_Couple.hxx>
03cca6f7 23#include <IntPolyh_CoupleMapHasher.hxx>
42cf5bc1 24#include <IntPolyh_MaillageAffinage.hxx>
7fd59977 25#include <IntPolyh_SectionLine.hxx>
26#include <IntPolyh_StartPoint.hxx>
03cca6f7 27#include <IntPolyh_Tools.hxx>
d642ddf5 28#include <IntPolyh_Triangle.hxx>
03cca6f7 29
68b07699 30#include <NCollection_Map.hxx>
7fd59977 31
03cca6f7 32static Standard_Boolean IsAdvRequired(IntPolyh_PMaillageAffinage& theMaillage);
7fd59977 33
03cca6f7 34static Standard_Integer ComputeIntersection(IntPolyh_PMaillageAffinage& theMaillage);
35
36static Standard_Boolean AnalyzeIntersection(IntPolyh_PMaillageAffinage& theMaillage);
37
38//=======================================================================
39//function : IntPolyh_Intersection
40//purpose :
41//=======================================================================
42IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_HSurface)& theS1,
43 const Handle(Adaptor3d_HSurface)& theS2)
7fd59977 44{
03cca6f7 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);
7fd59977 54 Perform();
55}
56
03cca6f7 57//=======================================================================
58//function : IntPolyh_Intersection
59//purpose :
60//=======================================================================
61IntPolyh_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)
7fd59977 67{
03cca6f7 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);
7fd59977 77 Perform();
78}
79
03cca6f7 80//=======================================================================
81//function : IntPolyh_Intersection
82//purpose :
83//=======================================================================
84IntPolyh_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);
7fd59977 101}
102
03cca6f7 103//=======================================================================
104//function : GetLinePoint
105//purpose :
106//=======================================================================
107void 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();
7fd59977 128}
129
03cca6f7 130//=======================================================================
131//function : GetTangentZonePoint
132//purpose :
133//=======================================================================
134void 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();
7fd59977 152}
153
03cca6f7 154//=======================================================================
155//function : Perform
156//purpose :
157//=======================================================================
158void 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);
7fd59977 164
03cca6f7 165 // Perform intersection
166 Perform(UPars1, VPars1, UPars2, VPars2);
7fd59977 167}
168
03cca6f7 169//=======================================================================
170//function : Perform
171//purpose :
172//=======================================================================
173void 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 }
7fd59977 199
03cca6f7 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 }
7fd59977 238
03cca6f7 239 // Clean up
240 if (pMaillageFF) delete pMaillageFF;
241 if (pMaillageFR) delete pMaillageFR;
242 if (pMaillageRF) delete pMaillageRF;
243 if (pMaillageRR) delete pMaillageRR;
244 }
7fd59977 245
03cca6f7 246 // clean up
247 if (pMaillageStd) delete pMaillageStd;
7fd59977 248}
249
03cca6f7 250//=======================================================================
251//function : PerformStd
252//purpose :
253//=======================================================================
254Standard_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;
7fd59977 269}
270
03cca6f7 271//=======================================================================
272//function : PerformAdv
273//purpose :
274//=======================================================================
275Standard_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 }
7fd59977 332
03cca6f7 333 return isDone;
7fd59977 334}
335
7fd59977 336//=======================================================================
337//function : PerformMaillage
03cca6f7 338//purpose : Computes standard MaillageAffinage (without shift)
7fd59977 339//=======================================================================
03cca6f7 340Standard_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)
7fd59977 347{
03cca6f7 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 }
7fd59977 376 }
377
03cca6f7 378 // if too many intersections, consider surfaces parallel
379 return AnalyzeIntersection(theMaillage);
7fd59977 380}
381
382//=======================================================================
383//function : PerformMaillage
384//purpose : Computes MaillageAffinage
385//=======================================================================
03cca6f7 386Standard_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)
7fd59977 397{
03cca6f7 398 theMaillage =
399 new IntPolyh_MaillageAffinage(mySurf1, theUPars1.Length(), theVPars1.Length(),
400 mySurf2, theUPars2.Length(), theVPars2.Length(),
401 0);
7fd59977 402
03cca6f7 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);
7fd59977 409}
410
411//=======================================================================
412//function : MergeCouples
68b07699 413//purpose : This method analyzes the lists to find same couples.
414// If some are detected it leaves the couple in only one list
7fd59977 415// deleting from others.
416//=======================================================================
68b07699 417void IntPolyh_Intersection::MergeCouples(IntPolyh_ListOfCouples &anArrayFF,
418 IntPolyh_ListOfCouples &anArrayFR,
419 IntPolyh_ListOfCouples &anArrayRF,
420 IntPolyh_ListOfCouples &anArrayRR) const
7fd59977 421{
68b07699 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;
7fd59977 432 }
68b07699 433 aIt.Next();
7fd59977 434 }
435 }
436}
7fd59977 437
68b07699 438//=======================================================================
03cca6f7 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.
68b07699 444//=======================================================================
03cca6f7 445Standard_Boolean IsAdvRequired(IntPolyh_PMaillageAffinage& theMaillage)
7fd59977 446{
03cca6f7 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;
7fd59977 478}
479
68b07699 480//=======================================================================
03cca6f7 481//function : ComputeIntersection
482//purpose : Computes the intersection of the triangles
483//=======================================================================
484Standard_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
68b07699 509//=======================================================================
03cca6f7 510Standard_Boolean AnalyzeIntersection(IntPolyh_PMaillageAffinage& theMaillage)
7fd59977 511{
03cca6f7 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 }
7fd59977 533 }
03cca6f7 534 return Standard_True;
7fd59977 535}