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.
On
Simplification is indeed one of the ideas that pops up first. But this would not be as clean as a native solution.
This kind of irregularity is obtained using a voronoi tesselation, the original problem boiling down to finding the point sampling distribution.
To find the points, it could get realized in the form of a poisson distribution with density driven by the sum of partial derivatives of the height map, along x and y. The measure can be tuned according the empirical fine tuning, (e.g. max instead of sum).
The distribution would better avoid aliasing if it follows a poisson distribution, but other patterns can be applied, like a scanline algorithm that would go line by line and decide the next distance according to absolute value of the derivative. However the distance between lines will be regular and this will cause statistical coherency along x, which is not as good as the original picture posted by Karl. This is why I propose a poisson in this case.
The poisson distribution can be simplified by using a regular uniform poisson on the whole of the map, and then point prunning according the zones where the absolute value of the derivative are the lowest.
The prunning could be decided in blocks, pre-subdivide the whole region in hundreds of sub-blocks, and for each block, take the sum of a good amount of sampling of the derivative map in this block. If the value is low, prune lots of points, randomly. With this method, blocks will have the chance of encompassing multiple points, making the prunning statistically clean. However, larger blocks will also result in bad resolution in zones with highly variating derivatives (the second derivative of the original height map is strong). So again, an empirical fine tuning should be done to determine the ideal size of blocks.
To mitigate the problem of the prunning blocks, MORE points could be generated at startup, and the blocks could be much smaller then, this will have benefits on the two fronts (good antialiasing, and good locality). However it will take more CPU time.
After the point distribution is decided, it is a classic voronoi tesselator, there are hundreds on google.
On
Just an idea. With recursive subdivision create good representation of a map.
Let suppose that area to cover is a triangle. First check does that triangle is good approximation for heights inside. If it is than leave it in a mesh. If it is not than choose one point inside triangle and split it in three triangles and proceed on them.
Check for a triangle approximation is easy, calculation of volume between height curve and triangle. For a split point it is easier to choose triangle center, but that method will produce quite regular mesh. Maybe some statistical method can be used to faster cover bumps in data. I think using mean position has sense.
On
See this answer to a related question: https://stackoverflow.com/a/20859459/3146587.
I also found this article online on TINs with references to actual algorithms: http://www.cs.uu.nl/docs/vakken/gis/TINalg.pdf. Have a look at 2.4.2 "From grid to TIN".
I would think that a mesh simplification algorithm would do what you want. I assume that the large triangles would be a combination of nearly-co-planar triangles in an area.
Some discussion below: http://webdocs.cs.ualberta.ca/~anup/Courses/604_3DTV/Presentation_files/Polygon_Simplification/7.pdf