Efficient Antialiasing

@DrWatson

Published in

atari

· 30 Nov 2023

24.july.1997
GFX

by Hin Jang

Increasing the sampling rate or removing the high frequency components of an image are two ways of limiting the effects of aliasing. Both methods, however, have high rendering costs. An incremental algorithm that is derived in the spatial domain under a subjectively meaningful error term is described herein. Its simplicity suggests a practical hardware implementation and produces the same pixels as Fujimoto-Iwata's algorithm at a fraction of the latter's computational cost [1, 2].

Let y = f(x) be a curve digitised in the raster plane. Sampling in a scan coherent fashion requires that for every pixel along the x axis, the sample value f(i) is quantised to some integer Yi. A dynamic error arises if

   | f(i) - Yi | > 0

In trying to mimimise the loss of dynamic information, thus producing a more appealing image, an antialiasing technique should aim to perserve the convexity of the curve. This is achieved by applying the following two-point scheme.

For a given value of (i, f(i)) the ideal addressable pixel may be visually simulated by defining

        I[i, floor(f(i))]   = Io[ceiling(f(i)) - f(i)] 
        I[i, ceiling(f(i))] = Io[f(i) - floor(f(i))]

where I[i,j] is the intensity of pixel (i,j) and Io is the intended intensity of the curve at (i, f(i)). If pixel (i,j) is a considered a unit square centered at (i,j) then pµ = (i, f(i)) is the center of gravity of the two points

        p0 = (i, floor(f(i))) 
        p1 = (i, ceiling(f(i)))

because

        Iopµ = I[i, floor(f(i))]p0 + I[i, ceiling(f(i))]p1

The lit area Io is focused at pµ, the perceived pixel exactly on the original curve.

Given a line in the first octant, let (x0, y0) and (x1, y1) be the endpoints of the line where x1 > x0 and y1 > y0. If the line is defined as f(x) = kx, the equations of the two-point antialiasing scheme can rewritten as

   I[x, ceiling(kx)] = I0[kx - floor(f(i))] 
   I[x, floor(kx)]   = I0 - I[x, ceiling(kx)]

The values of (x, floor(kx)), (x, ceiling(kx)), and their intensities I(x, floor(kx)) and I(x, ceiling(kx)) can be determined using an incremental algorithm operating on a single integer D, a machine word of n bits [2]. As initial values, D = 0 and I(x0, y0) = I. The increment of D is

   d = floor(k2n + 0.5)

where the overflow of D = D + d is recorded. When D overflows, the two-point pixel band moves diagonally; otherwise it moves horizontally. Given 2m - 1 discrete grey-scale intensity levels,

   I(x, ceiling(kx)) = I0(kx - floor(kx)) 
                     = (2m - 1)(D2-n + (k - d2-n)x) 
                     = D2m-n + (2m - 1)(k - d2-n)x - D2-n

Assuming n > m, the intensity can be approximated by the first term; the m most significant bits of D. Given that Io = 2m - 1, the integer 2m - 1 - D2m-n is the inverse of D2m-n. As such, I(x, floor(kx)) is the bitwise inverse of I(x, ceiling(kx)).

   Line() 
   { 
      PutPixel(x0, y0, I) 
      PutPixel(x1, y1, I) 
      D = 0 
      k = (y1 - y0) / (x1 - x0) 
      d = floor(k * 2^n + 0.5) 

      while(x0 < x1) { 

         x0++ 
         x1-- 

         D = D + d       /* module 2^n addition */ 

         if (D overflows) { 
             y0++ 
             y1-- 
         } 

         I = D div 2^(n-m) 
         PutPixel(x0, y0, I) 
         PutPixel(x1, y1, I) 

         I = ~I          /* bit-wise inverse */ 

         PutPixel(x0, y0+1, I) 
         PutPixel(x1, y1-1, I) 
      } 
   }

It suffices to consider one octant of the circle x^2 + y^2 = r^2 to extend the two-point antialiasing scheme for this primitive. The pair of pixel intensity equations is then

   I(floor(h) ,j)   = I(ceiling(h) - h) 
   I(ceiling(h), j) = I - I(floor(h), j)

where

   h = sqrt(r2 - j2) 
   1 <= j <= r / sqrt(2)

To move the pixel band to the left by one step, assuming scan-conversion occurs in the y axis from 0 to r / sqrt(2), the critical values of t in

   ceiling(sqrt(r2 - (t - 1)2)) - ceiling(sqrt(r2 - t2)) = 1

must be computed. Wu showed that the equation holds if and only if

        ceiling(sqrt(r2 - (t - 1)2)) - ceiling(sqrt(r2 - t2)) > 
        ceiling(sqrt(r2 - t2)) - sqrt(r2 - t2)

[2]. As such, for given values of r,

   ceiling(h) - h,  1 <= j <= r / sqrt(2)

determines the pixel positions and pixel intensities. For an intensity range from 0 to 2m - 1,

   D(r, j) = floor((2m - 1)(ceiling(h) - h) + 0.5)

which gives rise to

   I(floor(h), j)   = D(r, j) 
   I(ceiling(h), j) = bitwise-wise inverse of D(r ,j)

since

   I(ceiling(h), j) + I(floor(h), j) = I = 2m - 1

A D(r,j) table is used to facilitate the speed of the algorithm. If RMAX is the maximum allowable radius, the table size is sqrt(2) / 4 * RMAX The two-point antialiasing scheme for circles can also be realised at the hardware level.

   Circle() 
   { 
      i = r 
      j = 0 
      PutPixel(i, j, I) 
      T = 0 

      while (i < j) { 

         j++ 

         if (D(r, j) > T) 
             i-- 

         I = ~D(r, j)    /* bit-wise inverse */ 

         PutPixel(i, j, I) 
         PutPixel(i-1, j, D(r, j)) 
         T = D(r, j) 

      } 
   }