Visualização Volumétrica

Prova Didática

www.lsi.usp.br/~mkzuffo/psi5676

Exame de Livre Docência

Especialidade: Meios Eletrônicos Interativos

Candidato: Prof. Dr. Marcelo Knörich Zuffo

Defesa de Tese de Livre Docência

Local: Sala B2-08Horario: 9:00Data: 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 ZuffoEspecialidade: 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çãoDefiniçõesEscopoTerminologia BásicaHistóricoAplicaçõesSoftwares 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

Volume de Dados > 3D (x, y, z, t)

Imagem 2D

Lapidação

Rendering

?

Escopo

Zuffo el al 1997

Terminologia Básica

Vóxel, Volume, Célula Vóxel

Vóxel

Volume

CélulaVóxel

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órico1972 Tomografia Computadorizada Hounsfield1977 Contour Tracking [Fuchs et al.]1978 Apresentação de superfícies 3d [Sunguroff & Greenberg]1979 Cuberille [Herman & Liu]1981 Dephth only shading [Herman & Udupa]1982 Octree machine [Meagher] Voxel Processor [Goldwasser & Reynolds]1984 Marching Rays [Tuy & Tuy]1985 Cube Archicteture [Kaufman & Bakalash] Bach To Front & Front to Back Depht gradient Shading [Gordon et Al.] Contextual shading [Chen et al]1986 3D Scan convertion [Kaufman & Shimony] Grey-Level Shading [Hoehne & Berstein] 1987 Marching cubes [Lorensen & Cline] 1988 Volume Rendering [Debrin et al., Upson & Keller, Sabella] Ray-casting [Levoy] 1989 Splatting [Westover] 1993 Fourier Rendering [Levoy, Malzsender] 1994 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 6

Conectividade 18

Conectividade 26 Superfície 18 conectada

Conectividade Espacial

Taxonomia de Representação Volumétrica

Curvolineares Rectilineares

Anisotrópico Isotrópico

Não-conexos

Volumes

Conexos

Irregulares Regulares

Amorfo Lineares

Operadores

GradienteClassificadores de Cor e OpacidadeReamostragemIluminação VolumétricaA Equação de Visualização VolumétricaComposição Volumétrica

Operador Gradiente

i

j k

)()(),,()( k

z

fj

y

fi

x

ffk

zj

yi

xzyxffgrad

czyxf ),,(

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

f(x+1,y,z)f(x-1,y,z)

f(x,y,z-1)

f(x,y,z+1)

f(x,y+1,z)

f(x,y-1,z)

f(x,y,z)

Ex. Diferenças centrais

Operador Gradiente

Ex. Diferenças centrais

f(x,y,z) f(x,y,z)=f(x+1, y, z)-f(x-1, y, z) x x 2

f(x,y,z) f(x,y,z)=f(x, y+1, z)-f(x, y-1, z) y y 2

f(x,y,z) f(x,y,z)=f(x, y, z+1)-f(x, y, z-1) z z 2

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

F(x,y,z) = A + Dy + Ez + Gyz x

Operador Gradiente

F(x,y,z) = B + Dx + Fz + Gxz y

F(x,y,z) = C + Ex + Fy + Gxy z

Reamostragem

i

j k f(1,0,0)

f(1,0,1)

f(1,0,z) f(0,0,z)

f(0,0,1)

f(x,y,z)

f(0,1,1)

f(0,y,z) f(1, y, z)

f(0,1,z)

f(1,1,1)

f(0,1,0)

f(0,0,0)

f(1,1,0)

Interpolação Trilinearf(x,y,z) = A.x + B.y + C.z + D.x.y + E.x.z + F.y.z + H.x.y.z + G

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)

C(i,j,k) = C(f(i,j,k))

Ar Gordura Músculo OssoBrancoBranco

VermelhoVermelho

AmareloAmarelo

Opacidade (alpha) Magnitude do gradiente

função de transferência de opacidadeO(F(x,y,z))

alpha = | | * O(F(x,y,z))F(x,y,z)

Classificação da Opacidade

Opacidade Magnitude do gradiente

24

limiarda

isosuperfície

Classificação da Opacidade

xr

f f x

f xi

v i

i

= -

1

1 1

0

se f x fi v( ) =

se f x r f f x ri v i( ) ( )- +

caso contrário

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

N

V

L

zyxf ,,

c

I K I K N L I K R V Ia a d j j s j

n

j

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 n(f(x,y,z)) Índice de Especularidade 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

Luz Ambiente Luz Difusa Luz Especular

Um Algoritmo Rápido para a Iluminação Volumétrica

Representação em coordenadas esféricas

y

x

z

Normalização do volume (adequação da resolução do gradiente)

Índice(8 bits)

Mód. do Grad.(8 bits)

Grad. (8 bits)

Grad. (8 bits)

N

L

NN

NN

LL

LLZuffo 1996

Tabelas de iluminação

Um Algoritmo Rápido para a Iluminação Volumétrica

VOLUMEVOLUME TTnovonovo (s)(s) TT tradtrad (s)(s) TT tradtrad /T/Tnovonovo

EsferaEsfera 2,752,75 16,4016,40 5,965,96CrânioCrânio 8,398,39 57,6257,62 6,866,86

Um Algoritmo Rápido para a Iluminação Volumétrica

I B x e dx

t dt

a

ba

x

( )

( )

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;

Chandrasekhar 1949P. Sabella 1988

A Equação de Visualização Volumétrica

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 v i V i V i v i over

1 1 1

Algoritmos de Lapidação

Algoritmos BásicosLapidação Indireta de VolumeLapidaçã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

Técnicas Indiretas => Estruturas Intermediárias

Técnicas por ajuste de superfícies Rastreamento de Contornos Cubos Marchantes Dividing cubes

Lapidação Indireta de Volumes

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

Classifique cada vértice

Fora da Superfície (vértice >= limiar)

Dentro da Superfície (vértice < limiar)

Superfície

Célula Voxel

f(x,y,z) = cf(x,y,z) = c

LimiarLimiar(isosuperfície)(isosuperfície)

Cubos Marchantes

Classifique cada vértice

Construa um índice

Endereçe tabela de bordas

Interpole vértices dos triângulos

Calcule e interpole normais

Célula Voxel

Triângulos e normais

Cubos Marchantes

v 1

v 7v 8

v 3v 4

v 6v 5

v 2

v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8Índice

Construa um índice entre 0 e 255 a partir na classificação binária de cada vértice

Cubos Marchantes

Caso 0

Caso 5 Caso 6 Caso 7

Caso 1 Caso 2 Caso 3 Caso 4

Caso 8 Caso 9

Caso 10 Caso 11 Caso 12 Caso 13 Caso 14

256 combinações se reduzem a 15

Cubos Marchantes

Lapidação Direta de Volumes

Plano deImagem

Volume

Píxelacumulado

Vóxeis reamostrados

Raio

Algoritmo de Traçado de Raios

Imagem-Objeto Levoy 1988

Lapidação Direta de Volumes

i

j k

Vóxel original

Vóxel interpolado

Raio

Algoritmo de Traçado de Raios

Traçado de raiosVolume de EntradaVolume de Entrada

voxelvoxel voxelvoxel

classificação declassificação deopacidadeopacidade

classificaçãoclassificaçãode corde cor

Imagem FinalImagem Final

opacidadeopacidade corcor

FunçõesFunçõesdede

opacidadeopacidade

FunçõesFunçõesde corde cor

Cálculo daCálculo daopacidadeopacidade

tonalizaçãotonalização

ComposiçãoComposiçãoRGBORGBO

ReamostragemReamostragemRGBORGBO

parâmetrosparâmetrosdede

observadorobservador

Volume RGBOVolume RGBO

Etapa deEtapa deProcessamentoProcessamento

EstruturaEstruturade dadosde dados

LegendaLegenda

Lapidação Direta de Volumes

Fatias do

Volume

Plano de

imagem

Raios de

Projeção

Plano de

imagem

“Shear”

Composição

“Warp ”

Algoritmo de Shear Warp

Objeto-Imagem Lacroute 1993

Shear-warpVolume de EntradaVolume de Entrada

voxelvoxel voxelvoxel

classificação declassificação deopacidadeopacidade

classificaçãoclassificaçãode corde cor

opacidadeopacidade corcor

FunçõesFunçõesdede

opacidadeopacidade

FunçõesFunçõesde corde cor

Cálculo daCálculo daopacidadeopacidade

tonalizaçãotonalização

Imagem FinalImagem Final

““Warp”Warp”

““Shear”Shear”

RGBORGBO

ParâmetrosParâmetrosde observadorde observador

Volume RGBOVolume RGBO

ComposiçãoComposição

RGBORGBO

ImagemImagemDistorcidaDistorcida

Etapa deEtapa deprocessamentoprocessamento

EstruturaEstrutura

de dadosde dados

LegendaLegenda

Exercício para próxima aula

Considerando uma célula vóxel cúbica unitária, provar que

f(x,y,z) = f(1, y, z)-f(0, y, z) x

f(x,y,z) = f(x, 1, z)-f(x, 0, z) y

f(x,y,z) = f(x, y, 1)-f(x, y, 0) z

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.