Made available in DSpace on 2014-06-12T15:56:34Z (GMT). No. of bitstreams: 2 arquivo2955_1.pdf: 3111597 bytes, checksum: 1a429acd96d2734eec9d3245ce25cf3a (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Modelos de simulação física baseados em pontos vêm se tornando ao longo dos anos uma alternativa à utilização de malhas, visto que além de possiblitarem a simulação de características físicas mais realistas, possibilitam esta realização de forma mais eficiente do que nos modelos baseados em malhas. Esta dissertação de mestrado apresenta o desenvolvimento de uma solução para a simulação baseada em pontos de objetos deformáveis em tempo real, através da implementação de uma técnica livre de malha (meshless), conhecida por Point-Based Animation. Esta técnica utiliza apenas pontos como unidades de simulação, consequentemente reduzindo a necessidade de manter a informação de conectividade entre eles através de arestas. Essa abordagem possibilita a simulação mais eficiente de certos comportamentos, como mudança de topologia, por exemplo. Dessa forma, este modelo de simulação é adequado para a paralelização, podendo ser otimizado para execução em tempo real. Uma versão paralela do algoritmo foi implementada nesta dissertação, a fim de tornar os resultados interativos da versão sequencial do algoritmo em resultados de tempo real. Uma análise comparativa entre uma implementação em um processador de propósito geral (CPU) e uma em uma placa gráfica (GPU), através da abordagem massivamente paralela provida pela NVIDIA Compute Unified Device Architecture (CUDA), mostra um significativo ganho de desempenho. Foi observada a capacidade de simular em GPU dez objetos simultâneos a uma taxa de quadros por segundo (FPS) maior do que a execução de apenas um objeto em CPU, apesar da existência de alguns problemas relativos à precisão e estabilidade, em parte devido a algumas limitações impostas pela utilização da arquitetura de CUDA

Nos últimos anos a utilização de pontos como primitiva gráfica básica vem mostrandose uma poderosa e versátil ferramenta para a computação gráfica. Considerável esforço de pesquisa vem sendo dedicado para encontrar formas eficientes de aquisição, representação, processamento, renderização e animação para conjuntos de pontos. As representações baseadas em pontos têm-se destacado como uma estratégia eficiente em computação desde que se tornou comum extrair modelos geométricos a partir de Scanners 3D, os quais geram grandes quantidades de pontos que aproximam a geometria do objeto. Este trabalho apresenta um conjunto de métodos para tratar a visibilidade aproximada para nuvens de pontos sem informação de conectividade e topologia. Primeiramente é proposto uma abordagem baseada em clusters para acelerar o operador de remoção de pontos proposto por Katz et al. A principal motivação para esta otimização é a possibilidade de conseguir um equilíbrio entre a velocidade e a qualidade do resultado. Também é apresentado uma técnica de renderização baseada em pontos acelerada por hardware chamada Surface Splatting. Esta abordagem utiliza mapeamento de textura com alpha blending para aproximar um filtro de reamostragem Elliptical Weighted Average no espaço de objeto. Juntamente com o Geometry Shader das modernas placas gráficas, produz de forma eficiente imagens de alta qualidade de superfícies amostradas por surfels. Por último é proposto um novo operador de remoção de pontos ocultos acelerado por hardware baseados na técnica de splatting juntamente com um operador morfológico de erosão modificado para reduzir o efeito de silhuetas no resultado final do operador. A motivação para a criação deste novo operador é a baixa eficiência demonstrada pelos métodos existentes para a utilização em aplicações em tempo real onde as nuvens de pontos são muito densas. Todas as técnicas apresentadas neste trabalho podem ser utilizadas em visualização científica com taxas interativas, em particular na visualização direta de geometria baseada em pontos. / In recent years the use of points as a fundamental graphics primitive has proved to be a powerful and versatile tool for computer graphics. Considerable research has been devoted to the efficient representation, modeling, processing, rendering and animation of point-sampled geometry. The point-based representation has gained increasing attention in computer graphics because 3D scanning systems easily extract large information from real-world objects. On the other hand, point sets are more flexible when compared to triangle meshes, because they are not required to maintain consistent topological information. This work presents a set of tools to determine the visibility and also to render a point-based geometry efficiently. Firstly, a cluster-based approach is proposed to speed up the hidden point removal operator proposed by Katz et al. The main idea of this study is to trade-off speed and quality in dynamic scenes of moving or deforming point clouds. After that, a hardware based point rendering technique called Surface Splatting is introduced. This approach uses the texture mapping with alpha blending and the Geometry Shader to approximate the Elliptical Weighted Average filter in object space. This efficient technique produces high quality images as surfel-based geometry. Finally, a new hidden point removal operator is presented. This operator, based on the splatting technique and also hardware accelerated, applies a morphological erosion operation in the depth buffer to reduce the silhouette effect in the final image. The motivation to develop a new operator is the low efficiency demonstrated by existing hidden point removal methods in real time applications, where the point cloud is very dense. All the techniques introduced in this work can be used in scientific visualization with interactive frame rates, particularly when visualizing point-based geometry sets.

Nos últimos anos a utilização de pontos como primitiva gráfica básica vem mostrandose uma poderosa e versátil ferramenta para a computação gráfica. Considerável esforço de pesquisa vem sendo dedicado para encontrar formas eficientes de aquisição, representação, processamento, renderização e animação para conjuntos de pontos. As representações baseadas em pontos têm-se destacado como uma estratégia eficiente em computação desde que se tornou comum extrair modelos geométricos a partir de Scanners 3D, os quais geram grandes quantidades de pontos que aproximam a geometria do objeto. Este trabalho apresenta um conjunto de métodos para tratar a visibilidade aproximada para nuvens de pontos sem informação de conectividade e topologia. Primeiramente é proposto uma abordagem baseada em clusters para acelerar o operador de remoção de pontos proposto por Katz et al. A principal motivação para esta otimização é a possibilidade de conseguir um equilíbrio entre a velocidade e a qualidade do resultado. Também é apresentado uma técnica de renderização baseada em pontos acelerada por hardware chamada Surface Splatting. Esta abordagem utiliza mapeamento de textura com alpha blending para aproximar um filtro de reamostragem Elliptical Weighted Average no espaço de objeto. Juntamente com o Geometry Shader das modernas placas gráficas, produz de forma eficiente imagens de alta qualidade de superfícies amostradas por surfels. Por último é proposto um novo operador de remoção de pontos ocultos acelerado por hardware baseados na técnica de splatting juntamente com um operador morfológico de erosão modificado para reduzir o efeito de silhuetas no resultado final do operador. A motivação para a criação deste novo operador é a baixa eficiência demonstrada pelos métodos existentes para a utilização em aplicações em tempo real onde as nuvens de pontos são muito densas. Todas as técnicas apresentadas neste trabalho podem ser utilizadas em visualização científica com taxas interativas, em particular na visualização direta de geometria baseada em pontos. / In recent years the use of points as a fundamental graphics primitive has proved to be a powerful and versatile tool for computer graphics. Considerable research has been devoted to the efficient representation, modeling, processing, rendering and animation of point-sampled geometry. The point-based representation has gained increasing attention in computer graphics because 3D scanning systems easily extract large information from real-world objects. On the other hand, point sets are more flexible when compared to triangle meshes, because they are not required to maintain consistent topological information. This work presents a set of tools to determine the visibility and also to render a point-based geometry efficiently. Firstly, a cluster-based approach is proposed to speed up the hidden point removal operator proposed by Katz et al. The main idea of this study is to trade-off speed and quality in dynamic scenes of moving or deforming point clouds. After that, a hardware based point rendering technique called Surface Splatting is introduced. This approach uses the texture mapping with alpha blending and the Geometry Shader to approximate the Elliptical Weighted Average filter in object space. This efficient technique produces high quality images as surfel-based geometry. Finally, a new hidden point removal operator is presented. This operator, based on the splatting technique and also hardware accelerated, applies a morphological erosion operation in the depth buffer to reduce the silhouette effect in the final image. The motivation to develop a new operator is the low efficiency demonstrated by existing hidden point removal methods in real time applications, where the point cloud is very dense. All the techniques introduced in this work can be used in scientific visualization with interactive frame rates, particularly when visualizing point-based geometry sets.

Nos últimos anos a utilização de pontos como primitiva gráfica básica vem mostrandose uma poderosa e versátil ferramenta para a computação gráfica. Considerável esforço de pesquisa vem sendo dedicado para encontrar formas eficientes de aquisição, representação, processamento, renderização e animação para conjuntos de pontos. As representações baseadas em pontos têm-se destacado como uma estratégia eficiente em computação desde que se tornou comum extrair modelos geométricos a partir de Scanners 3D, os quais geram grandes quantidades de pontos que aproximam a geometria do objeto. Este trabalho apresenta um conjunto de métodos para tratar a visibilidade aproximada para nuvens de pontos sem informação de conectividade e topologia. Primeiramente é proposto uma abordagem baseada em clusters para acelerar o operador de remoção de pontos proposto por Katz et al. A principal motivação para esta otimização é a possibilidade de conseguir um equilíbrio entre a velocidade e a qualidade do resultado. Também é apresentado uma técnica de renderização baseada em pontos acelerada por hardware chamada Surface Splatting. Esta abordagem utiliza mapeamento de textura com alpha blending para aproximar um filtro de reamostragem Elliptical Weighted Average no espaço de objeto. Juntamente com o Geometry Shader das modernas placas gráficas, produz de forma eficiente imagens de alta qualidade de superfícies amostradas por surfels. Por último é proposto um novo operador de remoção de pontos ocultos acelerado por hardware baseados na técnica de splatting juntamente com um operador morfológico de erosão modificado para reduzir o efeito de silhuetas no resultado final do operador. A motivação para a criação deste novo operador é a baixa eficiência demonstrada pelos métodos existentes para a utilização em aplicações em tempo real onde as nuvens de pontos são muito densas. Todas as técnicas apresentadas neste trabalho podem ser utilizadas em visualização científica com taxas interativas, em particular na visualização direta de geometria baseada em pontos. / In recent years the use of points as a fundamental graphics primitive has proved to be a powerful and versatile tool for computer graphics. Considerable research has been devoted to the efficient representation, modeling, processing, rendering and animation of point-sampled geometry. The point-based representation has gained increasing attention in computer graphics because 3D scanning systems easily extract large information from real-world objects. On the other hand, point sets are more flexible when compared to triangle meshes, because they are not required to maintain consistent topological information. This work presents a set of tools to determine the visibility and also to render a point-based geometry efficiently. Firstly, a cluster-based approach is proposed to speed up the hidden point removal operator proposed by Katz et al. The main idea of this study is to trade-off speed and quality in dynamic scenes of moving or deforming point clouds. After that, a hardware based point rendering technique called Surface Splatting is introduced. This approach uses the texture mapping with alpha blending and the Geometry Shader to approximate the Elliptical Weighted Average filter in object space. This efficient technique produces high quality images as surfel-based geometry. Finally, a new hidden point removal operator is presented. This operator, based on the splatting technique and also hardware accelerated, applies a morphological erosion operation in the depth buffer to reduce the silhouette effect in the final image. The motivation to develop a new operator is the low efficiency demonstrated by existing hidden point removal methods in real time applications, where the point cloud is very dense. All the techniques introduced in this work can be used in scientific visualization with interactive frame rates, particularly when visualizing point-based geometry sets.

Made available in DSpace on 2014-06-12T15:57:17Z (GMT). No. of bitstreams: 2 arquivo3157_1.pdf: 3737373 bytes, checksum: 7ca491f9a72f2e9cf51764a7acac3e3c (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Esta dissertação introduz uma estrutura de dados baseada em gride implementada em GPU. Ela foi desenvolvida para pesquisa dos vizinhos mais próximos em nuvens de pontos dinâmicas, de uma forma massivamente paralela. A implementação possui desempenho em tempo real e é executada em GPU, ambas construção do gride e pesquisas dos vizinhos mais próximos (exatos e aproximados). Dessa forma, a transferência de memória entre sistema e dispositivo é minimizada, aumentando o desempenho de uma forma geral. O algoritmo proposto pode ser usado em diferentes aplicações com cenários estáticos ou dinâmicos. Além disso, a estrutura de dados suporta nuvens de pontos tridimensionais e dada sua natureza dinâmica, o usuário pode mudar seus parâmetros em tempo de execução. O mesmo se aplica ao número de vizinhos pesquisados. Uma referência em CPU foi implementada e comparações de desempenho justificam o uso de GPUs como processadores massivamente paralelos. Em adição, o desempenho da estrutura de dados proposta é comparada com implementações em CPU e GPU de trabalhos anteriores. Finalmente, uma aplicação de renderização baseada em pontos foi desenvolvida de forma a verificar o potencial da estrutura de dados

京都大学 / 0048 / 新制・課程博士 / 博士(医学) / 甲第19225号 / 医博第4024号 / 新制||医||1010(附属図書館) / 32224 / 京都大学大学院医学研究科医学専攻 / (主査)教授 戸井 雅和, 教授 富樫 かおり, 教授 一山 智 / 学位規則第4条第1項該当 / Doctor of Medical Science / Kyoto University / DGAM

Traditional global illumination lighting techniques like Radiosity and Monte Carlo sampling are computationally expensive. This has prompted the development of the Point-Based Color Bleeding (PBCB) algorithm by Pixar in order to approximate complex indirect illumination while meeting the demands of movie production; namely, reduced memory usage, surface shading independent run time, and faster renders than the aforementioned lighting techniques. The PBCB algorithm works by discretizing a scene’s directly illuminated geometry into a point cloud (surfel) representation. When computing the indirect illumination at a point, the surfels are rasterized onto cube faces surrounding that point, and the constituent pixels are combined into the final, approximate, indirect lighting value. In this thesis we present a performance enhancement to the Point-Based Color Bleeding algorithm through hardware acceleration; our contribution incorporates GPU-accelerated rasterization into the cube-face raster phase. The goal is to leverage the powerful rasterization capabilities of modern graphics processors in order to speed up the PBCB algorithm over standard software rasterization. Additionally, we contribute a preprocess that generates triangular surfels that are suited for fast rasterization by the GPU, and show that new heterogeneous architecture chips (e.g. Sandy Bridge from Intel) simplify the code required to leverage the power of the GPU. Our algorithm reproduces the output of the traditional Monte Carlo technique with a speedup of 41.65x, and additionally achieves a 3.12x speedup over software-rasterized PBCB.

Simulating light is a very computationally expensive proposition. There are a wide variety of global illumination algorithms that are implemented and used by major motion picture companies to render interesting and believable scenes. Every algorithm strives to find a balance between speed and accuracy. The Point Based Approximate Color Bleeding algorithm is one of the most widely used algorithms in the field today. The Point Based Approximate Color Bleeding(PBACB) global illumination algorithm is based on the central idea that the geometry and direct illumination of the scene can be approximated by using a point cloud representation. This point cloud representation can then be used to generate the indirect illumination. The most basic unit of the point cloud is a surfel. A surfel is a two dimensional circle in space that contains the direct illumination for that section of space. The surfels are gathered in a tree structure and approximations are generated for the different levels of the tree. This tree is then used to calculate the appropriate color bleeding effect to apply to the surfaces in a rendered image. The main goal of this project was to explore the possibility of applying CUDA to the PBACB global illumination algorithm. CUDA is an extension of the C/C++ programing languages which allows for GPU parallel programming. In this paper, we present our GPU based implementation of the PBACB algorithm. The PBACB algorithm involves three central steps, creation of a surfel point cloud, generation of the spherical harmonics approximations for the point cloud, and using the surfel point cloud to generate an approximation for global illumi- nation. For this project, CUDA was applied to two of the steps of the PBACB algorithm, the generation of the spherical harmonic representations and the ap- plication of the surfel point cloud to generate indirect illumination. Our final GPU algorithm was able to obtain a 4.0 times speedup over our CPU version. We also discuss future work which could include the use of CUDA’s Dynamic Parallelism and a stack free implementation which could increase the speedups seen by our algorithm.

No description available.

Nos anos recentes, suavização de superfícies é um assunto de intensa pesquisa em processamento geométrico. Muitas das abordagens para suavização de malhas usam um esquema de duas etapas: filtragem de normais seguido de um passo de atualização de vértices para corresponder com as normais filtradas. Neste trabalho, propomos uma adaptação de tais esquemas de duas etapas para superfícies representadas por nuvens de pontos. Para isso, exploramos esquemas de pesos para filtrar as normais. Além disso, investigamos três métodos para estimar normais, analisando o impacto de cada método para estimar normais em todo o processo de suavização da superfície. Para uma análise quantitativa, além da comparação visual convencional, avaliamos a eficácia de diferentes opções de implementação usando duas medidas, comparando nossos resultados com métodos de suavização de nuvens de pontos encontrados a literatura / In the last years, surface denoising is a subject of intensive research in geometry processing. Most of the recent approaches for mesh denoising use a twostep scheme: normal filtering followed by a point updating step to match the corrected normals. In this work, we propose an adaptation of such two-step approaches for point-based surfaces, exploring three different weight schemes for filtering normals. Moreover, we also investigate three techniques for normal estimation, analyzing the impact of each normal estimation method in the whole point-set smoothing process. Towards a quantitative analysis, in addition to conventional visual comparison, we evaluate the effectiveness of different choices of implementation using two measures, comparing our results against state-of-art point-based denoising techniques. Keywords: surface smoothing; point-based surface; normal estimation; normal filtering.