Cohen–Sutherland algorithm
In computer graphic, the Cohen–Sutherland algorithm (named after Danny Cohen and Ivan Sutherland) is a line clipping algorithm. The algorithm divides a 2D space into 9 regions, of which only the middle part (viewport) is visible.
In 1967, flight simulation work by Danny Cohen led to the development of the Cohen–Sutherland computer graphics two and three dimensional line clipping algorithms, created with Ivan Sutherland.[1]
Bold text==The algorithm==
The algorithm includes, excludes or partially includes the line based on where:
- Both endpoints are in the viewport region (bitwise OR of endpoints == 0): trivial accept.
- Both endpoints are on the same non-visible region (bitwise AND of endpoints != 0): trivial reject.
- Both endpoints are in different regions: In case of this non trivial 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 first bit is set to 1 if the point is above the viewport. The bits in the 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.
| 1001 | 1000 | 1010 |
| 0001 | 0000 | 0010 |
| 0101 | 0100 | 0110 |
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 (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)
{
OutCode code;
code = INSIDE; // initialised as being inside of clip window
if (x < xmin) // to the left of clip window
code |= LEFT;
else if (x > xmax) // to the right of clip window
code |= RIGHT;
if (y < ymin) // below the clip window
code |= BOTTOM;
else if (y > ymax) // above the clip window
code |= TOP;
return code;
}
// 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).
void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1)
{
// compute outcodes for P0, P1, and whatever point lies outside the clip rectangle
OutCode outcode0 = ComputeOutCode(x0, y0);
OutCode outcode1 = ComputeOutCode(x1, y1);
bool accept = false;
while (true) {
if (!(outcode0 | outcode1)) { // Bitwise OR is 0. Trivially accept and get out of loop
accept = true;
break;
} else if (outcode0 & outcode1) { // Bitwise AND is not 0. Trivially reject and get out of loop
break;
} else {
// failed both tests, so calculate the line segment to clip
// from an outside point to an intersection with clip edge
double x, y;
// At least one endpoint is outside the clip rectangle; pick it.
OutCode outcodeOut = outcode0? outcode0 : outcode1;
// Now find the intersection point;
// use formulas y = y0 + slope * (x - x0), x = x0 + (1 / slope) * (y - y0)
if (outcodeOut & TOP) { // point is above the clip rectangle
x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
y = ymax;
} else if (outcodeOut & BOTTOM) { // point is below the clip rectangle
x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
y = ymin;
} else if (outcodeOut & RIGHT) { // point is to the right of clip rectangle
y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
x = xmax;
} else if (outcodeOut & LEFT) { // point is to the left of clip rectangle
y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
x = xmin;
}
//NOTE:*****************************************************************************************
/* if you follow this algorithm exactly(at least for c#), then you will fall into an infinite loop
in case a line crosses more than two segments. to avoid that problem, leave out the last else
if(outcodeOut & LEFT) and just make it else*/
//**********************************************************************************************
// Now we move outside point to intersection point to clip
// and get ready for next pass.
if (outcodeOut == outcode0) {
x0 = x;
y0 = y;
outcode0 = ComputeOutCode(x0, y0);
} else {
x1 = x;
y1 = y;
outcode1 = ComputeOutCode(x1, y1);
}
}
}
if (accept) {
// Following functions are left for implementation by user based on his platform(OpenGL/graphics.h etc.)
DrawRectangle(xmin, ymin, xmax, ymax);
LineSegment(x0, y0, x1, y1);
}
}
Example C# implementation with Tao framework
//Created by Kyazze Michael: This program demonstrates the Cohen Sutherland algorithm
//by generating 100 random lines and clipping them
using System;
using System.Drawing;
using System.Windows.Forms;
using Tao.OpenGl;
namespace CohenSutherlandAlgorithm
{
public partial class Form1 : Form
{
//Create an enumerator to store the region values
enum side : uint
{
INSIDE = 0x0,
TOP = 0x1,
BOTTOM = 0x2,
RIGHT = 0x4,
LEFT = 0x8
};
//Create an enumerator to store true/false values
enum bval : int
{
FALSE,
TRUE
};
const int n = 6; //number of lines generated
int[,] ln;
public Form1()
{
InitializeComponent();
}
protected override void CreateHandle()
{
base.CreateHandle();
simpleOpenGlControl1.InitializeContexts();
}
protected override void DestroyHandle()
{
simpleOpenGlControl1.DestroyContexts();
base.DestroyHandle();
}
//The function below determines the location of the point whether above, below, inside,
//to the left or right of the clip window
side outcode_func(double x, double y, double xmin, double ymin, double xmax, double ymax)
{
side outcode = side.INSIDE;
if (y > ymax)
outcode |= side.TOP;
else if (y < ymin)
outcode |= side.BOTTOM;
if (x > xmax)
outcode |= side.RIGHT;
else if (x < xmin)
outcode |= side.LEFT;
return outcode;
}
//The function below does the clipping of the lines to differentiate between those in and those
//out of the clip window
void cohensutherland_func(double x1, double y1, double x2, double y2, double xmin, double ymax, double xmax, double ymin)
{
bval accept;
bval done;
side outcode1, outcode2;
accept = bval.FALSE;
done = bval.FALSE;
outcode1 = outcode_func(x1, y1, xmin, ymin, xmax, ymax);
outcode2 = outcode_func(x2, y2, xmin, ymin, xmax, ymax);
do
{
if (!(Convert.ToBoolean(outcode1 | outcode2)))
{
//no clipping meaning the line is with in the clip window
accept = bval.TRUE;
done = bval.TRUE;
}
else if (Convert.ToBoolean(outcode1 & outcode2))
{
//the line doesnt require clipping
done = bval.TRUE;
}
else
{
double x = 0, y = 0;
side outcode_ex = (outcode1 > 0) ? outcode1 : outcode2;
uint oval = (uint)outcode_ex;
//determine where the line is and clip off the part that is outside the clip window
if (Convert.ToBoolean(outcode_ex & side.TOP))
{
x = x1 + (x2 - x1) * (ymax - y1) / (y2 - y1);
y = ymax;
}
else if (Convert.ToBoolean(outcode_ex & side.BOTTOM))
{
x = x1 + (x2 - x1) * (ymin - y1) / (y2 - y1);
y = ymin;
}
else if (Convert.ToBoolean(outcode_ex & side.RIGHT))
{
y = y1 + (y2 - y1) * (xmax - x1) / (x2 - x1);
x = xmax;
}
else
{
y = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1);
x = xmin;
}
//get the new co-ordinates of the line
if (outcode_ex == outcode1)
{
x1 = x;
y1 = y;
outcode1 = outcode_func(x1, y1, xmin, ymin, xmax, ymax);
}
else
{
x2 = x;
y2 = y;
outcode2 = outcode_func(x2, y2, xmin, ymin, xmax, ymax);
}
}
} while (done == bval.FALSE);
if (accept == bval.TRUE)
{
//draw the line inside the clip window in red
Gl.glBegin(Gl.GL_LINES);
Gl.glColor3f(1.0f, 0.0f, 0.0f);
Gl.glVertex2d(x1, y1);
Gl.glVertex2d(x2, y2);
Gl.glEnd();
}
}
void printfunc()
{
int i;
ln = new int[n, 4]; //two dimensional array that stores line-endpoints
Random coordinates = new Random();
// //loop that generates the random co-ordinates
// for (int p = 0; p < n; p++)
// {
// for (int k = 0; k < 4; k++)
// {
// ln[p, k] = coordinates.Next((simpleOpenGlControl1.Height > simpleOpenGlControl1.Width) ?
//(simpleOpenGlControl1.Height) : (simpleOpenGlControl1.Width));
// }
// }
ln = new int[n, 4] { { 10, 390, 390, 10 }, { 30, 45, 67, 76 }, { 120, 100, 300, 120 }, { 120, 120, 150, 190 }, { 140, 100, 170, 100 }, { 142, 124, 136, 350 } };
Gl.glMatrixMode(Gl.GL_PROJECTION);
Gl.glLoadIdentity();
Glu.gluOrtho2D(0.0, 400.0, 0.0, 400.0);
int[] clip = new int[4] { 100, 300, 300, 100 }; //array that stores the co-ordinates of lef-top and
//right bottom corners of the clip window
//Plot the clipping window using a blue line loop to allow the window to be transparent
Gl.glBegin(Gl.GL_LINE_LOOP);
Gl.glColor3f(0.0f, 0.0f, 1.0f);
Gl.glVertex2i(clip[0], clip[1]);
Gl.glVertex2i(clip[2], clip[1]);
Gl.glVertex2i(clip[2], clip[3]);
Gl.glVertex2i(clip[0], clip[3]);
Gl.glEnd();
for (i = 0; i < n; i++)
{
//call the clipping function on all the lines
cohensutherland_func(ln[i, 0], ln[i, 1], ln[i, 2], ln[i, 3], clip[0], clip[1], clip[2], clip[3]);
}
}
private void simpleOpenGlControl1_Paint(object sender, PaintEventArgs e)
{
Gl.glClearColor(1.0f, 1.0f, 1.0f, 0.0f);
Gl.glColor3f(0.0f, 0.0f, 0.0f);
Gl.glClear(Gl.GL_COLOR_BUFFER_BIT);
Gl.glPointSize(2.0f);
printfunc();
Gl.glFlush();
}
}
}
Notes
- ^ Principles of Interactive Computer Graphics p.124 and p.252, by Bob Sproull and William M. Newman, 1973, McGraw–Hill Education, International edition, ISBN 0070855358
See also
Algorithms used for the same purpose:
References
- James D. Foley. Computer graphics: principles and practice. Addison-Wesley Professional, 1996. p. 113.