1 Rendering

2 Contenido Objetivo Representación de líneasAlgoritmo DDA Algoritmo de Bresenham Representación de polígonos Rellenado de polígonos Eliminación de superficies ocultas

3 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

4 Representación de una líneaDadas las coordenadas de dos vértices Determinar los pixels que deben marcarse Produce efectos incorrectos marcar todos los pixels por los que pasa Solución correcta

5 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 Next k

6 Algoritmo de BresenhamDDA 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 1

7 Algoritmo de BresenhamEl 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

8 Algoritmo de BresenhamOperaciones 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

9 Algoritmo de Bresenhamdx = 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 Loop

10 Representación de polígonosSe procesa cada línea (scan line) Se rellena entre el inicio y final de cada arista Para el polígono sólo son necesarios los pixels rojos

11 Representación de aristas de polígonosSe 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

12 Rellenado entre aristasEn 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

13 Scan Line Se genera la imagen línea a línea Para cada línealista 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

14 Polígono por polígono Se genera la imagen polígono por polígonoPara 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)

15 Eliminación de superficies ocultasHan 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

16 Z buffer Una matriz con los valores de z en cada pixelPermite 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

17 Creación de escenas Esquema (storyboard) Modelos de los objetosPosición Rendering inicial Modificaciones Rendering final

18

19