Complex 3D virtual scenes such as CAD models of airplanes and representations of the human body are notoriously hard to visualize. Those models are made of many parts, pieces and layers of varying size, that partially occlude or even fully surround one another. We introduce Gimlenses, a multi-view, detail-in-context visualization technique that enables users to navigate complex 3D models by interactively drilling holes into their outer layers to reveal objects that are buried, possibly deep, into the scene. Those holes get constantly adjusted so as to guarantee the visibility of objects of interest from the parent view. Gimlenses can be cascaded and constrained with respect to one another, providing synchronized, complementary viewpoints on the scene. Gimlenses enable users to quickly identify elements of interest, get detailed views of those elements, relate them, and put them in a broader spatial context.

Focus+context lens-based techniques smoothly integrate two levels of detail using spatial distortion to connect the magnified region and the context. Distortion guarantees visual continuity, but causes problems of interpretation and focus targeting, partly due to the fact that most techniques are based on statically-defined, regular lens shapes, that result in far-from-optimal magnification and distortion. JellyLenses dynamically adapt to the shape of the objects of interest, providing detail-in-context visualizations of higher relevance by optimizing what regions fall into the focus, context and spatially-distorted transition regions. This both improves the visibility of content in the focus region and preserves a larger part of the context region. We describe the approach and its implementation, and report on a controlled experiment that evaluates the usability of JellyLenses compared to regular fisheye lenses, showing clear performance improvements with the new technique for a multi-scale visual search task.

Visibility problems are central to many computer graphics applications. The most common examples include hidden-part removal for view computation, shadow boundaries, mutual visibility of objects for lighting simulation. In this paper, we present a theoretical study of 3D visibility properties for scenes of smooth convex objects. We work in the space of light rays, or more precisely, ofmaximal free segments. We group segments that "see" the same object; this defines the3D visibility complex. The boundaries of these groups of segments correspond to thevisual eventsof the scene (limits of shadows, disappearance of an object when the viewpoint is moved, etc.). We provide a worst case analysis of the complexity of the visibility complex of 3D scenes, as well as a probabilistic study under a simple assumption for "normal" scenes. We extend the visibility complex to handle temporal visibility. We give an output-sensitive construction algorithm and present applications of our approach.

Visualization of very complex scenes can be significantly accelerated using occlusion culling. In this paper we present a visibility preprocessing method which efficiently computes potentially visible geometry for volumetric viewing cells. We introduce novel extended projection operators, which permits efficient and conservative occlusion culling with respect to all viewpoints within a cell, and takes into account the combined occlusion effect of multiple occluders. We use extended projection of occluders onto a set of projection planes to create extended occlusion maps; we show how to efficiently test occludees against these occlusion maps to determine occlusion with respect to the entire cell. We also present an improved projection operator for certain specific but important configurations. An important advantage of our approach is that we can re-project extended projections onto a series of projection planes (via an occlusion sweep), and accumulate occlusion information from multiple blockers. This new approach allows the creation of effective occlusion maps for previously hard-to-treat scenes such as leaves of trees in a forest. Graphics hardware is used to accelerate both the extended projection and reprojection operations. We present a complete implementation demonstrating significant speedup with respect to view-frustum culling only, without the computational overhead of on-line occlusion culling.

Recent hierarchical global illumination algorithms permit the generation of images with a high degree of realism. Nonetheless, appropriate refinement of light transfers, high quality meshing, and accurate visibility calculation can be challenging tasks. This is particularly true for scenes containing multiple light sources and scenes lit mainly by indirect light. We present solutions to these problems by extending a global visibility data structure, the Visibility Skeleton. This extension allows us to calculate exact point-to-polygon form-factors at vertices created by subdivision. The structures also provides visibility information for all light interactions, allowing intelligent refinement strategies. High-quality meshing is effected based on a perceptualy based ranking strategy which results in appropriate insertions of discontinuity curves into the meshes representing illumination. We introduce a hierarchy of triangulations that allows the generation of a hierarchical radiosity solution using accurate visibility and meshing. Results of our implementation show that our new algorithm produces high quality view-independent lighting solutions for direct illumination, for scenes with multiple lights and also scenes lit mainly by indirect illumination.

Data structures baaed on uniform subdivisions of the space ---&o known as bucketing-have the nice properties that they can be walked through very easily and can provide neighborhood relations at low cost.For data sets which are uniformly scattered in 2D or 3D space, this makes the imple- mentation of algorithms such as ray tracing, nearest neighbors computation or Delaunay triangulation almost trivial.But should the processed data set admit dense clusters, the spatial partitioning does not result in data partitioning so that the performzmces are collapsing.Although it has been known for a long time in dimension one that recursive bucket-sort admits a linear complexity for a wide rage of probability densities, recursive bucketlike data structures have not received any attention in the computational geometry community.It has been observed in computer graphics that these were the fastest to ray-trace, but the question of understanding why they are not just another space partitioning data structure but rather the only data structure that succeeds in capturing the probabilistic properties of data distribution remains open.This paper is a first step in this direction and investigates hierarchical recursive and non recursive data structures for ray-tracing.First, we show that precisely analyzing an optimized ray-tracer is a difficult task due to the context sensitivity of the calls costs of the functions called most often.Second, we exhibit statistics showing that if uniform grids are definitely not the right data structure to use for non-uniform dktributions, recursive grids are very good at handling such distributions.Third, we present several improvements of the Hierarchy of Uniform Grids data structure, which result for the best cases in running times improved by up to a factor three with reference to the previously best known solution.

No abstract available.

Many problems in computer graphics and computer vision require accurate global visibility information.Previous approaches have typically been complicated to implement and numerically unstable, and often too expensive in storage or computation.The Visibility Skeleton is a new powerful utility which can efficiently and accurately answer visibility queries for the entire scene.The Visibility Skeleton is a multi-purpose tool, which can solve numerous different problems.A simple construction algorithm is presented which only requires the use of well known computer graphics algorithmic components such as ray-casting and line/plane intersections.We provide an exhaustive catalogue of visual events which completely encode all possible visibility changes of a polygonal scene into a graph structure.The nodes of the graph are extremal stabbing lines, and the arcs are critical line swaths.Our implementation demonstrates the construction of the Visibility Skeleton for scenes of over a thousand polygons.We also show its use to compute exact visible boundaries of a vertex with respect to any polygon in the scene, the computation of global or on-the-fly discontinuity meshes by considering any scene polygon as a source, as well as the extraction of the exact blocker list between any polygon pair.The algorithm is shown to be manageable for the scenes tested, both in storage and in computation time.To address the potential complexity problems for large scenes, on-demand or lazy contruction is presented, its implementation showing encouraging first results.

No abstract available.

Abstract The radiosity method is particularly suitable for global illumination calculations in static environments. Nonetheless, recent applications of image synthesis such as architectural simulation or lighting design require the ability to modify environments. Previous methods have attempted to deal with dynamic environments (environments where the geometry, the material properties, etc., can change)but still suffer some limitations in the case of moving objects. One of the main problems remaining is the efficient and accurate detection of which form factors must really be recomputed, since their calculation is the most time‐consuming part of the radiosity method. To correctly understand and solve this problem, we start with a method in 2D for polygonal scenes using the visibility complex. It is a powerful data structure representing the visibility relationships between objects in the plane. We have developed and implemented an algorithm which uses this structure to efficiently compute the discontinuity mesh and the form factors for static scenes. We also propose an extension to our algorithm to efficiently update only the modified form factors when an object is moving. This approach enhances our understanding and will hopefully lead to efficient solutions in 3D.

Abstract: This paper presents a method of constraining physically‐based deformable objects. In this method, an object can be defined locally in terms of kinetic and dynamic (mass, position, speed), and physical parameters (compressibility, elasticity, motor functioning). Several problems are solved: constant volume deformation, displacement constraints (fixed or moving required positions), and real object modelling. An object is described by a set of mass points on its contour. The evolution algorithm runs in two phases dealing successively with forces and constraints (which are presented as reaction forces). The main contribution of the method is the control of object volumes during evolution. We define a function that explicitly gives the inside volume of an object in order to use it as a constraint. Thus, the volume can be kept exactly constant during deformation without using an iterative process, in opposition to lagrangian approaches. Some results are illustrated by examples at the end of the paper.

No abstract available.

Abstract Data structures that handle very complex scenes (hundreds of thousands of objects) have in the past either been laboriously built by hand, or have required the determination of unintuitive parameter values by the user. It is often the case that an incorrect choice of these parameters can result in greedy memory requirements or severely degraded performance. As a remedy to this problem we propose a new data structure which is fully automatic since it does not require the user to determine any input parameters. The structure is built by first filtering the input objects by size, subsequently applying a clustering step to objects of the same size and finally building a hierarchy of uniform grids . We then show that this data structure can be efficiently constructed. The implementation of the shows that the new structure is stable since it's memory requirements grow linearly with the size of the scene, and that it presents a satisfactory compromise between memory usage and computational efficiency. A detailed comparison with previous data structures is also presented in the results.

Abstract We propose an integrated set of methods for designing and animating bodies whose deformable flesh coats an articulated skeleton. The proposed methods provide good automatic positioning of the ‘skin’ after movements, and automatic deformation after collisions with rigid or deformable objects (dynamic or static). The response to collisions includes a feedback from the flesh to the skeleton, whose movement is adequately modified. Moreover, coating the skeleton gives an easy solution to closed loop collisions and angle constraints control. Our model is modular and gives some high level control to the user.

We describe the main algorithms used in an interactive lighting simulation program based on a two-pass extension of the radiosity method. The system allows interactive walk-through as other systems based on radiosity calculations. Moreover, it offers increased realism in the lighting effects by use of extended form factors which accounts for "specular reflection of diffuse light", fast production and display of progressively refined images by distribution of the calculations, good quality of the images in the early stages of the refinement by the use of "hardware light sources", "cheap" rendering of some of the specular highlights at any time by use of the built-in specular shading model, lighting modification (color, intensity of the light sources) by use of "negative light", fast simulation of mirror effects and interactive tools for controling the quality of the final image.

We analyse some recent approaches to the global illumination problem by introducing the corresponding reflection operators, and we demonstrate the advantages of a two-pass method. A generalization of the system introduced by Wallace et al. at Siggraph '87 to integrate diffuse as well as specular effects is presented. It is based on the calculation of extended form-factors, which allows arbitrary geometries to be used in the scene description, as well as refraction effects. We also present a new sampling method for the calculation of form-factors, which is an alternative to the hemi-cube technique introduced by Cohen and Greenberg for radiosity calculations. This method is particularly well suited to the extended form-factors calculation. The problem of interactive display of the picture being created is also addressed by using hardware-assisted projections and image composition to recreate a complete specular view of the scene.

We propose a generating function approach to the problem of evaluating the sizes of derived relations in a relational database framework. We present a model of relations and show how to use it to deduce probabilistic estimations of derived relation sizes. These are found to asymptotically follow normal distributions under a variety of assumptions.

Some very impressive results have been obtained in the past few years in plants and trees image synthesis. Some algorithms are largely based on the irregularity and fuzziness of the objects, and use fractals, graftals or particle systems. Others focus on the branching pattern of the trees with emphasis on morphology. Our concern here is the faithfulness of the models to the botanical nature of trees and plants. We present a model which integrates botanical knowledge of the architecture of the trees: how they grow, how they occupy space, where and how leaves, flowers or fruits are located, etc. The very first interest of the model we propose is its great richness: the same procedural methods can produce "plants" as different as weeping willows, fir trees, cedar trees, frangipani trees, poplars, pine trees, wild cherry trees, herbs, etc. Another very important benefit one can derive from the model is the integration of time which enables viewing the aging of a tree (possibility to get different pictures of the same tree at different ages, accurate simulation of the death of leaves and branches for example). The ease to integrate physical parameters such as wind, the incidence of factors such as insects attacks, use of fertilizers, plantation density, and so on makes it a useful tool for agronomy or botany.

A precise analysis of partial match retrieval of multidimensional data is presented. The structures considered here are multidimensional search trees ( k -d-trees) and digital tries ( k -d-tries), as well as structures designed for efficient retrieval of information stored on external devices. The methods used include a detailed study of a differential system around a regular singular point in conjunction with suitable contour integration techniques for the analysis of k -d-trees, and properties of the Mellin integral transform for k -d-tries and extendible cell algorithms.

This paper describes general evaluation methods for "partial-match retrieval" in multikey record files. An expected cost analysis is given for some of the major multidimensional tree structures which have been proposed in the data base and graphics literature.