Efficient arithmetic for space partitioning
-
摘要: 针对三角面元目标提出了一种高效率的空间分割算法.该方法以一种空间点与单位立方体位置关系的判断法则为基础,并逐渐延拓到参数直线、三角形的空间分割上,给出了一种新的三角形面元目标快速分割的解决方法.介绍了该方法在参数曲线、NURBS(Non-Uniform Rational B-Spline)曲面目标的空间均匀分割上的应用,并给出了非均匀分割的处理方法.与计算机图形技术中最常用的BSP(Binary Space Partitioning)技术的比较中发现,对于特定情形,该算法的执行效率优于BSP法.通过实例证明了该算法的有效性和可靠性.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.
-
[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)
点击查看大图
计量
- 文章访问数: 2725
- HTML全文浏览量: 114
- PDF下载量: 2124
- 被引次数: 0