0030686: Visualization, SelectMgr_ViewerSelector - sorting issues of transformation...
[occt.git] / src / BRepLib / BRepLib_FindSurface.cxx
1 // Created on: 1994-07-22
2 // Created by: Remi LEQUETTE
3 // Copyright (c) 1994-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 <BRep_Builder.hxx>
19 #include <BRep_Tool.hxx>
20 #include <BRepAdaptor_Curve.hxx>
21 #include <BRepAdaptor_Surface.hxx>
22 #include <BRepLib_FindSurface.hxx>
23 #include <BRepLib_MakeFace.hxx>
24 #include <BRepTools_WireExplorer.hxx>
25 #include <BRepTopAdaptor_FClass2d.hxx>
26 #include <Geom2d_Curve.hxx>
27 #include <Geom_BezierCurve.hxx>
28 #include <Geom_BSplineCurve.hxx>
29 #include <Geom_Plane.hxx>
30 #include <Geom_RectangularTrimmedSurface.hxx>
31 #include <Geom_Surface.hxx>
32 #include <GeomLib.hxx>
33 #include <gp_Ax2.hxx>
34 #include <gp_Ax3.hxx>
35 #include <gp_Circ.hxx>
36 #include <gp_Elips.hxx>
37 #include <gp_Hypr.hxx>
38 #include <gp_Lin.hxx>
39 #include <gp_Parab.hxx>
40 #include <gp_Vec.hxx>
41 #include <math_Jacobi.hxx>
42 #include <math_Matrix.hxx>
43 #include <math_Vector.hxx>
44 #include <Precision.hxx>
45 #include <Standard_ErrorHandler.hxx>
46 #include <Standard_NoSuchObject.hxx>
47 #include <TColgp_Array1OfPnt.hxx>
48 #include <TColgp_HArray1OfPnt.hxx>
49 #include <TColgp_SequenceOfPnt.hxx>
50 #include <TColStd_SequenceOfReal.hxx>
51 #include <TopExp.hxx>
52 #include <TopExp_Explorer.hxx>
53 #include <TopLoc_Location.hxx>
54 #include <TopoDS.hxx>
55 #include <TopoDS_Shape.hxx>
56 #include <TopoDS_Vertex.hxx>
57 #include <TopoDS_Wire.hxx>
58
59 //=======================================================================
60 //function : Controle
61 //purpose  : 
62 //=======================================================================
63 static Standard_Real Controle(const TColgp_SequenceOfPnt& thePoints,
64                               const Handle(Geom_Plane)& thePlane)
65 {
66   Standard_Real dfMaxDist=0.;
67   Standard_Real a,b,c,d, dist;
68   Standard_Integer ii;
69   thePlane->Coefficients(a,b,c,d);
70   for (ii=1; ii<=thePoints.Length(); ii++) {
71     const gp_XYZ& xyz = thePoints(ii).XYZ();
72     dist = Abs(a*xyz.X() + b*xyz.Y() + c*xyz.Z() + d);
73     if (dist > dfMaxDist)
74       dfMaxDist = dist;
75   }
76
77   return dfMaxDist;
78 }
79 //=======================================================================
80 //function : Is2DConnected
81 //purpose  : Return true if the last vertex of theEdge1 coincides with
82 //           the first vertex of theEdge2 in parametric space of theFace
83 //=======================================================================
84 inline static Standard_Boolean Is2DConnected(const TopoDS_Edge& theEdge1,
85                                              const TopoDS_Edge& theEdge2,
86                                              const Handle(Geom_Surface)& theSurface,
87                                              const TopLoc_Location& theLocation)
88 {
89   Standard_Real f,l;
90   //TopLoc_Location aLoc;
91   Handle(Geom2d_Curve) aCurve;
92   gp_Pnt2d p1, p2;
93
94   // get 2D points
95   aCurve=BRep_Tool::CurveOnSurface(theEdge1, theSurface, theLocation, f, l);
96   p1       = aCurve->Value( theEdge1.Orientation() == TopAbs_FORWARD ? l : f );
97   aCurve=BRep_Tool::CurveOnSurface(theEdge2, theSurface, theLocation, f, l);
98   p2       = aCurve->Value(  theEdge2.Orientation() == TopAbs_FORWARD ? f : l );
99
100   // compare 2D points
101   GeomAdaptor_Surface aSurface( theSurface );
102   TopoDS_Vertex    aV = TopExp::FirstVertex( theEdge2, Standard_True );
103   Standard_Real tol3D = BRep_Tool::Tolerance( aV );
104   Standard_Real tol2D = aSurface.UResolution( tol3D ) + aSurface.VResolution( tol3D );
105   Standard_Real dist2 = p1.SquareDistance( p2 );
106   return dist2 < tol2D * tol2D;
107 }
108
109 //=======================================================================
110 //function : Is2DClosed
111 //purpose  : Return true if edges of theShape form a closed wire in
112 //           parametric space of theSurface
113 //=======================================================================
114
115 static Standard_Boolean Is2DClosed(const TopoDS_Shape&         theShape,
116                                    const Handle(Geom_Surface)& theSurface,
117                                    const TopLoc_Location& theLocation)
118 {
119   try
120   {
121     OCC_CATCH_SIGNALS
122     // get a wire theShape 
123     TopExp_Explorer aWireExp( theShape, TopAbs_WIRE );
124     if ( !aWireExp.More() ) {
125       return Standard_False;
126     }
127     TopoDS_Wire aWire = TopoDS::Wire( aWireExp.Current() );
128     // a tmp face
129     TopoDS_Face aTmpFace = BRepLib_MakeFace( theSurface, Precision::PConfusion() );
130
131     // check topological closeness using wire explorer, if the wire is not closed
132     // the 1st and the last vertices of wire are different
133     BRepTools_WireExplorer aWireExplorer( aWire, aTmpFace );
134     if ( !aWireExplorer.More()) {
135       return Standard_False;
136     }
137     // remember the 1st and the last edges of aWire
138     TopoDS_Edge aFisrtEdge = aWireExplorer.Current(), aLastEdge = aFisrtEdge;
139     // check if edges connected topologically (that is assured by BRepTools_WireExplorer)
140     // are connected in 2D
141     TopoDS_Edge aPrevEdge = aFisrtEdge;
142     for ( aWireExplorer.Next(); aWireExplorer.More(); aWireExplorer.Next() )    {
143       aLastEdge = aWireExplorer.Current();
144       if ( !Is2DConnected( aPrevEdge, aLastEdge, theSurface, theLocation)) { 
145         return false;
146       }
147       aPrevEdge = aLastEdge;
148     }
149     // wire is closed if ( 1st vertex of aFisrtEdge ) ==
150     // ( last vertex of aLastEdge ) in 2D
151     TopoDS_Vertex aV1 = TopExp::FirstVertex( aFisrtEdge, Standard_True );
152     TopoDS_Vertex aV2 = TopExp::LastVertex( aLastEdge, Standard_True );
153     return ( aV1.IsSame( aV2 ) && Is2DConnected( aLastEdge, aFisrtEdge, theSurface, theLocation));
154   }
155   catch (Standard_Failure const&)  {
156     return Standard_False;
157   }
158 }
159 //=======================================================================
160 //function : BRepLib_FindSurface
161 //purpose  : 
162 //=======================================================================
163 BRepLib_FindSurface::BRepLib_FindSurface() 
164 {
165 }
166 //=======================================================================
167 //function : BRepLib_FindSurface
168 //purpose  : 
169 //=======================================================================
170 BRepLib_FindSurface::BRepLib_FindSurface(const TopoDS_Shape&    S, 
171                                          const Standard_Real    Tol,
172                                          const Standard_Boolean OnlyPlane,
173                                          const Standard_Boolean OnlyClosed)
174 {
175   Init(S,Tol,OnlyPlane,OnlyClosed);
176 }
177 //=======================================================================
178 //function : Init
179 //purpose  : 
180 //=======================================================================
181 void BRepLib_FindSurface::Init(const TopoDS_Shape&    S, 
182                                                  const Standard_Real    Tol,
183                                                  const Standard_Boolean OnlyPlane,
184                                const Standard_Boolean OnlyClosed)
185 {
186   myTolerance = Tol;
187   myTolReached = 0.;
188   isExisted = Standard_False;
189   myLocation.Identity();
190   mySurface.Nullify();
191
192   // compute the tolerance
193   TopExp_Explorer ex;
194
195   for (ex.Init(S,TopAbs_EDGE); ex.More(); ex.Next()) {
196     Standard_Real t = BRep_Tool::Tolerance(TopoDS::Edge(ex.Current()));
197     if (t > myTolerance) myTolerance = t;
198   }
199
200   // search an existing surface
201   ex.Init(S,TopAbs_EDGE);
202   if (!ex.More()) return;    // no edges ....
203
204   TopoDS_Edge E = TopoDS::Edge(ex.Current());
205   Standard_Real f,l,ff,ll;
206   Handle(Geom2d_Curve) PC,aPPC;
207   Handle(Geom_Surface) SS;
208   TopLoc_Location L;
209   Standard_Integer i = 0,j;
210
211   // iterate on the surfaces of the first edge
212   for(;;) {
213     i++;
214     BRep_Tool::CurveOnSurface(E,PC,mySurface,myLocation,f,l,i);
215     if (mySurface.IsNull()) {
216       break;
217     }
218     // check the other edges
219     for (ex.Init(S,TopAbs_EDGE); ex.More(); ex.Next()) {
220       if (!E.IsSame(ex.Current())) {
221         j = 0;
222         for(;;) {
223           j++;
224           BRep_Tool::CurveOnSurface(TopoDS::Edge(ex.Current()),aPPC,SS,L,ff,ll,j);
225           if (SS.IsNull()) {
226             break;
227           }
228           if ((SS == mySurface) && (L.IsEqual(myLocation))) {
229             break;
230           }
231           SS.Nullify();
232         }
233
234         if (SS.IsNull()) {
235           mySurface.Nullify();
236           break;
237         }
238       }
239     }
240
241     // if OnlyPlane, eval if mySurface is a plane.
242     if ( OnlyPlane && !mySurface.IsNull() ) 
243     {
244       if ( mySurface->IsKind( STANDARD_TYPE(Geom_RectangularTrimmedSurface)))
245         mySurface = Handle(Geom_RectangularTrimmedSurface)::DownCast(mySurface)->BasisSurface();
246       mySurface = Handle(Geom_Plane)::DownCast(mySurface);
247     }
248
249     if (!mySurface.IsNull())
250       // if S is e.g. the bottom face of a cylinder, mySurface can be the
251       // lateral (cylindrical) face of the cylinder; reject an improper mySurface
252       if ( !OnlyClosed || Is2DClosed( S, mySurface, myLocation ))
253         break;
254   }
255
256   if (!mySurface.IsNull()) {
257     isExisted = Standard_True;
258     return;
259   }
260   //
261   // no existing surface, search a plane
262   // 07/02/02 akm vvv : (OCC157) changed algorithm
263   //                    1. Collect the points along all edges of the shape
264   //                       For each point calculate the WEIGHT = sum of
265   //                       distances from neighboring points (_only_ same edge)
266   //                    2. Minimizing the weighed sum of squared deviations
267   //                       compute coefficients of the sought plane.
268
269   TColgp_SequenceOfPnt aPoints;
270   TColStd_SequenceOfReal aWeight;
271
272   // ======================= Step #1
273   for (ex.Init(S,TopAbs_EDGE); ex.More(); ex.Next()) 
274   {
275     BRepAdaptor_Curve c(TopoDS::Edge(ex.Current()));
276
277     Standard_Real dfUf = c.FirstParameter();
278     Standard_Real dfUl = c.LastParameter();
279     if (IsEqual(dfUf,dfUl)) {
280       // Degenerate
281       continue;
282     }
283     Standard_Integer iNbPoints=0;
284
285     // Add the points with weights to the sequences
286     switch (c.GetType()) 
287     {
288     case GeomAbs_BezierCurve:
289       {
290         // Put all poles for bezier
291         Handle(Geom_BezierCurve) GC = c.Bezier();
292         Standard_Integer iNbPol = GC->NbPoles();
293         Standard_Real tf = GC->FirstParameter();
294         Standard_Real tl = GC->LastParameter();
295         Standard_Real r =  (dfUl - dfUf) / (tl - tf);
296         r *= iNbPol;
297         if ( iNbPol < 2 || r < 1.)
298           // Degenerate
299           continue;
300         else
301         {
302           Handle(TColgp_HArray1OfPnt) aPoles = new (TColgp_HArray1OfPnt) (1, iNbPol);
303           GC->Poles(aPoles->ChangeArray1());
304           gp_Pnt aPolePrev = aPoles->Value(1), aPoleNext;
305           Standard_Real dfDistPrev = 0., dfDistNext;
306           for (Standard_Integer iPol=1; iPol<=iNbPol; iPol++)
307           {
308             if (iPol<iNbPol)
309             {
310               aPoleNext = aPoles->Value(iPol+1);
311               dfDistNext = aPolePrev.Distance(aPoleNext);
312             }
313             else
314               dfDistNext = 0.;
315             aPoints.Append (aPolePrev);
316             aWeight.Append (dfDistPrev+dfDistNext);
317             dfDistPrev = dfDistNext;
318             aPolePrev = aPoleNext;
319           }
320         }
321       }
322       break;
323     case GeomAbs_BSplineCurve:
324       {
325         // Put all poles for bspline
326         Handle(Geom_BSplineCurve) GC = c.BSpline();
327         Standard_Integer iNbPol = GC->NbPoles();
328         Standard_Real tf = GC->FirstParameter();
329         Standard_Real tl = GC->LastParameter();
330         Standard_Real r =  (dfUl - dfUf) / (tl - tf);
331         r *= iNbPol;
332         if ( iNbPol < 2 || r < 1.)
333           // Degenerate
334           continue;
335         else
336         {
337           Handle(TColgp_HArray1OfPnt) aPoles = new (TColgp_HArray1OfPnt) (1, iNbPol);
338           GC->Poles(aPoles->ChangeArray1());
339           gp_Pnt aPolePrev = aPoles->Value(1), aPoleNext;
340           Standard_Real dfDistPrev = 0., dfDistNext;
341           for (Standard_Integer iPol=1; iPol<=iNbPol; iPol++)
342           {
343             if (iPol<iNbPol)
344             {
345               aPoleNext = aPoles->Value(iPol+1);
346               dfDistNext = aPolePrev.Distance(aPoleNext);
347             }
348             else
349               dfDistNext = 0.;
350             aPoints.Append (aPolePrev);
351             aWeight.Append (dfDistPrev+dfDistNext);
352             dfDistPrev = dfDistNext;
353             aPolePrev = aPoleNext;
354           }
355         }
356       }
357       break;
358
359     case GeomAbs_Line:
360     case GeomAbs_Circle:
361     case GeomAbs_Ellipse:
362     case GeomAbs_Hyperbola:
363     case GeomAbs_Parabola:
364       // Two points on straight segment, Four points on otheranalitical curves
365       iNbPoints = (c.GetType() == GeomAbs_Line ? 2 : 4);
366       Standard_FALLTHROUGH
367     default:
368       { 
369         // Put some points on other curves
370         if (iNbPoints==0)
371           iNbPoints = 15 + c.NbIntervals(GeomAbs_C3);
372         Standard_Real dfDelta = (dfUl-dfUf)/(iNbPoints-1);
373         Standard_Integer iPoint;
374         Standard_Real dfU;
375         gp_Pnt aPointPrev = c.Value(dfUf), aPointNext;
376         Standard_Real dfDistPrev = 0., dfDistNext;
377         for (iPoint=1, dfU=dfUf+dfDelta; 
378           iPoint<=iNbPoints; 
379           iPoint++, dfU+=dfDelta) 
380         {
381           if (iPoint<iNbPoints)
382           {
383             aPointNext = c.Value(dfU);
384             dfDistNext = aPointPrev.Distance(aPointNext);
385           }
386           else
387             dfDistNext = 0.;
388           aPoints.Append (aPointPrev);
389           aWeight.Append (dfDistPrev+dfDistNext);
390           dfDistPrev = dfDistNext;
391           aPointPrev = aPointNext;
392         }
393       } // default:
394     } // switch (c.GetType()) ...
395   } // for (ex.Init(S,TopAbs_EDGE); ex.More() && control; ex.Next()) ...
396
397   if (aPoints.Length() < 3) {
398     return;
399   }
400
401   // ======================= Step #2
402   myLocation.Identity();
403   Standard_Integer iPoint;
404   math_Matrix aMat (1,3,1,3, 0.);
405   math_Vector aVec (1,3, 0.);
406   // Find the barycenter and normalize weights 
407   Standard_Real dfMaxWeight=0.;
408   gp_XYZ aBaryCenter(0.,0.,0.);
409   Standard_Real dfSumWeight=0.;
410   for (iPoint=1; iPoint<=aPoints.Length(); iPoint++)  {
411     Standard_Real dfW = aWeight(iPoint);
412     aBaryCenter += dfW*aPoints(iPoint).XYZ();
413     dfSumWeight += dfW;
414     if (dfW > dfMaxWeight) {
415       dfMaxWeight = dfW;
416     }
417   }
418   aBaryCenter /= dfSumWeight;
419
420   // Fill the matrix and the right vector
421   for (iPoint=1; iPoint<=aPoints.Length(); iPoint++)  {
422     gp_XYZ p=aPoints(iPoint).XYZ()-aBaryCenter;
423     Standard_Real w=aWeight(iPoint)/dfMaxWeight;
424     aMat(1,1)+=w*p.X()*p.X(); 
425     aMat(1,2)+=w*p.X()*p.Y(); 
426     aMat(1,3)+=w*p.X()*p.Z();
427     //  
428     aMat(2,2)+=w*p.Y()*p.Y();  
429     aMat(2,3)+=w*p.Y()*p.Z();
430     //  
431     aMat(3,3)+=w*p.Z()*p.Z();
432   }
433   aMat(2,1) = aMat(1,2);
434   aMat(3,1) = aMat(1,3);
435   aMat(3,2) = aMat(2,3);
436   //
437   math_Jacobi anEignval(aMat);
438   math_Vector anEVals(1,3);
439   Standard_Boolean isSolved = anEignval.IsDone();
440   Standard_Integer isol = 0;
441   if(isSolved)
442   {
443     anEVals = anEignval.Values();
444     //We need vector with eigenvalue ~ 0.
445     Standard_Real anEMin = RealLast();
446     Standard_Real anEMax = -anEMin;
447     for(i = 1; i <= 3; ++i)
448     {
449       Standard_Real anE = Abs(anEVals(i));
450       if(anEMin > anE)
451       {
452         anEMin = anE;
453         isol = i;
454       }
455       if(anEMax < anE)
456       {
457         anEMax = anE;
458       }
459     }
460     
461     if(isol == 0)
462     {
463       isSolved = Standard_False;
464     }
465     else
466     {
467       Standard_Real eps = Epsilon(anEMax);
468       if(anEMin <= eps)
469       {
470         anEignval.Vector(isol, aVec);
471       }
472       else
473       {
474         //try using vector product of other axes
475         Standard_Integer ind[2] = {0,0};
476         for(i = 1; i <= 3; ++i)
477         {
478           if(i == isol)
479           {
480             continue;
481           }
482           if(ind[0] == 0)
483           {
484             ind[0] = i;
485             continue;
486           }
487           if(ind[1] == 0)
488           {
489             ind[1] = i;
490             continue;
491           }
492         }
493         math_Vector aVec1(1, 3, 0.), aVec2(1, 3, 0.);
494         anEignval.Vector(ind[0], aVec1);
495         anEignval.Vector(ind[1], aVec2);
496         gp_Vec aV1(aVec1(1), aVec1(2), aVec1(3));
497         gp_Vec aV2(aVec2(1), aVec2(2), aVec2(3));
498         gp_Vec aN = aV1^ aV2;
499         aVec(1) = aN.X();
500         aVec(2) = aN.Y();
501         aVec(3) = aN.Z();
502       }
503       if (aVec.Norm2() < gp::Resolution()) {
504         isSolved = Standard_False;
505       }
506     }
507   }
508     
509   //
510   //  let us be more tolerant (occ415)
511   Standard_Real dfDist = RealLast();
512   Handle(Geom_Plane) aPlane;
513   //
514   if (isSolved)  {
515     //Plane normal can have two directions, direction is chosen
516     //according to direction of eigenvector
517     gp_Vec anN(aVec(1), aVec(2), aVec(3));
518     aPlane = new Geom_Plane(aBaryCenter,anN);
519     dfDist = Controle (aPoints, aPlane);
520   }
521   //
522   if (!isSolved || myTolerance < dfDist)  {
523     gp_Pnt aFirstPnt=aPoints(1);
524     for (iPoint=2; iPoint<=aPoints.Length(); iPoint++)  {
525       gp_Vec aDir(aFirstPnt,aPoints(iPoint));
526       Standard_Real dfSide=aDir.Magnitude();
527       if (dfSide<myTolerance) {
528         continue; // degeneration
529       }
530       for (Standard_Integer iP1=iPoint+1; iP1<=aPoints.Length(); iP1++) {
531
532         gp_Vec aCross = gp_Vec(aFirstPnt,aPoints(iP1)) ^ aDir ;
533
534         if (aCross.Magnitude() > dfSide*myTolerance) {
535           Handle(Geom_Plane) aPlane2 = new Geom_Plane(aBaryCenter, aCross);
536           Standard_Real dfDist2 = Controle (aPoints, aPlane2);
537           if (dfDist2 < myTolerance)  {
538             myTolReached = dfDist2;
539             mySurface = aPlane2;
540             return;
541           }
542           if (dfDist2 < dfDist)  {
543             dfDist = dfDist2;
544             aPlane = aPlane2;
545           }
546         }
547       }
548     }
549   }
550   //
551   //XXf
552   //static Standard_Real weakness = 5.0;
553   Standard_Real weakness = 5.0;
554   //XXf
555   if(dfDist <= myTolerance || (dfDist < myTolerance*weakness && Tol<0)) { 
556     //XXf 
557     //myTolReached = dfDist;
558     //XXt
559     mySurface = aPlane;
560     //If S is wire, try to orient surface according to orientation of wire.
561     if(S.ShapeType() == TopAbs_WIRE && S.Closed())
562     {
563        //
564       TopoDS_Wire aW = TopoDS::Wire(S);
565       TopoDS_Face aTmpFace = BRepLib_MakeFace(mySurface, Precision::Confusion());
566       BRep_Builder BB;
567       BB.Add(aTmpFace, aW);
568       BRepTopAdaptor_FClass2d FClass(aTmpFace, 0.);
569       if ( FClass.PerformInfinitePoint() == TopAbs_IN ) 
570       {
571         gp_Dir aN = aPlane->Position().Direction();
572         aN.Reverse();
573         mySurface = new Geom_Plane(aPlane->Position().Location(), aN);
574       }
575
576     }
577   }
578   //XXf
579   myTolReached = dfDist;
580   //XXt
581 }
582 //=======================================================================
583 //function : Found
584 //purpose  : 
585 //=======================================================================
586 Standard_Boolean BRepLib_FindSurface::Found() const 
587 {
588   return !mySurface.IsNull();
589 }
590 //=======================================================================
591 //function : Surface
592 //purpose  : 
593 //=======================================================================
594 Handle(Geom_Surface) BRepLib_FindSurface::Surface() const 
595 {
596   return mySurface;
597 }
598 //=======================================================================
599 //function : Tolerance
600 //purpose  : 
601 //=======================================================================
602 Standard_Real BRepLib_FindSurface::Tolerance() const 
603 {
604   return myTolerance;
605 }
606 //=======================================================================
607 //function : ToleranceReached
608 //purpose  : 
609 //=======================================================================
610 Standard_Real BRepLib_FindSurface::ToleranceReached() const 
611 {
612   return myTolReached;
613 }
614 //=======================================================================
615 //function : Existed
616 //purpose  : 
617 //=======================================================================
618 Standard_Boolean BRepLib_FindSurface::Existed() const 
619 {
620   return isExisted;
621 }
622 //=======================================================================
623 //function : Location
624 //purpose  : 
625 //=======================================================================
626 TopLoc_Location BRepLib_FindSurface::Location() const
627 {
628   return myLocation;
629 }
630