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