main-content

## Über dieses Buch

Since its very existence as a separate field within computer science, computer graphics had to make extensive use of non-trivial mathematics, for example, projective geometry, solid modelling, and approximation theory. This interplay of mathematics and computer science is exciting, but also makes it difficult for students and researchers to assimilate or maintain a view of the necessary mathematics. The possibilities offered by an interdisciplinary approach are still not fully utilized. This book gives a selection of contributions to a workshop held near Genoa, Italy, in October 1991, where a group of mathematicians and computer scientists gathered to explore ways of extending the cooperation between mathematics and computer graphics.

## Inhaltsverzeichnis

### 1. Integer Approximation to the Intersection of Three Planes with Planar Constraints

Abstract
The intersection point of three planes specified with rational coordinates is approximated by a point with integer-valued coordinates so that the integer point is constrained within the pyramid specified by three half-spaces of the planes. An O(N log N) algorithm guarantees that the obtained integer point is closest to the apex of the pyramid. An O(log N) algorithm, not yet proven to guarantee the closest point, yields promising results.
Maharaj Mukherjee, George Nagy, Shashank Mehta

### 2. Approximate C1—blending with Triangular Cubic Patches

Abstract
This paper discusses a simple construction of triangular surfaces with prescribed boundary and cross boundary derivative curves. These surfaces are continuous piecewise cubics with arbitrarily small jumps in their first derivatives. Moreover, they form a sequence which converges to a proper C1—surface which is again piecewise cubic and interpolates the given boundary information.
Hartmut Prautzsch

### 3. A Geometric Approach to Bézier Curves

Abstract
Using techniques from classical geometry we present a purely geometric approach to Bézier curves and B-splines. The approach is based on the intersection of osculating flats: The osculating 1-flat is simply the tangent line, the osculating 2-flat is the osculating plane, etc. The intersection of osculating flats leads to the so-called polar form. We discuss the main properties of the polar form and show how polar forms lead to a simple new labeling scheme for Bézier curves and B-splines.
Hans-Peter Seidel

### 4. Representing and Modeling of Cyclide Patches using NURBS

Abstract
In this paper we introduce a method to represent cyclide patches using NURBS. This representation enables us to implement cyclide patches in a NURBS—based interactive environment and to enhance the flexibility of modeling with cyclide patches.
Xiaolin Zhou

### 5. Local Parametrization of Space Curves at Singular Points

Abstract
We propose a symbolic computation algorithm for computing local parametrization of analytic branches and real analytic branches of a curve in n-dimensional space, which is defined by implicit polynomial equations. The algorithm can be used in space curve tracing near a singular point, as an alternative to symbolic computations based on resolutions of singularities.
Maria E. Alonso, Teo Mora, Gianfranco Niesi, Mario Raimondo

### 6. Shape of Curves and Surfaces: the Combinatorics

Abstract
This paper develops some points that were only sketched in the companion paper [6], in particular explaining the combinatorial part of the algorithms for the computation of the topology of real plane curves and space surfaces. The origin of these algorithms is [11].
In particular, for the curves, we compute the shape through a computation of the intersection of the curve with the vertical tangents. From the number and placement of the roots of the intersection we can derive an explicit description of the shape. For the surfaces, we derive the information on the topology considering the change of the shape of a plane section, through a computation of the rank of the homology groups of the connected components.
Paola Cellini, Patrizia Gianni, Carlo Traverso

### 7. Two Surfaces Suffice

Abstract
Classical elimination theory is the study of conditions that guarantee the existence of solutions to systems of polynomial equations. The main goal is to construct a set of polynomial expressions in the coefficients of the original polynomial equations, which are satisfied exactly when the original polynomials have a common root. For n polynomials in n−1 unknowns, there is a single unique condition called the resultant. More generally, for an arbitrary number of equations and unknowns many conditions may be required; these conditions are called resolvents. Unfortunately, classical resolvents are not practical because they yield far too many conditions which are very expensive to compute.
In this paper, we develop a new resolvent which is computationally efficient, and we apply it to solve the space curve/curve intersection problem in Computer Aided Geometric Design (CAGD).
One way to solve the curve/curve intersection problem is to solve the implicitization and inversion problems. By applying our new resolvent, we find that generally two surfaces of relatively low degree suffice to implicitize any 3D, faithfully parametrized, polynomial curve, and the inversion equation is also a rational expression of relatively low degree. Thus we provide a very efficient curve/curve intersection algorithm for low degree, 3D, polynomial curves.
Hang K. Du, Ronald N. Goldman

### 8. Does a Trigonometric Curve Cross an Algebraic Surface?

Abstract
A symbolic method is given to decide whether or not a curve in three dimensional space given parametrically by three trigonometric $$\begin{array}{*{20}{c}} {x = {p_1}\left( {t,\sin \left( t \right),\cos \left( t \right)} \right)} \\ {y = {p_2}\left( {t,\sin \left( t \right),\cos \left( t \right)} \right)} \\ {z = {p_3}\left( {t,\sin \left( t \right),\cos \left( t \right)} \right)} \end{array}$$ polynomials crosses an algebraic surface, given as the zero set of a polynomial in three variables. The technique uses false derivative and local Sturm sequences.
Daniel Richardson

### 9. Incidence Relationships: Kernel Concept in Combinatorical Topology

Abstract
In this paper we introduce the concept of incidence relationships in combinatorial topology and show that it is the counterpart concept of nearness in point set topology. Starting from the concept of incidence relationships, we investigate several problems in B-rep solid modelling, namely the mathematical models of solids, the representations of non-manifold solids, and the mathematical expressions for regularized Boolean operations on B-rep solid models.
Yi Luo, Gábor Lukács

### 10. A Taxonomy on Geometric and Topological Models

Abstract
Mathematical fundamentals of point set topology and combinatorial topology are reviewed. All geometric models of practical interest are found to be finite collections of manifold elements of different dimensionalities, with boundary incidence as the most important relation among the elements. Based on this observation a classification scheme is proposed, characterizing a model topologically according to the compositional structure, boundary relations, dimensionality and connectivity of its elements. Geometric shapes are characterized as embeddings of manifolds into the Euclidian space, giving emphasis to homotopy groups. Accidental inconsistencies between embeddings and topological data are discussed, along with surgery operations on them. In focus of criticism is the inexact use of common terms like “boundary representation”, “regularization” and “non-manifold model”, which are here reconsidered mathematically.
Tapio Takala

### 11. Multilevel Generation of Fractal Images Using the Associated Markov Process

Abstract
Using a set of contractive affine transformations, one can describe an image with intricate detail. However, the process of generating fractals with these transformations is an expensive operation. In this paper, it is shown that it can become significantly less expensive, when looking at the iteration of a set of affine transformations as a Markov process. Using the special structure of the state transition matrix for the solution of the large set of equations, some multilevel scheme-algorithms emerge.
Marc Coevoet

### 12. Statistical Colour Quantization for Minimum Distortion

Abstract
Colour quantization for frame buffer displays, a basic computer graphics technique for efficient use of colours, is statistically a large scale clustering process and it poses a difficult discrete optimization problem. Many heuristic color quantization algorithms were proposed [7, 12, 22, 24] but they all suffer from various degrees of non-adaptability to the colour statistics of input images. In this article we will introduce an adaptive colour image quantization algorithm that outperforms existing algorithms in subjective image quality and in least square approximation sense. The new algorithm eliminates many current suboptimal treatments of colour quantization such as a prequantization of discarding few lower bits of RGB values, restricted cuts orthogonal to RGB axes, partition criteria based on population or marginal distributions rather than variance minimization. A constrained global optimization scheme is incorporated into a divide-and-conquer clustering process to minimize quantization distortion. The time and space complexities of the new algorithm are O(N log K) and O(N), where N is the number of pixels in the image and K is the number of colours in quantized image.
Xiaolin Wu

### 13. Minimizing the Absolute Value Energy Function: An Application to Geometrical Constraint-Solving

Abstract
This paper proposes a new connectionist model to minimize the absolute value energy function based on the Boltzmann machine. In conventional models, n th-order constraints (nonlinear optimization problems) are solved by minimizing the 2n thorder energy function, which brings forth explosive increase of the number of units and connections among them. By using the absolute value energy function, n th-order constraints can be directly represented by the n th-order energy function. Hence, a very great reduction of the network complexity becomes possible. Our model is particularly suited for applications, such as geometrical constraint-solving, in which nonlinearity plays a definitive role.
Nami Kin, Yoshiaki Takai, Tosiyasu L. Kunii

### 14. Geometric Constraint Propagation with Quantum Labels

Abstract
This paper presents an incremental approach to geometric constraint satisfaction that categorizes solutions into so-called quanta. A quantum is a range of solutions with uniform geometric characteristics. This approach is suitable for interactive design because it can handle (perhaps temporarily) incomplete specifications and alternative solutions, and performs satisfaction locally and incrementally. The intermediate solutions are kept in the geometric domain, so that new geometric constraints can be interpreted on the same high level of abstraction, allowing powerful reasoning. Both alternative discrete solutions and continuous ranges of solutions are determined. Propagation of information is performed by ‘propagation of known state’, and the information itself results from ‘solution set inference’, where a solution set is represented in geometrical form by unions and intersections of quantum labels. This representation allows the use of simple logical expressions of constraints, it uniformly handles delayed satisfaction, and it supports ‘constraint inference’, the derivation of implied constraints by geometric reasoning.

### 15. Computer Vision, Descriptive Geometry, and Classical Mechanics

Abstract
The medial-axis transform, also called skeleton, is a shape abstraction proposed by computer vision. The concept is closely related to cyclographic maps, a tool developed by descriptive geometry to investigate distance functions, and to the solution of the eikonal equation. We discuss these connections and their implications on techniques for computing the skeleton.
Christoph M. Hoffmann

### 16. Discrete Surface Models: Constraint-based Generation and Understanding

Abstract
A two level description is proposed for natural surface modelling: a geometric model, in terms of low level primitive entities, and a conceptual model, which is a symbolic surface representation based on its prominent shape characteristics. The geometric and conceptual level can exchange information using two operators: the abstraction operator and the generation operator.
An abstraction mechanism, based on the analysis of the Gaussian curvature, can be applied to a faceted model of the surface in order to identify subsets of primitive entities linked to particular morphological configurations.
A generation operator produces a geometric model through a tessellation technique that can keep constraints imposed by a high level description of the surface morphological characteristics. The level of approximation and quality of the visualization can be controlled by including an appropriate subset of the data points, and/or by using a stochastic perturbation to generate fractal-like details.
Bianca Falcidieno, Caterina Pienovi, Michela Spagnuolo

### 17. Visualization of Depth Maps

Abstract
Coordinate systems are presented for fast 3-D transformations of complex surfaces, such as the depth maps produced by a laser camera or by a viewing algorithm. It is shown that these coordinate systems are natural for calculation on depth maps and correspond to a differential geometry approach of the problem. We describe algorithms using these coordinate systems to realize perspective to perspective and parallel to parallel view transformations. These parallel algorithms can be implemented using 1-D transformations only.
Jacques Lemordant

### 18. An Analysis of Digitalization Algorithms for Non-linear Curves

Abstract
A brief introduction of the model, based on discrete lattices, used for rasterization onto both the square and the hexagonal lattice is given. Some of the existing rasterization algorithms for non-linear curves, in particular fixed step, forward and adaptive forward differencing, and bisection algorithms are analyzed and ported to perform rasterization onto the hexagonal lattice. A new bisection algorithm, based on the mean value theorem, is proposed. This algorithm naturally adapts the density of the sampling points of the curve to its curvature, increasing the point density where the curvature is greater.
Charles A. Wüthrich

### 19. Visualizing Hyperbolic Space

Abstract
Computer graphics opens windows onto previously unseen mathematical worlds. This has been firmly established in the study of chaotic dynamical systems, where signif­icant mathematical discoveries can be directly traced to the advent of visual display of computation. Other realms of science and mathematics stand to derive particular benefit from the powers of computer graphics. For example, non-Euclidean geometry is fundamental to many research areas in mathematics and physics. Heretofore, this has not been amenable to visualization, because standard visualization environments are implicitly Euclidean, or flat. Some of the simplest examples of these curved spaces are non-Euclidean geometries of constant curvature. This paper will describe work in visualizing such geometries, undertaken at the Geometry Supercomputer Project as part of a program to explore 3-dimensional manifolds. In particular, we demon­strate techniques for realistic rendering in three-dimensional hyperbolic space using readily available software tools. We have demonstrated the usefulness of these tools by making a computer graphics movie “Not Knot” which contains several minutes of animation inside hyperbolic space.
The discussion will be structured as follows:
• Previous work
• Mathematical models of hyperbolic geometry.
• Comparison of utility of different models of hyperbolic geometry.
• Rendering in hyperbolic space using custom Renderman 1 shaders.
• Three dimensional topology and hyperbolic geometry.
• A case study: the Borromean rings and the video “Not Knot”
• Conclusion and new directions.
• Appendix 1: Copy of Renderman shader for hyperbolic plastic surface.
Charlie Gunn

### Backmatter

Weitere Informationen