Fundamentals of Computer Graphics

The following sections are included:

• Preface

• Contents

This paper presents a new method for measuring 3D (three dimensional) facial shapes. First of all, the normal vectors at points on the face are computed by using three light sources and by solving Lambertian reflectance map. We can obtain dense information on the approximate facial shape at a time. Light stripes are then projected onto the face to increase the accuracy of the measured value and 3D coordinate values of the points on the stripes are computed by stereo vision. The normal vectors are then integrated inside the circular domains centered at points on the stripes. The local surface shape in each domain is computed using integration. Finally, the local surface shapes are blended to obtain the global facial shape using blending function.

This method enables the accurate 3D measurement of complicated shapes of a human face in a short time.

We present efficient algorithms to model a collection of scattered function data defined on a given smooth domain surface D in three dimensional real space (∝³), by a C¹ cubic or a C² quintic piecewise trivariate polynomial approximation F (a mapping from D into ℝ⁴). The smooth polynomial pieces or finite elements of F are defined on a three dimensional triangulation called the simplicial hull and defined over the domain surface D. Our smooth polynomial approximations allows one to additionally control the local geometry of the modeled function F. We also present two different techniques for visualizing the graph of the function F.

The algorithm for constructing isosurfaces within tetrahedral meshes has been considered as one approach to solve the ambiguity problem in Marching Cubes method and has attracted extensive attention. In this paper, it is pointed out that the ambiguity problem still exists even if isosurfaces are generated through tetrahedral meshes. Then, based on the assumption that the function value distribution along edges of cubes is linear, the criterion for testing the intersection between an isosurface and tetrahedron's edges is given and followed by the calculation method of intersection points. The connection of intersection points in tetrahedra to construct polygons and the triangularization of polygons are discussed in detail. Then the comparison among the Marching Cubes method, the existing Marching Tetrahedra method and the New Marching Tetrahedra method presented in this paper is given. It is shown that the isosurfaces generated by our method is independent of the subdivision modes of the tetrahedra from cubes. At last, two isosurface images generated by our method are shown.

A methodology is presented that enables to express any deformation technique in a unique framework. The driving idea of this paper is that every deformation can be reformulated as combination of three kinds of normalized operators, transformation, modulation and perturbation. Moreover, using some pleasant properties of the methodology, some innovative ways to use, combine and enhance classical techniques are provided.

In this paper, explicit conditions of G^k continuity between Bezier surfaces are given. We concentrate on the structures of G^k transformations between adjacent Bezier surfaces and show that a general G^k transformation can be represented recursively with the composition of k cardinal G^k transformations. We can thus construct a new Bezier surface Q from a given Bezier surface R such that Q and R meet with G^k continuity by recursively applying simple geometric transformations which have intuitive geometric meaning for k times. When these simple G^k transformations are also polynomial preserving, each of them is actually determined by three real constants. The structures of G^k transformations are explored and described. Since the G^k conditions between two Bezier surfaces are finally expressed with the explicit relationship of the related control points, these results can be used directly in closed surface modeling, surface blending and surface connecting.

Computer graphics plays an important role in rapid development and acceptance of fractal images visualizing the Mandelbrot set and Julia sets from a complex function. In particular, computer rendering of fractal images becomes a central tool to obtain nice fractal images and also to provide an aid for understanding the dynamical behavior of a complex function. In this paper, we present how to render 3D objects obtained from fractal images by giving the height of each complex point using the diverging speed of its orbit. To obtain nice fractal images, we consider the Newton form of an equation, which exhibits very interesting Julia set images in a bounded region.

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 radiosity solution. Particularly, it becomes possible for fractal surfaces to participate into energy shooting process of radiosity solution.

The key problem in the proposed approach is in calculating the radiosity redistribution for fractal subdivision. 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 radiosity image and promote the practical value of radiosity solution.

Many methods have been proposed that model the characteristics of light for producing realistic computer generated images in recent years. However, these aproaches are not adapted to take into account the typical properties of “any” light source and material. In order to generate simulations for industrial applications, as in the lighting industry, these emittance and reflectance properties have to be measured at a laboratory, and then used as input data in a global illumination model. This paper proposes a method that allows accurate simulations of these properties, and presents two typical applications.

While the radiosity method gradually established itself as a main rendering technique, there are still some fundamental problems regarding the radiosity method that remain unsolved. In this paper, we present a new radisosity approach for realistic image synthesis. Unlike the conventional radiosity method, the evaluation of light energy transfer is divided into two parts. In the first part, we establish the spatial light energy distribution of the source patch. In the second part, we subdivide the receiving surfaces accordingly and perform illumination calculation. The source patch and its receiving patches are related with each other through a global cube which acts as a light energy distributor. As no form—factors are involved, the conventional constraints on both the shooting patch and the receiving patch have been removed. Illumination coherence is exploited by performing dynamic subdivision of the receiving surface with respect to each current light source and by adaptive formation of the active light source. Accurate rendering of curved surfaces, anisotropic surfaces as well as the generation of high frequency details such as shadow edges, caustic borders and bump textures are supported efficiently. Experimental results show great potentials of the new approach.

In this paper, we explore the properties of radiosity equation systems and analyze the mathematical background of existing O(n) solvers for such systems. Based on our analysis, we present a new algorithm using an inverse matrix approximation technique along with an improvement in the existing algorithm due to Feda [2]. We prove the convergence of our method, as well as the modified version of Feda's method, under realistic conditions for radiosity computations. Experimental results indicate that our new methods converge faster than existing methods in all cases tested.

This paper presents the Provim system, a parallel ray tracing system accelerated by the bounding volume hierarchy developed in distributed environments contained a network of heterogeneous workstations. The system has been designed to be independent on the network topology, and the processor farm computational model is utilized to harness the computing. To facilitate the system development Parallel Virtual Machine (PVM) is adopted where the network communications are proceeded by calling routines in the PVM library. The Provim system supports both the centralized approach in which the master workstation is responsible for task generation and scheduling, and the decentralized approach where all of the slave workstations are able to generate and schedule tasks. The system load balancing is achieved by using the demand-driven task request strategy associated with appropriate task granularities. The Provim system has demonstrated that ray traced images that would have taken between several hours to generate on a single workstation can now be generated in between several minutes using 28 workstations. It is concluded that computing in distributed workstation environments is potential to bring significant benefits to computationally intensive applications offering advantages of low cost and ready availability.

The realistic animation of animal behavior by autonomous animate agents requires that the agents able to perceive their virtual worlds. We have created a virtual marine world inhabited by artificial fishes which can swim hydrodynamically in simulated water through the motor control of internal muscles. Artificial fishes exploit a rudimentary model of fish perception. Complex individual and group behaviors, including target tracking, obstacle avoidance, feeding, preying, schooling, and mating result from the interplay between the internal cognitive state of the artificial fish and its perception of the external world.

A model is described to simulate expressive wrinkles in 3D facial animation and skin aging. A plastic-visco-elastic skin surface is defined that can slide over an underlying layer. This layer constrains the skin surface by the spring force that simulates the connective fat tissue between skin and muscles. Muscle masks are constructed to characterize the muscular contractions that offer the tension to the skin and provide the facial movement. By choosing proper parameters for this physically based model, wrinkles in facial animation and skin aging are simulated through the elastic process assembled with visco and plastic units.

In this paper, we present an efficient approach for modeling the natural features of human hair. We consider not only its appearance, but also the control of its motion and a technique for rendering it realistically. A strand of hair is modeled as a sequence of linked rigid sticks. Basically we also use a simplified cantilever beam model for the bending of hair. In animation, the angular momenta for linked rigid sticks is used to describe its dynamic behavior. Besides we propose a new approach for the detection and avoidance of collisions between the hair and human head. By applying appropriate reflection model, the dynamic and natural beauty of human hair is shown.

This paper presents algorithms to manipulate previously created and stored Motion Units (MU). The user can asynchronously select and concurrently run many MUs. These algorithms provide the basis for a new generation of software titles that allow the user to directly control human animation on a game machine or PC. There is a need to shift the focus of human animation research from animatorbased or actor-based approaches, to a more user-based approach. With the new generation of PC and game machines, sophisticated graphics algorithms can be executed in real time. Even 3D human animation becomes possible. However, the traditional animator-based algorithms are inappropriate to use directly, since they are too computationally expensive. Our approach is to store Motion Units, and let the user directly manipulate and mix these MUs while playing a title on a game machine or PC. This is a user-based approach to generating human animation algorithms. We would like to present our motion algorithms, and discuss our research implementation that uses these.

In this paper, we propose the use of inverse dynamics in a closed-form with direct dynamics for interactive motion control of a human skeleton. An efficient recursive algorithm based on Newton-Euler formulae is used to calculate the force and torque produced by joint actuator in order to fulfill a desired motion. The resulting force and torque are then used in direct dynamics to make the final motion with external force and torque. Armstrong-Green algorithm is used for direct dynamic simulation. To decrease the errors in numerical integration, we use foui in-order Runge-Kutta method instead of Euler method. Inverse dynamic functions calculate the required force and torque at every small time interval in the process of direct dynamic simulation. In this way, it will correct errors at each time interval. The direct and inverse dynamic functions are integrated in the software TRACK with direct and inverse kinematics functions that provide a more powerful way for human animation.

This paper presents the “Impromptu Conductor” virtual reality system which combines computer graphics and music while emphasizing on computer music. We introduce the supervised learning method mentioned in the field of pattern recognition into the reproduction and the organization of music.

We have proposed and implemented a practical way of capturing human's motion to create music as well as generating the corresponding images on a screen by using a 6- D tracker to simulate a conductor's hand in real time. However, the mapping between music and hand motion in our system is not a simple one to one function, and is constrained and properly modified by music styles collected from supervised learning. That is, the music style produced by an interactive user strongly depends on the movement of one's hand gesture. The system we implemented shows that the system designer can give different styles of feedback to different patterns of a user's behavior easily.

The developments of recent years in computer hardware have resulted in rapid advances in the capabilities of Computer-aided Design: but continued hardware development alone is not enough to ensure similar progress in the future. In order to grow further, CAD must move further into the design process itself, which raises the need for a language whereby designers and computers can ‘discuss’ a design when it is still at the conceptual stage. The Engineering Design Centre at Cambridge University has now made substantive progress in this area: this paper summarises the progress made to date, and describes how some of the issues which have been raised are currently being tackled.

The two fundamental questions that arise in CAD/CAM systems concerning every type of manufacturing process that is intended to realize a design are: (1) Given a designed object, can it be constructed using a particular process? (2) Given that a designed object can be built using a particular process, what is the best way to construct the object? A brief survey is presented of computational geometric tools for designing algorithms to answer these types of questions, as well as key results already obtained, for several manufacturing processes such as gravity casting, injection molding, and stereolithography.

This paper provides a methodology permitting the conversion of range images into surface models. The calculated model should be acceptable by the major CAD systems. In this approach the range image is segmented into homogeneous patches, and then the surface model of each patch is calculated. The degree of each patch is automatically determined in order to respect the precision requirements. Finally the individual patches are merged, respecting G¹ continuity conditions. This model is converted into IGES format and sent to a CAD system.

Three configurations of block edge detections based on the third level of the conjugate classification for binary images of the hexagonal grid, are investigated in this paper. Constructing an operation of three configurations, it is necessary to collect a state set contained 48, 66 and 90 states as the structuring patterns respectively. To represent the selected state set in equivalent detecting functions, cellular logic and conjugate computations are illustrated and compared. Because a conjugate expression uses a class representation for structuring patterns, its real implementation is very efficient. For three configurations of 0 (or 1) block edge detections, a speed-up ratio 6-15 compared with the same activity performed by a standard implementation in a cellular logic expression, can be measured. Sample processed pictures and their timing measurements are illustrated and analyzed.

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 proposed a new volume rendering approach: Isosurface 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.)

This paper describes a new method of reconstructing the solid model of human anatomy from a series of X-ray Computed Tomography (CT) images. Our method starts with extracting the planar contours represented by a sequence of Bézier curves from each CT image. Then a solid model passing through the given contours is generated. To create the topological structure of the solid model, Euler operations are applied. The solid model is bounded by quadrilateral surface patches. In addition, we describe the application of a solid modeler for a computer aided surgery planning system.

In the algorithms of conventional direct volume rendering, the color at each pixel on the image is composited by recursively using a compositing operator for combining the effects of samples along the project path. In this paper, a new compositing color method is proposed & implemented. By the method, the effects of samples are distributed over a 2D plane, referred to as the virtual plane, and the final images are produced by a direct compression from the virtual plane. The mapping from volume samples into image space is therefore through an encoded 2D sampled space. The method takes away multiplication operations which are necessary in all the present compositing color methods. More importantly, images in various size can be produced without reoperation of projection, when the new method is integrated with the projection approach for direct volume rendering.