src/BRepOffset/BRepOffset_MakeOffset_1.cxx

   1 // Created on: 2016
   2 // Created by: Eugeny MALTCHIKOV
   3 // Copyright (c) 2016 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16
  17 // This is the implementation of the extension of the 3D offset algorithm
  18 // to work in mode Complete and Join Type Intersection.
  19 // Currently only the Planar cases are supported.
  20
  21
  22 #include <BRepOffset_MakeOffset.hxx>
  23
  24 #include <Precision.hxx>
  25 #include <TopoDS.hxx>
  26
  27 #include <BRepAlgo_AsDes.hxx>
  28 #include <BRepAlgo_Image.hxx>
  29
  30 #include <BRep_Builder.hxx>
  31 #include <BRep_Tool.hxx>
  32
  33 #include <BRepTools.hxx>
  34
  35 #include <BRepAdaptor_Curve.hxx>
  36
  37 #include <TopExp.hxx>
  38 #include <TopExp_Explorer.hxx>
  39
  40 #include <TopTools_DataMapOfShapeInteger.hxx>
  41
  42 #include <BRepOffset_Tool.hxx>
  43
  44 #include <BRepClass3d_SolidClassifier.hxx>
  45
  46 #include <BOPDS_DS.hxx>
  47
  48 #include <BOPAlgo_PaveFiller.hxx>
  49 #include <BOPAlgo_Builder.hxx>
  50 #include <BOPAlgo_Section.hxx>
  51 #include <BOPAlgo_MakerVolume.hxx>
  52 #include <BOPAlgo_BuilderFace.hxx>
  53
  54 #include <BOPCol_ListOfShape.hxx>
  55 #include <BOPCol_DataMapOfShapeShape.hxx>
  56 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
  57
  58 #include <BOPTools.hxx>
  59 #include <BOPTools_AlgoTools3D.hxx>
  60 #include <BOPTools_AlgoTools.hxx>
  61 #include <BOPTools_AlgoTools2D.hxx>
  62
  63 #include <IntTools_Context.hxx>
  64 #include <IntTools_ShrunkRange.hxx>
  65
  66 typedef NCollection_DataMap
  67   <TopoDS_Shape, TopTools_MapOfShape, TopTools_ShapeMapHasher> BRepOffset_DataMapOfShapeMapOfShape;
  68
  69 static
  70   void IntersectTrimmedEdges(const TopTools_ListOfShape& theLF,
  71                              const Handle(BRepAlgo_AsDes)& theAsDes,
  72                              TopTools_DataMapOfShapeListOfShape& theOEImages,
  73                              TopTools_DataMapOfShapeListOfShape& theOEOrigins,
  74                              TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
  75                              Handle(IntTools_Context)& theCtx,
  76                              TopTools_MapOfShape& theNewEdges,
  77                              TopTools_DataMapOfShapeShape& theETrimEInf);
  78
  79 static
  80   Standard_Boolean GetEdges(const TopoDS_Face& theFace,
  81                             const Handle(BRepAlgo_AsDes)& theAsDes,
  82                             const TopTools_DataMapOfShapeListOfShape& theEImages,
  83                             const TopTools_MapOfShape& theLastInvEdges,
  84                             const TopTools_IndexedMapOfShape& theInvEdges,
  85                             Handle(IntTools_Context)& theCtx,
  86                             const TopTools_MapOfShape& theModifiedEdges,
  87                             TopoDS_Shape& theEdges,
  88                             TopTools_IndexedMapOfShape& theInv);
  89
  90 static
  91   void BuildSplitsOfTrimmedFace(const TopoDS_Face& theFace,
  92                                 const TopoDS_Shape& theEdges,
  93                                 TopTools_ListOfShape& theLFImages);
  94
  95 static
  96   void BuildSplitsOfFace(const TopoDS_Face& theFace,
  97                          const TopoDS_Shape& theEdges,
  98                          TopTools_DataMapOfShapeShape& theOrigins,
  99                          TopTools_ListOfShape& theLFImages);
 100
 101 static
 102   void BuildSplitsOfFaces(const TopTools_ListOfShape& theLF,
 103                           const TopTools_MapOfShape& theModifiedEdges,
 104                           const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 105                           Handle(BRepAlgo_AsDes)& theAsDes,
 106                           TopTools_DataMapOfShapeShape& theFacesOrigins,
 107                           TopTools_DataMapOfShapeListOfShape& theOEImages,
 108                           TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 109                           TopTools_MapOfShape& theLastInvEdges,
 110                           TopTools_IndexedMapOfShape& theEdgesToAvoid,
 111                           TopTools_IndexedMapOfShape& theInvEdges,
 112                           TopTools_IndexedMapOfShape& theValidEdges,
 113                           TopTools_MapOfShape& theInvertedEdges,
 114                           TopTools_DataMapOfShapeInteger& theAlreadyInvFaces,
 115                           TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 116                           TopTools_DataMapOfShapeShape& theArtInvFaces,
 117                           TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 118                           TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
 119                           TopoDS_Shape& theSolids,
 120                           TopTools_DataMapOfShapeListOfShape& theSSInterfs);
 121
 122 static
 123   void BuildSplitsOfInvFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
 124                              const TopTools_MapOfShape& theModifiedEdges,
 125                              TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 126                              TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
 127                              TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 128                              TopTools_DataMapOfShapeShape& theFacesOrigins,
 129                              TopTools_DataMapOfShapeListOfShape& theOEImages,
 130                              TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 131                              TopTools_MapOfShape& theLastInvEdges,
 132                              TopTools_IndexedMapOfShape& theEdgesToAvoid,
 133                              TopTools_MapOfShape& theVertsToAvoid,
 134                              TopTools_DataMapOfShapeInteger& theAlreadyInvFaces,
 135                              TopTools_IndexedMapOfShape& theValidEdges,
 136                              TopTools_DataMapOfShapeShape& theETrimEInf,
 137                              Handle(BRepAlgo_AsDes)& theAsDes);
 138
 139 static
 140   Standard_Boolean CheckIfArtificial(const TopoDS_Shape& theF,
 141                                      const TopTools_ListOfShape& theLFImages,
 142                                      const TopoDS_Shape& theCE,
 143                                      const TopTools_IndexedMapOfShape& theMapEInv,
 144                                      const TopTools_DataMapOfShapeListOfShape& theOEImages,
 145                                      TopTools_MapOfShape& theMENInv,
 146                                      Handle(BRepAlgo_AsDes)& theAsDes);
 147
 148 static
 149   void FindInvalidEdges(const TopoDS_Face& theF,
 150                         const TopTools_ListOfShape& theLFImages,
 151                         const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 152                         const TopTools_DataMapOfShapeShape& theFacesOrigins,
 153                         const TopTools_DataMapOfShapeListOfShape& theOEImages,
 154                         const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 155                         TopTools_IndexedMapOfShape& theInvEdges,
 156                         TopTools_IndexedMapOfShape& theValidEdges,
 157                         TopTools_DataMapOfShapeListOfShape& theDMFLVE,
 158                         TopTools_DataMapOfShapeListOfShape& theDMFLNE,
 159                         TopTools_DataMapOfShapeListOfShape& theDMFLIE,
 160                         TopTools_DataMapOfShapeListOfShape& theDMFLVIE,
 161                         TopTools_DataMapOfShapeListOfShape& theDMEOrLEIm,
 162                         TopTools_MapOfShape& theMEInverted,
 163                         TopTools_MapOfShape& theEdgesInvalidByVertex);
 164
 165 static
 166   void FindInvalidFaces(TopTools_ListOfShape& theLFImages,
 167                         const TopTools_IndexedMapOfShape& theInvEdges,
 168                         const TopTools_IndexedMapOfShape& theValidEdges,
 169                         const TopTools_DataMapOfShapeListOfShape& theDMFLVE,
 170                         const TopTools_DataMapOfShapeListOfShape& theDMFLIE,
 171                         const TopTools_ListOfShape& theLENeutral,
 172                         const TopTools_ListOfShape& theLEValInverted,
 173                         const TopTools_MapOfShape& theMEInverted,
 174                         const TopTools_MapOfShape& theEdgesInvalidByVertex,
 175                         const TopTools_MapOfShape& theMFHoles,
 176                         TopTools_IndexedMapOfShape& theMFInvInHole,
 177                         TopTools_ListOfShape& theInvFaces);
 178
 179 static
 180   void FindFacesInsideHoleWires(const TopoDS_Face& theFOrigin,
 181                                 const TopoDS_Face& theFOffset,
 182                                 const TopTools_ListOfShape& theLFImages,
 183                                 const TopTools_MapOfShape& theInvertedEdges,
 184                                 const TopTools_DataMapOfShapeListOfShape& theDMEOrLEIm,
 185                                 TopTools_MapOfShape& theMFHoles,
 186                                 TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
 187                                 Handle(IntTools_Context)& theContext);
 188
 189 static
 190   gp_Vec GetAverageTangent(const TopoDS_Shape& theS,
 191                            const Standard_Integer theNbP);
 192
 193 static
 194   Standard_Boolean CheckInverted(const TopoDS_Edge& theEIm,
 195                                  const TopoDS_Face& theFOr,
 196                                  const TopTools_DataMapOfShapeListOfShape& theOEImages,
 197                                  const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 198                                  const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 199                                  const TopTools_IndexedDataMapOfShapeListOfShape& theDMVE,
 200                                  const TopTools_IndexedMapOfShape& theMEdges,
 201                                  TopTools_MapOfShape& theMEInverted);
 202
 203 static
 204   Standard_Boolean CheckInvertedBlock(const TopoDS_Shape& theCB,
 205                                       const TopTools_ListOfShape& theLCBF,
 206                                       const TopTools_MapOfShape& theMEInverted,
 207                                       const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 208                                       BRepOffset_DataMapOfShapeMapOfShape& theDMCBVInverted,
 209                                       BRepOffset_DataMapOfShapeMapOfShape& theDMCBVAll);
 210
 211 static
 212   void GetVerticesOnEdges(const TopoDS_Shape& theCB,
 213                           const TopTools_MapOfShape& theEdges,
 214                           TopTools_MapOfShape& theVerticesOnEdges,
 215                           TopTools_MapOfShape& theAllVertices);
 216
 217 static
 218   void RemoveInvalidSplitsByInvertedEdges(const TopTools_MapOfShape& theMEInverted,
 219                                           const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 220                                           TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 221                                           TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 222                                           TopTools_IndexedMapOfShape& theMERemoved);
 223
 224 static
 225   void RemoveInvalidSplitsFromValid(const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 226                                     const TopTools_DataMapOfShapeShape& theArtInvFaces,
 227                                     const TopTools_MapOfShape& theMEInverted,
 228                                     TopTools_IndexedDataMapOfShapeListOfShape& theFImages);
 229
 230 static
 231   void RemoveInsideFaces(TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 232                          TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 233                          const TopTools_DataMapOfShapeShape& theArtInvFaces,
 234                          const TopTools_IndexedMapOfShape& theInvEdges,
 235                          const TopTools_IndexedMapOfShape& theMFToCheckInt,
 236                          const TopTools_IndexedMapOfShape& theMFInvInHole,
 237                          const TopoDS_Shape& theFHoles,
 238                          TopTools_DataMapOfShapeListOfShape& theSSInterfs,
 239                          TopTools_IndexedMapOfShape& theMERemoved,
 240                          TopTools_IndexedMapOfShape& theMEInside,
 241                          TopoDS_Shape& theSolids);
 242
 243 static
 244   void ShapesConnections(const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 245                          const TopTools_IndexedMapOfShape& theInvEdges,
 246                          const TopTools_DataMapOfShapeShape& theDMFOr,
 247                          BOPAlgo_Builder& theBuilder,
 248                          TopTools_DataMapOfShapeListOfShape& theSSInterfs);
 249
 250 static
 251   void RemoveValidSplits(const TopTools_MapOfShape& theSpRem,
 252                          TopTools_IndexedDataMapOfShapeListOfShape& theImages,
 253                          BOPAlgo_Builder& theGF,
 254                          TopTools_IndexedMapOfShape& theMERemoved);
 255
 256 static
 257   void RemoveInvalidSplits(const TopTools_MapOfShape& theSpRem,
 258                            const TopTools_DataMapOfShapeShape& theArtInvFaces,
 259                            const TopTools_IndexedMapOfShape& theInvEdges,
 260                            TopTools_IndexedDataMapOfShapeListOfShape& theImages,
 261                            BOPAlgo_Builder& theGF,
 262                            TopTools_IndexedMapOfShape& theMERemoved);
 263
 264 static
 265   void FilterEdgesImages(const TopoDS_Shape& theS,
 266                          TopTools_DataMapOfShapeListOfShape& theOEImages,
 267                          TopTools_DataMapOfShapeListOfShape& theOEOrigins);
 268
 269 static
 270   void FilterInvalidFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 271                           const TopTools_IndexedDataMapOfShapeListOfShape& theDMEF,
 272                           const TopTools_IndexedMapOfShape& theMERemoved,
 273                           TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 274                           TopTools_DataMapOfShapeShape& theArtInvFaces);
 275
 276 static
 277   void FilterInvalidEdges(const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 278                           const TopTools_DataMapOfShapeShape& theArtInvFaces,
 279                           const TopTools_DataMapOfShapeListOfShape& theDMFLIE,
 280                           const TopTools_IndexedMapOfShape& theMERemoved,
 281                           TopTools_IndexedMapOfShape& theInvEdges);
 282
 283 static
 284   void FindFacesToRebuild(const TopTools_IndexedDataMapOfShapeListOfShape&  theLFImages,
 285                           const TopTools_IndexedMapOfShape& theInvEdges,
 286                           const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 287                           const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
 288                           TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
 289                           TopTools_MapOfShape& theFSelfRebAvoid);
 290
 291 static
 292   void RebuildFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
 293                     const TopTools_MapOfShape& theFSelfRebAvoid,
 294                     const TopoDS_Shape& theSolids,
 295                     const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
 296                     TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 297                     TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
 298                     TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 299                     TopTools_DataMapOfShapeShape& theFacesOrigins,
 300                     TopTools_DataMapOfShapeListOfShape& theOEImages,
 301                     TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 302                     TopTools_MapOfShape& theLastInvEdges,
 303                     TopTools_IndexedMapOfShape& theEdgesToAvoid,
 304                     TopTools_IndexedMapOfShape& theInvEdges,
 305                     TopTools_IndexedMapOfShape& theValidEdges,
 306                     const TopTools_MapOfShape& theInvertedEdges,
 307                     TopTools_DataMapOfShapeInteger& theAlreadyInvFaces,
 308                     TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 309                     const TopTools_DataMapOfShapeShape& theArtInvFaces,
 310                     TopTools_MapOfShape& theVertsToAvoid,
 311                     TopTools_DataMapOfShapeShape& theETrimEInf,
 312                     Handle(BRepAlgo_AsDes)& theAsDes);
 313
 314 static
 315   void IntersectFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
 316                       const TopTools_MapOfShape& theFSelfRebAvoid,
 317                       const TopoDS_Shape& theSolids,
 318                       const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
 319                       TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 320                       TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 321                       TopTools_DataMapOfShapeListOfShape& theOEImages,
 322                       TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 323                       TopTools_IndexedMapOfShape& theInvEdges,
 324                       TopTools_IndexedMapOfShape& theValidEdges,
 325                       const TopTools_MapOfShape& theInvertedEdges,
 326                       TopTools_IndexedMapOfShape& theEdgesToAvoid,
 327                       TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 328                       const TopTools_DataMapOfShapeShape& theArtInvFaces,
 329                       TopTools_MapOfShape& theVertsToAvoid,
 330                       TopTools_DataMapOfShapeShape& theETrimEInf,
 331                       TopTools_MapOfShape& theModifiedEdges,
 332                       Handle(BRepAlgo_AsDes)& theAsDes);
 333
 334 static
 335   void PrepareFacesForIntersection(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
 336                                    const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 337                                    const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 338                                    const TopTools_DataMapOfShapeShape& theArtInvFaces,
 339                                    const Standard_Boolean bLookVertToAvoid,
 340                                    TopTools_IndexedDataMapOfShapeListOfShape& theFLE,
 341                                    TopTools_DataMapOfShapeListOfShape& theMDone,
 342                                    TopTools_DataMapOfShapeListOfShape& theDMSF,
 343                                    TopTools_DataMapOfShapeListOfShape& theMEInfETrim,
 344                                    TopTools_DataMapOfShapeListOfShape& theDMVEFull,
 345                                    TopTools_DataMapOfShapeShape& theETrimEInf,
 346                                    TopTools_IndexedDataMapOfShapeListOfShape& theDMEFInv);
 347
 348 static
 349   void FindVerticesToAvoid(const TopTools_IndexedDataMapOfShapeListOfShape& theDMEFInv,
 350                            const TopTools_IndexedMapOfShape& theInvEdges,
 351                            const TopTools_IndexedMapOfShape& theValidEdges,
 352                            TopTools_DataMapOfShapeListOfShape& theDMVEFull,
 353                            TopTools_MapOfShape& theMVRInv);
 354
 355 static
 356   void FindFacesForIntersection(const TopoDS_Shape& theFInv,
 357                                 const TopTools_IndexedMapOfShape& theME,
 358                                 const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 359                                 const TopTools_DataMapOfShapeListOfShape& theDMSF,
 360                                 const TopTools_MapOfShape& theMVInvAll,
 361                                 const TopTools_DataMapOfShapeShape& theArtInvFaces,
 362                                 const Standard_Boolean theArtCase,
 363                                 const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
 364                                 TopTools_IndexedMapOfShape& theMFAvoid,
 365                                 TopTools_IndexedMapOfShape& theMFInt,
 366                                 TopTools_IndexedMapOfShape& theMFIntExt,
 367                                 TopTools_ListOfShape& theLFImInt);
 368
 369 static
 370   void ProcessCommonEdges(const TopTools_ListOfShape& theLEC,
 371                           const TopTools_IndexedMapOfShape& theInvEdges,
 372                           const TopTools_IndexedMapOfShape& theValidEdges,
 373                           const TopTools_IndexedMapOfShape& theME,
 374                           const TopTools_DataMapOfShapeShape& theETrimEInf,
 375                           const TopTools_DataMapOfShapeListOfShape& theMEInfETrim,
 376                           const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 377                           const TopTools_MapOfShape& theAllInvs,
 378                           const Standard_Boolean theForceUse,
 379                           TopTools_IndexedMapOfShape& theMECV,
 380                           TopTools_MapOfShape& theMECheckExt,
 381                           TopTools_DataMapOfShapeListOfShape& theDMEETrim,
 382                           TopTools_ListOfShape& theLFEi,
 383                           TopTools_ListOfShape& theLFEj,
 384                           TopTools_IndexedMapOfShape& theMEToInt);
 385
 386 static
 387   void UpdateIntersectedFaces(const TopoDS_Shape& theFInv,
 388                               const TopoDS_Shape& theFi,
 389                               const TopoDS_Shape& theFj,
 390                               const TopTools_ListOfShape& theLFInv,
 391                               const TopTools_ListOfShape& theLFImi,
 392                               const TopTools_ListOfShape& theLFImj,
 393                               const TopTools_ListOfShape& theLFEi,
 394                               const TopTools_ListOfShape& theLFEj,
 395                               TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 396                               TopTools_IndexedMapOfShape& theMEToInt);
 397
 398 static
 399   void IntersectFaces(const TopoDS_Shape& theFInv,
 400                       const TopoDS_Shape& theFi,
 401                       const TopoDS_Shape& theFj,
 402                       const TopTools_ListOfShape& theLFInv,
 403                       const TopTools_ListOfShape& theLFImi,
 404                       const TopTools_ListOfShape& theLFImj,
 405                       TopTools_ListOfShape& theLFEi,
 406                       TopTools_ListOfShape& theLFEj,
 407                       TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 408                       TopTools_IndexedMapOfShape& theMECV,
 409                       TopTools_IndexedMapOfShape& theMEToInt);
 410
 411 static
 412   void FindOrigins(const TopTools_ListOfShape& theLFIm1,
 413                    const TopTools_ListOfShape& theLFIm2,
 414                    const TopTools_IndexedMapOfShape& theME,
 415                    const TopTools_DataMapOfShapeListOfShape& theOrigins,
 416                    TopTools_ListOfShape& theLEOr);
 417
 418 static
 419   void IntersectAndTrimEdges(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
 420                              const TopTools_IndexedMapOfShape& theMFInt,
 421                              const TopTools_IndexedMapOfShape& theMEInt,
 422                              const TopTools_DataMapOfShapeListOfShape& theDMEETrim,
 423                              const TopTools_IndexedMapOfShape& theMSInv,
 424                              const TopTools_IndexedMapOfShape& theMVE,
 425                              const TopTools_MapOfShape& theVertsToAvoid,
 426                              const TopTools_MapOfShape& theNewVertsToAvoid,
 427                              const TopTools_MapOfShape& theMECheckExt,
 428                              TopTools_MapOfShape& theMVBounds,
 429                              TopTools_DataMapOfShapeListOfShape& theEImages);
 430
 431 static
 432   void GetInvalidEdges(const TopTools_MapOfShape& theVertsToAvoid,
 433                        const TopTools_MapOfShape& theMVBounds,
 434                        BOPAlgo_Builder& theGF,
 435                        TopTools_MapOfShape& theMEInv);
 436
 437 static
 438   void UpdateValidEdges(const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 439                         const TopTools_IndexedDataMapOfShapeListOfShape& theFLE,
 440                         const TopTools_MapOfShape& theMVBounds,
 441                         const TopoDS_Shape& theSolids,
 442                         const TopTools_IndexedMapOfShape& theInvEdges,
 443                         const TopTools_MapOfShape& theInvertedEdges,
 444                         const TopTools_MapOfShape& theMEInvOnArt,
 445                         TopTools_MapOfShape& theMECheckExt,
 446                         TopTools_IndexedMapOfShape& theEdgesToAvoid,
 447                         TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 448                         TopTools_DataMapOfShapeListOfShape& theOEImages,
 449                         TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 450                         TopTools_MapOfShape& theVertsToAvoid,
 451                         TopTools_DataMapOfShapeShape& theETrimEInf,
 452                         TopTools_DataMapOfShapeListOfShape& theEImages,
 453                         TopTools_DataMapOfShapeListOfShape& theEETrim,
 454                         TopTools_MapOfShape& theModifiedEdges,
 455                         Handle(BRepAlgo_AsDes)& theAsDes);
 456
 457 static
 458   void TrimNewIntersectionEdges(const TopTools_ListOfShape& theLE,
 459                                 const TopTools_DataMapOfShapeListOfShape& theEETrim,
 460                                 const TopTools_MapOfShape& theMVBounds,
 461                                 TopTools_MapOfShape& theMECheckExt,
 462                                 TopTools_DataMapOfShapeListOfShape& theEImages,
 463                                 TopTools_MapOfShape& theMEB,
 464                                 TopTools_MapOfShape& theMVOld,
 465                                 TopTools_ListOfShape& theLENew,
 466                                 BOPCol_ListOfShape& theLA,
 467                                 TopTools_DataMapOfShapeListOfShape& theDMEOr,
 468                                 TopTools_DataMapOfShapeListOfShape& theMELF);
 469
 470 static
 471   void IntersectEdges(const BOPCol_ListOfShape& theLA,
 472                       const TopTools_ListOfShape& theLE,
 473                       const TopTools_ListOfShape& theLENew,
 474                       const TopTools_MapOfShape& theMVBounds,
 475                       const TopTools_MapOfShape& theVertsToAvoid,
 476                       TopTools_MapOfShape& theMECheckExt,
 477                       TopTools_DataMapOfShapeListOfShape& theEImages,
 478                       TopTools_MapOfShape& theModifiedEdges,
 479                       TopTools_DataMapOfShapeListOfShape& theDMEOr,
 480                       TopTools_DataMapOfShapeListOfShape& theMELF,
 481                       TopTools_MapOfShape& theMENew,
 482                       TopoDS_Shape& theSplits);
 483
 484 static
 485   void GetBounds(const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 486                  const TopTools_MapOfShape& theMEB,
 487                  TopoDS_Shape& theBounds);
 488
 489 static
 490   void GetBoundsToUpdate(const TopTools_ListOfShape& theLF,
 491                          const TopTools_DataMapOfShapeListOfShape& theOEImages,
 492                          const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 493                          const TopTools_MapOfShape& theMEB,
 494                          TopTools_ListOfShape& theLABounds,
 495                          TopTools_ListOfShape& theLAValid,
 496                          TopoDS_Shape& theBounds,
 497                          Handle(BRepAlgo_AsDes)& theAsDes);
 498
 499 static
 500   void GetInvalidEdgesByBounds(const TopoDS_Shape& theSplits,
 501                                const TopoDS_Shape& theBounds,
 502                                const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 503                                const TopoDS_Shape& theSolids,
 504                                const TopTools_IndexedMapOfShape& theInvEdges,
 505                                const TopTools_MapOfShape& theMVOld,
 506                                const TopTools_MapOfShape& theMENew,
 507                                const TopTools_DataMapOfShapeListOfShape& theDMEOr,
 508                                const TopTools_DataMapOfShapeListOfShape& theMELF,
 509                                const TopTools_DataMapOfShapeListOfShape& theEImages,
 510                                const TopTools_MapOfShape& theMECheckExt,
 511                                const TopTools_MapOfShape& theMEInvOnArt,
 512                                TopTools_MapOfShape& theVertsToAvoid,
 513                                TopTools_MapOfShape& theMEInv);
 514
 515 static
 516   void UpdateNewIntersectionEdges(const TopTools_ListOfShape& theLE,
 517                                   const TopTools_DataMapOfShapeListOfShape& theMELF,
 518                                   const TopTools_DataMapOfShapeListOfShape& theEImages,
 519                                   const TopTools_IndexedMapOfShape& theInvEdges,
 520                                   const TopTools_MapOfShape& theInvertedEdges,
 521                                   TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 522                                   TopTools_DataMapOfShapeListOfShape& theOEImages,
 523                                   TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 524                                   TopTools_DataMapOfShapeShape& theETrimEInf,
 525                                   TopTools_DataMapOfShapeListOfShape& theEETrim,
 526                                   TopTools_MapOfShape& theModifiedEdges,
 527                                   Handle(BRepAlgo_AsDes)& theAsDes);
 528
 529 static
 530   void FillHistory(const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 531                    const TopTools_DataMapOfShapeListOfShape& theEImages,
 532                    BRepAlgo_Image& theImage);
 533
 534 static
 535   void UpdateOrigins(const TopTools_ListOfShape& theLA,
 536                      TopTools_DataMapOfShapeListOfShape& theOrigins,
 537                      BOPAlgo_Builder& theGF);
 538
 539 static
 540   void UpdateImages(const TopTools_ListOfShape& theLA,
 541                     TopTools_DataMapOfShapeListOfShape& theImages,
 542                     BOPAlgo_Builder& theGF,
 543                     TopTools_MapOfShape& theModified);
 544
 545 static
 546   void UpdateIntersectedEdges(const TopTools_ListOfShape& theLA,
 547                               TopTools_DataMapOfShapeShape& theETrimEInf,
 548                               BOPAlgo_Builder& theGF);
 549
 550 static
 551   Standard_Boolean ProcessMicroEdge(const TopoDS_Edge& theEdge,
 552                                     const Handle(IntTools_Context)& theCtx);
 553
 554 static
 555   void FindCommonParts(const TopTools_ListOfShape& theLS1,
 556                        const TopTools_ListOfShape& theLS2,
 557                        TopTools_ListOfShape& theLSC,
 558                        const TopAbs_ShapeEnum theType = TopAbs_EDGE);
 559
 560 static
 561   Standard_Integer NbPoints(const TopoDS_Edge& theE);
 562
 563 static
 564   Standard_Boolean FindShape(const TopoDS_Shape& theSWhat,
 565                              const TopoDS_Shape& theSWhere,
 566                              TopoDS_Shape& theRes);
 567
 568 static
 569   void AppendToList(TopTools_ListOfShape& theL,
 570                     const TopoDS_Shape& theS);
 571
 572 //=======================================================================
 573 //function : BuildSplitsOfTrimmedFaces
 574 //purpose  : Building splits of already trimmed faces
 575 //=======================================================================
 576 void BRepOffset_MakeOffset::BuildSplitsOfTrimmedFaces(const TopTools_ListOfShape& theLF,
 577                                                       Handle(BRepAlgo_AsDes)& theAsDes,
 578                                                       BRepAlgo_Image& theImage)
 579 {
 580   TopTools_DataMapOfShapeListOfShape anEImages, anEOrigins;
 581   TopTools_IndexedDataMapOfShapeListOfShape aDMFFIm;
 582   TopTools_IndexedMapOfShape anEmptyIM;
 583   TopTools_DataMapOfShapeListOfShape anEmptyDMSLS;
 584   TopTools_DataMapOfShapeShape anEmptyDMSS;
 585   TopTools_MapOfShape aNewEdges, anEmptyM;
 586   //
 587   // firstly it is necessary to fuse all the edges
 588   Handle(IntTools_Context) aCtx = new IntTools_Context();
 589   //
 590   IntersectTrimmedEdges(theLF, theAsDes, anEImages, anEOrigins, anEmptyDMSLS, aCtx, aNewEdges, anEmptyDMSS);
 591   //
 592   TopTools_ListIteratorOfListOfShape aItLF(theLF);
 593   for (; aItLF.More(); aItLF.Next()) {
 594     const TopoDS_Face& aF = *(TopoDS_Face*)&aItLF.Value();
 595     //
 596     TopoDS_Shape aCE;
 597     TopTools_ListOfShape aLFImages;
 598     //
 599     Standard_Boolean bFound = GetEdges(aF, theAsDes, anEImages, anEmptyM,
 600                                        anEmptyIM, aCtx, aNewEdges, aCE, anEmptyIM);
 601     // split the face by the edges
 602     if (!bFound) {
 603       if (!theImage.HasImage(aF)) {
 604         aLFImages.Append(aF);
 605         aDMFFIm.Add(aF, aLFImages);
 606       }
 607       continue;
 608     }
 609     //
 610     BuildSplitsOfTrimmedFace(aF, aCE, aLFImages);
 611     aDMFFIm.Add(aF, aLFImages);
 612   }
 613   // Fill history for faces and edges
 614   FillHistory(aDMFFIm, anEImages, theImage);
 615 }
 616
 617 //=======================================================================
 618 //function : BuildSplitsOfExtendedFaces
 619 //purpose  : Building splits of not-trimmed offset faces.
 620 //           For the cases in which invalidity will be found,
 621 //           these invalidities will be rebuilt.
 622 //=======================================================================
 623 void BRepOffset_MakeOffset::BuildSplitsOfExtendedFaces(const TopTools_ListOfShape& theLF,
 624                                                        Handle(BRepAlgo_AsDes)& theAsDes,
 625                                                        TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 626                                                        TopTools_DataMapOfShapeShape& theFacesOrigins,
 627                                                        TopTools_DataMapOfShapeShape& theETrimEInf,
 628                                                        BRepAlgo_Image& theImage)
 629 {
 630   Handle(IntTools_Context) aCtx = new IntTools_Context();
 631   // images and origins for offset edges
 632   TopTools_DataMapOfShapeListOfShape anOEImages, anOEOrigins;
 633   TopTools_MapOfShape aNewEdges;
 634   // fusing all trimmed offset edges to avoid self-intersections in the splits
 635   IntersectTrimmedEdges(theLF, theAsDes, anOEImages, anOEOrigins,
 636                         theEdgesOrigins, aCtx, aNewEdges, theETrimEInf);
 637   //
 638   // valid/invalid edges
 639   TopTools_IndexedMapOfShape anInvEdges, aValidEdges, anEdgesToAvoid;
 640   // inverted edges
 641   TopTools_MapOfShape anInvertedEdges;
 642   // splits of faces
 643   TopTools_IndexedDataMapOfShapeListOfShape aFImages;
 644   // found invalid faces
 645   TopTools_IndexedDataMapOfShapeListOfShape anInvFaces;
 646   // artificially invalid faces - it will be empty here,
 647   // but may be filled on the following rebuilding steps
 648   TopTools_DataMapOfShapeShape anArtInvFaces;
 649   // shapes connections for using in rebuilding
 650   TopTools_DataMapOfShapeListOfShape aSSInterfs;
 651   // edges to avoid on second steps
 652   TopTools_MapOfShape aLastInvEdges;
 653   // keep information of already invalid faces to avoid
 654   // infinite rebuilding of the same invalid face
 655   TopTools_DataMapOfShapeInteger anAlreadyInvFaces;
 656   // images of the hole faces of the original faces
 657   TopTools_DataMapOfShapeListOfShape aDMFNewHoles;
 658   // solid build from the new splits
 659   TopoDS_Shape aSolids;
 660   // now we can split the faces
 661   BuildSplitsOfFaces(theLF, aNewEdges, theEdgesOrigins, theAsDes, theFacesOrigins,
 662                      anOEImages, anOEOrigins, aLastInvEdges, anEdgesToAvoid, anInvEdges, aValidEdges,
 663                      anInvertedEdges, anAlreadyInvFaces, anInvFaces, anArtInvFaces, aFImages,
 664                      aDMFNewHoles, aSolids, aSSInterfs);
 665   //
 666   // Find faces to rebuild
 667   if (anInvFaces.Extent()) {
 668     TopTools_IndexedDataMapOfShapeListOfShape aFToRebuild;
 669     TopTools_MapOfShape aFSelfRebAvoid;
 670     FindFacesToRebuild(aFImages, anInvEdges, anInvFaces, aSSInterfs, aFToRebuild, aFSelfRebAvoid);
 671     //
 672     if (aFToRebuild.Extent()) {
 673       // vertices to avoid
 674       TopTools_MapOfShape aVAEmpty;
 675       RebuildFaces(aFToRebuild, aFSelfRebAvoid, aSolids, aSSInterfs, aFImages, aDMFNewHoles,
 676                    theEdgesOrigins, theFacesOrigins, anOEImages, anOEOrigins, aLastInvEdges,
 677                    anEdgesToAvoid, anInvEdges, aValidEdges, anInvertedEdges, anAlreadyInvFaces,
 678                    anInvFaces, anArtInvFaces, aVAEmpty, theETrimEInf, theAsDes);
 679     }
 680   }
 681   // Fill history for faces and edges
 682   FillHistory(aFImages, anOEImages, theImage);
 683 }
 684
 685 //=======================================================================
 686 //function : BuildSplitsOfInvFaces
 687 //purpose  : Rebuilding splits of faces with new intersection edges
 688 //=======================================================================
 689 void BuildSplitsOfInvFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
 690                            const TopTools_MapOfShape& theModifiedEdges,
 691                            TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 692                            TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
 693                            TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 694                            TopTools_DataMapOfShapeShape& theFacesOrigins,
 695                            TopTools_DataMapOfShapeListOfShape& theOEImages,
 696                            TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 697                            TopTools_MapOfShape& theLastInvEdges,
 698                            TopTools_IndexedMapOfShape& theEdgesToAvoid,
 699                            TopTools_MapOfShape& theVertsToAvoid,
 700                            TopTools_DataMapOfShapeInteger& theAlreadyInvFaces,
 701                            TopTools_IndexedMapOfShape& theValidEdges,
 702                            TopTools_DataMapOfShapeShape& theETrimEInf,
 703                            Handle(BRepAlgo_AsDes)& theAsDes)
 704 {
 705   Standard_Integer aNb = theFToRebuild.Extent();
 706   if (!aNb) {
 707     return;
 708   }
 709   //
 710   TopTools_ListOfShape aLF;
 711   aNb = theFImages.Extent();
 712   for (Standard_Integer i = 1; i <= aNb; ++i) {
 713     const TopoDS_Shape& aF = theFImages.FindKey(i);
 714     aLF.Append(aF);
 715   }
 716   //
 717   // invalid faces
 718   TopTools_IndexedDataMapOfShapeListOfShape anInvFaces;
 719   // artificially invalid faces
 720   TopTools_DataMapOfShapeShape anArtInvFaces;
 721   // invalid edges
 722   TopTools_IndexedMapOfShape anInvEdges;
 723   // inverted edges
 724   TopTools_MapOfShape anInvertedEdges;
 725   // shapes connection for using in rebuilding process
 726   TopTools_DataMapOfShapeListOfShape aSSInterfs;
 727   //
 728   TopoDS_Shape aSolids;
 729   //
 730   BuildSplitsOfFaces(aLF, theModifiedEdges, theEdgesOrigins, theAsDes, theFacesOrigins,
 731                      theOEImages, theOEOrigins, theLastInvEdges, theEdgesToAvoid, anInvEdges, theValidEdges,
 732                      anInvertedEdges, theAlreadyInvFaces, anInvFaces, anArtInvFaces, theFImages,
 733                      theDMFNewHoles, aSolids, aSSInterfs);
 734   //
 735   if (anInvFaces.Extent()) {
 736     TopTools_IndexedDataMapOfShapeListOfShape aFToRebuild;
 737     TopTools_MapOfShape aFSelfRebAvoid;
 738     FindFacesToRebuild(theFImages, anInvEdges, anInvFaces, aSSInterfs, aFToRebuild, aFSelfRebAvoid);
 739     //
 740     if (aFToRebuild.Extent()) {
 741       RebuildFaces(aFToRebuild, aFSelfRebAvoid, aSolids, aSSInterfs, theFImages, theDMFNewHoles,
 742                    theEdgesOrigins, theFacesOrigins, theOEImages, theOEOrigins, theLastInvEdges,
 743                    theEdgesToAvoid, anInvEdges, theValidEdges, anInvertedEdges, theAlreadyInvFaces,
 744                    anInvFaces, anArtInvFaces, theVertsToAvoid, theETrimEInf, theAsDes);
 745     }
 746   }
 747 }
 748
 749 //=======================================================================
 750 //function : BuildSplitsOfFaces
 751 //purpose  : Building the splits of offset faces and
 752 //           looking for the invalid splits
 753 //=======================================================================
 754 void BuildSplitsOfFaces(const TopTools_ListOfShape& theLF,
 755                         const TopTools_MapOfShape& theModifiedEdges,
 756                         const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
 757                         Handle(BRepAlgo_AsDes)& theAsDes,
 758                         TopTools_DataMapOfShapeShape& theFacesOrigins,
 759                         TopTools_DataMapOfShapeListOfShape& theOEImages,
 760                         TopTools_DataMapOfShapeListOfShape& theOEOrigins,
 761                         TopTools_MapOfShape& theLastInvEdges,
 762                         TopTools_IndexedMapOfShape& theEdgesToAvoid,
 763                         TopTools_IndexedMapOfShape& theInvEdges,
 764                         TopTools_IndexedMapOfShape& theValidEdges,
 765                         TopTools_MapOfShape& theInvertedEdges,
 766                         TopTools_DataMapOfShapeInteger& theAlreadyInvFaces,
 767                         TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
 768                         TopTools_DataMapOfShapeShape& theArtInvFaces,
 769                         TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
 770                         TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
 771                         TopoDS_Shape& theSolids,
 772                         TopTools_DataMapOfShapeListOfShape& theSSInterfs)
 773 {
 774   if (theLF.IsEmpty()) {
 775     return;
 776   }
 777   //
 778   BRep_Builder aBB;
 779   Standard_Integer i, aNb;
 780   //
 781   // processed faces
 782   TopTools_ListOfShape aLFDone;
 783   // extended face - list of neutral edges, i.e. in one splits - valid and in others - invalid
 784   TopTools_DataMapOfShapeListOfShape aDMFLNE;
 785   // list of valid edges for each face
 786   TopTools_DataMapOfShapeListOfShape aDMFLVE;
 787   // list of invalid edges for each face
 788   TopTools_DataMapOfShapeListOfShape aDMFLIE;
 789   // map of valid inverted edges for the face
 790   TopTools_DataMapOfShapeListOfShape aDMFLVIE;
 791   // map of splits to check for internals
 792   TopTools_IndexedMapOfShape aMFToCheckInt;
 793   // map of edges created from vertex and marked as invalid
 794   TopTools_MapOfShape aMEdgeInvalidByVertex;
 795   // connection map from old edges to new ones
 796   TopTools_DataMapOfShapeListOfShape aDMEOrLEIm;
 797   //
 798   Handle(IntTools_Context) aCtx = new IntTools_Context;
 799   // build splits of faces
 800   TopTools_ListIteratorOfListOfShape aItLF(theLF);
 801   for (; aItLF.More(); aItLF.Next()) {
 802     const TopoDS_Face& aF = *(TopoDS_Face*)&aItLF.Value();
 803     //
 804     TopTools_ListOfShape* pLFIm = theFImages.ChangeSeek(aF);
 805     if (pLFIm && pLFIm->IsEmpty()) {
 806       continue;
 807     }
 808     // get edges by which the face should be split
 809     TopoDS_Shape aCE;
 810     TopTools_IndexedMapOfShape aMapEInv;
 811     Standard_Boolean bFound =
 812       GetEdges(aF, theAsDes, theOEImages, theLastInvEdges,
 813                theEdgesToAvoid, aCtx, theModifiedEdges, aCE, aMapEInv);
 814     if (!bFound) {
 815       continue;
 816     }
 817     //
 818     // build splits
 819     TopTools_ListOfShape aLFImages;
 820     BuildSplitsOfFace(aF, aCE, theFacesOrigins, aLFImages);
 821     //
 822     if (aMapEInv.Extent()) {
 823       // check if all possible faces are built
 824       TopTools_MapOfShape aMENInv;
 825       Standard_Boolean bArtificialCase = aLFImages.IsEmpty() ||
 826         CheckIfArtificial(aF, aLFImages, aCE, aMapEInv, theOEImages, aMENInv, theAsDes);
 827       //
 828       // try to build splits using invalid edges
 829       TopoDS_Compound aCE1;
 830       aBB.MakeCompound(aCE1);
 831       aBB.Add(aCE1, aCE);
 832       for (i = 1; i <= aMapEInv.Extent(); ++i) {
 833         aBB.Add(aCE1, aMapEInv(i));
 834       }
 835       //
 836       TopTools_ListOfShape aLFImages1;
 837       BuildSplitsOfFace(aF, aCE1, theFacesOrigins, aLFImages1);
 838       //
 839       // check if the rebuilding has added some new faces to the splits
 840       for (TopTools_ListIteratorOfListOfShape aItLFIm(aLFImages1); aItLFIm.More();)
 841       {
 842         Standard_Boolean bAllInv = Standard_True;
 843         const TopoDS_Shape& aFIm = aItLFIm.Value();
 844         TopExp_Explorer aExpE(aFIm, TopAbs_EDGE);
 845         for (; aExpE.More(); aExpE.Next()) {
 846           const TopoDS_Shape& aE = aExpE.Current();
 847           if (!aMapEInv.Contains(aE)) {
 848             bAllInv = Standard_False;
 849             if (!aMENInv.Contains(aE)) {
 850               break;
 851             }
 852           }
 853         }
 854         //
 855         if (!aExpE.More()) {
 856           if (bAllInv) {
 857             aMFToCheckInt.Add(aFIm);
 858           }
 859           aLFImages1.Remove(aItLFIm);
 860         }
 861         else {
 862           aItLFIm.Next();
 863         }
 864       }
 865       //
 866       if (bArtificialCase) {
 867         if (aLFImages.Extent() == aLFImages1.Extent()) {
 868           bArtificialCase = Standard_False;
 869         }
 870         else {
 871           aLFImages = aLFImages1;
 872         }
 873       }
 874       //
 875       if (bArtificialCase) {
 876         TopTools_ListOfShape aLEInv;
 877         // make the face invalid
 878         theArtInvFaces.Bind(aF, aCE);
 879         //
 880         *pLFIm = aLFImages;
 881         TopTools_ListIteratorOfListOfShape aItLFIm(aLFImages);
 882         for (; aItLFIm.More(); aItLFIm.Next()) {
 883           const TopoDS_Shape& aFIm = aItLFIm.Value();
 884           TopExp_Explorer aExpE(aFIm, TopAbs_EDGE);
 885           for (; aExpE.More(); aExpE.Next()) {
 886             const TopoDS_Shape& aE = aExpE.Current();
 887             if (aMapEInv.Contains(aE)) {
 888               theInvEdges.Add(aE);
 889               AppendToList(aLEInv, aE);
 890             }
 891             else {
 892               theValidEdges.Add(aE);
 893             }
 894           }
 895         }
 896         //
 897         aDMFLIE.Bind(aF, aLEInv);
 898         aLFDone.Append(aF);
 899         //
 900         continue;
 901       }
 902     }
 903     //
 904     // find invalid edges
 905     FindInvalidEdges(aF, aLFImages, theEdgesOrigins, theFacesOrigins, theOEImages,
 906                      theOEOrigins, theInvEdges, theValidEdges, aDMFLVE, aDMFLNE, aDMFLIE,
 907                      aDMFLVIE, aDMEOrLEIm, theInvertedEdges, aMEdgeInvalidByVertex);
 908     //
 909     // save the new splits
 910     if (!pLFIm) {
 911       pLFIm = &theFImages(theFImages.Add(aF, TopTools_ListOfShape()));
 912     }
 913     else {
 914       pLFIm->Clear();
 915     }
 916     pLFIm->Append(aLFImages);
 917     //
 918     aLFDone.Append(aF);
 919   }
 920   //
 921   if (theInvEdges.IsEmpty() && theArtInvFaces.IsEmpty()) {
 922     return;
 923   }
 924   //
 925 #ifdef OFFSET_DEBUG
 926   // show invalid edges
 927   TopoDS_Compound aCEInv1;
 928   BRep_Builder().MakeCompound(aCEInv1);
 929   Standard_Integer aNbEInv = theInvEdges.Extent();
 930   for (i = 1; i <= aNbEInv; ++i) {
 931     const TopoDS_Shape& aE = theInvEdges(i);
 932     BRep_Builder().Add(aCEInv1, aE);
 933   }
 934   // show valid edges
 935   TopoDS_Compound aCEVal1;
 936   BRep_Builder().MakeCompound(aCEVal1);
 937   aNbEInv = theValidEdges.Extent();
 938   for (i = 1; i <= aNbEInv; ++i) {
 939     const TopoDS_Shape& aE = theValidEdges(i);
 940     BRep_Builder().Add(aCEVal1, aE);
 941   }
 942   // show inverted edges
 943   TopoDS_Compound aCEInverted;
 944   BRep_Builder().MakeCompound(aCEInverted);
 945   TopTools_MapIteratorOfMapOfShape aItM(theInvertedEdges);
 946   for (; aItM.More(); aItM.Next()) {
 947     BRep_Builder().Add(aCEInverted, aItM.Value());
 948   }
 949 #endif
 950   //
 951   TopTools_ListOfShape anEmptyList;
 952   // invalid faces inside the holes
 953   TopTools_IndexedMapOfShape aMFInvInHole;
 954   // all hole faces
 955   TopoDS_Compound aFHoles;
 956   aBB.MakeCompound(aFHoles);
 957   // find invalid faces
 958   // considering faces containing only invalid edges as invalid
 959   aItLF.Initialize(aLFDone);
 960   for (; aItLF.More(); aItLF.Next()) {
 961     const TopoDS_Face& aF = TopoDS::Face(aItLF.Value());
 962     TopTools_ListOfShape& aLFImages = theFImages.ChangeFromKey(aF);
 963     //
 964     TopTools_ListOfShape aLFInv;
 965     Standard_Boolean bArtificialCase = theArtInvFaces.IsBound(aF);
 966     if (bArtificialCase) {
 967       aLFInv = aLFImages;
 968     }
 969     else {
 970       // neutral edges
 971       TopTools_ListOfShape* pLNE = aDMFLNE.ChangeSeek(aF);
 972       if (!pLNE) {
 973         pLNE = &anEmptyList;
 974       }
 975       // valid inverted edges
 976       TopTools_ListOfShape* pLIVE = aDMFLVIE.ChangeSeek(aF);
 977       if (!pLIVE) {
 978         pLIVE = &anEmptyList;
 979       }
 980       //
 981       // find faces inside holes wires
 982       TopTools_MapOfShape aMFHoles;
 983       const TopoDS_Face& aFOr = TopoDS::Face(theFacesOrigins.Find(aF));
 984       FindFacesInsideHoleWires(aFOr, aF, aLFImages, theInvertedEdges,
 985                                aDMEOrLEIm, aMFHoles, theDMFNewHoles, aCtx);
 986       //
 987       TopTools_MapIteratorOfMapOfShape aItMH(aMFHoles);
 988       for (; aItMH.More(); aItMH.Next()) {
 989         aBB.Add(aFHoles, aItMH.Value());
 990       }
 991       //
 992       // find invalid faces
 993       FindInvalidFaces(aLFImages, theInvEdges, theValidEdges, aDMFLVE, aDMFLIE,
 994                        *pLNE, *pLIVE, theInvertedEdges, aMEdgeInvalidByVertex,
 995                        aMFHoles, aMFInvInHole, aLFInv);
 996     }
 997     //
 998     if (aLFInv.Extent()) {
 999       if (theAlreadyInvFaces.IsBound(aF)) {
1000         if (theAlreadyInvFaces.Find(aF) > 2) {
1001           if (aLFInv.Extent() == aLFImages.Extent() && !bArtificialCase) {
1002             aLFImages.Clear();
1003           }
1004           //
1005           aLFInv.Clear();
1006         }
1007       }
1008       theInvFaces.Add(aF, aLFInv);
1009     }
1010   }
1011   //
1012   if (theInvFaces.IsEmpty()) {
1013     theInvEdges.Clear();
1014     return;
1015   }
1016   //
1017 #ifdef OFFSET_DEBUG
1018   // show invalid faces
1019   TopoDS_Compound aCFInv1;
1020   BRep_Builder().MakeCompound(aCFInv1);
1021   Standard_Integer aNbFInv = theInvFaces.Extent();
1022   for (i = 1; i <= aNbFInv; ++i) {
1023     const TopTools_ListOfShape& aLFInv = theInvFaces(i);
1024     TopTools_ListIteratorOfListOfShape aItLFInv(aLFInv);
1025     for (; aItLFInv.More(); aItLFInv.Next()) {
1026       const TopoDS_Shape& aFIm = aItLFInv.Value();
1027       BRep_Builder().Add(aCFInv1, aFIm);
1028     }
1029   }
1030 #endif
1031   //
1032   TopTools_IndexedMapOfShape aMERemoved;
1033   // remove invalid splits of faces using inverted edges
1034   RemoveInvalidSplitsByInvertedEdges(theInvertedEdges, theOEOrigins,
1035                                      theInvFaces, theFImages, aMERemoved);
1036   if (theInvFaces.IsEmpty()) {
1037     theInvEdges.Clear();
1038     return;
1039   }
1040   //
1041   // remove invalid splits from valid splits
1042   RemoveInvalidSplitsFromValid(theInvFaces, theArtInvFaces, theInvertedEdges, theFImages);
1043   //
1044   // remove inside faces
1045   TopTools_IndexedMapOfShape aMEInside;
1046   RemoveInsideFaces(theFImages, theInvFaces, theArtInvFaces, theInvEdges,
1047                     aMFToCheckInt, aMFInvInHole, aFHoles, theSSInterfs,
1048                     aMERemoved, aMEInside, theSolids);
1049   //
1050   // make compound of valid splits
1051   TopoDS_Compound aCFIm;
1052   aBB.MakeCompound(aCFIm);
1053   //
1054   aNb = theFImages.Extent();
1055   for (i = 1; i <= aNb; ++i) {
1056     const TopTools_ListOfShape& aLFIm = theFImages(i);
1057     aItLF.Initialize(aLFIm);
1058     for (; aItLF.More(); aItLF.Next()) {
1059       const TopoDS_Shape& aFIm = aItLF.Value();
1060       aBB.Add(aCFIm, aFIm);
1061     }
1062   }
1063   //
1064   TopTools_IndexedDataMapOfShapeListOfShape aDMEF;
1065   TopExp::MapShapesAndAncestors(aCFIm, TopAbs_EDGE, TopAbs_FACE, aDMEF);
1066   //
1067   // filter maps of images and origins
1068   FilterEdgesImages(aCFIm, theOEImages, theOEOrigins);
1069   //
1070   // filter invalid faces
1071   FilterInvalidFaces(theFImages, aDMEF, aMEInside, theInvFaces, theArtInvFaces);
1072   aNb = theInvFaces.Extent();
1073   if (!aNb) {
1074     theInvEdges.Clear();
1075     return;
1076   }
1077   //
1078 #ifdef OFFSET_DEBUG
1079   // show invalid faces
1080   TopoDS_Compound aCFInv;
1081   BRep_Builder().MakeCompound(aCFInv);
1082   aNbFInv = theInvFaces.Extent();
1083   for (i = 1; i <= aNbFInv; ++i) {
1084     const TopTools_ListOfShape& aLFInv = theInvFaces(i);
1085     TopTools_ListIteratorOfListOfShape aItLFInv(aLFInv);
1086     for (; aItLFInv.More(); aItLFInv.Next()) {
1087       const TopoDS_Shape& aFIm = aItLFInv.Value();
1088       BRep_Builder().Add(aCFInv, aFIm);
1089     }
1090   }
1091 #endif
1092   //
1093   // filter invalid edges
1094   FilterInvalidEdges(theInvFaces, theArtInvFaces, aDMFLIE, aMERemoved, theInvEdges);
1095   //
1096 #ifdef OFFSET_DEBUG
1097   // show invalid edges
1098   TopoDS_Compound aCEInv;
1099   BRep_Builder().MakeCompound(aCEInv);
1100   aNbEInv = theInvEdges.Extent();
1101   for (i = 1; i <= aNbEInv; ++i) {
1102     const TopoDS_Shape& aE = theInvEdges(i);
1103     BRep_Builder().Add(aCEInv, aE);
1104   }
1105 #endif
1106   //
1107   theLastInvEdges.Clear();
1108   aNb = theInvEdges.Extent();
1109   for (i = 1; i <= aNb; ++i) {
1110     const TopoDS_Shape& aE = theInvEdges(i);
1111     theEdgesToAvoid.Add(aE);
1112     theLastInvEdges.Add(aE);
1113   }
1114   //
1115   aNb = theInvFaces.Extent();
1116   for (i = 1; i <= aNb; ++i) {
1117     const TopoDS_Shape& aF = theInvFaces.FindKey(i);
1118     if (theAlreadyInvFaces.IsBound(aF)) {
1119       theAlreadyInvFaces.ChangeFind(aF)++;
1120     }
1121     else {
1122       theAlreadyInvFaces.Bind(aF, 1);
1123     }
1124   }
1125 }
1126
1127 //=======================================================================
1128 //function : IntersectTrimmedEdges
1129 //purpose  : Intersection of the trimmed edges among themselves
1130 //=======================================================================
1131 void IntersectTrimmedEdges(const TopTools_ListOfShape& theLF,
1132                            const Handle(BRepAlgo_AsDes)& theAsDes,
1133                            TopTools_DataMapOfShapeListOfShape& theOEImages,
1134                            TopTools_DataMapOfShapeListOfShape& theOEOrigins,
1135                            TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
1136                            Handle(IntTools_Context)& theCtx,
1137                            TopTools_MapOfShape& theNewEdges,
1138                            TopTools_DataMapOfShapeShape& theETrimEInf)
1139 {
1140   if (theLF.IsEmpty()) {
1141     return;
1142   }
1143   //
1144   // get edges to intersect from descendants of the offset faces
1145   BOPCol_ListOfShape aLS;
1146   //
1147   TopTools_ListIteratorOfListOfShape aItLF(theLF);
1148   for (; aItLF.More(); aItLF.Next()) {
1149     const TopoDS_Face& aF = *(TopoDS_Face*)&aItLF.Value();
1150     //
1151     const TopTools_ListOfShape& aLE = theAsDes->Descendant(aF);
1152     TopTools_ListIteratorOfListOfShape aItLE(aLE);
1153     for (; aItLE.More(); aItLE.Next()) {
1154       const TopoDS_Edge& aE = *(TopoDS_Edge*)&aItLE.Value();
1155       //
1156       if (ProcessMicroEdge(aE, theCtx)) {
1157         continue;
1158       }
1159       //
1160       if (theNewEdges.Add(aE)) {
1161         aLS.Append(aE);
1162       }
1163     }
1164   }
1165   //
1166   if (aLS.Extent() < 2) {
1167     // nothing to intersect
1168     return;
1169   }
1170   //
1171   // perform intersection of the edges
1172   BOPAlgo_Builder aGFE;
1173   aGFE.SetArguments(aLS);
1174   aGFE.Perform();
1175   if (aGFE.ErrorStatus()) {
1176     return;
1177   }
1178   //
1179   TopTools_ListOfShape aLA;
1180   // fill map with edges images
1181   BOPCol_ListIteratorOfListOfShape aIt(aLS);
1182   for (; aIt.More(); aIt.Next()) {
1183     const TopoDS_Shape& aE = aIt.Value();
1184     const TopTools_ListOfShape& aLEIm = aGFE.Modified(aE);
1185     if (aLEIm.IsEmpty()) {
1186       continue;
1187     }
1188     //
1189     aLA.Append(aE);
1190     // save images
1191     theOEImages.Bind(aE, aLEIm);
1192     // save origins
1193     TopTools_ListIteratorOfListOfShape aItLE(aLEIm);
1194     for (; aItLE.More(); aItLE.Next()) {
1195       const TopoDS_Shape& aEIm = aItLE.Value();
1196       TopTools_ListOfShape* pLEOr = theOEOrigins.ChangeSeek(aEIm);
1197       if (!pLEOr) {
1198         pLEOr = theOEOrigins.Bound(aEIm, TopTools_ListOfShape());
1199       }
1200       AppendToList(*pLEOr, aE);
1201     }
1202   }
1203   //
1204   UpdateOrigins(aLA, theEdgesOrigins, aGFE);
1205   UpdateIntersectedEdges(aLA, theETrimEInf, aGFE);
1206 }
1207
1208 //=======================================================================
1209 //function : GetEdges
1210 //purpose  : Getting edges from AsDes map to build the splits of faces
1211 //=======================================================================
1212 Standard_Boolean GetEdges(const TopoDS_Face& theFace,
1213                           const Handle(BRepAlgo_AsDes)& theAsDes,
1214                           const TopTools_DataMapOfShapeListOfShape& theEImages,
1215                           const TopTools_MapOfShape& theLastInvEdges,
1216                           const TopTools_IndexedMapOfShape& theInvEdges,
1217                           Handle(IntTools_Context)& theCtx,
1218                           const TopTools_MapOfShape& theModifiedEdges,
1219                           TopoDS_Shape& theEdges,
1220                           TopTools_IndexedMapOfShape& theInv)
1221 {
1222   // get boundary edges
1223   TopTools_MapOfShape aMFBounds;
1224   TopExp_Explorer aExp(theFace, TopAbs_EDGE);
1225   for (; aExp.More(); aExp.Next()) {
1226     const TopoDS_Shape& aE = aExp.Current();
1227     const TopTools_ListOfShape* pLEIm = theEImages.Seek(aE);
1228     if (!pLEIm) {
1229       aMFBounds.Add(aE);
1230     }
1231     else {
1232       TopTools_ListIteratorOfListOfShape aItLE(*pLEIm);
1233       for (; aItLE.More(); aItLE.Next()) {
1234         const TopoDS_Shape& aEIm = aItLE.Value();
1235         aMFBounds.Add(aEIm);
1236       }
1237     }
1238   }
1239   //
1240   BRep_Builder aBB;
1241   Standard_Boolean bFound(Standard_False), bUpdate(Standard_False);
1242   // the resulting edges
1243   TopoDS_Compound anEdges;
1244   aBB.MakeCompound(anEdges);
1245   //
1246   // the edges by which the offset face should be split
1247   const TopTools_ListOfShape& aLE = theAsDes->Descendant(theFace);
1248   TopTools_ListIteratorOfListOfShape aItLE(aLE);
1249   for (; aItLE.More(); aItLE.Next()) {
1250     const TopoDS_Edge& aE = TopoDS::Edge(aItLE.Value());
1251     //
1252     if (!bUpdate) {
1253       bUpdate = theModifiedEdges.Contains(aE);
1254     }
1255     //
1256     const TopTools_ListOfShape* pLEIm = theEImages.Seek(aE);
1257     if (pLEIm) {
1258       TopTools_ListIteratorOfListOfShape aItLEIm(*pLEIm);
1259       for (; aItLEIm.More(); aItLEIm.Next()) {
1260         const TopoDS_Edge& aEIm = TopoDS::Edge(aItLEIm.Value());
1261         //
1262         if (theInvEdges.Contains(aEIm)) {
1263           theInv.Add(aEIm);
1264           if (!bUpdate) {
1265             bUpdate = theLastInvEdges.Contains(aEIm);
1266           }
1267           continue;
1268         }
1269         // check for micro edge
1270         if (ProcessMicroEdge(aEIm, theCtx)) {
1271           continue;
1272         }
1273         //
1274         aBB.Add(anEdges, aEIm);
1275         if (!bFound) {
1276           bFound = !aMFBounds.Contains(aEIm);
1277         }
1278         //
1279         if (!bUpdate) {
1280           bUpdate = theModifiedEdges.Contains(aEIm);
1281         }
1282       }
1283     }
1284     else {
1285       if (theInvEdges.Contains(aE)) {
1286         theInv.Add(aE);
1287         if (!bUpdate) {
1288           bUpdate = theLastInvEdges.Contains(aE);
1289         }
1290         continue;
1291       }
1292       //
1293       if (ProcessMicroEdge(aE, theCtx)) {
1294         continue;
1295       }
1296       aBB.Add(anEdges, aE);
1297       if (!bFound) {
1298         bFound = !aMFBounds.Contains(aE);
1299       }
1300     }
1301   }
1302   //
1303   theEdges = anEdges;
1304   return bFound && bUpdate;
1305 }
1306
1307 //=======================================================================
1308 //function : BuildSplitsOfFace
1309 //purpose  : Building the splits of offset face
1310 //=======================================================================
1311 void BuildSplitsOfFace(const TopoDS_Face& theFace,
1312                        const TopoDS_Shape& theEdges,
1313                        TopTools_DataMapOfShapeShape& theFacesOrigins,
1314                        TopTools_ListOfShape& theLFImages)
1315 {
1316   theLFImages.Clear();
1317   //
1318   // take edges to split the face
1319   BOPCol_ListOfShape aLE;
1320   TopExp_Explorer aExp(theEdges, TopAbs_EDGE);
1321   for (; aExp.More(); aExp.Next()) {
1322     TopoDS_Edge aE = TopoDS::Edge(aExp.Current());
1323     aE.Orientation(TopAbs_FORWARD);
1324     aLE.Append(aE);
1325     aE.Orientation(TopAbs_REVERSED);
1326     aLE.Append(aE);
1327   }
1328   //
1329   TopoDS_Face aFF = theFace;
1330   TopAbs_Orientation anOr = theFace.Orientation();
1331   aFF.Orientation(TopAbs_FORWARD);
1332   //
1333   // build pcurves for edges on the face
1334   BOPTools_AlgoTools2D::BuildPCurveForEdgesOnPlane(aLE, aFF);
1335   //
1336   // build splits of faces
1337   BOPAlgo_BuilderFace aBF;
1338   aBF.SetFace(aFF);
1339   aBF.SetShapes(aLE);
1340   aBF.Perform();
1341   //
1342   const BOPCol_ListOfShape& aLFSp = aBF.Areas();
1343   BOPCol_ListIteratorOfListOfShape aItLF(aLFSp);
1344   for (; aItLF.More(); aItLF.Next()) {
1345     TopoDS_Shape& aFSp = aItLF.ChangeValue();
1346     aFSp.Orientation(anOr);
1347     theLFImages.Append(aFSp);
1348     //
1349     theFacesOrigins.Bind(aFSp, theFace);
1350   }
1351 }
1352
1353 //=======================================================================
1354 //function : BuildSplitsOfFace
1355 //purpose  : Building the splits of offset face
1356 //=======================================================================
1357 void BuildSplitsOfTrimmedFace(const TopoDS_Face& theFace,
1358                               const TopoDS_Shape& theEdges,
1359                               TopTools_ListOfShape& theLFImages)
1360 {
1361   BOPAlgo_Builder aGF;
1362   //
1363   aGF.AddArgument(theFace);
1364   aGF.AddArgument(theEdges);
1365   aGF.Perform();
1366   if (aGF.ErrorStatus()) {
1367     return;
1368   }
1369   //
1370   // splits of the offset shape
1371   theLFImages = aGF.Modified(theFace);
1372 }
1373
1374 //=======================================================================
1375 //function : CheckIfArtificial
1376 //purpose  : Checks if the face is artificially invalid
1377 //=======================================================================
1378 Standard_Boolean CheckIfArtificial(const TopoDS_Shape& theF,
1379                                    const TopTools_ListOfShape& theLFImages,
1380                                    const TopoDS_Shape& theCE,
1381                                    const TopTools_IndexedMapOfShape& theMapEInv,
1382                                    const TopTools_DataMapOfShapeListOfShape& theOEImages,
1383                                    TopTools_MapOfShape& theMENInv,
1384                                    Handle(BRepAlgo_AsDes)& theAsDes)
1385 {
1386   // all boundary edges should be used
1387   TopTools_IndexedMapOfShape aMEUsed;
1388   TopTools_ListIteratorOfListOfShape aItLFIm(theLFImages);
1389   for (; aItLFIm.More(); aItLFIm.Next()) {
1390     const TopoDS_Shape& aFIm = aItLFIm.Value();
1391     TopExp::MapShapes(aFIm, TopAbs_EDGE, aMEUsed);
1392     TopExp::MapShapes(aFIm, TopAbs_VERTEX, aMEUsed);
1393   }
1394   //
1395   TopTools_IndexedDataMapOfShapeListOfShape aMVE;
1396   TopExp::MapShapesAndAncestors(theCE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
1397   //
1398   Standard_Integer i, aNb = theMapEInv.Extent();
1399   for (i = 1; i <= aNb; ++i) {
1400     const TopoDS_Shape& aEInv = theMapEInv(i);
1401     TopExp_Explorer aExpV(aEInv, TopAbs_VERTEX);
1402     for (; aExpV.More(); aExpV.Next()) {
1403       const TopoDS_Shape& aVEInv = aExpV.Current();
1404       const TopTools_ListOfShape* pLENInv = aMVE.Seek(aVEInv);
1405       if (pLENInv) {
1406         TopTools_ListIteratorOfListOfShape aItLEInv(*pLENInv);
1407         for (; aItLEInv.More(); aItLEInv.Next()) {
1408           const TopoDS_Shape& aENInv = aItLEInv.Value();
1409           if (!aMEUsed.Contains(aENInv)) {
1410             theMENInv.Add(aENInv);
1411           }
1412         }
1413       }
1414     }
1415   }
1416   //
1417   if (theMENInv.IsEmpty()) {
1418     return Standard_False;
1419   }
1420   //
1421   TopTools_IndexedMapOfShape aMEFound;
1422   TopExp::MapShapes(theCE, TopAbs_EDGE, aMEFound);
1423   //
1424   const TopTools_ListOfShape& aLE = theAsDes->Descendant(theF);
1425   TopTools_ListIteratorOfListOfShape aItLE(aLE);
1426   for (; aItLE.More(); aItLE.Next()) {
1427     const TopoDS_Edge& aE = TopoDS::Edge(aItLE.Value());
1428     //
1429     if (theOEImages.IsBound(aE)) {
1430       Standard_Boolean bChecked = Standard_False;
1431       const TopTools_ListOfShape& aLEIm = theOEImages.Find(aE);
1432       TopTools_ListIteratorOfListOfShape aItLEIm(aLEIm);
1433       for (; aItLEIm.More(); aItLEIm.Next()) {
1434         const TopoDS_Edge& aEIm = TopoDS::Edge(aItLEIm.Value());
1435         if (!aMEFound.Contains(aEIm) || theMENInv.Contains(aEIm)) {
1436           continue;
1437         }
1438         //
1439         bChecked = Standard_True;
1440         if (aMEUsed.Contains(aEIm)) {
1441           break;
1442         }
1443       }
1444       //
1445       if (bChecked && !aItLEIm.More()) {
1446         break;
1447       }
1448     }
1449     else {
1450       if (aMEFound.Contains(aE) && !theMENInv.Contains(aE) && !aMEUsed.Contains(aE)) {
1451         break;
1452       }
1453     }
1454   }
1455   //
1456   return aItLE.More();
1457 }
1458
1459 //=======================================================================
1460 //function : FindInvalidEdges
1461 //purpose  : Looking for the invalid edges
1462 //=======================================================================
1463 void FindInvalidEdges(const TopoDS_Face& theF,
1464                       const TopTools_ListOfShape& theLFImages,
1465                       const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
1466                       const TopTools_DataMapOfShapeShape& theFacesOrigins,
1467                       const TopTools_DataMapOfShapeListOfShape& theOEImages,
1468                       const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
1469                       TopTools_IndexedMapOfShape& theInvEdges,
1470                       TopTools_IndexedMapOfShape& theValidEdges,
1471                       TopTools_DataMapOfShapeListOfShape& theDMFLVE,
1472                       TopTools_DataMapOfShapeListOfShape& theDMFLNE,
1473                       TopTools_DataMapOfShapeListOfShape& theDMFLIE,
1474                       TopTools_DataMapOfShapeListOfShape& theDMFLVIE,
1475                       TopTools_DataMapOfShapeListOfShape& theDMEOrLEIm,
1476                       TopTools_MapOfShape& theMEInverted,
1477                       TopTools_MapOfShape& theEdgesInvalidByVertex)
1478 {
1479   // Edge is considered as invalid in the following cases:
1480   // 1. Its orientation on the face has changed comparing to the originals edge and face;
1481   // 2. The vertices of the edge have changed places comparing to the originals edge and face.
1482   //
1483   // The edges created from vertices, i.e. as intersection between two faces connected only
1484   // by VERTEX, will also be checked on validity. For these edges the correct orientation will
1485   // be defined by the edges on the original face adjacent to the connection vertex
1486
1487   // original face
1488   const TopoDS_Face& aFOr = *(TopoDS_Face*)&theFacesOrigins.Find(theF);
1489   // invalid edges
1490   TopTools_IndexedMapOfShape aMEInv;
1491   // valid edges
1492   TopTools_MapOfShape aMEVal;
1493   // internal edges
1494   TopTools_MapOfShape aMEInt;
1495   //
1496   // maps for checking the inverted edges
1497   TopTools_IndexedDataMapOfShapeListOfShape aDMVE, aDMEF;
1498   TopTools_IndexedMapOfShape aMEdges;
1499   //
1500   TopTools_ListIteratorOfListOfShape aItLF(theLFImages);
1501   for (; aItLF.More(); aItLF.Next()) {
1502     const TopoDS_Face& aFIm = *(TopoDS_Face*)&aItLF.Value();
1503     //
1504     TopExp_Explorer aExp(aFIm, TopAbs_EDGE);
1505     for (; aExp.More(); aExp.Next()) {
1506       const TopoDS_Shape& aE = aExp.Current();
1507       // keep all edges
1508       aMEdges.Add(aE);
1509       //
1510       // keep connection from edges to faces
1511       TopTools_ListOfShape* pLF = aDMEF.ChangeSeek(aE);
1512       if (!pLF) {
1513         pLF = &aDMEF(aDMEF.Add(aE, TopTools_ListOfShape()));
1514       }
1515       AppendToList(*pLF, aFIm);
1516       //
1517       // keep connection from vertices to edges
1518       TopoDS_Iterator aItV(aE);
1519       for (; aItV.More(); aItV.Next()) {
1520         const TopoDS_Shape& aV = aItV.Value();
1521         //
1522         TopTools_ListOfShape* pLE = aDMVE.ChangeSeek(aV);
1523         if (!pLE) {
1524           pLE = &aDMVE(aDMVE.Add(aV, TopTools_ListOfShape()));
1525         }
1526         AppendToList(*pLE, aE);
1527       }
1528     }
1529   }
1530   //
1531   // the map will be used to find the edges on the original face
1532   // adjacent to the same vertex. It will be filled at first necessity;
1533   TopTools_IndexedDataMapOfShapeListOfShape aDMVEFOr;
1534   //
1535   aItLF.Initialize(theLFImages);
1536   for (; aItLF.More(); aItLF.Next()) {
1537     const TopoDS_Face& aFIm = *(TopoDS_Face*)&aItLF.Value();
1538     //
1539     // valid edges for this split
1540     TopTools_ListOfShape aLVE;
1541     // invalid edges for this split
1542     TopTools_ListOfShape aLIE;
1543     //
1544     TopExp_Explorer aExp(aFIm, TopAbs_EDGE);
1545     for (; aExp.More(); aExp.Next()) {
1546       const TopoDS_Edge& aEIm = *(TopoDS_Edge*)&aExp.Current();
1547       //
1548       if (aEIm.Orientation() == TopAbs_INTERNAL) {
1549         aMEInt.Add(aEIm);
1550         continue;
1551       }
1552       //
1553       if (!theEdgesOrigins.IsBound(aEIm)) {
1554         continue;
1555       }
1556       //
1557       const TopTools_ListOfShape& aLEOr = theEdgesOrigins.Find(aEIm);
1558       if (aLEOr.IsEmpty()) {
1559         continue;
1560       }
1561       //
1562       Standard_Integer aNbVOr = 0;
1563       TopTools_ListIteratorOfListOfShape aItLEO(aLEOr);
1564       for (; aItLEO.More(); aItLEO.Next()) {
1565         if (aItLEO.Value().ShapeType() == TopAbs_VERTEX) {
1566           ++aNbVOr;
1567         }
1568       }
1569       //
1570       TopTools_MapOfShape aME, aMV;
1571       Standard_Boolean bInvalid = Standard_False, bChecked = Standard_False;
1572       Standard_Integer aNbP = NbPoints(aEIm);
1573       Standard_Boolean bUseVertex = !aNbVOr ? Standard_False :
1574         (aNbVOr == 1 &&
1575          aDMEF.FindFromKey(aEIm).Extent() == 1 &&
1576          !theOEOrigins.IsBound(aEIm));
1577       //
1578       aItLEO.Initialize(aLEOr);
1579       for (; aItLEO.More(); aItLEO.Next()) {
1580         const TopoDS_Shape& aSOr = aItLEO.Value();
1581         Standard_Boolean bVertex = (aSOr.ShapeType() == TopAbs_VERTEX);
1582         //
1583         TopoDS_Shape aEOrF;
1584         if (bVertex) {
1585           // for some cases it is impossible to check the validity of the edge
1586           if (!bUseVertex) {
1587             continue;
1588           }
1589           // find edges on the original face adjacent to this vertex
1590           if (aDMVEFOr.IsEmpty()) {
1591             // fill the map
1592             TopExp::MapShapesAndAncestors(aFOr, TopAbs_VERTEX, TopAbs_EDGE, aDMVEFOr);
1593           }
1594           //
1595           TopTools_ListOfShape *pLEFOr = aDMVEFOr.ChangeSeek(aSOr);
1596           if (pLEFOr) {
1597             TopoDS_Compound aCEOr;
1598             BRep_Builder().MakeCompound(aCEOr);
1599             TopTools_ListIteratorOfListOfShape aItLEFOr(*pLEFOr);
1600             for (; aItLEFOr.More(); aItLEFOr.Next()) {
1601               const TopoDS_Shape& aEOr = aItLEFOr.Value();
1602               BRep_Builder().Add(aCEOr, aEOr);
1603             }
1604             aEOrF = aCEOr;
1605           }
1606         }
1607         else {
1608           FindShape(aSOr, aFOr, aEOrF);
1609           //
1610           TopTools_ListOfShape *pLEIm = theDMEOrLEIm.ChangeSeek(aSOr);
1611           if (!pLEIm) {
1612             pLEIm = theDMEOrLEIm.Bound(aSOr, TopTools_ListOfShape());
1613           }
1614           AppendToList(*pLEIm, aEIm);
1615         }
1616         //
1617         if (aEOrF.IsNull()) {
1618           // the edge has not been found
1619           continue;
1620         }
1621         //
1622         // Check orientations of the image edge and original edge.
1623         // In case the 3d curves are having the same direction the orientations
1624         // must be the same. Otherwise the orientations should also be different.
1625         //
1626         // get average tangent vector for each curve taking into account
1627         // the orientations of the edges, i.e. the edge is reversed
1628         // the vector is reversed as well
1629         gp_Vec aVSum1 = GetAverageTangent(aEIm, aNbP);
1630         gp_Vec aVSum2 = GetAverageTangent(aEOrF, aNbP);
1631         //
1632         aVSum1.Normalize();
1633         aVSum2.Normalize();
1634         //
1635         Standard_Real aCos = aVSum1.Dot(aVSum2);
1636         if (!bVertex) {
1637           if (Abs(aCos) < 0.9999) {
1638             continue;
1639           }
1640           //
1641           aME.Add(aEOrF);
1642           TopExp_Explorer aExpE(aEOrF, TopAbs_VERTEX);
1643           for (; aExpE.More(); aExpE.Next()) {
1644             const TopoDS_Shape& aV = aExpE.Current();
1645             aMV.Add(aV);
1646           }
1647         }
1648         //
1649         if (aCos < Precision::Confusion()) {
1650           bInvalid = Standard_True;
1651           if (bVertex) {
1652             theEdgesInvalidByVertex.Add(aEIm);
1653           }
1654         }
1655         bChecked = Standard_True;
1656       }
1657       //
1658       if (!bChecked) {
1659         continue;
1660       }
1661       //
1662       Standard_Integer aNbE = aME.Extent(), aNbV = aMV.Extent();
1663       if ((aNbE > 1) && (aNbV == 2*aNbE)) {
1664         continue;
1665       }
1666       //
1667       if (bInvalid) {
1668         theInvEdges.Add(aEIm);
1669         aLIE.Append(aEIm);
1670         aMEInv.Add(aEIm);
1671         continue;
1672       }
1673       //
1674       // check if the edge has been inverted
1675       Standard_Boolean bInverted = !aNbE ? Standard_False :
1676         CheckInverted(aEIm, aFOr, theOEImages, theOEOrigins,
1677           theEdgesOrigins, aDMVE, aMEdges, theMEInverted);
1678       //
1679       if (!bInverted || !aNbVOr) {
1680         theValidEdges.Add(aEIm);
1681         aLVE.Append(aEIm);
1682         aMEVal.Add(aEIm);
1683       }
1684     }
1685     //
1686     // valid edges
1687     if (aLVE.Extent()) {
1688       theDMFLVE.Bind(aFIm, aLVE);
1689     }
1690     //
1691     // invalid edges
1692     if (aLIE.Extent()) {
1693       theDMFLIE.Bind(aFIm, aLIE);
1694     }
1695   }
1696   //
1697   // process invalid edges:
1698   // check for the inverted edges
1699   TopTools_ListOfShape aLVIE;
1700   // fill neutral edges
1701   TopTools_ListOfShape aLNE;
1702   //
1703   Standard_Integer i, aNbEInv = aMEInv.Extent();
1704   for (i = 1; i <= aNbEInv; ++i) {
1705     const TopoDS_Shape& aEIm = aMEInv(i);
1706     //
1707     // neutral edges - on the splits of the same offset face
1708     // it is valid for one split and invalid for other
1709     if (aMEVal.Contains(aEIm)) {
1710       aLNE.Append(aEIm);
1711       continue;
1712     }
1713     //
1714     // the inverted images of the origins of invalid edges should also be invalid
1715     if (!theMEInverted.Contains(aEIm)) {
1716       continue;
1717     }
1718     //
1719     const TopTools_ListOfShape* pLOEOr = theOEOrigins.Seek(aEIm);
1720     if (!pLOEOr) {
1721       continue;
1722     }
1723     //
1724     TopTools_ListIteratorOfListOfShape aItLOEOr(*pLOEOr);
1725     for (; aItLOEOr.More(); aItLOEOr.Next()) {
1726       const TopoDS_Shape& aOEOr = aItLOEOr.Value();
1727       const TopTools_ListOfShape& aLEIm1 = theOEImages.Find(aOEOr);
1728       //
1729       TopTools_ListIteratorOfListOfShape aItLEIm1(aLEIm1);
1730       for (; aItLEIm1.More(); aItLEIm1.Next()) {
1731         const TopoDS_Shape& aEIm1 = aItLEIm1.Value();
1732         if (aMEdges.Contains(aEIm1) &&
1733             !aMEInv.Contains(aEIm1) && !aMEInt.Contains(aEIm1) &&
1734             theMEInverted.Contains(aEIm1)) {
1735           theInvEdges.Add(aEIm1);
1736           aLVIE.Append(aEIm1);
1737         }
1738       }
1739     }
1740   }
1741   //
1742   if (aLNE.Extent()) {
1743     theDMFLNE.Bind(theF, aLNE);
1744   }
1745   //
1746   if (aLVIE.Extent()) {
1747     theDMFLVIE.Bind(theF, aLVIE);
1748   }
1749 }
1750
1751 //=======================================================================
1752 //function : FindInvalidFaces
1753 //purpose  : Looking for the invalid faces by analyzing their invalid edges
1754 //=======================================================================
1755 void FindInvalidFaces(TopTools_ListOfShape& theLFImages,
1756                       const TopTools_IndexedMapOfShape& theInvEdges,
1757                       const TopTools_IndexedMapOfShape& theValidEdges,
1758                       const TopTools_DataMapOfShapeListOfShape& theDMFLVE,
1759                       const TopTools_DataMapOfShapeListOfShape& theDMFLIE,
1760                       const TopTools_ListOfShape& theLENeutral,
1761                       const TopTools_ListOfShape& theLEValInverted,
1762                       const TopTools_MapOfShape& theMEInverted,
1763                       const TopTools_MapOfShape& theEdgesInvalidByVertex,
1764                       const TopTools_MapOfShape& theMFHoles,
1765                       TopTools_IndexedMapOfShape& theMFInvInHole,
1766                       TopTools_ListOfShape& theInvFaces)
1767 {
1768   // The face should be considered as invalid in the following cases:
1769   // 1. It has been reverted, i.e. at least two not connected edges
1770   //    have changed orientation (i.e. invalid). In this case all edges,
1771   //    should be invalid for that face, because edges have also been reverted;
1772   // 2. All checked edges of the face are invalid for this face;
1773   // The face should be removed from the splits in the following cases:
1774   // 1. All checked edges of the face are invalid for this one, but valid for
1775   //    some other face in this list of splits.
1776   // The face will be kept in the following cases:
1777   // 1. Some of the edges are valid for this face.
1778   Standard_Boolean bHasValid, bAllValid, bAllInvalid, bHasReallyInvalid, bAllInvNeutral;
1779   Standard_Boolean bValid, bValidLoc, bInvalid, bInvalidLoc, bNeutral;
1780   Standard_Integer i, aNbChecked;
1781   //
1782   // neutral edges
1783   TopTools_MapOfShape aMEN;
1784   for (TopTools_ListIteratorOfListOfShape aItLE(theLENeutral); aItLE.More(); aItLE.Next())
1785   {
1786     aMEN.Add(aItLE.Value());
1787   }
1788   //
1789   // valid inverted edges
1790   TopTools_MapOfShape aMEValInverted;
1791   for (TopTools_ListIteratorOfListOfShape aItLE(theLEValInverted); aItLE.More(); aItLE.Next())
1792   {
1793     aMEValInverted.Add(aItLE.Value());
1794   }
1795   //
1796   Standard_Boolean bCheckInverted = (theLFImages.Extent() == 1);
1797   //
1798   // neutral edges to remove
1799   TopTools_IndexedMapOfShape aMENRem;
1800   //
1801   // faces for post treat
1802   TopTools_ListOfShape aLFPT;
1803   //
1804   TopTools_ListIteratorOfListOfShape aItLF(theLFImages);
1805   for (; aItLF.More(); ) {
1806     const TopoDS_Face& aFIm = *(TopoDS_Face*)&aItLF.Value();
1807     //
1808     // valid edges for this split
1809     TopTools_MapOfShape aMVE;
1810     // invalid edges for this split
1811     TopTools_MapOfShape aMIE;
1812     //
1813     for (i = 0; i < 2; ++i) {
1814       TopTools_MapOfShape& aME = !i ? aMVE : aMIE;
1815       const TopTools_ListOfShape* pLE = !i ? theDMFLVE.Seek(aFIm) : theDMFLIE.Seek(aFIm);
1816       if (pLE) {
1817         TopTools_ListIteratorOfListOfShape aItLE(*pLE);
1818         for (; aItLE.More(); aItLE.Next()) {
1819           const TopoDS_Shape& aE = aItLE.Value();
1820           aME.Add(aE);
1821         }
1822       }
1823     }
1824     //
1825     bHasValid = Standard_False;
1826     bAllValid = Standard_True;
1827     bAllInvalid = Standard_True;
1828     bHasReallyInvalid = Standard_False;
1829     bAllInvNeutral = Standard_True;
1830     aNbChecked = 0;
1831     //
1832     const TopoDS_Wire& aWIm = BRepTools::OuterWire(aFIm);
1833     TopExp_Explorer aExp(aWIm, TopAbs_EDGE);
1834     for (; aExp.More(); aExp.Next()) {
1835       const TopoDS_Shape& aEIm = aExp.Current();
1836       //
1837       bValid = theValidEdges.Contains(aEIm);
1838       bInvalid = theInvEdges.Contains(aEIm);
1839       //
1840       if (!bValid && !bInvalid) {
1841         // edge has not been checked for some reason
1842         continue;
1843       }
1844       //
1845       ++aNbChecked;
1846       //
1847       bInvalidLoc = aMIE.Contains(aEIm);
1848       bHasReallyInvalid = bInvalidLoc && !bValid && !theEdgesInvalidByVertex.Contains(aEIm);
1849       if (bHasReallyInvalid) {
1850         break;
1851       }
1852       //
1853       bNeutral = aMEN.Contains(aEIm);
1854       bValidLoc = aMVE.Contains(aEIm);
1855       //
1856       if (!bInvalid && bCheckInverted) {
1857         bInvalid = theMEInverted.Contains(aEIm);
1858       }
1859       //
1860       if (bValidLoc && (bNeutral || aMEValInverted.Contains(aEIm))) {
1861         bHasValid = Standard_True;
1862       }
1863       //
1864       bAllValid = bAllValid && bValidLoc;
1865       bAllInvalid = bAllInvalid && bInvalid;
1866       bAllInvNeutral = bAllInvNeutral && bAllInvalid && bNeutral;
1867     }
1868     //
1869     if (!aNbChecked) {
1870       aItLF.Next();
1871       continue;
1872     }
1873     //
1874     if (!bHasReallyInvalid && (bAllInvNeutral && !bHasValid) && (aNbChecked > 1)) {
1875       // remove edges from neutral
1876       TopExp::MapShapes(aFIm, TopAbs_EDGE, aMENRem);
1877       // remove face
1878       theLFImages.Remove(aItLF);
1879       continue;
1880     }
1881     //
1882     if (bHasReallyInvalid || (bAllInvalid &&
1883                              !(bHasValid || bAllValid) &&
1884                              !(bAllInvNeutral && (aNbChecked == 1)))) {
1885       theInvFaces.Append(aFIm);
1886       if (theMFHoles.Contains(aFIm)) {
1887         theMFInvInHole.Add(aFIm);
1888       }
1889       aItLF.Next();
1890       continue;
1891     }
1892     //
1893     if (theMFHoles.Contains(aFIm)) {
1894       // remove edges from neutral
1895       TopExp::MapShapes(aFIm, TopAbs_EDGE, aMENRem);
1896       // remove face
1897       theLFImages.Remove(aItLF);
1898       continue;
1899     }
1900     //
1901     if (!bAllInvNeutral) {
1902       aLFPT.Append(aFIm);
1903     }
1904     else {
1905       // remove edges from neutral
1906       TopExp::MapShapes(aFIm, TopAbs_EDGE, aMENRem);
1907     }
1908     aItLF.Next();
1909   }
1910   //
1911   if (aLFPT.IsEmpty() || aMENRem.IsEmpty()) {
1912     return;
1913   }
1914   //
1915   Standard_Integer aNb = aMENRem.Extent();
1916   for (i = 1; i <= aNb; ++i) {
1917     aMEN.Remove(aMENRem(i));
1918   }
1919   //
1920   // check the splits once more
1921   aItLF.Initialize(aLFPT);
1922   for (; aItLF.More(); aItLF.Next()) {
1923     const TopoDS_Face& aFIm = *(TopoDS_Face*)&aItLF.Value();
1924     //
1925     // valid edges for this split
1926     TopTools_MapOfShape aMVE;
1927     const TopTools_ListOfShape* pLVE = theDMFLVE.Seek(aFIm);
1928     if (pLVE) {
1929       TopTools_ListIteratorOfListOfShape aItLE(*pLVE);
1930       for (; aItLE.More(); aItLE.Next()) {
1931         const TopoDS_Shape& aE = aItLE.Value();
1932         aMVE.Add(aE);
1933       }
1934     }
1935     //
1936     bHasValid = Standard_False;
1937     bAllValid = Standard_True;
1938     bAllInvalid = Standard_True;
1939     //
1940     const TopoDS_Wire& aWIm = BRepTools::OuterWire(aFIm);
1941     TopExp_Explorer aExp(aWIm, TopAbs_EDGE);
1942     for (; aExp.More(); aExp.Next()) {
1943       const TopoDS_Shape& aEIm = aExp.Current();
1944       //
1945       bValid = theValidEdges.Contains(aEIm);
1946       bInvalid = theInvEdges.Contains(aEIm);
1947       bNeutral = aMEN.Contains(aEIm);
1948       bValidLoc = aMVE.Contains(aEIm);
1949       //
1950       if (!bInvalid && bCheckInverted) {
1951         bInvalid = theMEInverted.Contains(aEIm);
1952       }
1953       //
1954       if (bValidLoc && (bNeutral || aMEValInverted.Contains(aEIm))) {
1955         bHasValid = Standard_True;
1956       }
1957       //
1958       bAllValid = bAllValid && bValidLoc;
1959       bAllInvalid = bAllInvalid && bInvalid;
1960     }
1961     //
1962     if (bAllInvalid && !bHasValid && !bAllValid) {
1963       theInvFaces.Append(aFIm);
1964     }
1965   }
1966 }
1967
1968 //=======================================================================
1969 //function : FindFacesInsideHoleWires
1970 //purpose  : Find faces inside holes wires from the original face
1971 //=======================================================================
1972 void FindFacesInsideHoleWires(const TopoDS_Face& theFOrigin,
1973                               const TopoDS_Face& theFOffset,
1974                               const TopTools_ListOfShape& theLFImages,
1975                               const TopTools_MapOfShape& theInvertedEdges,
1976                               const TopTools_DataMapOfShapeListOfShape& theDMEOrLEIm,
1977                               TopTools_MapOfShape& theMFHoles,
1978                               TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
1979                               Handle(IntTools_Context)& theContext)
1980 {
1981   if (theLFImages.IsEmpty()) {
1982     return;
1983   }
1984   //
1985   // find all hole wires in the original face
1986   TopTools_ListOfShape aLHoleWires;
1987   const TopoDS_Wire& anOuterWire = BRepTools::OuterWire(theFOrigin);
1988   TopExp_Explorer aExpW(theFOrigin, TopAbs_WIRE);
1989   for (; aExpW.More(); aExpW.Next()) {
1990     const TopoDS_Wire& aHoleWire = TopoDS::Wire(aExpW.Current());
1991     if (!aHoleWire.IsSame(anOuterWire) && aHoleWire.Orientation() != TopAbs_INTERNAL) {
1992       aLHoleWires.Append(aHoleWire);
1993     }
1994   }
1995   //
1996   if (aLHoleWires.IsEmpty()) {
1997     // no holes in the face
1998     return;
1999   }
2000   //
2001   TopTools_ListOfShape *pLFNewHoles = theDMFNewHoles.ChangeSeek(theFOrigin);
2002   //
2003   if (!pLFNewHoles) {
2004     pLFNewHoles = theDMFNewHoles.Bound(theFOrigin, TopTools_ListOfShape());
2005   }
2006   if (pLFNewHoles->IsEmpty()) {
2007     //
2008     // find the faces representing holes in the images of the faces:
2009     // 1. for each original hole wire try to build its image
2010     // 2. build the new planar face from the images
2011     //
2012     // map vertices and edges of the splits
2013     TopTools_IndexedMapOfShape aMESplits;
2014     TopTools_ListIteratorOfListOfShape aItLF(theLFImages);
2015     for (; aItLF.More(); aItLF.Next()) {
2016       TopExp::MapShapes(aItLF.Value(), TopAbs_EDGE, aMESplits);
2017     }
2018     //
2019     TopTools_ListIteratorOfListOfShape aItLW(aLHoleWires);
2020     for (; aItLW.More(); aItLW.Next()) {
2021       const TopoDS_Wire& aHoleWire = TopoDS::Wire(aItLW.Value());
2022       // find images of all edges of the original wire
2023       TopTools_IndexedMapOfShape aMEImWire;
2024       TopoDS_Iterator aItE(aHoleWire);
2025       for (; aItE.More(); aItE.Next()) {
2026         const TopoDS_Shape& aEOr = aItE.Value();
2027         const TopTools_ListOfShape *pLEIm = theDMEOrLEIm.Seek(aEOr);
2028         if (!pLEIm || pLEIm->IsEmpty()) {
2029           continue;
2030         }
2031         TopTools_ListIteratorOfListOfShape aItLEIm(*pLEIm);
2032         for (; aItLEIm.More(); aItLEIm.Next()) {
2033           const TopoDS_Shape& aEIm = aItLEIm.Value();
2034           if (aMESplits.Contains(aEIm)) {
2035             aMEImWire.Add(aEIm);
2036           }
2037         }
2038       }
2039       //
2040       if (aMEImWire.IsEmpty()) {
2041         continue;
2042       }
2043       //
2044       // build new planar face using these edges
2045       BOPCol_ListOfShape aLE;
2046       Standard_Integer i, aNbE = aMEImWire.Extent();
2047       for (i = 1; i <= aNbE; ++i) {
2048         aLE.Append(aMEImWire(i).Oriented(TopAbs_FORWARD));
2049         aLE.Append(aMEImWire(i).Oriented(TopAbs_REVERSED));
2050       }
2051       //
2052       BOPAlgo_BuilderFace aBF;
2053       aBF.SetFace(TopoDS::Face(theFOffset.Oriented(TopAbs_FORWARD)));
2054       aBF.SetShapes(aLE);
2055       aBF.Perform();
2056       //
2057       const BOPCol_ListOfShape& aLFNew = aBF.Areas();
2058       if (aLFNew.IsEmpty()) {
2059         continue;
2060       }
2061       //
2062       // check if outer edges in the new faces are not inverted
2063       // because the inverted edges mean that the hole has been
2064       // filled during offset and there will be no faces to remove
2065       TopTools_IndexedDataMapOfShapeListOfShape aDMEFNew;
2066       TopTools_ListIteratorOfListOfShape aItLFNew(aLFNew);
2067       for (; aItLFNew.More(); aItLFNew.Next()) {
2068         TopExp::MapShapesAndAncestors(aItLFNew.Value(), TopAbs_EDGE, TopAbs_FACE, aDMEFNew);
2069       }
2070       //
2071       aNbE = aDMEFNew.Extent();
2072       for (i = 1; i <= aNbE; ++i) {
2073         if (aDMEFNew(i).Extent() == 1) {
2074           const TopoDS_Shape& aE = aDMEFNew.FindKey(i);
2075           if (theInvertedEdges.Contains(aE)) {
2076             break;
2077           }
2078         }
2079       }
2080       //
2081       if (i <= aNbE) {
2082         continue;
2083       }
2084       //
2085       aItLFNew.Initialize(aLFNew);
2086       for (; aItLFNew.More(); aItLFNew.Next()) {
2087         pLFNewHoles->Append(aItLFNew.Value());
2088       }
2089     }
2090   }
2091   //
2092   // among the splits of the offset face find those that are
2093   // located inside the hole faces
2094   //
2095   TopTools_ListIteratorOfListOfShape aItLF(theLFImages);
2096   for (; aItLF.More(); aItLF.Next()) {
2097     const TopoDS_Face& aFIm = TopoDS::Face(aItLF.Value());
2098     //
2099     // get the point inside the face and classify it relatively hole faces
2100     gp_Pnt aP3D;
2101     gp_Pnt2d aP2D;
2102     Standard_Integer iErr = BOPTools_AlgoTools3D::PointInFace(aFIm, aP3D, aP2D, theContext);
2103     if (iErr) {
2104       continue;
2105     }
2106     //
2107     Standard_Real aTol = BRep_Tool::Tolerance(aFIm);
2108     //
2109     TopTools_ListIteratorOfListOfShape aItLFNew(*pLFNewHoles);
2110     for (; aItLFNew.More(); aItLFNew.Next()) {
2111       const TopoDS_Face& aFNew = TopoDS::Face(aItLFNew.Value());
2112       if (theContext->IsValidPointForFace(aP3D, aFNew, aTol)) {
2113         // the face is classified as IN
2114         theMFHoles.Add(aFIm);
2115         break;
2116       }
2117     }
2118   }
2119 }
2120
2121 //=======================================================================
2122 //function : GetAverageTangent
2123 //purpose  : Computes average tangent vector along the curve
2124 //=======================================================================
2125 gp_Vec GetAverageTangent(const TopoDS_Shape& theS,
2126                          const Standard_Integer theNbP)
2127 {
2128   gp_Vec aVA;
2129   TopExp_Explorer aExp(theS, TopAbs_EDGE);
2130   for (; aExp.More(); aExp.Next()) {
2131     const TopoDS_Edge& aE = *(TopoDS_Edge*)&aExp.Current();
2132     //
2133     Standard_Real aT1, aT2;
2134     const Handle(Geom_Curve)& aC = BRep_Tool::Curve(aE, aT1, aT2);
2135     //
2136     gp_Pnt aP;
2137     gp_Vec aV, aVSum;
2138     Standard_Real aT = aT1;
2139     Standard_Real aDt = (aT2 - aT1) / theNbP;
2140     while (aT <= aT2) {
2141       aC->D1(aT, aP, aV);
2142       aVSum += aV.Normalized();
2143       aT += aDt;
2144     }
2145     //
2146     if (aE.Orientation() == TopAbs_REVERSED) {
2147       aVSum.Reverse();
2148     }
2149     //
2150     aVA += aVSum;
2151   }
2152   return aVA;
2153 }
2154
2155 //=======================================================================
2156 //function : CheckInverted
2157 //purpose  : Checks if the edge has been inverted
2158 //=======================================================================
2159 Standard_Boolean CheckInverted(const TopoDS_Edge& theEIm,
2160                                const TopoDS_Face& theFOr,
2161                                const TopTools_DataMapOfShapeListOfShape& theOEImages,
2162                                const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
2163                                const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
2164                                const TopTools_IndexedDataMapOfShapeListOfShape& theDMVE,
2165                                const TopTools_IndexedMapOfShape& theMEdges,
2166                                TopTools_MapOfShape& theMEInverted)
2167 {
2168   // It is necessary to compare the direction from first vertex
2169   // to the last vertex on the original edge with the
2170   // same direction on the new edge. If the directions
2171   // will be different - the edge has been inverted.
2172   //
2173   TopoDS_Vertex aVI1, aVI2; // vertices on the offset edge
2174   TopoDS_Vertex aVO1, aVO2; // vertices on the original edge
2175   //
2176   Standard_Integer i;
2177   // find vertices of the offset shape
2178   TopExp::Vertices(theEIm, aVI1, aVI2);
2179   //
2180   // find images
2181   TopTools_ListOfShape aLEImages;
2182   if (theOEOrigins.IsBound(theEIm)) {
2183     TopoDS_Wire anImages;
2184     BRep_Builder().MakeWire(anImages);
2185     //
2186     TopTools_MapOfShape aMImFence;
2187     const TopTools_ListOfShape& aLOffsetOr = theOEOrigins.Find(theEIm);
2188     TopTools_ListIteratorOfListOfShape aItOffset(aLOffsetOr);
2189     for (; aItOffset.More(); aItOffset.Next()) {
2190       const TopoDS_Shape& aEOffsetOr = aItOffset.Value();
2191       const TopTools_ListOfShape& aLImages = theOEImages.Find(aEOffsetOr);
2192       //
2193       TopTools_ListIteratorOfListOfShape aItImages(aLImages);
2194       for (; aItImages.More(); aItImages.Next()) {
2195         const TopoDS_Edge& anIm = *(TopoDS_Edge*)&aItImages.Value();
2196         if (theMEdges.Contains(anIm) && aMImFence.Add(anIm)) {
2197           BRep_Builder().Add(anImages, anIm);
2198           aLEImages.Append(anIm);
2199         }
2200       }
2201     }
2202     //
2203     // find alone vertices
2204     TopoDS_Vertex aVW1, aVW2;
2205     TopTools_IndexedDataMapOfShapeListOfShape aDMImVE;
2206     TopExp::MapShapesAndAncestors(anImages, TopAbs_VERTEX, TopAbs_EDGE, aDMImVE);
2207     //
2208     TopTools_ListOfShape aLVAlone;
2209     Standard_Integer aNb = aDMImVE.Extent();
2210     for (i = 1; i <= aNb; ++i) {
2211       const TopTools_ListOfShape& aLImE = aDMImVE(i);
2212       if (aLImE.Extent() == 1) {
2213         aLVAlone.Append(aDMImVE.FindKey(i));
2214       }
2215     }
2216     //
2217     if (aLVAlone.Extent() > 1) {
2218       aVW1 = *(TopoDS_Vertex*)&aLVAlone.First();
2219       aVW2 = *(TopoDS_Vertex*)&aLVAlone.Last();
2220       //
2221       // check distances
2222       const gp_Pnt& aPI1 = BRep_Tool::Pnt(aVI1);
2223       const gp_Pnt& aPW1 = BRep_Tool::Pnt(aVW1);
2224       const gp_Pnt& aPW2 = BRep_Tool::Pnt(aVW2);
2225       //
2226       Standard_Real aDist1 = aPI1.SquareDistance(aPW1);
2227       Standard_Real aDist2 = aPI1.SquareDistance(aPW2);
2228       //
2229       if (aDist1 < aDist2) {
2230         aVI1 = aVW1;
2231         aVI2 = aVW2;
2232       }
2233       else {
2234         aVI1 = aVW2;
2235         aVI2 = aVW1;
2236       }
2237     }
2238   }
2239   else {
2240     aLEImages.Append(theEIm);
2241   }
2242   //
2243   // Find edges connected to these vertices
2244   const TopTools_ListOfShape& aLIE1 = theDMVE.FindFromKey(aVI1);
2245   const TopTools_ListOfShape& aLIE2 = theDMVE.FindFromKey(aVI2);
2246   //
2247   // Find vertices on the original face corresponding to vertices on the offset edge
2248   //
2249   // find original edges for both lists
2250   TopTools_ListOfShape aLOE1, aLOE2;
2251   for (i = 0; i < 2; ++i) {
2252     const TopTools_ListOfShape& aLIE = !i ? aLIE1 : aLIE2;
2253     TopTools_ListOfShape& aLOE = !i ? aLOE1 : aLOE2;
2254     //
2255     TopTools_MapOfShape aMFence;
2256     //
2257     TopTools_ListIteratorOfListOfShape aItLIE(aLIE);
2258     for (; aItLIE.More(); aItLIE.Next()) {
2259       const TopoDS_Shape& aEI = aItLIE.Value();
2260       if (theEdgesOrigins.IsBound(aEI)) {
2261         const TopTools_ListOfShape& aLEOrigins = theEdgesOrigins.Find(aEI);
2262         //
2263         TopTools_ListIteratorOfListOfShape aItLOE(aLEOrigins);
2264         for (; aItLOE.More(); aItLOE.Next()) {
2265           const TopoDS_Shape& aEO = aItLOE.Value();
2266           if (aEO.ShapeType() == TopAbs_EDGE && aMFence.Add(aEO)) {
2267             TopoDS_Shape aEOin;
2268             if (FindShape(aEO, theFOr, aEOin)) {
2269               AppendToList(aLOE, aEO);
2270             }
2271           }
2272         }
2273       }
2274     }
2275   }
2276   //
2277   if (aLOE1.Extent() < 2 || aLOE2.Extent() < 2) {
2278     return Standard_False;
2279   }
2280   //
2281   // find vertices common for all edges in the lists
2282   for (i = 0; i < 2; ++i) {
2283     const TopTools_ListOfShape& aLOE = !i ? aLOE1 : aLOE2;
2284     TopoDS_Vertex& aVO = !i ? aVO1 : aVO2;
2285     //
2286     const TopoDS_Shape& aEO = aLOE.First();
2287     TopExp_Explorer aExpV(aEO, TopAbs_VERTEX);
2288     for (; aExpV.More(); aExpV.Next()) {
2289       const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&aExpV.Current();
2290       //
2291       Standard_Boolean bVertValid = Standard_True;
2292       TopTools_ListIteratorOfListOfShape aItLOE(aLOE);
2293       for (aItLOE.Next(); aItLOE.More(); aItLOE.Next()) {
2294         const TopoDS_Shape& aEOx = aItLOE.Value();
2295         TopExp_Explorer aExpVx(aEOx, TopAbs_VERTEX);
2296         for (; aExpVx.More(); aExpVx.Next()) {
2297           const TopoDS_Shape& aVx = aExpVx.Current();
2298           if (aVx.IsSame(aV)) {
2299             break;
2300           }
2301         }
2302         //
2303         if (!aExpVx.More()) {
2304           bVertValid = Standard_False;
2305           break;
2306         }
2307       }
2308       //
2309       if (bVertValid) {
2310         aVO = aV;
2311         break;
2312       }
2313     }
2314   }
2315   //
2316   if (aVO1.IsNull() || aVO2.IsNull() || aVO1.IsSame(aVO2)) {
2317     return Standard_False;
2318   }
2319   //
2320   // check positions of the offset and original vertices
2321   const gp_Pnt& aPI1 = BRep_Tool::Pnt(aVI1);
2322   const gp_Pnt& aPI2 = BRep_Tool::Pnt(aVI2);
2323   const gp_Pnt& aPO1 = BRep_Tool::Pnt(aVO1);
2324   const gp_Pnt& aPO2 = BRep_Tool::Pnt(aVO2);
2325   //
2326   gp_Vec aVI(aPI1, aPI2);
2327   gp_Vec aVO(aPO1, aPO2);
2328   //
2329   Standard_Real anAngle = aVI.Angle(aVO);
2330   Standard_Boolean bInverted = Abs(anAngle - M_PI) < 1.e-4;
2331   if (bInverted) {
2332     TopTools_ListIteratorOfListOfShape aItLEIm(aLEImages);
2333     for (; aItLEIm.More(); aItLEIm.Next()) {
2334       const TopoDS_Shape& aEInvr = aItLEIm.Value();
2335       theMEInverted.Add(aEInvr);
2336     }
2337   }
2338   return bInverted;
2339 }
2340
2341 //=======================================================================
2342 //function : CheckInvertedBlock
2343 //purpose  : Checks if it is possible to remove the block containing
2344 //           inverted edges
2345 //=======================================================================
2346 Standard_Boolean CheckInvertedBlock(const TopoDS_Shape& theCB,
2347                                     const TopTools_ListOfShape& theLCBF,
2348                                     const TopTools_MapOfShape& theMEInverted,
2349                                     const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
2350                                     BRepOffset_DataMapOfShapeMapOfShape& theDMCBVInverted,
2351                                     BRepOffset_DataMapOfShapeMapOfShape& theDMCBVAll)
2352 {
2353   // For possible removal of the block:
2354   // 1. There should be more than just one face in the block
2355   TopoDS_Iterator aItF(theCB);
2356   aItF.Next();
2357   if (!aItF.More()) {
2358     return Standard_False;
2359   }
2360   //
2361   // 2. The block should at least contain two connected inverted edges with
2362   //    different origins (not just two images/splits of the same edge)
2363   TopTools_MapOfShape aMECBInv;
2364   TopoDS_Compound aCECBInv;
2365   BRep_Builder().MakeCompound(aCECBInv);
2366   //
2367   TopExp_Explorer aExp(theCB, TopAbs_EDGE);
2368   for (; aExp.More(); aExp.Next()) {
2369     const TopoDS_Shape& aE = aExp.Current();
2370     if (theMEInverted.Contains(aE)) {
2371       if (aMECBInv.Add(aE)) {
2372         BRep_Builder().Add(aCECBInv, aE);
2373       }
2374     }
2375   }
2376   //
2377   if (aMECBInv.Extent() < 2) {
2378     return Standard_False;
2379   }
2380   //
2381   // check that the edges are connected and different
2382   TopTools_ListOfShape aLCBE;
2383   BOPTools_AlgoTools::MakeConnexityBlocks(aCECBInv, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
2384   //
2385   TopTools_ListIteratorOfListOfShape aItLCBE(aLCBE);
2386   for (; aItLCBE.More(); aItLCBE.Next()) {
2387     const TopoDS_Shape& aCBE = aItLCBE.Value();
2388     // count the unique edges in the block
2389     Standard_Integer aNbUnique = 0;
2390     TopTools_MapOfShape aMEOrigins;
2391     TopoDS_Iterator aItE(aCBE);
2392     for (; aItE.More(); aItE.Next()) {
2393       const TopoDS_Shape& aE = aItE.Value();
2394       const TopTools_ListOfShape *pLEOr = theOEOrigins.Seek(aE);
2395       if (!pLEOr) {
2396         aMEOrigins.Add(aE);
2397         ++aNbUnique;
2398         continue;
2399       }
2400       TopTools_ListIteratorOfListOfShape aItLEOr(*pLEOr);
2401       for (; aItLEOr.More(); aItLEOr.Next()) {
2402         const TopoDS_Shape& aEOr = aItLEOr.Value();
2403         if (aMEOrigins.Add(aEOr)) {
2404           ++aNbUnique;
2405         }
2406       }
2407     }
2408     //
2409     if (aNbUnique >= 2) {
2410       break;
2411     }
2412   }
2413   //
2414   if (!aItLCBE.More()) {
2415     return Standard_False;
2416   }
2417   //
2418   // 3. the block should not contain inverted edges which vertices
2419   //    are contained in other blocks
2420   //
2421   // collect vertices from inverted edges and compare them with
2422   // vertices from other blocks
2423   TopTools_MapOfShape* pMVInverted = theDMCBVInverted.ChangeSeek(theCB);
2424   TopTools_MapOfShape* pMVAll = theDMCBVAll.ChangeSeek(theCB);
2425   if (!pMVInverted) {
2426     pMVInverted = theDMCBVInverted.Bound(theCB, TopTools_MapOfShape());
2427     pMVAll = theDMCBVAll.Bound(theCB, TopTools_MapOfShape());
2428     //
2429     GetVerticesOnEdges(theCB, theMEInverted, *pMVInverted, *pMVAll);
2430   }
2431   //
2432   TopTools_ListIteratorOfListOfShape aItLCB1(theLCBF);
2433   for (; aItLCB1.More(); aItLCB1.Next()) {
2434     const TopoDS_Shape& aCB1 = aItLCB1.Value();
2435     if (aCB1.IsSame(theCB)) {
2436       continue;
2437     }
2438     //
2439     // collect vertices from inverted edges
2440     TopTools_MapOfShape* pMVInverted1 = theDMCBVInverted.ChangeSeek(aCB1);
2441     TopTools_MapOfShape* pMVAll1 = theDMCBVAll.ChangeSeek(aCB1);
2442     if (!pMVInverted1) {
2443       pMVInverted1 = theDMCBVInverted.Bound(aCB1, TopTools_MapOfShape());
2444       pMVAll1 = theDMCBVAll.Bound(aCB1, TopTools_MapOfShape());
2445       //
2446       GetVerticesOnEdges(aCB1, theMEInverted, *pMVInverted1, *pMVAll1);
2447     }
2448     //
2449     if (pMVInverted->HasIntersection(*pMVAll1)) {
2450       return Standard_False;
2451     }
2452   }
2453   //
2454   return Standard_True;
2455 }
2456
2457 //=======================================================================
2458 //function : GetVerticesOnEdges
2459 //purpose  : Get vertices from the given shape belonging to the given edges
2460 //=======================================================================
2461 void GetVerticesOnEdges(const TopoDS_Shape& theCB,
2462                         const TopTools_MapOfShape& theEdges,
2463                         TopTools_MapOfShape& theVerticesOnEdges,
2464                         TopTools_MapOfShape& theAllVertices)
2465 {
2466   TopExp_Explorer aExp(theCB, TopAbs_EDGE);
2467   for (; aExp.More(); aExp.Next()) {
2468     const TopoDS_Shape& aE = aExp.Current();
2469     Standard_Boolean bOnGivenEdge = theEdges.Contains(aE);
2470     for (TopoDS_Iterator aItV(aE); aItV.More(); aItV.Next()) {
2471       theAllVertices.Add(aItV.Value());
2472       if (bOnGivenEdge) {
2473         theVerticesOnEdges.Add(aItV.Value());
2474       }
2475     }
2476   }
2477 }
2478
2479 //=======================================================================
2480 //function : RemoveInvalidSplitsByInvertedEdges
2481 //purpose  : Looking for the invalid faces containing inverted edges
2482 //           that can be safely removed
2483 //=======================================================================
2484 void RemoveInvalidSplitsByInvertedEdges(const TopTools_MapOfShape& theMEInverted,
2485                                         const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
2486                                         TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
2487                                         TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
2488                                         TopTools_IndexedMapOfShape& theMERemoved)
2489 {
2490   if (theMEInverted.IsEmpty()) {
2491     return;
2492   }
2493   //
2494   // check the faces on regularity, i.e. the splits of the same face
2495   // should not be connected only by vertex. Such irregular splits
2496   // will have to be rebuilt and cannot be removed.
2497   //
2498   BRep_Builder aBB;
2499   TopTools_IndexedMapOfShape aMEAvoid;
2500   TopTools_DataMapOfShapeListOfShape aDMVF;
2501   Standard_Integer aNb = theFImages.Extent(), i;
2502   for (i = 1; i <= aNb; ++i) {
2503     const TopTools_ListOfShape& aLFIm = theFImages(i);
2504     //
2505     TopoDS_Compound aCFIm;
2506     aBB.MakeCompound(aCFIm);
2507     //
2508     TopTools_DataMapOfShapeListOfShape aDMEF;
2509     TopTools_ListIteratorOfListOfShape aIt(aLFIm);
2510     for (; aIt.More(); aIt.Next()) {
2511       const TopoDS_Shape& aF = aIt.Value();
2512       aBB.Add(aCFIm, aF);
2513       //
2514       // make a map to use only outer edges
2515       TopExp_Explorer aExp(aF, TopAbs_EDGE);
2516       for (; aExp.More(); aExp.Next()) {
2517         const TopoDS_Shape& aE = aExp.Current();
2518         //
2519         TopTools_ListOfShape *pLF = aDMEF.ChangeSeek(aE);
2520         if (!pLF) {
2521           pLF = aDMEF.Bound(aE, TopTools_ListOfShape());
2522         }
2523         else {
2524           // internal edges should not be used
2525           aMEAvoid.Add(aE);
2526         }
2527         AppendToList(*pLF, aF);
2528       }
2529       //
2530       // fill connection map of the vertices of inverted edges to faces
2531       aExp.Init(aF, TopAbs_VERTEX);
2532       for (; aExp.More(); aExp.Next()) {
2533         const TopoDS_Shape& aV = aExp.Current();
2534         //
2535         TopTools_ListOfShape *pLF = aDMVF.ChangeSeek(aV);
2536         if (!pLF) {
2537           pLF = aDMVF.Bound(aV, TopTools_ListOfShape());
2538         }
2539         AppendToList(*pLF, aF);
2540       }
2541     }
2542     //
2543     // for the splits to be regular they should form only one block
2544     TopTools_ListOfShape aLCBF;
2545     BOPTools_AlgoTools::MakeConnexityBlocks(aCFIm, TopAbs_EDGE, TopAbs_FACE, aLCBF);
2546     if (aLCBF.Extent() == 1) {
2547       continue;
2548     }
2549     //
2550     // check if the inverted edges create the irregularity
2551     BRepOffset_DataMapOfShapeMapOfShape aDMCBVInverted, aDMCBVAll;
2552     //
2553     TopTools_ListIteratorOfListOfShape aItLCB(aLCBF);
2554     for (; aItLCB.More(); aItLCB.Next()) {
2555       const TopoDS_Shape& aCB = aItLCB.Value();
2556       //
2557       // check if it is possible to remove the block
2558       if (!CheckInvertedBlock(aCB, aLCBF, theMEInverted, theOEOrigins, aDMCBVInverted, aDMCBVAll)) {
2559         // non of the edges in this block should be removed
2560         TopExp::MapShapes(aCB, TopAbs_EDGE, aMEAvoid);
2561         continue;
2562       }
2563     }
2564   }
2565   //
2566   // all edges not included in aMEAvoid can be removed
2567   TopTools_MapOfShape aMERem;
2568   TopTools_MapIteratorOfMapOfShape aItM(theMEInverted);
2569   for (; aItM.More(); aItM.Next()) {
2570     const TopoDS_Shape& aE = aItM.Value();
2571     if (!aMEAvoid.Contains(aE)) {
2572       TopoDS_Iterator aIt(aE);
2573       for (; aIt.More(); aIt.Next()) {
2574         const TopoDS_Shape& aV = aIt.Value();
2575         const TopTools_ListOfShape *pLF = aDMVF.Seek(aV);
2576         if (pLF && (pLF->Extent() > 3)) {
2577           aMERem.Add(aE);
2578           break;
2579         }
2580       }
2581     }
2582   }
2583   //
2584   if (aMERem.IsEmpty()) {
2585     return;
2586   }
2587   //
2588   // all invalid faces containing these edges can be removed
2589   TopTools_IndexedDataMapOfShapeListOfShape aInvFaces;
2590   TopTools_MapOfShape aMFRem;
2591   TopTools_IndexedMapOfShape aMFToUpdate;
2592   aNb = theInvFaces.Extent();
2593   for (i = 1; i <= aNb; ++i) {
2594     const TopoDS_Shape& aF = theInvFaces.FindKey(i);
2595     TopTools_ListOfShape& aLFIm = theInvFaces(i);
2596     //
2597     TopTools_ListIteratorOfListOfShape aIt(aLFIm);
2598     for (; aIt.More(); ) {
2599       const TopoDS_Shape& aFIm = aIt.Value();
2600       //
2601       // to be removed the face should have at least two not connected
2602       // inverted edges
2603       TopoDS_Compound aCEInv;
2604       aBB.MakeCompound(aCEInv);
2605       TopExp_Explorer aExp(aFIm, TopAbs_EDGE);
2606       for (; aExp.More(); aExp.Next()) {
2607         const TopoDS_Shape& aE = aExp.Current();
2608         if (aMERem.Contains(aE)) {
2609           aBB.Add(aCEInv, aE);
2610         }
2611       }
2612       //
2613       // check connectivity
2614       TopTools_ListOfShape aLCBE;
2615       BOPTools_AlgoTools::MakeConnexityBlocks(aCEInv, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
2616       //
2617       if (aLCBE.Extent() >= 2) {
2618         aMFToUpdate.Add(aF);
2619         aMFRem.Add(aFIm);
2620         aLFIm.Remove(aIt);
2621       }
2622       else {
2623         aIt.Next();
2624       }
2625     }
2626     //
2627     if (aLFIm.Extent()) {
2628       aInvFaces.Add(aF, aLFIm);
2629     }
2630   }
2631   //
2632   if (aMFRem.IsEmpty()) {
2633     return;
2634   }
2635   //
2636   theInvFaces = aInvFaces;
2637   // remove from splits
2638   aNb = aMFToUpdate.Extent();
2639   for (i = 1; i <= aNb; ++i) {
2640     const TopoDS_Shape& aF = aMFToUpdate(i);
2641     TopTools_ListOfShape& aLFIm = theFImages.ChangeFromKey(aF);
2642     //
2643     TopTools_ListIteratorOfListOfShape aIt(aLFIm);
2644     for (; aIt.More(); ) {
2645       const TopoDS_Shape& aFIm = aIt.Value();
2646       if (aMFRem.Contains(aFIm)) {
2647         TopExp::MapShapes(aFIm, TopAbs_EDGE, theMERemoved);
2648         aLFIm.Remove(aIt);
2649       }
2650       else {
2651         aIt.Next();
2652       }
2653     }
2654   }
2655 }
2656
2657 //=======================================================================
2658 //function : RemoveInvalidSplitsFromValid
2659 //purpose  : Removing invalid splits of faces from valid
2660 //=======================================================================
2661 void RemoveInvalidSplitsFromValid(const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
2662                                   const TopTools_DataMapOfShapeShape& theArtInvFaces,
2663                                   const TopTools_MapOfShape& theMEInverted,
2664                                   TopTools_IndexedDataMapOfShapeListOfShape& theFImages)
2665 {
2666   // Decide whether to remove the found invalid faces or not.
2667   // The procedure is the following:
2668   // 1. Make connexity blocks from invalid faces;
2669   // 2. Find free edges in this blocks;
2670   // 3. If all free edges are valid for the faces - remove block.
2671   //
2672   TopTools_MapOfShape aMFence, aMFToRem;
2673   TopoDS_Compound aCFInv;
2674   BRep_Builder aBB;
2675   aBB.MakeCompound(aCFInv);
2676   TopTools_ListIteratorOfListOfShape aItLF;
2677   //
2678   // make compound of invalid faces
2679   TopTools_DataMapOfShapeShape aDMIFOF;
2680   Standard_Integer i, aNb = theInvFaces.Extent();
2681   for (i = 1; i <= aNb; ++i) {
2682     const TopoDS_Shape& aF = theInvFaces.FindKey(i);
2683     // artificially invalid faces should not be removed
2684     if (theArtInvFaces.IsBound(aF)) {
2685       continue;
2686     }
2687     const TopTools_ListOfShape& aLFInv = theInvFaces(i);
2688     aItLF.Initialize(aLFInv);
2689     for (; aItLF.More(); aItLF.Next()) {
2690       const TopoDS_Shape& aFIm = aItLF.Value();
2691       if (aMFence.Add(aFIm)) {
2692         aBB.Add(aCFInv, aFIm);
2693         aDMIFOF.Bind(aFIm, aF);
2694       }
2695     }
2696   }
2697   //
2698   // make connexity blocks
2699   TopTools_ListOfShape aLCBInv;
2700   BOPTools_AlgoTools::MakeConnexityBlocks(aCFInv, TopAbs_EDGE, TopAbs_FACE, aLCBInv);
2701   //
2702   // analyze each block
2703   aItLF.Initialize(aLCBInv);
2704   for (; aItLF.More(); aItLF.Next()) {
2705     const TopoDS_Shape& aCB = aItLF.Value();
2706     //
2707     // if connexity block contains only one face - it should be removed;
2708     TopExp_Explorer aExp(aCB, TopAbs_FACE);
2709     aExp.Next();
2710     if (aExp.More()) {
2711       // check if there are valid images left
2712       aExp.Init(aCB, TopAbs_FACE);
2713       for (; aExp.More(); aExp.Next()) {
2714         const TopoDS_Shape& aFIm = aExp.Current();
2715         const TopoDS_Shape& aF = aDMIFOF.Find(aFIm);
2716         //
2717         const TopTools_ListOfShape& aLFIm = theFImages.FindFromKey(aF);
2718         const TopTools_ListOfShape& aLFInv = theInvFaces.FindFromKey(aF);
2719         //
2720         if (aLFIm.Extent() == aLFInv.Extent()) {
2721           break;
2722         }
2723       }
2724     }
2725     //
2726     if (!aExp.More()) {
2727       aExp.Init(aCB, TopAbs_FACE);
2728       for (; aExp.More(); aExp.Next()) {
2729         const TopoDS_Shape& aF = aExp.Current();
2730         aMFToRem.Add(aF);
2731       }
2732       continue;
2733     }
2734     //
2735     // remove faces connected by inverted edges
2736     TopTools_IndexedDataMapOfShapeListOfShape aDMEF;
2737     TopExp::MapShapesAndAncestors(aCB, TopAbs_EDGE, TopAbs_FACE, aDMEF);
2738     //
2739     aExp.Init(aCB, TopAbs_FACE);
2740     for (; aExp.More(); aExp.Next()) {
2741       const TopoDS_Shape& aFCB = aExp.Current();
2742       //
2743       TopExp_Explorer aExpE(aFCB, TopAbs_EDGE);
2744       for (; aExpE.More(); aExpE.Next()) {
2745         const TopoDS_Shape& aECB = aExpE.Current();
2746         if (aDMEF.FindFromKey(aECB).Extent() > 1) {
2747           if (!theMEInverted.Contains(aECB)) {
2748             break;
2749           }
2750         }
2751       }
2752       //
2753       if (!aExpE.More()) {
2754         aMFToRem.Add(aFCB);
2755       }
2756     }
2757   }
2758   //
2759   if (aMFToRem.Extent()) {
2760     // remove invalid faces from images
2761     aNb = theInvFaces.Extent();
2762     for (i = 1; i <= aNb; ++i) {
2763       const TopoDS_Shape& aF = theInvFaces.FindKey(i);
2764       TopTools_ListOfShape& aLFImages = theFImages.ChangeFromKey(aF);
2765       aItLF.Initialize(aLFImages);
2766       for (; aItLF.More();) {
2767         const TopoDS_Shape& aFIm = aItLF.Value();
2768         if (aMFToRem.Contains(aFIm)) {
2769           aLFImages.Remove(aItLF);
2770         }
2771         else {
2772           aItLF.Next();
2773         }
2774       }
2775     }
2776   }
2777 }
2778
2779 //=======================================================================
2780 //function : RemoveInsideFaces
2781 //purpose  : Looking for the inside faces that can be safely removed
2782 //=======================================================================
2783 void RemoveInsideFaces(TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
2784                        TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
2785                        const TopTools_DataMapOfShapeShape& theArtInvFaces,
2786                        const TopTools_IndexedMapOfShape& theInvEdges,
2787                        const TopTools_IndexedMapOfShape& theMFToCheckInt,
2788                        const TopTools_IndexedMapOfShape& theMFInvInHole,
2789                        const TopoDS_Shape& theFHoles,
2790                        TopTools_DataMapOfShapeListOfShape& theSSInterfs,
2791                        TopTools_IndexedMapOfShape& theMERemoved,
2792                        TopTools_IndexedMapOfShape& theMEInside,
2793                        TopoDS_Shape& theSolids)
2794 {
2795   BOPCol_ListOfShape aLS;
2796   TopTools_MapOfShape aMFence;
2797   TopTools_IndexedMapOfShape aMFInv;
2798   TopTools_ListIteratorOfListOfShape aItLF;
2799   TopTools_DataMapOfShapeShape aDMFImF;
2800   //
2801   Standard_Integer i, aNb = theFImages.Extent();
2802   for (i = 1; i <= aNb; ++i) {
2803     const TopoDS_Shape& aF = theFImages.FindKey(i);
2804     // to avoid intersection of the splits of the same
2805     // offset faces among themselves make compound of the
2806     // splits and use it as one argument
2807     TopoDS_Compound aCFImi;
2808     BRep_Builder().MakeCompound(aCFImi);
2809     //
2810     for (Standard_Integer j = 0; j < 2; ++j) {
2811       const TopTools_ListOfShape* pLFSp = !j ? theInvFaces.Seek(aF) : &theFImages(i);
2812       if (!pLFSp) {
2813         continue;
2814       }
2815       //
2816       aItLF.Initialize(*pLFSp);
2817       for (; aItLF.More(); aItLF.Next()) {
2818         const TopoDS_Shape& aFIm = aItLF.Value();
2819         if (aMFence.Add(aFIm)) {
2820           BRep_Builder().Add(aCFImi, aFIm);
2821           aDMFImF.Bind(aFIm, aF);
2822           if (!j) {
2823             aMFInv.Add(aFIm);
2824           }
2825         }
2826       }
2827     }
2828     //
2829     aLS.Append(aCFImi);
2830   }
2831   //
2832   // to make the solids more complete add for intersection also the faces
2833   // consisting only of invalid edges and not included into splits
2834   aNb = theMFToCheckInt.Extent();
2835   for (i = 1; i <= aNb; ++i) {
2836     const TopoDS_Shape& aFSp = theMFToCheckInt(i);
2837     if (aMFence.Add(aFSp)) {
2838       aLS.Append(aFSp);
2839     }
2840   }
2841   //
2842   BOPAlgo_MakerVolume aMV;
2843   aMV.SetArguments(aLS);
2844   aMV.SetIntersect(Standard_True);
2845   aMV.Perform();
2846   //
2847   // get shapes connection for using in the rebuilding process
2848   // for the cases in which some of the intersection left undetected
2849   ShapesConnections(theInvFaces, theInvEdges, aDMFImF, aMV, theSSInterfs);
2850   //
2851   // find faces to remove
2852   const TopoDS_Shape& aSols = aMV.Shape();
2853   //
2854   TopTools_IndexedDataMapOfShapeListOfShape aDMFS;
2855   TopExp::MapShapesAndAncestors(aSols, TopAbs_FACE, TopAbs_SOLID, aDMFS);
2856   //
2857   aNb = aDMFS.Extent();
2858   if (!aNb) {
2859     return;
2860   }
2861   //
2862   // To use the created solids for classifications, firstly, it is necessary
2863   // to check them on validity - the created solids should be complete,
2864   // i.e. all faces should be included.
2865   //
2866   TopTools_MapOfShape aMFToRem;
2867   // Check completeness
2868   if (aMV.HasDeleted()) {
2869     TopTools_IndexedMapOfShape aMEHoles;
2870     TopExp::MapShapes(theFHoles, TopAbs_EDGE, aMEHoles);
2871     //
2872     // perform additional check on faces
2873     aNb = theFImages.Extent();
2874     for (i = 1; i <= aNb; ++i) {
2875       const TopTools_ListOfShape& aLFIm = theFImages(i);
2876       if (aLFIm.IsEmpty()) {
2877         continue;
2878       }
2879       //
2880       Standard_Boolean bFaceKept = Standard_False;
2881       aItLF.Initialize(aLFIm);
2882       for (; aItLF.More(); aItLF.Next()) {
2883         const TopoDS_Shape& aFIm = aItLF.Value();
2884         if (!aMV.IsDeleted(aFIm)) {
2885           bFaceKept = Standard_True;
2886           continue;
2887         }
2888         //
2889         TopExp_Explorer aExpE(aFIm, TopAbs_EDGE);
2890         for (; aExpE.More(); aExpE.Next()) {
2891           if (aMEHoles.Contains(aExpE.Current())) {
2892             bFaceKept = Standard_True;
2893             aMFToRem.Add(aFIm);
2894             break;
2895           }
2896         }
2897       }
2898       //
2899       if (!bFaceKept) {
2900         return;
2901       }
2902     }
2903   }
2904   //
2905   TopTools_IndexedMapOfShape aMEBoundary;
2906   aNb = aDMFS.Extent();
2907   for (i = 1; i <= aNb; ++i) {
2908     const TopoDS_Shape& aFIm = aDMFS.FindKey(i);
2909     const TopTools_ListOfShape& aLSol = aDMFS(i);
2910     if (aLSol.Extent() > 1) {
2911       aMFToRem.Add(aFIm);
2912     }
2913     else if (aFIm.Orientation() != TopAbs_INTERNAL) {
2914       TopExp::MapShapes(aFIm, TopAbs_EDGE, aMEBoundary);
2915     }
2916   }
2917   //
2918   // update invalid faces with images
2919   aNb = aMFInv.Extent();
2920   for (i = 1; i <= aNb; ++i) {
2921     const TopoDS_Shape& aFInv = aMFInv(i);
2922     const TopTools_ListOfShape& aLFInvIm = aMV.Modified(aFInv);
2923     TopTools_ListIteratorOfListOfShape aItLFInvIm(aLFInvIm);
2924     for (; aItLFInvIm.More(); aItLFInvIm.Next()) {
2925       const TopoDS_Shape& aFInvIm = aItLFInvIm.Value();
2926       aMFInv.Add(aFInvIm);
2927     }
2928   }
2929   //
2930   // check if the invalid faces inside the holes are really invalid:
2931   // check its normal direction - if it has changed relatively the
2932   // original face the offset face is invalid and should be kept for rebuilding
2933   Standard_Integer aNbFH = theMFInvInHole.Extent();
2934   for (i = 1; i <= aNbFH; ++i) {
2935     const TopoDS_Shape& aFInv = theMFInvInHole(i);
2936     TopTools_ListOfShape aLFInvIm = aMV.Modified(aFInv);
2937     if (aLFInvIm.IsEmpty()) {
2938       aLFInvIm.Append(aFInv);
2939     }
2940     //
2941     const TopoDS_Shape *pFOffset = aDMFImF.Seek(aFInv);
2942     if (!pFOffset) {
2943       continue;
2944     }
2945     TopTools_ListIteratorOfListOfShape aItLFInv(aLFInvIm);
2946     for (; aItLFInv.More(); aItLFInv.Next()) {
2947       const TopoDS_Shape& aFInvIm = aItLFInv.Value();
2948       const TopTools_ListOfShape* pLSols = aDMFS.Seek(aFInvIm);
2949       if (!pLSols || pLSols->Extent() != 1) {
2950         continue;
2951       }
2952       //
2953       const TopoDS_Shape& aFSol = pLSols->First();
2954       //
2955       TopoDS_Shape aFx;
2956       if (!FindShape(aFInvIm, aFSol, aFx)) {
2957         continue;
2958       }
2959       //
2960       if (BRepOffset_Tool::CheckPlanesNormals(TopoDS::Face(aFx), TopoDS::Face(*pFOffset))) {
2961         // the normal direction has not changed, thus the face can be removed
2962         aMFToRem.Add(aFInvIm);
2963       }
2964     }
2965   }
2966   //
2967   TopoDS_Compound aSolids;
2968   BRep_Builder().MakeCompound(aSolids);
2969   TopTools_MapOfShape aMFKeep;
2970   //
2971   TopExp_Explorer aExpS(aSols, TopAbs_SOLID);
2972   for (; aExpS.More(); aExpS.Next()) {
2973     const TopoDS_Shape& aSol = aExpS.Current();
2974     //
2975     Standard_Boolean bAllInv(Standard_True), bAllRemoved(Standard_True);
2976
2977     for (TopExp_Explorer aExpF(aSol, TopAbs_FACE); aExpF.More(); aExpF.Next())
2978     {
2979       const TopoDS_Shape& aFS = aExpF.Current();
2980       //
2981       if (aFS.Orientation() == TopAbs_INTERNAL) {
2982         aMFToRem.Add(aFS);
2983       }
2984       //
2985       bAllRemoved = bAllRemoved && aMFToRem.Contains(aFS);
2986       bAllInv = bAllInv && (aMFToRem.Contains(aFS) || aMFInv.Contains(aFS));
2987     }
2988     //
2989     if (bAllInv && !bAllRemoved) {
2990       // remove invalid faces but keep those that have already been marked for removal
2991       TopExp_Explorer aExpF(aSol, TopAbs_FACE);
2992       for (; aExpF.More(); aExpF.Next()) {
2993         const TopoDS_Shape& aFS = aExpF.Current();
2994         //
2995         if (aMFToRem.Contains(aFS)) {
2996           if (!aMFKeep.Add(aFS)) {
2997             aMFKeep.Remove(aFS);
2998           }
2999         }
3000         else {
3001           aMFToRem.Add(aFS);
3002         }
3003       }
3004     }
3005     else {
3006       BRep_Builder().Add(aSolids, aSol);
3007       theSolids = aSolids;
3008     }
3009   }
3010   //
3011   TopTools_MapIteratorOfMapOfShape aItM(aMFKeep);
3012   for (; aItM.More(); aItM.Next()) {
3013     aMFToRem.Remove(aItM.Value());
3014   }
3015   //
3016   // remove newly found internal faces
3017   RemoveValidSplits(aMFToRem, theFImages, aMV, theMERemoved);
3018   RemoveInvalidSplits(aMFToRem, theArtInvFaces, theInvEdges, theInvFaces, aMV, theMERemoved);
3019   //
3020   // Get inside faces from the removed ones comparing them with boundary edges
3021   aNb = theMERemoved.Extent();
3022   for (i = 1; i <= aNb; ++i) {
3023     const TopoDS_Shape& aE = theMERemoved(i);
3024     if (!aMEBoundary.Contains(aE)) {
3025       theMEInside.Add(aE);
3026     }
3027   }
3028 }
3029
3030 //=======================================================================
3031 //function : ShapesConnections
3032 //purpose  : Looking for the connections between faces not to miss
3033 //           some necessary intersection
3034 //=======================================================================
3035 void ShapesConnections(const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
3036                        const TopTools_IndexedMapOfShape& theInvEdges,
3037                        const TopTools_DataMapOfShapeShape& theDMFOr,
3038                        BOPAlgo_Builder& theBuilder,
3039                        TopTools_DataMapOfShapeListOfShape& theSSInterfs)
3040 {
3041   // update invalid edges with images and keep connection to original edge
3042   TopTools_DataMapOfShapeListOfShape aDMEOr;
3043   Standard_Integer aNb = theInvEdges.Extent();
3044   for (Standard_Integer i = 1; i <= aNb; ++i) {
3045     const TopoDS_Shape& aEInv = theInvEdges(i);
3046     const TopTools_ListOfShape& aLEIm = theBuilder.Modified(aEInv);
3047     if (aLEIm.IsEmpty()) {
3048       aDMEOr.Bound(aEInv, TopTools_ListOfShape())->Append(aEInv);
3049       continue;
3050     }
3051     //
3052     TopTools_ListIteratorOfListOfShape aItLEIm(aLEIm);
3053     for (; aItLEIm.More(); aItLEIm.Next()) {
3054       const TopoDS_Shape& aEIm = aItLEIm.Value();
3055       //
3056       TopTools_ListOfShape* pLEOr = aDMEOr.ChangeSeek(aEIm);
3057       if (!pLEOr) {
3058         pLEOr = aDMEOr.Bound(aEIm, TopTools_ListOfShape());
3059       }
3060       AppendToList(*pLEOr, aEInv);
3061     }
3062   }
3063   //
3064   // get shapes connections for using in the rebuilding process
3065   const BOPDS_PDS& pDS = theBuilder.PDS();
3066   // analyze all Face/Face intersections
3067   const BOPDS_VectorOfInterfFF& aFFs = pDS->InterfFF();
3068   Standard_Integer iInt, aNbFF = aFFs.Extent();
3069   for (iInt = 0; iInt < aNbFF; ++iInt) {
3070     const BOPDS_InterfFF& aFF = aFFs(iInt);
3071     const BOPDS_VectorOfCurve& aVNC = aFF.Curves();
3072     Standard_Integer aNbC = aVNC.Extent();
3073     if (!aNbC) {
3074       continue;
3075     }
3076     //
3077     const TopoDS_Shape& aFIm1 = pDS->Shape(aFF.Index1());
3078     const TopoDS_Shape& aFIm2 = pDS->Shape(aFF.Index2());
3079     //
3080     const TopoDS_Shape* pF1 = theDMFOr.Seek(aFIm1);
3081     const TopoDS_Shape* pF2 = theDMFOr.Seek(aFIm2);
3082     //
3083     if (!pF1 || !pF2) {
3084       continue;
3085     }
3086     //
3087     if (pF1->IsSame(*pF2)) {
3088       continue;
3089     }
3090     //
3091     Standard_Boolean bInv1 = theInvFaces.Contains(*pF1);
3092     Standard_Boolean bInv2 = theInvFaces.Contains(*pF2);
3093     //
3094     if (!bInv1 && !bInv2) {
3095       continue;
3096     }
3097     //
3098     // check if it is real Face/Face intersection
3099     TopTools_MapOfShape aMEInt;
3100     for (Standard_Integer iC = 0; iC < aNbC; ++iC) {
3101       const BOPDS_Curve& aNC = aVNC(iC);
3102       const BOPDS_ListOfPaveBlock& aLPB = aNC.PaveBlocks();
3103       BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
3104       for (; aItLPB.More(); aItLPB.Next()) {
3105         const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
3106         Standard_Integer nEInt;
3107         if (aPB->HasEdge(nEInt)) {
3108           const TopoDS_Shape& aEInt = pDS->Shape(nEInt);
3109           aMEInt.Add(aEInt);
3110         }
3111       }
3112     }
3113     //
3114     if (aMEInt.IsEmpty()) {
3115       continue;
3116     }
3117     //
3118     // check if invalid edges of the face are in the same splits with intersection edges
3119     for (Standard_Integer i = 0; i < 2; ++i) {
3120       if ((!i && !bInv1) || (i && !bInv2)) {
3121         continue;
3122       }
3123       //
3124       const TopoDS_Shape& aF = !i ? *pF1 : *pF2;
3125       const TopoDS_Shape& aFOp = !i ? *pF2 : *pF1;
3126       const TopoDS_Shape& aFIm = !i ? aFIm1 : aFIm2;
3127       //
3128       Standard_Boolean bFound = Standard_False;
3129       //
3130       TopTools_ListOfShape aLFIm = theBuilder.Modified(aFIm);
3131       if (aLFIm.IsEmpty()) {
3132         aLFIm.Append(aFIm);
3133       }
3134       //
3135       TopTools_ListIteratorOfListOfShape aItLFIm(aLFIm);
3136       for (; aItLFIm.More(); aItLFIm.Next()) {
3137         const TopoDS_Shape& aFImIm = aItLFIm.Value();
3138         //
3139         Standard_Boolean bInv(Standard_False), bInt(Standard_False);
3140         TopExp_Explorer aExpE(aFImIm, TopAbs_EDGE);
3141         for (; aExpE.More(); aExpE.Next()) {
3142           const TopoDS_Shape& aE = aExpE.Current();
3143           if (!bInv) {
3144             bInv = aDMEOr.IsBound(aE);
3145           }
3146           if (!bInt) {
3147             bInt = aMEInt.Contains(aE);
3148           }
3149           if (bInv && bInt) {
3150             break;
3151           }
3152         }
3153         //
3154         if (!bInt || !bInv) {
3155           continue;
3156         }
3157         //
3158         bFound = Standard_True;
3159         //
3160         // append opposite face to all invalid edges in the split
3161         aExpE.Init(aFImIm, TopAbs_EDGE);
3162         for (; aExpE.More(); aExpE.Next()) {
3163           const TopoDS_Shape& aE = aExpE.Current();
3164           const TopTools_ListOfShape* pLEOr = aDMEOr.Seek(aE);
3165           if (!pLEOr) {
3166             continue;
3167           }
3168           //
3169           TopTools_ListIteratorOfListOfShape aItLE(*pLEOr);
3170           for (; aItLE.More(); aItLE.Next()) {
3171             const TopoDS_Shape& aEOr = aItLE.Value();
3172             TopTools_ListOfShape *pLFE = theSSInterfs.ChangeSeek(aEOr);
3173             if (!pLFE) {
3174               pLFE = theSSInterfs.Bound(aEOr, TopTools_ListOfShape());
3175             }
3176             AppendToList(*pLFE, aFOp);
3177           }
3178         }
3179       }
3180       if (bFound) {
3181         // save connection between offset faces
3182         TopTools_ListOfShape *pLF = theSSInterfs.ChangeSeek(aF);
3183         if (!pLF) {
3184           pLF = theSSInterfs.Bound(aF, TopTools_ListOfShape());
3185         }
3186         AppendToList(*pLF, aFOp);
3187       }
3188     }
3189   }
3190 }
3191
3192 //=======================================================================
3193 //function : RemoveValidSplits
3194 //purpose  : Removing valid splits according to results of intersection
3195 //=======================================================================
3196 void RemoveValidSplits(const TopTools_MapOfShape& theSpRem,
3197                        TopTools_IndexedDataMapOfShapeListOfShape& theImages,
3198                        BOPAlgo_Builder& theGF,
3199                        TopTools_IndexedMapOfShape& theMERemoved)
3200 {
3201   Standard_Integer i, aNb = theImages.Extent();
3202   if (!aNb) {
3203     return;
3204   }
3205   //
3206   for (i = 1; i <= aNb; ++i) {
3207     TopTools_ListOfShape& aLSIm = theImages(i);
3208     TopTools_ListIteratorOfListOfShape aIt(aLSIm);
3209     for (; aIt.More(); ) {
3210       const TopoDS_Shape& aSIm = aIt.Value();
3211       if (theSpRem.Contains(aSIm)) {
3212         TopExp::MapShapes(aSIm, TopAbs_EDGE, theMERemoved);
3213         aLSIm.Remove(aIt);
3214         continue;
3215       }
3216       //
3217       // check if all its images are have to be removed
3218       const TopTools_ListOfShape& aLSImIm = theGF.Modified(aSIm);
3219       if (aLSImIm.Extent()) {
3220         Standard_Boolean bAllRem = Standard_True;
3221         TopTools_ListIteratorOfListOfShape aIt1(aLSImIm);
3222         for (; aIt1.More(); aIt1.Next()) {
3223           const TopoDS_Shape& aSImIm = aIt1.Value();
3224           if (theSpRem.Contains(aSImIm)) {
3225             TopExp::MapShapes(aSImIm, TopAbs_EDGE, theMERemoved);
3226           }
3227           else {
3228             bAllRem = Standard_False;
3229           }
3230         }
3231         //
3232         if (bAllRem) {
3233           TopExp::MapShapes(aSIm, TopAbs_EDGE, theMERemoved);
3234           aLSIm.Remove(aIt);
3235           continue;
3236         }
3237       }
3238       aIt.Next();
3239     }
3240   }
3241 }
3242
3243 //=======================================================================
3244 //function : RemoveInvalidSplits
3245 //purpose  : Removing invalid splits according to the results of intersection
3246 //=======================================================================
3247 void RemoveInvalidSplits(const TopTools_MapOfShape& theSpRem,
3248                          const TopTools_DataMapOfShapeShape& theArtInvFaces,
3249                          const TopTools_IndexedMapOfShape& theInvEdges,
3250                          TopTools_IndexedDataMapOfShapeListOfShape& theImages,
3251                          BOPAlgo_Builder& theGF,
3252                          TopTools_IndexedMapOfShape& theMERemoved)
3253 {
3254   Standard_Integer i, aNb = theImages.Extent();
3255   if (!aNb) {
3256     return;
3257   }
3258   //
3259   for (i = 1; i <= aNb; ++i) {
3260     const TopoDS_Shape& aS = theImages.FindKey(i);
3261     Standard_Boolean bArt = theArtInvFaces.IsBound(aS);
3262     //
3263     TopTools_ListOfShape& aLSIm = theImages(i);
3264     TopTools_ListIteratorOfListOfShape aIt(aLSIm);
3265     for (; aIt.More();) {
3266       const TopoDS_Shape& aSIm = aIt.Value();
3267       if (theSpRem.Contains(aSIm)) {
3268         TopExp::MapShapes(aSIm, TopAbs_EDGE, theMERemoved);
3269         aLSIm.Remove(aIt);
3270         continue;
3271       }
3272       //
3273       // check if all its images are have to be removed
3274       const TopTools_ListOfShape& aLSImIm = theGF.Modified(aSIm);
3275       if (aLSImIm.IsEmpty()) {
3276         aIt.Next();
3277         continue;
3278       }
3279       //
3280       Standard_Boolean bAllRem = Standard_True;
3281       TopTools_IndexedMapOfShape aMERemoved;
3282       TopTools_ListIteratorOfListOfShape aIt1(aLSImIm);
3283       for (; aIt1.More(); aIt1.Next()) {
3284         const TopoDS_Shape& aSImIm = aIt1.Value();
3285         if (theSpRem.Contains(aSImIm)) {
3286           TopExp::MapShapes(aSImIm, TopAbs_EDGE, aMERemoved);
3287         }
3288         else {
3289           bAllRem = Standard_False;
3290         }
3291       }
3292       //
3293       if (bAllRem) {
3294         aLSIm.Remove(aIt);
3295         continue;
3296       }
3297       //
3298       if (bArt) {
3299         aIt.Next();
3300         continue;
3301       }
3302       //
3303       // remove the face from invalid if all invalid edges of this face
3304       // have been marked for removal
3305       TopExp_Explorer aExpE(aSIm, TopAbs_EDGE);
3306       for (; aExpE.More(); aExpE.Next()) {
3307         const TopoDS_Shape& aEInv = aExpE.Current();
3308         if (theInvEdges.Contains(aEInv) && !aMERemoved.Contains(aEInv)) {
3309           break;
3310         }
3311       }
3312       if (!aExpE.More()) {
3313         TopExp::MapShapes(aSIm, TopAbs_EDGE, theMERemoved);
3314         aLSIm.Remove(aIt);
3315       }
3316       else {
3317         aIt.Next();
3318       }
3319     }
3320   }
3321 }
3322
3323 //=======================================================================
3324 //function : FilterEdgesImages
3325 //purpose  : Updating the maps of images and origins of the offset edges
3326 //=======================================================================
3327 void FilterEdgesImages(const TopoDS_Shape& theS,
3328                        TopTools_DataMapOfShapeListOfShape& theOEImages,
3329                        TopTools_DataMapOfShapeListOfShape& theOEOrigins)
3330 {
3331   // map edges
3332   TopTools_IndexedMapOfShape aME;
3333   TopExp::MapShapes(theS, TopAbs_EDGE, aME);
3334   //
3335   theOEOrigins.Clear();
3336   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape aItDM(theOEImages);
3337   for (; aItDM.More(); aItDM.Next()) {
3338     const TopoDS_Shape& aE = aItDM.Key();
3339     TopTools_ListOfShape& aLEIm = aItDM.ChangeValue();
3340     //
3341     TopTools_ListIteratorOfListOfShape aIt(aLEIm);
3342     for (; aIt.More(); ) {
3343       const TopoDS_Shape& aEIm = aIt.Value();
3344       // filter images
3345       if (!aME.Contains(aEIm)) {
3346         // remove the image
3347         // edges with no images left should be kept in the map
3348         // to avoid their usage when building the splits of faces
3349         aLEIm.Remove(aIt);
3350         continue;
3351       }
3352       //
3353       // save origins
3354       if (theOEOrigins.IsBound(aEIm)) {
3355         AppendToList(theOEOrigins.ChangeFind(aEIm), aE);
3356       }
3357       else {
3358         TopTools_ListOfShape aLOr;
3359         aLOr.Append(aE);
3360         theOEOrigins.Bind(aEIm, aLOr);
3361       }
3362       //
3363       aIt.Next();
3364     }
3365   }
3366 }
3367
3368 //=======================================================================
3369 //function : FilterInvalidFaces
3370 //purpose  : Filtering of the invalid faces
3371 //=======================================================================
3372 void FilterInvalidFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
3373                         const TopTools_IndexedDataMapOfShapeListOfShape& theDMEF,
3374                         const TopTools_IndexedMapOfShape& theMERemoved,
3375                         TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
3376                         TopTools_DataMapOfShapeShape& theArtInvFaces)
3377 {
3378   //
3379   // filter invalid faces, considering faces having only valid
3380   // images left with non-free edges as valid
3381   // do not remove invalid faces if it creates free edges
3382   //
3383   TopTools_IndexedDataMapOfShapeListOfShape aReallyInvFaces;
3384   TopTools_ListIteratorOfListOfShape aItLF;
3385   //
3386   Standard_Integer i, aNb = theInvFaces.Extent();
3387   for (i = 1; i <= aNb; ++i) {
3388     const TopoDS_Shape& aF = theInvFaces.FindKey(i);
3389     const TopTools_ListOfShape& aLFInv = theInvFaces(i);
3390     //
3391     if (theArtInvFaces.IsBound(aF)) {
3392       if (aLFInv.IsEmpty()) {
3393         theArtInvFaces.UnBind(aF);
3394       }
3395       else {
3396         aReallyInvFaces.Add(aF, aLFInv);
3397       }
3398       continue;
3399     }
3400     //
3401     if (aLFInv.IsEmpty()) {
3402       continue;
3403     }
3404     //
3405     const TopTools_ListOfShape& aLFIm = theFImages.FindFromKey(aF);
3406     Standard_Boolean bInvalid = aLFIm.IsEmpty();
3407     //
3408     if (!bInvalid) {
3409       // check two lists on common splits
3410       aItLF.Initialize(aLFInv);
3411       for (; aItLF.More(); aItLF.Next()) {
3412         const TopoDS_Shape& aFInv = aItLF.Value();
3413         //
3414         TopTools_ListIteratorOfListOfShape aItLFIm(aLFIm);
3415         for (; aItLFIm.More(); aItLFIm.Next()) {
3416           const TopoDS_Shape& aFIm = aItLFIm.Value();
3417           //
3418           if (aFInv.IsSame(aFIm)) {
3419             break;
3420           }
3421         }
3422         //
3423         if (aItLFIm.More()) {
3424           break;
3425         }
3426       }
3427       //
3428       bInvalid = aItLF.More();
3429     }
3430     //
3431     if (!bInvalid) {
3432       // check for free edges
3433       for (Standard_Integer j = 0; !bInvalid && j < 2; ++j) {
3434         const TopTools_ListOfShape& aLI = !j ? aLFIm : aLFInv;
3435         aItLF.Initialize(aLI);
3436         for (; aItLF.More(); aItLF.Next()) {
3437           const TopoDS_Shape& aFIm = aItLF.Value();
3438           //
3439           TopExp_Explorer aExp(aFIm, TopAbs_EDGE);
3440           for (; aExp.More(); aExp.Next()) {
3441             const TopoDS_Shape& aE = aExp.Current();
3442             if (!theMERemoved.Contains(aE)) {
3443               const TopTools_ListOfShape* pLEF = theDMEF.Seek(aE);
3444               if (pLEF && pLEF->Extent() == 1) {
3445                 break;
3446               }
3447             }
3448           }
3449           //
3450           if (aExp.More()) {
3451             break;
3452           }
3453         }
3454         bInvalid = aItLF.More();
3455       }
3456     }
3457     //
3458     if (bInvalid) {
3459       aReallyInvFaces.Add(aF, aLFInv);
3460     }
3461   }
3462   //
3463   theInvFaces = aReallyInvFaces;
3464 }
3465
3466 //=======================================================================
3467 //function : FilterInvalidEdges
3468 //purpose  : Filtering the invalid edges according to currently invalid faces
3469 //=======================================================================
3470 void FilterInvalidEdges(const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
3471                         const TopTools_DataMapOfShapeShape& theArtInvFaces,
3472                         const TopTools_DataMapOfShapeListOfShape& theDMFLIE,
3473                         const TopTools_IndexedMapOfShape& theMERemoved,
3474                         TopTools_IndexedMapOfShape& theInvEdges)
3475 {
3476   TopoDS_Compound aCEInv;
3477   TopTools_IndexedMapOfShape aMEInv;
3478   BRep_Builder aBB;
3479   aBB.MakeCompound(aCEInv);
3480   TopTools_ListIteratorOfListOfShape aItLF;
3481   //
3482   Standard_Integer i, aNb = theInvFaces.Extent();
3483   for (i = 1; i <= aNb; ++i) {
3484     const TopTools_ListOfShape& aLFInv = theInvFaces(i);
3485     aItLF.Initialize(aLFInv);
3486     for (; aItLF.More(); aItLF.Next()) {
3487       const TopoDS_Shape& aFIm = aItLF.Value();
3488       TopExp::MapShapes(aFIm, TopAbs_EDGE, aMEInv);
3489       //
3490       TopExp_Explorer aExpE(aFIm, TopAbs_EDGE);
3491       for (; aExpE.More(); aExpE.Next()) {
3492         const TopoDS_Shape& aE = aExpE.Current();
3493         if (theInvEdges.Contains(aE)) {
3494           aBB.Add(aCEInv, aE);
3495         }
3496       }
3497     }
3498   }
3499   //
3500   // remove edges which have been marked for removal
3501   TopTools_IndexedMapOfShape aMEInvToAvoid;
3502   TopTools_ListOfShape aLCBE;
3503   BOPTools_AlgoTools::MakeConnexityBlocks(aCEInv, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
3504   //
3505   TopTools_ListIteratorOfListOfShape aItLCBE(aLCBE);
3506   for (; aItLCBE.More(); aItLCBE.Next()) {
3507     const TopoDS_Shape& aCBE = aItLCBE.Value();
3508     TopExp_Explorer aExpCB(aCBE, TopAbs_EDGE);
3509     for (; aExpCB.More(); aExpCB.Next()) {
3510       const TopoDS_Shape& aE = aExpCB.Current();
3511       if (!theMERemoved.Contains(aE)) {
3512         break;
3513       }
3514     }
3515     //
3516     if (!aExpCB.More()) {
3517       TopExp::MapShapes(aCBE, TopAbs_EDGE, aMEInvToAvoid);
3518     }
3519   }
3520   //
3521   TopTools_IndexedMapOfShape aReallyInvEdges;
3522   //
3523   aNb = theInvFaces.Extent();
3524   for (i = 1; i <= aNb; ++i) {
3525     const TopoDS_Shape& aF = theInvFaces.FindKey(i);
3526     if (theArtInvFaces.IsBound(aF)) {
3527       const TopTools_ListOfShape& aLEInv = theDMFLIE.Find(aF);
3528       aItLF.Initialize(aLEInv);
3529       for (; aItLF.More(); aItLF.Next()) {
3530         const TopoDS_Shape& aE = aItLF.Value();
3531         if (aMEInv.Contains(aE) && !aMEInvToAvoid.Contains(aE)) {
3532           aReallyInvEdges.Add(aE);
3533         }
3534       }
3535     }
3536     else {
3537       const TopTools_ListOfShape& aLFInv = theInvFaces(i);
3538       aItLF.Initialize(aLFInv);
3539       for (; aItLF.More(); aItLF.Next()) {
3540         const TopoDS_Shape& aFIm = aItLF.Value();
3541         TopExp_Explorer aExpE(aFIm, TopAbs_EDGE);
3542         for (; aExpE.More(); aExpE.Next()) {
3543           const TopoDS_Shape& aE = aExpE.Current();
3544           if (theInvEdges.Contains(aE) && !aMEInvToAvoid.Contains(aE)) {
3545             aReallyInvEdges.Add(aE);
3546           }
3547         }
3548       }
3549     }
3550   }
3551   //
3552   theInvEdges = aReallyInvEdges;
3553 }
3554
3555 //=======================================================================
3556 //function : FindFacesToRebuild
3557 //purpose  : Looking for the faces that have to be rebuilt:
3558 //           1. Faces close to invalidity
3559 //           2. Faces containing some invalid parts
3560 //=======================================================================
3561 void FindFacesToRebuild(const TopTools_IndexedDataMapOfShapeListOfShape&  theLFImages,
3562                         const TopTools_IndexedMapOfShape&  theInvEdges,
3563                         const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
3564                         const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
3565                         TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
3566                         TopTools_MapOfShape& theFSelfRebAvoid)
3567 {
3568   Standard_Integer i, aNb = theLFImages.Extent();
3569   if (!aNb) {
3570     return;
3571   }
3572   //
3573   Standard_Boolean bRebuild;
3574   TopTools_ListIteratorOfListOfShape aItLF;
3575   TopTools_ListOfShape aLEValid;
3576   TopTools_MapOfShape aMFence, aMEReb, aMFReb;
3577   TopExp_Explorer aExp;
3578   //
3579   TopTools_DataMapOfShapeListOfShape aDMFLV;
3580   // get edges from invalid faces
3581   aNb = theInvFaces.Extent();
3582   for (i = 1; i <= aNb; i++) {
3583     const TopoDS_Shape& aF = theInvFaces.FindKey(i);
3584     aMFence.Clear();
3585     TopTools_ListOfShape aLVAvoid;
3586     const TopTools_ListOfShape& aLFIm = theInvFaces(i);
3587     aItLF.Initialize(aLFIm);
3588     for (; aItLF.More(); aItLF.Next()) {
3589       const TopoDS_Shape& aFIm = aItLF.Value();
3590       aExp.Init(aFIm, TopAbs_EDGE);
3591       for (; aExp.More(); aExp.Next()) {
3592         const TopoDS_Shape& aE = aExp.Current();
3593         aMEReb.Add(aE);
3594         if (theInvEdges.Contains(aE)) {
3595           TopExp_Explorer aExpV(aE, TopAbs_VERTEX);
3596           for (; aExpV.More(); aExpV.Next()) {
3597             const TopoDS_Shape& aV = aExpV.Current();
3598             if (aMFence.Add(aV)) {
3599               aLVAvoid.Append(aV);
3600               aMEReb.Add(aV);
3601             }
3602           }
3603         }
3604       }
3605     }
3606     //
3607     if (aLVAvoid.Extent()) {
3608       aDMFLV.Bind(aF, aLVAvoid);
3609     }
3610     //
3611     const TopTools_ListOfShape* pLF = theSSInterfs.Seek(aF);
3612     if (pLF) {
3613       TopTools_ListIteratorOfListOfShape aItLFE(*pLF);
3614       for (; aItLFE.More(); aItLFE.Next()) {
3615         const TopoDS_Shape& aFE = aItLFE.Value();
3616         aMFReb.Add(aFE);
3617       }
3618     }
3619   }
3620   //
3621   // get face to rebuild
3622   aNb = theLFImages.Extent();
3623   for (i = 1; i <= aNb; i++) {
3624     const TopoDS_Shape& aF = theLFImages.FindKey(i);
3625     const TopTools_ListOfShape& aLFIm = theLFImages(i);
3626     TopTools_MapOfShape aMVAvoid;
3627     if (aDMFLV.IsBound(aF)) {
3628       const TopTools_ListOfShape& aLVAvoid = aDMFLV.Find(aF);
3629       TopTools_ListIteratorOfListOfShape aItLV(aLVAvoid);
3630       for (; aItLV.More(); aItLV.Next()) {
3631         const TopoDS_Shape& aV = aItLV.Value();
3632         aMVAvoid.Add(aV);
3633       }
3634     }
3635     //
3636     bRebuild = aMFReb.Contains(aF);
3637     aLEValid.Clear();
3638     aMFence.Clear();
3639     //
3640     aItLF.Initialize(aLFIm);
3641     for (; aItLF.More(); aItLF.Next()) {
3642       const TopoDS_Shape& aFIm = aItLF.Value();
3643       aExp.Init(aFIm, TopAbs_EDGE);
3644       for (; aExp.More(); aExp.Next()) {
3645         const TopoDS_Edge& anEIm = TopoDS::Edge(aExp.Current());
3646         if (!theInvEdges.Contains(anEIm)) {
3647           if (aMFence.Add(anEIm)) {
3648             aLEValid.Append(anEIm);
3649           }
3650         }
3651         //
3652         if (!bRebuild) {
3653           bRebuild = aMEReb.Contains(anEIm);
3654         }
3655         //
3656         if (!bRebuild) {
3657           // check vertices
3658           TopExp_Explorer aExpV(anEIm, TopAbs_VERTEX);
3659           for (; aExpV.More() && !bRebuild; aExpV.Next()) {
3660             const TopoDS_Shape& aV = aExpV.Current();
3661             if (!aMVAvoid.Contains(aV)) {
3662               bRebuild = aMEReb.Contains(aV);
3663             }
3664           }
3665         }
3666       }
3667     }
3668     //
3669     if (!bRebuild) {
3670       bRebuild = aLFIm.Extent() && theInvFaces.Contains(aF);
3671       if (bRebuild) {
3672         theFSelfRebAvoid.Add(aF);
3673       }
3674     }
3675     //
3676     if (bRebuild) {
3677       theFToRebuild.Add(aF, aLEValid);
3678     }
3679   }
3680 }
3681
3682 //=======================================================================
3683 //function : RebuildFaces
3684 //purpose  : Rebuilding of the faces
3685 //=======================================================================
3686 void RebuildFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
3687                   const TopTools_MapOfShape& theFSelfRebAvoid,
3688                   const TopoDS_Shape& theSolids,
3689                   const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
3690                   TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
3691                   TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
3692                   TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
3693                   TopTools_DataMapOfShapeShape& theFacesOrigins,
3694                   TopTools_DataMapOfShapeListOfShape& theOEImages,
3695                   TopTools_DataMapOfShapeListOfShape& theOEOrigins,
3696                   TopTools_MapOfShape& theLastInvEdges,
3697                   TopTools_IndexedMapOfShape& theEdgesToAvoid,
3698                   TopTools_IndexedMapOfShape& theInvEdges,
3699                   TopTools_IndexedMapOfShape& theValidEdges,
3700                   const TopTools_MapOfShape& theInvertedEdges,
3701                   TopTools_DataMapOfShapeInteger& theAlreadyInvFaces,
3702                   TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
3703                   const TopTools_DataMapOfShapeShape& theArtInvFaces,
3704                   TopTools_MapOfShape& theVertsToAvoid,
3705                   TopTools_DataMapOfShapeShape& theETrimEInf,
3706                   Handle(BRepAlgo_AsDes)& theAsDes)
3707 {
3708   TopTools_MapOfShape aModifiedEdges;
3709   //
3710   // 1. Intersect faces
3711   IntersectFaces(theFToRebuild, theFSelfRebAvoid, theSolids, theSSInterfs, theFImages, theEdgesOrigins, theOEImages,
3712                  theOEOrigins, theInvEdges, theValidEdges, theInvertedEdges, theEdgesToAvoid,
3713                  theInvFaces, theArtInvFaces, theVertsToAvoid, theETrimEInf, aModifiedEdges, theAsDes);
3714   //
3715   // 2. Repeat steps to build the correct faces
3716   BuildSplitsOfInvFaces(theFToRebuild, aModifiedEdges, theFImages, theDMFNewHoles, theEdgesOrigins,
3717                         theFacesOrigins, theOEImages, theOEOrigins, theLastInvEdges,
3718                         theEdgesToAvoid, theVertsToAvoid, theAlreadyInvFaces, theValidEdges,
3719                         theETrimEInf, theAsDes);
3720 }
3721
3722 //=======================================================================
3723 //function : IntersectFaces
3724 //purpose  : Intersection of the faces that should be rebuild
3725 //           to resolve all invalidities
3726 //=======================================================================
3727 void IntersectFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
3728                     const TopTools_MapOfShape& theFSelfRebAvoid,
3729                     const TopoDS_Shape& theSolids,
3730                     const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
3731                     TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
3732                     TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
3733                     TopTools_DataMapOfShapeListOfShape& theOEImages,
3734                     TopTools_DataMapOfShapeListOfShape& theOEOrigins,
3735                     TopTools_IndexedMapOfShape& theInvEdges,
3736                     TopTools_IndexedMapOfShape& theValidEdges,
3737                     const TopTools_MapOfShape& theInvertedEdges,
3738                     TopTools_IndexedMapOfShape& theEdgesToAvoid,
3739                     TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
3740                     const TopTools_DataMapOfShapeShape& theArtInvFaces,
3741                     TopTools_MapOfShape& theVertsToAvoid,
3742                     TopTools_DataMapOfShapeShape& theETrimEInf,
3743                     TopTools_MapOfShape& theModifiedEdges,
3744                     Handle(BRepAlgo_AsDes)& theAsDes)
3745 {
3746   Standard_Integer aNbFR = theFToRebuild.Extent();
3747   if (!aNbFR) {
3748     return;
3749   }
3750   //
3751   Standard_Integer i, j, k, aNbInv;
3752   TopTools_ListIteratorOfListOfShape aItLF, aItLE;
3753   //
3754   // get vertices from invalid edges
3755   TopTools_MapOfShape aMVInv, aMVInvAll;
3756   aNbInv = theInvEdges.Extent();
3757   for (i = 1; i <= aNbInv; ++i) {
3758     const TopoDS_Shape& aEInv = theInvEdges(i);
3759     Standard_Boolean bValid = theValidEdges.Contains(aEInv);
3760     for (TopExp_Explorer aExp (aEInv, TopAbs_VERTEX); aExp.More(); aExp.Next()) {
3761       const TopoDS_Shape& aV = aExp.Current();
3762       aMVInvAll.Add(aV);
3763       if (!bValid) {
3764         aMVInv.Add(aV);
3765       }
3766     }
3767   }
3768   //
3769   Standard_Boolean bLookVertToAvoid = (aMVInv.Extent() > 0);
3770   //
3771   TopTools_DataMapOfShapeListOfShape aDMSF, aMDone, aMEInfETrim, aDMVEFull;
3772   TopTools_IndexedDataMapOfShapeListOfShape aFLE, aDMEFInv;
3773   //
3774   // Add all faces to rebuild to outgoing map <aFLE>,
3775   // plus link edges and vertices to the faces to
3776   // define intersection faces
3777   PrepareFacesForIntersection(theFToRebuild, theFImages, theInvFaces, theArtInvFaces,
3778                               bLookVertToAvoid, aFLE, aMDone, aDMSF, aMEInfETrim,
3779                               aDMVEFull, theETrimEInf, aDMEFInv);
3780
3781   // Find vertices to avoid while trimming the edges.
3782   // These vertices are taken from the invalid edges common between
3783   // splits of different invalid, but not artificially, faces.
3784   // Additional condition for these vertices is that all
3785   // edges adjacent to this vertex must be either invalid
3786   // or contained in invalid faces
3787   TopTools_MapOfShape aMVRInv = theVertsToAvoid;
3788   FindVerticesToAvoid(aDMEFInv, theInvEdges, theValidEdges, aDMVEFull, aMVRInv);
3789   //
3790   // The faces should be intersected selectively -
3791   // intersect only faces neighboring to the same invalid face
3792   // and connected to its invalid edges;
3793   // when dealing with artificially invalid faces for intersection to be
3794   // complete we need to use not only invalid edges, but also the
3795   // edges connected to invalid ones
3796
3797   // find blocks of artificially invalid faces
3798   TopTools_DataMapOfShapeShape aDMFImF;
3799   TopoDS_Compound aCFArt;
3800   BRep_Builder().MakeCompound(aCFArt);
3801   TopTools_DataMapIteratorOfDataMapOfShapeShape aItM(theArtInvFaces);
3802   for (; aItM.More(); aItM.Next()) {
3803     const TopoDS_Shape& aF = aItM.Key();
3804     const TopTools_ListOfShape& aLFInv = theInvFaces.FindFromKey(aF);
3805     aItLF.Initialize(aLFInv);
3806     for (; aItLF.More(); aItLF.Next()) {
3807       BRep_Builder().Add(aCFArt, aItLF.Value());
3808       aDMFImF.Bind(aItLF.Value(), aF);
3809     }
3810   }
3811   //
3812   // make connexity blocks
3813   TopTools_ListOfShape aLCBArt;
3814   BOPTools_AlgoTools::MakeConnexityBlocks(aCFArt, TopAbs_VERTEX, TopAbs_FACE, aLCBArt);
3815   //
3816   // alone edges
3817   TopTools_MapOfShape aMEAlone, aMEInvOnArt;
3818   //
3819   TopTools_ListIteratorOfListOfShape aItLCBArt(aLCBArt);
3820   for (; aItLCBArt.More(); aItLCBArt.Next()) {
3821     const TopoDS_Shape& aCB = aItLCBArt.Value();
3822     //
3823     // check if aCB contains splits of only one offset face
3824     TopTools_MapOfShape aMFArt;
3825     TopExp_Explorer aExpF(aCB, TopAbs_FACE);
3826     for (; aExpF.More(); aExpF.Next()) {
3827       aMFArt.Add(aDMFImF.Find(aExpF.Current()));
3828     }
3829     //
3830     Standard_Boolean bAlone = (aMFArt.Extent() == 1);
3831     //
3832     // vertices on invalid edges
3833     TopTools_MapOfShape aMVEInv;
3834     TopTools_MapOfShape aMFence;
3835     // edges that should not be marked as alone - edges having same origins as invalid ones
3836     TopTools_MapOfShape aMEAvoid;
3837     // map to find alone edges by looking for free vertices
3838     TopTools_IndexedDataMapOfShapeListOfShape aDMVEVal;
3839     //
3840     TopExp_Explorer aExpE(aCB, TopAbs_EDGE);
3841     for (; aExpE.More(); aExpE.Next()) {
3842       const TopoDS_Shape& aE = aExpE.Current();
3843       if (theInvEdges.Contains(aE)) {
3844         aMEInvOnArt.Add(aE);
3845         for (TopoDS_Iterator aItV(aE); aItV.More(); aItV.Next()) {
3846           aMVEInv.Add(aItV.Value());
3847         }
3848         //
3849         if (bAlone) {
3850           const TopTools_ListOfShape *pLEOr = theOEOrigins.Seek(aE);
3851           if (pLEOr) {
3852             TopTools_ListIteratorOfListOfShape aItLEOr(*pLEOr);
3853             for (; aItLEOr.More(); aItLEOr.Next()) {
3854               TopTools_ListIteratorOfListOfShape aItLEIm(theOEImages.Find(aItLEOr.Value()));
3855               for (; aItLEIm.More(); aItLEIm.Next()) {
3856                 aMEAvoid.Add(aItLEIm.Value());
3857               }
3858             }
3859           }
3860         }
3861         continue;
3862       }
3863       //
3864       if (aMFence.Add(aE)) {
3865         TopExp::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aDMVEVal);
3866       }
3867     }
3868     //
3869     // find edges with free vertices
3870     Standard_Integer aNbV = aDMVEVal.Extent();
3871     for (i = 1; i <= aNbV; ++i) {
3872       const TopoDS_Shape& aV = aDMVEVal.FindKey(i);
3873       if (!aMVEInv.Contains(aV)) {
3874         continue;
3875       }
3876       //
3877       const TopTools_ListOfShape& aLEV = aDMVEVal(i);
3878       if (aLEV.Extent() > 1) {
3879         continue;
3880       }
3881       //
3882       const TopoDS_Shape& aE = aLEV.First();
3883       if (aMEAvoid.Contains(aE)) {
3884         continue;
3885       }
3886       //
3887       aMEAlone.Add(aE);
3888       //
3889       // if this alone edge adds nothing to the intersection list
3890       // it means that the origin of this edge has been split and we need to
3891       // add the neighboring images of the same origins
3892       if (aDMSF.Find(aE).Extent() > 1) {
3893         continue;
3894       }
3895       //
3896       // check also its vertices
3897       TopoDS_Iterator aItE(aE);
3898       for (; aItE.More(); aItE.Next()) {
3899         const TopoDS_Shape& aVE = aItE.Value();
3900         if (aDMSF.Find(aVE).Extent() > 2) {
3901           break;
3902         }
3903       }
3904       //
3905       if (aItE.More()) {
3906         continue;
3907       }
3908       //
3909       // the edge is useless - look for other images
3910       const TopTools_ListOfShape *pLEOr = theOEOrigins.Seek(aE);
3911       if (!pLEOr) {
3912         continue;
3913       }
3914       //
3915       TopTools_ListIteratorOfListOfShape aItLEOr(*pLEOr);
3916       for (; aItLEOr.More(); aItLEOr.Next()) {
3917         const TopoDS_Shape& aEOr = aItLEOr.Value();
3918         //
3919         const TopTools_ListOfShape& aLEIm = theOEImages.Find(aEOr);
3920         TopTools_ListIteratorOfListOfShape aItLEIm(aLEIm);
3921         for (; aItLEIm.More(); aItLEIm.Next()) {
3922           const TopoDS_Shape& aEIm = aItLEIm.Value();
3923           //
3924           if (aMFence.Contains(aEIm)) {
3925             aMEAlone.Add(aEIm);
3926           }
3927         }
3928       }
3929     }
3930   }
3931   //
3932   // Get all invalidities from all faces to be used for avoiding
3933   // repeated usage of the common edges
3934   TopTools_MapOfShape aMAllInvs;
3935   aNbInv = theInvFaces.Extent();
3936   for (k = 1; k <= aNbInv; ++k) {
3937     TopTools_ListIteratorOfListOfShape aIt(theInvFaces(k));
3938     for (; aIt.More(); aIt.Next()) {
3939       TopExp_Explorer aExp(aIt.Value(), TopAbs_EDGE);
3940       for (; aExp.More(); aExp.Next()) {
3941         const TopoDS_Shape& aE = aExp.Current();
3942         if (theInvEdges.Contains(aE) || aMEAlone.Contains(aE)) {
3943           aMAllInvs.Add(aE);
3944           TopoDS_Iterator aItV(aE);
3945           for (; aItV.More(); aItV.Next()) {
3946             aMAllInvs.Add(aItV.Value());
3947           }
3948         }
3949       }
3950     }
3951   }
3952   //
3953   // Bounding vertices of not trimmed edges
3954   TopTools_MapOfShape aMVBounds;
3955   //
3956   TopTools_MapOfShape aMECheckExt;
3957   // Save connections between not trimmed edge and its trimmed parts
3958   TopTools_DataMapOfShapeListOfShape aDMEETrim;
3959   // Splits of the new edges
3960   TopTools_DataMapOfShapeListOfShape aEImages;
3961   BRep_Builder aBB;
3962   //
3963   aNbInv = theInvFaces.Extent();
3964   for (k = 1; k <= aNbInv; ++k) {
3965     const TopoDS_Shape& aFInv = theInvFaces.FindKey(k);
3966     Standard_Boolean bSelfRebAvoid = theFSelfRebAvoid.Contains(aFInv);
3967     const TopTools_ListOfShape& aLFInv = theInvFaces(k);
3968     //
3969     TopTools_ListOfShape aLCB;
3970     if (aLFInv.Extent() > 1) {
3971       // make compound of invalid faces
3972       TopoDS_Compound aCFInv;
3973       aBB.MakeCompound(aCFInv);
3974       //
3975       TopTools_ListIteratorOfListOfShape aIt(aLFInv);
3976       for (; aIt.More(); aIt.Next()) {
3977         const TopoDS_Shape& aFIm = aIt.Value();
3978         aBB.Add(aCFInv, aFIm);
3979       }
3980       //
3981       // make connexity blocks
3982       BOPTools_AlgoTools::MakeConnexityBlocks(aCFInv, TopAbs_EDGE, TopAbs_FACE, aLCB);
3983     }
3984     else {
3985       aLCB = aLFInv;
3986     }
3987     //
3988     Standard_Boolean bArtificial = theArtInvFaces.IsBound(aFInv);
3989     TopTools_ListIteratorOfListOfShape aItLCB(aLCB);
3990     for (; aItLCB.More(); aItLCB.Next()) {
3991       const TopoDS_Shape& aCBInv = aItLCB.Value();
3992       //
3993       TopTools_MapOfShape aMEFence;
3994       //
3995       TopoDS_Compound aCBE;
3996       aBB.MakeCompound(aCBE);
3997       //
3998       TopExp_Explorer aExp(aCBInv, TopAbs_EDGE);
3999       for (; aExp.More(); aExp.Next()) {
4000         const TopoDS_Shape& aE = aExp.Current();
4001         if (theInvEdges.Contains(aE) || (bArtificial && aMEAlone.Contains(aE))) {
4002           if (aMEFence.Add(aE)) {
4003             aBB.Add(aCBE, aE);
4004           }
4005         }
4006       }
4007       //
4008       // make connexity blocks of edges
4009       TopTools_ListOfShape aLCBE;
4010       BOPTools_AlgoTools::MakeConnexityBlocks(aCBE, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
4011       //
4012       TopTools_ListIteratorOfListOfShape aItLCBE(aLCBE);
4013       for (; aItLCBE.More(); aItLCBE.Next()) {
4014         const TopoDS_Shape& aCBELoc = aItLCBE.Value();
4015         //
4016         // map of edges and vertices of processing invalidity
4017         TopTools_IndexedMapOfShape aME;
4018         // map of vertices to trim the new edges
4019         TopTools_IndexedMapOfShape  aMECV;
4020         TopExp::MapShapes(aCBELoc, TopAbs_EDGE, aME);
4021         aMECV = aME;
4022         TopExp::MapShapes(aCBELoc, TopAbs_VERTEX, aME);
4023         //
4024         // Using the map <aME> find chain of faces to be intersected;
4025         //
4026         // faces for intersection
4027         TopTools_IndexedMapOfShape aMFInt;
4028         // additional faces for intersection
4029         TopTools_IndexedMapOfShape aMFIntExt;
4030         // splits of faces for intersection
4031         TopTools_ListOfShape aLFInt;
4032         // faces to avoid intersection
4033         TopTools_IndexedMapOfShape aMFAvoid;
4034         //
4035         FindFacesForIntersection(aFInv, aME, theFImages, aDMSF, aMVInvAll,
4036           theArtInvFaces, bArtificial, theSSInterfs, aMFAvoid, aMFInt, aMFIntExt, aLFInt);
4037         if (aMFInt.Extent() < 3) {
4038           // nothing to intersect
4039           continue;
4040         }
4041         //
4042         // intersect the faces, but do not intersect the invalid ones
4043         // among each other (except for the artificially invalid faces)
4044         TopTools_IndexedMapOfShape aMEToInt;
4045         Standard_Integer aNb = aMFInt.Extent();
4046         for (i = 1; i <= aNb; ++i) {
4047           const TopoDS_Face& aFi = TopoDS::Face(aMFInt(i));
4048           if (bSelfRebAvoid && aFi.IsSame(aFInv)) {
4049             continue;
4050           }
4051           //
4052           const TopTools_ListOfShape& aLFImi = theFImages.FindFromKey(aFi);
4053           //
4054           TopTools_ListOfShape& aLFEi = aFLE.ChangeFromKey(aFi);
4055           //
4056           TopTools_ListOfShape& aLFDone = aMDone.ChangeFind(aFi);
4057           //
4058           for (j = i + 1; j <= aNb; ++j) {
4059             const TopoDS_Face& aFj = TopoDS::Face(aMFInt(j));
4060             if (bSelfRebAvoid && aFj.IsSame(aFInv)) {
4061               continue;
4062             }
4063             //
4064             const TopTools_ListOfShape& aLFImj = theFImages.FindFromKey(aFj);
4065             //
4066             TopTools_ListOfShape& aLFEj = aFLE.ChangeFromKey(aFj);
4067             //
4068             // if there are some common edges between faces
4069             // we should use these edges and do not intersect again.
4070             TopTools_ListOfShape aLEC;
4071             FindCommonParts(aLFImi, aLFImj, aLEC);
4072             //
4073             if (aLEC.Extent()) {
4074               // no need to intersect if we have common edges between faces
4075               Standard_Boolean bForceUse = aMFIntExt.Contains(aFi) || aMFIntExt.Contains(aFj);
4076               ProcessCommonEdges(aLEC, theInvEdges, theValidEdges, aME, theETrimEInf, aMEInfETrim,
4077                                  theOEOrigins, aMAllInvs, bForceUse, aMECV, aMECheckExt, aDMEETrim, aLFEi, aLFEj, aMEToInt);
4078               continue;
4079             }
4080             //
4081             // check if both these faces are invalid and sharing edges
4082             if (theInvFaces.Contains(aFi) && theInvFaces.Contains(aFj) &&
4083               !theArtInvFaces.IsBound(aFi) && !theArtInvFaces.IsBound(aFj)) {
4084               continue;
4085             }
4086             //
4087             // check if these two faces have already been treated
4088             aItLE.Initialize(aLFDone);
4089             for (; aItLE.More(); aItLE.Next()) {
4090               const TopoDS_Shape& aF = aItLE.Value();
4091               if (aF.IsSame(aFj)) {
4092                 break;
4093               }
4094             }
4095             //
4096             if (aItLE.More()) {
4097               // use intersection line obtained on the previous steps
4098               // plus, find new origins for these lines
4099               UpdateIntersectedFaces(aFInv, aFi, aFj, aLFInv, aLFImi, aLFImj,
4100                                      aLFEi, aLFEj, theEdgesOrigins, aMEToInt);
4101               continue;
4102             }
4103             //
4104             if (aMFAvoid.Contains(aFi) || aMFAvoid.Contains(aFj)) {
4105               continue;
4106             }
4107             //
4108             aLFDone.Append(aFj);
4109             aMDone.ChangeFind(aFj).Append(aFi);
4110             //
4111             IntersectFaces(aFInv, aFi, aFj, aLFInv, aLFImi, aLFImj,
4112                            aLFEi, aLFEj, theEdgesOrigins, aMECV, aMEToInt);
4113           }
4114         }
4115         //
4116         // intersect and trim edges for this chain
4117         IntersectAndTrimEdges(theFToRebuild, aMFInt, aMEToInt, aDMEETrim, aME, aMECV,
4118                               aMVInv, aMVRInv, aMECheckExt, aMVBounds, aEImages);
4119       }
4120     }
4121   }
4122   //
4123   // filter the obtained edges
4124   UpdateValidEdges(theFImages, aFLE, aMVBounds, theSolids, theInvEdges, theInvertedEdges, aMEInvOnArt,
4125                    aMECheckExt, theEdgesToAvoid, theEdgesOrigins, theOEImages, theOEOrigins,
4126                    theVertsToAvoid, theETrimEInf, aEImages, aDMEETrim, theModifiedEdges, theAsDes);
4127 }
4128
4129 //=======================================================================
4130 //function : PrepareFacesForIntersection
4131 //purpose  : Preparation of the maps for analyzing intersections of the faces
4132 //=======================================================================
4133 void PrepareFacesForIntersection(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
4134                                  const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
4135                                  const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
4136                                  const TopTools_DataMapOfShapeShape& theArtInvFaces,
4137                                  const Standard_Boolean bLookVertToAvoid,
4138                                  TopTools_IndexedDataMapOfShapeListOfShape& theFLE,
4139                                  TopTools_DataMapOfShapeListOfShape& theMDone,
4140                                  TopTools_DataMapOfShapeListOfShape& theDMSF,
4141                                  TopTools_DataMapOfShapeListOfShape& theMEInfETrim,
4142                                  TopTools_DataMapOfShapeListOfShape& theDMVEFull,
4143                                  TopTools_DataMapOfShapeShape& theETrimEInf,
4144                                  TopTools_IndexedDataMapOfShapeListOfShape& theDMEFInv)
4145 {
4146   Standard_Integer i, aNb = theFToRebuild.Extent();
4147   for (i = 1; i <= aNb; ++i) {
4148     const TopoDS_Shape& aF = theFToRebuild.FindKey(i);
4149     //
4150     TopTools_ListOfShape aLE;
4151     theFLE.Add(aF, aLE);
4152     theMDone.Bind(aF, aLE);
4153     //
4154     const TopTools_ListOfShape& aLFIm = theFImages.FindFromKey(aF);
4155     TopTools_ListIteratorOfListOfShape aItLF(aLFIm);
4156     for (; aItLF.More(); aItLF.Next()) {
4157       const TopoDS_Shape& aFIm = aItLF.Value();
4158       TopExp_Explorer aExp(aFIm, TopAbs_EDGE);
4159       for (; aExp.More(); aExp.Next()) {
4160         const TopoDS_Shape& aE = aExp.Current();
4161         // save connection to untrimmed face
4162         TopTools_ListOfShape *pLF = theDMSF.ChangeSeek(aE);
4163         if (!pLF) {
4164           pLF = theDMSF.Bound(aE, TopTools_ListOfShape());
4165         }
4166         AppendToList(*pLF, aF);
4167         //
4168         // save connection to untrimmed edge
4169         const TopoDS_Shape& aEInf = theETrimEInf.Find(aE);
4170         TopTools_ListOfShape *pLETrim = theMEInfETrim.ChangeSeek(aEInf);
4171         if (!pLETrim) {
4172           pLETrim = theMEInfETrim.Bound(aEInf, TopTools_ListOfShape());
4173         }
4174         AppendToList(*pLETrim, aE);
4175         //
4176         TopExp_Explorer aExpV(aE, TopAbs_VERTEX);
4177         for (; aExpV.More(); aExpV.Next()) {
4178           const TopoDS_Shape& aV = aExpV.Current();
4179           // save connection to face
4180           TopTools_ListOfShape *pLFV = theDMSF.ChangeSeek(aV);
4181           if (!pLFV) {
4182             pLFV = theDMSF.Bound(aV, TopTools_ListOfShape());
4183           }
4184           AppendToList(*pLFV, aF);
4185           //
4186           if (bLookVertToAvoid) {
4187             // save connection to edges
4188             TopTools_ListOfShape *pLEV = theDMVEFull.ChangeSeek(aV);
4189             if (!pLEV) {
4190               pLEV = theDMVEFull.Bound(aV, TopTools_ListOfShape());
4191             }
4192             AppendToList(*pLEV, aE);
4193           }
4194         }
4195       }
4196     }
4197     //
4198     if (bLookVertToAvoid) {
4199       // get edges of invalid faces (from invalid splits only)
4200       const TopTools_ListOfShape *pLFInv = theInvFaces.Seek(aF);
4201       if (!pLFInv || theArtInvFaces.IsBound(aF)) {
4202         continue;
4203       }
4204       //
4205       aItLF.Initialize(*pLFInv);
4206       for (; aItLF.More(); aItLF.Next()) {
4207         const TopoDS_Shape& aFInv = aItLF.Value();
4208         TopExp_Explorer aExp(aFInv, TopAbs_EDGE);
4209         for (; aExp.More(); aExp.Next()) {
4210           const TopoDS_Shape& aE = aExp.Current();
4211           TopTools_ListOfShape *pLF = theDMEFInv.ChangeSeek(aE);
4212           if (!pLF) {
4213             pLF = &theDMEFInv(theDMEFInv.Add(aE, TopTools_ListOfShape()));
4214           }
4215           AppendToList(*pLF, aF);
4216         }
4217       }
4218     }
4219   }
4220 }
4221
4222 //=======================================================================
4223 //function : FindVerticesToAvoid
4224 //purpose  : Looking for the invalid vertices
4225 //=======================================================================
4226 void FindVerticesToAvoid(const TopTools_IndexedDataMapOfShapeListOfShape& theDMEFInv,
4227                          const TopTools_IndexedMapOfShape& theInvEdges,
4228                          const TopTools_IndexedMapOfShape& theValidEdges,
4229                          TopTools_DataMapOfShapeListOfShape& theDMVEFull,
4230                          TopTools_MapOfShape& theMVRInv)
4231 {
4232   TopTools_MapOfShape aMFence;
4233   Standard_Integer i, aNb = theDMEFInv.Extent();
4234   for (i = 1; i <= aNb; ++i) {
4235     const TopTools_ListOfShape& aLFInv = theDMEFInv(i);
4236     if (aLFInv.Extent() == 1) {
4237       continue;
4238     }
4239     //
4240     const TopoDS_Shape& aE = theDMEFInv.FindKey(i);
4241     if (!theInvEdges.Contains(aE) || theValidEdges.Contains(aE)) {
4242       continue;
4243     }
4244     //
4245     TopExp_Explorer aExp(aE, TopAbs_VERTEX);
4246     for (; aExp.More(); aExp.Next()) {
4247       const TopoDS_Shape& aV = aExp.Current();
4248       TopTools_ListOfShape *pLE = theDMVEFull.ChangeSeek(aV);
4249       if (!pLE) {
4250         theMVRInv.Add(aV);
4251         continue;
4252       }
4253       //
4254       TopTools_ListIteratorOfListOfShape aItLE(*pLE);
4255       for (; aItLE.More(); aItLE.Next()) {
4256         const TopoDS_Shape& aEV = aItLE.Value();
4257         if (!theInvEdges.Contains(aEV) && !theDMEFInv.Contains(aEV)) {
4258           break;
4259         }
4260       }
4261       if (!aItLE.More()) {
4262         theMVRInv.Add(aV);
4263       }
4264     }
4265   }
4266 }
4267
4268 //=======================================================================
4269 //function : FindFacesForIntersection
4270 //purpose  : Looking for the faces around each invalidity for intersection
4271 //=======================================================================
4272 void FindFacesForIntersection(const TopoDS_Shape& theFInv,
4273                               const TopTools_IndexedMapOfShape& theME,
4274                               const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
4275                               const TopTools_DataMapOfShapeListOfShape& theDMSF,
4276                               const TopTools_MapOfShape& theMVInvAll,
4277                               const TopTools_DataMapOfShapeShape& theArtInvFaces,
4278                               const Standard_Boolean theArtCase,
4279                               const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
4280                               TopTools_IndexedMapOfShape& theMFAvoid,
4281                               TopTools_IndexedMapOfShape& theMFInt,
4282                               TopTools_IndexedMapOfShape& theMFIntExt,
4283                               TopTools_ListOfShape& theLFImInt)
4284 {
4285   Standard_Integer i, aNbE = theME.Extent();
4286   //
4287   TopTools_IndexedMapOfShape aMShapes;
4288   //
4289   for (i = 1; i <= aNbE; ++i) {
4290     const TopoDS_Shape& aS = theME(i);
4291     if (!theDMSF.IsBound(aS)) {
4292       continue;
4293     }
4294     //
4295     // in artificial case we intersect the faces which are close to invalidity
4296     Standard_Boolean bAvoid = theArtCase ?
4297       ((aS.ShapeType() == TopAbs_VERTEX) && !theMVInvAll.Contains(aS)) : Standard_False;
4298     //
4299     const TopTools_ListOfShape& aLF = theDMSF.Find(aS);
4300     TopTools_ListIteratorOfListOfShape aItLF(aLF);
4301     for (; aItLF.More(); aItLF.Next()) {
4302       const TopoDS_Shape& aF = aItLF.Value();
4303       if (theMFInt.Contains(aF)) {
4304         continue;
4305       }
4306       //
4307       if (bAvoid && theArtInvFaces.IsBound(aF)) {
4308         theMFAvoid.Add(aF);
4309       }
4310       //
4311       theMFInt.Add(aF);
4312       //
4313       Standard_Boolean bUse = !aF.IsSame(theFInv);
4314       //
4315       const TopTools_ListOfShape& aLFIm = theFImages.FindFromKey(aF);
4316       TopTools_ListIteratorOfListOfShape aItLFIm(aLFIm);
4317       for (; aItLFIm.More(); aItLFIm.Next()) {
4318         const TopoDS_Shape& aFIm = aItLFIm.Value();
4319         theLFImInt.Append(aFIm);
4320         if (bUse) {
4321           TopExp::MapShapes(aFIm, TopAbs_EDGE, aMShapes);
4322         }
4323       }
4324     }
4325   }
4326   //
4327   if (theArtCase) {
4328     return;
4329   }
4330   //
4331   const TopTools_ListOfShape* pLFInv = theSSInterfs.Seek(theFInv);
4332   if (!pLFInv) {
4333     return;
4334   }
4335   //
4336   TopTools_MapOfShape aMF;
4337   TopTools_ListIteratorOfListOfShape aItLF(*pLFInv);
4338   for (; aItLF.More(); aItLF.Next()) {
4339     const TopoDS_Shape& aF = aItLF.Value();
4340     aMF.Add(aF);
4341   }
4342   //
4343   // the faces should be unique in each place
4344   TopoDS_Compound aCF;
4345   BRep_Builder().MakeCompound(aCF);
4346   //
4347   TopTools_IndexedMapOfShape aMFToAdd;
4348   TopTools_DataMapOfShapeShape aDMFOr;
4349   //
4350   for (i = 1; i <= aNbE; ++i) {
4351     const TopoDS_Shape& aS = theME(i);
4352     const TopTools_ListOfShape* pLF = theSSInterfs.Seek(aS);
4353     if (!pLF) {
4354       continue;
4355     }
4356     //
4357     aItLF.Initialize(*pLF);
4358     for (; aItLF.More(); aItLF.Next()) {
4359       const TopoDS_Shape& aF = aItLF.Value();
4360       if (theMFInt.Contains(aF) || aMFToAdd.Contains(aF) || !aMF.Contains(aF)) {
4361         continue;
4362       }
4363       //
4364       // check if the face has some connection to already added for intersection faces
4365       const TopTools_ListOfShape& aLFIm = theFImages.FindFromKey(aF);
4366       TopTools_ListIteratorOfListOfShape aItLFIm(aLFIm);
4367       for (; aItLFIm.More(); aItLFIm.Next()) {
4368         const TopoDS_Shape& aFIm = aItLFIm.Value();
4369         TopExp_Explorer aExp(aFIm, TopAbs_EDGE);
4370         for (; aExp.More(); aExp.Next()) {
4371           if (aMShapes.Contains(aExp.Current())) {
4372             break;
4373           }
4374         }
4375         if (aExp.More()) {
4376           break;
4377         }
4378       }
4379       if (!aItLFIm.More()) {
4380         continue;
4381       }
4382       //
4383       aMFToAdd.Add(aF);
4384       aItLFIm.Initialize(aLFIm);
4385       for (; aItLFIm.More(); aItLFIm.Next()) {
4386         const TopoDS_Shape& aFIm = aItLFIm.Value();
4387         aDMFOr.Bind(aFIm, aF);
4388         BRep_Builder().Add(aCF, aFIm);
4389       }
4390     }
4391   }
4392   //
4393   if (aMFToAdd.IsEmpty()) {
4394     return;
4395   }
4396   //
4397   TopTools_ListOfShape aLCB;
4398   BOPTools_AlgoTools::MakeConnexityBlocks(aCF, TopAbs_EDGE, TopAbs_FACE, aLCB);
4399   //
4400   if ((aLCB.Extent() == 1) && (aMFToAdd.Extent() > 1)) {
4401     return;
4402   }
4403   //
4404   TopTools_ListIteratorOfListOfShape aItLCB(aLCB);
4405   for (; aItLCB.More(); aItLCB.Next()) {
4406     const TopoDS_Shape& aCB = aItLCB.Value();
4407     aMFToAdd.Clear();
4408     TopExp_Explorer aExpF(aCB, TopAbs_FACE);
4409     for (; aExpF.More(); aExpF.Next()) {
4410       const TopoDS_Shape& aFIm = aExpF.Current();
4411       aMFToAdd.Add(aDMFOr.Find(aFIm));
4412     }
4413     //
4414     if (aMFToAdd.Extent() == 1) {
4415       const TopoDS_Shape& aF = aMFToAdd(1);
4416       //
4417       theMFInt.Add(aF);
4418       theMFIntExt.Add(aF);
4419       //
4420       const TopTools_ListOfShape& aLFIm = theFImages.FindFromKey(aF);
4421       TopTools_ListIteratorOfListOfShape aItLFIm(aLFIm);
4422       for (; aItLFIm.More(); aItLFIm.Next()) {
4423         const TopoDS_Shape& aFIm = aItLFIm.Value();
4424         theLFImInt.Append(aFIm);
4425       }
4426     }
4427   }
4428 }
4429
4430 //=======================================================================
4431 //function : ProcessCommonEdges
4432 //purpose  : Analyzing the common edges between splits of offset faces
4433 //=======================================================================
4434 void ProcessCommonEdges(const TopTools_ListOfShape& theLEC,
4435                         const TopTools_IndexedMapOfShape& theInvEdges,
4436                         const TopTools_IndexedMapOfShape& theValidEdges,
4437                         const TopTools_IndexedMapOfShape& theME,
4438                         const TopTools_DataMapOfShapeShape& theETrimEInf,
4439                         const TopTools_DataMapOfShapeListOfShape& theMEInfETrim,
4440                         const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
4441                         const TopTools_MapOfShape& theAllInvs,
4442                         const Standard_Boolean theForceUse,
4443                         TopTools_IndexedMapOfShape& theMECV,
4444                         TopTools_MapOfShape& theMECheckExt,
4445                         TopTools_DataMapOfShapeListOfShape& theDMEETrim,
4446                         TopTools_ListOfShape& theLFEi,
4447                         TopTools_ListOfShape& theLFEj,
4448                         TopTools_IndexedMapOfShape& theMEToInt)
4449 {
4450   TopTools_ListOfShape aLEC;
4451   // process common edges
4452   TopTools_ListIteratorOfListOfShape aItLE(theLEC);
4453   for (; aItLE.More(); aItLE.Next()) {
4454     const TopoDS_Shape& aEC = aItLE.Value();
4455     //
4456     // check first if common edges are valid
4457     if (theInvEdges.Contains(aEC) && !theValidEdges.Contains(aEC)) {
4458       continue;
4459     }
4460     //
4461     // common edge should have connection to current invalidity
4462     if (theME.Contains(aEC)) {
4463       aLEC.Append(aEC);
4464       continue;
4465     }
4466     //
4467     TopoDS_Iterator aItV(aEC);
4468     for (; aItV.More(); aItV.Next()) {
4469       const TopoDS_Shape& aVE = aItV.Value();
4470       if (theME.Contains(aVE)) {
4471         aLEC.Append(aEC);
4472         break;
4473       }
4474     }
4475   }
4476   //
4477   Standard_Boolean bUseOnlyInf = aLEC.IsEmpty();
4478   if (bUseOnlyInf) {
4479     if (theForceUse) {
4480       aLEC = theLEC;
4481     }
4482     else {
4483       aItLE.Initialize(theLEC);
4484       for (; aItLE.More(); aItLE.Next()) {
4485         const TopoDS_Shape& aEC = aItLE.Value();
4486         // check if all images of the origin of this edge
4487         // are not connected to any invalidity
4488         const TopoDS_Shape& aEInt = theETrimEInf.Find(aEC);
4489         const TopTools_ListOfShape& aLVE = theMEInfETrim.Find(aEInt);
4490         TopTools_ListIteratorOfListOfShape aItLVE(aLVE);
4491         for (; aItLVE.More(); aItLVE.Next()) {
4492           const TopoDS_Shape& aECx = aItLVE.Value();
4493           if (theAllInvs.Contains(aECx) || theInvEdges.Contains(aECx)) {
4494             return;
4495           }
4496           //
4497           TopoDS_Iterator aItV(aECx);
4498           for (; aItV.More(); aItV.Next()) {
4499             if (theAllInvs.Contains(aItV.Value())) {
4500               return;
4501             }
4502           }
4503         }
4504         // use only one element
4505         if (aLEC.IsEmpty()) {
4506           aLEC.Append(aEC);
4507         }
4508       }
4509     }
4510   }
4511   //
4512   aItLE.Initialize(aLEC);
4513   for (; aItLE.More(); aItLE.Next()) {
4514     const TopoDS_Shape& aEC = aItLE.Value();
4515     //
4516     const TopoDS_Shape& aEInt = theETrimEInf.Find(aEC);
4517     if (!bUseOnlyInf) {
4518       // find the edges of the same original edge
4519       // and take their vertices as well
4520       const TopTools_ListOfShape& aLVE = theMEInfETrim.Find(aEInt);
4521       TopTools_ListIteratorOfListOfShape aItLVE(aLVE);
4522       for (; aItLVE.More(); aItLVE.Next()) {
4523         const TopoDS_Shape& aECx = aItLVE.Value();
4524         //
4525         const TopTools_ListOfShape* pLEOr = theOEOrigins.Seek(aECx);
4526         if (!pLEOr || (pLEOr->Extent() == 1)) {
4527           TopExp::MapShapes(aECx, TopAbs_VERTEX, theMECV);
4528         }
4529       }
4530       //
4531       // bind unlimited edge to its trimmed part in face to update maps of
4532       // images and origins in the future
4533       TopTools_ListOfShape* pLTAdded = theDMEETrim.ChangeSeek(aEInt);
4534       if (!pLTAdded) {
4535         pLTAdded = theDMEETrim.Bound(aEInt, TopTools_ListOfShape());
4536       }
4537       AppendToList(*pLTAdded, aEC);
4538     }
4539     else if (!theForceUse) {
4540       theMECheckExt.Add(aEInt);
4541     }
4542     //
4543     AppendToList(theLFEi, aEInt);
4544     AppendToList(theLFEj, aEInt);
4545     theMEToInt.Add(aEInt);
4546   }
4547 }
4548
4549 //=======================================================================
4550 //function : UpdateIntersectedFaces
4551 //purpose  : Updating the already interfered faces
4552 //=======================================================================
4553 void UpdateIntersectedFaces(const TopoDS_Shape& theFInv,
4554                             const TopoDS_Shape& theFi,
4555                             const TopoDS_Shape& theFj,
4556                             const TopTools_ListOfShape& theLFInv,
4557                             const TopTools_ListOfShape& theLFImi,
4558                             const TopTools_ListOfShape& theLFImj,
4559                             const TopTools_ListOfShape& theLFEi,
4560                             const TopTools_ListOfShape& theLFEj,
4561                             TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
4562                             TopTools_IndexedMapOfShape& theMEToInt)
4563 {
4564   // Find common edges in these two lists
4565   TopTools_MapOfShape aMEi;
4566   TopTools_ListIteratorOfListOfShape aItLE(theLFEi);
4567   for (; aItLE.More(); aItLE.Next()) {
4568     const TopoDS_Shape& aE = aItLE.Value();
4569     aMEi.Add(aE);
4570   }
4571   //
4572   // find origins
4573   TopTools_IndexedMapOfShape aMEToFindOrigins;
4574   TopTools_ListOfShape aLEToFindOrigins;
4575   if (!theFi.IsSame(theFInv)) {
4576     FindCommonParts(theLFImi, theLFInv, aLEToFindOrigins);
4577   }
4578   if (!theFj.IsSame(theFInv)) {
4579     FindCommonParts(theLFImj, theLFInv, aLEToFindOrigins);
4580   }
4581   //
4582   TopTools_ListOfShape aLEOrInit;
4583   aItLE.Initialize(aLEToFindOrigins);
4584   for (; aItLE.More(); aItLE.Next()) {
4585     const TopoDS_Shape& aEC = aItLE.Value();
4586     aMEToFindOrigins.Add(aEC);
4587   }
4588   //
4589   FindOrigins(theLFImi, theLFImj, aMEToFindOrigins, theEdgesOrigins, aLEOrInit);
4590   //
4591   aItLE.Initialize(theLFEj);
4592   for (; aItLE.More(); aItLE.Next()) {
4593     const TopoDS_Shape& aE = aItLE.Value();
4594     if (aMEi.Contains(aE)) {
4595       theMEToInt.Add(aE);
4596       if (aLEOrInit.Extent()) {
4597         if (theEdgesOrigins.IsBound(aE)) {
4598           TopTools_ListOfShape& aLEOr = theEdgesOrigins.ChangeFind(aE);
4599           TopTools_ListIteratorOfListOfShape aItLEOr(aLEOrInit);
4600           for (; aItLEOr.More(); aItLEOr.Next()) {
4601             const TopoDS_Shape& aEOr = aItLEOr.Value();
4602             AppendToList(aLEOr, aEOr);
4603           }
4604         }
4605         else {
4606           theEdgesOrigins.Bind(aE, aLEOrInit);
4607         }
4608       }
4609     }
4610   }
4611 }
4612
4613 //=======================================================================
4614 //function : IntersectFaces
4615 //purpose  : Intersection of the pair of faces
4616 //=======================================================================
4617 void IntersectFaces(const TopoDS_Shape& theFInv,
4618                     const TopoDS_Shape& theFi,
4619                     const TopoDS_Shape& theFj,
4620                     const TopTools_ListOfShape& theLFInv,
4621                     const TopTools_ListOfShape& theLFImi,
4622                     const TopTools_ListOfShape& theLFImj,
4623                     TopTools_ListOfShape& theLFEi,
4624                     TopTools_ListOfShape& theLFEj,
4625                     TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
4626                     TopTools_IndexedMapOfShape& theMECV,
4627                     TopTools_IndexedMapOfShape& theMEToInt)
4628 {
4629   // intersect faces
4630   TopAbs_State aSide = TopAbs_OUT;
4631   TopTools_ListOfShape aLInt1, aLInt2;
4632   TopoDS_Edge aNullEdge;
4633   BRepOffset_Tool::Inter3D(TopoDS::Face(theFi), TopoDS::Face(theFj), aLInt1, aLInt2, aSide, aNullEdge);
4634   //
4635   if (aLInt1.IsEmpty()) {
4636     return;
4637   }
4638   //
4639   // find common vertices for trimming edges
4640   TopTools_ListOfShape aLCV;
4641   TopTools_ListIteratorOfListOfShape aItLE;
4642   FindCommonParts(theLFImi, theLFImj, aLCV, TopAbs_VERTEX);
4643   if (aLCV.Extent() > 1) {
4644     aItLE.Initialize(aLCV);
4645     for (; aItLE.More(); aItLE.Next()) {
4646       const TopoDS_Shape& aCV = aItLE.Value();
4647       theMECV.Add(aCV);
4648     }
4649   }
4650   //
4651   // find origins
4652   TopTools_IndexedMapOfShape aMEToFindOrigins;
4653   TopTools_ListOfShape aLEToFindOrigins;
4654   if (!theFi.IsSame(theFInv)) {
4655     FindCommonParts(theLFImi, theLFInv, aLEToFindOrigins);
4656   }
4657   if (!theFj.IsSame(theFInv)) {
4658     FindCommonParts(theLFImj, theLFInv, aLEToFindOrigins);
4659   }
4660   TopTools_ListOfShape aLEOrInit;
4661   aItLE.Initialize(aLEToFindOrigins);
4662   for (; aItLE.More(); aItLE.Next()) {
4663     const TopoDS_Shape& aEC = aItLE.Value();
4664     aMEToFindOrigins.Add(aEC);
4665   }
4666   //
4667   FindOrigins(theLFImi, theLFImj, aMEToFindOrigins, theEdgesOrigins, aLEOrInit);
4668   //
4669   aItLE.Initialize(aLInt1);
4670   for (; aItLE.More(); aItLE.Next()) {
4671     const TopoDS_Shape& aEInt = aItLE.Value();
4672     theLFEi.Append(aEInt);
4673     theLFEj.Append(aEInt);
4674     //
4675     if (aLEOrInit.Extent()) {
4676       theEdgesOrigins.Bind(aEInt, aLEOrInit);
4677     }
4678     //
4679     theMEToInt.Add(aEInt);
4680   }
4681 }
4682
4683 //=======================================================================
4684 //function : FindOrigins
4685 //purpose  : Looking for the origin edges
4686 //=======================================================================
4687 void FindOrigins(const TopTools_ListOfShape& theLFIm1,
4688                  const TopTools_ListOfShape& theLFIm2,
4689                  const TopTools_IndexedMapOfShape& theME,
4690                  const TopTools_DataMapOfShapeListOfShape& theOrigins,
4691                  TopTools_ListOfShape& theLEOr)
4692 {
4693   Standard_Integer i;
4694   TopTools_MapOfShape aMFence;
4695   TopExp_Explorer aExp;
4696   TopTools_ListIteratorOfListOfShape aIt, aItLE;
4697   //
4698   for (i = 0; i < 2; ++i) {
4699     const TopTools_ListOfShape& aLF = !i ? theLFIm1 : theLFIm2;
4700     aIt.Initialize(aLF);
4701     for (; aIt.More(); aIt.Next()) {
4702       const TopoDS_Shape& aF = aIt.Value();
4703       //
4704       aExp.Init(aF, TopAbs_EDGE);
4705       for (; aExp.More(); aExp.Next()) {
4706         const TopoDS_Shape& aE = aExp.Current();
4707         //
4708         if (theME.Contains(aE) && theOrigins.IsBound(aE)) {
4709           const TopTools_ListOfShape& aLEOr = theOrigins.Find(aE);
4710           aItLE.Initialize(aLEOr);
4711           for (; aItLE.More(); aItLE.Next()) {
4712             const TopoDS_Shape& aEOr = aItLE.Value();
4713             //
4714             if (aMFence.Add(aEOr) && (aEOr.ShapeType() == TopAbs_EDGE)) {
4715               theLEOr.Append(aEOr);
4716             }
4717           } // for (; aItLE.More(); aItLE.Next()) {
4718         } // if (theME.Contains(aE) && theOrigins.IsBound(aE)) {
4719       } // aExp.Init(aF, TopAbs_EDGE);
4720     } // for (; aIt.More(); aIt.Next()) {
4721   } // for (i = 0; i < 2; ++i) {
4722 }
4723
4724 //=======================================================================
4725 //function : IntersectAndTrimEdges
4726 //purpose  : Intersection of the new intersection edges among themselves
4727 //=======================================================================
4728 void IntersectAndTrimEdges(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
4729                            const TopTools_IndexedMapOfShape& theMFInt,
4730                            const TopTools_IndexedMapOfShape& theMEInt,
4731                            const TopTools_DataMapOfShapeListOfShape& theDMEETrim,
4732                            const TopTools_IndexedMapOfShape& theMSInv,
4733                            const TopTools_IndexedMapOfShape& theMVE,
4734                            const TopTools_MapOfShape& theVertsToAvoid,
4735                            const TopTools_MapOfShape& theNewVertsToAvoid,
4736                            const TopTools_MapOfShape& theMECheckExt,
4737                            TopTools_MapOfShape& theMVBounds,
4738                            TopTools_DataMapOfShapeListOfShape& theEImages)
4739 {
4740   Standard_Integer i, aNb = theMEInt.Extent();
4741   if (!aNb) {
4742     return;
4743   }
4744   //
4745   BOPCol_ListOfShape aLArgs;
4746   TopTools_MapOfShape aMFence;
4747   TopTools_ListIteratorOfListOfShape aIt, aIt1;
4748   TopExp_Explorer aExp;
4749   //
4750   // get vertices from the splits of intersected faces.
4751   // vertices are taken from the edges close to invalidity
4752   //
4753   TopTools_IndexedDataMapOfShapeListOfShape aDMVE;
4754   aNb = theMFInt.Extent();
4755   for (i = 1; i <= aNb; ++i) {
4756     const TopoDS_Shape& aF = theMFInt(i);
4757     const TopTools_ListOfShape& aLE = theFToRebuild.FindFromKey(aF);
4758     //
4759     aIt.Initialize(aLE);
4760     for (; aIt.More(); aIt.Next()) {
4761       const TopoDS_Shape& aE = aIt.Value();
4762       TopExp::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aDMVE);
4763       //
4764       aExp.Init(aE, TopAbs_VERTEX);
4765       for (; aExp.More(); aExp.Next()) {
4766         const TopoDS_Shape& aV1 = aExp.Current();
4767         if (!theVertsToAvoid.Contains(aV1) && theMVE.Contains(aV1) && aMFence.Add(aV1)) {
4768           aLArgs.Append(aV1);
4769         }
4770       }
4771     }
4772   }
4773   //
4774   aNb = theMSInv.Extent();
4775   for (i = 1; i <= aNb; ++i) {
4776     const TopoDS_Shape& aV = theMSInv(i);
4777     if (aV.ShapeType() != TopAbs_VERTEX) {
4778       continue;
4779     }
4780     //
4781     TopTools_ListOfShape *pLVE = aDMVE.ChangeSeek(aV);
4782     if (!pLVE) {
4783       continue;
4784     }
4785     //
4786     aIt.Initialize(*pLVE);
4787     for (; aIt.More(); aIt.Next()) {
4788       const TopoDS_Shape& aE = aIt.Value();
4789       //
4790       aExp.Init(aE, TopAbs_VERTEX);
4791       for (; aExp.More(); aExp.Next()) {
4792         const TopoDS_Shape& aV1 = aExp.Current();
4793         if (!theVertsToAvoid.Contains(aV1) && aMFence.Add(aV1)) {
4794           aLArgs.Append(aV1);
4795         }
4796       }
4797     }
4798   }
4799   //
4800   // bounding vertices of untrimmed edges
4801   TopTools_ListOfShape aLVBounds;
4802   // new intersection edges
4803   TopTools_ListOfShape aLENew;
4804   // get edges to intersect
4805   TopTools_ListOfShape aLEInt;
4806   // Common intersection edges. Should be intersected separetely
4807   TopTools_ListOfShape aLCE;
4808   //
4809   aNb = theMEInt.Extent();
4810   for (i = 1; i <= aNb; ++i) {
4811     const TopoDS_Shape& aE = theMEInt(i);
4812     if (theMECheckExt.Contains(aE)) {
4813       // avoid trimming of the intersection edges by additional common edges
4814       aLCE.Append(aE);
4815       continue;
4816     }
4817     //
4818     if (!theDMEETrim.IsBound(aE)) {
4819       aLENew.Append(aE);
4820     }
4821     //
4822     aLEInt.Append(aE);
4823     aLArgs.Append(aE);
4824     //
4825     aExp.Init(aE, TopAbs_VERTEX);
4826     for (; aExp.More(); aExp.Next()) {
4827       const TopoDS_Shape& aV = aExp.Current();
4828       aLVBounds.Append(aV);
4829     }
4830   }
4831   //
4832   // Intersect Edges
4833   BOPAlgo_Builder aGF;
4834   aGF.SetArguments(aLArgs);
4835   aGF.Perform();
4836   if (aGF.ErrorStatus()) {
4837     return;
4838   }
4839   //
4840   // update vertices to avoid with SD vertices
4841   aIt.Initialize(aLVBounds);
4842   for (; aIt.More(); aIt.Next()) {
4843     const TopoDS_Shape& aV = aIt.Value();
4844     const TopTools_ListOfShape& aLVIm = aGF.Modified(aV);
4845     if (aLVIm.IsEmpty()) {
4846       theMVBounds.Add(aV);
4847     }
4848     else {
4849       const TopoDS_Shape& aVIm = aLVIm.First();
4850       theMVBounds.Add(aVIm);
4851     }
4852   }
4853   //
4854   // find invalid splits of edges
4855   TopTools_MapOfShape aMEInv;
4856   GetInvalidEdges(theNewVertsToAvoid, theMVBounds, aGF, aMEInv);
4857   //
4858   BRep_Builder aBB;
4859   // get valid splits to intersect with the commons
4860   TopoDS_Compound aCEIm;
4861   aBB.MakeCompound(aCEIm);
4862   //
4863   // remove the splits containing vertices from invalid edges
4864   aIt.Initialize(aLEInt);
4865   for (; aIt.More(); aIt.Next()) {
4866     const TopoDS_Shape& aE = aIt.Value();
4867     //
4868     TopTools_ListOfShape aLEIm = aGF.Modified(aE);
4869     if (aLEIm.IsEmpty()) {
4870       continue;
4871     }
4872     //
4873     aIt1.Initialize(aLEIm);
4874     for (; aIt1.More(); ) {
4875       const TopoDS_Shape& aEIm = aIt1.Value();
4876       //
4877       if (aMEInv.Contains(aEIm)) {
4878         aLEIm.Remove(aIt1);
4879       }
4880       else {
4881         aBB.Add(aCEIm, aEIm);
4882         aIt1.Next();
4883       }
4884     }
4885     //
4886     if (aLEIm.Extent()) {
4887       TopTools_ListOfShape* pLEIm = theEImages.ChangeSeek(aE);
4888       if (!pLEIm) {
4889         pLEIm = theEImages.Bound(aE, TopTools_ListOfShape());
4890       }
4891       pLEIm->Append(aLEIm);
4892     }
4893   }
4894   //
4895   if (!aLCE.Extent()) {
4896     return;
4897   }
4898   //
4899   // trim common edges by other intersection edges
4900   BOPAlgo_Builder aGFCE;
4901   aGFCE.SetArguments(aLCE);
4902   aGFCE.AddArgument(aCEIm);
4903   aGFCE.Perform();
4904   //
4905   if (aGFCE.ErrorStatus()) {
4906     return;
4907   }
4908   //
4909   const BOPDS_PDS& pDS = aGFCE.PDS();
4910   TopTools_ListIteratorOfListOfShape aItLCE(aLCE);
4911   for (; aItLCE.More(); aItLCE.Next()) {
4912     const TopoDS_Shape& aE = aItLCE.Value();
4913     TopTools_ListOfShape aLEIm = aGFCE.Modified(aE);
4914     if (aLEIm.IsEmpty()) {
4915       continue;
4916     }
4917     //
4918     // check if it's not coincide with some intersection edge
4919     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(pDS->PaveBlocks(pDS->Index(aE)));
4920     for (; aItLPB.More(); aItLPB.Next()) {
4921       if (pDS->IsCommonBlock(aItLPB.Value())) {
4922         // find with what it is a common
4923         const BOPDS_ListOfPaveBlock& aLPBC = pDS->CommonBlock(aItLPB.Value())->PaveBlocks();
4924         BOPDS_ListIteratorOfListOfPaveBlock aItLPBC(aLPBC);
4925         for (; aItLPBC.More(); aItLPBC.Next()) {
4926           const TopoDS_Shape& aEC = pDS->Shape(aItLPBC.Value()->OriginalEdge());
4927           if (!theMECheckExt.Contains(aEC)) {
4928             break;
4929           }
4930         }
4931         if (aItLPBC.More()) {
4932           break;
4933         }
4934       }
4935     }
4936     if (aItLPB.More()) {
4937       // avoid creation of unnecessary splits from commons which
4938       // coincide with intersection edges
4939       continue;
4940     }
4941     //
4942     // save the images
4943     TopTools_ListOfShape* pLEIm = theEImages.ChangeSeek(aE);
4944     if (!pLEIm) {
4945       pLEIm = theEImages.Bound(aE, TopTools_ListOfShape());
4946     }
4947     pLEIm->Append(aLEIm);
4948     //
4949     // save bounding vertices
4950     for (TopoDS_Iterator aItV(aE); aItV.More(); aItV.Next()) {
4951       const TopoDS_Shape& aV = aItV.Value();
4952       const TopTools_ListOfShape& aLVIm = aGFCE.Modified(aV);
4953       theMVBounds.Add(aLVIm.IsEmpty() ? aV : aLVIm.First());
4954     }
4955   }
4956 }
4957
4958 //=======================================================================
4959 //function : GetInvalidEdges
4960 //purpose  : Looking for the invalid edges by intersecting with invalid vertices
4961 //=======================================================================
4962 void GetInvalidEdges(const TopTools_MapOfShape& theVertsToAvoid,
4963                      const TopTools_MapOfShape& theMVBounds,
4964                      BOPAlgo_Builder& theGF,
4965                      TopTools_MapOfShape& theMEInv)
4966 {
4967   if (theVertsToAvoid.IsEmpty()) {
4968     return;
4969   }
4970   //
4971   TopTools_ListIteratorOfListOfShape aIt, aIt1;
4972   // get vertices created with intersection edges
4973   const TopoDS_Shape& aRes = theGF.Shape();
4974   TopTools_IndexedDataMapOfShapeListOfShape aDMVE;
4975   TopExp::MapShapesAndAncestors(aRes, TopAbs_VERTEX, TopAbs_EDGE, aDMVE);
4976   //
4977   const BOPDS_PDS& pDS = theGF.PDS();
4978   //
4979   // find invalid splits of edges
4980   // check if the vertex is invalid:
4981   // a. it may be the vertex SD with the vertices to avoid
4982   // b. or it may be the vertex which is created by the intersection
4983   //    of only existing edges, i.e. no new intersection edges goes
4984   //    through this vertex
4985   //
4986   TopTools_MapOfShape aMVInv;
4987   Standard_Integer i, aNb = aDMVE.Extent();
4988   for (i = 1; i <= aNb; ++i) {
4989     const TopoDS_Vertex& aV = TopoDS::Vertex(aDMVE.FindKey(i));
4990     if (theMVBounds.Contains(aV)) {
4991       continue;
4992     }
4993     //
4994     Standard_Integer nV = pDS->Index(aV);
4995     if ((nV >= 0) && !pDS->IsNewShape(nV)) {
4996       continue;
4997     }
4998     //
4999     TopTools_MapIteratorOfMapOfShape aItM(theVertsToAvoid);
5000     for (; aItM.More(); aItM.Next()) {
5001       const TopoDS_Vertex& aVInv = *(TopoDS_Vertex*)&aItM.Value();
5002       Standard_Integer iFlag = BOPTools_AlgoTools::ComputeVV(aV, aVInv);
5003       if (!iFlag) {
5004         aMVInv.Add(aV);
5005         break;
5006       }
5007     }
5008     //
5009     if (aItM.More()) {
5010       const TopTools_ListOfShape& aLVE = aDMVE.FindFromKey(aV);
5011       aIt.Initialize(aLVE);
5012       for (; aIt.More(); aIt.Next()) {
5013         const TopoDS_Shape& aE = aIt.Value();
5014         theMEInv.Add(aE);
5015       }
5016     }
5017   }
5018 }
5019
5020 //=======================================================================
5021 //function : UpdateValidEdges
5022 //purpose  : Making the new splits and updating the maps
5023 //=======================================================================
5024 void UpdateValidEdges(const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
5025                       const TopTools_IndexedDataMapOfShapeListOfShape& theFLE,
5026                       const TopTools_MapOfShape& theMVBounds,
5027                       const TopoDS_Shape& theSolids,
5028                       const TopTools_IndexedMapOfShape& theInvEdges,
5029                       const TopTools_MapOfShape& theInvertedEdges,
5030                       const TopTools_MapOfShape& theMEInvOnArt,
5031                       TopTools_MapOfShape& theMECheckExt,
5032                       TopTools_IndexedMapOfShape& theEdgesToAvoid,
5033                       TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
5034                       TopTools_DataMapOfShapeListOfShape& theOEImages,
5035                       TopTools_DataMapOfShapeListOfShape& theOEOrigins,
5036                       TopTools_MapOfShape& theVertsToAvoid,
5037                       TopTools_DataMapOfShapeShape& theETrimEInf,
5038                       TopTools_DataMapOfShapeListOfShape& theEImages,
5039                       TopTools_DataMapOfShapeListOfShape& theEETrim,
5040                       TopTools_MapOfShape& theModifiedEdges,
5041                       Handle(BRepAlgo_AsDes)& theAsDes)
5042 {
5043   // update images and origins of edges, plus update AsDes
5044   //
5045   // new edges
5046   TopTools_ListOfShape aLE;
5047   // back connection from edges to faces
5048   TopTools_DataMapOfShapeListOfShape aMELF;
5049   //
5050   TopTools_MapOfShape aMETmp;
5051   Standard_Integer i, aNb = theFLE.Extent();
5052   for (i = 1; i <= aNb; ++i) {
5053     const TopoDS_Face& aF = TopoDS::Face(theFLE.FindKey(i));
5054     //
5055     const TopTools_ListOfShape& aLEInt = theFLE(i);
5056     TopTools_ListIteratorOfListOfShape aItLE(aLEInt);
5057     for (; aItLE.More(); aItLE.Next()) {
5058       const TopoDS_Shape& aE = aItLE.Value();
5059       if ((theMECheckExt.Contains(aE) || aMETmp.Contains(aE)) && !theEImages.IsBound(aE)) {
5060         theMECheckExt.Remove(aE);
5061         aMETmp.Add(aE);
5062         continue;
5063       }
5064       TopTools_ListOfShape* pLF = aMELF.ChangeSeek(aE);
5065       if (!pLF) {
5066         pLF = aMELF.Bound(aE, TopTools_ListOfShape());
5067         aLE.Append(aE);
5068       }
5069       pLF->Append(aF);
5070     }
5071   }
5072   //
5073   if (aLE.IsEmpty()) {
5074     return;
5075   }
5076   //
5077   // bounding edges, that are going to be replaced
5078   TopTools_MapOfShape aMEB;
5079   //
5080   // new intersection edges
5081   TopTools_ListOfShape aLENew;
5082   TopTools_MapOfShape aMENew;
5083   // map of old vertices
5084   TopTools_MapOfShape aMVOld;
5085   // back connection to untrimmed edges
5086   TopTools_DataMapOfShapeListOfShape aDMEOr;
5087   //
5088   // trim the new intersection edges
5089   BOPCol_ListOfShape aLA;
5090   TrimNewIntersectionEdges(aLE, theEETrim, theMVBounds, theMECheckExt, theEImages,
5091                            aMEB, aMVOld, aLENew, aLA, aDMEOr, aMELF);
5092   //
5093   if (aLA.IsEmpty()) {
5094     // update intersection edges
5095     UpdateNewIntersectionEdges(aLE, aMELF, theEImages, theInvEdges, theInvertedEdges, theEdgesOrigins,
5096       theOEImages, theOEOrigins, theETrimEInf, theEETrim, theModifiedEdges, theAsDes);
5097     return;
5098   }
5099   //
5100   TopoDS_Shape aSplits1;
5101   if (aLA.Extent() > 1) {
5102     // intersect the new splits among themselves to avoid self-intersections
5103     IntersectEdges(aLA, aLE, aLENew, theMVBounds, theVertsToAvoid, theMECheckExt,
5104                    theEImages, theModifiedEdges, aDMEOr, aMELF, aMENew, aSplits1);
5105   }
5106   else {
5107     aSplits1 = aLA.First();
5108   }
5109   //
5110   // filter the new splits with bounds
5111   TopoDS_Shape aFilterBounds;
5112   GetBounds(theFImages, aMEB, aFilterBounds);
5113   //
5114   // intersect splits and bounds and remove those splits which have pure E/E intersection
5115   TopTools_MapOfShape aMEInv;
5116   GetInvalidEdgesByBounds(aSplits1, aFilterBounds, theFImages, theSolids,
5117                           theInvEdges, aMVOld, aMENew, aDMEOr, aMELF, theEImages,
5118                           theMECheckExt, theMEInvOnArt, theVertsToAvoid, aMEInv);
5119   //
5120   // get valid edges only
5121   TopoDS_Shape aSplits;
5122   if (aMEInv.Extent()) {
5123     // clear images from found invalid edges
5124     TopoDS_Compound aSp;
5125     BRep_Builder().MakeCompound(aSp);
5126     TopTools_MapOfShape aMFence;
5127     //
5128     TopTools_ListIteratorOfListOfShape aItLE(aLE);
5129     for (; aItLE.More(); aItLE.Next()) {
5130       const TopoDS_Shape& aE = aItLE.Value();
5131       //
5132       TopTools_ListOfShape* pLEIm = theEImages.ChangeSeek(aE);
5133       if (!pLEIm) {
5134         continue;
5135       }
5136       //
5137       TopTools_ListIteratorOfListOfShape aItLEIm(*pLEIm);
5138       for (; aItLEIm.More();) {
5139         const TopoDS_Shape& aEIm = aItLEIm.Value();
5140         if (aMEInv.Contains(aEIm)) {
5141           pLEIm->Remove(aItLEIm);
5142         }
5143         else {
5144           if (aMFence.Add(aEIm)) {
5145             BRep_Builder().Add(aSp, aEIm);
5146           }
5147           aItLEIm.Next();
5148         }
5149       }
5150       //
5151       if (pLEIm->IsEmpty()) {
5152         theEImages.UnBind(aE);
5153       }
5154     }
5155     aSplits = aSp;
5156   }
5157   else {
5158     aSplits = aSplits1;
5159   }
5160   //
5161   // get bounds to update
5162   // we need to update the edges of all the affected faces
5163   TopTools_ListOfShape aLF;
5164   // prepare the vertices from new splits of edges
5165   TopTools_IndexedMapOfShape aMVSp;
5166   TopExp::MapShapes(aSplits, TopAbs_VERTEX, aMVSp);
5167   //
5168   Standard_Integer aNbF = theFImages.Extent();
5169   for (i = 1; i <= aNbF; ++i) {
5170     const TopoDS_Shape& aF = theFImages.FindKey(i);
5171     if (theFLE.Contains(aF)) {
5172       aLF.Append(aF);
5173       continue;
5174     }
5175     //
5176     // check the splits of faces to have vertices from splits
5177     const TopTools_ListOfShape& aLFIm = theFImages(i);
5178     TopTools_ListIteratorOfListOfShape aItLFIm(aLFIm);
5179     for (; aItLFIm.More(); aItLFIm.Next()) {
5180       const TopoDS_Shape& aFIm = aItLFIm.Value();
5181       //
5182       TopExp_Explorer aExpV(aFIm, TopAbs_VERTEX);
5183       for (; aExpV.More(); aExpV.Next()) {
5184         const TopoDS_Shape& aV = aExpV.Current();
5185         if (aMVSp.Contains(aV)) {
5186           break;
5187         }
5188       }
5189       //
5190       if (aExpV.More()) {
5191         break;
5192       }
5193     }
5194     //
5195     if (aItLFIm.More()) {
5196       aLF.Append(aF);
5197     }
5198   }
5199   //
5200   // get bounds from splits of faces of aLF
5201   TopoDS_Shape aBounds;
5202   TopTools_ListOfShape aLAValid, aLABounds;
5203   GetBoundsToUpdate(aLF, theOEImages, theOEOrigins, aMEB,
5204                     aLABounds, aLAValid, aBounds, theAsDes);
5205   //
5206   // intersect valid splits with bounds and update both
5207   BOPAlgo_Builder aGF;
5208   aGF.AddArgument(aSplits);
5209   aGF.AddArgument(aBounds);
5210   aGF.Perform();
5211   //
5212   // update splits
5213   UpdateImages(aLE, theEImages, aGF, theModifiedEdges);
5214   //
5215   // update new intersection edges
5216   UpdateNewIntersectionEdges(aLE, aMELF, theEImages, theInvEdges, theInvertedEdges, theEdgesOrigins,
5217     theOEImages, theOEOrigins, theETrimEInf, theEETrim, theModifiedEdges, theAsDes);
5218   //
5219   // update bounds
5220   UpdateImages(aLAValid, theOEImages, aGF, theModifiedEdges);
5221   UpdateOrigins(aLABounds, theOEOrigins, aGF);
5222   UpdateOrigins(aLABounds, theEdgesOrigins, aGF);
5223   UpdateIntersectedEdges(aLABounds, theETrimEInf, aGF);
5224   //
5225   // update the edges to avoid with the splits
5226   TopTools_IndexedMapOfShape aNewEdges;
5227   const TopTools_ListOfShape* pSplitsIm = aGF.Images().Seek(aSplits);
5228   if (pSplitsIm) {
5229     TopTools_ListIteratorOfListOfShape aItSpIm(*pSplitsIm);
5230     for (; aItSpIm.More(); aItSpIm.Next()) {
5231       TopExp::MapShapes(aItSpIm.Value(), TopAbs_EDGE, aNewEdges);
5232     }
5233   }
5234   //
5235   Standard_Integer aNbE = theEdgesToAvoid.Extent();
5236   for (i = 1; i <= aNbE; ++i) {
5237     const TopoDS_Shape& aE = theEdgesToAvoid(i);
5238     const TopTools_ListOfShape& aLEIm = aGF.Modified(aE);
5239     TopTools_ListIteratorOfListOfShape aItLEIm(aLEIm);
5240     for (; aItLEIm.More(); aItLEIm.Next()) {
5241       const TopoDS_Shape& aEIm = aItLEIm.Value();
5242       if (!aNewEdges.Contains(aEIm)) {
5243         theEdgesToAvoid.Add(aItLEIm.Value());
5244       }
5245     }
5246   }
5247 }
5248
5249 //=======================================================================
5250 //function : TrimNewIntersectionEdges
5251 //purpose  :
5252 //=======================================================================
5253 void TrimNewIntersectionEdges(const TopTools_ListOfShape& theLE,
5254                               const TopTools_DataMapOfShapeListOfShape& theEETrim,
5255                               const TopTools_MapOfShape& theMVBounds,
5256                               TopTools_MapOfShape& theMECheckExt,
5257                               TopTools_DataMapOfShapeListOfShape& theEImages,
5258                               TopTools_MapOfShape& theMEB,
5259                               TopTools_MapOfShape& theMVOld,
5260                               TopTools_ListOfShape& theLENew,
5261                               BOPCol_ListOfShape& theLA,
5262                               TopTools_DataMapOfShapeListOfShape& theDMEOr,
5263                               TopTools_DataMapOfShapeListOfShape& theMELF)
5264 {
5265   TopTools_ListIteratorOfListOfShape aIt, aIt1;
5266   aIt.Initialize(theLE);
5267   for (; aIt.More(); aIt.Next()) {
5268     const TopoDS_Shape& aE = aIt.Value();
5269     //
5270     Standard_Boolean bCheckExt = theMECheckExt.Remove(aE);
5271     //
5272     Standard_Boolean bOld = theEETrim.IsBound(aE);
5273     if (bOld) {
5274       const TopTools_ListOfShape& aLET = theEETrim.Find(aE);
5275       aIt1.Initialize(aLET);
5276       for (; aIt1.More(); aIt1.Next()) {
5277         const TopoDS_Shape& aET = aIt1.Value();
5278         theMEB.Add(aET);
5279         TopExp_Explorer aExpV(aET, TopAbs_VERTEX);
5280         for (; aExpV.More(); aExpV.Next()) {
5281           const TopoDS_Shape& aV = aExpV.Current();
5282           theMVOld.Add(aV);
5283         }
5284       }
5285     }
5286     //
5287     if (!theEImages.IsBound(aE)) {
5288       continue;
5289     }
5290     //
5291     TopTools_ListOfShape& aLEIm = theEImages.ChangeFind(aE);
5292     if (aLEIm.IsEmpty()) {
5293       theEImages.UnBind(aE);
5294       continue;
5295     }
5296     //
5297     TopoDS_Shape aCEIm;
5298     TopTools_MapOfShape aMEVBounds;
5299     //
5300     if (aLEIm.Extent() > 1) {
5301       TopTools_IndexedMapOfShape aMV;
5302       // fuse these parts
5303       BOPAlgo_Builder aGFE;
5304       TopTools_ListIteratorOfListOfShape aItLEIm(aLEIm);
5305       for (; aItLEIm.More(); aItLEIm.Next()) {
5306         const TopoDS_Shape& aEIm = aItLEIm.Value();
5307         aGFE.AddArgument(aEIm);
5308         TopExp::MapShapes(aEIm, TopAbs_VERTEX, aMV);
5309       }
5310       //
5311       // add two bounding vertices of this edge to the operation
5312       TopoDS_Vertex aV1, aV2;
5313       TopExp::Vertices(TopoDS::Edge(aE), aV1, aV2);
5314       //
5315       aGFE.AddArgument(aV1);
5316       aGFE.AddArgument(aV2);
5317       aMV.Add(aV1);
5318       aMV.Add(aV2);
5319       //
5320       aGFE.Perform();
5321       if (!aGFE.ErrorStatus()) {
5322         // get images of bounding vertices to remove splits containing them
5323         // in case some of the bounding edges has been interfered
5324         // during operation it is necessary to update their images as well
5325         Standard_Integer iV, aNbV = aMV.Extent();
5326         for (iV = 1; iV <= aNbV; ++iV) {
5327           const TopoDS_Shape& aV = aMV(iV);
5328           if (theMVBounds.Contains(aV) || aV.IsSame(aV1) || aV.IsSame(aV2)) {
5329             const TopTools_ListOfShape& aLVIm = aGFE.Modified(aV);
5330             aMEVBounds.Add(aLVIm.IsEmpty() ? aV : aLVIm.First());
5331           }
5332         }
5333         //
5334         aCEIm = aGFE.Shape();
5335       }
5336     }
5337     else {
5338       aCEIm = aLEIm.First();
5339     }
5340     //
5341     aLEIm.Clear();
5342     //
5343     TopExp_Explorer aExp(aCEIm, TopAbs_EDGE);
5344     for (; aExp.More(); aExp.Next()) {
5345       const TopoDS_Shape& aEIm = aExp.Current();
5346       //
5347       // check the split not to contain bounding vertices
5348       TopoDS_Iterator aItV(aEIm);
5349       for (; aItV.More(); aItV.Next()) {
5350         const TopoDS_Shape& aV = aItV.Value();
5351         if (aMEVBounds.Contains(aV) || theMVBounds.Contains(aV)) {
5352           break;
5353         }
5354       }
5355       //
5356       if (!aItV.More()) {
5357         theLA.Append(aEIm);
5358         aLEIm.Append(aEIm);
5359         //
5360         theDMEOr.Bound(aEIm, TopTools_ListOfShape())->Append(aE);
5361       }
5362     }
5363     //
5364     if (aLEIm.IsEmpty()) {
5365       theEImages.UnBind(aE);
5366     }
5367     else {
5368       const TopTools_ListOfShape& aLFE = theMELF.Find(aE);
5369       TopTools_ListIteratorOfListOfShape aItLEIm(aLEIm);
5370       for (; aItLEIm.More(); aItLEIm.Next()) {
5371         const TopoDS_Shape& aEIm = aItLEIm.Value();
5372         TopTools_ListOfShape* pLFEIm = theMELF.ChangeSeek(aEIm);
5373         if (!pLFEIm) {
5374           pLFEIm = theMELF.Bound(aEIm, TopTools_ListOfShape());
5375         }
5376         TopTools_ListIteratorOfListOfShape aItLF(aLFE);
5377         for (; aItLF.More(); aItLF.Next()) {
5378           AppendToList(*pLFEIm, aItLF.Value());
5379         }
5380         //
5381         if (bCheckExt) {
5382           theMECheckExt.Add(aEIm);
5383         }
5384         else if (!bOld) {
5385           theLENew.Append(aEIm);
5386         }
5387       }
5388     }
5389   }
5390 }
5391
5392 //=======================================================================
5393 //function : IntersectEdges
5394 //purpose  : Intersecting the trimmed edges to avoid self-intersections
5395 //=======================================================================
5396 void IntersectEdges(const BOPCol_ListOfShape& theLA,
5397                     const TopTools_ListOfShape& theLE,
5398                     const TopTools_ListOfShape& theLENew,
5399                     const TopTools_MapOfShape& theMVBounds,
5400                     const TopTools_MapOfShape& theVertsToAvoid,
5401                     TopTools_MapOfShape& theMECheckExt,
5402                     TopTools_DataMapOfShapeListOfShape& theEImages,
5403                     TopTools_MapOfShape& theModifiedEdges,
5404                     TopTools_DataMapOfShapeListOfShape& theDMEOr,
5405                     TopTools_DataMapOfShapeListOfShape& theMELF,
5406                     TopTools_MapOfShape& theMENew,
5407                     TopoDS_Shape& theSplits)
5408 {
5409   BOPAlgo_Builder aGFA;
5410   aGFA.SetArguments(theLA);
5411   aGFA.Perform();
5412   if (aGFA.ErrorStatus()) {
5413     // just copy input to the result
5414     TopoDS_Compound aSp;
5415     BRep_Builder aBB;
5416     aBB.MakeCompound(aSp);
5417     BOPCol_ListIteratorOfListOfShape anIt(theLA);
5418     for (; anIt.More(); anIt.Next()) {
5419       const TopoDS_Shape& aE = anIt.Value();
5420       aBB.Add(aSp, aE);
5421     }
5422     theSplits = aSp;
5423     return;
5424   }
5425   //
5426   UpdateImages(theLE, theEImages, aGFA, theModifiedEdges);
5427   //
5428   // compound of valid splits
5429   theSplits = aGFA.Shape();
5430   //
5431   // update new edges
5432   TopTools_ListIteratorOfListOfShape aIt, aIt1;
5433   aIt.Initialize(theLENew);
5434   for (; aIt.More(); aIt.Next()) {
5435     const TopoDS_Shape& aE = aIt.Value();
5436     const TopTools_ListOfShape& aLEIm = aGFA.Modified(aE);
5437     if (aLEIm.Extent()) {
5438       aIt1.Initialize(aLEIm);
5439       for (; aIt1.More(); aIt1.Next()) {
5440         const TopoDS_Shape& aEIm = aIt1.Value();
5441         theMENew.Add(aEIm);
5442       }
5443     }
5444     else {
5445       theMENew.Add(aE);
5446     }
5447   }
5448   //
5449   // update edges after intersection for extended checking
5450   aIt.Initialize(theLA);
5451   for (; aIt.More(); aIt.Next()) {
5452     const TopoDS_Shape& aE = aIt.Value();
5453     const TopTools_ListOfShape& aLEIm = aGFA.Modified(aE);
5454     if (aLEIm.IsEmpty()) {
5455       continue;
5456     }
5457     //
5458     if (theMECheckExt.Contains(aE)) {
5459       aIt1.Initialize(aLEIm);
5460       for (; aIt1.More(); aIt1.Next()) {
5461         theMECheckExt.Add(aIt1.Value());
5462       }
5463       theMECheckExt.Remove(aE);
5464     }
5465     //
5466     const TopTools_ListOfShape& aLFE = theMELF.Find(aE);
5467     aIt1.Initialize(aLEIm);
5468     for (; aIt1.More(); aIt1.Next()) {
5469       const TopoDS_Shape& aEIm = aIt1.Value();
5470       TopTools_ListOfShape* pLFEIm = theMELF.ChangeSeek(aEIm);
5471       if (!pLFEIm) {
5472         pLFEIm = theMELF.Bound(aEIm, TopTools_ListOfShape());
5473       }
5474       TopTools_ListIteratorOfListOfShape aItLF(aLFE);
5475       for (; aItLF.More(); aItLF.Next()) {
5476         AppendToList(*pLFEIm, aItLF.Value());
5477       }
5478     }
5479   }
5480   //
5481   TopTools_MapOfShape aMEInv;
5482   GetInvalidEdges(theVertsToAvoid, theMVBounds, aGFA, aMEInv);
5483   if (aMEInv.Extent()) {
5484     // update shape
5485     TopoDS_Compound aSp;
5486     BRep_Builder aBB;
5487     aBB.MakeCompound(aSp);
5488     TopExp_Explorer aExp(theSplits, TopAbs_EDGE);
5489     for (; aExp.More(); aExp.Next()) {
5490       const TopoDS_Shape& aE = aExp.Current();
5491       if (!aMEInv.Contains(aE)) {
5492         aBB.Add(aSp, aE);
5493       }
5494     }
5495     theSplits = aSp;
5496   }
5497   //
5498   UpdateOrigins(theLA, theDMEOr, aGFA);
5499 }
5500
5501 //=======================================================================
5502 //function : GetBounds
5503 //purpose  : Getting edges from the splits of offset faces
5504 //=======================================================================
5505 void GetBounds(const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
5506                const TopTools_MapOfShape& theMEB,
5507                TopoDS_Shape& theBounds)
5508 {
5509   // make compound of edges contained in the splits of faces
5510   TopoDS_Compound aBounds;
5511   BRep_Builder aBB;
5512   aBB.MakeCompound(aBounds);
5513   //
5514   TopTools_MapOfShape aMFence;
5515   //
5516   Standard_Integer i, aNb = theFImages.Extent();
5517   for (i = 1; i <= aNb; ++i) {
5518     const TopTools_ListOfShape& aLFIm = theFImages(i);
5519     TopTools_ListIteratorOfListOfShape aIt(aLFIm);
5520     for (; aIt.More(); aIt.Next()) {
5521       const TopoDS_Shape& aFIm = aIt.Value();
5522       //
5523       TopExp_Explorer aExpE(aFIm, TopAbs_EDGE);
5524       for (; aExpE.More(); aExpE.Next()) {
5525         const TopoDS_Shape& aEIm = aExpE.Current();
5526         if (!theMEB.Contains(aEIm) && aMFence.Add(aEIm)) {
5527           aBB.Add(aBounds, aEIm);
5528         }
5529       }
5530     }
5531   }
5532   theBounds = aBounds;
5533 }
5534
5535 //=======================================================================
5536 //function : GetBoundsToUpdate
5537 //purpose  : Get bounding edges that should be updated
5538 //=======================================================================
5539 void GetBoundsToUpdate(const TopTools_ListOfShape& theLF,
5540                        const TopTools_DataMapOfShapeListOfShape& theOEImages,
5541                        const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
5542                        const TopTools_MapOfShape& theMEB,
5543                        TopTools_ListOfShape& theLABounds,
5544                        TopTools_ListOfShape& theLAValid,
5545                        TopoDS_Shape& theBounds,
5546                        Handle(BRepAlgo_AsDes)& theAsDes)
5547 {
5548   // get all edges
5549   TopoDS_Compound aBounds;
5550   BRep_Builder aBB;
5551   aBB.MakeCompound(aBounds);
5552   //
5553   TopTools_MapOfShape aMAValid, aMFence;
5554   //
5555   TopTools_ListIteratorOfListOfShape aItLF(theLF);
5556   for (; aItLF.More(); aItLF.Next()) {
5557     const TopoDS_Shape& aF = aItLF.Value();
5558     //
5559     TopTools_IndexedMapOfShape aMDE;
5560     const TopTools_ListOfShape& aLFDes = theAsDes->Descendant(aF);
5561     TopTools_ListIteratorOfListOfShape aItLFDes(aLFDes);
5562     for (; aItLFDes.More(); aItLFDes.Next()) {
5563       const TopoDS_Shape& aED = aItLFDes.Value();
5564       const TopTools_ListOfShape *pLEDIm = theOEImages.Seek(aED);
5565       if (!pLEDIm) {
5566         aMDE.Add(aED);
5567         continue;
5568       }
5569       //
5570       TopTools_ListIteratorOfListOfShape aItLEDIm(*pLEDIm);
5571       for (; aItLEDIm.More(); aItLEDIm.Next()) {
5572         const TopoDS_Shape& aEDIm = aItLEDIm.Value();
5573         aMDE.Add(aEDIm);
5574       }
5575     }
5576     //
5577     Standard_Integer j, aNbE = aMDE.Extent();
5578     for (j = 1; j <= aNbE; ++j) {
5579       const TopoDS_Edge& aEIm = TopoDS::Edge(aMDE(j));
5580       //
5581       if (!theMEB.Contains(aEIm) && aMFence.Add(aEIm)) {
5582         aBB.Add(aBounds, aEIm);
5583         theLABounds.Append(aEIm);
5584       }
5585       //
5586       const TopTools_ListOfShape *pLO = theOEOrigins.Seek(aEIm);
5587       if (pLO) {
5588         TopTools_ListIteratorOfListOfShape aItLO(*pLO);
5589         for (; aItLO.More(); aItLO.Next()) {
5590           const TopoDS_Shape& aEO = aItLO.Value();
5591           //
5592           if (aMAValid.Add(aEO)) {
5593             theLAValid.Append(aEO);
5594           }
5595         }
5596       }
5597       else {
5598         if (aMAValid.Add(aEIm)) {
5599           theLAValid.Append(aEIm);
5600         }
5601       }
5602     }
5603   }
5604   theBounds = aBounds;
5605 }
5606
5607 //=======================================================================
5608 //function : GetInvalidEdgesByBounds
5609 //purpose  : Filter new splits by intersection with bounds
5610 //=======================================================================
5611 void GetInvalidEdgesByBounds(const TopoDS_Shape& theSplits,
5612                              const TopoDS_Shape& theBounds,
5613                              const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
5614                              const TopoDS_Shape& theSolids,
5615                              const TopTools_IndexedMapOfShape& theInvEdges,
5616                              const TopTools_MapOfShape& theMVOld,
5617                              const TopTools_MapOfShape& theMENew,
5618                              const TopTools_DataMapOfShapeListOfShape& theDMEOr,
5619                              const TopTools_DataMapOfShapeListOfShape& theMELF,
5620                              const TopTools_DataMapOfShapeListOfShape& theEImages,
5621                              const TopTools_MapOfShape& theMECheckExt,
5622                              const TopTools_MapOfShape& theMEInvOnArt,
5623                              TopTools_MapOfShape& theVertsToAvoid,
5624                              TopTools_MapOfShape& theMEInv)
5625 {
5626   // map splits to check the vertices of edges
5627   TopTools_IndexedDataMapOfShapeListOfShape aDMVE;
5628   TopExp::MapShapesAndAncestors(theSplits, TopAbs_VERTEX, TopAbs_EDGE, aDMVE);
5629   //
5630   BOPAlgo_Section aSec;
5631   aSec.AddArgument(theSplits);
5632   aSec.AddArgument(theBounds);
5633   //
5634   aSec.Perform();
5635   //
5636   // invalid vertices
5637   TopTools_IndexedMapOfShape aMVInv;
5638   // vertices to check additionally by classification relatively to solid
5639   TopTools_MapOfShape aMVCheckAdd;
5640   // collect parts for removal
5641   const BOPDS_PDS& pDS = aSec.PDS();
5642   //
5643   // check edge/edge intersections
5644   const BOPDS_VectorOfInterfEE& aEEs = pDS->InterfEE();
5645   Standard_Integer i, aNb = aEEs.Extent();
5646   for (i = 0; i < aNb; ++i) {
5647     const BOPDS_InterfEE& aEE = aEEs(i);
5648     //
5649     const TopoDS_Shape& aE1 = pDS->Shape(aEE.Index1());
5650     const TopoDS_Shape& aE2 = pDS->Shape(aEE.Index2());
5651     //
5652     if (!aEE.HasIndexNew()) {
5653       if (theMECheckExt.Contains(aE1) && (aEE.CommonPart().Type() == TopAbs_EDGE)) {
5654         theMEInv.Add(aE1);
5655       }
5656       continue;
5657     }
5658     //
5659     if (theInvEdges.Contains(aE2)) {
5660       theMEInv.Add(aE1);
5661     }
5662     //
5663     if (theMEInvOnArt.Contains(aE2)) {
5664       // avoid checking of the vertices of the split edge intersected by
5665       // the invalid edge from artificial face
5666       TopoDS_Vertex aV1, aV2;
5667       TopExp::Vertices(TopoDS::Edge(aE2), aV1, aV2);
5668       if (aDMVE.Contains(aV1) && aDMVE.Contains(aV2)) {
5669         continue;
5670       }
5671     }
5672     //
5673     // add vertices of all images of the edge from splits for checking
5674     const TopTools_ListOfShape& aLEOr = theDMEOr.Find(aE1);
5675     TopTools_ListIteratorOfListOfShape aItLEOr(aLEOr);
5676     for (; aItLEOr.More(); aItLEOr.Next()) {
5677       const TopoDS_Shape& aEOr = aItLEOr.Value();
5678       //
5679       const TopTools_ListOfShape& aLEIm = theEImages.Find(aEOr);
5680       TopTools_ListIteratorOfListOfShape aItLEIm(aLEIm);
5681       for (; aItLEIm.More(); aItLEIm.Next()) {
5682         const TopoDS_Shape& aEIm = aItLEIm.Value();
5683         //
5684         TopoDS_Iterator aItV(aEIm);
5685         for (; aItV.More(); aItV.Next()) {
5686           const TopoDS_Shape& aV = aItV.Value();
5687           if (!theMVOld.Contains(aV)) {
5688             aMVInv.Add(aV);
5689             aMVCheckAdd.Add(aV);
5690           }
5691         }
5692       }
5693     }
5694   }
5695   //
5696   // to avoid unnecessary filling of parts due to extra trim of the edges
5697   // process Edge/Edge interferences of type EDGE, i.e. common blocks and check
5698   // not the bounding vertices of the edges, but check the edge itself
5699   // to be lying on some face
5700   //
5701   // all common blocks are contained in the result of SECTION operation
5702   // between sets of edges
5703   const TopoDS_Shape& aSecR = aSec.Shape();
5704   //
5705   TopTools_IndexedMapOfShape aMSSec;
5706   TopExp::MapShapes(aSecR, aMSSec);
5707   //
5708   const BOPCol_DataMapOfShapeListOfShape& anIm = aSec.Images();
5709   for (TopExp_Explorer aExp(theSplits, TopAbs_EDGE); aExp.More(); aExp.Next())
5710   {
5711     const TopoDS_Shape& aE = aExp.Current();
5712     if (aSec.IsDeleted(aE)) {
5713       // no common blocks for this edge
5714       continue;
5715     }
5716     //
5717     const BOPCol_ListOfShape* pLEIm = anIm.Seek(aE);
5718     if (!pLEIm) {
5719       // no splits, i.e. completely coincides with some edge from boundary
5720       continue;
5721     }
5722     //
5723     BOPCol_ListIteratorOfListOfShape aItLEIm(*pLEIm);
5724     for (; aItLEIm.More(); aItLEIm.Next()) {
5725       const TopoDS_Shape& aEIm = aItLEIm.Value();
5726       if (!aMSSec.Contains(aEIm)) {
5727         // the edge included in section only partially.
5728         // the part not included in section may be excessive
5729         //
5730         // check vertices of this edge - if one of them is new
5731         // the edge might be removed
5732         TopoDS_Vertex aV1, aV2;
5733         TopExp::Vertices(TopoDS::Edge(aEIm), aV1, aV2);
5734         if (!theMVOld.Contains(aV1) || !theMVOld.Contains(aV2)) {
5735           // add this edge for checking by making new vertex in the middle of the edge
5736           TopoDS_Vertex aV;
5737           Standard_Real f, l;
5738           const Handle(Geom_Curve)& aC = BRep_Tool::Curve(TopoDS::Edge(aEIm), f, l);
5739           BRep_Builder().MakeVertex(aV, aC->Value((f+l)*0.5), Precision::Confusion());
5740           // and adding this vertex for checking
5741           aDMVE.ChangeFromIndex(aDMVE.Add(aV, TopTools_ListOfShape())).Append(aE);
5742           aMVInv.Add(aV);
5743           break;
5744         }
5745       }
5746     }
5747   }
5748   //
5749   // Add for check also the edges created from common between splits
5750   // of offset faces edges not connected to any invalidity.
5751   // These edges may also accidentally fill some part.
5752   TopTools_MapIteratorOfMapOfShape aItM(theMECheckExt);
5753   for (; aItM.More(); aItM.Next()) {
5754     const TopoDS_Shape& aE = aItM.Value();
5755     //
5756     // make new vertex in the middle of the edge
5757     TopoDS_Vertex aV;
5758     Standard_Real f, l;
5759     const Handle(Geom_Curve)& aC = BRep_Tool::Curve(TopoDS::Edge(aE), f, l);
5760     BRep_Builder().MakeVertex(aV, aC->Value((f + l)*0.5), Precision::Confusion());
5761     // add this vertex for checking
5762     aDMVE.ChangeFromIndex(aDMVE.Add(aV, TopTools_ListOfShape())).Append(aE);
5763     aMVInv.Add(aV);
5764   }
5765   //
5766   // add for check also the vertices connected only to new or old edges
5767   aNb = aDMVE.Extent();
5768   for (i = 1; i <= aNb; ++i) {
5769     const TopoDS_Shape& aV = aDMVE.FindKey(i);
5770     if (theMVOld.Contains(aV)) {
5771       continue;
5772     }
5773     //
5774     Standard_Boolean bNew = Standard_False, bOld = Standard_False;
5775     const TopTools_ListOfShape& aLEx = aDMVE(i);
5776     TopTools_ListIteratorOfListOfShape aIt(aLEx);
5777     for (; aIt.More(); aIt.Next()) {
5778       const TopoDS_Shape& aE = aIt.Value();
5779       if (theMECheckExt.Contains(aE)) {
5780         continue;
5781       }
5782       //
5783       if (theMENew.Contains(aE)) {
5784         bNew = Standard_True;
5785       }
5786       else {
5787         bOld = Standard_True;
5788       }
5789       //
5790       if (bNew && bOld) {
5791         break;
5792       }
5793     }
5794     //
5795     if (!bNew || !bOld) {
5796       aMVInv.Add(aV);
5797       aMVCheckAdd.Remove(aV);
5798     }
5799   }
5800   //
5801   // perform the checking
5802   Handle(IntTools_Context) aCtx = new IntTools_Context;
5803   // filter vertices
5804   Standard_Integer iv, aNbIV = aMVInv.Extent();
5805   for (iv = 1; iv <= aNbIV; ++iv) {
5806     const TopoDS_Vertex& aV = TopoDS::Vertex(aMVInv(iv));
5807     if (theMVOld.Contains(aV)) {
5808       continue;
5809     }
5810     //
5811     const TopTools_ListOfShape* pLEInv = aDMVE.Seek(aV);
5812     if (!pLEInv) {
5813       continue;
5814     }
5815     // find faces by the edges to check the vertex
5816     TopTools_IndexedMapOfShape aMF;
5817     TopTools_ListIteratorOfListOfShape aItLE(*pLEInv);
5818     for (; aItLE.More(); aItLE.Next()) {
5819       const TopoDS_Shape& aE = aItLE.Value();
5820       const TopTools_ListOfShape& aLF = theMELF.Find(aE);
5821       TopTools_ListIteratorOfListOfShape aItLF(aLF);
5822       for (; aItLF.More(); aItLF.Next()) {
5823         aMF.Add(aItLF.Value());
5824       }
5825     }
5826     //
5827     // check the vertex to belong to some split of the faces
5828     Standard_Boolean bInvalid = Standard_True;
5829     //
5830     Standard_Integer aNbF = aMF.Extent();
5831     for (i = 1; i <= aNbF && bInvalid; ++i) {
5832       const TopoDS_Face& aF = TopoDS::Face(aMF(i));
5833       const TopTools_ListOfShape& aLFIm = theFImages.FindFromKey(aF);
5834       //
5835       TopTools_ListIteratorOfListOfShape aItLF(aLFIm);
5836       for (; aItLF.More() && bInvalid; aItLF.Next()) {
5837         const TopoDS_Face& aFIm = TopoDS::Face(aItLF.Value());
5838         TopExp_Explorer aExp(aFIm, TopAbs_VERTEX);
5839         for (; aExp.More() && bInvalid; aExp.Next()) {
5840           const TopoDS_Shape& aVF = aExp.Current();
5841           bInvalid = !aVF.IsSame(aV);
5842         }
5843       }
5844       //
5845       if (bInvalid) {
5846         Standard_Real U, V, aTol;
5847         Standard_Integer iStatus = aCtx->ComputeVF(aV, aF, U, V, aTol);
5848         if (!iStatus) {
5849           // classify the point relatively faces
5850           gp_Pnt2d aP2d(U, V);
5851           aItLF.Initialize(aLFIm);
5852           for (; aItLF.More() && bInvalid; aItLF.Next()) {
5853             const TopoDS_Face& aFIm = TopoDS::Face(aItLF.Value());
5854             bInvalid = !aCtx->IsPointInOnFace(aFIm, aP2d);
5855           }
5856         }
5857       }
5858     }
5859     //
5860     if (bInvalid && aMVCheckAdd.Contains(aV)) {
5861       // the vertex is invalid for all faces
5862       // check the same vertex for the solids
5863       const gp_Pnt& aP = BRep_Tool::Pnt(aV);
5864       Standard_Real aTolV = BRep_Tool::Tolerance(aV);
5865       //
5866       TopExp_Explorer aExpS(theSolids, TopAbs_SOLID);
5867       for (; aExpS.More() && bInvalid; aExpS.Next()) {
5868         const TopoDS_Solid& aSol = TopoDS::Solid(aExpS.Current());
5869         BRepClass3d_SolidClassifier& aSC = aCtx->SolidClassifier(aSol);
5870         aSC.Perform(aP, aTolV);
5871         bInvalid = (aSC.State() == TopAbs_OUT);
5872       }
5873     }
5874     //
5875     if (bInvalid) {
5876       theVertsToAvoid.Add(aV);
5877       aItLE.Initialize(*pLEInv);
5878       for (; aItLE.More(); aItLE.Next()) {
5879         theMEInv.Add(aItLE.Value());
5880       }
5881     }
5882   }
5883 }
5884
5885 //=======================================================================
5886 //function : UpdateNewIntersectionEdges
5887 //purpose  : Updating the maps of images and origins of the offset edges
5888 //=======================================================================
5889 void UpdateNewIntersectionEdges(const TopTools_ListOfShape& theLE,
5890                                 const TopTools_DataMapOfShapeListOfShape& theMELF,
5891                                 const TopTools_DataMapOfShapeListOfShape& theEImages,
5892                                 const TopTools_IndexedMapOfShape& theInvEdges,
5893                                 const TopTools_MapOfShape& theInvertedEdges,
5894                                 TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
5895                                 TopTools_DataMapOfShapeListOfShape& theOEImages,
5896                                 TopTools_DataMapOfShapeListOfShape& theOEOrigins,
5897                                 TopTools_DataMapOfShapeShape& theETrimEInf,
5898                                 TopTools_DataMapOfShapeListOfShape& theEETrim,
5899                                 TopTools_MapOfShape& theModifiedEdges,
5900                                 Handle(BRepAlgo_AsDes)& theAsDes)
5901 {
5902   TopTools_ListOfShape aLEImEmpty;
5903   TopTools_ListIteratorOfListOfShape aIt, aIt1;
5904   // update global maps of images and origins with new splits
5905   aIt.Initialize(theLE);
5906   for (; aIt.More(); aIt.Next()) {
5907     const TopoDS_Shape& aE = aIt.Value();
5908     //
5909     if (!theEImages.IsBound(aE)) {
5910       TopTools_ListOfShape* pLET = theEETrim.ChangeSeek(aE);
5911       if (!pLET) {
5912         continue;
5913       }
5914       //
5915       TopTools_ListIteratorOfListOfShape aItLET(*pLET);
5916       for (; aItLET.More();) {
5917         const TopoDS_Shape& aET = aItLET.Value();
5918         if (!theInvEdges.Contains(aET) && !theInvertedEdges.Contains(aET)) {
5919           pLET->Remove(aItLET);
5920         }
5921         else {
5922           aItLET.Next();
5923         }
5924       }
5925       //
5926       if (pLET->IsEmpty()) {
5927         continue;
5928       }
5929     }
5930     // new images
5931     const TopTools_ListOfShape& aLENew =
5932       theEImages.IsBound(aE) ? theEImages.Find(aE) : aLEImEmpty;
5933     //
5934     // save connection to untrimmed edge for the next steps
5935     aIt1.Initialize(aLENew);
5936     for (; aIt1.More(); aIt1.Next()) {
5937       const TopoDS_Shape& aET = aIt1.Value();
5938       theETrimEInf.Bind(aET, aE);
5939       theModifiedEdges.Add(aET);
5940     }
5941     //
5942     // check if it is existing edge
5943     if (!theEETrim.IsBound(aE)) {
5944       const TopTools_ListOfShape& aLF = theMELF.Find(aE);
5945       // the edge is new
5946       // add this edge to AsDes
5947       aIt1.Initialize(aLF);
5948       for (; aIt1.More(); aIt1.Next()) {
5949         const TopoDS_Shape& aF = aIt1.Value();
5950         theAsDes->Add(aF, aE);
5951       }
5952       //
5953       // add aE to the images
5954       theOEImages.Bind(aE, aLENew);
5955       theModifiedEdges.Add(aE);
5956       //
5957       // add to origins
5958       TopTools_ListIteratorOfListOfShape aItNew(aLENew);
5959       for (; aItNew.More(); aItNew.Next()) {
5960         const TopoDS_Shape& aENew = aItNew.Value();
5961         if (theOEOrigins.IsBound(aENew)) {
5962           TopTools_ListOfShape& aEOrigins = theOEOrigins.ChangeFind(aENew);
5963           AppendToList(aEOrigins, aE);
5964         }
5965         else {
5966           TopTools_ListOfShape aEOrigins;
5967           aEOrigins.Append(aE);
5968           theOEOrigins.Bind(aENew, aEOrigins);
5969         }
5970       }
5971       //
5972       // update connection to initial origins
5973       if (theEdgesOrigins.IsBound(aE)) {
5974         const TopTools_ListOfShape& aLEOrInit = theEdgesOrigins.Find(aE);
5975         aIt1.Initialize(aLENew);
5976         for (; aIt1.More(); aIt1.Next()) {
5977           const TopoDS_Shape& aENew = aIt1.Value();
5978           if (theEdgesOrigins.IsBound(aENew)) {
5979             TopTools_ListOfShape& aLENewOr = theEdgesOrigins.ChangeFind(aENew);
5980             TopTools_ListIteratorOfListOfShape aItOrInit(aLEOrInit);
5981             for (; aItOrInit.More(); aItOrInit.Next()) {
5982               const TopoDS_Shape& aEOr = aItOrInit.Value();
5983               AppendToList(aLENewOr, aEOr);
5984             }
5985           }
5986           else {
5987             theEdgesOrigins.Bind(aENew, aLEOrInit);
5988           }
5989         }
5990       }
5991       //
5992       continue;
5993     }
5994     //
5995     // old images
5996     const TopTools_ListOfShape& aLEOld = theEETrim.Find(aE);
5997     //
5998     // list of initial origins
5999     TopTools_ListOfShape anInitOrigins;
6000     //
6001     // it is necessary to replace the old edges with new ones
6002     aIt1.Initialize(aLEOld);
6003     for (; aIt1.More(); aIt1.Next()) {
6004       const TopoDS_Shape& aEOld = aIt1.Value();
6005       //
6006       if (theOEOrigins.IsBound(aEOld)) {
6007         // get its origins
6008         const TopTools_ListOfShape& aEOrigins = theOEOrigins.Find(aEOld);
6009         //
6010         TopTools_ListIteratorOfListOfShape aItOr(aEOrigins);
6011         for (; aItOr.More(); aItOr.Next()) {
6012           const TopoDS_Shape& aEOr = aItOr.Value();
6013           //
6014           theModifiedEdges.Add(aEOr);
6015           //
6016           TopTools_ListOfShape& aEImages = theOEImages.ChangeFind(aEOr);
6017           //
6018           // remove old edge from images
6019           TopTools_ListIteratorOfListOfShape aItIm(aEImages);
6020           for (; aItIm.More(); ) {
6021             const TopoDS_Shape& aEIm = aItIm.Value();
6022             if (aEIm.IsSame(aEOld)) {
6023               aEImages.Remove(aItIm);
6024             }
6025             else {
6026               aItIm.Next();
6027             }
6028           }
6029           //
6030           // add new images
6031           TopTools_ListIteratorOfListOfShape aItNew(aLENew);
6032           for (; aItNew.More(); aItNew.Next()) {
6033             const TopoDS_Shape& aENew = aItNew.Value();
6034             AppendToList(aEImages, aENew);
6035             if (theOEOrigins.IsBound(aENew)) {
6036               TopTools_ListOfShape& aENewOrigins = theOEOrigins.ChangeFind(aENew);
6037               AppendToList(aENewOrigins, aEOr);
6038             }
6039             else {
6040               TopTools_ListOfShape aENewOrigins;
6041               aENewOrigins.Append(aEOr);
6042               theOEOrigins.Bind(aENew, aENewOrigins);
6043             }
6044           }
6045         }
6046       }
6047       else {
6048         // add to images
6049         theOEImages.Bind(aEOld, aLENew);
6050         //
6051         theModifiedEdges.Add(aEOld);
6052         //
6053         // add to origins
6054         TopTools_ListIteratorOfListOfShape aItNew(aLENew);
6055         for (; aItNew.More(); aItNew.Next()) {
6056           const TopoDS_Shape& aENew = aItNew.Value();
6057           if (theOEOrigins.IsBound(aENew)) {
6058             TopTools_ListOfShape& aEOrigins = theOEOrigins.ChangeFind(aENew);
6059             AppendToList(aEOrigins, aEOld);
6060           }
6061           else {
6062             TopTools_ListOfShape aEOrigins;
6063             aEOrigins.Append(aEOld);
6064             theOEOrigins.Bind(aENew, aEOrigins);
6065           }
6066         }
6067       }
6068       //
6069       // update connection to initial shape
6070       if (theEdgesOrigins.IsBound(aEOld)) {
6071         const TopTools_ListOfShape& aLEOrInit = theEdgesOrigins.Find(aEOld);
6072         TopTools_ListIteratorOfListOfShape aItEOrInit(aLEOrInit);
6073         for (; aItEOrInit.More(); aItEOrInit.Next()) {
6074           const TopoDS_Shape& aEOrInit = aItEOrInit.Value();
6075           AppendToList(anInitOrigins, aEOrInit);
6076         }
6077       }
6078     }
6079     //
6080     if (anInitOrigins.Extent()) {
6081       TopTools_ListIteratorOfListOfShape aItNew(aLENew);
6082       for (; aItNew.More(); aItNew.Next()) {
6083         const TopoDS_Shape& aENew = aItNew.Value();
6084         if (theEdgesOrigins.IsBound(aENew)) {
6085           TopTools_ListOfShape& aLENewOr = theEdgesOrigins.ChangeFind(aENew);
6086           TopTools_ListIteratorOfListOfShape aItOrInit(anInitOrigins);
6087           for (; aItOrInit.More(); aItOrInit.Next()) {
6088             const TopoDS_Shape& aEOr = aItOrInit.Value();
6089             AppendToList(aLENewOr, aEOr);
6090           }
6091         }
6092         else {
6093           theEdgesOrigins.Bind(aENew, anInitOrigins);
6094         }
6095       }
6096     }
6097   }
6098 }
6099
6100 //=======================================================================
6101 //function : FillHistory
6102 //purpose  : Saving obtained results in history tools
6103 //=======================================================================
6104 void FillHistory(const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
6105                  const TopTools_DataMapOfShapeListOfShape& theEImages,
6106                  BRepAlgo_Image& theImage)
6107 {
6108   Standard_Integer i, aNb = theFImages.Extent();
6109   if (!aNb) {
6110     return;
6111   }
6112   //
6113   BRep_Builder aBB;
6114   TopoDS_Compound aFaces;
6115   aBB.MakeCompound(aFaces);
6116   //
6117   // Fill history for faces
6118   for (i = 1; i <= aNb; ++i) {
6119     const TopoDS_Shape& aF = theFImages.FindKey(i);
6120     const TopTools_ListOfShape& aLFImages = theFImages(i);
6121     //
6122     if (aLFImages.Extent()) {
6123       if (theImage.HasImage(aF)) {
6124         theImage.Add(aF, aLFImages);
6125       }
6126       else {
6127         theImage.Bind(aF, aLFImages);
6128       }
6129     }
6130     //
6131     TopTools_ListIteratorOfListOfShape aItLF(aLFImages);
6132     for (; aItLF.More(); aItLF.Next()) {
6133       const TopoDS_Shape& aFIm = aItLF.Value();
6134       aBB.Add(aFaces, aFIm);
6135     }
6136   }
6137   //
6138   // fill history for edges
6139   TopTools_IndexedMapOfShape aMFE;
6140   TopExp::MapShapes(aFaces, TopAbs_EDGE, aMFE);
6141   //
6142   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape aItEIm(theEImages);
6143   for (; aItEIm.More(); aItEIm.Next()) {
6144     const TopoDS_Shape& aE = aItEIm.Key();
6145     const TopTools_ListOfShape& aLEIm = aItEIm.Value();
6146     //
6147     Standard_Boolean bHasImage = theImage.HasImage(aE);
6148     TopTools_ListIteratorOfListOfShape aItLE(aLEIm);
6149     for (; aItLE.More(); aItLE.Next()) {
6150       const TopoDS_Shape& aEIm = aItLE.Value();
6151       if (aMFE.Contains(aEIm)) {
6152         if (bHasImage) {
6153           theImage.Add(aE, aEIm);
6154         }
6155         else {
6156           theImage.Bind(aE, aEIm);
6157           bHasImage = Standard_True;
6158         }
6159       }
6160     }
6161   }
6162 }
6163
6164 //=======================================================================
6165 //function : ProcessMicroEdge
6166 //purpose  : Checking if the edge is micro edge
6167 //=======================================================================
6168 Standard_Boolean ProcessMicroEdge(const TopoDS_Edge& theEdge,
6169                                   const Handle(IntTools_Context)& theCtx)
6170 {
6171   TopoDS_Vertex aV1, aV2;
6172   TopExp::Vertices(theEdge, aV1, aV2);
6173   if (aV1.IsNull() || aV2.IsNull()) {
6174     return Standard_False;
6175   }
6176   //
6177   Standard_Boolean bMicro = BOPTools_AlgoTools::IsMicroEdge(theEdge, theCtx);
6178   if (bMicro && BRepAdaptor_Curve(theEdge).GetType() == GeomAbs_Line) {
6179     Standard_Real aLen = BRep_Tool::Pnt(aV1).Distance(BRep_Tool::Pnt(aV2));
6180     BRep_Builder().UpdateVertex(aV1, aLen / 2.);
6181     BRep_Builder().UpdateVertex(aV2, aLen / 2.);
6182   }
6183   //
6184   return bMicro;
6185 }
6186
6187 //=======================================================================
6188 //function : UpdateOrigins
6189 //purpose  : Updating origins
6190 //=======================================================================
6191 void UpdateOrigins(const TopTools_ListOfShape& theLA,
6192                    TopTools_DataMapOfShapeListOfShape& theOrigins,
6193                    BOPAlgo_Builder& theGF)
6194 {
6195   TopTools_ListIteratorOfListOfShape aItA(theLA);
6196   for (; aItA.More(); aItA.Next()) {
6197     const TopoDS_Shape& aS = aItA.Value();
6198     //
6199     const TopTools_ListOfShape& aLSIm = theGF.Modified(aS);
6200     if (aLSIm.IsEmpty()) {
6201       continue;
6202     }
6203     //
6204     TopTools_ListOfShape aLSEmpt;
6205     TopTools_ListOfShape *pLS = theOrigins.ChangeSeek(aS);
6206     if (!pLS) {
6207       pLS = &aLSEmpt;
6208       pLS->Append(aS);
6209     }
6210     //
6211     TopTools_ListIteratorOfListOfShape aIt(aLSIm);
6212     for (; aIt.More(); aIt.Next()) {
6213       const TopoDS_Shape& aSIm = aIt.Value();
6214       //
6215       TopTools_ListOfShape *pLSOr = theOrigins.ChangeSeek(aSIm);
6216       if (!pLSOr) {
6217         // just bind the origins
6218         theOrigins.Bind(aSIm, *pLS);
6219       }
6220       else {
6221         // merge two lists
6222         TopTools_ListIteratorOfListOfShape aIt1(*pLS);
6223         for (; aIt1.More(); aIt1.Next()) {
6224           const TopoDS_Shape& aS1 = aIt1.Value();
6225           AppendToList(*pLSOr, aS1);
6226         }
6227       }
6228     }
6229   }
6230 }
6231
6232 //=======================================================================
6233 //function : UpdateImages
6234 //purpose  : Updating images of the shapes
6235 //=======================================================================
6236 void UpdateImages(const TopTools_ListOfShape& theLA,
6237                   TopTools_DataMapOfShapeListOfShape& theImages,
6238                   BOPAlgo_Builder& theGF,
6239                   TopTools_MapOfShape& theModified)
6240 {
6241   TopTools_ListIteratorOfListOfShape aIt(theLA);
6242   for (; aIt.More(); aIt.Next()) {
6243     const TopoDS_Shape& aS = aIt.Value();
6244     //
6245     TopTools_ListOfShape* pLSIm = theImages.ChangeSeek(aS);
6246     if (!pLSIm) {
6247       const TopTools_ListOfShape& aLSIm = theGF.Modified(aS);
6248       if (aLSIm.Extent()) {
6249         theImages.Bind(aS, aLSIm);
6250         theModified.Add(aS);
6251       }
6252       continue;
6253     }
6254     //
6255     TopTools_MapOfShape aMFence;
6256     TopTools_ListOfShape aLSImNew;
6257     //
6258     Standard_Boolean bModified = Standard_False;
6259     //
6260     // check modifications of the images
6261     TopTools_ListIteratorOfListOfShape aIt1(*pLSIm);
6262     for (; aIt1.More(); aIt1.Next()) {
6263       const TopoDS_Shape& aSIm = aIt1.Value();
6264       const TopTools_ListOfShape& aLSIm1 = theGF.Modified(aSIm);
6265       if (aLSIm1.IsEmpty()) {
6266         if (aMFence.Add(aSIm)) {
6267           aLSImNew.Append(aSIm);
6268         }
6269       }
6270       else {
6271         TopTools_ListIteratorOfListOfShape aIt2(aLSIm1);
6272         for (; aIt2.More(); aIt2.Next()) {
6273           const TopoDS_Shape& aSImIm = aIt2.Value();
6274           if (aMFence.Add(aSImIm)) {
6275             aLSImNew.Append(aSImIm);
6276           }
6277         }
6278         bModified = Standard_True;
6279       }
6280     }
6281     //
6282     if (bModified) {
6283       *pLSIm = aLSImNew;
6284       theModified.Add(aS);
6285     }
6286   }
6287 }
6288
6289 //=======================================================================
6290 //function : UpdateIntersectedEdges
6291 //purpose  : Saving connection from trimmed edges to not trimmed ones
6292 //=======================================================================
6293 void UpdateIntersectedEdges(const TopTools_ListOfShape& theLA,
6294                             TopTools_DataMapOfShapeShape& theETrimEInf,
6295                             BOPAlgo_Builder& theGF)
6296 {
6297   TopTools_ListIteratorOfListOfShape aItA(theLA);
6298   for (; aItA.More(); aItA.Next()) {
6299     const TopoDS_Shape& aS = aItA.Value();
6300     //
6301     const TopoDS_Shape* pEInf = theETrimEInf.Seek(aS);
6302     if (!pEInf) {
6303       continue;
6304     }
6305     //
6306     const TopTools_ListOfShape& aLSIm = theGF.Modified(aS);
6307     if (aLSIm.IsEmpty()) {
6308       continue;
6309     }
6310     //
6311     TopTools_ListIteratorOfListOfShape aIt(aLSIm);
6312     for (; aIt.More(); aIt.Next()) {
6313       const TopoDS_Shape& aEIm = aIt.Value();
6314       if (!theETrimEInf.IsBound(aEIm)) {
6315         theETrimEInf.Bind(aEIm, *pEInf);
6316       }
6317     }
6318   }
6319 }
6320
6321 //=======================================================================
6322 //function : FindCommonParts
6323 //purpose  : Looking for the parts of type <theType> contained in both lists
6324 //=======================================================================
6325 void FindCommonParts(const TopTools_ListOfShape& theLS1,
6326                      const TopTools_ListOfShape& theLS2,
6327                      TopTools_ListOfShape& theLSC,
6328                      const TopAbs_ShapeEnum theType)
6329 {
6330   // map shapes in the first list
6331   TopTools_IndexedMapOfShape aMS1;
6332   TopTools_ListIteratorOfListOfShape aIt(theLS1);
6333   for (; aIt.More(); aIt.Next()) {
6334     const TopoDS_Shape& aS = aIt.Value();
6335     TopExp::MapShapes(aS, theType, aMS1);
6336   }
6337   //
6338   if (aMS1.IsEmpty()) {
6339     return;
6340   }
6341   //
6342   TopTools_MapOfShape aMFence;
6343   // check for such shapes in the other list
6344   aIt.Initialize(theLS2);
6345   for (; aIt.More(); aIt.Next()) {
6346     const TopoDS_Shape& aS = aIt.Value();
6347     //
6348     TopExp_Explorer aExp(aS, theType);
6349     for(; aExp.More(); aExp.Next()) {
6350       const TopoDS_Shape& aST = aExp.Current();
6351       //
6352       if (aMS1.Contains(aST) && aMFence.Add(aST)) {
6353         theLSC.Append(aST);
6354       }
6355     }
6356   }
6357 }
6358
6359 //=======================================================================
6360 //function : NbPoints
6361 //purpose  : Defines number of sample points to get average direction of the edge
6362 //=======================================================================
6363 Standard_Integer NbPoints(const TopoDS_Edge& theEdge)
6364 {
6365   Standard_Integer aNbP;
6366   BRepAdaptor_Curve aBAC(theEdge);
6367   switch (aBAC.GetType()) {
6368   case GeomAbs_Line:
6369     aNbP = 1;
6370     break;
6371   default:
6372     aNbP = 11;
6373   }
6374   //
6375   return aNbP;
6376 }
6377
6378 //=======================================================================
6379 //function : FindShape
6380 //purpose  : Looking for the same sub-shape in the shape
6381 //=======================================================================
6382 Standard_Boolean FindShape(const TopoDS_Shape& theSWhat,
6383                            const TopoDS_Shape& theSWhere,
6384                            TopoDS_Shape& theRes)
6385 {
6386   Standard_Boolean bFound = Standard_False;
6387   TopAbs_ShapeEnum aType = theSWhat.ShapeType();
6388   TopExp_Explorer aExp(theSWhere, aType);
6389   for (; aExp.More(); aExp.Next()) {
6390     const TopoDS_Shape& aS = aExp.Current();
6391     if (aS.IsSame(theSWhat)) {
6392       theRes = aS;
6393       bFound = Standard_True;
6394       break;
6395     }
6396   }
6397   return bFound;
6398 }
6399
6400
6401 //=======================================================================
6402 //function : AppendToList
6403 //purpose  : Add to a list only unique elements
6404 //=======================================================================
6405 void AppendToList(TopTools_ListOfShape& theList,
6406                   const TopoDS_Shape& theShape)
6407 {
6408   TopTools_ListIteratorOfListOfShape aIt(theList);
6409   for (; aIt.More(); aIt.Next()) {
6410     const TopoDS_Shape& aS = aIt.Value();
6411     if (aS.IsSame(theShape)) {
6412       return;
6413     }
6414   }
6415   theList.Append(theShape);
6416 }