Sumá
Sumário
Algoritmos de clipping
Introdução
Principais algoritmos
Algoritmos mais eficientes
Leandro Tonietto
Computação Gráfica
Desenvolvimento Jogos e Entretenimento Digital
[email protected]
http://www.inf.unisinos.br/~ltonietto/jed/cgr/clip.pdf
Out-2007
Introduç
Introdução
Categoria de algoritmos segunda maior importância em
computação gráfica
Clipping, ou recorte, de objetos em relação à outro
objeto, significa calcular a intersecção entre eles.
Dois tipos de algoritmos:
Line-clipping: segmentos de linhas que intersectam polígonos
Polygon-clipping: polígonos inteiros que intersectam outros
polígonos
Definições:
Introduç
Introdução
Trabalho para GB: apresentar
um dos algoritmos de clipping
Principais algoritmos:
Algoritmos Line-clipping
Algoritmos polygon-clipping
Polígono que será recortado é chamado de subject polygon.
Polígono que referência para o recorte é
chamado de clip polygon.
Introduç
Introdução
Conceitos: turning points
LineLine-clipping algorithms
Cohen-Sutherland Line Clipping:
Dado um segmento de linha (P1, P2), cortá-lo por
uma grade retangular e retornar qual segmento ele
faz parte.
O mais popular dos algoritmos, pois é muito simples.
c(P) = x3x2x1x0
Xn=(0|1)
X0=1 se esta à direita
X1=1 se esta acima
X2=1 se esta à esquerda
X3=1 se está abaixo
1
LineLine-clipping algorithms
Cohen-Sutherland Line Clipping:
LineLine-clipping algorithms
Cohen-Sutherland Line Clipping:
Passo 1: calcular a região de corte para os dois pontos do
segmento (c1 = c(P1) e c2 = c(P2))
Passo 2: testar descarte trivial:
c1 or c2 = 0 completamente dentro retornar Q1=P1 e
Q2=P2.
c1 and c2 ≠ 0 completamente fora retornar NULL ou
vazio.
Passo 3: subdividir segmento em partes cortando nas bordas
das linhas da janela.
Determinar ponto em que o segmento deve ser cortado
novamente.
A linha será corta a partir do c(P) que tem o bit não zerado a
esquerda. Assume a intersecção como novo ponto de início.
Repetir os passos 1-3 para cada segmento de linha
interseccionado.
LineLine-clipping algorithms
Cohen-Sutherland Line Clipping:
O passo 2 é o ponto de parada do algoritmo. Pois ou
a linha é descartada por ficar completamente fora
da grade ou em algumas das iterações será
retornado o segmento que está completamente
dentro da grade.
No pior caso serão quadro iterações.
Referências bibliográ
bibliográficas
Agoston, Max K. Computer Graphics and
Geometric Modeling: Implementation
and Algorithms. Springer. 2005.
2