Salome HOME
Mantis issue 0021465: EDF 2067 GEOM: Extrusion along a path leads to a self-intersect...
[modules/geom.git] / src / GEOMImpl / GEOMImpl_Block6Explorer.cxx
1 // Copyright (C) 2007-2011  CEA/DEN, EDF R&D, OPEN CASCADE
2 //
3 // Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
5 //
6 // This library is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU Lesser General Public
8 // License as published by the Free Software Foundation; either
9 // version 2.1 of the License.
10 //
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 // Lesser General Public License for more details.
15 //
16 // You should have received a copy of the GNU Lesser General Public
17 // License along with this library; if not, write to the Free Software
18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
19 //
20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
21
22 #include <Standard_Stream.hxx>
23
24 #include <GEOMImpl_Block6Explorer.hxx>
25
26 #include <ShHealOper_ShapeProcess.hxx>
27
28 #include "utilities.h"
29
30 #include <BRep_Tool.hxx>
31 #include <BRep_TFace.hxx>
32 #include <BRep_Builder.hxx>
33 #include <BRepLib.hxx>
34 #include <BRepLib_FindSurface.hxx>
35 #include <BRepTools.hxx>
36 #include <BRepTools_WireExplorer.hxx>
37 #include <BRepOffsetAPI_ThruSections.hxx>
38 #include <BRepOffsetAPI_MakeFilling.hxx>
39 #include <BRepCheck_Analyzer.hxx>
40 #include <BRepBuilderAPI_Copy.hxx>
41 #include <BRepBuilderAPI_MakeEdge.hxx>
42 #include <BRepBuilderAPI_MakeWire.hxx>
43 #include <BRepBuilderAPI_MakeFace.hxx>
44 #include <BRepBuilderAPI_Transform.hxx>
45
46 #include <TopAbs.hxx>
47 #include <TopoDS.hxx>
48 #include <TopoDS_Shape.hxx>
49 #include <TopoDS_Edge.hxx>
50 #include <TopoDS_Wire.hxx>
51 #include <TopoDS_Solid.hxx>
52 #include <TopExp.hxx>
53 #include <TopExp_Explorer.hxx>
54 #include <TopTools_MapOfShape.hxx>
55 #include <TopTools_ListOfShape.hxx>
56 #include <TopTools_ListIteratorOfListOfShape.hxx>
57 #include <TopTools_IndexedMapOfShape.hxx>
58 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
59
60 #include <Geom_Curve.hxx>
61 #include <Geom_TrimmedCurve.hxx>
62 #include <GeomFill_Generator.hxx>
63
64 #include <gce_MakePln.hxx>
65
66 #include <Precision.hxx>
67 #include <gp_Pnt.hxx>
68 #include <gp_Pln.hxx>
69 #include <TColgp_Array1OfPnt.hxx>
70
71 #include <StdFail_NotDone.hxx>
72 #include <Standard_NullObject.hxx>
73 #include <Standard_TypeMismatch.hxx>
74 #include <Standard_ConstructionError.hxx>
75 #include <Standard_NoSuchObject.hxx>
76
77 #define NBFACES 6
78 #define NBEDGES 12
79 #define NBVERTS 8
80
81 #define PLANAR_FACE_MAX_TOLERANCE 1e-06
82
83 static Standard_Integer mod4 (Standard_Integer nb)
84 {
85   if (nb <= 0) return nb + 4;
86   if (nb > 4)  return nb - 4;
87   return nb;
88 }
89
90 static Standard_Integer edge_id (const Standard_Integer theFaceID,
91                                  const Standard_Integer theEdgeNB)
92 {
93   static Standard_Integer edge_ids[NBFACES][4] = {
94     {  1,  2,  3,  4 },   // face 1
95     {  5,  6,  7,  8 },   // face 2
96     {  9,  5, 10,  1 },   // face 3
97     { 12,  7, 11,  3 },   // face 4
98     {  4, 12,  8,  9 },   // face 5
99     {  2, 11,  6, 10 } }; // face 6
100
101   return edge_ids[theFaceID - 1][theEdgeNB - 1];
102 }
103
104 static Standard_Integer side_edge_id (const Standard_Integer theEdgeNB)
105 {
106   static Standard_Integer side_edge_ids[4] = {9, 10, 11, 12};
107
108   return side_edge_ids[theEdgeNB - 1];
109 }
110
111 static Standard_Integer vertex_id (const Standard_Integer theFaceID,
112                                    const Standard_Integer theVertexNB)
113 {
114   static Standard_Integer vertex_ids[NBFACES][4] = {
115     { 1, 2, 3, 4 },   // face 1
116     { 5, 6, 7, 8 },   // face 2
117     { 1, 5, 6, 2 },   // face 3
118     { 4, 8, 7, 3 },   // face 4
119     { 1, 4, 8, 5 },   // face 5
120     { 2, 3, 7, 6 } }; // face 6
121
122   return vertex_ids[theFaceID - 1][theVertexNB - 1];
123 }
124
125 static Standard_Integer vertex_id_edge (const Standard_Integer theEdgeID, // [1,12]
126                                         const Standard_Integer theVertexNB) // [1,2]
127 {
128   static Standard_Integer vertex_ids_edge[NBEDGES][2] = {
129     {1, 2},   // edge 1
130     {2, 3},   // edge 2
131     {3, 4},   // edge 3
132     {4, 1},   // edge 4
133     {5, 6},   // edge 5
134     {6, 7},   // edge 6
135     {7, 8},   // edge 7
136     {8, 5},   // edge 8
137     {1, 5},   // edge 9
138     {2, 6},   // edge 10
139     {3, 7},   // edge 11
140     {4, 8} }; // edge 12
141
142   return vertex_ids_edge[theEdgeID - 1][theVertexNB - 1];
143 }
144
145 static Standard_Integer face_id_edges (const Standard_Integer theEdge1ID, // [1,12]
146                                        const Standard_Integer theEdge2ID) // [1,12]
147 {
148   static Standard_Integer face_ids_edges[NBEDGES][NBEDGES] = {
149     // 1  2  3  4  5  6  7  8  9  10 11 12
150     {  0, 1, 1, 1, 3, 0, 0, 0, 3, 3, 0, 0  },   // edge 1
151     {  1, 0, 1, 1, 0, 6, 0, 0, 0, 6, 6, 0  },   // edge 2
152     {  1, 1, 0, 1, 0, 0, 4, 0, 0, 0, 4, 4  },   // edge 3
153     {  1, 1, 1, 0, 0, 0, 0, 5, 5, 0, 0, 5  },   // edge 4
154     {  3, 0, 0, 0, 0, 2, 2, 2, 3, 3, 0, 0  },   // edge 5
155     {  0, 6, 0, 0, 2, 0, 2, 2, 0, 6, 6, 0  },   // edge 6
156     {  0, 0, 4, 0, 2, 2, 0, 2, 0, 0, 4, 4  },   // edge 7
157     {  0, 0, 0, 5, 2, 2, 2, 0, 5, 0, 0, 5  },   // edge 8
158     {  3, 0, 0, 5, 3, 0, 0, 5, 0, 3, 0, 5  },   // edge 9
159     {  3, 6, 0, 0, 3, 6, 0, 0, 3, 0, 6, 0  },   // edge 10
160     {  0, 6, 4, 0, 0, 6, 4, 0, 0, 6, 0, 4  },   // edge 11
161     {  0, 0, 4, 5, 0, 0, 4, 5, 5, 0, 4, 0  } }; // edge 12
162
163   return face_ids_edges[theEdge1ID - 1][theEdge2ID - 1];
164 }
165
166 static Standard_Integer edge_id_vertices (const Standard_Integer theVertex1ID, // [1,8]
167                                           const Standard_Integer theVertex2ID) // [1,8]
168 {
169   static Standard_Integer edge_ids_vertices[NBVERTS][NBVERTS] = {
170     // 1   2   3   4   5   6   7   8
171     {  0,  1,  0,  4,  9,  0,  0,  0},   // vertex 1
172     {  1,  0,  2,  0,  0, 10,  0,  0},   // vertex 2
173     {  0,  2,  0,  3,  0,  0, 11,  0},   // vertex 3
174     {  4,  0,  3,  0,  0,  0,  0, 12},   // vertex 4
175     {  9,  0,  0,  0,  0,  5,  0,  8},   // vertex 5
176     {  0, 10,  0,  0,  5,  0,  6,  0},   // vertex 6
177     {  0,  0, 11,  0,  0,  6,  0,  7},   // vertex 7
178     {  0,  0,  0, 12,  8,  0,  7,  0} }; // vertex 8
179
180   return edge_ids_vertices[theVertex1ID - 1][theVertex2ID - 1];
181 }
182
183 static Standard_Integer edge_id_faces (const Standard_Integer theFace1ID, // [1,6]
184                                        const Standard_Integer theFace2ID) // [1,6]
185 {
186   static Standard_Integer edge_ids_faces[NBFACES][NBFACES] = {
187     // 1   2   3   4   5   6
188     {  0,  0,  1,  3,  4,  2  },   // face 1
189     {  0,  0,  5,  7,  8,  6  },   // face 2
190     {  1,  5,  0,  0,  9, 10  },   // face 3
191     {  3,  7,  0,  0, 12, 11  },   // face 4
192     {  4,  8,  9, 12,  0,  0  },   // face 5
193     {  2,  6, 10, 11,  0,  0  } }; // face 6
194
195   return edge_ids_faces[theFace1ID - 1][theFace2ID - 1];
196 }
197
198 //=======================================================================
199 //function : GEOMImpl_Block6Explorer
200 //purpose  : Constructor
201 //=======================================================================
202 GEOMImpl_Block6Explorer::GEOMImpl_Block6Explorer ()
203      : myFaces(1,NBFACES), myEdges(1,NBEDGES), myVertices(1,NBVERTS)
204 {
205 }
206
207 //=======================================================================
208 //function : GetVertex
209 //purpose  :
210 //=======================================================================
211 TopoDS_Shape GEOMImpl_Block6Explorer::GetVertex (const Standard_Integer theVertexID)
212 {
213   TopoDS_Shape aNullShape;
214   if (theVertexID < 1 || theVertexID > NBVERTS) return aNullShape;
215   return myVertices(theVertexID);
216 }
217
218 //=======================================================================
219 //function : GetVertexID
220 //purpose  :
221 //=======================================================================
222 Standard_Integer GEOMImpl_Block6Explorer::GetVertexID (const TopoDS_Shape& theVertex)
223 {
224   for (Standard_Integer id = 1; id <= NBVERTS; id++) {
225     if (theVertex.IsSame(myVertices(id))) return id;
226   }
227   Standard_NoSuchObject::Raise("The Vertex does not belong to the Block");
228   return 0;
229 }
230
231 //=======================================================================
232 //function : GetVertexID
233 //purpose  :
234 //=======================================================================
235 Standard_Integer GEOMImpl_Block6Explorer::GetVertexID (const Standard_Integer theFaceID,
236                                                        const Standard_Integer theVertexNB)
237 {
238   return vertex_id(theFaceID, theVertexNB);
239 }
240
241 //=======================================================================
242 //function : GetVertexOnEdgeID
243 //purpose  :
244 //=======================================================================
245 Standard_Integer GEOMImpl_Block6Explorer::GetVertexOnEdgeID
246                                      (const Standard_Integer theEdgeID,
247                                       const Standard_Integer theVertexNB)
248 {
249   return vertex_id_edge(theEdgeID, theVertexNB);
250 }
251
252 //=======================================================================
253 //function : GetEdge
254 //purpose  :
255 //=======================================================================
256 TopoDS_Shape GEOMImpl_Block6Explorer::GetEdge (const Standard_Integer theEdgeID,
257                                                const Standard_Boolean doMake)
258 {
259   TopoDS_Shape aNullShape;
260   if (theEdgeID < 1 || theEdgeID > NBEDGES) return aNullShape;
261   if (myEdges(theEdgeID).IsNull() && doMake) {
262     // Create the required edge as a linear segment between
263     // corresponding vertices and put it in the Block's edges
264     BRepBuilderAPI_MakeEdge ME (TopoDS::Vertex(myVertices(vertex_id_edge(theEdgeID, 1))),
265                                 TopoDS::Vertex(myVertices(vertex_id_edge(theEdgeID, 2))));
266     if (!ME.IsDone()) {
267       Standard_ConstructionError::Raise("Edge construction failed");
268     }
269     myEdges(theEdgeID) = ME.Shape();
270   }
271
272   return myEdges(theEdgeID);
273 }
274
275 //=======================================================================
276 //function : GetEdgeID
277 //purpose  :
278 //=======================================================================
279 Standard_Integer GEOMImpl_Block6Explorer::GetEdgeID (const TopoDS_Shape& theEdge)
280 {
281   for (Standard_Integer id = 1; id <= NBEDGES; id++) {
282     if (theEdge.IsSame(myEdges(id))) return id;
283   }
284   Standard_NoSuchObject::Raise("The Edge does not belong to the Block");
285   return 0;
286 }
287
288 //=======================================================================
289 //function : GetEdgeID
290 //purpose  :
291 //=======================================================================
292 Standard_Integer GEOMImpl_Block6Explorer::GetEdgeID (const Standard_Integer theFaceID,
293                                                      const Standard_Integer theEdgeNB)
294 {
295   return edge_id(theFaceID, theEdgeNB);
296 }
297
298 //=======================================================================
299 //function : FindEdgeID
300 //purpose  :
301 //=======================================================================
302 Standard_Integer GEOMImpl_Block6Explorer::FindEdgeID (const Standard_Integer theVertex1ID,
303                                                       const Standard_Integer theVertex2ID)
304 {
305   return edge_id_vertices(theVertex1ID, theVertex2ID);
306 }
307
308 //=======================================================================
309 //function : FindCommonEdgeID
310 //purpose  :
311 //=======================================================================
312 Standard_Integer GEOMImpl_Block6Explorer::FindCommonEdgeID
313                                       (const Standard_Integer theFace1ID,
314                                        const Standard_Integer theFace2ID)
315 {
316   return edge_id_faces(theFace1ID, theFace2ID);
317 }
318
319 //=======================================================================
320 //function : GetFace
321 //purpose  :
322 //=======================================================================
323 TopoDS_Shape GEOMImpl_Block6Explorer::GetFace (const Standard_Integer theFaceID,
324                                                const Standard_Boolean doMake)
325 {
326   TopoDS_Shape aNullShape;
327   if (theFaceID < 1 || theFaceID > NBFACES) return aNullShape;
328
329   if (myFaces(theFaceID).IsNull() && doMake) {
330
331     // Create the required face between
332     // corresponding edges and put it in the Block's faces
333
334     TopoDS_Shape E1 = GetEdge(edge_id(theFaceID, 1), doMake);
335     TopoDS_Shape E2 = GetEdge(edge_id(theFaceID, 2), doMake);
336     TopoDS_Shape E3 = GetEdge(edge_id(theFaceID, 3), doMake);
337     TopoDS_Shape E4 = GetEdge(edge_id(theFaceID, 4), doMake);
338
339     BRepBuilderAPI_MakeWire MW (TopoDS::Edge(E1),
340                                 TopoDS::Edge(E2),
341                                 TopoDS::Edge(E3),
342                                 TopoDS::Edge(E4));
343     if (!MW.IsDone()) {
344       Standard_ConstructionError::Raise("Wire construction failed");
345     }
346     TopoDS_Shape aFace;
347     MakeFace(MW, Standard_False, aFace);
348     if (aFace.IsNull()) {
349       Standard_ConstructionError::Raise("Face construction failed");
350     }
351     myFaces(theFaceID) = aFace;
352   }
353
354   return myFaces(theFaceID);
355 }
356
357 //=======================================================================
358 //function : GetFaceID
359 //purpose  :
360 //=======================================================================
361 Standard_Integer GEOMImpl_Block6Explorer::GetFaceID (const TopoDS_Shape& theFace)
362 {
363   for (Standard_Integer id = 1; id <= NBFACES; id++) {
364     if (theFace.IsSame(myFaces(id))) return id;
365   }
366   Standard_NoSuchObject::Raise("The Face does not belong to the Block");
367   return 0;
368 }
369
370 //=======================================================================
371 //function : FindFaceID
372 //purpose  :
373 //=======================================================================
374 Standard_Integer GEOMImpl_Block6Explorer::FindFaceID (const Standard_Integer theEdge1ID,
375                                                       const Standard_Integer theEdge2ID)
376 {
377   return face_id_edges(theEdge1ID, theEdge2ID);
378 }
379
380 //=======================================================================
381 //function : GetOppositeFaceID
382 //purpose  :
383 //=======================================================================
384 Standard_Integer GEOMImpl_Block6Explorer::GetOppositeFaceID (const Standard_Integer theFaceID)
385 {
386   Standard_Integer opp_face_id[NBFACES + 1] = {
387     0,
388     2,  // to 1 face
389     1,  // to 2 face
390     4,  // to 3 face
391     3,  // to 4 face
392     6,  // to 5 face
393     5}; // to 6 face
394
395   return opp_face_id[theFaceID];
396 }
397
398 //=======================================================================
399 //function : IsSimilarFaces
400 //purpose  :
401 //=======================================================================
402 Standard_Boolean GEOMImpl_Block6Explorer::IsSimilarFaces (const Standard_Integer theFace1ID,
403                                                           const Standard_Integer theFace2ID,
404                                                           const gp_Trsf          theTransformation)
405 {
406   Standard_Integer common_edge_id = FindCommonEdgeID(theFace1ID, theFace2ID);
407
408   if (common_edge_id == 0) { // opposite faces
409     for (Standard_Integer id = 1; id <= 4; id++) {
410       TopoDS_Shape E1 = GetEdge(edge_id(theFace1ID, id));
411       TopoDS_Shape E2 = GetEdge(edge_id(theFace2ID, id));
412
413       BRepBuilderAPI_Transform aTrsf (E1, theTransformation, Standard_False);
414       if (!IsSimilarEdges(aTrsf.Shape(), E2))
415         return Standard_False;
416     }
417   } else { // the faces have common edge
418     TopTools_Array1OfShape aVerts1 (1,4);
419     TopTools_Array1OfShape aVerts2 (1,4);
420
421     Standard_Integer common_vertex1 = GetVertexOnEdgeID(common_edge_id, 1);
422     Standard_Integer common_vertex2 = GetVertexOnEdgeID(common_edge_id, 2);
423     aVerts1(1) = myVertices(common_vertex1);
424     aVerts1(2) = myVertices(common_vertex2);
425     aVerts2(1) = myVertices(common_vertex1);
426     aVerts2(2) = myVertices(common_vertex2);
427
428     Standard_Integer not_common_v11 = 0, not_common_v12 = 0;
429     Standard_Integer vnb, vid;
430     for (vnb = 1; vnb <= 4; vnb++) {
431       vid = GetVertexID(theFace1ID, vnb);
432       if (vid != common_vertex1 && FindEdgeID(vid, common_vertex1) == 0) {
433         not_common_v12 = vid;
434       } else {
435         if (vid != common_vertex2 && FindEdgeID(vid, common_vertex2) == 0) {
436           not_common_v11 = vid;
437         }
438       }
439     }
440
441     Standard_Integer not_common_v21 = 0, not_common_v22 = 0;
442     for (vnb = 1; vnb <= 4; vnb++) {
443       vid = GetVertexID(theFace2ID, vnb);
444       if (vid != common_vertex1 && FindEdgeID(vid, common_vertex1) == 0) {
445         not_common_v22 = vid;
446       } else {
447         if (vid != common_vertex2 && FindEdgeID(vid, common_vertex2) == 0) {
448           not_common_v21 = vid;
449         }
450       }
451     }
452     aVerts1(3) = myVertices(not_common_v11);
453     aVerts1(4) = myVertices(not_common_v12);
454     aVerts2(3) = myVertices(not_common_v21);
455     aVerts2(4) = myVertices(not_common_v22);
456
457     for (Standard_Integer id = 1; id <= 4; id++) {
458       BRepBuilderAPI_Transform aTrsf (aVerts1(id), theTransformation, Standard_False);
459       TopoDS_Vertex V1 = TopoDS::Vertex(aTrsf.Shape());
460       TopoDS_Vertex V2 = TopoDS::Vertex(aVerts2(id));
461       if (!BRepTools::Compare(V1, V2)) {
462         return Standard_False;
463       }
464     }
465   }
466
467   return Standard_True;
468 }
469
470 //============ Initialization methods ===================================
471
472 //=======================================================================
473 //function : InitByBlock
474 //purpose  :
475 //=======================================================================
476 void GEOMImpl_Block6Explorer::InitByBlock (const TopoDS_Shape& theBlock)
477 {
478   // 1. Find any one face of the block
479   TopExp_Explorer faces (theBlock, TopAbs_FACE);
480   if (!faces.More()) {
481     Standard_ConstructionError::Raise("The block has no faces");
482   }
483   TopoDS_Shape aFirstFace = faces.Current();
484
485   // 2. Store all elements of the block relatively aFirstFace
486   InitByBlockAndFace(theBlock, aFirstFace);
487 }
488
489 //=======================================================================
490 //function : InitByBlockAndFace
491 //purpose  :
492 //=======================================================================
493 void GEOMImpl_Block6Explorer::InitByBlockAndFace (const TopoDS_Shape& theBlock,
494                                                   const TopoDS_Shape& theFace)
495 {
496   myFaces(1) = theFace;
497
498   // 2. Get wire of the first face
499   TopExp_Explorer wires (myFaces(1), TopAbs_WIRE);
500   if (!wires.More()) {
501     Standard_ConstructionError::Raise("A face of the block has no wires");
502   }
503   TopoDS_Shape aWire = wires.Current();
504   wires.Next();
505   if (wires.More()) {
506     Standard_ConstructionError::Raise("A face of the block has more than one wires");
507   }
508
509   // 3. Explore wire to init edges and vertices of the first face
510   BRepTools_WireExplorer aWE (TopoDS::Wire(aWire), TopoDS::Face(myFaces(1)));
511   Standard_Integer nb = 1;
512   for (; aWE.More(); aWE.Next(), nb++) {
513     if (nb > 4) {
514       Standard_ConstructionError::Raise("A face of the block has more than four edges");
515     }
516     myEdges(edge_id(1, nb)) = aWE.Current();
517     myVertices(vertex_id(1, nb)) = aWE.CurrentVertex();
518   }
519   if (nb < 5) {
520     Standard_ConstructionError::Raise("A face of the block has less than four edges");
521   }
522
523   // 2. Store all other elements of the block
524   InitByBlockAndVertices (theBlock,
525                           myVertices(vertex_id(1,1)),
526                           myVertices(vertex_id(1,2)),
527                           myVertices(vertex_id(1,3)));
528 }
529
530 //=======================================================================
531 //function : InitByBlockAndEdges
532 //purpose  :
533 //=======================================================================
534 void GEOMImpl_Block6Explorer::InitByBlockAndEdges (const TopoDS_Shape& theBlock,
535                                                    const TopoDS_Shape& theEdge1,
536                                                    const TopoDS_Shape& theEdge3)
537 {
538   // 1. Store vertices and edges of the first face
539
540   // 1.1. Store two given edges
541   myEdges(edge_id(1, 1)) = theEdge1;
542   myEdges(edge_id(1, 3)) = theEdge3;
543
544   // 1.2. Find and store the first face
545   TopTools_IndexedDataMapOfShapeListOfShape MEF;
546   MapShapesAndAncestors(theBlock, TopAbs_EDGE, TopAbs_FACE, MEF);
547   if (MEF.Extent() != NBEDGES) {
548     Standard_TypeMismatch::Raise("Block has wrong number of edges");
549   }
550   const TopTools_ListOfShape& aFacesOfE1 = MEF.FindFromKey(theEdge1);
551   const TopTools_ListOfShape& aFacesOfE3 = MEF.FindFromKey(theEdge3);
552
553   Standard_Boolean isFound = Standard_False;
554   TopTools_ListIteratorOfListOfShape anIterF1 (aFacesOfE1);
555   for (; anIterF1.More() && !isFound; anIterF1.Next()) {
556
557     TopTools_ListIteratorOfListOfShape anIterF3 (aFacesOfE3);
558     for (; anIterF3.More() && !isFound; anIterF3.Next()) {
559
560       if (anIterF1.Value().IsSame(anIterF3.Value())) {
561         isFound = Standard_True;
562
563         // Store the face, defined by two opposite edges
564         myFaces(1) = anIterF1.Value();
565       }
566     }
567   }
568   if (!isFound) {
569     Standard_ConstructionError::Raise
570       ("Edges 1 and 2 do not belong to one face of the block");
571   }
572
573   // 1.3. Make vertices of the first edge the first and the
574   //      second vertices of the first face. Order is free.
575   TopoDS_Edge E = TopoDS::Edge(theEdge1);
576   TopoDS_Vertex V1, V2;
577   TopExp::Vertices(E, V1, V2, Standard_True);
578   myVertices(vertex_id(1,1)) = V1;
579   myVertices(vertex_id(1,2)) = V2;
580
581   // Init maps vertex->list_of_edges for the face
582   TopTools_IndexedDataMapOfShapeListOfShape M1;
583   MapShapesAndAncestors(myFaces(1), TopAbs_VERTEX, TopAbs_EDGE, M1);
584   if (M1.Extent() != 4) {
585     Standard_TypeMismatch::Raise("The first face of block has wrong number of vertices");
586   }
587
588   // 1.4. Find and store others elements of the first face
589
590   // edges of the first vertex
591   TopoDS_Shape E1_f = M1.FindFromKey(V1).First();
592   TopoDS_Shape E1_l = M1.FindFromKey(V1).Last();
593
594   if (E1_f.IsSame(theEdge1)) {
595     myEdges(edge_id(1, 4)) = E1_l;
596   } else {
597     myEdges(edge_id(1, 4)) = E1_f;
598   }
599
600   // fourth vertex
601   TopoDS_Edge E4 = TopoDS::Edge(myEdges(edge_id(1, 4)));
602   TopoDS_Vertex V41, V42;
603   TopExp::Vertices(E4, V41, V42, Standard_True);
604   if (V41.IsSame(V1)) {
605     myVertices(vertex_id(1,4)) = V42;
606   } else {
607     myVertices(vertex_id(1,4)) = V41;
608   }
609
610   // edges of the second vertex
611   TopoDS_Shape E2_f = M1.FindFromKey(V2).First();
612   TopoDS_Shape E2_l = M1.FindFromKey(V2).Last();
613
614   if (E2_f.IsSame(theEdge1)) {
615     myEdges(edge_id(1, 2)) = E2_l;
616   } else {
617     myEdges(edge_id(1, 2)) = E2_f;
618   }
619
620   // fird vertex
621   TopoDS_Edge E2 = TopoDS::Edge(myEdges(edge_id(1, 2)));
622   TopoDS_Vertex V21, V22;
623   TopExp::Vertices(E2, V21, V22, Standard_True);
624   if (V21.IsSame(V2)) {
625     myVertices(vertex_id(1,3)) = V22;
626   } else {
627     myVertices(vertex_id(1,3)) = V21;
628   }
629
630   // 2. Store all other elements of the block
631   InitByBlockAndVertices (theBlock,
632                           myVertices(vertex_id(1,1)),
633                           myVertices(vertex_id(1,2)),
634                           myVertices(vertex_id(1,3)));
635 }
636
637 //=======================================================================
638 //function : InitByBlockAndVertices
639 //purpose  :
640 //=======================================================================
641 void GEOMImpl_Block6Explorer::InitByBlockAndVertices (const TopoDS_Shape& theBlock,
642                                                       const TopoDS_Shape& theVertex1,
643                                                       const TopoDS_Shape& theVertex2,
644                                                       const TopoDS_Shape& theVertex3)
645 {
646   // Here we suppose, that vertices are ordered, i.e. exists edge between
647   // theVertex1 and theVertex2 and edge between theVertex2 and theVertex3
648
649   // 1. Store vertices and edges of the first face.
650   //    If the first face is initialized, it means, that this
651   //    method is called from another initialization method, and all
652   //    vertices and edges of the first face are also initialized
653   if (myFaces(1).IsNull()) {
654
655     // 1.1. Store first three vertices
656     myVertices(vertex_id(1, 1)) = theVertex1;
657     myVertices(vertex_id(1, 2)) = theVertex2;
658     myVertices(vertex_id(1, 3)) = theVertex3;
659
660     // 1.2. Find and store the first face
661     TopTools_IndexedDataMapOfShapeListOfShape MVF;
662     MapShapesAndAncestors(theBlock, TopAbs_VERTEX, TopAbs_FACE, MVF);
663     if (MVF.Extent() != NBVERTS) {
664       Standard_TypeMismatch::Raise("Block has wrong number of vertices");
665     }
666     const TopTools_ListOfShape& aFacesOfV1 = MVF.FindFromKey(theVertex1);
667     const TopTools_ListOfShape& aFacesOfV3 = MVF.FindFromKey(theVertex3);
668
669     Standard_Boolean isFound = Standard_False;
670     TopTools_ListIteratorOfListOfShape anIterF1 (aFacesOfV1);
671     for (; anIterF1.More() && !isFound; anIterF1.Next()) {
672
673       TopTools_ListIteratorOfListOfShape anIterF3 (aFacesOfV3);
674       for (; anIterF3.More() && !isFound; anIterF3.Next()) {
675
676         if (anIterF1.Value().IsSame(anIterF3.Value())) {
677           isFound = Standard_True;
678
679           // Store the face, defined by two opposite vertices
680           myFaces(1) = anIterF1.Value();
681         }
682       }
683     }
684     if (!isFound) {
685       Standard_ConstructionError::Raise
686         ("Vertices 1 and 3 do not belong to one face of the block");
687     }
688
689     // Init maps vertex->list_of_edges for the face
690     TopTools_IndexedDataMapOfShapeListOfShape M1;
691     MapShapesAndAncestors(myFaces(1), TopAbs_VERTEX, TopAbs_EDGE, M1);
692     if (M1.Extent() != 4) {
693       Standard_TypeMismatch::Raise("The first face of block has wrong number of vertices");
694     }
695
696     // 1.3. Find and store edges and last vertex of the first face
697     const TopTools_ListOfShape& anEdgesOfV1 = M1.FindFromKey(theVertex1);
698     const TopTools_ListOfShape& anEdgesOfV2 = M1.FindFromKey(theVertex2);
699     const TopTools_ListOfShape& anEdgesOfV3 = M1.FindFromKey(theVertex3);
700
701     TopTools_ListIteratorOfListOfShape anIterE2 (anEdgesOfV2);
702     for (; anIterE2.More(); anIterE2.Next()) {
703
704       TopTools_ListIteratorOfListOfShape anIterE1 (anEdgesOfV1);
705       for (; anIterE1.More(); anIterE1.Next()) {
706
707         if (anIterE1.Value().IsSame(anIterE2.Value())) {
708           // Store the first edge, defined by two vertices
709           myEdges(edge_id(1,1)) = anIterE1.Value();
710
711         } else {
712           // Store the last edge
713           myEdges(edge_id(1,4)) = anIterE1.Value();
714
715           // Find and store the last vertex
716           TopoDS_Edge E = TopoDS::Edge(myEdges(4));
717           TopoDS_Vertex V1, V2;
718           TopExp::Vertices(E, V1, V2, Standard_True);
719
720           if (V1.IsSame(theVertex1)) {
721             myVertices(vertex_id(1,4)) = V2;
722           } else {
723             myVertices(vertex_id(1,4)) = V1;
724           }
725         }
726       }
727
728       TopTools_ListIteratorOfListOfShape anIterE3 (anEdgesOfV3);
729       for (; anIterE3.More(); anIterE3.Next()) {
730
731         if (anIterE3.Value().IsSame(anIterE2.Value())) {
732           // Store the second edge, defined by two vertices
733           myEdges(edge_id(1,2)) = anIterE3.Value();
734
735         } else {
736           // Store the fird edge
737           myEdges(edge_id(1,3)) = anIterE3.Value();
738         }
739       }
740     }
741   }
742
743   // Init map vertex->list_of_edges for the block
744   TopTools_IndexedDataMapOfShapeListOfShape MB;
745   MapShapesAndAncestors(theBlock, TopAbs_VERTEX, TopAbs_EDGE, MB);
746   if (MB.Extent() != NBVERTS) {
747     Standard_TypeMismatch::Raise("Block has wrong number of vertices");
748   }
749
750   // 2. Store edges, linking the first face with the second one
751   //    and vertices of the second face
752   TopTools_IndexedMapOfShape aFaceEdges;
753   TopExp::MapShapes(myFaces(1), TopAbs_EDGE, aFaceEdges);
754
755   Standard_Integer i = 1;
756   for (; i <= 4; i++) {
757     // Get i-th vertex of the face 1
758     TopoDS_Shape Vi = myVertices(vertex_id(1, i));
759     if (!MB.Contains(Vi)) {
760       Standard_ConstructionError::Raise("Face does not belong to the block");
761     }
762
763     // Get list of block's edges, sharing this Vertex
764     const TopTools_ListOfShape& anEdgesOfVi = MB.FindFromKey(Vi);
765     TopTools_ListIteratorOfListOfShape anEdgesIter (anEdgesOfVi);
766
767     // Get Edge (from the List), not belonging to the face 1
768     Standard_Boolean isFound = Standard_False;
769     for (; anEdgesIter.More() && !isFound; anEdgesIter.Next()) {
770       if (!aFaceEdges.Contains(anEdgesIter.Value())) {
771         isFound = Standard_True;
772
773         // Store the linking edge
774         TopoDS_Shape aLinkEdge = anEdgesIter.Value();
775         myEdges(side_edge_id(i)) = aLinkEdge;
776
777         // Get another vertex of the linking edge
778         TopoDS_Edge E = TopoDS::Edge(aLinkEdge);
779         TopoDS_Vertex V1, V2;
780         TopExp::Vertices(E, V1, V2, Standard_True);
781
782         // Store the i-th vertex of the second (opposite to the first) face
783         if (V1.IsSame(Vi)) {
784           myVertices(vertex_id(2, i)) = V2;
785         } else {
786           myVertices(vertex_id(2, i)) = V1;
787         }
788       }
789     }
790   }
791
792   // 3. Store edges of the second (opposite to the first) face
793   for (i = 1; i <= 4; i++) {
794     // Get i-th and (i+1)-th vertices of the face 2
795     TopoDS_Shape Vi = myVertices(vertex_id(2, i));
796     TopoDS_Shape Vj = myVertices(vertex_id(2, mod4(i + 1)));
797
798     // Get list of block's edges, sharing Vi
799     const TopTools_ListOfShape& anEdgesOfVi = MB.FindFromKey(Vi);
800     // Get list of block's edges, sharing Vj
801     const TopTools_ListOfShape& anEdgesOfVj = MB.FindFromKey(Vj);
802
803     // Get Edge (from the List), linking this vertex with the next one
804     Standard_Boolean isFound = Standard_False;
805     TopTools_ListIteratorOfListOfShape anEdgesIteri (anEdgesOfVi);
806     for (; anEdgesIteri.More() && !isFound; anEdgesIteri.Next()) {
807
808       TopTools_ListIteratorOfListOfShape anEdgesIterj (anEdgesOfVj);
809       for (; anEdgesIterj.More() && !isFound; anEdgesIterj.Next()) {
810
811         if (anEdgesIteri.Value().IsSame(anEdgesIterj.Value())) {
812           isFound = Standard_True;
813
814           // Store the linking edge
815           myEdges(edge_id(2, i)) = anEdgesIteri.Value();
816         }
817       }
818     }
819   }
820
821   // 4. Store faces of the block
822   TopTools_IndexedDataMapOfShapeListOfShape MBE;
823   MapShapesAndAncestors(theBlock, TopAbs_EDGE, TopAbs_FACE, MBE);
824   if (MBE.Extent() != NBEDGES) {
825     Standard_TypeMismatch::Raise("Block has wrong number of edges");
826   }
827
828   for (i = 2; i <= NBFACES; i++) {
829     TopoDS_Shape Ei1 = myEdges(edge_id(i, 1));
830     TopoDS_Shape Ei2 = myEdges(edge_id(i, 2));
831     const TopTools_ListOfShape& aFacesOfEi1 = MBE.FindFromKey(Ei1);
832     const TopTools_ListOfShape& aFacesOfEi2 = MBE.FindFromKey(Ei2);
833
834     Standard_Boolean isFound = Standard_False;
835     TopTools_ListIteratorOfListOfShape anIterEi1 (aFacesOfEi1);
836     for (; anIterEi1.More() && !isFound; anIterEi1.Next()) {
837
838       TopTools_ListIteratorOfListOfShape anIterEi2 (aFacesOfEi2);
839       for (; anIterEi2.More() && !isFound; anIterEi2.Next()) {
840
841         if (anIterEi1.Value().IsSame(anIterEi2.Value())) {
842           isFound = Standard_True;
843
844           // Store the face, defined by two edges
845           myFaces(i) = anIterEi1.Value();
846         }
847       }
848     }
849   }
850 }
851
852 //=======================================================================
853 //function : InitByTwoFaces
854 //purpose  :
855 //=======================================================================
856 void GEOMImpl_Block6Explorer::InitByTwoFaces (const TopoDS_Shape& theFace1,
857                                               const TopoDS_Shape& theFace2)
858 {
859   if (theFace1.IsSame(theFace2)) {
860     Standard_ConstructionError::Raise("The faces must be different");
861   }
862
863   // Add two given faces in the structure
864   myFaces(1) = theFace1;
865   myFaces(2) = theFace2;
866
867   // Step 1. Order vertices (and edges)
868
869   // 1.1. Ordered vertices and edges of the first face we put in <myVertices>
870
871   // Get wire of the first face
872   TopExp_Explorer wires1 (myFaces(1), TopAbs_WIRE);
873   if (!wires1.More()) {
874     Standard_ConstructionError::Raise("A face for the block has no wires");
875   }
876   TopoDS_Shape aWire1 = wires1.Current();
877   wires1.Next();
878   if (wires1.More()) {
879     Standard_ConstructionError::Raise("A face for the block has more than one wire");
880   }
881
882   BRepTools_WireExplorer aWE1 (TopoDS::Wire(aWire1), TopoDS::Face(myFaces(1)));
883   Standard_Integer nb;
884   for (nb = 1; aWE1.More(); aWE1.Next(), nb++) {
885     if (nb > 4) {
886       Standard_ConstructionError::Raise("A face for the block has more than four edges");
887     }
888     myEdges(edge_id(1, nb)) = aWE1.Current();
889     myVertices(vertex_id(1, nb)) = aWE1.CurrentVertex();
890   }
891   if (nb < 5) {
892     Standard_ConstructionError::Raise("A face for the block has less than four edges");
893   }
894
895   // 1.2. Ordered vertices and edges of the second face we temporarily store
896   // in arrays, to find for them rigth location in <myVertices> on the Step 2.
897
898   // declare arrays
899   TopTools_Array1OfShape aVertis2(1,4); // ordered vertices of the second face
900   TopTools_Array1OfShape anEdges2(1,4); // anEdges2(i) links aVertis2(i) and aVertis2(i+1)
901
902   // Get wire of the second face
903   TopExp_Explorer wires2 (myFaces(2), TopAbs_WIRE);
904   if (!wires2.More()) {
905     Standard_ConstructionError::Raise("A face for the block has no wires");
906   }
907   TopoDS_Shape aWire2 = wires2.Current();
908   wires2.Next();
909   if (wires2.More()) {
910     Standard_ConstructionError::Raise("A face for the block has more than one wire");
911   }
912
913   BRepTools_WireExplorer aWE2 (TopoDS::Wire(aWire2), TopoDS::Face(myFaces(2)));
914   for (nb = 1; aWE2.More(); aWE2.Next(), nb++) {
915     if (nb > 4) {
916       Standard_ConstructionError::Raise("A face for the block has more than four edges");
917     }
918     anEdges2(nb) = aWE2.Current();
919     aVertis2(nb) = aWE2.CurrentVertex();
920   }
921   if (nb < 5) {
922     Standard_ConstructionError::Raise("A face for the block has less than four edges");
923   }
924
925   // Step 2. Find right place in <myVertices> for the <aVertis2>,
926   //         so as to minimize common length of linking edges
927   //         between face 1 and face 2.
928   //         Each linking edge (of four) will link vertices of the
929   //         faces 1 and 2 with equal local numbers.
930   // The right place is defined by:
931   //  - vertex <aVertis2(i_min)>, which will become the first vertex
932   //         of the second face <myVertices(vertex_id(2,1))>
933   //  - orientation of <aVertis2> relatively their future location
934   //         in <myVertices> (s_min = 1 if direct, s_min = -1 if reversed)
935   Standard_Integer i_min = 0, s_min = 0;
936
937   TColgp_Array1OfPnt aPnts1 (1,4); // points of the first face
938   aPnts1(1) = BRep_Tool::Pnt(TopoDS::Vertex(myVertices(vertex_id(1, 1))));
939   aPnts1(2) = BRep_Tool::Pnt(TopoDS::Vertex(myVertices(vertex_id(1, 2))));
940   aPnts1(3) = BRep_Tool::Pnt(TopoDS::Vertex(myVertices(vertex_id(1, 3))));
941   aPnts1(4) = BRep_Tool::Pnt(TopoDS::Vertex(myVertices(vertex_id(1, 4))));
942
943   TColgp_Array1OfPnt aPnts2 (1,4); // points of the second face
944   aPnts2(1) = BRep_Tool::Pnt(TopoDS::Vertex(aVertis2(1)));
945   aPnts2(2) = BRep_Tool::Pnt(TopoDS::Vertex(aVertis2(2)));
946   aPnts2(3) = BRep_Tool::Pnt(TopoDS::Vertex(aVertis2(3)));
947   aPnts2(4) = BRep_Tool::Pnt(TopoDS::Vertex(aVertis2(4)));
948
949   Standard_Real Dist_min = RealLast();
950   // try all possible locations to find the best (with minimum sum distance)
951   Standard_Integer i = 1;
952   for (; i <= 4; i++) {
953     // try direct orientation
954     Standard_Real Dist_plus = aPnts1(1).Distance(aPnts2(i)) +
955                               aPnts1(2).Distance(aPnts2(mod4(i + 1))) +
956                               aPnts1(3).Distance(aPnts2(mod4(i + 2))) +
957                               aPnts1(4).Distance(aPnts2(mod4(i + 3)));
958     if (Dist_plus < Dist_min) {
959       Dist_min = Dist_plus;
960       i_min = i;
961       s_min = 1;
962     }
963
964     // try reversed orientation
965     Standard_Real Dist_minus = aPnts1(1).Distance(aPnts2(i)) +
966                                aPnts1(2).Distance(aPnts2(mod4(i - 1))) +
967                                aPnts1(3).Distance(aPnts2(mod4(i - 2))) +
968                                aPnts1(4).Distance(aPnts2(mod4(i - 3)));
969     if (Dist_minus < Dist_min) {
970       Dist_min = Dist_minus;
971       i_min = i;
972       s_min = - 1;
973     }
974   }
975
976   // 3. Put vertices and edges of the second face to they
977   //    permanent location in <myVertices> and <myEdges>
978   for (i = 1; i <= 4; i++) {
979     Standard_Integer nb = mod4(i_min + s_min*(i - 1));
980
981     if (aPnts1(i).Distance(aPnts2(nb)) < Precision::Confusion()) {
982       Standard_ConstructionError::Raise("The faces are too close");
983     }
984
985     myVertices(vertex_id(2, i)) = aVertis2(nb);
986
987     if (s_min == -1) nb = mod4(nb - 1);
988     myEdges(edge_id(2, i)) = anEdges2(nb);
989   }
990
991   // check the wires closure
992   TopoDS_Wire wire1 = TopoDS::Wire(aWire1);
993   TopoDS_Wire wire2 = TopoDS::Wire(aWire2);
994   TopoDS_Vertex aV1, aV2;
995
996   TopExp::Vertices(wire1, aV1, aV2);
997   if ( !aV1.IsNull() && !aV2.IsNull() && aV1.IsSame(aV2) )
998     aWire1.Closed( true );
999
1000   TopExp::Vertices(wire2, aV1, aV2);
1001   if ( !aV1.IsNull() && !aV2.IsNull() && aV1.IsSame(aV2) )
1002     aWire2.Closed( true );
1003
1004   // 4. Generate side surface
1005   if (!aWire1.Closed() || !aWire2.Closed()) {
1006     // BRepOffsetAPI_ThruSections is not applicable on not closed wires
1007     GetFace(3, Standard_True);
1008     GetFace(4, Standard_True);
1009     GetFace(5, Standard_True);
1010     GetFace(6, Standard_True);
1011   } else {
1012     // try to build faces on native surfaces of edges or planar
1013     Standard_Boolean tryThru = Standard_False;
1014     for (Standard_Integer i = 3; i <= 6 && !tryThru; i++) {
1015       Standard_Boolean doMake = Standard_True;
1016       TopoDS_Shape E1 = GetEdge(edge_id(i, 1), doMake);
1017       TopoDS_Shape E2 = GetEdge(edge_id(i, 2), doMake);
1018       TopoDS_Shape E3 = GetEdge(edge_id(i, 3), doMake);
1019       TopoDS_Shape E4 = GetEdge(edge_id(i, 4), doMake);
1020
1021       BRepBuilderAPI_MakeWire MW (TopoDS::Edge(E1),
1022                                   TopoDS::Edge(E2),
1023                                   TopoDS::Edge(E3),
1024                                   TopoDS::Edge(E4));
1025       if (!MW.IsDone()) {
1026         Standard_ConstructionError::Raise("Wire construction failed");
1027       }
1028
1029       BRepBuilderAPI_MakeFace MF (MW, Standard_False);
1030       if (MF.IsDone()) {
1031         myFaces(i) = MF.Shape();
1032       } else {
1033         tryThru = Standard_True;
1034       }
1035     }
1036
1037     // Build side surface by ThruSections algorithm
1038     if (tryThru) {
1039       BRepOffsetAPI_ThruSections THS;
1040       THS.AddWire(TopoDS::Wire(aWire1));
1041       THS.AddWire(TopoDS::Wire(aWire2));
1042       THS.Build();
1043       if (!THS.IsDone()) {
1044         StdFail_NotDone::Raise("Side surface generation failed");
1045       }
1046       for (Standard_Integer i = 1; i <= 4; i++) {
1047         // fill face
1048         myFaces(i+2) = THS.GeneratedFace(myEdges(i));
1049
1050         // fill edge
1051         Standard_Integer ee = side_edge_id(i);
1052         TopTools_IndexedDataMapOfShapeListOfShape MVE;
1053         MapShapesAndAncestors(myFaces(i+2), TopAbs_VERTEX, TopAbs_EDGE, MVE);
1054         FindEdge(myEdges(ee),
1055                  myVertices(vertex_id_edge(ee, 1)),
1056                  myVertices(vertex_id_edge(ee, 2)),
1057                  MVE);
1058       }
1059     }
1060   }
1061 }
1062
1063 //=======================================================================
1064 //function : MapShapesAndAncestors
1065 //purpose  :
1066 //=======================================================================
1067 void GEOMImpl_Block6Explorer::MapShapesAndAncestors (const TopoDS_Shape& S,
1068                                                      const TopAbs_ShapeEnum TS,
1069                                                      const TopAbs_ShapeEnum TA,
1070                                                      TopTools_IndexedDataMapOfShapeListOfShape& M)
1071 {
1072   TopTools_ListOfShape empty;
1073   TopTools_MapOfShape mapA;
1074
1075   // visit ancestors
1076   TopExp_Explorer exa (S,TA);
1077   for (; exa.More(); exa.Next()) {
1078     // visit shapes
1079     const TopoDS_Shape& anc = exa.Current();
1080     if (mapA.Add(anc)) {
1081       TopExp_Explorer exs (anc,TS);
1082       TopTools_MapOfShape mapS;
1083       for (; exs.More(); exs.Next()) {
1084         if (mapS.Add(exs.Current())) {
1085           Standard_Integer index = M.FindIndex(exs.Current());
1086           if (index == 0) index = M.Add(exs.Current(),empty);
1087           M(index).Append(anc);
1088         }
1089       }
1090     }
1091   }
1092
1093   // visit shapes not under ancestors
1094   TopExp_Explorer ex (S,TS,TA);
1095   for (; ex.More(); ex.Next()) {
1096     Standard_Integer index = M.FindIndex(ex.Current());
1097     if (index == 0) index = M.Add(ex.Current(),empty);
1098   }
1099 }
1100
1101 //=======================================================================
1102 //function : IsSimilarEdges
1103 //purpose  :
1104 //=======================================================================
1105 Standard_Boolean GEOMImpl_Block6Explorer::IsSimilarEdges (const TopoDS_Shape& E1,
1106                                                           const TopoDS_Shape& E2)
1107 {
1108   TopoDS_Edge E1e = TopoDS::Edge(E1);
1109   TopoDS_Edge E2e = TopoDS::Edge(E2);
1110   TopoDS_Vertex V11, V12, V21, V22;
1111   TopExp::Vertices(E1e, V11, V12, Standard_True);
1112   TopExp::Vertices(E2e, V21, V22, Standard_True);
1113   if (BRepTools::Compare(V11, V21) && BRepTools::Compare(V12, V22))
1114     return Standard_True;
1115   if (BRepTools::Compare(V11, V22) && BRepTools::Compare(V12, V21))
1116     return Standard_True;
1117
1118   return Standard_False;
1119 }
1120
1121 //=======================================================================
1122 //function : FindEdge
1123 //purpose  :
1124 //=======================================================================
1125 Standard_Integer GEOMImpl_Block6Explorer::FindEdge
1126                    (TopoDS_Shape&       theResult,
1127                     const TopoDS_Shape& V1,
1128                     const TopoDS_Shape& V2,
1129                     const TopTools_IndexedDataMapOfShapeListOfShape& MVE,
1130                     const Standard_Boolean findAll)
1131 {
1132   Standard_Integer isFound = 0;
1133
1134   const TopTools_ListOfShape& anEdgesOfV1 = MVE.FindFromKey(V1);
1135   const TopTools_ListOfShape& anEdgesOfV2 = MVE.FindFromKey(V2);
1136
1137   TopTools_ListIteratorOfListOfShape it1 (anEdgesOfV1);
1138   for (; it1.More(); it1.Next()) {
1139     TopTools_ListIteratorOfListOfShape it2 (anEdgesOfV2);
1140     for (; it2.More(); it2.Next()) {
1141       if (it1.Value().IsSame(it2.Value())) {
1142         isFound++;
1143         theResult = it1.Value();
1144         if (!findAll) return isFound;
1145       }
1146     }
1147   }
1148
1149   return isFound;
1150 }
1151
1152 //=======================================================================
1153 //function : FindFace
1154 //purpose  :
1155 //=======================================================================
1156 Standard_Integer GEOMImpl_Block6Explorer::FindFace
1157                    (TopoDS_Shape&       theResult,
1158                     const TopoDS_Shape& V1,
1159                     const TopoDS_Shape& V2,
1160                     const TopoDS_Shape& V3,
1161                     const TopoDS_Shape& V4,
1162                     const TopTools_IndexedDataMapOfShapeListOfShape& MVF,
1163                     const Standard_Boolean findAll)
1164 {
1165   Standard_Integer isFound = Standard_False;
1166
1167   const TopTools_ListOfShape& aFacesOfV1 = MVF.FindFromKey(V1);
1168   const TopTools_ListOfShape& aFacesOfV2 = MVF.FindFromKey(V2);
1169   const TopTools_ListOfShape& aFacesOfV3 = MVF.FindFromKey(V3);
1170   const TopTools_ListOfShape& aFacesOfV4 = MVF.FindFromKey(V4);
1171
1172   TopTools_ListIteratorOfListOfShape it1 (aFacesOfV1);
1173   for (; it1.More(); it1.Next()) {
1174     TopTools_ListIteratorOfListOfShape it2 (aFacesOfV2);
1175     for (; it2.More(); it2.Next()) {
1176       if (it1.Value().IsSame(it2.Value())) {
1177         TopTools_ListIteratorOfListOfShape it3 (aFacesOfV3);
1178         for (; it3.More(); it3.Next()) {
1179           if (it1.Value().IsSame(it3.Value())) {
1180             TopTools_ListIteratorOfListOfShape it4 (aFacesOfV4);
1181             for (; it4.More(); it4.Next()) {
1182               if (it1.Value().IsSame(it4.Value())) {
1183                 isFound++;
1184                 theResult = it1.Value();
1185                 if (!findAll) return isFound;
1186               }
1187             }
1188           }
1189         }
1190       }
1191     }
1192   }
1193
1194   return isFound;
1195 }
1196
1197 //=======================================================================
1198 //function : MakeFace
1199 //purpose  :
1200 //=======================================================================
1201 TCollection_AsciiString GEOMImpl_Block6Explorer::MakeFace (const TopoDS_Wire&     theWire,
1202                                                            const Standard_Boolean isPlanarWanted,
1203                                                            TopoDS_Shape&          theResult)
1204 {
1205   if (!isPlanarWanted)
1206     return MakeAnyFace(theWire, theResult);
1207
1208   // Try to build a planar face.
1209
1210   // If required tolerance increase will be
1211   // higher than PLANAR_FACE_MAX_TOLERANCE,
1212   // we will try to build a non-planar face.
1213
1214   TCollection_AsciiString aWarning;
1215
1216   // Workaround for Mantis issue 0020956
1217
1218   // Count the number of points in the wire.
1219   // Collect the first three points.
1220   gp_Pnt p1, p2, p3;
1221   bool is3Pnts (false);
1222   bool p1set(false), p2set(false), p3set(false);
1223   BRepTools_WireExplorer wexpl (theWire);
1224   for (; wexpl.More(); wexpl.Next()) {
1225     if (!p1set) {
1226       p1set = true;
1227       p1 = BRep_Tool::Pnt(wexpl.CurrentVertex());
1228     }
1229     else if (!p2set) {
1230       p2set = true;
1231       p2 = BRep_Tool::Pnt(wexpl.CurrentVertex());
1232     }
1233     else if (!p3set) {
1234       p3set = true;
1235       is3Pnts = true;
1236       p3 = BRep_Tool::Pnt(wexpl.CurrentVertex());
1237     }
1238     else {
1239       is3Pnts = false;
1240       break;
1241     }
1242   }
1243
1244   // Construct a plane for the case of three points in the wire.
1245   gp_Pln plane;
1246   if (is3Pnts) {
1247     gce_MakePln mkPln (p1, p2, p3);
1248     if (mkPln.IsDone()) {
1249       plane = mkPln.Value();
1250     }
1251     else {
1252       is3Pnts = false;
1253     }
1254   }
1255
1256   // Construct a face based on the plane (in case of three points in the wire) or
1257   // allow MakeFace to build the plane itself (in case of the number of points is greater than 3).
1258   if (is3Pnts) {
1259     BRepBuilderAPI_MakeFace MK (plane, theWire, isPlanarWanted);
1260     if (MK.IsDone()) {
1261       theResult = MK.Shape();
1262       return aWarning;
1263     }
1264   }
1265   else {
1266     BRepBuilderAPI_MakeFace MK (theWire, isPlanarWanted);
1267     if (MK.IsDone()) {
1268       theResult = MK.Shape();
1269       return aWarning;
1270     }
1271   }
1272
1273   // try to update wire tolerances to build a planar face
1274
1275   // Find a deviation
1276   Standard_Real aToleranceReached, aTol;
1277   BRepLib_FindSurface aFS;
1278   aFS.Init(theWire, -1., isPlanarWanted);
1279   aToleranceReached = aFS.ToleranceReached();
1280   aTol = aFS.Tolerance();
1281
1282   if (!aFS.Found()) {
1283     aFS.Init(theWire, aToleranceReached, isPlanarWanted);
1284     if (!aFS.Found()) return aWarning;
1285     aToleranceReached = aFS.ToleranceReached();
1286     aTol = aFS.Tolerance();
1287   }
1288   aTol = Max(1.2 * aToleranceReached, aTol);
1289
1290   // Mantis issue 0021432: EDF GEOM: Faces with huge tolerance can be built in GEOM
1291   if (aTol > PLANAR_FACE_MAX_TOLERANCE) {
1292     aWarning = MakeAnyFace(theWire, theResult);
1293     if (aWarning.IsEmpty() && !theResult.IsNull())
1294       aWarning = "MAKE_FACE_TOLERANCE_TOO_BIG";
1295     return aWarning;
1296   }
1297
1298   // Copy the wire, bacause it can be updated with very-very big tolerance here
1299   BRepBuilderAPI_Copy aMC (theWire);
1300   if (!aMC.IsDone()) return aWarning;
1301   TopoDS_Wire aWire = TopoDS::Wire(aMC.Shape());
1302   // Update tolerances to <aTol>
1303   BRep_Builder B;
1304   for (TopExp_Explorer expE (aWire, TopAbs_EDGE); expE.More(); expE.Next()) {
1305     TopoDS_Edge anE = TopoDS::Edge(expE.Current());
1306     B.UpdateEdge(anE, aTol);
1307   }
1308   for (TopExp_Explorer expV (aWire, TopAbs_VERTEX); expV.More(); expV.Next()) {
1309     TopoDS_Vertex aV = TopoDS::Vertex(expV.Current());
1310     B.UpdateVertex(aV, aTol);
1311   }
1312   //BRepLib::UpdateTolerances(aWire);
1313   // Build face
1314   BRepBuilderAPI_MakeFace MK1 (aWire, isPlanarWanted);
1315   if (MK1.IsDone()) {
1316     theResult = MK1.Shape();
1317     // Mantis issue 0021432: EDF GEOM: Faces with huge tolerance can be built in GEOM
1318     //if (aTol > PLANAR_FACE_MAX_TOLERANCE)
1319     //  aWarning = "MAKE_FACE_TOLERANCE_TOO_BIG";
1320   }
1321
1322   return aWarning;
1323 }
1324
1325 //=======================================================================
1326 //function : MakeAnyFace
1327 //purpose  :
1328 //=======================================================================
1329 TCollection_AsciiString GEOMImpl_Block6Explorer::MakeAnyFace (const TopoDS_Wire& theWire,
1330                                                               TopoDS_Shape&      theResult)
1331 {
1332   TCollection_AsciiString aWarning;
1333
1334   // try to build a face on any surface under the edges of the wire
1335   BRepBuilderAPI_MakeFace MK (theWire, Standard_False);
1336   if (MK.IsDone()) {
1337     theResult = MK.Shape();
1338     return aWarning;
1339   }
1340
1341   // try to construct filling surface
1342   BRepOffsetAPI_MakeFilling MF;
1343
1344   Standard_Integer nbEdges = 0;
1345   BRepTools_WireExplorer aWE (theWire);
1346   for (; aWE.More(); aWE.Next(), nbEdges++) {
1347     MF.Add(TopoDS::Edge(aWE.Current()), GeomAbs_C0);
1348   }
1349
1350   MF.Build();
1351   if (!MF.IsDone()) {
1352     aWarning = "BRepOffsetAPI_MakeFilling failed";
1353     return aWarning;
1354   }
1355
1356   // Result of filling
1357   TopoDS_Shape aFace = MF.Shape();
1358
1359   // 12.04.2006 for PAL12149 begin
1360   Handle(Geom_Surface) aGS = BRep_Tool::Surface(TopoDS::Face(aFace));
1361   BRepBuilderAPI_MakeFace MK1 (aGS, theWire);
1362   if (MK1.IsDone()) {
1363     TopoDS_Shape aFace1 = MK1.Shape();
1364
1365     BRepCheck_Analyzer ana (aFace1, false);
1366     if (!ana.IsValid()) {
1367       TopoDS_Shape aFace2;
1368       ShHealOper_ShapeProcess aHealer;
1369       aHealer.Perform(aFace1, aFace2);
1370       if (aHealer.isDone())
1371         theResult = aFace2;
1372     }
1373   }
1374   // 12.04.2006 for PAL12149 end
1375
1376   if (theResult.IsNull()) { // try to deal with pure result of filling
1377     // Update tolerance
1378     Standard_Real aTol = MF.G0Error();
1379
1380     TColgp_Array1OfPnt aPnts (1,nbEdges); // points of the given wire
1381     BRepTools_WireExplorer aWE1 (theWire);
1382     Standard_Integer vi = 1;
1383     for (; aWE1.More() && vi <= nbEdges; aWE1.Next(), vi++) {
1384       aPnts(vi) = BRep_Tool::Pnt(TopoDS::Vertex(aWE1.CurrentVertex()));
1385     }
1386
1387     // Find maximum deviation in vertices
1388     TopExp_Explorer exp (aFace, TopAbs_VERTEX);
1389     TopTools_MapOfShape mapShape;
1390     for (; exp.More(); exp.Next()) {
1391       if (mapShape.Add(exp.Current())) {
1392         TopoDS_Vertex aV = TopoDS::Vertex(exp.Current());
1393         Standard_Real aTolV = BRep_Tool::Tolerance(aV);
1394         gp_Pnt aP = BRep_Tool::Pnt(aV);
1395         Standard_Real min_dist = aP.Distance(aPnts(1));
1396         for (vi = 2; vi <= nbEdges; vi++) {
1397           min_dist = Min(min_dist, aP.Distance(aPnts(vi)));
1398         }
1399         aTol = Max(aTol, aTolV);
1400         aTol = Max(aTol, min_dist);
1401       }
1402     }
1403
1404     if ((*((Handle(BRep_TFace)*)&aFace.TShape()))->Tolerance() < aTol) {
1405       (*((Handle(BRep_TFace)*)&aFace.TShape()))->Tolerance(aTol);
1406     }
1407     theResult = aFace;
1408   }
1409
1410   return aWarning;
1411 }