src/BRepMesh/BRepMesh_Delaun.cxx

   1 // Created on: 1993-05-12
   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_Delaun.hxx>
  18
  19 #include <gp.hxx>
  20 #include <gp_XY.hxx>
  21 #include <gp_Pnt2d.hxx>
  22 #include <gp_Vec2d.hxx>
  23
  24 #include <Precision.hxx>
  25 #include <Bnd_Box2d.hxx>
  26 #include <Bnd_B2d.hxx>
  27
  28 #include <BRepMesh_SelectorOfDataStructureOfDelaun.hxx>
  29
  30 #include <BRepMesh_Edge.hxx>
  31 #include <BRepMesh_Vertex.hxx>
  32 #include <BRepMesh_Triangle.hxx>
  33
  34 #include <NCollection_Vector.hxx>
  35
  36 #include <algorithm>
  37 #include <stack>
  38
  39 const Standard_Real AngDeviation1Deg  = M_PI/180.;
  40 const Standard_Real AngDeviation90Deg = 90 * AngDeviation1Deg;
  41 const Standard_Real Angle2PI          = 2 * M_PI;
  42
  43 const Standard_Real Precision    = Precision::PConfusion();
  44 const Standard_Real Precision2   = Precision * Precision;
  45
  46 namespace {
  47   //! Sort two points in projection on vector (1,1)
  48   struct ComparatorOfVertexOfDelaun
  49   {
  50     bool operator() (const BRepMesh_Vertex& theLeft, const BRepMesh_Vertex& theRight)
  51     {
  52       return theLeft.Coord().X() + theLeft.Coord().Y() < theRight.Coord().X() + theRight.Coord().Y();
  53     }
  54   };
  55
  56   //! Sort two points in projection on vector (1,1)
  57   struct ComparatorOfIndexedVertexOfDelaun
  58   {
  59   public:
  60     ComparatorOfIndexedVertexOfDelaun (const Handle(BRepMesh_DataStructureOfDelaun)& theDS)
  61       : myStructure(theDS) {}
  62
  63     bool operator() (Standard_Integer theLeft, Standard_Integer theRight)
  64     {
  65       const BRepMesh_Vertex& aLeft  = myStructure->GetNode(theLeft);
  66       const BRepMesh_Vertex& aRight = myStructure->GetNode(theRight);
  67       return ComparatorOfVertexOfDelaun() (aLeft, aRight);
  68     }
  69
  70   private:
  71     Handle(BRepMesh_DataStructureOfDelaun) myStructure;
  72   };
  73
  74   void UpdateBndBox(const gp_XY& thePnt1, const gp_XY& thePnt2, Bnd_B2d& theBox)
  75   {
  76     theBox.Add( thePnt1 );
  77     theBox.Add( thePnt2 );
  78     theBox.Enlarge(Precision);
  79   }
  80 } // anonymous namespace
  81
  82 //=======================================================================
  83 //function : BRepMesh_Delaun
  84 //purpose  :
  85 //=======================================================================
  86 BRepMesh_Delaun::BRepMesh_Delaun (
  87   const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
  88   const Standard_Integer                        theCellsCountU,
  89   const Standard_Integer                        theCellsCountV,
  90   const Standard_Boolean                        isFillCircles)
  91 : myMeshData ( theOldMesh ),
  92   myCircles (new NCollection_IncAllocator(
  93              IMeshData::MEMORY_BLOCK_SIZE_HUGE)),
  94   mySupVert (3),
  95   myInitCircles (Standard_False)
  96 {
  97   if (isFillCircles)
  98   {
  99     InitCirclesTool (theCellsCountU, theCellsCountV);
 100   }
 101 }
 102
 103 //=======================================================================
 104 //function : BRepMesh_Delaun
 105 //purpose  : Creates the triangulation with an empty Mesh data structure
 106 //=======================================================================
 107 BRepMesh_Delaun::BRepMesh_Delaun(IMeshData::Array1OfVertexOfDelaun& theVertices)
 108 : myCircles (theVertices.Length(), new NCollection_IncAllocator(
 109              IMeshData::MEMORY_BLOCK_SIZE_HUGE)),
 110   mySupVert (3),
 111   myInitCircles (Standard_False)
 112 {
 113   if ( theVertices.Length() > 2 )
 114   {
 115     myMeshData = new BRepMesh_DataStructureOfDelaun(
 116       new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE),
 117       theVertices.Length() );
 118     Init( theVertices );
 119   }
 120 }
 121
 122 //=======================================================================
 123 //function : BRepMesh_Delaun
 124 //purpose  : Creates the triangulation with and existent Mesh data structure
 125 //=======================================================================
 126 BRepMesh_Delaun::BRepMesh_Delaun(
 127   const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
 128   IMeshData::Array1OfVertexOfDelaun&            theVertices)
 129 : myMeshData( theOldMesh ),
 130   myCircles ( theVertices.Length(), new NCollection_IncAllocator(
 131              IMeshData::MEMORY_BLOCK_SIZE_HUGE)),
 132   mySupVert (3),
 133   myInitCircles (Standard_False)
 134 {
 135   if ( theVertices.Length() > 2 )
 136   {
 137     Init( theVertices );
 138   }
 139 }
 140
 141 //=======================================================================
 142 //function : BRepMesh_Delaun
 143 //purpose  : Creates the triangulation with and existent Mesh data structure
 144 //=======================================================================
 145 BRepMesh_Delaun::BRepMesh_Delaun(
 146   const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
 147   IMeshData::VectorOfInteger&                   theVertexIndices)
 148 : myMeshData( theOldMesh ),
 149   myCircles ( theVertexIndices.Length(), new NCollection_IncAllocator(
 150              IMeshData::MEMORY_BLOCK_SIZE_HUGE)),
 151   mySupVert (3),
 152   myInitCircles (Standard_False)
 153 {
 154   perform(theVertexIndices);
 155 }
 156
 157 //=======================================================================
 158 //function : BRepMesh_Delaun
 159 //purpose  : Creates the triangulation with and existent Mesh data structure
 160 //=======================================================================
 161 BRepMesh_Delaun::BRepMesh_Delaun (const Handle (BRepMesh_DataStructureOfDelaun)& theOldMesh,
 162                                   IMeshData::VectorOfInteger&                    theVertexIndices,
 163                                   const Standard_Integer                         theCellsCountU,
 164                                   const Standard_Integer                         theCellsCountV)
 165 : myMeshData (theOldMesh),
 166   myCircles (theVertexIndices.Length (), new NCollection_IncAllocator(
 167              IMeshData::MEMORY_BLOCK_SIZE_HUGE)),
 168   mySupVert (3),
 169   myInitCircles (Standard_False)
 170 {
 171   perform (theVertexIndices, theCellsCountU, theCellsCountV);
 172 }
 173
 174 //=======================================================================
 175 //function : Init
 176 //purpose  : Initializes the triangulation with an Array of Vertex
 177 //=======================================================================
 178 void BRepMesh_Delaun::Init(IMeshData::Array1OfVertexOfDelaun& theVertices)
 179 {
 180   Standard_Integer aLowerIdx  = theVertices.Lower();
 181   Standard_Integer anUpperIdx = theVertices.Upper();
 182   IMeshData::VectorOfInteger aVertexIndexes(theVertices.Size());
 183
 184   Standard_Integer anIndex = aLowerIdx;
 185   for ( ; anIndex <= anUpperIdx; ++anIndex )
 186   {
 187     aVertexIndexes.Append(myMeshData->AddNode( theVertices( anIndex ) ));
 188   }
 189
 190   perform( aVertexIndexes );
 191 }
 192
 193 //=======================================================================
 194 //function : InitCirclesTool
 195 //purpose  :
 196 //=======================================================================
 197 void BRepMesh_Delaun::InitCirclesTool (const Standard_Integer theCellsCountU,
 198                                        const Standard_Integer theCellsCountV)
 199 {
 200   Bnd_Box2d aBox;
 201   for (Standard_Integer aNodeIt = 1; aNodeIt <= myMeshData->NbNodes(); ++aNodeIt)
 202   {
 203     aBox.Add (gp_Pnt2d (GetVertex (aNodeIt).Coord ()));
 204   }
 205   aBox.Enlarge (Precision);
 206
 207   initCirclesTool (aBox, theCellsCountU, theCellsCountV);
 208
 209   IMeshData::IteratorOfMapOfInteger aTriangleIt (myMeshData->ElementsOfDomain());
 210   for (; aTriangleIt.More(); aTriangleIt.Next())
 211   {
 212     Standard_Integer aNodesIndices[3];
 213     const BRepMesh_Triangle& aTriangle = myMeshData->GetElement (aTriangleIt.Key());
 214     myMeshData->ElementNodes (aTriangle, aNodesIndices);
 215     myCircles.Bind (aTriangleIt.Key(),
 216                     GetVertex( aNodesIndices[0] ).Coord(),
 217                     GetVertex( aNodesIndices[1] ).Coord(),
 218                     GetVertex( aNodesIndices[2] ).Coord());
 219   }
 220 }
 221
 222 //=======================================================================
 223 //function : initCirclesTool
 224 //purpose  :
 225 //=======================================================================
 226 void BRepMesh_Delaun::initCirclesTool (const Bnd_Box2d&       theBox,
 227                                        const Standard_Integer theCellsCountU,
 228                                        const Standard_Integer theCellsCountV)
 229 {
 230   Standard_Real aMinX, aMinY, aMaxX, aMaxY;
 231   theBox.Get  ( aMinX, aMinY, aMaxX, aMaxY );
 232   const Standard_Real aDeltaX = aMaxX - aMinX;
 233   const Standard_Real aDeltaY = aMaxY - aMinY;
 234
 235   Standard_Integer aScaler = 2;
 236   if ( myMeshData->NbNodes() > 100 )
 237   {
 238     aScaler = 5;
 239   }
 240   else if( myMeshData->NbNodes() > 1000 )
 241   {
 242     aScaler = 7;
 243   }
 244
 245   myCircles.SetMinMaxSize( gp_XY( aMinX, aMinY ), gp_XY( aMaxX, aMaxY ) );
 246   myCircles.SetCellSize  ( aDeltaX / Max (theCellsCountU, aScaler),
 247                            aDeltaY / Max (theCellsCountV, aScaler));
 248
 249   myInitCircles = Standard_True;
 250 }
 251
 252 //=======================================================================
 253 //function : perform
 254 //purpose  : Create super mesh and run triangulation procedure
 255 //=======================================================================
 256 void BRepMesh_Delaun::perform(IMeshData::VectorOfInteger& theVertexIndices,
 257                               const Standard_Integer      theCellsCountU /* = -1 */,
 258                               const Standard_Integer      theCellsCountV /* = -1 */)
 259 {
 260   if (theVertexIndices.Length () <= 2)
 261   {
 262     return;
 263   }
 264
 265   Bnd_Box2d aBox;
 266   Standard_Integer anIndex = theVertexIndices.Lower ();
 267   Standard_Integer anUpper = theVertexIndices.Upper ();
 268   for (; anIndex <= anUpper; ++anIndex)
 269   {
 270     aBox.Add (gp_Pnt2d (GetVertex (theVertexIndices (anIndex)).Coord ()));
 271   }
 272
 273   aBox.Enlarge (Precision);
 274
 275   initCirclesTool (aBox, theCellsCountU, theCellsCountV);
 276   superMesh       (aBox);
 277
 278   ComparatorOfIndexedVertexOfDelaun aCmp(myMeshData);
 279   std::make_heap(theVertexIndices.begin(), theVertexIndices.end(), aCmp);
 280   std::sort_heap(theVertexIndices.begin(), theVertexIndices.end(), aCmp);
 281
 282   compute( theVertexIndices );
 283 }
 284
 285 //=======================================================================
 286 //function : superMesh
 287 //purpose  : Build the super mesh
 288 //=======================================================================
 289 void BRepMesh_Delaun::superMesh(const Bnd_Box2d& theBox)
 290 {
 291   Standard_Real aMinX, aMinY, aMaxX, aMaxY;
 292   theBox.Get  ( aMinX, aMinY, aMaxX, aMaxY );
 293   Standard_Real aDeltaX = aMaxX - aMinX;
 294   Standard_Real aDeltaY = aMaxY - aMinY;
 295
 296   Standard_Real aDeltaMin = Min( aDeltaX, aDeltaY );
 297   Standard_Real aDeltaMax = Max( aDeltaX, aDeltaY );
 298   Standard_Real aDelta    = aDeltaX + aDeltaY;
 299
 300   mySupVert.Append (myMeshData->AddNode(
 301     BRepMesh_Vertex( ( aMinX + aMaxX ) / 2, aMaxY + aDeltaMax, BRepMesh_Free ) ) );
 302
 303   mySupVert.Append (myMeshData->AddNode(
 304     BRepMesh_Vertex( aMinX - aDelta, aMinY - aDeltaMin, BRepMesh_Free ) ) );
 305
 306   mySupVert.Append (myMeshData->AddNode(
 307     BRepMesh_Vertex( aMaxX + aDelta, aMinY - aDeltaMin, BRepMesh_Free ) ) );
 308
 309   Standard_Integer e[3];
 310   Standard_Boolean o[3];
 311   for (Standard_Integer aNodeId = 0; aNodeId < 3; ++aNodeId)
 312   {
 313     Standard_Integer aFirstNode = aNodeId;
 314     Standard_Integer aLastNode  = (aNodeId + 1) % 3;
 315     Standard_Integer aLinkIndex = myMeshData->AddLink( BRepMesh_Edge(
 316       mySupVert[aFirstNode], mySupVert[aLastNode], BRepMesh_Free ) );
 317
 318     e[aNodeId] = Abs(aLinkIndex);
 319     o[aNodeId] = (aLinkIndex > 0);
 320   }
 321
 322   mySupTrian = BRepMesh_Triangle(e, o, BRepMesh_Free);
 323 }
 324
 325 //=======================================================================
 326 //function : deleteTriangle
 327 //purpose  : Deletes the triangle with the given index and adds the free
 328 //           edges into the map.
 329 //           When an edge is suppressed more than one time it is destroyed.
 330 //=======================================================================
 331 void BRepMesh_Delaun::deleteTriangle(const Standard_Integer          theIndex,
 332                                      IMeshData::MapOfIntegerInteger& theLoopEdges )
 333 {
 334   if (myInitCircles)
 335   {
 336     myCircles.Delete (theIndex);
 337   }
 338
 339   const BRepMesh_Triangle& aElement = GetTriangle(theIndex);
 340   const Standard_Integer(&e)[3] = aElement.myEdges;
 341   const Standard_Boolean(&o)[3] = aElement.myOrientations;
 342
 343   myMeshData->RemoveElement( theIndex );
 344
 345   for ( Standard_Integer i = 0; i < 3; ++i )
 346   {
 347     if ( !theLoopEdges.Bind( e[i], o[i] ) )
 348     {
 349       theLoopEdges.UnBind( e[i] );
 350       myMeshData->RemoveLink( e[i] );
 351     }
 352   }
 353 }
 354
 355 //=======================================================================
 356 //function : compute
 357 //purpose  : Computes the triangulation and add the vertices edges and
 358 //           triangles to the Mesh data structure
 359 //=======================================================================
 360 void BRepMesh_Delaun::compute(IMeshData::VectorOfInteger& theVertexIndexes)
 361 {
 362   // Insertion of edges of super triangles in the list of free edges:
 363   Handle(NCollection_IncAllocator) aAllocator = new NCollection_IncAllocator(
 364     IMeshData::MEMORY_BLOCK_SIZE_HUGE);
 365
 366   IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
 367   const Standard_Integer(&e)[3] = mySupTrian.myEdges;
 368
 369   aLoopEdges.Bind( e[0], Standard_True );
 370   aLoopEdges.Bind( e[1], Standard_True );
 371   aLoopEdges.Bind( e[2], Standard_True );
 372
 373   if ( theVertexIndexes.Length() > 0 )
 374   {
 375     // Creation of 3 trianglers with the first node and the edges of the super triangle:
 376     Standard_Integer anVertexIdx = theVertexIndexes.Lower();
 377     createTriangles( theVertexIndexes( anVertexIdx ), aLoopEdges );
 378
 379     // Add other nodes to the mesh
 380     createTrianglesOnNewVertices (theVertexIndexes, Message_ProgressRange());
 381   }
 382
 383   RemoveAuxElements ();
 384 }
 385
 386 //=======================================================================
 387 //function : RemoveAuxElements
 388 //purpose  :
 389 //=======================================================================
 390 void BRepMesh_Delaun::RemoveAuxElements ()
 391 {
 392   Handle (NCollection_IncAllocator) aAllocator = new NCollection_IncAllocator (
 393     IMeshData::MEMORY_BLOCK_SIZE_HUGE);
 394
 395   IMeshData::MapOfIntegerInteger aLoopEdges (10, aAllocator);
 396
 397   // Destruction of triangles containing a top of the super triangle
 398   BRepMesh_SelectorOfDataStructureOfDelaun aSelector (myMeshData);
 399   for (Standard_Integer aSupVertId = 0; aSupVertId < mySupVert.Size(); ++aSupVertId)
 400     aSelector.NeighboursOfNode( mySupVert[aSupVertId] );
 401
 402   IMeshData::IteratorOfMapOfInteger aFreeTriangles( aSelector.Elements() );
 403   for ( ; aFreeTriangles.More(); aFreeTriangles.Next() )
 404     deleteTriangle( aFreeTriangles.Key(), aLoopEdges );
 405
 406   // All edges that remain free are removed from aLoopEdges;
 407   // only the boundary edges of the triangulation remain there
 408   IMeshData::MapOfIntegerInteger::Iterator aFreeEdges( aLoopEdges );
 409   for ( ; aFreeEdges.More(); aFreeEdges.Next() )
 410   {
 411     if ( myMeshData->ElementsConnectedTo( aFreeEdges.Key() ).IsEmpty() )
 412       myMeshData->RemoveLink( aFreeEdges.Key() );
 413   }
 414
 415   // The tops of the super triangle are destroyed
 416   for (Standard_Integer aSupVertId = 0; aSupVertId < mySupVert.Size (); ++aSupVertId)
 417     myMeshData->RemoveNode( mySupVert[aSupVertId] );
 418 }
 419
 420 //=======================================================================
 421 //function : createTriangles
 422 //purpose  : Creates the triangles between the node and the polyline.
 423 //=======================================================================
 424 void BRepMesh_Delaun::createTriangles(const Standard_Integer          theVertexIndex,
 425                                       IMeshData::MapOfIntegerInteger& thePoly)
 426 {
 427   IMeshData::ListOfInteger aLoopEdges, anExternalEdges;
 428   const gp_XY& aVertexCoord = myMeshData->GetNode( theVertexIndex ).Coord();
 429
 430   IMeshData::MapOfIntegerInteger::Iterator anEdges( thePoly );
 431   for ( ; anEdges.More(); anEdges.Next() )
 432   {
 433     Standard_Integer     anEdgeId = anEdges.Key();
 434     const BRepMesh_Edge& anEdge   = GetEdge( anEdgeId );
 435
 436     Standard_Boolean isPositive = thePoly( anEdgeId ) != 0;
 437
 438     Standard_Integer aNodes[3];
 439     if ( isPositive )
 440     {
 441       aNodes[0] = anEdge.FirstNode();
 442       aNodes[2] = anEdge.LastNode();
 443     }
 444     else
 445     {
 446       aNodes[0] = anEdge.LastNode();
 447       aNodes[2] = anEdge.FirstNode();
 448     }
 449     aNodes[1] = theVertexIndex;
 450
 451     const BRepMesh_Vertex& aFirstVertex = GetVertex( aNodes[0] );
 452     const BRepMesh_Vertex& aLastVertex  = GetVertex( aNodes[2] );
 453
 454     gp_XY anEdgeDir( aLastVertex.Coord() - aFirstVertex.Coord() );
 455     Standard_Real anEdgeLen = anEdgeDir.Modulus();
 456     if ( anEdgeLen < Precision )
 457       continue;
 458
 459     anEdgeDir.SetCoord( anEdgeDir.X() / anEdgeLen,
 460                         anEdgeDir.Y() / anEdgeLen );
 461
 462     gp_XY aFirstLinkDir( aFirstVertex.Coord() - aVertexCoord );
 463     gp_XY aLastLinkDir ( aVertexCoord         - aLastVertex.Coord() );
 464
 465     Standard_Real aDist12 = aFirstLinkDir ^ anEdgeDir;
 466     Standard_Real aDist23 = anEdgeDir     ^ aLastLinkDir;
 467     if ( Abs( aDist12 ) < Precision ||
 468          Abs( aDist23 ) < Precision )
 469     {
 470       continue;
 471     }
 472
 473     BRepMesh_Edge aFirstLink( aNodes[1], aNodes[0], BRepMesh_Free );
 474     BRepMesh_Edge aLastLink ( aNodes[2], aNodes[1], BRepMesh_Free );
 475
 476     Standard_Integer anEdgesInfo[3] = {
 477       myMeshData->AddLink( aFirstLink ),
 478       isPositive ? anEdgeId : -anEdgeId,
 479       myMeshData->AddLink( aLastLink ) };
 480
 481     Standard_Boolean isSensOK = (aDist12 > 0. && aDist23 > 0.);
 482     if (isSensOK)
 483     {
 484       Standard_Integer anEdgeIds[3];
 485       Standard_Boolean anEdgesOri[3];
 486       for ( Standard_Integer aTriLinkIt = 0; aTriLinkIt < 3; ++aTriLinkIt )
 487       {
 488         const Standard_Integer& anEdgeInfo = anEdgesInfo[aTriLinkIt];
 489         anEdgeIds[aTriLinkIt]    = Abs( anEdgeInfo );
 490         anEdgesOri[aTriLinkIt] = anEdgeInfo > 0;
 491       }
 492
 493       addTriangle(anEdgeIds, anEdgesOri, aNodes );
 494     }
 495     else
 496     {
 497       if ( isPositive )
 498         aLoopEdges.Append(  anEdges.Key() );
 499       else
 500         aLoopEdges.Append( -anEdges.Key() );
 501
 502       if ( aFirstLinkDir.SquareModulus() > aLastLinkDir.SquareModulus() )
 503         anExternalEdges.Append( Abs( anEdgesInfo[0] ) );
 504       else
 505         anExternalEdges.Append( Abs( anEdgesInfo[2] ) );
 506     }
 507   }
 508
 509   thePoly.Clear();
 510   while ( !anExternalEdges.IsEmpty() )
 511   {
 512     const BRepMesh_PairOfIndex& aPair =
 513       myMeshData->ElementsConnectedTo( Abs( anExternalEdges.First() ) );
 514
 515
 516     if ( !aPair.IsEmpty() )
 517       deleteTriangle( aPair.FirstIndex(), thePoly );
 518
 519     anExternalEdges.RemoveFirst();
 520   }
 521
 522   for ( anEdges.Initialize( thePoly ); anEdges.More(); anEdges.Next() )
 523   {
 524     if ( myMeshData->ElementsConnectedTo( anEdges.Key() ).IsEmpty() )
 525       myMeshData->RemoveLink( anEdges.Key() );
 526   }
 527
 528   while ( !aLoopEdges.IsEmpty() )
 529   {
 530     const BRepMesh_Edge& anEdge = GetEdge( Abs( aLoopEdges.First() ) );
 531     if ( anEdge.Movability() != BRepMesh_Deleted )
 532     {
 533       Standard_Integer anEdgeIdx = aLoopEdges.First();
 534       meshLeftPolygonOf( Abs( anEdgeIdx ), ( anEdgeIdx > 0 ) );
 535     }
 536
 537     aLoopEdges.RemoveFirst();
 538   }
 539 }
 540
 541 //=======================================================================
 542 //function : createTrianglesOnNewVertices
 543 //purpose  : Creation of triangles from the new nodes
 544 //=======================================================================
 545 void BRepMesh_Delaun::createTrianglesOnNewVertices(
 546   IMeshData::VectorOfInteger&   theVertexIndexes,
 547   const Message_ProgressRange& theRange)
 548 {
 549   Handle(NCollection_IncAllocator) aAllocator =
 550     new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
 551
 552   Standard_Real aTolU, aTolV;
 553   myMeshData->Data()->GetTolerance(aTolU, aTolV);
 554   const Standard_Real aSqTol = aTolU * aTolU + aTolV * aTolV;
 555
 556   // Insertion of nodes :
 557   Standard_Boolean isModify = Standard_True;
 558
 559   Standard_Integer anIndex = theVertexIndexes.Lower();
 560   Standard_Integer anUpper = theVertexIndexes.Upper();
 561   Message_ProgressScope aPS(theRange, "Create triangles on new vertices", anUpper);
 562   for (; anIndex <= anUpper; ++anIndex, aPS.Next())
 563   {
 564     if (!aPS.More())
 565     {
 566       return;
 567     }
 568     aAllocator->Reset(Standard_False);
 569     IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
 570
 571     Standard_Integer aVertexIdx = theVertexIndexes( anIndex );
 572     const BRepMesh_Vertex& aVertex = GetVertex( aVertexIdx );
 573
 574     // Iterator in the list of indexes of circles containing the node
 575     IMeshData::ListOfInteger& aCirclesList = myCircles.Select( aVertex.Coord() );
 576
 577     Standard_Integer onEgdeId = 0, aTriangleId = 0;
 578     IMeshData::ListOfInteger::Iterator aCircleIt( aCirclesList );
 579     for ( ; aCircleIt.More(); aCircleIt.Next() )
 580     {
 581       // To add a node in the mesh it is necessary to check conditions:
 582       // - the node should be within the boundaries of the mesh and so in an existing triangle
 583       // - all adjacent triangles should belong to a component connected with this triangle
 584       if ( Contains( aCircleIt.Value(), aVertex, aSqTol, onEgdeId ) )
 585       {
 586         if (onEgdeId != 0 && GetEdge(onEgdeId).Movability() != BRepMesh_Free)
 587         {
 588           // We can skip free vertex too close to the frontier edge.
 589           if (aVertex.Movability() == BRepMesh_Free)
 590             continue;
 591
 592           // However, we should add vertex that have neighboring frontier edges.
 593         }
 594
 595         // Remove triangle even if it contains frontier edge in order
 596         // to prevent appearance of incorrect configurations like free
 597         // edge glued with frontier #26407
 598         aTriangleId = aCircleIt.Value();
 599         aCirclesList.Remove( aCircleIt );
 600         break;
 601       }
 602     }
 603
 604     if ( aTriangleId > 0 )
 605     {
 606       deleteTriangle( aTriangleId, aLoopEdges );
 607
 608       isModify = Standard_True;
 609       while ( isModify && !aCirclesList.IsEmpty() )
 610       {
 611         isModify = Standard_False;
 612         IMeshData::ListOfInteger::Iterator aCircleIt1( aCirclesList );
 613         for ( ; aCircleIt1.More(); aCircleIt1.Next() )
 614         {
 615           const BRepMesh_Triangle& aElement = GetTriangle(aCircleIt1.Value());
 616           const Standard_Integer(&e)[3] = aElement.myEdges;
 617
 618           if ( aLoopEdges.IsBound( e[0] ) ||
 619                aLoopEdges.IsBound( e[1] ) ||
 620                aLoopEdges.IsBound( e[2] ) )
 621           {
 622             isModify = Standard_True;
 623             deleteTriangle( aCircleIt1.Value(), aLoopEdges );
 624             aCirclesList.Remove( aCircleIt1 );
 625             break;
 626           }
 627         }
 628       }
 629
 630       // Creation of triangles with the current node and free edges
 631       // and removal of these edges from the list of free edges
 632       createTriangles( aVertexIdx, aLoopEdges );
 633     }
 634   }
 635
 636   ProcessConstraints();
 637 }
 638
 639 //=======================================================================
 640 //function : insertInternalEdges
 641 //purpose  :
 642 //=======================================================================
 643 void BRepMesh_Delaun::insertInternalEdges()
 644 {
 645   Handle(IMeshData::MapOfInteger) anInternalEdges = InternalEdges();
 646
 647   // Destruction of triangles intersecting internal edges
 648   // and their replacement by makeshift triangles
 649   IMeshData::IteratorOfMapOfInteger anInernalEdgesIt( *anInternalEdges );
 650   for ( ; anInernalEdgesIt.More(); anInernalEdgesIt.Next() )
 651   {
 652     const Standard_Integer aLinkIndex = anInernalEdgesIt.Key();
 653     const BRepMesh_PairOfIndex& aPair = myMeshData->ElementsConnectedTo(aLinkIndex);
 654
 655     // Check both sides of link for adjusted triangle.
 656     Standard_Boolean isGo[2] = { Standard_True, Standard_True };
 657     for (Standard_Integer aTriangleIt = 1; aTriangleIt <= aPair.Extent(); ++aTriangleIt)
 658     {
 659       const BRepMesh_Triangle& aElement = GetTriangle(aPair.Index(aTriangleIt));
 660       const Standard_Integer(&e)[3] = aElement.myEdges;
 661       const Standard_Boolean(&o)[3] = aElement.myOrientations;
 662
 663       for (Standard_Integer i = 0; i < 3; ++i)
 664       {
 665         if (e[i] == aLinkIndex)
 666         {
 667           isGo[o[i] ? 0 : 1] = Standard_False;
 668           break;
 669         }
 670       }
 671     }
 672
 673     if (isGo[0])
 674     {
 675       meshLeftPolygonOf(aLinkIndex, Standard_True);
 676     }
 677
 678     if (isGo[1])
 679     {
 680       meshLeftPolygonOf(aLinkIndex, Standard_False);
 681     }
 682   }
 683 }
 684
 685 //=======================================================================
 686 //function : isBoundToFrontier
 687 //purpose  :
 688 //=======================================================================
 689 Standard_Boolean BRepMesh_Delaun::isBoundToFrontier(
 690   const Standard_Integer theRefNodeId,
 691   const Standard_Integer theRefLinkId)
 692 {
 693   std::stack<Standard_Integer> aLinkStack;
 694   TColStd_PackedMapOfInteger   aVisitedLinks;
 695
 696   aLinkStack.push (theRefLinkId);
 697   while (!aLinkStack.empty ())
 698   {
 699     const Standard_Integer aCurrentLinkId = aLinkStack.top ();
 700     aLinkStack.pop ();
 701
 702     const BRepMesh_PairOfIndex& aPair = myMeshData->ElementsConnectedTo (aCurrentLinkId);
 703     if (aPair.IsEmpty ())
 704       return Standard_False;
 705
 706     const Standard_Integer aNbElements = aPair.Extent ();
 707     for (Standard_Integer anElemIt = 1; anElemIt <= aNbElements; ++anElemIt)
 708     {
 709       const Standard_Integer aTriId = aPair.Index (anElemIt);
 710       if (aTriId < 0)
 711         continue;
 712
 713       const BRepMesh_Triangle& aElement = GetTriangle (aTriId);
 714       const Standard_Integer (&anEdges)[3] = aElement.myEdges;
 715
 716       for (Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt)
 717       {
 718         const Standard_Integer anEdgeId = anEdges[anEdgeIt];
 719         if (anEdgeId == aCurrentLinkId)
 720           continue;
 721
 722         const BRepMesh_Edge& anEdge = GetEdge (anEdgeId);
 723         if (anEdge.FirstNode () != theRefNodeId &&
 724             anEdge.LastNode  () != theRefNodeId)
 725         {
 726           continue;
 727         }
 728
 729         if (anEdge.Movability () != BRepMesh_Free)
 730           return Standard_True;
 731
 732         if (aVisitedLinks.Add (anEdgeId))
 733         {
 734           aLinkStack.push (anEdgeId);
 735         }
 736       }
 737     }
 738   }
 739
 740   return Standard_False;
 741 }
 742
 743 //=======================================================================
 744 //function : cleanupMesh
 745 //purpose  : Cleanup mesh from the free triangles
 746 //=======================================================================
 747 void BRepMesh_Delaun::cleanupMesh()
 748 {
 749   Handle(NCollection_IncAllocator) aAllocator =
 750     new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
 751
 752   for(;;)
 753   {
 754     aAllocator->Reset(Standard_False);
 755     IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
 756     IMeshData::MapOfInteger aDelTriangles;
 757
 758     Handle(IMeshData::MapOfInteger) aFreeEdges = FreeEdges();
 759     IMeshData::IteratorOfMapOfInteger aFreeEdgesIt( *aFreeEdges );
 760     for ( ; aFreeEdgesIt.More(); aFreeEdgesIt.Next() )
 761     {
 762       const Standard_Integer& aFreeEdgeId = aFreeEdgesIt.Key();
 763       const BRepMesh_Edge&    anEdge      = GetEdge( aFreeEdgeId );
 764       if ( anEdge.Movability() == BRepMesh_Frontier )
 765         continue;
 766
 767       const BRepMesh_PairOfIndex& aPair =
 768         myMeshData->ElementsConnectedTo( aFreeEdgeId );
 769       if ( aPair.IsEmpty() )
 770       {
 771         aLoopEdges.Bind( aFreeEdgeId, Standard_True );
 772         continue;
 773       }
 774
 775       Standard_Integer aTriId = aPair.FirstIndex();
 776
 777       // Check that the connected triangle is not surrounded by another triangles
 778       const BRepMesh_Triangle& aElement = GetTriangle(aTriId);
 779       const Standard_Integer(&anEdges)[3] = aElement.myEdges;
 780
 781       Standard_Boolean isCanNotBeRemoved = Standard_True;
 782       for ( Standard_Integer aCurEdgeIdx = 0; aCurEdgeIdx < 3; ++aCurEdgeIdx )
 783       {
 784         if ( anEdges[aCurEdgeIdx] != aFreeEdgeId )
 785           continue;
 786
 787         for ( Standard_Integer anOtherEdgeIt = 1; anOtherEdgeIt <= 2 && isCanNotBeRemoved; ++anOtherEdgeIt )
 788         {
 789           Standard_Integer anOtherEdgeId = ( aCurEdgeIdx + anOtherEdgeIt ) % 3;
 790           const BRepMesh_PairOfIndex& anOtherEdgePair =
 791             myMeshData->ElementsConnectedTo( anEdges[anOtherEdgeId] );
 792
 793           if ( anOtherEdgePair.Extent() < 2 )
 794           {
 795             isCanNotBeRemoved = Standard_False;
 796           }
 797           else
 798           {
 799             for (int aTriIdx = 1; aTriIdx <= anOtherEdgePair.Extent () && isCanNotBeRemoved; ++aTriIdx)
 800             {
 801               if (anOtherEdgePair.Index (aTriIdx) == aTriId)
 802                 continue;
 803
 804               Standard_Integer v[3];
 805               const BRepMesh_Triangle& aCurTriangle = GetTriangle (anOtherEdgePair.Index (aTriIdx));
 806               myMeshData->ElementNodes (aCurTriangle, v);
 807               for (int aNodeIdx = 0; aNodeIdx < 3 && isCanNotBeRemoved; ++aNodeIdx)
 808               {
 809                 if (isSupVertex (v[aNodeIdx]))
 810                 {
 811                   isCanNotBeRemoved = Standard_False;
 812                 }
 813               }
 814             }
 815           }
 816         }
 817
 818         break;
 819       }
 820
 821       if ( isCanNotBeRemoved )
 822         continue;
 823
 824       Standard_Boolean isConnected[2] = { Standard_False, Standard_False };
 825       for ( Standard_Integer aLinkNodeIt = 0; aLinkNodeIt < 2; ++aLinkNodeIt )
 826       {
 827         isConnected[aLinkNodeIt] = isBoundToFrontier( ( aLinkNodeIt == 0 ) ?
 828           anEdge.FirstNode() : anEdge.LastNode(), aFreeEdgeId);
 829       }
 830
 831       if ( !isConnected[0] || !isConnected[1] )
 832         aDelTriangles.Add( aTriId );
 833     }
 834
 835     // Destruction of triangles :
 836     Standard_Integer aDeletedTrianglesNb = 0;
 837     IMeshData::IteratorOfMapOfInteger aDelTrianglesIt( aDelTriangles );
 838     for ( ; aDelTrianglesIt.More(); aDelTrianglesIt.Next() )
 839     {
 840       deleteTriangle( aDelTrianglesIt.Key(), aLoopEdges );
 841       aDeletedTrianglesNb++;
 842     }
 843
 844     // Destruction of remaining hanging edges
 845     IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
 846     for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
 847     {
 848       if ( myMeshData->ElementsConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
 849         myMeshData->RemoveLink( aLoopEdgesIt.Key() );
 850     }
 851
 852     if ( aDeletedTrianglesNb == 0 )
 853       break;
 854   }
 855 }
 856
 857 //=======================================================================
 858 //function : frontierAdjust
 859 //purpose  : Adjust the mesh on the frontier
 860 //=======================================================================
 861 void BRepMesh_Delaun::frontierAdjust()
 862 {
 863   Handle(IMeshData::MapOfInteger)  aFrontier = Frontier();
 864
 865   Handle(NCollection_IncAllocator) aAllocator =
 866     new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
 867
 868   IMeshData::VectorOfInteger      aFailedFrontiers(256, aAllocator);
 869   IMeshData::MapOfIntegerInteger  aLoopEdges(10, aAllocator);
 870   Handle(IMeshData::MapOfInteger) aIntFrontierEdges = new IMeshData::MapOfInteger;
 871
 872   for ( Standard_Integer aPass = 1; aPass <= 2; ++aPass )
 873   {
 874     // 1 pass): find external triangles on boundary edges;
 875     // 2 pass): find external triangles on boundary edges appeared
 876     //          during triangles replacement.
 877
 878     IMeshData::IteratorOfMapOfInteger aFrontierIt( *aFrontier );
 879     for ( ; aFrontierIt.More(); aFrontierIt.Next() )
 880     {
 881       Standard_Integer aFrontierId = aFrontierIt.Key();
 882       const BRepMesh_PairOfIndex& aPair = myMeshData->ElementsConnectedTo( aFrontierId );
 883       Standard_Integer aNbElem = aPair.Extent();
 884       for( Standard_Integer aElemIt = 1; aElemIt <= aNbElem; ++aElemIt )
 885       {
 886         const Standard_Integer aPriorElemId = aPair.Index( aElemIt );
 887         if( aPriorElemId < 0 )
 888           continue;
 889
 890         const BRepMesh_Triangle& aElement = GetTriangle(aPriorElemId);
 891         const Standard_Integer(&e)[3] = aElement.myEdges;
 892         const Standard_Boolean(&o)[3] = aElement.myOrientations;
 893
 894         Standard_Boolean isTriangleFound = Standard_False;
 895         for ( Standard_Integer n = 0; n < 3; ++n )
 896         {
 897           if ( aFrontierId == e[n] && !o[n] )
 898           {
 899             // Destruction  of external triangles on boundary edges
 900             isTriangleFound = Standard_True;
 901             deleteTriangle( aPriorElemId, aLoopEdges );
 902             break;
 903           }
 904         }
 905
 906         if ( isTriangleFound )
 907           break;
 908       }
 909     }
 910
 911     // destrucrion of remaining hanging edges :
 912     IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
 913     for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
 914     {
 915       Standard_Integer aLoopEdgeId = aLoopEdgesIt.Key();
 916       if (myMeshData->ElementsConnectedTo( aLoopEdgeId ).IsEmpty() )
 917         myMeshData->RemoveLink( aLoopEdgeId );
 918     }
 919
 920     // destruction of triangles crossing the boundary edges and
 921     // their replacement by makeshift triangles
 922     for ( aFrontierIt.Reset(); aFrontierIt.More(); aFrontierIt.Next() )
 923     {
 924       Standard_Integer aFrontierId = aFrontierIt.Key();
 925       if ( !myMeshData->ElementsConnectedTo( aFrontierId ).IsEmpty() )
 926         continue;
 927
 928       Standard_Boolean isSuccess =
 929         meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
 930
 931       if ( aPass == 2 && !isSuccess )
 932         aFailedFrontiers.Append( aFrontierId );
 933     }
 934   }
 935
 936   cleanupMesh();
 937
 938   // When the mesh has been cleaned up, try to process frontier edges
 939   // once again to fill the possible gaps that might be occurred in case of "saw" -
 940   // situation when frontier edge has a triangle at a right side, but its free
 941   // links cross another frontieres  and meshLeftPolygonOf itself can't collect
 942   // a closed polygon.
 943   IMeshData::VectorOfInteger::Iterator aFailedFrontiersIt( aFailedFrontiers );
 944   for ( ; aFailedFrontiersIt.More(); aFailedFrontiersIt.Next() )
 945   {
 946     Standard_Integer aFrontierId = aFailedFrontiersIt.Value();
 947     if ( !myMeshData->ElementsConnectedTo( aFrontierId ).IsEmpty() )
 948       continue;
 949
 950     meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
 951   }
 952 }
 953
 954 //=======================================================================
 955 //function : fillBndBox
 956 //purpose  : Add bounding box for edge defined by start & end point to
 957 //           the given vector of bounding boxes for triangulation edges
 958 //=======================================================================
 959 void BRepMesh_Delaun::fillBndBox(IMeshData::SequenceOfBndB2d& theBoxes,
 960                                  const BRepMesh_Vertex&       theV1,
 961                                  const BRepMesh_Vertex&       theV2)
 962 {
 963   Bnd_B2d aBox;
 964   UpdateBndBox(theV1.Coord(), theV2.Coord(), aBox);
 965   theBoxes.Append( aBox );
 966 }
 967
 968 //=======================================================================
 969 //function : meshLeftPolygonOf
 970 //purpose  : Collect the polygon at the left of the given edge (material side)
 971 //=======================================================================
 972 Standard_Boolean BRepMesh_Delaun::meshLeftPolygonOf(
 973   const Standard_Integer          theStartEdgeId,
 974   const Standard_Boolean          isForward,
 975   Handle(IMeshData::MapOfInteger) theSkipped)
 976 {
 977   if ( !theSkipped.IsNull() && theSkipped->Contains( theStartEdgeId ) )
 978     return Standard_True;
 979
 980   const BRepMesh_Edge& aRefEdge = GetEdge( theStartEdgeId );
 981
 982   IMeshData::SequenceOfInteger aPolygon;
 983   Standard_Integer aStartNode, aPivotNode;
 984   if ( isForward )
 985   {
 986     aPolygon.Append( theStartEdgeId );
 987     aStartNode = aRefEdge.FirstNode();
 988     aPivotNode = aRefEdge.LastNode();
 989   }
 990   else
 991   {
 992     aPolygon.Append( -theStartEdgeId );
 993     aStartNode = aRefEdge.LastNode();
 994     aPivotNode = aRefEdge.FirstNode();
 995   }
 996
 997   const BRepMesh_Vertex& aStartEdgeVertexS = GetVertex( aStartNode );
 998   BRepMesh_Vertex        aPivotVertex      = GetVertex( aPivotNode );
 999
1000   gp_Vec2d aRefLinkDir( aPivotVertex.Coord() -
1001     aStartEdgeVertexS.Coord() );
1002
1003   if ( aRefLinkDir.SquareMagnitude() < Precision2 )
1004     return Standard_True;
1005
1006   // Auxiliary structures.
1007   // Bounding boxes of polygon links to be used for preliminary
1008   // analysis of intersections
1009   IMeshData::SequenceOfBndB2d aBoxes;
1010   fillBndBox( aBoxes, aStartEdgeVertexS, aPivotVertex );
1011
1012   // Hanging ends
1013   IMeshData::MapOfInteger aDeadLinks;
1014
1015   // Links are temporarily excluded from consideration
1016   IMeshData::MapOfInteger aLeprousLinks;
1017   aLeprousLinks.Add( theStartEdgeId );
1018
1019   Standard_Boolean isSkipLeprous = Standard_True;
1020   Standard_Integer aFirstNode    = aStartNode;
1021   while ( aPivotNode != aFirstNode )
1022   {
1023     Bnd_B2d          aNextLinkBndBox;
1024     gp_Vec2d         aNextLinkDir;
1025     Standard_Integer aNextPivotNode = 0;
1026
1027     Standard_Integer aNextLinkId = findNextPolygonLink(
1028       aFirstNode,
1029       aPivotNode,     aPivotVertex,  aRefLinkDir,
1030       aBoxes,         aPolygon,      theSkipped,
1031       isSkipLeprous,  aLeprousLinks, aDeadLinks,
1032       aNextPivotNode, aNextLinkDir,  aNextLinkBndBox );
1033
1034     if ( aNextLinkId != 0 )
1035     {
1036       aStartNode   = aPivotNode;
1037       aRefLinkDir  = aNextLinkDir;
1038
1039       aPivotNode   = aNextPivotNode;
1040       aPivotVertex = GetVertex( aNextPivotNode );
1041
1042       aBoxes.Append  ( aNextLinkBndBox );
1043       aPolygon.Append( aNextLinkId );
1044
1045       isSkipLeprous = Standard_True;
1046     }
1047     else
1048     {
1049       // Nothing to do
1050       if ( aPolygon.Length() == 1 )
1051         return Standard_False;
1052
1053       // Return to the previous point
1054       Standard_Integer aDeadLinkId = Abs( aPolygon.Last() );
1055       aDeadLinks.Add      ( aDeadLinkId );
1056
1057       aLeprousLinks.Remove( aDeadLinkId );
1058       aPolygon.Remove     ( aPolygon.Length() );
1059       aBoxes.Remove       ( aBoxes.Length() );
1060
1061       Standard_Integer aPrevLinkInfo = aPolygon.Last();
1062       const BRepMesh_Edge& aPrevLink = GetEdge( Abs( aPrevLinkInfo ) );
1063
1064       if( aPrevLinkInfo > 0 )
1065       {
1066         aStartNode = aPrevLink.FirstNode();
1067         aPivotNode = aPrevLink.LastNode();
1068       }
1069       else
1070       {
1071         aStartNode = aPrevLink.LastNode();
1072         aPivotNode = aPrevLink.FirstNode();
1073       }
1074
1075       aPivotVertex = GetVertex( aPivotNode );
1076       aRefLinkDir =
1077         aPivotVertex.Coord() - GetVertex( aStartNode ).Coord();
1078
1079       isSkipLeprous = Standard_False;
1080     }
1081   }
1082
1083   if ( aPolygon.Length() < 3 )
1084     return Standard_False;
1085
1086   cleanupPolygon( aPolygon, aBoxes );
1087   meshPolygon   ( aPolygon, aBoxes, theSkipped );
1088
1089   return Standard_True;
1090 }
1091
1092 //=======================================================================
1093 //function : findNextPolygonLink
1094 //purpose  : Find next link starting from the given node and has maximum
1095 //           angle respect the given reference link.
1096 //           Each time the next link is found other neighbor links at the
1097 //           pivot node are marked as leprous and will be excluded from
1098 //           consideration next time until a hanging end is occurred.
1099 //=======================================================================
1100 Standard_Integer BRepMesh_Delaun::findNextPolygonLink(
1101   const Standard_Integer&               theFirstNode,
1102   const Standard_Integer&               thePivotNode,
1103   const BRepMesh_Vertex&                thePivotVertex,
1104   const gp_Vec2d&                       theRefLinkDir,
1105   const IMeshData::SequenceOfBndB2d&    theBoxes,
1106   const IMeshData::SequenceOfInteger&   thePolygon,
1107   const Handle(IMeshData::MapOfInteger) theSkipped,
1108   const Standard_Boolean&               isSkipLeprous,
1109   IMeshData::MapOfInteger&              theLeprousLinks,
1110   IMeshData::MapOfInteger&              theDeadLinks,
1111   Standard_Integer&                     theNextPivotNode,
1112   gp_Vec2d&                             theNextLinkDir,
1113   Bnd_B2d&                              theNextLinkBndBox )
1114 {
1115   // Find the next link having the greatest angle
1116   // respect to a direction of a reference one
1117   Standard_Real aMaxAngle = RealFirst();
1118
1119   Standard_Integer aNextLinkId = 0;
1120   IMeshData::ListOfInteger::Iterator aLinkIt( myMeshData->LinksConnectedTo( thePivotNode ) );
1121   for ( ; aLinkIt.More(); aLinkIt.Next() )
1122   {
1123     const Standard_Integer& aNeighbourLinkInfo = aLinkIt.Value();
1124     Standard_Integer        aNeighbourLinkId   = Abs( aNeighbourLinkInfo );
1125
1126     if ( theDeadLinks.Contains( aNeighbourLinkId ) ||
1127        ( !theSkipped.IsNull() && theSkipped->Contains( aNeighbourLinkId ) ) )
1128     {
1129       continue;
1130     }
1131
1132     Standard_Boolean isLeprous = theLeprousLinks.Contains( aNeighbourLinkId );
1133     if ( isSkipLeprous && isLeprous )
1134       continue;
1135
1136     const BRepMesh_Edge& aNeighbourLink = GetEdge( aNeighbourLinkId );
1137
1138     // Determine whether the link belongs to the mesh
1139     if ( aNeighbourLink.Movability() == BRepMesh_Free &&
1140          myMeshData->ElementsConnectedTo( aNeighbourLinkInfo ).IsEmpty() )
1141     {
1142       theDeadLinks.Add( aNeighbourLinkId );
1143       continue;
1144     }
1145
1146     Standard_Integer anOtherNode = aNeighbourLink.FirstNode();
1147     if ( anOtherNode == thePivotNode )
1148       anOtherNode = aNeighbourLink.LastNode();
1149
1150     gp_Vec2d aCurLinkDir( GetVertex( anOtherNode ).Coord() -
1151       thePivotVertex.Coord() );
1152
1153     if ( aCurLinkDir.SquareMagnitude() < Precision2 )
1154     {
1155       theDeadLinks.Add( aNeighbourLinkId );
1156       continue;
1157     }
1158
1159     if ( !isLeprous )
1160       theLeprousLinks.Add( aNeighbourLinkId );
1161
1162     Standard_Real    anAngle    = theRefLinkDir.Angle( aCurLinkDir );
1163     Standard_Boolean isFrontier =
1164       ( aNeighbourLink.Movability() == BRepMesh_Frontier );
1165
1166     Standard_Boolean isCheckPointOnEdge = Standard_True;
1167     if ( isFrontier )
1168     {
1169       if ( Abs( Abs(anAngle) - M_PI ) < Precision::Angular() )
1170       {
1171         // Glued constrains - don't check intersection
1172         isCheckPointOnEdge = Standard_False;
1173         anAngle            = Abs( anAngle );
1174       }
1175     }
1176
1177     if (anAngle <= aMaxAngle)
1178       continue;
1179
1180     Standard_Boolean isCheckEndPoints = ( anOtherNode != theFirstNode );
1181
1182     Bnd_B2d aBox;
1183     Standard_Boolean isNotIntersect =
1184       checkIntersection( aNeighbourLink, thePolygon, theBoxes,
1185       isCheckEndPoints, isCheckPointOnEdge, Standard_True, aBox );
1186
1187     if( isNotIntersect )
1188     {
1189       aMaxAngle         = anAngle;
1190
1191       theNextLinkDir    = aCurLinkDir;
1192       theNextPivotNode  = anOtherNode;
1193       theNextLinkBndBox = aBox;
1194
1195       aNextLinkId       = ( aNeighbourLink.FirstNode() == thePivotNode ) ?
1196         aNeighbourLinkId : -aNeighbourLinkId;
1197     }
1198   }
1199
1200   return aNextLinkId;
1201 }
1202
1203 //=======================================================================
1204 //function : checkIntersection
1205 //purpose  : Check is the given link intersects the polygon boundaries.
1206 //           Returns bounding box for the given link through the
1207 //           <theLinkBndBox> parameter.
1208 //=======================================================================
1209 Standard_Boolean BRepMesh_Delaun::checkIntersection(
1210   const BRepMesh_Edge&                theLink,
1211   const IMeshData::SequenceOfInteger& thePolygon,
1212   const IMeshData::SequenceOfBndB2d&  thePolyBoxes,
1213   const Standard_Boolean              isConsiderEndPointTouch,
1214   const Standard_Boolean              isConsiderPointOnEdge,
1215   const Standard_Boolean              isSkipLastEdge,
1216   Bnd_B2d&                            theLinkBndBox ) const
1217 {
1218   UpdateBndBox(GetVertex(theLink.FirstNode()).Coord(),
1219     GetVertex(theLink.LastNode()).Coord(), theLinkBndBox);
1220
1221   Standard_Integer aPolyLen = thePolygon.Length();
1222   // Don't check intersection with the last link
1223   if ( isSkipLastEdge )
1224     --aPolyLen;
1225
1226   Standard_Boolean isFrontier =
1227     ( theLink.Movability() == BRepMesh_Frontier );
1228
1229   for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1230   {
1231     if ( !theLinkBndBox.IsOut( thePolyBoxes.Value( aPolyIt ) ) )
1232     {
1233       // intersection is possible...
1234       Standard_Integer aPolyLinkId   = Abs( thePolygon( aPolyIt ) );
1235       const BRepMesh_Edge& aPolyLink = GetEdge( aPolyLinkId );
1236
1237       // skip intersections between frontier edges
1238       if ( aPolyLink.Movability() == BRepMesh_Frontier && isFrontier )
1239         continue;
1240
1241       gp_Pnt2d anIntPnt;
1242       BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( theLink, aPolyLink,
1243         isConsiderEndPointTouch, isConsiderPointOnEdge, anIntPnt );
1244
1245       if ( aIntFlag != BRepMesh_GeomTool::NoIntersection )
1246         return Standard_False;
1247     }
1248   }
1249
1250   // Ok, no intersection
1251   return Standard_True;
1252 }
1253
1254 //=======================================================================
1255 //function : addTriangle
1256 //purpose  : Add a triangle based on the given oriented edges into mesh
1257 //=======================================================================
1258 void BRepMesh_Delaun::addTriangle( const Standard_Integer (&theEdgesId)[3],
1259                                    const Standard_Boolean (&theEdgesOri)[3],
1260                                    const Standard_Integer (&theNodesId)[3] )
1261 {
1262   Standard_Integer aNewTriangleId =
1263     myMeshData->AddElement(BRepMesh_Triangle(theEdgesId,
1264       theEdgesOri, BRepMesh_Free));
1265
1266   Standard_Boolean isAdded = Standard_True;
1267   if (myInitCircles)
1268   {
1269     isAdded = myCircles.Bind(
1270       aNewTriangleId,
1271       GetVertex( theNodesId[0] ).Coord(),
1272       GetVertex( theNodesId[1] ).Coord(),
1273       GetVertex( theNodesId[2] ).Coord() );
1274   }
1275
1276   if ( !isAdded )
1277     myMeshData->RemoveElement( aNewTriangleId );
1278 }
1279
1280 //=======================================================================
1281 //function : cleanupPolygon
1282 //purpose  : Remove internal triangles from the given polygon
1283 //=======================================================================
1284 void BRepMesh_Delaun::cleanupPolygon(const IMeshData::SequenceOfInteger& thePolygon,
1285                                      const IMeshData::SequenceOfBndB2d&  thePolyBoxes )
1286 {
1287   Standard_Integer aPolyLen = thePolygon.Length();
1288   if ( aPolyLen < 3 )
1289     return;
1290
1291   Handle(NCollection_IncAllocator) aAllocator =
1292     new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
1293
1294   IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
1295   IMeshData::MapOfInteger    anIgnoredEdges;
1296   IMeshData::MapOfInteger    aPolyVerticesFindMap;
1297   IMeshData::VectorOfInteger aPolyVertices(256, aAllocator);
1298   // Collect boundary vertices of the polygon
1299   for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1300   {
1301     Standard_Integer aPolyEdgeInfo = thePolygon( aPolyIt );
1302     Standard_Integer aPolyEdgeId   = Abs( aPolyEdgeInfo );
1303     anIgnoredEdges.Add( aPolyEdgeId );
1304
1305     Standard_Boolean isForward = ( aPolyEdgeInfo > 0 );
1306     const BRepMesh_PairOfIndex& aPair =
1307       myMeshData->ElementsConnectedTo( aPolyEdgeId );
1308
1309     Standard_Integer anElemIt = 1;
1310     for ( ; anElemIt <= aPair.Extent(); ++anElemIt )
1311     {
1312       Standard_Integer anElemId = aPair.Index( anElemIt );
1313       if ( anElemId < 0 )
1314         continue;
1315
1316       const BRepMesh_Triangle& aElement = GetTriangle(anElemId);
1317       const Standard_Integer(&anEdges)[3] = aElement.myEdges;
1318       const Standard_Boolean(&anEdgesOri)[3] = aElement.myOrientations;
1319
1320       Standard_Integer isTriangleFound = Standard_False;
1321       for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
1322       {
1323         if ( anEdges[anEdgeIt]    == aPolyEdgeId &&
1324              anEdgesOri[anEdgeIt] == isForward )
1325         {
1326           isTriangleFound = Standard_True;
1327           deleteTriangle( anElemId, aLoopEdges );
1328           break;
1329         }
1330       }
1331
1332       if ( isTriangleFound )
1333         break;
1334     }
1335
1336     // Skip a neighbor link to extract unique vertices each time
1337     if ( aPolyIt % 2 )
1338     {
1339       const BRepMesh_Edge& aPolyEdge = GetEdge( aPolyEdgeId );
1340       Standard_Integer aFirstVertex  = aPolyEdge.FirstNode();
1341       Standard_Integer aLastVertex   = aPolyEdge.LastNode();
1342
1343       aPolyVerticesFindMap.Add( aFirstVertex );
1344       aPolyVerticesFindMap.Add( aLastVertex );
1345
1346       if ( aPolyEdgeInfo > 0 )
1347       {
1348         aPolyVertices.Append( aFirstVertex );
1349         aPolyVertices.Append( aLastVertex );
1350       }
1351       else
1352       {
1353         aPolyVertices.Append( aLastVertex );
1354         aPolyVertices.Append( aFirstVertex );
1355       }
1356     }
1357   }
1358
1359   // Make closed sequence
1360   if ( aPolyVertices.First() != aPolyVertices.Last() )
1361     aPolyVertices.Append( aPolyVertices.First() );
1362
1363   IMeshData::MapOfInteger aSurvivedLinks( anIgnoredEdges );
1364
1365   Standard_Integer aPolyVertIt          = 0;
1366   Standard_Integer anUniqueVerticesNum  = aPolyVertices.Length() - 1;
1367   for ( ; aPolyVertIt < anUniqueVerticesNum; ++aPolyVertIt )
1368   {
1369     killTrianglesAroundVertex( aPolyVertices( aPolyVertIt ),
1370       aPolyVertices, aPolyVerticesFindMap, thePolygon,
1371       thePolyBoxes, aSurvivedLinks, aLoopEdges );
1372   }
1373
1374   IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
1375   for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
1376   {
1377     const Standard_Integer& aLoopEdgeId = aLoopEdgesIt.Key();
1378     if ( anIgnoredEdges.Contains( aLoopEdgeId ) )
1379       continue;
1380
1381     if ( myMeshData->ElementsConnectedTo( aLoopEdgeId ).IsEmpty() )
1382       myMeshData->RemoveLink( aLoopEdgesIt.Key() );
1383   }
1384 }
1385
1386 //=======================================================================
1387 //function : killTrianglesAroundVertex
1388 //purpose  : Remove all triangles and edges that are placed
1389 //           inside the polygon or crossed it.
1390 //=======================================================================
1391 void BRepMesh_Delaun::killTrianglesAroundVertex(
1392   const Standard_Integer              theZombieNodeId,
1393   const IMeshData::VectorOfInteger&   thePolyVertices,
1394   const IMeshData::MapOfInteger&      thePolyVerticesFindMap,
1395   const IMeshData::SequenceOfInteger& thePolygon,
1396   const IMeshData::SequenceOfBndB2d&  thePolyBoxes,
1397   IMeshData::MapOfInteger&            theSurvivedLinks,
1398   IMeshData::MapOfIntegerInteger&     theLoopEdges )
1399 {
1400   IMeshData::ListOfInteger::Iterator aNeighborsIt =
1401     myMeshData->LinksConnectedTo( theZombieNodeId );
1402
1403   // Try to infect neighbor nodes
1404   IMeshData::VectorOfInteger aVictimNodes;
1405   for ( ; aNeighborsIt.More(); aNeighborsIt.Next() )
1406   {
1407     const Standard_Integer& aNeighborLinkId = aNeighborsIt.Value();
1408     if ( theSurvivedLinks.Contains( aNeighborLinkId ) )
1409       continue;
1410
1411     const BRepMesh_Edge& aNeighborLink = GetEdge( aNeighborLinkId );
1412     if ( aNeighborLink.Movability() == BRepMesh_Frontier )
1413     {
1414       // Though, if it lies onto the polygon boundary -
1415       // take its triangles
1416       Bnd_B2d aBox;
1417       Standard_Boolean isNotIntersect =
1418         checkIntersection( aNeighborLink, thePolygon,
1419         thePolyBoxes, Standard_False, Standard_True,
1420         Standard_False, aBox );
1421
1422       if ( isNotIntersect )
1423       {
1424         // Don't touch it
1425         theSurvivedLinks.Add( aNeighborLinkId );
1426         continue;
1427       }
1428     }
1429     else
1430     {
1431       Standard_Integer anOtherNode = aNeighborLink.FirstNode();
1432       if ( anOtherNode == theZombieNodeId )
1433         anOtherNode = aNeighborLink.LastNode();
1434
1435       // Possible sacrifice
1436       if ( !thePolyVerticesFindMap.Contains( anOtherNode ) )
1437       {
1438         if ( isVertexInsidePolygon( anOtherNode, thePolyVertices ) )
1439         {
1440           // Got you!
1441           aVictimNodes.Append( anOtherNode );
1442         }
1443         else
1444         {
1445           // Lucky. But it may intersect the polygon boundary.
1446           // Let's check it!
1447           killTrianglesOnIntersectingLinks( aNeighborLinkId,
1448             aNeighborLink, anOtherNode, thePolygon,
1449             thePolyBoxes, theSurvivedLinks, theLoopEdges );
1450
1451           continue;
1452         }
1453       }
1454     }
1455
1456     // Add link to the survivors to avoid cycling
1457     theSurvivedLinks.Add( aNeighborLinkId );
1458     killLinkTriangles( aNeighborLinkId, theLoopEdges );
1459   }
1460
1461   // Go and do your job!
1462   IMeshData::VectorOfInteger::Iterator aVictimIt( aVictimNodes );
1463   for ( ; aVictimIt.More(); aVictimIt.Next() )
1464   {
1465     killTrianglesAroundVertex( aVictimIt.Value(), thePolyVertices,
1466       thePolyVerticesFindMap, thePolygon, thePolyBoxes,
1467       theSurvivedLinks, theLoopEdges );
1468   }
1469 }
1470
1471 //=======================================================================
1472 //function : isVertexInsidePolygon
1473 //purpose  : Checks is the given vertex lies inside the polygon
1474 //=======================================================================
1475 Standard_Boolean BRepMesh_Delaun::isVertexInsidePolygon(
1476   const Standard_Integer&           theVertexId,
1477   const IMeshData::VectorOfInteger& thePolygonVertices ) const
1478 {
1479   Standard_Integer aPolyLen = thePolygonVertices.Length();
1480   if ( aPolyLen < 3 )
1481     return Standard_False;
1482
1483
1484   const gp_XY aCenterPointXY = GetVertex( theVertexId ).Coord();
1485
1486   const BRepMesh_Vertex& aFirstVertex = GetVertex( thePolygonVertices( 0 ) );
1487   gp_Vec2d aPrevVertexDir( aFirstVertex.Coord() - aCenterPointXY );
1488   if ( aPrevVertexDir.SquareMagnitude() < Precision2 )
1489     return Standard_True;
1490
1491   Standard_Real aTotalAng = 0.0;
1492   for ( Standard_Integer aPolyIt = 1; aPolyIt < aPolyLen; ++aPolyIt )
1493   {
1494     const BRepMesh_Vertex& aPolyVertex = GetVertex( thePolygonVertices( aPolyIt ) );
1495
1496     gp_Vec2d aCurVertexDir( aPolyVertex.Coord() - aCenterPointXY );
1497     if ( aCurVertexDir.SquareMagnitude() < Precision2 )
1498       return Standard_True;
1499
1500     aTotalAng     += aCurVertexDir.Angle( aPrevVertexDir );
1501     aPrevVertexDir = aCurVertexDir;
1502   }
1503
1504   if ( Abs( Angle2PI - aTotalAng ) > Precision::Angular() )
1505     return Standard_False;
1506
1507   return Standard_True;
1508 }
1509
1510 //=======================================================================
1511 //function : killTrianglesOnIntersectingLinks
1512 //purpose  : Checks is the given link crosses the polygon boundary.
1513 //           If yes, kills its triangles and checks neighbor links on
1514 //           boundary intersection. Does nothing elsewhere.
1515 //=======================================================================
1516 void BRepMesh_Delaun::killTrianglesOnIntersectingLinks(
1517   const Standard_Integer&             theLinkToCheckId,
1518   const BRepMesh_Edge&                theLinkToCheck,
1519   const Standard_Integer&             theEndPoint,
1520   const IMeshData::SequenceOfInteger& thePolygon,
1521   const IMeshData::SequenceOfBndB2d&  thePolyBoxes,
1522   IMeshData::MapOfInteger&            theSurvivedLinks,
1523   IMeshData::MapOfIntegerInteger&     theLoopEdges )
1524 {
1525   if ( theSurvivedLinks.Contains( theLinkToCheckId ) )
1526     return;
1527
1528   Bnd_B2d aBox;
1529   Standard_Boolean isNotIntersect =
1530     checkIntersection( theLinkToCheck, thePolygon,
1531       thePolyBoxes, Standard_False, Standard_False,
1532       Standard_False, aBox );
1533
1534   theSurvivedLinks.Add( theLinkToCheckId );
1535
1536   if ( isNotIntersect )
1537     return;
1538
1539   killLinkTriangles( theLinkToCheckId, theLoopEdges );
1540
1541   IMeshData::ListOfInteger::Iterator aNeighborsIt(
1542     myMeshData->LinksConnectedTo(theEndPoint));
1543
1544   for ( ; aNeighborsIt.More(); aNeighborsIt.Next() )
1545   {
1546     const Standard_Integer& aNeighborLinkId = aNeighborsIt.Value();
1547     const BRepMesh_Edge&    aNeighborLink   = GetEdge( aNeighborLinkId );
1548     Standard_Integer anOtherNode = aNeighborLink.FirstNode();
1549     if ( anOtherNode == theEndPoint )
1550       anOtherNode = aNeighborLink.LastNode();
1551
1552     killTrianglesOnIntersectingLinks( aNeighborLinkId,
1553       aNeighborLink, anOtherNode, thePolygon,
1554       thePolyBoxes, theSurvivedLinks, theLoopEdges );
1555   }
1556 }
1557
1558 //=======================================================================
1559 //function : killLinkTriangles
1560 //purpose  : Kill triangles bound to the given link.
1561 //=======================================================================
1562 void BRepMesh_Delaun::killLinkTriangles(
1563   const Standard_Integer&         theLinkId,
1564   IMeshData::MapOfIntegerInteger& theLoopEdges )
1565 {
1566   const BRepMesh_PairOfIndex& aPair =
1567     myMeshData->ElementsConnectedTo( theLinkId );
1568
1569   Standard_Integer anElemNb = aPair.Extent();
1570   for ( Standard_Integer aPairIt = 1; aPairIt <= anElemNb; ++aPairIt )
1571   {
1572     Standard_Integer anElemId = aPair.FirstIndex();
1573     if ( anElemId < 0 )
1574       continue;
1575
1576     deleteTriangle( anElemId, theLoopEdges );
1577   }
1578 }
1579
1580 //=======================================================================
1581 //function : getOrientedNodes
1582 //purpose  : Returns start and end nodes of the given edge in respect to
1583 //           its orientation.
1584 //=======================================================================
1585 void BRepMesh_Delaun::getOrientedNodes(const BRepMesh_Edge&   theEdge,
1586                                        const Standard_Boolean isForward,
1587                                        Standard_Integer       *theNodes) const
1588 {
1589   if ( isForward )
1590   {
1591     theNodes[0] = theEdge.FirstNode();
1592     theNodes[1] = theEdge.LastNode();
1593   }
1594   else
1595   {
1596     theNodes[0] = theEdge.LastNode();
1597     theNodes[1] = theEdge.FirstNode();
1598   }
1599 }
1600
1601 //=======================================================================
1602 //function : processLoop
1603 //purpose  : Processes loop within the given polygon formed by range of
1604 //           its links specified by start and end link indices.
1605 //=======================================================================
1606 void BRepMesh_Delaun::processLoop(const Standard_Integer              theLinkFrom,
1607                                   const Standard_Integer              theLinkTo,
1608                                   const IMeshData::SequenceOfInteger& thePolygon,
1609                                   const IMeshData::SequenceOfBndB2d&  thePolyBoxes)
1610 {
1611   Standard_Integer aNbOfLinksInLoop = theLinkTo - theLinkFrom - 1;
1612   if ( aNbOfLinksInLoop < 3 )
1613     return;
1614
1615   IMeshData::SequenceOfInteger aPolygon;
1616   IMeshData::SequenceOfBndB2d  aPolyBoxes;
1617   for ( ; aNbOfLinksInLoop > 0; --aNbOfLinksInLoop )
1618   {
1619     Standard_Integer aLoopLinkIndex = theLinkFrom + aNbOfLinksInLoop;
1620     aPolygon  .Prepend( thePolygon  ( aLoopLinkIndex ) );
1621     aPolyBoxes.Prepend( thePolyBoxes( aLoopLinkIndex ) );
1622   }
1623   meshPolygon( aPolygon, aPolyBoxes );
1624 }
1625
1626 //=======================================================================
1627 //function : createAndReplacePolygonLink
1628 //purpose  : Creates new link based on the given nodes and updates the
1629 //           given polygon.
1630 //=======================================================================
1631 Standard_Integer BRepMesh_Delaun::createAndReplacePolygonLink(
1632   const Standard_Integer       *theNodes,
1633   const gp_Pnt2d               *thePnts,
1634   const Standard_Integer        theRootIndex,
1635   const ReplaceFlag             theReplaceFlag,
1636   IMeshData::SequenceOfInteger& thePolygon,
1637   IMeshData::SequenceOfBndB2d&  thePolyBoxes )
1638 {
1639   Standard_Integer aNewEdgeId =
1640     myMeshData->AddLink( BRepMesh_Edge(
1641     theNodes[0], theNodes[1], BRepMesh_Free ) );
1642
1643   Bnd_B2d aNewBox;
1644   UpdateBndBox(thePnts[0].Coord(), thePnts[1].Coord(), aNewBox);
1645
1646   switch ( theReplaceFlag )
1647   {
1648   case BRepMesh_Delaun::Replace:
1649     thePolygon  .SetValue( theRootIndex, aNewEdgeId );
1650     thePolyBoxes.SetValue( theRootIndex, aNewBox );
1651     break;
1652
1653   case BRepMesh_Delaun::InsertAfter:
1654     thePolygon  .InsertAfter( theRootIndex, aNewEdgeId );
1655     thePolyBoxes.InsertAfter( theRootIndex, aNewBox );
1656     break;
1657
1658   case BRepMesh_Delaun::InsertBefore:
1659     thePolygon  .InsertBefore( theRootIndex, aNewEdgeId );
1660     thePolyBoxes.InsertBefore( theRootIndex, aNewBox );
1661     break;
1662   }
1663
1664   return aNewEdgeId;
1665 }
1666
1667 //=======================================================================
1668 //function : meshPolygon
1669 //purpose  :
1670 //=======================================================================
1671 void BRepMesh_Delaun::meshPolygon(IMeshData::SequenceOfInteger&   thePolygon,
1672                                   IMeshData::SequenceOfBndB2d&    thePolyBoxes,
1673                                   Handle(IMeshData::MapOfInteger) theSkipped)
1674 {
1675   // Check is the source polygon elementary
1676   if ( meshElementaryPolygon( thePolygon ) )
1677     return;
1678
1679   // Check and correct boundary edges
1680   Standard_Integer aPolyLen = thePolygon.Length();
1681   const Standard_Real aPolyArea      = Abs( polyArea( thePolygon, 1, aPolyLen ) );
1682   const Standard_Real aSmallLoopArea = 0.001 * aPolyArea;
1683   for ( Standard_Integer aPolyIt = 1; aPolyIt < aPolyLen; ++aPolyIt )
1684   {
1685     Standard_Integer aCurEdgeInfo = thePolygon( aPolyIt );
1686     Standard_Integer aCurEdgeId   = Abs( aCurEdgeInfo );
1687     const BRepMesh_Edge* aCurEdge = &GetEdge( aCurEdgeId );
1688     if ( aCurEdge->Movability() != BRepMesh_Frontier )
1689       continue;
1690
1691     Standard_Integer aCurNodes[2];
1692     getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aCurNodes );
1693
1694     gp_Pnt2d aCurPnts[2] = {
1695       GetVertex(aCurNodes[0]).Coord(),
1696       GetVertex(aCurNodes[1]).Coord()
1697     };
1698
1699     gp_Vec2d aCurVec( aCurPnts[0], aCurPnts[1] );
1700
1701     // check further links
1702     Standard_Integer aNextPolyIt = aPolyIt + 1;
1703     for ( ; aNextPolyIt <= aPolyLen; ++aNextPolyIt )
1704     {
1705       Standard_Integer aNextEdgeInfo = thePolygon( aNextPolyIt );
1706       Standard_Integer aNextEdgeId   = Abs( aNextEdgeInfo );
1707       const BRepMesh_Edge* aNextEdge = &GetEdge( aNextEdgeId );
1708       if ( aNextEdge->Movability() != BRepMesh_Frontier )
1709         continue;
1710
1711       Standard_Integer aNextNodes[2];
1712       getOrientedNodes( *aNextEdge, aNextEdgeInfo > 0, aNextNodes );
1713
1714       gp_Pnt2d aNextPnts[2] = {
1715         GetVertex(aNextNodes[0]).Coord(),
1716         GetVertex(aNextNodes[1]).Coord()
1717       };
1718
1719       gp_Pnt2d anIntPnt;
1720       BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( *aCurEdge, *aNextEdge,
1721         Standard_False, Standard_True, anIntPnt );
1722
1723       if ( aIntFlag == BRepMesh_GeomTool::NoIntersection )
1724         continue;
1725
1726       Standard_Boolean isRemoveFromFirst  = Standard_False;
1727       Standard_Boolean isAddReplacingEdge = Standard_True;
1728       Standard_Integer aIndexToRemoveTo   = aNextPolyIt;
1729       if ( aIntFlag == BRepMesh_GeomTool::Cross )
1730       {
1731         Standard_Real aLoopArea = polyArea( thePolygon, aPolyIt + 1, aNextPolyIt );
1732         gp_Vec2d aVec1( anIntPnt, aCurPnts [1] );
1733         gp_Vec2d aVec2( anIntPnt, aNextPnts[0] );
1734
1735         aLoopArea += ( aVec1 ^ aVec2 ) / 2.;
1736         if ( Abs( aLoopArea ) > aSmallLoopArea )
1737         {
1738           aNextNodes[1] = aCurNodes[0];
1739           aNextPnts [1] = aCurPnts [0];
1740
1741           aNextEdgeId = Abs( createAndReplacePolygonLink( aNextNodes, aNextPnts,
1742             aNextPolyIt, BRepMesh_Delaun::Replace, thePolygon, thePolyBoxes ) );
1743
1744           processLoop( aPolyIt, aNextPolyIt, thePolygon, thePolyBoxes );
1745           return;
1746         }
1747
1748         Standard_Real aDist1 = anIntPnt.SquareDistance(aNextPnts[0]);
1749         Standard_Real aDist2 = anIntPnt.SquareDistance(aNextPnts[1]);
1750
1751         // Choose node with lower distance
1752         const Standard_Boolean isCloseToStart = ( aDist1 < aDist2 );
1753         const Standard_Integer aEndPointIndex = isCloseToStart ? 0 : 1;
1754         aCurNodes[1] = aNextNodes[aEndPointIndex];
1755         aCurPnts [1] = aNextPnts [aEndPointIndex];
1756
1757         if ( isCloseToStart )
1758           --aIndexToRemoveTo;
1759
1760         // In this context only intersections between frontier edges
1761         // are possible. If intersection between edges of different
1762         // types occurred - treat this case as invalid (i.e. result
1763         // might not reflect the expectations).
1764         if ( !theSkipped.IsNull() )
1765         {
1766           Standard_Integer aSkippedLinkIt = aPolyIt;
1767           for ( ; aSkippedLinkIt <= aIndexToRemoveTo; ++aSkippedLinkIt )
1768             theSkipped->Add( Abs( thePolygon( aSkippedLinkIt ) ) );
1769         }
1770       }
1771       else if ( aIntFlag == BRepMesh_GeomTool::PointOnSegment )
1772       {
1773         // Identify chopping link
1774         Standard_Boolean isFirstChopping = Standard_False;
1775         Standard_Integer aCheckPointIt = 0;
1776         for ( ; aCheckPointIt < 2; ++aCheckPointIt )
1777         {
1778           gp_Pnt2d& aRefPoint = aCurPnts[aCheckPointIt];
1779           // Check is second link touches the first one
1780           gp_Vec2d aVec1( aRefPoint, aNextPnts[0] );
1781           gp_Vec2d aVec2( aRefPoint, aNextPnts[1] );
1782           if ( Abs( aVec1 ^ aVec2 ) < Precision )
1783           {
1784             isFirstChopping = Standard_True;
1785             break;
1786           }
1787         }
1788
1789         if ( isFirstChopping )
1790         {
1791           // Split second link
1792           isAddReplacingEdge = Standard_False;
1793           isRemoveFromFirst  = ( aCheckPointIt == 0 );
1794
1795           Standard_Integer aSplitLink[3] = {
1796             aNextNodes[0],
1797             aCurNodes [aCheckPointIt],
1798             aNextNodes[1]
1799           };
1800
1801           gp_Pnt2d aSplitPnts[3] = {
1802             aNextPnts[0],
1803             aCurPnts [aCheckPointIt],
1804             aNextPnts[1]
1805           };
1806
1807           Standard_Integer aSplitLinkIt = 0;
1808           for ( ; aSplitLinkIt < 2; ++aSplitLinkIt )
1809           {
1810             createAndReplacePolygonLink( &aSplitLink[aSplitLinkIt],
1811               &aSplitPnts[aSplitLinkIt], aNextPolyIt, ( aSplitLinkIt == 0 ) ?
1812               BRepMesh_Delaun::Replace : BRepMesh_Delaun::InsertAfter,
1813               thePolygon, thePolyBoxes );
1814           }
1815
1816           processLoop( aPolyIt + aCheckPointIt, aIndexToRemoveTo,
1817             thePolygon, thePolyBoxes );
1818         }
1819         else
1820         {
1821           // Split first link
1822           Standard_Integer aSplitLinkNodes[2] = {
1823             aNextNodes[1],
1824             aCurNodes [1]
1825           };
1826
1827           gp_Pnt2d aSplitLinkPnts[2] = {
1828             aNextPnts[1],
1829             aCurPnts [1]
1830           };
1831           createAndReplacePolygonLink( aSplitLinkNodes, aSplitLinkPnts,
1832             aPolyIt, BRepMesh_Delaun::InsertAfter, thePolygon, thePolyBoxes );
1833
1834           aCurNodes[1] = aNextNodes[1];
1835           aCurPnts [1] = aNextPnts [1];
1836           ++aIndexToRemoveTo;
1837
1838           processLoop( aPolyIt + 1, aIndexToRemoveTo,
1839             thePolygon, thePolyBoxes );
1840         }
1841       }
1842       else if ( aIntFlag == BRepMesh_GeomTool::Glued )
1843       {
1844         if ( aCurNodes[1] == aNextNodes[0] )
1845         {
1846           aCurNodes[1] = aNextNodes[1];
1847           aCurPnts [1] = aNextPnts [1];
1848         }
1849         // TODO: Non-adjacent glued links within the polygon
1850       }
1851       else if ( aIntFlag == BRepMesh_GeomTool::Same )
1852       {
1853         processLoop( aPolyIt, aNextPolyIt, thePolygon, thePolyBoxes );
1854
1855         isRemoveFromFirst  = Standard_True;
1856         isAddReplacingEdge = Standard_False;
1857       }
1858       else
1859         continue; // Not supported type
1860
1861       if ( isAddReplacingEdge )
1862       {
1863         aCurEdgeId = Abs( createAndReplacePolygonLink( aCurNodes, aCurPnts,
1864           aPolyIt, BRepMesh_Delaun::Replace, thePolygon, thePolyBoxes ) );
1865
1866         aCurEdge = &GetEdge( aCurEdgeId );
1867         aCurVec  = gp_Vec2d( aCurPnts[0], aCurPnts[1] );
1868       }
1869
1870       Standard_Integer aIndexToRemoveFrom =
1871         isRemoveFromFirst ? aPolyIt : aPolyIt + 1;
1872
1873       thePolygon  .Remove( aIndexToRemoveFrom, aIndexToRemoveTo );
1874       thePolyBoxes.Remove( aIndexToRemoveFrom, aIndexToRemoveTo );
1875
1876       aPolyLen = thePolygon.Length();
1877       if ( isRemoveFromFirst )
1878       {
1879         --aPolyIt;
1880         break;
1881       }
1882
1883       aNextPolyIt = aPolyIt;
1884     }
1885   }
1886
1887   IMeshData::SequenceOfInteger* aPolygon1   = &thePolygon;
1888   IMeshData::SequenceOfBndB2d*  aPolyBoxes1 = &thePolyBoxes;
1889
1890   Handle(IMeshData::SequenceOfInteger) aPolygon2   = new IMeshData::SequenceOfInteger;
1891   Handle(IMeshData::SequenceOfBndB2d)  aPolyBoxes2 = new IMeshData::SequenceOfBndB2d;
1892
1893   NCollection_Sequence<Handle(IMeshData::SequenceOfInteger)> aPolyStack;
1894   NCollection_Sequence<Handle(IMeshData::SequenceOfBndB2d)>  aPolyBoxStack;
1895   for (;;)
1896   {
1897     decomposeSimplePolygon(*aPolygon1, *aPolyBoxes1, *aPolygon2, *aPolyBoxes2);
1898     if (!aPolygon2->IsEmpty())
1899     {
1900       aPolyStack.Append(aPolygon2);
1901       aPolyBoxStack.Append(aPolyBoxes2);
1902
1903       aPolygon2   = new IMeshData::SequenceOfInteger;
1904       aPolyBoxes2 = new IMeshData::SequenceOfBndB2d;
1905     }
1906
1907     if (aPolygon1->IsEmpty())
1908     {
1909       if (!aPolyStack.IsEmpty() && aPolygon1 == &(*aPolyStack.First()))
1910       {
1911         aPolyStack.Remove(1);
1912         aPolyBoxStack.Remove(1);
1913       }
1914
1915       if (aPolyStack.IsEmpty())
1916         break;
1917
1918       aPolygon1   = &(*aPolyStack.ChangeFirst());
1919       aPolyBoxes1 = &(*aPolyBoxStack.ChangeFirst());
1920     }
1921   }
1922 }
1923
1924 //=======================================================================
1925 //function : meshElementaryPolygon
1926 //purpose  : Triangulation of closed polygon containing only three edges.
1927 //=======================================================================
1928 Standard_Boolean BRepMesh_Delaun::meshElementaryPolygon(
1929   const IMeshData::SequenceOfInteger& thePolygon)
1930 {
1931   Standard_Integer aPolyLen = thePolygon.Length();
1932   if ( aPolyLen < 3 )
1933     return Standard_True;
1934   else if ( aPolyLen > 3 )
1935     return Standard_False;
1936
1937   // Just create a triangle
1938   Standard_Integer anEdges[3];
1939   Standard_Boolean anEdgesOri[3];
1940
1941   for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
1942   {
1943     Standard_Integer anEdgeInfo = thePolygon( anEdgeIt + 1 );
1944     anEdges[anEdgeIt]           = Abs( anEdgeInfo );
1945     anEdgesOri[anEdgeIt]        = ( anEdgeInfo > 0 );
1946   }
1947
1948   const BRepMesh_Edge& anEdge1 = GetEdge( anEdges[0] );
1949   const BRepMesh_Edge& anEdge2 = GetEdge( anEdges[1] );
1950
1951   Standard_Integer aNodes[3] = { anEdge1.FirstNode(),
1952                                  anEdge1.LastNode(),
1953                                  anEdge2.FirstNode() };
1954   if ( aNodes[2] == aNodes[0] ||
1955        aNodes[2] == aNodes[1] )
1956   {
1957     aNodes[2] = anEdge2.LastNode();
1958   }
1959
1960   addTriangle( anEdges, anEdgesOri, aNodes );
1961   return Standard_True;
1962 }
1963
1964 //=======================================================================
1965 //function : meshSimplePolygon
1966 //purpose  :
1967 //=======================================================================
1968 void BRepMesh_Delaun::decomposeSimplePolygon(
1969   IMeshData::SequenceOfInteger& thePolygon,
1970   IMeshData::SequenceOfBndB2d&  thePolyBoxes,
1971   IMeshData::SequenceOfInteger& thePolygonCut,
1972   IMeshData::SequenceOfBndB2d&  thePolyBoxesCut)
1973 {
1974   // Check is the given polygon elementary
1975   if ( meshElementaryPolygon( thePolygon ) )
1976   {
1977     thePolygon.Clear();
1978     thePolyBoxes.Clear();
1979     return;
1980   }
1981
1982   // Polygon contains more than 3 links
1983   Standard_Integer aFirstEdgeInfo = thePolygon(1);
1984   const BRepMesh_Edge& aFirstEdge = GetEdge( Abs( aFirstEdgeInfo ) );
1985
1986   Standard_Integer aNodes[3];
1987   getOrientedNodes( aFirstEdge, aFirstEdgeInfo > 0, aNodes );
1988
1989   gp_Pnt2d aRefVertices[3];
1990   aRefVertices[0] = GetVertex( aNodes[0] ).Coord();
1991   aRefVertices[1] = GetVertex( aNodes[1] ).Coord();
1992
1993   gp_Vec2d aRefEdgeDir( aRefVertices[0], aRefVertices[1] );
1994
1995   Standard_Real aRefEdgeLen = aRefEdgeDir.Magnitude();
1996   if ( aRefEdgeLen < Precision )
1997   {
1998     thePolygon.Clear();
1999     thePolyBoxes.Clear();
2000     return;
2001   }
2002
2003   aRefEdgeDir /= aRefEdgeLen;
2004
2005   // Find a point with minimum distance respect
2006   // the end of reference link
2007   Standard_Integer aUsedLinkId = 0;
2008   Standard_Real    aOptAngle   = 0.0;
2009   Standard_Real    aMinDist    = RealLast();
2010   Standard_Integer aPivotNode  = aNodes[1];
2011   Standard_Integer aPolyLen    = thePolygon.Length();
2012   for ( Standard_Integer aLinkIt = 3; aLinkIt <= aPolyLen; ++aLinkIt )
2013   {
2014     Standard_Integer aLinkInfo = thePolygon( aLinkIt );
2015     const BRepMesh_Edge& aNextEdge = GetEdge( Abs( aLinkInfo ) );
2016
2017     aPivotNode = aLinkInfo > 0 ?
2018       aNextEdge.FirstNode() :
2019       aNextEdge.LastNode();
2020
2021     // We have end points touch case in the polygon - ignore it
2022     if (aPivotNode == aNodes[1])
2023       continue;
2024
2025     gp_Pnt2d aPivotVertex = GetVertex( aPivotNode ).Coord();
2026     gp_Vec2d aDistanceDir( aRefVertices[1], aPivotVertex );
2027
2028     Standard_Real aDist     = aRefEdgeDir ^ aDistanceDir;
2029     Standard_Real aAngle    = Abs( aRefEdgeDir.Angle(aDistanceDir) );
2030     Standard_Real anAbsDist = Abs( aDist );
2031     if (anAbsDist < Precision || aDist < 0.)
2032       continue;
2033
2034     if ( ( anAbsDist >= aMinDist                             ) &&
2035          ( aAngle <= aOptAngle || aAngle > AngDeviation90Deg ) )
2036     {
2037       continue;
2038     }
2039
2040     // Check is the test link crosses the polygon boundaries
2041     Standard_Boolean isIntersect = Standard_False;
2042     for ( Standard_Integer aRefLinkNodeIt = 0; aRefLinkNodeIt < 2; ++aRefLinkNodeIt )
2043     {
2044       const Standard_Integer& aLinkFirstNode   = aNodes[aRefLinkNodeIt];
2045       const gp_Pnt2d&         aLinkFirstVertex = aRefVertices[aRefLinkNodeIt];
2046
2047       Bnd_B2d aBox;
2048       UpdateBndBox(aLinkFirstVertex.Coord(), aPivotVertex.Coord(), aBox);
2049
2050       BRepMesh_Edge aCheckLink( aLinkFirstNode, aPivotNode, BRepMesh_Free );
2051
2052       Standard_Integer aCheckLinkIt = 2;
2053       for ( ; aCheckLinkIt <= aPolyLen; ++aCheckLinkIt )
2054       {
2055         if( aCheckLinkIt == aLinkIt )
2056           continue;
2057
2058         if ( !aBox.IsOut( thePolyBoxes.Value( aCheckLinkIt ) ) )
2059         {
2060           const BRepMesh_Edge& aPolyLink =
2061             GetEdge( Abs( thePolygon( aCheckLinkIt ) ) );
2062
2063           if ( aCheckLink.IsEqual( aPolyLink ) )
2064             continue;
2065
2066           // intersection is possible...
2067           gp_Pnt2d anIntPnt;
2068           BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( aCheckLink, aPolyLink,
2069             Standard_False, Standard_False, anIntPnt );
2070
2071           if( aIntFlag != BRepMesh_GeomTool::NoIntersection )
2072           {
2073             isIntersect = Standard_True;
2074             break;
2075           }
2076         }
2077       }
2078
2079       if ( isIntersect )
2080         break;
2081     }
2082
2083     if( isIntersect )
2084       continue;
2085
2086
2087     aOptAngle       = aAngle;
2088     aMinDist        = anAbsDist;
2089     aNodes[2]       = aPivotNode;
2090     aRefVertices[2] = aPivotVertex;
2091     aUsedLinkId     = aLinkIt;
2092   }
2093
2094   if ( aUsedLinkId == 0 )
2095   {
2096     thePolygon.Clear();
2097     thePolyBoxes.Clear();
2098     return;
2099   }
2100
2101
2102   BRepMesh_Edge aNewEdges[2] = {
2103     BRepMesh_Edge( aNodes[1], aNodes[2], BRepMesh_Free ),
2104     BRepMesh_Edge( aNodes[2], aNodes[0], BRepMesh_Free ) };
2105
2106   Standard_Integer aNewEdgesInfo[3] = {
2107     aFirstEdgeInfo,
2108     myMeshData->AddLink( aNewEdges[0] ),
2109     myMeshData->AddLink( aNewEdges[1] ) };
2110
2111   Standard_Integer anEdges[3];
2112   Standard_Boolean anEdgesOri[3];
2113   for ( Standard_Integer aTriEdgeIt = 0; aTriEdgeIt < 3; ++aTriEdgeIt )
2114   {
2115     const Standard_Integer& anEdgeInfo = aNewEdgesInfo[aTriEdgeIt];
2116     anEdges[aTriEdgeIt]    = Abs( anEdgeInfo );
2117     anEdgesOri[aTriEdgeIt] = anEdgeInfo > 0;
2118   }
2119   addTriangle( anEdges, anEdgesOri, aNodes );
2120
2121   if (aUsedLinkId == 3)
2122   {
2123     thePolygon.Remove  ( 1 );
2124     thePolyBoxes.Remove( 1 );
2125
2126     thePolygon.SetValue( 1, -aNewEdgesInfo[2] );
2127
2128     Bnd_B2d aBox;
2129     UpdateBndBox(aRefVertices[0].Coord(), aRefVertices[2].Coord(), aBox);
2130     thePolyBoxes.SetValue( 1, aBox );
2131   }
2132   else
2133   {
2134     // Create triangle and split the source polygon on two
2135     // parts (if possible) and mesh each part as independent
2136     // polygon.
2137     if ( aUsedLinkId < aPolyLen )
2138     {
2139       thePolygon.Split(aUsedLinkId, thePolygonCut);
2140       thePolygonCut.Prepend( -aNewEdgesInfo[2] );
2141       thePolyBoxes.Split(aUsedLinkId, thePolyBoxesCut);
2142
2143       Bnd_B2d aBox;
2144       UpdateBndBox(aRefVertices[0].Coord(), aRefVertices[2].Coord(), aBox);
2145       thePolyBoxesCut.Prepend( aBox );
2146     }
2147     else
2148     {
2149       thePolygon.Remove  ( aPolyLen );
2150       thePolyBoxes.Remove( aPolyLen );
2151     }
2152
2153     thePolygon.SetValue( 1, -aNewEdgesInfo[1] );
2154
2155     Bnd_B2d aBox;
2156     UpdateBndBox(aRefVertices[1].Coord(), aRefVertices[2].Coord(), aBox);
2157     thePolyBoxes.SetValue( 1, aBox );
2158   }
2159 }
2160
2161 //=======================================================================
2162 //function : RemoveVertex
2163 //purpose  : Removes a vertex from the triangulation
2164 //=======================================================================
2165 void BRepMesh_Delaun::RemoveVertex( const BRepMesh_Vertex& theVertex )
2166 {
2167   BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
2168   aSelector.NeighboursOf( theVertex );
2169
2170   IMeshData::MapOfIntegerInteger aLoopEdges;//( 10, myMeshData->Allocator() );
2171
2172   // Loop on triangles to be destroyed :
2173   IMeshData::IteratorOfMapOfInteger aTriangleIt( aSelector.Elements() );
2174   for ( ; aTriangleIt.More(); aTriangleIt.Next() )
2175     deleteTriangle( aTriangleIt.Key(), aLoopEdges );
2176
2177   IMeshData::SequenceOfBndB2d  aBoxes;
2178   IMeshData::SequenceOfInteger aPolygon;
2179   Standard_Integer aLoopEdgesCount = aLoopEdges.Extent();
2180   IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
2181
2182   if ( aLoopEdgesIt.More() )
2183   {
2184     const BRepMesh_Edge& anEdge = GetEdge( aLoopEdgesIt.Key() );
2185     Standard_Integer aFirstNode = anEdge.FirstNode();
2186     Standard_Integer aLastNode;
2187     Standard_Integer aPivotNode = anEdge.LastNode();
2188     Standard_Integer anEdgeId   = aLoopEdgesIt.Key();
2189
2190     Standard_Boolean isPositive = aLoopEdges( anEdgeId ) != 0;
2191     if ( !isPositive )
2192     {
2193       Standard_Integer aTmp;
2194       aTmp       = aFirstNode;
2195       aFirstNode = aPivotNode;
2196       aPivotNode = aTmp;
2197
2198       aPolygon.Append( -anEdgeId );
2199     }
2200     else
2201       aPolygon.Append( anEdgeId );
2202
2203     fillBndBox( aBoxes, GetVertex( aFirstNode ), GetVertex( aPivotNode ) );
2204
2205     aLoopEdges.UnBind( anEdgeId );
2206
2207     aLastNode = aFirstNode;
2208     while ( aPivotNode != aLastNode )
2209     {
2210       IMeshData::ListOfInteger::Iterator aLinkIt( myMeshData->LinksConnectedTo( aPivotNode ) );
2211       for ( ; aLinkIt.More(); aLinkIt.Next() )
2212       {
2213         if ( aLinkIt.Value() != anEdgeId &&
2214              aLoopEdges.IsBound( aLinkIt.Value() ) )
2215         {
2216           Standard_Integer aCurrentNode;
2217           anEdgeId = aLinkIt.Value();
2218           const BRepMesh_Edge& anEdge1 = GetEdge( anEdgeId );
2219
2220           aCurrentNode = anEdge1.LastNode();
2221           if ( aCurrentNode != aPivotNode )
2222           {
2223             aCurrentNode = anEdge1.FirstNode();
2224             aPolygon.Append( -anEdgeId );
2225           }
2226           else
2227             aPolygon.Append( anEdgeId );
2228
2229           fillBndBox( aBoxes, GetVertex( aCurrentNode ), GetVertex( aPivotNode ) );
2230
2231           aPivotNode = aCurrentNode;
2232           aLoopEdges.UnBind( anEdgeId );
2233           break;
2234         }
2235       }
2236
2237       if ( aLoopEdgesCount <= 0 )
2238         break;
2239       --aLoopEdgesCount;
2240     }
2241
2242     meshPolygon( aPolygon, aBoxes );
2243   }
2244 }
2245
2246
2247 //=======================================================================
2248 //function : AddVertices
2249 //purpose  : Adds some vertices in the triangulation.
2250 //=======================================================================
2251 void BRepMesh_Delaun::AddVertices(IMeshData::VectorOfInteger&  theVertices,
2252                                   const Message_ProgressRange& theRange)
2253 {
2254   ComparatorOfIndexedVertexOfDelaun aCmp(myMeshData);
2255   std::make_heap(theVertices.begin(), theVertices.end(), aCmp);
2256   std::sort_heap(theVertices.begin(), theVertices.end(), aCmp);
2257
2258   createTrianglesOnNewVertices(theVertices, theRange);
2259 }
2260
2261 //=======================================================================
2262 //function : UseEdge
2263 //purpose  : Modify mesh to use the edge. Return True if done
2264 //=======================================================================
2265 Standard_Boolean BRepMesh_Delaun::UseEdge( const Standard_Integer /*theIndex*/ )
2266 {
2267   /*
2268   const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theIndex );
2269   if ( aPair.Extent() == 0 )
2270   {
2271     const BRepMesh_Edge& anEdge = GetEdge( theIndex );
2272
2273     Standard_Integer aStartNode, aPivotNode, anOtherNode;
2274     aStartNode = anEdge.FirstNode();
2275     aPivotNode = anEdge.LastNode();
2276
2277     const BRepMesh_ListOfInteger& aStartNodeNeighbors = myMeshData->LinkNeighboursOf( aStartNode );
2278     const BRepMesh_ListOfInteger& aPivotNodeNeighbors = myMeshData->LinkNeighboursOf( aPivotNode );
2279
2280     if ( aStartNodeNeighbors.Extent() > 0 &&
2281          aPivotNodeNeighbors.Extent() > 0 )
2282     {
2283       const BRepMesh_Vertex& aStartVertex = GetVertex( aStartNode );
2284       const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
2285
2286       gp_XY aVEdge   ( aPivotVertex.Coord() );
2287       aVEdge.Subtract( aStartVertex.Coord() );
2288
2289       Standard_Real    anAngle    = 0.;
2290       Standard_Real    anAngleMin = RealLast();
2291       Standard_Real    anAngleMax = RealFirst();
2292       Standard_Integer aLeftEdge  = 0, aRightEdge = 0;
2293
2294       BRepMesh_ListOfInteger::Iterator aNeighborIt( aPivotNodeNeighbors );
2295       for ( ; aNeighborIt.More(); aNeighborIt.Next() )
2296       {
2297         Standard_Integer anEdgeId = aNeighborIt.Value();
2298         if ( anEdgeId != theIndex )
2299         {
2300           const BRepMesh_Edge& aNextEdge = GetEdge( anEdgeId );
2301
2302           Standard_Boolean isInMesh = Standard_True;
2303           if ( aNextEdge.Movability() == BRepMesh_Free )
2304           {
2305             if ( myMeshData->ElemConnectedTo( anEdgeId ).IsEmpty() )
2306               isInMesh = Standard_False;
2307           }
2308
2309           if ( isInMesh )
2310           {
2311             anOtherNode = aNextEdge.FirstNode();
2312             if ( anOtherNode == aPivotNode )
2313               anOtherNode = aNextEdge.LastNode();
2314
2315             gp_XY aVEdgeCur = GetVertex( anOtherNode ).Coord();
2316             aVEdgeCur.Subtract( aPivotVertex.Coord() );
2317
2318             anAngle = gp_Vec2d( aVEdge ).Angle( gp_Vec2d( aVEdgeCur ) );
2319           }
2320
2321           if ( anAngle > anAngleMax )
2322           {
2323             anAngleMax = anAngle;
2324             aLeftEdge  = anEdgeId;
2325           }
2326           if ( anAngle < anAngleMin )
2327           {
2328             anAngleMin = anAngle;
2329             aRightEdge = anEdgeId;
2330           }
2331         }
2332       }
2333
2334       if ( aLeftEdge > 0 )
2335       {
2336         if (aLeftEdge==aRightEdge)
2337         {
2338         }
2339         else
2340         {
2341         }
2342       }
2343     }
2344   }
2345   */
2346   return Standard_False;
2347 }
2348
2349 //=======================================================================
2350 //function : getEdgesByType
2351 //purpose  : Gives the list of edges with type defined by input parameter
2352 //=======================================================================
2353 Handle(IMeshData::MapOfInteger) BRepMesh_Delaun::getEdgesByType(
2354   const BRepMesh_DegreeOfFreedom theEdgeType ) const
2355 {
2356   Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
2357   Handle(IMeshData::MapOfInteger) aResult = new IMeshData::MapOfInteger;
2358   IMeshData::IteratorOfMapOfInteger anEdgeIt( myMeshData->LinksOfDomain() );
2359
2360   for ( ; anEdgeIt.More(); anEdgeIt.Next() )
2361   {
2362     Standard_Integer anEdge = anEdgeIt.Key();
2363     Standard_Boolean isToAdd = (theEdgeType == BRepMesh_Free) ?
2364       (myMeshData->ElementsConnectedTo( anEdge ).Extent() <= 1) :
2365       (GetEdge( anEdge ).Movability() == theEdgeType);
2366
2367     if (isToAdd)
2368       aResult->Add( anEdge );
2369   }
2370
2371   return aResult;
2372 }
2373
2374 //=======================================================================
2375 //function : calculateDist
2376 //purpose  : Calculates distances between the given point and edges of
2377 //           triangle
2378 //=======================================================================
2379 Standard_Real BRepMesh_Delaun::calculateDist( const gp_XY            theVEdges[3],
2380                                               const gp_XY            thePoints[3],
2381                                               const BRepMesh_Vertex& theVertex,
2382                                               Standard_Real          theDistance[3],
2383                                               Standard_Real          theSqModulus[3],
2384                                               Standard_Integer&      theEdgeOn ) const
2385 {
2386   Standard_Real aMinDist = RealLast();
2387   for( Standard_Integer i = 0; i < 3; ++i )
2388   {
2389     theSqModulus[i] = theVEdges[i].SquareModulus();
2390     if ( theSqModulus[i] <= Precision2 )
2391       return -1;
2392
2393     theDistance[i] = theVEdges[i] ^ ( theVertex.Coord() - thePoints[i] );
2394
2395     Standard_Real aDist = theDistance[i] * theDistance[i];
2396     aDist /= theSqModulus[i];
2397
2398     if ( aDist < aMinDist )
2399     {
2400       theEdgeOn = i;
2401       aMinDist  = aDist;
2402     }
2403   }
2404
2405   return aMinDist;
2406 }
2407
2408 //=======================================================================
2409 //function : Contains
2410 //purpose  : Test if triangle of index <TrianIndex> contains geometricaly
2411 //           <theVertex>. If <theEdgeOn> is != 0 then theVertex is on Edge
2412 //           of  index <theEdgeOn>
2413 //=======================================================================
2414 Standard_Boolean BRepMesh_Delaun::Contains( const Standard_Integer theTriangleId,
2415                                             const BRepMesh_Vertex& theVertex,
2416                                             const Standard_Real    theSqTolerance,
2417                                             Standard_Integer&      theEdgeOn) const
2418 {
2419   theEdgeOn = 0;
2420
2421   Standard_Integer p[3];
2422
2423   const BRepMesh_Triangle& aElement = GetTriangle( theTriangleId );
2424   const Standard_Integer(&e)[3] = aElement.myEdges;
2425
2426   const BRepMesh_Edge* anEdges[3] = { &GetEdge( e[0] ),
2427                                       &GetEdge( e[1] ),
2428                                       &GetEdge( e[2] ) };
2429
2430   myMeshData->ElementNodes(aElement, p);
2431
2432   gp_XY aPoints[3];
2433   aPoints[0] = GetVertex( p[0] ).Coord();
2434   aPoints[1] = GetVertex( p[1] ).Coord();
2435   aPoints[2] = GetVertex( p[2] ).Coord();
2436
2437   gp_XY aVEdges[3];
2438   aVEdges[0] = aPoints[1];
2439   aVEdges[0].Subtract( aPoints[0] );
2440
2441   aVEdges[1] = aPoints[2];
2442   aVEdges[1].Subtract( aPoints[1] );
2443
2444   aVEdges[2] = aPoints[0];
2445   aVEdges[2].Subtract( aPoints[2] );
2446
2447   Standard_Real aDistance[3];
2448   Standard_Real aSqModulus[3];
2449
2450   Standard_Real aSqMinDist;
2451   Standard_Integer aEdgeOnId;
2452   aSqMinDist = calculateDist( aVEdges, aPoints, theVertex, aDistance, aSqModulus, aEdgeOnId );
2453   if ( aSqMinDist < 0 )
2454     return Standard_False;
2455
2456   const Standard_Boolean isNotFree = (anEdges[aEdgeOnId]->Movability() != BRepMesh_Free);
2457   if ( aSqMinDist > theSqTolerance )
2458   {
2459     if (isNotFree && aDistance[aEdgeOnId] < ( aSqModulus[aEdgeOnId] / 5. ))
2460       theEdgeOn = e[aEdgeOnId];
2461   }
2462   else if (isNotFree)
2463     return Standard_False;
2464   else
2465     theEdgeOn = e[aEdgeOnId];
2466
2467   return (aDistance[0] >= 0. && aDistance[1] >= 0. && aDistance[2] >= 0.);
2468 }
2469
2470 //=============================================================================
2471 //function : intSegSeg
2472 //purpose  : Checks intersection between the two segments.
2473 //=============================================================================
2474 BRepMesh_GeomTool::IntFlag BRepMesh_Delaun::intSegSeg(
2475   const BRepMesh_Edge&   theEdg1,
2476   const BRepMesh_Edge&   theEdg2,
2477   const Standard_Boolean isConsiderEndPointTouch,
2478   const Standard_Boolean isConsiderPointOnEdge,
2479   gp_Pnt2d&              theIntPnt) const
2480 {
2481   gp_XY p1, p2, p3, p4;
2482   p1 = GetVertex( theEdg1.FirstNode() ).Coord();
2483   p2 = GetVertex( theEdg1.LastNode()  ).Coord();
2484   p3 = GetVertex( theEdg2.FirstNode() ).Coord();
2485   p4 = GetVertex( theEdg2.LastNode()  ).Coord();
2486
2487   return BRepMesh_GeomTool::IntSegSeg(p1, p2, p3, p4,
2488     isConsiderEndPointTouch, isConsiderPointOnEdge, theIntPnt);
2489 }
2490
2491 //=============================================================================
2492 //function : polyArea
2493 //purpose  : Returns area of the loop of the given polygon defined by indices
2494 //           of its start and end links.
2495 //=============================================================================
2496 Standard_Real BRepMesh_Delaun::polyArea(const IMeshData::SequenceOfInteger& thePolygon,
2497                                         const Standard_Integer              theStartIndex,
2498                                         const Standard_Integer              theEndIndex) const
2499 {
2500   Standard_Real aArea = 0.0;
2501   Standard_Integer aPolyLen = thePolygon.Length();
2502   if ( theStartIndex >= theEndIndex ||
2503        theStartIndex > aPolyLen )
2504   {
2505     return aArea;
2506   }
2507   Standard_Integer aCurEdgeInfo = thePolygon( theStartIndex );
2508   Standard_Integer aCurEdgeId   = Abs( aCurEdgeInfo );
2509   const BRepMesh_Edge* aCurEdge = &GetEdge( aCurEdgeId );
2510
2511   Standard_Integer aNodes[2];
2512   getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2513
2514   gp_Pnt2d aRefPnt = GetVertex( aNodes[0] ).Coord();
2515   Standard_Integer aPolyIt = theStartIndex + 1;
2516   for ( ; aPolyIt <= theEndIndex; ++aPolyIt )
2517   {
2518     aCurEdgeInfo = thePolygon( aPolyIt );
2519     aCurEdgeId   = Abs( aCurEdgeInfo );
2520     aCurEdge     = &GetEdge( aCurEdgeId );
2521
2522     getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2523     gp_Vec2d aVec1( aRefPnt, GetVertex( aNodes[0] ).Coord() );
2524     gp_Vec2d aVec2( aRefPnt, GetVertex( aNodes[1] ).Coord() );
2525
2526     aArea += aVec1 ^ aVec2;
2527   }
2528
2529   return aArea / 2.;
2530 }
2531
2532 #ifdef OCCT_DEBUG
2533 //=======================================================================
2534 //function : BRepMesh_DumpPoly
2535 //purpose  :
2536 //=======================================================================
2537 #include <TopoDS_Compound.hxx>
2538 #include <BRep_Builder.hxx>
2539 #include <Standard_ErrorHandler.hxx>
2540 #include <BRepBuilderAPI_MakeEdge.hxx>
2541 #include <BRepTools.hxx>
2542 Standard_CString BRepMesh_DumpPoly(void*            thePolygon,
2543                                    void*            theMeshHandlePtr,
2544                                    Standard_CString theFileNameStr)
2545 {
2546   if (thePolygon == 0 || theFileNameStr == 0)
2547   {
2548     return "Error: file name or polygon data is null";
2549   }
2550
2551   IMeshData::SequenceOfInteger& aPolygon = *(IMeshData::SequenceOfInteger*)thePolygon;
2552
2553   Handle(BRepMesh_DataStructureOfDelaun) aMeshData =
2554     *(Handle(BRepMesh_DataStructureOfDelaun)*)theMeshHandlePtr;
2555
2556   if (aMeshData.IsNull())
2557     return "Error: mesh data is empty";
2558
2559   TopoDS_Compound aMesh;
2560   BRep_Builder aBuilder;
2561   aBuilder.MakeCompound(aMesh);
2562
2563   try
2564   {
2565     OCC_CATCH_SIGNALS
2566
2567     IMeshData::SequenceOfInteger::Iterator aLinksIt(aPolygon);
2568     for (; aLinksIt.More(); aLinksIt.Next())
2569     {
2570       const BRepMesh_Edge& aLink = aMeshData->GetLink(Abs(aLinksIt.Value()));
2571
2572       gp_Pnt aPnt[2];
2573       for (Standard_Integer i = 0; i < 2; ++i)
2574       {
2575         const Standard_Integer aNodeId =
2576           (i == 0) ? aLink.FirstNode() : aLink.LastNode();
2577
2578         const gp_XY& aNode = aMeshData->GetNode(aNodeId).Coord();
2579         aPnt[i] = gp_Pnt(aNode.X(), aNode.Y(), 0.);
2580       }
2581
2582       if (aPnt[0].SquareDistance(aPnt[1]) < Precision::SquareConfusion())
2583         continue;
2584
2585       aBuilder.Add(aMesh, BRepBuilderAPI_MakeEdge(aPnt[0], aPnt[1]));
2586     }
2587
2588     if (!BRepTools::Write(aMesh, theFileNameStr))
2589       return "Error: write failed";
2590   }
2591   catch (Standard_Failure const& anException)
2592   {
2593     return anException.GetMessageString();
2594   }
2595
2596   return theFileNameStr;
2597 }
2598 #endif