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.
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.
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.
As time flies by, we are closer and closer to the end of this year's Google Summer of Code. I had a lot of fun and learned many things this summer thanks to the program. My main field of interest is computer graphics and rendering, so working on a project focused on this was a great challenge for me, that I think I barely - due to some unexpected events - but somehow, overcame.
Speaking of what I learned, there are just too many things to list, but if I have to name three things, I would say: Qt, the basic geography and the math related to it, but there are so many more beside those. For example I struggled during almost the entire summer to implement an acceptable form of street name labeling in real time, performance-wise and looks-wise. I realized that there is almost a whole field of study dealing with it. But more on that later.
Improvements made this summer
Decorations
Implementing the decoration system for the GeoDataGraphicsItem class was my favourite task, because this class (and those derived from it) is responsible for the OSM Vector Tile rendering in Marble. This decoration system is responsible for the outlines of the streets and highways and for the - now even further improved - (fake) 3D building rendering.
Street and building decorations visible on a loaded .osm file in Marble.
A close-up from the previous picture.
The improved building decoration is visible more visible here
(top right corner, bottom left cornet)
The best thing about these decorations is that every GeoDataGraphicsItem can be improved this way. After some refactoring and improving the solution since midterms, a GeoDataGraphicsItem nowcan have multiple decoration, decorations can have decorations, which can have multiple decorations, so there is more potential for further improving the rendering of these items.
Street labels
As I mentioned above, getting the best results for the street name label placement was a pretty hard task. Not because it is hard to understand the principle, the math behind it is not that difficult, but because we needed it to work in real time with almost no performance impact on the rendering. This was further complicated by the fact that Qt doesn't provide a function to draw text along curved paths. Finally I came up with a solution, then another, then another, then ... , and now we have a pretty good looking (but in the future improvable) implementation. Additionally I had to implement some style setting functionality for these labels, like color and font settings.
Before my work on this project. Street labels are "just there".
The latest version. Text along curved paths is drawn now.
The funny thing is when your solution has 200 lines of code, but the results don't satisfy you in terms of performance, so while improving the same code several times you get a much better performance and result with only cca. 40 lines of code in the end. This happened to me with the task above :)
Better zoom with the mouse wheel
When I first tried out Marble, I was a little disappointed by the blurry zoom on the openstreetmap map theme. The program downloads the texture tiles used on the openstreetmap website and then projects them with the current projection (the one used by openstreetmap is the Mercator projection). In my project proposal I had an intention to fix this, so when I saw a comment on my first blog post requesting this fix I was sure that this is a pretty needed one.
After some work on it I completed the fix. I even made a little video demonstrating it, but in some days you will be able to try it out yourself. The second part of the video shows the rendering improvements on a new, empty map theme.
Improving printing support
Making Marble dpi-aware (and so preparing it for better printing)
I told you in my previous post that I will start to work on improving Marble's printing support, but this proved to be a pretty big task for the remaining time, because first we need to make Marble more dpi-independent. This is needed because if we just simply scale up the map to a higher resolution, then every icon and text will be much smaller in proportion to the original map. This could be overcome if we change Marble's internal dpi resolution before painting. Another argument along this task is the fact that this summer Marble was successfully ported to Android by Gábor Péterffy and developing an application for a smart-phone always comes with the struggle of the UI's dependenccy on the screen's dpi resolution (density).
I already made Marble recognize the current dpi resolution of the screen and to respond to it's change(e. g. when printing). Next step will be to supply Marble with icons and bitmaps for different dpi resolutions (ldpi, mdpi, hdpi at least). I look forward to working on this in the next months, and if we achieve more progress, I'll let you know in a next blogpost.
Other minor improvements
Several color style tweaks and changes in the OSM Vector Tile rendering, my goal was to match the default color style on the openstreetmap website.
When my time allowed I was looking for unincluded OSM map features, like highway=cycleway, highway=pedestrian, highway=road etc. and added them to the list with the right style.
I've created a simple empty map theme to load, view and edit these .osm files, though it's mainly for developer purposes.
Some bug fixes and refactoring in the source code.
Some finishing words
Before I started, I was pretty confident in my programming skills, I had experience with Qt and C++, but looking back from now I see that there is a lot more to learn for me than I thought. And I think this is one of the most beautiful things to realize: to realize that you can learn new things as long as you are willing to.
I'm glad that I got such a great project to work on. If the Google Summer of Code program's goal is to encourage people (students) to work on open source projects in their free time even after the end of summer, then the Marble team is one which definitely achieved this goal with me. I look forward to work with them in the future, maybe I'll join some other KDE projects too :)
I'm working on the project Improve Marble's OSM vector rendering and printing support. The first part of the project is to polish and improve the rendering of the OSM vector tiles in Marble. In my previous post you could see what it looks like without the improvements I have in my mind and now I want to share some pics and videos about the progress and results so far.
Adding outlines for OSM ways
One of the most outstanding issue was the lack of the outlines for streets and highways. My first task was to somehow overcome this problem. These lines are drawn as a QPainter line and thus they don't have style settings for outlines, so the best that I could do is to draw these lines twice: first draw a bit thicker (with 2 pixels) line with the outline color, then a second over top of it with the fill color. This approach of course is not enough, because the streets are not rendered in the order in which we want them. This results in something like this (which I showed you in my previous blogpost):
The solution is to sort the lines (and every object) depending on their z-value, so they are rendered in the correct order. As this sorting is a little bit resource-hungry, the outlines (and further on the decorations) are not rendered below Normal quality setings.
I even changed the style of almost every OSM item and added some new, unimplemented items to the list(like cycle ways or pedestrian ways), so they would match even better the standard color theme of the openstreetmap website. The end result looks good I think.
After the improvements
Before the improvements
Decoration and "Fake3D"
Implementing this feature led us to the idea to create a more robust API for creating such decorations for the GeoGraphicsItem classes which are used in the rendering process (e.g. the class used to describe the streets is the GeoLineStringGraphicsItem class). With overriding a simple virtual function, one can create custom decorations for every GeoGraphicsItem-derived class. To demonstarte this functionality, the outlines are implemented this way and I added a simple 3D effect (shadow) for the buildings. This takes almost the same approach as the outline rendering, but now this shadow is rendered with a little offset, based on the focuspoint of the map (the little cross at the center). I think this is a pretty good example to demonstrate the capability of such a decoration system.
Struggle with the street labels
As you can see on the first pictures, the street labels aren't aligned to the streets at all, even if this is a crucial point of urban maps. I thought that this would be an easier task than the decorations, but I was wrong. The proper alignment of the street labels with the right color, right size, right font, right direction etc. it's more like an art, than a simple task. One of the problem is that the program needs this to be done in realtime, so I can't use a "complex algorithm" to calculate these properties. And on top of that, Qt doesn't provide a proper way to draw a text along a (curved) path. The best thing I could do is to try to avoid the curvatures of the streets when drawing the labels, so they will be rendered properly most of the times. A quick demonstration of what I achived this far:
Overall
Due to my exams, I couldn't give a 100% priority to GSoC, but the progress this far meets my expectations and from now on, I can even double the time spent working, programming, experimenting.
I'll post a smaller status-update when I start working on the printing support improvement, until then I'm going to polish the work I had done this far.
In the end, here is a video demonstrating these improvements:
One of the reasons why I choose KDE as my mentoring organization is that I already used their Plasma desktop for quite a while now, thus I'm a little familiar with KDE Applications, but the main reason is that my programming skills and knowledge was best matched with KDE's Marble project.
Application to GSoC
During the application period I had a lot of fun while getting started. My introductory tasks revolved around Marble's Ground overlay feature in the Edit(Annotation) plugin. I had to use git-bisect to find a commit in which a regression occured. Then I had to implement manual resizing and rotating for the GroundOverlay, and correcting some bugs. These were great tasks to get me started working as a developer for Marble. Frequently speaking with my mentor about the changes and ideas that I wanted to implement was one of the best and most memorable part of it.
About my project
Marble has a great rendering engine, which is fast (Marble starts up in 2-5 seconds), reliable and allows developers to easily improve some of its features. My projects main goals are to improve the following parts of the program: the rendering of the .osm file based vector tiles, the picking of the texture tiles, improving printing support. I also intend to fix any bugs that I may encounter in the process. This would improve Marble's rendering and maturity too, so the end-user should be more satisfied with the application.
Let's start coding!
Though the coding period started a week ago, I've only got time from now to work on GSoC, because I didn't want to throw my school projects aside, those are important too.
So now that I've completed my school project(a simple tile-based rouge-like rpg), I can begin to work on my GSoC project. The not-so-good thing is that we have a quite early mid-term evaluation period(June 26. - July 3.), so we need to get some of our work done by that time.
I've started to work on the OSM vector tile rendering part, so the polishing of the rendering will be my main task for this month. I'm currently working on the outlines of the streets and highways. Just to get you the idea, I'll show some pictures about it.
This is how is it now in Marble:
An .osm file loaded with into Marble.
The rendering performance is good, but it needs a little polishing in order to achive something similar to the one that's on the OpenStreetMap website. This is what it should look like:
Same region, but from the openstreetmap website.
And finally this is my progress for now:
It's a little cartoon-like.
The streets now clearly have outlines, but it's not the best result we can get. For now, this is just an experiment of what can be done. I'm only drawing the lines twice, first the outline color, then the fill color, but it's done par ways, this is why it gets outlines were it shouldn't. To be honest, it took me quite some time to find the files in which I need to work, but as you can see, it's working now, so my next task will be to get it to an acceptable state.
That's it for now. Next time I want to share my progress on this task, possibly the completed version then.
