WARNOCK, EL ALGORITMO DE JHON WARNOCK
Computación gráfica
Es el campo de la informática visual, donde se utilizan computadoras para generar imágenes visuales y espaciales del mundo real. También podemos definirlo como el arte de transmitir información usando imágenes que son generadas mediante la computación, la computación gráfica nace en 1955 con SAGE, una máquina creada durante la Guerra Fría por el ejército de Estados Unidos para poder ubicar las naves aéreas que entraban al territorio norteamericano, desarrollada para convertir los sonidos de detección de un radar en imágenes, fue el primero en emplear un lápiz óptico para seleccionar símbolos en la pantalla, Jhon Edward Warnock es uno de los aportadores más resaltantes en este campo.
John Edward Warnock
Fue un científico informático, inventor, empresario tecnológico y filántropo estadounidense, mejor conocido por cofundar Adobe Systems Inc., empresa de software gráfico y editorial, con Charles Geschke en 1982. Warnock fue pionero en el desarrollo de tecnologías gráficas, editoriales, web y de documentos electrónicos que han revolucionado el campo de la publicación y las comunicaciones visuales.
En su tesis doctoral de 1969, Warnock inventó el algoritmo Warnock para la determinación de superficies ocultas en gráficos por computadora. Funciona mediante la subdivisión recursiva de una escena hasta obtener áreas que son triviales de calcular. Resuelve el problema de renderizar una imagen complicada evitando el problema. Si la escena es lo suficientemente simple para calcular, se renderiza; de lo contrario, se divide en partes más pequeñas y se repite el proceso. Warnock señaló que por este trabajo recibió “la dudosa distinción de haber escrito la tesis doctoral más corta en la historia de la Universidad de Utah“.
El algoritmo de 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 píxeles en el área de dibujo. 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 píxel 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 píxel 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 sólo contenga polígonos visibles en el cuadrante.
Como se puede ver en la figura, en el primer caso nuestro marco de subdivisión debe contener completamente al objeto, en el caso 2 la intersección se ve cuando contiene parte del objeto, en el caso tres el marco no contiene absolutamente nada y en el último escenario el marco se encuentra completamente dentro del objeto o polígono.
Uso del algoritmo
El algoritmo de warnock es una de las soluciones que se encuentran en el enfoque de “visibilidad” y su resultado que son rectángulos(bloques) de píxeles, se encarga de dar una mejor visibilidad por cada respectivo cuadrante que llegó a subdividirse, a su vez este se considera que tiene precisión de imagen, dado a que se calcula el polígono visible en cada bloque.
Para usar este algoritmo inicialmente necesitamos dos parámetros, una lista de polígonos y la vista inicial que comprende todos los polígonos que se pueden encontrar en el “canvas”. Después de haber recibido los parámetros el algoritmo mira si es posible darle solución al marco de vista que se está enfocando actualmente dado a los casos base, si es así entonces este pintara en pantalla los píxeles de la imagen, en caso contrario se dividirá el rectángulo actual en cuatro partes y cada una de ellas se le aplica el algoritmo warnock de nuevo, de manera recursiva.
El algoritmo warnock hace parte de los algoritmos de “Hidden Surface Removal (HSR) “ , son los algoritmos que nos permite conocer qué vistas y superficies son visibles de una imagen llena de polígonos, sin importar la manera en que estos estén superpuestos o cruzados unos a otros. Este algoritmo es de complejidad O(np), siendo n el número de polígonos que encontramos en su lista y p el número de píxeles del canvas principal o conocido como el “viewport”. Cabe resaltar que en el peor de los casos el algoritmo tendrá que dividir el viewport hasta llegar a un área del tamaño de un pixel.
Conociendo el algoritmo
Ya conociendo las posibles relaciones dadas en la figura, para decidir si debemos renderizar la imagen contenida en el marco o si debemos seguir subdividiendo en cuatro partes iguales tenemos los siguientes casos:
- Encontramos que en el área actual, todos los polígonos son disjuntos, esto es que el área se encuentra vacía y ningún polígono de la lista se puede notar dentro de ella
2. Solo existe un polígono contenido dentro del marco en su totalidad o en una parte, ya sea que este sea intersección con el marco
3. Hay un solo polígono que se encuentra completamente en el área y es circundante, esto es que la ocupa en su totalidad.
4. Hay varios polígonos intersectados, solo que unos están encima de otros, en este caso se mira el eje z y los cuatro vértices que forman el marco y al cual se le quiere dar visibilidad, en este caso se subdivide el área.
Expandiendo el algoritmo
El algoritmo no es único, sino que existe una colección de ellos. De hecho, hay un algoritmo para cada interpretación de “ventana simple” y para cada método de subdivisión de ventanas, sean simples o no.
Para definir un criterio que determine el significado de “ventana simple”, es necesario considerar las posibles posiciones de un polígono con respecto a una ventana. En general, los polígonos se pueden clasificar en tres tipos:
- Disjuntos: cuando la intersección entre el polígono y la ventana es nula.
- Envolventes: cuando la ventana está completamente contenida dentro del polígono.
- Intersección o contención: cuando el polígono interseca la ventana o está totalmente contenido en ella.
Todo polígono disjunto de una ventana también será disjunto de cualquier posible subventana. De manera similar, si un polígono envuelve una ventana, también envolverá cualquier subventana dentro de ella. Además, un polígono envolvente oculta a todos aquellos que están más alejados, sin importar su clasificación.
Conclusión del algoritmo de Warnock
La informática gráfica ha experimentado una evolución notable desde sus comienzos en los años 50 con el sistema SAGE, pasando de ser un instrumento militar a transformarse en una de las áreas más impactantes en la tecnología contemporánea. Actualmente, es un elemento esencial en áreas como la animación, la simulación, el diseño industrial y los videojuegos, facilitando la generación de imágenes digitales cada vez más auténticas y minuciosas. Uno de los progresos fundamentales en esta área ha sido la creación de algoritmos eficaces para la representación y el manejo de imágenes, tal como el algoritmo de Warnock, propuesto por John Warnock en su tesis doctoral en 1969.
El algoritmo de Warnock representa una respuesta revolucionaria al problema de las superficies escondidas en los gráficos computacionales. Su método “divide y vencerás” facilita el manejo eficaz de imágenes complejas, segmentando la escena en zonas más reducidas hasta que se pueda determinar la visibilidad de cada zona. Este enfoque ha resultado fundamental en la renderización de gráficos, pues previene operaciones superfluas al enfocarse en fragmentos mínimos de la imagen, optimizando la eficacia y la calidad de la representación visual. Su influencia alcanza múltiples usos, desde simulaciones de ciencia hasta gráficos en tiempo real en el sector del entretenimiento.
Importancia
La importancia de la informática gráfica no solo se basa en su habilidad para producir imágenes, sino en cómo cambia nuestra interacción con la tecnología. Desde interfaces de usuario visuales hasta ambientes de realidad virtual, la habilidad para ilustrar de manera visual información compleja que ha propiciado la creación de nuevas herramientas y usos en diversas disciplinas. Adicionalmente, el progreso en hardware especializado, como las GPU, ha impulsado aún más el avance de métodos sofisticados de renderización.
Para concluir, la informática gráfica ha transformado la manera en que interpretamos y gestionamos la información visual en el universo digital. Mediante avances como el algoritmo de Warnock, se han creado técnicas más eficaces para la ilustración de gráficos, abriendo la vía para tecnologías en auge en inteligencia artificial, simulaciones y visualización de datos. Su influencia continuará creciendo conforme progresen las habilidades computacionales, fortaleciendo su función como una de las áreas más dinámicas e impactantes en la computación contemporánea.
Video refuerzo
Créditos
Autor: William Orlando Pinzón Castañeda
Editor: Magister Carlos Ivan Pinzón Romero
Código: UCCGG1-10
Universidad: Universidad Central
Fuentes
El Espectador. (2023). Falleció John Warnock, empresario y cofundador de Adobe. https://www.elespectador.com/economia/fallecio-john-warnock-empresario-y-cofundador-de-adobe/
Eveleens, M., & Goya, S. I. (1998). Cálculo de reflexiones, refracciones y sombras (Doctoral dissertation, Universidad Nacional de La Plata).
Jaavargasar. (2018). Workshop. https://jaavargasar.github.io/workshop.html
Lerner, Evan (21 de agosto de 2023)."Remembering John Warnock" (Recordando a John Warnock).Facultad de Ingeniería John y Marcia Price de la Universidad de Utah. Consultado el 22 de agosto de 2023.
Roselló Balanyà, C., & Peña Marí, R. (1987). Algoritmo paralelo para la eliminación de superficies ocultas. In CIL 87: Convenció Informàtica Llatina (pp. 721-739). Marcombo.
Sutori. (2022). La computación gráfica en la era tecnológica siglo XXI. https://www.sutori.com/en/story/la-computacion-grafica-en-la-era-tecnologica-siglo-xxi--Hc4YdqtCVMv3q6hWz3kANdQw
Wikipedia. (2008). Archivo: Warnock1.svg. Wikipedia, la enciclopedia libre. https://es.m.wikipedia.org/wiki/Archivo:Warnock1.svg
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.
WIT Solapur - Professional Learning Community. (2020, 10 noviembre). Warnock Algorithm [Vídeo]. YouTube. https://www.youtube.com/watch?v=pm5oLvNm-WQ