An efficient new algorithm for 2-D line clipping: Its development and analysis

ABSTRACT

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.

REFERENCES

• 1: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 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: B. A. Barsky, A New Concept and Method for Line Clipping, ACM Transactions on Graphics (TOG), v.3 n.1, p.1-22, Jan. 1984 [doi>10.1145/357332.357333]
• 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: Jacques J. Arsac, Syntactic source to source transforms and program manipulation, Communications of the ACM, v.22 n.1, p.43-54, Jan. 1979 [doi>10.1145/359046.359057]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Hierarchy and geometric transformations; Geometric algorithms, languages, and systems

General Terms:
Algorithms, Design, Measurement, Performance, Theory