src/GEOMAlgo/GEOMAlgo_AlgoTools.cxx

   1 // Copyright (C) 2007-2014  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 // Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   5 //
   6 // This library is free software; you can redistribute it and/or
   7 // modify it under the terms of the GNU Lesser General Public
   8 // License as published by the Free Software Foundation; either
   9 // version 2.1 of the License, or (at your option) any later version.
  10 //
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // Lesser General Public License for more details.
  15 //
  16 // You should have received a copy of the GNU Lesser General Public
  17 // License along with this library; if not, write to the Free Software
  18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  19 //
  20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  21 //
  22 //  File    : GEOMAlgo_AlgoTools.cxx
  23 //  Created :
  24 //  Author  : Peter KURNEV
  25
  26 #include <GEOMAlgo_AlgoTools.hxx>
  27
  28 #include <gp_Pnt.hxx>
  29 #include <gp_Pnt2d.hxx>
  30 #include <gp_Dir2d.hxx>
  31 #include <Bnd_Box.hxx>
  32
  33 #include <Geom2d_Curve.hxx>
  34 #include <Geom2d_TrimmedCurve.hxx>
  35 #include <Geom2d_Line.hxx>
  36 #include <Geom2d_TrimmedCurve.hxx>
  37
  38 #include <Geom2dHatch_Intersector.hxx>
  39 #include <Geom2dHatch_Hatcher.hxx>
  40
  41 #include <Geom2dAdaptor_Curve.hxx>
  42 #include <HatchGen_Domain.hxx>
  43
  44 #include <Geom_Curve.hxx>
  45 #include <Geom_Surface.hxx>
  46
  47 #include <GeomAdaptor_Surface.hxx>
  48
  49 #include <GeomAPI_ProjectPointOnSurf.hxx>
  50 #include <GeomAPI_ProjectPointOnCurve.hxx>
  51
  52 #include <Poly_Triangulation.hxx>
  53
  54 #include <TopAbs_Orientation.hxx>
  55
  56 #include <TopLoc_Location.hxx>
  57
  58 #include <TopoDS.hxx>
  59 #include <TopoDS_Iterator.hxx>
  60 #include <TopoDS_Face.hxx>
  61 #include <TopoDS_Edge.hxx>
  62
  63 #include <TopExp_Explorer.hxx>
  64
  65 #include <BRep_Tool.hxx>
  66 #include <BRep_Builder.hxx>
  67
  68 #include <BRepTools.hxx>
  69 #include <BRepBndLib.hxx>
  70 #include <BRepMesh_IncrementalMesh.hxx>
  71
  72 #include <IntTools_Tools.hxx>
  73
  74 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  75 #include <TopTools_ListOfShape.hxx>
  76
  77 #include <TopTools_ListIteratorOfListOfShape.hxx>
  78 #include <TopTools_IndexedMapOfShape.hxx>
  79 #include <TopAbs_ShapeEnum.hxx>
  80
  81 #include <IntTools_Tools.hxx>
  82
  83 #include <BOPTools_AlgoTools3D.hxx>
  84 #include <BOPTools_AlgoTools2D.hxx>
  85
  86 #include <GEOMAlgo_PassKeyShape.hxx>
  87
  88
  89 static
  90   void GetCount(const TopoDS_Shape& aS,
  91                 Standard_Integer& iCnt);
  92 static
  93   void CopySource(const TopoDS_Shape& aS,
  94                   TopTools_IndexedDataMapOfShapeShape& aMapSS,
  95                   TopoDS_Shape& aSC);
  96
  97 //=======================================================================
  98 //function : CopyShape
  99 //purpose  :
 100 //=======================================================================
 101 void GEOMAlgo_AlgoTools::CopyShape(const TopoDS_Shape& aS,
 102                                    TopoDS_Shape& aSC)
 103 {
 104   TopTools_IndexedDataMapOfShapeShape aMapSS;
 105   //
 106   CopySource(aS, aMapSS, aSC);
 107 }
 108 //=======================================================================
 109 //function : CopyShape
 110 //purpose  :
 111 //=======================================================================
 112 void GEOMAlgo_AlgoTools::CopyShape(const TopoDS_Shape& aS,
 113                                    TopoDS_Shape& aSC,
 114                                    TopTools_IndexedDataMapOfShapeShape& aMapSS)
 115 {
 116   CopySource(aS, aMapSS, aSC);
 117 }
 118 //=======================================================================
 119 //function : CopySource
 120 //purpose  :
 121 //=======================================================================
 122 void CopySource(const TopoDS_Shape& aS,
 123                 TopTools_IndexedDataMapOfShapeShape& aMapSS,
 124                 TopoDS_Shape& aSC)
 125 {
 126   Standard_Boolean bFree;
 127   TopAbs_ShapeEnum aT;
 128   TopoDS_Iterator aIt;
 129   TopoDS_Shape aSF;
 130   BRep_Builder BB;
 131   //
 132   aT=aS.ShapeType();
 133   //
 134   if (aMapSS.Contains(aS)) {
 135     aSC=aMapSS.ChangeFromKey(aS);
 136     aSC.Orientation(aS.Orientation());
 137     return;
 138   }
 139   else {
 140     aSC=aS.EmptyCopied();
 141     aMapSS.Add(aS, aSC);
 142   }
 143   //
 144   bFree=aSC.Free();
 145   aSC.Free(Standard_True);
 146   aSF=aS;
 147   if (aT==TopAbs_EDGE){
 148     TopAbs_Orientation aOr;
 149     //
 150     aOr=aS.Orientation();
 151     if(aOr==TopAbs_INTERNAL) {
 152       aSF.Orientation(TopAbs_FORWARD);
 153     }
 154   }
 155   aIt.Initialize(aSF);
 156   for (; aIt.More();  aIt.Next()) {
 157     TopoDS_Shape aSCx;
 158     //
 159     const TopoDS_Shape& aSx=aIt.Value();
 160     //
 161     CopySource (aSx, aMapSS, aSCx);
 162     //
 163     aSCx.Orientation(aSx.Orientation());
 164     BB.Add(aSC, aSCx);
 165   }
 166   aSC.Free(bFree);
 167 }
 168 //=======================================================================
 169 //function : FaceNormal
 170 //purpose  :
 171 //=======================================================================
 172 void GEOMAlgo_AlgoTools::FaceNormal (const TopoDS_Face& aF,
 173                                      const Standard_Real U,
 174                                      const Standard_Real V,
 175                                      gp_Vec& aN)
 176 {
 177   gp_Pnt aPnt ;
 178   gp_Vec aD1U, aD1V;
 179   Handle(Geom_Surface) aSurface;
 180
 181   aSurface=BRep_Tool::Surface(aF);
 182   aSurface->D1 (U, V, aPnt, aD1U, aD1V);
 183   aN=aD1U.Crossed(aD1V);
 184   aN.Normalize();
 185   if (aF.Orientation() == TopAbs_REVERSED){
 186     aN.Reverse();
 187   }
 188   return;
 189 }
 190 //=======================================================================
 191 //function : BuildPCurveForEdgeOnFace
 192 //purpose  :
 193 //=======================================================================
 194 Standard_Integer GEOMAlgo_AlgoTools::BuildPCurveForEdgeOnFace
 195   (const TopoDS_Edge& aEold,
 196    const TopoDS_Edge& aEnew,
 197    const TopoDS_Face& aF,
 198    const Handle(BOPInt_Context)& aCtx)
 199 {
 200   Standard_Boolean bIsClosed, bUClosed, bHasOld;
 201   Standard_Integer iRet, aNbPoints;
 202   Standard_Real aTS, aTS1, aTS2, aT, aT1, aT2, aScPr, aTol;
 203   Standard_Real aU, aV, aUS1, aVS1, aUS2, aVS2;
 204   gp_Pnt aP;
 205   gp_Pnt2d aP2DS1, aP2DS2, aP2D;
 206   gp_Vec2d aV2DS1, aV2DS2;
 207   Handle(Geom2d_Curve) aC2D, aC2DS1, aC2DS2;
 208   Handle(Geom_Surface) aS;
 209   TopoDS_Edge aES;
 210   //
 211   iRet=0;
 212   //
 213   bHasOld=BOPTools_AlgoTools2D::HasCurveOnSurface(aEnew, aF, aC2D, aT1, aT2, aTol);
 214   if (bHasOld) {
 215     return iRet;
 216   }
 217   //
 218   BOPTools_AlgoTools2D::BuildPCurveForEdgeOnFace(aEnew, aF);
 219   aC2D=BRep_Tool::CurveOnSurface(aEnew, aF, aT1, aT2);
 220   if (aC2D.IsNull()){
 221     iRet=1;
 222     return iRet;
 223   }
 224   //
 225   bIsClosed=BRep_Tool::IsClosed(aEold, aF);
 226   if (!bIsClosed) {
 227     return iRet;
 228   }
 229   //
 230   aTol=1.e-7;
 231   //
 232   // 1. bUClosed - direction of closeness
 233   //
 234   aES=aEold;
 235   aES.Orientation(TopAbs_FORWARD);
 236   aC2DS1=BRep_Tool::CurveOnSurface(aES, aF, aTS1, aTS2);
 237   //
 238   aES.Orientation(TopAbs_REVERSED);
 239   aC2DS2=BRep_Tool::CurveOnSurface(aES, aF, aTS1, aTS2);
 240   //
 241   aTS=IntTools_Tools::IntermediatePoint(aTS1, aTS2);
 242   //
 243   aC2DS1->D1(aTS, aP2DS1, aV2DS1);
 244   aC2DS2->D1(aTS, aP2DS2, aV2DS2);
 245   //
 246   gp_Vec2d aV2DS12(aP2DS1, aP2DS2);
 247   gp_Dir2d aD2DS12(aV2DS12);
 248   const gp_Dir2d& aD2DX=gp::DX2d();
 249   //
 250   aScPr=aD2DS12*aD2DX;
 251   bUClosed=Standard_True;
 252   if (fabs(aScPr) < aTol) {
 253     bUClosed=!bUClosed;
 254   }
 255   //
 256   // 2. aP2D - point on curve aC2D, that corresponds to aP2DS1
 257   aP2DS1.Coord(aUS1, aVS1);
 258   aP2DS2.Coord(aUS2, aVS2);
 259   //
 260   aS=BRep_Tool::Surface(aF);
 261   aS->D0(aUS1, aVS1, aP);
 262   //
 263   GeomAPI_ProjectPointOnCurve& aProjPC=aCtx->ProjPC(aEnew);
 264   //
 265   aProjPC.Perform(aP);
 266   aNbPoints=aProjPC.NbPoints();
 267   if (!aNbPoints) {
 268     iRet=2;
 269     return iRet;
 270   }
 271   //
 272   aT=aProjPC.LowerDistanceParameter();
 273
 274   //
 275   // 3. Build the second 2D curve
 276   Standard_Boolean bRevOrder;
 277   gp_Vec2d aV2DT, aV2D;
 278   Handle(Geom2d_Curve) aC2Dnew;
 279   Handle(Geom2d_TrimmedCurve) aC2DTnew;
 280   BRep_Builder aBB;
 281   //
 282   aC2D->D1(aT, aP2D, aV2D);
 283   aP2D.Coord(aU, aV);
 284   //
 285   aC2Dnew=Handle(Geom2d_Curve)::DownCast(aC2D->Copy());
 286   aC2DTnew = new Geom2d_TrimmedCurve(aC2Dnew, aT1, aT2);
 287   //
 288   aV2DT=aV2DS12;
 289   if (!bUClosed) {    // V Closed
 290     if (fabs(aV-aVS2)<aTol) {
 291       aV2DT.Reverse();
 292     }
 293   }
 294   else {   // U Closed
 295     if (fabs(aU-aUS2)<aTol) {
 296       aV2DT.Reverse();
 297     }
 298   }
 299   //
 300   aC2DTnew->Translate(aV2DT);
 301   //
 302   // 4 Order the 2D curves
 303   bRevOrder=Standard_False;
 304   aScPr=aV2D*aV2DS1;
 305   if(aScPr<0.) {
 306     bRevOrder=!bRevOrder;
 307   }
 308   //
 309   // 5. Update the edge
 310   aTol=BRep_Tool::Tolerance(aEnew);
 311   if (!bRevOrder) {
 312     aBB.UpdateEdge(aEnew, aC2D, aC2DTnew, aF, aTol);
 313   }
 314   else {
 315     aBB.UpdateEdge(aEnew, aC2DTnew, aC2D , aF, aTol);
 316   }
 317   //
 318   return iRet;
 319 }
 320 //////////////////////////////////////////////////////////////////////////
 321 //=======================================================================
 322 // function: MakeContainer
 323 // purpose:
 324 //=======================================================================
 325 void GEOMAlgo_AlgoTools::MakeContainer(const TopAbs_ShapeEnum theType,
 326                                        TopoDS_Shape& theC)
 327 {
 328   BRep_Builder aBB;
 329   //
 330   switch(theType) {
 331     case TopAbs_COMPOUND:{
 332       TopoDS_Compound aC;
 333       aBB.MakeCompound(aC);
 334       theC=aC;
 335     }
 336       break;
 337       //
 338     case TopAbs_COMPSOLID:{
 339       TopoDS_CompSolid aCS;
 340       aBB.MakeCompSolid(aCS);
 341       theC=aCS;
 342     }
 343       break;
 344       //
 345     case TopAbs_SOLID:{
 346       TopoDS_Solid aSolid;
 347       aBB.MakeSolid(aSolid);
 348       theC=aSolid;
 349     }
 350       break;
 351       //
 352       //
 353     case TopAbs_SHELL:{
 354       TopoDS_Shell aShell;
 355       aBB.MakeShell(aShell);
 356       theC=aShell;
 357     }
 358       break;
 359       //
 360     case TopAbs_WIRE: {
 361       TopoDS_Wire aWire;
 362       aBB.MakeWire(aWire);
 363       theC=aWire;
 364     }
 365       break;
 366       //
 367     default:
 368       break;
 369   }
 370 }
 371 //=======================================================================
 372 //function : IsUPeriodic
 373 //purpose  :
 374 //=======================================================================
 375 Standard_Boolean GEOMAlgo_AlgoTools::IsUPeriodic(const  Handle(Geom_Surface) &aS)
 376 {
 377   Standard_Boolean bRet;
 378   GeomAbs_SurfaceType aType;
 379   GeomAdaptor_Surface aGAS;
 380   //
 381   aGAS.Load(aS);
 382   aType=aGAS.GetType();
 383   bRet=(aType==GeomAbs_Cylinder||
 384         aType==GeomAbs_Cone ||
 385         aType==GeomAbs_Sphere);
 386   //
 387   return bRet;
 388 }
 389
 390 //=======================================================================
 391 //function : RefinePCurveForEdgeOnFace
 392 //purpose  :
 393 //=======================================================================
 394 void GEOMAlgo_AlgoTools::RefinePCurveForEdgeOnFace(const TopoDS_Edge& aE,
 395                                                    const TopoDS_Face& aF,
 396                                                    const Standard_Real aUMin,
 397                                                    const Standard_Real aUMax)
 398 {
 399   Standard_Real aT1, aT2, aTx, aUx, aTol;
 400   gp_Pnt2d aP2D;
 401   Handle(Geom_Surface) aS;
 402   Handle(Geom2d_Curve) aC2D;
 403   BRep_Builder aBB;
 404   //
 405   aC2D=BRep_Tool::CurveOnSurface(aE, aF, aT1, aT2);
 406   if (!aC2D.IsNull()) {
 407     if (BRep_Tool::IsClosed(aE, aF)) {
 408       return;
 409     }
 410     aTx=IntTools_Tools::IntermediatePoint(aT1, aT2);
 411     aC2D->D0(aTx, aP2D);
 412     aUx=aP2D.X();
 413     if (aUx < aUMin || aUx > aUMax) {
 414       // need to rebuild
 415       Handle(Geom2d_Curve) aC2Dx;
 416       //
 417       aTol=BRep_Tool::Tolerance(aE);
 418       aBB.UpdateEdge(aE, aC2Dx, aF, aTol);
 419     }
 420   }
 421 }
 422 //=======================================================================
 423 //function :IsSplitToReverse
 424 //purpose  :
 425 //=======================================================================
 426 Standard_Boolean GEOMAlgo_AlgoTools::IsSplitToReverse
 427   (const TopoDS_Edge& aEF1,
 428    const TopoDS_Edge& aEF2,
 429    const Handle(BOPInt_Context)& aContext)
 430 {
 431   Standard_Boolean aFlag;
 432   Standard_Real aT1, aT2, aScPr, a, b;
 433   gp_Vec aV1, aV2;
 434   gp_Pnt aP;
 435
 436
 437   Handle(Geom_Curve)aC1=BRep_Tool::Curve(aEF1, a, b);
 438   aT1=IntTools_Tools::IntermediatePoint(a, b);
 439   aC1->D0(aT1, aP);
 440   aFlag=BOPTools_AlgoTools2D::EdgeTangent(aEF1, aT1, aV1);
 441
 442   if(!aFlag) {
 443     return Standard_False;
 444   }
 445
 446   gp_Dir aDT1(aV1);
 447   //
 448   aFlag=aContext->ProjectPointOnEdge(aP, aEF2, aT2);
 449   if(!aFlag) {
 450     return Standard_False;
 451   }
 452   //
 453   aFlag=BOPTools_AlgoTools2D::EdgeTangent(aEF2, aT2, aV2);
 454   if(!aFlag) {
 455     return Standard_False;
 456   }
 457
 458   gp_Dir aDT2(aV2);
 459
 460   aScPr=aDT1*aDT2;
 461
 462   return (aScPr<0.);
 463 }
 464
 465
 466 //=======================================================================
 467 //function : ProjectPointOnShape
 468 //purpose  :
 469 //=======================================================================
 470 Standard_Boolean GEOMAlgo_AlgoTools::ProjectPointOnShape
 471   (const gp_Pnt& aP1,
 472    const TopoDS_Shape& aS,
 473    gp_Pnt& aP2,
 474    const Handle(BOPInt_Context)& aCtx)
 475 {
 476   Standard_Boolean bIsDone = Standard_False;
 477   Standard_Real aT2;
 478   TopAbs_ShapeEnum aType;
 479   //
 480   aType = aS.ShapeType();
 481   switch (aType)
 482     {
 483     case TopAbs_EDGE:
 484       {
 485         const TopoDS_Edge& aE2 = TopoDS::Edge(aS);
 486         //
 487         if (BRep_Tool::Degenerated(aE2)) { // jfa
 488           return Standard_True;
 489         }
 490         else {
 491           Standard_Real f, l;
 492           Handle(Geom_Curve) aC3D = BRep_Tool::Curve (aE2, f, l);
 493           if (aC3D.IsNull()) {
 494             return Standard_True;
 495           }
 496           bIsDone = aCtx->ProjectPointOnEdge(aP1, aE2, aT2);
 497         }
 498         if (!bIsDone) {
 499           return bIsDone;
 500         }
 501         //
 502         GEOMAlgo_AlgoTools::PointOnEdge(aE2, aT2, aP2);
 503       }
 504       break;
 505       //
 506     case TopAbs_FACE:
 507       {
 508         const TopoDS_Face& aF2 = TopoDS::Face(aS);
 509         GeomAPI_ProjectPointOnSurf& aProj = aCtx->ProjPS(aF2);
 510         //
 511         aProj.Perform(aP1);
 512         bIsDone = aProj.IsDone();
 513         if (!bIsDone) {
 514           return bIsDone;
 515         }
 516         //
 517         aP2 = aProj.NearestPoint();
 518       }
 519       break;
 520       //
 521     default:
 522       break; // Err
 523     }
 524   return bIsDone;
 525 }
 526
 527 //=======================================================================
 528 //function : PointOnEdge
 529 //purpose  :
 530 //=======================================================================
 531 void GEOMAlgo_AlgoTools::PointOnEdge(const TopoDS_Edge& aE,
 532                                      gp_Pnt& aP3D)
 533 {
 534   Standard_Real aTx, aT1, aT2;
 535   //
 536   BRep_Tool::Curve(aE, aT1, aT2);
 537   aTx=IntTools_Tools::IntermediatePoint(aT1, aT2);
 538   GEOMAlgo_AlgoTools::PointOnEdge(aE, aTx, aP3D);
 539 }
 540 //=======================================================================
 541 //function : PointOnEdge
 542 //purpose  :
 543 //=======================================================================
 544 void GEOMAlgo_AlgoTools::PointOnEdge(const TopoDS_Edge& aE,
 545                                      const Standard_Real aT,
 546                                      gp_Pnt& aP3D)
 547 {
 548   Standard_Real aT1, aT2;
 549   Handle(Geom_Curve) aC3D;
 550   //
 551   aC3D=BRep_Tool::Curve(aE, aT1, aT2);
 552   aC3D->D0(aT, aP3D);
 553 }
 554 //=======================================================================
 555 //function : PointOnFace
 556 //purpose  :
 557 //=======================================================================
 558 void GEOMAlgo_AlgoTools::PointOnFace(const TopoDS_Face& aF,
 559                                      const Standard_Real aU,
 560                                      const Standard_Real aV,
 561                                      gp_Pnt& aP3D)
 562 {
 563   Handle(Geom_Surface) aS;
 564   //
 565   aS=BRep_Tool::Surface(aF);
 566   aS->D0(aU, aV, aP3D);
 567 }
 568 //=======================================================================
 569 //function : PointOnFace
 570 //purpose  :
 571 //=======================================================================
 572 void GEOMAlgo_AlgoTools::PointOnFace(const TopoDS_Face& aF,
 573                                      gp_Pnt& aP3D)
 574 {
 575   Standard_Real aU, aV, aUMin, aUMax, aVMin, aVMax;
 576   //
 577   BRepTools::UVBounds(aF, aUMin, aUMax, aVMin, aVMax);
 578   //
 579   aU=IntTools_Tools::IntermediatePoint(aUMin, aUMax);
 580   aV=IntTools_Tools::IntermediatePoint(aVMin, aVMax);
 581   //
 582   GEOMAlgo_AlgoTools::PointOnFace(aF, aU, aV, aP3D);
 583 }
 584 //=======================================================================
 585 //function : PointOnShape
 586 //purpose  :
 587 //=======================================================================
 588 void GEOMAlgo_AlgoTools::PointOnShape(const TopoDS_Shape& aS,
 589                                       gp_Pnt& aP3D)
 590 {
 591   TopAbs_ShapeEnum aType;
 592   //
 593   aP3D.SetCoord(99.,99.,99.);
 594   aType=aS.ShapeType();
 595   switch(aType) {
 596     case TopAbs_EDGE: {
 597       const TopoDS_Edge& aE=TopoDS::Edge(aS);
 598       GEOMAlgo_AlgoTools::PointOnEdge(aE, aP3D);
 599       }
 600       break;
 601       //
 602     case TopAbs_FACE: {
 603       const TopoDS_Face& aF=TopoDS::Face(aS);
 604       GEOMAlgo_AlgoTools::PointOnFace(aF, aP3D);
 605       }
 606       break;
 607       //
 608     default:
 609       break; // Err
 610   }
 611 }
 612 //=======================================================================
 613 //function : FindSDShapes
 614 //purpose  :
 615 //=======================================================================
 616 Standard_Integer GEOMAlgo_AlgoTools::FindSDShapes
 617   (const TopoDS_Shape& aE1,
 618    const TopTools_ListOfShape& aLE,
 619    const Standard_Real aTol,
 620    TopTools_ListOfShape& aLESD,
 621    const Handle(BOPInt_Context)& aCtx)
 622 {
 623   Standard_Boolean bIsDone;
 624   Standard_Real aTol2, aD2;
 625   gp_Pnt aP1, aP2;
 626   TopTools_ListIteratorOfListOfShape aIt;
 627   //
 628   aTol2=aTol*aTol;
 629   GEOMAlgo_AlgoTools::PointOnShape(aE1, aP1);
 630   //
 631   aIt.Initialize(aLE);
 632   for (; aIt.More(); aIt.Next()) {
 633     const TopoDS_Shape& aE2=aIt.Value();
 634     if (aE2.IsSame(aE1)) {
 635        aLESD.Append(aE2);
 636     }
 637     else {
 638       bIsDone=GEOMAlgo_AlgoTools::ProjectPointOnShape(aP1, aE2, aP2, aCtx);
 639       if (!bIsDone) {
 640         //return 1;
 641         continue; // jfa BUG 20361
 642       }
 643       aD2=aP1.SquareDistance(aP2);
 644       if(aD2<aTol2) {
 645         aLESD.Append(aE2);
 646       }
 647     }
 648   }
 649   return 0;
 650 }
 651
 652 //=======================================================================
 653 //function : FindSDShapes
 654 //purpose  :
 655 //=======================================================================
 656 Standard_Integer GEOMAlgo_AlgoTools::FindSDShapes
 657   (const TopTools_ListOfShape& aLE,
 658    const Standard_Real aTol,
 659    TopTools_IndexedDataMapOfShapeListOfShape& aMEE,
 660    const Handle(BOPInt_Context)& aCtx)
 661 {
 662   Standard_Integer aNbE, aNbEProcessed, aNbESD, iErr;
 663   TopTools_ListOfShape aLESD;
 664   TopTools_ListIteratorOfListOfShape aIt, aIt1;
 665   TopTools_IndexedMapOfShape aMProcessed;
 666   TopAbs_ShapeEnum aType;
 667   //
 668   aNbE=aLE.Extent();
 669   if (!aNbE) {
 670     return 3; // Err
 671   }
 672   if (aNbE==1) {
 673     return 0; // Nothing to do
 674   }
 675   //
 676   while(1) {
 677     aNbEProcessed=aMProcessed.Extent();
 678     if (aNbEProcessed==aNbE) {
 679       break;
 680     }
 681     //
 682     aIt.Initialize(aLE);
 683     for (; aIt.More(); aIt.Next()) {
 684       const TopoDS_Shape& aS=aIt.Value();
 685       //
 686       if (aMProcessed.Contains(aS)) {
 687         continue;
 688       }
 689       //
 690       aType=aS.ShapeType();
 691       if (aType==TopAbs_EDGE) {
 692         const TopoDS_Edge& aE=TopoDS::Edge(aS);
 693         if (BRep_Tool::Degenerated(aE)) {
 694           aMProcessed.Add(aE);
 695           continue;
 696         }
 697       }
 698       //
 699       aLESD.Clear();
 700       iErr=GEOMAlgo_AlgoTools::FindSDShapes(aS, aLE, aTol, aLESD, aCtx);
 701       if (iErr) {
 702         return 2; // Err
 703       }
 704       //
 705       aNbESD=aLESD.Extent();
 706       if (!aNbESD) {
 707         return 1; // Err
 708       }
 709       //
 710       aMEE.Add(aS, aLESD);
 711       //
 712       aIt1.Initialize(aLESD);
 713       for (; aIt1.More(); aIt1.Next()) {
 714         const TopoDS_Shape& aE1=aIt1.Value();
 715         aMProcessed.Add(aE1);
 716       }
 717     }
 718   }
 719   return 0;
 720 }
 721 //=======================================================================
 722 //function : RefineSDShapes
 723 //purpose  :
 724 //=======================================================================
 725 Standard_Integer GEOMAlgo_AlgoTools::RefineSDShapes
 726   (GEOMAlgo_IndexedDataMapOfPassKeyShapeListOfShape& aMPKLE,
 727    const Standard_Real aTol,
 728    const Handle(BOPInt_Context)& aCtx)
 729 {
 730   Standard_Integer i, aNbE, iErr, j, aNbEE, aNbToAdd;
 731   TopTools_IndexedDataMapOfShapeListOfShape aMEE, aMSDE, aMEToAdd;
 732   //
 733   iErr=1;
 734   //
 735   aNbE=aMPKLE.Extent();
 736   for (i=1; i<=aNbE; ++i) {
 737     TopTools_ListOfShape& aLSDE=aMPKLE.ChangeFromIndex(i);
 738     //
 739     aMEE.Clear();
 740     iErr=GEOMAlgo_AlgoTools::FindSDShapes(aLSDE, aTol, aMEE, aCtx);
 741     if (iErr) {
 742       return iErr;
 743     }
 744     //
 745     aNbEE=aMEE.Extent();
 746     if (aNbEE==1) {
 747       continue;  // nothing to do
 748     }
 749     //
 750     for (j=1; j<=aNbEE; ++j) {
 751       TopTools_ListOfShape& aLEE=aMEE.ChangeFromIndex(j);
 752       //
 753       if (j==1) {
 754         aLSDE.Clear();
 755         aLSDE.Append(aLEE);
 756       }
 757       else {
 758         const TopoDS_Shape& aE1=aLEE.First();
 759         aMEToAdd.Add(aE1, aLEE);
 760       }
 761     }
 762   }
 763   //
 764   aNbToAdd=aMEToAdd.Extent();
 765   if (!aNbToAdd) {
 766     return aNbToAdd;
 767   }
 768   //
 769   for (i=1; i<=aNbToAdd; ++i) {
 770     GEOMAlgo_PassKeyShape aPKE1;
 771     //
 772     const TopoDS_Shape& aE1=aMEToAdd.FindKey(i);
 773     const TopTools_ListOfShape& aLE=aMEToAdd(i);
 774     //
 775     aPKE1.SetShapes(aE1);
 776     aMPKLE.Add(aPKE1, aLE);
 777   }
 778   //
 779   return 0;
 780 }
 781 //=======================================================================
 782 //function : BuildTriangulation
 783 //purpose  :
 784 //=======================================================================
 785 Standard_Boolean
 786   GEOMAlgo_AlgoTools::BuildTriangulation (const TopoDS_Shape& theShape)
 787 {
 788   // calculate deflection
 789   Standard_Real aDeviationCoefficient = 0.001;
 790
 791   Bnd_Box B;
 792   BRepBndLib::Add(theShape, B);
 793   Standard_Real aXmin, aYmin, aZmin, aXmax, aYmax, aZmax;
 794   B.Get(aXmin, aYmin, aZmin, aXmax, aYmax, aZmax);
 795
 796   Standard_Real dx = aXmax - aXmin, dy = aYmax - aYmin, dz = aZmax - aZmin;
 797   Standard_Real aDeflection = Max(Max(dx, dy), dz) * aDeviationCoefficient * 4;
 798   Standard_Real aHLRAngle = 0.349066;
 799
 800   // build triangulation
 801   BRepMesh_IncrementalMesh Inc (theShape, aDeflection, Standard_False, aHLRAngle);
 802
 803   // check triangulation
 804   bool isTriangulation = true;
 805
 806   TopExp_Explorer exp (theShape, TopAbs_FACE);
 807   if (exp.More())
 808   {
 809     TopLoc_Location aTopLoc;
 810     Handle(Poly_Triangulation) aTRF;
 811     aTRF = BRep_Tool::Triangulation(TopoDS::Face(exp.Current()), aTopLoc);
 812     if (aTRF.IsNull()) {
 813       isTriangulation = false;
 814     }
 815   }
 816   else // no faces, try edges
 817   {
 818     TopExp_Explorer expe (theShape, TopAbs_EDGE);
 819     if (!expe.More()) {
 820       isTriangulation = false;
 821     }
 822     else {
 823       TopLoc_Location aLoc;
 824       Handle(Poly_Polygon3D) aPE = BRep_Tool::Polygon3D(TopoDS::Edge(expe.Current()), aLoc);
 825       if (aPE.IsNull()) {
 826         isTriangulation = false;
 827       }
 828     }
 829   }
 830   return isTriangulation;
 831 }
 832
 833 //=======================================================================
 834 //function : IsCompositeShape
 835 //purpose  :
 836 //=======================================================================
 837 Standard_Boolean GEOMAlgo_AlgoTools::IsCompositeShape(const TopoDS_Shape& aS)
 838 {
 839   Standard_Boolean bRet;
 840   Standard_Integer iCnt;
 841   TopoDS_Iterator aIt;
 842   //
 843   iCnt=0;
 844   GetCount(aS, iCnt);
 845   bRet=(iCnt>1);
 846   //
 847   return bRet;
 848 }
 849 //=======================================================================
 850 //function : GetCount
 851 //purpose  :
 852 //=======================================================================
 853 void GetCount(const TopoDS_Shape& aS,
 854               Standard_Integer& iCnt)
 855 {
 856   TopoDS_Iterator aIt;
 857   TopAbs_ShapeEnum aTS;
 858   //
 859   aTS=aS.ShapeType();
 860   //
 861   if (aTS==TopAbs_SHAPE) {
 862     return;
 863   }
 864   if (aTS!=TopAbs_COMPOUND) {
 865     ++iCnt;
 866     return;
 867   }
 868   //
 869   aIt.Initialize(aS);
 870   for (; aIt.More(); aIt.Next()) {
 871     const TopoDS_Shape& aSx=aIt.Value();
 872     GetCount(aSx, iCnt);
 873   }
 874 }
 875 //=======================================================================
 876 //function : PntInFace
 877 //purpose  :
 878 //=======================================================================
 879 Standard_Integer GEOMAlgo_AlgoTools::PntInFace(const TopoDS_Face& aF,
 880                                                gp_Pnt& theP,
 881                                                gp_Pnt2d& theP2D)
 882 {
 883   Standard_Boolean bIsDone, bHasFirstPoint, bHasSecondPoint;
 884   Standard_Integer iErr, aIx, aNbDomains, i;
 885   Standard_Real aUMin, aUMax, aVMin, aVMax;
 886   Standard_Real aVx, aUx, aV1, aV2, aU1, aU2, aEpsT;
 887   Standard_Real aTotArcIntr, aTolTangfIntr, aTolHatch2D, aTolHatch3D;
 888   gp_Dir2d aD2D (0., 1.);
 889   gp_Pnt2d aP2D;
 890   gp_Pnt aPx;
 891   Handle(Geom2d_Curve) aC2D;
 892   Handle(Geom2d_TrimmedCurve) aCT2D;
 893   Handle(Geom2d_Line) aL2D;
 894   Handle(Geom_Surface) aS;
 895   TopAbs_Orientation aOrE;
 896   TopoDS_Face aFF;
 897   TopExp_Explorer aExp;
 898   //
 899   aTolHatch2D=1.e-8;
 900   aTolHatch3D=1.e-8;
 901   aTotArcIntr=1.e-10;
 902   aTolTangfIntr=1.e-10;
 903   //
 904   Geom2dHatch_Intersector aIntr(aTotArcIntr, aTolTangfIntr);
 905   Geom2dHatch_Hatcher aHatcher(aIntr,
 906                                aTolHatch2D, aTolHatch3D,
 907                                Standard_True, Standard_False);
 908   //
 909   iErr=0;
 910   aEpsT=1.e-12;
 911   //
 912   aFF=aF;
 913   aFF.Orientation (TopAbs_FORWARD);
 914   //
 915   aS=BRep_Tool::Surface(aFF);
 916   BRepTools::UVBounds(aFF, aUMin, aUMax, aVMin, aVMax);
 917   //
 918   // 1
 919   aExp.Init (aFF, TopAbs_EDGE);
 920   for (; aExp.More() ; aExp.Next()) {
 921     const TopoDS_Edge& aE=*((TopoDS_Edge*)&aExp.Current());
 922     aOrE=aE.Orientation();
 923     //
 924     aC2D=BRep_Tool::CurveOnSurface (aE, aFF, aU1, aU2);
 925     if (aC2D.IsNull() ) {
 926       iErr=1;
 927       return iErr;
 928     }
 929     if (fabs(aU1-aU2) < aEpsT) {
 930       iErr=2;
 931       return iErr;
 932     }
 933     //
 934     aCT2D=new Geom2d_TrimmedCurve(aC2D, aU1, aU2);
 935     aHatcher.AddElement(aCT2D, aOrE);
 936   }// for (; aExp.More() ; aExp.Next()) {
 937   //
 938   // 2
 939   aUx=IntTools_Tools::IntermediatePoint(aUMin, aUMax);
 940   aP2D.SetCoord(aUx, 0.);
 941   aL2D=new Geom2d_Line (aP2D, aD2D);
 942   Geom2dAdaptor_Curve aHCur(aL2D);
 943   //
 944   aIx=aHatcher.AddHatching(aHCur) ;
 945   //
 946   // 3.
 947   aHatcher.Trim();
 948   bIsDone=aHatcher.TrimDone(aIx);
 949   if (!bIsDone) {
 950     iErr=3;
 951     return iErr;
 952   }
 953   //
 954   aHatcher.ComputeDomains(aIx);
 955   bIsDone=aHatcher.IsDone(aIx);
 956   if (!bIsDone) {
 957     iErr=4;
 958     return iErr;
 959   }
 960   //
 961   // 4.
 962   aNbDomains=aHatcher.NbDomains(aIx);
 963   for (i=1; i<=aNbDomains; ++i) {
 964     const HatchGen_Domain& aDomain=aHatcher.Domain (aIx, i) ;
 965     bHasFirstPoint=aDomain.HasFirstPoint();
 966     if (!bHasFirstPoint) {
 967       iErr=5;
 968       return iErr;
 969     }
 970     //
 971     aV1=aDomain.FirstPoint().Parameter();
 972     //
 973     bHasSecondPoint=aDomain.HasSecondPoint();
 974     if (!bHasSecondPoint) {
 975       iErr=6;
 976       return iErr;
 977     }
 978     //
 979     aV2=aDomain.SecondPoint().Parameter();
 980     //
 981     aVx=IntTools_Tools::IntermediatePoint(aV1, aV2);
 982     //
 983     break;
 984   }
 985   //
 986   aS->D0(aUx, aVx, aPx);
 987   //
 988   theP2D.SetCoord(aUx, aVx);
 989   theP=aPx;
 990   //
 991   return iErr;
 992 }