El algoritmo Warnock es un algoritmo de superficie oculta inventado por John Warnock que se utiliza habitualmente en el campo de los gráficos por ordenador . [1] Resuelve el problema de renderizar una imagen complicada mediante la subdivisión recursiva de una escena hasta obtener áreas que sean fáciles de calcular. En otras palabras, si la escena es lo suficientemente sencilla como para calcularla de forma eficiente, se renderiza; de lo contrario, se divide en partes más pequeñas que también se prueban para comprobar su simplicidad. [2]
Este es un algoritmo de divide y vencerás con un tiempo de ejecución de [ dudoso – discutir ] , donde n es el número de polígonos y p 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, entonces se dibujan los polígonos en la ventana gráfica. Simple se define como un polígono (entonces el polígono o parte de él 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 recursivamente al algoritmo para cada cuadrante, con una lista de polígonos modificada de modo que solo contenga polígonos que sean visibles en ese cuadrante.
Warnock expresó su algoritmo en palabras e imágenes, en lugar de en código de software, como el núcleo de su tesis doctoral, en la que también describía protocolos para sombrear superficies oblicuas y otras características que ahora son el núcleo de los gráficos informáticos tridimensionales. La tesis completa constaba de tan solo 26 páginas, desde la Introducción hasta la Bibliografía.
El algoritmo fue la tesis doctoral de Warnock., 32 páginas