Reentrant polygon clipping

ABSTRACT

A new family of clipping algorithms is described. These algorithms are able to clip polygons against irregular convex plane-faced volumes in three dimensions, removing the parts of the polygon which lie outside the volume. In two dimensions the algorithms permit clipping against irregular convex windows. Polygons to be clipped are represented as an ordered sequence of vertices without repetition of first and last, in marked contrast to representation as a collection of edges as was heretofore the common procedure. Output polygons have an identical format, with new vertices introduced in sequence to describe any newly-cut edge or edges. The algorithms easily handle the particularly difficult problem of detecting that a new vertex may be required at a corner of the clipping window. The algorithms described achieve considerable simplicity by clipping separately against each clipping plane or window boundary. Code capable of clipping the polygon against a single boundary is reentered to clip against subsequent boundaries. Each such reentrant stage of clipping need store only two vertex values and may begin its processing as soon as the first output vertex from the preceeding stage is ready. Because the same code is reentered for clipping against subsequent boundaries, clipping against very complex window shapes is practical. For perspective applications in three dimensions, a six-plane truncated pyramid is chosen as the clipping volume. The two additional planes parallel to the projection screen serve to limit the range of depth preserved through the projection. A perspective projection method which provides for arbitrary view angles and depth of field in spite of simple fixed clipping planes is described. This method is ideal for subsequent hidden-surface computations.

REFERENCES

• 1: Archuleta, Michael. Computer Science Technical Memos 7002, 7102, 7105, and 7203 pertaining to Watkins' Hiddenline processing, U. of Utah, Salt Lake City, Utah, Nov. 1970, Oct. 1971, May 1971, and Mar. 1972 respectively.
• 2: W. Jack Bouknight, A procedure for generation of three-dimensional half-toned computer graphics presentations, Communications of the ACM, v.13 n.9, p.527-536, Sept. 1970 [doi>10.1145/362736.362739]
• 3: R. Galimberti, An algorithm for hidden line elimination, Communications of the ACM, v.12 n.4, p.206-211, April 1969 [doi>10.1145/362912.362921]
• 4: Loutrel, P.P. A solution to the hidden-line problem for computer-drawn polyhedra. NYU Eng. and Sci. Dept. of EE Rept. 400-167, Sep. 1967. (Also IEEE Tran. on Computers EC-1913}, Mar. 1970.)
• 5: Mathematical Applications Group Inc. (MAGI). 3-D simulated graphics. Datamation (Feb. 1968).
• 6: Moore, E. Shortest Path Through a Maze. Ann. of Computation Laboratory of Harvard U., Vol. 30, Harvard U. Press, Cambridge, Mass. pp. 285-292, 1959.
• 7: Newell, M.E., Newell, R.G., and Sancha, T.L. A new approach to the shaded picture problem. Proc. ACM Nat. Conf., Boston, Aug. 1972.
• 8: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 9: Newman, W.M. An informal graphics system based on the LOGO language. Proc. AFIPS 1973 FJCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 651-655.
• 10: Roberts, L.G. Homogeneous matrix representation and manipulation of N-dimensional constructs. MIT Lincoln Laboratory MS 1405, May 1965.
• 11: Sproull, R.F., and Sutherland I.E. A clipping divider. Proc. 1968 AFIPS FJCC, Vol. 33, AFIPS Press, Montvale, N.J., pp. 765-775.
• 12: Sutherland I.E. A head-mounted three-dimensional display. Proc. 1968 AFIPS FJCC, Vol. 33, AFIPS Press, Montvale, N.J., pp. 757-764.
• 13: Warnock, J.E. A hidden-surface algorithm for computergenerated halftone pictures. Computer Science Dept., U. of Utah, TR 4-15, June 1969.
• 14: Ruth A. Weiss, BE VISION, A Package of IBM 7090 FORTRAN Programs to Draw Orthographic Views of Combinations of Plane and Quadric Surfaces, Journal of the ACM (JACM), v.13 n.2, p.194-204, April 1966 [doi>10.1145/321328.321330]
• 15: Zajac, E.E., and Behler, B.L. A generalized window-shield routine. UAIDE Proc. 8th Ann. Meeting, Nov. 1969, pp. 351-388.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Decision problems

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Hidden line/surface removal

General Terms:
Algorithms, Design, Theory

Keywords:
clipping, computer graphics, hidden-suface