Upload
internet
View
103
Download
0
Embed Size (px)
Citation preview
Operação de inflação usando superfícies
implícitas variacionais
Apresentado por: Alvaro Cuno
Laboratorio de Computação Gráfica-UFRJ
Junho -2003
06/06/03 LCG-UFRJ 2
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 3
Sumario Contexto do seminário
O problema Trabalhos relacionados Objetivo da pesquisa
Marco Teórico Representação de objetos Superfícies implícitas variacionais Funções base radiais
Detalhes da implementação A operação de inflação
Interfaces naturais Conclusões Próximos passos
06/06/03 LCG-UFRJ 4
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 5
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:
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.
06/06/03 LCG-UFRJ 6
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: 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
06/06/03 LCG-UFRJ 7
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 8
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 9
Vantagens Representação de superfícies de topologia arbitraria Hardware especializado para o rendering (triângulos)
Desvantagens Devido ao tamanho do modelo há dificuldade na sua
manipulação interativa. Somente pode “aproximar” superfícies suaves Resolução fixa
06/06/03 LCG-UFRJ 10
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:
A superfície está representada por partes (patchs) descritos por uma equação paramétrica.(hermite, bezier patches, splines, NURBS)
06/06/03 LCG-UFRJ 11
Vantagens Amostragem em resolução arbitraria Modelagem de superfícies suaves
Desvantagens Precisa-se de muitos partes (patches) para modelar uma
superfície fechada. Isto origina costuras. Dificuldade para modelar detalhe fino
06/06/03 LCG-UFRJ 12
Modelos Implícitos: A superfície é caracterizada analiticamente por uma função tal que:
F(x,y,z) = c 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
06/06/03 LCG-UFRJ 13
Vantagens 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 Desvantagens
Visualização custosa, uma vez que a avaliação de F não fornece diretamente um ponto na superfície do objeto.
06/06/03 LCG-UFRJ 14
Curva Implícita Curva Paramétrica
f(t): onde está a abelha no tempo t? D=f(x,y,z): Quão longe do objeto está?
06/06/03 LCG-UFRJ 15
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
Classes de modelos implícitos
f(x,y,z)=0 [e.g. x2+y2+z2-r2=0]
06/06/03 LCG-UFRJ 16
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
Classes de modelos implícitos
06/06/03 LCG-UFRJ 17
O problema:
Superfícies implícitas variacionais
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 18
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:
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
06/06/03 LCG-UFRJ 19
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 20
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 21
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 22
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:
Encontrar
Considerando a ortogonalidade ou side conditions:
(1)
(2)
n
j
n
jjjjj
n
jjj
n
jj zdydxdd
1 111
0
ii hxf )( ni ..1
06/06/03 LCG-UFRJ 23
As equações (2) e (3) podem ser escritas na forma matricial, e assim obter di e pi:
06/06/03 LCG-UFRJ 24
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 25
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
Funções base radiais
06/06/03 LCG-UFRJ 26
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 27
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 28
Função base thin-plate(aproximadora)
Função base gaussiana Função base multi ordem
06/06/03 LCG-UFRJ 29
Detalhes da implementação Pre-processamento
06/06/03 LCG-UFRJ 30
A operação de inflação Amostragem e suavisação das pontas
06/06/03 LCG-UFRJ 31
Geração de restrições no plano Z=0 (surface constraints and exterior constraints)
06/06/03 LCG-UFRJ 32
Geração de restrições no plano Z=n (surface constraints and exterior constraints)
06/06/03 LCG-UFRJ 33
Renderização Poligonização: Marching Cubes
06/06/03 LCG-UFRJ 34
06/06/03 LCG-UFRJ 35
06/06/03 LCG-UFRJ 36
06/06/03 LCG-UFRJ 37
Geração de restrições no plano Z=n usando Spine (surface constraints and exterior constraints)
06/06/03 LCG-UFRJ 38
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
Recognizer Reasoning Resolution
stroke User Interface
Arquitetura pipeline do sistema
06/06/03 LCG-UFRJ 39
Desenho a mão livre Curvas e ambigüidade
06/06/03 LCG-UFRJ 40
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 41
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 42
Referencias [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.
. . .