Modelagem de Sólidos para Aplicações em Computação Gráfica Joaquim Bento Cavalcante-Neto...

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

GráficaJoaquim Bento Cavalcante-Neto

joaquimb@lia.ufc.br

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

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

Cavalcante-Neto, INFOSOL, 2004

Conceitos de modelagem

Cavalcante-Neto, INFOSOL, 2004

5

Definição de modelo

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

Cavalcante-Neto, INFOSOL, 2004

6

Definição de modelo

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

• 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

Cavalcante-Neto, INFOSOL, 2004

7

Definição de modelo

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

• 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

Cavalcante-Neto, INFOSOL, 2004

9

Modelos computacionais

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

Cavalcante-Neto, INFOSOL, 2004

10

Modelos computacionais

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

Cavalcante-Neto, INFOSOL, 2004

11

Modelos computacionais

• 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

Cavalcante-Neto, INFOSOL, 2004

12

Modelos computacionais

• 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”

Cavalcante-Neto, INFOSOL, 2004

13

Modelos computacionais

• 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”

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

Cavalcante-Neto, INFOSOL, 2004

14

Modelos computacionais

• 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”

– 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

Cavalcante-Neto, INFOSOL, 2004

Modelos de decomposição

Cavalcante-Neto, INFOSOL, 2004

16

Tipos de modelos

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

(voxels), etc.

Cavalcante-Neto, INFOSOL, 2004

17

Tipos de modelos

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

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

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

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

Cavalcante-Neto, INFOSOL, 2004

18

Tipos de modelos

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

(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

Cavalcante-Neto, INFOSOL, 2004

19

Subdivisão espacial

• Quadtrees Célula vazia

Cavalcante-Neto, INFOSOL, 2004

20

Subdivisão espacial

• Quadtrees Célula cheia

Cavalcante-Neto, INFOSOL, 2004

21

Subdivisão espacial

• Quadtrees Célula cheia

Cavalcante-Neto, INFOSOL, 2004

22

Subdivisão espacial

• Quadtrees Célula parcial

Cavalcante-Neto, INFOSOL, 2004

23

Subdivisão espacial

• Octree

Cavalcante-Neto, INFOSOL, 2004

24

Subdivisão espacial

• Octree

Cavalcante-Neto, INFOSOL, 2004

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

Cavalcante-Neto, INFOSOL, 2004

27

Tipos de modelos

• Baseados em polígonos– Lista de faces

Cavalcante-Neto, INFOSOL, 2004

28

Tipos de modelos

• Baseados em polígonos– Lista de faces

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

Cavalcante-Neto, INFOSOL, 2004

29

Tipos de modelos

• Baseados em polígonos– Lista de faces

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

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

Cavalcante-Neto, INFOSOL, 2004

30

Lista de faces

Cavalcante-Neto, INFOSOL, 2004

31

Lista de faces

Cavalcante-Neto, INFOSOL, 2004

32

Lista de faces

Cavalcante-Neto, INFOSOL, 2004

33

Lista de faces

Cavalcante-Neto, INFOSOL, 2004

34

Lista de faces

Cavalcante-Neto, INFOSOL, 2004

35

Winged-edge

Cavalcante-Neto, INFOSOL, 2004

36

Half-edge

Cavalcante-Neto, INFOSOL, 2004

37

Half-edge

Cavalcante-Neto, INFOSOL, 2004

38

Half-edge

Cavalcante-Neto, INFOSOL, 2004

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

Cavalcante-Neto, INFOSOL, 2004

Modelos de construção

Cavalcante-Neto, INFOSOL, 2004

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

Cavalcante-Neto, INFOSOL, 2004

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

Cavalcante-Neto, INFOSOL, 2004

43

CSG

Cavalcante-Neto, INFOSOL, 2004

44

CSG

Cavalcante-Neto, INFOSOL, 2004

45

CSG

Cavalcante-Neto, INFOSOL, 2004

46

CSG

Cavalcante-Neto, INFOSOL, 2004

47

CSG

Cavalcante-Neto, INFOSOL, 2004

48

CSG

Cavalcante-Neto, INFOSOL, 2004

49

CSG

Cavalcante-Neto, INFOSOL, 2004

50

CSG

Cavalcante-Neto, INFOSOL, 2004

51

CSG

Cavalcante-Neto, INFOSOL, 2004

52

CSG

Cavalcante-Neto, INFOSOL, 2004

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

Cavalcante-Neto, INFOSOL, 2004

Conclusões

Cavalcante-Neto, INFOSOL, 2004

55

Conclusões

• Modelar NÃO é somente usar um software

Cavalcante-Neto, INFOSOL, 2004

56

Conclusões

• Modelar NÃO é somente usar um software

• 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

Cavalcante-Neto, INFOSOL, 2004

57

Conclusões

• Modelar NÃO é somente usar um software

• 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

Cavalcante-Neto, INFOSOL, 2004

Parte II

Pesquisa

Cavalcante-Neto, INFOSOL, 2004

59

Roteiro

• Referência

• Jmesh

• Exemplos

• Conclusões

Cavalcante-Neto, INFOSOL, 2004

Referência

Cavalcante-Neto, INFOSOL, 2004

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

Cavalcante-Neto, INFOSOL, 2004

Jmesh

Cavalcante-Neto, INFOSOL, 2004

63

Jmesh

Cavalcante-Neto, INFOSOL, 2004

• Construção de uma octreeModelo de entrada

Concentração de elementos

64

Jmesh

Cavalcante-Neto, INFOSOL, 2004

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

Cavalcante-Neto, INFOSOL, 2004

Face base

66

Jmesh

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

Cavalcante-Neto, INFOSOL, 2004

Vértice ideal

67

Jmesh

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

Cavalcante-Neto, INFOSOL, 2004

Vértice ideal

Vértices candidatos

68

Jmesh

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

Cavalcante-Neto, INFOSOL, 2004

Ângulo sólido

Exemplos

Cavalcante-Neto, INFOSOL, 2004

70

Exemplos

Cavalcante-Neto, INFOSOL, 2004

71

Exemplos

Cavalcante-Neto, INFOSOL, 2004

Conclusões

Cavalcante-Neto, INFOSOL, 2004

73

Conclusões

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

Cavalcante-Neto, INFOSOL, 2004

74

Conclusões

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

• Gera modelos com milhões de elementos

Cavalcante-Neto, INFOSOL, 2004

75

Conclusões

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

• Gera modelos com milhões de elementos

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

Cavalcante-Neto, INFOSOL, 2004

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

GráficaJoaquim Bento Cavalcante-Neto

joaquimb@lia.ufc.br

www.crab.ufc.br

Fortaleza, Novembro 2004

CRAb