0023631: Infinite memory consumption in BRepMesh
[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 <BRepMesh.hxx>
20 #include <BRepMesh_Edge.hxx>
21 #include <BRepMesh_Triangle.hxx>
22 #include <BRepMesh_FastDiscret.hxx>
23 #include <BRepMesh_FastDiscretFace.hxx>
24 #include <BRepMesh_PluginMacro.hxx>
25
26 #include <Bnd_Box.hxx>
27 #include <BRep_Builder.hxx>
28 #include <BRep_Tool.hxx>
29 #include <BRepTools.hxx>
30 #include <BRepLib.hxx>
31 #include <BRepBndLib.hxx>
32 #include <BRepAdaptor_Curve.hxx>
33 #include <GCPnts_TangentialDeflection.hxx>
34 #include <Precision.hxx>
35 #include <TopExp.hxx>
36 #include <TopExp_Explorer.hxx>
37 #include <TopAbs.hxx>
38 #include <TopTools_ListIteratorOfListOfShape.hxx>
39 #include <TopTools_MutexForShapeProvider.hxx>
40 #include <TColgp_Array1OfPnt.hxx>
41 #include <TColStd_Array1OfReal.hxx>
42 #include <TopoDS_Shape.hxx>
43 #include <TopoDS_Face.hxx>
44 #include <TopoDS_Edge.hxx>
45 #include <TopoDS.hxx>
46 #include <TopTools_HArray1OfShape.hxx>
47 #include <Poly_Triangulation.hxx>
48 #include <Poly_Polygon3D.hxx>
49 #include <Poly_PolygonOnTriangulation.hxx>
50 #include <Standard_Mutex.hxx>
51 #include <BRepMesh_FaceChecker.hxx>
52
53 #ifdef HAVE_TBB
54   // paralleling using Intel TBB
55   #include <tbb/parallel_for_each.h>
56 #endif
57
58 namespace
59 {
60   //! Default flag to control parallelization for BRepMesh_IncrementalMesh
61   //! tool returned for Mesh Factory
62   static Standard_Boolean IS_IN_PARALLEL = Standard_False;
63 };
64
65 IMPLEMENT_STANDARD_HANDLE (BRepMesh_IncrementalMesh, BRepMesh_DiscretRoot)
66 IMPLEMENT_STANDARD_RTTIEXT(BRepMesh_IncrementalMesh, BRepMesh_DiscretRoot)
67
68 //=======================================================================
69 //function : isCorrectPolyData
70 //purpose  : 
71 //=======================================================================
72 Standard_Boolean BRepMesh_IncrementalMesh::isCorrectPolyData()
73 {
74   collectFaces();
75
76   BRepMesh_FaceChecker aFaceChecker(myInParallel);
77   if (myInParallel)
78   {
79   #ifdef HAVE_TBB
80     // check faces in parallel threads using TBB
81     tbb::parallel_for_each(myFaces.begin(), myFaces.end(), aFaceChecker);
82   #else
83     // alternative parallelization not yet available
84     for (std::vector<TopoDS_Face>::iterator it(myFaces.begin()); it != myFaces.end(); it++)
85       aFaceChecker(*it);
86   #endif
87   }
88   else
89   {
90     for (std::vector<TopoDS_Face>::iterator it(myFaces.begin()); it != myFaces.end(); it++)
91       aFaceChecker(*it);
92   }
93
94   return aFaceChecker.IsValid();
95 }
96
97 //=======================================================================
98 //function : BRepMesh_IncrementalMesh
99 //purpose  : 
100 //=======================================================================
101 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh() 
102 : myRelative (Standard_False),
103   myInParallel (Standard_False)
104 {
105   Init();
106 }
107
108 //=======================================================================
109 //function : BRepMesh_IncrementalMesh
110 //purpose  : 
111 //=======================================================================
112 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh (const TopoDS_Shape& theShape,
113                                                     const Standard_Real theDeflection,
114                                                     const Standard_Boolean theRelative,
115                                                     const Standard_Real theAngle,
116                                                     const Standard_Boolean theInParallel)
117 : myRelative (theRelative),
118   myInParallel (theInParallel)
119 {
120   Init();
121   myDeflection = theDeflection;
122   myAngle = theAngle;
123   myShape = theShape;
124
125   //
126   Perform();
127 }
128
129 //=======================================================================
130 //function : ~
131 //purpose  : 
132 //=======================================================================
133 BRepMesh_IncrementalMesh::~BRepMesh_IncrementalMesh() 
134 {
135 }
136
137 //=======================================================================
138 //function : SetParallel
139 //purpose  :
140 //=======================================================================
141 void BRepMesh_IncrementalMesh::SetParallel (const Standard_Boolean theInParallel)
142 {
143   myInParallel = theInParallel;
144 }
145
146 //=======================================================================
147 //function : IsParallel
148 //purpose  :
149 //=======================================================================
150 Standard_Boolean BRepMesh_IncrementalMesh::IsParallel() const
151 {
152   return myInParallel;
153 }
154
155 //=======================================================================
156 //function : Init
157 //purpose  : 
158 //=======================================================================
159 void BRepMesh_IncrementalMesh::Init() 
160 {
161   myStatus = 0;
162   myModified = Standard_False;
163   mymapedge.Clear();
164   myancestors.Clear();
165   myFaces.clear();
166 }
167
168 //=======================================================================
169 //function : SetRelative
170 //purpose  : 
171 //=======================================================================
172 void BRepMesh_IncrementalMesh::SetRelative(const Standard_Boolean theFlag)
173 {
174   myRelative = theFlag;
175 }
176
177 //=======================================================================
178 //function : Relative
179 //purpose  : 
180 //=======================================================================
181 Standard_Boolean BRepMesh_IncrementalMesh::Relative()const
182 {
183   return myRelative;
184 }
185
186 //=======================================================================
187 //function : IsModified
188 //purpose  : 
189 //=======================================================================
190 Standard_Boolean BRepMesh_IncrementalMesh::IsModified() const
191 {
192   return myModified;
193 }
194
195 //=======================================================================
196 //function : Perform
197 //purpose  : 
198 //=======================================================================
199 void BRepMesh_IncrementalMesh::Perform()
200 {
201   Init(); 
202
203   if (!isCorrectPolyData())
204     BRepTools::Clean(myShape);
205
206   Bnd_Box aBox;
207   //
208   SetDone();
209   //
210   BRepBndLib::Add(myShape, aBox);
211   myBox = aBox;
212   //
213   if (!myMesh.IsNull()) {
214     myMesh.Nullify();
215   }
216   //
217   myMesh = new BRepMesh_FastDiscret(myDeflection,
218                                     myAngle,
219                                     aBox,
220                                     Standard_True,
221                                     Standard_True,
222                                     myRelative,
223                                     Standard_True);
224   //
225   Update(myShape);
226 }
227
228 //=======================================================================
229 //function : GetStatus
230 //purpose  : 
231 //=======================================================================
232 Standard_Integer BRepMesh_IncrementalMesh::GetStatusFlags() const
233 {
234   return myStatus;
235 }
236
237 //=======================================================================
238 //function : collectFaces
239 //purpose  : 
240 //=======================================================================
241 void BRepMesh_IncrementalMesh::collectFaces()
242 {
243   TopTools_ListOfShape aFaceList;
244   BRepLib::ReverseSortFaces(myShape, aFaceList);
245   TopTools_MapOfShape aFaceMap;
246   myFaces.reserve(aFaceList.Extent());
247
248   // make array of faces suitable for processing (excluding faces without surface)
249   TopLoc_Location aDummyLoc;
250   const TopLoc_Location aEmptyLoc;
251   TopTools_ListIteratorOfListOfShape aFaceIter(aFaceList);
252   for (; aFaceIter.More(); aFaceIter.Next())
253   {
254     TopoDS_Shape aFaceNoLoc = aFaceIter.Value();
255     aFaceNoLoc.Location(aEmptyLoc);
256     if (!aFaceMap.Add (aFaceNoLoc))
257       continue; // already processed
258
259     TopoDS_Face aFace = TopoDS::Face(aFaceIter.Value());
260     const Handle(Geom_Surface)& aSurf = BRep_Tool::Surface(aFace, aDummyLoc);
261     if (aSurf.IsNull())
262       continue;
263
264     myFaces.push_back(aFace);
265   }
266 }
267
268 //=======================================================================
269 //function : Update(shape)
270 //purpose  : Builds the incremental mesh of the shape
271 //=======================================================================
272 void BRepMesh_IncrementalMesh::Update(const TopoDS_Shape& S)
273 {
274   myModified = Standard_False;
275   TopExp_Explorer ex;
276
277   //AGV 080407: Since version 6.2.0 there would be exception without this check
278   if (myBox.IsVoid())
279     return;
280
281   TopExp::MapShapesAndAncestors(myShape, TopAbs_EDGE, TopAbs_FACE, myancestors);
282   
283   BRepMesh_FastDiscret::BoxMaxDimension(myBox, mydtotale);
284   
285   for (ex.Init(S, TopAbs_EDGE); ex.More(); ex.Next()) {
286     if(BRep_Tool::IsGeometric(TopoDS::Edge(ex.Current()))) {
287       Update(TopoDS::Edge(ex.Current()));
288     }
289   }
290
291   // get list of faces
292   std::vector<TopoDS_Face>::iterator aFaceIt(myFaces.begin());
293   for (; aFaceIt != myFaces.end(); aFaceIt++)
294     Update(*aFaceIt);
295
296   if (myInParallel)
297   {
298   #ifdef HAVE_TBB
299     myMesh->CreateMutexesForSubShapes(S, TopAbs_EDGE);
300     // mesh faces in parallel threads using TBB
301     tbb::parallel_for_each (myFaces.begin(), myFaces.end(), *myMesh.operator->());
302   #else
303     // alternative parallelization not yet available
304     for (std::vector<TopoDS_Face>::iterator it(myFaces.begin()); it != myFaces.end(); it++)
305       myMesh->Process (*it);
306   #endif
307     myMesh->RemoveAllMutexes();
308   }
309   else
310   {
311     for (std::vector<TopoDS_Face>::iterator it(myFaces.begin()); it != myFaces.end(); it++)
312       myMesh->Process (*it);
313   }
314
315   // maillage des edges non contenues dans les faces :
316   Standard_Real f, l, defedge;
317   Standard_Integer i, nbNodes;
318   TopLoc_Location L;
319   Standard_Real cdef = 1.;
320   ex.Init(S ,TopAbs_EDGE, TopAbs_FACE);
321
322   while (ex.More()) {
323     const TopoDS_Edge& E = TopoDS::Edge(ex.Current());
324
325     if(!BRep_Tool::IsGeometric(E)) {
326       ex.Next();
327       continue;
328     }
329
330     if (myRelative) 
331       defedge = BRepMesh_FastDiscret::RelativeEdgeDeflection(E, myDeflection, 
332                                                              mydtotale, cdef);
333     else 
334       defedge = myDeflection;
335     
336     Handle(Poly_Polygon3D) P3D = BRep_Tool::Polygon3D(E, L);
337     Standard_Boolean maill = Standard_False;
338     if (P3D.IsNull()) {
339       maill = Standard_True;
340     }
341     else if (P3D->Deflection() > 1.1*defedge) {
342       maill = Standard_True;
343     }
344     if (maill) {
345       BRepAdaptor_Curve C(E);
346       f = C.FirstParameter();
347       l = C.LastParameter();
348       
349       GCPnts_TangentialDeflection TD(C, f, l, myAngle, defedge, 2);
350       nbNodes = TD.NbPoints();
351       
352       TColgp_Array1OfPnt Nodes(1, nbNodes);
353       TColStd_Array1OfReal UVNodes(1, nbNodes);
354       for ( i = 1; i <= nbNodes; i++) {
355         Nodes(i) = TD.Value(i);
356         UVNodes(i) = TD.Parameter(i);
357       }
358       
359       BRep_Builder B;
360       Handle(Poly_Polygon3D) P = new Poly_Polygon3D(Nodes, UVNodes);
361       P->Deflection(myDeflection);
362       B.UpdateEdge(E, P);
363     }
364
365     ex.Next();
366   }
367 }
368
369 //=======================================================================
370 //function : Update(edge)
371 //purpose  : Locate a correct discretisation if it exists
372 //           Set no one otherwise
373 //=======================================================================
374 void BRepMesh_IncrementalMesh::Update(const TopoDS_Edge& E)
375 {
376   TopLoc_Location l;
377   Standard_Integer i = 1;
378   Handle(Poly_Triangulation) T, TNull;
379   Handle(Poly_PolygonOnTriangulation) Poly, NullPoly;
380   Standard_Boolean found = Standard_False;
381   Standard_Real defedge = Precision::Confusion();
382   Standard_Real cdef = 1.;
383   BRep_Builder B;
384   Standard_Boolean defined = Standard_False;
385   
386   do {
387     BRep_Tool::PolygonOnTriangulation(E, Poly, T, l, i);
388     i++;
389     if (!T.IsNull() && !Poly.IsNull())
390     {
391       if (!defined)
392       {
393         if (myRelative) 
394           defedge = BRepMesh_FastDiscret::RelativeEdgeDeflection(E, myDeflection, 
395                                                                  mydtotale, cdef);
396         else
397           defedge = myDeflection;
398
399         mymapedge.Bind(E, defedge);
400         defined = Standard_True;
401       }
402       if (Poly->Deflection() <= 1.1 * defedge)
403       {
404         found = Standard_True;
405       }
406       else
407       {
408         myModified = Standard_True;
409         B.UpdateEdge(E, NullPoly, T, l);
410       }
411     }
412   } while (!Poly.IsNull());
413
414   if (!found) myMap.Add(E);
415 }
416
417
418 //=======================================================================
419 //function : Update(face)
420 //purpose  : If the face is not correctly triangulated, or if one of its
421 //           edges is to be discretisated correctly, the triangulation
422 //           of this face is built.
423 //=======================================================================
424 void  BRepMesh_IncrementalMesh::Update(const TopoDS_Face& F)
425 {
426   TopLoc_Location l;
427   Handle(Geom_Surface) SS = BRep_Tool::Surface(F, l);
428   if (SS.IsNull()) return;
429
430   //Standard_Integer i;
431   Standard_Boolean WillBeTriangulated = Standard_False;
432   Handle(Poly_Triangulation) T, TNull;
433   T = BRep_Tool::Triangulation(F, l);
434   Handle(Poly_PolygonOnTriangulation) Poly, NullPoly;
435
436   BRep_Builder B;
437   TopExp_Explorer ex;
438   
439   Standard_Real defedge, defface, cdef = 1.;
440   Standard_Integer nbEdge = 0;
441   if (myRelative) {
442     defface = 0.;
443     
444     for (ex.Init(F, TopAbs_EDGE); ex.More(); ex.Next()) {
445       const TopoDS_Edge& edge = TopoDS::Edge(ex.Current());
446       nbEdge++;
447       if (mymapedge.IsBound(edge)) {
448         defedge = mymapedge(edge);
449       }
450       else 
451         defedge = BRepMesh_FastDiscret::RelativeEdgeDeflection(edge, myDeflection, mydtotale, cdef);
452       defface = defface + defedge;
453     }
454     if (nbEdge != 0) defface = defface / nbEdge;
455     else             defface = myDeflection;
456   }
457   else
458     defface = myDeflection;
459
460   if (!T.IsNull())
461   {
462     if (T->Deflection() <= 1.1 * defface)
463     {
464       for (ex.Init(F, TopAbs_EDGE); ex.More(); ex.Next())
465       {
466         const TopoDS_Shape& anEdge = ex.Current();
467         Poly = BRep_Tool::PolygonOnTriangulation(TopoDS::Edge(anEdge), T, l);
468
469         if (Poly.IsNull() || myMap.Contains(anEdge))
470         {
471           // Triangulation is built but edge hasn't representation on it.
472           WillBeTriangulated = Standard_True;
473           break;
474         }
475       }
476     }
477     else
478     {
479       WillBeTriangulated = Standard_True;
480     }
481   }
482
483   if (WillBeTriangulated || T.IsNull()) {
484     myModified = Standard_True;
485     if (!T.IsNull()) {
486       for (ex.Init(F, TopAbs_EDGE); ex.More(); ex.Next()) {
487         B.UpdateEdge(TopoDS::Edge(ex.Current()), NullPoly, T, l);
488         myMap.Remove(ex.Current());
489       }
490       B.UpdateFace(F, TNull);
491     }
492     myMesh->Add(F, myancestors);
493     myStatus |= (Standard_Integer)(myMesh->CurrentFaceStatus());
494     if (myMesh->CurrentFaceStatus() == BRepMesh_ReMesh) {
495 #ifdef DEB_MESH
496       cout << " face remaillee + finement que prevu."<< endl;
497 #endif
498
499       Standard_Integer index;
500       
501       TopTools_MapOfShape MShape;
502       MShape.Add(F);
503
504       TopoDS_Iterator ex(F),ex2;
505       for (; ex.More(); ex.Next()) {
506         const TopoDS_Shape& aWire = ex.Value();
507         if (aWire.ShapeType() != TopAbs_WIRE)
508           continue;
509         TopoDS_Iterator exW(aWire);
510         for(; exW.More(); exW.Next()) {
511           const TopoDS_Edge& edge = TopoDS::Edge(exW.Value());
512           index = myancestors.FindIndex(edge);
513           if (index != 0) {
514             const TopTools_ListOfShape& L = myancestors.FindFromKey(edge);
515
516             TopTools_ListIteratorOfListOfShape it(L);
517
518             for (; it.More(); it.Next()) {
519               TopoDS_Face F2 = TopoDS::Face(it.Value());
520               if (!MShape.Contains(F2)) {
521                 MShape.Add(F2);
522                 T = BRep_Tool::Triangulation(F2, l);      
523                 if (!T.IsNull()) {
524 #ifdef DEB_MESH
525                   cout <<"triangulation a refaire" <<endl;
526 #endif
527                   for (ex2.Initialize(F2); ex2.More(); ex2.Next()) {
528                     const TopoDS_Shape& aWire2 = ex2.Value();
529                     if (aWire2.ShapeType() != TopAbs_WIRE)
530                       continue;
531                     TopoDS_Iterator exW2(aWire2);
532                     for(; exW2.More(); exW2.Next()) {
533                       TopoDS_Edge E2 = TopoDS::Edge(exW2.Value());
534                       B.UpdateEdge(E2, NullPoly, T, l);
535                     }
536                   }
537                   B.UpdateFace(F2, TNull);
538                   myMesh->Add(F2, myancestors);
539                 }
540               }
541             }
542           }
543         }
544       }
545     }
546   }
547 }
548
549
550 //=======================================================================
551 //function : Discret
552 //purpose  :
553 //=======================================================================
554 Standard_Integer BRepMesh_IncrementalMesh::Discret (const TopoDS_Shape&    theShape,
555                                                     const Standard_Real    theDeflection,
556                                                     const Standard_Real    theAngle,
557                                                     BRepMesh_PDiscretRoot& theAlgo)
558 {
559   BRepMesh_IncrementalMesh* anAlgo = new BRepMesh_IncrementalMesh();
560   anAlgo->SetDeflection (theDeflection);
561   anAlgo->SetAngle (theAngle);
562   anAlgo->SetShape (theShape);
563   anAlgo->SetParallel (IS_IN_PARALLEL);
564   theAlgo = anAlgo;
565   return 0; // no error
566 }
567
568 //=======================================================================
569 //function : IsParallelDefault
570 //purpose  :
571 //=======================================================================
572 Standard_Boolean BRepMesh_IncrementalMesh::IsParallelDefault()
573 {
574 #ifdef HAVE_TBB
575   return IS_IN_PARALLEL;
576 #else
577   // no alternative parallelization yet - flag has no meaning
578   return Standard_False;
579 #endif
580 }
581
582 //=======================================================================
583 //function : Discret
584 //purpose  :
585 //=======================================================================
586 void BRepMesh_IncrementalMesh::SetParallelDefault (const Standard_Boolean theInParallel)
587 {
588   IS_IN_PARALLEL = theInParallel;
589 }
590
591 //! Export Mesh Plugin entry function
592 DISCRETPLUGIN(BRepMesh_IncrementalMesh)