3D多层次模型简化算法的研究

细节层次模型(LOD)是指对同一个场景或场景中的物体,使用具有不同细节的方法得到一组模型,供绘制时使用.建立LOD模型能很有效地降低数据量和复杂度,实现三维场景的实时处理.以研究多层次细节模型快速生成算法为目的,在分析当前多层次细节模型生成算法的基础上,构建了三角形面片的权值计算公式,设计和实现了基于面片删除操作的LOD算法,详细描述了算法的设计,给出了算法实现所需的关键公式,最后给出了算法的应用实例和对算法时间效率的分析.此算法的最大特点是在不同的层次细节模型之间快速地平滑过渡.从试验结果和分析可见,该算法可以满足大的3D模型快速生成和交互的需要,同时也证明了算法的正确性和实用性.     

3D多层次模型简化算法的研究

细节层次模型（LOD）是指对同一个场景或场景中的物体,使用具有不同细节的方法得到一组模型,供绘制时使用。建立LOD模型能很有效地降低数据量和复杂度,实现三维场景的实时处理。以研究多层次细节模型快速生成算法为目的,在分析当前多层次细节模型生成算法的基础上,构建了三角形面片的权值计算公式,设计和实现了基于面片删除操作的LOD算法,详细描述了算法的设计,给出了算法实现所需的关键公式,最后给出了算法的应用实例和对算法时间效率的分析。此算法的最大特点是在不同的层次细节模型之间快速地平滑过渡。从试验结果和分析可见,该算法可以满足大的3D模型快速生成和交互的需要,同时也证明了算法的正确性和实用性。     

细节高度复杂表面模型的视点相关渐进传输

针对细节高度复杂模型的特点,提出一种视点相关的渐进传输方法.根据人的视觉特征,算法将模型表示为多分辨率的四边形参数面片和表面法向细节纹理.该算法利用法向映射提高传输和绘制的效率,然后随着视点的变化动态细化和传输当前视点下轮廓部分的参数面片信息,从而最大限度地减少了模型传输时面片的数量.参数面片的结构规则,面片之间关联性低,因此能够按任意顺序高效地传输,从而实现真正的视点相关传输,并可以采用有效的编码方法对其结构和几何信息进行压缩.实验结果表明了该算法的有效性,特别适合于表面细节复杂的表面模型的交互传输和绘制.     

面向动态流程工厂模型的快速分层层次细节法

分析了现有基于面片的分层层次细节算法在处理大规模动态流程工厂模型时存在的预处理时间过长、更新操作耗时等不足.提出一种新的基于基本体元的快速分层层次细节方法.该方法在体元级别对设备和元件进行聚合,对管线进行分割,建立场景图,然后基于几何参数和形状特征计算各体元的层次细节.利用管子及其元件的拓扑连接关系构成"组合管子",在体元级别对其进行合并简化.实验结果表明,对具有10M左右面片复杂度的动态流程工厂模型,该方法在普通PC机上能够在保证一定绘制质量的前提下将模型绘制速率平均提高3倍左右,并且将预处理时间控制在7min以内.     

自适应的线条画绘制

目的 基于参考图像的线条画生成是非真实感绘制最为常见的应用之一。尽可能模拟艺术家的创作风格生成疏密得当、具有层次感的线条画是这类工作的主要目标和挑战。本文提出一个自适应线画图绘制算法。方法 首先,将场景图像分割成若干个区域,分别计算每个区域亮度的方差以及每个像素到边界的最小距离,将每个区域的方差和面积的比值作为该区域的复杂度。然后,计算能反映其显著视觉特征的边缘切向流场。最后,使用基于流的各向异性高斯差分滤波生成线条画。在构造边缘切向流时,每个位置的切向量由其邻域的切向量加权而得到。文中增加了一个新的系数项,对于邻域的任意一个位置,如果它和参考位置在区域分类中属同一个类别。则该位置的权值更大。基于流的高斯差分自适应滤波过程中,高斯差分滤波的尺度参数和复杂度以及到区域边界距离有关。细节越丰富,离边界越近,尺度参数取值越小,这样得到的边缘比较细,同时可以防止将相邻小细线条连接成粗线条。然后,将高斯差分滤波结果沿着流线方向进行高斯滤波,对于细节丰富的区域,边缘比较多,尺度参数取值比较小,所连接边缘比较短,可以减少错误边缘可能。结果 对生物、树林、建筑、山河等具有代表性的图像,采用本文算法进行自动实时进行线条绘制,实验结果表明,采用本文算法所生成的线条随着区域场景的复杂程度呈现不同粗细和浓淡的变化,具有一定的层次感。因而本文算法能生成视觉特征鲜明、风格化效果突出的线条画,且能处理各种复杂场景的图像。结论 本文自适应参数的线条画生成算法,其算法参数调节以及算法效果优于固定参数的算法,本文算法在处理日常生活中各类主题场景的图像时均能取得良好效果。     

保细节的网格刚性变形算法

提出了一种新的保细节的变形算法,可以使网格模型进行尽量刚性的变形,以减少变形中几何细节的扭曲.首先根据网格曲面局部细节的丰富程度,对原始网格进行聚类生成其简化网格;然后对简化网格进行变形,根据其相邻面片变形的相似性,对简化网格作进一步的合并,生成新的变形结果,将该变形传递给原始网格作为初始变形结果.由于对属于同一个类的网格顶点进行相同的刚性变形,可在变形中较好地保持该区域的表面细节,但分属不同类的顶点之间会出现变形的不连续.为此,通过迭代优化一个二次能量函数,对每个网格顶点的变形进行调整来得到最终变形结果.实验结果显示,该算法简单高效,结果令人满意.     

可大规模应用的辐射度计算的自动网格化方法

合理地网格化场景是有效地进行辐射度计算的重要前提.现有的两种主要剖分方法是细分法和阴影边界计算法.前者是在必要时对大面片进行自动细分,后者是先解析地求出阴影的区域,然后根据阴影边界进行划分.前者存在的问题是无法检测出落在大面片中间的细节变化,绘制的质量得不到保证.后一种方法又局限于基本上只能处理纯多边形场景,而且计算时间长,实现复杂,难以在工程上进行应用.文章提出一种网格化方法,它面向大规模工程应用,简便易行,并能生成较高质量的图像.这种方法先将能量接受面划分成满足精度要求的细小面元,然后根据各面元对场景中各光源的可见性特征进行合并操作,以使能量变化情况不同的区域能以不同大小的尺寸进行剖分,这样,用于计算的面片大大减少,而图像质量没有明显的降低.实验结果和统计数据表明,此方法因其简单、高效,很适合大规模的工程应用.     

多边形网格的非流形封闭三角形网格正则化

为了提高基于网格模型的算法与应用的效率和稳定性,提出一种将任意多边形网格模型转化为正则三角网格模型的算法.首先对输入多边形网格模型中非三角形的面片进行三角剖分,然后查找并移除模型中的重合或重叠元素,再通过模型内部三角形求交对模型进行边和面的分割,从而修正模型的拓扑结构;在求交的过程中,根据边和三角形的位置关系对共面求交进行细致的分类处理,减少了求交次数,提高了算法的稳定性;最后循环搜索在网格模型中可以确定法向的种子三角形,通过拓扑结构调整与之相邻的三角形的法向,最终构成一个或多个法向确定的闭合曲面.实验结果表明,该算法能够将多边形网格转化为正则三角形网格模型.     

面向CAE 的网格模型特征简化与重建

针对CAE工程分析中网格模型的特点,提出了一种符合CAE特点的网格模型特征重建方法。鉴于CAD模型中的设计细节在CAE分析中可以忽略的特点,对CAD模型中的小圆角、倒角、小凸台等非结构性设计特征,采用基于面片法矢迭代滤波方法进行识别和滤除。算法首先识别出这些特征区域,然后根据非特征区域面片法矢调整特征区域法矢并更新顶点坐标,进行特征重建,最终得到符合CAE要求的网格模型。     

约束网格简化

针对三维激光扫描仪获得的彩色人头数据压缩问题,应用多细节层次模型自动生成技术,提出了基于区域分割的约束网格简化算法.在对三维彩色人头数据进行区域分割的基础上,把网格点分为两类,一类为区域边界点,在顶点合并操作中,区域边界点只能与边界点合并;一类为区域内部点,它能与边界点和内部点合并.然后根据区域加权的误差评价函数,生成多细节层次模型.该算法不但保证了压缩比,而且保持人头模型各区域(眼睛、鼻子、嘴、耳朵和头发)的边界和细节.文中最后给出了人头数据的一组简化实例.     

An algorithm for LOD by merging near coplanar faces based on gauss sphere

LOD（Level of Detail)models are widely used recently to accelerate the rendering of 3D scenes.An algorithm that creates multiple levels of detail for 3D scene y merging near-coplanar faces is presented in this paper,First a Gauss sphere is defined for the model of scene and it is divided into meshes near-uniformly.Then,the faces of objects are attached to the respective spherical meshes according to their normal direction.If faces attached to the same mesh are connected with each other,they are merged to form a near coplanar patch (Superface),Isolated vertices inside the patch are removed and the patch is retriangulated.To further imporve the simplification,vicinity vertices on the boundary of the surface patch are merged.In the algorithm,a planar separate rule planar-enneatree is adopted to set up a hierarchical structure of the Gauss sphere,which is used to support the hierarchical model of the scene(LOD),the experimental result shows that the algorithm can achieve desired simplification effects.     

基于表面提取的三维重建方法

本文提出了一种人机交互重建平面立体的新方法。该方法通过从视图上直接提取三维面,并由三维面导出三维点和三维边的方法建立平面立体的边界表示模型。这种方法具有重建速度快,为三维造型提供了一个便捷的手段。     

Connectivity-Based Segmentation for GPU-Accelerated Mesh Decompression

We present a novel algorithm to partition large 3D meshes for GPU-accelerated decompression.Our formulation focuses on minimizing the replicated vertices between patches,and balancing the numbers of faces of patches for efficient parallel computing.First we generate a topology model of the original mesh and remove vertex positions.Then we assign the centers of patches using geodesic farthest point sampling and cluster the faces according to the geodesic distance to the centers.After the segmentation we swap boundary faces to fix jagged boundaries and store the boundary vertices for whole-mesh preservation.The decompression of each patch runs on a thread of GPU,and we evaluate its performance on various large benchmarks.In practice,the GPU-based decompression algorithm runs more than 48x faster on NVIDIA GeForce GTX 580 GPU compared with that on the CPU using single core.     

一种保持纹理的网面简化算法

在计算机视觉领域,三维网面的简化不仅要求保持物体形状和拓扑关系,还要求保持物体表面法线,纹理,颜色和边缘等物体特征,以使计算机视觉系统能有效地表示,描述,识别和理解物体和场景,为此讨论了一种基于边操作（边收缩,边分裂）,并具有颜色或灰度纹理特征保持的三维网面的简化算法,该算法将网面不对称最大距离作为形状改变测度,将邻域内颜色或灰度最大改变量作为纹理改变测试,从而在大量简化模型数据的同时,有效地保持了模型的几何形状,拓扑关系,颜色或灰度特征,以及网面顶点均匀分布。     

基于逆 Loop 细分的半正则网格简化算法

摘 要：三维网格简化是在保留目标物体几何形状信息的前提下尽量减小精细化三维模型 中的点数和面数的一种操作,对提高三维网格数据的存取和网络传输速度、编辑和渲染效率具 有十分重要的作用。针对大多网格简化算法在简化过程中未考虑网格拓扑结构与视觉质量的问 题,提出了一种基于逆 Loop 细分的半正则网格简化算法。首先根据邻域质心偏移量进行特征 点检测,随后随机选取种子三角形,以边扩展方式获取正则区域并执行逆 Loop 细分进行简化。 最后,以向内分割方式进行边缘拼接,获取最终的简化模型。与经典算法在公开数据集上进行 实验对比,结果表明,该算法能够在简化的同时有效地保持网格特征,尽可能保留与原始网格 一致的规则的拓扑结构,并且在视觉质量上优于边折叠以及聚类简化算法。     

A mesh optimization algorithm based on neural networks

We have developed a mesh simplification method called GNG3D which is able to produce high quality approximations of polygonal models. This method consists of two distinct phases: an optimization phase and a reconstruction phase. The optimization phase is developed by applying an extension algorithm of the growing neural gas model, which constitutes an unsupervised incremental clustering algorithm. The primary goal of this phase is to obtain a simplified set of vertices representing the best approximation of the original 3D object. In the reconstruction phase we use the information provided by the optimization algorithm to reconstruct the faces obtaining the optimized mesh as a result. We study the model theoretically, analyzing its main components, and experimentally, using for this purpose some 3D objects with different topologies. To evaluate the quality of approximations produced by the method proposed in this paper, three existing error measurements are used. The ability of the model to establish the number of vertices of the final simplified mesh is demonstrated in the examples.     

基于CV／CAD的三维物体几何建模

在虚拟现实等技术领域中,都涉及到由现实世界中的实际景物建立对应的计算机描述的虚拟景物的问题,为此提出了利用计算机视觉与CAD几何建模技术相结合的三维珠体建模途径,首先通过编码光栅方法获取三维物体的深度图象,并采用数学形态学的方法加以分割,然后利用代数曲面拟合手段对分割后的三维曲面片进行重建,并使用CAD几何建模工具由重建的曲面片构成物体的几何模型,该文给出了初步的实验结果,证明所提出的技术途径基本可行。     

基于边折叠和质点-弹簧模型的网格简化优化算法

通过边折叠实现网格曲面简化，提出了保持曲面特征的边折叠基本规则，引入边折叠顺序控制因子λ，给出了折叠点坐标获取方法，简化过程中网格边长度趋于均匀．在曲面简化基础上，利用质点-弹簧模型优化网格形状．将网格顶点邻域参数化到二维域上，在质点-弹簧模型中引入约束弹簧，约束调整网格顶点，并逆映射到三维原始曲面上，局部优化网格顶点的相邻网格；调整曲面上所有网格顶点，在全局上优化网格形状．在曲面简化优化过程中，建立原始模型曲面和简化优化后曲面之间的双向映射关系；曲面的网格顶点始终在原始模型表面上滑动，并以双向Hausdorff距离衡量、控制曲面间的形状误差．应用实例表明：文中算法稳定、高效，适合于任意复杂的二维流形网格．     

Counting Hexagonal Patches and Independent Sets in Circle Graphs

A hexagonal patch is a plane graph in which inner faces have length 6, inner vertices have degree 3, and boundary vertices have degree 2 or 3. We consider the following counting problem: given a sequence of twos and threes, how many hexagonal patches exist with this degree sequence along the outer face? This problem is motivated by the enumeration of benzenoid hydrocarbons and fullerenes in computational chemistry. We give the first polynomial time algorithm for this problem. We show that it can be reduced to counting maximum independent sets in circle graphs, and give a simple and fast algorithm for this problem. It is also shown how to subsequently generate hexagonal patches.     

基于局部熵和四叉树结构的地形简化算法

地形实时简化在三维地形可视化和虚拟现实的应用中是非常重要的,为此提出了一种基于地形局部熵的实时地形简化算法,该算法采用四叉树结构进行地形简化,并使用局部熵作为误差测度来提高简化结果的质量,在四叉树结构“裂缝”的消除方面,采用更加合理的数据结构来提高算法的效率,实验结果表明,该算法具有实时,高效的特点,可以满足三维地形可视化和虚拟显示应用中地形实时简化与显示的要求。