Cohen–Sutherland algorithm


The Cohen–Sutherland algorithm is a computer-graphics 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 algorithm was developed in 1967 during flight-simulator work by Danny Cohen and Ivan Sutherland.

The algorithm

The algorithm includes, excludes or partially includes the line based on whether:
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.
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 = 0; // 0000
const int LEFT = 1; // 0001
const int RIGHT = 2; // 0010
const int BOTTOM = 4; // 0100
const int TOP = 8; // 1000
// Compute the bit code for a point using the clip rectangle
// bounded diagonally by, and
// ASSUME THAT xmax, xmin, ymax and ymin are global constants.
OutCode ComputeOutCode
// Cohen–Sutherland clipping algorithm clips a line from
// P0 = to P1 = against a rectangle with
// diagonal from to.
void CohenSutherlandLineClipAndDraw