Perfect Matching Quad Layouts for Manifold Meshes

This paper introduces a new approach to automatically generate pure quadrilateral patch layouts on manifold meshes. The algorithm is based on a careful construction of a singularity graph of a given input frame field or a given periodic global parameterization. A pure quadrilateral patch layout is then derived as a constrained minimum weight perfect matching of that graph. The resulting layout is optimal relative to a balance between coarseness and geometric feature alignment. We formulate the problem of finding pure quadrilateral patch layouts as a global optimization problem related to a well‐known concept in graph theory. The main advantage of the new method is its simplicity and its computation speed. Patch layouts generated by the present algorithm are high quality and are very competitive compared to current state of the art.     

一种QR码的预处理方法

针对摄像机采集的快速响应码(QR码)在提取之前存在光照不均匀以及可能产生的旋转、扭曲等现象,提出一种自适应阈值算法。对图像进行二值化,将Roberts算子与小波模极大值相结合,克服传统边缘检测算法对噪声敏感的缺点,提取QR码的边缘信息。根据四边形4个顶点到与对角线平行的直线的最短距离来定位QR码,并利用双线性差值进行纠正。实验结果证明了该算法的可靠性。     

Automatic comic page segmentation based on polygon detection

Comic page segmentation aims to automatically decompose scanned comic images into storyboards (frames), which is the key technique to produce digital comic documents that are suitable for reading on mobile devices. In this paper, we propose a novel method for comic page segmentation by finding the quadrilateral enclosing box of each storyboard. We first acquire the edge image of the input comic image, and then extract line segments with a heuristic line segment detection algorithm. We perform line clustering to further merge the overlapped line segments and remove the redundancy line segments. Finally, we perform another round of line clustering and post-processing to compose the obtained line segments into complete quadrilateral enclosing boxes of the storyboards. The proposed method is tested on 2,237 comic images from 12 different printed comic series, and the experimental results demonstrate that our method is effective for comic image segmentation and outperforms the existing methods.     

基于IFS的Sierpinski三角形的生成及其推广

阐述了基于IFS的Sierpinski三角形分形图形的生成原理,并对其生成技术进行推广。包括两个方面的推广,第一,生成元形状可以为点、线段、三角形、四边形（正方形）、圆,得到的吸引子相同,由此得到吸引子与生成元形状无关的结论。第二,对Sierpinski三角形的IFS进行适当的调节,可以得到新的IFS,并生成新的吸引子,这为从已知的IFS得到新的IFS提供了参考方法。     

Localized coarsening of conforming all-hexahedral meshes

Finite element mesh adaptation methods can be used to improve the efficiency and accuracy of solutions to computational modeling problems. In many applications involving hexahedral meshes, localized modifications which preserve a conforming all-hexahedral mesh are desired. Effective hexahedral refinement methods that satisfy these criteria have recently become available; however, due to hexahedral mesh topology constraints, little progress has been made in the area of hexahedral coarsening. This paper presents a new method to locally coarsen conforming all-hexahedral meshes. The method works on both structured and unstructured meshes and is not based on undoing previous refinement. Building upon recent developments in quadrilateral coarsening, the method utilizes hexahedral sheet and column operations, including pillowing, column collapsing, and sheet extraction. A general algorithm for automated coarsening is presented and examples of models that have been coarsened with this new algorithm are shown. While results are promising, further work is needed to improve the automated process.     

Grid-based hexahedral element meshing algorithms for solid models with concave curved boundary lines

This paper presented a grid-based hexahedral element mesh generation algorithm for solid models with concave curved boundary lines. A deep study was focused on the boundary matching and quality improvement techniques. Firstly, a method for computing the curvature values of the triangle facets and sub-surfaces was proposed. In order to improve the surface mesh quality, a layer of new elements was inserted on the surface of the jagged core mesh. Then, a relative position relationship method was used to match C-edges of the solid model. Eight different types of free quadrilateral facet configurations were established. In order to handle the concave curve-matching problem, this paper proposed a method to modify the matching properties of the degenerate quadrilateral facets fitted on the same concave curved boundary line by unifying their orientations to point to the same sub-surface. In addition, six mixed templates were newly proposed to improve the geometrical topology of the degenerate elements associated with concave curves and sharp features. The positions of the nodes were smoothed by the modified Laplacian method and objective function. Finally, the effectiveness and reliability of the algorithms proposed in this paper were demonstrated by a practical example.     

基于三角形连接的有限元网格划分

文中创新地提出了三角形连接的有限元网格划分的算法,但是三角形并不是有限元计算的基本单元,而是根据已经生成的三角形生成较为规整的四边形。在实际的项目过程中,创新地提出了三种有效的算法,并利用C＋＋面向对象的MFC程序设计和编写。本程序可以从模型文件读取边界以及点约束和线约束特征数据,程序自动计算出一个较为合理的边界间距值,并且根据需要人工或自动选择一种划分算法,从而自动完成高质量的四边形网格划分。三种算法皆可以处理大量数据点和线,并且划分速度较为高效。本程序模块成功应用于有限元计算软件中。     

An algorithm for automatic 2D quadrilateral mesh generation with line constraints

Finite element method (FEM) is a fundamental numerical analysis technique widely used in engineering applications. Although state-of-the-art hardware has reduced the solving time, which accounts for a small portion of the overall FEM analysis time, the relative time needed to build mesh models has been increasing. In particular, mesh models that must model stiffeners, those features that are attached to the plate in a ship structure, are imposed with line constraints and other constraints such as holes. To automatically generate a 2D quadrilateral mesh with the line constraints, an extended algorithm to handle line constraints is proposed based on the constrained Delaunay triangulation and Q-Morph algorithm. The performance of the proposed algorithm is evaluated, and numerical results of our proposed algorithm are presented.     

共轭梯度法的GPU实现

提出基于图形处理单元（GPU）实现矩阵与向量相乘的新算法,只需渲染四边形一次即可实现矩阵与向量乘法。并给出实现向量元素求和的新算法,与缩减算法不同,该算法不要求向量大小为2的幂。基于这2种算法使用OpenGL着色语言（GLSL）编程,用GPU实现求解线性方程组的共轭梯度法。与Krtiger算法相比,该方法所用计算时间更少。     

边界简化与多目标优化相结合的高质量四边形网格生成

目的 高质量四边形网格生成是计算机辅助设计、等几何分析与图形学领域中一个富有挑战性的重要问题。针对这一问题,提出一种基于边界简化与多目标优化的高质量四边形网格生成新框架。方法 首先针对亏格非零的平面区域,提出一种将多连通区域转化为单连通区域的方法,可生成高质量的插入边界;其次,提出"可简化角度"和"可简化面积比率"两个阈值概念,从顶点夹角和顶点三角形面积入手,将给定的多边形边界简化为粗糙多边形;然后对边界简化得到的粗糙多边形进行子域分解,并确定每个子域内的网格顶点连接信息;最后提出四边形网格的均匀性和正交性度量目标函数,并通过多目标非线性优化技术确定网格内部顶点的几何位置。结果 在同样的离散边界下,本文方法与现有方法所生成的四边网格相比,所生成的四边网格顶点和单元总数目较少,网格单元质量基本类似,计算时间成本大致相同,但奇异点数目可减少70% 80%,衡量网格单元质量的比例雅克比值等相关指标均有所提高。结论 本文所提出的四边形网格生成方法能够有效减少网格中的奇异点数目,并可生成具有良好光滑性、均匀性和正交性的高质量四边形网格,非常适用于工程分析和动画仿真。