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     

View-dependent refinement of multiresolution meshes using programmable graphics hardware

View-dependent multiresolution rendering places a heavy load on CPU. This paper presents a new method on view-dependent refinement of multiresolution meshes by using the computation power of modern programmable graphics hardware (GPU). Two rendering passes using this method are included. During the first pass, the level of detail selection is performed in the fragment shaders. The resultant buffer from the first pass is taken as the input texture to the second rendering pass by vertex texturing, and then the node culling and triangulation can be performed in the vertex shaders. Our approach can generate adaptive meshes in real-time, and can be fully implemented on GPU. The method improves the efficiency of mesh simplification, and significantly alleviates the computing load on CPU.     

Interactive inspection of complex multi-object industrial assemblies

The use of virtual prototypes and digital models containing thousands of individual objects is commonplace in complex industrial applications like the cooperative design of huge ships. Designers are interested in selecting and editing specific sets of objects during the interactive inspection sessions. This is however not supported by standard visualization systems for huge models. In this paper we discuss in detail the concept of rendering front in multiresolution trees, their properties and the algorithms that construct the hierarchy and efficiently render it, applied to very complex CAD models, so that the model structure and the identities of objects are preserved. We also propose an algorithm for the interactive inspection of huge models which uses a rendering budget and supports selection of individual objects and sets of objects, displacement of the selected objects and real-time collision detection during these displacements. Our solution–based on the analysis of several existing view-dependent visualization schemes–uses a Hybrid Multiresolution Tree that mixes layers of exact geometry, simplified models and impostors, together with a time-critical, view-dependent algorithm and a Constrained Front. The algorithm has been successfully tested in real industrial environments; the models involved are presented and discussed in the paper.     

Displaced subdivision surfaces of animated meshes

This paper proposes a novel technique for converting a given animated mesh into a series of displaced subdivision surfaces. Instead of independently converting each mesh frame in the animated mesh, our technique produces displaced subdivision surfaces that share the same topology of the control mesh and a single displacement map. We first propose a conversion framework that enables sharing the same control mesh topology and a single displacement map among frames, and then present the details of the components in the framework. Each component is specifically designed to minimize the shape conversion errors that can be caused by enforcing a single displacement map. The resulting displaced subdivision surfaces have a compact representation, while reproducing the details of the original animated mesh. The representation can also be used for efficient rendering on modern graphics hardware that supports accelerated rendering of subdivision surfaces.     

Interactive view-dependent rendering over networks

For a client-server based view-dependent rendering system, the overhead of view-dependent rendering and the network latency are major obstacles in achieving interactivity. In this paper, we first present a multiresolution hierarchy traversal management strategy to control the overhead of view-dependent rendering for low-capacity clients. Then we propose a predictive parallel strategy to overcome the network latency for client-server based view-dependent multiresolution rendering systems. Our solution is to make the client process and the server process run in parallel, using the rendering time to cover the network latency. For networks with long round-trip times, we manage to overlap the network latency for one frame with the rendering time for multiple frames. View-parameters prediction is incorporated to make the parallelism of the client and the server feasible. In order to maintain an acceptable view-dependent rendering quality in the network environment, we develop a synchronization mechanism and a dynamic adjustment mechanism to handle the transient network slowdowns and the changes of the network condition. Our experimental results, in comparison with the sequential method, show that our predictive parallel approach can achieve an interactive frame rate while keeping an acceptable rendering quality for large triangle models over networks with relatively long round-trip times.     

Displacement modeling: Hardware-accelerated interactive feature modeling on subdivision surfaces

Feature modeling on subdivision surfaces remains a challenging task for interactive 3D design. This paper presents the idea of displacement modeling, which utilizes displacement mapping as an interactive modeling method to design fine level features by exploiting the computation power of modern programmable graphics hardware (GPU). We also propose a view-dependent adaptive subdivision method according to the error metric in view space. It can highly reduce the number of refined faces and points while maintaining the same visual quality as uniform subdivision. Furthermore, several feature adjustment tools are introduced for flexible design and manipulation of created features. Since the displacement modeling approach is fully implemented on graphics hardware, it can substantially alleviate the computing load on CPU and significantly reduce the data transmission on the graphics channel.     

Reverse engineering with subdivision surfaces

Reverse engineering is concerned with the reconstruction of surfaces from three-dimensional point clouds originating from laser-scanned objects. We present an adaptive surface reconstruction method providing a hierarchy of quadrilateral meshes adapting surface topology when a mesh is refined. This way, a user can choose a model with proper resolution and topology from the hierarchy without having to run the algorithm multiple times with different parameters. The multiresolution mesh representation can be used subsequently for view-dependent rendering and wavelet compression.     

Uniform remeshing with an adaptive domain: a new scheme for view-dependent level-of-detail rendering of meshes

We present a new algorithm for view-dependent level-of-detail rendering of meshes. Not only can it effectively resolve complex geometry features similar to edge collapse-based schemes, but it also produces meshes that modern graphics hardware can render efficiently. This is accomplished through a novel hybrid approach: for each frame, we view-dependently refine the progressive mesh (PM) representation of the original mesh and use the output as the base domain of uniform regular refinements. The algorithm exploits frame-to-frame coherence and only updates portions of the output mesh corresponding to modified domain triangles. The PM representation is built using a custom volume preservation-based error function. A simple k-d tree enhanced jump-and-walk scheme is used to quickly map from the dynamic base domain to the original mesh during regular refinements. In practice, the PM refinement provides a view-optimized base domain for later regular refinements. The regular refinements ensure almost-everywhere regularity of output meshes, allowing optimization for vertex cache coherence and caching of geometry data in high-performance graphics memory. Combined, they also have the effect of allowing our algorithm to operate on uniform clusters of triangles instead of individual ones, reducing CPU workload.     

A Coordinate-Invariant Approach to Multiresolution Motion Analysis

Multiresolution motion analysis has gained considerable research interest as a unified framework to facilitate a variety of motion editing tasks. Within this framework, motion data are represented as a collection of coefficients that form a coarse-to-fine hierarchy. The coefficients at the coarsest level describe the global pattern of a motion signal, while those at fine levels provide details at successively finer resolutions. Due to the inherent nonlinearity of the orientation space, the challenge is to generalize multiresolution representations for motion data that contain orientations as well as positions. Our goal is to develop a multiresolution analysis method that guarantees coordinate-invariance without singularity. To do so, we employ two novel ideas: hierarchical displacement mapping and motion filtering. Hierarchical displacement mapping provides an elegant formulation to describe positions and orientations in a coherent manner. Motion filtering enables us to separate motion details level-by-level to build a multiresolution representation in a coordinate-invariant way. Our representation facilitates multiresolution motion editing through level-wise coefficient manipulation that uniformly addresses issues raised by motion modification, blending, and stitching.     

GPU-optimized indirect scalar displacement mapping

Displacement mapping refers to a technique for rendering a high-frequency surface by adding geometric details encoded in a displacement map to a low-frequency base surface. This paper proposes a method for indirectly accessing the base surface using a special displacement map and then carrying out scalar displacement. Given a high-frequency triangle mesh, a coarse PN (point-normal) quad mesh is computed as the base surface. The parameters used to evaluate the base surface are precomputed such that scalar displacement from the evaluated points reaches the features of the original surface. The parameters are stored in the displacement map together with the displacement scalars. The run-time algorithm uses the hardware tessellation capability of GPU and reconstructs the high-frequency surface. Using the proposed method, surface features are accurately preserved, surface deformation is well supported, LOD control becomes quite flexible, and the base surface can be extremely simplified.     

基于GPU的视点相关自适应细分

利用GPU的强大浮点数计算能力和并行处理能力,提出一种完全基于GPU的视点相关自适应细分内核进行快速细分计算的方法.在GPU中,依次实现视点相关的面片细分深度值计算、基于基函数表的细分表面顶点求值、细分表面绘制等核心步骤,无须与CPU端系统内存进行几何数据交换.视点相关的自适应细分准则在表面绘制精度保持不变的情况下,有效地降低了细分表面的细分深度和细分的计算量,在此基础上完全基于GPU的细分框架使得曲面细分具有快速高效的特点.该方法还可以在局部重要细节用较大深度值进行实时自适应细分,以逼近极限曲面.     

A multiresolution representation for massive meshes

We present a new external memory multiresolution surface representation for massive polygonal meshes. Previous methods for building such data structures have relied on resampled surface data or employed memory intensive construction algorithms that do not scale well. Our proposed representation combines efficient access to sampled surface data with access to the original surface. The construction algorithm for the surface representation exhibits memory requirements that are insensitive to the size of the input mesh, allowing it to process meshes containing hundreds of millions of polygons. The multiresolution nature of the surface representation has allowed us to develop efficient algorithms for view-dependent rendering, approximate collision detection, and adaptive simplification of massive meshes. The empirical performance of these algorithms demonstrates that the underlying data structure is a powerful and flexible tool for operating on massive geometric data.     

Interactive GPU-based adaptive cartoon-style rendering

In this paper we present a novel real-time cartoon-style rendering approach, which targets very large meshes. Cartoon drawing usually uses a limited number of colors for shading and emphasizes special effects, such as sharp curvature and silhouettes. It also paints the remaining large regions with uniform solid colors. Our approach quantizes light intensity to generate different shadow colors and utilizes multiresolution mesh hierarchy to maintain appropriate levels of detail across various regions of the mesh. To comply with visual requirements, our algorithm exploits graphics hardware programmability to draw smooth silhouette and color boundaries within the vertex and fragment processors. We have adopted a simplification scheme that executes simplification operators without incurring extra simplification operations as a precondition. The real-time refinement of the mesh, which is performed by the graphics processing unit (GPU), dramatically improves image quality and reduces CPU load.     

Adaptive extraction of time-varying isosurfaces

We present an algorithm for adaptively extracting and rendering isosurfaces from compressed time-varying volume data sets. Tetrahedral meshes defined by longest edge bisection are used to create a multiresolution representation of the volume in the spatial domain that is adapted overtime to approximate the time-varying volume. The reextraction of the isosurface at each time step is accelerated with the vertex programming capabilities of modern graphics hardware. A data layout scheme which follows the access pattern indicated by mesh refinement is used to access the volume in a spatially and temporally coherent manner. This data layout scheme allows our algorithm to be used for out-of-core visualization.     

基于参数空间的混合多分辨率绘制

根据点和多边形在表示和绘制物体上各自不同的特点,提出了一种有效绘制细节高度复杂物体的多分辨率方法.3D表面被映射到参数平面,经规则采样成为几何图像,P-Quadtrees是基于几何图像建立的四叉树多分辨率层次结构.通过对四叉树的遍历,面向视点的表面用较大多边形面片绘制,光照细节通过法向映射完成;轮廓部分通过视点相关的LOD(level of detail)控制进行细化,使用点来绘制物体复杂精细的轮廓.通过此方法,细节复杂模型的绘制不仅可以被硬件加速,而且无论在表面还是在轮廓部分都能获得很好的视觉效果.     

Visualization of level-of-detail meshes on the GPU

Extensive research has been carried out in multiresolution models for many decades. The tendency in recent years has been to harness the potential of GPUs to perform the level-of-detail extraction on graphics hardware. The aim of this work is to present a new level-of-detail scheme based on triangles which is both simple and efficient. In this approach, the extraction process updates vertices instead of indices, thus providing a perfect framework for adapting the algorithms to work completely on GPU shaders. One of the key aspects of our proposal is the need for just a single rendering pass in order to obtain the desired geometry. Moreover, coherence among the different approximations is maximized by means of a symmetric extraction algorithm, which performs the same process when refining and coarsening the mesh. Lastly, we also introduce different uses of the scheme to offer continuous and view-dependent resolution.     

大型网格模型多分辨率的外存构建与交互绘制

结合多分辨率、网格排布和基于视点的绘制技术,提出一种外存多分辨率构建和绘制算法.采用适应性八叉树对模型的包围盒进行划分,自顶向下构建模型的多分辨率层次结构,较好地保持了原模型的细节分布;并对多分辨率结构中每个节点所包含的三角形片段进行网格排布优化,降低了缓存的平均失效率;在实时绘制时,采用基于视点的细节层次选择策略进行模型的细化;最后通过引入数据预取机制来隐藏磁盘I/O延时,进一步提高绘制性能.实验结果表明,该算法在绘制速度与细节保留上均优于同类MRMM算法.     

Capturing and rendering geometry details for BTF-mapped surfaces

Bidirectional texture functions, or BTFs, accurately model reflectance variation at a fine (meso-) scale as a function of lighting and viewing direction. BTFs also capture view-dependent visibility variation, also called masking or parallax, but only within surface contours. Mesostructure detail is neglected at silhouettes, so BTF-mapped objects retain the coarse shape of the underlying model. We augment BTF rendering to obtain approximate mesoscale silhouettes. Our new representation, the 4D mesostructure distance function (MDF), tabulates the displacement from a reference frame where a ray first intersects the mesoscale geometry beneath as a function of ray direction and ray position along that reference plane. Given an MDF, the mesostructure silhouette can be rendered with a per-pixel depth peeling process on graphics hardware, while shading and local parallax are handled by the BTF. Our approach allows real-time rendering, handles complex, non-height-field mesostructure, requires that no additional geometry be sent to the rasterizer other than the mesh triangles, is more compact than textured visibility representations used previously, and, for the first time, can be easily measured from physical samples. We also adapt the algorithm to capture detailed shadows cast both by and onto BTF-mapped surfaces. We demonstrate the efficiency of our algorithm on a variety of BTF data, including real data acquired using our BTF–MDF measurement system.     

Feature‐Preserving Displacement Mapping With Graphics Processing Unit (GPU) Tessellation

Displacement mapping reconstructs a high‐frequency surface by adding geometric details encoded in the displacement map to the coarse base surface. In the context of hardware tessellation supported by GPUs, this paper aims at feature‐preserving surface reconstruction, and proposes the generation of a displacement map that displaces more vertices towards the higher‐frequency feature parts of the target mesh. In order to generate the feature‐preserving displacement map, surface features of the target mesh are estimated, and then the target mesh is parametrized and sampled using the features. At run time, the base surface is semi‐uniformly tessellated by hardware, and then the vertices of the tessellated mesh are displaced non‐uniformly along the 3‐D vectors stored in the displacement map. The experimental results show that the surfaces reconstructed by the proposed method are of a higher quality than those reconstructed by other methods.     

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.