基于图片序列的三维表面重建

根据非透明物体内部不可见的实际,提出了一种基于图片序列的三维表面重建算法.该算法首先利用传统的八叉树算法重建出物体的三维模型,然后利用一种新颖的表面点提取算法提取出物体表面点,最后利用这些表面点进行三角网格剖分,进而重建出光滑的三维物体表面.在表面点的提取过程中,算法对处于不同状态(处于立方体的顶点、棱、面)的点赋予不...     

基于顶点重要度的保形网格简化方法研究

为解决许多网格简化方法不能很好地保持模型的重要几何特征问题,提出基于顶点重要度和三角剖分的边折叠简化算法.算法通过特征因子加权顶点重要度作为边的折叠代价,定义法向量夹角因子,控制边的折叠顺序;在折叠过程中对边界特征区域进行冻结处理,以保持模型总体轮廓特征;采用边中点折叠和边邻域网格重建方法完成折叠操作.实验结果表明,模型在大规模简化后,该方法能较好地保持模型的几何特征.     

四面体胞的尽可能刚性网格变形算法

提出一种基于四面体胞的尽可能刚性三角形网格变形算法。用户通过操作网格上的若干顶点以得到所需的模型变形结果。首先,算法对网格模型内部进行稀疏四面体化,以产生一个贴合模型表面的四面体胞集。在模型变形过程中,算法通过最小化相应的变形能量函数,以保持网格模型表面局部区域的刚性以及每个四面体胞的刚性,从而有效避免模型表面及其内部的扭曲。同时,针对大尺度编辑可能造成的模型局部塌陷,提出一种简单的四面体胞自适应剖分方法,根据模型局部体积的剧烈变化,自动剖分对应的四面体胞以增加模型内部的局部变形自由度,进而消除不正确的变形效果。此外,自适应的四面体胞剖分允许算法在初始时只需对网格模型进行稀疏的四面体化,而在变形过程中根据需要进一步提高四面体胞的局部稠密度,因而保证了算法的鲁棒性及其效率。实验结果表明,该变形算法可以有效保持模型的表面细节以及模型的内部体积,并能够有效避免模型形状在大尺度变形时的局部退化。     

三角网格模型的基本群分割

提出一种有效的三角网格模型分割方法。用Dijkstra算法求出三角网格模型上任意给定一个基点到其余顶点的最短路径树;求出该模型对偶图的最大生成树,且对偶图的边与该最短路径树的边不相交;找出该模型上所有既不属于最短路径树也不和最大生成树相交的边,这些边分别与最短路径树组成的最短环集合就是给定基点处的基本群,沿着这些最短环就可以把网格分割成一个拓扑同胚于圆盘的区域。实验结果表明,该分割方法可以快速、有效地实现网格的分割。     

一种基于带噪声的三角网格模型的光顺算法

为了去除三角网格模型中的噪声,提出了一种基于均值漂移的特征保持的网格光顺算法。该方法在对模型中的三角形的法向量进行滤波的基础上鲁棒地计算了顶点的法向量,利用均值漂移方法自适应地聚类出顶点的邻域。结合顶点间几何特征的相似性,将改进后的双边滤波算子应用于顶点的位置更新,从而完成模型的光顺。实验结果证明了网格光顺算法的有效性。利用这种网格算法,可以达到光顺带噪声的三角网格模型的目的,并在光顺的同时,有效地保持了模型中原有的特征。     

一种新的基于顶点聚类的网格简化算法

在计算机图形学中,经常采用多边形网格来描述物体模型.由于绘制时间和存储量 与多边形的数量成正比,过于庞大的物体网格模型通常是不实用的.模型简化在计算机动画、 虚拟现实和交互式可视化等计算机图形应用领域有着广阔的应用前景.为此提出一种新的基 于顶点聚类的网格简化算法.该算法利用八叉树对网格进行自适应划分,给出了一种基于点 到平面距离的有效的误差控制方法,并能在用户指定的误差范围内通过使原始网格中的顶点 聚类达到大量简化的目的.该算法实现简单,速度快且能很好地保持边界特征.给出的一组图 例说明了该算法的有效性.     

基于二次误差度量的大型网格模型简化算法

针对传统网格模型简化算法无法处理尺寸大于内存容量的网格模型的问题,提出一种改进的基于二次误差度量的大型网格简化算法.在经典二次误差度量(quadric error metric,QEM)算法的基础上,改进算法引入顶点法向量夹角与边长作为权值,以及基于八叉树的模型划分策略.实验结果表明,该算法能够完成大型网格模型的简化,并且在简化过程中很好地保持了原模型的细节特征.     

优化变形能的平面多边形同构剖分

平面多边形间的同构三角剖分是平面形状渐进过渡与插值的基础,降低对应三角形的变形程度是获得高质量应用的关键.文中提出一种基于变形能优化的2个平面多边形的同构剖分算法,其中包含同构剖分生成和变形能最小化2个模块.首先根据用户指定的对应特征点对多边形进行顶点重采样,得到顶点一一对应的2个多边形;然后利用带约束的Delaunay剖分对其中的一个多边形进行三角化,得到源网格;再用重心坐标将源网格的内部顶点嵌入到另一个多边形得到同构剖分(目标网格);最后逐一检查三角形的变形能,对源网格中变形能超过阈值的三角形进行细分,用同构剖分模块生成新的目标网格.实验及数据统计分析表明,该算法可以得到较好的同构三角剖分,提升网格质量,并能很好地避免纹理细节失真.     

基于空间矢量变换的模型约束变形

基于空间矢量线性变换知识,提出了一种新的多边形网格模型变形方法。在三维模型空间选择一点作为约束源,并设置此约束源的影响半径。通过计算约束源与三维模型网格面片顶点之间的距离来确定待变形局部顶点区域。把空间矢量的线性变换应用到网格面片顶点变形所需的向量函数,依此函数直接精确地计算出网格面片顶点的新位置,从而实现模型的变形。通过对算法原理的进一步分析扩展了该变形方法的应用范围。     

支持STL数据源的网格曲面动态空间索引

针对STL文件格式存在网格顶点数据冗余以及缺乏面片邻接信息等缺陷,提出一种基于多维动态空间索引的显式曲面拓扑重建算法,在消除网格顶点数据复本的过程中逐步构建网格曲面顶点的KD树,通过该索引提高顶点数据复本消除效率,并基于KD树叶节点层数据存储的开放性融入半边数据结构,实现曲面拓扑结构的快速重建。最后,对6个不同规模的数据模型进行实验:与采用R^*-Tree、数组、散列表作为索引等方法相比,所提出的KD树与半边结构融合的动态空间索引在处理近百万面片的数据文件时,去除冗余顶点用时11.93 s,拓扑重建仅仅需要2.87 s,大大减少了冗余顶点的去除时间和拓扑重建时间,并且有效支持网格曲面拓扑邻域信息的快速查询,查询时间在1 ms之内,远小于对比算法所用时间。实验结果表明:所提算法能够提高网格曲面冗余顶点去除效率和拓扑重建效率,实现网格曲面拓扑邻域信息的快速查询。     

基于硬件细分的层次细节地形渲染算法

针对顶点着色器细分地形网格需要额外生成模板、计算细分层次复杂的不足,提出了一种利用细分着色器进行地形网格细分的层次细节(LOD)地形渲染算法。利用分块四叉树组织建立地形粗糙网格的分层结构,以LOD判别函数对活动地形块进行筛选;提出了在细分控制着色器中基于视点三维连续距离的细分因子计算方法,并针对外部细分因子进行处理消除了裂缝;实现在细分计算着色器上的置换贴图,对精细网格的高度分量进行位移。而且将四叉树结构存储至顶点缓冲区,减少中央处理器(CPU)与图形处理器(GPU)的资源交换;引入细分队列加速细分过程。实验证明,该算法具有平滑的细节层次过渡和良好的细分效果,能够有效提高GPU利用率和地形渲染效率。     

非平均化自适应Catmull-Clark细分算法

提出一种基于网格边的光滑度计算来进行Catmull-Clark自适应细分的新算法。该方法能够在满足显示需求的前提下较好地减小细分曲面过程中的网格生成数,同时解决了由于采用网格顶点曲率计算,来实现自适应细分方法中平均化生成顶点曲率带来的不足。通过对比试验,算法能更好地区别当前细分网格中光滑与非光滑区域,增加对非光滑区域网格加密密度,并且该算法能够普遍适用于较复杂的细分模式中,具有一定的推广价值。     

一种有效的细分曲面非盲水印算法

提出的细分曲面水印算法是基于图像水印算法和Fourier加法性质。首先将水印信息嵌入一幅图像,通过嵌入水印的图像和原始图像在空域作比较得到含有水印信息的矩阵,然后将细分曲面初始网格迭代三次以使网格的顶点数足够多,最后取出一部分顶点坐标和含有水印信息的矩阵相加得到嵌入水印的网格,嵌入水印后的网格作为新的初始网格。实验结果证明该算法具有较好的强壮性和计算量小的特点。     

基于CREW遍历图的一种并行算法

针对串行算法模型下基于顶点遍历图的情况,提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树,由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路,运用欧拉回路技术计算前缀和,前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O（n＋logn）的结论。     

基于二面角逆插值Loop细分的渐进传输方法

随着虚拟现实、增强现实等领域快速发展,渐进传输获得了良好的用户体验。为 了三角网格在移动终端的快速传输和显示,提出了一种基于二面角逆插值 Loop 细分(DRILS)的 渐进传输算法。主要通过对原始三角网格进行基于二面角插值 Loop 细分(DILS)和插值 Loop 细 分(ILS)进行预处理,在局部特征精确保持的同时获得具备细分连通性的精网格。在渐进传输的 过程中通过对该精网格迭代操作 3 个步骤,即奇偶顶点划分、预测偏移量、更新三角网格。由 于采用 DILS 与 ILS 结合获取精网格,在渐进传输的过程中保持了精确的局部特征,同时也加 快了渐进传输的速度。实验对比表明,该算法精确、高效,适应于移动终端设备的显示传输及 存储。     

基于STL文件的曲面网格重建算法

利用STL文件的数据相关性以及平衡二叉(AVL)树的数据搜索效率仅与树的高度相关的特性,提出一种高效的三角形曲面网格模型重建算法。该算法可以解决STL文件存在大量的冗余、使用效率不高等问题。实验结果证明,与基于AVL树的顶点快速聚合算法相比,该算法的重建效率更高。     

图形分析中平面图面基域划分的一种综合思想

面基域的确定是从工程设计二维平面图进行三维模型重构工作中的一个重要步骤。首先介绍两个面基域划分算法思想：一种是基于平面拓扑结构的广度遍历支撑树,然后对支撑树进行遍历确定各个面基域;另一种是对一个节点的可见边进行旋转角度的有序排列,确定从一条边出发如何选择后继边以围成面基域,从而对图进行划分确定面基域。在比较这两种算法的优缺点的基础上,结合它们的优点得出一种新的综合算法思想。     

基于GeoSOT剖分编码的多尺度空间信息区域包含关系计算方法

针对现阶段不同层次空间信息缺乏联系的问题,提出了一种基于剖分编码的多尺度空间信息间区域包含关系计算方法。首先,以GeoSOT剖分框架为组织基础,在不同尺度层上,以剖分面片作为基本单元组合表示地理对象,依据对象表达多尺度剖分编码模型将地理对象赋予剖分编码。然后,提出了基于剖分编码的区域包含关系计算方法,并给出了算法实现的具体流程。进一步采用剖分信息树状结构对空间信息进行统一管理,为剖分体系下组织与管理不同层次的空间信息提供了一种有效的解决思路。     

Surface interpolation of meshes by geometric subdivision

Subdivision surfaces are generated by repeated approximation or interpolation from initial control meshes. In this paper, two new non-linear subdivision schemes, face based subdivision scheme and normal based subdivision scheme, are introduced for surface interpolation of triangular meshes. With a given coarse mesh more and more details will be added to the surface when the triangles have been split and refined. Because every intermediate mesh is a piecewise linear approximation to the final surface, the first type of subdivision scheme computes each new vertex as the solution to a least square fitting problem of selected old vertices and their neighboring triangles. Consequently, sharp features as well as smooth regions are generated automatically. For the second type of subdivision, the displacement for every new vertex is computed as a combination of normals at old vertices. By computing the vertex normals adaptively, the limit surface is G¹ smooth. The fairness of the interpolating surface can be improved further by using the neighboring faces. Because the new vertices by either of these two schemes depend on the local geometry, but not the vertex valences, the interpolating surface inherits the shape of the initial control mesh more fairly and naturally. Several examples are also presented to show the efficiency of the new algorithms.     

Constructing a minimum height elimination tree of a tree in linear time

Given a graph, finding an optimal vertex ranking and constructing a minimum height elimination tree are two related problems. However, an optimal vertex ranking does not by itself provide enough information to construct an elimination tree of minimum height. On the other hand, an optimal vertex ranking can readily be found directly from an elimination tree of minimum height. On n-vertex trees, the optimal vertex ranking problem already has a linear-time algorithm in the literature. However, there is no linear-time algorithm for the problem of finding a minimum height elimination tree. A naive algorithm for this problem requires O(nlogn) time. In this paper, we propose a linear-time algorithm for constructing a minimum height elimination tree of a tree.