11

Aplicações de Funções de Base Radiais em Aplicações de Funções de Base Radiais em Reconstrução de Superfícies e ModelagemReconstrução de Superfícies e Modelagem

Apresentado por: Disney DouglasApresentado por: Disney Douglas

Orientador: Claudio EsperançaOrientador: Claudio Esperança

Universidade Federal do Rio de JaneiroPrograma de Engenharia de Sistemas e Computação -

COPPE

22

MotivaçãoMotivação

33

RoteiroRoteiro

Esquemas de RepresentaçãoEsquemas de RepresentaçãoFunções de Base RadiaisFunções de Base RadiaisVisualização e PoligonizaçãoVisualização e PoligonizaçãoProposta de TrabalhoProposta de TrabalhoResultados PreliminaresResultados PreliminaresConclusõesConclusões

44

Esquemas de representação de Esquemas de representação de superfíciessuperfícies

Representação DiscretaRepresentação DiscretaRepresentação ParamétricaRepresentação ParamétricaRepresentação ImplícitaRepresentação Implícita

55

Representação DiscretaRepresentação Discreta

Vantagem: Capacidade de representar formas de topologia arbitrária com precisão arbitráriaDesvantagens: Ocupam grande quantidade de memória e podem apenas aproximar objetos curvos

66

Representação paramétricaRepresentação paramétrica

Superfície representada por retalhosSuperfície representada por retalhos Descrita por equações paramétricasDescrita por equações paramétricas ExemplosExemplos

BézierBézier Hermite Hermite cúbicoscúbicos B-SplinesB-Splines NURBS (Non-Uniform Rational B-Spline)NURBS (Non-Uniform Rational B-Spline)

Vantagens: Podem representar superfícies suaves

Podem amostrar superfícies em resolução arbitrária

Desvantagem: Necessitam combinar muitos retalhos para objeto fechado

77

Representação ImplícitaRepresentação Implícita

A superfície é um conjunto de nível (A superfície é um conjunto de nível (level level set surfaceset surface),ou seja, ),ou seja, f f -1-1(c)(c)

f(p) = 0

f(p) < 0

f(p) > 0

88

Rep. Implícitas (cont.)Rep. Implícitas (cont.)

VantagensVantagensRepresentam bem superfícies suavesRepresentam bem superfícies suavesPodem ser avaliadas em resolução arbitráriaPodem ser avaliadas em resolução arbitrária

99

Reconstrução de SuperfíciesReconstrução de Superfícies

Escaneamento 3D

Renderização

1010

ReconstruçãoReconstrução

1111

Problema de interpolação de Problema de interpolação de pontos espalhadospontos espalhados

Desejamos construir algum objetoDesejamos construir algum objeto Esquemas explícitosEsquemas explícitos

Usam Usam Delaunay / VoronoiDelaunay / Voronoi (Edelsbrunner / Amenta et al) (Edelsbrunner / Amenta et al)

Esquemas implícitos Esquemas implícitos Método da Partição da Unidade (Ohtake et al)Método da Partição da Unidade (Ohtake et al) Moving Least Squares (MLS surfaces) Moving Least Squares (MLS surfaces) (Alexa / Levin / (Alexa / Levin /

Mederos et al / Xie et al / Amenta et Mederos et al / Xie et al / Amenta et Kil)Kil)

BlobsBlobs (Bloomenthal / Buraki) (Bloomenthal / Buraki) RBFsRBFs (Turk & O’Brien / Ohtake et al / Carr, Beatson et al ) (Turk & O’Brien / Ohtake et al / Carr, Beatson et al ) Conjuntos de nível (Conjuntos de nível (Level sets)Level sets) (Zhao et al / Du & Qin) (Zhao et al / Du & Qin)

1212

Interpolação Interpolação Thin-PlateThin-Plate

Dado um conjunto de n pontos Dado um conjunto de n pontos {{xx11, …, x, …, xnn}} e e

um conjunto de valores da função um conjunto de valores da função

{{vv11, …, v, …, vnn}}, obter uma função , obter uma função ss: : 33 tal tal

que que

ss((xxii) = ) = vvi i para para i = 1 , … , n i = 1 , … , n (1)(1)

““Suavidade”: Suavidade”:

(2)(2)

1313

Funções de Base RadiaisFunções de Base RadiaisUma função onde || . || denota a norma Euclideana é chamada uma função de base radial (RBF - Radial Basis Function), porque depende apenas da distância Euclideana entre os pontos x e xi.

r = ||x – xi||

1414

RBFs com suporte compactoRBFs com suporte compacto

• Funções de Wendland

1515

Função de interpolaçãoFunção de interpolação

A função de interpolação que satisfaz (1) e A função de interpolação que satisfaz (1) e minimiza (2) pode ser expressa por:minimiza (2) pode ser expressa por:

1616

Construção da função interpolanteConstrução da função interpolante

Onde ij = (xi – xj), ci = p(xi), vi = s(xi), i coef. RBF,

a, b, c, d cef. polinômio.

Construção: • O(n2) : espaço O(n2): operações

Resolução: • O(n2) : espaço O(n3): operações

1717

RBFsRBFs

O Sistema é mal condicionadoO Sistema é mal condicionadoSoluções numéricas: alguns erros para Soluções numéricas: alguns erros para NN

muito grandemuito grandeGeralmente é resolvido por decomposição LU Geralmente é resolvido por decomposição LU

ou similar (lento)ou similar (lento)RBFs com suporte compactoRBFs com suporte compacto

São bem condicionados (matriz esparsa)São bem condicionados (matriz esparsa)

1818

““Fast” RBFsFast” RBFs

Carr, Beatson & al Carr, Beatson & al Redução dos centros (solução aproximada)Redução dos centros (solução aproximada)

Fast Multipole Method (Greengard & Fast Multipole Method (Greengard & Rokhlin)Rokhlin)Avaliação aproximadaAvaliação aproximada

1919

Modelagem com RBFsModelagem com RBFs

Turk & O’BrienTurk & O’BrienUsaram pontos de restrição Usaram pontos de restrição

Pontos de fronteira: Pontos de fronteira: ff((ppii) = 0) = 0

Pontos normais: Pontos normais: ff((ppjj) > 0) > 0

Pontos interiores: Pontos interiores: ff((ppkk) < 0) < 0

f > 0 f < 0f = 0

2020

Visualização de objetos implícitos - Visualização de objetos implícitos - PontosPontos

•Espalhamento dos pontos baseado em física

•Forças de atração na superfície (gradiente e sinal)

•Forças de repulsão garentem afastamento uniforme

2121

Curvas de silhuetaCurvas de silhueta Definidas como o conjunto de curvas em Definidas como o conjunto de curvas em

que o produto interno da normal a superfície que o produto interno da normal a superfície e a direção da visão é zero.e a direção da visão é zero.

2222

Curvas de nívelCurvas de nível

Obtidas por interseção de planos Obtidas por interseção de planos perpendiculares à linha de visãoperpendiculares à linha de visão

2323

Renderização por polígonosRenderização por polígonos

Aproximação linear Aproximação linear por partes + por partes + algoritmos de algoritmos de rendarizaçãorendarização

2424

Ray TracingRay Tracing

Promove o Promove o acompanhamento de acompanhamento de um raio de luz no um raio de luz no sentido inversosentido inverso Para cada pixel da Para cada pixel da

imagem um raio é imagem um raio é lançadolançado

LentoLento

2525

Volumétrica - Ray CastingVolumétrica - Ray Casting

Raios do ponto de Raios do ponto de vista de visão através vista de visão através de cada pixel são de cada pixel são lançados no volumelançados no volume

A comtribuição ao A comtribuição ao pixel é calculada pixel é calculada intregrando a função intregrando a função de densidade ao de densidade ao longo do raio.longo do raio.

2626

PoligonizaçãoPoligonização

Dado um campo escalar, i.e. Dado um campo escalar, i.e. ff: : 33 e e uma constante uma constante cc, obter uma aproximação , obter uma aproximação linear por partes para a superfície linear por partes para a superfície f f –1 –1 ((cc))

Principais questõesPrincipais questõesErros de aproximaçãoErros de aproximaçãoTopologia correta Topologia correta Número de triângulosNúmero de triângulosQualidade dos triângulosQualidade dos triângulos

2727

Algoritmos de poligonizaçãoAlgoritmos de poligonização Algoritmo de continuação (Bloomenthal)Algoritmo de continuação (Bloomenthal) Marching Cubes (Lorensen & Cline) Marching Cubes (Lorensen & Cline)

VariantesVariantes Marching Tetrahedra (Marching Tetrahedra (Treece & al)Treece & al) Marching Triangles (Hartmann)Marching Triangles (Hartmann) Dual Contouring (Gibson, Shaefer & Warren)Dual Contouring (Gibson, Shaefer & Warren)

2828

O sistema Teddy (Igarashi)O sistema Teddy (Igarashi) Modelagem baseada em traçosModelagem baseada em traços Muitas operações são Muitas operações são

executadas através de traços executadas através de traços (curvas)(curvas) CriaçãoCriação ExtrusãoExtrusão CorteCorte MisturaMistura

Usa malha tradicional para Usa malha tradicional para representaçãorepresentação Suavização usa a poligonização de Suavização usa a poligonização de

HoppeHoppe Recentemente introduziu uma Recentemente introduziu uma

“malha mais bonita”“malha mais bonita” Objetos com topologia esféricaObjetos com topologia esférica

2929

Forma livre com superfícies Forma livre com superfícies variacionais (Karpenko & al) variacionais (Karpenko & al)

Parecido com o TeddyParecido com o Teddy Usa interpolação thin-plate Usa interpolação thin-plate

(RBFs)(RBFs) Visualização via poligonizaçãoVisualização via poligonização Relaxa um pouco as restricões Relaxa um pouco as restricões

do Teddydo Teddy Múltipla conexão dos Múltipla conexão dos

componentescomponentes Superfícies ralmente suavesSuperfícies ralmente suaves

Principais ProblemasPrincipais Problemas É lento para modelos com muitos É lento para modelos com muitos

pontospontos Sem vincos e pontas (Sem vincos e pontas (sharp sharp

featuresfeatures)) Sem furos Sem furos

3030

PropostaProposta

Propomos um sistema híbrido de modelagem à mão livre onde se possa construir e editar objetos tridimensionais trabalhando com representações paramétricas e implícitas variacionais.

Modelagem de superfícies por meio de traços Edição da malha da superfície Formas arredondadas Vincos e pontas

3131

Operações de ModelagemOperações de Modelagem

CriaçãoCriaçãoDeformaçãoDeformaçãoCombinaçãoCombinação

Operações booleanasOperações booleanasMisturaMistura

OutrosOutrosCorteCorteEscavaçãoEscavação

3232

CriaçãoCriação

O usuário desenha a silhueta do objeto (curva O usuário desenha a silhueta do objeto (curva fechada)fechada)

O sistema constrói o modelo 3D com base na O sistema constrói o modelo 3D com base na silhueta inflando o polígonosilhueta inflando o polígono

3333

Combinação (blending)Combinação (blending)

Uma curva é traçada para unir duas Uma curva é traçada para unir duas partes do Objetopartes do Objeto

As duas partes são unidasAs duas partes são unidas

3434

ExtrusãoExtrusão

3535

PerfuraçãoPerfuração Projeta-se o traço do Projeta-se o traço do

furo na parte frontal e furo na parte frontal e traseira da superfícietraseira da superfície

Usa-se as duas Usa-se as duas projeções p/ computar projeções p/ computar alguns pontos médiosalguns pontos médios Adiciona-se um ponrto Adiciona-se um ponrto

no “centro” que é no “centro” que é avaliado como negativoavaliado como negativo

Cria-se outro objetoCria-se outro objeto CombinaçãoCombinação

3636

Edição - malhasEdição - malhas

Free-Form Modeling (Botsh & Kobbelt)Free-Form Modeling (Botsh & Kobbelt) A superfície deformada pode ser moldada com rigidez A superfície deformada pode ser moldada com rigidez

de anisotropicade anisotropica A suavidade das deformaçõews variam de CA suavidade das deformaçõews variam de C00 a C a C22..

3737

Free-Form modelingFree-Form modeling

3838

Representação de malha híbrida Representação de malha híbrida (Allègre & al)(Allègre & al)

•Opera com malhas paramétricas e implícitas

•Utiliza uma Hybrid-Tree (generalização de CSG-Tree)

3939

SistemaSistema

Desejamos que o sistema tenha as Desejamos que o sistema tenha as seguintes característicaseguintes característicaBaixa complexidade de

avaliação/visualização, Baixo custo computacional para visualização, Pouco dependente das distribuições

espaciais de amostragem.

4040

Resultados PreliminaresResultados Preliminares

Reconstrução de superfícies através de Reconstrução de superfícies através de funções de base radiais com suporte funções de base radiais com suporte compactocompactoSubdivisão espacialSubdivisão espacialConstrução da função interpolanteConstrução da função interpolantePoligonizaçãoPoligonização

4141

Subdivisão espacialSubdivisão espacial

O espaço é O espaço é subdividido por meio subdividido por meio de uma de uma octreeoctree Critério de subdivisão: Critério de subdivisão:

Quantidade de pontos Quantidade de pontos por nó =por nó = L Lmaxmax

4242

Construção da função InterpolanteConstrução da função Interpolante

Para cada nó da Para cada nó da octreeoctree calculamos uma calculamos uma RBF com suporte compacto, com raio RBF com suporte compacto, com raio suporte igual a ¾ da diagonal do cubo do suporte igual a ¾ da diagonal do cubo do nó folhanó folha

Poucos pontos podem gerar funções ruinsPoucos pontos podem gerar funções ruinsSurgem falhas e artefatos indesejáveisSurgem falhas e artefatos indesejáveisSe a quantidade de pontos é insuficiente, Se a quantidade de pontos é insuficiente,

aumentamos progressivamente o raio do aumentamos progressivamente o raio do suporte da função.suporte da função.

4343

Cont.Cont.

Ri

ci

4444

Partição da unidadePartição da unidade

Depois que o domínio Depois que o domínio é dividido em é dividido em subconjuntos não disjuntos subconjuntos não disjuntos i i e calculada as e calculada as

funções locais funções locais ssii usamos o método da partição usamos o método da partição

da unidade.da unidade.

4545

ConclusõesConclusões

Acreditamos que um método híbrido que utilize funções de base radiais e manipulaçãode malha seja ideal para a modelagem à mão livre, satisfazendo os requisitos acima mencionados e capaz de criar modelos de superfícies que tenham formas arredondadas, bem como vincos e pontas.

4646

Algumas questõesAlgumas questões Como obter características afiadas na

interpolação e modelagem de superfícies usando funções de base radiais com suporte compacto?

Como melhorar a performance da poligonização de tal modo que não sejam avaliados todos os vértices da grade?

É possível conjugar abordagens como o método da partição da unidade com funções de base radiais com suporte compacto, e obter um comportamento da função como se tivesse suporte global?