Database Management for Interactive Display of Large Architectural Models | | BIB^{A} | GZ | GI 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 | | BIB^{A} | PDF | 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 | | BIB^{A} | GZ | GI 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. |
Awareness through fisheye views in relaxed-WYSIWIS groupware | | BIB^{A} | PDF | GI 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 | | BIB | Citation | 39-46 | |
Evan Graham |
The effect of feedback on a color selection interface | | BIB^{K} | Citation | 47-54 | |
Sarah Douglas; Ted Kirkpatrick | |||
Keywords: color models, color selection, direct manipulation, feedback |
Geometric Deformation by Merging a 3D Object with a Simple Shape | | BIB^{A} | GZ | GI 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 | | BIB^{K} | Citation | 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 | | BIB^{A} | GZ | 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 | | BIB^{A} | GZ | GI 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. |
Algebraic loop detection and evaluation algorithms for curve and surface interrogations | | BIB^{A} | PS | 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 | | BIB^{A} | GZ | GI 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 | | BIB^{A} | GZ | GI 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 caustics on non-lambertian surfaces | | BIB^{A} | GZ | GI Online Paper | HTML | 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 | | BIB^{A} | GZ | GI 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 | | BIB^{A} | GZ | GZ | GZ | GI Online Paper | HTML | 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 | | BIB^{A} | GZ | GI 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. |
Painting gradients: free-form surface design using shading patterns | | BIB^{A} | GZ | GI 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 | | BIB^{A} | GZ | GI 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. |
Surface intersection using affine arithmetic | | BIB^{A} | GZ | GI 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 | | BIB^{A} | GZ | GI 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 | | BIB^{A} | GZ | GI 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 | | BIB^{A} | GZ | GI 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. |
Realistic animation of liquids | | BIB^{A} | GZ | GI 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 | | BIB^{A} | GZ | GI 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 | | BIB^{A} | GZ | GI 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. |
Interactive visualization and augmentation of mechanical assembly sequences | | BIB | Citation | 230-237 | |
Rajeev Sharma; Jose Molineros |
Visualizing Geometric Uncertainty of Surface Interpolants | | BIB^{A} | Z | 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 | | BIB^{A} | GZ | GI 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. |