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 clipping: Cohen-Sutherland and Liang-Barsky.
Cohen-Sutherland
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:
- Both endpoints are in the viewport (bitwise OR of endpoints == 0): trivial accept.
- Both endpoints are in the same part, 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.
1001 | 1000 | 1010
| |
-----------------------
| |
0001 | 0000 | 0010
| |
------------------------
| |
0101 | 0100 | 0110
Here is the algorithm for Cohen-Sutherland
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;
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}
C# implementation for Cohen-Sutherland algorithm
internal sealed class CohenSutherlandClipping : IClippingAlgorithm
{
private Vector2 _clipMin, _clipMax;
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);
}
public void SetBoundingRectangle(Vector2 start, Vector2 end)
{
_clipMin = start;
_clipMax = end;
}
public void SetBoundingPolygon(IEnumerable<Vector2> points)
{
throw new NotSupportedException("see Capabilities =)");
}
private int getPointCode(Vector2 point)
{
int result = 0;
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";
}
}
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
 | This computer graphics–related article is a stub. You can help Wikipedia by expanding it. |