The increasing level of requirements in terms of performance, accuracy, repeatability and resolution in the semiconductors industry leads to several technological problems; among them the positioning accuracy and resolution are peculiarly important. In this paper, we address the crucial issue of high resolution and fast positioning mechanisms. We propose a novel type of high resolution and fast positioning mechanism, based on a macro/micro architecture composed of two stages. We focus here on the micro-stage. It is a combination of: a 3-RRR planar parallel structure (3-RRR stands for 3 kinematic chains in parallel, each chain composed of 3 revolute joints R in a serial arrangement) with deported PRR actuation (a rod connected with two revolute joints R to a linear actuator P and to the RRR chain). This architecture provides stiffness, symmetry and interesting thermal properties; Flexible R links (which avoid the drawbacks of conventional links in terms of backlash, friction, wear, stick-slip,...); and near serial-singular configuration which results in an improvement of the resolution. A modeling of inverse kinematics for position and velocity is presented. Then, an optimization is run to find the best set of geometrical parameters for the micro-stage. An articulated kinematic scheme is finally presented.

The giraffe and its patches, the leopard and its spots, the tiger and its stripes are spectacular examples of the integration of a pattern and a body shape. We present an approach that integrates a biologically-plausible pattern generation model, which can effectively deliver a variety of patterns characteristic of mammalian coats, and a body growth and animation system that uses experimental growth data to produce individual bodies and their associated patterns automatically. We use the example of the giraffe to illustrate how our approach takes us from a canonical embryo to a full adult giraffe in a continuous way, with results that are not only realistic looking, but also objectively validated. The flexibility of the approach is demonstrated by examples of big cat patterns, including an interpolation between patterns. The approach also allows a considerable amount of user control to fine-tune the results and to animate the resulting body with the pattern.

Recently, there has been considerable interest in the representation of radiance in terms of wavelet basis functions. We will present a coordinate system called Nusselt coordinates which, when combined with wavelets, considerably simplifies computation of radiative transport and surface interaction. It also provides straightforward computation of the physical quantities involved. We show how to construct a discrete representation of the radiative transport operator Τ involving inner products of smoothing functions, discuss the possible numerical integration techniques, and present an application. We also show how surface interaction can be represented as a kind of matrix product of the wavelet projections of an incident radiance and a bidirectional reflectance distribution function (BRDF).

Monte‐Carlo path tracing algorithms for computer graphics require that given an incident light ray at a surface an outgoing direction can be computed with a distribution given by the magnitude of the bidirectional reflectance distribution function (BRDF). For analytic reflectance functions this can be done using various techniques including inverting the function, or tabulating some representation of the inverse. However, measured BRDF data sets are too large for this to be practical. We present a method to generate reflection rays distributed according to the magnitude of the BRDF. The method relies on a wavelet‐based representation of the BRDF. This representation is efficient and compact, allowing large, anisotropic measured BRDF data sets to be represented with a few thousand coefficients. In particular, we exploit the wavelet representation to quickly compute integrals over ranges of the BRDF.

While there exist many computer models of animal bodies, as polygonal meshes and parametric surfaces, these are difficult to modify to take growth into account, or to animate. Growth data available from the literature usually is expressed as very sparse measurements over the body at various ages of the animal. We present here basic techniques to transfer growth data to computer models (especially polygonal meshes), which allows animation of the growth as well as animation of the body in the traditional sense. The main technique consists of defining local coordinate systems around the growing parts of the body, each one being transformed according to the relevant growth data while maintaining their relationship with the adjoining parts and the continuity of the surface. The local coordinates also permit ordinary animation mainly as relative rotation such as in articulated objects. We present examples with polygonal models of horses and cows, growth data from same, and motion from Muybridge’s classic photographic data.

The Yuan Ming Yuan, the Garden of Perfect Brightness, was the culmination of the art of Chinese Imperial gardens. Covering 350 hectares (875 acres) northwest of Beijing, it included 140 distinct sites, 2000 structures, thousands of pieces of furniture and precious objects, countless plants. It was almost totally destroyed in 1860 at the end of the second Opium War by English and French troops in one of the worst acts of cultural vandalism in recorded history. Rebuilding it has proven impossible, but now computer technology, based on 130 years of scholarly documentation makes it possible to build an accurate and detailed model, and will allow us to experience at least virtually the beauty and grandeur that was the Yuan Ming Yuan. This paper describes a project to build such a model, and details the main challenges and difficulties encountered. While commercially available graphics workstations and modelling software can take us most of the way in this task, they fall short with the modelling of natural phenomena such as plants, rocks and bodies of water. In addition the sheer size of the resulting database pushes rendering engines past their limits.

Analytical models of light reflection are in common use in computer graphics. However, models based on measured reflectance data promise increased realism by making it possible to simulate many more types of surfaces to a greater level of accuracy than with analytical models. They also require less expert knowledge about the illumination models and their parameters. There are a number of hurdles to using measured reflectance functions, however. The data sets are very large. A reflectance distribution function sampled at five degrees angular resolution, arguably sparse enough to miss highlights and other high frequency effects, can easily require over a million samples, which in turn amount to over four megabytes of data. These data then also require some form of interpolation and filtering to be used effectively. We examine issues of representation of measured reflectance distribution functions. In particular, we examine a wavelet basis representation of reflectance functions, and the algorithms required for efficient point-wise reconstruction of the BRDF. We show that the nonstandard wavelet decomposition leads to considerably more efficient algorithms than the standard wavelet decomposition. We also show that thresholding allows considerable improvement in running times, without unduly sacrificing image quality.

Abstract While the notion of shape of an object is very intuitive, its precise definition is very elusive, and defining a useful metric for the shape distance between objects is a difficult endeavor. At the same time many successful techniques have been developed which interpolate between two objects, so in essence interpolate between shapes. W e present here work which uses a representation of objects as union of circles to define a distance between two objects and to base a method to interpolate between the two. This method can be used in a totally automatic fashion (that is, without any user intervention), or users can guide a pre‐registration phase as well as a segmentation phase, after which the matched segments are interpolated pair‐wise. The union of circles representation of the two objects is obtained from the Delaunay triangulation of their boundary points. The circles can be simplified to obtain smaller data sets. The circles are then optimally matched according to a distance metric between circles which is a function of their position, size, and feature, that is, a local configuration of circles. The interpolation between the two objects is then obtained by interpolating between the matched pairs of circles (the interpolations can be affine or non ‐affine). Examples with simple and more complex objects show how the technique can give results which correspond closely to the human notion of shape interpolation. The interpolations shown include some between a calf and a cow and between a cow and a giraffe. The examples given are in two dimensions, but all the steps except the segmentation have been implemented as well for three dimensional objects. W e also show the results of computation of distances between the objects used in our examples.

No abstract available.

Our work addresses the problem of the control of a mobile robot. We present FIRST, a Friendly Interactive Robot for Service Tasks, designed to carry heavy loads in hospitals. A learning method is used to teach it the set of all the trajectories it has to follow. During the learning phase, a human operator teleoperates the robot while its sensors are activated. So the trajectory is built according to these data. The teleoperation is easy and accurate thanks to several locomotion modes of the robot, specially a crab mode. A "Learning Computer" helps the operator in each phase of the learning process. As the missions feasibility must be ensured each trajectory is checked before used. Eventually, while performing the mission, the robot compares the measurements provided by the localization system and the learned points in order to ensure an accurate trajectory tracking.

Abstract Parametric curves and surfaces are powerful and popular modelling tools in Computer Graphics and Computer Aided Design. Ray‐tracing is a versatile and popular rendering technique. There is therefore a strong incentive in developing fast, accurate and reliable algorithms to intersect rays and parametric curves and surfaces. We propose and demonstrate the use of Chebyshev basis functions to speed up the computation of the intersections between rays and parametric curves or surfaces. The properties of Chebyshev polynomials result in the computation of better and tighter enclosing boxes. For surfaces they provide a better termination criterion to decide on the limits of subdivision, and allow the use of bilinear surfaces for the computation of the intersection when needed. The efficiency of the techniques used depends on the relative magnitude of the coefficients of the Chebyshev basis functions. We show from a statistical analysis of the characteristics of several thousands surfaces of different origin that these techniques will result most of the time in significant improvement in speed and accuracy over other other boxing and subdivision techniques.

Abstract Stochastic approaches are very effective for modelling natural phenomena. This paper presents a motion model based on a stochastic process as well as physics, and proposes motion synthesis techniques for stochastic motion—motion under the influence of wind. The motion synthesis process is modelled by a cascade system of three components: wind model, dynamic model, and deformation model. Wind models produce spatio‐temporal wind velocity fields using the power spectrum and auto‐correlation of wind, just like fractal geometry. Dynamic models describe the dynamic response of the systems, using equation systems or response functions. Deformation models produce deformed shapes of objects according to the geometric models of the objects and the results of the dynamic systems. The biggest advantage of the model is its generality and consistency. The model is applicable to most of the existing trees and grass models, including structural models, particle systems, impressionist models, and 3D texture. It is demonstrated that the coupling of stochastic approaches and physically‐based approaches can synthesize realistic motion of trees, grass and snow with modest computational cost.

Two parallel robots are presented. The first is a three-degree-of-freedom lightweight robot called DELTA. The equations corresponding to different models of this robot (forward and inverse kinematics as well as inverse dynamics) are given. The important feature of the method used in deriving these models is the use of a 'good' set of parameters to simplify the equations. These models have been employed to control a real DELTA with a low-cost controller. An attempt was also made to extend the principle of the DELTA mechanical structure to a six-degree-of-freedom parallel robot. A design called the HEXA has been developed. The authors present this robot and show that it should have the same dynamic capabilities as the DELTA because, like the later, it can be built with light material and can be easily modeled.>

A prevailing trend in computer graphics is the demand for increasingly realistic global illumination models and algorithms. Despite the fact that the computational power of uniprocessors is increasing, it is clear that much greater computational power is required to achieve satisfactory throughput. The obvious next step is to employ parallel processing. The advent of affordable, tightly-coupled multiprocessors makes such an approach widely available for the first time. We propose a tightly-coupled parallel decomposition of FIAT, a global illumination algorithm, based on space subdivision and power balancing, that we have recently developed. This algorithm is somewhat ambitious, and severely strains existing uniprocessor environments. We discuss techniques for reducing memory contention and maximising parallelism. We also present empirical data on the actual performance of our parallel solution. Since the model of parallel computation that we have employed is likely to persist for quite some time, our techniques are applicable to other algorithms based on space subdivision.

A reflection and refraction model for anisotropic surfaces is introduced. The anisotropy is simulated by small cylinders (added or subtracted) distributed on the anisotropic surface. Different levels of anisotropy are achieved by varying the distance between each cylinder and/or rising the cylinders more or less from the surface. Multidirectional anisotropy is modelled by orienting groups of cylinders in different direction. The intensity of the reflected light is computed by determining the visible and illuminated portion of the cylinders, taking self-blocking into account. We present two techniques to compute this in practice. In one the intensity is computed by sampling the surface of the cylinders. The other is an analytic solution. In the case of the diffuse component, the solution is exact. In the case of the specular component, an approximation is developed using a Chebyshev polynomial approximation of the specular term, and integrating the polynomial.This model can be implemented easily within most rendering system, given a suitable mechanism to define and alter surface tangents. The effectiveness of the model and the visual importance of anisotropy are illustrated with some pictures.

Raster graphics displays are almost always refreshed out of a frame buffer in which a digital representation of the currently visible image is kept. The availability of the frame buffer as a two-dimensional memory array representing the displayable area in a screen coordinate system has motivated the development of algorithms that take advantage of this memory for more than just picture storage. The classic example of such an algorithm is the depth buffer algorithm for determining visible surfaces of a three-dimensional scene. This paper constitutes a first attempt at a disciplined analysis of the power of a frame buffer seen as a computational engine for use in graphics algorithms. We show the inherent power of frame buffers to perform a number of graphics algorithms in terms of the number of data fields (registers) required per pixel, the types of operations allowed on these registers, and the input data. In addition to upper bounds given by these algorithms, we prove lower bounds for most of them and show most of these algorithms to be optimal. One result of this study is the introduction of new frame buffer algorithms for computing realistic shadows and for determining the convex intersection of half spaces, an operation important in computational geometry and in rendering objects defined using planes rather than polygons. Another result is that it shows clearly the relationships between different and important areas of research in computer graphics, such as visible surface determination, compositing, and hardware for smart frame buffers.

A new class of geometric mappings is introduced to computer graphics, and the utility of this class is illustrated by applying it to texture mapping. When mapping a texture onto a surface such as a polygon, the entire texture can rarely be mapped without some clipping or non-linear transformation. Is it possible to map a texture bijectively to an arbitrary polygon such that the entire texture is mapped? This paper presents a solution to this problem. A new class of mapping techniques based on conformal mapping is proposed. The technique allows one to construct a continuous, bijective map from a polygonal texture space (e.g., a square) to an arbitrary convex polygon. The resulting map is texture-independent. The theory and .an implementation of conformal texture mapping is discussed, and several simple filtering techniques to support it are outlined. Conformal mapping extends the range of geometric mapping techniques, and is pertinent to many areas of computer graphics. Other examples of the potential utility of conformal mappings are also discussed.

This paper deals with the problem of true cooperation of robots working on the same task. We propose a method to carry out various tasks where both robots move together a same rigid object. Firstly we develop the theorical aspect and then we present the exchange problem between two grippers and an assembly task using two arms.

New modelling primitives and new rendering techniques are appearing at a rapid rate. To be able to implement and evaluate them easily, we need a very flexible display environment. We describe an environment which allows experimenting both with the basic modelling and rendering operations and with the process structure of the display system.The desired operations are implemented in nodes, coded in a traditional programming language, which can then be structured into arbitrary directed acyclic graphs. These nodes are all plug compatible, and pass streams of appels, which are generalized pixels, that is data structures containing information necessary for pixel evaluation. In addition, synchronization parameters are used to allow the expansion or the reduction of the stream of appels.This approach allows the assembly of new display systems from existing modules without coding, making it easy to experiment with different architectures and display processes. Algorithm designers are also able to test an algorithm at any point of the display process with a minimum of new coding.We describe an implementation of the scheme with a library of nodes written in C and the assembly of the graphs made through the use of the directory manipulation tools provided under UNIX™. We give examples of the uses of the implementation to build basic nodes, variations in compositing and texture mapping and special-purpose display systems.

While the race towards higher-resolution bitmap displays is still on, many grayscale displays have appeared on the scene. To fully utilize their capabilities, grayscale fonts are needed, and these can be produced by filtering bi-level masters. Most of the efficient filtering techniques cannot directly be applied. For example, prefiltering is impractical, due to the number of character masters and the requirement of sub-pixel positioning. Furthermore, we would like to impose as few restrictions as possible on the characteristics of the filter, in order to facilitate exploration into the quality of various filters.We describe a fast filtering technique especially adapted to this task. The characters are decomposed into rectangles, and a summed-area representation of the filter is efficiently convolved with each individual rectangle to construct the grayscale character. For a given filter, the number of operations is O (linear size of the grayscale character), which is optimal.We give an analysis of the efficiency of this technique, and examples of its implementation applied to various families of fonts and point sizes. The performance of the implementation is such that filtering characters for grayscale displays is feasible in realtime on personal workstations.

Stochastic modeling has found uses so far mainly for expensive very realistic graphics display. The cost of rendering is not intrinsic to the technique, but mainly due to the high resolution and the sophisticated display techniques which accompany it. We describe here a basic tool for a less expensive approach to stochastic modeling which is designed for a more “down to earth” type of application, and brings the display of stochastic models nearer to real-time.

It' has long been known that the complexity of triangulation of simple polygons having an upper bound of 0 (n log n) but a lower bound higher than ~(n) has not been proved yet.We propose here an easily implemented route to the triangulation of simple polygons through the trapezoidization of simple polygons, which is currently done in O(n log n).Then the trapezoidized polygons are triangulated in O(n) time.Both of those steps can be performed on polygons with holes with the same complexity.We also show in this paper that a number of problems, such as the decomposition of simple polygons into convex, star, monotone, spiral, and trapezoidal polygons and the determination of edgevertex visibility, are linearly equivalent to the triangulation problem and therefore share the same lower bound.It is hoped that this will simplify the task of reducing the gap between the lower and upper bound for these problems.

Popular approaches to speeding up scan conversion often employ parallel processing. Recently, several special-purpose parallel architectures have been suggested. We propose an alternative to these systems: the general-purpose ultracomputer, a parallel processor with many autonomous processing elements and a shared memory. The “serial semantics/parallel execution” feature of this architecture is exploited in the formulation of a scan conversion algorithm. Hidden surfaces are removed using a single scanline, z-buffer algorithm. Since exact anti-aliasing is inherently slow, a novel parallel anti-aliasing algorithm is presented in which subpixel coverage by edges is approximated using a look-up table. The ultimate intensity of a pixel is the weighted sum of the intensity contribution of the closest edge, that of the “losing” edges, and that of the background. The algorithm is fast and accurate, it is attractive even in a serial environment, and it avoids several artifacts that commonly occur in animated sequences.

A recurrent problem in generating realistic pictures by computers is to represent natural irregular objects and phenomena without undue time or space overhead. We develop a new and powerful solution to this problem by modeling objects as sample paths of stochastic processes. Of particular interest are those stochastic processes which previously have been found to be useful models of the natural phenomena to be represented. One such model applicable to the representation of terrains, known as “fractional Brownian motion”, has been proposed by B. Mandelbrot.