三角网格处理中若干算法研究及其应用
|
摘要
以三角平面网格建构三维实体模型在目前的三维造型领域发挥着越来越重要的作用，针对三角网格处理中模型显示、模型修改和模型简化这三个基础算法，将拓扑映射引入到模型显示处理，将区域搜索引入到模型切割，将夹角判断引入到网格简化，提出了新的高效算法。
通过将拓扑映射引入到背向面去除判断中，将三维向量的空间角度关系判断转化成二维平面上投影向量的角度判断，然后再转化成一维射影直线上映射点的位置判断。并根据网格法向量的拓扑映射点将其分成数个区域，对一个区域内的所有网格进行整体判断，进一步减少了计算量。
针对传统网格曲面切割中需要手工确定待切割曲面区域边界曲线或曲面的步骤，提出了一个新的较简便的曲面切割算法。根据内部或外部的种子网格顶点搜索出指定点所在的最小连通区域内的全部顶点，区域的边界切割线也由边界网格边上的切割线搜索得出。最后根据所在区域的网格信息和边界切割线，将其切割成新的曲面。将该算法运用于软件的实际操作中，可大大提高人机交互的友好性，且效率较高。
提出并实现了一个以依赖于视点的网格简化框架为基础的，运用顶点去除方法进行网格简化的算法。首先定义每个网格顶点上由该点和与其周围相邻顶点所形成的平均方向向量，然后根据方向向量和从该顶点指向周围网格各个重心点的向量的平均夹角来识别和简化网格中的平面区域，保留特征顶点，进而保持物体的视觉特征。在顶点去除后，还需要对因此而形成的多边形进行三角形重建，以填补空洞。
最后，介绍了在已开发完成的计算机辅助服装设计系统中，本文的研究成果在衣物模型显示、衣料立体裁剪和衣物模型简化三个主要功能上的应用。
In current 3D modeling research area, generating solid model by triangular mesh is becoming more and more important. According to three basic algorithms: model rendering, model modification and model simplification in mesh operations, new and efficiency algorithms are presented. Topological mapping is introduced into backface culling, region search is introduced into mesh trimming, vector angle is introduced into mesh simplification.
Angle comparison of two vectors in three dimensional space is converted to that of two projected vectors in two dimensional plane, then to two mapped points in one dimensional projection line. We partition the normal space by symmetrically subdividing the surface of a unit sphere. For each polygon, we can determine the cells it located according to the position of its mapping coordinates. In each cell, we compute all normals' topological mapping coordinates on the bounding plane.
By one specified point on the model surface, boundaries of the selected patch in form as closed cutting line loops are automatically found out, and all the vertexes and faces in the patch are also confirmed. According to this information about the selected patch, new mesh is generated.
We address a method for 3D triangular mesh simplification with vector average angle. The vector is made by the vertex and all the vertexes around it. And the average angle is calculated by the vector and all neighbor triangles' center of gravity. We decide the area is flat or not by the vertex's average angle, if the area is flat, the vertex will be deleted and the polygon will be re-triangulated.
All the researches are integrated in 3D garment design system.
通过将拓扑映射引入到背向面去除判断中，将三维向量的空间角度关系判断转化成二维平面上投影向量的角度判断，然后再转化成一维射影直线上映射点的位置判断。并根据网格法向量的拓扑映射点将其分成数个区域，对一个区域内的所有网格进行整体判断，进一步减少了计算量。
针对传统网格曲面切割中需要手工确定待切割曲面区域边界曲线或曲面的步骤，提出了一个新的较简便的曲面切割算法。根据内部或外部的种子网格顶点搜索出指定点所在的最小连通区域内的全部顶点，区域的边界切割线也由边界网格边上的切割线搜索得出。最后根据所在区域的网格信息和边界切割线，将其切割成新的曲面。将该算法运用于软件的实际操作中，可大大提高人机交互的友好性，且效率较高。
提出并实现了一个以依赖于视点的网格简化框架为基础的，运用顶点去除方法进行网格简化的算法。首先定义每个网格顶点上由该点和与其周围相邻顶点所形成的平均方向向量，然后根据方向向量和从该顶点指向周围网格各个重心点的向量的平均夹角来识别和简化网格中的平面区域，保留特征顶点，进而保持物体的视觉特征。在顶点去除后，还需要对因此而形成的多边形进行三角形重建，以填补空洞。
最后，介绍了在已开发完成的计算机辅助服装设计系统中，本文的研究成果在衣物模型显示、衣料立体裁剪和衣物模型简化三个主要功能上的应用。
In current 3D modeling research area, generating solid model by triangular mesh is becoming more and more important. According to three basic algorithms: model rendering, model modification and model simplification in mesh operations, new and efficiency algorithms are presented. Topological mapping is introduced into backface culling, region search is introduced into mesh trimming, vector angle is introduced into mesh simplification.
Angle comparison of two vectors in three dimensional space is converted to that of two projected vectors in two dimensional plane, then to two mapped points in one dimensional projection line. We partition the normal space by symmetrically subdividing the surface of a unit sphere. For each polygon, we can determine the cells it located according to the position of its mapping coordinates. In each cell, we compute all normals' topological mapping coordinates on the bounding plane.
By one specified point on the model surface, boundaries of the selected patch in form as closed cutting line loops are automatically found out, and all the vertexes and faces in the patch are also confirmed. According to this information about the selected patch, new mesh is generated.
We address a method for 3D triangular mesh simplification with vector average angle. The vector is made by the vertex and all the vertexes around it. And the average angle is calculated by the vector and all neighbor triangles' center of gravity. We decide the area is flat or not by the vertex's average angle, if the area is flat, the vertex will be deleted and the polygon will be re-triangulated.
All the researches are integrated in 3D garment design system.
引文
[1] S. Kumar, D. Manocha, B. Garrett, M. Lin. Hierarchical Back-face Culling. In 7th Eurographics Workshop on Rendering. pages 231-240, 1996.
[2] Johannsen. A. and Carter, M. B. "Clustered Backface Culling". Journal of Graphics Tools 3, 1(1998), 1-14.
[3] Zhang, H. and Hoff Ⅲ, K. Fast Backface Culling Using Normal Masks. In Proc. Symposium on Interactive 3D Graphics, 1997, pages 103-106.
[4] Casale. M.S., Bobrow. J.E. Solid Modeling Using Parametric Surfaces Defined Over Non-Square Domains. Eighth International Conference on Off-shore Mechanics and Arctic Engineering. March 1989, pages.231-236.
[5] Casale, M.S., Bobrow, J.E, The Analysis of Solids Without Mesh Generation Using Trimmed Patch Boundary Elements. Engineering with Computers. vol.5. 1989. pages. 249-257.
[6] Rockwood, A., Heaton, K., Davis, T. Real-Time Rendering of Trimmed Surfaces. Computer Graphics. vol.4, 1987, pages. 59-66.
[7] Hoscheck, J., "Approximate Conversion of Spline Curves" Computer-Aided Geometric Design. vol.4, 1987. pages. 59-66.
[8] 马翔，罗俊奇．一种trimmed NURBS曲面的裁剪方法．工程图学学报，1993(1)：41-47．
[9] 沈庆云，周来水，张乐年．一种NURBS曲面的裁剪方法，南京航空航天大学学报，1997，29(2)：138—144．
[10] Weiler K J,Atherton P R.Hidde surface removal Using polygon area sorting. Computer Graphics,1977,11(2).
[11] 董洪伟，周来水．周儒荣．一种曲面裁剪的快速新算法，工程图学学报，2000(2)：46-51
[12] Jarek Rossignac.Paul Borrel. Multi-resolution 3D approximations for rendering complex scenes, In B. Falcidieno and T.Kunii, editors, Modeling in Computer Graphics: Methods and Applications, pages 455-465. 1993.
[13] Low K.L., Tan T.S. Model Simplification Using Vertex-Clustering, Symposium on Interactive 3D Gragpics, page 75-81, 1997.
[14] Hugues Hoppe. Tony DeRose. Tom Duchamp. John McDonald, Werner Stuetzle. Mesh optimization. In SIGGRAPH'93 Proc., pages 19-26 August 1993.
[15] Algorri, M. M. and Schmitt. Mesh Simplification., EUROGRAPHICS'96 Vol 15. 3(C): 77-86, 1996.
[16] M.Garland and P.Heckber t. Surface Simplification Using Quadric Error Metrics. Computer Graphics(Proc.Siggraph 97), vol.31. ACM Press. New York. 1997. pages.209-216.
[17] William J. Schroeder. Jonathan A. Zarge. and William E. Lorensen. Decimation of Triangle Meshes. Computer Graphics (SIGGRAPH'92 Proc.), 26(2): pages. 65-70, July 1992.
[18] Hamman B. Chen J L. Data Point Selection for Piecewise Trilinear Approximation. Computer Aided Geometric Design. 1994.
[19] 张树有，谭建荣，彭群生，基于拓扑映射的视图轮廓信息自动获取算法，中国图象图形学报，2001，6A (10)：1016-1020
[20] 吴春福，陆国栋，张树有，基于拓扑映射的多边形顶点凸凹判别算法．计算机辅助设计与图形学学报，2002，14(9)：810-814
[21] 温星，陆国栋，李基拓，基于拓扑映射的点集在凸多边形内外判断算法．中国图象图形学报，2003．8A(4)：468-471
[22] 李际军，程耀东，柯映林，复合三角Bezier曲面的裁剪，计算机辅助设计与图形学学报，2000．12(1)：65-69
[23] Masahiro Okuda, Tsuhan Chen, Joint Geometry/Texture Progressive Coding of 3D Models, IEEE International Conference on Image Processing 2000.
[24] Piegl, Leslie A. and Wayne Tiller, Geometry-based Triangulation of Trimmed NURBS Surfaces, Computer Aided Design vol.30, No. 1, pages. 11-18(1998).
[25] Nathan Litke, Adi Levin, Peter Schroder, Trimming for Subdivision Surfaces. Computer Aided Geometric Design, vol. 18,2001,pages.463-481.
[26] Ravi, G.V.V. Kumar, Prabha Srinivasan, K.G. Shastry and B.G. Prakash, Geometry Based Triangulation of Multiple Trimmed NURBS Surfaces. Computer Aided Design, vol.33,No.6, pages.439-454(2001).
[27] Fang, Tsung-Pao and Les A. Piegl, Delaunay Triangulation using a uniform gird. IEEE Computer Graphics & Applications, vol. 13. No.3, pages.36-47(1993).
[28] Cignoni. P., C. Montani and R.Scopigno, De Wall: A Fast Divide and Conquer Detaunay Triangulation Algorithm in E~d. Computer Aided Design, vol.30, No.5. pages.333-341(1998).
[29] Piegl, Leslie A. Arnaud M. Richard. Tessellating Trimmed NURBS Surfaces. Computer Aided Design. vol.27.No. 1. pages. 16-26(1995).
[30] Piegl, Leslie A. Arnaud M. Richard. Algorithm and Data Structure for Triangulating Multiply Connected Polygonal Domains. Comput. & Graphics. vol.17, No.5 pages.563-574(1993).
[31] 潘志庚．马小虎．石教英．虚拟环境中多细节层次模型自动生成算法，软件学报，1996．7(9)：526—531．
[32] 周晓云．刘慎权，基于特征角准则的多面体模型简化方法．计算机学报，1996，19(增刊)：217-223。
[33] 周昆．潘志庚．石教英，基于三角形折叠的网格简化算法，计算机学报，1998，21(6)：506-513。
[34] 周叶．王家华．填充等值线图的区域搜索算法，计算机工程，1994，S1：508-511。
[35] 孟小红．方敏．位场建模中的曲面切割方法，长春科技大学学报，1999，29(1)：84-87。
[36] 田学东，郭宝兰，一种基于连通区域搜索的版面分析算法，河北大学学报，1997，17(12)：44-46。
[37] 王钧，汤晓安，景宁，一种大范围复杂场景的快速绘制算法，计算机工程与应用，2003，16：88-90。
[38] 许云杰．胡事民，基于层次细节模型的遮挡裁剪算法，中国图象图形学报，2002，7(A)，9：62-967。
[39] 张华琪．王毅刚，基于法向映射的复杂模型的实时绘制技术，系统仿真学报，2003，15(3)：343-346。
[40] Garland M. Heckbert PS, Simplifying Surfaces with color and texture using quadric error metrics. In IEEE Visualization'98. ACM Press, New York. 198:264-270.
[41] Cignoni P, Montani C, A General Method for Preserving Attribute Values on Simplified Meshes, in Visualization'98 proceedings. IEEE. 1998:59-66.
[42] Cohen J. Olano M. Manocha D. Appearance-preserving Simplification. Annual ConfSeries(SIGGRAPH'98),1998:114-122.
[43] Schweitzer, J.E., Analysis and Application of Subdivision Surfaces, Ph.D. Thesis. University of Washington.
[44] 张丽艳，周儒荣，唐杰，周来水，带属性的三角网格模型简化算法研究，计算机辅助设计与图形学学报，2002，14(3)．199-203。
[45] 蒋遂平，周明天，戴颖，基于法向的网格简化，计算机学报，1999，22(10)，1074-1079．
[46] 许栋，张泉方，刘新国，鲍虎军，彭群生，一般多边形网格的几何压缩，计算机辅助设计与图形学学报，2002，14(9)，815-819。
[2] Johannsen. A. and Carter, M. B. "Clustered Backface Culling". Journal of Graphics Tools 3, 1(1998), 1-14.
[3] Zhang, H. and Hoff Ⅲ, K. Fast Backface Culling Using Normal Masks. In Proc. Symposium on Interactive 3D Graphics, 1997, pages 103-106.
[4] Casale. M.S., Bobrow. J.E. Solid Modeling Using Parametric Surfaces Defined Over Non-Square Domains. Eighth International Conference on Off-shore Mechanics and Arctic Engineering. March 1989, pages.231-236.
[5] Casale, M.S., Bobrow, J.E, The Analysis of Solids Without Mesh Generation Using Trimmed Patch Boundary Elements. Engineering with Computers. vol.5. 1989. pages. 249-257.
[6] Rockwood, A., Heaton, K., Davis, T. Real-Time Rendering of Trimmed Surfaces. Computer Graphics. vol.4, 1987, pages. 59-66.
[7] Hoscheck, J., "Approximate Conversion of Spline Curves" Computer-Aided Geometric Design. vol.4, 1987. pages. 59-66.
[8] 马翔，罗俊奇．一种trimmed NURBS曲面的裁剪方法．工程图学学报，1993(1)：41-47．
[9] 沈庆云，周来水，张乐年．一种NURBS曲面的裁剪方法，南京航空航天大学学报，1997，29(2)：138—144．
[10] Weiler K J,Atherton P R.Hidde surface removal Using polygon area sorting. Computer Graphics,1977,11(2).
[11] 董洪伟，周来水．周儒荣．一种曲面裁剪的快速新算法，工程图学学报，2000(2)：46-51
[12] Jarek Rossignac.Paul Borrel. Multi-resolution 3D approximations for rendering complex scenes, In B. Falcidieno and T.Kunii, editors, Modeling in Computer Graphics: Methods and Applications, pages 455-465. 1993.
[13] Low K.L., Tan T.S. Model Simplification Using Vertex-Clustering, Symposium on Interactive 3D Gragpics, page 75-81, 1997.
[14] Hugues Hoppe. Tony DeRose. Tom Duchamp. John McDonald, Werner Stuetzle. Mesh optimization. In SIGGRAPH'93 Proc., pages 19-26 August 1993.
[15] Algorri, M. M. and Schmitt. Mesh Simplification., EUROGRAPHICS'96 Vol 15. 3(C): 77-86, 1996.
[16] M.Garland and P.Heckber t. Surface Simplification Using Quadric Error Metrics. Computer Graphics(Proc.Siggraph 97), vol.31. ACM Press. New York. 1997. pages.209-216.
[17] William J. Schroeder. Jonathan A. Zarge. and William E. Lorensen. Decimation of Triangle Meshes. Computer Graphics (SIGGRAPH'92 Proc.), 26(2): pages. 65-70, July 1992.
[18] Hamman B. Chen J L. Data Point Selection for Piecewise Trilinear Approximation. Computer Aided Geometric Design. 1994.
[19] 张树有，谭建荣，彭群生，基于拓扑映射的视图轮廓信息自动获取算法，中国图象图形学报，2001，6A (10)：1016-1020
[20] 吴春福，陆国栋，张树有，基于拓扑映射的多边形顶点凸凹判别算法．计算机辅助设计与图形学学报，2002，14(9)：810-814
[21] 温星，陆国栋，李基拓，基于拓扑映射的点集在凸多边形内外判断算法．中国图象图形学报，2003．8A(4)：468-471
[22] 李际军，程耀东，柯映林，复合三角Bezier曲面的裁剪，计算机辅助设计与图形学学报，2000．12(1)：65-69
[23] Masahiro Okuda, Tsuhan Chen, Joint Geometry/Texture Progressive Coding of 3D Models, IEEE International Conference on Image Processing 2000.
[24] Piegl, Leslie A. and Wayne Tiller, Geometry-based Triangulation of Trimmed NURBS Surfaces, Computer Aided Design vol.30, No. 1, pages. 11-18(1998).
[25] Nathan Litke, Adi Levin, Peter Schroder, Trimming for Subdivision Surfaces. Computer Aided Geometric Design, vol. 18,2001,pages.463-481.
[26] Ravi, G.V.V. Kumar, Prabha Srinivasan, K.G. Shastry and B.G. Prakash, Geometry Based Triangulation of Multiple Trimmed NURBS Surfaces. Computer Aided Design, vol.33,No.6, pages.439-454(2001).
[27] Fang, Tsung-Pao and Les A. Piegl, Delaunay Triangulation using a uniform gird. IEEE Computer Graphics & Applications, vol. 13. No.3, pages.36-47(1993).
[28] Cignoni. P., C. Montani and R.Scopigno, De Wall: A Fast Divide and Conquer Detaunay Triangulation Algorithm in E~d. Computer Aided Design, vol.30, No.5. pages.333-341(1998).
[29] Piegl, Leslie A. Arnaud M. Richard. Tessellating Trimmed NURBS Surfaces. Computer Aided Design. vol.27.No. 1. pages. 16-26(1995).
[30] Piegl, Leslie A. Arnaud M. Richard. Algorithm and Data Structure for Triangulating Multiply Connected Polygonal Domains. Comput. & Graphics. vol.17, No.5 pages.563-574(1993).
[31] 潘志庚．马小虎．石教英．虚拟环境中多细节层次模型自动生成算法，软件学报，1996．7(9)：526—531．
[32] 周晓云．刘慎权，基于特征角准则的多面体模型简化方法．计算机学报，1996，19(增刊)：217-223。
[33] 周昆．潘志庚．石教英，基于三角形折叠的网格简化算法，计算机学报，1998，21(6)：506-513。
[34] 周叶．王家华．填充等值线图的区域搜索算法，计算机工程，1994，S1：508-511。
[35] 孟小红．方敏．位场建模中的曲面切割方法，长春科技大学学报，1999，29(1)：84-87。
[36] 田学东，郭宝兰，一种基于连通区域搜索的版面分析算法，河北大学学报，1997，17(12)：44-46。
[37] 王钧，汤晓安，景宁，一种大范围复杂场景的快速绘制算法，计算机工程与应用，2003，16：88-90。
[38] 许云杰．胡事民，基于层次细节模型的遮挡裁剪算法，中国图象图形学报，2002，7(A)，9：62-967。
[39] 张华琪．王毅刚，基于法向映射的复杂模型的实时绘制技术，系统仿真学报，2003，15(3)：343-346。
[40] Garland M. Heckbert PS, Simplifying Surfaces with color and texture using quadric error metrics. In IEEE Visualization'98. ACM Press, New York. 198:264-270.
[41] Cignoni P, Montani C, A General Method for Preserving Attribute Values on Simplified Meshes, in Visualization'98 proceedings. IEEE. 1998:59-66.
[42] Cohen J. Olano M. Manocha D. Appearance-preserving Simplification. Annual ConfSeries(SIGGRAPH'98),1998:114-122.
[43] Schweitzer, J.E., Analysis and Application of Subdivision Surfaces, Ph.D. Thesis. University of Washington.
[44] 张丽艳，周儒荣，唐杰，周来水，带属性的三角网格模型简化算法研究，计算机辅助设计与图形学学报，2002，14(3)．199-203。
[45] 蒋遂平，周明天，戴颖，基于法向的网格简化，计算机学报，1999，22(10)，1074-1079．
[46] 许栋，张泉方，刘新国，鲍虎军，彭群生，一般多边形网格的几何压缩，计算机辅助设计与图形学学报，2002，14(9)，815-819。