Visualização Volumétrica
Prova Didática
www.lsi.usp.br/~mkzuffo/psi5676
Exame de Livre Docência
Especialidade: Meios Eletrônicos Interativos
Defesa de Tese de Livre Docência
Local: Sala B2-08
Horario: 9:00
Data: 05/12/2001
Título: A Convergência da Realidade Virtual e
da Internet Avançada em Novos Paradigmas
de TV Digital
Candidato: Prof. Dr. Marcelo Knörich Zuffo
Especialidade: Meios Eletronicos Interativos.
Sumário
 Introdução (10 minutos)
 Representação de Dados (5 minutos)
 Operadores (15 Minutos)
 Algoritmos de Lapidação (15 Minutos)
 Exercício (5 minutos)
 Bibliografia Recomendada
Introdução
Apresentação
Definições
Escopo
Terminologia Básica
Histórico
Aplicações
Softwares Disponíveis
Apresentação
 Aula do Curso de PSI-5676
Visualização Científica
 Objetivo da Aula:
 Introduzir
conceitos de Visualização
Volumétrica
 Descrever Estruturas de Dados,
Operadores e Principais Algoritmos
Livros Recomendados
 Lichtenbelt, B. & Crane, R. & Naqvi, S. “Introduction to Volume
Rendering”, Hewlett-Packard Professional Books, Prentice Hall,
1998.
 W. Schroeder, K. Martin and B. Lorensen, “The Visualization
Toolkit – And Object Oriented Approach to 3D Graphics”,
Prentice Hall, 1996.
 Kaufman, A.E., Introduction to Volume Visualization, A.E.
Kaufman (Ed.), IEEE Computer Society Press, 1991.
 M. Chen, A. K. Kaufman and Roni Yagel, “Volume Graphics”,
Springer Verlag, 2000.
Definição
 “A Visualização
Volumétrica é um conjunto
métodos para extração de informações a
partir de dados volumétricos, através do
uso de computação gráfica interativa e
imageamento, e está relacionada com a
representação, manipulação e lapidação
destes dados” .
Arie Kaufmann
 Conjunto
fundamental de técnicas para a
visualização científica
Escopo
?
Lapidação
Rendering
Volume de Dados
> 3D (x, y, z, t)
Imagem 2D
Escopo
Zuffo el al 1997
Terminologia Básica
 Vóxel, Volume, Célula Vóxel
Célula
Vóxel
Vóxel
Volume
Terminologia Básica
 Vóxel, (Elemento de Volume), amostra de
uma posição no espaço;

Escalar, vetorial, tupla, matriz, tensor
 Célula vóxel: conjunto de vóxels
organizados em uma célula espacial;
 Volume: Conjunto de voxels;
Fontes de Dados Volumétricos
 Tomografia Computadorizada
 CAT (Computerized Axial Tomography)
 PET, SPECT, MRI, fMRI)
 Ultrasom
 Microscopia Co-focal Baseada em Laser
 Fluidodinâmica Computacional
 FEM (Finite Element Analysis)
 Análise Não Destrutiva
 Análise Destrutiva Visible Human (2000x2048x1500)
 Balões
Histórico
1972
1977
1978
1979
1981
1982
1984
1985
1986
1987
1988
1989
1993
1994
Tomografia Computadorizada Hounsfield
Contour Tracking [Fuchs et al.]
Apresentação de superfícies 3d [Sunguroff & Greenberg]
Cuberille [Herman & Liu]
Dephth only shading [Herman & Udupa]
Octree machine [Meagher]
Voxel Processor [Goldwasser & Reynolds]
Marching Rays [Tuy & Tuy]
Cube Archicteture [Kaufman & Bakalash]
Bach To Front & Front to Back
Depht gradient Shading [Gordon et Al.]
Contextual shading [Chen et al]
3D Scan convertion [Kaufman & Shimony]
Grey-Level Shading [Hoehne & Berstein]
Marching cubes [Lorensen & Cline]
Volume Rendering [Debrin et al., Upson & Keller, Sabella]
Ray-casting [Levoy]
Splatting [Westover]
Fourier Rendering [Levoy, Malzsender]
Shear Warp [Levoy]
Aplicações
 Engenharia Mecânica
 Medicina
 Previsão numérica de tempo
 Geofísica
 Extração de Petróleo
Análise não Destrutiva
Planejamento Cirúrgico
Lapidação Direta
Lapidação Indireta
Anatomia
Análise Destrutiva
 O Homem Visível
Zuffo et al. 1999
Aeronáutica
 Fluidodinâmica Computacional
Softwares Disponíveis
 OpenGl Volumizer
www.sgi.com/volumizer
 OpenGL
www.opengl.org
 Visualization Tookit
www.kitware.com
 Volume Pro
www.rtviz.com
 Advanced Visualization System
www.avs.com
A Biblioteca PVV
 Parallel Volume Rendering
 Ambiente de programação voltado para a
visualização volumétrica
 Implementa os principais operadores volumétricos
e estruturas de dados
 Disponível em:


www.lsi.usp.br/~pvv
Zuffo et al 1996
Estrutura de Dados
 Conectividade Espacial
 Taxonomia de Representação Volumétrica
Conectividade Espacial
Conectividade 6
Conectividade 18
Conectividade 26
Superfície 18 conectada
Taxonomia de Representação Volumétrica
Volumes
Não-conexos
Conexos
Irregulares
Regulares
Lineares
Amorfo
Curvolineares
Rectilineares
Anisotrópico
Isotrópico
Operadores
Gradiente
Classificadores de Cor e Opacidade
Reamostragem
Iluminação Volumétrica
A Equação de Visualização Volumétrica
Composição Volumétrica
Operador Gradiente
r



f f
f
grad ( f )  f ( x, y, z )  ( i  j  k )  f  ( i  j  k )
x y z
x y
z
j
k
i
f ( x, y , z )  c
Operador Gradiente
 Estimadores do gradiente:
 Roberts
 Diferenças centrais
 Diferenças parciais
 Sobel
 Interpolação
 O gradiente aproxima a normal à
isosuperfície passando pelo ponto
considerado.
 O módulo de gradiente identifica a existência
de uma superfície baseada na variação em
torno da superfície
Operador Gradiente
 Ex. Diferenças centrais
f(x,y,z+1)
f(x,y-1,z)
f(x-1,y,z)
f(x+1,y,z)
f(x,y,z)
f(x,y+1,z)
f(x,y,z-1)
Operador Gradiente
 Ex. Diferenças centrais
df(x,y,z)  Df(x,y,z)=f(x+1, y, z)-f(x-1, y, z)
dx
Dx
2
df(x,y,z)  Df(x,y,z)=f(x, y+1, z)-f(x, y-1, z)
dy
Dy
2
df(x,y,z)  Df(x,y,z)=f(x, y, z+1)-f(x, y, z-1)
dz
Dz
2
Operador Gradiente
 Analiticamente a partir da função de interpolação
Para uma célula voxel cúbica de dimensões unitárias
F(x,y,z) = Ax + By + Cz + Dxy + Exz + Fyz + Gxyz + H
dF(x,y,z) = A + Dy + Ez + Gyz
dx
dF(x,y,z) = B + Dx + Fz + Gxz
dy
dF(x,y,z) = C + Ex + Fy + Gxy
dz
Reamostragem
 Interpolação Trilinear
f(x,y,z) = A.x + B.y + C.z + D.x.y + E.x.z + F.y.z + H.x.y.z + G
f(1,1,1)
f(0,1,1)
f(0,1,z)
f(1,1,0)
f(0,1,0)
f(x,y,z)
f(0,y,z)
f(0,0,1)
f(1,0,1)
f(0,0,z)
j
f(1,0,z)
k
f(0,0,0)
i
f(1, y, z)
f(1,0,0)
Classificação
 Atribuição das Propriedades Ópticas ao
Vóxels
 Cor e Opacidade
Histograma Original
Distribuição dos Tecidos
Atribuição dos Materiais
Classificação
Classificação de cor
Função de transferência entre volume de
dados originais e volume de cores
(pseudocolorização)
Branco
C(i,j,k) = C(f(i,j,k)) Vermelho
Amarelo
Ar
Gordura
Músculo
Osso
Classificação da Opacidade
alpha = |
F(x,y,z) | * O(F(x,y,z))
Opacidade (alpha)
Magnitude do gradiente
função de transferência de opacidade
O(F(x,y,z))
Classificação da Opacidade
1




a (x ) =  1 - 1  f vr f (xi ) 
i
 


r
f
x
( i) 



0
se f( xi ) = f v
se f( xi ) - r  f v  f ( xi ) + r
caso contrário
Magnitude do gradiente
Opacidade
limiar
da
isosuperfície
24
Iluminação Volumétrica
 baseada
no campo escalar e campo
gradiente
 etapa computacionalmente custosa
(operações vetoriais)
 fundamental para a obtenção de imagens
de alta qualidade
 aplicação da equação de Phong
 aplicação de modelos de iluminação aos
objetos no interior do volume
 modelo de espalhamento simples (não
considerar os efeitos entre vóxeis)
Iluminação Volumétrica
 Ka(f(x,y,z))











Coef. de Reflexão Ambiente
Kd(f(x,y,z)) Coef. De Reflexão Difusa
Ks(f(x,y,z)) Coef. De Reflexão Especular
r
n(f(x,y,z))
Índice de Especularidade
N
N
Vetor normal (gradiente)
L
Vetor Iluminação
V
Vetor Observação
R
Vetor Reflexão (L)
f(x,y,z)
Voxel
I
Intensidade Luminosa
Para R, G e B aplicar a equação abaixo
j
número de fontes de luz
r
L
c
r
V
I  Ka I a  Kd 
Luz Ambiente
(
)
f (x , y , z )
(
)
r r
r r n
N  L j I j  K s  R j V I j
Luz Difusa
Luz Especular
Um Algoritmo Rápido para a Iluminação
Volumétrica
r
z
L

r
N
Representação em
coordenadas
esféricas
qN
x
Zuffo 1996
Normalização do volume
gradiente)
Índice
(8 bits)
jN
jL
Mód. do Grad.
(8 bits)
y
qL
(adequação da resolução do
Grad. j
(8 bits)
Grad. q
(8 bits)
Um Algoritmo Rápido para a Iluminação
Volumétrica
Dj
Qj
Dq
Tabelas de iluminação
Dq
Um Algoritmo Rápido para a Iluminação
Volumétrica
VOLUME
Esfera
Crânio
T novo (s)
2,75
8,39
T trad (s) T trad /T novo
16,40
57,62
5,96
6,86
A Equação de Visualização Volumétrica
x
b
I  a B ( x )  e

( t )dt
a
dx
Chandrasekhar 1949
P. Sabella 1988
Onde:
I(x.y) = Intensidade de luz no ponto x,y do plano de projecão;
B(x) = Intensidade de luz (refletida emitida)
parametrizada sobre o raio de luz;
p(t) = opacidade parametrizada sobre o raio;
[a,b] = intervalo onde o raio intercepta o volume;
Composição Volumétrica
 Operador
Composição (Porter&Duff 1984)
 Composição de filmes digitais
 Versão Discreta da Equação da
Visualização Volumétrica
(
)
V (i ) over v(i  1)  V (i )  1 - Va (i )  v(i  1)
Algoritmos de Lapidação
Algoritmos Básicos
Lapidação Indireta de Volume
Lapidação Direta de Volumes
Algoritmos de Lapidação (rendering)
 Algoritmos Básicos
 Métodos de Lapidação Indiretos
 Cubos
Marchantes
 Métodos de Lapidação Diretos
 Traçado
de Raios
 Shear Warp
Algoritmo Básico: Fatiamento
Lapidação Indireta de Volumes
 Técnicas Indiretas => Estruturas
Intermediárias
 Técnicas por ajuste de superfícies
 Rastreamento
de Contornos
 Cubos Marchantes
 Dividing cubes
Rastreamento de Contornos
Cubos Marchantes
 (“Marching Cubes”)
Lorensen & Cline 1987
 Algoritmo
gerador de superfícies
 gera uma lista de triângulos
 utiliza tabela para a criação dos triângulos
 resultado pode ser visualizado em
aceleradores gráficos comerciais
 resultado pode ser manipulado por
pacotes de modelagem
Cubos Marchantes
Classifique cada vértice
f(x,y,z) = c
Superfície
Limiar
(isosuperfície)
Célula Voxel
Fora da Superfície (vértice >= limiar)
Dentro da Superfície
(vértice < limiar)
Cubos Marchantes
Célula Voxel
Classifique cada vértice
Construa um índice
Endereçe tabela de bordas
Interpole vértices dos triângulos
Calcule e interpole normais
Triângulos e normais
Cubos Marchantes
Construa um índice entre 0 e 255 a partir na
classificação binária de cada vértice
v8
v7
v4
v3
v5
v6
v1
v2
Índice
v1
v2
v3
v4
v5
v6
v7
v8
Cubos Marchantes
256 combinações se reduzem a 15
Caso 0
Caso 1
Caso 2
Caso 3
Caso 5
Caso 6
Caso 7
Caso 8
Caso 10
Caso 11
Caso 12
Caso 13
Caso 4
Caso 9
Caso 14
Lapidação Direta de Volumes
Algoritmo de Traçado de Raios
Imagem-Objeto
Levoy 1988
Plano de
Imagem
Píxel
acumulado
Volume
Vóxeis
reamostrados
Raio
Lapidação Direta de Volumes
Algoritmo de Traçado de Raios
Raio
j
k
i
Vóxel original
Vóxel interpolado
Traçado de raios
Volume de Entrada
voxel
Funções
de
opacidade
classificação de
opacidade
voxel
classificação
de cor
opacidade
Cálculo da
opacidade
cor
tonalização
Volume RGBO
Reamostragem
RGBO
Legenda
Etapa de
Processamento
Estrutura
de dados
Funções
de cor
Composição
RGBO
Imagem Final
parâmetros
de
observador
Lapidação Direta de Volumes
Algoritmo de Shear Warp
Objeto-Imagem
Lacroute 1993
Raios de
“Shear”
Projeção
Composição
Fatias do
Volume
“
Warp
Plano de
Plano de
imagem
imagem
”
Shear-warp
Volume de Entrada
voxel
Funções
de
opacidade
voxel
classificação
de cor
classificação de
opacidade
opacidade
Cálculo da
opacidade
Funções
de cor
cor
tonalização
Parâmetros
de observador
Volume RGBO
“Shear”
RGBO
Composição
RGBO
Imagem
Distorcida
Legenda
Etapa de
processamento
Estrutura
de dados
“Warp”
Imagem Final
Exercício para próxima aula
 Considerando uma célula vóxel cúbica
unitária, provar que
df(x,y,z) = f(1, y, z)-f(0, y, z)
dx
df(x,y,z) = f(x, 1, z)-f(x, 0, z)
dy
df(x,y,z) = f(x, y, 1)-f(x, y, 0)
dz
Sumário
 Introdução
 Aplicações
 Organização Espacial
 Operadores
 Algoritmos de Lapidação
Bibliografia Recomendada









L. Westover, “Footprint Evaluation for Volume Rendering”, ACM Computer
Graphics, V. 24, N. 4, Aug 1990, P. 144-153.
M.K. Zuffo, A.J. Grant, R.D. Lopes, E.T. Santos and J.A. Zuffo, “A Programming
Environment for High-Performance Volume Visualization Applications”,
Computer & Graphics, Oxford, V. 20, N. 3, Mai 1996, P. 385-394.
Y. Trousset and F. Schmitt, “Active-Ray Tracing for 3D Medical Imaging”,
Proceedings of the Eurographics’87, Elsevier Science Publishers, 1887, P.
139-150.
Leitão, R B V; Fagundes, R P; Ayres, F J; Santos, E T; Zuffo, M K. “Algoritmo
rápido para iluminação volumétrica”. In: SIBGRAPI 9, Caxambu: SBC/UFMG,
1996.Caxambu: p.9-14.
P. Sabella, “A Rendering Algorithm for Visualizing 3D Scalar Fields”, ACM
Computer Graphics, V. 22, N. 4, Aug 1988, P. 160-167.
S. Parker, M. Parker, Y. Livnat, P-P. Sloan and C. Hansen, “Interactive Ray
Tracing for Volume Visualization”, IEEE Trans. on Visualization and Computer
Graphics, Jul-Set 1999, V. 5, N. 3, P. 238-250.
M. Levoy, “Display of Surfaces from Volume Data”, IEEE Computer Graphics
and Applications, 1988, V. 8, N. 5, P. 29-37.
W. Lorensen, H. Cline, “Marching Cubes: A high Resolution 3D Reconstruction
Algorithm”, ACM Computer Graphics, 21(4), p. 163-170, 1987
P. Lacroute and M. Levoy, Fast Volume Rendering Using a Shear-Warp
Factorization of the Viewing Transformation, Proc. SIGGRAPH '94, Orlando,
Florida, July, 1994, P. 451-458.