Line clipping: Difference between revisions

Revision as of 23:35, 13 January 2007

Latest revision as of 02:57, 18 June 2025

(151 intermediate revisions by 97 users not shown)

Line 1:

{{Short description|In [[computer graphics]], '''line clipping''' is the process of removing lines or portionsremoval of lines outside of an area of interest. Typically, any line or part thereof which is outside of the viewingview area is removed./volume}}

[[Image:Line2_clipping.png|370x370px|right|Example of line clipping for a two-dimensional region]]

In [[computer graphics]], '''line clipping''' is the process of removing ([[Clipping (computer graphics)|clipping]]) lines or portions of lines outside an area of interest (a [[viewport]] or [[view volume]]). Typically, any part of a line which is outside of the viewing area is removed.

There are two common algorithms for line clipping: Cohen-Sutherland and Liang-Barsky.

There are two common algorithms for line clipping: [[Cohen–Sutherland]] and [[Liang–Barsky]].

== Cohen-Sutherland ==

A line-clipping method consists of various parts. Tests are conducted on a given line segment to find out whether it lies outside the view area or volume. Then, [[intersection]] calculations are carried out with one or more clipping boundaries.<ref>{{Cite web|url = http://www.cse.unt.edu/~renka/4230/LineClipping.pdf|title = Line Clipping|date = 2014-10-19|publisher = Department of Computer Science & Engineering, University of North Texas|last = Renka|first = R. J.|access-date = 2016-01-12}}</ref> Determining which portion of the line is inside or outside of the clipping volume is done by processing the endpoints of the line with regards to the intersection.

This algorithm divides a 2D space into 9 parts, of which only the middle part (viewport) is visible. The algorithm includes, excludes or partially includes the line based on where the two endpoints are:

==Cohen–Sutherland==

* Both endpoints are in the viewport (bitwise OR of endpoints == 0): trivial accept.

{{Main|Cohen–Sutherland algorithm}}

* Both endpoints are in the same part, which is not visible (bitwise AND of endpoints != 0): trivial reject.

In computer graphics, the Cohen–Sutherland algorithm (named after [[Danny Cohen (computer scientist)|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.

* 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.

In 1967, flight-simulation work by Danny Cohen led to the development of the Cohen–Sutherland computer graphics two-dimensional and three-dimensional line clipping algorithms, created with Ivan Sutherland.

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.

==Liang–Barsky==

1001 | 1000 | 1010

{{Main|Liang–Barsky algorithm}}

| |

The Liang–Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping box to determine the intersections between the line and the clipping box. With these intersections it knows which portion of the line should be drawn. This algorithm is significantly more efficient than Cohen–Sutherland, but Cohen–Sutherland does trivial accepts and rejects much faster, so it should be considered instead if most of the lines you need to clip would be completely in or out of the [[clip window]].

-----------------------

| |

0001 | 0000 | 0010

| |

------------------------

| |

0101 | 0100 | 0110

==Cyrus–Beck==

{{Main|Cyrus–Beck algorithm}}

Very similar to Liang–Barsky line-clipping algorithm. The difference is that Liang–Barsky is a simplified Cyrus–Beck variation that was optimized for a rectangular clip window.

Here is the algorithm for Cohen-Sutherland

<pre><nowiki>

procedure CohenSutherlandLineClipAndDraw(

x0,y0,x1,y1,xmin,xmax,ymin,ymax : real ; value: integer);

{ Cohen-Sutherland clipping algorithm for line P0=(x1,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;

The Cyrus–Beck algorithm is primarily intended for clipping a line in the parametric form against a convex polygon in 2 dimensions or against a convex polyhedron in 3 dimensions.<ref>Cyrus, M., Beck, J.: [https://www.sciencedirect.com/science/article/pii/0097849378900213 Generalized Two and Three Dimensional Clipping], Computers & Graphics, Vol. 3, No. 1, pp. 23–28, 1978.</ref>

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 exi

t.}

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

if BOTTOM in outcodeOut then

begin {Divide line at bottom of clip rectangle}

x := x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);

y := ymin

end

else 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 coordin

ates}

end; {CohenSutherlandLineClipAndDraw}

</nowiki></pre>

==Nicholl–Lee–Nicholl==

C# implementation for Cohen-Sutherland algorithm

{{Main|Nicholl–Lee–Nicholl algorithm}}

<pre><nowiki>

internal sealed class CohenSutherlandClipping : IClippingAlgorithm

{

private Vector2 _clipMin, _clipMax;

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. The clipping window is divided into a number of different areas, depending on the position of the initial point of the line to be clipped.

public IEnumerable<Vector2> GetBoundingPolygon()

{

yield return _clipMin;

yield return new Vector2(_clipMax.X, _clipMin.Y);

yield return _clipMax;

yield return new Vector2(_clipMin.X, _clipMax.Y);

}

==Fast clipping==

public void SetBoundingRectangle(Vector2 start, Vector2 end)

This algorithm has similarities with Cohen–Sutherland. The start and end positions are classified by which portion of the 9-area grid they occupy. A large switch statement jumps to a specialized handler for that case. In contrast, Cohen–Sutherland may have to iterate several times to handle the same case.<ref>{{cite journal|last1=Sobkow | first1 = Mark S. | last2 = Pospisil | first2 = Paul | last3 = Yang | first3 = Yee-Hong | title = A Fast Two-Dimensional Line Clipping Algorithm via Line Encoding | url = https://www.sciencedirect.com/science/article/pii/0097849387900616 | journal = Computers & Graphics | volume = 11 | number = 4 | pages = 459–467 | year = 1987}}</ref>

{

_clipMin = start;

_clipMax = end;

}

== ''O''(lg ''N'') algorithm ==

public void SetBoundingPolygon(IEnumerable<Vector2> points)

This algorithm classifies vertices against the given line in the implicit form ''p'': ''ax'' + ''by'' + ''c'' = 0. As the polygon is assumed to be convex and vertices are ordered clockwise or anti-clockwise, binary search can be applied and leads to a ''O''(lg ''N'') run-time complexity.<ref>[[Václav Skala|Skala, V.]]: ''O''(lg ''N'') Line Clipping Algorithm in E2, Computers & Graphics, Pergamon Press, Vol. 18, No. 4, 1994.</ref>

{

throw new NotSupportedException("see Capabilities =)");

}

==Skala==

private int getPointCode(Vector2 point)

This algorithm is based on [[homogeneous coordinates]] and [[Duality (projective geometry)|duality]].<ref>Skala, V.: [https://www.researchgate.net/profile/Vaclav_Skala/publication/220067375_A_new_approach_to_line_and_line_segment_clipping_in_homogeneous_coordinates/links/02bfe50f2654923b6f000000/A-new-approach-to-line-and-line-segment-clipping-in-homogeneous-coordinates.pdf A new approach to line and line segment clipping in homogeneous coordinates], The Visual Computer, ISSN 0178-2789, Vol. 21, No. 11, pp. 905–914, Springer Verlag, 2005.</ref> It can be used for line or line-segment clipping against a rectangular window, as well as against a convex polygon. The algorithm is based on classifying a vertex of the clipping window against a half-space given by a line ''p'': ''ax'' + ''by'' + ''c'' = 0. The result of the classification determines the edges intersected by the line ''p''. The algorithm is simple, easy to implement and extensible to a convex window as well. The line or line segment '''p''' can be computed from points '''r'''₁, '''r'''₂ given in homogeneous coordinates directly using the cross product as

{

:'''p''' = '''r'''₁ × '''r'''₂ = (''x''₁, ''y''₁, ''w''₁) × (''x''₂, ''y''₂, ''w''₂)

int result = 0;

or as

:'''p''' = '''r'''₁ × '''r'''₂ = (''x''₁, ''y''₁, 1) × (''x''₂, ''y''₂, 1).

if (point.X < _clipMin.X) ++result;

else if (point.X > _clipMax.X) result |= 2;

if (point.Y > _clipMax.Y) result |= 4;

else if (point.Y < _clipMin.Y) result |= 8;

return result;

}

public bool ClipLine(ref Line line)

{

Vector2 P = line.End - line.Start;

int startCode = getPointCode(line.Start);

int endCode = getPointCode(line.End);

float dxdy = 0, dydx = 0;

if (P.X != 0) dydx = P.Y / P.X;

if (P.Y != 0) dxdy = P.X / P.Y;

for (int stage = 0; stage < 4; stage++)

{

if ((startCode | endCode) == 0) return true;

else if ((startCode & endCode) != 0) return false;

if (startCode == 0)

{

int buf1 = startCode; startCode = endCode; endCode = buf1;

Vector2 buf2 = line.Start; line.Start = line.End; line.End = buf2;

}

if ((startCode & 1) == 1)

{

line.Start.Y += dydx * (_clipMin.X - line.Start.X);

line.Start.X = _clipMin.X;

}

else if ((startCode & 2) == 2)

{

line.Start.Y = line.Start.Y + dydx * (_clipMax.X - line.Start.X);

line.Start.X = _clipMax.X;

}

else if ((startCode & 4) == 4)

{

line.Start.X = line.Start.X + dxdy * (_clipMax.Y - line.Start.Y);

line.Start.Y = _clipMax.Y;

}

else if ((startCode & 8) == 8)

{

line.Start.X = line.Start.X + dxdy * (_clipMin.Y - line.Start.Y);

line.Start.Y = _clipMin.Y;

}

startCode = getPointCode(line.Start);

}

return true;

}

public ClippingCapabilities Capablities { get { return ClippingCapabilities.RectangleWindow; } }

public override string ToString()

{

return "Cohen-Sutherland algorithm";

}

}

</nowiki></pre>

== Liang-Barsky ==

The Liang-Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping box to determine the intersections between the line and the clipping box. With these intersections it knows which portion of the line should be drawn. This algorithm is significantly more efficient than Cohen-Sutherland.

==See also==

* [[Clipping (computer graphics)]]

==References==

{{compu-graphics-stub}}

{{Reflist}}

{{DEFAULTSORT:Line Clipping}}

[[Category:Computer graphics]]

[[Category:Clipping (computer graphics)]]