三维空间的拓扑可视化和多面体快速变形
|
摘要
计算机图形学中一个重要的研究对象就是三维空间对象。凭借着良好的视觉效果和广泛的应用领域,无论是科学研究还是经济需要,三维空间的拓扑可视化和多面体变形一直是该领域的研究焦点,越来越受到大家的青睐。
本文在分析可视化和变形的基本技术的基础上逐步延伸,讨论了一种新的拓扑可视化方法,并提出一种基于连通性转换的多面体快速变形方法。
在可视化部分,本文研究了基于莫尔斯理论的离散梯度向量域的构建方法,并尝试性的将其应用于拓扑可视化。用该方法和流形可视化方法分别演示了Moebius带和海螺,并做了分析和对比。从论文最终研究目的角度出发,结合实践,介绍了相关理论和离散梯度向量域构造过程,并完成向量域的可视化。实验结果表明了该方法的有效性。
对于三维多面体变形,提高变形速度一直是一个关键问题。本文研究了连通性转换方法,并将其应用于三维多面体的快速变形。采用优先权控制函数控制模型特征,实现点和边的同步处理。通过预先安排连通性转换提高了变形速度,通过解一个稀疏线性方程组缩短变形片的嵌入时间。之后,通过矫正特征点以及边界处理得到平滑的变形序列。本文用该方法和传统变形方法分别演示了三维多面体模型的变形实例,并对实验结果和相关数据进行了分析比较。实验结果表明,该变形方法可快速实现平滑变形。
The 3D object is an important aspect in the computer graphics. For the preferable vision purpose and the broad application purpose, whether for science research or economic requirement, the technology of visualizing and morphing of 3D object is always the focus in this domain,and it is becoming a favorite focus.
In this article, we have analyzed the basic technologies of visualization and metamorphosis. This thesis discussed a new method of visualization, and then presented a fast metamorphosis technology based on the connectivity transformation.
During the processing of 3D visualizing, the discrete gradient vector filed based on the Morse theory is presented, and is applied to visualization of topologies. This method and another flow-visualization way are respectively demonstrated with the Moebius strap and the trumpet shell, the analysis and the compare are presented. Considering our ultimate research purpose and practicality, the correlative theories are introduced first and then to construct the discrete gradient vector field. Finally the vector filed is visualized, and experiments show the availability of the result.
As for the fast metamorphosis of 3D polyhedral models, advancing the speed of metamorphosis is always a key issue. The connectivity transformations were presented, and were applied to the fast metamorphosis of polyhedral. In order to controls the both models’features in the process of metamorphosis, the priority control function was used to handle both vertex and edge at the same time. The scheduling connectivity transformations operation advanced the speed of morphing. A sparse linear system decreased the time of embedding patches. In addition, it took advantages of shape smooth by using rectifying feature points and boundary handling in the morphing sequence. This fast morphing method and the former morphing measure were respectively demonstrated with the metamorphosis of 3D polyhedral models. Furthermore, the result analysis was given. The experiment results show that this method can implement fast and smooth metamorphosis.
本文在分析可视化和变形的基本技术的基础上逐步延伸,讨论了一种新的拓扑可视化方法,并提出一种基于连通性转换的多面体快速变形方法。
在可视化部分,本文研究了基于莫尔斯理论的离散梯度向量域的构建方法,并尝试性的将其应用于拓扑可视化。用该方法和流形可视化方法分别演示了Moebius带和海螺,并做了分析和对比。从论文最终研究目的角度出发,结合实践,介绍了相关理论和离散梯度向量域构造过程,并完成向量域的可视化。实验结果表明了该方法的有效性。
对于三维多面体变形,提高变形速度一直是一个关键问题。本文研究了连通性转换方法,并将其应用于三维多面体的快速变形。采用优先权控制函数控制模型特征,实现点和边的同步处理。通过预先安排连通性转换提高了变形速度,通过解一个稀疏线性方程组缩短变形片的嵌入时间。之后,通过矫正特征点以及边界处理得到平滑的变形序列。本文用该方法和传统变形方法分别演示了三维多面体模型的变形实例,并对实验结果和相关数据进行了分析比较。实验结果表明,该变形方法可快速实现平滑变形。
The 3D object is an important aspect in the computer graphics. For the preferable vision purpose and the broad application purpose, whether for science research or economic requirement, the technology of visualizing and morphing of 3D object is always the focus in this domain,and it is becoming a favorite focus.
In this article, we have analyzed the basic technologies of visualization and metamorphosis. This thesis discussed a new method of visualization, and then presented a fast metamorphosis technology based on the connectivity transformation.
During the processing of 3D visualizing, the discrete gradient vector filed based on the Morse theory is presented, and is applied to visualization of topologies. This method and another flow-visualization way are respectively demonstrated with the Moebius strap and the trumpet shell, the analysis and the compare are presented. Considering our ultimate research purpose and practicality, the correlative theories are introduced first and then to construct the discrete gradient vector field. Finally the vector filed is visualized, and experiments show the availability of the result.
As for the fast metamorphosis of 3D polyhedral models, advancing the speed of metamorphosis is always a key issue. The connectivity transformations were presented, and were applied to the fast metamorphosis of polyhedral. In order to controls the both models’features in the process of metamorphosis, the priority control function was used to handle both vertex and edge at the same time. The scheduling connectivity transformations operation advanced the speed of morphing. A sparse linear system decreased the time of embedding patches. In addition, it took advantages of shape smooth by using rectifying feature points and boundary handling in the morphing sequence. This fast morphing method and the former morphing measure were respectively demonstrated with the metamorphosis of 3D polyhedral models. Furthermore, the result analysis was given. The experiment results show that this method can implement fast and smooth metamorphosis.
引文
1石教英,蔡文立.《科学计算可视化算法与系统》[M].北京:北京科学出版社,2004
2刘凯,信息可视化概念的深入探讨[J]. journal of information, 2004,12(12):20-25
3许寒,刘希顺.三维空间规则数据场体可视化系统设计[J].计算机应用研究,2003,1(1):96-99
4李梅.信息可视化系统概述[Z]. http :/ / www2. ccw. com. cn/ 04/ 0411/ b/0411b85-3. asp
5詹德川,周志华.基于集成的流形学习可视化[J].计算机研究与发展,2005:42(9):1533-1537
6徐森林.《微分拓扑》[M].天津:天津教育出版社,2004
7 Hong T,Thalmann N M,Thalmann D Ageneral.Algorithm for 3-D shape interpolation inafacet based representation [J].In:Crow F C,ed.Proceedings of the Graphics Interface'88.Edmonton:Morgan Kaufmann Publishers,Inc,1988.229-235
8 Kent J R,Carlson W E,Parent R E.Shape transition for polyhedral objects[J].Computer Graphics,1992,26(2):47-54
9 Bao Hu-jun,Peng Qun-sheng.Interactive 3D morphing[C].In:Rockwood,A.,ed.Proceedings of the SIGGRAPH'99 Conference.LisbonPortugal:BlackwellLtd,1998:23-30
10 Lee A W F,Dobkin D,Sweldens W.Multiresolution mesh morphing[C].T Brown,J R,ed.Proceedings of the Eurographics'91.LosAngeles:ACMPress,1999:343-350
11 Kaul A,Rossignac J.Solid-Interpolating deformations:construction and animation of PIPs[C].In:Rossignac J,Sillion F,eds.Proceedings of the Eurographics'96.Vienna:BlackwellL td,1991:493-506
12 Galin E,Akkouche S.Blob metamorphosis based on Minkovskisums[C].Proceedings of the Eurographics'96.Poitiers:BlackwellL td,1996:143-154
13 Payne B,Toga A.Distance field manipulation of surface models[J].IEEE Transactions on Computer Graphics & Applications,1992,12(1):65-71
14 Daniel Cohen-Or,Levin D,Solomovici A.Three-Dimensional distance field metamorphosis[J].ACM Transactions on Graphics,1998,17(2):116-141
15尹学松,张谦.四种体绘制算法的分析与评价[J].计算机工程与应用,2004,16(8):97-100
16 Taponecco F,Alexa M.Vector field visualization using Markovrandom field texture synthesis[J].Proceedings of IEEE TCVG Symposium on Visualization,Grenoble,2003:195-202
17 Sundquist A.Dynamic line integral convolution for visualizing streamline evolution[J].IEEE Transactions on Visualization and Computer Graphics,2003,9 (3):273-282
18 Post S H,Vrol B,Hauser H.The state of the art inflow visualization:Feature extracting and tracking[J].Computer Graphics Forum,2003,22(4):775-792
19 van J J.Image based flow visualization[J].ACM Transactions on Graphics,2002,21(3):745-754
20 S T Roweis,K S Lawrance.Nonlinear dimensionality reduction by locally linear embedding.Science[J].IEEE Transactions on Visualization and Computer Graphics,2000,290(5500 ):2323-2326
21 M Balasubramanian,E L Schwartz,,J B Tenenbaum.The Isomap algorithm and topological stability[J].Science, 2002,295(4):7a
22 M Belkin,P Niyogi.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation,2001,151(6):1373-1396
23 Forsey D R,Bartels R H.surface fitting with hierarchical splines[J].ACM Trans.On Graphics,1995,14(2):134-161
24 BarrA H.Global,local deformation of solid p rimitives.ACM Comp[J].Graph,1984,18(3):21-30
25 Sederberg T W,Parry S R.Freeform deformation of solid geometric models[J].ACMComp.Graph.,1986,20(4):151-160
26 Hsu W M,et al.Direct manipulation of freeform deformation[J].ACM Comp.Graph.,1992,26(2): 177-184
27 Coquillart S.Extended freeform deformation:a sculpturing tool for 3D geometric modeling[J].ACM Comp.Graph.,1990,4:187-196
28 Kalra P,Mangili A,Thalmann N M,Thalmann D.Simulation of facial muscle actors based on rational freeform deformation[J].Comp Graph Forum,1992,2(3):59-69
29 Lamousin H J,Waggenspack W N.NURBS based freeform deformation.IEEE Comp[J].Grap and Appl,1994,11:59-65
30 Feng J Q,et al.A new freeform deformation through the control of parametric surfaces[J].Computer & Graphics,1996,20(4):531-539
31 Singh K,Fiume E.Wires:a geometric deformation technique[J].In: Proc of the ACM SIGRAPH′98,1998
32 Hong T,Thalmann,N M,Thalmann D.A general algorithm for 3D shape interpolation in a face based representation[J].In:Crow F C,ed.Proceedings of the Graphics Interface’88.Edmonton: Morgan Kaufmann Publishers,Inc,1988.229-235
33 Chadwich J E,Haumann D R,Parent R E.Layered const ruction for deformable animated characters[J].ACM Computer Graphics,1989,23(3):243-252
34 Cohen Or D,Levin D,So lomovici A.Three dimensional distance field metamorphosis[J].ACM Transactions on Graphics,1998,17(2):116-141
35 Mac Cracken R,Joy K.Freeform deformation with lattices of arbitrary topology[C].In:Proc of the SIGGRAPH′96,Computer Graphics Proc,Annual Conf Series,ACM Press/ACM SIGGRAPH,1996
36 Bechmann D,Bertrand Y,Ther S.Continuous free form deformation[J].Computer Networks and ISDN System,1997,29(14):1715-1725
37方向,鲍虎军,彭群生.可控的三维morphing[J].软件学报,2001,12(6):856-863
38 Sun Y F,Nee A Y,Lee K S.Modifying freeformed NURBS curves and surfaces for off setting without local self intersection[J].Computer Aided Design,2004,36 (12):1161-1169
39方向,鲍虎军,王平安,彭群生.基于任意骨架的隐式曲面造型技术[J].软件学报,2000,11(9):1214-1220
40 Turk G,O’Brien J.Shape transformation using variational implicit functions[J].In:Rockwood A ed.S IGGRA PH’99 Conference Proceedings.Los Angeles:ACM Press,1999.335-342
41 T Lewiner.Constructing Discrete Morse Functions[J].MS thesis,2002,6(6):44-56
42 T Lewiner,H Lopes,G Tavares.Applications of Forman’s Discrete Morse Theory to Topology Visualization and Mesh Compression[J].IEEE Computer Graphics and Applications,2004,5(10):499-508
43 T K Dey,H Edesbrunner,S Guha. Computational Topology[J].Advances in Discrete and Computational Geometry,1999,3(6):109-143
44 T Lewiner,H Lopes,Gavares.Toward Optimality in Discrete Morse Theory[J].Experimental Math,2003,3(12):271-285
45 R Forman,A discrete Mores Theory Functions[J].Advances in Math,2002,4(4):66-78
46李元熹,张国梁.拓扑学[M].上海:上海科学技术出版社,2001
47斯蒂芬巴尔.《拓扑实验》[M].上海:上海教育出版社,2003
48 Fan H T,Liu Hong and Dong W.Conservative overlapping grid generation in supersonic viscous flow over complex geometry[J].FEDSM 99-6793,Proceedings of 3rd ASME / JSMEJoint Fluids Engineering Conference,July,1999
49李清泉,杨必胜.三维空间数据的实时获取建模与可视化[M].武汉:武汉大学出版社,2003
50吴信才.地理信息系统原理与方法[M].北京:电子工业出版社,2002.224-226
51 Chao-Hung Lin,Tong-Yee Lee.Metamorphosis of 3D Polyhedral Models UsingProgressive Connectivity Transformations[J],IEEE Trans.Visualization and Computer Graphics, 2005, 6(11):2-12
52 T Michikawa,T Kanai,M Fujita.MultiresolutionInterpolation Meshes[J],Proc Ninth Pacific Graphics Int’l Conf.(Pacific Graphics 2001),2001,10:60-69
53 A Gregory,A State, M Lin,D Manocha. Interactive Surface Decomposition for Polyhedra Morphing[J],TheVisual Computer,1999,9(15):453-470
54 S Hanke,T Ottmann,S Schuierer.The Edge-FlippingDistance of Triangulations[J],J Universal Computer Science,1996,8(8):570-579
55 Malte Zockler,Detlev Stalliing,Hans-Christian Hege.Fast and Intuitive Generation of Geometric Shape Transitions[J],Konrad-Zuse-Zentrum Informationstechnik Berlin,1999,9(9):1-20
56 S Shlafman,A Tal,S Katz.Metamorphosis of PolyhedralSurfaces Using Decomposition[J],Eurographics, 2002,3(3):219-228
57 M Alexa,Merging Polyhedral Shapes with Scattered Features[J],The Visual Computer,2000,1(1):26-37
58 T Y Lee,P H Hung.Fast and Intuitive Metamorphosis of 3D Polyhedral Models Using SMCC Mesh Merging Scheme[J],IEEE Trans Visualization and Computer Graphics,2003,5(9):85-98
2刘凯,信息可视化概念的深入探讨[J]. journal of information, 2004,12(12):20-25
3许寒,刘希顺.三维空间规则数据场体可视化系统设计[J].计算机应用研究,2003,1(1):96-99
4李梅.信息可视化系统概述[Z]. http :/ / www2. ccw. com. cn/ 04/ 0411/ b/0411b85-3. asp
5詹德川,周志华.基于集成的流形学习可视化[J].计算机研究与发展,2005:42(9):1533-1537
6徐森林.《微分拓扑》[M].天津:天津教育出版社,2004
7 Hong T,Thalmann N M,Thalmann D Ageneral.Algorithm for 3-D shape interpolation inafacet based representation [J].In:Crow F C,ed.Proceedings of the Graphics Interface'88.Edmonton:Morgan Kaufmann Publishers,Inc,1988.229-235
8 Kent J R,Carlson W E,Parent R E.Shape transition for polyhedral objects[J].Computer Graphics,1992,26(2):47-54
9 Bao Hu-jun,Peng Qun-sheng.Interactive 3D morphing[C].In:Rockwood,A.,ed.Proceedings of the SIGGRAPH'99 Conference.LisbonPortugal:BlackwellLtd,1998:23-30
10 Lee A W F,Dobkin D,Sweldens W.Multiresolution mesh morphing[C].T Brown,J R,ed.Proceedings of the Eurographics'91.LosAngeles:ACMPress,1999:343-350
11 Kaul A,Rossignac J.Solid-Interpolating deformations:construction and animation of PIPs[C].In:Rossignac J,Sillion F,eds.Proceedings of the Eurographics'96.Vienna:BlackwellL td,1991:493-506
12 Galin E,Akkouche S.Blob metamorphosis based on Minkovskisums[C].Proceedings of the Eurographics'96.Poitiers:BlackwellL td,1996:143-154
13 Payne B,Toga A.Distance field manipulation of surface models[J].IEEE Transactions on Computer Graphics & Applications,1992,12(1):65-71
14 Daniel Cohen-Or,Levin D,Solomovici A.Three-Dimensional distance field metamorphosis[J].ACM Transactions on Graphics,1998,17(2):116-141
15尹学松,张谦.四种体绘制算法的分析与评价[J].计算机工程与应用,2004,16(8):97-100
16 Taponecco F,Alexa M.Vector field visualization using Markovrandom field texture synthesis[J].Proceedings of IEEE TCVG Symposium on Visualization,Grenoble,2003:195-202
17 Sundquist A.Dynamic line integral convolution for visualizing streamline evolution[J].IEEE Transactions on Visualization and Computer Graphics,2003,9 (3):273-282
18 Post S H,Vrol B,Hauser H.The state of the art inflow visualization:Feature extracting and tracking[J].Computer Graphics Forum,2003,22(4):775-792
19 van J J.Image based flow visualization[J].ACM Transactions on Graphics,2002,21(3):745-754
20 S T Roweis,K S Lawrance.Nonlinear dimensionality reduction by locally linear embedding.Science[J].IEEE Transactions on Visualization and Computer Graphics,2000,290(5500 ):2323-2326
21 M Balasubramanian,E L Schwartz,,J B Tenenbaum.The Isomap algorithm and topological stability[J].Science, 2002,295(4):7a
22 M Belkin,P Niyogi.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation,2001,151(6):1373-1396
23 Forsey D R,Bartels R H.surface fitting with hierarchical splines[J].ACM Trans.On Graphics,1995,14(2):134-161
24 BarrA H.Global,local deformation of solid p rimitives.ACM Comp[J].Graph,1984,18(3):21-30
25 Sederberg T W,Parry S R.Freeform deformation of solid geometric models[J].ACMComp.Graph.,1986,20(4):151-160
26 Hsu W M,et al.Direct manipulation of freeform deformation[J].ACM Comp.Graph.,1992,26(2): 177-184
27 Coquillart S.Extended freeform deformation:a sculpturing tool for 3D geometric modeling[J].ACM Comp.Graph.,1990,4:187-196
28 Kalra P,Mangili A,Thalmann N M,Thalmann D.Simulation of facial muscle actors based on rational freeform deformation[J].Comp Graph Forum,1992,2(3):59-69
29 Lamousin H J,Waggenspack W N.NURBS based freeform deformation.IEEE Comp[J].Grap and Appl,1994,11:59-65
30 Feng J Q,et al.A new freeform deformation through the control of parametric surfaces[J].Computer & Graphics,1996,20(4):531-539
31 Singh K,Fiume E.Wires:a geometric deformation technique[J].In: Proc of the ACM SIGRAPH′98,1998
32 Hong T,Thalmann,N M,Thalmann D.A general algorithm for 3D shape interpolation in a face based representation[J].In:Crow F C,ed.Proceedings of the Graphics Interface’88.Edmonton: Morgan Kaufmann Publishers,Inc,1988.229-235
33 Chadwich J E,Haumann D R,Parent R E.Layered const ruction for deformable animated characters[J].ACM Computer Graphics,1989,23(3):243-252
34 Cohen Or D,Levin D,So lomovici A.Three dimensional distance field metamorphosis[J].ACM Transactions on Graphics,1998,17(2):116-141
35 Mac Cracken R,Joy K.Freeform deformation with lattices of arbitrary topology[C].In:Proc of the SIGGRAPH′96,Computer Graphics Proc,Annual Conf Series,ACM Press/ACM SIGGRAPH,1996
36 Bechmann D,Bertrand Y,Ther S.Continuous free form deformation[J].Computer Networks and ISDN System,1997,29(14):1715-1725
37方向,鲍虎军,彭群生.可控的三维morphing[J].软件学报,2001,12(6):856-863
38 Sun Y F,Nee A Y,Lee K S.Modifying freeformed NURBS curves and surfaces for off setting without local self intersection[J].Computer Aided Design,2004,36 (12):1161-1169
39方向,鲍虎军,王平安,彭群生.基于任意骨架的隐式曲面造型技术[J].软件学报,2000,11(9):1214-1220
40 Turk G,O’Brien J.Shape transformation using variational implicit functions[J].In:Rockwood A ed.S IGGRA PH’99 Conference Proceedings.Los Angeles:ACM Press,1999.335-342
41 T Lewiner.Constructing Discrete Morse Functions[J].MS thesis,2002,6(6):44-56
42 T Lewiner,H Lopes,G Tavares.Applications of Forman’s Discrete Morse Theory to Topology Visualization and Mesh Compression[J].IEEE Computer Graphics and Applications,2004,5(10):499-508
43 T K Dey,H Edesbrunner,S Guha. Computational Topology[J].Advances in Discrete and Computational Geometry,1999,3(6):109-143
44 T Lewiner,H Lopes,Gavares.Toward Optimality in Discrete Morse Theory[J].Experimental Math,2003,3(12):271-285
45 R Forman,A discrete Mores Theory Functions[J].Advances in Math,2002,4(4):66-78
46李元熹,张国梁.拓扑学[M].上海:上海科学技术出版社,2001
47斯蒂芬巴尔.《拓扑实验》[M].上海:上海教育出版社,2003
48 Fan H T,Liu Hong and Dong W.Conservative overlapping grid generation in supersonic viscous flow over complex geometry[J].FEDSM 99-6793,Proceedings of 3rd ASME / JSMEJoint Fluids Engineering Conference,July,1999
49李清泉,杨必胜.三维空间数据的实时获取建模与可视化[M].武汉:武汉大学出版社,2003
50吴信才.地理信息系统原理与方法[M].北京:电子工业出版社,2002.224-226
51 Chao-Hung Lin,Tong-Yee Lee.Metamorphosis of 3D Polyhedral Models UsingProgressive Connectivity Transformations[J],IEEE Trans.Visualization and Computer Graphics, 2005, 6(11):2-12
52 T Michikawa,T Kanai,M Fujita.MultiresolutionInterpolation Meshes[J],Proc Ninth Pacific Graphics Int’l Conf.(Pacific Graphics 2001),2001,10:60-69
53 A Gregory,A State, M Lin,D Manocha. Interactive Surface Decomposition for Polyhedra Morphing[J],TheVisual Computer,1999,9(15):453-470
54 S Hanke,T Ottmann,S Schuierer.The Edge-FlippingDistance of Triangulations[J],J Universal Computer Science,1996,8(8):570-579
55 Malte Zockler,Detlev Stalliing,Hans-Christian Hege.Fast and Intuitive Generation of Geometric Shape Transitions[J],Konrad-Zuse-Zentrum Informationstechnik Berlin,1999,9(9):1-20
56 S Shlafman,A Tal,S Katz.Metamorphosis of PolyhedralSurfaces Using Decomposition[J],Eurographics, 2002,3(3):219-228
57 M Alexa,Merging Polyhedral Shapes with Scattered Features[J],The Visual Computer,2000,1(1):26-37
58 T Y Lee,P H Hung.Fast and Intuitive Metamorphosis of 3D Polyhedral Models Using SMCC Mesh Merging Scheme[J],IEEE Trans Visualization and Computer Graphics,2003,5(9):85-98