Method and apparatus for generating anti-aliased vectors, arcs and circles on a video display

Abstract

A method and apparatus for anti-aliasing vectors, arcs and circles comprising a plurality of pixels on a video display. The distance, d, of each pixel from the centerline of a curve is computed using a plurality of linearly dependent equations. The intensity of each pixel is set as a function of the magnitude of the distance, d, of the pixel from the centerline of the curve. In some cases, the distance, d, is compared with ranges of distances and the intensity of the pixel set according to the range within which the pixel is located. In other cases, the intensity of the pixel is simply inversely proportional to its distance, d, from the centerline.

What is claimed is: 
     
       1. In a graphics processor having a plurality of pairs of first and second comparators, each of said comparators having a first and a second input and an output, a plurality of first and second AND gate means, each of said first and second AND gate means having an output, a plurality of memory planes and a video display, said video display having a plurality of pixels, a method for anti-aliasing a curve having a centerline on said video display comprising the steps of: generating for each one of a plurality of predetermined positions on said centerline a plurality of signals which correspond to the distance each of a predetermined number of said pixels is from said position;   generating a predetermined number of pairs of first and second numbers, said first number in each of said pairs having a magnitude corresponding to a predetermined minimum distance from said centerline and said second number in each of said pairs having a magnitude corresponding to a predetermined maximum distance from said centerline, each of said pairs of numbers defining a predetermined range of distances from said centerline;   applying a number corresponding to said distance each of said predetermined number of pixels is from said position on said centerline to said first input of each of said first and second comparators;   applying one of said first numbers corresponding to said minimum distance in each of said ranges of distances from said centerline to said second input of one of said first comparators, respectively, each of said first comparators providing a signal on its output when the magnitude of said number applied to its first input is equal to or greater than the magnitude of the number applied to its second input;   applying one of said second numbers corresponding to said maximum distance in each of said ranges of distances from said centerline to said second input of one of said second comparators, respectively, each of said second comparators providing a signal on its output when the magnitude of said number applied to its first input is equal to or less than the magnitude of the number applied to its second input;   coupling said outputs of said first and second comparators in each pair of comparators to a different one of said first AND gate means, each of said first AND gate means providing a signal on its output when there is a signal generated on the output of both said first and second comparators coupled thereto;   coupling a write enable signal to a first input of each of said second AND gate means;   coupling said output of each of said first AND gate means to a second input of a different one of said second AND gate means;   coupling said output of each of said second AND gate means to a different one of said plurality of memory planes, respectively; and   addressing said memory planes for storing a bit in each memory plane in response to an output from the second AND gate means coupled thereto, said bit and the memory plane in which it is stored determining the intensity of the pixel associated therewith.   
     
     
       2. A method according to claim 1 wherein said distance of each of said pixels from said centerline comprises a distance, d, said minimum distance comprises a distance d min  said maximum distance comprises a distance d max  and said steps of applying said numbers to said first and second inputs of said comparators comprises the step of comparing said d with said d min  and said d max  according to the equation:   d.sub.min ≦d≦d.sub.max.     
     
     
       3. A method according to claim 2 wherein: ##EQU22## d min  =N min  d max  =N max   dx=max[abs(X 2  -X 1 ),abs(Y 2  -Y 1 )]   D=internal error factor in Bresenham algorithm   X 1 ,X 2 ,Y 1 ,Y 2  =define the end points of a curve   K=constant   N min ,N max  =an integer.   
     
     
       4. A method according to claim 2 wherein: ##EQU23## dx=max[abs(X 2  -X 1 ),abs(Y 2  -Y 1 )] D=internal error factor in Bresenham algorithm X 1 ,X 2 ,Y 1 ,Y 2  =define the end points of a curve   K,M=constant   N min ,N max  =an integer.   
     
     
       5. A method according to claim 2 wherein: ##EQU24## d min  =N min  d max  =N max   R=radius of an arc   D=internal error factor in Bresenham algorithm   abs(D) ε[0,2R]   K=constant   N min ,N max  =an integer.   
     
     
       6. A method according to claim 2 wherein: ##EQU25## R=radius of an arc D=internal error factor in Bresenham algorithm abs(D) ε[0,2R]   K=constant   N min ,N max  =an integer.   
     
     
       7. A method of anti-aliasing an arc having a centerline on a video display, said video display having a plurality of pixels comprising the steps of: generating for each one of a plurality of predetermined positions on said centerline a plurality of signals which correspond to the distance each of a predetermined number of said pixels is from said position inside and outside of said arc; and   illuminating on said display in response to said signals each of said predetermined number of said pixels outside said arc with an intensity I s  and each of said predetermined number of said pixels inside said arc with an intensity I t  according to the equations: ##EQU26##  where R=radius of an arc D=internal error factor in Bresenham algorithm   abs(D) ( [0,2R]   K=constant.     
     
     
       8. An apparatus for anti-aliasing an arc having a centerline on a video display, said video display having a plurality of pixels comprising, means for generating for each one of a plurality of predetermined positions on said centerline a plurality of signals which correspond to the distance each of a predetermined number of said pixels is from said position inside and outside of said arc; and   means for illuminating on said display in response to said signals each of said predetermined number of pixels outside said arc with an intensity I s  and each of said predetermined number of pixels inside said arc with an intensity I t  according to the equations: ##EQU27##  where R=radius of an arc D=internal error factor in Bresenham algorithm   abs(D) ( [0,2R]   K=constant.     
     
     
       9. An apparatus for anti-aliasing a curve having a centerline on a video display, said video display having a plurality of pixels comprising: a plurality of pairs of first and second comparators, each of said comparators having a first and a second input and an output;   means for generating for each one of a plurality of predetermined positions on said centerline a plurality of signals which correspond to the distance each of a predetermined number of said pixels is from said position;   means for generating a predetermined number of pairs of first and second numbers, said first number in each of said pairs having a magnitude corresponding to a predetermined minimum distance from said centerline and said second number in each of said pairs having a magnitude corresponding to a predetermined maximum distance from said centerline, each of said pairs of numbers defining a predetermined range of distances from said centerline;   means for applying a number corresponding to said distance each of said predetermined number of pixels is from said position on said centerline to said first input of each of said first and second comparators;   means for applying one of said first numbers corresponding to said minimum distance in each of said ranges of distances from said centerline to said second input of one of said first comparators, respectively, each of said first comparators providing a signal on its output when the magnitude of said number applied to its first input is equal to or greater than the magnitude of the number applied to its second input;   means for applying one of said second numbers corresponding to said maximum distance in each of said ranges of distances from said centerline to said second input of one of said second comparators, respectively, each of said second comparators providing a signal on its output when the magnitude of said number applied to its first input is equal to or less than the magnitude of the number applied to its second input;   a plurality of first AND gates, each of said first AND gates having an output;   means for coupling said outputs of said first and second comparators in each pair of comparators to a different one of said first AND gates, each of said first AND gates providing a signal on its output when there is a signal generated on the output of both said first and second comparators coupled thereto;   a plurality of second AND gates, each of said second AND gates having an output;   means for coupling a write enable signal to a first input of each of said second AND gates;   means for coupling said output of each of said first AND gates to a second input of a different one of said second AND gates;   a plurality of memory planes;   means for coupling said output of each of said second AND gates to a different one of said plurality of memory planes, respectively; and   means for addressing said memory planes for storing a bit in each memory plane in response to an output from the second AND gate coupled thereto, said bit and the memory plane in which it is stored determining the intensity of the pixel associated therewith.   
     
     
       10. An apparatus according to claim 9 wherein said distance of each of said pixels from said centerline comprises a distance, d, said minimum distance comprises a distance d min  and said maximum distance comprises a distance d max  and said first and second comparators comprise means for comparing said d with said d min  and said d max  according to the equation:   d.sub.min ≦d≦d.sub.max.     
     
     
       11. An apparatus according to claim 10 wherein: ##EQU28## d min  =N min  d max  =N max   dx=max[abs(X 2  -X l ),abs(Y 2  -Y 1 )]   D=internal error factor in Bresenham algorithm   X l ,X 2 ,Y 1 ,Y 2  =define the end points of a curve   K=constant   N min ,N max  =an integer.   
     
     
       12. An apparatus according to claim 10 wherein: ##EQU29## dx=max[abs(X 2  -X l ),abs(Y 2  -Y 1 )] D=internal error factor in Bresenham algorithm X l ,X 2 ,Y 1 ,Y 2  =define the end points of a curve   K,M=constant   N min ,N max  =an integer.   
     
     
       13. An apparatus according to claim 10 wherein: ##EQU30## d min  =N min  d max  =N max   R=radius of an arc   D=internal error factor in Bresenham algorithm   abs(D) ε[0,2R]   K=constant   N min ,N max  =an integer.   
     
     
       14. An apparatus according to claim 10 wherein: ##EQU31## R=radius of an arc D=internal error factor in Bresenham algorithm abs(D) ε[0,2R]   K=constant   N min ,N max  =an integer.