We present an algorithm for generating a piecewise G1 circular spline curve from an arbitrary given control polygon. For every corner, a circular biarc is generated with each piece being parameterized by its arc length. This is the first subdivision scheme that produces a piecewise biarc curve that can interpolate an arbitrary set of points. It is easily adopted in a recursive subdivision surface scheme to generate surfaces with circular boundaries with pieces parameterized by arc length, a property not previously available. As an application, a modified version of Doo–Sabin subdivision algorithm is outlined making it possible to blend a subdivision surface with other surfaces having circular boundaries such as cylinders.

We present a method for computer generated pen‐and‐ink illustrations by the simulation of stippling. In a stipple drawing, dots are used to represent tone and also material of surfaces. We create such drawings by generating an initial dot set which is then processed by a relaxation method based on Voronoi diagrams. The point patterns generated are approximations of Poisson disc distributions and can also be used for integrating functions or the positioning of objects. We provide an editor similar to paint systems for interactively creating stipple drawings. This makes it possible to create such drawings within a matter of hours, instead of days or even weeks when the drawing is done manually.

We consider the problem of real-time animation of a cartoon character which is represented by a skeleton implicit surface. If the character's motions permit a constant topology for the skin, it is possible to reduce the problem of computing an approximation of the implicit surface to solve only one scalar equation per surface point for a fixed number of surface points; these surface points define the shape of a triangle mesh with constant topology. We present the algorithm, and demonstrate its working in a real-time model of walking cartoon legs.

A new method is presented for watermarking digital images and video streams. This technique embeds information in an image by changing the geometric features of the image. The method is essentially different from existing techniques in which a pseudo-noise pattern is added to the image. The new method has the advantage that the detection is computationally faster than existing methods. Furthermore, it is easier to detect the watermark in images that have been rotated, scaled, or distorted by a geometric transformation. The watermark is formed by a predefined dense pixel pattern, such as a collection of lines. Salient points in an image are warped into the vicinity of the line pattern in such a way that the changes to the image are imperceptible.

In order to achieve the impression of a smooth surface while rendering a polygon mesh, normal vector vectors may be provided in the vertices of the mesh that are the average of the surface normals of the adjacent polygons. Interpolation of these normal vectors while rendering of the polygons in the mesh, and using the interpolated normal vectors in the shading computations, yields a smoothly varying intensity distribution. There is an inherent mismatch, however, between the smoothness of the shading thus achieved and the non-smoothness of the geometry which is particularly visible at silhouettes, showing as straight edges and non-smooth edge junctions at the silhouette vertices. A remedy for these artefacts is suggested. The remedy consists of subdividing each input polygon into a mesh of polygons prior to rendering. The shape of this resulting polygon mesh is controlled by the normal vectors that are provided in the vertices of the original polygon, unlike other subdivision schemes that make use of adjacent polygons. With the method, polygons equipped with vertex normal vectors can therefore be processed without further knowledge of neighbour polygons. This makes the method well-suited in the context of graphics libraries, such as OpenGl, that treat polygons typically on a per-polygon basis. So the proposed computation of the mesh which replaces the original polygon can be viewed as a filter which may operate as a process in front of a traditional polygon rendering pipeline.

Freeform deformations are useful for describing a class of complex motions within an animation system. Such deformations have been described using a generalization of parametric surfaces and their application to modeling is well documented. We present a method that can be applied to implicit surfaces which are defined as an iso surface around a set of skeletal elements. The resulting surface is approximated by a polygon mesh. Shape distortions, such as "squash and stretch" are applied automatically to models in motion by warping the space in which the models exist. A model will change its shape as the function defining the warped space can change over time or the model will deform as it moves through the warped space. Our system also treats groups of skeletal implicit primitives as CSG primitives. Warping can also be applied to these primitives. Different warp functions, for example bend, taper and twist can be applied locally or globally, the contribution from each primitive is calculated using a set of warp functions associated with that primitive. The interesting shapes, and possibly nonlinear motion obtained from space warping, would be difficult to reproduce using other techniques.

A method for the extrusion of arbitrary polygon meshes is introduced. This method can be applied to model a large class of complex 3-D closed surfaces. It consists of defining a (typically small) set of connected polygons in 3-D that form a skeleton of the final object, and assigning extrusion distances to all polygons. The two sides of a polygon may have different extrusion distances. An automatic extrusion algorithm constructs a closed 3-D polygon mesh around the skeleton, making use of the indicated extrusion distances. We call this process inflating the polygons of the skeleton. Unlike traditional extrusion, the method works for non-planar skeleton configurations, and it also supports branching skeleton structures (i.e. edges with more than two incident polygons). © 1997 by John Wiley & Sons, Ltd.

Phong shading is one of the best known, and at the same time simplest techniques to arrive at realistic images whem rendering 3D geometric models. However, despite (or maybe due to) its success and its widespread use, some aspects remain to be clarified with respect to its validity and robustness. This might be caused by the fact that the Phong method is based on geometric arguments, illumination models, and clever heuristics. In this article we address some of the fundamentals that underlie Phong shading, such as the computation of vertex normals for nonmanifold models and the adequacy of linear interpolation and we apply a new interpolation technique to achieve an efficient and qualitatively improve result.

This paper describes an augmentation to the spline concept to account for topological relations between different spline curves. These topological relations include incidence relations, constraining the extremes of spline curves to other spline curves, and also more general geometric relations, for example, involving the tangents of spline curves in their extremes. To maintain these incidence relations, some spline curves may have to be transformed (translated, rotated, scaled), or even deformed (i.e., the shape of the curve may change) as a result of modifying other spline curves. A data structure and algorithms are given to implement the propagation of these transformations and deformations. Based on the augmented spline concept, to be called sticky splines , both a script system to represent spline structures and an interactive system for editing drawings while automatically, maintaining their topological structure are presented.

A geometric and kinematic model for describing the global shape and the predominant motions of the human tongue, to be applied in computer animation, is discussed. The model consists of a spatial configuration of moving points that form the vertices of a mesh of 9 3-D triangles. These triangles are interpreted as charge centres (the so-called skeleton) for a potential field, and the surface of the tongue is modelled as an equi-potential surface of this field. In turn, this surface is approximated by a triangular mesh prior to rendering. As to the motion of the skeleton, precautions are taken in order to achieve (approximate) volume conservation; the computation of the triangular mesh describing the surface of the tongue implements penetration avoidance with respect to the palate. Further, the motions of the skeleton derive from a formal speech model which also controls the motion of the lips to arrive at a visually plausible speech synchronous mouth model.>

Abstract Recently, the dynamics of linked articulated rigid bodies has become a valuable tool for making realistic three‐dimensional computer animations. An exact treatment of rigid body dynamics, however, is based on rather non‐intuitive results from classical mechanics (e.g. the Euler equations for rotating bodies) and it relies heavily on sophisticated numerical schemes to solve (large) sets of coupled non‐linear algebraic and differential equations. As a result, articulated rigid bodies are not yet supported by most real‐time animation systems. This paper discusses an approach to rigid body dynamics which is based on (both conceptually and algorithmically much simpler) point mechanics; this gives rise to an asymptotically exact numerical scheme (NSI) which is useful in the context of real‐time animation, provided that the number of degrees of freedom of the simulated system is not too large. Based on NSI, a second scheme (NS2) is derived which is useful for approximating the motions of linked articulated rigid bodies; NS2 turns out to be sufficiently fast to give at least qualitative results in real‐time simulation. In general, the algorithm NS2 is not necessarily (asymptotically) exact, but a quantitative analysis shows that in the absence of reaction forces it conserves angular momentum.

Abstract A simple approach for the simulation of bipedal locomotion is presented. It is based on a kinematically driven rigid body dynamics simulation. As inputs, our system uses a 14‐DOF simplified human body model, and the instantaneous walking direction and the gait length. From these parameters, the trajectories of the left and right feet are computed over time, using a purely kinematical recipe. Optionally, trajectories of other body parts (head, shoulders, hips, hands, knees, etc.) may be derived from a simple kinematic body model. Using these additional trajectories provides for increased control over the motion, adding extra kinematic constraints to the dynamical system. The trajectories, together with optional force fields (gravity etc.), serve to drive the motion of the articulated human body model. This means that for those points in the body that have not been specified kinematically, a rigid body dynamics calculation is used to describe their motion over time. An implementation of these ideas turns out to allow a frame update rate of about 20 Hz on a personal IRISTM workstation, which is sufficiently fast for real‐time interaction.

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

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

Abstract The concept of the display processor unit (DPU; see Reference 1, p. 94) is extended to arrive at a generalized display processor (GDP) which is able not only to produce a static screen image given the descriptions of a list of graphics elements but which allows for these graphics elements to show an autonomous kinematic (motion‐)behaviour. A language to program such a GDP is presented, and a software implementation of an interpreter/processor for this language is discussed. The application of a GDP both in computer animation and in interactive process control applications is sketched.

In this paper an algorithm is described for filling triangles in 3D. Since this algorithm uses integer arithmetic only, it is not hampered by inconsistencies that normally arise due to finite machine precision. Moreover, the same algorithm is used for both curved and flat triangular patches.