Operação de inflação usando
superfícies implícitas variacionais
Apresentado por: Alvaro Cuno
[email protected]
Laboratorio de Computação Gráfica-UFRJ
Junho -2003
Resumo



Neste seminário descreveremos os conceitos
relacionados ao processo de criação, à mão livre,
de modelos usando superficies implícitas
variacionais.
Apresentaremos uma interface que permite
descrever uma silhueta e, a partir desta, a criação
de um modelo 3D aproximado.
Também discutiremos de forma sucinta o
problema da ambigüidade na criação de interfaces
naturais para o computador.
06/06/03
LCG-UFRJ
2
Sumario

Contexto do seminário




Marco Teórico






Representação de objetos
Superfícies implícitas variacionais
Funções base radiais
Detalhes da implementação


O problema
Trabalhos relacionados
Objetivo da pesquisa
A operação de inflação
Interfaces naturais
Conclusões
Próximos passos
06/06/03
LCG-UFRJ
3
O problema



O ênfase dos atuais sistemas de modelagem 3D
(i.e. Maya, 3D Studio, etc.) está na criação e
manipulação de modelos precisos.
Eles não permitem a criação rápida de objetos de
forma livre. Porém, suas últimas versões
ofereçam algumas liberdades.
O paradigma WIMP (Windows, Icons, Menus,
Pointer ) usado no seu desenvolvimento requer
um treinamento especial para poder realizar as
suas complicadas operações de edição.
06/06/03
LCG-UFRJ
4
Trabalhos relacionados

Teddy: A Sketching Interface for 3D Freeform
Design [1] (SIGGRAPH 1999)

Limitações:



O sistema não suporta a criação de multiplos modelos
simultaneamente, não há operações para combinar objetos.
Os modelos criados têm topología esferíca (o usuario não pode
criar um torus).
Free-form sketching with Variational Implicit
Surfaces [2] (EUROGRAPHICS 2002)

Limitações:



06/06/03
A sua representação não suporta sharp features na superficie.
O merging é demasiadamente lento para um sistema interativo
O sistema prototipo não foi disponibilizado.
LCG-UFRJ
5
Pesquisa

Desenvolver uma interface “natural” para a criação
rápida e interativa de objetos de forma livre. Onde a
representação da superfície dos objetos estará definida
implicitamente por funções base radiais.
Contribuições:



06/06/03
Criação de objetos de forma livre inclusive com sharps edges,
corners e holes.
Operações para fácil edição dos objetos (Inflation, Merging,
Oversketching, Cutting)
A interface “natural”, “intuitiva” e “interativa” disponível
LCG-UFRJ
6
Marco teórico: Representação de objetos


A forma de um objeto sólido pode ser descrita
pela superfície S que delimita sua fronteira.
Dentro da modelagem geométrica, uma
formulação discreta e duas formulações
matemáticas se destacam na sua representação.
06/06/03
LCG-UFRJ
7

Modelos Discretos: é uma representação
poligonal definida por uma coleção de vértices,
arestas e polígonos (triângulos).
06/06/03
LCG-UFRJ
8

Vantagens



Desvantagens



06/06/03
Representação de superfícies de topologia arbitraria
Hardware especializado para o rendering (triângulos)
Devido ao tamanho do modelo há dificuldade na sua
manipulação interativa.
Somente pode “aproximar” superfícies suaves
Resolução fixa
LCG-UFRJ
9
Modelos Paramétricos: A superfície é descrita
por uma coleção de mapeamentos, que
correlacionam coordenadas do espaço de
parâmetros em coordenadas de pontos sobre a
superfície. Ou seja, um ponto p  S pode ser
descrito por:


06/06/03
A superfície está representada por partes (patchs)
descritos por uma equação paramétrica.(hermite,
bezier patches, splines, NURBS)
LCG-UFRJ
10

Vantagens



Desvantagens


06/06/03
Amostragem em resolução arbitraria
Modelagem de superfícies suaves
Precisa-se de muitos partes (patches) para modelar uma
superfície fechada. Isto origina costuras.
Dificuldade para modelar detalhe fino
LCG-UFRJ
11
Modelos Implícitos: A superfície é caracterizada
analiticamente por uma função
tal
que:
F(x,y,z) = c



06/06/03
Ou seja, F atua como uma função de classificação de
pontos do domínio de F, de modo que é possível
decidir se um ponto pertence ou não à superfície do
objeto pela avaliação desta função.
Também, um modelo implícito, pode ser descrito por
amostragem discreta (gridded volumes and octree
representations), sofrem das mesmas desvantagens das
representações discretas
LCG-UFRJ
12

Vantagens







Desvantagens

06/06/03
Topologia a arbitraria
Testes do tipo inside/outside, collision detection
Morphing, Blending, boolean operations
Modelagem com CSG (Computer Solid Geometry)
Fácil transformação para representação discreta por extração
de iso-superficies.
Representam bem a suavidade e podem ser avaliadas em
resolução arbitraria
Visualização custosa, uma vez que a avaliação de F não
fornece diretamente um ponto na superfície do objeto.
LCG-UFRJ
13
Curva Paramétrica
Curva Implícita
f(t): onde está a abelha no tempo t?
06/06/03
D=f(x,y,z): Quão longe do objeto está?
LCG-UFRJ
14
Classes de modelos implícitos

Superfícies implícitas algébricas: se a função que
a define é polinomial.

A superfície implícita dessa função é o conjunto dos
pontos onde a função tem valor zero
f(x,y,z)=0 [e.g. x2+y2+z2-r2=0]
06/06/03
LCG-UFRJ
15
Classes de modelos implícitos

Superfícies implícitas baseadas em esqueletos: A
superfície implícita será gerada a partir dos
pontos localizados a uma distância D do esqueleto
(Blobby, Meta Balls, Soft Objects, etc.).

Superfícies implícitas baseadas em amostras
06/06/03
LCG-UFRJ
16
Superfícies implícitas variacionais

O problema:
Dados os pontos (restrições)
{c1,c2,...,cn}
e os escalares {h1,h2,...,hn}
para cada um deles.
...procurar a função mais suave f(x)
que interpole os pontos ci
avaliando f(ci)= hi ,para i=1,...,n
06/06/03
LCG-UFRJ
17


Se definimos a palavra suave de um jeito particular,
existe uma única solução para o problema.
A solução é uma função f(x) que satisfaça todas as
restrições f(ci)= hi e que minimize o seguinte
funcional E :
Caso 2D:


06/06/03
E mede a curvatura agregada de f(x) numa região de
interesse
Uma função suave que não tenha regiões de alta curvatura
terá um valor pequeno de E
LCG-UFRJ
18

Há muitos métodos numéricos que são usados para
resolver este problema:





Elementos finitos
Diferenças finitas
Estes métodos discretizam a região de interesse num
conjunto de células e definem funções base locais sobre
estas células
Então, a função solução f(x) é expressa como uma
combinação linear destas funções base
Mas, a discretização origina funções que descrevem
superfícies visivelmente escalonadas, tem dificuldade
para representar detalhe fino e o custo do método cresce
cubicamente com a resolução.
06/06/03
LCG-UFRJ
19



Uma solução alternativa é expressar a solução f(x)
em termos de funções base radiais centradas nas
restrições ci
Extraordinariamente, é possível escolher as funções
radiais de forma que resolvam automaticamente as
equações diferenciais de E
Para a interpolação em 3D a função base mais
comumente usada é:
x=(x,y,z)
06/06/03
LCG-UFRJ
20

Usando a função base radial apropriada está
demonstrado que podemos escrever a função de
interpolação f(x) desta forma:
x=(x,y,z)


f(x) é definida como o somatório de uma coleção
de funções base radiais.
Resolvendo para dj e para os coeficientes de P(x)
sujeitos as restrições ci obtemos uma função que
interpola as restrições e minimiza o funcional E.
06/06/03
LCG-UFRJ
21

Definição do problema:

Dado um conjunto de pontos ci, i=1,...,n e um conjunto
de valores hi, i=1,...,n encontrar uma função
interpolante f:R3-R tal que:
f ( xi )  hi
i  1..n
(1)

Encontrar

Considerando a ortogonalidade ou side conditions:
n
n
n
 d   d x  d
j 1
06/06/03
j
j 1
j
j
j 1
LCG-UFRJ
n
j
yj  d jzj  0
(2)
j 1
22

As equações (2) e (3) podem ser escritas na forma
matricial, e assim obter di e pi:
06/06/03
LCG-UFRJ
23
Características da matriz





A utilização da função base thin-plate origina uma
matriz densa
Os valores não-nulos aumentam fora da diagonal.
A complexidade computacional cresce linearmente
quando mais restrições são adicionadas
Ordem de complexidade para armazenamento: O(n2)
Ordem de complexidade para operações aritméticas:
O(n3)
06/06/03
LCG-UFRJ
24
Funções base radiais



Determina a continuidade e a suavidade da
superfície representada
A thin-plate energy (equivalente à energia de
segunda ordem) não é suficiente para produzir
superfícies localmente detalhadas
Uma opção é usar uma função base que envolva
primeiro, segunda e terceira ordem de energia.
Produzirá uma matriz diagonalmente dominante,
os valores não-nulos diminuem fora da diagonal;
a qual pode ser corretamente manipula por o
método dos gradientes conjugados
06/06/03
LCG-UFRJ
25

Função base multi-ordem

O incremento da complexidade em relação ao
incremento de # de restrições é medianamente
linear com a função base multi-ordem em
comparação com a função base thin-plate.
06/06/03
LCG-UFRJ
26
Características da superfície resultante





Manifold
Suave (smooth)
Sem costuras (seamless)
A função base multi-ordem produzirá modelos
localmente mais detalhados mas mantendo sua
suavidade global
A função base thin-plate produzirá modelos
demasiados suaves, resultando modelos de tipo
arredondados (blobby)
06/06/03
LCG-UFRJ
27
Função base thin-plate
(aproximadora)
06/06/03
Função base gaussiana
LCG-UFRJ
Função base multi
ordem
28
Detalhes da implementação

Pre-processamento
06/06/03
LCG-UFRJ
29

A operação de inflação

06/06/03
Amostragem e suavisação das pontas
LCG-UFRJ
30

06/06/03
Geração de restrições no plano Z=0 (surface
constraints and exterior constraints)
LCG-UFRJ
31

06/06/03
Geração de restrições no plano Z=n (surface
constraints and exterior constraints)
LCG-UFRJ
32
Renderização

Poligonização: Marching Cubes
06/06/03
LCG-UFRJ
33
06/06/03
LCG-UFRJ
34
06/06/03
LCG-UFRJ
35
06/06/03
LCG-UFRJ
36

06/06/03
Geração de restrições no plano Z=n usando Spine
(surface constraints and exterior constraints)
LCG-UFRJ
37
Interfaces naturais

Interfaces naturais



Nova forma de interação com o usuário
Manipulação direta
O usuário expressa idéias através de traços e o
computador faz uma determinada ação analisando as
características perceptuais dos traços
User Interface
stroke
Recognizer
Reasoning
Resolution
Arquitetura pipeline do sistema
06/06/03
LCG-UFRJ
38
Desenho a mão livre

Curvas e ambigüidade
06/06/03
LCG-UFRJ
39
Conclusões


A análise das funções base radiais e do funcional
de enegía utilizado permitem um maior controle
sobre a superficie gerada.
O fato de inferir a intenção do usuário (em função
do traço feito) e executar a operação de edição
apropriada não é uma tarefa simples. É difícil
estabelecer regras gerais que abranjam todos os
casos.
06/06/03
LCG-UFRJ
40
Próximos passos ...


Múltiplos objetos
Operações:





Merging
Extrude
Cutting
Funções base anisotrópicas
Interface natural, interativa e intuitiva
06/06/03
LCG-UFRJ
41
Referencias




06/06/03
[1] IGARASHI T., MATSUOKA S., AND TANAKA H. Teddy: A
Sketching Interface for 3D Freeform Design. In Proceedings of
SIGGRAPH 99.
[2] KARPENKO O., HUGHES J., AND RASKAR R. Free-form
sketching with variational Implicit Surfaces. In Proceedings of
EUROGRAPHICS 2002.
[3] TURK G., AND O´BRIEN J. Modelling with Implicit
Surfaces that Interpolate. ACM Transaction on Graphics, 2002.
...
LCG-UFRJ
42