## Tuesday, May 21, 2013

### SVG Navigable Viewport Part 1: Theory and Frustrations

This is a continuation of my previous tests to try and develop a navigatable 2D scene using HTML5 and Scalable Vector Graphics. The features I want to discuss are:

• Panning the scene
• Scaling/Zooming in and out
• Rotating the scene

edit: I changed the text to match the terminology of the SVG standard, in particular when discussing viewport or user space. Basically I had them backwards before.

# Panning

The most basic idea of panning is:

1. The user selects a given start point $$x_0, y_0$$ in the viewport space
2. The user selects a given end point $$x_1, y_1$$ in the viewport space
3. The viewport should translate the scene in such a way that the end point $$x_1, y_1$$ in the viewport space translates to $$x_0', y_0'$$ in the user space.

The viewport coordinates are pixel coordinates, where (0, 0) refers to the top-left pixel of the containing svg element (or some equivalent when nesting svg elements). Now that we know what we want, let's use math to describe this goal:

$M_0 = \begin{bmatrix} a & c & e_0\\ b & d & f_0\\ 0 & 0 & 1 \end{bmatrix}\\ T_1 = \begin{bmatrix} 1 & 0 & \alpha_1\\ 0 & 1 & \beta_1\\ 0 & 0 & 1 \end{bmatrix}\\ \left(M_0 T_1 \right)^{-1} \begin{bmatrix} x_1\\ y_1\\ 1 \end{bmatrix} = M_0^{-1} \begin{bmatrix} x_0\\ y_0\\ 1 \end{bmatrix} = \begin{bmatrix} x_0'\\ y_0'\\ 1 \end{bmatrix}$

Our goal is to solve for $$\alpha_1$$ and $$\beta_1$$. $$M_0$$ is the initial tranformation matrix which translates the user coordinates to the viewport coordinates, which is why we must take the inverse. Why did I do this? Because this is how SVG stores the transformation matrix, so I may as well use it. Now to solve:

$M_0 T_1 \begin{bmatrix}x_0'\\ y_0'\\ 1 \end{bmatrix} = \begin{bmatrix}x_1\\ y_1\\ 1 \end{bmatrix}$ $\begin{bmatrix} a & c & a \alpha_1 + c \beta_1 + e_0\\ b & d & b \alpha_1 + d \beta_1 + f_0 \end{bmatrix} \begin{bmatrix} x_0'\\ y_0'\\ 1 \end{bmatrix} = \begin{bmatrix} x_1\\ y_1 \end{bmatrix}$ $\begin{bmatrix} a & c\\ b & d \end{bmatrix} \begin{bmatrix} \alpha_1\\ \beta_1 \end{bmatrix} = \begin{bmatrix} x_1 - a x_0' - c y_0' - e_0\\ y_1 - b x_0' - d y_0' - f_0 \end{bmatrix}$ $\beta_1 = \frac{a (y_1 - d y_0' - f_0 ) - b (x_1 - c y_0' - e_0) }{a d - b c}\\ \alpha_1 = \frac{x_1 - a x_0' - c y_0' - e_0 - c \beta_1}{a}$

The next question is how do we handle dynamically updating target destinations? Well, by definition $$x_0',y_0'$$ will always be the point of interest in user coordinates (i.e. the point under the cursor), so it will not change. We have also already updated the transform matrix at each step such that the previous definition is true, so there is no additional work required. Simply calculate $$M_n$$ using $$M_{n-1}$$ and $$x_0', y_0'$$.

$M_n = M_{n-1} T_n$

# Scaling/Zooming

The type of zooming behavior I want is similar to one I had previously re-created using Qt, and is used by Solidworks, Eagle CAD, and possibly other software tools (though I wish all similar software tools would use it). When I wrote this example in Qt, I kind of "half-hazardly" did this because of the rather interesting way Qt handles viewports. The closest approximation to how this could be acomplished with an SVG image is to muck around with the root SVG element's viewBox, or worse. I'd really rather not do this, so let's apply the same mathematical formulation to derive a better method.

The zoom function takes two arguments: the zoom factor, and the zoom focal point. The zoom focal point is defined as a point in viewport space which maps to the same point in user space before and after the transformation, i.e.:

$\left( M_0 S_1 T_1 \right)^{-1} \begin{bmatrix} x_0\\ y_0\\ 1 \end{bmatrix} = M_0^{-1} \begin{bmatrix} x_0\\ y_0\\ 1 \end{bmatrix} = \begin{bmatrix} x_0'\\ y_0'\\ 1 \end{bmatrix}$

where $$M_0$$ and $$T_1$$ are defined as before, and $$S_1$$ is:

$S_1 = \begin{bmatrix} s_x & 0 & 0\\ 0 & s_y & 0\\ 0 & 0 & 1 \end{bmatrix}$

But this is really just the same problem as translating! The only difference is to scale the transformation matrix, then solve for $$\alpha_1$$ and $$\beta_1$$. Unlike the Qt implementation, this definition should be applied universally irregardless of zooming in or out.

# Translation Simplifications: Only Panning/Scaling

Let's consider the case where the only allowed viewport transformations are translations and scaling. What simplifications can we make to the calculations of $$\alpha$$ and $$\beta$$? Well, assuming the initial transformation matrix is the identity matrix, we know that the transformation matrix will always take this form:

$M = \begin{bmatrix} a & 0 & e\\ 0 & d & f\\ 0 & 0 & 1 \end{bmatrix}$

This drops quite a few terms in the calculation of $$\alpha$$ and $$\beta$$:

$\beta_n = \frac{y_n - d y_0' - f_{n-1}}{d}\\ \alpha_n = \frac{x_n - a x_0' - e_{n-1}}{a}$

Microsoft has a page describing Panning and Zooming with SVG. I haven't dug too much into the details of their implementation, but their demo appears to work in cases similar to this simplified version (panning/scaling only). I don't know if non-uniform scaling is handled equally well (I don't see why not), and I don't know if it works in the general case. I'd be interested to know when their implementation works and when it doesn't.

# Javascript Implementation

Now let's look at how we would implement this in Javascript using the SVG DOM interface. The key idea is being able to manipulate an entire scene's viewport using a single DOM element transform. The SVG Group Element (g) allows us to group several child elements together and manipulate them synchronously. So the first thing to do is to wrap all scene elements with a viewport group:

<svg id='svg_base'>
<g id='viewport'>
<!-- scene elements go in here -->
</g>
</svg>


Next, we have to deal with the javascript event handlers. For this demonstration I'm going to use the following interface:

1. While mouse button 0 (typically LMB) is down, the user can move the mouse to pan the viewport.
2. Scrolling the mouse-wheel up zooms in
3. Scrolling the mouse-wheel down zooms out
4. Getting the mouse's location relative to an element is remarkably complicated. I used brainjam's solution to get this information.

This demonstration doesn't allow rotating or non-uniform scaling of the viewport, but I did implement the full $$\alpha$$ and $$\beta$$ translation function so adding these would not be difficult. I added a 4:1 non-uniform scale and 30 degree rotation to demonstrate that it does work in the general case. There are a few oddities I wanted to highlight:

1. Rather than attaching the mouseup event handler to the svg base element, I attached it to the document. This is because even though a mousedown may have been triggered inside the svg element, it doesn't capture the mouse focus, so theoretically any element can receive the mouseup event. As far as I'm aware the only way to track if a button is down or up is to capture these events and manually track this state. I believe the attaching the mouseup handler to the document element should capture all possible cases.
2. I'm manually binding and unbinding the mousemove event handler. This is kind of a "cheat" optimizations which I'm not really sure is considered good practice. It does reduce the CPU load from about 16% down to 5% or so when the mouse is moving over the svg and no mousemove event needs any special handling, which may be significant for machines with lower computing power than mine.
3. I implemented the scale/zoom functionality directly into the event handler while I did implement a helper for panning.
4. Firefox's wheel event handling is abysmal. I added a work-around that gets around this issue. See this page for more info.
5. I tried running this in IE10 and I didn't get anywhere. I honestly have no idea what's going on here, I'll have to dig deeper into the code to figure out just why it isn't working.
function SVGViewportHandler(svg_base, viewport)
{
this.svg_base = svg_base;
this.viewport = viewport;
this.mousedown = false;
var that = this;
this.mouse_move_wrapper = function(e){that.onmousemove(e);};
svg_base.addEventListener('mousedown', function(e){that.onmousedown(e);});
document.addEventListener('mouseup', function(e){that.onmouseup(e);});
svg_base.addEventListener('mousewheel', function(e){that.onmousewheel(e);});
// firefox does not support mousewheel yet!
svg_base.addEventListener('DOMMouseScroll', function(e){that.onmousewheel_ff(e);});

}

// arg: element, mouseevent
// source: brainjam, slightly modified
// http://stackoverflow.com/questions/5755312/getting-mouse-position-relative-to-content-area-of-an-element
function mousePosRelElement(elem, e)
{
var style = getComputedStyle(elem,null);
var borderTop = style.getPropertyValue('border-top-width');
var borderLeft = style.getPropertyValue('border-left-width');
var paddingTop = style.getPropertyValue('padding-top');
var paddingLeft = style.getPropertyValue('padding-left');
var offsetX = e.offsetX || e.layerX || 0;
var offsetY = e.offsetY || e.layerY || 0;
var loc = {x: offsetX, y: offsetY};
if(window.navigator.userAgent.indexOf('Opera') === -1)
{
loc.x -= parseInt(paddingLeft,10);
loc.y -= parseInt(paddingTop,10);
if(window.navigator.userAgent.indexOf('MSIE') === -1)
{
loc.x -= parseInt(borderLeft,10);
loc.y -= parseInt(borderTop,10);
}
}

return loc;
}

SVGViewportHandler.prototype = {
onmousedown: function(e)
{
if(e.button === 0)
{
this.viewport.setAttribute('stroke', 'red');
this.mousedown = true;
this.panStart = this.svg_base.createSVGPoint();
var temp = mousePosRelElement(this.svg_base, e);
this.panStart.x = temp.x;
this.panStart.y = temp.y;
this.panStart = this.panStart.matrixTransform(this.viewport.getCTM().inverse());
this.svg_base.addEventListener('mousemove', this.mouse_move_wrapper);
}
e.preventDefault();
e.stopPropagation();
return false;
},

pan: function(dst, origin, matrix)
{
var beta = (matrix.a * (dst.y - matrix.d * origin.y - matrix.f) - matrix.b * (dst.x - matrix.c * origin.y - matrix.e)) / (matrix.a * matrix.d - matrix.b * matrix.c);
var alpha = (dst.x - matrix.a * origin.x - matrix.c * origin.y - matrix.e - matrix.c * beta) / matrix.a;
matrix = matrix.translate(alpha, beta);
var transform = this.svg_base.createSVGTransformFromMatrix(matrix);
this.viewport.transform.baseVal.initialize(transform);
},

onmousemove: function(e)
{
if(this.mousedown)
{
var matrix = this.viewport.getCTM();
var dst = mousePosRelElement(this.svg_base, e);
this.pan(dst, this.panStart, matrix);

e.stopPropagation();
e.preventDefault();
return false;
}
},

onmouseup: function(e)
{
if(this.mousedown)
{
this.mousedown = false;
this.viewport.setAttribute('stroke', 'black');
this.svg_base.removeEventListener('mousemove', this.mouse_move_wrapper);

e.preventDefault();
e.stopPropagation();
return false;
}
},

onmousewheel: function(e)
{
var zoomFactor = Math.pow(1.1, e.wheelDeltaY / 56);

var matrix = this.viewport.getCTM();
var temp = mousePosRelElement(this.svg_base, e);
var dst = this.svg_base.createSVGPoint();
dst.x = temp.x;
dst.y = temp.y;
var focus = dst.matrixTransform(matrix.inverse());

matrix = matrix.scale(zoomFactor);
this.pan(dst, focus, matrix);

e.preventDefault();
e.stopPropagation();
return false;
},

onmousewheel_ff: function(e)
{
// not only is FF coords backwards, but stored in radians!
var zoomFactor = Math.pow(1.1, -e.detail * 180 / Math.PI / 56);

var matrix = this.viewport.getCTM();
var temp = mousePosRelElement(this.svg_base, e);
var dst = this.svg_base.createSVGPoint();
dst.x = temp.x;
dst.y = temp.y;
var focus = dst.matrixTransform(matrix.inverse());

matrix = matrix.scale(zoomFactor);
this.pan(dst, focus, matrix);

e.preventDefault();
e.stopPropagation();
return false;
}
};


To use this code, just pass an svg element and the viewport element to a new instance of SVGViewportHandler. And finally, a working demonstration. This demonstration adds a bunch of randomly distributed rectangles. During panning, the rects will be highlighted in red. I've also enabled the non-scaling-stroke vector effect, which makes the rectangles' stroke width indepedent of the zoom level.

# Conclusion

So at the end of the day, I have a navigable SVG viewport, sort of. There are still many problems, for example it doesn't work in IE10 (no idea why), and I have low hopes for this working in other browsers. It's disappointing that the code I wrote which is more or less to the HTML5 standard (I think) has such poor support from so many browsers. I'll keep working on trying to get more browsers working, but I just can't get all of them, especially mobile browsers. Even Microsoft's Zoom and Pan demo didn't quite function correctly in IE10!

I also haven't quite figured out the rotation mechanics. There are many ways to define a rotation, and I'm still figuring out which method I like best.