Pattern flattening for orthotropic materials

In many applications it is necessary to define good-fitting 2D flattened patterns for user-defined regions of a larger 3D surface. This paper describes the major stages involved in pattern flattening and illustrates the process with examples. In generating 2D patterns, some distortion is inevitably involved if the target 3D surface is not developable. For situations where distortion is required, it can be quantified in terms of the energy that must be imparted to the 2D flattening in localised areas so that it takes-up the original 3D region of the surface. An orthotropic strain model is adopted to convert the strain values to energy values. Starting with a bi-parametric definition of a large 3D surface, an arbitrary defined region is specified by the user in terms of a contiguous series of cubic curves lying on the bi-parametric plane. To extract the 3D region, a polygon list is generated to represent the surface. The triangulation process is based on a ‘marching front’ algorithm. A process is described which then flattens this polygon list and performs an energy minimisation analysis every time the process attempts to flatten an over-constrained triangle. Further consideration is made of seam insertion in the 3D surface definition and of adaptively modifying the triangulation process so that more triangles are used in areas of high-energy concentration. Examples are also presented to illustrate the sensitivity of the strain profiles to the fabric grain direction when the pattern is applied to the 3D surface.     

基于三角形法向量的离散点三维构网方法

构建平面不规则三角网的算法已经很成熟,但普遍的算法都是基于某一投影平面,不能满足三维空间离散点的构网要求。本文在研究二维构网生长算法及现有 空间三维构网方法的基础上,提出利用空间三角形的法向量实现三维构网,详细讨论该算法的细节问题,并探讨提高构网速度的方法。通过实验证明该算法能快速、 有效、稳定地对复杂物体表面离散点构建空间三角网,达到建模效果,同时也体现出其应用范围的广阔性。     

1D and 2D structured mass-spring models with preload

In this paper, the objective is to enrich the existing 1D and 2D mass-spring models with physical accuracy as well as visual realism. It is found that using nonzero preloads on the springs is a necessary condition for the models to approximate their continuum counterparts. First, the parameters of the 1D mass-spring model of a beam are derived based on pure bending and axial action. It is proved that the mass-spring model with this set of parameter has correct characteristics of resistance against lateral displacement, which is one of the most important aspects of the accuracy of the 1D mass-spring model. Then, the method is extended to the 2D mass-spring models of the continuum plate with two different mesh structures. The mass-spring model with equilateral triangle meshes is shown to be physically more accurate than that with rectangular meshes. Finally, the physical accuracy that the mass-spring models with preload can achieve is investigated under different load conditions by comparison with the finite element method (FEM) to demonstrate the efficacy of our approach.     

综合录井井下三维地层可视化建模研究与实现

针对综合录井井下地层特点,采用多层DEM三维可视化模型对地下地质环境进行三维描述,实现综合录井三维地层实时显示.将三维坐标投影转换到二维坐标系中,采用二维Delaunay剖分改进算法构建Delaunay三角网;探讨了剖分后的不规则三角网(TIN)到格网的转换和插值以及通过格网DEM构建三维地层;介绍了根据选择的剖切面方程生成地质体的剖面.系统采用VC++6.0和OPENGL图形接口作为开发平台,可以从任意的角度对剖切开的三维地质体进行观察和分析也能够从任意的角度对三维地质体整体进行观察、缩放和剖切等操作.     

An improved physically-based method for geometric restoration of distorted document images

In document digitization through camera-based systems, simple imaging setups often produce geometric distortions in the resultant 2D images because of the non-planar geometric shapes of certain documents such as thick bound books, rolled, folded or crumpled materials, etc. Previous works have demonstrated that arbitrary warped documents can be successfully restored by flattening a 3D scan of the document. These approaches use physically-based or relaxation-based techniques in their flattening process. While this has been demonstrated to be effective in rectifying the image content and improving OCR, these previous approaches have several limitations in terms of speed and stability. In this paper, we propose a distance-based penalty metric to replace the mass-spring model and introduce additional bending resistance and drag forces to improve the efficiency of the existing approaches. The use of Verlet integration and special plane collision handling schemes also help to achieve better stability without sacrificing efficiency. Experiments on various document images captured from books, brochures and historical documents with arbitrary warpings have demonstrated large improvements over the existing approaches in terms of stability and efficiency.     

基于图像化几何的三维模型彩绘

基于纹理映射的彩绘系统通常受到从三维模型空间到二维纹理空间参数化的限制.如果一个模型具有复杂的拓扑结构或高度复杂的表面细节,寻找一个好的参数化方法通常是非常困难的,即使可以实现,通常也不能自动完成,需要用户手工交互进行.针对这种问题,提出了一种用于在三维模型表面直接进行彩绘的数据表示方法和一个原型系统,通过在三维模型中的每一个三角形上生成带有颜色信息的几何点,该系统可以支持许多与二维图像编辑类似的操作.其中一个关键的内容是提出了一种包含几何、拓扑和色彩信息在内的自适应的数据表示方法.这种方法被称为图像化的几何,它允许用户将每一个三角形视为一个三角形图像,并可以在不需要任何参数化的前提下在三维模型表面进行彩绘.系统的输入为一个常见的三角形网格模型,通过系统处理后变成一个在三角形上分布着带有颜色信息的几何点的三维表面.因为创建过程是自适应的,因此只有那些需要进行绘画纹理的三角形才需要创建几何点,这样可以节省存储消耗.将这种数据表示用于三维模型彩绘可以很好地处理具有复杂拓扑结构的模型.     

A Local/Global Approach to Mesh Parameterization

We present a novel approach to parameterize a mesh with disk topology to the plane in a shape‐preserving manner. Our key contribution is a local/global algorithm, which combines a local mapping of each 3D triangle to the plane, using transformations taken from a restricted set, with a global “stitch” operation of all triangles, involving a sparse linear system. The local transformations can be taken from a variety of families, e.g. similarities or rotations, generating different types of parameterizations. In the first case, the parameterization tries to force each 2D triangle to be an as‐similar‐as‐possible version of its 3D counterpart. This is shown to yield results identical to those of the LSCM algorithm. In the second case, the parameterization tries to force each 2D triangle to be an as‐rigid‐as‐possible version of its 3D counterpart. This approach preserves shape as much as possible. It is simple, effective, and fast, due to pre‐factoring of the linear system involved in the global phase. Experimental results show that our approach provides almost isometric parameterizations and obtains more shape‐preserving results than other state‐of‐the‐art approaches. We present also a more general “hybrid” parameterization model which provides a continuous spectrum of possibilities, controlled by a single parameter. The two cases described above lie at the two ends of the spectrum. We generalize our local/global algorithm to compute these parameterizations. The local phase may also be accelerated by parallelizing the independent computations per triangle.     

基于动态OBB层次结构的曲面相交算法*

为提高大曲面相交算法的效率,提出一种基于新的碰撞检测的曲面相交算法。该算法采用动态OBB层次结构碰撞算法获取相交区域,准确计算交点并构成交线;再利用分治三角化算法重构相交区域,以基于交线平均长度的方法去除窄小三角形,同时对空间闭合交线进行三角化,更新相交区域的三角形,并以闭合交线区分不同的区域。通过分析和实验结果证明,该算法能够对由大量三角形组成且相交情况比较复杂的曲面进行较快的处理。     

基于弹簧-质点模型曲面展开的改进算法

为了提高现有弹簧-质点模型曲面展开算法的速度和稳定性,提出了自适应时间步长方法.通过计算模型中各质点的惩罚力,实现了三角片翻转区域的整体调整;同时结合了考虑初速度和忽略初速度2种方法的优点;最后对一些参数的计算方法做了改进.实验结果表明,该算法能够有效地消除初始展开及优化过程中出现的翻转三角片,提高了复杂曲面的展开质量.     

Crest lines for surface segmentation and flattening

We present a method for extracting feature curves called crest lines from a triangulated surface. Then, we calculate the geodesic Voronoi diagram of crest lines to segment the surface into several regions. Afterward, barycentric surface flattening using theory from graph embeddings is implemented and, using the geodesic Voronoi diagram, we develop a faster surface flattening algorithm.     

Coarse-to-fine surface simplification with geometric guarantees

Let PC be a 3D point cloud and ε be a positive value called tolerance. We aim at constructing a triangulated surface S based on a subset PCU of PC such that all the points in PCL = PC ∖ PCU are at distance at most ε from a facet of S . (PCU and PCL respectively stand for Point Cloud Used and Point Cloud Left .) We call this problem simplification with geometric guarantees.
This paper presents a new framework to simplify with geometric guarantees. The approach relies on two main ingredients. First an oracle providing information on the surface being reconstructed even though the triangulated surface itself has not been computed. Second, a reconstruction algorithm providing incremental updates of the reconstructed surface, as well as a fast point-to-triangles distance computation. The oracle is used to guess a subset of the point cloud from which a triangulated surface is reconstructed. It relies on an implicit surface the triangulated surface is an approximation of, and is therefore available before the triangle mesh. The point-to-triangles distance computation and the local updates are then invoked to insert new vertices until the tolerance is met.
We also present a detailed experimental study which shows the efficiency of the simplification process both in terms of simplification rate and running time.
To the best of our knowledge, this algorithm is the first one performing coarse-to-fine surface simplification with geometric guarantees.     

基于三角域快速行进法的地震波走时计算

地震波走时计算是地震资料解释处理技术的重要组成部分,本文根据复杂地层构造中速度场分布的特点,设计了一种采用快速行进法基于三角网格的走时计算方法,针对计算效率优化和快速行进法在三角域上的计算格式进行了重点的研究,并根据地层限定条件对速度场进行网格剖分,在三角网格上用快速行进算法计算各点走时。与基于矩形网格的差分方法相比,该方法不需要对速度场边界进行任何平滑,无须通过细分网格来提高计算精度 可根据不同地质构造的复杂度进行变网格大小的剖分,网格剖分数目相对较少。最后通过计算实例进行了验证。     

大规模地貌场景的实时纹理合成

提出一种新的高效的大规模三维地貌纹理合成方法。把三维地貌场景进行透视变换投影到平面上,对这些平面上的三角网格赋一个连续的缩放因子场,把给定的纹理缩放成很多级别,使得可以和网格上的缩放因子相对应,按二维平面三角面片纹理合成的思想进行合成。实验表明,该方法在不拉伸纹理的同时能够达到实时,取得良好的视觉合成效果。     

Edgebreaker: connectivity compression for triangle meshes

Edgebreaker is a simple scheme for compressing the triangle/vertex incidence graphs (sometimes called connectivity or topology) of three-dimensional triangle meshes. Edgebreaker improves upon the storage required by previously reported schemes, most of which can guarantee only an O(t log(t)) storage cost for the incidence graph of a mesh of t triangles. Edgebreaker requires at most 2t bits for any mesh homeomorphic to a sphere and supports fully general meshes by using additional storage per handle and hole. For large meshes, entropy coding yields less than 1.5 bits per triangle. Edgebreaker's compression and decompression processes perform identical traversals of the mesh from one triangle to an adjacent one. At each stage, compression produces an op-code describing the topological relation between the current triangle and the boundary of the remaining part of the mesh. Decompression uses these op-codes to reconstruct the entire incidence graph. Because Edgebreaker's compression and decompression are independent of the vertex locations, they may be combined with a variety of vertex-compressing techniques that exploit topological information about the mesh to better estimate vertex locations. Edgebreaker may be used to compress the connectivity of an entire mesh bounding a 3D polyhedron or the connectivity of a triangulated surface patch whose boundary need not be encoded. The paper also offers a comparative survey of the rapidly growing field of geometric compression     

Comparative investigation of GPU-accelerated triangle-triangle intersection algorithms for collision detection

Efficient collision detection is critical in 3D geometric modeling. In this paper, we first implement three parallel triangle-triangle intersection algorithms on a GPU and then compare the computational efficiency of these three GPU-accelerated parallel triangle-triangle intersection algorithms in an application that detects collisions between triangulated models. The presented GPU-based parallel collision detection method for triangulated models has two stages: first, we propose a straightforward and efficient parallel approach to reduce the number of potentially intersecting triangle pairs based on AABBs, and second, we conduct intersection tests with the remaining triangle pairs in parallel based on three triangle-triangle intersection algorithms, i.e., the Möller’s algorithm, Devillers’ and Guigue’s algorithm, and Shen’s algorithm. To evaluate the performance of the presented GPU-based parallel collision detection method for triangulated models, we conduct four groups of benchmarks. The experimental results show the following: (1) the time required to detect collisions for the triangulated model consisting of approximately 1.5 billion triangle pairs is less than 0.5 s; (2) the GPU-based parallel collision detection method speedup over the corresponding serial version is 50x - 60x, and (3) Devillers’ and Guigue’s algorithm is comparatively and comprehensively the best of the three GPU-based parallel triangle-triangle intersection algorithms. The presented GPU-accelerated method is capable of efficiently detecting the potential collisions of triangulated models. Overall, the GPU-accelerated parallel Devillers’ and Guigue’s triangle-triangle intersection algorithm is recommended when performing practical collision detections between large triangulated models.

     

Computational surface flattening: a voxel-based approach

A voxel-based method for flattening a surface in 3D space into 2D while best preserving distances is presented. Triangulation or polyhedral approximation of the voxel data are not required. The problem is divided into two main parts: Voxel-based calculation of the minimal geodesic distances between points on the surface and finding a configuration of points in 2D that has Euclidean distances as close as possible to these distances. The method suggested combines an efficient voxel-based hybrid distance estimation method, that takes the continuity of the underlying surface into account, with classical multidimensional scaling (MDS) for finding the 2D point configuration. The proposed algorithm is efficient, simple, and can be applied to surfaces that are not functions. Experimental results are shown     

Constructing hierarchies for triangle meshes

We present a method to produce a hierarchy of triangle meshes that can be used to blend different levels of detail in a smooth fashion. The algorithm produces a sequence of meshes M₀, M₁, M ₂..., M_n, where each mesh M_i can be transformed to mesh M_i+1 through a set of triangle-collapse operations. For each triangle, a function is generated that approximates the underlying surface in the area of the triangle, and this function serves as a basis for assigning a weight to the triangle in the ordering operation and for supplying the points to which the triangles are collapsed. The algorithm produces a limited number of intermediate meshes by selecting, at each step, a number of triangles that can be collapsed simultaneously. This technique allows us to view a triangulated surface model at varying levels of detail while insuring that the simplified mesh approximates the original surface well     

基于三角网格构建的扫描测头半径三维补偿

采用扩展的自组织特征映射神经网络探讨了三坐标测量机接触式密集数据采集的测头半径三维补偿。构建了基于三角形网格构建的测头半径三维补偿模型。经过训练,神经网络将整个数字化点群数据分成许多子区域,每个子区域用一个微切平面逼近;对子区域的分类核心,即神经元位置权重,沿微切平面法矢方向进行修正,得到逼近测头球心面的三角形网格II;根据微切平面的法线,对测头半径进行三维补偿,得到逼近接触曲面的三角形网格III。测头半径三维补偿的法矢方向,也可通过估算三角网格II顶点的法矢得到。算例表明所创建的测头半径三维补偿模型有效可行。     

Freeform surface flattening based on fitting a woven mesh model

This paper presents a robust and efficient surface flattening approach based on fitting a woven-like mesh model on a 3D freeform surface. The fitting algorithm is based on tendon node mapping (TNM) and diagonal node mapping (DNM), where TNM determines the position of a new node on the surface along the warp or weft direction and DNM locates a node along the diagonal direction. During the 3D fitting process, strain energy of the woven model is released by a diffusion process that minimizes the deformation between the resultant 2D pattern and the given surface. Nodes mapping and movement in the proposed approach are based on the discrete geodesic curve generation algorithm, so no parametric surface or pre-parameterization is required. After fitting the woven model onto the given surface, a continuous planar coordinate mapping is established between the 3D surface and its counterpart in the plane, based on the idea of geodesic interpolation of the mappings of the nodes in the woven model. The proposed approach accommodates surfaces with darts, which are commonly utilized in clothing industry to reduce the stretch of surface forming and flattening. Both isotropic and anisotropic materials are supported.