Operações em uma
subdivisão planar 2D
Rodrigo de Toledo
(CG1, UFRJ, 2010.2)
Esta versão deste ppt ainda não é a definitiva!
Plano de hoje
•
•
•
•
•
Feedback do trabalho passado
Passar o próximo trabalho
Formato de arquivo para descrição de malha (ply?)
Viewport 2D
Seleção de:
–
–
–
–
Ponto
Aresta
Triângulo
Polígono
• Outras formas de seleção:
– por cor
– por subdivisão espacial
What Went Well? (34)
•
•
•
•
Exercícios em aula (6)
Trabalhos interessantes (20)
Pontualidade (2)
Desenvolvimento ágil dos trabalhos (5)
– duplas etc...
•
•
Utilização de biblioteca já conhecida (Allegro)
Interação do prof.-turma (16)
– enche a turma devida a transparência
•
•
•
•
•
Material na internet (3)
Esquema de 8 pontos +2 extras (4)
A sequencia do conteúdo (14)
Aulas dinamicas (10)
Curiosidades fora do conteudo da materia (3)
– agile, petroleo, matrix
•
•
•
•
Decisoes tomadas com a turma (3)
Preocupacao do prof. com o ensino (2)
As aulas de laboratorio (6)
Monitor auxiliando o trabalho (8)
What Went Well? Rodrigo
•
•
•
•
Os ppts estão a 80% do que eu queria
Bastante alunos
Vários interessados
Trabalhos de proc img ficaram muito bons
– menor nota foi 6.3
•
•
•
•
Alguns feedbacks individuais positivos
A participação de alunos na criação do curso
O monitor bastante prestativo
Infra da UFRJ está dando conta do recado
– labs, projetor, salas, secretaria, minha sala...
• O horário é bom!
What can be improved?
•
Falta lista de exercicio (17)
–
•
•
•
•
•
•
Usar biblioteca OpenGL (4)
Marcar prova depois do feriado (2)
A prova pode ser mais fácil 
Exercicios para programar no papel (12)
Fazer maior uso do lab (12)
Cronograma deveria ser antecipado
–
•
•
•
•
•
•
•
•
desconfortável por pessoas diferentes corrigirem ((deixar claro a troca dos corretores))
tempo curto (4)
Aumentar peso do trabalho na nota
–
–
–
•
datas de trabalho / prova
Evitar coincidir provas
Não alternar com outro professor (4)
Atualizar o site mais rápido (2)
Deixar mais claro que pode ser feito em outras linguagens
Monitoria de programação
Mais teoria (2)
Bibliografia com indicações por assunto (no próprio slide)
Apresentação dos trabalhos
–
–
•
para preparar para a prova
como está agora (12)
aumentar o peso do trabalho (15)
o contrário (0)
Trabalho de modelagem também (7)
–
talvez uma aula extra....
What can be improved? Rodrigo
•
•
•
•
•
•
•
•
•
•
Preparação das aulas com mais antecedencia
Madrugadas em excesso
Mais reunioes com monitor
Dava para ser um pouco mais rápido
É provavel que não de para passar todo o conteudo
previsto
Não marquei data de prova com antecedencia
Na segunda é corrido (aula no H até as 10h)
Feriados + semana cientifica atrapalham
Um pouco de insegurança por ser a primeira vez
não sei lidar com alunos que dormem, se distraem e
saem
Trabalho 2
Faça um programa que leia um arquivo de entrada contendo a descrição de uma subdivisão
planar do espaço (malha de triângulos 2D). O programa deve:
Desenhar na tela essa malha (sugerimos o uso do Allegro, que tem comandos para
desenho de linha).
Permitir que o usuário selecione um vértice ou uma aresta ou um triângulo. Esse input não
é uma variação, todos os trabalhos devem permitir as 3 seleções.
Uma vez selecionado, mostrar a vizinhança do elemento selecionado segundo a variação
de trabalho da dupla. Variações de output:
oMostar os vértices vizinhos:
oMostrar as arestas vizinhas:
oMostrar os triângulos (polígonos) vizinhos:
Formato de arquivo de entrada:
oA ser definido pelo monitor (até segunda que vem).
oProvavelmente uma lista de vértices seguida de uma lista
de polígonos.
Mostrar na tela o resultado destacado.
Exemplos de algo mais:
oInterface do sistema de seleção caprichado.
oForma de destacar o resultado.
oZoom e/ou pan.
oPermitir malhas de polígonos (não apenas de triângulos).
oSistema topológico sofisticado (e bem implementado).
oImplementar as demais variações.
Formato de arquivo
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)