1 // Created on: 1995-12-12
2 // Created by: Jacques GOUSSARD
3 // Copyright (c) 1995-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
6 // This file is part of Open CASCADE Technology software library.
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
17 #include <BRepCheck_Shell.hxx>
19 #include <BRep_Builder.hxx>
20 #include <BRep_Tool.hxx>
21 #include <BRepCheck.hxx>
22 #include <BRepCheck_ListOfStatus.hxx>
23 #include <Standard_Type.hxx>
25 #include <TopExp_Explorer.hxx>
27 #include <TopoDS_Edge.hxx>
28 #include <TopoDS_Face.hxx>
29 #include <TopoDS_Shape.hxx>
30 #include <TopoDS_Shell.hxx>
31 #include <TopTools_DataMapOfShapeInteger.hxx>
32 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
33 #include <TopTools_ListOfShape.hxx>
34 #include <TopTools_MapOfShape.hxx>
36 IMPLEMENT_STANDARD_RTTIEXT(BRepCheck_Shell,BRepCheck_Result)
38 //=======================================================================
39 //function : Propagate
41 //=======================================================================
42 static void Propagate(const TopTools_IndexedDataMapOfShapeListOfShape& mapEF,
43 const TopoDS_Shape& theFace,
44 TopTools_IndexedMapOfShape& theMapF)
46 // Base for the traverse procedure.
49 // Perform well-known width-first traverse.
50 for (Standard_Integer anIdx = 1; anIdx <= theMapF.Extent(); ++anIdx)
52 const TopoDS_Shape& aFace = theMapF(anIdx);
53 for (TopExp_Explorer ex(aFace, TopAbs_EDGE); ex.More(); ex.Next())
55 const TopoDS_Edge& edg = TopoDS::Edge(ex.Current());
57 // Test if the edge is in the map (only oriented edges are present).
58 const TopTools_ListOfShape* aList = mapEF.Seek(edg);
63 for (TopTools_ListIteratorOfListOfShape itl(*aList); itl.More(); itl.Next())
65 // This code assumes that shape is added to an end of the map.
66 // The idea is simple: existing objects will not be added, new objects
67 // will be added to an end.
68 theMapF.Add(itl.Value());
74 //=======================================================================
75 //function : BRepCheck_Trace
77 //=======================================================================
78 Standard_EXPORT Standard_Integer BRepCheck_Trace(const Standard_Integer phase) {
79 static int BRC_Trace = 0;
80 if (phase < 0) BRC_Trace =0;
81 else if (phase > 0) BRC_Trace=phase;
85 void PrintShape(const TopoDS_Shape& theShape) {
86 if (!theShape.IsNull()) {
87 size_t code = TopTools_ShapeMapHasher{}(theShape);
88 std::cout << TopAbs::ShapeTypeToString (theShape.ShapeType()) << " : " << code
89 << " " << TopAbs::ShapeOrientationToString(theShape.Orientation()) << std::endl;
93 //=======================================================================
94 //function : IsOriented
96 //=======================================================================
97 inline Standard_Boolean IsOriented(const TopoDS_Shape& S)
99 return (S.Orientation() == TopAbs_FORWARD ||
100 S.Orientation() == TopAbs_REVERSED);
104 //=======================================================================
105 //function : BRepCheck_Shell
107 //=======================================================================
109 BRepCheck_Shell::BRepCheck_Shell(const TopoDS_Shell& S)
111 myCdone(Standard_False),
112 myCstat(BRepCheck_NoError),
113 myOdone(Standard_False),
114 myOstat(BRepCheck_NoError)
120 //=======================================================================
123 //=======================================================================
124 void BRepCheck_Shell::Minimum()
126 myCdone = Standard_False;
127 myOdone = Standard_False;
131 Handle(BRepCheck_HListOfStatus) aNewList = new BRepCheck_HListOfStatus();
132 BRepCheck_ListOfStatus& lst = **myMap.Bound(myShape, aNewList);
134 // it is checked if the shell is "connected"
135 TopExp_Explorer exp(myShape,TopAbs_FACE);
136 Standard_Integer nbface = 0;
138 for (; exp.More(); exp.Next())
141 TopExp_Explorer expe;
142 for (expe.Init(exp.Current(),TopAbs_EDGE);
143 expe.More(); expe.Next())
145 const TopoDS_Shape& edg = expe.Current();
146 Standard_Integer index = myMapEF.FindIndex(edg);
149 TopTools_ListOfShape thelist1;
150 index = myMapEF.Add(edg, thelist1);
153 myMapEF(index).Append(exp.Current());
155 }//for (; exp.More(); exp.Next())
159 BRepCheck::Add(lst,BRepCheck_EmptyShell);
161 else if (nbface >= 2)
163 TopTools_IndexedMapOfShape mapF;
166 Propagate(myMapEF,exp.Current(),mapF);
168 if (mapF.Extent() != nbface)
170 BRepCheck::Add(lst,BRepCheck_NotConnected);
172 }//else if (nbface >= 2)
176 lst.Append(BRepCheck_NoError);
180 myMin = Standard_True;
184 //=======================================================================
185 //function : InContext
187 //=======================================================================
189 void BRepCheck_Shell::InContext(const TopoDS_Shape& S)
191 Handle(BRepCheck_HListOfStatus) aHList;
193 Standard_Mutex::Sentry aLock(myMutex.get());
194 if (myMap.IsBound (S))
198 Handle(BRepCheck_HListOfStatus) aNewList = new BRepCheck_HListOfStatus();
199 aHList = *myMap.Bound(S, aNewList);
201 BRepCheck_ListOfStatus& lst = *aHList;
203 // for (TopExp_Explorer exp(S,TopAbs_SHELL); exp.More(); exp.Next()) {
204 TopExp_Explorer exp(S, TopAbs_SHELL);
205 for (; exp.More(); exp.Next()) {
206 if (exp.Current().IsSame(myShape)) {
211 BRepCheck::Add(lst,BRepCheck_SubshapeNotInShape);
215 TopAbs_ShapeEnum styp = S.ShapeType();
220 BRepCheck_Status fst = Closed();
221 if ((fst == BRepCheck_NotClosed && S.Closed()) ||
222 (fst != BRepCheck_NoError)) {
223 BRepCheck::Add(lst,fst);
225 else if (!IsUnorientable()) {
227 BRepCheck::Add(lst,fst);
238 lst.Append(BRepCheck_NoError);
243 //=======================================================================
246 //=======================================================================
248 void BRepCheck_Shell::Blind()
251 // nothing more than in the minimum
252 myBlind = Standard_True;
257 //=======================================================================
260 //=======================================================================
261 BRepCheck_Status BRepCheck_Shell::Closed(const Standard_Boolean Update)
263 Handle(BRepCheck_HListOfStatus) aHList;
265 Standard_Mutex::Sentry aLock(myMutex.get());
266 aHList = myMap (myShape);
269 BRepCheck_ListOfStatus& aStatusList = *aHList;
274 BRepCheck::Add (aStatusList, myCstat);
280 myCdone = Standard_True; // it will be done...
282 BRepCheck_ListIteratorOfListOfStatus itl (aStatusList);
283 if (itl.Value() != BRepCheck_NoError)
285 myCstat = itl.Value();
286 return myCstat; // already saved
289 myCstat = BRepCheck_NoError;
291 Standard_Integer index, aNbF;
292 TopExp_Explorer exp, ede;
293 TopTools_IndexedMapOfShape mapS;
294 TopTools_MapOfShape aMEToAvoid;
298 // Checks if the oriented faces of the shell give a "closed" shell,
299 // i-e if each oriented edge on oriented faces is found 2 times.
301 //modified by NIZNHY-PKV Mon Jun 4 13:59:21 2007f
302 exp.Init(myShape,TopAbs_FACE);
303 for (; exp.More(); exp.Next())
305 const TopoDS_Shape& aF=exp.Current();
308 ede.Init(exp.Current(),TopAbs_EDGE);
309 for (; ede.More(); ede.Next())
311 const TopoDS_Shape& aE=ede.Current();
319 //modified by NIZNHY-PKV Mon Jun 4 13:59:23 2007t
321 exp.Init(myShape,TopAbs_FACE);
322 for (; exp.More(); exp.Next())
324 const TopoDS_Shape& aF=exp.Current();
329 myCstat = BRepCheck_RedundantFace;
333 BRepCheck::Add (aStatusList, myCstat);
340 ede.Init(exp.Current(),TopAbs_EDGE);
341 for (; ede.More(); ede.Next())
343 const TopoDS_Shape& aE=ede.Current();
344 //modified by NIZNHY-PKV Mon Jun 4 14:07:57 2007f
345 //if (IsOriented(aE)) {
346 if (!aMEToAvoid.Contains(aE))
348 //modified by NIZNHY-PKV Mon Jun 4 14:08:01 2007
349 index = myMapEF.FindIndex(aE);
353 TopTools_ListOfShape thelist;
354 index = myMapEF.Add(aE, thelist);
357 myMapEF(index).Append(aF);
364 myNbori = mapS.Extent();
368 // Search for the first oriented face
370 exp.Init(myShape, TopAbs_FACE);
371 for (;exp.More(); exp.Next())
380 Propagate(myMapEF, aF, mapS);
388 myCstat = BRepCheck_NotConnected;
391 BRepCheck::Add (aStatusList, myCstat);
397 Standard_Integer i, Nbedges, nboc, nbSet;
399 Nbedges = myMapEF.Extent();
400 for (i = 1; i<=Nbedges; ++i)
402 nboc = myMapEF(i).Extent();
403 if (nboc == 0 || nboc >= 3)
405 TopTools_ListOfShape theSet;
406 nbSet=NbConnectedSet(theSet);
407 // If there is more than one closed cavity the shell is considered invalid
408 // this corresponds to the criteria of a solid (not those of a shell)
411 myCstat = BRepCheck_InvalidMultiConnexity;
414 BRepCheck::Add (aStatusList, myCstat);
422 if (!BRep_Tool::Degenerated(TopoDS::Edge(myMapEF.FindKey(i))))
424 myCstat=BRepCheck_NotClosed;
427 BRepCheck::Add (aStatusList ,myCstat);
436 BRepCheck::Add (aStatusList, myCstat);
442 //=======================================================================
443 //function : Orientation
445 //=======================================================================
446 BRepCheck_Status BRepCheck_Shell::Orientation(const Standard_Boolean Update)
448 Handle(BRepCheck_HListOfStatus) aHList;
450 Standard_Mutex::Sentry aLock(myMutex.get());
451 aHList = myMap (myShape);
453 BRepCheck_ListOfStatus& aStatusList = *aHList;
457 BRepCheck::Add (aStatusList, myOstat);
461 myOdone = Standard_True;
464 if (myOstat != BRepCheck_NotClosed && myOstat != BRepCheck_NoError) {
466 BRepCheck::Add (aStatusList, myOstat);
471 myOstat = BRepCheck_NoError;
474 // First the orientation of each face in relation to the shell is found.
475 // It is used to check BRepCheck_RedundantFace
477 TopTools_DataMapOfShapeInteger MapOfShapeOrientation;
478 TopExp_Explorer exp,ede;
480 for (exp.Init(myShape,TopAbs_FACE); exp.More(); exp.Next()) {
481 if (!MapOfShapeOrientation.Bind(exp.Current(), (Standard_Integer)(exp.Current().Orientation()))) {
482 myOstat = BRepCheck_RedundantFace;
484 BRepCheck::Add (aStatusList, myOstat);
493 if (BRepCheck_Trace(0) > 1) {
494 TopTools_DataMapIteratorOfDataMapOfShapeInteger itt(MapOfShapeOrientation);
495 std::cout << "La map shape Orientation :" << std::endl;
496 for (; itt.More(); itt.Next()) {
497 PrintShape(itt.Key());
499 std::cout << std::endl;
504 // Then the orientation of faces by their connectivity is checked
505 // BRepCheck_BadOrientationOfSubshape and
506 // BRepCheck_SubshapeNotInShape are checked;
508 Standard_Integer Nbedges = myMapEF.Extent();
510 TopAbs_Orientation orf;
512 for (Standard_Integer i = 1; i<= Nbedges; i++) {
514 const TopoDS_Edge& edg = TopoDS::Edge(myMapEF.FindKey(i));
515 if (BRep_Tool::Degenerated(edg)) continue;
516 TopTools_ListOfShape& lface = myMapEF(i);
517 TopTools_ListIteratorOfListOfShape lite(lface);
519 if (lface.Extent() <= 2)
521 lite.Initialize(lface);
522 Fref = TopoDS::Face(lite.Value());
524 if (!MapOfShapeOrientation.IsBound(Fref))
526 myOstat = BRepCheck_SubshapeNotInShape;
529 BRepCheck::Add (aStatusList, myOstat);
531 // quit because no workaround for the incoherence is possible
536 if (lite.More()) // Edge of connectivity
539 Standard_Integer iorf = MapOfShapeOrientation.Find(Fref);
540 orf = (TopAbs_Orientation) iorf;
541 //orf = (TopAbs_Orientation)MapOfShapeOrientation.Find(Fref);
542 Fref.Orientation(orf);
545 if (!lite.Value().IsSame(Fref)) // edge non "closed"
547 for (ede.Init(Fref,TopAbs_EDGE); ede.More(); ede.Next())
549 if (ede.Current().IsSame(edg))
554 TopAbs_Orientation orient = ede.Current().Orientation();
555 TopoDS_Face Fcur = TopoDS::Face(lite.Value());
556 if (!MapOfShapeOrientation.IsBound(Fcur))
558 myOstat = BRepCheck_SubshapeNotInShape;
561 BRepCheck::Add (aStatusList, myOstat);
563 // quit because no workaround for the incoherence is possible
568 Standard_Integer anOriFCur = MapOfShapeOrientation.Find(Fcur);
569 orf = (TopAbs_Orientation)anOriFCur;
570 // orf = (TopAbs_Orientation)MapOfShapeOrientation.Find(Fcur);
571 Fcur.Orientation(orf);
573 for (ede.Init(Fcur, TopAbs_EDGE); ede.More(); ede.Next())
575 if (ede.Current().IsSame(edg))
580 if (ede.Current().Orientation() == orient)
582 // The loop is continued on the edges as many times
583 // as the same edge is present in the wire
585 // modified by NIZHNY-MKK Tue Sep 30 11:11:42 2003
586 Standard_Boolean bfound = Standard_False;
588 for (; ede.More(); ede.Next())
590 if (ede.Current().IsSame(edg))
592 // modified by NIZHNY-MKK Tue Sep 30 11:12:03 2003
593 bfound = Standard_True;
597 // if (ede.Current().Orientation() == orient) {
598 // modified by NIZHNY-MKK Thu Oct 2 17:56:47 2003
599 if (!bfound || (ede.Current().Orientation() == orient))
601 myOstat = BRepCheck_BadOrientationOfSubshape;
604 BRepCheck::Add (aStatusList, myOstat);
613 else //more than two faces
615 Standard_Integer numF = 0, numR = 0;
616 TopTools_MapOfShape Fmap;
618 for (lite.Initialize(lface); lite.More(); lite.Next())
620 TopoDS_Face Fcur= TopoDS::Face(lite.Value());
621 if (!MapOfShapeOrientation.IsBound(Fcur))
623 myOstat = BRepCheck_SubshapeNotInShape;
626 BRepCheck::Add (aStatusList, myOstat);
628 // quit because no workaround for the incoherence is possible
632 Standard_Integer iorf = MapOfShapeOrientation.Find(Fcur);
633 orf = (TopAbs_Orientation) iorf;
634 //orf = (TopAbs_Orientation)MapOfShapeOrientation.Find(Fcur);
635 Fcur.Orientation(orf);
637 for (ede.Init(Fcur,TopAbs_EDGE); ede.More(); ede.Next())
638 if (ede.Current().IsSame(edg))
642 if (Fmap.Contains(Fcur)) //edge is "closed" on Fcur, we meet Fcur twice
645 for (; ede.More(); ede.Next())
647 if (ede.Current().IsSame(edg))
653 TopAbs_Orientation orient = ede.Current().Orientation();
654 if (orient == TopAbs_FORWARD)
668 myOstat = BRepCheck_BadOrientationOfSubshape;
671 BRepCheck::Add (aStatusList, myOstat);
679 // If at least one incorrectly oriented face has been found, it is checked if the shell can be oriented.
680 // i.e. : if by modification of the orientation of a face it is possible to find
681 // a coherent orientation. (it is not possible on a Moebius band)
682 // BRepCheck_UnorientableShape is checked
684 if (myOstat == BRepCheck_BadOrientationOfSubshape)
690 TopTools_MapOfShape alre;
691 TopTools_ListOfShape voisin;
692 voisin.Append (Fref);
694 while (!voisin.IsEmpty())
696 Fref=TopoDS::Face (voisin.First());
697 voisin.RemoveFirst();
698 if (!MapOfShapeOrientation.IsBound (Fref))
700 myOstat = BRepCheck_SubshapeNotInShape;
703 BRepCheck::Add (aStatusList, myOstat);
705 // quit because no workaround for the incoherence is possible
709 Standard_Integer iorf = MapOfShapeOrientation.Find(Fref) ;
710 orf = (TopAbs_Orientation) iorf ;
711 // orf = (TopAbs_Orientation)MapOfShapeOrientation.Find(Fref);
712 Fref.Orientation(orf);
715 if (BRepCheck_Trace(0) > 3)
717 std::cout << "Fref : " ;
722 TopExp_Explorer edFcur;
725 for (ede.Init(Fref,TopAbs_EDGE); ede.More(); ede.Next())
727 const TopoDS_Edge& edg = TopoDS::Edge (ede.Current());
728 TopAbs_Orientation orient = edg.Orientation();
729 TopTools_ListOfShape& lface = myMapEF.ChangeFromKey (edg);
730 TopTools_ListIteratorOfListOfShape lite (lface);
732 TopoDS_Face Fcur = TopoDS::Face (lite.Value());
733 if (Fcur.IsSame(Fref))
738 Fcur = TopoDS::Face (lite.Value());
742 // from the free border one goes to the next edge
747 if (!MapOfShapeOrientation.IsBound(Fcur))
749 myOstat = BRepCheck_SubshapeNotInShape;
752 BRepCheck::Add (aStatusList, myOstat);
754 // quit because no workaround for the incoherence is possible
759 Standard_Integer anOriFCur = MapOfShapeOrientation.Find(Fcur) ;
760 orf = (TopAbs_Orientation)anOriFCur;
761 // orf = (TopAbs_Orientation)MapOfShapeOrientation.Find(Fcur);
762 Fcur.Orientation(orf);
765 if (BRepCheck_Trace(0) > 3)
767 std::cout << " Fcur : " ;
771 for (edFcur.Init(Fcur, TopAbs_EDGE); edFcur.More(); edFcur.Next())
773 if (edFcur.Current().IsSame(edg))
778 if (edFcur.Current().Orientation() == orient)
780 if (alre.Contains(Fcur))
782 // It is necessary to return a face that has been already examined or returned
783 // if one gets nowhere, the shell cannot be oriented.
784 myOstat = BRepCheck_UnorientableShape;
787 BRepCheck::Add (aStatusList, myOstat);
789 // quit, otherwise there is a risk of taking too much time.
791 if (BRepCheck_Trace(0) > 3) {
792 orf = (TopAbs_Orientation)MapOfShapeOrientation.Find(Fcur);
793 Fcur.Orientation(orf);
794 std::cout << " Error : this face has been already examined " << std::endl;
795 std::cout << " Impossible to return it ";
801 orf = TopAbs::Reverse(orf);
802 MapOfShapeOrientation(Fcur)=orf;
806 if (BRepCheck_Trace(0) > 3)
808 orf = (TopAbs_Orientation)MapOfShapeOrientation.Find(Fcur);
809 Fcur.Orientation(orf);
810 std::cout << " Resulting Fcur is returned : " ;
818 voisin.Append (Fcur);
828 BRepCheck::Add (aStatusList, myOstat);
833 //=======================================================================
834 //function : SetUnorientable
836 //=======================================================================
837 void BRepCheck_Shell::SetUnorientable()
839 Standard_Mutex::Sentry aLock(myMutex.get());
840 BRepCheck::Add (*myMap (myShape), BRepCheck_UnorientableShape);
843 //=======================================================================
844 //function : IsUnorientable
846 //=======================================================================
847 Standard_Boolean BRepCheck_Shell::IsUnorientable() const
851 return (myOstat != BRepCheck_NoError);
854 Handle(BRepCheck_HListOfStatus) aHList;
856 Standard_Mutex::Sentry aLock(myMutex.get());
857 aHList = myMap (myShape);
859 BRepCheck_ListOfStatus& aStatusList = *aHList;
861 for (BRepCheck_ListIteratorOfListOfStatus itl(aStatusList); itl.More(); itl.Next())
863 if (itl.Value() == BRepCheck_UnorientableShape)
865 return Standard_True;
868 return Standard_False;
871 //=======================================================================
872 //function : NbConnectedSet
874 //=======================================================================
876 Standard_Integer BRepCheck_Shell::NbConnectedSet(TopTools_ListOfShape& theSets)
878 // The connections are found
879 TopTools_IndexedDataMapOfShapeListOfShape parents;
880 TopExp::MapShapesAndAncestors(myShape, TopAbs_EDGE, TopAbs_FACE, parents);
881 // All faces are taken
882 TopTools_MapOfShape theFaces;
883 TopExp_Explorer exsh(myShape, TopAbs_FACE);
884 for (; exsh.More(); exsh.Next()) theFaces.Add(exsh.Current());
885 // The edges that are not oriented or have more than 2 connections are missing
886 Standard_Integer iCur;
887 TopTools_MapOfShape theMultiEd;
888 TopTools_MapOfShape theUnOriEd;
889 for (iCur=1; iCur<=parents.Extent(); iCur++) {
890 const TopoDS_Edge& Ed = TopoDS::Edge(parents.FindKey(iCur));
891 if (parents(iCur).Extent()> 2) theMultiEd.Add(Ed);
892 if (Ed.Orientation()!=TopAbs_REVERSED &&
893 Ed.Orientation()!=TopAbs_FORWARD) theUnOriEd.Add(Ed);
895 // Starting from multiconnected edges propagation by simple connections
896 TopTools_ListIteratorOfListOfShape lconx1, lconx2;
897 TopTools_MapIteratorOfMapOfShape itmsh(theMultiEd);
898 TopoDS_Shell CurShell;
900 TopTools_ListOfShape lesCur;
902 Standard_Boolean newCur=Standard_True;
903 BRB.MakeShell(CurShell);
904 for (; itmsh.More(); itmsh.Next()) {
905 const TopoDS_Shape& Ed = itmsh.Key();
906 if (!theUnOriEd.Contains(Ed)) {
907 for (lconx1.Initialize(parents.FindFromKey(Ed)); lconx1.More(); lconx1.Next()) {
908 if (theFaces.Contains(lconx1.Value())) {
909 adFac=lconx1.Value();
910 BRB.Add(CurShell, adFac);
911 theFaces.Remove(adFac);
912 newCur=Standard_False;
913 if (theFaces.IsEmpty()) break;
914 lesCur.Append(adFac);
915 while (!lesCur.IsEmpty()) {
916 adFac=lesCur.First();
917 lesCur.RemoveFirst();
918 for (exsh.Init(adFac, TopAbs_EDGE); exsh.More(); exsh.Next()) {
919 const TopoDS_Shape& ced = exsh.Current();
920 if (!theMultiEd.Contains(ced)) {
921 for (lconx2.Initialize(parents.FindFromKey(ced)); lconx2.More(); lconx2.Next()) {
922 if (theFaces.Contains(lconx2.Value())) {
923 adFac=lconx2.Value();
924 BRB.Add(CurShell, adFac);
925 theFaces.Remove(adFac);
926 newCur=Standard_False;
927 if (theFaces.IsEmpty()) break;
928 lesCur.Append(adFac);
932 if (theFaces.IsEmpty()) break;
936 CurShell.Closed (BRep_Tool::IsClosed (CurShell));
937 theSets.Append(CurShell);
939 newCur=Standard_True;
940 BRB.MakeShell(CurShell);
943 if (theFaces.IsEmpty()) break;
946 if (theFaces.IsEmpty()) break;
948 return theSets.Extent();