src/BRepFill/BRepFill_TrimShellCorner.cxx

   1 // Created on: 2003-10-21
   2 // Created by: Mikhail KLOKOV
   3 // Copyright (c) 2003-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #include <BRepFill_TrimShellCorner.ixx>
  17
  18 #include <BRepAlgoAPI_Section.hxx>
  19 #include <BRep_Builder.hxx>
  20 #include <BRep_Tool.hxx>
  21 #include <BRepLib_MakeEdge.hxx>
  22 #include <BRepTools_ReShape.hxx>
  23 #include <TopoDS.hxx>
  24 #include <TopoDS_Shell.hxx>
  25 #include <TopoDS_Compound.hxx>
  26
  27 #include <IntTools_BeanFaceIntersector.hxx>
  28 #include <BOPInt_Context.hxx>
  29 #include <IntTools_Range.hxx>
  30
  31 #include <Geom_Curve.hxx>
  32 #include <Geom2d_Curve.hxx>
  33 #include <gp_Pnt2d.hxx>
  34
  35 #include <TopLoc_Location.hxx>
  36 #include <TopExp.hxx>
  37 #include <TopExp_Explorer.hxx>
  38 #include <TopTools_MapOfShape.hxx>
  39 #include <TopTools_ListOfShape.hxx>
  40 #include <TopTools_Array1OfListOfShape.hxx>
  41 #include <TopTools_ListIteratorOfListOfShape.hxx>
  42 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  43 #include <TopTools_DataMapOfShapeListOfShape.hxx>
  44 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
  45
  46 #include <gp_Pln.hxx>
  47 #include <TopoDS_Iterator.hxx>
  48 #include <TColgp_Array1OfPnt.hxx>
  49 #include <TColgp_Array2OfPnt.hxx>
  50 #include <TColgp_Array1OfDir.hxx>
  51 #include <TColStd_ListOfInteger.hxx>
  52 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  53 #include <GCPnts_UniformAbscissa.hxx>
  54 #include <GeomLib.hxx>
  55 #include <BRepLib_MakeWire.hxx>
  56 #include <TopTools_SequenceOfShape.hxx>
  57 #include <TColStd_Array1OfBoolean.hxx>
  58 #include <TColgp_SequenceOfPnt.hxx>
  59 #include <gce_MakeLin.hxx>
  60
  61 #include <BOPInt_Tools.hxx>
  62 #include <BOPAlgo_PaveFiller.hxx>
  63 #include <BOPDS_DS.hxx>
  64 #include <BOPAlgo_BOP.hxx>
  65
  66 #include <BOPCol_DataMapOfShapeListOfShape.hxx>
  67 #include <BOPCol_ListOfShape.hxx>
  68
  69 static Standard_Boolean FindCommonVertex(const BOPDS_PDS&         theDS,
  70                                          const Standard_Integer   theEIndex1,
  71                                          const Standard_Integer   theEIndex2,
  72                                          TopoDS_Vertex&           theCommonVertex,
  73                                          Standard_Real&           theParamOnE1,
  74                                          Standard_Real&           theParamOnE2);
  75
  76 static Standard_Boolean MakeFacesNonSec(const Standard_Integer                     theIndex,
  77                                         const Handle(TopTools_HArray2OfShape)&     theUEdges,
  78                                         const Handle(TopTools_HArray2OfShape)&     theBounds,
  79                                         const BOPDS_PDS&                           theDS,
  80                                         const Standard_Integer                     theFaceIndex1,
  81                                         const Standard_Integer                     theFaceIndex2,
  82                                         TopTools_DataMapOfShapeListOfShape&        theHistMap);
  83
  84 static Standard_Boolean MakeFacesSec(const Standard_Integer                     theIndex,
  85                                      const Handle(TopTools_HArray2OfShape)&     theUEdges,
  86                                      const Handle(TopTools_HArray2OfShape)&     theBounds,
  87                                      const BOPDS_PDS&                           theDS,
  88                                      const Standard_Integer                     theFaceIndex1,
  89                                      const Standard_Integer                     theFaceIndex2,
  90                                      const Standard_Integer                     theSSInterfIndex,
  91                                      const gp_Ax2&                              AxeOfBisPlane,
  92                                      TopTools_DataMapOfShapeListOfShape&        theHistMap);
  93
  94 static Standard_Boolean SplitUEdges(const Handle(TopTools_HArray2OfShape)&     theUEdges,
  95                                     const BOPDS_PDS&                           theDS,
  96                                     TopTools_DataMapOfShapeListOfShape&        theHistMap);
  97
  98 static void FindFreeVertices(const TopoDS_Shape&         theShape,
  99                              const TopTools_MapOfShape&  theVerticesToAvoid,
 100                              TopTools_ListOfShape&       theListOfVertex);
 101
 102 static Standard_Boolean CheckAndOrientEdges(const TopTools_ListOfShape&  theOrderedList,
 103                                             const gp_Pnt2d&              theFirstPoint,
 104                                             const gp_Pnt2d&              theLastPoint,
 105                                             const TopoDS_Face&           theFace,
 106                                             TopTools_ListOfShape&        theOrientedList);
 107
 108 static Standard_Boolean FillGap(const TopoDS_Vertex&   theFirstVertex,
 109                                 const TopoDS_Vertex&   theLastVertex,
 110                                 const gp_Pnt2d&        theFirstPoint,
 111                                 const gp_Pnt2d&        theLastPoint,
 112                                 const TopoDS_Face&     theFace,
 113                                 const TopoDS_Compound& theSectionEdges,
 114                                 TopTools_ListOfShape&  theOrderedList);
 115
 116 static Standard_Boolean FindNextEdge(const TopoDS_Vertex&   theFirstVertex,
 117                                      const TopoDS_Vertex&   theLastVertex,
 118                                      const TopTools_IndexedDataMapOfShapeListOfShape& theMapVE,
 119                                      const TopTools_MapOfShape& theMapToAvoid,
 120                                      TopTools_ListOfShape&  theOrderedList);
 121
 122 static Standard_Boolean FindVertex(const TopoDS_Edge&                        theEdge,
 123                                    const Standard_Integer                    theRank,
 124                                    const BOPDS_PDS&                          theDS,
 125                                    const TopTools_DataMapOfShapeListOfShape& theHistMap,
 126                                    TopoDS_Vertex&                            theVertex,
 127                                    BOPDS_Pave&                               thePave);
 128
 129 static Standard_Boolean FindNextVertex(const Standard_Integer                    theEdgeIndex,
 130                                        const BOPDS_Pave&                         thePrevPave,
 131                                        const BOPDS_PDS&                          theDS,
 132                                        TopoDS_Vertex&                            theNextVertex,
 133                                        BOPDS_Pave&                               thePave);
 134
 135 static Standard_Boolean GetPave(const Standard_Integer    theEdgeIndex,
 136                                 const Standard_Boolean    isFirst,
 137                                 const BOPDS_PDS&          theDS,
 138                                 BOPDS_Pave&               thePave);
 139
 140 static Standard_Boolean FindFromUEdge(const TopoDS_Edge&                        theUE1Old,
 141                                       const TopoDS_Edge&                        theUE2Old,
 142                                       const TopoDS_Edge&                        theUE1New,
 143                                       const TopoDS_Edge&                        theUE2New,
 144                                       const TopoDS_Face&                        theFace,
 145                                       const TopoDS_Compound&                    theSecEdges,
 146                                       const Standard_Integer                    theRank,
 147                                       const TopoDS_Edge&                        theBoundEdge,
 148                                       const Standard_Integer                    theBoundEdgeIndex,
 149                                       const BOPDS_PDS&                          theDS,
 150                                       const TopTools_DataMapOfShapeListOfShape& theHistMap,
 151                                       TopoDS_Compound&                          theSecEdgesNew,
 152                                       TopTools_ListOfShape&                     theListOfWireEdges,
 153                                       BOPDS_Pave&                               theFoundPave,
 154                                       Standard_Boolean&                         isOnUEdge);
 155
 156 static Standard_Boolean FindFromVEdge(const BOPDS_Pave&                         thePrevPave,
 157                                       const Standard_Boolean&                   isOnUEdge,
 158                                       const TopoDS_Edge&                        theUE1Old,
 159                                       const TopoDS_Edge&                        theUE2Old,
 160                                       const TopoDS_Face&                        theFace,
 161                                       const TopoDS_Compound&                    theSecEdges,
 162                                       const Standard_Integer                    theRank,
 163                                       const TopoDS_Edge&                        theBoundEdge,
 164                                       const Standard_Integer                    theBoundEdgeIndex,
 165                                       const BOPDS_PDS&                          theDS,
 166                                       const TopTools_DataMapOfShapeListOfShape& theHistMap,
 167                                       TopTools_ListOfShape&                     theListOfWireEdges,
 168                                       Standard_Boolean&                         isSectionFound);
 169
 170 static void RemoveEdges(const TopoDS_Compound&      theSourceComp,
 171                         const TopTools_ListOfShape& theListToRemove,
 172                         TopoDS_Compound&            theResultComp);
 173
 174 static Standard_Boolean FilterSectionEdges(const BOPDS_VectorOfCurve&       theBCurves,
 175                                            const TopoDS_Face&               theSecPlane,
 176                                            const BOPDS_PDS&                 theDS,
 177                                            TopoDS_Compound&                 theResult);
 178
 179 static Standard_Boolean GetUEdges(const Standard_Integer                     theIndex,
 180                                   const Standard_Integer                     theRank,
 181                                   const Handle(TopTools_HArray2OfShape)&     theUEdges,
 182                                   const TopoDS_Edge&                         theBoundEdge,
 183                                   const TopoDS_Face&                         theFace,
 184                                   TopoDS_Edge&                               theFirstUEdge,
 185                                   TopoDS_Edge&                               theSecondUEdge);
 186
 187 static Standard_Real ComputeAveragePlaneAndMaxDeviation(const TopoDS_Shape& aWire,
 188                                                         gp_Pln& thePlane,
 189                                                         Standard_Boolean& IsSingular);
 190
 191 static Standard_Boolean ChooseSection(const TopoDS_Shape& Comp,
 192                                       const gp_Ax2& bis,
 193                                       TopoDS_Shape& resWire,
 194                                       gp_Pln& resPlane,
 195                                       Standard_Boolean& IsSingular);
 196
 197 // ===========================================================================================
 198 // function: Constructor
 199 // purpose:
 200 // ===========================================================================================
 201 BRepFill_TrimShellCorner::BRepFill_TrimShellCorner(const Handle(TopTools_HArray2OfShape)& theFaces,
 202                                                    const gp_Ax2&                          theAxeOfBisPlane,
 203                                                    const TopoDS_Face&                     theSecPlane) :
 204 myAxeOfBisPlane(theAxeOfBisPlane),
 205 myDone(Standard_False),
 206 myHasSection(Standard_False)
 207 {
 208   myFaces = new TopTools_HArray2OfShape(theFaces->LowerRow(), theFaces->UpperRow(),
 209                                         theFaces->LowerCol(), theFaces->UpperCol());
 210   myFaces->ChangeArray2() = theFaces->Array2();
 211   mySecPln = theSecPlane;
 212 }
 213
 214 // ===========================================================================================
 215 // function: Constructor
 216 // purpose:
 217 // ===========================================================================================
 218 BRepFill_TrimShellCorner::BRepFill_TrimShellCorner(const Handle(TopTools_HArray2OfShape)& theFaces,
 219                                                    const gp_Ax2&                          theAxeOfBisPlane,
 220                                                    const TopoDS_Wire&                     theSpine,
 221                                                    const TopoDS_Face&                     theSecPlane):
 222 myAxeOfBisPlane(theAxeOfBisPlane),
 223 myDone(Standard_False),
 224 myHasSection(Standard_False)
 225 {
 226   myFaces = new TopTools_HArray2OfShape(theFaces->LowerRow(), theFaces->UpperRow(),
 227                                         theFaces->LowerCol(), theFaces->UpperCol());
 228   myFaces->ChangeArray2() = theFaces->Array2();
 229   mySpine = theSpine;
 230   mySecPln = theSecPlane;
 231 }
 232
 233 // ===========================================================================================
 234 // function: SetSpine
 235 // purpose:
 236 // ===========================================================================================
 237 void BRepFill_TrimShellCorner::SetSpine(const TopoDS_Wire& theSpine)
 238 {
 239   mySpine = theSpine;
 240 }
 241
 242 // ===========================================================================================
 243 // function: AddBounds
 244 // purpose:
 245 // ===========================================================================================
 246 void BRepFill_TrimShellCorner::AddBounds(const Handle(TopTools_HArray2OfShape)& theBounds)
 247 {
 248   myBounds = new TopTools_HArray2OfShape(theBounds->LowerRow(), theBounds->UpperRow(),
 249                                          theBounds->LowerCol(), theBounds->UpperCol());
 250   myBounds->ChangeArray2() = theBounds->Array2();
 251 }
 252
 253 // ===========================================================================================
 254 // function: AddUEdges
 255 // purpose:
 256 // ===========================================================================================
 257 void BRepFill_TrimShellCorner::AddUEdges(const Handle(TopTools_HArray2OfShape)& theUEdges)
 258 {
 259   myUEdges = new TopTools_HArray2OfShape(theUEdges->LowerRow(), theUEdges->UpperRow(),
 260                                          theUEdges->LowerCol(), theUEdges->UpperCol());
 261   myUEdges->ChangeArray2() = theUEdges->Array2();
 262 }
 263
 264 // ===========================================================================================
 265 // function: Perform
 266 // purpose:
 267 // ===========================================================================================
 268 void BRepFill_TrimShellCorner::Perform()
 269 {
 270   Standard_Integer anIndex1, anIndex2, nF1, nF2, i, j, aNbP, aNbC;
 271   Standard_Boolean bhassec;
 272
 273   myDone = Standard_False;
 274   myHistMap.Clear();
 275
 276   if(myFaces->RowLength() != 2)
 277     return;
 278   Standard_Integer ii = 0, jj = 0;
 279   BRep_Builder aBB;
 280
 281   for(jj = myFaces->LowerCol(); jj <= myFaces->UpperCol(); jj++) {
 282     TopoDS_Shell aShell;
 283     aBB.MakeShell(aShell);
 284
 285     for(ii = myFaces->LowerRow(); ii <= myFaces->UpperRow(); ii++) {
 286       aBB.Add(aShell, myFaces->Value(ii, jj));
 287     }
 288
 289     if(jj == myFaces->LowerCol()) {
 290       myShape1 = aShell;
 291     }
 292     else {
 293       myShape2 = aShell;
 294     }
 295   }
 296
 297   BOPAlgo_PaveFiller aPF;
 298   BOPCol_ListOfShape aLS;
 299   aLS.Append(myShape1);
 300   aLS.Append(myShape2);
 301   aPF.SetArguments(aLS);
 302   //
 303   aPF.Perform();
 304   if (aPF.ErrorStatus()) {
 305     return;
 306   }
 307   //
 308   const BOPDS_PDS& theDS = aPF.PDS();
 309   //
 310   BOPDS_VectorOfInterfFF& aFFs = theDS->InterfFF();
 311   Standard_Integer aNbFFs = aFFs.Extent();
 312
 313   if(!SplitUEdges(myUEdges, theDS, myHistMap)) {
 314     return;
 315   }
 316
 317   for(ii = myFaces->LowerRow(); ii <= myFaces->UpperRow(); ii++) {
 318     TopoDS_Shape aF1 = myFaces->Value(ii, myFaces->LowerCol());
 319     TopoDS_Shape aF2 = myFaces->Value(ii, myFaces->UpperCol());
 320     //
 321     anIndex1 = theDS->Index(aF1);
 322     anIndex2 = theDS->Index(aF2);
 323
 324     if((anIndex1 == -1) || (anIndex2 == -1))
 325       continue;
 326
 327     for (i=0; i < aNbFFs; ++i) {
 328       BOPDS_InterfFF& aFFi = aFFs(i);
 329       aFFi.Indices(nF1, nF2);
 330       //
 331       BOPDS_VectorOfPoint& aVP=aFFi.ChangePoints();
 332       aNbP=aVP.Extent();
 333       BOPDS_VectorOfCurve& aVC=aFFi.ChangeCurves();
 334       aNbC=aVC.Extent();
 335       if (!aNbP && !aNbC) {
 336         if (!theDS->HasInterfSubShapes(nF1, nF2)) {
 337           continue;
 338         }
 339       }
 340       //
 341       if((nF1 == anIndex1) && (nF2 == anIndex2)) {
 342         const BOPDS_VectorOfCurve& aVC = aFFi.Curves();
 343         bhassec = Standard_False;
 344         //
 345         for (j = 0; j < aNbC; ++j) {
 346           const BOPDS_Curve& aBCurve = aVC(j);
 347           const BOPDS_ListOfPaveBlock& aSectEdges = aBCurve.PaveBlocks();
 348           //
 349           if (aSectEdges.Extent()) {
 350             bhassec = Standard_True;
 351             break;
 352           }
 353         }
 354
 355         if(!bhassec) {
 356           if(!MakeFacesNonSec(ii, myUEdges, myBounds, theDS, anIndex1, anIndex2, myHistMap)) {
 357             myHistMap.Clear();
 358             return;
 359           }
 360         }
 361         else {
 362           if(!MakeFacesSec(ii, myUEdges, myBounds, theDS, anIndex1, anIndex2,
 363                            i, myAxeOfBisPlane, myHistMap)) {
 364             myHistMap.Clear();
 365             return;
 366           }
 367         }
 368         break;
 369       }
 370     }
 371   }
 372   myDone = Standard_True;
 373 }
 374
 375 // ===========================================================================================
 376 // function: IsDone
 377 // purpose:
 378 // ===========================================================================================
 379 Standard_Boolean BRepFill_TrimShellCorner::IsDone() const
 380 {
 381   return myDone;
 382 }
 383
 384 // ===========================================================================================
 385 // function: HasSection
 386 // purpose:
 387 // ===========================================================================================
 388 Standard_Boolean BRepFill_TrimShellCorner::HasSection() const
 389 {
 390   return myHasSection;
 391 }
 392
 393 // ===========================================================================================
 394 // function: Modified
 395 // purpose:
 396 // ===========================================================================================
 397 void BRepFill_TrimShellCorner::Modified(const TopoDS_Shape&   theShape,
 398                                         TopTools_ListOfShape& theModified)
 399 {
 400   theModified.Clear();
 401
 402   if(myHistMap.IsBound(theShape)) {
 403     theModified = myHistMap.Find(theShape);
 404   }
 405 }
 406
 407 // ----------------------------------------------------------------------------------------------------
 408 // static function: MakeFacesNonSec
 409 // purpose:
 410 // ----------------------------------------------------------------------------------------------------
 411 Standard_Boolean MakeFacesNonSec(const Standard_Integer                     theIndex,
 412                                  const Handle(TopTools_HArray2OfShape)&     theUEdges,
 413                                  const Handle(TopTools_HArray2OfShape)&     theBounds,
 414                                  const BOPDS_PDS&                           theDS,
 415                                  const Standard_Integer                     theFaceIndex1,
 416                                  const Standard_Integer                     theFaceIndex2,
 417                                  TopTools_DataMapOfShapeListOfShape&        theHistMap)
 418 {
 419   Standard_Boolean bHasNewEdge = Standard_False;
 420   TopoDS_Edge aNewEdge;
 421
 422   BRep_Builder aBB;
 423   const TopoDS_Shape& aE1 = theBounds->Value(theIndex, 1);
 424   const TopoDS_Shape& aE2 = theBounds->Value(theIndex, 2);
 425
 426   // search common vertex between bounds. begin
 427   TopoDS_Vertex aCommonVertex;
 428   Standard_Integer anIndex1 = theDS->Index(aE1);
 429   Standard_Integer anIndex2 = theDS->Index(aE2);
 430   Standard_Real apar1 = 0., apar2 = 0.;
 431
 432   Standard_Boolean bvertexfound =
 433     FindCommonVertex(theDS, anIndex1, anIndex2, aCommonVertex, apar1, apar2);
 434   // search common vertex between bounds. end
 435
 436   Handle(BRepTools_ReShape) aSubstitutor = new BRepTools_ReShape();
 437
 438   // search common vertices between uedges. begin
 439   TopTools_ListOfShape aCommonVertices;
 440   Standard_Boolean acommonflag = 0; // 0 - no, 1 - first pair, 2 - second pair, 3 - both
 441   Standard_Integer ueit = 0, eindex = 0;
 442
 443   for(ueit = 1, eindex = theIndex; ueit <= 2; ueit++, eindex++) {
 444     const TopoDS_Shape& aShape1 = theUEdges->Value(eindex, theUEdges->LowerCol());
 445     const TopoDS_Shape& aShape2 = theUEdges->Value(eindex, theUEdges->UpperCol());
 446     TopoDS_Edge aUE1 = TopoDS::Edge(aShape1);
 447     TopoDS_Edge aUE2 = TopoDS::Edge(aShape2);
 448
 449     if(theHistMap.IsBound(aShape1)) {
 450       const TopTools_ListOfShape& lst = theHistMap.Find(aShape1);
 451
 452       if(!lst.IsEmpty())
 453         aUE1 = TopoDS::Edge(lst.First());
 454     }
 455
 456     if(theHistMap.IsBound(aShape2)) {
 457       const TopTools_ListOfShape& lst = theHistMap.Find(aShape2);
 458
 459       if(!lst.IsEmpty())
 460         aUE2 = TopoDS::Edge(lst.First());
 461     }
 462
 463     if(!aShape1.IsSame(aUE1))
 464       aSubstitutor->Replace(aShape1.Oriented(TopAbs_FORWARD), aUE1.Oriented(TopAbs_FORWARD));
 465
 466     if(!aShape2.IsSame(aUE2))
 467       aSubstitutor->Replace(aShape2.Oriented(TopAbs_FORWARD), aUE2.Oriented(TopAbs_FORWARD));
 468
 469     TopoDS_Vertex V1 = TopExp::LastVertex(aUE1);
 470     TopoDS_Vertex V2 = TopExp::FirstVertex(aUE2);
 471
 472     if(V1.IsSame(V2)) {
 473       acommonflag = (acommonflag == 0) ? ueit : 3;
 474       aCommonVertices.Append(V1);
 475     }
 476   }
 477   // search common vertices between uedges. end
 478
 479   if(bvertexfound) {
 480     if(aCommonVertices.Extent() != 1)
 481       return Standard_False;
 482
 483     if(acommonflag == 1)
 484       aNewEdge = BRepLib_MakeEdge(TopoDS::Vertex(aCommonVertices.First()), aCommonVertex);
 485     else
 486       aNewEdge = BRepLib_MakeEdge(aCommonVertex, TopoDS::Vertex(aCommonVertices.First()));
 487
 488     bHasNewEdge = Standard_True;
 489   }
 490
 491   if(aCommonVertices.Extent() == 2) {
 492     aNewEdge = BRepLib_MakeEdge(TopoDS::Vertex(aCommonVertices.First()),
 493                                 TopoDS::Vertex(aCommonVertices.Last()));
 494     bHasNewEdge = Standard_True;
 495   }
 496   Standard_Integer fit = 0;
 497
 498   for(fit = 1; fit <= 2; fit++) {
 499     TopoDS_Compound aComp;
 500     TopTools_MapOfShape aMapV;
 501     aBB.MakeCompound(aComp);
 502
 503     for(ueit = 1, eindex = theIndex; ueit <= 2; ueit++, eindex++) {
 504       const TopoDS_Shape& aShape = theUEdges->Value(eindex, theUEdges->LowerCol() + fit - 1);
 505       TopoDS_Shape aUE = aShape;
 506
 507       if(theHistMap.IsBound(aShape)) {
 508         const TopTools_ListOfShape& lst = theHistMap.Find(aShape);
 509
 510         if(!lst.IsEmpty())
 511           aUE = TopoDS::Edge(lst.First());
 512       }
 513       const TopoDS_Shape& aV = (fit == 1) ? TopExp::FirstVertex(TopoDS::Edge(aUE)) : TopExp::LastVertex(TopoDS::Edge(aUE));
 514       aMapV.Add(aV);
 515       aBB.Add(aComp, aUE);
 516     }
 517     if(bHasNewEdge) {
 518       aBB.Add(aComp, aNewEdge);
 519     }
 520     TopTools_ListOfShape alonevertices;
 521     FindFreeVertices(aComp, aMapV, alonevertices);
 522
 523     if(!alonevertices.IsEmpty() && (alonevertices.Extent() != 2))
 524       return Standard_False;
 525
 526     Standard_Integer aFaceIndex = (fit == 1) ? theFaceIndex1 : theFaceIndex2;
 527     TopoDS_Shape aFace          = theDS->Shape(aFaceIndex);
 528     TopAbs_Orientation aFaceOri = aFace.Orientation();
 529     aFace.Orientation(TopAbs_FORWARD);
 530
 531     TopExp_Explorer anExpE(aFace, TopAbs_EDGE);
 532
 533     if(bHasNewEdge) {
 534       aNewEdge.Orientation(TopAbs_FORWARD);
 535     }
 536
 537     TopTools_ListOfShape aOrderedList;
 538
 539     if(!alonevertices.IsEmpty()) {
 540       Standard_Integer anEIndex = (fit == 1) ? anIndex1 : anIndex2;
 541       Standard_Boolean bfound1 = Standard_False;
 542       Standard_Boolean bfound2 = Standard_False;
 543       Standard_Real aparam1 = 0., aparam2 = 0.;
 544
 545       BOPDS_ListOfPave aLP;
 546       theDS->Paves(anEIndex, aLP);
 547       BOPDS_ListIteratorOfListOfPave aIt;
 548       aIt.Initialize(aLP);
 549       for ( ; aIt.More(); aIt.Next()) {
 550         const BOPDS_Pave& aPave = aIt.Value();
 551         TopoDS_Shape aV = theDS->Shape(aPave.Index());
 552
 553         if(aV.IsSame(alonevertices.First())) {
 554           if(!bfound1) {
 555             aparam1 = aPave.Parameter();
 556             bfound1 = Standard_True;
 557           }
 558         }
 559
 560         if(aV.IsSame(alonevertices.Last())) {
 561           if(!bfound2) {
 562             aparam2 = aPave.Parameter();
 563             bfound2 = Standard_True;
 564           }
 565         }
 566       }
 567
 568       if(bfound1 && bfound2) {
 569         TopoDS_Edge aNewBoundE;
 570
 571         if(fit == 1) {
 572           aNewBoundE = TopoDS::Edge(aE1.EmptyCopied());
 573         }
 574         else {
 575           aNewBoundE = TopoDS::Edge(aE2.EmptyCopied());
 576         }
 577         TopoDS_Vertex aV1, aV2;
 578
 579         if(aparam1 < aparam2) {
 580           aV1 = TopoDS::Vertex(alonevertices.First());
 581           aV2 = TopoDS::Vertex(alonevertices.Last());
 582         }
 583         else {
 584           aV1 = TopoDS::Vertex(alonevertices.Last());
 585           aV2 = TopoDS::Vertex(alonevertices.First());
 586           Standard_Real tmp = aparam1;
 587           aparam1 = aparam2;
 588           aparam2 = tmp;
 589         }
 590         aV1.Orientation(TopAbs_FORWARD);
 591         aV2.Orientation(TopAbs_REVERSED);
 592         aBB.Add(aNewBoundE, aV1);
 593         aBB.Add(aNewBoundE, aV2);
 594         aBB.Range(aNewBoundE, aparam1, aparam2);
 595         aNewBoundE.Orientation(TopAbs_FORWARD);
 596
 597         aOrderedList.Append(aNewBoundE);
 598
 599         if(bHasNewEdge) {
 600           TopExp_Explorer anExpV(aNewEdge, TopAbs_VERTEX);
 601           Standard_Boolean bfoundv = Standard_False;
 602
 603           for(; !bfoundv && anExpV.More(); anExpV.Next()) {
 604             if(aV2.IsSame(anExpV.Current()))
 605               bfoundv = Standard_True;
 606           }
 607
 608           if(bfoundv)
 609             aOrderedList.Append(aNewEdge);
 610           else
 611             aOrderedList.Prepend(aNewEdge);
 612         }
 613       }
 614       else {
 615         return Standard_False;
 616       }
 617     }
 618     else {
 619       if(bHasNewEdge) {
 620         aOrderedList.Append(aNewEdge);
 621       }
 622     }
 623
 624     if(!aOrderedList.IsEmpty()) {
 625       TopoDS_Wire aW;
 626       aBB.MakeWire(aW);
 627       TopTools_ListIteratorOfListOfShape anItE(aOrderedList);
 628
 629       for(; anItE.More(); anItE.Next()) {
 630         aBB.Add(aW, anItE.Value());
 631       }
 632       if(fit == 1)
 633         aSubstitutor->Replace(aE1.Oriented(TopAbs_FORWARD), aW);
 634       else
 635         aSubstitutor->Replace(aE2.Oriented(TopAbs_FORWARD), aW);
 636     }
 637
 638     aSubstitutor->Apply(aFace);
 639     TopoDS_Shape aNewFace = aSubstitutor->Value(aFace);
 640     aNewFace.Orientation(aFaceOri);
 641     TopTools_ListOfShape atmpList;
 642     atmpList.Append(aNewFace);
 643     theHistMap.Bind(aFace, atmpList);
 644
 645     anExpE.Init(aFace, TopAbs_EDGE);
 646
 647     for(; anExpE.More(); anExpE.Next()) {
 648       TopoDS_Shape aNewValue = aSubstitutor->Value(anExpE.Current());
 649
 650       if(aNewValue.IsNull() || aNewValue.IsSame(anExpE.Current()))
 651         continue;
 652
 653       if(theHistMap.IsBound(anExpE.Current()))
 654         continue;
 655       TopTools_ListOfShape aListOfNewEdge;
 656       TopExp_Explorer anExpE2(aNewValue, TopAbs_EDGE);
 657
 658       for(; anExpE2.More(); anExpE2.Next()) {
 659         aListOfNewEdge.Append(anExpE2.Current());
 660       }
 661       theHistMap.Bind(anExpE.Current(), aListOfNewEdge);
 662     }
 663   }
 664
 665   return Standard_True;
 666 }
 667
 668 // ----------------------------------------------------------------------------------------------------
 669 // static function: MakeFacesSec
 670 // purpose:
 671 // ----------------------------------------------------------------------------------------------------
 672 Standard_Boolean MakeFacesSec(const Standard_Integer                     theIndex,
 673                               const Handle(TopTools_HArray2OfShape)&     theUEdges,
 674                               const Handle(TopTools_HArray2OfShape)&     theBounds,
 675                               const BOPDS_PDS&                           theDS,
 676                               const Standard_Integer                     theFaceIndex1,
 677                               const Standard_Integer                     theFaceIndex2,
 678                               const Standard_Integer                     theSSInterfIndex,
 679                               const gp_Ax2&                              AxeOfBisPlane,
 680                               TopTools_DataMapOfShapeListOfShape&        theHistMap)
 681 {
 682   const BOPDS_VectorOfInterfFF& aFFs = theDS->InterfFF();
 683   const BOPDS_InterfFF& aFFi = aFFs(theSSInterfIndex);
 684   const BOPDS_VectorOfCurve& aBCurves = aFFi.Curves();
 685
 686   TopoDS_Compound aSecEdges;
 687   TopoDS_Face aSecPlane;
 688
 689   if(!FilterSectionEdges(aBCurves, aSecPlane, theDS, aSecEdges))
 690     return Standard_False;
 691
 692   TopoDS_Shape SecWire;
 693   gp_Pln SecPlane;
 694   Standard_Boolean IsSingular;
 695   Standard_Boolean WireFound = ChooseSection( aSecEdges, AxeOfBisPlane, SecWire, SecPlane, IsSingular );
 696
 697   if(WireFound) {
 698     //aSecEdges = SecWire;
 699     TopoDS_Compound aComp;
 700     BRep_Builder BB;
 701     BB.MakeCompound(aComp);
 702     TopExp_Explorer explo( SecWire, TopAbs_EDGE );
 703
 704     for (; explo.More(); explo.Next())
 705       BB.Add( aComp, explo.Current() );
 706     aSecEdges = aComp;
 707   }
 708
 709   TopTools_ListOfShape aCommonVertices;
 710 //  Standard_Boolean acommonflag = 0; // 0 - no, 1 - first pair, 2 - second pair, 3 - both
 711   Standard_Integer fit = 0; //, ueit = 0, eindex = 0, i = 0;
 712   Handle(BRepTools_ReShape) aSubstitutor = new BRepTools_ReShape();
 713
 714   for(fit = 0; fit < 2; fit++) {
 715     Standard_Integer aFaceIndex = (fit == 0) ? theFaceIndex1 : theFaceIndex2;
 716     TopoDS_Face aFace = TopoDS::Face(theDS->Shape(aFaceIndex));
 717     TopAbs_Orientation aFaceOri = aFace.Orientation();
 718     TopoDS_Face aFaceF = aFace;
 719     aFaceF.Orientation(TopAbs_FORWARD);
 720     TopoDS_Edge aBoundEdge = TopoDS::Edge(theBounds->Value(theIndex, theBounds->LowerCol() +fit));
 721     Standard_Integer aBoundEdgeIndex = theDS->Index(aBoundEdge);
 722     TopoDS_Edge aUE1;
 723     TopoDS_Edge aUE2;
 724
 725     if(!GetUEdges(theIndex, fit, theUEdges, aBoundEdge, aFaceF, aUE1, aUE2))
 726       return Standard_False;
 727
 728     TopoDS_Edge aUE1old = aUE1;
 729     TopoDS_Edge aUE2old = aUE2;
 730
 731     if(theHistMap.IsBound(aUE1)) {
 732       const TopTools_ListOfShape& lst = theHistMap.Find(aUE1);
 733
 734       if(!lst.IsEmpty()) {
 735         const TopoDS_Shape& anEdge = lst.First().Oriented(aUE1.Orientation());
 736
 737         if(!aUE1.IsSame(anEdge))
 738           aSubstitutor->Replace(aUE1.Oriented(TopAbs_FORWARD), anEdge.Oriented(TopAbs_FORWARD));
 739         aUE1 = TopoDS::Edge(anEdge);
 740       }
 741     }
 742
 743     if(theHistMap.IsBound(aUE2)) {
 744       const TopTools_ListOfShape& lst = theHistMap.Find(aUE2);
 745
 746       if(!lst.IsEmpty()) {
 747         const TopoDS_Shape& anEdge = lst.First().Oriented(aUE2.Orientation());
 748
 749         if(!aUE2.IsSame(anEdge))
 750           aSubstitutor->Replace(aUE2.Oriented(TopAbs_FORWARD), anEdge.Oriented(TopAbs_FORWARD));
 751         aUE2 = TopoDS::Edge(anEdge);
 752       }
 753     }
 754     TopoDS_Vertex aPrevVertex, aNextVertex;
 755     TopoDS_Compound aCompOfSecEdges = aSecEdges;
 756     TopTools_ListOfShape aListOfWireEdges;
 757     BRep_Builder aBB;
 758     BOPDS_Pave aPave1;
 759     Standard_Boolean isPave1OnUEdge = Standard_True;
 760
 761     if(FindFromUEdge(aUE1old, aUE2old, aUE1, aUE2, aFace, aSecEdges, fit, aBoundEdge, aBoundEdgeIndex,
 762                      theDS, theHistMap, aCompOfSecEdges, aListOfWireEdges, aPave1, isPave1OnUEdge)) {
 763       TopTools_ListOfShape aSecondListOfEdges;
 764       Standard_Boolean bisSectionFound = Standard_False;
 765
 766       if(!FindFromVEdge(aPave1, isPave1OnUEdge, aUE1old, aUE2old, aFace, aCompOfSecEdges, fit, aBoundEdge,
 767                         aBoundEdgeIndex, theDS, theHistMap, aSecondListOfEdges, bisSectionFound)) {
 768         return Standard_False;
 769       }
 770
 771       if(!bisSectionFound && aListOfWireEdges.IsEmpty()) {
 772         return Standard_False;
 773       }
 774       aListOfWireEdges.Append(aSecondListOfEdges);
 775     }
 776     else {
 777       return Standard_False;
 778     }
 779
 780     if(!aListOfWireEdges.IsEmpty()) {
 781       TopoDS_Wire aW;
 782       aBB.MakeWire(aW);
 783       TopTools_ListIteratorOfListOfShape aEIt(aListOfWireEdges);
 784
 785       for(; aEIt.More(); aEIt.Next()) {
 786         if(!aBoundEdge.IsSame(aEIt.Value()))
 787           aBB.Add(aW, aEIt.Value());
 788       }
 789       aSubstitutor->Replace(aBoundEdge.Oriented(TopAbs_FORWARD), aW);
 790     }
 791
 792     aSubstitutor->Apply(aFace);
 793     TopoDS_Shape aNewFace = aSubstitutor->Value(aFace);
 794     aNewFace.Orientation(aFaceOri);
 795     TopTools_ListOfShape atmpList;
 796     atmpList.Append(aNewFace);
 797     theHistMap.Bind(aFace, atmpList);
 798
 799     TopExp_Explorer anExpE(aFace, TopAbs_EDGE);
 800
 801     for(; anExpE.More(); anExpE.Next()) {
 802       TopoDS_Shape aNewValue = aSubstitutor->Value(anExpE.Current());
 803
 804       if(aNewValue.IsNull() || aNewValue.IsSame(anExpE.Current()))
 805         continue;
 806
 807       if(theHistMap.IsBound(anExpE.Current()))
 808         continue;
 809       TopTools_ListOfShape aListOfNewEdge;
 810       TopExp_Explorer anExpE2(aNewValue, TopAbs_EDGE);
 811
 812       for(; anExpE2.More(); anExpE2.Next()) {
 813         aListOfNewEdge.Append(anExpE2.Current());
 814       }
 815       theHistMap.Bind(anExpE.Current(), aListOfNewEdge);
 816     }
 817   }
 818   return Standard_True;
 819 }
 820
 821
 822 // ------------------------------------------------------------------------------------------
 823 // static function: SplitUEdges
 824 // purpose:
 825 // ------------------------------------------------------------------------------------------
 826 Standard_Boolean SplitUEdges(const Handle(TopTools_HArray2OfShape)&     theUEdges,
 827                              const BOPDS_PDS&                           theDS,
 828                              TopTools_DataMapOfShapeListOfShape&        theHistMap) {
 829
 830   const BOPDS_VectorOfInterfVV& aVVs = theDS->InterfVV();
 831
 832   BRep_Builder aBB;
 833   Standard_Integer ueit = 0, upRow, lowCol, upCol;
 834   TopTools_Array2OfShape aNewVertices(1,2,1,2);
 835   //
 836   upRow = theUEdges->UpperRow();
 837   lowCol = theUEdges->LowerCol();
 838   upCol = theUEdges->UpperCol();
 839   //
 840   for(ueit = theUEdges->LowerRow(); ueit <= upRow; ueit++) {
 841     const TopoDS_Shape& aE1 = theUEdges->Value(ueit, lowCol);
 842     const TopoDS_Shape& aE2 = theUEdges->Value(ueit, upCol);
 843
 844     if(theHistMap.IsBound(aE1) || theHistMap.IsBound(aE2))
 845       continue;
 846
 847     Standard_Integer anEIndex1 = theDS->Index(aE1);
 848     Standard_Integer anEIndex2 = theDS->Index(aE2);
 849
 850     TopoDS_Vertex aCommonVertex;
 851     Standard_Real apar1 = 0., apar2 = 0.;
 852     Standard_Boolean bvertexfound =
 853       FindCommonVertex(theDS, anEIndex1, anEIndex2, aCommonVertex, apar1, apar2);
 854     //
 855     if(!bvertexfound) {
 856       TopoDS_Vertex V1 = TopExp::LastVertex(TopoDS::Edge(aE1));
 857       TopoDS_Vertex V2 = TopExp::FirstVertex(TopoDS::Edge(aE2));
 858       Standard_Integer vindex1 = theDS->Index(V1);
 859       Standard_Integer vindex2 = theDS->Index(V2);
 860       Standard_Integer vvit = 0;
 861       Standard_Integer aNbVVs = aVVs.Extent();
 862
 863       for(vvit = 0; !bvertexfound && (vvit < aNbVVs); vvit++) {
 864         //const BOPTools_VVInterference& aVV = aVVs(vvit);
 865         const BOPDS_InterfVV& aVV = aVVs(vvit);
 866
 867         if(((vindex1 == aVV.Index1()) && (vindex2 == aVV.Index2())) ||
 868            ((vindex1 == aVV.Index2()) && (vindex2 == aVV.Index1()))) {
 869
 870           if(!aVV.HasIndexNew()) {
 871             continue;
 872           }
 873           aCommonVertex = TopoDS::Vertex(theDS->Shape(aVV.IndexNew()));
 874           bvertexfound = Standard_True;
 875           apar1 = BRep_Tool::Parameter(V1, TopoDS::Edge(aE1));
 876           apar2 = BRep_Tool::Parameter(V2, TopoDS::Edge(aE2));
 877         }
 878       }
 879     }
 880
 881     if(bvertexfound) {
 882       TopoDS_Vertex aV1, aV2;
 883       Standard_Real f = 0., l = 0.;
 884       //
 885       TopoDS_Edge aNewE1 = TopoDS::Edge(aE1.EmptyCopied());
 886       TopExp::Vertices(TopoDS::Edge(aE1), aV1, aV2);
 887       aNewE1.Orientation(TopAbs_FORWARD);
 888       aV1.Orientation(TopAbs_FORWARD);
 889       aBB.Add(aNewE1, aV1);
 890       aCommonVertex.Orientation(TopAbs_REVERSED);
 891       aBB.Add(aNewE1, aCommonVertex);
 892       BRep_Tool::Range(TopoDS::Edge(aE1), f, l);
 893       aBB.Range(aNewE1, f, apar1);
 894
 895       //
 896       TopoDS_Edge aNewE2 = TopoDS::Edge(aE2.EmptyCopied());
 897       TopExp::Vertices(TopoDS::Edge(aE2), aV1, aV2);
 898       aNewE2.Orientation(TopAbs_FORWARD);
 899       aCommonVertex.Orientation(TopAbs_FORWARD);
 900       aBB.Add(aNewE2, aCommonVertex);
 901       aBB.Add(aNewE2, aV2);
 902       BRep_Tool::Range(TopoDS::Edge(aE2), f, l);
 903       aBB.Range(aNewE2, apar2, l);
 904
 905       TopTools_ListOfShape lst;
 906       lst.Append(aNewE1);
 907       theHistMap.Bind(aE1, lst);
 908       lst.Clear();
 909       lst.Append(aNewE2);
 910       theHistMap.Bind(aE2, lst);
 911     }
 912   }
 913   return Standard_True;
 914 }
 915
 916 // ------------------------------------------------------------------------------------------
 917 // static function: FindFreeVertices
 918 // purpose:
 919 // ------------------------------------------------------------------------------------------
 920 void FindFreeVertices(const TopoDS_Shape&         theShape,
 921                       const TopTools_MapOfShape&  theVerticesToAvoid,
 922                       TopTools_ListOfShape&       theListOfVertex) {
 923
 924   theListOfVertex.Clear();
 925   TopTools_IndexedDataMapOfShapeListOfShape aMap;
 926   TopExp::MapShapesAndAncestors(theShape, TopAbs_VERTEX, TopAbs_EDGE, aMap);
 927   Standard_Integer i = 0;
 928
 929   for(i = 1; i <= aMap.Extent(); i++) {
 930     const TopoDS_Shape& aKey = aMap.FindKey(i);
 931
 932     if(theVerticesToAvoid.Contains(aKey))
 933       continue;
 934     const TopTools_ListOfShape& aList = aMap.FindFromIndex(i);
 935
 936     if(aList.Extent() < 2) {
 937       theListOfVertex.Append(aKey);
 938     }
 939   }
 940 }
 941
 942 // ------------------------------------------------------------------------------------------
 943 // static function: FindCommonVertex
 944 // purpose:
 945 // ------------------------------------------------------------------------------------------
 946 Standard_Boolean FindCommonVertex(const BOPDS_PDS&         theDS,
 947                                   const Standard_Integer   theEIndex1,
 948                                   const Standard_Integer   theEIndex2,
 949                                   TopoDS_Vertex&           theCommonVertex,
 950                                   Standard_Real&           theParamOnE1,
 951                                   Standard_Real&           theParamOnE2) {
 952
 953   const BOPDS_VectorOfInterfEE& aEEs = theDS->InterfEE();
 954
 955   Standard_Boolean bvertexfound = Standard_False;
 956   TopoDS_Vertex aCommonVertex;
 957   Standard_Integer eeit = 0;
 958
 959   Standard_Integer aNbEEs;
 960   aNbEEs = aEEs.Extent();
 961   for(eeit = 0; eeit < aNbEEs; ++eeit) {
 962     const BOPDS_InterfEE& aEE = aEEs(eeit);
 963
 964     if((theEIndex1 == aEE.Index1() && theEIndex2 == aEE.Index2()) ||
 965        (theEIndex1 == aEE.Index2() && theEIndex2 == aEE.Index1())) {
 966
 967       if(!aEE.HasIndexNew())
 968         continue;
 969
 970       IntTools_CommonPrt aCP = aEE.CommonPart();
 971       if(aCP.Type() == TopAbs_VERTEX) {
 972         theCommonVertex = *(TopoDS_Vertex*)&theDS->Shape(aEE.IndexNew());
 973         if (theEIndex1 == aEE.Index1()) {
 974           BOPInt_Tools::VertexParameters(aCP, theParamOnE1, theParamOnE2);
 975         } else {
 976           BOPInt_Tools::VertexParameters(aCP, theParamOnE2, theParamOnE1);
 977         }
 978         //
 979         bvertexfound = Standard_True;
 980         break;
 981       }
 982     }
 983   }
 984   return bvertexfound;
 985 }
 986
 987 // ----------------------------------------------------------------------------------------------------
 988 // static function: GetUEdges
 989 // purpose:
 990 // ----------------------------------------------------------------------------------------------------
 991 Standard_Boolean GetUEdges(const Standard_Integer                     theIndex,
 992                            const Standard_Integer                     theRank,
 993                            const Handle(TopTools_HArray2OfShape)&     theUEdges,
 994                            const TopoDS_Edge&                         theBoundEdge,
 995                            const TopoDS_Face&                         theFace,
 996                            TopoDS_Edge&                               theFirstUEdge,
 997                            TopoDS_Edge&                               theSecondUEdge) {
 998   const TopoDS_Shape& aUE1 = theUEdges->Value(theIndex, theUEdges->LowerCol() + theRank);
 999   const TopoDS_Shape& aUE2 = theUEdges->Value(theIndex + 1, theUEdges->LowerCol() + theRank);
1000
1001   TopoDS_Face aFace = theFace;
1002   aFace.Orientation(TopAbs_FORWARD);
1003   TopoDS_Edge E1, E2;
1004   TopExp_Explorer anExp(aFace, TopAbs_EDGE);
1005
1006   for(; anExp.More(); anExp.Next()) {
1007     if(E1.IsNull() && aUE1.IsSame(anExp.Current())) {
1008       E1 = TopoDS::Edge(anExp.Current());
1009     }
1010     else if(E2.IsNull() && aUE2.IsSame(anExp.Current())) {
1011       E2 = TopoDS::Edge(anExp.Current());
1012     }
1013   }
1014
1015   if(E1.IsNull() || E2.IsNull())
1016     return Standard_False;
1017
1018   Standard_Real f, l;
1019   Handle(Geom2d_Curve) C1 = BRep_Tool::CurveOnSurface(E1, aFace, f, l);
1020
1021   if(C1.IsNull())
1022      return Standard_False;
1023   gp_Pnt2d PU1 = (theRank == 0) ? C1->Value(l) : C1->Value(f);
1024   Handle(Geom2d_Curve) C2 = BRep_Tool::CurveOnSurface(theBoundEdge, aFace, f, l);
1025
1026   if(C2.IsNull())
1027     return Standard_False;
1028   BRep_Tool::Range(theBoundEdge, f, l);
1029   gp_Pnt2d pf = C2->Value(f);
1030   TopoDS_Vertex aV = (theRank == 0) ? TopExp::LastVertex(E1) : TopExp::FirstVertex(E1);
1031   Standard_Real aTolerance = BRep_Tool::Tolerance(aV);
1032   BRepAdaptor_Surface aBAS(aFace, Standard_False);
1033
1034   if(pf.Distance(PU1) > aBAS.UResolution(aTolerance)) {
1035     TopoDS_Edge atmpE = E1;
1036     E1 = E2;
1037     E2 = atmpE;
1038   }
1039   theFirstUEdge = E1;
1040   theSecondUEdge = E2;
1041   return Standard_True;
1042 }
1043
1044 // ----------------------------------------------------------------------------------------------------
1045 // static function: FillGap
1046 // purpose:
1047 // ----------------------------------------------------------------------------------------------------
1048 Standard_Boolean FillGap(const TopoDS_Vertex&   theFirstVertex,
1049                          const TopoDS_Vertex&   theLastVertex,
1050                          const gp_Pnt2d&        theFirstPoint,
1051                          const gp_Pnt2d&        theLastPoint,
1052                          const TopoDS_Face&     theFace,
1053                          const TopoDS_Compound& theSectionEdges,
1054                          TopTools_ListOfShape&  theOrderedList) {
1055
1056   TopTools_IndexedDataMapOfShapeListOfShape aMap;
1057   TopExp::MapShapesAndAncestors(theSectionEdges, TopAbs_VERTEX, TopAbs_EDGE, aMap);
1058
1059   if(aMap.IsEmpty()) {
1060     return Standard_False;
1061   }
1062
1063   if(!aMap.Contains(theFirstVertex) ||
1064      !aMap.Contains(theLastVertex)) {
1065     return Standard_False;
1066   }
1067   TopTools_ListOfShape aListOfEdge;
1068 //  Standard_Integer i = 0;
1069 //  TopoDS_Vertex aCurVertex = theFirstVertex;
1070   TopTools_MapOfShape aMapToAvoid;
1071
1072   if(FindNextEdge(theFirstVertex, theLastVertex, aMap, aMapToAvoid, aListOfEdge)) {
1073     if(!aListOfEdge.IsEmpty()) {
1074       return CheckAndOrientEdges(aListOfEdge, theFirstPoint, theLastPoint, theFace, theOrderedList);
1075     }
1076   }
1077   return Standard_False;
1078 }
1079
1080 // ----------------------------------------------------------------------------------------------------
1081 // static function: FindNextEdge
1082 // purpose:
1083 // ----------------------------------------------------------------------------------------------------
1084 Standard_Boolean FindNextEdge(const TopoDS_Vertex&   theFirstVertex,
1085                               const TopoDS_Vertex&   theLastVertex,
1086                               const TopTools_IndexedDataMapOfShapeListOfShape& theMapVE,
1087                               const TopTools_MapOfShape& theMapToAvoid,
1088                               TopTools_ListOfShape&  theOrderedList) {
1089   TopoDS_Vertex aCurVertex = theFirstVertex;
1090   TopTools_MapOfShape aMapToAvoid;
1091   aMapToAvoid = theMapToAvoid;
1092   TopTools_ListOfShape aListOfEdge;
1093   Standard_Integer i = 0;
1094
1095   for(i = 1; i <= theMapVE.Extent(); i++) {
1096     if(!theMapVE.Contains(aCurVertex))
1097       break;
1098     const TopTools_ListOfShape& lste = theMapVE.FindFromKey(aCurVertex);
1099     Standard_Boolean befound = Standard_False;
1100
1101     TopTools_ListIteratorOfListOfShape anIt(lste);
1102
1103     for(; anIt.More(); anIt.Next()) {
1104       TopoDS_Shape anEdge = anIt.Value();
1105       TopoDS_Vertex aSaveCurVertex = aCurVertex;
1106
1107       if(!aMapToAvoid.Contains(anEdge)) {
1108         TopoDS_Vertex V1, V2;
1109         TopExp::Vertices(TopoDS::Edge(anEdge), V1, V2);
1110
1111         if(!aCurVertex.IsSame(V1)) {
1112           aCurVertex = V1;
1113         }
1114         else if(!aCurVertex.IsSame(V2)) {
1115           aCurVertex = V2;
1116         }
1117         aMapToAvoid.Add(anEdge);
1118         befound = Standard_True;
1119         aListOfEdge.Append(anEdge);
1120
1121         if(!aCurVertex.IsSame(theLastVertex)) {
1122           TopTools_ListOfShape aListtmp;
1123
1124           if(!FindNextEdge(aCurVertex, theLastVertex, theMapVE, aMapToAvoid, aListtmp)) {
1125             aListOfEdge.Clear();
1126             aCurVertex = aSaveCurVertex;
1127             continue;
1128           }
1129           else {
1130             aListOfEdge.Append(aListtmp);
1131             theOrderedList.Append(aListOfEdge);
1132             return Standard_True;
1133           }
1134         }
1135         break;
1136       }
1137     }
1138
1139     if(aCurVertex.IsSame(theLastVertex))
1140       break;
1141
1142     if(!befound) {
1143       return Standard_False;
1144     }
1145   }
1146
1147   if(aCurVertex.IsSame(theLastVertex)) {
1148     theOrderedList.Append(aListOfEdge);
1149     return Standard_True;
1150   }
1151   return Standard_False;
1152 }
1153
1154 // ----------------------------------------------------------------------------------------------------
1155 // static function: CheckAndOrientEdges
1156 // purpose:
1157 // ----------------------------------------------------------------------------------------------------
1158 Standard_Boolean CheckAndOrientEdges(const TopTools_ListOfShape&  theOrderedList,
1159                                      const gp_Pnt2d&              theFirstPoint,
1160                                      const gp_Pnt2d&              theLastPoint,
1161                                      const TopoDS_Face&           theFace,
1162                                      TopTools_ListOfShape&        theOrientedList) {
1163   TopTools_ListIteratorOfListOfShape anIt(theOrderedList);
1164
1165   if(!anIt.More())
1166     return Standard_True;
1167
1168   Standard_Real f, l;
1169   TopoDS_Edge aEPrev = TopoDS::Edge(anIt.Value());
1170   anIt.Next();
1171
1172   Handle(Geom2d_Curve) aCurve = BRep_Tool::CurveOnSurface(aEPrev, theFace, f, l);
1173   TopoDS_Vertex Vf, Vl;
1174   TopExp::Vertices(aEPrev, Vf, Vl);
1175   BRepAdaptor_Surface aBAS(theFace, Standard_False);
1176
1177   Standard_Real aTolerance1 = (Vf.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(Vf);
1178   Standard_Real aTolerance2 = (Vl.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(Vl);
1179   Standard_Real utol = aBAS.UResolution(aTolerance1);
1180   Standard_Real vtol = aBAS.VResolution(aTolerance1);
1181   aTolerance1 = (utol > vtol) ? utol : vtol;
1182   utol = aBAS.UResolution(aTolerance2);
1183   vtol = aBAS.VResolution(aTolerance2);
1184   aTolerance2 = (utol > vtol) ? utol : vtol;
1185
1186   gp_Pnt2d ap = aCurve->Value(f);
1187   Standard_Boolean bFirstFound = Standard_False;
1188   Standard_Boolean bLastFound = Standard_False;
1189   Standard_Boolean bforward = Standard_True;
1190
1191   if(ap.Distance(theFirstPoint) < aTolerance1) {
1192     bforward = Standard_True;
1193     if(theOrientedList.IsEmpty())
1194       theOrientedList.Append(aEPrev.Oriented(TopAbs_FORWARD));
1195     bFirstFound = Standard_True;
1196   }
1197   else if(ap.Distance(theLastPoint) < aTolerance1) {
1198     bforward = Standard_False;
1199     if(theOrientedList.IsEmpty())
1200       theOrientedList.Append(aEPrev.Oriented(TopAbs_REVERSED));
1201     bLastFound = Standard_True;
1202   }
1203   ap = aCurve->Value(l);
1204
1205   if(ap.Distance(theLastPoint) < aTolerance2) {
1206     bforward = Standard_True;
1207
1208     if(theOrientedList.IsEmpty())
1209       theOrientedList.Append(aEPrev.Oriented(TopAbs_FORWARD));
1210     bLastFound = Standard_True;
1211   }
1212   else if(ap.Distance(theFirstPoint) < aTolerance2) {
1213     bforward = Standard_False;
1214
1215     if(theOrientedList.IsEmpty())
1216       theOrientedList.Append(aEPrev.Oriented(TopAbs_REVERSED));
1217     bFirstFound = Standard_True;
1218   }
1219
1220   for(; anIt.More(); anIt.Next()) {
1221     const TopoDS_Edge& aE = TopoDS::Edge(anIt.Value());
1222     TopoDS_Vertex aV11, aV12;
1223     TopExp::Vertices(aEPrev, aV11, aV12);
1224     TopoDS_Vertex aV21, aV22;
1225     TopExp::Vertices(aE, aV21, aV22);
1226     TopAbs_Orientation anOri = TopAbs_FORWARD;
1227
1228     if(aV12.IsSame(aV21) || aV11.IsSame(aV22)) {
1229       anOri = (bforward) ? TopAbs_FORWARD : TopAbs_REVERSED;
1230     }
1231     else {
1232       anOri = (bforward) ? TopAbs_REVERSED : TopAbs_FORWARD;
1233     }
1234     theOrientedList.Append(aE.Oriented(anOri));
1235     aEPrev = aE;
1236     aTolerance1 = (aV21.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(aV21);
1237     aTolerance2 = (aV22.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(aV22);
1238     utol = aBAS.UResolution(aTolerance1);
1239     vtol = aBAS.VResolution(aTolerance1);
1240     aTolerance1 = (utol > vtol) ? utol : vtol;
1241     utol = aBAS.UResolution(aTolerance2);
1242     vtol = aBAS.VResolution(aTolerance2);
1243     aTolerance2 = (utol > vtol) ? utol : vtol;
1244     aCurve = BRep_Tool::CurveOnSurface(aE, theFace, f, l);
1245     ap = aCurve->Value(f);
1246
1247     if(ap.Distance(theFirstPoint) < aTolerance1) {
1248       bFirstFound = Standard_True;
1249     }
1250     else if(ap.Distance(theLastPoint) < aTolerance1) {
1251       bLastFound = Standard_True;
1252     }
1253     ap = aCurve->Value(l);
1254
1255     if(ap.Distance(theFirstPoint) < aTolerance2) {
1256       bFirstFound = Standard_True;
1257     }
1258     else if(ap.Distance(theLastPoint) < aTolerance2) {
1259       bLastFound = Standard_True;
1260     }
1261   }
1262
1263   if(!bFirstFound || !bLastFound)
1264     return Standard_False;
1265   return Standard_True;
1266 }
1267
1268 // ----------------------------------------------------------------------------------------------------
1269 // static function: FindVertex
1270 // purpose:
1271 // ----------------------------------------------------------------------------------------------------
1272 Standard_Boolean FindVertex(const TopoDS_Edge&                        theEdge,
1273                             const Standard_Integer                    theRank,
1274                             const BOPDS_PDS&                          theDS,
1275                             const TopTools_DataMapOfShapeListOfShape& theHistMap,
1276                             TopoDS_Vertex&                            theVertex,
1277                             BOPDS_Pave&                               thePave) {
1278
1279   if(!theHistMap.IsBound(theEdge))
1280     return Standard_False;
1281
1282   const TopTools_ListOfShape& lst = theHistMap.Find(theEdge);
1283
1284   if(lst.IsEmpty())
1285     return Standard_False;
1286
1287   TopoDS_Edge aNewEdge = TopoDS::Edge(lst.First());
1288   Standard_Real f, l;
1289   BRep_Tool::Range(aNewEdge, f, l);
1290
1291   if(theRank == 0) {
1292     thePave.SetParameter(l);
1293     theVertex = TopExp::LastVertex(aNewEdge);
1294   }
1295   else {
1296     thePave.SetParameter(f);
1297     theVertex = TopExp::FirstVertex(aNewEdge);
1298   }
1299   Standard_Integer anIndex = theDS->Index(theVertex);
1300   if (anIndex == -1) {
1301     Standard_Integer i, i1, i2;
1302     i1=theDS->NbSourceShapes();
1303     i2=theDS->NbShapes();
1304     for (i=i1; i<i2; ++i) {
1305       const TopoDS_Shape& aSx=theDS->Shape(i);
1306       if(aSx.IsSame(theVertex)) {
1307         anIndex = i;
1308         break;
1309       }
1310     }
1311   }
1312
1313   thePave.SetIndex(anIndex);
1314
1315   return Standard_True;
1316 }
1317
1318 // ----------------------------------------------------------------------------------------------------
1319 // static function: FindNextVertex
1320 // purpose:
1321 // ----------------------------------------------------------------------------------------------------
1322 Standard_Boolean FindNextVertex(const Standard_Integer                    theEdgeIndex,
1323                                 const BOPDS_Pave&                         thePrevPave,
1324                                 const BOPDS_PDS&                          theDS,
1325                                 TopoDS_Vertex&                            theNextVertex,
1326                                 BOPDS_Pave&                               thePave) {
1327
1328   Standard_Boolean bTakePave, bFound;
1329   BOPDS_Pave aTmpPave;
1330   BOPDS_ListIteratorOfListOfPave aItP;
1331   //
1332   BOPDS_Pave anullpave;
1333   bFound = Standard_False;
1334   bTakePave = thePrevPave.IsEqual(anullpave);
1335
1336   BOPDS_ListOfPave aLP;
1337   theDS->Paves(theEdgeIndex, aLP);
1338   aItP.Initialize(aLP);
1339   for (; aItP.More(); aItP.Next()) {
1340     aTmpPave = aItP.Value();
1341     //
1342     if (bTakePave) {
1343       if (theDS->IsNewShape(aTmpPave.Index())) {
1344         theNextVertex = *(TopoDS_Vertex*)&theDS->Shape(aTmpPave.Index());
1345         thePave = aTmpPave;
1346         bFound = Standard_True;
1347         break;
1348       }
1349     }
1350     //
1351     else if (aTmpPave.IsEqual(thePrevPave)) {
1352       bTakePave = Standard_True;
1353     }
1354   }
1355
1356   return bFound;
1357 }
1358
1359 // ----------------------------------------------------------------------------------------------------
1360 // static function: GetPave
1361 // purpose:
1362 // ----------------------------------------------------------------------------------------------------
1363 Standard_Boolean GetPave(const Standard_Integer    theEdgeIndex,
1364                          const Standard_Boolean    isFirst,
1365                          const BOPDS_PDS&          theDS,
1366                          BOPDS_Pave&               thePave) {
1367
1368   Handle(BOPDS_PaveBlock) aPB;
1369   BOPDS_ListOfPave aLP;
1370
1371   theDS->Paves(theEdgeIndex, aLP);
1372   if (!aLP.Extent()) {
1373     return Standard_False;
1374   }
1375   //
1376   if (isFirst) {
1377     thePave = aLP.First();
1378   }
1379   else {
1380     thePave = aLP.Last();
1381   }
1382
1383   return Standard_True;
1384 }
1385
1386 // ----------------------------------------------------------------------------------------------------
1387 // static function: FindFromUEdge
1388 // purpose:
1389 // ----------------------------------------------------------------------------------------------------
1390 Standard_Boolean FindFromUEdge(const TopoDS_Edge&                        theUE1Old,
1391                                const TopoDS_Edge&                        theUE2Old,
1392                                const TopoDS_Edge&                        theUE1New,
1393                                const TopoDS_Edge&                        theUE2New,
1394                                const TopoDS_Face&                        theFace,
1395                                const TopoDS_Compound&                    theSecEdges,
1396                                const Standard_Integer                    theRank,
1397                                const TopoDS_Edge&                        theBoundEdge,
1398                                const Standard_Integer                    theBoundEdgeIndex,
1399                                const BOPDS_PDS&                          theDS,
1400                                const TopTools_DataMapOfShapeListOfShape& theHistMap,
1401                                TopoDS_Compound&                          theSecEdgesNew,
1402                                TopTools_ListOfShape&                     theListOfWireEdges,
1403                                BOPDS_Pave&                               theFoundPave,
1404                                Standard_Boolean&                         isOnUEdge) {
1405   theFoundPave.SetIndex(0);
1406   theFoundPave.SetParameter(0.);
1407   isOnUEdge = Standard_True;
1408
1409   TopoDS_Face aFaceF = theFace;
1410   aFaceF.Orientation(TopAbs_FORWARD);
1411   TopoDS_Vertex aPrevVertex, aNextVertex;
1412   TopoDS_Compound aCompOfSecEdges = theSecEdges;
1413   TopTools_ListOfShape aListOfWireEdges;
1414 //  BRep_Builder aBB;
1415
1416   BOPDS_Pave aPave1, aPave2;
1417   Standard_Real f = 0., l = 0.;
1418   gp_Pnt2d p1, p2;
1419   TopoDS_Vertex aFirstV, aLastV;
1420   BOPDS_Pave atmpPave;
1421
1422   if(!FindVertex(theUE1Old, theRank, theDS, theHistMap, aPrevVertex, atmpPave)) {
1423     return Standard_True;
1424   }
1425
1426   if(aPrevVertex.IsNull()) {
1427     return Standard_False;
1428   }
1429
1430   aFirstV = aPrevVertex;
1431   Standard_Boolean bSecFound = Standard_False;
1432   Handle(Geom2d_Curve) aC1 = BRep_Tool::CurveOnSurface(theUE1New, aFaceF, f, l);
1433   p1 = (theRank == 0) ? aC1->Value(l) : aC1->Value(f);
1434   BOPDS_Pave afoundpave;
1435   BOPDS_ListOfPave aLP;
1436   theDS->Paves(theBoundEdgeIndex, aLP);
1437   Standard_Integer nbpave = aLP.Extent();
1438   Standard_Integer pit = 0;
1439
1440   while(FindNextVertex(theBoundEdgeIndex, aPave1, theDS, aNextVertex, aPave2) && (pit < nbpave)) {
1441     aLastV = aNextVertex;
1442     Handle(Geom2d_Curve) aC2 = BRep_Tool::CurveOnSurface(theBoundEdge, aFaceF, f, l);
1443     p2 = aC2->Value(aPave2.Parameter());
1444     TopTools_ListOfShape aOrderedList;
1445
1446     if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1447       // remove found edges...
1448       TopoDS_Compound aComp;
1449       RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1450       aCompOfSecEdges = aComp;
1451       aListOfWireEdges.Append(aOrderedList);
1452       afoundpave = aPave2;
1453       isOnUEdge = Standard_False;
1454       bSecFound = Standard_True;
1455       break;
1456     }
1457     aPrevVertex = aNextVertex;
1458     aPave1 = aPave2;
1459     pit++;
1460   }
1461
1462   if(!bSecFound && FindVertex(theUE2Old, theRank, theDS, theHistMap, aNextVertex, aPave2)) {
1463     aLastV = aNextVertex;
1464     Handle(Geom2d_Curve) aC2 = BRep_Tool::CurveOnSurface(theUE2New, aFaceF, f, l);
1465     p2 = aC2->Value(aPave2.Parameter());
1466     TopTools_ListOfShape aOrderedList;
1467
1468     if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1469       // remove found edges...
1470       TopoDS_Compound aComp;
1471
1472       RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1473       aCompOfSecEdges = aComp;
1474       aListOfWireEdges.Append(aOrderedList);
1475       afoundpave = aPave2;
1476       bSecFound = Standard_True;
1477       isOnUEdge = Standard_True;
1478     }
1479   }
1480
1481   if(bSecFound) {
1482     theFoundPave = afoundpave;
1483     theListOfWireEdges = aListOfWireEdges;
1484     theSecEdgesNew = aCompOfSecEdges;
1485   }
1486   return Standard_True;
1487 }
1488
1489
1490 // ----------------------------------------------------------------------------------------------------
1491 // static function: FindFromVEdge
1492 // purpose:
1493 // ----------------------------------------------------------------------------------------------------
1494 Standard_Boolean FindFromVEdge(const BOPDS_Pave&                         thePrevPave,
1495                                const Standard_Boolean&                   isOnUEdge,
1496                                const TopoDS_Edge&                        theUE1Old,
1497                                const TopoDS_Edge&                        theUE2Old,
1498                                const TopoDS_Face&                        theFace,
1499                                const TopoDS_Compound&                    theSecEdges,
1500                                const Standard_Integer                    theRank,
1501                                const TopoDS_Edge&                        theBoundEdge,
1502                                const Standard_Integer                    theBoundEdgeIndex,
1503                                const BOPDS_PDS&                          theDS,
1504                                const TopTools_DataMapOfShapeListOfShape& theHistMap,
1505                                TopTools_ListOfShape&                     theListOfWireEdges,
1506                                Standard_Boolean&                         isSectionFound) {
1507
1508   theListOfWireEdges.Clear();
1509   isSectionFound = Standard_False;
1510   //
1511   TopoDS_Face aFaceF = theFace;
1512   aFaceF.Orientation(TopAbs_FORWARD);
1513   TopoDS_Vertex aPrevVertex, aNextVertex;
1514   TopoDS_Compound aCompOfSecEdges = theSecEdges;
1515   TopTools_ListOfShape aListOfWireEdges;
1516 //  BRep_Builder aBB;
1517
1518   BOPDS_Pave aPave1, aPave2;
1519
1520   if(isOnUEdge) {
1521     TopoDS_Vertex atmpVertex;
1522     BOPDS_Pave aPaveOfE2;
1523
1524     if(FindVertex(theUE2Old, theRank, theDS, theHistMap, atmpVertex, aPaveOfE2)) {
1525       if(thePrevPave.IsEqual(aPaveOfE2))
1526         return Standard_True;
1527     }
1528   }
1529
1530   Standard_Real f = 0., l = 0.;
1531   gp_Pnt2d p1(0., 0.), p2(0., 0.);
1532   TopoDS_Vertex aFirstV, aLastV;
1533   Handle(Geom2d_Curve) aC1 = BRep_Tool::CurveOnSurface(theUE1Old, aFaceF, f, l);
1534   Handle(Geom2d_Curve) aC2 = BRep_Tool::CurveOnSurface(theBoundEdge, aFaceF, f, l);
1535   Standard_Boolean bSecFound = Standard_False;
1536
1537   aPave1 = thePrevPave;
1538
1539   if(isOnUEdge) {
1540     BOPDS_Pave atmpPave;
1541
1542     if(!GetPave(theBoundEdgeIndex, Standard_True, theDS, atmpPave)) {
1543       return Standard_False;
1544     }
1545     aPave1 = atmpPave;
1546   }
1547   p1 = aC2->Value(aPave1.Parameter());
1548   aPrevVertex = TopoDS::Vertex(theDS->Shape(aPave1.Index()));
1549
1550   BOPDS_ListOfPave aLP;
1551   theDS->Paves(theBoundEdgeIndex, aLP);
1552   Standard_Integer nbpave = aLP.Extent();
1553   Standard_Integer pit = 0;
1554   TopTools_Array1OfListOfShape anArrayOfListOfSec(1, nbpave);
1555
1556   // by pairs non continuously. begin
1557   Standard_Integer k = 0;
1558   BOPDS_Pave aFirstPave = aPave1;
1559   TopoDS_Vertex aFirstVertex = aPrevVertex;
1560   gp_Pnt2d apfirst = p1;
1561   BOPDS_ListOfPave aFirstPaves, aLastPaves;
1562   TColStd_ListOfInteger aListOfFlags;
1563   Standard_Integer apaircounter = 1;
1564
1565   for(k = 0; k < nbpave; k++) {
1566     aPave1 = aFirstPave;
1567     p1 = apfirst;
1568     aPrevVertex = aFirstVertex;
1569     Standard_Boolean bfound = Standard_False;
1570     pit = 0;
1571
1572     while(FindNextVertex(theBoundEdgeIndex, aPave1, theDS, aNextVertex, aPave2) && (pit < nbpave)) {
1573       aFirstV = aPrevVertex;
1574       aLastV = aNextVertex;
1575       p2 = aC2->Value(aPave2.Parameter());
1576
1577       TopTools_ListOfShape aOrderedList;
1578
1579       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1580         TopoDS_Compound aComp;
1581         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1582         aCompOfSecEdges = aComp;
1583
1584         anArrayOfListOfSec(apaircounter++).Append(aOrderedList);
1585         aFirstPaves.Append(aFirstPave);
1586         aLastPaves.Append(aPave2);
1587         aListOfFlags.Append(1);
1588         aFirstPave = aPave2;
1589         aFirstVertex = aNextVertex;
1590         apfirst = p2;
1591         aPrevVertex = aNextVertex;
1592         bSecFound = Standard_True;
1593         bfound = Standard_True;
1594       }
1595       aPave1 = aPave2;
1596       pit++;
1597     }
1598
1599     if(FindVertex(theUE2Old, theRank, theDS, theHistMap, aNextVertex, aPave2)) {
1600       aFirstV = aPrevVertex;
1601       aLastV = aNextVertex;
1602       Handle(Geom2d_Curve) aC3 = BRep_Tool::CurveOnSurface(theUE2Old, aFaceF, f, l);
1603       p2 = aC3->Value(aPave2.Parameter());
1604
1605       TopTools_ListOfShape aOrderedList;
1606
1607       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1608         TopoDS_Compound aComp;
1609         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1610         aCompOfSecEdges = aComp;
1611         anArrayOfListOfSec(apaircounter++).Append(aOrderedList);
1612         aFirstPaves.Append(aFirstPave);
1613         aLastPaves.Append(aPave2);
1614         aListOfFlags.Append(0);
1615         bSecFound = Standard_True;
1616         break;
1617       }
1618     }
1619
1620     if(!bfound) {
1621       if(!FindNextVertex(theBoundEdgeIndex, aFirstPave, theDS, aNextVertex, aPave2)) {
1622         break;
1623       }
1624       aFirstPave = aPave2;
1625       apfirst = aC2->Value(aPave2.Parameter());
1626       aFirstVertex = aNextVertex;
1627     }
1628   }
1629   // by pairs non continuously. end
1630
1631   // by pairs continuously. begin
1632   aPave1 = thePrevPave;
1633
1634   if(isOnUEdge) {
1635     BOPDS_Pave atmpPave;
1636
1637     if(!GetPave(theBoundEdgeIndex, Standard_True, theDS, atmpPave)) {
1638       return Standard_False;
1639     }
1640     aPave1 = atmpPave;
1641   }
1642   p1 = aC2->Value(aPave1.Parameter());
1643   aPrevVertex = TopoDS::Vertex(theDS->Shape(aPave1.Index()));
1644
1645   pit = 0;
1646
1647   while(FindNextVertex(theBoundEdgeIndex, aPave1, theDS, aNextVertex, aPave2) && (pit < nbpave)) {
1648     aFirstV = aPrevVertex;
1649     aLastV = aNextVertex;
1650     p2 = aC2->Value(aPave2.Parameter());
1651
1652     Standard_Boolean bisinside = Standard_False;
1653     Standard_Integer apbindex = 0;
1654     Standard_Integer apbcounter = 1;
1655     BOPDS_ListIteratorOfListOfPaveBlock aPBIt;
1656     BOPDS_ListIteratorOfListOfPave aPIt1, aPIt2;
1657     TColStd_ListIteratorOfListOfInteger aFlagIt;
1658
1659     for(aPIt1.Initialize(aFirstPaves), aPIt2.Initialize(aLastPaves), aFlagIt.Initialize(aListOfFlags);
1660         aPIt1.More() && aPIt2.More() && aFlagIt.More();
1661         aPIt1.Next(), aPIt2.Next(), aFlagIt.Next(), apbcounter++) {
1662
1663       Standard_Boolean bfin = Standard_False;
1664       Standard_Boolean blin = Standard_False;
1665
1666       if(aPave1.IsEqual(aPIt1.Value())) {
1667         bfin = Standard_True;
1668       }
1669       else {
1670         bfin = (aPave1.Parameter() > aPIt1.Value().Parameter());
1671       }
1672
1673       if(aFlagIt.Value()) {
1674         if(aPave2.IsEqual(aPIt2.Value())) {
1675           blin = Standard_True;
1676         }
1677         else {
1678           blin = (aPave2.Parameter() < aPIt2.Value().Parameter());
1679         }
1680       }
1681       else {
1682         if((aPave2.Index() == aPIt2.Value().Index()) && (aPave2.Index() > 0)) {
1683           Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface(theUE2Old, aFaceF, f, l);
1684           gp_Pnt2d p3 = pc->Value(aPIt2.Value().Parameter());
1685           TopoDS_Vertex aV = TopoDS::Vertex(theDS->Shape(aPave2.Index()));
1686           BRepAdaptor_Surface aBAS(aFaceF, Standard_False);
1687           Standard_Real aTolerance = BRep_Tool::Tolerance(aV);
1688           Standard_Real utol = aBAS.UResolution(aTolerance);
1689           Standard_Real vtol = aBAS.VResolution(aTolerance);
1690           aTolerance = (utol > vtol) ? utol : vtol;
1691
1692           if(p2.Distance(p3) < aTolerance)
1693             blin = Standard_True;
1694         }
1695       }
1696
1697       if(bfin && blin) {
1698         apbindex = apbcounter;
1699         bisinside = Standard_True;
1700         break;
1701       }
1702     }
1703
1704     if(!bisinside) {
1705
1706       TopTools_ListOfShape aOrderedList;
1707
1708       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1709         TopoDS_Compound aComp;
1710         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1711         aCompOfSecEdges = aComp;
1712         aListOfWireEdges.Append(aOrderedList);
1713
1714         bSecFound = Standard_True;
1715       }
1716       else {
1717         TopoDS_Edge aESplit;
1718         // get split
1719         aPBIt.Initialize(theDS->PaveBlocks(theBoundEdgeIndex));
1720
1721         for(; aPBIt.More(); aPBIt.Next()) {
1722           const Handle(BOPDS_PaveBlock)& aPB1 = aPBIt.Value();
1723           if (aPB1->OriginalEdge() == theBoundEdgeIndex &&
1724               aPB1->Pave1().IsEqual(aPave1) &&
1725               aPB1->Pave2().IsEqual(aPave2) ) {
1726             if(aPB1->Edge() > 0) {
1727               aESplit = *(TopoDS_Edge*)&theDS->Shape(aPB1->Edge());
1728               break;
1729             }
1730           }
1731         }
1732
1733         if(!aESplit.IsNull()) {
1734           aListOfWireEdges.Append(aESplit);
1735         }
1736       }
1737     }
1738     else {
1739       if(apbindex > 0) {
1740         TopTools_ListOfShape& aListOfSec = anArrayOfListOfSec(apbindex);
1741         aListOfWireEdges.Append(aListOfSec);
1742       }
1743     }
1744     aPave1 = aPave2;
1745     aPrevVertex = aNextVertex;
1746     p1 = p2;
1747     pit++;
1748   }
1749
1750   if(FindVertex(theUE2Old, theRank, theDS, theHistMap, aNextVertex, aPave2)) {
1751     aFirstV = aPrevVertex;
1752     aLastV = aNextVertex;
1753     Handle(Geom2d_Curve) aC3 = BRep_Tool::CurveOnSurface(theUE2Old, aFaceF, f, l);
1754     p2 = aC3->Value(aPave2.Parameter());
1755
1756     Standard_Boolean bisinside = Standard_False;
1757     Standard_Integer apbindex = 0;
1758     Standard_Integer apbcounter = 1;
1759     BOPDS_ListIteratorOfListOfPaveBlock aPBIt;
1760     BOPDS_ListIteratorOfListOfPave aPIt1, aPIt2;
1761     TColStd_ListIteratorOfListOfInteger aFlagIt;
1762
1763     for(aPIt1.Initialize(aFirstPaves), aPIt2.Initialize(aLastPaves), aFlagIt.Initialize(aListOfFlags);
1764         aPIt1.More() && aPIt2.More() && aFlagIt.More();
1765         aPIt1.Next(), aPIt2.Next(), aFlagIt.Next(), apbcounter++) {
1766
1767       Standard_Boolean bfin = Standard_False;
1768       Standard_Boolean blin = Standard_False;
1769
1770       if(aPave1.IsEqual(aPIt1.Value())) {
1771         bfin = Standard_True;
1772       }
1773       else {
1774         bfin = (aPave1.Parameter() > aPIt1.Value().Parameter());
1775       }
1776
1777       if(aFlagIt.Value()) {
1778         if(aPave2.IsEqual(aPIt2.Value())) {
1779           blin = Standard_True;
1780         }
1781         else {
1782           blin = (aPave2.Parameter() < aPIt2.Value().Parameter());
1783         }
1784       }
1785       else {
1786         blin = Standard_True;
1787       }
1788
1789       if(bfin && blin) {
1790         apbindex = apbcounter;
1791         bisinside = Standard_True;
1792         break;
1793       }
1794     }
1795
1796     if(!bisinside) {
1797
1798       TopTools_ListOfShape aOrderedList;
1799
1800       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1801         TopoDS_Compound aComp;
1802         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1803         aCompOfSecEdges = aComp;
1804         aListOfWireEdges.Append(aOrderedList);
1805
1806         bSecFound = Standard_True;
1807       }
1808       else {
1809         //add split
1810         TopoDS_Edge aESplit;
1811         // get split
1812         if(!GetPave(theBoundEdgeIndex, Standard_False, theDS, aPave2))
1813           return Standard_False;
1814         //
1815         aPBIt.Initialize(theDS->PaveBlocks(theBoundEdgeIndex));
1816         for(; aPBIt.More(); aPBIt.Next()) {
1817           const Handle(BOPDS_PaveBlock)& aPB1 = aPBIt.Value();
1818           if (aPB1->OriginalEdge() == theBoundEdgeIndex &&
1819               aPB1->Pave1().IsEqual(aPave1) &&
1820               aPB1->Pave2().IsEqual(aPave2) ) {
1821             if(aPB1->Edge() > 0) {
1822               aESplit = *(TopoDS_Edge*)&theDS->Shape(aPB1->Edge());
1823               break;
1824             }
1825           }
1826         }
1827
1828         if(!aESplit.IsNull()) {
1829           aListOfWireEdges.Append(aESplit);
1830         }
1831       }
1832     }
1833     else {
1834       if(apbindex > 0) {
1835         TopTools_ListOfShape& aListOfSec = anArrayOfListOfSec(apbindex);
1836         aListOfWireEdges.Append(aListOfSec);
1837       }
1838     }
1839   }
1840   else {
1841     //add split
1842     TopoDS_Edge aESplit;
1843     // get split
1844     if(!GetPave(theBoundEdgeIndex, Standard_False, theDS, aPave2))
1845       return Standard_False;
1846
1847     BOPDS_ListIteratorOfListOfPaveBlock aPBIt;
1848     aPBIt.Initialize(theDS->PaveBlocks(theBoundEdgeIndex));
1849     for(; aPBIt.More(); aPBIt.Next()) {
1850       const Handle(BOPDS_PaveBlock)& aPB1 = aPBIt.Value();
1851       if (aPB1->OriginalEdge() == theBoundEdgeIndex &&
1852           aPB1->Pave1().IsEqual(aPave1) &&
1853           aPB1->Pave2().IsEqual(aPave2) ) {
1854         if(aPB1->Edge() > 0) {
1855           aESplit = *(TopoDS_Edge*)&theDS->Shape(aPB1->Edge());
1856           break;
1857         }
1858       }
1859     }
1860
1861     if(!aESplit.IsNull()) {
1862       aListOfWireEdges.Append(aESplit);
1863     }
1864   }
1865
1866   // by pairs continuously. end
1867   theListOfWireEdges = aListOfWireEdges;
1868   isSectionFound = bSecFound;
1869   return Standard_True;
1870 }
1871
1872 // ----------------------------------------------------------------------------------------------------
1873 // static function: RemoveEdges
1874 // purpose:
1875 // ----------------------------------------------------------------------------------------------------
1876 void RemoveEdges(const TopoDS_Compound&      theSourceComp,
1877                  const TopTools_ListOfShape& theListToRemove,
1878                  TopoDS_Compound&            theResultComp) {
1879   BRep_Builder aBB;
1880   TopoDS_Compound aComp;
1881   aBB.MakeCompound(aComp);
1882   TopExp_Explorer anExp(theSourceComp, TopAbs_EDGE);
1883
1884   for(; anExp.More(); anExp.Next()) {
1885     Standard_Boolean bfound = Standard_False;
1886     TopTools_ListIteratorOfListOfShape anIt(theListToRemove);
1887
1888     for(; !bfound && anIt.More(); anIt.Next()) {
1889       bfound = anExp.Current().IsSame(anIt.Value());
1890     }
1891
1892     if(!bfound) {
1893       aBB.Add(aComp, anExp.Current());
1894     }
1895   }
1896   theResultComp = aComp;
1897 }
1898
1899 // ----------------------------------------------------------------------------------------------------
1900 // static function: FilterSectionEdges
1901 // purpose:
1902 // ----------------------------------------------------------------------------------------------------
1903 Standard_Boolean FilterSectionEdges(const BOPDS_VectorOfCurve&       theBCurves,
1904                                     const TopoDS_Face&               theSecPlane,
1905                                     const BOPDS_PDS&                 theDS,
1906                                     TopoDS_Compound&                 theResult) {
1907
1908   theResult.Nullify();
1909
1910   BRep_Builder aBB;
1911   aBB.MakeCompound(theResult);
1912   Standard_Integer aNbCurves = theBCurves.Extent();
1913   Standard_Integer cit = 0;
1914   BOPDS_ListIteratorOfListOfPaveBlock aPBIt;
1915
1916   for(cit = 0; cit < aNbCurves; ++cit) {
1917     const BOPDS_Curve& aBCurve = theBCurves(cit);
1918     const BOPDS_ListOfPaveBlock& aSectEdges = aBCurve.PaveBlocks();
1919
1920     aPBIt.Initialize(aSectEdges);
1921     for (; aPBIt.More(); aPBIt.Next()) {
1922       const Handle(BOPDS_PaveBlock)& aPB = aPBIt.Value();
1923       Standard_Integer nSect = aPB->Edge();
1924       const TopoDS_Shape& aS = theDS->Shape(nSect);
1925       TopoDS_Edge anEdge = TopoDS::Edge(aS);
1926       Standard_Boolean bAddEdge = Standard_True;
1927
1928       if(!theSecPlane.IsNull()) {
1929         IntTools_BeanFaceIntersector anIntersector(anEdge, theSecPlane);
1930         Standard_Real f = 0., l = 0.;
1931         BRep_Tool::Range(anEdge, f, l);
1932         anIntersector.SetBeanParameters(f, l);
1933         //
1934         Handle(BOPInt_Context) aContext = new BOPInt_Context;
1935         anIntersector.SetContext(aContext);
1936         //
1937         anIntersector.Perform();
1938
1939         if(anIntersector.IsDone()) {
1940           bAddEdge = Standard_False;
1941           Standard_Integer r = 0;
1942
1943           for(r = 1; r <= anIntersector.Result().Length(); r++) {
1944             const IntTools_Range& aRange = anIntersector.Result().Value(r);
1945
1946             if(((aRange.First() - f) < Precision::PConfusion()) &&
1947                ((l - aRange.Last()) < Precision::PConfusion())) {
1948               bAddEdge = Standard_True;
1949               break;
1950             }//if(((aRange.First() - f) < Precision::PConfusion()) &&
1951           }//for(r = 1; r <= anIntersector.Result().Length(); r++) {
1952         }//if(anIntersector.IsDone()) {
1953       }//if(!theSecPlane.IsNull()) {
1954
1955       if(bAddEdge) {
1956         aBB.Add(theResult, aS);
1957       }
1958     }//for (; aPBIt.More(); aPBIt.Next()) {
1959   }//for(cit = 0; cit < aNbCurves; ++cit) {
1960
1961   return Standard_True;
1962 }
1963
1964
1965 //=======================================================================
1966 //function : ComputeAveragePlaneAndMaxDeviation
1967 //purpose  :
1968 //=======================================================================
1969 static Standard_Real ComputeAveragePlaneAndMaxDeviation(const TopoDS_Shape& aWire,
1970                                                         gp_Pln& thePlane,
1971                                                         Standard_Boolean& IsSingular)
1972 {
1973   Standard_Integer N = 40, nedges = 0;
1974
1975   TopoDS_Iterator iter( aWire );
1976   for (; iter.More(); iter.Next())
1977     nedges++;
1978
1979   TColgp_Array1OfPnt Pnts( 1, nedges*N );
1980   Standard_Integer ind = 1, i;
1981   for (iter.Initialize(aWire); iter.More(); iter.Next())
1982     {
1983       const TopoDS_Edge& anEdge = TopoDS::Edge( iter.Value() );
1984       BRepAdaptor_Curve aCurve(anEdge);
1985       GCPnts_UniformAbscissa Distribution( aCurve, N+1 );
1986       for (i = 1; i <= N; i++)
1987         {
1988           Standard_Real par = Distribution.Parameter(i);
1989           Pnts( ind++ ) = aCurve.Value(par);
1990         }
1991     }
1992
1993   gp_Ax2 Axe;
1994   GeomLib::AxeOfInertia( Pnts, Axe, IsSingular );
1995   if (IsSingular)
1996     return -1;
1997
1998   thePlane = gp_Pln( Axe );
1999   Standard_Real MaxDeviation = 0;
2000   for (i = 1; i <= Pnts.Length(); i++)
2001     {
2002       Standard_Real dist = thePlane.Distance( Pnts(i) );
2003       if (dist > MaxDeviation)
2004         MaxDeviation = dist;
2005     }
2006   return MaxDeviation;
2007 }
2008
2009 //=======================================================================
2010 //function : ChooseSection
2011 //purpose  :
2012 //=======================================================================
2013 static Standard_Boolean ChooseSection(const TopoDS_Shape& Comp,
2014                                       const gp_Ax2& bis,
2015                                       TopoDS_Shape& resWire,
2016                                       gp_Pln& resPlane,
2017                                       Standard_Boolean& IsSingular)
2018 {
2019   IsSingular = Standard_False;
2020   Standard_Real TolDeviation = 0.01; //, TolConf = 1.e-4, TolAng = 1.e-5;
2021
2022 //  Standard_Integer N = 100;
2023   Standard_Integer ind, i, j;
2024
2025   //Simplest case
2026   TopoDS_Compound OldComp;
2027   BRep_Builder B;
2028   B.MakeCompound( OldComp );
2029   TopoDS_Iterator iter( Comp );
2030   for (; iter.More(); iter.Next())
2031     B.Add( OldComp, iter.Value() );
2032
2033   Standard_Boolean anError = Standard_False;
2034   //TopoDS_Wire NewWire [2];
2035   TopTools_SequenceOfShape Wseq;
2036   for (;;)
2037     {
2038       TopExp_Explorer explo( OldComp, TopAbs_EDGE );
2039       if (!explo.More())
2040         break;
2041       TopoDS_Edge FirstEdge = TopoDS::Edge( explo.Current() );
2042       TopoDS_Wire NewWire = BRepLib_MakeWire( FirstEdge );
2043       B.Remove( OldComp, FirstEdge );
2044       if (NewWire.Closed())
2045         {
2046           Wseq.Append(NewWire);
2047           continue;
2048         }
2049
2050       for (;;)
2051         {
2052           TopoDS_Vertex Extremity [2];
2053           TopExp::Vertices( NewWire, Extremity[0], Extremity[1] );
2054           if (Extremity[0].IsNull() || Extremity[1].IsNull())
2055             {
2056               anError = Standard_True;
2057               break;
2058             }
2059           TopTools_IndexedDataMapOfShapeListOfShape VEmap;
2060           TopExp::MapShapesAndAncestors( OldComp, TopAbs_VERTEX, TopAbs_EDGE, VEmap );
2061           TopTools_ListOfShape Vedges [2];
2062           for (j = 0; j < 2; j++)
2063             if (VEmap.Contains( Extremity[j] ))
2064               Vedges[j] = VEmap.FindFromKey( Extremity[j] );
2065           if (Vedges[0].IsEmpty() && Vedges[1].IsEmpty())
2066             //no more edges in OldComp to continue NewWire
2067             break;
2068           Standard_Boolean Modified = Standard_False;
2069           for (j = 0; j < 2; j++)
2070             {
2071               if (Vedges[j].Extent() == 1)
2072                 {
2073                   const TopoDS_Edge& anEdge = TopoDS::Edge( Vedges[j].First() );
2074                   NewWire = BRepLib_MakeWire( NewWire, anEdge );
2075                   B.Remove( OldComp, anEdge );
2076                   Modified = Standard_True;
2077                 }
2078             }
2079           if (!Modified) //only multiple connections
2080             {
2081               ind = (Vedges[0].IsEmpty())? 1 : 0;
2082               TopTools_SequenceOfShape Edges;
2083               TopTools_ListIteratorOfListOfShape itl( Vedges[ind] );
2084               for (; itl.More(); itl.Next())
2085                 Edges.Append( itl.Value() );
2086               Standard_Integer theind=0;
2087               Standard_Real MinDeviation = RealLast();
2088               for (j = 1; j <= Edges.Length(); j++)
2089                 {
2090                   TopoDS_Wire aWire = BRepLib_MakeWire( NewWire, TopoDS::Edge(Edges(j)) );
2091                   gp_Pln aPlane;
2092                   Standard_Boolean issing;
2093                   Standard_Real Deviation = ComputeAveragePlaneAndMaxDeviation( aWire, aPlane, issing );
2094                   if (Deviation < MinDeviation)
2095                     {
2096                       MinDeviation = Deviation;
2097                       theind = j;
2098                     }
2099                 }
2100               NewWire = BRepLib_MakeWire( NewWire, TopoDS::Edge(Edges(theind)) );
2101               B.Remove( OldComp, Edges(theind) );
2102             }
2103           if (NewWire.Closed())
2104             break;
2105         }
2106       Wseq.Append(NewWire);
2107       if (anError)
2108         break;
2109     }
2110
2111   Standard_Real Deviation=0.;
2112   Standard_Real MinAngle = RealLast();
2113   TopExp_Explorer Explo( OldComp, TopAbs_EDGE );
2114   if (!anError && !Explo.More())
2115     {
2116       if (Wseq.Length() == 1)
2117         {
2118           resWire = Wseq.First();
2119           Deviation = ComputeAveragePlaneAndMaxDeviation( resWire, resPlane, IsSingular );
2120           return Standard_True;
2121         }
2122       else
2123         {
2124           for (i = 1; i <= Wseq.Length(); i++)
2125             {
2126               TopoDS_Wire aWire = TopoDS::Wire( Wseq(i) );
2127               gp_Pln aPln;
2128               Standard_Boolean issing;
2129               Standard_Real aDeviation =
2130                 ComputeAveragePlaneAndMaxDeviation( aWire, aPln, issing );
2131               if (issing)
2132                 continue;
2133
2134               Standard_Real Angle = aPln.Axis().Angle( bis.Axis() );
2135               if (Angle > M_PI/2)
2136                 Angle = M_PI - Angle;
2137
2138               if (Angle < MinAngle)
2139                 {
2140                   MinAngle = Angle;
2141                   resWire = aWire;
2142                   resPlane = aPln;
2143                   Deviation = aDeviation;
2144                 }
2145             }
2146           if (Deviation <= TolDeviation)
2147             return Standard_True;
2148         }
2149     }
2150   return Standard_False;
2151   //end of simplest case
2152 }