Algoritmo de Newell

De Wikipedia, la enciclopedia libre

El Algoritmo de Newell es un procedimiento de gráficos 3D por computadora usado para eliminar ciclos de polígonos en la ordenación por profundidad necesaria para la eliminación de caras ocultas. Fue propuesto en 1972 por M.E.Newell, R.Newell y T.Sancha.

En la fase de ordenación por profundidad de la eliminación de superficies ocultas, si dos polígonos no se superponen entre ellos ni tienen ni máximos ni mínimos extremos en las direcciones x, y, z, entonces pueden ser ordenados con facilidad. Si dos polígonos, Q y P, se superponen entre ellos en la dirección del eje z, entonces es posible que sea necesario cortarlos.

Los polígonos cíclicos deben ser eliminados para poder ordenarlos correctamente por profundidad

En ese caso, el Algoritmo de Newell hace lo siguiente:

1. Comprueba que se superpongan entre ellos en el eje Z; implicado en la selección de la cara Q de la lista de ordenación.

2. Las coordenadas extremas en X de las dos caras no se superponen(prueba minimax en X)

3. Las coordenadas extremas en Y de las dos caras no se superponen (prueba minimax en Y)

4. Todos los vértices de P están más lejos que los del plano Q

5. Todos los vértices de Q están más cercanos al campo de visión que el plano P.

6. La rasterización de P y Q no se superpone.

Las pruebas están ordenadas en función de su dificultad de cálculo.

Los polígonos deben ser planos.

Si las pruebas no se cumplen, entonces se deben dividir los polígonos. La división se hace seleccionando un polígono y cortándolo a lo largo de la línea de intersección con el otro polígono. De nuevo se ejecutan las pruebas anteriores hasta que todos los polígonos pasen las comprobaciones.

[editar] Referencias

Ivan E. Sutherland, Robert F, Sproull, and Robert A, Schumacker, “A Characterization of Ten Hidden-Surface Algorithms”, Computing Surveys, Vol 6, No 1, March 1974
Newell, M E, Newell R. G, and sancha, T.L, “ A New Approach to the Shaded Picture Problem”, Proc ACM National Conf. 1972