Algoritmo de Warnock

Visibilidad de un polígono en un área de dibujo: a) el polígono llena el área de dibujo, b) el polígono la llena parcialmente, c) el polígono es completamente visible, d) el polígono es invisible.

El algoritmo de Warnock es un algoritmo de determinación de caras ocultas inventado por John Warnock generalmente utilizado en computación gráfica,^[1] 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.^[2]

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.^[3]

Esquema del algoritmo[editar]

Warnock(PolyList PL, ViewPort VP)
If ( PL es simple en VP) then
    Dibujar PL en VP
else
    Dividir VP horizontal y verticalmente en cuadrantes VP1,VP2,VP3,VP4
    Warnock(PL en VP1, VP1)
    Warnock(PL en VP2, VP2)
    Warnock(PL en VP3, VP3)
    Warnock(PL en VP4, VP4)
end

Referencias[editar]

↑ Warnock, John (1969). «A hidden surface algorithm for computer generated halftone pictures (Tesis doctoral)». University of Utah. Archivado desde el original el 17 de abril de 2015. Consultado el 2 de febrero de 2016.
↑ Daintith, John; Wright, Edmund (2009). Oxford University Press, ed. Oxford Dictionary of Computing. ISBN 978-0-19-923400-4. Consultado el 2 de febrero de 2016.
↑ «Un resumen del algoritmo de Warnock». Consultado el 2 de febrero de 2016.

Datos: Q2549576
Multimedia: Warnock algorithm / Q2549576

[1] Warnock, John (1969). «A hidden surface algorithm for computer generated halftone pictures (Tesis doctoral)». University of Utah. Archivado desde el original el 17 de abril de 2015. Consultado el 2 de febrero de 2016.

[2] Daintith, John; Wright, Edmund (2009). Oxford University Press, ed. Oxford Dictionary of Computing. ISBN 978-0-19-923400-4. Consultado el 2 de febrero de 2016.

[3] «Un resumen del algoritmo de Warnock». Consultado el 2 de febrero de 2016.

[1]

[2]

[3]