Waze for WP7 – XNA here we come

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

Posted in Waze, WP7 | 23 Comments

Waze for WP7 – yet another “It’s about time” feature

Up until now, when you wanted to browse the map you would scroll it around. Problem was that after you put your finger up I had the MouseLeftButtonUp event skipped and therefore caused incomplete experience where you drag and drag just to get to the same place.

public void refresh(List<UIElement> list)
{
    Dispatcher.BeginInvoke(() =>
    {
        for (int i = MainGraphics.Children.Count - 1; i >= 0; i--)
        {
            if (!(MainGraphics.Children[i] is MediaElement))
            {
                MainGraphics.Children.RemoveAt(i);
            }
        }

        foreach (UIElement ui in list)
        {
            MainGraphics.Children.Add(ui);
            ui.IsHitTestVisible = false;
        }
    });
}

As you can see, each frame I remove all objects (except MediaElement so sound will be still available) and put the new objects instead.  Problem was that MouseLeftButtonDown event was caught by one of the objects on the map (Polygon, line, etc.) but as soon as the user moved the map around, this frame has been erased and new objects replaced the old ones. This causes SilverLight (and maybe other frameworks) to think you should not get the MouseLeftButtonUp event since the original control is not there anymore.

The “ui.IsHitTestVisible = false;” line directs SilverLight to pass the Left Button event ‘through’ all controls so it will be recieved by the canvas which is there all the time. This way I was able to receive the corresponding Button Up event and update the map current X,Y accordingly for the following scrollings.

http://meirtsvi.wordpress.com/2011/06/27/waze-for-wp7-downloads/

Posted in Waze, WP7 | Tagged | 3 Comments

Waze for WP7 – Hebrew support – finally

This post assumes you installed some package that provides you with Hebrew support.

I got to the point where I had just about enough time to finally debug the hebrew issues and motivation to do it as some of the addresses I typed recently were hard to translate.

Turns out that my code worked semi ASCII and semi UTF-8. In some places of the code I translated string to its ASCII chars (ignoring completely from chars above 128) and in some other I was good citizen and converted C# string to UTF-8 before returning them to C (now MSIL) code.

After 2 hours of struggling with buffers, ASCII and UTF-8 I’m now able to enter the navigation address in Hebrew using Native Keyboard integration.

Note that if you want to enter numbers as part of the address, just type them as you would in PC e.g. for “שנקר 13 הרצליה” enter “הילצרה 13 רקנש”.

Get the version in:

http://meirtsvi.wordpress.com/2011/06/27/waze-for-wp7-downloads/

 

Posted in Waze, WP7 | Tagged | Leave a comment

Smooth Sounds

Up until now there was a delay between direction instructions words, e.g. “within” “800″ “meters” “turn right”. Each word was contained in a separate mp3 file in order to maximize flexibility in direction variations. Problem was that there was big delay between words that sometimes led to cases where the instructions were almost irrelevant as you already passed the target point they were aiming at.

I spent the weekend in finding the root cause and trying to solve this issue. Turns out that WP7 has hard times decoding MP3 files and even worse is that you cannot pre-load/decode MP3 file before playing it.

I tried all kind of tricks in order to ‘concatenated words’ with no success:

- Use XNA SoundEffect class won’t work as it only decodes WAV files.

- I’m using MediaElement in order to play MP3, why not instantiate several such objects and play them one by one? because WP7 doesn’t allow several instances to exist – only one is allowed.

- Use playlist (client side playlist) – playlist aren’t supported in WP7.

The main issue here is that I wanted to keep the sound files in MP3 format since Waze downloads the sound files on demand from the server and I no control over the format of the d/l files. This is not quite true as I bring the hebrew and english sound files as part of the XAP file and copy them to isolatedstorage on the first time you run Waze in order to save redundant downloading time and data. So if I go with WAV format, which sould decode faster and probably solve the lagging I will lose the support for other languages’ audio.

I took the chance and converted all MP3 files to WAV files and went for a ride. Guess what? problem solved!

http://meirtsvi.wordpress.com/2011/06/27/waze-for-wp7-downloads/

Posted in Waze, WP7 | Tagged | 4 Comments

Waze for WP7 – Java to CSharp

OK, so I have Waze and Cibyl source code and all I need to do is make Cibyl yield C# code instead of Java. Simple, right? Well, not exactly.

Cibyl dictates you to work in two layers: the Java bytecode level and Java code level. The C code that comes in Cibyl is being translated to Java bytecode while every external call from the C code (printf, DrawLine, fopen etc.) is being translated to a call from the Java bytecode to Java code for implementing the required functionality. Example:

#include <stdio.h>
#include <cibyl.h>

int main(int argc, char **argv)
{
  printf("hello");
  return 0;
}

Will be translated into 10K Java bytecode lines (I shit you not) that will call Java for printing the characters to the screen:

; 0x01001c84: 0x1001c84: cibyl_sysc_arg 0x7
	iload_3
; 0x01001c88: 0x1001c88: cibyl_sysc_arg 0x8
	iload 7
; 0x01001c8c: 0x1001c8c: cibyl_sysc 0x120
	invokestatic Syscalls/NOPH_OutputStream_write(II)V
; 0x01001c90: 0x1001c90: addu  a3, v0, zero
	iload 4
	istore_3

What’s that?

Apparently, Simon, the creator of Cibyl, did amazing work of translation all LIBC to be compliant with Cibyl. Essentially he implemented all the I/O functions (fopen, printf etc.) as C code that calls Java predefined funtcions to do the real IO (print char to the screen, open file etc.). The C code is being compiled into Java byte code and, along with your code, being printed into J files (Java assembly files).

 

Now, for making it really useful, some performance work has to be done. Read about it here

Posted in Waze, WP7 | Tagged | 1 Comment

Waze for WP7 – screenshots

Latest screenshots:

Posted in Waze, WP7 | Tagged | Leave a comment

Additional speed improvements

I just found out that when calling roadmap_log, there’s a lot of computing going on (checking log level, preparing the timestamp etc.) just to get to the point of not doing anything since we are on Release mode and calling System.Diagnostics.Debug.WriteLine.

So roadmap_log will now immediately return.

Get the faster build on the Downloads page:

http://meirtsvi.wordpress.com/2011/06/27/waze-for-wp7-downloads/

What about those mumbling sounds? can you fix that?

Posted in Waze, WP7 | Tagged | 1 Comment