# Generating triangles from a square grid

I have a 2D square grid of values representing terrain elevations, and I want to generate triangles from that grid to make a 3D view of the terrain. My first thought was to split each square diagonally into 2 triangles, however the split diagonal can clearly be seen, especially from the top :

Is there a recommended way to generate triangles to remove/reduce this effect ?

-
 Out of curiosity, how did you color the terrain? Did you write a shader that assigned colors based on height? (I am still very much a beginner to modern OpenGL). – wardd Dec 7 '12 at 19:35 @wardd I simply set the color of the vertex to some value dependent on the height, and OpenGL does a linear interpolation when drawing the triangles (actually I'm using OpenGL ES 1.1 so no shaders for me :)) – vivi Dec 8 '12 at 5:06

Your terrain reminds me of the practicle example (Height Interpolation) used in the Delaunay Triangulations chapter (PDF) of Computational Geometry: Algorithms and Applications. Although they generate an irregular triangle mesh from a height map, the part on illegal edges might still apply to your regular triangle mesh.

The idea is there are two ways you might flip the edge for every four neighbouring grid vertices (I'll refer to these as a quad later on). They define an edge as illegal if we can locally increase the smallest angle by flipping that edge. The chapter then leads up to using a Delaunay triangulation to get an illegal edge free mesh, but since you have a regular grid you can suffice by running through all quads and decide the splitting edge based on the length, like so:

``````def get_triangles(quads):
# 0--1
# |  |
# 3--2
# NW-SE edge is shortest
else:
# NE-SW edge is shortest
``````

Choosing the shortest splitting edge should result in a more natural terrain with a relatively small amount of work.

Bonus: With a lot more work you can do even better by taking into account your height map's global features like peaks, ridges, valleys and drainage flow paths. For an introduction have a look at Section 3.2 and 3.5 of this article: Digital Elevation Models: overview and selected TIN algorithms.

-
I just tried this, it's noticeably better, especially in the river beds : imgur – vivi Dec 7 '12 at 22:54
Cool! Thanks for reporting the results. :-) – Eric Dec 8 '12 at 8:38

It won't look good to you unless you tessellate the mesh more finely (use more triangles, use a bigger grid, and have the elevation changes go much slower)

Your normals are off a bit. To find smoothed normals at a vertex, you have to take several cross products at each vertex, sum the normals you find, then normalize that normal.

For example,

Here you would find the vectors `a`, `b`, `c`, `d`, and the normal at the center vertex would be:

``````n1 = a x b
n2 = b x c
n3 = c x d
n4 = d x a

finalNormal = (n1 + n2 + n3 + n4).normalize()
``````

You could also use the other 4 (diagonal) vectors, but that is really overkill. If you use 4 vectors it will almost look the same as if you use 8 vectors.

-
 I think with smooth shading the mesh will turn out pretty well even at the amount of tesselation displayed in the images. – ktodisco Dec 7 '12 at 4:05 OK, I'm beginning to understand. It makes sense to consider that the normals are a property of the terrain vertexes, and not of the triangles, as I thought. Maybe I should have my terrain generator produce the normals as well. I think I'm confused also by the fact that vertex normals must be used with smooth shading, and looks weird with flat shading. Following your advice (see here (imgur)) it is definitely much better. I guess the linear interpolation just doesn't cut it for terrain, and the only solution is to compute more terrain data points in the first place. – vivi Dec 7 '12 at 4:43 They are equivalent. Here I am finding the normal as effectively the average normal of the 4 quads surrounding the vertex. Using the 8 vector solution will effectively find you the average normal of the 8 triangles surrounding the vertex. – bobobobo Dec 7 '12 at 19:15

I can think of a few approaches, here's a few in order of work required (but probably increased quality)

First: alternate edge direction; this should be easy to implement

``````.---.---.---.    .---.---.---.
| / | / | / |    | / | \ | / |
'---'---'---' -> '---'---'---'
| / | / | / |    | \ | / | \ |
'---'---'---'    '---'---'---'
``````

Second: choose edge direction based on edge length. Check whether / or \ is shorter and pick that - or the longer one. Test and see which looks better. The bad side about this approach is that it requires a little bit more work.

Third: Implement algorithm to "turn edges". For each edge you find two triangles (on the both sides of the edge) which form a quadrilateral. The edge that splits said quad can be "turned" to form two different triangles. Note that the "turnable" edges include the original horizontal and vertical edges. Run several passes over the geometry to minimize the edge lengths.

Fourth: Discard squares to begin with and while your source data may still be square-based, just sample it for the height values based on some sampling algorithm. Point sampling is fine if you first scale your source data way up.

After discarding squares, things get more interesting; what kind of mesh to use? Hexagons? Subdivided polygons based on amount of noise within the polygons (so flat areas use less polys than bumpy ones)? Random data?

You may also want to pick up the classic, "Texturing & Modelling, procedural approach" http://www.amazon.com/Texturing-Modeling-Third-Edition-Procedural/dp/1558608486

-
 I'm using a square mesh for gameplay reasons, but actually my terrain generation algorithm is a function R^2 -> R, maybe I made the newbie mistake of thinking "I want to achieve A, but I think B is a good way to do A so I'll ask how to do B instead of asking how to do A". – vivi Dec 7 '12 at 22:56

Based on the image you provided, I would say that you are on the right track, and the next step is to enable smooth shading on the mesh. Currently, you are seeing hard edges in the lighting on adjacent triangles because each triangle is being flat shaded. The normal of only one of the vertices is being used to do lighting calculations, rather than the normals of all three vertices being interpolated across the face of the triangle (or the lighting at each vertex being interpolated, depending on whether you're using per-pixel or per-vertex lighting, respectively).

In older OpenGL implementations, enabling smooth (Gourard) shading would be done with the following line:

``````glShadeModel(GL_SMOOTH);
``````

but note that this is now deprecated in favor of the programmable pipeline. Fear not, though, as it will still work if you work with an older OpenGL library (and it may also be supported in the most recent version; someone may correct me if I'm wrong about that). To go off on a brief tangent, learning OpenGL via the deprecated immediate mode is sometimes preferred because it's a little more straightforward than the programmable pipeline.

Anyway, the smooth shading is also dependent upon the normals of your vertices being set correctly, which seems to already be happening, upon examination of your image. If, for whatever reason, they are not quite correct, I'd be happy to update this answer to provide some direction on how to calculate them.

Hope this helps :)

Update: To calculate the normals for proper lighting, you can use the following rule: the normal for a vertex is equal to the average of the face normals of the triangles it is a part of. The face normal of a triangle is calculated by taking the cross-product of two of its edges. So, for one of the corners of your mesh:

``````A-----B
|   .`|
| .`  |
C`----D
``````

You can calculate the face normal of `ABC` by taking `BA x BC`, and the face normal of `BCD` to by taking `BC x BD`. Averaging the two resulting vectors together and normalizing the result gets you the normal for `B`. For vertices in the middle of the mesh, you will be calculating and averaging the face normals of eight triangles. Note that this is the method which bobobobo provided in his answer. I hope that this summary acts as a good complement to it.

For this kind of calculation, it really pays to store your mesh in a Half-Edge data structure. This makes traversal of the triangles much easier, and also allows you to implement subdivision and decimation of the mesh in case you need it later on.

-
 Smooth shading is enabled, but I duplicated the vertexes for each triangle and set their normals to the normal of the triangle. I don't immediately see what would be the normal of a single vertex, is it the average of the normals of the adjacent triangles? Does a triangle with a wide angle count more than a narrow angle? What about the edges? Sorry if my questions are a bit messy, I'm learning as I go :) – vivi Dec 6 '12 at 7:19 @vivi I have updated my answer to explain how the normals can be calculated, and also provided some other useful tips. – ktodisco Dec 7 '12 at 4:00