1 // Created on: 1996-07-15
2 // Created by: Laurent BUCHARD
3 // Copyright (c) 1996-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.
17 // Modified by skv - Thu Sep 4 11:22:05 2003 OCC578
19 #include <BRep_Tool.hxx>
20 #include <BRepClass3d_Intersector3d.hxx>
21 #include <BRepClass3d_SClassifier.hxx>
22 #include <BRepClass3d_SolidExplorer.hxx>
23 #include <BRepTopAdaptor_FClass2d.hxx>
25 #include <Geom_Surface.hxx>
29 #include <IntCurvesFace_Intersector.hxx>
30 #include <math_BullardGenerator.hxx>
31 #include <Standard_DomainError.hxx>
33 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
34 #include <TopTools_MapOfShape.hxx>
36 #include <BRepAdaptor_Surface.hxx>
37 #include <Extrema_ExtPS.hxx>
41 // modified by NIZHNY-MKK Mon Jun 21 15:13:40 2004
43 Standard_Boolean FaceNormal (const TopoDS_Face& aF,
44 const Standard_Real U,
45 const Standard_Real V,
49 Standard_Real GetAddToParam(const gp_Lin& L,const Standard_Real P,const Bnd_Box& B);
51 //gets transition of line <L> passing through/near the edge <e> of faces <f1>, <f2>. <param> is
52 // a parameter on the edge where the minimum distance between <l> and <e> was found
53 static Standard_Integer GetTransi(const TopoDS_Face& f1, const TopoDS_Face& f2, const TopoDS_Edge e,
54 Standard_Real param, const gp_Lin& L, IntCurveSurface_TransitionOnCurve& trans);
56 static Standard_Boolean GetNormalOnFaceBound(const TopoDS_Edge& E, const TopoDS_Face& F, Standard_Real param, gp_Dir& OutDir);
58 static void Trans(Standard_Real parmin, IntCurveSurface_TransitionOnCurve& tran, int& state);
60 //=======================================================================
61 //function : BRepClass3d_SClassifier
63 //=======================================================================
64 BRepClass3d_SClassifier::BRepClass3d_SClassifier()
69 //=======================================================================
70 //function : BRepClass3d_SClassifier
72 //=======================================================================
73 BRepClass3d_SClassifier::BRepClass3d_SClassifier(BRepClass3d_SolidExplorer& S,
75 const Standard_Real Tol) {
77 myState=3; //-- in ds solid case without face
85 //=======================================================================
86 //function : PerformInfinitePoint
88 //=======================================================================
89 void BRepClass3d_SClassifier::PerformInfinitePoint(BRepClass3d_SolidExplorer& aSE,
90 const Standard_Real /*Tol*/) {
92 //Take a normal to the first extracted face in its random inner point
93 //and intersect this reversed normal with the faces of the solid.
94 //If the min.par.-intersection point is
95 // a) inner point of a face
96 // b) transition is not TANGENT
97 // (the line does not touch the face but pierces it)
98 //then set <myState> to IN or OUT according to transition
99 //else take the next random point inside the min.par.-intersected face
102 if(aSE.Reject(gp_Pnt(0,0,0))) {
103 myState=3; //-- in ds solid case without face
107 //------------------------------------------------------------
109 Standard_Boolean bFound;
110 Standard_Real aParam, aU = 0., aV = 0.;
114 math_BullardGenerator aRandomGenerator;
118 // Collect faces in sequence to iterate
119 std::vector<TopoDS_Face> aFaces;
120 for (aSE.InitShell(); aSE.MoreShell(); aSE.NextShell())
122 for (aSE.InitFace(); aSE.MoreFace(); aSE.NextFace())
124 aFaces.push_back (aSE.CurrentFace());
128 // iteratively try up to 10 probing points from each face
129 const Standard_Integer NB_MAX_POINTS_PER_FACE = 10;
130 for (Standard_Integer itry = 0; itry < NB_MAX_POINTS_PER_FACE; itry++)
132 for (std::vector<TopoDS_Face>::iterator iFace = aFaces.begin(); iFace != aFaces.end(); ++iFace)
134 TopoDS_Face aF = *iFace;
136 TopAbs_State aState = TopAbs_OUT;
137 IntCurveSurface_TransitionOnCurve aTransition = IntCurveSurface_Tangent;
139 aParam = 0.1 + 0.8 * aRandomGenerator.NextReal(); // random number in range [0.1, 0.9]
140 bFound = aSE.FindAPointInTheFace(aF, aPoint, aU, aV, aParam);
141 if (!bFound || !FaceNormal(aF, aU, aV, aDN))
144 gp_Lin aLin(aPoint, -aDN);
145 Standard_Real parmin = RealLast();
146 for (aSE.InitShell();aSE.MoreShell();aSE.NextShell()) {
147 if (aSE.RejectShell(aLin) == Standard_False) {
148 for (aSE.InitFace();aSE.MoreFace(); aSE.NextFace()) {
149 if (aSE.RejectFace(aLin) == Standard_False) {
150 TopoDS_Shape aLocalShape = aSE.CurrentFace();
151 TopoDS_Face CurFace = TopoDS::Face(aLocalShape);
152 IntCurvesFace_Intersector& Intersector3d = aSE.Intersector(CurFace);
153 Intersector3d.Perform(aLin,-RealLast(),parmin);
155 if(Intersector3d.IsDone()) {
156 if(Intersector3d.NbPnt()) {
157 Standard_Integer imin = 1;
158 for (Standard_Integer i = 2; i <= Intersector3d.NbPnt(); i++)
159 if (Intersector3d.WParameter(i) < Intersector3d.WParameter(imin))
161 parmin = Intersector3d.WParameter(imin);
162 aState = Intersector3d.State(imin);
163 aTransition = Intersector3d.Transition(imin);
171 } //end of loop on the whole solid
173 if (aState == TopAbs_IN)
175 if (aTransition == IntCurveSurface_Out) {
176 //-- The line is going from inside the solid to outside
178 myState = 3; //-- IN --
181 else if (aTransition == IntCurveSurface_In) {
182 myState = 4; //-- OUT --
186 } // iteration by faces
187 } // iteration by points
190 //=======================================================================
193 //=======================================================================
194 void BRepClass3d_SClassifier::Perform(BRepClass3d_SolidExplorer& SolidExplorer,
196 const Standard_Real Tol)
198 if(SolidExplorer.Reject(P))
200 // Solid without faces => the whole space. Always in.
205 const BRepClass3d_BndBoxTree & aTree = SolidExplorer.GetTree();
206 const TopTools_IndexedMapOfShape & aMapEV = SolidExplorer.GetMapEV();
208 // Vertices/Edges vs Point.
209 BRepClass3d_BndBoxTreeSelectorPoint aSelectorPoint(aMapEV);
210 aSelectorPoint.SetCurrentPoint(P);
212 Standard_Integer SelsVE = 0;
213 SelsVE = aTree.Select(aSelectorPoint);
217 // The point P lays inside the tolerance area of vertices/edges => return ON state.
222 TopTools_IndexedDataMapOfShapeListOfShape mapEF;
223 TopExp::MapShapesAndAncestors(SolidExplorer.GetShape(), TopAbs_EDGE, TopAbs_FACE, mapEF);
225 BRepClass3d_BndBoxTreeSelectorLine aSelectorLine(aMapEV);
233 // We compute the intersection between the line built in the Solid Explorer and the shape.
234 //-- --------------------------------------------------------------------------------
235 // Calculate intersection with the face closest to the direction of bounding boxes
236 // by priority so that to have the smallest possible parmin.
237 // Optimization to produce as much as possible rejections with other faces.
238 Standard_Integer iFlag;
240 // If found line passes through a bound of any face, it means that the line
241 // is not found properly and it is necessary to repeat whole procedure.
242 // That's why the main loop while is added.
243 Standard_Boolean isFaultyLine = Standard_True;
244 Standard_Integer anIndFace = 0;
245 Standard_Real parmin = 0.0;
249 iFlag = SolidExplorer.Segment(P,L,Par);
251 iFlag = SolidExplorer.OtherSegment(P,L,Par);
253 Standard_Integer aCurInd = SolidExplorer.GetFaceSegmentIndex();
255 if (aCurInd > anIndFace)
259 myState = 1; // Faulty.
265 // IsOnFace iFlag==1 i.e face is Infinite
275 // Check if the point is ON surface but OUT of the face.
276 // Just skip this face because it is bad for classification.
280 isFaultyLine = Standard_False;
283 Standard_Real NearFaultPar = RealLast(); // Parameter on line.
284 aSelectorLine.ClearResults();
285 aSelectorLine.SetCurrentLine(L, Par);
286 Standard_Integer SelsEVL = 0;
287 SelsEVL = aTree.Select(aSelectorLine); //SelsEE > 0 => Line/Edges & Line/Vertex intersection
291 // Line and edges / vertices interference.
292 Standard_Integer VLInterNb = aSelectorLine.GetNbVertParam();
293 TopoDS_Vertex NearIntVert;
294 TopTools_MapOfShape LVInts;
295 for (Standard_Integer i = 1; i <= VLInterNb; i++)
298 Standard_Real LP = 0;
300 aSelectorLine.GetVertParam(i, V, LP);
303 if (Abs(LP) < Abs(NearFaultPar))
307 Standard_Real param = 0.0;
309 Standard_Real Lpar = RealLast();
310 for (Standard_Integer i = 1; i <= aSelectorLine.GetNbEdgeParam(); i++)
313 aSelectorLine.GetEdgeParam(i, EE, param, Lpar);
314 const TopTools_ListOfShape& ffs = mapEF.FindFromKey(EE); //ffs size == 2
315 if (ffs.Extent() != 2)
317 TopoDS_Face f1 = TopoDS::Face(ffs.First());
318 TopoDS_Face f2 = TopoDS::Face(ffs.Last());
319 TopoDS_Vertex V1, V2;
320 TopExp::Vertices(EE, V1, V2);
321 if (LVInts.Contains(V1) || LVInts.Contains(V2))
326 IntCurveSurface_TransitionOnCurve tran = IntCurveSurface_Tangent;
327 Standard_Integer Tst = GetTransi(f1, f2, EE, param, L, tran);
328 if (Tst == 1 && Abs(Lpar) < Abs(parmin))
331 Trans(parmin, tran, myState);
333 else if (Abs(Lpar) < Abs(NearFaultPar))
338 for(SolidExplorer.InitShell();
339 SolidExplorer.MoreShell() && !isFaultyLine;
340 SolidExplorer.NextShell())
342 if(SolidExplorer.RejectShell(L) == Standard_False)
344 for (SolidExplorer.InitFace();
345 SolidExplorer.MoreFace() && !isFaultyLine;
346 SolidExplorer.NextFace())
348 if (SolidExplorer.RejectFace(L) == Standard_False)
350 TopoDS_Shape aLocalShape = SolidExplorer.CurrentFace();
351 TopoDS_Face f = TopoDS::Face(aLocalShape);
352 IntCurvesFace_Intersector& Intersector3d = SolidExplorer.Intersector(f);
354 // Prolong segment, since there are cases when
355 // the intersector does not find intersection points with the original
356 // segment due to rough triangulation of a parameterized surface.
357 Standard_Real addW = Max(10 * Tol, 0.01*Par);
358 Standard_Real AddW = addW;
360 Bnd_Box aBoxF = Intersector3d.Bounding();
362 // The box must be finite in order to correctly prolong the segment to its bounds.
363 if (!aBoxF.IsVoid() && !aBoxF.IsWhole())
365 Standard_Real aXmin, aYmin, aZmin, aXmax, aYmax, aZmax;
366 aBoxF.Get(aXmin, aYmin, aZmin, aXmax, aYmax, aZmax);
368 Standard_Real boxaddW = GetAddToParam(L, Par, aBoxF);
369 addW = Max(addW, boxaddW);
372 Standard_Real minW = -AddW;
373 Standard_Real maxW = Min(Par * 10, Par + addW);
374 Intersector3d.Perform(L, minW, maxW);
375 if (Intersector3d.IsDone())
377 if (Intersector3d.NbPnt() == 0)
379 if (Intersector3d.IsParallel())
381 //Check distance between surface and point
382 BRepAdaptor_Surface aBAS(f, Standard_False);
383 Extrema_ExtPS aProj(P, aBAS, Precision::PConfusion(), Precision::PConfusion());
384 if (aProj.IsDone() && aProj.NbExt() > 0)
386 Standard_Integer i, indmin = 0;
387 Standard_Real d = RealLast();
388 for (i = 1; i <= aProj.NbExt(); ++i)
390 if (aProj.SquareDistance(i) < d)
392 d = aProj.SquareDistance(i);
400 const Extrema_POnSurf& aPonS = aProj.Point(indmin);
401 Standard_Real anU, anV;
402 aPonS.Parameter(anU, anV);
403 gp_Pnt2d aP2d(anU, anV);
404 TopAbs_State aSt = Intersector3d.ClassifyUVPoint(aP2d);
405 if (aSt == TopAbs_IN || aSt == TopAbs_ON)
417 for (Standard_Integer i = 1; i <= Intersector3d.NbPnt(); i++)
419 if (Abs(Intersector3d.WParameter(i)) < Abs(parmin) - Precision::PConfusion())
421 parmin = Intersector3d.WParameter(i);
422 TopAbs_State aState = Intersector3d.State(i);
423 if (Abs(parmin) <= Tol)
429 // Treatment of case TopAbs_ON separately.
430 else if (aState == TopAbs_IN)
432 //-- The intersection point between the line and a face F
433 // -- of the solid is in the face F
435 IntCurveSurface_TransitionOnCurve tran = Intersector3d.Transition(i);
436 if (tran == IntCurveSurface_Tangent)
439 std::cout<<"*Problem ds BRepClass3d_SClassifier.cxx"<<std::endl;
441 continue; // ignore this point
444 Trans(parmin, tran, myState);
447 // If the state is TopAbs_ON, it is necessary to chose
448 // another line and to repeat the whole procedure.
449 else if (aState == TopAbs_ON)
451 isFaultyLine = Standard_True;
457 //-- No point has been found by the Intersector3d.
458 //-- Or a Point has been found with a greater parameter.
460 } //-- loop by intersection points
465 } //-- Face has not been rejected
469 }//-- Exploration of the faces
474 } //-- Shell has not been rejected
477 } //-- Exploration of the shells
479 if (NearFaultPar != RealLast() &&
480 Abs(parmin) >= Abs(NearFaultPar) - Precision::PConfusion())
482 isFaultyLine = Standard_True;
487 //#################################################
488 SolidExplorer.DumpSegment(P,L,parmin,State());
489 //#################################################
494 TopAbs_State BRepClass3d_SClassifier::State() const
498 else if(myState == 3)
500 else if(myState == 4)
503 // return OUT state when there is an error during execution.
507 TopoDS_Face BRepClass3d_SClassifier::Face() const {
511 Standard_Boolean BRepClass3d_SClassifier::Rejected() const {
516 Standard_Boolean BRepClass3d_SClassifier::IsOnAFace() const {
521 void BRepClass3d_SClassifier::ForceIn() {
525 void BRepClass3d_SClassifier::ForceOut() {
529 Standard_Real GetAddToParam(const gp_Lin& L,
530 const Standard_Real P,
533 Standard_Real aXmin, aYmin, aZmin, aXmax, aYmax, aZmax;
534 B.Get(aXmin, aYmin, aZmin, aXmax, aYmax, aZmax);
535 Standard_Real x[2] = {aXmin,aXmax}, y[2] = {aYmin,aYmax}, z[2] = {aZmin,aZmax};
536 Standard_Integer i = 0, j = 0, k = 0;
537 Standard_Real Par = P;
538 for(i = 0 ; i < 2; i++) {
539 for(j = 0; j < 2; j++) {
540 for(k = 0; k < 2; k++) {
541 Standard_Real X = fabs(x[i]-L.Location().X());
542 Standard_Real Y = fabs(y[j]-L.Location().Y());
543 Standard_Real Z = fabs(z[k]-L.Location().Z());
544 if(X < 1.e+20 && Y < 1.e+20 && Z < 1.e+20) {
545 gp_Pnt aP(x[i],y[j],z[k]);
546 Standard_Real par = ElCLib::Parameter(L,aP);
557 //=======================================================================
558 //function : FaceNormal
560 //=======================================================================
561 Standard_Boolean FaceNormal (const TopoDS_Face& aF,
562 const Standard_Real U,
563 const Standard_Real V,
567 gp_Vec aD1U, aD1V, aN;
568 Handle(Geom_Surface) aS;
570 aS=BRep_Tool::Surface(aF);
571 aS->D1 (U, V, aPnt, aD1U, aD1V);
572 aN=aD1U.Crossed(aD1V);
573 if (aN.Magnitude() <= gp::Resolution())
574 return Standard_False;
577 aDN.SetXYZ(aN.XYZ());
578 if (aF.Orientation() == TopAbs_REVERSED){
581 return Standard_True;
584 //=======================================================================
585 //function : GetNormalOnFaceBound
587 //=======================================================================
588 static Standard_Boolean GetNormalOnFaceBound(const TopoDS_Edge& E,
589 const TopoDS_Face& F,
590 const Standard_Real param,
593 Standard_Real f = 0, l = 0;
596 Handle(Geom2d_Curve) c2d = BRep_Tool::CurveOnSurface(E, F, f, l);
598 return Standard_False;
599 if (param < f || param > l)
600 return Standard_False;
602 if (!FaceNormal(F, P2d.X(), P2d.Y(), OutDir))
603 return Standard_False;
604 return Standard_True;
607 //=======================================================================
608 //function : GetTransi
610 //=======================================================================
611 static Standard_Integer GetTransi(const TopoDS_Face& f1,
612 const TopoDS_Face& f2,
614 const Standard_Real param,
616 IntCurveSurface_TransitionOnCurve& trans)
621 //-1 => probably a faulty line
623 if (!GetNormalOnFaceBound(e, f1, param, nf1))
625 if (!GetNormalOnFaceBound(e, f2, param, nf2))
628 const gp_Dir& LDir = L.Direction();
630 if(Abs(LDir.Dot(nf1)) < Precision::Angular() || Abs(LDir.Dot(nf2)) < Precision::Angular())
632 //line is orthogonal to normal(s)
633 //trans = IntCurveSurface_Tangent;
637 if (nf1.IsParallel(nf2, Precision::Angular()))
639 Standard_Real angD = nf1.Dot(LDir);
640 if (Abs(angD) < Precision::Angular())
643 trans = IntCurveSurface_Out;
644 else //angD < -Precision::Angular())
645 trans = IntCurveSurface_In;
650 gp_Dir ProjL = N.XYZ() ^ LDir.XYZ() ^ N.XYZ(); //proj LDir on the plane defined by nf1/nf2 directions
652 Standard_Real fAD = nf1.Dot(ProjL);
653 Standard_Real sAD = nf2.Dot(ProjL);
655 if (fAD < -Precision::Angular() && sAD < -Precision::Angular())
656 trans = IntCurveSurface_In;
657 else if (fAD > Precision::Angular() && sAD > Precision::Angular())
658 trans = IntCurveSurface_Out;
664 //=======================================================================
667 //=======================================================================
668 static void Trans(const Standard_Real parmin,
669 IntCurveSurface_TransitionOnCurve& tran,
672 // if parmin is negative we should reverse transition
674 tran = (tran == IntCurveSurface_Out ? IntCurveSurface_In : IntCurveSurface_Out);
676 if(tran == IntCurveSurface_Out)
677 //-- The line is going from inside the solid to outside