Computational Methods for Algebraic Spline Surfaces (COMPASS)

Main page

Contents

Introduction

Cover

Sample chapter

Ordering information

Distance Separation Measures Between Parametric Curves and Surfaces Toward Intersection and Collision Detection Applications
Gershon Elber

This paper investigates the use of separation measures for parametric curves and surfaces toward the resolution of interference and intersections between curves and surfaces as well as collision detection. Two types of distance separation measures are discussed. While the trivial distance function can be derived quite efficiently, it is shown in this work that this trivial distance function is not the optimal approach, in general. better and more efficient scheme that projects the distance onto the normal field of either manifold is demonstrated to be superior in correctly detecting highly coupled non-intersecting arrangements as such.
Finally, a few extensions that further ease the detection of intersection-free arrangements, for both planar arrangements and arrangements in IR^3, are also discussed.

Self-Intersection Problems and Approximate Implicitization
Jan B. Thomassen

We discuss how approximate implicit representations of parametric curves and surfaces may be used in algorithms for finding self-intersections. We first recall how approximate implicitization can be formulated as a linear algebra problem, which may be solved by an SVD. We then sketch a self-intersection algorithm, and discuss two important problems we are faced with in implementing this algorithm: What algebraic degree to choose for the approximate implicit representation, and for surfaces how to find self-intersection curves, as opposed to just points.

Third Order Invariants of Surfaces
Jens Gravesen

The classical invariant theory from the 19th century is used to determine a complete system of 3rd order invariants on a surface in three-space. The invariant ring has 18 generators and the ideal of syzygies has 65 generators. The invariants are expressed as polynomials in the components of the first fundamental form, the second fundamental form and the covariant derivative of the latter, or in the case of an implicitly defined surface - M=f^-1(0) - as polynomials in the partial derivatives of f up to order three.
As an application some commonly used fairings measures are written in invariant form. It is shown that the ridges and the subparabolic curve of a surface are the zero set of invariant functions and it is finally shown that the Darboux classification of umbilical points can be given in terms of two invariants.

Polynomial C^2 Spline Surfaces Guided by Rational Multisided Patches
Kestutis Karciauskas and Jörg Peters

An algorithm is presented for approximating a rational multi-sided M-patch by a C^2 spline surface. The motivation is that the multi-sided patch can be assumed to have good shape but is in nonstandard representation or of too high a degree. The algorithm generates a finite approximation of the M-patch, by a sequence of patches of bidegree (5,5) capped off by patches of bidegree (11,11) surrounding the extraordinary point.
The philosophy of the approach is
(i) that intricate reparametrizations are permissible if they improve the surface parametrization since they can be precomputed and thereby do not reduce the time efficiency at runtime; and
(ii) that high patch degree is acceptable if the shape is controlled by a guiding patch.

Elementary Theory of Del Pezzo Surfaces
Josef Schicho

Del Pezzo surfaces are certain algebraic surfaces in projective n-space of degree n. They contain an interesting configuration of lines and have a rational parametrization. We give an overview of the classification with an emphasis on algorithmic constructions (e.g. of the parametrization), on explicit computations, and on real algebraic geometry.

On the Shape Effect of a Control Point: Experimenting with NURBS Surfaces
Panagiotis Kaklis and Spyridon Dellas

In this paper we further the theoretical investigation on the shape effect of a single control point, measured in terms of the sign of Gaussian and mean curvatures of the underlying parametric surface. The so far obtained theoretical results are illustrated by experimenting with three typical NURBS surfaces, namely a cylinder, an ellipsoid and a torus.

Universal Rational Parametrizations and Spline Curves on Toric Surfaces
Rimvydas Krasauskas and Margarita Kazakeviciute

Recently a constructive description of all rational parametrizations for toric surfaces was described in terms of the universal rational parametrizations (URP). We give an elementary introduction to this theory from the Geometric Modelling point of view: toric surfaces are defined via homogeneous coordinates; projections, singular cases, and non-canonical real structures are described; the URP theorem is explained. A theory of rational C^1 spline curves with certain interpolation properties on toric surfaces is developed. Applications for smooth blending of natural quadrics are sketched.

The Geometry of the Tangent Developable
Pal Hermunn Johansen

The tangent developable of a curve C in IP^3$ is a singular surface with a cuspidal edge along C and the flex tangents of C. It also contains a multiple curve, typically double, and we express the degree of this curve in terms of the invariants of C. In many cases we can calculate the intersections of C with the multiple curve, and pictures of these cases are provided.

Singularities of Some Projective Rational Surfaces
Ragni Piene

We discuss the singularities of some rational algebraic surfaces in complex projective space. In particular, we give formulas for the degrees of the various types of singular loci, in terms of invariants of the surface.
These enumerative results can be used, on the one hand, to show the existence of singularities in the complex case, and, on the other hand, as an ''upper bound" for the singularities that can occur on a real rational surface.

A Recursive Taylor Method for Algebraic Curves and Surfaces
Huahao Shou, Ralph Martin, Guojin Wang, Adrian Bowyer, and Irina Voiculescu

This paper examines recursive Taylor methods for multivariate polynomial evaluation over an interval, in the context of algebraic curve and surface plotting as a particular application representative of similar problems in CAGD. The modified affine arithmetic method (MAA), previously shown to be one of the best methods for polynomial evaluation over an interval, is used as a benchmark; experimental results show that a second order recursive Taylor method (i) achieves the same or better graphical quality compared to MAA when used for plotting, and (ii) needs fewer arithmetic operations in many cases. Furthermore, this method is simple and very easy to implement.
We also consider which order of Taylor method is best to use, and propose that second order Taylor expansion is generally best. Finally, we briefly examine theoretically the relation between the Taylor method and the MAA method.

Distance Properties of epsilon-Points on Algebraic Curves
Sonia Perez-Diaz, Juana Sendra and J.Rafael Sendra

This paper deals with some mathematical objects that the authors have named epsilon-points, and that appear in the problem of parametrizing approximately algebraic curves. This type of points are used as based points of the linear systems of curves that appear in the parametrization algorithms, and they play an important role in the error analysis. In this paper, we focus on the general study of distance properties of epsilon-points on algebraic plane curves, and we show that if P* is an epsilon-point on a plane curve C of proper degree d, then there exists an exact point P on C such that its distance to P* is at most sqrt(epsilon}) if P* is simple, and O(sqrt(epsilon)^{1/2d}) if P* is of multiplicity r>1. Furthermore, we see how these results particularize to the univariate case giving bounds that fit properly with the classical results in numerical analysis.

Computing the Topology of Three-Dimensional Algebraic Curves
G. Gatellier, A. Labrouzy, B. Mourrain and J.P. Tecourt

In this paper, we present a new method for computing the topology of curves defined as the intersection of two implicit surfaces. The main ingredients are projection tools, based on resultant constructions and 0-dimensional polynomial system solvers. We describe a lifting method for points on the projection of the curve on a plane, even in the case of multiple preimages on the 3D curve. Reducing the problem to the comparison of coordinates of so-called critical points, we propose an approach which combines control and efficiency. An emphasis in this work is put on the experimental validation of this new method. Examples treated with the tools of the library axel (http://www-sop.inria.fr/galaad/logiciels/axel/: Algebraic Software-Components for gEometric modeLing) are showing the potential of such techniques.

Challenges in Surface-Surface Intersections
Vibeke Skytt

Tangential and singular situations are still challenges in a system for surface-surface intersections. This paper presents several real world examples of hard intersection problems, and proposes methods on how to deal with them. In particular, solutions which use the possibility of representing a parametric surface as an algebraic surface through the use of approximate implicitization, are in focus. This allows us to transform an intersection between two parametric surfaces to the problem of finding zeroes of a function of two parameters.

Numerical and Algebraic Properties of Bernstein Basis Resultant Matrices
Joab R. Winkler

Algebraic properties of the power and Bernstein forms of the companion, Sylvester and Bezout resultant matrices are compared and it is shown that some properties of the power basis form of these matrices are not shared by their Bernstein basis equivalents because of the combinatorial factors in the Bernstein basis functions. Several condition numbers of a resultant matrix are considered and it is shown that the most refined measure is NP--hard, and that a simpler, sub--optimal measure is easily computed. The transformation of the companion and B\'ezout resultant matrices between the power and Bernstein bases is considered numerically and algebraically. In particular, it is shown that these transformations are ill--conditioned, even for polynomials of low degree, and that the matrices that occur in these basis transformation equations share some properties.

Approximate Parametrisation of Confidence Sets
Zbynek Sir

In various geometrical applications, the analysis and the visualization of the error of calculated or constructed results is required. This error has very often character of a nontrivial multidimensional probability distribution. Such distributions can be represented in a geometrically interesting way by a system of so called confidence sets. In our paper we present a method for an approximate parametrisation of these sets.
First we describe our motivation, which consists in the study of the errors of so called Passive Observation Systems (POS). Then we give a result about the intersection of quadric surfaces of revolution, which is useful in the investigation of the POS. Finally we give a general method for an approximate parametrisation of the confidence sets via simultaneous Taylor expansion. This method, which can be applied in a wide range of geometrical situations, is demonstrated on a concrete example of the POS.