Escola Politécnica da Universidade de São Paulo
Departamento de Engenharia Mecatrônica e Sistemas Mecânicos
Algoritmo para Converter
Sólidos CSG em Sólidos B-Rep
Defesa de Dissertação de Mestrado
Murilo Antonio Salomão Garcia
Orientador: Prof. Dr. Marcos de
Sales Guerra Tsuzuki
17 de abril de 2006
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
1. Introdução
•
Objetivo do trabalho: criar um algoritmo capaz de converter
modelos sólidos CSG (Construtive Solid Geometry) em
modelos sólidos B-Rep (Boundary Representation).
•
O algoritmo criado foi desenvolvido a partir do Marching
Cubes.
2 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
2. Representação CSG
•
Capturam o processo de construção que define o sólido por
uma seqüência de operações que instanciam ou combinam
primitivas.
•
Tradicionalmente as primitivas são simples, como cubos,
cilindros e esferas.
Posicionadas
Primitivas
(instâncias)
Combinadas
•
Indicado para o design e manipulação interativa de sólidos.
•
A exibição de CSG em tela não é suportada de forma nativa.
3 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
2. Representação CSG (cont.)
•
Formas mais complexas apropriadas para um conjunto de
aplicações particulares, como rasgos de chaveta e furos
roscados no caso da engenharia mecânica.
Primitivas
(instâncias)
Posicionadas
4 de 31
Combinadas
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
2.1
•
Transformações Afim
Manipulação de primitivas e sólidos:
•
Rotação
Posicionamento
Translação
•
Reflexão
5 de 31
Deformação
Escalamento
Escalamento
Uniforme
Não Uniforme
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
2.2
•
Operações Booleanas entre Sólidos
Combinar primitivas ou sólidos.
União:
Intersecção:
Diferença:
6 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
2.2
Operações Booleanas entre Sólidos (cont.)
Exemplos:
Intersecção
Subtração
7 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
2.3
•
Árvore CSG
Sintaxe que pode ser utilizada para especificar um sólido
em CSG.
8 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
2.4
•
Classificação de um Ponto para Sólidos CSG
Métodos de divisão e conquista, ou descida em
profundidade recursiva para calcular-se a classificação do
ponto (como interior ou exterior ao sólido).
9 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
3. Representação B-Rep
•
Modelos gráficos avançados que tentam resolver alguns
problemas através da inclusão de uma descrição completa
da superfície da fronteira do objeto.
3.1 Geometria e Topologia do Modelo B-Rep :
•
Três entidades fundamentais:
faces
arestas vértices
10 de 31
sólido
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
3.2 Operadores de Euler
•
A equação de Euler-Poincaré relaciona entidades primitivas
que formam o sólido de maneira quantitativa:
laços internos
v = número de vértices
a = número de arestas
f = número de faces
s = número de shells
h = número de furos
l = número de laços
laço externo
11 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
3.2 Operadores de Euler (cont.)
KVSF (Kill Vertex Solid Face)
KEV (Kill Edge Vertex)
KEF (Kill Edge Face)
12 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
3.2 Operadores de Euler (cont.)
MEKR (Make Edge Kill Ring)
MFKRH (Make Face Kill Ring Hole)
KSFMR (Kill Shell Face Make Ring)
13 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
4. Marching Cubes
Lorensen e Cline, 1987.
•
Geração de superfícies triangularizadas para fim de
visualização a partir de dados volumétricos.
•
Usualmente exames médicos como: tomografia
computadorizada, ressonância magnética, imagens de
microscópios.
•
Dados são pilhas de imagens 2D em tons de cinza.
14 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
4.1 Configurações do Cubo
•
Vértices classificados como interiores ou exteriores à região.
•
256 possibilidades
15 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
4.1 Configurações do Cubo (cont.)
• Uso de simetria reduz o
número de casos para 15
16 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
4.2 Variação de Delibasis
Original* (Lorensen e Cline)
•
Tabela com configurações
Delibasis
•
Gera configurações por
do cubo.
meio de algoritmo.
•
•
Gera superfícies com faces
triangulares.
Gera superfícies com faces.
poligonais (por vezes não planas).
* Algoritmo original mais configurações extras.
17 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
4.3 Versão Delibasis
1. Classificação dos vértices do cubo.
2. Definição dos isopontos.
3. Criação das arestas, sempre nas faces (conectando-se dois
isopontos).
•
Condição 0. Os dois isopontos devem estar situados na
mesma face do cubo;
•
Condição 1. Os dois isopontos devem compartilhar um
vértice adjacente classificado com interno;
Condição 0 E Condição 1
18 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
4.3 Versão Delibasis (cont.)
•
Condição 2. Os dois isopontos devem possuir vértices
adjacentes (um interno e o outro externo) de forma que um
vértice adjacente interno deve ser adjacente à um externo;
Condição 0 E Condição 2
•
Condição 3. Os dois isopontos devem compartilhar um
vértice adjacente externo e os outros três vértices da face
devem ser internos.
Condição 0 E Condição 3
19 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
5. Algoritmo de Conversão de
CSG para B-Rep
•
Início igual ao Marching Cubes: classificação dos vértices.
•
Encontra-se o primeiro Isocubo.
•
Processa-se o primeiro Isocubo:
•
Cria-se isopontos.
•
Gera-se polígonos.
•
Triangularização.
•
Gera-se a(s) face(s) triangulares no modelo B-REP.
Delibasis
continua
20 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
5.1 Laço de Abertura
• É a partir desse laço que o
sólido "cresce", ou seja, as
half-edges contidas nesse
laço são usadas na
geração das novas faces
do sólido.
21 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
5.2 Geração das Faces Triangulares
• Primeira Face
22 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
5.2 Geração das Faces Triangulares (cont.)
• Geração de Faces Triangulares com Uma Aresta
Já Criada:
<MEV> Make Edge Vertex;
<MEF> Make Edge Face;
23 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
5.2 Geração das Faces Triangulares (cont.)
• Geração de Faces Triangulares com Uma Aresta
Já Criada – Segunda Situação:
24 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
5.2 Geração das Faces Triangulares (cont.)
• Geração de Faces Triangulares com Duas Arestas
Já Criadas:
<MEF> Make Edge Face;
25 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
5.2 Geração das Faces Triangulares (cont.)
• Geração de Faces Triangulares com Três
Vértices:
OBS: Existem mais dois casos
26 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
5.4 Marcha através das Faces
Pilhas
27 de 31
cubos atuais
cubos futuros
0
cubo
cubo
cubo
65536
256
1
cubo
65792
cubo65793
257
65537
cubo
cubo
cubo
65536
256
cubo
257
cubo
65537
cubo
cubo 65536
65537
cubo
1
cubo
cubo
65792
257
cubo 65793
cubo
256
cubo
cubo
65537
257
cubo 65537
65536
cubo
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
6. Resultados
•
Etapas da construção.
•
28 de 31
Laço de abertura.
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
6. Resultados (cont.)
•
Primitivas.
•
29 de 31
Operações Booleanas.
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
6. Resultados (cont.)
•
Sólidos Complexos.
30 de 31
Algoritmo para Converter Sólidos CSG em Sólidos B-Rep
7. Conclusões
• Foi criado um algoritmo para conversão de sólidos
CSG em sólidos B-REP onde a marcha ocorre
apenas pela fronteira do sólido.
• Redução da complexidade do algoritmo marching
cubes de polinomial de primeira ordem para uma
complexidade constante.
• Utilização de arestas geradas em um dado cubo
no cubo adjacente, desta forma constrói-se um
sólido válido.
31 de 31