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