src/GEOMImpl/GEOMImpl_Block6Explorer.cxx

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