The Cohen-Sutherland algorithm ( Cohen – Sutherland ) is an algorithm for cutting off segments , that is, an algorithm that allows you to determine the part of a segment that intersects a rectangle . It was developed by Dan Cohen and Ivan Sutherland at Harvard from 1966 to 1968 , and published at the AFIPS conference in 1968 . [1] [2]
Algorithm Description
The algorithm divides the plane into 9 parts by straight lines that form the sides of a rectangle. Each of the 9 parts is assigned a four-bit code. Bits (from the youngest to the oldest) mean “left”, “right”, “lower”, “higher”. In other words, for those three parts of the plane that are to the left of the rectangle, the low-order bit is 1, and so on.
The algorithm determines the code of the ends of the segment. If both codes are zero, then the segment is completely in the rectangle. If the bit AND code is not zero, then the segment does not intersect the rectangle (as this means that both ends of the segment are on one side of the rectangle). In other cases, the algorithm selects the end of the segment (or one of the ends) that has a non-zero code (that is, located outside the rectangle), finds the point of intersection of the segment with one of the lines forming the sides of the rectangle, and uses this intersection point as the new end cut off. The shortened segment is again passed through the algorithm.
The implementation of the algorithm for the three-dimensional model is identical to the two-dimensional implementation, except for the fact that instead of a four-digit code, a six-bit one is used (an additional two bits of depth).
See also
- Wyler-Atherton Algorithm
- Algorithm of Cyrus - Beck
Notes
- ↑ A Critical History of Computer Graphics and Animation. Section 4: Basic and applied research moves the industry . The date of circulation is February 26, 2009. Archived on March 27, 2012.
- ↑ Robert F. Sproull, Ivan E. Sutherland. A clipping divider // AFIPS Joint Computer Conferences: Proceedings of the December 9-11, 1968, fall joint computer conference. - New York: ACM, 1968. - T. I. - p . 765-775 .