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)
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
140 <BOPAlgo_VertexEdge> BOPAlgo_VectorOfVertexEdge;
142 typedef BOPTools_ContextFunctor
144 BOPAlgo_VectorOfVertexEdge,
145 Handle(IntTools_Context),
146 IntTools_Context> BOPAlgo_VertexEdgeFunctor;
148 typedef BOPTools_ContextCnt
149 <BOPAlgo_VertexEdgeFunctor,
150 BOPAlgo_VectorOfVertexEdge,
151 Handle(IntTools_Context)> BOPAlgo_VertexEdgeCnt;
153 //=======================================================================
154 // function: PerformVE
156 //=======================================================================
157 void BOPAlgo_PaveFiller::PerformVE()
159 FillShrunkData(TopAbs_VERTEX, TopAbs_EDGE);
161 myIterator->Initialize(TopAbs_VERTEX, TopAbs_EDGE);
162 Standard_Integer iSize = myIterator->ExpectedLength();
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);
173 const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
174 if (aSIE.HasSubShape(nV)) {
182 if (myDS->HasInterf(nV, nE)) {
186 if (myDS->HasInterfShapeSubShapes(nV, nE)) {
190 const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks(nE);
191 if (aLPB.IsEmpty()) {
195 const Handle(BOPDS_PaveBlock)& aPB = aLPB.First();
196 if (!aPB->IsSplittable()) {
197 // this is a micro edge, ignore it
201 TColStd_ListOfInteger* pLV = aMVEPairs.ChangeSeek(aPB);
203 pLV = &aMVEPairs(aMVEPairs.Add(aPB, TColStd_ListOfInteger()));
207 IntersectVE(aMVEPairs);
210 //=======================================================================
211 // function: IntersectVE
213 //=======================================================================
214 void BOPAlgo_PaveFiller::IntersectVE
215 (const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& theVEPairs,
216 const Standard_Boolean theAddInterfs)
218 Standard_Integer i, aNbVE = theVEPairs.Extent();
223 BOPDS_VectorOfInterfVE& aVEs = myDS->InterfVE();
225 aVEs.SetIncrement(aNbVE);
228 // Prepare for intersection.
229 BOPAlgo_VectorOfVertexEdge aVVE;
230 // Map to collect all SD connections to add interferences
231 // for all vertices having the same SD vertex.
232 // It will also be used as a Fence map to avoid repeated
233 // intersection of the same SD vertex with edge
234 NCollection_DataMap<BOPDS_Pair, TColStd_ListOfInteger, BOPDS_PairMapHasher> aDMVSD;
236 for (i = 1; i <= aNbVE; ++i) {
237 const Handle(BOPDS_PaveBlock)& aPB = theVEPairs.FindKey(i);
238 Standard_Integer nE = aPB->OriginalEdge();
240 const TColStd_ListOfInteger& aLV = theVEPairs(i);
241 TColStd_ListIteratorOfListOfInteger aItLV(aLV);
242 for (; aItLV.More(); aItLV.Next()) {
243 Standard_Integer nV = aItLV.Value();
245 Standard_Integer nVSD = nV;
246 myDS->HasShapeSD(nV, nVSD);
248 BOPDS_Pair aPair(nVSD, nE);
249 TColStd_ListOfInteger* pLI = aDMVSD.ChangeSeek(aPair);
256 pLI = aDMVSD.Bound(aPair, TColStd_ListOfInteger());
259 const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nVSD));
260 const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
262 BOPAlgo_VertexEdge& aVESolver = aVVE.Appended();
263 aVESolver.SetIndices(nVSD, nE);
264 aVESolver.SetVertex(aV);
265 aVESolver.SetEdge(aE);
266 aVESolver.SetPaveBlock(aPB);
267 aVESolver.SetFuzzyValue(myFuzzyValue);
268 aVESolver.SetProgressIndicator(myProgressIndicator);
272 // Perform intersection
273 //=============================================================
274 BOPAlgo_VertexEdgeCnt::Perform(myRunParallel, aVVE, myContext);
275 //=============================================================
277 // Keep the modified edges for further update
278 TColStd_MapOfInteger aMEdges;
280 // Analyze intersections
281 aNbVE = aVVE.Length();
282 for (i = 0; i < aNbVE; ++i) {
283 const BOPAlgo_VertexEdge& aVESolver = aVVE(i);
284 if (aVESolver.Flag() != 0) {
285 if (aVESolver.HasErrors())
287 // Warn about failed intersection of sub-shapes
288 AddIntersectionFailedWarning(aVESolver.Vertex(), aVESolver.Edge());
293 Standard_Integer nV, nE;
294 aVESolver.Indices(nV, nE);
295 // Parameter of vertex on edge
296 Standard_Real aT = aVESolver.Parameter();
297 // 1. Update vertex V/E if necessary
298 Standard_Real aTolVNew = aVESolver.VertexNewTolerance();
299 Standard_Integer nVx = UpdateVertex(nV, aTolVNew);
300 // 2. Create new pave and add it as extra pave to pave block
301 // for further splitting of the edge
302 const Handle(BOPDS_PaveBlock)& aPB = aVESolver.PaveBlock();
305 aPave.SetParameter(aT);
306 aPB->AppendExtPave(aPave);
310 // Add interferences into DS
311 BOPDS_Pair aPair(nV, nE);
312 const TColStd_ListOfInteger& aLI = aDMVSD.Find(aPair);
313 TColStd_ListIteratorOfListOfInteger aItLI(aLI);
314 for (; aItLI.More(); aItLI.Next()) {
315 const Standard_Integer nVOld = aItLI.Value();
316 // 3. Create interference V/E
317 BOPDS_InterfVE& aVE = aVEs.Appended();
318 aVE.SetIndices(nVOld, nE);
319 aVE.SetParameter(aT);
320 // 2. Add a pair in the whole table of interferences
321 myDS->AddInterf(nVOld, nE);
322 // 4. Set index of new vertex in the interference
323 if (myDS->IsNewShape(nVx)) {
324 aVE.SetIndexNew(nVx);
330 // Split pave blocks of the intersected edges with the extra paves.
331 // At the same time compute shrunk data for the new pave blocks
332 // and in case there is no valid range for the pave block,
333 // the vertices of this pave block should be unified.
334 SplitPaveBlocks(aMEdges, theAddInterfs);
337 //=======================================================================
338 // function: MakeNewCommonBlock
339 // purpose: Make new Common Block from the given list of Pave Blocks
340 //=======================================================================
342 void MakeNewCommonBlock(const BOPDS_ListOfPaveBlock& theLPB,
343 const TColStd_ListOfInteger& theLFaces,
346 // Make Common Block from the pave blocks in the list
347 Handle(BOPDS_CommonBlock) aCBNew = new BOPDS_CommonBlock;
348 aCBNew->SetPaveBlocks(theLPB);
349 aCBNew->SetFaces(theLFaces);
351 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(theLPB);
352 for (; aItLPB.More(); aItLPB.Next()) {
353 theDS->SetCommonBlock(aItLPB.ChangeValue(), aCBNew);
357 //=======================================================================
358 // function: SplitPaveBlocks
360 //=======================================================================
361 void BOPAlgo_PaveFiller::SplitPaveBlocks(const TColStd_MapOfInteger& theMEdges,
362 const Standard_Boolean theAddInterfs)
364 // Fence map to avoid unification of the same vertices twice
365 BOPDS_MapOfPair aMPairs;
366 // Map to treat the Common Blocks
367 NCollection_IndexedDataMap<Handle(BOPDS_CommonBlock),
368 BOPDS_ListOfPaveBlock,
369 TColStd_MapTransientHasher> aMCBNewPB;
371 // Map of vertices to init the pave blocks for them
372 TColStd_MapOfInteger aMVerticesToInitPB;
374 TColStd_MapIteratorOfMapOfInteger aItM(theMEdges);
375 for (; aItM.More(); aItM.Next()) {
376 Standard_Integer nE = aItM.Value();
377 BOPDS_ListOfPaveBlock& aLPB = myDS->ChangePaveBlocks(nE);
379 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
380 for (; aItLPB.More();) {
381 Handle(BOPDS_PaveBlock)& aPB = aItLPB.ChangeValue();
383 if (!aPB->IsToUpdate()) {
388 const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(aPB);
390 // Compute new pave blocks
391 BOPDS_ListOfPaveBlock aLPBN;
394 // Make sure that each new pave block has a valid range,
395 // otherwise unify the vertices of the pave block
396 BOPDS_ListIteratorOfListOfPaveBlock aItLPBN(aLPBN);
397 for (; aItLPBN.More(); aItLPBN.Next()) {
398 Handle(BOPDS_PaveBlock)& aPBN = aItLPBN.ChangeValue();
399 myDS->UpdatePaveBlockWithSDVertices(aPBN);
400 FillShrunkData(aPBN);
402 Standard_Boolean bHasValidRange = aPBN->HasShrunkData();
403 // Take into account that the edge could have really small valid range,
404 // so that the Pave Block cannot be further split. In this case, check if
405 // the vertices of the Pave Block do not interfere. And if they are, unify them.
406 Standard_Boolean bCheckDist = (bHasValidRange && !aPBN->IsSplittable());
407 if (!bHasValidRange || bCheckDist)
409 Standard_Integer nV1, nV2;
410 aPBN->Indices(nV1, nV2);
412 // Same vertices -> no valid range, no need to unify vertices
415 // Decide whether to unify vertices or not
418 const TopoDS_Vertex& aV1 = TopoDS::Vertex(myDS->Shape(nV1));
419 const TopoDS_Vertex& aV2 = TopoDS::Vertex(myDS->Shape(nV2));
420 if (BOPTools_AlgoTools::ComputeVV(aV1, aV2, myFuzzyValue) == 0)
421 // vertices are interfering -> no valid range, unify vertices
422 bHasValidRange = Standard_False;
428 aPair.SetIndices(nV1, nV2);
429 if (aMPairs.Add(aPair))
431 TColStd_ListOfInteger aLV;
434 MakeSDVertices(aLV, theAddInterfs);
436 // Save vertices to init pave blocks
437 aMVerticesToInitPB.Add(nV1);
438 aMVerticesToInitPB.Add(nV2);
444 // Update the list with new pave block
446 // Treat the common block
448 // Store the new pave block to make new common block
449 BOPDS_ListOfPaveBlock* pLPBCB = aMCBNewPB.ChangeSeek(aCB);
451 pLPBCB = &aMCBNewPB(aMCBNewPB.Add(aCB, BOPDS_ListOfPaveBlock()));
453 pLPBCB->Append(aPBN);
456 // Remove old pave block
461 // Make Common Blocks
462 Standard_Integer i, aNbCB = aMCBNewPB.Extent();
463 for (i = 1; i <= aNbCB; ++i) {
464 const Handle(BOPDS_CommonBlock)& aCB = aMCBNewPB.FindKey(i);
465 const BOPDS_ListOfPaveBlock& aLPBN = aMCBNewPB(i);
467 // For each group of pave blocks with the same vertices make new common block
468 NCollection_IndexedDataMap<BOPDS_Pair, BOPDS_ListOfPaveBlock, BOPDS_PairMapHasher> aMInds;
469 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPBN);
470 for (; aItLPB.More(); aItLPB.Next()) {
471 const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
474 aPair.SetIndices(aPB->Pave1().Index(), aPB->Pave2().Index());
476 BOPDS_ListOfPaveBlock* pLPBx = aMInds.ChangeSeek(aPair);
478 pLPBx = &aMInds(aMInds.Add(aPair, BOPDS_ListOfPaveBlock()));
483 Standard_Integer nV1, nV2;
484 aCB->PaveBlock1()->Indices(nV1, nV2);
485 Standard_Boolean bIsClosed = (nV1 == nV2);
487 Standard_Integer j, aNbPairs = aMInds.Extent();
488 for (j = 1; j <= aNbPairs; ++j) {
489 BOPDS_ListOfPaveBlock& aLPB = aMInds(j);
492 // Make Common Block from the pave blocks in the list
493 MakeNewCommonBlock(aLPB, aCB->Faces(), myDS);
497 // Find coinciding pave blocks
498 while (aLPB.Extent()) {
499 // Pave blocks forming the common block
500 BOPDS_ListOfPaveBlock aLPBCB;
501 // Point in the middle of the first pave block in the common block
502 gp_Pnt aPMFirst(0., 0., 0.);
503 // Tolerance of the first edge in the common block
504 Standard_Real aTolEFirst = 0.;
506 aItLPB.Initialize(aLPB);
507 for (; aItLPB.More();) {
508 const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
509 if (aLPBCB.IsEmpty()) {
511 const TopoDS_Edge& aEFirst = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
512 aTolEFirst = BRep_Tool::MaxTolerance(aEFirst, TopAbs_VERTEX);
514 Standard_Real aTmFirst = (aPB->Pave1().Parameter() + aPB->Pave2().Parameter()) / 2.;
515 BOPTools_AlgoTools::PointOnEdge(aEFirst, aTmFirst, aPMFirst);
521 // Check pave blocks for coincidence
522 const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
523 Standard_Real aTolE = BRep_Tool::MaxTolerance(aE, TopAbs_VERTEX);
525 Standard_Real aTOut, aDist;
526 Standard_Integer iErr =
527 myContext->ComputePE(aPMFirst, aTolEFirst + aTolE + myFuzzyValue, aE, aTOut, aDist);
528 if (!iErr && ((aTOut > aPB->Pave1().Parameter()) && (aTOut < aPB->Pave2().Parameter()))) {
536 // Make Common Block from the pave blocks in the list
537 MakeNewCommonBlock(aLPBCB, aCB->Faces(), myDS);
542 // Init pave blocks for vertices which have acquired SD vertex
543 aItM.Initialize(aMVerticesToInitPB);
544 for (; aItM.More(); aItM.Next())
545 myDS->InitPaveBlocksForVertex(aItM.Value());
548 //=======================================================================
549 // function: AddIntersectionFailedWarning
551 //=======================================================================
552 void BOPAlgo_PaveFiller::AddIntersectionFailedWarning(const TopoDS_Shape& theS1,
553 const TopoDS_Shape& theS2)
555 // Create the warn shape
557 BRep_Builder().MakeCompound(aWC);
558 BRep_Builder().Add(aWC, theS1);
559 BRep_Builder().Add(aWC, theS2);
561 AddWarning(new BOPAlgo_AlertIntersectionOfPairOfShapesFailed(aWC));