Algoritmo de Cohen-Sutherland

Este algoritmo realiza varias comprobaciones iniciales para descubrir si se puede evitar cálculos de las intersecciones. El primer paso es comprobar si los puntos extremos del segmento son aceptados por sus posiciones. Si esto no es posible, entonces realizamos varias comprobaciones por regiones exteriores al rectángulo de recorte, formadas por las líneas rectas al extender sus aristas. Asimismo, podemos rechazar un segmento inmediatamente si sus extremos yacen en regiones a la izquierda de xizq, por encima de ysup, a la derecha de xder, y por debajo de yinf.

Si el segmento no se puede aceptar ni rechazar inmediatamente, entonces es partido en dos segmentos por un arista del rectángulo de recorte, para que uno de ellos sea rechazado de inmediato. Esto implica que implementamos un método iterativo de recorte para el segmento hasta que éste sea aceptado o rechazado. Este algoritmo es eficiente especialmente en el caso de tener un rectángulo de recorte muy grande que comprende a todos o una gran mayoría de los segmentos a visualizar. Asimismo, podemos tener el caso de un rectángulo de recorte muy pequeño que fuerza a todos o casi todos los segmentos a ser rechazados.

Se le asigna un código de cuatro bits, b3b2b1b0, a cada región de las nueve creadas. Este código binario es creado estratégicamente para representar rápida y fácilmente cada región. El valor de 1 indicará que un extremo yace en tal región mientras que un 0 indicará lo contrario. Aquí tenemos la estrategia a usar:

Bit Condición Descripción
b3 y > ysup  por encima de la arista superior
b2 y < yinf  por debajo de la arista inferior
b1 x > xder  a la derecha de la arista derecha
b0 x < xizq  a la izquierda de la arista izquierda
[IMAGEN]: Figura 9 - Las regiones con los Códigos del Algoritmo de Cohen-Sutherland
Figura 9 - Las regiones con los Códigos

Usaremos ciertas operaciones a nivel de bit para asginar el código regional a cada extremo en el que yace y también para determinar tal región cuando necesitemos discriminarlos. Una forma eficiente de asignar un valor a un bit particular es tomando el primer bit que indica el signo positivo o negativo de la resta entre las dos coordenadas de la condición. Esto es, b3 es asignado el bit del signo de (ysup-y), b2 es asignado el bit de (y - yinf), b1 es asignado el bit de (xsup-x), y b0 es asignado el bit de (x - xinf).

La figura 9 muestra las regiones con sus correspondientes códigos.

Con estos códigos podemos determinar si los extremos, y por tanto el segmento que representan, pueden ser aceptados o rechazados inmediatamente. Obviamente, si ambos códigos son 0, entonces ambos extremos existen dentro del rectángulo de recorte, y por consiguiente el segmento es aceptado de inmediato. Para combinar estos dos códigos, simplemente aplicamos una operación OR y comprobamos si el resultado es 0. Si el código no es 0, entonces aplicamos la operación AND a ambos códigos. Si el resultado no es cero, entonces rechazamos el segmento de inmediato.

Si no podemos aceptar ni rechazar inmediatamente el segmento, entonces iremos dividiendo el segmento y comprobando sus nuevos códigos, para determinar su aceptación o rechazo. Dividimos el segmento calculando la intersección con las líneas creadas al extender las aristas del rectángulo de recorte. Si no podemos discriminar el nuevo segmento, entonces debemos continuar dividiéndolo hasta que al final lo aceptamos o lo rechazamos. Una propiedad notable es que modificamos el segmento mudando el extremo, cuyo código no es cero. Dicho de otra manera, el algoritmo elige un extremo exterior que será mudado a la intersección con la arista o con la línea que separa y define las regiones. Asignamos el código regional del punto de intersección al extremo mudado.

La desventaja de este algoritmo es que puede realizar varias intersecciones antes de alcanzar la intersección final y válida. Una mejora es calcular la pendiente para determinar el punto de intersección una sola vez y conservarla para posteriores iteraciones. Aun con esta mejora, este algoritmo no es tan eficiente. Por otro lado, la ventaja de este algoritmo es su simplicidad y además se puede extender fácilmente al caso de un volumen de recorte en 3D.

Ejemplo

Descripción

[IMAGEN]: Figura 10 - Ejemplo del Algoritmo de Cohen-Sutherland
Figura 10 - Ejemplo

Queremos mostrar varios segmentos, pero únicamente dentro de nuestra vista representada por un rectángulo vertical descrito con las siguientes esquinas: superior izquierda (-1,3) e inferior derecha (3,-3). Tenemos los siguientes segmentos definidos por parejas de puntos que forman sus extremos:
A = (-2, 1) y B = ( 2, 2),
C = ( 1, 4) y D = ( 0,-4),
E = ( 4, 3) y F = ( 3, 0),
G = (-3,-1) y H = (-2,-4).

Solución

[IMAGEN]: Figura 11 - Ejemplo Solución con Códigos
Figura 11 - Solución

Calculamos los códigos regionales para cada punto:

A: 0001  B: 0000
C: 1000  D: 0100
E: 0010  F: 0000
G: 0001  H: 0101
[IMAGEN]: Figura 12 - Ejemplo Solución Aplicando Criterios
Figura 12 - Aplicando Criterios

Aplicamos nuestros criterios a los resultados de las operaciones a nivel de bit de los códigos regionales de cada punto dando lugar a:

AB: 0001 OR 0000 = 0001  ⇒  0001 AND 0000 = 0000  ⇒  Hay que recortar
CD: 1000 OR 0100 = 1100  ⇒  1000 AND 0100 = 0000  ⇒  Hay que recortar
EF: 0010 OR 0000 = 0010  ⇒  0010 AND 0000 = 0000  ⇒  Hay que recortar
GH: 0001 OR 0101 = 0101  ⇒  0001 AND 0101 = 0001  ⇒  Inmediatamente lo rechazamos
[IMAGEN]: Figura 13 - Ejemplo Solución Recortando con las Primeras Aristas Encontradas
Figura 13 - Recortando

Hacemos la primera tanda de recortes de los puntos con sus primeras aristas del algoritmo, obteniendo:

\{ A'x = -1
\{ A'y =  1 + 1 * 1 / 4 = 1,25

\{ C'x =  1 - 1 * 1 / (-8) = 1,125
\{ C'y =  3

\{ E'x =  3
\{ E'y =  3 - 3 * (-1) / (-1) = 0

Recalculamos los códigos de cada punto:

A′B: 0000 OR 0000 = 0000  ⇒  Aceptamos el segmento
C′D: 0000 OR 0100 = 0100  ⇒  0000 AND 0100 = 0000  ⇒  Hay que recortar
E′F: 0000 OR 0000 = 0000  ⇒  Aceptamos el segmento
[IMAGEN]: Figura 14 - Ejemplo Solución Recortar C′D
Figura 14 - Recortando

Nos falta recortar una segunda vez para el segmento C′D. El algoritmo elige el punto D para recortar, obteniendo:

\{ D'x =  0 + 1,125 * 1 / 7 = 0,1607
\{ D'y = -3

Recalculamos los códigos de cada punto:

C′D′: 0000 OR 0000 = 0000  ⇒  Aceptamos el segmento
[IMAGEN]: Figura 15 - Ejemplo Solución Final
Figura 15 - Final

Al final, obtenemos la siguiente imagen con los segmentos recortados e interiores al rectángulo de recorte.

Algoritmo

La función principal es Recortar(), la cual aceptará tres parámetros: dos puntos extremos, P y Q, donde cada uno contiene las coordenadas (x,y) que representan el segmento a recortar, y un rectángulo, R, que contiene los elementos \ representando las coordenadas de las dos esquinas izquierda superior y derecha inferior. También debemos definir los códigos binarios para: SUPERIOR=8, INFERIOR=4, DERECHA=2, e IZQUIERDA=1.

Para Recortar(), el algoritmo es:

booleano Recortar( ref Punto P, ref Punto Q, Rectángulo R )
  1. aceptar ← falso
  2. terminar ← falso
  3. códigoP ← Calcular_Código(P,R)
  4. códigoQ ← Calcular_Código(Q,R)
  5. Repetir:
  6. Si (códigoP OR códigoQ) = 0, entonces
  7. aceptar ← verdadero
  8. terminar ← verdadero
  9. Si no, compruebe que (códigoP AND códigoQ) ≠ 0,
  10. terminar ← verdadero
  11. Si no, entonces
  12. Si códigoP = 0, entonces
  13. código ← códigoQ
  14. Si no, entonces
  15. código ← códigoP
  16. Si código es SUPERIOR, entonces
  17. Δy ← Q.y-P.y
  18. Si Δy = 0, entonces // segmento vertical
  19. x ← P.x
  20. Si no, entonces
  21. x ← P.x + (Q.x-P.x)*(R.ysup-P.y) / Δy
  22. y ← ysup
  23. Si no, compruebe que código es INFERIOR
  24. Δy ← Q.y-P.y
  25. Si Δy = 0, entonces // segmento vertical
  26. x ← P.x
  27. Si no, entonces
  28. x ← P.x + (Q.x-P.x)*(R.yinf-P.y) / Δy
  29. y ← yinf
  30. Si no, compruebe que código es DERECHA
  31. x ← xder
  32. y ← P.y + (Q.y-P.y)*(R.xder-P.x) / (Q.x-P.x)
  33. Si no, entonces // código = IZQUIERDA
  34. x ← xizq
  35. y ← P.y + (Q.y-P.y)*(R.xizq-P.x) / (Q.x-P.x)
  36. Si código = códigoP, entonces
  37. P.x ← x
  38. P.y ← y
  39. códigoP ← Calcular_Código(P,R)
  40. Si no, entonces
  41. Q.x ← x
  42. Q.y ← y
  43. códigoQ ← Calcular_Código(Q,R)
  44. Mientras que terminar = falso
  45. Terminar( aceptar )

Si el segmento es aceptado, entonces el algoritmo terminará con el valor booleano verdadero. Además, los extremos, P y Q, contendrán los valores recortados por este mismo algoritmo. Si el segmento es rechazado, entonces uno debería hacer caso omiso de los parámetros, P y Q. En cualquier caso, se pasan estos dos parámetros por referencia, para así poder modificarlos.

A continuación presentamos el algoritmo para Calcular_Código(), el cual requiere un punto, P, y el rectángulo de recorte, R:

entero Calcular_Código( Punto P, Rectángulo R )
  1. código ← 0
  2. Si P.y > R.ysup, entonces
  3. código ← código OR SUPERIOR
  4. Si no, compruebe que P.y < R.yinf
  5. código ← código OR INFERIOR
  6. Si P.x > R.xder, entonces
  7. código ← código OR DERECHA
  8. Si no, compruebe que P.x < R.xizq
  9. código ← código OR IZQUIERDA
  10. Terminar( código )

No todos los lenguajes de programación aceptan realizar operaciones a nivel de bit con números que no sean enteros. Tampoco todos los lenguajes establecen exactamente la cantidad de bits para representar internamente un número real. Por estas razones, no hemos presentado el algoritmo mejorado para Calcular_Código() que previamente hablamos en este apartado.

Suponiendo que un número real se representase con 32 bits y el 32º bit contiene su signo positivo, como 0, o negativo, como 1, aquí presentamos otra versión del algoritmo Calcular_Código():

entero Calcular_Código( Punto P, Rectángulo R )
  1. código ← (((P.y - R.ysup) SHR 31) SHL 3) OR (((R.yinf - P.y) SHR 31) SHL 2) OR (((P.x - R.xder) SHR 31) SHL 1) OR ((R.xizq - P.x) SHR 31)
  2. Terminar( código )

El operador SHL se refiere a la operación común de desplazamiento de bits a la izquierda y el operador SHR se refiere a la del desplazamiento de bits a la derecha.