Cohen-Sutherland

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 algorithm

The algorithm includes, excludes or partially includes the line based on where the two endpoints are:

* Both endpoints are in the viewport (bitwise OR of endpoints = 0): trivial accept.
* Both endpoints are on the same side of the rectangle, which is not visible (bitwise AND of endpoints != 0): trivial reject.
* Both endpoints are in different parts: In case of this non trivial situation the algorithm finds one of the two points that are outside the viewport (there is 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.

Here is the algorithm for Cohen-Sutherlandprocedure CohenSutherlandLineClipAndDraw( x0,y0,x1,y1,xmin,xmax,ymin,ymax : real ; value: integer);{ Cohen-Sutherland clipping algorithm for line P0=(x0,y0) to P1=(x1,y1)and clip rectangle with diagonal from (xmin,ymin) to (xmax,ymax).}type edge = (LEFT,RIGHT,BOTTOM,TOP); outcode = set of edge;var accept,done : boolean; outcode0,outcode1,outcodeOut : outcode; {Outcodes for P0,P1, and whichever point lies outside the clip rectangle} x,y : real; procedure CompOutCode(x,y: real; var code:outcode); {Compute outcode for the point (x,y) } begin code := [] ; if y > ymax then code := [TOP] else if y < ymin then code := [BOTTOM] ;

if x > xmax then code := code + [RIGHT] else if x < xmin then code := code + [LEFT] end;

begin accept := false; done := false; CompOutCode (x0,y0,outcode0); CompOutCode (x1,y1,outcode1); repeat if(outcode0= [] ) and (outcode1= [] ) then {Trivial accept and exit} begin accept := true; done:=true end else if (outcode0*outcode1) <> [] then done := true {Logical intersection is true, so trivial reject and exit.} else {Failed both tests, so calculate the line segment to clip; from an outside point to an intersection with clip edge.} begin {At least one endpoint is outside the clip rectangle; pick it.} if outcode0 <> [] then outcodeOut := outcode0 else outcodeOut := outcode1; {Now find intersection point; use formulas y=y0+slope*(x-x0),x=x0+(1/slope)*(y-y0).}

if TOP in outcodeOut then begin {Divide line at top of clip rectangle} x := x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y := ymax end else if BOTTOM in outcodeOut then begin {Divide line at bottom of clip rectangle} x := x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y := ymin end

if RIGHT in outcodeOut then begin {Divide line at right edge of clip rectangle} y := y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x := xmax end else if LEFT in outcodeOut then begin {Divide line at left edge of clip rectangle} y := y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x := xmin end;

{Now we move outside point to intersection point to clip, and get ready for next pass.} if (outcodeOut = outcode0) then begin x0 := x; y0 := y; CompOutCode(x0,y0,outcode0) end else begin x1 := x; y1 := y; CompOutCode(x1,y1,outcode1); end end {subdivide} until done; if accept then MidpointLineReal(x0,y0,x1,y1,value) {Version for real coordinates}end; {CohenSutherlandLineClipAndDraw}

ee also

Algorithms used for the same purpose:
* Liang-Barsky
* Cyrus-Beck
* Nicholl-Lee-Nicholl
* Fast-Clipping

Wikimedia Foundation. 2010.

Look at other dictionaries:

• 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,… …   Wikipedia

• Cohen-Sutherland-Algorithmus — Der Algorithmus von Cohen Sutherland ist ein Algorithmus zum Clipping von Linien an einem Rechteck. Er ist nach seinen Erfindern Dan Cohen und Ivan Sutherland benannt. Der Algorithmus gilt als populärster, wenn auch nicht effizientester für seine …   Deutsch 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

• Algorithmus von Cohen-Sutherland — Der Algorithmus von Cohen Sutherland ist ein Algorithmus zum Clipping von Linien an einem Rechteck. Er ist nach seinen Erfindern Dan Cohen und Ivan Sutherland benannt. Der Algorithmus gilt als populärster, wenn auch nicht effizientester für seine …   Deutsch Wikipedia

• Cohen — ist ein jüdischer Familienname. Der Familienname hat die höchste Verbreitung vergleichbar mit Müller und Schmidt in der deutschsprachigen Welt oder mit Smith in der englischsprachigen Welt. Herkunft und Bedeutung Cohen ist der biblische Name von… …   Deutsch Wikipedia

• Sutherland — hace referencia a: Contenido 1 Personas 2 Lugares 3 Entidades 4 Matemáticas Personas Alexander Sutherla …   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

• Cohen, Albert — ▪ American criminologist born June 15, 1918, Boston, Massachusetts, U.S.       American criminologist best known for his subcultural theory of delinquent gangs. In 1993 Cohen received the Edwin H. Sutherland Award from the American Society of… …   Universalium

• Algoritmo de Sutherland-Hodgman — Sutherland Hodgman Empezando por el conjunto inicial de vertices del polígono, primero recorta el poligono contra una frontera para producir una nueva secuencia de vertices, con esta nueva secuencia se recorta contra otra frontera y así… …   Wikipedia Español