Computer Assisted Relief Generation—A Survey

In this paper, we present an overview of the achievements accomplished to date in the field of computer‐aided relief generation. We delineate the problem, classify different solutions, analyse similarities, investigate developments and review the approaches according to their particular relative strengths and weaknesses. Moreover, we describe remaining challenges and point out prospective extensions. In consequence, this survey is addressed to both researchers and artists, through providing valuable insights into the theory behind the different concepts in this field and augmenting the options available among the methods presented with regard to practical application.     

A Survey of Specularity Removal Methods

The separation of reflection components is an important issue in computer graphics, computer vision and image processing. It provides useful information for the applications that need consistent object surface appearance, such as stereo reconstruction, visual recognition, tracking, objects re‐illumination and dichromatic editing. In this paper we will present a brief survey of recent advances in separation of reflection components, also known as specularity (highlights) removal. Several techniques that try to tackle the problem from different points of view have been proposed so far. In this survey, we will overview these methods and we will present a critical analysis of their benefits and drawbacks.     

Geometry Textures and Applications†

Geometry textures are a novel geometric representation for surfaces based on height maps. The visualization is done through a graphics processing unit (GPU) ray casting algorithm applied to the whole object. At rendering time, the fine‐scale details (mesostructures) are reconstructed preserving original quality. Visualizing surfaces with geometry textures allows a natural level‐of‐detail (LOD) behaviour. There are numerous applications that can benefit from the use of geometry textures. In this paper, besides a mesostructure visualization survey, we present geometry textures with three possible applications: rendering of solid models, geological surfaces visualization and surface smoothing.     

Spectral Mesh Processing

Spectral methods for mesh processing and analysis rely on the eigenvalues, eigenvectors, or eigenspace projections derived from appropriately defined mesh operators to carry out desired tasks. Early work in this area can be traced back to the seminal paper by Taubin in 1995, where spectral analysis of mesh geometry based on a combinatorial Laplacian aids our understanding of the low‐pass filtering approach to mesh smoothing. Over the past 15 years, the list of applications in the area of geometry processing which utilize the eigenstructures of a variety of mesh operators in different manners have been growing steadily. Many works presented so far draw parallels from developments in fields such as graph theory, computer vision, machine learning, graph drawing, numerical linear algebra, and high‐performance computing. This paper aims to provide a comprehensive survey on the spectral approach, focusing on its power and versatility in solving geometry processing problems and attempting to bridge the gap between relevant research in computer graphics and other fields. Necessary theoretical background is provided. Existing works covered are classified according to different criteria: the operators or eigenstructures employed, application domains, or the dimensionality of the spectral embeddings used. Despite much empirical success, there still remain many open questions pertaining to the spectral approach. These are discussed as we conclude the survey and provide our perspective on possible future research.     

A Survey of Real‐Time Hard Shadow Mapping Methods

Because of its versatility, speed and robustness, shadow mapping has always been a popular algorithm for fast hard shadow generation since its introduction in 1978, first for offline film productions and later increasingly so in real‐time graphics. So it is not surprising that recent years have seen an explosion in the number of shadow map related publications. Because of the abundance of articles on the topic, it has become very hard for practitioners and researchers to select a suitable shadow algorithm, and therefore many applications miss out on the latest high‐quality shadow generation approaches. The goal of this survey is to rectify this situation by providing a detailed overview of this field. We show a detailed analysis of shadow mapping errors and derive a comprehensive classification of the existing methods. We discuss the most influential algorithms, consider their benefits and shortcomings and thereby provide the readers with the means to choose the shadow algorithm best suited to their needs.     

Adaptive Surface Texture Synthesis Using Round‐Shaped Neighbourhoods

This paper presents a novel surface texture synthesis method, which is capable of producing high‐quality results by performing the synthesis within an effective multi‐resolution scheme using an adaptive texture similarity metric. Compared with related works, our method allows us to directly carry out multi‐resolution synthesis without involving complicated operations such as mesh hierarchy and partitioning on the target surface. Also, the adaptive similarity metric focuses on measuring texture properties at different scales ranging from local to global, allowing for consistency within differently‐sized texture structures. Further, with the introduced round shaped neighbourhoods, we can save considerable amount of computation for the surface texture synthesis over variable texture directions. Experimental results are provided and comparisons are made against other latest works.     

Advances in Interaction with 3D Environments

Various interaction techniques have been developed for interactive 3D environments. This paper presents an up‐to‐date and comprehensive review of the state of the art of non‐immersive interaction techniques for Navigation, Selection & Manipulation, and System Control, including a basic introduction to the topic, the challenges and an examination of a number of popular approaches. We also introduce 3D Interaction Testbed (3DIT) to firstly allow a ‘hands‐on' understanding of 3D interaction principles, and secondly to create an open platform for defining evaluation methods, stimuli as well as representative tasks akin to those found in other disciplines of science. We hope that this survey can aid both researchers and developers of interactive 3D applications in having a clearer overview of the topic and in particular can be useful for practitioners and researchers that are new to the field of interactive 3D graphics.     

Modeling Color Properties of Tiled Displays

The concept of tiled displays can be successful only if such displays are made to look like a single display perceptually. The two issues that need to be solved to achieve this goal are geometric correction and color seamlessness of images spanning across tiles. Geometric correction algorithms borrow pin‐hole camera models to model projector display geometry. In this paper, we introduce an abstract modeling function that describes the color seen by a viewer when displayed by a display device. Though this function can be used to model color displayed by any common display device, in this paper, we use it to model color in multiprojector display systems. We use the model to explain the reasons for different types of color variations in a multiprojector display, to compare different color correction algorithms, and to derive such algorithms directly from the model.     

Semi On-Line Scheduling on Two Identical Machines

This paper investigates two different semi on-line scheduling problems on a two-machine system. In the first case, we assume that all jobs have their processing times in between p and rp . In the second case, we assume that the largest processing time is known in advance. We show that one has a best possible algorithm with worst case ratio 4/3 while LS is still the best possible for the other problem with ratio which is still in the worst case . Received: February 23, 1998; revised August 5, 1998     

GPU‐Based Spherical Light Field Rendering with Per‐Fragment Depth Correction

Image‐based rendering techniques are a powerful alternative to traditional polygon‐based computer graphics. This paper presents a novel light field rendering technique which performs per‐pixel depth correction of rays for high‐quality reconstruction. Our technique stores combined RGB and depth values in a parabolic 2D texture for every light field sample acquired at discrete positions on a uniform spherical setup. Image synthesis is implemented on the GPU as a fragment program which extracts the correct image information from adjacent cameras for each fragment by applying per‐pixel depth correction of rays. We show that the presented image‐based rendering technique provides a significant improvement compared to previous approaches. We explain two different rendering implementations which make use of a uniform parametrisation to minimise disparity problems and ensure full six degrees of freedom for virtual view synthesis. While one rendering algorithm implements an iterative refinement approach for rendering light fields with per pixel depth correction, the other approach employs a raycaster, which provides superior rendering quality at moderate frame rates. GPU based per‐fragment depth correction of rays, used in both implementations, helps reducing ghosting artifacts to a non‐noticeable amount and provides a rendering technique that performs without exhaustive pre‐processing for 3D object reconstruction and without real‐time ray‐object intersection calculations at rendering time.     

Shrinkability Maps for Content‐Aware Video Resizing

A novel method is given for content‐aware video resizing, i.e. targeting video to a new resolution (which may involve aspect ratio change) from the original. We precompute a per‐pixel cumulative shrinkability map which takes into account both the importance of each pixel and the need for continuity in the resized result. (If both x and y resizing are required, two separate shrinkability maps are used, otherwise one suffices). A random walk model is used for efficient offline computation of the shrinkability maps. The latter are stored with the video to create a multi‐sized video, which permits arbitrary‐sized new versions of the video to be later very efficiently created in real‐time, e.g. by a video‐on‐demand server supplying video streams to multiple devices with different resolutions. These shrinkability maps are highly compressible, so the resulting multi‐sized videos are typically less than three times the size of the original compressed video. A scaling function operates on the multi‐sized video, to give the new pixel locations in the result, giving a high‐quality content‐aware resized video. Despite the great efficiency and low storage requirements for our method, we produce results of comparable quality to state‐of‐the‐art methods for content‐aware image and video resizing.     

A Survey of Inverse Surface Design From Light Transport Behavior Specification

Inverse surface design problems from light transport behavior specification usually represent extremely complex and costly processes, but their importance is well known. In particular, they are very interesting for lighting and luminaire design, in which it is usually difficult to test design decisions on a physical model in order to avoid costly mistakes. In this survey, we present the main ideas behind these kinds of problems, characterize them, and summarize existing work in the area, revealing problems that remain open and possible areas of further research.     

State‐of‐the‐Art in GPU‐Based Large‐Scale Volume Visualization

This survey gives an overview of the current state of the art in GPU techniques for interactive large‐scale volume visualization. Modern techniques in this field have brought about a sea change in how interactive visualization and analysis of giga‐, tera‐ and petabytes of volume data can be enabled on GPUs. In addition to combining the parallel processing power of GPUs with out‐of‐core methods and data streaming, a major enabler for interactivity is making both the computational and the visualization effort proportional to the amount and resolution of data that is actually visible on screen, i.e. ‘output‐sensitive’ algorithms and system designs. This leads to recent output‐sensitive approaches that are ‘ray‐guided’, ‘visualization‐driven’ or ‘display‐aware’. In this survey, we focus on these characteristics and propose a new categorization of GPU‐based large‐scale volume visualization techniques based on the notions of actual output‐resolution visibility and the current working set of volume bricks—the current subset of data that is minimally required to produce an output image of the desired display resolution. Furthermore, we discuss the differences and similarities of different rendering and data traversal strategies in volume rendering by putting them into a common context—the notion of address translation. For our purposes here, we view parallel (distributed) visualization using clusters as an orthogonal set of techniques that we do not discuss in detail but that can be used in conjunction with what we present in this survey.     

Visualization for the Physical Sciences

Close collaboration with other scientific fields is an important goal for the visualization community. Yet engaging in a scientific collaboration can be challenging. The physical sciences, namely astronomy, chemistry, earth sciences and physics, exhibit an extensive range of research directions, providing exciting challenges for visualization scientists and creating ample possibilities for collaboration. We present the first survey of its kind that provides a comprehensive view of existing work on visualization for the physical sciences. We introduce novel classification schemes based on application area, data dimensionality and main challenge addressed, and apply these classifications to each contribution from the literature. Our survey helps in understanding the status of current research and serves as a useful starting point for those interested in visualization for the physical sciences.     

Polynomial Approximation and Graph-Coloring

Consider a graph G=(V,E) of order n. In the minimum graph-coloring problem we try to color V with as few colors as possible so that no two adjacent vertices receive the same color. This problem is among the first ones proved to be intractable, and hence, it is very unlikely that an optimal polynomial-time algorithm could ever be devised for it. In this paper, we survey the main polynomial time approximation algorithms (the ones for which theoretical approximability bounds have been studied) for the minimum graph-coloring and we discuss their approximation performance and their complexity. Finally, we further improve the approximation ratio for graph-coloring. Received October 5, 2001; revised November 15, 2002 Published online: February 20, 2003     

Quality Metrics for Information Visualization

The visualization community has developed to date many intuitions and understandings of how to judge the quality of views in visualizing data. The computation of a visualization's quality and usefulness ranges from measuring clutter and overlap, up to the existence and perception of specific (visual) patterns. This survey attempts to report, categorize and unify the diverse understandings and aims to establish a common vocabulary that will enable a wide audience to understand their differences and subtleties. For this purpose, we present a commonly applicable quality metric formalization that should detail and relate all constituting parts of a quality metric. We organize our corpus of reviewed research papers along the data types established in the information visualization community: multi‐ and high‐dimensional, relational, sequential, geospatial and text data. For each data type, we select the visualization subdomains in which quality metrics are an active research field and report their findings, reason on the underlying concepts, describe goals and outline the constraints and requirements. One central goal of this survey is to provide guidance on future research opportunities for the field and outline how different visualization communities could benefit from each other by applying or transferring knowledge to their respective subdomain. Additionally, we aim to motivate the visualization community to compare computed measures to the perception of humans.     

Fast Isosurface Rendering on a GPU by Cell Rasterization

This paper presents a fast, high‐quality, GPU‐based isosurface rendering pipeline for implicit surfaces defined by a regular volumetric grid. GPUs are designed primarily for use with polygonal primitives, rather than volume primitives, but here we directly treat each volume cell as a single rendering primitive by designing a vertex program and fragment program on a commodity GPU. Compared with previous raycasting methods, ours has a more effective memory footprint (cache locality) and better coherence between multiple parallel SIMD processors. Furthermore, we extend and speed up our approach by introducing a new view‐dependent sorting algorithm to take advantage of the early‐z‐culling feature of the GPU to gain significant performance speed‐up. As another advantage, this sorting algorithm makes multiple transparent isosurfaces rendering available almost for free. Finally, we demonstrate the effectiveness and quality of our techniques in several real‐time rendering scenarios and include analysis and comparisons with previous work.     

Visual Supercomputing: Technologies, Applications and Challenges

If we were to have a Grid infrastructure for visualization, what technologies would be needed to build such an infrastructure, what kind of applications would benefit from it, and what challenges are we facing in order to accomplish this goal? In this survey paper, we make use of the term ‘visual supercomputing’ to encapsulate a subject domain concerning the infrastructural technology for visualization. We consider a broad range of scientific and technological advances in computer graphics and visualization, which are relevant to visual supercomputing. We identify the state‐of‐the‐art technologies that have prepared us for building such an infrastructure. We examine a collection of applications that would benefit enormously from such an infrastructure, and discuss their technical requirements. We propose a set of challenges that may guide our strategic efforts in the coming years.     

Speed-up Technique for a Local Automatic Colour Equalization Model

In this paper we propose a speed‐up technique for a local automatic colour equalization operator derived from a model of the human vision system. This method is characterized by local and global filtering effects, that simultaneously achieve different equalization tasks e.g. performing colour and lightness constancy, realizing dynamic image data driven stretching, controlling the contrast. We describe a way to quickly create a filtering mapping function to perform the global component of the mapping. This method is based on singular value decomposition (SVD) applied to sampled and filtered points in the input image. Then, the local information is added computing the basic algorithm on a neighbourhood of each input pixel. A slight quality loss is the price that we have to pay for a speed‐up of more than two orders of magnitude of the basic algorithm. We present the results on several images and discuss the efficiency and the drawbacks of the speed‐up technique.