src/BRepClass3d/BRepClass3d_SolidExplorer.cxx

   1 // Created on: 1994-03-10
   2 // Created by: Laurent BUCHARD
   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 // Modifed:     Porting NT 7-5-97 DPF (stdio.h)
  18 //              Apr 16 2002 eap, classification against infinite solid (occ299)
  19
  20
  21 //  Modified by skv - Thu Sep  4 12:29:30 2003 OCC578
  22
  23 //-- Process the case of a hole!!
  24 #define REJECTION 1
  25
  26 //-- To printf on NT
  27
  28 #include <Bnd_Box.hxx>
  29 #include <BRep_Tool.hxx>
  30 #include <BRepAdaptor_Curve2d.hxx>
  31 #include <BRepAdaptor_HSurface.hxx>
  32 #include <BRepAdaptor_Surface.hxx>
  33 #include <BRepBndLib.hxx>
  34 #include <BRepClass3d_DataMapIteratorOfMapOfInter.hxx>
  35 #include <BRepClass3d_SolidExplorer.hxx>
  36 #include <BRepClass_Edge.hxx>
  37 #include <BRepClass_FaceClassifier.hxx>
  38 #include <BRepClass_FacePassiveClassifier.hxx>
  39 #include <BRepTools.hxx>
  40 #include <BRepTopAdaptor_FClass2d.hxx>
  41 #include <ElCLib.hxx>
  42 #include <Extrema_ExtPS.hxx>
  43 #include <Geom2d_Curve.hxx>
  44 #include <GeomAbs_Shape.hxx>
  45 #include <gp.hxx>
  46 #include <gp_Lin.hxx>
  47 #include <gp_Pnt.hxx>
  48 #include <gp_Vec.hxx>
  49 #include <gp_Vec2d.hxx>
  50 #include <IntCurvesFace_Intersector.hxx>
  51 #include <Precision.hxx>
  52 #include <TopAbs_Orientation.hxx>
  53 #include <TopExp_Explorer.hxx>
  54 #include <TopoDS.hxx>
  55 #include <TopoDS_Face.hxx>
  56 #include <TopoDS_Shape.hxx>
  57 #include <TopoDS_Shell.hxx>
  58 #include <TopExp.hxx>
  59
  60 #include <stdio.h>
  61 //OCC454(apo)->
  62 //<-OCC454(apo)
  63 //=======================================================================
  64 //function : FindAPointInTheFace
  65 //purpose  : Compute a point P in the face  F. Param is a Real in
  66 //           ]0,1[ and   is  used to  initialise  the algorithm. For
  67 //           different values , different points are returned.
  68 //=======================================================================
  69 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
  70 (const TopoDS_Face& _face,
  71  gp_Pnt& APoint_,
  72  Standard_Real& param_)
  73 {
  74   Standard_Real u,v;
  75   Standard_Boolean r = FindAPointInTheFace(_face,APoint_,u,v,param_);
  76   return r;
  77 }
  78
  79 //=======================================================================
  80 //function : FindAPointInTheFace
  81 //purpose  :
  82 //=======================================================================
  83
  84 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
  85 (const TopoDS_Face& _face,
  86  gp_Pnt& APoint_,
  87  Standard_Real& u_, Standard_Real& v_,
  88  Standard_Real& param_)
  89 {
  90   gp_Vec aVecD1U, aVecD1V;
  91   return FindAPointInTheFace (_face, APoint_, u_, v_, param_, aVecD1U, aVecD1V);
  92 }
  93
  94 //=======================================================================
  95 //function : FindAPointInTheFace
  96 //purpose  :
  97 //=======================================================================
  98
  99 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
 100 (const TopoDS_Face& _face,
 101  gp_Pnt& APoint_,
 102  Standard_Real& u_, Standard_Real& v_,
 103  Standard_Real& param_,
 104  gp_Vec& theVecD1U,
 105  gp_Vec& theVecD1V)
 106 {
 107   TopoDS_Face face = _face;
 108   face.Orientation (TopAbs_FORWARD);
 109
 110   TopExp_Explorer faceexplorer;
 111   BRepAdaptor_Curve2d c;
 112   gp_Vec2d T;
 113   gp_Pnt2d P;
 114
 115   for (faceexplorer.Init(face,TopAbs_EDGE);
 116        faceexplorer.More();
 117        faceexplorer.Next())
 118   {
 119     TopoDS_Edge Edge = TopoDS::Edge (faceexplorer.Current());
 120     c.Initialize (Edge, face);
 121     c.D1((c.LastParameter() - c.FirstParameter()) * param_ + c.FirstParameter(),P,T);
 122
 123     Standard_Real x = T.X();
 124     Standard_Real y = T.Y();
 125     if (Edge.Orientation() == TopAbs_FORWARD)
 126     {
 127       T.SetCoord (-y,  x);
 128     }
 129     else
 130     {
 131       T.SetCoord ( y, -x);
 132     }
 133     Standard_Real ParamInit = RealLast();
 134     Standard_Real TolInit   = 0.00001;
 135     Standard_Boolean APointExist = Standard_False;
 136
 137     BRepClass_FacePassiveClassifier FClassifier;
 138
 139     T.Normalize();
 140     P.SetCoord (P.X() + TolInit * T.X(), P.Y() + TolInit * T.Y());
 141     FClassifier.Reset (gp_Lin2d (P, T), ParamInit, RealEpsilon()); //-- Length and Tolerance #######
 142
 143     TopExp_Explorer otherfaceexplorer;
 144     Standard_Integer aNbEdges = 0;
 145     for (otherfaceexplorer.Init (face, TopAbs_EDGE);
 146          otherfaceexplorer.More();
 147          otherfaceexplorer.Next(), ++aNbEdges)
 148     {
 149       TopoDS_Edge OtherEdge = TopoDS::Edge (otherfaceexplorer.Current());
 150       if (OtherEdge.Orientation() != TopAbs_EXTERNAL && OtherEdge != Edge)
 151       {
 152         BRepClass_Edge AEdge (OtherEdge, face);
 153         FClassifier.Compare (AEdge, OtherEdge.Orientation());
 154         if (FClassifier.ClosestIntersection())
 155         {
 156           if(ParamInit > FClassifier.Parameter())
 157           {
 158             ParamInit = FClassifier.Parameter();
 159             APointExist = Standard_True;
 160           }
 161         }
 162       }
 163     }
 164
 165     if (aNbEdges == 1)
 166     {
 167       BRepClass_Edge AEdge (Edge, face);
 168       FClassifier.Compare (AEdge, Edge.Orientation());
 169       if (FClassifier.ClosestIntersection())
 170       {
 171         if (ParamInit > FClassifier.Parameter())
 172         {
 173           ParamInit = FClassifier.Parameter();
 174           APointExist = Standard_True;
 175         }
 176       }
 177     }
 178
 179     while (APointExist)
 180     {
 181       ParamInit *= 0.41234;
 182       u_ = P.X() + ParamInit* T.X();
 183       v_ = P.Y() + ParamInit* T.Y();
 184
 185       //Additional check
 186       BRepTopAdaptor_FClass2d Classifier(face, Precision::Confusion());
 187       gp_Pnt2d aPnt2d(u_, v_);
 188       TopAbs_State StateOfResultingPoint = Classifier.Perform(aPnt2d);
 189       if (StateOfResultingPoint != TopAbs_IN)
 190         return Standard_False;
 191
 192       BRepAdaptor_Surface s;
 193       s.Initialize (face, Standard_False);
 194       s.D1 (u_, v_, APoint_, theVecD1U, theVecD1V);
 195
 196       if(theVecD1U.CrossMagnitude(theVecD1V) > gp::Resolution())
 197         return Standard_True;
 198
 199       if(ParamInit < Precision::PConfusion())
 200         return Standard_False;
 201     }
 202   }
 203   return Standard_False;
 204 }
 205
 206 //=======================================================================
 207 //function : PointInTheFace
 208 //purpose  :
 209 //=======================================================================
 210
 211 Standard_Boolean BRepClass3d_SolidExplorer::PointInTheFace
 212 (const TopoDS_Face& Face,
 213  gp_Pnt& APoint_,
 214  Standard_Real& u_, Standard_Real& v_,
 215  Standard_Real& param_,
 216  Standard_Integer& IndexPoint,
 217  const Handle(BRepAdaptor_HSurface)& surf,
 218  const Standard_Real U1,
 219  const Standard_Real V1,
 220  const Standard_Real U2,
 221  const Standard_Real V2) const
 222 {
 223   gp_Vec aVecD1U, aVecD1V;
 224   return PointInTheFace (Face, APoint_, u_, v_, param_, IndexPoint, surf,
 225                          U1, V1, U2, V2, aVecD1U, aVecD1V);
 226 }
 227
 228 //=======================================================================
 229 //function : ClassifyUVPoint
 230 //purpose  :
 231 //=======================================================================
 232
 233 TopAbs_State BRepClass3d_SolidExplorer::ClassifyUVPoint
 234                    (const IntCurvesFace_Intersector& theIntersector,
 235                     const Handle(BRepAdaptor_HSurface)& theSurf,
 236                     const gp_Pnt2d& theP2d) const
 237 {
 238   // first find if the point is near an edge/vertex
 239   gp_Pnt aP3d = theSurf->Value(theP2d.X(), theP2d.Y());
 240   BRepClass3d_BndBoxTreeSelectorPoint aSelectorPoint(myMapEV);
 241   aSelectorPoint.SetCurrentPoint(aP3d);
 242   Standard_Integer aSelsVE = myTree.Select(aSelectorPoint);
 243   if (aSelsVE > 0)
 244   {
 245     // The point is inside the tolerance area of vertices/edges => return ON state.
 246     return TopAbs_ON;
 247   }
 248   return theIntersector.ClassifyUVPoint(theP2d);
 249 }
 250
 251 //=======================================================================
 252 //function : PointInTheFace
 253 //purpose  :
 254 //=======================================================================
 255
 256 Standard_Boolean BRepClass3d_SolidExplorer::PointInTheFace
 257 (const TopoDS_Face& Face,
 258  gp_Pnt& APoint_,
 259  Standard_Real& u_, Standard_Real& v_,
 260  Standard_Real& param_,
 261  Standard_Integer& IndexPoint,
 262  const Handle(BRepAdaptor_HSurface)& surf,
 263  const Standard_Real U1,
 264  const Standard_Real V1,
 265  const Standard_Real U2,
 266  const Standard_Real V2,
 267  gp_Vec& theVecD1U,
 268  gp_Vec& theVecD1V) const
 269 {
 270   Standard_Real u,du = (U2-U1)/6.0;
 271   Standard_Real v,dv = (V2-V1)/6.0;
 272   if(du<1e-12) du=1e-12;
 273   if(dv<1e-12) dv=1e-12;
 274   Standard_Boolean IsNotUper = !surf->IsUPeriodic(), IsNotVper = !surf->IsVPeriodic();
 275   Standard_Integer NbPntCalc=0;
 276   if(myMapOfInter.IsBound(Face)) {
 277     void *ptr = (void*)(myMapOfInter.Find(Face));
 278     Standard_Boolean IsInside = Standard_True;
 279     if(IsNotUper)
 280     {
 281       IsInside = (u_ >= U1) && (u_ <= U2);
 282     }
 283     if(IsNotVper)
 284     {
 285       IsInside &= (v_ >= V1) && (v_ <= V2);
 286     }
 287     if(ptr) {
 288       const IntCurvesFace_Intersector& TheIntersector = (*((IntCurvesFace_Intersector *)ptr));
 289       // Check if the point is already in the face
 290       if (IsInside && (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u_, v_)) == TopAbs_IN)) {
 291         gp_Pnt aPnt;
 292         surf->D1(u_, v_, aPnt, theVecD1U, theVecD1V);
 293         if (aPnt.SquareDistance(APoint_) < Precision::Confusion() * Precision::Confusion())
 294           return Standard_True;
 295       }
 296
 297       //-- Take 4 points in each Quarter of surface
 298       //-- -> Index : 1 -> 16
 299       //--
 300       //--
 301       //--  Then take a matrix of points on a tight grid
 302       //--
 303       for(u=du+(U1+U2)*0.5; u<U2; u+=du) {          //--  0  X    u increases
 304         for(v=dv+(V1+V2)*0.5; v<V2; v+=dv) {        //--  0  0    v increases
 305           if(++NbPntCalc>=IndexPoint) {
 306             if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
 307               u_=u; v_=v;
 308               surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
 309               IndexPoint = NbPntCalc;
 310               return(Standard_True);
 311             }
 312           }
 313         }
 314       }
 315
 316       for(u=-du+(U1+U2)*0.5; u>U1; u-=du) {         //--  0  0    u decreases
 317         for(v=-dv+(V1+V2)*0.5; v>V1; v-=dv) {       //--  X  0    v decreases
 318           if(++NbPntCalc>=IndexPoint) {
 319             if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
 320               u_=u; v_=v;
 321               surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
 322               IndexPoint = NbPntCalc;
 323               return(Standard_True);
 324             }
 325           }
 326         }
 327       }
 328       for(u=-du+(U1+U2)*0.5; u>U1; u-=du) {         //--  X  0    u decreases
 329         for(v=dv+(V1+V2)*0.5; v<V2; v+=dv) {        //--  0  0    v increases
 330           if(++NbPntCalc>=IndexPoint) {
 331             if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
 332               u_=u; v_=v;
 333               surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
 334               IndexPoint = NbPntCalc;
 335               return(Standard_True);
 336             }
 337           }
 338         }
 339       }
 340       for(u=du+(U1+U2)*0.5; u<U2; u+=du) {         //--  0  0     u increases
 341         for(v=-dv+(V1+V2)*0.5; v>V1; v-=dv) {      //--  0  X     v decreases
 342           if(++NbPntCalc>=IndexPoint) {
 343             if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
 344               u_=u; v_=v;
 345               surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
 346               IndexPoint = NbPntCalc;
 347               return(Standard_True);
 348             }
 349           }
 350         }
 351       }
 352       //-- the remainder
 353       du = (U2-U1)/37.0;
 354       dv = (V2-V1)/37.0;
 355       if(du<1e-12) du=1e-12;
 356       if(dv<1e-12) dv=1e-12;
 357
 358       for(u=du+U1; u<U2; u+=du) {
 359         for(v=dv+V1; v<V2; v+=dv) {
 360           if(++NbPntCalc>=IndexPoint) {
 361             if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
 362               u_=u; v_=v;
 363               surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
 364               IndexPoint = NbPntCalc;
 365               return(Standard_True);
 366             }
 367           }
 368         }
 369       }
 370       u=(U1+U2)*0.5;
 371       v=(V1+V2)*0.5;
 372       if(++NbPntCalc>=IndexPoint) {
 373         if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
 374           u_=u; v_=v;
 375           surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
 376           IndexPoint = NbPntCalc;
 377           return(Standard_True);
 378         }
 379       }
 380     }
 381     IndexPoint = NbPntCalc;
 382   }
 383   else {
 384     //printf("BRepClass3d_SolidExplorer Face not found ds the map \n");
 385   }
 386
 387   return BRepClass3d_SolidExplorer
 388     ::FindAPointInTheFace (Face,APoint_, u_, v_, param_, theVecD1U, theVecD1V);
 389 }
 390
 391 //=======================================================================
 392 //function : LimitInfiniteUV
 393 //purpose  : Limit infinite parameters
 394 //=======================================================================
 395 static void LimitInfiniteUV (Standard_Real& U1,
 396                              Standard_Real& V1,
 397                              Standard_Real& U2,
 398                              Standard_Real& V2)
 399 {
 400   Standard_Boolean
 401     infU1 = Precision::IsNegativeInfinite(U1),
 402     infV1 = Precision::IsNegativeInfinite(V1),
 403     infU2 = Precision::IsPositiveInfinite(U2),
 404     infV2 = Precision::IsPositiveInfinite(V2);
 405
 406   if (infU1) U1 = -1e10;
 407   if (infV1) V1 = -1e10;
 408   if (infU2) U2 =  1e10;
 409   if (infV2) V2 =  1e10;
 410 }
 411 //=======================================================================
 412 //function : IsInfiniteUV
 413 //purpose  :
 414 //=======================================================================
 415 static Standard_Integer IsInfiniteUV (Standard_Real& U1,
 416                                       Standard_Real& V1,
 417                                       Standard_Real& U2,
 418                                       Standard_Real& V2)
 419 {
 420   Standard_Integer aVal = 0;
 421
 422   if (Precision::IsInfinite(U1))
 423     aVal |= 1;
 424
 425   if (Precision::IsInfinite(V1))
 426     aVal |= 2;
 427
 428   if (Precision::IsInfinite(U2))
 429     aVal |= 4;
 430
 431   if (Precision::IsInfinite(V2))
 432     aVal |= 8;
 433
 434   return aVal;
 435 }
 436 //<-OCC454
 437 //  Modified by skv - Tue Sep 16 13:50:39 2003 OCC578 End
 438 //=======================================================================
 439 //function : OtherSegment
 440 //purpose  : Returns  in <L>, <Par>  a segment having at least
 441 //           one  intersection  with  the  shape  boundary  to
 442 //           compute  intersections.
 443 //           The First Call to this method returns a line which
 444 //           point to a point of the first face of the shape.
 445 //           The Second Call provide a line to the second face
 446 //           and so on.
 447 //=======================================================================
 448 Standard_Integer BRepClass3d_SolidExplorer::OtherSegment(const gp_Pnt& P,
 449                                                          gp_Lin& L,
 450                                                          Standard_Real& _Par)
 451 {
 452   const Standard_Real TolU = Precision::PConfusion();
 453   const Standard_Real TolV = TolU;
 454
 455   TopoDS_Face         face;
 456   TopExp_Explorer     faceexplorer;
 457   gp_Pnt APoint;
 458   gp_Vec aVecD1U, aVecD1V;
 459   Standard_Real maxscal=0;
 460   Standard_Boolean ptfound=Standard_False;
 461   Standard_Real Par;
 462   Standard_Real _u,_v;
 463   Standard_Integer IndexPoint=0;
 464   Standard_Integer NbPointsOK=0;
 465   Standard_Integer NbFacesInSolid=0;
 466   Standard_Boolean aRestr = Standard_True;
 467   Standard_Boolean aTestInvert = Standard_False;
 468
 469   for(;;) {
 470     myFirstFace++;
 471     faceexplorer.Init(myShape,TopAbs_FACE);
 472     // look for point on face starting from myFirstFace
 473 //  Modified by skv - Thu Sep  4 14:31:12 2003 OCC578 Begin
 474 //     while (faceexplorer.More()) {
 475     NbFacesInSolid = 0;
 476     for (; faceexplorer.More(); faceexplorer.Next()) {
 477 //  Modified by skv - Thu Sep  4 14:31:12 2003 OCC578 End
 478       NbFacesInSolid++;
 479       if (myFirstFace > NbFacesInSolid) continue;
 480       face = TopoDS::Face(faceexplorer.Current());
 481
 482       Handle(BRepAdaptor_HSurface) surf = new BRepAdaptor_HSurface();
 483       if(aTestInvert)
 484       {
 485         BRepTopAdaptor_FClass2d aClass(face, Precision::Confusion());
 486         if(aClass.PerformInfinitePoint() == TopAbs_IN)
 487         {
 488           aRestr = Standard_False;
 489           if(myMapOfInter.IsBound(face))
 490           {
 491             myMapOfInter.UnBind(face);
 492             void *ptr = (void *)(new IntCurvesFace_Intersector(face, Precision::Confusion(),
 493                                                                aRestr, Standard_False));
 494             myMapOfInter.Bind(face,ptr);
 495           }
 496         }
 497         else
 498         {
 499           aRestr = Standard_True;
 500         }
 501       }
 502       surf->ChangeSurface().Initialize(face, aRestr);
 503       Standard_Real U1,V1,U2,V2;
 504       U1 = surf->FirstUParameter();
 505       V1 = surf->FirstVParameter();
 506       U2 = surf->LastUParameter();
 507       V2 = surf->LastVParameter();
 508       face.Orientation(TopAbs_FORWARD);
 509       //
 510       //avoid process faces from uncorrected shells
 511       const Standard_Real eps = Precision::PConfusion();
 512       Standard_Real epsU = Max(eps * Max(Abs(U2), Abs(U1)), eps);
 513       Standard_Real epsV = Max(eps * Max(Abs(V2), Abs(V1)), eps);
 514       if( Abs (U2 - U1) < epsU || Abs(V2 - V1) < epsV) {
 515         return 2;
 516       }
 517       //
 518       Standard_Real svmyparam=myParamOnEdge;
 519       //
 520       // Check if the point is on the face or the face is infinite.
 521       Standard_Integer anInfFlag = IsInfiniteUV(U1,V1,U2,V2);
 522       // default values
 523       _u = (U1 + U2) * 0.5;
 524       _v = (V1 + V2) * 0.5;
 525
 526       GeomAdaptor_Surface GA(BRep_Tool::Surface(face));
 527       Extrema_ExtPS Ext(P, GA, TolU, TolV);
 528       //
 529       if (Ext.IsDone() && Ext.NbExt() > 0) {
 530         Standard_Integer i, iNear,  iEnd;
 531         Standard_Real  aUx, aVx, Dist2, Dist2Min;
 532         Extrema_POnSurf aPx;
 533         //
 534         iNear = 1;
 535         Dist2Min = Ext.SquareDistance(1);
 536         iEnd = Ext.NbExt();
 537         for (i = 2; i <= iEnd; i++) {
 538           aPx=Ext.Point(i);
 539           aPx.Parameter(aUx, aVx);
 540           if (aUx>=U1 && aUx<=U2 && aVx>=V1 && aVx<=V2) {
 541             Dist2 = Ext.SquareDistance(i);
 542             if (Dist2 < Dist2Min) {
 543               Dist2Min = Dist2;
 544               iNear = i;
 545             }
 546           }
 547         }
 548         //
 549         Standard_Real aDist2Tresh=1.e-24;
 550         //
 551         if (Dist2Min<aDist2Tresh) {
 552           if (anInfFlag) {
 553             return 1;
 554           }
 555           else {
 556             BRepClass_FaceClassifier classifier2d;
 557             Standard_Real            aU;
 558             Standard_Real            aV;
 559
 560             (Ext.Point(iNear)).Parameter(aU, aV);
 561
 562             gp_Pnt2d aPuv(aU, aV);
 563
 564             classifier2d.Perform(face,aPuv,Precision::PConfusion());
 565
 566             TopAbs_State aState = classifier2d.State();
 567
 568             if (aState == TopAbs_IN || aState == TopAbs_ON) {
 569               return 1;
 570             }
 571             else {
 572               return 3; // skv - the point is on surface but outside face.
 573             }
 574           }
 575         }
 576         if (anInfFlag) {
 577           APoint = (Ext.Point(iNear)).Value();
 578           gp_Vec V(P,APoint);
 579           _Par = V.Magnitude();
 580           L = gp_Lin(P,V);
 581           ptfound=Standard_True;
 582           return 0;
 583         }
 584
 585         // set the parameters found by extrema
 586         aPx = Ext.Point(iNear);
 587         aPx.Parameter(_u, _v);
 588         APoint = aPx.Value();
 589       }
 590       //The point is not ON the face or surface. The face is restricted.
 591       // find point in a face not too far from a projection of P on face
 592       do {
 593         if (PointInTheFace (face, APoint, _u, _v, myParamOnEdge, ++IndexPoint, surf,
 594                             U1, V1, U2, V2,
 595                             aVecD1U, aVecD1V))
 596         {
 597           ++NbPointsOK;
 598           gp_Vec V (P, APoint);
 599           Par = V.Magnitude();
 600           if (Par > gp::Resolution() &&
 601               aVecD1U.Magnitude() > gp::Resolution() &&
 602               aVecD1V.Magnitude() > gp::Resolution())
 603           {
 604             gp_Vec Norm = aVecD1U.Crossed (aVecD1V);
 605             Standard_Real tt = Norm.Magnitude();
 606             if (tt > gp::Resolution())
 607             {
 608               tt = Abs (Norm.Dot (V)) / (tt * Par);
 609               if (tt > maxscal)
 610               {
 611                 maxscal = tt;
 612                 L = gp_Lin (P, V);
 613                 _Par = Par;
 614                 ptfound = Standard_True;
 615                 if (maxscal>0.2)
 616                 {
 617                   myParamOnEdge=svmyparam;
 618                   return 0;
 619                 }
 620               }
 621             }
 622           }
 623         }
 624       }
 625       while(IndexPoint<200 && NbPointsOK<16);
 626
 627       myParamOnEdge=svmyparam;
 628       if(maxscal>0.2) {
 629         return 0;
 630       }
 631
 632
 633       //  Modified by skv - Thu Sep  4 14:32:14 2003 OCC578 Begin
 634       // Next is done in the main for(..) loop.
 635       //       faceexplorer.Next();
 636       //  Modified by skv - Thu Sep  4 14:32:14 2003 OCC578 End
 637       IndexPoint = 0;
 638
 639       Standard_Boolean encoreuneface = faceexplorer.More();
 640       if(ptfound==Standard_False && encoreuneface==Standard_False) {
 641         if(myParamOnEdge < 0.0001) {
 642           //-- This case takes place when the point is on the solid
 643           //-- and this solid is reduced to a face
 644           gp_Pnt PBidon(P.X()+1.0,P.Y(),P.Z());
 645           gp_Vec V(P,PBidon);
 646           Par= 1.0;
 647           _Par=Par;
 648           L  = gp_Lin(P,V);
 649           return 0;
 650         }
 651       }
 652     } //-- Exploration of the faces
 653
 654     if(NbFacesInSolid==0) {
 655       _Par=0.0;
 656       myReject=Standard_True;
 657 #ifdef OCCT_DEBUG
 658       cout<<"\nWARNING : BRepClass3d_SolidExplorer.cxx  (Solid without face)"<<endl;
 659 #endif
 660       return 0;
 661     }
 662
 663     if(ptfound) {
 664       return 0;
 665     }
 666     myFirstFace = 0;
 667     if(myParamOnEdge==0.512345)  myParamOnEdge = 0.4;
 668     else if(myParamOnEdge==0.4)  myParamOnEdge = 0.6;
 669     else if(myParamOnEdge==0.6)  myParamOnEdge = 0.3;
 670     else if(myParamOnEdge==0.3)  myParamOnEdge = 0.7;
 671     else if(myParamOnEdge==0.7)  myParamOnEdge = 0.2;
 672     else if(myParamOnEdge==0.2)  myParamOnEdge = 0.8;
 673     else if(myParamOnEdge==0.8)  myParamOnEdge = 0.1;
 674     else if(myParamOnEdge==0.1)  myParamOnEdge = 0.9;
 675     //
 676     else {
 677       myParamOnEdge*=0.5;
 678       if(myParamOnEdge < 0.0001) {
 679         gp_Pnt PBidon(P.X()+1.0,P.Y(),P.Z());
 680         gp_Vec V(P,PBidon);
 681         Par= 1.0;
 682         _Par=Par;
 683         L  = gp_Lin(P,V);
 684         return 0;
 685       }
 686     }
 687     aTestInvert = Standard_True;
 688   } //-- for(;;) { ...  }
 689 }
 690
 691 //  Modified by skv - Thu Sep  4 12:30:14 2003 OCC578 Begin
 692 //=======================================================================
 693 //function : GetFaceSegmentIndex
 694 //purpose  : Returns the index of face for which last segment is calculated.
 695 //=======================================================================
 696
 697 Standard_Integer BRepClass3d_SolidExplorer::GetFaceSegmentIndex() const
 698 {
 699   return myFirstFace;
 700 }
 701 //  Modified by skv - Thu Sep  4 12:30:14 2003 OCC578 End
 702
 703 //=======================================================================
 704 //function : PointInTheFace
 705 //purpose  :
 706 //=======================================================================
 707
 708 Standard_Boolean BRepClass3d_SolidExplorer::PointInTheFace
 709 (const TopoDS_Face& _face,
 710  gp_Pnt& APoint_,
 711  Standard_Real& u_, Standard_Real& v_,
 712  Standard_Real& param_,
 713  Standard_Integer& IndexPoint) const
 714 {
 715   TopoDS_Face Face = _face;
 716   Face.Orientation(TopAbs_FORWARD);
 717   Handle(BRepAdaptor_HSurface) surf = new BRepAdaptor_HSurface();
 718   surf->ChangeSurface().Initialize(Face);
 719   Standard_Real U1,V1,U2,V2;//,u,v;
 720   U1 = surf->FirstUParameter();
 721   V1 = surf->FirstVParameter();
 722   U2 = surf->LastUParameter();
 723   V2 = surf->LastVParameter();
 724   LimitInfiniteUV (U1,V1,U2,V2);
 725   return(PointInTheFace(Face,APoint_,u_,v_,param_,IndexPoint,surf,U1,V1,U2,V2));
 726 }
 727
 728 //=======================================================================
 729 //function : FindAPointInTheFace
 730 //purpose  :
 731 //=======================================================================
 732
 733 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
 734 (const TopoDS_Face& _face,
 735  gp_Pnt& APoint_,
 736  Standard_Real& u_,Standard_Real& v_)
 737 {
 738   Standard_Real param = 0.1;
 739   Standard_Boolean r = FindAPointInTheFace(_face,APoint_,u_,v_,param);
 740   return r;
 741 }
 742
 743 //=======================================================================
 744 //function : FindAPointInTheFace
 745 //purpose  :
 746 //=======================================================================
 747
 748 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
 749 (const TopoDS_Face& _face,
 750  gp_Pnt& APoint_)
 751 { Standard_Real u,v;
 752   Standard_Boolean r = FindAPointInTheFace(_face,APoint_,u,v);
 753   return r;
 754 }
 755
 756 //=======================================================================
 757 //function : FindAPointInTheFace
 758 //purpose  :
 759 //=======================================================================
 760
 761 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
 762 (const TopoDS_Face& _face,
 763  Standard_Real& u_,Standard_Real& v_)
 764 { gp_Pnt APoint;
 765   Standard_Boolean r = FindAPointInTheFace(_face,APoint,u_,v_);
 766   return r;
 767 }
 768
 769 //=======================================================================
 770 //function : BRepClass3d_SolidExplorer
 771 //purpose  :
 772 //=======================================================================
 773
 774 BRepClass3d_SolidExplorer::BRepClass3d_SolidExplorer()
 775 {
 776 }
 777
 778 //=======================================================================
 779 //function : BRepClass3d_SolidExplorer
 780 //purpose  :
 781 //=======================================================================
 782
 783 BRepClass3d_SolidExplorer::BRepClass3d_SolidExplorer(const TopoDS_Shape& S)
 784 {
 785   InitShape(S);
 786 }
 787
 788 //=======================================================================
 789 //function : ~BRepClass3d_SolidExplorer
 790 //purpose  :
 791 //=======================================================================
 792
 793 BRepClass3d_SolidExplorer::~BRepClass3d_SolidExplorer()
 794 {
 795  Destroy() ;
 796 }
 797
 798 //=======================================================================
 799 //function : Destroy
 800 //purpose  : C++: alias ~
 801 //=======================================================================
 802
 803 void BRepClass3d_SolidExplorer::Destroy() {
 804   BRepClass3d_DataMapIteratorOfMapOfInter iter(myMapOfInter);
 805   for(;iter.More();iter.Next()) {
 806     void *ptr=iter.Value();
 807     if(ptr) {
 808       delete (IntCurvesFace_Intersector *)ptr;
 809       myMapOfInter.ChangeFind(iter.Key()) = NULL;
 810     }
 811   }
 812   myMapOfInter.Clear();
 813 }
 814
 815 //=======================================================================
 816 //function : InitShape
 817 //purpose  :
 818 //=======================================================================
 819
 820 void BRepClass3d_SolidExplorer::InitShape(const TopoDS_Shape& S)
 821 {
 822   myMapEV.Clear();
 823   myTree.Clear();
 824
 825   myShape = S;
 826   myFirstFace = 0;
 827   myParamOnEdge = 0.512345;
 828   //-- Exploring of the Map and removal of allocated objects
 829
 830
 831   BRepClass3d_DataMapIteratorOfMapOfInter iter(myMapOfInter);
 832   for(;iter.More();iter.Next()) {
 833     void *ptr=iter.Value();
 834     if(ptr) {
 835       delete (IntCurvesFace_Intersector *)ptr;
 836       myMapOfInter.ChangeFind(iter.Key()) = NULL;
 837     }
 838   }
 839
 840   myMapOfInter.Clear();
 841
 842   myReject = Standard_True; //-- case of infinite solid (without any face)
 843
 844   TopExp_Explorer Expl;
 845   for(Expl.Init(S,TopAbs_FACE);
 846       Expl.More();
 847       Expl.Next()) {
 848     const TopoDS_Face Face = TopoDS::Face(Expl.Current());
 849     void *ptr = (void *)(new IntCurvesFace_Intersector(Face,Precision::Confusion(),Standard_True, Standard_False));
 850     myMapOfInter.Bind(Face,ptr);
 851     myReject=Standard_False;  //-- at least one face in the solid
 852   }
 853
 854 #ifdef OCCT_DEBUG
 855   if(myReject) {
 856     cout<<"\nWARNING : BRepClass3d_SolidExplorer.cxx  (Solid without face)"<<endl;
 857   }
 858 #endif
 859
 860 #if REJECTION
 861   BRepBndLib::Add(myShape,myBox);
 862 #endif
 863
 864   // since the internal/external parts should be avoided in tree filler,
 865   // there is no need to add these parts in the EV map as well
 866   TopExp_Explorer aExpF(myShape, TopAbs_FACE);
 867   for (; aExpF.More(); aExpF.Next()) {
 868     const TopoDS_Shape& aF = aExpF.Current();
 869     //
 870     TopAbs_Orientation anOrF = aF.Orientation();
 871     if (anOrF == TopAbs_INTERNAL || anOrF == TopAbs_EXTERNAL) {
 872       continue;
 873     }
 874     //
 875     TopExp_Explorer aExpE(aF, TopAbs_EDGE);
 876     for (; aExpE.More(); aExpE.Next()) {
 877       const TopoDS_Shape& aE = aExpE.Current();
 878       //
 879       TopAbs_Orientation anOrE = aE.Orientation();
 880       if (anOrE == TopAbs_INTERNAL || anOrE == TopAbs_EXTERNAL) {
 881         continue;
 882       }
 883       //
 884       if (BRep_Tool::Degenerated(TopoDS::Edge(aE))) {
 885         continue;
 886       }
 887       //
 888       TopExp::MapShapes(aE, myMapEV);
 889     }
 890   }
 891   //
 892   // Fill mapEV with vertices and edges from shape
 893   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller (myTree);
 894   //
 895   Standard_Integer i, aNbEV = myMapEV.Extent();
 896   for (i = 1; i <= aNbEV; ++i) {
 897     const TopoDS_Shape& aS = myMapEV(i);
 898     //
 899     Bnd_Box aBox;
 900     BRepBndLib::Add(aS, aBox);
 901     aTreeFiller.Add(i, aBox);
 902   }
 903   aTreeFiller.Fill();
 904 }
 905
 906 //=======================================================================
 907 //function : Reject
 908 //purpose  : Should return True if P outside of bounding vol. of the shape
 909 //=======================================================================
 910
 911 //Standard_Boolean  BRepClass3d_SolidExplorer::Reject(const gp_Pnt& P) const
 912 Standard_Boolean  BRepClass3d_SolidExplorer::Reject(const gp_Pnt& ) const
 913 {
 914   return(myReject);  // case of solid without face
 915 }
 916
 917 //=======================================================================
 918 //function : InitShell
 919 //purpose  : Starts an exploration of the shells.
 920 //=======================================================================
 921
 922 void BRepClass3d_SolidExplorer::InitShell()
 923 {
 924   myShellExplorer.Init(myShape,TopAbs_SHELL);
 925 }
 926
 927 //=======================================================================
 928 //function : MoreShell
 929 //purpose  : Returns True if there is a current shell.
 930 //=======================================================================
 931
 932 Standard_Boolean BRepClass3d_SolidExplorer::MoreShell() const
 933 {
 934   return(myShellExplorer.More());
 935 }
 936
 937 //=======================================================================
 938 //function : NextShell
 939 //purpose  : Sets the explorer to the next shell.
 940 //=======================================================================
 941
 942 void BRepClass3d_SolidExplorer::NextShell()
 943 {
 944   myShellExplorer.Next();
 945 }
 946
 947 //=======================================================================
 948 //function : CurrentShell
 949 //purpose  : Returns the current shell.
 950 //=======================================================================
 951
 952 TopoDS_Shell BRepClass3d_SolidExplorer::CurrentShell() const
 953 {
 954   return(TopoDS::Shell(myShellExplorer.Current()));
 955 }
 956
 957 //=======================================================================
 958 //function : RejectShell
 959 //purpose  : Returns True if the Shell is rejected.
 960 //=======================================================================
 961
 962 Standard_Boolean BRepClass3d_SolidExplorer::RejectShell(const gp_Lin& ) const
 963 {
 964   return(Standard_False);
 965 }
 966
 967 //=======================================================================
 968 //function : InitFace
 969 //purpose  : Starts an exploration of the faces of the current shell.
 970 //=======================================================================
 971
 972 void BRepClass3d_SolidExplorer::InitFace()
 973 {
 974   myFaceExplorer.Init(TopoDS::Shell(myShellExplorer.Current()),TopAbs_FACE);
 975 }
 976
 977 //=======================================================================
 978 //function : MoreFace
 979 //purpose  : Returns True if current face in current shell.
 980 //=======================================================================
 981
 982 Standard_Boolean BRepClass3d_SolidExplorer::MoreFace() const
 983 {
 984   return(myFaceExplorer.More());
 985 }
 986
 987 //=======================================================================
 988 //function : NextFace
 989 //purpose  : Sets the explorer to the next Face of the current shell.
 990 //=======================================================================
 991
 992 void BRepClass3d_SolidExplorer::NextFace()
 993 {
 994   myFaceExplorer.Next();
 995 }
 996
 997 //=======================================================================
 998 //function : CurrentFace
 999 //purpose  : Returns the current face.
1000 //=======================================================================
1001
1002 TopoDS_Face BRepClass3d_SolidExplorer::CurrentFace() const
1003 {
1004   return(TopoDS::Face(myFaceExplorer.Current()));
1005 }
1006
1007 //=======================================================================
1008 //function : RejectFace
1009 //purpose  : returns True if the face is rejected.
1010 //=======================================================================
1011
1012 Standard_Boolean BRepClass3d_SolidExplorer::RejectFace(const gp_Lin& ) const
1013 {
1014   return(Standard_False);
1015 }
1016
1017 #ifdef OCCT_DEBUG
1018 #include <TopAbs_State.hxx>
1019 #endif
1020
1021 //=======================================================================
1022 //function : Segment
1023 //purpose  : Returns  in <L>, <Par>  a segment having at least
1024 //           one  intersection  with  the  shape  boundary  to
1025 //           compute  intersections.
1026 //=======================================================================
1027 Standard_Integer  BRepClass3d_SolidExplorer::Segment(const gp_Pnt& P,
1028                                                      gp_Lin& L,
1029                                                      Standard_Real& Par)
1030 {
1031   Standard_Integer bRetFlag;
1032   myFirstFace = 0;
1033   bRetFlag=OtherSegment(P,L,Par);
1034   return bRetFlag;
1035 }
1036
1037 //=======================================================================
1038 //function : Intersector
1039 //purpose  :
1040 //=======================================================================
1041
1042 IntCurvesFace_Intersector&  BRepClass3d_SolidExplorer::Intersector(const TopoDS_Face& F) const  {
1043   void *ptr = (void*)(myMapOfInter.Find(F));
1044   IntCurvesFace_Intersector& curr = (*((IntCurvesFace_Intersector *)ptr));
1045   return curr;
1046 }
1047
1048 //=======================================================================
1049 //function : Box
1050 //purpose  :
1051 //=======================================================================
1052
1053 const Bnd_Box& BRepClass3d_SolidExplorer::Box() const {
1054   return(myBox);
1055 }
1056
1057 //=======================================================================
1058 //function : DumpSegment
1059 //purpose  :
1060 //=======================================================================
1061
1062 void BRepClass3d_SolidExplorer::DumpSegment(const gp_Pnt&,
1063                                             const gp_Lin&,
1064                                             const Standard_Real,
1065                                             const TopAbs_State) const
1066 {
1067 #ifdef OCCT_DEBUG
1068
1069 #endif
1070 }
1071
1072 const TopoDS_Shape& BRepClass3d_SolidExplorer::GetShape() const
1073 {
1074   return(myShape);
1075 }