启发式轮廓线不变的网格自适应简化算法

系统仿真学报 ›› 2016, Vol. 28 ›› Issue (9): 2176-2185.

启发式轮廓线不变的网格自适应简化算法

周文, 贾金原

同济大学软件学院,上海 201804

收稿日期:2016-05-30 修回日期:2016-07-11 出版日期:2016-09-08 发布日期:2020-08-14
作者简介:周文(1984-),男,安徽,博士生,研究方向为图像处理,草图搜索等;贾金原(1963-),男,山东,博导,教授,研究方向为虚拟现实、几何造型等。
基金资助:
国家自然科学基金(61272276)

Self-adaptive Simplification Algorithm for Suggestive-contours preserving

Zhou Wen, Jia Jinyuan

School of software engineering, Tongji University, Shanghai 201804, China

Received:2016-05-30 Revised:2016-07-11 Online:2016-09-08 Published:2020-08-14

摘要/Abstract

摘要： 在大规模的三维模型检索中,快速提取特征是非常重要的。简化网格的数量,但不改变模型外在形态,这样既保持特征不变,又提高提取特征的速度。提出了基于十字链表的索引结构的自适应简化算法的框架,自适应选择简化比率。对网格计算主曲率,选择合适的边入堆并进行简化。实验中,模型进行分组比较,程序都能够很快进行简化操作。同时,还进行了简化效率和提出的算法和半边数据结构的算法的对比实验,发现提出的算法在时间耗费有明显优势。进行提取了启发式轮廓线和自适应算法的对比实验,表明算法在时间上具有比较优势。

关键词: 模型检索, 十字链表, 自适应, 主曲率, 堆, 启发式轮廓线

Abstract: It is important that features quickly extract in large-scale model retrieval. The preprocessing of 3D model simplified the mesh, not changed the contours. Based on the data structure of the cross linked list, a framework for self-adaptive algorithm was proposed, according to mesh structure, it automatically selected the rate to simplify. Besides, by computing the related mesh principal curvatures, the edge that some condition was met, were put in the structure of heap for simplification operating. In the experiment, the models were divided into the complex model and the common model. The program could simplify the operation of the mesh. Moreover, the comparative experiment of mesh simplification efficiency was conducted. It could be found that the efficiency of complex model was less than common model. Besides, the different methods were compared, the proposed method was better in time consuming facet. Then, extracted suggestive contours experiment was done. The result show proposed method is better. The best simply rate can been computed by the proposed self-adaptive algorithm.

Key words: model retrieval, cross linked list, self-adaptive, principal curvature, heap, suggestive contours

中图分类号:

TP391.9

周文, 贾金原. 启发式轮廓线不变的网格自适应简化算法[J]. 系统仿真学报, 2016, 28(9): 2176-2185.

Zhou Wen, Jia Jinyuan. Self-adaptive Simplification Algorithm for Suggestive-contours preserving[J]. Journal of System Simulation, 2016, 28(9): 2176-2185.

参考文献 16

[1]	Shanghong Zhao, Wei Tsang Ooi, A Carlier, et al. 3D mesh preview streaming[C]// ACM Multimedia Systems Conference Series, 2013. USA: ACM, 2013. [DOI: 10.1016/S0925-7721(99)00007-3].
[2]	Kettner L.Using generic programming for designing a data structure for polyhedral surfaces[J]. Computational Geometry(S0925-7721), 1999, 13(1): 65-90.
[3]	Garland M, Heckbert P S.Surface simplification using quadric error metrics [C]// Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’97, New York, NY, USA. New York, USA: ACM Press/Addison-Wesley, 1997: 209-216.
[4]	Rossignac J, Borrel P.Multi-resolution 3D approximation for rendering complex scenes[C]// Falcidieno B, Kunii T L.(eds.) Geometric Modeling in Computer Graphics: Graphics: Methods and Applications. Berlin, Germany: Springer, 1993: 455-465.
[5]	Hoppe H, DeRose T, Duchamp T, et al. Mesh optimization[C]// Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH’93. USA: ACM, 1993: 19-26.
[6]	Schroeder W, Zarge J, Lorensen W.Decimation of triangle meshes, Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques[J]. ACM SIGGRAPH Computer Graphics (S1467-8659), 1992, 26(1): 65-70.
[7]	Hoppe H.Progressive meshes[C]// Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’96. USA: ACM, 1996 : 99-108.
[8]	Laixiang Wen, J Jia, S Liang LPM. Lightweight Progressive Meshes Towards Smooth Transmission of Web3D Media over Internet[C]// Proceedings of the 13th ACM SIGGRAPH, 2014. USA: ACM, 2014.
[9]	S Morigi, M Rucci.Multilevel mesh simplification[J] Vis Compute, 2014, 30(5): 479-492. [DOI: S00371-013- 0873-6].
[10]	Lavoué G, Chevalier L, Dupont F.Streaming compressed 3D data on the web using JavaScript and WebGL[C]// Proceedings of the 18th International Conference on 3D Web Technology. USA: ACM, 2013: 19-27.
[11]	Evans A, Romeo M, Bahrehmand A, et al.3D graphics on the web: A survey[J]. Computers & Graphics (S0097-8493), 2014, 41(1): 43-61.
[12]	Botsch M, Kobbelt L, Pauly M, et al.Polygon mesh processing [M]. London, BK: Taylor and Francis Press, 2010.
[13]	Decarlo D, Finkelstein A, Rusinkiewicz S, et al.Suggestive Contours for Conveying Shape[J]. ACM Transactions on Graphics (S0730-0301), 2003, 22(3): 848-855.
[14]	Eitz M, Hildebrand K, Boubekeur T, et al.Sketch-Based Shape Retrieval[J]. ACM Transactions on Graphics (S0730-0301), 2010, 31(4): 13-15.
[15]	Sang M Y, Kuijper A.View-based 3D model retrieval using compressive sensing based classification[J]. Histogram (S2230-7109), 2011, 11(1): 437-442.
[16]	Lee C H, Varshney A, Jacobs D W.Mesh Saliency[J]. ACM Transactions on Graphics (S0730-0301), 2005, 24(3): 659-666.