Instituto de Computação - UFF 1 Computação Gráfica I Professor: Anselmo Montenegro anselmo Conteúdo: - Recorte 2D

1

Instituto de Computação - UFF

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

Anselmo Montenegrowww.ic.uff.br/~anselmo

Conteúdo:

- Recorte 2D

2


• Quando especificamos uma janela no Quando especificamos uma janela no espaço do objeto queremos exibir somente espaço do objeto queremos exibir somente dos objetos que estejam no seu dos objetos que estejam no seu interior.interior.

• Naturalmente alguns objetos estarão Naturalmente alguns objetos estarão parcialmente visíveisparcialmente visíveis..

• A operação que determina quais partes A operação que determina quais partes dos objetos planares estão visíveis na dos objetos planares estão visíveis na janela é denominado janela é denominado recorte 2Drecorte 2D..

Recorte 2D:Recorte 2D: introdução introdução

3


Recorte 2D:Recorte 2D: introdução introdução

4


• Problema clássico 2DProblema clássico 2D

• Entrada: Entrada: – Segmento de reta Segmento de reta PP11PP22

– Janela alinhada com eixos (Janela alinhada com eixos (xminxmin, , yminymin), (), (xmaxxmax, , ymaxymax))

• Saída: Segmento recortado (possivelmente nulo)Saída: Segmento recortado (possivelmente nulo)

• Algoritmos:Algoritmos:– Cohen-SutherlandCohen-Sutherland– Cyrus-BeckCyrus-Beck

Recorte 2D:Recorte 2D: recorte segmento de reta x recorte segmento de reta x retânguloretângulo

5


• Vértices do segmento são classificados Vértices do segmento são classificados com relação a cada semi-espaço plano com relação a cada semi-espaço plano que delimita a janelaque delimita a janela

x ≥ xminx ≥ xmin e e x ≤ xmaxx ≤ xmax ee y ≥ yminy ≥ ymin ee y ≤ ymaxy ≤ ymax

• Se ambos os vértices são classificados Se ambos os vértices são classificados como “como “forafora”, descartar o segmento ”, descartar o segmento (totalmente invisível).(totalmente invisível).

Recorte 2D:Recorte 2D: algoritmo Cohen-Sutherland algoritmo Cohen-Sutherland

6


• Se ambos são classificados como “Se ambos são classificados como “dentrodentro”, ”, testar o próximo semi-espaço.testar o próximo semi-espaço.

• Se um vértice está dentro e outro fora, Se um vértice está dentro e outro fora, computar o ponto de interseção computar o ponto de interseção QQ e e continuar o algoritmo com o segmento continuar o algoritmo com o segmento recortado.recortado.


7



xminxmin xmaxxmax

ymaxymax

yminymin

8



xminxmin xmaxxmax

ymaxymax

yminymin

9



xminxmin xmaxxmax

ymaxymax

yminymin

10



xminxmin xmaxxmax

ymaxymax

yminymin

11



xminxmin xmaxxmax

ymaxymax

yminymin

12


• Recorte só é necessário Recorte só é necessário qquando houver um uando houver um vértice dentro e outro foravértice dentro e outro fora..

• Classificação de cada vértice Classificação de cada vértice pode ser codificada pode ser codificada em 4 bitsem 4 bits, um para cada semi-espaço: Dentro = 0 , um para cada semi-espaço: Dentro = 0 e Fora = 1e Fora = 1


10001000

x=xx=x00

y=yy=y11

x=xx=x11

y=yy=y00

1010101010011001

00000000 0010001000010001

01000100 0110011001010101 tbrl

13


• Rejeição trivial: Rejeição trivial: Classif(Classif(PP1)1) andand Classif(Classif(PP2) ≠ 02) ≠ 0

• Aceitação trivial: Aceitação trivial: Classif(Classif(PP1)1) or Classif(or Classif(PP2) = 02) = 0

• Interseção com quais semi-espaços? Interseção com quais semi-espaços? Classif(Classif(PP1) xor Classif(1) xor Classif(PP2)2)


10001000 1010101010011001

00000000 0010001000010001

01000100 0110011001010101

10001000 1010101010011001

00000000 0010001000010001

01000100 0110011001010101

10001000 1010101010011001

00000000 0010001000010001

01000100 0110011001010101

10001000 1010101010011001

00000000 0010001000010001

01000100 0110011001010101

0000 and 0000 = 00000000 and 0000 = 0000

0000 or 0000 = 00000000 or 0000 = 0000

0000 xor 0000 = 00000000 xor 0000 = 0000

1010 and 0110 = 00101010 and 0110 = 0010

1010 or 0110 = 11101010 or 0110 = 1110

1010 xor 0110 = 11001010 xor 0110 = 1100

0001 and 0100 = 00000001 and 0100 = 0000

0001 or 0100 = 01010001 or 0100 = 0101

0001 xor 0100 = 01010001 xor 0100 = 0101

0100 and 1010 = 00000100 and 1010 = 0000

0100 or 1010 = 11100100 or 1010 = 1110

0100 xor 1010 = 11100100 xor 1010 = 1110

14


Recorte 2D:Recorte 2D: algoritmo Cohen-Sutherland - algoritmo Cohen-Sutherland - cálculo do código de um vérticecálculo do código de um vértice

unsigned char code(double x, double y, double xmin, double xmax, double ymin, double ymax){ unsigned char code=0; if (y > ymax) code += 8; if (y < ymin) code += 4; if (x > xmax) code += 2; if (x < xmin) code += 1; return code;}

unsigned char code(double x, double y, double xmin, double xmax, double ymin, double ymax){ unsigned char code=0; if (y > ymax) code += 8; if (y < ymin) code += 4; if (x > xmax) code += 2; if (x < xmin) code += 1; return code;}

15



void CohenSutherlandLineClip(double x0, double y0, double x1, double y1, double xmin, double xmax, double ymin, double ymax) { unsigned char outcode0, outcode1, outcodeOut; double x, y; boolean accept = FALSE, done = FALSE;

outcode0 = code(x0, y0, xmin, xmax, ymin, ymax); outcode1 = code(x1, y1, xmin, xmax, ymin, ymax);

do { if (outcode0 == 0 && outcode1 == 0) { accept = TRUE; done = TRUE; /* trivial draw and exit */ } else if((outcode0 & outcode1) != 0) { done = TRUE; /* trivial reject and exit */ } else { /* discart an out part */ outcodeOut = (outcode0 != 0) ? outcode0 : outcode1; /* pick an out vertice */ if (outcodeOut & 8) { /* discart top */ x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y = ymax; } else if(outcodeOut & 4) { /* discart bottom */ x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y = ymin; } else if(outcodeOut & 2) { /* discart right */ y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x = xmax; } else if(outcodeOut & 1) { /* discart left */ y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x = xmin; } if (outcodeOut == outcode0) { x0 = x; y0 = y; outcode0 = code(x0, y0, xmin, xmax, ymin, ymax); } else { x1 = x; y1 = y; outcode1 = code(x1, y1, xmin, xmax, ymin, ymax); }

} } while (!done);

if (accept) DrawLineReal(x0, y0, x1, y1);}

void CohenSutherlandLineClip(double x0, double y0, double x1, double y1, double xmin, double xmax, double ymin, double ymax) { unsigned char outcode0, outcode1, outcodeOut; double x, y; boolean accept = FALSE, done = FALSE;

outcode0 = code(x0, y0, xmin, xmax, ymin, ymax); outcode1 = code(x1, y1, xmin, xmax, ymin, ymax);

do { if (outcode0 == 0 && outcode1 == 0) { accept = TRUE; done = TRUE; /* trivial draw and exit */ } else if((outcode0 & outcode1) != 0) { done = TRUE; /* trivial reject and exit */ } else { /* discart an out part */ outcodeOut = (outcode0 != 0) ? outcode0 : outcode1; /* pick an out vertice */ if (outcodeOut & 8) { /* discart top */ x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y = ymax; } else if(outcodeOut & 4) { /* discart bottom */ x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y = ymin; } else if(outcodeOut & 2) { /* discart right */ y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x = xmax; } else if(outcodeOut & 1) { /* discart left */ y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x = xmin; } if (outcodeOut == outcode0) { x0 = x; y0 = y; outcode0 = code(x0, y0, xmin, xmax, ymin, ymax); } else { x1 = x; y1 = y; outcode1 = code(x1, y1, xmin, xmax, ymin, ymax); }

} } while (!done);

if (accept) DrawLineReal(x0, y0, x1, y1);}

16


• O algoritmo de Cohen-Sutherland calcula O algoritmo de Cohen-Sutherland calcula interseções desnecessáriasinterseções desnecessárias..

• O algoritmo de Cyrus-Beck utiliza uma O algoritmo de Cyrus-Beck utiliza uma estratégia que permite recortar um estratégia que permite recortar um segmento com menor número de segmento com menor número de interseções.interseções.

• Pode ser utilizado quando a região de Pode ser utilizado quando a região de recorte é um recorte é um polígono convexopolígono convexo..

Recorte 2D:Recorte 2D: algoritmo Cyrus-Beck algoritmo Cyrus-Beck

17


• SSe baseia na e baseia na equação paramétricaequação paramétrica da reta e da reta e no cálculo de interseções baseado nesta no cálculo de interseções baseado nesta representação.representação.


PP00

PP11

NNii

PPEiEi

01,

,

0)(,

)()(

0

010

PPN

PPNt

PtPN

PPtPtP

i

Eii

Eii

0)(, Eii PtPN

0)(, Eii PtPN

0)(, Eii PtPN

18


• Dado um segmento Dado um segmento PP00PP11, sua reta sup, sua reta supoorte rte

intersecta as quatro retas laterintersecta as quatro retas lateraais dis doo retângulo em retângulo em quatro pontosquatro pontos ((caso geral).caso geral).

• UUsando a equação paramsando a equação paraméétrica trica calculamos os calculamos os quatro valores do parâmetro quatro valores do parâmetro tt no qual a reta no qual a reta intersecta as quatro retaintersecta as quatro retass late laterrais do retângulo de ais do retângulo de recorte.recorte.

• Após calcular o valor de Após calcular o valor de tt para as quatro retas para as quatro retas descartamos os valores de descartamos os valores de t t fora do intervalo fora do intervalo [[0,10,1]]..


19


• Cada uma das quatro retas dCada uma das quatro retas diivide ovide o espaço em espaço em dois semi-planos.dois semi-planos.

• CChhamaremos de samaremos de seemi-planos positivos aqueles mi-planos positivos aqueles ddados pelas ados pelas eequações quações yyyy11, , yyyy00, , x x x x11, , x x xx00..


xx xx00

yy yy11

xx xx11

yy yy00

20


• Quando a reta Quando a reta PP((tt)) entra em um dos semi- entra em um dos semi-pplanos lanos através do ponto através do ponto PP((tt00)), tal ponto é identificado com , tal ponto é identificado com

um sinal um sinal - (- (tEtE))..

• SSe o ponto for de saida indicamos com sinal e o ponto for de saida indicamos com sinal +(+(tLtL))..

• OO sinal do ponto é obtido usando o sinal do sinal do ponto é obtido usando o sinal do produto interno produto interno <<NNii,,PP11-P-P00>>..

• SSe e <<NNii,,PP11-P-P00>><0<0 então o ponto é negativo então o ponto é negativo,, cas casoo

contcontrrário é positivo.ário é positivo.


21



CC

DD

AA

BB

x=xx=x00

y=yy=y11

x=xx=x11

y=yy=y00

EE

FF

--

--

--

++

++++ ++

22


Recorte 2D:Recorte 2D: algoritmo Cyrus-Beck – pseudo- algoritmo Cyrus-Beck – pseudo-códigocódigo

{ Calcule Ni e escolha um PEi para cada aresta

tE = 0; tL = 1; for (cada aresta ){ if (Ni.(P1-P0)!=0 ){ /* aresta não é paralela ao segmento */ calcule t; use sign of Ni.(P1-P0) para categorizar como PE ou PL; if( PE ) tE = max(tE, t); if( PL ) tL = min(tL, t); } else { /* aresta paralela ao segmento */ if (Ni.(P0-PEi) > 0) /* está fora */ return nil; } if (tE > tL) return nil; else return P(tE) and P(tL) as true clip intersections; } }}

{ Calcule Ni e escolha um PEi para cada aresta

tE = 0; tL = 1; for (cada aresta ){ if (Ni.(P1-P0)!=0 ){ /* aresta não é paralela ao segmento */ calcule t; use sign of Ni.(P1-P0) para categorizar como PE ou PL; if( PE ) tE = max(tE, t); if( PL ) tL = min(tL, t); } else { /* aresta paralela ao segmento */ if (Ni.(P0-PEi) > 0) /* está fora */ return nil; } if (tE > tL) return nil; else return P(tE) and P(tL) as true clip intersections; } }}

23


• Inclui o problema de recorte de segmentos de reta.Inclui o problema de recorte de segmentos de reta.– Polígono resultante tem vértices que são:Polígono resultante tem vértices que são:

• Vértices da janela,Vértices da janela,

• Vértices do polígono original, ouVértices do polígono original, ou

• Pontos de interseção aresta do polígono/aresta da janelaPontos de interseção aresta do polígono/aresta da janela

• Dois algoritmos clássicosDois algoritmos clássicos– Sutherland-HodgmanSutherland-Hodgman

• Figura de recorte pode ser qualquer polígono convexo.Figura de recorte pode ser qualquer polígono convexo.

– Weiler-AthertonWeiler-Atherton• Figura de recorte pode ser qualquer polígono.Figura de recorte pode ser qualquer polígono.

Recorte 2D:Recorte 2D: recorte de polígono x retângulo recorte de polígono x retângulo

24


• Casos SimplesCasos Simples

• Casos ComplicadosCasos Complicados

Recorte 2D:Recorte 2D: recorte de polígono x retângulo recorte de polígono x retângulo

25


• Idéia é semelhante a do algoritmo de Cohen-Idéia é semelhante a do algoritmo de Cohen-Sutherland.Sutherland.

– Recortar o polígono sucessivamente contra Recortar o polígono sucessivamente contra todos os semi-espaços planos da figura de todos os semi-espaços planos da figura de recorte.recorte.

Recorte 2D:Recorte 2D: Algoritmo Sutherland-Hodgeman Algoritmo Sutherland-Hodgeman

26


• Polígono é dado como uma lista circular de vértices.Polígono é dado como uma lista circular de vértices.

• Vértices e arestas são processados em seqüência e Vértices e arestas são processados em seqüência e classificados contra o semi-espaço plano corrente.classificados contra o semi-espaço plano corrente.

– Vértice:Vértice:• Dentro: copiar para a saída.Dentro: copiar para a saída.

• Fora: ignorar.Fora: ignorar.

– ArestaAresta• Intercepta semi-espaço plano (vértice anterior e posterior Intercepta semi-espaço plano (vértice anterior e posterior

têm classificações diferentes): copiar ponto de interseção têm classificações diferentes): copiar ponto de interseção para a saída.para a saída.

• Não intercepta: ignorar.Não intercepta: ignorar.


27


ForaFora

ss

pp

Copiar pCopiar p

DentroDentro ForaFora

sspp

Copiar iCopiar i


ss

pp

IgnorarIgnorar


sspp

Copiar i,pCopiar i,p

ii

ii

DentroDentro


28


Recorte 2D:Recorte 2D: Algoritmo Sutherland-Hodgeman - Algoritmo Sutherland-Hodgeman - exemploexemplo

29


Recorte 2D:Recorte 2D: Algoritmo Sutherland-Hodgeman - Algoritmo Sutherland-Hodgeman - exemploexemplo

30


• Distinguir os pontos de interseção Distinguir os pontos de interseção gerados:gerados:– De dentro para fora: rotular como do tipo De dentro para fora: rotular como do tipo ..– De fora para dentro: rotular como do tipo De fora para dentro: rotular como do tipo ββ..

• IniciarIniciar o percurso de algum vértice o percurso de algum vértice ““forafora”.”.

• Ao encontrar um ponto de interseção Ao encontrar um ponto de interseção , ligar com o último , ligar com o último ββ visto visto..

• Resultado pode ter mais de uma Resultado pode ter mais de uma componente conexacomponente conexa..

ForaDentro

β

Recorte 2D:Recorte 2D: eliminando arestas fantasmas eliminando arestas fantasmas

31


Recorte 2D:Recorte 2D: eliminando arestas fantasmas - eliminando arestas fantasmas - exemploexemplo

32


vdvd00

00

vdvd22 vdvd33

001111

vdvd11

vfvf0 0 0 0 vdvd0 0 0 0 vfvf1 1 vfvf2 2 11vdvd1 1 vdvd2 2 vdvd3 3 1 1 vfvf33vfvf00

vfvf00vfvf33

vfvf11 vfvf22

0 0 vdvd0 0 0 0 0 0 ee 1 1 vdvd1 1 vdvd2 2 vdvd3 3 1 1 1 1


33


vdvd00

00

vdvd22 vdvd33

001111

vdvd11


34


vdvd11

vdvd00

vdvd33 vfvf22

vdvd22vfvf33vfvf00

vfvf1100

00


35


vdvd11

vdvd00

vdvd33

vdvd22

00

00


36


• Facilmente generalizável para 3D.Facilmente generalizável para 3D.

• Pode ser adaptado para implementação em hardware.Pode ser adaptado para implementação em hardware.– Cada vértice gerado pode ser passado pelo Cada vértice gerado pode ser passado pelo pipelinepipeline para o para o

recorte contra o próximo semi-espaço plano.recorte contra o próximo semi-espaço plano.

• Pode gerar arestas “fantasma”Pode gerar arestas “fantasma”

– Irrelevante para propósitos de desenho.Irrelevante para propósitos de desenho.– Podem ser eliminadas com um pouco mais de trabalho.Podem ser eliminadas com um pouco mais de trabalho.

Recorte 2D:Recorte 2D: algoritmo Sutherland-Hodgman - algoritmo Sutherland-Hodgman - resumoresumo

Documents

Instituto de Computação - UFF 1 Computação Gráfica I Professor: Anselmo Montenegro anselmo Conteúdo: - Recorte 2D