基于雕刻操作的网格LOD技术的研究
|
摘要
随着数据采集技术的进步,可以得到的数据量越来越大,但是这些大规模的数据给模型的渲染、存储以及传输带来了很大的不便.为了解决这些问题,近年来,提出了很多简化算法来减少数据量,从而根据不同的要求生成不同的网格细节层次(LOD).但是因为数据的几何信息以及拓扑信息的复杂性,各种算法都有其不能解决的问题.本文的算法可以很好地简化拓扑信息很复杂的模型,实现网格LOD.
首先,本文提出了一个适用面更广的网格简化的算法框架从而生成网格LOD:把网格简化分为保拓扑的几何简化和拓扑简化两个过程.通过对几何信息和拓扑信息不同的处理方式,使得对拓扑信息很复杂的网格,简化效果也不错.并且此算法采用算子形式操作,从而实现连续LOD.
其次,本文提出的拓扑简化算法更为直观且有效:基于四面体雕刻操作的简化技术.在拓扑简化的过程中,首先,与传统三角网格和多边形网格表示方式不同,本文采用的是四面体网格.四面体网格不仅具有多边形网格的所有优点,并且四面体网格处理的是体数据,因此处理拓扑信息更加灵活.其次,对雕刻算子,我们从四面体的度,可见性,体积,表面积,外接球的直径以及网格特征等各方面进行了详细的分析和研究,使得通过雕刻算子得到的网格LOD更加合理.最后,我们对LOD生成技术作了进一步地改进和优化,对初始网格进一步简化以及重新三角化,从而进一步简化网格和改善网格质量.同时,我们还提出用更多地保持原始网格明显特征的紧包围盒作初始网格逼近,由紧包围盒.
最后,本文给出了很多例子,通过例子,可以看出,本文的简化算法适用范围更广,可以很好地处理复杂拓扑结构的数据.
The LOD-Mesh has become increasingly important as it has become possible in recent years to create models of greater detail. Such models are notoriously difficult to render, store, and transmit. LOD-Mesh is useful in order to make display, storage, transmission more efficient. Recently, it has developed a lot of algorithms on this problem. It always does not work well when the models have complex geometric and topologic information. We propose a novel method to avoid the problems.
Firstly, we propose a simplification framework which can work well when the model has complex geometric and topologic information to generate LOD-Mesh. The main idea is to divide the simplification algorithm into two steps: geometry simplification and topology simplification. With this method we can simplify models with complex topology. What is more, we can apply this method to get continuous level of detail since we use operators to simplify.
Secondly, we develop a novel topology simplification algorithm using carving operator based on tetrahedron. In this method, first, we use tetrahedral mesh instead of triangular mesh and polygonal mesh. Not only does tetrahedral mesh have all advantages of traditional mesh, but also it can deal with topologic information more flexibly. Second, we analyze the carving operator from the factors, such as the volume, area, diameter of circumsphere and ratio of tetrahedron and features of origin mesh, to make the carving operator more reasonable. Finally, we improve the algorithm through simplifying the initial approximate mesh and remeshing it. We also use cage to be the initial mesh for preserving the origin features of the mesh.
Finally, we give a lot of examples to indicate that our method works well when models have complex geometric and topologic information.
首先,本文提出了一个适用面更广的网格简化的算法框架从而生成网格LOD:把网格简化分为保拓扑的几何简化和拓扑简化两个过程.通过对几何信息和拓扑信息不同的处理方式,使得对拓扑信息很复杂的网格,简化效果也不错.并且此算法采用算子形式操作,从而实现连续LOD.
其次,本文提出的拓扑简化算法更为直观且有效:基于四面体雕刻操作的简化技术.在拓扑简化的过程中,首先,与传统三角网格和多边形网格表示方式不同,本文采用的是四面体网格.四面体网格不仅具有多边形网格的所有优点,并且四面体网格处理的是体数据,因此处理拓扑信息更加灵活.其次,对雕刻算子,我们从四面体的度,可见性,体积,表面积,外接球的直径以及网格特征等各方面进行了详细的分析和研究,使得通过雕刻算子得到的网格LOD更加合理.最后,我们对LOD生成技术作了进一步地改进和优化,对初始网格进一步简化以及重新三角化,从而进一步简化网格和改善网格质量.同时,我们还提出用更多地保持原始网格明显特征的紧包围盒作初始网格逼近,由紧包围盒.
最后,本文给出了很多例子,通过例子,可以看出,本文的简化算法适用范围更广,可以很好地处理复杂拓扑结构的数据.
The LOD-Mesh has become increasingly important as it has become possible in recent years to create models of greater detail. Such models are notoriously difficult to render, store, and transmit. LOD-Mesh is useful in order to make display, storage, transmission more efficient. Recently, it has developed a lot of algorithms on this problem. It always does not work well when the models have complex geometric and topologic information. We propose a novel method to avoid the problems.
Firstly, we propose a simplification framework which can work well when the model has complex geometric and topologic information to generate LOD-Mesh. The main idea is to divide the simplification algorithm into two steps: geometry simplification and topology simplification. With this method we can simplify models with complex topology. What is more, we can apply this method to get continuous level of detail since we use operators to simplify.
Secondly, we develop a novel topology simplification algorithm using carving operator based on tetrahedron. In this method, first, we use tetrahedral mesh instead of triangular mesh and polygonal mesh. Not only does tetrahedral mesh have all advantages of traditional mesh, but also it can deal with topologic information more flexibly. Second, we analyze the carving operator from the factors, such as the volume, area, diameter of circumsphere and ratio of tetrahedron and features of origin mesh, to make the carving operator more reasonable. Finally, we improve the algorithm through simplifying the initial approximate mesh and remeshing it. We also use cage to be the initial mesh for preserving the origin features of the mesh.
Finally, we give a lot of examples to indicate that our method works well when models have complex geometric and topologic information.
引文
[1] C.B. Barber, D.P. Dobkin, and H. Huhdanpaa. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22(4):469-483, 1996.
[2] J.H. Clark. Hierarchical geometric models for visible surface algorithms. Communications of the ACM. vol. 19(10). pp. 547-554, 1976.
[3] L.P. Chew, Constrained Delaunay triangulations. Algorithmica 4(1), 97-108, 1989.
[4] X. Decoret, F. Durand, F. X. Sillion, and J. Dorsey, Billboard clouds for extreme model simplification. ACM Transactions on Graphics 22, 3, 689-696, 2003.
[5] J. El-Sana and A. Varshney. Topology simplification for polygonal virtual environments. IEEE Transactions on Visualization and Computer Graphics. Vol. 4(2).pp. 133-144, 1998.
[6] J. El-Sana and A. Varshney. View-Dependent topology simplification. Proceedings of Virtual Environments'99, 1999.
[7] M. Garland and P. Heckber. Surface simplification using quadric error metrics. Proceedings of SIGGRAP'97, 209-216, 1997.
[8] H. Hoppe. Progressive meshes. Computer Graphics. Proceedings of SIGGRAPH'96, 99-108, 1996.
[9] H. Hoppe. View-dependent refinement of progressive meshes. CG (SIGGRAPH '97 Proceedings), 1997.
[10] T. He, L. Hong, A. Varshney, and S. Wang. Controlled topology simplification. IEEE Transactions on Visualization and Computer Graphics. Vol. 2(2). pp. 171-184, 1996.
[11] B. Hamann. Curvature approximation for 3D manifolds in 4D space. Computer Aided Geometric, 11(6). 621-632, 1994.
[12] N. Hegbi and J. El-Sana. A Carving framework for topology simplification of polygon meshes. Geometric Modeling and Processing, 2008.
[13] D. Luebke, M. Reddy, J.D. Cohen, A. Varshney, B. Watson, and R. Huebner. Level of detail for 3D graphics. Published by Morgan Kaufmann as part of their series in Computer Graphics and Geometric Modeling. ISBN 1-55860-838-9, 2003.
[14] D. Luebke. A Developer's Survey of polygonal simplification algorithms. IEEE Computer Graphics and Applications. Vol. 32(13). pp. 753-772, 2000.
[15] Y. Lipman, J. Kopf, D. Cohen-Or, and D. Levin. GPU-assisted positive mean value coordinates for mesh deformations. Eurographics Symposium on Geometry Processing, 2007.
[16] F. Nooruddin and G. Turk. Simplification and repair of polygonal models using volumetric techniques. Technical Report GIT-GVU-99-37. Georgia Institute of Technology, Atlanta, GA, 1999.
[17] J. Rossignac and P. Borrel. Multi-resolution 3D approximations for rendering complex scenes. Geometric Modeling in Computer Graphics. New York: Springer Verlag: 455-465, 1993.
[18] W. Schroeder, J. Zarge, and W. Lorensen. Decimation of triangle meshes. Proceedings of SIGGRAPH'92, Computer Graphics, 26(2). 65-70, 1992.
[19] H. Si, TetGen. A quality tetrahedral mesh generator and three-dimensional Delaunay triangulator. Version 1.4. User's Manual, 2006. http://tetgen.berlios.de
[20] J.R. Shewchuk, Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations. In: Proceedings of the Sixteenth Annual Symposium on Computational Geometry, pp. 350-208, 2000.
[21] J.R. Shewchuk, General-Dimensional constrained Delaunay and constrained regular triangulations I: Combinatorial Properties. To appear in Discrete and Computational Geometry, 2005.
[22] S. Valette and J.M. Chassery. Approximated Centroidal Voronoi Diagrams for uniform polygonal mesh coarsening. Eurographics 2004.
[23] Z. Wood, H. Hoppe, M. Desbrun, and P. Schroder. Removing excess topology from isosurfaces. ACM Transactions on Graphics 23(2), 190-208, 2004.
[2] J.H. Clark. Hierarchical geometric models for visible surface algorithms. Communications of the ACM. vol. 19(10). pp. 547-554, 1976.
[3] L.P. Chew, Constrained Delaunay triangulations. Algorithmica 4(1), 97-108, 1989.
[4] X. Decoret, F. Durand, F. X. Sillion, and J. Dorsey, Billboard clouds for extreme model simplification. ACM Transactions on Graphics 22, 3, 689-696, 2003.
[5] J. El-Sana and A. Varshney. Topology simplification for polygonal virtual environments. IEEE Transactions on Visualization and Computer Graphics. Vol. 4(2).pp. 133-144, 1998.
[6] J. El-Sana and A. Varshney. View-Dependent topology simplification. Proceedings of Virtual Environments'99, 1999.
[7] M. Garland and P. Heckber. Surface simplification using quadric error metrics. Proceedings of SIGGRAP'97, 209-216, 1997.
[8] H. Hoppe. Progressive meshes. Computer Graphics. Proceedings of SIGGRAPH'96, 99-108, 1996.
[9] H. Hoppe. View-dependent refinement of progressive meshes. CG (SIGGRAPH '97 Proceedings), 1997.
[10] T. He, L. Hong, A. Varshney, and S. Wang. Controlled topology simplification. IEEE Transactions on Visualization and Computer Graphics. Vol. 2(2). pp. 171-184, 1996.
[11] B. Hamann. Curvature approximation for 3D manifolds in 4D space. Computer Aided Geometric, 11(6). 621-632, 1994.
[12] N. Hegbi and J. El-Sana. A Carving framework for topology simplification of polygon meshes. Geometric Modeling and Processing, 2008.
[13] D. Luebke, M. Reddy, J.D. Cohen, A. Varshney, B. Watson, and R. Huebner. Level of detail for 3D graphics. Published by Morgan Kaufmann as part of their series in Computer Graphics and Geometric Modeling. ISBN 1-55860-838-9, 2003.
[14] D. Luebke. A Developer's Survey of polygonal simplification algorithms. IEEE Computer Graphics and Applications. Vol. 32(13). pp. 753-772, 2000.
[15] Y. Lipman, J. Kopf, D. Cohen-Or, and D. Levin. GPU-assisted positive mean value coordinates for mesh deformations. Eurographics Symposium on Geometry Processing, 2007.
[16] F. Nooruddin and G. Turk. Simplification and repair of polygonal models using volumetric techniques. Technical Report GIT-GVU-99-37. Georgia Institute of Technology, Atlanta, GA, 1999.
[17] J. Rossignac and P. Borrel. Multi-resolution 3D approximations for rendering complex scenes. Geometric Modeling in Computer Graphics. New York: Springer Verlag: 455-465, 1993.
[18] W. Schroeder, J. Zarge, and W. Lorensen. Decimation of triangle meshes. Proceedings of SIGGRAPH'92, Computer Graphics, 26(2). 65-70, 1992.
[19] H. Si, TetGen. A quality tetrahedral mesh generator and three-dimensional Delaunay triangulator. Version 1.4. User's Manual, 2006. http://tetgen.berlios.de
[20] J.R. Shewchuk, Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations. In: Proceedings of the Sixteenth Annual Symposium on Computational Geometry, pp. 350-208, 2000.
[21] J.R. Shewchuk, General-Dimensional constrained Delaunay and constrained regular triangulations I: Combinatorial Properties. To appear in Discrete and Computational Geometry, 2005.
[22] S. Valette and J.M. Chassery. Approximated Centroidal Voronoi Diagrams for uniform polygonal mesh coarsening. Eurographics 2004.
[23] Z. Wood, H. Hoppe, M. Desbrun, and P. Schroder. Removing excess topology from isosurfaces. ACM Transactions on Graphics 23(2), 190-208, 2004.