Quid strives to power human intuition by delivering vast quantities of data and their connections through network visualizations. Those networks are usually made of nodes and edges. Lots of them. To enable our customers to visualize, navigate and manipulate these big networks in their browser, a question naturally arises: how can we render those nodes and edges as fast as possible?

WebGL To The Rescue

WebGL lends the power of the computer’s GPU to the web browser which affords processing large amounts of geometric data quickly in parallel. However, WebGL’s rather rudimentary set of APIs focused largely on drawing points, lines, and triangles, which makes our life difficult when drawing curved edges.

Rendering edges with lines is quickly rejected due to the WebGL’s poor support of line endings and joints1. What if we draw triangles? First thought in mind would be to divide the curve into multiple segments and fit each of them with a quadrilateral (quad), which is rendered as two triangles. We increase the number of segments until the curve is smooth enough. Bartosz Ciechanowski describes this approach in his article “Drawing Bézier Curves”2. Although this would work if we had only tens or hundreds of edges to draw, it is simply unrealistic to render tens of thousands of edges and still have each of them retain the same level of smoothness.

To reduce the amount of geometries WebGL draws, we turn to transparency. Instead of drawing a strip of triangles to fit the curve, we draw a single quad, and make every pixel that does not belong to the curve transparent. The following 3-nodes network illustrates this technique. On the left, note the actual curve has the same color as background, and the transparent pixels which would be eventually invisible are in red. The actual rendering of the network is displayed to the right.

Looks like we have solved our problem. We draw very few geometries and are able to produce the smooth curve you see in Quid’s networks!

Overdraw Kills Performance

Our network rendering performed decently when more sparse, which typically was less than 5000 nodes. But it started to slow down when dealing with larger networks, especially on computers with weaker graphics capability. It may seem natural larger networks perform worse than smaller networks, but consider modern realtime 3D applications easily render millions of triangles per frame, WebGL, having derived from OpenGL, should easily handle ten thousand triangles on a Macbook with a dedicated graphics card.

What was dragging frame rate down? After analyzing the possible bottlenecks throughout the rendering pipeline, it seems that we were not limited by how many triangles we draw, but how many pixels. For each edge, only pixels within the boundary of the curve, a fraction of total pixels drawn, are actually visible in the final image, other pixels, being completely transparent and therefore not visible eventually, still have to run the fragment shader to obtain a (unused) color and thus have a cost associated!

Consider a network that appears to be as follows:

1000 nodes network

A network with about 1000 nodes

Recall that we mark the pixels lying inside the boundary of the curve opaque (0% transparency) and other pixels transparent (100% transparency). If we reverse the transparency of edge pixels to see only pixels that are NOT visible in the end, this is what we get:

Render transparent pixels for the same network

Render transparent pixels for the same network

This shows how many pixels we are wasting precious GPU power to draw only to make it transparent and get the same color as background! To make matters worse, the transparent pixels in an edge occupies so much area that it is very likely to overlap with the transparent area from another edge, which overlaps with yet another edge. The actual wasted transparent pixels are, as a result, many times what is shown in the image. Since GPU can only draw so many pixels in a given amount of time, those extra pixels will have to wait, and therefore reducing frame rate.

A Compromise

We know we can’t draw too many triangles nor too many pixels. What do we do? Well, we make compromises and try to get the best from both worlds. If we are allowed to draw a reasonable number of triangles instead of just 2 in the case of a single quad, we would be able reduce the average height of the triangles, thus having a lower percentage of transparent pixels in an edge. In the meantime, we maintained the ability to draw smooth curves without having too many triangles.

image1

The Result

To give a rough perception of how many transparent pixels we have saved from drawing, we follow what we have done before and render only the transparent area of edges. As you can see, a massive reduction of those pixels are clearly visible!

Zoomed-out view:

In terms of frame rate, we noticed an increase from around 10-15 FPS to 30-35 FPS in the densest area of a large network (7000 nodes), running on a MacBook Pro with a moderate GPU at a 3840 x 1824 resolution canvas. For smaller networks, the performance boost is most noticeable on weaker machines, such as those without a dedicated GPU.

The following videos are captured on a relatively weak MacBook Air with only integrated GPU.

Pre-optimization:

Post-optimization:

End Notes

We sped up rendering by balancing the load between geometry rendering and pixel rendering. Both now run at optimal efficiency without one waiting for the other which slows down the entire pipeline.

Looking ahead, we have more optimization planned for our rendering performance. An example would be to extend what we have done here, and make the number of segments/triangles used for rendering an edge vary with edge length and thickness. For longer edges, decomposing them into more segments will enable us to shrink the width of each segment even further and for shorter edges, fewer segments may suffice without drawing too many transparent pixels. So stay tuned for a better, faster graphics engine!

References

1. Drawing Lines is Hard
2. Drawing Bézier Curves


Interested in helping us solve awesome problems? If so, then head over to our careers page!