Deep Zoom, MultiScaleTileSource and the Mandelbrot Set

Article
08/22/2008

There are some changes to Deep Zoom in Silverlight 2 Beta 2 including a new XML based file format and the ability to dynamically generate Deep Zoom images by creating your own MultiScaleTileSource. MultiScaleTileSource is an abstract class with one method to override - GetTileLayers() .

 protected abstract void GetTileLayers(
    int tileLevel,
    int tilePositionX,
    int tilePositionY,
    IList<Object> tileImageLayerSources
)

In other words Deep Zoom (or more accurately, a MultiScaleImage control) will come to me and say I want tile x,y at tile level z, what should it look like? And I need to respond with an image. How this actually works is not well documented and not very intuitive so I'm going to do my best to explain it here as I eventually figured it out with help from MikeT who has already written a blog post on this which provides a lot of good info. I'm going to try and explain it in simple terms that even I can understand.

Rather than setting the MultiScaleImage.Source property in XAML, if you want to use your own MultiScaleTileSource you need to set the Source property on the MultiScaleImage control like this:

 this.msi.Source = 
  new DynamicDeepZoom.DynamicTileSource((int)Math.Pow(2,20), (int)Math.Pow(2,20),128,128);

Which says, I have an image of dimensions 2^20 x 2^20 and I can supply you with tiles of dimensions 128x128. ie up front I have to specify the dimension of my image (even though I don't *really* have an image as such, I'm going to be generating it on the fly and in my case, as I'm really generating a fractal, in theory I have infinite resolution but Deep Zoom doesn't work like that and I guess mine is something of a special case :-)). We'll come back and talk about tile dimensions at length in a moment.

My DynamicTileSource class is very similar to Mike's implementation:

 public class DynamicTileSource : MultiScaleTileSource
{
  public int tileWidth { get; set; }
  public int tileHeight { get; set; }

  public DynamicTileSource(int imageWidth, int imageHeight, int tileWidth, int tileHeight)
    : base(imageWidth, imageHeight, tileWidth, tileHeight, 0)
  {
    this.tileWidth = tileWidth;
    this.tileHeight = tileHeight;
  }

  protected override void GetTileLayers(int tileLevel, int tilePositionX, int tilePositionY,
    System.Collections.Generic.IList<object> tileImageLayerSources)
  {
    string source =

      string.Format(
        "https://localhost:61753/DynamicDeepZoomWeb/handler.ashx?" +
        "tileLevel={0}&tilePositionX={1}&tilePositionY={2}" +
        "&tileWidth={3}&tileHeight={4}",
        tileLevel,
        tilePositionX, tilePositionY,
        tileWidth, tileHeight);

    Uri uri = new Uri(source, UriKind.Absolute);

    tileImageLayerSources.Add(uri);
  }
}

Mike, in his post, refers to "remoting requests" to server side code because there's not much you can do in SL2 by way of creating bitmap images. In fact, I believe GetTileLayers() *expects* you to add URIs to tileImageLayerSources. That means generating bitmaps client side wont be much good to you anyway. Instead I went down exactly the same route as Mike with the same caveat - System.Drawing server side probably isn't a great idea (at least not without some thought to caching) - especially with the type of drawing I'm going to do. But it serves to illustrate how this works.

I created a handler (again, the implementation is almost identical to Mike's) which expects a set of parameters (tileLevel, tilePositionX, tilePositionY, tileWidth, tileHeight) and will respond with an image in png format. In GetTileLayers() (above) I simply construct the URL to the handler, setting the appropriate querystring parameters and add that to tileImageLayerSources.

Where this gets a bit complicated is when you come to draw your bitmap. Somehow, you need to figure out from those parameters which bit of the overall image you're being asked to draw.

Fundamental to how Deep Zoom works is the concept of layers and tiles. The overall, "full-res" image is divided into n x m tiles. Subsequent, lower res versions of the image form a sort of pyramid where the next layer has dimensions n/2 and m/2 tiles and the next layer n/2/2 and m/2/2 tiles and so on.

The "magic" of Deep Zoom is it determines the optimum layer to display at any particular zoom level. As you zoom deeper, you progress to a deeper layer and more, higher-res tiles are requested and displayed.

If you take the simplest example using images and tiles whose dimensions are powers of 2, then things become a little clearer. Imagine our "original" image is 1024x1024 and our tile size is 256x256. At the base of the pyramid is a layer 4 tiles x 4 tiles. At the next layer, 2 x 2, then 1 x 1.

In reality, things work the other way around. In Deep Zoom terms, the top of the pyramid is always 1x1 pixels and is defined as tileLevel=0. tileLevel is simply a layer numbering system that is independent of tile size. ie we can calculate the maxtileLevel simply from the image dimensions. It's always going to be

Ceiling( log₂(ImageDimension) )

whether my tile size is 1x1 or 1024x1024.

So, for our 1024x1024 image, the maximum number of layers you'd ever need would be 10 (as 2^10 = 1024). ie even with a tile size of 1x1 pixels, 10 layers would be enough to represent the original image. If my maximum image dimension is 512, my maxtileLevel is 9. If it's 5096, then maxtileLevel is 12 etc. It doesn't matter if my tile is 1x1 or 128x128, tileLevel is always the same.

When GetTileLayers() gets called and tileLevel = 0, that means MutliScaleImage is displaying a 1x1 pixel image. If tileLevel = 2 it's a 4x4 pixel image etc. A consequence of this is that tilePosX and tilePosY only become a factor when

tileLevel > log₂(tileDimension)

Below that, your tile is bigger than the image MultiScaleImage is displaying. ie if you have 128x128 tiles, tileLevels 0-7 are 1x1, 2x2 .... 128x128 and you always return the same tile. Only at tileLevel 8 and above do you have to worry about which tile you should return. At tileLevel 8 it could be one of 4, at tileLevel 9, one of 16 etc up to the maxtileLevel which we know is Ceiling( log₂(ImageDimension) ).

That means we can do something like this to figure out how many tiles in X and Y dimensions would be displayed at the requested tileLevel:

   private Bitmap DrawMandel(int tileLevel, int tilePosX, 
    int tilePosY, int tileWidth, int tileHeight)
  {
    Bitmap ei = new Bitmap(tileWidth, tileHeight);

    int tileCountX = (int)Math.Pow(2, tileLevel) / tileWidth;
    int tileCountY = (int)Math.Pow(2, tileLevel) / tileHeight;

    tileCountX = tileCountX < 1 ? 1 : tileCountX;
    tileCountY = tileCountY < 1 ? 1 : tileCountY;

This allows me to calculate what proportion of the image I'm displaying (1/tileCountXorY) and which portion (tilePosXorY). This is important for my application to display the Mandelbrot set. ie performing the calculations on the fly and delivering the rendered tiles back to MultiScaleImage. I need to know which portion of the set to calculate and display as the user zooms into the image:

I'm no expert on the Mandelbrot set but I do remember being fascinated by it many years ago when I first came across programs to display a graphical representation. I remember having to *wait* for these things to draw and here we are in a world where we can easily do the calculations on the fly, turn them into a bitmap and serve them up over http!

Anyway, for the theoretically minded amongst you, the Wikipedia article is as good a place to start as any. I actually derived my implementation from the excellent explanation and sample code here.

Essentially the calculation revolves around complex numbers and whether, for a particular number, the iterative application of a specific function remains bounded. If it does, the number is a member of the Mandelbrot set and vice-versa. The colour effects are achieved at the boundaries by shading based on the number of iterations before the calculation diverges. Anyway, this isn't meant to be about Mandelbrot :-).

Here's my implementation which is concerned with complex numbers from -2.0-1.2j to 1.0+1.2j. ReStart, ReDiff, MinRe and MaxRe refer to the real components and ImStart, ImDiff, MinIm and MaxIm to the imaginary components.

 private Bitmap DrawMandel(int tileLevel, int tilePosX, 
  int tilePosY, int tileWidth, int tileHeight)
{
  Bitmap ei = new Bitmap(tileWidth, tileHeight);

  int tileCountX = (int)Math.Pow(2, tileLevel) / tileWidth;
  int tileCountY = (int)Math.Pow(2, tileLevel) / tileHeight;

  tileCountX = tileCountX < 1 ? 1 : tileCountX;
  tileCountY = tileCountY < 1 ? 1 : tileCountY;

  double ReStart = -2.0;
  double ReDiff = 3.0;

  double MinRe = ReStart + ReDiff * tilePosX / tileCountX;
  double MaxRe = MinRe + ReDiff / tileCountX;

  double ImStart = -1.2;
  double ImDiff = 2.4;

  double MinIm = ImStart + ImDiff * tilePosY / tileCountY;
  double MaxIm = MinIm + ImDiff / tileCountY;

  double Re_factor = (MaxRe - MinRe) / (tileWidth - 1);
  double Im_factor = (MaxIm - MinIm) / (tileHeight - 1);

  int MaxIterations = 30;

  for (int y = 0; y &lt; tileHeight; ++y)
  {
    double c_im = MinIm + y * Im_factor;

    for (int x = 0; x &lt; tileWidth; ++x)
    {
      double c_re = MinRe + x * Re_factor;

      double Z_re = c_re, Z_im = c_im;
      bool isInside = true;
      int n = 0;
      for (n = 0; n &lt; MaxIterations; ++n)
      {
        double Z_re2 = Z_re * Z_re, Z_im2 = Z_im * Z_im;
        if (Z_re2 + Z_im2 &gt; 4)
        {
          isInside = false;
          break;
        }
        Z_im = 2 * Z_re * Z_im + c_im;
        Z_re = Z_re2 - Z_im2 + c_re;
      }
      if (isInside)
      {
        ei.SetPixel(x, y, Color.Black);
      }
      else
      {
        if (n &lt; MaxIterations / 2)
          ei.SetPixel(x, y, Color.FromArgb(255 / (MaxIterations / 2) * n, 0, 0));
        else
          ei.SetPixel(x, y, Color.FromArgb(255,
            (n - MaxIterations / 2) * 255 / (MaxIterations / 2),
            (n - MaxIterations / 2) * 255 / (MaxIterations / 2)));
      }
    }
  }
  return ei;
}

We calculate the minimum value for the real or imaginary component from the start value and add:

diff / tileCount * tilePos

The maximum value is just the minimum + a "tile width" = diff / tileCount

Having set things up in this fashion, the rest is pretty much the same implementation as the article referenced above.

The images above are from the application rendering in Silverlight using Deep Zoom. I'd like to publish a "live" version but I suspect the System.Drawing functions might make me less than popular with my hosting company. I'll post the full source code shortly and publish a link here.

Did any of that make sense?

Technorati Tags: silverlight,deep zoom,multiscaleimage,multiscaletilesource,mandelbrot

Deep Zoom, MultiScaleTileSource and the Mandelbrot Set

Additional resources