0026682: TopExp::MapShapesAndAncestors() will build map with duplicated ancestors.
[occt.git] / src / BRepOffset / BRepOffset_Analyse.cxx
1 // Created on: 1995-10-20
2 // Created by: Yves FRICAUD
3 // Copyright (c) 1995-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
18 #include <Adaptor3d_Surface.hxx>
19 #include <BRep_Builder.hxx>
20 #include <BRep_Tool.hxx>
21 #include <BRepAdaptor_Curve.hxx>
22 #include <BRepAdaptor_Surface.hxx>
23 #include <BRepOffset_Analyse.hxx>
24 #include <BRepOffset_Interval.hxx>
25 #include <BRepOffset_ListIteratorOfListOfInterval.hxx>
26 #include <BRepOffset_Tool.hxx>
27 #include <BRepTools.hxx>
28 #include <Geom2d_Curve.hxx>
29 #include <Geom_Curve.hxx>
30 #include <Geom_Surface.hxx>
31 #include <gp.hxx>
32 #include <gp_Dir.hxx>
33 #include <gp_Pnt.hxx>
34 #include <gp_Pnt2d.hxx>
35 #include <gp_Vec.hxx>
36 #include <Precision.hxx>
37 #include <TopExp.hxx>
38 #include <TopExp_Explorer.hxx>
39 #include <TopoDS.hxx>
40 #include <TopoDS_Compound.hxx>
41 #include <TopoDS_Edge.hxx>
42 #include <TopoDS_Face.hxx>
43 #include <TopoDS_Shape.hxx>
44 #include <TopoDS_Vertex.hxx>
45 #include <TopTools_ListIteratorOfListOfShape.hxx>
46 #include <TopTools_MapOfShape.hxx>
47
48 //
49 static void Correct2dPoint(const TopoDS_Face& theF, gp_Pnt2d& theP2d);
50 //
51 static BRepOffset_Type DefineConnectType(const TopoDS_Edge&         E,
52                                                            const TopoDS_Face&         F1,
53                                                            const TopoDS_Face&         F2,
54                                                            const Standard_Real        SinTol,
55                                          const Standard_Boolean     CorrectPoint);
56 //
57 static void CorrectOrientationOfTangent(gp_Vec& TangVec,
58                                         const TopoDS_Vertex& aVertex,
59                                         const TopoDS_Edge& anEdge)
60 {
61   TopoDS_Vertex Vlast = TopExp::LastVertex(anEdge);
62   if (aVertex.IsSame(Vlast))
63     TangVec.Reverse();
64 }
65 //=======================================================================
66 //function : BRepOffset_Analyse
67 //purpose  : 
68 //=======================================================================
69
70 BRepOffset_Analyse::BRepOffset_Analyse()
71 :myDone(Standard_False)
72 {
73 }
74
75
76 //=======================================================================
77 //function : BRepOffset_Analyse
78 //purpose  : 
79 //=======================================================================
80
81 BRepOffset_Analyse::BRepOffset_Analyse(const TopoDS_Shape& S, 
82                                        const Standard_Real Angle)
83 :myDone(Standard_False)
84 {
85   Perform( S, Angle);
86 }
87
88 //=======================================================================
89 //function : EdgeAnlyse
90 //purpose  : 
91 //=======================================================================
92
93 static void EdgeAnalyse(const TopoDS_Edge&         E,
94                                           const TopoDS_Face&         F1,
95                                           const TopoDS_Face&         F2,
96                                           const Standard_Real        SinTol,
97                                                 BRepOffset_ListOfInterval& LI)
98 {
99   
100   Standard_Real   f,l;
101   BRep_Tool::Range(E, F1, f, l);
102   BRepOffset_Interval I;
103   I.First(f); I.Last(l);
104   //
105   // Tangent if the regularity is at least G1.
106   if (BRep_Tool::HasContinuity(E,F1,F2)) {
107     if (BRep_Tool::Continuity(E,F1,F2) > GeomAbs_C0) {
108       I.Type(BRepOffset_Tangent);
109       LI.Append(I);
110       return;
111     }
112   }
113   //
114   BRepOffset_Type aType = DefineConnectType(E, F1, F2, SinTol, Standard_False);
115   if(aType != BRepOffset_Tangent)
116   {
117     aType = DefineConnectType(E, F1, F2, SinTol, Standard_True);
118   }
119   I.Type(aType);
120   LI.Append(I);
121 }
122
123 //=======================================================================
124 //function : BuildAncestors
125 //purpose  : 
126 //=======================================================================
127
128 static void BuildAncestors (const TopoDS_Shape&                        S,
129                             TopTools_IndexedDataMapOfShapeListOfShape& MA)
130 {  
131   MA.Clear();
132   TopExp::MapShapesAndUniqueAncestors(S,TopAbs_VERTEX,TopAbs_EDGE,MA);
133   TopExp::MapShapesAndUniqueAncestors(S,TopAbs_EDGE  ,TopAbs_FACE,MA);
134 }
135
136 //=======================================================================
137 //function : IsDone
138 //purpose  : 
139 //=======================================================================
140
141 Standard_Boolean BRepOffset_Analyse::IsDone() const 
142 {
143   return myDone;
144 }
145
146
147 //=======================================================================
148 //function : Perform
149 //purpose  : 
150 //=======================================================================
151
152 void BRepOffset_Analyse::Perform (const TopoDS_Shape& S, 
153                                   const Standard_Real Angle)
154 {
155   myShape = S;
156
157   angle                = Angle;
158   Standard_Real SinTol = Sin(Angle);
159
160   // Build ancestors.
161   BuildAncestors (S,ancestors);
162
163   
164   TopExp_Explorer Exp(S.Oriented(TopAbs_FORWARD),TopAbs_EDGE);
165   for ( ; Exp.More(); Exp.Next()) {
166     const TopoDS_Edge& E = TopoDS::Edge(Exp.Current());
167     if (!mapEdgeType.IsBound(E)) {
168       BRepOffset_ListOfInterval LI;
169       mapEdgeType.Bind(E,LI);
170       
171       const TopTools_ListOfShape& L = Ancestors(E);
172       if ( L.IsEmpty()) 
173         continue;
174
175       if (L.Extent() == 2) {
176         const TopoDS_Face& F1 = TopoDS::Face(L.First());
177         const TopoDS_Face& F2 = TopoDS::Face(L.Last ());
178         EdgeAnalyse(E,F1,F2,SinTol,mapEdgeType(E));
179       }
180       else if (L.Extent() == 1) {
181         Standard_Real U1,U2;
182         const TopoDS_Face& F = TopoDS::Face(L.First());
183         BRep_Tool::Range(E,F,U1,U2);
184         BRepOffset_Interval Inter(U1,U2,BRepOffset_Other);
185         
186         if (! BRepTools::IsReallyClosed(E,F)) {
187           Inter.Type(BRepOffset_FreeBoundary);
188         }
189         mapEdgeType(E).Append(Inter);
190       }
191       else {  
192 #ifdef OCCT_DEBUG
193         cout <<"edge shared by more than two faces"<<endl;
194 #endif  
195       }
196     }
197   }
198   myDone = Standard_True;
199 }
200
201 //=======================================================================
202 //function : Clear
203 //purpose  : 
204 //=======================================================================
205
206 void BRepOffset_Analyse::Clear()
207 {
208   myDone = Standard_False;
209   myShape     .Nullify();
210   mapEdgeType.Clear();
211   ancestors  .Clear();
212 }
213
214
215
216
217
218 //=======================================================================
219 //function : BRepOffset_ListOfInterval&
220 //purpose  : 
221 //=======================================================================
222
223 const BRepOffset_ListOfInterval& BRepOffset_Analyse::Type(const TopoDS_Edge& E)
224 const 
225 {
226   return mapEdgeType (E);
227 }
228
229
230 //=======================================================================
231 //function : Edges
232 //purpose  : 
233 //=======================================================================
234
235 void BRepOffset_Analyse::Edges(const TopoDS_Vertex&  V, 
236                                const BRepOffset_Type T,
237                                TopTools_ListOfShape& LE) 
238 const 
239 {
240   LE.Clear();
241   const TopTools_ListOfShape& L = Ancestors (V);
242   TopTools_ListIteratorOfListOfShape it(L);
243   
244   for ( ;it.More(); it.Next()) {
245     const TopoDS_Edge& E = TopoDS::Edge(it.Value());
246     TopoDS_Vertex V1,V2;
247     BRepOffset_Tool::EdgeVertices (E,V1,V2);
248     if (V1.IsSame(V)) {
249       if (mapEdgeType(E).Last().Type() == T)
250         LE.Append(E);
251     }
252     if (V2.IsSame(V)) {
253       if (mapEdgeType(E).First().Type() == T)
254         LE.Append(E);
255     }
256   }
257 }
258
259
260 //=======================================================================
261 //function : Edges
262 //purpose  : 
263 //=======================================================================
264
265 void BRepOffset_Analyse::Edges(const TopoDS_Face&    F, 
266                                const BRepOffset_Type T,
267                                TopTools_ListOfShape& LE) 
268 const 
269 {
270   LE.Clear();
271   TopExp_Explorer exp(F, TopAbs_EDGE);
272   
273   for ( ;exp.More(); exp.Next()) {
274     const TopoDS_Edge& E = TopoDS::Edge(exp.Current());
275
276     const BRepOffset_ListOfInterval& Lint = Type(E);
277     BRepOffset_ListIteratorOfListOfInterval it(Lint);
278     for ( ;it.More(); it.Next()) {
279       if (it.Value().Type() == T) LE.Append(E);
280     }
281   }
282 }
283
284 //=======================================================================
285 //function : TangentEdges
286 //purpose  : 
287 //=======================================================================
288
289 void BRepOffset_Analyse::TangentEdges(const TopoDS_Edge&    Edge  ,
290                                       const TopoDS_Vertex&  Vertex,
291                                       TopTools_ListOfShape& Edges  ) const 
292 {
293   gp_Vec V,VRef;
294
295
296   Standard_Real U,URef;
297   BRepAdaptor_Curve C3d, C3dRef;
298
299   URef   = BRep_Tool::Parameter(Vertex,Edge);
300   C3dRef = BRepAdaptor_Curve(Edge);
301   VRef   = C3dRef.DN(URef,1);
302   CorrectOrientationOfTangent(VRef, Vertex, Edge);
303   if (VRef.SquareMagnitude() < gp::Resolution()) return;
304
305   Edges.Clear();
306
307   const TopTools_ListOfShape& Anc = Ancestors(Vertex);
308   TopTools_ListIteratorOfListOfShape it(Anc);
309   for ( ; it.More(); it.Next()) {
310     const TopoDS_Edge& CurE = TopoDS::Edge(it.Value());
311     if ( CurE.IsSame(Edge)) continue;
312     U   = BRep_Tool::Parameter(Vertex,CurE);
313     C3d = BRepAdaptor_Curve(CurE);
314     V   = C3d.DN(U,1);
315     CorrectOrientationOfTangent(V, Vertex, CurE);
316     if (V.SquareMagnitude() < gp::Resolution()) continue;
317     if (V.IsOpposite(VRef,angle)) {
318       Edges.Append(CurE);
319     }
320   }
321 }
322
323
324
325 //=======================================================================
326 //function : HasAncestor
327 //purpose  : 
328 //=======================================================================
329
330 Standard_Boolean  BRepOffset_Analyse::HasAncestor (const TopoDS_Shape& S) const 
331 {
332   return ancestors.Contains(S);
333 }
334
335
336 //=======================================================================
337 //function : Ancestors
338 //purpose  : 
339 //=======================================================================
340
341 const TopTools_ListOfShape& BRepOffset_Analyse::Ancestors 
342 (const TopoDS_Shape& S) const 
343 {
344   return ancestors.FindFromKey(S);
345 }
346
347
348 //=======================================================================
349 //function : Explode
350 //purpose  : 
351 //=======================================================================
352
353 void BRepOffset_Analyse::Explode(      TopTools_ListOfShape& List,
354                                  const BRepOffset_Type       T   ) const 
355 {
356   List.Clear();
357   BRep_Builder B;
358   TopTools_MapOfShape Map;
359   
360   TopExp_Explorer Fexp;
361   for (Fexp.Init(myShape,TopAbs_FACE); Fexp.More(); Fexp.Next()) {
362     if ( Map.Add(Fexp.Current())) {
363       TopoDS_Face Face = TopoDS::Face(Fexp.Current());
364       TopoDS_Compound Co;
365       B.MakeCompound(Co);
366       B.Add(Co,Face);
367       // add to Co all faces from the cloud of faces
368       // G1 created from <Face>
369       AddFaces(Face,Co,Map,T);
370       List.Append(Co);
371     }
372   }
373 }
374
375 //=======================================================================
376 //function : Explode
377 //purpose  : 
378 //=======================================================================
379
380 void BRepOffset_Analyse::Explode(      TopTools_ListOfShape& List,
381                                  const BRepOffset_Type       T1,
382                                  const BRepOffset_Type       T2) const 
383 {
384   List.Clear();
385   BRep_Builder B;
386   TopTools_MapOfShape Map;
387   
388   TopExp_Explorer Fexp;
389   for (Fexp.Init(myShape,TopAbs_FACE); Fexp.More(); Fexp.Next()) {
390     if ( Map.Add(Fexp.Current())) {
391       TopoDS_Face Face = TopoDS::Face(Fexp.Current());
392       TopoDS_Compound Co;
393       B.MakeCompound(Co);
394       B.Add(Co,Face);
395       // add to Co all faces from the cloud of faces
396       // G1 created from  <Face>
397       AddFaces(Face,Co,Map,T1,T2);
398       List.Append(Co);
399     }
400   }
401 }
402
403
404 //=======================================================================
405 //function : AddFaces
406 //purpose  : 
407 //=======================================================================
408
409 void BRepOffset_Analyse::AddFaces (const TopoDS_Face&    Face,
410                                    TopoDS_Compound&      Co,
411                                    TopTools_MapOfShape&  Map,
412                                    const BRepOffset_Type T) const 
413 {
414   BRep_Builder B;
415   TopExp_Explorer exp(Face,TopAbs_EDGE);
416   for ( ; exp.More(); exp.Next()) {
417     const TopoDS_Edge& E = TopoDS::Edge(exp.Current());
418     const BRepOffset_ListOfInterval& LI = Type(E);
419     if (!LI.IsEmpty() && LI.First().Type() == T) {
420       // so <NewFace> is attached to G1 by <Face>
421       const TopTools_ListOfShape& L = Ancestors(E);
422       if (L.Extent() == 2) {
423         TopoDS_Face F1 = TopoDS::Face(L.First());
424         if ( F1.IsSame(Face)) 
425           F1 = TopoDS::Face(L.Last ());
426         if ( Map.Add(F1)) {
427           B.Add(Co,F1);
428           AddFaces(F1,Co,Map,T);
429         }
430       }
431     }
432   }
433 }
434 //=======================================================================
435 //function : AddFaces
436 //purpose  : 
437 //=======================================================================
438
439 void BRepOffset_Analyse::AddFaces (const TopoDS_Face&    Face,
440                                    TopoDS_Compound&      Co,
441                                    TopTools_MapOfShape&  Map,
442                                    const BRepOffset_Type T1,
443                                    const BRepOffset_Type T2) const 
444 {
445   BRep_Builder B;
446   TopExp_Explorer exp(Face,TopAbs_EDGE);
447   for ( ; exp.More(); exp.Next()) {
448     const TopoDS_Edge& E = TopoDS::Edge(exp.Current());
449     const BRepOffset_ListOfInterval& LI = Type(E);
450     if (!LI.IsEmpty() && 
451         (LI.First().Type() == T1 || LI.First().Type() == T2)) {
452       // so <NewFace> is attached to G1 by <Face>
453       const TopTools_ListOfShape& L = Ancestors(E);
454       if (L.Extent() == 2) {
455         TopoDS_Face F1 = TopoDS::Face(L.First());
456         if ( F1.IsSame(Face)) 
457           F1 = TopoDS::Face(L.Last ());
458         if ( Map.Add(F1)) {
459           B.Add(Co,F1);
460           AddFaces(F1,Co,Map,T1,T2);
461         }
462       }
463     }
464   }
465 }
466
467 //=======================================================================
468 //function : Correct2dPoint
469 //purpose  : 
470 //=======================================================================
471 void Correct2dPoint(const TopoDS_Face& theF, gp_Pnt2d& theP2d)
472 {
473   BRepAdaptor_Surface aBAS(theF, Standard_False);
474   if (aBAS.GetType() < GeomAbs_BezierSurface) {
475     return;
476   }
477   //
478   const Standard_Real coeff = 0.01;
479   Standard_Real eps;
480   Standard_Real u1, u2, v1, v2;
481   //
482   aBAS.Initialize(theF, Standard_True);
483   u1 = aBAS.FirstUParameter();
484   u2 = aBAS.LastUParameter();
485   v1 = aBAS.FirstVParameter();
486   v2 = aBAS.LastVParameter();
487   if (!(Precision::IsInfinite(u1) || Precision::IsInfinite(u2)))
488   {
489     eps = Max(coeff*(u2 - u1), Precision::PConfusion());
490     if (Abs(theP2d.X() - u1) < eps)
491     {
492       theP2d.SetX(u1 + eps);
493     }
494     if (Abs(theP2d.X() - u2) < eps)
495     {
496       theP2d.SetX(u2 - eps);
497     }
498   }
499   if (!(Precision::IsInfinite(v1) || Precision::IsInfinite(v2)))
500   {
501     eps = Max(coeff*(v2 - v1), Precision::PConfusion());
502     if (Abs(theP2d.Y() - v1) < eps)
503     {
504       theP2d.SetY(v1 + eps);
505     }
506     if (Abs(theP2d.Y() - v2) < eps)
507     {
508       theP2d.SetY(v2 - eps);
509     }
510   }
511 }
512
513 //=======================================================================
514 //function : DefineConnectType
515 //purpose  : 
516 //=======================================================================
517 BRepOffset_Type DefineConnectType(const TopoDS_Edge&     E,
518                                   const TopoDS_Face&     F1,
519                                   const TopoDS_Face&     F2,
520                                   const Standard_Real    SinTol,
521                                   const Standard_Boolean CorrectPoint)
522 {
523   TopLoc_Location L;
524   Standard_Real   f,l;
525   
526   const Handle(Geom_Surface)& S1 = BRep_Tool::Surface(F1);
527   const Handle(Geom_Surface)& S2 = BRep_Tool::Surface(F2);
528   //
529   Handle (Geom2d_Curve) C1 = BRep_Tool::CurveOnSurface(E,F1,f,l);
530   Handle (Geom2d_Curve) C2 = BRep_Tool::CurveOnSurface(E,F2,f,l);
531
532   BRepAdaptor_Curve C(E);
533   f = C.FirstParameter();
534   l = C.LastParameter();
535 //
536   Standard_Real ParOnC = 0.5*(f+l);
537   gp_Vec T1 = C.DN(ParOnC,1).Transformed(L.Transformation());
538   if (T1.SquareMagnitude() > gp::Resolution()) {
539     T1.Normalize();
540   }
541   
542   if (BRepOffset_Tool::OriEdgeInFace(E,F1) == TopAbs_REVERSED) {
543     T1.Reverse();
544   }
545   if (F1.Orientation() == TopAbs_REVERSED) T1.Reverse();
546
547   gp_Pnt2d P  = C1->Value(ParOnC);
548   gp_Pnt   P3;
549   gp_Vec   D1U,D1V;
550   
551   if(CorrectPoint) 
552     Correct2dPoint(F1, P);
553   //
554   S1->D1(P.X(),P.Y(),P3,D1U,D1V);
555   gp_Vec DN1(D1U^D1V);
556   if (F1.Orientation() == TopAbs_REVERSED) DN1.Reverse();
557   
558   P = C2->Value(ParOnC);
559   if(CorrectPoint) 
560     Correct2dPoint(F2, P);
561   S2->D1(P.X(),P.Y(),P3,D1U,D1V);
562   gp_Vec DN2(D1U^D1V);
563   if (F2.Orientation() == TopAbs_REVERSED) DN2.Reverse();
564
565   DN1.Normalize();
566   DN2.Normalize();
567
568   gp_Vec        ProVec     = DN1^DN2;
569   Standard_Real NormProVec = ProVec.Magnitude(); 
570
571   if (Abs(NormProVec) < SinTol) {
572     // plane
573     if (DN1.Dot(DN2) > 0) {   
574       //Tangent
575       return BRepOffset_Tangent;
576     }
577     else  {                   
578       //Mixed not finished!
579 #ifdef OCCT_DEBUG
580       cout <<" faces locally mixed"<<endl;
581 #endif
582       return BRepOffset_Convex;
583     }
584   }
585   else {  
586     if (NormProVec > gp::Resolution())
587       ProVec.Normalize();
588     Standard_Real Prod  = T1.Dot(DN1^DN2);
589     if (Prod > 0.) {       
590       //
591       return BRepOffset_Convex;
592     }
593     else {                       
594       //reenters
595       return BRepOffset_Concave;
596     }
597   }
598 }