Copy Link
Add to Bookmark
Report

Efficient Antialiasing

DrWatson's profile picture
Published in 
atari
 · 2 months ago
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)

}
}

[1] Fujimoto, A., and K. Iwata, "Jay-free Images on Raster Displays" IEEE Computer Graphics and Applications, 3(9):26-34, December 1983

[2] Wu, X., "An Efficient Antialiasing Technique," Computer Graphics, SIGGRAPH 1991 Proceedings, 25(4):143-152

← previous
next →
loading
sending ...
New to Neperos ? Sign Up for free
download Neperos from Google Play

Latest Articles

Recent comments

Neperos cookies
This website uses cookies to store your preferences and improve the service. Cookies authorization will allow me and / or my partners to process personal data such as browsing behaviour.

By pressing OK you agree to the Terms of Service and acknowledge the Privacy Policy

By pressing REJECT you will be able to continue to use Neperos (like read articles or write comments) but some important cookies will not be set. This may affect certain features and functions of the platform.
OK
REJECT