Cohen–Sutherland algorithm

Cohen–Sutherland algorithm

In computer graphics, the Cohen–Sutherland algorithm (named after Michael F. 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].

Contents

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;
                        }
                        // 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);
        }
}

Notes

  1. ^ 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

References

See also

Algorithms used for the same purpose:

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Cohen-Sutherland — In computer graphics, the Cohen Sutherland algorithm is a line clipping algorithm. The algorithm divides a 2D space into 9 parts, of which only the middle part (viewport) is visible. The algorithmThe algorithm includes, excludes or partially… …   Wikipedia

  • Algoritmo de Cohen-Sutherland — El algoritmo de Cohen Sutherland es un algoritmo de recorte de líneas usado en gráficos por computadora. Fue desarrollado por Danny Cohen e Ivan Sutherland en 1967. Contenido 1 Introducción 2 Funcionamiento 2.1 Códigos de frontera …   Wikipedia Español

  • Sutherland-Hodgeman — Der Algorithmus von Sutherland Hodgman ist ein Algorithmus der Computergrafik zum Clipping von Polygonen. Inhaltsverzeichnis 1 Grundversion 2 Erweiterte Version 3 Literatur 4 Weblinks …   Deutsch Wikipedia

  • Sutherland Hodgman — Der Algorithmus von Sutherland Hodgman ist ein Algorithmus der Computergrafik zum Clipping von Polygonen. Inhaltsverzeichnis 1 Grundversion 2 Erweiterte Version 3 Literatur 4 Weblinks …   Deutsch Wikipedia

  • Algorithmus von Sutherland-Hodgman — Der Algorithmus von Sutherland Hodgman ist ein nach Ivan Sutherland und Gary W. Hodgman benannter Algorithmus der Computergrafik zum Clipping von Polygonen. Inhaltsverzeichnis 1 Grundversion 1.1 Pseudo Code 2 Erweiterte Version …   Deutsch Wikipedia

  • Cyrus–Beck algorithm — The Cyrus–Beck algorithm is a line clipping algorithm. It was designed to be more efficient than the Sutherland–Cohen algorithm which uses repetitive clipping [1]. Cyrus–Beck is a general algorithm and can be used with a convex polygon clipping… …   Wikipedia

  • Nicholl–Lee–Nicholl — The Nicholl Lee Nicholl algorithm is a fast line clipping algorithm that reduces the chances of clipping a single line segment multiple times, as may happen in the Cohen Sutherland algorithm. Description Using the Nicholl–Lee–Nicholl algorithm,… …   Wikipedia

  • Line clipping — In computer graphics, line clipping is the process of removing lines or portions of lines outside of an area of interest. Typically, any line or part thereof which is outside of the viewing area is removed.There are two common algorithms for line …   Wikipedia

  • Algoritmo de Liang-Barsky — El algoritmo de Liang Barsky es un algoritmo de recorte de líneas similar al algoritmo de Cohen Sutherland. Usa la ecuación paramétrica de la línea y desigualdades describiendo el rango del área de recorte para determinar las intersecciones entre …   Wikipedia Español

  • Clipping (computer graphics) — Any procedure which identifies that portion of a picture which is either inside or outside a picture is referred to as a clipping algorithm or clipping. The region against which an object is to be clipped is called clipping window. Contents 1… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”