{"id":59894,"date":"2025-02-14T13:39:51","date_gmt":"2025-02-14T18:39:51","guid":{"rendered":"https:\/\/niixer.com\/?p=59894"},"modified":"2025-02-16T19:43:36","modified_gmt":"2025-02-17T00:43:36","slug":"warnock-el-algoritmo-de-jhon-warnock","status":"publish","type":"post","link":"https:\/\/niixer.com\/index.php\/2025\/02\/14\/warnock-el-algoritmo-de-jhon-warnock\/","title":{"rendered":"WARNOCK, EL ALGORITMO DE JHON WARNOCK"},"content":{"rendered":"\n
\"\"<\/figure>\n\n\n\n

Computaci\u00f3n gr\u00e1fica<\/strong><\/h3>\n\n\n\n

Es el campo de la inform\u00e1tica visual, donde se utilizan computadoras para generar im\u00e1genes visuales y espaciales del mundo real. Tambi\u00e9n podemos definirlo como el arte de transmitir informaci\u00f3n usando im\u00e1genes que son generadas mediante la computaci\u00f3n, la computaci\u00f3n gr\u00e1fica nace en 1955 con SAGE<\/a>, una m\u00e1quina creada durante la Guerra Fr\u00eda por el ej\u00e9rcito de Estados Unidos para poder ubicar las naves a\u00e9reas que entraban al territorio norteamericano, desarrollada para convertir los sonidos de detecci\u00f3n de un radar en im\u00e1genes, fue el primero en emplear un l\u00e1piz \u00f3ptico para seleccionar s\u00edmbolos en la pantalla, Jhon Edward Warnock es uno de los aportadores m\u00e1s resaltantes en este campo.<\/p>\n\n\n\n

John Edward Warnock <\/strong><\/h3>\n\n\n\n
\"Jhon<\/figure>\n\n\n\n

Fue un\u00a0cient\u00edfico inform\u00e1tico<\/a>,\u00a0inventor<\/a>, empresario tecnol\u00f3gico y\u00a0fil\u00e1ntropo<\/a>\u00a0estadounidense, mejor conocido por cofundar\u00a0Adobe Systems Inc.<\/a>, empresa de software gr\u00e1fico y editorial, con\u00a0Charles Geschke<\/a>\u00a0en 1982. Warnock fue pionero en el desarrollo de tecnolog\u00edas gr\u00e1ficas, editoriales, web y de documentos electr\u00f3nicos que han revolucionado el campo de la publicaci\u00f3n y las comunicaciones visuales.<\/p>\n\n\n\n

En su tesis doctoral de 1969, Warnock invent\u00f3 el algoritmo Warnock<\/a> para la determinaci\u00f3n de superficies ocultas<\/a> en gr\u00e1ficos por computadora<\/a>. Funciona mediante la subdivisi\u00f3n recursiva<\/a> de una escena hasta obtener \u00e1reas 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<\/a>, se renderiza; de lo contrario, se divide en partes m\u00e1s peque\u00f1as y se repite el proceso. Warnock se\u00f1al\u00f3 que por este trabajo recibi\u00f3 “la dudosa distinci\u00f3n de haber escrito la tesis doctoral m\u00e1s corta en la historia de la Universidad de Utah<\/a>“.<\/p>\n\n\n\n

El algoritmo de Warnock<\/strong><\/h3>\n\n\n\n
\"Figuras<\/figure>\n\n\n\n

Generalmente utilizado en computaci\u00f3n gr\u00e1fica<\/a>, como soluci\u00f3n al problema de visualizaci\u00f3n de im\u00e1genes complicadas por subdivisi\u00f3n recursiva de una escena hasta que las \u00e1reas obtenidas sean f\u00e1cilmente calculables. En otras palabras, hasta que la escena sea tan sencilla que permita calcular eficientemente su visualizaci\u00f3n. <\/p>\n\n\n\n

Este es un algoritmo divide y vencer\u00e1s<\/a> de orden O(np) siendo n el n\u00famero de pol\u00edgonos y p el n\u00famero de p\u00edxeles en el \u00e1rea de dibujo. Las entradas son una lista de pol\u00edgonos y un \u00e1rea de dibujo. <\/p>\n\n\n\n

El mejor caso se presenta cuando la lista de pol\u00edgonos es sencilla, entonces se puede dibujar los pol\u00edgonos en el \u00e1rea de dibujo. Por sencillo se entiende que el pol\u00edgono mida un p\u00edxel en cuyo caso el pol\u00edgono o su parte se dibuja en la correspondiente parte del \u00e1rea de dibujo o que el \u00e1rea de dibujo mida un pixel, en cuyo caso el p\u00edxel toma el color del pol\u00edgono m\u00e1s cercano al observador. El paso recurrente consiste en dividir el \u00e1rea de dibujo en cuatro cuadrantes de igual tama\u00f1o y llamar al algoritmo para cada cuadrante con la lista de pol\u00edgonos modificada tal que s\u00f3lo contenga pol\u00edgonos visibles en el cuadrante.<\/p>\n\n\n\n

Como se puede ver en la figura, en el primer caso nuestro marco de subdivisi\u00f3n debe contener completamente al objeto, en el caso 2 la intersecci\u00f3n se ve cuando contiene parte del objeto, en el caso tres el marco no contiene absolutamente nada y en el \u00faltimo escenario el marco se encuentra completamente dentro del objeto o pol\u00edgono.<\/p>\n\n\n\n

Uso del algoritmo<\/strong><\/h3>\n\n\n\n

El algoritmo de warnock es una de las soluciones que se encuentran en el enfoque de \u201cvisibilidad\u201d y su resultado que son rect\u00e1ngulos(bloques) de p\u00edxeles, se encarga de dar una mejor visibilidad por cada respectivo cuadrante que lleg\u00f3 a subdividirse, a su vez este se considera que tiene precisi\u00f3n de imagen, dado a que se calcula el pol\u00edgono visible en cada bloque. <\/p>\n\n\n\n

Para usar este algoritmo <\/a>inicialmente necesitamos dos par\u00e1metros, una lista de pol\u00edgonos y la vista inicial que comprende todos los pol\u00edgonos que se pueden encontrar en el \u201ccanvas\u201d. Despu\u00e9s de haber recibido los par\u00e1metros el algoritmo mira si es posible darle soluci\u00f3n al marco de vista que se est\u00e1 enfocando actualmente dado a los casos base, si es as\u00ed entonces este pintara en pantalla los p\u00edxeles de la imagen, en caso contrario se dividir\u00e1 el rect\u00e1ngulo actual en cuatro partes y cada una de ellas se le aplica el algoritmo warnock de nuevo, de manera recursiva. <\/p>\n\n\n\n

El algoritmo warnock hace parte de los algoritmos de \u201cHidden Surface Removal (HSR) \u201c , son los algoritmos que nos permite conocer qu\u00e9 vistas y superficies son visibles de una imagen llena de pol\u00edgonos, sin importar la manera en que estos est\u00e9n superpuestos o cruzados unos a otros. Este algoritmo es de complejidad O(np), siendo n el n\u00famero de pol\u00edgonos que encontramos en su lista y p el n\u00famero de p\u00edxeles del canvas principal o conocido como el \u201cviewport\u201d. Cabe resaltar que en el peor de los casos el algoritmo tendr\u00e1 que dividir el viewport hasta llegar a un \u00e1rea del tama\u00f1o de un pixel.<\/p>\n\n\n\n

Conociendo el algoritmo<\/strong><\/h3>\n\n\n\n

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:<\/p>\n\n\n\n

    \n
  1. Encontramos que en el \u00e1rea actual, todos los pol\u00edgonos son disjuntos, esto es que el \u00e1rea se encuentra vac\u00eda y ning\u00fan pol\u00edgono de la lista se puede notar dentro de ella<\/li>\n<\/ol>\n\n\n\n
    \"Fase<\/figure>\n\n\n\n

    2. Solo existe un pol\u00edgono contenido dentro del marco en su totalidad o en una parte, ya sea que este sea intersecci\u00f3n con el marco<\/p>\n\n\n\n

    \"Fase<\/figure>\n\n\n\n

    3. Hay un solo pol\u00edgono que se encuentra completamente en el \u00e1rea y es circundante, esto es que la ocupa en su totalidad.<\/p>\n\n\n\n

    \"Fase<\/figure>\n\n\n\n

    4. Hay varios pol\u00edgonos intersectados, solo que unos est\u00e1n encima de otros, en este caso se mira el eje z y los cuatro v\u00e9rtices que forman el marco y al cual se le quiere dar visibilidad, en este caso se subdivide el \u00e1rea.<\/p>\n\n\n\n

    \"Expansion<\/figure>\n\n\n\n
    \"\"<\/figure>\n\n\n\n

    Expandiendo el algoritmo<\/strong><\/h3>\n\n\n\n

    El algoritmo no es \u00fanico, sino que existe una colecci\u00f3n de ellos. De hecho, hay un algoritmo para cada interpretaci\u00f3n de “ventana simple” y para cada m\u00e9todo de subdivisi\u00f3n de ventanas, sean simples o no.<\/p>\n\n\n\n

    Para definir un criterio que determine el significado de “ventana simple”, es necesario considerar las posibles posiciones de un pol\u00edgono con respecto a una ventana. En general, los pol\u00edgonos se pueden clasificar en tres tipos:<\/p>\n\n\n\n