6462ea6348332add60d1ff71c6dcf74922e78605
[occt.git] / 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 <BRepLib.hxx>
34 #include <BRepTools.hxx>
35
36 #include <BRepAdaptor_Curve.hxx>
37
38 #include <TopExp.hxx>
39 #include <TopExp_Explorer.hxx>
40
41 #include <TopTools_DataMapOfShapeInteger.hxx>
42
43 #include <BRepOffset_Tool.hxx>
44
45 #include <BRepClass3d_SolidClassifier.hxx>
46
47 #include <BOPDS_DS.hxx>
48
49 #include <BOPAlgo_PaveFiller.hxx>
50 #include <BOPAlgo_Builder.hxx>
51 #include <BOPAlgo_Section.hxx>
52 #include <BOPAlgo_MakerVolume.hxx>
53 #include <BOPAlgo_BuilderFace.hxx>
54
55 #include <TopTools_ListOfShape.hxx>
56 #include <TopTools_DataMapOfShapeShape.hxx>
57 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
58 #include <TopTools_MapOfOrientedShape.hxx>
59
60 #include <BOPTools_AlgoTools3D.hxx>
61 #include <BOPTools_AlgoTools.hxx>
62 #include <BOPTools_AlgoTools2D.hxx>
63
64 #include <IntTools_Context.hxx>
65 #include <IntTools_ShrunkRange.hxx>
66
67 #ifdef OFFSET_DEBUG
68 #include <BRepAlgoAPI_Check.hxx>
69 #endif
70
71 typedef NCollection_DataMap
72   <TopoDS_Shape, TopTools_MapOfShape, TopTools_ShapeMapHasher> BRepOffset_DataMapOfShapeMapOfShape;
73 typedef NCollection_DataMap
74   <TopoDS_Shape, TopTools_IndexedMapOfShape, TopTools_ShapeMapHasher> BRepOffset_DataMapOfShapeIndexedMapOfShape;
75
76 static
77   void IntersectTrimmedEdges(const TopTools_ListOfShape& theLF,
78                              const Handle(BRepAlgo_AsDes)& theAsDes,
79                              TopTools_DataMapOfShapeListOfShape& theOEImages,
80                              TopTools_DataMapOfShapeListOfShape& theOEOrigins,
81                              TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
82                              Handle(IntTools_Context)& theCtx,
83                              TopTools_MapOfShape& theNewEdges,
84                              TopTools_DataMapOfShapeShape& theETrimEInf);
85
86 static
87   Standard_Boolean GetEdges(const TopoDS_Face& theFace,
88                             const Handle(BRepAlgo_AsDes)& theAsDes,
89                             const TopTools_DataMapOfShapeListOfShape& theEImages,
90                             const TopTools_MapOfShape& theLastInvEdges,
91                             const TopTools_IndexedMapOfShape& theInvEdges,
92                             Handle(IntTools_Context)& theCtx,
93                             const TopTools_MapOfShape& theModifiedEdges,
94                             TopoDS_Shape& theEdges,
95                             TopTools_IndexedMapOfShape& theInv);
96
97 static
98   void BuildSplitsOfTrimmedFace(const TopoDS_Face& theFace,
99                                 const TopoDS_Shape& theEdges,
100                                 TopTools_ListOfShape& theLFImages);
101
102 static
103   void BuildSplitsOfFace(const TopoDS_Face& theFace,
104                          const TopoDS_Shape& theEdges,
105                          TopTools_DataMapOfShapeShape& theOrigins,
106                          TopTools_ListOfShape& theLFImages);
107
108 static
109   void BuildSplitsOfFaces(const TopTools_ListOfShape& theLF,
110                           const TopTools_MapOfShape& theModifiedEdges,
111                           const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
112                           const BRepOffset_Analyse* theAnalyse,
113                           Handle(BRepAlgo_AsDes)& theAsDes,
114                           TopTools_DataMapOfShapeShape& theFacesOrigins,
115                           TopTools_DataMapOfShapeListOfShape& theOEImages,
116                           TopTools_DataMapOfShapeListOfShape& theOEOrigins,
117                           TopTools_MapOfShape& theLastInvEdges,
118                           TopTools_IndexedMapOfShape& theEdgesToAvoid,
119                           TopTools_IndexedMapOfShape& theInvEdges,
120                           TopTools_IndexedMapOfShape& theValidEdges,
121                           TopTools_MapOfShape& theInvertedEdges,
122                           TopTools_DataMapOfShapeInteger& theAlreadyInvFaces,
123                           TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
124                           TopTools_DataMapOfShapeShape& theArtInvFaces,
125                           TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
126                           TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
127                           TopoDS_Shape& theSolids,
128                           TopTools_DataMapOfShapeListOfShape& theSSInterfs);
129
130 static 
131   void BuildSplitsOfInvFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild, 
132                              const TopTools_MapOfShape& theModifiedEdges,
133                              TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
134                              TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
135                              TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
136                              TopTools_DataMapOfShapeShape& theFacesOrigins,
137                              TopTools_DataMapOfShapeListOfShape& theOEImages,
138                              TopTools_DataMapOfShapeListOfShape& theOEOrigins,
139                              TopTools_MapOfShape& theLastInvEdges,
140                              TopTools_IndexedMapOfShape& theEdgesToAvoid,
141                              TopTools_MapOfShape& theVertsToAvoid,
142                              TopTools_DataMapOfShapeInteger& theAlreadyInvFaces,
143                              TopTools_IndexedMapOfShape& theValidEdges,
144                              TopTools_DataMapOfShapeShape& theETrimEInf,
145                              Handle(BRepAlgo_AsDes)& theAsDes);
146
147 static 
148   Standard_Boolean CheckIfArtificial(const TopoDS_Shape& theF,
149                                      const TopTools_ListOfShape& theLFImages,
150                                      const TopoDS_Shape& theCE,
151                                      const TopTools_IndexedMapOfShape& theMapEInv,
152                                      const TopTools_DataMapOfShapeListOfShape& theOEImages,
153                                      TopTools_MapOfShape& theMENInv,
154                                      Handle(BRepAlgo_AsDes)& theAsDes);
155
156 static
157   void FindInvalidEdges(const TopoDS_Face& theF,
158                         const TopTools_ListOfShape& theLFImages,
159                         const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
160                         const TopTools_DataMapOfShapeShape& theFacesOrigins,
161                         const BRepOffset_Analyse* theAnalyse,
162                         const TopTools_DataMapOfShapeListOfShape& theOEImages,
163                         const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
164                         TopTools_IndexedMapOfShape& theInvEdges,
165                         TopTools_IndexedMapOfShape& theValidEdges,
166                         BRepOffset_DataMapOfShapeMapOfShape& theDMFMVE,
167                         BRepOffset_DataMapOfShapeMapOfShape& theDMFMNE,
168                         BRepOffset_DataMapOfShapeIndexedMapOfShape& theDMFMIE,
169                         BRepOffset_DataMapOfShapeMapOfShape& theDMFMVIE,
170                         TopTools_DataMapOfShapeListOfShape& theDMEOrLEIm,
171                         TopTools_MapOfShape& theMEInverted,
172                         TopTools_MapOfShape& theEdgesInvalidByVertex,
173                         TopTools_MapOfShape& theEdgesValidByVertex);
174
175 static
176   void FindInvalidFaces(TopTools_ListOfShape& theLFImages,
177                         const TopTools_IndexedMapOfShape& theInvEdges,
178                         const TopTools_IndexedMapOfShape& theValidEdges,
179                         const BRepOffset_DataMapOfShapeMapOfShape& theDMFMVE,
180                         const BRepOffset_DataMapOfShapeIndexedMapOfShape& theDMFMIE,
181                         const TopTools_MapOfShape& theLENeutral,
182                         const TopTools_MapOfShape& theMEInverted,
183                         const TopTools_MapOfShape& theEdgesInvalidByVertex,
184                         const TopTools_MapOfShape& theEdgesValidByVertex,
185                         const TopTools_MapOfShape& theMFHoles,
186                         TopTools_IndexedMapOfShape& theMFInvInHole,
187                         TopTools_ListOfShape& theInvFaces,
188                         TopTools_ListOfShape& theInvertedFaces);
189
190 static
191   void FindFacesInsideHoleWires(const TopoDS_Face& theFOrigin,
192                                 const TopoDS_Face& theFOffset,
193                                 const TopTools_ListOfShape& theLFImages,
194                                 const TopTools_MapOfShape& theInvertedEdges,
195                                 const TopTools_DataMapOfShapeListOfShape& theDMEOrLEIm,
196                                 const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
197                                 TopTools_MapOfShape& theMFHoles,
198                                 TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
199                                 Handle(IntTools_Context)& theContext);
200
201 static
202   gp_Vec GetAverageTangent(const TopoDS_Shape& theS,
203                            const Standard_Integer theNbP);
204
205 static
206   Standard_Boolean CheckInverted(const TopoDS_Edge& theEIm,
207                                  const TopoDS_Face& theFOr,
208                                  const TopTools_DataMapOfShapeListOfShape& theOEImages,
209                                  const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
210                                  const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
211                                  const TopTools_IndexedDataMapOfShapeListOfShape& theDMVE,
212                                  const TopTools_IndexedMapOfShape& theMEdges,
213                                  TopTools_MapOfShape& theMEInverted);
214
215 static
216   Standard_Boolean CheckInvertedBlock(const TopoDS_Shape& theCB,
217                                       const TopTools_ListOfShape& theLCBF,
218                                       const TopTools_MapOfShape& theMEInverted,
219                                       const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
220                                       BRepOffset_DataMapOfShapeMapOfShape& theDMCBVInverted,
221                                       BRepOffset_DataMapOfShapeMapOfShape& theDMCBVAll);
222
223 static
224   void GetVerticesOnEdges(const TopoDS_Shape& theCB,
225                           const TopTools_MapOfShape& theEdges,
226                           TopTools_MapOfShape& theVerticesOnEdges,
227                           TopTools_MapOfShape& theAllVertices);
228
229 static
230   void RemoveInvalidSplitsByInvertedEdges(const TopTools_MapOfShape& theMEInverted,
231                                           const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
232                                           TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
233                                           TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
234                                           TopTools_IndexedMapOfShape& theMERemoved);
235
236 static
237   void RemoveInvalidSplitsFromValid(const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
238                                     const TopTools_DataMapOfShapeShape& theArtInvFaces,
239                                     const TopTools_MapOfShape& theMEInverted,
240                                     const BRepOffset_DataMapOfShapeMapOfShape& theDMFMVIE,
241                                     TopTools_IndexedDataMapOfShapeListOfShape& theFImages);
242
243 static
244   void RemoveInsideFaces(TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
245                          TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
246                          const TopTools_DataMapOfShapeShape& theArtInvFaces,
247                          const TopTools_IndexedMapOfShape& theInvEdges,
248                          const TopTools_MapOfShape& theInvertedEdges,
249                          const TopTools_ListOfShape& theInvertedFaces,
250                          const TopTools_IndexedMapOfShape& theMFToCheckInt,
251                          const TopTools_IndexedMapOfShape& theMFInvInHole,
252                          const TopoDS_Shape& theFHoles,
253                          TopTools_DataMapOfShapeListOfShape& theSSInterfs,
254                          TopTools_IndexedMapOfShape& theMERemoved,
255                          TopTools_IndexedMapOfShape& theMEInside,
256                          TopoDS_Shape& theSolids);
257
258 static
259   void ShapesConnections(const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
260                          const TopTools_IndexedMapOfShape& theInvEdges,
261                          const TopTools_DataMapOfShapeShape& theDMFOr,
262                          BOPAlgo_Builder& theBuilder,
263                          TopTools_DataMapOfShapeListOfShape& theSSInterfs);
264
265 static
266   void RemoveHangingParts(const BOPAlgo_MakerVolume& theMV,
267                           const TopTools_DataMapOfShapeShape& theDMFImF,
268                           const TopTools_IndexedMapOfShape& theMFInv,
269                           const TopTools_IndexedMapOfShape& theInvEdges,
270                           const TopTools_MapOfShape& theInvertedEdges,
271                           TopTools_MapOfShape& theMFToRem);
272
273 static
274   void RemoveValidSplits(const TopTools_MapOfShape& theSpRem,
275                          TopTools_IndexedDataMapOfShapeListOfShape& theImages,
276                          BOPAlgo_Builder& theGF,
277                          TopTools_IndexedMapOfShape& theMERemoved);
278
279 static
280   void RemoveInvalidSplits(const TopTools_MapOfShape& theSpRem,
281                            const TopTools_DataMapOfShapeShape& theArtInvFaces,
282                            const TopTools_IndexedMapOfShape& theInvEdges,
283                            TopTools_IndexedDataMapOfShapeListOfShape& theImages,
284                            BOPAlgo_Builder& theGF,
285                            TopTools_IndexedMapOfShape& theMERemoved);
286
287 static
288   void FilterEdgesImages(const TopoDS_Shape& theS,
289                          TopTools_DataMapOfShapeListOfShape& theOEImages,
290                          TopTools_DataMapOfShapeListOfShape& theOEOrigins);
291
292 static
293   void FilterInvalidFaces(TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
294                           const TopTools_IndexedDataMapOfShapeListOfShape& theDMEF,
295                           const TopTools_IndexedMapOfShape& theInvEdges,
296                           const TopTools_IndexedMapOfShape& theMERemoved,
297                           TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
298                           TopTools_DataMapOfShapeShape& theArtInvFaces);
299
300 static
301   void FilterInvalidEdges(const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
302                           const TopTools_DataMapOfShapeShape& theArtInvFaces,
303                           const BRepOffset_DataMapOfShapeIndexedMapOfShape& theDMFMIE,
304                           const TopTools_IndexedMapOfShape& theMERemoved,
305                           TopTools_IndexedMapOfShape& theInvEdges);
306
307 static 
308   void FindFacesToRebuild(const TopTools_IndexedDataMapOfShapeListOfShape&  theLFImages,
309                           const TopTools_IndexedMapOfShape& theInvEdges,
310                           const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
311                           const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
312                           TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
313                           TopTools_MapOfShape& theFSelfRebAvoid);
314
315 static
316   void RebuildFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
317                     const TopTools_MapOfShape& theFSelfRebAvoid,
318                     const TopoDS_Shape& theSolids,
319                     const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
320                     TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
321                     TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
322                     TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
323                     TopTools_DataMapOfShapeShape& theFacesOrigins,
324                     TopTools_DataMapOfShapeListOfShape& theOEImages,
325                     TopTools_DataMapOfShapeListOfShape& theOEOrigins,
326                     TopTools_MapOfShape& theLastInvEdges,
327                     TopTools_IndexedMapOfShape& theEdgesToAvoid,
328                     TopTools_IndexedMapOfShape& theInvEdges,
329                     TopTools_IndexedMapOfShape& theValidEdges,
330                     const TopTools_MapOfShape& theInvertedEdges,
331                     TopTools_DataMapOfShapeInteger& theAlreadyInvFaces,
332                     TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
333                     const TopTools_DataMapOfShapeShape& theArtInvFaces,
334                     TopTools_MapOfShape& theVertsToAvoid,
335                     TopTools_DataMapOfShapeShape& theETrimEInf,
336                     Handle(BRepAlgo_AsDes)& theAsDes);
337
338 static
339   void IntersectFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
340                       const TopTools_MapOfShape& theFSelfRebAvoid,
341                       const TopoDS_Shape& theSolids,
342                       const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
343                       TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
344                       TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
345                       TopTools_DataMapOfShapeListOfShape& theOEImages,
346                       TopTools_DataMapOfShapeListOfShape& theOEOrigins,
347                       TopTools_IndexedMapOfShape& theInvEdges,
348                       TopTools_IndexedMapOfShape& theValidEdges,
349                       const TopTools_MapOfShape& theInvertedEdges,
350                       TopTools_IndexedMapOfShape& theEdgesToAvoid,
351                       TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
352                       const TopTools_DataMapOfShapeShape& theArtInvFaces,
353                       TopTools_MapOfShape& theVertsToAvoid,
354                       TopTools_DataMapOfShapeShape& theETrimEInf,
355                       TopTools_MapOfShape& theModifiedEdges,
356                       Handle(BRepAlgo_AsDes)& theAsDes);
357
358 static
359   void PrepareFacesForIntersection(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
360                                    const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
361                                    const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
362                                    const TopTools_DataMapOfShapeShape& theArtInvFaces,
363                                    const Standard_Boolean bLookVertToAvoid,
364                                    TopTools_IndexedDataMapOfShapeListOfShape& theFLE,
365                                    TopTools_DataMapOfShapeListOfShape& theMDone,
366                                    TopTools_DataMapOfShapeListOfShape& theDMSF,
367                                    TopTools_DataMapOfShapeListOfShape& theMEInfETrim,
368                                    TopTools_DataMapOfShapeListOfShape& theDMVEFull,
369                                    TopTools_DataMapOfShapeShape& theETrimEInf,
370                                    TopTools_IndexedDataMapOfShapeListOfShape& theDMEFInv);
371
372 static
373   void FindVerticesToAvoid(const TopTools_IndexedDataMapOfShapeListOfShape& theDMEFInv,
374                            const TopTools_IndexedMapOfShape& theInvEdges,
375                            const TopTools_IndexedMapOfShape& theValidEdges,
376                            const TopTools_MapOfShape& theInvertedEdges,
377                            const TopTools_DataMapOfShapeListOfShape& theDMVEFull,
378                            const TopTools_DataMapOfShapeListOfShape& theOEImages,
379                            const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
380                            TopTools_MapOfShape& theMVRInv);
381
382 static
383   void FindFacesForIntersection(const TopoDS_Shape& theFInv,
384                                 const TopTools_IndexedMapOfShape& theME,
385                                 const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
386                                 const TopTools_DataMapOfShapeListOfShape& theDMSF,
387                                 const TopTools_MapOfShape& theMVInvAll,
388                                 const TopTools_DataMapOfShapeShape& theArtInvFaces,
389                                 const Standard_Boolean theArtCase,
390                                 const TopTools_DataMapOfShapeListOfShape& theSSInterfs,
391                                 TopTools_IndexedMapOfShape& theMFAvoid,
392                                 TopTools_IndexedMapOfShape& theMFInt,
393                                 TopTools_IndexedMapOfShape& theMFIntExt,
394                                 TopTools_ListOfShape& theLFImInt);
395
396 static
397   void ProcessCommonEdges(const TopTools_ListOfShape& theLEC,
398                           const TopTools_IndexedMapOfShape& theInvEdges,
399                           const TopTools_IndexedMapOfShape& theValidEdges,
400                           const TopTools_IndexedMapOfShape& theME,
401                           const TopTools_DataMapOfShapeShape& theETrimEInf,
402                           const TopTools_DataMapOfShapeListOfShape& theMEInfETrim,
403                           const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
404                           const TopTools_MapOfShape& theAllInvs,
405                           const Standard_Boolean theForceUse,
406                           TopTools_IndexedMapOfShape& theMECV,
407                           TopTools_MapOfShape& theMECheckExt,
408                           TopTools_DataMapOfShapeListOfShape& theDMEETrim,
409                           TopTools_ListOfShape& theLFEi,
410                           TopTools_ListOfShape& theLFEj,
411                           TopTools_IndexedMapOfShape& theMEToInt);
412
413 static
414   void UpdateIntersectedFaces(const TopoDS_Shape& theFInv,
415                               const TopoDS_Shape& theFi,
416                               const TopoDS_Shape& theFj,
417                               const TopTools_ListOfShape& theLFInv,
418                               const TopTools_ListOfShape& theLFImi,
419                               const TopTools_ListOfShape& theLFImj,
420                               const TopTools_ListOfShape& theLFEi,
421                               const TopTools_ListOfShape& theLFEj,
422                               TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
423                               TopTools_IndexedMapOfShape& theMEToInt);
424
425 static
426   void IntersectFaces(const TopoDS_Shape& theFInv,
427                       const TopoDS_Shape& theFi,
428                       const TopoDS_Shape& theFj,
429                       const TopTools_ListOfShape& theLFInv,
430                       const TopTools_ListOfShape& theLFImi,
431                       const TopTools_ListOfShape& theLFImj,
432                       TopTools_ListOfShape& theLFEi,
433                       TopTools_ListOfShape& theLFEj,
434                       TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
435                       TopTools_IndexedMapOfShape& theMECV,
436                       TopTools_IndexedMapOfShape& theMEToInt);
437
438 static 
439   void FindOrigins(const TopTools_ListOfShape& theLFIm1,
440                    const TopTools_ListOfShape& theLFIm2,
441                    const TopTools_IndexedMapOfShape& theME,
442                    const TopTools_DataMapOfShapeListOfShape& theOrigins,
443                    TopTools_ListOfShape& theLEOr);
444
445 static
446   void IntersectAndTrimEdges(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild,
447                              const TopTools_IndexedMapOfShape& theMFInt,
448                              const TopTools_IndexedMapOfShape& theMEInt,
449                              const TopTools_DataMapOfShapeListOfShape& theDMEETrim,
450                              const TopTools_IndexedMapOfShape& theMSInv,
451                              const TopTools_IndexedMapOfShape& theMVE,
452                              const TopTools_MapOfShape& theVertsToAvoid,
453                              const TopTools_MapOfShape& theNewVertsToAvoid,
454                              const TopTools_MapOfShape& theMECheckExt,
455                              TopTools_MapOfShape& theMVBounds,
456                              TopTools_DataMapOfShapeListOfShape& theEImages);
457
458 static
459   void GetInvalidEdges(const TopTools_MapOfShape& theVertsToAvoid,
460                        const TopTools_MapOfShape& theMVBounds,
461                        BOPAlgo_Builder& theGF,
462                        TopTools_MapOfShape& theMEInv);
463
464 static
465   void UpdateValidEdges(const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
466                         const TopTools_IndexedDataMapOfShapeListOfShape& theFLE,
467                         const TopTools_IndexedDataMapOfShapeListOfShape& theOENEdges,
468                         const TopTools_MapOfShape& theMVBounds,
469                         const TopoDS_Shape& theSolids,
470                         const TopTools_IndexedMapOfShape& theInvEdges,
471                         const TopTools_MapOfShape& theInvertedEdges,
472                         const TopTools_MapOfShape& theMEInvOnArt,
473                         TopTools_MapOfShape& theMECheckExt,
474                         TopTools_IndexedMapOfShape& theEdgesToAvoid,
475                         TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
476                         TopTools_DataMapOfShapeListOfShape& theOEImages,
477                         TopTools_DataMapOfShapeListOfShape& theOEOrigins,
478                         TopTools_MapOfShape& theVertsToAvoid,
479                         TopTools_DataMapOfShapeShape& theETrimEInf,
480                         TopTools_DataMapOfShapeListOfShape& theEImages,
481                         TopTools_DataMapOfShapeListOfShape& theEETrim,
482                         TopTools_MapOfShape& theModifiedEdges,
483                         Handle(BRepAlgo_AsDes)& theAsDes);
484
485 static
486   void TrimNewIntersectionEdges(const TopTools_ListOfShape& theLE,
487                                 const TopTools_DataMapOfShapeListOfShape& theEETrim,
488                                 const TopTools_MapOfShape& theMVBounds,
489                                 TopTools_MapOfShape& theMECheckExt,
490                                 TopTools_DataMapOfShapeListOfShape& theEImages,
491                                 TopTools_MapOfShape& theMEB,
492                                 TopTools_MapOfShape& theMVOld,
493                                 TopTools_MapOfShape& theMENew,
494                                 TopTools_DataMapOfShapeListOfShape& theDMEOr,
495                                 TopTools_DataMapOfShapeListOfShape& theMELF);
496
497 static
498   void IntersectEdges(const TopTools_ListOfShape& theLA,
499                       const TopTools_ListOfShape& theLE,
500                       const TopTools_MapOfShape& theMVBounds,
501                       const TopTools_MapOfShape& theVertsToAvoid,
502                       TopTools_MapOfShape& theMENew,
503                       TopTools_MapOfShape& theMECheckExt,
504                       TopTools_DataMapOfShapeListOfShape& theEImages,
505                       TopTools_MapOfShape& theModifiedEdges,
506                       TopTools_DataMapOfShapeListOfShape& theDMEOr,
507                       TopTools_DataMapOfShapeListOfShape& theMELF,
508                       TopoDS_Shape& theSplits);
509
510 static
511   void GetBounds(const TopTools_ListOfShape& theLFaces,
512                  const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
513                  const TopTools_MapOfShape& theMEB,
514                  TopoDS_Shape& theBounds);
515
516 static
517   void GetBoundsToUpdate(const TopTools_ListOfShape& theLF,
518                          const TopTools_DataMapOfShapeListOfShape& theOEImages,
519                          const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
520                          const TopTools_MapOfShape& theMEB,
521                          TopTools_ListOfShape& theLABounds,
522                          TopTools_ListOfShape& theLAValid,
523                          TopoDS_Shape& theBounds,
524                          Handle(BRepAlgo_AsDes)& theAsDes);
525
526 static
527   void GetInvalidEdgesByBounds(const TopoDS_Shape& theSplits,
528                                const TopoDS_Shape& theBounds,
529                                const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
530                                const TopoDS_Shape& theSolids,
531                                const TopTools_IndexedMapOfShape& theInvEdges,
532                                const TopTools_MapOfShape& theMVOld,
533                                const TopTools_MapOfShape& theMENew,
534                                const TopTools_DataMapOfShapeListOfShape& theDMEOr,
535                                const TopTools_DataMapOfShapeListOfShape& theMELF,
536                                const TopTools_DataMapOfShapeListOfShape& theEImages,
537                                const TopTools_MapOfShape& theMECheckExt,
538                                const TopTools_MapOfShape& theMEInvOnArt,
539                                Handle(IntTools_Context)& theCtx,
540                                TopTools_MapOfShape& theVertsToAvoid,
541                                TopTools_MapOfShape& theMEInv);
542
543 static
544   void FilterSplits(const TopTools_ListOfShape& theLE,
545                     const TopTools_MapOfShape& theMEFilter,
546                     const Standard_Boolean theIsInv,
547                     TopTools_DataMapOfShapeListOfShape& theEImages,
548                     TopoDS_Shape& theSplits);
549
550 static
551   void UpdateNewIntersectionEdges(const TopTools_ListOfShape& theLE,
552                                   const TopTools_DataMapOfShapeListOfShape& theMELF,
553                                   const TopTools_DataMapOfShapeListOfShape& theEImages,
554                                   const TopTools_IndexedMapOfShape& theInvEdges,
555                                   const TopTools_MapOfShape& theInvertedEdges,
556                                   TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
557                                   TopTools_DataMapOfShapeListOfShape& theOEImages,
558                                   TopTools_DataMapOfShapeListOfShape& theOEOrigins,
559                                   TopTools_DataMapOfShapeShape& theETrimEInf,
560                                   TopTools_DataMapOfShapeListOfShape& theEETrim,
561                                   TopTools_MapOfShape& theModifiedEdges,
562                                   Handle(BRepAlgo_AsDes)& theAsDes);
563
564 static
565   void FillGaps(TopTools_IndexedDataMapOfShapeListOfShape& theFImages);
566
567 static
568   void FillHistory(const TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
569                    const TopTools_DataMapOfShapeListOfShape& theEImages,
570                    BRepAlgo_Image& theImage);
571
572 static
573   void UpdateOrigins(const TopTools_ListOfShape& theLA,
574                      TopTools_DataMapOfShapeListOfShape& theOrigins,
575                      BOPAlgo_Builder& theGF);
576
577 static
578   void UpdateImages(const TopTools_ListOfShape& theLA,
579                     TopTools_DataMapOfShapeListOfShape& theImages,
580                     BOPAlgo_Builder& theGF,
581                     TopTools_MapOfShape& theModified);
582
583 static
584   void UpdateIntersectedEdges(const TopTools_ListOfShape& theLA,
585                               TopTools_DataMapOfShapeShape& theETrimEInf,
586                               BOPAlgo_Builder& theGF);
587
588 static
589   Standard_Boolean ProcessMicroEdge(const TopoDS_Edge& theEdge,
590                                     const Handle(IntTools_Context)& theCtx);
591
592 static
593   void FindCommonParts(const TopTools_ListOfShape& theLS1,
594                        const TopTools_ListOfShape& theLS2,
595                        TopTools_ListOfShape& theLSC,
596                        const TopAbs_ShapeEnum theType = TopAbs_EDGE);
597
598 static
599   Standard_Integer NbPoints(const TopoDS_Edge& theE);
600
601 static
602   Standard_Boolean FindShape(const TopoDS_Shape& theSWhat,
603                              const TopoDS_Shape& theSWhere,
604                              const BRepOffset_Analyse* theAnalyse,
605                              TopoDS_Shape& theRes);
606
607 static
608   void AppendToList(TopTools_ListOfShape& theL,
609                     const TopoDS_Shape& theS);
610
611 template <class ContainerType, class FenceMapType>
612 static Standard_Boolean TakeModified(const TopoDS_Shape& theS,
613                                      const TopTools_DataMapOfShapeListOfShape& theImages,
614                                      ContainerType& theMapOut,
615                                      FenceMapType* theMFence);
616
617 template <class ContainerType>
618 static Standard_Boolean TakeModified(const TopoDS_Shape& theS,
619                                      const TopTools_DataMapOfShapeListOfShape& theImages,
620                                      ContainerType& theMapOut)
621 {
622   TopTools_MapOfShape* aDummy = NULL;
623   return TakeModified (theS, theImages, theMapOut, aDummy);
624 }
625
626 //=======================================================================
627 //function : BuildSplitsOfTrimmedFaces
628 //purpose  : Building splits of already trimmed faces
629 //=======================================================================
630 void BRepOffset_MakeOffset::BuildSplitsOfTrimmedFaces(const TopTools_ListOfShape& theLF,
631                                                       Handle(BRepAlgo_AsDes)& theAsDes,
632                                                       BRepAlgo_Image& theImage)
633 {
634   TopTools_DataMapOfShapeListOfShape anEImages, anEOrigins;
635   TopTools_IndexedDataMapOfShapeListOfShape aDMFFIm;
636   TopTools_IndexedMapOfShape anEmptyIM;
637   TopTools_DataMapOfShapeListOfShape anEmptyDMSLS;
638   TopTools_DataMapOfShapeShape anEmptyDMSS;
639   TopTools_MapOfShape aNewEdges, anEmptyM;
640   //
641   // firstly it is necessary to fuse all the edges
642   Handle(IntTools_Context) aCtx = new IntTools_Context();
643   //
644   IntersectTrimmedEdges(theLF, theAsDes, anEImages, anEOrigins, anEmptyDMSLS, aCtx, aNewEdges, anEmptyDMSS);
645   //
646   TopTools_ListIteratorOfListOfShape aItLF(theLF);
647   for (; aItLF.More(); aItLF.Next()) {
648     const TopoDS_Face& aF = *(TopoDS_Face*)&aItLF.Value();
649     //
650     TopoDS_Shape aCE;
651     TopTools_ListOfShape aLFImages;
652     //
653     Standard_Boolean bFound = GetEdges(aF, theAsDes, anEImages, anEmptyM,
654                                        anEmptyIM, aCtx, aNewEdges, aCE, anEmptyIM);
655     // split the face by the edges
656     if (!bFound) {
657       if (!theImage.HasImage(aF)) {
658         aLFImages.Append(aF);
659         aDMFFIm.Add(aF, aLFImages);
660       }
661       continue;
662     }
663     //
664     BuildSplitsOfTrimmedFace(aF, aCE, aLFImages);
665     aDMFFIm.Add(aF, aLFImages);
666   }
667   // Fill history for faces and edges
668   FillHistory(aDMFFIm, anEImages, theImage);
669 }
670
671 //=======================================================================
672 //function : BuildSplitsOfExtendedFaces
673 //purpose  : Building splits of not-trimmed offset faces.
674 //           For the cases in which invalidity will be found,
675 //           these invalidities will be rebuilt.
676 //=======================================================================
677 void BRepOffset_MakeOffset::BuildSplitsOfExtendedFaces(const TopTools_ListOfShape& theLF,
678                                                        const BRepOffset_Analyse& theAnalyse,
679                                                        Handle(BRepAlgo_AsDes)& theAsDes,
680                                                        TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
681                                                        TopTools_DataMapOfShapeShape& theFacesOrigins,
682                                                        TopTools_DataMapOfShapeShape& theETrimEInf,
683                                                        BRepAlgo_Image& theImage)
684 {
685   Handle(IntTools_Context) aCtx = new IntTools_Context();
686   // images and origins for offset edges
687   TopTools_DataMapOfShapeListOfShape anOEImages, anOEOrigins;
688   TopTools_MapOfShape aNewEdges;
689   // fusing all trimmed offset edges to avoid self-intersections in the splits
690   IntersectTrimmedEdges(theLF, theAsDes, anOEImages, anOEOrigins,
691                         theEdgesOrigins, aCtx, aNewEdges, theETrimEInf);
692   //
693   // valid/invalid edges
694   TopTools_IndexedMapOfShape anInvEdges, aValidEdges, anEdgesToAvoid;
695   // inverted edges
696   TopTools_MapOfShape anInvertedEdges;
697   // splits of faces
698   TopTools_IndexedDataMapOfShapeListOfShape aFImages;
699   // found invalid faces
700   TopTools_IndexedDataMapOfShapeListOfShape anInvFaces;
701   // artificially invalid faces - it will be empty here,
702   // but may be filled on the following rebuilding steps
703   TopTools_DataMapOfShapeShape anArtInvFaces;
704   // shapes connections for using in rebuilding
705   TopTools_DataMapOfShapeListOfShape aSSInterfs;
706   // edges to avoid on second steps
707   TopTools_MapOfShape aLastInvEdges;
708   // keep information of already invalid faces to avoid
709   // infinite rebuilding of the same invalid face
710   TopTools_DataMapOfShapeInteger anAlreadyInvFaces;
711   // images of the hole faces of the original faces
712   TopTools_DataMapOfShapeListOfShape aDMFNewHoles;
713   // solid build from the new splits
714   TopoDS_Shape aSolids;
715   // now we can split the faces
716   BuildSplitsOfFaces(theLF, aNewEdges, theEdgesOrigins, &theAnalyse, theAsDes, theFacesOrigins,
717                      anOEImages, anOEOrigins, aLastInvEdges, anEdgesToAvoid, anInvEdges, aValidEdges,
718                      anInvertedEdges, anAlreadyInvFaces, anInvFaces, anArtInvFaces, aFImages,
719                      aDMFNewHoles, aSolids, aSSInterfs);
720   //
721   // Find faces to rebuild
722   if (anInvFaces.Extent()) {
723     TopTools_IndexedDataMapOfShapeListOfShape aFToRebuild;
724     TopTools_MapOfShape aFSelfRebAvoid;
725     FindFacesToRebuild(aFImages, anInvEdges, anInvFaces, aSSInterfs, aFToRebuild, aFSelfRebAvoid);
726     //
727     if (aFToRebuild.Extent()) {
728       // vertices to avoid
729       TopTools_MapOfShape aVAEmpty;
730       RebuildFaces(aFToRebuild, aFSelfRebAvoid, aSolids, aSSInterfs, aFImages, aDMFNewHoles,
731                    theEdgesOrigins, theFacesOrigins, anOEImages, anOEOrigins, aLastInvEdges,
732                    anEdgesToAvoid, anInvEdges, aValidEdges, anInvertedEdges, anAlreadyInvFaces,
733                    anInvFaces, anArtInvFaces, aVAEmpty, theETrimEInf, theAsDes);
734     }
735   }
736
737   // Fill possible gaps in the splits of offset faces to increase possibility of
738   // creating closed volume from these splits
739   FillGaps(aFImages);
740
741   // Fill history for faces and edges
742   FillHistory(aFImages, anOEImages, theImage);
743 }
744
745 //=======================================================================
746 //function : BuildSplitsOfInvFaces
747 //purpose  : Rebuilding splits of faces with new intersection edges
748 //=======================================================================
749 void BuildSplitsOfInvFaces(const TopTools_IndexedDataMapOfShapeListOfShape& theFToRebuild, 
750                            const TopTools_MapOfShape& theModifiedEdges,
751                            TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
752                            TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
753                            TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
754                            TopTools_DataMapOfShapeShape& theFacesOrigins,
755                            TopTools_DataMapOfShapeListOfShape& theOEImages,
756                            TopTools_DataMapOfShapeListOfShape& theOEOrigins,
757                            TopTools_MapOfShape& theLastInvEdges,
758                            TopTools_IndexedMapOfShape& theEdgesToAvoid,
759                            TopTools_MapOfShape& theVertsToAvoid,
760                            TopTools_DataMapOfShapeInteger& theAlreadyInvFaces,
761                            TopTools_IndexedMapOfShape& theValidEdges,
762                            TopTools_DataMapOfShapeShape& theETrimEInf, 
763                            Handle(BRepAlgo_AsDes)& theAsDes)
764 {
765   Standard_Integer aNb = theFToRebuild.Extent();
766   if (!aNb) {
767     return;
768   }
769   //
770   TopTools_ListOfShape aLF;
771   aNb = theFImages.Extent();
772   for (Standard_Integer i = 1; i <= aNb; ++i) {
773     const TopoDS_Shape& aF = theFImages.FindKey(i);
774     aLF.Append(aF);
775   }
776   //
777   // invalid faces
778   TopTools_IndexedDataMapOfShapeListOfShape anInvFaces;
779   // artificially invalid faces
780   TopTools_DataMapOfShapeShape anArtInvFaces;
781   // invalid edges
782   TopTools_IndexedMapOfShape anInvEdges;
783   // inverted edges
784   TopTools_MapOfShape anInvertedEdges;
785   // shapes connection for using in rebuilding process
786   TopTools_DataMapOfShapeListOfShape aSSInterfs;
787   //
788   TopoDS_Shape aSolids;
789   //
790   BuildSplitsOfFaces(aLF, theModifiedEdges, theEdgesOrigins, NULL, theAsDes, theFacesOrigins, 
791                      theOEImages, theOEOrigins, theLastInvEdges, theEdgesToAvoid, anInvEdges, theValidEdges, 
792                      anInvertedEdges, theAlreadyInvFaces, anInvFaces, anArtInvFaces, theFImages,
793                      theDMFNewHoles, aSolids, aSSInterfs);
794   //
795   if (anInvFaces.Extent()) {
796     TopTools_IndexedDataMapOfShapeListOfShape aFToRebuild;
797     TopTools_MapOfShape aFSelfRebAvoid;
798     FindFacesToRebuild(theFImages, anInvEdges, anInvFaces, aSSInterfs, aFToRebuild, aFSelfRebAvoid);
799     //
800     if (aFToRebuild.Extent()) {
801       RebuildFaces(aFToRebuild, aFSelfRebAvoid, aSolids, aSSInterfs, theFImages, theDMFNewHoles,
802                    theEdgesOrigins, theFacesOrigins, theOEImages, theOEOrigins, theLastInvEdges,
803                    theEdgesToAvoid, anInvEdges, theValidEdges, anInvertedEdges, theAlreadyInvFaces,
804                    anInvFaces, anArtInvFaces, theVertsToAvoid, theETrimEInf, theAsDes);
805     }
806   }
807 }
808
809 //=======================================================================
810 //function : BuildSplitsOfFaces
811 //purpose  : Building the splits of offset faces and
812 //           looking for the invalid splits
813 //=======================================================================
814 void BuildSplitsOfFaces(const TopTools_ListOfShape& theLF,
815                         const TopTools_MapOfShape& theModifiedEdges,
816                         const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
817                         const BRepOffset_Analyse* theAnalyse,
818                         Handle(BRepAlgo_AsDes)& theAsDes,
819                         TopTools_DataMapOfShapeShape& theFacesOrigins,
820                         TopTools_DataMapOfShapeListOfShape& theOEImages,
821                         TopTools_DataMapOfShapeListOfShape& theOEOrigins,
822                         TopTools_MapOfShape& theLastInvEdges,
823                         TopTools_IndexedMapOfShape& theEdgesToAvoid,
824                         TopTools_IndexedMapOfShape& theInvEdges,
825                         TopTools_IndexedMapOfShape& theValidEdges,
826                         TopTools_MapOfShape& theInvertedEdges,
827                         TopTools_DataMapOfShapeInteger& theAlreadyInvFaces,
828                         TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
829                         TopTools_DataMapOfShapeShape& theArtInvFaces,
830                         TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
831                         TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
832                         TopoDS_Shape& theSolids,
833                         TopTools_DataMapOfShapeListOfShape& theSSInterfs)
834 {
835   if (theLF.IsEmpty()) {
836     return;
837   }
838   //
839   BRep_Builder aBB;
840   Standard_Integer i, aNb;
841   //
842   // processed faces
843   TopTools_ListOfShape aLFDone;
844   // extended face - map of neutral edges, i.e. in one split - valid and in other - invalid
845   BRepOffset_DataMapOfShapeMapOfShape aDMFMNE;
846   // map of valid edges for each face
847   BRepOffset_DataMapOfShapeMapOfShape aDMFMVE;
848   // map of invalid edges for each face
849   BRepOffset_DataMapOfShapeIndexedMapOfShape aDMFMIE;
850   // map of valid inverted edges for the face
851   BRepOffset_DataMapOfShapeMapOfShape aDMFMVIE;
852   // map of splits to check for internals
853   TopTools_IndexedMapOfShape aMFToCheckInt;
854   // map of edges created from vertex and marked as invalid
855   TopTools_MapOfShape aMEdgeInvalidByVertex;
856   // map of edges created from vertex and marked as valid
857   TopTools_MapOfShape aMEdgeValidByVertex;
858   // connection map from old edges to new ones
859   TopTools_DataMapOfShapeListOfShape aDMEOrLEIm;
860   //
861   Handle(IntTools_Context) aCtx = new IntTools_Context;
862   // build splits of faces
863   TopTools_ListIteratorOfListOfShape aItLF(theLF);
864   for (; aItLF.More(); aItLF.Next()) {
865     const TopoDS_Face& aF = *(TopoDS_Face*)&aItLF.Value();
866     //
867     TopTools_ListOfShape* pLFIm = theFImages.ChangeSeek(aF);
868     if (pLFIm && pLFIm->IsEmpty()) {
869       continue;
870     }
871     // get edges by which the face should be split
872     TopoDS_Shape aCE;
873     TopTools_IndexedMapOfShape aMapEInv;
874     Standard_Boolean bFound =
875       GetEdges(aF, theAsDes, theOEImages, theLastInvEdges,
876                theEdgesToAvoid, aCtx, theModifiedEdges, aCE, aMapEInv);
877     if (!bFound) {
878       continue;
879     }
880     //
881 #ifdef OFFSET_DEBUG
882     // check the found edges on self-intersection
883     BRepAlgoAPI_Check aChecker(aCE);
884     if (!aChecker.IsValid())
885     {
886       std::cout << "Offset_i_c Error: set of edges to build faces is self-intersecting\n";
887     }
888 #endif
889     // build splits
890     TopTools_ListOfShape aLFImages;
891     BuildSplitsOfFace(aF, aCE, theFacesOrigins, aLFImages);
892     //
893     if (aMapEInv.Extent()) {
894       // check if all possible faces are built
895       TopTools_MapOfShape aMENInv;
896       Standard_Boolean bArtificialCase = aLFImages.IsEmpty() ||
897         CheckIfArtificial(aF, aLFImages, aCE, aMapEInv, theOEImages, aMENInv, theAsDes);
898       //
899       // try to build splits using invalid edges
900       TopoDS_Compound aCE1;
901       aBB.MakeCompound(aCE1);
902       aBB.Add(aCE1, aCE);
903       for (i = 1; i <= aMapEInv.Extent(); ++i) {
904         aBB.Add(aCE1, aMapEInv(i));
905       }
906       //
907       TopTools_ListOfShape aLFImages1;
908       BuildSplitsOfFace(aF, aCE1, theFacesOrigins, aLFImages1);
909       //
910       // check if the rebuilding has added some new faces to the splits
911       for (TopTools_ListIteratorOfListOfShape aItLFIm(aLFImages1); aItLFIm.More();)
912       {
913         Standard_Boolean bAllInv = Standard_True;
914         const TopoDS_Shape& aFIm = aItLFIm.Value();
915         TopExp_Explorer aExpE(aFIm, TopAbs_EDGE);
916         for (; aExpE.More(); aExpE.Next()) {
917           const TopoDS_Shape& aE = aExpE.Current();
918           if (!aMapEInv.Contains(aE)) {
919             bAllInv = Standard_False;
920             if (!aMENInv.Contains(aE)) {
921               break;
922             }
923           }
924         }
925         //
926         if (!aExpE.More()) {
927           if (bAllInv) {
928             aMFToCheckInt.Add(aFIm);
929           }
930           aLFImages1.Remove(aItLFIm);
931         }
932         else {
933           aItLFIm.Next();
934         }
935       }
936       //
937       if (bArtificialCase) {
938         if (aLFImages.Extent() == aLFImages1.Extent()) {
939           bArtificialCase = Standard_False;
940         }
941         else {
942           aLFImages = aLFImages1;
943         }
944       }
945       //
946       if (bArtificialCase) {
947         TopTools_IndexedMapOfShape aMEInv;
948         // make the face invalid
949         theArtInvFaces.Bind(aF, aCE);
950         //
951         *pLFIm = aLFImages;
952         TopTools_ListIteratorOfListOfShape aItLFIm(aLFImages);
953         for (; aItLFIm.More(); aItLFIm.Next()) {
954           const TopoDS_Shape& aFIm = aItLFIm.Value();
955           TopExp_Explorer aExpE(aFIm, TopAbs_EDGE);
956           for (; aExpE.More(); aExpE.Next()) {
957             const TopoDS_Shape& aE = aExpE.Current();
958             if (aMapEInv.Contains(aE)) {
959               theInvEdges.Add(aE);
960               aMEInv.Add (aE);
961             }
962             else {
963               theValidEdges.Add(aE);
964             }
965           }
966         }
967         //
968         aDMFMIE.Bind(aF, aMEInv);
969         aLFDone.Append(aF);
970         //
971         continue;
972       }
973     }
974     //
975     // find invalid edges
976     FindInvalidEdges(aF, aLFImages, theEdgesOrigins, theFacesOrigins, theAnalyse, theOEImages,
977                      theOEOrigins, theInvEdges, theValidEdges, aDMFMVE, aDMFMNE, aDMFMIE,
978                      aDMFMVIE, aDMEOrLEIm, theInvertedEdges, aMEdgeInvalidByVertex, aMEdgeValidByVertex);
979     //
980     // save the new splits
981     if (!pLFIm) {
982       pLFIm = &theFImages(theFImages.Add(aF, TopTools_ListOfShape()));
983     }
984     else {
985       pLFIm->Clear();
986     }
987     pLFIm->Append(aLFImages);
988     //
989     aLFDone.Append(aF);
990   }
991   //
992   if (theInvEdges.IsEmpty() && theArtInvFaces.IsEmpty() && aDMFMIE.IsEmpty()) {
993     return;
994   }
995   //
996 #ifdef OFFSET_DEBUG
997   // show invalid edges
998   TopoDS_Compound aCEInv1;
999   BRep_Builder().MakeCompound(aCEInv1);
1000   Standard_Integer aNbEInv = theInvEdges.Extent();
1001   for (i = 1; i <= aNbEInv; ++i) {
1002     const TopoDS_Shape& aE = theInvEdges(i);
1003     BRep_Builder().Add(aCEInv1, aE);
1004   }
1005   // show valid edges
1006   TopoDS_Compound aCEVal1;
1007   BRep_Builder().MakeCompound(aCEVal1);
1008   aNbEInv = theValidEdges.Extent();
1009   for (i = 1; i <= aNbEInv; ++i) {
1010     const TopoDS_Shape& aE = theValidEdges(i);
1011     BRep_Builder().Add(aCEVal1, aE);
1012   }
1013   // show inverted edges
1014   TopoDS_Compound aCEInverted;
1015   BRep_Builder().MakeCompound(aCEInverted);
1016   TopTools_MapIteratorOfMapOfShape aItM(theInvertedEdges);
1017   for (; aItM.More(); aItM.Next()) {
1018     BRep_Builder().Add(aCEInverted, aItM.Value());
1019   }
1020 #endif
1021
1022 #ifdef OFFSET_DEBUG
1023   // Show all obtained splits of faces
1024   TopoDS_Compound aCFIm1;
1025   BRep_Builder().MakeCompound(aCFIm1);
1026 #endif
1027
1028   // Build Edge-Face connectivity map to find faces which removal
1029   // may potentially lead to creation of the holes in the faces
1030   // preventing from obtaining closed volume in the result
1031   TopTools_IndexedDataMapOfShapeListOfShape anEFMap;
1032   const Standard_Integer aNbF = theFImages.Extent();
1033   for (i = 1; i <= aNbF; ++i)
1034   {
1035     TopTools_ListIteratorOfListOfShape itLFIm(theFImages(i));
1036     for (; itLFIm.More(); itLFIm.Next())
1037     {
1038       TopExp::MapShapesAndAncestors(itLFIm.Value(), TopAbs_EDGE, TopAbs_FACE, anEFMap);
1039 #ifdef OFFSET_DEBUG
1040       BRep_Builder().Add(aCFIm1, itLFIm.Value());
1041 #endif
1042     }
1043   }
1044
1045   TopTools_MapOfShape anEmptyMap;
1046   // invalid faces inside the holes
1047   TopTools_IndexedMapOfShape aMFInvInHole;
1048   // all hole faces
1049   TopoDS_Compound aFHoles;
1050   aBB.MakeCompound(aFHoles);
1051   // Find the faces containing only the inverted edges and the invalid ones
1052   TopTools_ListOfShape anInvertedFaces;
1053   // find invalid faces
1054   // considering faces containing only invalid edges as invalid
1055   aItLF.Initialize(aLFDone);
1056   for (; aItLF.More(); aItLF.Next()) {
1057     const TopoDS_Face& aF = TopoDS::Face(aItLF.Value());
1058     TopTools_ListOfShape& aLFImages = theFImages.ChangeFromKey(aF);
1059     //
1060     TopTools_ListOfShape aLFInv;
1061     Standard_Boolean bArtificialCase = theArtInvFaces.IsBound(aF);
1062     if (bArtificialCase) {
1063       aLFInv = aLFImages;
1064     }
1065     else
1066     {
1067       // neutral edges
1068       const TopTools_MapOfShape* pMNE = aDMFMNE.ChangeSeek(aF);
1069       if (!pMNE) {
1070         pMNE = &anEmptyMap;
1071       }
1072       // find faces inside holes wires
1073       TopTools_MapOfShape aMFHoles;
1074       const TopoDS_Face& aFOr = TopoDS::Face(theFacesOrigins.Find(aF));
1075       FindFacesInsideHoleWires(aFOr, aF, aLFImages, theInvertedEdges,
1076                                aDMEOrLEIm, anEFMap, aMFHoles, theDMFNewHoles, aCtx);
1077       //
1078       TopTools_MapIteratorOfMapOfShape aItMH(aMFHoles);
1079       for (; aItMH.More(); aItMH.Next()) {
1080         aBB.Add(aFHoles, aItMH.Value());
1081       }
1082       //
1083       // find invalid faces
1084       FindInvalidFaces(aLFImages, theInvEdges, theValidEdges, aDMFMVE, aDMFMIE,
1085                        *pMNE, theInvertedEdges, aMEdgeInvalidByVertex, aMEdgeValidByVertex,
1086                        aMFHoles, aMFInvInHole, aLFInv, anInvertedFaces);
1087     }
1088     //
1089     if (aLFInv.Extent()) {
1090       if (theAlreadyInvFaces.IsBound(aF)) {
1091         if (theAlreadyInvFaces.Find(aF) > 2) {
1092           if (aLFInv.Extent() == aLFImages.Extent() && !bArtificialCase) {
1093             aLFImages.Clear();
1094           }
1095           //
1096           aLFInv.Clear();
1097         }
1098       }
1099       theInvFaces.Add(aF, aLFInv);
1100     }
1101   }
1102   //
1103   if (theInvFaces.IsEmpty()) {
1104     theInvEdges.Clear();
1105     return;
1106   }
1107   //
1108 #ifdef OFFSET_DEBUG
1109   // show invalid faces
1110   TopoDS_Compound aCFInv1;
1111   BRep_Builder().MakeCompound(aCFInv1);
1112   Standard_Integer aNbFInv = theInvFaces.Extent();
1113   for (i = 1; i <= aNbFInv; ++i) {
1114     const TopTools_ListOfShape& aLFInv = theInvFaces(i);
1115     TopTools_ListIteratorOfListOfShape aItLFInv(aLFInv);
1116     for (; aItLFInv.More(); aItLFInv.Next()) {
1117       const TopoDS_Shape& aFIm = aItLFInv.Value();
1118       BRep_Builder().Add(aCFInv1, aFIm);
1119     }
1120   }
1121 #endif
1122   //
1123   TopTools_IndexedMapOfShape aMERemoved;
1124   // remove invalid splits of faces using inverted edges
1125   RemoveInvalidSplitsByInvertedEdges(theInvertedEdges, theOEOrigins,
1126                                      theInvFaces, theFImages, aMERemoved);
1127   if (theInvFaces.IsEmpty()) {
1128     theInvEdges.Clear();
1129     return;
1130   }
1131   //
1132   // remove invalid splits from valid splits
1133   RemoveInvalidSplitsFromValid (theInvFaces, theArtInvFaces, theInvertedEdges,
1134                                 aDMFMVIE, theFImages);
1135   //
1136   // remove inside faces
1137   TopTools_IndexedMapOfShape aMEInside;
1138   RemoveInsideFaces(theFImages, theInvFaces, theArtInvFaces, theInvEdges, theInvertedEdges,
1139                     anInvertedFaces, aMFToCheckInt, aMFInvInHole, aFHoles, theSSInterfs,
1140                     aMERemoved, aMEInside, theSolids);
1141   //
1142   // make compound of valid splits
1143   TopoDS_Compound aCFIm;
1144   aBB.MakeCompound(aCFIm);
1145   //
1146   aNb = theFImages.Extent();
1147   for (i = 1; i <= aNb; ++i) {
1148     const TopTools_ListOfShape& aLFIm = theFImages(i);
1149     aItLF.Initialize(aLFIm);
1150     for (; aItLF.More(); aItLF.Next()) {
1151       const TopoDS_Shape& aFIm = aItLF.Value();
1152       aBB.Add(aCFIm, aFIm);
1153     }
1154   }
1155   //
1156   TopTools_IndexedDataMapOfShapeListOfShape aDMEF;
1157   TopExp::MapShapesAndAncestors(aCFIm, TopAbs_EDGE, TopAbs_FACE, aDMEF);
1158   //
1159   // filter maps of images and origins
1160   FilterEdgesImages(aCFIm, theOEImages, theOEOrigins);
1161   //
1162   // filter invalid faces
1163   FilterInvalidFaces(theFImages, aDMEF, theInvEdges, aMEInside, theInvFaces, theArtInvFaces);
1164   aNb = theInvFaces.Extent();
1165   if (!aNb) {
1166     theInvEdges.Clear();
1167     return;
1168   }
1169   //
1170 #ifdef OFFSET_DEBUG
1171   // show invalid faces
1172   TopoDS_Compound aCFInv;
1173   BRep_Builder().MakeCompound(aCFInv);
1174   aNbFInv = theInvFaces.Extent();
1175   for (i = 1; i <= aNbFInv; ++i) {
1176     const TopTools_ListOfShape& aLFInv = theInvFaces(i);
1177     TopTools_ListIteratorOfListOfShape aItLFInv(aLFInv);
1178     for (; aItLFInv.More(); aItLFInv.Next()) {
1179       const TopoDS_Shape& aFIm = aItLFInv.Value();
1180       BRep_Builder().Add(aCFInv, aFIm);
1181     }
1182   }
1183 #endif
1184   //
1185   // filter invalid edges
1186   FilterInvalidEdges(theInvFaces, theArtInvFaces, aDMFMIE, aMERemoved, theInvEdges);
1187   //
1188 #ifdef OFFSET_DEBUG
1189   // show invalid edges
1190   TopoDS_Compound aCEInv;
1191   BRep_Builder().MakeCompound(aCEInv);
1192   aNbEInv = theInvEdges.Extent();
1193   for (i = 1; i <= aNbEInv; ++i) {
1194     const TopoDS_Shape& aE = theInvEdges(i);
1195     BRep_Builder().Add(aCEInv, aE);
1196   }
1197 #endif
1198   //
1199   theLastInvEdges.Clear();
1200   aNb = theInvEdges.Extent();
1201   for (i = 1; i <= aNb; ++i) {
1202     const TopoDS_Shape& aE = theInvEdges(i);
1203     theEdgesToAvoid.Add(aE);
1204     theLastInvEdges.Add(aE);
1205   }
1206   //
1207   aNb = theInvFaces.Extent();
1208   for (i = 1; i <= aNb; ++i) {
1209     const TopoDS_Shape& aF = theInvFaces.FindKey(i);
1210     if (theAlreadyInvFaces.IsBound(aF)) {
1211       theAlreadyInvFaces.ChangeFind(aF)++;
1212     }
1213     else {
1214       theAlreadyInvFaces.Bind(aF, 1);
1215     }
1216   }
1217 }
1218
1219 //=======================================================================
1220 //function : IntersectTrimmedEdges
1221 //purpose  : Intersection of the trimmed edges among themselves
1222 //=======================================================================
1223 void IntersectTrimmedEdges(const TopTools_ListOfShape& theLF,
1224                            const Handle(BRepAlgo_AsDes)& theAsDes,
1225                            TopTools_DataMapOfShapeListOfShape& theOEImages,
1226                            TopTools_DataMapOfShapeListOfShape& theOEOrigins,
1227                            TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
1228                            Handle(IntTools_Context)& theCtx,
1229                            TopTools_MapOfShape& theNewEdges,
1230                            TopTools_DataMapOfShapeShape& theETrimEInf)
1231 {
1232   if (theLF.IsEmpty()) {
1233     return;
1234   }
1235   //
1236   // get edges to intersect from descendants of the offset faces
1237   TopTools_ListOfShape aLS;
1238   //
1239   TopTools_ListIteratorOfListOfShape aItLF(theLF);
1240   for (; aItLF.More(); aItLF.Next()) {
1241     const TopoDS_Face& aF = *(TopoDS_Face*)&aItLF.Value();
1242     //
1243     const TopTools_ListOfShape& aLE = theAsDes->Descendant(aF);
1244     TopTools_ListIteratorOfListOfShape aItLE(aLE);
1245     for (; aItLE.More(); aItLE.Next()) {
1246       const TopoDS_Edge& aE = *(TopoDS_Edge*)&aItLE.Value();
1247       //
1248       if (ProcessMicroEdge(aE, theCtx)) {
1249         continue;
1250       }
1251       //
1252       if (theNewEdges.Add(aE)) {
1253         aLS.Append(aE);
1254       }
1255     }
1256   }
1257   //
1258   if (aLS.Extent() < 2) {
1259     // nothing to intersect
1260     return;
1261   }
1262   //
1263   // perform intersection of the edges
1264   BOPAlgo_Builder aGFE;
1265   aGFE.SetArguments(aLS);
1266   aGFE.Perform();
1267   if (aGFE.HasErrors()) {
1268     return;
1269   }
1270   //
1271   TopTools_ListOfShape aLA;
1272   // fill map with edges images
1273   TopTools_ListIteratorOfListOfShape aIt(aLS);
1274   for (; aIt.More(); aIt.Next()) {
1275     const TopoDS_Shape& aE = aIt.Value();
1276     const TopTools_ListOfShape& aLEIm = aGFE.Modified(aE);
1277     if (aLEIm.IsEmpty()) {
1278       continue;
1279     }
1280     //
1281     aLA.Append(aE);
1282     // save images
1283     theOEImages.Bind(aE, aLEIm);
1284     // save origins
1285     TopTools_ListIteratorOfListOfShape aItLE(aLEIm);
1286     for (; aItLE.More(); aItLE.Next()) {
1287       const TopoDS_Shape& aEIm = aItLE.Value();
1288       TopTools_ListOfShape* pLEOr = theOEOrigins.ChangeSeek(aEIm);
1289       if (!pLEOr) {
1290         pLEOr = theOEOrigins.Bound(aEIm, TopTools_ListOfShape());
1291       }
1292       AppendToList(*pLEOr, aE);
1293     }
1294   }
1295   //
1296   UpdateOrigins(aLA, theEdgesOrigins, aGFE);
1297   UpdateIntersectedEdges(aLA, theETrimEInf, aGFE);
1298 }
1299
1300 //=======================================================================
1301 //function : GetEdges
1302 //purpose  : Getting edges from AsDes map to build the splits of faces
1303 //=======================================================================
1304 Standard_Boolean GetEdges(const TopoDS_Face& theFace,
1305                           const Handle(BRepAlgo_AsDes)& theAsDes,
1306                           const TopTools_DataMapOfShapeListOfShape& theEImages,
1307                           const TopTools_MapOfShape& theLastInvEdges,
1308                           const TopTools_IndexedMapOfShape& theInvEdges,
1309                           Handle(IntTools_Context)& theCtx,
1310                           const TopTools_MapOfShape& theModifiedEdges,
1311                           TopoDS_Shape& theEdges,
1312                           TopTools_IndexedMapOfShape& theInv)
1313 {
1314   // get boundary edges
1315   TopTools_MapOfShape aMFBounds;
1316   TopExp_Explorer aExp(theFace, TopAbs_EDGE);
1317   for (; aExp.More(); aExp.Next()) {
1318     const TopoDS_Shape& aE = aExp.Current();
1319     const TopTools_ListOfShape* pLEIm = theEImages.Seek(aE);
1320     if (!pLEIm) {
1321       aMFBounds.Add(aE);
1322     }
1323     else {
1324       TopTools_ListIteratorOfListOfShape aItLE(*pLEIm);
1325       for (; aItLE.More(); aItLE.Next()) {
1326         const TopoDS_Shape& aEIm = aItLE.Value();
1327         aMFBounds.Add(aEIm);
1328       }
1329     }
1330   }
1331   //
1332   BRep_Builder aBB;
1333   Standard_Boolean bFound(Standard_False), bUpdate(Standard_False);
1334   // the resulting edges
1335   TopoDS_Compound anEdges;
1336   aBB.MakeCompound(anEdges);
1337   // Fence map
1338   TopTools_MapOfShape aMEFence;
1339   // the edges by which the offset face should be split
1340   const TopTools_ListOfShape& aLE = theAsDes->Descendant(theFace);
1341   TopTools_ListIteratorOfListOfShape aItLE(aLE);
1342   for (; aItLE.More(); aItLE.Next()) {
1343     const TopoDS_Edge& aE = TopoDS::Edge(aItLE.Value());
1344     //
1345     if (!bUpdate) {
1346       bUpdate = theModifiedEdges.Contains(aE);
1347     }
1348     //
1349     const TopTools_ListOfShape* pLEIm = theEImages.Seek(aE);
1350     if (pLEIm) {
1351       TopTools_ListIteratorOfListOfShape aItLEIm(*pLEIm);
1352       for (; aItLEIm.More(); aItLEIm.Next()) {
1353         const TopoDS_Edge& aEIm = TopoDS::Edge(aItLEIm.Value());
1354         //
1355         if (!aMEFence.Add(aEIm))
1356           continue;
1357
1358         if (theInvEdges.Contains(aEIm)) {
1359           theInv.Add(aEIm);
1360           if (!bUpdate) {
1361             bUpdate = theLastInvEdges.Contains(aEIm);
1362           }
1363           continue;
1364         }
1365         // check for micro edge
1366         if (ProcessMicroEdge(aEIm, theCtx)) {
1367           continue;
1368         }
1369         //
1370         aBB.Add(anEdges, aEIm);
1371         if (!bFound) {
1372           bFound = !aMFBounds.Contains(aEIm);
1373         }
1374         //
1375         if (!bUpdate) {
1376           bUpdate = theModifiedEdges.Contains(aEIm);
1377         }
1378       }
1379     }
1380     else {
1381       if (theInvEdges.Contains(aE)) {
1382         theInv.Add(aE);
1383         if (!bUpdate) {
1384           bUpdate = theLastInvEdges.Contains(aE);
1385         }
1386         continue;
1387       }
1388       //
1389       if (ProcessMicroEdge(aE, theCtx)) {
1390         continue;
1391       }
1392       aBB.Add(anEdges, aE);
1393       if (!bFound) {
1394         bFound = !aMFBounds.Contains(aE);
1395       }
1396     }
1397   }
1398   //
1399   theEdges = anEdges;
1400   return bFound && bUpdate;
1401 }
1402
1403 //=======================================================================
1404 //function : BuildSplitsOfFace
1405 //purpose  : Building the splits of offset face
1406 //=======================================================================
1407 void BuildSplitsOfFace(const TopoDS_Face& theFace,
1408                        const TopoDS_Shape& theEdges,
1409                        TopTools_DataMapOfShapeShape& theFacesOrigins,
1410                        TopTools_ListOfShape& theLFImages)
1411 {
1412   theLFImages.Clear();
1413   //
1414   // take edges to split the face
1415   TopTools_ListOfShape aLE;
1416   TopExp_Explorer aExp(theEdges, TopAbs_EDGE);
1417   for (; aExp.More(); aExp.Next()) {
1418     TopoDS_Edge aE = TopoDS::Edge(aExp.Current());
1419     aE.Orientation(TopAbs_FORWARD);
1420     aLE.Append(aE);
1421     aE.Orientation(TopAbs_REVERSED);
1422     aLE.Append(aE);
1423   }
1424   //
1425   TopoDS_Face aFF = theFace;
1426   TopAbs_Orientation anOr = theFace.Orientation();
1427   aFF.Orientation(TopAbs_FORWARD);
1428   //
1429   // build pcurves for edges on the face
1430   BRepLib::BuildPCurveForEdgesOnPlane(aLE, aFF);
1431   //
1432   // build splits of faces
1433   BOPAlgo_BuilderFace aBF;
1434   aBF.SetFace(aFF);
1435   aBF.SetShapes(aLE);
1436   aBF.Perform();
1437   //
1438   const TopTools_ListOfShape& aLFSp = aBF.Areas();
1439   TopTools_ListIteratorOfListOfShape aItLF(aLFSp);
1440   for (; aItLF.More(); aItLF.Next()) {
1441     TopoDS_Shape& aFSp = aItLF.ChangeValue();
1442     aFSp.Orientation(anOr);
1443     theLFImages.Append(aFSp);
1444     //
1445     theFacesOrigins.Bind(aFSp, theFace);
1446   }
1447 }
1448
1449 //=======================================================================
1450 //function : BuildSplitsOfFace
1451 //purpose  : Building the splits of offset face
1452 //=======================================================================
1453 void BuildSplitsOfTrimmedFace(const TopoDS_Face& theFace,
1454                               const TopoDS_Shape& theEdges,
1455                               TopTools_ListOfShape& theLFImages)
1456 {
1457   BOPAlgo_Builder aGF;
1458   //
1459   aGF.AddArgument(theFace);
1460   aGF.AddArgument(theEdges);
1461   aGF.Perform();
1462   if (aGF.HasErrors()) {
1463     return;
1464   }
1465   //
1466   // splits of the offset shape
1467   theLFImages = aGF.Modified(theFace);
1468 }
1469
1470 //=======================================================================
1471 //function : CheckIfArtificial
1472 //purpose  : Checks if the face is artificially invalid
1473 //=======================================================================
1474 Standard_Boolean CheckIfArtificial(const TopoDS_Shape& theF,
1475                                    const TopTools_ListOfShape& theLFImages,
1476                                    const TopoDS_Shape& theCE,
1477                                    const TopTools_IndexedMapOfShape& theMapEInv,
1478                                    const TopTools_DataMapOfShapeListOfShape& theOEImages,
1479                                    TopTools_MapOfShape& theMENInv,
1480                                    Handle(BRepAlgo_AsDes)& theAsDes)
1481 {
1482   // all boundary edges should be used
1483   TopTools_IndexedMapOfShape aMEUsed;
1484   TopTools_ListIteratorOfListOfShape aItLFIm(theLFImages);
1485   for (; aItLFIm.More(); aItLFIm.Next()) {
1486     const TopoDS_Shape& aFIm = aItLFIm.Value();
1487     TopExp::MapShapes(aFIm, TopAbs_EDGE, aMEUsed);
1488     TopExp::MapShapes(aFIm, TopAbs_VERTEX, aMEUsed);
1489   }
1490   //
1491   TopTools_IndexedDataMapOfShapeListOfShape aMVE;
1492   TopExp::MapShapesAndAncestors(theCE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
1493   //
1494   Standard_Integer i, aNb = theMapEInv.Extent();
1495   for (i = 1; i <= aNb; ++i) {
1496     const TopoDS_Shape& aEInv = theMapEInv(i);
1497     TopExp_Explorer aExpV(aEInv, TopAbs_VERTEX);
1498     for (; aExpV.More(); aExpV.Next()) {
1499       const TopoDS_Shape& aVEInv = aExpV.Current();
1500       const TopTools_ListOfShape* pLENInv = aMVE.Seek(aVEInv);
1501       if (pLENInv) {
1502         TopTools_ListIteratorOfListOfShape aItLEInv(*pLENInv);
1503         for (; aItLEInv.More(); aItLEInv.Next()) {
1504           const TopoDS_Shape& aENInv = aItLEInv.Value();
1505           if (!aMEUsed.Contains(aENInv)) {
1506             theMENInv.Add(aENInv);
1507           }
1508         }
1509       }
1510     }
1511   }
1512   //
1513   if (theMENInv.IsEmpty()) {
1514     return Standard_False;
1515   }
1516   //
1517   TopTools_IndexedMapOfShape aMEFound;
1518   TopExp::MapShapes(theCE, TopAbs_EDGE, aMEFound);
1519   //
1520   const TopTools_ListOfShape& aLE = theAsDes->Descendant(theF);
1521   TopTools_ListIteratorOfListOfShape aItLE(aLE);
1522   for (; aItLE.More(); aItLE.Next()) {
1523     const TopoDS_Edge& aE = TopoDS::Edge(aItLE.Value());
1524     //
1525     if (theOEImages.IsBound(aE)) {
1526       Standard_Boolean bChecked = Standard_False;
1527       const TopTools_ListOfShape& aLEIm = theOEImages.Find(aE);
1528       TopTools_ListIteratorOfListOfShape aItLEIm(aLEIm);
1529       for (; aItLEIm.More(); aItLEIm.Next()) {
1530         const TopoDS_Edge& aEIm = TopoDS::Edge(aItLEIm.Value());
1531         if (!aMEFound.Contains(aEIm) || theMENInv.Contains(aEIm)) {
1532           continue;
1533         }
1534         //
1535         bChecked = Standard_True;
1536         if (aMEUsed.Contains(aEIm)) {
1537           break;
1538         }
1539       }
1540       //
1541       if (bChecked && !aItLEIm.More()) {
1542         break;
1543       }
1544     }
1545     else {
1546       if (aMEFound.Contains(aE) && !theMENInv.Contains(aE) && !aMEUsed.Contains(aE)) {
1547         break;
1548       }
1549     }
1550   }
1551   //
1552   return aItLE.More();
1553 }
1554
1555 //=======================================================================
1556 //function : FindInvalidEdges
1557 //purpose  : Looking for the invalid edges
1558 //=======================================================================
1559 void FindInvalidEdges(const TopoDS_Face& theF,
1560                       const TopTools_ListOfShape& theLFImages,
1561                       const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
1562                       const TopTools_DataMapOfShapeShape& theFacesOrigins,
1563                       const BRepOffset_Analyse* theAnalyse,
1564                       const TopTools_DataMapOfShapeListOfShape& theOEImages,
1565                       const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
1566                       TopTools_IndexedMapOfShape& theInvEdges,
1567                       TopTools_IndexedMapOfShape& theValidEdges,
1568                       BRepOffset_DataMapOfShapeMapOfShape& theDMFMVE,
1569                       BRepOffset_DataMapOfShapeMapOfShape& theDMFMNE,
1570                       BRepOffset_DataMapOfShapeIndexedMapOfShape& theDMFMIE,
1571                       BRepOffset_DataMapOfShapeMapOfShape& theDMFMVIE,
1572                       TopTools_DataMapOfShapeListOfShape& theDMEOrLEIm,
1573                       TopTools_MapOfShape& theMEInverted,
1574                       TopTools_MapOfShape& theEdgesInvalidByVertex,
1575                       TopTools_MapOfShape& theEdgesValidByVertex)
1576 {
1577   // Edge is considered as invalid in the following cases:
1578   // 1. Its orientation on the face has changed comparing to the originals edge and face;
1579   // 2. The vertices of the edge have changed places comparing to the originals edge and face.
1580   //
1581   // The edges created from vertices, i.e. as intersection between two faces connected only
1582   // by VERTEX, will also be checked on validity. For these edges the correct orientation will
1583   // be defined by the edges on the original face adjacent to the connection vertex
1584
1585   // original face
1586   const TopoDS_Face& aFOr = *(TopoDS_Face*)&theFacesOrigins.Find(theF);
1587   // invalid edges
1588   TopTools_IndexedMapOfShape aMEInv;
1589   // valid edges
1590   TopTools_MapOfShape aMEVal;
1591   // internal edges
1592   TopTools_MapOfShape aMEInt;
1593   //
1594   // maps for checking the inverted edges
1595   TopTools_IndexedDataMapOfShapeListOfShape aDMVE, aDMEF;
1596   TopTools_IndexedMapOfShape aMEdges;
1597   // back map from the original shapes to their offset images
1598   TopTools_DataMapOfShapeListOfShape anImages;
1599   //
1600   TopTools_ListIteratorOfListOfShape aItLF(theLFImages);
1601   for (; aItLF.More(); aItLF.Next()) {
1602     const TopoDS_Face& aFIm = *(TopoDS_Face*)&aItLF.Value();
1603     //
1604     TopExp_Explorer aExp(aFIm, TopAbs_EDGE);
1605     for (; aExp.More(); aExp.Next()) {
1606       const TopoDS_Shape& aE = aExp.Current();
1607       // keep all edges
1608       aMEdges.Add(aE);
1609       //
1610       // keep connection from edges to faces
1611       TopTools_ListOfShape* pLF = aDMEF.ChangeSeek(aE);
1612       if (!pLF) {
1613         pLF = &aDMEF(aDMEF.Add(aE, TopTools_ListOfShape()));
1614       }
1615       AppendToList(*pLF, aFIm);
1616       //
1617       // keep connection from vertices to edges
1618       TopoDS_Iterator aItV(aE);
1619       for (; aItV.More(); aItV.Next()) {
1620         const TopoDS_Shape& aV = aItV.Value();
1621         //
1622         TopTools_ListOfShape* pLE = aDMVE.ChangeSeek(aV);
1623         if (!pLE) {
1624           pLE = &aDMVE(aDMVE.Add(aV, TopTools_ListOfShape()));
1625         }
1626         AppendToList(*pLE, aE);
1627       }
1628
1629       // back map from original edges to their offset images
1630       const TopTools_ListOfShape* pLOr = theEdgesOrigins.Seek (aE);
1631       if (!pLOr)
1632         continue;
1633       for (TopTools_ListOfShape::Iterator itOr (*pLOr); itOr.More(); itOr.Next())
1634       {
1635         const TopoDS_Shape& aSOr = itOr.Value();
1636         TopoDS_Shape aSInF;
1637         if (!FindShape (aSOr, aFOr, theAnalyse, aSInF))
1638           continue;
1639         TopTools_ListOfShape* pImages = anImages.ChangeSeek (aSInF);
1640         if (!pImages)
1641           pImages = anImages.Bound (aSInF, TopTools_ListOfShape());
1642         AppendToList (*pImages, aE);
1643       }
1644     }
1645   }
1646   //
1647   // the map will be used to find the edges on the original face
1648   // adjacent to the same vertex. It will be filled at first necessity;
1649   TopTools_IndexedDataMapOfShapeListOfShape aDMVEFOr;
1650   //
1651   aItLF.Initialize(theLFImages);
1652   for (; aItLF.More(); aItLF.Next()) {
1653     const TopoDS_Face& aFIm = *(TopoDS_Face*)&aItLF.Value();
1654     //
1655     // valid edges for this split
1656     TopTools_MapOfShape aMVE;
1657     // invalid edges for this split
1658     TopTools_IndexedMapOfShape aMIE;
1659     //
1660     TopExp_Explorer aExp(aFIm, TopAbs_EDGE);
1661     for (; aExp.More(); aExp.Next()) {
1662       const TopoDS_Edge& aEIm = *(TopoDS_Edge*)&aExp.Current();
1663       //
1664       if (aEIm.Orientation() == TopAbs_INTERNAL) {
1665         aMEInt.Add(aEIm);
1666         continue;
1667       }
1668       //
1669       if (!theEdgesOrigins.IsBound(aEIm)) {
1670         continue;
1671       }
1672       //
1673       const TopTools_ListOfShape& aLEOr = theEdgesOrigins.Find(aEIm);
1674       if (aLEOr.IsEmpty()) {
1675         continue;
1676       }
1677       //
1678       Standard_Integer aNbVOr = 0;
1679       TopTools_ListIteratorOfListOfShape aItLEO(aLEOr);
1680       for (; aItLEO.More(); aItLEO.Next()) {
1681         if (aItLEO.Value().ShapeType() == TopAbs_VERTEX) {
1682           ++aNbVOr;
1683         }
1684       }
1685       if (aNbVOr > 1 && (aLEOr.Extent() - aNbVOr) > 1)
1686         continue;
1687       //
1688       TopTools_MapOfShape aME, aMV, aMF;
1689       Standard_Boolean bInvalid = Standard_False, bChecked = Standard_False;
1690       Standard_Integer aNbP = NbPoints(aEIm), aNbInv = 0;
1691       Standard_Boolean bUseVertex = !aNbVOr ? Standard_False :
1692         (aNbVOr == 1 &&
1693          aDMEF.FindFromKey(aEIm).Extent() == 1 &&
1694          !theOEOrigins.IsBound(aEIm));
1695       //
1696       aItLEO.Initialize(aLEOr);
1697       for (; aItLEO.More(); aItLEO.Next()) {
1698         const TopoDS_Shape& aSOr = aItLEO.Value();
1699         Standard_Boolean bVertex = (aSOr.ShapeType() == TopAbs_VERTEX);
1700         //
1701         TopoDS_Shape aEOrF;
1702         if (bVertex) {
1703           // for some cases it is impossible to check the validity of the edge
1704           if (!bUseVertex) {
1705             continue;
1706           }
1707           // find edges on the original face adjacent to this vertex
1708           if (aDMVEFOr.IsEmpty()) {
1709             // fill the map
1710             TopExp::MapShapesAndAncestors(aFOr, TopAbs_VERTEX, TopAbs_EDGE, aDMVEFOr);
1711           }
1712           //
1713           TopTools_ListOfShape *pLEFOr = aDMVEFOr.ChangeSeek(aSOr);
1714           if (pLEFOr) {
1715             TopoDS_Compound aCEOr;
1716             BRep_Builder().MakeCompound(aCEOr);
1717             // Avoid classification of edges originated from vertices
1718             // located between tangent edges
1719             Standard_Boolean bAllTgt = Standard_True;
1720             TopTools_ListIteratorOfListOfShape aItLEFOr(*pLEFOr);
1721             gp_Vec aVRef = GetAverageTangent (aItLEFOr.Value(), aNbP);
1722             for (; aItLEFOr.More(); aItLEFOr.Next())
1723             {
1724               const TopoDS_Shape& aEOr = aItLEFOr.Value();
1725               BRep_Builder().Add(aCEOr, aEOr);
1726
1727               gp_Vec aVCur = GetAverageTangent (aEOr, aNbP);
1728               if (!aVRef.IsParallel (aVCur, Precision::Angular()))
1729                 bAllTgt = Standard_False;
1730             }
1731             if (!bAllTgt)
1732               aEOrF = aCEOr;
1733           }
1734         }
1735         else {
1736           FindShape(aSOr, aFOr, theAnalyse, aEOrF);
1737           //
1738           TopTools_ListOfShape *pLEIm = theDMEOrLEIm.ChangeSeek(aSOr);
1739           if (!pLEIm) {
1740             pLEIm = theDMEOrLEIm.Bound(aSOr, TopTools_ListOfShape());
1741           }
1742           AppendToList(*pLEIm, aEIm);
1743         }
1744         //
1745         if (aEOrF.IsNull()) {
1746           // the edge has not been found
1747           continue;
1748         }
1749
1750         if (bVertex)
1751         {
1752           TopTools_MapOfShape aMVTotal;
1753           Standard_Integer aNbChecked = 0;
1754           // Just check if the original edges sharing the vertex do not share it any more.
1755           for (TopoDS_Iterator it (aEOrF); it.More(); it.Next())
1756           {
1757             const TopoDS_Shape& aEOr = it.Value();
1758             const TopTools_ListOfShape* aLIm = anImages.Seek (aEOr);
1759             if (!aLIm)
1760               continue;
1761             ++aNbChecked;
1762             TopTools_IndexedDataMapOfShapeListOfShape aMVLoc;
1763             for (TopTools_ListOfShape::Iterator itLIM (*aLIm); itLIM.More(); itLIM.Next())
1764               TopExp::MapShapesAndAncestors (itLIM.Value(), TopAbs_VERTEX, TopAbs_EDGE, aMVLoc);
1765             for (Standard_Integer i = 1; i <= aMVLoc.Extent(); ++i)
1766             {
1767               if (aMVLoc(i).Extent() > 1 && !aMVTotal.Add (aMVLoc.FindKey (i)))
1768               {
1769                 bInvalid = Standard_True;
1770                 theEdgesInvalidByVertex.Add(aEIm);
1771                 break;
1772               }
1773             }
1774             if (bInvalid)
1775               break;
1776           }
1777           if (!bInvalid && aNbChecked < 2)
1778             continue;
1779           else
1780             theEdgesValidByVertex.Add (aEIm);
1781         }
1782         else
1783         {
1784           //
1785           // Check orientations of the image edge and original edge.
1786           // In case the 3d curves are having the same direction the orientations 
1787           // must be the same. Otherwise the orientations should also be different.
1788           //
1789           // get average tangent vector for each curve taking into account
1790           // the orientations of the edges, i.e. the edge is reversed
1791           // the vector is reversed as well
1792           gp_Vec aVSum1 = GetAverageTangent(aEIm, aNbP);
1793           gp_Vec aVSum2 = GetAverageTangent(aEOrF, aNbP);
1794           //
1795           aVSum1.Normalize();
1796           aVSum2.Normalize();
1797           //
1798           Standard_Real aCos = aVSum1.Dot(aVSum2);
1799           if (Abs(aCos) < 0.9999) {
1800             continue;
1801           }
1802           //
1803           aME.Add(aEOrF);
1804           TopExp_Explorer aExpE(aEOrF, TopAbs_VERTEX);
1805           for (; aExpE.More(); aExpE.Next()) {
1806             const TopoDS_Shape& aV = aExpE.Current();
1807             aMV.Add(aV);
1808           }
1809           if (theAnalyse)
1810           {
1811             for (TopTools_ListOfShape::Iterator itFA (theAnalyse->Ancestors (aEOrF));
1812                  itFA.More(); itFA.Next())
1813               aMF.Add (itFA.Value());
1814           }
1815           //
1816           if (aCos < Precision::Confusion()) {
1817             bInvalid = Standard_True;
1818             aNbInv++;
1819           }
1820         }
1821         bChecked = Standard_True;
1822       }
1823       //
1824       if (!bChecked) {
1825         continue;
1826       }
1827       //
1828       Standard_Boolean bLocalOnly = (aNbVOr > 1 && (aLEOr.Extent() - aNbVOr) > 1);
1829       Standard_Integer aNbE = aME.Extent(), aNbV = aMV.Extent();
1830       if (aNbE > 1 && aNbV == 2*aNbE)
1831       {
1832         Standard_Boolean bSkip = Standard_True;
1833
1834         // Allow the edge to be analyzed if it is:
1835         // * originated from more than two faces
1836         // * unanimously considered valid or invalid
1837         // * not a boundary edge in the splits
1838         if (aMF.Extent () > 2 && (aNbInv == 0 || aNbInv == aNbE))
1839         {
1840           if (theLFImages.Extent() > 2)
1841           {
1842             TopoDS_Iterator itV (aEIm);
1843             for (; itV.More(); itV.Next())
1844             {
1845               TopTools_ListOfShape::Iterator itE (aDMVE.FindFromKey (itV.Value()));
1846               for (; itE.More(); itE.Next())
1847                 if (aDMEF.FindFromKey (itE.Value()).Extent() < 2)
1848                   break;
1849               if (itE.More())
1850                 break;
1851             }
1852             bSkip = itV.More();
1853           }
1854         }
1855         if (bSkip)
1856           continue;
1857         else
1858           bLocalOnly = Standard_True;
1859       }
1860       //
1861       if (bInvalid) {
1862         if (!bLocalOnly)
1863           theInvEdges.Add(aEIm);
1864         aMIE.Add (aEIm);
1865         aMEInv.Add(aEIm);
1866         continue;
1867       }
1868       //
1869       // check if the edge has been inverted
1870       Standard_Boolean bInverted = !aNbE || bLocalOnly ? Standard_False :
1871         CheckInverted(aEIm, aFOr, theOEImages, theOEOrigins,
1872           theEdgesOrigins, aDMVE, aMEdges, theMEInverted);
1873       //
1874       if (!bInverted || !aNbVOr) {
1875         if (!bLocalOnly)
1876           theValidEdges.Add(aEIm);
1877         aMVE.Add (aEIm);
1878         aMEVal.Add(aEIm);
1879       }
1880     }
1881     //
1882     // valid edges
1883     if (aMVE.Extent())
1884     {
1885       theDMFMVE.Bind (aFIm, aMVE);
1886     }
1887     //
1888     // invalid edges
1889     if (aMIE.Extent())
1890     {
1891       theDMFMIE.Bind (aFIm, aMIE);
1892     }
1893   }
1894   //
1895   // process invalid edges:
1896   // check for the inverted edges
1897   TopTools_MapOfShape aMVIE;
1898   // fill neutral edges
1899   TopTools_MapOfShape aMNE;
1900   //
1901   Standard_Integer i, aNbEInv = aMEInv.Extent();
1902   for (i = 1; i <= aNbEInv; ++i) {
1903     const TopoDS_Shape& aEIm = aMEInv(i);
1904     //
1905     // neutral edges - on the splits of the same offset face
1906     // it is valid for one split and invalid for other
1907     if (aMEVal.Contains(aEIm))
1908     {
1909       aMNE.Add (aEIm);
1910       continue;
1911     }
1912     //
1913     // the inverted images of the origins of invalid edges should also be invalid
1914     if (!theMEInverted.Contains(aEIm)) {
1915       continue;
1916     }
1917     //
1918     const TopTools_ListOfShape* pLOEOr = theOEOrigins.Seek(aEIm);
1919     if (!pLOEOr) {
1920       continue;
1921     }
1922     //
1923     TopTools_ListIteratorOfListOfShape aItLOEOr(*pLOEOr);
1924     for (; aItLOEOr.More(); aItLOEOr.Next()) {
1925       const TopoDS_Shape& aOEOr = aItLOEOr.Value();
1926       const TopTools_ListOfShape& aLEIm1 = theOEImages.Find(aOEOr);
1927       //
1928       TopTools_ListIteratorOfListOfShape aItLEIm1(aLEIm1);
1929       for (; aItLEIm1.More(); aItLEIm1.Next()) {
1930         const TopoDS_Shape& aEIm1 = aItLEIm1.Value();
1931         if (aMEdges.Contains(aEIm1) &&
1932             !aMEInv.Contains(aEIm1) && !aMEInt.Contains(aEIm1) &&
1933             theMEInverted.Contains(aEIm1)) {
1934           theInvEdges.Add(aEIm1);
1935           aMVIE.Add (aEIm1);
1936         }
1937       }
1938     }
1939   }
1940   //
1941   if (aMNE.Extent())
1942   {
1943     theDMFMNE.Bind (theF, aMNE);
1944   }
1945   //
1946   if (aMVIE.Extent())
1947   {
1948     theDMFMVIE.Bind (theF, aMVIE);
1949   }
1950 }
1951
1952 //=======================================================================
1953 //function : FindInvalidFaces
1954 //purpose  : Looking for the invalid faces by analyzing their invalid edges
1955 //=======================================================================
1956 void FindInvalidFaces(TopTools_ListOfShape& theLFImages,
1957                       const TopTools_IndexedMapOfShape& theInvEdges,
1958                       const TopTools_IndexedMapOfShape& theValidEdges,
1959                       const BRepOffset_DataMapOfShapeMapOfShape& theDMFMVE,
1960                       const BRepOffset_DataMapOfShapeIndexedMapOfShape& theDMFMIE,
1961                       const TopTools_MapOfShape& theMENeutral,
1962                       const TopTools_MapOfShape& theMEInverted,
1963                       const TopTools_MapOfShape& theEdgesInvalidByVertex,
1964                       const TopTools_MapOfShape& theEdgesValidByVertex,
1965                       const TopTools_MapOfShape& theMFHoles,
1966                       TopTools_IndexedMapOfShape& theMFInvInHole,
1967                       TopTools_ListOfShape& theInvFaces,
1968                       TopTools_ListOfShape& theInvertedFaces)
1969 {
1970   // The face should be considered as invalid in the following cases:
1971   // 1. It has been reverted, i.e. at least two not connected edges 
1972   //    have changed orientation (i.e. invalid). In this case all edges,
1973   //    should be invalid for that face, because edges have also been reverted;
1974   // 2. All checked edges of the face are invalid for this face;
1975   // The face should be removed from the splits in the following cases:
1976   // 1. All checked edges of the face are invalid for this one, but valid for
1977   //    some other face in this list of splits.
1978   // The face will be kept in the following cases:
1979   // 1. Some of the edges are valid for this face.
1980   Standard_Boolean bHasValid, bAllValid, bAllInvalid, bHasReallyInvalid, bAllInvNeutral;
1981   Standard_Boolean bValid, bValidLoc, bInvalid, bInvalidLoc, bNeutral, bInverted;
1982   Standard_Boolean bIsInvalidByInverted;
1983   Standard_Integer aNbChecked;
1984   //
1985   Standard_Boolean bTreatInvertedAsInvalid = (theLFImages.Extent() == 1);
1986   //
1987   // neutral edges to remove
1988   TopTools_IndexedMapOfShape aMENRem;
1989   //
1990   // faces for post treat
1991   TopTools_ListOfShape aLFPT;
1992   //
1993   TopTools_IndexedDataMapOfShapeListOfShape aDMEF;
1994   TopTools_ListIteratorOfListOfShape aItLF(theLFImages);
1995   for (; aItLF.More(); aItLF.Next())
1996   {
1997     const TopoDS_Face& aFIm = *(TopoDS_Face*)&aItLF.Value();
1998     TopExp::MapShapesAndAncestors (aFIm, TopAbs_EDGE, TopAbs_FACE, aDMEF);
1999   }
2000
2001   aItLF.Initialize (theLFImages);
2002   for (; aItLF.More(); ) {
2003     const TopoDS_Face& aFIm = *(TopoDS_Face*)&aItLF.Value();
2004     //
2005     // valid edges for this split
2006     const TopTools_MapOfShape* pMVE = theDMFMVE.Seek (aFIm);
2007     // invalid edges for this split
2008     const TopTools_IndexedMapOfShape* pMIE = theDMFMIE.Seek (aFIm);
2009     //
2010     bHasValid = Standard_False;
2011     bAllValid = Standard_True;
2012     bAllInvalid = Standard_True;
2013     bHasReallyInvalid = Standard_False;
2014     bAllInvNeutral = Standard_True;
2015     bIsInvalidByInverted = Standard_True;
2016     aNbChecked = 0;
2017     //
2018     const TopoDS_Wire& aWIm = BRepTools::OuterWire(aFIm);
2019     TopExp_Explorer aExp(aWIm, TopAbs_EDGE);
2020     for (; aExp.More(); aExp.Next()) {
2021       const TopoDS_Shape& aEIm = aExp.Current();
2022       //
2023       bValid = theValidEdges.Contains(aEIm);
2024       bInvalid = theInvEdges.Contains(aEIm);
2025       bNeutral = theMENeutral.Contains(aEIm);
2026       //
2027       if (!bValid && !bInvalid && !bNeutral) {
2028         // edge has not been checked for some reason
2029         continue;
2030       }
2031
2032       // skip not-boundary edges originated from vertex
2033       if ((theEdgesInvalidByVertex.Contains (aEIm) ||
2034            theEdgesValidByVertex.Contains (aEIm)) &&
2035            aDMEF.FindFromKey (aEIm).Extent() != 1)
2036         continue;
2037
2038       ++aNbChecked;
2039       //
2040       bInvalidLoc = pMIE && pMIE->Contains (aEIm);
2041       bHasReallyInvalid = bInvalid && bInvalidLoc && !bValid && !theEdgesInvalidByVertex.Contains(aEIm);
2042       if (bHasReallyInvalid) {
2043         break;
2044       }
2045       //
2046       bValidLoc = pMVE && pMVE->Contains(aEIm);
2047       bInverted = theMEInverted.Contains(aEIm);
2048       if (!bInvalid && !bInvalidLoc && bTreatInvertedAsInvalid) {
2049         bInvalid = bInverted;
2050       }
2051       //
2052       if (bValidLoc && bNeutral) {
2053         bHasValid = Standard_True;
2054       }
2055       //
2056       bAllValid &= bValidLoc;
2057       bAllInvalid &= (bInvalid || bInvalidLoc);
2058       bAllInvNeutral &= (bAllInvalid && bNeutral);
2059       bIsInvalidByInverted &= (bInvalidLoc || bInverted);
2060     }
2061     //
2062     if (!aNbChecked) {
2063       aItLF.Next();
2064       continue;
2065     }
2066     //
2067     if (!bHasReallyInvalid && (bAllInvNeutral && !bHasValid) && (aNbChecked > 1)) {
2068       // remove edges from neutral
2069       TopExp::MapShapes(aFIm, TopAbs_EDGE, aMENRem);
2070       // remove face
2071       theLFImages.Remove(aItLF);
2072       continue;
2073     }
2074     //
2075     if (bHasReallyInvalid || (bAllInvalid && 
2076                              !(bHasValid || bAllValid) &&
2077                              !(bAllInvNeutral && (aNbChecked == 1)))) {
2078       theInvFaces.Append(aFIm);
2079       if (theMFHoles.Contains(aFIm)) {
2080         theMFInvInHole.Add(aFIm);
2081       }
2082       aItLF.Next();
2083       continue;
2084     }
2085     //
2086     if (theMFHoles.Contains(aFIm)) {
2087       // remove edges from neutral
2088       TopExp::MapShapes(aFIm, TopAbs_EDGE, aMENRem);
2089       // remove face
2090       theLFImages.Remove(aItLF);
2091       continue;
2092     }
2093     //
2094     if (bIsInvalidByInverted && !(bHasValid || bAllValid))
2095     {
2096       // The face contains only the inverted and locally invalid edges
2097       theInvertedFaces.Append(aFIm);
2098     }
2099
2100     if (!bAllInvNeutral) {
2101       aLFPT.Append(aFIm);
2102     }
2103     else {
2104       // remove edges from neutral
2105       TopExp::MapShapes(aFIm, TopAbs_EDGE, aMENRem);
2106     }
2107     aItLF.Next();
2108   }
2109   //
2110   if (aLFPT.IsEmpty() || aMENRem.IsEmpty()) {
2111     return;
2112   }
2113
2114   // check the splits once more
2115   aItLF.Initialize(aLFPT);
2116   for (; aItLF.More(); aItLF.Next()) {
2117     const TopoDS_Face& aFIm = *(TopoDS_Face*)&aItLF.Value();
2118     //
2119     // valid edges for this split
2120     const TopTools_MapOfShape* pMVE = theDMFMVE.Seek(aFIm);
2121     //
2122     bHasValid = Standard_False;
2123     bAllValid = Standard_True;
2124     bAllInvalid = Standard_True;
2125     //
2126     const TopoDS_Wire& aWIm = BRepTools::OuterWire(aFIm);
2127     TopExp_Explorer aExp(aWIm, TopAbs_EDGE);
2128     for (; aExp.More(); aExp.Next()) {
2129       const TopoDS_Shape& aEIm = aExp.Current();
2130       //
2131       bValid = theValidEdges.Contains(aEIm);
2132       bInvalid = theInvEdges.Contains(aEIm);
2133       bNeutral = theMENeutral.Contains(aEIm) && !aMENRem.Contains (aEIm);
2134       bValidLoc = pMVE && pMVE->Contains(aEIm);
2135       //
2136       if (!bInvalid && bTreatInvertedAsInvalid) {
2137         bInvalid = theMEInverted.Contains(aEIm);
2138       }
2139       //
2140       if (bValidLoc && bNeutral) {
2141         bHasValid = Standard_True;
2142       }
2143       //
2144       bAllValid = bAllValid && bValidLoc;
2145       bAllInvalid = bAllInvalid && bInvalid;
2146     }
2147     //
2148     if (bAllInvalid && !bHasValid && !bAllValid) {
2149       theInvFaces.Append(aFIm);
2150     }
2151   }
2152 }
2153
2154 //=======================================================================
2155 //function : FindFacesInsideHoleWires
2156 //purpose  : Find faces inside holes wires from the original face
2157 //=======================================================================
2158 void FindFacesInsideHoleWires(const TopoDS_Face& theFOrigin,
2159                               const TopoDS_Face& theFOffset,
2160                               const TopTools_ListOfShape& theLFImages,
2161                               const TopTools_MapOfShape& theInvertedEdges,
2162                               const TopTools_DataMapOfShapeListOfShape& theDMEOrLEIm,
2163                               const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
2164                               TopTools_MapOfShape& theMFHoles,
2165                               TopTools_DataMapOfShapeListOfShape& theDMFNewHoles,
2166                               Handle(IntTools_Context)& theContext)
2167 {
2168   if (theLFImages.IsEmpty()) {
2169     return;
2170   }
2171   //
2172   // find all hole wires in the original face
2173   TopTools_ListOfShape aLHoleWires;
2174   const TopoDS_Wire& anOuterWire = BRepTools::OuterWire(theFOrigin);
2175   TopExp_Explorer aExpW(theFOrigin, TopAbs_WIRE);
2176   for (; aExpW.More(); aExpW.Next()) {
2177     const TopoDS_Wire& aHoleWire = TopoDS::Wire(aExpW.Current());
2178     if (!aHoleWire.IsSame(anOuterWire) && aHoleWire.Orientation() != TopAbs_INTERNAL) {
2179       aLHoleWires.Append(aHoleWire);
2180     }
2181   }
2182   //
2183   if (aLHoleWires.IsEmpty()) {
2184     // no holes in the face
2185     return;
2186   }
2187   //
2188   TopTools_ListOfShape *pLFNewHoles = theDMFNewHoles.ChangeSeek(theFOrigin);
2189   //
2190   if (!pLFNewHoles) {
2191     pLFNewHoles = theDMFNewHoles.Bound(theFOrigin, TopTools_ListOfShape());
2192   }
2193   if (pLFNewHoles->IsEmpty()) {
2194     //
2195     // find the faces representing holes in the images of the faces:
2196     // 1. for each original hole wire try to build its image
2197     // 2. build the new planar face from the images
2198     //
2199     // map vertices and edges of the splits
2200     TopTools_IndexedMapOfShape aMESplits;
2201     TopTools_ListIteratorOfListOfShape aItLF(theLFImages);
2202     for (; aItLF.More(); aItLF.Next()) {
2203       TopExp::MapShapes(aItLF.Value(), TopAbs_EDGE, aMESplits);
2204     }
2205     //
2206     TopTools_ListIteratorOfListOfShape aItLW(aLHoleWires);
2207     for (; aItLW.More(); aItLW.Next()) {
2208       const TopoDS_Wire& aHoleWire = TopoDS::Wire(aItLW.Value());
2209       // find images of all edges of the original wire
2210       TopTools_IndexedMapOfShape aMEImWire;
2211       TopoDS_Iterator aItE(aHoleWire);
2212       for (; aItE.More(); aItE.Next()) {
2213         const TopoDS_Shape& aEOr = aItE.Value();
2214         const TopTools_ListOfShape *pLEIm = theDMEOrLEIm.Seek(aEOr);
2215         if (!pLEIm || pLEIm->IsEmpty()) {
2216           continue;
2217         }
2218         TopTools_ListIteratorOfListOfShape aItLEIm(*pLEIm);
2219         for (; aItLEIm.More(); aItLEIm.Next()) {
2220           const TopoDS_Shape& aEIm = aItLEIm.Value();
2221           if (aMESplits.Contains(aEIm)) {
2222             aMEImWire.Add(aEIm);
2223           }
2224         }
2225       }
2226       //
2227       if (aMEImWire.IsEmpty()) {
2228         continue;
2229       }
2230       //
2231       // build new planar face using these edges
2232       TopTools_ListOfShape aLE;
2233       Standard_Integer i, aNbE = aMEImWire.Extent();
2234       for (i = 1; i <= aNbE; ++i) {
2235         aLE.Append(aMEImWire(i).Oriented(TopAbs_FORWARD));
2236         aLE.Append(aMEImWire(i).Oriented(TopAbs_REVERSED));
2237       }
2238       //
2239       BOPAlgo_BuilderFace aBF;
2240       aBF.SetFace(TopoDS::Face(theFOffset.Oriented(TopAbs_FORWARD)));
2241       aBF.SetShapes(aLE);
2242       aBF.Perform();
2243       //
2244       const TopTools_ListOfShape& aLFNew = aBF.Areas();
2245       if (aLFNew.IsEmpty()) {
2246         continue;
2247       }
2248       //
2249       // check if outer edges in the new faces are not inverted
2250       // because the inverted edges mean that the hole has been
2251       // filled during offset and there will be no faces to remove
2252       TopTools_IndexedDataMapOfShapeListOfShape aDMEFNew;
2253       TopTools_ListIteratorOfListOfShape aItLFNew(aLFNew);
2254       for (; aItLFNew.More(); aItLFNew.Next()) {
2255         TopExp::MapShapesAndAncestors(aItLFNew.Value(), TopAbs_EDGE, TopAbs_FACE, aDMEFNew);
2256       }
2257       //
2258       aNbE = aDMEFNew.Extent();
2259       for (i = 1; i <= aNbE; ++i) {
2260         if (aDMEFNew(i).Extent() == 1) {
2261           const TopoDS_Shape& aE = aDMEFNew.FindKey(i);
2262           if (theInvertedEdges.Contains(aE)) {
2263             break;
2264           }
2265         }
2266       }
2267       //
2268       if (i <= aNbE) {
2269         continue;
2270       }
2271       //
2272       aItLFNew.Initialize(aLFNew);
2273       for (; aItLFNew.More(); aItLFNew.Next()) {
2274         pLFNewHoles->Append(aItLFNew.Value());
2275       }
2276     }
2277   }
2278
2279   // Build Edge-Face map for splits of current offset face
2280   TopTools_IndexedDataMapOfShapeListOfShape anEFSplitsMap;
2281   // Build Edge-Face map for holes
2282   TopTools_IndexedDataMapOfShapeListOfShape anEFHolesMap;
2283
2284   // among the splits of the offset face find those that are
2285   // located inside the hole faces
2286   TopTools_ListIteratorOfListOfShape aItLF(theLFImages);
2287   for (; aItLF.More(); aItLF.Next()) {
2288     const TopoDS_Face& aFIm = TopoDS::Face(aItLF.Value());
2289     TopExp::MapShapesAndAncestors(aFIm, TopAbs_EDGE, TopAbs_FACE, anEFSplitsMap);
2290     // get the point inside the face and classify it relatively hole faces
2291     gp_Pnt aP3D;
2292     gp_Pnt2d aP2D;
2293     Standard_Integer iErr = BOPTools_AlgoTools3D::PointInFace(aFIm, aP3D, aP2D, theContext);
2294     if (iErr) {
2295       continue;
2296     }
2297     //
2298     Standard_Real aTol = BRep_Tool::Tolerance(aFIm);
2299     //
2300     TopTools_ListIteratorOfListOfShape aItLFNew(*pLFNewHoles);
2301     for (; aItLFNew.More(); aItLFNew.Next()) {
2302       const TopoDS_Face& aFNew = TopoDS::Face(aItLFNew.Value());
2303       if (theContext->IsValidPointForFace(aP3D, aFNew, aTol)) {
2304         // the face is classified as IN
2305         theMFHoles.Add(aFIm);
2306         TopExp::MapShapesAndAncestors(aFIm, TopAbs_EDGE, TopAbs_FACE, anEFHolesMap);
2307         break;
2308       }
2309     }
2310   }
2311
2312   // Out of all found holes find those which cannot be removed
2313   // by checking their connectivity to splits of other offset faces.
2314   // These are the faces, which will create uncovered holes if removed.
2315   const Standard_Integer aNbE = anEFHolesMap.Extent();
2316   for (Standard_Integer i = 1; i <= aNbE; ++i)
2317   {
2318     const TopoDS_Shape& anEdge = anEFHolesMap.FindKey(i);
2319     const TopTools_ListOfShape& aLFHoles = anEFHolesMap(i);
2320     // Check if the edge is outer for holes
2321     if (aLFHoles.Extent() != 1)
2322       continue;
2323
2324     const TopoDS_Shape& aFHole = aLFHoles.First();
2325     if (!theMFHoles.Contains(aFHole))
2326       // Already removed
2327       continue;
2328
2329     // Check if the edge is not outer for splits
2330     const TopTools_ListOfShape& aLSplits = anEFSplitsMap.FindFromKey(anEdge);
2331     if (aLSplits.Extent() == 1)
2332       continue;
2333
2334     // Check if edge is only connected to splits of the current offset face
2335     const TopTools_ListOfShape& aLFAll = theEFMap.FindFromKey(anEdge);
2336     if (aLFAll.Extent() == 2)
2337       // Avoid removal of the hole from the splits
2338       theMFHoles.Remove(aFHole);
2339   }
2340 }
2341
2342 //=======================================================================
2343 //function : GetAverageTangent
2344 //purpose  : Computes average tangent vector along the curve
2345 //=======================================================================
2346 gp_Vec GetAverageTangent(const TopoDS_Shape& theS,
2347                          const Standard_Integer theNbP)
2348 {
2349   gp_Vec aVA;
2350   TopExp_Explorer aExp(theS, TopAbs_EDGE);
2351   for (; aExp.More(); aExp.Next()) {
2352     const TopoDS_Edge& aE = *(TopoDS_Edge*)&aExp.Current();
2353     //
2354     Standard_Real aT1, aT2;
2355     const Handle(Geom_Curve)& aC = BRep_Tool::Curve(aE, aT1, aT2);
2356     //
2357     gp_Pnt aP;
2358     gp_Vec aV, aVSum;
2359     Standard_Real aT = aT1;
2360     Standard_Real aDt = (aT2 - aT1) / theNbP;
2361     while (aT <= aT2) {
2362       aC->D1(aT, aP, aV);
2363       aVSum += aV.Normalized();
2364       aT += aDt;
2365     }
2366     //
2367     if (aE.Orientation() == TopAbs_REVERSED) {
2368       aVSum.Reverse();
2369     }
2370     //
2371     aVA += aVSum;
2372   }
2373   return aVA;
2374 }
2375
2376 //=======================================================================
2377 //function : CheckInverted
2378 //purpose  : Checks if the edge has been inverted
2379 //=======================================================================
2380 Standard_Boolean CheckInverted(const TopoDS_Edge& theEIm,
2381                                const TopoDS_Face& theFOr,
2382                                const TopTools_DataMapOfShapeListOfShape& theOEImages,
2383                                const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
2384                                const TopTools_DataMapOfShapeListOfShape& theEdgesOrigins,
2385                                const TopTools_IndexedDataMapOfShapeListOfShape& theDMVE,
2386                                const TopTools_IndexedMapOfShape& theMEdges,
2387                                TopTools_MapOfShape& theMEInverted)
2388 {
2389   // It is necessary to compare the direction from first vertex
2390   // to the last vertex on the original edge with the
2391   // same direction on the new edge. If the directions
2392   // will be different - the edge has been inverted.
2393   //
2394   TopoDS_Vertex aVI1, aVI2; // vertices on the offset edge
2395   TopoDS_Vertex aVO1, aVO2; // vertices on the original edge
2396   //
2397   Standard_Integer i;
2398   // find vertices of the offset shape
2399   TopExp::Vertices(theEIm, aVI1, aVI2);
2400   //
2401   // find images
2402   TopTools_ListOfShape aLEImages;
2403   if (theOEOrigins.IsBound(theEIm)) {
2404     TopoDS_Wire anImages;
2405     BRep_Builder().MakeWire(anImages);
2406     //
2407     TopTools_MapOfShape aMImFence;
2408     const TopTools_ListOfShape& aLOffsetOr = theOEOrigins.Find(theEIm);
2409     TopTools_ListIteratorOfListOfShape aItOffset(aLOffsetOr);
2410     for (; aItOffset.More(); aItOffset.Next()) {
2411       const TopoDS_Shape& aEOffsetOr = aItOffset.Value();
2412       const TopTools_ListOfShape& aLImages = theOEImages.Find(aEOffsetOr);
2413       //
2414       TopTools_ListIteratorOfListOfShape aItImages(aLImages);
2415       for (; aItImages.More(); aItImages.Next()) {
2416         const TopoDS_Edge& anIm = *(TopoDS_Edge*)&aItImages.Value();
2417         if (theMEdges.Contains(anIm) && aMImFence.Add(anIm)) {
2418           BRep_Builder().Add(anImages, anIm);
2419           aLEImages.Append(anIm);
2420         }
2421       }
2422     }
2423     //
2424     // find alone vertices
2425     TopoDS_Vertex aVW1, aVW2;
2426     TopTools_IndexedDataMapOfShapeListOfShape aDMImVE;
2427     TopExp::MapShapesAndAncestors(anImages, TopAbs_VERTEX, TopAbs_EDGE, aDMImVE);
2428     //
2429     TopTools_ListOfShape aLVAlone;
2430     Standard_Integer aNb = aDMImVE.Extent();
2431     for (i = 1; i <= aNb; ++i) {
2432       const TopTools_ListOfShape& aLImE = aDMImVE(i);
2433       if (aLImE.Extent() == 1) {
2434         aLVAlone.Append(aDMImVE.FindKey(i));
2435       }
2436     }
2437     //
2438     if (aLVAlone.Extent() > 1) {
2439       aVW1 = *(TopoDS_Vertex*)&aLVAlone.First();
2440       aVW2 = *(TopoDS_Vertex*)&aLVAlone.Last();
2441       //
2442       // check distances
2443       const gp_Pnt& aPI1 = BRep_Tool::Pnt(aVI1);
2444       const gp_Pnt& aPW1 = BRep_Tool::Pnt(aVW1);
2445       const gp_Pnt& aPW2 = BRep_Tool::Pnt(aVW2);
2446       //
2447       Standard_Real aDist1 = aPI1.SquareDistance(aPW1);
2448       Standard_Real aDist2 = aPI1.SquareDistance(aPW2);
2449       //
2450       if (aDist1 < aDist2) {
2451         aVI1 = aVW1;
2452         aVI2 = aVW2;
2453       }
2454       else {
2455         aVI1 = aVW2;
2456         aVI2 = aVW1;
2457       }
2458     }
2459   }
2460   else {
2461     aLEImages.Append(theEIm);
2462   }
2463   //
2464   // Find edges connected to these vertices
2465   const TopTools_ListOfShape& aLIE1 = theDMVE.FindFromKey(aVI1);
2466   const TopTools_ListOfShape& aLIE2 = theDMVE.FindFromKey(aVI2);
2467   //
2468   // Find vertices on the original face corresponding to vertices on the offset edge
2469   //
2470   // find original edges for both lists
2471   TopTools_ListOfShape aLOE1, aLOE2;
2472   for (i = 0; i < 2; ++i) {
2473     const TopTools_ListOfShape& aLIE = !i ? aLIE1 : aLIE2;
2474     TopTools_ListOfShape& aLOE = !i ? aLOE1 : aLOE2;
2475     //
2476     TopTools_MapOfShape aMFence;
2477     //
2478     TopTools_ListIteratorOfListOfShape aItLIE(aLIE);
2479     for (; aItLIE.More(); aItLIE.Next()) {
2480       const TopoDS_Shape& aEI = aItLIE.Value();
2481       if (theEdgesOrigins.IsBound(aEI)) {
2482         const TopTools_ListOfShape& aLEOrigins = theEdgesOrigins.Find(aEI);
2483         //
2484         TopTools_ListIteratorOfListOfShape aItLOE(aLEOrigins);
2485         for (; aItLOE.More(); aItLOE.Next()) {
2486           const TopoDS_Shape& aEO = aItLOE.Value();
2487           if (aEO.ShapeType() == TopAbs_EDGE && aMFence.Add(aEO)) {
2488             TopoDS_Shape aEOin;
2489             if (FindShape(aEO, theFOr, NULL, aEOin)) {
2490               AppendToList(aLOE, aEO);
2491             }
2492           }
2493         }
2494       }
2495     }
2496   }
2497   //
2498   if (aLOE1.Extent() < 2 || aLOE2.Extent() < 2) {
2499     return Standard_False;
2500   }
2501   //
2502   // find vertices common for all edges in the lists
2503   for (i = 0; i < 2; ++i) {
2504     const TopTools_ListOfShape& aLOE = !i ? aLOE1 : aLOE2;
2505     TopoDS_Vertex& aVO = !i ? aVO1 : aVO2;
2506     //
2507     const TopoDS_Shape& aEO = aLOE.First();
2508     TopExp_Explorer aExpV(aEO, TopAbs_VERTEX);
2509     for (; aExpV.More(); aExpV.Next()) {
2510       const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&aExpV.Current();
2511       //
2512       Standard_Boolean bVertValid = Standard_True;
2513       TopTools_ListIteratorOfListOfShape aItLOE(aLOE);
2514       for (aItLOE.Next(); aItLOE.More(); aItLOE.Next()) {
2515         const TopoDS_Shape& aEOx = aItLOE.Value();
2516         TopExp_Explorer aExpVx(aEOx, TopAbs_VERTEX);
2517         for (; aExpVx.More(); aExpVx.Next()) {
2518           const TopoDS_Shape& aVx = aExpVx.Current();
2519           if (aVx.IsSame(aV)) {
2520             break;
2521           }
2522         }
2523         //
2524         if (!aExpVx.More()) {
2525           bVertValid = Standard_False;
2526           break;
2527         }
2528       }
2529       //
2530       if (bVertValid) {
2531         aVO = aV;
2532         break;
2533       }
2534     }
2535   }
2536   //
2537   if (aVO1.IsNull() || aVO2.IsNull() || aVO1.IsSame(aVO2)) {
2538     return Standard_False;
2539   }
2540   //
2541   // check positions of the offset and original vertices
2542   const gp_Pnt& aPI1 = BRep_Tool::Pnt(aVI1);
2543   const gp_Pnt& aPI2 = BRep_Tool::Pnt(aVI2);
2544   const gp_Pnt& aPO1 = BRep_Tool::Pnt(aVO1);
2545   const gp_Pnt& aPO2 = BRep_Tool::Pnt(aVO2);
2546   //
2547   gp_Vec aVI(aPI1, aPI2);
2548   gp_Vec aVO(aPO1, aPO2);
2549   //
2550   Standard_Real anAngle = aVI.Angle(aVO);
2551   Standard_Boolean bInverted = Abs(anAngle - M_PI) < 1.e-4;
2552   if (bInverted) {
2553     TopTools_ListIteratorOfListOfShape aItLEIm(aLEImages);
2554     for (; aItLEIm.More(); aItLEIm.Next()) {
2555       const TopoDS_Shape& aEInvr = aItLEIm.Value();
2556       theMEInverted.Add(aEInvr);
2557     }
2558   }
2559   return bInverted;
2560 }
2561
2562 //=======================================================================
2563 //function : CheckInvertedBlock
2564 //purpose  : Checks if it is possible to remove the block containing
2565 //           inverted edges
2566 //=======================================================================
2567 Standard_Boolean CheckInvertedBlock(const TopoDS_Shape& theCB,
2568                                     const TopTools_ListOfShape& theLCBF,
2569                                     const TopTools_MapOfShape& theMEInverted,
2570                                     const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
2571                                     BRepOffset_DataMapOfShapeMapOfShape& theDMCBVInverted,
2572                                     BRepOffset_DataMapOfShapeMapOfShape& theDMCBVAll)
2573 {
2574   // For possible removal of the block:
2575   // 1. There should be more than just one face in the block
2576   if (theCB.NbChildren() < 2) {
2577     return Standard_False;
2578   }
2579   //
2580   // 2. The block should at least contain two connected inverted edges with
2581   //    different origins (not just two images/splits of the same edge)
2582   TopTools_MapOfShape aMECBInv;
2583   TopoDS_Compound aCECBInv;
2584   BRep_Builder().MakeCompound(aCECBInv);
2585   //
2586   TopExp_Explorer aExp(theCB, TopAbs_EDGE);
2587   for (; aExp.More(); aExp.Next()) {
2588     const TopoDS_Shape& aE = aExp.Current();
2589     if (theMEInverted.Contains(aE)) {
2590       if (aMECBInv.Add(aE)) {
2591         BRep_Builder().Add(aCECBInv, aE);
2592       }
2593     }
2594   }
2595   //
2596   if (aMECBInv.Extent() < 2) {
2597     return Standard_False;
2598   }
2599   //
2600   // check that the edges are connected and different
2601   TopTools_ListOfShape aLCBE;
2602   BOPTools_AlgoTools::MakeConnexityBlocks(aCECBInv, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
2603   //
2604   TopTools_ListIteratorOfListOfShape aItLCBE(aLCBE);
2605   for (; aItLCBE.More(); aItLCBE.Next()) {
2606     const TopoDS_Shape& aCBE = aItLCBE.Value();
2607     // count the unique edges in the block
2608     Standard_Integer aNbUnique = 0;
2609     TopTools_MapOfShape aMEOrigins;
2610     TopoDS_Iterator aItE(aCBE);
2611     for (; aItE.More(); aItE.Next()) {
2612       const TopoDS_Shape& aE = aItE.Value();
2613       const TopTools_ListOfShape *pLEOr = theOEOrigins.Seek(aE);
2614       if (!pLEOr) {
2615         aMEOrigins.Add(aE);
2616         ++aNbUnique;
2617         continue;
2618       }
2619       TopTools_ListIteratorOfListOfShape aItLEOr(*pLEOr);
2620       for (; aItLEOr.More(); aItLEOr.Next()) {
2621         const TopoDS_Shape& aEOr = aItLEOr.Value();
2622         if (aMEOrigins.Add(aEOr)) {
2623           ++aNbUnique;
2624         }
2625       }
2626     }
2627     //
2628     if (aNbUnique >= 2) {
2629       break;
2630     }
2631   }
2632   //
2633   if (!aItLCBE.More()) {
2634     return Standard_False;
2635   }
2636   //
2637   // 3. the block should not contain inverted edges which vertices
2638   //    are contained in other blocks
2639   //
2640   // collect vertices from inverted edges and compare them with
2641   // vertices from other blocks
2642   TopTools_MapOfShape* pMVInverted = theDMCBVInverted.ChangeSeek(theCB);
2643   TopTools_MapOfShape* pMVAll = theDMCBVAll.ChangeSeek(theCB);
2644   if (!pMVInverted) {
2645     pMVInverted = theDMCBVInverted.Bound(theCB, TopTools_MapOfShape());
2646     pMVAll = theDMCBVAll.Bound(theCB, TopTools_MapOfShape());
2647     //
2648     GetVerticesOnEdges(theCB, theMEInverted, *pMVInverted, *pMVAll);
2649   }
2650   //
2651   TopTools_ListIteratorOfListOfShape aItLCB1(theLCBF);
2652   for (; aItLCB1.More(); aItLCB1.Next()) {
2653     const TopoDS_Shape& aCB1 = aItLCB1.Value();
2654     if (aCB1.IsSame(theCB)) {
2655       continue;
2656     }
2657     //
2658     // collect vertices from inverted edges
2659     TopTools_MapOfShape* pMVInverted1 = theDMCBVInverted.ChangeSeek(aCB1);
2660     TopTools_MapOfShape* pMVAll1 = theDMCBVAll.ChangeSeek(aCB1);
2661     if (!pMVInverted1) {
2662       pMVInverted1 = theDMCBVInverted.Bound(aCB1, TopTools_MapOfShape());
2663       pMVAll1 = theDMCBVAll.Bound(aCB1, TopTools_MapOfShape());
2664       //
2665       GetVerticesOnEdges(aCB1, theMEInverted, *pMVInverted1, *pMVAll1);
2666     }
2667     //
2668     if (pMVInverted->HasIntersection(*pMVAll1)) {
2669       return Standard_False;
2670     }
2671   }
2672   //
2673   return Standard_True;
2674 }
2675
2676 //=======================================================================
2677 //function : GetVerticesOnEdges
2678 //purpose  : Get vertices from the given shape belonging to the given edges
2679 //=======================================================================
2680 void GetVerticesOnEdges(const TopoDS_Shape& theCB,
2681                         const TopTools_MapOfShape& theEdges,
2682                         TopTools_MapOfShape& theVerticesOnEdges,
2683                         TopTools_MapOfShape& theAllVertices)
2684 {
2685   TopExp_Explorer aExp(theCB, TopAbs_EDGE);
2686   for (; aExp.More(); aExp.Next()) {
2687     const TopoDS_Shape& aE = aExp.Current();
2688     Standard_Boolean bOnGivenEdge = theEdges.Contains(aE);
2689     for (TopoDS_Iterator aItV(aE); aItV.More(); aItV.Next()) {
2690       theAllVertices.Add(aItV.Value());
2691       if (bOnGivenEdge) {
2692         theVerticesOnEdges.Add(aItV.Value());
2693       }
2694     }
2695   }
2696 }
2697
2698 //=======================================================================
2699 //function : RemoveInvalidSplitsByInvertedEdges
2700 //purpose  : Looking for the invalid faces containing inverted edges
2701 //           that can be safely removed
2702 //=======================================================================
2703 void RemoveInvalidSplitsByInvertedEdges(const TopTools_MapOfShape& theMEInverted,
2704                                         const TopTools_DataMapOfShapeListOfShape& theOEOrigins,
2705                                         TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
2706                                         TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
2707                                         TopTools_IndexedMapOfShape& theMERemoved)
2708 {
2709   if (theMEInverted.IsEmpty()) {
2710     return;
2711   }
2712   //
2713   // check the faces on regularity, i.e. the splits of the same face
2714   // should not be connected only by vertex. Such irregular splits
2715   // will have to be rebuilt and cannot be removed.
2716   //
2717   BRep_Builder aBB;
2718   TopTools_IndexedMapOfShape aMEAvoid;
2719   TopTools_DataMapOfShapeListOfShape aDMVF;
2720   Standard_Integer aNb = theFImages.Extent(), i;
2721   for (i = 1; i <= aNb; ++i) {
2722     const TopTools_ListOfShape& aLFIm = theFImages(i);
2723     //
2724     TopoDS_Compound aCFIm;
2725     aBB.MakeCompound(aCFIm);
2726     //
2727     TopTools_DataMapOfShapeListOfShape aDMEF;
2728     TopTools_ListIteratorOfListOfShape aIt(aLFIm);
2729     for (; aIt.More(); aIt.Next()) {
2730       const TopoDS_Shape& aF = aIt.Value();
2731       aBB.Add(aCFIm, aF);
2732       //
2733       // make a map to use only outer edges
2734       TopExp_Explorer aExp(aF, TopAbs_EDGE);
2735       for (; aExp.More(); aExp.Next()) {
2736         const TopoDS_Shape& aE = aExp.Current();
2737         //
2738         TopTools_ListOfShape *pLF = aDMEF.ChangeSeek(aE);
2739         if (!pLF) {
2740           pLF = aDMEF.Bound(aE, TopTools_ListOfShape());
2741         }
2742         else {
2743           // internal edges should not be used
2744           aMEAvoid.Add(aE);
2745         }
2746         AppendToList(*pLF, aF);
2747       }
2748       //
2749       // fill connection map of the vertices of inverted edges to faces
2750       aExp.Init(aF, TopAbs_VERTEX);
2751       for (; aExp.More(); aExp.Next()) {
2752         const TopoDS_Shape& aV = aExp.Current();
2753         //
2754         TopTools_ListOfShape *pLF = aDMVF.ChangeSeek(aV);
2755         if (!pLF) {
2756           pLF = aDMVF.Bound(aV, TopTools_ListOfShape());
2757         }
2758         AppendToList(*pLF, aF);
2759       }
2760     }
2761     //
2762     // for the splits to be regular they should form only one block
2763     TopTools_ListOfShape aLCBF;
2764     BOPTools_AlgoTools::MakeConnexityBlocks(aCFIm, TopAbs_EDGE, TopAbs_FACE, aLCBF);
2765     if (aLCBF.Extent() == 1) {
2766       continue;
2767     }
2768     //
2769     // check if the inverted edges create the irregularity
2770     BRepOffset_DataMapOfShapeMapOfShape aDMCBVInverted, aDMCBVAll;
2771     //
2772     TopTools_ListIteratorOfListOfShape aItLCB(aLCBF);
2773     for (; aItLCB.More(); aItLCB.Next()) {
2774       const TopoDS_Shape& aCB = aItLCB.Value();
2775       //
2776       // check if it is possible to remove the block
2777       if (!CheckInvertedBlock(aCB, aLCBF, theMEInverted, theOEOrigins, aDMCBVInverted, aDMCBVAll)) {
2778         // non of the edges in this block should be removed
2779         TopExp::MapShapes(aCB, TopAbs_EDGE, aMEAvoid);
2780         continue;
2781       }
2782     }
2783   }
2784   //
2785   // all edges not included in aMEAvoid can be removed
2786   TopTools_MapOfShape aMERem;
2787   TopTools_MapIteratorOfMapOfShape aItM(theMEInverted);
2788   for (; aItM.More(); aItM.Next()) {
2789     const TopoDS_Shape& aE = aItM.Value();
2790     if (!aMEAvoid.Contains(aE)) {
2791       TopoDS_Iterator aIt(aE);
2792       for (; aIt.More(); aIt.Next()) {
2793         const TopoDS_Shape& aV = aIt.Value();
2794         const TopTools_ListOfShape *pLF = aDMVF.Seek(aV);
2795         if (pLF && (pLF->Extent() > 3)) {
2796           aMERem.Add(aE);
2797           break;
2798         }
2799       }
2800     }
2801   }
2802   //
2803   if (aMERem.IsEmpty()) {
2804     return;
2805   }
2806   //
2807   // all invalid faces containing these edges can be removed
2808   TopTools_IndexedDataMapOfShapeListOfShape aInvFaces;
2809   TopTools_MapOfShape aMFRem;
2810   TopTools_IndexedMapOfShape aMFToUpdate;
2811   aNb = theInvFaces.Extent();
2812   for (i = 1; i <= aNb; ++i) {
2813     const TopoDS_Shape& aF = theInvFaces.FindKey(i);
2814     TopTools_ListOfShape& aLFIm = theInvFaces(i);
2815     //
2816     TopTools_ListIteratorOfListOfShape aIt(aLFIm);
2817     for (; aIt.More(); ) {
2818       const TopoDS_Shape& aFIm = aIt.Value();
2819       //
2820       // to be removed the face should have at least two not connected
2821       // inverted edges
2822       TopoDS_Compound aCEInv;
2823       aBB.MakeCompound(aCEInv);
2824       TopExp_Explorer aExp(aFIm, TopAbs_EDGE);
2825       for (; aExp.More(); aExp.Next()) {
2826         const TopoDS_Shape& aE = aExp.Current();
2827         if (aMERem.Contains(aE)) {
2828           aBB.Add(aCEInv, aE);
2829         }
2830       }
2831       //
2832       // check connectivity
2833       TopTools_ListOfShape aLCBE;
2834       BOPTools_AlgoTools::MakeConnexityBlocks(aCEInv, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
2835       //
2836       if (aLCBE.Extent() >= 2) {
2837         aMFToUpdate.Add(aF);
2838         aMFRem.Add(aFIm);
2839         aLFIm.Remove(aIt);
2840       }
2841       else {
2842         aIt.Next();
2843       }
2844     }
2845     //
2846     if (aLFIm.Extent()) {
2847       aInvFaces.Add(aF, aLFIm);
2848     }
2849   }
2850   //
2851   if (aMFRem.IsEmpty()) {
2852     return;
2853   }
2854   //
2855   theInvFaces = aInvFaces;
2856   // remove from splits
2857   aNb = aMFToUpdate.Extent();
2858   for (i = 1; i <= aNb; ++i) {
2859     const TopoDS_Shape& aF = aMFToUpdate(i);
2860     TopTools_ListOfShape& aLFIm = theFImages.ChangeFromKey(aF);
2861     //
2862     TopTools_ListIteratorOfListOfShape aIt(aLFIm);
2863     for (; aIt.More(); ) {
2864       const TopoDS_Shape& aFIm = aIt.Value();
2865       if (aMFRem.Contains(aFIm)) {
2866         TopExp::MapShapes(aFIm, TopAbs_EDGE, theMERemoved);
2867         aLFIm.Remove(aIt);
2868       }
2869       else {
2870         aIt.Next();
2871       }
2872     }
2873   }
2874 }
2875
2876 //=======================================================================
2877 //function : RemoveInvalidSplitsFromValid
2878 //purpose  : Removing invalid splits of faces from valid
2879 //=======================================================================
2880 void RemoveInvalidSplitsFromValid(const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
2881                                   const TopTools_DataMapOfShapeShape& theArtInvFaces,
2882                                   const TopTools_MapOfShape& theMEInverted,
2883                                   const BRepOffset_DataMapOfShapeMapOfShape& theDMFMVIE,
2884                                   TopTools_IndexedDataMapOfShapeListOfShape& theFImages)
2885 {
2886   // Decide whether to remove the found invalid faces or not.
2887   // The procedure is the following:
2888   // 1. Make connexity blocks from invalid faces;
2889   // 2. Find free edges in this blocks;
2890   // 3. If all free edges are valid for the faces - remove block.
2891   //
2892   TopTools_MapOfShape aMFence, aMFToRem;
2893   TopoDS_Compound aCFInv;
2894   BRep_Builder aBB;
2895   aBB.MakeCompound(aCFInv);
2896   TopTools_ListIteratorOfListOfShape aItLF;
2897   //
2898   // make compound of invalid faces
2899   TopTools_DataMapOfShapeShape aDMIFOF;
2900   Standard_Integer i, aNb = theInvFaces.Extent();
2901   for (i = 1; i <= aNb; ++i) {
2902     const TopoDS_Shape& aF = theInvFaces.FindKey(i);
2903     // artificially invalid faces should not be removed
2904     if (theArtInvFaces.IsBound(aF)) {
2905       continue;
2906     }
2907     const TopTools_ListOfShape& aLFInv = theInvFaces(i);
2908     aItLF.Initialize(aLFInv);
2909     for (; aItLF.More(); aItLF.Next()) {
2910       const TopoDS_Shape& aFIm = aItLF.Value();
2911       if (aMFence.Add(aFIm)) {
2912         aBB.Add(aCFInv, aFIm);
2913         aDMIFOF.Bind(aFIm, aF);
2914       }
2915     }
2916   }
2917   //
2918   // make connexity blocks
2919   TopTools_ListOfShape aLCBInv;
2920   BOPTools_AlgoTools::MakeConnexityBlocks(aCFInv, TopAbs_EDGE, TopAbs_FACE, aLCBInv);
2921   //
2922   // analyze each block
2923   aItLF.Initialize(aLCBInv);
2924   for (; aItLF.More(); aItLF.Next()) {
2925     const TopoDS_Shape& aCB = aItLF.Value();
2926     //
2927     // if connexity block contains only one face - it should be removed;
2928     TopExp_Explorer aExp(aCB, TopAbs_FACE);
2929     aExp.Next();
2930     if (aExp.More()) {
2931       // check if there are valid images left
2932       aExp.Init(aCB, TopAbs_FACE);
2933       for (; aExp.More(); aExp.Next()) {
2934         const TopoDS_Shape& aFIm = aExp.Current();
2935         const TopoDS_Shape& aF = aDMIFOF.Find(aFIm);
2936         //
2937         const TopTools_ListOfShape& aLFIm = theFImages.FindFromKey(aF);
2938         const TopTools_ListOfShape& aLFInv = theInvFaces.FindFromKey(aF);
2939         //
2940         if (aLFIm.Extent() == aLFInv.Extent()) {
2941           break;
2942         }
2943       }
2944     }
2945     //
2946     if (!aExp.More()) {
2947       aExp.Init(aCB, TopAbs_FACE);
2948       for (; aExp.More(); aExp.Next()) {
2949         const TopoDS_Shape& aF = aExp.Current();
2950         aMFToRem.Add(aF);
2951       }
2952       continue;
2953     }
2954     //
2955     // remove faces connected by inverted edges
2956     TopTools_IndexedDataMapOfShapeListOfShape aDMEF;
2957     TopExp::MapShapesAndAncestors(aCB, TopAbs_EDGE, TopAbs_FACE, aDMEF);
2958     //
2959     TopTools_DataMapOfShapeListOfShape aDMFF;
2960     aExp.Init(aCB, TopAbs_FACE);
2961     for (; aExp.More(); aExp.Next()) {
2962       const TopoDS_Shape& aFCB = aExp.Current();
2963       const TopoDS_Shape& aF = aDMIFOF.Find (aFCB);
2964       TopTools_ListOfShape* pList = aDMFF.ChangeSeek (aF);
2965       if (!pList)
2966         pList = aDMFF.Bound (aF, TopTools_ListOfShape());
2967       pList->Append (aFCB);
2968     }
2969
2970     for (TopTools_DataMapOfShapeListOfShape::Iterator itM (aDMFF); itM.More(); itM.Next())
2971     {
2972       const TopoDS_Shape& aF = itM.Key();
2973       const TopTools_MapOfShape* pValidInverted = theDMFMVIE.Seek (aF);
2974
2975       // either remove all of these faces or none.
2976       const TopTools_ListOfShape& aLFCB = itM.Value();
2977       TopTools_ListOfShape::Iterator itL (aLFCB);
2978       for (; itL.More(); itL.Next())
2979       {
2980         const TopoDS_Shape& aFCB = itL.Value();
2981         TopExp_Explorer aExpE(aFCB, TopAbs_EDGE);
2982         for (; aExpE.More(); aExpE.Next()) {
2983           const TopoDS_Shape& aECB = aExpE.Current();
2984           if (pValidInverted && pValidInverted->Contains (aECB))
2985             break;
2986           if (aDMEF.FindFromKey(aECB).Extent() > 1)
2987           {
2988             if (!theMEInverted.Contains(aECB))
2989               break;
2990           }
2991         }
2992         if (!aExpE.More())
2993           // if one removed - remove all
2994           break;
2995       }
2996       if (itL.More())
2997       {
2998         for (itL.Initialize (aLFCB); itL.More(); itL.Next())
2999         {
3000           aMFToRem.Add (itL.Value());
3001         }
3002       }
3003     }
3004   }
3005   //
3006   if (aMFToRem.Extent()) {
3007     // remove invalid faces from images
3008     aNb = theInvFaces.Extent();
3009     for (i = 1; i <= aNb; ++i) {
3010       const TopoDS_Shape& aF = theInvFaces.FindKey(i);
3011       TopTools_ListOfShape& aLFImages = theFImages.ChangeFromKey(aF);
3012       aItLF.Initialize(aLFImages);
3013       for (; aItLF.More();) {
3014         const TopoDS_Shape& aFIm = aItLF.Value();
3015         if (aMFToRem.Contains(aFIm)) {
3016           aLFImages.Remove(aItLF);
3017         }
3018         else {
3019           aItLF.Next();
3020         }
3021       }
3022     }
3023   }
3024 }
3025
3026 //=======================================================================
3027 //function : RemoveInsideFaces
3028 //purpose  : Looking for the inside faces that can be safely removed
3029 //=======================================================================
3030 void RemoveInsideFaces(TopTools_IndexedDataMapOfShapeListOfShape& theFImages,
3031                        TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
3032                        const TopTools_DataMapOfShapeShape& theArtInvFaces,
3033                        const TopTools_IndexedMapOfShape& theInvEdges,
3034                        const TopTools_MapOfShape& theInvertedEdges,
3035                        const TopTools_ListOfShape& theInvertedFaces,
3036                        const TopTools_IndexedMapOfShape& theMFToCheckInt,
3037                        const TopTools_IndexedMapOfShape& theMFInvInHole,
3038                        const TopoDS_Shape& theFHoles,
3039                        TopTools_DataMapOfShapeListOfShape& theSSInterfs,
3040                        TopTools_IndexedMapOfShape& theMERemoved,
3041                        TopTools_IndexedMapOfShape& theMEInside,
3042                        TopoDS_Shape& theSolids)
3043 {
3044   TopTools_ListOfShape aLS;
3045   TopTools_MapOfShape aMFence;
3046   TopTools_IndexedMapOfShape aMFInv;
3047   TopTools_ListIteratorOfListOfShape aItLF;
3048   TopTools_DataMapOfShapeShape aDMFImF;
3049   //
3050   Standard_Integer i, aNb = theFImages.Extent();
3051   for (i = 1; i <= aNb; ++i) {
3052     const TopoDS_Shape& aF = theFImages.FindKey(i);
3053     // to avoid intersection of the splits of the same
3054     // offset faces among themselves make compound of the
3055     // splits and use it as one argument
3056     TopoDS_Compound aCFImi;
3057     BRep_Builder().MakeCompound(aCFImi);
3058     //
3059     for (Standard_Integer j = 0; j < 2; ++j) {
3060       const TopTools_ListOfShape* pLFSp = !j ? theInvFaces.Seek(aF) : &theFImages(i);
3061       if (!pLFSp) {
3062         continue;
3063       }
3064       //
3065       aItLF.Initialize(*pLFSp);
3066       for (; aItLF.More(); aItLF.Next()) {
3067         const TopoDS_Shape& aFIm = aItLF.Value();
3068         if (aMFence.Add(aFIm)) {
3069           BRep_Builder().Add(aCFImi, aFIm);
3070           aDMFImF.Bind(aFIm, aF);
3071           if (!j) {
3072             aMFInv.Add(aFIm);
3073           }
3074         }
3075       }
3076     }
3077     //
3078     aLS.Append(aCFImi);
3079   }
3080   //
3081   // to make the solids more complete add for intersection also the faces
3082   // consisting only of invalid edges and not included into splits
3083   aNb = theMFToCheckInt.Extent();
3084   for (i = 1; i <= aNb; ++i) {
3085     const TopoDS_Shape& aFSp = theMFToCheckInt(i);
3086     if (aMFence.Add(aFSp)) {
3087       aLS.Append(aFSp);
3088     }
3089   }
3090   //
3091   BOPAlgo_MakerVolume aMV;
3092   aMV.SetArguments(aLS);
3093   aMV.SetIntersect(Standard_True);
3094   aMV.Perform();
3095   if (aMV.HasErrors())
3096     return;
3097
3098   //
3099   // get shapes connection for using in the rebuilding process
3100   // for the cases in which some of the intersection left undetected
3101   ShapesConnections(theInvFaces, theInvEdges, aDMFImF, aMV, theSSInterfs);
3102   //
3103   // find faces to remove
3104   const TopoDS_Shape& aSols = aMV.Shape();
3105   //
3106   TopTools_IndexedDataMapOfShapeListOfShape aDMFS;
3107   TopExp::MapShapesAndAncestors(aSols, TopAbs_FACE, TopAbs_SOLID, aDMFS);
3108   //
3109   aNb = aDMFS.Extent();
3110   if (!aNb) {
3111     return;
3112   }
3113   //
3114   // To use the created solids for classifications, firstly, it is necessary
3115   // to check them on validity - the created solids should be complete,
3116   // i.e. all faces should be included.
3117   //
3118   TopTools_MapOfShape aMFToRem;
3119   // Check completeness
3120   if (aMV.HasDeleted()) {
3121     TopTools_IndexedMapOfShape aMEHoles;
3122     TopExp::MapShapes(theFHoles, TopAbs_EDGE, aMEHoles);
3123
3124     // Map edges of the solids to check the connectivity
3125     // of the removed invalid splits
3126     TopTools_IndexedMapOfShape aMESols;
3127     TopExp::MapShapes(aSols, TopAbs_EDGE, aMESols);
3128
3129     // perform additional check on faces
3130     aNb = theFImages.Extent();
3131     for (i = 1; i <= aNb; ++i) {
3132       const TopTools_ListOfShape& aLFIm = theFImages(i);
3133       if (aLFIm.IsEmpty()) {
3134         continue;
3135       }
3136
3137       const TopoDS_Shape& aF = theFImages.FindKey(i);
3138       Standard_Boolean bInvalid = theInvFaces.Contains(aF);
3139       // For invalid faces it is allowed to be at least connected
3140       // to the solids, otherwise the solids are considered as broken
3141       Standard_Boolean bConnected = Standard_False;
3142
3143       Standard_Boolean bFaceKept = Standard_False;
3144       aItLF.Initialize(aLFIm);
3145       for (; aItLF.More(); aItLF.Next()) {
3146         const TopoDS_Shape& aFIm = aItLF.Value();
3147         if (!aMV.IsDeleted(aFIm)) {
3148           bFaceKept = Standard_True;
3149           continue;
3150         }
3151         //
3152         TopExp_Explorer aExpE(aFIm, TopAbs_EDGE);
3153         for (; aExpE.More(); aExpE.Next()) {
3154           if (aMEHoles.Contains(aExpE.Current())) {
3155             bFaceKept = Standard_True;
3156             aMFToRem.Add(aFIm);
3157             break;
3158           }
3159           if (!bFaceKept && bInvalid && !bConnected)
3160             bConnected = aMESols.Contains(aExpE.Current());
3161         }
3162       }
3163       //
3164       if (!bFaceKept && !bConnected) {
3165         return;
3166       }
3167     }
3168   }
3169   //
3170   TopTools_IndexedMapOfShape aMEBoundary;
3171   aNb = aDMFS.Extent();
3172   for (i = 1; i <= aNb; ++i) {
3173     const TopoDS_Shape& aFIm = aDMFS.FindKey(i);
3174     const TopTools_ListOfShape& aLSol = aDMFS(i);
3175     if (aLSol.Extent() > 1) {
3176       aMFToRem.Add(aFIm);
3177     }
3178     else if (aFIm.Orientation() != TopAbs_INTERNAL) {
3179       TopExp::MapShapes(aFIm, TopAbs_EDGE, aMEBoundary);
3180     }
3181   }
3182
3183   // Tool for getting the splits of faces
3184   const TopTools_DataMapOfShapeListOfShape& aMVIms = aMV.Images();
3185
3186   // update invalid faces with images
3187   aNb = aMFInv.Extent();
3188   for (i = 1; i <= aNb; ++i) {
3189     const TopoDS_Shape& aFInv = aMFInv(i);
3190     TakeModified(aFInv, aMVIms, aMFInv);
3191   }
3192
3193   // Take into account the faces invalid by inverted edges
3194   for (TopTools_ListOfShape::Iterator itLF(theInvertedFaces); itLF.More(); itLF.Next())
3195     TakeModified(itLF.Value(), aMVIms, aMFInv);
3196
3197   // check if the invalid faces inside the holes are really invalid:
3198   // check its normal direction - if it has changed relatively the
3199   // original face the offset face is invalid and should be kept for rebuilding
3200   Standard_Integer aNbFH = theMFInvInHole.Extent();
3201   for (i = 1; i <= aNbFH; ++i) {
3202     const TopoDS_Shape& aFInv = theMFInvInHole(i);
3203     TopTools_ListOfShape aLFInvIm = aMV.Modified(aFInv);
3204     if (aLFInvIm.IsEmpty()) {
3205       aLFInvIm.Append(aFInv);
3206     }
3207     //
3208     const TopoDS_Shape *pFOffset = aDMFImF.Seek(aFInv);
3209     if (!pFOffset) {
3210       continue;
3211     }
3212     TopTools_ListIteratorOfListOfShape aItLFInv(aLFInvIm);
3213     for (; aItLFInv.More(); aItLFInv.Next()) {
3214       const TopoDS_Shape& aFInvIm = aItLFInv.Value();
3215       const TopTools_ListOfShape* pLSols = aDMFS.Seek(aFInvIm);
3216       if (!pLSols || pLSols->Extent() != 1) {
3217         continue;
3218       }
3219       //
3220       const TopoDS_Shape& aFSol = pLSols->First();
3221       //
3222       TopoDS_Shape aFx;
3223       if (!FindShape(aFInvIm, aFSol, NULL, aFx)) {
3224         continue;
3225       }
3226       //
3227       if (BRepOffset_Tool::CheckPlanesNormals(TopoDS::Face(aFx), TopoDS::Face(*pFOffset))) {
3228         // the normal direction has not changed, thus the face can be removed
3229         aMFToRem.Add(aFInvIm);
3230       }
3231     }
3232   }
3233   //
3234   TopoDS_Compound aSolids;
3235   BRep_Builder().MakeCompound(aSolids);
3236   TopTools_MapOfShape aMFKeep;
3237   //
3238   TopExp_Explorer aExpS(aSols, TopAbs_SOLID);
3239   for (; aExpS.More(); aExpS.Next()) {
3240     const TopoDS_Shape& aSol = aExpS.Current();
3241     //
3242     Standard_Boolean bAllInv(Standard_True), bAllRemoved(Standard_True);
3243
3244     for (TopExp_Explorer aExpF(aSol, TopAbs_FACE); aExpF.More(); aExpF.Next())
3245     {
3246       const TopoDS_Shape& aFS = aExpF.Current();
3247       //
3248       if (aFS.Orientation() == TopAbs_INTERNAL) {
3249         aMFToRem.Add(aFS);
3250         continue;
3251       }
3252
3253       if (aMFToRem.Contains(aFS))
3254         continue;
3255
3256       bAllRemoved = false;
3257       bAllInv &= aMFInv.Contains(aFS);
3258     }
3259     //
3260     if (bAllInv && !bAllRemoved) {
3261       // remove invalid faces but keep those that have already been marked for removal
3262       TopExp_Explorer aExpF(aSol, TopAbs_FACE);
3263       for (; aExpF.More(); aExpF.Next()) {
3264         const TopoDS_Shape& aFS = aExpF.Current();
3265         //
3266         if (aMFToRem.Contains(aFS)) {
3267           if (!aMFKeep.Add(aFS)) {
3268             aMFKeep.Remove(aFS);
3269           }
3270         }
3271         else {
3272           aMFToRem.Add(aFS);
3273         }
3274       }
3275     }
3276     else {
3277       BRep_Builder().Add(aSolids, aSol);
3278       theSolids = aSolids;
3279     }
3280   }
3281   //
3282   TopTools_MapIteratorOfMapOfShape aItM(aMFKeep);
3283   for (; aItM.More(); aItM.Next()) {
3284     aMFToRem.Remove(aItM.Value());
3285   }
3286
3287   // Remove the invalid hanging parts external to the solids
3288   RemoveHangingParts(aMV, aDMFImF, aMFInv, theInvEdges, theInvertedEdges, aMFToRem);
3289
3290   // Remove newly found internal and hanging faces
3291   RemoveValidSplits(aMFToRem, theFImages, aMV, theMERemoved);
3292   RemoveInvalidSplits(aMFToRem, theArtInvFaces, theInvEdges, theInvFaces, aMV, theMERemoved);
3293   //
3294   // Get inside faces from the removed ones comparing them with boundary edges
3295   aNb = theMERemoved.Extent();
3296   for (i = 1; i <= aNb; ++i) {
3297     const TopoDS_Shape& aE = theMERemoved(i);
3298     if (!aMEBoundary.Contains(aE)) {
3299       theMEInside.Add(aE);
3300     }
3301   }
3302 }
3303
3304 //=======================================================================
3305 //function : ShapesConnections
3306 //purpose  : Looking for the connections between faces not to miss
3307 //           some necessary intersection
3308 //=======================================================================
3309 void ShapesConnections(const TopTools_IndexedDataMapOfShapeListOfShape& theInvFaces,
3310                        const TopTools_IndexedMapOfShape& theInvEdges,
3311                        const TopTools_DataMapOfShapeShape& theDMFOr,
3312                        BOPAlgo_Builder& theBuilder,
3313                        TopTools_DataMapOfShapeListOfShape& theSSInterfs)
3314 {
3315   // update invalid edges with images and keep connection to original edge
3316   TopTools_DataMapOfShapeListOfShape aDMEOr;
3317   Standard_Integer aNb = theInvEdges.Extent();
3318   for (Standard_Integer i = 1; i <= aNb; ++i) {
3319     const TopoDS_Shape& aEInv = theInvEdges(i);
3320     const TopTools_ListOfShape& aLEIm = theBuilder.Modified(aEInv);
3321     if (aLEIm.IsEmpty()) {
3322       aDMEOr.Bound(aEInv, TopTools_ListOfShape())->Append(aEInv);
3323       continue;
3324     }
3325     //
3326     TopTools_ListIteratorOfListOfShape aItLEIm(aLEIm);
3327     for (; aItLEIm.More(); aItLEIm.Next()) {
3328       const TopoDS_Shape& aEIm = aItLEIm.Value();
3329       //
3330       TopTools_ListOfShape* pLEOr = aDMEOr.ChangeSeek(aEIm);
3331       if (!pLEOr) {
3332         pLEOr = aDMEOr.Bound(aEIm, TopTools_ListOfShape());
3333       }
3334       AppendToList(*pLEOr, aEInv);
3335     }
3336   }
3337   //
3338   // get shapes connections for using in the rebuilding process
3339   const BOPDS_PDS& pDS = theBuilder.PDS();
3340   // analyze all Face/Face intersections
3341   const BOPDS_VectorOfInterfFF& aFFs = pDS->InterfFF();
3342   Standard_Integer iInt, aNbFF = aFFs.Length();
3343   for (iInt = 0; iInt < aNbFF; ++iInt) {
3344     const BOPDS_InterfFF& aFF = aFFs(iInt);
3345     const BOPDS_VectorOfCurve& aVNC = aFF.Curves();
3346     Standard_Integer aNbC = aVNC.Length();
3347     if (!aNbC) {
3348       continue;
3349     }
3350     //
3351     const TopoDS_Shape& aFIm1 = pDS->Shape(aFF.Index1());
3352     const TopoDS_Shape& aFIm2 = pDS->Shape(aFF.Index2());
3353     //
3354     const TopoDS_Shape* pF1 = theDMFOr.Seek(aFIm1);
3355     const TopoDS_Shape* pF2 = theDMFOr.Seek(aFIm2);
3356     //
3357     if (!pF1 || !pF2) {
3358       continue;
3359     }
3360     //
3361     if (pF1->IsSame(*pF2)) {
3362       continue;
3363     }
3364     //
3365     Standard_Boolean bInv1 = theInvFaces.Contains(*pF1);
3366     Standard_Boolean bInv2 = theInvFaces.Contains(*pF2);
3367     //
3368     if (!bInv1 && !bInv2) {
3369       continue;
3370     }
3371     //
3372     // check if it is real Face/Face intersection
3373     TopTools_MapOfShape aMEInt;
3374     for (Standard_Integer iC = 0; iC < aNbC; ++iC) {
3375       const BOPDS_Curve& aNC = aVNC(iC);
3376       const BOPDS_ListOfPaveBlock& aLPB = aNC.PaveBlocks();
3377       BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
3378       for (; aItLPB.More(); aItLPB.Next()) {
3379         const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
3380         Standard_Integer nEInt;
3381         if (aPB->HasEdge(nEInt)) {
3382           const TopoDS_Shape& aEInt = pDS->Shape(nEInt);
3383           aMEInt.Add(aEInt);
3384         }
3385       }
3386     }
3387     //
3388     if (aMEInt.IsEmpty()) {
3389       continue;
3390     }
3391     //
3392     // check if invalid edges of the face are in the same splits with intersection edges
3393     for (Standard_Integer i = 0; i < 2; ++i) {
3394       if ((!i && !bInv1) || (i && !bInv2)) {
3395         continue;
3396       }
3397       //
3398       const TopoDS_Shape& aF = !i ? *pF1 : *pF2;
3399       const TopoDS_Shape& aFOp = !i ? *pF2 : *pF1;
3400       const TopoDS_Shape& aFIm = !i ? aFIm1 : aFIm2;
3401       //
3402       Standard_Boolean bFound = Standard_False;
3403       //
3404       TopTools_ListOfShape aLFIm = theBuilder.Modified(aFIm);
3405       if (aLFIm.IsEmpty()) {
3406         aLFIm.Append(aFIm);
3407       }
3408       //
3409       TopTools_ListIteratorOfListOfShape aItLFIm(aLFIm);
3410       for (; aItLFIm.More(); aItLFIm.Next()) {
3411         const TopoDS_Shape& aFImIm = aItLFIm.Value();
3412         //
3413         Standard_Boolean bInv(Standard_False), bInt(Standard_False);
3414         TopExp_Explorer aExpE(aFImIm, TopAbs_EDGE);
3415         for (; aExpE.More(); aExpE.Next()) {
3416           const TopoDS_Shape& aE = aExpE.Current();
3417           if (!bInv) {
3418             bInv = aDMEOr.IsBound(aE);
3419           }
3420           if (!bInt) {
3421             bInt = aMEInt.Contains(aE);
3422           }
3423           if (bInv && bInt) {
3424             break;
3425           }
3426         }
3427         //
3428         if (!bInt || !bInv) {
3429           continue;
3430         }
3431         //
3432         bFound = Standard_True;
3433         //
3434         // append opposite face to all invalid edges in the split
3435         aExpE.Init(aFImIm, TopAbs_EDGE);
3436         for (; aExpE.More(); aExpE.Next()) {
3437           const TopoDS_Shape& aE = aExpE.Current();
3438           const TopTools_ListOfShape* pLEOr = aDMEOr.Seek(aE);
3439           if (!pLEOr) {
3440             continue;
3441           }
3442           //
3443           TopTools_ListIteratorOfListOfShape aItLE(*pLEOr);
3444           for (; aItLE.More(); aItLE.Next()) {
3445             const TopoDS_Shape& aEOr = aItLE.Value();
3446             TopTools_ListOfShape *pLFE = theSSInterfs.ChangeSeek(aEOr);
3447             if (!pLFE) {
3448               pLFE = theSSInterfs.Bound(aEOr, TopTools_ListOfShape());
3449             }
3450             AppendToList(*pLFE, aFOp);
3451           }
3452         }
3453       }
3454       if (bFound) {
3455         // save connection between offset faces
3456         TopTools_ListOfShape *pLF = theSSInterfs.ChangeSeek(aF);
3457         if (!pLF) {
3458           pLF = theSSInterfs.Bound(aF, TopTools_ListOfShape());
3459         }
3460         AppendToList(*pLF, aFOp);
3461       }
3462     }
3463   }
3464 }
3465
3466 //=======================================================================
3467 //function : RemoveHangingParts
3468 //purpose  : Remove isolated invalid hanging parts
3469 //=======================================================================
3470 void RemoveHangingParts(const BOPAlgo_MakerVolume& theMV,
3471                         const TopTools_DataMapOfShapeShape& theDMFImF,
3472                         const TopTools_IndexedMapOfShape& theMFInv,
3473                         const TopTools_IndexedMapOfShape& theInvEdges,
3474                         const TopTools_MapOfShape& theInvertedEdges,
3475                         TopTools_MapOfShape& theMFToRem)
3476 {
3477   // Map the faces of the result solids to filter them from avoided faces
3478   TopTools_IndexedMapOfShape aMFS;
3479   TopExp::MapShapes(theMV.Shape(), TopAbs_FACE, aMFS);
3480
3481   BRep_Builder aBB;
3482   // Build compound of all faces not included into solids
3483   TopoDS_Compound aCFHangs;
3484   aBB.MakeCompound(aCFHangs);
3485
3486   // Tool for getting the splits of faces
3487   const TopTools_DataMapOfShapeListOfShape& aMVIms = theMV.Images();
3488
3489   TopTools_ListIteratorOfListOfShape aItLArgs(theMV.Arguments());
3490   for (; aItLArgs.More(); aItLArgs.Next())
3491   {
3492     TopExp_Explorer anExpF(aItLArgs.Value(), TopAbs_FACE);
3493     for (; anExpF.More(); anExpF.Next())
3494     {
3495       const TopoDS_Shape& aF = anExpF.Current();
3496       TakeModified(aF, aMVIms, aCFHangs, &aMFS);
3497     }
3498   }
3499
3500   // Make connexity blocks of all hanging parts and check that they are isolated
3501   TopTools_ListOfShape aLCBHangs;
3502   BOPTools_AlgoTools::MakeConnexityBlocks(aCFHangs, TopAbs_EDGE, TopAbs_FACE, aLCBHangs);
3503   if (aLCBHangs.IsEmpty())
3504     return;
3505
3506   // To be removed, the block should contain invalid splits of offset faces and should
3507   // meet one of the following conditions:
3508   // 1. The block should not be connected to any invalid parts (Faces or Edges)
3509   //    contained in solids;
3510   // 2. The block should be isolated from other faces, i.e. it should consist of
3511   //    the splits of the single offset face.
3512
3513   // Map the edges and vertices of the result solids to check connectivity
3514   // of the hanging blocks to invalid parts contained in solids
3515   TopTools_IndexedDataMapOfShapeListOfShape aDMEF, aDMVE;
3516   TopExp::MapShapesAndAncestors(theMV.Shape(), TopAbs_EDGE  , TopAbs_FACE, aDMEF);
3517   TopExp::MapShapesAndAncestors(theMV.Shape(), TopAbs_VERTEX, TopAbs_EDGE, aDMVE);
3518
3519   // Update invalid edges with intersection results
3520   TopTools_MapOfShape aMEInv;
3521   Standard_Integer i, aNbE = theInvEdges.Extent();
3522   for (i = 1; i <= aNbE; ++i)
3523     TakeModified(theInvEdges(i), aMVIms, aMEInv);
3524
3525   // Update inverted edges with intersection results
3526   TopTools_MapOfShape aMEInverted;
3527   for (TopTools_MapIteratorOfMapOfShape itM(theInvertedEdges); itM.More(); itM.Next())
3528     TakeModified(itM.Value(), aMVIms, aMEInverted);
3529
3530   // Tool for getting the origins of the splits
3531   const TopTools_DataMapOfShapeListOfShape& aMVOrs = theMV.Origins();
3532
3533   // Find hanging blocks to remove
3534   TopTools_ListOfShape aBlocksToRemove;
3535
3536   TopTools_ListIteratorOfListOfShape aItLCBH(aLCBHangs);
3537   for (; aItLCBH.More(); aItLCBH.Next())
3538   {
3539     const TopoDS_Shape& aCBH = aItLCBH.Value();
3540
3541     // Remove the block containing the inverted edges
3542     Standard_Boolean bHasInverted = Standard_False;
3543     TopExp_Explorer anExpE(aCBH, TopAbs_EDGE);
3544     for (; anExpE.More() && !bHasInverted; anExpE.Next())
3545     {
3546       const TopoDS_Shape& aE = anExpE.Current();
3547       bHasInverted = !aDMEF      .Contains(aE) &&
3548                       aMEInverted.Contains(aE);
3549     }
3550
3551     if (bHasInverted)
3552     {
3553       aBlocksToRemove.Append(aCBH);
3554       continue;
3555     }
3556
3557     // Check the block to contain invalid split
3558     Standard_Boolean bHasInvalidFace = Standard_False;
3559     // Check connectivity to invalid parts
3560     Standard_Boolean bIsConnected = Standard_False;
3561     TopTools_IndexedMapOfShape aBlockME;
3562     TopExp::MapShapes(aCBH, TopAbs_EDGE, aBlockME);
3563     // Map to collect all original faces
3564     TopTools_MapOfShape aMOffsetF;
3565
3566     TopExp_Explorer anExpF(aCBH, TopAbs_FACE);
3567     for (; anExpF.More(); anExpF.Next())
3568     {
3569       const TopoDS_Shape& aF = anExpF.Current();
3570       // Check block to contain invalid face
3571       if (!bHasInvalidFace)
3572         bHasInvalidFace = theMFInv.Contains(aF);
3573
3574       // Check block for connectivity to invalid parts
3575       if (!bIsConnected)
3576       {
3577         // check edges
3578         anExpE.Init(aF, TopAbs_EDGE);
3579         for (; anExpE.More() && !bIsConnected; anExpE.Next())
3580         {
3581           const TopoDS_Shape& aE = anExpE.Current();
3582           const TopTools_ListOfShape *pLF = aDMEF.Seek(aE);
3583           if (pLF)
3584           {
3585             TopTools_ListIteratorOfListOfShape aItLF(*pLF);
3586             for (; aItLF.More() && !bIsConnected; aItLF.Next())
3587               bIsConnected = theMFInv.Contains(aItLF.Value());
3588           }
3589         }
3590         // check vertices
3591         if (!bIsConnected)
3592         {
3593           TopExp_Explorer anExpV(aF, TopAbs_VERTEX);
3594           for (; anExpV.More() && !bIsConnected; anExpV.Next())
3595           {
3596             const TopoDS_Shape& aV = anExpV.Current();
3597             const TopTools_ListOfShape *pLE = aDMVE.Seek(aV);
3598             if (pLE)
3599             {
3600               TopTools_ListIteratorOfListOfShape aItLE(*pLE);
3601               for (; aItLE.More() && !bIsConnected; aItLE.Next())
3602                 bIsConnected = !aBlockME.Contains(aItLE.Value()) &&
3603                                 aMEInv  .Contains(aItLE.Value());
3604             }
3605           }
3606         }
3607       }
3608
3609       // Check block to be isolated
3610       const TopTools_ListOfShape* pLFOr = aMVOrs.Seek(aF);
3611       if (pLFOr)
3612       {
3613         TopTools_ListIteratorOfListOfShape aItLFOr(*pLFOr);
3614         for (; aItLFOr.More(); aItLFOr.Next())
3615         {
3616           const TopoDS_Shape* pFOffset = theDMFImF.Seek(aItLFOr.Value());
3617           if (pFOffset)
3618             aMOffsetF.Add(*pFOffset);
3619         }
3620       }
3621       else
3622       {
3623         const TopoDS_Shape* pFOffset = theDMFImF.Seek(aF);
3624         if (pFOffset)
3625           aMOffsetF.Add(*pFOffset);
3626       }
3627     }
3628
3629     Standard_Boolean bRemove = bHasInvalidFace &&
3630       (!bIsConnected || aMOffsetF.Extent() == 1);
3631
3632     if (bRemove)
3633       aBlocksToRemove.Append(aCBH);
3634   }
3635
3636   // remove the invalidated blocks
3637   aItLCBH.Initialize(aBlocksToRemove);
3638   for (; aItLCBH.More(); aItLCBH.Next())
3639   {
3640     const TopoDS_Shape& aCBH = aItLCBH.Value();
3641     TopExp_Explorer anExpF(aCBH, TopAbs_FACE);
3642     for (; anExpF.More(); anExpF.Next())
3643       theMFToRem.Add(anExpF.Current());
3644   }
3645 }
3646
3647 //=======================================================================
3648 //function : RemoveValidSplits
3649 //purpose  : Removing valid splits according to results of intersection
3650 //=======================================================================
3651 void RemoveValidSplits(const TopTools_MapOfShape& theSpRem,
3652                        TopTools_IndexedDataMapOfShapeListOfShape& theImages,
3653                        BOPAlgo_Builder& theGF,
3654                        TopTools_IndexedMapOfShape& theMERemoved)
3655 {
3656   Standard_Integer i, aNb = theImages.Extent();
3657   if (!aNb) {
3658     return;
3659   }
3660   //
3661   for (i = 1; i <= aNb; ++i) {
3662     TopTools_ListOfShape& aLSIm = theImages(i);
3663     TopTools_ListIteratorOfListOfShape aIt(aLSIm);
3664     for (; aIt.More(); ) {
3665       const TopoDS_Shape& aSIm = aIt.Value();
3666       if (theSpRem.Contains(aSIm)) {
3667         TopExp::MapShapes(aSIm, TopAbs_EDGE, theMERemoved);
3668         aLSIm.Remove(aIt);
3669         continue;
3670       }
3671       //
3672       // check if all its images are have to be removed
3673       const TopTools_ListOfShape& aLSImIm = theGF.Modified(aSIm);
3674       if (aLSImIm.Extent()) {
3675         Standard_Boolean bAllRem = Standard_True;
3676         TopTools_ListIteratorOfListOfShape aIt1(aLSImIm);
3677         for (; aIt1.More(); aIt1.Next()) {
3678           const TopoDS_Shape& aSImIm = aIt1.Value();
3679           if (theSpRem.Contains(aSImIm)) {
3680             TopExp::MapShapes(aSImIm, TopAbs_EDGE, theMERemoved);
3681           }
3682           else {
3683             bAllRem = Standard_False;
3684           }
3685         }
3686         //
3687         if (bAllRem) {
3688           TopExp::MapShapes(aSIm, TopAbs_EDGE, theMERemoved);
3689           aLSIm.Remove(aIt);
3690           continue;
3691         }
3692       }
3693       aIt.Next();
3694     }
3695   }
3696 }
3697
3698 //=======================================================================
3699 //function : RemoveInvalidSplits
3700 //purpose  : Removing invalid splits according to the results of intersection
3701 //=======================================================================
3702 void RemoveInvalidSplits(const TopTools_MapOfShape& theSpRem,
3703                          const TopTools_DataMapOfShapeShape& theArtInvFaces,
3704                          const TopTools_IndexedMapOfShape& theInvEdges,
3705                          TopTools_IndexedDataMapOfShapeListOfShape& theImages,
3706                          BOPAlgo_Builder& theGF,
3707                          TopTools_IndexedMapOfShape& theMERemoved)
3708 {
3709   Standard_Integer i, aNb = theImages.Extent();
3710   if (!aNb) {
3711     return;
3712   }
3713   //
3714   for (i = 1; i <= aNb; ++i) {
3715     const TopoDS_Shape& aS = theImages.FindKey(i);
3716     Standard_Boolean bArt = theArtInvFaces.IsBound(aS);
3717     //
3718     TopTools_ListOfShape& aLSIm = theImages(i);
3719     TopTools_ListIteratorOfListOfShape aIt(aLSIm);
3720     for (; aIt.More();) {
3721       const TopoDS_Shape& aSIm = aIt.Value();
3722       if (theSpRem.Contains(aSIm)) {
3723         TopExp::MapShapes(aSIm, TopAbs_EDGE, theMERemoved);
3724         aLSIm.Remove(aIt);
3725         continue;
3726       }
3727       //
3728       // check if all its images are have to be removed
3729       const TopTools_ListOfShape& aLSImIm = theGF.Modified(aSIm);
3730       if (aLSImIm.IsEmpty()) {
3731         aIt.Next();
3732         continue;
3733       }
3734       //
3735       Standard_Boolean bAllRem = Standard_True;
3736       TopTools_IndexedMapOfShape aMERemoved;
3737       TopTools_ListIteratorOfListOfShape aIt1(aLSImIm);
3738       for (; aIt1.More(); aIt1.Next()) {
3739         const TopoDS_Shape& aSImIm = aIt1.Value();
3740         if (theSpRem.Contains(aSImIm)) {
3741           TopExp::MapShapes(aSImIm, TopAbs_EDGE, aMERemoved);
3742         }
3743         else {
3744           bAllRem = Standard_False;
3745         }
3746       }
3747       //
3748       if (bAllRem) {
3749         aLSIm.Remove(aIt);
3750         continue;
3751       }
3752       //
3753       if (bArt) {
3754         aIt.Next();
3755         continue;
3756       }
3757       //
3758       // remove the face from invalid if all invalid edges of this face
3759       // have been marked for removal
3760       TopExp_Explorer aExpE(aSIm, TopAbs_EDGE);
3761       for (; aExpE.More(); aExpE.Next()) {
3762         const TopoDS_Shape& aEInv = aExpE.Current();
3763         if (theInvEdges.Contains(aEInv) && !aMERemoved.Contains(aEInv)) {
3764           break;
3765         }
3766       }
3767       if (!aExpE.More()) {
3768         TopExp::MapShapes(aSIm, TopAbs_EDGE, theMERemoved);
3769         aLSIm.Remove(aIt);
3770       }
3771       else {
3772         aIt.Next();
3773       }
3774     }
3775   }
3776 }
3777