Heloisa Reis Leal profs - visgraf.impa.br · Computação Gráfica Interativa . Abstract Leal, Heloisa Reis; ... 3.5. Aquisição do modelo 23 ... d (d) Resultado de A ∩ B: A d

Heloisa Reis Leal

Operaccedilotildees Booleanas na Modelagem por Pontos

Dissertaccedilatildeo de Mestrado

Dissertaccedilatildeo apresentada como requisito parcial para obtenccedilatildeo do tiacutetulo de Mestre pelo Programa de Poacutes-Graduaccedilatildeo em Informaacutetica da PUC-Rio

Orientadores Prof Waldemar Celes Filho Prof Luiz Velho

Rio de Janeiro agosto de 2004

Heloisa Reis Leal


Dissertaccedilatildeo apresentada como requisito parcial para obtenccedilatildeo do tiacutetulo de Mestre pelo Programa de Poacutes-Graduaccedilatildeo em Informaacutetica da PUC-Rio Aprovada pela Comissatildeo Examinadora abaixo assinada

Prof Waldemar Celes Filho Orientador

Departamento de Informaacutetica-PUC-Rio

Prof Luiz Velho Co-orientador

Instituto de Matemaacutetica Pura e Aplicada (IMPA)

Prof Bruno Feijoacute Departamento de Informaacutetica-PUC-Rio

Prof Marcelo Dreux Departamento de Mecacircnica-PUC-Rio

Prof Paulo Cezar Pinto Carvalho Instituto de Matemaacutetica Pura e Aplicada (IMPA)

Prof Joseacute Eugecircnio Leal Coordenador Setorial do Centro Teacutecnico Cientiacutefico - PUC-Rio

Rio de Janeiro 3 de agosto de 2004

Todos os direitos reservados Eacute proibida a reproduccedilatildeo total ou parcial do trabalho sem autorizaccedilatildeo da universidade da autora e do orientador

Heloisa Reis Leal Graduou-se em Ciecircncia da Computaccedilatildeo pela Universidade Federal de Minas Gerais (UFMG) em abril de 1992 Trabalhou como Analista de Sistemas na empresa Telecomunicaccedilotildees de Minas Gerais SA (TELEMIG) entre 1993 e 1997 onde atuou no desenvolvimento de sistemas de controle da rede telefocircnica de Minas Gerais Trabalhou como Analista de Sistemas no Tribunal de Justiccedila do Estado de Minas Gerais (TJMG) entre 1998 e 2001 onde atuou no desenvolvimento de sistemas controle de processos e controle de equipamentos Desde 2002 trabalha no Serviccedilo Federal de Processamento de Dados (SERPRO) desenvolvendo sistema de controle da Malha Fiscal do Imposto de Renda - Pessoa Fiacutesica

Ficha Catalograacutefica

Leal Heloisa Reis

Operaccedilotildees booleanas na modelagem por pontos

Heloisa Reis Leal orientadores Waldemar Celes Filho

Luiz Velho ndash Rio de Janeiro PUC Departamento de

Informaacutetica 2004

75 f il 30 cm

Dissertaccedilatildeo (mestrado) ndash Pontifiacutecia

Universidade Catoacutelica do Rio de Janeiro Departamento de

Informaacutetica

Inclui referecircncias bibliograacuteficas

1 Informaacutetica ndash Teses 2 Computaccedilatildeo graacutefica

interativa 3 Modelagem 3D 4 Modelagem por pontos 5

Operaccedilotildees booleanas I Celes Filho Waldemar II Velho

Luiz III Pontifiacutecia Universidade Catoacutelica do Rio de Janeiro

Departamento de Informaacutetica III Tiacutetulo

CDD 004

Agrave minha matildee Tetecirc Daacutelton e Lucas

Agradecimentos Aos meus orientadores Waldemar Celes e Luiz Velho pelo apoio dedicaccedilatildeo e paciecircncia que tornaram este trabalho possiacutevel Agrave PUC-Rio pelo apoio financeiro Aos membros da banca examinadora pelas correccedilotildees e sugestotildees Agrave Cristina Griner chefe de projeto do SERPRO pelo apoio compreensatildeo e ajuda Aos meus professores de mestrado pelos conhecimentos transmitidos Agrave Mauren Paola Ruthner pela amizade e colaboraccedilatildeo durante todo o mestrado Aos colegas do Departamento de Informaacutetica da PUC-Rio pelos momentos compartilhados Agrave minha matildee pela revisatildeo do texto desta dissertaccedilatildeo e pelo total apoio sem o qual este trabalho natildeo seria possiacutevel Agrave Daacutelton e Tetecirc meus queridos irmatildeos pelo apoio incentivo e colaboraccedilatildeo

Resumo

Leal Heloisa ReisCeles Waldemar (Orientador) Operaccedilotildees Booleanas na Modelagem por Pontos Rio de Janeiro 2004 75p Dissertaccedilatildeo de Mestrado - Departamento de Informaacutetica Pontifiacutecia Universidade Catoacutelica do Rio de Janeiro

Operaccedilotildees booleanas em modelagem 3D satildeo usadas para criar novos

modelos ou para modificaacute-los Na maioria dos tipos de representaccedilatildeo de objetos

3D estas operaccedilotildees satildeo bastante complexas Nos uacuteltimos anos tem sido muito

explorado um novo tipo de modelagem a modelagem por pontos que apresenta

muitas vantagens em relaccedilatildeo agraves outras representaccedilotildees como maior simplicidade

e eficiecircncia Dois trabalhos exploram as operaccedilotildees booleanas na modelagem

por pontos o trabalho de Adams e Dutreacute e o trabalho de Pauly et al Dada a

grande importacircncia deste novo tipo de modelagem e do uso de operaccedilotildees

booleanas esta dissertaccedilatildeo apresenta uma introduccedilatildeo agrave modelagem por pontos

implementa o algoritmo proposto em Adams e Dutreacute com algumas melhorias e o

compara com o meacutetodo de Pauly et al

Palavras-chave

Modelagem 3D Modelagem por pontos Operaccedilotildees Booleanas

Computaccedilatildeo Graacutefica Interativa

Abstract

Leal Heloisa Reis Celes Waldemar(Advisor) Boolean Operations on Point-based models Rio de Janeiro 2004 75p MSc Dissertation - Departamento de Informaacutetica Pontifiacutecia Universidade Catoacutelica do Rio de Janeiro

Boolean operations are used to create or modify models These operations

in the majority of 3D object representations are very complex In the last years a

significant trend in computer graphics has been the shift towards point sampled

3D models due to their advantages over other representations such as simplicity

and efficiency Two recent works present algorithms to perform interactive

boolean operations on point-based models the work by Adams and Dutreacute and

the work by Pauly et Al Due to great importance of this novel representation

and of the use of boolean operations the present work makes an introduction to

point-based representation implements the algorithm proposed by Adams and

Dutreacute with some improvements and compares this implementation with the work

by Pauly et al

Palavras-chave

3D Modeling Point-based Modeling Boolean Operation Interactive

Computer Graphics

Sumaacuterio

1 Introduccedilatildeo 15

2 Trabalhos relacionados 18

3 Modelagem por Pontos 20 31 Ideacuteia da Representaccedilatildeo 20 32 Tipos de distribuiccedilatildeo dos surfels 22 33 Estrutura de multi-resoluccedilatildeo 22 34 Dados que um surfel pode conter 23 35 Aquisiccedilatildeo do modelo 23 351 Aquisiccedilatildeo da geometria 23 352 Aquisiccedilatildeo da textura 24 353 Correccedilatildeo das falhas da aquisiccedilatildeo 25 36 Reconstruccedilatildeo da superfiacutecie (contiacutenua) a partir do modelo (discreto) 25 37 Visualizaccedilatildeo do modelo 26 38 Ediccedilatildeo do modelo 28

4 Operaccedilotildees Booleanas com Pontos 29 41 Meacutetodos para realizar operaccedilotildees booleanas em objetos modelados por

pontos 29 42 Meacutetodo de Adams e Dutreacute 33 421 Modelo por Pontos em Adams e Dutreacute 33 422 Algoritmo de Operaccedilotildees Booleanas 34 43 Meacutetodo de Pauly 39 431 Modelo em Pauly 40 432 Algoritmo de Operaccedilotildees Booleanas 40 44 Validade da Regra 2 43

5 Melhorias Propostas 47 51 Descriccedilatildeo do algoritmo 47 511 Criaccedilatildeo e classificaccedilatildeo de uma octree para cada modelo 48

512 Teste DentroFora 52 513 Criaccedilatildeo do modelo resultado 54 52 Implementaccedilatildeo 55 521 Estruturas de Dados 57

6 Resultados 61 61 Testes 61 62 Comparaccedilatildeo entre os dois meacutetodos que realizam operaccedilotildees booleanas 68

7 Conclusatildeo 71 71 Trabalhos Futuros 72

8 Referecircncias Bibliograacuteficas 73

11

Lista de figuras

Figura 1 Um modelo por pontos e sua visualizaccedilatildeo 21 Figura 2 A superfiacutecie modelada por surfels O surfel em destaque tem raio de

alcance rt e normal n 22 Figura 3 Modelo por pontos e sua renderizaccedilatildeo usando Surface Splatting 26 Figura 4 Trecircs modelos novos foram criados a partir dos quatro iniciais (esfera

cilindro dois cubos) O primeiro eacute a esfera menos um cubo em seguida

retirou-se outro cubo e por uacuteltimo retirou-se o cilindro 29 Figura 5 A partir de dois modelos por pontos uma heacutelice e uma cabeccedila as trecircs

operaccedilotildees booleanas satildeo mostradas da esquerda para a direita uniatildeo

diferenccedila e interseccedilatildeo 30 Figura 6 (a) Dois modelos A e B (b) Posicionados de forma que A tem uma parte

dentro de B eacute mostrado o resultado A U B Af + Bf (c) Resultado de A ndash B Af

+ Bd (d) Resultado de A cap B Ad + Bd 31 Figura 7 Para classificar o ponto x encontra-se o surfel p (com normal np) mais

proacuteximo a x Se o produto interno entre np e (x ndash p) for maior que zero entatildeo

x eacute classificado como fora senatildeo seraacute classificado como dentro 32 Figura 8 Interseccedilatildeo de duas esferas agrave esquerda sem nenhum tratamento de

interseccedilatildeo agrave direita apoacutes o tratamento de interseccedilatildeo 33 Figura 9 Um objeto representado por pontos com suas normais e sua quadtree

correspondente classificada os noacutes cinza claro estatildeo dentro do modelo noacutes

cinza mais escuro estatildeo fora do modelo e noacutes com cinza intermediaacuterio satildeo

noacutes cheios noacutes que conteacutem pontos 35 Figura 10 Divisatildeo de noacute de contorno a parte agrave esquerda estaacute fora do modelo a

parte agrave direita estaacute dentro do modelo e a faixa intermediaacuteria conteacutem os

surfels 36 Figura 11 Interseccedilatildeo do surfel s e do plano que passa pelo surfel t o surfel mais

proacuteximo a s O surfel s eacute substituiacutedo por trecircs surfels menores 38 Figura 12 Agrave direita eacute mostrado o resultado do tratamento de interseccedilatildeo para o

caso de Arestas Vivas do objeto agrave esquerda 39 Figura 13 Os novos surfels satildeo colocados exatamente na curva de interseccedilatildeo e

convergem para o ponto de interseccedilatildeo 42 Figura 14 (a) Suponhamos a reta que eacute a interseccedilatildeo do plano tangente a S1 em

q1 e o plano tangente a S2 em q2 O ponto r eacute o ponto desta reta que estaacute

12

mais proacuteximo a q1 e q2 (b) r eacute projetado sobre S1 e S2 obtendo-se q1acute e q2acute

dois novos pontos de partida para nova iteraccedilatildeo (c) A nova iteraccedilatildeo gera r

que eacute uma aproximaccedilatildeo melhor de q 43 Figura 15 Para verificar se o ponto x estaacute fora de um contorno C encontra-se o

ponto y de C Se o produto interno entre a normal em y e o vetor que liga y a

x for maior que zero entatildeo x estaacute fora de C senatildeo estaacute dentro de C 44 Figura 16 As curvas vermelhas satildeo o Eixo Medial da curva em preto 45 Figura 17 Em 3D geralmente o Eixo Medial eacute uma superfiacutecie 2D (em vermelho)

Aqui o quadrado eacute o Eixo Medial da superfiacutecie transparente que o contorna

45 Figura 18 A figura mostra o diagrama de Voronoi de uma amostragem de pontos

S Da mesma forma que a amostragem aproxima a curva os veacutertices de

Voronoi aproximam o Eixo Medial 46 Figura 19 Quadtree classificada Os noacutes mais escuros estatildeo fora do modelo os

mais claros dentro e os em tom intermediaacuterio satildeo noacutes de contorno 48 Figura 20 O noacute cheio eacute dividido em trecircs partes agrave esquerda a regiatildeo estaacute dentro

do modelo agrave direita estaacute fora e entre as duas linhas que dividem o noacute estaacute a

regiatildeo que conteacutem os surfels 49 Figura 21 O noacute a eacute classificado pelo noacute c o noacute d tambeacutem eacute classificado pelo noacute c

a classificaccedilatildeo do noacute a eacute propagada para o noacute b 50 Figura 22 Os cantos a e b do noacute cheio possuem a mesma classificaccedilatildeo fora do

modelo Esta classificaccedilatildeo foi dada ao noacute vazio adjacente 50 Figura 23 Quadtree classificada 51 Figura 24 A normal n eacute a normal meacutedia e os surfels s1 e s2 juntamente com a

normal n definem as retas que dividem o noacute 52 Figura 25 Duas circunferecircncias e suas quadtrees correspondentes 53 Figura 26 a modelos natildeo se intersectam b modelo intersecta noacutes fora c

modelo intersecta apenas noacutes dentro d modelo intersecta noacutes dentro e noacutes

fora 54 Figura 27 Software PointShop 3D com dois modelos carregados na sua cena 56 Figura 28 Menu do PointShop com o plugin e as opccedilotildees para operaccedilotildees

booleanas 57 Figura 29 Modelo do PointShop Igea 62 Figura 30 Resultado da uniatildeo de duas Igeas 63 Figura 31 Resultado da interseccedilatildeo de duas Igeas 63 Figura 32 Resultado da diferenccedila entre duas Igeas 64

13

Figura 33 Modelo do PointShop MaxPlanck 65 Figura 34 Modelo do PointShop Male 66 Figura 35 Resultado da Uniatildeo do modelo Male com MaxPlanck 66 Figura 36 Resultado da interseccedilatildeo do modelo Male com o MaxPlanck 67 Figura 37 Resultado da diferenccedila do modelo Male do modelo MaxPlanck 67

14

Lista de tabelas

Tabela 1 Classificaccedilatildeo para operaccedilotildees booleanas 42

Tabela 2- Nuacutemero de surfels dos modelos resultantes 64 Tabela 3- Meacutedia dos tempos de processamento para as operaccedilotildees com duas

Igeas 65

Tabela 4-Tempo de processamento das operaccedilotildees com os modelos MaxPlanck

e Male 68 Tabela 5- Nuacutemero de surfels dos modelos resultados das operaccedilotildees com os

modelos MaxPlanck e Male 68

15

1 Introduccedilatildeo

O mundo digital estaacute conquistando cada vez mais espaccedilo nos meios de

comunicaccedilatildeo Sons imagens viacutedeos digitais satildeo miacutedias muito usadas em

diversas aacutereas como entretenimento medicina desenho industrial engenharia

arquitetura educaccedilatildeo arte ciecircncia entre outras Podemos citar alguns

exemplos dentro destas aacutereas como jogos efeitos especiais filmes digitais

visualizaccedilatildeo cientiacutefica viacutedeo-conferecircncia comeacutercio na internet Nos uacuteltimos anos

verificamos que o modelo 3D vem se tornando um novo meio de comunicaccedilatildeo

digital Com o desenvolvimento da tecnologia de aquisiccedilatildeo e do processamento

de modelos 3D ele vem sendo cada vez mais utilizado Jogos 3D animaccedilotildees

aplicaccedilotildees em realidade virtual visualizaccedilatildeo cientiacutefica aplicaccedilotildees para aacuterea

meacutedica e odontoloacutegica criaccedilatildeo de reacuteplicas para estudo e preservaccedilatildeo do

patrimocircnio histoacuterico sistemas CADCAM cataacutelogos de modelos 3D na Web para

comercializaccedilatildeo criaccedilatildeo de protoacutetipos para arquitetura engenharia satildeo alguns

exemplos de aplicaccedilotildees que usam modelos 3D

A aacuterea que estuda a representaccedilatildeo de um modelo 3D no computador eacute

chamada de modelagem em computaccedilatildeo graacutefica Existem diversos tipos de

modelagem para as diversas aplicaccedilotildees que usam um modelo 3D como por

exemplo representaccedilotildees poligonais como malhas triangulares que satildeo

geralmente usadas na aacuterea de entretenimento Este trabalho explora um novo

tipo de modelagem a modelagem por pontos

A modelagem por pontos comeccedilou a ser largamente explorada nesta

deacutecada e trata-se de uma aacuterea muito promissora em computaccedilatildeo graacutefica dadas

agraves vaacuterias e grandes vantagens em relaccedilatildeo aos outros tipos de representaccedilatildeo

como esquema de representaccedilatildeo CSG (Constructive Solid Geometry) [1] ou

malhas poligonais Dentre as principais vantagens podemos citar grande

simplicidade e flexibilidade boa performance robustez Mas a principal

vantagem desta modelagem que foi o fator que impulsionou o seu grande

desenvolvimento nesta deacutecada eacute que esta modelagem por pontos eacute a melhor

opccedilatildeo para tratar os dados de saiacuteda de equipamentos de aquisiccedilatildeo de modelos

3D O uso destes equipamentos tem aumentado muito nesta deacutecada A

16

tecnologia destes equipamentos tem progredido muito e eles tecircm se tornado

mais baratos A tendecircncia eacute que o uso destes equipamentos se torne o mais

utilizado meio de obtenccedilatildeo de modelos 3D Isto porque construir modelos 3D

bastante detalhados por meio de um software de modelagem eacute muito trabalhoso

O processo de aquisiccedilatildeo de modelos por meio destes equipamentos automatiza

este processo de construccedilatildeo

No trabalho com modelos 3D frequumlentemente satildeo usadas as operaccedilotildees

booleanas que satildeo operaccedilotildees de uniatildeo interseccedilatildeo ou diferenccedila No esquema

de representaccedilatildeo CSG estas operaccedilotildees fazem parte da representaccedilatildeo do

objeto Estas operaccedilotildees tambeacutem podem ser usadas para criar novos modelos ou

para alteraacute-los Na maioria dos tipos de representaccedilatildeo de objetos 3D estas

operaccedilotildees satildeo bastante complexas

A simplicidade da representaccedilatildeo por pontos permite que as operaccedilotildees

booleanas sejam realizadas com facilidade se compararmos com a realizaccedilatildeo

destas operaccedilotildees em outros tipos de representaccedilatildeo como malhas poligonais

Motivada pelas vantagens desta modelagem e pela utilidade destas operaccedilotildees

esta dissertaccedilatildeo apresenta uma introduccedilatildeo geral de modelagem por pontos e

trabalha mais especificamente com operaccedilotildees booleanas em objetos

modelados por pontos Dois trabalhos que exploram as operaccedilotildees booleanas na

modelagem por pontos seratildeo abordados o trabalho de Adams e Dutreacute [2] e o

trabalho de Pauly et al [3] O presente trabalho implementa o meacutetodo de Adams

e Dutreacute com algumas melhorias e faz uma comparaccedilatildeo entre o meacutetodo de Pauly

[3] e o meacutetodo de Adams e Dutreacute [2] com nossas melhorias

Como contribuiccedilotildees dadas por este trabalho apresentamos

- um estudo sobre modelagem por pontos

- um estudo sobre operaccedilotildees booleanas com pontos

- proposta de melhorias ao algoritmo proposto por Adams e Dutreacute [2]

- comparaccedilatildeo dos dois meacutetodos propostos para realizar estas operaccedilotildees

meacutetodo de Pauly et al [3] e de Adams e Dutreacute [2]

Este trabalho vem apresentado nesta dissertaccedilatildeo organizada em sete

capiacutetulos conforme descrito resumidamente a seguir

O capiacutetulo 2 cita alguns trabalhos sobre modelagem por pontos que estatildeo

relacionados a este trabalho

O capiacutetulo 3 apresenta uma visatildeo geral do modelo por pontos e explica

melhor alguns trabalhos citados no capiacutetulo 2

17

O capiacutetulo 4 apresenta operaccedilotildees booleanas com pontos e os dois

meacutetodos para realizaacute-las na modelagem por pontos meacutetodo de Pauly et al [3] e

de Adams e Dutreacute [2]

O capiacutetulo 5 apresenta algumas melhorias ao algoritmo de Adams e Dutreacute

[2] e a nossa implementaccedilatildeo deste algoritmo

O capiacutetulo 6 traz os resultados obtidos

E finalmente o capiacutetulo 7 encerra o trabalho com uma conclusatildeo e com

possiacuteveis trabalhos futuros

Trabalhos relacionados 18

2 Trabalhos relacionados

O primeiro pesquisador a propor o uso de pontos como primitiva graacutefica foi

Levoy em [4] Ele propotildee o uso de pontos como primitiva de renderizaccedilatildeo e

discute a conversatildeo dos outros modelos para o modelo por pontos

Nos uacuteltimos anos vaacuterios trabalhos importantes tecircm sido realizados na aacuterea

em diversos segmentos em visualizaccedilatildeo podemos destacar os trabalhos de

Pfister [5] e de Zwicker [6] que usam pontos como primitiva de renderizaccedilatildeo e

com resultados praacuteticos interativos muito bons

Em [7] Pauly et al propotildeem algoritmos para modelagem multi-resoluccedilatildeo

em modelos por pontos

Os trabalhos de Curless [8] e Rusinkiewicz [9] discutem os meacutetodos de

aquisiccedilatildeo que consistem em obter uma amostragem de pontos da superfiacutecie do

objeto real por meio de equipamentos como por exemplo o scanner 3D

Nas operaccedilotildees booleanas a interseccedilatildeo das superfiacutecies dos modelos

iniciais seraacute parte do modelo resultado e para ser representada corretamente

precisa ser reconstruiacuteda A reconstruccedilatildeo da superfiacutecie tambeacutem eacute usada na

visualizaccedilatildeo de um modelo Um trabalho significativo na aacuterea de reconstruccedilatildeo de

superfiacutecies estaacute em [10] de N Amenta etal Este trabalho apresenta uma

soluccedilatildeo praacutetica com garantias teoacutericas para este problema e uma heuriacutestica para

o tratamento de arestas vivas a questatildeo mais difiacutecil desta aacuterea Um exemplo

de uma aresta viva eacute o encontro de dois planos natildeo coincidentes

Frequumlentemente a interseccedilatildeo citada acima (interseccedilatildeo entre os modelos iniciais)

gera uma aresta viva (seccedilatildeo 4223)

O algoritmo aqui implementado eacute um plugin para o software PointShop 3D

[11] de Zwicker et al software de ediccedilatildeo de modelos com pontos O PointShop

tem seu coacutedigo aberto documentaccedilatildeo e trabalha com plugins Ele permite a

visualizaccedilatildeo e ediccedilatildeo interativa do modelo por pontos Eacute o uacutenico software livre

disponiacutevel com estas caracteriacutesticas Esta implementaccedilatildeo na forma de um plugin

facilitou muito o trabalho pois natildeo foi necessaacuterio implementar a visualizaccedilatildeo do

modelo 3D Aleacutem disso o Pointshop conteacutem tambeacutem um plugin com a

implementaccedilatildeo do meacutetodo de Pauly et al [3] discutido nesta dissertaccedilatildeo A


execuccedilatildeo dos dois plugins que realizam operaccedilotildees booleanas pocircde ser

comparada

Os trabalhos aqui discutidos satildeo o de Bart Adams e Philip Dutreacute [2] e de

Pauly et al[3] que apresentam meacutetodos diferentes para realizaccedilatildeo de

operaccedilotildees booleanas com pontos Adams e Dutreacute utilizam octrees [1] e Pauly

Kd-Tree [16] e MLS (Moving Least Squares) [18] Estes algoritmos satildeo

discutidos no capiacutetulo 4

O trabalho de Sara F Frisken [12] apresenta um algoritmo para realizar

operaccedilotildees em octree de forma mais eficiente Como estas operaccedilotildees estatildeo

presentes em todo o nosso algoritmo este trabalho certamente oferece uma

forma de otimizaccedilatildeo mas que natildeo foi implementada

Modelagem por Pontos 20

3 Modelagem por Pontos

A computaccedilatildeo graacutefica natildeo lida diretamente com o objeto ou com o

fenocircmeno fiacutesico lida com modelos graacuteficos ou geomeacutetricos Modelos graacuteficos

satildeo estruturas computacionais (abstratas) que capturam aspectos de objetos de

interesse para uma aplicaccedilatildeo como forma cor textura etc Se apenas a forma

ou a geometria do objeto eacute relevante temos modelos geomeacutetricos

Estes modelos satildeo usados em vaacuterias aplicaccedilotildees em computaccedilatildeo graacutefica

como roboacutetica visatildeo computacional simulaccedilotildees realistas anaacutelises estruturais

prototipagem projeto e manufatura de produtos eletromecacircnicos arquitetura

Existem vaacuterios tipos de modelos graacuteficos Esta dissertaccedilatildeo trata de um tipo

muito em voga atualmente que eacute o modelo por pontos

Neste capiacutetulo daremos uma visatildeo geral do modelo por pontos

Introduziremos este modelo e seu processo de criaccedilatildeo Seraacute apresentado o que

eacute um modelo por pontos e o conceito de surfel [5] introduziremos os tipos de

distribuiccedilatildeo dos surfels uma estruturaccedilatildeo aplicada a estes surfels e dados que

eles podem conter As quatro proacuteximas subseccedilotildees (Ideacuteia da representaccedilatildeo

Tipos de distribuiccedilatildeo dos surfels Estrutura de multi-resoluccedilatildeo e Dados que um

surfel pode conter) tratam destes toacutepicos Um modelo por pontos pode ser criado

a partir da conversatildeo de outros tipos de modelagem NURBS por exemplo para

o modelo por pontos ou a partir de um processo de aquisiccedilatildeo Esta uacuteltima forma

de criaccedilatildeo pode ser dividida em duas etapas aquisiccedilatildeo do modelo reconstruccedilatildeo

da superfiacutecie As subseccedilotildees 35 e 36 tratam destas duas etapas

respectivamente A ediccedilatildeo do modelo 3D eacute tratada brevemente na subseccedilatildeo 38

e a sua visualizaccedilatildeo na subseccedilatildeo 37 A apresentaccedilatildeo do processo de aquisiccedilatildeo

(seccedilatildeo 35) eacute baseada no tutorial de W T Correcirca [13] A etapa de ediccedilatildeo 3D

consiste em operaccedilotildees para mudanccedila da cor textura ou forma do modelo Para

esta etapa enfocaremos as operaccedilotildees booleanas que modificam a forma do

modelo ou criam novos modelos

31 Ideacuteia da Representaccedilatildeo


Figura 1 [20] -Um modelo por pontos e sua visualizaccedilatildeo

Um modelo por pontos representa um objeto atraveacutes de seu contorno Eacute

um tipo de representaccedilatildeo B-Rep (Boundary Representation) [1] Este contorno

consiste em uma superfiacutecie 2D posicionada no espaccedilo 3D Na modelagem por

pontos ela eacute representada por um conjunto de pontos 3D que satildeo uma

amostragem dos (infinitos) pontos que formam a superfiacutecie contiacutenua (Figura 1) A

amostragem pode ser obtida de diversas maneiras Uma delas o processo de

aquisiccedilatildeo progrediu muito nos uacuteltimos anos e este foi um dos fatores que tornou

muito importante o desenvolvimento deste modelo por pontos Outra forma de

gerar amostragem eacute fazer uma conversatildeo de um outro modelo NURBS por

exemplo para o modelo por pontos

Estes pontos satildeo denominados surfels e podem conter aleacutem da posiccedilatildeo

3D outras informaccedilotildees como normal agrave superfiacutecie cor textura raio de alcance A

Figura 2 mostra um conjunto de surfels representando uma superfiacutecie No surfel

em destaque podemos ver o raio de alcance rt e a normal n agrave superfiacutecie


Figura 2 [5] A superfiacutecie modelada por surfels O surfel em destaque tem raio de alcance

rt e normal n

Como o modelo natildeo armazena qualquer informaccedilatildeo sobre a conexatildeo entre

os surfels a reconstruccedilatildeo da superfiacutecie contiacutenua a partir dele pode exigir

algumas restriccedilotildees na amostragem (seccedilatildeo 36)

32 Tipos de distribuiccedilatildeo dos surfels

Existem dois tipos de distribuiccedilatildeo dos surfels na modelagem por pontos

uniforme e natildeo uniforme Na distribuiccedilatildeo uniforme cada um deles descreve

partes de mesmo tamanho da superfiacutecie Na natildeo uniforme cada surfel armazena

a informaccedilatildeo de seu raio de alcance que eacute o raio do disco que este surfel

representa

A distribuiccedilatildeo uniforme tem a vantagem de ser mais simples e natildeo ser

necessaacuterio armazenar o raio de alcance do disco mas ela apresenta a seguinte

desvantagem se o modelo possui regiotildees com muito detalhe e regiotildees com

pouco detalhe ele teraacute que manter uma alta densidade mesmo nas regiotildees de

poucos detalhes

33 Estrutura de multi-resoluccedilatildeo

Um objeto pode ser representado em vaacuterios niacuteveis de detalhes Por

exemplo podemos representar um mesmo objeto com vaacuterias resoluccedilotildees

diferentes Este conceito pode ser aplicado ao modelo por pontos Desta forma

um modelo eacute representado por uma estrutura hieraacuterquica (uma aacutervore por

exemplo) onde em cada niacutevel temos uma representaccedilatildeo do objeto em uma


determinada resoluccedilatildeo Em [7] Pauly et al propotildeem algoritmos para modelagem

multi-resoluccedilatildeo em modelos por pontos

34 Dados que um surfel pode conter

Cada surfel armazena sua localizaccedilatildeo e pode tambeacutem conter informaccedilotildees

como a cor ou coordenadas de textura Se a amostragem natildeo for uniforme o

surfel conteacutem a informaccedilatildeo do raio de alcance que eacute o raio de um disco cujo

centro eacute a posiccedilatildeo do surfel O surfel pode tambeacutem conter o vetor normal agrave

superfiacutecie e assim o surfel pode ser visto como um disco orientado A superfiacutecie

tambeacutem pode ser vista como uma superfiacutecie orientada

35 Aquisiccedilatildeo do modelo

Esta introduccedilatildeo sobre aquisiccedilatildeo do modelo aqui apresentada baseia-se no

tutorial de W T Correcirca [13]

O processo de aquisiccedilatildeo consiste em obter uma amostragem de pontos da

superfiacutecie do objeto real por meio de equipamentos como por exemplo o

scanner 3D Eacute uma aacuterea que tem progredido muito nos uacuteltimos anos A

resoluccedilatildeo e a precisatildeo dos equipamentos de aquisiccedilatildeo tecircm melhorado bastante

e o custo deles reduzido de forma significativa Isso possibilita que a aquisiccedilatildeo

de modelos 3D seja usada em aplicaccedilotildees de desenho industrial arte ou em

produtos para a aacuterea de entretenimento O consequumlente maior uso destes

equipamentos criou a necessidade de avanccedilos no tratamento dos seus dados de

saiacuteda que satildeo um conjunto de pontos

Este processo pode ser dividido em trecircs partes [13] aquisiccedilatildeo da

geometria aquisiccedilatildeo da textura e correccedilatildeo de falhas da aquisiccedilatildeo

351 Aquisiccedilatildeo da geometria

Existem vaacuterios meacutetodos de aquisiccedilatildeo da geometria Curless [8] e

Rusinkiewicz [9] classificaram estes meacutetodos em trecircs categorias meacutetodos por

contato transmissatildeo e reflexatildeo

O meacutetodo por contato toca a superfiacutecie do objeto com uma sonda e grava

a posiccedilatildeo Este meacutetodo do qual o Coordinate Measuring Machines (CMMs) eacute


um exemplo eacute bastante preciso mas eacute muito lento e natildeo adequado a objetos

fraacutegeis

Meacutetodos por transmissatildeo projetam ondas de energia sobre o objeto e

gravam a energia transmitida Por exemplo tomografia computadorizada que

projeta ondas de raio-x sobre o objeto e mede a quantidade de radiaccedilatildeo que

passa atraveacutes dele O resultado eacute um modelo geomeacutetrico de alta resoluccedilatildeo Este

meacutetodo pode captar detalhes do objeto que natildeo satildeo visiacuteveis de fora do objeto

Por outro lado ele eacute caro e arriscado

Meacutetodos por reflexatildeo podem ser oacuteticos ou natildeo-oacuteticos Natildeo-oacuteticos incluem

radares que medem a distacircncia a um objeto enviando microondas ou ondas

sonoras para o objeto e gravando o tempo que a onda gasta para retornar Estes

meacutetodos natildeo satildeo muito precisos nem raacutepidos

Meacutetodos por reflexatildeo oacuteticos podem ser passivos ou ativos Meacutetodos oacuteticos

passivos natildeo interagem com o objeto e incluem teacutecnicas de visatildeo computacional

como shape-from-shading stereo triangulation optical flow e meacutetodos de

decomposiccedilatildeo para video streams Estes meacutetodos raramente constroem

modelos precisos e sua maior aplicaccedilatildeo eacute em reconhecimento de objetos

Meacutetodos oacuteticos ativos projetam luz sobre um objeto de maneira estruturada

e atraveacutes da reflexatildeo da luz determinam a forma do objeto Exemplos satildeo depth

from defocus photometric stereo projected-light triangulation time of flight

Meacutetodos por reflexatildeo oacuteticos ativos tecircm muitas vantagens sobre os passivos tecircm

um melhor desempenho quando natildeo existe textura satildeo mais baratos e mais

robustos e produzem uma amostragem precisa

352 Aquisiccedilatildeo da textura

Idealmente noacutes gostariacuteamos de ter uma completa descriccedilatildeo de como um

ponto da superfiacutecie reflete a luz dependendo do vetor normal a esta superfiacutecie

da direccedilatildeo do raio de luz incidente e do comprimento de onda Tal descriccedilatildeo eacute

conhecida como Bidirectional Reflectance Distribution Function (BRDF) Medir

BRDFs com precisatildeo eacute um problema difiacutecil

Pode-se ter uma aproximaccedilatildeo da aquisiccedilatildeo de cores do objeto tirando

fotos dele O objeto eacute fotografado e a cor de cada ponto da superfiacutecie eacute obtida a

partir de um mapeamento das fotos 2D para o modelo 3D Para mapear a

fotografia agrave geometria precisamos conhecer os paracircmetros de projeccedilatildeo da

cacircmera e a sua posiccedilatildeo no momento em que a foto foi batida Para cada ponto


3D do modelo encontramos sua projeccedilatildeo 2D no plano da cacircmera e associamos

a cor do pixel nesta projeccedilatildeo agrave cor do ponto 3D

353 Correccedilatildeo das falhas da aquisiccedilatildeo

O processo de aquisiccedilatildeo deixa frequumlentemente buracos no modelo devido

a ruiacutedos no processo ou agrave impossibilidade de aquisiccedilatildeo de determinadas partes

de uma superfiacutecie Estes buracos devem ser corrigidos Pode-se usar por

exemplo um filtro de passa-baixa para remoccedilatildeo de ruiacutedos [14] Meacutetodos de

difusatildeo geomeacutetrica tecircm sido aplicados para preenchimento dos buracos [15] A

correccedilatildeo das falhas eacute tida como um preacute-processamento para o processo de

reconstruccedilatildeo da superfiacutecie contiacutenua (seccedilatildeo 36)

36 Reconstruccedilatildeo da superfiacutecie (contiacutenua) a partir do modelo (discreto)

A reconstruccedilatildeo da superfiacutecie contiacutenua consiste em a partir de um conjunto

natildeo estruturado de pontos obter um modelo contiacutenuo desta superfiacutecie Esta

reconstruccedilatildeo eacute frequumlentemente exigida para um modelo por pontos Na sua

visualizaccedilatildeo podemos desejar focar qualquer parte do modelo Para fazermos

operaccedilotildees booleanas com os modelos podemos querer determinar exatamente

onde eles se intersectam

No entanto natildeo precisamos ter necessariamente a representaccedilatildeo contiacutenua

de todo o objeto ao mesmo tempo A reconstruccedilatildeo desta superfiacutecie a partir dos

pontos amostrados pode ser feita no momento que for mais adequado agrave

aplicaccedilatildeo Na visualizaccedilatildeo a reconstruccedilatildeo pode ser feita na projeccedilatildeo 2D da

parte do modelo em foco (seccedilatildeo 37) Para operaccedilotildees booleanas pode-se

reconstruir apenas a aacuterea da interseccedilatildeo dos modelos

Este processo de reconstruccedilatildeo de superfiacutecie tem sido muito estudado em

modelagem geomeacutetrica e geometria computacional nos uacuteltimos anos O trabalho

mais importante desta aacuterea eacute o trabalho de Amenta et al [10] que foi a primeira

soluccedilatildeo com garantias demonstraacuteveis para este problema de reconstruccedilatildeo de

superfiacutecie A seccedilatildeo 44 explica estes conceitos e o trabalho [10] Este trabalho

demonstra que teoricamente para que a reconstruccedilatildeo da superfiacutecie (contiacutenua) a

partir das amostras seja correta a amostragem deve ser adequada Ele usa o

conceito de ldquoEixo Medialrdquo para definir o que eacute uma amostragem adequada


(seccedilatildeo 44) Em duas dimensotildees os veacutertices de Voronoi de uma amostragem

densa aproximam o ldquoEixo Medialrdquo da amostragem

Por meio deste conceito de Eixo Medial [1016] obtecircm-se paracircmetros

teoacutericos para a definiccedilatildeo de amostragem adequada e baseado neste conceito

o algoritmo apresentado em [10] traz uma soluccedilatildeo praacutetica para o problema

obtendo uma malha poligonal a partir do modelo por pontos

O PointShop 3D [11] software de ediccedilatildeo de modelos por pontos utilizado

nesta pesquisa faz quando necessaacuterio a reconstruccedilatildeo da superfiacutecie Para isso

o PointShop 3D explora a vizinhanccedila local (surfels vizinhos de acordo com suas

posiccedilotildees) Ele usa o conceito de Eixo Medial para justificar seu meacutetodo de

reconstruccedilatildeo da superfiacutecie que na praacutetica apresenta resultados bastante

satisfatoacuterios apesar de teoricamente natildeo ter garantias [16]

37 Visualizaccedilatildeo do modelo

A primeira abordagem para visualizaccedilatildeo de um modelo por pontos foi

construir uma malha de poliacutegonos a partir dos surfels e renderizaacute-la Mas a

construccedilatildeo de malhas a partir dos surfels eacute um processo muito caro e lento

principalmente para modelos complexos Na tentativa de obter uma visualizaccedilatildeo

interativa do modelo por pontos estatildeo sendo estudadas teacutecnicas que utilizam

surfels como primitiva de visualizaccedilatildeo A ideacuteia foi apresentada inicialmente por

Levoy [4]

Figura 3 [21] -Modelo por pontos e sua renderizaccedilatildeo usando Surface Splatting


O objetivo da renderizaccedilatildeo a partir dos surfels eacute projetaacute-los na tela e

reconstruir as superfiacutecies de forma contiacutenua sem buracos Para que esta

renderizaccedilatildeo seja amplamente utilizada deve-se ter cuidado com o uso de

memoacuteria e com a qualidade da imagem gerada Teacutecnicas recentes como Surface

Splatting [6] faz a renderizaccedilatildeo interativamente com qualidade (Figura 3)

comparada a outros meacutetodos de renderizaccedilatildeo como Image Based Rendering

Em geral a visualizaccedilatildeo do modelo por pontos pode ser dividida nas seguintes

etapas

- warping - projeccedilatildeo em perspectiva de cada ponto do modelo na tela

processo anaacutelogo agrave projeccedilatildeo de veacutertices dos triacircngulos na malha triangular Se

um pixel da tela estiver contido em mais de uma projeccedilatildeo de surfels (vizinhos)

ou seja mais de um ponto cobre este pixel os atributos destes pontos seratildeo

combinados

- shading por ponto - o processo de shading eacute realizado para cada ponto

visiacutevel (os pontos que natildeo satildeo vistos do ponto de vista em questatildeo devem ser

retirados) Qualquer modelo local de shading pode ser aplicado Uma nova

teacutecnica foi proposta em Surface Splatting [6]

- reconstruccedilatildeo da imagem ndash pixels que natildeo ldquoreceberamrdquo projeccedilatildeo de

nenhum ponto formam buracos na imagem Esta imagem deve ser reconstruiacuteda

sem buracos sem aliasing e as superfiacutecies devem ser reconstruiacutedas de forma

contiacutenua e devem ser ldquosuavizadasrdquo (smooth surface)

Os algoritmos de renderizaccedilatildeo por pontos podem tratar a questatildeo de

buracos na visualizaccedilatildeo de trecircs formas [17]

Detecccedilatildeo e preenchimento de buracos no espaccedilo da tela pontos satildeo

projetados na tela e pixels que natildeo receberam pontos satildeo detectados (buracos)

Para preencher estes buracos que natildeo receberam pontos eacute feita uma

interpolaccedilatildeo entre os vizinhos

Geraccedilatildeo de mais pontos a superfiacutecie eacute interpolada no espaccedilo do modelo

para garantir que todos os pixels recebam pelo menos a projeccedilatildeo de um ponto

Splatting um surfel eacute projetado na tela e sua contribuiccedilatildeo eacute espalhada de

forma diferenciada para os pixels vizinhos Agrave medida em que o vizinho se torna

mais distante a contribuiccedilatildeo do surfel diminui

Raumlsaumlnen faz uma analogia do processo de renderizaccedilatildeo proposto em [6]

com o mapeamento de textura [15] No mapeamento de textura para um

determinado pixel da tela satildeo encontrados os pontos da textura que afetam este


pixel Num sentido inverso em splatting para um determinado surfel (que

representa a textura) satildeo encontrados os pixels da tela que este surfel afeta

38 Ediccedilatildeo do modelo

Ediccedilatildeo de um modelo 3D consiste em operaccedilotildees que modificam

caracteriacutesticas deste modelo como cor textura forma ou criam novos modelos

O software PointShop 3D [11] software de ediccedilatildeo de modelos por pontos 3D

implementa vaacuterias destas operaccedilotildees (ver seccedilatildeo 52)

Para modificar a forma de um modelo ou criar um novo satildeo muito usadas

as operaccedilotildees booleanas que eacute o nosso enfoque nesta dissertaccedilatildeo Na

modelagem CSG (Constructive Solid Geometry) as operaccedilotildees booleanas satildeo

usadas juntamente com primitivas soacutelidas para definir um modelo No entanto

em alguns tipos de modelos estas operaccedilotildees satildeo difiacuteceis como por exemplo

em malhas poligonais Com pontos elas podem ser feitas interativamente [32]

Operaccedilotildees Booleanas com Pontos 29

4 Operaccedilotildees Booleanas com Pontos

Operaccedilotildees booleanas satildeo as operaccedilotildees de uniatildeo interseccedilatildeo e diferenccedila

definidas na teoria matemaacutetica de conjuntos Estas operaccedilotildees satildeo aplicadas em

modelos soacutelidos para alteraacute-los ou para criar novos modelos A Figura 4 abaixo

mostra a criaccedilatildeo de trecircs novos modelos a partir de quatro modelos iniciais

Figura 4 [22] Trecircs modelos novos foram criados a partir dos quatro iniciais (esfera

cilindro dois cubos) O primeiro eacute a esfera menos um cubo em seguida retirou-se outro

cubo e por uacuteltimo retirou-se o cilindro

Estas operaccedilotildees satildeo aplicadas em objetos modelados por pontos em dois

trabalhos no trabalho de Bart Adams e Philip Dutreacute [2] e no trabalho de Pauly

et Al [3] Neste capiacutetulo a seccedilatildeo 41 apresenta a parte comum aos dois

trabalhos e as seccedilotildees 42 e 43 apresentam as particularidades de cada um A

seccedilatildeo 44 discute uma questatildeo natildeo explicitada em nenhum dos dois trabalhos

41 Meacutetodos para realizar operaccedilotildees booleanas em objetos modelados por pontos

A Figura 5 mostra o resultado do meacutetodo de Adams[2] operaccedilotildees de

uniatildeo diferenccedila e interseccedilatildeo de objetos soacutelidos 3D modelados por pontos


Figura 5 [2]-A partir de dois modelos por pontos uma heacutelice e uma cabeccedila as trecircs operaccedilotildees booleanas satildeo mostradas da esquerda para a direita uniatildeo diferenccedila e interseccedilatildeo

Sejam A e B objetos 3D soacutelidos modelados por pontos Definem-se os

seguintes elementos

Af ndash superfiacutecie (contorno) de A que estaacute fora de B

Ad ndash superfiacutecie (contorno) de A que estaacute dentro de B

Bf ndash superfiacutecie (contorno) de B que estaacute fora de A

Bd ndash superfiacutecie (contorno) de B que estaacute dentro de A

O resultado da operaccedilatildeo booleana entre A e B seraacute um modelo C cuja

superfiacutecie de contorno pode ser determinada pela seguinte regra [2] que aqui

chamamos de Regra 1

Regra 1 A U B Af + Bf

A cap B Ad + Bd

A ndash B Af + Bd (com a orientaccedilatildeo invertida)

B ndash A Ad (com a orientaccedilatildeo invertida) + Bf

A Figura 6 mostra as operaccedilotildees com dois modelos A e B

(a) (b)


(c) (d)

Figura 6 [22] (a) Dois modelos A e B (b) Posicionados de forma que A tem

uma parte dentro de B eacute mostrado o resultado A U B Af + Bf (c) Resultado de A ndash B Af

+ Bd (d) Resultado de A cap B Ad + Bd

Bart [2] e Pauly [3] apresentam dois meacutetodos para determinar os

elementos acima Estes dois meacutetodos satildeo construiacutedos a partir dos seguintes

conceitos os elementos Af Ad Bf Bd satildeo uma parte da superfiacutecie modelada por

pontos e portanto satildeo conjuntos de surfels Para determinaacute-los eacute necessaacuteria

entatildeo a classificaccedilatildeo de um surfel (que pode se resumir agrave classificaccedilatildeo de um

ponto que eacute o seu centro) de uma superfiacutecie como dentro ou fora de um outro

modelo Os dois meacutetodos utilizam a seguinte regra para esta classificaccedilatildeo aqui

denominada Regra 2

Regra 2 Dado um ponto x qualquer um volume V determinado por uma superfiacutecie

de contorno S uma amostragem P da superfiacutecie S um ponto p є P que eacute a

amostra mais proacutexima a x um vetor np normal agrave S em p e orientado para fora de

S temos que

(x ndash p) np gt 0 x notinV

Ou seja para classificar um ponto em relaccedilatildeo a um modelo verificamos o

produto interno entre a normal em p (surfel mais proacuteximo a x) e o vetor (x - p)

se este produto interno for maior que zero x natildeo pertence ao volume V e seraacute

classificado como fora senatildeo seraacute classificado como dentro De maneira

ainda mais informal se a normal em p apontar para a direccedilatildeo oposta a x x seraacute

classificado como dentro se apontar para x x seraacute classificado como fora

A Figura 7 mostra a Regra 2


Figura 7 Para classificar o ponto x encontra-se o surfel p (com normal np) mais proacuteximo

a x Se o produto interno entre np e (x ndash p) for maior que zero entatildeo x eacute classificado como

fora senatildeo seraacute classificado como dentro

A validade da Regra 2 eacute discutida na Seccedilatildeo 44 Uma das restriccedilotildees

teoacutericas para garantir-lhe a validade eacute que a superfiacutecie seja suave

Cada um dos dois meacutetodos daacute um tratamento diferente para o uso desta

regra Pauly usa a regra diretamente encontrando o surfel mais proacuteximo a um

ponto e classificando este ponto a partir deste surfel Ele utiliza tambeacutem a

representaccedilatildeo impliacutecita MLS (Moving Least Squares [18]) para casos em que a

Regra 2 poderia falhar e para tratamento de interseccedilotildees [3] Seu meacutetodo vale

para modelos soacutelidos ou natildeo soacutelidos O meacutetodo de Adams e Dutreacute [2] utiliza

octrees [1] criando uma classificaccedilatildeo dos noacutes da octree a partir desta Regra 2

Os pontos satildeo entatildeo classificados de acordo com o noacute da octree que o conteacutem

Este segundo meacutetodo aplica-se somente a modelos soacutelidos Os dois meacutetodos

seratildeo descritos em detalhes nas seccedilotildees abaixo

Como um surfel eacute considerado um disco podemos dizer que surfels de

dois modelos diferentes podem se intersectar A interseccedilatildeo destes dois surfels

corresponde agrave interseccedilatildeo destes dois discos Estes surfels geram problemas

para visualizaccedilatildeo se forem acrescentados ao resultado sem um tratamento

especiacutefico apresentaratildeo artefatos natildeo desejaacuteveis na renderizaccedilatildeo do modelo

resultado (Figura 8) se natildeo forem acrescentados ao resultado deixaratildeo buracos

no modelo


Figura 8 [2] -Interseccedilatildeo de duas esferas agrave esquerda sem nenhum tratamento de interseccedilatildeo agrave direita apoacutes o tratamento de interseccedilatildeo

Aleacutem disso nem sempre esta interseccedilatildeo forma uma superfiacutecie suave

Esta interseccedilatildeo pode formar uma aresta viva (seccedilatildeo 4223) gerando

problemas tambeacutem para o uso da Regra 2 que eacute vaacutelida apenas para superfiacutecies

suaves Eacute necessaacuterio entatildeo fazer um tratamento desta superfiacutecie de interseccedilatildeo

(formada por surfels originados de diferentes modelos) O tratamento de cada

um dos meacutetodos para este caso seraacute tambeacutem abaixo apresentado

42 Meacutetodo de Adams e Dutreacute

O meacutetodo aplica-se somente a modelos soacutelidos Para determinaccedilatildeo dos

elementos da aqui chamada Regra 1 (seccedilatildeo 41) este meacutetodo utiliza uma octree

[1] que subdivide o espaccedilo do modelo em trecircs fora dentro ou no contorno do

modelo Estes espaccedilos satildeo determinados pela classificaccedilatildeo dos noacutes da octree a

partir da Regra 2 Tambeacutem eacute usado o meacutetodo TINN - Triangle Inequality Nearest

Neighbour [19] - para otimizar a pesquisa dentro do noacute A seguir descrevemos o

modelo usado neste meacutetodo apresentando os dados associados aos pontos o

tipo de distribuiccedilatildeo e o algoritmo que realiza as operaccedilotildees

421 Modelo por Pontos em Adams e Dutreacute

Os surfels neste meacutetodo contecircm as seguintes informaccedilotildees posiccedilatildeo do

surfel xs orientaccedilatildeo do surfel ns e raio de alcance do surfel rs O surfel pode ser

pensado como um disco ortogonal a ns com centro xs e raio rs O raio eacute

escolhido de tal forma que a projeccedilatildeo dos discos no plano da imagem se

sobreponham


Os objetos representados satildeo soacutelidos A distribuiccedilatildeo dos surfels eacute

uniforme embora o algoritmo natildeo exija esta condiccedilatildeo Para cada soacutelido eacute

definido um rmax = Max rs o raio de alcance do maior surfel pertencente agrave

superfiacutecie do soacutelido Como o raio eacute escolhido de tal forma que a projeccedilatildeo dos

discos no plano da imagem se sobreponham o controle da amostragem eacute

entatildeo ligado agrave renderizaccedilatildeo

422 Algoritmo de Operaccedilotildees Booleanas

Utilizando objetos modelados da forma descrita acima o meacutetodo realiza

operaccedilotildees de uniatildeo interseccedilatildeo e diferenccedila com modelos soacutelidos Supondo dois

modelos soacutelidos S1 e S2 O algoritmo pode ser dividido nas seguintes etapas

Criaccedilatildeo de uma octree para cada modelo Teste Dentro-Fora Tratamento da

interseccedilatildeo Estas etapas satildeo apresentadas nas proacuteximas seccedilotildees

4221 Criaccedilatildeo de uma octree para cada modelo

Eacute criada uma octree [1] para cada modelo A criaccedilatildeo de uma octree eacute feita

da seguinte forma

Gera-se a ldquoCaixa envolventerdquo caixa alinhada com os eixos que conteacutem

todo o modelo A ldquoCaixa envolventerdquo corresponde ao noacute raiz da octree Este noacute

conteacutem inicialmente todos os surfels do modelo Em seguida o noacute raiz eacute

dividido em oito noacutes filhos Os surfels satildeo distribuiacutedos entre estes oito noacutes Cada

um deles caso contenha surfels eacute dividido novamente em 8 filhos e seus surfels

satildeo redistribuiacutedos entre eles Este processo eacute repetido recursivamente enquanto

o nuacutemero de surfels do noacute for maior que zero ou ateacute uma profundidade maacutexima

preacute-definida da octree ser alcanccedilada

Cada noacute da octree deve ser classificado O objetivo desta classificaccedilatildeo eacute

determinar que parte da octree estaacute dentro do modelo e que parte estaacute fora Os

noacutes da octree satildeo entatildeo classificados como ldquodentrordquo ldquoforardquo e ldquocontornordquo

Podemos ilustrar esta classificaccedilatildeo em 2D a Figura 9 mostra uma quadtree

classificada


Figura 9-Um objeto representado por pontos com suas normais e sua quadtree correspondente classificada os noacutes cinza claro estatildeo dentro do modelo noacutes cinza mais escuro estatildeo fora do modelo e noacutes com cinza intermediaacuterio satildeo noacutes cheios noacutes que conteacutem pontos

O noacutes que conteacutem surfels satildeo classificados como ldquocontornordquo Para

classificar um noacute vazio existem trecircs casos

o noacute vazio tem apenas um vizinho-irmatildeo natildeo vazio

o noacute vazio tem mais de um vizinho-irmatildeo natildeo vazio

o noacute vazio natildeo tem vizinhos-irmatildeos natildeo vazios

No primeiro caso o noacute vazio eacute classificado pelo seu vizinho natildeo vazio No

segundo caso considera-se qualquer um dos vizinhos natildeo vazios No terceiro

caso classifica-se primeiro os noacutes vizinhos e eacute dada a mesma classificaccedilatildeo para

o noacute vazio Como cada noacute natildeo folha de uma octree tem pelo menos um noacute filho

natildeo vazio sempre pode ser feita a classificaccedilatildeo dos noacutes vazios A classificaccedilatildeo

eacute feita da seguinte forma dentre os surfels do vizinho-irmatildeo escolhido encontra-

se o surfel mais proacuteximo ao noacute a ser classificado Se a normal deste surfel

aponta para o noacute vazio a ser classificado entatildeo ele eacute classificado como ldquoforardquo

Se a normal aponta no sentido contraacuterio entatildeo ele eacute classificado como ldquodentrordquo

De maneira mais formal sejam cv e cc coordenadas dos centros do noacute vazio e

do noacute contorno respectivamente Seja s o surfel mais proacuteximo ao noacute vazio e ns

a normal em s Se ( cv - cc )٠ ns gt 0 ( produto interno entre a normal em s e o

vetor cv - cc for maior que zero ) o noacute vazio seraacute classificado como ldquoforardquo

Senatildeo seraacute classificado como ldquodentrordquo

Em geral os noacutes ldquocontornordquo satildeo subdivididos em trecircs partes uma que estaacute

fora do modelo uma que estaacute dentro do modelo e uma terceira que conteacutem os

surfels Esta subdivisatildeo eacute feita por meio da criaccedilatildeo de dois planos paralelos que


dividem o noacute Para determinar estes planos calcula-se o vetor nm igual agrave

meacutedia das normais dos surfels do noacute nm = sum ns sum ns onde ns eacute a normal de

cada surfel do noacute

Em seguida encontra-se o surfel com maior produto interno entre a sua

normal e a normal meacutedia d1=Max(nm ٠ ns) Este surfel juntamente com a normal

meacutedia define um dos planos Encontra-se tambeacutem o surfel com menor produto

interno entre a sua normal e a normal meacutedia d2=Min(nm ٠ ns) Este surfel

juntamente com a normal meacutedia define o outro plano A Figura 10 mostra a

divisatildeo de um noacute de uma quadtree nas trecircs partes dentro do modelo fora do

modelo e no ldquocontornordquo

Esta subdivisatildeo aplica-se apenas a noacutes que conteacutem surfels cujas direccedilotildees

natildeo variem em mais de 90 graus Caso isso ocorra ele natildeo seraacute subdividido Ou

seja se um noacute possuir dois vetores normais (de dois surfels diferentes) que

formem um acircngulo maior que 90 graus ele natildeo seraacute subdividido

Figura 10 [2] -Divisatildeo de noacute de contorno a parte agrave esquerda estaacute fora do modelo a parte agrave direita estaacute dentro do modelo e a faixa intermediaacuteria conteacutem os surfels

4222 Teste Dentro-Fora

O Teste Dentro-Fora faz a classificaccedilatildeo dos surfels de um modelo como

ldquodentrordquo ou ldquoforardquo de outro modelo Portanto aplicaremos este mesmo teste duas

vezes uma para o modelo S1 em relaccedilatildeo ao modelo S2 e outra para S2 em

relaccedilatildeo a S1 Vamos mostrar o teste Dentro-Fora para o caso da classificaccedilatildeo

dos surfels do modelo S1 em relaccedilatildeo a S2


No item anterior foram criadas duas octrees uma para o modelo S1 e

outra para o modelo S2 Chamemos de A e B as octrees de S1 e S2

respectivamente Para classificar S1 em relaccedilatildeo a S2 inicialmente eacute feita uma

avaliaccedilatildeo da posiccedilatildeo de A em relaccedilatildeo a B A e B podem estar nas seguintes

situaccedilotildees

- A natildeo intersecta B

- A intersecta apenas noacutes ldquoforardquo de B

- A intersecta apenas noacutes ldquodentrordquo de B

- A intersecta noacutes ldquoforardquo e noacutes ldquodentrordquo de B

Para testar estas situaccedilotildees os noacutes satildeo aumentados de rmax o raio do

maior surfel do modelo soacutelido Isto eacute feito para compensar o fato de que o surfel

natildeo eacute apenas um ponto mas sim considerado como um disco

No primeiro e no segundo caso todos os surfels de A satildeo classificados

como ldquoforardquo No terceiro caso todos os surfels de A satildeo classificados como

ldquodentrordquo

No quarto caso temos que percorrer a octree A Comeccedilando pelo noacute raiz

percorre-se os filhos deste noacute Para cada filho os quatro testes acima satildeo feitos

Se o noacute filho encontra-se em um dos trecircs primeiros casos a classificaccedilatildeo eacute dada

como foi citada acima Se um filho estaacute no quarto caso e natildeo eacute um noacute folha

repete-se recursivamente o mesmo procedimento para seus filhos ateacute encontrar-

se um noacute folha Para um noacute que estaacute no quarto caso e eacute folha percorre-se a lista

de surfels que este noacute conteacutem classificando cada um destes surfels Seja sa um

surfel desta lista Para este caso percorre-se a octree B para classificar sa

Primeiramente encontramos o noacute de B que conteacutem sa Se este noacute de B foi

dividido testa-se de acordo com esta divisatildeo do noacute se o surfel sa estaacute na parte

do noacute que estaacute dentro do modelo ele eacute classificado como ldquodentrordquo se sa estaacute na

parte que estaacute fora do modelo ele eacute classificado como ldquoforardquo se sa estaacute na parte

intermediaacuteria ou se o noacute de B natildeo foi subdividido em planos encontra-se sb que

eacute o surfel pertencente a este noacute de B que estaacute mais proacuteximo de sa sa seraacute

entatildeo classificado de acordo com sb Se ( sa - sb )٠ nb gt 0 sa eacute classificado

como ldquoforardquo senatildeo eacute classificado como ldquodentrordquo Se os discos de sb e sa se

intersectam sa eacute marcado como interseccedilatildeo Para encontrar sb o algoritmo

implementa o meacutetodo TINN ndash Triangle Inequality Nearest Neighbour [19]


4223 Tratamento da interseccedilatildeo

Os surfels de A que intersectam surfels de B satildeo classificados como

ldquointerseccedilatildeordquo Se eles natildeo forem incluiacutedos no modelo resultado o soacutelido resultado

teraacute buracos Se eles forem incluiacutedos sem algum tratamento eles natildeo

representaratildeo adequadamente a regiatildeo Em geral o surfel sa (um surfel

ldquointerseccedilatildeordquo de A) eacute dividido em dois pelo plano que conteacutem o surfel sb (surfel de

B que sa intersecta) uma parte que estaacute fora de B e outra que estaacute dentro de B

Dependendo da operaccedilatildeo que estaacute sendo realizada vamos querer manter uma

destas partes do surfel sa no modelo resultado Seja xa a posiccedilatildeo do surfel sa e o

surfel sa uma circunferecircncia de centro xa e raio ra igual ao raio de alcance de sa

O plano que conteacutem o surfel sb define uma corda desta circunferecircncia como

mostra a Figura 11 O surfel sa seraacute substituiacutedo por um surfel menor que

ultrapassa esta corda de uma distacircncia e definida pelo usuaacuterio Para cobrir

completamente a interseccedilatildeo seratildeo adicionados surfels menores que cruzam a

corda de interseccedilatildeo

Figura 11 -Interseccedilatildeo do surfel s e do plano que passa pelo surfel t o surfel mais proacuteximo a s O surfel s eacute substituiacutedo por trecircs surfels menores


O tratamento de interseccedilatildeo proposto por Adams e Dutreacute [2] natildeo soacute evita

os buracos mas tambeacutem cria uma forma de renderizaccedilatildeo de arestas vivas A

colocaccedilatildeo de vaacuterios pequenos surfels na regiatildeo da interseccedilatildeo permite esta

correta renderizaccedilatildeo das ldquoarestas vivasrdquo Desta forma o problema das arestas

vivas eacute resolvido na modelagem (Figura 12) A vantagem de se resolver o caso

na modelagem eacute que natildeo eacute necessaacuterio fazer um tratamento especial na

renderizaccedilatildeo para que mostre esta aresta viva Diferente do tratamento feito

em Pauly (seccedilatildeo 431) que resolve esta questatildeo em tempo de renderizaccedilatildeo

Aleacutem disso o tratamento resolve alguns casos onde a Regra 2 poderia falhar

(veja em Validade da Regra 2-seccedilatildeo 44)

Figura 12 [2] -Agrave direita eacute mostrado o resultado do tratamento de interseccedilatildeo para o caso de Arestas Vivas do objeto agrave esquerda

43 Meacutetodo de Pauly

O meacutetodo aplica-se a objetos soacutelidos e natildeo soacutelidos Os modelos podem ser

obtidos a partir de diferentes entradas como nuvem de pontos irregulares ou por

meio de scanners 3D Cria um modelo hiacutebrido destes objetos usa o modelo por

pontos juntamente com a representaccedilatildeo impliacutecita Moving Least Squares - MLS

[18] Realiza operaccedilotildees booleanas com pontos e utiliza adicionalmente MLS

para alguns casos de classificaccedilatildeo de surfels e no tratamento de interseccedilatildeo A

seguir apresentamos as caracteriacutesticas do modelo por pontos deste meacutetodo e o

algoritmo que realiza as operaccedilotildees


431 Modelo em Pauly

O modelo eacute uma estrutura hiacutebrida de pontos com a representaccedilatildeo impliacutecita

Moving Least Squares - MLS [18] Esta estrutura eacute usada para fazer operaccedilotildees

booleanas e tambeacutem operaccedilotildees de free-form (natildeo abordadas nesta

dissertaccedilatildeo) Para operaccedilotildees booleanas a representaccedilatildeo MLS permite que a

curva de interseccedilatildeo entre os modelos seja reconstruiacuteda e surfels sejam

colocados nesta curva e em alguns casos de classificaccedilatildeo de surfels mostrados

na seccedilatildeo 432 Para este modelo natildeo existem restriccedilotildees quanto agrave forma do

objeto

Os surfels contecircm informaccedilotildees sobre sua posiccedilatildeo e sua normal Aleacutem

disso surfels podem conter informaccedilotildees adicionais como textura cor

propriedades de materiais

A distribuiccedilatildeo dos surfels eacute natildeo-uniforme e a amostragem eacute

aproximadamente adequada (Veja seccedilatildeo 44)


O algoritmo classifica surfels de um modelo como ldquodentrordquo ou ldquoforardquo de

outro modelo Antes de colocarmos como eacute feita esta classificaccedilatildeo devemos

acrescentar que Pauly estende esta classificaccedilatildeo para modelos que natildeo satildeo

soacutelidos Ou seja mesmo um modelo natildeo soacutelido divide o espaccedilo da cena (espaccedilo

em que se encontra o modelo) em dois sub-espaccedilos dentro ou fora do modelo

Pauly faz esta subdivisatildeo da seguinte forma

Como a superfiacutecie que determina o modelo eacute orientada (conteacutem vetores

normais agrave superfiacutecie que apontam para ldquoforardquo do modelo) Pauly considera que

um modelo natildeo soacutelido divide o espaccedilo em dois sub-espaccedilos um ldquoforardquo do

modelo (os vetores normais apontam para este sub-espaccedilo) e um que estaacute

ldquodentrordquo do modelo (os vetores normais apontam para direccedilatildeo oposta a este sub-

espaccedilo) Por exemplo um plano eacute representado como um conjunto de surfels

contidos num determinado espaccedilo geomeacutetrico plano π Cada surfel conteacutem um

vetor normal direcionado Este modelo divide entatildeo o espaccedilo em dois sub-

espaccedilos o sub-espaccedilo que eacute apontado por estes surfels (considerado ldquoforardquo do

modelo) e o sub-espaccedilo que estaacute na direccedilatildeo oposta (considerado ldquodentrordquo do

modelo) Desta forma ele aplica as classificaccedilotildees de ldquodentrordquo e ldquoforardquo de um

modelo tambeacutem a modelos natildeo soacutelidos A partir desta consideraccedilatildeo as


operaccedilotildees booleanas satildeo realizadas com os modelos natildeo soacutelidos da mesma

forma que com os modelos soacutelidos

Para determinar esta classificaccedilatildeo (dentro ou fora do modelo) Pauly utiliza

a Regra 2 Para pesquisa do surfel mais proacuteximo o meacutetodo usa a estrutura Kd-

tree [16] e tambeacutem o algoritmo ANN [16] No entanto o meacutetodo apresenta uma

restriccedilatildeo da Regra 2 ela soacute deve ser usada para classificaccedilotildees de pontos x se

a distacircncia x-p for maior que o espaccedilamento da amostragem local ηp em p

Este espaccedilamento da amostragem local ηp em p eacute um caacutelculo aproximado da

distacircncia meacutedia entre os surfels vizinhos a p Se x estaacute muito proacuteximo agrave

superfiacutecie a classificaccedilatildeo pode falhar Neste caso ele calcula o ponto exato de

S mais proacuteximo a x usando a projeccedilatildeo MLS (ldquoMoving Least Squaresrdquo)

Por questotildees de melhoria de desempenho utiliza-se o fato de que sendo

Ωp (x) a classificaccedilatildeo do ponto x em relaccedilatildeo agrave amostragem P tem-se que Ωp (x)

= Ωp (xrsquo) para todos os pontos de xrsquo que estatildeo dentro da esfera de centro x e

raio igual a x-p - ηp (onde p eacute o surfel mais proacuteximo e ηp eacute o espaccedilamento

local da amostragem em p acima citado) Ou seja sendo x um ponto qualquer p

o surfel mais proacuteximo a x ηp eacute o espaccedilamento local da amostragem em p se

desenharmos uma esfera com centro x e raio igual a x-p - ηp temos que

todos os pontos xrsquo que estatildeo dentro da esfera teratildeo a mesma classificaccedilatildeo de x

Desta forma o nuacutemero de vezes que a classificaccedilatildeo eacute feita (pesquisando-se o

surfel mais proacuteximo ao ponto e usando a Regra 2) diminui em ateacute 90 Assim

em geral a classificaccedilatildeo de um surfel eacute obtida a partir do seu surfel vizinho

Dados

S1 a superfiacutecie MLS de contorno que define o modelo A

S2 a superfiacutecie MLS de contorno que define o modelo B

P1 o conjunto de surfels que representa a superfiacutecie S1


Ωp1 (x) a classificaccedilatildeo do ponto p em relaccedilatildeo a uma amostragem P1

Q1 o subconjunto de P1 que vai compor o resultado



Os conjuntos Q1 e Q2 satildeo obtidos por meio da Tabela 1 mostrada abaixo


Tabela 1 Classificaccedilatildeo para operaccedilotildees booleanas

Para o tratamento de interseccedilatildeo neste meacutetodo satildeo computados pontos

que caem exatamente na curva de interseccedilatildeo e estes satildeo acrescentados ao

modelo resultado Estes pontos satildeo determinados de forma que a densidade da

amostragem vai crescendo agrave medida que os surfels se aproximam da curva de

interseccedilatildeo e convergem para este ponto de interseccedilatildeo como mostra a Figura

13

(a) (b) (c)

Figura 13 - Os novos surfels satildeo colocados exatamente na curva de interseccedilatildeo

e convergem para o ponto de interseccedilatildeo

A Figura 14 mostra o processo de encontrar os surfels que caem nesta

curva de interseccedilatildeo Inicialmente satildeo encontrados todos os pontos de Q1 e Q2

que estatildeo proacuteximos agrave curva de interseccedilatildeo por meio da funccedilatildeo de distacircncia do

operador de projeccedilatildeo MLS Em seguida procura-se todos os pares mais

proacuteximos (q1 є Q1 q2 є Q2 ) e computa-se o ponto q na curva de interseccedilatildeo da

seguinte forma (veja a Figura 14)Seja r o ponto na linha de interseccedilatildeo dos dois

planos tangentes em q1 e q2 e que estaacute mais proacuteximo a estes dois pontos isto eacute

que minimiza a distacircncia ||r-q1|| + ||r-q2|| r eacute a primeira aproximaccedilatildeo de q e agora

pode ser projetado sobre S1 e S2 para obter dois novos pontos de partida q1rsquo e q2

rsquo

para a iteraccedilatildeo Este procedimento pode ser repetido iterativamente ateacute que os

pontos q1 e q2 convirjam ao ponto q na curva de interseccedilatildeo Normalmente este

processo requer menos de trecircs iteraccedilotildees


(a) (b)

(c)

Figura 14 (a) Suponhamos a reta que eacute a interseccedilatildeo do plano tangente a S1 em q1 e o

plano tangente a S2 em q2 O ponto r eacute o ponto desta reta que estaacute mais proacuteximo a q1 e

q2 (b) r eacute projetado sobre S1 e S2 obtendo-se q1acute e q2acute dois novos pontos de partida

para nova iteraccedilatildeo (c) A nova iteraccedilatildeo gera r que eacute uma aproximaccedilatildeo melhor de q

Pauly faz o tratamento de arestas vivas em tempo de renderizaccedilatildeo Ele

faz uma alteraccedilatildeo no renderizador Marca os surfels de interseccedilatildeo e ao

renderizaacute-los satildeo cortados para gerar uma aresta viva

44 Validade da Regra 2

Os dois meacutetodos analisados nesta dissertaccedilatildeo utilizam a seguinte regra

para a classificaccedilatildeo de um surfel

Regra 2 dado um volume V determinado por uma superfiacutecie de contorno

S uma amostragem P da superfiacutecie S um ponto x qualquer um ponto p є P que

eacute a amostra mais proacutexima a x um vetor ny normal a S em p e orientado para

fora de S temos que (x ndash p) np gt 0 x notinV

Em [16] eacute colocado que esta regra eacute tirada da seguinte propriedade da

geometria diferencial (aqui chamada Propriedade 1)

Propriedade 1 Dado um volume V determinado por uma superfiacutecie de

contorno S contiacutenua e duplamente diferenciaacutevel um ponto x qualquer um ponto


y є S que eacute o ponto de S mais proacuteximo a x um vetor ny normal a S em y e

orientado para fora de S temos que (x ndash y) ny gt 0 x notinV

A Figura 15 ilustra esta propriedade

Figura 15 Para verificar se o ponto x estaacute fora de um contorno C encontra-se o ponto y

de C Se o produto interno entre a normal em y e o vetor que liga y a x for maior que

zero entatildeo x estaacute fora de C senatildeo estaacute dentro de C

Pauly assume que tendo uma amostragem P da superfiacutecie S podemos

usar a Propriedade 1 substituindo y por p o surfel mais proacuteximo ao ponto x (x ndash

p) np gt 0 x notinV (Regra 2) Esta amostragem P em seu trabalho eacute

(aproximadamente) uma ldquoamostragem adequadardquo Tambeacutem seu tratamento de

interseccedilatildeo cria uma aproximaccedilatildeo dela (seccedilatildeo 43) Empiricamente a

ldquodiscretizaccedilatildeo da propriedaderdquo eacute vaacutelida a partir desta suposiccedilatildeo Mas isso natildeo foi

demonstrado teoricamente em seu trabalho

Pauly coloca em [16] que natildeo existe ainda uma teoria matemaacutetica rigorosa

de amostragem anaacuteloga a teoria de Fourier para superfiacutecies discretas

A melhor aproximaccedilatildeo teoacuterica para esta aacuterea eacute o uso do Eixo Medial que

foi colocado em [10] Vamos descrever este trabalho brevemente nesta seccedilatildeo

Este trabalho apresenta um algoritmo de reconstruccedilatildeo de superfiacutecie que parte de

uma amostragem adequada (abaixo definida) de pontos e obteacutem uma malha

que eacute topologicamente equivalente agrave superfiacutecie do objeto e agrave medida que a

densidade da amostragem cresce a saiacuteda converge para esta superfiacutecie

Para definir amostragem adequada o trabalho parte do conceito de Eixo

Medial


ldquoEixo Medialrdquo de uma superfiacutecie 2D posicionada no R3 eacute o conjunto

(fechado) de pontos pi para os quais buscando-se o ponto da superfiacutecie que

estaacute mais proacuteximo a pi mais de um ponto pertencentes a esta superfiacutecie satildeo

encontrados A Figura 16 abaixo ilustra o Eixo Medial em 2D

Figura 16 [10] As curvas de cor mais clara satildeo o Eixo Medial da curva em preto

Em duas dimensotildees os veacutertices de Voronoi de uma amostragem densa

aproximam o ldquoEixo Medialrdquo da amostragem (mas esta propriedade natildeo se

estende a 3D) A Figura 17 mostra o Eixo Medial em 3D

Figura 17 [10] Em 3D geralmente o Eixo Medial eacute uma superfiacutecie 2D (em cor mais

clara) Aqui o quadrado eacute o Eixo Medial da superfiacutecie transparente que o contorna

Podemos definir agora a amostragem adequada da seguinte forma

Supondo uma superfiacutecie suave que quer dizer uma 2-manifold duplamente

diferenciaacutevel posicionada no R3 uma ldquoamostragem adequadardquo desta superfiacutecie eacute

aquela na qual a densidade da amostragem eacute (pelo menos) inversamente

proporcional agrave distacircncia ao ldquoEixo Medialrdquo A Figura 18 mostra uma amostragem

adequada


Figura 18 [10] A figura mostra o diagrama de Voronoi de uma amostragem de pontos S

Da mesma forma que o a amostragem aproxima a curva os veacutertices de Voronoi

aproximam o Eixo Medial

Na praacutetica na reconstruccedilatildeo da superfiacutecie uma aproximaccedilatildeo deste ldquoEixo

Medialrdquo eacute computada (devido agrave dificuldade de computaacute-lo exatamente e em

alguns casos ateacute impossibilidade)

Melhorias Propostas 47

5 Melhorias Propostas

No capiacutetulo 4 apresentamos dois meacutetodos que realizam operaccedilotildees

booleanas em modelos por pontos o meacutetodo de Adams e Dutreacute [2] e o meacutetodo

de Pauly[3] Para esta dissertaccedilatildeo usamos o meacutetodo de Adams e Dutreacute [2] e

propomos as seguintes melhorias

- Alteramos o momento em que eacute feita a classificaccedilatildeo da octree Fazemos

esta classificaccedilatildeo durante a sua criaccedilatildeo Os noacutes filhos de um noacute pai P qualquer

satildeo classificados logo apoacutes a criaccedilatildeo de todos estes filhos de P

independentemente do restante da octree ter sido criada Isso pode ser feito

porque a octree eacute construiacuteda na ordem raiz-esquerda-direita (preorder

traversal) e portanto apoacutes todos os filhos de um noacute pai serem criados a parte

necessaacuteria da octree para a classificaccedilatildeo destes filhos jaacute estaacute criada

- A classificaccedilatildeo da octree eacute otimizada classificando-se os cantos dos seus

noacutes como dentro ou fora do modelo Na classificaccedilatildeo de um noacute n1 a partir de seu

vizinho n2 se os cantos que satildeo comuns a n1 e n2 tiverem a mesma

classificaccedilatildeo esta seraacute dada ao noacute Assim diminuiacutemos o nuacutemero de pesquisas

pelo surfel mais proacuteximo que eacute a parte criacutetica da classificaccedilatildeo dos noacutes da octree

em termos de tempo de processamento

- Acrescentamos um valor miacutenimo (maior que zero) para o nuacutemero de

surfels contidos em um noacute que eacute uma das condiccedilotildees de parada na criaccedilatildeo da

octree Verificamos que desta forma diminui-se a chance de erro na classificaccedilatildeo

de partes criacuteticas como ldquoarestas vivasrdquo

Uma comparaccedilatildeo entre a nossa implementaccedilatildeo e a de Pauly tambeacutem seraacute

feita no capiacutetulo 6

51 Descriccedilatildeo do algoritmo

O algoritmo implementado para esta dissertaccedilatildeo baseado no meacutetodo de

Adams e Dutreacute [2] pode ser dividido nas seguintes partes Criaccedilatildeo e

classificaccedilatildeo de uma octree para cada modelo Teste DentroFora Criaccedilatildeo do

modelo resultado Natildeo foi implementado tratamento especial algum de

interseccedilatildeo para o nosso plugin As proacuteximas seccedilotildees apresentam estas partes


511 Criaccedilatildeo e classificaccedilatildeo de uma octree para cada modelo

As ideacuteias do algoritmo satildeo aqui ilustradas em 2D mas a extensatildeo delas

para 3D eacute feita facilmente

Para cada modelo a octree eacute criada e classificada da seguinte forma

Figura 19-Quadtree classificada Os noacutes mais escuros estatildeo fora do modelo os mais claros dentro e os em tom intermediaacuterio satildeo noacutes de contorno

Gera-se uma ldquocaixa envolventerdquo do modelo contendo todos os surfels e

cria-se o noacute raiz da octree que corresponde a esta ldquocaixa envolventerdquo Este noacute

raiz eacute subdividido em oito filhos e seus surfels satildeo distribuiacutedos entre eles Ao

inveacutes de testarmos os valores de xy e z para cada surfel a fim de determinar

para qual filho ele iraacute utilizamos listas auxiliares Primeiro os surfels satildeo

subdivididos em dois grupos pelos valores de x e armazenados em uma lista

auxiliar Em seguida cada uma das listas eacute subdividida pelo valor de y e as

quatro listas obtidas seratildeo subdivididas pelo valor de z Ao final teremos 8 listas

de surfels cada uma delas pertencente a um filho

Cada noacute seraacute entatildeo novamente subdividido enquanto contiver um nuacutemero

de surfels gt nmin (valor preacute-definido) ou enquanto a profundidade da aacutervore lt pmax

(valor preacute-definido) Na figura 19 pmax = 3 e nmin = 3


Figura 20-O noacute cheio eacute dividido em trecircs partes agrave esquerda a regiatildeo estaacute dentro do modelo agrave direita estaacute fora e entre as duas linhas que dividem o noacute estaacute a regiatildeo que conteacutem os surfels

Os noacutes cheios recebem um tratamento especial Eles satildeo subdivididos em

trecircs partes da seguinte forma uma que estaacute fora do modelo outra que estaacute

dentro e uma que conteacutem os surfels Esta subdivisatildeo eacute feita por meio da criaccedilatildeo

de dois planos paralelos que dividem o noacute Para determinar estes planos

calcula-se o vetor nm igual agrave meacutedia das normais dos surfels do noacute nm = sum ns

sum ns onde ns eacute a normal de cada surfel do noacute Em seguida encontra-se o

surfel com maior produto interno entre a sua normal e a normal meacutedia

d1=Max(nm ٠ ns) Este surfel juntamente com a normal meacutedia define um dos

planos Encontra-se tambeacutem o surfel com menor produto interno entre a sua

normal e a normal meacutedia d2=Min (nm ٠ ns) Este surfel juntamente com a normal

meacutedia define o outro plano (Figura 20) Se o noacute conteacutem surfels de superfiacutecies de

orientaccedilotildees diferentes ele natildeo seraacute subdividido ou seja os planos coincidiratildeo

com os planos que delimitam o proacuteprio noacute Este teste foi implementado da

seguinte forma escolhe-se um surfel qualquer do noacute Calcula-se o produto

interno entre a normal deste surfel e as outras normais dos outros surfels deste

noacute Se algum produto interno for menor que zero este noacute natildeo seraacute subdividido

Apoacutes a etapa de subdivisatildeo classificam-se os oito cantos deste noacute como

dentro ou fora do modelo por meio da classificaccedilatildeo de um ponto que

descreveremos na sub-seccedilatildeo 5111


a b

c d

Figura 21-O noacute a eacute classificado pelo noacute c o noacute d tambeacutem eacute classificado pelo noacute c a classificaccedilatildeo do noacute a eacute propagada para o noacute b

Jaacute os noacutes vazios da octree seratildeo classificados como ldquodentrordquo ou ldquoforardquo do

modelo da seguinte forma cada noacute folha vazio eacute classificado a partir de um de

seus irmatildeos vizinhos adjacentes Se ele possuir um vizinho adjacente cheio ele

seraacute classificado por este vizinho se natildeo possuir os vizinhos adjacentes seratildeo

classificados primeiro e ele teraacute esta mesma classificaccedilatildeo (Figura 21) Como tem

que existir sempre pelo menos um noacute cheio entre os filhos de um noacute pai entatildeo

sempre esta classificaccedilatildeo poderaacute ser feita Com a classificaccedilatildeo de todos os

filhos tem-se tambeacutem a classificaccedilatildeo dos cantos do noacute pai

Mf03c003fmx a b

Figura 22-Os cantos a e b do noacute cheio possuem a mesma classificaccedilatildeo fora do modelo Esta classificaccedilatildeo foi dada ao noacute vazio adjacente


Para classificar um noacute vazio por meio de um noacute cheio verificam-se os

cantos comuns destes dois noacutes se todos os cantos tiverem a mesma

classificaccedilatildeo esta seraacute dada ao noacute vazio (Figura 22) Se houver classificaccedilotildees

diferentes escolhe-se o surfel do noacute cheio mais proacuteximo ao noacute vazio faz-se o

produto interno entre a normal deste surfel e o vetor que liga o centro do noacute

cheio ao centro do noacute vazio (ou o vetor que liga o surfel ao centro do noacute vazio)

Se o produto interno for maior que zero o noacute eacute classificado como ldquoforardquo senatildeo eacute

classificado como ldquodentrordquo Para encontrar o surfel (pertencente a um noacute cheio)

mais proacuteximo ao noacute vazio existem dois casos

- O noacute cheio eacute folha percorre-se toda a lista de surfels e escolhe o surfel

mais proacuteximo da fronteira entre o noacute cheio e o vazio

- O noacute cheio natildeo eacute um noacute folha percorrem-se os filhos do noacute cheio ou seja

esta pesquisa eacute feita descendo na octree a partir do noacute cheio procurando o

surfel mais proacuteximo agrave fronteira do pai com o noacute vazio a ser classificado

Classificando o centro do noacute vazio todo o noacute deve ter a mesma

classificaccedilatildeo pois este noacute natildeo conteacutem surfels Para encontrar o surfel do noacute

vazio mais proacuteximo da fronteira entre o noacute cheio e o vazio basta testar o valor da

coordenada se a fronteira eacute o lado direito do noacute cheio escolhe-se o surfel com

maior coordenada lsquoxrsquo se eacute o lado esquerdo escolhe-se o surfel com menor lsquoxrsquo

se lado superior surfel com maior lsquoyrsquo etc A seguir apresentamos a classificaccedilatildeo

de um ponto qualquer pertencente a um noacute cheio

Figura 23- Quadtree classificada


5111 Classificaccedilatildeo de um ponto de um noacute cheio

Figura 24 [2] A normal n eacute a normal meacutedia e os surfels s1 e s2 juntamente com a normal

n definem as retas que dividem o noacute O ponto a estaacute fora do modelo e o ponto b estaacute

dentro do modelo

Para um ponto localizado dentro do noacute faz-se o seguinte teste se o noacute foi

dividido testa-se de acordo com a divisatildeo do noacute se o ponto estaacute na parte do noacute

que estaacute dentro do modelo ele eacute classificado como ldquodentrordquo se o ponto estaacute na

parte que estaacute fora do modelo ele eacute classificado como ldquoforardquo (Figura 24) se o

ponto estaacute na parte que conteacutem os surfels encontra-se o surfel s pertencente ao

noacute mais proacuteximo do ponto e o classifica de acordo com s seja ns a normal em s

cs a coordenada de s cp a coordenada do ponto Se (cp - cs )٠ ns gt 0 o ponto

seraacute classificado como ldquoforardquo Senatildeo seraacute classificado como ldquodentrordquo

Se o noacute natildeo foi dividido em planos esta classificaccedilatildeo a partir do surfel

mais proacuteximo seraacute sempre feita

512 Teste DentroFora


Figura 25-Duas circunferecircncias e suas quadtrees correspondentes

O Teste DentroFora classifica os surfels de um modelo como dentro ou

fora de outro modelo ou na sua interseccedilatildeo Este teste foi aqui implementado

exatamente como foi proposto em Adams e Dutreacute [2] exceto que natildeo foi

implementado o meacutetodo TINN - Triangle Inequality Nearest Neighbour [19]

Cada octree eacute percorrida verificando-se se os seus noacutes ou surfels estatildeo dentro

fora ou no contorno do outro modelo (Figura 25) Sejam A e B duas octrees e

queremos classificar a octree A As duas octrees (AB) satildeo percorridas partindo

da raiz

Para cada noacute de A existem quatro casos (Figura 26) Para testar estas

situaccedilotildees os boxes dos noacutes satildeo aumentados de rmax o raio do maior surfel do

modelo Isto eacute feito para compensar o fato de que o surfel natildeo eacute apenas um

ponto mas sim considerado como um disco

Os quatro casos satildeo

Se o noacute de A natildeo intersecta B entatildeo todos os surfels deste noacute satildeo

classificados como fora

Se o noacute de A intersecta apenas noacutes de B que estatildeo fora do modelo

todos os surfels deste noacute satildeo fora

Se o noacute de A intersecta apenas noacutes de B que estatildeo dentro do modelo

todos os surfels deste noacute satildeo dentro


Se o noacute de A intersecta noacutes de B que estatildeo dentro e tambeacutem noacutes de B

que estatildeo fora testa-se se este noacute de A eacute ou natildeo folha Se natildeo for folha

percorre-se os filhos deste noacute de A ateacute encontrar um noacute folha cheio que

intersecta B Para cada surfel sa deste noacute folha de A encontra-se o surfel de B

mais proacuteximo e classifica-se a coordenada de sa da forma apresentada na seccedilatildeo

5111 Seja sb o surfel usado na classificaccedilatildeo de sa Se os discos de sb e sa

se intersectam sa eacute classificado como ldquointerseccedilatildeordquo

(a) (b)

(c) (d)

Figura 26- a modelos natildeo se intersectam b modelo intersecta noacutes fora c modelo intersecta apenas noacutes dentro d modelo intersecta noacutes dentro e noacutes fora

513 Criaccedilatildeo do modelo resultado

Um novo modelo eacute criado com os seguintes surfels (de acordo com a

operaccedilatildeo booleana escolhida pelo usuaacuterio - veja Regra 1 da seccedilatildeo 41)

Uniatildeo - surfels de A que estatildeo fora de B + surfels de B que estatildeo fora de A


Interseccedilatildeo - surfels de A que estatildeo dentro de B + surfels de B que estatildeo

dentro de A

Diferenccedila A-B - surfels de A que estatildeo fora de B + surfels de B que estatildeo

dentro de A (com orientaccedilatildeo invertida)

Como natildeo foi implementado tratamento especial algum de interseccedilatildeo para

o nosso plugin os surfels que se intersectam satildeo mantidos no modelo resultado

final sem modificaccedilotildees

Descrito o algoritmo vejamos a seguir a sua implementaccedilatildeo

52 Implementaccedilatildeo

Este algoritmo foi implementado na forma de um plugin para o software

PointShop 3D [11] Este plugin foi desenvolvido na linguagem C e no sistema

operacional Windows

A escolha deste tipo de implementaccedilatildeo permitiu-nos usar o software

PointShop para os testes do algoritmo Estes testes foram feitos com os modelos

disponibilizados para o PointShop [11] Nesta seccedilatildeo apresentaremos o software

PointShop e as principais estruturas de dados usadas em nosso plugin

O Pointshop eacute um software aberto com seu coacutedigo disponiacutevel e preparado

para trabalhar com plugins Eacute um software de ediccedilatildeo de modelos 3D por pontos

Ele permite aleacutem de visualizar o modelo alterar as suas caracteriacutesticas como

cor brilho e fazer mapeamento de textura iluminaccedilatildeo filtragem (Figura 27)


Figura 27-Software PointShop 3D com dois modelos carregados na sua cena

Aleacutem disso pode-se criar uma cena com vaacuterios modelos e visualizaacute-los de

qualquer ponto de vista Implementa o virtual trackball para rotacionaacute-los e

transladaacute-los Usa uma iluminaccedilatildeo simples direcional A sua arquitetura eacute

extensiacutevel permite que o usuaacuterio adicione seus proacuteprios componentes ao

sistema Possui trecircs tipos de componentes

ldquoToolsrdquo fornece funcionalidades para ediccedilatildeo interativa de superfiacutecie Satildeo

disponibilizados na ldquotoolbarrdquo

Plugins fornece funcionalidades para processar em um soacute passo

modelos ou partes deles selecionadas Satildeo disponibilizados no menu ldquoPluginsrdquo

Renderes fornece funcionalidades de display para os modelos

Para esta dissertaccedilatildeo foi escolhida a construccedilatildeo do componente Plugin

por adequar-se agrave nossa proposta e ser a mais simples de ser construiacuteda O

PointShop [11] jaacute conteacutem uma tool que executa operaccedilotildees booleanas e

deformaccedilatildeo free-form sobre os modelos carregados na cena usando o meacutetodo

de Pauly [3] apresentado no capiacutetulo 4 O nosso plugin Operaccedilotildees Booleanas

implementa o algoritmo descrito na seccedilatildeo anterior baseado na proposta de


Adams e Dutreacute [2] Uma comparaccedilatildeo entre o nosso plugin e a tool de Pauly [3] eacute


Figura 28-Menu do PointShop com o plugin e as opccedilotildees para operaccedilotildees booleanas

Para se executar o plugin o usuaacuterio precisa carregar dois modelos na

cena do PointShop acionar o plugin informando a operaccedilatildeo que seraacute executada

O plugin executaraacute o algoritmo acima proposto e carregaraacute o resultado na cena

do Pointshop retirando os modelos anteriores

521 Estruturas de Dados

Como vimos o software PointShop [11] trabalha com modelos por pontos

Um modelo deste software descrito na seccedilatildeo 42 conteacutem todas as informaccedilotildees

que o algoritmo proposto em Bart [2] necessita Abaixo relacionamos as


principais estruturas de dados do PointShop usadas no plugin e as principais

estruturas de dados do nosso plugin

As principais classes do PointShop usadas no plugin satildeo

Classe Scene

Classe Objects

Classe SurfelColections

Classe Surfel

Classe StatusBar

Classe Transformer

A hierarquia de dados eacute a seguinte a Scene conteacutem vaacuterios Objects os

quais conteacutem SurfelColections Cada SurfelColections conteacutem Surfels que

suportam uma ou mais propriedades tais como cor difusa cor especular

Classe Scene Classe que representa uma cena que conteacutem modelos

Classe Object Um modelo eacute representado pela classe Object que

conteacutem uma SurfelCollection e as matrizes de transformaccedilatildeo para rotaccedilatildeo

escala e translaccedilatildeo Cada Object eacute identificado pelo seu nome que eacute uacutenico na

Scene O meacutetodo getUniqueName retorna um nome uacutenico Cada Object tem sua

proacutepria matriz de transformaccedilatildeo que pode ser modificada com setRotation

rotate setPosition translate setScale e scale Objects podem ser copiados com

copy Objects consiste em um conjunto de surfels os quais podem ser

recuperados pela getSurfelCollection O Object pode ser ativado com

setActiveObject e recuperado com getActiveObject

Objects podem ser adicionados ou removidos com addObject e

removeObject Os Objects podem ser obtidos pela getFirstObject e

getNextObject

Classe SurfelCollection representa o conjunto de surfels de um modelo

Cada surfelcollection consiste em um conjunto de surfels (SurfelInterface) de

tamanho obtido por getNofSurfels Os surfels podem ser recuperados com

getFirstSurfel getCurrentSurfel e getNextSurfel

A SurfelCollection conteacutem um PropertyDescriptor e uma SurfelList

A SurfelList eacute uma lista duplamente encadeada de surfels Possui os

atributos firstSurfel lastSurfel currentSurfel que satildeo ponteiros para uma

SurfelInterface nSurfels que eacute o nuacutemero de Surfels

A SurfelInterface define a API para os surfels que satildeo os menores

elementos que compotildeem um Object Podem ser considerados como pontos com

uma normal que define a orientaccedilatildeo do ciacuterculo (ou elipse) que seraacute desenhado


tatildeo logo o surfel seja renderizado Tem como atributos dois ponteiros (next e

prev) para SurfelInterface

PropertyDescriptor consiste em ateacute 32 valores descrevendo quais as

propriedades a SurfelInterface suporta

Classe Surfel classe que representa o surfel

Classe StatusBar classe que imprime mensagens na tela Os plugins

podem mandar mensagens para o usuaacuterio pela StatusBar

Mensagens texto podem ser impressas com showMessage O progresso

de uma operaccedilatildeo pode ser indicado com setProgress ou resetProgress

Classe Transformer representa a transformaccedilatildeo entre sistemas de

coordenadas Esta classe fornece meacutetodos para transformar pontos e vetores

entre os diferentes sistemas de coordenadas do Pointshop

A seguir apresentamos as principais estruturas de dados do plugin

Operaccedilotildees Booleanas

As principais estruturas de dados do plugin satildeo boundingbox tree no

lista_surfel surfel

Boundingbox conteacutem dois pontos 3D que definem uma caixa que conteacutem

o modelo um ponto com menores coordenadas xy e z e outro ponto com

maiores xyz

Tree representa a octree do modelo Cada registro conteacutem um ponteiro

para um noacute e oito ponteiros para as 8 octrees filhas

No representa um noacute da octree Conteacutem os seguintes dados

- localizaccedilatildeo do noacute que eacute o canto inferior esquerdo do noacute

- lista_surfel (preenchida apenas para noacutes folha cheios)

- quantidade de surfels do noacute

- classificaccedilatildeo do noacute como dentro fora ou contorno

- classificaccedilatildeo do noacute em relaccedilatildeo a outro modelo

- indica se o noacute eacute folha ou natildeo

- vetor que eacute a meacutedia das normais dos surfels do noacute

- ponto que eacute a meacutedia das localizaccedilotildees dos surfels do noacute

- surfel que tem (entre todos os surfels do noacute) o maior produto interno

entre a sua normal e a normal meacutedia

- surfel que tem (entre todos os surfels do noacute) o menor produto interno


- produto interno maacuteximo e miacutenimo entre as normais dos surfels do noacute e a

normal meacutedia deste noacute


- indica se o noacute conteacutem surfels com normais em sentido oposto (produto

interno entre elas eacute menor que zero)

- classificaccedilatildeo dos oito cantos do noacute

lista_surfels lista em que cada registro conteacutem um apontador para um

surfel e um apontador para o proacuteximo registro

surfel representa o surfel da octree Conteacutem a classificaccedilatildeo em relaccedilatildeo a

outro modelo e um ponteiro para o surfel do Poinshop

Resultados 61

6 Resultados

Neste capiacutetulo apresentamos os testes realizados com o plugin para o

PointShop implementado para esta dissertaccedilatildeo a comparaccedilatildeo deste plugin com

o plugin de Pauly [3] e a comparaccedilatildeo entre o meacutetodo de Adams e Dutreacute [2] e o

meacutetodo de Pauly [3]

61 Testes

Os testes foram feitos em um PC x86 Family 6 261600 KB de RAM sem

placa graacutefica sistema operacional Windows 2000 O plugin foi implementado na

linguagem C

Os modelos usados para os testes satildeo modelos disponibilizados no

PointShop [11] Vale lembrar que o meacutetodo implementado em nosso plugin eacute

restrito a modelos soacutelidos e portanto foram usados apenas estes modelos

soacutelidos para os testes

O modelo na Figura 29 que eacute um dos modelos disponibilizados no

PointShop [11] foi usado para mostrar o resultado das operaccedilotildees realizadas

pelo plugin implementado nesta dissertaccedilatildeo O modelo Igea eacute um modelo soacutelido

que conteacutem 134345 surfels

Resultados 62

Figura 29-Modelo do PointShop Igea

Para realizar as operaccedilotildees este modelo foi carregado na cena do

PointShop duas vezes e um deles colorido de vermelho As Figuras 30 31 32

mostram o resultado da operaccedilatildeo de uniatildeo interseccedilatildeo e diferenccedila

respectivamente Os nuacutemeros de surfels dos modelos resultantes satildeo mostrados

na Tabela 2

Resultados 63

Figura 30-Resultado da uniatildeo de duas Igeas

Figura 31-Resultado da interseccedilatildeo de duas Igeas

Resultados 64

Figura 32-Resultado da diferenccedila entre duas Igeas

Tabela 2-Nuacutemero de surfels dos modelos resultantes

Observamos que o nuacutemero de surfels dos modelos resultantes estaacute

coerente com as figuras dos seus modelos

Para avaliar o tempo de processamento das operaccedilotildees foram realizados

vaacuterios testes com o objetivo de obter uma meacutedia dos tempos de realizaccedilatildeo de

cada operaccedilatildeo Tambeacutem foram armazenados os tempos da criaccedilatildeo das duas

octrees e da classificaccedilatildeo de todos os surfels dos dois objetos (como dentro ou

fora do outro modelo) Estes testes foram feitos usando o modelo Igea A meacutedia

dos tempos de processamento foi calculada e os resultados satildeo mostrados na

Tabela 3 Verificamos que o maior tempo gasto eacute para criaccedilatildeo das octrees

Verificamos tambeacutem que este resultado apresentado eacute similar ao resultado

verificado empiricamente com o plugin de Pauly [3] Os tempos gastos para

realizar as operaccedilotildees satildeo similares e o maior tempo gasto no plugin de Pauly

tambeacutem eacute para inicializaccedilatildeo de suas estruturas de dados que incluem a kd-tree

Operaccedilatildeo Nuacutemero de surfels do modelo resultado

Uniatildeo 189715

Interseccedilatildeo 72225

Diferenccedila 134552

Resultados 65

Operaccedilatildeo Criaccedilatildeo das

Octrees (seg)

Classificaccedilatildeo

(seg)

Criaccedilatildeo do

resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154

Interseccedilatildeo 38585 1585 09547 63982

Diferenccedila 399875 1504 1729 729475

Tabela 3- Meacutedia dos tempos de processamento para as operaccedilotildees com duas Igeas

Com o objetivo de expor melhor os resultados deste trabalho

apresentamos abaixo mais um teste das operaccedilotildees booleanas usando o nosso

plugin Os modelos usados para este segundo teste satildeo o Max Planck e o Male

ambos modelos soacutelidos disponibilizados no PointShop Estes modelos satildeo

mostrados nas figura 33 e 34

O primeiro Max Planck conteacutem 52809 surfels

Figura 33-Modelo do PointShop MaxPlanck

O segundo modelo abaixo Male conteacutem 148138 surfels

Resultados 66

Figura 34-Modelo do PointShop Male

As Figuras 353637 mostram o resultado da operaccedilatildeo de uniatildeo interseccedilatildeo

e diferenccedila respectivamente usando os dois modelos acima Podemos observar

pela figura 35 que o resultado da operaccedilatildeo de diferenccedila neste caso gerou um

modelo resultado com trecircs partes desconexas Os nuacutemeros de surfels de cada

modelo resultado satildeo mostrados na Tabela 5

Figura 35- Resultado da Uniatildeo do modelo Male com MaxPlanck

Resultados 67

Figura 36-Resultado da interseccedilatildeo do modelo Male com o MaxPlanck

Figura 37-Resultado da diferenccedila do modelo Male do modelo MaxPlanck

As meacutedias de tempos de processamento foram calculadas da mesma

forma que o primeiro teste com o modelo Igea acima apresentado Os

resultados satildeo mostrados na Tabela 4 Podemos observar que este teste

Resultados 68

apresenta tempos um pouco menores que o teste com o modelo Igea Isto se

deve ao fato de que o modelo MaxPlanck ser significativamente menor que o

modelo Igea MaxPlanck possui 52809 surfels e Igea conteacutem 134345 surfels


Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285


Diferenccedila 2965 0911 0791 4667

Tabela 4-Tempo de processamento das operaccedilotildees com os modelos MaxPlanck e Male

Operaccedilatildeo Nuacutemero de surfels do resultado

Uniatildeo 126532



Tabela 5-Nuacutemero de surfels dos modelos resultados das operaccedilotildees com os modelos MaxPlanck e Male

Em seguida apresentaremos uma comparaccedilatildeo entre o nosso plugin e o

plugin de Pauly[3] e tambeacutem uma comparaccedilatildeo entre o meacutetodo de Adams e Dutreacute

[2] e o meacutetodo de Pauly [3]

62 Comparaccedilatildeo entre os dois meacutetodos que realizam operaccedilotildees booleanas

A comparaccedilatildeo entre os meacutetodos de Pauly[3] e de Adams e Dutreacute foi feita

em termos de tempo de processamento e em termos conceituais Em termos de

tempo de processamento comparamos o plugin de Pauly[3] com o nosso plugin

Em termos de tempo de processamento verifica-se empiricamente que os

dois meacutetodos apresentam tempos bastante similares Entretanto o tempo de

processamento do algoritmo aqui implementado ainda pode ser melhorado com

Resultados 69

o uso do meacutetodo TINN [19] que foi proposto em Adams[2] - para otimizar a

pesquisa do surfel mais proacuteximo a um ponto que estaacute localizado na regiatildeo de um

noacute que conteacutem surfels - veja seccedilatildeo 42 O uso deste meacutetodo natildeo foi

implementado para este trabalho e a sua implementaccedilatildeo melhoraria o tempo de

resposta do algoritmo Aleacutem disso o trabalho de Sara F Frisken [12] citado no

capiacutetulo 2 apresenta uma otimizaccedilatildeo no uso de octrees que pode ser

incorporada no algoritmo implementado neste trabalho

Em termos conceituais vamos fazer a comparaccedilatildeo do uso do que

chamamos aqui de Regra 2 do tratamento de interseccedilatildeo e do tratamento de

ldquoarestas vivasrdquo

Como vimos na seccedilatildeo 41 tanto o algoritmo implementado nesta

dissertaccedilatildeo baseado no trabalho de Adams e Dutreacute como o meacutetodo de Pauly

[3] parte do que chamamos aqui de Regra 2 para realizar operaccedilotildees booleanas

com pontos Mas cada um destes meacutetodos daacute um tratamento diferente para o

uso desta regra

O meacutetodo de Pauly usa a Regra 2 para classificaccedilatildeo de cada ponto ou de

cada surfel Para classificar um surfel de B sb como dentro ou fora de A eacute

encontrado o surfel de A sa mais proacuteximo a sb e sb eacute classificado a partir de sa

Para encontrar sa Pauly utiliza uma kd-tree Como esta pesquisa para encontrar

sa eacute cara (mesmo usando uma kd-tree) Pauly utiliza uma esfera que conteacutem

pontos com a mesma classificaccedilatildeo (seccedilatildeo 432) e diminui em 90 este nuacutemero

de pesquisas Pauly utiliza tambeacutem a representaccedilatildeo impliacutecita MLS (Moving Least

Squares) para casos em que a Regra 2 poderia falhar e para tratamento de

interseccedilotildees Entretanto o nuacutemero destes casos em que a Regra 2 poderia falhar

eacute muito pequeno E a representaccedilatildeo MLS natildeo eacute uma estrutura simples de ser

implementada Portanto natildeo encontramos vantagens em usar MLS para estes

casos O meacutetodo de Adams e Dutreacute natildeo trata estes casos e na praacutetica

apresenta resultados bastante satisfatoacuterios como foi mostrado Portanto

consideramos que valeria a pena fazer algum tratamento especial para estes

casos se fosse um procedimento simples Para a execuccedilatildeo do algoritmo de

Pauly o uso de MLS natildeo interfere significativamente porque a construccedilatildeo desta

representaccedilatildeo natildeo eacute feita somente para realizar operaccedilotildees booleanas Os testes

empiacutericos que fizemos com o algoritmo de Pauly natildeo incluem a construccedilatildeo desta

representaccedilatildeo

Aparentemente os dois algoritmos satildeo bastante parecidos um usa octrees

e o outro usa kd-tree As duas estruturas de dados satildeo simples e otimizam a

classificaccedilatildeo dos surfels de um modelo como dentro ou fora do outro modelo

Resultados 70

Mas existe uma diferenccedila conceitual entre dois que merece ser destacada O

algoritmo aqui implementado usa a Regra 2 para classificaccedilatildeo dos noacutes de uma

octree e armazena esta octree classificada (ver capiacutetulo 5) Assim na maioria dos

casos natildeo seraacute necessaacuterio encontrar o surfel mais proacuteximo para classificar um

ponto (ou um surfel) como fora ou dentro de um modelo Caso o ponto esteja em

uma aacuterea da octree classificada ele teraacute a classificaccedilatildeo dada agravequela aacuterea A

pesquisa ao surfel mais proacuteximo seraacute feita apenas nos casos em que o ponto a

ser classificado estaacute localizado entre os planos que subdividem um noacute cheio

O uso desta octree classificada levanta uma questatildeo que natildeo foi citada no

trabalho de Adams e Dutreacute que eacute a proximidade desta estrutura (armazenada)

de octree classificada com uma representaccedilatildeo volumeacutetrica do objeto Sendo

assim esta estrutura pode ser aproveitada para outras funccedilotildees aleacutem da

classificaccedilatildeo dos surfels Por exemplo podemos ter uma aproximaccedilatildeo do

volume de uma cena somando os volumes aproximados dos modelos que a

compotildeem Como o enfoque deste trabalho eacute operaccedilatildeo booleana natildeo vamos nos

aprofundar nesta questatildeo

Outra importante diferenccedila entre os dois trabalhos que jaacute foi explicada na

seccedilatildeo 432 eacute que o meacutetodo de Pauly aplica-se a modelos soacutelidos ou natildeo

soacutelidos enquanto que o meacutetodo de Adams e Dutreacute aplica-se somente a modelos

soacutelidos

Quanto ao tratamento de interseccedilatildeo em termos de visualizaccedilatildeo todos os

dois resolvem bem o problema O tratamento de interseccedilatildeo nos dois trabalhos

tambeacutem resolve o problema da validade da Regra 2 (ver seccedilatildeo 44) Entretanto

o tratamento de Adams e Dutreacute natildeo depende da renderizaccedilatildeo sendo portanto

mais portaacutevel Aleacutem disso uma desvantagem do meacutetodo de Pauly eacute o uso da

representaccedilatildeo impliacutecita MLS (ldquoMoving Least Squaresrdquo) do objeto para obter os

pontos exatamente na curva de interseccedilatildeo Esta representaccedilatildeo torna o

tratamento de interseccedilatildeo mais complexo e a vantagem apresentada natildeo eacute tatildeo

significativa para este tratamento de interseccedilatildeo

Conclusatildeo 71

7 Conclusatildeo

Concluiacutemos entatildeo que as escolhas de Adams e Dutreacute por usar uma

octree classificada e pelo tratamento dado agrave interseccedilatildeo satildeo mais abrangentes

que a escolha de Pauly E consideramos que quanto mais abrangente for uma

escolha conceitual mais resultados poderemos tirar dela No caso de Adams e

Dutreacute eles estendem o problema de classificar um ponto para classificar todo o

modelo Como foi citado ele quase fornece uma representaccedilatildeo volumeacutetrica do

modelo Esta aproximada representaccedilatildeo volumeacutetrica pode nos fornecer outras

informaccedilotildees como por exemplo o volume aproximado do modelo

Aleacutem disso o uso da representaccedilatildeo impliacutecita MLS no meacutetodo de Pauly cria

uma complexidade a mais para o meacutetodo sem apresentar vantagens para a

realizaccedilatildeo de operaccedilotildees booleanas que eacute o nosso enfoque

Logo podemos dizer que o meacutetodo de Adams e Dutreacute apresenta as

seguintes vantagens em relaccedilatildeo ao de Pauly

- a estrutura de octree classificada aleacutem de ser usada para classificaccedilatildeo

fornece informaccedilotildees adicionais como volume aproximado do objeto

- o tempo de processamento no meacutetodo de Adams e Dutreacute tende a ser

melhor que no meacutetodo de Pauly se implementadas as melhorias acima citadas e

se colocaacutessemos em consideraccedilatildeo o uso da representaccedilatildeo impliacutecita MLS

(Moving Least Squares)

- o tratamento de interseccedilatildeo de Adams e Dutreacute apresenta a vantagem da

portabilidade ou seja iraacute funcionar independente do algoritmo de renderizaccedilatildeo

utilizado

E as vantagens do meacutetodo de Pauly em relaccedilatildeo ao de Adams e Dutreacute

- a colocaccedilatildeo de surfels exatamente na curva de interseccedilatildeo

- a possibilidade de trabalhar com modelos soacutelidos ou natildeo soacutelidos

E finalizando concluiacutemos que o estudo relatado nesta dissertaccedilatildeo foi

importante por

- fornecer um breve estudo sobre modelagem por pontos uma nova e

promissora aacuterea dentro da computaccedilatildeo graacutefica

Conclusatildeo 72

- por apresentar uma avaliaccedilatildeo dos dois trabalhos existentes sobre

operaccedilotildees booleanas com pontos encontrando as vantagens de cada um

e levantando questotildees que natildeo tinham sido citadas nos trabalhos originais

- por propor e implementar melhorias ao trabalho de Adams e Dutreacute

71 Trabalhos Futuros

Nossa implementaccedilatildeo pode ser ainda evoluiacuteda com as propostas

apresentadas na seccedilatildeo 62 Como observamos o tempo de processamento do

algoritmo aqui implementado ainda pode ser melhorado com o uso do meacutetodo

TINN [19] - que foi proposto em Adams[2] - para otimizar a pesquisa do surfel

mais proacuteximo a um ponto que estaacute localizado na regiatildeo de um noacute que conteacutem

surfels Aleacutem disso o trabalho Simple and Efficient Trasversal Methods for

Quadtrees and Octrees de Sara F Frisken [12] citado no capiacutetulo 2 apresenta

uma otimizaccedilatildeo no uso de octrees Outra proposta para melhorar o tempo de

processamento do algoritmo aqui implementado eacute usar a forma de trabalhar com

octrees apresentada neste trabalho

O trabalho de Adams e Dutreacute [2] eacute aplicado apenas a objetos soacutelidos O

nosso plugin portanto aplica-se somente a este tipo de objeto Jaacute o trabalho de

Pauly[3] eacute aplicado tambeacutem a modelos natildeo soacutelidos Apresentamos como

proposta a um trabalho futuro a extensatildeo do algoritmo aqui implementado para

modelos natildeo soacutelidos O surfel pode conter uma informaccedilatildeo adicional que indica

se ele estaacute delimitando um volume ou natildeo Assim pode-se ter um modelo com

ldquopartes soacutelidasrdquo e ldquopartes natildeo soacutelidasrdquo Por exemplo a uniatildeo de um plano com

uma esfera poderia resultar numa esfera com ldquoabasrdquo (seriam as partes do plano

que estariam fora da esfera) O modelo resultado teria uma parte correspondente

a um espaccedilo 3D (esfera) e outra parte que seria uma superfiacutecie 2D posicionada

no espaccedilo 3D sem delimitar algum volume (abas)

Muitos trabalhos podem ser desenvolvidos aplicando-se o modelo por

pontos em animaccedilatildeo jogos visualizaccedilatildeo de terrenos criaccedilatildeo de protoacutetipos etc

considerando-se a eficiecircncia e simplicidade do modelo E mais especificamente

as operaccedilotildees booleanas com pontos podem ser aplicadas para criaccedilatildeo de

cenaacuterios testes de colisotildees e nestes casos a representaccedilatildeo usando octrees

pode ser mais explorada considerando-se o seu potencial de representaccedilatildeo

volumeacutetrica de um objeto

Referecircncias Bibliograacuteficas 73

8 Referecircncias Bibliograacuteficas

[1] MAumlNTYLAuml M An Introduction to Solid Modeling Computer Science Press 1988

[2] ADAMS B DUTREacute P Interactive Boolean Operations on Surfel-

Bounded Solids Proceedings of SIGGRAPH 2003 San Diego USA 2003

[3] PAULY M KEISER R KOBBELT L GROSS M Shape Modeling

with Point-Sampled Geometry SIGGRAPH 2003 Computer Graphics

Proceedings Annual Conference Series ACM Press ACM SIGGRAPH 2003

[4] LEVOY M WHITTED T The Use of Points as Display Primitives

Technical Report TR 85-022 The University of North Carolina at Chapel Hill

Department of Computer Science 1985

[5] PFISTER H ZWICKER M VAN BAAR J GROSS M 2000 Surfels

Surface Elements as Rendering Primitives SIGGRAPH 2000 pp 335ndash342 New

Orleans LA July 23-28 2000

[6] ZWICKER M PFISTER H VAN BAAR J GROSS M Surface

Splatting SIGGRAPH 2001

[7] PAULY M KOBBELT L GROSS M Multiresolution Modeling of

Point-Sampled Geometry CS Techinical Report 378 September 16 2002

[8] CURLESS B New Methods for Surface Reconstruction from Range Images PhD thesis Stanford University 1997

[9] RUSINKIEWICZ S Real-time Acquisition and Rendering of Large 3D Models PhD thesis Stanford University 2001


[10] AMENTA N BERN M KAMVYSSELIS M A new Voronoi-Based

Surface Reconstruction Algorithm SIGGRAPH 98 Conference proceedings pp

415-421 New York 1998

[11] ZWICKER M PAULY M KNOLL O GROSS M Pointshop 3D an

Interactive System for Point-Based Surface Editing Proceedings of SIGGRAPH 2002 San Antonio TX July 2002

[12] FRISKEN S PERRY R Simple and Efficient Traversal Methods for

Quadtrees and Octrees Journal of Graphics Tools Vol 7 Issue 3 May 2003

[13] CORREcircA W T OLIVEIRA M M Silva C T Wang J

Modeling and Rendering of Real Environments

Revista de Informaacutetica Teoacuterica e Aplicada (Brazilian Journal of Theoretic and Applied Computing) 9(2)127-156 2002

[14] DAVIS J MARSCHNER S GARR M LEVOY M Filling Holes in

Complex Surfaces Using Volumetric Diffusion First International Symposium on 3D Data Processing Visualization Transmission June 2002

[15] RAumlSAumlNEN J Surface Splatting Theory Extensions and Implementation Masterrsquos Thesis Dept of Computer Science Helsinki

University of Technology May 28 2002

[16] PAULY M Point Primitives for Interactive Modeling and Processing of 3D Geometry PhD thesis Federal Institute of Technology (ETH)

of Zurich 2003

[17] HOPPE H DEROSE T DUCHAMP T MCDONALD J

STUELZLE W Surface Reconstruction from Unorganized Points Computer Graphics 26(2)71ndash78 July 1992

[18] ALEXA M BEHR J COHEN-OR D FLEISHMAN S LEVIN D

SILVA C T Point Set Surfaces IEEE Visualization 2001 pp 21ndash28 October

2001


[19] GREENSPAN M GODIN G TALBOT J Acceleration of Binning

Nearest Neighbor Methods Proceedings of Vision Interface 2000 pp 337-

344

[20] MENCL R Reconstruction of Surfaces from Unorganized Three-Dimensional Point Clouds Dissertation Dortmund Univ 2001

[21] KRIVANEK J Representing and Rendering Surfaces With Points

httpciteseernjneccomkrivanek03representinghtml Acesso em 30 jul

2003

[22] KRISTJANSSON ET AL Approximate Boolean Operations on Free-

form Solids Proceedings of SIGGRAPH 01 2001

Heloisa Reis Leal


Dissertaccedilatildeo apresentada como requisito parcial para obtenccedilatildeo do tiacutetulo de Mestre pelo Programa de Poacutes-Graduaccedilatildeo em Informaacutetica da PUC-Rio Aprovada pela Comissatildeo Examinadora abaixo assinada

Prof Waldemar Celes Filho Orientador

Departamento de Informaacutetica-PUC-Rio

Prof Luiz Velho Co-orientador

Instituto de Matemaacutetica Pura e Aplicada (IMPA)

Prof Bruno Feijoacute Departamento de Informaacutetica-PUC-Rio

Prof Marcelo Dreux Departamento de Mecacircnica-PUC-Rio

Prof Paulo Cezar Pinto Carvalho Instituto de Matemaacutetica Pura e Aplicada (IMPA)

Prof Joseacute Eugecircnio Leal Coordenador Setorial do Centro Teacutecnico Cientiacutefico - PUC-Rio

Rio de Janeiro 3 de agosto de 2004




Leal Heloisa Reis





75 f il 30 cm



Informaacutetica







CDD 004



Resumo













Palavras-chave



Abstract












by Pauly et al

Palavras-chave


Computer Graphics

Sumaacuterio











11

Lista de figuras





















12



















13


14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003






Leal Heloisa Reis





75 f il 30 cm



Informaacutetica







CDD 004



Resumo













Palavras-chave



Abstract












by Pauly et al

Palavras-chave


Computer Graphics

Sumaacuterio











11

Lista de figuras





















12



















13


14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003





Resumo













Palavras-chave



Abstract












by Pauly et al

Palavras-chave


Computer Graphics

Sumaacuterio











11

Lista de figuras





















12



















13


14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003




Resumo













Palavras-chave



Abstract












by Pauly et al

Palavras-chave


Computer Graphics

Sumaacuterio











11

Lista de figuras





















12



















13


14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Resumo













Palavras-chave



Abstract












by Pauly et al

Palavras-chave


Computer Graphics

Sumaacuterio











11

Lista de figuras





















12



















13


14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Abstract












by Pauly et al

Palavras-chave


Computer Graphics

Sumaacuterio











11

Lista de figuras





















12



















13


14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Sumaacuterio











11

Lista de figuras





















12



















13


14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003







11

Lista de figuras





















12



















13


14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



11

Lista de figuras





















12



















13


14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



12



















13


14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



13


14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



14

Lista de tabelas



Igeas 65




15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



15
































16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



16




































17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



17











































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003





































comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003





comparada


























































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



















































rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003





















rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003





rt e normal n









representa





poucos detalhes







































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



































fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003





fraacutegeis





















































































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003























































Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003























Levoy [4]










etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003











etapas





combinados

























































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003





































seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003























seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003






seguintes elementos







chamamos de Regra 1


A cap B Ad + Bd




(a) (b)


(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003




(c) (d)











denominada Regra 2




S temos que































no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003

























no modelo























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003

























sobreponham
















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003


















da seguinte forma













classificada




















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003






















































situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003






























situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003








situaccedilotildees










ldquodentrordquo


























































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003










































431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003

























431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003




431 Modelo em Pauly








objeto
















































Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003


























Dados

















13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003










13

(a) (b) (c)












rsquo





(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003




(a) (b)

(c)










































Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003


























Medial

















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



















adequada















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003

















































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003










































































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003











































a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003

























a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003




a b

c d










Mf03c003fmx a b





























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003






























dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003







dentro do modelo





















da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003












da raiz




















(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003











(a) (b)

(c) (d)








dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003





dentro de A










operacional Windows











































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003





































Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



















Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003







Classe Scene

Classe Objects


Classe Surfel

Classe StatusBar

Classe Transformer
















getNextObject




























lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



















lista_surfel surfel



maiores xyz


























Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003











Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Resultados 61

6 Resultados





61 Testes



linguagem C









Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Resultados 62






na Tabela 2

Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Resultados 63



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Resultados 64

















Uniatildeo 189715



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Resultados 65


Octrees (seg)


(seg)


resultado (seg)

Total (seg)

Uniatildeo 39375 1324 18925 7154


Diferenccedila 399875 1504 1729 729475










Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Resultados 66








Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Resultados 67






Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Resultados 68





Octrees (seg)


(seg)


resultado (seg)

Total

(seg)

Uniatildeo 3012 1254 102 5285





Uniatildeo 126532














Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Resultados 69















uso desta regra























Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Resultados 70




















soacutelidos










Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Conclusatildeo 71

7 Conclusatildeo






















utilizado





importante por



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003



Conclusatildeo 72

























































415-421 New York 1998













of Zurich 2003





2001




344




2003


























415-421 New York 1998













of Zurich 2003





2001




344




2003






415-421 New York 1998













of Zurich 2003





2001




344




2003






344




2003



Documents

Heloisa Reis Leal profs - visgraf.impa.br · Computação Gráfica Interativa . Abstract Leal, Heloisa Reis; ... 3.5. Aquisição do modelo 23 ... d (d) Resultado de A ∩ B: A d