Books and Surveys
|
|
Delaunay
mesh generation of three dimensional domains.
T. K. Dey. Technical Report OSU-CISRC-9/07-TR64,
October, 2007.
Delaunay meshes are used in various applications such as finite
element analysis, computer graphics rendering, geometric modeling,
and shape analysis. As the applications vary, so do the domains to
be meshed. Although meshing of geometric domains with Delaunay simplices
have been around for a while, provable techniques to meshing various
types of three dimenisonal domains have been developed only recently.
We devote this article to presenting these techniques. We survey various
related results and detail a few core algorithms that have provable guarantees
and are amenable to practical implementation. Delaunay refinement, a
paradigm originally developed for guaranteeing shape quality of mesh elements,
is a common thread in these algorithms. We finish the article by listing
a set of open questions.
|
|
|
Sample
based geometric modeling
T. K. Dey.
Chapter in Geometric and Algorithmic Aspects
of Computer-Aided Design and Manufacturing, eds Janardan, Smid,
Dutta. DIMACS series in Discrete Mathematics and Theoretical
Computer Science, Volume 67, 2005.
A new paradigm
for digital modeling of physical objects from sample
points is fast emerging due to recent advances in scanning
technology. Researchers are investigating many of
the traditional modeling problems in this new setting. We
name this new area as sample based geometric modeling.
The purpose of this article is to expose
the readers to this new modeling paradigm through three basic
problems, namely surface reconstruction, medial axis approximation,
and shape segmentation. The algorithms for these three problems
developed by the author and his co-authors are described.
|
|
|
Curve
and surface reconstruction
T. K. Dey.
Chapter in Handbook of Discrete and Computational
Geometry, Goodman and O' Rourke eds., CRC press, 2nd
edition (2004)
The problem
of reconstructing a shape from its sample appears in
many scientific and engineering applications. Because
of the variety in shapes and applications, many algorithms
have been proposed over the last two decades, some
of which exploit application-specific information and
some of which are more general. We will concentrate on
techniques that apply to the general setting and have proved
to provide some guarantees on the quality of reconstruction.
|
|
|
Papers
|
Computing
Geometry-aware Handle and Tunnel Loops in 3D Models.
T. K. Dey, K. Li, J. Sun, and D. Cohen-Steiner. SIGGRAPH 2008, to appear.
[Video][Software][Talk-slide][Web-page]
Many applications such
as topology repair, model editing, surface parameterization, and feature recognition
benefit from computing loops on surfaces that wrap around their `handles'
and `tunnels'. Computing such loops while optimizing their geometric lengths
is difficult. On the other hand, computing such loops without considering
geometry is easy but may not be very useful. In this paper we strike a balance
by computing topologically correct loops that are also geometrically relevant.
Our algorithm is a novel application of the concepts from topological persistence
introduced recently in computational topology. The usability of the computed
loops is demonstrated with some examples in feature identification and topology
simplification. |
|
|
Recursive
geometry of the flow complex and topology of the flow
complex filtration.
K. Buchin, T. K. Dey, J. Giesen, and M. John. Comput.
Geom. Theory Application. (2008),
vol. 40, 115--157.
The flow complex is a
geometric structure, similar to the Delaunay tessellation, to organize a
set of (weighted) points in R^k. Flow shapes are topological spaces correspoding
to substructures of the flow complex. The flow complex and flow shapes have
found applications in surface reconstruction, shape matching, and molecular
modeling. In this article we give an algorithm for computing the flow complex
of weighted points in any dimension. The algorithm reflects the recursive
structure of the flow complex. On the basis of the algorithm we establish
a topological similarity between flow shapes and the nerve of a corresponding
ball set, namely homotopy equivalence.
|
|
|
Normal
variation with adaptive feature size (2008)
The proof of the normal
variation lemma (Lemma 2) in Amenta-Bern paper ``Surface reconstruction
by Voronoi filtering", DCG, 1999, pg. 481-504, is not correct (which also
appears in my book on reconstruction). In this short note we fix the problem
and improve the bound on the normal variation. This should improve various
bounds derived afterwards using the normal variation result.
|
|
|
Maintaining
Deforming Surface Meshes
S.-W. Cheng and T. K. Dey. Proc. 19th ACM-SIAM
Sympos. Discrete Algorithms (SODA08) (2008), 112--121.
We present a method to maintain a mesh approximating
a deforming surface, which is specified by a dense set of sample points.
We identify a reasonable motion model for which a provably good surface
mesh can be maintained. Our algorithm determines the appropriate times
at which the mesh is updated to maintain a good approximation. The updates
use simple primitives, and no costly computation such as line-surface
intersection is necessary. Point insertions and deletions are allowed
at the updates. Each update takes time linear in the size of the current
sample set plus the new sample points inserted. We also construct examples
for which, under the same model, no other algorithm makes asymptotically
fewer changes to the mesh than our algorithm.
This paper is based on the following flip paper available
as a preprint from computational geoemtry arxiv.
|
|
|
Delaunay
Edge Flips in Dense Surface Triangulations
S.-W. Cheng and T. K. Dey. Pre-print arXiv:cs.CG/0712.1959,
2007. short version in EuroCG 2008.
Delaunay
flip is an elegant, simple tool to convert a triangulation of a point
set to its Delaunay triangulation. The technique has been researched extensively
for full dimensional triangulations of point sets. However, an important
case of triangulations which are not full dimensional is surface triangulations
in three dimensions. In this paper we address the question of converting
a surface triangulation to a subcomplex of the Delaunay triangulation
with edge flips. We show that the surface triangulations which closely
approximate a smooth surface with uniform density can be transformed to
a Delaunay triangulation with a simple edge flip algorithm. The condition
on uniformity becomes less stringent with increasing density of the triangulation.
If the condition is dropped completely, the flip algorithm still terminates
although the output surface triangulation becomes ``almost Delaunay" instead
of exactly Delaunay.
|
|
|
A practical Delaunay meshing algorithm for a large class of domains
S.-W. Cheng, T. K. Dey, and J. A. Levine.
Proc. 16th Internat. Meshing Roundtable (2007), 477--494.
[Talk
slides] DelPSC software.
Recently
a Delaunay refinement algorithm has been proposed that can mesh domains
as general as piecewise smooth complexes [CDR07]. In this paper we introduce
a novel modification of the algorithm to make it implementable
in practice. In particular, we replace four tests of the original algorithm
with only a single test that is easy to implement. The algorithm has
the following guarantees. The output mesh restricted to each manifold
element in the complex is a manifold with proper incidence relations.
More importantly, with increasing level of refinement which can be controlled
by an input parameter, the output mesh becomes homeomorphic to the input
while preserving all input features. Implementation results on a disparate
array of input domains are presented to corroborate our claims.
|
|
|
On
computing handle and tunnel loops
T. K. Dey, K. Li, and J. Sun.
IEEE Proc. Internat. Conf. Cyberworlds (NASAGEM workshop) (2007),
357--366. Tech Report OSU-CISRC-06/07-TR48, June 2007.
[Talk
slides] HandleTunnel
software
Many applications seek to identify features
like `handles' and `tunnels' in a shape bordered by a surface embedded
in three dimensions. To this end we define handle and tunnel loops
on surfaces which can help identifying these features. We show that
a closed surface of genus g always has g handle and g tunnel loops induced
by the embedding. For a class of shapes that retract to graphs, we characterize
these loops by a linking condition with these graphs. These characterizations
lead to algorithms for detection and generation of these loops. We
provide an impementation with applications to feature detection and
topology simplification to show the effectiveness of the method.
|
|
|
Stability of critical points with interval persistence
T. K. Dey and R. Wenger. Discrete
& Computational Geometry, vol 38 (2007), 479--512. Tech Report
OSU-CISRC-4/06-TR47, April 2006.
Scalar functions defined on a topological
space T are at the core of many applications such as shape matching,
visualization, and physical simulations. Topological persistence
is an approach to characterizing these functions. It measures
how long topological structures in the level sets {x in T : f(x)
<= c} persist as c changes. Recently it was shown that the critical
values defining a topological structure with relatively large persistence
remain almost unaffected by small perturbations. This result suggests
that topological persistence is a good measure for matching and comparing
scalar functions. We extend these results to critical points
in the domain by redefining persistence and critical points and replacing
sub-level sets {x in T : f(x) <= c} with interval sets {x
in T : a<=f(x)< b}. With these modifications we establish a stability
result for critical points. This result is strengthened for maxima
that can be used for matching two scalar functions.
|
|
|
Delaunay meshing of isosurfaces
T. K. Dey and J. A. Levine. Proc.
Shape Modeling International (2007), 241--250.
DelIso software
We present an isosurface meshing algorithm DelIso, based on the
Delaunay refinement paradigm. This paradigm has been successfully
applied to mesh a variety of domains with guarantees for topology, geometry,
mesh gradedness, and triangle shape. A restricted Delaunay triangulation,
dual of the intersection between the surface and the three dimensional
Voronoi diagram, is often the main ingredient in Delaunay refinement. Computing
and storing three dimensional Voronoi/Delaunay diagrams become bottlenecks
for Delaunay refinement techniques since isosurface computations generally
have large input datasets and output meshes. A highlight of our algorithm
is that we find a simple way to recover the restricted Delaunay triangulation
of the surface without computing the full 3D structure. We employ techniques
for efficient ray tracing of isosurfaces to generate surface sample points,
and demonstrate the effectiveness of our implementation on a variety of
volume datasets. |
|
|
Delaunay refinement for piecewise smooth complexes
S.-W. Cheng, T. K. Dey, and E. A. Ramos.
Proc. 18th Annu. ACM-SIAM Sympos. Discrete Algorithms
(2007), 1096--1105.
Extended
Full Version
We present a Delaunay refinement algorithm for meshing
a piecewise smooth complex in three dimensions with correct topology.
The small angles between the tangents of two meeting manifold patches
pose difficulty. We protect these regions with weighted points. The
weights are chosen to mimic the local feature size and to satisfy a
Lipschitz-like property. A Delaunay refinement using the weighted Voronoi
diagram is shown to terminate with the recovery of the topology of the
input. To this end, we present new concepts and results including a
new definition of local feature size and a proof for a generalized topological
ball property.
|
|
|
Defining
and computing curve-skeletons with medial geodesic function
T. K. Dey and J. Sun. Proc. Sympos.
Geometry Processing (2006), 143--152.
CurveSkel Software
Many applications in geometric modeling, computer
graphics, visualization, and computer vision benefit from a
reduced representation called curve-skeletons of a shape. These
are curves possibly with branches which compactly represent the
shape geometry and topology. The lack of a proper mathematical definition
has been a bottleneck in developing and applying the curve-skeletons.
A set of desirable properties of these skeletons has been identified
and the existing algorithms try to satisfy these properties mainly
through a procedural definition. We define a function called medial
geodesic on the medial axis which leads to a mathematical definition
and an approximation algorithm for curve-skeletons. Empirical study
shows that the algorithm is robust against noise, operates well with
a single user parameter, and produces curve-skeletons with the desirable
properties. Moreover, the curve-skeletons can be associated with additional
attributes that follow naturally from the definition. These attributes
capture shape eccentricity, a local measure of how far a shape is away
from a tubular one.
|
|
|
Identifying
flat and tubular regions of a shape by unstable manifolds
S. Goswami, T. K. Dey, and C. Bajaj.
Proc. 11th ACM Sympos. Solid Modeling Applications
(2006), 27--37.
We present
an algorithm to identify the flat and tubular regions of a three
dimensional shape from its point sample. We consider the distance
function to the input point cloud and the Morse structure induced
by it on R^3. Specifically we focus on the index 1 and index 2 saddle
points and their unstable manifolds. The unstable manifolds of index
2 saddles are one dimensional whereas those of index 1 saddles are two
dimensional. Mapping these unstable manifolds back onto the surface,
we get the tubular and flat regions. The computations are carried out
on the Voronoi diagram of the input points by approximating the unstable
manifolds with Voronoi faces. We demonstrate the performance of our
algorithm on several point sampled objects. |
|
|
Normal
and feature approximations from noisy point clouds.
T. K. Dey and
J. Sun. Proc. FST&TCS 2006, LNCS 4337, 21--32.
NormFet
software
We consider the problem of approximating
normal and feature sizes approximations of a surface from
point cloud data that may be noisy. These problems are central
to many applications dealing with point cloud data. In the noise-free
case, the normals and feature sizes can be approximated by the
centers of a set of unique large Delaunay balls called polar balls.
In presence of noise, polar balls do not necessarily remain large
and hence their centers may not be good for normal and feature approximations.
Earlier works suggest that some large Delaunay balls can play the
role of polar balls. However, these results were short in explaining
how the big Delaunay balls should be chosen for reliable approximations
and how the approximation error depends on various factors. We provide
new analyses that fill these gaps. In particular, they lead to new
algorithms for practical and reliable normal and feature approximations.
|
|
|
Anisotropic
surface meshing
S.-W. Cheng, T. K. Dey and E. A. Ramos.
Proc. ACM-SIAM Sympos. Discrete Algorithms
(2006), 202--211.
We study the
problem of triangulating a smooth closed implicit surface
S endowed with a 2D metric tensor that varies over S. This is
commonly known as the anisotropic surface meshing problem. We
extend the 2D metric tensor naturally to 3D and employ the 3D anisotropic
Voronoi diagram of a set P of samples on S to triangulate S. We
prove that a restricted dual, Mesh P, is a valid triangulation
homeomorphic to S under appropriate conditions. We also develop
an algorithm for constructing P and Mesh P. In addition to
being homeomorphic to S, each triangle in Mesh P is well-shaped when
measured using the 3D metric tensors of its vertices. Users can set
upper bounds on the anisotropic edge lengths and the angles between the
surface normals at vertices and the normals of incident triangles (measured
both isotropically and anisotropically). |
|
|
An Adaptive MLS Surface for Reconstruction
with Guarantees.
T. K. Dey and
J. Sun. Symposium on Geometry Processing
2005, 43--52.
Conference
version.
Extended
version.
Technical Report
OSU-CISRC-4-05-TR26, April, 2005.
AMLS Software
Recent work
have shown that moving least squares (MLS) surfaces
can be used effectively to reconstruct surfaces from possibly
noisy point cloud data. Several variants of MLS surfaces
have been suggested, some of which have been analyzed theoretically
for guarantees. These analyses, so far, have assumed uniform
sampling density. We propose a new variant of the MLS surface that,
for the first time, incorporates local feature sizes in its formulation,
and we analyze it for reconstruction guarantees using a non-uniform
sampling density. The proposed variant of the MLS surface has
several computational advantages over existing MLS methods.
Also see
Extremal
Surface Based Projections Converge and Reconstruct
with Isotopy.
T. K. Dey, S. Goswami
and J. Sun. Technical Report OSU-CISRC-05-TR25,
April, 2005.
An early attempt
T. K. Dey, S. Goswami and J. Sun.
Smoothing
noisy point clouds with Delaunay preprocessing
and MLS. Tech-report OSU-CISRC-3/04-TR17, 2004.
|
|
|
Normal
Estimation for Point Clouds : A Comparison
Study for a Voronoi Based Method
T. K. Dey,
G. Li and J. Sun. Eurographics Sympos. on
Point-Based Graphics (2005), 39--46.
Many applications that
process a point cloud data benefit from a reliable
normal estimation step. Given a point cloud presumably sampled
from an unknown surface, the problem is to estimate the normals
of the surface at the data points. Two approaches, one
based on numerical optimizations and another based on Voronoi
diagrams are known for the problem. Variations of numerical
approaches work well even when point clouds are contaminated
with noise. Recently a variation of the Voronoi based method is proposed
for noisy point clouds. The centrality of the normal estimation
step in point cloud processing begs a thorough study of the two
approaches so that one knows which approach is appropriate for what
circumstances. This paper presents such results.
|
|
|
Polygonal Surface
Remeshing with Delaunay Refinement
T. K. Dey,
G. Li and T. Ray. Proc.14th Internat. Meshing
Roundtable, 2005, 343--361.
Conference
version
Extended
version
SurfRemesh
software
Polygonal meshes are used
to model smooth surfaces in many applications. Often
these meshes need to be remeshed for improving the quality,
density or gradedness. We apply the Delaunay refinement
paradigm to design a provable algorithm for isotropic remeshing
of a polygonal mesh that approximates a smooth surface. The
proofs provide new insights and our experimental results corroborate
the theory.
|
|
|
Weighted
Delaunay Refinement for Polyhedra with Small Angles
S.-W. Cheng,
T. K. Dey and T. Ray. Proc.14th Internat.
Meshing Roundtable 2005, 325--342.
Recently, a provable Delaunay
meshing algorithm called QMesh has been proposed for
polyhedra that may have acute input angles. The algorithm guarantees
bounded circumradius to shortest edge length ratio for all
tetrahedra except the ones near small input angles. This guarantee
eliminates or limits the occurrences of all types of poorly
shaped tetrahedra except slivers. A separate technique called
weight pumping is known for sliver elimination. But, allowable
input for the technique so far have been periodic point sets
and piecewise linear complex with non-acute input angles. In this
paper, we incorporate the weight pumping method into QMesh thereby
ensuring that all tetrahedra except the ones near small input angles
have bounded aspect ratio. Theoretically, the algorithm has an
abysmally small angle guarantee inherited from the weight pumping
method. Nevertheless, our experiments show that it produces better
angles in practice.
|
|
|
Critical points of distance
to an epsilon-sampling of a surface and flow-complex- based surface
reconstruction.
T. K. Dey,
J. Giesen, E. A. Ramos and B. Sadri. Proc.
21st Annu. Sympos. Comput. Geom., (2005), 218--227.
( Invited Journal version in Internat. J. Comput. Geom. Applications,
Vol 18, 2008, 29--61.)
Extended
version.
The distance
function to surfaces in three dimensions plays a key
role in many geometric modeling applications such as medial
axis approximations, surface reconstructions, offset computations,
feature extractions and others. In most of these cases,
the distance function to the surface is approximated by a discrete
distance function where the distances are measured from a discrete
sample of the surface. The critical points of the distance function
determines the topology of the geometric structures in question.
Howvere, no theoretical result exists linking the sampling and
the critical point structures of the distance functions. We provide
this link by showing that the critical points of the discrete distance
function either lie very close to the surface or near the medial
axis both quantified with the sampling density. One implication
of this result is that known Morse theory based surface reconstruction
algorithms do indeed approximate the surface geometrically.
|
|
|
Manifold Reconstruction
from Point Samples
Siu-Wing Cheng,
T. K. Dey and E. A. Ramos. Proc. ACM-SIAM
Sympos. Discrete Algorithms, 2005, 1018--1027.
Extended
AbstractSee also [Talk
slides]
We present
an algorithm to "reconstruct" a smooth k-dimensional
manifold M embedded in an Euclidean space R^d from
a "sufficiently dense" point sample from the manifold.
The algorithm outputs a simplicial manifold that is homeomorphic
and geometrically close to M. The running time is O(nlogn)
where n is the number of points in the sample (the multiplicative
constant depends exponentially on the dimension though).
|
|
|
Delaunay
Triangulations Approximate Anchor Hulls
T. K. Dey,
Joachim Giesen and Samrat Goswami. Comput. Geom. Theory Applications,
vol. 36 (2006), 131--143. (prelim. version in SODA 2005, 1028-1037).
Recent results
establish that a subset of the Voronoi diagram of
a point set that is sampled from a smooth boundary of
a shape approximates the medial axis. The corresponding question
for the dual Delaunay triangulation is not addressed
in the literature. We show that, for two dimensional
shapes, the Delaunay triangulation approximates a specific
structure which we call anchor hulls.
As an application we demonstrate that our approximating result
is useful for the problem of shape matching.
|
|
|
Quality meshing
for polyhedra with small angles
S.-W. Cheng,
T. K. Dey, E. Ramos and T. Ray. International J. Comput.
Geom. & Applications, Vol. 15, No. 4 (2005), 421--461.
Extended
version
QualMesh
Software
We present
an algorithm to compute a Delaunay mesh conforming
to a polyhedron possibly with small input angles. The
radius-edge ratio of most output tetrahedra are bounded
by a constant, except possibly those that are provably
close to small angles. Further, the mesh is graded, that is,
edge lengths are at least a constant fraction of the local
feature sizes at the edge endpoints. Unlike a previous algorithm,
this algorithm is simple to implement as it avoids computing
local feature sizes and protective zones explicitly. Our experimental
results confirm our claims and show that few skinny tetrahedra
remain.
|
|
|
Sampling and
meshing a surface with guaranteed topology and geometry
S.-W. Cheng,
T. K. Dey, E. Ramos and T. Ray.Proc. 20th Sympos.
Comput. Geom. (2004), 280--289 .
Extended
version, in SIAM Journal Computing,
Vol. 37 (2007), 1199--1227.
This paper
presents an algorithm for sampling and triangulating
a smooth surface in R3 where the triangulation
is homeomorphic to the surface. The only assumption
we make is that the input surface representation
is amenable to certain types of computations, namely computations
of the intersection points of a line with the surface, computations
of the critical points of some height functions defined
on the surface and its restriction to a plane, and computations
of some silhouette points. The algorithm ensures bounded aspect
ratio, size optimality, and smoothness of the output triangulation.
Unlike previous algorithms, this algorithm does not need
to compute the local feature size for generating the sample points
which was a major bottleneck. Experiments show the usefulness
of the algorithm in remeshing and meshing CAD surfaces that are piecewise
smooth. |
|
|
Provable
surface reconstruction from noisy samples
T. K. Dey and
S. Goswami. Computationa
Geometry Theory & Applications, vol. 35, 2006, 124--141.
RobustCocone
software
We
present an algorithm for surface reconstruction in
presence of noise. We show that, under a reasonable noise
model, the algorithm has theoretical guarantees. Actual performance
of the algorithm is illustrated by our experimental results.
|
|
|
Approximating
the Medial Axis from the Voronoi Diagram with
a Convergence Guarantee
T. K. Dey and
W. Zhao. Algorithmica, vol. 38, 2003, 179--200.
Medial Software
The medial axis of a
surface in 3D is the closure of all points that have
two or more closest points on the surface. It is an essential
geometric structure in a number of applications involving
3D geometric shapes. Since exact computation of the
medial axis is difficult in general, efforts continue to improve
their approximations. Voronoi diagrams turn out to be useful
for this approximation. Although it is known that Voronoi
vertices for a sample of points from a curve in 2D approximate
its medial axis, similar result does not hold in 3D. Recently,
it has been discovered that only a subset of Voronoi vertices
converge to the medial axis as sample density approaches infinity.
However, most applications need a non-discrete approximation
as opposed to a discrete one. To date no known algorithm
can compute this approximation straight from the Voronoi
diagram with a guarantee of convergence.We present such an
algorithm and its convergence analysis in this paper. One salient
feature of the algorithm is that it is scale and density independent.
Experimental results corroborate our theoretical claims.
|
|
|
Hierarchy
of surface models and irreducible triangulation
S.-W. Cheng,
T. K. Dey and S.-H. Poon.Computational Geometry
: Theory & Applications, Vol. 27, No. 2 (2004), 135--150
Given a triangulated
closed surface, the problem of constructing a hierarchy
of surface models of decreasing level of detail has attracted
much attention in computer graphics. A hierarchy provides
a view-dependent refinement and facilitates the computation
of parameterization. For a triangulated closed surface of
n vertices and genus g, we prove that there is a constant c>0
such that if n > c g, a greedy strategy can identify \Theta(n)
topology-preserving edge contractions that do not interfere with
each other. Further, each of them affects only a constant number
of triangles. Repeatedly identifying and contracting such edges
produces a topology-preserving hierarchy of O(n+g^2) size and O(logn
+g) depth. Although several implementations exist for constructing
hierarchies, our work is the first to show that a greedy algorithm
can efficiently compute a hierarchy of provably small size and
low depth. When no contractible edge exists, the triangulation
is irreducible. Nakamoto and Ota showed that any irreducible triangulation
of an orientable 2-manifold has at most max{342g-72, 4} vertices.
Uisng our proof techniques we obtain a new bound of mx{240g,4}.
|
|
|
Shape segmentation
and matching with flow discretization
T. K. Dey,
J. Giesen and S. Goswami. Proc. Workshop Algorithms
Data Strucutres (WADS 03), LNCS 2748, F. De | |
