Delaunay meshing is not merely about creating a mesh on points; it’s about Quality Meshing. This involves crafting a Delaunay mesh with triangles that meet certain quality criteria, such as minimal interior angles or maximum edge lengths. These properties are typically achieved by adding points, effectively refining an existing triangulation. You can find the source code related to this article in the download package under “examples_2D/ex7_qualityMeshing.cpp.”
The initial zone to be refined
The function createSimpleZone(Fade_2D& dt) creates the initial shape. If you’ve explored the preceding examples, you’re already familiar with the process of creating a Zone2 from a polygon. The image labeled ‘Initial Shape’ illustrates the resulting output, which is a Zone2 within a standard Delaunay triangulation of the polygon points. This Zone2 object will undergo various remeshing techniques in the following sections.
Zone2* createSimpleZone(Fade_2D& dt)
{
// Create a shape
std::vector<Point2> vConstraintPoints;
vConstraintPoints.push_back(Point2(30,0));
vConstraintPoints.push_back(Point2(80,0));
vConstraintPoints.push_back(Point2(55,20));
vConstraintPoints.push_back(Point2(100,20));
vConstraintPoints.push_back(Point2(100,100));
vConstraintPoints.push_back(Point2(54.5,22));
vConstraintPoints.push_back(Point2(0,100));
vConstraintPoints.push_back(Point2(0,20));
vConstraintPoints.push_back(Point2(54,20));
std::vector<Segment2> vSegments;
for(size_t i=0;i<vConstraintPoints.size();++i)
{
Point2& p0(vConstraintPoints[i]);
Point2& p1(vConstraintPoints[(i+1)%vConstraintPoints.size()]);
vSegments.push_back(Segment2(p0,p1));
}
ConstraintGraph2* pCG(NULL);
pCG=dt.createConstraint(vSegments,CIS_CONSTRAINED_DELAUNAY);
dt.applyConstraintsAndZones();
Zone2* pZone(dt.createZone(pCG,ZL_INSIDE));
return pZone;
}Delaunay Meshing with Default Parameters
We create the initial zone using the function introduced in the previous paragraph. Then, we proceed to set up a MeshGenParams object, which contains parameters that control the meshing process. The parameters within MeshGenParams have defaults that are well suited for many use cases. We opt to utilize these defaults and proceed to invoke the refineAdvanced() method. For a visual representation of the result, please refer to the image labeled “Polygon meshing with default parameters.”
void strategy_default()
{
Fade_2D dt;
Zone2* pZone=createSimpleZone(dt);
MeshGenParams params(pZone);
dt.refineAdvanced(&params);
highlightTriangles(dt,pZone,"default.ps");
}Delaunay Meshing using the growFactor Parameter
The growFactor parameter in the MeshGenParams class is used to ensure that adjacent triangles do not differ in size by more than this factor. In the code snippet below, we set the growFactor parameter to 3.0 to achieve a smooth transition from smaller to larger triangles. For a visual representation of the result, refer to the image labeled ‘Mesh generation with limited growth.
void strategy_growFactor()
{
Fade_2D dt;
Zone2* pZone=createSimpleZone(dt);
MeshGenParams params(pZone);
params.growFactor=3.0;
dt.refineAdvanced(¶ms);
highlightTriangles(dt,pZone,"growFactor.ps");
}
Delaunay Meshing using the maxEdgeLength Parameter
The maxEdgeLength parameter in the MeshGenParams class is utilized to control the length of the edges in the generated mesh. By default, this parameter is set to DBL_MAX, indicating no limit. When a specific value is assigned to maxEdgeLength, the mesh generation process creates triangles with edges approximately of this specified length, as shown in the image “Mesh generation with limited edge length.”
void strategy_maxLength()
{
Fade_2D dt;
Zone2* pZone=createSimpleZone(dt);
MeshGenParams params(pZone);
params.maxEdgeLength=10.0;
dt.refineAdvanced(&params);
highlightTriangles(dt,pZone,"maxLength.ps");
}The Parameters gridLength and gridVector
Grid Meshing refines a mesh by inserting points that lie on a grid. The side length of the grid corresponds to the gridLength parameter, which may be slightly adapted by the meshing algorithm to ensure a good fit to the shape. By default, the used grid is axis-oriented, but this alignment can be changed using the gridVector parameter, as illustrated in the two Grid-Meshing images.
Fade_2D dt; Zone2* pZone=createSimpleZone(dt); MeshGenParams params(pZone); params.gridLength=3.0; params.gridVector=Vector2(1.0,0.0,0.0); // params.gridVector=Vector2(1.0,0.3,0.0); dt.refineAdvanced(¶ms); highlightTriangles(dt,pZone,"gridMeshing.ps");
Creating a Custom Parameters Class
It may be desirable for your program to have local control over mesh density. This can be accomplished by deriving a class from MeshGenParams and overriding either the getMaxTriangleArea() or getMaxEdgeLength() method with your own code. In the example below, a class named CustomParameters is derived, and getMaxTriangleArea() is overridden to enforce smaller triangles for coordinates x<20 and y<40.
class CustomParameters:public MeshGenParams
{
public:
CustomParameters(Zone2* pZone):MeshGenParams(pZone)
{
}
double getMaxTriangleArea(Triangle2* pT)
{
Point2 barycenter(pT->getBarycenter());
if(barycenter.x()<20 && barycenter.y()<40)
{
// Dense meshing in the lower left corner
return 1.0;
}
else
{
// No density restriction otherwise
return 10.0;
}
}
};
// Uses CustomParameters with a custom getMaxTriangleArea method
void strategy_customParameters()
{
Fade_2D dt;
Zone2* pZone=createSimpleZone(dt);
CustomParameters params(pZone);
dt.refineAdvanced(¶ms);
pZone->show("customParameters.ps",true,true);
}Height Guide Triangulations in 2.5D
While our focus is on a 2D example, refining a triangulation is also applicable in 2.5D. By default, the z-value of a new point is derived from the triangle currently being refined by this point. However, you may encounter a scenario where a second, higher-resolution triangulation is available. In such instances, this second triangulation can serve as a height guide from which the z-coordinate is taken.
void strategy_heightGuide()
{
Fade_2D dt;
Zone2* pZoneSimple=createSimpleZone(dt);
// Another triangulation is used as height guide
Fade_2D dt_guide;
createHeightGuide(dt_guide);
MeshGenParams params(pZoneSimple);
params.maxTriangleArea=10.0;
params.pHeightGuideTriangulation=&dt_guide;
dt.refineAdvanced(¶ms);
dt.writeWebScene("mesh_with_height");
}