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_Tools.hxx>
21 #include <BOPCol_NCVector.hxx>
22 #include <BOPCol_Parallel.hxx>
23 #include <BOPDS_DS.hxx>
24 #include <BOPDS_Interf.hxx>
25 #include <BOPDS_Iterator.hxx>
26 #include <BOPDS_Pair.hxx>
27 #include <BOPDS_PaveBlock.hxx>
28 #include <BOPDS_VectorOfInterfVE.hxx>
29 #include <BOPTools_AlgoTools.hxx>
30 #include <BRep_Tool.hxx>
32 #include <IntTools_Context.hxx>
33 #include <Precision.hxx>
35 #include <TopoDS_Edge.hxx>
36 #include <TopoDS_Vertex.hxx>
38 //=======================================================================
39 //class : BOPAlgo_VertexEdge
41 //=======================================================================
42 class BOPAlgo_VertexEdge : public BOPAlgo_Algo {
47 BOPAlgo_VertexEdge() :
49 myIV(-1), myIE(-1), myFlag(-1), myT(-1.), myTolVNew(-1.) {
52 virtual ~BOPAlgo_VertexEdge(){
55 void SetIndices(const Standard_Integer nV,
56 const Standard_Integer nE) {
61 void Indices(Standard_Integer& nV,
62 Standard_Integer& nE) const {
67 void SetVertex(const TopoDS_Vertex& aV) {
71 void SetEdge(const TopoDS_Edge& aE) {
75 const TopoDS_Vertex& Vertex() const {
79 const TopoDS_Edge& Edge() const {
83 Standard_Integer Flag()const {
87 Standard_Real Parameter()const {
91 Standard_Real VertexNewTolerance()const {
95 void SetContext(const Handle(IntTools_Context)& aContext) {
99 const Handle(IntTools_Context)& Context()const {
103 void SetPaveBlock(const Handle(BOPDS_PaveBlock)& thePB) {
107 const Handle(BOPDS_PaveBlock)& PaveBlock() const {
111 virtual void Perform() {
112 BOPAlgo_Algo::UserBreak();
113 myFlag=myContext->ComputeVE (myV, myE, myT, myTolVNew, myFuzzyValue);
117 Standard_Integer myIV;
118 Standard_Integer myIE;
119 Standard_Integer myFlag;
121 Standard_Real myTolVNew;
124 Handle(IntTools_Context) myContext;
125 Handle(BOPDS_PaveBlock) myPB;
127 //=======================================================================
128 typedef BOPCol_NCVector
129 <BOPAlgo_VertexEdge> BOPAlgo_VectorOfVertexEdge;
131 typedef BOPCol_ContextFunctor
133 BOPAlgo_VectorOfVertexEdge,
134 Handle(IntTools_Context),
135 IntTools_Context> BOPAlgo_VertexEdgeFunctor;
137 typedef BOPCol_ContextCnt
138 <BOPAlgo_VertexEdgeFunctor,
139 BOPAlgo_VectorOfVertexEdge,
140 Handle(IntTools_Context)> BOPAlgo_VertexEdgeCnt;
142 //=======================================================================
143 // function: PerformVE
145 //=======================================================================
146 void BOPAlgo_PaveFiller::PerformVE()
148 FillShrunkData(TopAbs_VERTEX, TopAbs_EDGE);
150 myIterator->Initialize(TopAbs_VERTEX, TopAbs_EDGE);
151 Standard_Integer iSize = myIterator->ExpectedLength();
156 // Prepare pairs for intersection
157 BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMVEPairs;
158 for (; myIterator->More(); myIterator->Next()) {
159 Standard_Integer nV, nE;
160 myIterator->Value(nV, nE);
162 const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
163 if (aSIE.HasSubShape(nV)) {
171 if (myDS->HasInterfShapeSubShapes(nV, nE)) {
175 const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks(nE);
176 if (aLPB.IsEmpty()) {
180 const Handle(BOPDS_PaveBlock)& aPB = aLPB.First();
181 if (!aPB->IsSplittable()) {
182 // this is a micro edge, ignore it
186 BOPCol_ListOfInteger* pLV = aMVEPairs.ChangeSeek(aPB);
188 pLV = &aMVEPairs(aMVEPairs.Add(aPB, BOPCol_ListOfInteger()));
192 IntersectVE(aMVEPairs);
195 //=======================================================================
196 // function: IntersectVE
198 //=======================================================================
199 void BOPAlgo_PaveFiller::IntersectVE
200 (const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& theVEPairs,
201 const Standard_Boolean theAddInterfs)
203 Standard_Integer i, aNbVE = theVEPairs.Extent();
208 BOPDS_VectorOfInterfVE& aVEs = myDS->InterfVE();
210 aVEs.SetIncrement(aNbVE);
213 // Prepare for intersection.
214 BOPAlgo_VectorOfVertexEdge aVVE;
215 // Map to collect all SD connections to add interferences
216 // for all vertices having the same SD vertex.
217 // It will also be used as a Fence map to avoid repeated
218 // intersection of the same SD vertex with edge
219 NCollection_DataMap<BOPDS_Pair, BOPCol_ListOfInteger, BOPDS_PairMapHasher> aDMVSD;
221 for (i = 1; i <= aNbVE; ++i) {
222 const Handle(BOPDS_PaveBlock)& aPB = theVEPairs.FindKey(i);
223 Standard_Integer nE = aPB->OriginalEdge();
225 const BOPCol_ListOfInteger& aLV = theVEPairs(i);
226 BOPCol_ListIteratorOfListOfInteger aItLV(aLV);
227 for (; aItLV.More(); aItLV.Next()) {
228 Standard_Integer nV = aItLV.Value();
230 Standard_Integer nVSD = nV;
231 myDS->HasShapeSD(nV, nVSD);
233 BOPDS_Pair aPair(nVSD, nE);
234 BOPCol_ListOfInteger* pLI = aDMVSD.ChangeSeek(aPair);
241 pLI = aDMVSD.Bound(aPair, BOPCol_ListOfInteger());
244 const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nVSD));
245 const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
247 BOPAlgo_VertexEdge& aVESolver = aVVE.Append1();
248 aVESolver.SetIndices(nVSD, nE);
249 aVESolver.SetVertex(aV);
250 aVESolver.SetEdge(aE);
251 aVESolver.SetPaveBlock(aPB);
252 aVESolver.SetFuzzyValue(myFuzzyValue);
253 aVESolver.SetProgressIndicator(myProgressIndicator);
257 // Perform intersection
258 //=============================================================
259 BOPAlgo_VertexEdgeCnt::Perform(myRunParallel, aVVE, myContext);
260 //=============================================================
262 // Keep the modified edges for further update
263 BOPCol_MapOfInteger aMEdges;
265 // Analyze intersections
266 aNbVE = aVVE.Extent();
267 for (i = 0; i < aNbVE; ++i) {
268 const BOPAlgo_VertexEdge& aVESolver = aVVE(i);
269 if (aVESolver.Flag() != 0) {
273 Standard_Integer nV, nE;
274 aVESolver.Indices(nV, nE);
275 // Parameter of vertex on edge
276 Standard_Real aT = aVESolver.Parameter();
277 // 1. Update vertex V/E if necessary
278 Standard_Real aTolVNew = aVESolver.VertexNewTolerance();
279 Standard_Integer nVx = UpdateVertex(nV, aTolVNew);
280 // 2. Create new pave and add it as extra pave to pave block
281 // for further splitting of the edge
282 const Handle(BOPDS_PaveBlock)& aPB = aVESolver.PaveBlock();
285 aPave.SetParameter(aT);
286 aPB->AppendExtPave(aPave);
290 // Add interferences into DS
291 BOPDS_Pair aPair(nV, nE);
292 const BOPCol_ListOfInteger& aLI = aDMVSD.Find(aPair);
293 BOPCol_ListIteratorOfListOfInteger aItLI(aLI);
294 for (; aItLI.More(); aItLI.Next()) {
295 const Standard_Integer nVOld = aItLI.Value();
296 // 3. Create interference V/E
297 BOPDS_InterfVE& aVE = aVEs.Append1();
298 aVE.SetIndices(nVOld, nE);
299 aVE.SetParameter(aT);
300 // 2. Add a pair in the whole table of interferences
301 myDS->AddInterf(nVOld, nE);
302 // 4. Set index of new vertex in the interference
303 if (myDS->IsNewShape(nVx)) {
304 aVE.SetIndexNew(nVx);
310 // Split pave blocks of the intersected edges with the extra paves.
311 // At the same time compute shrunk data for the new pave blocks
312 // and in case there is no valid range for the pave block,
313 // the vertices of this pave block should be unified.
314 SplitPaveBlocks(aMEdges, theAddInterfs);
317 //=======================================================================
318 // function: MakeNewCommonBlock
319 // purpose: Make new Common Block from the given list of Pave Blocks
320 //=======================================================================
322 void MakeNewCommonBlock(const BOPDS_ListOfPaveBlock& theLPB,
323 const BOPCol_ListOfInteger& theLFaces,
326 // Make Common Block from the pave blocks in the list
327 Handle(BOPDS_CommonBlock) aCBNew = new BOPDS_CommonBlock;
328 aCBNew->SetPaveBlocks(theLPB);
329 aCBNew->SetFaces(theLFaces);
331 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(theLPB);
332 for (; aItLPB.More(); aItLPB.Next()) {
333 theDS->SetCommonBlock(aItLPB.ChangeValue(), aCBNew);
337 //=======================================================================
338 // function: SplitPaveBlocks
340 //=======================================================================
341 void BOPAlgo_PaveFiller::SplitPaveBlocks(const BOPCol_MapOfInteger& theMEdges,
342 const Standard_Boolean theAddInterfs)
344 // Fence map to avoid unification of the same vertices twice
345 BOPDS_MapOfPair aMPairs;
346 // Map to treat the Common Blocks
347 NCollection_IndexedDataMap<Handle(BOPDS_CommonBlock),
348 BOPDS_ListOfPaveBlock,
349 TColStd_MapTransientHasher> aMCBNewPB;
351 BOPCol_MapIteratorOfMapOfInteger aItM(theMEdges);
352 for (; aItM.More(); aItM.Next()) {
353 Standard_Integer nE = aItM.Value();
354 BOPDS_ListOfPaveBlock& aLPB = myDS->ChangePaveBlocks(nE);
356 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
357 for (; aItLPB.More();) {
358 Handle(BOPDS_PaveBlock)& aPB = aItLPB.ChangeValue();
360 if (!aPB->IsToUpdate()) {
365 const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(aPB);
367 // Compute new pave blocks
368 BOPDS_ListOfPaveBlock aLPBN;
371 // Make sure that each new pave block has a valid range,
372 // otherwise unify the vertices of the pave block
373 BOPDS_ListIteratorOfListOfPaveBlock aItLPBN(aLPBN);
374 for (; aItLPBN.More(); aItLPBN.Next()) {
375 Handle(BOPDS_PaveBlock)& aPBN = aItLPBN.ChangeValue();
376 myDS->UpdatePaveBlockWithSDVertices(aPBN);
377 FillShrunkData(aPBN);
379 if (!aPBN->HasShrunkData()) {
380 // No valid range, unify vertices
381 Standard_Integer nV1, nV2;
382 aPBN->Indices(nV1, nV2);
385 aPair.SetIndices(nV1, nV2);
386 if (aMPairs.Add(aPair)) {
387 BOPCol_ListOfInteger aLV;
390 MakeSDVertices(aLV, theAddInterfs);
396 // Update the list with new pave block
398 // Treat the common block
400 // Store the new pave block to make new common block
401 BOPDS_ListOfPaveBlock* pLPBCB = aMCBNewPB.ChangeSeek(aCB);
403 pLPBCB = &aMCBNewPB(aMCBNewPB.Add(aCB, BOPDS_ListOfPaveBlock()));
405 pLPBCB->Append(aPBN);
408 // Remove old pave block
413 // Make Common Blocks
414 Standard_Integer i, aNbCB = aMCBNewPB.Extent();
415 for (i = 1; i <= aNbCB; ++i) {
416 const Handle(BOPDS_CommonBlock)& aCB = aMCBNewPB.FindKey(i);
417 const BOPDS_ListOfPaveBlock& aLPBN = aMCBNewPB(i);
419 // For each group of pave blocks with the same vertices make new common block
420 NCollection_IndexedDataMap<BOPDS_Pair, BOPDS_ListOfPaveBlock, BOPDS_PairMapHasher> aMInds;
421 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPBN);
422 for (; aItLPB.More(); aItLPB.Next()) {
423 const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
426 aPair.SetIndices(aPB->Pave1().Index(), aPB->Pave2().Index());
428 BOPDS_ListOfPaveBlock* pLPBx = aMInds.ChangeSeek(aPair);
430 pLPBx = &aMInds(aMInds.Add(aPair, BOPDS_ListOfPaveBlock()));
435 Standard_Integer nV1, nV2;
436 aCB->PaveBlock1()->Indices(nV1, nV2);
437 Standard_Boolean bIsClosed = (nV1 == nV2);
439 Standard_Integer j, aNbPairs = aMInds.Extent();
440 for (j = 1; j <= aNbPairs; ++j) {
441 BOPDS_ListOfPaveBlock& aLPB = aMInds(j);
444 // Make Common Block from the pave blocks in the list
445 MakeNewCommonBlock(aLPB, aCB->Faces(), myDS);
449 // Find coinciding pave blocks
450 while (aLPB.Extent()) {
451 // Pave blocks forming the common block
452 BOPDS_ListOfPaveBlock aLPBCB;
453 // Point in the middle of the first pave block in the common block
454 gp_Pnt aPMFirst(0., 0., 0.);
455 // Tolerance of the first edge in the common block
456 Standard_Real aTolEFirst = 0.;
458 aItLPB.Initialize(aLPB);
459 for (; aItLPB.More();) {
460 const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
461 if (aLPBCB.IsEmpty()) {
463 const TopoDS_Edge& aEFirst = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
464 aTolEFirst = BRep_Tool::MaxTolerance(aEFirst, TopAbs_VERTEX);
466 Standard_Real aTmFirst = (aPB->Pave1().Parameter() + aPB->Pave2().Parameter()) / 2.;
467 BOPTools_AlgoTools::PointOnEdge(aEFirst, aTmFirst, aPMFirst);
473 // Check pave blocks for coincidence
474 const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
475 Standard_Real aTolE = BRep_Tool::MaxTolerance(aE, TopAbs_VERTEX);
477 Standard_Real aTOut, aDist;
478 Standard_Integer iErr =
479 myContext->ComputePE(aPMFirst, aTolEFirst + aTolE + myFuzzyValue, aE, aTOut, aDist);
480 if (!iErr && ((aTOut > aPB->Pave1().Parameter()) && (aTOut < aPB->Pave2().Parameter()))) {
488 // Make Common Block from the pave blocks in the list
489 MakeNewCommonBlock(aLPBCB, aCB->Faces(), myDS);