基于室内动静结合分割的射线跟踪加速方法

密闭环境的信道建模在许多应用场景中具有重要作用。在空间内障碍物较多时,传统射线跟踪算法在运算过程中会有无用的求交点次数过多的问题,使得算法的计算效率较低。为此,提出一种基于空间分割的射线跟踪加速方法。该方法根据三维空间中物体的分布情况,合理地结合静态与动态两种空间分割加速方法,大幅度减少了射线与空间内物体的求交点次数,提高了算法的计算效率。仿真分析表明,在相同预测精度的三维环境下,与原始算法对比,使用静态空间分割的射线跟踪算法随着分割等级的提升计算效率提高了至少50.2%;而与只使用静态空间分割的算法对比,使用静态与动态空间分割结合的加速方法的计算效率在已经提高的基础上至少还能提升8.9%。     

基于动态分区的射线跟踪加速方法

射线跟踪模型在3G网络规划中存在计算效率低的问题。分析了当前各种加速方法的不足,提出一种基于动态分区的射线跟踪加速方法。该方法根据城市微小区的建筑物分布情况,动态地划分小区,大大减少了射线与建筑物求交点次数,同时解决了静态分区在复杂建筑物环境下由于分区不均匀导致射线跟踪加速效果差的问题。仿真表明,在相同预测精度下,与静态分区加速方法相比,该方法具有计算效率高的优点。     

基于历史缓存技术的射线跟踪加速算法研究*

通过分析影响射线跟踪效率的因素,提出一种基于历史缓存技术的射线跟踪加速算法,以提高射线跟踪的运算效率。通过建立一个缓存区存储历史信息,用来减少每条射线必须处理的建筑物面的数量和减少计算无效的交点。对提出的算法进行仿真计算,仿真结果证明了这种算法的正确性,有效降低了计算的复杂度。     

基于射线跟踪和Voronoi图的室内定位算法

传统的射线跟踪方法在离线数据采集时需要大量的求交运算,计算效率低,而传统的在线定位需要遍历数据库才能确定目标位置,为此,提出一种提高室内定位运算效率的新方法.该方法利用Voronoi图势力范围特性和局域动态特性,大大减少了离线阶段中射线与物体的求交次数;同时利用Voronoi图一级邻接点的特点,减少了在线阶段的匹配计算量.仿真结果表明了该方法的有效性.     

基于动态物体跟踪的语义SLAM

针对传统视觉SLAM在动态场景下容易出现特征匹配错误从而导致定位精度下降的问题,提出了一种基于动态物体跟踪的语义SLAM算法。基于经典的视觉SLAM框架,提取动态物体进行帧间跟踪,并利用动态物体的位姿信息来辅助相机自身的定位。首先,算法在数据预处理中使用YOLACT、RAFT以及SC-Depth网络,分别提取图像中的语义掩膜、光流向量以及像素深度值。其次,视觉前端模块根据所提信息,通过语义分割掩膜、运动一致性检验以及遮挡点检验算法计算概率图以平滑区分场景中的动态特征与静态特征。然后,后端中的捆集调整模块融合了物体运动的多特征约束以提高算法在动态场景中的位姿估计性能。最后,在KITTI和OMD数据集的动态场景中进行对比验证。实验表明,所提算法能够准确地跟踪动态物体,在室内外动态场景中具备鲁棒、良好的定位性能。     

基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度;其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～ O(n~(1/2)),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向;最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件。     

复杂场景中基于拓扑空间网格的碰撞检测算法

为了提高复杂场景的碰撞检测效率,提出一种基于拓扑空间网格的碰撞检测算法. 由于场景中存在众多形状复杂、尺寸不一且运动状态不同的物体,首先采取场景预处理对空间进行均匀八叉树网格划分,建立物体方向包围盒层次树与空间网格拓扑结构,利用静态大尺寸物体分割策略提升定位精确性,然后在实时检测中利用拓扑空间网格及投影相交测试排除大量不相交物体对,利用层次包围盒算法对潜在碰撞对进行精确检测并计算出碰撞点. 实验结果表明,本算法有效地提高了实时检测的效率,适用于复杂虚拟场景中的碰撞检测.     

USSCD：一个基于均匀空间分割的快速碰撞检测算法

对于存在大量运动物体的虚拟环境，碰撞检测往往成为影响系统计算效率的瓶颈，为提高多体碰撞检测的效率，提出了一个基于均匀空间分割的快速多体碰撞检测算法——USSCD，该算法首先将物体空间均匀分割成一系列单元格，然后在每个单元格，通过基于AVL排序的扫描排除法进行碰撞检测，同时依据物体的分布密度，提出了一个计算单元格尺寸的优化方法，通过一系列实验，测试了USSCD算法的性能，并与I-COLLIDE算法进行比较，实验结果表明，在均匀分布条件下，当物体数量较大时，USSCD的效率高于I-COLLIDE算法，而且，USSCD算法的效率基本不受物体运动相关性的影响。     

动态环境下基于线特征的RGB-D视觉里程计

基于RGB-D的视觉SLAM(同时定位与建图)算法基本都假设环境是静态的,然而在实际环境中经常会出现动态物体,导致SLAM算法性能的下降.为此,本文提出一种基于线特征的RGB-D视觉里程计方法,通过计算直线特征的静态权重来剔除动态直线特征,并根据剩余的直线特征估计相机位姿.本文方法既可以减小动态物体的影响,又能避免点特征过少而导致的跟踪失效.公共数据集实验结果表明,与现有的基于ORB(orientedFAST and rotated BRIEF)点特征的方法相比,本文方法减小了动态环境下的跟踪误差约30%,提高了视觉里程计在动态环境下的精度和鲁棒性.     

雕塑物体的布尔运算

本文提出了一种带有trimmed曲面物体的快速布尔运算算法。算法首先对trimmed曲面在其trimmed区域内离散,并进行离散求交,在离散求交时保证三角形边面仅求交一次;算法采用交点表与连续跟踪相结的方法跟踪交线,并在跟踪交线的同时用Euler算子建立起交线的数据结构且对特殊交点进行特球处理;算法最后用一种新的交点修正法对离散交线进行求精。     

Pixel-selected ray tracing

An acceleration method based on an idea that T. Whitted (Commun. ACM, vol.23, no.6 pp.343-349, June 1980) presented on ray tracing is discussed. He proposed making antialiased images by hierarchical adaptive oversampling. The present authors use hierarchical adaptive undersampling to reduce the number of pixels whose intensity must be calculated by ray tracing. To implement pixel-selected ray tracing (PSRT), homogeneous regions in images must first be found. Generally, adaptive undersampling can result in some image-quality defects, because small objects and parts of thin or wedge-shaped objects may disappear when they are located between the initially sampled pixels. PSRT has an improved algorithm that uses pixels with the correct object information from among the sampled pixels to find pixels with erroneous color and correct them. Moreover, PRST uses ray-object intersection trees for precise classification of the homogeneity of regions and for fast intensity calculation in homogeneous regions. Experimental results are presented. They show that PSRT is two to nine times faster than standard ray tracing     

结合轴对齐包围盒和空间划分的碰撞检测算法

目的 碰撞检测是虚拟现实,特别是虚拟装配中的关键技术。针对基于包围盒的碰撞检测算法的准确性和检测效率不足的问题,提出一种结合AABB轴对齐包围盒和空间划分的碰撞检测算法。方法 本文算法采用分步检测的方法,利用AABB算法来确定两包围盒的相交区域后,结合模型移动方向和运动趋势进行空间划分,利用碰撞检测的时空相关性,对时空相关的部分进行相交测试,通过将包围盒还原成三角面以及点的方式来保证检测的准确性。结果 本文算法与AABB层次包围盒二叉树算法、k-Dops包围盒算法以及BPS空间分割树算法进行对比实验分析。在碰撞的几何精度上,本文算法在大部分情况下与AABB算法和k-Dops算法的距离差超过阈值0.02,证明本文算法在碰撞几何精度上有明显的提高。在碰撞检测时耗上,随着碰撞检测难度的不断增加,本文算法在平移自由度下比AABB算法和BSP算法、在旋转自由度下比AABB算法和k-Dops算法的检测时间均降低了50%以上。在三角面数对算法碰撞检测时耗的影响上,当运动模型的三角面数较多时,本文算法表现出更高的稳定性。结论 结合AABB包围盒和空间划分方法的碰撞检测算法,在减少碰撞检测所需时间的同时提高了碰撞检测的准确性,可以满足虚拟装配技术中对碰撞检测算法准确性的要求,同时也能满足使用者实时性的交互习惯。     

基于空间网格细分的不规则场景的光线跟踪

针对不规则场景中光线跟踪算法绘制速度慢的问题,在深入学习和比较近些年的光线跟踪加速算法的基础上,提出了一种改进的网格细分的光线跟踪算法。首先,设置矩形场景包围盒,剔除对场景没有影响的外部光线,进而简化求交运算;其次,采用新方法创建空间网格,该方法可使空间单元数量和存储空间复杂度都限定在一定范围内;最后,对网格进行细分,这一步骤消除了传统空间网格算法忽略部分空白区域对加速效果产生的不良影响, 极大完善了传统空间网格算法。通过实验证明,该方法能有效提高光线在空白空间的穿行速度,不仅提高了时间效率,而且减少了空间开销。     

The same origin ray set query for realistic illumination: Algorithm and analysis

The same origin ray set (SORS) is a computational primitive which can be used by ray tracing, radiosity and multiple pass illumination simulation algorithms for realistic image synthesis. A SORS consists of a set of rays emanating from the same point in space. The SORS query computes the first object intersected by each ray and the intersection point. In this paper we present an efficient projection algorithm for computing a SORS query for polygonal scenes. The algorithm achieves its efficiency by separating ray-polygon intersection detection from the computation of the intersection point between the ray and the polygon's plane. The algorithm can be integrated with all current illumination acceleration schemes. We analyse the projection algorithm and compare it to the alternative of computing the SORS query one ray at a time. The analysis' results are expressed in terms of a few intuitive parameters, measuring the success of the acceleration scheme in culling irrelevant objects and the concentration of the ray set. The projection algorithm can be up to five times more efficient, depending on these parameters and the quality of the image. The relative advantage of the projection increases with image quality.     

Inverse Displacement Mapping in the General Case

Inverse Displacement Mapping is a form of displacement mapping which allows the ray tracing of displacement mapped surfaces. The technique performs all calculations in the inverse (parametric) space of the surface thus avoiding the need to explicitly model the complex three dimensional geometry. This produces a compact and general algorithm, Only when the solution, in parametric space, has been determined is it transformed back to 3D space. The algorithm works by projecting the ray into the parametric space of the surface. This ray is then split into a series of segments, each of which can be efficiently handled to calculate the intersection points. The algorithm presented here has been used to ray trace displacement mapped objects from a variety of underlying surface types.     

基于八叉树邻域分析光线跟踪的云三维模拟

针对目前三维云模拟绘制效率低、计算资源消耗大、绘制效果差等问题,提出基于八叉树邻域分析的光线跟踪算法,并用于WRF模式云数据的三维模拟。使用八叉树结构优化传统光线跟踪算法的数据存储结构,通过存储节点编码和划分层次改进邻域分析算法,通过简化光线的折射公式优化Whitted光照模型,借助OpenGL和Vapor工具实现云数据的三维可视化。实验结果表明,该方法降低了绘制时间,提高了渲染效率,更好体现了云的真实物理特征。     

基于空间扫描策略的3维相交检测算法

针对复杂虚拟场景中碰撞检测和空间分析等操作实时性差的问题,提出一种适用于3维空间对象间的快速相交检测算法——Space Sweep。该算法首先根据场景内空间对象分布特征,构建事件点及其列表;利用空间扫描策略,自适应地构建一系列假想的空间扫描面;在扫描面移动的过程中,将空间对象的状态分为死亡态、激活态和休眠态,通过只对当前处于激活态的空间对象进行相交测试,有效地减少了空间对象间不必要的相交计算。该算法提高了虚拟场景中3维空间对象间相交检测的效率,为3D GIS中实时空间分析提供了有力的技术支持。最后,通过对比测试验证了本文算法的实用性。     

基于二分内包围盒的玉米光照逆光线跟踪算法

为了在玉米仿真中构建逼真有效的光环境,提出一种基于二分内包围盒的玉米光照逆光线跟踪算法。首先,在玉米表面建立二分内包围盒进行预处理,减少光线与玉米相交运算量;其次,引入遮挡因子简化光能计算的复杂度;最后,通过调整光能阈值达到光环境逼真度和算法效率的统一。为了验证算法的快速有效性,建立玉米模型,对比不同包围盒求交运算的速率,得出二分内包围盒的求交速度最快,逆光线跟踪算法模拟出的玉米生长效果较为逼真。