Real‐Time Concurrent Linked List Construction on the GPU

We introduce a method to dynamically construct highly concurrent linked lists on modern graphics processors. Once constructed, these data structures can be used to implement a host of algorithms useful in creating complex rendering effects in real time. We present a straightforward way to create these linked lists using generic atomic operations available in APIs such as OpenGL 4.0 and DirectX 11. We also describe several possible applications of our algorithm. One example uses per‐pixel linked lists for order‐independent transparency; as a consequence, we are able to directly implement fully programmable blending, which frees developers from the restrictions imposed by current graphics APIs. The second uses linked lists to implement real‐time indirect shadows.     

Teaching, Exploring, Learning—Developing Tutorials for In-Class Teaching and Self-Learning

This paper presents an experience report on a novel approach for a course on intermediate and advanced computer graphics topics. The approach uses Teachlet Tutorials, a combination of traditional seminar–type teaching with interactive exploration of the content by the audience, plus development of self-contained tutorials on the topic. In addition to a presentation, an interactive software tool is developed by the students to assist the audience in learning and exploring the topic's details. This process is guided through set tasks. The resulting course material is developed for two different contexts: (a) for classroom presentation and (b) as an interactive, self-contained, self-learning tutorial. The overall approach results in a more thorough understanding of the topic both for the student teachers as well as for the class participants. In addition to detailing the Teachlet Tutorial approach, this paper presents our experiences implementing the approach in our Advanced Computer Graphics course and presents the resultant projects. Most of the final Teachlet Tutorials were surprisingly good and we had excellent feedback from the students on the approach and course.     

BqR‐Tree: A Data Structure for Flights and Walkthroughs in Urban Scenes with Mobile Elements

BqR‐Tree, the data structure presented in this paper is an improved R‐Tree data structure based on a quadtree spatial partitioning which improves the rendering speed of the usual R‐trees when view‐culling is implemented, especially in urban scenes. The city is split by means of a spatial quadtree partition and the block is adopted as the basic urban unit. One advantage of blocks is that they can be easily identified in any urban environment, regardless of the origins and structure of the input data. The aim of the structure is to accelerate the visualization of complex scenes containing not only static but dynamic elements. The usefulness of the structure has been tested with low structured data, which makes its application appropriate to almost all city data. The results of the tests show that when using the BqR‐Tree structure to perform walkthroughs and flights, rendering times vastly improve in comparison to the data structures which have yielded best results to date, with average improvements of around 30%.     

Visualizing and animating the winged-edge data structure

The winged- and half-edge data structures are commonly used representations for polyhedron models. Due to the complexity, students in an introductory course to computer graphics usually have difficulty in handling these data structures and developing applications. This paper describes the authors’ effort in the development of a visualization and animation tool for teaching and learning these data structures. This tool also includes a simple pseudo-code-like language for algorithm design. Instructors may employ this tool for presentation and demonstration purposes. Students may use the simple language to develop and experiment with new algorithms before their actual implementation. The visualization and animation system may be used to explore and understand the relationship among mesh elements and algorithm execution.     

Camera Control in Computer Graphics

Recent progress in modelling, animation and rendering means that rich, high fidelity virtual worlds are found in many interactive graphics applications. However, the viewer's experience of a 3D world is dependent on the nature of the virtual cinematography, in particular, the camera position, orientation and motion in relation to the elements of the scene and the action. Camera control encompasses viewpoint computation, motion planning and editing. We present a range of computer graphics applications and draw on insights from cinematographic practice in identifying their different requirements with regard to camera control. The nature of the camera control problem varies depending on these requirements, which range from augmented manual control (semi‐automatic) in interactive applications, to fully automated approaches. We review the full range of solution techniques from constraint‐based to optimization‐based approaches, and conclude with an examination of occlusion management and expressiveness in the context of declarative approaches to camera control.     

On‐the‐fly generation and rendering of infinite cities on the GPU

In this paper, we present a new approach for shape‐grammar‐based generation and rendering of huge cities in real‐time on the graphics processing unit (GPU). Traditional approaches rely on evaluating a shape grammar and storing the geometry produced as a preprocessing step. During rendering, the pregenerated data is then streamed to the GPU. By interweaving generation and rendering, we overcome the problems and limitations of streaming pregenerated data. Using our methods of visibility pruning and adaptive level of detail, we are able to dynamically generate only the geometry needed to render the current view in real‐time directly on the GPU. We also present a robust and efficient way to dynamically update a scene's derivation tree and geometry, enabling us to exploit frame‐to‐frame coherence. Our combined generation and rendering is significantly faster than all previous work. For detailed scenes, we are capable of generating geometry more rapidly than even just copying pregenerated data from main memory, enabling us to render cities with thousands of buildings at up to 100 frames per second, even with the camera moving at supersonic speed.     

Into the Blue: Better Caustics through Photon Relaxation

The photon mapping method is one of the most popular algorithms employed in computer graphics today. However, obtaining good results is dependent on several variables including kernel shape and bandwidth, as well as the properties of the initial photon distribution. While the photon density estimation problem has been the target of extensive research, most algorithms focus on new methods of optimising the kernel to minimise noise and bias. In this paper we break from convention and propose a new approach that directly redistributes the underlying photons. We show that by relaxing the initial distribution into one with a blue noise spectral signature we can dramatically reduce background noise, particularly in areas of uniform illumination. In addition, we propose an efficient heuristic to detect and preserve features and discontinuities. We then go on to demonstrate how reconfiguration also permits the use of very low bandwidth kernels, greatly improving render times whilst reducing bias.     

Linkless Octree Using Multi‐Level Perfect Hashing

The standard C/C++ implementation of a spatial partitioning data structure, such as octree and quadtree, is often inefficient in terms of storage requirements particularly when the memory overhead for maintaining parent‐to‐child pointers is significant with respect to the amount of actual data in each tree node. In this work, we present a novel data structure that implements uniform spatial partitioning without storing explicit parent‐to‐child pointer links. Our linkless tree encodes the storage locations of subdivided nodes using perfect hashing while retaining important properties of uniform spatial partitioning trees, such as coarse‐to‐fine hierarchical representation, efficient storage usage, and efficient random accessibility. We demonstrate the performance of our linkless trees using image compression and path planning examples.     

Computational Geometry Education for Computer Graphics Students

The paper surveys main features of computational geometry and presents the argument that a course oriented to applied computational geometry should be a part of the computer graphics curriculum, as it teaches effective algorithmic methods and helps to develop abstract thinking. Possible contents of the course and forms suitable and interesting for computer graphics students are discussed. The students' feedback on such a course has been mostly positive.     

Estimation and Modeling of Actual Numerical Errors in Volume Rendering

In this paper we study the comprehensive effects on volume rendered images due to numerical errors caused by the use of finite precision for data representation and processing. To estimate actual error behavior we conduct a thorough study using a volume renderer implemented with arbitrary floating‐point precision. Based on the experimental data we then model the impact of floating‐point pipeline precision, sampling frequency and fixed‐point input data quantization on the fidelity of rendered images. We introduce three models, an average model, which does not adapt to different data nor varying transfer functions, as well as two adaptive models that take the intricacies of a new data set and transfer function into account by adapting themselves given a few different images rendered. We also test and validate our models based on new data that was not used during our model building.     

Matrix Trees

We propose a new data representation for octrees and kd‐trees that improves upon memory size and algorithm speed of existing techniques. While pointerless approaches exploit the regular structure of the tree to facilitate efficient data access, their memory footprint becomes prohibitively large as the height of the tree increases. Pointerbased trees require memory consumption proportional to the number of tree nodes, thus exploiting the typical sparsity of large trees. Yet, their traversal is slowed by the need to follow explicit pointers across the different levels. Our solution is a pointerless approach that represents each tree level with its own matrix, as opposed to traditional pointerless trees that use only a single vector. This novel data organization allows us to fully exploit the tree's regular structure and improve the performance of tree operations. By using a sparse matrix data structure we obtain a representation that is suited for sparse and dense trees alike. In particular, it uses less total memory than pointer‐based trees even when the data set is extremely sparse. We show how our approach is easily implemented on the GPU and illustrate its performance in typical visualization scenarios.     

On the Effective Dimension of Light Transport

Light transport is often characterized within a high‐dimensional space although practitioners have long known that it commonly behaves as a much lower‐dimensional phenomenon. We study the effective dimension of light transport over a neighborhood on the scene manifold and show that under plausible assumptions the dimensionality is characterized by the spectrum of the spatio‐spectral concentration problem. This allows us to improve existing estimates for the dimension in computer graphics using a more insightful derivation and for the first time we obtain optimal representations. The relevance of our results for existing rendering applications is discussed.     

A Survey on Position‐Based Simulation Methods in Computer Graphics

The dynamic simulation of mechanical effects has a long history in computer graphics. The classical methods in this field discretize Newton's second law in a variety of Lagrangian or Eulerian ways, and formulate forces appropriate for each mechanical effect: joints for rigid bodies; stretching, shearing or bending for deformable bodies and pressure, or viscosity for fluids, to mention just a few. In the last years, the class of position‐based methods has become popular in the graphics community. These kinds of methods are fast, stable and controllable which make them well‐suited for use in interactive environments. Position‐based methods are not as accurate as force‐based methods in general but they provide visual plausibility. Therefore, the main application areas of these approaches are virtual reality, computer games and special effects in movies. This state‐of‐the‐art report covers the large variety of position‐based methods that were developed in the field of physically based simulation. We will introduce the concept of position‐based dynamics, present dynamic simulation based on shape matching and discuss data‐driven upsampling approaches. Furthermore, we will present several applications for these methods.     

面向能力培养的“计算机图形学”课程教学方法

本文针对计算机图形学课程的具体特点和大纲要求,在剖析课程内容、总结教学实践经验的基础上,提出金字塔式、发现式和四结合式教学方法,以此提高学生对计算机图形学课程的学习兴趣,提高学生面向问题求解的能力,同时,针对该课程特点和能力培养目标,提出侧重于综合能力测试的课程考核方法,最后,介绍课程教学实践的效果。     

A survey on Mesh Segmentation Techniques

We present a review of the state of the art of segmentation and partitioning techniques of boundary meshes. Recently, these have become a part of many mesh and object manipulation algorithms in computer graphics, geometric modelling and computer aided design. We formulate the segmentation problem as an optimization problem and identify two primarily distinct types of mesh segmentation, namely part segmentation and surface‐patch segmentation. We classify previous segmentation solutions according to the different segmentation goals, the optimization criteria and features used, and the various algorithmic techniques employed. We also present some generic algorithms for the major segmentation techniques.     

Probabilistic Visibility Evaluation for Direct Illumination

The efficient evaluation of visibility in a three‐dimensional scene is a longstanding problem in computer graphics. Visibility evaluations come in many different forms: figuring out what object is visible in a pixel; determining whether a point is visible to a light source; or evaluating the mutual visibility between 2 surface points. This paper provides a new, experimental view on visibility, based on a probabilistic evaluation of the visibility function. Instead of checking the visibility against all possible intervening geometry the visibility between 2 points is now evaluated by testing only a random subset of objects. The result is not a Boolean value that is either 0 or 1, but a numerical value that can even be negative. Because we use the visibility evaluation as part of the integrand in illumination computations, the probabilistic evaluation of visibility becomes part of the Monte Carlo procedure of estimating the illumination integral, and results in an unbiased computation of illumination values in the scene. Moreover, the number of intersections tests for any given ray is decreased, since only a random selection of geometric primitives is tested. Although probabilistic visibility is an experimental and new idea, we present a practical algorithm for direct illumination that uses the probabilistic nature of visibility evaluations.     

An Integer One-Pass Algorithm for Voxel Traversal

Voxel traversing along a line in a uniformly divided voxel space is frequently needed in different applications of computer graphics. The paper presents a new integer one‐pass algorithm for this problem. In 2D, the proposed approach is based on a modification of the well‐known Bresenham algorithm. The algorithm is then extended in 3D where a special case may occur. It is characterized by a simple discriminator. A derivation for this discriminator given in the paper confirms that all calculations can be realized using only integer arithmetic. In this way, the accumulation of rounding errors is completely eliminated, and a robust and compact implementation can be easily achieved. One of the main advantages of the proposed algorithm is that it visits 1–3 voxels during each iteration thus assuring its efficiency. The algorithm has been compared with other algorithms for voxel traversing by measuring spent CPU time. For comparison, Cleary & Wyvill's, Amanatides & Woo's, and Code‐based algorithm have been used. The proposed algorithm is faster than the referenced algorithms.     

Manipulating, Deforming and Animating Sampled Object Representations

A sampled object representation (SOR) defines a graphical model using data obtained from a sampling process, which takes a collection of samples at discrete positions in space in order to capture certain geometrical and physical properties of one or more objects of interest. Examples of SORs include images, videos, volume datasets and point datasets. Unlike many commonly used data representations in computer graphics, SORs lack in geometrical, topological and semantic information, which is much needed for controlling deformation and animation. Hence it poses a significant scientific and technical challenge to develop deformation and animation methods that operate upon SORs. Such methods can enable computer graphics and computer animation to benefit enormously from the advances of digital imaging technology. In this state of the art report, we survey a wide range of techniques that have been developed for manipulating, deforming and animating SORs. We consider a collection of elementary operations for manipulating SORs, which can serve as building blocks of deformation and animation techniques. We examine a collection of techniques that are designed to transform the geometry shape of deformable objects in sampled representations and pay particular attention to their deployment in surgical simulation. We review a collection of techniques for animating digital characters in SORs, focusing on recent developments in volume animation.     

Improving Memory Space Efficiency of Kd‐tree for Real‐time Ray Tracing

Compared with its competitors such as the bounding volume hierarchy, a drawback of the kd‐tree structure is that a large number of triangles are repeatedly duplicated during its construction, which often leads to inefficient, large and tall binary trees with high triangle redundancy. In this paper, we propose a space‐efficient kd‐tree representation where, unlike commonly used methods, an inner node is allowed to optionally store a reference to a triangle, so highly redundant triangles in a kd‐tree can be culled from the leaf nodes and moved to the inner nodes. To avoid the construction of ineffective kd‐trees entailing computational inefficiencies due to early, possibly unnecessary, ray‐triangle intersection calculations that now have to be performed in the inner nodes during the kd‐tree traversal, we present heuristic measures for determining when and how to choose triangles for inner nodes during kd‐tree construction. Based on these metrics, we describe how the new form of kd‐tree is constructed and stored compactly using a carefully designed data layout. Our experiments with several example scenes showed that our kd‐tree representation technique significantly reduced the memory requirements for storing the kd‐tree structure, while effectively suppressing the unavoidable frame‐rate degradation observed during ray tracing.     

Diffusion Based Photon Mapping

Density estimation employed in multi‐pass global illumination algorithms give cause to a trade‐off problem between bias and noise. The problem is seen most evident as blurring of strong illumination features. In particular, this blurring erodes fine structures and sharp lines prominent in caustics. To address this problem, we introduce a photon mapping algorithm based on nonlinear anisotropic diffusion. Our algorithm adapts according to the structure of the photon map such that smoothing occurs along edges and structures and not across. In this way, we preserve important illumination features, while eliminating noise. We demonstrate the applicability of our algorithm through a series of tests. In the tests, we evaluate the visual and computational performance of our algorithm comparing it to existing popular algorithms.