0024968: Impove BRepMesh_Classifier to cope with intersection of huge number of wires
[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             myInParallel);
225   //
226   Update(myShape);
227 }
228
229 //=======================================================================
230 //function : GetStatus
231 //purpose  : 
232 //=======================================================================
233 Standard_Integer BRepMesh_IncrementalMesh::GetStatusFlags() const
234 {
235   return myStatus;
236 }
237
238 //=======================================================================
239 //function : collectFaces
240 //purpose  : 
241 //=======================================================================
242 void BRepMesh_IncrementalMesh::collectFaces()
243 {
244   TopTools_ListOfShape aFaceList;
245   BRepLib::ReverseSortFaces(myShape, aFaceList);
246   TopTools_MapOfShape aFaceMap;
247   myFaces.reserve(aFaceList.Extent());
248
249   // make array of faces suitable for processing (excluding faces without surface)
250   TopLoc_Location aDummyLoc;
251   const TopLoc_Location aEmptyLoc;
252   TopTools_ListIteratorOfListOfShape aFaceIter(aFaceList);
253   for (; aFaceIter.More(); aFaceIter.Next())
254   {
255     TopoDS_Shape aFaceNoLoc = aFaceIter.Value();
256     aFaceNoLoc.Location(aEmptyLoc);
257     if (!aFaceMap.Add (aFaceNoLoc))
258       continue; // already processed
259
260     TopoDS_Face aFace = TopoDS::Face(aFaceIter.Value());
261     const Handle(Geom_Surface)& aSurf = BRep_Tool::Surface(aFace, aDummyLoc);
262     if (aSurf.IsNull())
263       continue;
264
265     myFaces.push_back(aFace);
266   }
267 }
268
269 //=======================================================================
270 //function : Update(shape)
271 //purpose  : Builds the incremental mesh of the shape
272 //=======================================================================
273 void BRepMesh_IncrementalMesh::Update(const TopoDS_Shape& S)
274 {
275   myModified = Standard_False;
276   TopExp_Explorer ex;
277
278   //AGV 080407: Since version 6.2.0 there would be exception without this check
279   if (myBox.IsVoid())
280     return;
281
282   TopExp::MapShapesAndAncestors(myShape, TopAbs_EDGE, TopAbs_FACE, myancestors);
283   
284   BRepMesh_FastDiscret::BoxMaxDimension(myBox, mydtotale);
285   
286   for (ex.Init(S, TopAbs_EDGE); ex.More(); ex.Next()) {
287     if(BRep_Tool::IsGeometric(TopoDS::Edge(ex.Current()))) {
288       Update(TopoDS::Edge(ex.Current()));
289     }
290   }
291
292   // get list of faces
293   std::vector<TopoDS_Face>::iterator aFaceIt(myFaces.begin());
294   for (; aFaceIt != myFaces.end(); aFaceIt++)
295     Update(*aFaceIt);
296
297   if (myInParallel)
298   {
299   #ifdef HAVE_TBB
300     myMesh->CreateMutexesForSubShapes(S, TopAbs_EDGE);
301     // mesh faces in parallel threads using TBB
302     tbb::parallel_for_each (myFaces.begin(), myFaces.end(), *myMesh.operator->());
303   #else
304     // alternative parallelization not yet available
305     for (std::vector<TopoDS_Face>::iterator it(myFaces.begin()); it != myFaces.end(); it++)
306       myMesh->Process (*it);
307   #endif
308     myMesh->RemoveAllMutexes();
309   }
310   else
311   {
312     for (std::vector<TopoDS_Face>::iterator it(myFaces.begin()); it != myFaces.end(); it++)
313       myMesh->Process (*it);
314   }
315
316   // maillage des edges non contenues dans les faces :
317   Standard_Real f, l, defedge;
318   Standard_Integer i, nbNodes;
319   TopLoc_Location L;
320   Standard_Real cdef = 1.;
321   ex.Init(S ,TopAbs_EDGE, TopAbs_FACE);
322
323   while (ex.More()) {
324     const TopoDS_Edge& E = TopoDS::Edge(ex.Current());
325
326     if(!BRep_Tool::IsGeometric(E)) {
327       ex.Next();
328       continue;
329     }
330
331     if (myRelative) 
332       defedge = BRepMesh_FastDiscret::RelativeEdgeDeflection(E, myDeflection, 
333                                                              mydtotale, cdef);
334     else 
335       defedge = myDeflection;
336     
337     Handle(Poly_Polygon3D) P3D = BRep_Tool::Polygon3D(E, L);
338     Standard_Boolean maill = Standard_False;
339     if (P3D.IsNull()) {
340       maill = Standard_True;
341     }
342     else if (P3D->Deflection() > 1.1*defedge) {
343       maill = Standard_True;
344     }
345     if (maill) {
346       BRepAdaptor_Curve C(E);
347       f = C.FirstParameter();
348       l = C.LastParameter();
349       
350       GCPnts_TangentialDeflection TD(C, f, l, myAngle, defedge, 2);
351       nbNodes = TD.NbPoints();
352       
353       TColgp_Array1OfPnt Nodes(1, nbNodes);
354       TColStd_Array1OfReal UVNodes(1, nbNodes);
355       for ( i = 1; i <= nbNodes; i++) {
356         Nodes(i) = TD.Value(i);
357         UVNodes(i) = TD.Parameter(i);
358       }
359       
360       BRep_Builder B;
361       Handle(Poly_Polygon3D) P = new Poly_Polygon3D(Nodes, UVNodes);
362       P->Deflection(myDeflection);
363       B.UpdateEdge(E, P);
364     }
365
366     ex.Next();
367   }
368 }
369
370 //=======================================================================
371 //function : Update(edge)
372 //purpose  : Locate a correct discretisation if it exists
373 //           Set no one otherwise
374 //=======================================================================
375 void BRepMesh_IncrementalMesh::Update(const TopoDS_Edge& E)
376 {
377   TopLoc_Location l;
378   Standard_Integer i = 1;
379   Handle(Poly_Triangulation) T, TNull;
380   Handle(Poly_PolygonOnTriangulation) Poly, NullPoly;
381   Standard_Boolean found = Standard_False;
382   Standard_Real defedge = Precision::Confusion();
383   Standard_Real cdef = 1.;
384   BRep_Builder B;
385   Standard_Boolean defined = Standard_False;
386   
387   do {
388     BRep_Tool::PolygonOnTriangulation(E, Poly, T, l, i);
389     i++;
390     if (!T.IsNull() && !Poly.IsNull())
391     {
392       if (!defined)
393       {
394         if (myRelative) 
395           defedge = BRepMesh_FastDiscret::RelativeEdgeDeflection(E, myDeflection, 
396                                                                  mydtotale, cdef);
397         else
398           defedge = myDeflection;
399
400         mymapedge.Bind(E, defedge);
401         defined = Standard_True;
402       }
403       if (Poly->Deflection() <= 1.1 * defedge)
404       {
405         found = Standard_True;
406       }
407       else
408       {
409         myModified = Standard_True;
410         B.UpdateEdge(E, NullPoly, T, l);
411       }
412     }
413   } while (!Poly.IsNull());
414
415   if (!found) myMap.Add(E);
416 }
417
418
419 //=======================================================================
420 //function : Update(face)
421 //purpose  : If the face is not correctly triangulated, or if one of its
422 //           edges is to be discretisated correctly, the triangulation
423 //           of this face is built.
424 //=======================================================================
425 void  BRepMesh_IncrementalMesh::Update(const TopoDS_Face& F)
426 {
427   TopLoc_Location l;
428   Handle(Geom_Surface) SS = BRep_Tool::Surface(F, l);
429   if (SS.IsNull()) return;
430
431   //Standard_Integer i;
432   Standard_Boolean WillBeTriangulated = Standard_False;
433   Handle(Poly_Triangulation) T, TNull;
434   T = BRep_Tool::Triangulation(F, l);
435   Handle(Poly_PolygonOnTriangulation) Poly, NullPoly;
436
437   BRep_Builder B;
438   TopExp_Explorer ex;
439   
440   Standard_Real defedge, defface, cdef = 1.;
441   Standard_Integer nbEdge = 0;
442   if (myRelative) {
443     defface = 0.;
444     
445     for (ex.Init(F, TopAbs_EDGE); ex.More(); ex.Next()) {
446       const TopoDS_Edge& edge = TopoDS::Edge(ex.Current());
447       nbEdge++;
448       if (mymapedge.IsBound(edge)) {
449         defedge = mymapedge(edge);
450       }
451       else 
452         defedge = BRepMesh_FastDiscret::RelativeEdgeDeflection(edge, myDeflection, mydtotale, cdef);
453       defface = defface + defedge;
454     }
455     if (nbEdge != 0) defface = defface / nbEdge;
456     else             defface = myDeflection;
457   }
458   else
459     defface = myDeflection;
460
461   if (!T.IsNull())
462   {
463     if (T->Deflection() <= 1.1 * defface)
464     {
465       for (ex.Init(F, TopAbs_EDGE); ex.More(); ex.Next())
466       {
467         const TopoDS_Shape& anEdge = ex.Current();
468         Poly = BRep_Tool::PolygonOnTriangulation(TopoDS::Edge(anEdge), T, l);
469
470         if (Poly.IsNull() || myMap.Contains(anEdge))
471         {
472           // Triangulation is built but edge hasn't representation on it.
473           WillBeTriangulated = Standard_True;
474           break;
475         }
476       }
477     }
478     else
479     {
480       WillBeTriangulated = Standard_True;
481     }
482   }
483
484   if (WillBeTriangulated || T.IsNull()) {
485     myModified = Standard_True;
486     if (!T.IsNull()) {
487       for (ex.Init(F, TopAbs_EDGE); ex.More(); ex.Next()) {
488         B.UpdateEdge(TopoDS::Edge(ex.Current()), NullPoly, T, l);
489         myMap.Remove(ex.Current());
490       }
491       B.UpdateFace(F, TNull);
492     }
493     myMesh->Add(F, myancestors);
494     myStatus |= (Standard_Integer)(myMesh->CurrentFaceStatus());
495     if (myMesh->CurrentFaceStatus() == BRepMesh_ReMesh) {
496 #ifdef DEB_MESH
497       cout << " face remaillee + finement que prevu."<< endl;
498 #endif
499
500       Standard_Integer index;
501       
502       TopTools_MapOfShape MShape;
503       MShape.Add(F);
504
505       TopoDS_Iterator ex(F),ex2;
506       for (; ex.More(); ex.Next()) {
507         const TopoDS_Shape& aWire = ex.Value();
508         if (aWire.ShapeType() != TopAbs_WIRE)
509           continue;
510         TopoDS_Iterator exW(aWire);
511         for(; exW.More(); exW.Next()) {
512           const TopoDS_Edge& edge = TopoDS::Edge(exW.Value());
513           index = myancestors.FindIndex(edge);
514           if (index != 0) {
515             const TopTools_ListOfShape& L = myancestors.FindFromKey(edge);
516
517             TopTools_ListIteratorOfListOfShape it(L);
518
519             for (; it.More(); it.Next()) {
520               TopoDS_Face F2 = TopoDS::Face(it.Value());
521               if (!MShape.Contains(F2)) {
522                 MShape.Add(F2);
523                 T = BRep_Tool::Triangulation(F2, l);
524                 if (!T.IsNull()) {
525 #ifdef DEB_MESH
526                   cout <<"triangulation a refaire" <<endl;
527 #endif
528                   for (ex2.Initialize(F2); ex2.More(); ex2.Next()) {
529                     const TopoDS_Shape& aWire2 = ex2.Value();
530                     if (aWire2.ShapeType() != TopAbs_WIRE)
531                       continue;
532                     TopoDS_Iterator exW2(aWire2);
533                     for(; exW2.More(); exW2.Next()) {
534                       TopoDS_Edge E2 = TopoDS::Edge(exW2.Value());
535                       B.UpdateEdge(E2, NullPoly, T, l);
536                     }
537                   }
538                   B.UpdateFace(F2, TNull);
539                   myMesh->Add(F2, myancestors);
540                 }
541               }
542             }
543           }
544         }
545       }
546     }
547   }
548 }
549
550
551 //=======================================================================
552 //function : Discret
553 //purpose  :
554 //=======================================================================
555 Standard_Integer BRepMesh_IncrementalMesh::Discret (const TopoDS_Shape&    theShape,
556                                                     const Standard_Real    theDeflection,
557                                                     const Standard_Real    theAngle,
558                                                     BRepMesh_PDiscretRoot& theAlgo)
559 {
560   BRepMesh_IncrementalMesh* anAlgo = new BRepMesh_IncrementalMesh();
561   anAlgo->SetDeflection (theDeflection);
562   anAlgo->SetAngle (theAngle);
563   anAlgo->SetShape (theShape);
564   anAlgo->SetParallel (IS_IN_PARALLEL);
565   theAlgo = anAlgo;
566   return 0; // no error
567 }
568
569 //=======================================================================
570 //function : IsParallelDefault
571 //purpose  :
572 //=======================================================================
573 Standard_Boolean BRepMesh_IncrementalMesh::IsParallelDefault()
574 {
575 #ifdef HAVE_TBB
576   return IS_IN_PARALLEL;
577 #else
578   // no alternative parallelization yet - flag has no meaning
579   return Standard_False;
580 #endif
581 }
582
583 //=======================================================================
584 //function : Discret
585 //purpose  :
586 //=======================================================================
587 void BRepMesh_IncrementalMesh::SetParallelDefault (const Standard_Boolean theInParallel)
588 {
589   IS_IN_PARALLEL = theInParallel;
590 }
591
592 //! Export Mesh Plugin entry function
593 DISCRETPLUGIN(BRepMesh_IncrementalMesh)