Abstract We present a pseudo‐dynamics model of a cantilever beam to visually simulate motions of leaves and branches in a wind field by considering the influence of natural frequency (f0) and damping ratio (e). Our pseudo‐dynamics model consists of a static equilibrium model, which can handle the bending of a curved beam loaded by an arbitrary force in three‐dimensions, and a dynamic motion model that describes the dynamic response of the beam subjected to turbulence. Using the static equilibrium model, we can apply it to controlling the free bending of petioles and branches. Furthermore, we extend it to a surface deformation model that can deform some flexible laminae. Based on a mass spring system, we analyze the property of dynamic response of a cantilever beam in turbulence with various combinations off0ande, and we give some guidelines to determine the combination types of branches and leaves according to their shapes and stiffness. The main advantage of our techniques is that we are able to deform curved branches and some flexible leaves dynamically by taking account of their structures. Finally, we demonstrate that our proposed method is effective by showing various motions of leaves and branches with different model parameters. Copyright © 2009 John Wiley & Sons, Ltd.

A technology for automatically creating and adding the sound to interactive CG animations of spark discharges in real time has been developed. In the procedure proposed in this paper, the user inputs the electric charge distribution, boundary conditions and other parameters affecting the initiation of electric discharges in virtual space. The animation of the discharge is then created by generating the shape of the discharge pattern and rendering it, and the sound synchronized with the animation is automatically generated in real time. The noises from spark discharges are shock waves, which exhibit complicated behavior; but, in this study, an empirical shape for a shock wave is employed to efficiently generate the acoustic waveform. Effective procedures for expressing lightning discharges and continuous discharges are also proposed.

Surface reconstruction from particle system is a difficult problem. In this paper, we introduce a method to reconstruct the surface from particle-based simulation of ocean waves with complex shape and splashes. Each 2D slice of particle volume is projected onto an image, and then the image is segmented for recognition of water body and splash fragments. Outlines of the water body are extracted directionally. The mesh of surface is reconstructed by tiling the triangular strip from the outlines of the slices. The experiments show that the efficiency of this method is very competitive.

This paper presents a method for automatically generating sound effects for an animation of branches and leaves moving in the wind. Each tree is divided into branches and leaves, and an independent sound effect generation process is employed for each element. The individual results are then compounded into one sound effect. For the branches, we employ an approach based on the frequencies of experimentally obtained Karman vortex streets. For the leaves, we use the leaf blade state as the input and assume a virtual musical instrument that uses wave tables as the sound source. All computations can be performed independently for each frame step. Therefore, each frame step can be executed on completion of the animation step. The results of the implementation of the approach are presented and it is shown that the process offers the possibility of real-time operation through the use of parallel computing techniques. Copyright © 2005 John Wiley & Sons, Ltd.

Research on methods for representing natural objects and phenomena by computer graphics (CG) has been steadily broadening the scope of represented objects in recent years. Among such research, visual simulation of rocky scenery is an important issue that has a wide range of applications related to visual contents, such as in landscape simulation. In the early days of research on terrain scenery representation, a great deal of techniques for representing terrain shapes and rocky textures mainly using noise generation methods such as the midpoint displacement method and FFT were reported. In the natural rocky scenery, cracks called "joints" are an important visual feature. After cracking base rocks by joints, the change of the rock shapes according to some factors, such as eliminating rock pieces by weathering or moving by gravity, determines the consequent rocky scenery. In order to create such rocky scenery, we propose a rocky scenery modelling method based on joint formation and rock elimination/movement simulation.

Trees are one of the most important elements of natural landscapes. Therefore, in computer graphics, there is a great demand for methods to realize the natural representation of trees in virtual landscapes in various fields such as entertainment industry or environmental assessment in construction. Many studies have been made on techniques in which the shapes of trees are modeled but only a few studies have been reported on methods to incorporate the shapes with motions in a wind field. Most of these studies use physical simulation techniques based on the equations of motion to generate the branch motions and cannot realize the motions of individual leaves. We propose a method to create the natural motions of individual leaves and branches swaying in a wind field. This method generates the leaf and branch motions based on "1/f/sup /spl beta// noise", which is observed in various natural phenomena. For the branch motion, a simple simulation method based on the spring model is applied to enhance the realism of the motion. This method enables the real-time creation of the leaf and branch motions. Diverse motions according to tree species and shapes and wind conditions can be easily realized by controlling the parameters.

In the present paper, we propose a particle-based method for the visual simulation of explosive flames. This method consists of a numerical simulation method based on a fluid model described by discrete Lagrangian using particles and a rendering method for generating a CG animation from the movement data of the particles. This fluid model uses flame particles and air particles. The model calculates the buoyancy caused by the difference in temperature as the external force in the Navier-Stokes equations and approximates the viscous force and pressure via a discrete particle model. In addition, the heat conduction between particles is taken into account. The proposed method realizes the representation of distinctive phenomena such as an ascending airflow with a quantity of explosive flame and a swirling airflow behind the ascending airflow. CG images are rendered using a Z-buffer based volume rendering method.

Abstract We propose a fast, high quality tone mapping technique to display high contrast images on devices with limited dynamicrange of luminance values. The method is based on logarithmic compression of luminance values, imitatingthe human response to light. A bias power function is introduced to adaptively vary logarithmic bases, resultingin good preservation of details and contrast. To improve contrast in dark areas, changes to the gamma correctionprocedure are proposed. Our adaptive logarithmic mapping technique is capable of producing perceptually tunedimages with high dynamic content and works at interactive speed. We demonstrate a successful application of ourtone mapping technique with a high dynamic range video player enabling to adjust optimal viewing conditions forany kind of display while taking into account user preference concerning brightness, contrast compression, anddetail reproduction. Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Image Processing and Computer Vision]: Image Representation

In the walk-through via the Internet, we move a mouse to imitate a walk by our foot (Chen, 1995). Here, we consider the case which maps a real motion to an immersive virtual reality environment. For example, we wander in a computer room as if we do in a museum for watching some arts. The user's head motion at a relative large scale environment is needed to be known for realizing this immersive virtual reality. This research proposes a method of estimating the head motion based upon vision approaches for mapping a head motion to an immersive virtual reality environment. We put fiducial markers around the room to be changed virtually and use an omnidirectional image sensor to observe these markers. By mounting the visual sensor on a helmet, the head motion of a user who wears the helmet can be estimated by processing images captured from the omnidirectional image sensor. Since it has a 360 degree view, it can cope with a large head rotation motion compared with a normal camera. Since a head motion at every time is directly estimated from the observed markers, there is no accumulated errors in our method compared with an inertial sensor.

Simulation of weather scenery in computer graphics (CG) is an important issue that has a wide range of applications related to image content, such as in movies and in various landscape simulations. In general, research to date into CG lightning has focused on generating a lightning pattern by applying probability and statistics techniques, which do not consider the generating mechanism of lightning. In natural lightning, an electrical-discharge path (stepped leader) is generated under the influence of an electric field formed by electrification of a cloud. We present a method that generates a lightning pattern by simulating a stepped leader in an electric field defined by placement of electric charges. We also give rendering methods for lightning in a cloud that are based on the volume rendering method using point light sources.

The paper describes a method for modeling the natural peeling phenomenon over any 3D surface. Using crack input data, precomputed with a semi physical solution, this method allows simulation of peeling on any type of triangulated 3D object. The model's main advantage is that it proposes a method that is intuitive enough to make it easy to understand and convenient to apply, user controllable, and easily extensible, especially to simultaneous natural phenomena. We first introduce the general development of peeling over various materials. Then, we present how to define groups of peeling, how to determine a realistic and natural peeling order, and how to simulate the rendering of two types of special peelings. Finally, a set of graphical results concludes the paper, presenting a series of direct peeling and curling patterns using classical paintings or plastic-paintings simulated materials.

Describes a method for modeling the propagation of cracks on any 3D surface. Taking a previous cellular automata model of the authors (1999) as the basis, this method allows just about any type of cracks on any type of triangulated 3D object. Our model's main advantage is that it proposes a semi-physical solution, making it at the same time user-controllable and easily extendable. After summarizing works in the literature, we make a brief and simple description of what cracks are physically, and how they are generated. Based on this idea, we detail our model of crack propagation. We first introduce the general development of cracks. We then propose an original model of spectrum stress. This is followed by a description of the mutual interaction between cracks and stresses. Finally, a set of graphical examples, together with their respective parameters, concludes this paper.

This paper describes the generation and rendering of three-dimensional (3D) surface cellular automata (CA). Our model's main advantage is that it gives direct texturing simulation based on the actual shape of any triangulated input object. We first introduce general CA concepts and summarize works in the literature. We then describe our 3D surface CA method, emphasizing how it avoids potential problems in data structure and rendering steps. We then detail, two examples of specific 3D surface CA with their respective cell structures and corresponding computer graphics images. Copyright © 1999 John Wiley & Sons, Ltd.

Suibokuga is a style of monochrome painting characterized by the use of Chinese black ink (sumi), a complex interaction between brush, ink and paper, and such visual features as Noutan (shade), Kasure (scratchiness), and Nijimi (blur). In this paper we present a simple behavioural model of water and ink particles based on a 2D cellular automaton computational model, and its application to a Suibokuga-like rendering of 3D trees. Copyright © 1999 John Wiley & Sons, Ltd.

Visual simulation of natural scenery using computer graphics is an interesting research field with wide applications such as flight simulation and special effects in movies. There have been many studies of fractal techniques that use 1/f noise generated by FFT or the midpoint displacement method as modelling methods for imaginary mountain scenery. These methods are suitable for creating impressive mountain scenes, but they cannot create clear ridge and valley lines, which are notable features of mountains produced by erosion processes. Although a few reports have presented modelling methods that take erosion processes into account, the results have not been satisfactory. In this paper we present a simple ‘quasi-physically based’ method for simulating the topography of eroded mountains based on velocity fields of water flow. © 1998 John Wiley & Sons, Ltd.

Visual simulation of forest scenery is a challenging problem which includes the following tough sub-problems: generation of vegetation, representation of trees, simulation of colour change of leaves, and rendering of numerous trees. Among those sub-problems, this paper treats mainly the last one. A conventional polygon-based rendering algorithm often produces troublesome aliasing effects when it is applied to the objects having complex fine surfaces, such as forest scenery. In this paper, we show that an extended volume rendering technique applied to 3D textures, i.e. volume data in this paper, of trees is effective in the concerned problem. Kajiya left, as further work, the problem of rendering forest scenery by applying his 3D texture called texel. Our rendering method consists of the following three steps: we first generate 3D textures of trees from their polygon-based geometric models, we next arrange the 3D textures, allowing their possible mutual intersections, on the surface of a given polygon-based terrain model according to a simulated vegetation, and we finally produce an image of forest scenery by applying the ray-tracing algorithm including our slightly extended volume rendering technique. © 1997 John Wiley & Sons, Ltd.

The representation methods of botanical trees have been presented so far by several researchers in recent years. A great deal of effort has been dedicated mainly to designing a procedural modelling method, especially a growth model of a tree/plant skeleton. However, few previous works have treated the problems of appropriate leaf arrangement and autumn colour evolution of a leaf which are essential to giving natural and seasonal impressions in a close-range view of a tree. In this paper, we will present the simulation methods for these attractive problems based mainly on the estimation of the amount of sunlight and the brightest direction of each part of every leaf.

Abstract Several CG researchers have simulated impressive ocean waves so far. Recently, other researchers have succeeded in simulating waterfalls by employing a mass of particles. However, visual simulation of water currents having complex surfaces, such as mountain streams and turbulent water, still remains a challenging problem thanks to their complicated patterns of behaviour. Effective simulation methods for water currents are expected to have abilities to represent the following remarkable behavioural visual features of water: the appearance of a pool, an obstacle avoidance flow, a fluent flow, a flow into an open space, the collision and the confluence of flows and the occurrence of splashes. In this paper, we present a new type of particle‐based simulation method for complex water currents which is not based on strict fluid dynamics but rather classified into a ‘quasi‐physically‐based’ simulation method constructed on the basis of algorithmic approaches. We first present a simple behavioural model of a ‘water‐particle’. Next, we propose a method for generating CG images of water currents from a set of water‐particles. Finally, we demonstrate the ability of our method by showing several examples of the simulation.

Abstract 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.

Abstract 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.

In this paper we introduce a new simple strategy into edge-searching of a graph, which is useful to the various subgraph listing problems. Applying the strategy, we obtain the following four algorithms. The first one lists all the triangles in a graph G in $O(a(G)m)$ time, where m is the number of edges of G and $a(G)$ the arboricity of G. The second finds all the quadrangles in $O(a(G)m)$ time. Since $a(G)$ is at most three for a planar graph G, both run in linear time for a planar graph. The third lists all the complete subgraphs $K_l $ of order l in $O(la(G)^{l - 2} m)$ time. The fourth lists all the cliques in $O(a(G)m)$ time per clique. All the algorithms require linear space. We also establish an upper bound on $a(G)$ for a graph $G:a(G) \leqq \lceil (2m + n)^{1/2} \rceil $, where n is the number of vertices in G.

Abstract A subset of the vertices of a graph is independent if no two vertices in the set are adjacent. M. O. Albertson proposed an algorithm for finding an independent set that contains more than two‐ninth of the vertices of a planar graph. Refining his algorithm, we give an O (n 2 ) algorithm for the same purpose.

In this paper we consider the maximum independent set problem in which one would like to find a maximum set of independent (i.e., pairwise nonadjacent) vertices in a given graph. The problem is NP-complete, and still remains so even if we restrict ourselves to the class of planar graphs. It has been conjectured that there exist no polynomial-time exact algorithms for any NP-complete problems. We present a polynomial-time approximation algorithm for the maximum independent set problem on planar graphs. For a given planar graph having any number n of vertices, our algorithm finds, in $O(n\log n)$ time, an independent set that is necessarily larger in size than half a maximum independent set. Thus the absolute worst case ratio of our algorithm is greater than $\tfrac{1}{2}$.