GitHub - kylebarron/pydelatin: Python bindings to hmm for fast terrain mesh generation (original) (raw)

pydelatin

A Python wrapper of hmm (of which Delatin is a port) for fast terrain mesh generation.

A screenshot of Glacier National Park taken from the demo. The mesh is created using pydelatin, encoded usingquantized-mesh-encoder, served on-demand usingdem-tiler, and rendered with deck.gl.

Install

With pip:

or with Conda:

conda install -c conda-forge pydelatin

On Windows, installing via Conda is strongly recommended.

If installing with pip on Windows, glm is a prerequisite for building from source. Open an issue if you'd like to help package binary wheels for Windows.

Using

Example

from pydelatin import Delatin

tin = Delatin(terrain, width, height)

Mesh vertices

tin.vertices

Mesh triangles

tin.triangles

API

The API is similar to that of hmm.

Additionally I include a helper function: decode_ele, to decode a Mapbox Terrain RGB or Terrarium PNG array to elevations.

Delatin

Arguments

• arr (numpy ndarray): data array. If a 2D array, dimensions are expected to be (height, width). If a 1D array, height and width parameters must be passed, and the array is assumed to be in C order.
• height (int, default: None): height of array; required when arr is not 2D
• width (int, default: None): width of array; required when arr is not 2D
• z_scale (float, default: 1): z scale relative to x & y
• z_exag (float, default: 1): z exaggeration
• max_error (float, default: 0.001): maximum triangulation error
• max_triangles (int, default: None): maximum number of triangles
• max_points (int, default: None): maximum number of vertices
• base_height (float, default: 0): solid base height
• level (bool, default: False): auto level input to full grayscale range
• invert (bool, default: False): invert heightmap
• blur (int, default: 0): gaussian blur sigma
• gamma (float, default: 0): gamma curve exponent
• border_size (int, default: 0): border size in pixels
• border_height (float, default: 1): border z height

Attributes

• vertices (ndarray of shape (-1, 3)): the interleaved 3D coordinates of each vertex, e.g. [[x0, y0, z0], [x1, y1, z1], ...].
• triangles (ndarray of shape (-1, 3)): represents indices within the vertices array. So [0, 1, 3, ...] would use the first, second, and fourth vertices within the vertices array as a single triangle.
• error (float): the maximum error of the mesh.

util.rescale_positions

A helper function to rescale the vertices output to a new bounding box. Returns an ndarray of shape (-1, 3) with positions rescaled. Each row represents a single 3D point.

Arguments

• vertices: (np.ndarray) vertices output from Delatin
• bounds: (Tuple[float]) linearly rescale position values to this extent. Expected to be [minx, miny, maxx, maxy].
• flip_y: (bool, default False) Flip y coordinates. Can be useful since images' coordinate origin is in the top left.

Saving to mesh formats

Quantized Mesh

A common mesh format for the web is the Quantized Meshformat, which is supported in Cesium and deck.gl (vialoaders.gl). You can usequantized-mesh-encoder to save in this format:

import quantized_mesh_encoder from pydelatin import Delatin from pydelatin.util import rescale_positions

tin = Delatin(terrain, max_error=30) vertices, triangles = tin.vertices, tin.triangles

Rescale vertices linearly from pixel units to world coordinates

rescaled_vertices = rescale_positions(vertices, bounds)

with open('output.terrain', 'wb') as f: quantized_mesh_encoder.encode(f, rescaled_vertices, triangles)

Meshio

Alternatively, you can save to a variety of mesh formats usingmeshio:

from pydelatin import Delatin import meshio

tin = Delatin(terrain, max_error=30) vertices, triangles = tin.vertices, tin.triangles

cells = [("triangle", triangles)] mesh = meshio.Mesh(vertices, cells)

Example output format

Refer to meshio documentation

mesh.write('foo.vtk')

Martini or Delatin?

Two popular algorithms for terrain mesh generation are the **"Martini"**algorithm, found in the JavaScript martini library and the Pythonpymartini library, and the "Delatin" algorithm, found in the C++ hmm library, this Python pydelatin library, and the JavaScriptdelatin library.

Which to use?

For most purposes, use pydelatin over pymartini. A good breakdown from a Martini issue:

Martini:

• Only works on square 2^n+1 x 2^n+1 grids.
• Generates a hierarchy of meshes (pick arbitrary detail after a single run)
• Optimized for meshing speed rather than quality.

Delatin:

• Works on arbitrary raster grids.
• Generates a single mesh for a particular detail.
• Optimized for quality (as few triangles as possible for a given error).

Benchmark

The following uses the same dataset as the pymartinibenchmarks, a 512x512 pixel heightmap of Mt. Fuji.

For the 30-meter mesh, pydelatin is 25% slower than pymartini, but the mesh is much more efficient: it has 40% fewer vertices and triangles.

pydelatin is 4-5x faster than the JavaScript delatin package.

Python

git clone https://github.com/kylebarron/pydelatin cd pydelatin pip install '.[test]' python bench.py

mesh (max_error=30m): 27.322ms
vertices: 5668, triangles: 11140

mesh (max_error=1m): 282.946ms
mesh (max_error=2m): 215.839ms
mesh (max_error=3m): 163.424ms
mesh (max_error=4m): 127.203ms
mesh (max_error=5m): 106.596ms
mesh (max_error=6m): 91.868ms
mesh (max_error=7m): 82.572ms
mesh (max_error=8m): 74.335ms
mesh (max_error=9m): 65.893ms
mesh (max_error=10m): 60.999ms
mesh (max_error=11m): 55.213ms
mesh (max_error=12m): 54.475ms
mesh (max_error=13m): 48.662ms
mesh (max_error=14m): 47.029ms
mesh (max_error=15m): 44.517ms
mesh (max_error=16m): 42.059ms
mesh (max_error=17m): 39.699ms
mesh (max_error=18m): 37.657ms
mesh (max_error=19m): 36.333ms
mesh (max_error=20m): 34.131ms

JS (Node)

This benchmarks against the delatin JavaScript module.

git clone https://github.com/kylebarron/pydelatin cd test/bench_js/ yarn wget https://raw.githubusercontent.com/mapbox/delatin/master/index.js node -r esm bench.js

mesh (max_error=30m): 143.038ms
vertices: 5668
triangles: 11140

mesh (max_error=0m): 1169.226ms
mesh (max_error=1m): 917.290ms
mesh (max_error=2m): 629.776ms
mesh (max_error=3m): 476.958ms
mesh (max_error=4m): 352.907ms
mesh (max_error=5m): 290.946ms
mesh (max_error=6m): 240.556ms
mesh (max_error=7m): 234.181ms
mesh (max_error=8m): 188.273ms
mesh (max_error=9m): 162.743ms
mesh (max_error=10m): 145.734ms
mesh (max_error=11m): 130.119ms
mesh (max_error=12m): 119.865ms
mesh (max_error=13m): 114.645ms
mesh (max_error=14m): 101.390ms
mesh (max_error=15m): 100.065ms
mesh (max_error=16m): 96.247ms
mesh (max_error=17m): 89.508ms
mesh (max_error=18m): 85.754ms
mesh (max_error=19m): 79.838ms
mesh (max_error=20m): 75.607ms

License

This package wraps @fogleman's hmm, a C++ library that is also MIT-licensed.