Drawing

Performance test

drawing.js is a graphics library I'm developing for use in simple 2D demos. Most of the graphics libraries available are heavy in terms of size and dependencies. drawing.js on the other hand is designed be a simple, single file library that supports a wide variety of shapes, high resolutions, and even embedded fonts.

The library is modeled after javascript canvases. Everything from polygons, to circles, to letters are composed of just 2 things: lines and bezier curves.

Loading javascript...

Defining Shapes

Defining even simple polygons programmatically can be tedious, so the library allows SVG path notation: M move to, L line, C curve, Z close path. This allows us to make use of SVG editors (like yqnn's) to easily define polygons. Using this notation we can draw a simple cat:

M 0 0 L 250 250 L 750 250 L 1000 0 L 1000 700 L 500 1000 L 0 700 Z M 500 683 L 394 727 L 396 732 L 500 689 L 604 732 L 606 727 Z M 190 398 C 207 487 327 512 395 450 Z M 605 450 C 673 512 793 487 810 398 Z

Left shows the control points, right shows the final result.

In addition to geometric shapes we can represent letters, numbers, and symbols as SVG paths. At 5 lines and 22 curves, this is the most complex character in drawing.js - as expected of a real g.

M 538 267 L 538 340 L 454 340 C 467 353 485 385 485 433 C 485 548 395 614 284 614 C 239 614 212 607 177 590 C 166 605 154 622 154 646 C 154 673 182 690 218 692 L 372 698 C 467 702 536 750 536 828 C 536 933 439 1000 281 1000 C 156 1000 48 966 48 866 C 48 806 85 771 120 745 C 103 739 68 711 68 662 C 68 620 90 585 122 548 C 93 516 80 486 80 438 C 80 333 160 258 282 258 C 315 258 332 262 350 267 Z M 282 547 C 350 547 395 497 395 436 C 395 385 363 325 282 325 C 238 325 171 353 171 436 C 171 524 245 547 282 547 M 200 770 C 176 788 143 810 144 857 C 143 911 216 930 289 929 C 400 928 441 879 440 838 C 439 794 397 776 339 775 Z

Optimizations

Curve Segmentation

The cubic bezier curves we use are represented as cubic polynomials. This makes determining what pixels they overlap computationally expensive. Instead, the curves are decomposed into lines immediately before rasterization. This conversion ends up being faster and simpler than rasterizing the curves directly.

A good segmentation algorithm will create the fewest lines possible while closely approximating the curve. drawing.js does this by picking 3 points on a section of the curve and finding their distance to the line. If the distance is too great that section is split. We continue doing this until all lines are close enough to the curve.

Pixel Runs

While processing each line on a row, we can calculate how many pixels we are able to draw (or skip) before reaching the next line. This allows us to skip empty portions of the polygon and also enter a tight loop to allow the polygon filler to focus on drawing pixels.

Line Ends

When calculating pixel coverage, one of the biggest optimizations comes from noting that lines that span multiple pixels on a row can be divided into 3 sections: a beginning, middle, and end. Since the middle section's area will change at a constant rate (depending on the slope), we can skip calculating area coverage - we just need to add a constant value to the area as we process each pixel along the row. This means that the worst case complexity per row can be reduced from width*lines to 2*lines. We only need to calculate the non-constant area changes at each end of the line.

Heaps

The filler needs to keep track of where each line starts and ends on each row to determine where to draw and where to skip. In order to efficiently keep track of all these lines, which can easily number in the hundreds, the filler uses a binary heap to track on what pixel a line starts. To determine where to draw next, we pop the top entry off the heap and jump to that row and column. We then look at the next entry to determine how far we can draw before we encounter another line. This allows log(n) complexity when managing lines.

Line Caching

Although a binary heap makes managing lines efficient, it still eats up about 29% of fillpoly's run time. Mathematically, we would expect shorter lines (per row) to be more common, and this is what I also observed. In order to reduce the time spent on these short lines, I expanded the variables used in the Line Ends section to handle 2 pixel wide lines. This ended being as fast as the basic 1 pixel wide algorithm while being more complex, so it was abandoned.

Bounding Boxes

Ideally, we'd like to avoid drawing as many polygons as possible. To do this, when building an SVG path, we also keep track of the axis aligned bounding box around its points. When it's time to draw, we apply any transforms to this bounding box and can easily determine if this oriented box overlaps the screen. If it doesn't we skip drawing altogether in O(1) time.

WebAssembly

One attempt at speeding up polygon filling was by using webassembly. In good conditions, it offers a 1.2x to 2.0x speed up in browsers. The downsides are needing to move images to the sandboxed WASM memory, maintain a separate version of fillpoly, and handle the scaffolding to support swapping to WASM during runtime. Currently drawing.js has WASM module removed until it becomes faster.

Pixel Blending

Pixels on the edge of the polygon might not be entirely covered by the polygon. When this happens, we don't want to completely replace the background pixel's color. Instead, we want to blend it with the polygon's color. This can be incredibly slow due to the math involved. The fastest algorithm I've found so far involves using imul to blend multiple rgb components at once:

src = polygon color
lh  = (src&0x00ff00ff)>>>0;
hh  = (src&0xff00ff00)>>>0;
hh2 = hh>>>8;


a   = alpha in [0,256]
col = img[i];
col = (((Math.imul((col&0x00ff00ff)-lh,a)>>>8)+lh)&0x00ff00ff)+
      ((Math.imul(((col&0xff00ff00)>>>8)-hh2,a)+hh)&0xff00ff00);

Alpha Tables

In order to speed up pixel compositing, I looked into precomputing the source and dest alpha values. Ultimately, it was as fast as direct computation while being more complex, so it's been abandoned.