%%%% -*-BibTeX-*- %%% ==================================================================== %%% BibTeX-file{ %%% author = "Nelson H. F. Beebe", %%% version = "1.17", %%% date = "23 August 2006", %%% time = "07:43:48 MDT", %%% filename = "jgraphtools.bib", %%% address = "University of Utah %%% Department of Mathematics, 110 LCB %%% 155 S 1400 E RM 233 %%% Salt Lake City, UT 84112-0090 %%% USA", %%% telephone = "+1 801 581 5254", %%% FAX = "+1 801 581 4148", %%% URL = "http://www.math.utah.edu/~beebe", %%% checksum = "64360 5000 24637 227234", %%% email = "beebe at math.utah.edu, beebe at acm.org, %%% beebe at computer.org (Internet)", %%% codetable = "ISO/ASCII", %%% keywords = "bibliography, BibTeX, Journal of Graphics %%% Tools: JGT", %%% license = "public domain", %%% supported = "yes", %%% docstring = "This is a COMPLETE bibliography of the %%% quarterly Journal of Graphics Tools: JGT %%% (CODEN JGTOFD, ISSN 1086-7651), which began %%% with volume 1, number 1, in 1996. The %%% journal is published by %%% %%% A K Peters, Ltd. %%% 289 Linden Street, %%% Wellesley, MA 02181 %%% USA %%% Phone: +1 617 235 2210 %%% Fax: +1 617 235 2404 %%% Email: akpeters at tiac.net %%% %%% and has World-Wide Web sites at %%% %%% http://www.acm.org/jgt/ %%% http://jgt.akpeters.com/ %%% %%% where abstracts to individual articles may %%% be found. Uniform Resource Locator (URL) %%% values in the bibliography entries below %%% point to those abstracts. %%% %%% At version 1.17, the (complete) year coverage %%% looked like this: %%% %%% 1996 ( 15) 2000 ( 16) 2004 ( 15) %%% 1997 ( 16) 2001 ( 14) 2005 ( 25) %%% 1998 ( 13) 2002 ( 30) 2006 ( 11) %%% 1999 ( 18) 2003 ( 16) %%% %%% Article: 189 %%% %%% Total entries: 189 %%% %%% Entries in this bibliography are derived %%% primarily from information at the journal's %%% Web site, because the journal is not %%% covered by major article databases, such as %%% Compendex, IEEE INSPEC, OCLC Contents1st, %%% or UnCover, nor is the journal available at %%% the University of Utah Marriott Library. %%% %%% In this bibliography, entries are sorted in %%% publication order, using bibsort -byvolume. %%% %%% The checksum field above contains a CRC-16 %%% checksum as the first value, followed by the %%% equivalent of the standard UNIX wc (word %%% count) utility output of lines, words, and %%% characters. This is produced by Robert %%% Solovay's checksum utility.", %%% } %%% ==================================================================== @Preamble{ "\input path.sty" # "\ifx \undefined \TM \def \TM {${}^{\sc TM}$} \fi" # "\hyphenation{ Kuz-i-ora } " } %%% ==================================================================== %%% Acknowledgement abbreviations: @String{ack-nhfb = "Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|"} %%% ==================================================================== %%% Journal abbreviations: @String{j-J-GRAPHICS-TOOLS = "Journal of Graphics Tools: JGT"} %%% ==================================================================== %%% Bibliography entries: @Article{Smith:1996:HMI, author = "Alvy Ray Smith and Eric Ray Lyons", title = "{HWB}: {A} more intuitive hue-based color model", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "1", pages = "3--17", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/SmithLyons96/", abstract = "The two most common color selector models, other than RGB (Red-Green-Blue), are the hue-based HSV (Hue-Saturation-Value) and HSL (Hue-Saturation-Lightness) color models. It is shown that both of these models are flawed. A closely related model, HWB (Hue-Whiteness-Blackness), is introduced that avoids the flaws, is slightly faster to compute, and is very easy to teach to new users: Choose a hue. Lighten it with white. Darken it with black. We explain that lightening is not the opposite of darkening.", acknowledgement = ack-nhfb, } @Article{Bigos:1996:ABC, author = "Andrew Bigos", title = "Avoiding buffer clears", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "1", pages = "19--20", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Bigos96/", abstract = "A trick to avoid clearing a depth buffer between frames of an animation.", acknowledgement = ack-nhfb, } @Article{Goldsmith:1996:MCC, author = "Jeff Goldsmith and Allan S. Jacobson", title = "Marching cubes in cylindrical and spherical coordinates", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "1", pages = "21--32", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/GoldsmithJacobson96/", abstract = "Isosurface extraction is a common analysis and visualization technique for three-dimensional scalar data. Marching Cubes is the most commonly-used algorithm for finding polygonal representations of isosurfaces in such data. We extend Marching Cubes to produce geometry for data sets that lie in spherical and cylindrical coordinate systems as well as show the steps for derivation of transformations for other coordinate systems. Such data sets are very common in the physical sciences, and display within their natural coordinate system aids visualization considerably.", acknowledgement = ack-nhfb, } @Article{Hubbard:1996:IAR, author = "Philip M. Hubbard", title = "Improving accuracy in a robust algorithm for {$3$D Voronoi} diagrams", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "1", pages = "33--45", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Hubbard96/", abstract = "This paper describes extensions to a previous algorithm that robustly builds three-dimensional Voronoi diagrams in the presence of inexact numerical computations. The extensions improve the algorithm's accuracy, making its results more nearly represent the proximity properties of an ideal Voronoi diagram. In empirical tests, these extensions ahve improved accuracy by more than eight orders of magnitude. Complete pseudocode for the algorithm appears in an appendix of this paper.", acknowledgement = ack-nhfb, } @Article{Cignoni:1996:TCP, author = "P. Cignoni and C. Montani and R. Scopigno", title = "Triangulating convex polygons having ${T}$-vertices", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "2", pages = "1--4", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/CignoniMontaniScopigno96/", abstract = "A technique to triangulate planar convex polygons having T-vertices is described. Simple strip or fan tessellation of a polygon with T-vertices can result in zero-area triangles and compromise the rendering process. Our technique splits such a polygon into one triangle strip and, at most, one triangle fan. The technique is particularly useful in multiresolution or adaptive representation of polygonal surfaces and the simplification of surfaces.", acknowledgement = ack-nhfb, } @Article{Velho:1996:SEP, author = "Luiz Velho", title = "Simple and efficient polygonization of implicit surfaces", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "2", pages = "5--24", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Velho96/", abstract = "This paper describes a simple and efficient polygonization algorithm that gives a practical way to construct adapted piecewise linear representations of implicit surfaces. The method starts with a coarse uniform polygonal approximation of the surface and subdivides each polygon recursively according to local curvature. In that way, the inherent complexity of the problem is tamed by separating structuring from sampling and reducing part of the full three dimensional search to two dimensions.", acknowledgement = ack-nhfb, } @Article{vanOverveld:1996:HSH, author = "C. W. A. M. {van Overveld} and Brian Wyvill", title = "Hi-speed, hi-fi hi-lights: a fast algorithm for the specular term in the {Phong} illumination model", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "2", pages = "25--30", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/vanOverVeldWyvill96/", abstract = "The computational effort to render images with light sources and camera at infinity is less than with light sources at finite distance from the illuminated surface. On the other hand, in the case of an infinitely remote light source and camera, planar polygons don't receive highlights. In this paper, a method is suggested to use the (relatively cheap) infinite-distance model instead of the expensive finite-distance model for the computation of highlights. It works by replacing a light source at finite distance by a light source at infinite distance, and at the same time adjusting the normal vectors in such a way that the resulting illumination pattern stays the same. With these modifications, a simple table look-up comes in the place of an expensive computation to obtain the specular term in the standard illumination model.", acknowledgement = ack-nhfb, } @Article{Mirtich:1996:FAC, author = "Brian Mirtich", title = "Fast and accurate computation of polyhedral mass properties", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "2", pages = "31--50", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Mirtich96/; http://www.cs.berkeley.edu/~mirtich/massProps.html", abstract = "The location of a body's center of mass, and its moments and products of inertia about various axes are important physical quantities needed for any type of dynamic simulation or physically based modeling. We present an algorithm for automatically computing these quantities for a general class of rigid bodies: those composed of uniform density polyhedra. The mass integrals may be converted into volume integrals under these assumptions, and the bulk of the paper is devoted to the computation of these volume integrals. Our algorithm is based on a three step reduction of the volume integrals to successively simpler integrals. The algorithm is designed to minimize the numerical errors that can result from poorly conditioned alignment of polyhedral faces. It is also designed for efficiency. All required volume integrals of a polyhedron are computed together during a single walk over the boundary of the polyhedron; exploiting common subexpressions reduces floating point operations. We present numerical results detailing the speed and accuracy of the algorithm, and also give a complete low level pseudocode description.", acknowledgement = ack-nhfb, } @Article{Haines:1996:FLM, author = "Eric Haines and Steven Worley", title = "Fast, Low Memory ${Z}$-Buffering when Performing Medium-Quality Rendering", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "3", pages = "1--5", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/HainesWorley96/", abstract = "This article presents algorithms which both improve performance and decrease memory costs when using a Z-buffer for medium-quality rendering. The crux of the method is to perform rendering in two passes; the first quickly renders only Z-depth values, the second does all shading calculations. This method allows the reuse of memory used to store the Z-depths and colors, as only one of these two values is needed at any given moment for any given pixel. It also eliminates all unnecessary shading/shadowing/texturing calls, which typically take the majority of computation time in medium-quality algorithms.", acknowledgement = ack-nhfb, } @Article{Hutchinson:1996:RVI, author = "Dave Hutchinson and Terry Hewitt", title = "Rapidly Visualizing Isophotes", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "3", pages = "7--12", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/HutchinsonHewitt96/", abstract = "For computer aided design it is often necessary to identify regions of unwanted curvature in a surface. Isophotes can be used to detect first- and second-order discontinuities in a surface. This paper describes a method to visualize isophotes using existing hardware or software display and false colour capabilities. This method is faster and easier to implement than the traditional approach of explicitly computing isophotes.", acknowledgement = ack-nhfb, } @Article{vanOverveld:1996:BBB, author = "C. W. A. M. {van Overveld} and Brian Wyvill", title = "Banishing bad buckling", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "3", pages = "13--28", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/vanOverVeldWyvill96b/; http://www.win.tue.nl/win/cs/tt/kees/PAPERS_PS/b_buckl.ps.gz", abstract = "An algorithm is presented which can be used to alleviate shape artifacts (buckling) that occur with interpolating spline curves or interpolating spline surfaces. The algorithm consists of applying small displacements to some of the vertices that are interpolated. It is based on a quantitative measure for the amount of buckling, and a relaxation method to reduce this amount.", acknowledgement = ack-nhfb, } @Article{Gritz:1996:BGI, author = "Larry Gritz and James K. Hahn", title = "{BMRT}: {A} global illumination implementation of the {RenderMan} standard", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "3", pages = "29--47", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/GritzHahn96/", abstract = "The RenderMan Interface specification proposed by Pixar is a standard for communication between modeling software and rendering software or devices. This standard has proven very powerful and is extremely popular in production work. Although the standard itself claims not to specify a rendering algorithm, people have speculated RenderMan and global illumination are mutually incompatible.\par We have implemented a rendering system which fully adheres to the RenderMan Interface and uses global illumination algorithms. Specifically, this implementation supports progressive refinement radiosity and distribution ray tracing in a two-pass approach. This rendering system is widely distributed, very popular, and has been used in production (three properties usually not found in global illumination renderers). We discuss how we overcame problems in mating global illumination algorithms with the RenderMan standard, and make recommendations for future versions of the standard to better accommodate such algorithms. We also present a summary of important lessons we learned by creating and distributing this tool.", acknowledgement = ack-nhfb, } @Article{Nelson:1996:TCC, author = "Scott R. Nelson", title = "Twelve characteristics of correct antialiased lines", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "4", pages = "1--20", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Nelson96/", abstract = "Many papers have been written on line antialiasing algorithms. Most ignore important features that can leave visible artifacts. This paper presents twelve desirable characteristics of antialiased lines and discusses algorithmic tradeoffs that affect each of the characteristics from a behavioral perspective. Accompanying color images show the differences between acceptable and unacceptable behavior for each characteristic. This paper provides the information needed to visibly analyze how well a particular antialiased line algorithm works.", acknowledgement = ack-nhfb, } @Article{Ranjan:1996:CUS, author = "Vishwa Ranjan and Alain Fournier", title = "Creating union of spheres models from multiple views", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "4", pages = "21--39", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/RanjanFournier96/", abstract = "In this paper, we present a method to obtain a {\em union of spheres (UoS)\/} model of an object by integrating the information obtained from different views, each view created by point-sampling of the visible surface of the object. The boundary points can be obtained from multiple range-finder images, or by ray-tracing a model of the object (if available in a ray-traceable form) from different views. The algorithm consists of two parts: construction and simplification. The construction method is based on the Delaunay tetrahedralization of points in three dimensions and uses the half-space constraints imposed by the visibility directions of boundary points. The simplification method is based on the concept of {\em sphericity}. Sphericity is a quantity that measures how well a set of spheres is approximated by a single sphere. This allows us to reduce the number of primitives in a controlled way, while keeping the union of spheres model. It can also be used to stabilize the union of spheres model, i.e., to make it independent of the noise in the samples or other small distortions in the data. Several examples illustrate the algorithm.", acknowledgement = ack-nhfb, } @Article{Sherstyuk:1996:RTS, author = "Andrei Sherstyuk", title = "Ray tracing with selective visibility", journal = j-J-GRAPHICS-TOOLS, volume = "1", number = "4", pages = "41--46", year = "1996", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Sherstyuk96/", abstract = "We propose a simple yet effective extension of the ray-tracing algorithm that allows selective visibility of objects for specific rays. Typically, rays are classified as pixel, shadow, reflected, and transmitted. We suggest adding to material descriptions a visibility mask which controls how these rays interact with the material. This addition can be incorporated seamlessly into any ray tracer and may help to generate visually interesting images.", acknowledgement = ack-nhfb, } @Article{Barzel:1997:LCC, author = "Ronen Barzel", title = "Lighting Controls for Computer Cinematography", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "1", pages = "1--20", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Barzel97/", abstract = "Lighting is an essential component of visually rich cinematographic images. However, the common computer graphics light source models, such as a cone-shaped spotlight, are not versatile enough for cinematographic-quality lighting. In this paper we describe the controls and features of a light source model for lighting computer graphics films. The model is based on generalized light cones, emphasizing independent control over the shape and texture of lights and shadows. While inspired by techniques of real-world cinematography, it is tailored to the needs and capabilities of computer graphics. The model has been used successfully in production over the past few years, to light many short works and the movie {\em Toy Story}.", acknowledgement = ack-nhfb, } @Article{Moller:1997:FMS, author = "Tomas M{\"o}ller and Ben Trumbore", title = "Fast, Minimum Storage Ray-Triangle Intersection", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "1", pages = "21--28", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/MollerTrumbore97/", abstract = "We present a clean algorithm for determining whether a ray intersects a triangle. The algorithm translates the origin of the ray and then changes the base to yield a vector $(t u v)^{\tt T}$, where $t$ is the distance to the plane in which the triangle lies and $(u,v)$ represents the coordinates inside the triangle.", acknowledgement = ack-nhfb, } @Article{Nelson:1997:HQH, author = "Scott R. Nelson", title = "High quality hardware line antialiasing", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "1", pages = "29--46", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Nelson97/", abstract = "The graphics community has understood line antialiasing reasonably well for many years. Many papers have been written on the subject, but none of them have offered a complete solution. This paper explains all of the details of a well behaved hardware algorithm used in the SparcStation ZX that, although imperfect, works very well in practice. The paper discusses tradeoffs at each point and the reasoning that went into the decisions that were made.", acknowledgement = ack-nhfb, } @Article{Telea:1997:COB, author = "A. C. Telea and C. W. A. M. van Overveld", title = "The Close Objects Buffer: {A} Sharp Shadow Detection Technique for Radiosity Methods", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "2", pages = "1--8", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/TeleaVanOverveld97/", abstract = "Detecting sharp illumination variations such as shadow boundaries is an important problem for radiosity methods. Such illumination variations are captured using a nonuniform mesh that refines the areas exhibiting high illumination gradients. Nonuniform meshing techniques like discontinuity meshing often rely on shadow casting, and as a result their application is computationally expensive. This paper presents a sharp shadow detection technique for radiosity tools based on the progressive refinement method. The presented technique offers good results (especially for capturing sharp shadows cast by small `detail' objects), is very simple to implement, has negligible time and space requirements, and integrates well with other adaptive subdivision strategies in a radiosity tool based on progressive refinement.", acknowledgement = ack-nhfb, } @Article{Wong:1997:SHH, author = "Tien-Tsin Wong and Wai-Shing Luk and Pheng-Ann Heng", title = "Sampling with {Hammersley} and {Halton} Points", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "2", pages = "9--24", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/WongLukHeng97/", abstract = "The Hammersley and Halton point sets, two well known low discrepancy sequences, have been used for quasi-Monte Carlo integration in previous research. A deterministic formula generates a uniformly distributed and stochastic-looking sampling pattern, at low computational cost. The Halton point set is also useful for incremental sampling. In this paper, we discuss detailed implementation issues and our experience of choosing suitable bases of the point sets, not just on the $2$D plane, but also on a spherical surface. The sampling scheme is also applied to ray tracing, with a significant improvement in error.", acknowledgement = ack-nhfb, } @Article{Moller:1997:FTT, author = "Tomas M{\"o}ller", title = "A Fast Triangle-Triangle Intersection Test", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "2", pages = "25--30", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Moller97/", abstract = "This paper presents a method, along with some optimizations, for computing whether or not two triangles intersect. The code, which is shown to be fast, can be used, for example, in collision detection algorithms.", acknowledgement = ack-nhfb, } @Article{Chung:1997:RRS, author = "A. J. Chung and A. J. Field", title = "Rendering Radiosity Solutions by Adaptive Gathering", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "2", pages = "31--44", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/ChungField97/", abstract = "The radiosity method is a finite element global illumination technique that usually involves the discretization of the environment being modeled and estimating the light transported between the resulting elements. The computed result, a collection of patches and their estimated radiances, does not produce a very realistic image and often the reconstruction of the illuminance functions over each visible surface is necessary. The more sophisticated of these reconstruction techniques perform a local gathering step at closely spaced sample points, typically one per pixel. This paper describes an algorithmic framework for implementing this final gathering pass that allows one to adaptively control the spacing of sample points in order to minimize the number of computationally expensive local gather operations while still achieving a rendered image of acceptable quality.\par The basic algorithm is independent of the method by which the global illumination solution is obtained but can easily be tuned for specific models and surfaces. The method is also easily extended to allow the shading of curved surfaces within a radiosity environment.", acknowledgement = ack-nhfb, } @Article{vanOverveld:1997:DGM, author = "C. W. A. M. {van Overveld} and M. G. J. R. Stalpers", title = "Deforming Geometric Models Based on a Polygonal Skeleton Mesh", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "3", pages = "1--14", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/StalpersVanOverveld97/", abstract = "A technique is presented for the deformation of a given geometric model (to be called: the skin) by means of a polygonized skeleton model. It is based on recognition of similarities in shape between these models by means of a method called dual-connectivity search. The technique uses these similarities in shape to define a semantic relation between the skeleton and the skin such that a smooth deformation for the skin is generated, that resembles, and is derived from, a deformation of the skeleton.", acknowledgement = ack-nhfb, } @Article{Cignoni:1997:CAG, author = "P. Cignoni and C. Montani and R. Scopigno", title = "Computer-Assisted Generation of Bas- and High-Reliefs", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "3", pages = "15--28", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/CignoniMontaniScopigno97/", abstract = "This paper proposes a computer-oriented interpretation of the laws ruling the elevation of figures in bas- or high-relief sculptures. It presents some simple algorithms and a prototypical, public-domain software tool for the generation of three-dimensional bas- and high-reliefs starting from three-dimensional surface models.", acknowledgement = ack-nhfb, } @Article{Bailey:1997:ETD, author = "Michael Bailey and Dru Clark", title = "Encoding Three-Dimensional Surface Information in a Texture Vector", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "3", pages = "29--35", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/BaileyClark97/", abstract = "This paper describes a novel use of texture mapping. Surface information, in this case the surface normal, is used as the texture coordinates. As we rotate the object, the color pattern on its surfaces fluctuates based on its surface normal orientation in world space. The result is a fast human-in-the-loop interactive system for optimizing mechanical part orientation for fabrication.", acknowledgement = ack-nhfb, } @Article{Xiang:1997:TPC, author = "Zhigang Xiang", title = "A Tri-Plane Cursor", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "3", pages = "37--43", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Xiang97/", abstract = "Interactive three-dimensional editing requires visualization techniques that help the user gauge position and shape. This paper describes the use of a tri-plane cursor to provide correlated cursor/object position and surface-shape feedback. These visual cues are generated dynamically by three cursor planes in the form of contours and shading variations.", acknowledgement = ack-nhfb, } @Article{Shirley:1997:LDM, author = "Peter Shirley and Kenneth Chiu", title = "A Low Distortion Map Between Disk and Square", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "3", pages = "45--52", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/ShirleyChiu97/", abstract = "This paper presents a map between squares and disks that associates concentric squares with concentric circles. This map preserves adjacency and fractional area, and has proven useful in many sampling applications where correspondences must be maintained between the two shapes. The paper also provides code to compute the map that minimizes branching and is robust for all inputs. Finally, it extends the map to the hemisphere. Though this map has been used in publications before, details of its computation have never previously been published.", acknowledgement = ack-nhfb, } @Article{vandenBergen:1997:ECD, author = "Gino van den Bergen", title = "Efficient Collision Detection of Complex Deformable Models using {AABB} Trees", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "4", pages = "1--14", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/vanDenBergen97/", abstract = "We present a scheme for exact collision detection between complex models undergoing rigid motion and deformation. The scheme relies on a hierarchical model representation using axis-aligned bounding boxes (AABBs). Recent work has shown that AABB trees are slower than oriented bounding box (OBB) trees for performing overlap tests. In this paper, we describe a way to speed up overlap tests between AABBs, such that for collision detection of rigid models, the difference in performance between the two representations is greatly reduced. Furthermore, we show how to update an AABB tree quickly as a model is deformed. We thus find AABB trees to be the method of choice for collision detection of complex models undergoing deformation. In fact, because they are not much slower to test, are faster to build, and use less storage than OBB trees, AABB trees might be a reasonable choice for rigid models as well.", acknowledgement = ack-nhfb, } @Article{Havran:1997:FRB, author = "Vlastimil Havran and Tomas Kopal and Jiri Bittner and Jiri Zara", title = "Fast Robust {BSP} Tree Traversal Algorithm for Ray Tracing", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "4", pages = "15--24", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/HavranKopalBittnerZara97/", abstract = "An orthogonal BSP (binary space partitioning) tree is a commonly used spatial subdivision data structure for ray tracing acceleration. While the construction of a BSP tree takes a relatively short time, the efficiency of a traversal algorithm significantly influences the overall rendering time. We propose a new fast traversal algorithm based on statistical evaluation of all possible cases occurring during traversing a BSP tree. More frequent cases are handled simply, while less frequent ones are more computationally expensive. The proposed traversal algorithm handles all singularities correctly. The algorithm saves from 30\% up to 50\% of traversal time comparing with the commonly-known Sung and Arvo algorithms.", acknowledgement = ack-nhfb, } @Article{Held:1997:ECE, author = "Martin Held", title = "{ERIT}: {A} Collection of Efficient and Reliable Intersection Tests", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "4", pages = "25--44", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Held97/", abstract = "We describe ERIT, a collection of C routines for efficiently and reliably handling intersection queries between pairs of primitive objects in three dimensions. ERIT supports intersection queries between the following pairs of primitives: triangle/line-segment, triangle/triangle, sphere/line-segment, sphere/triangle, cylinder/line-segment, cylinder/triangle, cylinder/sphere, cone/line-segment, cone/triangle, toroid/line-segment, toroid/triangle, and sphere/sphere. All intersection routines are based on standard ``epsilon-based'' floating-point arithmetic. Practical tests have proved that ERIT's routines are efficient and reliable, and we provide performance statistics for three widely-used hardware platforms.", acknowledgement = ack-nhfb, } @Article{vanOverveld:1997:CWS, author = "C. W. A. M. {van Overveld}", title = "Color Waves: {A} Simple Heuristic for Choosing False Colors", journal = j-J-GRAPHICS-TOOLS, volume = "2", number = "4", pages = "45--50", year = "1997", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/vanOverveld97/", abstract = "A simple heuristic is presented for choosing false colors for visualizing scalar functions on two-dimensional domains. The color scheme allows inspection of the function on several length scales simultaneously.", acknowledgement = ack-nhfb, } @Article{Johannsen:1998:CBC, author = "Andreas Johannsen and Michael B. Carter", title = "Clustered Backface Culling", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "1", pages = "1--14", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/JohannsenCarter98/", abstract = "This paper presents a simple, practical, and effective backface-culling technique for clusters of polygons, as well as a method for generating efficient clusters from a set of triangle strips. The cluster-backface test is directly derived from the traditional single-polygon test, and has about the same complexity. Memory requirements are 40 bytes per test. Cluster-backface tests may be arranged hierarchically, and frontface tests added for symmetry. Experiments show graphics performance improvements of up to 50 percent in terms of the number of effective polygons rendered per second.", acknowledgement = ack-nhfb, } @Article{Larson:1998:LEF, author = "Gregory Ward Larson", title = "{LogLuv} Encoding for Full-Gamut, High-Dynamic Range Images", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "1", pages = "15--31", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Larson98/", abstract = "The human eye can accommodate luminance in a single view over a range of about 10,000:1 and is capable of distinguishing about 10,000 colors at a given brightness. By comparison, typical computer monitors have a luminance range less than 100:1 and cover about half of the visible color gamut. Despite this difference, most digital image formats are geared to the capabilities of conventional displays, rather than the characteristics of human vision. In this paper, we propose a compact encoding suitable for the transfer, manipulation, and storage of high-dynamic range color images. This format is a replacement for conventional RGB images, and encodes color pixels as log luminance values and CIE $(u',v')$ chromaticity coordinates. We have implemented and distributed this encoding as part of teh standard TIFF I/O library available by anonymous ftp. After explaining our encoding, we describe its use within TIFF and present some techniques for handling high-dynamic range pixels, and demonstrate with an example image.", acknowledgement = ack-nhfb, } @Article{Max:1998:OPV, author = "Nelson Max", title = "A One-Pass Version of Two-Pass Image Resampling", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "1", pages = "33--41", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Max98/", abstract = "The intermediate storage and memory access for the first-pass output of the Catmull-Smith two-pass image resampling are eliminated by feeding output directly to the second apss as soon as it is computed. The algorithm reads input and intermediate data sequentially, so that it is suitable for efficient hardware or software implementation on modern, cache-based computers.", acknowledgement = ack-nhfb, } @Article{Thurmer:1998:CVN, author = "Grit Th{\"u}rmer and Charles A. W{\"u}thrich", title = "Computing Vertex Normals from Polygonal Facets", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "1", pages = "43--46", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/ThurmerWuthrich98/", abstract = "The method most commonly used to estimate the normal vector at a vertex of a polygonal surface averages the normal vectors of the facets incident to the vertex considered. The vertex normal obtained in this way may vary depending on the tessellation of the polygonal surface since the normal of each incident facet contributes equally to the normal in the vertex. To overcome this drawback, we extend the method so that it also incorporates the geometric contribution of each facet, consider the angle under which a facet is incident to the vertex in question.", acknowledgement = ack-nhfb, } @Article{Smits:1998:EIR, author = "Brian Smits", title = "Efficiency Issues for Ray Tracing", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "2", pages = "1--14", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Smits98/", abstract = "Ray casting is the bottleneck of many rendering algorithms. Although much work has been done on making ray casting more efficient, most published work is high level. This paper discusses efficiency at a slightly lower level, presenting optimizations for bounding-volume hierarchies that many people use but are rarely described in the literature. A set of guidelines for optimization are presented that avoid some of the common pitfalls. Finally, the effects of the optimizations are shown for a set of models.", acknowledgement = ack-nhfb, } @Article{Woo:1998:CTS, author = "Andrew Woo", title = "Chordlength Texturing of Spline Surfaces", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "2", pages = "15--19", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Woo98/", abstract = "This paper presents an inexpensive way to provide (s,t) texture coordinates of a spline surface that mitigates texture compression and stretching artifacts. The approach employs a chordlength approximation based on the original spline-surface parameterization. Its success can be seen in existing Alias|Wavefront renderers since 1991.", acknowledgement = ack-nhfb, } @Article{VanGelder:1998:ASE, author = "Allen {Van Gelder}", title = "Approximate Simulation of Elastic Membranes by Triangulated Spring Meshes", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "2", pages = "21--41", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/VanGelder98/", abstract = "Spring meshes have been used to model elastic material in computer graphics, with skin, textiles, and soft tissue being typical applications. A spring mesh is a system of vertices and edges, possibly with highly irregular geometry, in which each edge is a spring, and springs are connected by ``pin-joints'' (``gimbal-joints'' in three dimensions) at the vertices. This method is computationally attractive, compared to some alternatives. Given a specified set of elastic material properties, however, the question of whether a particular spring mesh accurately simulates those properties has been largely ignored in the literature. Additionally, previous reports on the technique are silent on the subject of assigning stiffness to the various springs. This paper shows that assigning the same stiffness to all springs fails to simulate a uniform elastic membrane, for equilibrium calculations. A formula for spring stuffness that provides a more accurate simulation is then derived. In its simplest form, this formula specifies that stiffness varies as triangle area over edge length squared. Its accuracy is demonstrated on test and practical mesh examples. It is also shown that, in general, an exact simulation is not possible.", acknowledgement = ack-nhfb, } @Article{Bailey:1998:UCO, author = "Michael Bailey and Dru Clark", title = "Using {ChromaDepth} to Obtain Inexpensive Single-image Stereovision for Scientific Visualization", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "3", pages = "1--9", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/BaileyClark98/", abstract = "Stereographics is an effective way to enhance insight in three-dimensional scientific visualization. This is especially true for visualizations consisting of complex geometry, such as molecular studies, or where one data set needs to be registered against another, such as in earth science. But, as effective as it is, stereoviewing sees only limited use in scientific visualization because of the difficulty and expense of creating images that everyone can see. This paper demonstrates how a low-end, inexpensive viewing technique can be used as a ``quick trick'' to produce many of the same effects as high-end stereoviewing. Not only is this technique easy to view and easy to publish, it is easy to create. This paper shows how standard OpenGL features can be used to create such images, both statically and interactively.", acknowledgement = ack-nhfb, } @Article{Feng:1998:ABS, author = "Jieqing Feng and Pheng-Ann Heng and Tien-Tsin Wong", title = "Accurate {B}-spline Free-Form Deformation of Polygonal Objects", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "3", pages = "11--27", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/FengHengWong98/", abstract = "Free-form deformation is an important geometric shape modification method in computer animation and geometric modeling. We explore it by means of functional composition via shifting operators. Our method takes a polygonal model as input but yields a curved model described by triangular B{\'e}zier patches as output. The proposed method solves the sampling problem of free-form deformation.", acknowledgement = ack-nhfb, } @Article{Grassia:1998:PPR, author = "F. Sebastian Grassia", title = "Practical Parameterization of Rotations Using the Exponential Map", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "3", pages = "29--48", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Grassia98/", abstract = "Parameterizing three degree-of-freedom (DOF) rotations is difficult to do well. Many graphics applications demand that we be able to compute and differentiate positions and orientations of articulated figures with respect to their rotational (and other) parameters, as well as integrate differential equations, optimize rotation parameters, and interpolate orientations. Widely used parameterizations such as Euler angles and quaternions are well suited to only a few of these operations. The exponential map maps a vector in $R^3$ describing the axis and magnitude of a three-DOF rotation to the corresponding rotation. Several graphics researchers have applied it with limited success to interpolation of orientations, but it has been virtually ignored with respect to the other operations mentioned above. In this paper we present formulae for computing, differentiating, and integrating three-DOF rotations with the exponential map. We show that our formulation is numerically stable in the face of machine precision issues, and that for most applications all singularities in the map can be avoided through a simple technique of dynamic reparameterization. We demonstrate how to use the exponential map to solve both the ``freely rotating body'' problem and the important ball-and-socket joint required to accurately model shoulder and hip joints in articulated figures. Examining several common graphics applications, we explain the benefits of our formulation of the exponential map over Euler angles and quaternions, including robustness, small state vectors, lack of explicit constraints, good modeling capabilities, simplicity of solving ordinary differential equations, and good interpolation behavior.", acknowledgement = ack-nhfb, } @Article{Campagna:1998:DES, author = "Swen Campagna and Leif Kobbelt and Hans-Peter Seidel", title = "Directed Edges --- {A} Scalable Representation for Triangle Meshes", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "4", pages = "1--12", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/CampagnaKobbeltSeidel98/", abstract = "In a broad range of computer graphics applications, the representation of geometric shape is based on triangle meshes. General purpose data structures for polygonal meshes typically provide fast access to geometric objects (e.g., points) and topological entities (e.g., neighborhood relationships) but the memory requirements are rather high due to the many special configurations. In this paper, we present a new data structure which is specifically designed for triangle meshes. The data structure enables the programmer to trade memory for access time by either storing internal references explicitly, or by reconstructing them locally on demand. The trade-off can be hidden from the programmer by an object-oriented API and can automatically adapt to the available hardware resources or the complexity of the mesh (scalability).", acknowledgement = ack-nhfb, } @Article{Fu:1998:TBV, author = "Chi-Wing Fu and Tien-Tsin Wong and Pheng-Ann Heng", title = "Triangle-Based View Interpolation without Depth-Buffering", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "4", pages = "13--31", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/FuWongHeng98/", abstract = "In this paper, we propose a triangle-based view interpolation algorithm that can correctly resolve the visibility problem without depth-buffering. The algorithm is especially useful when depth information is not available, such as in the case of real-world photographs. By subdividing the reference image into variable-sized triangles, view interpolation can be done efficiently using existing graphics hardware. We derive the drawing order between each pair of neighboring triangles from the epipolar geometry. Using this drawing order, a graph can be built and topological sorting is applied on the graph to obtain the complete drawing order of all triangles in linear time.", acknowledgement = ack-nhfb, } @Article{Chen:1998:FVT, author = "Hongsheng Chen and Shiaofen Fang", title = "Fast Voxelization of Three-Dimensional Synthetic Objects", journal = j-J-GRAPHICS-TOOLS, volume = "3", number = "4", pages = "33--45", year = "1998", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/ChenFang98/", abstract = "This paper presents a new approach to the voxelization of three-dimensional synthetic objects. It makes use of existing graphics hardware on standard graphics workstations, such as the polygon-based geometry engine and frame buffer operations, and is able to generate the voxel-based volume representations of general curves, surfaces, or solid objects efficiently. On a workstation with hardware-supported texture mapping, the voxelization result may also be written directly to the three-dimensional texture memory as a three-dimensional texture object, and interactively rendered by the three-dimensional texture-mapping hardware. This approach provides a practical solution to the interactive manipulations of geometric objects within a volume graphics framework.", acknowledgement = ack-nhfb, } @Article{Wang:1999:NMP, author = "Wencheng Wang and Yanyun Chen and Enhua Wu", title = "A New Method for Polygon Edging on Shaded Surfaces", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "1", pages = "1--10", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/WangChenWu99/", abstract = "Wireframe and shaded surfaces are often rendered together to reap the advantages of both methods. However, existing methods for such a combination can lead to edge stitching and/or draw edges of polygons that are behind other polygons; the Z-buffer comparison widely used in existing methods is not very suitable for the task. In this paper, a new method without a Z-buffer comparison is proposed. Using this proposed method, the correspondence between edges and polygons is examined and the occluding relation between polygons is used to decide if a pixel of an edge is to be drawn. Thus, the problems caused by Z-buffer comparisons are eliminated, and high-quality wireframe-overlayed shaded surfaces can be rendered.", acknowledgement = ack-nhfb, } @Article{Wan:1999:OIV, author = "Ming Wan and Arie Kaufman and Steve Bryson", title = "Optimized Interpolation for Volume Ray Casting", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "1", pages = "11--24", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/WanKaufmanBryson99/", abstract = "An acceleration technique using bilinear and simplified trilinear interpolation which reduces the amount of interpolation computation during the ray sampling procedure of the volume ray casting algorithm is described. It has several characteristics: It is applicable to both perspective projection and parallel projection; it uses almost no extra space and processing power; there is no noticeable sacrifice of image quality; and more importantly, it can be easily applied to existing ray casting optimizations to further improve their efficiency. In addition, an adaptive depth-sampling optimization has been developed based on our technique, which serves as an effective approach to meet the frame rate demand of time-critical visualization environment. Experimental results show that a rendering rate of more than ten frames per second has been achieved on a 16-processor SGI Power Challenge.", acknowledgement = ack-nhfb, } @Article{Karabassi:1999:ITC, author = "Evaggelia-Aggeliki Karabassi and Georgios Papaioannou and Theoharis Theoharis", title = "Intersection Test for Collision Detection in Particle Systems", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "1", pages = "25--37", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/KarabassiEtAl99/", abstract = "We present a method for detecting collisions between a system of spherical particles and an environment composed of triangles. The proposed algorithm takes into account each particle's volume and is based on an intersection test between a triangle and a cylinder with spherical caps (the trajectory of a particle). The algorithm also efficiently calculates a close estimate of the point of intersection, which is necessary for collision detection.", acknowledgement = ack-nhfb, } @Article{Wang:1999:MSR, author = "Changyaw Wang and Kelvin Sung", title = "Multi-Stage {$N$}-rooks Sampling Method", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "1", pages = "39--47", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/WangSung99/", abstract = "In many graphics tasks, such as pixel antialiasing, a set of spatially ``uniform'' samples must be generated on a unit square. Some algorithms attempt to create sets of samples whose $x$ and $y$ coordinates are each themselves uniform, while making sure that the samples are also uniform in two dimensions. However, this is hard to do if the number of samples is not a perfect square. In this paper, we introduce a new sampling strategy which generates any number of uniform two-dimensional samples while maintaining uniformity in $x$ and $y$ as well.", acknowledgement = ack-nhfb, } @Article{Max:1999:WCV, author = "Nelson Max", title = "Weights for Computing Vertex Normals from Facet Normals", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "2", pages = "1--6", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Max99/", abstract = "I propose a new equation to estimate the normal at a vertex of a polygonal approximation to a smooth surface, as a weighted sum of the normals to the facets surrounding the vertex. The equation accounts for the difference in size of these facets by assigning larger weights for smaller facets. When tested on random cubic polynomial surfaces, the equation is superior to other popular weighting methods.", acknowledgement = ack-nhfb, } @Article{vandenBergen:1999:FRG, author = "Gino van den Bergen", title = "A Fast and Robust {GJK} Implementation for Collision Detection of Convex Objects", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "2", pages = "7--25", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/vanDenBergen99/", abstract = "This paper presents an implementation of the Gilbert-Johnson-Keerthi algorithm for computing the distance between convex objects, that has improved performance, robustness, and versatility over earlier implementations. The algorithm presented here is especially suitable for use in collision detection of objects modeled using various types of geometric primitives, such as boxes, cones, and spheres, and their images under affine transformation.", acknowledgement = ack-nhfb, } @Article{Zhang:1999:DIB, author = "Hansong Zhang", title = "A Derivation of Image-Based Rendering for Conventional Three-Dimensional Graphics", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "2", pages = "27--36", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Zhang99/", abstract = "Image-based rendering generates images from one or more known images without explicit geometric representation of objects. This paper presents a derivation of the pixel transformations for three-dimensional image warping, a popular form of image-based rendering. The derivation is based entirely on traditional three-dimensional graphics terminology, using only 4~x~4 matrices. The transformations are optimized based on the fact that transformations of adjacent pixels share much common computation. Derivatives and frame-to-frame coherence are also discussed.", acknowledgement = ack-nhfb, } @Article{Schmalstieg:1999:FPA, author = "Dieter Schmalstieg and Robert F. Tobler", title = "Fast Projected Area Computation for Three-Dimensional Bounding Boxes", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "2", pages = "37--43", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/SchmalstiegTobler99/", abstract = "The area covered by a three-dimensional bounding box after projection onto the screen is relevant for view-dependent algorithms in real-time and photorealistic rendering. We describe a fast method to compute the accurate two-dimensional area of a three-dimensional oriented bounding box, and show how it can be computed equally fast or faster than its approximation with a two-dimensional bounding box enclosing the projected three-dimensional bounding box.", acknowledgement = ack-nhfb, } @Article{Christensen:1999:FPM, author = "Per H. Christensen", title = "Faster Photon Map Global Illumination", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "3", pages = "1--10", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Christensen99/", abstract = "The photon map method is an extension of ray tracing that makes it able to efficiently compute caustics and soft indirect illumination on surfaces and in participating media. This paper describes a method to further speed up the computation of soft indirect illumination (diffuse-diffuse light transport such as color bleeding) on surfaces. The speed-up is based on the observation that the many look-ups in the global photon map during final gathering can be simplified by precomputing local irradiance values at the photon positions. Our tests indicate that the calculation of soft indirect illumination during rendering, which is the most time-consuming part, can be sped up by a factor of 5--7 in typical scenes at the expense of (1) a precomputation that takes about 2\%--5\% of the time saved during rendering and (2) a 28\% increase of memory use.", acknowledgement = ack-nhfb, } @Article{Teller:1999:DLT, author = "Seth Teller and Michael Hohmeyer", title = "Determining the Lines Through Four Lines", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "3", pages = "11--22", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/TellerHohmeyer99/", abstract = "This paper describes how to compute the line or lines which intersect four given lines in three dimensions. This intersection computation arises in computer graphics (for visibility computations), computational geometry (for line traversals), and computer vision (for object recognition).\par Given four distinct lines in three dimensions, there exist zero, one, two, or various infinities of lines intersecting the given lines. We use Pl{\"u}cker coordinatization of lines to cast this problem as a null-space computation in five dimensions, and show how the singular value decomposition (SVD) yields a simple, stable characterization of the incident lines, and an efficient algorithm to determine them.\par Finally, we enumerate the types of input degeneracies that may arise, show how to detect each type in practice, and describe for each case the solution set of lines that arises.", acknowledgement = ack-nhfb, } @Article{Keating:1999:ESA, author = "Brett Keating", title = "Efficient Shadow Antialiasing Using an {$A$}-Buffer", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "3", pages = "23--33", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Keating99/", abstract = "The Z-buffer shadow algorithm is a popular method for producing hard shadows. However, antialiasing of the shadow edges is necessary. This paper provides a new technique for antialiasing of shadow edges that is based on the A-buffer hidden-surface algorithm, which uses bitmasks to describe the area of a pixel occupied by an object. Compared to percentage-closer filtering, which is the standard method for antialiasing shadow edges, the new technique is much faster and has no noisiness present in the blurred regions.", acknowledgement = ack-nhfb, } @Article{McCormick:1999:DAB, author = "Patrick S. McCormick and Charles Hansen and Edward Angel", title = "The Deferred Accumulation Buffer", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "3", pages = "35--46", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/McCormickHansenAngel99/", abstract = "A well-known disadvantage of using the Z-buffer algorithm for medium-quality rendering is the overhead associated with shading, shadowing, and texturing pixels that do not contribute to the final image. This problem may be avoided by deferring shading calculations until the end of the rendering pipeline. In this paper, we review two approaches to deferred shading, discuss how to handle transparency, and then extend these ideas to implement a deferred accumulation buffer.", acknowledgement = ack-nhfb, } @Article{Moller:1999:EBM, author = "Tomas M{\"o}ller and John F. Hughes", title = "Efficiently Building a Matrix to Rotate One Vector to Another", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "4", pages = "1--4", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/MollerHughes99/", abstract = "We describe an efficient (no square roots or trigonometric functions) method to construct the $3\times3$ matrix that rotates a unit vector {\bf f} into another unit vector {\bf t}, rotating about the axis {\bf f} $\times$ {\bf t}. We give experimental results showing this method is faster than previously known methods. An implementation in C is provided.", acknowledgement = ack-nhfb, } @Article{Karabassi:1999:FDB, author = "Evaggelia-Aggeliki Karabassi and Georgios Papaioannou and Theoharis Theoharis", title = "A Fast Depth-Buffer-Based Voxelization Algorithm", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "4", pages = "5--10", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/KarabassiEtAl99b/", abstract = "This paper presents a fast and easy to implement voxelization algorithm, which is based on the z-buffer. Unlike most existing methods, our approach is suitable both for polygonal and analytical objects. The efficiency of the method is independent of the object complexity and can be accelerated by taking advantage of widely available, low-cost hardware.", acknowledgement = ack-nhfb, } @Article{Smits:1999:RSC, author = "Brian Smits", title = "An {RGB}-to-Spectrum Conversion for Reflectances", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "4", pages = "11--22", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Smits99/", abstract = "This paper presents a solution to the problem of using RGB data created by most modeling systems in a spectrally-based renderer. It differs from previous methods in that it attempts to create physically plausible spectra for reflectances. The method searches the metamer space for a spectrum that best fits a set of criteria. The results are used in an algorithm that is simple and efficient enough to be used within the rendering process for both importing models and for texture mapping.", acknowledgement = ack-nhfb, } @Article{Boyles:1999:SBV, author = "Michael Boyles and Shiaofen Fang", title = "Slicing-Based Volumetric Collision Detection", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "4", pages = "23--32", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/BoylesFang99/", abstract = "In this paper, we present a new approach for collision detection of volumetric objects. Good speeds and accuracy can be achieved using existing graphics hardware. The algorithm in simple to implement and, unlike other collision detection mechanisms, requires very little extra memory and preprocessing time. Using a combination of the two-dimensional scanline process and three-dimensional texture mapping technique, a number of polygonal slides can be computed for all volume objects in a scene. For each slice, the objects are checked for collisions using the framebuffer and logical color coding operations. Experiments are provided and analyzed.", acknowledgement = ack-nhfb, } @Article{Hughes:1999:BOB, author = "John F. Hughes and Tomas M{\"o}ller", title = "Building an Orthonormal Basis from a Unit Vector", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "4", pages = "33--35", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/HughesMoller99/", abstract = "We show how to easily create a right-handed orthonormal basis, given a unit vector, in 2-,~3-, and 4-space.", acknowledgement = ack-nhfb, } @Article{Li:1999:IPD, author = "Frederick W. B. Li and Rynson W. H. Lau", title = "Incremental Polygonization of Deforming {NURBS} Surfaces", journal = j-J-GRAPHICS-TOOLS, volume = "4", number = "4", pages = "37--50", year = "1999", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/LiLau99/", abstract = "Nonuniform rational B-splines (NURBS) are a powerful tool to model deformable objects. Their shapes can be easily modified by moving the control points. A common method used to render these objects is polygonization. However, the polygonization process is computationally very expensive. If the object deforms, we need to execute this process in every frame to reflect the geometric change of the object. This limitation makes real-time rendering of deforming objects very difficult. In this paper, we present an incremental method for polygonizing deforming objects modeled by NURBS surfaces. Some incremental techniques are introduced here to further improve the performance of the method. They include an efficient mechanism for determining the deformation region when the surface deforms, an incremental crack prevention technique, and an updating method for multiple control point movement.", acknowledgement = ack-nhfb, } @Article{Feng:2000:AAB, author = "Jieqing Feng and Qunsheng Peng", title = "Accelerating Accurate {B}-spline Free-Form Deformation of Polygonal Objects", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "1", pages = "1--8", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/FengPeng00/", abstract = "A previous paper described an algorithm for accurate B-spline free-form deformation of polygonal objects to produce triangular B{\'e}zier patches. However that algorithm computed the control points of the resulting patches using a generalized de Casteljau algorithm, which is expensive to compute. In this short note, we describe an algorithm that instead uses polynomial interpolation; both theoretical analysis and implementation results show that this new algorithm runs faster than the original.", acknowledgement = ack-nhfb, } @Article{Assarsson:2000:OVF, author = "Ulf Assarsson and Tomas M{\"o}ller", title = "Optimized View Frustum Culling Algorithms for Bounding Boxes", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "1", pages = "9--22", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AssarssonMoller00/", abstract = "This paper presents optimizations for faster view frustum culling (VFC) for axis-aligned bounding box (AABB) and oriented bounding box (OBB) hierarchies. We exploit frame-to-frame coherency by caching and by comparing against previous distances and rotation angles. By using an octant test, we potentially halve the number of plane tests needed, and we also evaluate masking, which is a well-known technique. The optimizations can be used for arbitrary bounding volumes, but we present only results for ABBs and OBBs. In particular, we provide solutions which are 2-11 times faster than other VFC algorithms for AABBs and OBBs, depending on the circumstances.", acknowledgement = ack-nhfb, } @Article{Haines:2000:SCT, author = "Eric Haines", title = "A Shaft Culling Tool", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "1", pages = "23--26", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Haines00/", abstract = "Shaft culling is a means to accelerate the testing of visibility between two objects. This paper briefly describes an algorithm for shaft culling and various implementation options. The code and test harness for the algorithm is available online.", acknowledgement = ack-nhfb, } @Article{Martin:2000:PRT, author = "William Martin and Elaine Cohen and Russell Fish and Peter Shirley", title = "Practical Ray Tracing of Trimmed {NURBS} Surfaces", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "1", pages = "27--52", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/MartinCohenFishShirley00/", abstract = "A system is presented for ray tracing trimmed NURBS surfaces. While approaches to components are drawn largely from existing literature, their combination within a single framework is novel. This paper also differs from prior work in that the details of an efficient implementation are fleshed out. Throughout, emphasis is placed on practical methods suitable to implementation in general ray-tracing programs.", acknowledgement = ack-nhfb, } @Article{Wong:2000:AIS, author = "Kevin Chun-Ho Wong and Pheng-Ann Heng and Tien-Tsin Wong", title = "Accelerating ``Intelligent Scissors'' Using Slimmed Graphs", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "2", pages = "1--13", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Sat Jan 13 13:11:20 2001", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/WongHengWong00/", abstract = "In this paper, we describe an acceleration technique for the semi-automatic image segmentation algorithm, ``intelligent scissors''. Using intelligent scissors, the user can accurately and interactively extract an object from a digitized image. However, the original algorithm suffers from slow performance when large images are treated. In practice, pixels within the non-edge regions are seldom involved in the determination of boundaries (segmentation curves). If these pixels are removed before boundary determination, the performance of intelligent scissors can be improved. We generate a slimmed graph to achieve this goal with significant improvement in response time.", acknowledgement = ack-nhfb, } @Article{Jin:2000:TDD, author = "Xiaogang Jin and Y. F. Li", title = "Three-Dimensional Deformation Using Directional Polar Coordinates", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "2", pages = "15--24", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Sat Jan 13 13:11:20 2001", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/JinLi00/", abstract = "Spatial deformation is an important tool in both computer animation and shape design. In this paper, we present a new three-dimensional deformation method using directional polar coordinates. The user specifies a source control object and a destination control object, which act as embedding spaces. The source and the destination control objects determine a three-dimensional volume morphing which maps the space enclosed in the source control object to that of the destination control object. By embedding the object to be deformed into the source control object, the three-dimensional volume morphing determines the deformed object automatically without the cumbersome moving of control points. Experiments show that this deformation model is efficient and intuitive, and it can achieve some deformation effects which are difficult with traditional methods.", acknowledgement = ack-nhfb, } @Article{Ashikhmin:2000:APB, author = "Michael Ashikhmin and Peter Shirley", title = "An Anisotropic {Phong BRDF} Model", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "2", pages = "25--32", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Sat Jan 13 13:11:20 2001", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AshikhminShirley00/", abstract = "We present a BRDF model that combines several advantages of the various empirical models currently in use. In particular, it has intuitive parameters, is anisotropic, conserves energy, is reciprocal, has an appropriate non-Lambertian diffuse term, and is well-suited for use in Monte Carlo renderers.", acknowledgement = ack-nhfb, } @Article{Alonso:2000:UGH, author = "Laurent Alonso and Nicolas Holzschuch", title = "Using Graphics Hardware to Speed Up Your Visibility Queries", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "2", pages = "33--47", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Sat Jan 13 13:11:20 2001", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AlonsoHolzschuch00/", abstract = "We present a visibility method that takes advantage of the graphics hardware to give fast answers to visibility queries. Our visibility method is designed to solve two types of visibility queries: point-based visibility queries, where several visibility queries share the same origin, and plane-based visibility queries, where several visibility queries have their origins on the same plane. Both occur frequently in global illumination algorithms. Combining the speed given by graphics hardware with a software heuristic to avoid reliability problems, our visibility method is significantly faster than ray-casting, and still gives the same results", acknowledgement = ack-nhfb, } @Article{Chung:2000:SRT, author = "A. J. Chung and A. J. Field", title = "A Simple Recursive Tessellator for Adaptive Surface Triangulation", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "3", pages = "1--9", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Fri Jul 20 12:38:17 2001", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AlonsoHolzschuch00/", abstract = "Sometimes there is a need to create a triangular mesh approximation of a parametric surface. If the parametrization is nonuniform (compressed in some areas, stretchy in others), a uniform grid in parameter space becomes distorted and provides a bad approximation. We describe how to create an adaptive triangulation of such a surface, provided the user of the algorithm provides a routine {\tt split_edge()} which indicates whether a particular edge is close enough to the surface or requires splitting, and optionally a routine {\tt flat_enough()} which tells whether a triangle whose edges appear adequate is indeed flat enough, or requires further subdivision. Our contribution is a simple algorithm for guaranteeing that the topology of the resulting mesh is well formed in the sense that there are no cracks between triangles (i.e., T-junction), and for ensuring that subdivision halts at a given point. There is also rudimentary support for trimmed surfaces. Source code for the algorithm is available online.", acknowledgement = ack-nhfb, } @Article{Wolberg:2000:ODR, author = "George Wolberg and H. M. Sueyllam and M. A. Ismail and K. M. Ahmed", title = "One-Dimensional Resampling with Inverse and Forward Mapping Functions", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "3", pages = "11--33", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Fri Jul 20 12:38:17 2001", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AlonsoHolzschuch00/", abstract = "Separable resampling algorithms significantly reduce the complexity of image warping. Fant presented a separable algorithm that is well suited for hardware implementation. That method, however, is inherently serial and applies only when the inverse mapping is given. Wolberg presented another algorithm that is less suited for hardware implementation and applies only when the forward mapping is given. This paper demonstrates the equivalence of the two algorithms in the sense that they produce identical output scanlines. We derive a variation of Fant's algorithm that applies when the forward mapping is given and a variation of Wolberg's algorithm that applies when the inverse mapping is given. Integrated hardware implementations that perform one-dimensional resampling under either forward or inverse mappings are presented for both algorithms based on their software descriptions. The Fant algorithm has the advantage of being simple when implemented in hardware, while the Wolberg algorithm has the advantage of being parallelizable and facilitates a faster software implementation. The Wolberg algorithm also has the advantage of decoupling the roundoff errors made among intervals since it does not accrue errors through the incremental calculations required by the Fant algorithm.", acknowledgement = ack-nhfb, } @Article{Velho:2000:USR, author = "Luiz Velho", title = "Using Semi-Regular $4$-$8$ Meshes for Subdivision Surfaces", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "3", pages = "35--47", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Fri Jul 20 12:38:17 2001", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AlonsoHolzschuch00/", abstract = "Semi-regular $4$-$8$ meshes are refinable {\em triangulated quadrangulations}. They provide a powerful hierarchical structure for multiresolution applications. In this paper, we show how to decompose the Doo-Sabin and Catmull-Clark subdivision schemes using $4$-$8$ refinement. The described technique makes it possible to use these classical subdivision surfaces with semi-regular $4$-$8$ meshes.", acknowledgement = ack-nhfb, } @Article{Castro:2000:EAT, author = "Francesc Castro and L{\'a}szl{\'o} Neumann and Mateu Sbert", title = "Extended Ambient Term", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "4", pages = "1--7", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Fri Jul 20 12:38:17 2001", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AlonsoHolzschuch00/", abstract = "The ambient term in a renderer is a constant color added to all points yielding a crude global approximation to indirect lighting. Because the ambient term ignores geometric occlusion conditions, it is computationally inexpensive. We present an extended ambient term that provides better results than the constant term, but is still inexpensive, because it also does not compute occlusion conditions. It is based on the idea of finding a six-sided axis-aligned environment which is similar in color and area to the real scene, and deriving an approximation to indirect lighting by computing interreflections in the simplified scene.", acknowledgement = ack-nhfb, } @Article{Rocchini:2000:GRP, author = "C. Rocchini and P. Cignoni", title = "Generating Random Points in a Tetrahedron", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "4", pages = "9--12", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Fri Jul 20 12:38:17 2001", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AlonsoHolzschuch00/", abstract = "This paper proposes a simple and efficient technique to generate uniformly random points in a tetrahedron. The technique generates random points in a cube and folds the cube into the barycentric space of the tetrahedron in a way that preserves uniformity.", acknowledgement = ack-nhfb, } @Article{Livingston:2000:CCT, author = "Mark A. Livingston and Arthur Gregory and W. Bruce Culbertson", title = "Camera Control in Three Dimensions with a Two-Dimensional Input Device", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "4", pages = "13--24", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Fri Jul 20 12:38:17 2001", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AlonsoHolzschuch00/", abstract = "We implement a variety of operations to control a virtual camera using a two-dimensional modal input device, such as a standard three-button mouse. All operations are designed to be easy to use for the end user, but we also designed for ease of implementation for the programmer.", acknowledgement = ack-nhfb, } @Article{Torres:2000:FAD, author = "J. C. Torres and F. A. Conde", title = "A Fast Algorithm to Decide the Inclusion of a Point in the Convex Hull of a Two-Dimensional Point Set", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "4", pages = "25--32", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Fri Jul 20 12:38:17 2001", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AlonsoHolzschuch00/", abstract = "This paper presents a new fast algorithm to compute the two-dimensional inclusion test of a point in the convex hull of a set of points, without computing the convex hull. The algorithm is based on the classification of the points in octants of the plane. The classification step for each point requires only simple test operations, and makes the algorithm run in at worst, O(n). For point sets larger than 11 points, the proposed algorithm is faster than other known approaches. The paper includes a practical evaluation of the algorithm, comparing it with several previously known approaches.", acknowledgement = ack-nhfb, } @Article{Elinas:2000:RTR, author = "Pantelis Elinas and Wolfgang Stuerzlinger", title = "Real-time rendering of {$3$D} clouds", journal = j-J-GRAPHICS-TOOLS, volume = "5", number = "4", pages = "33--45", year = "2000", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Wed Feb 06 11:23:34 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/ElinasStuerzlinger00.html", abstract = "The visual realism of a computer graphics simulation of outdoor scenery is greatly enhanced by a realistic display of clouds. In this paper, we present an algorithm based on Gardner's work that can render perspectively-correct 3D clouds in real time on current graphics hardware. The use of 3D ellipsoids as primitives permits even close-ups without the viewer noticing the approximation. We describe an implementation using OpenGL.", acknowledgement = ack-nhfb, } @Article{Dinerstein:2001:LGM, author = "Jonathan Dinerstein and Larre Egbert and Nick Flann", title = "Linear grouping---a method for optimizing {$3$D} vertex transformation and clipping", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "1", pages = "1--6", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Wed Feb 06 11:23:34 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/DinersteinEgbertFlann01.html", abstract = "This paper introduces {\em linear grouping}, a slightly lossy optimization technique for affine transformation of rigid vertex data. This technique is beneficial when vertex transformation is of notable cost, such as in software rendering systems and applications and where visual correctness is sufficient, for example games, simulators, and other real-time applications. In practice, linear grouping (nearly visually lossless) eliminates approximately~55\% of the vertices in an average polygonal mesh, reducing transform overhead by about~50\% and clipping overhead by about~32\%.", acknowledgement = ack-nhfb, } @Article{Kallmann:2001:SVC, author = "Marcelo Kallmann and Daniel Thalmann", title = "Star-vertices: {A} compact representation for planar meshes with adjacency information", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "1", pages = "7--18", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Wed Feb 06 11:23:34 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/KallmannThalmann01.html", abstract = "In this paper we propose a new structure, {\em star-vertex}, to represent general planar meshes. The basic concept is simple, allowing constant adjacency query time, and scalability (ability to trade size for speed), and under specific situations requiring less storage space than others. For simplicity, we use a generic traverse element, which resembles the behavior of oriented edges. We present implementation examples of the proposed structure and comparisons with other mesh representation schemes.", acknowledgement = ack-nhfb, } @Article{Haines:2001:SPS, author = "Eric Haines", title = "Soft planar shadows using plateaus", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "1", pages = "19--27", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Wed Feb 06 11:23:34 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Haines01.html", abstract = "This paper presents an algorithm for rapidly creating and rendering soft shadows on a plane. It has the advantages of rapid generation on current hardware, as well as high quality and a realistic feel on a perceptual level. The algorithm renders the soft shadow to a texture. It begins with a hard drop shadow, then uses the object's silhouette edges to generate penumbrae in a single pass. Though the shadows generated are physically inaccurate, this technique yields penumbrae that are smooth and perceptually convincing.", acknowledgement = ack-nhfb, } @Article{Akenine-Moller:2001:FTB, author = "Tomas Akenine-M{\"o}ller", title = "Fast {$3$D} triangle-box overlap testing", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "1", pages = "29--33", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Wed Feb 06 11:23:34 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AkenineMoller01.html", abstract = "A fast routine for testing whether a triangle and a box are overlapping in three dimensions is presented. The test is derived using the separating axis theorem, whereafter the test is simplified and the code is optimized for speed. We show that this approach is 2.3 vs. 3.8 (PC vs. Sun) times faster than previous routines. It can be used for faster collision detection and faster voxelization in interactive ray tracers. The code is available online.", acknowledgement = ack-nhfb, } @Article{Nasri:2001:SAG, author = "Ahmed Nasri and Gerald Farin", title = "A subdivision algorithm for generating rational curves", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "1", pages = "35--47", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Wed Feb 06 11:23:34 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/", abstract = "The well-known Chaikin algorithm generates uniform quadratic B-spline curves by repeating the process of cutting off the corners of a polygon. One disadvantage of this algorithm is the incapability of generating circles. This paper proposes a modification of this algorithm to produce piecewise rational curves; in particular a circle is produced from a given square. For a general control polygon, every two subsequent polygon legs of equal length will correspond to a circular arc. Such an arc will be parameterized by arc length and will remain circular under affine transformations. Both properties are not shared by the standard rational quadratic form.", acknowledgement = ack-nhfb, } @Article{vanderLinden:2001:MEL, author = "Jarno van der Linden and Richard Lobb", title = "{MPEG}-Encoded light fields", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "2", pages = "1--15", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Wed Feb 06 11:23:34 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/vanDerLindenLobb01.html", abstract = "Light fields (or Lumigraphs) are an image-based rendering method. As light fields require a large number of images, memory and disk space requirements are a significant barrier to the practical use of light fields. In this paper, we explain how to greatly reduce the space demands of light fields by encoding them in an MPEG format. The encoding is comprised of an MPEG bitstream and two tables of precomputed information to aid real-time decoding. By restricting the parameters used for MPEG encoding, and by employing a caching system, new views of the compressed light field can be rendered at fast interactive frame rates on consumer hardware. Compression ratios of around 50:1 are demonstrated. Combined, the speed and compression make the use of light fields practical on consumer hardware.", acknowledgement = ack-nhfb, } @Article{Molla:2001:SA, author = "Ram{\'o}n Moll{\'a} and Roberto Viv{\'o}", title = "The Stair algorithm", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "2", pages = "17--25", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Wed Feb 06 11:23:34 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/MollaVivo01.html", abstract = "This algorithm draws straight lines on discrete devices as if they were staircases. It determines the fractional average length of each step, and it fills the pixels along every scanline intersected by the line to be drawn. This algorithm supports fractional line ends, and it uses internal 32-bit, fixed-point arithmetic; 16 bits for the integer and 16 bits for the decimal part.", acknowledgement = ack-nhfb, } @Article{Wilhelms:2001:FER, author = "Jane Wilhelms and Allen Van Gelder", title = "Fast and easy reach-cone joint limits", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "2", pages = "27--41", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Wed Feb 06 11:23:34 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/WilhelmsVanGelder01.html", abstract = "We describe a simple and fast method of creating and using joint sinus reach cones to limit the range of motion on universal and ball-and-socket joints. Reach cones can be created interactively or based on results from biomechanics. A reach cone is specified as a spherical polygon on the surface of a reach sphere that defines all positions the longitudinal segment axis beyond the joint can take. Reach polygons can be concave or convex, and cover more than one hemisphere. Longitudinal axis rotation limits can also be defined for locations in the reach cone. Calculations to determine whether a segment is within the reach cone are based on the relation of the segment longitudinal axis to the planes defining the reach cone and are done in the local coordinate space of the segment. The calculations have no discernible effect on the speed of interactive display or animation.", acknowledgement = ack-nhfb, } @Article{Stam:2001:SFS, author = "Jos Stam", title = "A simple fluid solver based on the {FFT}", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "2", pages = "43--52", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Wed Feb 06 11:23:34 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Stam01.html", abstract = "This paper presents a very simple implementation of a fluid solver. The implementation is consistent with the equations of fluid flow and produces velocity fields that contain incompressible rotational structures and dynamically react to user-supplied forces. Specialized for a fluid which wraps around in space, it allows us to take advantage of the Fourier transform, which greatly simplifies many aspects of the solver. Indeed, given a Fast Fourier Transform, our solver can be implemented in roughly one page of readable C code. The solver is a good starting point for anyone interested in coding a basic fluid solver. The fluid solver presented is useful also as a basic motion primitive that can be used for many different applications in computer graphics.", acknowledgement = ack-nhfb, } @Article{Mech:2001:HAR, author = "Radom{\'\i}r Mech", title = "Hardware-accelerated real-time rendering of gaseous phenomena", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "3", pages = "1--16", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Apr 11 07:08:39 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Mech01/", abstract = "In this paper, the problem of rendering a gas in real time is approached by placing specific constraints on the distribution of densities and colors inside the gas. A multi-pass algorithm for real-time rendering of a gas defined by a three-dimensional boundary is presented. The density and the color of the gas inside the boundary may be constant, or the color of a dense gas can be defined by a texture. This algorithm is combined with an existing algorithm for rendering layered fog so that the density and color inside the three-dimensional boundary can vary along a single axis. Despite the constraints, the algorithms can be used to render a variety of volumetric phenomena in real time. The OpenGL implementation of the algorithm presented in this paper is used in SGI's Performer, Version 2.4, released in November 2000.", acknowledgement = ack-nhfb, } @Article{Jin:2001:CSL, author = "Xiaogang Jin and Chiew-Lan Tai and Jieqing Feng and Qunsheng Peng", title = "Convolution surfaces for line skeletons with polynomial weight distributions", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "3", pages = "17--28", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Apr 11 07:08:39 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/JinEtAl01/", abstract = "Convolution surfaces generalize point-based implicit surfaces to incorporate higher-dimensional skeletal elements; line segments can be considered the most fundamental skeletal elements since they can approximate curve skeletons. Existing analytical models for line-segment skeletons assume uniform weight distributions, and thus they can produce only constant-radius convolution surfaces. This paper presents an analytical solution for convolving line-segment skeletons with a variable kernel modulated by a polynomial function, allowing generalized cylindrical convolution surfaces to be modeled conveniently. Its computational requirement is competitive with that of uniform weight distribution. The source code of the field computation is available online.", acknowledgement = ack-nhfb, } @Article{Max:2001:CSC, author = "Nelson Max", title = "Consistent subdivision of convex polyhedra into tetrahedra", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "3", pages = "29--36", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Apr 11 07:08:39 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/Max01/", abstract = "This paper presents a simple method of subdividing a grid of convex polyhedral cells into tetrahedra such that the subdivision of two adjacent cells divide their common face into the same set of triangles. The method is then generalized to grids of convex polytopes in $n$ dimensions.", acknowledgement = ack-nhfb, } @Article{Wiseman:2001:CEC, author = "Yair Wiseman and Erick Fredj", title = "Contour extraction of compressed {JPEG} images", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "3", pages = "37--43", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Apr 11 07:08:39 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/WisemanFredj01/", abstract = "We present a new algorithm that uses the JPEG compression format and provides a significant improvement in contour extraction for medical imaging, such as X-ray photos. The algorithm searches for an object's contour in the compressed file. The complexity is reduced to $O(n)$ in the case of a high resolution picture, which is better than the state-of-the-art for contour extraction.", acknowledgement = ack-nhfb, } @Article{Andersen:2001:TDP, author = "Clark R. Andersen and William L. {Buford, Jr.}", title = "The three-dimensional parametric ellipse", journal = j-J-GRAPHICS-TOOLS, volume = "6", number = "3", pages = "45--48", year = "2001", CODEN = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Apr 11 07:08:39 2002", bibsource = "http://www.acm.org/jgt/issues.html", URL = "http://www.acm.org/jgt/papers/AndersenBuford01/", abstract = "The common approach to generating an arbitrarily oriented ellipse or circle in three dimensions is to generate it first in two dimensions, then transform the result into the desired position and orientation. We present a technique to model the ellipse directly as a three-dimensional parametric function, a constrained variation of a Lissajous curve, avoiding the need for subsequent transformations.", acknowledgement = ack-nhfb, } @Article{Nielsen:2002:FTB, author = "Kasper H{\o}y Nielsen and Niels J{\o}rgen Chris