bluuebunny/crossref_metadata_2025 huggingface dataset:
Operational machine specification in a functional programming language
Authors: Koopman P. W. M. , Eekelen M. C. J. D. Van , Plasmeijer M. J.
Published: November 2006

This paper advocates the use functional programming languages for the formal specification of (abstract) machines. The presented description method describes machines by a two‐level model. At the bottom layer machine components and the micro instructions to handle them are described by using an abstract data type. The top layer describes the machine instructions in terms of these micro instructions.

Using a functional language as specification language has several advantages. The abstraction mechanisms offered by a functional programming language are that good that one can abstract from irrelevant details as is required for a specification language. Functional languages have a well‐defined semantics such that the meaning of the specification is clear as well. Moreover, they offer the advantages of a programming language: the compiler can check the specification for partial correctness, eliminating for example type errors and unbound identifiers (errors which occur in many published descriptions). Furthermore, the specification can be executed such that one obtains a prototype implementation almost for free. Such an executable formal specification can, for instance, be used to investigate the dynamic behaviour of the described machine.

For a simple machine, the proposed description method is compared with several other description methods: a traditional style, a denotational semantics and a formal specification in the language Z. To show that the proposed method is indeed useful to describe large and complicated machines, the method is applied for the specification of an abstract imperative graph rewrite machine (the ABC‐machine) which has been used in the construction of the compiler for the functional language Concurrent Clean.
Using multicast communications to distribute code and data in wide area networks
Authors: Knight Jon , Guest Steve
Published: November 2006

This paper describes the implementation and use of a prototype multicast late‐binding RPC (LbRPC) system. The system provides a mechanism for exporting arbitrary code and data across a wide area internetwork to multiple hosts for evaluation. This mechanism provides a means to ensure that the total execution time for the application is as small as possible without requiring continual monitoring and estimation of the state of the hosts and the intervening network. The impact of sending the same code and data to a group of remote hosts is minimized by using multicast Internet protocol (IP) communications for the outward leg of the transaction. This prototype implementation demonstrates the feasibility of using multicasting for process placement and some performance measurements are included to show how it stands up to usage on the Internet. The paper concludes with a discussion of outstanding issues raised by this research.
Automatic verification of properties in transition systems
Authors: Arnold A. , Brlek S.
Published: November 2006

The aim of this paper is to show the use of MEC, an automated tool for analysing transition systems, for discovering deadlocks, livelocks and other properties of a given transition system. The features of MEC are shown with two instructive examples: first, the analysis of an electronic mail system, first analysed by G. Brebner using the concurrency work bench (another automated analysis tool); second, the analysis of a simple call‐processing system originating from Bell‐Northern‐Research.
Runtime and language support for compiling adaptive irregular programs on distributed‐memory machines
Authors: Hwang Yuan‐Shin , Moon Bongki , Sharma Shamik D. , Ponnusamy Ravi , Das Raja , Saltz Joel H.
Published: November 2006

In many scientific applications, arrays containing data are indirectly indexed through indirection arrays. Such scientific applications are called irregular programs and are a distinct class of applications that require special techniques for parallelization.

This paper presents a library called CHAOS, which helps users implement irregular programs on distributed‐memory message‐passing machines, such as the Paragon, Delta, CM‐5 and SP‐1. The CHAOS library provides efficient runtime primitives for distributing data and computation over processors; it supports efficient index translation mechanisms and provides users high‐level mechanisms for optimizing communication. CHAOS subsumes the previous PARTI library and supports a larger class of applications. In particular, it provides efficient support for parallelization of adaptive irregular programs where indirection arrays are modified during the course of computation. To demonstrate the efficacy of CHAOS, two challenging real‐life adaptive applications were parallelized using CHAOS primitives: a molecular dynamics code, CHARMM, and a particle‐in‐cell code, DSMC.

Besides providing runtime support to users, CHAOS can also be used by compilers to automatically parallelize irregular applications. This paper demonstrates how CHAOS can be effectively used in such a framework. By embedding CHAOS primitives in the Syracuse Fortran 90D/HPF compiler, kernels taken from the CHARMM and DSMC codes have been automatically parallelized.
Parallel 1D‐FFT computation on constant‐valence multicomputers
Authors: Mazzeo Antonino , Villano Umberto
Published: November 2006

This paper addresses the problem of monodimensional (1D) FFT parallel computation on constant‐valence multicomputers, i.e. on parallel systems made up of processing elements (PEs) which do not share memory and are connected to a bounded number of neighbours. After a qualitative analysis of several possible partitionings of the DIT FFT algorithm, a decomposition is introduced that has good scalability properties and makes it possible to use sections of sequential code based on the most common 1D‐FFT algorithms. If a computing architecture with indirect binary n‐cube interconnection network is used, the proposed decomposition guarantees strictly local communications and therefore requires no through‐routing support. These characteristics have a positive impact on software development and also on overall performance. Furthermore, thanks to a pipelined organization of the PEs, the resulting architecture has high potentialities for real‐time signal processing. As these useful features are obtained at the ‘expense’ of an uneven workload distribution, computing efficiency is relatively low but does not significantly change in a wide range of the number of processors. An implementation on a Transputer‐based system is presented along with the performance results obtained. Finally a simple analytical model of the architecture is shown, that allows the values of the main performance parameters to be obtained as a function of the number of processors used and of the elementary response times of the first stage of PEs.
Implementation issues in the development of the parsec parser
Authors: Harper Mary P. , Helzerman Randall A. , Zoltowski Carla B. , Yeo Boon‐Dock , Chan Yin , Stewart Todd , Pellom Bryan L.
Published: November 2006

This paper describes the implementation of a constraint‐based parser, PARSEC (Parallel ARchitecture SEntence Constrainer), which has the required flexibility that a user may easily construct a custom grammar and test it. Once the user designs grammar parameters, constraints, and a lexicon, our system checks them for consistency and creates a parser for the grammar. The parser has an X‐windows interface that allows a user to view the state of a parse of a sentence, test new constraints, and dump the constraint network to a file. The parser has an option to perform the computationally expensive constraint propagation steps on the MasPar MP‐1. Stream and socket communication was used to interface the MasPar constraint parser with a standard X‐windows interface on our Sun Sparcstation.

The design of our heterogeneous parser has benefitted from the use of object‐oriented techniques. Without these techniques, it would have been more difficult to combine the processing power of the MasPar with a Sun Sparcstation. Also, these techniques allowed the parser to gracefully evolve from a system that operated on single sentences, to one capable of processing word graphs containing multiple sentences, consistent with speech processing. This system should provide an important component of a real‐time speech understanding system.
Signatures: A language extension for improving type abstraction and subtype polymorphism in C++
Authors: Baumgartner Gerald , Russo Vincent F.
Published: November 2006

C++ uses inheritance as a substitute for subtype polymorphism. We give examples where this makes the type system too inflexible. We then describe a conservative language extension that allows a programmer to define an abstract type hierarchy independent of any implementation hierarchies, to retroactively abstract over an implementation, and to decouple subtyping from inheritance. This extension gives the user more of the flexibility of dynamic typing while retaining the efficiency and security of static typing. Withdefault implementationsandviewsflexible mechanisms are provided for implementing an abstract type by different concrete class types. We first show how the language extension can be implemented in a preprocessor to a C++ compiler, and then detail and analyse the efficiency of an implementation we directly incorporated in the GNU C++ compiler.
Adding compression to a full‐text retrieval system
Authors: Zobel Justin , Moffat Alistair
Published: November 2006

We describe the implementation of a data compression scheme as an integral and transparent layer within a full‐text retrieval system. Using a semi‐static word‐based compression model, the space needed to store the text is under 30 per cent of the original requirement. The model is used in conjunction with canonical Huffman coding and together these two paradigms provide fast decompression. Experiments with 500 Mb of newspaper articles show that in full‐text retrieval environments compression not only saves space, it can also yield faster query processing ‐ a win‐win situation.
The heart of IGES
Authors: Kahrs Mark
Published: November 2006

This paper describes the problems and complexity of implementing an interpreter for IGES. IGES (the Initial Graphics Exchange Standard) is an attempt to define a language that can specify geometrical, electrical and mechanical specifications with a uniform syntax.

The syntax of IGES is sketched first. This is followed by a short review of the primitives available within IGES. The interior of the interpreter is presented next with particular attention paid to the implementation of the macro language residing inside of IGES.
A prettier compiler‐compiler: Generating higher‐order parsers in C
Authors: Breuer Peter T. , Bowen Jonathan P.
Published: November 2006

Top‐down (LL) context‐sensitive parsers with integrated synthesis and use of attributes are easy to express in functional programming languages, but the elegant functional programming model can also serve as an exact prototype for a more efficient implementation of the technology in ANSI C. The result is a compiler‐compiler that takes unlimited lookahead and backtracking, the extended BNF notation, and parameterized grammars with (higher‐order) meta‐parameters to the world of C programming. This article reports on the utility in question three years after public release.Preccgenerates standard ANSI C and is ‘plug compatible’ withlex‐ generated lexical analyzers prepared for the UNIXyacccompiler‐compiler. In contrast toyacc, however, the generated code is modular, which allows parts of scripts to be compiled separately and linked together incrementally. The constructed code is relatively efficient, as is demonstrated by the example Occam parser treated in depth here, but the main advantages we claim are ease of use, separation of specification and implementation concerns, and maintainability.
A scalability test for parallel code
Authors: Lyon Gordon , Kacker Raghu , Linz Arnaud
Published: November 2006

Code scalability, crucial on any parallel system, determines how well parallel code avoids becoming a bottleneck as its host computer is made larger. The scalability of computer code can be estimated by statistically designed experiments that empirically approximate a multivariate Taylor expansion of the code's execution response function. Each suspected code bottleneck corresponds to a first‐order term in the expansion, the coefficient for that term indicating how sensitive execution is to changes in the suspect location. However, it is the expansion coefficients for second‐order interactions between code segments and the number of processors that are fundamental to discovering which program elements impede parallel speedup. A new, unified view of these second‐order coefficients yields an informal relative scalability test of high utility in code development. Discussion proceeds through actual examples, including a straightforward illustration of the test applied to SLALOM, a complex, multiphase benchmark. A quick graphical shortcut makes the scalability test readily accessible.
A specification case study using the B‐methodology
Authors: Storey Andrew
Published: November 2006

The B‐Method is a complete formal development process for mathematically transforming software systems from specification through to code. This article provides the reader with an overview of the process including a description of the language used for specifying systems (Abstract Machine Notation) and demonstrates its application by a simple, real‐life case study. The method has tool support in the form of a tool‐kit which is described here and applied to the case study. The results of the case study show how a system can be validated and verified in the early stages of its development through proof of the mathematical specification and an animating tool.
Software reliability models—A selected annotated bibliography
Authors: Xie M.
Published: November 2006

Many articles on software reliability models have been published in the last two decades. Because of the importance of this area and increasing interest in it, this annotated bibliography of 100 selected publications has been prepared. First, books, edited works and review papers of general interest are summarized and this is followed by separate introductions to various types of models.
Employing static information in the generation of test cases
Authors: Gupta Rajiv , Soffa Mary Lou
Published: November 2006

A commonly used approach for detecting defects in a program is to generate a suite of test inputs which exercises the entire program under a given testing criterion. Current techniques to generate test cases automatically that satisfy a testing criterion choose test input data by considering the testing requirements in an arbitrary order. In this paper, a technique is presented that groups the requirements and orders the generation of the test cases to reduce the number of test cases generated. The grouping is based on the statically determined property of post‐dominance. Test cases for each group are generated taking into account requirements for other groups. The use of this technique to generate test cases can be expected to produce fewer test cases that have to be retained with the software. A smaller number of test cases will require less effort and resources to test the software. The technique is especially useful in the maintenance environment, whether retesting of a changed program is done exhaustively or incrementally. The technique not only attempts to minimize the number of test cases generated but also reduces the effort to generate the test cases using the concept of a program slice.
Defining testability metrics axiomatically
Authors: Bainbridge John
Published: November 2006

Testability measures have been defined on flowgraphs modelling the control flow through a program. These measures attempt to quantify aspects of the structural complexity of code that might give useful information about the testing stage of software production. This paper shows how two such metrics, the Number of Trails metric and the Mask [k = 2] metric, can be calculated axiomatically.
Transformational program analysis
Authors: Lano K.
Published: November 2006

This paper describes an approach to the semantic analysis of procedural code. The techniques differ from those adopted in current static analysis tools such as MALPAS (Bramson, 1984) and SPADE (Clutterbuck and Carré, 1988) in two key respects: (1) A database is used, together with language‐specific and language‐independent data models, as a repository for all information about a program or set of programs which is required for analysis, and for storing and interrelating the results of analyses; (2) The techniques aim to treat the full language under consideration by a process of successive transformation and abstraction from the source code until a representation is obtained which is amenable to analysis. This abstraction process can include the production of formal specifications from code. The techniques have been partially implemented for the OS/VS IBM diallect of COBOL '74 and for FORTRAN '77. Several components of the resulting toolset have been formally specified in Z, thus meeting some of the integrity requirements for verification tools given in ‘The procurement of safety critical software in defence equipment’ (MoD, 1991). The techniques have been applied in practice to a wide range of source programs and analysis problems (Lano and Haughton, 1993b; Lano, et al., 1991), including assessment problems (Lloyd's Register, 1992, 1993; Hornsby and Eldridge, 1990). Section 1 gives an overview of the analysis process. Section 2 describes the representations used to support the process. Section 3 describes some of the techniques involved, and Section 4 gives examples of applications of the process. The Appendix contains extracts from a large case study carried out using tools developed to support the process.
Re‐designing tasking structures of Ada programs for analysis: A case study
Authors: Yeh Wei Jen , Young Michal
Published: November 2006

In previous publications the authors described a compositional (hierarchical) approach to reachability analysis of Ada tasking programs based on process algebra. The abstraction capabilities of process algebra provide an effective means to control state explosion in automated state‐space analysis, but only if a design is carefully modularized to encapsulate details of behaviour. This paper reports experience modifying an existing design (a remote temperature sensor system described by Sanden) to make it more amenable to hierarchical analysis. Redesign for analysis was effective in improving the design in other ways as well: flaws uncovered in the analysis (and present in the original design) were easy to understand and correct because of the increased understandability of the revised design. This also suggests that these flaws might have been avoided, and the design generally improved, had ‘design for analysis’ been applied from the start.
An experimental evaluation of capture‐recapture in software inspections
Authors: Wohlin Claes , Runeson Per , Brantestam Johan
Published: November 2006

The use of capture‐recapture to estimate the residual faults in a software artifact has evolved as a promising method. However, the assumptions needed to make the estimates are not completely fulfilled in software development, leading to an underestimation of the residual fault content. Therefore, a method employing a filtering technique with an experience factor to improve the estimate of the residual faults is proposed in this paper. An experimental study of the capture‐recapture method with this correction method has been conducted. It is concluded that the correction method improves the capture‐recapture estimate of the number of residual defects in the inspected document.
Exploring the pyridoxal 5′‐phosphate‐dependent enzymes
Authors: Mozzarelli Andrea , Bettati Stefano
Published: November 2006

Pyridoxal 5′‐phosphate (PLP)‐dependent enzymes represent about 4% of the enzymes classified by the Enzyme Commission. The versatility of PLP in carrying out a large variety of reactions exploiting the electron sink effect of the pyridine ring, the conformational changes accompanying the chemical steps and stabilizing distinct catalytic intermediates, and the spectral properties of the different coenzyme‐substrate derivatives signaling the reaction progress, are some of the features that have attracted our interest to investigate the structure–dynamics–function relationships of PLP‐dependent enzymes. To this goal, an integrated approach combining biochemical, biophysical, computational, and molecular biology methods was used. The extensive work carried out on two enzymes, tryptophan synthase and O‐acetylserine sulfhydrylase, is presented and discussed as representative of other PLP‐dependent enzymes we have investigated. Finally, perspectives of PLP‐dependent enzymes functional genomics and drug targeting highlight the continuous novelty of an “old” class of enzymes. © 2006 The Japan Chemical Journal Forum and Wiley Periodicals, Inc. Chem Rec 6: 275–287; 2006: Published online in Wiley InterScience (www.interscience.wiley.com) DOI 10.1002/tcr.20094
Heating and melting deformable models
Authors: Terzopoulos Demetri , Platt John , Fleischer Kurt
Published: November 2006

We develop physically‐based graphics models of non‐rigid objects capable of heat conduction, thermoelasticity, melting and fluid‐like behaviour in the molten state. These deformable models feature non‐rigid dynamics governed by Lagrangian equations of motion and conductive heat transfer governed by the heat equation for non‐homogeneous, non‐isotropic media. In its solid state, the discretized model is an assembly of hexahedral finite elements in which thermoelastic units interconnect particles situated in a lattice. The stiffness of a thermoelastic unit decreases as its temperature increases, and the unit fuses when its temperature exceeds the melting point. The molten state of the model involves a molecular dynamics simulation in which ‘fluid’ particles that have broken free from the lattice interact through long‐range attraction forces and short‐range repulsion forces. We present a physically‐based animation of a thermoelastic model in a simulated physical world populated by hot constraint surfaces.
Rendering hair using pixel blending and shadow buffers
Authors: Leblanc André M. , Turner Russell , Thalmann Daniel
Published: November 2006

A technique is described for adding natural‐looking hair to standard rendering algorithms. Using an explicit hair model, in which each individual hair is represented by a three‐dimensional curve, the technique uses pixel blending combined with Z‐buffer and shadow buffer information from the scene to yield a final anti‐aliased image with soft shadows. Although developed for rendering human hair, this technique can also be used to render any model consisting of long filaments of sub‐pixel width. The technique can be adapted to any rendering method that outputs Z‐buffer and shadow buffer information and is amenable to hardware implementation.
Interference detection through rasterization
Authors: Shinya Mikio , Forgue Marie‐Claire
Published: November 2006

Interference detection is a useful technique, but it is also generally time‐consuming. In this paper, a new type of interference detection algorithm is proposed for real‐time interference detection. The algorithm first rasterizes the projection of the target objects and calculates the z‐values, just as done by the z‐buffer visible surface algorithm. For interference detection, all z‐values and pointers to the corresponding faces of objects are saved in a z‐list for each pixel. Sorting the z‐list against the z‐values allows the detection of overlapping objects in the z‐direction at each pixel position and, thus, finds interfering faces by referring to the face pointers in the z‐list.

The algorithm is simple and easy to implement. Its computational complexity is directly proportional to the number of polygons, and, in addition, standard graphics hardware can be used to greatly accelerate execution. Another advantage is that the algorithm can be applied to all ‘ray‐traceable’ objects, including algebraic surfaces, and procedurally defined objects; traditionally these were not suitable subjects for interference detection.

The algorithm is implemented on a graphics workstation using a standard graphics library. Interference detection at a practical interaction speed is achieved for complicated objects such as polyhedra with thousands of polygons. The algorithm can be used in two ways: for inexpensive interference detection, and as an efficient culling method for more precise collision/interference detection algorithms.
Volume seeds: A volume exploration technique
Authors: Ma Kwan‐Liu , Cohen Michael F. , Painter James S.
Published: November 2006

Ray‐traced volume rendering has been shown to be an effective method for visualizing 3D scalar data. However, with currently available workstation technology, interactive volume exploration using conventional volume rendering is still too slow to be attractive. This paper describes an enhanced volume rendering method which allows interactive changes of rendering parameters such as colour and opacity maps. An innovative technique is provided which allows the user to plant a ‘seed’ in the volume to rapidly modify local shading parameters. For a fixed viewing position, the user can interactively explore specific regions of interest. Furthermore, a virtual cutting technique with the exploratory seed allows the user to remove surfaces and see the internal structure of the volume. Examples demonstrate these techniques as an attractive option in many applications.
Choreographed image flow
Authors: Sims Karl
Published: November 2006

Choreographed fluid‐like motions have been created and used to animate two dimensional images. Techniques are presented for generating these animations by repeatedly warping images using vector field representations of arbitrary flowing motions. Tools that allow interactively creating and aligning vector flow‐fields with images are also described. These methods lend themselves well to highly parallel computation, and have been implemented using the Connection Machine System.
Hanging cloths and dangling rods: A unified approach to constraints in computer animation
Authors: van Overveld C. W. A. M. , van Loon Erik
Published: November 2006

A simple unified approach for dealing with constraints on real‐valued parameters in computer simulations and computer animation is described. The main characteristics of the approach are its flexibility (it works for a variety of constraint‐types and it can be implemented to handle both under‐ and over‐constrained systems in a stable way) and its ease for distributed computation. The method is based on the idea of genetic algorithms. The mathematical merits of the method for one constraint‐type are discussed in some detail and some examples of applications are given.
Shape transformation by boundary representation interpolation: A recursive approach to establishing face correspondences
Authors: Parent Richard E.
Published: November 2006

The issues relating to the shape transformation problem are discussed and a new algorithm is presented for computing the transformation of one shape into another. In this algorithm, the boundary definitions of the two initial shapes are used and a mapping is established between the vertices and edges of the respective objects. New vertices and edges are introduced into the object definitions when necessary to establish a one‐to‐one vertex correspondence and to match connectivity relationships between vertices. These can then be used to do a vertex‐to‐vertex interpolation that maintains valid polyhedral topologies for all of the intermediate shapes. The algorithm establishes a mapping between areas of the object such that adjacency relationships are preserved. These areas are recursively subdivided so that adjacency relationships of subareas are also preserved. During subdivision, vertices and edges are added to the boundaries of subareas so that a one‐to‐one mapping is established between them. Subdivision continues until each subarea consists of a single face. The algorithm presented works for objects that are topologically equivalent to spheres and can easily be extended to other pairs of objects as long as they are topologically equivalent to each other.
NPSNET: Real‐time collision detection and response
Authors: Zyda Michael J. , Pratt David R. , Osborne William D. , Monahan James G.
Published: November 2006

The Graphics and Video Laboratory of the Naval Postgraduate School (NPS) is in the process of constructing a three dimensional (3D) virtual world called NPSNET.1 NPSNET is a low‐cost, commercial workstation‐based 3D visual simulator that uses SIMNET terrain databases and networking.2 NPSNET is programmed using off‐the‐shelf SGI IRIS graphics workstations, rather than the platform‐specific nodes of SIMNET. Part of the work in constructing the NPSNET world is detecting and resolving collisions in real‐time. Such collision detection and resolution has been accomplished and integrated into the latest version of NPSNET, NPSNET‐2. The detection of vehicle‐weapon, vehicle‐vehicle and vehicle‐stationary non‐vehicle collisions is performed throughout the virtual world.
The same origin ray set query for realistic illumination: Algorithm and analysis
Authors: Rappoport Ari
Published: November 2006

The same origin ray set (SORS) is a computational primitive which can be used by ray tracing, radiosity and multiple pass illumination simulation algorithms for realistic image synthesis. A SORS consists of a set of rays emanating from the same point in space. The SORS query computes the first object intersected by each ray and the intersection point. In this paper we present an efficient projection algorithm for computing a SORS query for polygonal scenes. The algorithm achieves its efficiency by separating ray‐polygon intersection detection from the computation of the intersection point between the ray and the polygon's plane. The algorithm can be integrated with all current illumination acceleration schemes. We analyse the projection algorithm and compare it to the alternative of computing the SORS query one ray at a time. The analysis' results are expressed in terms of a few intuitive parameters, measuring the success of the acceleration scheme in culling irrelevant objects and the concentration of the ray set. The projection algorithm can be up to five times more efficient, depending on these parameters and the quality of the image. The relative advantage of the projection increases with image quality.
Advanced object‐oriented methods and concepts for simulations of multi‐body systems
Authors: Kühn Volker , Müller Wolfgang
Published: November 2006

A common way to simulate the motion and behaviour of a complex system is to approximate it with a multi‐body system based on particles, and to evaluate the particle interactions over time. Normally, the calculations require such a large amount of computer power that methods have been developed to decrease computation time by taking advantage of new computer architectures.

These methods have been in use since the early 1980s, but there is still a lack of concepts supporting the application of these methods, to build highly efficient simulation systems with reusable entities.

In this paper we describe a new approach for the development of flexible, efficient methods and techniques to control multi‐body systems. The major goal of our concept is the integration of advanced modern simulation techniques such as particle‐based modelling and simulated annealing, and efficient data structures such as octrees and the Greengard algorithm. We introduce high‐level concepts represented by agents, environments, and controllers based on and supported by the object‐oriented paradigm.

We demonstrate the flexibility of our new simuation system for applications related to environmental research and air quality control.
Building blocks for goal‐directed motion
Authors: van Overveld C. W. A. M.
Published: November 2006

An approach for the integration of intelligent goal directed motion within an interactive real‐time computer animation environment is sketched. The approach is based on a cause‐and‐effect model for intelligent goal direction motion which gives rise to types of motion primitives: one is the application of a so called multi‐track recording paradigm for direction motion manipulation; the second is an algorithm to mimic a control system for goal directed motion of joints in a multi‐link structure. The techniques described here are features of the procedure based animation system which is described in Reference 1.
Visual simulation of botanical trees based on virtual heliotropism and dormancy break
Authors: Chiba Norishige , Ohkawa Shunichi , Muraoka Kazunobu , Miura Mamoru
Published: November 2006

Realistic image synthesis of botanical trees has many applications. Since the generation of ‘tree skeletons’ having natural visual impressions is essential to realistic image synthesis, various methods of modelling skeletons, especially growth models, have been presented. However, no one has succeeded in simulating natural tree features which appear in a growth process, such as generation of a round tree crown, a weeping bough, an irregular branching pattern, or regeneration of a crown.

This paper demonstrates, by showing several simulated examples, that a growth model having the abilities of heliotropism and dormancy break, which produces shapes of trees adapted to changes in the light environment, is effective in the CG simulation of realistic tree skeletons.
Two‐dimensional visual simulation of flames, smoke and the spread of fire
Authors: Chiba Norishige , Muraoka Kazunobu , Takahashi Hiromichi , Miura Mamoru
Published: November 2006

Since CG simulation of natural phenomena on the basis of their forms and motions has many applications, such as various landscape designs and special effects in films, it is very important and interesting to develop efficient techniques for their visual simulation. It is especially interesting to produce realistic images and animations of flames and smoke, on account of their complicated patterns of behaviour.

Effective simulation methods for flames and smoke are expected to satisfy the following requirements:

The motion of flames or smoke produced in an interaction with obstacles can be simulated.

The motion of flames and smoke can be easily controlled according to scenarios.

The spread of fire can be simulated.

Although several useful representation methods have been proposed so far, simulating flames and smoke still remains a challenging problem. In this paper, we first describe our basic two‐dimensional visual simulation method based on particle‐based simulation, but not based on exact physical simulation. Roughly speaking, our method assumes that the images of flames and smoke are basically obtained by visualizing turbulence, that is, the particles of flames and smoke play the role of tracers in the field of turbulence. Next, we present an improved method for simulating the spread of fire and the appearance of smoke produced in an incomplete combustion. Simultaneously, we show several examples of the simulation. Finally, we will touch slightly on further problems for extending the model to one which works in three‐dimensional space.
Direct volume rendering of multiple scalar fields
Authors: Giertsen Christopher
Published: November 2006

Rendering of volume data without forming geometric objects is often termed direct volume rendering. Most of the previously developed methods for this purpose are restricted to display of one scalar variable. This paper presents methods for direct volume rendering of several scalar variables defined at discrete points in three‐dimensional space. Typical requirements for the rendering of such data are proposed and then used as a basis for the derivation of a computational model. The proposed model uses a classification technique to composite specific types of information from different scalar fields. The visual display of the composite information is controlled through a set of rendering parameters.
Super TEX‐SIM: Interactive textile design and simulation
Authors: Kambe Hisashi , Yamasaki Nobuhiko , Lee Myeong Won
Published: November 2006

This paper presents an interactive tool for designing and simulating textile images. It comprises a yarn editor, a textile editor and a texture mapper. These subsystems share a colour editor that can modify the colours of yarn and textile images interactively. We describe how yarn and textile images are generated, and how they are mapped to a target picture read from an image scanner. The user interface in the tool has many useful functions so that users can design textile images without knowledge of computer graphics and programming languages. Several examples of texture mapping are included.
The modelling of large waterfalls using string texture
Authors: Mallinder Hugh
Published: November 2006

Particle systems have been extensively used for modelling fluid flow. But if a large number of particles are required, this can lead to unreasonably large amounts of memory usage. This is because the position and velocity is stored explicitly for each particle. Solid texture, on the other hand, stores parameters implicitly, by means of addressing small look‐up tables. This paper presents a method of implicitly storing particles, and illustrates its use with the modelling of large waterfalls.
Application paper. Applying ray casting to the flow visualization data using linear and B‐spline hyperpatch interpolation
Authors: Semwal Sudhanshu Kumar , Swann Paul Gene
Published: November 2006

Visualizing the flow of air or fluids is especially challenging because of their transparency and possible high velocity. Complex patterns are created when the flow is over or around an object. Our aim is to visualize the flow in three dimensions, eliminating the need for mentally piecing the flow from two‐dimensional slices. We have applied the well‐known ray casting technique to visualize the flow around an aircraft wing. During ray casting, when the ray does not intercept the lattice points, linear and B‐spline hyperpatch interpolations are used to estimate the colour. We describe the shading equation, and compare the linear and the B‐spline hyperpatch interpolation schemes during ray casting. Several images are produced to show the difference in the image quality of these two methods, and their image generation time.
Combining physically‐based simulation of colliding objects with trajectory control
Authors: Lamouret Alexis , Gascuel Marie‐Paule , Gascuel Jean‐Dominique
Published: November 2006

This paper describes a method that facilitates the use of physically‐based models by animators. The main point is to give the animator a familiar interface, while providing a simulation module which detects collisions, thus enhancing realism.

The user gives a set of key‐frames to guide motion, but does not have to address problems such as interpenetration avoidance, deformations due to collisions, or realism of motion. The simulator will correct the trajectories and compute deformations according to each object's physical properties (such as mass, inertia, stiffness) as well as the collisions and contacts automatically detected during motion. To achieve this, objects are provided with actuators capable of generating forces and torques computed via generalized proportional‐derivative controllers. When deflected by external actions, actuated objects try to return to their initial path. Speed variations over time are computed during the simulation, and depend on the complexity of the paths, on the objects models, and on the events such as collisions occurring during motion. In addition simulations are generated at interactive rates, even in the case of complex articulated objects. This facilitates the fine tuning of an animation sequence.
An L‐systems approach to the modelling of fungal growth
Authors: Tunbridge Andrew , Jones Huw
Published: November 2006

A parametric L‐system is developed to model the growth and structure of the fungus Aspergillus nidulans. The model uses biological understanding of the flow of nutrients through the fungus to control the simulation of growth, with L‐systems productions being dependent on the levels of nutrients, stored as parameters, in various parts of the model. This produces a structural model that is consistent with previous observations of the natural fungus. Visual interpretation of the L‐systems string uses a turtle graphics method. When stochastic rules are implemented to model specific features of Aspergillus nidulans, the simulation is convincing both visually and structurally. Other potential applications for the method are suggested.
An integrated approach to motion and sound
Authors: Hahn James K. , Geigel Joe , Lee Jong Won , Gritz Larry , Takala Tapio , Mishra Suneil
Published: November 2006

Until recently, sound has been given little attention in computer graphics and related domains of computer animation and virtual environments, although sounds which are properly synchronized to motion provide a great deal of information about events in the environment. Sounds are often not properly synchronized because the sounds and the phenomena that caused the sounds are not considered in an integrated way. In this paper, we present an integrated approach to motion and sound as it applies to computer animation and virtual environments. The key to this approach is synchronization by mapping the motion parameters to sound parameters so that the sound changes as a result of changes in the motion. This is done by representing sounds using a technique for functional composition analogous to the ‘shade trees’ which we calltimbre trees.These timbre trees are used as a part of a sound description language that is analogous to scene description languages such as RenderMan. Using this methodology, we have produced convincing sound effects for a wide variety of animated scenes including the automatic generation of background music.
Visualization of connectivity in octree based models
Authors: Fedenczuk Leon L. , Wyvill Brian
Published: November 2006

An interesting problem in the oil and gas industry is the visualization of the movement of oil and gas in porous media. An example of such a medium is a rock sample with some distribution of holes (pores) connected by channels (pore throats), the solid parts of the rock are called grains. In our work we have simulated the porous medium using a pointer‐based octree, representing these pores and grains. This data structure allows us to model the connectivity of the pores and thus visualize fluid penetration within the medium. Whereas earlier models represent a serious simplifications or two dimensional homogeneous layers, our model provides us with a statistically accurate distribution in three dimensions and a more accurate representation of the connectivity.

In this paper we present our data structure and the techniques which were used to create models of porous media and their porous networks. Next, we present algorithms for connectivity in octrees and we show how to apply them to modelling and visualization of fluid penetration in porous media.
Subvolume projection: A full exploitation of function coherence for volume rendering
Authors: Zhou Yong , Tang Zesheng
Published: November 2006

Direct volume rendering techniques present a huge potential for displaying a great amount of information in 3D data sets within one image. However, generating such an image is extremely expensive, and rendering for high quality pictures is far from interactive. Traditional volume rendering approaches are based on a cell‐by‐cell model. They consider cells as the smallest manipulation object. The time complexity of the volume rendering is determined by the number of cells, and the image quality, to some extent, is affected by the cell tessellation of volumes. Many scientists and technicians rarely venture to research the exploitation of coherence of function distribution over scalar fields through partition of data volumes. This paper proposes a new volume rendering approach: subvolume projection. It not only exploits the spatial coherence of cells but employs fully the spatial coherence of function distribution to partition a volume into a number of subvolumes, so that the function varies slowly over each subvolume. Each newly generated subvolume can be considered as containing a single material and treated as the smallest unit instead of cells in the processing. Based on the subdivision of the volume, this paper discusses the calculation of intensity contributed by the subvolumes in detail. Theoretical analysis and a variety of experimental results show that the new approach improves image quality and reduces rendering time period. (Usually the new algorithm is three to four times faster than the traditional volume rendering algorithms).
A radiosity solution for random fractal surfaces
Authors: Wu En‐Hua
Published: November 2006

Fractal geometry provides an outstanding mathematical tool for simulating natural phenomena. However, the recursive process of stochastic modelling in generating random fractals puts forward difficult problems in the rendering. At present, only some special ray tracing methods have been provided to render fractals, mainly producing specular illumination. This paper proposes a radiosity solution for rendering random fractals, in which diffuse interreflection can be calculated in the process of stochastic modelling. By this solution, the recursive process of fractal generation is naturally incorporated into the progressive refinement procedure of the radiosity solution. Particularly, it becomes possible for fractal surfaces to participate in the energy shooting process of the radiosity solution.

The key problem in the proposed approach is in calculating the radiosity redistribution for fractal subdivision. An algorithm for solving the problem has been proposed and implemented. Test examples show that the method is quite efficient. The technique may improve the visual realism of the radiosity image and promote the practical value of the radiosity solution.
Regime shifts: catastrophic responses of ecosystems to human impacts
Authors: Genkai‐Kato Motomi
Published: November 2006

Evidence of abrupt changes in ecosystem states, such as sudden eutrophication in lakes, has been increasingly reported in a variety of aquatic and terrestrial systems. Ecosystems may have more than one state with a self‐stabilizing mechanism, so that a shift between states does not occur frequently and is not readily reversible. These big changes are termed regime shifts where often one state is preferred over another. Thus, regime shifts are problematic for ecosystem managers, and the need exists for studies that lead to the identification of thresholds of key variables that trigger regime shifts. Regime shifts are currently difficult to predict and in many cases may be caused by the human pursuit of efficiency in land and water productivity in the last few decades. Here I briefly introduce a theoretical approach to predict the shift between a clear‐water state and a turbid state in lakes, the best‐studied example of regime shifts. This paper also discusses alternative states in other natural systems besides ecosystems to draw more attention to the research currently being performed on regime shifts.