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