一种针对复杂曲面的快速自由交互拾取算法

熊宇龙，李维诗

一种针对复杂曲面的快速自由交互拾取算法

熊宇龙，李维诗

(合肥工业大学仪器科学与光电工程学院测量理论与精密仪器安徽省重点实验室，安徽 合肥 230009)

三维模型的交互拾取作为最直观的人机交互方式，在各个领域都有广泛地应用，如几何建模、3D游戏和有限元分析等。针对目前含有复杂曲面模型的拾取效率和拾取自由度低等问题，提出了一种对复杂曲面的快速自由交互拾取算法。首先采用一种类似画刷的工具，对画刷在屏幕中移动的路径进行离散，接着对每一个离散点应用基于BVH结构的单点拾取法来拾取复杂曲面，然后用2个哈希结构降低算法的响应时间，最后对该算法进行了验证。

图形交互；交互拾取；复杂曲面

三维模型的交互拾取作为最直观的人机交互方式，在各个领域都有广泛地应用，如几何制图、3D游戏和有限元分析等。随着图形技术和图形硬件的快速发展，交互式图形应用中三维场景的复杂度越来越高，在图形交互领域中，能快速、准确地提取到目标模型对其后续进行分析、修改、增删等操作具有非常重要的意义。

在现有的研究中，对于三维模型进行鼠标交互拾取的算法主要有以下几种：

(1) 射线拾取法(ray-casting)[1-5]。该方法将屏幕二维坐标转化为三维环境中的射线，通过射线与图元求交的方法来检测三维环境中散落的图元，最终根据深度信息确定拾取到的图元。该方法拾取的准确度高，但针对复杂模型，该方法的效率较低；

(2) 基于缓冲区的拾取方法[6-7]。该方法在需要进行鼠标拾取时，将所有的三维图形重新渲染到缓冲区，并在缓冲区中给每个图元一个特定的索引号，将鼠标点击的屏幕二维坐标作为索引值，在缓冲区中拾取对应的图元。由于在拾取时需对图形进行重新渲染，导致该方法拾取速率不及射线拾取法；

(3) 基于视口空间的拾取法[8]。该算法根据视口变换将所有三维环境中的图形包围盒投影到二维空间，在二维空间中进行拾取。该方法的缺陷和基于缓冲区的方法一样，在拾取时，三维环境向二维空间中投影的时间随着模型的复杂度呈线性增长，导致拾取速率低。

针对交互拾取效率较低的问题，文献[1]首先计算模型的包围球，然后用包围球和射线进行求交，一定程度上提升了拾取的效率，但该方法有可能造成图形的误拾取；文献[2]采用分层次求交的形式，先将射线与包围盒求交，再对包围盒内的三角形求交，一定程度上解决了网格模型拾取效率问题，但对于大型复杂曲面模型，用该方法所生成的包围盒较多，拾取效率得不到保障；文献[5]通过Three.js中自带的组合功能来合并已有的几何体，从而达到单次拾取多个几何体的目的；文献[3,9-11]将拾取、渲染等计算过程放到GPU上，与使用CPU计算的方法相比，拾取效率有一定程度上的提升，但仅限于鼠标的单点拾取，对于复杂曲面的拾取效率仍较低。

为了解决上述问题，本文首先介绍一种基于表面积启发式(surface area heuristic，SAH)方法的结构单点拾取算法(bounding volume hierarchy，BVH)；然后在单点拾取算法的基础上，提出了一种类似画刷工具的快速自由拾取算法；最后，验证了该算法的自由性和低延时性。

1 鼠标单点拾取算法

1.1 射线拾取原理

将三维环境中的几何模型需要经过视点变换、投影变换、透视变换、视口变换4个步骤被投影到二维屏幕上，并将原模型所在的物体坐标系转换到屏幕所在的窗口坐标系上，如图1(a)所示。上述过程可由一个变换矩阵来表示，称作相机综合变换矩阵(viewing-modeling-projection-viewport transformation，MVPW)。因此从屏幕拾取目标实体的过程可以看作是上述过程的逆过程，即通过MVPW的逆变换，将屏幕上的二维坐标点转换为物体坐标系中的一条射线，然后通过射线与三维空间中自由曲面求交的方式来确定具体拾取的曲面。如图2所示，鼠标所拾取的曲面为4。

图1 坐标系变换((a)物体坐标系到窗口坐标系；(b)窗口坐标系到物体坐标系)

图2 射线拾取原理

虽然采用该方法能准确地拾取到自由曲面，但随着三维空间中曲面数量的增加，射线和曲面作相交测试所花费的时间呈线性增长，其时间复杂度为()，对于大型复杂曲面的交互拾取延迟高、响应时间慢，因此亟需一种快速、自由的拾取方法来解决大型复杂曲面的拾取问题。

通常使用基于包围体的数据结构和层次空间分解(hierarchical spatial decomposition，HSD)技术来解决上述难题。这些结构包含k-d树[12]、基于球的分割树[13]、轴对齐包围盒(axis aligned bounding box，AABB)树[14]、k-点树[15]、方向包围盒(oriented bounding box，OBB)树[16]等。上述结构可将算法的时间复杂度优化为(logN)，其中为树节点的分支数。为了达到系统所需求的响应时间，并尽可能简化数据结构，本文采用基于SAH方法的BVH结构，该结构在模型导入预处理阶段时建立，不会随场景、视点的变化而重新构建，且时间复杂度为(log2)，符合本文所需的实时性要求。

1.2 基于BVH结构的射线拾取法

BVH数据结构实际上是一棵二叉树，每个节点最多包含2个子节点。该结构中，所有的节点只可能是以下2种类型：叶子结点(leaf node)或内部节点(internal node)。其中叶子结点保存的是唯一的几何元素及包围盒且该节点不再有子节点；内部节点有的包围盒能将其所有子树中的几何体包围起来，并按照特定划分方式划分出2个子节点，如图3所示。

图3 BVH结构示意图

根据上述性质，可得BVH结构的节点定义如下：

其中，leftChild和rightChild为该节点的左右子节点，若该节点为叶子节点，则上述2项值为空(Null)；bx为当前节点的包围盒；nPrimitives为当前节点所包含的几何元素数量，当该节点为叶子节点时，该值为1；s为具体的几何体，只有当该节点为叶子节点时才有具体的值，其他情况均为空(Null)。

BVH结构包含构建和遍历2个阶段。

构建工作考虑的是如何构造一颗有效描述当前场景信息的二叉树。该过程的关键问题是如何将毫无规律分布在场景中的曲面进行划分，即决定左子树与右子树上包含哪些曲面。由于是在三维空间中对曲面进行划分，为了将问题简化，可以采用分而治之的方法，即决定在哪个坐标轴上进行划分。该方法与场景中曲面片在各个轴上分布的“散度”有关，即若某个轴上，曲面分布的跨度最大，则沿该轴进行划分。

确定了划分原则后，还需选用适当的划分方法，才能发挥该结构最大的作用。本文中选用的划分方法为表面启发式算法。该算法根据物体在划分轴分布的跨度，将该轴平分为个区域，根据代价公式计算出每一个块分割的代价，并选择代价最低的块进行分割及迭代，直到每一个曲面片都被划分到唯一的一个BVH叶子结点中[17]。代价公式为

其中，为当前节点；和分别为左右子节点；()为节点的包围盒面积；N为节点的物体数量；K和K分别为遍历和单次相交测试的代价。在构建数据结构的过程中，通过最大限度地降低划分代价来实现高渲染效果。SAH算法不能完全做到曲面片不重叠或划分后绝对均匀，但其每一次划分都是选取当前情形下的最优方案，因此性能远高于中点划分法和等量划分法。图4为SAH算法的划分示意图，图中矩形代表节点包围盒的大小，最佳的分割位置如图所示。

图4 基于SAH方法的物体划分示意图

Fig. 4 Object segmentation based on SAH

BVH结构的遍历与普通二叉树的遍历一样，采用深度优先遍历法，即通过射线与左右节点进行相交测试，最终找到的叶子节点即为所要拾取的曲面片。由于遍历与二叉树的遍历方法相同，所以时间复杂度为(log2)，其中为树的节点数量。单点拾取算法的具体流程图如图5所示。

基于单点拾取算法的拾取原理，可将其引申为OpenGL中的拾取方法，即在需要拾取的区域左上角按下鼠标左键，将鼠标拖动到目标区域的右下角松开左键，记录这2个点并以此生成一个矩形框，落在框内的物体即为拾取到的物体。按照图1(b)的转换流程，屏幕上的矩形经MVPW逆变换后会生成一个截锥，锥体的生长方向由当前的视点决定。用该截锥与BVH结构中的各曲面包围盒求交，有交集的即为拾取到的曲面。拾取过程如图6所示。

图5 单点拾取算法流程图

图6 矩形拾取示意图

2 鼠标快速拾取算法

鼠标单点拾取算法，适用于含有少数曲面模型的低延时性交互拾取。但对于大型复杂模型，如飞机的机翼(约3 705个曲面)、汽车的车门(约20 735个曲面)等，若用鼠标逐个单击拾取，其效率较为低下；矩形拾取的效率较高，但是自由度较低。因此需要一种快速、自由拾取多个曲面的方法，提升对复杂曲面拾取效率与自由度。

2.1 画刷拾取原理

为了满足自由拾取的需求，可将需要拾取区域的屏幕二维点集拟合成一条光滑的曲线，曲线经过的部分即为需要拾取的部分。由此联想到Windows系统下的画刷工具，首先对画刷工具的宽度进行设置，然后鼠标按下后在屏幕上绘制的轨迹与曲面相交的部分即为需要拾取的部分。图7中被拾取到的曲面为4～9。

图7 画刷拾取示意图

与单点拾取和矩形拾取不同，画刷在屏幕上绘制的拾取轨迹可为任意图形，若要将该图形经过MVPW逆矩阵投影到三维空间中会比较复杂且耗时较长。因此，不能单纯沿用图1(b)所示的转换方式。

孙鑫在《VC++深入详解》中介绍了一种在MFC框架中实现画图功能的方法，其利用MFC对消息的响应机制，将绘图过程的程序写在响应函数OnMouseMove中，根据个人电脑配置的不同，该函数在鼠标移动的过程中每隔一定时间响应一次。因此，对于复杂轨迹的绘制可离散成一些小段直线首尾相接连成的组合线，给出画刷的宽度后，相当于绘制一系列以鼠标轨迹为中心，画刷宽度为半径的圆。

本文利用上述方法并结合单点拾取方法，先将每一小段直线根据指定的离散度离散成一些列点，再对每一个离散点运用单点拾取原理，即可实现画刷拾取。画刷的宽度和离散度相关系数如图8所示。

图8 画刷宽度和离散度

2.2 画刷拾取算法优化

由于单点拾取可将拾取到的曲面压入到拾取队列中，若将所有离散点所对应的曲面拾取到拾取队列之中，将导致队列中包含多个重复曲面，其不仅消耗大量的系统内存，还给后续拓扑关系的建立、曲面分析等带来困难。

为解决上述问题，本文引入了三维实体的哈希表，用来记录已拾取过的几何实体。因此在二维点所对应的曲面片进入拾取队列之前，先通过哈希表判断该曲面是否已存在于队列中。若存在，则略过该点；反之，将其对应的曲面片压入拾取队列中。

为了提升程序的性能，还引入了储存屏幕像素坐标点的哈希表，在鼠标轨迹反复经过同一片区域时，程序不进行任何操作，可节省大量单点拾取的时间。在当前场景经过平移、旋转和缩放等操作后，将该哈希表清空。图9为画刷拾取的流程图。

图9 画刷拾取流程图

3 曲面拾取结果

本文在配置CPU：Intel(R) Xeon(R) CPU E5-1650 v4及GPU：NVIDIA Quadro M2000的电脑上，基于Visual Studio 2013的平台环境以及采用MFC架构和C++语言进行编程，实现上述的拾取算法。图10(a)为单点拾取的结果，其中蓝色网格部分为拾取到的曲面；图10(b)为采用单点拾取算法拾取50次曲面的单点响应时间，图中橙色直线为50次拾取的算法平均响应时间(ms)，由此可知该算法满足低延时性拾取的需求。

图11(a)为矩形拾取结果，从图中可知矩形拾取算法能一次性拾取到大量的自由曲面；图11(b)为矩形拾取曲面数与其响应时间之间的关系。由图可知，随着矩形拾取框选的曲面数量增加，算法所需的响应时间呈线性增长趋势，这主要是由截锥和BVH结构中包围盒求交的次数增多所导致的。

图10 单点拾取算法验证((a)拾取结果；(b)算法响应时间)

图11 矩形拾取算法验证((a)拾取结果；(b)算法响应时间)

图12(a)为画刷拾取结果，从图中可知，与矩形拾取相比，画刷拾取具有更大的自由度，但拾取效率不如矩形拾取；图12(b)为画刷拾取曲面数与其响应时间之间的关系，与矩形拾取相比，画刷拾取随拾取曲面数量的增加，响应时间上升的趋势不明显，主要是因为画刷拾取是分时段进行的，但由于需对画刷拾取的路径进行离散，所以在所拾取曲面较少的情况下，其响应时间与矩形拾取相比没有优势。

图12 画刷拾取算法验证((a)拾取结果；(b)算法响应时间)

4 总 结

本文介绍了一种采用基于SAH方法的BVH结构的鼠标单点快速拾取算法，并在此基础上提出了画刷拾取方法。该方法与OpenGL中的矩形拾取方法相比，在同一时间内拾取的曲面数量较少，且不支持拾取点云数据，但该方法的拾取自由度高，可由用户设置画刷的宽度和拾取路径的离散密度，对画刷在屏幕上任意扫掠路径下的曲面进行拾取。经验证，该画刷拾取方法满足复杂曲面拾取的自由性和低延时性。

References)

[1] 姚继权, 李晓豁. 计算机图形学人机交互中三维拾取方法的研究[J]. 工程设计学报, 2006, 13(2): 116-120.

YAO J Q, LI X H. Research on 3-dimension pick-up of human-computer interaction in computer graphics[J]. Journal of Engineering Design, 2006, 13(2): 116-120 (in Chinese).

[2] 陈煜, 林玮. Web3D引擎中三维图形对象拾取的算法与实现[J]. 工程图学学报, 2011, 32(6): 82-88.

CHEN Y, LIN W. The algorithm and implementation of picking 3D figure by Web3D engine[J]. Journal of Engineering Graphics, 2011, 32(6): 82-88 (in Chinese).

[3] 张嘉华, 梁成, 李桂清. GPU三维图元拾取[J]. 工程图学学报, 2009, 30(1): 46-52.

ZHANG J H, LIANG C, LI G Q. 3D primitive picking on GPU[J]. Journal of Engineering Graphics, 2009, 30(1): 46-52 (in Chinese).

[4] LEE A, JANG I. Mouse picking with ray casting for 3D spatial information open-platform[C]//2018 International Conference on Information and Communication Technology Convergence (ICTC). New York: IEEE Press, 2018: 649-651.

[5] 余莉. 基于Three.js的拾取方法的研究[J]. 计算机时代, 2020(6): 61-63, 66.

YU L. Research on Three.js based pick-up method[J]. Computer Era, 2020(6): 61-63, 66 (in Chinese).

[6] 王亚平, 余柯, 罗堃. 在OpenGL中一种新的拾取方法及其应用: 基于对象缓冲区的选择拾取方法[J]. 工程图学学报, 2003, 24(2): 60-65.

WANG Y P, YU K, LUO K. A new method of pick object in OpenGL and application—the method of pick object based on object-buffer[J]. Journal of Engineering Graphics, 2003, 24(2): 60-65 (in Chinese).

[7] 马梓翔, 周顺, 李青元, 等. 基于虚拟倒序绘制-像素着色检测的图形要素拾取方法[J]. 计算机应用, 2014, 34(S2): 243-245, 252.

MA Z X, ZHOU S, LI Q Y, et al. Generic graphical object picking method based on virtual reverse order drawing and pixel colored detection[J]. Journal of Computer Applications, 2014, 34(S2): 243-245, 252 (in Chinese).

[8] 朱明亮, 董冰, 王祎, 等. 三维场景中基于视口空间的拾取算法[J]. 工程图学学报, 2008, 29(2): 94-97.

ZHU M L, DONG B, WANG Y, et al. Algorithm for picking in 3D scenes based on viewport space[J]. Journal of Engineering Graphics, 2008, 29(2): 94-97 (in Chinese).

[9] 叶美芬, 郑贵洲. 三维点云数据拾取与可视化技术[J]. 测绘与空间地理信息, 2019, 42(7): 134-137.

YE M F, ZHENG G Z. Technology of 3D point cloud data picking and visualization[J]. Geomatics & Spatial Information Technology, 2019, 42(7): 134-137 (in Chinese).

[10] ZHAO H L, JIN X G, SHEN J B, et al. Fast and reliable mouse picking using graphics hardware[J]. International Journal of Computer Games Technology, 2009, 2009: 1-7.

[11] GU G, KIM D. Accurate and efficient GPU ray-casting algorithm for volume rendering of unstructured grid data[J]. ETRI Journal, 2020, 42(4): 608-618.

[12] DE BOI I, RIBBENS B, JORISSEN P, et al. Feasibility of kd-trees in Gaussian process regression to partition test points in high resolution input space[J]. Algorithms, 2020, 13(12): 327.

[13] BENITEZ A, DEL CARMEN RAMIREZ M, VALLEJO D. Collision detection using sphere-tree construction[C]//The 15th International Conference on Electronics, Communications and Computers (CONIELECOMP’05). New York: IEEE Press, 2005: 286-291.

[14] 邓峻生, 毛世峰, 刘旭峰, 等. 基于AABB树的聚变堆形变部件碰撞检测算法[J]. 计算机系统应用, 2018, 27(11): 161-167.

DENG J S, MAO S F, LIU X F, et al. Collision detecting algorithm for deformable components in fusion reactor based on AABB tree[J]. Computer Systems & Applications, 2018, 27(11): 161-167 (in Chinese).

[15] WU H Y, SHU Z M, LIU Y G. Study based on hybrid bounding volume hierarchy for collision detection in the virtual manipulator[J]. Applied Mechanics and Materials, 2013, 454: 74-77.

[16] TANG L, SONG W G, HOU T C, et al. Collision detection of virtual plant based on bounding volume hierarchy: a case study on virtual wheat[J]. Journal of Integrative Agriculture, 2018, 17(2): 306-314.

[17] DMITRY S, DENIS B, DANILA U. Real-Time SAH BVH construction for ray tracing dynamic scenes[EB/OL]. [2021-01-26]. http://graphicon.ru/html/2011/conference/gc2011Sopin.pdf.

A fast and free interactive picking method for complex surfaces

XIONG Yu-long, LI Wei-shi

(Anhui Province Key Laboratory of Measuring Theory and Precision Instrument, School of Instrument Science and Opto-Electronics Engineering, Hefei University of Technology, Hefei Anhui 230009, China)

As an intuitive way for human-computer interaction, the interactive picking of 3D models is widely used in various fields, such as geometric modeling, 3D games, and finite element analysis.To address the problems of low picking efficiency and low degree of picking freedom of complex surface models, a fast and free interactive picking method for complex surface model was proposed. This method employed a brush-like tool to discretize the moving path of the brush in the screen, applied the single point picking method based on BVH structure to pick up the complex surface for each discrete point, and then utilized two hash structures to reduce the response time of the algorithm, and finally the algorithm was verified.

graphic interaction; interactive picking; complex surface

TP 391

10.11996/JG.j.2095-302X.2021060957

A

2095-302X(2021)06-0957-06

2021-04-21；

2021-06-17

国家自然科学基金(51927811)

熊宇龙(1995-)，男，湖南常德人，硕士研究生。主要研究方向为复杂曲面与大尺寸测量技术。E-mail：xyl147033@163.com

李维诗(1970–)，男，山东烟台人，教授，博士，博士生导师。主要研究方向为反求工程、复杂外形自动检测中的几何建模与计算等。E-mail：weishili@hfut.edu.cn

21 April，2021；

17 June，2021

National Natural Science Foundation of China (51927811)

XIONG Yu-long (1995–), male, master student. His main research interests cover geometric modeling and calculation in automatic detection of complex surface. E-mail：xyl147033@163.com

LI Wei-shi (1970-), male, professor，Ph.D,. His main research interests cover reverse engineering, geometric modeling and computing in automatic inspection of complex shapes, etc. E-mail：weishili@hfut.edu.cn