This project is read-only.

Performance Architecture for Shapes - please contribute

Oct 12, 2008 at 3:15 AM
We need to make some decisions for how we can get some awesome performance for complex polygon/polylines like for example routes and also large quanities.

Currently on the MultiScaleImage (MSI) "ViewportChanged" event that fires whenever you pan or zoom (fires about 80 times on an animated zoom on my dev machine) we trigger updates to shapes.
We want our shapes to stay snapped to their location on the map.

Based on the code from lutzg "powerLaw" example : http://blogs.msdn.com/lutzg/archive/2008/08/19/synchronizing-images-with-the-deep-zoom-content.aspx
I have changed the code to run a 0 frame animation triggered off this event to ensure we have a single instance of the updating occuring smoothly. I added some logic to ensure it doesn't bother to call the update unless a pixel change has actually occured (reduced the number of calls by half).

I beleive the expensive function to be the conversion of lat/long to pixel location. I've added a complex polyline to the prototype project by getting about 9000 points from the VE Routing Service. You can see this in action here:
http://deepzoom.soulclients.com/ve Click on the button "route Brisbane -> Sydney" - > zoom in on east coast Australia. Note the Performance sucks.

The issue is the animation triggered by the map move hammers the lat/long -> pixel conversion. 9000 conversions X 45 frames on a zoom in.

I suggest the following but am looking for ideas from people who have done this before:

  1. If the zoom level doesn't change we should be able to simply move the shape by a calculated pixel value, since it stays at the same location on the map the projection doesn't change. No need to recaluate Lat/Long -> pixel.
  2. Option to have complex polygons/polylines only render once a zoom has completed.
  3. Reduce the number of points in a polygon/polyline to actual pixel values at the given zoom level.
  4. Find a way to counteract the strange wobble effect the MSI produce on the animated zoom in.

John.

Oct 12, 2008 at 4:14 PM
Great job on implementing the route! But yes, very poor performance as of now. I agree with options 1 and 3. However, I have notices that in the ShapeEventBehavior class, ViewChanged() gets called 4 times when doing a simple pan / zoom. Each time it is called the route with 9000+ points are updated ... so thats 36,000+ points being updated!!!

I think we need to look at this and have this call only happen once, maybe twice to ensure things are where they are supposed to be. However, if there is a route then that update only needs to happen once.
Oct 12, 2008 at 11:22 PM
Its a trade off between performance and having the points accurate and synced to the map during the animated pan.

5. During the animated zoom reduce the set of points in a polygon/polyline and use a less accurate transform, on zoom complete redraw accuratly.

So assuming #1 fixes our panning issues and #3 is a given if we set it at 1 pixel (make that configurable), we need to speed up the zoom for complex shapes. Two ideas, first reduce the set of points further, during the zoomed animation I suspect it is less important that these shapes are super detailed - but it make look horrible. Second is rather then convert the Lat/Long to a pixel location can we find a faster transformation based on the MSI data. It may not very accurate but could be significantly faster and useful for all shapes.

Side note: anyone know the best way to accurately monitor the performance of silverlight methods?
Oct 13, 2008 at 4:52 PM
Edited Oct 13, 2008 at 4:55 PM
After watching the video where the Route is explained, e.g. the 9000 points Brisbane to Sydney.... this is what I initially was thinking.

first, I would try to reduce points when the map is zoomed out and increase as the map zooms in to a closer view...
also as the map zooms in you see less of the actual "Route" so in the loop that is adding the points, could you test to see if this point is actually going to be drawn on a section of the map that is able to be viewed by the user at this particular zoom level...

e.g. if I am zoomed in on brisbane, and I can only see the city streets, I want the detail of a lot of points, but I cannot see 95% of the route as it is not in view, that part of tthe map is not displayed, therefore there is no need to draw those points...  so I may only need to have 50 points draw which is detailing the streets in brisbane city, not the whole 9000 all the way to Sydney.

but currently I notice that the "Route" is only draw/added onto the map once via the 

routeLayer.List.Add(

new Polyline { Points = points, LineThickness = 2, LineColor = Colors.Blue});

 

then it is not added again, my method describe above would mean that you would call the service once, then you have the list of points and hold them in memory
then you would have to contiune to calcualate the points depending in if the user zooms and/or drags the map and wok out which points in the route are actually being displayed on the map at that moment and how many you are going to add for that zoom level and then remove the old points for the previous Route and add the new points for the updated Route as the map is moved or zoomed...

so I am not sure how difficult this would be and if you think it would actually end up being slower that what you have now...?

it is just my first idea as I was watched the video...
Oct 20, 2008 at 9:09 PM
The fact that the route from the VE route service has 9000 points shouldnt be an issue if only the required level of detail is drawn. Currently the GeometryBase.CreatePoyuGeometry() only reduces the number of points if the projection of the lat/long is the same pixel as the previous point, and therefore for a 9000 point line when zoomed out, most points in the line will be on adjacent pixels. Obviously slightly less detail can still give the desired visual reults, and reduce the number of points beind updated while zooming around.

I suggest we bolt in a distance based line simplifier, like the one below, to reduce the number of  points in the PathGeometry. Just need to determine the acceptable minimum number of pixes in distance between points on the screen to be the distance tollerance.
http://code.google.com/p/nettopologysuite/source/browse/branches/v2.0/NetTopologySuite/Simplify/DouglasPeuckerLineSimplifier.cs

Oct 23, 2008 at 4:13 PM
Edited Oct 23, 2008 at 4:14 PM
On an application that I am working on at my job, these are things that I did to improve performance:
* Hide shapes when zoom animation starts. Show and re-calculate after the zoom animation completes. We could change that to only hide geometry types so that we can continue to animate the points, which is pretty slick
* When converting shapes to pixels, I convert to logical pixels instead of screen/viewport pixels. Then I apply an TranslateTransform to the shape canvas and let silverlight handle moving the shapes around when panning the map.
* Only re-calculate logical pixels when the zoom level changes
* Improved bounds intersection testing so that only the shapes in the viewport get calculated.
This drastically increased the performance of the shapes especially when multiple geometry shapes were in view. I can try to port it back to this application but I am using a different mapping client (I can't use DeepZoom because I need it to support multiple tile layer overlays with per layer opacity and I need to use it in Silverlight and WPF projects).
Oct 23, 2008 at 11:33 PM
I think we are all in agreement this is exactly what needs to happen. I have made each of these a Task assigned to the Version 1.0 release.
Oct 24, 2008 at 1:06 PM
Also, we can set the max frame rate to control how often the shapes will get updated, might be an easy way to fix this for now:
http://blogs.microsoft.co.il/blogs/alex_golesh/archive/2008/07/17/silverlight-application-performance-refresh-rate-amp-cpu-usage.aspx

Here's a link to silverlight performance tips:
http://msdn.microsoft.com/en-us/library/cc189071(VS.95).aspx

Oct 24, 2008 at 10:26 PM
Given the recent changes to ShapeEventBehaviour, I think that adjusting the FrameRate may no longer have an affect on UpdateShapes.  If you think about how it is now implemented as an animation, it simply loops as many times as it can until the time is up.  This is kind of a self governing loop, since the more objects are needing to be updated, the fewer updates are performed during the animation time limit. 
Oct 25, 2008 at 10:16 PM
I implemented the changes that I described above. The performance on geometry shapes is much better now.
Oct 26, 2008 at 4:53 AM
performance is much better when you add the "Route" and move/pan or zoom in and out on the map :)

I notice that sometimes the "PushPins" are not getting redrawn/added back onto the map sometimes when I zoom in and out with the mouse wheel
and the pushpins while panning are not staying on there spot, their like they are on a rubber band and lag a little behind the map movement, while the route line seems to maintain it's position alot better.

also if you pan the map so the route goes off the viewable screen and then pan it back into view the push pins are also gone untill you zoom the map again then they will come back, sometimes and sometimes they do not comeback

the above is also the same for a PushPin that I add via "alt+click"

this is not happening when I add the "Polygone" that acts as before, e.g. does not disapear when paned off the screen and back on again and does not lag while panning the map
Oct 26, 2008 at 10:04 PM
Edited Oct 26, 2008 at 10:05 PM
That was an oversight on my part. Pushpins were not being added back to the canvas after being panned back into view. I made the changes and checked it in.
Oct 26, 2008 at 10:24 PM
Regarding the lagging effect, I think there is an explanation.  With our implementation of the animation loop in the ShapeLayer, we have effectively severed the direct relationship between UpdateViewPort and UpdateShapes.  So when we have a large number of shapes to update, UpdateShapes will be invoked fewer times within the 1500 ms timeframe.  This is the rubberband lag you see when there are 9000 points to update.  You should not see the effect when there are only a few shapes in the ViewPort to be updated. 

I think most of us would choose the rubber banding effect over the choking effect of prior.  That being said there is still have more we can do to improve the problem.  As suggested previously, I agree that shape simplification probably holds a lot of promise for further performance gains.
Oct 27, 2008 at 9:57 AM
Interesting the lagging is only for pushpins - the geometry seems to stick fine. We need to look at this further - I agree it is a good comprimise when we hit performance limitations but currently it happens with only 2 pins. Something is not quite right.
Oct 27, 2008 at 4:29 PM
Great observation.  Your right, there must be something else going on. Now I wonder if the complexity of the shape has anything to do with it.  Let's try to see what happens when the PushPinVisual is as simple as can be (e.g. single elipsis).
Oct 29, 2008 at 12:20 AM
I don't think it has anything to do with the complexity of the shape as I tried using just an Image control and it still suffers from the rubber band effect. I even tried to remove the animation and it still had the rubber band effect.
Oct 29, 2008 at 12:46 PM
Edited Oct 29, 2008 at 4:39 PM
Fixed the pushpin rubber band effect.

The cause was the fact that we were using MSI.LogicalToElementPoint to convert from logical coordinates to screen coordinates. This works fine in typical situations, but resulted in the rubber band effect during panning and zooming. I took the implementation used in this sample and the rubber band effect is no more :)