基于改进包围盒树和GPU的水稻群体叶片间快速碰撞检测

Fast collision detection for rice leaf population based on improved bounded box tree and GPU

为了解决水稻群体动态生长模拟过程中叶片间碰撞检测效率较低的技术问题,该文利用水稻叶片抛物线的形态结构特性以及CPU/GPU硬件加速特性,提出了水稻叶片混合层次包围盒树(mixed level tree,MLT)快速构造方法以及基于CPU/GPU的群体叶片快速相交检测方法。提出了新的OBB包围盒方向轴计算方式,降低了OBB包围盒构建的复杂度,在此基础上,利用单株叶片之间、群体叶片之间碰撞检测计算关系的依赖性,设计了CPU/GPU加速方案,并使用CUDA在Tesla 40加速卡上实现。对分蘖期大规模水稻群体叶片进行了效率对比试验,结果表明,水稻群体规模从2 000株增长到10 000株的过程中,本文提出的基于MLT的碰撞检测方法耗时是传统的AABB方法耗时的50%,是OBB方法耗时的30%,有效地提升了叶片之间的碰撞检测速度;同时,基于CPU的碰撞检测方法耗时呈线性增长,而利用CPU/GPU并行加速耗时相较于在CPU上的运行时间节省了98%,大幅度提升碰撞检测效率。该研究可为虚拟作物可视化仿真提供参考。

Virtual rice technology has played an important role in modern agricultural production decision-making,yield prediction,crop breeding and growth conditions optimization.In the visualization of virtual rice,the phenomenon of interpenetration between organs is often found.There is need to use collision detection technology to avoid this phenomenon.However,when the number and size of the population increase,there will be a lower collision detection efficiency.To improve the efficiency of leaf collision detection during the dynamic growth simulation of rice population,methods for rapid construction of mixed leaf tree(MLT)and fast detection of CPU/GPU are proposed in this paper.The main ideas of these methods are based on the morphological structure characteristics of leaf parabola and the accelerating characteristics of CPU/GPU.On the single leaf scale,a new calculation of OBB bounding box direction axis method is proposed to reduce the construction complexity of OBB bounding box,and the MLT is constructed based on the upper axis aligned bounding box(AABB)and the lower oriented bounding box(OBB).The AABB bounding box is built to quickly exclude the disjointed leaf pairs and the OBB bounding box is built to ensure the accuracy of the collision detection.According to the morphological characteristics of rice leaves,the calculation method of the new OBB bounding box direction axis is proposed to replace the traditional calculation method based on covariance matrix and mean value,which reduces the complexity of OBB bounding box construction.The new calculation method is applicable to the cases in which the leaves of rice are not twisted,curled,broken,and so on.In these cases,the mid-vein curve of the rice leaves can be considered as the first order derivable and the second order continuous.The connection line between the starting point and the end point in the mid-vein curve is a direction axis of the OBB bounding box,in the initial structure of rice leaves,the z-axis is the other axis of the leaf OBB bounding box,and the third direction axis can be determined by the2determined direction axes.On the group scale,firstly,according to the regularity of rice population cultivation and the law of rice growth,the rule of collision detection between rice is proposed:No collision detection is calculated between rows or columns of non-adjacent plants,and if row or column distance is greater than the sum of the length of the2longest leaves of rice,there is no collision detection between them.Use these rules to reduce the number of rice leaves for collision detection.Then the CPU/GPU acceleration scheme was designed by using the dependence of the collision detection between the leaves of the individual plants and rice population:The construction of the rice population MLT on the CPU side is carried out,and the intersection of the calculation on the GPU side is calculated.Each thread block represents the result of the intersection detection of a leaf,and for each thread in the thread block a crossing detection is calculated between a pair of leaves;when the thread block in the calculation of all the results has no collision,it is determined that thread block represents no collision,otherwise it is determined to have the collision.After all the calculation is completed,the intersection test result is returned to the CPU side for processing.In order to verify the effectiveness of this study,the experiment of collision detection efficiency was carried out with the leaves of large-scale rice population at tillering stage.The results show that the time consumed by collision detection method proposed in this paper is50%less than the traditional AABB and OBB method,which effectively improves the collision detection speed between leaves.When the rice population is large,the running time of CPU/GPU parallel acceleration is98%less than that of the CPU,and the collision detection efficiency is greatly improved.