Modelagem de Sólidos para Aplicações em Computação Gráfica Joaquim Bento Cavalcante-Neto [email protected] Grupo de Computação Gráfica, Realidade Virtual

Modelagem de Sólidos para Aplicações em Computação

GráficaJoaquim Bento Cavalcante-Neto

[email protected]

Grupo de Computação Gráfica, Realidade Virtual e Animação (CRAb)

Departamento de Computação (DC)Universidade Federal do Ceará (UFC)

Fortaleza, Novembro 2004

CRAb UFC

mailto:[email protected]

Parte I

Conceitos

Cavalcante-Neto, INFOSOL, 2004

3

Roteiro

• Conceitos de modelagem

• Modelos de decomposição

• Modelos de construção

• Modelos de fronteira

• Conclusões


Conceitos de modelagem


5

Definição de modelo

• O que são modelos? – Objetos artificialmente construídos– Facilitam a análise de fenômenos, situações


6



• Quais são os tipos de modelos?– Modelos físicos - prédios, navios, carros– Modelos moleculares - arranjo de átomos

– Modelos matemáticos - equações e dados


7



• Quais são os tipos de modelos?– Modelos físicos - prédios, navios, carros– Modelos moleculares - arranjo de átomos– Modelos matemáticos - equações e dados

• Para que usar modelos? – Estudo de características de coisas reais– Simulação do comportamento de coisas

reaisCavalcante-Neto, INFOSOL, 2004

8

Modelos computacionais

• Definição– Dados armazenados no computador

– Podem representar vários tipos de modelos


9


• Definição– Dados armazenados no computador– Podem representar vários tipos de modelos

• Modelagem geométrica– Modelagem para resolver problemas

geométricos– Responde a perguntas do tipo:

•a) que parte do corpo é visível para o usuário?

•b) qual cor é associada a cada elemento?


10


• Modelagem de sólidos– Braço da modelagem geométrica– Trata de coisas completas, fechadas– Responde às questões “algoritmicamente”


11


• Modelagem de sólidos– Braço da modelagem geométrica– Trata de coisas completas, fechadas– Responde às questões “algoritmicamente”

• Níveis de abstração em modelagem– Nível físico - sólido propriamente dito– Nível contínuo - representação matemática– Nível representação - armazenamento

(pontos, coeficientes, etc…)– Nível implementação - código, estrutura de

dados


12


• Classificação dos tipos de modelos– Modelos de decomposição

• Uso de primitivas básicas (cubos, etc…)• Sólido descrito através de operações de “gluing”


13




– Modelos de fronteira• Uso de hierarquia (sólido, faces, arestas, etc…)• Sólido descrito através de seu contorno


14




– Modelos de fronteira• Uso de hierarquia (sólido, faces, arestas, etc…)• Sólido descrito através de seu contorno

– Modelos de construção • Uso de primitivas básicas mais elaboradas (cone,

etc…)• Sólido descrito através de operações de

construção


Modelos de decomposição


16

Tipos de modelos

• Enumeração exaustiva– Primitiva básica - cubos de mesmo tamanho– Usadas em visualização volumétrica

(voxels), etc.


17

Tipos de modelos


(voxels), etc.• Decomposição celular

– Primitiva básica - qualquer célula (triângulo, quadrilátero, etc.)

– Usadas em simulações numéricas (MEF), etc.


18

Tipos de modelos


(voxels), etc.• Decomposição celular

– Primitiva básica - qualquer célula (triângulo, quadrilátero, etc.)

– Usadas em simulações numéricas (MEF), etc.• Subdivisão espacial

– Primitiva básica - cubos de tamanho variável– Usadas em modelagem propriamente dita


19

Subdivisão espacial

• Quadtrees Célula vazia


20


• Quadtrees Célula cheia


21


• Quadtrees Célula cheia


22


• Quadtrees Célula parcial


23


• Octree


24


• Octree


25

Características

• Baixa precisão, porque são aproximadas

• Geram modelos válidos

• Não é ambíguo e a representação é única

• Não é conciso (árvore com muitas células)

• Realiza operações fechadas (Booleanas)

• Útil para modelagem auxiliar (buscar, localizar, etc.) Cavalcante-Neto, INFOSOL,

2004

Modelos de fronteira


27

Tipos de modelos

• Baseados em polígonos– Lista de faces


28

Tipos de modelos


• Baseados em vértices– Lista de vértices


29

Tipos de modelos


• Baseados em vértices– Lista de vértices

• Baseados em arestas– Aresta “alada” (winged-edge) - Wed – Meia aresta (half-edge) - Hed


30

Lista de faces


31

Lista de faces


32

Lista de faces


33

Lista de faces


34

Lista de faces


35

Winged-edge


36

Half-edge


37

Half-edge


38

Half-edge


39

Características

• Precisão muito alta, representação eficiente

• Geram modelos válidos

• Não é ambíguo e a representação é única

• Não é muito conciso (Hed é grande, etc.)

• Poderoso para modelagens complexas


Modelos de construção


41

Tipos de modelos

• Modelos de semi-espaço– Primitiva básica - semi-espaços (semi-

espaço planar, semi-espaço cilíndrico, etc.)– O modelo é definido pela combinação dos

semi-espaços em uma árvore por op. Booleanas


42

Tipos de modelos

• Modelos de semi-espaço– Primitiva básica - semi-espaços (semi-espaço

planar, semi-espaço cilíndrico, etc.)– O modelo é definido pela combinação dos semi-

espaços em uma árvore por op. Booleanas

• Modelos CSG (Constructive Solid Geometry)– Primitiva básica - quaisquer objetos construídos

a partir de uma combinação de semi-espaços– O modelo é definido pela combinação das

primitivas em uma árvore usando op. Booleanas


43

CSG


44

CSG


45

CSG


46

CSG


47

CSG


48

CSG


49

CSG


50

CSG


51

CSG


52

CSG


53

Características

• Precisão depende das primitivas, se existirem muitas primitivas a precisão pode ser bem grande

• Podem gerar modelos não-válidos

• Não é ambíguo e a representação não é única

• É bem mais conciso que as demais, mas em modelagens práticas tende a crescer

• Uma modelagem por CSG pode ser bem complexa, dependendo do problema


Conclusões


55

Conclusões

• Modelar NÃO é somente usar um software


56

Conclusões


• O tipo de modelagem que se aplica a um caso específico depende de vários fatores: – precisão desejada – memória disponível– custo computacional


57

Conclusões


• O tipo de modelagem que se aplica a um caso específico depende de vários fatores: – precisão desejada – memória disponível– custo computacional

• Modelagem é um passo fundamental para aplicações em computação gráfica e várias outras áreas de aplicação


Parte II

Pesquisa


59

Roteiro

• Referência

• Jmesh

• Exemplos

• Conclusões


Referência


61

Referência

• Título: – An Algorithm for Three-Dimensional Mesh Generation for

Arbitrary Regions with Cracks

• Autores:– Cavalcante-Neto, Joaquim B. (CRAb, UFC)– Wawrzynek, Paul A. (CFG, Cornell University)– Ingraffea, Anthony R. (CFG, Cornell University)– Carvalho, Marcelo T. (Tecgraf, PUC-Rio)– Martha, Luiz F. (Tecgraf, PUC-Rio)

• Referência:– Cavalcante-Neto, et al., Engineering with Computers, 17:

75-91, Springer-Verlag, 2001


Jmesh


63

Jmesh


• Construção de uma octreeModelo de entrada

Concentração de elementos

64

Jmesh


• Construção de uma octreeModelo de entrada

Árvore refinada

Árvore gerada

Concentração de elementos

65

Jmesh

• Geração dos elementos (Avanço de fronteira)


Face base

66

Jmesh



Vértice ideal

67

Jmesh



Vértice ideal

Vértices candidatos

68

Jmesh

• Geração dos elementos (Critério de escolha)


Ângulo sólido

Exemplos


70

Exemplos


71

Exemplos


Conclusões


73

Conclusões

• Técnica robusta, rápida e confiável– 3 R,s => Rapid, Robust and Reliable


74

Conclusões


• Gera modelos com milhões de elementos


75

Conclusões


• Gera modelos com milhões de elementos

• Trata modelos complexos– Com furos– Com geometrias complexa– Com fraturas


Modelagem de Sólidos para Aplicações em Computação

GráficaJoaquim Bento Cavalcante-Neto

[email protected]

www.crab.ufc.br

Fortaleza, Novembro 2004

CRAb

mailto:[email protected]

http://www.crab.ufc.br/

Documents

Modelagem de Sólidos para Aplicações em Computação Gráfica Joaquim Bento Cavalcante-Neto [email protected] Grupo de Computação Gráfica, Realidade Virtual