Alternative Tilings for Improved Surface Area Estimates by Local Counting Algorithms

In this paper, we first review local counting methods for perimeter estimation of piecewise smooth binary figures on square, hexagonal, and triangular grids. We verify that better perimeter estimates, using local counting algorithms, can be obtained using hexagonal or triangular grids. We then compare surface area estimates using local counting techniques for binary three-dimensional volumes under the three semi-regular polyhedral tilings: the cubic, truncated octahedral, and rhombic dodecahedral tilings. It is shown that for surfaces of random orientation with a uniform distribution, the expected error of surface area estimates is smaller for the truncated octahedral and rhombic dodecahedral tilings than for the standard cubic or rectangular prism tilings of space. Additional properties of these tessellations are reviewed and potential applications of better surface area estimates are discussed.     

On the verification of polynomial system solvers

We discuss the verification of mathematical software solving polynomial systems symbolically by way of triangular decomposition. Standard verification techniques are highly resource consuming and apply only to polynomial systems which are easy to solve. We exhibit a new approach which manipulates constructible sets represented by regular systems. We provide comparative benchmarks of different verification procedures applied to four solvers on a large set of well-known polynomial systems. Our experimental results illustrate the high efficiency of our new approach. In particular, we are able to verify triangular decompositions of polynomial systems which are not easy to solve.     

An automatic coarse and fine surface mesh generation scheme based on medial axis transform: Part II implementation

In this paper, we present implementation aspects of a surface finite element (FE) meshing algorithm described in Part I (this volume) [1]. This meshing scheme is based on the medial axis transform (MAT) [2] to interrogate shape and to subdivide it into topologically simple subdomains. The algorithm can be effectively used to create coarse discretization and fine triangular surface meshes. We describe our techniques and methodology used in the implementation of the meshing and MAT algorithms. We also present some running times of our experimental system. We finally report the results we have obtained from several design and analysis applications which include adaptive surface approximations using triangular facets, and adaptiveh- andp-adaptive finite element analysis (FEA) of plane stress problems. These studies demonstrate the potential applicability of our techniques in computer aided design and analysis.     

Wavelet-based progressive compression scheme for triangle meshes: wavemesh

We propose a new lossy to lossless progressive compression scheme for triangular meshes, based on a wavelet multiresolution theory for irregular 3D meshes. Although remeshing techniques obtain better compression ratios for geometric compression, this approach can be very effective when one wants to keep the connectivity and geometry of the processed mesh completely unchanged. The simplification is based on the solving of an inverse problem. Optimization of both the connectivity and geometry of the processed mesh improves the approximation quality and the compression ratio of the scheme at each resolution level. We show why this algorithm provides an efficient means of compression for both connectivity and geometry of 3D meshes and it is illustrated by experimental results on various sets of reference meshes, where our algorithm performs better than previously published approaches for both lossless and progressive compression.     

三维数字牙颌模型分析诊断系统设计

利用三维测量技术获取含咬合信息的数字牙颌模型,建立网格包围盒层次表示结构,并在其基础上实现网格单元快速拾取框架,结合特征提取算法,实现模型分析的常用功能;参考正常合数据库中的标准值生成初步诊断报表．应用该系统有助于提高正畸临床的诊断水平。     

Matrix structures in parallel matrix computations

We survey certain techniques such as approximation, interpolation and embedding in matrix algebra, which are particularly useful to devise fast parallel algorithms for some matrix-structured problems. The problems we consider are triangular Toeplitz matrix inversion and its algebraic counterpart polynomial division, matrix multiplication, and some computations concerning banded Toeplitz matrices.     

Homotopy techniques for multiplication modulo triangular sets

We study the cost of multiplication modulo triangular families of polynomials. Following previous work by Li et al. (2007), we propose an algorithm that relies on homotopy and fast evaluation–interpolation techniques. We obtain a quasi-linear time complexity for substantial families of examples, for which no such result was known before. Applications are given notably to additions of algebraic numbers in small characteristic.     

Combination of augmented Lagrangian technique and ST preconditioner for saddle point problems

For symmetric indefinite linear systems, we introduce a new triangular preconditioner based on symmetric and triangular (ST) decomposition. A new (1, 1) block is obtained by augmented Lagrangian technique. The new ST preconditioner is introduced by the combination of the new (1, 1) block and symmetric and triangular (ST) decomposition. Then a preconditioned system can be obtained by preconditioning technique, which is superior to the original system in terms of condition number. We study the spectral properties of preconditioned system, such as eigenvalues, the estimation of condition number and then give the quasi-optimal parameter. Numerical examples are given to indicate that the new preconditioner has obvious efficiency advantages. Finally, we conclude that the new ST preconditioner is a better option to deal with large and sparse problems.     

Block jacobi preconditioning of the conjugate gradient method on a vector processor

The preconditioned conjugate gradient method is well established for solving linear systems of equations that arise from the discretization of partial differential equations. Point and block Jacobi preconditioning are both common preconditioning techniques. Although it is reasonable to expect that block Jacobi preconditioning is more effective, block preconditioning requires the solution of triangular systems of equations that are difficult to vectorize. We present an implementation of block Jacobi for vector computers, especially for the Cray Y-MP/264, and discuss several techniques to improve vectorization. We present these in a progression to show the effect on performance. For the model problem, resulting from a self-adjoint operator, the final implementation of one block Jacobi step uses almost the same amount of time as one point Jacobi step on the Cray Y-MP/264 despite the solution of triangular systems.     

基于内在变量的空间三角网格的形状混合

本文给出了基于内在变量插值的空间三角网格形状混合的内在解算法。     

Automatic Shape Control of Triangular B-Splines of Arbitrary Topology

Triangular B-splines are powerful and flexible in modeling a broader class of geometric objects defined over arbitrary, non-rectangular domains. Despite their great potential and advantages in theory, practical techniques and computational tools with triangular B-splines are less-developed. This is mainly because users have to handle a large number of irregularly distributed control points over arbitrary triangulation. In this paper, an automatic and efficient method is proposed to generate visually pleasing, high-quality triangular B-splines of arbitrary topology. The experimental results on several real datasets show that triangular B-splines are powerful and effective in both theory and practice.     

Multiresolution methods for nonmanifold models

The concept of fairing applied to triangular meshes with irregular connectivity has become more and more important. Previous contributions proposed a variety of fairing operators for manifolds and applied them to the design of multi-resolution representations and editing tools for meshes. In this paper, we generalize these powerful techniques to handle non-manifold models. We propose a method to construct fairing operators for non-manifolds which is based on standard operators for the manifold setting. Furthermore, we describe novel approaches to guarantee volume preservation. We introduce various multi-resolution techniques that allow us to represent, smooth and edit non-manifold models efficiently. Finally, we discuss a semi-automatic feature preservation strategy to retain important model information during the fairing process     

Computing the block factorization of complex Hankel matrices

In this paper, we present an algorithm for finding an approximate block diagonalization of complex Hankel matrices. Our method is based on inversion techniques of an upper triangular Toeplitz matrix, specifically, by simple forward substitution. We also consider an approximate block diagonalization of complex Hankel matrices via Schur complementation. An application of our algorithm by calculating the approximate polynomial quotient and remainder appearing in the Euclidean algorithm is also given. We have implemented our algorithms in Matlab. Numerical examples are included. They show the effectiveness of our strategy.     

三角域上Said-Ball基的推广渐近迭代逼近

目的：如果一组基函数是规范全正（Normalized Totally Positive, abbr. NTP）的,并且对应的配置矩阵是非奇异的,那么由它所生成的参数曲线或张量积曲面具有渐近迭代逼近（progressive iteration approximation, abbr. PIA）性质。为了进一步推广渐近迭代逼近性质的适用范围,本文提出对于一组基函数,如果其对应的配置矩阵不是全正的,那么该基函数也可能具有渐近迭代逼近性质。方法：提出的定理是以基函数具有渐近迭代逼近性质时其对应的配置矩阵所需满足的条件作为理论基础,建立了配置矩阵为严格对角占优或者广义严格对角占优矩阵与基函数具有渐近迭代逼近性质之间的联系。结果：配置矩阵为严格对角占优或者广义严格对角占优矩阵,则相应的三角曲面具有PIA性质或带权PIA性质,即广义PIA性质。数值试验验证了上述理论,并细致地分析了三角域上的低次Said-Ball基,指出了它们具有相应的广义PIA性质。结论：本文将渐近迭代逼近的适用范围推广到三角域上的一般混合基函数。类似三角域上Said-Ball基,本文算法亦可用于研究三角域上的其他各类广义Ball基的PIA性质。     

Diffusion equations over arbitrary triangulated surfaces for filtering and texture applications

In computer graphics, triangular mesh representations of surfaces have become very popular. Compared with parametric and implicit forms of surfaces, triangular mesh surfaces have many advantages, such as easy to render, convenient to store and the ability to model geometric objects with arbitrary topology. In this paper, we are interested in data processing over triangular mesh surfaces through PDEs (partial differential equations). We study several diffusion equations over triangular mesh surfaces, and present corresponding numerical schemes to solve them. Our methods work for triangular mesh surfaces with arbitrary geometry (the angles of each triangle are arbitrary) and topology (open meshes or closed meshes of arbitrary genus). Besides the flexibility, our methods are efficient due to the implicit/semi-implicit time discretization. We finally apply our methods to several filtering and texture applications such as image processing, texture generating and regularization of harmonic maps over triangular mesh surfaces. The results demonstrate the flexibility and effectiveness of our methods.     

High-quality rendering of quartic spline surfaces on the GPU

We present a novel GPU-based algorithm for high-quality rendering of bivariate spline surfaces. An essential difference to the known methods for rendering graph surfaces is that we use quartic smooth splines on triangulations rather than triangular meshes. Our rendering approach is direct in the sense that since we do not use an intermediate tessellation but rather compute ray-surface intersections (by solving quartic equations numerically) as well as surface normals (by using Bernstein-Bézier techniques) for Phong illumination on the GPU. Inaccurate shading and artifacts appearing for triangular tesselated surfaces are completely avoided. Level of detail is automatic since all computations are done on a per fragment basis. We compare three different (quasi-) interpolating schemes for uniformly sampled gridded data, which differ in the smoothness and the approximation properties of the splines. The results show that our hardware based renderer leads to visualizations (including texturing, multiple light sources, environment mapping, etc.) of highest quality.     

Cross‐migrative triangular norms

We study the cross‐migrativity of triangular norms. The classes of continuous triangular norms, which are cross‐migrative with respect to some strict or nilpotent triangular norm, respectively, are completely characterized, as well as those which are cross‐migrative with respect to the greatest and smallest triangular norms, respectively. As a by‐product, parametric systems of equivalence relations on the classes of strict and nilpotent triangular norms are found. © 2012 Wiley Periodicals, Inc.     

Surface Modelling and Mesh Generation for Simulating Superplastic Forming

This paper presents an approach which enables surface modelling, mesh generation and the Finite Element (FE) analysis to be integrated together to simulate superplastic forming process for complex shaped components. Techniques have been developed to generate an FE mesh over non-four-sided surface areas, the boundaries of which are Bezier curves of arbitrary degree, using a consistent expression. Theoretical evidence is given to determine the number of Bezier triangular patches required for accurately re-constructing die surfaces within a commercial FE solver. The developed techniques have been successfully used in determining the process parameters for forming a 3D rectangular box.     

Surface Modellinhg and Mesh Generation for Simulating Superplastic Forming

This paper presents an approach which enables surface modelling,mesh generation and the Finite Element(FE) analysis to be integrated together to simulate superplastic forming process for complex shaped components.Techniques have been developed to generate an FE mesh over non-four-sided surface areas,the boundaries of which are Bezier curves of arbitrary degree,using a consistent expression.Theoretical evidence is given to determine the number of Bezier triangular patches required for accurately re-constructing die surfaces within a commercial FE solver.The developed techniques have been successfully used in determining the process parameters for forming a 3D rectangular box.