Representação Geométrica
Rodrigo de Toledo
(CG1, UFRJ, 2010.2)
Níveis de escala
Aqui
Cena
Meso
• Objetos do mundo virtual
• Textura
Macro
Microscale
• Representação dos objetos
• Nível fotométrico
Representação da geometria
• Implícita
– Equação determina a descrição geométrica
– Ex: quádricas, cúbicas e torus
• Paramétrica
– Função determina regra de construção
– Ex: Bézier, Nurbs
• Explícita
– A geometria é descrita “ponto-a-ponto”
– Ex: malha de triângulo e mapa de alturas
Representação Geométrica
Implícita
• Quádricas, cúbicas, etc...
• CSG
Exemplo: círculo
Representação Implícita:
Representação Paramétrica:
Representação Explícita:
Superfícies implícitas
f 0
• superfícies implícitas são
definidas por uma função
f:
R3R
• A função divide o espaço
em três:
surperfíce: f(x,y,z)  0
interior: f(x,y,z) < 0
exterior: f(x,y,z) > 0
f 0
f 0
Classificação das superfícies
implícitas
• O grau da polinomial da função é que
define o grau da superfície.
– Grau 2: quádricas
– Grau 3: cúbicas
– Grau 4: quárticas
• A quantidade de parâmetros S para cada
grau p pode ser calculada usando:
Quádricas
– Quádricas:
Esfera: x2 + y2 + z2 = 1
Representação matricial das
quádricas
• Matriz simétrica Q4x4 contendo os 10
coeficientes:
Classificação das quádricas
spheres
ellipsoids
cones
cylinders
hyperboloids
• Para entender a nomenclatura 3D,
primeiro vamos ver a nomenclatura 2D...
Curvas em 2D
Classificação das Quádricas
Saddle
Cela do cavalo
• vide wikepedia
Cúbicas
Quárticas
• Torus é a quártica mais conhecida:
Qual a complexidade da equação
do coração?
f(x,y,z) = (2x2 + y2 + z2 – 1)3 – 0.1 x2 z3 – y2 z3
Cálculo da normal à superfície
• Gradiente da superfície no ponto x,y,z
• Qual é a normal de uma quádrica?
• Qual é a normal normalizada do ponto
[x,y,z] numa esfera de raio unitário?
CSG
(Constructive Solid Geometry)
CSG
• Operações booleanas
Diferença
União
Interseção
A diferença
não é comutativa
CSG
• Objeto é representado por uma
árvore
– Operadores em nós internos
– Primitivas simples nas folhas
– Combinação bottom-up
• Obs:
– Como há operações não
comutativas, as arestas são
ordenadas
– Pode haver nós de transformação:
rotação, translação e escala...
Half-spaces
• Alguns sistemas CSG, além de primitivas
sólidas, também fazem uso de half-spaces, ou
seja, planos que dividem o espaço em dois
• Como definir um cubo a partir de half-spaces?
– 6 half-spaces
• Vantagem:
– Para se fazer um corte, não precisa usar um objeto
com vários lados.
• Desvantagem:
– Problema de validação:
• nem toda combinação pode resultar em um objeto válido
• (talvez só faça sentido usar para subtração)
CSG & raytracing
Um objeto em CSG
é comumente
descrito por
combinações de
objetos implícitos,
cujos cálculos de
interseção com a
reta são conhecidos,
tornando o
raytracing de objetos
CSG uma extensão
natural.
CSG & raytracing
• Realizar operações booleanas com sólidos nem
sempre é uma operação fácil
• É mais fácil interpretar o que acontece com um
raio atravessando esse sólido.
– redução do problema a cálculos em intervalos 1D
Goldstein and Nagel, “3-D Visual Simulation”, Simulation, January 1971.
CSG 1D
A
A:
B:
A  B:
B
AB
CSG 1D
A:
B:
A  B:
A  B:
A – B:
B – A:
A–B
AB
B–A
CSG 1D
• Classificação in/out por região:
A
B
AB
AB
A–B
B–A
in
in
in
in
out
out
in
out
in
out
in
out
out
in
in
out
out
in
out
out
out
out
out out
Exercício: Preencher a tabela acima!
CSG & Rasterização
• Também é possível visualizar sólidos
CSG com rasterização
• Ordenação a posteriori dos fragmentos
(pixels de cada primitiva)
• Vide:
– Rossignac and Requicha, “Depth-buffering
Display Techniques for Constructive Solid
Geometry”, CG & A, September 1986.
Algumas questões
• A ordem na árvore tem importância?
– Sim, verticalmente e horizontalmente (dif.).
• Existe uma representação única, dado um
objeto final e suas primitivas?
– Não
• A árvore tem que ser binária?
– Os nós de união e interseção poderiam ter
mais de um filho, mas diferença é sempre
entre dois filhos.
Possíveis questões de prova
Monte a árvore CSG deste sólido, sabendo
que as folhas são 2 cilindros e 1 esfera
Monte a árvore CSG deste sólido e
desenhe o que acontece com o raio r
ao longo do seu caminho para cada nó
da árvore à raíz.
in
out
Representação Geométrica
Paramétrica
• Curvas paramétricas cúbicas
– Introdução
– Continuidade
– Algoritmo de De Casteljau
– Hermite, Bézier e Splines (B-Splines e Nurbs)
• Superfícies paramétricas bicúbicas
– Bézier...
http://www.cin.ufpe.br/~marcelow/Marcelow/Ensino.html
Curvas Paramétricas Cúbicas
• Por que paramétricas?
– são descritas em t
• f(t), 0 ≤ t ≤ 1
1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
t = 0.0
Por que cúbicas?
• Grau 3:
• Por que não <3?
– Pouca flexibilidade
• Por que não >3?
– Computacionalmente caro
– “Franjas” indesejáveis (unwanted wiggles)
• Por que 3?
– Controle suave (derivadas) da curva passando em dois pontos
– Menor grau de curva em 3D
Paramétricas
• Por que não f(x), ao invés de f(t)?
f(x)
x
• Mas como representar esses casos?
Uma função para cada dimensão
Q(t )  x(t )
y(t ) z(t )
Matricialmente
ax
bx
C
 cx

dx
az
bz
cz 

dz
ay
by
cy
dy


T  t3 t2 t 1
Q(t )  x(t )
y(t ) z(t )  T  C
• Derivada em t ?
d
Q(t )
dt
3a t
x
2
 2bxt  cx 3ayt 2  2byt  cy 3azt 2  2bzt  cz

Algoritmo de De Casteljau
Interpolação x Aproximação
John Edson R. de Carvalho
Algoritmo de De Casteljau
P1
P12 (u)
u = 0.25
P01 (u)
P0
P02 (u)
P2
Algoritmo de De Casteljau
P1
u = 0.5
P02 (u)
P12 (u)
P01 (u)
P0
P2
Algoritmo de De Casteljau
P1
P01 (u)
u = 0.75
P02 (u)
P0
P12 (u)
P2
Algoritmo de De Casteljau
P1
0≥u≥1
P02(u)
P0
P2
∑bi(u) = 1,
0≥u≥1
Juntando curvas
• Como representar uma curva grande?
• Poderia se usar uma curva de grau n
(n grande para caramba )
• Ou, pode-se fazer emendas de cúbicas
– Mas nesse caso, queremos garantir uma boa
continuidade no ponto de junção
Continuidade
• Geometric Continuity G0
– Duas curvas tem um ponto de junção
• G1
– Se no ponto de junção, a direção (não necessariamente a
magnitude) do vetor tangente é igual para as duas curvas
• C1
– Se, além da direção, a magnitude for igual.
• C2
– Se a direção e magnitude da derivada segunda for igual.
• Cn
dn
Q(t ) for igual.
– Se a direção e magnitude de
n
dt
• Para funções de grau alto, pode-se ter continuidade
de grau ainda maior: n-polinomial  Cn-1
• Existe G2? Existe C0?
Classificação das curvas
• Definidas por 4 constrains geométricas
– Bézier (4 pontos)
– Hermite (2 pontos e 2 tangentes)
• Splines
– São C1 e C2 nos pontos de junção
– Porém, não interpolam os pontos (aproximam)
– 3 tipos:
• B-splines
• Nonuniform B-splines (Nurbs)
• β-splines
Blending Function
• Matricialmente, podemos definir a curva como:
Q(t )  x(t )
y(t ) z(t )  T  C
• Vamos reescrever C como o resultado da multiplicação
entre M e G, onde G são as constrains geométricas
Q(t )  x(t )

y(t ) z(t )  t
3
t
2
 m11
m
21
t 1 
m31

m41

• Blending Function: B = T • M
m12
m22
m32
m42
m13
m23
m33
m43
m14 
m24 
m34 

m44 
 G1x
G
 2x
G3 x

G4 x
G1 y
G2 y
G3 y
G4 y
G1z 
G2 z 
G3 z 

G4 z 
Bézier
• 70’s
• Como vimos no algoritmo de De Casteljau para
construção de curvas de Bézier
– 4 pontos definem a curva de Bézier
P1
P3
P0
P2
– No caso acima, quem são G1, G2, G3 e G4?
t
3
t
2
 m11
m
 21
m31
t 1 m41

m12
m22
m32
m42
m13
m23
m33
m43
m14 
m24 
m34 

m44 
 G1x
G
 2x
G3 x

G4 x
G1 y
G2 y
G3 y
G4 y
G1z 
G2 z 
G3 z 

G4 z 
Bézier
• No caso de Bézier, quais são os valores de M11 a M44?
Q(t )  t 3 t 2
 m11
m
21
t 1 
m31

m41

m12
m22
m32
m42
m13
m23
m33
m43
m14 
m24 
m34 

m44 
 P0 
P 
 1
 P2 
 
 P3 
Q(t )  (1  t )3 P0  3t (1  t )2 P1  3t 2 (1  t )P2  t 3 P3
Lembrando que: (a-b)3 = a3 – 3a2b + 3ab2 – b3
 1 3  3
 3 6 3

 3 3
0

0
0
1
1
0
0

0
e (a-b)2 = a2 – 2ab + b2
Últimas observações Bézier
• Fecho convexo
• Continuidade G1: pontos colineares
• E para ter
continuidade C1?
Hermite
• 4 constrains geométricos:
– 2 pontos e suas 2 tangentes:
R1
P4
P1
R4
 P1 
P 
GH   4 
 R1 
 
 R4 
1
 2 2 1
 3 3  2  1

MH  
0
0
1
0


1
0
0
0


Hermite
• Hermite Blending Function
• Familia de curvas alterando
magnitude e direção de R1
Splines
• Origem: “ducks” usados para retorcer uma chapa de metal
flexível (spline) na determinação de superfícies curvas para
navios, aviões e carros.
• Observe que a spline interpola todos os pontos de controle
• A spline é contínua em C0, C1 e C2.
B-splines
• Splines tem duas desvantagens:
– Os coeficientes dependem de todos os pontos de controle
• ou seja, mover um ponto de controle pode afetar toda a curva
– A computação depende de inversão de matrizes
• B-splines são uma solução:
–
–
–
–
Os segmentos dependem de alguns poucos pontos de controle
Tem a mesma continuidade das splines
Menor computação
Porém: não interpolam todos os pontos
• Uniforme x não-uniforme
– Se os pontos de controles estiverem equidistantemente
distribuídos, então ela é uniforme
– Caso contrário: não uniforme: NURBS
Superfícies paramétricas
Superfícies paramétricas bicúbicas
• Multiplicação de duas curvas
• A informação geométrica que define uma
curva é também em função de uma
variável paramétrica
• Forma geral de uma superfície 3D:
Superfícies paramétricas bicúbicas
• Vimos que um curva cúbica pode ser definida por (onde G é o vetor
geométrico): Q(t )  T  M  G
• Substituindo t por s (temos que ter outra variável para o caso das
Q( s )  S  M  G
• Imaginemos os pontos em G variando em 3D, parametrizado por t:
 G1 (t ) 
G (t )
Q( s, t )  S  M  G (t )  S  M   2 
G3 (t ) 


G
(
t
)
 4 
superfícies), então:
• Se Gi(t) forem cúbicos, então Q(s,t) é uma superfície paramétrica
bicúbica
• Cada Gi(t) = T•M•G, é definido por Gi = [gi1, gi2, gi3, gi4]T
• Usando (ABC)T= CT • BT • AT,
• Gi(t) = GT•MT•TT = [gi1, gi2, gi3, gi4]T •MT •TT,
• Então:
• Escrito separadamente:
Superfícies de Bèzier
Retalhos de Bézier
• Curvas na fronteira são curvas de Bézier
• Qualquer curva para s ou t constante é uma curva Bézier
• Podemos pensar assim:
– Cada linha da grade com 4 pontos de controle define uma curva de
Bézier para o parâmetro s
– Ao avaliar cada curva para um mesmo s obtemos 4 pontos de controle
“virtuais”
– Pontos de controle “virtuais” definem uma curva Bézier em t
– Avaliando esta curva em um dado t resulta no ponto x(s,t)
x(s,t)
Propriedades dos Retalhos de
Bézier
• O retalho interpola os pontos dos cantos da grade de
controle
– Decorre das propriedades análogas das curvas de Bézier
• O plano tangente em um ponto do canto é dado pelas
duas arestas da grade incidentes no ponto
– Decorre do fato que as curvas Bézier das fronteiras incidentes
têm tangentes definidas pelas arestas correspondentes
• O retalho é restrito ao fecho convexo da grade de
controle
– As funções de base somam 1 e são positivas em toda parte
Retalhos Bézier em Forma
Matricial
x( s, t )  S T BT PBT

x ( s, t )  s 3
s2
 1 3  3
 3 6 3
s 1
 3 3
0

0
0
1
1  P0, 0

0  P1, 0
0  P2, 0

0  P3, 0

P0,1
P1,1
P2,1
P3,1
P0, 2
P1, 2
P2, 2
P3, 2
P0,3    1 3  3
P1,3   3  6 3

P2,3   3 3
0

P3,3   1
0
0
1  t 3 
 
0 t 2 
0  t 
 
0  1 
• Se os pontos de controle não se modificam,
pode-se pré-computar o produto das 3
matrizes do meio:

x ( s, t )  s
3
s
2
 M 0, 0
M
1, 0
s 1
 M 2, 0

 M 3, 0

M 0,1
M 0, 2
M 1,1
M 1, 2
M 2,1
M 2, 2
M 3,1
M 3, 2
M 0 , 3  t 3 
M 1,3  t 2 
M 2,3   t 
 
M 3,3   1 
Malhas de Retalhos Bézier
• São malhas compostas de diversos retalhos
unidos ao longo de suas fronteiras
– As arestas das grades de controle precisam se
justapor perfeitamente
– As grades precisam ser quadriláteros
OK
Não
OK
Não
Continuidade em Malhas de
Retalhos Bézier
• Como no caso das curvas Bézier, os pontos de controle
precisam satisfazer restrições para assegurar
continuidade paramétrica
• Continuidade ao longo das arestas dos retalhos:
– C0 → Pontos de controle da aresta são os mesmos em ambos
retalhos
– C1 → Pontos de controle vizinhos aos da aresta têm que ser
colineares e eqüidistantes
– C2 → Restrições sobre pontos de controle mais distantes da
aresta
• Para obter continuidade geométrica, as restrições são
menos rígidas
– G1 → Pontos de controle vizinhos aos da aresta têm que ser
colineares mas não precisam ser eqüidistantes
• Para obter continuidade C1 nos vértices das grades
– Todas as arestas incidentes no ponto têm que ser colineares
Desenhando Retalhos Bézier
• Opção 1: Avaliar o retalho para um conjunto de
pontos do domínio paramétrico e triangular
– Normalmente, s e t são tomados em intervalos
(regulares ou não) de forma que os pontos avaliados
formam uma grade
– Cada célula da grade é constituída de quatro pontos
que vão gerar 2 triângulos
– Não se usa quadriláteros visto que os pontos não são
necessariamente co-planares
– Renderização fácil com triangle strips
– Vantagem: Simples e suportado pelo OpenGL
– Desvantagem: Não há uma maneira fácil de controlar
o aspecto da superfície de forma adaptativa
Desenhando Retalhos Bézier
• Opção 2: Usar subdivisão
– Permite controle de erro durante a aproximação
– Definida de forma semelhante à subdivisão de curvas
Bézier, mas refinamento é feito de forma alternada
nos dois eixos de parâmetros
– Sucessivamente computar pontos médios dos
vértices e uní-los
• Aplicar procedimento inicialmente em cada linha da grade de
controle: 4x4 → 4x7
• Repetir procedimento para cada coluna da grade de
controle: 4x7 → 7x7
Procedimento Adaptativo
• Através da subdivisão obtemos 4 grades de controle e testamos:
– Se a grade é aproximadamente plana, ela é desenhada
– Senão, subdividir em 4 sub-grades e aplicar o procedimento
recursivamente
• Problema: Retalhos vizinhos podem não ser subdivididos
uniformemente
– Rachaduras: polígonos de controle não se justapõem
– Pode ser consertado forçando grades mais subdivididas a se
justaporem às grades menos subdivididas ao longo da aresta comum
Rachadura
Normal
• Como calcular a normal de uma superfície
paramétrica Q(s,t) no ponto s=α e t=β ?
t=β
s=α
Computando o Vetor Normal
• Derivadas parciais em relação a t e a s
pertencem ao plano tangente
• Vetor normal é calculado normalizando o
produto cruzado de ambas
n m
dBin m
x
  Pi , j
B j t 
s s ,t i 0 j 0
ds s
x
x
n

s s ,t t s ,t
n m
dBj
x
n
  Pi , j Bi s 
t s ,t i 0 j 0
dt
m
nˆ 
n
n
t
Exemplos de outras
superfícies paramétricas
• Superfícies criadas por rotação
de um curva em torno de um
eixo
• Knots: movimentação de um
círculo no espaço
– Exemplo: Trefoil Knot
Representação Geométrica
Explícita
Referências das transparências:
– Prof. Paulo Roma
– Prof. Thomas Ottmann e Khaireel A. Mohamed
–
Paradigma dos quatro universos.
• Objetos do universo físico: “sólidos” (formas)
• Universo matemático, descrição:
– Implícita x Paramétrica x Explícita
• Explicitamente, exemplos de representação:
mapa de
altura
por bordo
(superfícies poliédricas)
por volume
(voxles)
Representação explícita por bordo
(superfícies poliédricas)
• Qualquer poliedro convexo pode ser
representado por uma subdivisão planar
(representação linear por partes)
– Malha de polígonos (ou malha de triângulos)
Representação Linear por Partes
• Superfície com geometria complexa pode ser
aproximada por uma superfície linear por partes.
• Particiona-se o domínio da parametrização por
um conjunto de polígonos.
– Cada vértice no domínio poligonal é levado para a
superfície pela parametrização.
– A conectividade entre vértices adjacentes se mantem.
Propriedades
• Gera uma malha poligonal, definida por um
conjunto de vértices, arestas e faces.
– Cada aresta é compartilhada por no máximo duas
faces.
– A interseção de duas faces é uma aresta, um vértice
ou vazia.
• Relação de Euler
F+V=A+2
• Adjacência de vértices, arestas e faces é
chamada de topologia da superfície.
Relação de Euler
• F+V=A+2
(Foi Você que Assassinou o 2)
– Existe uma face externa
• F + V = A + 2s
• s é a quantidade de bordas da
malha (depende do genus do
objeto)
– O genus do objeto depende da
quantidade de “alças” (handles)
g=0
g=1
g=2
Geometria x Topologia
• Dois objetos com a mesma geometria
podem ter topologias diferentes
• Dois objetos com a mesma topologia
podem ter geometrias diferentes
• Vamos nos concentrar na topologia!
– Problema em 2D
Manifold
• Uma superfície é 2-manifold se em todo o seu
domínio ela for localmente homeomorfa a um
disco
manifold
non-manifold edge
Non-manifold vertex
Subdivisão Planar
• Como representar (codificar)?
– lista de vértices e arestas, ou
– lista de vértices e faces,
– Winged edge ou Half edge ou ...
• Operações sobre Malhas Poligonais
–
–
–
–
Achar todas as arestas que incidem em um vértice.
Achar as faces que incidem numa aresta ou vértice.
Achar as arestas na fronteira de uma face
As 9 perguntas devem ser respondidas em tempo ótimo!
9 tipos de Relacionamentos de
Adjacência
Codificação
•
•
•
•
•
•
•
Explícita.
Ponteiros para lista de vértices.
Ponteiros para lista de arestas.
Winged-Edge (Half-Edge, Face-Edge).
Quad-Edge (Guibas-Stolfi).
Radial-Edge.
Half-Edge.
Sugestões?
Codificação Explícita
• A mais simples.
• Cada face armazena explicitamente a lista
ordenada das coordenadas dos seus vértices:
P  ( x1 , y1 , z1 ), ( x2 , y2 , z 2 ),...,( xn , yn , zn )
• Muita redundância de informação.
• Consultas são complicadas.
– Obriga a execução de algoritmos geométricos para
determinar adjacências.
Desenho da Malha
• Cada aresta é
desenhada duas
vezes, pelos duas
faces que a
compartilham.
• Não é bom para
plotadoras ou filmes.
Ponteiros para Lista de Vértices
• Vértices são armazenados
separadamente.
• Há uma lista de vértices.
• Faces referenciam seus vértices através
de ponteiros.
• Proporciona maior economia de memória.
• Achar adjacências ainda é complicado.
• Arestas ainda são desenhadas duas
vezes.
Exemplo
Ponteiros para Lista de Arestas
• Há também uma lista de arestas.
• Faces referenciam as suas arestas
através de ponteiros.
• Arestas são desenhadas percorrendo-se a
lista de arestas.
• Introduzem-se referências para as duas
faces que compartilham uma aresta.
– Facilita a determinação das duas faces
incidentes na aresta.
Exemplo
Outra linha de solução...
• DCEL: Doubly-Connected Edge List
– winged-edge
– radial-edge
– half-edge
Winged-Edge
Winged-Edge
• Criada em 1974 por Baumgart.
• Foi um marco na representação por fronteira.
• Armazena informação na estrutura associada às
arestas (número de campos é fixo).
• Todos os 9 tipos de adjacência entre vértices,
arestas e faces são determinados em tempo
constante.
• Atualizada com o uso de operadores de Euler,
que garantem: V – A + F = 2.
• Porém, o tamanho da estrutura é: 3V + 8A + F
Face-Edge
Radial-Edge
• Criada em 1986 por Weiler.
• Representa objetos non-manifold (não
variedades).
• Armazena a lista ordenada de faces incidentes em
uma aresta.
• Muito mais complicada que a Winged-Edge.
Radial-Edge
Half-edge data structure
• A estrutura de dados de uma Half-edge deve
armazenar:
–
–
–
–
Ponteiro para a half-edge seguinte
Ponteiro para a half-edge oposta
Ponteiro para sua face
A reference to the vertex it points to
• Face data structure stores:
– A reference to an half-edge in the face
• Vertex data structure stores:
– A reference to the outgoing half-edge
Half-edge data structure
• Example:
7
6
4
5
3
1
9
2
10
3
1
he
0
1
2
Face list
f e
0 e0
1 e8
2 …
2
0
0
Vertex list
V coord
0 000
1 100
2 110
3 …..
8
11
Half-edge list
he to_vertex
0
1
1
2
2
3
3
0
next_he
1
2
3
0
opposite_he
6
11
15
18
face
0
0
0
0
Half-edge
• The half-edges in the DCEL that border a face, form a circular
linked-list around its perimeter (anti-clockwise); i.e. each half-edge
in the loop stores a pointer to the face it borders (incident).
• Each half-edge is directed and can be described in a Java class as
follows:
class H_Edge {
Vertex vOrig;
H_Edge eTwin;
Face f;
H_Edge eNext;
H_Edge ePrev;
f
H_Edge
vOrig
}
ePrev
eTwin
eNext
DCEL Component - Vertex
• A vertex in the DCEL stores:
– its actual location of the point on the plane, and
– a pointer to exactly ONE of the H_Edge, which uses this vertex as its
origin.
class Vertex {
Point2D p;
H_Edge hEdge;
}
hEdge
Vertex
p=(x,y)
• There may be several H_Edge which origins start at the same vertex.
We need only one, and it does not matter which one.
DCEL Component – Face
• A face component stores
– a reference to any one of the half-edges it borders
(the face’s outer-most boundary), and
– a set of references to half-edges of unique holes
inside the face.
class Face {
H_Edge eOuterComp;
List<H_Edge> eInnerComps;
}
eInnerComps[0]
Face
eOuterComp
DCEL Example: Planar Subdivision
v11
15
14
v9
13
v8
f3
12
v10
f4
11
v7
10
v6
9
f2
8
7
v5
v4
6
v3
5
f1
4
3
2
v1
1
0
v2
0
1
2
3
4
5
6
7
8
9 10 11
Vertex
p
v1
(1,1)
v2
(10,0)
v3
(9,5)
v4
(2,7)
v5
(5,8)
v6
(8,9)
v7
(5,11)
v8
(7,13)
v9
(1,13)
v10
(11,12)
v11
(6,15)
hEdge
e1_3
e2_3
e3_4
e4_9
e5_9
e6_7
e7_8
e8_6
e9_11
DCEL Example: Planar Subdivision
Half-Edge
e1_3
14
e3_1
v9
v8
13
v10
e2_3
f3
12
e3_2
f4
11
v7
e10_3
10
e11_10
v6
9
f2 v5
e9_11
8
e4_9
7
v4
e3_4
6
e4_3
v3
5
f1
e9_4
4
e5_9
3
e3_5
2
v1
e5_3
1
v2
e9_5
0
0 1 2 3 4 5 6 7 8 9 10 11
e11_9
15
v11
vOrig
v1
eTwin
e3_1
f eNext
f1 e3_4
ePrev
e3_1
DCEL Example: Planar Subdivision
v11
15
14
v9
13
v8
f3
12
v10
f4
11
v7
10
v6
9
f2
8
7
v5
eTwin f eNext
e11_10 f3 e11_9
ePrev
e3_10
v4
6
v3
5
f1
4
3
2
v1
1
0
Half-Edge vOrig
e10_11 v10
e3_10
e6_7
e8_6
e7_8
e8_7
e7_6
e6_8
v2
0
1
2
3
4
5
6
7
8
9 10 11
Face eOuterComp
f1
NULL
f2
f3
f4
eInnerComps
e1_3
Adjacency Queries
• Given a half-edge e, we can perform queries in
constant time.
• Example:
Vertex v1
Vertex v2
Face f1 =
Face f2 =
= e . vOrig;
= e . eTwin . vOrig;
f1
e . f;
e . eTwin . f;
v1
v2
e
f2
Iterated Adjacency Queries
• Iterating over the half-edges adjacent to a given
face f.
H_Edge hEdge = f . eOuterComp;
do {
// Do something with edge.
hEdge = hEdge . eNext;
} while (
Iterated Adjacency Queries
• Iterating over the half-edges on a given vertex v.
H_Edge hEdge = v . hEdge;
do {
// Do something with edge.
hEdge = hEdge . eTwin . eNext;
} while (
Triângulos
• Muitos sistemas trabalham exclusivamente com
malhas de triângulos
• Por que triângulos?
• Algumas propriedades especiais:
– Vértices são sempre coplanares
– Sempre convexo
– Interpolação linear
(coordenadas baricêntricas)
– Qualquer malha de polígonos pode ser transformada
em malha de triângulos
– Especialidade das GPU’s
– Triângulo é sempre rígido (ex: Torre Eifel)
Outros Temas em
Geometria Computacional
• Interseção de segmento de linhas
• Localização de Ponto
– Em um polígono
– Em uma subdivisão planar
• Triangulação de Delaunay
– Delaunay (maximiza o menor ângulo de todos os triângulos)
• “gordura dos triângulos”
• Diagramas de Voronoi
– Mapa de localização de ponto mais próximo
– Grafo complementar ao Delaunay
•
•
•
•
Fecho Convexo 3D
Planejamento de Movimentação de Robôs
Grafos de Visibilidade
Árvores Espaciais
– Kd-Trees
– Quadtrees
– BSP (Binary Space Partition)