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
|
Approximating
loops in a shortest homology basis from point data
T. K. Dey, J. Sun, and Y. Wang. arXiv:0909.5654v1[cs.CG], 30th
September 2009.
Inference of topological and geometric
attributes of a hidden manifold from its point data is a fundamental problem
arising in many scientific studies and engineering applications. In this
paper we present an algorithm to compute a set of loops from a point data
which approximates a shortest basis of the one dimensional homology group
H_1(M) of the sampled manifold M. Previous results addressed the issue of
computing the rank of the homology groups from point data, but there is no
result on approximating the shortest basis of a manifold from its point sample.
In arriving our result, we also present a polynomial time algorithm for computing
a shortest basis of H_1(K) for any finite simplicial complex K embedded in
Euclidean space.
|
|
|
Convergence,
Stability, and Discrete Approximation of Laplace Spectra
T. K. Dey, P. Ranjan, and Y. Wang. Proc. ACM/SIAM Sympos. Discrete
Algorithms 2010, to appear.
Spectral methods have been widely
used in a broad range of applications fields. One important object involved
in such methods is the Laplace-Beltrami operator of a manifold. Indeed, a
variety of work in graphics and geometric optimization uses the eigen-structures
(i.e., the eigenvalues and eigenfunctions) of the Laplace operator. Applications
include mesh smoothing, compression, editing, shape segmentation, matching,
parameterization, and so on. While the Laplace operator is defined (mathematically)
for a smooth domain, these applications often approximate a smooth manifold
by a discrete mesh. The spectral structure of the manifold Laplcian is estimated
from some discrete Laplace operator constructed from this mesh.
In this paper, we study the important question of how well the specturm
computed from the discrete mesh approximates the true spectrum of the manifold
Lplacian. We exploit a recent result on mesh Laplacian and provide the first
convergence result to relate the spectrum constructed from a general mesh
(approximating an m-manifold embedded in R^d) with the true spectrum. We
also study how stable these eigenvalues and their discrete approximations
are when the underlying manifold is perturbed, and provide explicit bounds
for the Laplacian spectra of two ``close" manifolds, as well as a convergence
result for their discrete approximations. Finally, we present various experimental
results to demonstrate that these discrete spectra are both accurate and
robust in practice.
|
|
|
Repairing
and meshing imperfect shapes with Delaunay refinement
O. Busaryev, T. K. Dey, J. A. Levine. Proc. SIAM/ACM Joint
Conf. Geometric and Physical Modeling (2009), to appear.
As a direct consequence of software
quirks, designer errors, and representation flaws, often three-dimensional
shapes are stored in formats that introduce inconsistencies such as small
gaps and overlaps between surface patches. We present a new algorithm that
simultaneously repairs imperfect geometry and topology while generating
Delaunay meshes of these shapes. At the core of this approach is a meshing
algorithm for input shapes that are piecewise smooth complexes (PSCs), a
collection of smooth surface patches meeting at curves non-smoothly or in
non-manifold configuarations. Guided by a user tolerance parameter, we automatically
merge nearby components while building a Delaunay mesh that has many of these
errors fixed. Experimental evidence is provided to show the results of our
algorithm on common computer-aided design (CAD) formats. Our algorithm may
also be used to simplify shapes by removing small features which would
require an excessive number of elements to preserve them in the output mesh.
Note: One of the main ingredients of this paper is our PSC
meshing paper.
|
|
|
Isotopic
Reconstruction of Surfaces with Boundaries
T. K. Dey, K. Li., E. A. Ramos, and R. Wenger.
Proc. Sympos. Geom. Processing.(SGP09), special issue of Computer
Graphics Forum, Vol. 28, No. 5 (2009), 1371--1382. [Web-page]
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. Algorithms, vol. 2, issue
4 (2009), 1327--1349. doi:10.3390/a2041327
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
|
|
|
