I'm looking for an algorithm that converts a regular grid of heights (e.g. 1024x1024) to a triangular irregular network. Here is an image showing an example of a triangular irregular network:
I've looked in the internet for an algorithms to convert it, but I just couldn't find one. Basically the triangle density depends on the roughness and/or pixel error (when rasterized), or something like that.
Here's an idea for a two-step algorithm: Do a Delaunay triangulation based on a rough mesh first, then smoothe out the triangles recursively until a certain error criterion is met.
For the first step, identify a set of vertices for the Delaunay triangulation. These vertices coincide with pixel coordinates. Extreme points that are either higher or lower than all four neighbouring pixels should be in the set as should ridge points on the borders where the adjacent pixels along the border are either lower or higher. This should give a coarse triangular mesh. You can get a finer mesh by also including pixels that have a high curvature.
In the second step, iterate through all triangles. Scan through the triangle along the pixel grid and accumulate an error square for each pixel inside the triangle and also identify the points of maximum and minimum signed error. If the average error per pixel does not meet your criterion, add the points of lowest and highest error to your triangulation. Verify the new triangles and re-triangulate as necessary.
Notes:
The coarse triangulation in step one should be reasonably fast. If the height map is ragged, you might end up with too many vertices in the ragged area. In that case, the hight map might be smoothed with a Gaussian filter before applying the algorithm.
The recursive re-triangulation is probably not so fast, because determining the error requires scanning the triangles over and over. (The process should get faster as the triangle size decreases, but still.) A good criterion for finding vertices in step 1 might speed up step 2.
You can scan a triangle by finding the bounding box of pixels. Find the barycentric coordinates s, t of the lower left point of the bounding box and also the barycentric increments (dsx, dtx) and (dsy, dty) that correspond to a pixel move in the x and y directions. You can then scan the bounding box in two loops over the included pixels (x, y), calculate the barycentric coordinates (s, t) from your delta vectors and accumulate the error if you are inside the triangle, i.e. when s > 0, t > 0 and s + t < 1.
I haven't implemented this algorithm (yet - it is an interesting task), but I imagine that finding a good balance between speed and mesh quality is a matter of tailoring error criteria and vertex selection to the current height map.