运用改进的八叉树算法实现精确碰撞检测

提出一种精确碰撞检测算法,通过计算空间多面体之间距离实现碰撞检测功能.在计算2个多面体之间距离时,运用空间层次划分技术高效地寻找多面体中充分接近的三角面片,然后在这些三角面片中进行距离计算,以提高算法效率;同时运用改进的八叉树层次分割算法,与基本八叉树算法相比,减少了算法的空间复杂度.文中算法已经在超导Tokamak实验装置（EAST）虚拟装配仿真系统的碰撞检测模块中得到应用,通过实验比较,证明了该算法的可行性.     

计算线性八叉树边界象素集的新算法

八叉树作为一种新的形体表示方法,在几何造型、物性分析、动态模拟、干涉检测、计算机视觉、机器人等应用领域内有着广泛的应用前景。用其它方法表示的形体,可以转换为八叉树表示进行处理,从而弥补了这些形体表示方法的缺陷。但是,八叉树表示占有存储空间过多,为了解决这一问题,常采用线性八叉树的存储结构[1,2],本文在线性八叉树的基础上,提出了一个计算八叉树边界象素集的新算法。该算法采用一种“增减”原则,根据这一原则,对八叉树的边界象素集进行不断的增减操作,最终产生形体的全部边界象素。利用本算法产生的结果,可以大大提高干涉检测、形体间最小距离计算等算法的效率。同时,也可用于医学中CT扫描图像的三维形体重建,以及由八叉树表示转换为边界表示的算法。算法的复杂性为0(nN+M),其中,n为八叉树的精度,N为线性八叉树的长度,M为形体边界象素的数目。     

基于混合空间剖分八叉树场景管理技术的研究

基于传统八叉树和面向对象八叉树的设计思想提出了一种混合空间剖分八叉树的场景管理方法,对混合空间剖分八叉树的数据结构、生成算法及遍历方面进行了详细的论述,最后按照该思路结合所设计的一个虚拟场景有效地实现了场景管理,实验表明该方法很适于实时游戏及虚拟现实领域。     

基于八叉树编码的点云数据精简方法

针对逆向工程中的点云数据预处理,分析了现有数据精简方法的不足,提出了基于八叉树编码的均匀精简方法。应用八叉树编码法划分点云邻域空间为多个指定边长的子立方体,保留每个子立方体中距中心点最近的点,实现从空间整体角度对点云的精简。对涡轮叶片测量数据进行了精简测试,证明了该算法的有效性和实用性。     

采用空间分割的平滑曲面重构算法

面绘制是科学计算可视化中一个重要的研究方向，移动立方体是实现面绘制的一个重要算法，八叉树是一种有效的表示三维物体的方法，该文在八叉树生成的基础上，提出一种基于空间分割的表面重构算法，将绘制空间分别按X轴、Y轴和Z轴进行分割，生成的树的节点个数小于等于8个，与八叉树方法相比，减少了所生成叶结点数量，再通过移动立方体算法生成三角面片。三角面片通过平滑处理，提高了图形显示质量。     

基于Z曲线和八叉树的高效Hausdorff距离计算方法

为提高计算点云模型之间Hausdorff距离(HD距离)的效率,提出基于Z曲线和八叉树的Hausdorff距离计算方法.首先利用Z曲线和八叉树实现点云模型预处理;然后在八叉树结构中定义了2类邻居(邻居点和邻居节点),并提出基于八叉树的局部搜索,以某一个叶子节点作为搜索的起点,递归地搜索其邻居直到根节点;最后结合模型预处理和局部搜索,给出了算法的实现细节.针对三维高斯随机数据和点云模型进行大量实验,并与经典方法进行对比,结果验证了文中方法的高效性.     

基于多级线性结构和规则分块的虚拟八叉树

提出一种基于多级线性结构和规则分块、无指针/无位置码的虚拟八叉树模型,具有高效的结点访问效率和存储空间压缩效率,实现了指针八叉树在时间效率、线性八叉树在空间效率两方面优势的统一。新模型能够对三维实体及其内部的非均质属性进行建模,可以保证各种可视化与分析算法的处理效率,在空间信息系统和体图形学等实体建模相关的领域中具有重要的研究意义和应用价值。     

一种基于GPU实现的自适应八叉树纹理绘画算法

当前,虽然基于二维图像映射定义的传统二维纹理已得到广泛应用。但是它有很多局限性。这是因为很多三维模型在纹理空间中进行参数化是非常困难的,例如隐式表面、细分表面和高密度或高细节的多边形网格。基于八叉树纹理定义,提出了一种新型的自适应八叉树纹理绘画算法。和传统的八叉树纹理映射算法相比,不但占用更少的存储空间,而且实现了基于GPU的纹理查询,有更快的查找速度。     

基于体模型优化的虚拟试衣算法

针对目前虚拟试衣人体模型存在的精度和时效上的问题,提出了一种基于体素八叉树的优化的体模型的高效、真实感强的虚拟试衣算法。将空间划分为若干体素,与人体表面相交的体素构成人体表面模型,且体素采用八叉树结构存储。通过Kinect采集的人物的深度图像来计算八叉树中体素的符号距离函数(SDF);使用Marching cube融合图像彩色纹理并渲染出逼真的三维人体模型;提出了碰撞检测响应算法。实验结果表明,提出的方法增强了人物模型的真实感,八叉树结构有效缩短了碰撞检测时间,具有较强的实用价值。     

线性八叉树及其上的集合运算

八叉树编码方法是目前计算机图形学、图象处理和CAD/CAM技术中的一种新的方法。由于采用这种方法表示物体后,对物体进行相干性判别和消除隐藏线(面)操作变得容易而越来越引起人们的兴趣。但由于八叉树编码方法占用的内存太多,而且采用的数据结构是一个非线性结构(树状结构),因此不令人满意。而线性八叉树编码方法很好地解决了上面这两个问题。线性八叉树编码方法由Gar-gantini引入,但她没有给出线性八叉树的深入的性质,也没有详细给出算法。 本文引入了一些与线性八叉树有关的概念,给出并证明了线性八叉树的一些性质。最后,作为这些结果的应用,我们提出了由线性八叉树编码方法所表示的物体之间的集合运算的算法。并对这些算法进行了分析。这些算法都具有线性的时间复杂性。     

无线传感器网络交点质心定位算法的优化

节点自身定位是无线传感器网络的重要应用之一。为提高定位精度,以求解精度优于传统最小二乘法的交点质心算法为基础,定义距未知节点最近的锚节点为参考节点,通过测量参考节点与锚节点之间的距离获得RSSI的测距误差,并对未知节点与锚节点间的测量距离进行误差修正,抑制了RSSI测距误差对定位精度的影响;再引入四边测距定位和优选锚节点的思想,对算法进行改进。MATLAB仿真结果表明：本算法在相同实验环境下相较于交点质心法又进一步提高了定位精度。     

矢量道路拓扑追踪匹配算法

目的 基于道路形状特征的匹配算法在匹配性能上比较稳定,但当遇到道路交叉口等复杂路况时容易出现误匹配,且实时性上有一定缺陷,而矢量道路良好的拓扑结构,为此提出一种利用矢量道路拓扑关系进行追踪匹配的算法。方法 算法利用结点、路段和路口这3种对象来对矢量道路进行表达,建立各个对象之间的拓扑关系,并将匹配过程划分为4个不同的状态,根据各个状态实施相应的匹配方法。首先,进行初始化、追踪、路口和搜索4个状态的定义和划分,确定各个状态之间的转换关系;进一步,设计道路中的结点、路段和路口3种对象的数据结构,建立点、线之间的空间拓扑关系;其次,根据4个状态的具体任务和实际特点,对进入该状态的行驶轨迹进行相应地分析处理和匹配计算;最后,根据追踪的结果进行匹配分析,完成对车辆行驶轨迹的误差修正。结果 采用GPS-RTK采集的北京市西五环及密云地区的矢量道路数据对实地跑车的惯性导航轨迹进行拓扑追踪匹配仿真实验,完成拓扑追踪匹配算法的路口距离阈值选取,并与传统基于道路形状特征的匹配算法在匹配效果和实时性进行性能对比测试,其性能指标为匹配准确率和匹配时间。当矢量道路拓扑追踪算法的路口距离阈值取20 m时,匹配准确率达到了最高值93.5%。在匹配性能对比上,拓扑追踪算法相较于其他两种算法也有一定优势,在相同道路段中匹配准确率达到了90.2%,匹配速度也提高了48倍。结论 采用矢量道路数据的拓扑信息对车辆轨迹进行追踪匹配的方法,能够用于卫星信号“盲区”或者信号干扰等特殊环境和场合的组合系统辅助导航,弥补传统基于卫星的组合导航在自主性、抗干扰性的不足。同时,算法针对复杂路况的匹配结果也较为理想,能够满足组合导航匹配工作的要求。     

图像检索中颜色的特征提取及匹配算法

介绍了基于内容图像检索中多种颜色的特征提取和匹配算法,以及加权欧几里得距离、中心距的加权距离、直方图交集算法等。结合西北大学可视化研究所开发的数字博物馆影像数据库系统,对这些算法进行了实验比较。结果表明,加权距比欧氏距有所改善;而中心距算法简单,检索速度快;直方图交集法相对于加权欧氏距并没有明显改善。在实际应用中可先使用一种速度快的算法,再在查询结果上进行二次查询。     

距离交会算法在无线传感网络节点定位中的应用

Knowing the locations of nodes in wireless sensor networks (WSN) is essential for many applications. Nodes in a WSN can have multiple capabilities and exploiting one or more of the capabilities can help to solve the localization problem. In this paper, we assume that each node in a WSN has the capability of distance measurement and present a location computation technique called linear intersection for node localization. We also propose an applied localization model using linear intersection and do some concerned experiments to estimate the location computation algorithm.     

A linear time algorithm for computing exact Euclidean distance transforms of binary images in arbitrary dimensions

A sequential algorithm is presented for computing the exact Euclidean distance transform (DT) of a k-dimensional binary image in time linear in the total number of voxels N. The algorithm, which is based on dimensionality reduction and partial Voronoi diagram construction, can be used for computing the DT for a wide class of distance functions, including the L/sub p/ and chamfer metrics. At each dimension level, the DT is computed by constructing the intersection of the Voronoi diagram whose sites are the feature voxels with each row of the image. This construction is performed efficiently by using the DT in the next lower dimension. The correctness and linear time complexity are demonstrated analytically and verified experimentally. The algorithm may be of practical value since it is relatively simple and easy to implement and it is relatively fast (not only does it run in O(N) time but the time constant is small). A simple modification of the algorithm computes the weighted Euclidean DT, which is useful for images with anisotropic voxel dimensions. A parallel version of the algorithm runs in O(N/p) time with p processors.     

一种参数曲线间Hausdorff 距离的计算方法

针对一般的连续参数曲线,提出一种快速计算曲线间Hausdorff 距离的方法。由 于曲线的近似折线能很好的表示曲线,所以,许多软件中,采用曲线的近似折线绘制曲线。为 此,证明了在任意给定误差范围下,可以将曲线间的Hausdorff 距离转化为折线间的Hausdorff 距离,进一步转化为点到线段间的距离进行计算,并辅之必要的剪枝策略和增量式算法以提高 计算效率。该方法计算速度快,逼近度高,基本解决了参数曲线间Hausdorff 距离的计算问题, 在几何设计、图像匹配、图像识别等领域有广泛应用。     

格网划分的双策略跟踪多边形裁剪算法

论文提出了一种高效稳定的多边形裁剪算法,算法支持带内环的平面简单 多边形,同时也支持多边形的“并”和“差”等布尔运算。首先,设计了算法所需的数据结构; 其次,基于直线扫描转换Bresenham 算法原理提出了边网格划分的有效算法,并应用一个简 单的方法避免不同网格内边的重复求交;最后,将交点分类为普通交点和顶交点,并针对这 两类交点构造了不同的跟踪策略,在跟踪过程中交替、递归地应用这两个策略来确保算法处 理特殊情况时的稳定性。与其它同类算法的比较表明,新算法具有更高的效率。     

Finding Starting Points for Tracing Surface Intersections

To find starting points for all the intersection curves, one of the surfaces is subdivided into some small surface patches. Based on a correlative algorithm of computing the minimum distance of two surfaces, the intersections of every patch with another surface are detected, and starting points are calculated by dichotomy. This algorithm shows superior efficiency in the computational complexity and number of iterations needed. It can be used to determine exact starting points on all possible solution curves between any kinds of parametric sculptured surfaces.     

Finding Starting Points for Tracing Surface Intersections

1 Introduction Finding out proper starting points for all the intersection curves between two surfaces is a key process in numerical tracing methods for surface-surface intersection (SSI) problems. A number of methods [1] are introduced to calculate the starting points. Cugini et al. [2] introduced the concept of shrinking bounding boxes to calculate starting points. This method is simple and in some cases effective, but it may miss some intersection components. Muellenheim [3] presented an…     

Detection of loops and singularities of surface intersections

Two surface patches intersecting each other generally at a set of points (singularities), form open curves or closed loops. While open curves are easily located by following the boundary curves of the two patches, closed loops and singularities pose a robustness challenge since such points or loops can easily be missed by any subdivision or marching-based intersection algorithms, especially when the intersecting patches are flat and ill-positioned. This paper presents a topological method to detect the existence of closed loops or singularities when two flat surface patches intersect each other. The algorithm is based on an oriented distance function defined between two intersecting surfaces. The distance function is evaluated in a vector field to identify the existence of singular points of the distance function since these singular points indicate possible existence of closed intersection loops. The algorithm detects the existence rather than the absence of closed loops and singularities. This algorithm requires general C² parametric surfaces.