0025748: Parallel version of progress indicator
[occt.git] / src / BOPAlgo / BOPAlgo_PaveFiller_2.cxx
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
6 //
7 // This file is part of Open CASCADE Technology software library.
8 //
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.
14 //
15 // Alternatively, this file may be used under the terms of Open CASCADE
16 // commercial license or contractual agreement.
17
18
19 #include <BOPAlgo_PaveFiller.hxx>
20 #include <BOPAlgo_Alerts.hxx>
21 #include <BOPAlgo_Tools.hxx>
22 #include <BOPDS_DS.hxx>
23 #include <BOPDS_Interf.hxx>
24 #include <BOPDS_Iterator.hxx>
25 #include <BOPDS_Pair.hxx>
26 #include <BOPDS_PaveBlock.hxx>
27 #include <BOPDS_VectorOfInterfVE.hxx>
28 #include <BOPTools_AlgoTools.hxx>
29 #include <BOPTools_Parallel.hxx>
30 #include <BRep_Builder.hxx>
31 #include <BRep_Tool.hxx>
32 #include <gp_Pnt.hxx>
33 #include <IntTools_Context.hxx>
34 #include <NCollection_Vector.hxx>
35 #include <Precision.hxx>
36 #include <TopoDS.hxx>
37 #include <TopoDS_Edge.hxx>
38 #include <TopoDS_Vertex.hxx>
39
40 //=======================================================================
41 //class    : BOPAlgo_VertexEdge
42 //purpose  : 
43 //=======================================================================
44 class BOPAlgo_VertexEdge : public BOPAlgo_Algo {
45
46  public:
47   DEFINE_STANDARD_ALLOC
48
49   BOPAlgo_VertexEdge() : 
50     BOPAlgo_Algo(),
51     myIV(-1), myIE(-1), myFlag(-1), myT(-1.), myTolVNew(-1.) {
52   };
53   //
54   virtual ~BOPAlgo_VertexEdge(){
55   };
56   //
57   void SetIndices(const Standard_Integer nV,
58                   const Standard_Integer nE) {
59     myIV=nV;
60     myIE=nE;
61   }
62   //
63   void Indices(Standard_Integer& nV,
64                Standard_Integer& nE) const {
65     nV=myIV;
66     nE=myIE;
67   }
68   //
69   void SetVertex(const TopoDS_Vertex& aV) {
70     myV=aV;
71   }
72   //
73   void SetEdge(const TopoDS_Edge& aE) {
74     myE=aE;
75   }
76   //
77   const TopoDS_Vertex& Vertex() const {
78     return myV;
79   }
80   //
81   const TopoDS_Edge& Edge() const {
82     return myE;
83   }
84   //
85   Standard_Integer Flag()const {
86     return myFlag;
87   }
88   //
89   Standard_Real Parameter()const {
90     return myT;
91   }
92   //
93   Standard_Real VertexNewTolerance()const {
94     return myTolVNew;
95   }
96   //
97   void SetContext(const Handle(IntTools_Context)& aContext) {
98     myContext=aContext;
99   }
100   //
101   const Handle(IntTools_Context)& Context()const {
102     return myContext;
103   }
104   //
105   void SetPaveBlock(const Handle(BOPDS_PaveBlock)& thePB) {
106     myPB = thePB;
107   }
108   //
109   const Handle(BOPDS_PaveBlock)& PaveBlock() const {
110     return myPB;
111   }
112   //
113   virtual void Perform() {
114     BOPAlgo_Algo::UserBreak();
115     try
116     {
117       OCC_CATCH_SIGNALS
118
119       myFlag=myContext->ComputeVE (myV, myE, myT, myTolVNew, myFuzzyValue);
120     }
121     catch (Standard_Failure const&)
122     {
123       AddError(new BOPAlgo_AlertIntersectionFailed);
124     }
125   };
126   //
127  protected:
128   Standard_Integer myIV;
129   Standard_Integer myIE;
130   Standard_Integer myFlag;
131   Standard_Real myT;
132   Standard_Real myTolVNew;
133   TopoDS_Vertex myV;
134   TopoDS_Edge myE;
135   Handle(IntTools_Context) myContext;
136   Handle(BOPDS_PaveBlock) myPB;
137 };
138 //=======================================================================
139 typedef NCollection_Vector<BOPAlgo_VertexEdge> BOPAlgo_VectorOfVertexEdge;
140
141 //=======================================================================
142 // function: PerformVE
143 // purpose: 
144 //=======================================================================
145 void BOPAlgo_PaveFiller::PerformVE()
146 {
147   FillShrunkData(TopAbs_VERTEX, TopAbs_EDGE);
148   //
149   myIterator->Initialize(TopAbs_VERTEX, TopAbs_EDGE);
150   Standard_Integer iSize = myIterator->ExpectedLength();
151   if (!iSize) {
152     return; 
153   }
154   //
155   // Prepare pairs for intersection
156   BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMVEPairs;
157   for (; myIterator->More(); myIterator->Next()) {
158     Standard_Integer nV, nE;
159     myIterator->Value(nV, nE);
160     //
161     const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
162     if (aSIE.HasSubShape(nV)) {
163       continue;
164     }
165     //
166     if (aSIE.HasFlag()){
167       continue;
168     }
169     //
170     if (myDS->HasInterf(nV, nE)) {
171       continue;
172     }
173     //
174     if (myDS->HasInterfShapeSubShapes(nV, nE)) {
175       continue;
176     }
177     //
178     const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks(nE);
179     if (aLPB.IsEmpty()) {
180       continue;
181     }
182     //
183     const Handle(BOPDS_PaveBlock)& aPB = aLPB.First();
184     if (!aPB->IsSplittable()) {
185       // this is a micro edge, ignore it
186       continue;
187     }
188     //
189     TColStd_ListOfInteger* pLV = aMVEPairs.ChangeSeek(aPB);
190     if (!pLV)
191       pLV = &aMVEPairs(aMVEPairs.Add(aPB, TColStd_ListOfInteger()));
192     pLV->Append(nV);
193   }
194   //
195   IntersectVE(aMVEPairs);
196 }
197
198 //=======================================================================
199 // function: IntersectVE
200 // purpose: 
201 //=======================================================================
202 void BOPAlgo_PaveFiller::IntersectVE
203   (const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& theVEPairs,
204    const Standard_Boolean theAddInterfs)
205 {
206   Standard_Integer i, aNbVE = theVEPairs.Extent();
207   if (!aNbVE) {
208     return;
209   }
210   //
211   BOPDS_VectorOfInterfVE& aVEs = myDS->InterfVE();
212   if (theAddInterfs) {
213     aVEs.SetIncrement(aNbVE);
214   }
215   //
216   // Prepare for intersection.
217   BOPAlgo_VectorOfVertexEdge aVVE;
218   // Map to collect all SD connections to add interferences
219   // for all vertices having the same SD vertex.
220   // It will also be used as a Fence map to avoid repeated
221   // intersection of the same SD vertex with edge
222   NCollection_DataMap<BOPDS_Pair, TColStd_ListOfInteger, BOPDS_PairMapHasher> aDMVSD;
223   //
224   for (i = 1; i <= aNbVE; ++i) {
225     const Handle(BOPDS_PaveBlock)& aPB = theVEPairs.FindKey(i);
226     Standard_Integer nE = aPB->OriginalEdge();
227     //
228     TColStd_MapOfInteger aMVPB;
229     const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks (nE);
230     for (BOPDS_ListOfPaveBlock::Iterator itPB (aLPB); itPB.More(); itPB.Next())
231     {
232       aMVPB.Add (itPB.Value()->Pave1().Index());
233       aMVPB.Add (itPB.Value()->Pave2().Index());
234     }
235
236     const TColStd_ListOfInteger& aLV = theVEPairs(i);
237     TColStd_ListIteratorOfListOfInteger aItLV(aLV);
238     for (; aItLV.More(); aItLV.Next()) {
239       Standard_Integer nV = aItLV.Value();
240       //
241       Standard_Integer nVSD = nV;
242       myDS->HasShapeSD(nV, nVSD);
243       //
244       if (aMVPB.Contains (nVSD))
245         continue;
246
247       BOPDS_Pair aPair(nVSD, nE);
248       TColStd_ListOfInteger* pLI = aDMVSD.ChangeSeek(aPair);
249       if (pLI) {
250         // Already added
251         pLI->Append(nV);
252         continue;
253       }
254       // New pair
255       pLI = aDMVSD.Bound(aPair, TColStd_ListOfInteger());
256       pLI->Append(nV);
257       //
258       const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nVSD));
259       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
260       //
261       BOPAlgo_VertexEdge& aVESolver = aVVE.Appended();
262       aVESolver.SetIndices(nVSD, nE);
263       aVESolver.SetVertex(aV);
264       aVESolver.SetEdge(aE);
265       aVESolver.SetPaveBlock(aPB);
266       aVESolver.SetFuzzyValue(myFuzzyValue);
267       aVESolver.SetProgressIndicator(*myProgressScope);
268     }
269   }
270   //
271   // Perform intersection
272   //=============================================================
273   BOPTools_Parallel::Perform (myRunParallel, aVVE, myContext);
274   //=============================================================
275   //
276   // Keep the modified edges for further update
277   TColStd_MapOfInteger aMEdges;
278   //
279   // Analyze intersections
280   aNbVE = aVVE.Length();
281   for (i = 0; i < aNbVE; ++i) {
282     const BOPAlgo_VertexEdge& aVESolver = aVVE(i);
283     if (aVESolver.Flag() != 0) {
284       if (aVESolver.HasErrors())
285       {
286         // Warn about failed intersection of sub-shapes
287         AddIntersectionFailedWarning(aVESolver.Vertex(), aVESolver.Edge());
288       }
289       continue;
290     }
291     //
292     Standard_Integer nV, nE;
293     aVESolver.Indices(nV, nE);
294     // Parameter of vertex on edge
295     Standard_Real aT = aVESolver.Parameter();
296     // 1. Update vertex V/E if necessary
297     Standard_Real aTolVNew = aVESolver.VertexNewTolerance();
298     Standard_Integer nVx = UpdateVertex(nV, aTolVNew);
299     // 2. Create new pave and add it as extra pave to pave block
300     //    for further splitting of the edge
301     const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks (nE);
302     // Find the appropriate one
303     Handle(BOPDS_PaveBlock) aPB;
304     BOPDS_ListOfPaveBlock::Iterator itPB (aLPB);
305     for (; itPB.More(); itPB.Next())
306     {
307       aPB = itPB.Value();
308       Standard_Real aT1, aT2;
309       aPB->Range (aT1, aT2);
310       if (aT > aT1 && aT < aT2)
311         break;
312     }
313     if (!itPB.More())
314       continue;
315
316     BOPDS_Pave aPave;
317     aPave.SetIndex(nVx);
318     aPave.SetParameter(aT);
319     aPB->AppendExtPave(aPave);
320     aMEdges.Add(nE);
321     //
322     if (theAddInterfs) {
323       // Add interferences into DS
324       BOPDS_Pair aPair(nV, nE);
325       const TColStd_ListOfInteger& aLI = aDMVSD.Find(aPair);
326       TColStd_ListIteratorOfListOfInteger aItLI(aLI);
327       for (; aItLI.More(); aItLI.Next()) {
328         const Standard_Integer nVOld = aItLI.Value();
329         // 3. Create interference V/E
330         BOPDS_InterfVE& aVE = aVEs.Appended();
331         aVE.SetIndices(nVOld, nE);
332         aVE.SetParameter(aT);
333         // 2. Add a pair in the whole table of interferences
334         myDS->AddInterf(nVOld, nE);
335         // 4. Set index of new vertex in the interference
336         if (myDS->IsNewShape(nVx)) {
337           aVE.SetIndexNew(nVx);
338         }
339       }
340     }
341   }
342   //
343   // Split pave blocks of the intersected edges with the extra paves.
344   // At the same time compute shrunk data for the new pave blocks
345   // and in case there is no valid range for the pave block,
346   // the vertices of this pave block should be unified.
347   SplitPaveBlocks(aMEdges, theAddInterfs);
348 }
349
350 //=======================================================================
351 // function: MakeNewCommonBlock
352 // purpose: Make new Common Block from the given list of Pave Blocks
353 //=======================================================================
354 static
355   void MakeNewCommonBlock(const BOPDS_ListOfPaveBlock& theLPB,
356                           const TColStd_ListOfInteger& theLFaces,
357                           BOPDS_PDS& theDS)
358 {
359   // Make Common Block from the pave blocks in the list
360   Handle(BOPDS_CommonBlock) aCBNew = new BOPDS_CommonBlock;
361   aCBNew->SetPaveBlocks(theLPB);
362   aCBNew->SetFaces(theLFaces);
363   //
364   BOPDS_ListIteratorOfListOfPaveBlock aItLPB(theLPB);
365   for (; aItLPB.More(); aItLPB.Next()) {
366     theDS->SetCommonBlock(aItLPB.ChangeValue(), aCBNew);
367   }
368 }
369
370 //=======================================================================
371 // function: SplitPaveBlocks
372 // purpose: 
373 //=======================================================================
374 void BOPAlgo_PaveFiller::SplitPaveBlocks(const TColStd_MapOfInteger& theMEdges,
375                                          const Standard_Boolean theAddInterfs)
376 {
377   // Fence map to avoid unification of the same vertices twice
378   BOPDS_MapOfPair aMPairs;
379   // Map to treat the Common Blocks
380   NCollection_IndexedDataMap<Handle(BOPDS_CommonBlock),
381                              BOPDS_ListOfPaveBlock,
382                              TColStd_MapTransientHasher> aMCBNewPB;
383   //
384   // Map of vertices to init the pave blocks for them
385   TColStd_MapOfInteger aMVerticesToInitPB;
386
387   TColStd_MapIteratorOfMapOfInteger aItM(theMEdges);
388   for (; aItM.More(); aItM.Next()) {
389     Standard_Integer nE = aItM.Value();
390     BOPDS_ListOfPaveBlock& aLPB = myDS->ChangePaveBlocks(nE);
391     //
392     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
393     for (; aItLPB.More();) {
394       Handle(BOPDS_PaveBlock)& aPB = aItLPB.ChangeValue();
395       //
396       if (!aPB->IsToUpdate()) {
397         aItLPB.Next();
398         continue;
399       }
400       //
401       const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(aPB);
402       //
403       // Compute new pave blocks
404       BOPDS_ListOfPaveBlock aLPBN;
405       aPB->Update(aLPBN);
406       //
407       // Make sure that each new pave block has a valid range,
408       // otherwise unify the vertices of the pave block
409       BOPDS_ListIteratorOfListOfPaveBlock aItLPBN(aLPBN);
410       for (; aItLPBN.More(); aItLPBN.Next()) {
411         Handle(BOPDS_PaveBlock)& aPBN = aItLPBN.ChangeValue();
412         myDS->UpdatePaveBlockWithSDVertices(aPBN);
413         FillShrunkData(aPBN);
414         //
415         Standard_Boolean bHasValidRange = aPBN->HasShrunkData();
416         // Take into account that the edge could have really small valid range,
417         // so that the Pave Block cannot be further split. In this case, check if
418         // the vertices of the Pave Block do not interfere. And if they are, unify them.
419         Standard_Boolean bCheckDist = (bHasValidRange && !aPBN->IsSplittable());
420         if (!bHasValidRange || bCheckDist)
421         {
422           Standard_Integer nV1, nV2;
423           aPBN->Indices(nV1, nV2);
424           if (nV1 == nV2)
425             // Same vertices -> no valid range, no need to unify vertices
426             continue;
427
428           // Decide whether to unify vertices or not
429           if (bCheckDist)
430           {
431             const TopoDS_Vertex& aV1 = TopoDS::Vertex(myDS->Shape(nV1));
432             const TopoDS_Vertex& aV2 = TopoDS::Vertex(myDS->Shape(nV2));
433             if (BOPTools_AlgoTools::ComputeVV(aV1, aV2, myFuzzyValue) == 0)
434               // vertices are interfering -> no valid range, unify vertices
435               bHasValidRange = Standard_False;
436           }
437
438           if (!bHasValidRange)
439           {
440             BOPDS_Pair aPair;
441             aPair.SetIndices(nV1, nV2);
442             if (aMPairs.Add(aPair))
443             {
444               TColStd_ListOfInteger aLV;
445               aLV.Append(nV1);
446               aLV.Append(nV2);
447               MakeSDVertices(aLV, theAddInterfs);
448
449               // Save vertices to init pave blocks
450               aMVerticesToInitPB.Add(nV1);
451               aMVerticesToInitPB.Add(nV2);
452             }
453             continue;
454           }
455         }
456         //
457         // Update the list with new pave block
458         aLPB.Append(aPBN);
459         // Treat the common block
460         if (!aCB.IsNull()) {
461           // Store the new pave block to make new common block
462           BOPDS_ListOfPaveBlock* pLPBCB = aMCBNewPB.ChangeSeek(aCB);
463           if (!pLPBCB) {
464             pLPBCB = &aMCBNewPB(aMCBNewPB.Add(aCB, BOPDS_ListOfPaveBlock()));
465           }
466           pLPBCB->Append(aPBN);
467         }
468       }
469       // Remove old pave block
470       aLPB.Remove(aItLPB);
471     }
472   }
473   //
474   // Make Common Blocks
475   Standard_Integer i, aNbCB = aMCBNewPB.Extent();
476   for (i = 1; i <= aNbCB; ++i) {
477     const Handle(BOPDS_CommonBlock)& aCB = aMCBNewPB.FindKey(i);
478     const BOPDS_ListOfPaveBlock& aLPBN = aMCBNewPB(i);
479     //
480     // For each group of pave blocks with the same vertices make new common block
481     NCollection_IndexedDataMap<BOPDS_Pair, BOPDS_ListOfPaveBlock, BOPDS_PairMapHasher> aMInds;
482     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPBN);
483     for (; aItLPB.More(); aItLPB.Next()) {
484       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
485       //
486       BOPDS_Pair aPair;
487       aPair.SetIndices(aPB->Pave1().Index(), aPB->Pave2().Index());
488       //
489       BOPDS_ListOfPaveBlock* pLPBx = aMInds.ChangeSeek(aPair);
490       if (!pLPBx) {
491         pLPBx = &aMInds(aMInds.Add(aPair, BOPDS_ListOfPaveBlock()));
492       }
493       pLPBx->Append(aPB);
494     }
495     //
496     Standard_Integer nV1, nV2;
497     aCB->PaveBlock1()->Indices(nV1, nV2);
498     Standard_Boolean bIsClosed = (nV1 == nV2);
499     //
500     Standard_Integer j, aNbPairs = aMInds.Extent();
501     for (j = 1; j <= aNbPairs; ++j) {
502       BOPDS_ListOfPaveBlock& aLPB = aMInds(j);
503       //
504       if (!bIsClosed) {
505         // Make Common Block from the pave blocks in the list
506         MakeNewCommonBlock(aLPB, aCB->Faces(), myDS);
507         continue;
508       }
509       //
510       // Find coinciding pave blocks
511       while (aLPB.Extent()) {
512         // Pave blocks forming the common block
513         BOPDS_ListOfPaveBlock aLPBCB;
514         // Point in the middle of the first pave block in the common block
515         gp_Pnt aPMFirst(0., 0., 0.);
516         // Tolerance of the first edge in the common block
517         Standard_Real aTolEFirst = 0.;
518         //
519         aItLPB.Initialize(aLPB);
520         for (; aItLPB.More();) {
521           const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
522           if (aLPBCB.IsEmpty()) {
523             aLPBCB.Append(aPB);
524             const TopoDS_Edge& aEFirst = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
525             aTolEFirst = BRep_Tool::MaxTolerance(aEFirst, TopAbs_VERTEX);
526             //
527             Standard_Real aTmFirst = (aPB->Pave1().Parameter() + aPB->Pave2().Parameter()) / 2.;
528             BOPTools_AlgoTools::PointOnEdge(aEFirst, aTmFirst, aPMFirst);
529             //
530             aLPB.Remove(aItLPB);
531             continue;
532           }
533           //
534           // Check pave blocks for coincidence
535           const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
536           Standard_Real aTolE = BRep_Tool::MaxTolerance(aE, TopAbs_VERTEX);
537           //
538           Standard_Real aTOut, aDist;
539           Standard_Integer iErr =
540             myContext->ComputePE(aPMFirst, aTolEFirst + aTolE + myFuzzyValue, aE, aTOut, aDist);
541           if (!iErr && ((aTOut > aPB->Pave1().Parameter()) && (aTOut < aPB->Pave2().Parameter()))) {
542             aLPBCB.Append(aPB);
543             aLPB.Remove(aItLPB);
544             continue;
545           }
546           aItLPB.Next();
547         }
548         //
549         // Make Common Block from the pave blocks in the list
550         MakeNewCommonBlock(aLPBCB, aCB->Faces(), myDS);
551       }
552     }
553   }
554
555   // Init pave blocks for vertices which have acquired SD vertex
556   aItM.Initialize(aMVerticesToInitPB);
557   for (; aItM.More(); aItM.Next())
558     myDS->InitPaveBlocksForVertex(aItM.Value());
559 }
560
561 //=======================================================================
562 // function: AddIntersectionFailedWarning
563 // purpose: 
564 //=======================================================================
565 void BOPAlgo_PaveFiller::AddIntersectionFailedWarning(const TopoDS_Shape& theS1,
566                                                       const TopoDS_Shape& theS2)
567 {
568   // Create the warn shape
569   TopoDS_Compound aWC;
570   BRep_Builder().MakeCompound(aWC);
571   BRep_Builder().Add(aWC, theS1);
572   BRep_Builder().Add(aWC, theS2);
573   // Add the warning
574   AddWarning(new BOPAlgo_AlertIntersectionOfPairOfShapesFailed(aWC));
575 }