Navigating large terrains using commodity mobile devices

We describe a hybrid client-server technique for remote adaptive streaming and rendering of large terrains in resource-limited mobile devices. The technique has been designed to achieve an interactive rendering performance on a mobile device connected to a low-bandwidth wireless network. The rendering workload is split between the client and the server. The terrain area close to the viewer is rendered in real-time by the client. The terrain located far from the viewer is portrayed as view-dependent impostors, rendered by the server on demand. A prototype has been built and an exhaustive set of experiments covering several platforms, wireless networks and a wide range of viewer velocities has been conducted. Results show that the approach is feasible, effective and robust.     

面向移动终端的分布并行化渲染

目的 随着移动互联技术和实时渲染技术的快速发展,面向移动终端的3维展示提供了远程交互式的模型渲染,但较高的渲染计算复杂度与较大的数据处理规模,影响了移动终端3维展示的渲染质量和实时性。针对以上不足,提出一种面向移动终端的分布并行化渲染方法。方法 该方法将渲染任务分布到服务端与终端,服务端采用层次细节模型控制场景复杂度,生成初次渲染图像;终端采用基于图像的渲染技术再次绘制图像,提高渲染质量,同时在渲染过程中利用CUDA(compute unified device architecture)并行计算加速渲染数据处理。结果 本方法有效提高了渲染速度,降低了数据传输量,并保证了图像质量,帧率和数据传输量优化了大约10.8%。结论 本文方法为面向移动终端的3维展示提供了很好的解决途径,在移动网络环境中,能够有效降低服务端负载压力,提高资源利用率并改善用户体验。     

移动设备上基于三维模型的线条画绘制

提出一种综合考虑移动设备客户端绘制能力和传输速度的混合型远程绘制方法.该方法采用渐进网格得到不同分辨率的细节层次模型,并利用渐进传输机制逐步传输数据,以缓解单次网络负载.服务器端可以根据网络质量状况、移动客户端的处理能力和用户交互请求来选择适宜的三维细节层次模型,提取特征轮廓线并将生成的线条集合传输给客户端进行本地风格化绘制.将该方法应用于考古数字博物馆展示中取得了良好的效果.     

Displacement patches for view-dependent rendering

In this paper we present a new approach for interactive view-dependent rendering of large polygonal data sets which relies on advanced features of modern graphics hardware. Our preprocessing algorithm starts by generating a simplified representation of the input mesh. It then builds a multiresolution hierarchy for the simplified model. For each face in the hierarchy, it generates and assigns a displacement map that resembles the original surface represented by that face. At runtime, the multiresolution hierarchy is used to select a coarse view-dependent level-of-detail representation, which is sent to the graphics hardware. The GPU then refines the coarse representation by replacing each face with a planar tile, which is elevated according to the assigned displacement map. Our results show that our implementation achieves quality images at high frame rates.     

Progressive volume rendering of large unstructured grids

We describe a new progressive technique that allows real-time rendering of extremely large tetrahedral meshes. Our approach uses a client-server architecture to incrementally stream portions of the mesh from a server to a client which refines the quality of the approximate rendering until it converges to a full quality rendering. The results of previous steps are re-used in each subsequent refinement, thus leading to an efficient rendering. Our novel approach keeps very little geometry on the client and works by refining a set of rendered images at each step. Our interactive representation of the dataset is efficient, light-weight, and high quality. We present a framework for the exploration of large datasets stored on a remote server with a thin client that is capable of rendering and managing full quality volume visualizations.     

Layered point clouds: a simple and efficient multiresolution structure for distributing and rendering gigantic point-sampled models

We recently introduced an efficient multiresolution structure for distributing and rendering very large point sampled models on consumer graphics platforms [1]. The structure is based on a hierarchy of precomputed object-space point clouds, that are combined coarse-to-fine at rendering time to locally adapt sample densities according to the projected size in the image. The progressive block based refinement nature of the rendering traversal exploits on-board caching and object based rendering APIs, hides out-of-core data access latency through speculative prefetching, and lends itself well to incorporate backface, view frustum, and occlusion culling, as well as compression and view-dependent progressive transmission. The resulting system allows rendering of complex out-of-core models at high frame rates (over 60 M rendered points/second), supports network streaming, and is fundamentally simple to implement. We demonstrate the efficiency of the approach on a number of very large models, stored on local disks or accessed through a consumer level broadband network, including a massive 234 M samples isosurface generated by a compressible turbulence simulation and a 167 M samples model of Michelangelo's St. Matthew. Many of the details of our framework were presented in a previous study. We here provide a more thorough exposition, but also significant new material, including the presentation of a higher quality bottom-up construction method and additional qualitative and quantitative results.     

Interactive, internet delivery of visualization via structured prerendered multiresolution imagery

We present a novel approach for latency-tolerant delivery of visualization and rendering results where client-side frame rate display performance is independent of source dataset size, image size, visualization technique or rendering complexity. Our approach delivers pre-rendered, multiresolution images to a remote user as they navigate through different viewpoints, visualization or rendering parameters. We employ demand-driven tiled, multiresolution image streaming and prefetching to efficiently utilize available bandwidth while providing the maximum resolution user can perceive from a given viewpoint. Since image data is the only input to our system, our approach is generally applicable to all visualization and graphics rendering applications capable of generating image files in an ordered fashion. In our implementation, a normal web server provides on-demand images to a remote custom client application, which uses client-pull to obtain and cache only those images required to fulfill the interaction needs. The main contributions of this work are: (1) an architecture for latency-tolerant, remote delivery of precomputed imagery suitable for use with any visualization or rendering application capable of producing images in an ordered fashion; (2) a performance study showing the impact of diverse network environments and different tunable system parameters on end-to-end system performance in terms of deliverable frames per second.     

Visualizing dynamic geosciences phenomena using an octree-based view-dependent LOD strategy within virtual globes

Geoscientists build dynamic models to simulate various natural phenomena for a better understanding of our planet. Interactive visualizations of these geoscience models and their outputs through virtual globes on the Internet can help the public understand the dynamic phenomena related to the Earth more intuitively. However, challenges arise when the volume of four-dimensional data (4D), 3D in space plus time, is huge for rendering. Datasets loaded from geographically distributed data servers require synchronization between ingesting and rendering data. Also the visualization capability of display clients varies significantly in such an online visualization environment; some may not have high-end graphic cards. To enhance the efficiency of visualizing dynamic volumetric data in virtual globes, this paper proposes a systematic framework, in which an octree-based multiresolution data structure is implemented to organize time series 3D geospatial data to be used in virtual globe environments. This framework includes a view-dependent continuous level of detail (LOD) strategy formulated as a synchronized part of the virtual globe rendering process. Through the octree-based data retrieval process, the LOD strategy enables the rendering of the 4D simulation at a consistent and acceptable frame rate. To demonstrate the capabilities of this framework, data of a simulated dust storm event are rendered in World Wind, an open source virtual globe. The rendering performances with and without the octree-based LOD strategy are compared. The experimental results show that using the proposed data structure and processing strategy significantly enhances the visualization performance when rendering dynamic geospatial phenomena in virtual globes.     

Efficient implementation of real-time view-dependent multiresolution meshing

In this paper, we present an efficient (topology preserving) multiresolution meshing framework for interactive level-of-detail (LOD) generation and rendering of large triangle meshes. More specifically, the presented approach, called FastMesh, provides view-dependent LOD generation and real-time mesh simplification that minimizes visual artifacts. Multiresolution triangle mesh representations are an important tool for reducing triangle mesh complexity in interactive rendering environments. Ideally, for interactive visualization, a triangle mesh is simplified to the maximal tolerated visible error and, thus, mesh simplification is view-dependent. This paper introduces an efficient hierarchical multiresolution triangulation framework based on a half-edge triangle mesh data structure and presents optimized implementations of several view-dependent or visual mesh simplification heuristics within that framework. Despite being optimized for performance, these error heuristics provide conservative error bounds. The presented framework is highly efficient both in space and time cost and needs only a fraction of the time required for rendering to perform the error calculations and dynamic mesh updates.     

Optimal node-selection algorithm for parallel download in overlay content-distribution networks

In this paper, we investigate the issue of server selection for parallel download in overlay content-distribution networks. To achieve high performance and resilience to failures, a receiver can make connections with multiple servers simultaneously and receive different portions of the data from the servers in parallel. Prior studies mostly focus on the user-centric performance objectives, such as reducing the round-trip time (RTT) or the completion time of individual download, but tend to ignore the congestion caused by the concurrent connections from different servers or the total network resource usage. The latter performance concerns are important for the service providers who operate content-distribution networks. In this paper, we present a node-selection scheme in a hypercube-like overlay network that generates the optimal server set with respect to the worst-case link stress (WLS) criterion. The algorithm allows scaling to a large system because it is very efficient and does not require network measurement or collection of topology or routing information. It has performance advantages in a number of areas, particularly against the random selection scheme. First, it minimizes the level of congestion at the bottleneck link. This is equivalent to maximizing the achievable throughput. Second, it consumes less network resources in terms of the total number of links used and the total bandwidth usage. Third, it often leads to low average round-trip time to selected servers, hence, allowing nearby nodes to exchange more data, an objective sought by many content-distribution systems.     

移动环境下缓存弱一致性的研究

在移动环境下，客户缓存为提高客户一服务器数据库系统的整体性能提供了有效途径。缓存与服务方数据的同步策略是缓存研究的重要内容。移动环境下，考虑到网络的带宽、开销和可靠性等因素，客户有可能允许缓存维护弱一致性，即允许缓存与服务方数据存在偏差。本文针对基于语义的缓存，给出客户限定偏差范围的方法，并且提出基于有效期的缓存同步算法。     

Incremental view-dependent multiresolution triangulation of terrain

A view-dependent multiresolution triangulation algorithm is presented for a real-time fly-through. The triangulation of the terrain is generated incrementally on-the-fly during the rendering time. We show that since the view changes smoothly, only a few incremental modifications are required to update the triangulation to a new view. The resulting triangles form a multiresolution Delaunay triangulation which satisfies a predetermined view-dependent error tolerance. The presented method provides a guaranteed-quality mesh since it has control over the global geometric approximation error of the multiresolution view-dependent triangulation. © 1998 John Wiley & Sons, Ltd.     

Web-based visualization of spatial objects in 3DGIS

Adaptive rendering large and complex spatial data has become an important research issue in a 3DGIS application. In order to transmit the data to the client efficiently,this paper proposes a node-layer data model to manage the 3D scene. Because the large spatial data and limited network bandwidth are the main bottlenecks of web-based 3DGIS,a client/server architecture including progressive transmission methods and multiresolution representations,together with the spatial index,are developed to improve the p...     

A case study of Web server benchmarking using parallel WAN emulation

This paper describes the use of a parallel discrete-event network emulator called the Internet Protocol Traffic and Network Emulator (IP-TNE) for Web server benchmarking. The experiments in this paper demonstrate the feasibility of high-performance wide area network (WAN) emulation using parallel discrete-event simulation (PDES) techniques on a single shared-memory multiprocessor. Our experiments with an Apache Web server achieve up to 8000 HTTP/1.1 transactions/s for static document retrieval across emulated WAN topologies with up to 4096 concurrent Web/TCP clients. The results show that WAN characteristics, including round-trip delays, packet losses, and bandwidth asymmetry, all have significant impacts on Web server performance, as do client protocol behaviors. WAN emulation using the IP-TNE enables stress testing and benchmarking of Web servers in ways that may not be possible in simple local area network (LAN) test scenarios.     

WebCompanion: a friendly client-side Web prefetching agent

Accessing remote sites of the World Wide Web is often a frustrating experience for users because of long Web page retrieval times even over relatively fast Internet connections. Users are more likely to embrace the further expansion of the role of the Web into a major infrastructure for electronic commerce and for information, application, and multimedia delivery if Web accesses can be accelerated. One technique that attempts this is prefetching. We built a client-side Java-implemented prefetching agent, WebCompanion, which employs a novel adaptive, fast, and selective online prefetching strategy based on estimated round-trip times for Web resources. This strategy efficiently hides the access latencies for slow resources while at the same time limiting the network and server overhead and local resource consumption to moderate levels. Our extensive experiments show an average access speedup of greater than 50 percent and an average network byte overhead of less than 150 percent using WebCompanion over a fast Internet connection. We measured a slight acceleration in accessing the Web through WebCompanion even in a pessimistic scenario where the user never requests a prefetched document     

Performance evaluation of client-server systems

A client-server system is a distributed system where a server station receives requests from its client stations, processes the requests and returns replies to the requesting stations. The authors consider client-server systems in which a set of workstations access a file server over a local area network. The systems are modelled by a class of stochastic Petri nets. The mean response time, the throughput and the parametric sensitivities are evaluated for a client-server system based on token ring network and a system based on CSMA/CD network. These models are different from the prevalent performance models of token ring or CSMA/CD network systems because of the message interdependencies introduced by the clients-server structure. An approximate analytic-numeric method rather than simulation is used to solve the models. The solution method and the accuracy of approximation are also discussed     

Stereoscopic view-dependent visualization of terrain height fields

Visualization of large geometric environments has always been an important problem of computer graphics. We present a framework for the stereoscopic view-dependent visualization of large scale terrain models. We use a quadtree based multiresolution representation for the terrain data. This structure is queried to obtain the view-dependent approximations of the terrain model at different levels of detail. In order not to lose depth information, which is crucial for the stereoscopic visualization, we make use of a different simplification criterion, namely, distance-based angular error threshold. We also present an algorithm for the construction of stereo pairs in order to speed up the view-dependent stereoscopic visualization. The approach we use is the simultaneous generation of the triangles for two stereo images using a single draw-list so that the view frustum culling and vertex activation is done only once for each frame. The cracking problem is solved using the dependency information stored for each vertex. We eliminate the popping artifacts that can occur while switching between different resolutions of the data using morphing. We implemented the proposed algorithms on personal computers and graphics workstations. Performance experiments show that the second eye image can be produced approximately 45 percent faster than drawing the two images separately and a smooth stereoscopic visualization can be achieved at interactive frame rates using continuous multiresolution representation of height fields     

A motion-aware approach for efficient evaluation of continuous queries on 3D object databases

With recent advances in mobile computing technologies, mobile devices can render 3D objects realistically. Users of these devices such as tourists, mixed-reality gamers, and rescue officers, often need real-time retrieval of 3D objects over wireless networks. Due to bandwidth and latency restrictions in mobile settings, efficient continuous retrieval of 3D objects is a major challenge. In this paper, we present a motion-aware approach to this problem in a client-server model. Specifically, we propose: (i) representing 3D objects in multiple resolutions through wavelets to facilitate motion-aware incremental retrieval, (ii) motion-aware buffer management schemes for both client and server, (iii) an efficient index structure for 3D objects represented by wavelets, and (iv) techniques for processing group queries exploiting group motion behavior of clients. The results of our extensive experimental study demonstrate the effectiveness of our solution.     

Performance-based path determination for interprocessorcommunication in distributed computing systems

The different types of messages used by a parallel application program executing in a distributed computing system can each have unique characteristics so that no single communication network can produce the lowest latency for all messages. For instance, short control messages may be sent with the lowest overhead on one type of network, such as Ethernet, while bulk data transfers may be better suited to a different type of network, such as Fibre Channel or HIPPI. This work investigates how to exploit multiple heterogeneous communication networks that interconnect the same set of processing nodes using a set of techniques we call performance-based path determination (PBPD). The performance-based path selection (PBPS) technique selects the best (lowest latency) network among several for each individual message to reduce the communication overhead of parallel programs. The performance-based path aggregation (PBPA) technique, on the other hand, aggregates multiple networks into a single virtual network to increase the available bandwidth. We test the PBPD techniques on a cluster of SGI multiprocessors interconnected with Ethernet, Fibre Channel, and HiPPI networks using a custom communication library built on top of the TCP/IP protocol layers. We find that PBPS can reduce communication overhead in applications compared to using either network alone, while aggregating networks into a single virtual network can reduce communication latency for bandwidth-limited applications. The performance of the PBPD techniques depends on the mix of message sizes in the application program and the relative overheads of the networks, as demonstrated in our analytical models     

Quick-VDR: out-of-core view-dependent rendering of gigantic models

We present a novel approach for interactive view-dependent rendering of massive models. Our algorithm combines view-dependent simplification, occlusion culling, and out-of-core rendering. We represent the model as a clustered hierarchy of progressive meshes (CHPM). We use the cluster hierarchy for coarse-grained selective refinement and progressive meshes for fine-grained local refinement. We present an out-of-core algorithm for computation of a CHPM that includes cluster decomposition, hierarchy generation, and simplification. We introduce novel cluster dependencies in the preprocess to generate crack-free, drastic simplifications at runtime. The clusters are used for LOD selection, occlusion culling, and out-of-core rendering. We add a frame of latency to the rendering pipeline to fetch newly visible clusters from the disk and avoid stalls. The CHPM reduces the refinement cost of view-dependent rendering by more than an order of magnitude as compared to a vertex hierarchy. We have implemented our algorithm on a desktop PC. We can render massive CAD, isosurface, and scanned models, consisting of tens or a few hundred million triangles at 15-35 frames per second with little loss in image quality.