Scale up your D3 graph visualisation, part 2
WebWorker layout and PIXI.js rendering performance improvements
In the first part, I started with a usual D3-based graph visualisation and replaced SVG rendering code with PIXI.js, a 2D drawing library, which uses WebGL with automatic fallback to Canvas. In this part, I’m going to present to you a few further possible performance improvements. I have also expanded available configuration with multiple layouts and sample graph generators, so that layout performance and visual quality can be compared.
The presented techniques are available in the live demo, feel free to tinker with the code.
WebWorker layout
Although JS supports async programming thanks to the event loop pattern, this is not a true parallelism. JS is a single-threaded language.
Any long-running function delays running other functions, potentially freezing UI responsiveness, because it affects user input event handlers as well. Graph layouts belong to this category, they are CPU-intensive algorithms with usual time complexity O(n log n) or worse.
This situation improved with the introduction of WebWorkers, a native browser feature that enables us to run code in a parallel background thread. WebWorker code doesn’t have access to the main thread global scope. Communication between threads happens strictly via message passing with postMessage method, which either clones the message payload, or transfers message ownership to WebWorker thread, so that it can’t be used by the main thread anymore. Note that this avoids the need for thread-safe data structures known from other languages. However, in the case of larger messages, it is recommended to strip the message only to fundamental properties or use the ownership transfer method.
If you use a build tool in your frontend development flow, such as Webpack or Rollup, take note that providing code to WebWorker thread is very different. This code can’t be part of the usual JS bundle, but it must be referenced as a standalone JS file. Therefore you’ll need to specify a separate main entry point in the build tool to get a separate bundle with dependencies.
For simple use cases, there is a shortcut. It is possible to store the code in a string in an in-memory blob, where you can import dependencies from external files by importScripts function and run this blob as a virtual file.
Combining all these tips, here is a minimal function running d3-force layout inside WebWorker. It can be called from the main thread as any other usual function returning a promise:
Culling and levels of detail
There was a significant rendering performance issue in the previous demo. With many nodes, the visual experience during mouse interaction with the graph was sluggish, FPS was dropping to unacceptable low numbers. Measuring with Spector.js helped me a lot to find the bottlenecks. The good rule of thumb is to limit the number of GPU calls and the number of active textures in GPU memory. Reusing textures to draw similar objects is highly preferable. In the rest of this article, I’m going to focus on reducing these numbers.
Culling is the process of removing objects that lie entirely outside of the viewport. It improves performance for zoomed-in views, where only a few graph elements are visible. I have implemented it with pixi-cull library. However, it doesn’t help with zoomed-out, full graph views, which are also desired in graph viz.
For improving the performance of the full graph view, I have employed a technique of displaying different levels of detail by zoom level in 4 steps. When you start with a zoomed-out graph, only nodes as color circles are visible. When zooming in, first edges appear, then node icons, then node labels. This reduces the number of draw calls significantly for large graphs.
Sprites
When you start digging into how to optimize PIXI.js rendering, the most frequent suggestion is to use sprites wherever possible. Sprites are simple 2D objects with texture. The advantage is that PIXI.js batches drawing multiple of them into with a single WebGL shader.
Therefore I have replaced all PIXI.Graphics instances by pre-rendering into PIXI.Texture, and later rendering it with PIXI.Sprite.
Text rendering
Remember that WebGL is primarily a low-level 2D API for GPU-accelerated drawing of triangles. It lacks high-level methods like fillText from Canvas, which allows simple drawing of text by any font available on the computer (including imported web fonts). Generic support for rendering text is a massive feature on its own. There is an excellent write-up Techniques for Rendering Text with WebGL in Three.js I highly recommend to read about all possible solutions and font preprocessing. PIXI.js provides some of them ready-to-use so that you don’t have to implement the solutions manually.
PIXI.Text
Previously I used PIXI.Text. It is the most straightforward method, which doesn’t need any font preparation. You can render any font available, same as with rendering with Canvas. Internally it renders the full desired text string into Canvas and uses it as a texture for a sprite.
However, there is a severe performance drawback. Each PIXI.Text instance obviously produces a new texture, leading to many draw calls if there are lots of texts on the scene.
PIXI.BitmapText
I have switched to PIXI.BitmapText. It expects you to provide a font preprocessed into an image (also called texture atlas) with all supported characters + font descriptor file defining coordinates of each character in the image (example). The image is used as a shared texture, and any text is rendered by drawing separate characters next to each other from the texture with alpha test 0.5.
There is one caveat of bitmap format to keep in mind. The bitmap image must be pre-rendered with the maximum resolution used for the text font size, potentially even larger if you allow your users to zoom in. Scaling the text beyond pre-rendered resolution produces pixelated text.
Distance Fields
The last and most flexible technique uses a font preprocessed into a distance field and stored in Signed Distance Field (SDF) or more recent Multi-channel Signed Distance Field (MSDF).
In bitmap format, each pixel encodes only if the pixel is inside or outside the shape. In distance fields, each pixel encodes the distance from the shape edge. The significant benefit of distance fields is that you can scale from low resolution to higher resolutions for rendering with no pixelation.
SDF format encodes the distance in shades of gray. If you open SDF image, don’t get confused that the image looks blurry, it’s only the effect of that 50% gray effectively means the shape edge, >50% means inside, <50% means outside.
When you scale SDF text a lot, you start noticing chipped or rounded corners instead of sharp corners. To fix this, either you can increase the resolution of the pre-rendered SDF image, or switch to MSDF.
MSDF format encodes the distance in all three color channels, and for each pixel, all color channels participate in the decision that the pixel is inside or outside of the shape. If you open MSDF image, it looks really funky, but don’t be afraid. There are clever tricks behind it.
There is pixi-sdf-text plugin for PIXI.js implementing text rendering from both SDF and MSDF formats. Unfortunately, it supports only PIXI.js v4. It hasn’t been upgraded to PIXI v5 yet. This is an opportunity to be contributed by the first engineer who strongly needs it :)
Final words
There are many ways of how the performance of a custom graph visualisation can be improved. This is an excerpt of techniques I have added to my live demo of graph visualisation in PIXI.js, and I’m exploring further options.
Of course, if your use case or engineering capacity doesn’t allow you to spend time with low-level graphical rendering, a great choice is ready-to-use commercial libraries (Keylines, Ogma, yFiles, in alphabetical order). They already solved all the complexities, expose high-level methods that can be used immediately, and provide quick support.
Also, I have recently switched to continue my journey as an independent consultant. If you have an interesting problem to solve, don’t hesitate and drop me a line!
