Cohen–Sutherland algorithm explained

In computer graphics, the Cohen–Sutherland algorithm is an algorithm used for line clipping. The algorithm divides a two-dimensional space into 9 regions and then efficiently determines the lines and portions of lines that are visible in the central region of interest (the viewport).

The algorithm was developed in 1967 during flight simulator work by Danny Cohen and Ivan Sutherland.^[1]

The algorithm

The algorithm includes, excludes or partially includes the line based on whether:

• Both endpoints are in the viewport region (bitwise OR of endpoints = 0000): trivial accept.
• Both endpoints share at least one non-visible region, which implies that the line does not cross the visible region. (bitwise AND of endpoints ≠ 0000): trivial reject.
• Both endpoints are in different regions: in case of this nontrivial situation the algorithm finds one of the two points that is outside the viewport region (there will be at least one point outside). The intersection of the outpoint and extended viewport border is then calculated (i.e. with the parametric equation for the line), and this new point replaces the outpoint. The algorithm repeats until a trivial accept or reject occurs.

The numbers in the figure below are called outcodes. An outcode is computed for each of the two points in the line. The outcode will have 4 bits for two-dimensional clipping, or 6 bits in the three-dimensional case. The first bit is set to 1 if the point is above the viewport. The bits in the 2D outcode represent: top, bottom, right, left. For example, the outcode 1010 represents a point that is top-right of the viewport.

	left	central	right
top	1001	1000	1010
central	0001	0000	0010
bottom	0101	0100	0110

Note that the outcodes for endpoints must be recalculated on each iteration after the clipping occurs.

The Cohen–Sutherland algorithm can be used only on a rectangular clip window.

Example C/C++ implementation

typedef int OutCode;

const int INSIDE = 0b0000;const int LEFT = 0b0001;const int RIGHT = 0b0010;const int BOTTOM = 0b0100;const int TOP = 0b1000;

// Compute the bit code for a point (x, y) using the clip rectangle// bounded diagonally by (xmin, ymin), and (xmax, ymax)

// ASSUME THAT xmax, xmin, ymax and ymin are global constants.

OutCode ComputeOutCode(double x, double y)

// Cohen–Sutherland clipping algorithm clips a line from// P0 = (x0, y0) to P1 = (x1, y1) against a rectangle with // diagonal from (xmin, ymin) to (xmax, ymax).bool CohenSutherlandLineClip(double& x0, double& y0, double& x1, double& y1)

See also

Algorithms used for the same purpose:

• Liang–Barsky algorithm
• Cyrus–Beck algorithm
• Nicholl–Lee–Nicholl algorithm
• Fast clipping

References

• James D. Foley. Computer graphics: principles and practice. Addison-Wesley Professional, 1996. p. 113.

External links

• JavaScript polyline clipping library using Cohen-Sutherland algorithm
• Animated JavaScript implementation
• Delphi implementation
• Stata implementation

Notes and References

1. Principles of Interactive Computer Graphics, p. 124, 252, by Bob Sproull and William M. Newman, 1973, McGraw–Hill Education, International edition, .