Join GitHub today
GitHub is home to over 31 million developers working together to host and review code, manage projects, and build software together.Sign up
Unstructured Mesh Layers #119
QGIS Enhancement: Unstructured Mesh Layer
Contact wonder dot sk at gmail dot com, zilolv at gmail dot com
Version QGIS 3.2 or 3.4
This QEP proposes implementation of a new map layer type: in addition to raster and vector layers,
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).
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, ...)
A mesh layer (QgsMeshLayer) consists of the following main components:
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.
Mesh layer renderer (QgsMeshLayerRenderer) is responsible for drawing map of given map extent.
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:
The rendering algorithm consists of the following steps:
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:
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.
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.
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.
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...
Hi, nice QEP, very glad to see this coming into QGIS !
Could you elaborate on the limitations you found in the MeshLayer Plugin ? We would like to be sure that all cases handled by this plugin would be handled as well by native support.
Do you plan to use OpenGL rendering as well for mesh layers ? It proved to be really efficient for the plugin.
@vmora will certainly react to this. We are really interested in this area of work and have various use cases. We would for sure be able to take part in the development, should funding be assured.
MeshLayer plugin limitations to my best knowledge from reading the code (I may be wrong):
Regarding OpenGL rendering for 2D maps, I am a bit skeptical. My breakdown of pros/cons would be:
If rendering of a mesh layer on CPU takes 50ms and rendering with OpenGL is done in 1ms, then I would probably argue that the disadvantages are greater than the performance benefit...
@rouault Yes that may as well happen at some point. I would prefer to do a gradual approach with implementation directly in QGIS first and then if there is enough interest, move the low-level code and drivers to a separate library...
MDAL would be actually a great name as it starts with my initials :-D The next thing would be to figure out whether to pronounce it "em-dal" or "moodle" !
Sure. You'll have to consider the licensing of those parts from the beginning though. Not wanting to start a flame war about licensing, but a GPL'ed MDAL could limit its audience.
I think the vision of Martin is a great value for this development!
This is the first clear manifesto against the confines of traditional GIS that I've seen in the public domain, thank you! I hope this gets traction beyond the scope of QGIS, it's a foundation needed by many. (I definitely support @rouault point about that, QGIS is awesome but it's not the whole world - it is a wide audience though, so long-term it's the right place to get support for truly general tools).
Absolutely agreed. However as of now (to my knowledge) there is no such open source library to support I/O, rendering and editing of this kind of data.
Don't get me wrong - I have nothing against vector simple features! That representation is great for vector layers, it is just not the best representation to use for meshes.
I believe this is a meta-topic of the highest order, it is criticized in the small in different contexts, has pockets in various places and only by a large-enough unification, a truly "not-just-simple features" with enough key players will it get traction soon.
This discussion is relevant: https://lists.osgeo.org/pipermail/gdal-dev/2017-October/047464.html and there are many others. If anyone wants to pursue this topic beyond this context I'm keen ;) My small experiment is here: https://github.com/hypertidy/silicate and I'll be exploring this proposal in detail, it's the most interesting big picture topic for spatial I've seen in open source.
@wonder-sk first of all: Great QEP!
I've been working mostly on simulation related projects for the past 4 years. I resorted to a lot of "ad hoc" solutions. Meshlayer tries to be a bit more general (it's used in several projects) but it's just a plugin, and a rather small one at that:: a thousand lines of python. Just a word about the limitations that I believe it has not::
Limitations really it has: does not implement caching of data and does not have spatial index. Those limitation are structural (i.e. I'm not planing to change that) : the full mesh is sent to the graphic card, only values are fetched dynamically. Usually simulation meshes fit in memory, so not a big deal for my use case. But for a general GIS layer, this is not acceptable.
Concerning OpenGL 2D rendering:
Here is the key issue for me: if the CPU can do that in less than 20ms (50Hz) fair enough, if not, then you need something else. Animation is the most natural way to understand time variation, and IMO a must-have feature for post-processing simulation results.
MDAL is certainly appealing. I don't have a strong opinion on that, but...
Indeed, but it would be great to have the mesh layer being loaded as a point layer, a polygon layer and a raster layer (with infinite resolutions). The arrow representation would benefit raster too.
So MDAL could do just that: take a mesh format and expose 3 pseudo-datasources.
@vmora Many thanks for your comments.
Regarding meshlayer plugin:
In terms of memory consumption, my assumption in the QEP is that mesh structure always fits into memory, but datasets do not have to.
Regarding OpenGL rendering:
Loading mesh layer as point/polygon/raster layer: for this I would like to use Processing toolbox, where users could take a mesh layers as input and convert them to whatever representation they need (in fact, Crayfish already supports such algorithm: export nodes, export elements, export data as raster, export contour isolines).
It works for MeshLayer, the other layers are cached (as long as you don't want pan/zoom + animate).
It wouldn't help if the bottleneck is data fetch, which occurs with every frame.
Well, I'm not sure that the extend of what I was thinking was properly expressed in my short sentence.
What the mesh represents is a continuous scalar or vector field (node values + elements interpolation), and I think raster really do the job to represent fields. The only real difference is that you can zoom indefinitely on the mesh representation, but bottom line you are not interested in a resolution that is higher than your viewport (or a multiple of that for eg. antialiasing).
Classified colors is something we already have for rasters. On the other hand, the arrow field representation would be really nice to have for raster layers (not just mesh layers), same holds for nicer classified and continuous colors.
The basic idea is to implement a rasterizer in MDAL (that has more or less the same API as GDAL except for the max resolution). That rasterizer gives you the interpolated field values (one band for scalar, 2/3 for vector fields) at the desired resolution. Then the only thing that need improvements in QGIS is the raster symbology.
So what I propose, with 3 views on the same datasource doesn't involve brand new concepts in GIS. Of course we won't benefit from the new concepts, eg. processing won't see the "graph" aspect of the mesh (a 4th view on the same thing)... but do we truly need the new concepts ?
@vmora Thanks for elaborating on that - now I recall someone from Oslandia mentioned such idea to me longer time ago (either Hugo or VincentP or you?) and they said they would like to have mesh rasterizer driver in GDAL to be able to reuse QGIS raster renderers. Did you pursue that idea any further or were there some obstacles that were difficult to overcome?
Having such mesh rasterizer in QGIS would be a good solution to avoid duplication of some rendering code. And having vector field renderer shared with rasters would be nice too (so that raster grid datasets would not need to be opened as mesh layers).
I will think about this approach a bit more to see if there are any complications coming from it. At the same time, having the possibility to directly access the mesh structure (graph) and raw datasets could be still useful (e.g. for mesh calculator or for mesh structure/data editing).
@wonder-sk Thanks for this, it is (to me) very interesting and I learn from your thorough write ups.
I sometimes get grib files, and either open them with QGIS/GDAL, or your Crayfish plugin. I wonder if I understand correctly that the first QgsMeshDataProvider implementation will probably be GDAL, followed by a 'native' QGIS one, being your work in Crayfish?
As grib and other meteo formats often contain TimeRanges, I wonder if the QgsMeshLayer or QgsMeshDataProvider will have machinery to handle those. Actually I would favour native handling of time-ranges in all layers/providers :-)
@rduivenvoorde The idea is that GDAL-based data provider would be included to support GRIB and possibly other data sources. Crayfish would introduce another provider (or a whole bunch of providers - one for each format).
Regarding time steps vs time ranges, at this point the mesh layers / data providers do not really care about that - they work with a bunch of datasets that may or may not contain some time information in metadata. I hope one day there will be a nice QEP for time dimension handling and that's where time support should get formalized.
As said by Vincent the "MDAL" library could offer a raster view of the Mesh for display ( with OpenGL process to render as raster), as well as vector views for points ( middle of cells or nodes) and edges. This would allow for mesh calculator or mesh structure editing too.
What may be needed is a graph structure support in QGIS : this would also be useful to support topology editing, like the PostGIS one. But it could be added later as another view on the mesh layer.
Did you find time to think about such an approach ?
Just earlier today we have had a discussion and decided to go ahead with MDAL library. The initial goals are to provide data structures for representation of mesh data and support for drivers - following the model of GDAL/OGR. It is meant to be a C++ library, MIT licensed.
In the first stage I would consider MDAL to be just a simple (read-only) data access library, without caching, indexing or rasterization support - all those things would be initially handled inside QGIS. Using Vincent's suggestion, for scalar values we would rasterize mesh data and then use ordinary raster pseudo-color renderer. For vector values we want to create a generic vector field renderer that may be reused for vector, raster or mesh data.
Once the basics are implemented inside MDAL, we can start looking into further topics:
@@> why not make MDAL part of gdal ?
On a pure technical point of view, there's the QT dependency question ( lutraconsulting/MDAL#1 ) that would be a no-go for GDAL (or that would make the MDAL part necessarily an optionally compiled component of GDAL, which would in particular mean that a lot of packaging wouldn't compile MDAL functionality)
This issue left aside, that might make sense. We have already added recently the GNM (Geographical Network Model) abstraction in GDAL, so why not the mesh one ?
There are pros & cons to being integrated or standalone:
And you forgot the best "pro" argument : if MDAL is part of GDAL, we would favor @rouault 's contributions, and that would make a real difference :-)
Thanks, didn't know about OpenMesh!
I appreciate @rapidlasso will know much more about the details here, but here's my list.
The other candidates I know of for constrained and/or conforming Deluanay triangulation (there aren't many so I appreciate any pointers to others)
Commercially the ones I'm familiar with are
There are other "lower quality mesh" approaches with ear clipping, this is the best one I've tried:
To comment on the libraries mentioned here:
OpenMesh (which seems similar to VCGlib used by MeshLab) is geared towards mesh representation data structures and mesh processing algorithms. This is different from what we are trying to do. We do not need mesh processing algorithms and sophisticated data structures - we are not going to use any of it. We need mesh just to define domain of data that are going to be displayed on top of it. We need drivers for various formats used in meteorology, oceanography, flood modelling simulators and other similar data sources.
We also most likely will not need libraries for triangulation: typical domain is either a triangular mesh or a mesh with convex polygons which are trivial to triangulate. (And in QGIS 3D we already make use of poly2tri where triangulation is needed.)
referenced this issue
Apr 19, 2018
Hi, nice QEP, a big +1 for MDAL!
What about to develop the
If the Mesh provides a stream or iterator of triangles or faces, instead of arrays of vertices or faces, MDAL could provide a huge set of features to render. Something similar to
QGIS could draw huge sets of TIN's from LiDAR repositories, etc. A similar concept to this.
Thanks for the pointer to our "streaming mesh" work. I also like to advocate against - yet another - two array based mesh representation but suggest to consider one that exists of a stream of 3 events: Vertex, Polygon, Finalization. A more format specific reference to such a "Streaming Mesh" is this one here. It exlains the concept of storing (or exposing an API to) a mesh that allows true streaming access. Such an access has two components: (1) vertices and triangles/polygons can appear interleaved in the sense that vertices just need to be loaded/introduced when the the first triangle/polygon references them and not all of them upfront (such as in many other indexed formats) and (2) there is "finalization" information that tells us when vertices are no longer needed (and can be safely deallocated). Every existing indexed format implicitly fits this model and simply has the worst-case "stream width" which refers to the maximum number of vertices that are active (introduced and not finalized) as the mesh streams by. For the standard indexed mesh format such as PLY all vertices are loaded/introduced first and are finalized only after the last triangle/polygon was read. More details (abstract and paper) are here: Streaming Meshes. Any actual implementation will require only tiny API changes compared to a non-streaming approach. But the practical benefits can be huge as meshes grow in size.
For your purpose I could imagine that operating in increments of single vertices and triangles (as done in the sample Streaming Mesh format used by LAStools BLAST engine) might be too granular. But here an as small as possible example. This is our SMA (Streaming Mesh Ascii) format which is also a valid OBJ file. This is a simple tetrahedron.
The interleaving is easily seen. After the first three vertices we already can specify the first face. Then comes the fourths and last vertex. Hence now the next three (here the final three) faces can be specified as all needed vertices have been introduced in the stream.
Now notice the negative reference '-4' in the third face. This is the last time that the first vertex is referenced so we finalize it. In this moment (once the triangle was rendered or processed or etc) we could potentially already deallocate it's memory. That is what allows streaming. The knowledge when we can destroy things. Like in a video stream. Once we decompressed and displayed a frame and completed using it for predictive decompression of future frames we deallocate it. Otherwise the whole "Finding Nemo" movie would be in memory at the end of watching it ... (-:
We use negative indices to "hide" finalization tags because it's actually supported in the OBJ format specification. Those are rarely used in practice it seems but a complete OBJ reader should implement them. They are relative indices that reference the vertex in the array at the position computed from the total number of introduced vertices plus (hence minus) this (negative) value. So when -4 appears the vertex count is at 4 and 4 - 4 = 0 so that vertex at position 0 in the array gets finalized. Using a hash instead of an array to map from indices to vertices allows to deallocate finalized vertices.
The last face finalizes the other three vertices explicitly, although the end of the file would do that anyhow.
Your API could implement introduction of vertices and faces in batches rather than individuals. For small meshes where streaming does not matter those batches are simply all vertices first, then all triangles, and nothing changes, cause initially most users won't have big meshes anyways. But integrating the concepts from the start - some variety of the above - can really turn out to be a slick move in the long run.
I could share a larger example if needed.
referenced this issue
Jun 26, 2018
referenced this issue
Jul 12, 2018
First of all I really congratulate you this is very big development! I am working on a plugin hydrology, hydrodynamic modelling in QGIS, as well. I wonder that. How can we prepare a mesh layer? What are the inputs for that layer? As I can see there is no attribute table. QGIS only show the layer data, but I dont know how I can create a mesh layer.
You need to add your format to mdal:
There are already examples of hydrodynamic model outputs, for example 3Di:
Currently, a copy of medal sits within QGIS source:
Ping us if you need further information or help.
I stil can not unserstand how I can create a mesh layer. For instance creating a vector layer is described in here:https://docs.qgis.org/testing/en/docs/pyqgis_developer_cookbook/vector.html#add-features. I want to an example like that. For instance I want to learn how time series initialize and features add?
Well it is okey. However it uses *.grb file. How can I create like a file I cannot see the attribute table like shape file because when I want to create a shape file I add the fields whatever I want because I know which fields I need. Four instance a mesh layer use time series, wind information, temperature information etc. How can I initialize these fields to mash layer.
You can create input data for mesh layer even in a text editor, for example:
Seems awesome! Will it support NetCDF on OS X too? It doesn't seem to right now, using a clean install of QGis 3.4 and the mesh layer (or the raser layer I should add). I'm getting: "Raster layer provided is not valid" and "file.nc is not a valid or recognized data source". EDIT: File is valid though, I can open it just fine in Panoply for example.
Also, in the "Add layer" menu, the mesh option does not seem to be available, only going via the data source manager?
Hi @Puffton, NetCDF files are supported, but maybe you have some file that has unrecognized syntax. Which installer do you use (https://lutraconsulting.github.io/qgis-mac-packager/ or QGIS official one?)