基于商空间的视景仿真模型构建
|
摘要
随着计算机图形学和三维建模技术的发展,三维模型的精度越来越高,数据量也随之快速增长,给计算机的绘制、显示、传输等都带来了巨大的压力。同时,人工智能在解决复杂多样的问题方面发挥着越来越重要的作用,而商空间作为其中的一个分支,在路径时间表安排、信息融合、空间路径规划、分形学、遥感图象分析和处理、模式识别等领域得到了广泛应用。为了解决三维模型在视景仿真过程中遇到的问题,本文引入商空间粒度计算理论对复杂三维模型的构建技术进行研究。
首先,本文通过研究典型的三角化方法,提出一种基于Delaunay的区域增长表面三角化算法,该算法综合了两者的优点,根据来自三维物体表面的一系列散乱样本点集,产生一个三角化模型,并且具有正确的几何拓扑结构,该算法只需要进行一次Delaunay计算,而且不需要Voronoi信息。
其次,将商空间粒度理论应用于视景仿真领域,利用分层递阶思想实现对三维网格模型的分割,将三维网格模型划分为具有不同粗细粒度的模型,使得在视景仿真过程中可以根据视点的需要,在不同的粒度模型间跳转,不仅有效地减少了三维网格模型的数据量,而且提高了视景的刷新率。
最后,利用粒度合成原理,根据三维网格的属性特征,快速形成不同的粒度空间,并设计出有效算法,准确、高效构建三维网格模型的商空间结构,在三维网格模型分割的基础上,通过简化和重建算法实现多分辨率模型的有效控制和实时显示。
With the development of computer graphics and three-dimensional modeling technology, the accuracy of three-dimensional model and the amount of data are also increasing ,which will rapidly increase tremendous pressure to the computer rendering, display and transmission . Simultaneously, artificial intelligence is playing an increasingly important role in solving complex and diverse problems, and as one branch in the artificial intelligence, the Quotient Space Theory is widely used in the path schedule, information fusion, path planning of space, fractal science, analysis and processing of remote sensing images, pattern recognition. In order to deal with these problems encountered during the process of visual simulation for three-dimensional models for dealing with the problems, this paper introduces granularity computing of Quotient Space theory to study the construction techniques of complex three-dimensional models.
First,a triangulation method based on the region growth and Delaunay triangulation algorithm is proposed through the study of typical triangulation methods, which combines the advantages of both,and generates a triangulation model with correct geometry and topology structure , according to three-dimensional surface from a series of scattered set of sample points. The algorithm is calculated only once and did not require Voronoi information.
Secondly, the Quotient Space theory is used in the field of visual simulation, using a hierarchical idea to realize the hierarchical structure of three-dimensional mesh segmentation, which divides three-dimensional mesh model into model with different granularities and could make it jump between different granularities durning the process of visual simulation according to the viewpoint location. It not only could reduce the three-dimensional mesh model effectively, but also improve the visual refresh rate.
Finally, a different granularity space is formed rapidly using of granularity synthetic principle, according to the property characteristics of three-dimensional mesh models. Meanwhile, effective algorithms are designed to construct the Quotient Space structure of three-dimensional mesh models accurately and efficiently.Based on the segmentation of three-dimensional mesh model, effective control and real-time display of multi-resolution models are realized by simplification and reconstruction algorithms.
首先,本文通过研究典型的三角化方法,提出一种基于Delaunay的区域增长表面三角化算法,该算法综合了两者的优点,根据来自三维物体表面的一系列散乱样本点集,产生一个三角化模型,并且具有正确的几何拓扑结构,该算法只需要进行一次Delaunay计算,而且不需要Voronoi信息。
其次,将商空间粒度理论应用于视景仿真领域,利用分层递阶思想实现对三维网格模型的分割,将三维网格模型划分为具有不同粗细粒度的模型,使得在视景仿真过程中可以根据视点的需要,在不同的粒度模型间跳转,不仅有效地减少了三维网格模型的数据量,而且提高了视景的刷新率。
最后,利用粒度合成原理,根据三维网格的属性特征,快速形成不同的粒度空间,并设计出有效算法,准确、高效构建三维网格模型的商空间结构,在三维网格模型分割的基础上,通过简化和重建算法实现多分辨率模型的有效控制和实时显示。
With the development of computer graphics and three-dimensional modeling technology, the accuracy of three-dimensional model and the amount of data are also increasing ,which will rapidly increase tremendous pressure to the computer rendering, display and transmission . Simultaneously, artificial intelligence is playing an increasingly important role in solving complex and diverse problems, and as one branch in the artificial intelligence, the Quotient Space Theory is widely used in the path schedule, information fusion, path planning of space, fractal science, analysis and processing of remote sensing images, pattern recognition. In order to deal with these problems encountered during the process of visual simulation for three-dimensional models for dealing with the problems, this paper introduces granularity computing of Quotient Space theory to study the construction techniques of complex three-dimensional models.
First,a triangulation method based on the region growth and Delaunay triangulation algorithm is proposed through the study of typical triangulation methods, which combines the advantages of both,and generates a triangulation model with correct geometry and topology structure , according to three-dimensional surface from a series of scattered set of sample points. The algorithm is calculated only once and did not require Voronoi information.
Secondly, the Quotient Space theory is used in the field of visual simulation, using a hierarchical idea to realize the hierarchical structure of three-dimensional mesh segmentation, which divides three-dimensional mesh model into model with different granularities and could make it jump between different granularities durning the process of visual simulation according to the viewpoint location. It not only could reduce the three-dimensional mesh model effectively, but also improve the visual refresh rate.
Finally, a different granularity space is formed rapidly using of granularity synthetic principle, according to the property characteristics of three-dimensional mesh models. Meanwhile, effective algorithms are designed to construct the Quotient Space structure of three-dimensional mesh models accurately and efficiently.Based on the segmentation of three-dimensional mesh model, effective control and real-time display of multi-resolution models are realized by simplification and reconstruction algorithms.
引文
[1]张茂军.虚拟现实系统.北京:科学出版社,2001.
[2] Grigore C.Burdea,Philippe Coiffet.虚拟现实技术=Virtual reality technology(魏迎梅,栾悉道,等译).北京:电子工业出版社,2005:5-10.
[3]于海凤,邢桂芬,张凯.虚拟现实技术在视景仿真系统中的应用.计算机工程与设计. 2006,27(6):1108-1110.
[4]吴家铸,党岗,刘华峰等.视景仿真技术及应用.西安:西安电子科技大学出版社, 2001:5-6.
[5] Frederick Wieland,AlexSzabo.Object-Oriented Design of a Scene Generation Simulation. Proceedings of the 1994 Computer Simulation Conference.1995:174-180.
[6]陈应松.OpenGL在数字化货车超限监测模拟仿真中的应用研究.硕士学位论文.西南交通大学,2003.
[7] Gu X. F.,Gortler S.,Hoppe H.Geometry image[A].Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH[C],San Antonio. Texas,2002:355-361.
[8] Chen E,Williams L.View interpolation for image synthesis. International Conference on Computer Graphics and Interactive Techniques(SIGGRAPH’93),NewYork,1993:279-288.
[9] Memillan L,Bishop G. Plenoptic modeling:An image-based rendering system.International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’95),Los Angeles,1995:39-46.
[10] Debevec P E,Taylar C J,Malik J. Modeling and Rendering Architecture from Photographs:A hybrid geometry and image-based approach. International Conference on Computer Graphics and Interactive Techniques(SIGGRAPH’96),NewYork,1996:11-20.
[11] Shum H Y,Kang S B.A review of image-based rendering techniques.Visual Communications and Image Processing,San Jose,2000:2-13.
[12]谢明.基于DirectX9.0的3D游戏设计.硕士学位论文.成都:四川大学,2004,32-36.
[13] Nister D.Automatic Dense Reconstruction form Uncalibrated Video Sequences:(dissertation).Stockholm:Univ.of Stockholms,2001.
[14] Pollefeys M,Gool L V,Vergauwen M et al.Visual modeling with a hand-held camera. International Journal of Computer Vision,2004,59(3):207-232.
[15] Turk G,Levoy M. Zippered polygon meshes from range images. International Conference on Computer Graphics and Interactive Techniques(SIGGRAPH’94) Orlando,1994:311-318.
[16] Pulli K. Multiview registration for large data sets. Proceedings of the 2nd International Conference on 3D Digital Imaging and Modeling,Tampa,1999:160-168.
[17] Levoy M,Pulli K,Curless B et al. The Digital Michelangelo Projeet:3D scanning of large statues.International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’00),NewOrleans,2000:131-144.
[18] Rusinkiewicz S,Levoy M. A multiresolution point rendering system for large meshes. International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’00),NewOrleans,2000:343-352.
[19] Yu Y,Ferencz A,Malik J.Extracting.Objects from range and radiance images.IEEE Transactions on Visualization and Computer Graphics,2001,7(4):351-364.
[20] Dachsbacher C,Vogelgsang C.Mare Stamminger Sequential Point trees[C]. In: Proceedings of SIGGRAPH 2003:657-662.
[21]李必军,方志祥,任娟.从激光扫描数据中进行建筑物特征提取研究.武汉大学学报, 2003,28(1):65-70.
[22]卢秀山,李清泉,冯文颧.车载式城市信息采集与三维建模系统.武汉大学学报(工学版),2003,36(3):76-80.
[23]王君秋,查红彬.结合兴趣点与边缘的建筑物与物体识别方法.计算机辅助设计与图形学学报,2006,18(8):1257-1263.
[24]孟放,查红彬.基于LOD控制与内外存调度的大型三维点云数据绘制.计算机辅助设计与图形学学报,2006,18(1):l-8.
[25]李必军,方志祥,任娟.从激光扫描数据中进行建筑物特征提取研究[J].武汉大学学报(信息科学版),2003,28(l):65-70.
[26]张爱武,孙卫东,李风亭.基于激光扫描数据的室外场景表面重建方法[J].系统仿真学报,2005,17(2):384-391.
[27] G.Taubin,J.Rossignac.3D Geometric Compression.SIGGRAPH 1999 Course Notes,1999.
[28] M.Deering.Geometric Compression.Proc. SIGGRAPH 1995,13-20.
[29] S.Rusinkiewicz,M.Levoy.Efficient Variants of the ICP Algorithm.Proc.International Conference on 3D Digital Imaging and Modeling(3DIM),2001:145-152.
[30]张俊霞.三维地形可视化及其实时显示方法概论[J].北京测绘,2001,2.
[31] CI.ARK J.Hierarchical geometric models for visible surface algorithms[J]. Communications of the ACM.1976,19(10):547-554.
[32]康凤举.现代仿真技术.北京:国防工业出版社,2001:10-245.
[33] L.A.azdeh著,阮达,黄崇福译,模糊集与模糊信息粒理论[M],北京师范大学出版社, 2000,9.
[34]李道国,苗夺谦,张红云.粒度计算的理论,模型与方法[J].复旦学报自然科学版,2004, (5).
[35]李道国,苗夺谦,张东星等.粒度计算研究综述[J].计算机科学,2005,(9).
[36] L.A.Zadeh.Some reflections on sotf computing,granular computing and their roles in the conception design and utilization of information/intelligent systems[J].Sotf Computing, 1998,2(l):23-25.
[37]王国胤,Rouhg集理论与知识获取[M],西安:西安交通大学出版社,2001.
[38] Pawlak Z. Rough Sets: Theoretical Aspects of Reasoning about Data[M]. Dordrecht: Kluwer Academic Publishers,1991.
[39] Zhang B.,Zhang L.,Theory and Application of Problem Solving[M]. North- Holland, Elsevier Science Publishers B.V.,1992.
[40]张铃,张钹,人工神经网络的学习方法[C],陆汝钤,周志华主编,神经网络及其应用,北京:清华大学出版社,2004,1:35.
[41]张铃,张钹,殷海风,多层前向网络的交叉覆盖算法[J],软件学报,1999,10(7):737-742.
[42]边肇祺,张学工.模式识别[M].北京:清华大学出版社,2000,1.
[43]张尧庭,方开泰.多元统计分析引论[M].北京:科学出版社,1982,6.
[44]卜东波,白硕,李国杰.聚类/分类中的粒度原理[J],计算机学报,2002,25(8):810-816.
[45]谢丰.多视点距离图像的对准和集成方法的研究.硕士学位论文.北京:北京工业大学, 2003.
[46] Rossignac,J,Bowel P.Multi-Resolution 3D approximation for rendering complex scenes [C].In Proceedings of the 2nd Conference Modeling in Computer Graphics:Methods and Applications.Berlin 1993,453-465.
[47] Sclmiitt F,Barsky B,Du,W.-H.An adaptive subdivision method for surface-fitting from sampled data[C].In Proceedings of the Computer Graphics(SIGGRAPH 86).1986,179- 188.
[48] Pauly M,Kobbelt LP,Gross M.Point 2 based multi-scale surface representation[J].ACM Trans on Graphics,2006,25(2):177-193.
[49] Alexa M,Behr J,Cohen-Or D,Fleishman S,Levin D,Silva T.Point Set Surface[C].IEEE Visualization,2001:110-116.
[50] Michale E Agishtein,Alexzander A Migdal.Smooth surface reconstruction from scattered data points.Computer & Graphics,1991,15(1):29-39.
[51] P.Cignoni,C.Montani,R.Scopigno.A Fast Divide and Conquer Delaunay Triangulation Algorithm in Ed.CAD,1998,30(5):333-341.
[52] Kuo CC, Yau HT. Reconstruction of virtual parts from unorganized scanned data for automated dimensional inspection[J]. Comput Inf SciEng (JCISE), Trans ASME.2003, 3(1):76-86.
[53] Aurenhammer F.Voronoi diagrams-a survey of a fundamental geometric data structure. ACM Comput Surv. 1991,23(3):345-405.
[54] David C-S,A greedy Delaunay based surface reconstruction algorithm. Research Report, INRIA.2002.
[2] Grigore C.Burdea,Philippe Coiffet.虚拟现实技术=Virtual reality technology(魏迎梅,栾悉道,等译).北京:电子工业出版社,2005:5-10.
[3]于海凤,邢桂芬,张凯.虚拟现实技术在视景仿真系统中的应用.计算机工程与设计. 2006,27(6):1108-1110.
[4]吴家铸,党岗,刘华峰等.视景仿真技术及应用.西安:西安电子科技大学出版社, 2001:5-6.
[5] Frederick Wieland,AlexSzabo.Object-Oriented Design of a Scene Generation Simulation. Proceedings of the 1994 Computer Simulation Conference.1995:174-180.
[6]陈应松.OpenGL在数字化货车超限监测模拟仿真中的应用研究.硕士学位论文.西南交通大学,2003.
[7] Gu X. F.,Gortler S.,Hoppe H.Geometry image[A].Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH[C],San Antonio. Texas,2002:355-361.
[8] Chen E,Williams L.View interpolation for image synthesis. International Conference on Computer Graphics and Interactive Techniques(SIGGRAPH’93),NewYork,1993:279-288.
[9] Memillan L,Bishop G. Plenoptic modeling:An image-based rendering system.International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’95),Los Angeles,1995:39-46.
[10] Debevec P E,Taylar C J,Malik J. Modeling and Rendering Architecture from Photographs:A hybrid geometry and image-based approach. International Conference on Computer Graphics and Interactive Techniques(SIGGRAPH’96),NewYork,1996:11-20.
[11] Shum H Y,Kang S B.A review of image-based rendering techniques.Visual Communications and Image Processing,San Jose,2000:2-13.
[12]谢明.基于DirectX9.0的3D游戏设计.硕士学位论文.成都:四川大学,2004,32-36.
[13] Nister D.Automatic Dense Reconstruction form Uncalibrated Video Sequences:(dissertation).Stockholm:Univ.of Stockholms,2001.
[14] Pollefeys M,Gool L V,Vergauwen M et al.Visual modeling with a hand-held camera. International Journal of Computer Vision,2004,59(3):207-232.
[15] Turk G,Levoy M. Zippered polygon meshes from range images. International Conference on Computer Graphics and Interactive Techniques(SIGGRAPH’94) Orlando,1994:311-318.
[16] Pulli K. Multiview registration for large data sets. Proceedings of the 2nd International Conference on 3D Digital Imaging and Modeling,Tampa,1999:160-168.
[17] Levoy M,Pulli K,Curless B et al. The Digital Michelangelo Projeet:3D scanning of large statues.International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’00),NewOrleans,2000:131-144.
[18] Rusinkiewicz S,Levoy M. A multiresolution point rendering system for large meshes. International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’00),NewOrleans,2000:343-352.
[19] Yu Y,Ferencz A,Malik J.Extracting.Objects from range and radiance images.IEEE Transactions on Visualization and Computer Graphics,2001,7(4):351-364.
[20] Dachsbacher C,Vogelgsang C.Mare Stamminger Sequential Point trees[C]. In: Proceedings of SIGGRAPH 2003:657-662.
[21]李必军,方志祥,任娟.从激光扫描数据中进行建筑物特征提取研究.武汉大学学报, 2003,28(1):65-70.
[22]卢秀山,李清泉,冯文颧.车载式城市信息采集与三维建模系统.武汉大学学报(工学版),2003,36(3):76-80.
[23]王君秋,查红彬.结合兴趣点与边缘的建筑物与物体识别方法.计算机辅助设计与图形学学报,2006,18(8):1257-1263.
[24]孟放,查红彬.基于LOD控制与内外存调度的大型三维点云数据绘制.计算机辅助设计与图形学学报,2006,18(1):l-8.
[25]李必军,方志祥,任娟.从激光扫描数据中进行建筑物特征提取研究[J].武汉大学学报(信息科学版),2003,28(l):65-70.
[26]张爱武,孙卫东,李风亭.基于激光扫描数据的室外场景表面重建方法[J].系统仿真学报,2005,17(2):384-391.
[27] G.Taubin,J.Rossignac.3D Geometric Compression.SIGGRAPH 1999 Course Notes,1999.
[28] M.Deering.Geometric Compression.Proc. SIGGRAPH 1995,13-20.
[29] S.Rusinkiewicz,M.Levoy.Efficient Variants of the ICP Algorithm.Proc.International Conference on 3D Digital Imaging and Modeling(3DIM),2001:145-152.
[30]张俊霞.三维地形可视化及其实时显示方法概论[J].北京测绘,2001,2.
[31] CI.ARK J.Hierarchical geometric models for visible surface algorithms[J]. Communications of the ACM.1976,19(10):547-554.
[32]康凤举.现代仿真技术.北京:国防工业出版社,2001:10-245.
[33] L.A.azdeh著,阮达,黄崇福译,模糊集与模糊信息粒理论[M],北京师范大学出版社, 2000,9.
[34]李道国,苗夺谦,张红云.粒度计算的理论,模型与方法[J].复旦学报自然科学版,2004, (5).
[35]李道国,苗夺谦,张东星等.粒度计算研究综述[J].计算机科学,2005,(9).
[36] L.A.Zadeh.Some reflections on sotf computing,granular computing and their roles in the conception design and utilization of information/intelligent systems[J].Sotf Computing, 1998,2(l):23-25.
[37]王国胤,Rouhg集理论与知识获取[M],西安:西安交通大学出版社,2001.
[38] Pawlak Z. Rough Sets: Theoretical Aspects of Reasoning about Data[M]. Dordrecht: Kluwer Academic Publishers,1991.
[39] Zhang B.,Zhang L.,Theory and Application of Problem Solving[M]. North- Holland, Elsevier Science Publishers B.V.,1992.
[40]张铃,张钹,人工神经网络的学习方法[C],陆汝钤,周志华主编,神经网络及其应用,北京:清华大学出版社,2004,1:35.
[41]张铃,张钹,殷海风,多层前向网络的交叉覆盖算法[J],软件学报,1999,10(7):737-742.
[42]边肇祺,张学工.模式识别[M].北京:清华大学出版社,2000,1.
[43]张尧庭,方开泰.多元统计分析引论[M].北京:科学出版社,1982,6.
[44]卜东波,白硕,李国杰.聚类/分类中的粒度原理[J],计算机学报,2002,25(8):810-816.
[45]谢丰.多视点距离图像的对准和集成方法的研究.硕士学位论文.北京:北京工业大学, 2003.
[46] Rossignac,J,Bowel P.Multi-Resolution 3D approximation for rendering complex scenes [C].In Proceedings of the 2nd Conference Modeling in Computer Graphics:Methods and Applications.Berlin 1993,453-465.
[47] Sclmiitt F,Barsky B,Du,W.-H.An adaptive subdivision method for surface-fitting from sampled data[C].In Proceedings of the Computer Graphics(SIGGRAPH 86).1986,179- 188.
[48] Pauly M,Kobbelt LP,Gross M.Point 2 based multi-scale surface representation[J].ACM Trans on Graphics,2006,25(2):177-193.
[49] Alexa M,Behr J,Cohen-Or D,Fleishman S,Levin D,Silva T.Point Set Surface[C].IEEE Visualization,2001:110-116.
[50] Michale E Agishtein,Alexzander A Migdal.Smooth surface reconstruction from scattered data points.Computer & Graphics,1991,15(1):29-39.
[51] P.Cignoni,C.Montani,R.Scopigno.A Fast Divide and Conquer Delaunay Triangulation Algorithm in Ed.CAD,1998,30(5):333-341.
[52] Kuo CC, Yau HT. Reconstruction of virtual parts from unorganized scanned data for automated dimensional inspection[J]. Comput Inf SciEng (JCISE), Trans ASME.2003, 3(1):76-86.
[53] Aurenhammer F.Voronoi diagrams-a survey of a fundamental geometric data structure. ACM Comput Surv. 1991,23(3):345-405.
[54] David C-S,A greedy Delaunay based surface reconstruction algorithm. Research Report, INRIA.2002.