On sorting triangles in a delaunay tessellation

In a two-dimensional Delaunay-triangulated domain, there exists a partial ordering of the triangles (with respect to a vertex) that is consistent with the two-dimensional visibility of the triangles from that vertex. An equivalent statement is that a polygon that is star-shaped with respect to a given vertex can be extended, one triangle at a time, until it includes the entire domain. Arbitrary planar triangulations do not possess this useful property which allows incremental processing of the triangles.     

Blocking for external graph searching

In this paper we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for completed-ary trees andd-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex. We also show that, for the special case of grid graphs blocked with isothetic hypercubes, there is a provably better speed-up if even a small amount of redundancy is permitted.Support was provided in part by an IBM Graduate Fellowship, by NSF Research Grants CCR-9007851 and IRI-9116451, and by Army Research Office Grant DAAL03-91-G-0035.Support was provided in part by NSF Grants CCR-9003299, CCR-9300079, and IRI-9116843, and by NSF/DARPA Grant CCR-8908092.Support was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, and by Army Research Office Grant DAAL03-91-G-0035.     

Curvature estimation for meshes based on vertex normal triangles

The estimation of surface curvature is essential for a variety of applications in computer graphics because of its invariance with respect to rigid transformations. In this article, we describe a curvature estimation method for meshes by converting each planar triangular facet into a curved patch using the vertex positions and the normals of three vertices of each triangle. Our method interpolates three end points and the corresponding normal vectors of each triangle to construct a curved patch. Then, we compute the per triangle curvature of the neighboring triangles of a mesh point of interest. Similar to estimating per vertex normal from the adjacent per triangle normal, we compute the per vertex curvature by taking a weighted average of per triangle curvature. Through some examples, we demonstrate that our method is efficient and its accuracy is comparable to that of the existing methods.     

Multiresolution indexing of triangulated irregular networks

We show how to build a continuous, one-dimensional index of the points on a triangulated irregular network (TIN). The index is constructed by first finding an ordering of the triangles in which consecutive triangles share a vertex or an edge. Then, the space within each triangle is continuously indexed with a space-filling curve that begins at one vertex of the triangle and ends at another. The space-filling curve is oriented such that the first point in each triangle is a vertex shared with the previous triangle and the last point is a vertex shared with the next triangle. Furthermore, our index can be refined locally and, therefore, efficiently when the TIN is augmented by filling any face with another TIN (to make a hierarchical TIN). Such processes arise, for example, in the elaboration of detail on a graphical surface.     

Mesh simplification by stochastic sampling and topological clustering

We introduce TopStoc, a fast mesh simplification algorithm. The two main components are stochastic vertex selection and re-indexing of triangles. The probability for vertex selection depends on a local feature estimator, which prefers areas of high curvatures but still ensures sufficient sampling in flat parts. Re-indexing the triangles is done by breadth-first traversal starting from the selected vertices and then identifying triangles incident upon three regions. Both steps are linear in the number of triangles, require minimal data, and are very fast, while still preserving geometrical and topological features. Additional optional processing steps improve sampling properties and/or guarantee homotopy equivalence with the input. These properties provide an alternative to vertex clustering especially for CAD/CAM models in the areas of previewing or network graphics.     

Uniform remeshing with an adaptive domain: a new scheme for view-dependent level-of-detail rendering of meshes

We present a new algorithm for view-dependent level-of-detail rendering of meshes. Not only can it effectively resolve complex geometry features similar to edge collapse-based schemes, but it also produces meshes that modern graphics hardware can render efficiently. This is accomplished through a novel hybrid approach: for each frame, we view-dependently refine the progressive mesh (PM) representation of the original mesh and use the output as the base domain of uniform regular refinements. The algorithm exploits frame-to-frame coherence and only updates portions of the output mesh corresponding to modified domain triangles. The PM representation is built using a custom volume preservation-based error function. A simple k-d tree enhanced jump-and-walk scheme is used to quickly map from the dynamic base domain to the original mesh during regular refinements. In practice, the PM refinement provides a view-optimized base domain for later regular refinements. The regular refinements ensure almost-everywhere regularity of output meshes, allowing optimization for vertex cache coherence and caching of geometry data in high-performance graphics memory. Combined, they also have the effect of allowing our algorithm to operate on uniform clusters of triangles instead of individual ones, reducing CPU workload.     

Observability for two-dimensional systems

Sufficient conditions that a two-dimensional system with output is locally observable are presented. Known results depend on time derivatives of the output and the inverse function theorem. In some cases, no information is provided by these theories, and one must study observability by other methods. We dualize the observability problem to the controllability problem, and apply the deep results of Hermes on local controllability to prove a theorem concerning local observability.Research supported by NASA Ames Research Center under Grant NAG2-189 and the Joint Services Electronics Program under ONR Contract N0014-76-C1136.Research supported by NASA Ames Research Center under Grant NAG2-203 and the Joint Services Electronics Program under ONR Contract N0014-76-C1136.     

复杂带状图像的快速三角剖分与骨架化算法

为了快速准确地计算带状图像的骨架，以便对其进行识别、重建等处理，提出一种基于快速三角剖分的骨架化算法，首先通过对带状图像边界的近似多边形进行三角剖分，生成一系列具有拓扑关系的三角形，然后根据三角形的类型生成局部骨架，最后连接生成整幅带状图像的骨架．该算法充分利用了图像的整体与局部信息，且与分辨率无关。     

三维不规则三角网格的精确裁剪算法

给出了一种基于约束Delaunay三角剖分的三维不规则三角网格的精确裁剪算法。算法结合TIN数据的生成特点,首先将TIN投影到二维平面,然后利用约束Delaunay三角剖分把裁剪多边形的每条边嵌入三角网中,再利用边-三角形的拓扑关系删除裁剪多边形外部多余三角形,最后利用边-点的拓扑关系对裁剪多边形顶点高程进行插值,使生成裁剪后的TIN模型。对不同复杂程度的三维TIN模型进行裁剪实验,发现二维投影策略极大地提高了三维TIN裁剪效率。算法的程序实现简单,且符合工程需求。     

基于贪心优化策略的网格排布算法

针对由存储带宽和数据访问速度导致的复杂数据集绘制性能低下等问题,提出了一种基于贪心优化策略的三角形排布算法,通过对绘制数据集进行重排以改善数据的空间局部性和时间局部性。该算法首先将顶点分为三类,根据改进的代价函数选择代价度量最小的顶点作为活动顶点;然后绘制（即输出）其所有未绘制的邻接三角形,并将相邻顶点压入缓存,算法迭代执行直到所有顶点的邻接三角形都绘制完成,得到重新排列后的三角形序列。实验结果表明,该算法不仅具备较高的顶点缓存命中率,还提高了渲染速度,减少了排序的时间,有效地解决了图形处理器的处理速度不断提升而数据访问速度严重滞后的问题。     

Searching for empty convex polygons

A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear-time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r> 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.The first author is pleased to acknowledge support by the National Science Foundation under Grant CCR-8700917. The research of the second author was supported by Amoco Foundation Faculty Development Grant CS 1-6-44862 and by the National Science Foundation under Grant CCR-8714565.     

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

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

提高数控加工仿真速度和效果的关键技术研究

提出了三角网格模型局部重绘的顶点搜索算法，以提高数控加工动态仿真的速度和效果．每仿真一条加工代码，先为所有被改变的三角片构造一个略宽的包围盒，然后通过对该包围盒内部的像素点，以及沿，方向从包围盒上下两条边出发对它外部的像素点进行搜索，获得完全或部分位于包围盒内的三角片所对应的顶点，并依此重绘这些三角片．在此基础上改进了本单位自主研制的机械CAD/CAM系列软件中加工仿真软件的功能，并通过对比测试，表明在仿真速度和效果两方面接近国外主流商业仿真软件．     

Ray shooting in polygons using geodesic triangulations

LetP be a simple polygon withn vertices. We present a simple decomposition scheme that partitions the interior ofP intoO(n) so-called geodesic triangles, so that any line segment interior toP crosses at most 2 logn of these triangles. This decomposition can be used to preprocessP in a very simple manner, so that any ray-shooting query can be answered in timeO(logn). The data structure requiresO(n) storage andO(n logn) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time toO(n). We also extend our general technique to the case of ray shooting amidstk polygonal obstacles with a total ofn edges, so that a query can be answered inO( logn) time.Work by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-89-21421. Work by Micha Sharir has been supported by ONR Grants N00014-89-J-3042 and N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

A robust hole-filling algorithm for triangular mesh

This paper presents a novel hole-filling algorithm that can fill arbitrary holes in triangular mesh models. First, the advancing front mesh technique is used to cover the hole with newly created triangles. Next, the desirable normals of the new triangles are approximated using our desirable normal computing schemes. Finally, the three coordinates of every new vertex are re-positioned by solving the Poisson equation based on the desirable normals and the boundary vertices of the hole. Many experimental results and error evaluations are given to show the robustness and efficiency of the algorithm.     

一种改进的MC算法

为了对等值面与子等值面进行提取和分组,在MC算法原理的基础上,提出了一种改进的等值面提取与子等值面分组算法。该算法首先将数据场分解为点、棱边、面与体元的拓扑结构;然后在整个数据场范围内求所有棱边与等值面的交点,并在面内连接交点形成面与等值面的交线,交线在体元内连接生成空间多边形;接着通过三角化各个体元内的空间多边形得到由顶点表与三角形表组成的等值面数据;最后根据三角形在顶点处的连接关系,采用种子算法对属于同一子等值面的三角形与顶点进行标记,属于同一子等值面的顶点与三角形将被存放在独立的顶点表与三角形表中。实验结果表明,该算法可以高效地实现等值面提取与子等值面的分组。     

Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs

The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant ε > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (ku, kl), our algorithm constructs a vertex cover of size (ku*, kl* ), satisfying max{ku*/ku, kl* /kl} 1 ε.     

Optimal iterative learning control for end-point product qualities in semi-batch process based on neural network model

An optimal iterative learning control (ILC) strategy of improving endpoint products in semi-batch processes is presented by combining a neural network model. Control affine feed-forward neural network (CAFNN) is proposed to build a model of semi-batch process. The main advantage of CAFNN is to obtain analytically its gradient of endpoint products with respect to input. Therefore, an optimal ILC law with direct error feedback is obtained explicitly, and the convergence of tracking error can be analyzed theoretically. It has been proved that the tracking errors may converge to small values. The proposed modeling and control strategy is illustrated on a simulated isothermal semi-batch reactor, and the results show that the endpoint products can be improved gradually from batch to batch. Supported by the National Natural Science Foundation of China (Grant Nos. 60404012, 60874049), the National High-Tech Research & Development Program of China (Grant No. 2007AA041402), the New Star of Science and Technology of Beijing City (Grant No. 2006A62), and the IBM China Research Lab 2008 UR-Program     

Oversampling analysis in fractional Fourier domain

Oversampling is widely used in practical applications of digital signal processing. As the fractional Fourier transform has been developed and applied in signal processing fields, it is necessary to consider the oversampling theorem in the fractional Fourier domain. In this paper, the oversampling theorem in the fractional Fourier domain is analyzed. The fractional Fourier spectral relation between the original oversampled sequence and its subsequences is derived first, and then the expression for exact reconstruction of the missing samples in terms of the subsequences is obtained. Moreover, by taking a chirp signal as an example, it is shown that, reconstruction of the missing samples in the oversampled signal is suitable in the fractional Fourier domain for the signal whose time-frequency distribution has the minimum support in the fractional Fourier domain. Supported partially by the National Natural Science Foundation of China for Distinguished Young Scholars (Grant No. 60625104), the National Natural Science Foundation of China (Grant Nos. 60890072, 60572094), and the National Basic Research Program of China (Grant No. 2009CB724003)     

虚拟环境中多细节层次模型生成新算法

网格简化在科学计算可视化和虚拟现实等领域具有重要意义,它有利于降低几何模型的复杂度,提高模型实时绘制的速度。本文提出一个基于法向矢量的模型简化算法,算法通过比较顶点法矢与关联三角形法矢的夹角,有序地删除顶点,重组简化模型的拓扑结构。实验结果表明,算法在不影响模型视觉特征的前提下,实现了模型较大幅度的简化。