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