0029400: Fuse of two edges creates self-interfered shape
[occt.git] / src / BOPAlgo / BOPAlgo_PaveFiller_2.cxx
CommitLineData
4e57c75e 1// Created by: Peter KURNEV
973c2be1 2// Copyright (c) 2010-2014 OPEN CASCADE SAS
4e57c75e 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//
973c2be1 7// This file is part of Open CASCADE Technology software library.
4e57c75e 8//
d5f74e42 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
973c2be1 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.
4e57c75e 14//
973c2be1 15// Alternatively, this file may be used under the terms of Open CASCADE
16// commercial license or contractual agreement.
4e57c75e 17
4e57c75e 18
42cf5bc1 19#include <BOPAlgo_PaveFiller.hxx>
ad8b073e 20#include <BOPAlgo_Alerts.hxx>
8ae442a8 21#include <BOPAlgo_Tools.hxx>
42cf5bc1 22#include <BOPDS_DS.hxx>
4e57c75e 23#include <BOPDS_Interf.hxx>
42cf5bc1 24#include <BOPDS_Iterator.hxx>
25dfc507 25#include <BOPDS_Pair.hxx>
42cf5bc1 26#include <BOPDS_PaveBlock.hxx>
27#include <BOPDS_VectorOfInterfVE.hxx>
3510db62 28#include <BOPTools_AlgoTools.hxx>
1155d05a 29#include <BOPTools_Parallel.hxx>
ad8b073e 30#include <BRep_Builder.hxx>
42cf5bc1 31#include <BRep_Tool.hxx>
42cf5bc1 32#include <gp_Pnt.hxx>
33#include <IntTools_Context.hxx>
1155d05a 34#include <NCollection_Vector.hxx>
8ae442a8 35#include <Precision.hxx>
36#include <TopoDS.hxx>
42cf5bc1 37#include <TopoDS_Edge.hxx>
42cf5bc1 38#include <TopoDS_Vertex.hxx>
4e57c75e 39
505abfb8 40//=======================================================================
8ae442a8 41//class : BOPAlgo_VertexEdge
505abfb8 42//purpose :
43//=======================================================================
36f4947b 44class BOPAlgo_VertexEdge : public BOPAlgo_Algo {
45
505abfb8 46 public:
36f4947b 47 DEFINE_STANDARD_ALLOC
48
49 BOPAlgo_VertexEdge() :
50 BOPAlgo_Algo(),
0d0481c7 51 myIV(-1), myIE(-1), myFlag(-1), myT(-1.), myTolVNew(-1.) {
505abfb8 52 };
53 //
36f4947b 54 virtual ~BOPAlgo_VertexEdge(){
505abfb8 55 };
56 //
57 void SetIndices(const Standard_Integer nV,
0d0481c7 58 const Standard_Integer nE) {
505abfb8 59 myIV=nV;
60 myIE=nE;
505abfb8 61 }
62 //
63 void Indices(Standard_Integer& nV,
0d0481c7 64 Standard_Integer& nE) const {
505abfb8 65 nV=myIV;
66 nE=myIE;
505abfb8 67 }
68 //
69 void SetVertex(const TopoDS_Vertex& aV) {
70 myV=aV;
71 }
72 //
505abfb8 73 void SetEdge(const TopoDS_Edge& aE) {
74 myE=aE;
75 }
76 //
3510db62 77 const TopoDS_Vertex& Vertex() const {
78 return myV;
79 }
80 //
81 const TopoDS_Edge& Edge() const {
505abfb8 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 //
3510db62 93 Standard_Real VertexNewTolerance()const {
94 return myTolVNew;
95 }
96 //
1e143abb 97 void SetContext(const Handle(IntTools_Context)& aContext) {
505abfb8 98 myContext=aContext;
99 }
100 //
1e143abb 101 const Handle(IntTools_Context)& Context()const {
505abfb8 102 return myContext;
103 }
104 //
8ae442a8 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 //
36f4947b 113 virtual void Perform() {
114 BOPAlgo_Algo::UserBreak();
ad8b073e 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 }
505abfb8 125 };
126 //
127 protected:
128 Standard_Integer myIV;
129 Standard_Integer myIE;
505abfb8 130 Standard_Integer myFlag;
131 Standard_Real myT;
3510db62 132 Standard_Real myTolVNew;
505abfb8 133 TopoDS_Vertex myV;
134 TopoDS_Edge myE;
1e143abb 135 Handle(IntTools_Context) myContext;
8ae442a8 136 Handle(BOPDS_PaveBlock) myPB;
505abfb8 137};
138//=======================================================================
1155d05a 139typedef NCollection_Vector
505abfb8 140 <BOPAlgo_VertexEdge> BOPAlgo_VectorOfVertexEdge;
141//
1155d05a 142typedef BOPTools_ContextFunctor
505abfb8 143 <BOPAlgo_VertexEdge,
144 BOPAlgo_VectorOfVertexEdge,
1e143abb 145 Handle(IntTools_Context),
146 IntTools_Context> BOPAlgo_VertexEdgeFunctor;
505abfb8 147//
1155d05a 148typedef BOPTools_ContextCnt
505abfb8 149 <BOPAlgo_VertexEdgeFunctor,
150 BOPAlgo_VectorOfVertexEdge,
1e143abb 151 Handle(IntTools_Context)> BOPAlgo_VertexEdgeCnt;
505abfb8 152//
4e57c75e 153//=======================================================================
154// function: PerformVE
155// purpose:
156//=======================================================================
505abfb8 157void BOPAlgo_PaveFiller::PerformVE()
4e57c75e 158{
3510db62 159 FillShrunkData(TopAbs_VERTEX, TopAbs_EDGE);
160 //
4e57c75e 161 myIterator->Initialize(TopAbs_VERTEX, TopAbs_EDGE);
8ae442a8 162 Standard_Integer iSize = myIterator->ExpectedLength();
4e57c75e 163 if (!iSize) {
164 return;
165 }
166 //
8ae442a8 167 // Prepare pairs for intersection
168 BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMVEPairs;
4e57c75e 169 for (; myIterator->More(); myIterator->Next()) {
8ae442a8 170 Standard_Integer nV, nE;
25dfc507 171 myIterator->Value(nV, nE);
4e57c75e 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)) {
4e57c75e 183 continue;
184 }
185 //
3510db62 186 const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks(nE);
01b5b3df 187 if (aLPB.IsEmpty()) {
188 continue;
189 }
190 //
191 const Handle(BOPDS_PaveBlock)& aPB = aLPB.First();
192 if (!aPB->IsSplittable()) {
3510db62 193 // this is a micro edge, ignore it
194 continue;
195 }
196 //
1155d05a 197 TColStd_ListOfInteger* pLV = aMVEPairs.ChangeSeek(aPB);
8ae442a8 198 if (!pLV)
1155d05a 199 pLV = &aMVEPairs(aMVEPairs.Add(aPB, TColStd_ListOfInteger()));
8ae442a8 200 pLV->Append(nV);
201 }
202 //
203 IntersectVE(aMVEPairs);
204}
205
206//=======================================================================
207// function: IntersectVE
208// purpose:
209//=======================================================================
210void 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
1155d05a 230 NCollection_DataMap<BOPDS_Pair, TColStd_ListOfInteger, BOPDS_PairMapHasher> aDMVSD;
8ae442a8 231 //
232 for (i = 1; i <= aNbVE; ++i) {
233 const Handle(BOPDS_PaveBlock)& aPB = theVEPairs.FindKey(i);
234 Standard_Integer nE = aPB->OriginalEdge();
505abfb8 235 //
1155d05a 236 const TColStd_ListOfInteger& aLV = theVEPairs(i);
237 TColStd_ListIteratorOfListOfInteger aItLV(aLV);
8ae442a8 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);
1155d05a 245 TColStd_ListOfInteger* pLI = aDMVSD.ChangeSeek(aPair);
8ae442a8 246 if (pLI) {
247 // Already added
248 pLI->Append(nV);
249 continue;
250 }
251 // New pair
1155d05a 252 pLI = aDMVSD.Bound(aPair, TColStd_ListOfInteger());
8ae442a8 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 //
1155d05a 258 BOPAlgo_VertexEdge& aVESolver = aVVE.Appended();
8ae442a8 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 }
505abfb8 267 //
8ae442a8 268 // Perform intersection
505abfb8 269 //=============================================================
270 BOPAlgo_VertexEdgeCnt::Perform(myRunParallel, aVVE, myContext);
271 //=============================================================
272 //
8ae442a8 273 // Keep the modified edges for further update
1155d05a 274 TColStd_MapOfInteger aMEdges;
8ae442a8 275 //
276 // Analyze intersections
1155d05a 277 aNbVE = aVVE.Length();
8ae442a8 278 for (i = 0; i < aNbVE; ++i) {
279 const BOPAlgo_VertexEdge& aVESolver = aVVE(i);
280 if (aVESolver.Flag() != 0) {
ad8b073e 281 if (aVESolver.HasErrors())
282 {
283 // Warn about failed intersection of sub-shapes
284 AddIntersectionFailedWarning(aVESolver.Vertex(), aVESolver.Edge());
285 }
8ae442a8 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);
1155d05a 308 const TColStd_ListOfInteger& aLI = aDMVSD.Find(aPair);
309 TColStd_ListIteratorOfListOfInteger aItLI(aLI);
8ae442a8 310 for (; aItLI.More(); aItLI.Next()) {
311 const Standard_Integer nVOld = aItLI.Value();
312 // 3. Create interference V/E
1155d05a 313 BOPDS_InterfVE& aVE = aVEs.Appended();
8ae442a8 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);
3510db62 321 }
322 }
8ae442a8 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//=======================================================================
337static
338 void MakeNewCommonBlock(const BOPDS_ListOfPaveBlock& theLPB,
1155d05a 339 const TColStd_ListOfInteger& theLFaces,
8ae442a8 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//=======================================================================
1155d05a 357void BOPAlgo_PaveFiller::SplitPaveBlocks(const TColStd_MapOfInteger& theMEdges,
8ae442a8 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 //
1155d05a 367 TColStd_MapIteratorOfMapOfInteger aItM(theMEdges);
8ae442a8 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();
3510db62 378 continue;
8ae442a8 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 //
e25185ff 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 {
8ae442a8 402 Standard_Integer nV1, nV2;
403 aPBN->Indices(nV1, nV2);
e25185ff 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 {
8ae442a8 420 BOPDS_Pair aPair;
421 aPair.SetIndices(nV1, nV2);
e25185ff 422 if (aMPairs.Add(aPair))
423 {
1155d05a 424 TColStd_ListOfInteger aLV;
8ae442a8 425 aLV.Append(nV1);
426 aLV.Append(nV2);
427 MakeSDVertices(aLV, theAddInterfs);
428 }
e25185ff 429 continue;
8ae442a8 430 }
8ae442a8 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();
3510db62 461 //
8ae442a8 462 BOPDS_Pair aPair;
463 aPair.SetIndices(aPB->Pave1().Index(), aPB->Pave2().Index());
3510db62 464 //
8ae442a8 465 BOPDS_ListOfPaveBlock* pLPBx = aMInds.ChangeSeek(aPair);
466 if (!pLPBx) {
467 pLPBx = &aMInds(aMInds.Add(aPair, BOPDS_ListOfPaveBlock()));
3510db62 468 }
8ae442a8 469 pLPBx->Append(aPB);
4e57c75e 470 }
8ae442a8 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}
ad8b073e 531
532//=======================================================================
533// function: AddIntersectionFailedWarning
534// purpose:
535//=======================================================================
536void 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}