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.This work was partially supported by the National Science Foundation's US-Italy Collaborative Research Program under Grant INT-8714578 and Information, Robotics, and Intelligent Research Grant IRI-8704781.     

Applications of the discrete element method in mechanical engineering

Compared to other fields of engineering, in mechanical engineering, the Discrete Element Method (DEM) is not yet a well known method. Nevertheless, there is a variety of simulation problems where the method has obvious advantages due to its meshless nature. For problems where several free bodies can collide and break after having been largely deformed, the DEM is the method of choice. Neighborhood search and collision detection between bodies as well as the separation of large solids into smaller particles are naturally incorporated in the method. The main DEM algorithm consists of a relatively simple loop that basically contains the three substeps contact detection, force computation and integration. However, there exists a large variety of different algorithms to choose the substeps to compose the optimal method for a given problem. In this contribution, we describe the dynamics of particle systems together with appropriate numerical integration schemes and give an overview over different types of particle interactions that can be composed to adapt the method to fit to a given simulation problem. Surface triangulations are used to model complicated, non-convex bodies in contact with particle systems. The capabilities of the method are finally demonstrated by means of application examples. Commemorative Contribution.     

Mesh data structure selection for mesh generation and FEA applications

The data structure representing a mesh and the operators to create and query such a database play a crucial role in the performance of mesh generation and FE analysis applications. The design of such a database must balance the conflicting requirements of compactness and computational efficiency. In this article, 10 different mesh representations are reviewed for linear tetrahedral and hexahedral meshes. A methodology for calculating the storage and computational costs of mesh representations is presented and the 10 data structures are analysed. Also, a system for ranking different data structures based on their computational and storage costs is devised and the various mesh representations are ranked according to this measure. Copyright © 2002 John Wiley & Sons, Ltd.     

《周培德三角剖分不是最小权三角剖分》一文商榷——反例不成立

周培协三角剖分是否能得到最小权三角剖分，周培德在《周培德三角部分不是最小权三角剖分》一文撰写之前已有新的结论，本文还指出《周培德三角剖分不是最小权三角剖分》一文所举反例不成立。     

Projection center calibration by motion

Camera calibration is the first step of three-dimensional machine vision. A fundamental parameter to be calibrated is the position of the camera projection center with respect to the image plane. This paper presents a method for the computation of the projection center position using images of a translating rigid object, taken by the camera itself.

Many works have been proposed in literature to solve the calibration problem, but this method has several desirable features. The projection center position is computed directly, independently of all other camera parameters. The dimensions and position of the object used for calibration can be completely unknown.

This method is based on a geometric relation between the projection center and the focus of expansion. The use of this property enables the problem to be split into two parts. First a suitable number of focuses of expansion are computed from the images of the translating object. Then the focuses of expansion are taken as landmarks to build a spatial back triangulation problem, the solution of which gives the projection center position.     

裁剪曲面的三角化及图形显示

结合自主版权的超人ＣＡＤ／ＣＡＭ系统的开发，本文提出了一种适合于裁剪曲面图形显示的曲面三角化算法，该算法将曲面的三角化转化为曲面参数域的三角化，并将二维图形的集合运算与Ｄｅｌａｕｎａｙ三角剖分应有和于曲面参数域边界的处理，从而使裁剪曲面在边界上的三角形分布均匀。     

基于Delaunay三角网的任意多边形三角剖分算法研究

文章通过分析现有多边形三角剖分算法,给出一种基于Delaunay三角网的任意复杂多边形三角剖分的改进算法。算法首先忽略多边形顶点与边线间的逻辑关系,将其看做散乱顶点的集合,然后采用Delaunay三角化方法对点集进行合理剖分,再依据多边形顶点及边线间的逻辑关系,逐一将那些不合理的三角网剔除,最终重新组合出符合要求的三角网格。     

可控的高度规整三角网格生成算法

本文提出了一种新的用户可控的高度规整三角网格生成算法.通过在网格表面上构造3个标量场,利用其等值线相交生成高度规整的三角网格.算法借助N-对称方向场来指导生成网格的边方向,在网格表面指定密度场来控制采样密度,同时还提供了特征对齐和对带边界模型的处理能力.所有的控制需求都被纳入标量场求解框架中统一优化.实验表明,本文的方法能够满足多种用户控制需求,生成高度规整的三角网格.     

动态优化不等精度经纬仪交会方法

在多台不等精度经纬仪交会测量系统中,为提高数据的可靠性和精度,根据异面交会原理,提出空间定位精度及其误差的模型;提出采用定常异动算子算法和普通加权平均法相结合的处理方法;对该算法进行数学仿真,计算分别使用定常异动算子和普通加权平均法的交会角区间,并在实际任务中加以应用。试验结果表明,采用合理的算法对多台不等精度经纬仪进行交会测量,增加了测量基线数量从而提高了整体数据的稳定性,同时提高了测量精度。     

A faster divide-and-conquer algorithm for constructing delaunay triangulations

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its (n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn2¹⁶, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL _p metric for 1<p.This research was supported by National Science Foundation Grants DCR-8352081 and DCR-8416190.