Instituto de Computação - UFF 1 Computação Gráfica I Professor: Anselmo Montenegro anselmo Conteúdo: - Algoritmos para rastreio (scan-conversion)

1

Instituto de Computação - UFF

Computação Gráfica IComputação Gráfica IProfessor:

Anselmo Montenegrowww.ic.uff.br/~anselmo

Conteúdo:

- Algoritmos para rastreio (scan-conversion).

2


Algoritmos para rastreioAlgoritmos para rastreio: : introduçãointrodução

3


pontoponto: (3,2) tamanho 1 sem anti-alias: (3,2) tamanho 1 sem anti-alias pontoponto: (3,3) tamanho 3 sem anti-alias: (3,3) tamanho 3 sem anti-alias

21

21

w

w

y

x

y

x

OpenGL SpecOpenGL Spec

0.50.5 1.51.5 2.52.5 3.53.5 4.54.5 5.55.5

0.50.5

1.51.5

2.52.5

3.53.5

4.54.5

5.55.5w=w=6 e 6 e h=h=55

00 11 22 33 44 55

00

11

22

33

44

xxww

yyww

Algoritmos para rastreioAlgoritmos para rastreio: : Coordenadas de um Coordenadas de um ponto na janela ponto na janela ((windows coordinatewindows coordinate))

As coordenadas do centro de um As coordenadas do centro de um ponto de tamanho impar são:ponto de tamanho impar são:

4


0 1 2 3 4 5

0

1

2

3

4

linha: (0,0),(4,0)linha: (5,1),(5,4)linha: (0,2),(3,5)

Casos triviais em que as linhas passam pelo Casos triviais em que as linhas passam pelo centro das células.centro das células.

Algoritmos para rastreioAlgoritmos para rastreio: : critério geométrico critério geométrico para linhas horizontais, verticais e à 45para linhas horizontais, verticais e à 45°°

5


linha: (0,0),(5,2)linha: (0,0),(5,2)

00 11 22 33 44 55

00

11

22

33

00 11 22 33 44 55

00

11

22

33

x dominantex dominante 1212 yyxx 1212 yyxx x dominante, um pixel por colunax dominante, um pixel por coluna

1212 yyxx 1212 yyxx y dominante, um pixel por linhay dominante, um pixel por linha

Algoritmos para rastreioAlgoritmos para rastreio: : critério geométrico critério geométrico de Bresenham de Bresenham ((19651965)) para linhas para linhas

6


#define ROUND(x) (int)floor((x)+0.5)

void linha(int x1, int y1, int x2, int y2){ float m = (y2-y1)/(x2-x1); float b = y1 - m*x1; float y; fragmento(x1,y1); while( x1 < x2 ) { x1++; y = m*x1 + b; fragmento(x1,ROUND(y)); }}

bmxy ii

11

12

12

mxyb

xx

yym

Podemos evitar a multiplicação?

00 11 22 33 44 55

00

11

22

33

(x(x11,y,y11))

(x2,y2)

Algoritmos para rastreioAlgoritmos para rastreio: : algoritmo simples algoritmo simples para o primeior octantepara o primeior octante

7


void linha(int x1, int y1, int x2, int y2){ float m = (y2-y1)/(x2-x1); float b = y1 - m*x1; float y=y1; pixel(x1,y1); while( x1 < x2 ) { x1++; y += m; fragmento(x1,ROUND(y)); }}

void linha(int x1, int y1, int x2, int y2){ float m = (y2-y1)/(x2-x1); float b = y1 - m*x1; float y=y1; pixel(x1,y1); while( x1 < x2 ) { x1++; y += m; fragmento(x1,ROUND(y)); }}

bmxy ii

11

12

12

mxyb

xx

yym

bxmy ii 11

bmxy ii

myy ii 1

Podemos evitar o uso de ponto flutuante?

(x(x11,y,y11))

(x(x22,y,y22))

Algoritmos para rastreioAlgoritmos para rastreio: : algoritmo simples algoritmo simples para o primeior octante – forma incrementalpara o primeior octante – forma incremental

8


112

121

12

12 xxx

yyyx

xx

yyy

cybxayxF ..),(

1121121212 xyyyxxxyyyxx 01121122112 xyyyxxyxxxyy

xx11 xx22

yy11

yy22

xx

yy

21

12

xx

yyn

F x y( , ) 0

F x y( , ) 0 bmxy ii

11

12

12

mxyb

xx

yym

Algoritmos para rastreioAlgoritmos para rastreio: : equação implícita da equação implícita da retareta

9


cybxayxF ..),( cybxayxF ..),(

ee

nene

xxpp

yypp

mm

0),( mm yxF

xxpp++11 xxpp++22

yypp++1/21/2

yypp++11

yypp++22

mmee

ee

nene

ee

nene

xxpp xxpp++11 xxpp++22

yypp

mmyypp++1/21/2

yypp++11

yypp++22mmnene

ee

nene

0),( mm yxF

Algoritmos para rastreioAlgoritmos para rastreio: : equação básica do equação básica do algoritmo do ponto médio para linhasalgoritmo do ponto médio para linhas

10


),(2),( yxFyxd

e

nemm

escolha

escolhaFd

0

0)(2)(

e

cybxayxFd ppppnovo 2)(2)2(2),2(2 21

21

add antnovo 2

cybxayxFd ppppnovo 2)(2)2(2),2(2 23

23

badd antnovo 22 ne

ae 2

bane 22

ee

nene

xxpp xxpp++11 xxpp++22yypp

mmyypp++1/21/2

yypp++3/23/2mmnene

mmee

bacybxayxFdini 22)(2)1(2),1(2 21

0021

00

bad ini .2

ba

a

ne

e

2

2

Algoritmos para rastreioAlgoritmos para rastreio: : algoritmo do ponto algoritmo do ponto médio - versão para aritmética inteiramédio - versão para aritmética inteira

11


void linhaPM(int x1, int y1, int x2, int y2){ int a = y2-y1; int b = x1-x2; int d=2*a+b; /* valor inicial da var. decisao */ int incrE = 2*a; /* incremento p/ mover E */ int incrNE = 2*(a+b); /* incremento p/ mover NE */ fragmento(x1,y1);

while (x1<x2) { x1++; if (d<=0) /* escolha E */ d+=incrE; else { /* escolha NE */ d+=incrNE; y1++; } fragmento(x1,y1); }

}

void linhaPM(int x1, int y1, int x2, int y2){ int a = y2-y1; int b = x1-x2; int d=2*a+b; /* valor inicial da var. decisao */ int incrE = 2*a; /* incremento p/ mover E */ int incrNE = 2*(a+b); /* incremento p/ mover NE */ fragmento(x1,y1);

while (x1<x2) { x1++; if (d<=0) /* escolha E */ d+=incrE; else { /* escolha NE */ d+=incrNE; y1++; } fragmento(x1,y1); }

}

Algoritmos para rastreioAlgoritmos para rastreio: : algoritmo do ponto algoritmo do ponto médio para linhas – código em Cmédio para linhas – código em C

12


void linhaPM(int x1, int y1, int x2, int y2){ int a = y2-y1; int b = x1-x2; int d=2*a+b; /* valor inicial da var. decisao */ int incrE = 2*a; /* incremento p/ mover E */ int incrNE = 2*(a+b); /* incremento p/ mover NE */ int style[8]={1,1,0,0,1,1,0,0}; int k=1; fragmento(x1,y1); /* primeiro pixel */

while (x1<x2) { x1++; if (d<=0) /* escolha E */ d+=incrE; else { /* escolha NE */ d+=incrNE; y1++; } if (style[(++k)%8]==1) fragmento(x1,y1); }

}

void linhaPM(int x1, int y1, int x2, int y2){ int a = y2-y1; int b = x1-x2; int d=2*a+b; /* valor inicial da var. decisao */ int incrE = 2*a; /* incremento p/ mover E */ int incrNE = 2*(a+b); /* incremento p/ mover NE */ int style[8]={1,1,0,0,1,1,0,0}; int k=1; fragmento(x1,y1); /* primeiro pixel */

while (x1<x2) { x1++; if (d<=0) /* escolha E */ d+=incrE; else { /* escolha NE */ d+=incrNE; y1++; } if (style[(++k)%8]==1) fragmento(x1,y1); }

}

Algoritmos para rastreioAlgoritmos para rastreio: : algoritmo do ponto algoritmo do ponto médio para linhas com estilo – código em Cmédio para linhas com estilo – código em C

13


F

F

xF

y

xx

F(x,y) =F(x,y) = 0 0

4545oo

yy

Segundo o critério de Bresenham se a curva está Segundo o critério de Bresenham se a curva está mais próxima da horizontal tomamos um ponto por mais próxima da horizontal tomamos um ponto por coluna caso contrário tomamos um ponto por linha.coluna caso contrário tomamos um ponto por linha.

O ponto de transição é o que possui gradiente na O ponto de transição é o que possui gradiente na direção dada pelo ângulo de 45 graus.direção dada pelo ângulo de 45 graus.

Algoritmos para rastreioAlgoritmos para rastreio: : rastreio para elipses rastreio para elipses – critério de Bresenham– critério de Bresenham

14


O critério do ponto médio é aplicado de forma O critério do ponto médio é aplicado de forma semelhante ao aplicado para linhas.semelhante ao aplicado para linhas.

A diferença principal é que F(x,y) é quadrática.A diferença principal é que F(x,y) é quadrática. Para implementar o algoritmo eficazmente é Para implementar o algoritmo eficazmente é

necessário calcular incrementos dos incrementos necessário calcular incrementos dos incrementos de y quando x é acrescido de 1.de y quando x é acrescido de 1.

Algoritmos para rastreioAlgoritmos para rastreio: : rastreio para elipses rastreio para elipses

15


A figura abaixo ilustra a porção do primeiro A figura abaixo ilustra a porção do primeiro quadrante no qual a curva é x dominante. Neste quadrante no qual a curva é x dominante. Neste caso as escolhas sãocaso as escolhas são e e e e sese..

A partir do ponto de transição a curva é y A partir do ponto de transição a curva é y dominante e as escolhas são dominante e as escolhas são ss e e sese..

ee

sese

mmmmee

mmsese

F(F(x,yx,y) ) = 0= 0

Algoritmos para rastreioAlgoritmos para rastreio: : rastreio para elipses rastreio para elipses

16


O rastreio de um círculo é um O rastreio de um círculo é um caso particular do caso particular do rastreio de uma elipserastreio de uma elipse..

Trabalhamos com o segundo octante, no qual a Trabalhamos com o segundo octante, no qual a curva é curva é xx dominante. dominante.

Utilizamos a simetria do círculoUtilizamos a simetria do círculo para definir os para definir os pontos nos demais octantes.pontos nos demais octantes.

Algoritmos para rastreioAlgoritmos para rastreio: : rastreio de círculosrastreio de círculos

17


x=0,y=raio; fragmento(x,y);while (x<y) { x++; if (F(M)<0) escolha E; else escolha SE; fragmento(E ou SE);}

x=0,y=raio; fragmento(x,y);while (x<y) { x++; if (F(M)<0) escolha E; else escolha SE; fragmento(E ou SE);}

xx

yy

cada ponto calculadocada ponto calculado define 8 define 8 pixelspixels

e

se

mme

mse

F(x,y) = 0

xx

yy

4545oo

x = yx = y

Algoritmos para rastreioAlgoritmos para rastreio: : rastreio de círculosrastreio de círculos

18


Algoritmos para rastreioAlgoritmos para rastreio: : rastreio de polígonosrastreio de polígonos

19


02

1

1

0

1

3

6

1

Algoritmos para rastreioAlgoritmos para rastreio: : rastreio de polígonos rastreio de polígonos – noção de interior para um polígono qualquer– noção de interior para um polígono qualquer

20


y

ys

x

0

1

2

3

4

0xi4

ymax

ymin

dados: {(x0,y0), (x1,y1), (x2,y2) (x3,y3), (x4,y4)}dados: {(x0,y0), (x1,y1), (x2,y2) (x3,y3), (x4,y4)}

Achar ymax e ymin

Para cada y [ymax,ymin]

Para cada aresta calcular as interseções

ordenar interseções

desenhar linhas horizontais

Achar ymax e ymin

Para cada y [ymax,ymin]

Para cada aresta calcular as interseções

ordenar interseções

desenhar linhas horizontais

vx= {xi1 , xi0 , xi4 , xi3}vx= {xi1 , xi0 , xi4 , xi3}

i0i1 i3i4

xi1 xi0 xi3

Algoritmos para rastreioAlgoritmos para rastreio: : preenchimento de preenchimento de polígonospolígonos

21


inclui vértices:inclui vértices: ii0-0-ii1, 1, ii2-i3, 2-i3, ii4-?4-?

não inclui vértices:não inclui vértices: ii0-?0-?

xx

yy

yyss

5500

11

22 44

ii00 ii22

ii33

00

ii11 ii44

33xx

yy

yyss

5500

11

22 44

ii00 ii22

ii33

00

ii11 ii44

33xx

yy

yyss

5500

11

22 44

ii00 ii22

ii33

00

ii11 ii44

33

Solução:Solução:

xx

yy

yyss

5500

11

22 44

ii00

00

ii44

33

ouou

xx

yy

yyss

5500

11

22 44

ii00 ii22

ii33

00

ii11

33

Algoritmos para rastreioAlgoritmos para rastreio: : interseção nos interseção nos vérticesvértices

22


,2,, 000 dxxdxxx ,2,, 000 dxxdxxx

Interpolação linear na arestaInterpolação linear na aresta

yyss++11dy = dy = 11

01

01

yy

xxdx

xx

yy

yy00

yy11

yyss

xx11xx0000 xxii xxi+1i+1

,2,, 000 dccdccc ,2,, 000 dccdccc

Algoritmos para rastreioAlgoritmos para rastreio: : otimização do otimização do algoritmo de preenchimento – interpolação algoritmo de preenchimento – interpolação linearlinear

23


0

1

2

3

4

5

6B

C

a

b

c

x

y A

Algoritmos para rastreioAlgoritmos para rastreio: : otimização do otimização do algoritmo de preenchimento – triângulosalgoritmo de preenchimento – triângulos

24


))(())(( ABACACAB yyxxyyxxbc

BB

CCaa

bb

cc

xx

yy AA

0bc xx

yy

BB

CC

aa

bb

cc

AA

0bc

Algoritmos para rastreioAlgoritmos para rastreio: : possíveis possíveis configurações para um triângulo configurações para um triângulo yyAA≥ ≥ yyBB ≥ ≥ yyCC

25


BB

CC

aa

bb

cc

xx

yy AA

yyCC

yyAA

yyBB

xxaa xxbb

yyss

BB

CCaa

bb

cc

xx

yy AA

yyCC

yyAA

yyBB

xxcc xxbb

yyss

Algoritmos para rastreioAlgoritmos para rastreio: : rastreio de um rastreio de um triângulotriângulo

Documents

Instituto de Computação - UFF 1 Computação Gráfica I Professor: Anselmo Montenegro anselmo Conteúdo: - Algoritmos para rastreio (scan-conversion)