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_FaceChecker.hxx>
23 #include <BRepMesh_ShapeTool.hxx>
24 #include <BRepMesh_Edge.hxx>
25 #include <BRepMesh_PluginMacro.hxx>
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>
35 #include <Poly_Triangulation.hxx>
36 #include <Poly_Polygon3D.hxx>
37 #include <Poly_PolygonOnTriangulation.hxx>
40 #include <TopoDS_Edge.hxx>
41 #include <TopoDS_Face.hxx>
42 #include <TopoDS_Shape.hxx>
45 #include <TopExp_Explorer.hxx>
47 #include <TopTools_ListIteratorOfListOfShape.hxx>
48 #include <TColgp_Array1OfPnt.hxx>
49 #include <TColgp_Array1OfPnt2d.hxx>
50 #include <TColStd_Array1OfReal.hxx>
51 #include <TopTools_HArray1OfShape.hxx>
52 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
54 #include <GCPnts_TangentialDeflection.hxx>
57 // paralleling using Intel TBB
58 #include <tbb/parallel_for_each.h>
63 //! Default flag to control parallelization for BRepMesh_IncrementalMesh
64 //! tool returned for Mesh Factory
65 static Standard_Boolean IS_IN_PARALLEL = Standard_False;
68 IMPLEMENT_STANDARD_HANDLE (BRepMesh_IncrementalMesh, BRepMesh_DiscretRoot)
69 IMPLEMENT_STANDARD_RTTIEXT(BRepMesh_IncrementalMesh, BRepMesh_DiscretRoot)
71 //=======================================================================
72 //function : Default constructor
74 //=======================================================================
75 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh()
76 : myRelative (Standard_False),
77 myInParallel (Standard_False)
81 //=======================================================================
82 //function : Constructor
84 //=======================================================================
85 BRepMesh_IncrementalMesh::BRepMesh_IncrementalMesh(
86 const TopoDS_Shape& theShape,
87 const Standard_Real theLinDeflection,
88 const Standard_Boolean isRelative,
89 const Standard_Real theAngDeflection,
90 const Standard_Boolean isInParallel)
91 : myRelative (isRelative),
92 myInParallel(isInParallel)
94 myDeflection = theLinDeflection;
95 myAngle = theAngDeflection;
101 //=======================================================================
102 //function : Destructor
104 //=======================================================================
105 BRepMesh_IncrementalMesh::~BRepMesh_IncrementalMesh()
109 //=======================================================================
112 //=======================================================================
113 void BRepMesh_IncrementalMesh::init()
116 myModified = Standard_False;
118 myEdgeDeflection.Clear();
123 if (!isCorrectPolyData())
124 BRepTools::Clean(myShape);
127 BRepBndLib::Add(myShape, aBox, Standard_False);
136 BRepMesh_ShapeTool::BoxMaxDimension(aBox, myMaxShapeSize);
138 myMesh = new BRepMesh_FastDiscret(myDeflection, myAngle, aBox,
139 Standard_True, Standard_True, myRelative, Standard_True, myInParallel);
141 myMesh->InitSharedFaces(myShape);
144 //=======================================================================
145 //function : isCorrectPolyData
147 //=======================================================================
148 Standard_Boolean BRepMesh_IncrementalMesh::isCorrectPolyData()
152 BRepMesh_FaceChecker aFaceChecker(myInParallel);
157 // check faces in parallel threads using TBB
158 tbb::parallel_for_each(myFaces.begin(), myFaces.end(), aFaceChecker);
163 std::vector<TopoDS_Face>::iterator aFaceIt = myFaces.begin();
164 for (; aFaceIt != myFaces.end(); aFaceIt++)
165 aFaceChecker(*aFaceIt);
170 return aFaceChecker.IsValid();
173 //=======================================================================
174 //function : collectFaces
176 //=======================================================================
177 void BRepMesh_IncrementalMesh::collectFaces()
179 TopTools_ListOfShape aFaceList;
180 BRepLib::ReverseSortFaces(myShape, aFaceList);
181 TopTools_MapOfShape aFaceMap;
182 myFaces.reserve(aFaceList.Extent());
184 // make array of faces suitable for processing (excluding faces without surface)
185 TopLoc_Location aDummyLoc;
186 const TopLoc_Location aEmptyLoc;
187 TopTools_ListIteratorOfListOfShape aFaceIter(aFaceList);
188 for (; aFaceIter.More(); aFaceIter.Next())
190 TopoDS_Shape aFaceNoLoc = aFaceIter.Value();
191 aFaceNoLoc.Location(aEmptyLoc);
192 if (!aFaceMap.Add (aFaceNoLoc))
193 continue; // already processed
195 TopoDS_Face aFace = TopoDS::Face(aFaceIter.Value());
196 const Handle(Geom_Surface)& aSurf = BRep_Tool::Surface(aFace, aDummyLoc);
200 myFaces.push_back(aFace);
204 //=======================================================================
207 //=======================================================================
208 void BRepMesh_IncrementalMesh::Perform()
218 //=======================================================================
219 //function : update()
221 //=======================================================================
222 void BRepMesh_IncrementalMesh::update()
225 TopExp_Explorer aExplorer(myShape, TopAbs_EDGE);
226 for (; aExplorer.More(); aExplorer.Next())
228 const TopoDS_Edge& aEdge = TopoDS::Edge(aExplorer.Current());
229 if(!BRep_Tool::IsGeometric(aEdge))
236 std::vector<TopoDS_Face>::iterator aFaceIt(myFaces.begin());
237 for (; aFaceIt != myFaces.end(); aFaceIt++)
244 tbb::parallel_for_each(myFaces.begin(), myFaces.end(), *myMesh);
249 for (aFaceIt = myFaces.begin(); aFaceIt != myFaces.end(); aFaceIt++)
250 myMesh->Process(*aFaceIt);
258 //=======================================================================
259 //function : discretizeFreeEdges
261 //=======================================================================
262 void BRepMesh_IncrementalMesh::discretizeFreeEdges()
264 TopExp_Explorer aExplorer(myShape ,TopAbs_EDGE, TopAbs_FACE);
265 for (; aExplorer.More(); aExplorer.Next())
267 const TopoDS_Edge& aEdge = TopoDS::Edge(aExplorer.Current());
268 if(!BRep_Tool::IsGeometric(aEdge))
271 TopLoc_Location aLoc;
272 Standard_Real aEdgeDeflection = edgeDeflection(aEdge);
273 Handle(Poly_Polygon3D) aPoly3D = BRep_Tool::Polygon3D(aEdge, aLoc);
274 if (!aPoly3D.IsNull() && aPoly3D->Deflection() < 1.1 * aEdgeDeflection)
277 BRepAdaptor_Curve aCurve(aEdge);
278 GCPnts_TangentialDeflection aDiscret(aCurve, aCurve.FirstParameter(),
279 aCurve.LastParameter(), myAngle, aEdgeDeflection, 2);
281 Standard_Integer aNodesNb = aDiscret.NbPoints();
282 TColgp_Array1OfPnt aNodes (1, aNodesNb);
283 TColStd_Array1OfReal aUVNodes(1, aNodesNb);
284 for (Standard_Integer i = 1; i <= aNodesNb; ++i)
286 aNodes (i) = aDiscret.Value(i);
287 aUVNodes(i) = aDiscret.Parameter(i);
290 aPoly3D = new Poly_Polygon3D(aNodes, aUVNodes);
291 aPoly3D->Deflection(myDeflection);
293 BRep_Builder aBuilder;
294 aBuilder.UpdateEdge(aEdge, aPoly3D);
298 //=======================================================================
299 //function : edgeDeflection
301 //=======================================================================
302 Standard_Real BRepMesh_IncrementalMesh::edgeDeflection(
303 const TopoDS_Edge& theEdge)
305 if (myEdgeDeflection.IsBound(theEdge))
306 return myEdgeDeflection(theEdge);
308 Standard_Real aEdgeDeflection;
311 Standard_Real aScale;
312 aEdgeDeflection = BRepMesh_ShapeTool::RelativeEdgeDeflection(theEdge,
313 myDeflection, myMaxShapeSize, aScale);
316 aEdgeDeflection = myDeflection;
318 myEdgeDeflection.Bind(theEdge, aEdgeDeflection);
319 return aEdgeDeflection;
322 //=======================================================================
323 //function : faceDeflection
325 //=======================================================================
326 Standard_Real BRepMesh_IncrementalMesh::faceDeflection(
327 const TopoDS_Face& theFace)
332 Standard_Integer aEdgesNb = 0;
333 Standard_Real aFaceDeflection = 0.;
335 TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
336 for (; aEdgeIt.More(); aEdgeIt.Next(), ++aEdgesNb)
338 const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
339 aFaceDeflection += edgeDeflection(aEdge);
342 return (aEdgesNb == 0) ? myDeflection : (aFaceDeflection / aEdgesNb);
345 //=======================================================================
346 //function : update(edge)
348 //=======================================================================
349 void BRepMesh_IncrementalMesh::update(const TopoDS_Edge& theEdge)
351 Standard_Integer aPolyIndex = 1;
352 Standard_Real aEdgeDeflection = edgeDeflection(theEdge);
353 Handle(Poly_PolygonOnTriangulation) aPolygon;
356 TopLoc_Location aLoc;
357 Handle(Poly_Triangulation) aTriangulation;
358 BRep_Tool::PolygonOnTriangulation(theEdge, aPolygon,
359 aTriangulation, aLoc, aPolyIndex++);
361 if (!aTriangulation.IsNull() && !aPolygon.IsNull())
363 if (aPolygon->Deflection() < 1.1 * aEdgeDeflection &&
364 aPolygon->HasParameters())
369 myModified = Standard_True;
370 BRepMesh_ShapeTool::NullifyEdge(theEdge, aTriangulation, aLoc);
373 if (!myEmptyEdges.IsBound(theEdge))
374 myEmptyEdges.Bind(theEdge, BRepMeshCol::MapOfTriangulation());
376 if (!aTriangulation.IsNull())
377 myEmptyEdges(theEdge).Add(aTriangulation);
379 while (!aPolygon.IsNull());
382 //=======================================================================
383 //function : isToBeMeshed
385 //=======================================================================
386 Standard_Boolean BRepMesh_IncrementalMesh::toBeMeshed(
387 const TopoDS_Face& theFace,
388 const Standard_Boolean isWithCheck)
390 TopLoc_Location aLoc;
391 Handle(Poly_Triangulation) aTriangulation =
392 BRep_Tool::Triangulation(theFace, aLoc);
394 if (aTriangulation.IsNull())
395 return Standard_True;
399 Standard_Real aFaceDeflection = faceDeflection(theFace);
400 if (aTriangulation->Deflection() < 1.1 * aFaceDeflection)
402 Standard_Boolean isEdgesConsistent = Standard_True;
403 TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
404 for (; aEdgeIt.More() && isEdgesConsistent; aEdgeIt.Next())
406 const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
407 if (!myEmptyEdges.IsBound(aEdge))
410 BRepMeshCol::MapOfTriangulation& aTriMap = myEmptyEdges(aEdge);
411 isEdgesConsistent &= !aTriMap.IsEmpty() && !aTriMap.Contains(aTriangulation);
414 if (isEdgesConsistent)
415 return Standard_False;
420 TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
421 for (; aEdgeIt.More(); aEdgeIt.Next())
423 const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
424 BRepMesh_ShapeTool::NullifyEdge(aEdge, aTriangulation, aLoc);
427 BRepMesh_ShapeTool::NullifyFace(theFace);
428 return Standard_True;
431 //=======================================================================
432 //function : update(face)
434 //=======================================================================
435 void BRepMesh_IncrementalMesh::update(const TopoDS_Face& theFace)
437 if (!toBeMeshed(theFace, Standard_True))
440 myModified = Standard_True;
441 Standard_Integer aStatus = myMesh->Add(theFace);
444 if (aStatus != BRepMesh_ReMesh)
447 BRepMeshCol::MapOfShape aUsedFaces;
448 aUsedFaces.Add(theFace);
450 const TopTools_IndexedDataMapOfShapeListOfShape& aMapOfSharedFaces =
451 myMesh->SharedFaces();
453 TopExp_Explorer aEdgeIt(theFace, TopAbs_EDGE);
454 for (; aEdgeIt.More(); aEdgeIt.Next())
456 const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
457 if (aMapOfSharedFaces.FindIndex(aEdge) == 0)
460 const TopTools_ListOfShape& aSharedFaces = aMapOfSharedFaces.FindFromKey(aEdge);
461 TopTools_ListIteratorOfListOfShape aSharedFaceIt(aSharedFaces);
462 for (; aSharedFaceIt.More(); aSharedFaceIt.Next())
464 const TopoDS_Face& aFace = TopoDS::Face(aSharedFaceIt.Value());
465 if (aUsedFaces.Contains(aFace))
468 aUsedFaces.Add(aFace);
469 toBeMeshed(aFace, Standard_False);
471 myStatus |= myMesh->Add(aFace);
476 //=======================================================================
479 //=======================================================================
480 void BRepMesh_IncrementalMesh::commit()
482 std::vector<TopoDS_Face>::iterator aFaceIt(myFaces.begin());
483 for (; aFaceIt != myFaces.end(); aFaceIt++)
484 commitFace(*aFaceIt);
486 discretizeFreeEdges();
489 //=======================================================================
490 //function : commitFace
492 //=======================================================================
493 void BRepMesh_IncrementalMesh::commitFace(const TopoDS_Face& theFace)
495 TopoDS_Face aFace = theFace;
496 aFace.Orientation(TopAbs_FORWARD);
498 Handle(BRepMesh_FaceAttribute) aFaceAttribute;
499 if (!myMesh->GetFaceAttribute(aFace, aFaceAttribute))
502 BRepMesh_ShapeTool::NullifyFace(aFace);
504 if (!aFaceAttribute->IsValid())
506 myStatus |= aFaceAttribute->GetStatus();
510 TopLoc_Location aLoc = aFace.Location();
511 Handle(Poly_Triangulation) aOldTriangulation = BRep_Tool::Triangulation(aFace, aLoc);
517 Handle(BRepMesh_DataStructureOfDelaun)& aStructure = aFaceAttribute->ChangeStructure();
518 const BRepMeshCol::MapOfInteger& aTriangles = aStructure->ElementsOfDomain();
519 if (aTriangles.IsEmpty())
522 BRepMeshCol::HIMapOfInteger& aVetrexEdgeMap = aFaceAttribute->ChangeVertexEdgeMap();
525 Standard_Integer aVerticesNb = aVetrexEdgeMap->Extent();
526 Standard_Integer aTrianglesNb = aTriangles.Extent();
527 Handle(Poly_Triangulation) aNewTriangulation =
528 new Poly_Triangulation(aVerticesNb, aTrianglesNb, Standard_True);
530 Poly_Array1OfTriangle& aPolyTrianges = aNewTriangulation->ChangeTriangles();
532 Standard_Integer aTriangeId = 1;
533 BRepMeshCol::MapOfInteger::Iterator aTriIt(aTriangles);
534 for (; aTriIt.More(); aTriIt.Next())
536 const BRepMesh_Triangle& aCurElem = aStructure->GetElement(aTriIt.Key());
538 Standard_Integer aNode[3];
539 aStructure->ElementNodes(aCurElem, aNode);
541 Standard_Integer aNodeId[3];
542 for (Standard_Integer i = 0; i < 3; ++i)
543 aNodeId[i] = aVetrexEdgeMap->FindIndex(aNode[i]);
545 aPolyTrianges(aTriangeId++).Set(aNodeId[0], aNodeId[1], aNodeId[2]);
549 TColgp_Array1OfPnt& aNodes = aNewTriangulation->ChangeNodes();
550 TColgp_Array1OfPnt2d& aNodes2d = aNewTriangulation->ChangeUVNodes();
552 for (Standard_Integer i = 1; i <= aVerticesNb; ++i)
554 Standard_Integer aVertexId = aVetrexEdgeMap->FindKey(i);
555 const BRepMesh_Vertex& aVertex = aStructure->GetNode(aVertexId);
556 const gp_Pnt& aPoint = aFaceAttribute->GetPoint(aVertex);
559 aNodes2d(i) = aVertex.Coord();
562 aNewTriangulation->Deflection(aFaceAttribute->GetDefFace());
563 BRepMesh_ShapeTool::AddInFace(aFace, aNewTriangulation);
565 // Store discretization of edges
566 BRepMeshCol::HDMapOfShapePairOfPolygon& aInternalEdges = aFaceAttribute->ChangeInternalEdges();
567 BRepMeshCol::DMapOfShapePairOfPolygon::Iterator aEdgeIt(*aInternalEdges);
568 for (; aEdgeIt.More(); aEdgeIt.Next())
570 const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Key());
571 const BRepMesh_PairOfPolygon& aPolyPair = aEdgeIt.Value();
572 const Handle(Poly_PolygonOnTriangulation)& aPolygon1 = aPolyPair.First();
573 const Handle(Poly_PolygonOnTriangulation)& aPolygon2 = aPolyPair.Last();
575 BRepMesh_ShapeTool::NullifyEdge(aEdge, aOldTriangulation, aLoc);
576 if (aPolygon1 == aPolygon2)
577 BRepMesh_ShapeTool::UpdateEdge(aEdge, aPolygon1, aNewTriangulation, aLoc);
579 BRepMesh_ShapeTool::UpdateEdge(aEdge, aPolygon1, aPolygon2, aNewTriangulation, aLoc);
582 catch (Standard_Failure)
584 myStatus |= BRepMesh_Failure;
588 //=======================================================================
591 //=======================================================================
592 Standard_Integer BRepMesh_IncrementalMesh::Discret(
593 const TopoDS_Shape& theShape,
594 const Standard_Real theDeflection,
595 const Standard_Real theAngle,
596 BRepMesh_DiscretRoot* &theAlgo)
598 BRepMesh_IncrementalMesh* anAlgo = new BRepMesh_IncrementalMesh();
599 anAlgo->SetDeflection(theDeflection);
600 anAlgo->SetAngle (theAngle);
601 anAlgo->SetShape (theShape);
602 anAlgo->SetParallel (IS_IN_PARALLEL);
604 return 0; // no error
607 //=======================================================================
608 //function : IsParallelDefault
610 //=======================================================================
611 Standard_Boolean BRepMesh_IncrementalMesh::IsParallelDefault()
614 return IS_IN_PARALLEL;
616 // no alternative parallelization yet - flag has no meaning
617 return Standard_False;
621 //=======================================================================
624 //=======================================================================
625 void BRepMesh_IncrementalMesh::SetParallelDefault(
626 const Standard_Boolean theInParallel)
628 IS_IN_PARALLEL = theInParallel;
631 //! Export Mesh Plugin entry function
632 DISCRETPLUGIN(BRepMesh_IncrementalMesh)