三维场景地面坐标拾取的射线投影算法
收稿日期：2013-06-23；修回日期：2013-10-17。作者简介：李奇峰（1988－），男，河南济源人，
硕士生，主要研究方向为水利信息技术。E-mail ：lqfisme@126．com 文章编号：1673-
6338（2014）01-0093-04三维场景地面坐标拾取的射线投影算法
李奇峰，郭同德
(郑州大学水利与环境学院，河南郑州
450001)
摘要：简述了虚拟三维场景中对象拾取及地面坐标拾取的基本原理，分析了实时地面坐标拾取的研究背景和现状；提出了基于射线投影的地面坐标拾取算法。该算法利用射线在水平面的投影确定可能与之相交
的三角形集合，从而将线面求交的搜索空间由二维降至一维，使算法的时间复杂度由基本方法的O （n 2
）降
至O （n ）。基于Direct3D 和VC ++开发了相应试验系统，验证了该算法的正确性和效率。关
键
词：三维场景；地面坐标；实时拾取；射线投影；三维量算
中图分类号：P208；TP391．41
文献标识码：A
DOI 编码：10．3969/j．issn．1673-6338．2014．01．020
The Algorithm of Ground Coordinates Picking in
3D Scene Based on Projection of Ｒay
LI Qifeng，GUO Tongde
(College of Water Conservancy and Environmental Engineering，Zhengzhou University，Zhengzhou 450001，China )Abstract:The algorithms concerning the real-time picking of ground coordinates in 3D scene were investigated in
this paper．By setting a reference projection plane for terrain，the correspondence between the triangles intersected with a given ray and the triangles intersected with the projection line of the ray was established．Based on the corre-spondence mentioned above，an algorithm for picking the ground coordinates was proposed．The testing space of in-tersection between spatial lines and triangles was reduced to one-dimension from two-dimension，and its time com-plexity was improved to O(n )from O(n 2
)．The correctness and the efficiency of the algorithm were tested by a sys-tem developed by using Direct3D and VC ++．Key words:3D scene;ground coordinates;real-time picking;projection line;3D measurement
三维场景地面点坐标的实时拾取，是指根据鼠标在计算机屏幕上所指位置，实时地反算出对应的三维坐标。这是三维GIS 的一个基本操作，也是很多其他高级操作的基础，比如各种几何量算、地物的选取、动态标注等。三维渲染过程须将空间坐标投影为屏幕坐标，而投影变换是不可逆的，这是坐标反算的困难所在。基于当前三维GIS 的可交互性和空间分析能力有待提高的事实
［1］
，研究实时高效的三维场景坐标拾取算法显得尤为重要。空间对象的拾取比较简单。常规的做法是：先将鼠标所指点的屏幕坐标转换为投影窗口坐标，过投影中心向该点引一条射线，将该射线通过取景变换的逆变换转换至世界坐标空间；在世界坐标空间判断该射线与所有空间对象（或其包围盒）的相交情况，若无相交则没有选中对象，否则
记录所有相交对象的索引；再对这些空间对象按
照到投影中心的距离排序，最近者即为目标对象。若将该方法用于三维场景地面坐标的拾取—通过遍历地形三角格网做相交测试，而后依照深度排序———因为地形三角格网数量庞大，故很难满足实时性要求。所以，尽量减少测试格网的数目是三维场景地面坐标实时拾取技术的关键任务。
何健鹰等［2］
给出了一种分块的方法，即先将整个三维地形均匀划分为若干空间四边形区域，每块区域中包含若干三角形格网，先对各分块做相交测试，抛弃不相交的块，再在相交的块中遍历
所有三角形格网同射线做相交测试；朱明亮等［3］
通过将地物投影到视图空间，然后在视图空间（平面）解决拣选问题，相当于通过可视剪裁缩小了搜索范围。这两种方法在一定程度上缩小了线面求交的搜索空间，但其搜索空间仍是二维的。
2014年第31卷第1期
测绘科学技术学报
Journal of Geomatics Science and Technology
2014Vol．31No．1
而刘彬等人［4］通过人机交互方法，适当设置参考平面的高度，将问题转化为投影窗口到参考平面的可逆变换，而后计算平面坐标，该方法虽直观，但额外的人机交互使其不具备实时性；刘力强等人［5］给出了一种基于正交平行投影的三维拾取算法，然而在三维渲染系统中通常采用的投影模式是中心投影。
本研究给出了一种射线投影算法。用射线在参考平面的投影线来确定搜索范围和搜索次序，将线面求交的搜索空间降至一维有序空间，提高了三维场景地面点坐标拾取的效率。该方法同文献［2］中的分块思想相结合，可满足超大规模地形渲染系统中实时拾取的需求。
1射线投影快速求交算法
1．1算法原理和思路
下面讨论相交测试的搜索空间。参照图1，首先给出以下两个引理。
引理1：DEM上的空间△ABC与其在xOy平面上的投影△A1B1C1相互唯一确定。
引理2：直线L与空间△ABC相交，则L在参考平面的投影线L1与△ABC的投影△A1B1C1相交，反之不成立。
图1空间三角形与参考面对应三角形
引理1可由DEM的单值性得证。下面证明引理2。
证明：设有直线L，空间△ABC，二者相交于点o，二者在参考平面的投影分别记为L1和△A1B1C1。
由于点o是L与△ABC的交点，即：点o既在L上，又在△ABC中（也可能在边缘上），所以点o 的投影o1必在L的投影L1上，同时也在△ABC的投影△A1B1C1中。
从而o1必为L1与△A1B1C1的交点。
由投影运算的逆运算解的不唯一性，可知前者非后者的必要条件。
证毕。
由以上引理可以得出以下推论。
推论：记空间直线L与DEM相交的三角形面元集合为S，记S在参考平面（xOy）的投影三角形集合为S1，记L在参考平面的投影线为L1，记参考平面上与L1相交的三角形集合为S2，则S1为S2的子集。
由文献［6-8］容易获取从投影中心P到鼠标所指屏幕位置o所确定直线在世界坐标空间的表达式（即引理2中所指直线L，该直线也即视线）。由前述推论，按如下方法确定相交测试范围：1）为地形建立参考平面（如包围体的底面）；2）根据直线L确定其投影线L1；3）在投影平面上找出与L
1
相交的三角形集合S2；4）最后确定与S2对应的原始DEM格网集合S0，则S0构成搜索空间。该搜索空间是一维的，如图2（a）所示。
为了进一步缩小搜索空间，先为整个地形建立一个长方体包围盒，将视线同该包围盒做相交测试，若没有交点，则说明当前视线未与该地形块相交；若有2个交点，如图2（b）所示，则这2个交点在参考平面的投影确定的线段（s'e'）定义了需要测试的射线范围；如果只有1个交点（e），如图2（c）所示，则该交点及相机所在位置（投影中心P，基于一致性考虑，这里同样记为s）在参考平面的投影确定的线段定义了射线范围。该范围的确定受启发于计算机图形学中的光线跟踪算法［9］。
（a）算法的搜索空间
（b）2个交点的情况
（c）1个交点的情况
图2搜索空间
49测绘科学技术学报2014
年
1．2算法流程及实现细节
算法流程如下所述。
1）根据当前鼠标指示的屏幕位置，找到投影窗口上的对应点O，求出摄像机位置P到点O确定的射线在世界坐标系下的表达式。
2）计算射线PO同地形块长方体包围盒的交点，确定点s和点e，进而确定线段se在参考平面的投影线段s'e'，参考平面内所有与s'e'相交的平面三角形对应的空间三角形构成了射线求交的搜索空间，如图2所示。
3）沿投影线段s'e'方向在搜索空间中搜索与射线PO相交的空间三角形格网，若无相交格网，则鼠标没有指向当前地形范围，转下一步，若有相交格网，则交点坐标即为拾取点的三维坐标。
4）算法结束。
关于求取PO在世界坐标空间的表达式的技术细节，文献［6-8］中有详细阐述；文献［2，10］给出了求解空间三角形与空间射线交点的方法；需要指出以上算法流程的2）和3）是协同执行的。相交测试沿s'e'方向进行，根据空间三角形与投影面上三角形的对应关系，第1个与射线相交的三角形就是距视点最近（可见）的三角形，测试得以结束，这样既免去了后继的相交测试，也不必再作深度排序，拾取效率得以大幅提高。
假设地形格网按照如图3方式组织，即将规则格网DEM中的每个规则格网按照西南东北方向分为两个三角形（依西北东南方向分割的情况可类比）。
图3搜索空间“准则”的确定
假设射线方向均自左向右（自西向东），k表示s'e'的斜率。分情况讨论如下。
1）0＜k≤1时，以图3中L
1为例，自左向右
确定L1同DEM格网在南北方向上的划分线的交
点，而每一个交点必然属于相邻（有一条公共边）
两个三角形格网，则这两个三角形格网对应的空
间三角形必然包含于搜索空间。
2）k＞1时，以图3中L
2
为例，自下而上确定
L
2
同DEM格网在东西方向的划分线的交点，每一
个交点必然属于两个相邻三角形格网，则这两个
三角形格网对应的空间三角形必然包含于搜索空
间。
3）－1≤k≤0时，以图3中L
3
为例，自左向
右自上而下确定L3同DEM格网在南北和东西方
向上的划分线的交点，每一个交点同样属于两个
相邻三角形格网，则这两个三角形格网对应的空
间三角形也必然包含于搜索空间。
4）k＜－1时，同3）。
图3中黑圈代表摄像投影同相关规则格网
DEM划分线的交点；对k不存在（无穷大）的情
况，可以令k取绝对值小于10－10的任意数；当射
线投影通过规则格网DEM南北方向和东西方向
划分线的交点时，需要将与该交点相关的所有空
间三角形加入搜索空间；上述每种情况，射线投影
的起始位置和结束位置所在的规则格网DEM所
包含的两个空间三角形都必须加入搜索空间。
1．3算法的时间复杂度
假设需要考虑的地形块大小为n?n（即该地
形块的规则格网DEM有n?n个控制点），则其中
包含三角形的数目为（n－1）?（n－1）?2。不
考虑从屏幕坐标到世界坐标空间射线的计算量，
也不考虑求交空间三角形与空间射线求交点的复
杂性，将其视为单位时间。
传统方法，例如文献［2-4］，即使采用了优化，
但最终其实质都是在一个二维区域遍历搜索与射
线相交的三角形。显然，此类方法的时间复杂度
为O（n2）。
根据1．2节描述，以k≥0为例，搜索空间的
三角形数目不超过（（n－2）?2+2）个，也即不
超过（n－1）?2个。而最快的情况下，例如摄像
机垂直向下俯视时，可能仅仅需要计算射线与一
个空间三角形的交点。所以，本文算法的时间复
杂度为O（n），当n较大时，该算法的优越性将更
明显。如，文献［2-3］对于512?512规模的地形
块，一次地面坐标拾取操作可能需要解522242次
线面求交问题，而本文算法则不超过1022次，效
率提高500倍之多。当k取值为其他情况时结果
亦然。
59
第31卷第1期李奇峰，等：
三维场景地面坐标拾取的射线投影算法
2算法验证
为了验证上述算法的正确性和效率，本文基于Direct3D和VC++开发了试验系统。试验采用河南省济源市河口村水库的库区地形（规则格网DEM，2049?2049）（如图4所示），在Intel Core（TM）i3－23102．1GHz处理器、2Gb内存、NVIDIA GEFOＲCE GT520Mb显卡配置的PC上测试。将整块地形数据一次性读入内存，加入灯光、材质、纹理、水体等，鼠标拾取响应WM_MOUSEMOVE消息无迟延现象，经测试每秒可进行20次以上拾取运算。
图4河南省济源市河口村水库库区地形
试验系统除了实现实时坐标拾取之外，还做了动态标注、距离量算、高程量算、面积量算、体积量算以及动态可交互淹没分析量算等分析。图5是试验系统中面积量算的截图：图中围着房子的一圈标杆是基于该拾取算法的动态标注；贴着地表的辅助线确定了量测范围；如图中对话框所示，系统不仅计算了选定区域在水平面的投影面积，还计算了其地表面积。
图5量算和标注3结论
1）基于射线投影的快速坐标拾取算法将传统算法遍历二维平面的相交搜索化为沿射线投影线段的一维搜索。这种沿射线投影的搜索是有向的，只要找到一个同射线相交的三角形，其交点即为距相机最近的点，免去了对后继三角形的测试和距离排序。若定义传统算法的时间复杂度为O（n2），则此算法的时间复杂度不超过O（n）。
2）针对本文提出的算法，设计了试验系统。试验结果表明，该算法有较高的计算效率，能胜任较大场景的地面坐标的实时拾取，基于该拾取方法可以完成一系列地形量算与分析。
3）测试系统是针对规则格网设计的，对于动态LOD或静态LOD绘制方式，此算法仍适用。试验系统的开发没有考虑到与虚拟现实技术相结合的双目交互，但本文算法对于文献［11］中的各种虚拟现实化方法同样适用。测试系统采用的是单线程处理，若将多线程并行处理［12］的方式运用到鼠标拣选算法的实现中，其效率将进一步提高。
参考文献：
［1］霍亮，朱王璋，杨辉东，等．三维地理景观多方位一体化表达技术研究［J］．测绘科学技术学报，2013，30（1）：7-9．［2］何健鹰，徐强华，游佳．基于OpenGL的一种三维拾取方法［J］．计算机工程与科学，2006，28（1）：45-46；70．
［3］朱明亮，董冰，王祎，等．三维场景中基于视口空间的拾取算法［J］．工程图学学报，2008，29（2）：94-97．
［4］刘彬，孙勇，高明，等．基于OpenGL三维拾取技术研究［C］∥中国地理信息系统协会第四次会员代表大会暨第十一
届年会论文集．北京，2007：200-206．
［5］刘力强，周明全，耿国华．一种平行透视下的三维拾取方法［J］．西北大学学报：自然科学版，2002，32（1）：40-42．
［6］郑阿奇．DirectX3D游戏编程使用教程［M］．北京：电子工业出版社，2010：53-78；164.
［7］郭艳霞，侯彤璞，杜园园．基于DirectX的三维场景实体的拾取［J］．辽宁石油化工大学学报，2009，19（3）：77-84．［8］阳富民，赵宁，张杰．基于OpenGL的三维窗口裁剪、拾取算法研究［J］．华中科技大学学报：自然科学版，2005，33（4）：
23-26．
［9］ALAN WATT．3D Computer Graphics［M］.3th ed．Beijing：China Machine Press，2005：285-287．
［10］谭晓昱，雷珏，粟光好．鼠标拾取3D物体算法研究及实现［J］．科技向导，2010（14）：100；157．
［11］闾国年，周良辰，盛业华，等．GIS虚拟现实化方法［J］．测绘科学技术学报，2013，30（4）：392-398．
［12］杨硕磊，郝爱民，王莉莉．运用矩阵结构的可并行地形层次细节算法［J］．计算机辅助设计与图形学学报，2011，
23（2）：277-283．
责任编辑安敏
69测绘科学技术学报2014
年