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

About these ads
This entry was posted in Waze, WP7. Bookmark the permalink.

23 Responses to Waze for WP7 – XNA here we come

  1. Didi Barak says:

    Used it yesterday and today – and it become usable. THANKS!

  2. whizzz says:

    Hey, nice job.

    But I cannot login with my existing login or create new account in app.
    If I try to login it returns “You must have a valid username and password”, same if I don’t enter anything. I tripple check my password, tried to change it etc.
    If I try to create account it just tells username is empty, even I entered all fields.

    Is it supposed to be like that?

    I use waze in iOS without any problem.

    • Meir Tsvi says:

      I saw similar problems happening to others. It seems like the server you are trying to connect to is not updated with your account. For others closing and re-opening the app worked.
      If you are desperate, simply click on Sign-Up (instead of Sign-in) and on the followign screen click ‘Skip’. At least you will be able to use the app.

  3. Christophe says:

    Great job !
    It seems to work for me. I’ve installed it few minutes ago and I will test it this afternoon.
    Thanks a lot

    PS I’ve been unable to sign in at the first time. After exiting and restarting the application it was possible.

  4. Elad Avron says:

    thanks!
    I’ll be giving it a shot soon, just wanted to thank you for your dedication and hard work before I do!

  5. Jorge says:

    How do I install this app on my Omnia W? Please advise, I do not see why I should blow 100 USD on Navigon when I had this app free on my samsung Galaxy S (it crapped out on me and the WP7 phone looked and handled smoother than my Galaxy)..

    • Jorge says:

      Your assistance would be greatly appreciated in this matter :)

      • Meir Tsvi says:

        You need to dev unlock your device. Chevron might still offer the service.
        Once you did, install windows phone sdk and using the app deployment tool, install the latest xap file from downloads page.

    • Meir Tsvi says:

      You need to dev unlock the device. Chevron might still offer this service. Once you did that, install WP SDK and use the app deployment tool to install the latest XAP file from downloads page.

  6. Tamir Ofri says:

    are you going to publish it on “market place”? I can`t unlock my phone because all the token have been sold out. please help me.

  7. Dimitry says:

    Hi Meir,
    Is there a way to install waze on car-pc running on WinCE6.0 or Android 2.x
    If no, do you plan to do it possible?

  8. I am really impressed with your blog as it shows great dedication to the task. I actually found your site when I was looking for a C# port of Waze – not for a phone though. I want to put Waze onto a PC.

    Does that sound possible? I hope so.

    • Meir Tsvi says:

      Waze code can be easily compiled into win32 executable. Simply load the win32_env.sln from win32\win32_env directory. It is based on the C++ code though, not C#.

  9. Thanks very much for the quick reply. I’m not a C++ coder, so I will be attempting a conversion of your WM code to Win32. The end-result I am after is a full navigation/entertainment system for a car-PC, so this is only one of the “modules” I need.

    • Meir Tsvi says:

      The funny thing is that before producing WM code I did produce winforms code. Then I refined it over 6 months to run on WM especially by combining SL with XNA.
      I hope that XNA Game project type in Windows allows integration with SL. If this works, then it is only a matter of time to take this kind of conversion project.

  10. Yoel says:

    Hey, is this support windows phone 8?
    It’s will be great if then.
    TNX.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s