0025333: Result wires obtained after TestHarness command "connectedges" contains...
[occt.git] / src / ShapeAnalysis / ShapeAnalysis_FreeBounds.cxx
1 // Created on: 1998-04-27
2 // Created by: Roman LYGIN
3 // Copyright (c) 1998-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
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.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17 // Modified:    Thu Sep 17 12:27:58 1998
18 // 25.12.98 pdn transmission from BRepTools_Sewing to BRepBuilderAPI_Sewing
19 //szv#4 S4163
20 // 11.01.00 svv #1: porting on DEC  
21
22 #include <ShapeAnalysis_FreeBounds.ixx>
23
24 #include <BRep_Builder.hxx>
25 #include <BRep_Tool.hxx>
26 #include <BRepBuilderAPI_Sewing.hxx>
27
28 #include <Precision.hxx>
29
30 #include <TopoDS.hxx>
31 #include <TopoDS_Vertex.hxx>
32 #include <TopoDS_Wire.hxx>
33 #include <TopoDS_Edge.hxx>
34 #include <TopoDS_Iterator.hxx>
35
36 #include <TColStd_Array1OfBoolean.hxx>
37 #include <TColStd_Array1OfInteger.hxx>
38 #include <TColStd_SequenceOfInteger.hxx>
39
40 #include <ShapeExtend_WireData.hxx>
41 #include <ShapeExtend_Explorer.hxx>
42 #include <ShapeBuild_Vertex.hxx>
43 #include <ShapeBuild_Edge.hxx>
44 #include <ShapeAnalysis.hxx>
45 #include <ShapeAnalysis_Edge.hxx>
46 #include <ShapeAnalysis_Wire.hxx>
47 #include <ShapeAnalysis_Shell.hxx>
48
49 #include <gp_Pnt.hxx> //ied_modif_for_compil_Nov-19-1998
50 #include <TopExp_Explorer.hxx>
51 #include <TopTools_MapOfShape.hxx>
52 #include <TopTools_MapIteratorOfMapOfShape.hxx>
53 #include <TopoDS_Shell.hxx>
54 #include <ShapeAnalysis_BoxBndTree.hxx>
55 #include <NCollection_UBTreeFiller.hxx>
56 #include <TColStd_ListIteratorOfListOfInteger.hxx>
57 #include <TopTools_HArray1OfShape.hxx>
58 #include <TopExp.hxx>
59
60 //=======================================================================
61 //function : ShapeAnalysis_FreeBounds
62 //purpose  : Empty constructor
63 //=======================================================================
64
65 ShapeAnalysis_FreeBounds::ShapeAnalysis_FreeBounds() {}
66
67 //=======================================================================
68 //function : ShapeAnalysis_FreeBounds
69 //purpose  : 
70 //=======================================================================
71
72 ShapeAnalysis_FreeBounds::ShapeAnalysis_FreeBounds(const TopoDS_Shape& shape,
73                                                    const Standard_Real toler,
74                                                    const Standard_Boolean splitclosed,
75                                                    const Standard_Boolean splitopen) :
76        myTolerance (toler), myShared (Standard_False),
77        mySplitClosed (splitclosed), mySplitOpen (splitopen)
78 {
79   BRepBuilderAPI_Sewing Sew(toler, Standard_False, Standard_False);
80   for (TopoDS_Iterator S (shape); S.More(); S.Next()) Sew.Add(S.Value());
81   Sew.Perform();
82   //
83   // Extract free edges.
84   //
85   Standard_Integer nbedge = Sew.NbFreeEdges();
86   Handle(TopTools_HSequenceOfShape) edges = new TopTools_HSequenceOfShape;
87   Handle(TopTools_HSequenceOfShape) wires;
88   TopoDS_Edge anEdge;
89   for (Standard_Integer iedge = 1 ; iedge <= nbedge ; iedge++) {
90     anEdge = TopoDS::Edge (Sew.FreeEdge(iedge));
91     if ( !BRep_Tool::Degenerated(anEdge) ) edges->Append (anEdge);
92   }
93   //
94   // Chainage.
95   //
96   ConnectEdgesToWires (edges, toler, Standard_False, wires);
97   DispatchWires (wires, myWires, myEdges);
98   SplitWires ();
99   
100   return ;
101 }
102
103 //=======================================================================
104 //function : ShapeAnalysis_FreeBounds
105 //purpose  : 
106 //=======================================================================
107
108 ShapeAnalysis_FreeBounds::ShapeAnalysis_FreeBounds(const TopoDS_Shape& shape,
109                                                    const Standard_Boolean splitclosed,
110                                                    const Standard_Boolean splitopen,
111                                                    const Standard_Boolean checkinternaledges) :
112        myTolerance (0.), myShared (Standard_True),
113        mySplitClosed (splitclosed), mySplitOpen (splitopen)
114 {
115   TopoDS_Shell aTmpShell;
116   BRep_Builder aB;
117   aB.MakeShell(aTmpShell);
118   for(TopExp_Explorer aExpFace(shape,TopAbs_FACE);aExpFace.More(); aExpFace.Next())
119     aB.Add(aTmpShell,aExpFace.Current());
120   
121   ShapeAnalysis_Shell sas;
122   sas.CheckOrientedShells (aTmpShell, Standard_True, checkinternaledges);
123   
124   if (sas.HasFreeEdges()) {
125     ShapeExtend_Explorer see;
126     Handle(TopTools_HSequenceOfShape) edges = see.SeqFromCompound (sas.FreeEdges(), Standard_False);
127   
128     Handle(TopTools_HSequenceOfShape) wires;
129     ConnectEdgesToWires (edges, Precision::Confusion(), Standard_True, wires);
130     DispatchWires (wires, myWires, myEdges);
131     SplitWires ();
132   }
133   
134   
135 }
136
137 //=======================================================================
138 //function : ConnectEdgesToWires
139 //purpose  : 
140 //=======================================================================
141
142  void ShapeAnalysis_FreeBounds::ConnectEdgesToWires(Handle(TopTools_HSequenceOfShape)& edges,
143                                                     const Standard_Real toler,
144                                                     const Standard_Boolean shared,
145                                                     Handle(TopTools_HSequenceOfShape)& wires) 
146 {
147   Handle(TopTools_HSequenceOfShape) iwires = new TopTools_HSequenceOfShape;
148   BRep_Builder B;
149   
150   Standard_Integer i; // svv #1
151   for (i = 1; i <= edges->Length(); i++) {
152     TopoDS_Wire wire;
153     B.MakeWire (wire);
154     B.Add (wire, edges->Value (i));
155     iwires->Append (wire);
156   }
157
158   ConnectWiresToWires (iwires, toler, shared, wires);
159
160   for (i = 1; i <= edges->Length(); i++)
161     if (iwires->Value(i).Orientation() == TopAbs_REVERSED)
162       edges->ChangeValue(i).Reverse();
163 }
164
165 //=======================================================================
166 //function : ConnectWiresToWires
167 //purpose  : 
168 //=======================================================================
169
170  void ShapeAnalysis_FreeBounds::ConnectWiresToWires(Handle(TopTools_HSequenceOfShape)& iwires,
171                                                     const Standard_Real toler,
172                                                     const Standard_Boolean shared,
173                                                     Handle(TopTools_HSequenceOfShape)& owires) 
174 {
175   TopTools_DataMapOfShapeShape map;
176   ConnectWiresToWires (iwires, toler, shared, owires, map);
177 }
178
179 //=======================================================================
180 //function : ConnectWiresToWires
181 //purpose  : 
182 //=======================================================================
183
184  void ShapeAnalysis_FreeBounds::ConnectWiresToWires(Handle(TopTools_HSequenceOfShape)& iwires,
185                                                     const Standard_Real toler,
186                                                     const Standard_Boolean shared,
187                                                     Handle(TopTools_HSequenceOfShape)& owires,
188                                                     TopTools_DataMapOfShapeShape& vertices) 
189 {
190   if (iwires.IsNull() || !iwires->Length()) return;
191   Handle(TopTools_HArray1OfShape) arrwires = new TopTools_HArray1OfShape(1, iwires->Length());
192   //amv
193   Standard_Integer i;
194   for (i = 1; i <= arrwires->Length(); i++)
195     arrwires->SetValue(i, iwires->Value(i));
196   owires = new TopTools_HSequenceOfShape;
197   Standard_Real tolerance = Max (toler, Precision::Confusion());
198   
199   Handle(ShapeExtend_WireData)
200     sewd = new ShapeExtend_WireData (TopoDS::Wire (arrwires->Value (1)));
201
202   Standard_Boolean isUsedManifoldMode = Standard_True;
203
204   if((sewd->NbEdges() < 1) && (sewd->NbNonManifoldEdges() > 0))
205   {
206     isUsedManifoldMode = Standard_False;
207     sewd = new ShapeExtend_WireData (TopoDS::Wire (arrwires->Value (1)), Standard_True,
208                                      isUsedManifoldMode);
209   }
210
211   Handle(ShapeAnalysis_Wire) saw = new ShapeAnalysis_Wire;
212   saw->Load (sewd);
213   saw->SetPrecision (tolerance);
214
215   ShapeAnalysis_BoxBndTree aBBTree;
216   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
217   ShapeAnalysis_BoxBndTreeSelector aSel(arrwires, shared);
218   aSel.LoadList(1);
219  
220   for (Standard_Integer inbW = 2; inbW <= arrwires->Length(); inbW++){
221     TopoDS_Wire trW = TopoDS::Wire (arrwires->Value (inbW));
222     Bnd_Box aBox;
223     TopoDS_Vertex trV1, trV2;
224     ShapeAnalysis::FindBounds (trW, trV1, trV2);
225     gp_Pnt trP1 = BRep_Tool::Pnt(trV1);
226     gp_Pnt trP2 = BRep_Tool::Pnt(trV2);
227     aBox.Set(trP1);
228     aBox.Add(trP2);
229     aBox.SetGap(tolerance);
230     aTreeFiller.Add(inbW, aBox);
231   }
232
233   aTreeFiller.Fill();
234   Standard_Integer nsel;
235   
236   ShapeAnalysis_Edge sae; //szv#4:S4163:12Mar99 moved
237   Standard_Boolean done = Standard_False;
238
239   
240   while (!done)
241   {
242     Standard_Boolean found = Standard_False, tail = Standard_False, direct = Standard_False;
243     Standard_Integer lwire=0;
244     aSel.SetStop();
245     Bnd_Box FVBox, LVBox;
246     TopoDS_Vertex Vf, Vl;
247     Vf = sae.FirstVertex(sewd->Edge(1));
248     Vl = sae.LastVertex(sewd->Edge(sewd->NbEdges()));
249
250     gp_Pnt pf, pl;
251     pf = BRep_Tool::Pnt(Vf);
252     pl = BRep_Tool::Pnt(Vl);
253     FVBox.Set(pf);
254     FVBox.SetGap(tolerance);
255     LVBox.Set(pl);
256     LVBox.SetGap(tolerance);
257     
258     aSel.DefineBoxes(FVBox, LVBox);
259     
260     if (shared)
261       aSel.DefineVertexes(Vf,Vl);
262     else
263     {
264       aSel.DefinePnt(pf,pl);
265       aSel.SetTolerance(tolerance);
266     }
267     
268     nsel = aBBTree.Select(aSel);
269     
270     if (nsel != 0 && !aSel.LastCheckStatus(ShapeExtend_FAIL))
271     {
272       found = Standard_True;
273       lwire = aSel.GetNb();
274       tail    = aSel.LastCheckStatus (ShapeExtend_DONE1) ||
275                 aSel.LastCheckStatus (ShapeExtend_DONE2);
276       direct  = aSel.LastCheckStatus (ShapeExtend_DONE1) ||
277                 aSel.LastCheckStatus (ShapeExtend_DONE3);
278       aSel.LoadList(lwire);
279     }
280     
281     if (found)
282     {
283       if (!direct)
284         arrwires->ChangeValue(lwire).Reverse();
285
286       TopoDS_Wire aCurW = TopoDS::Wire (arrwires->Value (lwire));
287       Handle(ShapeExtend_WireData) acurwd = new 
288         ShapeExtend_WireData ( TopoDS::Wire (arrwires->Value (lwire)), Standard_True, isUsedManifoldMode);
289       if( !acurwd->NbEdges())
290         continue;
291       sewd->Add (acurwd, (tail ? 0 : 1));
292     }
293     else
294     {
295       //making wire
296       //1.providing connection (see ShapeFix_Wire::FixConnected())
297       //Standard_Integer i; // svv #1
298       for (/*Standard_Integer*/ i = 1; i <= saw->NbEdges(); i++)
299       {
300         if (saw->CheckConnected (i))
301         {
302           Standard_Integer n2 = i;
303           Standard_Integer n1 = (n2 > 1 ? n2 - 1 : saw->NbEdges());
304           TopoDS_Edge E1 = sewd->Edge(n1);
305           TopoDS_Edge E2 = sewd->Edge(n2);
306
307           TopoDS_Vertex Vprev, Vfol, V; //connection vertex
308           Vprev = sae.LastVertex (E1);
309           Vfol = sae.FirstVertex (E2);
310
311           if (saw->LastCheckStatus (ShapeExtend_DONE1)) //absolutely confused
312             V = Vprev;
313           else {
314             ShapeBuild_Vertex sbv; 
315             V = sbv.CombineVertex (Vprev, Vfol);
316           }
317           vertices.Bind (Vprev, V);
318           vertices.Bind (Vfol, V);
319
320           //replace vertices to a new one
321           ShapeBuild_Edge sbe;
322           if (saw->NbEdges() < 2)
323             sewd->Set (sbe.CopyReplaceVertices (E2, V, V), n2);
324           else {
325             sewd->Set (sbe.CopyReplaceVertices (E2, V, TopoDS_Vertex()), n2);
326             if (!saw->LastCheckStatus (ShapeExtend_DONE1))
327               sewd->Set (sbe.CopyReplaceVertices (E1, TopoDS_Vertex(), V), n1);
328           }
329         }
330       }
331
332       //2.making wire
333       TopoDS_Wire wire = sewd->Wire();
334       if(isUsedManifoldMode)
335       {
336         if (!saw->CheckConnected (1) && saw->LastCheckStatus (ShapeExtend_OK))
337           wire.Closed (Standard_True);
338       }
339       else
340       {
341         //Try to check connection by number of free vertices
342         TopTools_MapOfShape vmap;
343         TopoDS_Iterator it(wire);
344
345         for(; it.More(); it.Next())
346         {
347           const TopoDS_Shape& E = it.Value();
348           TopoDS_Iterator ite(E, Standard_False, Standard_True);
349           for(; ite.More(); ite.Next())
350           {
351             const TopoDS_Shape& V = ite.Value();
352             if (V.Orientation() == TopAbs_FORWARD ||
353                 V.Orientation() == TopAbs_REVERSED)
354             {
355               // add or remove in the vertex map
356               if (!vmap.Add(V)) vmap.Remove(V);
357             }
358           }
359
360         }
361         if(vmap.IsEmpty())
362         {
363           wire.Closed(Standard_True);
364         }
365       }
366
367       owires->Append (wire);
368       sewd->Clear();
369       sewd->ManifoldMode() = isUsedManifoldMode;
370         
371       // Recherche de la premier edge non traitee pour un autre wire.
372       //Searching for first edge for next wire
373       lwire = -1;
374       for (/*Standard_Integer*/ i = 1 ; i <= arrwires->Length(); i++)
375       {
376         if (!aSel.ContWire(i))
377         {
378           lwire = i; //szv#4:S4163:12Mar99 optimized
379           sewd->Add (TopoDS::Wire (arrwires->Value (lwire)));
380           aSel.LoadList(lwire);
381
382           if (sewd->NbEdges() > 0)
383             break;
384           sewd->Clear();
385         }
386       }
387
388       if (lwire == -1)
389         done = 1;
390     }
391   }
392
393   for ( /*Standard_Integer*/ i = 1; i <= iwires->Length(); i++)
394   {
395     iwires->SetValue (i, arrwires->Value(i));
396   }
397 }
398
399 static void SplitWire(const TopoDS_Wire& wire,
400                       const Standard_Real toler,
401                       const Standard_Boolean shared,
402                       Handle(TopTools_HSequenceOfShape)& closed,
403                       Handle(TopTools_HSequenceOfShape)& open) 
404 {
405   closed = new TopTools_HSequenceOfShape;
406   open   = new TopTools_HSequenceOfShape;
407   Standard_Real tolerance = Max (toler, Precision::Confusion());
408
409   BRep_Builder B;
410   ShapeAnalysis_Edge sae;
411   
412   Handle(ShapeExtend_WireData) sewd = new ShapeExtend_WireData (wire);
413   Standard_Integer nbedges = sewd->NbEdges();
414
415   //ConnectedEdgeSequence - list of indices of connected edges to build a wire
416   TColStd_SequenceOfInteger ces;
417   //statuses - array of flags describing the edge:
418   //0-free, 1-in CES, 2-already in wire,
419   //3-no closed wire can be produced starting at this edge
420   TColStd_Array1OfInteger statuses (1, nbedges); 
421   statuses.Init (0);
422
423   //building closed wires
424   Standard_Integer i; // svv #1
425   for (i = 1; i <= nbedges; i++)
426     if (statuses.Value (i) == 0) {
427       ces.Append (i); statuses.SetValue (i, 1); //putting into CES
428       Standard_Boolean SearchBackward = Standard_True;
429
430       for(;;) {
431         Standard_Boolean found;
432         TopoDS_Edge edge;
433         TopoDS_Vertex lvertex;
434         gp_Pnt lpoint;
435
436         //searching for connection in ces
437         if (SearchBackward) {
438           SearchBackward = Standard_False;
439           found = Standard_False;
440           edge = sewd->Edge (ces.Last());
441           lvertex = sae.LastVertex (edge);
442           lpoint = BRep_Tool::Pnt (lvertex);
443           Standard_Integer j; // svv #1
444           for (j = ces.Length(); (j >= 1) && !found; j--) {
445             TopoDS_Vertex fv = sae.FirstVertex (sewd->Edge (ces.Value (j)) );
446             gp_Pnt fp = BRep_Tool::Pnt (fv);
447             if ((shared && lvertex.IsSame (fv)) ||
448                 (!shared && lpoint.IsEqual (fp, tolerance)))
449               found = Standard_True;
450           }
451
452           if (found) {
453             j++;//because of decreasing last iteration
454             //making closed wire
455             TopoDS_Wire wire1;
456             B.MakeWire (wire1);
457             for (Standard_Integer cesindex = j; cesindex <= ces.Length(); cesindex++) {
458               B.Add (wire1, sewd->Edge (ces.Value (cesindex)));
459               statuses.SetValue (ces.Value (cesindex), 2);
460             }
461             wire1.Closed (Standard_True);
462             closed->Append (wire1);
463             ces.Remove (j, ces.Length());
464             if (ces.IsEmpty()) break;
465           }
466         }
467     
468         //searching for connection among free edges
469         found = Standard_False;
470         edge = sewd->Edge (ces.Last());
471         lvertex = sae.LastVertex (edge);
472         lpoint = BRep_Tool::Pnt (lvertex);
473         Standard_Integer j; // svv #1
474         for (j = 1; (j <= nbedges) && !found; j++)
475           if (statuses.Value (j) == 0) {
476             TopoDS_Vertex fv = sae.FirstVertex (sewd->Edge (j));
477             gp_Pnt fp = BRep_Tool::Pnt (fv);
478             if ((shared && lvertex.IsSame (fv)) ||
479                 (!shared && lpoint.IsEqual (fp, tolerance)))
480               found = Standard_True;
481           }
482
483         if (found) {
484           j--;//because of last iteration
485           ces.Append (j); statuses.SetValue (j, 1);//putting into CES
486           SearchBackward = Standard_True;
487           continue;
488         }
489         
490         //no edges found - mark the branch as open (use status 3)
491         statuses.SetValue (ces.Last(), 3);
492         ces.Remove (ces.Length());
493         if (ces.IsEmpty()) break;
494       }
495     }
496   
497   //building open wires
498   Handle(TopTools_HSequenceOfShape) edges = new TopTools_HSequenceOfShape;
499   for (i = 1; i <= nbedges; i++)
500     if (statuses.Value (i) != 2) edges->Append (sewd->Edge(i));
501
502   ShapeAnalysis_FreeBounds::ConnectEdgesToWires (edges, toler, shared, open);
503 }
504
505  void ShapeAnalysis_FreeBounds::SplitWires(const Handle(TopTools_HSequenceOfShape)& wires,
506                                            const Standard_Real toler,
507                                            const Standard_Boolean shared,
508                                            Handle(TopTools_HSequenceOfShape)& closed,
509                                            Handle(TopTools_HSequenceOfShape)& open) 
510 {
511   closed = new TopTools_HSequenceOfShape;
512   open   = new TopTools_HSequenceOfShape;
513
514   for (Standard_Integer i = 1; i <= wires->Length(); i++) {
515     Handle(TopTools_HSequenceOfShape) tmpclosed, tmpopen;
516     SplitWire (TopoDS::Wire (wires->Value (i)), toler, shared, tmpclosed, tmpopen);
517     closed->Append (tmpclosed);
518     open->Append (tmpopen);
519   }
520 }
521
522 //=======================================================================
523 //function : DispatchWires
524 //purpose  : 
525 //=======================================================================
526
527  void ShapeAnalysis_FreeBounds::DispatchWires(const Handle(TopTools_HSequenceOfShape)& wires,
528                                               TopoDS_Compound& closed,
529                                               TopoDS_Compound& open)
530 {
531   BRep_Builder B;
532   if (closed.IsNull()) B.MakeCompound (closed);
533   if (open.IsNull())  B.MakeCompound (open);
534   if (wires.IsNull()) return;
535
536   for (Standard_Integer iw = 1 ; iw <= wires->Length(); iw++)
537     if ( wires->Value (iw).Closed() )
538       B.Add (closed, wires->Value (iw));
539     else
540       B.Add (open, wires->Value (iw));
541 }
542
543 //=======================================================================
544 //function : SplitWires
545 //purpose  : Splits compounds of closed (myWires) and open (myEdges) wires
546 //           into small closed wires according to fields mySplitClosed and
547 //           mySplitOpen and rebuilds compounds
548 //=======================================================================
549
550  void ShapeAnalysis_FreeBounds::SplitWires()
551 {
552   if (!mySplitClosed && !mySplitOpen) return; //nothing to do
553
554   ShapeExtend_Explorer see;
555   Handle(TopTools_HSequenceOfShape) closedwires, cw1, cw2,
556                                     openwires,   ow1, ow2;
557   closedwires = see.SeqFromCompound (myWires, Standard_False);
558   openwires   = see.SeqFromCompound (myEdges, Standard_False);
559   
560   if (mySplitClosed) SplitWires (closedwires, myTolerance, myShared, cw1, ow1);
561   else {cw1 = closedwires; ow1 = new TopTools_HSequenceOfShape;}
562
563   if (mySplitOpen) SplitWires (openwires, myTolerance, myShared, cw2, ow2);
564   else {cw2 = new TopTools_HSequenceOfShape; ow2 = openwires;}
565   
566   closedwires = cw1; closedwires->Append (cw2);
567   openwires = ow1;   openwires->Append (ow2);
568
569   //szv#4:S4163:12Mar99 SGI warns
570   TopoDS_Shape compWires = see.CompoundFromSeq (closedwires);
571   TopoDS_Shape compEdges = see.CompoundFromSeq (openwires);
572   myWires = TopoDS::Compound (compWires);
573   myEdges = TopoDS::Compound (compEdges);
574 }