Line clipping

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged into Clipping (computer graphics). (Discuss)

It has been suggested that this article be split into multiple articles. (Discuss)

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.

1 Cohen-Sutherland
2 Liang-Barsky
3 Fast-Clipping
4 Cyrus-Beck
5 Nicholl-Lee-Nicholl
6 See also
7 References

[edit] Cohen-Sutherland

Main article: 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.

[edit] Liang-Barsky

Main article: 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.

[edit] Fast-Clipping

It has been suggested that this section be split into a new article. (Discuss)

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

It has been suggested that this section be split into a new article. (Discuss)

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

[edit] Nicholl-Lee-Nicholl

Main article: Nicholl-Lee-Nicholl

[edit] See also

Clipping (computer graphics)

[edit] References

This article does not cite any references or sources. (May 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

Categories: Clipping (computer graphics)

Hidden categories: Articles to be merged since September 2007 | Articles to be split | Articles lacking sources from May 2007 | All articles lacking sources

Line clipping

From Wikipedia, the free encyclopedia

Contents

[edit] Cohen-Sutherland

[edit] Liang-Barsky

[edit] Fast-Clipping

[edit] Cyrus-Beck

[edit] Nicholl-Lee-Nicholl

[edit] See also

[edit] References

Views

Navigation

Interaction

Search

Languages