search

mapbox / martini

A JavaScript library for real-time RTIN terrain mesh generation
https://observablehq.com/@mourner/martin-real-time-rtin-terrain-mesh
ISC License
612 stars 41 forks source link

alternative initial split ? #4

Closed andreasplesch closed 5 years ago

andreasplesch commented 5 years ago

Thanks, very intriguing. After the initial split, the refinement should be unique because there is only one way to split a right-angle triangle into two right-angle triangles by splitting the diagonal. So the resulting mesh can be reproduced given the same input DEM and max. error.

However, there are two options for the initial split. Currently, the diagonal from 0,0 to sizeX, sizeY is used for the initial split (https://github.com/mapbox/martini/blob/master/index.js#L159). Equally valid would be an alternative, initial split: from 0, sizeY to sizeX, 0.

In some cases, the alternative, initial split may lead to a more optimized mesh, eg. fewer triangles and there may be situations where exploring both options would be worth the (doubled) cost. Perhaps this is discussed in the original publication. In most cases, it should not matter much. It may be possible to prove that at most only a few triangles can be saved.

Consider adding an option to choose which initial split to use ? Then a user could explore both if wanted, and choose one.

andreasplesch commented 5 years ago

Looking just at the figures of https://www.cs.ubc.ca/~will/papers/rtin.pdf, there is also the option to divide the initial square into four triangles, using the center as an additional vertex. This would avoid the ambiguity of having two alternatives for the initial split, probably a benefit. That would require a minimum size of 3 rather than 1 which should not have practical consequences.

andreasplesch commented 5 years ago

Since the second split should generate the exact same four triangles for both alternatives, it actually should not matter at all which initial split to choose. So I think I can close this.

andreasplesch commented 5 years ago

yeah, tested in fork. sorry for the noise.

andreasplesch commented 5 years ago

After the second split there should be no difference between the two initial splits. Unless the second split is not necessary which is essentially never the case anyways. Just for completeness.