Algoritmo de Recorte de Líneas - Cohen-Sutherland

En este post explicaré el algoritmo de recorte de lineas Cohen-Shuterland y su aplicación en Opengl.

El algoritmo de recorte de Cohen-Shuterland:

• Este algoritmo realiza varias comprobaciones iniciales para descubrir si se puede evitar cálculos de las intersecciones.
• Eliminar porciones de la escena fuera del espacio de visualización (ventana de recorte).
• Región rectangular, coordenadas límite (XWmin, YWmin) – (XWmax, YWmax).

Este es uno de los procedimientos de recorte de líneas mas antiguo y común.

A todos los extremos de línea de una imagen se asigna un código binario de cuatro dígitos, que se conoce como código de región, el cual identifica la localización del punto con respecto de las fronteras del rectángulo de recorte.

De derecha a izquierda:

• bit 1: izquierda
• bit 2: derecha
• bit 3: abajo
• bit 4: arriba

1. Se calculan las diferencias entre las coordenadas de los extremos de la línea y las fronteras de recorte.
2. Se utiliza el bit del signo resultante de cada calculo de diferencias para establecer el valor correspondiente en el código de región.

• El bit 1 es el bit de signo de x - wxmin .
• El bit 2 es el bit de signo de wxmax - x.
• El bit 3 es el bit de signo de y - ywmin .
• El bit 4 es el bit de signo de ywmax - y.

• Cualquier línea que se encuentre por completo dentro de las fronteras de la ventana tiene un código de región de 0000 para ambos extremos y se aceptan estas líneas en forma común.
• Cualquier línea que tenga un 1 en la misma posición de bit en los códigos de bit para cada extremo se halla por completo afuera del rectángulo de recorte y se rechazan estas líneas en forma común. Un método que se puede emplear para probar estas líneas para el recorte total consiste en realizar la operación lógica and con ambos códigos de región.

Las líneas que no se pueden identificar como completamente adentro o completamente afuera de la ventana de recorte mediante estas pruebas se verifican para saber si intersectan las fronteras de la ventana. Como se muestra en la siguiente figura, estas líneas pueden o no cruzar hacia el interior de la ventana.

Parcialmente dentro-fuera: verificar intersección con los límites de la ventana. 

• 1 en un punto y 0 en el mismo bit del otro punto → la línea cruza el límite de recorte correspondiente. 
• se actualizan las coordenadas del punto. 
• se recalculan los códigos de región.

Intersección con límite vertical (dado x):

$$y=y_0+m(x-x_0)$$

donde se asigna el valor de x ya sea xmin o xmax

Intersección con límite horizontal (dado y):

$$x=x_0+(y-y_0)/m$$

ya sea con y como ymin o ymax

EJEMPLO

Primero las líneas de las cuales se aplicará el recorte.

Luego la ventana donde se aplicará el recorte a las lineas.

ymin=0, ymax=10, xmin=0, xmax=12

calculando el código de todos los puntos en su respectiva región

Para AB:
 A: 0000
 B: 0000
Ambos puntos se encuentran dentro de la ventana recorte

Para CD:
 C: 1001
 D: 0101
Coinciden en el bit 1, por lo que la linea se encuentra completamente fuera.

Para EF:
 E: 0000
 F: 0100
El punto E se encuentra dentro de la ventana pero el punto F se encuentra fuera, por lo que a esta línea se le aplicará recorte.

ymin es 0, por lo que el punto a calcular es 'x'.

x0 = 10
y0=-2
m= -2.3
$$x=10+(0-(-2))/-2.3$$
x≅9.14