A faster fisheye plugin for d3.js

Introduction to fisheye

Fisheye is a kind of “Focus+Context” techniques for visualizations. Fisheye enhances glyphs locally with displacements and zooming, providing details in the focal area. Meanwhile, it keeps the glyphs unchanged outside the area, serving as context so that the user still has an overview for the visualization. One of the advantages of fisheye over a plain magnifier, which has a constant scaling factor in the whole area, is the continuity at the boundary of focal area.

The continuity implies different glyphs should have different displacements and scaling factor ($\ge 1$) inside the focal area. Usually, we are more interested in the following isotropic case:

  • the focal area is a round region centered at the current focal point, which can be the current position of the mouse cursor if on a computer interface like a web page;
  • inside the area displacements or scaling factors are functions of the distances between their original positions and the focal point;
  • at the boundary there is no displacement nor scaling
    The first two visualizations in d3’s fisheye demo page are examples for this case. To be more specific, let $p_0=(x_0,y_0)$ be the coordinate of the focal point, $p=(x, y)$ be the coordinate of a glyph to be distorted, and $r$ be the radius of the focal region. Here is one way for distortion:
$$\begin{equation} \begin{aligned} x_{f} = & x_0+k\cdot(x-x_0) \\ y_{f} = & y_0+k\cdot(y-y_0) \\ s_{f} = & k \end{aligned} \label{eq:distortion} \end{equation}$$

where $f$ stands for “fisheye”, $s$ is the scaling factor, and $k=k(d(p,p_0))$ is a monotonically decreasing function w.r.t. the distance between $p$ and $p_0$. Figure 1 shows a curve for $k$ from the implementation in d3-plugins/fisheye with $r=200$.


Figure 1: an example for the function $k$ in Eq. \eqref{eq:distortion}. Notice $k(r)=1$ so no changes at the boundary.

So if we apply the calculated distortions on the nearest neighbors of the current focal point whenever the focal position changes then we are done. d3-plugins/fisheye implements this. However, this naive $O(n)$ nearest neighbor searching does not scale. Different tree-like space-partitioning data structures have been invented for indexing points in $\mathbb{R}^n$, reducing the time complexity of spatial searching to $O(\log n)$ on average. There are for example k-d tree, ball tree, quadtree, etc. I simply choose k-d tree in fast-fisheye.

k-d tree is a binary tree for space indexing, created from subdividing the space by axis-aligned hyperplanes recursively. To build a k-d tree, we start with an axis and find the median in that axis. The axis-aligned hyperplane going through the median will divide the whole point set into two subsets. We then create the root node at the median, and construct the two child k-d trees from the two subsets, until a stopping criterion is met, which is usually reaching the limit for tree depth, leaf size, or leaf radius. Figure 2 is taken from Wikipedia, showing an example of the construction.


Figure 2: a k-d tree for point set $\{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)\}$. Axis $x$ and $y$ are chosen alternatingly when moving down during the construction. In fact cycling through the axes is the standard way of axis-choosing at each level.

Given a query point, k-d tree supports two kinds of nearest neighbor searching: the $k$ nearest neighbors of the query point, or all neighbors within a radius of the query point. We only care about the latter case in fisheye. A branch in the k-d tree is pruned if its bounding rectangle does not intersect the query disk. The Python-like pseudocode is shown below.

1
2
3
4
5
6
7
8
9
10
11
12
13
# input: root, query, radius
# output: neighbors
neighbors = []
stack = [root]
while stack:
	node = stack.pop()
	if node is leaf:
		neighbors += [for p in node.points if distance(p, query) <= radius]
	else:
		if bounding_rect(node.left_child) intersects disk(query, radius):
			stack.push(node.left_child)
		if bounding_rect(node.right_child) intersects disk(query, radius):
			stack.push(node.right_child)

Finally, I use the k-d tree implementation in nanoflann for fast-fisheye.

Emscripten: compile C++ to JavaScript

To glue things together, I use emscripten to compile the C++ computation code into JavaScript. Emscripten is an LLVM-based project, which “compiles any other code that can be translated into LLVM bitcode into JavaScript” without losing the native performance. In the simplest cases like here, all you need to do is 1) write adapters in C++ to expose your C++ classes or functions to JavaScript, and 2) compile the C++ code to JavaScript. Check their documentations for more information. A list of porting examples and demos may also be of interest.

An example

The code can be found on GitHub, including an example with 20000 random circles and fisheye effect rendered by this fast-fisheye, as well as a baseline with the same set of points but rendered by d3-plugins/fisheye. At least in my Chromium (version: 48.0.2564.82 (Developer Build) Ubuntu 15.04 (64-bit)), I can see a noticeable speedup and smoother rendering in fast-fisheye compared with the baseline. Unfortunately in Firefox both are slow, but I might be too lazy to figure out the reason.

It is also possible to incorporate nearest neighbor searching techniques for moving query. I leave this to future works.