src/BOPDS/BOPDS_DS.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   3 //
   4 // This file is part of Open CASCADE Technology software library.
   5 //
   6 // This library is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU Lesser General Public License version 2.1 as published
   8 // by the Free Software Foundation, with special exception defined in the file
   9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  10 // distribution for complete text of the license and disclaimer of any warranty.
  11 //
  12 // Alternatively, this file may be used under the terms of Open CASCADE
  13 // commercial license or contractual agreement.
  14
  15 #include <BOPDS_DS.ixx>
  16 //
  17 #include <NCollection_IncAllocator.hxx>
  18 #include <NCollection_BaseAllocator.hxx>
  19
  20 #include <gp_Pnt.hxx>
  21 #include <Bnd_Box.hxx>
  22 //
  23 #include <TopoDS_Shape.hxx>
  24 #include <TopoDS_Iterator.hxx>
  25 #include <TopoDS_Vertex.hxx>
  26 #include <TopoDS_Edge.hxx>
  27 #include <TopoDS_Face.hxx>
  28 #include <BRep_Tool.hxx>
  29 //
  30 #include <BRepBndLib.hxx>
  31 //
  32 #include <BOPCol_MapOfInteger.hxx>
  33 #include <BOPCol_ListOfInteger.hxx>
  34 #include <BOPCol_DataMapOfShapeInteger.hxx>
  35 //
  36 #include <BOPDS_IndexRange.hxx>
  37 #include <BOPDS_ShapeInfo.hxx>
  38 #include <BOPDS_PassKey.hxx>
  39 #include <BOPDS_DataMapOfPassKeyListOfPaveBlock.hxx>
  40 #include <BOPDS_PassKey.hxx>
  41
  42 #include <Geom_Curve.hxx>
  43 #include <BRep_Builder.hxx>
  44 #include <Precision.hxx>
  45 #include <IntTools_Tools.hxx>
  46 #include <BOPTools_AlgoTools.hxx>
  47 #include <GeomAPI_ProjectPointOnCurve.hxx>
  48 #include <BOPDS_MapOfPave.hxx>
  49
  50 //
  51 static
  52   inline void ResetShape(const TopoDS_Shape& aS);
  53
  54 static
  55   inline void ResetShapes(const TopoDS_Shape& aS);
  56
  57 static
  58   void TotalShapes(const TopoDS_Shape& aS,
  59                    Standard_Integer& aNbS);
  60
  61 static
  62   Standard_Real ComputeParameter(const TopoDS_Vertex& aV,
  63                                  const TopoDS_Edge& aE);
  64 static
  65   void SortShell(const int n, BOPDS_Pave *a);
  66
  67 //=======================================================================
  68 //function :
  69 //purpose  :
  70 //=======================================================================
  71 BOPDS_DS::BOPDS_DS()
  72 :
  73   myAllocator(NCollection_BaseAllocator::CommonBaseAllocator()),
  74   myArguments(myAllocator),
  75   myRanges(myAllocator),
  76   myLines(myAllocator),
  77   myMapShapeIndex(100, myAllocator),
  78   myPaveBlocksPool(myAllocator),
  79   myMapPBCB(100, myAllocator),
  80   myFaceInfoPool(myAllocator),
  81   myShapesSD(100, myAllocator),
  82   myInterfTB(100, myAllocator),
  83   myInterfVV(myAllocator),
  84   myInterfVE(myAllocator),
  85   myInterfVF(myAllocator),
  86   myInterfEE(myAllocator),
  87   myInterfEF(myAllocator),
  88   myInterfFF(myAllocator),
  89   myInterfVZ(myAllocator),
  90   myInterfEZ(myAllocator),
  91   myInterfFZ(myAllocator),
  92   myInterfZZ(myAllocator)
  93 {
  94   myNbShapes=0;
  95   myNbSourceShapes=0;
  96 }
  97 //=======================================================================
  98 //function :
  99 //purpose  :
 100 //=======================================================================
 101 BOPDS_DS::BOPDS_DS(const Handle(NCollection_BaseAllocator)& theAllocator)
 102 :
 103   myAllocator(theAllocator),
 104   myArguments(myAllocator),
 105   myRanges(myAllocator),
 106   myLines(myAllocator),
 107   myMapShapeIndex(100, myAllocator),
 108   myPaveBlocksPool(myAllocator),
 109   myMapPBCB(100, myAllocator),
 110   myFaceInfoPool(myAllocator),
 111   myShapesSD(100, myAllocator),
 112   myInterfTB(100, myAllocator),
 113   myInterfVV(myAllocator),
 114   myInterfVE(myAllocator),
 115   myInterfVF(myAllocator),
 116   myInterfEE(myAllocator),
 117   myInterfEF(myAllocator),
 118   myInterfFF(myAllocator),
 119   myInterfVZ(myAllocator),
 120   myInterfEZ(myAllocator),
 121   myInterfFZ(myAllocator),
 122   myInterfZZ(myAllocator)
 123 {
 124   myNbShapes=0;
 125   myNbSourceShapes=0;
 126 }
 127 //=======================================================================
 128 //function : ~
 129 //purpose  :
 130 //=======================================================================
 131 BOPDS_DS::~BOPDS_DS()
 132 {
 133   Clear();
 134 }
 135 //=======================================================================
 136 //function : Clear
 137 //purpose  :
 138 //=======================================================================
 139 void BOPDS_DS::Clear()
 140 {
 141   myNbShapes=0;
 142   myNbSourceShapes=0;
 143   //
 144   myArguments.Clear();
 145   myRanges.Clear();
 146   myLines.Clear();
 147   myMapShapeIndex.Clear();
 148   myPaveBlocksPool.Clear();
 149   myFaceInfoPool.Clear();
 150   myShapesSD.Clear();
 151   myMapPBCB.Clear();
 152   myInterfTB.Clear();
 153   myInterfVV.Clear();
 154   myInterfVE.Clear();
 155   myInterfVF.Clear();
 156   myInterfEE.Clear();
 157   myInterfEF.Clear();
 158   myInterfFF.Clear();
 159   myInterfVZ.Clear();
 160   myInterfEZ.Clear();
 161   myInterfFZ.Clear();
 162   myInterfZZ.Clear();
 163 }
 164 //=======================================================================
 165 //function : SetArguments
 166 //purpose  :
 167 //=======================================================================
 168 void BOPDS_DS::SetArguments(const BOPCol_ListOfShape& theLS)
 169 {
 170   myArguments=theLS;
 171 }
 172 //=======================================================================
 173 //function : Arguments
 174 //purpose  :
 175 //=======================================================================
 176 const BOPCol_ListOfShape& BOPDS_DS::Arguments()const
 177 {
 178   return myArguments;
 179 }
 180 //=======================================================================
 181 //function : Allocator
 182 //purpose  :
 183 //=======================================================================
 184 const Handle(NCollection_BaseAllocator)& BOPDS_DS::Allocator()const
 185 {
 186   return myAllocator;
 187 }
 188
 189 //=======================================================================
 190 //function : NbShapes
 191 //purpose  :
 192 //=======================================================================
 193 Standard_Integer BOPDS_DS::NbShapes()const
 194 {
 195   return myLines.Size();
 196 }
 197 //=======================================================================
 198 //function : NbSourceShapes
 199 //purpose  :
 200 //=======================================================================
 201 Standard_Integer BOPDS_DS::NbSourceShapes()const
 202 {
 203   return myNbSourceShapes;
 204 }
 205 //=======================================================================
 206 //function : NbRanges
 207 //purpose  :
 208 //=======================================================================
 209 Standard_Integer BOPDS_DS::NbRanges()const
 210 {
 211   return myRanges.Size();
 212 }
 213 //=======================================================================
 214 //function : Range
 215 //purpose  :
 216 //=======================================================================
 217 const BOPDS_IndexRange& BOPDS_DS::Range(const Standard_Integer theI)const
 218 {
 219   return myRanges(theI);
 220 }
 221 //=======================================================================
 222 //function : Rank
 223 //purpose  :
 224 //=======================================================================
 225 Standard_Integer BOPDS_DS::Rank(const Standard_Integer theI)const
 226 {
 227   Standard_Integer i, aNb, iErr;
 228   //
 229   iErr=-1;
 230   aNb=NbRanges();
 231   for(i=0; i<aNb; ++i) {
 232     const BOPDS_IndexRange& aR=Range(i);
 233     if (aR.Contains(theI)) {
 234       return i;
 235     }
 236   }
 237   return iErr;
 238 }
 239 //=======================================================================
 240 //function : IsNewShape
 241 //purpose  :
 242 //=======================================================================
 243 Standard_Boolean BOPDS_DS::IsNewShape(const Standard_Integer theI)const
 244 {
 245   return theI>=NbSourceShapes();
 246 }
 247 //=======================================================================
 248 //function : Append
 249 //purpose  :
 250 //=======================================================================
 251 Standard_Integer BOPDS_DS::Append(const BOPDS_ShapeInfo& theSI)
 252 {
 253   Standard_Integer iX;
 254   //
 255   iX=myLines.Append()-1;
 256   myLines(iX)=theSI;
 257   return iX;
 258 }
 259 //=======================================================================
 260 //function : Append
 261 //purpose  :
 262 //=======================================================================
 263 Standard_Integer BOPDS_DS::Append(const TopoDS_Shape& theS)
 264 {
 265   Standard_Integer iX;
 266   //
 267   iX=myLines.Append()-1;
 268   myLines(iX).SetShape(theS);
 269   return iX;
 270 }
 271 //=======================================================================
 272 //function : ShapeInfo
 273 //purpose  :
 274 //=======================================================================
 275 const BOPDS_ShapeInfo& BOPDS_DS::ShapeInfo
 276   (const Standard_Integer theI)const
 277 {
 278   return myLines(theI);
 279 }
 280 //=======================================================================
 281 //function : ChangeShapeInfo
 282 //purpose  :
 283 //=======================================================================
 284 BOPDS_ShapeInfo& BOPDS_DS::ChangeShapeInfo(const Standard_Integer theI)
 285 {
 286   BOPDS_ShapeInfo *pSI;
 287   //
 288   const BOPDS_ShapeInfo& aSI=ShapeInfo(theI);
 289   pSI=(BOPDS_ShapeInfo *)&aSI;
 290   return *pSI;
 291 }
 292 //=======================================================================
 293 //function : Shape
 294 //purpose  :
 295 //=======================================================================
 296 const TopoDS_Shape& BOPDS_DS::Shape(const Standard_Integer theI)const
 297 {
 298   const TopoDS_Shape& aS=ShapeInfo(theI).Shape();
 299   return aS;
 300 }
 301 //=======================================================================
 302 //function : Index
 303 //purpose  :
 304 //=======================================================================
 305 Standard_Integer BOPDS_DS::Index(const TopoDS_Shape& theS)const
 306 {
 307   Standard_Integer iRet;
 308   //
 309   iRet=-1;
 310   if (myMapShapeIndex.IsBound(theS)) {
 311     iRet=myMapShapeIndex.Find(theS);
 312   }
 313   return iRet;
 314 }
 315
 316 //=======================================================================
 317 //function : Init
 318 //purpose  :
 319 //=======================================================================
 320 void BOPDS_DS::Init()
 321 {
 322   Standard_Integer i1, i2, j, aI, aNb, aNbS, aNbE, aNbSx;
 323   Standard_Integer n1, n2, n3, nV, nW, nE, aNbF;
 324   Standard_Real aTol;
 325   TopAbs_ShapeEnum aTS;
 326   TopoDS_Iterator aItS;
 327   BOPCol_ListIteratorOfListOfInteger aIt1, aIt2, aIt3;
 328   BOPCol_ListIteratorOfListOfShape aIt;
 329   BOPDS_IndexRange aR;
 330   Handle(NCollection_IncAllocator) aAllocator;
 331   //
 332   // 1 Append Source Shapes
 333   aNb=myArguments.Extent();
 334   if (!aNb) {
 335     return;
 336   }
 337   //
 338   myRanges.SetStartSize(aNb);
 339   myRanges.Init();
 340   //
 341   aIt.Initialize(myArguments);
 342   for (; aIt.More(); aIt.Next()) {
 343     const TopoDS_Shape& aSx=aIt.Value();
 344     ResetShapes(aSx);
 345   }
 346   //
 347   aNbS=0;
 348   aIt.Initialize(myArguments);
 349   for (; aIt.More(); aIt.Next()) {
 350     const TopoDS_Shape& aSx=aIt.Value();
 351     //
 352     aNbSx=0;
 353     TotalShapes(aSx, aNbSx);
 354     aNbS=aNbS+aNbSx;
 355   }
 356   //
 357   myLines.SetStartSize(2*aNbS);
 358   myLines.SetIncrement(aNbS);
 359   myLines.Init();
 360   //
 361   //-----------------------------------------------------scope_1 f
 362   aAllocator=new NCollection_IncAllocator();
 363   //
 364   BOPCol_DataMapOfShapeInteger& aMSI=myMapShapeIndex;
 365   //
 366   i1=0;
 367   i2=0;
 368   aIt.Initialize(myArguments);
 369   for (; aIt.More(); aIt.Next()) {
 370     const TopoDS_Shape& aS=aIt.Value();
 371     if (aMSI.IsBound(aS)) {
 372       continue;
 373     }
 374     aI=Append(aS);
 375     aMSI.Bind(aS, aI);
 376     //
 377     InitShape(aI, aS, aAllocator, aMSI);
 378     //
 379     i2=NbShapes()-1;
 380     aR.SetIndices(i1, i2);
 381     myRanges.Append(aR);
 382     i1=i2+1;
 383   }
 384   //
 385   myNbSourceShapes=NbShapes();
 386   //
 387   // 2 Bounding Boxes
 388   //
 389   // 2.1 Vertex
 390   for (j=0; j<myNbSourceShapes; ++j) {
 391     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
 392     //
 393     const TopoDS_Shape& aS=aSI.Shape();
 394     ResetShape(aS);
 395     //
 396     aTS=aSI.ShapeType();
 397     //
 398     if (aTS==TopAbs_VERTEX) {
 399       Bnd_Box& aBox=aSI.ChangeBox();
 400       const TopoDS_Vertex& aV=*((TopoDS_Vertex*)&aS);
 401       const gp_Pnt& aP=BRep_Tool::Pnt(aV);
 402       aTol=BRep_Tool::Tolerance(aV);
 403       aBox.SetGap(aTol);
 404       aBox.Add(aP);
 405     }
 406   }
 407   // 2.2 Edge
 408   aNbE=0;
 409   for (j=0; j<myNbSourceShapes; ++j) {
 410     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
 411     //
 412     aTS=aSI.ShapeType();
 413     if (aTS==TopAbs_EDGE) {
 414       const TopoDS_Shape& aS=aSI.Shape();
 415       const TopoDS_Edge& aE=*((TopoDS_Edge*)&aS);
 416       aTol=BRep_Tool::Tolerance(aE);
 417       //
 418       if (!BRep_Tool::Degenerated(aE)) {
 419         Standard_Boolean bInf1, bInf2;
 420         Standard_Integer aIx;
 421         Standard_Real aT1, aT2;
 422         gp_Pnt aPx;
 423         Handle(Geom_Curve) aC3D;
 424         TopoDS_Vertex aVx;
 425         TopoDS_Edge aEx;
 426         BRep_Builder aBB;
 427         BOPDS_ShapeInfo aSIx;
 428         //
 429         BOPCol_ListOfInteger& aLI=aSI.ChangeSubShapes();
 430         //
 431         aEx=aE;
 432         aEx.Orientation(TopAbs_FORWARD);
 433         //
 434         aC3D=BRep_Tool::Curve (aEx, aT1, aT2);
 435         bInf1=Precision::IsNegativeInfinite(aT1);
 436         bInf2=Precision::IsPositiveInfinite(aT2);
 437         //
 438         if (bInf1) {
 439           aC3D->D0(aT1, aPx);
 440           aBB.MakeVertex(aVx, aPx, aTol);
 441           aVx.Orientation(TopAbs_FORWARD);
 442           //
 443           aSIx.SetShape(aVx);
 444           aSIx.SetShapeType(TopAbs_VERTEX);
 445           aSIx.SetFlag(1); //infinite flag
 446           //
 447           aIx=Append(aSIx);
 448           aLI.Append(aIx);
 449         }
 450         if (bInf2) {
 451           aC3D->D0(aT2, aPx);
 452           aBB.MakeVertex(aVx, aPx, aTol);
 453           aVx.Orientation(TopAbs_REVERSED);
 454           //
 455           aSIx.SetShape(aVx);
 456           aSIx.SetShapeType(TopAbs_VERTEX);
 457           aSIx.SetFlag(1);//infinite flag
 458           //
 459           aIx=Append(aSIx);
 460           aLI.Append(aIx);
 461         }
 462       }
 463       else {
 464         aSI.SetFlag(j);
 465       }
 466       //
 467       Bnd_Box& aBox=aSI.ChangeBox();
 468       BRepBndLib::Add(aE, aBox);
 469       //
 470       const BOPCol_ListOfInteger& aLV=aSI.SubShapes();
 471       aIt1.Initialize(aLV);
 472       for (; aIt1.More(); aIt1.Next()) {
 473         nV=aIt1.Value();
 474         BOPDS_ShapeInfo& aSIV=ChangeShapeInfo(nV);
 475         Bnd_Box& aBx=aSIV.ChangeBox();
 476         aBox.Add(aBx);
 477       }
 478       ++aNbE;
 479     }
 480   }
 481   // 2.3 Face
 482   BOPCol_MapOfInteger aMI(100, aAllocator);
 483   BOPCol_MapIteratorOfMapOfInteger aItMI;
 484   //
 485   aNbF=0;
 486   for (j=0; j<myNbSourceShapes; ++j) {
 487     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
 488     //
 489     aTS=aSI.ShapeType();
 490     if (aTS==TopAbs_FACE) {
 491       const TopoDS_Shape& aS=aSI.Shape();
 492       const TopoDS_Face& aF=*((TopoDS_Face*)&aS);
 493       aTol=BRep_Tool::Tolerance(aF);
 494       //
 495       Bnd_Box& aBox=aSI.ChangeBox();
 496       BRepBndLib::Add(aS, aBox);
 497       //
 498       BOPCol_ListOfInteger& aLW=aSI.ChangeSubShapes();
 499       aIt1.Initialize(aLW);
 500       for (; aIt1.More(); aIt1.Next()) {
 501         nW=aIt1.Value();
 502         BOPDS_ShapeInfo& aSIW=ChangeShapeInfo(nW);
 503         //
 504         const BOPCol_ListOfInteger& aLE=aSIW.SubShapes();
 505         aIt2.Initialize(aLE);
 506         for (; aIt2.More(); aIt2.Next()) {
 507           nE=aIt2.Value();
 508           BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
 509           Bnd_Box& aBx=aSIE.ChangeBox();
 510           aBox.Add(aBx);
 511           aMI.Add(nE);
 512           //
 513           const TopoDS_Edge& aE=*(TopoDS_Edge*)(&aSIE.Shape());
 514           if (BRep_Tool::Degenerated(aE)) {
 515             aSIE.SetFlag(j);
 516           }
 517           //
 518           const BOPCol_ListOfInteger& aLV=aSIE.SubShapes();
 519           aIt3.Initialize(aLV);
 520           for (; aIt3.More(); aIt3.Next()) {
 521             nV=aIt3.Value();
 522             aMI.Add(nV);
 523           }
 524         }
 525       }//for (; aIt1.More(); aIt1.Next()) {
 526       //
 527       // pure internal vertices on the face
 528       aItS.Initialize(aS);
 529       for (; aItS.More(); aItS.Next()) {
 530         const TopoDS_Shape& aSx=aItS.Value();
 531         if (aSx.ShapeType()==TopAbs_VERTEX){
 532           nV=Index(aSx);
 533           aMI.Add(nV);
 534         }
 535       }
 536       //
 537       //
 538       // For a Face: change wires for BRep sub-shapes
 539       aLW.Clear();
 540       aItMI.Initialize(aMI);
 541       for (; aItMI.More(); aItMI.Next()) {
 542         nV=aItMI.Value();
 543         aLW.Append(nV);
 544       }
 545       aMI.Clear();
 546       ++aNbF;
 547     }//if (aTS==TopAbs_FACE) {
 548   }//for (j=0; j<myNbSourceShapes; ++j) {
 549   //
 550   // 2.4 Solids
 551   for (j=0; j<myNbSourceShapes; ++j) {
 552     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
 553     //
 554     aTS=aSI.ShapeType();
 555     if (aTS!=TopAbs_SOLID) {
 556       continue;
 557     }
 558     Bnd_Box& aBox=aSI.ChangeBox();
 559     BuildBndBoxSolid(j, aBox);
 560     //
 561     //
 562     // update sub-shapes by BRep comprising ones
 563     aMI.Clear();
 564     BOPCol_ListOfInteger& aLI1=aSI.ChangeSubShapes();
 565     //
 566     aIt1.Initialize(aLI1);
 567     for (; aIt1.More(); aIt1.Next()) {
 568       n1=aIt1.Value();
 569       BOPDS_ShapeInfo& aSI1=ChangeShapeInfo(n1);
 570       if (aSI1.ShapeType()!=TopAbs_SHELL) {
 571         continue;
 572       }
 573       //
 574       const BOPCol_ListOfInteger& aLI2=aSI1.SubShapes();
 575       aIt2.Initialize(aLI2);
 576       for (; aIt2.More(); aIt2.Next()) {
 577         n2=aIt2.Value();
 578         BOPDS_ShapeInfo& aSI2=ChangeShapeInfo(n2);
 579         if (aSI2.ShapeType()!=TopAbs_FACE) {
 580           continue;
 581         }
 582         //
 583         aMI.Add(n2);
 584         //
 585         const BOPCol_ListOfInteger& aLI3=aSI2.SubShapes();
 586         aIt3.Initialize(aLI3);
 587         for (; aIt3.More(); aIt3.Next()) {
 588           n3=aIt3.Value();
 589           aMI.Add(n3);
 590         }
 591       }
 592     }
 593     //
 594     aLI1.Clear();
 595     aItMI.Initialize(aMI);
 596     for (; aItMI.More(); aItMI.Next()) {
 597       n1=aItMI.Value();
 598       aLI1.Append(n1);
 599     }
 600     aMI.Clear();
 601   }//for (j=0; j<myNbSourceShapes; ++j) {
 602   //
 603   aMI.Clear();
 604   aAllocator.Nullify();
 605   //-----------------------------------------------------scope_1 t
 606   //
 607   // 3 myPaveBlocksPool
 608   myPaveBlocksPool.SetStartSize(aNbE);
 609   myPaveBlocksPool.SetIncrement(aNbE);
 610   myPaveBlocksPool.Init();
 611   //
 612   // 4. myFaceInfoPool
 613   myFaceInfoPool.SetStartSize(aNbF);
 614   myFaceInfoPool.SetIncrement(aNbF);
 615   myFaceInfoPool.Init();
 616   //
 617 }
 618 //=======================================================================
 619 //function : InitShape
 620 //purpose  :
 621 //=======================================================================
 622 void BOPDS_DS::InitShape
 623   (const Standard_Integer aI,
 624    const TopoDS_Shape& aS,
 625    Handle(NCollection_BaseAllocator)& theAllocator,
 626    BOPCol_DataMapOfShapeInteger& aMSI)
 627 {
 628   Standard_Integer aIx;
 629   TopoDS_Iterator aIt;
 630   BOPCol_ListIteratorOfListOfInteger aIt1;
 631   //
 632   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(aI);
 633   aSI.SetShapeType(aS.ShapeType());
 634   BOPCol_ListOfInteger& aLI=aSI.ChangeSubShapes();
 635   //
 636   BOPCol_MapOfInteger aM(100, theAllocator);
 637   //
 638   aIt1.Initialize(aLI);
 639   for (; aIt1.More(); aIt1.Next()) {
 640     aM.Add(aIt1.Value());
 641   }
 642   //
 643   aIt.Initialize(aS);
 644   for (; aIt.More(); aIt.Next()) {
 645     const TopoDS_Shape& aSx=aIt.Value();
 646     if (aMSI.IsBound(aSx)) {
 647       aIx=aMSI.Find(aSx);
 648     }
 649     else {
 650       aIx=Append(aSx);
 651       aMSI.Bind(aSx, aIx);
 652     }
 653     //
 654     InitShape(aIx, aSx, theAllocator, aMSI);
 655     //
 656     if (aM.Add(aIx)) {
 657       aLI.Append(aIx);
 658     }
 659   }
 660 }
 661
 662 //=======================================================================
 663 //function : HasInterf
 664 //purpose  :
 665 //=======================================================================
 666 Standard_Boolean BOPDS_DS::HasInterf(const Standard_Integer theI) const
 667 {
 668   Standard_Integer n1, n2;
 669   Standard_Boolean bRet;
 670   BOPDS_MapIteratorMapOfPassKey aIt;
 671   //
 672   bRet = Standard_False;
 673   //
 674   aIt.Initialize(myInterfTB);
 675   for (; aIt.More(); aIt.Next()) {
 676     const BOPDS_PassKey& aPK = aIt.Value();
 677     aPK.Ids(n1, n2);
 678     if (n1 == theI || n2 == theI) {
 679       bRet = Standard_True;
 680       break;
 681     }
 682   }
 683   //
 684   return bRet;
 685 }
 686 //=======================================================================
 687 //function : HasInterfShapeSubShapes
 688 //purpose  :
 689 //=======================================================================
 690 Standard_Boolean BOPDS_DS::HasInterfShapeSubShapes
 691   (const Standard_Integer theI1,
 692    const Standard_Integer theI2,
 693    const Standard_Boolean theFlag)const
 694 {
 695   Standard_Boolean bRet;
 696   Standard_Integer n2;
 697   BOPCol_ListIteratorOfListOfInteger aIt;
 698   bRet = Standard_False;
 699   //
 700   const BOPDS_ShapeInfo& aSI=ShapeInfo(theI2);
 701   const BOPCol_ListOfInteger& aLI=aSI.SubShapes();
 702   aIt.Initialize(aLI);
 703   for (; aIt.More(); aIt.Next()) {
 704     n2=aIt.Value();
 705     bRet=HasInterf(theI1, n2);
 706     if (theFlag) {
 707       if(bRet) {
 708  break;
 709       }
 710     }
 711     else {
 712       if(!bRet) {
 713  break;
 714       }
 715     }
 716   }
 717   return bRet;
 718 }
 719 //=======================================================================
 720 //function : HasInterfSubShapes
 721 //purpose  :
 722 //=======================================================================
 723 Standard_Boolean BOPDS_DS::HasInterfSubShapes
 724   (const Standard_Integer theI1,
 725    const Standard_Integer theI2)const
 726 {
 727   Standard_Boolean bRet;
 728   Standard_Integer n1;
 729   BOPCol_ListIteratorOfListOfInteger aIt;
 730   bRet = Standard_False;
 731   //
 732   const BOPDS_ShapeInfo& aSI=ShapeInfo(theI1);
 733   const BOPCol_ListOfInteger& aLI=aSI.SubShapes();
 734   aIt.Initialize(aLI);
 735   for (; aIt.More(); aIt.Next()) {
 736     n1=aIt.Value();
 737     bRet=HasInterfShapeSubShapes(n1, theI2);
 738     if(bRet) {
 739       break;
 740     }
 741   }
 742   return bRet;
 743 }
 744 //
 745 // PaveBlocks
 746 //=======================================================================
 747 //function : PaveBlocksPool
 748 //purpose  :
 749 //=======================================================================
 750 const BOPDS_VectorOfListOfPaveBlock& BOPDS_DS::PaveBlocksPool()const
 751 {
 752   return myPaveBlocksPool;
 753 }
 754 //=======================================================================
 755 //function : ChangePaveBlocksPool
 756 //purpose  :
 757 //=======================================================================
 758 BOPDS_VectorOfListOfPaveBlock& BOPDS_DS::ChangePaveBlocksPool()
 759 {
 760   return myPaveBlocksPool;
 761 }
 762 //=======================================================================
 763 //function : HasPaveBlocks
 764 //purpose  :
 765 //=======================================================================
 766 Standard_Boolean BOPDS_DS::HasPaveBlocks(const Standard_Integer theI)const
 767 {
 768   return ShapeInfo(theI).HasReference();
 769 }
 770 //=======================================================================
 771 //function : PaveBlocks
 772 //purpose  :
 773 //=======================================================================
 774 const BOPDS_ListOfPaveBlock& BOPDS_DS::PaveBlocks
 775   (const Standard_Integer theI)const
 776 {
 777   static BOPDS_ListOfPaveBlock sLPB;
 778   Standard_Integer aRef;
 779   //
 780   if (HasPaveBlocks(theI)) {
 781     aRef=ShapeInfo(theI).Reference();
 782     const BOPDS_ListOfPaveBlock& aLPB=myPaveBlocksPool(aRef);
 783     return aLPB;
 784   }
 785   return sLPB;
 786 }
 787 //=======================================================================
 788 //function : ChangePaveBlocks
 789 //purpose  :
 790 //=======================================================================
 791 BOPDS_ListOfPaveBlock& BOPDS_DS::ChangePaveBlocks
 792   (const Standard_Integer theI)
 793 {
 794   Standard_Boolean bHasReference;
 795   Standard_Integer aRef;
 796   //
 797   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
 798   bHasReference=aSI.HasReference();
 799   if (!bHasReference) {
 800     InitPaveBlocks(theI);
 801   }
 802   //
 803   aRef=aSI.Reference();
 804   return myPaveBlocksPool(aRef);
 805 }
 806 //=======================================================================
 807 //function : InitPaveBlocks
 808 //purpose  :
 809 //=======================================================================
 810 void BOPDS_DS::InitPaveBlocks(const Standard_Integer theI)
 811 {
 812   Standard_Integer nV = 0, iRef, aNbV, nVSD, i;
 813   Standard_Real aT;
 814   TopoDS_Vertex aV;
 815   BOPCol_ListIteratorOfListOfInteger aIt;
 816   BOPDS_Pave aPave;
 817   Handle(BOPDS_PaveBlock) aPB;
 818   //
 819   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
 820   const TopoDS_Edge& aE=*(TopoDS_Edge*)(&aSI.Shape());
 821   //
 822   const BOPCol_ListOfInteger& aLV=aSI.SubShapes();
 823   aNbV=aLV.Extent();
 824   if (!aNbV) {
 825     return;
 826   }
 827   //
 828   aPB=new BOPDS_PaveBlock;
 829   aPB->SetOriginalEdge(theI);
 830   //
 831   aIt.Initialize(aLV);
 832   for (i=0; aIt.More(); aIt.Next(), ++i) {
 833     nV=aIt.Value();
 834     //
 835     const BOPDS_ShapeInfo& aSIV=ShapeInfo(nV);
 836     aV=*(TopoDS_Vertex*)(&aSIV.Shape());
 837     if (aSIV.HasFlag()) {
 838       aT=ComputeParameter(aV, aE);
 839     }
 840     else {
 841       aT=BRep_Tool::Parameter(aV, aE);
 842     }
 843     //
 844     if (HasShapeSD(nV, nVSD)) {
 845       nV=nVSD;
 846     }
 847     aPave.SetIndex(nV);
 848     aPave.SetParameter(aT);
 849     aPB->AppendExtPave(aPave);
 850   }
 851   //
 852   if (aNbV==1) {
 853     aV.Reverse();
 854     aT=BRep_Tool::Parameter(aV, aE);
 855     aPave.SetIndex(nV);
 856     aPave.SetParameter(aT);
 857     aPB->AppendExtPave1(aPave);
 858   }
 859   //
 860   iRef = myPaveBlocksPool.Append() - 1;
 861   BOPDS_ListOfPaveBlock &aLPB=myPaveBlocksPool(iRef);
 862   //
 863   aPB->Update(aLPB, Standard_False);
 864   aSI.SetReference(iRef);
 865 }
 866 //=======================================================================
 867 //function : UpdatePaveBlocks
 868 //purpose  :
 869 //=======================================================================
 870 void BOPDS_DS::UpdatePaveBlocks()
 871 {
 872   Standard_Boolean bIsToUpdate;
 873   Standard_Integer i, aNbPBP;
 874   BOPDS_ListOfPaveBlock aLPBN(myAllocator);
 875   BOPDS_ListIteratorOfListOfPaveBlock aItPB, aItPBN;
 876   //
 877   BOPDS_VectorOfListOfPaveBlock& aPBP=myPaveBlocksPool;
 878   //
 879   aNbPBP=aPBP.Size();
 880   for (i=0; i<aNbPBP; ++i) {
 881     BOPDS_ListOfPaveBlock& aLPB=aPBP(i);
 882     //
 883     aItPB.Initialize(aLPB);
 884     for (; aItPB.More(); aItPB.Next()) {
 885       Handle(BOPDS_PaveBlock)& aPB=aItPB.ChangeValue();
 886       //
 887       bIsToUpdate=aPB->IsToUpdate();
 888       if (bIsToUpdate){
 889         aLPBN.Clear();
 890         aPB->Update(aLPBN);
 891
 892         aItPBN.Initialize(aLPBN);
 893         for (; aItPBN.More(); aItPBN.Next()) {
 894           Handle(BOPDS_PaveBlock)& aPBN=aItPBN.ChangeValue();
 895           aLPB.Append(aPBN);
 896         }
 897         aLPB.Remove(aItPB);
 898       }
 899     }// for (; aItPB.More(); aItPB.Next()) {
 900   }// for (i=0; i<aNbPBP; ++i) {
 901 }
 902 //=======================================================================
 903 //function : UpdatePaveBlock
 904 //purpose  :
 905 //=======================================================================
 906 void BOPDS_DS::UpdatePaveBlock(const Handle(BOPDS_PaveBlock)& thePB)
 907 {
 908   if (!thePB->IsToUpdate()){
 909     return;
 910   }
 911   //
 912   Standard_Integer nE, iRef;
 913   BOPDS_ListIteratorOfListOfPaveBlock aItPB, aItPBN;
 914   BOPDS_ListOfPaveBlock aLPBN(myAllocator);
 915   Handle(BOPDS_PaveBlock) aPB;
 916   //
 917   BOPDS_VectorOfListOfPaveBlock& aPBP=myPaveBlocksPool;
 918   //
 919   nE=thePB->OriginalEdge();
 920   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(nE);
 921   iRef=aSI.Reference();
 922   BOPDS_ListOfPaveBlock& aLPB=aPBP(iRef);
 923   //
 924   aItPB.Initialize(aLPB);
 925   for (; aItPB.More(); aItPB.Next()) {
 926     aPB=aItPB.ChangeValue();
 927     if (aPB==thePB) {
 928       aPB->Update(aLPBN);
 929       //
 930       aItPBN.Initialize(aLPBN);
 931       for (; aItPBN.More(); aItPBN.Next()) {
 932         Handle(BOPDS_PaveBlock)& aPBN=aItPBN.ChangeValue();
 933         aLPB.Append(aPBN);
 934       }
 935       aLPB.Remove(aItPB);
 936       break;
 937     }
 938   }
 939 }
 940 //=======================================================================
 941 //function : UpdateCommonBlock
 942 //purpose  :
 943 //=======================================================================
 944 void BOPDS_DS::UpdateCommonBlock(const Handle(BOPDS_CommonBlock)& theCB)
 945 {
 946   Standard_Integer nE, iRef, n1, n2;
 947   BOPDS_ListIteratorOfListOfPaveBlock aItPB, aItPBCB, aItPBN;
 948   BOPDS_DataMapIteratorOfDataMapOfPassKeyListOfPaveBlock aItMPKLPB;
 949   BOPDS_ListOfPaveBlock aLPBN;
 950   BOPDS_DataMapOfPassKeyListOfPaveBlock aMPKLPB;
 951   Handle(BOPDS_PaveBlock) aPB;
 952   Handle(BOPDS_CommonBlock) aCBx;
 953   BOPDS_PassKey aPK;
 954   //
 955   const BOPDS_ListOfPaveBlock& aLPBCB=theCB->PaveBlocks();
 956   if (!aLPBCB.First()->IsToUpdate()){
 957     return;
 958   }
 959   //
 960   const BOPCol_ListOfInteger& aLF=theCB->Faces();
 961   //
 962   BOPDS_VectorOfListOfPaveBlock& aPBP=myPaveBlocksPool;
 963   //
 964   aItPBCB.Initialize(aLPBCB);
 965   for (; aItPBCB.More(); aItPBCB.Next()) {
 966     const Handle(BOPDS_PaveBlock)& aPBCB=aItPBCB.ChangeValue();
 967     //
 968     nE=aPBCB->OriginalEdge();
 969     iRef=ChangeShapeInfo(nE).Reference();
 970     BOPDS_ListOfPaveBlock& aLPB=aPBP(iRef);
 971     //
 972     aItPB.Initialize(aLPB);
 973     for (; aItPB.More(); aItPB.Next()) {
 974       aPB=aItPB.ChangeValue();
 975       if (aPB==aPBCB) {
 976         //
 977         aLPBN.Clear();
 978         aPB->Update(aLPBN);
 979         //
 980         aItPBN.Initialize(aLPBN);
 981         for (; aItPBN.More(); aItPBN.Next()) {
 982           Handle(BOPDS_PaveBlock)& aPBN=aItPBN.ChangeValue();
 983           aLPB.Append(aPBN);
 984           //
 985           aPBN->Indices(n1, n2);
 986           aPK.SetIds(n1, n2);
 987           if (aMPKLPB.IsBound(aPK)) {
 988             BOPDS_ListOfPaveBlock& aLPBx=aMPKLPB.ChangeFind(aPK);
 989             aLPBx.Append(aPBN);
 990           }
 991           else {
 992             BOPDS_ListOfPaveBlock aLPBx;
 993             aLPBx.Append(aPBN);
 994             aMPKLPB.Bind(aPK, aLPBx);
 995           }
 996         }
 997         aLPB.Remove(aItPB);
 998         break;
 999       }
1000     }
1001   }
1002   //
1003   aItMPKLPB.Initialize(aMPKLPB);
1004   for (; aItMPKLPB.More(); aItMPKLPB.Next()) {
1005     BOPDS_ListOfPaveBlock& aLPBx=aItMPKLPB.ChangeValue();
1006     //
1007     while (aLPBx.Extent()) {
1008       Standard_Boolean bCoinside;
1009       Standard_Real aTol, aTolMax(0.);
1010       BOPDS_ListOfPaveBlock aLPBxN;
1011       //
1012       aItPB.Initialize(aLPBx);
1013       for(; aItPB.More(); ) {
1014         const Handle(BOPDS_PaveBlock)& aPBx=aItPB.Value();
1015         if (aLPBxN.Extent()) {
1016           const Handle(BOPDS_PaveBlock)& aPBCx = aLPBxN.First();
1017           bCoinside = CheckCoincidence(aPBx, aPBCx);
1018           if (bCoinside) {
1019             nE = aPBx->OriginalEdge();
1020             const TopoDS_Edge& aE = *(TopoDS_Edge*)&Shape(nE);
1021             aTol = BRep_Tool::Tolerance(aE);
1022             //
1023             //pave block with the max tolerance of the original edge
1024             //must be the first in the common block
1025             if (aTolMax < aTol) {
1026               aTolMax = aTol;
1027               aLPBxN.Prepend(aPBx);
1028             } else {
1029               aLPBxN.Append(aPBx);
1030             }
1031             aLPBx.Remove(aItPB);
1032             continue;
1033           }//if (bCoinside) {
1034         }//if (aLPBxN.Extent()) {
1035         else {
1036           nE = aPBx->OriginalEdge();
1037           const TopoDS_Edge& aE = *(TopoDS_Edge*)&Shape(nE);
1038           aTolMax = BRep_Tool::Tolerance(aE);
1039           //
1040           aLPBxN.Append(aPBx);
1041           aLPBx.Remove(aItPB);
1042           continue;
1043         }
1044         aItPB.Next();
1045       }//for(; aItPB.More(); ) {
1046       //
1047       aCBx=new BOPDS_CommonBlock;
1048       aCBx->AddPaveBlocks(aLPBxN);
1049       aCBx->AddFaces(aLF);
1050       //
1051       aItPB.Initialize(aLPBxN);
1052       for (; aItPB.More(); aItPB.Next()) {
1053         aPB=aItPB.ChangeValue();
1054         SetCommonBlock(aPB, aCBx);
1055       }
1056     }
1057   }
1058 }
1059
1060 //=======================================================================
1061 // function: RealPaveBlock
1062 // purpose:
1063 //=======================================================================
1064 Handle(BOPDS_PaveBlock) BOPDS_DS::RealPaveBlock
1065     (const Handle(BOPDS_PaveBlock)& thePB) const
1066 {
1067   if (IsCommonBlock(thePB)) {
1068     const Handle(BOPDS_CommonBlock)& aCB = CommonBlock(thePB);
1069     const Handle(BOPDS_PaveBlock)& aPB = aCB->PaveBlock1();
1070     return aPB;
1071   }
1072   return thePB;
1073 }
1074
1075 //=======================================================================
1076 // function: IsCommonBlockOnEdge
1077 // purpose:
1078 //=======================================================================
1079 Standard_Boolean BOPDS_DS::IsCommonBlockOnEdge
1080     (const Handle(BOPDS_PaveBlock)& thePB) const
1081 {
1082   if (IsCommonBlock(thePB)) {
1083     const Handle(BOPDS_CommonBlock)& aCB = CommonBlock(thePB);
1084     return aCB->PaveBlocks().Extent()>1;
1085   }
1086   return Standard_False;
1087 }
1088
1089 //=======================================================================
1090 //function : IsCommonBlock
1091 //purpose  :
1092 //=======================================================================
1093 Standard_Boolean BOPDS_DS::IsCommonBlock
1094     (const Handle(BOPDS_PaveBlock)& thePB) const
1095 {
1096   return myMapPBCB.IsBound(thePB);
1097 }
1098
1099 //=======================================================================
1100 //function : CommonBlock
1101 //purpose  :
1102 //=======================================================================
1103 const Handle(BOPDS_CommonBlock)& BOPDS_DS::CommonBlock
1104     (const Handle(BOPDS_PaveBlock)& thePB) const
1105 {
1106   Handle(BOPDS_CommonBlock) aNullCB;
1107   //
1108   const Handle(BOPDS_CommonBlock)& aCB =
1109     IsCommonBlock(thePB) ? myMapPBCB.Find(thePB) : aNullCB;
1110   //
1111   return aCB;
1112 }
1113
1114 //=======================================================================
1115 //function : SetCommonBlock
1116 //purpose  :
1117 //=======================================================================
1118 void BOPDS_DS::SetCommonBlock(const Handle(BOPDS_PaveBlock)& thePB,
1119                               const Handle(BOPDS_CommonBlock)& theCB)
1120 {
1121   if (IsCommonBlock(thePB)) {
1122     Handle(BOPDS_CommonBlock)& aCB = myMapPBCB.ChangeFind(thePB);
1123     aCB=theCB;
1124   }
1125   else {
1126     myMapPBCB.Bind(thePB, theCB);
1127   }
1128 }
1129
1130 //
1131 // FaceInfo
1132 //
1133
1134 //=======================================================================
1135 //function : FaceInfoPool
1136 //purpose  :
1137 //=======================================================================
1138 const BOPDS_VectorOfFaceInfo& BOPDS_DS::FaceInfoPool()const
1139 {
1140   return myFaceInfoPool;
1141 }
1142 //=======================================================================
1143 //function : HasFaceInfo
1144 //purpose  :
1145 //=======================================================================
1146 Standard_Boolean BOPDS_DS::HasFaceInfo(const Standard_Integer theI)const
1147 {
1148   return ShapeInfo(theI).HasReference();
1149 }
1150 //=======================================================================
1151 //function : FaceInfo
1152 //purpose  :
1153 //=======================================================================
1154 const BOPDS_FaceInfo& BOPDS_DS::FaceInfo(const Standard_Integer theI)const
1155 {
1156   static BOPDS_FaceInfo sFI;
1157   Standard_Integer aRef;
1158   //
1159   if (HasFaceInfo(theI)) {
1160     aRef=ShapeInfo(theI).Reference();
1161     const BOPDS_FaceInfo& aFI=myFaceInfoPool(aRef);
1162     return aFI;
1163   }
1164   return sFI;
1165 }
1166 //=======================================================================
1167 //function : ChangeFaceInfo
1168 //purpose  :
1169 //=======================================================================
1170 BOPDS_FaceInfo& BOPDS_DS::ChangeFaceInfo(const Standard_Integer theI)
1171 {
1172   Standard_Boolean bHasReference;
1173   Standard_Integer aRef;
1174   BOPDS_FaceInfo* pFI;
1175   //
1176   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1177   bHasReference=aSI.HasReference();
1178   if (!bHasReference) {
1179     InitFaceInfo(theI);
1180   }
1181   //
1182   aRef=aSI.Reference();
1183   const BOPDS_FaceInfo& aFI=myFaceInfoPool(aRef);
1184   pFI=(BOPDS_FaceInfo*)&aFI;
1185   return *pFI;
1186 }
1187 //=======================================================================
1188 //function : InitFaceInfo
1189 //purpose  :
1190 //=======================================================================
1191 void BOPDS_DS::InitFaceInfo(const Standard_Integer theI)
1192 {
1193   Standard_Integer iRef;
1194   //
1195   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1196   iRef=myFaceInfoPool.Append()-1;
1197   BOPDS_FaceInfo &aFI=myFaceInfoPool(iRef);
1198   aSI.SetReference(iRef);
1199   //
1200   aFI.SetIndex(theI);
1201   UpdateFaceInfoIn(theI);
1202   UpdateFaceInfoOn(theI);
1203 }
1204 //=======================================================================
1205 //function : UpdateFaceInfoIn
1206 //purpose  :
1207 //=======================================================================
1208 void BOPDS_DS::UpdateFaceInfoIn(const Standard_Integer theI)
1209 {
1210   Standard_Integer iRef;
1211   //
1212   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1213   if (aSI.HasReference()) {
1214     iRef=aSI.Reference();
1215     BOPDS_FaceInfo &aFI=myFaceInfoPool(iRef);
1216     //
1217     BOPDS_IndexedMapOfPaveBlock& aMPBIn=aFI.ChangePaveBlocksIn();
1218     BOPCol_MapOfInteger& aMVIn=aFI.ChangeVerticesIn();
1219     aMPBIn.Clear();
1220     aMVIn.Clear();
1221     FaceInfoIn(theI, aMPBIn, aMVIn);
1222   }
1223 }
1224 //=======================================================================
1225 //function : UpdateFaceInfoOn
1226 //purpose  :
1227 //=======================================================================
1228 void BOPDS_DS::UpdateFaceInfoOn(const Standard_Integer theI)
1229 {
1230   Standard_Integer iRef;
1231   //
1232   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1233   if (aSI.HasReference()) {
1234     iRef=aSI.Reference();
1235     BOPDS_FaceInfo &aFI=myFaceInfoPool(iRef);
1236     //
1237     BOPDS_IndexedMapOfPaveBlock& aMPBOn=aFI.ChangePaveBlocksOn();
1238     BOPCol_MapOfInteger& aMVOn=aFI.ChangeVerticesOn();
1239     aMPBOn.Clear();
1240     aMVOn.Clear();
1241     FaceInfoOn(theI, aMPBOn, aMVOn);
1242   }
1243 }
1244 //=======================================================================
1245 //function : FaceInfoOn
1246 //purpose  :
1247 //=======================================================================
1248 void BOPDS_DS::FaceInfoOn(const Standard_Integer theF,
1249                           BOPDS_IndexedMapOfPaveBlock& theMPB,
1250                           BOPCol_MapOfInteger& theMI)
1251 {
1252   Standard_Integer nS, nSD, nV1, nV2;
1253   BOPCol_ListIteratorOfListOfInteger aIt;
1254   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
1255   //
1256   const BOPDS_ShapeInfo& aSI=ShapeInfo(theF);
1257   const BOPCol_ListOfInteger& aLI=aSI.SubShapes();
1258   aIt.Initialize(aLI);
1259   for (; aIt.More(); aIt.Next()) {
1260     nS=aIt.Value();
1261     const BOPDS_ShapeInfo& aSIE=ShapeInfo(nS);
1262     if (aSIE.ShapeType()==TopAbs_EDGE) {
1263       const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nS);
1264       aItPB.Initialize(aLPB);
1265       for (; aItPB.More(); aItPB.Next()) {
1266         const Handle(BOPDS_PaveBlock)& aPB=aItPB.Value();
1267         aPB->Indices(nV1, nV2);
1268         theMI.Add(nV1);
1269         theMI.Add(nV2);
1270         Handle(BOPDS_PaveBlock) aPBR=RealPaveBlock(aPB);
1271         theMPB.Add(aPBR);
1272       }
1273     }//if (aSIE.ShapeType()==TopAbs_EDGE)
1274     else {
1275       // nE is TopAbs_VERTEX
1276       if (HasShapeSD(nS, nSD)) {
1277         nS=nSD;
1278       }
1279       theMI.Add(nS);
1280     }
1281   }
1282 }
1283 //=======================================================================
1284 //function : FaceInfoIn
1285 //purpose  :
1286 //=======================================================================
1287 void BOPDS_DS::FaceInfoIn(const Standard_Integer theF,
1288                           BOPDS_IndexedMapOfPaveBlock& theMPB,
1289                           BOPCol_MapOfInteger& theMI)
1290 {
1291   Standard_Integer i, aNbVF, aNbEF, nV, nE, nVSD;
1292   TopoDS_Iterator aItS;
1293   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
1294   //
1295   // 1. Pure internal vertices on the face
1296   const TopoDS_Shape& aF=Shape(theF);
1297   aItS.Initialize(aF);
1298   for (; aItS.More(); aItS.Next()) {
1299     const TopoDS_Shape& aSx=aItS.Value();
1300     if (aSx.ShapeType()==TopAbs_VERTEX){
1301       nV=Index(aSx);
1302       if (HasShapeSD(nV, nVSD)) {
1303  nV=nVSD;
1304       }
1305       theMI.Add(nV);
1306     }
1307   }
1308   //
1309   // 2. aVFs
1310   BOPDS_VectorOfInterfVF& aVFs=InterfVF();
1311   aNbVF=aVFs.Extent();
1312   for (i=0; i<aNbVF; ++i) {
1313     BOPDS_InterfVF& aVF=aVFs(i);
1314     if(aVF.Contains(theF)) {
1315       nV=aVF.OppositeIndex(theF);
1316       theMI.Add(nV);
1317     }
1318   }
1319   //
1320   // 3. aEFs
1321   BOPDS_VectorOfInterfEF& aEFs=InterfEF();
1322   aNbEF=aEFs.Extent();
1323   for (i=0; i<aNbEF; ++i) {
1324     BOPDS_InterfEF& aEF=aEFs(i);
1325     if(aEF.Contains(theF)) {
1326       if(aEF.HasIndexNew(nV)) {
1327         theMI.Add(nV);
1328       }
1329       else {
1330         nE=aEF.OppositeIndex(theF);
1331         const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nE);
1332         aItPB.Initialize(aLPB);
1333         for (; aItPB.More(); aItPB.Next()) {
1334           const Handle(BOPDS_PaveBlock)& aPB=aItPB.Value();
1335           if (IsCommonBlock(aPB)) {
1336             const Handle(BOPDS_CommonBlock)& aCB=CommonBlock(aPB);
1337             if (aCB->Contains(theF)) {
1338               const Handle(BOPDS_PaveBlock)& aPB1=aCB->PaveBlock1();
1339               theMPB.Add(aPB1);
1340             }
1341           }
1342         }// for (; aItPB.More(); aItPB.Next()) {
1343       }// else {
1344     }// if(aEF.Contains(theF)) {
1345   }// for (i=0; i<aNbEF; ++i) {
1346 }
1347
1348 //=======================================================================
1349 //function : RefineFaceInfoOn
1350 //purpose  :
1351 //=======================================================================
1352 void BOPDS_DS::RefineFaceInfoOn()
1353 {
1354   Standard_Integer i, aNb, nF, aNbPB, j;
1355   BOPDS_IndexedMapOfPaveBlock aMPB;
1356   //
1357   aNb=myFaceInfoPool.Extent();
1358   for (i=0; i<aNb; ++i) {
1359     BOPDS_FaceInfo &aFI=myFaceInfoPool(i);
1360     nF=aFI.Index();
1361     UpdateFaceInfoOn(nF);
1362     BOPDS_IndexedMapOfPaveBlock& aMPBOn=aFI.ChangePaveBlocksOn();
1363     //
1364     aMPB.Clear();
1365     aMPB.Assign(aMPBOn);
1366     aMPBOn.Clear();
1367     //
1368     aNbPB=aMPB.Extent();
1369     for (j=1; j<=aNbPB; ++j) {
1370       const Handle(BOPDS_PaveBlock)& aPB=aMPB(j);
1371       if (aPB->HasEdge()) {
1372         aMPBOn.Add(aPB);
1373       }
1374     }
1375   }
1376 }
1377 //=======================================================================
1378 //function : AloneVertices
1379 //purpose  :
1380 //=======================================================================
1381 void BOPDS_DS::AloneVertices(const Standard_Integer theI,
1382                              BOPCol_ListOfInteger& theLI)const
1383 {
1384   if (HasFaceInfo(theI)) {
1385     //
1386     Standard_Integer i, nV1, nV2, nV;
1387     BOPDS_MapIteratorOfMapOfPaveBlock aItMPB;
1388     BOPCol_MapIteratorOfMapOfInteger aItMI;
1389     //
1390     BOPCol_MapOfInteger aMI(100, myAllocator);
1391     //
1392     const BOPDS_FaceInfo& aFI=FaceInfo(theI);
1393     //
1394     for (i=0; i<2; ++i) {
1395       const BOPDS_IndexedMapOfPaveBlock& aMPB=
1396         (!i) ? aFI.PaveBlocksIn() : aFI.PaveBlocksSc();
1397       aItMPB.Initialize(aMPB);
1398       for (; aItMPB.More(); aItMPB.Next()) {
1399         const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
1400         aPB->Indices(nV1, nV2);
1401         aMI.Add(nV1);
1402         aMI.Add(nV2);
1403       }
1404     }
1405     //
1406     for (i=0; i<2; ++i) {
1407       const BOPCol_MapOfInteger& aMIV=
1408         (!i) ? aFI.VerticesIn() : aFI.VerticesSc();
1409       aItMI.Initialize(aMIV);
1410       for (; aItMI.More(); aItMI.Next()) {
1411         nV=aItMI.Value();
1412         if (nV>=0) {
1413           if (aMI.Add(nV)) {
1414             theLI.Append(nV);
1415           }
1416         }
1417       }
1418     }
1419   }
1420 }
1421 //=======================================================================
1422 //function : VerticesOnIn
1423 //purpose  :
1424 //=======================================================================
1425 void BOPDS_DS::VerticesOnIn
1426   (const Standard_Integer nF1,
1427    const Standard_Integer nF2,
1428    BOPCol_MapOfInteger& aMI,
1429    BOPDS_MapOfPaveBlock& aMPB)const
1430 {
1431   Standard_Integer i, nV, nV1, nV2;
1432   BOPCol_MapIteratorOfMapOfInteger aIt;
1433   BOPDS_IndexedMapOfPaveBlock* pMPB[4];
1434   BOPDS_MapIteratorOfMapOfPaveBlock aItMPB;
1435   //
1436   const BOPDS_FaceInfo& aFI1=FaceInfo(nF1);
1437   const BOPDS_FaceInfo& aFI2=FaceInfo(nF2);
1438   //
1439   pMPB[0]=(BOPDS_IndexedMapOfPaveBlock*)&aFI1.PaveBlocksOn();
1440   pMPB[1]=(BOPDS_IndexedMapOfPaveBlock*)&aFI1.PaveBlocksIn();
1441   pMPB[2]=(BOPDS_IndexedMapOfPaveBlock*)&aFI2.PaveBlocksOn();
1442   pMPB[3]=(BOPDS_IndexedMapOfPaveBlock*)&aFI2.PaveBlocksIn();
1443   //
1444   for (i=0; i<4; ++i) {
1445     aItMPB.Initialize(*pMPB[i]);
1446     for (; aItMPB.More(); aItMPB.Next()) {
1447       const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
1448       aMPB.Add(aPB);
1449       aPB->Indices(nV1, nV2);
1450       aMI.Add(nV1);
1451       aMI.Add(nV2);
1452     }
1453   }
1454   //
1455   const BOPCol_MapOfInteger& aMVOn1=aFI1.VerticesOn();
1456   const BOPCol_MapOfInteger& aMVIn1=aFI1.VerticesIn();
1457   const BOPCol_MapOfInteger& aMVOn2=aFI2.VerticesOn();
1458   const BOPCol_MapOfInteger& aMVIn2=aFI2.VerticesIn();
1459   //
1460   for (i=0; i<2; ++i) {
1461     const BOPCol_MapOfInteger& aMV1=(!i) ? aMVOn1 : aMVIn1;
1462     aIt.Initialize(aMV1);
1463     for (; aIt.More(); aIt.Next()) {
1464       nV=aIt.Value();
1465       if (aMVOn2.Contains(nV) || aMVIn2.Contains(nV)) {
1466  aMI.Add(nV);
1467       }
1468     }
1469   }
1470 }
1471 //=======================================================================
1472 //function : SharedEdges
1473 //purpose  :
1474 //=======================================================================
1475 void BOPDS_DS::SharedEdges(const Standard_Integer nF1,
1476       const Standard_Integer nF2,
1477       BOPCol_ListOfInteger& theLI,
1478       const Handle(NCollection_BaseAllocator)& aAllocator)
1479 {
1480   Standard_Integer nE, nSp;
1481   BOPCol_ListIteratorOfListOfInteger aItLI;
1482   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
1483   BOPCol_MapOfInteger aMI(100, aAllocator);
1484   //
1485   const BOPDS_ShapeInfo& aSI1=ShapeInfo(nF1);
1486   const BOPCol_ListOfInteger& aLI1=aSI1.SubShapes();
1487   aItLI.Initialize(aLI1);
1488   for (; aItLI.More(); aItLI.Next()) {
1489     nE=aItLI.Value();
1490     const BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
1491     if(aSIE.ShapeType()==TopAbs_EDGE) {
1492       const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nE);
1493       if (aLPB.IsEmpty()) {
1494         aMI.Add(nE);
1495       }
1496       else {
1497         aItLPB.Initialize(aLPB);
1498         for (; aItLPB.More(); aItLPB.Next()) {
1499           const Handle(BOPDS_PaveBlock) aPB=RealPaveBlock(aItLPB.Value());
1500           nSp=aPB->Edge();
1501           aMI.Add(nSp);
1502         }
1503       }
1504     }
1505   }
1506   //
1507   const BOPDS_ShapeInfo& aSI2=ShapeInfo(nF2);
1508   const BOPCol_ListOfInteger& aLI2=aSI2.SubShapes();
1509   aItLI.Initialize(aLI2);
1510   for (; aItLI.More(); aItLI.Next()) {
1511     nE=aItLI.Value();
1512     const BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
1513     if(aSIE.ShapeType()==TopAbs_EDGE) {
1514       const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nE);
1515       if (aLPB.IsEmpty()) {
1516         if (aMI.Contains(nE)) {
1517           theLI.Append(nE);
1518         }
1519       }
1520       else {
1521         aItLPB.Initialize(aLPB);
1522         for (; aItLPB.More(); aItLPB.Next()) {
1523           const Handle(BOPDS_PaveBlock) aPB=RealPaveBlock(aItLPB.Value());
1524           nSp=aPB->Edge();
1525           if (aMI.Contains(nSp)) {
1526             theLI.Append(nSp);
1527           }
1528         }
1529       }
1530     }
1531   }
1532 }
1533
1534 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1535 //
1536 // same domain shapes
1537 //
1538 //=======================================================================
1539 //function : ShapesSD
1540 //purpose  :
1541 //=======================================================================
1542 BOPCol_DataMapOfIntegerInteger& BOPDS_DS::ShapesSD()
1543 {
1544   return myShapesSD;
1545 }
1546 //=======================================================================
1547 //function : AddShapeSD
1548 //purpose  :
1549 //=======================================================================
1550 void BOPDS_DS::AddShapeSD(const Standard_Integer theIndex,
1551                           const Standard_Integer theIndexSD)
1552 {
1553   myShapesSD.Bind(theIndex, theIndexSD);
1554 }
1555 //=======================================================================
1556 //function : HasShapeSD
1557 //purpose  :
1558 //=======================================================================
1559 Standard_Boolean BOPDS_DS::HasShapeSD
1560   (const Standard_Integer theIndex,
1561    Standard_Integer& theIndexSD)const
1562 {
1563   Standard_Boolean bRet;
1564   //
1565   bRet=myShapesSD.IsBound(theIndex);
1566   if (bRet) {
1567    theIndexSD=myShapesSD.Find(theIndex);
1568   }
1569   return bRet;
1570 }
1571 //=======================================================================
1572 //function : Dump
1573 //purpose  :
1574 //=======================================================================
1575 void BOPDS_DS::Dump()const
1576 {
1577   Standard_Integer i, aNb, aNbSS;
1578   //
1579   printf(" *** DS ***\n");
1580   aNb=NbRanges();
1581   printf(" Ranges:%d\n", aNb);
1582   for (i=0; i<aNb; ++i) {
1583     const BOPDS_IndexRange& aR=Range(i);
1584     aR.Dump();
1585     printf("\n");
1586   }
1587   //
1588   aNbSS=NbSourceShapes();
1589   printf(" Shapes:%d\n", aNbSS);
1590   aNb=NbShapes();
1591   for (i=0; i<aNb; ++i) {
1592     const BOPDS_ShapeInfo& aSI=ShapeInfo(i);
1593     printf(" %d :", i);
1594     aSI.Dump();
1595     printf("\n");
1596     if (i==aNbSS-1) {
1597       printf(" ****** adds\n");
1598     }
1599   }
1600   printf(" ******\n");
1601 }
1602
1603 //=======================================================================
1604 // function: CheckCoincidence
1605 // purpose:
1606 //=======================================================================
1607 Standard_Boolean BOPDS_DS::CheckCoincidence
1608   (const Handle(BOPDS_PaveBlock)& aPB1,
1609    const Handle(BOPDS_PaveBlock)& aPB2)
1610 {
1611   Standard_Boolean bRet;
1612   Standard_Integer nE1, nE2, aNbPoints;
1613   Standard_Real aT11, aT12, aT21, aT22, aT1m, aD, aTol, aT2x;
1614   gp_Pnt aP1m;
1615   //
1616   bRet=Standard_False;
1617   //
1618   aPB1->Range(aT11, aT12);
1619   aT1m=IntTools_Tools::IntermediatePoint (aT11, aT12);
1620   nE1=aPB1->OriginalEdge();
1621   const TopoDS_Edge& aE1=(*(TopoDS_Edge*)(&Shape(nE1)));
1622   BOPTools_AlgoTools::PointOnEdge(aE1, aT1m, aP1m);
1623   //
1624   aPB2->Range(aT21, aT22);
1625   nE2=aPB2->OriginalEdge();
1626   const TopoDS_Edge& aE2=(*(TopoDS_Edge*)(&Shape(nE2)));
1627   //
1628   Standard_Real f, l;
1629   Handle(Geom_Curve)aC2 = BRep_Tool::Curve (aE2, f, l);
1630   GeomAPI_ProjectPointOnCurve aPPC;
1631   aPPC.Init(aC2, f, l);
1632   aPPC.Perform(aP1m);
1633   aNbPoints=aPPC.NbPoints();
1634   if (aNbPoints) {
1635     aD=aPPC.LowerDistance();
1636     //
1637     aTol=BRep_Tool::Tolerance(aE1);
1638     aTol=aTol+BRep_Tool::Tolerance(aE2);
1639     if (aD<aTol) {
1640       aT2x=aPPC.LowerDistanceParameter();
1641       if (aT2x>aT21 && aT2x<aT22) {
1642         return !bRet;
1643       }
1644     }
1645   }
1646   return bRet;
1647 }
1648 //=======================================================================
1649 // function: SortPaveBlocks
1650 // purpose:
1651 //=======================================================================
1652 void BOPDS_DS::SortPaveBlocks(const Handle(BOPDS_CommonBlock)& aCB)
1653 {
1654   Standard_Integer theI;
1655   Standard_Boolean bToSort;
1656   bToSort = IsToSort(aCB, theI);
1657   if (!bToSort) {
1658     return;
1659   }
1660
1661   Standard_Integer i(0);
1662   const BOPDS_ListOfPaveBlock& aLPB = aCB->PaveBlocks();
1663   BOPDS_ListOfPaveBlock aLPBN = aLPB;
1664
1665   Handle(BOPDS_PaveBlock) aPB;
1666   BOPDS_ListIteratorOfListOfPaveBlock aIt;
1667   //
1668   aIt.Initialize(aLPBN);
1669   for (aIt.Next(); aIt.More(); ) {
1670     i++;
1671     if(i == theI) {
1672       aPB = aIt.Value();
1673       aLPBN.Remove(aIt);
1674       aLPBN.Prepend(aPB);
1675       break;
1676     }
1677     aIt.Next();
1678   }
1679   //
1680   aCB->AddPaveBlocks(aLPBN);
1681 }
1682 //=======================================================================
1683 // function: IsToSort
1684 // purpose:
1685 //=======================================================================
1686 Standard_Boolean BOPDS_DS::IsToSort
1687   (const Handle(BOPDS_CommonBlock)& aCB,
1688    Standard_Integer& theI)
1689 {
1690   Standard_Boolean bRet;
1691   bRet = Standard_False;
1692   const BOPDS_ListOfPaveBlock& aLPB = aCB->PaveBlocks();
1693   if (aLPB.Extent()==1) {
1694     return bRet;
1695   }
1696
1697   Standard_Integer nE;
1698   Standard_Real aTolMax, aTol;
1699   Handle(BOPDS_PaveBlock) aPB;
1700   TopoDS_Edge aE;
1701   BOPDS_ListIteratorOfListOfPaveBlock aIt;
1702   //
1703   aPB = aLPB.First();
1704   nE = aPB->OriginalEdge();
1705   aE = (*(TopoDS_Edge *)(&Shape(nE)));
1706   aTolMax = BRep_Tool::Tolerance(aE);
1707   //
1708   theI = 0;
1709   aIt.Initialize(aLPB);
1710   for (aIt.Next(); aIt.More(); aIt.Next()) {
1711     theI++;
1712     aPB = aIt.Value();
1713     nE = aPB->OriginalEdge();
1714     aE = (*(TopoDS_Edge *)(&Shape(nE)));
1715     aTol = BRep_Tool::Tolerance(aE);
1716     if (aTolMax < aTol) {
1717       aTolMax = aTol;
1718       bRet = Standard_True;
1719     }
1720   }
1721
1722   return bRet;
1723 }
1724 //=======================================================================
1725 // function: IsSubShape
1726 // purpose:
1727 //=======================================================================
1728 Standard_Boolean BOPDS_DS::IsSubShape
1729   (const Standard_Integer theI1,
1730    const Standard_Integer theI2)
1731 {
1732   Standard_Boolean bRet;
1733   Standard_Integer nS;
1734   bRet = Standard_False;
1735   //
1736   BOPCol_ListIteratorOfListOfInteger aItLI;
1737   //
1738   const BOPDS_ShapeInfo& aSI = ShapeInfo(theI2);
1739   const BOPCol_ListOfInteger& aLI = aSI.SubShapes();
1740   aItLI.Initialize(aLI);
1741   for(;aItLI.More(); aItLI.Next()) {
1742     nS = aItLI.Value();
1743     if (nS == theI1) {
1744       bRet = Standard_True;
1745       break;
1746     }
1747   }
1748
1749   return bRet;
1750 }
1751
1752 //=======================================================================
1753 // function: Paves
1754 // purpose:
1755 //=======================================================================
1756 void BOPDS_DS::Paves(const Standard_Integer theEdge,
1757                      BOPDS_ListOfPave& theLP)
1758 {
1759   Standard_Integer aNb, i;
1760   BOPDS_Pave *pPaves;
1761   BOPDS_ListIteratorOfListOfPaveBlock aIt;
1762   BOPDS_MapOfPave aMP;
1763   //
1764   const BOPDS_ListOfPaveBlock& aLPB = PaveBlocks(theEdge);
1765   aNb = aLPB.Extent();
1766   aNb = (aNb==0) ? 0 : (aNb+1);
1767   //
1768   pPaves=(BOPDS_Pave *)myAllocator->Allocate(aNb*sizeof(BOPDS_Pave));
1769   for (i=0; i<aNb; ++i) {
1770     new (pPaves+i) BOPDS_Pave();
1771   }
1772   //
1773   i = 0;
1774   for (aIt.Initialize(aLPB); aIt.More(); aIt.Next()) {
1775     const Handle(BOPDS_PaveBlock)& aPB = aIt.Value();
1776     if (aMP.Add(aPB->Pave1())){
1777       pPaves[i] = aPB->Pave1();
1778       ++i;
1779     }
1780     if (aMP.Add(aPB->Pave2())){
1781       pPaves[i] = aPB->Pave2();
1782       ++i;
1783     }
1784   }
1785   //
1786   SortShell(aNb, pPaves);
1787   //
1788   for (i = 0; i < aNb; ++i) {
1789     theLP.Append(pPaves[i]);
1790   }
1791 }
1792
1793 //=======================================================================
1794 // function: UpdateTolerance
1795 // purpose:
1796 //=======================================================================
1797 void BOPDS_DS::UpdateEdgeTolerance(const Standard_Integer nE,
1798                                    const Standard_Real aTol)
1799 {
1800   Standard_Integer nV;
1801   Standard_Real aTolV;
1802   BRep_Builder aBB;
1803   BOPCol_ListIteratorOfListOfInteger aIt;
1804   //
1805   const TopoDS_Edge& aE = *(TopoDS_Edge*)&Shape(nE);
1806   aBB.UpdateEdge(aE, aTol);
1807   BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
1808   Bnd_Box& aBoxE=aSIE.ChangeBox();
1809   BRepBndLib::Add(aE, aBoxE);
1810   //
1811   const BOPCol_ListOfInteger& aLI = aSIE.SubShapes();
1812   aIt.Initialize(aLI);
1813   for (; aIt.More(); aIt.Next()) {
1814     nV = aIt.Value();
1815     const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&Shape(nV);
1816     aTolV = BRep_Tool::Tolerance(aV);
1817     if (aTolV < aTol) {
1818       aBB.UpdateVertex(aV, aTol);
1819       BOPDS_ShapeInfo& aSIV = ChangeShapeInfo(nV);
1820       Bnd_Box& aBoxV = aSIV.ChangeBox();
1821       BRepBndLib::Add(aV, aBoxV);
1822     }
1823   }
1824 }
1825
1826 //=======================================================================
1827 //function : TotalShapes
1828 //purpose  :
1829 //=======================================================================
1830 void TotalShapes(const TopoDS_Shape& aS,
1831                  Standard_Integer& aNbS)
1832 {
1833   TopoDS_Shape *pS;
1834   //
1835   pS=(TopoDS_Shape *)&aS;
1836   if (!pS->Checked()) {
1837     TopoDS_Iterator aIt;
1838     //
1839     pS->Checked(1);
1840     ++aNbS;
1841     aIt.Initialize(aS);
1842     for (; aIt.More(); aIt.Next()) {
1843       const TopoDS_Shape& aSx=aIt.Value();
1844       TotalShapes(aSx, aNbS);
1845     }
1846   }
1847 }
1848 //=======================================================================
1849 //function : ResetShape
1850 //purpose  :
1851 //=======================================================================
1852 void ResetShape(const TopoDS_Shape& aS)
1853 {
1854   TopoDS_Shape *pS;
1855   //
1856   pS=(TopoDS_Shape *)&aS;
1857   pS->Checked(0);
1858 }
1859 //=======================================================================
1860 //function : ResetShape
1861 //purpose  :
1862 //=======================================================================
1863 void ResetShapes(const TopoDS_Shape& aS)
1864 {
1865   TopoDS_Iterator aIt;
1866   //
1867   ResetShape(aS);
1868   aIt.Initialize(aS);
1869   for (; aIt.More(); aIt.Next()) {
1870     const TopoDS_Shape& aSx=aIt.Value();
1871     ResetShape(aSx);
1872   }
1873 }
1874 //=======================================================================
1875 //function : ComputeParameter
1876 //purpose  :
1877 //=======================================================================
1878 Standard_Real ComputeParameter(const TopoDS_Vertex& aV,
1879                                const TopoDS_Edge& aE)
1880 {
1881   Standard_Real aT1, aT2, aTRet, aTolE2, aD2;
1882   gp_Pnt aPC, aPV;
1883   Handle(Geom_Curve) aC3D;
1884   TopoDS_Edge aEE;
1885   //
1886   aEE=aE;
1887   aEE.Orientation(TopAbs_FORWARD);
1888   //
1889   aTRet=0.;
1890   //
1891   aTolE2=BRep_Tool::Tolerance(aE);
1892   aTolE2=aTolE2*aTolE2;
1893   //
1894   aPV=BRep_Tool::Pnt(aV);
1895   //
1896   aC3D=BRep_Tool::Curve (aEE, aT1, aT2);
1897   //
1898   aC3D->D0(aT1, aPC);
1899   aD2=aPC.SquareDistance(aPV);
1900   if (aD2<aTolE2) {
1901     aTRet=aT1;
1902   }
1903   //
1904   aC3D->D0(aT2, aPC);
1905   aD2=aPC.SquareDistance(aPV);
1906   if (aD2<aTolE2) {
1907     aTRet=aT2;
1908   }
1909   //
1910   return aTRet;
1911 }
1912 //=======================================================================
1913 // function: SortShell
1914 // purpose :
1915 //=======================================================================
1916 void SortShell(const int n, BOPDS_Pave *a)
1917 {
1918   int nd, i, j, l, d=1;
1919   BOPDS_Pave x;
1920   //
1921   while(d<=n) {
1922     d*=2;
1923   }
1924   //
1925   while (d) {
1926     d=(d-1)/2;
1927     //
1928     nd=n-d;
1929     for (i=0; i<nd; ++i) {
1930       j=i;
1931     m30:;
1932       l=j+d;
1933       if (a[l] < a[j]){
1934         x=a[j];
1935         a[j]=a[l];
1936         a[l]=x;
1937         j-=d;
1938         if (j > -1) goto m30;
1939       }//if (a[l] < a[j]){
1940     }//for (i=0; i<nd; ++i)
1941   }//while (1)
1942 }
1943 //=======================================================================
1944 //function : BuildBndBoxSolid
1945 //purpose  :
1946 //=======================================================================
1947 void BOPDS_DS::BuildBndBoxSolid(const Standard_Integer theIndex,
1948                                 Bnd_Box& aBoxS)
1949 {
1950   Standard_Boolean bIsOpenBox, bIsInverted;
1951   Standard_Integer nSh, nFc;
1952   Standard_Real aTolS, aTolFc;
1953   BOPCol_ListIteratorOfListOfInteger aItLI, aItLI1;
1954   //
1955   const BOPDS_ShapeInfo& aSI=ShapeInfo(theIndex);
1956   const TopoDS_Shape& aS=aSI.Shape();
1957   const TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aS));
1958   //
1959   bIsOpenBox=Standard_False;
1960   //
1961   aTolS=0.;
1962   const BOPCol_ListOfInteger& aLISh=aSI.SubShapes();
1963   aItLI.Initialize(aLISh);
1964   for (; aItLI.More(); aItLI.Next()) {
1965     nSh=aItLI.Value();
1966     const BOPDS_ShapeInfo& aSISh=ShapeInfo(nSh);
1967     if (aSISh.ShapeType()!=TopAbs_SHELL) {
1968       continue;
1969     }
1970     //
1971     const BOPCol_ListOfInteger& aLIFc=aSISh.SubShapes();
1972     aItLI1.Initialize(aLIFc);
1973     for (; aItLI1.More(); aItLI1.Next()) {
1974       nFc=aItLI1.Value();
1975       const BOPDS_ShapeInfo& aSIFc=ShapeInfo(nFc);
1976       if (aSIFc.ShapeType()!=TopAbs_FACE) {
1977         continue;
1978       }
1979       //
1980       const Bnd_Box& aBFc=aSIFc.Box();
1981       aBoxS.Add(aBFc);
1982       //
1983       if (!bIsOpenBox) {
1984         bIsOpenBox=(aBFc.IsOpenXmin() || aBFc.IsOpenXmax() ||
1985                     aBFc.IsOpenYmin() || aBFc.IsOpenYmax() ||
1986                     aBFc.IsOpenZmin() || aBFc.IsOpenZmax());
1987         if (bIsOpenBox) {
1988           break;
1989         }
1990       }
1991       //
1992       const TopoDS_Face& aFc=*((TopoDS_Face*)&aSIFc.Shape());
1993       aTolFc=BRep_Tool::Tolerance(aFc);
1994       if (aTolFc>aTolS) {
1995         aTolS=aTolFc;
1996       }
1997     }//for (; aItLI1.More(); aItLI1.Next()) {
1998     if (bIsOpenBox) {
1999       break;
2000     }
2001     //
2002     const TopoDS_Shell& aSh=*((TopoDS_Shell*)&aSISh.Shape());
2003     bIsOpenBox=BOPTools_AlgoTools::IsOpenShell(aSh);
2004     if (bIsOpenBox) {
2005       break;
2006     }
2007   }//for (; aItLI.More(); aItLI.Next()) {
2008   //
2009   if (bIsOpenBox) {
2010     aBoxS.SetWhole();
2011   }
2012   else {
2013     bIsInverted=BOPTools_AlgoTools::IsInvertedSolid(aSolid);
2014     if (bIsInverted) {
2015       aBoxS.SetWhole();
2016     }
2017   }
2018 }