Fast Image‐Space Silhouette Extraction for Non‐Photorealistic Landscape Rendering

Landscape illustration, a core visualization technique for field geologists and geomorphologists, employs the parsimonious use of linework to represent surface structure in a straightforward and intuitive manner. Under the rubric of non‐photorealistic rendering (NPR), automated procedures in this vein render silhouettes and creases to represent, respectively, view‐dependent and view‐independent landscape features. This article presents two algorithms and implementations for rendering silhouettes from adaptive tessellations of point‐normal (PN) triangles at speeds approaching those suitable for animation. PN triangles use cubic polynomial models to provide a surface that appears smooth at any required resolution. The first algorithm, drawing on standard silhouette detection techniques in surface meshes, builds object space facet adjacencies and image space pixel adjacencies in the graphics pipeline following adaptive tessellation. The second makes exclusive use of image space analysis without referencing the underlying scene world geometry. Other than initial pre‐processing operations, recent advances in the OpenGL API allow implementations for both algorithms to be hosted entirely on the graphics processing unit (GPU), eliminating slowdowns through data transfer across the system memory bus. We show that both algorithms provide viable paths to real‐time animation of pen and ink style landscape illustrations but that the second demonstrates superior performance over the first.     

多级存储优化的大规模全局光照快速计算

针对大规模复杂场景渲染的全局光照计算量大从而影响其渲染实时性的问题,提出了一种基于多级分辨率纹理存储结构的改进体素锥追踪全局光照算法。算法首先采用基于人眼视觉特性的多级分辨率纹理存储结构高效存储光照信息,并在直接光照计算时,结合存储结果特点,然后采用混合存储的GPU硬件加速与无贡献节点丢弃的软件加速相结合方法,进一步提高光照渲染效率,最后基于多级纹理及闭合体节点自适应合并对锥波滤器进行改进,实现全局光照的高效计算。试验结果表明,改进算法减少了光照计算量,降低了系统内存占用,并取得了与经典算法相近的场景光照渲染效果,从而验证了其在大规模光照计算的有效性。     

Out‐of‐Core GPU‐based Change Detection in Massive 3D Point Clouds

If sites, cities, and landscapes are captured at different points in time using technology such as LiDAR, large collections of 3D point clouds result. Their efficient storage, processing, analysis, and presentation constitute a challenging task because of limited computation, memory, and time resources. In this work, we present an approach to detect changes in massive 3D point clouds based on an out‐of‐core spatial data structure that is designed to store data acquired at different points in time and to efficiently attribute 3D points with distance information. Based on this data structure, we present and evaluate different processing schemes optimized for performing the calculation on the CPU and GPU. In addition, we present a point‐based rendering technique adapted for attributed 3D point clouds, to enable effective out‐of‐core real‐time visualization of the computation results. Our approach enables conclusions to be drawn about temporal changes in large highly accurate 3D geodata sets of a captured area at reasonable preprocessing and rendering times. We evaluate our approach with two data sets from different points in time for the urban area of a city, describe its characteristics, and report on applications.     

Automating Landscape Illustration with Pen and Ink Style Rendering

This paper introduces object space procedures for extracting silhouettes, slope lines, and drainage features from digital elevation models (DEMs) to direct the rendering of landform features in the style of pen-and-ink landscape illustrations. Unlike image space procedures which generally extract feature information through 2-dimensional (2D) rendered image processing techniques, object space procedures operate directly on 3-dimensional (3D) surface models. The ultimate goal of this work is to produce fully automated tools that can imitate the styles characterized by the traditional pen-and-ink techniques of Lobeck, Imhof, Raisz, and other scientific illustrators to bring the beauty of their effective and economical visual techniques to automated cartographic environments. Through the implementation of a Java 3D application programming interface (API) prototype, a testing platform was established for the application of stylistic elements to linework representing surface form lines. This paper explores the aesthetic effects of silhouette lines, creases, and slope lines on the rendering of terrain features. It also introduces the use of adaptively resampled triangulated irregular networks (TINs) as a basis for perspective rendering applications.     

A Parallel Scheme for Large‐scale Polygon Rasterization on CUDA‐enabled GPUs

This research develops a parallel scheme to adopt multiple graphics processing units (GPUs) to accelerate large‐scale polygon rasterization. Three new parallel strategies are proposed. First, a decomposition strategy considering the calculation complexity of polygons and limited GPU memory is developed to achieve balanced workloads among multiple GPUs. Second, a parallel CPU/GPU scheduling strategy is proposed to conceal the data read/write times. The CPU is engaged with data reads/writes while the GPU rasterizes the polygons in parallel. This strategy can save considerable time spent in reading and writing, further improving the parallel efficiency. Third, a strategy for utilizing the GPU's internal memory and cache is proposed to reduce the time required to access the data. The parallel boundary algebra filling (BAF) algorithm is implemented using the programming models of compute unified device architecture (CUDA), message passing interface (MPI), and open multi‐processing (OpenMP). Experimental results confirm that the implemented parallel algorithm delivers apparent acceleration when a massive dataset is addressed (50.32 GB with approximately 1.3 × 10⁸ polygons), reducing conversion time from 25.43 to 0.69 h, and obtaining a speedup ratio of 36.91. The proposed parallel strategies outperform the conventional method and can be effectively extended to a CPU‐based environment.     

Three‐dimensional terrain modeling with multiple‐source illumination

Three‐dimensional (3D) terrain modeling based on digital elevation models (DEMs) with the use of orthographic and perspective projections is a standard procedure implemented in many commercial and open‐source geoinformation systems. However, standard tools may be insufficient for 3D scientific visualization. In particular, single‐source illumination of 3D models may be deficient for topographically complex terrains. We present an approach for 3D terrain modeling with multiple‐source illumination in the virtual environment of the Blender free and open‐source software. The approach includes the following key stages: (1) automatic creation of a polygonal object; (2) selecting an algorithm to model the 3D geometry; (3) selecting a vertical exaggeration scale; (4) selecting types, parameters, a number, and positions of light sources; (5) selecting methods for generating shadows; (6) selecting a shading method for the 3D model; (7) selecting a material for the 3D model surface; (8) overlaying a texture on the 3D model; (9) setting a virtual camera; and (10) rendering the 3D model. To illustrate the approach, we processed a test DEM extracted from the International Bathymetric Chart of the Arctic Ocean version 3.0 (IBCAO 3.0). The approach is currently being used to develop a system for geomorphometric modeling of the Arctic Ocean floor.     

An efficient data organization and scheduling strategy for accelerating large vector data rendering

Rendering large volumes of vector data is computationally intensive and therefore time consuming, leading to lower efficiency and poorer interactive experience. Graphics processing units (GPUs) are powerful tools in data parallel processing but lie idle most of the time. In this study, we propose an approach to improve the performance of vector data rendering by using the parallel computing capability of many‐core GPUs. Vertex transformation, largely a mathematical calculation that does not require communication with the host storage device, is a time‐consuming procedure because all coordinates of each vector feature need to be transformed to screen vertices. Use of a GPU enables optimization of a general‐purpose mathematical calculation, enabling the procedure to be executed in parallel on a many‐core GPU and optimized effectively. This study mainly focuses on: (1) an organization and storage strategy for vector data based on equal pitch alignment, which can adapt to the GPU's calculating characteristics; (2) a paging‐coalescing transfer and memory access strategy for vector data between the CPU and the GPU; and (3) a balancing allocation strategy to take full advantage of all processing cores of the GPU. Experimental results demonstrate that the approach proposed can significantly improve the efficiency of vector data rendering.     

Asynchronous Geospatial Processing: An Event‐Driven Push‐Based Architecture for the OGC Web Processing Service

Geospatial processing tasks like solar potential analyses or floodplain investigations within flood scenarios are often complex and deal with large amounts of data. If such analysis operations are performed in distributed web‐based systems, technical capabilities are mostly not sufficient. Major shortcomings comprise the potentially long execution times and the vast amount of messaging overhead that arise from common poll‐based approaches. To overcome these issues, an approach for an event‐driven architecture for web‐based geospatial processing is proposed within this article. First, this article presents a thorough qualitative discussion of different available technologies for push‐based notifications. The aim of this discussion is to find the most suitable push‐based messaging technologies for application with OGC Web Processing Services (WPS). Based on this, an event‐driven architecture for asynchronous geospatial processing with the WPS is presented, building on the Web Socket Protocol as the transport protocol and the OGC Event Service as the message‐oriented middleware. The proposed architecture allows pushing notifications to clients once a task has completed. This paradigm enables the efficient execution of web‐based geospatial processing tasks as well as the integration of geographical analyses into event‐driven real‐time workflows.     

一种基于GPU Tessellation的地形无缝绘制算法

针对传统多分辨率地形绘制算法构网速度慢、T型裂缝不易处理等问题,提出了一种GPU（graphic processing unit）构网的地形无缝绘制算法。首先,引入实时网格细分（tessellation）技术,将地形构网分为CPU粗粒度Tile网格构建和GPU细粒度Patch网格细分两个阶段;然后,Tile网格采用基于视距的细节层次模型进行LoD层次选择,Patch采用基于屏幕空间投影误差的细节层次模型完成网格细分,兼顾了视距和地形粗糙度对地形绘制的影响,实现了地形细节层次的自适应选择;最后,应用C++语言和DirectX 11工具,设计开发了相应的可视化实验系统。实验结果表明,该方法实现了多分辨率地形的自适应无缝表达,保证了地形网格的连续性;并通过合理平衡CPU-GPU负担,显著提升了地形渲染效率。     

一种面向CPU/GPU异构环境的协同并行空间插值算法

CPU/GPU异构混合系统是一种新型高性能计算平台,但现有并行空间插值算法仅依赖CPU或GPU进行加速,迫切需要研究协同并行空间插值算法以充分利用异构计算资源,进一步提升插值效率。以薄板样条函数插值为例,提出一种CPU/GPU协同并行插值算法以加速海量激光雷达（light detector & ranger,LiDAR）点云生成数字高程模型（DEM）。通过插值任务的分解与抽象封装以屏蔽底层硬件执行模式的差异性,同时在多级协同并行框架基础上设计了Greedy-SET动态调度策略,策略顾及底层硬件能力的差异性,以实现异构并行资源的充分利用和良好负载均衡。实验表明,协同并行插值算法在高性能工作站上取得19.6倍的加速比,相比单一CPU或GPU并行算法,其效率提升分别达到54%和44%,实现了高效的协同并行处理。     

A high accuracy surface modeling method based on GPU accelerated multi‐grid method

A high accuracy surface modeling method (HASM) has been developed to provide a solution to many surface modeling problems such as DEM construction, surface estimation and spatial prediction. Although HASM is able to model surfaces with a higher accuracy, its low computing speed limits its popularity in constructing large scale surfaces. Hence, the research described in this article aims to improve the computing efficiency of HASM with a graphic processor unit (GPU) accelerated multi‐grid method (HASM‐GMG). HASM‐GMG was tested with two types of surfaces: a Gauss synthetic surface and a real‐world example. Results indicate that HASM‐GMG can gain significant speedups compared with CPU‐based HASM without acceleration on GPU. Moreover, both the accuracy and speed of HASM‐GMG are superior to the classical interpolation methods including Kriging, Spline and IDW.     

负载分配的CPU/GPU高分辨率卫星影像调制传递补偿方法

本文系统地探讨了使用CPU/GPU协同处理理论对高分辨率卫星影像进行MTF补偿的方法。首先在GPU上对方法进行了基本实现,并通过三种性能优化策略（执行配置优化、存储访问优化和指令优化）进一步提高了方法的执行效率。在Intel Xeon E5650 CPU和NVIDIA Tesla C2050 GPU组成的CPU/GPU系统中对高分一号卫星全色影像进行MTF补偿,加速比达到42.80倍。在此基础上,为充分利用CPU的计算性能,使用CPU/GPU负载分配策略将部分负载分配给CPU进行处理,使用该策略后,方法加速比达到47.82倍,相应的处理时间压缩至1.62s,可满足对高分辨率卫星影像进行近实时MTF补偿的需求。     

遥感影像正射纠正的GPU-CPU协同处理研究

提出了一种基于CUDA的遥感影像正射纠正GPU-CPU协同处理方法,以实现重采样操作的GPU细粒度并行化。根据GPU的并行结构和硬件特点,采用执行配置优化技术提高warp占有率,利用共享存储器优化减少对效率低下的全局存储器中坐标变换系数的重复访问,通过纹理存储器代替全局存储器优化对原始影像数据的访问。实验结果表明,并行算法能够充分发挥GPU的并行处理能力,利用GeForce 9500 GT显卡,对大小为6 000像素×6 000像素的全色影像进行多项式纠正对比实验,最邻近灰度内插重采样和双线性灰度内插重采样的最终加速比分别能够达到8倍和10倍以上。     

Supporting Automated Pen and Ink Style Surface Illustration with B-Spline Models

This paper introduces a methodology for constructing pen and ink style landscape illustrations using B-spline surface models. Following a brief discussion of manual methods and recent developments in automated non-photorealistic rendering (NPR) techniques, the paper discusses polynomial models for surface rendering and their implementation in the OpenGL graphics interface. It then discusses the generation of silhouettes and form lines for topographic surfaces from a set of triangulated vertices obtained from polygonal tessellations. An implementation of the methodology outlined in the paper is described and tested. The results are analyzed and suggestions for further research are presented.     

基于纹理合成的三维地形水墨风格渲染研究

提出了基于纹理合成的三维地形水墨风格渲染的方法,以规则格网DEM为数据源,基于OSG进行三维地形建模,在此基础上提取山体特征线,然后生成一幅灰度控制图像。对Efros01纹理合成算法进行改进,利用灰度控制图像指导水墨纹理的合成,将得到的纹理图像映射到三维地形上,实现对三维地形的水墨风格渲染,通过对水墨纹理样本的选择和纹理合成参数的设置能够实现对纹理合成过程的交互控制。结果表明,该渲染方法对三维地形的水墨风格渲染具有较好的效果。     

Partial polygon pruning of hydrographic features in automated generalization

This article demonstrates a working method to automatically detect and prune portions of waterbody polygons to support creation of a multi‐scale hydrographic database. Water features are sensitive to scale change, therefore multiple representations are required to maintain visual and geographic logic at smaller scales. Partial pruning of polygonal features – such as long, sinuous reservoir arms, stream channels too narrow at the target scale, and islands that begin to coalesce – entails concurrent management of the length and width of polygonal features as well as integrating pruned polygons with other generalized point and linear hydrographic features to maintain stream network connectivity. The implementation follows data representation standards developed by the US Geological Survey (USGS) for the National Hydrography Dataset (NHD). Portions of polygonal rivers, streams, and canals are automatically characterized for width, length, and connectivity. This article describes an algorithm for automatic detection and subsequent processing, and shows results for a sample of NHD subbasins in different landscape conditions in the US.     

A Triangular Form‐based Multiple Flow Algorithm to Estimate Overland Flow Distribution and Accumulation on a Digital Elevation Model

In this study, we present a newly developed method for the estimation of surface flow paths on a digital elevation model (DEM). The objective is to use a form‐based algorithm, analyzing flow over single cells by dividing them into eight triangular facets and to estimate the surface flow paths on a raster DEM. For each cell on a gridded DEM, the triangular form‐based multiple flow algorithm (TFM) was used to distribute flow to one or more of the eight neighbor cells, which determined the flow paths over the DEM. Because each of the eight facets covering a cell has a constant slope and aspect, the estimations of – for example – flow direction and divergence/convergence are more intuitive and less complicated than many traditional raster‐based solutions. Experiments were undertaken by estimating the specific catchment area (SCA) over a number of mathematical surfaces, as well as on a real‐world DEM. Comparisons were made between the derived SCA by the TFM algorithm with eight other algorithms reported in the literature. The results show that the TFM algorithm produced the closest outcomes to the theoretical values of the SCA compared with other algorithms, derived more consistent outcomes, and was less influenced by surface shapes. The real‐world DEM test shows that the TFM was capable of modeling flow distribution without noticeable ‘artefacts’, and its ability to track flow paths makes it an appropriate platform for dynamic surface flow simulation.     

Parallel algorithm for viewshed analysis on a modern GPU

Spatial analysis, including viewshed analysis, is an important aspect of the Digital Earth system. Viewshed analysis is usually performed on a large scale, so efficiency is important in any Digital Earth application making these calculations. In this paper, a real-time algorithm for viewshed analysis in 3D scenes is presented by using the parallel computing capabilities of a graphics processing unit (GPU). In contrast to traditional algorithms based on line-of-sight, this algorithm runs completely within the programmable 3D visualization pipeline to render 3D terrains with viewshed analysis. The most important difference is its integration of the viewshed calculation with the rendering module. Invisible areas are rendered as shadows in the 3D scene. The algorithm process is paralleled by rasterizer units in the graphics card and by vertex and pixel shaders executed on the GPU. We have implemented this method in our 3D Digital Earth system with the DirectX 9.0c API and tested on some consumer-level PC platforms with interactive frame-rates and high image quality. Our algorithm has been widely used in related systems based on Digital Earth.     

Integrated Spatio‐temporal Data Mining for Forest Fire Prediction

Forests play a critical role in sustaining the human environment. Most forest fires not only destroy the natural environment and ecological balance, but also seriously threaten the security of life and property. The early discovery and forecasting of forest fires are both urgent and necessary for forest fire control. This article explores the possible applications of Spatio‐temporal Data Mining for forest fire prevention. The research pays special attention to the spatio‐temporal forecasting of forest fire areas based upon historic observations. An integrated spatio‐temporal forecasting framework – ISTFF – is proposed: it uses a dynamic recurrent neural network for spatial forecasting. The principle and algorithm of ISTFF are presented, and are then illustrated by a case study of forest fire area prediction in Canada. Comparative analysis of ISTFF with other methods shows its high accuracy in short‐term prediction. The effect of spatial correlations on the prediction accuracy of spatial forecasting is also explored.     

面向WebGL的矢量数据三维绘制技术

矢量数据的叠加显示能够提高三维虚拟地球的表达效果与分析能力。受限于GPU的计算精度,在三维虚拟地球中矢量数据绘制普遍存在抖动现象和深度冲突现象。对基于WebGL的矢量数据三维绘制中计算精度问题进行了分析,提出了使用CPU RTC技术和GPU RTE技术提高顶点变换的精度,使用多视锥渲染算法和深度平面技术解决深度缓存精度问题。实验证明,这几种技术和算法可以有效缓解抖动现象和深度冲突现象导致的视觉干扰,改善了各种尺度和范围的矢量数据在三维地形上的叠加显示效果。