Method for point sampling in computer graphics systems

Abstract

A point sampling method for improving the images produced by a computer graphics system which uses quality measures together with a hill-climbing technique to generate an optimal rook placement of sample points. Two quality measures are used, the root-mean-square (rms) transition error and the maximal circle size. To derive the optimal rook placement, points are placed initially in any rook placement, such as along the diagonal of the pixel. New rook placements are generated by interchanging the x-coordinates of any pair of points. The optimal placement is determined by in a sequence of steps. At each step, all possible pair interchanges are tested by computing the quality measure for each of the possible interchanges. After all are evaluated, the sequence is concluded by making the interchange that provided the most improvement in the quality measure. The point placement after each interchange is used as the basis for the next step in the process. Each step follows the same procedure until no interchange improves the quality measure, or until the quality measure fails to be improved by at least a predetermined small increment.

Dependencies are inferred from the claim text.