1 // File: NMTAlgo_Splitter_1.cxx
2 // Created: Mon Feb 2 14:58:54 2004
3 // Author: Peter KURNEV
7 #include <NMTAlgo_Splitter.ixx>
8 #include <TopExp_Explorer.hxx>
9 #include <TopoDS_Shape.hxx>
10 #include <TopoDS_Compound.hxx>
11 #include <TopTools_MapOfShape.hxx>
12 #include <TopTools_DataMapOfShapeListOfShape.hxx>
13 #include <TopTools_MapIteratorOfMapOfShape.hxx>
14 #include <TopTools_ListOfShape.hxx>
15 #include <TopTools_ListIteratorOfListOfShape.hxx>
17 #include <TopoDS_Iterator.hxx>
18 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
20 #include <TopoDS_Edge.hxx>
21 #include <TopoDS_Face.hxx>
22 #include <NMTAlgo_Loop3d.hxx>
23 #include <Precision.hxx>
24 #include <BRep_Tool.hxx>
25 #include <BRepClass3d_SolidClassifier.hxx>
27 #include <TopoDS_Solid.hxx>
28 #include <NMTAlgo_Loop3d.hxx>
29 #include <TopTools_DataMapIteratorOfDataMapOfShapeShape.hxx>
31 //=======================================================================
32 //function : ShellsAndSolids
34 //=======================================================================
35 void NMTAlgo_Splitter::ShellsAndSolids()
37 Standard_Boolean bMakeSolids;
38 TopAbs_ShapeEnum aType;
39 TopTools_ListIteratorOfListOfShape aItS;
40 TopTools_ListOfShape aLNS;
42 myAddedFacesMap.Clear();
43 bMakeSolids=(myLimit==TopAbs_SHAPE || myLimit<TopAbs_SHELL);
45 aItS.Initialize(myListShapes);
46 for ( ;aItS.More(); aItS.Next()) {
47 const TopoDS_Shape& aS=aItS.Value();
49 if (myToolShapes.Contains(aS)) {
54 if (aType > TopAbs_SHELL) {
55 continue;//face,wire,...
60 MakeShells (aS, aLNS);
62 if (bMakeSolids && aType==TopAbs_SOLID) {
66 TopTools_ListIteratorOfListOfShape it (aLNS);
67 for (; it.More(); it.Next()) {
68 myBuilder.Add (myShape, it.Value());
73 aItS.Initialize(myListShapes);
74 for ( ;aItS.More(); aItS.Next()) {
75 const TopoDS_Shape& aS=aItS.Value();
78 if (aType!=TopAbs_FACE || myMapTools.Contains(aS)) {
82 const TopoDS_Shape& aCSF=myImageShape.Image(aS).First();
83 TopoDS_Iterator itS(aCSF);
84 for (; itS.More(); itS.Next()){
85 const TopoDS_Shape& aF=itS.Value();
86 if (!myAddedFacesMap.Contains(aF)){
87 myBuilder.Add (myShape, aF);
92 //=======================================================================
93 //function : MakeShells
94 //purpose : split S into compound of shells
95 //=======================================================================
96 void NMTAlgo_Splitter::MakeShells(const TopoDS_Shape& aS,
97 TopTools_ListOfShape& aLNS)
99 NMTAlgo_Loop3d aShellMaker;
101 // get compound of split faces of aS
102 const TopoDS_Shape& aFC=myImageShape.Image(aS).First();
103 aShellMaker.AddConstFaces(aFC);
105 // add split faces inside aS
106 if (myClosedShapes.Contains(aS)) {
108 // internal faces compound
109 TopoDS_Shape aIFC=FindFacesInside(aS, Standard_True);
110 aShellMaker.AddSectionFaces(aIFC);
113 aLNS=aShellMaker.MakeShells(myAddedFacesMap);
115 // Add faces added to new shell to myAddedFacesMap:
116 // avoid rebuilding twice common part of 2 solids.
118 TopTools_ListIteratorOfListOfShape itS(aLNS);
119 TopExp_Explorer expF;
120 for (; itS.More(); itS.Next()) {
121 const TopoDS_Shape& aSh=itS.Value();
122 expF.Init (aSh, TopAbs_FACE);
123 for (; expF.More(); expF.Next()){
124 myAddedFacesMap.Add (expF.Current());
129 //=======================================================================
130 //function : MakeSolids
131 //purpose : make solids out of Shells
132 //=======================================================================
133 void NMTAlgo_Splitter::MakeSolids(const TopoDS_Shape& theSolid,
134 TopTools_ListOfShape& theShellList)
136 // for a solid wrapping other shells or solids without intersection,
137 // it is necessary to find shells making holes in it
138 Standard_Boolean isWrapping;
139 TopTools_ListOfShape aNewSolids; // result
140 TopTools_ListOfShape aHoleShells;
141 TopoDS_Shape anInfinitePointShape;
142 TopTools_DataMapOfShapeShape aInOutMap;
143 TopTools_ListIteratorOfListOfShape aShellIt, aSolisIt;
145 isWrapping = myWrappingSolid.Contains(theSolid);
146 if (!isWrapping && !theShellList.IsEmpty()) {
147 // check if theSolid initially has internal shells
148 TopoDS_Iterator aShellExp (theSolid);
150 isWrapping = aShellExp.More();
153 aShellIt.Initialize(theShellList);
154 for ( ; aShellIt.More(); aShellIt.Next()) {
155 const TopoDS_Shape & aShell = aShellIt.Value();
156 // check if a shell is a hole of theSolid
157 if (isWrapping && IsInside(anInfinitePointShape, aShell)){
158 aHoleShells.Append(aShell);
161 // make a solid from a shell
163 myBuilder.MakeSolid( Solid );
164 myBuilder.Add (Solid, aShell);
166 aNewSolids.Append (Solid);
170 // find outer a shell most close to each hole shell
171 aShellIt.Initialize(aHoleShells);
172 for (; aShellIt.More(); aShellIt.Next()){
173 const TopoDS_Shape & aHole = aShellIt.Value();
175 aSolisIt.Initialize(aNewSolids);
176 for ( ; aSolisIt.More(); aSolisIt.Next()) {
177 const TopoDS_Shape & aSolid = aSolisIt.Value();
179 if (! IsInside(aHole, aSolid)){
183 if ( aInOutMap.IsBound (aHole)){
184 const TopoDS_Shape & aSolid2 = aInOutMap( aHole );
185 if ( IsInside( aSolid, aSolid2 )) {
186 aInOutMap.UnBind( aHole );
187 aInOutMap.Bind ( aHole, aSolid );
191 aInOutMap.Bind (aHole, aSolid);
195 // add aHole to a solid
196 if (aInOutMap.IsBound( aHole )){
197 TopoDS_Shape & aSolid=aInOutMap(aHole);
198 myBuilder.Add (aSolid, aHole);
201 theShellList.Clear();
202 theShellList.Append( aNewSolids );
205 //=======================================================================
206 //function : FindFacesInside
207 //purpose : return compound of faces of other shapes that are
208 // inside <theShape>.
209 // <theShape> is an object shape.
210 // <CheckClosed> makes avoid faces that do not form a
212 // <All> makes return already added faces
213 //=======================================================================
214 TopoDS_Shape NMTAlgo_Splitter::FindFacesInside(const TopoDS_Shape& theShape,
215 const Standard_Boolean CheckClosed,
216 const Standard_Boolean All)
218 TopExp_Explorer expl;
220 // ================================================
221 // check if internal faces have been already found
222 // ================================================
223 if (myInternalFaces.IsBound(theShape)) {
224 TopoDS_Shape aIntFComp = myInternalFaces.Find (theShape);
225 TopoDS_Shape aIntRemFComp = myIntNotClFaces.Find (theShape);
227 expl.Init( aIntRemFComp, TopAbs_FACE);
228 if (CheckClosed || !expl.More()){
233 myBuilder.MakeCompound( C );
235 for (; expl.More(); expl.Next()){
236 myBuilder.Add( C, expl.Current() );
238 // add good internal faces
239 expl.Init( aIntFComp, TopAbs_FACE);
240 for (; expl.More(); expl.Next()) {
241 myBuilder.Add( C, expl.Current() );
247 // ===================================
248 // get data for internal faces search
249 // ===================================
251 // compound of split faces of theShape
252 const TopoDS_Shape& CSF = myImageShape.Image(theShape).First();
254 TopTools_MapOfShape MSE, MFP;
255 TopTools_DataMapOfShapeListOfShape DMSEFP;
256 TopTools_MapIteratorOfMapOfShape itm;
257 TopTools_ListOfShape EmptyL;
258 TopTools_ListIteratorOfListOfShape itl;
260 // MSE filling: map of new section edges of CSF
261 expl.Init(CSF, TopAbs_EDGE);
262 for (; expl.More(); expl.Next()) {
263 const TopoDS_Shape& aE = expl.Current() ;
267 // DMEF: map edge of CSF - faces of CSF
268 TopTools_IndexedDataMapOfShapeListOfShape DMEF;
269 TopExp::MapShapesAndAncestors(CSF, TopAbs_EDGE, TopAbs_FACE, DMEF);
272 // 1. MFP - a map of faces to process: map of resulting faces except
273 // those of theShape; we`ll add to C those of them which are inside CSF
274 // 2. DMSEFP - edge of MSE => faces of MFP
276 itl.Initialize(myListShapes);
277 for (;itl.More(); itl.Next()) {
278 const TopoDS_Shape& aShape = itl.Value();
280 if ( theShape.IsSame(aShape)) {
284 // iterate on split faces of aShape
285 const TopoDS_Shape& CSF1 = myImageShape.Image(aShape).First();
286 TopoDS_Iterator itF (CSF1);
287 for ( ; itF.More(); itF.Next()) {
288 const TopoDS_Shape& aF1 = itF.Value();
290 // iterate on edges of split faces of aShape,
291 // add to DMSEFP edges that are new
292 expl.Init(aF1, TopAbs_EDGE);
293 for (; expl.More(); expl.Next()) {
294 TopoDS_Shape aE1 = expl.Current();
295 if ( MSE.Contains(aE1)) {// section edge
296 if (!DMSEFP.IsBound(aE1)) {
297 DMSEFP.Bind(aE1, EmptyL);
299 DMSEFP(aE1).Append(aF1);
303 }//for (;itl.More(); itl.Next())
305 // add tool faces... (is absent)
307 // ===========================
308 // find faces inside theShape
309 // ===========================
310 Standard_Boolean skipAlreadyAdded = Standard_False;
311 Standard_Boolean GoodOri, inside;
313 TopTools_ListOfShape KeepFaces;
314 TopTools_DataMapIteratorOfDataMapOfShapeListOfShape Mapit;
316 // iterate on section edges, check faces of other shapes
317 // sharing section edges and put internal faces to KeepFaces
318 Mapit.Initialize(DMSEFP);
319 for (; Mapit.More() ; Mapit.Next() ) {
320 // a new edge of theShape
321 const TopoDS_Edge& E = TopoDS::Edge (Mapit.Key());
322 // an original edge of which E is a split
323 //const TopoDS_Edge& OrigE = TopoDS::Edge (myImagesEdges.Root(E));
324 // does OrigE itself splits a face
325 Standard_Boolean isSectionE=IsSectionEdge(E);//(OrigE);
327 // split faces of other shapes sharing E
328 TopTools_ListOfShape& LSF = DMSEFP.ChangeFind(E);
329 itl.Initialize( LSF );
331 // a split faces of other shape
332 TopoDS_Face aFace1 = TopoDS::Face(itl.Value());
333 // remove aFace1 form DMSEFP and MFP
334 LSF.Remove( itl ); // == itl.Next();
335 if (!MFP.Remove( aFace1 ))
336 continue; // was not is MFP ( i.e already checked)
337 // check if aFace1 was already added to 2 shells
339 myAddedFacesMap.Contains(aFace1) &&
340 myAddedFacesMap.Contains(aFace1.Reversed())) {
341 skipAlreadyAdded = Standard_True;
342 //modified by NIZNHY-PKV Wed Feb 11 16:11:53 2004 f
344 //modified by NIZNHY-PKV Wed Feb 11 16:35:48 2004 t
347 // find another face which originates from the same face as aFace1:
348 // usually aFace2 is internal if aFace1 is not and vice versa
349 TopoDS_Shape anOrigFace = aFace1;
350 if (myImagesFaces.IsImage(aFace1)){
351 anOrigFace = myImagesFaces.Root(aFace1);
357 aFace2 = itl.Value();
359 TopoDS_Shape anOrigFace2 = aFace2;
360 if (myImagesFaces.IsImage(aFace2)) {
361 anOrigFace2 = myImagesFaces.Root(aFace2);
364 if (!MFP.Contains( aFace2 )) {
368 //if (anOrigFace.IsSame( myImagesFaces.Root( aFace2 )))
369 if (anOrigFace.IsSame(anOrigFace2)) {
374 if (itl.More()) { // aFace2 found, remove it from maps
381 itl.Initialize( LSF );
384 // check that anOrigFace is not same domain with CSF faces it intersects
386 const TopTools_ListOfShape& FL = DMEF.FindFromKey(E); //faces of CSF sharing E
388 const TopoDS_Shape& origF1 = myImagesFaces.IsImage(FL.First()) ?
389 myImagesFaces.Root(FL.First()) : FL.First();
390 const TopoDS_Shape& origF2 = myImagesFaces.IsImage(FL.Last()) ?
391 myImagesFaces.Root(FL.Last()) : FL.Last();
393 Standard_Boolean sameDom1 = anOrigFace.IsSame( origF1 );
394 Standard_Boolean sameDom2 = anOrigFace.IsSame( origF2 );
396 if (!(sameDom1 || sameDom2) && HasSameDomainF( TopoDS::Face(anOrigFace) )) {
397 sameDom1 = IsSameDomainF( TopoDS::Face(anOrigFace), TopoDS::Face(origF1));
398 if (origF1 == origF2) {
402 IsSameDomainF( TopoDS::Face(anOrigFace), TopoDS::Face(origF2));
405 if (sameDom1 && sameDom2){
408 if (sameDom1 || sameDom2) {
409 inside = NMTAlgo_Loop3d::IsInside (E,
410 TopoDS::Face(FL.First()),
411 TopoDS::Face(FL.Last()),
413 if (inside || (dot + Precision::Angular() >= 1.0))
414 continue; // E is convex between origF1 and origF2 or they are tangent
417 // keep one of found faces
419 //face of CSF sharing E
420 const TopoDS_Shape& aShapeFace = sameDom1 ? FL.Last() : FL.First();
421 // analyse aFace1 state
422 inside = NMTAlgo_Loop3d::IsInside (E, TopoDS::Face(aShapeFace), aFace1,
424 // if (inside && isSectionE) {
425 if (inside) { //IFV 27.08.04
426 // aFace1 must be tested with both adjacent faces of CSF
427 const TopoDS_Shape& aShapeFace2 = sameDom1 ? FL.First() : FL.Last();
428 if (aShapeFace2 != aShapeFace){
429 inside = NMTAlgo_Loop3d::IsInside (E, TopoDS::Face(aShapeFace2), aFace1,
434 // store internal face
436 KeepFaces.Append(aFace1);
438 else if (!aFace2.IsNull()) {
439 if (dot + Precision::Angular() >= 1.0) {
440 // aFace2 state is not clear, it will be analysed alone,
441 // put it back to the maps
443 LSF.Append( aFace2 );
446 KeepFaces.Append(aFace2);
451 // ===================================================
452 // add not distributed faces connected with KeepFaces
453 // ===================================================
455 // ultimate list of internal faces
456 TopTools_ListOfShape KeptFaces;
458 // add to MFP not split tool faces as well, they may be connected with
459 // tool faces interfering with theShape
461 itm.Initialize(myMapTools);
462 for (; itm.More(); itm.Next() ) {
463 const TopoDS_Shape& aToolFace = itm.Key();
464 if (!myImageShape.HasImage(aToolFace)){
471 KeptFaces.Append (KeepFaces);
473 while (!KeepFaces.IsEmpty()) {
474 // KeepEdges : map of edges of faces kept last time
475 TopTools_IndexedMapOfShape KeepEdges;
476 for ( itl.Initialize(KeepFaces); itl.More(); itl.Next() ) {
477 TopExp::MapShapes( itl.Value(), TopAbs_EDGE, KeepEdges);
478 KeptFaces.Append( itl.Value() );
483 // keep faces connected with already kept faces by KeepEdges
484 for ( itm.Initialize(MFP); itm.More(); itm.Next() ) {
485 const TopoDS_Shape& FP = itm.Key();
486 for (expl.Init(FP,TopAbs_EDGE); expl.More(); expl.Next()) {
487 const TopoDS_Shape& se = expl.Current();
488 if (!MSE.Contains(se) && KeepEdges.Contains(se) ) {
489 KeepFaces.Append(FP);
497 // ===============================================================
498 // here MFP contains faces outer of theShape and those of shapes
499 // which do not interfere with theShape at all and between which
500 // there may be those wrapped by theShape and whose faces may be
501 // needed to be returned as well
502 // ===============================================================
504 Standard_Boolean isSolid = (theShape.ShapeType() == TopAbs_SOLID);
505 if (All || isSolid) // All is for sub-result removal
507 for ( itm.Initialize( MFP ); itm.More(); itm.Next() ) {
508 TopoDS_Shape aFace = itm.Key();
510 // find a shape aFace originates from
511 TopoDS_Shape anOrigShape = GetOriginalShape( aFace );
513 // find out if all faces of anOrigShape are not in MFP
514 // and by the way remove them from MFP
515 Standard_Boolean isAllOut = Standard_True;
516 TopoDS_Shape aSplitFaces = anOrigShape;
517 if (myImageShape.HasImage(anOrigShape))
518 aSplitFaces = myImageShape.Image(anOrigShape).First();
520 TopTools_ListOfShape aSplitFaceL;
521 for (expl.Init( aSplitFaces, TopAbs_FACE ); expl.More(); expl.Next())
523 const TopoDS_Shape & aSpFace = expl.Current();
524 // a tool face which become object has image but the whole tool shape has not
525 if (myImageShape.HasImage( aSpFace ))
527 TopExp_Explorer exF (myImageShape.Image( aSpFace ).First(), TopAbs_FACE );
528 for ( ; exF.More(); exF.Next() )
530 aSplitFaceL.Append( exF.Current() );
531 if ( ! MFP.Remove( exF.Current() ))
532 isAllOut = Standard_False;
537 aSplitFaceL.Append( aSpFace );
538 if ( ! MFP.Remove( aSpFace ))
539 isAllOut = Standard_False;
542 itm.Initialize( MFP );
546 // classify anOrigShape against theShape
547 if (IsInside (anOrigShape, theShape)) {
548 if (isSolid && myClosedShapes.Contains(anOrigShape)) {
549 // to make a special care at solid reconstruction
550 myWrappingSolid.Add ( theShape );
552 // keep faces of an internal shape anOrigShape
553 KeptFaces.Append( aSplitFaceL );
558 // ====================================================
559 // check if kept faces form a shell without free edges
560 // ====================================================
562 DMEF.Clear(); // edge - kept faces
563 MFP.Clear(); // reuse it for wrong faces
565 for (itl.Initialize(KeptFaces); itl.More(); itl.Next() )
566 TopExp::MapShapesAndAncestors(itl.Value(), TopAbs_EDGE, TopAbs_FACE, DMEF);
568 Standard_Integer i, nb = DMEF.Extent();
569 Standard_Boolean isClosed = Standard_False;
571 isClosed = Standard_True;
572 for (i=1; isClosed && i<=nb; ++i) {
573 const TopoDS_Shape& E = DMEF.FindKey( i );
574 if (! BRep_Tool::Degenerated( TopoDS::Edge( E )) &&
576 isClosed = ( DMEF(i).Extent() != 1 );
579 const TopoDS_Shape& F = DMEF.FindFromIndex( i-1 ).First(); // bad face
581 // remove bad face from DMEF
582 for (expl.Init( F, TopAbs_EDGE); expl.More(); expl.Next()) {
583 const TopoDS_Shape& E = expl.Current();
584 TopTools_ListOfShape& FL = DMEF.ChangeFromKey( E );
585 for (itl.Initialize( FL ); itl.More(); itl.Next() ) {
586 if ( F.IsSame( itl.Value() )) {
601 // compound of removed internal faces
602 TopoDS_Compound CNotCl;
604 myBuilder.MakeCompound(C);
605 myBuilder.MakeCompound(CNotCl);
608 itl.Initialize(KeptFaces);
609 for (; itl.More(); itl.Next() ) {
610 TopoDS_Shape & aIntFace = itl.Value();
613 myAddedFacesMap.Contains(aIntFace) &&
614 myAddedFacesMap.Contains(aIntFace.Reversed())) {
618 if (! MFP.Contains( aIntFace )){
619 myBuilder.Add(C, aIntFace);
622 myBuilder.Add(CNotCl, aIntFace);
626 if (!skipAlreadyAdded && CheckClosed) {
627 myInternalFaces.Bind(theShape, C);
628 myIntNotClFaces.Bind(theShape, CNotCl);
632 if (!myMapSIFC.IsBound(theShape)) {
633 TopoDS_Compound aCIF;
634 myBuilder.MakeCompound(aCIF);
636 itl.Initialize(KeptFaces);
637 for (; itl.More(); itl.Next() ) {
638 TopoDS_Shape & aIntFace = itl.Value();
639 if (! MFP.Contains(aIntFace )){
640 myBuilder.Add(aCIF, aIntFace);
643 myMapSIFC.Bind(theShape, aCIF);
648 //=======================================================================
649 //function : IsInside
650 //purpose : Return True if the first vertex of S1 inside S2.
651 // If S1.IsNull(), check infinite point against S2.
652 //=======================================================================
653 Standard_Boolean NMTAlgo_Splitter::IsInside (const TopoDS_Shape& theS1,
654 const TopoDS_Shape& theS2)
656 BRepClass3d_SolidClassifier aClassifier( theS2 );
658 TopExp_Explorer expl(theS1, TopAbs_VERTEX);
661 aClassifier.PerformInfinitePoint( ::RealSmall());
664 const TopoDS_Vertex & aVertex = TopoDS::Vertex( expl.Current() );
665 aClassifier.Perform (BRep_Tool::Pnt( aVertex ),
666 BRep_Tool::Tolerance( aVertex ));
669 return ( aClassifier.State() == TopAbs_IN );
672 //=======================================================================
673 //function : GetOriginalShape
674 //purpose : Return the shape aShape originates from. aShape
675 // should be a face or more complex result shape
676 //=======================================================================
677 TopoDS_Shape NMTAlgo_Splitter::GetOriginalShape(const TopoDS_Shape& theShape) const
679 TopoDS_Shape anOrigShape;
681 TopExp_Explorer expl( theShape, TopAbs_FACE);
683 TopoDS_Shape aFace = expl.Current();
684 if (myImagesFaces.IsImage( aFace ))
685 aFace = myImagesFaces.Root( aFace );
686 anOrigShape = myFaceShapeMap.Find( aFace );