...on mesh generation

Extracting Semi-Regular Multiresolution Meshes from Volumes

Extracting isosurfaces from volume data is a long-standing technique in scientific visualization. Isosurfaces are one of the most useful tools for visualizing volume data. They allow the visualization of key structures and surfaces within the volume data. Meanwhile, multiresolution representations have emerged as a critical tool in addressing complexity issues (time and memory) for the large-scale, complex geometries typically found in computer graphics and scientific visualization. There are benefits to extracting a surface that inherently has a hierarchical framework and all the desirable features of multiresolution from the very beginning. Thus, our work focuses on the task of directly extracting semi-regular meshes from volumes. Our general approach involves recursively subdividing a coarse mesh to produce a semi-regular mesh.

One of the most important features of the semi-regular mesh is that it has a higher approximation order than a Marching Cubes mesh or decimated Marching Cubes mesh, which are only piecewise linear approximations of the original surface. A semi-regular mesh has the mathematical structure to represent a higher order surface. This feature is fundamentally important for performing numerical computations associated with the surface. Most of the present work in mesh extraction and simplification is only concerned with the visual appearance of the final mesh, however, if the final mesh will be used for any kind of physical simulation, the function space associated with smoothness and higher approximation order of the surface becomes important. If one wants to compute various high order computations and simulations with the extracted surface, the structure provided by the semi-regular setting is essential. Additionally, the mathematical machinery that is a part of a semi-regular representation

The approach we will take to extracting semi-regular meshes is a coarse-to-fine subdivision, using the machinery of variational calculus to solve for a best fit for the final surface. The algorithm begins by generating a coarse approximation of the surface. First a coarse mesh is generated by tiling geodesic isolines extracted from the volume. This input mesh will be iteratively refined and repositioned so that it has a semi-regular structure and best fits the desired zero-contour within the volume. Since our initial mesh captures the genus of the final surface, our evolving surface is guaranteed to match the topology of the desired surface. As the system iterates, an energy function that both minimizes distance and maintains smoothness will be minimized, resulting in a surface that best matches the desired surface and has a smooth hierarchical structure. Then we successively refine the intermediate mesh, using a multi-grid type approach, and re-solve the minimization problem. The result of this process will be semi-regular mesh fitting the desired surface.

Interval Methods for Generating Triangle Meshes with Guaranteed Properties

The standard solution to extract polygonal surfaces from volume datasets, the Marching Cubes algorithm, generates meshes that have large numbers of "bad" triangles. A "bad" triangle is a triangle in which the ratio between the lengths of its edges (aspect ratio) is far from one, either too large or too small. Several improvements have been proposed, including relaxation methods, etc. These are, however, complicated and expensive to run, and do not produce guaranteed results.

We propose a new algorithm based on interval analysis that can generate meshes with guaranteed global bounds on the edge length and aspect ratio of the triangles. An interval analysis solver will be used to find vertices on the isosurface with constraints placed on the minimum distance between these vertices. This will guarantee that all edges will be between epsilon and 2\epsilon long, where ε is a user-supplied parameter. In the next step the edges of the triangles will be generated subject to minimum angle constraints. This capability will allow us to generate level-of-detail meshes by running the previous algorithm in several passes with increasingly smaller epsilons. A level-of-detail mesh is composed of a low resolution mesh (few large triangles), and several levels of detail (additional triangles, smaller with each level). Level-of-detail meshes can significantly speed up rendering in real-time applications, such as visualization and simulation.