Efficient Anti-aliasing Algorithm For Computer Generated Images

Efficient Anti-Aliasing Algorithm for Computer Generated Images Tsuyoshi Isshiki and Hiroaki Kunieda Dept. Electrical and Electronics Engineering Tokyo Institute of Technology 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552, JAPAN [email protected], [email protected]

Abstract

detection and calculation of pixel blending ratio is significantly simpler and more effective than that of the Anti-aliasing is one of the most important process for previous post-filtering approaches. It is also well-tuned generating high quality 3D graphics images. There have for efficient hardware implementation for real time combeen many approaches for anti-aliasing but few consider puter graphics. the real-time processing constraints which is critical for various interactive graphics applications. In this paper, Pixel Connectivity we propose a very powerful but simple method for anti- 2 aliasing called double line scanning method which is suitWe define the color intensity difference of two pixels Pa able for low cost hardware implementation. and Pb as follows:

d(Pa,Pb)= lP," -

1

Introduction

Although the computational power of current microprocessors and 3D graphics hardwares enable fast graphics image generation, there are strong demands for next generation graphics platform which supports high quality real time graphics rendering. Anti-aliasing, especially, is one of the crucial task for such high quality graphics rendering which deals with the 'saggy edge" effect of computer generated images. Several methods on antialiasing are present t o date [l] [2] [3] [4]. A popular supersampling approach generates the image at subpixel resolution and averages the color intensity on each pixel region. The drawback of this approach is the high computational cost t o generate the image at subpixel resolution. Another approach is by post-filtering the generated graphics image [3] [4]. It estimates the shape of the objects on the generated image, and calculates the pixel blending ratio on the edge pixels. The advantage of this approach is that the computational cost is significantly less than other anti-aliasing approaches, and it can be totally isolated from other graphics rendering tasks. In this paper, we propose a new anti-aliasing method called double-line scanning method. It is based on postfiltering approach which detects object edges on two line buffers, estimates the edge slope and calculates the pixel blending ratio for the edge pixels. Our method of edge

IP," - PSI -k lp," - PFl (1)

where P,", P,", P," are the RGB values of pixel P,, respectively. We say that the pixels Pa and Pb are connected if d(P,,Pb) is below a predefined threshold T, otherwise we say they are disconnected. Also, a connected region is a group of orthogonally adjacent pixels where the color intensity difference between any two adjacent pixels is below the threshold T . A jaggy is thus defined as the boundary of such connected region which has staircase pattern. From a 2D image, horizontal and vertical pixel connectivities are first extracted and stored in two arrays of Boolean value:

c h ( i , j ) = d(p,,J,P*,J-l) < T, c v ( i , j ) = d(P,,J,p,-l,J)< T

(2)

where P,,J is the pixel color value at ( i , j ) , c h ( i , j )is the horizontal pixel connectivity, and cv(i,j ) is the vertical pixel connectivity.

3

Jaggy Extraction Algorithm

Jaggies are extracted by two phases: jaggies whose slope is between -45" and 45" angle are extracted by horizontally scanning two adjacent rows of pixels, and jaggies whose slope is between 45" and 135' angle are extracted by vertically scanning two adjacent columns.

0-7803-5471-0/99/$10.0001999IEEE

IV-532

j-1

j-1

j

i

j-1

j

i

i-1

i-1

if cv(i, j-1 j=1 andch I J) 1 and ch[;-; =0 openingti) :I UP

,E

j-1

i-1

if cv(i, j-1) = 1 and ch(i-1, j) = 1 and ch(i, j) E 0 openingti) :I DOWN

j

j-1

i

otherwise openingu) := NULL j-1

j

i

i-1

j

Figure 3: Simple line fitting.

i

i-1

if cvfi. i) = 1 and c@-1, j) = 1 and ch(i, j) = 0 closingti) := UP

j

i

i-1 if cv(i. i) = 1 and cwi, j)) = 1

and ch(i-1, j) = 0 closingti) := DOWN

El otherwise

closing(j) := NULL

(a) Simple line fitting

Figure 1: Shapes of connected region on the scanning points. jaggy-head

(b) Our smooth line fitting

Figure 4: Comparison of simple line fitting and our smooth line fitting.

jaggy-tail

case, assign jaggy-tail := closing(j). And also: if (jaggy-head = UP and jaggy-tail f DOWN or jaggy-head # DOWN and jaggy-tail = UP) jaggy-shape := "INC".

0 0

else if (jaggy-head = DOWN and jaggy-tail # UP or jaggy-head # UP and jaggy-tail = DOWN) jaggy-shape := "DEC".

0

If c v ( i , j ) = 1, there are no pending jaggy. Else if c h ( i , j ) = 0 and c h ( i - 1 , j ) = 0, then a new jaggy has started at j . In this case, assign jaggy-head := opening(j).

Else another jaggy is pending.

The shape of the jaggy is then determined by jaggy-head and jaggy-tail as shown in Fig.2.

else if (jaggy-head = UP and jaggy-tail = DOWN) jaggy-shape := "MAX".

4

else jaggy-shape := "MIN"

Figure 2: Jaggy shape evaluation. When scanning the two pixel rows i and i - 1 horizontally from left to right, we first detect the starting point of the jaggy, and then detect its termination. Detection of the starting point and termination point of a jaggy as well as its shape are determined by the shapes of the connected region at each scanning point j as shown in Fig.1 (denoted as o p e n i n g ( j ) and c l o s i n g ( j ) ) . Here, the conditions for detecting the start of jaggy and the termination of jaggy are: 1. If jaggy is not pending, and o p e n i n g ( j ) # N U L L , then jaggy starts at j . In this case, assign jaggy-head :=

opening(j). 2. If jaggy is pending, and c v ( i , j ) = 1 or (jaggy-head =

U P and c h ( i , j ) = 0) or (jaggy-head = D O W N and c h ( i - 1,j)= 0), then jaggy has terminated at j. In this

Smooth Line Fitting Algorithm

After the jaggy has been extracted and its length and shape evaluated, we need to calculate the jaggy slope and the pixel blending ratio at each pixel on the jaggy. Bloomenthal[3] and Overveld[4] use a simple line fitting method which is illustrated in Fig.3. In the case of Fig.3(a), the jaggy slope is determined solely by the jaggy length (1 / j a g g y - l e n g t h ) , and the line is positioned so that it crosses the jaggy boundaries at half way point which makes the fitted lines on the adjacent jaggies to be continuous at the jaggy boundaries. In the case of Fig.3(b), it is considered as horizontal edge and thus a horizontal line is fitted. The problem of this simple line-fitting algorithm is that the slope of the fitted line can only be the inverse of integers (1,1/2,1/3,. . .), therefore the accuracy of the fitted line is quite limited. Especially when the actual edge slope is close to 45", jaggy cannot be effectively removed. Also, fitting a horizontal line in the case of Fig.3(b) can cause unnatural appearance since the original edge may actually be continuing from the left jaggy. In order to deal with these problems, we use the length information of three adjacent jaggies t o determine the

IV-533

Pixel Blending Ratio Calculaline slope of the middle jaggy. Let IO and 11 be the 5 starting point and the termination point of a jaggy at t ion rows i and i - 1, and let L be the jaggy length ( L := 21 - 20 1). If the jaggy shape is “INC”,then After the fitted lines are calculated, we need to compute the blending ratio of the pixels on the jaggy. When 1. If there is an adjacent jaggy terminating at 20 - 1 whose the fitted line equation is given as in eq.(3), the blendshape is “INC” with a length of Lo, then ing ratio between the two vertically adjacent pixels on rows i - 1 and a becomes b ( j ) := ( j - d0/3 1/2)/(L 1 (Lo > L ) d o / 3 d1/3) where j = 0,1, ,L - 1 and 0 < b ( j ) < 1. 0 (Lo = L ) b ( j ) can be obtained by calculating the gradient db := 1/(L d 0 / 3 d1/3) and b(O), and then simply accuelse do := 0. mulate db: i.e. b ( j + 1) := b ( j ) db. Here, we have + 1 whose obtained that 6 bits for representing the blending factor 2. If there is a adjacent jaggy starting at is enough without any noticeable difference compared shape is “INC” with a length of L1, then with floating-point representation. Let n be the number of bits to represent the blending factor. Following 1 (L1 > L ) describes the blending ratio calculation which adopts in0 (L1 = L ) cremental linear interpolation algorithm [5].

+

+

+ +

+

a . .

+

+

Blending Calculation(L, do, d l ) : W := 3L do dl. N := 3 . 2 ” . q := LN/Wj. r := N mod W . a := 0. c := q/2 do . 12”/Wj. For j = 0 to L - 1 b ( j ) := c . c:=c+q. a := a + r . If a 1 W, then a :=a - W . c := c + 1. Here, q and T are the quotient and the remainder of N

+ +

else d l := 0. 3. Set the line equation as

+

.

Similar calculation is done for the case when the jaggy shape is “DEC”.Important point here is that we modify the length of the jaggy by f 2 / 3 , f 1 / 3 or 0, depending on the length of the adjacent jaggies. In this way, we can increase the accuracy of the fitted line (line slope can now have the values 1,3/4,3/5,3/6,3/7,. . .), and further reduce the aliasing effect especially on edges near divided by W . The term c := q / 2 do . L2”/W] calcu4 5 O angle. lates the initial value of the blending factor b ( 0 ) . Then Next, if the shape is “ M A X ” , at each iteration, q and r are accumulated in c and a, 1. If there is a jaggy terminating at 20 - 1 with length LO, respectively, and when a becomes larger than W , c is then let f o ( z ) := (z - 20 + 1/2)/Lo + i - 1. Otherwise incremented by 1. These operations avoid the exact diLO:= 0 and fo(z) := i - 1. vision of N / W by evaluating the accumulated remainder 2. If there is a jaggy terminating at 2 1 + 1 with length L1, a. Values LN/WJ,N mod W , and L2n/WJ can be prethen let f l ( z ) := -(z - 2 1 - 1/2)/L1 + i - 1. Otherwise computed and stored in a lookup table. When n = 6, only 3 . 26 2 = 194 entries are needed in the lookup L1 := 0 and fl(z) := i - 1. table.

+

+

3. If Lo

> 1 or L1 > 1, then set the line equation

as

6

Results

else

Here, we show the results of our anti-aliasing method on a 3D graphics image. The original image is shown in Similar calculation is done for case when the jaggy shape Fig.5, where the image size is 400 x 400. In Fig.6, the reis “ M I N ” . Here we simply extend the fitted lines on the sult of anti-aliasing using our method is shown, where all left and right of the jaggy to the middle jaggy region. the visible jaggies have effectively been smoothed withFig.4 shows the comparison of simple line fitting and out causing any blurring of the details. Here, the blending factor is represented using 6 bits. our modified smooth line fitting. y =i

- 1/2.

IV-534

Figure 5: Original graphics image without anti-aliasing. Figure 6: Graphics image processed with our antialiasing method.

7

Summary ACM, ~01.20,pp.799-805, 1977.

In this paper, we have presented an efficient yet very effective method for anti-aliasing computer generated images. Its features are:

1. We first convert the pixel color information into pixel connectivity matrix which are represented by a single bit, therefore reduced the memory bandwidth requirement considerably. 2. Jaggy extraction is done merely by scanning the two pixel rows horizontally and vertically with a series of simple logic operations which is well suited for hardware implementation. Note that horizontal scanning and vertical scanning can be done simult aneously.

3. We developed an effective line fitting algorithm which smoot hes the jaggies more effectively than the conventional line fitting method. 4. We developed an efficient pixel blending ratio calculation method by adopting incremental linear interpolation algorithm which does not require division and therefore ideal for hardware implementation.

References [l] F.C. Crow, “The Aliasing Problem in ComputerGenerated Shaded Images”, Communication of the

IV-535

L. Carpenter, “The A-Buffer, an Anti-Aliased Hidden Surface Method”, ACM Proc. SIGGRAPH 18, pp.103-108, 1984. J. Bloomenthal, “Edge Inference with Applications to Anti-Aliasing” , ACM Proc. SIGGRAPH .I 7, pp.157-162, 1983.

C. van Overveld, “Application of Morphological Filters to Tackle Discretisation Artefacts”, Visual Computer, vo1.8, pp.217-232, 1992. D. Field, “Incremental Linear Interpolation”, ACM Trans. Graphics, vo1.4, pp.1-11, 1985.