Mesh Segmentation Refinement

This paper proposes a method for refining existing mesh segmentations, employing a novel extension of the active contour approach to meshes. Given a segmentation, produced either by an automatic segmentation method or interactively, our algorithm propagates the segment boundaries to more appropriate locations. In addition, unlike most segmentation algorithms, our method allows the boundaries to pass through the mesh faces, resulting in smoother curves, particularly visible on coarse meshes. The method is also capable of changing the number of segments, by enabling splitting and merging of boundary curves during the process. Finally, by changing the propagation rules, it is possible to segment the mesh by a variety of criteria, for instance geometric‐meaningful segmentations, texture‐based segmentations, or constriction‐based segmentations.     

Parallel Semi-Implicit Spectral Element Methods for Atmospheric General Circulation Models

Spectral elements combine the accuracy and exponential convergence of conventional spectral methods with the geometric flexibility of finite elements. Additionally, there are several apparent computational advantages to using spectral element methods on microprocessors. In particular, the computations are naturally cache-blocked and derivatives may be computed using nearest neighbor communications. Thus, an explicit spectral element atmospheric model has demonstrated close to linear scaling on a variety of distributed memory computers including the IBM SP and Linux Clusters. Explicit formulations of PDE's arising in geophysical fluid dynamics, such as the primitive equations on the sphere, are time-step limited by the phase speed of gravity waves. Semi-implicit time integration schemes remove the stability restriction but require the solution of an elliptic BVP. By employing a weak formulation of the governing equations, it is possible to obtain a symmetric Helmholtz operator that permits the solution of the implicit problem using conjugate gradients. We find that a block-Jacobi preconditioned conjugate gradient solver accelerates the simulation rate of the semi-implicit relative to the explicit formulation for practical climate resolutions by about a factor of three.     

一种矩形网格自动剖分及加密算法

利用差分算子分列式进行高效预处理,需要对目标域进行矩形网格剖分。而常用的有限元网格自动生成器难以满足需要。文章吸取了逐点比较法的思想,设计了一种新的算法,可以实现矩形网格的均匀和非均匀剖分以及网格的自动加密,并大大简化剖分时的运算量和需要记录的数据量。     

一种网格融合算法

快速建模是三维游戏动画领域的重要技术,从已有模型经过修改、编辑、融合构建出新的模型是一种高效的建模方法.本文提出了一种网格模型融合算法,该算法首先将需要的部分网格从源模型上交互剪切下来,并将其配准对齐;然后将两网格模型转化成点模型表示,并将点模型转化成RBF隐函数表示;再对两隐函数进行布尔运算;最后将布尔运算生的隐函数曲面在两网格接合区域进行三角形化,得到最终的网格模型.算法定义了隐函数曲面的影响区域,有效控制融合过渡.采用边界扩展的三角形化方法,保留了融合区域以外源模型的特征.实验结果表明,本文算法具有很好的网格融合结果,可用于游戏动画中快速造型.     

A Flexible Kernel for Adaptive Mesh Refinement on GPU

We present a flexible GPU kernel for adaptive on‐the‐fly refinement of meshes with arbitrary topology. By simply reserving a small amount of GPU memory to store a set of adaptive refinement patterns, on‐the‐fly refinement is performed by the GPU, without any preprocessing nor additional topology data structure. The level of adaptive refinement can be controlled by specifying a per‐vertex depth‐tag, in addition to usual position, normal, color and texture coordinates. This depth‐tag is used by the kernel to instanciate the correct refinement pattern, which will map a refined connectivity on the input coarse polygon. Finally, the refined patch produced for each triangle can be displaced by the vertex shader, using any kind of geometric refinement, such as Bezier patch smoothing, scalar valued displacement, procedural geometry synthesis or subdivision surfaces. This refinement engine does neither require multipass rendering nor any use of fragment processing nor special preprocess of the input mesh structure. It can be implemented on any GPU with vertex shading capabilities.     

Hierarchical Partitioning Techniques for Structured Adaptive Mesh Refinement Applications

This paper presents the design and preliminary evaluation of hierarchical partitioning and load-balancing techniques for distributed structured adaptive mesh refinement (SAMR) applications. The overall goal of these techniques is to enable the load distribution to reflect the state of the adaptive grid hierarchy and exploit it to reduce synchronization requirements, improve load-balance, and enable concurrent communications and incremental redistribution. The hierarchical partitioning algorithm (HPA) partitions the computational domain into subdomains and assigns them to hierarchical processor groups. Two variants of HPA are presented in this paper. The static hierarchical partitioning algorithm (SHPA) assigns portions of overall load to processor groups. In SHPA, the group size and the number of processors in each group is setup during initialization and remains unchanged during application execution. It is experimentally shown that SHPA reduces communication costs as compared to the Non-HPA scheme, and reduces overall application execution time by up to 59%. The adaptive hierarchical partitioning algorithm (AHPA) dynamically partitions the processor pool into hierarchical groups that match the structure of the adaptive grid hierarchy. Initial evaluations of AHPA show that it can reduce communication costs by up to 70%.     

海量断层网格数据的并行简化

利用Marching Cube算法重建的网格数据通常存在三角面片数量庞大的特点,必须对其进行一定程度的简化才能够方便地使用。对于海量断层网格数据可以将其分成连续的若干段,然后将各段在不同的计算节点上进行简化操作以达到并行的效果,但是这样会丢失各段连接处的拓扑信息,因而不利于后续的网格操作。采取了一种新的网格数据存储格式,并基于此提出了相应的合并算法。结果表明该算法能够很好地保持各段之间的拓扑关系,从而实现了断层网格数据的分布式并行简化。     

面向JAUMIN的并行AFT四面体网格生成

非结构网格应用软件编程框架JAUMIN(J adaptive unstructured mesh applications infrastructure)支撑了多个千万亿次并行应用软件的快速研发,并已成功应用于重大科学装置结构力学分析与优化设计、裂变能源等领域,在这些应用中,网格生成是重要步骤,为了精确刻画物理现象对应的复杂几何区域,需快速生成高质量和高精度网格。提出了一种无缝对接JAUMIN的AFT(advancing front technique)四面体网格生成并行方法,它支撑基于JAUMIN研发的应用软件进行大规模四面体网格生成,其主要特点是:(1)首先生成几何自适应的粗网格,然后基于粗网格进行分区,再通过子区域的AFT方法保证分区交界处网格的一致性;(2)在并行流程中进行表面网格贴体加密,使网格越细化越贴近真实几何形状;(3)并行流程中插入对分区交界处网格的优化步骤,进一步提高网格质量。该方法能针对实际工程应用模型快速生成数亿规模的四面体网格,可扩展性良好。     

网格模型的局部编辑算法

提出一种新的网格模型局部编辑算法,该算法可以精确地控制变形区域的大小、边界和变形点的位移,克服了FFD及其改进算法的缺点．首先交互地定义一个附着在模型表面的控制网格;然后建立模型变形区域与控制网格间点的映射,再依据变形要求来编辑控制网格;最后根据映射关系反算出模型变形区域点的新位置．控制网格可以是参数曲面的控制网格,也可采用一般三角网格或预先定义的网格模板．为达到精确变形的目的,对模型与控制网格重叠的区域进行自适应细分．该算法计算简便、易于实现,并能达到很好的效果．     

Adaptive Mesh Refinement for conservative systems: multi-dimensional efficiency evaluation

Obtainable computational efficiency is evaluated when using an Adaptive Mesh Refinement (AMR) strategy in time accurate simulations governed by sets of conservation laws. For a variety of 1D, 2D, and 3D hydro- and magnetohydrodynamic simulations, AMR is used in combination with several shock-capturing, conservative discretization schemes. Solution accuracy and execution times are compared with static grid simulations at the corresponding high resolution and time spent on AMR overhead is reported. Our examples reach corresponding efficiencies of 5 to 20 in multi-dimensional calculations and only 1.5-8% overhead is observed. For AMR calculations of multi-dimensional magnetohydrodynamic problems, several strategies for controlling the constraint are examined. Three source term approaches suitable for cell-centered representations are shown to be effective. For 2D and 3D calculations where a transition to a more globally turbulent state takes place, it is advocated to use an approximate Riemann solver based discretization at the highest allowed level(s), in combination with the robust Total Variation Diminishing Lax-Friedrichs method on the coarser levels. This level-dependent use of the spatial discretization acts as a computationally efficient, hybrid scheme.     

Parallel Algorithm Oriented Mesh Database

In this paper, we present a new point of view for efficiently managing general parallel mesh representations. Taking as a slarting point the Algorithm Oriented Mesh Database (AOMD) of [1] we extend the concepts to a parallel mesh representation. The important aspects of parallel adaptivity and dynamic load balancing are discussed. We finally show how AOMD can be effectively interfaced with mesh adaptive partial differential equation solvers. Results of the calculation of an elasticity problem and of a transient fluid dynamics problem involving thousands of mesh refinements, and load balancings are finally presented. ID="A1" Correspondence and offprint requests to: J. Remacle, Scientific Computation Research Center, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY 12180, USA. E-mail: remacle@scorec.rpi.edu     

Progressive Lossless Mesh Compression Via Incremental Parametric Refinement

In this paper, we propose a novel progressive lossless mesh compression algorithm based on Incremental Parametric Refinement, where the connectivity is uncontrolled in a first step, yielding visually pleasing meshes at each resolution level while saving connectivity information compared to previous approaches. The algorithm starts with a coarse version of the original mesh, which is further refined by means of a novel refinement scheme. The mesh refinement is driven by a geometric criterion, in spirit with surface reconstruction algorithms, aiming at generating uniform meshes. The vertices coordinates are also quantized and transmitted in a progressive way, following a geometric criterion, efficiently allocating the bit budget. With this assumption, the generated intermediate meshes tend to exhibit a uniform sampling. The potential discrepancy between the resulting connectivity and the original one is corrected at the end of the algorithm. We provide a proof-of-concept implementation, yielding very competitive results compared to previous works in terms of rate/distortion trade-off.     

A Refinement Calculus for Shared-Variable Parallel and Distributed Programming

Parallel computers have not yet had the expected impact on mainstream computing. Parallelism adds a level of complexity to the programming task that makes it very error-prone. Moreover, a large variety of very different parallel architectures exists. Porting an implementation from one machine to another may require substantial changes. This paper addresses some of these problems by developing a formal basis for the design of parallel programs in the form of a refinement calculus. The calculus allows the stepwise formal derivation of an abstract, low-level implementation from a trusted, high-level specification. The calculus thus helps structuring and documenting the development process. Portability is increased, because the introduction of a machine-dependent feature can be located in the refinement tree. Development efforts above this point in the tree are independent of that feature and are thus reusable. Moreover, the discovery of new, possibly more efficient solutions is facilitated. Last but not least, programs are correct by construction, which obviates the need for difficult debugging. Our programming/specification notation supports fair parallelism, shared-variable and message-passing concurrency, local variables and channels. The calculus rests on a compositional trace semantics that treats shared-variable and message-passing concurrency uniformly. The refinement relation combines a context-sensitive notion of trace inclusion and assumption-commitment reasoning to achieve compositionality. The calculus straddles both concurrency paradigms, that is, a shared-variable program can be refined into a distributed, message-passing program and vice versa. Received July 2001 / Accepted in revised form May 2002     

Complexity and Modeling Aspects of Mesh Refinement into Quadrilaterals

We investigate the following mesh refinement problem: Given a mesh of polygons in three-dimensional space, find a decomposition into strictly convex quadrilaterals such that the resulting mesh is conforming and satisfies prescribed local density constraints. The conformal mesh refinement problem is shown to be feasible if and only if a certain system of linear equations over GF(2) has a solution. To improve mesh quality with respect to optimization criteria such as density, angles, and regularity, we introduce a reduction to a minimum cost bidirected flow problem. However, this model is only applicable if the mesh does not contain branching edges, that is, edges incident to more than two polygons. The general case with branchings, however, turns out to be strongly -hard. To enhance the mesh quality for meshes with branchings, we introduce a two-stage approach which first decomposes the whole mesh into components without branchings, and then uses minimum cost bidirected flows on the components in a second phase. Received March 10, 1997; revised August 15, 1997.     

一种任意网格模型的选择细化算法

以基于最大误差L∞控制的网格简化算法为基础,通过删除边操作对网格模型进行向下采样,同时建立各删除操作的依赖关系．在进行网格选择细化时,将细化操作分解为对网格模型的几何修改信息和各细化操作之间的关系信息,确保了网格模型选择细化结果的正确性．实验结果证明了文中算法的有效性．     

三维网格模型的边界性度量方法

在三维网格分割中,如何实现网格模型边界的自动准确分割是目前亟待解决的问题。为给自动分割提供理论依据,提出了一种新的三维网格模型表面边界性计算方法,将少量手工标注的边界点视为能量的放射源,根据能量流动原理,自动计算出其他点作为分割边界的可能性。实验表明,该方法是行之有效的,可以依据手工标注的少量边界点找到更多的真实边界点,进而为最终实现网格模型的自动分割提供可行的理论基础。     

三角网格模型的各向异性孔洞修补算法

提出一种用于三角网格模型的各向异性孔洞修补算法.该算法避免了高代价的孔洞多边形最优三角化求解过程,只需对其进行一般三角化;而后通过很少次数的迭代过程对孔洞三角化后的网格进行细化和几何形态的调整,使其和周边网格自然过渡.实验结果证明,该算法高效、稳定,能够处理各种类型的孔洞.     

三维限定Voronoi网格剖分细化算法

针对分段线性复合形约束条件下的三维限定Voronoi剖分问题,提出一种细化算法.首先证明了分段线性复合形中的元素在最终生成的三维限定Voronoi网格中可表示为Power图结构;受此启发,提出了对限定线段平面片分别进行一维二维Power图细化以实现三维限定Voronoi 网格生成的细化算法,并且证明了该算法对于任意分段线性复合形收敛.最后通过实例验证了文中算法的有效性.