Rendering

Contenido

• Objetivo

• Representación de líneas– Algoritmo DDA– Algoritmo de Bresenham

• Representación de polígonos

• Rellenado de polígonos

• Eliminación de superficies ocultas

Representación (Rasterization)

• Se dispone de:– Topología de la escena– Coordenadas de los vértices proyectados– Intensidades en los vértices o en cada punto– Coordenada z de los vértices

• Se desea obtener:– Color en cada pixel

Representación de una línea

• Dadas las coordenadas de dos vértices

• Determinar los pixels que deben marcarse– Produce efectos incorrectos marcar todos los

pixels por los que pasa

432100 1 2 3 4 5 6

432100 1 2 3 4 5 6

Solución correcta

Algoritmo DDA (Digital Diferential Analyzer)

dx = xb - xa

dy = yb - ya

x = xa

y = ya

If (Abs(dx) > Abs(dy)) Then

steps = Abs(dx)

Else

steps = Abs(dy)

End If

xIncrement = dx / steps

yIncrement = dy / steps

Call Plot(x, y)

For k = 0 To steps - 1

x = x + xIncrement

y = y + yIncrement

Call Plot(x, y)

Next k

Algoritmo de Bresenham

• DDA trabaja con números reales

• El algoritmo de Bresenham se desarrolló para plotters digitales

• Se basa en:– incrementar en el sentido mayor– la otra coordenada se incrementa 0 o 1– Se controla por el error entre la línea y

el orígen del píxel más cercano

1/2

0

1

Algoritmo de Bresenham

• El error se incrementa con el valor de la pendiente: e = e + dy/dx

• Cuando el error es superior a 1/2:– se incrementa y– se resta 1 al error

• Se comienza con– e = -1/2– se controla e > 0 -0,4

-0,3

-0,2

-0,1

0

0,1

0,2

0,3

0,4

0,5

0,6

1 2 3 4 5

Algoritmo de Bresenham

• Operaciones con e:– Inicio: e = dy/dx - 1/2– Incremento: e = e + dy/dx– Control: if (e>0) then e = e -1, x = x + 1

• x e y son enteros

• e es real– Para trabajar con enteros, se multiplica el error

por 2 • dx

Algoritmo de Bresenham

dx = Abs(xa - xb)

dy = Abs(ya - yb)

e = 2 * dy - dx

If (xa > xb) Then

x = xb

y = yb

xEnd = xa

Else

x = xa

y = ya

xEnd = xb

End If

Call Plot(x, y)

Do While (x < xEnd)

x = x + 1

If (e > 0) Then

y = y + 1

e = e - 2 * dx

End If

e = e + 2 * dy

Call Plot(x, y)

Loop

Representación de polígonos

• Se procesa cada línea (scan line)

• Se rellena entre el inicio y final de cada arista

10

9

8

7

6

5

4

3

2

1

0

0 1 2 3 4 5 6 7 8 9 10

4

3

2

1

0

0 1 2 3 4 5 6

Para el polígono sóloson necesarios los pixels rojos

Representación de aristas de polígonos

• Se necesita un pixel por línea horizontal (scan line)• Se basan en modificaciones de los algoritmos DDA o de Bresenham,

ejemplo con DDA:

dx = xb - xa

dy = yb - ya

x = xa

increment = dx / dy

For y = ya To yb

Call Plot(x, y)

x = x + increment

Next y

4

3

2

1

0

0 1 2 3 4 5 6

Rellenado entre aristas

• En cada línea hay un número par de aristas

• En polígonos convexos son siempre 2

• Se realiza el sombreado y la coordenada z

• El modo de representación se puede realizar– scan line– polígono por polígono

Scan Line

• Se genera la imagen línea a línea

• Para cada línea– lista de aristas en la línea (añadir y eliminar)– en cada pixel, obtener valores de los polígonos

en el pixel a partir de sus aristas (incrementalmente)

– representar el pixel del polígono más cercano

Polígono por polígono

• Se genera la imagen polígono por polígono

• Para cada polígono– Para cada línea entre ymax e ymin del polígono

• obtener lista de aristas en la línea

• representar los pixels entre estas aristas si no hay representado otro polígono más cercano (se almacena también el valor de z)

Eliminación de superficies ocultas

• Han existido históricamente distintos métodos

• Se puede comentar el algoritmo del pintor

• El utilizado habitualmente es el Z-buffer– es el único posible en representación polígono

por polígono– implementado en hardware

Z buffer

• Una matriz con los valores de z en cada pixel

• Permite representar los polígonos de forma independiente

• Al representar un polígono, se comparan sus pixels con los almacenados y si son visibles se representan y substituyen el valor de z

Creación de escenas

• Esquema (storyboard)

• Modelos de los objetos

• Posición

• Rendering inicial

• Modificaciones

• Rendering final

http://www.pixar.com/howwedoit/index.html