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
6 // This file is part of Open CASCADE Technology software library.
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.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
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>
35 #include <gp_Circ.hxx>
36 #include <gp_Elips.hxx>
37 #include <gp_Hypr.hxx>
39 #include <gp_Parab.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>
52 #include <TopExp_Explorer.hxx>
53 #include <TopLoc_Location.hxx>
55 #include <TopoDS_Shape.hxx>
56 #include <TopoDS_Vertex.hxx>
57 #include <TopoDS_Wire.hxx>
59 //=======================================================================
62 //=======================================================================
63 static Standard_Real Controle(const TColgp_SequenceOfPnt& thePoints,
64 const Handle(Geom_Plane)& thePlane)
66 Standard_Real dfMaxDist=0.;
67 Standard_Real a,b,c,d, dist;
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);
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)
90 //TopLoc_Location aLoc;
91 Handle(Geom2d_Curve) aCurve;
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 );
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;
109 //=======================================================================
110 //function : Is2DClosed
111 //purpose : Return true if edges of theShape form a closed wire in
112 // parametric space of theSurface
113 //=======================================================================
115 static Standard_Boolean Is2DClosed(const TopoDS_Shape& theShape,
116 const Handle(Geom_Surface)& theSurface,
117 const TopLoc_Location& theLocation)
122 // get a wire theShape
123 TopExp_Explorer aWireExp( theShape, TopAbs_WIRE );
124 if ( !aWireExp.More() ) {
125 return Standard_False;
127 TopoDS_Wire aWire = TopoDS::Wire( aWireExp.Current() );
129 TopoDS_Face aTmpFace = BRepLib_MakeFace( theSurface, Precision::PConfusion() );
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;
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)) {
147 aPrevEdge = aLastEdge;
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));
155 catch (Standard_Failure const&) {
156 return Standard_False;
159 //=======================================================================
160 //function : BRepLib_FindSurface
162 //=======================================================================
163 BRepLib_FindSurface::BRepLib_FindSurface()
166 //=======================================================================
167 //function : BRepLib_FindSurface
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)
175 Init(S,Tol,OnlyPlane,OnlyClosed);
177 //=======================================================================
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)
188 isExisted = Standard_False;
189 myLocation.Identity();
192 // compute the tolerance
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;
200 // search an existing surface
201 ex.Init(S,TopAbs_EDGE);
202 if (!ex.More()) return; // no edges ....
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;
209 Standard_Integer i = 0,j;
211 // iterate on the surfaces of the first edge
214 BRep_Tool::CurveOnSurface(E,PC,mySurface,myLocation,f,l,i);
215 if (mySurface.IsNull()) {
218 // check the other edges
219 for (ex.Init(S,TopAbs_EDGE); ex.More(); ex.Next()) {
220 if (!E.IsSame(ex.Current())) {
224 BRep_Tool::CurveOnSurface(TopoDS::Edge(ex.Current()),aPPC,SS,L,ff,ll,j);
228 if ((SS == mySurface) && (L.IsEqual(myLocation))) {
241 // if OnlyPlane, eval if mySurface is a plane.
242 if ( OnlyPlane && !mySurface.IsNull() )
244 if ( mySurface->IsKind( STANDARD_TYPE(Geom_RectangularTrimmedSurface)))
245 mySurface = Handle(Geom_RectangularTrimmedSurface)::DownCast(mySurface)->BasisSurface();
246 mySurface = Handle(Geom_Plane)::DownCast(mySurface);
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 ))
256 if (!mySurface.IsNull()) {
257 isExisted = Standard_True;
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.
269 TColgp_SequenceOfPnt aPoints;
270 TColStd_SequenceOfReal aWeight;
272 // ======================= Step #1
273 for (ex.Init(S,TopAbs_EDGE); ex.More(); ex.Next())
275 BRepAdaptor_Curve c(TopoDS::Edge(ex.Current()));
277 Standard_Real dfUf = c.FirstParameter();
278 Standard_Real dfUl = c.LastParameter();
279 if (IsEqual(dfUf,dfUl)) {
283 Standard_Integer iNbPoints=0;
285 // Add the points with weights to the sequences
288 case GeomAbs_BezierCurve:
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);
297 if ( iNbPol < 2 || r < 1.)
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++)
310 aPoleNext = aPoles->Value(iPol+1);
311 dfDistNext = aPolePrev.Distance(aPoleNext);
315 aPoints.Append (aPolePrev);
316 aWeight.Append (dfDistPrev+dfDistNext);
317 dfDistPrev = dfDistNext;
318 aPolePrev = aPoleNext;
323 case GeomAbs_BSplineCurve:
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);
332 if ( iNbPol < 2 || r < 1.)
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++)
345 aPoleNext = aPoles->Value(iPol+1);
346 dfDistNext = aPolePrev.Distance(aPoleNext);
350 aPoints.Append (aPolePrev);
351 aWeight.Append (dfDistPrev+dfDistNext);
352 dfDistPrev = dfDistNext;
353 aPolePrev = aPoleNext;
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);
369 // Put some points on other curves
371 iNbPoints = 15 + c.NbIntervals(GeomAbs_C3);
372 Standard_Real dfDelta = (dfUl-dfUf)/(iNbPoints-1);
373 Standard_Integer iPoint;
375 gp_Pnt aPointPrev = c.Value(dfUf), aPointNext;
376 Standard_Real dfDistPrev = 0., dfDistNext;
377 for (iPoint=1, dfU=dfUf+dfDelta;
379 iPoint++, dfU+=dfDelta)
381 if (iPoint<iNbPoints)
383 aPointNext = c.Value(dfU);
384 dfDistNext = aPointPrev.Distance(aPointNext);
388 aPoints.Append (aPointPrev);
389 aWeight.Append (dfDistPrev+dfDistNext);
390 dfDistPrev = dfDistNext;
391 aPointPrev = aPointNext;
394 } // switch (c.GetType()) ...
395 } // for (ex.Init(S,TopAbs_EDGE); ex.More() && control; ex.Next()) ...
397 if (aPoints.Length() < 3) {
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();
414 if (dfW > dfMaxWeight) {
418 aBaryCenter /= dfSumWeight;
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();
428 aMat(2,2)+=w*p.Y()*p.Y();
429 aMat(2,3)+=w*p.Y()*p.Z();
431 aMat(3,3)+=w*p.Z()*p.Z();
433 aMat(2,1) = aMat(1,2);
434 aMat(3,1) = aMat(1,3);
435 aMat(3,2) = aMat(2,3);
437 math_Jacobi anEignval(aMat);
438 math_Vector anEVals(1,3);
439 Standard_Boolean isSolved = anEignval.IsDone();
440 Standard_Integer isol = 0;
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)
449 Standard_Real anE = Abs(anEVals(i));
463 isSolved = Standard_False;
467 Standard_Real eps = Epsilon(anEMax);
470 anEignval.Vector(isol, aVec);
474 //try using vector product of other axes
475 Standard_Integer ind[2] = {0,0};
476 for(i = 1; i <= 3; ++i)
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;
503 if (aVec.Norm2() < gp::Resolution()) {
504 isSolved = Standard_False;
510 // let us be more tolerant (occ415)
511 Standard_Real dfDist = RealLast();
512 Handle(Geom_Plane) aPlane;
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);
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
530 for (Standard_Integer iP1=iPoint+1; iP1<=aPoints.Length(); iP1++) {
532 gp_Vec aCross = gp_Vec(aFirstPnt,aPoints(iP1)) ^ aDir ;
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;
542 if (dfDist2 < dfDist) {
552 //static Standard_Real weakness = 5.0;
553 Standard_Real weakness = 5.0;
555 if(dfDist <= myTolerance || (dfDist < myTolerance*weakness && Tol<0)) {
557 //myTolReached = dfDist;
560 //If S is wire, try to orient surface according to orientation of wire.
561 if(S.ShapeType() == TopAbs_WIRE && S.Closed())
564 TopoDS_Wire aW = TopoDS::Wire(S);
565 TopoDS_Face aTmpFace = BRepLib_MakeFace(mySurface, Precision::Confusion());
567 BB.Add(aTmpFace, aW);
568 BRepTopAdaptor_FClass2d FClass(aTmpFace, 0.);
569 if ( FClass.PerformInfinitePoint() == TopAbs_IN )
571 gp_Dir aN = aPlane->Position().Direction();
573 mySurface = new Geom_Plane(aPlane->Position().Location(), aN);
579 myTolReached = dfDist;
582 //=======================================================================
585 //=======================================================================
586 Standard_Boolean BRepLib_FindSurface::Found() const
588 return !mySurface.IsNull();
590 //=======================================================================
593 //=======================================================================
594 Handle(Geom_Surface) BRepLib_FindSurface::Surface() const
598 //=======================================================================
599 //function : Tolerance
601 //=======================================================================
602 Standard_Real BRepLib_FindSurface::Tolerance() const
606 //=======================================================================
607 //function : ToleranceReached
609 //=======================================================================
610 Standard_Real BRepLib_FindSurface::ToleranceReached() const
614 //=======================================================================
617 //=======================================================================
618 Standard_Boolean BRepLib_FindSurface::Existed() const
622 //=======================================================================
623 //function : Location
625 //=======================================================================
626 TopLoc_Location BRepLib_FindSurface::Location() const