Scanline edge-flag algorithm for antialiasing

Created: 2021-01-28T18:58:19-06:00

This card pertains to a resource available on the internet.

Multisampling: when content is rendered to a canvas of a larger size and scaled down

Edge-flag: a 1-bit bitmap is used to mark where individual scanlines should be filled and when filling should stop

Scanline: a physical "line" of the output image

Subpixel scanline: a partial scanline, for example in 8x antialiasing each scanline actually has 8 "subpixel scanlines."

Kallio's algorithm does not require multisampling.

Naive implementation is to keep using 1-bit bitmaps but do but shuffling/masking which is slower. Kallio changes so 1 byte = 1 pixel, but each bit represents if the mark exists in that 8x supersample.

Plotting edges with supersampling

offset[8] <- [0.25, 0.875, 0.5, 0.125, 0.75, 0.375, 0, 0.625]
x <- x0

∀ y between y0 to y1
xi <- FLOOR(x + offset[y mod 8])
bits[y, xi] <- XOR(1, bits[y, xi])
x <- x + dx

This only works with "even odd" fills; that is, rendering shapes that require non-zero winding does not work.

Adaptation to support non-zero winding

Temporary map now stores edge directions as +1 or -1, sums these for each pixel. Counters can be stored as 7-bit which are masked when doing operations that could make them overflow.

QUINN: sounds like you should take care of cutting paths before you get to this point so there is no zero winding... maybe there is a good reason this is not done.

Edge table; scanline optimization

Keep an edge table; a list of edges for each scanline.

Each node stores:

beginning and end y coordinates for the edge
current x value
current x increment per subpixel scanline
value for ascending/descending edge, if the table is using the zero-winding rule

Generating the edge table

y0 and y1 for a polygon are first and last subpixel scanlines the edge crosses

starting x is the x value at the crossing of the first subpixel scanline

x increment is (x1 - x0)/(y1 - y0)

direction is optional (only needed if zero windings are needed.) set to 1. if y1 < y0, set to -1 and swap start/end points.

Clipping

Polygons should be clipped to the canvas. If you have a polygon clipping layer then use that first.

Otherwise perform clipping when generating the edge table.

Optimization

Avoid floating points; fixed integers to avoid conversion overhead
Work only on the region the polygon actually occupies to reduce bookkeeping pixels that wont be written
Use scanline & edge table since edge node can be kept in cache memory when plotting a single scanline
Calculate mask values only where data on the temporary canvas exists; ex. if inside a polygon then don't re-calculate until you reach an edge
Loop unrolling

Sampling patterns

n-rooks sampling: determining which sample offsets by modeling them as rooks on a chess board, then distributing the rooks, and the placement of the rook becomes the offset that bit represents.

Discrepency: a measure of "sample point equidistribution"

Optimize sample positions over: Sum of squares of minimum distances between sample points

A sampling pattern determines where an edge must be to trigger that particular bit in the multisampling point.

Points are then offset by a small amount for each sample. If the offset still crosses that bit's sample threshold then it will activate.

N-Rooks problem

Other references

A related winding counter method has been used by Herf [Her97] for rendering soft shadow polygons.

Also Aila et al. [AM04] have used similar method for rendering masks for occlusion culling.