src/BRepLib/BRepLib_MakeWire_1.cxx

   1 // Created on: 1998-05-20
   2 // Created by: Didier PIFFAULT
   3 // Copyright (c) 1998-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17
  18 #include <BRep_Builder.hxx>
  19 #include <BRep_Tool.hxx>
  20 #include <BRepLib.hxx>
  21 #include <BRepLib_MakeWire.hxx>
  22 #include <gp_Pnt.hxx>
  23 #include <StdFail_NotDone.hxx>
  24 #include <TopExp.hxx>
  25 #include <TopExp_Explorer.hxx>
  26 #include <TopoDS.hxx>
  27 #include <TopoDS_Compound.hxx>
  28 #include <TopoDS_Edge.hxx>
  29 #include <TopoDS_Vertex.hxx>
  30 #include <TopoDS_Wire.hxx>
  31 #include <TopTools_DataMapOfShapeShape.hxx>
  32 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  33 #include <TopTools_ListIteratorOfListOfShape.hxx>
  34 #include <TopTools_ListOfShape.hxx>
  35 #include <TopTools_MapIteratorOfMapOfOrientedShape.hxx>
  36 #include <TopTools_MapIteratorOfMapOfShape.hxx>
  37 #include <TopTools_MapOfOrientedShape.hxx>
  38 #include <TopTools_MapOfShape.hxx>
  39 #include <NCollection_UBTreeFiller.hxx>
  40 #include <BRepBndLib.hxx>
  41 #include <BRepLib_MakeVertex.hxx>
  42
  43 //=======================================================================
  44 //function : Add
  45 //purpose  : Add the list of edges to the current wire
  46 //=======================================================================
  47 void  BRepLib_MakeWire::Add(const TopTools_ListOfShape& L)
  48 {
  49   myError = BRepLib_WireDone;
  50   Standard_Integer aLSize = 0;
  51   Standard_Integer aRefSize = L.Size();
  52   if (!L.IsEmpty())
  53   {
  54     ///
  55     NCollection_List<NCollection_List<TopoDS_Vertex>> aGrVL;
  56
  57     TopTools_IndexedDataMapOfShapeListOfShape aMapVE;
  58
  59     CollectCoincidentVertices(L, aGrVL);
  60
  61     TopTools_DataMapOfShapeShape anO2NV;
  62
  63     CreateNewVertices(aGrVL, anO2NV);
  64
  65     TopTools_ListOfShape aNewEList;
  66
  67     CreateNewListOfEdges(L, anO2NV, aNewEList);
  68     ///
  69
  70     TopExp::MapShapesAndAncestors(myShape, TopAbs_VERTEX, TopAbs_EDGE, aMapVE);
  71
  72     TopTools_MapOfShape aProcessedEdges;
  73     TopExp_Explorer anExp;
  74
  75     TopTools_ListOfShape anActEdges, aNeighEdges;
  76
  77     if (myEdge.IsNull())
  78     {
  79       //take the first edge from the list and add it
  80       const TopoDS_Edge& aFE = TopoDS::Edge(aNewEList.First());
  81       Add(aFE);
  82       aProcessedEdges.Add(aFE);
  83       anActEdges.Append(aFE);
  84       aLSize++;
  85     }
  86     else
  87     {
  88       //existing edges are already connected
  89       for (anExp.Init(myShape, TopAbs_EDGE); anExp.More(); anExp.Next())
  90       {
  91         const TopoDS_Shape& aCSh = anExp.Current();
  92         aProcessedEdges.Add(aCSh);
  93         anActEdges.Append(aCSh);
  94       }
  95     }
  96
  97     TopTools_ListIteratorOfListOfShape anItL1, anItL2;
  98
  99     for (anItL1.Initialize(aNewEList); anItL1.More(); anItL1.Next())
 100       TopExp::MapShapesAndAncestors(anItL1.Value(), TopAbs_VERTEX, TopAbs_EDGE, aMapVE);
 101
 102     while (!anActEdges.IsEmpty())
 103     {
 104       anItL2.Initialize(anActEdges);
 105       for (;anItL2.More(); anItL2.Next())
 106       {
 107         const TopoDS_Shape& aCE = anItL2.Value();
 108         anExp.Init(aCE, TopAbs_VERTEX);
 109         for (;anExp.More(); anExp.Next())
 110         {
 111           const TopoDS_Shape& aCV = anExp.Current();
 112           for (anItL1.Initialize(aMapVE.FindFromKey(aCV)); anItL1.More(); anItL1.Next())
 113           {
 114             const TopoDS_Shape& aNE = anItL1.Value(); //neighbor edge
 115             if (!aProcessedEdges.Contains(aNE))
 116             {
 117               Add(TopoDS::Edge(aNE), Standard_False);
 118               aNeighEdges.Append(aNE);
 119               aProcessedEdges.Add(aNE);
 120               aLSize++;
 121             }
 122           }
 123         }
 124       }
 125       anActEdges.Clear();
 126       anActEdges.Append(aNeighEdges);
 127     }
 128   }
 129   if (aLSize == aRefSize)
 130     Done();
 131   else
 132   {
 133     NotDone();
 134     myError = BRepLib_DisconnectedWire;
 135   }
 136 }
 137
 138 //=======================================================================
 139 //function : Accept
 140 //purpose  :
 141 //=======================================================================
 142 Standard_Boolean BRepLib_MakeWire::BRepLib_BndBoxVertexSelector::
 143   Accept (const Standard_Integer& theObj)
 144 {
 145   if (theObj > myMapOfShape.Extent())
 146     return Standard_False;
 147
 148   const TopoDS_Vertex& aV = TopoDS::Vertex(myMapOfShape(theObj));
 149
 150   if (theObj == myVInd)
 151     return Standard_False;
 152
 153   gp_Pnt aVPnt = BRep_Tool::Pnt(aV);
 154
 155   Standard_Real aTolV = BRep_Tool::Tolerance(aV);
 156
 157   Standard_Real aL = myP.SquareDistance(aVPnt);
 158   Standard_Real aSTol = aTolV + myTolP;
 159   aSTol *= aSTol;
 160
 161   if (aL <= aSTol)
 162   {
 163     myResultInd.Append(theObj);
 164     return Standard_True;
 165   }
 166
 167   return Standard_False;
 168 }
 169
 170 //=======================================================================
 171 //function : SetCurrentVertex
 172 //purpose  :
 173 //=======================================================================
 174 void BRepLib_MakeWire::BRepLib_BndBoxVertexSelector::
 175   SetCurrentVertex (const gp_Pnt& theP, Standard_Real theTol,
 176                     Standard_Integer theVInd)
 177 {
 178   myP = theP;
 179   myVBox.Add(myP);
 180   myVBox.Enlarge(theTol);
 181   myTolP = theTol;
 182   myVInd = theVInd;
 183 }
 184
 185 //=======================================================================
 186 //function : CollectCoincidentVertices
 187 //purpose  :
 188 //=======================================================================
 189 void BRepLib_MakeWire::CollectCoincidentVertices(const TopTools_ListOfShape& theL,
 190   NCollection_List<NCollection_List<TopoDS_Vertex>>& theGrVL)
 191 {
 192   TopTools_IndexedMapOfShape anAllV;
 193   TopTools_IndexedDataMapOfShapeListOfShape aMV2EL;
 194
 195   TopExp::MapShapes(myShape, TopAbs_VERTEX, anAllV);
 196
 197   TopTools_ListIteratorOfListOfShape anItL(theL);
 198   for (; anItL.More(); anItL.Next())
 199     TopExp::MapShapes(anItL.Value(), TopAbs_VERTEX, anAllV);
 200
 201   //aV2CV : vertex <-> its coincident vertices
 202   NCollection_DataMap<TopoDS_Vertex, NCollection_Map<TopoDS_Vertex>> aV2CV;
 203   NCollection_UBTree <Standard_Integer, Bnd_Box> aTree;
 204   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller (aTree);
 205   NCollection_Map<TopoDS_Vertex> aNonGroupedV;
 206
 207   /// add vertices from anAllV to treefiller
 208   for (Standard_Integer i = 1; i <= anAllV.Extent(); i++)
 209   {
 210     const TopoDS_Shape& aSh = anAllV(i);
 211     Bnd_Box aBB;
 212     BRepBndLib::Add(aSh, aBB);
 213     aTreeFiller.Add(i, aBB);
 214   }
 215
 216   aTreeFiller.Fill();
 217   BRepLib_BndBoxVertexSelector aSelector(anAllV);
 218
 219   Standard_Integer aNbColl = 0;
 220   NCollection_List<Standard_Integer>::Iterator itI;
 221   for (Standard_Integer i = 1; i <= anAllV.Extent(); i++ )
 222   {
 223     const TopoDS_Vertex& aV = TopoDS::Vertex(anAllV(i));
 224     if (myVertices.Contains(aV))
 225       continue;
 226     aSelector.SetCurrentVertex(BRep_Tool::Pnt(aV), BRep_Tool::Tolerance(aV), i );
 227     aNbColl = aTree.Select(aSelector);
 228     if (aNbColl > 0)
 229     {
 230       const NCollection_List<Standard_Integer>& aResInds = aSelector.GetResultInds();
 231       NCollection_Map<TopoDS_Vertex>* aVM =
 232         aV2CV.Bound(aV, NCollection_Map<TopoDS_Vertex>());
 233       for (itI.Initialize(aResInds); itI.More(); itI.Next() )
 234       {
 235         const TopoDS_Vertex& aCV = TopoDS::Vertex(anAllV(itI.Value()));
 236         aVM->Add(aCV);
 237         if (myVertices.Contains(aCV))
 238         {
 239           if (aV2CV.IsBound(aCV))
 240             aV2CV(aCV).Add(aV);
 241           else
 242           {
 243             aV2CV.Bound(aCV, NCollection_Map<TopoDS_Vertex>())->Add(aV);
 244             aNonGroupedV.Add(aCV);
 245           }
 246         }
 247       }
 248       if (!aVM->IsEmpty())
 249         aNonGroupedV.Add(aV); //vertexes to be grouped; store only coincident vertices
 250     }
 251     aSelector.ClearResInds();
 252   }
 253
 254
 255   /// group the coincident vertices
 256   NCollection_Map<TopoDS_Vertex>::Iterator itMV;
 257   NCollection_List<TopoDS_Vertex> aStartV, aCurrentV, anOneGrV;
 258   NCollection_List<TopoDS_Vertex>::Iterator itLV;
 259   Standard_Boolean IsStartNewGroup = Standard_True;
 260   while(!aNonGroupedV.IsEmpty() || !IsStartNewGroup)
 261   //exit only if there are no nongrouped vertices
 262   //and the last group are fully are constructed
 263   {
 264     if (IsStartNewGroup)
 265     {
 266       //start list of vertices is empty => append one from aNonGroupedV
 267       // and remove it from it (i.e. mark as grouped)
 268       itMV.Initialize(aNonGroupedV);
 269       const TopoDS_Vertex& aCurV = itMV.Value();
 270       aStartV.Append(aCurV);
 271       aNonGroupedV.Remove(aCurV);
 272     }
 273     itLV.Init(aStartV);
 274     for (;itLV.More();itLV.Next())
 275     {
 276       const TopoDS_Vertex& aSV = itLV.Value();
 277       anOneGrV.Append(aSV);
 278       itMV.Initialize(aV2CV(aSV));
 279       for (;itMV.More();itMV.Next())
 280       {
 281         const TopoDS_Vertex& aCV = itMV.Value();
 282         if (aNonGroupedV.Contains(aCV))
 283         {
 284           aCurrentV.Append(aCV);
 285           aNonGroupedV.Remove(aCV);
 286         }
 287       }
 288     }
 289     aStartV.Clear();
 290     aStartV.Append(aCurrentV);
 291     IsStartNewGroup = aStartV.IsEmpty();
 292     if (IsStartNewGroup && !anOneGrV.IsEmpty())
 293     {
 294       theGrVL.Append(anOneGrV);
 295       anOneGrV.Clear();
 296     }
 297   }
 298 }
 299
 300 //=======================================================================
 301 //function : CreateNewVertices
 302 //purpose  :
 303 //=======================================================================
 304 void BRepLib_MakeWire::CreateNewVertices(const NCollection_List<NCollection_List<TopoDS_Vertex>>& theGrVL,
 305                                          TopTools_DataMapOfShapeShape& theO2NV)
 306 {
 307   //map [old vertex => new vertex]
 308   //note that already existing shape (i.e. the original ones)
 309   //shouldnt be modified on the topological level
 310   NCollection_List<NCollection_List<TopoDS_Vertex>>::Iterator itLLV;
 311   NCollection_List<TopoDS_Vertex>::Iterator itLV;
 312   BRep_Builder aBB;
 313   itLLV.Init(theGrVL);
 314   for (;itLLV.More();itLLV.Next())
 315   {
 316     TopoDS_Vertex aNewV;
 317     NCollection_List<TopoDS_Shape> aValList;
 318     const NCollection_List<TopoDS_Vertex>& aVal = itLLV.Value();
 319     itLV.Initialize(aVal);
 320     Standard_Real aNewTol = 0;
 321     gp_Pnt aNewC;
 322     for (;itLV.More();itLV.Next())
 323     {
 324       const TopoDS_Vertex& aVV = itLV.Value();
 325       aValList.Append(aVV);
 326       if (myVertices.Contains(aVV))
 327         aNewV = aVV;
 328     }
 329     BRepLib::BoundingVertex(aValList, aNewC, aNewTol);
 330
 331     if (aNewV.IsNull())
 332     {
 333       //vertices from the original shape isnt found in this group
 334       //create the new vertex
 335       aNewV = BRepLib_MakeVertex(aNewC);
 336       aBB.UpdateVertex(aNewV, aNewTol);
 337     }
 338     else
 339       //update already existing vertex
 340       aBB.UpdateVertex(aNewV, gp_Pnt(aNewC), aNewTol);
 341
 342     //fill the map of old->new vertices
 343     itLV.Initialize(aVal);
 344     for (;itLV.More();itLV.Next())
 345     {
 346       const TopoDS_Vertex& aVV = itLV.Value();
 347       theO2NV.Bind(aVV, aNewV);
 348     }
 349   }
 350 }
 351
 352 //=======================================================================
 353 //function : CreateNewListOfEdges
 354 //purpose  :
 355 //=======================================================================
 356 void BRepLib_MakeWire::CreateNewListOfEdges(const TopTools_ListOfShape& theL,
 357   const TopTools_DataMapOfShapeShape& theO2NV,
 358   TopTools_ListOfShape& theNewEList)
 359 {
 360   ///create the new list (theNewEList) from the input list L
 361   Standard_Boolean IsNewEdge;
 362   NCollection_List<TopoDS_Vertex> aVList;
 363   TopExp_Explorer exp;
 364   BRep_Builder aBB;
 365   TopTools_ListIteratorOfListOfShape anItL;
 366   for (anItL.Initialize(theL); anItL.More(); anItL.Next())
 367   {
 368     IsNewEdge = Standard_False;
 369     aVList.Clear();
 370     const TopoDS_Edge& aCE = TopoDS::Edge(anItL.Value());
 371     exp.Init(aCE, TopAbs_VERTEX);
 372     for (;exp.More(); exp.Next())
 373     {
 374       const TopoDS_Vertex& aVal = TopoDS::Vertex(exp.Current());
 375       if (theO2NV.IsBound(aVal))
 376       {
 377         IsNewEdge = Standard_True;
 378         //append the new vertex
 379         aVList.Append(TopoDS::Vertex(theO2NV(aVal).Oriented(aVal.Orientation())));
 380       }
 381       else
 382         aVList.Append(aVal);
 383     }
 384     if (IsNewEdge)
 385     {
 386       TopoDS_Shape NewE = aCE.EmptyCopied();
 387       NCollection_List<TopoDS_Edge>::Iterator it(aVList);
 388       for (; it.More(); it.Next())
 389         aBB.Add(NewE, it.Value());
 390       theNewEList.Append(TopoDS::Edge(NewE));
 391     }
 392     else
 393       theNewEList.Append(aCE);
 394   }
 395 }
 396