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
|
Optimal
homologous cycles, total unimodularity, and linear programming.
T. K. Dey, A. Hirani, and B. Krishnamoorthy. arXiv:1001.0338v1[math.AT],
2nd January, 2010.
Given a simplicial complex with weights on its simplices,
and a nontrivial cycle on it, we are interested in finding the cycle with
minimal weight which is homologous to the given one. Assuming that the homology
is defined with integer (Z) coefficients, we show the following (Theorem
5.2):
For a finite simplicial complex K of dimension greater than p, the boundary
matrix [d_(p+1)] is totally unimodular if and only if H_p(L,L_0) is torsion-free
for all pure subcomplexes L_0, L in K of dimension p and p+1 respectively
where L_0\subset L.
Because of the total unimodularity of the boundary matrix, we can solve
the optimization problem, which is inherently an integer programming problem,
as a linear program and obtain integer solution. Thus the problem of finding
optimal cycles in a given homology class can be solved in polynomial time.
This result is surprising in the backdrop of a recent result which says
that the problem is NP-hard under Z_2 coefficients which, being a field,
is in general easier to deal with. One consequence of our result, among
others, is that one can compute in polynomial time an optimal 2-cycle in
a given homology class for any finite simplicial complex embedded in R^3.
Our optimization approach can also be used for various related problems,
such as finding an optimal chain homologous to a given one when they are
not cycles.
|
|
|
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
that presumably sample a smooth manifold M\subset R^d. These loops approximate
a shortest basis of the one dimensional homology group H_1(M) over coefficients
in finite field Z_2. 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 whose edges
have non-negative weights.
|
|
|
Convergence,
Stability, and Discrete Approximation of Laplace Spectra
T. K. Dey, P. Ranjan, and Y. Wang. Proc. ACM/SIAM Sympos.
Discrete Algorithms (2010), 650--663.
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), 25--33.
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]
[Software]
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
|
|
|
