0029400: Fuse of two edges creates self-interfered shape
[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)
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
140   <BOPAlgo_VertexEdge> BOPAlgo_VectorOfVertexEdge; 
141 //
142 typedef BOPTools_ContextFunctor 
143   <BOPAlgo_VertexEdge,
144   BOPAlgo_VectorOfVertexEdge,
145   Handle(IntTools_Context), 
146   IntTools_Context> BOPAlgo_VertexEdgeFunctor;
147 //
148 typedef BOPTools_ContextCnt 
149   <BOPAlgo_VertexEdgeFunctor,
150   BOPAlgo_VectorOfVertexEdge,
151   Handle(IntTools_Context)> BOPAlgo_VertexEdgeCnt;
152 //
153 //=======================================================================
154 // function: PerformVE
155 // purpose: 
156 //=======================================================================
157 void BOPAlgo_PaveFiller::PerformVE()
158 {
159   FillShrunkData(TopAbs_VERTEX, TopAbs_EDGE);
160   //
161   myIterator->Initialize(TopAbs_VERTEX, TopAbs_EDGE);
162   Standard_Integer iSize = myIterator->ExpectedLength();
163   if (!iSize) {
164     return; 
165   }
166   //
167   // Prepare pairs for intersection
168   BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMVEPairs;
169   for (; myIterator->More(); myIterator->Next()) {
170     Standard_Integer nV, nE;
171     myIterator->Value(nV, nE);
172     //
173     const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
174     if (aSIE.HasSubShape(nV)) {
175       continue;
176     }
177     //
178     if (aSIE.HasFlag()){
179       continue;
180     }
181     //
182     if (myDS->HasInterfShapeSubShapes(nV, nE)) {
183       continue;
184     }
185     //
186     const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks(nE);
187     if (aLPB.IsEmpty()) {
188       continue;
189     }
190     //
191     const Handle(BOPDS_PaveBlock)& aPB = aLPB.First();
192     if (!aPB->IsSplittable()) {
193       // this is a micro edge, ignore it
194       continue;
195     }
196     //
197     TColStd_ListOfInteger* pLV = aMVEPairs.ChangeSeek(aPB);
198     if (!pLV)
199       pLV = &aMVEPairs(aMVEPairs.Add(aPB, TColStd_ListOfInteger()));
200     pLV->Append(nV);
201   }
202   //
203   IntersectVE(aMVEPairs);
204 }
205
206 //=======================================================================
207 // function: IntersectVE
208 // purpose: 
209 //=======================================================================
210 void BOPAlgo_PaveFiller::IntersectVE
211   (const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& theVEPairs,
212    const Standard_Boolean theAddInterfs)
213 {
214   Standard_Integer i, aNbVE = theVEPairs.Extent();
215   if (!aNbVE) {
216     return;
217   }
218   //
219   BOPDS_VectorOfInterfVE& aVEs = myDS->InterfVE();
220   if (theAddInterfs) {
221     aVEs.SetIncrement(aNbVE);
222   }
223   //
224   // Prepare for intersection.
225   BOPAlgo_VectorOfVertexEdge aVVE;
226   // Map to collect all SD connections to add interferences
227   // for all vertices having the same SD vertex.
228   // It will also be used as a Fence map to avoid repeated
229   // intersection of the same SD vertex with edge
230   NCollection_DataMap<BOPDS_Pair, TColStd_ListOfInteger, BOPDS_PairMapHasher> aDMVSD;
231   //
232   for (i = 1; i <= aNbVE; ++i) {
233     const Handle(BOPDS_PaveBlock)& aPB = theVEPairs.FindKey(i);
234     Standard_Integer nE = aPB->OriginalEdge();
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       BOPDS_Pair aPair(nVSD, nE);
245       TColStd_ListOfInteger* pLI = aDMVSD.ChangeSeek(aPair);
246       if (pLI) {
247         // Already added
248         pLI->Append(nV);
249         continue;
250       }
251       // New pair
252       pLI = aDMVSD.Bound(aPair, TColStd_ListOfInteger());
253       pLI->Append(nV);
254       //
255       const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nVSD));
256       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
257       //
258       BOPAlgo_VertexEdge& aVESolver = aVVE.Appended();
259       aVESolver.SetIndices(nVSD, nE);
260       aVESolver.SetVertex(aV);
261       aVESolver.SetEdge(aE);
262       aVESolver.SetPaveBlock(aPB);
263       aVESolver.SetFuzzyValue(myFuzzyValue);
264       aVESolver.SetProgressIndicator(myProgressIndicator);
265     }
266   }
267   //
268   // Perform intersection
269   //=============================================================
270   BOPAlgo_VertexEdgeCnt::Perform(myRunParallel, aVVE, myContext);
271   //=============================================================
272   //
273   // Keep the modified edges for further update
274   TColStd_MapOfInteger aMEdges;
275   //
276   // Analyze intersections
277   aNbVE = aVVE.Length();
278   for (i = 0; i < aNbVE; ++i) {
279     const BOPAlgo_VertexEdge& aVESolver = aVVE(i);
280     if (aVESolver.Flag() != 0) {
281       if (aVESolver.HasErrors())
282       {
283         // Warn about failed intersection of sub-shapes
284         AddIntersectionFailedWarning(aVESolver.Vertex(), aVESolver.Edge());
285       }
286       continue;
287     }
288     //
289     Standard_Integer nV, nE;
290     aVESolver.Indices(nV, nE);
291     // Parameter of vertex on edge
292     Standard_Real aT = aVESolver.Parameter();
293     // 1. Update vertex V/E if necessary
294     Standard_Real aTolVNew = aVESolver.VertexNewTolerance();
295     Standard_Integer nVx = UpdateVertex(nV, aTolVNew);
296     // 2. Create new pave and add it as extra pave to pave block
297     //    for further splitting of the edge
298     const Handle(BOPDS_PaveBlock)& aPB = aVESolver.PaveBlock();
299     BOPDS_Pave aPave;
300     aPave.SetIndex(nVx);
301     aPave.SetParameter(aT);
302     aPB->AppendExtPave(aPave);
303     aMEdges.Add(nE);
304     //
305     if (theAddInterfs) {
306       // Add interferences into DS
307       BOPDS_Pair aPair(nV, nE);
308       const TColStd_ListOfInteger& aLI = aDMVSD.Find(aPair);
309       TColStd_ListIteratorOfListOfInteger aItLI(aLI);
310       for (; aItLI.More(); aItLI.Next()) {
311         const Standard_Integer nVOld = aItLI.Value();
312         // 3. Create interference V/E
313         BOPDS_InterfVE& aVE = aVEs.Appended();
314         aVE.SetIndices(nVOld, nE);
315         aVE.SetParameter(aT);
316         // 2. Add a pair in the whole table of interferences
317         myDS->AddInterf(nVOld, nE);
318         // 4. Set index of new vertex in the interference
319         if (myDS->IsNewShape(nVx)) {
320           aVE.SetIndexNew(nVx);
321         }
322       }
323     }
324   }
325   //
326   // Split pave blocks of the intersected edges with the extra paves.
327   // At the same time compute shrunk data for the new pave blocks
328   // and in case there is no valid range for the pave block,
329   // the vertices of this pave block should be unified.
330   SplitPaveBlocks(aMEdges, theAddInterfs);
331 }
332
333 //=======================================================================
334 // function: MakeNewCommonBlock
335 // purpose: Make new Common Block from the given list of Pave Blocks
336 //=======================================================================
337 static
338   void MakeNewCommonBlock(const BOPDS_ListOfPaveBlock& theLPB,
339                           const TColStd_ListOfInteger& theLFaces,
340                           BOPDS_PDS& theDS)
341 {
342   // Make Common Block from the pave blocks in the list
343   Handle(BOPDS_CommonBlock) aCBNew = new BOPDS_CommonBlock;
344   aCBNew->SetPaveBlocks(theLPB);
345   aCBNew->SetFaces(theLFaces);
346   //
347   BOPDS_ListIteratorOfListOfPaveBlock aItLPB(theLPB);
348   for (; aItLPB.More(); aItLPB.Next()) {
349     theDS->SetCommonBlock(aItLPB.ChangeValue(), aCBNew);
350   }
351 }
352
353 //=======================================================================
354 // function: SplitPaveBlocks
355 // purpose: 
356 //=======================================================================
357 void BOPAlgo_PaveFiller::SplitPaveBlocks(const TColStd_MapOfInteger& theMEdges,
358                                          const Standard_Boolean theAddInterfs)
359 {
360   // Fence map to avoid unification of the same vertices twice
361   BOPDS_MapOfPair aMPairs;
362   // Map to treat the Common Blocks
363   NCollection_IndexedDataMap<Handle(BOPDS_CommonBlock),
364                              BOPDS_ListOfPaveBlock,
365                              TColStd_MapTransientHasher> aMCBNewPB;
366   //
367   TColStd_MapIteratorOfMapOfInteger aItM(theMEdges);
368   for (; aItM.More(); aItM.Next()) {
369     Standard_Integer nE = aItM.Value();
370     BOPDS_ListOfPaveBlock& aLPB = myDS->ChangePaveBlocks(nE);
371     //
372     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
373     for (; aItLPB.More();) {
374       Handle(BOPDS_PaveBlock)& aPB = aItLPB.ChangeValue();
375       //
376       if (!aPB->IsToUpdate()) {
377         aItLPB.Next();
378         continue;
379       }
380       //
381       const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(aPB);
382       //
383       // Compute new pave blocks
384       BOPDS_ListOfPaveBlock aLPBN;
385       aPB->Update(aLPBN);
386       //
387       // Make sure that each new pave block has a valid range,
388       // otherwise unify the vertices of the pave block
389       BOPDS_ListIteratorOfListOfPaveBlock aItLPBN(aLPBN);
390       for (; aItLPBN.More(); aItLPBN.Next()) {
391         Handle(BOPDS_PaveBlock)& aPBN = aItLPBN.ChangeValue();
392         myDS->UpdatePaveBlockWithSDVertices(aPBN);
393         FillShrunkData(aPBN);
394         //
395         Standard_Boolean bHasValidRange = aPBN->HasShrunkData();
396         // Take into account that the edge could have really small valid range,
397         // so that the Pave Block cannot be further split. In this case, check if
398         // the vertices of the Pave Block do not interfere. And if they are, unify them.
399         Standard_Boolean bCheckDist = (bHasValidRange && !aPBN->IsSplittable());
400         if (!bHasValidRange || bCheckDist)
401         {
402           Standard_Integer nV1, nV2;
403           aPBN->Indices(nV1, nV2);
404           if (nV1 == nV2)
405             // Same vertices -> no valid range, no need to unify vertices
406             continue;
407
408           // Decide whether to unify vertices or not
409           if (bCheckDist)
410           {
411             const TopoDS_Vertex& aV1 = TopoDS::Vertex(myDS->Shape(nV1));
412             const TopoDS_Vertex& aV2 = TopoDS::Vertex(myDS->Shape(nV2));
413             if (BOPTools_AlgoTools::ComputeVV(aV1, aV2, myFuzzyValue) == 0)
414               // vertices are interfering -> no valid range, unify vertices
415               bHasValidRange = Standard_False;
416           }
417
418           if (!bHasValidRange)
419           {
420             BOPDS_Pair aPair;
421             aPair.SetIndices(nV1, nV2);
422             if (aMPairs.Add(aPair))
423             {
424               TColStd_ListOfInteger aLV;
425               aLV.Append(nV1);
426               aLV.Append(nV2);
427               MakeSDVertices(aLV, theAddInterfs);
428             }
429             continue;
430           }
431         }
432         //
433         // Update the list with new pave block
434         aLPB.Append(aPBN);
435         // Treat the common block
436         if (!aCB.IsNull()) {
437           // Store the new pave block to make new common block
438           BOPDS_ListOfPaveBlock* pLPBCB = aMCBNewPB.ChangeSeek(aCB);
439           if (!pLPBCB) {
440             pLPBCB = &aMCBNewPB(aMCBNewPB.Add(aCB, BOPDS_ListOfPaveBlock()));
441           }
442           pLPBCB->Append(aPBN);
443         }
444       }
445       // Remove old pave block
446       aLPB.Remove(aItLPB);
447     }
448   }
449   //
450   // Make Common Blocks
451   Standard_Integer i, aNbCB = aMCBNewPB.Extent();
452   for (i = 1; i <= aNbCB; ++i) {
453     const Handle(BOPDS_CommonBlock)& aCB = aMCBNewPB.FindKey(i);
454     const BOPDS_ListOfPaveBlock& aLPBN = aMCBNewPB(i);
455     //
456     // For each group of pave blocks with the same vertices make new common block
457     NCollection_IndexedDataMap<BOPDS_Pair, BOPDS_ListOfPaveBlock, BOPDS_PairMapHasher> aMInds;
458     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPBN);
459     for (; aItLPB.More(); aItLPB.Next()) {
460       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
461       //
462       BOPDS_Pair aPair;
463       aPair.SetIndices(aPB->Pave1().Index(), aPB->Pave2().Index());
464       //
465       BOPDS_ListOfPaveBlock* pLPBx = aMInds.ChangeSeek(aPair);
466       if (!pLPBx) {
467         pLPBx = &aMInds(aMInds.Add(aPair, BOPDS_ListOfPaveBlock()));
468       }
469       pLPBx->Append(aPB);
470     }
471     //
472     Standard_Integer nV1, nV2;
473     aCB->PaveBlock1()->Indices(nV1, nV2);
474     Standard_Boolean bIsClosed = (nV1 == nV2);
475     //
476     Standard_Integer j, aNbPairs = aMInds.Extent();
477     for (j = 1; j <= aNbPairs; ++j) {
478       BOPDS_ListOfPaveBlock& aLPB = aMInds(j);
479       //
480       if (!bIsClosed) {
481         // Make Common Block from the pave blocks in the list
482         MakeNewCommonBlock(aLPB, aCB->Faces(), myDS);
483         continue;
484       }
485       //
486       // Find coinciding pave blocks
487       while (aLPB.Extent()) {
488         // Pave blocks forming the common block
489         BOPDS_ListOfPaveBlock aLPBCB;
490         // Point in the middle of the first pave block in the common block
491         gp_Pnt aPMFirst(0., 0., 0.);
492         // Tolerance of the first edge in the common block
493         Standard_Real aTolEFirst = 0.;
494         //
495         aItLPB.Initialize(aLPB);
496         for (; aItLPB.More();) {
497           const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
498           if (aLPBCB.IsEmpty()) {
499             aLPBCB.Append(aPB);
500             const TopoDS_Edge& aEFirst = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
501             aTolEFirst = BRep_Tool::MaxTolerance(aEFirst, TopAbs_VERTEX);
502             //
503             Standard_Real aTmFirst = (aPB->Pave1().Parameter() + aPB->Pave2().Parameter()) / 2.;
504             BOPTools_AlgoTools::PointOnEdge(aEFirst, aTmFirst, aPMFirst);
505             //
506             aLPB.Remove(aItLPB);
507             continue;
508           }
509           //
510           // Check pave blocks for coincidence
511           const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
512           Standard_Real aTolE = BRep_Tool::MaxTolerance(aE, TopAbs_VERTEX);
513           //
514           Standard_Real aTOut, aDist;
515           Standard_Integer iErr =
516             myContext->ComputePE(aPMFirst, aTolEFirst + aTolE + myFuzzyValue, aE, aTOut, aDist);
517           if (!iErr && ((aTOut > aPB->Pave1().Parameter()) && (aTOut < aPB->Pave2().Parameter()))) {
518             aLPBCB.Append(aPB);
519             aLPB.Remove(aItLPB);
520             continue;
521           }
522           aItLPB.Next();
523         }
524         //
525         // Make Common Block from the pave blocks in the list
526         MakeNewCommonBlock(aLPBCB, aCB->Faces(), myDS);
527       }
528     }
529   }
530 }
531
532 //=======================================================================
533 // function: AddIntersectionFailedWarning
534 // purpose: 
535 //=======================================================================
536 void BOPAlgo_PaveFiller::AddIntersectionFailedWarning(const TopoDS_Shape& theS1,
537                                                       const TopoDS_Shape& theS2)
538 {
539   // Create the warn shape
540   TopoDS_Compound aWC;
541   BRep_Builder().MakeCompound(aWC);
542   BRep_Builder().Add(aWC, theS1);
543   BRep_Builder().Add(aWC, theS2);
544   // Add the warning
545   AddWarning(new BOPAlgo_AlertIntersectionOfPairOfShapesFailed(aWC));
546 }