While working on a gdscript to generate a terrain with several level of details (LOD), a tricky issue popped up: the terrain had holes scattered across its surface…
There is a difference of definition on the tesselation frontiers, the vertices at the lower level joins 2 distant areas of the texture while the vertices at the upper level takes a sample in between these 2 areas.
As the terrain is using an heightmap to set its altitude, this difference of sampling implied visual inconsistencies, as seen in the second image.
After some researches (moving UVS, solving via shader, extra data in the mesh), the simplest option appeared to be a smart sewing of vertices at these level frontiers. Indeed, only 2 special triangulations are enough:
In case of 2 adjacent quads having a different tesselation level, an extra vertices is generated in the middle of the common edges (see top case). Instead of the common triangulation, we split the quad with the lowest tesselation level into 3 triangles. By doing this, we only add one triangle per quad, so 3 instead of 2.
There is a special case where a quad is adjacent to 2 quads with higher tesselation level (see bottom case). The most efficient way to solve this is to add 2 extra vertices on common edges and generate the triangles as shown.
These 2 cases are enough to sew together all frontiers, we just have to rotate or flip the case accordingly to the position of the common edge.
Once we apply this on the mesh, we get this kind of triangulation:
Any heightmap can be applied on the mesh: as all faces are linked together, there is no more “holes” appearing in the surface.
Note: the tesselation algorithm is using a tree to store quads, meaning a quad of level #1 has 4 smaller quads inside of him, level #2 has 4 quads each one have 4 quads (16 sub-sub-quads) and so on.
Due to this nesting of quads, detection of tesselation frontiers is harder, as there can be frontiers inside a quad of level #1 or between it and ones on top, right, bottom or left.
The implementation of this algorithm can be found in this script: hw_generator.gd
See method func add_face( f : Dictionary, surf : SurfaceTool ): for the implementation of the special sewing.