可变形物体间的精确碰撞检测方法研究

针对可变形物体,提出了一种基于粒子的精确碰撞检测算法。首先用LBG矢量量化技术将物体的表面划分成几个小区域,然后在每个区域中分别选择一个点作为检测粒子。当一个物体接近另一个物体时,找出两物体上靠得最近的粒子对。为了得到精确的碰撞位置坐标,进一步计算靠得最近的顶点的相关三角面片之间的最短距离。若此距离小于某个给定的阈值,则可认为两物体在相关三角面片上的最近点处发生了碰撞。仿真实验验证了该算法能有效处理虚拟力交互仿真中的可变形物体的碰撞检测。     

破碎刚体三角网格曲面模型的特征轮廓线提取方法

区分了三角网格曲面模型上的三组概念：外表面与断裂面、内外边及内外轮廓线．运用内外边的性质快速提取了外轮廓线,采用法矢夹角计算和统计方法获取了模型上断裂面与原表面夹角的经验阈值及断裂面面积的上限,继而确定候选特征点集,最后利用扫描线算法获取包络于候选特征点集的内轮廓线．基于以上步骤提出三角网格曲面模型的特征轮廓线提取方法,该方法正确提取了破碎刚体模型的特征轮廓线,使空间曲线匹配得以进行．     

由任意形状轮廓线重建三维表面的方法研究

由一组二维轮廓线重建出物体的三维表面是医学数据可视化的一种主要绘制方式。当轮廓线比较复杂,例如当遇到非凸轮廓或相邻层轮廓线相差过大时,常用的三角化拼接方法就会失败。文章提出一种新的轮廓拼接方法能够处理任意形状的轮廓线。该方法的基本思想是对轮廓线进行凹凸性层次分析,然后将相邻轮廓线从外到内逐层拼接,从而构成一个三角化的物体表面。实验结果表明,该算法对于手动勾画和自动提取的轮廓线都可以给出较好的重建效果。     

一种面向三维人脸识别的同一截面有效轮廓线提取算法

针对三维人脸识别对表情及姿态变化的鲁棒性研究,提出一种基于人脸同一截面有效轮廓线的人脸识别方法。首先根据手工标定鼻尖点区域的法向量对人脸进行粗略矫正,再基于同一标准正中面人脸的迭代最近点(ICP)算法进行精确姿态矫正,标定精确鼻尖位置,提取过鼻尖的不同人脸同一截面横纵两条轮廓线。用阈值法提取过鼻尖点的有效轮廓线,采用ICP算法计算相似度,对两条轮廓线识别结果进行融合。实验结果表明,在CASIA 3D人脸库上对表情及姿态变化有较好的鲁棒性。     

基于地层轮廓的三维重构的设计和实现

在进行海底地质地层调查勘探时,通常根据测量仪器采集的数据生成地层断面轮廓线,按照这些连续的轮廓线的分布特征及其灰底不同来粗略地分辨地层的性质.然而这些单一的剖面轮廓还不足以直观地反映该地域整体地层的三维形状分布信息.根据地质地层分布的特性,通过对相邻断层轮廓线点集的匹配和三角剖分算法来进行地层分布的三维重构,并利用基于三角域的Bernstein-Bezier曲面构造三次光滑曲面,从而模拟三维的地层分布效果图.     

基于贪心算法与多边形剖分的印鉴匹配算法

将计算几何中平面点集的三角剖分方法之一贪心算法与多边形三角剖分方法引入印鉴匹配,研究了一种基于三角网格(用贪心算法进行平面点集的三角剖分)的印鉴匹配方法.用贪心算法对基于线条的细节点集进行三角剖分,而对于基于多边形的细节点直接进行多边形的三角剖分.通过对两种细节点(基于线条的细节点和基于多边形的细节点)的拓扑结构进行三角划分,把空间上位置相近的细节点按照一定的规则相连,得到三角形网格.然后基于该网格寻找若干参考点对,并根据获得的参考点对将两幅印鉴图像进行姿势调整.最后使用获得的参考点时实现基于点模式的印鉴匹配,经分析该方法是一种行之有效的印鉴识别方法.     

一个计算凸多面体间碰撞点的快速算法

计算两个物体之间的碰撞点是碰撞响应的基础,也是一项系统开销很大的任务.因此,研究碰撞点快速求解算法对碰撞响应的实时性具有重要意义.该文提出了一个算法,当在虚拟环境中检测到碰撞时,应用此算法可以在碰撞响应之前快速计算出两个物体之间的准确碰撞时间,并能计算出此时两个物体之间的碰撞点.     

基于模型散乱点的三维物体重建

基于三维模型的散乱数据点,通过引入分割平面,对数据集进行划分,将散乱数据划分为n个子集合来重建物体。具体的过程,是通过引入控制参数δ和η,将满足相应条件的3D散乱点划分到相应的子集合中,然后对各个散乱点子集合进行判断,提取其各个子集上的控制点,构造各个子集的控制点构成的边界。最后,对每两个相邻的边界进行相似性评估,对相似的边界之间通过等比例划分,非相似的边界采用全局优化,从而得到重建的三维物体的模型。经过实验证实该方法高效、方便、准确。     

基于二维凸多边形内散乱点的三角划分新算法

基于给定的平面散点数据,提出了逐层提取轮廓线,并将轮廓线之间的区域进行三角划分的新算法。实现这一算法的关键是在给定阈值的条件下逐层提取内部离散点的轮廓线,再在所提取的轮廓线间进行等比例三角划分。最后,利用Lawson提出的局部优化过程来优化分割好的三角形网。通过实验证明了算法的有效性。     

基于实测轮廓线的岔道口三维实体建模方法

在数字矿山系统中,为使错综复杂的地下巷道重建效果能达到矿山的验收标准,根据实测巷道交岔口轮廓线,采用分区(分块)建模思想,提出一种基于实测轮廓线的岔道口三维实体建模方法。将实测的岔道口轮廓数据按其特点分为顶底板和侧面轮廓线点集,采用凸包算法构造顶底板的简单多边形,并对其进行三角化。根据顶底板多边形顶点的先后顺序关系,建立侧面轮廓线的相邻关系,并采用连线框算法对相邻轮廓线进行三角化。实验结果表明,该方法简单有效,可解决任意断面形状、多个岔道口的建模问题,并且已经应用于DIMINE软件的测量插件中,效果良好。     

三维物体表面三角划分的遗传算法

提出了一种基于遗传算法的从给定平行截面线重建物体表面的方法。该算法利用了三维表面三角形划分和遗传算法的基本原理,使用多目标适应函数,能够进行多目标优化从而满足不同的要求,算法还采有了新交叉与变异算子－三维多边形交叉与三维四边形变异。     

平面简单闭合曲线离散采样与重建算法

提出一种鲁棒的平面简单闭合曲线离散采样与重建算法。算法分为采样过程和重 建过程两部分。采样部分首先对平面闭合曲线均匀取点,然后计算各点到曲线所围平面区域中 轴的最近距离,最后根据所求距离确定采样间隔,获取采样点集;重建部分首先构建采样点集 的Delaunay 三角剖分,然后从得到的三角形中选择边构建初始化图形,最后通过修改该图形获 得重建图形。实验表明算法得到的采样点较少且能反映曲线的局部几何特性,重建图形能够较 好地表示原闭合曲线的形状及走向。     

A Crust-based Method of Reconstructing Human Bone

We present a crust-based procedure for modeling human being’s bone, which is based on voronoi diagram and its dual, Delaunay triangulation. In three-dimensional space, the crust algorithm can generate a 3D-model using a set of sample points. The purposes of this paper is to extract precise contour from CT series, then refer to these contours as sample points, and then apply the crust algorithm to these sample points to get three dimensional mesh.     

三维物体表面重建的分支处理算法研究

根据平面点集Delaunay三角剖分的特性,将Delaunay三角剖分应用到分支问题上,改进和实现了一种分支问题处理算法。将相邻层轮廓线投影到同一个剖面上形成一个带约束边的平面点集,并将它们Delaunay三角化,根据这些三角形组来生成新的轮廓线,使轮廓线一一对应。实验结果表明该算法实现的效果较符合实际情况,能有效地处理各种不同情况。     

一种基于三维Delaunay三角化的曲面重建算法

提出一种基于三维Delaunay三角化的区域增长式曲面重建方法。该方法以空间点云的Delaunay三角化为基础,结合局部区域增长的曲面构造,较以往方法具有人为参与更少、适用范围更广的优点。算法采用增量式插入点的方式构建空间Delaunay划分,采用广度优先算法,以外接圆最小为准则从Delaunay三角化得到的四面体中抽取出合适的三角片构成曲面。该算法的设计无须计算原始点集的法矢,且孔洞系数对重建的结果影响很小,重建出的三角网格面更符合原始曲面的几何特征。无论待建曲面是否是封闭曲面,本算法均可获得较好的重建效果。     

Shape recovery from turntable sequence using rim reconstruction

This paper makes use of both feature points and silhouettes to deliver fast 3D shape recovery. The algorithm exploits object silhouettes in two views to establish a 3D rim curve, which is defined with respect to the two frontier points arising from two views. The images of this 3D rim curve in the two views are matched using cross-correlation technique. A 3D planar rim curve is then reconstructed using point-based reconstruction method. A set of 3D rim curves enclosing the object can be obtained from an image sequence captured under circular motion. Silhouettes are further utilized to check for mismatched rim points. The proposed method solves the problem of reconstruction of concave object surface, which is usually left unresolved in general silhouette-based reconstruction methods. In addition, the property of the reconstructed 3D rim curves allows fast surface extraction. Experimental results with real data are presented.     

Incremental Labelling of Voronoi Vertices for Shape Reconstruction

We present an incremental Voronoi vertex labelling algorithm for approximating contours, medial axes and dominant points (high curvature points) from 2D point sets. Though there exist many number of algorithms for reconstructing curves, medial axes or dominant points, a unified framework capable of approximating all the three in one place from points is missing in the literature. Our algorithm estimates the normals at each sample point through poles (farthest Voronoi vertices of a sample point) and uses the estimated normals and the corresponding tangents to determine the spatial locations (inner or outer) of the Voronoi vertices with respect to the original curve. The vertex classification helps to construct a piece‐wise linear approximation to the object boundary. We provide a theoretical analysis of the algorithm for points non‐uniformly (ε‐sampling) sampled from simple, closed, concave and smooth curves. The proposed framework has been thoroughly evaluated for its usefulness using various test data. Results indicate that even sparsely and non‐uniformly sampled curves with outliers or collection of curves are faithfully reconstructed by the proposed algorithm.     

Delaunay三角网高效构建及地形仿真应用

针对基于离散点的Delaunay三角网构建过程中待插入点的定位耗时问题,提出Delaunay三角网高效构建算法,并将其用于三维地形仿真应用中。对大量数据点进行分块排序预处理后,运用空间自相关理论使下一个待插入点总是紧邻新近插入点,融合最短路径定位算法和三角形面积法,结合三角形重心与点、有向线段的关系遍历三角形,减少遍历时间。在对三角网进行LOP局部优化时,采用Delaunay四叉树保存待调整的所有边的节点信息,提高遍历效率。实验结果证明,该算法构建的三维地表真实感较强,并且具有较低的时间复杂度。