El algoritmo de Cohen-Sutherland es un algoritmo de gráficos por computadora que se utiliza 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 de 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 (O bit a bit de puntos finales = 0000): aceptación trivial .
- Ambos extremos 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). A continuación, se calcula la intersección del punto de salida y el borde de la vista ampliada (es decir, con la ecuación paramétrica de la línea), y este nuevo punto sustituye al punto de salida. 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 en el código de salida 2D representan: arriba, abajo, derecha, izquierda. Por ejemplo, el código de salida 1010 representa un punto que se encuentra en la parte superior derecha de la ventana gráfica.
izquierda central derecho cima 1001 1000 1010 central 0001 0000 0010 fondo 0101 0100 0110
Tenga en cuenta que los códigos de salida para los puntos finales se deben volver a calcular en cada iteración después de que se produzca el recorte.
El algoritmo de Cohen-Sutherland solo se puede utilizar en una ventana de clip rectangular .
Ejemplo de implementación de C / C ++
typedef int OutCode ;const int DENTRO = 0 ; // 0000 const int LEFT = 1 ; // 0001 const int DERECHA = 2 ; // 0010 const int BOTTOM = 4 ; // 0100 const int TOP = 8 ; // 1000// Calcula el código de bits para un punto (x, y) usando el clip // delimitado diagonalmente por (xmin, ymin) y (xmax, ymax)// ASUME QUE xmax, xmin, ymax e ymin son constantes globales.OutCode ComputeOutCode ( doble x , doble y ) { Código de salida ;código = DENTRO ; // inicializado como dentro de [[ventana de clip]]if ( x < xmin ) // a la izquierda del código de la ventana del clip | = LEFT ; else if ( x > xmax ) // a la derecha del código de la ventana del clip | = RIGHT ; if ( y < ymin ) // debajo del código de la ventana del clip | = BOTTOM ; else if ( y > ymax ) // encima del código de la ventana del clip | = TOP ; 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). void CohenSutherlandLineClipAndDraw ( doble x0 , doble y0 , doble x1 , doble y1 ) { // calcula los códigos de salida para P0, P1 y cualquier punto que se encuentre fuera del rectángulo del clip OutCode outcode0 = ComputeOutCode ( x0 , y0 ); OutCode outcode1 = ComputeOutCode ( x1 , y1 ); bool accept = false ;while ( verdadero ) { if ( ! ( outcode0 | outcode1 )) { // bit a bit OR es 0: ambos puntos dentro de la ventana; aceptar trivialmente y salir del bucle accept = true ; romper ; } else if ( outcode0 & outcode1 ) { // bit a bit Y no es 0: ambos puntos comparten una zona exterior (IZQUIERDA, DERECHA, SUPERIOR, // o INFERIOR), por lo que ambos deben estar fuera de la ventana; bucle de salida (aceptar es falso) romper ; } else { // falló ambas pruebas, así que calcule el segmento de línea a recortar // desde un punto exterior a una intersección con el borde del clip double x , y ;// Al menos un punto final está fuera del rectángulo del clip; recogerlo. OutCode outcodeOut = outcode1 > outcode0 ? outcode1 : outcode0 ;// Ahora encuentra el punto de intersección; // use 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 dividir por cero porque, en cada caso, el // bit de código de salida que se está probando garantiza que el denominador es distinto de cero if ( outcodeOut & TOP ) { // el punto está encima de 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 del clip x = x0 + ( x1 - x0 ) * ( ymin - y0 ) / ( y1 - y0 ); y = ymin ; } else if ( outcodeOut & RIGHT ) { // el punto está a la derecha de la ventana del clip y = y0 + ( y1 - y0 ) * ( xmax - x0 ) / ( x1 - x0 ); x = xmax ; } else if ( outcodeOut & LEFT ) { // el punto está a la izquierda de la ventana del clip y = y0 + ( y1 - y0 ) * ( xmin - x0 ) / ( x1 - x0 ); x = xmin ; }// Ahora nos movemos del punto exterior al punto de intersección para recortar // y nos preparamos para la siguiente pasada. si ( outcodeOut == outcode0 ) { x0 = x ; y0 = y ; outcode0 = ComputeOutCode ( x0 , y0 ); } más { x1 = x ; y1 = y ; outcode1 = ComputeOutCode ( x1 , y1 ); } } } }
Notas
- ^ Principios de gráficos por computadora interactivos , p. 124, 252, por Bob Sproull y William M. Newman, 1973, McGraw – Hill Education, edición internacional, ISBN 0-07-085535-8 .
Ver también
Algoritmos utilizados para el mismo propósito:
Referencias
- James D. Foley. Infografía: principios y práctica . Addison-Wesley Professional, 1996. pág. 113.