meshextraction.dvi - 00885705.pdf

Semi-Regular Mesh Extraction from Volumes

Zo ̈

e J. Wood

Caltech

Mathieu Desbrun

USC

Peter Schr ̈

oder

Caltech

David Breen

Caltech

Abstract

We present a novel method to extract iso-surfaces from distance

volumes. It generates high quality semi-regular multiresolution

meshes of arbitrary topology. Our technique proceeds in two stages.

First, a very coarse mesh with guaranteed topology is extracted.

Subsequently an iterative multi-scale force-based solver refines the

initial mesh into a semi-regular mesh with geometrically adaptive

sampling rate and good aspect ratio triangles. The coarse mesh ex-

traction is performed using a new approach we call

surface wave-

front propagation

. A set of discrete iso-distance ribbons are rapidly

built and connected while respecting the topology of the iso-surface

implied by the data. Subsequent multi-scale refinement is driven by

a simple force-based solver designed to combine good iso-surface

fit and high quality sampling through reparameterization. In con-

trast to the Marching Cubes technique our output meshes adapt

gracefully to the iso-surface geometry, have a natural multiresolu-

tion structure and good aspect ratio triangles, as demonstrated with

a number of examples.

Keywords:

Semi-regular meshes, subdivision, volumes, surface extraction, implicit

functions, level set methods

1 Introduction

Iso-surface extraction is a fundamental technique of scientific vi-

sualization and one of the most useful tools for visualizing volume

data. The predominant algorithm for iso-surface extraction, March-

ing Cubes (MC) [36], computes a local triangulation within each

voxel of the volume containing the surface, resulting in a uniform

resolution mesh. Often much smaller meshes adequately describe

the surface since MC meshes tend to oversample the iso-surface,

encumbering downstream applications, e.g., rendering, denoising,

finite element simulations, and network transmission. These chal-

lenges can be addressed through multiresolution mesh representa-

tions.

We present a method for the

direct

extraction of an adaptively

sampled multiresolution iso-surface mesh with good aspect ratio

triangles. The multiresolution structure is based on adaptive

semi-

regular

meshes, well known from the subdivision setting [54]. A

semi-regular mesh consists of a coarsest level triangle mesh which

is recursively refined through quadrisection. The resulting meshes

have regular (valence 6) vertices almost everywhere. Adaptivity is

achieved through terminating the recursion appropriately and en-

forcing a restriction criterion (triangles sharing an edge must be

off by no more than one level of refinement). Conforming edges

are used to prevent T-vertices (see Fig. 1). Because of their spe-

cial structure such meshes enjoy many benefits including efficient

compression [25] and editing [55] (among many others). Since the

Figure 1:

Example extractions of adaptive semi-regular meshes

from volumes using our algorithm.

mesh hierarchy is represented through a forest of quad-trees, im-

plementation is simple, elegant, and efficient. Figure 1 shows an

example of a multiresolution semi-regular mesh extracted from a

distance volume with our algorithm.

1.1 Contributions

We propose an algorithm for the extraction of semi-regular meshes

directly from volume data. In a first step a coarse, irregular connec-

tivity mesh with the same global topology as the iso-surface is ex-

tracted (Fig. 2, left). This stage works for arbitrary scalar volumes

with well defined iso-surfaces and has a small memory footprint.

In a second step the mesh is refined and its geometry optimized

(Fig. 2, right). Here we require a distance volume for the desired

iso-surface. During refinement, aspect ratios and sizes of triangles

are controlled through adaptive quadrisection and

reparameteriza-

tion forces

. Since our algorithm proceeds from coarser to finer res-

olutions, simple multi-scale methods are easily used. In particular

we solve successively for the best fitting mesh at increasing resolu-

tions using an upsampling of a coarser solution as the starting guess

for the next finer level. In summary, novel aspects of our algorithm

include:

•

direct extraction of semi-regular meshes from volume data;

•

a new and fast method to extract a topologically accurate coarse

mesh with low memory requirements, suitable for large datasets;

•

an improved force-based approach to quickly converge to a re-

fined mesh that adaptively fits the data with good aspect ratio

triangles.

1.2 Related Work

Traditional Methods and Multiresolution

proceed by first

constructing an MC mesh and then improving it through simpli-

fication [20] and/or remeshing [11, 29, 33, 28, 19]. Common mesh

simplification algorithms have large memory footprints [21, 15]

and are impractical for decimating meshes with millions of sam-

ples (see [35, 34] to address this issue). In addition, simplification

algorithms create irregular connectivity meshes with non-smooth

parameterizations. These cannot be compressed as efficiently as

semi-regular meshes [25] leading to the need for remeshing. In

Figure 2:

Overview of our algorithm (left to right). Given a volume and a particular iso-value of interest a set of topologically faithful

ribbons is constructed. Stitching them gives the coarsest level mesh for the solver. Adaptive refinement constructs a better and better fit with

a semi-regular mesh.

contrast we wish to directly extract multiresolution meshes with a

smooth parameterization.

Alternatively multiresolution can be applied to the volume fol-

lowed by subsequent MC extractions [50, 2]. Unfortunately, it

is difficult to guarantee the topology of the mesh extracted from

the simplified volume, e.g., small handles will disappear at various

stages of the smoothing step, causing a change in the topology of

the extracted mesh (see [16] for a new solution). In contrast our

approach constructs a topologically accurate semi-regular mesh at

every stage of the algorithm.

Deformable Model Approaches

define the surface as the min-

imum (thin-plate) energy solution induced by a suitable potential

function [40, 23, 38, 43, 28]. The second stage of our algorithm

proceeds similarly with the important distinction that we exert spe-

cific control over the connectivity of the mesh to achieve a semi-

regular structure and we use a balloon [5] approach coupled with

a novel

reparameterization

force. Similar to previous approaches

the initial mesh for our finite element solver must have the cor-

rect topology, however almost all previous approaches rely on user

input to determine the appropriate global topology for the initial

mesh [40, 43, 28, 38]. The largest advantage of our algorithm is

our ability to extract a surface of arbitrary topology without any

input from the user. Solvers which accommodate topological mod-

ifications are possible, but rather delicate [31, 39]. Instead we opt

for a robust algorithm which

automatically

extracts a surface with

the correct global topology from the volume data

without recourse

to MC

Topological Graphs

can be constructed to encode the topology

of a surface. Our algorithm uses the adjacency relationships of the

voxels in the volume to traverse the surface and record its connec-

tivity in a graph that is topologically equivalent to the MC mesh for

the same volume. This traversal and graph construction is related to

work done by Lachaud [30] on topologically defined iso-surfaces.

However, unlike Lachaud we do not triangulate the entire graph.

Instead, our algorithm extracts a coarse mesh by eliminating redun-

dant regions of the graph where the topology does not change.

Morse Theory and Reeb Graphs

are also concerned with cod-

ing the topology of a surface [47, 45, 46]. However, neither method

uniquely identifies the embedding of the surface in space, poten-

tially leading to ambiguities in the topology coding. Work done on

surface coding and Reeb graph construction by Shinagawa, using

contours defined by a height function, resolves these ambiguities

through requiring apriori knowledge [45, 46] of the number of han-

dles. In contrast the topological graph we construct from the con-

tours of the

wavefront propagation

uniquely

determines the topol-

ogy of the surface with

apriori information (for more details and

a proof see [53]).

Distance Iso-contours

are critical in our approach. We use

ideas from level set methods on manifolds [26, 44] and discrete dis-

tance computations [32, 49]. Note that we compute these distances

on implicitly defined (through the volume) surfaces, not on meshes.

Specifically, we use the connectivity relationship of voxels in the

volume to build a graph representing the surface. Distances are

then propagated on this graph, creating a discrete distance graph.

Iso-distance contours in this graph are used to correctly encode the

topology of the surface without ever constructing an explicit mesh

as in the MC algorithm.

Signed Distance Volumes

are required by our solver, though

the initial topology discovery stage runs on any volume with well-

defined iso-contours. A signed distance volume stores the shortest

signed distance to the surface at each voxel which is useful in a

variety of applications [7, 6, 17, 42, 51]. Distance volumes are

constructed by computing the shortest Euclidean distance within

a narrow band around the desired iso-contour and then sweeping

it out to the remaining voxels using a Fast Marching Method [44].

Distance volumes can easily be generated for a variety of input data.

For example, distance volumes for MRI and CT data are computed

by fitting a level set model to the desired iso-surface, creating a

smooth segmentation of the input data [37, 52].

2 Coarse Mesh Extraction

In order to construct a topologically accurate coarse representation

of a given iso-surface we slice the surface along contours that cap-

ture the overall topology. This concept is similar to representing a

surface with a Reeb graph, which uses contours defined by a height

function. The latter leads to ambiguities which we avoid by using

contours of a distance function defined

the iso-surface. Exam-

ining the way these geometric contours are connected, we can al-

ways uniquely encode a topological graph of the iso-surface. This

is achieved by discarding topologically redundant cross-sections,

i.e., those where surface topology can not change.

Background

Before we explain the details of this approach,

recall some important theorems and definitions from Geometric

Topology [41]. First, the topology of a 2-manifold

(closed poly-

hedral surface) is completely determined by its genus:

(

−

=2(1

−

)

where

is the Euler characteristic,

the number of vertices,

the

number of edges,

the number of faces and

the genus. We use

this fact and two related theorems:

•

the Euler characteristic of an entire polyhedron can be decom-

posed into the sum of the Euler characteristics of smaller regions

whose disjoint union is the polyhedron;

•

the Euler characteristic of any given 2-manifold, or subset of a

2-manifold is invariant,

regardless of how the surface is trian-

gulated

Given these facts, it is easy to see that topology can be captured

accurately by selecting contours where the Euler characteristic of

the associated region will change the genus of the surface. This

selection is based on decomposing the surface into a combination

of a few simple primitives:

1-sphere:

A 1-sphere

is a set homeomorphic to a unit circle with

(

)=0

2-cell:

A 2-cell

is a set homeomorphic to a disk with

(

)=1

For example, we can decompose a sphere into two 1-spheres (con-

tours), two 2-cells (disks), and the triangulation between the two

contours (which we call a

ribbon

) that respects the orientation of

the original surface (see Fig. 3). Consider the combined Euler char-

acteristic of these regions. As stated in the definitions, the Euler