1 // Created by: Peter KURNEV
2 // Copyright (c) 2010-2014 OPEN CASCADE SAS
3 // Copyright (c) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE
4 // Copyright (c) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, CEDRAT,
5 // EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
7 // This file is part of Open CASCADE Technology software library.
9 // This library is free software; you can redistribute it and/or modify it under
10 // the terms of the GNU Lesser General Public License version 2.1 as published
11 // by the Free Software Foundation, with special exception defined in the file
12 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
13 // distribution for complete text of the license and disclaimer of any warranty.
15 // Alternatively, this file may be used under the terms of Open CASCADE
16 // commercial license or contractual agreement.
19 #include <Bnd_Box.hxx>
20 #include <BOPAlgo_PaveFiller.hxx>
21 #include <BOPAlgo_Tools.hxx>
22 #include <BOPAlgo_Alerts.hxx>
23 #include <BOPDS_CommonBlock.hxx>
24 #include <BOPDS_CoupleOfPaveBlocks.hxx>
25 #include <BOPDS_DS.hxx>
26 #include <BOPDS_Interf.hxx>
27 #include <BOPDS_Iterator.hxx>
28 #include <BOPDS_MapOfPaveBlock.hxx>
29 #include <BOPDS_Pave.hxx>
30 #include <BOPDS_PaveBlock.hxx>
31 #include <BOPDS_VectorOfInterfEE.hxx>
32 #include <BOPTools_AlgoTools.hxx>
33 #include <BOPTools_AlgoTools2D.hxx>
34 #include <BOPTools_Parallel.hxx>
35 #include <BndLib_Add3dCurve.hxx>
36 #include <BRep_Tool.hxx>
37 #include <BRep_Builder.hxx>
38 #include <BRepAdaptor_Curve.hxx>
39 #include <GeomAPI_ProjectPointOnCurve.hxx>
41 #include <IntTools_CommonPrt.hxx>
42 #include <IntTools_Context.hxx>
43 #include <IntTools_EdgeEdge.hxx>
44 #include <IntTools_Range.hxx>
45 #include <IntTools_SequenceOfCommonPrts.hxx>
46 #include <IntTools_SequenceOfRanges.hxx>
47 #include <IntTools_ShrunkRange.hxx>
48 #include <IntTools_Tools.hxx>
49 #include <NCollection_IncAllocator.hxx>
50 #include <NCollection_Vector.hxx>
51 #include <Precision.hxx>
53 #include <TopoDS_Edge.hxx>
54 #include <TopoDS_Vertex.hxx>
56 /////////////////////////////////////////////////////////////////////////
57 //=======================================================================
58 //class : BOPAlgo_EdgeEdge
60 //=======================================================================
61 class BOPAlgo_EdgeEdge :
62 public IntTools_EdgeEdge,
74 virtual ~BOPAlgo_EdgeEdge(){
77 void SetPaveBlock1(const Handle(BOPDS_PaveBlock)& aPB) {
81 Handle(BOPDS_PaveBlock)& PaveBlock1() {
85 void SetPaveBlock2(const Handle(BOPDS_PaveBlock)& aPB) {
89 Handle(BOPDS_PaveBlock)& PaveBlock2() {
93 void SetBoxes (const Bnd_Box& theBox1,
94 const Bnd_Box& theBox2)
100 void SetFuzzyValue(const Standard_Real theFuzz) {
101 IntTools_EdgeEdge::SetFuzzyValue(theFuzz);
104 virtual void Perform() {
105 BOPAlgo_Algo::UserBreak();
106 TopoDS_Edge anE1 = myEdge1, anE2 = myEdge2;
107 Standard_Boolean hasTrsf = false;
113 if (BOPAlgo_Tools::TrsfToPoint (myBox1, myBox2, aTrsf))
115 // Shapes are located far from origin, move the shapes to the origin,
116 // to increase the accuracy of intersection.
117 TopLoc_Location aLoc (aTrsf);
120 hasTrsf = Standard_True;
123 IntTools_EdgeEdge::Perform();
125 catch (Standard_Failure const&)
127 AddError(new BOPAlgo_AlertIntersectionFailed);
134 for (Standard_Integer i = 1; i <= myCommonParts.Length(); ++i)
136 IntTools_CommonPrt& aCPart = myCommonParts (i);
137 aCPart.SetEdge1 (myEdge1);
138 aCPart.SetEdge2 (myEdge2);
145 Handle(BOPDS_PaveBlock) myPB1;
146 Handle(BOPDS_PaveBlock) myPB2;
151 //=======================================================================
152 typedef NCollection_Vector<BOPAlgo_EdgeEdge> BOPAlgo_VectorOfEdgeEdge;
154 //=======================================================================
155 // function: PerformEE
157 //=======================================================================
158 void BOPAlgo_PaveFiller::PerformEE()
160 FillShrunkData(TopAbs_EDGE, TopAbs_EDGE);
162 myIterator->Initialize(TopAbs_EDGE, TopAbs_EDGE);
163 Standard_Integer iSize = myIterator->ExpectedLength();
168 Standard_Boolean bExpressCompute, bIsPBSplittable1, bIsPBSplittable2;
169 Standard_Integer i, iX, nE1, nE2, aNbCPrts, k, aNbEdgeEdge;
170 Standard_Integer nV11, nV12, nV21, nV22;
171 Standard_Real aTS11, aTS12, aTS21, aTS22, aT11, aT12, aT21, aT22;
172 TopAbs_ShapeEnum aType;
173 BOPDS_ListIteratorOfListOfPaveBlock aIt1, aIt2;
174 Handle(NCollection_BaseAllocator) aAllocator;
175 BOPAlgo_VectorOfEdgeEdge aVEdgeEdge;
176 BOPDS_MapIteratorOfMapOfPaveBlock aItPB;
177 // keep modified edges for further update
178 TColStd_MapOfInteger aMEdges;
180 aAllocator=NCollection_BaseAllocator::CommonBaseAllocator();
181 //-----------------------------------------------------scope f
182 BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock aMPBLPB(100, aAllocator);
183 BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMVCPB(100, aAllocator);
184 BOPAlgo_DataMapOfPaveBlockBndBox aDMPBBox(100, aAllocator);
186 BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
187 aEEs.SetIncrement(iSize);
189 for (; myIterator->More(); myIterator->Next()) {
190 myIterator->Value(nE1, nE2);
192 const BOPDS_ShapeInfo& aSIE1=myDS->ShapeInfo(nE1);
193 if (aSIE1.HasFlag()){
196 const BOPDS_ShapeInfo& aSIE2=myDS->ShapeInfo(nE2);
197 if (aSIE2.HasFlag()){
201 BOPDS_ListOfPaveBlock& aLPB1 = myDS->ChangePaveBlocks(nE1);
202 if (aLPB1.IsEmpty()) {
206 BOPDS_ListOfPaveBlock& aLPB2 = myDS->ChangePaveBlocks(nE2);
207 if (aLPB2.IsEmpty()) {
211 const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aSIE1.Shape()));
212 const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aSIE2.Shape()));
214 aIt1.Initialize(aLPB1);
215 for (; aIt1.More(); aIt1.Next()) {
218 Handle(BOPDS_PaveBlock)& aPB1=aIt1.ChangeValue();
220 if (!GetPBBox(aE1, aPB1, aDMPBBox, aT11, aT12, aTS11, aTS12, aBB1)) {
224 aPB1->Indices(nV11, nV12);
226 aIt2.Initialize(aLPB2);
227 for (; aIt2.More(); aIt2.Next()) {
230 Handle(BOPDS_PaveBlock)& aPB2=aIt2.ChangeValue();
232 if (!GetPBBox(aE2, aPB2, aDMPBBox, aT21, aT22, aTS21, aTS22, aBB2)) {
236 if (aBB1.IsOut(aBB2)) {
240 aPB2->Indices(nV21, nV22);
242 bExpressCompute=((nV11==nV21 && nV12==nV22) ||
243 (nV12==nV21 && nV11==nV22));
245 BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge.Appended();
247 anEdgeEdge.UseQuickCoincidenceCheck(bExpressCompute);
249 anEdgeEdge.SetPaveBlock1(aPB1);
250 anEdgeEdge.SetPaveBlock2(aPB2);
252 anEdgeEdge.SetEdge1(aE1, aT11, aT12);
253 anEdgeEdge.SetEdge2(aE2, aT21, aT22);
254 anEdgeEdge.SetBoxes (aBB1, aBB2);
255 anEdgeEdge.SetFuzzyValue(myFuzzyValue);
256 if (myProgressScope != NULL)
258 anEdgeEdge.SetProgressIndicator(*myProgressScope);
260 }//for (; aIt2.More(); aIt2.Next()) {
261 }//for (; aIt1.More(); aIt1.Next()) {
262 }//for (; myIterator->More(); myIterator->Next()) {
264 aNbEdgeEdge=aVEdgeEdge.Length();
265 //======================================================
266 BOPTools_Parallel::Perform (myRunParallel, aVEdgeEdge);
267 //======================================================
269 for (k = 0; k < aNbEdgeEdge; ++k) {
272 BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge(k);
273 if (!anEdgeEdge.IsDone() || anEdgeEdge.HasErrors()) {
274 // Warn about failed intersection of sub-shapes
275 const TopoDS_Shape& aE1 = myDS->Shape(anEdgeEdge.PaveBlock1()->OriginalEdge());
276 const TopoDS_Shape& aE2 = myDS->Shape(anEdgeEdge.PaveBlock2()->OriginalEdge());
277 AddIntersectionFailedWarning(aE1, aE2);
281 const IntTools_SequenceOfCommonPrts& aCPrts = anEdgeEdge.CommonParts();
282 aNbCPrts = aCPrts.Length();
286 //--------------------------------------------
287 Handle(BOPDS_PaveBlock)& aPB1=anEdgeEdge.PaveBlock1();
288 nE1=aPB1->OriginalEdge();
289 aPB1->Range(aT11, aT12);
290 if (!aPB1->HasShrunkData()) {
293 bIsPBSplittable1 = Standard_False;
296 aPB1->ShrunkData(aTS11, aTS12, aBB1, bIsPBSplittable1);
299 Handle(BOPDS_PaveBlock)& aPB2=anEdgeEdge.PaveBlock2();
300 nE2=aPB2->OriginalEdge();
301 aPB2->Range(aT21, aT22);
302 if (!aPB2->HasShrunkData()) {
305 bIsPBSplittable2 = Standard_False;
308 aPB2->ShrunkData(aTS21, aTS22, aBB2, bIsPBSplittable2);
311 //--------------------------------------------
312 IntTools_Range aR11(aT11, aTS11), aR12(aTS12, aT12),
313 aR21(aT21, aTS21), aR22(aTS22, aT22);
315 Standard_Boolean bAnalytical = Standard_False;
317 const TopoDS_Edge& aOE1 = *(TopoDS_Edge*)&myDS->Shape(nE1);
318 const TopoDS_Edge& aOE2 = *(TopoDS_Edge*)&myDS->Shape(nE2);
320 BRepAdaptor_Curve aBAC1(aOE1), aBAC2(aOE2);
322 GeomAbs_CurveType aType1 = aBAC1.GetType();
323 GeomAbs_CurveType aType2 = aBAC2.GetType();
325 bAnalytical = (((aType1 == GeomAbs_Line) &&
326 (aType2 == GeomAbs_Line ||
327 aType2 == GeomAbs_Circle)) ||
328 ((aType2 == GeomAbs_Line) &&
329 (aType1 == GeomAbs_Line ||
330 aType1 == GeomAbs_Circle)));
333 for (i=1; i<=aNbCPrts; ++i) {
334 const IntTools_CommonPrt& aCPart=aCPrts(i);
336 const TopoDS_Edge& aE1=aCPart.Edge1();
337 const TopoDS_Edge& aE2=aCPart.Edge2();
341 case TopAbs_VERTEX: {
342 if (!bIsPBSplittable1 || !bIsPBSplittable2) {
346 Standard_Boolean bIsOnPave[4];
347 Standard_Integer nV[4], j;
348 Standard_Real aT1, aT2, aTol;
350 IntTools_Range aCR1, aCR2;
352 IntTools_Tools::VertexParameters(aCPart, aT1, aT2);
353 aTol = Precision::Confusion();
354 aCR1 = aCPart.Range1();
355 aCR2 = aCPart.Ranges2()(1);
357 //decide to keep the pave or not
358 bIsOnPave[0] = IntTools_Tools::IsOnPave1(aT1, aR11, aTol) ||
359 IntTools_Tools::IsOnPave1(aR11.First(), aCR1, aTol);
360 bIsOnPave[1] = IntTools_Tools::IsOnPave1(aT1, aR12, aTol) ||
361 IntTools_Tools::IsOnPave1(aR12.Last(), aCR1, aTol);
362 bIsOnPave[2] = IntTools_Tools::IsOnPave1(aT2, aR21, aTol) ||
363 IntTools_Tools::IsOnPave1(aR21.First(), aCR2, aTol);
364 bIsOnPave[3] = IntTools_Tools::IsOnPave1(aT2, aR22, aTol) ||
365 IntTools_Tools::IsOnPave1(aR22.Last(), aCR2, aTol);
367 aPB1->Indices(nV[0], nV[1]);
368 aPB2->Indices(nV[2], nV[3]);
370 if((bIsOnPave[0] && bIsOnPave[2]) ||
371 (bIsOnPave[0] && bIsOnPave[3]) ||
372 (bIsOnPave[1] && bIsOnPave[2]) ||
373 (bIsOnPave[1] && bIsOnPave[3])) {
377 Standard_Boolean isVExists = Standard_False;
378 for (j = 0; j < 4; ++j)
382 Handle(BOPDS_PaveBlock)& aPB = (j < 2) ? aPB2 : aPB1;
383 bIsOnPave[j] = ForceInterfVE(nV[j], aPB, aMEdges);
384 if (bIsOnPave[j]) isVExists = Standard_True;
388 BOPTools_AlgoTools::MakeNewVertex(aE1, aT1, aE2, aT2, aVnew);
389 const gp_Pnt aPnew = BRep_Tool::Pnt(aVnew);
393 // The found intersection point is located closely to one of the
394 // pave blocks bounds. So, do not create the new vertex in this point.
395 // Check if this point is a real intersection point or just a touching point.
396 // If it is a touching point, do nothing.
397 // If it is an intersection point, update the existing vertex to cover the
398 // intersection point.
399 const gp_Pnt aPOnE1 = BRepAdaptor_Curve(aE1).Value(aT1);
400 const gp_Pnt aPOnE2 = BRepAdaptor_Curve(aE2).Value(aT2);
401 if (aPOnE1.Distance(aPOnE2) > Precision::Intersection())
402 // No intersection point
405 // Real intersection is present.
406 // Update the existing vertex to cover the intersection point.
407 for (j = 0; j < 4; ++j)
411 const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV[j]));
412 const gp_Pnt aP = BRep_Tool::Pnt(aV);
413 Standard_Real aDistPP = aP.Distance(aPnew);
414 // Just update the vertex
415 UpdateVertex(nV[j], aDistPP);
416 myVertsToAvoidExtension.Add(nV[j]);
421 Standard_Real aTolVnew = BRep_Tool::Tolerance(aVnew);
423 // increase tolerance for Line/Line intersection, but do not update
424 // the vertex till its intersection with some other shape
425 Standard_Real aTolMin = (BRepAdaptor_Curve(aE1).GetType() == GeomAbs_Line) ?
426 (aCR1.Last() - aCR1.First()) / 2. : (aCR2.Last() - aCR2.First()) / 2.;
427 if (aTolMin > aTolVnew) {
433 Standard_Integer nVS[2], iFound;
434 Standard_Real aTolVx, aD2, aDT2;
435 TColStd_MapOfInteger aMV;
443 if (aMV.Contains(nV[2])) {
447 if (aMV.Contains(nV[3])) {
452 for (Standard_Integer k1=0; k1<=j; ++k1) {
453 const TopoDS_Vertex& aVx= *(TopoDS_Vertex*)&(myDS->Shape(nVS[k1]));
454 aTolVx=BRep_Tool::Tolerance(aVx);
455 aPx=BRep_Tool::Pnt(aVx);
456 aD2=aPnew.SquareDistance(aPx);
458 aDT2=100.*(aTolVnew+aTolVx)*(aTolVnew+aTolVx);
472 BOPDS_InterfEE& aEE=aEEs.Appended();
474 aEE.SetIndices(nE1, nE2);
475 aEE.SetCommonPart(aCPart);
477 myDS->AddInterf(nE1, nE2);
479 BOPDS_CoupleOfPaveBlocks aCPB;
481 aCPB.SetPaveBlocks(aPB1, aPB2);
482 aCPB.SetIndexInterf(iX);
483 aCPB.SetTolerance(aTolVnew);
484 aMVCPB.Add(aVnew, aCPB);
485 }//case TopAbs_VERTEX:
493 Standard_Boolean bHasSameBounds;
494 bHasSameBounds=aPB1->HasSameBounds(aPB2);
495 if (!bHasSameBounds) {
499 BOPDS_InterfEE& aEE=aEEs.Appended();
501 aEE.SetIndices(nE1, nE2);
502 aEE.SetCommonPart(aCPart);
504 myDS->AddInterf(nE1, nE2);
506 BOPAlgo_Tools::FillMap<Handle(BOPDS_PaveBlock), TColStd_MapTransientHasher>(aPB1, aPB2, aMPBLPB, aAllocator);
512 }//for (i=1; i<=aNbCPrts; i++) {
513 }//for (k=0; k < aNbFdgeEdge; ++k) {
515 //=========================================
517 //=========================================
518 BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, aAllocator, myDS, myContext);
519 // Update vertices of common blocks with real CB tolerances
520 UpdateVerticesOfCB();
522 PerformNewVertices(aMVCPB, aAllocator);
524 if (aMEdges.Extent()) {
525 Standard_Integer aNbV = aMVCPB.Extent();
526 for (i = 1; i <= aNbV; ++i) {
527 Handle(BOPDS_PaveBlock) aPB1, aPB2;
528 const BOPDS_CoupleOfPaveBlocks& aCPB = aMVCPB.FindFromIndex(i);
529 aCPB.PaveBlocks(aPB1, aPB2);
531 aMEdges.Remove(aPB1->OriginalEdge());
532 aMEdges.Remove(aPB2->OriginalEdge());
535 SplitPaveBlocks(aMEdges, Standard_False);
538 //-----------------------------------------------------scope t
542 //=======================================================================
543 //function : PerformVerticesEE
545 //=======================================================================
546 void BOPAlgo_PaveFiller::PerformNewVertices
547 (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
548 const Handle(NCollection_BaseAllocator)& theAllocator,
549 const Standard_Boolean bIsEEIntersection)
551 Standard_Integer aNbV = theMVCPB.Extent();
556 Standard_Real aTolAdd = myFuzzyValue / 2.;
558 // 1. Fuse the new vertices
559 TopTools_IndexedDataMapOfShapeListOfShape aImages;
560 TreatNewVertices(theMVCPB, aImages);
562 // 2. Add new vertices to myDS and connect indices to CPB structure
563 BOPDS_VectorOfInterfEE& aEEs = myDS->InterfEE();
564 BOPDS_VectorOfInterfEF& aEFs = myDS->InterfEF();
566 Standard_Integer i, aNb = aImages.Extent();
567 for (i = 1; i <= aNb; ++i) {
568 const TopoDS_Vertex& aV = TopoDS::Vertex(aImages.FindKey(i));
569 const TopTools_ListOfShape& aLVSD = aImages.FindFromIndex(i);
572 aSI.SetShapeType(TopAbs_VERTEX);
574 Standard_Integer iV = myDS->Append(aSI);
576 BOPDS_ShapeInfo& aSIDS = myDS->ChangeShapeInfo(iV);
577 Bnd_Box& aBox = aSIDS.ChangeBox();
578 aBox.Add(BRep_Tool::Pnt(aV));
579 aBox.SetGap(BRep_Tool::Tolerance(aV) + aTolAdd);
581 TopTools_ListIteratorOfListOfShape aItLS(aLVSD);
582 for (; aItLS.More(); aItLS.Next()) {
583 const TopoDS_Shape& aVx = aItLS.Value();
584 BOPDS_CoupleOfPaveBlocks &aCPB = theMVCPB.ChangeFromKey(aVx);
586 // update interference
587 Standard_Integer iX = aCPB.IndexInterf();
588 BOPDS_Interf *aInt = bIsEEIntersection ? (BOPDS_Interf*)(&aEEs(iX)) : (BOPDS_Interf*) (&aEFs(iX));
589 aInt->SetIndexNew(iV);
593 // 3. Map PaveBlock/ListOfVertices to add to this PaveBlock ->aMPBLI
594 BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, theAllocator);
595 for (i = 1; i <= aNbV; ++i) {
596 const BOPDS_CoupleOfPaveBlocks& aCPB = theMVCPB.FindFromIndex(i);
597 Standard_Integer iV = aCPB.Index();
599 Handle(BOPDS_PaveBlock) aPB[2];
600 aCPB.PaveBlocks(aPB[0], aPB[1]);
601 for (Standard_Integer j = 0; j < 2; ++j) {
602 TColStd_ListOfInteger *pLI = aMPBLI.ChangeSeek(aPB[j]);
604 pLI = &aMPBLI(aMPBLI.Add(aPB[j], TColStd_ListOfInteger(theAllocator)));
608 if (aPB[0] == aPB[1]) {
614 // 4. Compute Extra Paves and split Pave blocks by the Extra paves
615 IntersectVE(aMPBLI, Standard_False);
617 //=======================================================================
618 //function : TreatNewVertices
620 //=======================================================================
621 void BOPAlgo_PaveFiller::TreatNewVertices
622 (const BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
623 TopTools_IndexedDataMapOfShapeListOfShape& myImages)
626 // Prepare for intersection
627 TopTools_IndexedDataMapOfShapeReal aVerts;
628 Standard_Integer i, aNbV = theMVCPB.Extent();
629 for (i = 1; i <= aNbV; ++i) {
630 const TopoDS_Shape& aV = theMVCPB.FindKey(i);
631 Standard_Real aTol = theMVCPB.FindFromIndex(i).Tolerance();
632 aVerts.Add(aV, aTol);
635 // Perform intersection
636 TopTools_ListOfListOfShape aChains;
637 BOPAlgo_Tools::IntersectVertices(aVerts, myFuzzyValue, aChains);
639 // Treat the results - make new vertices for each chain
640 TopTools_ListOfListOfShape::Iterator aItC(aChains);
641 for (; aItC.More(); aItC.Next()) {
642 const TopTools_ListOfShape& aLVSD = aItC.Value();
645 BOPTools_AlgoTools::MakeVertex(aLVSD, aVNew);
646 myImages.Add(aVNew, aLVSD);
649 //=======================================================================
650 //function : FillShrunkData
652 //=======================================================================
653 void BOPAlgo_PaveFiller::FillShrunkData(Handle(BOPDS_PaveBlock)& thePB)
656 Standard_Integer nV1, nV2;
657 thePB->Indices(nV1, nV2);
658 const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1)));
659 const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2)));
661 Standard_Integer nE = -1;
662 if (!thePB->HasEdge(nE))
664 nE = thePB->OriginalEdge();
669 const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE)));
671 Standard_Real aT1, aT2;
672 thePB->Range(aT1, aT2);
674 IntTools_ShrunkRange aSR;
675 aSR.SetContext(myContext);
676 aSR.SetData(aE, aT1, aT2, aV1, aV2);
678 // Analyze the results of computations
679 AnalyzeShrunkData(thePB, aSR);
681 //=======================================================================
682 // function: AnalyzeShrunkData
684 //=======================================================================
685 void BOPAlgo_PaveFiller::AnalyzeShrunkData(const Handle(BOPDS_PaveBlock)& thePB,
686 const IntTools_ShrunkRange& theSR)
688 // in case of error treat the warning status
689 Standard_Boolean bWholeEdge = Standard_False;
690 TopoDS_Shape aWarnShape;
692 if (!theSR.IsDone() || !theSR.IsSplittable()) {
693 Standard_Real aEFirst, aELast, aPBFirst, aPBLast;
694 BRep_Tool::Range(theSR.Edge(), aEFirst, aELast);
695 thePB->Range(aPBFirst, aPBLast);
696 bWholeEdge = !(aPBFirst > aEFirst || aPBLast < aELast);
697 if (bWholeEdge && thePB->OriginalEdge() >= 0) {
698 aWarnShape = theSR.Edge();
701 const TopoDS_Shape& aV1 = myDS->Shape(thePB->Pave1().Index());
702 const TopoDS_Shape& aV2 = myDS->Shape(thePB->Pave2().Index());
703 BRep_Builder().MakeCompound(TopoDS::Compound(aWarnShape));
704 BRep_Builder().Add(aWarnShape, theSR.Edge());
705 BRep_Builder().Add(aWarnShape, aV1);
706 BRep_Builder().Add(aWarnShape, aV2);
709 if (!theSR.IsDone()) {
711 AddWarning (new BOPAlgo_AlertTooSmallEdge (aWarnShape));
713 AddWarning (new BOPAlgo_AlertBadPositioning (aWarnShape));
714 Standard_Real aTS1, aTS2;
715 theSR.ShrunkRange(aTS1, aTS2);
716 thePB->SetShrunkData(aTS1, aTS2, Bnd_Box(), Standard_False);
721 AddWarning (new BOPAlgo_AlertNotSplittableEdge (aWarnShape));
723 AddWarning (new BOPAlgo_AlertBadPositioning (aWarnShape));
726 Standard_Real aTS1, aTS2;
727 theSR.ShrunkRange(aTS1, aTS2);
728 Bnd_Box aBox = theSR.BndBox();
729 aBox.SetGap(aBox.GetGap() + myFuzzyValue / 2.);
730 thePB->SetShrunkData(aTS1, aTS2, aBox, theSR.IsSplittable());
732 //=======================================================================
733 //function : ForceInterfVE
735 //=======================================================================
736 Standard_Boolean BOPAlgo_PaveFiller::ForceInterfVE(const Standard_Integer nV,
737 Handle(BOPDS_PaveBlock)& aPB,
738 TColStd_MapOfInteger& theMEdges)
740 Standard_Integer nE, nVx, nVSD, iFlag;
741 Standard_Real aT, aTolVNew;
743 nE = aPB->OriginalEdge();
745 const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
746 if (aSIE.HasSubShape(nV)) {
747 return Standard_True;
750 if (myDS->HasInterf(nV, nE)) {
751 return Standard_True;
754 if (myDS->HasInterfShapeSubShapes(nV, nE)) {
755 return Standard_True;
758 if (aPB->Pave1().Index() == nV ||
759 aPB->Pave2().Index() == nV) {
760 return Standard_True;
764 if (myDS->HasShapeSD(nV, nVSD)) {
768 const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nVx);
769 const TopoDS_Edge& aE = *(TopoDS_Edge*) &myDS->Shape(nE);
771 iFlag = myContext->ComputeVE(aV, aE, aT, aTolVNew, myFuzzyValue);
772 if (iFlag == 0 || iFlag == -4) {
776 BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
777 aVEs.SetIncrement(10);
779 BOPDS_InterfVE& aVE=aVEs.Appended();
780 aVE.SetIndices(nV, nE);
781 aVE.SetParameter(aT);
783 myDS->AddInterf(nV, nE);
785 // 3 update vertex V/E if necessary
786 nVx=UpdateVertex(nV, aTolVNew);
788 if (myDS->IsNewShape(nVx)) {
789 aVE.SetIndexNew(nVx);
791 // 5 append ext pave to pave block
793 aPave.SetParameter(aT);
794 aPB->AppendExtPave(aPave);
798 // check for self-interference
799 Standard_Integer iRV = myDS->Rank(nV);
800 if (iRV >= 0 && iRV == myDS->Rank(nE)) {
801 // add warning status
803 BRep_Builder().MakeCompound(aWC);
804 BRep_Builder().Add(aWC, aV);
805 BRep_Builder().Add(aWC, aE);
806 AddWarning (new BOPAlgo_AlertSelfInterferingShape (aWC));
808 return Standard_True;
810 return Standard_False;
813 //=======================================================================
814 //function : GetPBBox
816 //=======================================================================
817 Standard_Boolean BOPAlgo_PaveFiller::GetPBBox(const TopoDS_Edge& theE,
818 const Handle(BOPDS_PaveBlock)& thePB,
819 BOPAlgo_DataMapOfPaveBlockBndBox& thePBBox,
820 Standard_Real& theFirst,
821 Standard_Real& theLast,
822 Standard_Real& theSFirst,
823 Standard_Real& theSLast,
826 thePB->Range(theFirst, theLast);
827 // check the validity of PB's range
828 Standard_Boolean bValid = theLast - theFirst > Precision::PConfusion();
834 if (thePB->HasShrunkData()) {
835 Standard_Boolean bIsSplittable;
836 thePB->ShrunkData(theSFirst, theSLast, theBox, bIsSplittable);
840 theSFirst = theFirst;
843 if (thePBBox.IsBound(thePB)) {
844 theBox = thePBBox.Find(thePB);
847 // build bounding box
848 BRepAdaptor_Curve aBAC(theE);
849 Standard_Real aTol = BRep_Tool::Tolerance(theE) + Precision::Confusion();
850 BndLib_Add3dCurve::Add(aBAC, theSFirst, theSLast, aTol, theBox);
851 thePBBox.Bind(thePB, theBox);
856 //=======================================================================
857 //function : UpdateVerticesOfCB
859 //=======================================================================
860 void BOPAlgo_PaveFiller::UpdateVerticesOfCB()
862 // Fence map to avoid checking same Common block twice
863 BOPDS_MapOfPaveBlock aMPBFence;
865 BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
866 const Standard_Integer aNbPBP = aPBP.Length();
867 for (Standard_Integer i = 0; i < aNbPBP; ++i)
869 const BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
870 BOPDS_ListIteratorOfListOfPaveBlock itPB(aLPB);
871 for (; itPB.More(); itPB.Next())
873 const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(itPB.Value());
877 const Handle(BOPDS_PaveBlock)& aPBR = aCB->PaveBlock1();
878 if (!aMPBFence.Add(aPBR))
881 Standard_Real aTolCB = aCB->Tolerance();
884 UpdateVertex(aPBR->Pave1().Index(), aTolCB);
885 UpdateVertex(aPBR->Pave2().Index(), aTolCB);
891 //=======================================================================
892 //function : ForceInterfEE
894 //=======================================================================
895 void BOPAlgo_PaveFiller::ForceInterfEE()
897 // Now that we have vertices increased and unified, try to find additional
898 // common blocks among the pairs of edges.
899 // Since all real intersections should have already happened, here we
900 // are interested in common blocks only, thus we need to check only
901 // those pairs of pave blocks with the same bounding vertices.
903 Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
905 // Initialize pave blocks for all vertices which participated in intersections
906 const Standard_Integer aNbS = myDS->NbSourceShapes();
907 for (Standard_Integer i = 0; i < aNbS; ++i)
909 const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
910 if (aSI.ShapeType() == TopAbs_VERTEX)
912 if (myDS->HasInterf(i))
913 myDS->InitPaveBlocksForVertex(i);
917 // Fill the connection map from bounding vertices to pave blocks
918 // having those bounding vertices
919 NCollection_IndexedDataMap<BOPDS_Pair,
920 BOPDS_ListOfPaveBlock,
921 BOPDS_PairMapHasher> aPBMap(1, anAlloc);
922 // Fence map of pave blocks
923 BOPDS_MapOfPaveBlock aMPBFence(1, anAlloc);
925 for (Standard_Integer i = 0; i < aNbS; ++i)
927 const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
928 if (aSI.ShapeType() != TopAbs_EDGE)
932 if (!aSI.HasReference())
933 // Edge has no pave blocks
940 const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks(i);
941 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
942 for (; aItLPB.More(); aItLPB.Next())
944 const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
945 const Handle(BOPDS_PaveBlock)& aPBR = myDS->RealPaveBlock(aPB);
946 if (!aMPBFence.Add(aPBR))
950 Standard_Integer nV1, nV2;
951 aPBR->Indices(nV1, nV2);
953 // Add pave block to a map
954 BOPDS_Pair aPair(nV1, nV2);
955 BOPDS_ListOfPaveBlock *pList = aPBMap.ChangeSeek(aPair);
957 pList = &aPBMap(aPBMap.Add(aPair, BOPDS_ListOfPaveBlock(anAlloc)));
962 Standard_Integer aNbPB = aPBMap.Extent();
966 const Standard_Boolean bSICheckMode = (myArguments.Extent() == 1);
968 // Prepare pave blocks with the same vertices for intersection.
969 BOPAlgo_VectorOfEdgeEdge aVEdgeEdge;
971 for (Standard_Integer i = 1; i <= aNbPB; ++i)
973 const BOPDS_ListOfPaveBlock& aLPB = aPBMap(i);
974 if (aLPB.Extent() < 2)
977 const BOPDS_Pair& aPair = aPBMap.FindKey(i);
978 Standard_Integer nV1, nV2;
979 aPair.Indices(nV1, nV2);
981 const TopoDS_Vertex& aV1 = TopoDS::Vertex(myDS->Shape(nV1));
982 const TopoDS_Vertex& aV2 = TopoDS::Vertex(myDS->Shape(nV2));
984 // Use the max tolerance of vertices as Fuzzy value for intersection of edges.
985 // In the Self-Interference check mode we are interested in real
986 // intersections only, so use only the real tolerance of edges,
987 // no need to use the extended tolerance.
988 Standard_Real aTolAdd = (bSICheckMode ? myFuzzyValue :
989 2 * Max(BRep_Tool::Tolerance(aV1), BRep_Tool::Tolerance(aV2)));
991 // All possible pairs combined from the list <aLPB> should be checked
992 BOPDS_ListIteratorOfListOfPaveBlock aItLPB1(aLPB);
993 for (; aItLPB1.More(); aItLPB1.Next())
995 const Handle(BOPDS_PaveBlock)& aPB1 = aItLPB1.Value();
996 const Handle(BOPDS_CommonBlock)& aCB1 = myDS->CommonBlock(aPB1);
997 const Standard_Integer nE1 = aPB1->OriginalEdge();
998 const Standard_Integer iR1 = myDS->Rank(nE1);
999 const TopoDS_Edge& aE1 = TopoDS::Edge(myDS->Shape(nE1));
1000 Standard_Real aT11, aT12;
1001 aPB1->Range(aT11, aT12);
1002 BRepAdaptor_Curve aBAC1(aE1);
1005 aBAC1.D1((aT11 + aT12) * 0.5, aPm, aVTgt1);
1006 if (aVTgt1.SquareMagnitude() < gp::Resolution())
1010 BOPDS_ListIteratorOfListOfPaveBlock aItLPB2 = aItLPB1;
1011 for (aItLPB2.Next(); aItLPB2.More(); aItLPB2.Next())
1013 const Handle(BOPDS_PaveBlock)& aPB2 = aItLPB2.Value();
1014 const Handle(BOPDS_CommonBlock)& aCB2 = myDS->CommonBlock(aPB2);
1015 const Standard_Integer nE2 = aPB2->OriginalEdge();
1016 const Standard_Integer iR2 = myDS->Rank(nE2);
1018 // Check that the edges came from different arguments
1021 // If the sharing of the vertices is not original, but has been acquired
1022 // during the operation, check the coincidence of the edges even if
1023 // they came from the same argument
1024 if ((!myDS->IsNewShape(nV1) && (myDS->Rank(nV1) == iR1)) ||
1025 (!myDS->IsNewShape(nV2) && (myDS->Rank(nV2) == iR2)))
1029 // Check that the Pave blocks do not form the Common block already
1030 if (!aCB1.IsNull() && !aCB2.IsNull())
1036 const TopoDS_Edge& aE2 = TopoDS::Edge(myDS->Shape(nE2));
1037 Standard_Real aT21, aT22;
1038 aPB2->Range(aT21, aT22);
1040 // Check the angle between edges in the middle point.
1041 // If the angle is more than 25 degrees, do not use the additional
1042 // tolerance, as it may lead to undesired unification of edges
1043 Standard_Boolean bUseAddTol = Standard_True;
1045 BRepAdaptor_Curve aBAC2(aE2);
1046 if (aBAC1.GetType() != GeomAbs_Line ||
1047 aBAC2.GetType() != GeomAbs_Line)
1049 GeomAPI_ProjectPointOnCurve& aProjPC = myContext->ProjPC(aE2);
1050 aProjPC.Perform(aPm);
1051 if (!aProjPC.NbPoints())
1056 aBAC2.D1(aProjPC.LowerDistanceParameter(), aPm2, aVTgt2);
1057 if (aVTgt2.SquareMagnitude() < gp::Resolution())
1060 // The angle should be close to zero
1061 Standard_Real aCos = aVTgt1.Dot (aVTgt2.Normalized());
1062 if (Abs(aCos) < 0.9063)
1063 bUseAddTol = Standard_False;
1067 // Add pair for intersection
1068 BOPAlgo_EdgeEdge& anEdgeEdge = aVEdgeEdge.Appended();
1069 anEdgeEdge.UseQuickCoincidenceCheck(Standard_True);
1070 anEdgeEdge.SetPaveBlock1(aPB1);
1071 anEdgeEdge.SetPaveBlock2(aPB2);
1072 anEdgeEdge.SetEdge1(aE1, aT11, aT12);
1073 anEdgeEdge.SetEdge2(aE2, aT21, aT22);
1074 anEdgeEdge.SetBoxes (myDS->ShapeInfo(nE1).Box(), myDS->ShapeInfo (nE2).Box());
1077 anEdgeEdge.SetFuzzyValue(myFuzzyValue + aTolAdd);
1081 anEdgeEdge.SetFuzzyValue(myFuzzyValue);
1083 if (myProgressScope != NULL)
1085 anEdgeEdge.SetProgressIndicator(*myProgressScope);
1091 Standard_Integer aNbPairs = aVEdgeEdge.Length();
1099 // Perform intersection of the found pairs
1100 BOPTools_Parallel::Perform (myRunParallel, aVEdgeEdge);
1102 BOPDS_VectorOfInterfEE& aEEs = myDS->InterfEE();
1104 aEEs.SetIncrement(10);
1106 // Analyze the results of intersection looking for TopAbs_EDGE
1107 // intersection type only.
1109 BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock aMPBLPB(1, anAlloc);
1111 for (Standard_Integer i = 0; i < aNbPairs; ++i)
1113 BOPAlgo_EdgeEdge& anEdgeEdge = aVEdgeEdge(i);
1114 if (!anEdgeEdge.IsDone() || anEdgeEdge.HasErrors())
1116 // Warn about failed intersection of sub-shapes
1117 const TopoDS_Shape& aE1 = myDS->Shape(anEdgeEdge.PaveBlock1()->OriginalEdge());
1118 const TopoDS_Shape& aE2 = myDS->Shape(anEdgeEdge.PaveBlock2()->OriginalEdge());
1119 AddIntersectionFailedWarning(aE1, aE2);
1123 const IntTools_SequenceOfCommonPrts& aCParts = anEdgeEdge.CommonParts();
1124 if (aCParts.Length() != 1)
1127 const IntTools_CommonPrt& aCP = aCParts(1);
1128 if (aCP.Type() != TopAbs_EDGE)
1131 Handle(BOPDS_PaveBlock) aPB[] = {anEdgeEdge.PaveBlock1(), anEdgeEdge.PaveBlock2()};
1132 const Standard_Integer nE1 = aPB[0]->OriginalEdge();
1133 const Standard_Integer nE2 = aPB[1]->OriginalEdge();
1135 if (myDS->Rank(nE1) == myDS->Rank(nE2))
1137 // Add acquired self-interference warning
1138 TopoDS_Compound aWC;
1139 BRep_Builder().MakeCompound(aWC);
1140 BRep_Builder().Add(aWC, myDS->Shape(nE1));
1141 BRep_Builder().Add(aWC, myDS->Shape(nE2));
1142 AddWarning(new BOPAlgo_AlertAcquiredSelfIntersection(aWC));
1145 BOPDS_InterfEE& aEE = aEEs.Appended();
1146 aEE.SetIndices(nE1, nE2);
1147 aEE.SetCommonPart(aCP);
1148 myDS->AddInterf(nE1, nE2);
1150 // Fill map for common blocks creation
1151 for (Standard_Integer j = 0; j < 2; ++j)
1153 if (myDS->IsCommonBlock(aPB[j]))
1155 const BOPDS_ListOfPaveBlock& aLPBCB = myDS->CommonBlock(aPB[j])->PaveBlocks();
1156 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPBCB);
1157 for (; aItLPB.More(); aItLPB.Next())
1158 BOPAlgo_Tools::FillMap<Handle(BOPDS_PaveBlock),
1159 TColStd_MapTransientHasher>(aPB[j], aItLPB.Value(), aMPBLPB, anAlloc);
1162 BOPAlgo_Tools::FillMap<Handle(BOPDS_PaveBlock),
1163 TColStd_MapTransientHasher>(aPB[0], aPB[1], aMPBLPB, anAlloc);
1166 // Create new common blocks of coinciding pairs.
1167 BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, anAlloc, myDS);