Analysis and acceleration of high quality isosurface contouring

Abstract

This work presents an analysis of the GPU implementations of the main isosurface polygonization algorithms. The result of the analysis shows how the GPU may be modified in order to support polygonization of isosurfaces and also how these algorithms are adapted to fit current GPUs. The techniques used in GPU-based versions of Marching Cubes are extended and a polygonization with improved quality is achieved. We propose parallel versions of Dual Contouring and Macet, algorithms which improve accuracy and shape of triangles meshes, respectively. Both GPU approaches extract isosurfaces from large volumetric data in less than one second, improving CPU versions up to two orders of magnitude. The contributions of this work also include a novel table-driven approach of Dual Contouring (DC) for uniform grids. A table is used for quad topology specification, which aids the implementation and cache efficiency of parallel scenarios. It is suitable for stream expansion with GPU versions of both geometry shader and Histogram Pyramids. In addition, our isosurface feature approximation version of DC is more straightforward than Singular Value and QR Decompositions. The vertex positioning does not require diagonalization of matrices. Instead, it uses a simple trilinear interpolation. In order to evaluate the efficiency of the techniques presented in this work, we compare our approaches to state-of-the-art Marching Cubes GPU versions. We also present a deep analysis of GPU architectures for isosurface extraction, in which industry profiling tools are used. This analysis shows bottlenecks of the graphics hardware and helps the evaluation of possible solutions for next generation GPUs.

Este trabalho apresenta uma análise dos principais algoritmos de poligonização de isosuperfícies na GPU. O resultado desta análise mostra tanto como a GPU pode ser modificada para oferecer suporte a este tipo de algoritmo quanto como os algoritmos podem ser modificados para se adaptar as características das GPUs atuais. As técnicas usadas em versões de GPU do Marching Cubes são extendidas e uma poligonização com menos artefatos é gerada. São propostas versões paralelas do Dual Contouring e do Macet, algoritmos que melhoram a aproximação e a forma das malhas de triângulos, respectivamente. Ambas técnicas extraem isosuperfícies a partir de grandes volumes de dados em menos de um segundo, superando versões de CPU em até duas ordens de grandeza. As contribuições desse trabalho incluem uma versão orientada a tabelas do Dual Contouring (DC) para grids estruturados. A tabela é utilizada na especificação da topologia dos quadriláteros, que ajuda a implementação e a eficiência de cache em cenários paralelos. A tabela é adequada para a expansão de streams na GPU em ambos geometry shader e Histogram Pyramids. Além disso, nossa versão de aproximação de características das isosuperfícies é mais simples que a Decomposição de Valores Singulares e também que a Decomposição QR. O posicionamento dos vértices não requer uma diagonalização de matrizes. Ao invés disso, usa-se uma simples interpolação trilinear. Afim de avaliar a eficiência das técnicas apresentadas neste trabalho, comparamos nossas técnicas com versões do Marching Cubes na GPU do estado da arte. Também incluímos uma análise detalhada da arquitetura de GPU para a extração de isosuperfícies, usando ferramentas de avaliação de desempenho da indústria. Essa análise apresenta os gargalos das placas gráficas na extração de isosuperfícies e ajuda na avaliação de possíveis soluções para as GPUs das próximas gerações.