4fdd2228338eb86491c70237fca72b29423d545d
[occt.git] / src / LocOpe / LocOpe_Spliter.cxx
1 // Created on: 1996-01-09
2 // Created by: Jacques GOUSSARD
3 // Copyright (c) 1996-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 by skv - Mon May 31 12:34:09 2004 OCC5865
18
19 #include <BRep_Builder.hxx>
20 #include <BRep_Tool.hxx>
21 #include <BRepTools_Substitution.hxx>
22 #include <Geom_Curve.hxx>
23 #include <GeomAPI_ProjectPointOnCurve.hxx>
24 #include <gp_Vec.hxx>
25 #include <gp_Vec2d.hxx>
26 #include <LocOpe_BuildWires.hxx>
27 #include <LocOpe_Spliter.hxx>
28 #include <LocOpe_SplitShape.hxx>
29 #include <LocOpe_WiresOnShape.hxx>
30 #include <Standard_ConstructionError.hxx>
31 #include <Standard_NoSuchObject.hxx>
32 #include <Standard_NullObject.hxx>
33 #include <StdFail_NotDone.hxx>
34 #include <TopExp.hxx>
35 #include <TopExp_Explorer.hxx>
36 #include <TopoDS.hxx>
37 #include <TopoDS_Edge.hxx>
38 #include <TopoDS_Face.hxx>
39 #include <TopoDS_Iterator.hxx>
40 #include <TopoDS_Shape.hxx>
41 #include <TopoDS_Vertex.hxx>
42 #include <TopoDS_Wire.hxx>
43 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
44 #include <TopTools_DataMapIteratorOfDataMapOfShapeShape.hxx>
45 #include <TopTools_DataMapOfShapeShape.hxx>
46 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
47 #include <TopTools_IndexedMapOfShape.hxx>
48 #include <TopTools_ListIteratorOfListOfShape.hxx>
49 #include <TopTools_MapIteratorOfMapOfShape.hxx>
50 #include <TopTools_MapOfShape.hxx>
51 #include <TopTools_SequenceOfShape.hxx>
52
53 //#include <LocOpe_ProjectedWires.hxx>
54 //  Modified by skv - Mon May 31 13:00:30 2004 OCC5865 Begin
55 // static void RebuildWires(TopTools_ListOfShape&);
56 static void RebuildWires(TopTools_ListOfShape&,
57                          const Handle(LocOpe_WiresOnShape)&);
58 //  Modified by skv - Mon May 31 13:00:31 2004 OCC5865 End
59
60 static void Put(const TopoDS_Shape&,
61                 TopTools_DataMapOfShapeListOfShape&);
62
63 static void Select(const TopoDS_Edge&,
64                    TopTools_ListOfShape&);
65
66
67 //=======================================================================
68 //function : Perform
69 //purpose  : 
70 //=======================================================================
71
72 void LocOpe_Spliter::Perform(const Handle(LocOpe_WiresOnShape)& PW)
73 {
74   if (myShape.IsNull()) {
75     Standard_NullObject::Raise();
76   }
77   myDone = Standard_False;
78   myMap.Clear();
79   myRes.Nullify();
80
81   Put(myShape,myMap);
82
83   TopTools_MapOfShape mapV,mapE;
84   TopTools_DataMapOfShapeShape EdgOnEdg;
85   TopTools_IndexedDataMapOfShapeListOfShape mapFE;
86   TopExp_Explorer exp,exp2;
87   
88   // 1ere etape : substitution des vertex
89
90   TopoDS_Vertex Vb;
91   TopTools_ListOfShape lsubs;
92   BRepTools_Substitution theSubs;
93   BRep_Builder BB;
94
95   for (PW->InitEdgeIterator(); PW->MoreEdge(); PW->NextEdge()) {
96     const TopoDS_Edge& edg = PW->Edge();
97     mapE.Add(edg);
98     for (exp.Init(edg,TopAbs_VERTEX); exp.More(); exp.Next()) {
99       const TopoDS_Vertex& vtx = TopoDS::Vertex(exp.Current());
100       if (!mapV.Contains(vtx)) {
101         if (PW->OnVertex(vtx,Vb)) {
102           mapV.Add(vtx);
103           lsubs.Clear();
104           TopoDS_Vertex vsub = TopoDS::Vertex(vtx.Oriented(TopAbs_FORWARD));
105           gp_Pnt p1 = BRep_Tool::Pnt(vsub), p2 = BRep_Tool::Pnt(Vb);
106           Standard_Real d = p1.Distance(p2);
107           d = d + BRep_Tool::Tolerance(Vb);
108           BB.UpdateVertex(vsub, d);
109           lsubs.Append(vsub);
110           theSubs.Substitute(Vb.Oriented(TopAbs_FORWARD),lsubs);
111         }
112         
113       }
114     }
115   }
116
117   theSubs.Build(myShape);
118   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape itdesc(myMap);
119   if (theSubs.IsCopied(myShape)) {
120     // on n`a fait que des substitutions de vertex. Donc chaque element
121     // est remplace par lui meme ou par un seul element du meme type.
122     for (; itdesc.More(); itdesc.Next()) {
123       if (theSubs.IsCopied(itdesc.Key())) {
124         const TopTools_ListOfShape& lsub = theSubs.Copy(itdesc.Key());
125 #ifdef OCCT_DEBUG
126         if (lsub.Extent() != 1) {
127           Standard_ConstructionError::Raise();
128         }
129 #endif
130         myMap(itdesc.Key()).Clear(); 
131         myMap(itdesc.Key()).Append(lsub.First()); 
132       }
133     }
134   }
135
136   myRes = myMap(myShape).First();
137   LocOpe_SplitShape theCFace(myRes);
138
139   // Adds every vertices lying on an edge of the shape, and prepares 
140   // work to rebuild wires on each face
141   TopoDS_Edge Ed;
142   Standard_Real prm;
143
144   TopTools_MapOfShape theFacesWithSection;
145   for (PW->InitEdgeIterator(); PW->MoreEdge(); PW->NextEdge()) {
146     const TopoDS_Edge& edg = PW->Edge();
147     for (exp.Init(edg,TopAbs_VERTEX); exp.More(); exp.Next()) {
148       const TopoDS_Vertex& vtx = TopoDS::Vertex(exp.Current());
149       if (!mapV.Contains(vtx)) {
150         mapV.Add(vtx);
151         if (PW->OnEdge(vtx,edg,Ed,prm)) {
152           // on devrait verifier que le vtx n`existe pas deja sur l`edge
153           if(!myMap.IsBound(Ed)) continue;
154           Ed = TopoDS::Edge(myMap(Ed).First());
155           theCFace.Add(vtx,prm,Ed);
156         }
157       }
158     }
159     TopoDS_Edge Ebis;
160     if (PW->OnEdge(Ebis)) {
161       //        Ebis = TopoDS::Edge(myMap(Ebis).First());
162       EdgOnEdg.Bind(edg,Ebis);
163     }
164     else {
165       TopoDS_Face fac = PW->OnFace();
166       if(!myMap.IsBound(fac)) continue;
167       Standard_Boolean IsFaceWithSec = PW->IsFaceWithSection(fac);
168       fac = TopoDS::Face(myMap(fac).First());
169       if (IsFaceWithSec)
170         theFacesWithSection.Add(fac);
171       if (!mapFE.Contains(fac)) {
172         TopTools_ListOfShape thelist;
173         mapFE.Add(fac, thelist);
174       }
175       mapFE.ChangeFromKey(fac).Append(edg);
176     }
177   }
178
179   // Rebuilds wires on each face of the shape
180
181   TopTools_ListIteratorOfListOfShape itl;
182   for (Standard_Integer i=1; i<=mapFE.Extent(); i++) {
183     const TopoDS_Face& fac = TopoDS::Face(mapFE.FindKey(i));
184     TopTools_ListOfShape& ledges = mapFE(i);
185 //  Modified by skv - Mon May 31 12:32:54 2004 OCC5865 Begin
186 //     RebuildWires(ledges);
187     RebuildWires(ledges, PW);
188 //  Modified by skv - Mon May 31 12:32:54 2004 OCC5865 End
189     if (theFacesWithSection.Contains(fac))
190       theCFace.Add(ledges, fac);
191     else
192       for (itl.Initialize(ledges); itl.More(); itl.Next())
193         theCFace.Add(TopoDS::Wire(itl.Value()),fac);
194   }
195
196
197   // Mise a jour des descendants
198
199   for (itdesc.Reset(); itdesc.More(); itdesc.Next()) {
200     const TopoDS_Shape& sori = itdesc.Key();
201     const TopoDS_Shape& scib = itdesc.Value().First();
202     myMap(sori) = theCFace.DescendantShapes(scib);
203   }
204
205   const TopTools_ListOfShape& lres = myMap(myShape);
206
207   TopAbs_ShapeEnum typS = myShape.ShapeType();
208   if (typS == TopAbs_FACE && lres.Extent() >=2) {
209     BRep_Builder B;
210     myRes.Nullify();
211     B.MakeShell(TopoDS::Shell(myRes));
212     myRes.Orientation(TopAbs_FORWARD);
213     for (itl.Initialize(lres); itl.More(); itl.Next()) {
214       B.Add(myRes,itl.Value().Oriented(myShape.Orientation()));
215     }
216   }
217   else if (typS == TopAbs_EDGE && lres.Extent() >=2) {
218     BRep_Builder B;
219     myRes.Nullify();
220     B.MakeWire(TopoDS::Wire(myRes));
221     myRes.Orientation(TopAbs_FORWARD);
222     for (itl.Initialize(lres); itl.More(); itl.Next()) {
223       B.Add(myRes,itl.Value().Oriented(myShape.Orientation()));
224     }
225   }
226   else {
227     if (lres.Extent() != 1) {
228       return;
229     }
230     myRes = lres.First();
231   }
232
233   theSubs.Clear();
234   for (TopTools_DataMapIteratorOfDataMapOfShapeShape itee(EdgOnEdg);
235        itee.More();
236        itee.Next()) {
237     const TopoDS_Edge& e1 = TopoDS::Edge(itee.Key());
238     // on recherche dans les descendants de e2 l`edge qui correspont a e1
239
240     TopoDS_Vertex vf1,vl1,vf2,vl2;
241     TopExp::Vertices(e1,vf1,vl1);
242     lsubs.Clear();
243     for (itl.Initialize(myMap(itee.Value()));
244          itl.More();
245          itl.Next()) {
246       const TopoDS_Edge& e2 = TopoDS::Edge(itl.Value());
247       TopExp::Vertices(e2,vf2,vl2);
248
249       if (!vl1.IsSame(vf1)) {
250         if (vf1.IsSame(vf2) && vl1.IsSame(vl2)) {
251           lsubs.Append(e2.Oriented(TopAbs_FORWARD));
252           //    break;
253         }
254         else if (vf1.IsSame(vl2) && vl1.IsSame(vf2)) {
255           lsubs.Append(e2.Oriented(TopAbs_REVERSED));
256           //    break;
257         }
258       }
259       else { // discrimination sur les tangentes
260         if (vf2.IsSame(vl2) && vl2.IsSame(vl1)) { // tout au meme point
261           TopLoc_Location Loc;
262           Standard_Real f,l;
263           gp_Pnt pbid;
264           gp_Vec v1,v2;
265           Handle(Geom_Curve) C = BRep_Tool::Curve(e1,Loc,f,l);
266           C->D1(f,pbid,v1);
267           v1.Transform(Loc.Transformation());
268
269           C = BRep_Tool::Curve(e2,Loc,f,l);
270           C->D1(f,pbid,v2);
271           v2.Transform(Loc.Transformation());
272           if (v1.Dot(v2) >0.) {
273             lsubs.Append(e2.Oriented(TopAbs_FORWARD));
274           }
275           else {
276             lsubs.Append(e2.Oriented(TopAbs_REVERSED));
277           }
278         }
279       }
280
281     }
282     if (lsubs.Extent() >= 2) { // il faut faire un choix
283       Select(e1,lsubs);
284     }
285     if (lsubs.Extent() == 1) {
286       TopoDS_Shape ebase = lsubs.First();
287       lsubs.Clear();
288       lsubs.Append(e1.Oriented(ebase.Orientation()));
289       theSubs.Substitute(ebase.Oriented(TopAbs_FORWARD),lsubs);
290     }
291     else {
292 #ifdef OCCT_DEBUG
293       cout << "Pb pour substitution" << endl;
294 #endif
295     }
296   }
297
298   theSubs.Build(myRes);
299
300   for (itdesc.Reset(); itdesc.More(); itdesc.Next()) {
301     TopTools_ListOfShape& ldesc = myMap(itdesc.Key());
302     TopTools_ListOfShape newdesc;
303     for (itl.Initialize(ldesc); itl.More(); itl.Next()) {
304       if (theSubs.IsCopied(itl.Value())) {
305         const TopTools_ListOfShape& lsub = theSubs.Copy(itl.Value());
306 #ifdef OCCT_DEBUG
307         if (lsub.Extent() != 1) {
308           Standard_ConstructionError::Raise();
309         }
310 #endif
311         newdesc.Append(lsub.First());
312       }
313       else {
314         newdesc.Append(itl.Value());
315       }
316     }
317     myMap(itdesc.Key()) = newdesc;
318   }
319   
320   if (theSubs.IsCopied(myRes)) {
321     myRes = theSubs.Copy(myRes).First();
322   }
323
324   ////remove superfluous vertices on degenerated edges
325   theSubs.Clear();
326   TopTools_IndexedMapOfShape Emap;
327   TopExp::MapShapes(myRes, TopAbs_EDGE, Emap);
328   TopTools_SequenceOfShape DegEdges;
329   Standard_Integer i, j;
330   for (i = 1; i <= Emap.Extent(); i++)
331   {
332     const TopoDS_Edge& anEdge = TopoDS::Edge(Emap(i));
333     if (BRep_Tool::Degenerated(anEdge))
334       DegEdges.Append(anEdge);
335   }
336   
337   TopTools_SequenceOfShape DegWires;
338   for (;;)
339   {
340     if (DegEdges.IsEmpty())
341       break;
342     TopoDS_Wire aDegWire;
343     BB.MakeWire(aDegWire);
344     BB.Add(aDegWire, DegEdges(1));
345     DegEdges.Remove(1);
346     TopoDS_Vertex Vfirst, Vlast;
347     for (;;)
348     {
349       TopExp::Vertices(aDegWire, Vfirst, Vlast);
350       Standard_Boolean found = Standard_False;
351       for (i = 1; i <= DegEdges.Length(); i++)
352       {
353         const TopoDS_Edge& anEdge = TopoDS::Edge(DegEdges(i));
354         TopoDS_Vertex V1, V2;
355         TopExp::Vertices(anEdge, V1, V2);
356         if (V1.IsSame(Vfirst) || V1.IsSame(Vlast) || V2.IsSame(Vfirst) || V2.IsSame(Vlast))
357         {
358           BB.Add(aDegWire, anEdge);
359           DegEdges.Remove(i);
360           found = Standard_True;
361           break;
362         }
363       }
364       if (!found)
365         break;
366     }
367     DegWires.Append(aDegWire);
368   }
369
370   for (i = 1; i <= DegWires.Length(); i++)
371   {
372     TopTools_IndexedMapOfShape Vmap;
373     TopExp::MapShapes(DegWires(i), TopAbs_VERTEX, Vmap);
374     TopTools_ListOfShape LV;
375     LV.Append(Vmap(1).Oriented(TopAbs_FORWARD));
376     for (j = 2; j <= Vmap.Extent(); j++)
377     {
378       if (!Vmap(j).IsSame(Vmap(1)))
379         theSubs.Substitute(Vmap(j), LV);
380     }
381   }
382   theSubs.Build(myRes);
383   if (theSubs.IsCopied(myRes))
384     myRes = theSubs.Copy(myRes).First();
385   ////
386
387   myDLeft.Clear();
388   myLeft.Clear();
389   mapV.Clear();
390
391   TopTools_MapIteratorOfMapOfShape itms;
392
393   for (exp.Init(myRes, TopAbs_FACE); exp.More(); exp.Next()) {
394     const TopoDS_Face& fac = TopoDS::Face(exp.Current());
395     for (exp2.Init(fac,TopAbs_EDGE); exp2.More(); exp2.Next()) {
396       const TopoDS_Edge& edg = TopoDS::Edge(exp2.Current());
397       for (itms.Initialize(mapE); 
398            itms.More(); itms.Next()) {
399         if (itms.Key().IsSame(edg) &&
400             edg.Orientation() == itms.Key().Orientation()) {
401           break;
402         }
403       }
404       if (itms.More()) {
405         break;
406       }
407     }
408     if (exp2.More()) {
409       myDLeft.Append(fac);
410       myLeft.Append(fac);
411     }
412     else {
413       mapV.Add(fac);
414     }
415   }
416
417 /* JAG : Ne peut pas marcher
418
419   Standard_Boolean full = mapV.IsEmpty();
420   while (!full) {
421     full = Standard_True;
422     itms.Initialize(mapV);
423     const TopoDS_Face& fac = TopoDS::Face(itms.Key());
424     for (exp.Init(fac,TopAbs_EDGE); exp.More(); exp.Next()) {
425       if (!mapE.Contains(exp.Current())) {
426         for (itl.Initialize(myLeft); itl.More(); itl.Next()) {
427           const TopoDS_Face& fac2 = TopoDS::Face(itl.Value());
428           for (exp2.Init(fac2,TopAbs_EDGE); exp2.More(); exp2.Next()) {
429             if (exp2.Current().IsSame(exp.Current())) {
430               myLeft.Append(fac);
431               mapV.Remove(fac);
432               full = mapV.IsEmpty();
433               break;
434             }
435           }
436           if (exp2.More()) {
437             break;
438           }
439         }
440         if (itl.More()) {
441           break;
442         }
443       }
444     }
445   }
446 */
447
448   // Map des edges ou les connexions sont possibles
449   TopTools_MapOfShape Mapebord;
450   for (itl.Initialize(myLeft); itl.More(); itl.Next()) {
451     for (exp.Init(itl.Value(),TopAbs_EDGE); exp.More(); exp.Next()) {
452       if (!mapE.Contains(exp.Current())) {
453         if (!Mapebord.Add(exp.Current())) {
454           Mapebord.Remove(exp.Current());
455         }
456       }
457     }
458   }
459
460
461   while (Mapebord.Extent() != 0) {
462     itms.Initialize(Mapebord);
463     TopoDS_Shape edg = itms.Key();
464
465     for (itms.Initialize(mapV); itms.More(); itms.Next()) {
466       const TopoDS_Shape& fac = itms.Key();
467       for (exp.Init(fac,TopAbs_EDGE); exp.More(); exp.Next()) {
468         if (exp.Current().IsSame(edg)) {
469           break;
470         }
471       }
472       if (exp.More()) {
473         break; // face a gauche
474       }
475     }
476     if (itms.More()) {
477       TopoDS_Shape fac = itms.Key();
478       for (exp.Init(fac,TopAbs_EDGE); exp.More(); exp.Next()) {
479         if (!Mapebord.Add(exp.Current())) {
480           Mapebord.Remove(exp.Current());
481         }
482       }
483       mapV.Remove(fac);
484       myLeft.Append(fac);
485     }
486     else {
487       Mapebord.Remove(edg);
488     }
489   }
490
491   myDone = Standard_True;
492 }
493
494
495 //=======================================================================
496 //function : DescendantShapes
497 //purpose  : 
498 //=======================================================================
499
500 const TopTools_ListOfShape& LocOpe_Spliter::
501    DescendantShapes(const TopoDS_Shape& F)
502 {
503   if (!myDone) {StdFail_NotDone::Raise();}
504   if (myMap.IsBound(F))
505     return myMap(F);
506   else {
507     static TopTools_ListOfShape empty;
508     return empty;
509   }
510 }
511
512
513 //=======================================================================
514 //function : DirectLeft
515 //purpose  : 
516 //=======================================================================
517
518 const TopTools_ListOfShape& LocOpe_Spliter::DirectLeft() const
519 {
520   if (!myDone) {StdFail_NotDone::Raise();}
521   return myDLeft;
522
523 }
524
525
526 //=======================================================================
527 //function : Left
528 //purpose  : 
529 //=======================================================================
530
531 const TopTools_ListOfShape& LocOpe_Spliter::Left() const
532 {
533   if (!myDone) {StdFail_NotDone::Raise();}
534   return myLeft;
535
536 }
537
538
539 //=======================================================================
540 //function : RebuildWires
541 //purpose  : 
542 //=======================================================================
543
544 //  Modified by skv - Mon May 31 12:31:39 2004 OCC5865 Begin
545 //static void RebuildWires(TopTools_ListOfShape& ledge)
546 static void RebuildWires(TopTools_ListOfShape& ledge,
547                          const Handle(LocOpe_WiresOnShape)& PW)
548 {
549   LocOpe_BuildWires theBuild(ledge, PW);
550 //  Modified by skv - Mon May 31 12:31:40 2004 OCC5865 End
551   if (!theBuild.IsDone()) {
552     Standard_ConstructionError::Raise();
553   }
554   ledge = theBuild.Result();
555
556
557 }
558
559
560
561 //=======================================================================
562 //function : Put
563 //purpose  : 
564 //=======================================================================
565
566 static void Put(const TopoDS_Shape& S,
567                 TopTools_DataMapOfShapeListOfShape& theMap)
568 {
569   if (theMap.IsBound(S)) {
570     return;
571   }
572   TopTools_ListOfShape thelist;
573   theMap.Bind(S, thelist);
574   theMap(S).Append(S);
575   for (TopoDS_Iterator it(S); it.More(); it.Next()) {
576     Put(it.Value(),theMap);
577   }
578 }
579
580
581 //=======================================================================
582 //function : Select
583 //purpose  : 
584 //=======================================================================
585
586 static void Select(const TopoDS_Edge& Ebase,
587                    TopTools_ListOfShape& lsubs)
588 {
589
590   // Choix d`un point
591
592   Handle(Geom_Curve) C;
593   TopLoc_Location Loc;
594   Standard_Real f,l,dmin = RealLast();
595   Standard_Integer i=0,imin = 0;
596
597   C = BRep_Tool::Curve(Ebase,Loc,f,l);
598
599   if (!Loc.IsIdentity()) {
600     Handle(Geom_Geometry) GG = C->Transformed(Loc.Transformation());
601     C = Handle(Geom_Curve)::DownCast (GG);
602   }
603   gp_Pnt Pt(C->Value((f+l)/2.));
604
605   GeomAPI_ProjectPointOnCurve proj;
606 //  for (TopTools_ListIteratorOfListOfShape itl(lsubs);
607   TopTools_ListIteratorOfListOfShape itl(lsubs);
608   for ( ;itl.More();itl.Next()) {
609     i++;
610     const TopoDS_Edge& edg = TopoDS::Edge(itl.Value());
611     C = BRep_Tool::Curve(edg,Loc,f,l);
612     if (!Loc.IsIdentity()) {
613       Handle(Geom_Geometry) GG = C->Transformed(Loc.Transformation());
614       C = Handle(Geom_Curve)::DownCast (GG);
615     }
616     proj.Init(Pt,C,f,l);
617     if (proj.NbPoints() > 0) {
618       if (proj.LowerDistance() < dmin) {
619         imin = i;
620         dmin = proj.LowerDistance();
621       }
622     }
623   }
624   if (imin == 0) {
625     lsubs.Clear();
626   }
627   else {
628     itl.Initialize(lsubs);
629     i = 1;
630     while (i < imin) {
631       lsubs.Remove(itl);
632       i++;
633     }
634     itl.Next();
635     while (itl.More()) {
636       lsubs.Remove(itl);
637     }
638   }
639 }