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
6 // This file is part of Open CASCADE Technology software library.
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.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
17 #include <BRepMesh_IncrementalMesh.hxx>
19 #include <Precision.hxx>
20 #include <Standard_ErrorHandler.hxx>
22 #include <BRepMesh_ShapeTool.hxx>
23 #include <BRepMesh_Edge.hxx>
24 #include <BRepMesh_PluginMacro.hxx>
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>
34 #include <Poly_Triangulation.hxx>
35 #include <Poly_Polygon3D.hxx>
36 #include <Poly_PolygonOnTriangulation.hxx>
39 #include <TopoDS_Edge.hxx>
40 #include <TopoDS_Face.hxx>
41 #include <TopoDS_Shape.hxx>
44 #include <TopExp_Explorer.hxx>
46 #include <TopTools_ListIteratorOfListOfShape.hxx>
47 #include <TColgp_Array1OfPnt.hxx>
48 #include <TColgp_Array1OfPnt2d.hxx>
49 #include <TColStd_Array1OfReal.hxx>
50 #include <TopTools_HArray1OfShape.hxx>
51 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
53 #include <GCPnts_TangentialDeflection.hxx>
56 // paralleling using Intel TBB
57 #include <tbb/parallel_for_each.h>
62 //! Default flag to control parallelization for BRepMesh_IncrementalMesh
63 //! tool returned for Mesh Factory
64 static Standard_Boolean IS_IN_PARALLEL = Standard_False;
67 IMPLEMENT_STANDARD_HANDLE (BRepMesh_IncrementalMesh, BRepMesh_DiscretRoot)
68 IMPLEMENT_STANDARD_RTTIEXT(BRepMesh_IncrementalMesh, BRepMesh_DiscretRoot)
70 //=======================================================================
71 //function : Default constructor
73 //=======================================================================
74 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh()
75 : myRelative (Standard_False),
76 myInParallel(Standard_False),
77 myMinSize (Precision::Confusion()),
78 myInternalVerticesMode(Standard_True),
79 myIsControlSurfaceDeflection(Standard_True)
83 //=======================================================================
84 //function : Constructor
86 //=======================================================================
87 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh(
88 const TopoDS_Shape& theShape,
89 const Standard_Real theLinDeflection,
90 const Standard_Boolean isRelative,
91 const Standard_Real theAngDeflection,
92 const Standard_Boolean isInParallel)
93 : myRelative (isRelative),
94 myInParallel(isInParallel),
95 myMinSize (Precision::Confusion()),
96 myInternalVerticesMode(Standard_True),
97 myIsControlSurfaceDeflection(Standard_True)
99 myDeflection = theLinDeflection;
100 myAngle = theAngDeflection;
106 //=======================================================================
107 //function : Destructor
109 //=======================================================================
110 BRepMesh_IncrementalMesh::~BRepMesh_IncrementalMesh()
114 //=======================================================================
117 //=======================================================================
118 void BRepMesh_IncrementalMesh::clear()
121 myEdgeDeflection.Clear();
126 //=======================================================================
129 //=======================================================================
130 void BRepMesh_IncrementalMesh::init()
133 myModified = Standard_False;
141 BRepBndLib::Add(myShape, aBox, Standard_False);
149 BRepMesh_ShapeTool::BoxMaxDimension(aBox, myMaxShapeSize);
151 myMesh = new BRepMesh_FastDiscret(myDeflection,
152 myAngle, aBox, Standard_True, Standard_True,
153 myRelative, Standard_True, myInParallel, myMinSize,
154 myInternalVerticesMode, myIsControlSurfaceDeflection);
156 myMesh->InitSharedFaces(myShape);
159 //=======================================================================
160 //function : collectFaces
162 //=======================================================================
163 void BRepMesh_IncrementalMesh::collectFaces()
165 TopTools_ListOfShape aFaceList;
166 BRepLib::ReverseSortFaces(myShape, aFaceList);
167 TopTools_MapOfShape aFaceMap;
169 // make array of faces suitable for processing (excluding faces without surface)
170 TopLoc_Location aDummyLoc;
171 const TopLoc_Location aEmptyLoc;
172 TopTools_ListIteratorOfListOfShape aFaceIter(aFaceList);
173 for (; aFaceIter.More(); aFaceIter.Next())
175 TopoDS_Shape aFaceNoLoc = aFaceIter.Value();
176 aFaceNoLoc.Location(aEmptyLoc);
177 if (!aFaceMap.Add (aFaceNoLoc))
178 continue; // already processed
180 TopoDS_Face aFace = TopoDS::Face(aFaceIter.Value());
181 const Handle(Geom_Surface)& aSurf = BRep_Tool::Surface(aFace, aDummyLoc);
185 myFaces.Append(aFace);
189 //=======================================================================
192 //=======================================================================
193 void BRepMesh_IncrementalMesh::Perform()
203 //=======================================================================
204 //function : update()
206 //=======================================================================
207 void BRepMesh_IncrementalMesh::update()
210 TopExp_Explorer aExplorer(myShape, TopAbs_EDGE);
211 for (; aExplorer.More(); aExplorer.Next())
213 const TopoDS_Edge& aEdge = TopoDS::Edge(aExplorer.Current());
214 if(!BRep_Tool::IsGeometric(aEdge))
221 NCollection_Vector<TopoDS_Face>::Iterator aFaceIt(myFaces);
222 for (; aFaceIt.More(); aFaceIt.Next())
223 update(aFaceIt.Value());
229 tbb::parallel_for_each(myFaces.begin(), myFaces.end(), *myMesh);
234 for (aFaceIt.Init(myFaces); aFaceIt.More(); aFaceIt.Next())
235 myMesh->Process(aFaceIt.Value());
244 //=======================================================================
245 //function : discretizeFreeEdges
247 //=======================================================================
248 void BRepMesh_IncrementalMesh::discretizeFreeEdges()
250 TopExp_Explorer aExplorer(myShape ,TopAbs_EDGE, TopAbs_FACE);
251 for (; aExplorer.More(); aExplorer.Next())
253 const TopoDS_Edge& aEdge = TopoDS::Edge(aExplorer.Current());
254 if(!BRep_Tool::IsGeometric(aEdge))
257 TopLoc_Location aLoc;
258 Standard_Real aEdgeDeflection = edgeDeflection(aEdge);
259 Handle(Poly_Polygon3D) aPoly3D = BRep_Tool::Polygon3D(aEdge, aLoc);
260 if (!aPoly3D.IsNull() && aPoly3D->Deflection() < 1.1 * aEdgeDeflection)
263 BRepAdaptor_Curve aCurve(aEdge);
264 GCPnts_TangentialDeflection aDiscret(aCurve, aCurve.FirstParameter(),
265 aCurve.LastParameter(), myAngle, aEdgeDeflection, 2, myMinSize);
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)
272 aNodes (i) = aDiscret.Value(i);
273 aUVNodes(i) = aDiscret.Parameter(i);
276 aPoly3D = new Poly_Polygon3D(aNodes, aUVNodes);
277 aPoly3D->Deflection(myDeflection);
279 BRep_Builder aBuilder;
280 aBuilder.UpdateEdge(aEdge, aPoly3D);
284 //=======================================================================
285 //function : edgeDeflection
287 //=======================================================================
288 Standard_Real BRepMesh_IncrementalMesh::edgeDeflection(
289 const TopoDS_Edge& theEdge)
291 if (myEdgeDeflection.IsBound(theEdge))
292 return myEdgeDeflection(theEdge);
294 Standard_Real aEdgeDeflection;
297 Standard_Real aScale;
298 aEdgeDeflection = BRepMesh_ShapeTool::RelativeEdgeDeflection(theEdge,
299 myDeflection, myMaxShapeSize, aScale);
302 aEdgeDeflection = myDeflection;
304 myEdgeDeflection.Bind(theEdge, aEdgeDeflection);
305 return aEdgeDeflection;
308 //=======================================================================
309 //function : faceDeflection
311 //=======================================================================
312 Standard_Real BRepMesh_IncrementalMesh::faceDeflection(
313 const TopoDS_Face& theFace)
318 Standard_Integer aEdgesNb = 0;
319 Standard_Real aFaceDeflection = 0.;
321 TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
322 for (; aEdgeIt.More(); aEdgeIt.Next(), ++aEdgesNb)
324 const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
325 aFaceDeflection += edgeDeflection(aEdge);
328 return (aEdgesNb == 0) ? myDeflection : (aFaceDeflection / aEdgesNb);
331 //=======================================================================
332 //function : update(edge)
334 //=======================================================================
335 void BRepMesh_IncrementalMesh::update(const TopoDS_Edge& theEdge)
337 if (!myEdges.IsBound(theEdge))
338 myEdges.Bind(theEdge, BRepMesh::DMapOfTriangulationBool());
340 Standard_Real aEdgeDeflection = edgeDeflection(theEdge);
341 // Check that triangulation relies to face of the given shape.
342 const TopTools_IndexedDataMapOfShapeListOfShape& aMapOfSharedFaces =
343 myMesh->SharedFaces();
345 const TopTools_ListOfShape& aSharedFaces =
346 aMapOfSharedFaces.FindFromKey(theEdge);
348 TopTools_ListIteratorOfListOfShape aSharedFaceIt(aSharedFaces);
349 for (; aSharedFaceIt.More(); aSharedFaceIt.Next())
351 TopLoc_Location aLoc;
352 const TopoDS_Face& aFace = TopoDS::Face(aSharedFaceIt.Value());
353 const Handle(Poly_Triangulation)& aFaceTriangulation =
354 BRep_Tool::Triangulation(aFace, aLoc);
356 if (aFaceTriangulation.IsNull())
359 Standard_Boolean isConsistent = Standard_False;
360 const Handle(Poly_PolygonOnTriangulation)& aPolygon =
361 BRep_Tool::PolygonOnTriangulation(theEdge, aFaceTriangulation, aLoc);
363 if (!aPolygon.IsNull())
365 isConsistent = aPolygon->Deflection() < 1.1 * aEdgeDeflection &&
366 aPolygon->HasParameters();
370 myModified = Standard_True;
371 BRepMesh_ShapeTool::NullifyEdge(theEdge, aFaceTriangulation, aLoc);
375 myEdges(theEdge).Bind(aFaceTriangulation, isConsistent);
379 //=======================================================================
380 //function : isToBeMeshed
382 //=======================================================================
383 Standard_Boolean BRepMesh_IncrementalMesh::toBeMeshed(
384 const TopoDS_Face& theFace,
385 const Standard_Boolean isWithCheck)
387 TopLoc_Location aLoc;
388 const Handle(Poly_Triangulation)& aTriangulation =
389 BRep_Tool::Triangulation(theFace, aLoc);
391 if (aTriangulation.IsNull())
392 return Standard_True;
396 Standard_Real aFaceDeflection = faceDeflection(theFace);
397 if (aTriangulation->Deflection() < 1.1 * aFaceDeflection)
399 Standard_Boolean isEdgesConsistent = Standard_True;
400 TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
401 for (; aEdgeIt.More() && isEdgesConsistent; aEdgeIt.Next())
403 const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
404 if (!myEdges.IsBound(aEdge))
407 BRepMesh::DMapOfTriangulationBool& aTriMap = myEdges(aEdge);
408 isEdgesConsistent &= aTriMap.IsBound(aTriangulation) &&
409 aTriMap(aTriangulation);
412 if (isEdgesConsistent)
414 // #25080: check that indices of links forming triangles are in range.
415 Standard_Boolean isTriangulationConsistent = Standard_True;
416 const Standard_Integer aNodesNb = aTriangulation->NbNodes();
417 const Poly_Array1OfTriangle& aTriangles = aTriangulation->Triangles();
418 Standard_Integer i = aTriangles.Lower();
419 for (; i <= aTriangles.Upper() && isTriangulationConsistent; ++i)
421 const Poly_Triangle& aTriangle = aTriangles(i);
422 Standard_Integer n[3];
423 aTriangle.Get(n[0], n[1], n[2]);
424 for (Standard_Integer j = 0; j < 3 && isTriangulationConsistent; ++j)
425 isTriangulationConsistent = (n[j] >= 1 && n[j] <= aNodesNb);
428 if (isTriangulationConsistent)
429 return Standard_False;
435 TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
436 for (; aEdgeIt.More(); aEdgeIt.Next())
438 const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
439 BRepMesh_ShapeTool::NullifyEdge(aEdge, aTriangulation, aLoc);
442 BRepMesh_ShapeTool::NullifyFace(theFace);
443 return Standard_True;
446 //=======================================================================
447 //function : update(face)
449 //=======================================================================
450 void BRepMesh_IncrementalMesh::update(const TopoDS_Face& theFace)
452 if (!toBeMeshed(theFace, Standard_True))
455 myModified = Standard_True;
456 Standard_Integer aStatus = myMesh->Add(theFace);
459 if (aStatus != BRepMesh_ReMesh)
462 BRepMesh::MapOfShape aUsedFaces;
463 aUsedFaces.Add(theFace);
465 const TopTools_IndexedDataMapOfShapeListOfShape& aMapOfSharedFaces =
466 myMesh->SharedFaces();
468 TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
469 for (; aEdgeIt.More(); aEdgeIt.Next())
471 const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
472 if (aMapOfSharedFaces.FindIndex(aEdge) == 0)
475 const TopTools_ListOfShape& aSharedFaces = aMapOfSharedFaces.FindFromKey(aEdge);
476 TopTools_ListIteratorOfListOfShape aSharedFaceIt(aSharedFaces);
477 for (; aSharedFaceIt.More(); aSharedFaceIt.Next())
479 const TopoDS_Face& aFace = TopoDS::Face(aSharedFaceIt.Value());
480 if (aUsedFaces.Contains(aFace))
483 aUsedFaces.Add(aFace);
484 toBeMeshed(aFace, Standard_False);
486 myStatus |= myMesh->Add(aFace);
491 //=======================================================================
494 //=======================================================================
495 void BRepMesh_IncrementalMesh::commit()
497 NCollection_Vector<TopoDS_Face>::Iterator aFaceIt(myFaces);
498 for (; aFaceIt.More(); aFaceIt.Next())
499 commitEdges(aFaceIt.Value());
501 discretizeFreeEdges();
504 //=======================================================================
505 //function : commitEdges
507 //=======================================================================
508 void BRepMesh_IncrementalMesh::commitEdges(const TopoDS_Face& theFace)
510 TopoDS_Face aFace = theFace;
511 aFace.Orientation(TopAbs_FORWARD);
513 Handle(BRepMesh_FaceAttribute) aFaceAttribute;
514 if (!myMesh->GetFaceAttribute(aFace, aFaceAttribute))
517 if (!aFaceAttribute->IsValid())
519 myStatus |= aFaceAttribute->GetStatus();
523 TopLoc_Location aLoc;
524 Handle(Poly_Triangulation) aTriangulation = BRep_Tool::Triangulation(aFace, aLoc);
526 if (aTriangulation.IsNull())
533 // Store discretization of edges
534 BRepMesh::HDMapOfShapePairOfPolygon& aInternalEdges = aFaceAttribute->ChangeInternalEdges();
535 BRepMesh::DMapOfShapePairOfPolygon::Iterator aEdgeIt(*aInternalEdges);
536 for (; aEdgeIt.More(); aEdgeIt.Next())
538 const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Key());
539 const BRepMesh_PairOfPolygon& aPolyPair = aEdgeIt.Value();
540 const Handle(Poly_PolygonOnTriangulation)& aPolygon1 = aPolyPair.First();
541 const Handle(Poly_PolygonOnTriangulation)& aPolygon2 = aPolyPair.Last();
543 if (aPolygon1 == aPolygon2)
544 BRepMesh_ShapeTool::UpdateEdge(aEdge, aPolygon1, aTriangulation, aLoc);
546 BRepMesh_ShapeTool::UpdateEdge(aEdge, aPolygon1, aPolygon2, aTriangulation, aLoc);
549 catch (Standard_Failure)
551 myStatus |= BRepMesh_Failure;
555 //=======================================================================
558 //=======================================================================
559 Standard_Integer BRepMesh_IncrementalMesh::Discret(
560 const TopoDS_Shape& theShape,
561 const Standard_Real theDeflection,
562 const Standard_Real theAngle,
563 BRepMesh_DiscretRoot* &theAlgo)
565 BRepMesh_IncrementalMesh* anAlgo = new BRepMesh_IncrementalMesh();
566 anAlgo->SetDeflection(theDeflection);
567 anAlgo->SetAngle (theAngle);
568 anAlgo->SetShape (theShape);
569 anAlgo->SetParallel (IS_IN_PARALLEL);
571 return 0; // no error
574 //=======================================================================
575 //function : IsParallelDefault
577 //=======================================================================
578 Standard_Boolean BRepMesh_IncrementalMesh::IsParallelDefault()
581 return IS_IN_PARALLEL;
583 // no alternative parallelization yet - flag has no meaning
584 return Standard_False;
588 //=======================================================================
591 //=======================================================================
592 void BRepMesh_IncrementalMesh::SetParallelDefault(
593 const Standard_Boolean theInParallel)
595 IS_IN_PARALLEL = theInParallel;
598 //! Export Mesh Plugin entry function
599 DISCRETPLUGIN(BRepMesh_IncrementalMesh)