Algoritmo de Newell

Algoritmo de Newell

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.

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

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Algoritmo del pintor — El algoritmo del pintor es una de las soluciones más simples para el problema de visibilidad en los gráficos 3D por computadora: Cuando se proyecta una escena de tres dimensiones en un plano de dos, es necesario determinar qué polígonos son… …   Wikipedia Español

  • Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW …   Wikipedia Español

  • Donald Knuth — Nombre …   Wikipedia Español

  • Historia del hardware — La máquina analítica de Charles Babbage, en el Science Museum de Londres. El hardware ha sido un componente importante del proceso de cálculo y almacenamiento de datos desde que se volvió útil para que los valores numéricos fueran procesados y… …   Wikipedia Español

  • Michael Oser Rabin — Para el violínista, véase Michael Rabin (violinista). Michael Oser Rabin Nombre …   Wikipedia Español

  • Inteligencia artificial — «IA» redirige aquí. Para otras acepciones, véase IA (desambiguación). Inteligencia artificial TOPIO, un robot humanoide, jugando tenis de mesa en Tokio International Robot Exhibition (IREX) 2009 …   Wikipedia Español

  • Adopciones — Wikiproyecto:Adopciones Saltar a navegación, búsqueda Atajo PR:ADPR:AD El Wikiproyecto Adopciones tiene como propósito que los distintos wikipedistas se encarguen de la vigilancia de cierto tipo de artículos que pueden ser propensos al vandalismo …   Wikipedia Español

  • Wikiproyecto:Adopciones — Atajo PR:ADPR:AD El Wikiproyecto Adopciones tiene como propósito que los distintos wikipedistas se encarguen de la vigilancia de cierto tipo de artículos que pueden ser propensos al vandalismo. Para participar de este wikiproyectos solo necesitas …   Wikipedia Español

  • Historia de la inteligencia artificial — La Inteligencia Artificial surge definitivamente a partir de algunos trabajos publicados en la década de 1940 que no tuvieron gran repercusión, pero a partir del influyente trabajo en 1950 de Alan Turing, matemático británico, se abre una nueva… …   Wikipedia Español

  • Premio Turing — El Premio Turing es un premio de las Ciencias de la Computación que es otorgado anualmente por la Asociación para la Maquinaria Computacional (ACM) a quienes hayan contribuido de manera trascendental al campo de las ciencias computacionales. El… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”