@article{Akkouche:2001:AIS, author = {Samir Akkouche and Eric Galin}, title = {Adaptive Implicit Surface Polygonization Using Marching Triangles}, volume = {20}, number = {2}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, pages = {67-80}, note = {{ISSN} 1067-7055}, keywords = {Implicit Surfaces, Incremental Meshing, Marching Triangles, Polygonization}, annote = {This paper presents several improvements to the marching triangles algorithm for general implicit surfaces. The original method generates equilateral triangles of constant size almost everywhere on the surface. We present several modifications to adapt the size of the triangles to the curvature of the surface. As cracks may arise in the resulting polygonization, we propose a specific crack-closing method invoked at the end of the mesh growing step. Eventually, we show that the marching triangles can be used as an incremental meshing technique in an interactive modeling environment. In contrast to existing incremental techniques based on spatial subdvision, no extra data-structure is needed to incrementally edit skeletal implicit surfaces, which saves both memory and computation time. }, } @article{Smith:2001:FAC, author = {Jeffrey Smith and Andrew Witkin and David Baraff}, title = {Fast and Controllable Simulation of the Shattering of Brittle Objects}, volume = {20}, number = {2}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, pages = {81-91}, note = {{ISSN} 1067-7055}, keywords = {physically based modeling, computer animation, impact, brittle materials}, annote = {We present a method for the rapid and controllable simulation of the shattering of brittle objects under impact. An object is represented as a set of point masses connected by distance-preserving linear constraints. This use of constraints, rather than stiff springs, gains us a significant advantage in speed while still retaining fine control over the fracturing behavior. The forces exerted by these constraints during impact are computed using Lagrange multipliers. These constraint forces are then used to determine when and where the object will break, and to calculate the velocities of the newly created fragments. We present the details of our technique together with examples illustrating its use. }, } @article{Isenburg:2001:TSC, author = {Martin Isenburg}, title = {Triangle Strip Compression}, volume = {20}, number = {2}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, pages = {91-101}, note = {{ISSN} 1067-7055}, keywords = {mesh compression, connectivity coding, triangle strips, triangle fans, stripification}, annote = {In this paper we introduce a simple and efficient scheme for encoding the connectivity and the stripification of a triangle mesh. Since generating a good set of triangle strips is a hard problem, it is desirable to do this just once and store the computed strips with the triangle mesh. However, no previously reported mesh encoding scheme is designed to include triangle strip information into the compressed representation. Our algorithm encodes the stripification and the connectivity in an interwoven fashion, that exploits the correlation existing between the two. }, } @article{Thuermer:2001:SNV, author = {Grit Th{\"{u}}rmer}, title = {Smoothing Normal Vectors on Discrete Surfaces While Preserving Slope Discontinuities}, volume = {20}, number = {2}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, pages = {103-113}, note = {{ISSN} 1067-7055}, keywords = {Discrete Normals, Discrete Shading, Discrete Surfaces, Visualization}, annote = {A new method is proposed which smoothes normal vectors over a discrete surface, preserving slope discontinuities and small details. Assume an estimate of the normal vector at each surface point is known and these estimates are computed from small neighbourhoods such that slope discontinuities and small details are still reflected by these normals. To smooth these normals, the normal vectors at points in a certain neighbourhood are averaged. The size of the neighbourhood considered for the smoothing at a point is adapted according the local surface configuration. The adaptation is performed, depending on the tangent plane at the point considered as well as the angles between the normals at neighbouring points and the normal at the point in question. }, } @article{Liu:2001:CFF, author = {Xinguo Liu and Hujun Bao and PhengAnn Heng and TienTsin Wong and Qunsheng Peng}, title = {Constrained Fairing for Meshes}, volume = {20}, number = {2}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, pages = {115-124}, note = {{ISSN} 1067-7055}, keywords = {curves, surfaces, geometric modeling, level of detail, algorithms, mesh generation}, annote = {In this paper, we present a novel fairing algorithm for the removal of noise from uniform triangular meshes without shrinkage and serious distortion. The key feature of this algorithm is to keep all triangle centers invariant at each smoothing step by including some constraints in the energy minimization functional. The constrained functional is then minimized efficiently using an iterative method. Further, we apply this smoothing technique to a multiresolution representation to remove arbitrary levels of detail. A volume-preserving decimation algorithm is presented to generate the multiresolution representation. The experimental results demonstrate the combined algorithm's stability and efficiency. }, } @article{Brodlie:2001:RAI, author = {Ken Brodlie and Jason Wood}, title = {Recent Advances in Volume Visualization}, volume = {20}, number = {2}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, pages = {125-148}, note = {{ISSN} 1067-7055}, keywords = {scientific visualization, data visualization, volume visualization, isosurfacing, slicing, volume rendering}, annote = {In the past few years, there have been key advances in the three main approaches to the visualization of volumetric data: isosurfacing, slicing and volume rendering, which together make up the field of volume visualization. In this survey paper we set the scene by describing the fundamental techniques for each of these approaches, using this to motivate the range of advances which have evolved over the past few years. In isosurfacing, we see how the original marching cubes algorithm has matured, with improvements in robustness, topological consistency, accuracy and performance. In the performance area, we look in detail at pre-processing steps which help identify data which contributes to the particular isosurface required. In slicing too, there are performance gains from identifying active cells quickly. In volume rendering, we describe the two main approaches of ray casting and projection. Both approaches have evolved technically over the past decade, and the holy grail of real-time volume rendering has arguably been reached. The aim of this review paper is to pull these developments together in a coherent review of recent advances in volume visualization. }, } @article{Briere:2001:ARO, author = {Normand Bri{\`{e}}re and Pierre Poulin}, title = {Adaptive Representation of Specular Light}, volume = {20}, number = {2}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, pages = {149-162}, note = {{ISSN} 1067-7055}, keywords = {caustics, global illumination, ray tracing, wavefront, beam, shaft}, annote = {Caustics produce beautiful and intriguing illumination patterns. However, their complex behavior makes them difficult to simulate accurately in all but the simplest configurations. To capture their appearance, we present an adaptive approach based upon light beams. Exploiting the coherence between the light rays forming a beam greatly reduces the number of samples required for precise illumination reconstruction. The beams characterize the light distribution due to interactions with specular surfaces in {3D} space. They thus allow for the treatment of illumination within single-scattering participating media. A hierarchical structure enclosing the light beams possesses inherent properties to detect efficiently all beams reaching any {3D} point, to adapt itself according to illumination effects in the final image, and to reduce memory consumption via caching. }, } @article{Nonato:2001:ANA, author = {L. Nonato and R. Minghim and M. C. F. Oliveira and G. Tavares}, title = {A Novel Approach for Delaunay {3D} Reconstruction with a Comparative Analysis in the Light of Applications}, volume = {20}, number = {2}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, pages = {161-171}, note = {{ISSN} 1067-7055}, annote = {This paper presents a novel algorithm for volumetric reconstruction of objects from planar sections using Delaunay triangulation, which solves the main problems posed to models defined by reconstruction, particularly from the viewpoint of producing meshes that are suitable for interaction and simulation tasks. The requirements for these applications are discussed here and the results of the method are presented. Additionally, it is compared to another commonly used reconstruction algorithm based on Delaunay triangulation, showing the advantages of the reconstructions obtained by our technique. }, } @article{Buehler:2001:LIE, author = {Katja B{\"{u}}hler}, title = {Linear Interval Estimations for Parametric Objects Theory and Application}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {The new concept of parametrized bounding volumes for parametric objects is proposed to replace the common compact bounding volumes like axis aligned bounding boxes and parallelepipeds. Linear Interval Estimations (LIEs) are developed as a realization of the discussed ideas. Two reliable methods for the computation of LIEs are introduced based on a new understanding of the use of affine arithmetics and a special application of Taylor Models. The particular structure of LIEs allows an effective intersection test of LIEs with rays, boxes and other LIEs. The test gives besides of a possible location of the intersection in object space information about affected parts in the parameter spaces of the enclosed objects. A subdivision algorithm for the intersection of two parametric surface patches with remarkable experimental results is presented as a possible application. }, } @article{Lane:2001:RII , author = {J. R. T. Lane and V. Lalioti}, title = {Reflective Interaction in Virtual Environments}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {The proliferation of projection-based systems in recent years resulted in a variety of specialised interaction techniques that make Virtual Environments a better man machine interface. However, the success of these techniques and metaphors is directly linked to the interaction and tracking devices used in their implementation. Users find that devices such as the data glove, stylus or joystick can be expensive and cumbersome especially for the inexperienced. A variety of approaches exist that make use of computer vision for tracking gestures or for achieving wireless interaction. Typically these approaches involve the use of a two- camera pair, or a stereoscopic camera. Our approach uses only one camera and one or more reflective surfaces, to effectively and accurately calculate {3D} information. The calibration time is minimal and it allows for a very flexible positioning of the camera and reflecting surfaces. Wireless interaction and natural interaction metaphors in the user's physical space can be created using our method. The method can be combined easily and effectively with projection-based systems as well as with standard and stereoscopic monitors, or extended for the use in augmented spaces. It is an inexpensive method that uses commonly available hardware and therefore its application areas as an interaction and tracking device, include games and use of virtual environments in education. In this paper, we describe the method and its use as an interaction device in two applications, and conclude with a discussion on its advantages and limitations. }, } @article{Staadt:2001:JAP, author = {Oliver G. Staadt and Martin N{\"{a}}f and Edouard Lamboray and Stephan W{\"{u}}rmlin}, title = {{JAPE}: A Prototyping System for Collaborative Virtual Environments}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {We present {JAPE}, a flexible prototyping system to support the design of a new advanced collaborative virtual environment. We describe the utilization of different hard- and software components to quickly build a flexible, yet powerful test bed for application and algorithm development. These components include a 3-D rendering toolkit, live video acquisition, speech transmission, and the control of tracking and interaction devices. To facilitate the simultaneous design of applications and algorithms that take advantage of unique features of new collaborative virtual environments, we provide the developer with a flexible prototyping toolkit which emulates the functionality of the final system. The applicability of {JAPE} is demonstrated with several prototype applications and algorithms. }, } @article{Rushmeier:2001:RIA, author = {Holly Rushmeier}, title = {Rendering: Input and Output}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Rendering is the process of creating an image from numerical input data. In the past few years our ideas about methods for acquiring the input data and the form of the output have expanded. The availability of inexpensive cameras and scanners has influenced how we can obtain data needed for rendering. Input for rendering ranges from sets of images to complex geometric descriptions with detailed {BRDF} data. The images that are rendered may be simply arrays of {RGB} images, or they may be arrays with vectors or matrices of data defined for each pixel. The rendered images may not be intended for direct display, but may be textures for geometries that are to be transmitted to be rendered on another system. A broader range of parameters now need to be taken into account to render images that are perceptually consistent across displays that range from CAVEs to personal digital assistants. This presentation will give an overview of how new hardware and new applications have changed traditional ideas of rendering input and output. }, } @article{Teler:2001:SOC, author = {Eyal Teler and Dani Lischinski}, title = {Streaming of Complex {3D} Scenes for Remote Walkthroughs}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {We describe a new {3D} scene streaming approach for remote walkthroughs. In a remote walkthrough, a user on a client machine interactively navigates through a scene that resides on a remote server. Our approach allows a user to walk through a remote {3D} scene, without ever having to download the entire scene from the server. Our algorithm achieves this by selectively transmitting only small parts of the scene and lower quality representations of objects, based on the user's viewing parameters and the available connection bandwidth. An online optimization algorithm selects which object representations to send, based on the integral of a benefit measure along the predicted path of movement. The rendering quality at the client depends on the available bandwidth, but practical navigation of the scene is possible even when bandwidth is low. }, } @article{Felkel:2001:IAC, author = {Petr Felkel and Mario Bruckschwaiger and Rainer Wegenkittl}, title = {Implementation and Complexity of the Watershed-from-Markers Algorithm Computed as a Minimal Cost Forest}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {The watershed algorithm belongs to classical algorithms in mathematical morphology. Lotufo et al.1 published a principle of the watershed computation by means of an iterative forest transform (IFT), which computes a shortest path forest from given markers. The algorithm itself was described for a {2D} case (image) without a detailed discussion of its computation and memory demands for real datasets. As {IFT} cleverly solves the problem of plateaus and as it gives precise results when thin objects have to be segmented, it is obvious to use this algorithm for {3D} datasets taking in mind the minimizing of a higher memory consumption for the {3D} case without loosing low asymptotical time complexity of O(m + C) (and also the real computation speed). The main goal of this paper is an implementation of the {IFT} algorithm with a priority queue with buckets and careful tuning of this implementation to reach as minimal memory consumption as possible. The paper presents five possible modifications and methods of implementation of the {IFT} algorithm. All presented implementations keep the time complexity of the standard priority queue with buckets but the best one minimizes the costly memory allocation and needs only 19-45% of memory for typical {3D} medical imaging datasets. Memory saving was reached by an {IFT} algorithm simplification, which stores more elements in temporary structures but these elements are simpler and thus need less memory.The best presented modification allows segmentation of large {3D} medical datasets (up to 512×512×680 voxels) with 12- or 16-bits per voxel on currently available {PC} based workstations. }, } @article{Breen:2001:3MB, author = {David E. Breen and Sean Mauch and Ross T. Whitaker and Jia Mao}, title = {{3D} Metamorphosis Between Different Types of Geometric Models}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {We present a powerful morphing technique based on level set methods, that can be combined with a variety of scan conversion/model processing techniques. Bringing these techniques together creates a general morphing approach that allows a user to morph a number of geometric model types in a single animation. We have developed techniques for converting several types of geometric models (polygonal meshes, {CSG} models and {MRI} scans) into distance volumes, the volumetric representation required by our level set morphing approach. The combination of these two capabilities allows a user to create a morphing sequence regardless of the model type of the source and target objects, freeing him/her to use whatever model type is appropriate for a particular animation. }, } @article{Nguyen:2001:RHQ, author = {Ky Giang Nguyen and Dietmar Saupe}, title = {Rapid High Quality Compression of Volume Data for Visualization}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Volume data sets resulting from, e.g., computerized tomography (CT) or magnetic resonance (MR) imaging modalities require enormous storage capacity even at moderate resolution levels. Such large files may require compression for processing in {CPU} memory which, however, comes at the cost of decoding times and some loss in reconstruction quality with respect to the original data. For many typical volume visualization applications (rendering of volume slices, subvolumes of interest, or isosurfaces) only a part of the volume data needs to be decoded. Thus, efficient compression techniques are needed that provide random access and rapid decompression of arbitrary parts the volume data. We propose a technique which is block based and operates in the wavelet transformed domain. We report performance results which compare favorably with previously published methods yielding large reconstruction quality gains from about 6 to 12 dB in {PSNR} for a 5123-volume extracted from the Visible Human data set. In terms of compression our algorithm compressed the data 6 times as much as the previous state-of-the-art block based coder for a given {PSNR} quality. }, } @article{Kunimatsu:2001:FSA, author = {A. Kunimatsu and Y. Watanabe and H. Fujii and T. Saito and K. Hiwada and T. Takahashi and H. Ueki}, title = {Fast simulation and rendering techniques for fluid objects}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Movies with actions and light effects of fluid objects are aesthetically pleasing and interesting. Until now, the calculation costs of simulation and rendering of fluid objects have been very high. Using a modern {PC} system and appropriate methods, we achieved a time of 10-20 seconds per frame for this application. Our system uses a full Navier-Stokes equation solver with uniform Eulerian mesh, marching cube isosurface techniques, Catmull-Clark subdivision surface techniques, ray tracing techniques on each vertex and conventional polygon base rendering by {HW} accelerator. In this paper, we describe the components of our system and the reasons for choosing them. By measuring {CPU} times of each process for some movie scenes of fluid objects, we evaluate this system. We consider what factors are important for creating movies of fluid objects with short {TAT}. }, } @article{Durikovic:2001:AOS, author = {Roman Durikovic}, title = {Animation of Soap Bubble Dynamics, Cluster Formation and Collision}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {What is happening when a soap bubble floats on the air? How do bubbles coalesce to form beautiful three-dimensional clusters? The physical-based model and animation described herein provide the answers. This paper deals with a complete computer simulation of soap bubbles from a dynamic perspective, which should prove to be of great interest to physicists and mathematicians. We discuss the dynamic formation of irregular bubble clusters and how to animate bubbles. The resulting model takes into account surface tension, film elasticity, and shape variations due to gravity and external wind forces. }, } @article{Harris:2001:RCR, author = {Mark J. Harris and Anselmo Lastra}, title = {Real-Time Cloud Rendering}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {This paper presents a method for realistic real-time rendering of clouds suitable for flight simulation and games. It provides a cloud shading algorithm that approximates multiple forward scattering in a preprocess, and first order anisotropic scattering at runtime. Impostors are used to accelerate cloud rendering by exploiting frame-to-frame coherence in an interactive flight simulation. Impostors are shown to be particularly well suited to clouds, even in circumstances under which they cannot be applied to the rendering of polygonal geometry. The method allows hundreds of clouds and hundreds of thousands of particles to be rendered at high frame rates, and improves interaction with clouds by reducing artifacts introduced by direct particle rendering techniques. }, } @article{Rushmeier:2001:HMC, author = {Holly Rushmeier and Laurent Balmelli and Fausto Bernardini}, title = {Horizon Map Capture}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {We present a method for computing horizon maps from captured images of a bumpy surface. Horizon maps encode surface self-shadowing effects, and can be used with bump or normals maps to realistically render surfaces with small height perturbations. The method does not rely on complete surface reconstruction, and requires only eight captured images as input. In this paper we discuss how shadow information is extrapolated from the eight captured images to compute the horizon map. Our implementation accounts for the noise and uncertainties in physically acquired data. }, } @article{Eckstein:2001:TMW, author = {Ilya Eckstein and Vitaly Surazhsky and Craig Gotsman}, title = {Texture Mapping with Hard Constraints}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {We show how to continuously map a texture onto a {3D} triangle mesh when some of the mesh vertices are constrained to have given (u, v) coordinates. This problem arises frequently in interactive texture mapping applications and, to the best of our knowledge, a complete and efficient solution is not available. Our techniques always guarantee a solution by introducing extra (Steiner) vertices in the triangulation if needed. We show how to apply our methods to texture mapping in multi-resolution scenarios and image warping and morphing. }, } @article{Hecker:2001:WGW, author = {Chris Hecker}, title = {Why Games Will Be the Preeminent Art Form of the 21st Century}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Computer games share many artistic and technical characteristics with films of the early 1900s. Games' artistic evolution is hampered by the lack of artistic respect from society at large, and the lack of technical standards that would allow artistic innovation. The same problems affected cinema during its birth. During the early 20th century, film managed to find its way from popular diversion to highly respected art form. Will games follow the same course, or will they be stuck forever in the ghetto of pop culture? What technological and artistic changes need to occur in the medium for games to evolve beyond merely shooting aliens and into an art form worthy of association with painting, music, writing, and film? This talk will pose some of those questions, if not attempt to answer them. }, } @article{Iwakiri:2001:PRT, author = {Yuya Iwakiri and Toyohisa Kaneko}, title = {PC-based Real-time Texture Painting on Real World Objects}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {The problem of texture mapping on real world objects has attracted attention recently. A work by Lensch et al. addressed the problem of locating a camera position in the celestial sphere and then mapping the acquired pictures on a real world object. The entire process took a half hour to one hour to map 10 to 15 pictures. In this paper, we propose a new innovative algorithm to speed up the texture mapping or painting process in real-time. We built a PC-based system using a commonly available video card with a geometry engine. Mapping of a picture required about 20 seconds. It is successful in giving an illusion to the operator to paint a colorless real world object with a color texture brush. }, } @article{Bourguignon:2001:DFI, author = {David Bourguignon and Marie-Paule Cani and George Drettakis}, title = {Drawing for Illustration and Annotation in {3D}}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, keywords = {drawing, stroke-based illustration, interface}, annote = {We present a system for sketching in {3D}, which strives to preserve the degree of expression, imagination, and simplicity of use achieved by {2D} drawing. Our system directly uses user-drawn strokes to infer the sketches representing the same scene from different viewpoints, rather than attempting to reconstruct a {3D} model. This is achieved by interpreting strokes as indications of a local surface silhouette or contour. Strokes thus deform and disappear progressively as we move away from the original viewpoint. They may be occluded by objects indicated by other strokes, or, in contrast, be drawn above such objects. The user draws on a plane which can be positioned explicitly or relative to other objects or strokes in the sketch. Our system is interactive, since we use fast algorithms and graphics hardware for rendering. We present applications to education, design, architecture and fashion, where {3D} sketches can be used alone or as an annotation of an existing {3D} model. }, } @article{Way:2001:TSO, author = {Der-Lor Way and Zen-Chung Shih}, title = {The Synthesis of Rock Textures in Chinese Landscape Painting}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {In Chinese landscape painting, rock textures portray the orientation of mountains and contribute to the atmosphere. Many landscape-painting skills are required according to the type of rock. Landscape painting is the major theme of Chinese painting. Over the centuries, masters of Chinese landscape painting developed various texture strokes. Hemp-fiber and axe-cut are two major types of texture strokes. A slightly sinuous and seemingly broken line, the hemp-fiber stroke is used for describing the gentle slopes of rock formations whereas the axe-cut stroke best depicts hard, rocky surfaces. This paper presents a novel method of synthesizing rock textures in Chinese landscape painting, useful not only to artists who want to paint interactively, but also in automated rendering of natural scenes. The method proposed underwrites the complete painting process after users have specified only the contour and parameters. }, } @article{Kang:2001:TIT, author = {Hyung Woo Kang and Soon Hyoung Pyo and Ken-ichi Anjyo and Sung Yong Shin}, title = {Tour Into the Picture using a Vanishing Line and its Extension to Panoramic Images}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, keywords = {Image-based modeling/rendering, projective geometry, vanishing line, panoramic image}, annote = {Tour into the picture (TIP) proposed by Horry et al.is a method for generating a sequence of walk-through images from a single reference picture (or image). By navigating a {3D} scene model constructed from the picture, {TIP} produces convincing 3D effects. Assuming that the picture has one vanishing point, they proposed the scene modeling scheme called spidery mesh. However, this scheme has to go through major modification when the picture contains multiple vanishing points or does not have any well-defined vanishing point. Moreover, the spidery mesh is hard to generalize for other types of images such as panoramic images. In this paper, we propose a new scheme for {TIP} which is based on a single vanishing line instead of a vanishing point. Based on projective geometry, our scheme is simple and yet general enough to address the problems faced with the previous method. We also show that our scheme can be naturally extended to a panoramic image. }, } @article{Haber:2001:PGC, author = {J{\"{o}}rg Haber and Karol Myszkowski and Hitoshi Yamauchi and Hans-Peter Seidel}, title = {Perceptually Guided Corrective Splatting}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {One of the basic difficulties with interactive walkthroughs is the high quality rendering of object surfaces with non-diffuse light scattering characteristics. Since full ray tracing at interactive rates is usually impossible, we render a precomputed global illumination solution using graphics hardware and use remaining computational power to correct the appearance of non-diffuse objects on-the-fly. The question arises, how to obtain the best image quality as perceived by a human observer within a limited amount of time for each frame. We address this problem by enforcing corrective computation for those non-diffuse objects that are selected using a computational model of visual attention. We consider both the saliency- and task-driven selection of those objects and benefit from the fact that shading artifacts of "unattended" objects are likely to remain unnoticed. We use a hierarchical image-space sampling scheme to control ray tracing and splat the generated point samples. The resulting image converges progressively to a ray traced solution if the viewing parameters remain unchanged. Moreover, we use a sample cache to enhance visual appearance if the time budget for correction has been too low for some frame. We check the validity of the cached samples using a novel criterion suited for non-diffuse surfaces and reproject valid samples into the current view. }, } @article{Wald:2001:IRW, author = {Ingo Wald and Philipp Slusallek and Carsten Benthin and Markus Wagner}, title = {Interactive Rendering with Coherent Ray Tracing}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {For almost two decades researchers have argued that ray tracing will eventually become faster than the rasterization technique that completely dominates todays graphics hardware. However, this has not happened yet. Ray tracing is still exclusively being used for off-line rendering of photorealistic images and it is commonly believed that ray tracing is simply too costly to ever challenge rasterization-based algorithms for interactive use. However, there is hardly any scientific analysis that supports either point of view. In particular there is no evidence of where the crossover point might be, at which ray tracing would eventually become faster, or if such a point does exist at all. This paper provides several contributions to this discussion: We first present a highly optimized implementation of a ray tracer that improves performance by more than an order of magnitude compared to currently available ray tracers. The new algorithm make better use of computational resources such as caches and SIMD instructions and better exploits image and object space coherence. Secondly, we show that this software implementation can challenge and even outperform high-end graphics hardware in interactive rendering performance for complex environments. We also provide an brief overview of the benefits of ray tracing over rasterization algorithms and point out the potential of interactive ray tracing both in hardware and software. }, } @article{Schirmacher:2001:OPO, author = {Hartmut Schirmacher and Li Ming and Hans-Peter Seidel}, title = {On-the-Fly Processing of Generalized Lumigraphs}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {We introduce a flexible and powerful concept for reconstructing arbitrary views from multiple source images on the fly. Our approach is based on a Lumigraph structure with per-pixel depth values, and generalizes the classical two-plane parameterized light fields and Lumigraphs. With our technique, it is possible to render arbitrary views of time-varying, non-diffuse scenes at interactive frame rates, and it allows using any kind of sensor that yields images with dense depth information. We demonstrate the flexibility and efficiency of our approach through various examples. }, } @article{Halper:2001:ACE, author = {Nicolas Halper and Ralf Helbing and Thomas Strothotte}, title = {A Camera Engine for Computer Games: Managing the Trade-Off Between Constraint Satisfaction and Frame Coherence}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Many computer games treat the user in the "1st person" and bind the camera to his or her view. More sophistication in a game can be achieved by enabling the camera to leave the users' viewpoint. This, however, requires new methods for automatic, dynamic camera control. In this paper we present methods and tools for such camera control. We emphasize guiding camera control by constraints; however, optimal constraint satisfaction tends to lead to the camera jumping around too much. Thus, we pay particular attention to a trade-off between constraint satisfaction and frame coherence. We present a new algorithm for dynamic consideration of the visibility of objects which are deemed to be important in a given game context. }, } @article{Freudenberg:2001:WIF, author = {Bert Freudenberg and Maic Masuch and Thomas Strothotte}, title = {Walk-Through Illustrations: Frame-Coherent Pen-and-Ink Style in a Game Engine}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {In this paper we show how a game engine designed to generate photorealistic images can be extended to produce non-photorealistic and hybrid renditions. We introduce new hardware-based methods to accomplish pen-and-ink illustrations. The combination of the highly optimized processing of a game engine and the use of hardware for {NPR} algorithms yields real-time animation of pen-and-ink illustrations. The particular advance of this method is that it yields the first real-time, frame-coherent pen-and-ink animations which maintain both tone and texture. }, } @article{Oshita:2001:ADM, author = {Masaki Oshita and Akifumi Makinouchi}, title = {A Dynamic Motion Control Technique for Human-like Articulated Figures}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {This paper presents a dynamic motion control technique for human-like articulated figures in a physically based character animation system. This method controls a figure such that the figure tracks input motion specified by a user. When environmental physical input such as an external force or a collision impulse are applied to the figure, this method generates dynamically changing motion in response to the physical input. We have introduced comfort and balance control to compute the angular acceleration of the figure's joints. Our algorithm controls the several parts of a human-like articulated figure separetely through the minimum number of degrees-of-freedom. Using this approach, our algorithm simulates realistic human motions at efficient computational cost. Unlike existing dynamic simulation systems, our method assumes that input motion is already realistic, and is aimed at dynamically changing the input motion in real-time only when unexpected physical input is applied to the figure. As such, our method works efficiently in the framework of current computer games. }, } @article{Gibson:2001:FIP, author = {Simon Gibson and Toby Howard and Roger Hubbold}, title = {Flexible Image-Based Photometric Reconstruction using Virtual Light Sources}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Photometric reconstruction is the process of estimating the illumination and surface reflectance properties of an environment, given a geometric model of the scene and a set of photographs of its surfaces. For mixed-reality applications, such data is required if synthetic objects are to be correctly illuminated or if synthetic light sources are to be used to re-light the scene. Current methods of estimating such data are limited in the practical situations in which they can be applied, due to the fact that the geometric and radiometric models of the scene which are provided by the user must be complete, and that the position (and in some cases, intensity) of the light sources must also be specified a-priori. In this paper, a novel algorithm is presented which overcomes these constraints, and allows photometric data to be reconstructed in less restricted situations. This is achieved through the use of virtual light sources which mimic the effect of direct illumination from unknown luminaires, and indirect illumination reflected off unknown geometry. The intensity of these virtual light sources and the surface material properties are estimated using an iterative algorithm which attempts to match calculated radiance values to those observed in photographs. Results are presented for both synthetic and real scenes that show the quality of the reconstructed data and its use in off-line mixed-reality applications. }, } @article{Shacked:2001:ALD, author = {Ram Shacked and Dani Lischinski}, title = {Automatic Lighting Design using a Perceptual Quality Metric}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Lighting has a crucial impact on the appearance of 3D objects and on the ability of an image to communicate information about a {3D} scene to a human observer. This paper presents a new automatic lighting design approach for comprehensible rendering of {3D} objects. Given a geometric model of a {3D} object or scene, the material properties of the surfaces in the model, and the desired viewing parameters, our approach automatically determines the values of various lighting parameters by optimizing a perception-based image quality objective function. This objective function is designed to quantify the extent to which an image of a {3D} scene succeeds in communicating scene information, such as the {3D} shapes of the objects, fine geometric details, and the spatial relationships between the objects. Our results demonstrate that the proposed approach is an effective lighting design tool, suitable for users without expertise or knowledge in visual perception or in lighting design. }, } @article{Ershov:2001:RPA, author = {Sergey Ershov and Konstantin Kolchin and Karol Myszkowski}, title = {Rendering Pearlescent Appearance Based On Paint-Composition Modelling}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {We describe a new approach to modelling pearlescent paints based on decomposing paint layers into stacks of imaginary thin sublayers. The sublayers are chosen so thin that multiple scattering can be considered across different sublayers, while it can be neglected within each of the sublayers. Based on this assumption, an efficient recursive procedure of assembling the layers is developed, which enables to compute the paint {BRDF} at interactive speeds. Since the proposed paint model connects fundamental optical properties of multi-layer pearlescent and metallic paints with their microscopic structure, interactive prediction of the paint appearance based on its composition becomes possible. }, } @article{Rose:2001:AIU, author = {Charles F. Rose {III} and Peter-Pike J. Sloan and Michael F. Cohen}, title = {Artist-Directed Inverse-Kinematics Using Radial Basis Function Interpolation}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {One of the most common tasks in computer animation is inverse-kinematics, or determining a joint configuration required to place a particular part of an articulated character at a particular location in global space. Inverse-kinematics is required at design-time to assist artists using commercial {3D} animation packages, for motion capture analysis, and for run-time applications such as games. We present an efficient inverse-kinematics methodology based on the interpolation of example motions and positions. The technique is demonstrated on a number of inverse-kinematics positioning tasks for a human figure. In addition to simple positioning tasks, the method provides complete motion sequences that satisfy an inverse-kinematic goal. The interpolation at the heart of the algorithm allows an artist's influence to play a major role in ensuring that the system always generates plausible results. Due to the lightweight nature of the algorithm, we can position a character at extremely high frame rates, making the technique useful for time-critical run-time applications such as games. }, } @article{Kitamura:2001:ICA, author = {Yoshifumi Kitamura and Tomohiko Higashi and Takayuki Iida and Fumio Kishino}, title = {Interactive Computer Animation of Hand Gestures using Status Estimation with Multiple Regression Analysis}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {This paper presents a method of interactively generating natural hand gesture animation using reduced dimensionality from multiple captured data sequences of finger motions conducting specific tasks. This method is achieved by introducing an estimation with multiple regression analysis. Even when the skeletal structure of the user who inputs the motion is different from that of the shape model in the computer, the motion that a user imagines is generated. Experimental results obtained from the interface applied to virtual object manipulation showed that the proposed method generates animation naturally, just as users would expect. This method enables us to make input devices that require minimal user training and computer calibration, and helps to make the user interface intuitive and easy to use. }, } @article{Vassilev:2001:FCA, author = {T. Vassilev and B. Spanlang and Y. Chrysanthou}, title = {Fast Cloth Animation on Walking Avatars}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {This paper describes a fast technique for animating clothing on walking humans. It exploits a mass-spring cloth model but applies a new velocity directional modification approach to overcome its super-elasticity. The algorithm for cloth-body collision detection and response is based on image-space interference tests, unlike the existing ones that use object-space checks. The modern workstations' graphics hardware is used not only to compute the depth maps of the body but also to interpolate the body normal vectors and velocities of each vertex. As a result the approach is very fast and makes it possible to produce animation at a rate of three to four frames per second. }, } @article{Granier:2001:IUF, author = {Xavier Granier and George Drettakis}, title = {Incremental Updates for Rapid Glossy Global Illumination}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, keywords = {Global Illumination, Rapid/Interactive Updates, Radiosity, Particle Tracing, Textures, Reconstruction}, annote = {We present an integrated global illumination algorithm including non-diffuse light transport which can handle complex scenes and enables rapid incremental updates. We build on a unified algorithm which uses hierarchical radiosity with clustering and particle tracing for diffuse and non-diffuse transport respectively. We present a new algorithm which chooses between reconstructing specular effects such as caustics on the diffuse radiosity mesh, or special purpose caustic textures, when high frequencies are present. Algorithms are presented to choose the resolution of these textures and to reconstruct the high-frequency non-diffuse lighting effects. We use a dynamic spatial data structure to restrict the number of particles re-emitted during the local modifications of the scene. By combining this incremental particle trace with a line-space hierarchy for incremental update of diffuse illumination, we can locally modify complex scenes rapidly. We also develop an algorithm which, by permitting slight quality degradation during motion, achieves quasi-interactive updates. We present an implementation of our new method and its application to indoors and outdoors scenes. }, } @article{Serpaggi:2001:AAM, author = {Xavier Serpaggi and Bernard P{\'{e}}roche}, title = {An Adaptive Method for Indirect Illumination Using Light Vectors}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = { }, } @article{Szirmay-Kalos:2001:GIA, author = {L{\'{a}}szl{\'{o}} Szirmay-Kalos and Ferenc Csonka and Gy{\"{o}}rgy Antal}, title = {Global Illumination as a Combination of Continuous Random Walk and Finite-Element Based Iteration}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {The paper introduces a global illumination method that combines continuous and finite-element approaches, preserving the speed of finite-element based iteration and the accuracy of continuous random walks. The basic idea is to decompose the radiance function to a finite-element component that is only a rough estimate and to a difference component that is obtained by Monte-Carlo techniques. Iteration and random walk are handled uniformly in the framework of stochastic iteration. This uniform treatment allows the finite-element component to be built up adaptively aiming at minimizing the Monte-Carlo component. The method is also suited for interactive walkthrough animation in glossy scenes since when the viewpoint changes, only the small Monte-Carlo component needs to be recomputed. }, } @article{Rocchini:2001:ALC, author = {C. Rocchini and Paulo Cignoni and C. Montani and P. Pingi and Roberto Scopigno}, title = {A low cost {3D} scanner based on structured light}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Automatic {3D} acquisition devices (often called {3D} scanners) allow to build highly accurate models of real {3D} objects in a cost- and time-effective manner. We have experimented this technology in a particular application context: the acquisition of Cultural Heritage artefacts. Specific needs of this domain are: medium-high accuracy, easy of use, affordable cost of the scanning device, self-registered acquisition of shape and color data, and finally operational safety for both the operator and the scanned artefacts. According to these requirements, we designed a low-cost {3D} scanner based on structured light which adopts a new, versatile colored stripe pattern approach. We present the scanner architecture, the software technologies adopted, and the first results of its use in a project regarding the {3D} acquisition of an archeological statue. }, } @article{Monzani:2001:IBA, author = {Jean-S{\'{e}}bastien Monzani and Angela Caicedo and Daniel Thalmann}, title = {Integrating Behavioural Animation Techniques}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, keywords = {behavioural animation and planning, virtual humans animation, inter-agents communication}, annote = {Our research focuses on animating autonomous virtual humans which are able to take decisions by themselves. We especially address in this paper the technical problem of integrating altogether the physical simulation of agents (represented as virtual humans in a {3D} environment) and their behaviours and motivations, driven by a Beliefs, Desires and Intentions architecture. We also explain how goals drive plans, and how an agent can coherently handle concurrent tasks. }, } @article{Hauth:2001:AHP, author = {Michael Hauth and Olaf Etzmuss}, title = {A High Performance Solver for the Animation of Deformable Objects using Advanced Numerical Methods}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Physically based modelling of deformable objects has become the most popular technique to model textiles, skin or human tissue. The crucial problem in the animation of deformable objects is the solution of the resulting differential equations. Recently fast solutions have been presented. In this work we will first give a theoretical analysis and then exploit special properties of the system and advanced numerical techniques to achieve further speed-ups of the simulations. Also, higher accuracy, leading to higher quality animations, will be achieved and an error bound is enforced. }, } @article{Hadap:2001:MDH, author = {Sunil Hadap and Nadia Magnenat-Thalmann}, title = {Modeling Dynamic Hair as a Continuum}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {In this paper we address the difficult problem of hair dynamics, particularly hair-hair and hair-air interactions. To model these interactions, we propose to consider hair volume as a continuum. Subsequently, we treat the interaction dynamics to be fluid dynamics. This proves to be a strong as well as viable approach for an otherwise very complex phenomenon. However, we retain the individual character of hair, which is vital to visually realistic rendering of hair animation. For that, we develop an elaborate model for stiffness and inertial dynamics of individual hair strand. Being a reduced coordinate formulation, the stiffness dynamics is numerically stable and fast. We then unify the continuum interaction dynamics and the individual hair's stiffness dynamics. }, } @article{Reissell:2001:MSD, author = {L. M. Reissell and Dinesh K. Pai}, title = {Modeling Stochastic Dynamical Systems for Interactive Simulation}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {We present techniques for constructing approximate stochastic models of complicated dynamical systems for applications in interactive computer graphics. The models are designed to produce realistic interaction at low cost. We describe two kinds of stochastic models: continuous state (ARX) models and discrete state (Markov chains) models. System identi cation techniques are used for learning the input-output dynamics automatically, from either measurements of a real system or from an accurate simulation. The synthesis of behavior in this manner is several orders of magnitude faster than physical simulation.We demonstrate the techniques with two examples: (1) the dynamics of candle ame in the wind, modeled using data from a real candle and (2) the motion of a falling leaf, modeled using data from a complex simulation. We have implemented an interactive Java program which demonstrates real-time interaction with a realistically behaving simulation of a cartoon candle ame. The user makes the ame animation icker by blowing into a microphone. }, } @article{Wu:2001:ANF, author = {Xunlei Wu and Michael S. Downes and Tolga Goktekin and Frank Tendick}, title = {Adaptive Nonlinear Finite Elements for Deformable Body Simulation Using Dynamic Progressive Meshes}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Realistic behavior of deformable objects is essential for many applications such as simulation for surgical training. Existing techniques of deformable modeling for real time simulation have either used approximate methods that are not physically accurate or linear methods that do not produce reasonable global behavior. Nonlinear finite element methods (FEM) are globally accurate, but conventional {FEM} is not real time. In this paper, we apply nonlinear {FEM} using mass lumping to produce a diagonal mass matrix that allows real time computation. Adaptive meshing is necessary to provide sufficient detail where required while minimizing unnecessary computation. We propose a scheme for mesh adaptation based on an extension of the progressive mesh concept, which we call dynamic progressive meshes. }, } @article{Tanaka:2001:GSS, author = {Satoshi Tanaka and Akihiro Shibata and Hiroaki Yamamoto and Hisakiyo Kotsuru}, title = {Generalized Stochastic Sampling Method for Visualization and Investigation of Implicit Surfaces}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Recently we proposed the stochastic sampling method (SSM), which can numerically generate sample points on complicated implicit surfaces quickly and uniformly. In this paper we generalize the method in two aspects: (1) We introduce two kinds of boundary conditions, so that we can sample a finite part of an open surface spreading infinitely. (2) We generalize the stochastic differential equation used in the {SSM}, so that its solutions can satisfy plural constraint conditions simultaneously. The first generalization enables us to visualize cut views of open surfaces. The second generalization enables us to visualize intersections of static and moving implicit surfaces, which leads to detailed investigation of intersections and other interesting applications such as visualization of contour maps. }, } @article{Ohtake:2001:MOF, author = {Yutaka Ohtake and Alexander G. Belyaev}, title = {Mesh Optimization for Polygonized Isosurfaces}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {In this paper, we propose a method for improvement of isosurface polygonizations. Given an initial polygonization of an isosurface, we introduce a mesh evolution process initialized by the polygonization. The evolving mesh converges quickly to its limit mesh which provides with a high quality approximation of the isosurface even if the isosurface has sharp features, boundary, complex topology. To analyze how close the evolving mesh approaches its destined isosurface, we introduce error estimators measuring the deviations of the mesh vertices from the isosurface and mesh normals from the isosurface normals. A new technique for mesh editing with isosurfaces is also proposed. In particular, it can be used for creating carving effects. }, } @article{Mora:2001:VOI, author = {B. Mora and J. P. Jessel and R. Caubet}, title = {Visualization of Isosurfaces with Parametric Cubes}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, keywords = {isosurface, reconstruction filter, octree, quantization}, annote = {To render images from volume datasets, an interpolation method also called reconstruction is needed. The level of details of the resultant image closely depends on the filter used for reconstruction. We propose here a new filter producing C1 continue surfaces. The provided image quality is better than current high-quality algorithms, like splatting or trilinear raycasting, where tiny details are often eliminated. In contrast with other studied high quality filters that are practically unusable, our algorithm has been implemented interactively on a modest platform thanks to an efficient implementation using parametric cubes. We also demonstrate the interest of a min-max octree in the visualization of isosurfaces interactively thresholded. }, } @article{Watanabe:2001:DOS, author = {Kouki Watanabe and Alexander G. Belyaev}, title = {Detection of Salient Curvature Features on Polygonal Surfaces}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {We develop an approach for stable detection of perceptually salient curvature features on surfaces approximated by dense triangle meshes. The approach explores an "area degenerating" effect of the focal surface near its singularities and combines together a new approximations of the mean and Gaussian curvatures, nonlinear averaging of curvature maps, histogram-based curvature extrema filtering, and an image processing skeletonization procedure adapted for triangular meshes. Finally we use perceptually significant curvature extrema triangles to enhance the Garland-Heckbert mesh decimation method. }, } @article{Vorsatz:2001:FSR, author = {J. Vorsatz and C. R{\"{o}}ssl and Leif P. Kobbelt and Hans-Peter Seidel}, title = {Feature Sensitive Remeshing}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Remeshing artifacts are a fundamental problem when converting a given geometry into a triangle mesh. We propose a new remeshing technique that is sensitive to features. First, the resolution of the mesh is iteratively adapted by a global restructuring process which additionally optimizes the connectivity. Then a particle system approach evenly distributes the vertices across the original geometry. To exactly find the features we extend this relaxation procedure by an effective mechanism to attract the vertices to feature edges. The attracting force is imposed by means of a hierarchical curvature field and does not require any thresholding parameters to classify the features. }, } @article{Botsch:2001:RFA, author = {Mario Botsch and Leif P. Kobbelt}, title = {Resampling Feature and Blend Regions in Polygonal Meshes for Surface Anti-Aliasing}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Efficient surface reconstruction and reverse engineering techniques are usually based on a polygonal mesh representation of the geometry: the resulting models emerge from piecewise linear interpolation of a set of sample points. The quality of the reconstruction not only depends on the number and density of the sample points but also on their alignment to sharp and rounded features of the original geometry. Bad alignment can lead to severe alias artifacts. In this paper we present a sampling pattern for feature and blend regions which minimizes these alias errors. We show how to improve the quality of a given polygonal mesh model by resampling its feature and blend regions within an interactive framework. We further demonstrate sophisticated modeling operations that can be implemented based on this resampling technique. }, } @article{Wonka:2001:IV, author = {Peter Wonka and Michael Wimmer and Fran{\c{c}}ois X. Sillion}, title = {Instant Visibility}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {We present an online occlusion culling system which computes visibility in parallel to the rendering pipeline. We show how to use point visibility algorithms to quickly calculate a tight potentially visible set (PVS) which is valid for several frames, by shrinking the occluders used in visibility calculations by an adequate amount. These visibility calculations can be performed on a visibility server, possibly a distinct computer communicating with the display host over a local network. The resulting system essentially combines the advantages of online visibility processing and region-based visibility calculations, allowing asynchronous processing of visibility and display operations. We analyze two different types of hardware-based point visibility algorithms and address the problem of bounded calculation time which is the basis for true real-time behavior. Our results show reliable, sustained 60 Hz performance in a walkthrough with an urban environment of nearly 2 million polygons, and a terrain flyover. }, } @article{Roth:2001:RTT, author = {S. H. Martin Roth and Patrick Diezi and Markus H. Gross}, title = {Ray Tracing Triangular B{\'{e}}zier Patches}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {We present a new approach to finding ray-patch intersections with triangular Bernstein-B{\'{e}}zier patches of arbitrary degree. This paper extends and complements on the short presentation. Unlike a previous approach which was based on a combination of hierarchical subdivision and a Newton-like iteration scheme, this work adapts the concept of B{\'{e}}zier clipping to the triangular domain. The problem of reporting wrong intersections, inherent to the original B{\'{e}}zier clipping algorithm, is investigated and opposed to the triangular case. It turns out that reporting wrong hits is very improbable, even close to impossible, in the triangular set-up. A combination of B{\'{e}}zier clipping and a simple hierarchy of nested bounding volumes offers a reliable and accurate solution to the problem of ray tracing triangular B{\'{e}}zier patches. }, } @article{Brunet:2001:H3C, author = {Pere Brunet and Isabel Navazo and Jarek Rossignac and Carlos Saona-V{\'{a}}zquez}, title = {Hoops: {3D} Curves as Conservative Occluders for Cell-Visibility}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Most visibility culling algorithms require convexity of occluders. Occluder synthesis algorithms attempt to construct large convex occluders inside bulky non-convex sets. Occluder fusion algorithms generate convex occluders that are contained in the umbra cast by a group of objects given an area light. In this paper we prove that convexity requirements can be shifted from the occluders to their umbra with no loss of efficiency, and use this property to show how some special non-planar, non-convex closed polylines that we call "hoops" can be used to compute occlusion efficiently for objects that have no large interior convex sets and were thus rejected by previous approaches. }, } @article{Westermann:2001:RVD, author = {R{\"{u}}diger Westermann and Christof Rezk-Salama}, title = {Real-Time Volume Deformations}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Real-time free-form deformation tools are primarily based on surface or particle representations to allow for interactive modification and fast rendering of complex models. The efficient handling of volumetric representations, however, is still a challenge and has not yet been addressed sufficiently. Volumetric models, on the other hand, form an important class of representation in many applications. In this paper we present a novel approach to the real-time deformation of scalar volume data sets taking advantage of hardware supported {3D} texture mapping. In a prototype implementation a modeling environment has been designed that allows for interactive manipulation of arbitrary parts of volumetric objects. In this way, any desired shape can be modeled and used subsequently in various applications. The underlying algorithms have wide applicability and can be exploited effectively for volume morphing and medical data processing. }, } @article{Csebfalvi:2001:FVO, author = {Bal{\'{a}}zs Cs{\'{e}}bfalvi and Lukas Mroz and Helwig Hauser and Andreas K{\"{o}}nig and Eduard Gr{\"{o}}ller}, title = {Fast Visualization of Object Contours by Non-Photorealistic Volume Rendering}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, keywords = {interactive volume rendering, non-photorealistic rendering, shear-warp projection}, annote = {In this paper we present a fast visualization technique for volumetric data, which is based on a recent non-photorealistic rendering technique. Our new approach enables alternative insights into {3D} data sets (compared to traditional approaches such as direct volume rendering or iso-surface rendering). Object contours, which usually are characterized by locally high gradient values, are visualized regardless of their density values. Cumbersome tuning of transfer functions, as usually needed for setting up {DVR} views is avoided. Instead, a small number of parameters is available to adjust the non-photorealistic display. Based on the magnitude of local gradient information as well as on the angle between viewing direction and gradient vector, data values are mapped to visual properties (color, opacity), which then are combined to form the rendered image (MIP is proposed as the default compositing stragtegy here). Due to the fast implementation of this alternative rendering approach, it is possible to interactively investigate the {3D} data, and quickly learn about internal structures. Several further extensions of our new approach, such as level lines are also presented in this paper. }, } @article{Tricoche:2001:TTT, author = {X. Tricoche and G. Scheuermann and Hans Hagen}, title = {Tensor Topology Tracking: A Visualization Method for Time-Dependent {2D} Symmetric Tensor Fields}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Topological methods produce simple and meaningful depictions of symmetric, second order two-dimensional tensor fields. Extending previous work dealing with vector fields, we propose here a scheme for the visualization of time-dependent tensor fields. Basic notions of unsteady tensor topology are discussed. Topological changes - known as bifurcations - are precisely detected and identified by our method which permits an accurate tracking of degenerate points and related structures. }, } @article{Maillot:200:AUS, author = {J{\'{e}}r{\^{o}}me Maillot and Jos Stam}, title = {A Unified Subdivision Scheme for Polygonal Modeling}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Subdivision rules have traditionally been designed to generate smooth surfaces from polygonal meshes. In this paper we propose to employ subdivision rules as a polygonal modeling tool, specifically to add additional level of detail to meshes. However, existing subdivision schemes have several undesirable properties making them ill suited for polygonal modeling. In this paper we propose a general set of subdivision rules which provides users with more control over the subdivision process. Most existing subdivision schemes are special cases. In particular, we provide subdivision rules which blend approximating spline based schemes with interpolatory ones. Also, we generalize subdivision to allow any number of refinements to be performed in a single step. }, } @article{Alliez:2001:VCE, author = {Pierre Alliez and Mathieu Desbrun}, title = {Valence-Driven Connectivity Encoding for {3D} Meshes}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {In this paper, we propose a valence-driven, single-resolution encoding technique for lossless compression of triangle mesh connectivity. Building upon a valence-based approach pioneered by Touma and Gotsman, we design a new valence-driven conquest for arbitrary meshes that always guarantees smaller compression rates than the original method. Furthermore, we provide a novel theoretical entropy study of our technique, hinting the optimality of the valence-driven approach. Finally, we demonstrate the practical efficiency of this approach (in agreement with the theoretical prediction) on a series of test meshes, resulting in the lowest compression ratios published so far, for both irregular and regular meshes, small or large. }, } @article{Boissonnat:2001:CSS, author = {Jean-Daniel Boissonnat and Fr{\'{e}}d{\'{e}}ric Cazals}, title = {Coarse-to-fine surface simplification with geometric guarantees}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Let {PC} be a {3D} point cloud and "epsilon" be a positive value called tolerance. We aim at constructing a triangulated surface S based on a subset {PCU} of {PC} such that all the points in {PCL} = PC\PCU are at distance at most "epsilon" from a facet of S. (PCU and {PCL} respectively stand for Point Cloud Used and Point Cloud Left.) We call this problem simplification with geometric guarantees. This paper presents a new framework to simplify with geometric guarantees. The approach relies on two main ingredients. First an oracle providing information on the surface being reconstructed even though the triangulated surface itself has not been computed. Second, a reconstruction algorithm providing incremental updates of the reconstructed surface, as well as a fast point-to-triangles distance computation. The oracle is used to guess a subset of the point cloud from which a triangulated surface is reconstructed. It relies on an implicit surface the triangulated surface is an approximation of, and is therefore available before the triangle mesh. The point-to-triangles distance computation and the local updates are then invoked to insert new vertices until the tolerance is met. We also present a detailed experimental study which shows the efficiency of the simplification process both in terms of simplification rate and running time. To the best of our knowledge, this algorithm is the first one performing coarse-to-fine surface simplification with geometric guarantees. }, } @article{Ehmann:2001:AAF, author = {Stephan A. Ehmann}, title = {Accurate and Fast Proximity Queries Between Polyhedra Using Convex Surface Decomposition}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, pages = {Ming C. Lin}, note = {{ISSN} 1067-7055}, annote = {The need to perform fast and accurate proximity queries arises frequently in physically-based modeling, simulation, animation, real-time interaction within a virtual environment, and game dynamics. The set of proximity queries include intersection detection, tolerance verification, exact and approximate minimum distance computation, and (disjoint) contact determination. Specialized data structures and algorithms have often been designed to perform each type of query separately. We present a unified approach to perform any of these queries seamlessly for general, rigid polyhedral objects with boundary representations which are orientable 2-manifolds. The proposed method involves a hierarchical data structure built upon a surface decomposition of the models. Furthermore, the incremental query algorithm takes advantage of coherence between successive frames. It has been applied to complex benchmarks and compares very favorably with earlier algorithms and systems. }, } @article{Ivanov:2001:SPA , author = {D. Ivanov and Ye Kuzmin}, title = {Spatial Patches - A Primitive for {3D} Model Representation}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {The commonly used solution for real-life {3D} model representation is polygonal spatially consistent geometry, with texture, and, optionally, bump or displacement maps attached. Although the idea of displacement mapping is well known, there are just a few approaches to its efficient implementation. In this paper we develop a technique that allows for efficient representation and rendering of {3D} models by getting a new angle on the displacement mapping concept. We introduce a new primitive that is defined as the range image of a small part of the model's surface; therefore, it is called a spatial patch. The whole model is just a collection of patches with no connectivity information between them. Such a representation can be directly acquired by 3D scanning machinery, and stored in a compact uniform form. It also allows for efficient visualization, which is the major focus of this paper. Thus, we present the logical structure of a rendering unit based on conventional z-buffering, and discuss the involved algorithms in detail. These algorithms benefit from modern features of computing units for which we believe the proposed technique can be used in a wide range of applications dealing with real-life {3D} data. }, } @article{Gross:2001:APT, author = {Markus Gross}, title = {Are Points the Better Graphics Primitives?}, volume = {20}, number = {3}, journal = {Computer Graphics Forum}, year = {2001}, publisher = {Blackwell Publishers}, note = {{ISSN} 1067-7055}, annote = {Since the early days of graphics the computer based representation of three-dimensional geometry has been one of the core research fields. Today, various sophisticated geometric modelling techniques including {NURBS} or implicit surfaces allow the creation of {3D} graphics models with increasingly complex shape. In spite of these methods the triangle has survived over decades as the king of graphics primitives meeting the right balance between descriptive power and computational burden. As a consequence, today's consumer graphics hardware is heavily tailored for high performance triangle processing. In addition, a new generation of geometry processing methods including hierarchical representations, geometric filtering, or feature detection fosters the concept of triangle meshes for graphics modelling. Unlike triangles, points have amazingly been neglected as a graphics primitive. Although being included in APIs since many years, it is only recently that point samples experience a renaissance in computer graphics. Conceptually, points provide a mere discretization of geometry without explicit storage of topology. Thus, point samples reduce the representation to the essentials needed for rendering and enable us to generate highly optimized object representations. Although the loss of topology poses great challenges for graphics processing, the latest generation of algorithms features high performance rendering, point/pixel shading, anisotropic texture mapping, and advanced signal processing of point sampled geometry. This talk will give an overview of how recent research results in the processing of triangles and points are changing our traditional way of thinking of surface representations in computer graphics - and will discuss the question: Are Points the Better Graphics Primitives? }, }