• Articles • Previous Articles     Next Articles

Differentials-based segmentation and parameterization for point-sampled surfaces

Yong-Wei Miao{1,2, Jie-Qing Feng1, Chun-Xia Xiao1, Qun-Sheng Peng1 and A.R. Forrest3   

  1. 1State Key Laboratory of CAD&CG, Zhejiang University, Hangzhou 310027, China 2College of Science, Zhejiang University of Technology, Hangzhou 310032, China 3School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, U.K.
  • Received:2006-09-30 Revised:2007-05-06 Online:2007-09-10 Published:2007-09-10

Efficient parameterization of point-sampled surfaces is a fundamental problem in the field of digital geometry processing. In order to parameterize a given point-sampled surface for minimal distance distortion, a differentials-based segmentation and parameterization approach is proposed in this paper. Our approach partitions the point-sampled geometry based on two criteria: variation of Euclidean distance between sample points, and angular difference between surface differential directions. According to the analysis of normal curvatures for some specified directions, a new projection approach is adopted to estimate the local surface differentials. Then a $k$-means clustering ($k$-MC) algorithm is used for partitioning the model into a set of charts based on the estimated local surface attributes. Finally, each chart is parameterized with a statistical method --- multidimensional scaling (MDS) approach, and the parameterization results of all charts form an atlas for compact storage.

Key words: collaborative problem solving; concurrent action; multi-agent sys-tem; possible world;

[1] Levy B, Petitjean S, Ray N, Maillot J. \rm Least squares conformal maps for automatic texture atlas generation. -\it ACM Transactions on Graphics}, 2002, 21(3): 362$\sim$371.

[2] Zwicker M, Pauly M, Knoll O, Gross M. \rm Pointshop 3D: An interactive system for point-based surface editing. -\it ACM Transactions on Graphics}, 2002, 21(3): 322$\sim$329.

[3] Zigelman G, Kimmel R, Kiryati N. \rm Texture mapping using surface flattening via multidimensional scaling. -\it IEEE Transactions on Visualization and Computer Graphics}, 2002, 8(2): 198$\sim$207.

[4] Biermann H, Martin I, Bernardini F, Zorin D. \rm Cut-and-paste editing of multiresolution surfaces. -\it ACM Transactions on Graphics}, 2002, 21(3): 312$\sim$321.

[5] Pauly M, Keiser R, Kobbelt L, Gross M. \rm Shape modeling with point-sampled geometry. -\it ACM Transactions on Graphics}, 2003, 22(3): 641$\sim$650.

[6] Liu X G, Bao H J, Peng Q S. \rm Digital differential geometry processing. -\it Journal of Computer Science and Technology}, 2006, 21(5): 847$\sim$860.

[7] Eck M, DeRose T, Duchamp T \it et al. \rm Multiresolution analysis of arbitrary meshes. In -\it Proc. ACM SIGGRAPH'95}, Los Angeles, California, 1995, pp.173$\sim$182.

[8] Lee A, Sweldens W, Schr\"-o}der P \it et al. \rm MAPS: Multiresolution adaptive parametrization of surfaces. In -\it Proc. ACM SIGGRAPH'98}, Orlando, Florida, 1998, pp. 95$\sim$104.

[9] Liu Y J, Tang K, Yuen M M. \rm Multiresolution free form object modeling with point sampled geometry. -\it Journal of Computer Science and Technology}, 2004, 19(5): 607$\sim$617.

[10] Khodakovsky A, Schr\"-o}der P, Sweldens W. \rm Progressive geometry compression. In -\it Proc. ACM SIGGRAPH'00}, New Orleans, Louisiana, 2000, pp.271$\sim$278.

[11] Waschb\"-u}sch M, W\"-u}rmlin S, Lamboray E \it et al. \rm Progressive compression of point-sampled models. In -\it Proc. the Eurographics Symposium on Point-Based Graphics'04}, Zurich, Switzerland, 2004, pp.95$\sim$102.

[12] Zhou K, Bao H J, Shi J Y, Peng Q S. \rm Geometric signal compression. -\it Journal of Computer Science and Technology}, 2004, 19(5): 596$\sim$606.

[13] Floater M, Hormann K. \rm Surface Parameterization: A Tutorial and Survey. Advances in Multiresolution for Geometric Modelling, Dodgson N, Floater M, Sabin M (eds.), Heidelberg: Springer-Verlag, 2005, pp.157$\sim$186.

[14] doCarmo M P. Differential Geometry of Curves and Surfaces. Englewood Cliffs: Prentice-Hall, New Jersey, 1976.

[15] Maillot J, Yahia H, Verroust A. \rm Interactive Texture Mapping. In -\it Proc. ACM SIGGRAPH'93}, Anaheim, California, 1993, pp.27$\sim$34.

[16] Sander P, Snyder J, Gortler S, Hoppe H. \rm Texture mapping progressive meshes. In -\it Proc. ACM SIGGRAPH'01}, Los Angeles, California, 2001, pp.409$\sim$416.

[17] Sorkine O, Cohen-or D, Goldenthal R, Lischinski D. \rm Bounded-distortion piecewise mesh parameterization. In -\it Proc. IEEE Visualization'02}, Boston, Massachusetts, 2002, pp.355$\sim$362.

[18] Sander P, Wood Z, Gortler S \it et al. \rm Multi-chart geometry images. In -\it Proc. the Eurographics Symposium on Geometry Processing'03}, Aachen, Germany, 2003, pp.146$\sim$155.

[19] Zhou K, Snyder J, Guo B, Shum H-Y. \rm Iso-charts: Stretch-driven mesh parameterization using spectral analysis. In -\it Proc. the Eurographics Symposium on Geometry Processing'04}, Nice, France, 2004, pp.47$\sim$56.

[20] Zhou K, Wang X, Tong Y \it et al. \rm TextureMontage: seamless texturing of arbitrary surfaces from multiple images. -\it ACM Transactions on Graphics}, 2005, 24(3): 1148$\sim$1155.

[21] Floater M, Reimers M. \rm Meshless parameterization and surface reconstruction. -\it Computer Aided Geometric Design}, 2001, 18(2): 77$\sim$92.

[22] Zwicker M, Gotsman C. \rm Meshing point clouds using spherical parameterization. In -\it Proc. the Eurographics Symposium on Point-Based Graphics'04}, Zurich, Switzerland, 2004, pp.173$\sim$180.

[23] Kalaiah A, Varshney A. \rm Differential point rendering. In -\it Proc. 12th Eurographics Workshop on Rendering}, London, UK, 2001, pp.139$\sim$150.

[24] Pauly M, Gross M, Kobbelt L. \rm Efficient simplification of point-sampled surfaces. In -\it Proc. IEEE Visualization'02}, Boston, Massachusetts, 2002, pp.163$\sim$170.

[25] Adamson A, Alexa M. \rm Anisotropic point set surfaces. In -\it Proc. Afrigraph'06}, Cape Town, South Africa, 2006, pp.7$\sim$13.

[26] Levin D. \rm Mesh-Independent Surface Interpolation. -\it Geometric Modeling for Scientific Visualization}, Brunnett G, Hamann B, Mueller K, Linsen L (eds.), Heidelberg: Springer-Verlag, 2003, pp.37$\sim$49.

[27] Alexa M, Adamson A. \rm On normals and projection operators for surfaces defined by point sets. In -\it Proc. the Eurographics Symposium on Point-Based Graphics'04}, Zurich, Switzerland, 2004, pp.149$\sim$155.

[28] Taubin G. \rm Estimating the tensor of curvature of a surface from a polyhedral approximation. In -\it Proc. 5th International Conference on Computer Vision'95}, Boston, Massachusetts, 1995, pp.902$\sim$907.

[29] Lange C, Polthier K. \rm Anisotropic smoothing of point sets. -\it Computer Aided Geometric Design}, 2005, 22(7): 680$\sim$692.

[30] Krishnamurthy V, Levoy M. \rm Fitting smooth surfaces to dense polygon meshes. In -\it Proc. ACM SIGGRAPH'96}, New Orleans, Louisiana, 1996, pp.313$\sim$324.

[31] Yamauchi H, Gumhold S, Zayer R, Seidel H-P. \rm Mesh segmentation driven by Gaussian curvature. -\it The Visual Computer}, 2005, 21(8$\sim$10): 659$\sim$668.

[32] Katz S, Tal A. \rm Hierachical mesh decomposition using fuzzy clustering and cuts. -\it ACM Transactions on Graphics}, 2003, 22(3): 954$\sim$961.

[33] Sander P, Gortler S, Snyder J, Hoppe H. \rm Signal-specialized parameterization. In -\it Proc. 13th Eurographics Workshop on Rendering}, Pisa, Italy, 2002, pp.87$\sim$100.

[34] Desbrun M, Meyer M, Alliez P. \rm Intrinsic parameterizations of surface meshes. -\it Computer Graphics Forum}, 2002, 21(3): 209$\sim$218.

[35] Barhak J, Fischer A. \rm Parameterization and reconstruction from 3D scattered points based on neural network and PDE techniques. -\it IEEE Transactions on Visualization and Computer Graphics}, 2001, 7(1): 1$\sim$16.

[36] Lloyd S P. \rm Least squares quantization in PCM. -\it IEEE Trans. Information Theory}, 1982, 28(2): 129$\sim$137.

[37] Kanungo T, Mount D M, Netanyahu N S \it et al. \rm An efficient $k$-means clustering algorithm: Analysis and implementation. -\it IEEE Transactions on Pattern Analysis and Machine Intelligence}, 2002, 24(7): 881$\sim$892.

[38] Tenenbaum J, Silva V, Langford J. \rm A global geometric framework for nonlinear dimensionality reduction. -\it Science}, 2000, 290(12): 2319$\sim$2323.

[39] Jia Y-B, Mi L C, Tian J. \rm Surface patch reconstruction via curve sampling. In -\it Proc. the IEEE International Conference on Robotics and Automation}, Orlando, Florida, 2006, pp.1371$\sim$1377.

[40] Kruskal J B, Wish M. Multidimensional scaling. Beverly Hills, California: Sage Publications, 1978.
[1] FAN Xiaocong; XU Dianxiang; HOU Jianmin; ZHENG Guoliang;. Reasoning about Concurrent Actionsin Multi-Agent Systems [J]. , 1999, 14(4): 422-428.
Full text



[1] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4] Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[5] Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[6] Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[7] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[8] Zhao Jinghai; Liu Shenquan;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .
[9] Shang Lujun; Xu Lihui;. Notes on the Design of an Integrated Object-Oriented DBMS Family[J]. , 1991, 6(4): 389 -394 .
[10] Xu Jianguo; Gou Yuchai; Lin Zongkai;. HEPAPS:A PCB Automatic Placement System[J]. , 1992, 7(1): 39 -46 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved