0027490: BRepMesh: Reduce number of memory allocations
[occt.git] / src / BRepMesh / BRepMesh_FastDiscret.cxx
1 // Created on: 1996-02-27
2 // Created by: Ekaterina SMIRNOVA
3 // Copyright (c) 1996-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17 #include <BRepMesh_FastDiscret.hxx>
18
19 #include <BRepMesh_WireChecker.hxx>
20 #include <BRepMesh_FastDiscretFace.hxx>
21 #include <BRepMesh_FaceAttribute.hxx>
22 #include <BRepMesh_DataStructureOfDelaun.hxx>
23 #include <BRepMesh_GeomTool.hxx>
24 #include <BRepMesh_PairOfPolygon.hxx>
25 #include <BRepMesh_Classifier.hxx>
26 #include <BRepMesh_EdgeParameterProvider.hxx>
27 #include <BRepMesh_IEdgeTool.hxx>
28 #include <BRepMesh_EdgeTessellator.hxx>
29 #include <BRepMesh_EdgeTessellationExtractor.hxx>
30
31 #include <BRepAdaptor_Curve.hxx>
32 #include <BRepAdaptor_Surface.hxx>
33 #include <BRepAdaptor_HSurface.hxx>
34
35 #include <Bnd_Box.hxx>
36 #include <BRepTools.hxx>
37 #include <BRepBndLib.hxx>
38 #include <BndLib_Add3dCurve.hxx>
39 #include <Poly_Triangulation.hxx>
40 #include <Poly_PolygonOnTriangulation.hxx>
41
42 #include <Precision.hxx>
43 #include <Geom2d_Curve.hxx>
44 #include <Geom_Surface.hxx>
45 #include <Geom_Plane.hxx>
46 #include <GeomAbs_SurfaceType.hxx>
47 #include <Extrema_LocateExtPC.hxx>
48
49 #include <TColStd_Array1OfInteger.hxx>
50 #include <TColStd_Array1OfCharacter.hxx>
51 #include <TColStd_HArray1OfReal.hxx>
52 #include <TColgp_Array1OfPnt2d.hxx>
53 #include <TColGeom2d_SequenceOfCurve.hxx>
54
55 #include <TopTools_SequenceOfShape.hxx>
56 #include <TopTools_ListIteratorOfListOfShape.hxx>
57
58 #include <TopAbs.hxx>
59 #include <TopoDS.hxx>
60 #include <TopoDS_Vertex.hxx>
61 #include <TopExp.hxx>
62 #include <TopExp_Explorer.hxx>
63
64 #include <OSD_Parallel.hxx>
65
66 #include <Standard_ErrorHandler.hxx>
67 #include <Standard_Failure.hxx>
68 #include <NCollection_IncAllocator.hxx>
69
70 #include <BRep_ListIteratorOfListOfPointRepresentation.hxx>
71 #include <BRep_PointRepresentation.hxx>
72
73 #include <vector>
74
75 IMPLEMENT_STANDARD_RTTIEXT(BRepMesh_FastDiscret,Standard_Transient)
76
77 #define UVDEFLECTION 1.e-05
78
79 //=======================================================================
80 //function : BRepMesh_FastDiscret
81 //purpose  : 
82 //=======================================================================
83 BRepMesh_FastDiscret::BRepMesh_FastDiscret( const Bnd_Box&         theBox,
84                                             const BRepMesh_FastDiscret::Parameters& theParams)
85    :
86   myMapdefle(1000, new NCollection_IncAllocator()),
87   myBoundaryVertices(new BRepMesh::DMapOfVertexInteger),
88   myBoundaryPoints(new BRepMesh::DMapOfIntegerPnt),
89   myParameters(theParams),
90   myDtotale(0.)
91
92   if ( myParameters.Relative )
93     BRepMesh_ShapeTool::BoxMaxDimension(theBox, myDtotale);
94 }
95
96 //=======================================================================
97 //function : InitSharedFaces
98 //purpose  : 
99 //=======================================================================
100 void BRepMesh_FastDiscret::InitSharedFaces(const TopoDS_Shape& theShape)
101 {
102   TopExp::MapShapesAndAncestors(theShape, TopAbs_EDGE, TopAbs_FACE, mySharedFaces);
103 }
104
105 //=======================================================================
106 //function : Perform(shape)
107 //purpose  : 
108 //=======================================================================
109 void BRepMesh_FastDiscret::Perform(const TopoDS_Shape& theShape)
110 {
111   InitSharedFaces(theShape);
112
113   std::vector<TopoDS_Face> aFaces;
114   TopExp_Explorer anExplorer(theShape, TopAbs_FACE);
115   for (; anExplorer.More(); anExplorer.Next())
116   {
117     const TopoDS_Face& aFace = TopoDS::Face(anExplorer.Current());
118     Add(aFace);
119     aFaces.push_back(aFace);
120   }
121
122   OSD_Parallel::ForEach(aFaces.begin(), aFaces.end(), *this, !myParameters.InParallel);
123 }
124
125
126 //=======================================================================
127 //function : Process
128 //purpose  : 
129 //=======================================================================
130 void BRepMesh_FastDiscret::Process(const TopoDS_Face& theFace) const
131 {
132   Handle(BRepMesh_FaceAttribute) anAttribute;
133   if (GetFaceAttribute(theFace, anAttribute))
134   {
135     try
136     {
137       OCC_CATCH_SIGNALS
138
139       BRepMesh_FastDiscretFace aTool(myParameters.Angle, myParameters.MinSize, 
140         myParameters.InternalVerticesMode, myParameters.ControlSurfaceDeflection);
141       aTool.Perform(anAttribute);
142     }
143     catch (Standard_Failure)
144     {
145       anAttribute->SetStatus(BRepMesh_Failure);
146     }
147   }
148 }
149
150 //=======================================================================
151 //function : resetDataStructure
152 //purpose  : 
153 //=======================================================================
154 void BRepMesh_FastDiscret::resetDataStructure()
155 {
156   Handle(NCollection_IncAllocator) aAllocator;
157   if (myAttribute->ChangeStructure().IsNull())
158     aAllocator = new NCollection_IncAllocator(BRepMesh::MEMORY_BLOCK_SIZE_HUGE);
159   else
160     aAllocator = myAttribute->ChangeStructure()->Allocator();
161
162   myAttribute->Clear();
163   aAllocator->Reset(Standard_False);
164   Handle(BRepMesh_DataStructureOfDelaun) aStructure = 
165     new BRepMesh_DataStructureOfDelaun(aAllocator);
166
167   const Standard_Real aTolU = myAttribute->ToleranceU();
168   const Standard_Real aTolV = myAttribute->ToleranceV();
169   const Standard_Real uCellSize = 14.0 * aTolU;
170   const Standard_Real vCellSize = 14.0 * aTolV;
171
172   aStructure->Data()->SetCellSize ( uCellSize, vCellSize);
173   aStructure->Data()->SetTolerance( aTolU    , aTolV    );
174
175   myAttribute->ChangeStructure() = aStructure;
176 }
177
178 //=======================================================================
179 //function : Add(face)
180 //purpose  : 
181 //=======================================================================
182 Standard_Integer BRepMesh_FastDiscret::Add(const TopoDS_Face& theFace)
183 {
184   myAttribute.Nullify();
185   GetFaceAttribute(theFace, myAttribute, Standard_True);
186
187   try
188   {
189     OCC_CATCH_SIGNALS
190
191     // Initialize face attributes
192     if (!myAttribute->IsInitialized ())
193       myAttribute->SetFace (theFace, myParameters.AdaptiveMin);
194     
195     BRepMesh::HIMapOfInteger&            aVertexEdgeMap = myAttribute->ChangeVertexEdgeMap();
196     BRepMesh::HDMapOfShapePairOfPolygon& aInternalEdges = myAttribute->ChangeInternalEdges();
197
198     resetDataStructure();
199
200     Standard_Real defedge = myParameters.Deflection;
201     Standard_Integer nbEdge = 0;
202     Standard_Real savangle = myParameters.Angle;
203     Standard_Real cdef;
204     Standard_Real maxdef = 2.* BRepMesh_ShapeTool::MaxFaceTolerance(theFace);
205
206     Standard_Real defface = 0.;
207     if (!myParameters.Relative)
208       defface = Max(myParameters.Deflection, maxdef);
209
210     const TopoDS_Face&                  aFace = myAttribute->Face();
211     for (TopoDS_Iterator aWireIt(aFace); aWireIt.More(); aWireIt.Next())
212     {
213       for (TopoDS_Iterator aEdgeIt(aWireIt.Value()); aEdgeIt.More(); aEdgeIt.Next(), ++nbEdge)
214       {
215         const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Value());
216         if (aEdge.IsNull())
217           continue;
218         if (!myMapdefle.IsBound(aEdge))
219         {
220           if (myParameters.Relative)
221           {
222             if (myEdges.IsBound(aEdge))
223             {
224               const BRepMesh_PairOfPolygon& aPair = myEdges.Find(aEdge);
225               const Handle(Poly_PolygonOnTriangulation)& aPolygon = aPair.First();
226               defedge = aPolygon->Deflection();
227             }
228             else
229             {
230               defedge = BRepMesh_ShapeTool::RelativeEdgeDeflection(
231                 aEdge, myParameters.Deflection, myDtotale, cdef);
232
233               myParameters.Angle = savangle * cdef;
234             }
235
236             defface += defedge;
237             defface = Max(maxdef, defface);
238           }
239           else
240           {
241             defedge = myParameters.Deflection;
242           }
243
244           defedge = Max(maxdef, defedge);
245           defedge = Max(UVDEFLECTION, defedge);
246           myMapdefle.Bind(aEdge, defedge);
247         }
248         else
249         {
250           defedge = myMapdefle(aEdge);
251           if ( myParameters.Relative )
252           {
253             defface += defedge;
254             defface = Max(maxdef, defface);
255           }
256         }
257
258         Standard_Real aFirstParam, aLastParam;
259         Handle(Geom2d_Curve) aCurve2d = 
260           BRep_Tool::CurveOnSurface(aEdge, aFace, aFirstParam, aLastParam);
261
262         if (aCurve2d.IsNull())
263           continue;
264
265         EdgePCurve aPCurve = { aCurve2d, aFirstParam, aLastParam };
266
267         add(aEdge, aPCurve, defedge);
268         myParameters.Angle = savangle;
269       }
270     }
271
272     if ( nbEdge == 0 || aVertexEdgeMap->Extent() < 3 )
273     {
274       myAttribute->ChangeStructure().Nullify();
275       myAttribute->SetStatus(BRepMesh_Failure);
276       return myAttribute->GetStatus();
277     }
278
279     if ( myParameters.Relative )
280     {
281       defface = defface / nbEdge;
282     }
283     else
284     {
285       defface = myParameters.Deflection;
286     }
287
288     defface = Max(maxdef, defface);
289
290     TopLoc_Location aLoc;
291     Handle(Poly_Triangulation) aTriangulation = BRep_Tool::Triangulation(aFace, aLoc);
292     const Handle(BRepAdaptor_HSurface)& gFace = myAttribute->Surface();
293
294     if ( aTriangulation.IsNull() )
295     {
296       Standard_Real xCur, yCur;
297       Standard_Real maxX, minX, maxY, minY;
298
299       minX = minY = 1.e100;
300       maxX = maxY =-1.e100;
301
302       Standard_Integer ipn = 0;
303       Standard_Integer i1 = 1;
304       for ( i1 = 1; i1 <= aVertexEdgeMap->Extent(); ++i1 )
305       {
306         const BRepMesh_Vertex& aVertex = 
307           myAttribute->ChangeStructure()->GetNode(aVertexEdgeMap->FindKey(i1));
308
309         ++ipn;
310
311         xCur = aVertex.Coord().X();
312         yCur = aVertex.Coord().Y();
313
314         minX = Min(xCur, minX);
315         maxX = Max(xCur, maxX);
316         minY = Min(yCur, minY);
317         maxY = Max(yCur, maxY);
318       }
319
320       Standard_Real myumin = minX;
321       Standard_Real myumax = maxX;
322       Standard_Real myvmin = minY;
323       Standard_Real myvmax = maxY;
324
325       const Standard_Real umin = gFace->FirstUParameter();
326       const Standard_Real umax = gFace->LastUParameter();
327       const Standard_Real vmin = gFace->FirstVParameter();
328       const Standard_Real vmax = gFace->LastVParameter();
329
330       if (myumin < umin || myumax > umax)
331       {
332         if (gFace->IsUPeriodic())
333         {
334           if ((myumax - myumin) > (umax - umin))
335             myumax = myumin + (umax - umin);
336         }
337         else
338         {
339           if (umin > myumin)
340             myumin = umin;
341
342           if (umax < myumax)
343             myumax = umax;
344         }
345       }
346
347       if (myvmin < vmin || myvmax > vmax)
348       {
349         if (gFace->IsVPeriodic())
350         {
351           if ((myvmax - myvmin) > (vmax - vmin))
352             myvmax = myvmin + (vmax - vmin);
353         }
354         else
355         {
356           if ( vmin > myvmin )
357             myvmin = vmin;
358
359           if (vmax < myvmax)
360             myvmax = vmax;
361         }
362       }
363
364       GeomAbs_SurfaceType aSurfType = gFace->GetType();
365       // Fast verification of the validity of calculated limits.
366       // If wrong, sure a problem of pcurve.
367       if (aSurfType == GeomAbs_BezierSurface &&
368          (myumin < -0.5 || myumax > 1.5 || myvmin < -0.5 || myvmax > 1.5) )
369       {
370         myAttribute->ChangeStructure().Nullify();
371         myAttribute->SetStatus(BRepMesh_Failure);
372         return myAttribute->GetStatus();
373       }
374
375       //define parameters for correct parametrics
376       Standard_Real deltaX = 1.0;
377       Standard_Real deltaY = 1.0;
378
379       {
380         Standard_Real aTolU, aTolV;
381         myAttribute->ChangeStructure()->Data()->GetTolerance(aTolU, aTolV);
382         const Standard_Real aTol = Sqrt(aTolU * aTolU + aTolV * aTolV);
383
384         BRepMesh::HClassifier& aClassifier = myAttribute->ChangeClassifier();
385         BRepMesh_WireChecker aDFaceChecker(aFace, aTol, aInternalEdges, 
386           aVertexEdgeMap, myAttribute->ChangeStructure(),
387           myumin, myumax, myvmin, myvmax, myParameters.InParallel );
388
389         aDFaceChecker.ReCompute(aClassifier);
390         BRepMesh_Status aCheckStatus = aDFaceChecker.Status();
391
392         if (aCheckStatus == BRepMesh_SelfIntersectingWire)
393         {
394           Standard_Integer nbmaill = 0;
395           Standard_Real eps = Precision::Confusion();
396           while (nbmaill < 5 && aCheckStatus != BRepMesh_ReMesh)
397           {
398             ++nbmaill;
399
400             resetDataStructure();
401
402             for (TopoDS_Iterator aWireIt(aFace); aWireIt.More(); aWireIt.Next())
403             {
404               for (TopoDS_Iterator aEdgeIt(aWireIt.Value()); aEdgeIt.More(); aEdgeIt.Next(), ++nbEdge)
405               {
406                 const TopoDS_Edge& anEdge = TopoDS::Edge(aEdgeIt.Value());
407                 if (anEdge.IsNull())
408                   continue;
409                 if (myEdges.IsBound(anEdge))
410                   myEdges.UnBind(anEdge);
411
412                 defedge = Max(myMapdefle(anEdge) / 3.0, eps);
413                 myMapdefle.Bind(anEdge, defedge);
414
415                 Standard_Real aFirstParam, aLastParam;
416                 Handle(Geom2d_Curve) aCurve2d =
417                   BRep_Tool::CurveOnSurface(anEdge, aFace, aFirstParam, aLastParam);
418                 if (aCurve2d.IsNull())
419                   continue;
420
421                 EdgePCurve aPCurve = { aCurve2d, aFirstParam, aLastParam };
422                 add(anEdge, aPCurve, defedge);
423               }
424             }
425
426             aDFaceChecker.ReCompute(aClassifier);
427             if (aDFaceChecker.Status() == BRepMesh_NoError)
428               aCheckStatus = BRepMesh_ReMesh;
429           }
430         }
431
432         myAttribute->SetStatus(aCheckStatus);
433         if (!myAttribute->IsValid())
434         {
435           myAttribute->ChangeStructure().Nullify();
436           return myAttribute->GetStatus();
437         }
438       }
439
440       // try to find the real length:
441       // akm (bug OCC16) : We must calculate these measures in non-singular
442       //     parts of face. Let's try to compute average value of three
443       //     (umin, (umin+umax)/2, umax), and respectively for v.
444       //                 vvvvv
445       Standard_Real longu = 0.0, longv = 0.0; //, last , first;
446       gp_Pnt P11, P12, P21, P22, P31, P32;
447
448       Standard_Real du = 0.05 * ( myumax - myumin );
449       Standard_Real dv = 0.05 * ( myvmax - myvmin );
450       Standard_Real dfuave = 0.5 * ( myumin + myumax );
451       Standard_Real dfvave = 0.5 * ( myvmin + myvmax );
452       Standard_Real dfucur, dfvcur;
453
454       // U loop
455       gFace->D0(myumin, myvmin, P11);
456       gFace->D0(myumin, dfvave, P21);
457       gFace->D0(myumin, myvmax, P31);
458       for (i1=1, dfucur=myumin+du; i1 <= 20; i1++, dfucur+=du)
459       {
460         gFace->D0(dfucur, myvmin, P12);
461         gFace->D0(dfucur, dfvave, P22);
462         gFace->D0(dfucur, myvmax, P32);
463         longu += ( P11.Distance(P12) + P21.Distance(P22) + P31.Distance(P32) );
464         P11 = P12;
465         P21 = P22;
466         P31 = P32;
467       }
468
469       // V loop
470       gFace->D0(myumin, myvmin, P11);
471       gFace->D0(dfuave, myvmin, P21);
472       gFace->D0(myumax, myvmin, P31);
473       for (i1=1, dfvcur=myvmin+dv; i1 <= 20; i1++, dfvcur+=dv)
474       {
475         gFace->D0(myumin, dfvcur, P12);
476         gFace->D0(dfuave, dfvcur, P22);
477         gFace->D0(myumax, dfvcur, P32);
478         longv += ( P11.Distance(P12) + P21.Distance(P22) + P31.Distance(P32) );
479         P11 = P12;
480         P21 = P22;
481         P31 = P32;
482       }
483
484       longu /= 3.;
485       longv /= 3.;
486       // akm (bug OCC16) ^^^^^
487
488       if (longu <= 1.e-16 || longv <= 1.e-16)
489       {
490         //yes, it is seen!!
491         myAttribute->ChangeStructure().Nullify();
492         myAttribute->SetStatus(BRepMesh_Failure);
493         return myAttribute->GetStatus();
494       }
495
496
497       if (aSurfType == GeomAbs_Torus)
498       {
499         gp_Torus Tor = gFace->Torus();
500         Standard_Real r = Tor.MinorRadius(), R = Tor.MajorRadius();
501         Standard_Real Du, Dv;//, pasu, pasv;
502
503         Dv = Max(1.0e0 - (defface/r),0.0e0) ;
504         Standard_Real oldDv = 2.0 * ACos (Dv);
505         oldDv = Min(oldDv, myParameters.Angle);
506         Dv  =  0.9*oldDv; //TWOTHIRD * oldDv;
507         Dv = oldDv;
508
509         Standard_Integer nbV = Max((Standard_Integer)((myvmax-myvmin)/Dv), 2);
510         Dv = (myvmax-myvmin)/(nbV+1);
511
512         Standard_Real ru = R + r;
513         if ( ru > 1.e-16 )
514         {
515           Du = Max(1.0e0 - (defface/ru),0.0e0);
516           Du  = (2.0 * ACos (Du));
517           Du = Min(Du, myParameters.Angle);
518           Standard_Real aa = sqrt(Du*Du + oldDv*oldDv);
519
520           if (aa < gp::Resolution())
521           {
522             myAttribute->ChangeStructure().Nullify();
523             return myAttribute->GetStatus();
524           }
525
526           Du = Du * Min(oldDv, Du) / aa;
527         }
528         else
529         {
530           Du = Dv;
531         }
532
533         Standard_Integer nbU = Max((Standard_Integer)((myumax-myumin)/Du), 2);
534         nbU = Max(nbU, (Standard_Integer)(nbV*(myumax-myumin)*R/((myvmax-myvmin)*r)/5.));
535       
536         Du = (myumax-myumin)/(nbU+1);
537         //-- DeltaX and DeltaY are chosen so that to avoid "jumping" 
538         //-- of points on the grid
539         deltaX = Du;
540         deltaY = Dv;
541       }
542       else if (aSurfType == GeomAbs_Cylinder)
543       {
544         gp_Cylinder Cyl = gFace->Cylinder();
545         Standard_Real R = Cyl.Radius();
546
547         // Calculate parameters for iteration in U direction
548         Standard_Real Du = 1.0 - (defface/R);
549         if (Du < 0.0)
550           Du = 0.0;
551
552         Du = 2.0 * ACos (Du);
553         if (Du > myParameters.Angle)
554           Du = myParameters.Angle;
555
556         deltaX = Du / longv;
557         deltaY = 1.;
558       }
559       else
560       {
561         deltaX = (myumax-myumin)/longu;
562         deltaY = (myvmax-myvmin)/longv;
563       }
564
565       // Restore face attribute
566       myAttribute->SetDefFace(defface);
567       myAttribute->SetUMax(myumax);
568       myAttribute->SetVMax(myvmax);
569       myAttribute->SetUMin(myumin);
570       myAttribute->SetVMin(myvmin);
571       myAttribute->SetDeltaX(deltaX);
572       myAttribute->SetDeltaY(deltaY);
573     }
574
575     myAttribute->ChangeMeshNodes() = 
576       myAttribute->ChangeStructure()->Data()->Vertices();
577   }
578   catch(Standard_Failure)
579   {
580     myAttribute->SetStatus(BRepMesh_Failure);
581   }
582
583   myAttribute->ChangeStructure().Nullify();
584   return myAttribute->GetStatus();
585 }
586
587 //=======================================================================
588 //function : getEdgeAttributes
589 //purpose  :
590 //=======================================================================
591 Standard_Boolean BRepMesh_FastDiscret::getEdgeAttributes(
592   const TopoDS_Edge&                      theEdge,
593   const BRepMesh_FastDiscret::EdgePCurve& thePCurve,
594   const Standard_Real                     theDefEdge,
595   BRepMesh_FastDiscret::EdgeAttributes&   theAttributes) const
596 {
597   EdgeAttributes& aEAttr = theAttributes;
598
599   // Get vertices
600   TopExp::Vertices(theEdge, aEAttr.FirstVertex, aEAttr.LastVertex);
601   if (aEAttr.FirstVertex.IsNull() || aEAttr.LastVertex.IsNull())
602     return Standard_False;
603
604   // Get range on 2d curve
605   const TopoDS_Face& aFace = myAttribute->Face();
606   BRep_Tool::Range(theEdge, aFace, aEAttr.FirstParam, aEAttr.LastParam);
607
608   // Get end points on 2d curve
609   BRep_Tool::UVPoints(theEdge, aFace, aEAttr.FirstUV, aEAttr.LastUV);
610
611   aEAttr.IsSameUV =
612     aEAttr.FirstUV.IsEqual(aEAttr.LastUV, Precision::PConfusion());
613
614   //Control tolerance of vertices
615   const Handle(BRepAdaptor_HSurface)& gFace = myAttribute->Surface();
616   gp_Pnt pFirst = gFace->Value(aEAttr.FirstUV.X(), aEAttr.FirstUV.Y());
617   gp_Pnt pLast  = gFace->Value(aEAttr.LastUV.X(),  aEAttr.LastUV.Y());
618
619   aEAttr.MinDist = 10. * Max(pFirst.Distance(BRep_Tool::Pnt(aEAttr.FirstVertex)),
620                              pLast .Distance(BRep_Tool::Pnt(aEAttr.LastVertex)));
621
622   if (aEAttr.MinDist < BRep_Tool::Tolerance(aEAttr.FirstVertex) ||
623       aEAttr.MinDist < BRep_Tool::Tolerance(aEAttr.LastVertex))
624   {
625     aEAttr.MinDist = theDefEdge;
626   }
627
628   if (aEAttr.IsSameUV)
629   {
630     // 1. is it really sameUV without being degenerated
631     gp_Pnt2d uvF, uvL;
632     thePCurve.Curve2d->D0(thePCurve.FirstParam, uvF);
633     thePCurve.Curve2d->D0(thePCurve.LastParam,  uvL);
634
635     if (!aEAttr.FirstUV.IsEqual(uvF, Precision::PConfusion()))
636       aEAttr.FirstUV = uvF;
637
638     if (!aEAttr.LastUV.IsEqual(uvL, Precision::PConfusion()))
639       aEAttr.LastUV = uvL;
640   }
641
642   return Standard_True;
643 }
644
645 //=======================================================================
646 //function : registerEdgeVertices
647 //purpose  : 
648 //=======================================================================
649 void BRepMesh_FastDiscret::registerEdgeVertices(
650   BRepMesh_FastDiscret::EdgeAttributes& theAttributes,
651   Standard_Integer&                     ipf,
652   Standard_Integer&                     ivf,
653   Standard_Integer&                     isvf,
654   Standard_Integer&                     ipl,
655   Standard_Integer&                     ivl,
656   Standard_Integer&                     isvl)
657 {
658   EdgeAttributes& aEAttr = theAttributes;
659   if (aEAttr.FirstVExtractor.IsNull())
660   {
661     // Use edge geometry to produce tesselation.
662     aEAttr.FirstVExtractor = 
663       new TopoDSVExplorer(aEAttr.FirstVertex, aEAttr.IsSameUV, aEAttr.LastVertex);
664   }
665
666   if (aEAttr.LastVExtractor.IsNull())
667   {
668     // Use edge geometry to produce tesselation.
669     aEAttr.LastVExtractor = 
670       new TopoDSVExplorer(aEAttr.LastVertex, aEAttr.IsSameUV, aEAttr.FirstVertex);
671   }
672
673   gp_XY aTmpUV;
674   // Process first vertex
675   ipf = myAttribute->GetVertexIndex(aEAttr.FirstVExtractor, Standard_True);
676   aTmpUV = BRepMesh_ShapeTool::FindUV(ipf, aEAttr.FirstUV, aEAttr.FirstVertex, 
677     aEAttr.MinDist, myAttribute);
678
679   myAttribute->AddNode(ipf, aTmpUV, BRepMesh_Frontier, ivf, isvf);
680
681   // Process last vertex
682   ipl = aEAttr.LastVertex.IsSame(aEAttr.FirstVertex) ? ipf :
683     myAttribute->GetVertexIndex(aEAttr.LastVExtractor, Standard_True);
684   aTmpUV = BRepMesh_ShapeTool::FindUV(ipl, aEAttr.LastUV, aEAttr.LastVertex, 
685     aEAttr.MinDist, myAttribute);
686
687   myAttribute->AddNode(ipl, aTmpUV, BRepMesh_Frontier, ivl, isvl);
688 }
689
690 //=======================================================================
691 //function : add
692 //purpose  : 
693 //=======================================================================
694 void BRepMesh_FastDiscret::add(
695   const TopoDS_Edge&                      theEdge,
696   const BRepMesh_FastDiscret::EdgePCurve& thePCurve,
697   const Standard_Real                     theDefEdge)
698 {
699   const TopAbs_Orientation orEdge = theEdge.Orientation();
700   if (orEdge == TopAbs_EXTERNAL)
701     return;
702
703   EdgeAttributes aEAttr;
704   if (!getEdgeAttributes(theEdge, thePCurve, theDefEdge, aEAttr))
705     return;
706
707   if (!myEdges.IsBound(theEdge))
708   {
709     update(theEdge, thePCurve.Curve2d, theDefEdge, aEAttr);
710     return;
711   }
712
713   Standard_Integer ipf, ivf, isvf, ipl, ivl, isvl;
714   registerEdgeVertices(aEAttr, ipf, ivf, isvf, ipl, ivl, isvl);
715
716   // If this Edge has been already checked and it is not degenerated, 
717   // the points of the polygon calculated at the first check are retrieved :
718
719   // retrieve the polygone:
720   const BRepMesh_PairOfPolygon&              aPair    = myEdges.Find(theEdge);
721   const Handle(Poly_PolygonOnTriangulation)& aPolygon = aPair.First();
722   const TColStd_Array1OfInteger&             aNodes   = aPolygon->Nodes();
723   Handle(TColStd_HArray1OfReal)              aParams  = aPolygon->Parameters();
724
725   // creation anew:
726   const Standard_Integer  aNodesNb = aNodes.Length();
727   TColStd_Array1OfInteger aNewNodes (1, aNodesNb);
728   TColStd_Array1OfReal    aNewParams(1, aNodesNb);
729
730   aNewNodes (1) = isvf;
731   aNewParams(1) = aEAttr.FirstParam;
732
733   aNewNodes (aNodesNb) = isvl;
734   aNewParams(aNodesNb) = aEAttr.LastParam;
735
736   const TopoDS_Face& aFace = myAttribute->Face();
737   if (!BRepMesh_ShapeTool::IsDegenerated(theEdge, aFace))
738   {
739     BRepMesh_EdgeParameterProvider aProvider(theEdge, aFace, aParams);
740     for (Standard_Integer i = 2; i < aNodesNb; ++i)
741     {
742       const Standard_Integer aPointId = aNodes(i);
743       const gp_Pnt& aPnt = myBoundaryPoints->Find(aPointId);
744
745       const Standard_Real aParam = aProvider.Parameter(i, aPnt);
746       gp_Pnt2d aUV = thePCurve.Curve2d->Value(aParam);
747
748       Standard_Integer iv2, isv;
749       myAttribute->AddNode(aPointId, aUV.Coord(), BRepMesh_OnCurve, iv2, isv);
750
751       aNewNodes (i) = isv;
752       aNewParams(i) = aParam;
753     }
754   }
755
756   Handle(Poly_PolygonOnTriangulation) P1 = 
757     new Poly_PolygonOnTriangulation(aNewNodes, aNewParams);
758
759   storePolygon(theEdge, P1, theDefEdge);
760 }
761
762 //=======================================================================
763 //function : update(edge)
764 //purpose  :
765 //=======================================================================
766 void BRepMesh_FastDiscret::update(
767   const TopoDS_Edge&                                theEdge,
768   const Handle(Geom2d_Curve)&                       theC2d,
769   const Standard_Real                               theDefEdge,
770   BRepMesh_FastDiscret::EdgeAttributes&             theAttributes)
771 {
772   EdgeAttributes& aEAttr = theAttributes;
773
774   const TopoDS_Face& aFace = myAttribute->Face();
775   Handle(BRepMesh_IEdgeTool) aEdgeTool;
776   // Try to find existing tessellation.
777   for (Standard_Integer i = 1; aEdgeTool.IsNull(); ++i)
778   {
779     TopLoc_Location aLoc;
780     Handle(Poly_Triangulation) aTriangulation;
781     Handle(Poly_PolygonOnTriangulation) aPolygon;
782     BRep_Tool::PolygonOnTriangulation(theEdge, aPolygon, aTriangulation, aLoc, i);
783
784     if (aPolygon.IsNull())
785       break;
786
787     if (aTriangulation.IsNull() || !aPolygon->HasParameters())
788       continue;
789
790     if (aPolygon->Deflection() > 1.1 * theDefEdge)
791       continue;
792
793     const TColgp_Array1OfPnt&      aNodes   = aTriangulation->Nodes();
794     const TColStd_Array1OfInteger& aIndices = aPolygon->Nodes();
795     Handle(TColStd_HArray1OfReal)  aParams  = aPolygon->Parameters();
796
797     aEAttr.FirstVExtractor = new PolyVExplorer(aEAttr.FirstVertex, 
798       aEAttr.IsSameUV, aEAttr.LastVertex, aIndices(1), aNodes, aLoc);
799
800     aEAttr.LastVExtractor = new PolyVExplorer(aEAttr.LastVertex, 
801       aEAttr.IsSameUV, aEAttr.FirstVertex, aIndices(aIndices.Length()), aNodes, aLoc);
802
803     aEdgeTool = new BRepMesh_EdgeTessellationExtractor(theEdge, theC2d, 
804       aFace, aTriangulation, aPolygon, aLoc);
805   }
806
807   if (aEdgeTool.IsNull())
808   {
809     aEdgeTool = new BRepMesh_EdgeTessellator(theEdge, myAttribute, 
810       mySharedFaces, theDefEdge, myParameters.Angle, myParameters.MinSize);
811   }
812
813   Standard_Integer ipf, ivf, isvf, ipl, ivl, isvl;
814   registerEdgeVertices(aEAttr, ipf, ivf, isvf, ipl, ivl, isvl);
815
816   Handle(Poly_PolygonOnTriangulation) P1, P2;
817   if (BRepMesh_ShapeTool::IsDegenerated(theEdge, aFace))
818   {
819     // two nodes
820     Standard_Integer aNewNodesArr[] = {isvf, isvl};
821     Standard_Integer aNewNodInStructArr[] = {ipf, ipl};
822     Standard_Real aNewParamsArr[] = {aEAttr.FirstParam, aEAttr.LastParam};
823     TColStd_Array1OfInteger aNewNodes      (aNewNodesArr[0], 1, 2);
824     TColStd_Array1OfInteger aNewNodInStruct(aNewNodInStructArr[0], 1, 2);
825     TColStd_Array1OfReal    aNewParams     (aNewParamsArr[0], 1, 2);
826
827     P1 = new Poly_PolygonOnTriangulation(aNewNodes,       aNewParams);
828     P2 = new Poly_PolygonOnTriangulation(aNewNodInStruct, aNewParams);
829   }
830   else
831   {
832     const Standard_Integer  aNodesNb = aEdgeTool->NbPoints();
833     // Allocate the memory for arrays aNewNodesVec, aNewNodesInStructVec, aNewParamsVec
834     // only once using the buffer aBuf.
835     TColStd_Array1OfCharacter aBuf(1, aNodesNb * (2*sizeof(Standard_Integer) + sizeof(Standard_Real)));
836     TColStd_Array1OfInteger aNewNodesVec(*reinterpret_cast<const Standard_Integer*>
837       (&aBuf(1)), 1, aNodesNb);
838     TColStd_Array1OfInteger aNewNodesInStructVec(*reinterpret_cast<const Standard_Integer*>
839       (&aBuf(1 + aNodesNb*sizeof(Standard_Integer))), 1, aNodesNb);
840     TColStd_Array1OfReal    aNewParamsVec(*reinterpret_cast<const Standard_Real*>
841       (&aBuf(1 + aNodesNb*2*sizeof(Standard_Integer))), 1, aNodesNb);
842
843     Standard_Integer aNodesCount = 1;
844     aNewNodesInStructVec(aNodesCount) = ipf;
845     aNewNodesVec        (aNodesCount) = isvf;
846     aNewParamsVec       (aNodesCount) = aEAttr.FirstParam;
847
848     ++aNodesCount;
849     Standard_Integer aLastPointId = myAttribute->LastPointId();
850     for (Standard_Integer i = 2; i < aNodesNb; ++i)
851     {
852       gp_Pnt        aPnt;
853       gp_Pnt2d      aUV;
854       Standard_Real aParam;
855       if (!aEdgeTool->Value(i, aParam, aPnt, aUV))
856         continue;
857
858       myBoundaryPoints->Bind(++aLastPointId, aPnt);
859
860       Standard_Integer iv2, isv;
861       myAttribute->AddNode(aLastPointId, aUV.Coord(), BRepMesh_Frontier, iv2, isv);
862
863       aNewNodesInStructVec(aNodesCount) = aLastPointId;
864       aNewNodesVec        (aNodesCount) = isv;
865       aNewParamsVec       (aNodesCount) = aParam;
866       ++aNodesCount;
867     }
868
869     aNewNodesInStructVec(aNodesCount) = ipl;
870     aNewNodesVec        (aNodesCount) = isvl;
871     aNewParamsVec       (aNodesCount) = aEAttr.LastParam;
872
873     TColStd_Array1OfInteger aNewNodes      (aNewNodesVec.First (),        1, aNodesCount);
874     TColStd_Array1OfInteger aNewNodInStruct(aNewNodesInStructVec.First(), 1, aNodesCount);
875     TColStd_Array1OfReal    aNewParams     (aNewParamsVec.First(),        1, aNodesCount);
876
877     P1 = new Poly_PolygonOnTriangulation(aNewNodes,       aNewParams);
878     P2 = new Poly_PolygonOnTriangulation(aNewNodInStruct, aNewParams);
879   }
880
881   storePolygon(theEdge, P1, theDefEdge);
882   storePolygonSharedData(theEdge, P2, theDefEdge);
883 }
884
885 //=======================================================================
886 //function : storeInternalPolygon
887 //purpose  : 
888 //=======================================================================
889 void BRepMesh_FastDiscret::storePolygon(
890   const TopoDS_Edge&                         theEdge,
891   Handle(Poly_PolygonOnTriangulation)&       thePolygon,
892   const Standard_Real                        theDeflection)
893 {
894   thePolygon->Deflection(theDeflection);
895   BRepMesh::HDMapOfShapePairOfPolygon& aInternalEdges = myAttribute->ChangeInternalEdges();
896   if (aInternalEdges->IsBound(theEdge))
897   {
898     BRepMesh_PairOfPolygon& aPair = aInternalEdges->ChangeFind(theEdge);
899     if (theEdge.Orientation() == TopAbs_REVERSED)
900       aPair.Append(thePolygon);
901     else
902       aPair.Prepend(thePolygon);
903
904     return;
905   }
906
907   BRepMesh_PairOfPolygon aPair;
908   aPair.Append(thePolygon);
909   aInternalEdges->Bind(theEdge, aPair);
910 }
911
912 //=======================================================================
913 //function : storePolygonSharedData
914 //purpose  : 
915 //=======================================================================
916 void BRepMesh_FastDiscret::storePolygonSharedData(
917   const TopoDS_Edge&                         theEdge,
918   Handle(Poly_PolygonOnTriangulation)&       thePolygon,
919   const Standard_Real                        theDeflection)
920 {
921   thePolygon->Deflection(theDeflection);
922   BRepMesh_PairOfPolygon aPair;
923   aPair.Append(thePolygon);
924   myEdges.Bind(theEdge, aPair);
925 }
926
927 //=======================================================================
928 //function : GetFaceAttribute
929 //purpose  : 
930 //=======================================================================
931 Standard_Boolean BRepMesh_FastDiscret::GetFaceAttribute(
932   const TopoDS_Face&              theFace,
933   Handle(BRepMesh_FaceAttribute)& theAttribute,
934   const Standard_Boolean          isForceCreate) const
935 {
936   if (myAttributes.IsBound(theFace))
937   {
938     theAttribute = myAttributes(theFace);
939     return Standard_True;
940   }
941   else if (isForceCreate)
942   {
943     theAttribute = new BRepMesh_FaceAttribute(myBoundaryVertices, myBoundaryPoints);
944     myAttributes.Bind(theFace, theAttribute);
945   }
946
947   return Standard_False;
948 }
949
950 //=======================================================================
951 //function : RemoveFaceAttribute
952 //purpose  : 
953 //=======================================================================
954 void BRepMesh_FastDiscret::RemoveFaceAttribute(const TopoDS_Face& theFace)
955 {
956   if (myAttributes.IsBound(theFace))
957     myAttributes.UnBind(theFace);
958 }