Viewpoint-based simplification using f-divergences

We propose a new viewpoint-based simplification method for polygonal meshes, driven by several f-divergences such as Kullback-Leibler, Hellinger and Chi-Square. These distances are a measure of discrimination between probability distributions. The Kullback-Leibler distance between the projected and the actual area distributions of the polygons in the scene already has been used as a measure of viewpoint quality. In this paper, we use the variation in those viewpoint distances to determine the error introduced by an edge collapse. We apply the best half-edge collapse as a decimation criterion. The approximations produced by our method are close to the original model in terms of both visual and geometric criteria. Unlike many pure visibility-driven methods, our new approach does not completely remove hidden interiors in order to increase the visual quality of the simplified models. This makes our approach more suitable for applications which require exact geometry tolerance but also require high visual quality.     

Punctuated simplification of man-made objects

We present a simplification algorithm for manifold polygonal meshes of plane-dominant models. Models of this type are likely to appear in man-made environments. While traditional simplification algorithms focus on generality and smooth meshes, the approach presented here considers a specific class of man-made models. By detecting and classifying edge loops on the mesh and providing a guided series of binary mesh partitions, our approach generates a series of simplified models, each of which better respects the semantics of these kinds of models than conventional approaches do. A guiding principle is to eliminate simplifications that do not make sense in constructed environments. This, coupled with the concept of “punctuated simplification”, leads to an approach that is both efficient and delivers high visual quality. Comparative results are given.     

Three-axis NC milling simulation based on adaptive triangular mesh

NC milling simulation has become an important step in computer aided manufacturing (CAM). To achieve real-time simulation, the total number of polygons has to be reduced, which results in poor image quality. This paper presents an adaptive triangular mesh algorithm to reduce the number of polygons while image quality remains high. Binary tree is used to represent the milling surface, and the optimization of the mesh is performed dynamically in the process of simulation. In this algorithm, the resolution of triangles is automatically updated according to local surface flatness, thus greatly reducing the number of triangles at planar regions. By doing this, real-time and high quality of visual presentation is insured and the translation, rotation and zooming operations are still applicable. When machining precision is evaluated, or overcut, undercut and interference are inspected, full resolution model stored in memory is automatically loaded to ensure the accuracy and correctness of these inspections. Finally, an example is presented to illustrate the validity of proposed algorithm.     

基于点采样的大规模三维模型显示

大规模三维模型的实时显示一直是许多虚拟现实应用追求的目标之一,也是计算机图形学领域的研究热点之一。文中采用基于采样点的显示方法,把具有显示质量优势的传统三角形与显示速度快、简化表示能力强的采样点,通过八叉树有机组织起来;通过对基本算法做出有效的改进,并添加计算分解和重用、有效的数据管理等模块,以高效的实现方式完成了30,000个独立运动的虚拟人场景的实时显示。文中的方法也可处理其它场景,能直接应用于紧急疏散或影视、游戏等领域中大规模三维模型的显示,具有很好的应用前景。     

Generating high-quality discrete LOD meshes for 3D computer games in linear time

The real-time interactive 3D multimedia applications such as 3D computer games and virtual reality (VR) have become prominent multimedia applications in recent years. In these applications, both visual fidelity and degree of interactivity are usually crucial to the success or failure of employment. Although the visual fidelity can be increased using more polygons for representing an object, it takes a higher rendering cost and adversely affects the rendering efficiency. To balance between the visual quality and the rendering efficiency, a set of level-of-detail (LOD) meshes has to be generated in advance. In this paper, we propose a highly efficient polygonal mesh simplification algorithm that is capable of generating a set of high-quality discrete LOD meshes in linear run time. The new algorithm adopts memoryless vertex quadric computation, and suggests the use of constant size replacement selection min-heap, pipelined simplification, two-stage optimization, and a new hole-filling scheme, which enable it to generate very high-quality LOD meshes using relatively small amount of main memory space in linear runtime.     

Carving for topology simplification of polygonal meshes

The topological complexity of polygonal meshes has a large impact on the performance of various geometric processing algorithms, such as rendering and collision detection algorithms. Several approaches for simplifying topology have been discussed in the literature. These methods operate locally on models, which makes their effect on the topology hard to predict and analyze. Most existing methods tend to exhibit several disturbing artifacts, such as shrinking of the input and splitting of its components. We propose a novel top-down approach for topology simplification that avoids most problems that are common in existing methods. We start with a simple, genus-zero mesh that bounds the input and gradually introduce topologic features by a series of carving operations. This process yields a multiresolution stream of meshes with increasing topologic level of detail. We further present a carving algorithm that is based on constrained Delaunay tetrahedralization. The algorithm first constructs the tetrahedral mesh of the complement of the input with respect to its convex hull. It then proceeds to eliminate tetrahedra in a prioritized manner. We present quality results for two families of meshes that are difficult to simplify by all existing methods known to us: topologically complex meshes and highly clustered meshes.     

Seamless patches for GPU-based terrain rendering

In this paper we present a novel approach for interactive rendering of large terrain datasets. Our approach is based on subdividing a terrain into rectangular patches at different resolutions. Each patch is represented by four triangular tiles that are selected form different resolutions, and four strips which are used to stitch the four tiles in a seamless manner. Such a scheme maintains resolution changes within patches through the stitching strips, and not across patches. At runtime, these patches are used to construct a level-of-detail representation of the input terrain based on view-parameters. A selected level of detail only includes the layout of the patches and their boundary edges resolutions. The layout includes the location and dimension of each patch. Within the graphics hardware, the GPU generates the meshes of the patches by using scaled instances of cached tiles and assigns elevation for each vertex from cached textures. Since adjacent rectangular patches agree on the resolution of the common edges, the resulted mesh does not include cracks or degenerate triangles. Our algorithm manages to achieve quality images at high frame rates while providing seamless transition between different levels of detail.     

一种大规模地形的高效绘制算法

大规模地形的实时可视化是仿真和虚拟地理环境系统的重要问题。文章提出了一种基于规则网格的视点相关的地形模型实时生成及绘制算法。该算法采用类似于纹理多重映射的技术,以屏幕误差作为细分的依据,通过基于地形小块的自顶向下的细分来实时生成地形连续LO D模型。在PⅣ1.7G、集成显卡、256M B RAM的硬件平台上,本算法可实现对257×257个采样点地形的实时漫游.实验表明,该算法具有较低的时间、空间开销,适于大规模地形的实时可视化。     

Point-based rendering techniques

The increasing popularity of points as rendering primitives has led to a variety of different rendering algorithms, and the different implementations compare like apples to oranges. In this paper, we revisit and compare a number of recently developed point-based rendering implementations within a common testbed. Also we briefly summarize a few proposed hierarchical multiresolution point data structures and discuss their advantages. Based on a common view-dependent level-of-detail (LOD) rendering framework, we then examine different hardware accelerated point rendering algorithms. Experimental results are given with respect to performance timing and rendering quality for the different approaches. Additionally, we also compare the point-based rendering techniques to a basic triangle mesh approach.