Hardware-assisted feature analysis and visualization of procedurally encoded multifield volumetric data

We take a new approach to interactive visualization and feature detection of large scalar, vector, and multifield computational fluid dynamics data sets that is also well suited for meshless CFD methods. Radial basis functions (RBFs) are used to procedurally encode both scattered and irregular gridded scalar data sets. The RBF encoding creates a complete, unified, functional representation of the scalar field throughout 3D space, independent of the underlying data topology, and eliminates the need for the original data grid during visualization. The capability of commodity PC graphics hardware to accelerate the reconstruction and rendering and to perform feature detection from this functional representation is a powerful tool for visualizing procedurally encoded volumes. Our RBF encoding and GPU-accelerated reconstruction, feature detection, and visualization tool provides a flexible system for visually exploring and analyzing large, structured, scattered, and unstructured scalar, vector, and multifield data sets at interactive rates on desktop PCs.     

A near optimal isosurface extraction algorithm using the span space

Presents the “Near Optimal IsoSurface Extraction” (NOISE) algorithm for rapidly extracting isosurfaces from structured and unstructured grids. Using the span space, a new representation of the underlying domain, we develop an isosurface extraction algorithm with a worst case complexity of o(√n+k) for the search phase, where n is the size of the data set and k is the number of cells intersected by the isosurface. The memory requirement is kept at O(n) while the preprocessing step is O(n log n). We utilize the span space representation as a tool for comparing isosurface extraction methods on structured and unstructured grids. We also present a fast triangulation scheme for generating and displaying unstructured tetrahedral grids     

三维空间非结构网格生成方法研究

随着计算流体力学领域待解决问题复杂程度的不断提高,传统的统一贴体结构网格已不能很好地满足针对复杂外形的高精度网格生成需求,而非结构网格以其独特优势受到CFD工作者的普遍关注。带有附面层的非结构网格是非结构网格生成的难点。进行了非结构四面体网格的生成方法研究,同时结合Spider软件平台中结构网格参数化附面层推进的技术优势,进行了基于Spider软件平台中非结构网格生成模块“UGCS”的开发。通过分析大量网格生成实例中网格质量和数值计算结果,验证了算法的可靠性与鲁棒性。     

Evenly Spaced Streamlines for Surfaces: An Image-Based Approach

We introduce a novel, automatic streamline seeding algorithm for vector fields defined on surfaces in 3D space. The algorithm generates evenly spaced streamlines fast, simply and efficiently for any general surface-based vector field. It is general because it handles large, complex, unstructured, adaptive resolution grids with holes and discontinuities, does not require a parametrization, and can generate both sparse and dense representations of the flow. It is efficient because streamlines are only integrated for visible portions of the surface. It is simple because the image-based approach removes the need to perform streamline tracing on a triangular mesh, a process which is complicated at best. And it is fast because it makes effective, balanced use of both the CPU and the GPU. The key to the algorithm's speed, simplicity and efficiency is its image-based seeding strategy. We demonstrate our algorithm on complex, real-world simulation data sets from computational fluid dynamics and compare it with object-space streamline visualizations.     

Mesh-driven vector field clustering and visualization: an image-based approach

Vector field visualization techniques have evolved very rapidly over the last two decades, however, visualizing vector fields on complex boundary surfaces from computational flow dynamics (CFD) still remains a challenging task. In part, this is due to the large, unstructured, adaptive resolution characteristics of the meshes used in the modeling and simulation process. Out of the wide variety of existing flow field visualization techniques, vector field clustering algorithms offer the advantage of capturing a detailed picture of important areas of the domain while presenting a simplified view of areas of less importance. This paper presents a novel, robust, automatic vector field clustering algorithm that produces intuitive and insightful images of vector fields on large, unstructured, adaptive resolution boundary meshes from CFD. Our bottom-up, hierarchical approach is the first to combine the properties of the underlying vector field and mesh into a unified error-driven representation. The motivation behind the approach is the fact that CFD engineers may increase the resolution of model meshes according to importance. The algorithm has several advantages. Clusters are generated automatically, no surface parameterization is required, and large meshes are processed efficiently. The most suggestive and important information contained in the meshes and vector fields is preserved while less important areas are simplified in the visualization. Users can interactively control the level of detail by adjusting a range of clustering distance measure parameters. We describe two data structures to accelerate the clustering process. We also introduce novel visualizations of clusters inspired by statistical methods. We apply our method to a series of synthetic and complex, real-world CFD meshes to demonstrate the clustering algorithm results.     

Towards an efficient storage and retrieval mechanism for large unstructured grids

The size of spatial scientific datasets is steadily increasing due to improvements in instruments and availability of computational resources. However, much of the research on efficient storage and access to spatial datasets has focused on large multidimensional arrays. In contrast, unstructured grids consisting of collections of simplices (e.g. triangles or tetrahedra) present special challenges that have received less attention. Data values found at the vertices of the simplices may be dispersed throughout a datafile, producing especially poor disk locality.Our previous work has focused on addressing this locality problem. In this paper, we reorganize the unstructured grid to improve locality of disk access by maintaining the spatial neighborhood relationships inherent in the unstructured grid. This reorganization produces significant gains in performance by reducing the number of accesses made to the data file. We also examine the effects of different chunking configurations on data retrieval performance. A major motivation for reorganizing the unstructured grid is to allow the application of iteration aware prefetching. Applying this prefetching method to unstructured grids produces further performance gains over and above the gains seen from reorganization alone.The work presented in this journal contains at least 40% new material not included in our conference paper (Akande and Rhodes 2013).     

三维矢量场的流动拓扑结构抽取

提出一种基于关键点分类的三维矢量场流动拓扑结构抽取算法,可应用于三维曲线网格、结构化网格和分块网格中.在许多计算流体力学计算中,存在非滑移边界,这种边界上流体的速度为0.通过分析流场边界的表面摩擦场的拓扑,展示绕壁面流体的流动结构;使用图标定位关键点,可交互式地标记和显示涡核区域,并通过选择暗示螺旋流动的图标,沿着该关键点的实特征值对应的特征矢量方向积分流线来完成.测试结果清晰地展示了关键特征区域的流体流动特征.     

A coherent grid traversal approach to visualizing particle-based simulation data

We present an approach to visualizing particle-based simulation data using interactive ray tracing and describe an algorithmic enhancement that exploits the properties of these data sets to provide highly interactive performance and reduced storage requirements. This algorithm for fast packet-based ray tracing of multilevel grids enables the interactive visualization of large time-varying data sets with millions of particles and incorporates advanced features like soft shadows. We compare the performance of our approach with two recent particle visualization systems: one based on an optimized single ray grid traversal algorithm and the other on programmable graphics hardware. This comparison demonstrates that the new algorithm offers an attractive alternative for interactive particle visualization.     

Generation algorithm of grid model for complex terrain based on geodetic coordinate data transformation

Grid model construction is one of the preconditions for computational fluid dynamics (CFD) simulation. As many environmental accidents or unfavorable incidents occur in complex real terrain circumstances, corresponding grid model generation algorithm for scenario simulation has become a hot research field. The digital elevation model (DEM) is common for three-dimensional terrain modeling. DEM data usually consist of a certain number of geodetic coordinates, however, CFD preprocessing platform can't identify geodetic coordinates directly. In this paper, firstly an algorithm of coordinate transformation was proposed, which could convert geodetic coordinates to Cartesian coordinates in the form of length (x), width (y) and height (z). Secondly, another algorithm that generates a complex real terrain grid model was recommended based on the algorithm mentioned previously, which could import converted terrain data into a gridding platform for constructing the CFD terrain grid model. Experiments’ results showed that the terrain grid algorithm obtained through the combination of the two algorithms is highly geometrically consistent with real terrain. The algorithm provided by this study could give a more reliable and convenient basis for the application of CFD fine simulation in real complex terrain.     

Fast, memory-efficient cell location in unstructured grids for visualization

Applying certain visualization techniques to datasets described on unstructured grids requires the interpolation of variables of interest at arbitrary locations within the dataset's domain of definition. Typical solutions to the problem of finding the grid element enclosing a given interpolation point make use of a variety of spatial subdivision schemes. However, existing solutions are memory- intensive, do not scale well to large grids, or do not work reliably on grids describing complex geometries. In this paper, we propose a data structure and associated construction algorithm for fast cell location in unstructured grids, and apply it to the interpolation problem. Based on the concept of bounding interval hierarchies, the proposed approach is memory-efficient, fast and numerically robust. We examine the performance characteristics of the proposed approach and compare it to existing approaches using a number of benchmark problems related to vector field visualization. Furthermore, we demonstrate that our approach can successfully accommodate large datasets, and discuss application to visualization on both CPUs and GPUs.     

基于笛卡尔切割单元法的复杂河道地理信息系统环评可视化

复杂河道中污染物扩散计算及其在地理信息系统(GIS)上的可视化,对于地表水环境影响评价(EIA)具有非常重要的意义,但在网格生成、污染物计算模型及计算结果可视化方面存在着诸多困难。针对点源岸边排放河流污染物计算及基于GIS可视化中的难点问题,提出了基于切割单元法的地面水环境影响评价可视化方法。将切割单元法应用于网格剖分,通过切割单元交点追踪算法及河道轮廓线内背景网格筛取算法,生成了复杂河道笛卡尔网格。提出了基于污染物二维稳态衰减模式的网格自适应加密与稀疏算法,在非结构化笛卡尔网格基础上采用了基于河流几何信息判断的点源岸边排放河流污染预测算法与区域填充算法,实现了环境影响评价计算结果的可视化显示。通过一个河流污染环境影响评价可视化的实例,验证了所提方法的可行性与有效性。     

WaveLines: towards effective visualization and analysis of stability in power grid simulation

Closely related to the safety and stability of power grids, stability analysis has long been a core topic in the electric industry. Conventional approaches employ computational simulation to make the quantitative judgement of the grid stability under distinctive conditions. The lack of in-depth data analysis tools has led to the difficulty in analytical tasks such as situation-aware analysis, instability reasoning and pattern recognition. To facilitate visual exploration and reasoning on the simulation data, we introduce WaveLines, a visual analysis approach which supports the supervisory control of multivariate simulation time series of power grids. We design and implement an interactive system that supports a set of analytical tasks proposed by domain experts and experienced operators. Experiments have been conducted with domain experts to illustrate the usability and effectiveness of WaveLines.     

Interactive cloud rendering using temporally coherent photon mapping

This work presents a novel interactive algorithm for simulation of light transport in clouds. Exploiting the high temporal coherence of the typical illumination and morphology of clouds we build on volumetric photon mapping, which we modify to allow for interactive rendering speeds—instead of building a fresh irregular photon map for every scene state change we accumulate photon contributions in a regular grid structure. This is then continuously being refreshed by re-shooting only a fraction of the total amount of photons in each frame. To maintain its temporal coherence and low variance, a low-resolution grid is initially used, and is then upsampled to the density field resolution on a physical basis in each frame. We also present a technique to store and reconstruct the angular illumination information by exploiting properties of the standard Henyey–Greenstein function, namely its ability to express anisotropic angular distributions with a single dominating direction. The presented method is physically plausible, conceptually simple and comparatively easy to implement. Moreover, it operates only above the cloud density field, thus not requiring any precomputation, and handles all light sources typical for the given environment, i.e., where one of the light sources dominates.     

ParTransgrid: A scalable parallel preprocessing tool for unstructured-grid cell-centered computational fluid dynamics applications

The development of a basic scalable preprocessing tool is the key routine to accelerate the entire computational fluid dynamics (CFD) workflow toward the exascale computing era. In this work, a parallel preprocessing tool, called ParTransgrid, is developed to translate the general grid format like CFD General Notation System into an efficient distributed mesh data format for large-scale parallel computing. Through ParTransgrid, a flexible face-based parallel unstructured mesh data structure designed in Hierarchical Data Format can be obtained to support various cell-centered unstructured CFD solvers. The whole parallel preprocessing operations include parallel grid I/O, parallel mesh partition, and parallel mesh migration, which are linked together to resolve the run-time and memory consumption bottlenecks for increasingly large grid size problems. An inverted index search strategy combined with a multi-master-slave communication paradigm is proposed to improve the pairwise face matching efficiency and reduce the communication overhead when constructing the distributed sparse graph in the phase of parallel mesh partition. And we present a simplified owner update rule to fast the procedure of raw partition boundaries migration and the building of shared faces/nodes communication mapping list between new sub-meshes with an order of magnitude of speed-up. Experiment results reveal that ParTransgrid can be easily scaled to billion-level grid CFD applications, the preparation time for parallel computing with hundreds of thousands of cores is reduced to a few minutes.     

基于网格耦合的数据流异常检测

基于网格的数据分析方法以网格为单位处理数据,避免了数据对象点对点的计算,极大提高了数据分析的效率。但是,传统基于网格的方法在数据分析过程中独立处理网格,忽略了网格之间的耦合关系,影响了分析的精确度。在应用网格检测数据流异常的过程中不再独立处理网格,而是考虑了网格之间的耦合关系,提出了一种基于网格耦合的数据流异常检测算法GCStream-OD。该算法通过网格耦合精确地表达了数据流对象之间的相关性,并通过剪枝策略提高算法的效率。在5个真实数据集上的实验结果表明,GCStream-OD算法具有较高的异常检测质量和效率。     

A unifying grid approach for solving potential flows applicable to structured and unstructured grid configurations

In this study, an efficient numerical method is proposed for unifying the structured and unstructured grid approaches for solving the potential flows. The new method, named as the “alternating cell directions implicit - ACDI”, solves for the structured and unstructured grid configurations equally well. The new method in effect applies a line implicit method similar to the Line Gauss Seidel scheme for complex unstructured grids including mixed type quadrilateral and triangle cells. To this end, designated alternating directions are taken along chains of contiguous cells, i.e. ‘cell directions’, and an ADI-like sweeping is made to update these cells using a Line Gauss Seidel like scheme. The algorithm makes sure that the entire flow field is updated by traversing each cell twice at each time step for unstructured quadrilateral grids that may contain triangular cells. In this study, a cell-centered finite volume formulation of the ACDI method is demonstrated. The solutions are obtained for incompressible potential flows around a circular cylinder and a forward step. The results are compared with the analytical solutions and numerical solutions using the implicit ADI and the explicit Runge-Kutta methods on single-and multi-block structured and unstructured grids. The results demonstrate that the present ACDI method is unconditionally stable, easy to use and has the same computational performance in terms of convergence, accuracy and run times for both the structured and unstructured grids.     

Semi-Unstructured Grids

We present a novel automatic grid generator for the finite element discretization of partial differential equations in 3D. The grids constructed by this grid generator are composed of a pure tensor product grid in the interior of the domain and an unstructured grid which is only contained in boundary cells. The unstructured component consists of tetrahedra, each of which satisfies a maximal interior angle condition. By suitable constructing the boundary cells, the number of types of boundary subcells is reduced to 12 types. Since this grid generator constructs large structured grids in the interior and small unstructured grids near the boundary, the resulting semi-unstructured grids have similar properties as structured tensor product grids. Some appealing properties of this method are computational efficiency and natural construction of coarse grids for multilevel algorithms. Numerical results and an analysis of the discretization error are presented. Received July 17, 2000; revised October 27, 2000     

A distributed resource discovery algorithm for P2P grids

Centralized or hierarchical administration of the classical grid resource discovery approaches is unable to efficiently manage the highly dynamic large-scale grid environments. Peer-to-peer (P2P) overlay represents a dynamic, scalable, and decentralized prospect of the grids. Structured P2P methods do not fully support the multi-attribute range queries and unstructured P2P resource discovery methods suffer from the network-wide broadcast storm problem. In this paper, a decentralized learning automata-based resource discovery algorithm is proposed for large-scale P2P grids. The proposed method supports the multi-attribute range queries and forwards the resource queries through the shortest path ending at the grid peers more likely having the requested resource. Several simulation experiments are conducted to show the efficiency of the proposed algorithm. Numerical results reveal the superiority of the proposed model over the other methods in terms of the average hop count, average hit ratio, and control message overhead.     

JADLib-科学计算数据高层I/O软件库

JADLib是为满足大规模复杂结构数据的存储与共享需求而研制的科学数据I/O软件库。其目标是设计并实现管理科学计算网格数据的数据存储模型,支持多种复杂结构数据的表示与操作,应用程序接口直观、易掌握,文件格式统一、可直接可视化,提供并行I/O、数居子集访问、压缩存储等高性能存储机制,支持多类科学计算程序跨平台使用,目前已应用到惯性约束聚变、高功率微波、计算流体力学、材料科学等多个研究领域中。实际应用表明,JADLib对于解决数值模拟软件数据存储及后处理分析所面临的I/O效率与组织管理问题具有很好的应用效果。     

Raycasting of Nonregularly Structured Volume Data

Raycasting is an efficient, but computation-intensive technique for the direct rendering of volumetric data. Nonregularly structured volume data is produced in a variety of applications, such as numerical simulation, ultrasonic inspection, or seismic measurement. Unfortunately, in raycasting nonregulary structured grids, sampling data along the rays is even more computation-intensive. One idea might be to resample the data onto a regular grid for further processing. It is shown, that resampling typical grids results either in extreme sub- sampling of the most interesting areas or in data sets too huge to handle. Additionally, no better hardware will overcome the fact that all topology and context information is lost through resampling. Therefore, dedicated algorithms for the raycasting of nonregularly structured volumes are required. We present a new approach for this task, which is based on sending rays through the computational space of a nonregular grid, instead of conventionally raycasting the physical space. This technique overcomes the difficulties in sampling data along the rays, since the computational space is regular by definition. The paper outlines the mathematical operations of this technique as well as its embedding in a rendering algorithm. We have implemented the new raycasting strategy as a module of our interactive visualization system, providing the users with an additional tool for the efficient exploration of their data.