Algoritmo de Warnock
# Algoritmo de Warnock

El algoritmo de Warnock es un algoritmo de determinación de caras ocultas inventado por John Warnock generalmente utilizado en computación gráfica, como solución al problema de visualización de imágenes complicadas por subdivisión recursiva de una escena hasta que las áreas obtenidas sean fácilmente calculables. En otras palabras, hasta que la escena sea tan sencilla que permita calcular eficientemente su visualización.

Este es un algoritmo divide y vencerás de orden $O(np)$ siendo $n$ el número de polígonos y $p$ el número de pixeles en el área de dibujo (viewport en inglés).

Las entradas son una lista de polígonos y un área de dibujo. El mejor caso se presenta cuando la lista de polígonos es sencilla, entonces se puede dibujar los polígonos en el área de dibujo. Por sencillo se entiende que el polígono mida un pixel (en cuyo caso el polígono o su parte se dibuja en la correspondiente parte del área de dibujo) o que el área de dibujo mida un pixel (en cuyo caso el pixel toma el color del polígono más cercano al observador). El paso recurrente consiste en dividir el área de dibujo en cuatro cuadrantes de igual tamaño y llamar al algoritmo para cada cuadrante con la lista de polígonos modificada tal que lo sólo contenga polígonos visibles en el cuadrante.

