You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
libraries available in C++ (CGAL) and Fortran (STRIPACK) with fast implementations of 2D Delaunay triangulation on the sphere or 3D triangulation (CGAL)
scales well to millions or billions of mesh nodes
support for basic spatial queries (find triangle that contains a query point)
Cons:
overkill for (quasi-)uniform resolution and simple geometries
memory expensive (need to store the explicit topology, i.e., triangle node indices)
we need to implement custom logic on top of the features provided by the triangulation libraries, e.g.,
generate an initial set of mesh nodes on the sphere with quasi-uniform resolution
iterate through each neighbors of a node
extract voronoi cells and compute their areas (or use tricks with rough approximations)
exclude or mask ocean nodes
the custom implementations mentioned above usually imply performance overhead (additional data structures stored in memory, pre-computation, etc.) that might not always scale well or that would require optimization effort
A Discrete Global Grid System (DGGS) can be roughly defined as a partitioning or tessellation of the entire Earth's surface into a finite number of "cells" or "zones". The shape and the properties of these cells generally vary from one DGGS to another. Most DGGSs are also hierarchical, i.e., the cells are arranged recursively on multiple levels or resolutions.
computation and memory friendly: no triangulation required, no need to store explicit topology in memory
should scale well to millions or billions of grid nodes
(nearly-)all batteries-included (by design!) for our case:
API to iterate over the node neighors (*)
API to get cell areas (*)
basic to more advanced spatial queries (e.g., find the cell containing a point, find all cells containing or intersecting an arbitrary polygon, etc.)
no need to manually generate grid nodes quasi-uniformly distributed on the sphere, we just need to pick a level / resolution (integer)
domain masking or sub-domain selection is straightforward: we just need (resp.) a bollean array or an integer array of grid node indices.
Fixed size neighborhood (with some exceptions at a few nodes), which makes cheaper cache data structures if needed
(*) Those operations are computationally cheap by design, although I need to check that it is the case. Pre-computing / caching is still possible for speed-up (and probably needed for handling sub-domain boundary limits)
Cons:
less popular than triangular meshes.
Proposed strategy
Choose the DGGS option and implement in Fastscapelib a global_grid class that is built on top of healpix.
Pros of using healpix in our application:
the Healpix grid cells on the same level (resolution) all have an equal area
it has a C++ API and also efficient Python/Numpy bindings, both are packaged on conda-forge
pretty large comunnity (especially in astronomy / astrophysics)
Limitations of using healpix in our application:
cell shape and grid node neighbors on diagonals. Other DGGSs may have better cell shape (like hexagons in H3). Not a big deal, though, we're still heavily using raster grids in LEMs with the same diagonal limitations
distances between a cell and its neighbors varies depending on the node location: we either can use a rough approximation or need to (pre-)compute it explicitly
not sure Healpix C++ provides any CMake configuration, not a big deal but more work for configuring it with Fastscapelib.
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
-
Problem statement
Run Fastscape on a global, planetary domain with the following set of requirements:
Spherical triangular mesh
(source: https://doc.cgal.org/latest/Triangulation_on_sphere_2)
Pros:
Cons:
Discrete Global Grid System (DGGS)
(source: https://healpix.sourceforge.io)
A Discrete Global Grid System (DGGS) can be roughly defined as a partitioning or tessellation of the entire Earth's surface into a finite number of "cells" or "zones". The shape and the properties of these cells generally vary from one DGGS to another. Most DGGSs are also hierarchical, i.e., the cells are arranged recursively on multiple levels or resolutions.
Pros:
(*) Those operations are computationally cheap by design, although I need to check that it is the case. Pre-computing / caching is still possible for speed-up (and probably needed for handling sub-domain boundary limits)
Cons:
Proposed strategy
Choose the DGGS option and implement in Fastscapelib a
global_grid
class that is built on top of healpix.Pros of using healpix in our application:
Limitations of using healpix in our application:
Beta Was this translation helpful? Give feedback.
All reactions