After the awesome work that Eran Gonen has done on the entire dialog system and configuration screens the only pain left for proper version was the map movement.
Waze works in its own special way of rendering the map. Each frame is being drawn from scratch so there isn’t one big map you simply move around but rather draw each polygon again and again for each frame even if there wasn’t any change or the map simply moved one pixel to the left. The layer that is responsible for the graphics (roadmap_canvas) get simple instructions (draw_polygon, draw_circle) but without the context so it can make it own judgement what will be the best strategy of re-rendering each frame.
When I started the project the only options available for me were XNA and Silverlight but not both of them together. Mango changed the picture and offers rendering Silverlight on top of XNA.
Out of the two, I chose Silverlight as it offered everything I needed regarding graphics and controls. Choosing XNA back then would have force me to draw each and every Windows control (textbox, combobox) pixel-by-pixel. After many profiling sessions I learned that creating the graphic elements (polygon, arc etc.) and rendering them again and again for each frame is not being done efficiently enough by Silverlight.
One idea I asked Meni Zalzman to check was WriteableBitmapEx control that seemed to offer hassle free vector objects without the overhead of maintaining them later on; you simply draw polygon and forget about it – no need to add it to canvas and remember to remove it afterwards.
From early checks it seemed not fast enough and for me it meant I had to start thinking about XNA.
XNA provides three primitive types: point, line and triangle. The purpose of offering only those basic elements is that the GPU is using those primitives to draw to the screen in the most optimal way and XNA strives to remove any unnecessary levels between the code and the GPU. What you usually do, as a game developer, is to draw a model using Maya, 3dxmax etc. and export it in a format that XNA can load and render. In my case it wasn’t possible as Waze draws each frame out of polygons that don’t have any pre-defined mesh.
So I started by implementing each and every shape Waze requires: line, polygon wait! how do you draw polygon?
This is where Triangulator class gets in. When you want to draw filled polygon you need to break the shape into triangles and draw them one after the other. In order to break the polygon into triangles you should use Triangulator. I took the one that was available in OpenGL implementation of Waze C code and converted it to C#. It gets a list of points the polygon is composed of and returns triples of points for the triangles that compose the polygon.
OK, what about empty polygons?
If you have the list of points the polygon is composed of, simply draw line between each one and there you have it.
I did some optimizations on 4-point polygons by bypassing the Triangulator and simply created 2 triangles out of the 4 points. Rectangles were not different either.
As for circle, where I only get the radius as an input, I had to find the geometry formula for drawing one out of simple points and draw line between each one. Filled circles will be implemented later :)
OK, now I had all graphics being drawn by XNA objects but what about the text?
The way XNA provides text support is by taking a font and converting it to a series of bitmaps, each one representing single character. Very simple but introduces another issue: how do you scale font? Waze draws text in sizes between 3 and 38. For now, I simply created 36 groups of bitmaps, each for every size. This makes the compilation take longer and the XAP package to grow. I opened issue in GitHub for that.
Did it help?
When running Waze using XNA implementation on the Windows Phone Emulator it shows huge performance improvement. It felt like this is it, just wrap it and release the XAP package. Then I installed it on the device and… it wasn’t that good at all. Map movement had many hiccups and the performance was only slightly better compared to the SL version.
Profiling
Windows Phone SDK provides profiler specially crafted to Windows Phone. It resides on different menus and looks that someone have not had the time to polish it so it will look as part of the IDE. I guess that on the next version it will look more native.
I ran several cycles of profiling and found out I had two function inside roadmap_label that caused all the trouble. They both consumed 50% of the CPU time!
These functions are responsible for drawing the street labels on each frame in the right size, place and angle. But most interestingly, the problem was they used too much ‘free’ C calls.
If you open smalloc.c file inside cibyl you can find malloc and free implementation. This is a little bit tricky as malloc cannot allocate memory in order to achieve its goals :)
What they do is keep two meta-data linked lists, one for maintaining free memory chunks and the other for the occupied ones. Whenever you need new memory, malloc looks for free chunk that is big enough for you, removes it from free chunk list and adds it (sorted) to the occupied list. Since the occupied list is sorted you can probably image yourself what happens when you allocate and free memory at high frequency; the memory gets very fragmented and every insert operation to either list takes a long time since they are kept sorted.
Fortunately enough, Waze had similar problem and developed roadmap_label_fast implementation where they don’t do any free but try to use preallocated memory. This comes on the account of not showing all the street names in a given frame but only the significant ones (not sure why). So we have new task to compare the roadmap_label to roadmap_label_fast and come up with optimized version free of ‘free’s and full of labels.
To really get all the benefit from XNA I will have to use the antialiasing feature it provides. The regular way of enabling antialiasing does not seem to be provided when using Silverlight/XNA project. I’ll have to find the right way for this kind of project.
Wanna try the new version? get it from here
