src/BRepMesh/BRepMesh_DataStructureOfDelaun.cxx

   1 // Created on: 1993-05-11
   2 // Created by: Didier PIFFAULT
   3 // Copyright (c) 1993-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 #include <BRepMesh_DataStructureOfDelaun.hxx>
  18 #include <BRepMesh_PairOfIndex.hxx>
  19 #include <BRepBuilderAPI_MakeEdge.hxx>
  20
  21 #include <TopoDS_Compound.hxx>
  22 #include <BRep_Builder.hxx>
  23 #include <BRepTools.hxx>
  24 #include <Standard_ErrorHandler.hxx>
  25
  26 IMPLEMENT_STANDARD_HANDLE (BRepMesh_DataStructureOfDelaun, Standard_Transient)
  27 IMPLEMENT_STANDARD_RTTIEXT(BRepMesh_DataStructureOfDelaun, Standard_Transient)
  28
  29 //=======================================================================
  30 //function : BRepMesh_DataStructureOfDelaun
  31 //purpose  :
  32 //=======================================================================
  33 BRepMesh_DataStructureOfDelaun::BRepMesh_DataStructureOfDelaun(
  34   const Handle(NCollection_IncAllocator)& theAllocator,
  35   const Standard_Integer                  theReservedNodeSize)
  36   : myNodes           (theReservedNodeSize, theAllocator),
  37     myLinks           (theReservedNodeSize * 3),
  38     myDelLinks        (theAllocator),
  39     myElements        (theReservedNodeSize * 2),
  40     myElementsOfDomain(theReservedNodeSize * 2, theAllocator),
  41     myLinksOfDomain   (theReservedNodeSize * 2, theAllocator),
  42     myAllocator       (theAllocator)
  43 {
  44 }
  45
  46 //=======================================================================
  47 //function : SubstituteNode
  48 //purpose  :
  49 //=======================================================================
  50 Standard_Boolean BRepMesh_DataStructureOfDelaun::SubstituteNode(
  51   const Standard_Integer theIndex,
  52   const BRepMesh_Vertex& theNewNode)
  53 {
  54   if (myNodes.FindIndex(theNewNode) != 0)
  55     return Standard_False;
  56
  57   const BRepMesh::ListOfInteger& aLinks = myNodes(theIndex);
  58   myNodes.Substitute(theIndex, theNewNode, aLinks);
  59   return Standard_True;
  60 }
  61
  62 //=======================================================================
  63 //function : AddLink
  64 //purpose  :
  65 //=======================================================================
  66 Standard_Integer BRepMesh_DataStructureOfDelaun::AddLink(
  67   const BRepMesh_Edge& theLink)
  68 {
  69   Standard_Integer aLinkIndex = IndexOf(theLink);
  70   if (aLinkIndex > 0)
  71   {
  72     return theLink.IsSameOrientation(GetLink(aLinkIndex)) ?
  73        aLinkIndex : -aLinkIndex;
  74   }
  75
  76   BRepMesh_PairOfIndex aPair;
  77   if (!myDelLinks.IsEmpty())
  78   {
  79     aLinkIndex = myDelLinks.First();
  80     myLinks.Substitute(aLinkIndex, theLink, aPair);
  81     myDelLinks.RemoveFirst();
  82   }
  83   else
  84     aLinkIndex = myLinks.Add(theLink, aPair);
  85
  86   const Standard_Integer aLinkId = Abs(aLinkIndex);
  87   myNodes(theLink.FirstNode()).Append(aLinkId);
  88   myNodes(theLink.LastNode() ).Append(aLinkId);
  89   myLinksOfDomain.Add(aLinkIndex);
  90
  91   return aLinkIndex;
  92 }
  93
  94 //=======================================================================
  95 //function : SubstituteLink
  96 //purpose  :
  97 //=======================================================================
  98 Standard_Boolean BRepMesh_DataStructureOfDelaun::SubstituteLink(
  99   const Standard_Integer theIndex,
 100   const BRepMesh_Edge&   theNewLink)
 101 {
 102   BRepMesh_PairOfIndex aPair;
 103   BRepMesh_Edge aLink = GetLink(theIndex);
 104   if (aLink.Movability() == BRepMesh_Deleted)
 105   {
 106     myLinks.Substitute(theIndex, theNewLink, aPair);
 107     return Standard_True;
 108   }
 109
 110   if (IndexOf(theNewLink) != 0)
 111     return Standard_False;
 112
 113   aLink.SetMovability(BRepMesh_Deleted);
 114   myLinks.Substitute(theIndex, aLink, aPair);
 115   cleanLink(theIndex, aLink);
 116
 117   const Standard_Integer aLinkId = Abs(theIndex);
 118   myNodes(theNewLink.FirstNode()).Append(aLinkId);
 119   myNodes(theNewLink.LastNode() ).Append(aLinkId);
 120   myLinks.Substitute(theIndex, theNewLink, aPair);
 121
 122   return Standard_True;
 123 }
 124
 125 //=======================================================================
 126 //function : ForceRemoveLink
 127 //purpose  :
 128 //=======================================================================
 129 void BRepMesh_DataStructureOfDelaun::RemoveLink(
 130   const Standard_Integer theIndex,
 131   const Standard_Boolean isForce)
 132 {
 133   BRepMesh_Edge& aLink = (BRepMesh_Edge&)GetLink(theIndex);
 134   if (aLink.Movability() == BRepMesh_Deleted            ||
 135       (!isForce && aLink.Movability() != BRepMesh_Free) ||
 136       ElementsConnectedTo(theIndex).Extent() != 0)
 137   {
 138     return;
 139   }
 140
 141   cleanLink(theIndex, aLink);
 142   aLink.SetMovability(BRepMesh_Deleted);
 143
 144   myLinksOfDomain.Remove(theIndex);
 145   myDelLinks.Append     (theIndex);
 146 }
 147
 148 //=======================================================================
 149 //function : cleanLink
 150 //purpose  :
 151 //=======================================================================
 152 void BRepMesh_DataStructureOfDelaun::cleanLink(
 153   const Standard_Integer theIndex,
 154   const BRepMesh_Edge&   theLink)
 155 {
 156   for (Standard_Integer i = 0; i < 2; ++i)
 157   {
 158     const Standard_Integer aNodeId = (i == 0) ?
 159       theLink.FirstNode() : theLink.LastNode();
 160
 161     BRepMesh::ListOfInteger& aLinkList = myNodes(aNodeId);
 162     BRepMesh::ListOfInteger::Iterator aLinkIt(aLinkList);
 163     for(; aLinkIt.More(); aLinkIt.Next())
 164     {
 165       if (aLinkIt.Value() == theIndex)
 166       {
 167         aLinkList.Remove(aLinkIt);
 168         break;
 169       }
 170     }
 171   }
 172 }
 173
 174 //=======================================================================
 175 //function : AddElement
 176 //purpose  :
 177 //=======================================================================
 178 Standard_Integer BRepMesh_DataStructureOfDelaun::AddElement(
 179   const BRepMesh_Triangle& theElement)
 180 {
 181   Standard_Integer aElementIndex = IndexOf(theElement);
 182   if (aElementIndex > 0)
 183     return aElementIndex;
 184
 185   aElementIndex = myElements.Add(theElement);
 186   myElementsOfDomain.Add(aElementIndex);
 187
 188   Standard_Integer e[3];
 189   Standard_Boolean o[3];
 190   theElement.Edges(e, o);
 191   for (Standard_Integer i = 0; i < 3; ++i)
 192     myLinks(e[i]).Append(aElementIndex);
 193
 194   return aElementIndex;
 195 }
 196
 197 //=======================================================================
 198 //function : RemoveElement
 199 //purpose  :
 200 //=======================================================================
 201 void BRepMesh_DataStructureOfDelaun::RemoveElement(
 202   const Standard_Integer theIndex)
 203 {
 204   BRepMesh_Triangle& aElement = (BRepMesh_Triangle&)GetElement(theIndex);
 205   if (aElement.Movability() == BRepMesh_Deleted)
 206     return;
 207
 208   cleanElement(theIndex, aElement);
 209   aElement.SetMovability(BRepMesh_Deleted);
 210   myElementsOfDomain.Remove(theIndex);
 211 }
 212
 213 //=======================================================================
 214 //function : cleanElement
 215 //purpose  :
 216 //=======================================================================
 217 void BRepMesh_DataStructureOfDelaun::cleanElement(
 218   const Standard_Integer   theIndex,
 219   const BRepMesh_Triangle& theElement)
 220 {
 221   if (theElement.Movability() != BRepMesh_Free)
 222     return;
 223
 224   Standard_Integer e[3];
 225   Standard_Boolean o[3];
 226   theElement.Edges(e, o);
 227
 228   for (Standard_Integer i = 0; i < 3; ++i)
 229     removeElementIndex(theIndex, myLinks(e[i]));
 230 }
 231
 232 //=======================================================================
 233 //function : removeElementIndex
 234 //purpose  :
 235 //=======================================================================
 236 void BRepMesh_DataStructureOfDelaun::removeElementIndex(
 237   const Standard_Integer theIndex,
 238   BRepMesh_PairOfIndex&  thePair)
 239 {
 240   for (Standard_Integer i = 1, n = thePair.Extent(); i <= n; ++i)
 241   {
 242     if (thePair.Index(i) == theIndex)
 243     {
 244       thePair.RemoveIndex(i);
 245       return;
 246     }
 247   }
 248 }
 249
 250 //=======================================================================
 251 //function : SubstituteElement
 252 //purpose  :
 253 //=======================================================================
 254 Standard_Boolean BRepMesh_DataStructureOfDelaun::SubstituteElement(
 255   const Standard_Integer   theIndex,
 256   const BRepMesh_Triangle& theNewElement)
 257 {
 258   const BRepMesh_Triangle& aElement = GetElement(theIndex);
 259   if (aElement.Movability() == BRepMesh_Deleted)
 260   {
 261     myElements.Substitute(theIndex, theNewElement);
 262     return Standard_True;
 263   }
 264
 265   if (IndexOf(theNewElement) != 0)
 266     return Standard_False;
 267
 268   cleanElement(theIndex, aElement);
 269   // Warning: here new element and old element should have different Hash code
 270   myElements.Substitute(theIndex, theNewElement);
 271
 272   Standard_Integer e[3];
 273   Standard_Boolean o[3];
 274   theNewElement.Edges(e, o);
 275   for (Standard_Integer i = 0; i < 3; ++i)
 276     myLinks(e[i]).Append(theIndex);
 277
 278   return Standard_True;
 279 }
 280
 281 //=======================================================================
 282 //function : ElementNodes
 283 //purpose  :
 284 //=======================================================================
 285 void BRepMesh_DataStructureOfDelaun::ElementNodes(
 286     const BRepMesh_Triangle& theElement,
 287     Standard_Integer         (&theNodes)[3])
 288 {
 289   Standard_Integer e[3];
 290   Standard_Boolean o[3];
 291   theElement.Edges(e, o);
 292
 293   const BRepMesh_Edge& aLink1 = GetLink(e[0]);
 294   if (o[0])
 295   {
 296     theNodes[0] = aLink1.FirstNode();
 297     theNodes[1] = aLink1.LastNode();
 298   }
 299   else
 300   {
 301     theNodes[1] = aLink1.FirstNode();
 302     theNodes[0] = aLink1.LastNode();
 303   }
 304
 305   const BRepMesh_Edge& aLink2 = GetLink(e[2]);
 306   if (o[2])
 307     theNodes[2] = aLink2.FirstNode();
 308   else
 309     theNodes[2] = aLink2.LastNode();
 310 }
 311
 312 //=======================================================================
 313 //function : ClearDomain
 314 //purpose  :
 315 //=======================================================================
 316 void BRepMesh_DataStructureOfDelaun::ClearDomain()
 317 {
 318   BRepMesh::MapOfInteger aFreeEdges;
 319   BRepMesh::MapOfInteger::Iterator aElementIt(myElementsOfDomain);
 320   for (; aElementIt.More(); aElementIt.Next())
 321   {
 322     const Standard_Integer aElementId = aElementIt.Key();
 323     BRepMesh_Triangle& aElement = (BRepMesh_Triangle&)GetElement(aElementId);
 324
 325     Standard_Integer e[3];
 326     Standard_Boolean o[3];
 327     aElement.Edges(e, o);
 328
 329     for (Standard_Integer i = 0; i < 3; ++i)
 330       aFreeEdges.Add(e[i]);
 331
 332     cleanElement(aElementId, aElement);
 333     aElement.SetMovability(BRepMesh_Deleted);
 334   }
 335   myElementsOfDomain.Clear();
 336
 337   BRepMesh::MapOfInteger::Iterator aEdgeIt(aFreeEdges);
 338   for (; aEdgeIt.More(); aEdgeIt.Next())
 339     RemoveLink(aEdgeIt.Key());
 340 }
 341
 342 //=======================================================================
 343 //function : clearDeletedLinks
 344 //purpose  :
 345 //=======================================================================
 346 void BRepMesh_DataStructureOfDelaun::clearDeletedLinks()
 347 {
 348   Standard_Integer aLastLiveItem = NbLinks();
 349   while (!myDelLinks.IsEmpty())
 350   {
 351     while (aLastLiveItem > 0)
 352     {
 353       if (GetLink(aLastLiveItem).Movability() != BRepMesh_Deleted)
 354         break;
 355
 356       myLinks.RemoveLast();
 357       --aLastLiveItem;
 358     }
 359
 360     Standard_Integer aDelItem = myDelLinks.First();
 361     myDelLinks.RemoveFirst();
 362
 363     if (aDelItem > aLastLiveItem)
 364       continue;
 365
 366     BRepMesh_Edge aLink = GetLink(aLastLiveItem);
 367     BRepMesh_PairOfIndex& aPair = myLinks(aLastLiveItem);
 368
 369     myLinks.RemoveLast();
 370     myLinks.Substitute(aDelItem, aLink, aPair);
 371
 372     myLinksOfDomain.Remove(aLastLiveItem);
 373     myLinksOfDomain.Add(aDelItem);
 374     --aLastLiveItem;
 375
 376     const Standard_Integer aLastLiveItemId = aLastLiveItem + 1;
 377     BRepMesh::ListOfInteger::Iterator aLinkIt;
 378     // update link references
 379     for (Standard_Integer i = 0; i < 2; ++i)
 380     {
 381       const Standard_Integer aCurNodeId = (i == 0) ?
 382         aLink.FirstNode() : aLink.LastNode();
 383
 384       for (aLinkIt.Init(myNodes(aCurNodeId)); aLinkIt.More(); aLinkIt.Next())
 385       {
 386         Standard_Integer& aLinkId = aLinkIt.ChangeValue();
 387         if (aLinkId == aLastLiveItemId)
 388         {
 389           aLinkId = aDelItem;
 390           break;
 391         }
 392       }
 393     }
 394
 395     // update elements references
 396     for(Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j)
 397     {
 398       const BRepMesh_Triangle& aElement = GetElement(aPair.Index(j));
 399
 400       Standard_Integer e[3];
 401       Standard_Boolean o[3];
 402       aElement.Edges(e, o);
 403       for (Standard_Integer i = 0; i < 3; ++i)
 404       {
 405         if (e[i] == aLastLiveItemId)
 406         {
 407           e[i] = aDelItem;
 408           break;
 409         }
 410       }
 411
 412       myElements.Substitute(aLinkIt.Value(),
 413         BRepMesh_Triangle(e, o, aElement.Movability()));
 414     }
 415   }
 416 }
 417
 418 //=======================================================================
 419 //function : clearDeletedNodes
 420 //purpose  :
 421 //=======================================================================
 422 void BRepMesh_DataStructureOfDelaun::clearDeletedNodes()
 423 {
 424   BRepMesh::ListOfInteger& aDelNodes =
 425     (BRepMesh::ListOfInteger&)myNodes.GetListOfDelNodes();
 426
 427   Standard_Integer aLastLiveItem = NbNodes();
 428   while (!aDelNodes.IsEmpty())
 429   {
 430     while (aLastLiveItem > 0)
 431     {
 432       if (GetNode(aLastLiveItem).Movability() != BRepMesh_Deleted)
 433         break;
 434
 435       myNodes.RemoveLast();
 436       --aLastLiveItem;
 437     }
 438
 439     Standard_Integer aDelItem = aDelNodes.First();
 440     aDelNodes.RemoveFirst();
 441
 442     if (aDelItem > aLastLiveItem)
 443       continue;
 444
 445     BRepMesh_Vertex aNode = GetNode(aLastLiveItem);
 446     BRepMesh::ListOfInteger& aLinkList = myNodes(aLastLiveItem);
 447
 448     myNodes.RemoveLast();
 449     --aLastLiveItem;
 450
 451     myNodes.Substitute(aDelItem, aNode, aLinkList);
 452
 453     const Standard_Integer aLastLiveItemId = aLastLiveItem + 1;
 454     BRepMesh::ListOfInteger::Iterator aLinkIt(aLinkList);
 455     for (; aLinkIt.More(); aLinkIt.Next())
 456     {
 457       const Standard_Integer aLinkId = aLinkIt.Value();
 458       const BRepMesh_Edge& aLink = GetLink(aLinkId);
 459       BRepMesh_PairOfIndex& aPair = myLinks(aLinkId);
 460
 461       Standard_Integer v[2] = { aLink.FirstNode(), aLink.LastNode() };
 462       if (v[0] == aLastLiveItemId)
 463         v[0] = aDelItem;
 464       else if (v[1] == aLastLiveItemId)
 465         v[1] = aDelItem;
 466
 467       myLinks.Substitute(aLinkId,
 468         BRepMesh_Edge(v[0], v[1], aLink.Movability()), aPair);
 469     }
 470   }
 471 }
 472
 473 //=======================================================================
 474 //function : Statistics
 475 //purpose  :
 476 //=======================================================================
 477 void BRepMesh_DataStructureOfDelaun::Statistics(Standard_OStream& theStream) const
 478 {
 479   theStream << " Map of nodes : \n";
 480   myNodes.Statistics(theStream);
 481   theStream << "\n Deleted nodes : " << myNodes.GetListOfDelNodes().Extent() << endl;
 482
 483   theStream << "\n\n Map of Links : \n";
 484   myLinks.Statistics(theStream);
 485   theStream << "\n Deleted links : " << myDelLinks.Extent() << endl;
 486
 487   theStream << "\n\n Map of elements : \n";
 488   myElements.Statistics(theStream);
 489 }
 490
 491 //=======================================================================
 492 //function : BRepMesh_Write
 493 //purpose  :
 494 //  Global function not declared in any public header, intended for use
 495 //  from debugger prompt (Command Window in Visual Studio).
 496 //
 497 //  Stores the mesh data structure to BRep file with the given name.
 498 //=======================================================================
 499 Standard_CString BRepMesh_Dump(void*            theMeshHandlePtr,
 500                                Standard_CString theFileNameStr)
 501 {
 502   if (theMeshHandlePtr == 0 || theFileNameStr == 0)
 503   {
 504     return "Error: file name or mesh data is null";
 505   }
 506
 507   Handle(BRepMesh_DataStructureOfDelaun) aMeshData =
 508     *(Handle(BRepMesh_DataStructureOfDelaun)*)theMeshHandlePtr;
 509
 510   if (aMeshData.IsNull())
 511     return "Error: mesh data is empty";
 512
 513   TopoDS_Compound aMesh;
 514   BRep_Builder aBuilder;
 515   aBuilder.MakeCompound(aMesh);
 516
 517   try
 518   {
 519     OCC_CATCH_SIGNALS
 520
 521     BRepMesh::MapOfInteger::Iterator aLinksIt(aMeshData->LinksOfDomain());
 522     for (; aLinksIt.More(); aLinksIt.Next())
 523     {
 524       const BRepMesh_Edge& aLink = aMeshData->GetLink(aLinksIt.Value());
 525       gp_Pnt aPnt[2];
 526       for (Standard_Integer i = 0; i < 2; ++i)
 527       {
 528         const Standard_Integer aNodeId =
 529           (i == 0) ? aLink.FirstNode() : aLink.LastNode();
 530
 531         const gp_XY& aNode = aMeshData->GetNode(aNodeId).Coord();
 532         aPnt[i] = gp_Pnt(aNode.X(), aNode.Y(), 0.);
 533       }
 534
 535       if (aPnt[0].SquareDistance(aPnt[1]) < Precision::SquareConfusion())
 536         continue;
 537
 538       aBuilder.Add(aMesh, BRepBuilderAPI_MakeEdge(aPnt[0], aPnt[1]));
 539     }
 540
 541     if (!BRepTools::Write(aMesh, theFileNameStr))
 542       return "Error: write failed";
 543   }
 544   catch (Standard_Failure)
 545   {
 546     return Standard_Failure::Caught()->GetMessageString();
 547   }
 548
 549   return theFileNameStr;
 550 }