一种新的多分辨率模型表示方法

提出了一种简洁高效的多分辨率模型表示方法MRM,该方法能对网格简化或精化过程进行编码,并在此基础上实现了一个多分辨率造型与编辑系统。该系统能为给定的模型生成多分辨率表示,并支持对模型的分辨率进行编辑,统一地完成有选择地精化和简化操作。     

PaGrid: A Mesh Partitioner for Computational Grids

Computational Grids are emerging as a new infrastructure for high performance computing. Since the resources in a Grid can be heterogeneous and distributed, mesh-based applications require a mesh partitioner that considers both processor and network heterogeneity. We have developed a heterogeneous mesh partitioner, called PaGrid. PaGrid uses a multilevel graph partitioning approach, augmented by execution time load balancing in the final uncoarsening phase. We show that minimization of total communication cost (e.g., as used by JOSTLE) can lead to significant load being placed on processors connected by slow links, which results in higher application execution times. Therefore, PaGrid balances the estimated execution time of the application across processors. PaGrid performance is compared with two existing mesh partitioners, METIS 4.0 and JOSTLE 3.0, for mapping several application meshes to two models of heterogeneous computational Grids. PaGrid is found to produce significantly better partitions than JOSTLE and slightly better partitions than METIS in most cases, in terms of estimated application execution time averaged over a large number of runs with different random number seeds.     

Selective refinement queries for volume visualization of unstructured tetrahedral meshes

We address the problem of the efficient visualization of large irregular volume data sets by exploiting a multiresolution model based on tetrahedral meshes. Multiresolution models, also called Level-Of-Detail (LOD) models, allow encoding the whole data set at a virtually continuous range of different resolutions. We have identified a set of queries for extracting meshes at variable resolution from a multiresolution model, based on field values, domain location, or opacity of the transfer function. Such queries allow trading off between resolution and speed in visualization. We define a new compact data structure for encoding a multiresolution tetrahedral mesh built through edge collapses to support selective refinement efficiently and show that such a structure has a storage cost from 3 to 5.5 times lower than standard data structures used for tetrahedral meshes. The data structures and variable resolution queries have been implemented together with state-of-the art visualization techniques in a system for the interactive visualization of three-dimensional scalar fields defined on tetrahedral meshes. Experimental results show that selective refinement queries can support interactive visualization of large data sets.     

Multilevel mesh simplification

The goal of a multilevel simplification method is to produce different levels of refinement of a mesh, reducing the resolution (total number of faces), while preserving the original topology and a good approximation to the original geometry. A new approach to simplification based on the evolution of surfaces under p-Laplacian flow is presented. Such an evolution provides a natural geometric clustering process where the spatial effect of the p-Laplacian allows for identifying suitable regions that need to be simplified. The concrete scheme is a multiresolution framework composed, at each simplification level, of a spatial clustering diffusion flow to determine the potential candidates for deletion, followed by an incremental decimation process to update the mesh vertex locations in order to decrease the overall resolution. Numerical results show the effectiveness of our strategy in multilevel simplification of different models with different complexities, in particular for models characterized by sharp features and flat parts.     

Conservative distributed discrete-event simulation on the Amazon EC2 cloud: An evaluation of time synchronization protocol performance and cost efficiency

Distributed execution of simulation models comes into play when memory limitations of a single computational resource prohibit their execution. In addition, the potential for parallel execution of a model on a distributed platform through the integration of multiple computational cores, can potentially reduce the execution time of a simulation. However, such gains can be voided by the overhead that time synchronization protocols for parallel and distributed simulation induce. This overhead is determined by the protocol used, the characteristics of the simulation model, as well as the architectural and performance characteristics of the hardware platform used. Recently, Infrastructure-as-a-Service offerings in the cloud computing domain have introduced flexibility in acquiring access to virtualized hardware platforms on a pay-as-you-go basis. At present, it is however unclear to what extent these offerings are suited for the distributed execution of discrete-event simulations, and how the characteristics of different resource types impact the performance of distributed simulation under different time synchronization protocols. Likewise, it is unclear which type of resources are most cost-efficient for this type of workload. To our knowledge, this paper is the first to investigate these aspects through an assessment of the performance and cost efficiency of different conservative time synchronization protocols on a range of cloud resource types that are currently available on Amazon EC2. Our analysis shows that performance levels comparable to those realized on commodity hardware based-clusters are attainable, and that the relative performance of different synchronization protocols is retained on high-end IaaS resources. In terms of cost-efficiency, we find that IaaS products tailored to traditional cluster workloads do not necessarily constitute the optimal choice, and we assess the impact of different packing configurations for logical processes in this regard.     

Dynamic Data Migration for Structured AMR Solvers

On cc-NUMA multi-processors, the non-uniformity of main memory latencies motivates the need for co-location of threads and data. We call this special form of data locality, geographical locality. In this article, we study the performance of a parallel PDE solver with adaptive mesh refinement (AMR). The solver is parallelized using OpenMP and the adaptive mesh refinement makes dynamic load balancing necessary. Due to the dynamically changing memory access pattern caused by the runtime adaption, it is a challenging task to achieve a high degree of geographical locality. The main conclusions of the study are: (1) that geographical locality is very important for the performance of the solver, (2) that the performance can be improved significantly using dynamic page migration of misplaced data, (3) that a migrate-on-next-touch directive works well whereas the first-touch strategy is less advantageous for programs exhibiting a dynamically changing memory access patterns, and (4) that the overhead for such migration is low compared to the total execution time.     

A Comparative Evaluation of Metrics for Fast Mesh Simplification

Triangle mesh simplification is of great interest in a variety of knowledge domains, since it allows manipulation and visualization of large models, and it is the starting point for the design of many multiresolution representations. A crucial point in the structure of a simplification method is the definition of an appropriate metric for guiding the decimation process, with the purpose of generating low error approximations at different levels of resolution. This paper proposes two new alternative metrics for mesh simplification, with the aim of producing high‐quality results with reduced execution time and memory usage, and being simple to implement. A set of different established metrics is also described and a comparative evaluation of these metrics against the two new metrics is performed. A single implementation is used in the experiments, in order to enable the evaluation of these metrics independently from other simplification aspects. Results obtained from the simplification of a number of models, using the different metrics, are compared.     

Texture-based volume rendering of adaptive mesh refinement data

Many phenomena in nature and engineering happen simultaneously on rather diverse spatial and temporal scales. In other words, they exhibit a multi-scale character. A special numerical multilevel technique associated with a particular hierarchical data structure is adaptive mesh refinement (AMR). This scheme achieves locally very high spatial and temporal resolutions. Due to its popularity, many scientists are in need of interactive visualization tools for AMR data. In this article, we present a 3D texture-based volume-rendering algorithm for AMR data that directly utilizes the hierarchical structure. Thereby fast rendering performance is achieved even for high-resolution data sets. To avoid multiple rendering of regions that are covered by grids of different levels of resolution, we propose a space partitioning scheme to decompose the volume into axis-aligned regions of equal-sized cells. Furthermore the problems of interpolation artifacts, opacity corrections, and texture memory limitations are addressed. Published online: November 6, 2002 Correspondence to: R. K?hler     

Adaptive mesh refinement in stress-constrained topology optimization

We present a topology structural optimization framework with adaptive mesh refinement and stress-constraints. Finite element approximation and geometry representation benefit from such refinement by enabling more accurate stress field predictions and greater resolution of the optimal structural boundaries. We combine a volume fraction filter to impose a minimum design feature size, the RAMP penalization to generate “black-and-white designs” and a RAMP-like stress definition to resolve the “stress singularity problem.” Regions with stress concentrations dominate the optimized design. As such, rigorous simulations are required to accurately approximate the stress field. To achieve this goal, we invoke a threshold operation and mesh refinement during the optimization. We do so in an optimal fashion, by applying adaptive mesh refinement techniques that use error indicators to refine and coarsen the mesh as needed. In this way, we obtain more accurate simulations and greater resolution of the design domain. We present results in two dimensions to demonstrate the efficiency of our method.     

A novel dynamic load balancing scheme for parallel systems

Adaptive mesh refinement (AMR) is a type of multiscale algorithm that achieves high resolution in localized regions of dynamic, multidimensional numerical simulations. One of the key issues related to AMR is dynamic load balancing (DLB), which allows large-scale adaptive applications to run efficiently on parallel systems. In this paper, we present an efficient DLB scheme for structured AMR (SAMR) applications. This scheme interleaves a grid-splitting technique with direct grid movements (e.g., direct movement from an overloaded processor to an underloaded processor), for which the objective is to efficiently redistribute workload among all the processors so as to reduce the parallel execution time. The potential benefits of our DLB scheme are examined by incorporating our techniques into a SAMR cosmology application, the ENZO code. Experiments show that by using our scheme, the parallel execution time can be reduced by up to 57% and the quality of load balancing can be improved by a factor of six, as compared to the original DLB scheme used in ENZO.     

Mesh generation and mesh refinement procedures for the analysis of concrete shells

In this paper, a mesh generation and mesh refinement procedure for adaptive finite element (FE) analyses of real-life surface structures are proposed. For mesh generation, the advancing front method is employed. FE meshes of curved structures are generated in the respective 2D parametric space of the structure. Thereafter, the 2D mesh is mapped onto the middle surface of the structure. For mesh refinement, two different modes, namely uniform and adaptive mesh refinement, are considered. Remeshing in the context of adaptive mesh refinement is controlled by the spatial distribution of the estimated error of the FE results. Depending on this distribution, remeshing may result in a partial increase and decrease, respectively, of the element size. In contrast to adaptive mesh refinement, uniform mesh refinement is characterized by a reduction of the element size in the entire domain. The different refinement strategies are applied to ultimate load analysis of a retrofitted cooling tower. The influence of the underlying FE discretization on the numerical results is investigated.     

基于区域分解的并行动态LOD构建算法

面向大规模可视数据的高速绘制问题,提出了一种基于区域分解的并行动态LOD（level-of-detail,层次细节模型）构建算法。算法首先改进了传统的渐进网格方法,实现了基于二次误差测度网格简化算法的渐进网格方法;接着提出了一种基于模型包围盒的区域分解算法,实现了原始模型的自适应区域分解;在每个子区域上,并行地执行渐进网格方法,实现了模型的并行动态LOD构建。实验结果表明,该算法可生成高质量的LOD模型,具备理想的加速比和可扩放性;与串行算法相比,该算法有效地提高了算法的执行效率。     

An efficient block parallel AMR method for two phase interfacial flow simulations

The direct numerical simulation of two phase interfacial flows can be computationally challenging, as the strong resolution needed to follow the deformations of the interface leads to a lot of time spent solving the whole computation domain. Efficient solution of such problems requires an adaptive mesh refinement capability to concentrate computational effort where it is most needed. In this paper a parallel adaptive algorithm to solve incompressible two-phase flows with surface tension is presented: the AMR is handled with the help of the PARAMESH package. The free interface between fluids is tracked via Level Set approach; the jump conditions at the interface for pressure and velocity are imposed by the Ghost Fluid method. A multigrid preconditioned BiCG-stab solver adapted to the AMR data structure has been developed to allow high density ratio computations (up to 1:1000). Special treatment has been done at the refinement jumps to maintain the fine mesh accuracy. Computational results are compared in different test cases with analytical solutions or literature, and show very good agreement with the references. The effectiveness of PARAMESH parallelization has been quite well maintained, as shown in the strong and weak scaling tests. Speed-up capabilities of the AMR are demonstrated.     

Development of adaptive mesh refinement scheme for engine spray simulations

Spray modeling is a critical component to engine combustion and emissions simulations. Accurate spray modeling often requires a fine computational mesh for better numerical resolutions. However, computations with a fine mesh will require extensive computer time. This study developed a methodology that uses a locally refined mesh in the spray region. The fine mesh virtually moves with the liquid spray. Such adaptive mesh refinement can enable greater resolution of the liquid-gas interaction while incurring only a small increase in the total number of computational cells. The present study uses an h-refinement adaptive method. A face-based approach is used for the inter-level boundary condition. The prolongation and restriction procedure preserves conservation of properties in performing grid refinement/coarsening. The refinement criterion is based on the total mass of liquid drops and fuel vapor in each cell. The efficiency and accuracy of the present adaptive mesh refinement scheme is described in the paper. Results show that the present scheme can achieve the same level of accuracy in modeling sprays with significantly lower computational cost as compared to a uniformly fine mesh.     

Generation of Tetrahedral Meshes with Multiple Elements through Thin Sections

Finite element simulations in domains with strong gradients across thin sections typically require meshes with multiple elements through these sections to accurately capture the solution. Most of the published techniques for isotropic mesh generation are not suited for the creation of such meshes in general, arbitrarily complex, non-manifold domains. In this paper, an automatic method is described for identification of thin sections of a domain and anisotropic refinement of an initial mesh to introduce a user-requested number of elements through the thin sections. The method uses local mesh modification operations to effect the refinement and subsequent realignment of edges along the thickness direction and perpendicular to it. Results are presented for a number of general models to illustrate the capability of the mesh generator.     

On local finite element refinements in multiscale air quality modeling

Variable resolution is a highly desirable property in air quality models, especially in regional applications. Resolution can be increased in dense source regions by using finite element refinements. Here, the important principles that must be obeyed at refinement boundaries are discussed. Mass conservation is achieved by making the element basis functions continuous. Constraint relations that assure continuity for various refinement ratios are described. A second issue is to keep the refinement boundaries free of noise. Since coarse and fine elements act like different media, aliasing errors usually lead to noise waves. A non-linear filter is used to remove some of this noise. Tests are conducted with different refinement ratios to see the effect of increased resolution on accuracy. In general, refinements increase accuracy by reducing diffusion errors. The peak concentrations are overpredicted during the transition from the fine to the coarse grid. These overpredictions are smaller when the refinements are gradual.     

Approximate Shape Quality Mesh Generation

We present two techniques for simplifying the list processing required in standard iterative refinement approaches to shape quality mesh generation. The goal of these techniques is to gain simplicity of programming, efficiency in execution, and robustness of termination. ‘Shape quality’ for a mesh generation method usually means that, under suitable conditions, a mesh with all angles exceeding a prescribed tolerance is generated. The methods introduced in this paper are truncated versions of such methods. They depend on the shape improvement properties of the terminal-edge LEPP-Delaunay refinement technique; we refer to them as approximate shape quality methods. They are intended for geometry-based preconditioning of coarse initial meshes for subsequent refinement to meet data representation needs. One technique is an algorithm re-organization to avoid maintaining a global list of triangles to be refined. The re-organization uses a recursive triangle processing strategy. Truncating the recursion depth results in an approximate method. Based on this, we argue that the refinement process can be carried out using a static list of the triangles to be refined that can be identified in the initial mesh. Comparisons of approximate to full shape quality meshes are provided.     

Online task recognition and real-time adaptive assistance for computer-aided machine control

Segmentation and recognition of operator-generated motions are commonly facilitated to provide appropriate assistance during task execution in teleoperative and human-machine collaborative settings. The assistance is usually provided in a virtual fixture framework where the level of compliance can be altered online, thus improving the performance in terms of execution time and overall precision. However, the fixtures are typically inflexible, resulting in a degraded performance in cases of unexpected obstacles or incorrect fixture models. In this paper, we present a method for online task tracking and propose the use of adaptive virtual fixtures that can cope with the above problems. Here, rather than executing a predefined plan, the operator has the ability to avoid unforeseen obstacles and deviate from the model. To allow this, the probability of following a certain trajectory (subtask) is estimated and used to automatically adjusts the compliance, thus providing the online decision of how to fixture the movement.     

Time‐Domain Parallelization for Accelerating Cloth Simulation

Cloth simulations, widely used in computer animation and apparel design, can be computationally expensive for real‐time applications. Some parallelization techniques have been proposed for visual simulation of cloth using CPU or GPU clusters and often rely on parallelization using spatial domain decomposition techniques that have a large communication overhead. In this paper, we propose a novel time‐domain parallelization technique that makes use of the two‐level mesh representation to resolve the time‐dependency issue and develop a practical algorithm to smooth the state transition from the corresponding coarse to fine meshes. A load estimation and a load balancing technique used in online partitioning are also proposed to maximize the performance acceleration. Our method achieves a nearly linear performance scaling on manycore clusters and outperforms spatial‐domain parallelization on a diverse set of benchmarks.