“A family of new algorithms for soft filling” by Fishkin and Barsky

Soft filling algorithms change the color of an anti-aliased region, maintaining the anti-aliasing of the region. The two published algorithms for soft filling work only if the foreground region is anti-aliased against a black background. This paper presents three new algorithms. The first fills against a region consisting of any two distinct colors, and is faster than the published algorithms on a pixel-by-pixel basis for an RGB frame buffer; the second fills against a region composed of three distinct colors; and the third fills against a region composed of four distinct colors. As the power of the algorithms increases, so do the number of assumptions they make, and the computational cost.

1. Kenneth P. Fishkin and Brian A. Barsky, Linear Fill Perturbation Analysis, University of California, Berkeley, California (1983). Berkeley Computer Graphics Laboratory internal document.
2. Kenneth P. Fishkin, Applying Color Science to Computer Graphics, Master’s Thesis, University of California, Berkeley, California (December, 1983).
3. Graphics Standards Planning Committee, “Status Report of the Graphics Standards Committee,” Computer Graphics, Vol. 13, No. 3, August, 1979.
4. Marc S. Levoy, Computer-Assisted Cartoon Animation, Master’s Thesis, Cornell University, Ithaca, N.Y. (August, 1978).
5. Mare S. Levoy, Area Flooding Algorithms, Report, Hanna-Barbera Productions (June, 1981).
6. Marc S. Levoy, private communication. December, 1983.
7. Henry Lieberman, “How To Color in a Coloring Book,” pp. 111-116 in SIGGRAPH ’78 Conference Proceedings,, ACM,(1978).
8. F.P. Perparata and S. J. Hong, “Convex Hulls of Finite Sets of Points in Two and Three Dimensions,” Communications of the ACM, Vol. 20, No. 2, February, 1977, pp. 87 – 93.
9. William K. Pratt, Digital Image Processing, John Wiley & Sons, New York (1978).
10. Michael I. Shamos, Computational Geometry, Ph.D. Thesis, Yale University, New Haven, Connecticut (May, 1978). Book of same title to be published by Springer-Verlag.
11. Alvy Ray Smith, “Tint Fill,” pp. 276-283 in SIGGRAPH ’79 Conference Proceedings, ACM, (August, 1979). Also Technical Memo No. 6, New York Institute of Technology.
12. Alvy Ray Smith, Fill Tutorial Notes, Report No. 40, LucasFilm (1981).
13. Alvy Ray Smith, Color Tutorial Notes, Report No. 37, LucasFilm (1981).
14. Alvy Ray Smith, private communication. September, 1982.