UNIVERSIDADE DO VALE DO RIO DOS SINOSCENTRO DE CIÊNCIAS EXATAS E TECNOLÓGICAS

CURSO DE CIÊNCIA DA COMPUTAÇÃO

Uma proposta de Amostragem Adaptativa paraComputação Gráfica Baseada em Pontos

por

UBIRATÃ AZEVEDO IGNÁCIO

Prof Dr. Marcelo WalterOrientador

Monografia submetida como requisitoparcial para a obtenção do título de

Bacharel em Ciência da Computação

São Leopoldo, Novembro de 2003

Resumo

A Computação Gráfica Baseada em Pontos é uma abordagem relativamente recentena Computação Gráfica, onde a idéia principal é a utilização de pontos como primi-tiva fundamental na representação dos objetos. Dentro deste contexto este trabalho ini-cialmente contribui para a divulgação deste novo paradigma na comunidade da UNISI-NOS, apresentando detalhadamente a técnica, sua evolução até o momento e suas prin-cipais aplicações. Como contribuições principais apresenta (i) uma nova proposta paraamostragem adaptativa de pontos que utiliza a orientação dos polígonos como critériopara realizar uma super-amostragem localizada e (ii) uma proposta para resolver falhasnas imagens geradas.

Palavras-chave: Renderização, Traçado de Raios, Imagens 3D, Pontos, Modelagem.

TITLE: “A PROPOSAL FOR ADAPTATIVE SAMPLING FOR POINT BASED COM-PUTER GRAPHICS”

Abstract

Point Based Graphics is a relatively new paradigm in Computer Graphics wherepoints are used as primitives for the representation of objects. We initially present thistechnique, its development, and main applications. Through this presentation we hopeto contribute for dissemination of this new paradigm in the UNISINOS community. Asmain contributions, this work introduces (i) a new approach for adaptative point sampling,where the orientation of polygons is used as criterion for a local supersampling and (ii) atechnique for filling in the images at the rendering step.

Keywords: Rendering, Ray Tracing, 3D Images, Point, Modeling.

Agradecimentos

Tantas são as pessoas e entidades às quais eu preciso e devo agradecer que seriamnecessários mais alguns trabalhos como este para comportar todos os votos e palavras.Os agradecimentos vão desde de meus familiares até o produtor de café que me manteveacordado quanto era necessário.

Mas momentos e pessoas são especiais, cada um à sua maneira. E são para estaspessoas que gostaria de expressar toda minha gratidão e sincero reconhecimento.

Aos meus pais, Jorge e Wanda, agradeço do fundo do meu coração por terem feitode mim a pessoa que sou hoje, e se estou alcançando esta vitória na minha vida, devo aosseus ensinamentos.

A minha amada Ana quero agradecer por sua compreensão, amor e carinho expres-sado, que me aliviaram as dores e me fizeram continuar no caminho.

Agradeço ao meu orientador, professor Marcelo Walter, por sua maneira tão sábiae humana de observar o caminho e me guiar corretamente neste trabalho. O esforço serárecompensado.

Minha gratidão aos professores Fernando Osório e Cláudio Jung pelas sábias ob-servações feitas a este trabalho, e que foram de suma importância para torná-lo melhor.

Agradeço aos meus colegas de trabalho pela paciência e compreensão durante esteano, e gostaria de finalizar com uma frase simples, transformada em clichê, mas queporém, poucos dão atenção ao seu real sentido:

Quando realmente queremos alguma coisa, nós conseguimosE assim encontramos as conquistas. Obrigado!

5

Conteúdo

Resumo 2

Abstract 3

Lista de Abreviaturas 7

Lista de Figuras 8

Lista de Tabelas 9

1 Apresentação 101.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.2 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4 Estrutura do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 O Modelo de Computação Gráfica Baseada em Pontos 122.1 Trabalhos Anteriores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2 O Processo de Renderização Baseada em Pontos . . . . . . . . . . . . . . 132.3 Amostragem de Pontos . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3.1 Especificação dos Dados de Entrada . . . . . . . . . . . . . . . . 142.3.2 Amostrando com Traçado de Raios . . . . . . . . . . . . . . . . 152.3.3 Capturando Pontos . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.4 Armazenando os Pontos Obtidos . . . . . . . . . . . . . . . . . . 22

2.4 Reconstrução de Imagens . . . . . . . . . . . . . . . . . . . . . . . . . . 232.4.1 Reconstruindo com Projeção Perspectiva . . . . . . . . . . . . . 232.4.2 Preenchendo Falhas Existentes . . . . . . . . . . . . . . . . . . . 25

2.5 Aplicações da CGBP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Amostragem Adaptativa e Preenchimento de Falhas 293.1 Amostragem Adaptativa . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2 Ajustando a Super-Amostragem . . . . . . . . . . . . . . . . . . . . . . 303.3 Resolvendo a Etapa de Renderização . . . . . . . . . . . . . . . . . . . . 30

4 Implementação e Resultados 344.1 O Sistema Protótipo SARS . . . . . . . . . . . . . . . . . . . . . . . . . 344.2 Resultados Obtidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

6

4.2.1 Analisando a Amostragem . . . . . . . . . . . . . . . . . . . . . 364.2.2 Imagens Renderizadas . . . . . . . . . . . . . . . . . . . . . . . 374.2.3 Preenchendo Falhas na Imagem . . . . . . . . . . . . . . . . . . 42

5 Conclusões e Trabalhos Futuros 455.1 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Bibliografia 48

Lista de Abreviaturas

CG Computação Gráfica

CGBP Computação Gráfica Baseada em Pontos

EWA Eliptical weighed Average

LDC Layered Depth Cube

LDI Layered Depth Image

RBP Renderização Baseada em Pontos

SARS Sistema de Amostragem e Reconstrução de Superfícies

Lista de Figuras

2.1 Determinação de vetores na superfície de uma triângulo ou polígono. . . . 142.2 Amostragem de um objeto em três planos ortogonais. . . . . . . . . . . . 152.3 Intersecção entre raios disparados e a superfície de um objeto. . . . . . . 162.4 Intervalo ∆d de amostragem de um objeto. . . . . . . . . . . . . . . . . 172.5 Esquema de traçado de raios utilizado no processo de amostragem. . . . . 182.6 Representação das coordenadas baricêntricas em um triângulo. . . . . . . 212.7 Divisão de um polígono em um conjunto de triângulos. . . . . . . . . . . 222.8 Determinação do triângulo que contém um ponto em um polígono. . . . . 232.9 Imagem renderizada através de RBP. . . . . . . . . . . . . . . . . . . . . 242.10 Renderização de um objeto amostrado em resoluções diferentes . . . . . 252.11 Imagem com falhas de preenchimento. . . . . . . . . . . . . . . . . . . . 262.12 Falhas de superfície e de fundo de imagem . . . . . . . . . . . . . . . . . 272.13 Estátua de David, parte do projeto Digital Michelangelo . . . . . . . . . 28

3.1 Intervalo ∆d′ entre os pontos amostrados . . . . . . . . . . . . . . . . . 303.2 Área de análise para a determinação de falhas. . . . . . . . . . . . . . . . 323.3 Imagens variando o fator de preenchimento de falhas de fundo. . . . . . . 323.4 Imagens variando o fator de preenchimento de falhas de superfície na

imagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.1 Janela principal do SARS . . . . . . . . . . . . . . . . . . . . . . . . . 344.2 Controles para renderização do SARS . . . . . . . . . . . . . . . . . . . 354.3 Amostragem de um objeto em várias resoluções . . . . . . . . . . . . . . 364.4 Amostragem Adaptativa de um objeto. . . . . . . . . . . . . . . . . . . . 374.5 Objetos escolhidos para os testes. Geometrias variadas. . . . . . . . . . 394.6 Gráfico 1: Variação do número de falhas em diferentes objetos amostrados 414.7 Gráfico 2: Variação do número de falhas em diferentes objetos amostrados 414.8 Imagem utilizada para comparação dos fatores de precisão . . . . . . . . 43

Lista de Tabelas

4.1 Tempos de amostragem em diferentes resoluções . . . . . . . . . . . . . 364.2 Tempos de aquisição de pontos com super-amostragem. . . . . . . . . . . 374.3 Tempos de renderização de imagem. . . . . . . . . . . . . . . . . . . . . 384.4 Resultados da amostragem de objetos sem super-amostragem . . . . . . . 394.5 Resultados da amostragem dos objetos com super-amostragem. . . . . . . 404.6 Variação do número de falhas e número de pontos em relação a simetria

dos objetos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.7 Análise da simetria da superfície de objetos. . . . . . . . . . . . . . . . . 424.8 Comparação de imagens renderizadas com vários fatores de precisão. . . 44

1 Apresentação

Este capítulo faz uma breve introdução do assunto tratado nesta monografia, abor-dando os aspectos que motivaram a realização do trabalho, bem como de seus objetivos,finalizando com a disposição da organização dos capítulos ao longo do texto apresentado.

1.1 Introdução

A computação gráfica tem se tornado cada vez mais uma ferramenta poderosa emdiversas áreas do conhecimento. A indústria de entretenimento, jogos eletrônicos (Quake,Doom, etc), cinema (em filmes como Matrix, Guerra nas Estrelas e Final Fantasy), e tele-visão, têm utilizado técnicas de processamento gráfico para representar mundos e objetosnão existentes, assim como reduzir custo na produção de efeitos especiais em ambientesreais.

Esta monografia inicialmente apresenta um novo paradigma para a geração de ce-nas de computação gráfica, onde são utilizados apenas pontos para representar e descre-ver a superfície de um objeto. Este novo paradigma é entitulado Computação GráficaBaseada em Pontos (CGBP), e dentro deste explora-se a amostragem de superfícies deobjetos tridimensionais (3D).

1.2 Motivação

O desafio de se conseguir melhores resultados na renderização de cenas, atravésde imagens com mais realismo, tem sido um objetivo constante de pesquisa em CG, etécnicas como Traçado de Raios [24] e Radiosidade [5] foram marcos importantes eque revolucionaram esta área da Computação Gráfica.

Porém, para criar um ambiente, uma imagem que transmita o máximo de represen-tação da realidade, é preciso haver pesquisa em novas técnicas, novos algoritmos e novosparadigmas. A Renderização Baseada em Pontos [14] (RBP), tópico dentro da Com-putação Gráfica Baseada em Pontos, pode desempenhar um papel importante na definiçãode novos mecanismos de modelagem e renderização.

Nesta abordagem, os objetos são representados como um denso conjunto de pon-tos que possuem tanto informação da sua geometria, como do material que determina aaparência deste. Nos métodos tradicionais de renderização, é necessário obter um con-junto de dados que forma uma superfície, independente de sua representação (poligonal,paramétrica, implícita, etc), para depois projetar estes pontos em uma imagem em duasdimensões. Na CGBP, parte-se da etapa onde os pontos que definem a superfície já estãodisponíveis, eliminando de certa forma uma parte do processo de renderização, que é arasterização.

Assim, grande parte da carga computacional necessária para gerar uma imagemé transferida para pré-processamento, justamente a captura dos pontos e de suas pro-priedades, permitindo que se organize estas informações de maneira que seja possíveltornar as renderizações mais rápidas.

11

1.3 Objetivos

A CGBP está atualmente em um processo de pesquisa intensa, e apesar de recente,pode viabilizar novos métodos de renderização de cenas até mesmo de forma interativa.Objetiva-se genericamente demonstrar o potencial desta abordagem como alternativa paraa geração de imagens a partir de modelos de objetos em três dimensões. Em termos maisespecíficos, existem algumas possibilidades para investigação de aperfeiçoamentos natécnica.

O objetivo principal deste trabalho é explorar a técnica de Computação GráficaBaseada em Pontos, identificando suas principais etapas e em função disto, um objetivoa ser fortemente abordado é a possibilidade de realizar uma amostragem adaptativa deobjetos, que melhor se adeque à qualquer superfície desejada.

Em se tratando de uma técnica em recente estudo intenso, existem muitos pro-blemas não muito esclarecidos na literatura atual. Assim, esta monografia demonstraalguns desses problemas, de forma bastante clara, juntamente com algumas respostas eações que abordam tais problemas. Como uma contribuição mais específica, a questãoda amostragem dos pontos em objetos, propondo métodos que visam adaptar-se à geo-metria do objeto, permitindo extrair o máximo de informação possível no processo deamostragem, facilitando a etapa de reconstrução da imagem, e melhorando sua quali-dade final. Outro ponto de destaque é a realização de uma proposta que permita resolverproblemas como a descoberta e preenchimento de falhas na imagem final renderizada,tornando esta mais isenta de artefatos. Além disto, o trabalho analisa a técnica como umanova abordagem, verificando as vantagens e desvantagens em relação a outras técnicasde geração de imagens de computação gráfica, identificando aplicações potenciais quepodem melhor se aproveitar deste modelo de renderização.

1.4 Estrutura do Texto

O texto deste trabalho está dividido em 4 capítulos, distribuídos da seguinte forma:

• Capítulo 2: Este capítulo introduz a Computação Gráfica Baseada em Pontos, con-textualizando o assunto através dos trabalhos realizados até o momento, e apresen-tando os passos gerais necessários para a renderização de imagens;

• Capítulo 3: As principais contribuições realizadas neste trabalho são apresentadasneste capítulo, demonstrando técnicas de amostragem alternativas e procedimentospara a melhoria da qualidade das imagens geradas;

• Capítulo 4: Apresenta a implementação das técnicas descritas nos capítulos ante-riores bem como os resultados (e a análise destes) obtidos a partir dos experimentosrealizados.

A monografia encerra no capítulo 5, ao abordar trabalhos que podem ser aindadesenvolvidos baseados no que foi apresentado, e ainda resumindo as considerações reali-zadas, de forma a consolidar os conceitos de Computação Gráfica Baseada em Pontos.

2 O Modelo de Computação Gráfica Baseada em Pontos

Este capítulo inicia apresentando os trabalhos mais relevantes sobre ComputaçãoGráfica Baseada em Pontos e demonstrando a evolução da técnica em ordem cronoló-gica. Em seguida, o processo de renderização de imagens é descrito de forma geral,aprofundando-se no mecanismo de geração de imagens utilizando pontos como primitivade representação. Dentro do processo, são descritas as duas etapas principais: Amostra-gem e Reconstrução de imagens. Na amostragem é realizada uma análise de um objetoseguida da obtenção de pontos que descrevam a sua superfície. Já o processo de reconstru-ção da imagem, consiste em remontar a informação contida dos pontos obtidos no passoanterior. Esta etapa é composta de pequenas outras partes com a função específica deresolver problemas causados pela possível falta de informação, como por exemplo, falhas(furos onde a cor de fundo aparece em pixels onde não deveria) na imagem gerada.

2.1 Trabalhos Anteriores

Pontos, às vezes também denominados partículas, já haviam sido utilizados pararepresentar objetos intangíveis, como neblina, fogo ou fumaça [20] [6]. O primeiro passopara o desenvolvimento desta abordagem como método de renderização de imagens foidado por Levoy e Whitted em 1985 [14], focando o caso específico de superfícies con-tínuas e diferenciáveis. Naquele momento, os autores apresentaram os primeiros con-ceitos de ponto (neste contexto, apenas coordenadas e cores), de representação geométricade um objeto para a forma de conjunto de pontos, os processos de preparação das primiti-vas (recorte, remoção de faces ocultas e filtragem de texturas) encerrando com a geraçãoda imagem propriamente dita.

Apesar do trabalho pioneiro de Levoy e Whitted, as pesquisas nesta área ficaramestagnadas por um certo tempo, até que, em 1998 Grossman e Dally [10], introduziramum mecanismo mais complexo do que o apresentado pelos primeiros autores, onde édescrito com detalhes o processo de construção de uma cena com objetos representadosapenas por pontos e os problemas encontrados.

As pesquisas realizadas sobre este assunto ganharam importância novamente como trabalho recente de Pfister et al, no ano 2000 [18] e com a disponibilidade cada vezmaior de hardware específico para amostragem espacial, como scanners 3D. No trabalhode Pfister, os autores reafirmam a proposta de Grossman e Dally e inserem novas estraté-gias como, principalmente, a amostragem dos objetos em pontos utilizando técnicas deLayered Depth Images (LDI) [22]. Resumidamente, um LDI é uma imagem onde, paracada pixel, existe um conjunto de profundidades formados pelos pontos resultantes daintersecção do raio de projeção com o objeto. O trabalho também aborda novos meiosde filtragem de textura e de remoção de falhas na imagem final. Os mesmos autoresapresentaram outras publicações, e em 2001 propõem um método para a renderização depontos chamado Surface Splatting [25], que visa melhorar a qualidade nos processos desuavização (anti-aliasing) e mapeamento de textura em RBP.

Também em 2001 Kalaiah [12] apresenta uma forma de representação de pontosamostrados, visando otimizar a dispersão desses pontos sobre superfícies com curvaturas

13

mais acentuadas. Em 2003, Alexa et al [1] apresentam um mecanismo de RBP onde adensidade já amostrada de pontos pode ser alterada, aumentando (up-sampling) a quanti-dade de pontos em áreas onde a densidade é baixa, ou diminuindo (down-sampling) emalgumas áreas, retirando de um conjunto de pontos aqueles que menos contribuem para adescrição da superfície.

Ainda em 2003 é apresentado um novo tópico na utilização de pontos como primiti-va de representação. No artigo [16] Pauly et al demonstram um framework de modelageme criação de formas utilizando primitivas híbridas, através de pontos e superfícies implíc-itas. O trabalho de Pauly também demonstra a capacidade da computação gráfica baseadaem pontos aplicada em modelagem de sólidos e processamento de geometrias com estetipo de representação.

Em comum às técnicas que amostram pontos, verifica-se que esta é feita uniforme-mente ao longo da superfície. Em processos onde a obtenção de pontos é feita comhardware especializado, esta é uma limitação intrínseca (por exemplo, em digitalizadores3D). Entretanto, em várias situações a CGBP pode ser utilizada em aplicações onde hácontrole sobre o processo de amostragem e, neste caso, uma amostragem adaptativa podetrazer benefícios nos resultados. Este trabalho explora uma possibilidade de amostragemadaptativa apresentada no capítulo 3. No ano de 2004, atestando a importância e a maturi-dade da área será realizado na Suíça o primeiro evento de Computação Gráfica Baseadaem Pontos, entitulado Point-Based Graphics inserido no Eurographics e com participaçãodo IEEE e ACM/SIGGRAPH.

2.2 O Processo de Renderização Baseada em Pontos

Neste método de renderização, os objetos em uma cena são representados atravésde conjuntos de pontos. Estes por sua vez, são amostrados traçando-se raios de três vistasortogonais de acordo com uma resolução determinada. Cada ponto amostrado é deno-minado Surfel (Surface Element) [18] e o conjunto de todos estes Surfels nos dá então aamostragem final do objeto.

Neste trabalho, os tipos de objetos utilizados têm sua representação inicial na formade polígonos quaisquer, ou triângulos, uma vez que esta é a estrutura mais utilizada paraarmazenamento da geometria de um objeto, e em geral é como este é modelado paradiversas aplicações em Computação Gráfica.

Percebe-se duas etapas bastante distintas neste processo. Inicialmente é necessárioobter um conjunto de pontos que represente a superfície do objeto, e em seguida, é precisoreconstruir uma imagem partindo destes pontos. As sessões seguintes descrevem maisdetalhadamente cada uma destas etapas denominando-as Amostragem e Reconstrução.

2.3 Amostragem de Pontos

Na CGBP a maior parte do trabalho de manipulação dos objetos é feita em pré-processamento. Whitted observou que 90%-95% do tempo de processamento da técnicade traçado de raios é gasto calculando intersecções com as superfícies [24]. Assim, secomparado a este mecanismo, é fácil observar, que, enquanto os polígonos devem ser

14

processados no momento da geração da imagem, capturando assim os pontos e transfor-mando estes para o espaço 2D, no modelo apresentado neste trabalho a fase de aquisiçãode pontos é feita de forma independente, deixando apenas a geração da imagem e apli-cação de efeitos para o processo de renderização.

Esta seção trata do processo de obtenção dos pontos que representarão um objetoutilizando recursos da técnica de traçado de raios. Problemas encontrados e mecanismosde aceleração também são discutidos nas seções a seguir.

2.3.1 Especificação dos Dados de Entrada

Os objetos utilizados para a elaboração deste trabalho têm sua representação feitaatravés de triângulos ou polígonos quaisquer, onde todos os seus vértices são coplanares.Mais especificamente, está sendo utilizado o formato de arquivo Wavefront OBJ [23],onde, além da geometria, pode se encontrar informações como cor e o comportamento domaterial perante uma fonte de iluminação.

Este arquivo deve ser processado para que se possa identificar a geometria e cap-turar pontos nesta geometria. Uma estrutura de dados deve ser criada, onde é possívelarmazenar todas as informações pertinentes sobre o objeto. Como o processo de obtençãode pontos utiliza traçado de raios, é possível já durante esta etapa calcular algumas infor-mações que futuramente serão necessárias, acelerando o processo de amostragem. Umdado importante que pode ser determinado nesta etapa é a equação do plano de cada polí-gono. A equação de um plano é dada por ax + by + cz + d = 0, onde a, b, e c são osvalores do vetor normal do polígono em questão. Para isto, considere três pontos A, B eC, vértices do polígono (ver figura 2.1), e obtenha dois vetores ~U e ~V , de acordo com asequações em 2.1 e 2.2.

Figura 2.1: Determinação de vetores na superfície de uma triângulo ou polígono.

~U = B − A (2.1)

~V = C − A (2.2)

Determine a, b e c através de ~Ux~V , conforme abaixo:

a = (yU ∗ zV ) − (zU ∗ yV ) (2.3)

b = (zU ∗ xV ) − (xU ∗ zV ) (2.4)

c = (xU ∗ yV ) − (yU ∗ xV ) (2.5)

15

É necessário ter o vetor normal encontrado anteriormente (formado por (a, b, c))normalizado. Assim pode-se encontrar d utilizando um dos vértices do polígono, con-forme a equação 2.6:

−d = a ∗ xA + b ∗ yA + c ∗ zA; (2.6)

Nesta etapa também é importante identificar uma Caixa Delimitante, formandoum paralelepípedo onde o objeto está completamente inserido. Esta informação é uti-lizada para o processamento das etapas posteriores. Esta caixa delimitante pode ser obtidaidentificando-se os maiores e menores valores das coordenadas x, y e z dos vértices quecompõe o objeto. Isto pode ser realizado na etapa de leitura do objeto.

2.3.2 Amostrando com Traçado de Raios

A amostragem de um objeto consiste na obtenção dos pontos que descrevem suasuperfície. Estes pontos podem ser capturados "disparando"raios partindo de três vistasortogonais, conforme ilustrado na figura 2.2. Esta abordagem é citada inicialmente porPfister et al, no ano 2000 em [18], e permite que sejam obtidos pontos sem perder muitosdetalhes da superfície do objeto.

Y

X

Z

Figura 2.2: Amostragem de um objeto em três planos ortogonais.

A utilização de três pontos de partida para a amostragem faz-se necessária pois, naetapa de reconstrução da imagem, deve ser possível renderizar uma cena, independenteda posição do observador. Ou seja, o objeto pode estar sendo visto por qualquer ânguloe de qualquer distância, tornando-se imprescindível ter o máximo de informação possívelpara que a reconstrução da imagem seja feita corretamente.

Um ponto é dito na superfície do objeto quando um raio disparado intercepta um dospolígonos que forma esta superfície. Neste mecanismo de amostragem, é necessário obteras informações de todos os polígonos, assim, uma pequena variação na técnica de traçadode raios é necessária. Cada raio disparado deve atravessar completamente o objeto, e paracada intersecção raio e polígono, um ponto é capturado, como mostra a figura 2.3, onde

16

o raio A atravessa a superfície do objeto, interceptando-o em dois pontos, e o raio B étangente a superfície de objeto, capturando apenas um ponto.

Figura 2.3: Intersecção entre raios disparados e a superfície de um objeto.

Acelerando com Subdivisão do Espaço

Assim como nos mecanismos tradicionais de traçado de raios, é possível acelerar esteprocesso de amostragem subdividindo o espaço onde se encontra o objeto em uma oc-tree [21]. Cada nodo desta estrutura possui informações sobre quais polígonos este nodoesta delimitando. Assim, para cada raio disparado, basta identificar quais nodos são in-terceptados pelo raio - o que pode ser feito rapidamente caminhando pela estrutura emárvore - e determinar os pontos de intersecção apenas para os polígonos contidos nos no-dos encontrados, eliminando a necessidade de varrer todos os polígonos para cada raiodisparado.

A árvore que armazena a divisão do espaço pode ter sua altura parametrizável, o queimpacta no tempo de amostragem. Quanto maior a altura da árvore, menor será o volumede cada nodo e mais precisa será a determinação dos polígonos que o raio irá interceptar.Quanto menor a altura, mais polígonos farão parte de cada nodo, fazendo com que sejanecessário calcular muitas intersecções que na realidade não atingirão polígono algum.

Porém, existe um limite para a altura da árvore onde não se consegue obter umaumento de velocidade. Este limite é dado pela relação entre o tamanho de cada nodo e asdimensões dos polígonos. Uma vez que a maior diagonal de um nodo torna-se menor ouigual a dimensão máxima do menor polígono que compõe o objeto, não é possível maisobter ganho de velocidade nesta etapa da amostragem.

Esta nova estrutura, em árvore, é utilizada pelas etapas de amostragem seguintes,que serão responsáveis por adquirir os pontos que representarão o objeto.

2.3.3 Capturando Pontos

Os pontos que representam a superfície do objeto contém a posição no espaço daintersecção raio-polígono. Porém, para a reconstrução da imagem, outras informações sãonecessárias, e que também devem ser obtidas neste momento. Cada parte da superfícieamostrada deve conter também a informação sobre o vetor normal ao ponto necessário

17

para realizar os cálculos da iluminação daquele ponto na etapa de reconstrução da ima-gem. Juntamente com a cor - tomada como a mesma cor associada ao polígono - estessão os atributos que compõe o que neste trabalho denomina-se Elemento de Superfície(Surfel).

Ponto de Partida dos Raios

A informação espacial de cada ponto é obtida disparando raios perpendiculares aos planosx = c, y = c e z = c, onde c é uma constante. Nesta etapa, é necessário determinar aquantidade de raios projetados, que caracteriza a Resolução de Amostragem r. O valorinicial da resolução de amostragem é um parâmetro definido pelo usuário. Juntamentecom os valores da caixa delimitante que envolve o objeto, é possível definir um intervalo∆d entre cada raio a ser disparado.

Os limites máximos e mínimos do paralelepípedo que envolve o objeto fornecemuma distância Dmax, que é o valor da maior dimensão deste paralelepípedo. Com isto, épossível encontrar ∆d = Dmax/r (ver figura 2.4), que seja sempre a mesma utilizada paraamostrar todos os três pontos de visão do objeto. Usar a maior dimensão do objeto paracalcular a distância entre os raios faz com que se tenha também a maior distância entre osraios, permitindo que o usuário ajuste o valor de r de acordo com o tamanho do objeto.Este recurso insere homogeneidade entre os pontos obtidos, fazendo com que a distânciaentre pontos adjacentes seja a mesma para cada eixo amostrado. Esta característica podeser utilizada para melhorar o desempenho de qualquer cálculo aplicado a um conjunto depontos.

Figura 2.4: Intervalo ∆d de amostragem de um objeto.

O intervalo ∆d é utilizado então para calcular a posição e a direção dos raios, sendoque a posição inicial é definida pelos limites do objeto, com um recuo em uma unidade novalor da coordenada referente ao eixo do vetor direção. Esta direção é determinada pelosvetores que descrevem os eixos de coordenadas, ou seja, os vetores unitários [1 0 0], [0 10] e [0 0 1].

Pode-se tomar como exemplo uma esfera de raio 1 e centralizada na origem, per-feitamente contida em um cubo com lado 1, como ilustrado na figura 2.5. A ordem emque os planos são tomados para amostragem é arbitrária, assim como o ponto em que se

18

inicia o traçado de raios, desde que este esteja sobre uma das bordas do cubo, o que fa-cilita os cálculos. Neste caso pode-se tomar fazer a amostragem do primeiro plano usandoz = c, tendo o início do primeiro raio em [-1 -1 -2] (ponto destacado na figura 2.5), e comsua direção definida pelo vetor [0 0 1]. O valor -2 para a coordenada z da posição inicialé resultado da aplicação do recuo citado anteriormente, calculado fazendo z − 1 = −2,onde z = −1. Isto evita que um ponto válido exatamente na posição inicial da borda caixaque delimita o objeto (em [-1 -1 -1]) seja perdido por erro de precisão de ponto flutuantenos cálculos de intersecção.

Figura 2.5: Esquema de traçado de raios utilizado no processo de amostragem.

Uma vez definida a posição inicial, no exemplo [-1 -1 -2], basta ir incrementando ovalor de ∆d para todas as coordenadas que têm valor zero no vetor direção, neste caso, xe y. Isto se repete até que tenha sido alcançado a borda que delimita o objeto.

Calculando Pontos no espaço

Com uma posição inicial para o raio e um vetor direção, é possível determinar se esteraio intercepta um polígono e em que ponto no espaço isto ocorre. Glassner descreve esteprocesso com detalhes em [8] e é facilmente compreendido em três etapas:

• Verificar se o raio não é paralelo ao plano onde o polígono está contido;

• Calcular o ponto onde a intersecção raio-plano ocorre;

• Verificar se este ponto pertence ao polígono;

Neste momento, faz-se uso da equação do plano calculada no momento da leiturado arquivo. Com um vetor formado por a, b, e c, pode-se determinar se o raio é ounão paralelo ao plano, através do produto escalar vd entre este vetor e o que determina adireção do raio, como apresenta a equação 2.7. Caso vd = 0, o raio é paralelo ao plano, enenhuma intersecção ocorre.

19

vd = a ∗ xd + b ∗ yd + c ∗ zd (2.7)

Caso vd 6= 0, deve-se então calcular a posição no espaço onde o ponto de inter-secção se encontra utilizando os valores de a, b, c e d da equação do plano e as coorde-nadas O de origem do raio. Isto é feito encontrando um valor t que determina a distânciaentre o ponto inicial (inicio do raio disparado) até o plano, como mostram as equaçõesque abaixo:

vo = −(a ∗ xo + b ∗ yo + c ∗ zo) + d (2.8)

t = vo/vd (2.9)

O valor de t deve sempre ser maior que zero, pois, o contrário significa que oplano estaria atrás da origem do raio, o que neste caso não deve ocorrer. O ponto deintersecção raio-plano é calculado como nas equações 2.10, 2.11 e 2.12, onde (x, y, z)O

são as coordenadas de origem do raio e [x, y, z]d é o vetor direção do raio.

xp = xo + xd ∗ t (2.10)

yp = yo + yd ∗ t (2.11)

zp = zo + zd ∗ t (2.12)

O ponto encontrado fornece a posição no espaço da intersecção do raio com o planoque suporta o polígono, e não necessariamente este ponto pertence a este polígono. Ummétodo para determinar se um ponto está ou não contido em um polígono qualquer édescrito em [8] que baseia-se no algoritmo descrito por Blinn em [3]. Este procedimentoconsiste em projetar um raio em uma direção arbitrária partindo do ponto de intersecçãoe contando o número de seguimentos (arestas) que este raio corta. Caso este número forímpar, o ponto está dentro do polígono. Caso contrário, o ponto está fora.

Primeiramente é necessário projetar o polígono em um plano bi-dimensional. Istopode ser feito facilmente apenas eliminando uma das coordenadas dos vértices. Estapode ser a coordenada do vetor normal do polígono que possui maior valor absoluto. Emoutras palavras, se ~N = (0,−5, 3) é o vetor normal ao plano cujo polígono em questãoestá inserido, a coordenada do eixo y deve ser eliminada nos vértices. Esta técnica garanteque o polígono será projetado em um plano 2D utilizando a maior área possível.

As coordenadas restantes devem ser renomeadas como U e V , e o polígono deve sertransladado de forma que o ponto de intersecção fique na origem, o que pode ser obtidosubtraindo as coordenadas deste ponto (Ui, Vi) de cada vértice. Estes novos vértices de-vem ser nomeados como (U ′, V ′). O pseudo-algoritmo a seguir descreve os passos finaisdo processo.

1. defina NC como o número de intersecçõese com o valor zero;

2. defina SH como o controle de sinal,em função de V’0

(valor de V’ para o primeiro vértice da primeira aresta);atribua SH = -1 se V’0 for negativoatribua SH = +1 se V’0 for positivo

20

3. considere NV como o número de vértices,formando uma lista (U’n, V’n);

4. para cada aresta do polígono formadapelos pontos (U’a, V’a) e (U’b, V’b),onde a = 0 até NV-1, b =((a+1) mod NV):

defina o atributo de sinal NSH para -1caso V’b for negativoe para +1 caso contrário;se SH \neq NSH:se U’a é positivo e U’_b é positivoentão, NC = NC+1;

caso contrário,se U’a for positivo ou U’bfor positivo então:se U’a - V’a * (U’b - U’a) / (V’b - V’a) > 0

então NC = NC+1;SH = NSH;

5. continuar os vértices partindo do passo 4.

Capturando a normal do ponto

A estrutura geométrica do objeto fornece os vetores normais para cada vértice dos polí-gonos que o compõem. Estes vetores são utilizados para calcular a influência da fonte deluz sobre a superfície deste objeto. No processo conhecido como Gourad Shading [7] ospontos do interior do polígono tem seu vetor normal sendo resultado da interpolação pon-derada dos vetores normais dos vértices. Esta técnica permite atribuir cores à superfíciedo objeto, causando um efeito visual mais realístico.

Para que seja possível obter esta mesma qualidade, deve-se calcular os vetores nor-mais para cada ponto já no momento da amostragem. A técnica utilizada neste trabalhopara obter a normal de cada ponto em função dos vértices baseia-se no conceito de Coor-denadas Baricêntricas [15].

As Coordenadas Baricêntricas fornecem um ponto P como sendo o Centróide Ge-ométrico de três massas (t1, t2, t3) que compõem um triângulo ∆ABC, como mostra afigura 2.6. Uma analogia ao processo inverso permite determinar fatores de peso (u, v, w)que representem o balanceamento entre o ponto P e os vértices do triângulo, como mostraa figura 2.6. Considera-se o uso de coordenadas baricêntricas onde t1 + t2 + t3 = 1 eu + v + w = 1, de forma que seja possível identificar a influência de cada vértice ABCsobre o ponto P .

Os valores de u, v e w podem ser determinados de acordo com as equações 2.13,2.14 e 2.15 respectivamente.

u =area(ABP )

area(ABC)(2.13)

21

Figura 2.6: Representação das coordenadas baricêntricas em um triângulo.

v =area(BPC)

area(ABC)(2.14)

w =area(APC)

area(ABC)(2.15)

A função area resulta na área de um triângulo qualquer e pode ser calculada uti-lizando o produto vetorial dos vetores que determinam os vértices este triângulo, comomostra a equação abaixo:

area(ABC) =|(B − A) × (C − A)|

2

Uma vez determinado (u, v, w), pode-se calcular a normal em P em função das nor-mais dos vértices A, B e C (estas normais devem ser unitárias), como mostra a equação2.16.

~NP = ~NA ∗ u + ~NB ∗ v + ~NC ∗ w (2.16)

O vetor ~NP é então atribuído como o vetor normal do ponto amostrado.As Coordenadas Baricêntricas são aplicáveis apenas em triângulos. Como os obje-

tos utilizados podem estar descritos como polígonos quaisquer, é necessário dividir estesde uma maneira adequada. Um processo de triangularização possível é feito, unindo con-juntos de três vértices em seqüência, como mostra a figura 2.7. Esta triangularização nãoprecisa alterar a representação geométrica do objeto, ou seja, pode ser realizada apenaspara realização deste procedimento.

Porém esta triangularização não precisa ser realizada para toda a superfície do polí-gono, pois é necessário apenas identificar um triângulo onde o ponto amostrado estejacontido. É possível que mais de um conjunto de 3 vértices forme triângulos que satis-façam esta condição, de fato, esta escolha pode ser arbitrária, uma vez que os valores de

22

Figura 2.7: Divisão de um polígono em um conjunto de triângulos.

(u, v, w) vão ser sempre coerentes ao conjunto de vértices escolhidos. Esta escolha nãocausa artefatos nas imagens renderizadas.

Neste trabalho o triângulo escolhido é aquele formado pelos três primeiros vérticesmais próximos ao ponto em questão. Esta proximidade é determinada pela distânciaeuclidiana dos vértices dos pontos. A figura 2.8 ilustra esta idéia. As linhas pontilhadasdefinem triângulos onde o ponto pode estar inserido e a linha contínua o triângulo formadopelos vértices mais próximos a este ponto.

2.3.4 Armazenando os Pontos Obtidos

Neste trabalho as informações dos elementos de superfície são armazenadas naforma de listas simples, utilizando três listas, uma para cada vista de amostragem. Istojá fornece algumas vantagens, pois permite que o comportamento simétrico da posiçãoespacial de cada ponto diminua o número de operações em alguns cálculos do processode reconstrução da imagem. Outras formas que utilizam estruturas de dados mais com-plexas podem requintar ainda mais o processo. Pfister propõe em [18] que os pontossejam agrupados em uma representação que consiste na união dos conjuntos amostrados.Esta representação é denominada de LDC (Layered Depth Cube), que é construída sobuma octree incompleta e de altura parametrizável, onde nas folhas encontram-se os pontosamostrados.

Uma vez determinada a estrutura de dados a ser utilizada, a amostragem pode ser ar-mazenada em arquivos. Isto tem um valor muito importante, pois mesmo sendo o processode amostragem demorado, ele só precisa ser executado uma única vez para cada objetoamostrado. Qualquer imagem relativa ao objeto amostrado pode ser gerada partindo-sede uma única tomada de pontos.

23

Figura 2.8: Determinação do triângulo que contém um ponto em um polígono.

2.4 Reconstrução de Imagens

Com um conjunto de pontos amostrados é possível reconstruir uma imagem a partirdestes. Deseja-se projetar o conjunto de pontos obtidos na etapa de amostragem, no es-paço 3D, para uma imagem em 2D com uma resolução previamente definida pelo usuário.Para isto, são utilizadas as técnicas de operações de câmera sintética [7], aplicando ope-rações com matrizes de forma a mapear as coordenadas dos pontos e de suas normais doantes espaço de objeto, para um espaço de câmera.

As etapas necessárias para esta operação são:

• Projetar os pontos no espaço para uma viewport pré-definida;

• Associar as coordenadas na viewport com as coordenadas de tela (2D);

• Testar a visibilidade do pixel no ZBuffer;

• Calcular a cor do pixel considerando as propriedades materiais e fontes de luz;

Existe ainda uma etapa de pós-processamento da imagem que visa preencher pos-síveis falhas de cobertura dos pixels. Isto se dá em virtude que, as transformações reali-zadas no objeto, magnificação (efeitos como zoom) e a distorção da projeção perspectivaconforme a posição do observador, podem tornar a resolução escolhida para a amostragemdo objeto não suficiente. Este efeito também é causado caso a resolução da imagem a sergerada for muito superior à resolução amostrada. Métodos para resolver este tipo deproblema são discutidos de forma geral na seção 2.4.2 e uma solução desenvolvida nestetrabalho é apresentada na seção 3.3.

2.4.1 Reconstruindo com Projeção Perspectiva

Para realizar a projeção perspectiva, é preciso estabelecer as informações da câmerae da área de visualização do objeto, denominada Frustum [7]. Este Frustum delimita o

24

espaço onde o objeto está inserido por seis planos, na forma de um tronco de pirâmide (verfigura 4.2). Isto significa que apenas pontos que estejam contidos neste volume devem serprojetados, eliminando cálculos desnecessários com pontos não visíveis. Além disto, oplano mais próximo da câmera fornece a janela de visualização (viewport), onde os pontosserão projetados ainda em coordenadas no espaço.

Considera-se neste trabalho, sem perda de generalidade, que a câmera está cen-tralizada na origem, tendo o vetor do observador no sentido do eixo z positivo [0 0 1],e o vetor que define a direção superior no sentido do eixo y positivo [0 1 0]. Natural-mente, o frustum deve acompanhar o sentido da câmera e o objeto deve estar contidoneste frustum para poder ser visualizado. Tomando estes cuidados os cálculos necessáriostornam-se mais simples. Do contrário, é necessário realizar as operações de transfor-mação necessários sobre o objeto para que esta configuração seja atingida. Em outraspalavras, passar o objeto do sistema de coordenadas do universo, para o sistema de coor-denadas da câmera.

Cada ponto deve ser projetado para a janela de visualização considerando sua posiçãono espaço. Porém, esta projeção eliminará a coordenada z de cada ponto, fornecendo ascoordenadas desse ponto em uma janela de visualização em duas dimensões. Isto é feitoutilizando as profundidades do ponto em questão z e da janela de visualização d, cal-culando w = z/d. As novas coordenadas xp e yp são obtidas simplesmente calculandoxp = x/w e yp = y/w [7].

Os valores de xp e yp permitem calcular as coordenadas com valores inteiros daposição do pixel que este ponto representa na imagem, utilizando as dimensões da janelade visualização. As coordenadas discretizadas x′ e y′ também indexam as informaçõesno ZBuffer. É possível que dois ou mais pontos projetem no mesmo pixel, porém apenaso mais próximo deve ser mantido. Um simples teste de profundidade no ZBuffer [4]permite saber se o ponto projetado está na frente ou atrás de algum outro já projetado.

No ZBuffer também é armazenada a cor do pixel, que é resultado da aplicação dasfontes de luz sobre a cor previamente obtida na amostragem. O modelo de iluminaçãoutilizado aqui é o modelo de Phong [19]. A figura 2.9 mostra o resultado do processode reconstrução completo com uma imagem gerada pelo protótipo desenvolvido nestetrabalho.

Figura 2.9: Imagem renderizada através de RBP.

25

Estas operações são realizadas para todos os pontos amostrados. Nesta monografianão está sendo considerado nenhum mecanismo de melhoria nos cálculos envolvidosporém algum mecanismo que acelere as operações pode ser desenvolvido tirando proveitoda coerência existente entre os pontos amostrados. Também não está sendo realizadorecorte dos pontos no Frustum, apenas identificando quais pontos estão fora da janela devisualização por scissoring [7].

O processo de reconstrução de imagens é fortemente afetado pela amostragem dospontos. Na figura 2.10 pode-se notar este fato de forma bem destacada. Estas imagensforam renderizadas com uma resolução final de 2562 pixels, sem receber pós proces-samento para preencher falhas. A imagem da esquerda, 2.10(a), representa um objetoamostrado com o valor de resolução igual a 2003, e pode-se notar um número bem supe-rior de falhas do que a da imagem da direita, 2.10(b), onde a resolução de amostragem foiaumentada para 4003.

(a) (b)

Figura 2.10: Renderização de um objeto amostrado em resoluções diferentes

A imagem final tem resolução de 2562, e em (a) tem-se um objeto amostrado em 2003,enquanto que em (b) a amostragem foi de 4003.

Considerando este fato, uma das principais contribuições deste trabalho é umasolução que visa melhorar a amostragem de um objeto adaptando-se a sua superfície éapresentada na seção 3.1.

2.4.2 Preenchendo Falhas Existentes

A amostragem do objeto fornece um conjunto de pontos baseado na resolução deamostragem solicitada pelo usuário. Em alguns casos, esta resolução pode não ser su-ficiente para gerar uma imagem perfeita, ou seja, podem existir pixels que não estãopreenchidos com a cor correta, ou mesmo sem cor alguma. A figura 2.11 ilustra falhas decobertura em uma imagem.

Uma falha pode ser formada quando nenhum dos pontos amostrados é projetado emum pixel que deveria ser preenchido. Este tipo de falha é referenciado como falha comfundo de imagem. Ainda, quando um pixel está preenchido com alguma cor que faz parteda superfície do objeto que não deveria estar visível, a falha causada é denominada falhade superfície. Este último caso é comum acontecer considerando-se que na projeção

26

Figura 2.11: Imagem com falhas de preenchimento. A resolução de amostragem é 1003 ea da imagem renderizada é de 2562

perspectiva os pontos mais próximos à câmera serão projetados em pixels mais distantesum do outro do que os pontos mais distantes.

Na figura 2.12 é possível notar a falha de superfície (em verde), causada pela pro-jeção de pontos que fazem parte da área não visível do objeto. O pixel em branco re-presenta uma falha de fundo de imagem, onde nenhum ponto projeta para aquele pixel,quando deveria.

A resolução final da imagem também influencia no surgimento de falhas. Quantomaior a resolução desejada, maior a distância entre os pixels, aumentando a probabili-dade de existir falhas entre estes pixels. No caso de menores resoluções, mais pontosprojetaram no mesmo pixel ou em arredores, diminuindo a distância entre eles, e conse-qüentemente o número de falhas.

De forma que não seja necessário reamostrar este objeto, deve-se de alguma maneirapreencher os pixels que não contém informação de cor. Esta etapa é um tanto delicada,uma vez que pode ser complicado quando uma falha é autêntica ou não.

Zwicker utiliza uma técnica denominada Surface Splatting [25] que evita o surgi-mento deste tipo de problema já no momento da projeção dos pontos. Ao invés de umponto representar exatamente um pixel na tela, este ponto incidirá em uma área no frame-buffer. Esta área descreve uma forma elíptica determinada pelo EWA (Eliptical WeightedAverage), onde os pixels mais distantes do centro da elipse possuem um peso mais baixo.Este peso é utilizado para determinar a influência daquela cor no pixel em questão, umavez que diversas elipses podem estar sobrepostas.

Outra solução, proposta por Grossman, analisa os pixels vizinhos daquele ondeocorreu a falha, comparando a profundidade no ZBuffer. Uma vez identificado se aquelepixel é uma falha autêntica, sua cor deve ser preenchida, e para isto, uma técnica semel-hante ao mapeamento de texturas com Mip-Map. Várias imagens com menores resoluçãosão geradas, até que o pixel equivalente ao que tem falha esteja preenchido. A cor destepixel é utilizada então para preencher a falha na imagem original.

27

Figura 2.12: Falhas de superfície e de fundo de imagem. A área em verde representa umafalha de superfície, e a em branco, uma falha de fundo.

Este trabalho propõe um novo mecanismo para preenchimento de falhas que visaobter a melhor relação entre tempo de processamento e qualidade da imagem. Estasolução é apresentada na seção 3.3.

2.5 Aplicações da CGBP

A técnica de renderização baseada em pontos tem tomado importância na comu-nidade apenas recentemente, apesar de ter trabalhos iniciados há algum tempo. Muitosestudos estão sendo realizados, tanto para melhorar os procedimento existentes como paradeterminar novas aplicações possíveis.

Neste trabalho, os pontos foram capturados em objetos representados por polí-gonos. No entanto, a técnica pode ser facilmente aplicada em objetos que já têm suasuperfície capturada como conjunto de pontos, por exemplo, através de scanners 3D.Levoy et al demonstram esta aplicabilidade no projeto Michelangelo [13] (ver figura2.13, onde o conjunto de pontos é obtido varrendo a superfície de estátuas.

Outras aplicações em áreas como geociências [11], dados volumétricos como emaplicações médicas [9] e visualização de fluidos [17] também fazem uso de pontos pararepresentar superfícies explicitamente. Isto mostra que, independente da fonte, qualquersuperfície que estiver representada por pontos pode gerar imagens reconstruídas atravésdos mecanismos citados nesta monografia.

A modelagem de formas de objetos também pode tirar proveito da representaçãopor pontos. Aplicar efeitos como deformações ou distensões em superfícies represen-tadas por triângulos por exemplo, implica em problemas como realizar a alteração dasuperfície de acordo com o que a disposição dos vértices dos triângulos. Em casos que sedeseja uma fidelidade maior, talvez seja necessário dinamicamente subdividir a superfície

28

visando aumentar o nível de detalhes. Em superfícies representadas por pontos, aplicarestes efeitos torna-se mais simples, uma vez que já existe um alto nível de detalhe comuma primitiva fundamental como um ponto. A liberdade e a facilidade para movimentarpontos no espaço é maior do que com polígonos, em virtude da independência de umponto em relação ao outro, o que não acontece com vértices de triângulos por exemplo.

O mesmo acontece em situações onde deseja-se remover partes do objeto ou atémesmo fundir dois objetos. Remover uma área de um objeto representado por pontosconsiste em apenas remover os pontos que dizem respeito aquela área. Unir dois objetosou parte destes também torna-se simples neste abordagem, bastando adicionar o conjuntode pontos do um objeto à representação do outro.

Figura 2.13: Estátua de David, parte do projeto Digital Michelangelo, sendo capturadapor um scanner 3D.

3 Amostragem Adaptativa e Preenchimento de Falhas

As falhas geradas na imagem final podem ser diminuídas melhorando a amostragemdo objeto. Isto pode ser feito simplesmente aumentando a resolução de amostragem, oque levaria a um aumento homogêneo na quantidade de pontos amostrados. Uma outrasolução é obter um número maior de pontos apenas em áreas onde se faz mais necessário.Estas áreas correspondem intuitivamente a partes da superfície do objeto que possuemuma certa curvatura. Quanto mais acentuada for esta, mais pontos seriam necessáriospara representá-la corretamente.

O problema pode ser imaginado, analisando-se dois raios adjacentes sendo dispara-dos contra uma superfície. Quanto mais próximo de zero for o ângulo entre este raio e anormal da superfície em questão, mais próximos estarão os pontos amostrados. Porém, amedida que o ângulo entre o raio e o plano do polígono vai se aproximando de 90 graus,mais distantes ficam os pontos amostrados, criando a possibilidade de gerar falhas narenderização da imagem. Pode-se observar este fato na figura 3.1, onde em (a) tem-sedois raios disparados contra uma superfície perpendicular a estes e uma distância d1 entreos pontos de intersecção. Esta distância aumenta na figura (b) conforme a inclinação dasuperfície aumenta em relação aos raios, tendo como resultado d1 < d2 < d3.

A melhoria na amostragem de superfícies representada por polígonos descrita nestetrabalho é denominada Amostragem Adaptativa, e é apresentada na próxima seção.

3.1 Amostragem Adaptativa

O processo de Amostragem Adaptativa tenta sempre manter os pontos amostradoso mais próximos possíveis, sendo que a distância máxima aceita é definida pela resoluçãoda amostragem inicial.

A solução proposta permite determinar a necessidade de amostragem mais densaem função da inclinação local da superfície, que é identificada por um ângulo θ entreo raio e o vetor normal à superfície no ponto de incidência. Um novo valor ∆d′ deveser calculado de acordo com ∆d′ = ∆d. cos θ (aproveitando-se do valor já calculado doproduto escalar entre os vetores do raio de incidência e a normal à superfície).

Isto pode ser observado na figura 3.1, onde em (a) tem-se a distância entre doisraios (∆d) ortogonais a superfície (θ=0◦) descrevendo exatamente a distância entre doispontos. Já em (c), mantendo ∆d em uma superfície inclinada aos raios (0◦< θ <90◦),a distância entre os pontos é aumentada na dimensão representada pelo segmento con-tínuo. O segmento pontilhado representa a distância que os pontos deveriam manter, ouseja exatamente ∆d. Quanto maior for θ, menor o novo intervalo entre os raios. Raiosortogonais ao vetor normal (θ=90◦) não são considerados como intersecções válidas.

Este novo passo de intervalo calculado deve ser utilizado para realizar uma super-amostragem local, ou seja, o valor de ∆d é mantido como passo original entre os raios.Novos pontos são capturados iterativamente, em torno de cada ponto original, porém,desta vez utilizando o intervalo ∆d′. É importante observar que a resolução de amostrageminicial deve ser tal que possibilite atingir todos os polígonos do objeto. Caso isto nãoocorra, a amostragem adaptativa não terá efeito sobre estes polígonos, já que nem um raio

30

Figura 3.1: Intervalo ∆d′ entre os pontos amostrados. Em superfícies mais inclinadas ovalor do intervalo deve ser corrigido para manter a distância original entre os pontos.

o atingiu.Com isto é possível garantir uma distância mínima entre pontos adjacentes, que na

etapa de renderização potencialmente diminui a quantidade de falhas na imagem. Umaamostragem ideal garante que sejam projetados no mínimo um ponto por pixel para umadeterminada distância entre o observador e o objeto.

3.2 Ajustando a Super-Amostragem

Para fornecer mais flexibilidade ao processo de Amostragem Adaptativa, foi cri-ado um fator k que atua sobre o novo intervalo ∆d′. Este intervalo é ajustado fazendo-se cos θk, e pode-se notar que variando k é possível fazer com que mais pontos sejamamostrados (diminuindo o intervalo), ou até mesmo que não seja capturado nenhum novoponto (aumentando o intervalo).

Este ajuste permite a aumentar o nível de detalhe capturado em regiões onde a cur-vatura é mais acentuada. Pode-se ainda refinar o procedimento evitando de capturar pon-tos onde não é tão necessário, considerando realizar a super-amostragem, por exemplo,apenas em locais com inclinação maior que 45◦ (cos θ ≤ 0.707). Como a amostragemé feita a partir de três vistas, regiões menos curvas para uma vista podem ser regiõesmais curvas para outra, fazendo com que a amostragem seja realizada com mais detalhesapenas quando necessário.

3.3 Resolvendo a Etapa de Renderização

Uma forma de determinar um pixel com falha e atribuir a ele a cor mais adequada éanalisando os pixels ao seu redor. Este pixel passa a ser o centro de um quadrado que de-fine quais pixels são seus vizinhos. O tamanho do lado deste quadrado é determinado pela

31

maior distância possível de ser obtida entre dois pontos adjacentes (pontos amostrados).Isto pode ser facilmente determinado utilizando o valor de ∆d calculado na amos-

tragem (ver seção 2.3.3). Aplicando as equações de projeção em ∆d, e considerando-sea distância da câmera exatamente igual a distância da janela de visualização, obtém-sea distância máxima em pixels entre 2 pontos adjacentes, no pior caso. Se esta distânciafor menor que 1 então, considera-se como tendo o valor 1. Por exemplo, se a distânciamáxima em pixels for 2, o quadrado será formado por uma matriz 5 × 5.

Determinada a vizinhança onde os pixels serão analisados, basta analisar a infor-mação de cada pixel no ZBuffer, porém, isto precisa ser feito diferentemente para cadacaso.

Para as falhas onde nenhum ponto convergiu para um pixel que deveria ser pre-enchido (falha de fundo de imagem), deve-se contar os pixels os quais tiveram algumponto projetado. Além disto, é necessário determinar a cor do pixel somando as cores dosvizinhos preenchidos ou somando a cor de fundo da imagem. Com isto, é possível obteruma cor final resultado da média das cores dos pixels ao redor, causando um efeito desuavização, e completando a falha.

Porém, é possível que o pixel analisado realmente não deva ser preenchido, exigindouma análise mais sutil. Este método pode confundir-se nos casos onde um pixel está pertoda borda do objeto, pois se considerar a cor dos vizinhos, o resultado da cor não será ocorreto.

Para resolver este problema, foram criados fatores de precisão, aplicáveis aos doistipos de falhas existentes, que devem ser ajustados pelo usuário. Estes fatores variamentre zero e um, e devem ser comparados com o resultado da razão entre os pixels queestão à frente do pixel analisado, e do total de pixels computados. O teste de proximidadeé feito verificando os valores de zv dos pixels vizinhos e comparando com o valor de zp

do pixel em questão. Para que um pixel seja considerado à frente a equação zv − zp > ∆dtem que ser válida, uma vez possam existir pixels atrás do pixel em análise, porém emuma distância inferior à distância máxima entre os pixels (dada por ∆d). Caso a razão forsuperior ou igual ao fator, então o pixel deve ser preenchido. Quanto maior este fator, maispreciso será o preenchimento, no entanto, é possível que falhas não sejam identificadascorretamente.

A figura 3.2 ilustra este processo, onde no centro de cada área há um pixel comfalha (de cor branca). Os quadros hachurados representam pixels preenchidos, porém nãoà frente do pixel do centro, já os em cinza representam pixels preenchidos e que estão àfrente do pixel em análise.

Porém, quanto menor for o fator, mais relaxada será a análise podendo até causarefeitos como borrões na silhueta do objeto. A figura 3.3 ilustra o efeito causado variandoo valor deste fator de precisão. No detalhe das imagens, pode-se ver em 3.3(a) o objetorenderizado com um fator de precisão de 0.85, ajustado para ser ideal. Na figura 3.3(b), ofator de precisão foi reduzido para 0.05.

No caso de falhas de superfície, a analogia é a mesma, porém, na área analisadasão contabilizados apenas os pixels que contribuem com alguma cor, ignorando a cor defundo. Além disto, os pixels devem conter um valor de profundidade z menor que o pixelque está sendo verificado. Isto garante que os pixels que contribuirão para a nova correalmente estão na frente. A cor final também é resultado da média dos pixels que con-tribuíram, e um fator de precisão também deve ser utilizado porém, deve ser comparado

32

Figura 3.2: Área de análise para a determinação de falhas ao redor de um ponto. Em(a), apenas um pixel não está à frente do pixel do centro, resultando numa razão de 7/8 =0, 875. Em (b) esta razão diminui para 5/8 = 0, 625, e em (c) para 3/8 = 0, 375. Supondoque os fatores de precisão escolhidos sejam de 0,5, os casos (a) e (b) teriam o pixelpreenchido.

(a) (b)

Figura 3.3: Imagens variando o fator de preenchimento de falhas de fundo. (a) Renderi-zação com fator de precisão para preenchimento de falhas de fundo de valor igual a 0,85.(b) Mesma renderização, porém com fator de precisão igual a 0,05, causando borrões nasilhueta.

33

com a razão entre os pixels que contribuíram para a cor e do total de pixels que tem al-guma cor, lembrando que na área analisada podem existir pixels que estão preenchidoscom a cor de fundo.

A figura 3.4 (com magnificação) ilustra a os efeitos causados pela variação do fa-tor de precisão no caso do preenchimento de falhas de superfície. A imagem em 3.4(a)apresenta uma renderização com fatores de preenchimento ideal (0.45) enquanto que em3.4(b) o fator foi exageradamente relaxado (0.05). Os pixels tiveram sua cor alteradas,tornando a aparência do objeto disforme.

(a) (b)

Figura 3.4: Imagens variando o fator de preenchimento de falhas de superfície na imagem.(a) Renderização com fator de precisão para preenchimento de falhas de superfície devalor igual a 0,45. (b) Mesma renderização, porém com fator de precisão igual a 0,05.

É fácil perceber a complexidade em determinar se uma falha é autêntica ou não. Oprocedimento de analisar os pixels vizinhos ao pixel com falha pode estar considerandooutros pixels, também com falhas para resolver o problema do primeiro. Mesmo assim, assoluções apresentadas fornecem bons resultados visuais. Na seção 4.2.3 serão demonstra-dos alguns resultados obtidos utilizando estes métodos de preenchimentos de falhas nasimagens renderizadas.

4 Implementação e Resultados

Este capítulo apresenta o SARS - Sistema de Amostragem e Reconstrução deSuperfícies - um sistema protótipo que implementa as técnicas de amostragem de pontose reconstrução de imagens apresentadas nos capítulos anteriores. Será possível observartambém o comportamento das soluções aplicadas aos problemas intrínsecos à RBP. Comisto, uma seção apresentando os resultados obtidos e comparando experimentos encerra ocapítulo.

4.1 O Sistema Protótipo SARS

Este sistema foi criado para consolidar o mecanismo de CGBP apresentado nestetrabalho. No SARS é possível carregar arquivos com o modelo de um objeto no formatoOBJ, amostrar pontos neste objeto permitindo que o usuário escolha uma resolução inicialde amostragem e ainda, ajustar a densidade de super-amostragem se desejado.

A figura 4.1 apresenta a janela inicial do sistema, onde se destacam os itens parapersonalização da amostragem, e os dois painéis que mostram o objeto. O usuário podecarregar modelos de objetos, salvar os pontos amostrados e ainda carregar um conjuntode pontos já capturados.

Figura 4.1: Janela principal do SARS

No painel da esquerda nota-se o objeto reconstruído a partir do seu formato orig-inal (representado por polígonos). O painel da direita mostra os pontos resultantes da

35

amostragem dispersos no espaço. Ambas representações do objeto são apresentadas uti-lizando OpenGL, apenas para permitir a comparação do objeto original com o represen-tado por pontos.

A geração de uma imagem também pode ser realizada permitindo que o usuáriocontrole os fatores de precisão de cobertura de falhas (ver seção 2.4.2) para os dois tiposde falhas que podem ocorrer. Na figura 4.2 pode se observar estas opções bem comoa possibilidade de informar a resolução que a imagem reconstruída deverá ter. Nota-setambém um frustum que está orientado por uma câmera fixa na origem e observando emdireção ao eixo z positivo. Os planos deste frustum também podem ser controlados pelousuário.

Figura 4.2: Controles para renderização do SARS

4.2 Resultados Obtidos

Os resultados apresentados a seguir demonstram as saídas obtidas nas etapas deamostragem e renderização de imagens. As imagens geradas pelo SARS tem sua quali-dade afetada pelos fatores informados pelo usuário como resolução inicial de amostragem,altura da árvore, super-amostragem, fatores de preenchimento de falhas e resolução finalda imagem. Comparativos variando estes parâmetros são analisados considerando a qual-idade da imagem gerada e tempo de duração dos procedimentos.

Todos os testes apresentados foram realizados em um computador com processadorAthlon 1.1GHz com 256MB de RAM, sem a utilização de hardware específico para pro-cessamento gráfico.

36

4.2.1 Analisando a Amostragem

As imagens que seguem apresentam a amostragem de um mesmo objeto, variando-se apenas a resolução inicial de amostragem, sem utilizar nenhum mecanismo de superamostragem. Para todos as imagens demonstradas foi utilizado OpenGL apenas paraexibir o conjunto de pontos.

A figura 4.3 mostra a representação em pontos do modelo de um tie-fighter. Aimagem em 4.3(a) foi amostrada com resolução 2003, em 4.3(b) a resolução é de 4003 eem 4.3(c) tem-se a resolução de 6003.

(a) (b) (c)

Figura 4.3: Amostragem de um objeto em várias resoluções . (a) 2003, (b) 4003 e (c)6003. As imagens geradas tem resolução de 2562

Em todos os objetos amostrados pode-se observador uma melhora na representaçãoda superfície do objeto pelo conjunto de pontos obtidos à medida que a resolução au-menta. Naturalmente isto implica em um aumento no número de pontos e também notempo de processamento. A altura da árvore que subdivide o espaço do objeto (ver 2.3.2)influencia bastante no tempo da amostragem. A tabela 4.1 demonstra esses resultadosconsiderando número de polígonos do objeto e número de pontos gerados. O tempo deamostragem também é considerado utilizando árvores de altura 3 e 4.

Objeto N◦ Poli. Resolução N◦ Pontos Tempo (altura 3) Tempo (altura 4)

águia 1652 200 34992 2s 1ságuia 1652 400 140051 7s 3ságuia 1652 600 315388 16s 8s

chimp 3786 200 97037 3s 1schimp 3786 400 388085 12s 5schimp 3786 600 873153 26s 12s

Tabela 4.1: Tempos de amostragem em diferentes resoluções

Os efeitos causados pela super-amostragem podem ser visualizados na figura 4.4,com uma amostragem inicial fixa em 2003, variando apenas os parâmetros pertinentes esem utilizar nenhum refinamento para ignorar inclinações mais ou menos acentuadas. Na

37

imagem à esquerda tem-se o objeto representados por pontos sem super-amostragem. Nocentro, utilizando super-amostragem com k = 1 (super-amostragem normal), e na direitaa imagem representa a super-amostragem com k = 1.25.

(a) (b) (c)

Figura 4.4: Amostragem Adaptativa de um objeto. (a) Sem amostragem adaptativa ; (b)com amostragem adaptativa e k = 1 ; (c) com amostragem adaptativa e k = 1.25

A tabela 4.2 mostra a variação de tempo e número de pontos aplicando a super-amostragem em um objeto com 3786 polígonos (mesmo objeto chimp da tabela 4.1),tendo uma variação em k, mantendo uma árvore de altura igual a 4 e resolução iguala 3003. É possível notar que o número de pontos aumenta consideravelmente utilizandoeste procedimento, o que permite capturar com mais detalhe a superfície do objeto, poréminserindo um custo maior para o armazenamento dos pontos.

Parâmetros N◦ Pontos Tempo

sem super-amostragem 218168 4scom super-amostragem (k=1.00) 1320157 6scom super-amostragem (k=1.05) 1799880 7scom super-amostragem (k=1.10) 2592840 8scom super-amostragem (k=1.15) 3931839 10s

Tabela 4.2: Tempos de aquisição de pontos com super-amostragem.

4.2.2 Imagens Renderizadas

Os resultados apresentados no processo de renderização já são imagens geradascom o mecanismo de reconstrução do SARS, aplicando os devidos efeitos de iluminaçãoconsiderando 3 fontes de luz existentes e propriedades materiais do objetos. É sabido queo processo de reconstrução de imagens é fortemente afetado pela amostragem dos pontos.

Tempos de renderização das imagens são demonstrados na tabela 4.3 e permitemidentificar a influência da quantidade de pontos e dos mecanismos de preenchimento defalhas sobre estes tempos. Os testes foram aplicados ao objeto chimp com resoluções deamostragem de 2003, 4003 e 6003, tomados em um computador com processador Athlon

38

1.1GHz com 256MB de RAM e sem a utilização de hardware específico para processa-mento gráfico.

N◦ Pontos Resolução img. Tempo sem preenchimento Tempo com preenchimento

97024 2562 0,35s 0,62s

97024 5122 0,61s 0,93s

388057 2562 0,81s 1,00s

388057 5122 1,08s 1,33s

873094 2562 1,05s 1,34s

873094 5122 1,41s 1,63s

Tabela 4.3: Tempos de renderização de imagem.

Uma análise mais aprofundada pode ser feita determinando quantas falhas existemem uma imagem renderizada. Para isto foi implementado um utilitário que compara oZBuffer de duas imagens (a primeira com uma amostragem menor que a segunda), anali-sando os pixels que passaram a ser preenchidos e aqueles cuja profundidade passou a sermais próxima do observador. Isto significa que estes pixels, na imagem primeira imagemeram falhas e foram preenchidas na segunda.

Para saber quantas falhas reais existem em uma imagem foi estabelecido o conceitode imagem com amostragem ideal. Esta amostragem ideal resulta em uma renderiza-ção sem pixel com falhas. Para determinar a imagem com amostragem ideal, foram ger-adas seqüências de imagens com a resolução de amostragem aumentando gradativamente.Quando a comparação entre a última imagem gerada e diretamente anterior indicar quenenhum pixel foi preenchido com o aumento de resolução, significa que esta imagemanterior já é a ideal.

Desta forma, é possível comparar uma imagem renderizada com a imagem ideal,e descobrir quantas falhas relativas a pixels não preenchidos esta possui. Foram feitostestes para verificar o processo de amostragem de duas formas: variando a resoluçãode amostragem sem a utilização de amostragem adaptativa, e mantendo a resolução deamostragem fixa em 2563 e variando o valor de k na super-amostragem. Cuidados foramtomados para que o objeto estivesse sempre na mesma posição do espaço em relação acâmera, para evitar que a renderização gerasse imagens diferentes. Para estes testes aresolução da imagem final gerada foi de 2563 pixels.

Os testes foram realizados com três objetos diferentes - apresentados na figura 4.5chimp (a), tie-fighter (b) e uma esfera (c)- que foram escolhidos em função da variação dasua geometria, de uma forma menos homogênea à uma forma mais homogênea.

A tabela 4.4 mostra os resultados da amostragem para os objetos escolhidos parateste, tendo o número de pontos obtidos e a variação na quantidade de falhas (de am-bos os tipos). O número de falhas foi medido de acordo com o princípio de compara-ção com a imagem ideal, e a geração desta necessitou uma amostragem inicial, semsuper-amostragem de 18003 para o objeto chimp e de 9003 para os objetos tie-fighter eesfera. Para a construção desta tabela, os valores foram tomados sem a utilização desuper-amostragem, e variando as resoluções entre 1503 e 18003.

39

(a) (b) (c)

Figura 4.5: Objetos escolhidos para os testes. Geometrias variadas.

Chimp Tie-fighter Esfera

Resolução N◦ Falhas N◦ Pontos N◦ Falhas N◦ Pontos N◦ Falhas N◦ Pontos

150 - - 7739 208817 15804 130280

300 17296 218168 4376 836726 2304 413215

450 - - 1457 1882440 387 929788

600 6096 873094 706 3346700 151 1653174

750 - - 311 5232041 52 2582975

900 1585 1964929 0 7533098 0 3719634

1200 567 3493109 - - - -

1500 229 5458778 - - - -

1800 0 7860563 - - - -

Tabela 4.4: Resultados da amostragem dos objetos chimp,tie-fighter e esfera, sem super-amostragem.

Também foram realizados testes nos mesmos objetos com a utilização de super-amostragem - dispostos na tabela 4.5 - porém com uma resolução fixa, que foi de 3003

para o chimp e de 1503 para o tie-fighter e para a esfera. A única variação foi o valor dek, ficando entre 1,00 e 1,25 e testando as imagens geradas contra e mesma imagem idealutilizada nos testes anteriores.

Ao comparar os parâmetros das tabelas 4.4 e 4.5, pode-se notar uma diminuição nonúmero de falhas para a amostragem com valor 3003 do objeto chimp (usado nos testessem super amostragem) que é bastante significativa utilizando a super-amostragem maissimples (k = 1). Neste caso, o número de falhas diminui para 7979, se em comparaçãoao mesmo processo sem amostragem adaptativa, cujo o número de falhas é igual a 17296.Esta diferença acentua-se à medida que o valor de k aumenta.

40

A realização dos testes com os objetos tie-fighter e a esfera (tabela 4.4) tambémseguiram o mesmo princípio que os testes com o objeto chimp, porém com as devidasadaptações. A imagem ideal, tanto para o tie-fighter quanto para a esfera foram obtidascom uma resolução de 9003. Assim, os testes sem super-amostragem tiveram resoluçõesvariadas entre 1503 e 9003.

A diferença entre a geometria dos objetos testados já começa a ficar saliente quantoao seu comportamento na amostragem. À medida que a superfície do objeto torna-semais homogênea, uma mesma resolução de amostragem captura melhor as informaçõesdo objeto, gerando um número menor de falhas nas imagens renderizadas. Isto pode serobservado comparando o número de falhas em imagens geradas com resolução 1503 notie-fighter e na esfera, que foram de 7739 e 1584. No caso da esfera, pode-se ainda notara rápida queda do número de falhas à medida que a resolução de amostragem aumenta.

Os resultados para amostragem do tie-fighter e da esfera com super-amostragemsão apresentados na tabela 4.5. Para ambos os objetos a resolução inicial é de 1503 tendok variando entre 1,00 e 1,25.

Chimp Tie-fighter Esfera

Valor de k N◦ Falhas N◦ Pontos N◦ Falhas N◦ Pontos N◦ Falhas N◦ Pontos

1,00 7979 1320157 6058 636346 14796 407792

1,05 5893 1799880 5319 872973 9990 537835

1,10 4331 2592840 4761 983609 6729 757373

1,15 3370 3931839 4406 1160916 4328 1132729

1,20 2575 6193425 3679 1973237 3053 1734944

1,25 1873 8185545 3295 2868070 2372 2657451

Tabela 4.5: Resultados da amostragem dos objetos chimp,tie-fighter e esfera, com super-amostragem.

O gráfico ilustrado na figura 4.6 apresenta uma comparação entre os testes semamostragem adaptativa, permitindo identificar uma convergência em relação a diminuiçãodo número de falhas, à medida que a amostragem aumenta.

É possível perceber que a amostragem adaptativa captura melhor as informaçõesda superfície de um objeto, porém para isto, o número de pontos amostrados aumentaconsideravelmente, mesmo com pequenas variações no valor de k.

O gráfico da figura 4.7 apresenta o efeito do parâmetro k para a redução de falhascom amostragem adaptativa. Objetos com uma geometria mais simétrica não tomamvantagem da amostragem adaptativa e o número de falhas preenchidas não converge tãorapidamente à medida que o valor de k aumenta.

A simetria da geometria de um objeto é fator que influência a amostragem de um ob-jeto, podendo ser acentuada na técnica de amostragem adaptativa proposta neste trabalho.Um exemplo disto pode ser construído tomando os objetos alvos dos testes. Para isto,consideremos imagens geradas com os menores valores de amostragem (sem amostragemadaptativa) dos três objetos: 3003 para o chimp e 1503 para o tie-fighter e para a esfera.

Deseja-se diminuir em aproximadamente 50% o número de falhas encontradas nasimagens de cada objeto, usando super-amostragem e variando o valor de k. As novas

41

Figura 4.6: Variação do número de falhas em diferentes objetos amostrados semamostragem adaptativa.

Figura 4.7: Variação do número de falhas em diferentes objetos amostrados com super-amostragem.

42

amostragens resultam em um número de pontos que aumenta um certo número de vezesem relação à quantidade de pontos sem super-amostragem. Isto pode ser observado natabela 4.6.

Objeto N◦Falhas ini. N◦ Falhas desej. k N◦ pts sem sa N◦ pts com sa Razão

tie-fighter 7739 3800 1,18 208817 1811717 8,67

chimp 17296 8000 1,00 218168 1320157 6,05

esfera 15804 7800 1,09 130280 704785 5,41

Tabela 4.6: Variação do número de falhas e número de pontos em relação a simetria dosobjetos.

Os resultados da tabela 4.6 permitem observar o número de vezes em que aumenta onúmero de pontos necessários para realizar uma redução controlada do número de falhasem uma imagem. Pode-se notar que a medida que a simetria do objeto diminui, menor éo aumento do número de pontos necessários para preencher em aproximadamente 50% onúmero de falhas nas imagens.

A noção de simetria é muito intuitiva para os objetos do exemplo. Para isto estesobjetos foram analisados em relação a sua geometria e a variação desta em relação a umponto centróide destes objetos. Foram computadas as distâncias para todos os vérticesdos polígonos que formam cada objeto, em relação ao seu centróide, que neste caso, é aorigem dos eixos de coordenadas. Estas distâncias fornecem valores estatísticos de médiae desvio padrão que podem ser observados na tabela 4.7.

Objeto Média Desvio padrão % da média

tie-fighter 1,74 1,17 67,2chimp 5,2 1,37 26,3esfera 1,98 0,01 0,5

Tabela 4.7: Análise da simetria da superfície de objetos.

Com estes resultados podemos observar que, quanto maior o desvio padrão ( emrelação à média), mais variada as distâncias entre os vértices e a origem, e portanto maisassimétrico este objeto é. De acordo com a tabela 4.7, confirma-se o comportamentoapresentado na tabela 4.6, onde o número de pontos necessários para reduzir um certonúmero de falhas é menor para objetos mais simétricos (esfera) aumentando quanto maisassimétrico forem os objetos (tie-fighter).

4.2.3 Preenchendo Falhas na Imagem

As falhas existentes em uma imagem podem ser preenchidas totalmente ou parcial-mente, de acordo com o procedimento descrito na seção 2.4.2. Ajustando os fatores deprecisão para recuperar falhas na imagem dos dois tipos identificados, é possível reduziro os defeitos visuais em uma imagem ao ponto de não ser perceptível aos olhos humanos.

A tabela 4.8 mostra exemplos em uma seqüência de imagens onde os fatores deprecisão para falhas de superfície e fundo de imagem variam. A amostragem foi feita

43

com resolução de 5003, a resolução final de imagem é de 3002, e a variação dos fatores foiescolhida, devido ao comportamento não linear que a técnica de preenchimento de falhaspossui.

As imagens geradas ilustram o detalhe destacado na figura 4.8, que apresenta aimagem completa do objeto testado. Pode-se notar que muitos detalhes da imagem pud-eram ser recuperados satisfatoriamente, e para conseguir uma imagem semelhante, serianecessário amostrar o mesmo objeto com uma resolução de no mínimo 700.

Figura 4.8: Imagem utilizada para comparação dos fatores de precisão. O destaque refere-se a parte apresentada na tabela 4.8

Artefatos podem ocorrer quando o fator que define quando um pixel que tem a corde um polígono que não deveria estar visível é muito baixo. Quanto mais próximos dezero, este fator pode fazer com que o procedimento de preenchimento de falhas identi-fique qualquer pixel como tendo a cor incorreta, preenchendo-o com a cor dos vizinhos.Isto causa uma distorção muito mais acentuada que o caso anterior, fazendo com que asuperfície do objeto tenha um aspecto visual muito diferente da imagem original.

44

fundo/sup. 0,0 0,4 0,8 1,0

0,0

0,1

0,5

1,0

Tabela 4.8: Comparação de imagens renderizadas com vários fatores de precisão.

5 Conclusões e Trabalhos Futuros

Este capítulo finaliza o trabalho apresentando conclusões gerais sobre a ComputaçãoGráfica Baseada em Pontos e principalmente sobre a Renderização de imagens e o pro-cesso de amostragem de objetos. Também é apresentado novas propostas e extensões àstécnicas discutidas e implementadas neste trabalho.

5.1 Conclusões

As técnicas apresentadas nesta monografia demonstram a evolução da ComputaçãoGráfica Baseada em Pontos, e que este modelo alcançou um nível de maturidade quepermitiu chegar a bons resultados. Estes são demonstrados no método de RenderizaçãoBaseada em Pontos descrito ao longo deste texto. Este método caracteriza-se em repre-sentar modelos de objetos utilizando pontos como primitiva, ao invés de triângulos ousuperfícies paramétricas como é feito tradicionalmente.

Duas etapas se destacam neste método: a amostragem de pontos em um objeto ea reconstrução (renderização) da imagem. Vários aspectos peculiares a cada uma dessasetapas são discutidos e dois problemas relevantes são abordados de forma mais diretacomo contribuição deste trabalho.

Tendo como objetivo gerar imagens de melhor qualidade, uma melhor represen-tação da superfície do objeto leva a reconstrução de uma imagem com menos falhas. Amelhoria desta representação é denominada Amostragem Adaptativa, visando capturarmais pontos em áreas da geometria do objeto onde é for mais necessário, em relação à suainclinação em relação a um ponto de observação.

Também com a intenção de eliminar falhas em uma imagem renderizada, um pro-cedimento de preenchimento de falhas foi desenvolvido, permitindo que a precisão aodeterminar a cor que preencherá os pixels com falhas seja ajustada conforme desejado.Esta técnica de recuperação da imagem permite que a renderização de um objeto gerebons resultados sem a necessidade de reamostrá-lo.

Até o presente momento, a Renderização Baseada em Pontos não intenciona substi-tuir os mecanismos de renderização tradicionais, e sim ser uma alternativa em casos maisespecíficos. Diversos efeitos podem ser mais facilmente formulados e criados utilizandopontos como representação de superfícies, e algumas entidades como nuvens e poeira jápossuem esta característica por natureza.

Existem muitos problemas a serem resolvidos, e também a necessidade de adequaras representações de forma que possam ser utilizadas mais facilmente. Armazenar umobjeto representado por pontos pode exigir até dezenas de vezes mais memória do querepresentar este mesmo objeto com polígonos, o que tornaria inviável a manipulação devários objetos simultaneamente. O tempo gasto na renderização ainda não permite que aRBP seja utilizada em aplicações em tempo real.

Porém, o desenvolvimento de técnicas que permitam a utilização de hardware es-pecífico para processamento gráfico na etapa de renderização pode diminuir bastante otempo de processamento. Da mesma forma, uma grande vantagem do método é permitirque a imagem seja trabalhada com um alto nível de detalhe, permitindo a renderização

46

com efeitos aplicados sobre fragmentos. Este tipo de efeito pode pode significar maisrealismo a uma cena ou simplesmente incrementar seu aspecto visual. Algumas placasgráficas atuais permitem gerar estes efeitos diretamente nos pixels da imagem. Com umarepresentação através de pontos, as mesmas operações podem ser realizadas sem a neces-sidade de tal equipamento sem um grande aumento do custo computacional.

A renderização de uma cena através de rasterização de polígonos ainda é um dosmeios mais viáveis para aplicações em tempo real. Contudo, a qualidade visual alcançadaainda é inferior a de imagens tão tradicionalmente geradas com a utilização de traçadode raios, pagando-se o preço de um considerável aumento no tempo de processamento ARBP nos permite gerar imagens que visualmente se equivaleriam a imagens geradas comtraçado de raios, porém com um tempo de processamento significantemente inferior.

Todos estes aspectos nos mostram o grande potencial da técnica tanto como alter-nativa quanto para complemento na geração de imagens de computação gráfica. Coma evolução do modelo e dos procedimentos a RBP pode tornar-se mais uma ferramentaimportante na área.

5.2 Trabalhos Futuros

A Computação Gráfica Baseada em Pontos possui um grande potencial para explo-ração de suas funcionalidades, melhoramento das técnicas já existentes e proposições denovas aplicações. Este trabalho colabora para a expansão deste novo modelo de repre-sentação de objetos, propondo novas técnicas e funcionalidades, e também criando umsistema protótipo que consolide os trabalhos.

Porém, existem diversos pontos que podem ser melhorados ou explorados de formaa estender a capacidade das proposições apresentadas, tornando-as mais corretas e com-pletas. Algumas das extensões são dispostas abaixo e servem como orientação para acontinuação dos trabalhos com Computação Gráfica Baseada em Pontos.

• estender a capacidade da técnica de amostragem de forma que possa trabalhar out-ros tipos de superfícies com paramétricas e procedurais;

• utilizar pontos obtidos com scanners 3D como entrada para a renderização de ima-gens;

• implementar a super-amostragem de forma que esta seja mais eficiente e maisotimizada, sendo realizada em apenas um dos planos de amostragem, ao invés de 3planos;

• aprimorar a idéia de uma técnica de auto-amostragem aplicada em superfícies rep-resentada por polígonos onde o número de pontos amostrado em cada polígonoseria uma função de sua área;

• implementar mecanismos de aquisição e filtragem de texturas aplicadas diretamenteno momento da amostragem;

• utilizar uma estrutura de dados, com subdivisão espacial, mais apropriada para ar-mazenar os conjuntos de pontos amostrados de forma a otimizar a manipulaçãodestes pontos e acelerar o processo de renderização;

47

• permitir a combinação de um ou mais objetos em uma única cena;

• renderizar imagens aplicando efeitos de iluminação como sombras e bump-mapping[2];

• estudar e desenvolver técnicas que permitam implementar outros efeitos de ilumi-nação como reflexão, transparência e refração;

• criar um mecanismo, parte do sistema, que permita realizar renderizações de formainterativa;

• inserir técnicas de Computação Gráfica Baseada em Pontos na criação de efeitosutilizados em jogos eletrônicos ;

• difundir os conceitos e as aplicações da CGBP entre a comunidade de ComputaçãoGráfica.

A implementação das técnicas descritas nos ítens acima permitirão a continuidadedeste trabalho, gerando material de interesse científico e acadêmico, permitindo tambémque o uso da CGBP torne-se suficientemente prático para o uso em aplicações diversas.

48

Bibliografia

[1] Marc Alexa, Johannes Behr, Daniel Cohen-Or, Shachar Fleishman, David Levin,and Claudio T. Silva. Computing and rendering point set surfaces. volume 9 ofTransactions on Visualization and Computer Graphics, pages 3–15, January 2003.

[2] James F. Blinn. Simulation of wrinkled surfaces. In Computer Graphics (Proceed-ings of SIGGRAPH 78), volume 12, pages 286–292, August 1978.

[3] James F. Blinn. A generalization of algebraic surface drawing. ACM Transactionson Graphics, 1(3):235–256, July 1982.

[4] E. Catmull. A hidden-surface algorithm with anti-aliasing. In Computer Graph-ics (Proceedings of SIGGRAPH 78), volume 12, pages 6–11. ACM Press / ACMSIGGRAPH / Addison Wesley Longman, August 1978.

[5] DP Cohen, Steven Gortler, and Philipp Slusallek. Radiosity and realistic imagesynthesis. Academic Press Professional, Boston, 1993.

[6] Charles Csuri, Ron Hackathorn, Richard Parent, Wayne E. Carlson, and MarcHoward. Towards an interactive high visual complexity animation system. InComputer Graphics (Proceedings of SIGGRAPH 79), volume 13, pages 289–299.ACM Press / ACM SIGGRAPH / Addison Wesley Longman, August 1979.

[7] James D. Foley. Computer Graphics: Principles and Pratice. Addison-Wesley,Reading, MA, 2000.

[8] Andrew Glassner. An Introduction to Ray Tracing. Academic Press, San Diego,CA 92101, 1989.

[9] M. Gross. Graphics in medicine: From visualization to surgery. ACM ComputerGraphics, 32, 1998.

[10] J. P. Grossman and William J. Dally. Point sample rendering. In EurographicsRendering Workshop 1998, pages 181–192, June 1998.

[11] A. Hubeli and M. Gross. Fairing of non-manifolds for visualization. IEEE Visual-ization 00, 2000.

[12] Aravind Kalaiah and Amitabh Varshney. Differential point rendering. In Render-ing Techniques 2001: 12th Eurographics Workshop on Rendering, pages 139–150,June 2001.

49

[13] Marc Levoy, Kari Pulli, Brian Curless, Szymon Rusinkiewicz, David Koller, LucasPereira, Matt Ginzton, Sean Anderson, James Davis, Jeremy Ginsberg, JonathanShade, and Duane Fulk. The digital michelangelo project: 3d scanning of largestatues. pages 131–144, July 2000.

[14] Marc Levoy and Turner Whitted. The use of points as display primitives. TechnicalReport 85-022, Computer Science Department, University of North Carolina atChapel Hill, June 1985.

[15] Tomas Möller and Eric Haines. Real-Time Rendering. A. K. Peters, Natick, MA,2◦ edition, 2003.

[16] Mark Pauly, Richard Keiser, Leif P. Kobbelt, and Markus Gross. Shape modelingwith point-sampled geometry. volume 22, pages 641–650, July 2003.

[17] R. Peikert and M. Roth. The paralel vectors operator - a vector field visualizationprimitive. IEEE Visualization 99, 1999.

[18] Hanspeter Pfister, Matthias Zwicker, Jeroen van Baar, and Markus Gross. Surfels:Surface elements as rendering primitives. In Proceedings of ACM SIGGRAPH2000, Computer Graphics Proceedings, Annual Conference Series, pages 335–342, July 2000.

[19] B. T. Phong. Illumination for computer generated pictures. Communications ofthe ACM, 18(6):311–317, June 1975.

[20] W. T. Reeves. Particle systems - a technique for modeling a class of fuzzy objects.ACM Transactions on Graphics, 2(2):91–108, April 1983.

[21] Hanam Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1990.

[22] Jonathan Shade, Steven J. Gortler, Li wei He, and Richard Szeliski. Layered depthimages. In Proceedings of SIGGRAPH 98, Computer Graphics Proceedings, An-nual Conference Series, pages 231–242, July 1998.

[23] Wave Front Technologies. The advanced visualizer - users guide: Appendix b,1990.

[24] Turner Whitted. An improved illumination model for shaded display. Communi-cations of the ACM, 23(6):343–349, June 1980.

[25] Matthias Zwicker, Hanspeter Pfister, Jeroen Baar, and Markus Gross. Surfacesplatting. In Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceed-ings, Annual Conference Series, pages 371–378. ACM Press / ACM SIGGRAPH/ Addison Wesley Longman, August 2001.