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
10 // under the terms of the GNU Lesser General Public 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.
18 #include <BOPAlgo_PaveFiller.ixx>
20 #include <Precision.hxx>
21 #include <NCollection_IncAllocator.hxx>
22 #include <NCollection_UBTreeFiller.hxx>
24 #include <Bnd_Box.hxx>
26 #include <GeomAPI_ProjectPointOnCurve.hxx>
28 #include <TopoDS_Edge.hxx>
29 #include <TopoDS_Vertex.hxx>
30 #include <TopoDS_Compound.hxx>
31 #include <BRep_Tool.hxx>
32 #include <BRep_Builder.hxx>
33 #include <BRepTools.hxx>
34 #include <BRepBndLib.hxx>
36 #include <IntTools_EdgeEdge.hxx>
37 #include <IntTools_Range.hxx>
38 #include <IntTools_SequenceOfCommonPrts.hxx>
39 #include <IntTools_CommonPrt.hxx>
40 #include <IntTools_SequenceOfRanges.hxx>
42 #include <BOPTools_AlgoTools.hxx>
44 #include <BOPCol_DataMapOfShapeInteger.hxx>
45 #include <BOPCol_DataMapOfIntegerShape.hxx>
46 #include <BOPCol_IndexedDataMapOfShapeBox.hxx>
47 #include <BOPCol_BoxBndTree.hxx>
49 #include <BOPInt_Context.hxx>
50 #include <BOPInt_ShrunkRange.hxx>
51 #include <BOPInt_Tools.hxx>
53 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
54 #include <BOPDS_MapOfPaveBlock.hxx>
55 #include <BOPDS_CommonBlock.hxx>
56 #include <BOPDS_CoupleOfPaveBlocks.hxx>
57 #include <BOPDS_DataMapOfPaveBlockListOfInteger.hxx>
58 #include <BOPDS_Iterator.hxx>
59 #include <BOPDS_VectorOfInterfEE.hxx>
60 #include <BOPDS_Interf.hxx>
61 #include <BOPDS_Pave.hxx>
63 #include <BOPAlgo_Tools.hxx>
66 //=======================================================================
67 // function: PerformEE
69 //=======================================================================
70 void BOPAlgo_PaveFiller::PerformEE()
72 Standard_Boolean bJustAdd;
73 Standard_Integer i, iX, iSize, nE1, nE2;
74 Standard_Integer aNbCPrts;
75 Standard_Real aTS11, aTS12, aTS21, aTS22,
76 aT11, aT12, aT21, aT22;
77 TopAbs_ShapeEnum aType;
78 BOPDS_ListIteratorOfListOfPaveBlock aIt1, aIt2;
79 Handle(NCollection_IncAllocator) aAllocator;
80 BOPDS_MapOfPaveBlock aMPBToUpdate;
81 BOPDS_MapIteratorOfMapOfPaveBlock aItPB;
85 myIterator->Initialize(TopAbs_EDGE, TopAbs_EDGE);
86 iSize=myIterator->ExpectedLength();
91 //-----------------------------------------------------scope f
92 aAllocator=new NCollection_IncAllocator();
93 BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock aMPBLPB(100, aAllocator);
94 BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMVCPB(100, aAllocator);
96 BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
97 aEEs.SetStartSize(iSize);
98 aEEs.SetIncrement(iSize);
101 for (; myIterator->More(); myIterator->Next()) {
102 myIterator->Value(nE1, nE2, bJustAdd);
107 const BOPDS_ShapeInfo& aSIE1=myDS->ShapeInfo(nE1);
108 if (aSIE1.HasFlag()){
111 const BOPDS_ShapeInfo& aSIE2=myDS->ShapeInfo(nE2);
112 if (aSIE2.HasFlag()){
116 const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aSIE1.Shape()));
117 const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aSIE2.Shape()));
119 BOPDS_ListOfPaveBlock& aLPB1=myDS->ChangePaveBlocks(nE1);
120 BOPDS_ListOfPaveBlock& aLPB2=myDS->ChangePaveBlocks(nE2);
122 aIt1.Initialize(aLPB1);
123 for (; aIt1.More(); aIt1.Next()) {
126 Handle(BOPDS_PaveBlock)& aPB1=aIt1.ChangeValue();
127 if (!aPB1->HasShrunkData()) {
128 FillShrunkData(aPB1);
129 if (myWarningStatus) {
133 aPB1->ShrunkData(aTS11, aTS12, aBB1);
135 aIt2.Initialize(aLPB2);
136 for (; aIt2.More(); aIt2.Next()) {
139 Handle(BOPDS_PaveBlock)& aPB2=aIt2.ChangeValue();
140 if (!aPB2->HasShrunkData()) {
141 FillShrunkData(aPB2);
142 if (myWarningStatus) {
146 aPB2->ShrunkData(aTS21, aTS22, aBB2);
148 if (aBB1.IsOut(aBB2)) {
152 IntTools_EdgeEdge anEdgeEdge;
154 aPB1->Range(aT11, aT12);
155 aPB2->Range(aT21, aT22);
157 anEdgeEdge.SetEdge1(aE1, aT11, aT12);
158 anEdgeEdge.SetEdge2(aE2, aT21, aT22);
160 anEdgeEdge.Perform();
161 if (!anEdgeEdge.IsDone()) {
165 IntTools_Range aR11(aT11, aTS11), aR12(aTS12, aT12),
166 aR21(aT21, aTS21), aR22(aTS22, aT22);
168 const IntTools_SequenceOfCommonPrts& aCPrts = anEdgeEdge.CommonParts();
169 aNbCPrts=aCPrts.Length();
170 for (i=1; i<=aNbCPrts; ++i) {
171 const IntTools_CommonPrt& aCPart=aCPrts(i);
174 case TopAbs_VERTEX: {
175 Standard_Boolean bIsOnPave[4], bFlag;
176 Standard_Integer nV[4], j;
177 Standard_Real aT1, aT2, aTol;
179 IntTools_Range aCR1, aCR2;
181 BOPInt_Tools::VertexParameters(aCPart, aT1, aT2);
182 aTol = Precision::Confusion();
183 aCR1 = aCPart.Range1();
184 aCR2 = aCPart.Ranges2()(1);
186 //decide to keep the pave or not
187 bIsOnPave[0] = BOPInt_Tools::IsOnPave1(aT1, aR11, aTol) ||
188 BOPInt_Tools::IsOnPave1(aR11.First(), aCR1, aTol);
189 bIsOnPave[1] = BOPInt_Tools::IsOnPave1(aT1, aR12, aTol) ||
190 BOPInt_Tools::IsOnPave1(aR12.Last(), aCR1, aTol);
191 bIsOnPave[2] = BOPInt_Tools::IsOnPave1(aT2, aR21, aTol) ||
192 BOPInt_Tools::IsOnPave1(aR21.First(), aCR2, aTol);
193 bIsOnPave[3] = BOPInt_Tools::IsOnPave1(aT2, aR22, aTol) ||
194 BOPInt_Tools::IsOnPave1(aR22.Last(), aCR2, aTol);
196 aPB1->Indices(nV[0], nV[1]);
197 aPB2->Indices(nV[2], nV[3]);
199 if((bIsOnPave[0] && bIsOnPave[2]) || (bIsOnPave[0] && bIsOnPave[3]) ||
200 (bIsOnPave[1] && bIsOnPave[2]) || (bIsOnPave[1] && bIsOnPave[3])) {
204 bFlag = Standard_False;
205 for (j = 0; j < 4; ++j) {
207 //add interf VE(nV[j], nE)
208 Handle(BOPDS_PaveBlock)& aPB = (j < 2) ? aPB2 : aPB1;
209 ForceInterfVE(nV[j], aPB, aMPBToUpdate);
210 bFlag = Standard_True;
218 BOPTools_AlgoTools::MakeNewVertex(aE1, aT1, aE2, aT2, aVnew);
221 Standard_Integer nVS[2], iFound, k;
222 Standard_Real aTolVx, aTolVnew, aD2, aDT2;
223 BOPCol_MapOfInteger aMV;
231 if (aMV.Contains(nV[2])) {
235 if (aMV.Contains(nV[3])) {
240 aTolVnew=BRep_Tool::Tolerance(aVnew);
241 aPnew=BRep_Tool::Pnt(aVnew);
243 for (k=0; k<=j; ++k) {
244 const TopoDS_Vertex& aVx= *(TopoDS_Vertex*)&(myDS->Shape(nVS[k]));
245 aTolVx=BRep_Tool::Tolerance(aVx);
246 aPx=BRep_Tool::Pnt(aVx);
247 aD2=aPnew.SquareDistance(aPx);
249 aDT2=100.*(aTolVnew+aTolVx)*(aTolVnew+aTolVx);
264 BOPDS_InterfEE& aEE=aEEs(iX);
265 aEE.SetIndices(nE1, nE2);
266 aEE.SetCommonPart(aCPart);
268 myDS->AddInterf(nE1, nE2);
270 BOPDS_CoupleOfPaveBlocks aCPB;
272 aCPB.SetPaveBlocks(aPB1, aPB2);
273 aCPB.SetIndexInterf(iX);
274 aMVCPB.Add(aVnew, aCPB);
275 }//case TopAbs_VERTEX:
283 Standard_Boolean bHasSameBounds;
284 bHasSameBounds=aPB1->HasSameBounds(aPB2);
285 if (!bHasSameBounds) {
290 BOPDS_InterfEE& aEE=aEEs(iX);
291 aEE.SetIndices(nE1, nE2);
292 aEE.SetCommonPart(aCPart);
294 myDS->AddInterf(nE1, nE2);
296 BOPAlgo_Tools::FillMap(aPB1, aPB2, aMPBLPB, aAllocator);
302 }//for (i=1; i<=aNbCPrts; i++) {
305 }// for (; aIt2.More(); aIt2.Next()) {
306 }// for (; aIt1.More(); aIt1.Next()) {
309 //=========================================
311 //=========================================
312 aItPB.Initialize(aMPBToUpdate);
313 for (; aItPB.More(); aItPB.Next()) {
314 Handle(BOPDS_PaveBlock) aPB=aItPB.Value();
315 if (!myDS->IsCommonBlock(aPB)) {
316 myDS->UpdatePaveBlock(aPB);
319 const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
320 myDS->UpdateCommonBlock(aCB);
324 BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, aAllocator, myDS);
325 PerformVerticesEE(aMVCPB, aAllocator);
326 //-----------------------------------------------------scope t
329 aMPBToUpdate.Clear();
330 aAllocator.Nullify();
332 //=======================================================================
333 //function : PerformVertices
335 //=======================================================================
336 Standard_Integer BOPAlgo_PaveFiller::PerformVerticesEE
337 (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
338 Handle(NCollection_BaseAllocator)& theAllocator)
340 Standard_Integer aNbV, iRet;
343 aNbV=theMVCPB.Extent();
348 Standard_Integer nVx, iV, j, nE, iFlag, iX, i, aNb;
351 BOPCol_ListIteratorOfListOfShape aItLS;
352 BOPCol_ListIteratorOfListOfInteger aItLI;
353 BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
357 BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, theAllocator);
358 BOPCol_ListOfShape aLS(theAllocator);
359 BOPCol_IndexedDataMapOfShapeInteger aMVI(100, theAllocator);
360 BOPCol_IndexedDataMapOfShapeListOfShape aImages;
362 aSI.SetShapeType(TopAbs_VERTEX);
363 BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
365 // 1 prepare arguments
368 for (i=1; i<=aNbV; ++i) {
369 const TopoDS_Shape& aS=theMVCPB.FindKey(i);
370 const BOPDS_CoupleOfPaveBlocks& aCPB=theMVCPB.FindFromIndex(i);
371 iV=aCPB.IndexInterf();
376 TreatNewVertices(aMVI, aImages);
378 // 3 Add new vertices to myDS;
379 // connect indices to CPB structure
380 aNb = aImages.Extent();
381 for (i=1; i<=aNb; ++i) {
382 const TopoDS_Vertex& aV=(*(TopoDS_Vertex*)(&aImages.FindKey(i)));
383 const BOPCol_ListOfShape& aLVSD=aImages.FindFromIndex(i);
386 iV=myDS->Append(aSI);
388 BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(iV);
389 Bnd_Box& aBox=aSIDS.ChangeBox();
390 BRepBndLib::Add(aV, aBox);
392 aItLS.Initialize(aLVSD);
393 for (; aItLS.More(); aItLS.Next()) {
394 const TopoDS_Shape& aVx = aItLS.Value();
395 BOPDS_CoupleOfPaveBlocks &aCPB=theMVCPB.ChangeFromKey(aVx);
397 // update EE interference
398 iX=aCPB.IndexInterf();
399 BOPDS_InterfEE& aEE=aEEs(iX);
404 // 4 Map PaveBlock/ListOfVertices to add to this PaveBlock ->aMPBLI
406 Handle(BOPDS_PaveBlock) aPB[2];
408 for (i=1; i<=aNbV; ++i) {
409 const BOPDS_CoupleOfPaveBlocks& aCPB=theMVCPB.FindFromIndex(i);
411 aCPB.PaveBlocks(aPB[0], aPB[1]);
412 for (j=0; j<2; ++j) {
413 if (aMPBLI.Contains(aPB[j])) {
414 BOPCol_ListOfInteger& aLI=aMPBLI.ChangeFromKey(aPB[j]);
418 BOPCol_ListOfInteger aLI(theAllocator);
420 aMPBLI.Add(aPB[j], aLI);
427 // 5.1 Compute Extra Paves and
428 // 5.2. Add Extra Paves to the PaveBlocks
430 for(i=1; i<=aNb; ++i) {
431 Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
432 nE=aPB->OriginalEdge();
433 const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE)));
435 const BOPCol_ListOfInteger& aLI=aMPBLI.FindFromIndex(i);
436 aItLI.Initialize(aLI);
437 for (; aItLI.More(); aItLI.Next()) {
439 const TopoDS_Vertex& aVx=(*(TopoDS_Vertex *)(&myDS->Shape(nVx)));
441 iFlag=myContext->ComputeVE (aVx, aE, aT);
444 aPave.SetParameter(aT);
445 aPB->AppendExtPave(aPave);
449 // 6 Split PaveBlocksa
451 for(i=1; i<=aNb; ++i) {
452 Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
453 nE=aPB->OriginalEdge();
455 if (!myDS->IsCommonBlock(aPB)) {
456 myDS->UpdatePaveBlock(aPB);
459 const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
460 myDS->UpdateCommonBlock(aCB);
462 }//for (; aItMPBLI.More(); aItMPBLI.Next()) {
467 //=======================================================================
468 //function : TreatNewVertices
470 //=======================================================================
471 void BOPAlgo_PaveFiller::TreatNewVertices
472 (const BOPCol_IndexedDataMapOfShapeInteger& aMapVI,
473 BOPCol_IndexedDataMapOfShapeListOfShape& myImages)
475 Standard_Integer j, i, aNbV, aNbVSD;
479 BOPCol_IndexedMapOfShape aMVProcessed;
481 BOPCol_ListIteratorOfListOfInteger aIt;
482 BOPCol_IndexedDataMapOfShapeListOfShape aMVLV;
483 BOPCol_DataMapOfIntegerShape aMIS;
484 BOPCol_IndexedDataMapOfShapeBox aMSB;
486 BOPCol_BoxBndTreeSelector aSelector;
487 BOPCol_BoxBndTree aBBTree;
488 NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
490 aNbV = aMapVI.Extent();
491 for (i=1; i<=aNbV; ++i) {
492 const TopoDS_Shape& aV=aMapVI.FindKey(i);
495 aTol=BRep_Tool::Tolerance(*(TopoDS_Vertex*)(&aV));
497 BRepBndLib::Add(aV, aBox);
499 aTreeFiller.Add(i, aBox);
508 for (i=1; i<=aNbV; ++i) {
509 const TopoDS_Shape& aV=aMapVI.FindKey(i);
511 if (aMVProcessed.Contains(aV)) {
515 Standard_Integer aNbIP, aIP, aNbIP1, aIP1;
516 BOPCol_ListOfShape aLVSD;
517 BOPCol_MapOfInteger aMIP, aMIP1, aMIPC;
518 BOPCol_MapIteratorOfMapOfInteger aIt1;
523 aIt1.Initialize(aMIP);
524 for(; aIt1.More(); aIt1.Next()) {
526 if (aMIPC.Contains(aIP)) {
530 const TopoDS_Shape& aVP=aMIS.Find(aIP);
531 const Bnd_Box& aBoxVP=aMSB.FindFromKey(aVP);
534 aSelector.SetBox(aBoxVP);
536 aNbVSD=aBBTree.Select(aSelector);
538 continue; // it must not be
541 const BOPCol_ListOfInteger& aLI=aSelector.Indices();
543 for (; aIt.More(); aIt.Next()) {
545 if (aMIP.Contains(aIP1)) {
549 } //for (; aIt.More(); aIt.Next()) {
550 }//for(; aIt1.More(); aIt1.Next()) {
552 aNbIP1=aMIP1.Extent();
554 break; // from while(1)
557 aIt1.Initialize(aMIP);
558 for(; aIt1.More(); aIt1.Next()) {
564 aIt1.Initialize(aMIP1);
565 for(; aIt1.More(); aIt1.Next()) {
572 aNbIP=aMIPC.Extent();
577 aIt1.Initialize(aMIPC);
578 for(j=0; aIt1.More(); aIt1.Next(), ++j) {
580 const TopoDS_Shape& aVP=aMIS.Find(aIP);
585 aMVProcessed.Add(aVP);
587 aMVLV.Add(aVF, aLVSD);
588 }// for (i=1; i<=aNbV; ++i) {
592 for (i=1; i<=aNbV; ++i) {
593 const TopoDS_Shape& aV=aMVLV.FindKey(i);
594 BOPCol_ListOfShape& aLVSD=aMVLV.ChangeFromIndex(i);
595 aNbVSD=aLVSD.Extent();
597 BOPTools_AlgoTools::MakeVertex(aLVSD, aVnew);
598 myImages.Add(aVnew, aLVSD);
600 myImages.Add(aV, aLVSD);
605 //=======================================================================
606 //function : FillShrunkData
608 //=======================================================================
609 void BOPAlgo_PaveFiller::FillShrunkData(Handle(BOPDS_PaveBlock)& thePB)
611 Standard_Integer nE, nV1, nV2, iErr;
612 Standard_Real aT1, aT2, aTS1, aTS2;
613 BOPInt_ShrunkRange aSR;
618 const BOPDS_Pave& aPave1=thePB->Pave1();
620 aT1=aPave1.Parameter();
621 const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1)));
623 const BOPDS_Pave& aPave2=thePB->Pave2();
625 aT2=aPave2.Parameter();
626 const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2)));
628 nE=thePB->OriginalEdge();
629 const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE)));
631 aSR.SetData(aE, aT1, aT2, aV1, aV2, myContext);
634 iErr=aSR.ErrorStatus();
641 aSR.ShrunkRange(aTS1, aTS2);
642 const Bnd_Box& aBox=aSR.BndBox();
644 thePB->SetShrunkData(aTS1, aTS2, aBox);
646 //=======================================================================
647 //function : ForceInterfVE
649 //=======================================================================
650 void BOPAlgo_PaveFiller::ForceInterfVE(const Standard_Integer nV,
651 Handle(BOPDS_PaveBlock)& aPB,
652 BOPDS_MapOfPaveBlock& aMPBToUpdate)
654 Standard_Integer aNbPnt, nE;
657 nE = aPB->OriginalEdge();
659 const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
660 if (aSIE.HasSubShape(nV)) {
664 if (myDS->HasInterf(nV, nE)) {
668 if (myDS->HasInterfShapeSubShapes(nV, nE)) {
672 if (aPB->Pave1().Index() == nV || aPB->Pave2().Index() == nV) {
676 const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nV);
677 const TopoDS_Edge& aE = *(TopoDS_Edge*) &myDS->Shape(nE);
678 aP=BRep_Tool::Pnt(aV);
680 GeomAPI_ProjectPointOnCurve& aProjector=myContext->ProjPC(aE);
681 aProjector.Perform(aP);
683 aNbPnt = aProjector.NbPoints();
685 Standard_Real aT, aDist;
690 aDist=aProjector.LowerDistance();
691 aT=aProjector.LowerDistanceParameter();
693 BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
695 BOPDS_InterfVE& aVE=aVEs(i);
696 aVE.SetIndices(nV, nE);
697 aVE.SetParameter(aT);
699 myDS->AddInterf(nV, nE);
701 aBB.UpdateVertex(aV, aDist);
702 BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(nV);
703 Bnd_Box& aBox=aSIDS.ChangeBox();
704 BRepBndLib::Add(aV, aBox);
707 aPave.SetParameter(aT);
708 aPB->AppendExtPave(aPave);
710 aMPBToUpdate.Add(aPB);
719 aBBx.MakeCompound(aCx);
720 aItMVCPB.Initialize(theMVCPB);
721 for (; aItMVCPB.More(); aItMVCPB.Next()) {
722 const TopoDS_Shape& aS=aItMVCPB.Key();
725 BRepTools::Write(aCx, "cx");