Hispanopedia WikiEn gráficos por computadora , el algoritmo de Cohen-Sutherland es un algoritmo utilizado para el recorte de líneas . El algoritmo divide un espacio bidimensional en 9 regiones y luego determina de manera eficiente las líneas y porciones de líneas que son visibles en la región central de interés (la ventana gráfica ).
El algoritmo fue desarrollado en 1967 durante el trabajo de simulador de vuelo por Danny Cohen e Ivan Sutherland . [1]
El algoritmo
El algoritmo incluye, excluye o incluye parcialmente la línea en función de si:
- Ambos puntos finales están en la región de la ventana gráfica (OR bit a bit de los puntos finales = 0000): trivial accept .
- Ambos puntos finales comparten al menos una región no visible, lo que implica que la línea no cruza la región visible. (AND bit a bit de puntos finales ≠ 0000): rechazo trivial .
- Ambos puntos finales están en regiones diferentes: en el caso de esta situación no trivial, el algoritmo encuentra uno de los dos puntos que está fuera de la región de la ventana gráfica (habrá al menos un punto fuera). Luego se calcula la intersección del punto final y el borde extendido de la ventana gráfica (es decir, con la ecuación paramétrica de la línea), y este nuevo punto reemplaza al punto final. El algoritmo se repite hasta que se produce una aceptación o un rechazo trivial.
Los números de la figura siguiente se denominan códigos de salida . Se calcula un código de salida para cada uno de los dos puntos de la línea. El código de salida tendrá 4 bits para el recorte bidimensional o 6 bits en el caso tridimensional. El primer bit se establece en 1 si el punto está por encima de la ventana gráfica. Los bits del código de salida 2D representan: superior, inferior, derecha, izquierda. Por ejemplo, el código de salida 1010 representa un punto que está en la parte superior derecha de la ventana gráfica.
Tenga en cuenta que los códigos de salida de los puntos finales deben recalcularse en cada iteración después de que se produce el recorte.
El algoritmo Cohen-Sutherland solo se puede utilizar en una ventana de recorte rectangular .
Ejemplo de implementación en C/C++
typedef int Código de salida ;
const int INTERIOR = 0b0000 ; const int IZQUIERDA = 0b0001 ; const int DERECHA = 0b0010 ; const int ABAJO = 0b0100 ; const int ARRIBA = 0b1000 ;
// Calcular el código de bits para un punto (x, y) utilizando el rectángulo de recorte
// delimitado diagonalmente por (xmin, ymin) y (xmax, ymax)
// ASUMIR QUE xmax, xmin, ymax e ymin son constantes globales.
OutCode ComputeOutCode ( double x , double y ) { OutCode code = INSIDE ; // inicializado como dentro de la ventana del clip
if ( x < xmin ) // a la izquierda de la ventana de recorte código |= IZQUIERDA ; de lo contrario if ( x > xmax ) // a la derecha de la ventana de recorte código |= DERECHA ; if ( y < ymin ) // debajo de la ventana de recorte código |= ABAJO ; de lo contrario if ( y > ymax ) // encima de la ventana de recorte código |= ARRIBA ;
código de retorno ; }
// El algoritmo de recorte de Cohen-Sutherland recorta una línea desde
// P0 = (x0, y0) a P1 = (x1, y1) contra un rectángulo con
// diagonal desde (xmin, ymin) a (xmax, ymax).
bool CohenSutherlandLineClip ( double & x0 , double & y0 , double & x1 , double & y1 ) { // Calcula los códigos de salida para P0, P1 y cualquier punto que se encuentre fuera del rectángulo de recorte OutCode outcode0 = ComputeOutCode ( x0 , y0 ); OutCode outcode1 = ComputeOutCode ( x1 , y1 ); bool accept = false ;
mientras ( verdadero ) { si ( ! ( outcode0 | outcode1 )) { // OR bit a bit es 0: ambos puntos dentro de la ventana; aceptar trivialmente y salir del bucle accept = true ; break ; } de lo contrario si ( outcode0 y outcode1 ) { // AND bit a bit no es 0: ambos puntos comparten una zona exterior (IZQUIERDA, DERECHA, SUPERIOR o INFERIOR), por lo que ambos deben estar fuera de la ventana; salir del bucle (accept es falso) break ; } de lo contrario { // falló ambas pruebas, por lo que calcula el segmento de línea a recortar // desde un punto exterior a una intersección con el borde de recorte double x , y ;
// Al menos un punto final está fuera del rectángulo de recorte; selecciónelo.
OutCode outcodeOut = outcode1 > outcode0 ? outcode1 : outcode0 ;
// Ahora encuentra el punto de intersección;
// usa fórmulas: // pendiente = (y1 - y0) / (x1 - x0) // x = x0 + (1 / pendiente) * (ym - y0), donde ym es ymin o ymax // y = y0 + pendiente * (xm - x0), donde xm es xmin o xmax // No hay necesidad de preocuparse por la división por cero porque, en cada caso, el bit de código de salida que se está probando garantiza que el denominador no sea cero if ( outcodeOut & TOP ) { // el punto está sobre la ventana de recorte x = x0 + ( x1 - x0 ) * ( ymax - y0 ) / ( y1 - y0 ); y = ymax ; } else if ( outcodeOut & BOTTOM ) { // el punto está debajo de la ventana de recorte x = x0 + ( x1 - x0 ) * ( ymin - y0 ) / ( y1 - y0 ); y = ymin ; } else if ( outcodeOut & RIGHT ) { // el punto está a la derecha de la ventana de recorte y = y0 + ( y1 - y0 ) * ( xmax - x0 ) / ( x1 - x0 ); x = xmax ; } else if ( outcodeOut & LEFT ) { // el punto está a la izquierda de la ventana de recorte y = y0 + ( y1 - y0 ) * ( xmin - x0 ) / ( x1 - x0 ); x = xmin ; }
// Ahora nos movemos fuera del punto al punto de intersección para recortar
// y prepararnos para el siguiente pase. if ( outcodeOut == outcode0 ) { x0 = x ; y0 = y ; outcode0 = ComputeOutCode ( x0 , y0 ); } else { x1 = x ; y1 = y ; outcode1 = ComputeOutCode ( x1 , y1 ); } } } return accept ; }
Notas
- ^ Principios de gráficos informáticos interactivos , pág. 124, 252, por Bob Sproull y William M. Newman, 1973, McGraw–Hill Education, edición internacional, ISBN 0-07-085535-8 .
Véase también
Algoritmos utilizados para el mismo propósito:
Referencias
- James D. Foley. Gráficos por ordenador: principios y práctica . Addison-Wesley Professional, 1996. pág. 113.
Enlaces externos
- Biblioteca de recorte de polilíneas de JavaScript que utiliza el algoritmo Cohen-Sutherland
- Implementación de JavaScript animada
- Implementación de Delphi
- Implementación de Stata