“A hidden-surface algorithm with anti-aliasing” by Catmull

  • ©Edwin (Ed) Catmull




    A hidden-surface algorithm with anti-aliasing



    In recent years we have gained understanding about aliasing in computer generated pictures and about methods for reducing the symptoms of aliasing. The chief symptoms are staircasing along edges and objects that pop on and off in time. The method for reducing these symptoms is to filter the image before sampling at the display resolution. One filter that is easy to understand and that works quite effectively is equivalent to integrating the visible intensities over the area that the pixel covers. There have been several implementations of this method – mostly unpublished – however most algorithms break down when the data for the pixel is complicated. Unfortunately, as the quality of displays and the complexity of pictures increase, the small errors that can occur in a single pixel become quite noticeable. A correct solution for this filter requires a hidden-surface algorithm at each pixel! If the data at the pixel is presented as a depth-ordered list of polygons then the average visible intensity can be found using a polygon clipper in a way similar to that employed by two known hidden-surface algorithms. All of the polygons in a pixel are clipped against some front unclipped edge into two lists of polygons. The algorithm is recursively entered with each new list and halts when the front polygon is clipped on all sides, thereby obscuring the polygons behind. The area weighted colors are then returned as the value to be added to the other pieces in the pixel.


    1. Catmull, Edwin, A subdivision algorithm for computer display of curved surfaces, Technical report UTEC-CSs-74-133 University of Utah, 1974
    2. Crow, Frank, The aliasing problem in Computer-generated shaded images, CACM November 1977
    3. Myers, Allan J., An efficient visible surface program, Ohio State University, Computer Graphics Research Group, report to NSF, July 1975
    4. Shoup, R.G., Some quantization effects in digitally-generated pictures, Society for Information Display, 1973 proceedings.
    5. Sutherland, I.E., Polygon sorting by subdivision: A solution to the hidden-surface problem, Unpublished manuscript, October 1973, Also public lecture at University of Utah 1973.
    6. Sutherland, I.E., and Hodgman, G.W., Reentrant polygon clipping, CACM January 1974.
    7. Sutherland, I.E., Sproull, R.F., and Schumacker, R.A., A characterization of ten hidden-surface algorithms, ACM Computing Surveys, March 1974.
    8. Hamlin, Griffith Jr., and Gear, C.W., Rasterscan hidden surface algorithm techniques, Siggraph 1977 proceedings.
    9. Weiler, K. and Atherton, P., Hidden surface removal using polygon area sorting, Siggraph 1977 proceedings.

ACM Digital Library Publication: