基于多直线简化方法的二维CAD显示优化研究
摘要
针对二维CAD软件在处理图元数量较大的图纸时响应速度较慢的问题,本文提出一种多直线简化算法。该算法在保证图形显示效果的前提下,通过减少图元的绘制量,达到CAD软件图形显示速度加快,响应速度提高的目的。
多直线简化算法要求CAD图纸中的图元用R-Tree索引结构组织。R-Tree是一种动态的空间索引结构,它基于图元的最小包围矩形而构建,并允许图元之间相互重叠。R-Tree索引结构天然的图元聚集效应,是多直线简化算法的实现基础。
首先,直接利用R-Tree的树状结构特点,提出屏幕显示过程中的“微小节点简化”,即:对于变换到屏幕坐标系之后包围盒最大边长不超过一个像素的R-Tree节点,可以用屏幕上的一次点绘制过程代替该节点下的全部图元的显示。
其次,通过对直线显示算法的分析,结合R-Tree索引结构天然的图元聚集效应,提出“基于遮挡、拼接方法的多直线简化”算法。该算法在“微小节点简化”的基础之上,旨在通过一次直线绘制过程,实现尽可能多的直线的屏幕显示。整个多直线简化算法由“微小节点简化”和“基于遮挡、拼接方法的多直线简化”这两级简化构成。
然后,为了使得多直线简化算法能够更好的发挥作用,本文提出了一个新的二维CAD图形显示框架,同时阐述了该框架的工作机制以及优势。
最后,文章通过具体的实验数据,确定了简化算法中的一些关键参数。测试结果表明,多直线简化算法在大数据量图纸的屏幕显示中能够有效的发挥作用,同时能够保证较好的图形显示质量。
When handling 2D-CAD drafting which contains a large number of data, 2D-CAD software——specially domestic 2D-CAD software——always has a significant performance degradation. This paper presents a multi-line simplification algorithm to deal with this problem. When refreshing the screen, the algorithm reduces the amount of data to display on the screen with the promise of the quality of graphic display. The algorithm can improve the response speed of 2D-CAD significantly.
Good algorithm needs appropriate data structures. This paper attempts to organize the data in a 2D-CAD drafting by spatial data structure, and finally selects R-Tree. As a dynamic data structure, R-Tree allows elements overlap each other, and this feature makes it suitable for the geographic information systems and CAD systems. The multi-line simplification algorithm demonstrated in this paper is based on R-Tree.
Firstly, the algorithm“Tiny Node Simplification”is present: when transform the minimum boundary box of an R-Tree node to screen coordinates, if its maximum side length is not more than one pixel, draw a point on the screen, and ignore the all elements which are the children of the node.
Secondly, with the naturally data accumulation effect of R-Tree, the algorithm“Multi-line Simplification by Covering and Splicing”is presented. Based on the“tiny node simplification”method, the algorithm tries to achieve the display of several lines by only one line display process. The multi-line simplification algorithm is composed by“Tiny Node Simplification”and“Multi-line Simplification by Covering and Splicing”.
Thirdly, to make multi-line simplification algorithm works better, this paper presents a new framework for the display module of 2D-CAD, and describes the working mechanism of the framework as well as advantages.
Finally, the paper tests the effect of the algorithm by experiment. The result shows that the“Multi-line simplification”algorithm can play an effective role on the improvement of response speed for 2D-CAD.
多直线简化算法要求CAD图纸中的图元用R-Tree索引结构组织。R-Tree是一种动态的空间索引结构,它基于图元的最小包围矩形而构建,并允许图元之间相互重叠。R-Tree索引结构天然的图元聚集效应,是多直线简化算法的实现基础。
首先,直接利用R-Tree的树状结构特点,提出屏幕显示过程中的“微小节点简化”,即:对于变换到屏幕坐标系之后包围盒最大边长不超过一个像素的R-Tree节点,可以用屏幕上的一次点绘制过程代替该节点下的全部图元的显示。
其次,通过对直线显示算法的分析,结合R-Tree索引结构天然的图元聚集效应,提出“基于遮挡、拼接方法的多直线简化”算法。该算法在“微小节点简化”的基础之上,旨在通过一次直线绘制过程,实现尽可能多的直线的屏幕显示。整个多直线简化算法由“微小节点简化”和“基于遮挡、拼接方法的多直线简化”这两级简化构成。
然后,为了使得多直线简化算法能够更好的发挥作用,本文提出了一个新的二维CAD图形显示框架,同时阐述了该框架的工作机制以及优势。
最后,文章通过具体的实验数据,确定了简化算法中的一些关键参数。测试结果表明,多直线简化算法在大数据量图纸的屏幕显示中能够有效的发挥作用,同时能够保证较好的图形显示质量。
When handling 2D-CAD drafting which contains a large number of data, 2D-CAD software——specially domestic 2D-CAD software——always has a significant performance degradation. This paper presents a multi-line simplification algorithm to deal with this problem. When refreshing the screen, the algorithm reduces the amount of data to display on the screen with the promise of the quality of graphic display. The algorithm can improve the response speed of 2D-CAD significantly.
Good algorithm needs appropriate data structures. This paper attempts to organize the data in a 2D-CAD drafting by spatial data structure, and finally selects R-Tree. As a dynamic data structure, R-Tree allows elements overlap each other, and this feature makes it suitable for the geographic information systems and CAD systems. The multi-line simplification algorithm demonstrated in this paper is based on R-Tree.
Firstly, the algorithm“Tiny Node Simplification”is present: when transform the minimum boundary box of an R-Tree node to screen coordinates, if its maximum side length is not more than one pixel, draw a point on the screen, and ignore the all elements which are the children of the node.
Secondly, with the naturally data accumulation effect of R-Tree, the algorithm“Multi-line Simplification by Covering and Splicing”is presented. Based on the“tiny node simplification”method, the algorithm tries to achieve the display of several lines by only one line display process. The multi-line simplification algorithm is composed by“Tiny Node Simplification”and“Multi-line Simplification by Covering and Splicing”.
Thirdly, to make multi-line simplification algorithm works better, this paper presents a new framework for the display module of 2D-CAD, and describes the working mechanism of the framework as well as advantages.
Finally, the paper tests the effect of the algorithm by experiment. The result shows that the“Multi-line simplification”algorithm can play an effective role on the improvement of response speed for 2D-CAD.
引文
[1]高德,冯志友.机械CAD技术基础[M].第二版.哈尔滨:哈尔滨工程大学出版社.2004.
[2] I. Sutherland.Sketchpad: A man-machine graphical communication system[C].proceedings of AFIPS Spring Joint Computer Conference. Michigan: Spartan Book, 1963: 329-346.
[3]杨千里.机械CAD的历史回顾与现代CAD的技术发展趋势.中国科技信息:2005,11.
[4]张晓云,蔡俊辉.图形加速技术的发展[C].电脑知识与技术:2007,125.
[5] Krakiwsky SE,Turner LE,Okoniewski MM.Graphics processor unit(GPU) acceleration of finite-difference time-domain(FDTD)algorithm.Proceedings of IEEEIS-CAS,2004.
[6]张舒,褚艳丽等.GPU高性能运算之CUDA[M].中国水利水电出版社:2009.
[7]杨正龙,金林,李蔚清.基于GPU的图形电磁计算加速算法.电子学报:2007,6,1056-1060.
[8] Dave Shreiner,Mason Woo,Jackie Neider,Tom Davis著,徐波等译.OpenGL编程指南[M].北京:机械工业出版社,2006:407-408.
[9] AnderwS.Tanenbaum著,陈向群等译.现代操作系统[M].北京:机械工业出版社,2009.
[10]石志昕.基于光栅图形生成算法研究[D].济南:山东大学.2007.
[11]孙家广.计算机图形学[M].清华大学出版社:1998.
[12]贾银亮;张焕春;经亚枝.Bresenham直线生成算法的改进[C].中国图象图形学报:2008,1.
[13] George Taylor.Line simplification algorithms[C].2005.
[14] David H Douglas, Thomas K Peucker.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[C].The Canadian Cartographer.1973,Vol 10,112-122.
[15]毋河海.基于多叉树结构的曲线综合算法[C].武汉大学学报(信息科学版):2004,29(6) .
[16] Konrad Ebisch.A correction to the Douglas-Peucker line generalization algorithm[C].Computers and Geosciences:2002.
[17]贾利峰.无级比例尺GIS的线状要素化简算法研究[C].西南交通大学,2005.
[18] J.S.Marino.Identification of characteristic points along naturally occurring lines: An empirical study[C].Canadian Cartography:1979,16.
[19] E.R.White.Assessment of line-generalization algorithoms using characteristic points[C].American Cartography:1985,12(1) .
[20] M. de Berg,M. van Kreveid,M. Overmars等.Computational Geomerty:Algorithms and Applications [M].Springer-Verlag Berlin Heidelberg New York:2000.
[21] J. L. Bentley.Multidimensional binary search tree used for associative searching[C].ACM:18,1975,509-517.
[22] R. A. Finkerl,J. L. Bentley.Quad trees: a data structure for retrieval on composite keys[C].Acta Inform:1974,4,1-9.
[23] Antomn Guttman.R-Trees: A Dynamic Index Structure for Spatial Searching [C].Proceeding of ACM SIGMOD Int Conf on Management of Data:1984,47-57.
[24]张明波,陆峰,申排伟等.R树家族的演变和发展[C].计算机学报:2005,28(3),281-300.
[25]蔡浴泓.空间数据库索引技术的研究与探索[D].上海:华东师范大学.2007.
[26] Beckmann N.,Kriegel H. P.,Schneider R.,Seeger B..The R*-tree: An efficient and robust access method for points and rectangles[C].Proceedings of SIGMOD:New Jersey , 1990 , 322-331.
[27] Kamel I.,Faloutsos C..Hilbert R-tree : An improved R-tree using fractals[C].Proceedings of the 20th VLDB:1994,500-509.
[28] Brakatsoulas S.,Pfoser D.,Theodoridis Y..Revisiting R-tree construction principles[C].Proceedings of the 6th ADBIS:2002,149-162.
[29] A. Al-Badarneh,M. Tawil.Linear R-Tree Revisited[C].International Journal of Computer and Applications:2009,31(2),74-85.
[30] Oosterom P.,Johannes P.,van M..Reactive Data Structures for Geographic Information Systems[C].Oxford University Press:1993.
[31]史文中等.一种面向地理信息系统的空间索引方法[C].测绘学报:2001,30 (2) ,156-161.
[32] Guenther O..The cell tree : An object oriented index structure for geometric databases[C].Proceedings of the 5th IEEE ICDE:1989, 598-605.
[33] Jagadish H. V..Spatial search with polyhedra[C].Proceedings of the 6th IEEE ICDE:1990,311-319.
[34] Ang C. H.,Tan T. C..New linear node splitting algorithm for R-trees[C].Proceedings of the 5th SSD:1997,339-349.
[35] Garcia Y., Lopez M., Leutenegger S..On optimal node splitting for R-trees[C].Proceedings of the 24th VLDB:1998,334-344.
[36] Schrek T.,Chen Z..Branch grafting method for R-tree implementation[C].Journal of Systems and Software:2000,53 (1),83-93.
[37] S. Berchtold,D. A. Keim,H. P. Kriegel.The X-tree: an index structure for high- dimensional data: Proceeding of the 22nd VLDB conf [C].Mumb India, 1996:28-39.
[38]郭菁,郭薇,胡志勇.大型GIS空间数据库的有效索引结构QR-树[J].武汉大学学报:信息科学版,2003,28(3):306-310.
[39]徐少平,王命延,王炜立.一种基于R树和四叉树的移动对象空间数据库混合索引结构[J].计算机与数字工程.2006,34(3):54-57.
[40] Lee Taewon,Moon Bongki,Lee Sukho.Bulk insertion for R-tree by seeded clustering[C].Proceedings of DEXA:2003,129-138.
[41]空间数据索引技术的研究及在GIS中的应用[D].大连:大连理工大学.2005.
[42] K. A. Mohamed.R-Tree: Special Representation on a Dynamic-Index Structure.2006.
[43]周东.R-Tree代价模型与查询优化研究与实现[D].成都:西南交通大学.2007.
[44] Randal E. Bryant,David O’Hallaron著,龚奕利等译.深入理解计算机系统(修订版)[M].中国电力出版社:2005.
[2] I. Sutherland.Sketchpad: A man-machine graphical communication system[C].proceedings of AFIPS Spring Joint Computer Conference. Michigan: Spartan Book, 1963: 329-346.
[3]杨千里.机械CAD的历史回顾与现代CAD的技术发展趋势.中国科技信息:2005,11.
[4]张晓云,蔡俊辉.图形加速技术的发展[C].电脑知识与技术:2007,125.
[5] Krakiwsky SE,Turner LE,Okoniewski MM.Graphics processor unit(GPU) acceleration of finite-difference time-domain(FDTD)algorithm.Proceedings of IEEEIS-CAS,2004.
[6]张舒,褚艳丽等.GPU高性能运算之CUDA[M].中国水利水电出版社:2009.
[7]杨正龙,金林,李蔚清.基于GPU的图形电磁计算加速算法.电子学报:2007,6,1056-1060.
[8] Dave Shreiner,Mason Woo,Jackie Neider,Tom Davis著,徐波等译.OpenGL编程指南[M].北京:机械工业出版社,2006:407-408.
[9] AnderwS.Tanenbaum著,陈向群等译.现代操作系统[M].北京:机械工业出版社,2009.
[10]石志昕.基于光栅图形生成算法研究[D].济南:山东大学.2007.
[11]孙家广.计算机图形学[M].清华大学出版社:1998.
[12]贾银亮;张焕春;经亚枝.Bresenham直线生成算法的改进[C].中国图象图形学报:2008,1.
[13] George Taylor.Line simplification algorithms[C].2005.
[14] David H Douglas, Thomas K Peucker.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[C].The Canadian Cartographer.1973,Vol 10,112-122.
[15]毋河海.基于多叉树结构的曲线综合算法[C].武汉大学学报(信息科学版):2004,29(6) .
[16] Konrad Ebisch.A correction to the Douglas-Peucker line generalization algorithm[C].Computers and Geosciences:2002.
[17]贾利峰.无级比例尺GIS的线状要素化简算法研究[C].西南交通大学,2005.
[18] J.S.Marino.Identification of characteristic points along naturally occurring lines: An empirical study[C].Canadian Cartography:1979,16.
[19] E.R.White.Assessment of line-generalization algorithoms using characteristic points[C].American Cartography:1985,12(1) .
[20] M. de Berg,M. van Kreveid,M. Overmars等.Computational Geomerty:Algorithms and Applications [M].Springer-Verlag Berlin Heidelberg New York:2000.
[21] J. L. Bentley.Multidimensional binary search tree used for associative searching[C].ACM:18,1975,509-517.
[22] R. A. Finkerl,J. L. Bentley.Quad trees: a data structure for retrieval on composite keys[C].Acta Inform:1974,4,1-9.
[23] Antomn Guttman.R-Trees: A Dynamic Index Structure for Spatial Searching [C].Proceeding of ACM SIGMOD Int Conf on Management of Data:1984,47-57.
[24]张明波,陆峰,申排伟等.R树家族的演变和发展[C].计算机学报:2005,28(3),281-300.
[25]蔡浴泓.空间数据库索引技术的研究与探索[D].上海:华东师范大学.2007.
[26] Beckmann N.,Kriegel H. P.,Schneider R.,Seeger B..The R*-tree: An efficient and robust access method for points and rectangles[C].Proceedings of SIGMOD:New Jersey , 1990 , 322-331.
[27] Kamel I.,Faloutsos C..Hilbert R-tree : An improved R-tree using fractals[C].Proceedings of the 20th VLDB:1994,500-509.
[28] Brakatsoulas S.,Pfoser D.,Theodoridis Y..Revisiting R-tree construction principles[C].Proceedings of the 6th ADBIS:2002,149-162.
[29] A. Al-Badarneh,M. Tawil.Linear R-Tree Revisited[C].International Journal of Computer and Applications:2009,31(2),74-85.
[30] Oosterom P.,Johannes P.,van M..Reactive Data Structures for Geographic Information Systems[C].Oxford University Press:1993.
[31]史文中等.一种面向地理信息系统的空间索引方法[C].测绘学报:2001,30 (2) ,156-161.
[32] Guenther O..The cell tree : An object oriented index structure for geometric databases[C].Proceedings of the 5th IEEE ICDE:1989, 598-605.
[33] Jagadish H. V..Spatial search with polyhedra[C].Proceedings of the 6th IEEE ICDE:1990,311-319.
[34] Ang C. H.,Tan T. C..New linear node splitting algorithm for R-trees[C].Proceedings of the 5th SSD:1997,339-349.
[35] Garcia Y., Lopez M., Leutenegger S..On optimal node splitting for R-trees[C].Proceedings of the 24th VLDB:1998,334-344.
[36] Schrek T.,Chen Z..Branch grafting method for R-tree implementation[C].Journal of Systems and Software:2000,53 (1),83-93.
[37] S. Berchtold,D. A. Keim,H. P. Kriegel.The X-tree: an index structure for high- dimensional data: Proceeding of the 22nd VLDB conf [C].Mumb India, 1996:28-39.
[38]郭菁,郭薇,胡志勇.大型GIS空间数据库的有效索引结构QR-树[J].武汉大学学报:信息科学版,2003,28(3):306-310.
[39]徐少平,王命延,王炜立.一种基于R树和四叉树的移动对象空间数据库混合索引结构[J].计算机与数字工程.2006,34(3):54-57.
[40] Lee Taewon,Moon Bongki,Lee Sukho.Bulk insertion for R-tree by seeded clustering[C].Proceedings of DEXA:2003,129-138.
[41]空间数据索引技术的研究及在GIS中的应用[D].大连:大连理工大学.2005.
[42] K. A. Mohamed.R-Tree: Special Representation on a Dynamic-Index Structure.2006.
[43]周东.R-Tree代价模型与查询优化研究与实现[D].成都:西南交通大学.2007.
[44] Randal E. Bryant,David O’Hallaron著,龚奕利等译.深入理解计算机系统(修订版)[M].中国电力出版社:2005.