›› 2010, Vol. 25 ›› Issue (3): 595-605.

• Computer Graphics and Visualization • Previous Articles     Next Articles

Feature Preserving Mesh Simplification Using Feature Sensitive Metric

Jin Wei1 (魏瑨), Student Member, CCF, ACM, and Yu Lou2 (楼宇), Student Member, ACM   

  1. 1Tsinghua National Laboratory for Information Science and Technology, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
    2Department of Computer Science, Stanford University, Stanford, 94305, U.S.A.
  • Received:2009-04-20 Revised:2010-03-18 Online:2010-05-05 Published:2010-05-05
  • About author:
    Jin Wei is a Master candidate at the Department of Computer Science and Technology, Tsinghua University. His research interests include digital geometry processing, video processing, and computational camera. He is a student member of China Computer Federation and ACM.
    Yu Lou is currently a Master candidate in the Department of Computer Science, Stanford University. His research interests include computer graphics, mesh processing, and image processing. He is a student member of ACM.
  • Supported by:

    This work was supported by the National Basic Research 973 Program of China (Grant No. 2006CB303106), the National Natural Science Foundation of China (Grant Nos. 60673004, 90718035) and the National High Technology Research and Development 863 Program of China (Grant No. 2007AA01Z336).

We present a new method for feature preserving mesh simplification based on feature sensitive (FS) metric. Previous quadric error based approach is extended to a high-dimensional FS space so as to measure the geometric distance together with normal deviation. As the normal direction of a surface point is uniquely determined by the position in Euclidian space, we employ a two-step linear optimization scheme %SOR (successive over-relaxation) to efficiently derive the constrained optimal target point. We demonstrate that our algorithm can preserve features more precisely under the global geometric properties, and can naturally retain more triangular patches on the feature regions without special feature detection procedure during the simplification process. Taking the advantage of the blow-up phenomenon in FS space, we design an error weight that can produce more suitable results. We also show that Hausdorff distance is markedly reduced during FS simplification.

[1] Heckbert P, Garland M. Survey of polygonal surface simplification algorithms. In SIGGRAPH 1997 Course Notes: Multiresolution Surface Modeling, 1997.

[2] Garland M, Heckbert P. Surface simplification using quadric error metrics. In Proc. SIGGRAPH, Los Angeles, USA, Aug. 3-8, 1997, pp.209-216.

[3] Hoppe H. New quadric metric for simplifying meshes with appearance attributes. In Proc. the 10th IEEE Visualization Conference, San Francisco, USA, Oct. 24-29, 1999, pp.59-66.

[4] Yan J, Shi P, Zhang D. Mesh simplification with hierarchical shape analysis and iterative edge contraction. IEEE Transactions on Visualization and Computer Graphics, 2004, 10(2): 142-151.

[5] Jong B S, Teng J L, Yang W H. An efficient and low-error mesh simplification method based on torsion detection. The Visual Computer, 2005, 22(1): 56-67.

[6] Kimmel R, Malladi R, Sochen N. Image as embedded maps and minimal surfaces: Movies, color, texture and volumetric medical images. International Journal of Computer Vision, 2000, 39(2): 111-129.

[7] Lai Y K, Zhou Q Y, Hu S M, Wallner J, Pottmann H. Robust feature classification and editing. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(1): 34-45.

[8] Lai Y K, Hu S M, Pottmann H. Surfacefitting based on a feature sensitive parameterization. Computer-Aided Design, 2006, 38(7): 800-807.

[9] Lai Y K, Zhou Q Y, Hu S M, Martin R R. Feature sensitive mesh segmentation. In Proc. ACM Symposium on Solid and Physical Modeling, Cardiff, UK, June 6-8, 2006, pp.17-25.

[10] Cohen J, Olano M, Manocha D. Appearance-preserving simplification. In Proc. the 25th Annual Conference on Computer Graphics and Interactive Techniques, Orlando, USA, July 19-24, 1998, pp.115-122.

[11] Kho Y, Garland M. User-guided simplification. In Proc. ACM Symposium on Interactive 3D Graphics, Monterey, USA, April 27-30, 2003, pp.123-126.

[12] Garland M, Zhou Y. Quadric-based simplification in any dimension. ACM Transactions on Graphics, 2005, 24(2): 209239.

[13] Lindstrom P, Turk G. Image-driven simplification. ACM Transactions on Graphics, 2000, 19(3): 204-241.

[14] Yoshizawa S, Belyaev A G, Seidel H P. Fast and robust detection of crest lines on meshes. In Proc. ACM Symposium on Solid and Physical Modeling, Cambridge, USA, June 13-15, 2005, pp.13-15.

[15] Cohen-Steiner D, Alliez P, Desbrun M. Variational shape approximation. In Proc. ACM SIGGRAPH, Los Angeles, USA, Aug. 8-12,, 2004 pp.905-914.

[16] Bian Z, Hu S M, Martin R R. Evaluation for small visual difference between conforming meshes on strainfield. Journal of Computer Science and Technology, 2009, 24(1): 65-75.

[17] Cignoni P, Rocchini C, Scopigno R. Metro: Measuring error on simplified surfaces. Computer Graphics Forum, 1998, 17(2): 167-174.

[18] Hussain M. Efficient simplification methods for generating high quality LODs of 3D meshes. Journal of Computer Science and Technology, 2009, 24(3): 604-inside back cover.

No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

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