4.1 Relleno de poligonos

El polígono es una figura básica dentro de las representaciones y tratamiento de imágenes bidimensionales y su utilización es muy interesante para modelar objetos del mundo real.

En un sentido amplio, se define como una región del espacio delimitada por un conjunto de líneas (aristas) y cuyo interior puede estar rellenado por un color o patrón dado.

El caso más sencillo de relleno es el triángulo.

Luego sigue el relleno de polígonos convexos de N-lados.

Relleno de polígonos cóncavos.

MÉTODO DE RELLENO DE POLÍGONOS CON COLOR

SCAN-LINE

También llamado scan conversion algorithm, fila a fila van trazando líneas de color entre aristas.

Para scan-line el cruce del polígono se busca en la intersección entre las líneas de barrido y las aristas del polígono.

Dichas intersecciones se ordenan y se rellenan a pares.

Consiste en detectar la intersección de los scanlines del dispositivo con los bordes de la primitiva, y por cada scanline rellena el span de pixeles entre cada par de intersecciones.

Cuando el polígono no es convexo, solo hay dos intersecciones por scanline, en cualquier dirección.

en el procedimiento, primero encuentra las intersecciones en alguna estructura de datos ET(edge table), de forma ordenada, ascendentemente en "y" y en "x", en buckets y rellena los spans utilizando la estructura:

utiliza algún criterio de paridad para saber cuándo un intervalo debe ser rellenado o no.

ejemplo: (x2,x3) debe ser rellenado; (x3,x4)no; (x4,x5)si debe ser rellenado.

INUNDACIÓN

También conocido como Flood-fil algorithm (FFA) o algoritmo de relleno por inundación.

Se comienza desde un píxel dentro del polígono, al cual se le asigna el color de relleno, el color se propaga desde esta hacia sus pixeles vecinos, y de estos a sus vecinos y así sucesivamente, simulando una inundación dentro del polígono.

La propagación continúa hasta encontrar los pixeles del borde, o simplemente encontrar pixeles de un color diferente al color de la semilla inicial.

se pueden usar dos patrones distintos para hacer la propagación:

Este algoritmo es inherentemente recursivo.

• Empieza en un interior y pinta hasta encontrar la frontera del objeto.
• Partimos de un punto inicial (x,y), un color de relleno y un color de frontera.
• El algoritmo va testeando los píxeles vecinos a los ya pintados, viendo si son frontera o no.
• No solo sirven para polígonos, sino para cualquier área curva para cualquier imagen AE se usan los programas de dibujo.

LINEA DE BARRIDO

Es válido para polígonos cóncavos como convexos. Incluso para si el objeto tiene huecos interiores.

Funcionan en el trozo de líneas horizontales, denominadas líneas de barridos, que intersectan un número de veces, permitiendo a partir de ella identificar los puntos que se consideran interiores al polígono.

FUERZA BRUTA

• Calcula una caja contenedora del objeto.
• Hace un barrido interno de la caja para comprobar c/pixel este dentro del polígono.
• Con polígonos simétricos basta con que hagamos un solo barrido en una sección y replicar los demás pixeles.
• Requiere aritmética punto-flotante, esto lo hace preciso y costoso.

RELLENO MEDIANTE UN PATRÓN

Un patrón viene definido por el área rectangular en el que cada punto tiene determinado color o novel de gris. Este patrón debe repetirse de modo periódico dentro de la región a rellenar. Para ello debemos establecer una relación entre los puntos del patrón y los pixeles de la figura. En definitiva debemos determinar la situación inicial del patrón respecto a la figura de tal forma que podamos establecer una correspondencia entre los pixeles interiores al polígono y los puntos del patrón.

ALTERNATIVAS PARA LA SITUACIÓN INICIAL DEL PATRÓN

Consiste en situar el punto asociado a la esquina superior izquierda del patrón en un vértice del polígono.

Considerar la región a rellenar en toda la pantalla y por lo tanto el patrón se citua en el origen de esta (esquina superior izquierda).

Conclusiones:

Los métodos de relleno de polígonos son muy útiles, para dar color a nuestras figuras, existen diferentes métodos y cada uno con un propósito especifico que nos ayudan es nuestras tareas, pero no todos funcionan de la misma manera por lo cual no todos nos sirven para colorear el mismo tipo de figuras ni con la misma precisión, es importante conocerlos para saber cuál elegir al querer darle color a alguna de nuestras imágenes, o en el caso de utilizar un software especializado con el cual ya no tengamos que preocuparnos más que por escoger el color, almenas saber cómo es que funciona internamente y todo el proceso necesario para poder colorear una figura.

Referencias:

• http://ccg.ciens.ucv.ve/~esmitt/cgI/II-2010/RellenoPoligonos.pdf
• http://graficacionporcomputadora.blogspot.mx/2013/05/41-relleno-de-poligonos.html