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