Algoritmos de Varrimento
Avançados para Desenho
de Primitivas 2D
24T12 – Sala 3F5
Bruno Motta de Carvalho
DIMAp – Sala 15 – Ramal 327
1
DIM102
Recorte


2
Recorte (clipping) é o processo de determinação
da(s) porção(ões) de uma primitiva internas à
uma área de recorte (clip region)
Scissoring (tesourando?)
DIM102
Algoritmo de NichollLee-Nicholl

Algoritmos podem calcular as 4 interseções da
linha com a janela de recorte e compará-las aos
pontos finais da linha

O Algoritmo de NLN determina onde o ponto
inicial (P) e o ponto final (Q) estão

Essas posições determinam quais arestas a
linha intersecta

Regiões são nomeadas de acordo com quais
arestas intersectadas pelas linhas que passam
por elas
3
DIM102
Algoritmo de NichollLee-Nicholl

Linha PQ é testada para se saber se está a direita
ou a esquerda das linhs P(xmin,ymax) e P(xmax,ymax)

Como os cálculos destes testes e das interseções
são similares, alguns valores são armazenados
para reutilização
4
DIM102
Recorte de Polígonos
5
DIM102

Ambiguidade: inclusão
ou não de arestas
não-pertencentes
(degenerated) ao
polígono original

Podem causar
problemas caso o
polígono recortado
seja utilizado para
definir uma polilinha
Algoritmo de LiangBarsky

Polígonos são uma sequência de pontos P1,
P2, ..., Pn e as arestas do polígono são P1P2,
P2P3, ..., PnP1

P(t)=(1-t)Pi + tPi+1, onde 0<t<=1

Regiões são classificadas de acordo com os
planos definidos pela linhas de recorte

Posições finais de arestas determinam quais
linhas de recorte podem ser interceptadas
pela próxima aresta
6
DIM102
Algoritmo de LiangBarsky
7
DIM102

A aresta que entra
em uma das 4
regiões dos cantos
adiciona o vértice do
canto

Usando-se a
formulação
paramétrica,
computa-se os
valores tin1, tin2, tout1 e
tout2
Algoritmo de LiangBarsky

Duas possibilidades (abaixo) – tin1 e tout2 são a
primeira e última interseções

Se a aresta é visível então 0<tout1 e 1>tin2

Casos especiais para linhas verticais e
horizontais
8
DIM102
Algoritmo de LiangBarsky

9
Uma etapa de pós-processamento é necessária
para remover arestas não desejáveis geradas
pelo algoritmo
DIM102
Algoritmo para
Polígonos de Weiler

Permite efetuar o recorte de um polígono (A)
contra outro (B)

Algoritmo encontra grupos de polilinhas
fechadas que são bordas de regiões
disjuntas

O polígono recortado corresponde as regiões
pertencentes a A e B

Interseções de arestas dos dois polígonos
resultam na adição de novos vértices

As arestas são repetidas, gerando contornos
10
DIM102
Algoritmo para
Polígonos de Weiler
11
DIM102
Algoritmo para
Polígonos de Weiler

Cada aresta gera dois contornos

Reorganização de contornos para que eles
formem as bordas das regiões disjuntas

As áreas classificadas como pertencentes a
AB formam o polígono recortado

Algoritmo funciona com um número arbitrário
de polígonos e consiste em:
 Achar interseções de arestas de A e B
 Separar as regiões
 Selecionar regiões que estão em A e B
12
DIM102
Algoritmo para
Polígonos de Weiler

13
DIM102
Reorganizando
contornos em:
 Interseções
transversas
 Interseções nãotransversas
(arestas
coincidentes)
 Interseções
tangenciais
Algoritmo para
Polígonos de Weiler
14
DIM102
Algoritmo para
Polígonos de Weiler

Árvore utilizada para descrever relacionamento
entre os contornos

Resultado é obtido selecionando-se a sub-árvore
que contém os contornos que pertencem a A e B
15
DIM102
Desenhando primitivas

Atributos: Estilos de linha, fim-de-linha,
preenchimento e junção-de-linhas, e largura de
linha

Atributos são tratados como geométricos ou
cosméticos

Modelo de referência determina a semântica de
um sistema gráfico
16
DIM102
Algoritmos de Linha,
Polilinha e Círculo

Linhas com pontos finais não-inteiros

Polilinhas com ângulos muito agudos
(problemas com xor)

Círculos com raio e centro não inteiros (sem
simetria)

Algoritmo do ponto médio tem de ser
modificado, alterando-se a inicialização e
diferenças parcias
17
DIM102
Primitivas Largas
18
DIM102

Formato dos
pontos finais de
linhas e junções
em polilinhas

Geralmente vários
estilos são
implementados em
sistemas gráficos
Primitivas preenchidas


19
Estratégias de preenchimento:

Par-ímpar

Não-exterior

Nonzero winding
Nonzero winding

Traçe uma reta do ponto para o exterior do
polígono.

Adicione 1 para as arestas cruzadas em uma
direção e subtraia 1 para a outra direção

Se o número de winding não é 0 o ponto é
interno
DIM102
Antialiasing (linhas)
20

Calculando interseções de
linhas de larguras
diferentes

Como lidar com os pontos
finais das linhas?

Problemas com
interseções de linhas

Como tratar cores em
linhas cruzadas?

Acumulação das primitivas
antes do desenho
DIM102
Antialiasing (Círculos)
21
DIM102

Interseção com filtro
cônico de raio 1
também depende do
raio do círculo

Tabelas individuais para
raios menores e uma
para raios maiores

Para círculos de raio
não-inteiro, interpola-se
os valores das tabelas
Antialiasing (Pontos
Fins de Linhas,
Retângulos, Polígonos)

No caso de pequenos retângulos, a
interseção é calculada pela subtração de
duas interseções com retângulos maiores

Fins de linhas arredondados podem ser
calculados como meios-círculos

Polígonos podem ser tratados como se
fossem retângulos, i.e., com ângulos de 90o
(aproximação falha em alguns casos)

Tabelas extras para 45o e 135o propiciam um
melhor resultado
22
DIM102
Problemas com Texto

Especificações subpixel (superamostragem)

Armazenamento das fontes em diferentes
fases (translações no subgrid) aumenta a
quantidade de memória necessária

Mover e aumentar definições de letras
baseadas em splines

Filtros passa-baixa borram as letras,
eliminando pimples, pequenos buracos e
imperfeições. Técnicas para diminuição do
custo computacional são necessárias
23
DIM102
Álgebra de Formas
24
DIM102

Decomposição de
formas em regiões
retangulares disjuntas

Estrutura de dados
armazena os spans

Facilmente
combinadas usandose operações
Booleanas (importante
em Geometria
Construtiva de Sólidos
- CSG)
Álgebra de Formas

Pode-se usar um algoritmo de conversão de
scans para criar formas de primitivas mais
complexas

Pode-se usar tabelas de arestas ativas para
armazenar os retângulos (neste caso linhas) que
compõem a forma
25
DIM102
Álgebra de Formas Interseções
26
DIM102

A interseção é
calculada buscandose por retângulos que
se sobrepõem

Checa-se por ordem:
as extensões das
formas em y, os
intervalos dos spans
em y e em x

Algoritmo pode ser
combinado com
preenchimento
Álgebra de Formas

Algumas primitivas não produzem formas
compactas (linhas inclinadas), então pode ser
vantajoso usar recorte analítico

Formas podem ficar fragmentadas após várias
operações, tornando-se necessário fazer uma
condensação de formas

Para acelerar o uso desta técnica é vantajoso
que se implemente rotinas de interseção-epreenchimento, eliminando-se a necessidade da
estrutura de dados mencionada anteriormente
27
DIM102