Merging Two Triangulations

Just like the previous article, this one focuses on the C++ example of merging. In this part, we describe the function demo3_mergeShapes(), which explains how to merge two triangulations.

You pass two zones to the function: one is the higher-priority triangulation, while the other has just base priority. The higher-priority triangulation remains intact, and we remove the overlap area — plus optionally a clearance region — from the base-priority triangulation. Afterward, we connect the two triangulations. You can find the corresponding C++ code in the file examples_real/mergingTriangulations/main.cpp.

Merging two triangulated shapes is hard. There are quite a few unexpected details to consider, and you probably won’t find source code like this anywhere else. These 80 lines of code are pure gold. So grab a coffee and enjoy!

Input Meshes for the Merge Algorithm

The function getLetters() generates input zones for this demo: pBaseZone and pPriorityZone, located in two separate Fade_2D objects. In this example, pBaseZone is the blue triangulation, while pPriorityZone is the green triangulation, which will be treated with higher priority. You can safely ignore the function implementation, as you will create or load your own zones as input. Refer to the article I/O: Bridging Your Software With Fade2D to learn about common I/O operations.

// Create input zones for the 
// merging triangulations demo
Fade_2D baseFade,priorityFade;
Zone2 *pBaseZone,*pPriorityZone;
getLetters(baseFade,pBaseZone,priorityFade,pPriorityZone);

The Merge Function

void demo3_mergeShapes(Fade_2D& baseFade, Zone2* pBaseZone,
					   Zone2* pPriorityZone,
					   Fade_2D& resultFade,Zone2*& pResultZone)

This function takes two zones, pBaseZone and pPriorityZone, as input and creates a merged triangulation in pResultZone. The merging algorithm preserves all triangles of pPriorityZone while removing the overlapping area and an optional clearance from pBaseZone. The clearance is needed for the slopes between the zones when they overlap at different heights, as perfectly vertical walls are not feasible in 2.5D. Let’s now walk through the demo3_mergeShapes() function step by step.

Step 1: Creating an Offset Zone

This step prepares the offset zone, pOffPrioZone, which will be used to create the clearance between the zones. To define it, we generate an offset boundary (red) from pPriorityZone (green) and project it onto baseFade, the Fade_2D instance of pBaseZone. Then, we create pOffPrioZone using this projected offset boundary. It closesly matches pPriorityZone as the used offset distance is small.

// * Step 1 *   
// Compute an offset polygon of pPriorityZone, project it 
// onto baseFade and create the offset zone pOffPrioZone.
const double OFFSET(0.1); // >0 if the zones overlap at different heights!
vector<Segment2> vOffsetBoundary;
pPriorityZone->getOffsetBoundary(OFFSET, vOffsetBoundary, 91, 45);
vector<Segment2> vDrapedOffsetBoundary;
baseFade.drape(vOffsetBoundary, vDrapedOffsetBoundary, .01, 0.0,true);
ConstraintGraph2* pOffCG(baseFade.createConstraint(vDrapedOffsetBoundary, CIS_CONSTRAINED_DELAUNAY,true));
Zone2* pOffPrioZone(baseFade.createZone(pOffCG,ZL_INSIDE));

Step 2: Collecting the Triangles to Retain

We want to keep only the part of pBaseZone (blue) that doesn’t overlap pOffPrioZone. We denote this area by pKeptBaseZone, and compute it using the boolean set operation zoneDifference(). Then we iterate over the triangles in pKeptBaseZone and pPriorityZone, and collect their corners in the point vector vCorners, which will later be used to import these triangles into a new triangulation.

Zone2* pKeptBaseZone=zoneDifference(pBaseZone,pOffPrioZone);
vector<Point2> vCorners; // Collects the triangle corners
for(Zone2* pZone:{pKeptBaseZone,pPriorityZone})
{
	vector<Triangle2*> vT;
	pZone->getTriangles(vT);
	for(Triangle2* pT:vT)
	{
		for(int i=0;i<3;++i)
		{
			vCorners.emplace_back(*pT->getCorner(i));
		}
	}
}

This image shows the triangles we retain, copied to vCorners. The offset distance was intentionally set larger for this image to better visualize the clearance between the triangles of the two zones. Note that the connecting triangles in the clearance area are still missing.

Step 3: Creating the new Boundary

We need a polygon to bound the new, merged zone. This polygon is essentially the boundary of the union of the two input zones, but computing it requires attention to two important details:

1. Boolean set operations require both input zones to be from the same Fade_2D instance. Therefore, we replicate pPriorityZone in baseFade before computing pZoneUnion.
2. We could extract the polygon from pZoneUnion using getBoundarySegments(). However, due to the finite accuracy of floating-point numbers, the coordinates of new points, resulting from the intersections, may not be exact. To avoid extra triangles caused by points not lying on the merged triangulation, we compute the boundary using a small negative offset distance, ensuring that all points lie on pZoneUnion.

Zone2* pReplPrioZone=baseFade.replicateZoneBoundary(pPriorityZone,true);
Zone2* pUnionZone=zoneUnion(pReplPrioZone,pBaseZone);
vector<Segment2> vUnionBoundary;
pUnionZone->getOffsetBoundary(-0.001,vUnionBoundary,91,45);

Step 4: Importing the Triangles into a New Triangulation

We use importTriangles_robust(vCorners) to import the triangles to be retained into resultFade. This command completes the convex hull with additional fill-triangles, so the connecting triangles in the clearance area appear automatically. While the command returns the imported zone, it is not suitable for our purposes, as it excludes the connecting triangles. Therefore, we create pResultZone using the boundary segments in vUnionBoundary, which were generated in the previous step.

// * Step 4 *   Import the triangles into a new triangulation,
// optionally remove any constraint segments, and create the
// required boundary constraint segments.
resultFade.importTriangles_robust(vCorners);
ConstraintGraph2* pBoundaryCG(resultFade.createConstraint(vUnionBoundary,CIS_CONSTRAINED_DELAUNAY,true));
pResultZone=resultFade.createZone(pBoundaryCG,ZL_INSIDE);
pResultZone->showVtk("resultZone.vtk",VTK_GREEN,VTK_TRANSPARENT,VTK_RED);

The image below shows the merged result. Notice that the importTriangles_robust() command has created inner constraint segments.

Step 5: Removing the Inner Constraint Segments

Whether to keep or remove the inner constraint segments depends on your application. This step is optional. The following code snippet:

• Clears vUnionBoundary and retrieves the final boundary segments (potentially subdivided) from pResultZone.
• Deletes all existing constraints and zones in resultFade.
• Inserts only vUnionBoundary as constraint and uses it to recreate pResultZone.

// * Step 5 *   Optional: Remove the inner constraints
vUnionBoundary.clear();
pResultZone->getBoundarySegments(vUnionBoundary);

resultFade.deleteConstraintsAndZones(); // Optional: Do this only if you are aware of the consequences!
pBoundaryCG=resultFade.createConstraint(vUnionBoundary,CIS_CONSTRAINED_DELAUNAY,true);
pResultZone=resultFade.createZone(pBoundaryCG,ZL_INSIDE);
pResultZone->showVtk("resultZoneClean.vtk",VTK_GREEN,VTK_TRANSPARENT,VTK_RED);