Computer-Aided Design 41 (2009) 395–403
Contents lists available at ScienceDirect
Computer-Aided Design
journal homepage: www.elsevier.com/locate/cad
Curvature-aware adaptive re-sampling for point-sampled geometry
Yongwei Miao
a,b,c,∗
, Renato Pajarola
c
, Jieqing Feng
a
a
State Key Laboratory of CAD&CG, Zhejiang University, China
b
College of Science, Zhejiang University of Technology, China
c
Department of Informatics, University of Zurich, Switzerland
a r t i c l e i n f o
Article history:
Received 14 April 2008
Accepted 22 January 2009
Keywords:
Point-sampled geometry
Adaptive re-sampling
Simplification
Curvature-aware
Mean-shift clustering
a b s t r a c t
With the emergence of large-scale point-sampled geometry acquired by high-resolution 3D scanning
devices, it has become increasingly important to develop efficient algorithms for processing such models
which have abundant geometric details and complex topology in general. As a preprocessing step, surface
simplification is important and necessary for the subsequent operations and geometric processing. Owing
to adaptive mean-shift clustering scheme, a curvature-aware adaptive re-sampling method is proposed
for point-sampled geometry simplification. The generated sampling points are non-uniformly distributed
and can account for the local geometric feature in a curvature aware manner, i.e. in the simplified model
the sampling points are dense in the high curvature regions, and sparse in the low curvature regions. The
proposed method has been implemented and demonstrated by several examples.
© 2009 Elsevier Ltd. All rights reserved.
1. Introduction
With the rapid development of various 3D scanning devices,
point-sampled geometry has become a powerful alternative to
the traditional polygonal geometric model in computer graphics
[1–3]. Efficient modeling and rendering techniques for the point-
sampled geometry have developed into an attractive research
area for its potential ability in representing complex geometric
models with high-fidelity [4–6]. However, due to the large memory
requirement and high time complexity, efficiently processing large
scale point-sampled geometry is still facing great challenges, such
as storage, editing, transmission, and rendering, etc. To achieve
real-time performance required in many application fields such
as entertainment, industrial design, virtual reality etc. [7,8], a
simplification procedure is an efficient solution to alleviate the
storage and time complexities.
In the point-sampled geometry simplification, it is important
to choose the representative points and re-sampling the original
geometry for faithfully approximating the underlying geometry
in both geometry and topology. In practical applications, how to
keep geometric features may attract more attentions since it is
a comparably simple task to keep the simplified model topology
unchanged. Thus, pursuing the geometry fidelity of the simplified
model, the sampling density variation should manifest the local
geometric features, i.e. the sample points should be dense in
the sharp features regions (usually with high curvatures), and
∗
Corresponding author.
E-mail addresses: miaoyw@cad.zju.edu.cn, ywmiao@zjut.edu.cn (Y. Miao).
sparse in the relative planar regions (usually with low curvatures).
Another important issue that relates to surface re-sampling is
the theoretical analysis of sampling conditions and other pre-
conditions for correct reconstruction of surfaces with or without
boundaries [9–11].
Owing to the efficiency of feature space analysis, a mean-shift
scheme is performed in both spatial and range domain of the
underlying geometry. Due to the bilateral filtering property of our
mean-shift clustering scheme, the proposed re-sampling approach
can filter moderate noise attached by the given model. Moreover,
in order to guide a feature sensitive re-sampling procedure,
unlike the fixed bandwidth mean-shift clustering, the proposed
adaptive scheme is suitable for the moderately non-uniformly
distributed point-sampled geometry. However, point clouds with
highly non-uniform sampling or large noise cannot be treated well
by our algorithm. For these raw scanner data, some pre-processing
steps [12] should be performed for subsequent re-sampling task.
The contributions are summarized as follows:
• Based on an adaptive mean-shift clustering scheme, a novel
point-sampled geometry simplification method is proposed,
which can adaptively re-sample the underlying model so as
to reflect the intrinsic geometry features whilst introducing
relatively lower geometric error.
• By choosing different thresholds and different weights in
our mean-shift clustering scheme, the adaptive re-sampling
scheme can adapt to different sampling density requirements
of the underlying point-sampled geometry.
0010-4485/$ – see front matter © 2009 Elsevier Ltd. All rights reserved.
doi:10.1016/j.cad.2009.01.006