Author Martin Dobias (@wonder-sk), Peter Petrik (@PeterPetrik)
Contact wonder dot sk at gmail dot com, zilolv at gmail dot com
Maintainer @PeterPetrik, @wonder-sk
Version QGIS 3.2 or 3.4
Summary
This QEP proposes implementation of a new map layer type: in addition to raster and vector layers,
there will be mesh layer supporting display of data on structured or unstructured meshes (grids).
The idea is to introduce foundations to QGIS so that it is possible to create visualizations like this one (done with Crayfish plugin):
What is a mesh?
In our context, a mesh is a collection of vertices, edges and faces in 2D or 3D space:
vertices - XY(Z) points (in the layer's coordinate reference system)
edges - connect pairs of vertices
faces - sets of edges forming a closed shape - typically triangles or quadrilaterals (quads), rarely polygons with higher number of vertices
Mesh gives us information about the spatial structure. In addition to the mesh we have datasets that assign a value to every vertex. For example, ice cap thickness at particular moment of time. A single file may contain multiple datasets - typically multiple quantities (e.g. water depth, water flow) that may be varying in time (time being represented in discrete timesteps, so each quantity may have N arrays, one for each timestep). Datasets do not have to vary in time (e.g. maximum water depth over the whole simulation).
Here is an example of a triangular mesh with numbered vertices:
The following table gives an idea what information is stored in datasets. Table columns represent indices of mesh vertices, each row represents one dataset. The first two are scalar datasets, the latter two are datasets with 2D vectors.
1
2
3
...
13
Water depth at time=0s
5
5
5
...
2
Water depth at time=60s
6
5
3
...
4
Water flow at time=0s
[1,2]
[2,2]
[3,2]
...
[1,2]
Water flow at time=60s
[3,2]
[3,2]
[2,2]
...
[4,2]
In some cases datasets assign values to faces or edges instead of assigning values to vertices.
We can visualize the data by assigning colors to values (similarly to how it is done with "Singleband pseudocolor" raster rendering) and interpolating data between vertices according to the mesh topology. It is common that some quantities are 2D vectors rather than being simple scalar values (e.g. wind direction). For such quantities it is very desired to display arrows indicating vector direction.
When would I use it?
Most often this kind of representation is used when preparing data for simulation software or when viewing results of physical simulations, typically for meteorology, oceanography, hydrological or hydraulic models. All computation in such software is done on meshes, with values (physical quantities) usually stored in vertices (less commonly in edges or faces). Results usually comprise of various quantities (e.g. wind speed, water depth) which may be also time-varying (e.g. calculated water flow estimates in 5 minute intervals).
Some of the modelling software packages are free and open source (e.g. AnuGA, EPANET), there are some freeware packages (e.g. Basement, HEC-RAS) as well as many commercial pieces of software.
Do we really need this in QGIS? Maybe raster and vector layers are good enough?
It will be very useful to have native support for this data representation. Mesh-based data cannot be properly represented either as vector or raster layers. Vector data in QGIS use "simple features" representation which looses topological relationships between vertices, edges and faces, moreover we would need potentially large number of attributes for features. Efficient access to data is also a concern - dataset sizes can easily get to gigabytes. Reusing existing vector data support would be therefore impractical and complicated - just like as if we wanted to use ordinary vector layers for point clouds: in theory it is possible, but the nature of the data is quite different.
Raster layers are not an answer either. Sometimes users take mesh-based data and export those to raster grid files, but this always comes at the expense of loss of information and it only makes sense for visualization of results, it does not allow manipulation of the raw data. Rasters in fact can be thought of as a special case of meshes - having all vertices in a grid with regular spacing and all faces being quads.
Mesh layers also come useful when dealing with weather data (historical or predicted). Although such data are commonly available as raster grids (with some formats such as GRIB being supported by GDAL), interpolation and rendering of vector data adds extra value when visualizing such datasets.
To summarize, native support for mesh data opens QGIS to a whole new set of use cases.
Isn't this is already handled by plugins?
Only to some degree. There is Crayfish plugin that deals with mesh data, but it some issues when it comes to distribution of it: the data access and rendering are written in C++ for efficiency which means that it needs users to either manually compile the c++ library from source code or to download pre-built binaries. Once support for mesh layers is available in QGIS 3, we would like to update Crayfish to become Python-only plugin making use of mesh layers, still providing support for various mesh formats and adding extra GUI functionality.
There is also Meshlayer plugin from Oslandia which is written in Python and uses OpenGL for rendering, however it has various limitations (only supports triangular meshes, no support for element-centered data, ...)
Proposed Solution
A mesh layer (QgsMeshLayer) consists of the following main components:
data provider - just like how providers are used for vector and raster layers, this is an abstraction for access to mesh structure and to data on top of the mesh.
renderer - takes care of rendering the mesh layer to map images according to the configuration specified by the user
cache - since fetching data from data provider may be slow, a cache is used to keep some data in memory for fast access
Data provider
There may be multiple data providers available for different file formats, but one layer will always point to a single data provider (QgsMeshDataProvider)
The main responsibilities of a data provider are:
return mesh structure (list of nodes, edges and faces)
return metadata about datasets (similar to getting a list of raster bands and their metadata)
return a window of data from a dataset
In the initial implementation we assume that data providers will be read-only. In the future this may change and there may be calls to modify mesh structure or add/remove/modify datasets.
Renderer
Mesh layer renderer (QgsMeshLayerRenderer) is responsible for drawing map of given map extent.
It is derived from QgsMapLayerRenderer and it gets called from QGIS map rendering engine.
Renderer renders data from the active dataset - users will be able to choose which dataset is the active one.
Rendering consists of three steps and the user should be able to configure which steps will be used:
rendering of contours. This interpolates values from the active dataset and assigns a color to each pixel covered by the mesh. For vector datasets, magnitudes of vectors are used as the values.
rendering of vectors. This draws arrow symbols with appropriate scaling for data from the active dataset. Obviously this is only possible for vector datasets.
rendering of mesh. The active dataset is not used here - only mesh structure gets rendered, optionally with labels.
The rendering algorithm consists of the following steps:
Given map extent, use spatial index to figure out which elements of the mesh are needed for rendering
Using the list of elements, figure out which data blocks will be needed from the active dataset.
Try to fetch the required data blocks from the cache. If the blocks are not available in the cache, get them from the data provider and temporarily store in the cache.
Walk elements of the mesh in map extent and render one by one (first contours, then vectors, then mesh).
Cache
In order to make sure that the data access is fast enough, we will need to keep a cache. It will consist of the following parts:
Mesh structure. This data structure will be accessed very often and it is relatively small so it can be cached as a whole.
Data blocks. Access to the data from data providers may be relatively slow and very often the map renderer will need access to the same or similar subset of data over time. At the same time the total amount of data stored in data blocks may be large (in the order of gigabytes), so this part of the cache will have to be limited with a maximum cache size and data blocks would be replaced with the least recently used (LRU) strategy.
"Derived" triangular mesh. Used to speed up and simplify rendering, as well as providing mesh for rendering in 3D map view. More details below.
Spatial index. For map rendering and layer identification we need fast spatial queries ("which mesh elements are in this rectangle").
Derived mesh
Reasons why we need derived triangular mesh:
mesh structure in general may contain triangles, quadrilaterals or even polygons with higher number of vertices. Interpolation on shapes other than triangles is more expensive/difficult and for rendering in 3D we need to have a triangular mesh anyway.
when rendering 1D elements (edges), we need to turn them into quads according to their thickness (and quads are turned into a pair of triangles).
when map CRS is different from the mesh layer CRS, we need to do on-the-fly reprojection. Keeping derived mesh in the map CRS saves us from reprojecting on every rendering.
level of detail - when rendering a large area, we can do simplification and use fewer triangles for rendering, for smaller area we may want to split elements such as quads into more than two triangles for better rendering quality.
Derived mesh is kept for particular map settings parameters (especially scale and CRS). Whenever the map settings are changed, the derived mesh needs to be invalidated. The assumption is that often these map settings parameters stay the same over multiple rendering calls.
GUI
Loading of mesh layers should be possible via the integrated browser panel and/or through the unified add layer dialog.
Once a mesh layer is loaded, it will have a map layer properties dialog similar to the ones for vector/raster layers, with renderer configuration similar to the GUI mockups above.
Supported data formats
Out of the box, we would like to support few generic file formats that are useful for wide range of uses and do not introduce any additional dependencies, e.g. GRIB format (for weather data). Support for other formats may be added by plugins.
Affected files
Most of the development will be done in new files (e.g. src/core/mesh/qgsmeshlayer*.cpp).
We will need to add a new layer type in QgsMapLayer and add support for it in various bits of QGIS code.
Q/A
Would it be possible to implement support for any custom format?
Yes, by implementation of subclass of QgsMeshDataProvider and registering it in the list of providers available. This could be done in Python plugins.
How will you handle time component?
This QEP intentionally tries to stay away from dealing with time component as that is quite a large topic itself. We assume that plugins may introduce convenience functionality for handling of the temporal nature of mesh layers (e.g. easy moving between time steps, animation, export of videos). In the future we would like to look into having a separate QEP to cover time component within QGIS for all types of map layers.
Would it be possible to visualize mesh data in 3D?
Yes, probably not from the very beginning, but it should be possible at some point.
Would it be possible to load very large files with results?
Yes, data provider does not store any data internally in memory. The mesh layer cache will gather data from provider when needed. It will be configurable (e.g. limit for memory usage) so the performance should be good even for large files.
Can I carry out Processing on my mesh layer?
We may provide some basic Processing modules for conversion of mesh layers to raster/vector layers. For advanced processing (e.g. mesh calculator, time manipulation) you can use Crayfish or develop a python plugin.
Is it the end of Crayfish?
No, at least not in the short term. Crayfish will just get rid of the C++ part (and become pure Python plugin) and serve as a time manager with some additional functionality (plots, animations). But if we manage to implement support for time management in QGIS and integrate other parts of it as well, maybe there will not be much need for it anymore...
wonder-sk
commented
6 years ago
QGIS Enhancement: Unstructured Mesh Layer
Date 2018/03/28
Author Martin Dobias (@wonder-sk), Peter Petrik (@PeterPetrik)
Contact wonder dot sk at gmail dot com, zilolv at gmail dot com
Maintainer @PeterPetrik, @wonder-sk
Version QGIS 3.2 or 3.4
Summary
This QEP proposes implementation of a new map layer type: in addition to raster and vector layers, there will be mesh layer supporting display of data on structured or unstructured meshes (grids).
The idea is to introduce foundations to QGIS so that it is possible to create visualizations like this one (done with Crayfish plugin):
What is a mesh?
In our context, a mesh is a collection of vertices, edges and faces in 2D or 3D space:
Mesh gives us information about the spatial structure. In addition to the mesh we have datasets that assign a value to every vertex. For example, ice cap thickness at particular moment of time. A single file may contain multiple datasets - typically multiple quantities (e.g. water depth, water flow) that may be varying in time (time being represented in discrete timesteps, so each quantity may have N arrays, one for each timestep). Datasets do not have to vary in time (e.g. maximum water depth over the whole simulation).
Here is an example of a triangular mesh with numbered vertices:
The following table gives an idea what information is stored in datasets. Table columns represent indices of mesh vertices, each row represents one dataset. The first two are scalar datasets, the latter two are datasets with 2D vectors.
In some cases datasets assign values to faces or edges instead of assigning values to vertices.
We can visualize the data by assigning colors to values (similarly to how it is done with "Singleband pseudocolor" raster rendering) and interpolating data between vertices according to the mesh topology. It is common that some quantities are 2D vectors rather than being simple scalar values (e.g. wind direction). For such quantities it is very desired to display arrows indicating vector direction.
When would I use it?
Most often this kind of representation is used when preparing data for simulation software or when viewing results of physical simulations, typically for meteorology, oceanography, hydrological or hydraulic models. All computation in such software is done on meshes, with values (physical quantities) usually stored in vertices (less commonly in edges or faces). Results usually comprise of various quantities (e.g. wind speed, water depth) which may be also time-varying (e.g. calculated water flow estimates in 5 minute intervals).
Some of the modelling software packages are free and open source (e.g. AnuGA, EPANET), there are some freeware packages (e.g. Basement, HEC-RAS) as well as many commercial pieces of software.
Do we really need this in QGIS? Maybe raster and vector layers are good enough?
It will be very useful to have native support for this data representation. Mesh-based data cannot be properly represented either as vector or raster layers. Vector data in QGIS use "simple features" representation which looses topological relationships between vertices, edges and faces, moreover we would need potentially large number of attributes for features. Efficient access to data is also a concern - dataset sizes can easily get to gigabytes. Reusing existing vector data support would be therefore impractical and complicated - just like as if we wanted to use ordinary vector layers for point clouds: in theory it is possible, but the nature of the data is quite different.
Raster layers are not an answer either. Sometimes users take mesh-based data and export those to raster grid files, but this always comes at the expense of loss of information and it only makes sense for visualization of results, it does not allow manipulation of the raw data. Rasters in fact can be thought of as a special case of meshes - having all vertices in a grid with regular spacing and all faces being quads.
Mesh layers also come useful when dealing with weather data (historical or predicted). Although such data are commonly available as raster grids (with some formats such as GRIB being supported by GDAL), interpolation and rendering of vector data adds extra value when visualizing such datasets.
To summarize, native support for mesh data opens QGIS to a whole new set of use cases.
Isn't this is already handled by plugins?
Only to some degree. There is Crayfish plugin that deals with mesh data, but it some issues when it comes to distribution of it: the data access and rendering are written in C++ for efficiency which means that it needs users to either manually compile the c++ library from source code or to download pre-built binaries. Once support for mesh layers is available in QGIS 3, we would like to update Crayfish to become Python-only plugin making use of mesh layers, still providing support for various mesh formats and adding extra GUI functionality.
There is also Meshlayer plugin from Oslandia which is written in Python and uses OpenGL for rendering, however it has various limitations (only supports triangular meshes, no support for element-centered data, ...)
Proposed Solution
A mesh layer (QgsMeshLayer) consists of the following main components:
data provider - just like how providers are used for vector and raster layers, this is an abstraction for access to mesh structure and to data on top of the mesh.
renderer - takes care of rendering the mesh layer to map images according to the configuration specified by the user
cache - since fetching data from data provider may be slow, a cache is used to keep some data in memory for fast access
Data provider
There may be multiple data providers available for different file formats, but one layer will always point to a single data provider (QgsMeshDataProvider)
The main responsibilities of a data provider are:
In the initial implementation we assume that data providers will be read-only. In the future this may change and there may be calls to modify mesh structure or add/remove/modify datasets.
Renderer
Mesh layer renderer (QgsMeshLayerRenderer) is responsible for drawing map of given map extent. It is derived from QgsMapLayerRenderer and it gets called from QGIS map rendering engine.
Renderer renders data from the active dataset - users will be able to choose which dataset is the active one.
Rendering consists of three steps and the user should be able to configure which steps will be used:
rendering of contours. This interpolates values from the active dataset and assigns a color to each pixel covered by the mesh. For vector datasets, magnitudes of vectors are used as the values.
rendering of vectors. This draws arrow symbols with appropriate scaling for data from the active dataset. Obviously this is only possible for vector datasets.
rendering of mesh. The active dataset is not used here - only mesh structure gets rendered, optionally with labels.
The rendering algorithm consists of the following steps:
Cache
In order to make sure that the data access is fast enough, we will need to keep a cache. It will consist of the following parts:
Mesh structure. This data structure will be accessed very often and it is relatively small so it can be cached as a whole.
Data blocks. Access to the data from data providers may be relatively slow and very often the map renderer will need access to the same or similar subset of data over time. At the same time the total amount of data stored in data blocks may be large (in the order of gigabytes), so this part of the cache will have to be limited with a maximum cache size and data blocks would be replaced with the least recently used (LRU) strategy.
"Derived" triangular mesh. Used to speed up and simplify rendering, as well as providing mesh for rendering in 3D map view. More details below.
Spatial index. For map rendering and layer identification we need fast spatial queries ("which mesh elements are in this rectangle").
Derived mesh
Reasons why we need derived triangular mesh:
Derived mesh is kept for particular map settings parameters (especially scale and CRS). Whenever the map settings are changed, the derived mesh needs to be invalidated. The assumption is that often these map settings parameters stay the same over multiple rendering calls.
GUI
Loading of mesh layers should be possible via the integrated browser panel and/or through the unified add layer dialog.
Once a mesh layer is loaded, it will have a map layer properties dialog similar to the ones for vector/raster layers, with renderer configuration similar to the GUI mockups above.
Supported data formats
Out of the box, we would like to support few generic file formats that are useful for wide range of uses and do not introduce any additional dependencies, e.g. GRIB format (for weather data). Support for other formats may be added by plugins.
Affected files
Most of the development will be done in new files (e.g. src/core/mesh/qgsmeshlayer*.cpp).
We will need to add a new layer type in QgsMapLayer and add support for it in various bits of QGIS code.
Q/A
Would it be possible to implement support for any custom format?
Yes, by implementation of subclass of QgsMeshDataProvider and registering it in the list of providers available. This could be done in Python plugins.
How will you handle time component?
This QEP intentionally tries to stay away from dealing with time component as that is quite a large topic itself. We assume that plugins may introduce convenience functionality for handling of the temporal nature of mesh layers (e.g. easy moving between time steps, animation, export of videos). In the future we would like to look into having a separate QEP to cover time component within QGIS for all types of map layers.
Would it be possible to visualize mesh data in 3D?
Yes, probably not from the very beginning, but it should be possible at some point.
Would it be possible to load very large files with results?
Yes, data provider does not store any data internally in memory. The mesh layer cache will gather data from provider when needed. It will be configurable (e.g. limit for memory usage) so the performance should be good even for large files.
Can I carry out Processing on my mesh layer?
We may provide some basic Processing modules for conversion of mesh layers to raster/vector layers. For advanced processing (e.g. mesh calculator, time manipulation) you can use Crayfish or develop a python plugin.
Is it the end of Crayfish?
No, at least not in the short term. Crayfish will just get rid of the C++ part (and become pure Python plugin) and serve as a time manager with some additional functionality (plots, animations). But if we manage to implement support for time management in QGIS and integrate other parts of it as well, maybe there will not be much need for it anymore...
Backwards Compatibility
Not applicable
Votes
(required)