Algoritmo de Liang-Barsky

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:

1. La ecuación paramétrica de la recta.
2. 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:

Se pueden calcular los parámetros t ₁ y t _{2 que definen la parte de la línea que se encuentra dentro del rectángulo de recorte.}
Cuando,

1. p _k < 0, se toma el máximo (0, q _k /p _k ).
2. p _k > 0, se toma el mínimo (1, q _k /p _k ).

Si t ₁ > t ₂ , 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 –

1. Establezca t _mín = 0, t _máx = 1.
2. 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.
3. Si t _min < t _max , dibuje una línea desde (x ₁ + t _min (x ₂ -x ₁ ), y ₁ + t _min (y ₂ -y ₁ )) hasta (x ₁ + t _max (x ₂ -x ₁ ), y ₁ + t _máx (y ₂ -y ₁ ))
4. Si la línea cruza sobre la ventana, (x ₁ + t _min (x ₂ -x ₁ ), y ₁ + t _min (y ₂ -y ₁ )) y (x ₁ + t _max (x ₂ -x ₁ ), y ₁ + t _max (y ₂ -y ₁ )) 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 ₁ = 0 y t ₂ = 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