El algoritmo Warnock es un algoritmo de superficie oculta inventado por John Warnock que se usa típicamente en el campo de los gráficos por computadora . [1] Resuelve el problema de renderizar una imagen complicada mediante la subdivisión recursiva de una escena hasta que se obtienen áreas que son triviales de calcular. En otras palabras, si la escena es lo suficientemente simple para computar de manera eficiente, entonces se renderiza; de lo contrario, se divide en partes más pequeñas que también se prueban para su simplicidad. [2]
Este es un algoritmo de divide y vencerás con tiempo de ejecución de, donde n es el número de polígonos yp es el número de píxeles en la ventana gráfica.
Las entradas son una lista de polígonos y una ventana gráfica. El mejor caso es que si la lista de polígonos es simple, dibuje los polígonos en la ventana gráfica. Simple se define como un polígono (luego el polígono o su parte se dibuja en la parte apropiada de una ventana gráfica) o una ventana gráfica que tiene un tamaño de un píxel (entonces ese píxel obtiene un color del polígono más cercano al observador). El paso continuo es dividir la ventana gráfica en 4 cuadrantes de igual tamaño y llamar de forma recursiva el algoritmo para cada cuadrante, con una lista de polígonos modificada de modo que solo contenga polígonos que son visibles en ese cuadrante.
Warnock expresó su algoritmo en palabras e imágenes, en lugar de código de software, como el núcleo de su tesis doctoral, que también describió protocolos para sombrear superficies oblicuas y otras características que ahora son el núcleo de los gráficos por computadora tridimensionales. La tesis completa tenía solo 26 páginas de Introducción a la bibliografía.
Referencias
- ^ Warnock, John (1969). "Un algoritmo de superficie oculta para imágenes de medios tonos generadas por computadora" . Universidad de Utah.
El algoritmo fue la tesis doctoral de Warnock.
, 32 páginas
También: http://www.codersnotes.com/notes/warnock-subdivision-for-deferred-lighting/warnock.pdf - ^ Daintith, John; Wright, Edmund (2009). Diccionario Oxford de Computación . Prensa de la Universidad de Oxford. ISBN 978-0-19-923400-4., 608 páginas