Algoritmo De Recorte De líneas De Liang-Barsky

En 1984, Liang y Barsky desarrollaron de forma independiente un algoritmo para recorte de línea paramétrica más eficiente que es especialmente rápido en el caso de regiones de recorte horizontal y vertical de 2D y 3D.

Además de aprovechar estos bordes de recorte simples, introdujeron pruebas triviales de rechazo más eficientes que trabajan para regiones de recorte generales.

En el algoritmo de Cohen-Sutherlan, para las líneas que no pueden aceptarse o rechazarse trivialmente, se calcula

La intersección (x,y) de un segmento de línea con un arista de recorte sustituyendo el valor conocido de x o y del arista de recorte vertical u horizontal, respectivamente.

El algoritmo de línea paramétrica, sin embargo, encuentra el valor del parámetro u en la representación paramétrica del segmento de línea para el punto donde el segmento intersecta la línea infinita del arista de recorte.

Como todas las aristas de recorte son, en general, intersectadas por la línea, cuatro valores de u se calculan.

Una serie de comparaciones sencillas se usan para determinar cuál (si alguno) de los cuatro valores de u corresponde a las intersecciones actuales.

Solo entonces se calculan los valores (x,y) para una o dos intersecciones reales.

Teniendo como consideración la figura siguiente en donde se observa en plano de recorte, su vector normal y el punto de intersección de la recta a recortar, se procede a explicar el algoritmo de Liang-Barsky.

Los segmentos de línea expresados de forma paramétrica como, para 0 ≤u ≤ 1,

P = P1 + u(P2 -P1) = P1 + u∆P

donde P = (x,y), P1 = (x1,y1) y P2 = (x2,y2).

Se escoge un punto arbitrario PEi sobre el arista Ei y se consideran los tres vectores P - PEi de PEi a los tres puntos designados en la línea de P1 a P2:

· El punto de intersección a ser determinado,

· un extremo de la línea en el plano interno, y

· un extremo de la línea en el plano externo.

Se puede distinguir en que región está un punto viendo el valor del producto de punto Ni ·[P - PEi].

· Este valor es negativo para un punto está en el plano interior, ya que el ángulo entre los dos vectores está dentro del intervalo de 90 a 180 grados ( a ×bcosᶿ ), siendo cosᶿ negativo en tal intervalo.

· cero para un punto en la línea conteniendo el arista ( a ×bcosᶿ ), ya que el ángulo entre los dos vectores seria

90 grados, y cos 90 = 0.

· positivo para un punto que está en el medio plano exterior, ya que el ángulo entre los dos vectores está dentro

del intervalo de 0 a 90 grados ( a ×bcosᶿ ), siendo cosᶿ positivo en tal intervalo.

Ahora se puede resolver el

...