Evaluate the requirements to implement offline hillshading

[Framstag]

It would be nice to be able to render local hillshading. Currently one has to fallback to use tile servers (See janbar/osmin#9). The goal of the issue is to collect research and evaluate if this goal is realistic.

See the following links, for possible rendering code:

• https://observablehq.com/@sahilchinoy/hillshader
• https://observablehq.com/@sahilchinoy/a-faster-hillshader

The are the following obvious requirements, constraints and questions

• We need elevation data is necessary precision. How precise elevation would be required?
• Is OSM database a "OK" source of elevation or do we need an external source?
• If OSM database is OK, how would be the transformation? elevation data is nit by default bitmap oriented.
• What are the licenses for this sources, in which format are they?
• Assume that elevation is bitmap orientated (possibly with some run length or tree based compression or similar) how big such bitmap would be in the end (rough estimation, asume, we have 256 grey levels)? How big should it be in maximum to be useful?
• Are there chances to preprocess parts of the calculation by for example lookup tables? The are a (huge) number of expensive mathematical functions involved. How big the lookup tables would have to be (in the end we have 256 grey levels, some symmetry and color depends only on the relative slope)?

[vyskocil]

What a great idea !
I used to compute bitmap overlay with tools like QGIS and combine them with libosmscout rendering but I was workable at a little scale as the bitmap take a lot of space.
Actually I use phyghtmap to compute elevation contours from SRTM data to OSM PBF and combine this with the general OSM data for a region. I mainly use this for hiking, the coverage I use is limited to French, Swiss, Italian,... Alps but not for a whole country.
I also embed the SRTM data files in my app and use the raw height data to compute elevation profile for routes, you could also touch the map in the covered area and get the elevation at this point (I use the SRTM function I added a long time ago to libosmscout). Here is a screenshot of my iOS app :

[Framstag]

To have an idea is the simple part ;-)

As it looks like you already worked with this, you may answer some of the above questions?

Which basic SRTM data did you use (link)? What its resolution and how big would an possible naive bitmap be thus (See http://libosmscout.sourceforge.net/tutorials/importing/for rendering elevation profiles, sounds like you use a different way for generating a elevation profile *.osm /*osm.pbf file?)?

Do you have a value how much the resulting database increases in your case (I remember @Karry found it to be OK)?

It look like elevation profile and hill shading may use the same base data but are they transformable during runtime (if I have some bitmap of elevation pixels is there a simple way to generate elevation profile lines or vice versa)?

[vyskocil]

It would be wonderful to have elevation data right in the osmscout database in a compressed form because raw SRTM files are quite heavy and not compressed at all, it's just a array of int values written in a file... A 1" x 1" tile (10 m resolution) is about 26Mo. I generally use this site to get the SRTM files : http://viewfinderpanoramas.org/dem3.html
Some time ago I looked how to add a elevation data for all the nodes imported at the first stage of the Import process as it would give us elevation for all OSM nodes imported and would not be too heavy. This would allow to compute route profile without the need of embedding the SRTM files but we would have to interpolate to have the height in between the nodes but if we also import the elevation lines the data would be dense enough.

[vyskocil]

Here is a link to a 1" x 1" SRTM tile right in the Alps : http://viewfinderpanoramas.org/dem1/n45e007.zip
The 1" x 1" (10m resolution) is not covering the whole world, unfortunately, but 3" x 3" (30m resolution) should cover almost the whole earth.

[vyskocil]

Do you have a value how much the resulting database increases in your case (I remember @Karry found it to be OK)?

I didn't really measured it but seems not to be a big deal in my cases but I "only" import for now the French Alps when I build the database for the whole France.

It look like elevation profile and hill shading may use the same base data but are they transformable during runtime (if I have some bitmap of elevation pixels is there a simple way to generate elevation profile lines or vice versa)?

The way from bitmap to elevation profile is what phyghtmap is doing and it needs quite a log of computation on my desktop computer. I think that the algorithm could use a lot of data even when we needs a localized rendering because the iso height lines could go far away before coming back...
The other way computing the bitmap from elevation lines seems a lot easier as it should only be some interpolation on a grid from the nearest iso lines.

[Framstag]

The other way computing the bitmap from elevation lines seems a lot easier as it should only be some interpolation on a grid from the nearest iso lines.

I'm not sure. If I have small cells (math note book) and every cell has an hight, there ar ea number of combination regarding the neighbouring 8 cells that have (nearly) the same hight - or not. For each of these patterns (symmetry involved!) the path of an elevation profile line should/might be static/lookup table. In result you should get a number of nodes for drawing a bezier curve which should be roughly the elevation line.

Something worth to try out?

The main advantage of a bitmap like structure is its locality - which is good for fast rendering (and database lookup) :-)

[Karry]

Hi guys. It is great topic, I was thinking about it already, but it will not be trivial :-)

Is OSM database a "OK" source of elevation or do we need an external source?

We definitely need external source. OSM contains just some hills, not contour lines. There was two SRTM dataset from NASA, and various national dataset. All combined together and "cleaned" can be found on http://viewfinderpanoramas.org/dem3.html

What are the licenses for this sources...

All DEM data on viewfinderpanoramas should be free for non-profit usage. At least these datasets from NASA.

...in which format are they?

HGT file format. @vyskocil prepared basic code already: https://github.com/Framstag/libosmscout/blob/master/libosmscout/include/osmscout/SRTM.h

Do you have a value how much the resulting database increases in your case...

Adding contour lines to libosmscout database increase size by tens of percent in Europe, but increase may be bigger in big countries with sparse map coverage. For example 60% for Zimbabwe (167 -> 274 MiB).

For generating contour lines in osm format I am using phyghtmap tool now (@vyskocil mentioned it already).

For generating route elevation profile may be used raw HGT data (@vyskocil using that, right?) or estimate it from intersections with contour lines, as I prepared in this MR #992 and using in my app.

For generating hillshades from raw DEM data (tif format) may be used GDAL python library. I am using it on my hillshade server. Whole planet (without polar areas) in 3" resolution occupy 71 GiB (9.1 GiB for zoom level < 7). I don't tried to generate hillshades on mobile device or even with c++ code. But it should be possible :-)

I may even imagine to use current elevation lines for that. When you generate triangles to fill space between nearby elevation lines, it should be easy to compute slope of such triangle and compute shadow when you know where the sun is. Resulted layer may be blurred then to looks more realistic :-) When whole process will be computed on gpu, it may be usable fast. Any volunteer for this fun programming on gpu?

[Framstag]

OK, based on @vyskocil and @Karry feedback, we should definitely improve the documentation. I have the feeling I currently would not be able to reproduce you processing beyond coastlines and basic osm.pbf parsing. It might also make sense to enhance the build.sh script (or add other scripts) the ease the number of calls? I can make an additional issue for this.

Btw., contour lines and elevation profile is for me the same!? Seem like I'm missing some know how, too ;-)

Contour lines: Draw lines of equal height on the map
Elevation profile: Draw the hight profile for a given path on the map?

Right? Should/Could both not be based on the same data?

I can offer the database part (in a simple first version). I'm also interested to do some algorithmical tests and of course coding for trying to extract elevation lines from a hight bitmap.

My problem is simply time. Especially if you are waiting for me finishing the database part, I'm blocking all of you.

I'm currently working on using for CPU during import by reworking some import steps and creating some code patterns and helper classes. This matches fine to my interest to improving my coding skills by getting influenced from some functional programming technics.

[Karry]

Contour lines: Draw lines of equal height on the map
Elevation profile: Draw the hight profile for a given path on the map?
Right?

Yes, I am using this naming :-) I am displaying elevation profile (chart) for router/navigation track in application...

Should/Could both not be based on the same data?

• contour lines are prepared before import by phyghtmap tool and then imported as usual ways to database
• elevation profile is computed in application on the device - from SRTM data or intersections with contour lines ^^^

[Framstag]

I have now done some cleanup of the existing SRTM code of @vyskocil to get to know the existing code. See #1036

Some findings:

• For e more general usage of SRTM we likely not only need a "get elevation at point" function but also a "get elevation array in (visible) bounding box" function.
• Depending on the zoom level this matrix has to get compacted to a usable size (at runtime or at import time). Likely a tree like structure is the answer. Every layer may compact the elevation data by a factor of multiple of two...
• In SRTM a database uses 2 bytes. I could imagine that this could further be compressed for areas with small elevation changes (we can handles changes of +/- 127 meter in one byte). In the following I speak of HGT files, by we could use or own posisbly more compact file format, too.
• In the end we must be able to handle multiple HGT files, so the SRTM code must be able to efficiently access multiple HGT files (or their transformation).
• All imported HGT files should have the same resolution (SRTM1 or SRTM3) so that data form a bounding box is "same sized" independent of the HGT files merged. The resulting data should be a rectangular bounding box, though may be smaller than the requested bounding box.
• The next step would be to add a GetBoundingBox()-like method for one HGT file as a start. This could be the base for further experiments (contour lines or hillshading).
• For this I have to have clear, how data in the file is sorted (the answer is in the code, but I would like to be sure ;-))
• A question for later on: Would we use the existing Renderer for drawing contour lines (yes, could make sense) or do hillshading (may not make sense => hardware rendering?)?

[vyskocil]

Hi @Framstag !
I just compiled the code from the head of the repository and tried the OSMScout Style Editor on my Mac, it works well but now we are seeing the SRTM grid by default, is it intended ? :

[vyskocil]

I also have a question about the elevation data coming from SRTM will it be available for the router ?
My dream for long would be to add a new pedestrian routing algorithm for hiking that would take the route profile into account !
We could define the walking speed related to the angle of the route segments something like :
-90° ... -45° : 0.5 km/h
-45° ... -20° : 3 km/h
-20° .. 20° : 4.5 km/h
20° ... 45° : 3 km/h
45° ... 90° : 0.5 km/h
Of course this would need to be tuned :-)
Then this new pedestrian routing algorithm would choose the fastest path and not only the shortest like for the routing for a car.

[Framstag]

@vyskocil I can reproduce it. That looks like the tile grid (MapPainter::DRawOSMTileGrids()), not the SRTM data grid.

Looks like

    //[TYPE _osm_tile_border] WAY {color: #222222; displayWidth: 0.2mm; }
    //[TYPE _osm_subtile_border] WAY {color: #444444; displayWidth: 0.1mm; }

are somehow activated!? Some special internal code in the StyleEditor?

I'll try to get contour lines working first. That is mainly "a rather huge work" with some algorithmic trickery. I'll try get as much boiler plate code running, that we can improve this step by step over time.

This should be a good base for hillshading. But this is something I likely will not have time myself.

Elevation lines for a route like @Karry did before in his application should be rather easy to implement based on contour line code.

SRTM & routing:
In principle it should be possible to evaluate SRTM data during routing (food, bike), too. I have neither a concrete plan for this nor good idea how to di it (one step after the other ;-)). IMHO this will likely be more a problem of APIs, locality, performance etc... Since I expect routes by foot to be smaller, in practice performance might not be a problem at all....With my experience regarding routing though I'm not sure if this generate "better" routes, I expect it more relevant for bike routing than foot.

[Karry]

Hi Tim. Your plan to have generic elevation data in database sounds ambitious :-) It may have various usages, I may even imagine fully 3D map with terrain. Did you some preliminary calculations how big these data sets will be?

[Framstag]

Sometimes one has to be ambitious and have to try ;-) I do not have a calculation. Currently height is stored in tiles with 1 bytes for each tile cell. If the area is rather flat you can reduce it to one byte by storing a "base height" per tile and the difference -128/+128 meter in one byte (possibly even 2 data cells in one byte?). Since there will be tiles with more height "dynamics" one likely has to store tiles in a tree-like structure, where bigger tiles are broken down into smaller tiles - possibly even storing data in two bytes for some tiles in cases where this is more efficient.

We already have some experience with combined tree and bitmap data structures.

Obviously (if you look at the tile grid) we also have to store compressed data for low-zoom views since the number of data cell to be loaded is too high in this case. These low-zoom tiles would need additional space. So in the end a 1:1 ratio in relation to SRTM data would be already great. It is unrealistic to gain more than 1:2 without much effort.

I'M still thinking if such SRTM index will be part of the basemap or of one database. Since original format is already tile based an independent of the actual *.osm.pbf file, part of the basemap would make more sense. Currently I'm thinking of generate one database file for each *.hbt or tile. The initial implementation places it into Database, but this is easy to move later on.

The database will thus either load height of one coordinate or it can (efficiently) load height in a rectangular bounding box.

And yes, there will be other use cases, too. But I would already be happy if we get contour lines ;-) I'll try to work on this today for a few hours to have more code infrastructure ready, but do not expect me to work on it alone, due to lack of time. There will definitely help needed. That is the reason I communicate this much and I'll want same base code running so that we share a common idea (or come to a common idea by discussion ;-)) and you all can help.

[Framstag]

As promised #1049 for same basic "hacked down" code. It is neither fast nor nice, it does not really integrate into the renderer architecture, is not refactored and full of redundant code...but there are simple contour lines ;-)

See https://opentopomap.org/#marker=16/51.56572/7.45508 in comparison for the opentopomap. I assume that they may use SRTM1 instead of SRTM3 since there are some more details or they have some variance in the algorithm.

For nicer contour lines one have to do weight the lines between to SRTM cells depending on the slope (currently we draw the border just in the middle). Also currently we just draw paths for the cell border trusting that this automatically builds longer paths. If we must anker points for the contour lines we have to do real path detection. Also for adding contour labels to the contour lines we have to build path segments up to longer contours. to make them look nice.

Nervetheless:It is a start.

The map was created using

Demos/DrawMapCairo --contourlines true --hillshading true --srtmDirectory ../maps/srtm ../maps/nordrhein-westfalen ../stylesheets/standard.oss 1600 1024 51.565 7.455 70000 test.png 2>&1 && display test.png

where maps/srtm contains *.hgt files for the region. You have to use an import of germany/nordrhein-westfalen. Also note, that maps.ost got a new type, so you have to reimport things to get it working.

If I have some time left over the weekend, I create a number of issues so that someone can assign the issue to itself to signal that he/She is working on it.

[vyskocil]

Congrats, that's a great achievement in such short time !
I just remembered the name of a algorithm I saw when I was student that could be useful for the contour lines extraction, it's the marching squares

[Framstag]

@vyskocil Yes, that sounds like a good algorithm to choose, Cool, I was not aware of it. I have an issue for it, see #1051.