Algoritmo de Liang-Barsky

Este algoritmo se basa en el algoritmo propuesto por Cyrus-Beck. La diferencia es que el algoritmo de Liang-Barsky aplica ciertas interpretaciones geométricas y simplificaciones al basarse en un rectángulo vertical de recorte. Con un rectángulo vertical, podemos definir los vectores normales sin problemas al igual que los vectores en las aristas. Veamos una tabla de ciertos valores y las simplificaciones que podemos realizar.

Arista de Recorte    Normal, N    Vértice, V    P0-V    D = P1-P0    t = -N⋅(P0 - V) / N⋅D
izquierda: x = xizq    (-1,0)    (xizq, Vy)    (x0-xizq, y0-Vy)    (x1-x0, y1-y0)    -(x0-xizq) / (x1-x0)   
derecha: x = xder (1,0) (xder, Vi.y) (x0-xder, y0-Vy)    (x1-x0, y1-y0)    (x0-xder) / -(x1-x0)   
superior: y = ysup (0,-1) (Vi.x, ysup) (x0-Vx, y0-ysup)    (x1-x0, y1-y0)    -(y0-ysup) / (y1-y0)   
inferior: y = yinf (0,1) (Vi.x, yinf) (x0-Vx, y0-yinf)    (x1-x0, y1-y0)    (y0-yinf) / -(y1-y0)   

Según esta tabla, vemos que el cálculo de t se reduce a una división de distancias entre coordenadas homogéneas: anchuras para el recorte de las coordenadas en X y alturas para el recorte de las coordenadas en Y. El numerador pasa a ser la distancia del punto extremo del segmeneto a la arista. Esta distancia equivale a la misma cantidad que usamos en el método de Cohen-Sutherland al calcular el código binario para cada punto extremo. También podemos ver que el denominador es la anchura, dx, o la altura, dy. Según el signo de estas longitudes, el segmento es PE o PS, y por ello los signos del numerador y del denominador se deben conservar, para que el algoritmo funcione correctamente.

Ejemplo

Descripción

[IMAGEN]: Figura 24 - Ejemplo del Algoritmo de Liang-Barsky
Figura 24 - Ejemplo

Retomamos el mismo ejemplo del método exhaustivo. Tenemos un rectángulo de recorte cuya diagonal es de (-1,3) a (3,-3) que representa nuestra vista. Queremos mostrar el segmento AB, en tal rectángulo de recorte, descrito por los puntos,

A = ( -2, 1 )  y  B = ( 2, 2 )

Solución

[IMAGEN]: Figura 25 - Calculamos t[e] y t[s] para la intersección con la arista izquierda
Figura 25 - Arista Izquierda

Calculamos el vector D de A a B:

D = B - A = (  2,  2 ) - ( -2,  1 ) = (  4,  1 )

Comprobamos el caso trivial en el que los dos puntos representan un mismo punto visible, en lugar de un segmento. Como D ≠ (0,0), tenemos un segmento.

Calculamos la intersección del segmento AB con la arista izquierda. Como el denominador, Dx = 4, es positivo, calculamos t:

     R.xizq - Ax    -1 - (-2)    1
t = ------------ = --------- = --- = 0,25
          Dx           4        4

Como t > te, actualizamos te = 0,25. El intervalo de t por ahora es [0,25, 1].

[IMAGEN]: Figura 26 - Calculamos t[e] y t[s] para la intersección con la arista derecha
Figura 26 - Arista Derecha

Calculamos la intersección del segmento AB con la arista derecha. Usamos el denominador, -Dx = -4, que al ser negativo, calculamos t:

     Ax - R.xder     -2 - 3     -5
t = ------------ = -------- = ---- = 1,25
         -Dx          -4       -4

Como t > ts, no actualizamos ts. El intervalo de t por ahora sigue siendo [0,25, 1].

[IMAGEN]: Figura 27 - Calculamos t[e] y t[s] para la intersección con la arista inferior
Figura 27 - Arista Inferior

Calculamos la intersección del segmento AB con la arista inferior. Usamos el denominador, Dy = 1, que al ser positivo, calculamos t:

     R.yinf - Ay     -3 - 1
t = ------------ = -------- = -4
          Dy           1

Como t < te, no actualizamos te. El intervalo de t por ahora sigue siendo [0,25, 1].

[IMAGEN]: Figura 28 - Calculamos t[e] y t[s] para la intersección con la arista superior
Figura 28 - Arista Superior

Calculamos la intersección del segmento AB con la arista superior. Usamos el denominador, -Dy = -1, que al ser negativo, calculamos t:

     Ay - R.ysup     1 - 3
t = ------------ = ------- = 2
         -Dy          -1

Como t > ts, no actualizamos ts. El intervalo de t por ahora sigue siendo [0,25, 1].

[IMAGEN]: Figura 29 - Calculamos los puntos extremos a partir de t[e] y t[s]
Figura 29 - Solución Final

Como ts no fue actualizado, no necesitamos que realizar ningún cáculo. Como te fue actualizado, calculamos el punto entrante de intersección, A:

A′ = A + te * ( Dx, Dy ) 
   = ( -3,  1 ) + 0,25 * (  4,  1 ) 
   = ( -2,  1,25 )

Algoritmo

Tenemos varias funciones a destacar para implementar este 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 vertical, R, que contiene los elementos \ representando las coordenadas de las dos esquinas izquierda superior y derecha inferior.
  • La función Recortar_Punto() se invocará para tratar el segmento como un único punto. Básicamente, se realizará el algoritmo explicado anteriormente. El resultado es un valor booleano que indicará si el punto fue recortado (verdadero) o no (falso).
  • La función Calcular_Parámetros() servirá para calcular los parámetros, te y ts. Necesitamos pasar el numerador, el denominador, y los parámetros, te y ts, que serán modificados. Esta función nos indicará si estos parámetros, te y ts, han sido modificados y por tanto, el segmento es aceptado (verdadero) o rechazado (falso).

Para Recortar(), el algoritmo es:

booleano Recortar( ref Punto P, ref Punto Q, Rectángulo R )
  1. dx ← Q.x - P.x
  2. dy ← Q.y - P.y
  3. resultado ← falso
  4. Si dx = 0, y Si dy = 0, y Si Recortar_Punto( P, R ) = verdadero, entonces
  5. Q ← P
  6. resultado ← verdadero
  7. Si no, entonces
  8. te ← 0
  9. ts ← 1
  10. Si Calcular_Parámetros( R.xizq-P.x, dx, te, ts ) = verdadero, entonces
  11. Si Calcular_Parámetros( P.x-R.xder, -dx, te, ts ) = verdadero, entonces
  12. Si Calcular_Parámetros( R.yinf-P.y, dy, te, ts ) = verdadero, entonces
  13. Si Calcular_Parámetros( P.y-R.ysup, -dy, te, ts ) = verdadero, entonces
  14. resultado ← verdadero
  15. Si ts < 1, entonces
  16. Q.x ← P.x + ts dx
  17. Q.y ← P.y + ts dy
  18. Si te > 0, entonces
  19. P.x ← P.x + te dx
  20. P.y ← P.y + te dy
  21. Terminar( resultado )

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, el algoritmo termina con el valor falso, lo cual implica que los parámetros, P y Q, no son alterados. En cualquier caso, se pasan estos dos parámetros por referencia, para así poder modificarlos.

A continuación presentamos el algoritmo para Calcular_Parámetros(), el cual requiere el numerador, el denominador, te, y ts, los cuales estos dos últimos se pasan por referencia:

booleano Calcular_Parámetros( real numerador, real denominador, ref real te, ref real ts )
  1. Si denominador > 0, entonces
  2. t ← numerador / denominador
  3. Si t > ts
  4. Terminar( falso )
  5. Si no, compruebe que t > te
  6. te ← t
  7. Si no, compruebe que denominador < 0,
  8. t ← numerador / denominador
  9. Si t < te
  10. Terminar( falso )
  11. Si no, compruebe que t < ts
  12. ts ← t
  13. Si no, compruebe que numerador > 0,
  14. Terminar( falso )
  15. Terminar( verdadero )