Conteúdo Online 3

Prévia do material em texto

RASTERIZAÇÃO DE LINHAS
Vimos como transformar as coordenadas reais de um ponto nas coordenadas de um pixel no interior de uma janela de visualização (mapeamento window-to-viewport). Não devemos nos esquecer que esse mapeamento converte tanto pontos do SRU em pixels do SRD como o contrário, ou seja, dado um pixel no SRD calcula-se o ponto no SRU. Desta vez, vamos ligar dois pixels para obtermos uma linha reta.
A motivação é simples. Em vez de mapearmos do SRU para o SRD cada ponto de uma aresta que liga dois vértices, mapeamos apenas os vértices no interior da viewport e completamos as arestas com um algoritmo que considere apenas os pixels do SRD.
Sejam XRi e YRi as coordenadas de um ponto inicial Pi e XRf e YRf as coordenadas de um ponto Pf, final, ambos pertencentes ao R2 (logo, ao SRU). A equação da reta que passa por Pi e Pf é dada por: y = mx + b (figura 1)
 
É claro que, em um primeiro momento, precisamos transformar as coordenadas dos pontos Pi e Pf em pixels, coordenadas da janela de visualização (viewport). Para tanto, procedemos como no módulo anterior. Na maioria dos casos, contudo, já temos os pontos Pi e Pf em pixels. Por exemplo: Em um programa de desenho tipo PaintBrush, na ferramenta "linha", pressionamos o botão do mouse para indicar o pixel inicial (Pi). Em seguida, arrastamos o ponteiro através da tela com o botão do mouse pressionado e soltamos, indicando o ponto final (Pf). Neste caso, observe, não houve necessidade de transformação de pontos reais em pixels. No entanto, em programas como CAD/CAM ou programas que desenham gráficos (Excel, Grapher, etc...), o mapeamento window-to-viewport dos pontos Pi e Pf é necessário. No entanto, seja em um caso ou no outro, o PREENCHIMENTO do espaço entre os pontos para gerar uma linha reta pode ser feito mais eficientemente calculando-se apenas os pixels que devem ser ativados MAIS PRÓXIMOS da reta teórica. A RASTERIZAÇÃO DE LINHAS é, portanto, efetuada no espaço dos pixels, através de um algoritmo que ligue os dois pontos dados na viewport do SRD.
Há vários algoritmos para esse fim. O mais simples pertence a categoria chamada DDA (Digital Differencial Analizer) 
[veja http://en.wikipedia.org/wiki/Digital_Differential_Analyzer_(graphics_algorithm)]
Basicamente, os DDAs são ALGORITMOS INCREMENTAIS em uma das variáveis, que se utilizam diretamente da definição de reta dada por sua equação: y = mx +b. Algoritmos incrementais são aqueles em que uma das variáveis é obtida apenas incrementando o seu valor, por exemplo X = X + 1, e a outra é calculada por alguma regra a partir da primeira.
Vamos ligar os pixels (XPi, YPi) e (XPf, YPf)...
Primeiro calculamos os parâmetros da reta e inicializamos variáveis:
·         n = XPf-XPi
·         m = (YPf-YPi)/n
·         X0 = XPi
·         Y0 = YPi
Observe que "n" é o número de colunas de pixels entre Pi e Pf e que Y0 também pode ser entendido como Y0 = m*X0 + b.
Em seguida incrementamos sucessivos Xs e calculamos os Ys correspondentes pela definição da reta:
·         X1 = X0 + 1
·         Y1 = m.X1 + b = m*(X0+1) + b = m*X0 + m + b = m*X0 + b + m Þ Y1 = Y0 + m
Continuando (faça as contas!) ...
·         X2 = X1 + 1 Þ X2 = X0 + 2
·         Y2 = Y0 + 2*m
·         X3 = X0 + 3
·         Y3 = Y0 + 3*m
·         ...
Por indução, obtemos uma expressão geral para o j-ésimo ponto:
·         Xj = X0 + j
·         Yj = Y0 + j*m
O último ponto será o ponto n
·         Xn = X0 + n
·         Yn = Y0 + n*m ~ YPf
Observe que Yn ~ YPf porque o resultado da expressão n*m é truncado (ou, se preferir, arredondado), introduzindo um pequeno erro que pode ser de até um pixel.
Os pontos fracos nos algoritmos DDAs são o uso da ARITMÉTICA REAL e uma pequena imprecisão por ERROS DE ARREDONDAMENTO.
Além dessas desvantagens, que são bastante indesejáveis, o algoritmo apresenta uma restrição importante: ele funciona apenas para retas onde |m| < 1, ou seja, retas com inclinações entre -45° e 45°. Para obtermos corretamente as demais inclinações, devemos lançar mão de SIMETRIAS.
Por exemplo, podemos dividir o plano cartesiano em oito fatias, ou OCTANTES. Para cada um deles as retas assumem direções diferentes. O algoritmo descrito foi pensado para servir no PRIMEIRO OCTANTE, mas funciona também no OITAVO OCTANTE. Com uma pequena modificação pode-se facilmente estendê-lo para os QUARTO e QUINTO OCTANTES (pense em como isso pode ser feito!). Os demais também podem ser obtidos a partir dessas extensões transpondo as variáveis X <=> Y.
ALGORITMO DE BRESEHAM PARA SEGMENTOS DE RETAS
Outra família de Algoritmos é formada pelos ALGORITMO DE BRESENHAM e ALGORITMO DO PONTO MÉDIO (Há uma pequena confusão de nomenclatura nas diferentes referências. Ambos algoritmos, Bresenham e Ponto Médio, são, frequentemente, tidos como a mesma coisa, pois geram os mesmos pixels).
Esses algoritmos não usam diretamente a definição da reta, mas sim as DIFERENÇAS, ou as distâncias (erro) entre os pixels adjacentes à reta desejada. Como nos DDAs, são algoritmos incrementais. Entretanto, diferentemente, AMBAS AS VARIÁVEIS são incrementadas de uma quantidade inteira. Assim, para cada X = X + 1 o valor de Y é decidido pelo algoritmo incrementando-se ou não em função de alguns testes de diferenças. Ou seja, faz-se Y = Y ou Y = Y + 1 conforme o caso. Procure na Internet algum site onde o algoritmo de Bresenham é obtido para mais informação de como é seu desenvolvimento matemático. Detalhe, Jack Bresenham trabalhava na IBM na década de 1960 quando desenvolveu esses algoritmos para rasterização de linhas e curvas
O algoritmo de Bresenham baseia-se no argumento de que um segmento de reta, ao ser plotado, deve ser contínuo, ou melhor, os pixels que compõem um segmento de reta devem ser vizinhos.
Uma vez que o algoritmo também é pensado para o PRIMEIRO OCTANTE, discutiremos o caso de 0 £ m £ 1
Aqui, o ponto de partida é a seguinte pergunta: se 0 < m < 1, e dado um ponto de um segmento de reta (x, y) o próximo pixel a ser pintado será o (x+1, y) ou o (x+1, y+1) ? O algoritmo de Breseham responde esta questão calculando uma variável de teste (p no algoritmo dado abaixo) para cada pixel, e passando para o pixel seguinte, até alcançar o último pixel do segmento de reta (c.f. figura 2).
 
 
 
 
 
 
 
 
 
 
 
 
Vejamos como podemos descrever o algoritmo de Bresenham...
Parâmetros de entrada: (xi, yi) e (xf, yf) (pontos inicial e final do segmento de reta)
1. Calcula-se    Dx = xf – xi    e          Dy = yf – yi.
2. Coloca-se nas variáveis de trabalho o ponto inicial:    x = xi             e          y = yi
3. Calcula-se o parâmetro de decisão:               p = 2Dy - Dx
4. Plota-se o ponto (x, y).
5. Se p for negativo (isto é, se p < 0) então:      x = x + 1,       p = p + 2Dy e passa-se para o passo 7.
6. Se p for positivo ou zero então:         x = x + 1,       y = y + 1        e          p = p + 2Dy - 2Dx
7. Repete-se os passos 4 a 6 até que o ponto (xf, yf) seja alcançado.
 Note que o algoritmo de Bresenham (e o algoritmo do ponto médio) também só calcula linhas que estejam entre 0 e 45°, ou seja, se 0 < m < 1, primeiro OCTANTE. As alterações necessárias para estender o algoritmo para os demais octantes não parecem tão triviais quando no caso do DDA. O emprego de SIMETRIAS é muito comum nos algoritmos de rasterização de primitivas. Os casos especiais (Dy=0,Dx=0 ou  Dx = Dy) também devem ser considerados com o objetivo de otimização.
A principal desvantagem do algoritmo de Bresenham é sua implementação, o que é completamente irrelevante no contexto da relação programador x usuário. Um bom programador é aquele que procura implementar bons algoritmos, ou seja, algoritmos com máxima eficiência. Já o usuário espera um resultado limpo e preciso, que é o que o algoritmo de Bresenham oferece, ao contrário do DDA. Como vantagens altamente desejáveis do algoritmo de Bresenham podemos citar: o uso de aritmética inteira, o que o torna rápido na execução e mais facilmente tratável em nível de linguagem de máquina, e preciso, ou seja, ele rigorosamente começa no pixel inicial e terminano pixel final, possibilitando uma concatenação limpa de polilinhas, sem superposições e duplicação de pixels.
 
EXERCÍCIOS RESOLVIDOS
R1. Escreva a equação da reta que passa pelos pontos A = (0.5, 1.5) e B = (2.0, 3.5) no SRU. Quais os valores dos coeficientes linear e angular da mesma?
RESP.: y = 1.3x + 0.8     Coef. Angular (m) = 1.3, Coef. Linear (b) = 0.8
Pela figura 1 deste módulo:
y = mx +b
onde m é o coeficiente linear e b o coeficiente angular da equação da reta
Fazendo XRi = 0.5, YRi = 1.5, XRf = 2.0 e YRf = 3.5, temos:
m = (YRf - YRi)/(XRf - XRi) = (3.5 - 1.5)/(2.0 - 0.5) = 2.0/1.5 = 1.33
b =YRi - m.XRi = 1.5 - 1.33´0.5 = 0.835
 
Note que o coeficiente angular é maior do que 1, o que indica que a reta tem mais de 45° de inclinação. De fato, tan(a) = m = 1.33 => a = atan(m) = 53.13°. Isto significa que não poderíamos usar diretamente os algoritmos DDA ou Bresenham desenvolvidos neste texto, pois foram obtidos para retas com inclinação entre 0° e 45°. Uma alternativa para resolver esse problema seria permutar as coordenadas (x, y) como (y, x), usar os algoritmos e retornar os valores originais. Note também, que o coeficiente linear não é utilizado nos algoritmos final para rasterização de linhas.
 
R2. Quando traçamos a ARESTA (segmento de reta) entre dois VÉRTICES (pontos) A e B, apenas o segmento A'B' que encontra-se no interior da window deve ser mapeado para a viewport (o recorte, ou clipping, na figura ao lado). Pense no caso mais simples onde só o vértice A encontra-se no exterior da window (ou seja, o segmento de reta representável é o A'B). Ache as coordenadas do ponto A' no SRU para o caso em que A = (0.5, 1.5), B = (2.5, 2.5) e uma window limitada por (1.0, 1.0) - (3.0, 3.0).
 
RESP.: A' = (1.0, 1.625)
 
Para calcularmos o valor de A' primeiro devemos calcular a equação da reta AB de maneira análoga com fizemos anteriormente. Assim:
Fazendo XRi = 0.5, YRi = 1.5, XRf = 2.5 e YRf = 2.5, temos:
m = (YRf - YRi)/(XRf - XRi) = (2.5 - 1.5)/(2.5 - 0.5) = 0.5/2.0 = 0.25
b =YRi - m.XRi = 1.5 - 0.25´0.5 = 1.375
 => y = 0.25x + 1.375
 
Depois precisamos identificar em que lugar o ponto A' aparece nas bordas da window. Essa é a parte difícil do algoritmo, mas vamos fazê-lo visualmente. Note que o ponto A = (0.5, 1.5) está a esquerda e acima de (XRMIN, YRMIN) = (1.0, 1.0) e abaixo de YRMAX = 3.0, na área rotulada com 0001 (veja figura da direita abaixo)
 
 
 
Ou seja, A' está sobre a reta vertical x = XRMIN = 1.0
 
Sabendo isso, podemos calcular o valor da coordenada y do ponto A' pela equação da reta fazendo x = 1.0. Assim:
y = 0.25 x 1.0 + 1.375 = 1.625
Logo: A' = (1.0, 1.625)
 
NOTA. O que acabamos de fazer é parte do que chamamos de clipping. Para desenharmos o segmento de reta A'B na viewport devemos calcular, ainda, os valores das coordenadas dos pixels correspondente aos pontos A' e B na viewport e uni-los usando o algoritmo DDA ou Bresenham.
image1.jpeg
image2.jpeg
image3.jpeg
image4.jpeg