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