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:

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,

  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 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 –

  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 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 ))
  4. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *