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