Categories
2D Delaunay Triangulation Examples in C++

Advanced Delaunay Meshing – Example 7

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.

A triangulation to be refined
Initial shape
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.”

Delaunay meshing with default parameters
Polygon meshing with default parameters
void strategy_default()
{
Fade_2D dt;
Zone2* pZone=createSimpleZone(dt);
MeshGenParams params(pZone);
dt.refineAdvanced(&amp;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.

Delaunay meshing, but triangle sizes are limited by the growFactor parameter
Mesh generation with limited growth
void strategy_growFactor()
{
Fade_2D dt;
Zone2* pZone=createSimpleZone(dt);

MeshGenParams params(pZone);
params.growFactor=3.0;
dt.refineAdvanced(&params);
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.”

Delaunay triangulation meshed with maxEdgeLength parameter, yielding triangles of approximately equal size
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(&amp;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.

Grid-points-driven Delaunay Meshing with an axis-aligned grid
Grid Meshing with an axis aligned grid
Grid-points-driven Delaunay Meshing oriented by the 'gridVector' parameter
Grid Mesh aligned to the Vector2(1.0,0.3)
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(&params);
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.

Controlling the local mesh density
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(&params);
	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(&params);
	dt.writeWebScene("mesh_with_height");
}

Leave a Reply

Your email address will not be published. Required fields are marked *