1 // Created by: Peter KURNEV
2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
4 // This file is part of Open CASCADE Technology software library.
6 // This library is free software; you can redistribute it and/or modify it under
7 // the terms of the GNU Lesser General Public License version 2.1 as published
8 // by the Free Software Foundation, with special exception defined in the file
9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
10 // distribution for complete text of the license and disclaimer of any warranty.
12 // Alternatively, this file may be used under the terms of Open CASCADE
13 // commercial license or contractual agreement.
15 // File: BOPAlgo_ShellSplitter.cxx
16 // Created: Thu Jan 16 08:33:50 2014
18 #include <BOPAlgo_ShellSplitter.hxx>
19 #include <BOPTools_AlgoTools.hxx>
20 #include <BOPTools_CoupleOfShape.hxx>
21 #include <BOPTools_Parallel.hxx>
22 #include <BRep_Builder.hxx>
23 #include <IntTools_Context.hxx>
24 #include <NCollection_Vector.hxx>
26 #include <TopExp_Explorer.hxx>
28 #include <TopoDS_Edge.hxx>
29 #include <TopoDS_Shape.hxx>
30 #include <TopoDS_Shell.hxx>
31 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
32 #include <TopTools_IndexedMapOfShape.hxx>
33 #include <TopTools_MapOfOrientedShape.hxx>
34 #include <TopTools_MapOfShape.hxx>
38 void MakeShell(const TopTools_ListOfShape& ,
42 void RefineShell(TopoDS_Shell& theShell,
43 const TopTools_IndexedDataMapOfShapeListOfShape& theMEF,
44 TopTools_ListOfShape& aLShX);
46 //=======================================================================
49 //=======================================================================
59 void SetConnexityBlock (const BOPTools_ConnexityBlock& aCB) {
60 myPCB=(BOPTools_ConnexityBlock*)&aCB;
63 BOPTools_ConnexityBlock& ConnexityBlock () {
68 BOPAlgo_ShellSplitter::SplitBlock(*myPCB);
71 BOPTools_ConnexityBlock *myPCB;
73 //=======================================================================
74 typedef NCollection_Vector<BOPAlgo_CBK> BOPAlgo_VectorOfCBK;
76 //=======================================================================
79 //=======================================================================
80 BOPAlgo_ShellSplitter::BOPAlgo_ShellSplitter()
83 myStartShapes(myAllocator),
84 myShells(myAllocator),
88 //=======================================================================
91 //=======================================================================
92 BOPAlgo_ShellSplitter::BOPAlgo_ShellSplitter
93 (const Handle(NCollection_BaseAllocator)& theAllocator)
95 BOPAlgo_Algo(theAllocator),
96 myStartShapes(theAllocator),
97 myShells(theAllocator),
101 //=======================================================================
104 //=======================================================================
105 BOPAlgo_ShellSplitter::~BOPAlgo_ShellSplitter()
108 //=======================================================================
109 //function : AddStartElement
111 //=======================================================================
112 void BOPAlgo_ShellSplitter::AddStartElement(const TopoDS_Shape& aE)
114 myStartShapes.Append(aE);
116 //=======================================================================
117 //function : StartElements
119 //=======================================================================
120 const TopTools_ListOfShape& BOPAlgo_ShellSplitter::StartElements()const
122 return myStartShapes;
124 //=======================================================================
127 //=======================================================================
128 const TopTools_ListOfShape& BOPAlgo_ShellSplitter::Shells()const
132 //=======================================================================
135 //=======================================================================
136 void BOPAlgo_ShellSplitter::Perform()
138 GetReport()->Clear();
140 BOPTools_AlgoTools::MakeConnexityBlocks
141 (myStartShapes, TopAbs_EDGE, TopAbs_FACE, myLCB);
146 //=======================================================================
147 //function : SplitBlock
149 //=======================================================================
150 void BOPAlgo_ShellSplitter::SplitBlock(BOPTools_ConnexityBlock& aCB)
152 Standard_Integer aNbLF, aNbOff, aNbFP;
154 TopAbs_Orientation anOr;
157 TopoDS_Iterator aItS;
158 TopExp_Explorer aExp;
159 TopTools_ListIteratorOfListOfShape aItF;
160 BOPTools_CoupleOfShape aCSOff;
161 TopTools_MapOfOrientedShape AddedFacesMap;
162 TopTools_IndexedDataMapOfShapeListOfShape aEFMap, aMEFP;
163 Handle (IntTools_Context) aContext;
165 aContext=new IntTools_Context;
167 const TopTools_ListOfShape& myShapes=aCB.Shapes();
169 TopTools_ListOfShape& myLoops=aCB.ChangeLoops();
172 // Copy faces into the map, for recursive search of free bounds
173 TopTools_MapOfOrientedShape aMFaces;
174 aItF.Initialize (myShapes);
175 for (; aItF.More(); aItF.Next()) {
176 aMFaces.Add(aItF.Value());
179 // remove the faces with free edges from processing
183 aItF.Initialize(myShapes);
184 for (; aItF.More(); aItF.Next()) {
185 const TopoDS_Shape& aF = aItF.Value();
186 if (aMFaces.Contains(aF)) {
187 TopExp::MapShapesAndAncestors (aF, TopAbs_EDGE, TopAbs_FACE, aEFMap);
191 Standard_Integer aNbBegin = aMFaces.Extent();
192 // check the free edges
193 Standard_Integer aNbE = aEFMap.Extent();
194 for (i = 1; i <= aNbE; ++i) {
195 const TopoDS_Edge& aE = TopoDS::Edge(aEFMap.FindKey(i));
196 if (!(BRep_Tool::Degenerated(aE) || aE.Orientation() == TopAbs_INTERNAL)) {
197 const TopTools_ListOfShape& aLF = aEFMap(i);
198 if (aLF.Extent() == 1) {
200 aMFaces.Remove(aLF.First());
205 // check if any faces have been removed
206 Standard_Integer aNbEnd = aMFaces.Extent();
207 if ((aNbEnd == aNbBegin) || (aNbEnd == 0)) {
212 if (aMFaces.IsEmpty()) {
216 // use only connected faces
217 TopTools_ListOfShape aLFConnected;
218 aItF.Initialize (myShapes);
219 for (; aItF.More(); aItF.Next()) {
220 const TopoDS_Shape& aF = aItF.Value();
221 if (aMFaces.Contains(aF)) {
222 aLFConnected.Append(aF);
226 const Standard_Integer aNbShapes = aLFConnected.Extent();
227 Standard_Boolean bAllFacesTaken = Standard_False;
230 aItF.Initialize (aLFConnected);
231 for (i = 1; aItF.More() && !bAllFacesTaken; aItF.Next(), ++i) {
232 const TopoDS_Shape& aFF = aItF.Value();
233 if (!AddedFacesMap.Add(aFF)) {
238 TopoDS_Shell aShellStart;
239 aBB.MakeShell(aShellStart);
240 aBB.Add(aShellStart, aFF);
242 TopTools_ListOfShape aLShells;
243 aLShells.Append(aShellStart);
245 TopTools_ListIteratorOfListOfShape aItLShells(aLShells);
246 for (; aItLShells.More(); aItLShells.Next()) {
247 TopoDS_Shell& aShell = TopoDS::Shell(aItLShells.ChangeValue());
250 TopExp::MapShapesAndAncestors(aShell, TopAbs_EDGE, TopAbs_FACE, aMEFP);
252 // loop on faces added to Shell;
253 // add their neighbor faces to Shell and so on
254 aItS.Initialize(aShell);
255 for (; aItS.More(); aItS.Next()) {
256 const TopoDS_Face& aF = (*(TopoDS_Face*)(&aItS.Value()));
258 // loop on edges of aF; find a good neighbor face of aF by aE
259 aExp.Init(aF, TopAbs_EDGE);
260 for (; aExp.More(); aExp.Next()) {
261 const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&aExp.Current()));
263 // proceed only free edges in this shell
264 if (aMEFP.Contains(aE)) {
265 const TopTools_ListOfShape& aLFP = aMEFP.FindFromKey(aE);
266 aNbFP = aLFP.Extent();
271 // avoid processing of internal edges
272 anOr = aE.Orientation();
273 if (anOr == TopAbs_INTERNAL) {
276 // avoid processing of degenerated edges
277 if (BRep_Tool::Degenerated(aE)) {
281 // candidate faces list
282 const TopTools_ListOfShape& aLF = aEFMap.FindFromKey(aE);
283 aNbLF = aLF.Extent();
288 // prepare for selecting the next face
289 // take only not-processed faces as a candidates
290 BOPTools_ListOfCoupleOfShape aLCSOff;
292 TopTools_ListIteratorOfListOfShape aItLF(aLF);
293 for (; aItLF.More(); aItLF.Next()) {
294 const TopoDS_Face& aFL = (*(TopoDS_Face*)(&aItLF.Value()));
295 if (aF.IsSame(aFL) || AddedFacesMap.Contains(aFL)) {
299 // find current edge in the face
300 if (!BOPTools_AlgoTools::GetEdgeOff(aE, aFL, aEL)) {
304 aCSOff.SetShape1(aEL);
305 aCSOff.SetShape2(aFL);
306 aLCSOff.Append(aCSOff);
307 }//for (; aItLF.More(); aItLF.Next()) {
309 aNbOff = aLCSOff.Extent();
314 // among all the adjacent faces chose one with the minimal
315 // angle to the current one
318 aSelF = (*(TopoDS_Face*)(&aLCSOff.First().Shape2()));
320 else if (aNbOff > 1) {
321 BOPTools_AlgoTools::GetFaceOff(aE, aF, aLCSOff, aSelF, aContext);
324 if (!aSelF.IsNull() && AddedFacesMap.Add(aSelF)) {
325 aBB.Add(aShell, aSelF);
326 TopExp::MapShapesAndAncestors(aSelF, TopAbs_EDGE, TopAbs_FACE, aMEFP);
328 } // for (; aExp.More(); aExp.Next()) {
329 } // for (; aItS.More(); aItS.Next()) {
331 // split the shell on multi-connected edges
332 TopTools_ListOfShape aLShSp;
333 RefineShell(aShell, aMEFP, aLShSp);
335 // collect the not closed shells for further processing
336 TopTools_ListOfShape aLShNC;
338 TopTools_ListIteratorOfListOfShape aItLShSp(aLShSp);
339 for (; aItLShSp.More(); aItLShSp.Next()) {
340 TopoDS_Shell& aShSp = *((TopoDS_Shell*)&aItLShSp.Value());
342 if (BRep_Tool::IsClosed(aShSp)) {
343 aShSp.Closed(Standard_True);
344 myLoops.Append(aShSp);
347 aLShNC.Append(aShSp);
351 bAllFacesTaken = (AddedFacesMap.Extent() == aNbShapes);
352 if (bAllFacesTaken) {
356 if (aLShSp.Extent() == 1) {
357 // not further processing of not closed shells is needed,
358 // as it will not bring any new results
362 Standard_Integer aNbShNC = aLShNC.Extent();
364 // try to complete the shell with other faces
365 aLShells.Append(aLShNC);
367 else if (aNbShNC > 1) {
368 // remove th faces of not closed shells from the map of processed faces
369 // and try to rebuild the shells using all not processed faces,
370 // because faces of one shell might be needed for building the other
371 TopTools_ListIteratorOfListOfShape aItLShNC(aLShNC);
372 for (; aItLShNC.More(); aItLShNC.Next()) {
373 TopoDS_Iterator aItNC(aItLShNC.Value());
374 for (; aItNC.More(); aItNC.Next()) {
375 AddedFacesMap.Remove(aItNC.Value());
380 } // for (; aItF.More(); aItF.Next()) {
382 //=======================================================================
383 //function : RefineShell
385 //=======================================================================
386 void RefineShell(TopoDS_Shell& theShell,
387 const TopTools_IndexedDataMapOfShapeListOfShape& theMEF,
388 TopTools_ListOfShape& theLShSp)
390 TopoDS_Iterator aIt(theShell);
395 // Find edges with more than 2 adjacent faces - branch edges -
396 // edges on which the input shell should be split
397 TopTools_MapOfShape aMEStop;
399 Standard_Integer i, aNbMEF = theMEF.Extent();
400 for (i = 1; i <= aNbMEF; ++i) {
401 const TopoDS_Edge& aE = TopoDS::Edge(theMEF.FindKey(i));
402 const TopTools_ListOfShape& aLF = theMEF(i);
403 if (aLF.Extent() > 2) {
408 // check for internal edges - count faces, in which the edge
409 // is internal, twice
410 Standard_Integer aNbF = 0;
411 TopTools_ListIteratorOfListOfShape aItLF(aLF);
412 for (; aItLF.More() && aNbF <= 2; aItLF.Next()) {
413 const TopoDS_Face& aF = TopoDS::Face(aItLF.Value());
415 TopExp_Explorer aExp(aF, TopAbs_EDGE);
416 for (; aExp.More(); aExp.Next()) {
417 const TopoDS_Shape& aEF = aExp.Current();
418 if (aEF.IsSame(aE)) {
419 if (aEF.Orientation() == TopAbs_INTERNAL) {
432 if (aMEStop.IsEmpty()) {
433 theLShSp.Append(theShell);
438 TopExp_Explorer aExp;
439 TopTools_IndexedMapOfShape aMFB;
440 TopTools_MapOfOrientedShape aMFProcessed;
441 TopTools_ListOfShape aLFP, aLFP1;
442 TopTools_ListIteratorOfListOfShape aItLF, aItLFP;
445 for (; aIt.More(); aIt.Next()) {
446 const TopoDS_Shape& aF1 = aIt.Value();
447 if (!aMFProcessed.Add(aF1)) {
457 // Trying to reach the branch point
459 aItLFP.Initialize(aLFP);
460 for (; aItLFP.More(); aItLFP.Next()) {
461 const TopoDS_Shape& aFP = aItLFP.Value();
463 aExp.Init(aFP, TopAbs_EDGE);
464 for (; aExp.More(); aExp.Next()) {
465 const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&aExp.Current()));
466 if (aMEStop.Contains(aE)) {
470 if (aE.Orientation() == TopAbs_INTERNAL) {
474 if (BRep_Tool::Degenerated(aE)) {
478 const TopTools_ListOfShape& aLF = theMEF.FindFromKey(aE);
480 aItLF.Initialize(aLF);
481 for (; aItLF.More(); aItLF.Next()) {
482 const TopoDS_Shape& aFP1 = aItLF.Value();
483 if (aFP1.IsSame(aFP)) {
486 if (aMFB.Contains(aFP1)) {
490 if (aMFProcessed.Add(aFP1)) {
494 }// for (; aItLF.More(); aItLF.Next()) {
495 }// for (; aExp.More(); aExp.Next()) {
496 } // for (; aItLFP.More(); aItLFP.Next()) {
499 if (aLFP1.IsEmpty()) {
507 Standard_Integer aNbMFB = aMFB.Extent();
510 aBB.MakeShell(aShSp);
512 for (i = 1; i <= aNbMFB; ++i) {
513 const TopoDS_Shape& aFB = aMFB(i);
516 theLShSp.Append(aShSp);
518 }//for (; aIt.More(); aIt.Next()) {
520 //=======================================================================
521 //function : MakeShells
523 //=======================================================================
524 void BOPAlgo_ShellSplitter::MakeShells()
526 Standard_Boolean bIsRegular;
527 Standard_Integer aNbVCBK, k;
528 BOPTools_ListIteratorOfListOfConnexityBlock aItCB;
529 TopTools_ListIteratorOfListOfShape aIt;
530 BOPAlgo_VectorOfCBK aVCBK;
534 aItCB.Initialize(myLCB);
535 for (; aItCB.More(); aItCB.Next()) {
536 BOPTools_ConnexityBlock& aCB=aItCB.ChangeValue();
537 bIsRegular=aCB.IsRegular();
541 const TopTools_ListOfShape& aLF=aCB.Shapes();
542 MakeShell(aLF, aShell);
543 aShell.Closed(Standard_True);
544 myShells.Append(aShell);
547 BOPAlgo_CBK& aCBK=aVCBK.Appended();
548 aCBK.SetConnexityBlock(aCB);
552 aNbVCBK=aVCBK.Length();
553 //===================================================
554 BOPTools_Parallel::Perform (myRunParallel, aVCBK);
555 //===================================================
556 for (k=0; k<aNbVCBK; ++k) {
557 BOPAlgo_CBK& aCBK=aVCBK(k);
558 const BOPTools_ConnexityBlock& aCB=aCBK.ConnexityBlock();
559 const TopTools_ListOfShape& aLS=aCB.Loops();
561 for (; aIt.More(); aIt.Next()) {
562 TopoDS_Shape& aShell=aIt.ChangeValue();
563 aShell.Closed(Standard_True);
564 myShells.Append(aShell);
568 //=======================================================================
569 //function : MakeShell
571 //=======================================================================
572 void MakeShell(const TopTools_ListOfShape& aLS,
573 TopoDS_Shell& aShell)
576 TopTools_ListIteratorOfListOfShape aIt;
578 aBB.MakeShell(aShell);
581 for (; aIt.More(); aIt.Next()) {
582 const TopoDS_Shape& aF=aIt.Value();
586 BOPTools_AlgoTools::OrientFacesOnShell(aShell);