INTERPOLATING SUBDIVISION FOR
MESHES
WITH
ARBITRARY
TOPOLOGY [ZORIN ET. AL] –
SIGGRAPH’96
Rodrigo Braga Pinheiro
INTRODUÇÃO



A superfície a ser subdividida começa com uma
malha poligonal original, chamada de “gaiola de
controle”.
A partir daí a superfície é subdividida em
polígonos adicionais e seus vértices são movidos
de acordo com uma série de regras.
As regras variam de um esquema de subdivisão
para outro. Estas regras que determinam as
propriedades da superfície. Por exemplo:
Modified
Butterfly
(triângulos),
CatmullClark(quad).
CONTINUIDADE



Uma característica
continuidade.
cada
esquema
é
a
sua
Esquemas
são referenciados como tendo continuidade
n
. , onde n determina quantas derivadas são continuas.
C
C
0
significa que nenhuma derivada é continua. Esta
superfície não tem buracos na malha, mas pode
apresentar quinas.
1

de
C
significa que a 1a derivada é continua. Esta
superfície não tem buracos na malha e não gera quinas
quando duas funções se encontram.
CONTINUIDADE
Não tem continuidade
1
C
C
0
Se encontram e possuem
derivadas iguais no ponto p.
Se encontram, mas
derivadas diferentes
no ponto p.
APROXIMATIVO VS INTERPOLATIVO


No esquema aproximativo os vértices da gaiola de
controle não ficam em cima da superfície limite.
No esquema interpolativo os vértices já criados
no passo de subdivisão anterior são mantidos na
mesma posição.
UNIFORME VS NÃO-UNIFORME


Os esquemas uniformes dividem todas as áreas
da gaiola de controle usando as mesmas regras.
Os esquemas não-uniformes podem, por exemplo,
subdividir uma aresta de uma maneira e outra
aresta de outra maneira.
TRIANGULAR VS QUADRILÁTERO

Um esquema pode ter a característica de
trabalhar com malhas de triângulos ou de quads.
AVALIAÇÃO DA SUPERFÍCIE

Todo algoritmo de subdivisão possui como
característica uma “máscara de avaliação”. A
máscara define quais os vértices que deverão ser
levados em conta para deslocar um novo vértice
gerado em determinada subdivisão.
ESTACIONÁRIO VS NÃO-ESTACIONÁRIO


Se um esquema é estacionário, significa que o
mesmo grupo de regras é usado para subdividir a
malha em cada passo.
Um esquema não estacionário pode usar um
conjunto de regras para o passo i e um conjunto
diferente para o passo i + 1.
VÉRTICES REGULARES VS
EXTRAORDINÁRIOS


Cada esquema de subdivisão tem sua preferência para a valência de um
vértice. Ou seja, o criador do algoritmo de subdivisão define um número
considerado ideal para a quantidade de arestas que devem chegam a um
vértice.
Um vértice com a valência “preferida” é chamada de vértice regular. Ou seja, se
um vértice tem “n” arestas chegando nele e o número de valência escolhido pelo
criador for “n”, esse vértice é regular.

Um vértice com uma valência diferente da definida pelo criador é chamado de
extraordinário.

Os esquemas podem ou não produzir novos vértices extraordinários em cada
subdivisão.
Extraordinário
Regular
MODIFIED BUTTERFLY

C
Nosso esquema escolhido possui continuidade
é interpolativo, uniforme, estacionário, utiliza
malhas triangulares, tem como valência 6 os
vértices regulares e usa as seguintes máscaras
abaixo para subdivisão.
Regular
Extraordinário
1
,
MODIFIED BUTTERFLY – SUBDIVISÃO
REGULAR


Ao dividir uma aresta em duas, se os dois vértices da ponta
da aresta (pais) forem regulares, a seguinte máscara com os
respectivos pesos são usados.
W é o valor de tensão a ser usado. Esse fator representa o
quanto a superfície vai ficar próxima da malha de controle.
MODIFIED BUTTERFLY – SUBDIVISÃO
EXTRAORDINÁRIA


Caso os dois vértices da aresta (pais) sejam extraordinários, calcula-se
o peso de acordo com o número de vértices vizinhos e divide-se por
dois.
Caso somente um vértice da aresta seja irregular, usa-se somente este
vértice para se calcular o peso.
IMPLEMENTAÇÃO (INEFICIENTE)


Primeiro foi feito com uma estrutura de dados
convencional para malhas. Um array guardava os
vértices e outro array guardava as faces (em
grupo de 3 indíces).
Na hora da subdivisão, este algoritmo apresenta
complexidade O(F*F) e uma constante alta. Pois
cada face deve ser subdividida e para cada
subdivisão deve se achar a valência e os vértices
vizinhos de cada vértice. Para achar esta
valência, deve-se varrer toda a estrutura de
dados de novo.
IMPLEMENTAÇÃO (INEFICIENTE)

A tabela abaixo mostra os resultados para a
implementação com a estrutura de dados
mencionada no slide anterior.
Tetraedro
Coelho
Faces
T(s)
Faces
T(s)
16
0.001
800
0.016
64
0.002
3200
0.127
256
0.005
12800
1.7
1024
0.013
51200
27.9
4096
0.187
204800
7 min
16384
2.8
819200
>10min
65536
44.6
262144
>10 min
IMPLEMENTAÇÃO

Para melhorar o desempenho, foi utilizada uma
estrutura de half-edge. Que permite que
consultas variadas na malha sejam feitas em
tempo constante.
IMPLEMENTAÇÃO


Carrega modelo e cria um VertexBuffer e um
IndexBuffer.
A partir do VertexBuffer e do IndexBuffer,
inicializa-se a estrutura de Half-Edge
Para cada vértice, cria-se um HE_vert
 A cada 3 vértices, cria-se uma HE_face e
interativamente começa a criar as HE_edge

IMPLEMENTAÇÃO (HALF-EDGE)
Tetraedro (visão de cima)
IMPLEMENTAÇÃO (HALF-EDGE)
Estão sendo avaliados
os vértices da base
IMPLEMENTAÇÃO (HALF-EDGE)
Half-edge oposta
Half-edge
A
IMPLEMENTAÇÃO (HALF-EDGE)
• Uma face pode ter 3 half-edges,
mas só é necessário a referência
para uma delas.
• Um vértice pode ter “n” half-edges (se
estiver conectado a “n” arestas), mas só é
necessário a referência para uma delas.
IMPLEMENTAÇÃO (NORMAIS)
Média das normais das faces que contém o vértice
IMPLEMENTAÇÃO (TESSELLATION)
• Percorre cada face
• Cria vértice de cada aresta da face
• 12 novas half-edges
2
0
• Marca vértices que deverão ter
suas half-edges antigas deletadas
1
8
9
11
10
7
6
4
3
5
IMPLEMENTAÇÃO (TESSELLATION)


Para cada um dos vértices criados, calcula-se as
novas half-edges.
Após todas as half-edges terem sidos criadas, é
necessário deslocar os vértices de acordo com a
informação dos seus vértices geradores (pais).
Regular
Extraordinário
IMPLEMENTAÇÃO

Algumas consultas usadas através dessa
estrutura de dados.
IMPLEMENTAÇÃO

Com essa estrutura a complexidade o algoritmo
ficou linear. O(F). Abaixo os resultados:
Tetraedro
Coelho
Faces
T(s)
Faces
T(s)
16
0.001
800
0.017
64
0.002
3200
0.50
256
0.003
12800
0.131
1024
0.010
51200
0.644
4096
0.051
204800 4.2
16384
0.204
819200 42.9
65536
0.901
262144
6.3
IMPLEMENTAÇÃO

O(F*F) vs O(F)
Tetraedro
Coelho
T(s)
Faces
T(s)
Faces
T(s)
800
0.016
16
0.001
800
0.017
0.002
3200
0.127
64
0.002
3200
0.50
256
0.005
12800
1.7
256
0.003
12800
0.131
1024
0.013
51200
27.9
4096
0.187
20480
0
7 min
1024
0.010
51200
0.644
4096
0.051
4.2
16384
2.8
81920
0
>10min
20480
0
16384
0.204
42.9
65536
44.6
81920
0
65536
0.901
Tetraedro
Coelho
Faces
T(s)
Faces
16
0.001
64
262144 >10
min
262144 6.3
RESULTADOS
RESULTADOS
BIBLIOGRAFIA








Zorin, D., P. Schröder, and W. Sweldens. “Interpolating Subdivision
for Meshes with Arbitrary Topology.” Siggraph ‘96. pp. 189–192.
Dyn, N., J. A. Gregory, and D. A. Levin. “Butterfly Subdivision
Scheme for Surface Interpolation with Tension Control.” ACM
Transactions on Graphics. Vol. 9, No. 2 (April 1990): pp. 160–169.
DeRose, T., M. Kass, and T. Truong. “Subdivision Surfaces in
Character Animation.” Siggraph ‘98. pp. 85–94.
Dyn, N., S. Hed, and D. Levin. “Subdivision Schemes for Surface
Interpolation.” Workshop in Computational Geometry (1993), A. C. et
al., Ed.,” World Scientific, pp. 97–118.
Zorin, D. “Stationary Subdivision and Multiresolution Surface
Representations.” Ph.D. diss., California Institute of Technology,
1997. (Available at ftp://ftp.cs.caltech.edu/tr/cs-tr-97-32.ps.Z)
Catmull, E., and J. Clark. “Recursively Generated B-Spline Surfaces
on Arbitrary Topological Meshes.” Computer Aided Design, 1978.
Halstead, M., M. Kass, and T. DeRose. “Efficient, Fair Interpolation
Using Catmull-Clark Surfaces.” Siggraph ‘93. p. 35.
http://www.gamasutra.com/view/feature/3177/subdivision_surface_the
ory.php?page=2