e313ce718354151b31841fb6faa821329b1eaf96
[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 <Precision.hxx>
20 #include <Standard_Mutex.hxx>
21
22 #include <BRepMesh_FaceChecker.hxx>
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 <TopTools_MutexForShapeProvider.hxx>
49 #include <TColgp_Array1OfPnt.hxx>
50 #include <TColStd_Array1OfReal.hxx>
51 #include <TopTools_HArray1OfShape.hxx>
52
53 #include <GCPnts_TangentialDeflection.hxx>
54
55 #ifdef HAVE_TBB
56   // paralleling using Intel TBB
57   #include <tbb/parallel_for_each.h>
58 #endif
59
60 namespace
61 {
62   //! Default flag to control parallelization for BRepMesh_IncrementalMesh
63   //! tool returned for Mesh Factory
64   static Standard_Boolean IS_IN_PARALLEL = Standard_False;
65 };
66
67 IMPLEMENT_STANDARD_HANDLE (BRepMesh_IncrementalMesh, BRepMesh_DiscretRoot)
68 IMPLEMENT_STANDARD_RTTIEXT(BRepMesh_IncrementalMesh, BRepMesh_DiscretRoot)
69
70 //=======================================================================
71 //function : Default constructor
72 //purpose  : 
73 //=======================================================================
74 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh()
75 : myRelative (Standard_False),
76   myInParallel (Standard_False)
77 {
78 }
79
80 //=======================================================================
81 //function : Constructor
82 //purpose  : 
83 //=======================================================================
84 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh(
85   const TopoDS_Shape&    theShape,
86   const Standard_Real    theLinDeflection,
87   const Standard_Boolean isRelative,
88   const Standard_Real    theAngDeflection,
89   const Standard_Boolean isInParallel)
90   : myRelative  (isRelative),
91     myInParallel(isInParallel)
92 {
93   myDeflection = theLinDeflection;
94   myAngle      = theAngDeflection;
95   myShape      = theShape;
96
97   Perform();
98 }
99
100 //=======================================================================
101 //function : Destructor
102 //purpose  : 
103 //=======================================================================
104 BRepMesh_IncrementalMesh::~BRepMesh_IncrementalMesh()
105 {
106 }
107
108 //=======================================================================
109 //function : init
110 //purpose  : 
111 //=======================================================================
112 void BRepMesh_IncrementalMesh::init() 
113 {
114   myStatus   = 0;
115   myModified = Standard_False;
116
117   myEdgeDeflection.Clear();
118   mySharedFaces.Clear();
119   myFaces.clear();
120
121   setDone();
122
123   if (!isCorrectPolyData())
124     BRepTools::Clean(myShape);
125
126   Bnd_Box aBox;
127   BRepBndLib::Add(myShape, aBox, Standard_False);
128
129   if (aBox.IsVoid())
130   {
131     // Nothing to mesh.
132     myMesher.Nullify();
133     return;
134   }
135
136   BRepMesh_ShapeTool::BoxMaxDimension(aBox, myMaxShapeSize);
137   TopExp::MapShapesAndAncestors(myShape, TopAbs_EDGE, TopAbs_FACE, mySharedFaces);
138
139   myMesher = new BRepMesh_FastDiscret(myDeflection, myAngle, aBox,
140     Standard_True, Standard_True, myRelative, Standard_True, myInParallel);
141 }
142
143 //=======================================================================
144 //function : isCorrectPolyData
145 //purpose  : 
146 //=======================================================================
147 Standard_Boolean BRepMesh_IncrementalMesh::isCorrectPolyData()
148 {
149   collectFaces();
150
151   BRepMesh_FaceChecker aFaceChecker(myInParallel);
152
153 #ifdef HAVE_TBB
154   if (myInParallel)
155   {
156     // check faces in parallel threads using TBB
157     tbb::parallel_for_each(myFaces.begin(), myFaces.end(), aFaceChecker);
158   }
159   else
160   {
161 #endif
162     std::vector<TopoDS_Face>::iterator aFaceIt = myFaces.begin();
163     for (; aFaceIt != myFaces.end(); aFaceIt++)
164       aFaceChecker(*aFaceIt);
165 #ifdef HAVE_TBB
166   }
167 #endif
168
169   return aFaceChecker.IsValid();
170 }
171
172 //=======================================================================
173 //function : collectFaces
174 //purpose  : 
175 //=======================================================================
176 void BRepMesh_IncrementalMesh::collectFaces()
177 {
178   TopTools_ListOfShape aFaceList;
179   BRepLib::ReverseSortFaces(myShape, aFaceList);
180   TopTools_MapOfShape aFaceMap;
181   myFaces.reserve(aFaceList.Extent());
182
183   // make array of faces suitable for processing (excluding faces without surface)
184   TopLoc_Location aDummyLoc;
185   const TopLoc_Location aEmptyLoc;
186   TopTools_ListIteratorOfListOfShape aFaceIter(aFaceList);
187   for (; aFaceIter.More(); aFaceIter.Next())
188   {
189     TopoDS_Shape aFaceNoLoc = aFaceIter.Value();
190     aFaceNoLoc.Location(aEmptyLoc);
191     if (!aFaceMap.Add (aFaceNoLoc))
192       continue; // already processed
193
194     TopoDS_Face aFace = TopoDS::Face(aFaceIter.Value());
195     const Handle(Geom_Surface)& aSurf = BRep_Tool::Surface(aFace, aDummyLoc);
196     if (aSurf.IsNull())
197       continue;
198
199     myFaces.push_back(aFace);
200   }
201 }
202
203 //=======================================================================
204 //function : Perform
205 //purpose  : 
206 //=======================================================================
207 void BRepMesh_IncrementalMesh::Perform()
208 {
209   init();
210
211   if (myMesher.IsNull())
212     return;
213
214   update();
215 }
216
217 //=======================================================================
218 //function : update()
219 //purpose  : 
220 //=======================================================================
221 void BRepMesh_IncrementalMesh::update()
222 {
223   // Update edges data
224   TopExp_Explorer aExplorer(myShape, TopAbs_EDGE);
225   for (; aExplorer.More(); aExplorer.Next())
226   {
227     const TopoDS_Edge& aEdge = TopoDS::Edge(aExplorer.Current());
228     if(!BRep_Tool::IsGeometric(aEdge))
229       continue;
230
231     update(aEdge);
232   }
233
234   // Update faces data
235   std::vector<TopoDS_Face>::iterator aFaceIt(myFaces.begin());
236   for (; aFaceIt != myFaces.end(); aFaceIt++)
237     update(*aFaceIt);
238
239   // Mesh faces
240 #ifdef HAVE_TBB
241   if (myInParallel)
242   {
243     myMesher->CreateMutexesForSubShapes(myShape, TopAbs_EDGE);
244     tbb::parallel_for_each(myFaces.begin(), myFaces.end(), *myMesher);
245     myMesher->RemoveAllMutexes();
246   }
247   else
248   {
249 #endif
250     for (aFaceIt = myFaces.begin(); aFaceIt != myFaces.end(); aFaceIt++)
251       myMesher->Process(*aFaceIt);
252 #ifdef HAVE_TBB
253   }
254 #endif
255
256   discretizeFreeEdges();
257 }
258
259 //=======================================================================
260 //function : discretizeFreeEdges
261 //purpose  : 
262 //=======================================================================
263 void BRepMesh_IncrementalMesh::discretizeFreeEdges()
264 {
265   TopExp_Explorer aExplorer(myShape ,TopAbs_EDGE, TopAbs_FACE);
266   for (; aExplorer.More(); aExplorer.Next())
267   {
268     const TopoDS_Edge& aEdge = TopoDS::Edge(aExplorer.Current());
269     if(!BRep_Tool::IsGeometric(aEdge))
270       continue;
271     
272     TopLoc_Location aLoc;
273     Standard_Real aEdgeDeflection  = edgeDeflection(aEdge);
274     Handle(Poly_Polygon3D) aPoly3D = BRep_Tool::Polygon3D(aEdge, aLoc);
275     if (!aPoly3D.IsNull() && aPoly3D->Deflection() < 1.1 * aEdgeDeflection)
276       continue;
277
278     BRepAdaptor_Curve aCurve(aEdge);
279     GCPnts_TangentialDeflection aDiscret(aCurve, aCurve.FirstParameter(),
280       aCurve.LastParameter(), myAngle, aEdgeDeflection, 2);
281
282     Standard_Integer aNodesNb = aDiscret.NbPoints();
283     TColgp_Array1OfPnt   aNodes  (1, aNodesNb);
284     TColStd_Array1OfReal aUVNodes(1, aNodesNb);
285     for (Standard_Integer i = 1; i <= aNodesNb; ++i)
286     {
287       aNodes  (i) = aDiscret.Value(i);
288       aUVNodes(i) = aDiscret.Parameter(i);
289     }
290     
291     aPoly3D = new Poly_Polygon3D(aNodes, aUVNodes);
292     aPoly3D->Deflection(myDeflection);
293
294     BRep_Builder aBuilder;
295     aBuilder.UpdateEdge(aEdge, aPoly3D);
296   }
297 }
298
299 //=======================================================================
300 //function : edgeDeflection
301 //purpose  : 
302 //=======================================================================
303 Standard_Real BRepMesh_IncrementalMesh::edgeDeflection(
304   const TopoDS_Edge& theEdge)
305 {
306   if (myEdgeDeflection.IsBound(theEdge))
307     return myEdgeDeflection(theEdge);
308
309   Standard_Real aEdgeDeflection;
310   if (myRelative) 
311   {
312     Standard_Real aScale;
313     aEdgeDeflection = BRepMesh_ShapeTool::RelativeEdgeDeflection(theEdge, 
314       myDeflection, myMaxShapeSize, aScale);
315   }
316   else
317     aEdgeDeflection = myDeflection;
318
319   myEdgeDeflection.Bind(theEdge, aEdgeDeflection);
320   return aEdgeDeflection;
321 }
322
323 //=======================================================================
324 //function : faceDeflection
325 //purpose  : 
326 //=======================================================================
327 Standard_Real BRepMesh_IncrementalMesh::faceDeflection(
328   const TopoDS_Face& theFace)
329 {
330   if (!myRelative)
331     return myDeflection;
332
333   Standard_Integer aEdgesNb        = 0;
334   Standard_Real    aFaceDeflection = 0.;
335
336   TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
337   for (; aEdgeIt.More(); aEdgeIt.Next(), ++aEdgesNb)
338   {
339     const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
340     aFaceDeflection += edgeDeflection(aEdge);
341   }
342
343   return (aEdgesNb == 0) ? myDeflection : (aFaceDeflection / aEdgesNb);
344 }
345
346 //=======================================================================
347 //function : update(edge)
348 //purpose  : 
349 //=======================================================================
350 void BRepMesh_IncrementalMesh::update(const TopoDS_Edge& theEdge)
351 {
352   Standard_Integer aPolyIndex   = 1;
353   Standard_Real aEdgeDeflection = edgeDeflection(theEdge);
354   Handle(Poly_PolygonOnTriangulation) aPolygon;
355   do
356   {
357     TopLoc_Location aLoc;
358     Handle(Poly_Triangulation) aTriangulation;
359     BRep_Tool::PolygonOnTriangulation(theEdge, aPolygon, 
360       aTriangulation, aLoc, aPolyIndex++);
361
362     if (!aTriangulation.IsNull() && !aPolygon.IsNull())
363     {
364       if (aPolygon->Deflection() < 1.1 * aEdgeDeflection)
365         continue;
366
367       myModified = Standard_True;
368       BRepMesh_ShapeTool::NullifyEdge(theEdge, aTriangulation, aLoc);
369     }
370
371     if (!myEmptyEdges.IsBound(theEdge))
372       myEmptyEdges.Bind(theEdge, BRepMeshCol::MapOfTriangulation());
373
374     myEmptyEdges(theEdge).Add(aTriangulation);
375   }
376   while (!aPolygon.IsNull());
377 }
378
379 //=======================================================================
380 //function : isToBeMeshed
381 //purpose  : 
382 //=======================================================================
383 Standard_Boolean BRepMesh_IncrementalMesh::toBeMeshed(
384   const TopoDS_Face&     theFace,
385   const Standard_Boolean isWithCheck)
386 {
387   TopLoc_Location aLoc;
388   Handle(Poly_Triangulation) aTriangulation = 
389     BRep_Tool::Triangulation(theFace, aLoc);
390
391   if (aTriangulation.IsNull())
392     return Standard_True;
393
394   if (isWithCheck)
395   {
396     Standard_Real aFaceDeflection = faceDeflection(theFace);
397     if (aTriangulation->Deflection() < 1.1 * aFaceDeflection)
398     {
399       Standard_Boolean isEdgesConsistent = Standard_True;
400       TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
401       for (; aEdgeIt.More() && isEdgesConsistent; aEdgeIt.Next())
402       {
403         const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
404         if (!myEmptyEdges.IsBound(aEdge))
405           continue;
406
407         isEdgesConsistent &= myEmptyEdges(aEdge).Contains(aTriangulation);
408       }
409
410       if (isEdgesConsistent)
411         return Standard_False;
412     }
413   }
414
415   // Nullify edges
416   TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
417   for (; aEdgeIt.More(); aEdgeIt.Next())
418   {
419     const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
420     BRepMesh_ShapeTool::NullifyEdge(aEdge, aTriangulation, aLoc);
421   }
422
423   BRepMesh_ShapeTool::NullifyFace(theFace);
424   return Standard_True;
425 }
426
427 //=======================================================================
428 //function : update(face)
429 //purpose  : 
430 //=======================================================================
431 void BRepMesh_IncrementalMesh::update(const TopoDS_Face& theFace)
432 {
433   if (!toBeMeshed(theFace, Standard_True))
434     return;
435
436   myModified = Standard_True;
437   myMesher->Add(theFace, mySharedFaces);
438
439   BRepMesh_Status aStatus = myMesher->CurrentFaceStatus();
440   myStatus |= (Standard_Integer)aStatus;
441   if (aStatus != BRepMesh_ReMesh)
442     return;
443
444   BRepMeshCol::MapOfShape aUsedFaces;
445   aUsedFaces.Add(theFace);
446
447   TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
448   for (; aEdgeIt.More(); aEdgeIt.Next())
449   {
450     const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
451     if (mySharedFaces.FindIndex(aEdge) == 0)
452       continue;
453      
454     const TopTools_ListOfShape& aSharedFaces = mySharedFaces.FindFromKey(aEdge);
455     TopTools_ListIteratorOfListOfShape aSharedFaceIt(aSharedFaces);
456     for (; aSharedFaceIt.More(); aSharedFaceIt.Next())
457     {
458       const TopoDS_Face& aFace = TopoDS::Face(aSharedFaceIt.Value());
459       if (aUsedFaces.Contains(aFace))
460         continue;
461
462       aUsedFaces.Add(aFace);
463       toBeMeshed(aFace, Standard_False);
464
465       myMesher->Add(aFace, mySharedFaces);
466       myStatus |= (Standard_Integer)myMesher->CurrentFaceStatus();
467     }
468   }
469 }
470
471 //=======================================================================
472 //function : Discret
473 //purpose  :
474 //=======================================================================
475 Standard_Integer BRepMesh_IncrementalMesh::Discret(
476   const TopoDS_Shape&    theShape,
477   const Standard_Real    theDeflection,
478   const Standard_Real    theAngle,
479   BRepMesh_PDiscretRoot& theAlgo)
480 {
481   BRepMesh_IncrementalMesh* anAlgo = new BRepMesh_IncrementalMesh();
482   anAlgo->SetDeflection(theDeflection);
483   anAlgo->SetAngle     (theAngle);
484   anAlgo->SetShape     (theShape);
485   anAlgo->SetParallel  (IS_IN_PARALLEL);
486   theAlgo = anAlgo;
487   return 0; // no error
488 }
489
490 //=======================================================================
491 //function : IsParallelDefault
492 //purpose  :
493 //=======================================================================
494 Standard_Boolean BRepMesh_IncrementalMesh::IsParallelDefault()
495 {
496 #ifdef HAVE_TBB
497   return IS_IN_PARALLEL;
498 #else
499   // no alternative parallelization yet - flag has no meaning
500   return Standard_False;
501 #endif
502 }
503
504 //=======================================================================
505 //function : Discret
506 //purpose  :
507 //=======================================================================
508 void BRepMesh_IncrementalMesh::SetParallelDefault(
509   const Standard_Boolean theInParallel)
510 {
511   IS_IN_PARALLEL = theInParallel;
512 }
513
514 //! Export Mesh Plugin entry function
515 DISCRETPLUGIN(BRepMesh_IncrementalMesh)