|
On Computing Handle and Tunnel Loops
with T. K. Dey and Kuiyu Li. OSU-CISRC-6/07-TR48
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
implementation with applications to feature detection and topology
simplification to show the effectiveness of the method.
paper
|
|
|
Defining and Computing Curve-skeletons with Medial Geodesic Function
with T. K. Dey. Symposium on Geometry Processing 2006.
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
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 methematical 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.
paper
talk slides
software: CurveSkel
|
|
|
Normal and Feature Estimations from Noisy Point Clouds
with T. K. Dey. The 26th Conference on Foundations of Software Technology
and Theoretical Computer Science (FSTTCS) 2006
We consider the problem of normal and feature size approximations of a
surface from its point cloud data that may be noisy. These problems are central
to many applications dealing with point cloud data. Although solutions to
these problems for noise-free case are known, the case with noise is not
fully understood. We provide new analysis that brings new insights and design
new algorithms based on these analyses.
paper
software: NormFet
|
|
|
An Adaptive MLS Surface for Reconstruction with Guarantees.
with T. K. Dey. Symposium on Geometry Processing 2005.
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.
paper
talk slides
software: AMLS
For those interested in the proofs, please see the
extended version
Technical Report OSU-CISRC-4-05-TR26, April, 2005.
|
|
|
Normal Estimation for Point Clouds : A Comparison Study for a Voronoi Based Method
with T. K. Dey and Gang Li. Symposium on Point-Based Graphics 2005.
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.
paper
talk slides
|
|
|
Extremal Surface Based Projections Converge and Reconstruct with Isotopy.
with T. K. Dey and S. Goswami. Technical Report OSU-CISRC-05-TR25, April, 2005
Many real world applications need to model a
smooth surface from a
noisy point sample. In order to eliminate unnecessary undulations on
the output surface, it is necessary to project the points on a nearby
smooth surface and then approximate the smooth surface with a surface
reconstruction algorithm. Moving Least Square (MLS) surfaces in the
family of extremal surfaces have been shown to be useful as
projection
targets. However, it is unknown if the extremal surface based
projection procedure converges and if the target extremal surface
is
isotopic to the original sampled surface. We prove these two facts. The
success the entire projection method depends on the quality of
the
estimated normals at the sample points. We suggest an algorithm
to estimate the normals from the noisy samples which can be of independent
interest for other applications. We also present some experimental
results.
paper
|
|
