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   }