HCI Bibliography Home | HCI Conferences | GI Archive | Detailed Records | RefWorks | EndNote | Hide Abstracts
GI Tables of Contents: 858688899091929394959697989900010203040506

Proceedings of the 1996 Conference on Graphics Interface

Fullname:Proceedings of the 1996 Conference on Graphics Interface
Editors:Wayne A. Davis; Richard Bartels
Location:Toronto, Ontario, Canada
Dates:1996-May-22 to 1996-May-24
Publisher:Canadian Information Processing Society
Standard No:ISBN 0-9695338-5-3; hcibib: GI96
Papers:29
Pages:260
Links:Conference Series Home Page | Online Proceedings
  1. Visualization I
  2. Interaction
  3. Techniques
  4. Modeling and Applications
  5. Rendering
  6. Surfaces I
  7. Surfaces II
  8. Animation
  9. Visualization II

Visualization I

Database Management for Interactive Display of Large Architectural Models BIBAGZGI Online Paper 1-8
  Thomas Funkhouser
This paper describes algorithms for predictive database management used in The UC Berkeley Building Walkthrough System. The algorithms forecast a range of possible observer viewpoints during upcoming frames and use precomputed cell visibility information to determine a set of objects likely to be visible to the observer in the near future. For each of these objects, detail elision techniques determine which levels of detail must be stored in a memory resident cache. Cache management algorithms determine which objects to load into memory from disk, and which to replace when the cache is full. Using these algorithms, the system is able to maintain real-time frame rates during interactive visualization of large building models with furniture and radiosity illumination.
Exploring human visualization of computer algorithms BIBAPDF 9-16
  Sarah Douglas; Christopher Hundhausen; Donna McKeown
Many educators have used Algorithm Visualization (AV) to teach students of computer science about how computer algorithms work. Our study sheds light on two important questions: (a) How do people conceptualize algorithm animations in the first place; and (b) To what extent do such visualizations accord with AV software. In the first half of this study, pairs of graduate students in computer science were asked to construct animations for a simple sort (bubble sort) using ordinary art materials. In the second half, they implemented a bubble sort visualization using an interactive AV program called LENS [1], which allows one to construct and view an animation of any C program. The way in which pairs visualized the same sort differed tremendously from each other and did not accord completely with the animation language provided by LENS. This paper analyzes those differences by a detailed examination of the semantics of the human visualizations, the algorithm code, and the LENS AV language.
An Adaptable Software Architecture for Rapidly Creating Information Visualizations BIBAGZGI Online Paper 17-27
  Rick Kazman; Jeromy Carrière
While data visualization is an increasingly important analysis tool, both in research and commercial communities, the process of creating these visualizations is still quite complex. Visualizations tend to be hand-crafted, each one different from the previous. This paper presents VANISH, a system created to ease the rapid creation of arbitrary data visualizations. VANISH simplifies the creation of visualizations in two ways: by providing a special-purpose visual language, called VaPL, which maps semantic domains to visual domains; and by easing the integration of new semantic and visual domains. The software structure of VANISH emphasizes separation of concerns: we follow the Arch/Slinky metamodel of user interface software by not only separating the underlying semantic domain to be visualized from the dialog and presentation components, but by providing virtual semantic domain and presentation layers. In this way, it is simple to port from one visualization domain to another, and from one presentation component to another. We demonstrate that it is simple to create arbitrary visualizations by implementing several well-known visualization styles such as cone-trees, tree-maps, fisheye views.

Interaction

Awareness through fisheye views in relaxed-WYSIWIS groupware BIBAPDFGI Online Paper 28-38
  Saul Greenberg; Carl Gutwin; Andy Cockburn
Desktop conferencing systems are now shifting from strict view-sharing towards relaxed what-you-see-is-what-I-see" interfaces, where distributed participants in a real time session can view different parts of a shared visual workspace. As with strict view-sharing, people using relaxed-WYSIWIS require a sense of workspace awareness-the up-to-the-minute knowledge about another person's interactions with the shared workspace. The problem is deciding how to provide a user with an appropriate level of awareness of what other participants are doing when they are working in different areas of the workspace. In this paper, we summarize requirements for workspace awareness, identify limitations of existing groupware solutions, and propose as a replacement fisheye views that show both global context and local detail within a single window. Within groupware, these displays provide: a) peripheral awareness of other participants by showing their position and actions in the global context; b) detailed awareness of interactions by assigning multiple focal points for each participant, and by magnifying the areas where they are working. Two groupware prototypes illustrate these concepts: a fisheye graph browser, and a fisheye text viewer."
Virtual pointing on a computer display: non-linear control-display mappings BIBCitation 39-46
  Evan Graham
The effect of feedback on a color selection interface BIBKCitation 47-54
  Sarah Douglas; Ted Kirkpatrick
Keywords: color models, color selection, direct manipulation, feedback

Techniques

Geometric Deformation by Merging a 3D Object with a Simple Shape BIBAGZGI Online Paper 55-60
  Philippe Decaudin
Deformation techniques are often used to model the shape of geometric objects. This paper presents a new geometric deformation technique allowing local deformation of the shape of an object by merging the object with a simple 3D-shape (sphere, ellipsoid,...). Two kinds of effects can be obtained: the simple shape is used to produce either a bump or a dent on the object. The object is deformed so that it includes or it embeds the simple shape. In order to deform the object, the 3D-space where it lies is continuously deformed so that the object is bumped and the shape of the bump corresponds to the simple 3D-shape. If the surfaces of both the original object and the simple shape are smooth (continuously differentiable), the surface of the deformed object is also smooth. Moreover, topological properties of the object are unchanged, and the volume variation of the deformed object is controlled by the volume delimited by the simple shape.
   An interactive deformation tool based on this technique is presented. It comprises a convex 3D-shape and a center (a 3D point included in the shape). The user can interactively control the deformation by changing the parameters of the tool shape and the position of the tool center. Control of the parameters is particularly intuitive.
View synthesis from unregistered 2-D images BIBKCitation 61-69
  Parag Havaldar; Mi-Suen Lee; Gérard Medioni
Keywords: epipolar geometry, image based rendering, projective invariants
Multi-frame thrashless ray casting with advancing ray-front BIBAGZ 70-77
  Asish Law; Roni Yagel
Coherency (data locality) is one of the most important factors that influences the performance of distributed ray tracing systems, especially when object dataflow approach is employed. The enormous cost associated with remote fetches must be reduced to improve the efficiency of the parallel renderer. Objects once fetched should be maximally utilized before replacing them with other objects. In this paper, we describe a parallel volume ray caster that eliminates thrashing by efficiently advancing a rayfront in a front-to-back manner. The method adopts an image-order approach, but capitalizes on the advantages of object-order algorithms as well to almost eliminate the communication overheads. Unlike previous algorithms, we have successfully preserved the thrashless property across a number of incrementally changing screen positions also. The use of efficient data structures and object ordering scheme has enabled complete latency hiding of non-local objects. The sum total of all these result in a scalable parallel volume renderer with the most coherent screen traversal. Comparison with other existing screen traversal schemes delineates the advantages of our approach.
Error diffusion: Wavefront traversal and contrast considerations BIBAGZGI Online Paper 78-86
  Avi Naiman; David Lam
Error diffusion algorithms are used widely to halftone grayscale images. We present three enhancements to the standard approach: wavefront traversal of the pixels, error weights based on the distances to a pixel's neighbors and contrast considerations in determining error weights dynamically. The novel algorithm is demonstrated to yield improved detail over standard and serpentine error diffusion and to provide greater control over the contrast in the halftone image.

Modeling and Applications

Algebraic loop detection and evaluation algorithms for curve and surface interrogations BIBAPS 87-94
  Shankar Krishnan; Dinesh Manocha
Evaluating curves on surfaces is a frequently occurring operation in a number of applications involving surface interrogations. For example, evaluating the intersection curve of two surfaces is critical to boundary (B-rep) computation, and in applications involving visibility and rendering, the ability to evaluate the silhouette curve of surfaces is important. While dealing with high degree surfaces, these curves usually consist of a number of components, including loops. We present a new algebraic loop characterization algorithm that can be applied in a number of applications. In particular, we discuss its application to the intersection curve of two surfaces and the silhouette curve of a surface. Unlike some other loop detection algorithms, our method can be applied even when the curve contain(s) singularities.
Programming Support for Blossoming BIBAGZGI Online Paper 95-106
  Wayne Liu; Stephen Mann
A C++ library has been created to facilitate prototyping of curve and surface modeling techniques. The library provides blossoming datatypes to support creation of modeling techniques based on blossoming analysis. The datatypes have efficient operations that are generalizations of important CAGD algorithms and can be used to implement many algorithms. Most importantly, the library is able to inter-operate with user-supplied datatypes or routines to create complex modeling techniques.
Spatial bounding of self-affine iterated function system attractor sets BIBAGZGI Online Paper 107-115
  Jonathan Rice
An algorithm is presented which, given the parameters of an Iterated Function System (IFS) which uses affine maps, constructs a closed ball which completely contains the attractor set of the IFS. These bounding balls are almost always smaller than those computed by existing methods, and are sometimes much smaller. The algorithm is numerical in form, involving the optimisation of centre-point and radius relationships between the overall bounding ball and a set of smaller, contained balls which are derived by analysis of the contractive maps of the IFS. The algorithm is well-behaved, in that although it converges toward an optimal ball which it only achieves in the limit, the process may still be stopped after any finite number of steps, with a guarantee that the sub-optimal ball which is returned will still bound the attractor.

Rendering

Rendering caustics on non-lambertian surfaces BIBAGZGI Online PaperHTML 116-121
  Henrik Wann Jensen
This paper presents a new technique for rendering caustics on non-Lambertian surfaces. The method is based on an extension of the photon map which removes previous restrictions limiting the usage to Lambertian surfaces. We add information about the incoming direction to the photons and this allows us to combine the photon map with arbitrary reflectance functions. Furthermore we introduce balancing of the photon map which not only reduces the memory requirements but also significantly reduces the rendering time. We have used the method to render caustics on surfaces with reflectance functions varying from Lambertian to glossy specular.
A complete treatment of D1 discontinuities in a discontinuity mesh BIBAGZGI Online Paper 122-131
  Sherif Ghali; James Stewart
This paper presents a treatment of first-order discontinuities (D1) that arise in discontinuity meshes. An algorithm is described that, given a planar D1 discontinuity surface in a polyhedral scene, computes the corresponding discontinuity curves on the faces of the scene. A method is described to efficiently update the backprojection across a D1 discontinuity curve. An alternative update method is presented which is novel and numerically robust.
Fast rendering of complex environments using a spatial hierarchy BIBAGZGZGZGI Online PaperHTML 132-141
  Bradford Chamberlain; Tony DeRose; Dani Lischinski; David Salesin; John Snyder
We present a new method for accelerating the rendering of complex static scenes. The technique is applicable to unstructured scenes containing arbitrary geometric primitives and has sublinear asymptotic complexity. Our approach is to construct a spatial hierarchy of cells over the scene and to associate with each cell a simplified representation of its contents. The scene is then rendered using a traversal of the hierarchy in which a cell's approximation is drawn instead of its contents if the approximation is sufficiently accurate. We apply the method to several different scenes and demonstrate significant speedups with little image degradation. We also exhibit and discuss some of the artifacts that our approximation may cause.
Hierarchical Visibility Culling for Spline Models BIBAGZGI Online Paper 142-150
  Subodh Kumar; Dinesh Manocha
We present hierarchical algorithms for visibility culling of spline models. This includes back-patch culling, a generalization of back-face culling for polygons to splines. These algorithms are extended to trimmed surfaces as well. We propose different spatial approximations for enclosing the normals of a spline surface and compare them for efficiency and effectiveness on different graphics systems. We extend the culling algorithms using hierarchical techniques to collection of surface patches and combine them with view-frustum culling to formulate a ONE (Object-Normal Exclusion)-tree for a given model. The algorithm traverses the ONE-tree at run time and culls away portions of the model not visible from the current viewpoint. These algorithms have been implemented and applied to a number of large models. In practice, we are able to speed-up the overall spline rendering algorithms by about 20-30% based on back-patch culling only and by more than 50% using ONE-trees.

Surfaces I

Painting gradients: free-form surface design using shading patterns BIBAGZGI Online Paper 151-158
  C. W. A. M. van Overveld
An interactive system for designing curved surfaces is proposed which is based on direct manipulation of a single-view shaded image of this surface. Apart from functions like carving in the surface or adding to it, and local smoothing, sharpening or shifting of selected surface regions, the system supports painting local gradient distributions.
   An iterative algorithm enforces conservativity of the gradient map at all times, so that the shaded image corresponds everywhere to a possible 3-dimensional surface. This surface can be output either as a gradient map, to be used e.g. in bump mapping, or as an adaptively tiled triangular mesh.
Interactive construction of smoothly blended star solids BIBAGZGI Online Paper 159-167
  Ergun Akleman
We introduce a computationally efficient method for interactive construction of implicitly represented star solids. These solids smoothly approximate control shapes that are defined by exact union and intersections over half-spaces containing the origin. Based on our algorithm, computation of a new solid shape when a new half-space is added or when the position of an existing half-space is changed can be performed in constant time and in space linear in the number of half-spaces.
   Our implicit shape construction is based on a family of non-polynomials called ray-linears [Akle93b]. Computation of an implicitly represented shape is a root finding process and in general can be extremely difficult. However since ray-linear implicit representations can easily be parameterized, the computation of any ray-linearly represented shape simplifies to evaluation of a parametric equation instead of root finding. But the related parametric equations are non-polynomials and their complexity increases as the number of building blocks (in this case half-spaces) increases. Our algorithm makes the computation of this parametric equation independent of the number of half-spaces. We develop an interactive platform based on our algorithm with which we are able to construct star solids that resemble human faces.

Surfaces II

Surface intersection using affine arithmetic BIBAGZGI Online Paper 168-175
  Luiz Henrique de Figueiredo
We describe a variant of a domain decomposition method proposed by Gleicher and Kass for intersecting and trimming parametric surfaces. Instead of using interval arithmetic to guide the decomposition, the variant described here uses affine arithmetic, a tool recently proposed for range analysis. Affine arithmetic is similar to standard interval arithmetic, but takes into account correlations between operands and sub-formulas, generally providing much tighter bounds for the computed quantities. As a consequence, the quadtree domain decompositions are much smaller and the intersection algorithm runs faster.
A technique for constructing developable surfaces BIBAGZGI Online Paper 176-185
  Meng Sun; Eugene Fiume
Paper, sheet metal, and many other materials are approximately unstretchable. The surfaces obtained by bending these materials can be flattened onto a plane without stretching or tearing. More precisely, there exists a transformation that maps the surface onto the plane, after which the length of any curve drawn on the surface remains the same. Such surfaces, when sufficiently regular, are well known to mathematicians as developable surfaces. While developable surfaces have been widely used in engineering, design and manufacture, they have been less popular in computer graphics, despite the fact that their isometric properties make them ideal primitives for texture mapping, some kinds of surface modelling, and computer animation. Unfortunately, their constrained isometric behaviour cuts across common surface formulations. We formulate a new developable surface representation technique suitable for use in interactive computer graphics. The feasibility of our model is demonstrated by applying it to the modelling of a hanging scarf and ribbons and bows. Possible extensions and interesting areas of further research are discussed.
Triangular B-Splines for Blending & Filling of Polygonal Holes BIBAGZGI Online Paper 186-193
  Ron Pfeifle; Hans-Peter Seidel
Triangular B-splines lend themselves naturally to problems such as blending and the filling of polygonal holes. Here we present an automatic method for smoothly blending piecewise polynomial surfaces using triangular B-splines.
   The method proceeds in two phases. In the first phase, the domain of the region to be blended or filled is triangulated and populated with basis functions. In the second phase, coefficients for these basis functions are found by minimizing a functional that measures the curvature of the blending or filling surface.
   Examples are provided that show the use of this method for a number of blending and filling problems.
Topological Evolution of Surfaces BIBAGZGI Online Paper 194-203
  Douglas DeCarlo; Jean Gallier
This paper presents a framework for generating smooth-looking transformations between pairs of surfaces that may differ in topology. The user controls the transformation by specifying a sparse control mesh on each surface and by associating each face in one control mesh with a corresponding face in the other. The algorithm builds a transformation from this information in two steps. The first step constructs a series of shapes and meshes (according the theory of topological surgery) that describes how topological changes should occur at critical points during the transformation. This makes possible the second step, which establishes smooth transformations by combining intermediate shapes in this series. Control meshes allow the user precise but intuitive control of the morph, while the 3D surfaces that result can be used for rendering or keyframing.

Animation

Realistic animation of liquids BIBAGZGI Online Paper 204-212
  Nick Foster; Dimitri Metaxas
We present a comprehensive methodology for realistically animating liquid phenomena. Physically accurate 3D motion is achieved by performing a two-stage calculation over an arbitrary environment of static obstacles surrounded by fluid. A finite difference approximation to the Navier-Stokes equations is first applied to a low resolution, voxelized representation of the scene. The resulting velocity and pressure fields describe the gross transport of liquid, including effects such as splashing, vorticity and overturning. Local fluid velocity is then used to drive a height field equation or to convect massless marker particles. The position of any free surface can thus be determined to a significantly higher resolution than that of the Navier-Stokes calculation. In addition, the pressure field, together with the Lagrange equations of motion, is used to simulate dynamic buoyant objects. Typical disadvantages to volumetric methods such as poor scalability and lack of control are addressed by assuming that stationary obstacles align with grid cells during the finite difference discretization, and by appending driving functions to the Navier-Stokes equations. The output from our system is suitable for many of the water rendering algorithms presented by researchers in recent years.
Knowledge-driven, interactive animation of human running BIBAGZGI Online Paper 213-221
  Armin Bruderlin; Tom Calvert
A high-level motion control system for the animation of human-like figures is introduced which generates a wide variety of individual running styles in real time. Sequences such as a leisurely jog, a fast sprint or a bouncy run are conveniently obtained by interactively setting the values of ''running'' parameters such as desired velocity, step length, ''flight'' height or ''heel/toe'' strike while observing a running figure on the screen.
   The algorithm incorporates knowledge of how humans run at several levels: empirical knowledge defines the relationships between the running parameters; for example, a change in running velocity by the user triggers a change in step length to maintain a ''natural'' running stride. Physical knowledge calculates the trajectory of the body for the current running step. Knowledge about limb-coordination of a running stride is utilized for establishing both, state-constraints which define the support and flight states, and phase-constraints to ''guide'' the internal joint-angle interpolation for the stance and swing phases.
Emotion from Motion BIBAGZGI Online Paper 222-229
  Kenji Amaya; Armin Bruderlin; Tom Calvert
This paper introduces a model to generate ''emotional'' animation from ''neutral'' human motion. Using techniques from signal processing, our method calculates certain emotional transforms which are then applied to existing motions of articulated figures in order to produce the same motions, but with an emotional quality such as angry or sad. These transforms capture the difference between a neutral and emotional movement with respect to two components: speed (timing), and spatial amplitude (range) of a movement.
   Since the transforms are applied as global operations, they provide a convenient and efficient way to adapt motion-captured, simulated or keyframed animation of articulated figures to different situations and characters.

Visualization II

Interactive visualization and augmentation of mechanical assembly sequences BIBCitation 230-237
  Rajeev Sharma; Jose Molineros
Visualizing Geometric Uncertainty of Surface Interpolants BIBAZ 238-245
  Suresh Lodha; Robert Sheehan; Alex Pang; Craig Wittenbrink
Evaluating and comparing the quality of surface interpolants is an important problem in computer graphics, computer aided geometric design and scientific visualization. We introduce geometric uncertainty as a measure of interpolation error, level of confidence or quality of an interpolant. Geometric uncertainty can be estimated as a scalar or a vector-valued function that depends upon geometric characteristics of interpolants associated with the underlying data. These characteristics include position, normals, isophotes, principal curvatures and directions, mean and Gaussian curvatures. We present several new techniques for visualizing geometric uncertainty of surface interpolants, that combine the strengths of traditional techniques such as pseudo-coloring, differencing, overlay, and transparency with new glyph and texture-based techniques.
Visualization of developmental processes by extrusion in space-time BIBAGZGI Online Paper 246-258
  Mark Hammel; Przemyslaw Prusinkiewicz
Developmental processes in nature may involve complex changes in the topology, shape, and patterns of growing structures. Processes taking place in one or two dimensions can be visualized as objects in three-dimensional space, obtained by extruding the growing structures along a line or curve representing the progress of time. In this paper, we extend the notion of L-systems with turtle interpretation to facilitate the construction of such objects. This extension is based on the interpretation of the entire derivation graph generated by an L-system, as opposed to the interpretation of individual words. We illustrate the proposed method by applying it to visualize the development of compound leaves, a sea shell with a pigmentation pattern, and a filamentous bacteria. In addition to serving as visualization examples, these models are of interest on their own. The sea shell model uses an L-system to express a reaction-diffusion process, thus relating these two models of morphogenesis. The model of bacteria, which is also of the reaction-diffusion type, sheds new light on one of the basic problems of morphogenesis, the formation of equally spaced organs in a developing medium.