Skip to main content
main-content

Über dieses Buch

In the history of technology, many fields have passed from an initial stage of empirical recipes to a mature stage where work is based on formal theories and procedures. This transition is made possible through a process called "modeling". Also Computer Graphics as a separate field of Computer Science makes extensive use of formal theories and procedures of modeling, often derived from related disciplines such as mathematics and physics. Modeling makes different application results consistent, unifying varieties of techniques and formal approaches into a smaller number of models by generalizing and abstracting the knowledge in Computer Graphics. This volume presents a selection of research papers submitted to the conference "Modeling in Computer Graphics: Methods and Applications" held at the Research Area of the National Research Council in Genoa, Italy, on June 28 -July 1, 1993. This meeting was the ideal continuation of a previous conference organized in Tokyo, Japan, in April 1991. The success and the variety of research themes discussed at that meeting suggested to promote a new working conference on methods and applications of modeling to be held in Italy two years later.

Inhaltsverzeichnis

Frontmatter

Methods of Modeling

Frontmatter

Mathematical Modeling for Vision and Graphics

Area Guide Map Modeling by Manifolds and CW-Complexes

Abstract
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.
Tosiyasu L. Kunii, Shigeo Takahashi

The Elementary Equation of the Conjugate Transformation for the Hexagonal Grid

Abstract
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 22*n functions in which only a total of 2n+1 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.
Z. J. Zheng, A. J. Maeder

Generating Views of 3D Objects from Viewer-Centered Representations

Abstract
Computer vision and graphics applications involve generating views of 3D objects. We present a scheme for generating views of objects from viewer-centered representations. In this scheme an object is modeled by a small number of views with the correspondence between the views. Novel views of the object are generated by linearly combining the model views. The scheme handles rigid objects accurately and was extended to handle objects with smooth bounding surfaces and articulated objects. To construct models for this scheme, the correspondence between the model views should be recovered. The paper concludes with an algorithm to achieve such correspondence.
Ronen Basri

Modeling with Constraints

A System for Constructive Constraint-Based Modelling

Abstract
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.
Lluis Solano, Pere Brunet

Constrained Optimization in Surface Design

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

Adaptive Range Data Approximation by Constrained Surface Triangulation

Abstract
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.
Xin Chen, Francis Schmitt

Collinearity Constraints on Geometric Figures

Abstract
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.
Maharaj Mukherjee, George Nagy

Modeling of Dynamic Objects

Animation of Interacting Objects with Collisions and Prolonged Contacts

Abstract
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.
Stéphane Jimenez, Annie Luciani

Hexadecimal-Tree: A Time-Continuous 4D Interference Check Method

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

Precise Object Interactions using Solid Modeling Techniques

Abstract
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.
Mauro Figueiredo, Klaus Böhm, José Teixeira

On the Spherical Splines for Robot Modeling

Abstract
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.
Martin Mellado, Josep Tornero

Geometric Modeling

Different Combinatorial Models based on the Map Concept for the Representation of Subsets of Cellular Complexes

Abstract
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.
Hervé Elter, Pascal Lienhardt

A Scheme for Single Instance Representation in Hierarchical Assembly Graphs

Abstract
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 this paper we present a scheme for representing single instances in the assembly graph itself, by identifying an instance with the last node in its path when the only way of reaching the last node is through a unique path starting at the first node of the path. We give an algorithm for singling an instance in the graph, i.e. transforming the graph into an equivalent one in which the instance can be identified with a node. We also show how to undo an instance’s singling when its private data is no longer needed.
Ari Rappoport

Towards the Integration of Solid and Surface Modeling by Means of Pseudo-Boolean Operators

Abstract
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.
Luca Mari, Cristiano Sacchi

Surface Modeling as a Creative Tool

Interactive Axial Deformations

Abstract
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.
Francis Lazarus, Sabine Coquillart, Pierre Jancène

Surface Generation from an Irregular Network of Parametric Curves

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

Hybrid Symbolic and Numeric Operators as Tools for Analysis of Freeform Surfaces

Abstract
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.
Gershon Elber, Elaine Cohen

Curve and Surface Modeling

Smooth Surface Interpolation with Bézier Surfaces Having Rational Bézier Points

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

Curvature continuous blend surfaces

Abstract
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.
Günther Greiner, Hans-Peter Seidel

Filling N-sided Holes

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

Finite Representations of Real Parametric Curves and Surfaces

Abstract
Algebraic curves and surfaces are commonly used in geometric modeling. Parametric curves and surfaces are those that can be represented using rational parametric equations, and are particularly important. In geometric modeling applications, the parametric equations are restricted to some bounded portion of the domain, yielding a segment of a curve or a patch of a surface. However, the algebraic curve or surface is an image of the entire infinite parameter domain. Attempting to map the entire curve or surface using very large regions of the parameter domain is not a solution because some finite points may be images of infinite parameter values.
Chandrajit L. Bajaj, Andrew V. Royappa

Interproximation using Cubic B-Spline Curves

Abstract
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.
Fuhua Cheng, Brian A. Barsky

Modeling for Applications

Frontmatter

Modeling for Animation

Animated Parameter Space

Abstract
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.
Miroslav M. Novak

Modelling Facial Communication Between an Animator and a Synthetic Actor in Real Time

Abstract
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.
Nadia Magnenat Thalmann, Antoine Cazedevals, Daniel Thalmann

Synthesis and animation of human faces: artificial reality in interpersonal video communication

Abstract
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.
S. Curinga, A. Grattarola, F. Lavagetto

Modeling for CIM Applications

Reasoning about Physical Solids and Processes

Abstract
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.
Aristides A. G. Requicha

Integration of Design by Features and Feature Recognition approaches through a Unified Model

Abstract
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.
T. De Martino, B. Falcidieno, F. Giannini, S. Haßinger, J. Ovtcharova

Modeling for Rendering Complex Objects

Modeling in Volume Graphics

Abstract
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.
Arie Kaufman, Roni Yagel, Daniel Cohen

Multi-resolution 3D approximations for rendering complex scenes

Abstract
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.
Jarek Rossignac, Paul Borrel

Volume Tracing Soft Objects

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

Backmatter

Weitere Informationen