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