PDF de programación - Visualización - Parte 3

Visualización
Visualización

- Parte 3 -

Dpto. de Informática
Fac. Cs. Físico-Mat. y Nat.
Universidad Nacional De San Luis
Argentina

Visualización – Parte 3
Visualización – Parte 3

Computación Gráfica
Computación Gráfica

 Según Fetter, CG referencia a la creación, almacenamiento y manipulación

de modelos de objetos e imágenes.

 Simular un mundo 3D por medio de fórmulas matemáticas que describan la

forma y el aspecto de los objetos.
 Los modelos deben ser susceptibles de ser manipulados de forma efectiva por un

computador

 Tres grandes aspectos a considerar:

- Modelado de las Formas
- Modelado de la Apariencia
- Visualización



Rio 14

- Roberto Guerrero @ 2014

2

Visualización – Parte 3
Visualización – Parte 3

Rendering - Generación de la Imagen



Es el proceso por medio del cual se obtiene una representación estática 2D de un mundo
abstracto 3D.

Muestreo

Imagen
Abstracta
3D

Modelo de
Imagen

Procesa-
miento

Frame
Buffer
2D

 Una imagen abstracta se encuentra definida y existe dentro del procesador como una imagen









continua.
La imagen resultante, en el Frame Buffer es una imagen discreta.
El muestreo es el proceso por el cual se convierte una imagen continua en discreta.
El hardware de visualización de un sistema gráfico convierte los valores de intensidad
discretos en voltajes analógicos continuos aplicados a un dispositivo específico.



Rio 14

- Roberto Guerrero @ 2014

3

Visualización – Parte 3
Visualización – Parte 3

Convenciones acerca de los Pixels
De Organización:
 Una grilla regular de puntos 2D.





Los pixels son ubicaciones puntuales asociadas a valores de muestra de una señal continua
–imagen- (intensidad de luz, color, etc.)
La geometría visualizada de los pixels varía según el dispositivo que se utilice para
representarlo.

4

4



2

circular

2

rectangular

Rio 14

- Roberto Guerrero @ 2014

4

Visualización – Parte 3
Visualización – Parte 3

Convertir Líneas en Puntos

(scan convertion)

Problema
 Dados 2 puntos P y Q en el plano, ambos con coordenadas enteras, determinar que pixels
del dispositivo de visualización deben ser encendidos con el objeto de pintar un segmento
de línea del ancho de un pixel que comience en P y termine en Q.

P

Línea ideal

Aproximación discreta

Q

Dibujar una línea





Problemas con el enunciado
 No establece cuales deben ser los pixels a ser iluminados.
 No es claro el concepto de “dibujar”.
 Que se entiende por línea en un dispositivo raster?.
 Cómo se evalúa el éxito de algún algoritmo propuesto?.



Rio 14

- Roberto Guerrero @ 2014

5

Visualización – Parte 3
Visualización – Parte 3

Encontrar el pixel
Casos especiales:







Línea Horizontal:
Dibujar el pixel P e incrementar la coordenada x en un valor de 1 hasta alcanzar el pixel final Q.

Línea Vertical:
Dibujar el pixel P e incrementar la coordenada y en un valor de 1 hasta alcanzar el pixel final Q.

Línea Diagonal:
Dibujar el pixel P e incrementar ambas coordenadas x e y en un valor de 1 hasta alcanzar el valor
final Q.

¿Cómo sería el caso general?



Rio 14

- Roberto Guerrero @ 2014

6

Visualización – Parte 3
Visualización – Parte 3

Estrategia 1: Algoritmo Incremental (1/3)

El Algoritmo Básico

(y = mx + B)



Encontrar la ecuación de la línea que conecta los dos puntos P y Q.

 Comenzando por el punto de mas a la izquierda P,





incremenart xi en 1
calcular yi = mxi + B

donde m = pendiente =    (y1-y0) / (x1-x0), B = donde y es interceptada



Iluminar el pixel en (xi, Round(yi))
donde Round (yi) = Floor (yi + 0.5)



Rio 14

- Roberto Guerrero @ 2014

7

Visualización – Parte 3
Visualización – Parte 3

Código de Ejemplo

// Assumes –1 <= m <= 1, x0 < x1

void Line(int x0, int y0,

int x1, int y1, int value) {

int x;
float y;
float
float
float
y = y0;
for (x = x0; x < x1; x++) {

dy = y1 – y0;
dx = x1 – x0;
m = dy / dx;

WritePixel(x, Round(y), value);
y = m * x;



}

}

Rio 14

- Roberto Guerrero @ 2014

8

Visualización – Parte 3
Visualización – Parte 3

Estrategia 1: Algoritmo Incremental (2/3)

El Algoritmo Incremental:

 Cada interación requiere una operacion flotante



debe intentar eliminarse.



yi+1 = mxi+1 + B = m(xi + x) + B = (mxi + B) + m   x = yi + m    x
Δ

Δ

Δ

 Como x = 1, luego yi+1 = yi + m

Δ



En cada paso, para encontrar el valor del próximo y se realizan cálculos incrementales
basados en el paso anterior.



Rio 14

- Roberto Guerrero @ 2014

9

Visualización – Parte 3
Visualización – Parte 3

Código de Ejemplo

// Incremental Line Algorithm
// Digital Differential Analyzer DDA
// Assumes –1 <= m <= 1, x0 < x1

void Line(int x0, int y0,

int x1, int y1, int value) {

int x, y;
float
float
float

dy = y1 – y0;
dx = x1 – x0;
m = dy / dx;

y = y0;
for (x = x0; x < x1; x++) {
WritePixel(x, y, value);
y = Round(y + m);

}



}

Rio 14

- Roberto Guerrero @ 2014

10

Visualización – Parte 3
Visualización – Parte 3

Estrategia 1: Algoritmo Incremental (2/3)

(

i yx
,

i

)

+

(

x
i

,1

Round

(

+

my
i

))



(

x
i

,

Round

(

y

))

i

(

x
i

+

,1

+

my
i

)

Rio 14

- Roberto Guerrero @ 2014

11

Visualización – Parte 3
Visualización – Parte 3

Problema del Algoritmo Incremental





La operación de redondeo consume tiempo.
Las variables y y m deben ser reales o fraccionarias pues la pendiente es una fracción.


las líneas verticales se tratan como caso especial

 Dado que las variables tienen precisión limitada, la suma repetida de un m no correcto
introduce un error acumulativo en la reconstrucción. El problema se agrava con líneas
largas.



Puntos perdidos

Rio 14

- Roberto Guerrero @ 2014

12

Visualización – Parte 3
Visualización – Parte 3

Distancia Vertical



Se podría utilizar la distancia vertical para establecer que punto se encuentra más cercano?
 La distancia vertical es proporcional a la distancia actual

(x1, y1)

(x2, y2)







Por triángulos semejantes, para cada punto la distancia real a la línea (azul) es directamente
proporcional a la distancia vertical a la línea (negro).
Por consiguiente, el punto con menor distancia vertical a la línea se encuentra más cerca de
la línea.



Rio 14

- Roberto Guerrero @ 2014

13

Visualización – Parte 3
Visualización – Parte 3

Estrategia 2: Algoritmo del Punto Medio (1/3)

 Asuma que la línea tiene pendiente positiva suave.

(0 < pendiente < 1); variaciones de la misma pueden realizarse mediante simple reflexión
de los valores de las coordenadas.

 Denominemos al punto inferior izquierdo (x0, y0) y al superior derecho (x1, y1).
 Asuma que se ha seleccionado el pixel P en (xp, yp).



Se debe elegir el proximo pixel a pintar entre: el que se encuentra a la derecha (pixel E)
o el que se encuentra a la derecha y hacia arriba (pixel NE).

 Donde Q es el punto de intersección de la línea que se esta digitalizando con la línea de la

grilla en x = xp +1.

(x1, y1)

NE

Q

E



(x0, y0)

P

Rio 14

- Roberto Guerrero @ 2014

14

Visualización – Parte 3
Visualización – Parte 3

Estrategia 2: Algoritmo del Punto Medio (2/3)

y= y p1

NE pixel

Q

Punto medio M

P =



)

p

(

x

p y
,
Pixel previo

= px

E pixel
1+
x
Opciones para
el pixel actual

pixel

Opciones para

el próximo

Rio 14

- Roberto Guerrero @ 2014

15

Visualización – Parte 3
Visualización – Parte 3

Estrategia 2: Algoritmo del Punto Medio (2/3)





La línea pasa entre E y NE.

El punto que se encuentre mas cercano al punto de intersección Q debe ser elegido.

 Objetivo: encontrar una forma de calcular automáticamente de que lado de la línea se

encuentra M y hacerlo con la menor cantidad de cálculos.

 Variable de decisión: observar de que lado de la línea real se encuentra el punto medio M

de la grilla:
 E se encuentra cercano a la línea si el punto medio M esta por arriba de la línea (Q).
 NE se encuentra cercano a la línea si el punto medio M esta por debajo de la línea (Q)..

 Reducción del error acumulado: la distancia vertical entre el pixel elegido y la línea real

es siempre <= ½.



Para el ejemplo, el algoritmo selecciona NE.



Rio 14

- Roberto Guerrero @ 2014

16

Visualización – Parte 3
Visualización – Parte 3

Example Code

void MidpointLine( int x0, int y0,
{

int x1, int y1, int value)



dx = x1 - x0;
dy = y1 - y0;
d = 2 * dy – dx;
incrE = 2 * dy;
incrNE = 2 * (dy - dx);
x = x0;
y = y0;

int
int
int
int
int
int
int
writePixel(x, y, value);
while (x < x1) {

if (d <= 0) {
} else {

// East Case
// NorthEast Case

d = d + incrE;
d = d + incrNE;
y++;



}

}

}
x++;
writePixel(x, y, value);

/* while */
/* MidpointLine */

Rio 14

- Roberto Guerrero @ 2014

17

Visualización – Parte 3
Visualización – Parte 3

Digitalizar Círculos

 Versión 1 – malo – a partir de la función explicita



y=√ R2−x2

For x = -R to R

y = sqrt(R2 – x2);
Pixel (round(x), round(y));
Pixel (round(x), round(-y));

(0, 17)

Huecos para los
valores de x
cercanos a R

(17, 0)

 Versión 2 – un poco mejor
For = 0 to 360
Pixel (round (R • cos( )), round(R • sin( )));









Rio 14

- Roberto Guerrero @ 2014

18

Visualización – Parte 3
Visualización – Parte 3

Versión 3 — Uso de la Simetría



Simetría de 8-lados

(

x
0

+

ya
,

0

+

b

)



R

(

0 yx
,

0

)

k

 x− x02 y−y02=R2

donde x0 <= x <= k y k = R/sqrt(2)





Simetría: Si (x0 + a, y0 + b) pertenece al circulo, también lo son (x0 ± a, y0 ± b) y
(x0 ± b, y0 ± a); por consiguiente existe simetría de 8-lados.



 A los fines prácticos, los valores a obtener dependerá de que x0 y y0 sean valores enteros.

Rio 14

- Roberto Guerrero @ 2014

19

Visualización – Parte 3
Visualización – Parte 3

Consideraciones para el algoritmo





Es necesaria una variable de decisió