Fuse detailed road mesh with regular grid terrain mesh

Question

I am experienced with C++ and know more embedded device related stuff but have absolutely no knowledge of computer graphics and its algorithms.

I would like to get a road mesh (based off of a spline) blended seamlessly into a terrain mesh, which is based on a regular grid, like in the picture below. How is this achieved?

Just looked at the CGAL documentation and I cannot even see which problem I am facing and which package to study. Delauney refinement maybe? But I only see a CGAL package for 2D. I'd like to generate a 3D mesh.

The road mesh should be unmodified, the terrain mesh can be altered to form a seamloss mesh.

Can you guide me to the kind of algorithms needed for this?

Kind regards Max

Answer 1

I think the best way to tackle this problem would be to make an algorithm that works on a single triangle at a time.

You'd look at each terrain triangle individually that the road intersected and process it.

Looking at one triangle individually, you would have to chop that triangle into one or more meshes to make it contour to the road.

Here are some of the cases to consider in the image below. I'm betting there is some triangle slicing algorithm that would be suited to this, and I'm not sure of a name off hand, but the main contribution I'm proposing here is that you deal with triangles individually.

When cutting the triangle on the x/y plane to make a hole for for the road, you would also want the terrain to take on the z value (height) of the road, for those vertices that touch the road. This will make the terrain rise up to meet the road.

At this point, you'd have a terrain mesh which did conform to the road but it would be ugly.

Instead of having a nice even looking hill that went up to the road at reasonable slopes, you'd have some triangles that went very sharply up to the road, and others that had a very flat slope.

What you would need to do now is do some kind of "relaxation" algorithm to address this.

Basically, if something is too steep, because there wasn't enough triangle to make the height adjustment, you need to make your whole triangle closer in height to the road and bleed off some of the height adjustment to neighboring triangles.

If something was not steep enough for your liking, because there was a lot of triangle to make a small height adjustment, you may want to break the triangle up into more polygons where it gets closer to the road and have that smaller area handle the change in elevation.

During this second step, when you added a vertex to an edge between two triangles you would also need to adjust the triangle that shares the edge to prevent cracks from showing up in the terrain.

The details are a bit vague, but hopefully the two step approach will help you tackle the problem.

1. Make the terrain mesh adapt to the road, without caring about how it looks.
2. Refine the terrain mesh to make it appear to meet the road in a more organic man made way.

Answer 2

For a 3D terrain, you can triangulate using the points projected onto the XY-plane. This is easily implemented in CGAL using the Projection_traits_xy_3 class, as in this terrain triangulation example.

For the fusion of the road triangulation you can use a constrained Delaunay triangulation. You constrain the road mesh and insert the regular grid points of the terrain mesh to construct the full triangulation. See this code for an example of how to use CGAL's constrained Delaunay triangulation.

This should enable you to solve the problem without going into the details of the triangles. If the result is not good enough, you can always refine the mesh by inserting additional points in problematic triangles.