Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!rutgers!sri-spam!sri-unix!hplabs!turtlevax!ken From: ken@turtlevax.UUCP (Ken "Turk" Turkowski) Newsgroups: net.graphics Subject: Re: Possible way of anti-aliasing. Message-ID: <1234@turtlevax.UUCP> Date: Tue, 7-Oct-86 03:37:39 EDT Article-I.D.: turtleva.1234 Posted: Tue Oct 7 03:37:39 1986 Date-Received: Wed, 8-Oct-86 06:40:45 EDT References: <280@joevax.UUCP> <265@hoqam.UUCP> <7706@sun.uucp> <109@pixar.UUCP> Reply-To: ken@turtlevax.UUCP (Ken "Turk" Turkowski) Distribution: net Organization: CIMLINC, Inc. @ Menlo Park, CA Lines: 193 In article <109@pixar.UUCP> ph@pixar.UUCP (Paul Heckbert) writes: >The theoretically "correct" approach is (b), however: analytic antialiasing. >Algorithms have been developed for simple objects such as lines and >polygons, but analytic antialiasing of curved surfaces is an open problem. Anti-aliasing of circles is relatively easy: all you need to do is compute the distance from a pixel to the center of the circle, and subtract this from the radius of the circle. This value is then used to index into the table used for lines, in the previously referenced paper (in an acompanying USENET article). An incremental method for calculating the distance to a circle is given in the enclosed text (I call it circle.e). eqn circle.e | itroff -ms to read it. It requires a couple of additions and a division at each step. ----------------------------------------------------------------- .TL Anti-Aliased Circle Drawing .AU Ken Turkowski .SH Introduction and Prior Art .PP The problem we here pose is how to calculate anti-aliased circles. From our familiarity with lines, we feel that a possible key to this problem is the distance from the circle to an arbitrary point. .PP One obvious way to do this is to calculate the Euclidean distance of an arbitrary point to the center of the circle, ans subtract from this the radius of the circle. This involves two multiplications and a square root at each point we visit, giving us a calculation time of approximately 4 multiplications. .PP Additionally, we would like to calculate the arc length so that we can draw dotted and dashed lines. This can be determined simply by calculating the angle difference between two points on the circle and multiplying by the radius. .PP Using CORDIC iterations, we could convert from rectangular to polar in the time of 5.5 multiplications; arc length still requires another multiplication, resulting in 6.5 multiplications per point visited. .PP This still requires considerable computation, so we search for a way to do the computations incrementally. The equations for radius and arc length are given with the folowing integral matrix equation: .EQ I (1) delim @@ int from C r ^ left [ pile { dr above dl } right ] = int from C r ^ left [ matrix { ccol { x above -y } ccol { y above x } } right ] ^ left [ pile { dx above dy } right ] .EN .LP Where @ r @ is the distance from the center of the circle, @ l @ is the arc length from some point on the circle, and @ C @ is an arbitrary curve of integration from @ ( x sub 0 , ^ y sub 0 ) @ to @ ( x sub 1 , ^ y sub 1 ) @, where @ r @ and @ l @ also change, from @ ( r sub 0 , ^ l sub 0 ) @ to @ ( r sub 1 , ^ l sub 1 ) @. The integrand is an exact differential, so the actual curve used for integration is not important. .PP We shall use this equation to derive incremental changes from differential changes. .SH Incremental Radius .PP Let us first look at the incremental radius: .EQ I (2) int from C r ^ dr = int from C x ^ dx ~ + ~ y ^ dy .EN .LP Integrating on both sides, we have: .EQ I (3) size -3 { 1 over 2 } ^ left "" r sup 2 right ] from { r sub 0 } to { r sub 1 } ~ = ~ size -3 { 1 over 2 } ^ left "" x sup 2 right ] from { x sub 0 } to { x sub 1 } ~ + ~ size -3 { 1 over 2 } ^ left "" y sup 2 right ] from { y sub 0 } to { y sub 1 } .EN .EQ I size -3 { 1 over 2 } left [ r sub 1 sup 2 ^ - ^ r sub 0 sup 2 right ] ~ = ~ size -3 { 1 over 2 } left [ x sub 1 sup 2 ^ - ^ x sub 0 sup 2 ~ + ~ y sub 1 sup 2 ^ - ^ y sub 0 sup 2 right ] .EN .EQ I size -3 { 1 over 2 } ^ ( r sub 1 ^ + ^ r sub 0 ) ( r sub 1 ^ - ^ r sub 0 ) ~ = ~ size -3 { 1 over 2 } ^ left [ ( x sub 1 ^ + ^ x sub 0 ) ( x sub 1 ^ - ^ x sub 0 ) ~ + ~ ( y sub 1 ^ + ^ y sub 0 ) ( y sub 1 ^ - ^ y sub 0 ) right ] .EN .EQ I size -3 { 1 over 2 } ^ ( 2 r sub 0 ^ + ^ DELTA r ) DELTA r ~ = ~ size -3 { 1 over 2 } ^ left [ ( 2 x sub 0 ^ + ^ DELTA x ) DELTA x ~ + ~ ( 2 y sub 0 ^ + ^ DELTA y ) DELTA y right ] .EN .EQ I DELTA r ^ ( r sub 0 ^ + ^ { DELTA r } over 2 ) ~ = ~ { DELTA x } ( x sub 0 ^ + ^ { DELTA x } over 2 ) ~ + ~ { DELTA y } ( y sub 0 ^ + ^ { DELTA y } over 2 ) .EN .LP Therefore, the resultant change in radius for an incremental change in @ x @ and @ y @ is: .EQ I (4) DELTA r ~ = ~ { DELTA x ( x sub 0 ^ + ^ { DELTA x } over 2 ) ~ + ~ DELTA y ( y sub 0 ^ + ^ { DELTA y } over 2 ) } over { r sub 0 ^ + ^ { DELTA r } over 2 } .EN .PP If the increments in x and y are @ +- 1 @ or @ 0 @, and if @ r sub c ^ >> ^ 1 @ (where @ r sub c @ is the radius of the circle), then its doesn't much matter what we divide by, as long as it is in the interval @ [ r sub 0 , ~ r sub 1 ] @. .PP However, for small circles, @ DELTA r @ is on the order of @ r sub c @, the radius of the circle. For these, we must increase our accuracy of the calculations. This can be done rather easily by iteration as follows: Make a first calculation for @ DELTA r @ using eq. (7). Then use the computed value for @ DELTA r @ in the same equation, generating a second @ DELTA r @. This can be continued until the successive iterates converge, or for a fixed number of iterations. Two good starting values for @ DELTA r @ are @ 0 @ and the last calculated value for @ DELTA r @. .SH Incremental Arc Length .PP We start out with the integral equation for arc length: .EQ I (5) int from C r ^ dl = int from C -y ^ dx ~ + ~ x ^ dy .EN .LP We choose to integrate along the straight line between @ ( x sub 0 , ^ y sub 0 ) @ and @ ( x sub 1 , ^ y sub 1 ) @. Since @ r @ and @ l @ are both change during the integration, but not in a simple way, we invoke the .I "mean value theorem" on the left-hand side. .EQ I (6) r sub m DELTA l ~ mark = ~ - int from { x sub 0 } to { x sub 1 } left [ y sub 0 ^ + ^ { DELTA y } over { DELTA x } ( x ^ - ^ x sub 0 ) right ] dx ~ + ~ int from { y sub 0 } to { y sub 1 } left [ x sub 0 ^ + ^ { DELTA x } over { DELTA y } ( y ^ - ^ y sub 0 ) right ] dy .EN .EQ I lineup = ~ - y sub 0 DELTA x ~ - ~ size -3 { 1 over 2 } { DELTA y } over { DELTA x } DELTA x sup 2 ~ + ~ x sub 0 DELTA y ~ + ~ size -3 { 1 over 2 } { DELTA x } over { DELTA y } DELTA y sup 2 .EN .EQ I lineup = ~ x sub 0 ^ DELTA y ~ - ~ y sub 0 ^ DELTA x .EN .LP This gives a value for the incremental arc length: .EQ I (7) DELTA l ~ = ~ { x sub 0 ^ DELTA y ^ - ^ y sub 0 ^ DELTA x } over r sub m .EN .LP Where @ r sub m @ lies somewhere between @ r sub 0 @ and @ r sub 1 @. A good value to use for @ r sub m @ is the value @ r sub 0 ^ + ^ { DELTA r } over 2 @ computed above in eq. (4). -- Ken Turkowski @ Apple Computer, Cupertino, CA UUCP: nsc!apple!turk, {amd,decwrl,hplabs,seismo}!turtlevax!ken ARPA: turk%apple@CSNET-RELAY.ARPA, turtlevax!ken@DECWRL.DEC.COM CSNET: turk@apple.CSNET