一种空间数据结构加速的顶点与地形实时交互算法

邹刘磊 徐安琦 张震 朱洪锦 范洪辉

摘要：针对动态场景的实时交互式渲染中，离散碰撞检测算法导致的“穿模”现象，提出一种新的顶点与地形实时交互算法，并利用空间数据结构进行加速。算法利用顶点与模型表面多边形的空间位置关系，首先计算顶点在当前模型移动后的位置，然后计算本次移动与其他模型的相交情况，将移动沿路径依次分解到每个经过的面上，以此计算移动轨迹与终点位置。算法可通过层次包围盒、八叉树、KD树等各类现有的空间数据结构进行加速。使用八叉树，设计并实现了简易的场景漫游与寻路，以此为实验环境进行性能分析。实验数据证明，该方法能够满足实时性的要求，并且具有较高精度。

关键词：实时交互式渲染;空间数据结构;碰撞检测

计算机图形学领域中，创建有效的视觉交流是研究的核心。其中，在实时渲染的三维场景中，涉及大量人机交互，交互时给予用户以类似现实世界的视觉感受，是必不可少的。

实时渲染系统中，针对物体间交互的常用方法主要依赖动态碰撞检测算法[1，2]。动态碰撞检测主要可分为两类，一类是连续碰撞检测，另一类是离散碰撞检测。离散碰撞检测考虑经过一段时间间隔后，物体间的碰撞检测问题，因此，在复杂场景中存在穿模现象。连续碰撞检测算法则能很好的计算运动中的碰撞问题，但其速度较慢。因实时性的要求，目前实时渲染中使用的技术主要为离散碰撞检测。离散碰撞检测中大部分算法都依赖于空间数据结构加速。

空间数据结构[3]是将几何体组织在多维空间中的一系列数据结构。空间数据结构的组织通常是层次结构的，用层次结构的实现方式，使得几何体访问速度得到提升。空间数据结构可以用于很多实时渲染相关操作的加速查询中，如相交测试、碰撞检测、裁减算法、场景管理、光线追踪等。

常见的用于动态三维场景的空间数据结构有：BSP树及其变体[4]、八叉树[5]、层次包围盒[6，7]等。其中，层次包围盒对物体本身所在空的进行划分，将物体分层放入几何特性更为简单的包围盒，用包围盒来进行初步的碰撞检测。BSP树、八叉树是基于空间分割思想[5]的空间数据结构，从整个空间的角度进行细分。

为了解决存在多个复杂模型的三维场景中，以某一个模型表面一点为起点沿某一模糊方向移动一定距离后，如何确定终点位置、如何确定移动轨迹的问题，本文提出一种空间数据结构加速的顶点与地形实时交互算法。该算法有效的解决了离散碰撞检测中的穿模问题，并能满足实时性要求。算法核心思想为：根据三维模型表面多边形与起点的空间位置关系，将移动分解到每个多边形上，以此计算移动轨迹与终点位置。算法在查找相邻三角形、不同物体间转移时，可利用空间数据结构，进行进一步的加速。

1     空间数据结构加速的顶点与地形实时交互算法

提出一种顶点与地形实时交互算法，并利用空间数据结构加速。该算法要求在可移动的空间内，网格模型没有孔洞或其他缺陷。可通过孔洞修补[8，9]对模型进行预处理，以达到此要求。算法将移动沿路径依次分解到每个经过的多边形上，下文以三角形网格模型为例。

上述步骤中，初始的S不可与F所在平面垂直，具体原因为S与F所在平面垂直时，并非为沿物体表面移动，而表示一种离开表面的移动趋势。

如上所述，其中步骤2、步骤3中的计算，可利用空间分割、层次包围盒等空间数据结构进行加速。实验证明，算法利用空间数据结构后，能十分有效的减少时间开销。

算法可用于悬浮于物体表面的顶点移动，此时需要存储顶点与所属三角形的初始间隔距离，并在各步骤中考虑此距离。算法可拓展至三角形图元以外的模型数据存储方式，此时，仅需将移动分解至单个面上。算法可用于计算移动路径，只需在循环中每次记录位置即可。

1.1   单个模型内移动

步骤2.1中，所在三角形F，分为三种情况。其一，O与三角形顶点重合时，则F为所有共有此顶点的三角形。其二，O位于三角形边上时，则F为共有此边的所有三角形。其三，O位于某三角形内时，则F为该三角形。

如步骤2.3中所述的交点，每次计算时有且仅有两个点。因为不考虑S与F法线平行的情况，所以两个点分别令OO与S夹角大于或小于90°。依据S的趋势，O需满足：OO与S夹角小于90°。

上述算法中，步骤2.3中计算交点时，若O与F中三角形顶点重合时，可能出现F中的某一个三角形的边位于平面P内。此时，O的位置须根据移动限制进行计算，亦可延后至步骤3计算。如算法用于控制游戏角色时，模拟重力系统，此时O的选择为高度较低的点。

1.2    多个模型间移动与移动限制

步骤3中碰撞检测时，若存在数个可在其表面移动的物体，物体间移动的计算方式，其流程如图3所示，其文字描述具体步骤如下。

步骤3.1：如果场景中存在其他允许在其表面移动的模型，且OO（不含O点）与这些模型存在交点（若O、O均属于此时相交三角形所在平面或与三角形边有重合，则碰撞检测时不考虑此三角形）;则执行步骤3.2;否则步骤结束。

步骤3.2：C=与O距离最短的交点。

步骤3.3：找出C在相交的模型上所在的所有三角形，计算P与这些三角形边的交点。

步骤3.4：如果交点中存在满足K的法线与交点属于的三角形所在的面的夹角小于90°的点;则S=normalize（线段OC与交点属于的三角形所在的面夹角最小者-O）;M=交点所在模型;O=C。

步骤3.3中所述的所有三角形与步骤2.1中情况类似，兩者需要遍历M上的所有三角形，遍历的过程可通过空间数据结构加速。步骤3.1中的碰撞检测，也可以使用空间数据结构加速。

上述步骤3中所述的移动限制，需根据不同系统中的要求进行相应变化，可以为：与其他不可在其表面移动的物体产生碰撞、高度限制、边界限制、移动时仰角限制等，该步骤有可能需要算法提前结束。比如：场景中移动存在边界限制情况下，OO与边界相交时，如果O点不与OO、边界的交点重合，则将交点值赋给O，否则算法提前结束。

2     实验与性能分析

基于上文描述的方法，使用八叉树进行场景

管理，笔者设计并实现了简易的场景漫游与寻路。以此，对八叉树层数为4、模型相同（400个顶点、722个三角形）、模型数量不同时的计算速度进行了测试。十组测试数据处理后如表1所示。

同时，对单个模型下（400个顶点、722个三角形），八叉树最高层数对计算速度的影响进行了测试，数据如表2所示。

从数据显示可知，模型个数对算法速度有较大影响，并且最短时间与最长时间差异较大，分析后可知，其主要原因为不同模型间的碰撞检测时间消耗差异较大，并带有一定随机性。八叉树最高层数对算法有较大影响，空间划分越细，速度越快。因此可知，算法性能主要由空间数据结构决定，空间数据结构为算法的主要的性能瓶颈。

3     结论

针对交互式实时渲染中，顶点与复杂三维场景交互时，常规的离散碰撞检测易发生穿模现象，提出一种空间数据结构加速的顶点与地形实时交互算法。算法首先计算顶点在当前模型移动后的位置，然后计算本次移动与其他模型的相交情况，有效解决了动态场景中的穿模问题，并能够满足实时渲染的性能要求。实验证明，算法性能主要依赖空间数据结构加速后，数据的查询速度。

参考文献：

[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 BVH-based 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.

Abstract： 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.

Key words： real-time interactive rendering; spatial data structure; collision detection

責任编辑    张志钊