Desafio 5
FUNDAMENTOS DA COMPUTAÇÃO GRÁFICA
ALUNO: THIAGO RIBEIRO DA MOTTA
MATRÍCULA: 1512348
PERÍODO: 2015.1
Desafio 5 – Opposite e CHE table
1) Tendo como entrada o vetor que descreve a triangulacao, implemente um algoritmo linear
com o numero de triangulos (ou numero de arestas e vertices) para construir a tabela de
opposites (O) da Corner Table.
Dica: Use o vetor de triangulacao para construir uma lista de adjacencia de vertices para corner.
Alem disso, lembre-se que o vetor de triangulacao funciona como um conversor de vertice para
corner.
2) Altera o algoritmo de 1) para construir a tabela de opposites (O) da CHE.
O programa deve ler um arquivo de entrada e escrever um arquivo de saida com o vetor de
opposites.
1. Opposite Table
5
13
10
9
Tc (Tabela de Corner) =
0
{ {0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}, {5, 3},
0
{6, 7}, {7, 8}, {8, 6}, {9, 10}, {10, 11}, {11, 9},
{12, 13}, {13, 14}, {14, 12}, {15, 16}, {16, 17}, {17, 15} }
11
6 14
17
12 1 1
16 8 3
2 2
5
Aresta
Tv (Tabela de Vértices) =
{ {0, 1}, {1, 2}, {2, 0}, {1, 4}, {4, 2}, {2, 1},
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
{3, 4}, {4, 1}, {1, 3}, {0, 5}, {5, 1}, {1, 0},
7 4
4
0, 5, 1,
{1, 5}, {5, 6}, {6, 1}, {3, 1}, {1, 6}, {6, 3} }
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
1. Opposite Table
5
13
10
9
Implementado
como um dicionário { {0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}, {5, 3},
com pesquisa por
{6, 7}, {7, 8}, {8, 6}, {9, 10}, {10, 11}, {11, 9},
Aresta ( in = Aresta,
out = Indice)
{12, 13}, {13, 14}, {14, 12}, {15, 16}, {16, 17}, {17, 15} }
0
11
12 1 1
16 8 3
6 14
17
Tc (Tabela de Corner) =
0
2 2
5
Aresta
Tv (Tabela de Vértices) =
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
7 4
4
Implementado como
{ {0, 1}, {1, 2}, {2, 0}, {1, 4}, {4, 2}, {2, 1},
um dicionário com
pesquisa por Indice {3, 4}, {4, 1}, {1, 3}, {0, 5}, {5, 1}, {1, 0},
(in = Indice, out =
{1, 5}, {5, 6}, {6, 1}, {3, 1}, {1, 6}, {6, 3} }
aresta)
0, 5, 1,
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
1. Opposite Table
5
13
10
9
Para cada corner c
0
◦ Se visitado[c] for false
0
◦ n = Next(c)
◦ n1 = Next(n)
◦ eVolta = Tv[ V[n1], V[n] ]
11
12 1 1
16 8 3
6 14
17
◦ Se eVolta for null
2 2
5
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].y
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
◦ p = Next(m)
7 4
◦ Se V[c] != V[p] ou V[n] != V[m]
4
0, 5, 1,
◦ O[c] = p
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
◦ O[p] = c
◦ Visitado[c] = true
◦ Visitado[p] = true
1. Opposite Table
5
13
10
9
0
15
Execução
0
◦ Se visitado[c] for false
c = 0 n = 1 n1 = 2
V[n1] = V[2] = 2
V[n] = V[1] = 1
2 2 eVolta = Tv[2,1] = 5
11
12 1 1
16 8 3
6 14
17
Para cada corner c
5
Tv (Tabela de Vértices) =
{ {0, 1}, {1, 2}, {2, 0}, {1, 4},
{4, 2}, {2, 1}, ...
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
7 4
◦ n1 = Next(n)
◦ eVolta = Tv[ V[n1], V[n] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].y
◦ p = Next(m)
◦ Se V[c] != V[p] ou V[n] != V[m]
4
0, 5, 1,
◦ n = Next(c)
◦ O[c] = p
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
◦ O[p] = c
◦ Visitado[c] = true
◦ Visitado[p] = true
1. Opposite Table
5
13
10
9
0
15
Execução
0
◦ Se visitado[c] for false
eVolta = 5
m = Tc[5].y
m = {5,3}.y = 3
2 2 p=4
11
12 1 1
16 8 3
6 14
17
Para cada corner c
5
Tc (Tabela de Corner) =
{ {0, 1}, {1, 2}, {2, 0}, {3, 4},
{4, 5}, {5, 3}, ...
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
7 4
◦ n1 = Next(n)
◦ eVolta = Tv[ V[n1], V[n] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].y
◦ p = Next(m)
◦ Se V[c] != V[p] ou V[n] != V[m]
4
0, 5, 1,
◦ n = Next(c)
◦ O[c] = p
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
◦ O[p] = c
◦ Visitado[c] = true
◦ Visitado[p] = true
1. Opposite Table
5
13
10
9
0
Execução
0
◦ Se visitado[c] for false
p=4
O[0] = 4
O[4] = 0
2 2 Visitado[0] = true
5
Visitado[4] = true
11
12 1 1
16 8 3
6 14
17
Para cada corner c
◦ n = Next(c)
◦ n1 = Next(n)
◦ eVolta = Tv[ V[n1], V[n] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].y
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
◦ p = Next(m)
7 4
◦ Se V[c] != V[p] ou V[n] != V[m]
4
0, 5, 1,
◦ O[c] = p
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
◦ O[p] = c
◦ Visitado[c] = true
◦ Visitado[p] = true
1. Opposite Table
5
13
10
9
0
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
Execução
0
11
12 1 1
16 8 3
6 14
17
7 4
4
Para cada corner c
◦ Se visitado[c] for false
c = 1 n = 2 n1 = 0
V[n1] = V[0] = 0
V[n] = V[2] = 2
2 2 eVolta = Tv[0,2] = null
5
Tv (Tabela de Vértices) =
{ {0, 1}, {1, 2}, {2, 0}, {1, 4},
{4, 2}, {2, 1}, {3, 4}, {4, 1},
{1, 3}, {0, 5}, {5, 1}, {1, 0},
{1, 5}, {5, 6}, {6, 1}, {3, 1},
{1, 6}, {6, 3} }
0, 5, 1,
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
◦ n = Next(c)
◦ n1 = Next(n)
◦ eVolta = Tv[ V[n1], V[n] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].y
◦ p = Next(m)
◦ Se V[c] != V[p] ou V[n] != V[m]
◦ O[c] = p
◦ O[p] = c
◦ Visitado[c] = true
◦ Visitado[p] = true
1. Opposite Table
5
13
10
9
0
15
Execução
0
◦ Se visitado[c] for false
c = 1 n = 2 n1 = 0
V[n1] = V[0] = 0
V[n] = V[2] = 2
2 2 eVolta = Tv[0,2] = null
11
12 1 1
16 8 3
6 14
17
Para cada corner c
5
Não existe uma aresta que
comece no Vértice 0 e vá
para o Vértice 2.
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
7 4
◦ n1 = Next(n)
◦ eVolta = Tv[ V[n1], V[n] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].y
◦ p = Next(m)
◦ Se V[c] != V[p] ou V[n] != V[m]
4
0, 5, 1,
◦ n = Next(c)
◦ O[c] = p
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
◦ O[p] = c
◦ Visitado[c] = true
◦ Visitado[p] = true
1. Opposite Table
5
13
10
9
0
Execução
0
◦ Se visitado[c] for false
eVolta = null
O[1] = -1
Visitado[1] = true
11
12 1 1
16 8 3
6 14
17
Para cada corner c
2 2
5
◦ n = Next(c)
◦ n1 = Next(n)
◦ eVolta = Tv[ V[n1], V[n] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].y
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
◦ p = Next(m)
7 4
◦ Se V[c] != V[p] ou V[n] != V[m]
4
0, 5, 1,
◦ O[c] = p
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
◦ O[p] = c
◦ Visitado[c] = true
◦ Visitado[p] = true
2. Compact Half-Edge (CHE) Table
5
13
10
9
Para cada corner c
0
◦ Se visitado[c] for false
0
◦ n = Next(c)
◦ n1 = Next(n)
◦ eVolta = Tv[ V[n1], V[n] ]
11
12 1 1
16 8 3
6 14
17
◦ Se eVolta for null
2 2
5
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].x
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
◦ O[c] = m
7 4
◦ O[m] = c
4
0, 5, 1,
◦ Visitado[c] = true
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
◦ Visitado[m] = true
2. Compact Half-Edge (CHE) Table
Opposite Table
Para cada corner c
◦ Se visitado[c] for false
◦
◦
◦
◦
n = Next(c)
n1 = Next(n)
eVolta = Tv[ V[n1], V[n] ]
Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].y
◦ p = Next(m)
◦ Se V[c] != V[p] ou V[n] != V[m]
◦ O[c] = p
◦ O[p] = c
◦ Visitado[c] = true
◦ Visitado[p] = true
Compact Half-Edge (CHE) Table
Para cada corner c
◦ Se visitado[c] for false
◦ n = Next(c)
◦ eVolta = Tv[ V[n], V[c] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].x
◦ O[c] = m
◦ O[m] = c
◦ Visitado[c] = true
◦ Visitado[m] = true
2. Compact Half-Edge (CHE) Table
Opposite Table
Para cada corner c
◦ Se visitado[c] for false
◦
◦
◦
◦
n = Next(c)
n1 = Next(n)
eVolta = Tv[ V[n1], V[n] ]
Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].y
◦ p = Next(m)
◦ Se V[c] != V[p] ou V[n] != V[m]
◦ O[c] = p
◦ O[p] = c
◦ Visitado[c] = true
◦ Visitado[p] = true
Compact Half-Edge (CHE) Table
Para cada corner c
◦ Se visitado[c] for false
◦ n = Next(c)
◦ eVolta = Tv[ V[n], V[c] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].x
◦ O[c] = m
◦ O[m] = c
◦ Visitado[c] = true
◦ Visitado[m] = true
2. Compact Half-Edge (CHE) Table
5
13
10
9
0
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
Execução
0
◦ Se visitado[c] for false
c=0 n=1
V[n1] = V[1] = 1
V[n] = V[0] = 0
2 2 eVolta = Tv[1,0] = 11
11
12 1 1
16 8 3
6 14
17
Para cada corner c
5
7 4
◦ eVolta = Tv[ V[n], V[c] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
Tv (Tabela de Vértices) =
{ {0, 1}, {1, 2}, {2, 0}, {1, 4},
{4, 2}, {2, 1}, {3, 4}, {4, 1},
{1, 3}, {0, 5}, {5, 1}, {1, 0}, ...
4
0, 5, 1,
◦ n = Next(c)
◦ m = Tc[eVolta].x
◦ O[c] = m
◦ O[m] = c
◦ Visitado[c] = true
◦ Visitado[m] = true
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
2. Compact Half-Edge (CHE) Table
5
13
10
9
0
Para cada corner c
Execução
0
◦ Se visitado[c] for false
eVolta = 11
m = Tc[11].x = 11
11
12 1 1
16 8 3
6 14
17
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
4
0, 5, 1,
◦ eVolta = Tv[ V[n], V[c] ]
◦ Se eVolta for null
◦ O[c] = -1
2 2
5
7 4
◦ n = Next(c)
◦ Visitado[c] = true
◦ Senão
Tc (Tabela de Corner) =
◦
{ {0, 1}, {1, 2}, {2, 0}, {3, 4},
◦
{4, 5}, {5, 3}, {6, 7}, {7, 8},
◦
{8, 6}, {9, 10}, {10, 11}, {11, 9}, ◦
...
◦
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
m = Tc[eVolta].x
O[c] = m
O[m] = c
Visitado[c] = true
Visitado[m] = true
2. Compact Half-Edge (CHE) Table
5
13
10
9
0
Execução
0
◦ Se visitado[c] for false
eVolta = 11
m = Tc[11].x = 11
O[0] = 11
2 2 O[11] = 0
5
Visitado[0] = true
Visitado[11] = true
11
12 1 1
16 8 3
6 14
17
Para cada corner c
◦ n = Next(c)
◦ eVolta = Tv[ V[n], V[c] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].x
◦ O[c] = m
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
◦ O[m] = c
7 4
◦ Visitado[c] = true
4
0, 5, 1,
◦ Visitado[m] = true
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
2. Compact Half-Edge (CHE) Table
5
13
10
9
0
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
Execução
0
11
12 1 1
16 8 3
6 14
17
7 4
4
Para cada corner c
◦ Se visitado[c] for false
c=2 n=0
V[n1] = V[0] = 0
V[n] = V[2] = 2
2 2 eVolta = Tv[0,2] = null
5
Tv (Tabela de Vértices) =
{ {0, 1}, {1, 2}, {2, 0}, {1, 4},
{4, 2}, {2, 1}, {3, 4}, {4, 1},
{1, 3}, {0, 5}, {5, 1}, {1, 0},
{1, 5}, {5, 6}, {6, 1}, {3, 1},
{1, 6}, {6, 3} }
0, 5, 1,
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
◦ n = Next(c)
◦ eVolta = Tv[ V[n], V[c] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].x
◦ O[c] = m
◦ O[m] = c
◦ Visitado[c] = true
◦ Visitado[m] = true
Pulei o exemplo
de c = 1 por ser
análogo ao
exemplo de c = 0
2. Compact Half-Edge (CHE) Table
5
13
10
9
0
15
Execução
0
◦ Se visitado[c] for false
c=2 n=0
V[n1] = V[0] = 0
V[n] = V[2] = 2
2 2 eVolta = Tv[0,2] = null
11
12 1 1
16 8 3
6 14
17
Para cada corner c
5
Não existe uma aresta que
comece no Vértice 0 e vá
para o Vértice 2.
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
7 4
◦ eVolta = Tv[ V[n], V[c] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].x
◦ O[c] = m
◦ O[m] = c
◦ Visitado[c] = true
4
0, 5, 1,
◦ n = Next(c)
◦ Visitado[m] = true
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
2. Compact Half-Edge (CHE) Table
5
13
10
9
0
Execução
0
◦ Se visitado[c] for false
eVolta = null
O[2] = -1
Visitado[2] = true
11
12 1 1
16 8 3
6 14
17
Para cada corner c
2 2
5
◦ n = Next(c)
◦ eVolta = Tv[ V[n], V[c] ]
◦ Se eVolta for null
◦ O[c] = -1
◦ Visitado[c] = true
◦ Senão
◦ m = Tc[eVolta].x
◦ O[c] = m
15
6
3
V = 0, 1, 2, 1, 4, 2, 3, 4, 1,
◦ O[m] = c
7 4
◦ Visitado[c] = true
4
0, 5, 1,
◦ Visitado[m] = true
1, 5, 6,
3, 1, 6
C = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17