El algoritmo de Liang-Barsky es un algoritmo de recorte de línea. Este algoritmo es más eficiente que el algoritmo de recorte de línea de Cohen-Sutherland y se puede extender al recorte tridimensional. Este algoritmo se considera el algoritmo de recorte de línea paramétrico más rápido. En este recorte se utilizan los siguientes conceptos:
- La ecuación paramétrica de la recta.
- Las desigualdades que describen el rango de la ventana de recorte que se utiliza para determinar las intersecciones entre la línea y la ventana de recorte.
La ecuación paramétrica de una recta puede estar dada por,
X = x1 + t(x2-x1) Y = y1 + t(y2-y1)
Donde, t está entre 0 y 1.
Luego, escribiendo las condiciones de recorte de puntos en la forma paramétrica:
xwmin <= x1 + t(x2-x1) <= xwmax ywmin <= y1 + t(y2-y1) <= ywmax
Las 4 desigualdades anteriores se pueden expresar como,
tpk <= qk
Donde k = 1, 2, 3, 4 (corresponden a los límites izquierdo, derecho, inferior y superior, respectivamente).
La p y q se definen como,
p1 = -(x2-x1), q1 = x1 - xwmin (Left Boundary) p2 = (x2-x1), q2 = xwmax - x1 (Right Boundary) p3 = -(y2-y1), q3 = y1 - ywmin (Bottom Boundary) p4 = (y2-y1), q4 = ywmax - y1 (Top Boundary)
Cuando la línea es paralela al límite de una ventana de vista, el valor p para ese límite es cero.
Cuando p k < 0, a medida que t aumenta la línea va de afuera hacia adentro (entrante).
Cuando p k > 0, la línea va de adentro hacia afuera (salida).
Cuando p k = 0 y q k < 0, la línea es trivialmente invisible porque está fuera de la ventana de visualización.
Cuando p k = 0 y q k > 0, la línea está dentro del límite de la ventana correspondiente.
Usando las siguientes condiciones, se puede determinar la posición de la línea:
Condición | Posición de la línea |
---|---|
pag = 0 | paralelo a los límites de recorte |
p k = 0 y q k < 0 | completamente fuera del límite |
p k = 0 y q k >= 0 | dentro del límite de recorte paralelo |
pag < 0 | la línea procede de afuera hacia adentro |
p k > 0 | la línea procede de adentro hacia afuera |
Se pueden calcular los parámetros t 1 y t 2 que definen la parte de la línea que se encuentra dentro del rectángulo de recorte.
Cuando,
- p k < 0, se toma el máximo (0, q k /p k ).
- p k > 0, se toma el mínimo (1, q k /p k ).
Si t 1 > t 2 , la línea está completamente fuera de la ventana de recorte y puede ser rechazada. De lo contrario, los extremos de la línea recortada se calculan a partir de los dos valores del parámetro t.
Algoritmo –
- Establezca t mín = 0, t máx = 1.
- Calcule los valores de t (t (izquierda), t (derecha), t (arriba), t (abajo)),
(i) Si t < t min , ignore eso y muévase al siguiente borde.
(ii) de lo contrario, separe los valores t como valores de entrada o salida usando el producto interno.
(iii) Si t está ingresando valor, establecer t min = t; si t es un valor existente, establezca t max = t. - Si t min < t max , dibuje una línea desde (x 1 + t min (x 2 -x 1 ), y 1 + t min (y 2 -y 1 )) hasta (x 1 + t max (x 2 -x 1 ), y 1 + t máx (y 2 -y 1 ))
- Si la línea cruza sobre la ventana, (x 1 + t min (x 2 -x 1 ), y 1 + t min (y 2 -y 1 )) y (x 1 + t max (x 2 -x 1 ), y 1 + t max (y 2 -y 1 )) son el punto de intersección de la línea y el borde.
Este algoritmo se presenta en el siguiente código. Los parámetros de intersección de línea se inicializan a los valores t 1 = 0 y t 2 = 1.
#include"graphics.h" #define ROUND(a) ((int)(a+0.5)) int clipTest (float p,float q, float * tl, float * t2) { float r ; int retVal = TRUE; //line entry point if (p < 0.0) { r = q /p ; // line portion is outside the clipping edge if ( r > *t2 ) retVal = FALSE; else if (r > *t1 ) *tl = r; } else //line leaving point if (p>0.0) { r = q/p ; // line portion is outside if ( r<*t1 ) retVal = FALSE; else i f (r<*t2) *t2 = r; } // p = 0, so line is parallel to this clipping edge else // Line is outside clipping edge if (q<0.0) retVal = FALSE; return ( retVal ) ; } void clipLine (dcPt winMin, dcPt winMax, wcPt2 pl , wcPt2 p2) { float t1 = 0.0, t2 = 1.0, dx = p2.x-p1.x, dy; // inside test wrt left edge if(clipTest (-dx, p1.x - winMin.x, &t1, &t2)) // inside test wrt right edge if(clipTest (dx, winMax.x - p1.x, &t1, &t2)) { dy = p2.y - p1.y; // inside test wrt bottom edge if(clipTest (-dy, p1.y - winMin.y, &t1, &t2)) // inside test wrt top edge if(clipTest (dy, winMax.y - p1.y, &t1, &t2)) { if(t2 < 1.0) { p2.x = p1.x + t2*dx; p2.y = p1.y + t2*dy; } if(t1 > 0.0) { p1.x += t1*dx; p1.y += t1*dy; } lineDDA ( ROUND(p1.x), ROUND(p1.y), ROUND(p2.x), ROUND(p2.y) ); } } }
Referencia: Gráficos por computadora por Donald Hearn, M.Pauline Baker
Publicación traducida automáticamente
Artículo escrito por lakshmiprabha y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA