bluuebunny/crossref_metadata_2025 huggingface dataset:
An ACL for a Dynamic System of Agents
Authors: Gaspari M.
Published: March 2003

In this article we present the design of an ACL for a dynamic system of agents. The ACL includes a set of conversation performatives extended with operations to register, create, and terminate agents. The main design goal at the agent–level is to provide only knowledge–level primitives that are well integrated with the dynamic nature of the system. This goal has been achieved by defining an anonymous interaction protocol which enables agents to request and supply knowledge without considering symbol–level issues concerning management of agent names, routing, and agent reachability. This anonymous interaction protocol exploits a distributed facilitator schema which is hidden at the agent–level and provides mechanisms for registering capabilities of agents and delivering requests according to the competence of agents. We present a formal specification of the ACL and of the underlying architecture, exploiting an algebra of actors, and illustrate it with the help of a graphical notation. This approach provides the basis for discussing dynamic primitives in ACL and for studying properties of dynamic multi agent systems, for example concerning the behavior of agents and the correctness of their conversation policies.
A Procedural Description of Geometric Textures by Spectral and Spatial Analysis of Profiles
Authors: Dischler J.‐M. , Ghazanfarpour D.
Published: March 2003

In this paper we describe a method for automatically generating procedural “geometric” textures, using a hybrid (spectral and spatial) analysis of profiles (ID curves). The profile describes a certain height variation for a certain abscissa. We call “geometric” textures a class of textures including “Bump” textures and “hypertextures”. In dealing with this challenge (automatic synthesis), we introduce two new key ideas.

The first is to compute efficiently a compact and procedural description of the texture, by using a spectral (Fourier transform based) and spatial (histogram based) analytical approach of profiles. The resulting texture is defined as a sum of elementary random functions. This sum is generated according to the profile. The procedural description allows the direct computation of the texture values at any co‐ordinates in the Euclidean space and the stochastic aspect of the elementary functions also allows for the processing of highly random textures, with no considerable increase of computation time.

The second key idea consists of using analysis in the particular and more complex case of geometric textures. For most analytical methods, underlying geometry is never considered. Using profiles as models, the resulting geometric texture is obtained by extending this profile to 2D or 3D space. The resulting texture directly matches the supplied 1D model. Hence, our method promises to be a very useful tool for easily and efficiently “modelling” any kind of geometric textures including rocks, bumps, peaks, fur, cotton and so on.
Tree Visualisation and Navigation Clues for Information Visualisation
Authors: Herman Ivan , Delest Maylis , Melancon Guy
Published: March 2003

Information visualisation often requires good navigation aids on large trees, which represent the underlying abstract information. Using trees for information visualisation requires novel user interface techniques, visual clues, and navigational aids. This paper describes a visual clue: using the so‐called Strahler numbers, a map is provided that indicates which parts of the tree are interesting. A second idea is that of “folding” away subtrees that are too “different” in some sense, thereby reducing the visual complexity of the tree. Examples are given demonstrating these techniques, and what the further challenges in this area are.
Anno 2010 – Remembering Our Future: Challenges and Frontiers of Human‐Media Technology as the Kernel for Human‐Centered Computing
Authors: Encarnação José
Published: March 2003

Based on a forecast by Battelle, Human‐Media Technology is one of "technology’s top 10 challenges and opportunities" for the year 2010. The subject hereby is: "Humans live, science finds out how technology conforms". The goal is to develop environments that allow users to cooperate in the most efficient and natural way. Human‐centered systems will have to incorporate people as an explicit design component. This lecture will address the main goals in developing such systems based on their general characteristics and the corresponding enabling technologies: Visualization (seeing the unseen), Virtual and Augmented Reality (environment must be immersive), and also Multimedia (to introduce the combination of visual, auditory and voice data). Examples from applications and case studies will support the clarification of ideas and goals. Several videos will be used to show the impact.

So far, the human‐centered interfaces to accommodate human perception and human response capabilities and limitations will have been presented and discussed. These interfaces allow to integrate the desired amount of immersion and cooperation (CSCW). Based on this, some "hands‐on" life demos will be shown to discuss the state of the art of these technologies, like Virtual Tables (responsive workbenches), special I/O technologies, etc. Some of these demos will be stand‐alone demos; others will show the potential of telecommunication for collaboration by connecting the floor with other locations to demonstrate CSCW‐based visual tele‐applications.
A Collaborative Scene Editor for VRML Worlds
Authors: Lu Tain‐chi , Chiang Chuanwen , Lin Ming‐tang , Lee Chungnan
Published: March 2003

In this paper, we analyze the requirements for a Web‐based collaborative infrastructure within a virtual world. Additionally, we combine several tools and methodologies to propose a flexible and fluid collaborative environment using Java language to create a VRML scene graph. The proposed prototype aims at four aspects: a shared workspace of scene editor, an active entity composition algorithm in Java, collaborative control in the multi‐user environment, and access control mechanism toward the shared data.
A Light Hierarchy for Fast Rendering of Scenes with Many Lights
Authors: Paquette Eric , Poulin Pierre , Drettakis George
Published: March 2003

We introduce a new data structure in the form of a light hierarchy for efficiently ray‐tracing scenes with many light sources. An octree is constructed with the point light sources in a scene. Each node represents all the light sources it contains by means of a virtual light source. We determine bounds on the error committed with this approximation to shade a point, both for the cases of diffuse and specular reflections. These bounds are then used to guide a hierarchical shading algorithm. If the current level of the light hierarchy provides shading of sufficient quality, the approximation is used, thus avoiding the cost of shading for all the light sources contained below this level. Otherwise the descent into the light hierarchy continues.

Our approach has been implemented for scenes without occlusion. The results show important acceleration compared to standard ray‐tracing (up to 90 times faster) and an important improvement compared to Ward’s adaptive shadow testing.
Progressive Iso‐Surface Extraction from Hierarchical 3D Meshes
Authors: Grosso Roberto , Ertl Thomas
Published: March 2003

A multiresolution data decomposition offers a fundamental framework supporting compression, progressive transmission, and level‐of‐detail (LOD) control for large two or three dimensional data sets discretized on complex meshes. In this paper we extend a previously presented algorithm for 3D mesh reduction for volume data based on multilevel finite element approximations in two ways. First, we present efficient data structures which allow to incrementally construct approximations of the volume data at lower or higher resolutions at interactive rates. An abstract description of the mesh hierarchy in terms of a coarse base mesh and a set of integer records offers a high compression potential which is essential for an efficient storage and a progressive network transmission. Based on this mesh hierarchy we then develop a new progressive iso‐surface extraction algorithm. For a given iso‐value, the corresponding iso‐surface can be computed at different levels of resolution. Changing to a higher or coarser resolution will update the surface only in those regions where the volume data is being refined or coarsened. Our approach allows to interactively visualize very large scalar fields like medical data sets, whereas the conventional algorithms would have required at least an order of magnitude more resources.
Getting Rid of Links in Hierarchical Radiosity
Authors: Stamminger M. , Schirmacher H. , Slusallek Ph. , Seidel H.‐P.
Published: March 2003

Hierarchical radiosity with clustering has positioned itself as one of the most efficient algorithms for computing global illumination in non‐trivial environments. However, using hierarchical radiosity for complex scenes is still problematic due to the necessity of storing a large number of transport coefficients between surfaces in the form of links. In this paper, we eliminate the need for storage of links through the use of a modified shooting method for solving the radiosity equation. By distributing only unshot radiosity in each step of the iteration, the number of links decreases exponentially. Recomputing these links instead of storing them increases computation time, but reduces memory consumption dramatically. Caching may be used to reduce the time overhead. We analyze the error behavior of the new algorithm in comparison with the normal gathering approach for hierarchical radiosity. In particular, we consider the relation between the global error of a hierarchical radiosity solution and the local error threshold for each link.
Screen‐Space Constraints for Camera Movements: the Virtual Cameraman
Authors: Jardillier Frank , Languénou Eric
Published: March 2003

This article presents a virtual cameraman which allows us to obtain the whole set of camera movements satisfying user defined constraints specified in the image space and/or constraints on the objects of the scene. This research follows the "Declarative Modelling" approach, which focuses on a 3‐phase modeller concept: description; generation; result exploration.

Our tool is based on a solver using interval arithmetic. The time dimension is treated as another variable, thus constraints can be specified for the total duration of the animation or could last only for a given amount of time. There is no keyframing and no interpolation, thereby, for the solutions obtained, the satisfaction of the specified constraints are guaranteed. Several ways to include time dimension efficiently are discussed.

We claim that the method is simple enough to be implemented easily without the need of any external solver.
Emotion Editing using Finite Elements
Authors: Koch Rolf M. , Gross Markus H. , Bosshard Albert A.
Published: March 2003

This paper describes the prototype of a facial expression editor. In contrast to existing systems the presented editor takes advantage of both medical data for the simulation and the consideration of facial anatomy during the definition of muscle groups. The Cl‐continuous geometry and the high degree of abstraction for the expression editing sets this system apart from others. Using finite elements we achieve a better precision in comparison to particle systems. Furthermore, a precomputing of facial action units enables us to compose facial expressions by a superposition of facial action geometries in real‐time. The presented model is based on a generic facial model using a thin plate and membrane approach for the surface and elastic springs for facial tissue modeling. It has been used successfully for performing facial surgery simulation. We illustrate features of our system with examples from the Visible Human Dataset.™
A New Approach for Direct Manipulation of Free‐Form Curve
Authors: Zheng J.M. , Chan K.W. , Gibson I.
Published: March 2003

There is an increasing demand for more intuitive methods for creating and modifying free‐form curves and surfaces in CAD modeling systems. The methods should be based not only on the change of the mathematical parameters, such as control points, knots, and weights, but also on the user’s specified constraints and shapes. This paper presents a new approach for directly manipulating the shape of a free‐form curve, leading to a better control of the curve deformation and a more intuitive CAD modeling interface. The user’s intended deformation of a curve is automatically converted into the modification of the corresponding NURBS control points and knot sequence of the curve. The algorithm for this approach includes curve elevation, knot refinement, control point repositioning, and knot removal. Several examples shown in this paper demonstrate that the proposed method can be used to deform a NURBS curve into the desired shape. Currently, the algorithm concentrates on the purely geometric consideration. Further work will include the effect of material properties.
A Free Form Feature Taxonomy
Authors: Fontana M. , Giannini F. , Meirana M.
Published: March 2003

In this paper the notion of free form feature for aesthetic design is presented. The design of industrial products constituted by free form surfaces is done by using CAD systems representing curves and surfaces by means of NURBS functions, which are usually defined by low level entities that are not intuitive and require some knowledge of the mathematical language. Similarly to the feature‐based approach adopted by CAD systems for classical mechanical design, a set of high level modelling entities which provides commonly performed shape modifications has been identified. Particularly, the paper suggests a classification of the so‐called detail features for an aesthetic and/or functional characterization of predefined free form surfaces. Feature types are formally described by means of an analytical definition of the surface modification through deformation and elimination laws. A topological classification is then given according to the application domain of such laws. A further sub‐classification of morphological types is then suggested according to geometric properties of weak convexity and concavity for the resulting modified shape, leading to a taxonomy of simple free form features meaningful for aesthetic design.
Weighted Multipass Methods for Global Illumination
Authors: Suykens Frank , Willems Yves D.
Published: March 2003

In multipass rendering, care has to be taken to include all light transport only once in the final solution. Therefore the different methods in current multipass configurations handle a perfectly disjunct part of the light transport. In this paper a Monte Carlo variance reduction technique is presented that probabilistically weights overlapping transport between different methods. A good heuristic for the weights is derived so that strengths of the respective methods are retained. The technique is applied to a combination of radiosity and bidirectional path tracing and significant improvement is obtained over the non‐weighted combination. This method promises to be a very useful extension to other multipass algorithms as well.
Stochastic Iteration for Non‐diffuse Global Illumination
Authors: Szirmay‐Kalos László
Published: March 2003

This paper presents a single‐pass, view‐dependent method to solve the rendering equation, using a stochastic iterational scheme where the transport operator is selected randomly in each iteration. The requirements of convergence are given for the general case. To demonstrate the basic idea, a very simple,continuous random transport operator is examined, which gives back the light tracing algorithm incorporating Russian roulette. Then, a new mixed continuous and finite‐element based iteration method is proposed, which uses ray‐bundles to transfer the radiance in a single random direction. The resulting algorithm is fast, it provides initial results in seconds and accurate solutions in minutes and does not suffer from the error accumulation problem and the high memory demand of other finite‐element and hierarchical approaches.
Interactive Mechanical Design Variation for Haptics and CAD
Authors: Nelson Donald D. , Cohen Elaine
Published: March 2003

A fast design variation technique for mechanical systems is presented. It is used to interactively optimize mechanical characteristics while “self‐assembling” or satisfying large systems of mechanical constraints. The high speed method is central to providing inverse dynamics force feedback in haptics and control applications. Performance advantages with the use of augmented coordinates for inverse dynamics of closed loop topologies are also noted. The interaction framework allows manipulation of complex assemblies while maintaining kinematically admissible configurations though linkage and joint limit constraints. Furthermore, design variables such as link length can be treated as free variables and optimized to meet design criteria such as assembly dexterity. Assemblies with flexible bodies fit naturally within this framework. Thus, the contribution of this paper is the advancement of techniques in augmented coordinates for the kinematic and force feedback interaction with virtual mechanical assembly design optimization at force control rates.
The Hybrid World of Virtual Environments
Authors: Smith Shamus , Duke David , Massink Mieke
Published: March 2003

Much of the work concerned with virtual environments has addressed the development of new rendering technologies or interaction techniques. As the technology matures and becomes adopted in a wider range of applications, there is, however, a need to better understand how this technology can be accommodated in software engineering practice. A particular challenge presented by virtual environments is the complexity of the interaction that is supported, and sometimes necessary, for a particular task. Methods such as finite‐state automata which are used to represent and design dialogue components for more conventional interfaces, e.g. using direct manipulation within a desktop model, do not seem to capture adequately the style of interaction that is afforded by richer input devices and graphical models. In this paper, we suggest that virtual environments are, fundamentally, what are known as hybrid systems. Building on this insight, we demonstrate how techniques developed for modelling hybrid systems can be used to represent and understand virtual interaction in a way that can be used in the specification and design phases of software development, and which have the potential to support prototyping and analysis of virtual interfaces.
An Informed Environment Dedicated to the Simulation of Virtual Humans in Urban Context
Authors: Farenc Nathalie , Boulic Ronan , Thalmann Daniel
Published: March 2003

In this paper, we outline the creation of an Informed Environment, dedicated to urban life simulation.We propose methods and tools for creating and providing the information necessary for animating virtual humans in a city using an Informed Environment. The Informed Environment is based on a hierarchical decomposition of a urban scene into Environment Entities providing geometrical information as well as semantic notions, thus allowing a more realistic simulation of human behaviour. In this manner, virtual humans can integrate with a certain kind of urban knowledge.
Hermitian B‐Splines
Authors: Grisoni Laurent , Blanc Carole , Schlick Christophe
Published: March 2003

This paper proposes to study a spline model, called HB‐splines, that is in fact a B‐spline representation of Hermite splines, combined with some restriction on the differential values at segment boundaries. Although this model does not appear able to offer something new to the computer graphics community, we think that HB‐splines deserve to be considered for themselves because they embed many interesting features. First, they include all the classical properties required in a geometric modeling environment (convex hull, local control, arbitrary orders of parametric or geometric continuity). Second, they have a nice aptitude for direct manipulation (i.e. manipulation without using control points). For this purpose, we propose a new graphic widget, called control sails, that offers the user an intuitive way to specify local properties (position, tangent, curvature) of a curve or a surface. Finally, they provide an elegant formulation of a biorthogonal wavelet family, that permits multiresolution manipulations of the resulting curves or surfaces, in a very efficient way.
Efficient Glossy Global Illumination with Interactive Viewing
Authors: Stamminger Marc , Scheel Annette , Granier Xavier , Perez‐Cazorla Frederic , Drettakis George , Sillion François
Published: March 2003

The ability to perform interactive walkthroughs of global illumination solutions including glossy effects is a challenging open problem. In this paper we overcome certain limitations of previous approaches. We first introduce a novel, memory‐ and compute‐efficient representation of incoming illumination, in the context of a hierarchical radiance clustering algorithm. We then represent outgoing radiance with an adaptive hierarchical basis, in a manner suitable for interactive display. Using appropriate refinement and display strategies, we achieve walkthroughs of glossy solutions at interactive rates for non‐trivial scenes. In addition, our implementation has been developed to be portable and easily adaptable as an extension to existing, diffuse‐only, hierarchical radiosity systems. We present results of the implementation of glossy global illumination in two independent global illumination systems.
A Novel Approach Makes Higher Order Wavelets Really Efficient for Radiosity
Authors: Cuny François , Alonso Laurent , Holzschuch Nicolas
Published: March 2003

Since wavelets were introduced in the radiosity algorithm 5, surprisingly little research has been devoted to higher order wavelets and their use in radiosity algorithms. A previous study 13 has shown that wavelet radiosity, and especially higher order wavelet radiosity was not bringing significant improvements over hierarchical radiosity and was having a very important extra memory cost, thus prohibiting any effective computation. In this paper, we present a new implementation of wavelets in the radiosity algorithm, that is substantially different from previous implementations in several key areas (refinement oracle, link storage, resolution algorithm). We show that, with this implementation, higher order wavelets are actually bringing an improvement over standard hierarchical radiosity and lower order wavelets.
Priority‐Driven Acoustic Modeling for Virtual Environments
Authors: Min Patrick , Funkhouser Thomas
Published: March 2003

Geometric acoustic modeling systems spatialize sounds according to reverberation paths from a sound source to a receiver to give an auditory impression of a virtual 3D environment. These systems are useful for concert hall design, teleconferencing, training and simulation, and interactive virtual environments. In many cases, such as in an interactive walkthrough program, the reverberation paths must be updated within strict timing constraints ‐ e.g., as the sound receiver moves under interactive control by a user. In this paper, we describe a geometric acoustic modeling algorithm that uses a priority queue to trace polyhedral beams representing reverberation paths in best‐first order up to some termination criteria (e.g., expired time‐slice). The advantage of this algorithm is that it is more likely to find the highest priority reverberation paths within a fixed time‐slice, avoiding many geometric computations for lower‐priority beams. Yet, there is overhead in computing priorities and managing the priority queue. The focus of this paper is to study the trade‐offs of the priority‐driven beam tracing algorithm with different priority functions. During experiments computing reverberation paths between a source and a receiver in a 3D building environment, we find that priority functions incorporating more accurate estimates of source‐to‐receiver path length are more likely to find early reverberation paths useful for spatialization, especially in situations where the source and receiver cannot reach each other through trivial reverberation paths. However, when receivers are added to the environment such that it becomes more densely and evenly populated, this advantage diminishes.
Integration of Multidimensional Interaction Devices in Real‐Time Computer Graphics Applications
Authors: Fröhlich Torsten , Roth Marcus
Published: March 2003

Modern CAD/CAM and Virtual Reality applications cannot be imagined without the new class of interaction devices allowing the user direct interaction with computer generated scenes. Integrating such devices into existing or newly developed software is a complex task for a number of reasons. The set of devices is very heterogeneous in functionality and data formats. Most devices are difficult to handle by inexperienced users or need careful handling and calibration. After reviewing a number of existing systems, a novel approach to this problem is presented. A device interface that allows the flexible, hardware independent configuration and error robust operation, even reconfiguration and exchanges of interaction devices during operation, will be introduced. The system structure is discussed and novel communication protocols reducing latency are invented.
Conflict Neutralization on Binary Space Partitioning
Authors: James A. , Day A.M.
Published: March 2003

The Binary Space Partitioning (BSP) tree achieves fast hidden surface removal for most practical applications where an observer can move through a scene of static objects. However, the BSP algorithm generally increases the number of polygons in a scene due to its splitting stage resulting in a detrimental effect on the priority ordering and more significantly, the display calculations (shading, lighting, shadows, etc.) of the rendering pipeline.

We present the Conflict Neutralization algorithm which attempts to reduce the number of splits more effectively than existing techniques whilst maintaining the ‘standard’ model of a BSP tree. Our idea is similar to Conflict Minimization proposed by Fuchs; the significant difference is that our algorithm recognizes that a polygon suitable for selection in the Minimization criterion may subsequently stop the remainder of polygons achieving some reductions in cuts—with Conflict Neutralization, such a polygon is demoted.

We compare the results of Conflict Neutralization against Conflict Minimization, the Least‐crossed with Most‐crossed tie‐breaking criterion and our own, enhanced implementation of Conflict Minimization. We show how these techniques fall into different ‘depths of analysis’.
Automatic Creation of Object Hierarchies for Radiosity Clustering
Authors: Müller Gordon , Schäfer Stephan , Fellner Dieter
Published: March 2003

Using object clusters for hierarchical radiosity greatly improves the efficiency and thus usability of radiosity computations. By eliminating the quadratic starting phase very large scenes containing about 100k polygons can be handled efficiently. Although the main algorithm extends rather easily to using object clusters, the creation of ‘good’ object hierarchies is a difficult task both in terms of construction time and in the way how surfaces or objects are grouped to clusters. The quality of an object hierarchy for clustering depends on its ability to accurately simulate the hierarchy of the energy flow in a given scene. Additionally it should support visibility computations by providing efficient ray acceleration techniques.

In this paper we will present a new approach of building hierarchies of object clusters. Our hybrid structuring algorithm provides accuracy and speed by combining a highly optimized bounding volume hierarchy together with uniform spatial subdivisions for nodes with regular object densities. The algorithm works without user intervention and is well suited for a wide variety of scenes. First results of using these hierarchies in a radiosity clustering environment are very promising and will be presented here.

The combination of very deep hierarchies (we use a binary tree) together with an efficient ray acceleration structure shifts the computational effort away from form factor and visibility calculation towards accurately propagating the energy through the hierarchy. We will show how an efficient single pass gathering can be used to minimize traversal costs.
Triangle Strip Compression
Authors: Isenburg Martin
Published: March 2003

In this paper we introduce a simple and efficient scheme for encoding the connectivity and the stripification of a triangle mesh. Since generating a good set of triangle strips is a hard problem, it is desirable to do this just once and store the computed strips with the triangle mesh. However, no previously reported mesh encoding scheme is designed to include triangle strip information into the compressed representation. Our algorithm encodes the stripification and the connectivity in an interwoven fashion, that exploits the correlation existing between the two.
Guided Exploration with Dynamic Potential Fields: the Cubical Path System
Authors: Beckhaus Steffi , Ritter Felix , Strothotte Thomas
Published: March 2003

Exploring unknown models or scenes is a highly interactive and dynamic process. Systems for automatic presentation of models or scenes either require cinematographic rules, direct human interaction, framesets, or pre‐calculation of paths to a known goal. In this paper we present a system which can deal with rapidly changing user interest in objects of a scene or model as well as with dynamic models and changes of the camera position introduced interactively by the user or through cuts. We describe CubicalPath, a new potential field‐based camera control system that helps with the exploration of virtual environments.
Ray Tracing and Graphics Standards
Authors: Urban B. , Haberstroh T.
Published: March 2003

Existing standards for three‐dimensional graphic representations are unable to produce any realistically shaded images (except PHIGS PLUS, which provides discrete shading only). Ray Tracing or Radiosity are not taken into account up to this time.

This article is intended to show one way to integrate the Ray Tracing technique into the pipeline of the graphics standards GKS‐3D and PHIGS. No modifications of the viewing concepts are required by our implementation.
Pandora: An Experiment in Distributed Multimedia
Authors: King Tony
Published: March 2003

An experimental workstation is described which supports digital video and audio in a distributed environment, and which presents this functionality to the user through the medium of a video‐extended implementation of the X Window System. The Pandora Workstation is built out of two quite separate parts. A standard UNIX machine (the Pandora Host) brings standard hardware and software computing resources to the system; a highly‐specialised processing engine (Pandora's Box) handles the high‐bandwidth, time‐critical, and device‐dependent processing. A 50 Mbit/second ATM network provides for real‐time data communication within the system. Nineteen Pandora Workstations have been deployed within Olivetti Research Ltd and the Cambridge University Computer Laboratory, and are used routinely to run distributed applications including video mail, video conferencing, and real‐time media delivery services.
A Unified Approach for Physical and Geometric Modeling for Graphics and Animation
Authors: Essa Irfan A. , Sclaroff Stan , Pentland Alex
Published: March 2003

We present a unified approach for geometric and physical modeling using implicit functions, for application to graphics and animation. This method extends previously proposed techniques, and allows the standard finite element method to be directly combined with geometric modeling, resulting in quick calculation of an object's mass and stiffness matrices, and its vibration modes and frequencies. Because the approach is based on an implicitfunction representation, it allows very fast collision detection and characterization. Examples of complex physical and geometric modeling are presented.
The Input Model of Standard Graphics Systems Revisited by Formal Specification
Authors: Faconti Giorgio P. , Zani Nicola , Paterno' Fabio
Published: March 2003

This paper describes the specification of an input model for graphics systems. The initial aim of the work reported in this paper was to revise the input model adopted by graphics standards by means of formal specification techniques in order to acquire a deep knowledge of its capabilities, to eventually discover errors and to develop improvements. Taking into account similar works done in this area by others and considering a number of major issues related to input recently discussed within the graphics community, a new model is being proposed that addresses the very key concepts of parallelism, extensibility and reconfigurability. The model is based upon composition operations defined over basic components specified as a set of concurrent processes. Composition operations and process definitions have been formally specified by using the LOTOS notation and investigated by means of the LOTOS Interactive Tools Environment. In the first part of the paper, the input model of graphics standards is shortly examined in the light of the results so far achieved by related works on formal specification of computer graphics systems. Subsequently, an improved model is presented. Finally, its capability of simulating the traditional operating modes of logical input devices and a methodology for defining new operating modes is demonstrated.
Adaptive Sampling of Area Light Sources in Ray Tracing Including Diffuse Interreflection
Authors: Kok Arjan J. F. , Jansen Frederik W.
Published: March 2003

Ray tracing algorithms that sample both the light received directly from light sources and the light received indirectly by diffuse reflection from other patches, can accurately render the global illumination in a scene and can display complex scenes with accurate shadowing. A drawback of these algorithms, however, is the high cost for sampling the direct light which is done by shadow ray testing. Although several strategies are available to reduce the number of shadow rays, still a large number of rays will be needed, in particular to sample large area light sources. An adaptive sampling strategy is proposed that reduces the number of shadow rays by using statistical information from the sampling process and by applying information from a radiosity preprocessing. A further reduction in shadow rays is obtained by applying shadow pattern coherence, i.e. reusing the adaptive sampling pattern for neighboring sampling points.
Fractals and Solid Modeling
Authors: Gröller Eduard
Published: March 2003

Trying to combine fractal geometry and solid modeling seems to be a contradiction in itself, In this paper a new type of 3D objects is presented that accomplishes this combination in a specific way. Objects with a fractal macro structure and a 3D solid micro structure can be specified and rendered efficiently by using context free, attribute, geometric grammars. This new object type can be incorporated into the CSG‐modeling technique (Constructive Solid Geometry) in two ways: a) using CSG for the specification of the micro structure of the new object type, b) using these fractal like objects as a new type of primitive in the CSG model. Ray tracing is used for generating high quality images of these geometrically complex objects.
Performance of Space Subdivision Techniques in Ray Tracing
Authors: McNeill M. D. J. , Shah B. C. , Hebert M.‐P. , Lister P. F. , Grimsdale R. L.
Published: March 2003

Whilst providing images of excellent quality, ray tracing is a computationally intensive task. The first part of this paper compares the speed‐up achieved in ray tracing using various space subdivision algorithms and discusses the implications of implementing the algorithms on parallel processing systems. The second part addresses the problem of building the data structure within the rendering process, a situation which occurs when the rendering process is parallelised and dynamic scenes are rendered. Greater performance can be achieved with dynamic structure building compared to creation of the structure prior to rendering. The dynamic building algorithm proposed reduces the building time and storage cost of space subdivision structures, and decreases the data structure creation‐render cycle time, thus enhancing image parallelism performance.
Modelling and Programming Evolutions of Surfaces
Authors: Chen X. , Lienhardt P.
Published: March 2003

In recent years, a lot of work has been done on modelling natural phenomena and simulating the evolution of natural objects. For instance, procedural methods have been developed for simulating corpuscular phenomena and tree growth. In this paper we present a new procedural method for simulating evolutions of subdivisions of surfaces (i.e. partitions of surfaces into vertices, edges and faces). The representations of topology, embedding and photometry are clearly distinguished in the geometric model used for the representation of such subdivisions and thus, each of these features may be evolved independently (as in natural metamorphoses). Evolutions are achieved by applying topological and embedding operations on the geometric model. Control of these evolutions is based upon the behaviour concept. Behaviours (i.e. sets of operations) are associated with cells of the modelled subdivision. At each step, and for each cell, the corresponding behaviour is applied to the cell. The definition and computation of parameters have been studied, in order to control such evolutions. The method has been implemented and tested with many examples of surface evolutions (mainly evolutions of vegetal surfaces: leaves, flowers). Based on the method, a language has been defined for programming surface evolutions.
The Potential Equation and Importance in Illumination Computations
Authors: Pattanaik S. N. , Mudur S. P.
Published: March 2003

An equation adjoint to the luminance equation for describing the global illumination can be formulated using the notion of a surface potential to illuminate the region of interest. This adjoint equation which we shall call as the potential equation, is fundamental to the adjoint radiosity equation used to devise the importance driven radiosity algorithm. In this paper we first briefly derive the adjoint system of integral equations and then show that the adjoint linear equations used in the above algorithm are basically discrete formulations of the same. We also show that the importance entity of the linear equations is basically the potential function integrated over a patch. Further we prove that the linear operators in the two equations are indeed transposes of each other.
The Cone of Normals Technique for Fast Processing of Curved Patches
Authors: Shirmun Leon A. , Abi‐Ezzi Salim S.
Published: March 2003

The cone of normals technique for curved surface patches allows to perform various quick tests at the patch level such as front‐ or backfacing test, light influence test, and existence of silhouette edges test. For a given patch, a truncated cone of normals is constructed at creation time, which contains all points and all normal directions of the patch. At traversal time, a simple scalar product test determines whether the whole patch is backfacing or frontfacing, so that the costly step of tessellating the patch is avoided in case of patch level face culling. In addition, the technique quickly determines which light sources have no influence on a patch, and which patches have no silhouette edges. The technique can also be used for other surface primitives, such as triangular strips and quadrilateral meshes,
Classification of Ray‐Generators in Uniform Subdivisions and Octrees for Ray Tracing
Authors: Endl Robert , Sommer Manfred
Published: March 2003

Spatial subdivisions cause an enormous acceleration of ray tracing due to the reduction of ray‐object intersections. For this purpose it is necessary to generate the sequence of ray‐cells (all cells met consecutively by a given ray). A method generating this sequence will be called a ray‐generator. First this paper analyses the common properties of ray‐generators in order to establish a classification. Then some well‐known ray‐ generators are described and classified, as well as some new ones. In the sequel nine different ray‐generators are implemented in one single program allowing direct comparisons with the same scene. Finally, global time measurements for two scenes are given, as well as time measurements for random rays enabling the calculation of mean values for the time of initialization and determination of ray‐cells.
A Survey of Shading and Reflectance Models
Authors: Schlick Christophe
Published: March 2003

Since the beginning of computer graphics, three decades ago, a large number of models intended to describe the behaviour of light on a given point of a surface have been proposed. Almost every author uses his own terminology and/or notation. To understand clearly the similarities and the differences between existing models, reformulating them with a unified notation is essential. This has been done by Hall in 1986. This paper is a new survey of shading and reflectance models, including the most recent models. Moreover, after the lengthy enumeration, some original models are proposed, which attempt to include interesting features of previous disjointed work into new formulations.
Towards Context‐ Dependent Interpolation of Digital Elevation Models
Authors: Dixon A.R. , Kirby G.H. , Wills D.P.M.
Published: March 2003

The fractional Brownian motion (fBm) model has become increasingly popular in recent years as a mechanism for the synthesis of many natural phenomena. Unfortunately, the required interdependence of neighbouring points over an unbounded area (context dependence) renders valid approximations to fBm extremely inefficient. This paper describes a technique for the interpolation of digital elevation models to an arbitrarily high spatial resolution. This is achieved using an efficient recursive subdivision algorithm which has the ability to permit some degree of context dependence within, and across the boundaries of interpolation areas. The application of this technique to flight simulation is described and the technique is evaluated based on its ability to reduce run‐time storage requirements.
Adaptive mesh generation for progressive radiosity: A ray‐tracing based algorithm.
Authors: PAULIN Mathias , JESSEL Jean‐Pierre
Published: March 2003

The radiosity method is one of the most popular rendering algorithms. It allows to simulate interreflections of light accurately between surfaces as energy transfers are well designed. However, this algorithm and its derivatives need to break scenes into a relatively large number of small elements to approximate the illumination function. Even with a very large number of elements, not all the illumination effects can be simulated. In fact, there are always artefacts when modelling sharp shadows, besides shadows falling between mesh vertices can be missed entirely. To reduce the computational cost of such methods and to increase the accuracy of the radiosity solution, adaptive mesh generation is well suited. In this paper, we present a ray‐tracing based algorithm for adaptive mesh generation which resolves all the illumination problems without lengthening computation time too much. This method allows a small number of initial elements and increases element density in critical locations while solving the illumination problem.
Cross Scan Buffer and its Applications
Authors: Tanaka Toshimitsu , Takahashi Tokiichiro
Published: March 2003

We propose the Cross Scanline Buffer which preserves the result of hidden surface removal as performed by the Cross Scanline Algorithm. The Cross Scan Buffer reduces image re‐generation time and eliminates aliasing artifacts even if the image is arbitrarily scaled. Perfect anti‐aliasing is achieved because the Cross Scanline Algorithm analytically determines visible polygonal surfaces and divides them into sets of triangles and trapezia. The Cross Scan Buffer supports the various applications that currently use the conventional buffering methods for anti‐aliasing. This paper introduces and tests three applications: image scaling, shadow creation, and texture mapping. Experimental results verify that the Cross Scan Buffer is very powerful yet efficient.
Output‐SensitiveVisibility Algorithms for Dynamic Scenes with Applications to Virtual Reality
Authors: Sudarsky Oded , Gotsman Craig
Published: March 2003

An output‐sensitive visibility algorithm is one whose runtime is proportional to the number of visible graphic primitives in a scene model—not to the total number of primitives, which can be much greater. The known practical output‐sensitive visibility algorithms are suitable only for static scenes, because they include a heavy preprocessing stage that constructs a spatial data structure which relies on the model objects’ positions. Any changes to the scene geometry might cause significant modifications to this data structure. We show how these algorithms may be adapted to dynamic scenes. Two main ideas are used: first, update the spatial data structure to reflect the dynamic objects’ current positions; make this update efficient by restricting it to a small part of the data structure. Second, use temporal bounding volumes (TBVs) to avoid having to consider every dynamic object in each frame. The combination of these techniques yields efficient, output‐sensitive visibility algorithms for scenes with multiple dynamic objects. The performance of our methods is shown to be significantly better than previous output‐sensitive algorithms, intended for static scenes.

TBVs can be adapted to applications where no prior knowledge of the objects’ trajectories is available, such as virtual reality (VR), simulations etc. Furthermore, they save updates of the scene model itself; notjust of the auxiliary data structure used by the visibility algorithm. They can therefore be used to greatly reduce the communications overhead in client‐server VR systems, as well as in general distributed virtual environments.
Modelling Megalithic Sites
Authors: POULET Francois , LUCAS Michel
Published: March 2003

In this paper, we present the MégaFormes project which deals with the modelling of megalithic sites. The goal is to enable virtual visits of megalithic sites and to help archaeologists in picturing the evolution of a monument. A megalithic site is made of a set of elements that can be: fogous, dolmens, chamber tombs, stone alignments or circles. The description of such a site is done in two stages: during the first stage, a draft of the site is drawn, each stone being represented by its bounding box. The second stage allows the user to describe the content of the boxes (the stones).

To describe fogous and chamber tombs, basic models of these monuments are used. These basic types are simplified representations of the monuments (walls only). The models can be modified by changing the dimensions and locations of the walls and by cutting the initial walls into individual stones. The definition of stone alignments or circles calls for the use of a one‐dimensional position vocabulary (along simple geometric primitives or curves). The different elements (alignments, circles, fogous, and chamber tombs) are then combined to obtain the draft of the site. A two‐dimensional vocabulary allowing to position the elements in the site is used. The paper is illustrated with examples obtained with the developed software.