Ivan E. Sutherland
Gary W. Hodgman
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.
- 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.Google Scholar
- 2 Bouknight, W.J. A procedure for generation of threedimensional half-toned computer graphics representations. Comm. ACM 13, 9 (Sept. 1970), 527-536. Google ScholarDigital Library
- 3 Galimberti, R. and Montanari U. An algorithm for hiddenline elimination. Comm. ACM 12,4 (Apr. 1969), 206-211. Google ScholarDigital Library
- 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.)Google Scholar
- 5 Mathematical Applications Group Inc. (MAGI). 3-D simulated graphics. Datamation (Feb. 1968).Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 8 Newman, W.M.; and Sprouli, R.F. Prhrciples ofblteractive Computer Graphics. }McGraw-Hill, New York, 1973. (See especially Chap. 13). Google ScholarDigital Library
- 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.Google Scholar
- 10 Roberts, L.G. Homogeneous matrix representation and manipulation of N-dimensional constructs. MIT Lincoln Laboratory MS 1405, May 1965.Google Scholar
- 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.Google Scholar
- 12 Sutherland I.E. A head-mounted three-dimensional display. Proc. 1968 AFIPS FJCC, Vol. 33, AFIPS Press, Montvale, N.J., pp. 757-764.Google Scholar
- 13 Warnock, J.E. A hidden-surface algorithm for computergenerated halftone pictures. Computer Science Dept., U. of Utah, TR 4-15, June 1969.Google Scholar
- 14 Weiss, R.A. BE VISION, A package of IBM 7090 FORTRAN programs to draw orthographic views of combinations of planes and quadric surfaces. J.ACM 13, 2 (Apr. 1966), 194-204. Google ScholarDigital Library
- 15 Zajac, E.E., and Behler, B.L. A generalized window-shield routine. UAIDE Proc. 8th Ann. Meeting, Nov. 1969, pp. 351-388.Google Scholar
Index Terms
- Reentrant polygon clipping
Recommendations
A new, fast method for 2D polygon clipping: analysis and software implementation
This paper presents a new 2D polygon clipping method, based on an extension to the Sutherland-Cohen 2D line clipping method. After discussing three basic polygon clipping algorithms, a different approach is proposed, explaining the principles of a new ...
Efficient clipping of arbitrary polygons
Clipping 2D polygons is one of the basic routines in computer graphics. In rendering complex 3D images it has to be done several thousand times. Efficient algorithms are therefore very important. We present such an efficient algorithm for clipping ...
Comments