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