Operações em uma
subdivisão planar 2D
Rodrigo de Toledo
(CG1, UFRJ, 2011.1)
Viewport 2D
Exemplo:
(em pixels)
Umin = 0
Vmin = 0
Umax = 300
Vmax = 200
Exemplo:
(em coordenadas de mundo)
Xmin = -500
Ymin = 300
Xmax = 400
Ymax = 800
Como transformar?
Manter aspect ratio?
Viewport 2D
Viewport 2D
Ponto
P
?
• Percorrer sequencialmente os pontos
comparando a localização.
• Como tratar precisão?
– Margem (threshold)
– Distância euclidiana
Aresta
V2
V1
• P pertence a reta?
• P está entre V1 e V2?
P
?
Triângulo
V3
V1
P
?
P
?
V2
• Produto Vetorial de 2
• (v1xv2) = {x1y2 – y1x2}
• v1xv2 > 0, se e só se v2 está “a esquerda” de v1
Ponto no interior de um
triângulo (CW ou CCW)
t1  a12  ( P  V1 )
t2  a23  ( P  V2 )
V3
t3  a31  ( P  V3 )
a31
N
a23
Pi
V1
P é interior se t1, t2 e t3 tem o mesmo sentido,
ou seja:
a12
Pe
V2
t1  t2   0
t1  t3   0
Polígono convexo
V5
V4
V1
P
P
?
?
V3
V2
Pergunta se P está do mesmo lado de todas as arestas...
Polígono côncavo
V5
V6
P
V1
P
?
V2
?
V3
V4
Polígono côncavo
• Achar fecho convexo
• Verificar se OK para fecho convexo
– senão está fora
– Considerar área que não pertence ao fecho convexo
como polígono CW (sentido horário). Verificar se
dentro deste polígono
• senão está dentro
– Atenção:
• pode ser mais de um polígono...
• pode ser que o polígono também seja côncavo, tendo de
usar recursão nesse caso
Regra da paridade
(even-odd parity rule)
•Um ponto é considerado
dentro de um polígono se
uma raio vindo do infinito
cruzar um número par de
bordas!
Cuidado!
A
B
Como descobrir qual triângulo?
• Existe alguma outra maneira do que
percorrer todos os triângulos?
Rasterização de cor
• Truque usado em 3D
1. Chamar a função que
renderiza com cores no
“back-buffer”
2. Leia o pixel do back-buffer
correspondente a posição do
mouse-click.
3. Processe a cor para
descobrir qual o item que foi
clicado.
Obs: Cuidado para que não
apareça ao usuário o
esquema de cores.
Subdivisão do espaço
• Em 2D, o mais comum é quadtree
– dos vértices?
– das arestas?
– dos triângulos?
• Em 3D se chama octree
• Existem outras subdivisões mais inteligentes...
kD-tree
Em 3D
BSP (Binary Space Partition)