Browse Prior Art Database

Parallel Line Anti-Aliasing Algorithm

IP.com Disclosure Number: IPCOM000111403D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 6 page(s) / 177K

Publishing Venue

IBM

Related People

Narayanaswami, C: AUTHOR [+2]

Abstract

"Anti-Aliasing" is a technique to mitigate the artifacts produced by representing lines by point sampling on a raster pixel grid [1,2,3]. This problem occurs while drawing simple lines on a raster display because a pixel is either turned on or is turned off and there are no intermediate states for the pixels. This problem is often referred to as "jaggies" in the non-technical domain. This article describes a parallel algorithm to draw anti-aliased lines on a raster display.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 35% of the total text.

Parallel Line Anti-Aliasing Algorithm

      "Anti-Aliasing" is a technique to mitigate the artifacts
produced by representing lines by point sampling on a raster pixel
grid [1,2,3].  This problem occurs while drawing simple lines on a
raster display because a pixel is either turned on or is turned off
and there are no intermediate states for the pixels.  This problem is
often referred to as "jaggies" in the non-technical domain.  This
article describes a parallel algorithm to draw anti-aliased lines on
a raster display.

Prior Art

      One solution to this problem is to use exact area sampling
where the intensity of the pixel is proportional to the area of the
pixel covered by the line.  Another approach is to use
"post-filtering" which low-pass filters the image.  The latter
approach is more suited for removing high-frequency noise in image
processing applications because often a complete image is processed
in "batch mode" and therefore all pixels in the image are processed
together.  However, in computer graphics applications the image is
created by rendering objects in order and very often far more pixels
in the image are covered by the background than by the objects.
Since post-filtering depends on the resolution of the image and exact
area sampling depends on the number and size of the objects being
drawn, it is computationally more efficient to use an approximation
to exact area sampling than to do post-filtering.

      The commonly used approximation to exact area sampling is shown
in Fig. 1.  The anti-aliased line is treated as a one-pixel-wide
rectangle with its centerline coinciding with the ideal geometric
line.  The intersections of the dashed lines are the centers of the
pixels.  The dark lines are the boundaries of the pixels.  For exact
area sampling, the intensity of the pixel whose center is C1 should
be proportional to the area a1a2a3a7 and the intensity of the pixel
whose center is C2 should be proportional to the area a7a6a5a4a3.

      The approximation to exact area sampling uses an approximation
to the slope of the line and approximations to the distances C1e and
C2e for computing the areas of the pixels with centers C2 and C1 that
are covered by the one-pixel-wide line.  The point of intersection
between the centerline of the one-pixel-wide line and the vertical
centerline of the pixel grid (Fig. 1).  A look-up table indexed by
the slope s and distance d is created to determine the coverage of
the pixel approximately.  Henceforth, we shall refer to distances
C1e, etc., as intercepts.

      In order to avoid artifacts, such as brighter pixels, at the
vertices of closed anti-aliased polylines, the first and last pixels
of individual lines are drawn with half their intensity.  Since two
contiguous lines in a closed polyline share a vertex, the pixel
chosen to represent the vertex will get a fraction of its intensity
from the first line and the rest from the second line sharing the
ver...