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 <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>
33 #include <IntTools_Context.hxx>
34 #include <NCollection_Vector.hxx>
35 #include <Precision.hxx>
37 #include <TopoDS_Edge.hxx>
38 #include <TopoDS_Vertex.hxx>
40 //=======================================================================
41 //class : BOPAlgo_VertexEdge
43 //=======================================================================
44 class BOPAlgo_VertexEdge : public BOPAlgo_Algo {
49 BOPAlgo_VertexEdge() :
51 myIV(-1), myIE(-1), myFlag(-1), myT(-1.), myTolVNew(-1.) {
54 virtual ~BOPAlgo_VertexEdge(){
57 void SetIndices(const Standard_Integer nV,
58 const Standard_Integer nE) {
63 void Indices(Standard_Integer& nV,
64 Standard_Integer& nE) const {
69 void SetVertex(const TopoDS_Vertex& aV) {
73 void SetEdge(const TopoDS_Edge& aE) {
77 const TopoDS_Vertex& Vertex() const {
81 const TopoDS_Edge& Edge() const {
85 Standard_Integer Flag()const {
89 Standard_Real Parameter()const {
93 Standard_Real VertexNewTolerance()const {
97 void SetContext(const Handle(IntTools_Context)& aContext) {
101 const Handle(IntTools_Context)& Context()const {
105 void SetPaveBlock(const Handle(BOPDS_PaveBlock)& thePB) {
109 const Handle(BOPDS_PaveBlock)& PaveBlock() const {
113 virtual void Perform() {
114 BOPAlgo_Algo::UserBreak();
119 myFlag=myContext->ComputeVE (myV, myE, myT, myTolVNew, myFuzzyValue);
121 catch (Standard_Failure const&)
123 AddError(new BOPAlgo_AlertIntersectionFailed);
128 Standard_Integer myIV;
129 Standard_Integer myIE;
130 Standard_Integer myFlag;
132 Standard_Real myTolVNew;
135 Handle(IntTools_Context) myContext;
136 Handle(BOPDS_PaveBlock) myPB;
138 //=======================================================================
139 typedef NCollection_Vector<BOPAlgo_VertexEdge> BOPAlgo_VectorOfVertexEdge;
141 //=======================================================================
142 // function: PerformVE
144 //=======================================================================
145 void BOPAlgo_PaveFiller::PerformVE()
147 FillShrunkData(TopAbs_VERTEX, TopAbs_EDGE);
149 myIterator->Initialize(TopAbs_VERTEX, TopAbs_EDGE);
150 Standard_Integer iSize = myIterator->ExpectedLength();
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);
161 const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
162 if (aSIE.HasSubShape(nV)) {
170 if (myDS->HasInterf(nV, nE)) {
174 if (myDS->HasInterfShapeSubShapes(nV, nE)) {
178 const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks(nE);
179 if (aLPB.IsEmpty()) {
183 const Handle(BOPDS_PaveBlock)& aPB = aLPB.First();
184 if (!aPB->IsSplittable()) {
185 // this is a micro edge, ignore it
189 TColStd_ListOfInteger* pLV = aMVEPairs.ChangeSeek(aPB);
191 pLV = &aMVEPairs(aMVEPairs.Add(aPB, TColStd_ListOfInteger()));
195 IntersectVE(aMVEPairs);
198 //=======================================================================
199 // function: IntersectVE
201 //=======================================================================
202 void BOPAlgo_PaveFiller::IntersectVE
203 (const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& theVEPairs,
204 const Standard_Boolean theAddInterfs)
206 Standard_Integer i, aNbVE = theVEPairs.Extent();
211 BOPDS_VectorOfInterfVE& aVEs = myDS->InterfVE();
213 aVEs.SetIncrement(aNbVE);
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;
224 for (i = 1; i <= aNbVE; ++i) {
225 const Handle(BOPDS_PaveBlock)& aPB = theVEPairs.FindKey(i);
226 Standard_Integer nE = aPB->OriginalEdge();
228 TColStd_MapOfInteger aMVPB;
229 const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks (nE);
230 for (BOPDS_ListOfPaveBlock::Iterator itPB (aLPB); itPB.More(); itPB.Next())
232 aMVPB.Add (itPB.Value()->Pave1().Index());
233 aMVPB.Add (itPB.Value()->Pave2().Index());
236 const TColStd_ListOfInteger& aLV = theVEPairs(i);
237 TColStd_ListIteratorOfListOfInteger aItLV(aLV);
238 for (; aItLV.More(); aItLV.Next()) {
239 Standard_Integer nV = aItLV.Value();
241 Standard_Integer nVSD = nV;
242 myDS->HasShapeSD(nV, nVSD);
244 if (aMVPB.Contains (nVSD))
247 BOPDS_Pair aPair(nVSD, nE);
248 TColStd_ListOfInteger* pLI = aDMVSD.ChangeSeek(aPair);
255 pLI = aDMVSD.Bound(aPair, TColStd_ListOfInteger());
258 const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nVSD));
259 const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
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 if (myProgressScope != NULL)
269 aVESolver.SetProgressIndicator(*myProgressScope);
274 // Perform intersection
275 //=============================================================
276 BOPTools_Parallel::Perform (myRunParallel, aVVE, myContext);
277 //=============================================================
279 // Keep the modified edges for further update
280 TColStd_MapOfInteger aMEdges;
282 // Analyze intersections
283 aNbVE = aVVE.Length();
284 for (i = 0; i < aNbVE; ++i) {
285 const BOPAlgo_VertexEdge& aVESolver = aVVE(i);
286 if (aVESolver.Flag() != 0) {
287 if (aVESolver.HasErrors())
289 // Warn about failed intersection of sub-shapes
290 AddIntersectionFailedWarning(aVESolver.Vertex(), aVESolver.Edge());
295 Standard_Integer nV, nE;
296 aVESolver.Indices(nV, nE);
297 // Parameter of vertex on edge
298 Standard_Real aT = aVESolver.Parameter();
299 // 1. Update vertex V/E if necessary
300 Standard_Real aTolVNew = aVESolver.VertexNewTolerance();
301 Standard_Integer nVx = UpdateVertex(nV, aTolVNew);
302 // 2. Create new pave and add it as extra pave to pave block
303 // for further splitting of the edge
304 const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks (nE);
305 // Find the appropriate one
306 Handle(BOPDS_PaveBlock) aPB;
307 BOPDS_ListOfPaveBlock::Iterator itPB (aLPB);
308 for (; itPB.More(); itPB.Next())
311 Standard_Real aT1, aT2;
312 aPB->Range (aT1, aT2);
313 if (aT > aT1 && aT < aT2)
321 aPave.SetParameter(aT);
322 aPB->AppendExtPave(aPave);
326 // Add interferences into DS
327 BOPDS_Pair aPair(nV, nE);
328 const TColStd_ListOfInteger& aLI = aDMVSD.Find(aPair);
329 TColStd_ListIteratorOfListOfInteger aItLI(aLI);
330 for (; aItLI.More(); aItLI.Next()) {
331 const Standard_Integer nVOld = aItLI.Value();
332 // 3. Create interference V/E
333 BOPDS_InterfVE& aVE = aVEs.Appended();
334 aVE.SetIndices(nVOld, nE);
335 aVE.SetParameter(aT);
336 // 2. Add a pair in the whole table of interferences
337 myDS->AddInterf(nVOld, nE);
338 // 4. Set index of new vertex in the interference
339 if (myDS->IsNewShape(nVx)) {
340 aVE.SetIndexNew(nVx);
346 // Split pave blocks of the intersected edges with the extra paves.
347 // At the same time compute shrunk data for the new pave blocks
348 // and in case there is no valid range for the pave block,
349 // the vertices of this pave block should be unified.
350 SplitPaveBlocks(aMEdges, theAddInterfs);
353 //=======================================================================
354 // function: MakeNewCommonBlock
355 // purpose: Make new Common Block from the given list of Pave Blocks
356 //=======================================================================
358 void MakeNewCommonBlock(const BOPDS_ListOfPaveBlock& theLPB,
359 const TColStd_ListOfInteger& theLFaces,
362 // Make Common Block from the pave blocks in the list
363 Handle(BOPDS_CommonBlock) aCBNew = new BOPDS_CommonBlock;
364 aCBNew->SetPaveBlocks(theLPB);
365 aCBNew->SetFaces(theLFaces);
367 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(theLPB);
368 for (; aItLPB.More(); aItLPB.Next()) {
369 theDS->SetCommonBlock(aItLPB.ChangeValue(), aCBNew);
373 //=======================================================================
374 // function: SplitPaveBlocks
376 //=======================================================================
377 void BOPAlgo_PaveFiller::SplitPaveBlocks(const TColStd_MapOfInteger& theMEdges,
378 const Standard_Boolean theAddInterfs)
380 // Fence map to avoid unification of the same vertices twice
381 BOPDS_MapOfPair aMPairs;
382 // Map to treat the Common Blocks
383 NCollection_IndexedDataMap<Handle(BOPDS_CommonBlock),
384 BOPDS_ListOfPaveBlock,
385 TColStd_MapTransientHasher> aMCBNewPB;
387 // Map of vertices to init the pave blocks for them
388 TColStd_MapOfInteger aMVerticesToInitPB;
390 TColStd_MapIteratorOfMapOfInteger aItM(theMEdges);
391 for (; aItM.More(); aItM.Next()) {
392 Standard_Integer nE = aItM.Value();
393 BOPDS_ListOfPaveBlock& aLPB = myDS->ChangePaveBlocks(nE);
395 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
396 for (; aItLPB.More();) {
397 Handle(BOPDS_PaveBlock)& aPB = aItLPB.ChangeValue();
399 if (!aPB->IsToUpdate()) {
404 const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(aPB);
406 // Compute new pave blocks
407 BOPDS_ListOfPaveBlock aLPBN;
410 // Make sure that each new pave block has a valid range,
411 // otherwise unify the vertices of the pave block
412 BOPDS_ListIteratorOfListOfPaveBlock aItLPBN(aLPBN);
413 for (; aItLPBN.More(); aItLPBN.Next()) {
414 Handle(BOPDS_PaveBlock)& aPBN = aItLPBN.ChangeValue();
415 myDS->UpdatePaveBlockWithSDVertices(aPBN);
416 FillShrunkData(aPBN);
418 Standard_Boolean bHasValidRange = aPBN->HasShrunkData();
419 // Take into account that the edge could have really small valid range,
420 // so that the Pave Block cannot be further split. In this case, check if
421 // the vertices of the Pave Block do not interfere. And if they are, unify them.
422 Standard_Boolean bCheckDist = (bHasValidRange && !aPBN->IsSplittable());
423 if (!bHasValidRange || bCheckDist)
425 Standard_Integer nV1, nV2;
426 aPBN->Indices(nV1, nV2);
428 // Same vertices -> no valid range, no need to unify vertices
431 // Decide whether to unify vertices or not
434 const TopoDS_Vertex& aV1 = TopoDS::Vertex(myDS->Shape(nV1));
435 const TopoDS_Vertex& aV2 = TopoDS::Vertex(myDS->Shape(nV2));
436 if (BOPTools_AlgoTools::ComputeVV(aV1, aV2, myFuzzyValue) == 0)
437 // vertices are interfering -> no valid range, unify vertices
438 bHasValidRange = Standard_False;
444 aPair.SetIndices(nV1, nV2);
445 if (aMPairs.Add(aPair))
447 TColStd_ListOfInteger aLV;
450 MakeSDVertices(aLV, theAddInterfs);
452 // Save vertices to init pave blocks
453 aMVerticesToInitPB.Add(nV1);
454 aMVerticesToInitPB.Add(nV2);
460 // Update the list with new pave block
462 // Treat the common block
464 // Store the new pave block to make new common block
465 BOPDS_ListOfPaveBlock* pLPBCB = aMCBNewPB.ChangeSeek(aCB);
467 pLPBCB = &aMCBNewPB(aMCBNewPB.Add(aCB, BOPDS_ListOfPaveBlock()));
469 pLPBCB->Append(aPBN);
472 // Remove old pave block
477 // Make Common Blocks
478 Standard_Integer i, aNbCB = aMCBNewPB.Extent();
479 for (i = 1; i <= aNbCB; ++i) {
480 const Handle(BOPDS_CommonBlock)& aCB = aMCBNewPB.FindKey(i);
481 const BOPDS_ListOfPaveBlock& aLPBN = aMCBNewPB(i);
483 // For each group of pave blocks with the same vertices make new common block
484 NCollection_IndexedDataMap<BOPDS_Pair, BOPDS_ListOfPaveBlock, BOPDS_PairMapHasher> aMInds;
485 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPBN);
486 for (; aItLPB.More(); aItLPB.Next()) {
487 const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
490 aPair.SetIndices(aPB->Pave1().Index(), aPB->Pave2().Index());
492 BOPDS_ListOfPaveBlock* pLPBx = aMInds.ChangeSeek(aPair);
494 pLPBx = &aMInds(aMInds.Add(aPair, BOPDS_ListOfPaveBlock()));
499 Standard_Integer nV1, nV2;
500 aCB->PaveBlock1()->Indices(nV1, nV2);
501 Standard_Boolean bIsClosed = (nV1 == nV2);
503 Standard_Integer j, aNbPairs = aMInds.Extent();
504 for (j = 1; j <= aNbPairs; ++j) {
505 BOPDS_ListOfPaveBlock& aLPB = aMInds(j);
508 // Make Common Block from the pave blocks in the list
509 MakeNewCommonBlock(aLPB, aCB->Faces(), myDS);
513 // Find coinciding pave blocks
514 while (aLPB.Extent()) {
515 // Pave blocks forming the common block
516 BOPDS_ListOfPaveBlock aLPBCB;
517 // Point in the middle of the first pave block in the common block
518 gp_Pnt aPMFirst(0., 0., 0.);
519 // Tolerance of the first edge in the common block
520 Standard_Real aTolEFirst = 0.;
522 aItLPB.Initialize(aLPB);
523 for (; aItLPB.More();) {
524 const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
525 if (aLPBCB.IsEmpty()) {
527 const TopoDS_Edge& aEFirst = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
528 aTolEFirst = BRep_Tool::MaxTolerance(aEFirst, TopAbs_VERTEX);
530 Standard_Real aTmFirst = (aPB->Pave1().Parameter() + aPB->Pave2().Parameter()) / 2.;
531 BOPTools_AlgoTools::PointOnEdge(aEFirst, aTmFirst, aPMFirst);
537 // Check pave blocks for coincidence
538 const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
539 Standard_Real aTolE = BRep_Tool::MaxTolerance(aE, TopAbs_VERTEX);
541 Standard_Real aTOut, aDist;
542 Standard_Integer iErr =
543 myContext->ComputePE(aPMFirst, aTolEFirst + aTolE + myFuzzyValue, aE, aTOut, aDist);
544 if (!iErr && ((aTOut > aPB->Pave1().Parameter()) && (aTOut < aPB->Pave2().Parameter()))) {
552 // Make Common Block from the pave blocks in the list
553 MakeNewCommonBlock(aLPBCB, aCB->Faces(), myDS);
558 // Init pave blocks for vertices which have acquired SD vertex
559 aItM.Initialize(aMVerticesToInitPB);
560 for (; aItM.More(); aItM.Next())
561 myDS->InitPaveBlocksForVertex(aItM.Value());
564 //=======================================================================
565 // function: AddIntersectionFailedWarning
567 //=======================================================================
568 void BOPAlgo_PaveFiller::AddIntersectionFailedWarning(const TopoDS_Shape& theS1,
569 const TopoDS_Shape& theS2)
571 // Create the warn shape
573 BRep_Builder().MakeCompound(aWC);
574 BRep_Builder().Add(aWC, theS1);
575 BRep_Builder().Add(aWC, theS2);
577 AddWarning(new BOPAlgo_AlertIntersectionOfPairOfShapesFailed(aWC));