Modeling in Computer Graphics

From ancient times, area guide maps have been drawn intuitively without appropriate modeling. Understanding such maps and developing guide map CAD require clear modeling. This paper presents the model of area guide maps using manifolds and CW-complexes. The process of drawing an area guide map is modeled as that of creating a manifold. First, we represent the surface shape of an area as a CW-complex. Then, we glue the CW-complexes representing the areas into a manifold. Surface shapes in the overlaps are blended by a partition of unity. The mechanism to project a surface shape from multiple views is installed. Finally, the area guide map is generated automatically.

In this paper the conjugate transformation of the hexagonal grid is described and its elementary equation is defined. Two strategies are used to extend a matrix morphology into the conjugate transformation. First, the conjugate classification represents 128 structuring elements of the kernel form of the hexagonal grid to a tree of six levels. Each node of a given level is a class of structuring elements with a calculable index. Two conjugate nodes of the same level with the same index can be distinguished by two conjugate sets of 2 * n classes respectively. Second, by considering each element which has six neighbours as a state for any Boolean matrix of the hexagonal grid, it can be transformed into an index matrix relevant to a specific level of the classification. From the index matrix, two sets of Boolean matrices (feature matrices) can be constructed with the same number of classes on the level. Depending on simpler algebraic properties of feature matrices, dilation and erosion can be unified to one operation, reversion, in the elementary equation. The reversion has a self-duality property with a space of 2^2*n functions in which only a total of 2ⁿ⁺¹ functions are dilation and erosion. In addition, several images generated by applying morphological operations using an implemented prototype of the conjugate transformation and their running complexities compared with a matrix morphology, are illustrated. Owing to the class representation, the new scheme has more than a 4–8 speed-up ratio for the general applications.

The paper discusses proposed solutions for constraint-based modelling, with special emphasis on constructive approaches. A new constructive scheme that overcomes a number of the present limitations is proposed. It is based on a non-evaluated, constructive solid model. The proposed approach supports instantiation of pre-defined models, parametric geometric operations in 1D, 2D and 3D, variable topologies, and operations with structural constraints. The EBNF specification of the model definition language is presented and discussed through several examples.

Constrained optimization is used for interactive surface design in our new surface editor. It allows designers to modify B-spline surfaces to satisfy their design intents, expressed as geometric constraints. The restrictions on the set of constraints are few. In the special case of no constraints a surface can be faired to remove design flaws.

Polyhedral approximation of range data has the advantage of being simple to obtain from raw data and of being capable of approximating any sampled surface to the desired precision. Among different possible polyhedral approximation schemes, surface triangulation is a popular one due to its efficiency in computing and storage. Surface triangulation has been used to solve many problems, such as definition of the object shape [BOIS-84], digital terrain modeling [FOWL-79], control of the automatic machining of surfaces [JERA-89], smooth interpolation between 3-D points [LAWS- 77], approximation of the digitized object surfaces [FAUG-84,DELI-91], and computer graphics.

The preservation of collinearity relationships under geometric operations is important in computer-graphics applications that manipulate line arrangements in engineering drawings and geographic information systems. Finite-precision computer implementations of these operations do not generally preserve these relationships. We show that for a wide class of line arrangements, any specified collinearity relationships can be preserved, without extending the precision, at the expense of a bounded displacement of the vertices of the arrangement.

In this paper, we present the development of an interaction simulation model between deformable objects which deal with both collisions and prolonged contacts. The model involves reaction forces (in the normal direction) and friction forces (in the tangential direction). Friction forces are classified as either kinetic friction when the objects are slipping on each other, and static friction when the objects are stuck. This model is developed in the framework of a modular system for dynamic simulations: The CordisAnima system.

In a first part, we will consider the existing physically based methods for movement generation in computer animation and their capacity to tackle the problem of interacting objects. These methods are essentially based on a continuous representation of matter. Then we will present the general context in which our interaction model was developed: a formalism for discrete structural modelling specially directed towards the representation of interactions. The third part is devoted to the description of our interaction model. And finally, we will describe several simulations achieved thanks to the modelor-simulator Cordis-Anima and using our surface interaction model: several kind of wheel drive vehicles crossing over various terrains.

I propose a new 4D interference check method among multiple 3D moving objects. One characteristics of this method is using hexadecimal-tree as a 4D spatial index. Another characteristics is using 4D polyhedron to avoid direct treatment of curved surfaces which are boundaries of 4D motion trajectories. Based on an appropriate 3D geometric modeling system, I experimented on this method in a very simple case. I report its results.

The great potential provided by the existing 3D hardware and software provide us the tools for modeling and displaying complete 3D physical objects in computer systems. Despite the advanced ability to create and display 3D objects, there is a lack of interaction techniques by which the user can intuitively manipulate these 3D objects and perceive information about them.

GIVEN (Gesture-driven Interactions in Virtual ENvironments) is a 3D interaction toolkit which aims at aiding in the development of new 3D interaction and dialogue techniques. The user of the GIVEN toolkit is not dealing any more with a picture of an object. He can directly manipulate 3D objects using 3D input devices, such as spaceball and dataglove, for grabbing, pushing and moving them.

With our first application, for virtual environments, we found out that very unnatural object interactions happen if the collision detection, necessary for the interaction, is made by using only bounding volumes. Precise object interactions are required to let users grab, push and position objects precisely in a 3D world.

For this purpose, a boundary representation was integrated to be used for the implementation of an advanced collision detection scheme.

This paper describes an algorithm for performing the intersection of two polyhedra. New preprocessing algorithms are explained in detail that speed up on average the overall performance of the intersection algorithm. Robustness is achieved by propagating all topological information immediately to the neighbor faces. The application of this algorithm inside GIVEN is also presented.

This paper presents a new mathematical representation for modeling robotic systems based on the use of spherical splines. They can be considered as a generalization of the spline concept with the introduction of control spheres. Very complex volumes modeled by spherical splines are described in funtion of a low number of control spheres. To modify the robot configuration, only control spheres must be recomputed. An extended hierarchical structure with different levels of accuracy including polyhedra, spherical volumes and spherical splines is explained in the paper. Distance computation for collision detection between robots results very fast when this structure is used.

N-dimensional chains of maps, or n-chains, is a combinatorial model defined for representing the topology of cellular complexes. In this paper, we deduce from n-chains specialized combinatorial models for the representation of subsets of cellular complexes. Operations for handling these models are deduced from operations defined for handling n-chains. After generalization and systemization, we think that this study can be used in order to define the kernel of a geometric modeler, not based upon a single combinatorial model, but upon a set of combinatorial models. This can be very useful when simultaneously handling different subsets of cellular complexes.

The Hierarchical Assembly Graph (HAG) is a common representation method for geometric models. The HAG is a directed acyclic graph. Nodes in the graph represent objects, and arcs denote the sub-part relation between objects. Affine transformations and other instantiation parameters are attached to the arcs. An instance of an object in a HAG is defined as a path ending at its node. Information common to all instances whose paths end at a given node can be attached to this node. Data associated with a single instance cannot be attached to any single node or arc in the graph. Such private data can be stored in an external list, hash table, or a partial expansion of the graph into a tree, but all of these schemes have severe drawbacks in terms of storage, access efficiency, or update efficiency.

In geometric modeling two main technologies have been successful and are continuing their development: solid modeling and surface modeling. These techniques are still used separately while being complementary in their advantages: a solid modeler is able to describe objects with a clear distinction between inner and outer parts, whereas a surface modeler is better suited in the description of free form objects, but leaves the model validity to the user responsibility. The integration of the two technologies is therefore an important topic of the current research in the field.

This paper presents a new technique to perform booleans with trimmed curves and surfaces; such a technique is not based on point set classification, but exploits geometry orientation; this makes it able to deal with non closed topologies, thus extending the classical concept of boolean operators. According to this approach several valid operators can be defined, which behave like booleans in the case of closed topologies but differently with non closed ones.

This paper presents an interactive deformation technique. The entity employed for defining the deformation of an object is a 3D axis as well as some associated parameters.

The technique allows an easy specification and control of deformations that can be defined with that entity such as bending, twisting and scaling.

Contrary to existing techniques, the method developed is independent of both the geometric model of the object to be deformed and the creation technique used to define the object.

Moreover, it can easily be integrated into traditional interactive modeling systems.

This paper proposes a method of generating surfaces from a network of curves that have arbitrary parametric forms, and that intersect in an arbitrary topology.

The surfaces generated from the network are represented by multisided patches defined on a multivariate coordinate system. An m-sided patch is generated by blending m sub-surfaces with a transfinite interpolant, and each sub-surface is generated by blending two sweep surfaces that are defined by a pair of curves intersecting with each other in the network. An advantage of the final surfaces is that they have everywhere the same order of continuity as the curves.

This method is flexible in its representation of the curve expressions and the connective topology of a network. It can implement a surface model in user-friendly and designer-oriented CAD interfaces that handle direct input of 3D curves.

Freeform surfaces are commonly used in computer aided geometric design, so accurate analysis of surface properties is becoming increasingly important. In this paper, we define surface slope and surface speed, develop visualization tools, and demonstrate that they can be useful in the design process. Generally, surface properties such as curvature and twist are evaluated at a finite set of predetermined samples on the surface. This paper takes a different approach. A small set of tools is used to symbolically compute surfaces representing curvature, twist and other properties. These surfaces are then analyzed using numeric techniques.

The Combination of symbolic computation to provide an exact property representation (up to machine accuracy) and numerical methods to extract data is demonstrated to be powerful and robust. This approach supports a uniform treatment once the surfaces are computed and also provides global information, so questions such as ‘is a surface developable?’ or ‘what are the hyperbolic regions of a surface?’ can be answered robustly.

The first order cross boundary derivatives of Bézier rectangles and triangles are independently derived for each boundary by putting the Bézier points in the rational Bézier form. This representation simplifies the cross boundary construction in connecting two Bézier patches. Degree elevation allows handling the Bézier rectangle and triangle in a uniform manner. The interpolating surfaces take the standard Bézier form except the control points are convex combinations of the control points defining the cross boundary derivatives. The blending functions are in the rational Bézier form of the smallest degree and have the minimum significant values to define the control points. The surfaces having rational Bézier points can be easily and economically converted to rational Bézier surfaces, however, with zero weight Bézier points at comers. A method for removing such singularities is also described.

We describe a method to generate blend surfaces which fit with continuous curvature to the primary surfaces. This blend surface is obtained as the bicubic tensor spline minimizing a variational problem. Among all the bicubic tensor splines which give a curvature continuous blend surface, the one is chosen which minimizes a bilinear functional. In Section 2 we summarize and extend the results of a previous paper in such a way that they are applicable to our problem. In Section 3 we outline in detail the procedure how to generate a blend surface based on these results.

Smooth surface patches, such as Gregory patch, Brown’s square and Nielson- Foley patch, which interpolate a given function and its derivatives on the boundary of a rectangle or a triangle, with incompatible twist terms, have been constructed with rational parametric representation by using boolean sum techniques, convex combination methods and procedural methods to fill N-sided holes. Chiyokura and Kimura proposed a representation of Gregory patch in Bernstein-Bezier form, where interior control points are expressed as convex combinations of incompatible control points via rational blending functions. No such representation is known for solutions to the above problem over pentagonal domains. We construct smooth rational surface patches which interpolate a given function and its cross-boundary C ^k derivatives on the boundary of any convex polygonal domain with incompatible twist data. These patches are represented in S-patch form, where control points are expressed as convex combinations of incompatible control points via rational blending functions. This constructive rational technique provides novel solutions for blending incompatible C ^k data over polygonal domains. In particular, new solutions are constructed for rectangular and triangular patches as well.

An algorithm for the construction of a non-uniform cubic B-spline curve that interpolates a set of 2D data { D _i } is presented. Each D _i is either a point or a region. If D _i is a point, the curve interpolates it. Otherwise, the curve passes through the region specified by D _i The curve is constructed based on minimizing the energy of each of its components. The parametric knots of the curve are parametrized using the centripetal model. These processes facilitate the geometric smoothness and fairness of the curve. The new technique allows a user to design a curve with more flexibility and fewer trial-and-error iterations than conventional approach. This work is a continuation of the paper “Interproximation: Interpolation and Approximation Using Cubic Spline Curves” published in 1991.

Description of an interaction of a charged particle with fields is well known, in principle. Under some conditions, this system undergoes a very complicated behaviour. Two challenging tasks must be met, before the deeper insight into and understanding of the dynamics of such a system can be retrieved from the modelling: numerical and representational. The former is due to the excessive computer processing times, the latter deals with a way to display the large amount of data in a useful way. In this paper, we concentrate on the latter and describe some aspects of producing an animated display, within the tight budgetary constraints.

This paper describes methods for acquiring and analyzing in real-time the motion of human faces. It proposes a model based on the use of snakes and image processing techniques. It explains how to generate real-time facial animation corresponding to the recorded motion. It also proposed a strategy for the communication between animators and synthetic actors.

This paper describes an approach to use artificial reality techniques for real-time interpersonal visual communication at very low bitrate. A flexible structure is suitably adapted to the specific characteristics of the speaker’s head by means of few parameters estimated from the analysis of the real image sequence, while head motion and facial mimics are synthesized on the model by means of knowledge-based deformation rules acting on a simplified muscle structure. The analysis algorithms performed at the transmitter to estimate the model parameters are based on feature-oriented operators aimed at segmenting the real incoming frames and at the extraction of the primary facial descriptors. The system performances have been evaluated on different “head-and-shoulder” sequences and the precision, robustness and complexity of the employed analysis/synthesis algorithms have been tested. Promising results have been achieved for applications both in videophone coding and in picture animation where the facial mimics of a synthetic actor is reproduced according to the parameters extracted from a real speaking face.

The development of solid modeling has been motivated primarily by its potential for supporting automated applications. Analytic applications have been addressed successfully, and algorithms are available for visualization, mass property calculation, static interference analysis, kinematic simulation of mechanisms, and simulation of manufacturing processes such as machining. Work on automatic meshing for Finite Element Analysis (FEA), simulation of semiconductor fabrication operations, and electronic packaging is progressing nicely.

Features are real existing constituencies of product parts that associate engineering significance with shapes. A feature-based representation of product models is an essential prerequisite to the development of a new generation of Computer Aided Design systems.

In this paper, we propose a system architecture for feature-based modeling which is founded on the integration of two approaches: feature extraction from existing solid models and design-by-features. This integration is obtained through the definition of a common feature library and a Unified Model, which plays the role of communication link between the geometric model and the feature- based model. This system should enable the user to mix the two modes of definition allowing him to design an object directly with features or to start with a geometric model and to extract a feature model from it.

In traditional CAD and solid modeling, 3D objects are represented in terms of their geometric components. In contrast, in volume graphics 3D objects are represented by a discrete digital model, which is stored as a large 3D array of unit volume elements (voxels). The rapid progress in hardware, primarily in memory subsystems, has been recently transforming the field of volume graphics into a major trend which offers an alternative to traditional 3D surface graphics. This paper discusses volume graphics and several related modeling techniques.

We present a simple, effective, and efficient technique for approximating arbitrary polyhedra. It is based on triangulation and vertex-clustering, and produces a series of 3D approximations (also called “levels of detail”) that resemble the original object from all viewpoints, but contain an increasingly smaller number of faces and vertices. The simplification is more efficient than competing techniques because it does not require building and maintaining a topological adjacency graph. Furthermore, it is better suited for mechanical CAD models which often exhibit patterns of small features, because it automatically groups and simplifies features that are geometrically close, but need not be topologically close or even part of a single connected component Using a lower level of detail when displaying small, distant, or background objects improves graphic performance without a significant loss of perceptual information, and thus enables realtime inspection of complex scenes or a convenient environment for animation or walkthrough preview.

This paper presents a volume rendering technique called the volume tracing. Volume tracing is an extension to ray tracing rendering technique. In this paper, we focus on the rendering of soft objects. Soft objects include implicit surfaces which are called “the metaballs”. The visualization of volume data defined by soft objects is achieved by the use of volume tracing.