Grupos de arestas : uma nova abordagem para entender a qualidade da malha gerada pelo Marching Cubes e suas variantes

Abstract

Este trabalho descreve uma nova visão sobre um dos algoritmos mais importantes da Computação Gráfica, o algoritmo para a poligonização de isosuperfícies Marching Cubes (MC). Esta visão permite o estudo das situações onde são gerados triângulos de baixa qualidade, uma das grandes deficiências do MC, e serve como suporte à proposta de modificações no algoritmo. Neste trabalho também são propostas três modificações ao MC, com objetivo de gerar triângulos de boa qualidade e manter as características mais atraentes do MC, ou seja, a sua simplicidade, eficiência e robustez. O funcionamento do MC é analisado a partir da decomposição das células de amostragem em Grupos de Arestas. Os Grupos de Arestas permitem o estudo do modo como os triângulos são construídos no interior de cada célula de amostragem, e possibilitam identificar onde e como são gerados triângulos de baixa qualidade. As situações onde triângulos de baixa qualidade são gerados são resolvidas através da proposta de três modificações no algoritmo MC, sendo elas: (1) um critério para conduzir a construção da tabela de triangulações, (2) o reposicionamento das arestas ativas e (3) o deslocamento dos vértices de intersecção sobre as arestas ativas. A primeira modificação é a proposta de um novo critério para conduzir a construção da tabela de triangulações do MC. O critério tem como objetivo o aumento da qualidade da malha gerada, através do uso de triangulações que não resultem nos grupos de arestas que têm maior probabilidade de gerar triângulos de baixa qualidade. A segunda modificação propõe o reposicionamento das arestas ativas. Os grupos de arestas mostram que a posição das arestas ativas influencia a qualidade dos triângulos, o que motiva a criação de um procedimento que reposicione as arestas ativas em relação ao comportamento da isosuperfície. Este procedimento resulta na maximização da distância entre os vértices de intersecção e na melhora na qualidade da malha gerada. A terceira modificação propõe o deslocamento dos vértices de intersecção ao longo das arestas ativas. O movimento dos vértices é controlado por um parâmetro que oferece a oportunidade de comprometer a qualidade de aproximação (distância entre a malha gerada e a isosuperfície) em razão da qualidade da malha. O conjunto de modificações propostas resulta no algoritmo Macet (Marching Cubes with Edge Transformations). O Macet é simples e eficiente, gera malhas com qualidade de aproximação igual ou superior à do MC e onde os triângulos de baixa qualidade ainda têm qualidade comparável ou superior aos métodos disponíveis atualmente.

This work sheds a new light on one of the most important algorithms of Computer Graphics, the isosurface polygonization algorithm Marching Cubes (MC). The analysis described here allows the study of situations where low quality triangles are generated, one of the well-know MC drawbacks, and also supports the proposal of extensions for the algorithm. In this work three extensions for MC are also proposed, all with purpose of increase the quality of the resulting triangulations and keep the simplicity, efficiency and robustness of MC. The MC is studied with the breaking of its sampling cells in Edge Groups. The Edge Groups allow the study of how triangles are generated inside each sampling cell, and make possible to identify where and how low quality triangles are generated. The low quality triangle generation is tackled through the proposal of three modifications to the MC algorithm, namely: (1) a new rule to create the look-up table, (2) the warping of active edges and (3) the displacement of cut vertices along active edges. The first modification is the proposal of a new rule to create the triangulations of the MC look-up table. This rule aims the mesh quality improvement through the creation of triangulations that are based on edge groups with fewer chances of generate low quality triangles. The second modification is the proposal of the active edge warping. The edge groups analysis shows that active edges position have a high impact on the triangle quality, which motivates the proposal of a procedure that warps the active edges in response to the isosurface behavior. This procedure results in the maximization of the distance between cut edges, and, consequently, in the overall mesh quality improvement. The third modification is the proposal of the cut vertex displacement along active edges. The vertex displacement is controlled by a user-defined parameter which results in a tradeoff between approximation quality (the distance between the mesh and the “real” isosurface) and the mesh quality. The set of modifications results in the proposal of the Macet (Marching Cubes with Edge Transformations) algorithm. Macet is simple and efficient, and results in high quality meshes with the same (or higher) MC approximation quality.