projects / occt.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
0022627: Change OCCT memory management defaults
[occt.git] / src / BRepMesh / BRepMesh_Delaun.cxx
CommitLineData
0d88155b
O		 1// File: BRepMesh_Delaun.cxx
2// Created: Wed May 12 08:58:20 1993
3// Author: Didier PIFFAULT
4// <dpf@zerox>
5
6#include <BRepMesh_Delaun.ixx>
7#include <gp_XY.hxx>
8#include <gp_Pnt2d.hxx>
9#include <gp_Vec2d.hxx>
10#include <TColStd_ListIteratorOfListOfInteger.hxx>
11#include <TColStd_ListOfInteger.hxx>
12#include <Precision.hxx>
13#include <Bnd_Box2d.hxx>
14#include <gp.hxx>
15#include <TColStd_MapOfInteger.hxx>
2b59653e 16#include <TColStd_Array1OfBoolean.hxx>
0d88155b
O		 17#include <BRepMesh_MapOfIntegerInteger.hxx>
18#include <BRepMesh_HeapSortIndexedVertexOfDelaun.hxx>
19#include <BRepMesh_ComparatorOfIndexedVertexOfDelaun.hxx>
20#include <BRepMesh_HeapSortIndexedVertexOfDelaun.hxx>
21#include <BRepMesh_SelectorOfDataStructureOfDelaun.hxx>
22#include <BRepMesh_HeapSortVertexOfDelaun.hxx>
23#include <BRepMesh_ComparatorOfVertexOfDelaun.hxx>
2b59653e
E		 24#include <TColgp_Array1OfXY.hxx>
25#include <TColStd_Array1OfReal.hxx>
0d88155b
O		 26
27typedef TColStd_ListIteratorOfListOfInteger IteratorOnListOfInteger;
28typedef TColStd_ListOfInteger ListOfInteger;
29
30#define EPSEPS Precision::PConfusion()*Precision::PConfusion()
31
32const gp_XY SortingDirection(M_SQRT1_2, M_SQRT1_2);
33
34//#define TRIANGULATION_MESURE
35
36#ifdef TRIANGULATION_MESURE
37#include <OSD_Chronometer.hxx>
38#include <NCollection_IncAllocator.hxx>
39static OSD_Chronometer ChroTrigu;
40static OSD_Chronometer ChroSearch;
41static OSD_Chronometer ChroDelete;
42static OSD_Chronometer ChroDelTri;
43static OSD_Chronometer ChroDelCir;
44static OSD_Chronometer ChroCreate;
45static OSD_Chronometer ChroFront;
46Standard_EXPORT Standard_Boolean Triangulation_Chrono;
47#endif
48
49//#define TRIANGULATION_DEBUG
50
51#ifdef TRIANGULATION_DEBUG
52Standard_IMPORT Standard_Integer Triangulation_Trace;
53#endif
54
55
56//=======================================================================
57//function : BRepMesh_Delaun
58//purpose :
59//=======================================================================
60BRepMesh_Delaun::BRepMesh_Delaun
61(BRepMesh_Array1OfVertexOfDelaun& Vertices, const Standard_Boolean ZPositive)
62: PositiveOrientation(ZPositive), tCircles(Vertices.Length(),new NCollection_IncAllocator())
63{
64 if (Vertices.Length()>2) {
65 MeshData=new BRepMesh_DataStructureOfDelaun(new NCollection_IncAllocator(),Vertices.Length());
66 Init(Vertices);
67 }
68}
69
70//=======================================================================
71//function : BRepMesh_Delaun
72//purpose :
73//=======================================================================
74BRepMesh_Delaun::BRepMesh_Delaun
75(const Handle(BRepMesh_DataStructureOfDelaun)& OldMesh,
76 BRepMesh_Array1OfVertexOfDelaun& Vertices,
77 const Standard_Boolean ZPositive)
78 : PositiveOrientation(ZPositive), tCircles(Vertices.Length(),OldMesh->Allocator())
79{
80 MeshData=OldMesh;
81 if (Vertices.Length()>2)
82 Init(Vertices);
83}
84
85
86//=======================================================================
87//function : Init
88//purpose :
89//=======================================================================
90void BRepMesh_Delaun::Init(BRepMesh_Array1OfVertexOfDelaun& Vertices)
91{
92 Bnd_Box2d theBox;
93 TColStd_Array1OfInteger vertexIndices(Vertices.Lower(), Vertices.Upper());
94 Standard_Integer niver;
95
96 for (niver=Vertices.Lower(); niver<=Vertices.Upper(); niver++) {
97 theBox.Add(gp_Pnt2d(Vertices(niver).Coord()));
98 vertexIndices(niver)=MeshData->AddNode(Vertices(niver));
99 }
100
2b59653e 101 Perform(theBox, vertexIndices);
0d88155b
O		 102}
103
104
105//=======================================================================
106//function : BRepMesh_Delaun
107//purpose :
108//=======================================================================
109BRepMesh_Delaun::BRepMesh_Delaun
110(const Handle(BRepMesh_DataStructureOfDelaun)& OldMesh,
111 TColStd_Array1OfInteger& VertexIndices,
112 const Standard_Boolean ZPositive)
113 : PositiveOrientation(ZPositive), tCircles(VertexIndices.Length(),OldMesh->Allocator())
114{
115 MeshData=OldMesh;
116 if (VertexIndices.Length()>2) {
117 Bnd_Box2d theBox;
118 Standard_Integer niver;
119 for (niver=VertexIndices.Lower(); niver<=VertexIndices.Upper(); niver++) {
120 theBox.Add(gp_Pnt2d(GetVertex(VertexIndices(niver)).Coord()));
121 }
122
2b59653e
E		 123 Perform(theBox, VertexIndices);
124 }
125}
126
127//=======================================================================
128//function : Perform
129//purpose :
130//=======================================================================
131void BRepMesh_Delaun::Perform (Bnd_Box2d& theBndBox, TColStd_Array1OfInteger& theVertexIndices)
132{
133 theBndBox.Enlarge(Precision::PConfusion());
134 SuperMesh(theBndBox);
0d88155b 135
2b59653e
E		 136 BRepMesh_HeapSortIndexedVertexOfDelaun::Sort
137 (theVertexIndices,
138 BRepMesh_ComparatorOfIndexedVertexOfDelaun(SortingDirection,
139 Precision::PConfusion(),
140 MeshData));
0d88155b 141
2b59653e 142 Compute(theVertexIndices);
0d88155b
O		 143}
144
145//=======================================================================
146//function : Compute
147//purpose :
148//=======================================================================
149void BRepMesh_Delaun::Compute (TColStd_Array1OfInteger& VertexIndices)
150{
151 // Insertion of edges of super triangles in the list of free edges:
152 BRepMesh_MapOfIntegerInteger loopEdges(10,MeshData->Allocator());
153 Standard_Integer e1, e2, e3;
154 Standard_Boolean o1, o2, o3;
155 supTrian.Edges(e1, e2, e3, o1, o2, o3);
156 loopEdges.Bind(e1, Standard_True);
157 loopEdges.Bind(e2, Standard_True);
158 loopEdges.Bind(e3, Standard_True);
159
160 if (VertexIndices.Length()>0) {
161
162 // Creation of 3 trianglers with the node and the edges of the super triangle:
163 Standard_Integer iVert=VertexIndices.Lower();
164 CreateTriangles(VertexIndices(iVert), loopEdges);
165
2b59653e 166 CreateTrianglesOnNewVertices(VertexIndices);
0d88155b
O		 167
168 // To add a node in the mesh it is necessary to check to conditions
169 // - the node should be located on the border of the mesh and in an existing triangle
170 // - all adjacent triangles should belong to a component connected with this triangle
2b59653e 171 /* if (Contains(itT.Value(), refToVert, edgeOn)) {
0d88155b
O		 172 triPerce=itT.Value();
173 cirL.Remove(itT);
174 break;
2b59653e
E		 175 }*/
176 // Insertion of nodes :
0d88155b
O		 177 }
178
179 // destruction of triangles containing a top of the super triangle
180 BRepMesh_SelectorOfDataStructureOfDelaun select(MeshData);
181 select.NeighboursOfNode(supVert1);
182 select.NeighboursOfNode(supVert2);
183 select.NeighboursOfNode(supVert3);
184 BRepMesh_MapOfInteger::Iterator trs(select.Elements());
185 loopEdges.Clear();
186 for (;trs.More(); trs.Next()) {
187 DeleteTriangle(trs.Key(), loopEdges);
188 }
189
190 // all edges that remain free are removed from loopEdges;
191 // only the boundary edges of the triangulation remain in loopEdges
192 BRepMesh_MapOfIntegerInteger::Iterator itLEd(loopEdges);
193 for (; itLEd.More(); itLEd.Next()) {
194 if (MeshData->ElemConnectedTo(itLEd.Key()).IsEmpty())
195 MeshData->RemoveLink(itLEd.Key());
196 }
197
198 //the tops of the super triangle are destroyed
199 MeshData->RemoveNode(supVert1);
200 MeshData->RemoveNode(supVert2);
201 MeshData->RemoveNode(supVert3);
202
203}
204
0d88155b
O		 205//=======================================================================
206//function : FrontierAdjust
207//purpose :
208//=======================================================================
209void BRepMesh_Delaun::FrontierAdjust()
210{
211 Standard_Integer e1, e2, e3;
212 Standard_Boolean o1, o2, o3;
213 BRepMesh_MapOfIntegerInteger loopEdges(10,MeshData->Allocator());
214 BRepMesh_ListOfInteger::Iterator itconx;
215 ListOfInteger tril;
216
2b59653e
E		 217 Standard_Integer pass = 1;
218 for (; pass <= 2; pass++ )
219 {
220 // 1 pass): find external triangles on boundary edges
221 // 2 pass): find external triangles on boundary edges
222 // because in comlex curved boundaries external triangles can appear
223 // after "mesh left polygon"
224 BRepMesh_MapOfInteger::Iterator itFr(Frontier());
225 for (; itFr.More(); itFr.Next()) {
226 const BRepMesh_PairOfIndex& aPair = MeshData->ElemConnectedTo(itFr.Key());
227 for(Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; j++) {
228 const BRepMesh_Triangle& trc=GetTriangle(aPair.Index(j));
229 trc.Edges(e1,e2,e3,o1,o2,o3);
230 if ((itFr.Key()==e1 && !o1) ||
231 (itFr.Key()==e2 && !o2) ||
232 (itFr.Key()==e3 && !o3)) {
0d88155b 233#ifdef TRIANGULATION_DEBUG
2b59653e
E		 234 if (Triangulation_Trace>0) {
235 cout << "---> destruction du triangle " << aPair.Index(j) << endl;
236 }
0d88155b 237#endif
2b59653e
E		 238 tril.Append(aPair.Index(j));
239 }
0d88155b
O		 240 }
241 }
0d88155b 242
2b59653e
E		 243 // destruction of external triangles on boundary edges
244 for (; !tril.IsEmpty(); tril.RemoveFirst()) {
245 DeleteTriangle(tril.First(), loopEdges);
246 }
0d88155b 247
2b59653e
E		 248 // destrucrion of remaining hanging edges :
249 BRepMesh_MapOfIntegerInteger::Iterator itFE(loopEdges);
0d88155b 250
2b59653e
E		 251 for (; itFE.More(); itFE.Next()) {
252 if (MeshData->ElemConnectedTo(itFE.Key()).IsEmpty())
253 MeshData->RemoveLink(itFE.Key());
254 }
0d88155b 255
2b59653e
E		 256 // destruction of triangles crossing the boundary edges and
257 // their replacement by makeshift triangles
258 if ( pass == 1 )
259 {
260 itFr.Reset();
261 }
262 else
263 {
264 // in some cases there remain unused boundaries check
265 itFr.Initialize(Frontier());
266 }
267
268 for (; itFr.More(); itFr.Next()) {
269 if (MeshData->ElemConnectedTo(itFr.Key()).IsEmpty()) {
270 MeshLeftPolygonOf(itFr.Key(), Standard_True);
271 }
0d88155b 272 }
0d88155b 273
2b59653e 274 if ( pass == 2 ) break;
0d88155b 275
2b59653e
E		 276 // After this processing there sometimes remain triangles outside boundaries.
277 // Destruction of these triangles :
278 Standard_Integer nbFront;
0d88155b 279
2b59653e
E		 280 // For each edge with only one connection
281 // If one of its tops already passes two boundary edges,
282 // the connected triangle is outside of the contour
283 Standard_Boolean again = Standard_True;
0d88155b 284
2b59653e
E		 285 while (again) {
286 tril.Clear();
287 loopEdges.Clear();
288
289 for (itFr.Initialize(FreeEdges()); itFr.More(); itFr.Next()) {
290 const BRepMesh_Edge& edg=GetEdge(itFr.Key());
291 if (edg.Movability()!=BRepMesh_Frontier) {
292 nbFront=0;
293 if (MeshData->ElemConnectedTo(itFr.Key()).IsEmpty())
294 loopEdges.Bind(itFr.Key(), Standard_True);
295 else {
296 for (itconx.Init(MeshData->LinkNeighboursOf(edg.FirstNode()));
297 itconx.More(); itconx.Next()) {
298 if (GetEdge(itconx.Value()).Movability()==BRepMesh_Frontier) {
299 nbFront++;
300 if (nbFront>1) break;
301 }
302 }
303 if (nbFront==2) {
304 const BRepMesh_PairOfIndex& aPair = MeshData->ElemConnectedTo(itFr.Key());
305 for(Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; j++) {
306 const Standard_Integer elemId = aPair.Index(j);
307 GetTriangle(elemId).Edges(e1, e2, e3, o1, o2, o3);
308 if (GetEdge(e1).Movability()==BRepMesh_Free &&
309 GetEdge(e2).Movability()==BRepMesh_Free &&
310 GetEdge(e3).Movability()==BRepMesh_Free) {
311 #ifdef TRIANGULATION_DEBUG
312 if (Triangulation_Trace>0) {
313 cout << " ----> destruction du triangle" << elemId <<endl;
314 }
315 #endif
316 tril.Append(elemId);
317 }
0d88155b
O		 318 }
319 }
320 }
321 }
322 }
0d88155b 323
b2342827 324 // Destruction of triangles :
2b59653e
E		 325 Standard_Integer kk = 0;
326 for (; !tril.IsEmpty(); tril.RemoveFirst()) {
327 DeleteTriangle(tril.First(), loopEdges);
328 kk++;
329 }
0d88155b 330
2b59653e
E		 331 // destruction of remaining hanging edges
332 for (itFE.Initialize(loopEdges); itFE.More(); itFE.Next()) {
333 if (MeshData->ElemConnectedTo(itFE.Key()).IsEmpty())
334 MeshData->RemoveLink(itFE.Key());
335 }
0d88155b 336
2b59653e
E		 337 if (kk == 0) break;
338 }
0d88155b
O		 339 }
340
2b59653e 341/* // find external triangles on boundary edges
0d88155b
O		 342 // because in comlex curved boundaries external triangles can appear
343 // after "mesh left polygon"
344 for (itFr.Initialize(Frontier()); itFr.More(); itFr.Next()) {
345 const BRepMesh_PairOfIndex& aPair = MeshData->ElemConnectedTo(itFr.Key());
346 for(Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; j++) {
347 const BRepMesh_Triangle& trc=GetTriangle(aPair.Index(j));
348 trc.Edges(e1,e2,e3,o1,o2,o3);
349 if ((itFr.Key()==e1 && !o1) ||
350 (itFr.Key()==e2 && !o2) ||
351 (itFr.Key()==e3 && !o3)) {
352#ifdef TRIANGULATION_DEBUG
353 if (Triangulation_Trace>0) {
b2342827 354 cout << "---> destruction of triangle " << aPair.Index(j) << endl;
0d88155b
O		 355 }
356#endif
357 tril.Append(aPair.Index(j));
358 }
359 }
360 }
361
362 // destruction of external triangles on boundary edges
363 for (; !tril.IsEmpty(); tril.RemoveFirst()) {
364 DeleteTriangle(tril.First(), loopEdges);
365 }
366
367 for (itFE.Initialize(loopEdges); itFE.More(); itFE.Next()) {
368 if (MeshData->ElemConnectedTo(itFE.Key()).IsEmpty())
369 MeshData->RemoveLink(itFE.Key());
370 }
371
372
373 // in some cases there remain unused boundaries check
374 for (itFr.Initialize(Frontier()); itFr.More(); itFr.Next()) {
375 if (MeshData->ElemConnectedTo(itFr.Key()).IsEmpty()) {
376 MeshLeftPolygonOf(itFr.Key(), Standard_True);
377 }
2b59653e 378 } */
0d88155b
O		 379}
380
381
382//=======================================================================
383//function : MeshLeftPolygonOf
384//purpose : Triangulation of the polygon to the left of <indexEdg>.(material side)
385//=======================================================================
386void BRepMesh_Delaun::MeshLeftPolygonOf(const Standard_Integer indexEdg,
387 const Standard_Boolean forwdEdg)
388{
389 const BRepMesh_Edge& edg=GetEdge(indexEdg);
390 TColStd_SequenceOfInteger polyg;
391 BRepMesh_MapOfIntegerInteger loopEdges(10,MeshData->Allocator());
392 TColStd_MapOfInteger usedEdges;
393
394 // Find the polygon
395 usedEdges.Add(indexEdg);
396 Standard_Integer debut, prem, pivo;
397#ifndef DEB
398 Standard_Integer ders =0, oth =0;
399#else
400 Standard_Integer ders, oth;
401#endif
402 if (forwdEdg) {
403 polyg.Append(indexEdg);
404 prem=edg.FirstNode();
405 pivo=edg.LastNode();
406 }
407 else {
408 polyg.Append(-indexEdg);
409 prem=edg.LastNode();
410 pivo=edg.FirstNode();
411 }
412 debut=prem;
413 const BRepMesh_Vertex& debEd=GetVertex(debut);
414 const BRepMesh_Vertex& finEd=GetVertex(pivo);
415
416 // Check the presence of the previous edge <indexEdg> :
417 BRepMesh_ListOfInteger::Iterator itLiVer(MeshData->LinkNeighboursOf(prem));
418 for (; itLiVer.More(); itLiVer.Next()) {
419 oth=0;
420 if (itLiVer.Value()!=indexEdg) {
421 const BRepMesh_Edge& nedg=GetEdge(itLiVer.Value());
422 oth=nedg.LastNode();
423 if (oth==prem) oth=nedg.FirstNode();
424 break;
425 }
426 }
427 if (oth==0) {
428#ifdef TRIANGULATION_DEBUG
429 if (Triangulation_Trace>0)
b2342827 430 cout << " MeshLeftPolygonOf : No path previous Edge!" << endl;
0d88155b
O		 431#endif
432 return;
433 }
434
435
436 gp_XY vedge(finEd.Coord());
437 vedge.Subtract(debEd.Coord());
438 gp_XY ved1(vedge);
439 gp_XY ved2;
440 Standard_Integer curEdg=indexEdg, e1, e2, e3;
441 Standard_Boolean o1, o2, o3;
442
443 // Find the nearest to <indexEdg> closed polygon :
444 Standard_Boolean InMesh, notInters;
445 Standard_Integer nextedge;
446 Standard_Real ang, angref;
447 gp_XY vpivo, vedcur, voth;
448
449 while (pivo!=debut) {
450 nextedge=0;
451 if (PositiveOrientation) angref=RealFirst();
452 else angref=RealLast();
453 const BRepMesh_Vertex& vertPivo=GetVertex(pivo);
454 vpivo=vertPivo.Coord();
455 vpivo.Subtract(debEd.Coord());
456
457 itLiVer.Init(MeshData->LinkNeighboursOf(pivo));
458
459 // Find the next edge with the greatest angle with <indexEdg>
460 // and non intersecting <indexEdg> :
461
462 for (; itLiVer.More(); itLiVer.Next()) {
463 if (itLiVer.Value()!=curEdg) {
464 notInters=Standard_True;
465 const BRepMesh_Edge& nedg=GetEdge(itLiVer.Value());
466
467 InMesh=Standard_True;
468 if (nedg.Movability()==BRepMesh_Free) {
469 if (MeshData->ElemConnectedTo(itLiVer.Value()).IsEmpty())
470 InMesh=Standard_False;
471 }
472
473 if (InMesh) {
474 oth=nedg.FirstNode();
475 if (oth==pivo) oth=nedg.LastNode();
476
477 vedcur=GetVertex(oth).Coord();
478 vedcur.Subtract(vertPivo.Coord());
479 if (vedcur.Modulus() >= gp::Resolution() &&
480 ved1.Modulus() >= gp::Resolution()) {
481 if (prem!=debut && oth!=debut) {
482 voth=GetVertex(oth).Coord();
483 voth.Subtract(debEd.Coord());
484 if ((vedge^vpivo)*(vedge^voth)<0.) {
485 voth=vertPivo.Coord();
486 voth.Subtract(finEd.Coord());
487 if ((vedcur^vpivo)*(vedcur^voth)<0.)
488 notInters=Standard_False;
489 }
490 }
491
492 if (notInters) {
493 ang=gp_Vec2d(ved1).Angle(gp_Vec2d(vedcur));
494
495 if ((PositiveOrientation && ang>angref) ||
496 (!PositiveOrientation && ang<angref)) {
497 angref=ang;
498 ved2=vedcur;
499 if (nedg.FirstNode()==pivo) nextedge=itLiVer.Value();
500 else nextedge=-itLiVer.Value();
501 ders=oth;
502
503 //epa: Find correct closing not direct to
504 // link but with maximal angle
505 // otherwise, polygon greater that expected is found
506 //if (ders==debut) break;
507 }
508 }
509 }
510 }
511 }
512 }
513
514 if (nextedge!=0) {
515 if (Abs(nextedge)!=indexEdg && Abs(nextedge)!=curEdg) {
516 curEdg=Abs(nextedge);
517
518 if (!usedEdges.Add(curEdg)) {
519
520 //if this edge has already been added to the polygon,
521 //there is a risk of looping (attention to open contours)
522#ifdef TRIANGULATION_DEBUG
523 if (Triangulation_Trace>0)
b2342827 524 cout << " MeshLeftPolygonOf : no closing of the polygon !"
0d88155b
O		 525 << endl;
526#endif
527
528 // all edges of the boundary contour are removed from the polygon
529 curEdg=Abs(polyg(polyg.Length()));
530 while (GetEdge(curEdg).Movability()==BRepMesh_Frontier){
531 polyg.Remove(polyg.Length());
532 if (polyg.Length()<=0) break;
533 curEdg=Abs(polyg(polyg.Length()));
534 }
535 return;
536 }
537
538 polyg.Append(nextedge);
539
540 Standard_Boolean forw=nextedge>0;
541 const BRepMesh_PairOfIndex& aPair = MeshData->ElemConnectedTo(curEdg);
542 for(Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; j++) {
543 const Standard_Integer elemId = aPair.Index(j);
544 GetTriangle(elemId).Edges(e1,e2,e3,o1,o2,o3);
545 if ((e1==curEdg && o1==forw) ||
546 (e2==curEdg && o2==forw) ||
547 (e3==curEdg && o3==forw)) {
548 DeleteTriangle(elemId, loopEdges);
549 break;
550 }
551 }
552 }
553 }
554 else {
555#ifdef TRIANGULATION_DEBUG
556 if (Triangulation_Trace>0)
b2342827 557 cout << " MeshLeftPolygonOf : No next !" << endl;
0d88155b
O		 558#endif
559 return;
560 }
561 prem=pivo;
562 pivo=ders;
563 ved1=ved2;
564 }
565
566
567 // Destruction of unused free edges :
568 BRepMesh_MapOfIntegerInteger::Iterator itFE(loopEdges);
569
570 for (; itFE.More(); itFE.Next()) {
571 if (MeshData->ElemConnectedTo(itFE.Key()).IsEmpty())
572 MeshData->RemoveLink(itFE.Key());
573 }
574
575 MeshPolygon(polyg);
576}
577
578
579//=======================================================================
580//function : MeshPolygon
581//purpose : Triangulatiion of a closed polygon described by the list of indexes of
582// its edges in the structure. (negative index == reversed)
583//=======================================================================
584void BRepMesh_Delaun::MeshPolygon (TColStd_SequenceOfInteger& poly)
585{
586 Standard_Integer vert, vert1, vert2, vert3 =0, tri;
587
588 if (poly.Length()==3) {
589 tri=MeshData->AddElement(BRepMesh_Triangle(Abs(poly(1)),Abs(poly(2)),Abs(poly(3)),
590 poly(1)>0, poly(2)>0, poly(3)>0,
591 BRepMesh_Free));
592 tCircles.MocAdd(tri);
593 const BRepMesh_Edge& edg1=GetEdge(Abs(poly(1)));
594 const BRepMesh_Edge& edg2=GetEdge(Abs(poly(2)));
595 if (poly(1)>0) {
596 vert1=edg1.FirstNode();
597 vert2=edg1.LastNode();
598 }
599 else {
600 vert1=edg1.LastNode();
601 vert2=edg1.FirstNode();
602 }
603 if (poly(2)>0)
604 vert3=edg2.LastNode();
605 else
606 vert3=edg2.FirstNode();
607
608 if (!tCircles.Add(GetVertex(vert1).Coord(),
609 GetVertex(vert2).Coord(),
610 GetVertex(vert3).Coord(),
611 tri)) {
612 MeshData->RemoveElement(tri);
613 }
614 }
615
616 else if (poly.Length()>3) {
617 const BRepMesh_Edge& edg=GetEdge(Abs(poly(1)));
618 Standard_Real distmin=RealLast();
619 Standard_Integer ip, used =0;
620
621 if (poly(1)>0) {
622 vert1=edg.FirstNode();
623 vert2=edg.LastNode();
624 }
625 else {
626 vert1=edg.LastNode();
627 vert2=edg.FirstNode();
628 }
629 gp_XY vedg(GetVertex(vert2).Coord()-
630 GetVertex(vert1).Coord());
631 Standard_Real modul=vedg.Modulus();
632 if (modul>0.) {
633 vedg.SetCoord(vedg.X()/modul, vedg.Y()/modul);
634
635 for (ip=3; ip<=poly.Length(); ip++) {
636 const BRepMesh_Edge& nedg=GetEdge(Abs(poly(ip)));
637 if (poly(ip)>0) vert=nedg.FirstNode();
638 else vert=nedg.LastNode();
639 gp_XY vep(GetVertex(vert).Coord()-GetVertex(vert2).Coord());
640
641 Standard_Real dist=vedg^vep;
642 if (Abs(dist)>Precision::PConfusion()) {
643 if ((dist>0. && PositiveOrientation) ||
644 (dist<0. && !PositiveOrientation)) {
645 if (Abs(dist)<distmin) {
646 distmin=dist;
647 vert3=vert;
648 used=ip;
649 }
650 }
651 }
652 }
653 }
654
655 Standard_Integer ne2, ne3;
656 if (distmin<RealLast()) {
657 ne2=MeshData->AddLink(BRepMesh_Edge(vert2, vert3, BRepMesh_Free));
658 ne3=MeshData->AddLink(BRepMesh_Edge(vert3, vert1, BRepMesh_Free));
659 tri=MeshData->AddElement(BRepMesh_Triangle(Abs(poly(1)), Abs(ne2), Abs(ne3),
660 (poly(1)>0), (ne2>0), (ne3>0),
661 BRepMesh_Free));
662
663 if (!tCircles.Add(GetVertex(vert1).Coord(),
664 GetVertex(vert2).Coord(),
665 GetVertex(vert3).Coord(),
666 tri)) {
667 MeshData->RemoveElement(tri);
668 }
669
670 if (used<poly.Length()) {
671 TColStd_SequenceOfInteger suitePoly;
672 poly.Split(used, suitePoly);
673 suitePoly.Prepend(-ne3);
674 MeshPolygon(suitePoly);
675 }
676 else
677 poly.Remove(poly.Length());
678
679 if (used>3) {
680 poly.SetValue(1, -ne2);
681 MeshPolygon(poly);
682 }
683 }
684 else {
685#ifdef TRIANGULATION_DEBUG
686 if (Triangulation_Trace>0) {
687