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.

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.

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 algorithminternal sealed class FastClipping : IClippingAlgorithm { private Vector2 _clipMin, _clipMax;

public IEnumerable 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 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

Cyrus-Beck

C# implementation for Cyrus-Beck algorithminternal sealed class CyrusBeckClipping : IClippingAlgorithm { private List _clipArea = new List(); private List _normals = new List();

public IEnumerable 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 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

Nicholl-Lee-Nicholl

ee also

*Clipping (computer graphics)

References