Books and Surveys
|
|
Delaunay
mesh generation of three dimensional domains.
T. K. Dey. Technical Report
OSU-CISRC-9/07-TR64, October, 2007. To appear in
Tessellations in the sciences: Virtues, Techniques and Applications of Geometric
Tilings, eds. R. van de Weygaert, G. Vegter, J. Ritzerveld & V. Icke,
Springer-Verlag, 2009.
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
|
Isotopic
Reconstruction of Surfaces with Boundaries
T. K. Dey, K. Li., E. A. Ramos, and R. Wenger. Proc.
Sympos. Geom. Processing.(SGP09), 2009, to appear.
We present an algorithm for the reconstruction
of a surface with boundaries (including a non-orientable one) in three dimensions
from a sufficiently dense sample. It is guaranteed that the output is isotopic
to the unknown sampled surface. No previously known algorithm guarantees
isotopic or homeomorphic reconstruction of surfaces with boundaries. Our
algorihtm is surprisingly simple. It `peels' slivers greedily from an alpha-complex
of a sample of the surface. No other post-processing is necessary. We provide
several experimental results from an implementation of our basic algorithm
and also a modified version of it.
|
|
|
Cut
Locus and Topology from Surface Point Data.
T. K. Dey, K. Li. Proc. 25th Ann. Sympos. Comput. Geom.(SoCG09),
2009, 125--134.
A cut locus of a point in a compact Riemannian
manifold M is defined as the set of points where minimizing geodesics issued
from p stop being minimizing. It is known that a cut locus contains most
of the topological information of M. Our goal is to utilize this property
of cut loci to decipher the topology of M from a point sample. Recently it
has been shown that Rips complexes can be built from a point sample
P of M systematically to compute the Betti numbers, the rank of the homology
groups of M. Rips complexes can be computed easily and therefore are favored
over others such as restricted Delaunay, alpha, Cech, and witness complex.
However, the sizes of the Rips complexes tend to be large. Since the dimension
of a cut locus is lower than that of the manifold M, a subsample of P approximating
the cut locus is usually much smaller in size and hence admits a relatively
smaller Rips complex.
In this paper we explore the above approach for point data sampled from
surfaces embedded in any high dimensional Euclidean space. We present an
algorithm that computes a subsample P' of a sample P of a 2-manifold where
P' approximates a cut locus. Empirical results show that the first Betti
number of M can be computed from Rips complexes built on these subsamples.
The sizes of these Rips complexes are much smaller than the one built on
the original sample of M.
Our first attempt on a related topic was the following paper:
Topology
from Data via Geodesic Complexes. T. K. Dey and K. Li. Tech Report
OSU-CISRC-3/09-TR05.
|
|
|
Delaunay
meshing of piecewise smooth complexes without expensive predicates.
T. K. Dey, J. A. Levine. Tech Report, OSU-CISRC-7/08-TR40, July
2008.
[Video][Software][Talk-slide][Web-page]
Recently a Delaunay
refinement algorithm has been proposed that can mesh piecewise smooth
complexes which include polyhedra, smooth and piecewise smooth surfaces,
and non-manifolds. However, this algorihtm employs domain dependent numerical
predicates, some of which could be computationally expensive and hard
to implement. In this paper we develop a refinement strategy that eliminates
these complicated domain dependent predicates. As a result we obtain a
meshing algorithm that is practical and implementation-friendly.
|
|
|
Persistence-based
Handle and Tunnel Loops Computation Revisited for Speed Up.
T. K. Dey and K. Li. Shape Modeling International (SMI09), 2009.
Special issue of Computer & Graphics, Article in press,
doi:10.1016/j.cag.2009.03.008.
[Software]
Loops in surfaces
associated with topological features such as handles and tunnels are important
entities in many applications including surface parameterization, feature
identification, and topological simplification. Recently, a persistent homology
based algorithm has been proposed to compute them. The algorithm has several
advantages including its simplicity, combinatorial nature and independence
from computing other extra structures. In this paper, we propose changes
to this loop computation algorithm based on some novel observations. These
changes reduce the computation time of the algorithm dramatically. In particular,
our experimental results show that the suggested changes achieve considerable
speed up for large data sets without sacrificing loop qualities.
Note: This is a follow-up paper of our
SIGGRAPH08 paper below.
|
|
|
Computing
Geometry-aware Handle and Tunnel Loops in 3D Models.
T. K. Dey, K. Li, J. Sun, and D. Cohen-Steiner. SIGGRAPH 2008,
45:1--45:9.
[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.
Note: See the paper below On
computing handle and tunnel loops for our first attempt on this
problem.
|
|
|
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 (2007)
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.
Note: We are temporarily retracting this result due to a bug in a Lemma
(Lemma 3.1). We are trying to salvage the other results without using Lemma
3.1. The abstract was:
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]
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.
For the theory see the following paper:
Theory
of a practical Delaunay meshing algorithm for a large class of domains.
S.-W. Cheng, T. K. Dey and J. Levine. Algorithms, Architecture and Information
Systems Security, B. Bhattacharya, S. Sur-Kolay, S. Nandy and A. Bagchi
(eds.), World Scientific Review Volume 3, 2008, 17--41.
|
|
|
On
computing handle and tunnel loops
T. K. Dey, K. Li, and
J. Sun. IEEE Proc. Internat. Conf. Cyberworlds (NASAGEM workshop)
(2007), 357--366. Journal version is in Computer-Aided Design, in press,
doi:10.1016/j.cad.2009.01.001.
[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. Journal Version in Discrete
& Comput. Geom., 2008, article in press. doi.10.1007/s00454-008-9109-3.
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.
Dehne, J.-R. Sack, M. Smid Eds., 25--36
Extended
version
Segmatch
Software
Geometric shapes
are identified with their features. For computational
purposes a concrete mathematical definition of
features is required. In this paper we use a topological
approach, namely dynamical systems, to define
features of shapes. To exploit this definition algorithmically
we assume that a point sample of the shape is given
as input from which features of the shape have to be approximated.
We translate our definition of features to the discrete
domain while mimicking the set-up developed for the
continuous shapes. The outcome of this approach is a clean
mathematical definition of features that are efficiently
computable with combinatorial algorithms. Experimental
results show that our algorithms segment shapes in two
and three dimensions into so-called features quite effectively.
Further, we develop a shape matching algorithm that
takes advantage of our robust feature segmentation step.
Performance of this algorithm is exhibited with experimental
results.
Also
see the following paper:
Shape
segmentation and matching from noisy point
clouds
T.
K. Dey, J. Giesen and S. Goswami. Proc. Eurographics
Sympos. Point-Based Graphics (2004), Marc Alexa and
S. Rusinkiewicz (eds) (2004), 193--199.
|
|
|
Quality
meshing with weighted Delaunay refinement
S.-W.
Cheng and T. K. Dey.SIAM J. Computing, Vol. 33
(2003), 69--93
Delaunay
meshes with bounded circumradius to shorten edge
length ratio have been propsed in the past for quality
meshing. The only poor quality tetrahedra called
slivers that can occur in such
a mesh can be eliminated by the sliver exudation
method. This method has been shown to work for periodic
point sets, but not with boundaries. Recently a randomized
point-placement strategy has been proposed to remove slivers
while conforming to a given boundary. In this paper we present
a deterministic algorithm for generating a weighted Delaunay
mesh which respects the input boundary and has no poor quality
tetrahedron including slivers. As in previous work, we assume
that no input angle is acute. This success is achieved by combining
the weight pumping method for sliver exudation and the Delaunay
refinement method for boundary conformation. |
|
|
Shape
dimension and approximation from samples
T.
K. Dey, J. Giesen, S. Goswami and W. Zhao.
Discrete & Comput. Geom., vol 29, 419--434
(2003)
There
are many scientific and engineering applications
where an automatic detection of shape dimension from
sample data is necessary. Topological dimensions of
shapes constitute an important global feature of them.
We present a Voronoi based dimension detection algorithm
that assigns a dimension to a sample point which is the
topological dimension of the manifold it belongs to. Based
on this dimension detection, we also present an algorithm
to approximate shapes of arbitrary dimension from their
samples. Our empirical results with data sets in three dimensions
support our theory. |
|
|
A
simple algorithm for homeomorphic surface
reconstruction
N.
Amenta, S. Choi, T. K. Dey and N. Leekha.
Intl. Journal on Computational Geometry &
Applications, vol. 12, (2002), 125--141
The
problem of computing a piecewise linear approximation
to a surface from a set of sample points is improtant
in solid modeling, computer graphics and computer
vision. A recent algorithm using the Voronoi diagram of
the sample points gave a guarantee on the distance of the
output surface from the original sampled surface assuming that
the sample was sufficiently dense. We give a similar algorithm,
simplifying the computation and the proof of the geometric
guarantee. In addition, we guarantee that our output surface
is homeomorphic to the original surface; to our knowledge this is
the first such topological guarantee for this problem.
Also
see the following paper:
Tight
Cocone : A water-tight surface reconstructor
T. K. Dey and S. Goswami. J.
Computing Inform. Sci. Engin., vol. 30, (2003), 302--307.
Cocone Software
|
|
|
Dynamic
skin triangulation
H-L.
Cheng, T. K. Dey, H. Edelsbrunner and J. Sullivan.
Discrete Comput. Geom., vol. 25, (2001),
525--568
This
paper describes an algorithm for maintaining an
approximating triangulation of a deforming surface
in R 3 . The surface is the envelope of an infinite
family of spheres defined and controlled by a finite
collection of weighted points. The triangulation adapts
dynamically to changing shape, curvature, and topology of
the surface. |
|
|
Sliver
exudation
S.-W.
Cheng, T. K. Dey, H. Edelsbrunner, M. A. Facello and
S.-H. Teng.J. ACM, Vol. 47, (2000), 883--904
A
sliver is a tetrahedron whose four vertices lie close
to a plane and whose orthogonal projection to that
plane is a convex quadrilateral with no short
edge. Slivers are notoriously common in 3-dimensional
Delaunay triangulations even for well-spaced point
sets. We show that if the Delaunay triangulation has the
ratio property then there is an assignment of weights
so the weighted Delaunay triangulation contains no
slivers. We also give an algorithm to compute such a weight
assignment. |
|
|
A
simple provable algorithm for curve reconstruction
T.
K. Dey and P. Kumar.Proc. 10th. ACM-SIAM Symposium
on Discrete Algorithms (SODA '99) , 1999, 893--894
We
present an algorithm that provably reconstructs a
curve in the framework introduced by Amenta, Bern
and Eppstein. The highlights of the algorithm are:
(i) it is simple, (ii) it requires a sampling density
better than previously known, (iii) it can be adapted
for curve reconstruction in higher dimensions straightforwardly.
|
|
|
Topology
preserving edge contraction
T.
K. Dey, H. Edelsbrunner, S. Guha and D. Nekhayev.Publications
de l' Institut Mathematique (Beograd), Vol. 60
(80), 23--45, 1999
We
study edge contractions in simplicial complexes and
local conditions under which they preserve the
topological type. The conditions are based on a generalized
notion of boundary, which lends itself to defining a
nested hierarchy of triangulable spaces measuring the
distance to being a manifold. |
|
|
Transforming curves on surfaces
T.
K. Dey and S. Guha.Journal of Computer and System
Sciences, vol. 58, 1999, 297--325. Preliminary version
in IEEE FOCS , 1995, 266-274
We
describe an optimal algorithm to decide if one closed
curve on a triangulated 2-manifold can be continuously
transformed to another, i.e., if they are homotopic.
Suppose C_1 and C_2 are two closed curves on a surface
M of genus g. Further, suppose T is a triangulation of
M of size n such that C_1 and C_2 are represented as edge-vertex
sequences of lengths k_1 and k_2 in T, respectively. Then,
our algorithm decides if C_1 and C_2 are homotopic in O(n+k_1+k_2)
time and space, provided g \not = 2 if M is orientable, and g
\not 3, 4 if M is non-orientable. This as well implies an optimal
algorithm to decide if a closed curve on a surface can be
continuously contracted to a point. Except for the three low
genus cases, our algorithm completes an investigation into the
computational complexity of two classical problems for surfaces
posed by the mathematician Max Dehn at the beginning of this
century. The novelty of our approach is in the application
of methods from modern combinatorial group theory.
Reprint
available upon request |
|
|
Improved
bounds for planar k-sets and related problems
T.
K. Dey.Invited paper in a special issue of Discrete
& Computational Geometry, Vol. 19, No. 3, (1998),
373-382
We
prove an O(nk1/3) upper bound for planar
k-sets. This is the first considerable improvement
on this bound after its early solutions approximately
twenty seven years ago. Our proof technique also
applies to improve the current bounds on the combinatorial
complexities of k-levels in arrangements of line segments,
k convex polygons in the union of n lines, parametric
minimum spanning trees and parametric matroids in general.
|
|
|
Extremal
problems for geometric hypergraphs
T.
K. Dey and J. Pach.Discrete & Computational
Geometry, Vol. 19, No. 4, (1998), 473--484. Preliminary
version in ISAAC 96, LNCS 1178, 105-114
A
geometric hypergraph H is a collection of i-dimensional
simplices, called hyperedges or, simply,
edges, induced by some (i + 1)-tuples of a vertex set V
in general position in d-space. The topological structure
of geometric graphs, i.e., the case d = 2; i = 1, has been
studied extensively, and it proved to be instrumental
for the solution of a wide range of problems in combinatorial and
computational geometry. They include the k-set problem,
proximity questions, bounding the number of incidences
between points and lines, designing various efficient graph
drawing algorithms, etc. In this paper, we make an attempt
to generalize some of these tools to higher dimensions. We
will mainly consider extremal problems of the following type. What
is the largest number of edges (i-simplices) that a geometric
hypergraph of n vertices can have without containing certain
forbidden configurations? In particular, we discuss the special
cases when the forbidden configura tions are k intersecting
edges, k pairwise intersecting edges, k crossing edges, k pairwise
crossing edges, k edges that can be stabbed by an i-flat, etc.
Some of our estimates will be tight. |
|
|
Computational
Topology
T.
K. Dey, H. Edelsbrunner and S. Guha. Advances
in Discrere and Computational Geometry, eds. B. Chazelle,
J. E. Goodman and R. Pollack. Contemporary Mathematics,
AMS, Providence, 1998 .
The
authors of this article believe there is or should
be a research area appropriately referred to as computational
topology. Its agenda includes the identification
and formalization of topological questions in computer
applications and the study of algorithms for topological
problems. It is hoped this article can contribute to
the creation of a computational branch of topology
with a unifying influence on computing and computer applications.
|
|
|
Visibility
with multiple reflections
B.
Aronov, A. Davis, T. K. Dey, S. P. Pal and D. C. Prasad.Discrete
& Computational Geometry, Vol. 20, No. 61,
(1998), 61--78. Preliminary version in 5th SWAT, 1996,
LNCS 1097, 284-295
We
show that the region lit by a point light source inside
a simple n-gon after at most k reflections off the
boundary has combinatorial complexity O(n2k ),
for any k – 1. A lower bound of Ω((n/k θ(1))2k
) is also established which matches the upper bound for
any fixed k. A simple near-optimal algorithm for computing the
illuminated region is presented, which runs in O(n2k
log n) time and O(n2k ) space for k > 1, and in
O(n2 log2 n) time and O(n2
) space for k = 1. |
|
|
Counting triangle crossings and halving
planes
T.
K. Dey and H. Edelsbrunner.Invited paper in a
special issue, Discrete & Computational Geometry,
Vol. 12 (1994), 281--289
Every
collection of t > 2n^2 triangles with a total of
n vertices in R^3 has \Omega(t^4/n^6) crossing pairs.
This implies that one of their edges meets \Omega(t^3/n^6)
of the triangles. From this it follows that n points
in R^3 have only O(n^{8/3}) halving planes.
Reprint
available upon request |
|
|
