“An efficient new algorithm for 2-D line clipping: Its development and analysis” by Nicholl, Lee and Nicholl

This paper describes a new alorithm for clipping a line in two dimensions against a rectangular window. This algorithm avoids computation of intersection points which are not endpoints of the output line segment. The performance of this algorithm is shown to be consistently better than existing algorithms, including the Cohen-Sutherland and Liang-Barsky algorithms. This performance comparison is machine-independent, based on an analysis of the number of arithmetic operations and comparisons required by the different algorithms. We first present the algorithm using procedures which perform geometric transformations to exploit symmetry properties and then show how program transformation techniques may be used to eliminate the extra statements involved in performing geometric transformations.

1. Newman, W. M. and R. F. Sproull. Principles of Interactive Computer Graphics, 2nd ed., McGraw-Hill, New York, 1979.
2. Sproull, R. F. and I. E. Sutherland. A Clipping Divider, FICC 1968, Thompson Books, Washington, D.C., pp. 765-775.
3. Cyrus, M. and I. Beck. Generalised Two- and Three- Dimensional Clipping, Computers and Graphics, Vol. 3, No. 1, 1978, pp. 23-28.
4. Liang, Y.-D. and B. A. Barsky. A New Concept and Method for Line Clipping, ACM Transactions on Graphies, Vol. 3, No. 1, 1984, pp. 1-22.
5. Sobkow, M. S., Pospisil, P. and Y.-II. Yang. A Fast Two- Dimensional Line Clipping Algorithm, University of Saskatchewan Technical Report, 86-2.
6. Hoare, C. A. R. et al. Laws of Programming: a tutorial paper, Oxford University Programming Research Group PRG-45, 1985.
7. Arsac, J. I. Syntactic Source to Source Transforms and Program Manipulation, Communications of the ACM, Vol. 22, No. 1, 1979, pp. 43-54.