Line clipping
From Wikipedia, the free encyclopedia
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.
Contents |
[edit] 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. 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 |
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 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}
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 += dydx * (_clipMax.X - line.Start.X);
line.Start.X = _clipMax.X;
}
else if ((startCode & 4) == 4) {
line.Start.X += dxdy * (_clipMax.Y - line.Start.Y);
line.Start.Y = _clipMax.Y;
}
else if ((startCode & 8) == 8) {
line.Start.X += dxdy * (_clipMin.Y - line.Start.Y);
line.Start.Y = _clipMin.Y;
}
startCode = getPointCode(line.Start);
}
return true;
}
public ClippingCapabilities Capabilities {
get {
return ClippingCapabilities.RectangleWindow;
}
}
public override string ToString() {
return "Cohen-Sutherland algorithm";
}
}
// This code was implemented by Grishul Eugeny as part of preparation
// to exam in ITMO university
[edit] 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.
C# implementation for Liang-Barsky algorithm
internal sealed class LiangBarskyClipping : 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 delegate bool ClippingHandler(float p, float q);
public bool ClipLine(ref Line line) {
Vector2 P = line.End - line.Start;
float tMinimum = 0, tMaximum = 1;
ClippingHandler pqClip = delegate(float directedProjection,
float directedDistance) {
if (directedProjection == 0) {
if (directedDistance < 0) return false;
}
else {
float amount = directedDistance / directedProjection;
if (directedProjection < 0) {
if (amount > tMaximum) return false;
else if (amount > tMinimum) tMinimum = amount;
}
else {
if (amount < tMinimum) return false;
else if (amount < tMaximum) tMaximum = amount;
}
}
return true;
};
if (pqClip(-P.X, line.Start.X - _clipMin.X)) {
if (pqClip(P.X, _clipMax.X - line.Start.X)) {
if (pqClip(-P.Y, line.Start.Y - _clipMin.Y)) {
if (pqClip(P.Y, _clipMax.Y - line.Start.Y)) {
if (tMaximum < 1) {
line.End.X = line.Start.X + tMaximum * P.X;
line.End.Y = line.Start.Y + tMaximum * P.Y;
}
if (tMinimum > 0) {
line.Start.X += tMinimum * P.X;
line.Start.Y += tMinimum * P.Y;
}
return true;
}
}
}
}
return false;
}
public ClippingCapabilities Capabilities {
get {
return ClippingCapabilities.RectangleWindow;
}
}
public override string ToString() {
return "Liang-Barsky algorithm";
}
}
// This code was implemented by Grishul Eugeny as part of preparation
// to exam in ITMO university
[edit] Fast-Clipping
Mark S. Sobkow, Paul Pospisil and Yee-Hong Yang. A Fast Two-Dimensional Line Clipping Algorithm via Line Encoding//Computer & Graphics, Vol. 11, No. 4, pp. 459-467, 1987.
C# implementation for Fast-Clipping algorithm
internal sealed class FastClipping : 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 =)");
}
#region cliping line endings
private void clipStartTop(ref Line line) {
line.Start.X += line.Dx * (_clipMin.Y - line.Start.Y) / line.Dy;
line.Start.Y = _clipMin.Y;
}
private void clipStartBottom(ref Line line) {
line.Start.X += line.Dx * (_clipMax.Y - line.Start.Y) / line.Dy;
line.Start.Y = _clipMax.Y;
}
private void clipStartRight(ref Line line) {
line.Start.Y += line.Dy * (_clipMax.X - line.Start.X) / line.Dx;
line.Start.X = _clipMax.X;
}
private void clipStartLeft(ref Line line) {
line.Start.Y += line.Dy * (_clipMin.X - line.Start.X) / line.Dx;
line.Start.X = _clipMin.X;
}
private void clipEndTop(ref Line line) {
line.End.X += line.Dx * (_clipMin.Y - line.End.Y) / line.Dy;
line.End.Y = _clipMin.Y;
}
private void clipEndBottom(ref Line line) {
line.End.X += line.Dx * (_clipMax.Y - line.End.Y) / line.Dy;
line.End.Y = _clipMax.Y;
}
private void clipEndRight(ref Line line) {
line.End.Y += line.Dy * (_clipMax.X - line.End.X) / line.Dx;
line.End.X = _clipMax.X;
}
private void clipEndLeft(ref Line line) {
line.End.Y += line.Dy * (_clipMin.X - line.End.X) / line.Dx;
line.End.X = _clipMin.X;
}
#endregion
public bool ClipLine(ref Line line) {
int lineCode = 0;
if (line.End.Y < _clipMin.Y) lineCode |= 8;
else if (line.End.Y > _clipMax.Y) lineCode |= 4;
if (line.End.X > _clipMax.X) lineCode |= 2;
else if (line.End.X < _clipMin.X) lineCode |= 1;
if (line.Start.Y < _clipMin.Y) lineCode |= 128;
else if (line.Start.Y > _clipMax.Y) lineCode |= 64;
if (line.Start.X > _clipMax.X) lineCode |= 32;
else if (line.Start.X < _clipMin.X) lineCode |= 16;
// 9 - 8 - A
// | | |
// 1 - 0 - 2
// | | |
// 5 - 4 - 6
switch (lineCode) {
// center
case 0x00:
return true;
case 0x01:
clipEndLeft(ref line);
return true;
case 0x02:
clipEndRight(ref line);
return true;
case 0x04:
clipEndBottom(ref line);
return true;
case 0x05:
clipEndLeft(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
case 0x06:
clipEndRight(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
case 0x08:
clipEndTop(ref line);
return true;
case 0x09:
clipEndLeft(ref line);
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
return true;
case 0x0A:
clipEndRight(ref line);
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
return true;
// left
case 0x10:
clipStartLeft(ref line);
return true;
case 0x12:
clipStartLeft(ref line);
clipEndRight(ref line);
return true;
case 0x14:
clipStartLeft(ref line);
if (line.Start.Y > _clipMax.Y) return false;
clipEndBottom(ref line);
return true;
case 0x16:
clipStartLeft(ref line);
if (line.Start.Y > _clipMax.Y) return false;
clipEndBottom(ref line);
if (line.End.X > _clipMax.X) clipEndRight(ref line);
return true;
case 0x18:
clipStartLeft(ref line);
if (line.Start.Y < _clipMin.Y) return false;
clipEndTop(ref line);
return true;
case 0x1A:
clipStartLeft(ref line);
if (line.Start.Y < _clipMin.Y) return false;
clipEndTop(ref line);
if (line.End.X > _clipMax.X) clipEndRight(ref line);
return true;
// right
case 0x20:
clipStartRight(ref line);
return true;
case 0x21:
clipStartRight(ref line);
clipEndLeft(ref line);
return true;
case 0x24:
clipStartRight(ref line);
if (line.Start.Y > _clipMax.Y) return false;
clipEndBottom(ref line);
return true;
case 0x25:
clipStartRight(ref line);
if (line.Start.Y > _clipMax.Y) return false;
clipEndBottom(ref line);
if (line.End.X < _clipMin.X) clipEndLeft(ref line);
return true;
case 0x28:
clipStartRight(ref line);
if (line.Start.Y < _clipMin.Y) return false;
clipEndTop(ref line);
return true;
case 0x29:
clipStartRight(ref line);
if (line.Start.Y < _clipMin.Y) return false;
clipEndTop(ref line);
if (line.End.X < _clipMin.X) clipEndLeft(ref line);
return true;
// bottom
case 0x40:
clipStartBottom(ref line);
return true;
case 0x41:
clipStartBottom(ref line);
if (line.Start.X < _clipMin.X) return false;
clipEndLeft(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
case 0x42:
clipStartBottom(ref line);
if (line.Start.X > _clipMax.X) return false;
clipEndRight(ref line);
return true;
case 0x48:
clipStartBottom(ref line);
clipEndTop(ref line);
return true;
case 0x49:
clipStartBottom(ref line);
if (line.Start.X < _clipMin.X) return false;
clipEndLeft(ref line);
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
return true;
case 0x4A:
clipStartBottom(ref line);
if (line.Start.X > _clipMax.X) return false;
clipEndRight(ref line);
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
return true;
// bottom-left
case 0x50:
clipStartLeft(ref line);
if (line.Start.Y > _clipMax.Y) clipStartBottom(ref line);
return true;
case 0x52:
clipEndRight(ref line);
if (line.End.Y > _clipMax.Y) return false;
clipStartBottom(ref line);
if (line.Start.X < _clipMin.X) clipStartLeft(ref line);
return true;
case 0x58:
clipEndTop(ref line);
if (line.End.X < _clipMin.X) return false;
clipStartBottom(ref line);
if (line.Start.X < _clipMin.X) clipStartLeft(ref line);
return true;
case 0x5A:
clipStartLeft(ref line);
if (line.Start.Y < _clipMin.Y) return false;
clipEndRight(ref line);
if (line.End.Y > _clipMax.Y) return false;
if (line.Start.Y > _clipMax.Y) clipStartBottom(ref line);
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
return true;
// bottom-right
case 0x60:
clipStartRight(ref line);
if (line.Start.Y > _clipMax.Y) clipStartBottom(ref line);
return true;
case 0x61:
clipEndLeft(ref line);
if (line.End.Y > _clipMax.Y) return false;
clipStartBottom(ref line);
if (line.Start.X > _clipMax.X) clipStartRight(ref line);
return true;
case 0x68:
clipEndTop(ref line);
if (line.End.X > _clipMax.X) return false;
clipStartRight(ref line);
if (line.Start.Y > _clipMax.Y) clipStartBottom(ref line);
return true;
case 0x69:
clipEndLeft(ref line);
if (line.End.Y > _clipMax.Y) return false;
clipStartRight(ref line);
if (line.Start.Y < _clipMin.Y) return false;
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
if (line.Start.Y > _clipMax.Y) clipStartBottom(ref line);
return true;
// top
case 0x80:
clipStartTop(ref line);
return true;
case 0x81:
clipStartTop(ref line);
if (line.Start.X < _clipMin.X) return false;
clipEndLeft(ref line);
return true;
case 0x82:
clipStartTop(ref line);
if (line.Start.X > _clipMax.X) return false;
clipEndRight(ref line);
return true;
case 0x84:
clipStartTop(ref line);
clipEndBottom(ref line);
return true;
case 0x85:
clipStartTop(ref line);
if (line.Start.X < _clipMin.X) return false;
clipEndLeft(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
case 0x86:
clipStartTop(ref line);
if (line.Start.X > _clipMax.X) return false;
clipEndRight(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
// top-left
case 0x90:
clipStartLeft(ref line);
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
return true;
case 0x92:
clipEndRight(ref line);
if (line.End.Y < _clipMin.Y) return false;
clipStartTop(ref line);
if (line.Start.X < _clipMin.X) clipStartLeft(ref line);
return true;
case 0x94:
clipEndBottom(ref line);
if (line.End.X < _clipMin.X) return false;
clipStartLeft(ref line);
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
return true;
case 0x96:
clipStartLeft(ref line);
if (line.Start.Y > _clipMax.Y) return false;
clipEndRight(ref line);
if (line.End.Y < _clipMin.Y) return false;
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
// top-right
case 0xA0:
clipStartRight(ref line);
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
return true;
case 0xA1:
clipEndLeft(ref line);
if (line.End.Y < _clipMin.Y) return false;
clipStartTop(ref line);
if (line.Start.X > _clipMax.X) clipStartRight(ref line);
return true;
case 0xA4:
clipEndBottom(ref line);
if (line.End.X > _clipMax.X) return false;
clipStartRight(ref line);
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
return true;
case 0xA5:
clipEndLeft(ref line);
if (line.End.Y < _clipMin.Y) return false;
clipStartRight(ref line);
if (line.Start.Y > _clipMax.Y) return false;
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
return true;
}
return false;
}
public ClippingCapabilities Capabilities {
get {
return ClippingCapabilities.RectangleWindow;
}
}
public override string ToString() {
return "Fast-Clipping algorithm";
}
}
// This code was implemented by Grishul Eugeny as part of
// preparation to exam in ITMO university
[edit] Cyrus-Beck
C# implementation for Cyrus-Beck algorithm
internal sealed class CyrusBeckClipping : IClippingAlgorithm {
private List<Vector2> _clipArea = new List<Vector2>();
private List<Vector2> _normals = new List<Vector2>();
public IEnumerable<Vector2> GetBoundingPolygon() {
return _clipArea;
}
public void SetBoundingRectangle(Vector2 start, Vector2 end) {
_clipArea.Clear();
_clipArea.Add(start);
_clipArea.Add(new Vector2(end.X, start.Y));
_clipArea.Add(end);
_clipArea.Add(new Vector2(start.X, end.Y));
computeNormals();
}
public void SetBoundingPolygon(IEnumerable<Vector2> points) {
_clipArea.Clear();
_clipArea.AddRange(points);
computeNormals();
}
private void computeNormals() {
_normals.Clear();
for (int i = 0; i < _clipArea.Count - 1; i++) {
Vector2 direction = _clipArea[i + 1] - _clipArea[i];
direction.Normalize();
_normals.Add(new Vector2(-direction.Y, direction.X));
}
{
Vector2 direction = _clipArea[0] - _clipArea[_clipArea.Count - 1];
direction.Normalize();
_normals.Add(new Vector2(-direction.Y, direction.X));
}
}
public bool ClipLine(ref Line line) {
Vector2 P = line.End - line.Start;
float tMinimum = 0, tMaximum = 1;
const float epsilon = 0.0001f;
for (int i = 0; i < _clipArea.Count; i++) {
Vector2 F = _clipArea[i];
Vector2 N = _normals[i];
Vector2 Q = line.Start - F;
float Pn = Vector2.DotProduct(P, N);
float Qn = Vector2.DotProduct(Q, N);
if (Pn < epsilon && Pn > -epsilon) {
if (Qn < 0) return false;
}
else {
float computedT = -Qn / Pn;
if (Pn < 0) {
if (computedT < tMinimum)
return false;
if (computedT < tMaximum)
tMaximum = computedT;
}
else {
if (computedT > tMaximum)
return false;
if (computedT > tMinimum)
tMinimum = computedT;
}
}
}
if (tMinimum < tMaximum) {
if (tMaximum < 1)
line.End = line.Start + tMaximum * P;
if (tMinimum > 0)
line.Start = line.Start + tMinimum * P;
}
else return false;
return true;
}
public ClippingCapabilities Capabilities {
get {
return ClippingCapabilities.ConvexWindow |
ClippingCapabilities.RectangleWindow;
}
}
public override string ToString() {
return "Cyrus-Beck algorithm";
}
}
// This code was implemented by Grishul Eugeny as part of preparation
// to exam in ITMO university
