一种空间数据结构加速的顶点与地形实时交互算法
|
摘要
针对动态场景的实时交互式渲染中,离散碰撞检测算法导致的"穿模"现象,提出一种新的顶点与地形实时交互算法,并利用空间数据结构进行加速。算法利用顶点与模型表面多边形的空间位置关系,首先计算顶点在当前模型移动后的位置,然后计算本次移动与其他模型的相交情况,将移动沿路径依次分解到每个经过的面上,以此计算移动轨迹与终点位置。算法可通过层次包围盒、八叉树、KD树等各类现有的空间数据结构进行加速。使用八叉树,设计并实现了简易的场景漫游与寻路,以此为实验环境进行性能分析。实验数据证明,该方法能够满足实时性的要求,并且具有较高精度。
For real-time interactive rendering of dynamic scenes, the phenomenon of mutual penetration or superposition of objects caused by discrete collision detection algorithms, this paper proposes a new real-time interaction algorithm between vertex and terrain, and accelerates with spatial data structure. The algorithm uses the spatial positional relationship between the vertex and the surface polygon of the model. Firstly, the position of the vertex after the current model is moved is calculated. Then, the intersection of the current movement and other models is calculated, and the movement is sequentially decomposed along the path to each passing surface to This calculates the movement path and the end position. The algorithm can be accelerated by various existing spatial data structures such as bounding volume hierarchies, octrees, and KD trees. In this paper, we use octree to design and implement simple scene roaming and pathfinding to analyze the performance of the experimental environment. The experimental data proves that the method can meet the requirements of real-time and has high precision.
For real-time interactive rendering of dynamic scenes, the phenomenon of mutual penetration or superposition of objects caused by discrete collision detection algorithms, this paper proposes a new real-time interaction algorithm between vertex and terrain, and accelerates with spatial data structure. The algorithm uses the spatial positional relationship between the vertex and the surface polygon of the model. Firstly, the position of the vertex after the current model is moved is calculated. Then, the intersection of the current movement and other models is calculated, and the movement is sequentially decomposed along the path to each passing surface to This calculates the movement path and the end position. The algorithm can be accelerated by various existing spatial data structures such as bounding volume hierarchies, octrees, and KD trees. In this paper, we use octree to design and implement simple scene roaming and pathfinding to analyze the performance of the experimental environment. The experimental data proves that the method can meet the requirements of real-time and has high precision.
引文
[1]冯立颖.碰撞检测技术研究综述[J].计算机时代,2014(8):7-10.
[2]刘复昌,王双建,潘志庚,等.并行化碰撞检测算法综述[J].系统仿真学报,2017(11):2601-2607.
[3]吴元洪,郭平,应新洋.空间数据结构分析[J].计算机应用研究,2004(3):39-41.
[4] AR S,CHAZELLE B,TAL A.Self-customized BSP trees for collision detection[J]. Computational Geometry,2000,15(1-3):91-102.
[5] MEI K J,LEE R S.Collision detection for virtual machine tools and virtual robot arms using the Shared Triangles Extended Octrees method[J].International Journal of Computer Integrated Manufacturing,2016,29(4):355-373.
[6] SCHWESINGER U,SIEGWART R,FURGALE P T. Fast collision detection through bounding volume hierarchies in workspace-time space for sampling-based motion planners[C].ICRA,2015:63-68.
[7] WANG X,TANG M,MANOCHA D, et al.Efficient BVHbased Collision Detection Scheme with Ordering and Restructuring[C]. Computer Graphics Forum,2018,37(2):227-237.
[8]谢倩茹,耿国华.三维模型孔洞修补方法的研究[J].计算机应用研究,2013,30(10):3175-3177.
[9]王运钢,徐岩军,林海荣.基于双向切片的点云孔洞修补方法研究[J].测绘与空间地理信息,2015,38(10):218-220.
[2]刘复昌,王双建,潘志庚,等.并行化碰撞检测算法综述[J].系统仿真学报,2017(11):2601-2607.
[3]吴元洪,郭平,应新洋.空间数据结构分析[J].计算机应用研究,2004(3):39-41.
[4] AR S,CHAZELLE B,TAL A.Self-customized BSP trees for collision detection[J]. Computational Geometry,2000,15(1-3):91-102.
[5] MEI K J,LEE R S.Collision detection for virtual machine tools and virtual robot arms using the Shared Triangles Extended Octrees method[J].International Journal of Computer Integrated Manufacturing,2016,29(4):355-373.
[6] SCHWESINGER U,SIEGWART R,FURGALE P T. Fast collision detection through bounding volume hierarchies in workspace-time space for sampling-based motion planners[C].ICRA,2015:63-68.
[7] WANG X,TANG M,MANOCHA D, et al.Efficient BVHbased Collision Detection Scheme with Ordering and Restructuring[C]. Computer Graphics Forum,2018,37(2):227-237.
[8]谢倩茹,耿国华.三维模型孔洞修补方法的研究[J].计算机应用研究,2013,30(10):3175-3177.
[9]王运钢,徐岩军,林海荣.基于双向切片的点云孔洞修补方法研究[J].测绘与空间地理信息,2015,38(10):218-220.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |