PDF de programación - Graficación

UMSNH

Facultad de Ing. Eléctrica

Carrera: Ingeniería en Computación

Materia: Graficación

Dr. José Antonio Camarena Ibarrola

Septiembre de 2010

Introducción

Aplicaciones: Simulación

Introducción

• Video-juegos

http://www.acclaim.com/games/crazytaxi/

Introducción

• Animación por computadora

http://www.pixar.com

Introducción

• Diseño (recorridos virtuales 3D)

The William gates Building
http://www3.arct.cam.ac.uk/westC/cl/cl.html

Introducción

• Visualización de gráficas 3D

Convective modelling
group, AOS, Univ
Illinois at Urbana-
Champaign
http://redrock.ncsa.uiu
c.edu/AOS/home.html
(NCSA storm model)

Introducción

• Interfaces en la medicina

The Sonic Flashlight, MRT Center, The
Robotics Institute,
Carnegie Mellon University,
http://www.ri.cmu.edu/projects/proj
ect_438.html

Primitivas de Gráficación

• Algoritmos de trazado de líneas. Algoritmo DDA

(Digital Diferential Analizer), Algoritmo de Bresenham.

• Algoritmo de Bresenham para trazado de

circunferencias, Algoritmo del punto medio para
trazado de circunferencias

• Algoritmo del punto medio para generación de elipses
• Polilíneas
• Curvas Splines cúbicas naturales, Splines de Hermite,

Curvas de Bezier.

• Estructura de un Programa OpenGL
• Despliege de lineas, triángulos, cuadrados,

circunferencias, etc mediante OpenGL

Primitivas de Graficación

Trazado de líneas

Algoritmo DDA (Digital Diferential Analizer)

Primitivas de Graficación

Trazado de líneas

Algoritmo de Bresenham

Con el signo de d1-d2 podemos decidir cual pixel
Está mas cerca de la línea ideal

Primitivas de Graficación

Trazado de líneas

Algoritmo de Bresenham

Problema: Requiere modificarse para evitar aritmética de flotantes

Primitivas de Graficación

Trazado de líneas

Algoritmo de Bresenham

Esta versión usa solo aritmética entera

Primitivas de Graficación
Trazado de circunferencias
Algoritmo de Bresenham

• La idea básica es usar solo el signo del error en que se incurre

para decidir cual pixel encender

y=r;
d= -r;
pixel(0,r);
for(x=1;x<r/sqrt(2);x++) {

d+= 2x-1;
if (d>=0) {

y--;
d -= 2y;

}
pixel(x,y);

}

Primitivas de Graficación
Trazado de circunferencias
Algoritmo del punto medio

Primitivas de Graficación

Algoritmo del punto medio para trazado de elipses

-Usamos la ecuación de la elipse para
decidir si el punto medio está dentro
o fuera de la elipse

-Como no tenemos simetría a nivel
octante, tenemos que generar todo un
cuadrante

Primitivas de Graficación

Polilíneas

Abierta

Autointersectada

Cerrada

Primitivas de Graficación

Splines

De interpolación

De aproximación

Primitivas de Graficación

Splines

(a) Continuidad de orden cero. (b) de primer orden c) de segundo orden

Primitivas de Graficación

Curvas Splines cúbicas naturales

Cada segmento se representa por un polinomio de tercer grado (cúbico)

Por cada polinomio cúbico hay 4 incógnitas

Hay que resolver un sistema de 4n ecuaciones con 4n incógnitas

Si un punto de control se modifica hay que volver a solucionar el sistema de ecuaciones

En estas splines no hay control local

Tienen continuidad de segundo orden

Primitivas de Graficación

Splines de Hermite

Tienen continuidad de primer orden

Permiten control local

Restricciones

Por cada segmento hay que resolver un sistema de 4x4

Primitivas de Graficación

Splines de Hermite

Como la matriz de
coeficientes no cambia
en realidad solo se requiere
de una simple multiplicación
matricial por cada segmento

Primitivas de Graficación

Reagrupando:

Splines de Hermite

Funciones de ponderación

Primitivas de Graficación

Splines cardinales

Problema: las Splines de Hermite requieren que el usuario especifique la pendiente
En cada punto de control

Solución: Estimar las pendientes usando las formulas

Donde t es el parámetro de tensión

t<0

t>0

Primitivas de Graficación

Curvas de Bezier

Pierre Bézier trabajaba para la Renault diseñando carrocerías

Donde:

Primitivas de Graficación

Curvas de Bézier

Por ejemplo, para n=4 (número de puntos de control)

Primitivas de Graficación

Estructura de un programa en OpenGL

Primitivas de Graficación

Despliegue de líneas, triángulos y cuadrados en

OpenGL

Despliega dos líneas

Despliega polilínea

Primitivas de Graficación

Despliegue de líneas, triángulos y cuadrados en

OpenGL

Despliega polilínea cerrada

Despliega dos triángulos

Primitivas de Graficación

Despliegue de líneas, triángulos y cuadrados en

OpenGL

Despliega polígono

Algoritmos de relleno de áreas

• Relleno mediante ordenamiento de aristas
• Relleno mediante complementación
• Relleno mediante complementación usando

una cerca

• Algoritmo simple de siembra de semilla
• Siembra de semilla por línea de rastreo
• Funciones de OpenGL para manejo del color

de las figuras y del fondo

Algoritmos de relleno de áreas

Relleno mediante ordenamiento de aristas

-Procesar por cada línea de rastreo
-ordenar aristas respecto a y y luego respecto a x
-Rellenar de la primera arista a la segunda, luego de la tercera a la cuarta
, etc

Algoritmos de relleno de áreas

Relleno mediante ordenamiento de aristas

Mantener la lista de aristas ordenada en lugar de ordenarla al final

Algoritmos de relleno de áreas

Relleno mediante ordenamiento de aristas

Eliminar duplicados correspondientes a los vértices que no son
Máximos ni mínimos (Ej vértice 4 y 12)

Algoritmos de relleno de áreas

Relleno mediante complementación

En este ejemplo se procesaron las aristas en el sig. orden: d,b,e,c,a
Cualquier orden funciona
No se procesan las aristas horizontales

Algoritmos de relleno de áreas

Relleno mediante complementación

Modificación usando una cerca

En este ejemplo se procesaron las aristas en el sig. orden: d,b,e,c,a
Cualquier orden funciona
No se procesan las aristas horizontales

Algoritmos de relleno de áreas

Algoritmo simple de siembra de semilla

Conectividad 4

Conectividad 8

Algoritmos de relleno de áreas

Algoritmo simple de siembra de semilla

Se detiene porque se a
sumió conectividad 4

Semilla inicial

Algoritmos de relleno de áreas

Algoritmo simple de siembra de semilla

Algoritmos de relleno de áreas

Algoritmo de siembra de semilla por línea de rastreo

Algoritmos de relleno de área

Funciones de OpenGL para manejo del color de las

figuras y del fondo

• void glColor3f( GLfoat red, GLfoat green, GLfoat blue)
• Una vez ejecutada esta instrucción las figuras que se

dibujen tendrán este color

• void glColor4f( GLfoat red, GLfoat green, GLfoat blue,

GLfoat alpha)

• Igual que la anterior pero tiene un parametro de

transparencia

• void glClearColor3f( GLfoat red, GLfoat green, GLfoat

blue)

• Para especificar el color del fondo

Algoritmos de recorte

• Códigos de región para determinar la

visibilidad de líneas

• Algoritmo de recorte explícito en 2D
• Algoritmo de Sutherland-Cohen
• Algoritmo de la subdivisión del punto medio
• Algoritmo de Cyrus-Beck para recorte de

regiones convexas

El concepto de recorte

Antes del recorte

Después del recorte

Algoritmos de recorte
Códigos de Región para

determinar la visibilidad de líneas

0101

0110

Bit 0 Izquierda
Bit 1 Derecha
Bit 2 Arriba
Bit 3 Abajo

1001

1010

Algoritmos de recorte
Códigos de Región para

determinar la visibilidad de líneas

Algoritmos de recorte

Algoritmo de recorte explícito en 2D

Deduciendo la ec de la
recta que va de
(x1,y2) a (x2,y2)

Algoritmos de recorte

Algoritmo de recorte explícito en 2D

De manera Similar

Algoritmos de recorte

Algoritmo de recorte explícito en 2D

La intersección con el extremo superior ocurre en:

Algoritmos de recorte

Algoritmo de recorte explícito en 2D.

Ejemplo

Recorte la línea que va de
(-3/2,1/6) a (1/2,3/2)

Algoritmos de recorte

Algoritmo de recorte explícito en 2D. Ejemplo

Algoritmos de recorte

Algoritmo de recorte explícito en 2D. Ejemplo

Algoritmos de recorte

Algoritmo de Sutherland-Cohen

Algoritmos de recorte

Algoritmo de la subdivisión del punto medio

Ideal para
implementar
en hardware

Algoritmos de recorte

Algoritmo de Cyrus-Beck para recorte de

regiones convexas

El Algoritmo de Cyrus-Beck hace uso del hecho de que un punto a está dentro
de un área de recorte convexa respecto a cierta área que define un borde si se
cumple la desigualdad:

donde n es un vector normal a la línea que define el borde y b es cualquier
punto en ese borde

El Algoritmo de Cyrus-Beck hace uso de la ecuación paramétrica de una
línea recta que va de P1 a P2

Algoritmos de recorte

Algoritmo de Cyrus-Beck para recorte de

regiones convexas

podemos obtener el valor de t para el cual la línea coincide con la frontera
del área de recorte despejándolo de:

Donde f es cualquiér punto de esa frontera

Algoritmos de recorte

Algoritmo de Cyrus-Beck para recorte de

regiones convexas. Ejemplo

Recortar la línea que
va de (-1,1) a (3,3)

Algoritmos de recorte

Algoritmo de Cyrus-Beck para recorte de

regiones convexas. Ejemplo

La directríz es:

Para la arista V5V6 la normal es:

Algoritmos de recorte

Algoritmo de Cyrus-Beck para recorte de

regiones convexas. Ejemplo

Algoritmos de recorte

Algoritmo de Cyrus-Beck para recorte de regiones

convexas. Ejemplo

Repitiendo para el
Resto de las aristas
Completamos la tabla

Para terminar el ejemplo solo resta decir que la línea recortada comienza
en t = 1=4 y termina en t = 5=6, lo cual corresponde a una nueva línea que
va de (0,3/2) a (7/3,8/3)

Pipeline de visualización bidimensional

• Coordenadas locales
• Coordenadas mundiales
• Puerto de visión
• Funciones OpenGL para visualización 2D

Pipeline de visualización bidimensional

Coordenadas locales

• También se llaman “coordenadas de modelado”
• Una figura se define en coordenadas relativas a un

punto de la misma figura, por ejemplo el centro de la
misma

• Por ejemplo los vértices de un rectángulo pudieran

establecerse relativos a la esquina inferior e izquierda
del mismo

Pipeline de visualización