grupo de informática gráfica avanzada universidad de...
TRANSCRIPT
Grupo de Informática Gráfica AvanzadaUniversidad de Zaragoza
Polígonos
Diego Gutiérrez
Diego Gutiérrez
Indice
DefiniciónRepresentaciónTriangulación (Gouraud, Phong)Modelado poligonal
Diego Gutiérrez
Con lo que habíamos visto hastaahora...
Diego Gutiérrez
Diego Gutiérrez
Definición
La mayoría de renderizadores trabajan sobre polígonosLa mayoría de los objetos se representan como polígonosLa mayoría de los algoritmos están pensados para polígonosLos aceleradores gráficos trabajan sobre polígonos
Diego Gutiérrez
Definición
¿Qué es un polígono? Un polígono es una región 2D de un plano limitada por segmentos de línea llamados ladosLados adyacentes no pueden ser colinealesUn vértice es el punto de los límites del polígono donde dos ladosintersectanDos lados pueden intersectar sólo en un vérticeUn polígono simple es uno sin agujeros
Diego Gutiérrez
Definición
Teorema de Jordan: un polígono divide el plano en una zona interior, una exterior y un límite
El polígono abarca la interior y el límite
Diego Gutiérrez
Definición
Otra propiedad interesante: convexidad
Convex hull: mínima área convexa que contiene todos los puntos de un conjunto
Diego Gutiérrez
Representación
Diego Gutiérrez
Representación
¿Cómo los representamos?
Esquema 1:Para cada polígono, construir el conjunto de vértices en orden arbitrarioRepresentar cada vértice con un par de números reales (coordenadasdefinidas respecto a un sistema de referencia común)Construir una lista con esas parejas de reales
Sintácticamente correcto. Semánticamente?
Diego Gutiérrez
Representación
Sintácticamente correcto. Semánticamente?
El esquema anterior es ambiguo o incompleto
Diego Gutiérrez
Representación
Esquema 2: restringir el esquema anterior a polígonos convexosEl convex hull de un polígono es único: esquema no ambiguo
Problema: hay puntos que no se definen como vértices, por lo que quedan fuera de nuestra representación
El esquema 2 es inválido
Diego Gutiérrez
Representación
Esquema 3: redefinimos las reglasVértices listados en orden consecutivo, siguiendo los lados del polígono
Diego Gutiérrez
Representación
Más esquemas?
Diego Gutiérrez
Representación
Más esquemas?
Sólo para polígonos convexos
Diego Gutiérrez
Representación
En resumen. Necesitamos:Un dominio. Qué objetos son representables?Validez. Puedo al menos representar un objeto?No ambigüedad. La representación corresponde a un único objeto?
Es también conveniente:Unicidad. Puede un objeto ser representado de varias formas?Concisión. Es le representación muy farragosa?Adaptabilidad a las aplicaciones. Para qué hago la representación?
Diego Gutiérrez
Representación
A veces el problema se simplifica mediante primitivas
Diego Gutiérrez
Representación
Baja resolución vs. Alta resolución
Diego Gutiérrez
Representación
Baja resolución vs. Alta resolución
Diego Gutiérrez
Triangularización
Diego Gutiérrez
Triangulación
¿Qué polígono sería más interesante?
Diego Gutiérrez
Triangulación
El triángulo es el más sencillo: menor representación, todos susvértices se conectan, siempre convexoAlgoritmos de sombreado basados en scanline, para determinar la intensidad de un punto P interior
Diego Gutiérrez
Sombreado de polígonos
¿Puede verse un modelo con apariencia suave si lo hacemos a partir de polígonos?
Diego Gutiérrez
Sombreado de polígonos
Los modelos de iluminación en IG calculan la intensidad de la luzen un punto aislado de la superficie¿Cómo lo calculamos para todo el polígono?
Diferentes enfoques:Repetimos el cálculo para todos los puntos del polígono (innecesario, poco práctico, nada inteligente)Flat shading: calculamos en un punto del polígono (generalmente el centroide) y con el valor obtenido pintamos todo el polígonoGouraud y Phong: calculamos en puntos clave del polígono (vértices) e interpolamos
Diego Gutiérrez
Flat shading (sombreado constante)
En inglés, a.k.a constant shadingEl método más rápido y sencillo
El método menos realistaNo pain, no gain
Diego Gutiérrez
Flat shading (sombreado constante)
En realidad, para fuentes puntuales, la dirección de la fuente de luz no es constantesobre todo el polígonoPara reflejos especulares, la dirección del ojotampocoEsto hace que la estructura poligonal interna se haga evidentePodemos refinar más la malla para disimularla un poco
Diego Gutiérrez
Mach banding
Además, aparece el problema del Mach bandingEl sistema visual es muy bueno detectando aristas... aunque éstas no existan!Discontinuidades C1Esto hace que las diferencias de sombreado entre polígonos parezcantodavía mayoresY aunque usáramos el horriblemente ineficiente método de calcular en cada punto del polígono, el resultado sería pobre
Diego Gutiérrez
Mach banding
Diego Gutiérrez
Sombreado de Gouraud
Gouraud shading se basa en interpolar las intensidades obtenidasen cada vérticePrimero calculamos esa intensidad en A,B,C
Necesitamos calcular la normal en cada vérticeLa aproximamos promediando la normal a la superficie en los polígonos que comparten ese vértice
Diego Gutiérrez
Sombreado de Gouraud
Equivale a hallar la normal a la superficie real que aproximan los polígonos, asumiendo que éstos son una aproximación piecewise de la superficie real (C0)Las normales proporcionan información sobre el plano tangente a la superficie en cada punto (C1)Las normales en los vértices se usan sólo para iluminación (no backfaceculling u otros cálculos geométricos)
Diego Gutiérrez
Sombreado de Gouraud
Luego calculamos la intensidad en Q y R (intersección del scan-line con el polígono)Y luego interpolamos entre IQ e IR para obtener Ip
Diego Gutiérrez
Sombreado de Gouraud
Las discontinuidades entre polígonos adyacentes desaparecen (la intensidad “al final de un polígono” a la que llegamos interpolandoserá la intensidad “al comienzo del polígono siguiente”
Diego Gutiérrez
Sombreado de Gouraud
Problemas de Gouraud:Las aristas tienden a desaparecerLos reflejos especulares pueden perderse si caen dentro de un solo polígonoComo hemos visto, las bandas de Mach no se eliminan del todo
Para “recuperar” una arista que queremos que sea visible, calculamos dos normales al vértice, una para cada lado. Cada normal se halla promediando las normales a la superficie de los polígonos del lado correspondiente
Diego Gutiérrez
Sombreado de Phong
No confundir con el modelo de iluminación de PhongInterpolamos linealmente las normales de la superficie a lo largo del polígono (no las intensidades como Gouraud)Aparte de eso, el concepto es similar:
Diego Gutiérrez
Sombreado de Phong
Una vez interpoladas las normales, se aplica el modelo de iluminación con la normal interpolada, para hallar la intesidad de luz en el punto requerido
Apariencia más real. Los reflejos especulares se capturan mejor. Las bandas de Mach se reducenRequiere más cálculos (un cálculo de iluminación completo por cada interpolación)
Diego Gutiérrez
Triangulación
La clave, entonces, parece ser reducir los polígonos a triángulos
Diego Gutiérrez
Triangulación
Diego Gutiérrez
Triangulación
Wikipedia: In computational geometry, polygon triangulation isthe decomposition of a polygon into a set of triangles.A triangulation of a polygon P is its partition into non-overlappingtriangles whose union is P. In the strictest sense, these trianglesmay have vertices only at the vertices of P. In a less strict sense, points can be added anywhere on or inside the polygon to serveas vertices of triangles.
Reduce formas complejas a formas simples. Es el primer paso en muchos algoritmos más complejos
Robótica, situación 3D de puntos, generación de mallas...
Diego Gutiérrez
Triangulación
Todo polígono es triangularizableLa triangularización de un polígono de n-lados da como resultadon-2 triángulosEjemplo: 13 lados, 11 triángulos
Diego Gutiérrez
Triangulación
El problema de la galería de arte:
?
Diego Gutiérrez
Triangulación
El problema de la galería de arte:Cada guardia está fijo en un sitioTiene visión de 360ºNo ve a través de las paredes
Problema planteado en 1973, y resuelto ese mismo año mediantecomplejas formulacionesDesde entonces, se han propuestosoluciones mucho más sencillasbasadas en triangulación
Diego Gutiérrez
Triangulación
Teorema final: un polígono de n-lados puede ser “vigilado” con n/3 guardias en los vértices
Diego Gutiérrez
Triangulación
Primeros algoritmos: O(n4)En seguida reducidos a O(n2)Primer algoritmo no-trivial O(nlog n): 19781991: Chazelle publica un algoritmo O(n) extremadamentecomplejoActualmente se suele trabajar con O(nlog n)
Diego Gutiérrez
Triangulación
Algoritmo:Barrer el plano con una scanlineEn cada vértice, trazar una línea vertical (horizontal) hasta chocarcon un lado del polígono
El resultado es una serie de trapezoides, que son trivialmentedescompuestos en triángulosO(nlog n)
Diego Gutiérrez
Modelado poligonal
Ahora que ya tenemos un montón de polígonos (triángulos), cómo trabajamos con ellos?
Diego Gutiérrez
Modelado poligonal
Ahora que ya tenemos un montón de polígonos (triángulos), cómo trabajamos con ellos?
Diego Gutiérrez
Modelado poligonal
Diego Gutiérrez
Modelado poligonal
Diego Gutiérrez
Modelado poligonal
Diego Gutiérrez
Modelado poligonal
Diego Gutiérrez
Modelado poligonal
Diego Gutiérrez
Modelado poligonal
Diego Gutiérrez
Modelado poligonal
Diego Gutiérrez
Modelado poligonal
Diego Gutiérrez
Modelado poligonal
Diego Gutiérrez
Modelado poligonal
Cubic tragedy: http://www.youtube.com/watch?v=-fBcjHq9rv0SIGGRAPH 2005, Electronic Theater