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