一种高效空间分割算法

刘忠铁; 马东立

一种高效空间分割算法

北京航空航天大学航空科学与工程学院, 北京 100191

详细信息

作者简介:
刘忠铁(1980-),男,辽宁本溪人,博士生,liuzhongtie@ase.buaa.edu.cn.

中图分类号: TP 391
计量
- 文章访问数: 2725
- HTML全文浏览量: 114
- PDF下载量: 2124
- 被引次数: 0
出版历程
- 收稿日期: 2009-03-16
- 网络出版日期: 2010-04-30

Efficient arithmetic for space partitioning

School of Aeronautic Science and Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100191, China

摘要

摘要: 针对三角面元目标提出了一种高效率的空间分割算法.该方法以一种空间点与单位立方体位置关系的判断法则为基础,并逐渐延拓到参数直线、三角形的空间分割上,给出了一种新的三角形面元目标快速分割的解决方法.介绍了该方法在参数曲线、NURBS(Non-Uniform Rational B-Spline)曲面目标的空间均匀分割上的应用,并给出了非均匀分割的处理方法.与计算机图形技术中最常用的BSP(Binary Space Partitioning)技术的比较中发现,对于特定情形,该算法的执行效率优于BSP法.通过实例证明了该算法的有效性和可靠性.
- 空间分割 /
- 二叉空间分割 /
- 参数曲线 /
- 非均匀有理B样条 /
- 取整
Abstract: An efficient algorithm was provided for space partitioning of triangular facets. The algorithm based on judging the position relationship between a 3D point and a unit cubic, and extended to the straight-lines and triangles- partitioning. A new method of triangle-facet targets fast partitioning was given. Its application in solving parametric curves and non-uniform rational B-spline (NURBS) surface was considered, and the solution to the situation of non-uniform partitioning was also given for consult. Compared with the binary space partitioning(BSP) trees technology, which was the most popular method, this arithmetic performed better than BSP in solving particular problem. The results prove the efficiency and reliability of the arithmetic.
- space partitioning /
- binary space partitioning (BSP) /
- parametric curve /
- non-uniform rational B-spline (NURBS) /
- rounding

HTML全文

参考文献(1)

[1] David F R.Procedural elements for computer graphics [M].New York:McGraw-Hill,1998:4-6,299-306 [2] Zhi H M,David D,Eric F.Space partition for conflict resolution of intersecting flows of mobile agents [J].IEEE Transactions on Intelligent Transportation Systems,2007,8(3):512-527 [3] 顾耀林,袁江琛.采用空间分割的平滑曲面重构算法[J].计算机工程,2007,33(21):226-228 Gu Yaolin,Yuan Jiangchen.Smooth surface reconstruction algorithm using space segmentation[J].Computer Engineering,2007,33(21):226-228(in Chinese) [4] Fuchs H,Kedem Z,Naylor B.On visible surface generation by a priori tree structures[J].Computer Graphics,1980,14(3):124-133 [5] Martinez J A,Meana J G,Las H,et al.A physical optics multi-level binary space partitioning algorithm for large scattering problems //Antennas and Propagation Society International Symposium.Albuquerque: IEEE,2006:1845-1848 [6] Sarkis M,Diepold K.Content adaptive mesh representation of images using binary space partitions[J].Image Processing,2009,18(5):1069-1079 [7] 于文洋,杨崇俊,乐小虬,等.三维复杂场景管理研究[J].计算机工程与应用,2006,13:38-40 Yu Wenyang,Yang Chongjun,Le Xiaoqiu,et al.Research on management of complex three-dimensional scene[J].Computer Engineering and Applications,2006,13:38-40(in Chinese) [8] 施法中.计算机辅助几何设计与非均匀有理B样条[M].北京:高等教育出版社,2001:131-135 Shi Fazhong.Computer aided geometric design and non-uniform rational B-spline[M].Beijing:Higher Education Press,2001:131-135(in Chinese)

施引文献

资源附件(0)

访问统计