Marble: GSoC 2016 wrap-up

Today is the deadline for submitting the final evaluations for Google Summer of Code 2016, that gives me the opportunity to write a wrap-up post about my project this summer.

About my project

The aim of my GSoC project this summer was to bring fluent rendering to Marble's OSM Vector Tile map theme. The idea for this map theme is to render the vector data taken from the openstreetmap and natural earth databases. These are merged and cut into many many tiles that are stored in .o5m format on a server, and downloaded by Marble. To achieve this in the frst place we needed a tool that will handle this for us. Creating that tool was my main objective.

osm-simplify tool

This little program's purpose is to generate the data used by the OSM Vector Tile map theme. It does many different things regarding map data manipulation, but one of it's most important job is to create the tiles. That means to cut a huge world map to tiny little tiles that can be rendered in Marble.

osm-simplify tool

The tool uses Marble's data handling and parsing which I demonstrated in my previous post. That way you can even use this tool as an example if you want to use Marble for your map data manipulation project, but this tool is far from just an example program.

Tile cutting

More exactly this turned out to be a very resource hungry program. If you look at this table, you can guess why is that:

The hardest part of the tile cutting algorithm was the processing of polygons. This turned out to be a little challenging, but in the end, the solution was to inject another algorithm into Marble's clipping algorithm. The Weiler-Atherton polygon clipping algorithm works on concave polygons too, that solves the borderline issue which I described in my previous post, that comes from the Sutherland-Hodgman polygon clipping algorithm. The tool now uses the more simple Sutherland-Hodgman algorithm for clipping non-polygons, and the Weiler-Atherton kicks in when dealing with polygons.

Here is a nice demonstration of the results of the osm-simplify tool. I loaded 20 separate map files, each is a level 5 tile generated with this tool. I marked the corners of the tiles with red, because they are generated without any gaps between them.

Turning on polygon debugging gives us a nice view of each tile and the underlying cutting process:

To be continued...

I've done a little benchmark to check the performance of the tool, and the results were not that promising. Just for zoom level 9 it needed 6 hours to generate all of the tiles from a single map. The good thing is, there is many ways to improve on the performance. Parallel processing and tile tessellation comes to help. That will be my autumn project, because in the end, Google Summer of Code is about to encouraging students to get involved with open-source projects. 

Final words about GSoC 2016

This year I learned a lot about time management and programming, it was a really great experience. I don't know if I'll have time next year for GSoC, because that will be my last year in university, but I'll just encourage anyone who wants to participate in it, especially for KDE and the Marble team. 

GSoC 2016, Marble

Hi everyone!

This post is an overdue introduction and past-midterm wrap-up for this year's Google Summer of Code, but that is a great opportunity to write about all the great stuff that happened during this past two months. 

Some of you may remember me from previous year, if not, check out my GSoC blog. I worked on the Vector rendering of Marble, which was really fun, but this year's project is the real deal. I've got to work for the Marble team under the KDE organization, on a project which's goal is to help create the long awaited Vector OSM map theme for Marble. With the help of Akshat Tandon and our two mentors, we look forward to bring Marble's real-time vector rendering powers to Android by the end of summer.

Instead of apologizing for the missed introductory and mid-term blog posts, I will just jump straight into the details of this exciting project. 

For those who don't know much about vector graphics, it stands for a type of computer graphics, where the image is rendered with the use of lines and polygons, instead of a pixel-matrix with limited size(raster graphics). Up until now, one of the mainly used map theme in Marble was the OpenStreetMap map theme, which uses raster images(256x256 .png files) from the openstreetmap website. While that is a pretty good and widely used map, it has its downsides, which all translates back to the nature of its raster-based rendering. Using the XML-like openstreetmap data, we can create a vector rendered copy of the same map, but with much more possibilities and functions.

I was invited to the KDE Randa Sprint meeting this year, and started to develop the osm-simplify tool as part of my GSoC project. This will be used to style, cut and optimize the vector data which in the end will be downloaded and rendered by the Marble app. Instead of .png raster images, the tile data will be stored in a compressed vector format(.o5m), specially created for the OSM data.

Difference between raster and vector rendered map in Marble, on Android
Source

osm-simplify tool

Reading, parsing the data

Thanks to the way how Marble is written to be used as a library for other projects, the parsing of the data takes only 3 lines of code, and we get the usual, KML based GeoDataDocument. 

MarbleModel model;

ParsingRunnerManager manager(model.pluginManager());

GeoDataDocument* map = manager.openFile(inputFileName, DocumentRole::MapDocument);

After creating a QApplication, you just need to include the marble header, and that three line of code will do the parsing in the most convenient and efficient way I could think of. 

Manipulating the data

In order to achieve an optimal performance, we need to use the tiling approach for the vector rendering too. That way we can limit the whole processing and rendering only to the visible part of the map. The data is split into several zoom levels, each zoom level containing more and more data. For example, at zoom level 1 we have only 4 tiles, which cover the whole world, but on higher zoom levels, ie. level 12 we have 4096 x 4096 tiles, that's more than 16 million tiles. The data in those tiles needs to be profiled to the zoom level in which they appear. On lower zoom levels it would contain only the country borders, and major lakes and rivers, but on the highest zoom levels, even buildings, trees, bus stops should be rendered.

I had to create the tool in a way to be scalable enough to handle the different data manipulations we throw at it. Calling it with various command line arguments, it can merge maps, filter ways, reduce the node count by joining them(which was added by Tandon), and finally cutting whole maps into tiles. In the coming weeks we will add even more functionality to it, in order to get the vector data profiled for our Vector OSM map theme. 

Some level 5 vector tiles loaded in Marble

In the previous weeks I was working on the tile cutting of the osm-simplify tool. This is considered by me the Gordian Knot of this whole project, because it has to manipulate each type of vector data the OSM map contains, from polygons, to lines, nodes, etc. It has many opporunity to introduce visual artifacts, so it needs to be as bug-free as possible. Currently I'm about to remove that annoying tile border-line issue, which you can see on the picture above.

A nicely cut tile would look like this, without any issues at the borders

Problems and solutions

I had some problems with relatively slow progress with my project during the past month, mainly because I hit too many walls, and didn't want to ask for help in a "I can handle this myself" spirit. After getting a slight earful from my mentors I realized that, and that communication is vital, in a project of this scale, so I guess after completing GSoC this year, that will be one of those things that will come to my mind when someone asks "what did you learn during GSoC 2016".

Speaking of which, I look forward to learn even more things while working with Marble during and after Google Summer of Code. Can't wait to use the Vector OSM map theme on my Android phone.

Have a nice day and summer,

David Kolozsvari