42
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

Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno [email protected] Laboratorio de Computação Gráfica-UFRJ

Embed Size (px)

Citation preview

Page 1: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 2: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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.

Page 3: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 4: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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.

Page 5: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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.

Page 6: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 7: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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.

Page 8: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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).

Page 9: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 10: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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)

Page 11: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 12: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 13: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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.

Page 14: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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á?

Page 15: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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]

Page 16: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 17: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 18: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 19: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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.

Page 20: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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)

Page 21: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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.

Page 22: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 23: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 23

As equações (2) e (3) podem ser escritas na forma matricial, e assim obter di e pi:

Page 24: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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)

Page 25: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 26: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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.

Page 27: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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)

Page 28: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 28

Função base thin-plate(aproximadora)

Função base gaussiana Função base multi ordem

Page 29: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 29

Detalhes da implementação Pre-processamento

Page 30: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 30

A operação de inflação Amostragem e suavisação das pontas

Page 31: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 31

Geração de restrições no plano Z=0 (surface constraints and exterior constraints)

Page 32: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 32

Geração de restrições no plano Z=n (surface constraints and exterior constraints)

Page 33: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 33

Renderização Poligonização: Marching Cubes

Page 34: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 34

Page 35: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 35

Page 36: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 36

Page 37: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 37

Geração de restrições no plano Z=n usando Spine (surface constraints and exterior constraints)

Page 38: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 39: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

06/06/03 LCG-UFRJ 39

Desenho a mão livre Curvas e ambigüidade

Page 40: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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.

Page 41: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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

Page 42: Operação de inflação usando superfícies implícitas variacionais Apresentado por: Alvaro Cuno alvaro@lcg.ufrj.br Laboratorio de Computação Gráfica-UFRJ

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.

. . .