0029935: Foundation Classes - introduce OSD_ThreadPool class defining a thread pool
[occt.git] / src / BRepMesh / BRepMesh_IncrementalMesh.cxx
1 // Created on: 1995-06-20
2 // Created by: Stagiaire Alain JOURDAIN
3 // Copyright (c) 1995-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_IncrementalMesh.hxx>
18
19 #include <OSD_Parallel.hxx>
20 #include <Precision.hxx>
21 #include <Standard_ErrorHandler.hxx>
22
23 #include <BRepMesh_ShapeTool.hxx>
24 #include <BRepMesh_Edge.hxx>
25 #include <BRepMesh_PluginMacro.hxx>
26
27 #include <Bnd_Box.hxx>
28 #include <BRep_Builder.hxx>
29 #include <BRep_Tool.hxx>
30 #include <BRepTools.hxx>
31 #include <BRepLib.hxx>
32 #include <BRepBndLib.hxx>
33 #include <BRepAdaptor_Curve.hxx>
34
35 #include <Poly_Triangulation.hxx>
36 #include <Poly_Polygon3D.hxx>
37 #include <Poly_PolygonOnTriangulation.hxx>
38
39 #include <TopoDS.hxx>
40 #include <TopoDS_Edge.hxx>
41 #include <TopoDS_Face.hxx>
42 #include <TopoDS_Shape.hxx>
43 #include <TopAbs.hxx>
44 #include <TopExp.hxx>
45 #include <TopExp_Explorer.hxx>
46
47 #include <TopTools_ListIteratorOfListOfShape.hxx>
48 #include <TColgp_Array1OfPnt.hxx>
49 #include <TColgp_Array1OfPnt2d.hxx>
50 #include <TColStd_Array1OfReal.hxx>
51 #include <TColStd_MapOfTransient.hxx>
52 #include <TopTools_HArray1OfShape.hxx>
53 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
54
55 #include <GCPnts_TangentialDeflection.hxx>
56
57 IMPLEMENT_STANDARD_RTTIEXT(BRepMesh_IncrementalMesh,BRepMesh_DiscretRoot)
58
59 namespace
60 {
61   //! Default flag to control parallelization for BRepMesh_IncrementalMesh
62   //! tool returned for Mesh Factory
63   static Standard_Boolean IS_IN_PARALLEL = Standard_False;
64 }
65
66
67 //=======================================================================
68 //function : Default constructor
69 //purpose  : 
70 //=======================================================================
71 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh()
72 : myMaxShapeSize(0.),
73   myModified(Standard_False),
74   myStatus(0)
75 {
76 }
77
78 //=======================================================================
79 //function : Constructor
80 //purpose  : 
81 //=======================================================================
82 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh( const TopoDS_Shape&    theShape,
83                                                     const Standard_Real    theLinDeflection,
84                                                     const Standard_Boolean isRelative,
85                                                     const Standard_Real    theAngDeflection,
86                                                     const Standard_Boolean isInParallel,
87                                                     const Standard_Boolean adaptiveMin)
88 : myMaxShapeSize(0.),
89   myModified(Standard_False),
90   myStatus(0)
91 {
92   myParameters.Deflection = theLinDeflection;
93   myParameters.Relative = isRelative;
94   myParameters.Angle = theAngDeflection;
95   myParameters.InParallel = isInParallel;
96   myParameters.AdaptiveMin = adaptiveMin;
97
98   myShape = theShape;
99   Perform();
100 }
101
102 //=======================================================================
103 //function : Constructor
104 //purpose  : 
105 //=======================================================================
106 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh(const TopoDS_Shape& theShape,
107                                                    const BRepMesh_FastDiscret::Parameters& theParameters)
108   : myParameters(theParameters)
109 {
110   myShape       = theShape;
111   
112   Perform();
113 }
114
115 //=======================================================================
116 //function : Destructor
117 //purpose  : 
118 //=======================================================================
119 BRepMesh_IncrementalMesh::~BRepMesh_IncrementalMesh()
120 {
121 }
122
123 //=======================================================================
124 //function : clear
125 //purpose  : 
126 //=======================================================================
127 void BRepMesh_IncrementalMesh::clear()
128 {
129   // the allocator will be alive while the structures are alive
130   Handle(NCollection_BaseAllocator) anAlloc =
131     new NCollection_IncAllocator(BRepMesh::MEMORY_BLOCK_SIZE_HUGE);
132   myEdges.Clear(anAlloc);
133   myEdgeDeflection.Clear(anAlloc);
134   myFaces.Clear();
135   myMesh.Nullify();
136 }
137
138 //=======================================================================
139 //function : init
140 //purpose  : 
141 //=======================================================================
142 void BRepMesh_IncrementalMesh::init() 
143 {
144   myStatus   = 0;
145   myModified = Standard_False;
146
147   setDone();
148   clear();
149
150   collectFaces();
151
152   Bnd_Box aBox;
153   if ( myParameters.Relative ) 
154   {
155     BRepBndLib::Add(myShape, aBox, Standard_False);
156
157     if (aBox.IsVoid())
158     {
159       // Nothing to mesh.
160       return;
161     }
162
163     BRepMesh_ShapeTool::BoxMaxDimension(aBox, myMaxShapeSize);
164   }
165
166   myMesh = new BRepMesh_FastDiscret (aBox, myParameters);
167   
168   myMesh->InitSharedFaces(myShape);
169 }
170
171 //=======================================================================
172 //function : collectFaces
173 //purpose  : 
174 //=======================================================================
175 void BRepMesh_IncrementalMesh::collectFaces()
176 {
177   Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
178   TopTools_ListOfShape aFaceList(anAlloc);
179   BRepLib::ReverseSortFaces(myShape, aFaceList);
180   TColStd_MapOfTransient aTFaceMap(1, anAlloc);
181
182   // make array of faces suitable for processing (excluding faces without surface)
183   TopLoc_Location aDummyLoc;
184   TopTools_ListIteratorOfListOfShape aFaceIter(aFaceList);
185   for (; aFaceIter.More(); aFaceIter.Next())
186   {
187     const TopoDS_Face& aFace = TopoDS::Face(aFaceIter.Value());
188     const Handle(TopoDS_TShape)& aTFace = aFace.TShape();
189     if (!aTFaceMap.Add (aTFace))
190       continue; // already processed
191
192     const Handle(Geom_Surface)& aSurf = BRep_Tool::Surface(aFace, aDummyLoc);
193     if (aSurf.IsNull())
194       continue;
195
196     myFaces.Append(aFace);
197   }
198 }
199
200 //=======================================================================
201 //function : Perform
202 //purpose  : 
203 //=======================================================================
204 void BRepMesh_IncrementalMesh::Perform()
205 {
206   init();
207
208   if (myMesh.IsNull())
209     return;
210
211   update();
212 }
213
214 //=======================================================================
215 //function : update()
216 //purpose  : 
217 //=======================================================================
218 void BRepMesh_IncrementalMesh::update()
219 {
220   // Update edges data
221   TopExp_Explorer aExplorer(myShape, TopAbs_EDGE);
222   for (; aExplorer.More(); aExplorer.Next())
223   {
224     const TopoDS_Edge& aEdge = TopoDS::Edge(aExplorer.Current());
225     if(!BRep_Tool::IsGeometric(aEdge))
226       continue;
227
228     update(aEdge);
229   }
230
231   // Update faces data
232   NCollection_Vector<TopoDS_Face>::Iterator aFaceIt(myFaces);
233   for (; aFaceIt.More(); aFaceIt.Next())
234     update(aFaceIt.Value());
235
236   // Mesh faces
237   OSD_Parallel::ForEach(myFaces.begin(), myFaces.end(), *myMesh, !myParameters.InParallel, myFaces.Size());
238
239   commit();
240   clear();
241 }
242
243 //=======================================================================
244 //function : discretizeFreeEdges
245 //purpose  : 
246 //=======================================================================
247 void BRepMesh_IncrementalMesh::discretizeFreeEdges()
248 {
249   TopExp_Explorer aExplorer(myShape ,TopAbs_EDGE, TopAbs_FACE);
250   for (; aExplorer.More(); aExplorer.Next())
251   {
252     const TopoDS_Edge& aEdge = TopoDS::Edge(aExplorer.Current());
253     if(!BRep_Tool::IsGeometric(aEdge))
254       continue;
255     
256     TopLoc_Location aLoc;
257     Standard_Real aEdgeDeflection  = edgeDeflection(aEdge);
258     Handle(Poly_Polygon3D) aPoly3D = BRep_Tool::Polygon3D(aEdge, aLoc);
259     if (!aPoly3D.IsNull() && aPoly3D->Deflection() < 1.1 * aEdgeDeflection)
260       continue;
261
262     BRepAdaptor_Curve aCurve(aEdge);
263     GCPnts_TangentialDeflection aDiscret(aCurve, aCurve.FirstParameter(),
264       aCurve.LastParameter(), myParameters.Angle, aEdgeDeflection, 2,
265       Precision::PConfusion(), myParameters.MinSize);
266
267     Standard_Integer aNodesNb = aDiscret.NbPoints();
268     TColgp_Array1OfPnt   aNodes  (1, aNodesNb);
269     TColStd_Array1OfReal aUVNodes(1, aNodesNb);
270     for (Standard_Integer i = 1; i <= aNodesNb; ++i)
271     {
272       aNodes  (i) = aDiscret.Value(i);
273       aUVNodes(i) = aDiscret.Parameter(i);
274     }
275     
276     aPoly3D = new Poly_Polygon3D(aNodes, aUVNodes);
277     aPoly3D->Deflection(myParameters.Deflection);
278
279     BRep_Builder aBuilder;
280     aBuilder.UpdateEdge(aEdge, aPoly3D);
281   }
282 }
283
284 //=======================================================================
285 //function : edgeDeflection
286 //purpose  : 
287 //=======================================================================
288 Standard_Real BRepMesh_IncrementalMesh::edgeDeflection(
289   const TopoDS_Edge& theEdge)
290 {
291   const Standard_Real* pDef = myEdgeDeflection.Seek(theEdge);
292   if (pDef)
293     return *pDef;
294
295   Standard_Real aEdgeDeflection;
296   if ( myParameters.Relative ) 
297   {
298     Standard_Real aScale;
299     aEdgeDeflection = BRepMesh_ShapeTool::RelativeEdgeDeflection(theEdge, 
300       myParameters.Deflection, myMaxShapeSize, aScale);
301   }
302   else
303     aEdgeDeflection = myParameters.Deflection;
304
305   myEdgeDeflection.Bind(theEdge, aEdgeDeflection);
306   return aEdgeDeflection;
307 }
308
309 //=======================================================================
310 //function : faceDeflection
311 //purpose  : 
312 //=======================================================================
313 Standard_Real BRepMesh_IncrementalMesh::faceDeflection(
314   const TopoDS_Face& theFace)
315 {
316   if ( !myParameters.Relative )
317     return myParameters.Deflection;
318
319   Standard_Integer aEdgesNb        = 0;
320   Standard_Real    aFaceDeflection = 0.;
321
322   TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
323   for (; aEdgeIt.More(); aEdgeIt.Next(), ++aEdgesNb)
324   {
325     const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
326     aFaceDeflection += edgeDeflection(aEdge);
327   }
328
329   return (aEdgesNb == 0) ? myParameters.Deflection : (aFaceDeflection / aEdgesNb);
330 }
331
332 //=======================================================================
333 //function : update(edge)
334 //purpose  : 
335 //=======================================================================
336 void BRepMesh_IncrementalMesh::update(const TopoDS_Edge& theEdge)
337 {
338   if (!myEdges.IsBound(theEdge))
339     myEdges.Bind(theEdge, BRepMesh::DMapOfTriangulationBool(3, myEdges.Allocator()));
340
341   Standard_Real aEdgeDeflection = edgeDeflection(theEdge);
342   // Check that triangulation relies to face of the given shape.
343   const TopTools_IndexedDataMapOfShapeListOfShape& aMapOfSharedFaces = 
344     myMesh->SharedFaces();
345
346   const TopTools_ListOfShape& aSharedFaces = 
347     aMapOfSharedFaces.FindFromKey(theEdge);
348
349   TopTools_ListIteratorOfListOfShape aSharedFaceIt(aSharedFaces);
350   for (; aSharedFaceIt.More(); aSharedFaceIt.Next())
351   {
352     TopLoc_Location aLoc;
353     const TopoDS_Face& aFace = TopoDS::Face(aSharedFaceIt.Value());
354     const Handle(Poly_Triangulation)& aFaceTriangulation = 
355       BRep_Tool::Triangulation(aFace, aLoc);
356
357     if (aFaceTriangulation.IsNull())
358       continue;
359
360     Standard_Boolean isConsistent = Standard_False;
361     const Handle(Poly_PolygonOnTriangulation)& aPolygon =
362       BRep_Tool::PolygonOnTriangulation(theEdge, aFaceTriangulation, aLoc);
363
364     if (!aPolygon.IsNull())
365     {
366       isConsistent = aPolygon->Deflection() < 1.1 * aEdgeDeflection &&
367         aPolygon->HasParameters();
368
369       if (!isConsistent)
370       {
371         myModified = Standard_True;
372         BRepMesh_ShapeTool::NullifyEdge(theEdge, aFaceTriangulation, aLoc);
373       }
374     }
375
376     myEdges(theEdge).Bind(aFaceTriangulation, isConsistent);
377   }
378 }
379
380 //=======================================================================
381 //function : isToBeMeshed
382 //purpose  : 
383 //=======================================================================
384 Standard_Boolean BRepMesh_IncrementalMesh::toBeMeshed(
385   const TopoDS_Face&     theFace,
386   const Standard_Boolean isWithCheck)
387 {
388   TopLoc_Location aLoc;
389   const Handle(Poly_Triangulation)& aTriangulation = 
390     BRep_Tool::Triangulation(theFace, aLoc);
391
392   if (aTriangulation.IsNull())
393     return Standard_True;
394
395   if (isWithCheck)
396   {
397     Standard_Real aFaceDeflection = faceDeflection(theFace);
398     if (aTriangulation->Deflection() < 1.1 * aFaceDeflection)
399     {
400       Standard_Boolean isEdgesConsistent = Standard_True;
401       TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
402       for (; aEdgeIt.More() && isEdgesConsistent; aEdgeIt.Next())
403       {
404         const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
405         if (!myEdges.IsBound(aEdge))
406           continue;
407
408         BRepMesh::DMapOfTriangulationBool& aTriMap = myEdges(aEdge);
409         isEdgesConsistent &= aTriMap.IsBound(aTriangulation) &&
410           aTriMap(aTriangulation);
411       }
412
413       if (isEdgesConsistent)
414       {
415         // #25080: check that indices of links forming triangles are in range.
416         Standard_Boolean isTriangulationConsistent = Standard_True;
417         const Standard_Integer aNodesNb = aTriangulation->NbNodes();
418         const Poly_Array1OfTriangle& aTriangles = aTriangulation->Triangles();
419         Standard_Integer i = aTriangles.Lower();
420         for (; i <= aTriangles.Upper() && isTriangulationConsistent; ++i)
421         {
422           const Poly_Triangle& aTriangle = aTriangles(i);
423           Standard_Integer n[3];
424           aTriangle.Get(n[0], n[1], n[2]);
425           for (Standard_Integer j = 0; j < 3 && isTriangulationConsistent; ++j)
426             isTriangulationConsistent = (n[j] >= 1 && n[j] <= aNodesNb);
427         }
428
429         if (isTriangulationConsistent)
430           return Standard_False;
431       }
432     }
433   }
434
435   // Nullify edges
436   TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
437   for (; aEdgeIt.More(); aEdgeIt.Next())
438   {
439     const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
440     BRepMesh_ShapeTool::NullifyEdge(aEdge, aTriangulation, aLoc);
441   }
442
443   BRepMesh_ShapeTool::NullifyFace(theFace);
444   return Standard_True;
445 }
446
447 //=======================================================================
448 //function : update(face)
449 //purpose  : 
450 //=======================================================================
451 void BRepMesh_IncrementalMesh::update(const TopoDS_Face& theFace)
452 {
453   if (!toBeMeshed(theFace, Standard_True))
454     return;
455
456   myModified = Standard_True;
457   Standard_Integer aStatus = myMesh->Add(theFace);
458
459   myStatus |= aStatus;
460   if (aStatus != BRepMesh_ReMesh)
461     return;
462
463   BRepMesh::MapOfShape aUsedFaces;
464   aUsedFaces.Add(theFace);
465
466   const TopTools_IndexedDataMapOfShapeListOfShape& aMapOfSharedFaces = 
467     myMesh->SharedFaces();
468
469   TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
470   for (; aEdgeIt.More(); aEdgeIt.Next())
471   {
472     const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
473     if (aMapOfSharedFaces.FindIndex(aEdge) == 0)
474       continue;
475      
476     const TopTools_ListOfShape& aSharedFaces = aMapOfSharedFaces.FindFromKey(aEdge);
477     TopTools_ListIteratorOfListOfShape aSharedFaceIt(aSharedFaces);
478     for (; aSharedFaceIt.More(); aSharedFaceIt.Next())
479     {
480       const TopoDS_Face& aFace = TopoDS::Face(aSharedFaceIt.Value());
481       if (aUsedFaces.Contains(aFace))
482         continue;
483
484       aUsedFaces.Add(aFace);
485       toBeMeshed(aFace, Standard_False);
486
487       myStatus |= myMesh->Add(aFace);
488     }
489   }
490 }
491
492 //=======================================================================
493 //function : commit
494 //purpose  : 
495 //=======================================================================
496 void BRepMesh_IncrementalMesh::commit()
497 {
498   NCollection_Vector<TopoDS_Face>::Iterator aFaceIt(myFaces);
499   for (; aFaceIt.More(); aFaceIt.Next())
500     commitEdges(aFaceIt.Value());
501
502   discretizeFreeEdges();
503 }
504
505 //=======================================================================
506 //function : commitEdges
507 //purpose  : 
508 //=======================================================================
509 void BRepMesh_IncrementalMesh::commitEdges(const TopoDS_Face& theFace)
510 {
511   TopoDS_Face aFace = theFace;
512   aFace.Orientation(TopAbs_FORWARD);
513
514   Handle(BRepMesh_FaceAttribute) aFaceAttribute;
515   if (!myMesh->GetFaceAttribute(aFace, aFaceAttribute))
516     return;
517
518   if (!aFaceAttribute->IsValid())
519   {
520     myStatus |= aFaceAttribute->GetStatus();
521     return;
522   }
523
524   TopLoc_Location aLoc;
525   Handle(Poly_Triangulation) aTriangulation = BRep_Tool::Triangulation(aFace, aLoc);
526
527   if (aTriangulation.IsNull())
528     return;
529
530   try
531   {
532     OCC_CATCH_SIGNALS
533
534     // Store discretization of edges
535     BRepMesh::HDMapOfShapePairOfPolygon& aInternalEdges = aFaceAttribute->ChangeInternalEdges();
536     BRepMesh::DMapOfShapePairOfPolygon::Iterator aEdgeIt(*aInternalEdges);
537     for (; aEdgeIt.More(); aEdgeIt.Next())
538     {
539       const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Key());
540       const BRepMesh_PairOfPolygon& aPolyPair = aEdgeIt.Value();
541       const Handle(Poly_PolygonOnTriangulation)& aPolygon1 = aPolyPair.First();
542       const Handle(Poly_PolygonOnTriangulation)& aPolygon2 = aPolyPair.Last();
543
544       if (aPolygon1 == aPolygon2)
545         BRepMesh_ShapeTool::UpdateEdge(aEdge, aPolygon1, aTriangulation, aLoc);
546       else
547         BRepMesh_ShapeTool::UpdateEdge(aEdge, aPolygon1, aPolygon2, aTriangulation, aLoc);
548     }
549   }
550   catch (Standard_Failure)
551   {
552     myStatus |= BRepMesh_Failure;
553   }
554 }
555
556 //=======================================================================
557 //function : Discret
558 //purpose  :
559 //=======================================================================
560 Standard_Integer BRepMesh_IncrementalMesh::Discret(
561   const TopoDS_Shape&    theShape,
562   const Standard_Real    theDeflection,
563   const Standard_Real    theAngle,
564   BRepMesh_DiscretRoot* &theAlgo)
565 {
566   BRepMesh_IncrementalMesh* anAlgo = new BRepMesh_IncrementalMesh();
567   anAlgo->ChangeParameters().Deflection = theDeflection;
568   anAlgo->ChangeParameters().Angle = theAngle;
569   anAlgo->ChangeParameters().InParallel = IS_IN_PARALLEL;
570   anAlgo->SetShape     (theShape);
571   theAlgo = anAlgo;
572   return 0; // no error
573 }
574
575 //=======================================================================
576 //function : IsParallelDefault
577 //purpose  :
578 //=======================================================================
579 Standard_Boolean BRepMesh_IncrementalMesh::IsParallelDefault()
580 {
581   return IS_IN_PARALLEL;
582 }
583
584 //=======================================================================
585 //function : Discret
586 //purpose  :
587 //=======================================================================
588 void BRepMesh_IncrementalMesh::SetParallelDefault(
589   const Standard_Boolean theInParallel)
590 {
591   IS_IN_PARALLEL = theInParallel;
592 }
593
594 //! Export Mesh Plugin entry function
595 DISCRETPLUGIN(BRepMesh_IncrementalMesh)