Algoritmos

Algoritmos de recorte

El algoritmo de Cohen-Sutherland es un algoritmo de recorte de líneas usado en gráficos por computadora. Fue desarrollado por Danny Cohen e Ivan Sutherland en1967.

Funcionamiento

Cada punto tiene asignados unos códigos de frontera que indican la posición de ese punto respecto al viewport. Cada código de frontera se compone de 4 bits.

El algoritmo incluye, excluye, o incluye parcialmente, la línea (segmento) basado en dónde están sus puntos extremos:

• Ambos puntos están en el viewport (la operación bitwise OR de sus puntos extremos es igual a cero): aceptación trivial.
• Ambos puntos están en la misma región no visible (la operación bitwise AND de sus puntos extremos no es igual a cero): rechazo trivial.
• Ambos puntos están en regiones distintas: En caso de esta situación no trivial el algoritmo encuentra uno de los 2 puntos que está fuera del viewport (hay al menos un punto fuera). La intersección del punto exterior con la frontera extendida es entonces calculada (es decir, con la ecuación paramétrica de la línea) y este nuevo punto reemplaza al punto exterior. El algoritmo se repite hasta que ocurre un éxito o rechazo trivial.

Puede verse en el dibujo un ejemplo para cada caso. Nótese como sólo las porciones de las líneas dentro del área verde (coloreadas de azul) necesitan ser dibujadas.

Códigos de frontera

Los números en la figura inferior se llaman códigos de frontera. Un código de frontera es calculado para cada uno de los dos puntos extremos de la línea (tanto para el punto inicial como el punto final de la línea). El primer bit es asignado a 1 si el punto esta por encima del viewport. Los bits del código de frontera representan: Arriba, Abajo, Derecha, Izquierda. Por ejemplo el código de frontera 1010 representa un punto que está arriba y a la derecha del viewport. Note que los puntos de frontera tienen que ser recalculados en cada iteración después de que el corte ocurre.

1001	1000	1010
0001	0000	0010
0101	0100	0110

Analizando los valores y pasándolos a decimal (que resulta más comprensible a cualquier audiencia), puede analizarse que horizontalmente, hay una separación de 1 unidad entre el valor central y el de su izquierda y entre éste y el valor de la derecha (8,9,10 - 0,1,2 - 4,5,6). Y de modo equivalente hay una separación verticalmente de 4 unidades entre un valor de la fila central y el de la fila inferior y entre éste y el de la fila superior (1,5,9 - 0,4,8 - 2,6,10.

09	08	10
01	00	02
05	04	06

Algoritmo de Cohen-Sutherland

Aquí está el algoritmo de Cohen-Sutherland

Implementación en Pascal

procedure CohenSutherlandLineClipAndDraw(
       x0,y0,x1,y1,xmin,xmax,ymin,ymax : real ; value: integer);
{ Cohen-Sutherland clipping algorithm for line P0=(x0,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}

Implementación en C#

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";
    }

Algoritmo de Cyrus-Beck











Ilustración del algoritmo de Cyrus-Beck.



El algoritmo de Cyrus-Beck es un algoritmo de recorte de líneas y polígonos convexos. De forma similar al algoritmo de Cohen-Sutherland también utiliza aristas extendidas. Se puede adaptar muy fácilmente entre rayos y polígonos convexos o segmentos y polígonos convexos.

Implementación del algoritmo de Cyrus-Beck en C#

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";