Geometric Computation

The following sections are included:

• PREFACE

• CONTENTS

In this chapter, we show how to adapt algebraic techniques to deal with some problems, such as implicitization or parameterization, in computer aided geometric design that involve floating-point real numbers. In addition, applications to the offsetting and blending problems are also considered.

Constructing algebraic blending surfaces is an important problem in geometric modeling. In this chapter, we review some methods for this problem and summarize the main results on the construction of piecewise algebraic surfaces investigated recently by members of our group.

This chapter is organized into seven sections. We begin with a brief introduction to the problem of surface blending, followed by some notations and preliminary knowledge from computational algebraic geometry which will be used in later sections. We then discuss four methods — direct method, Gröbner basis method, Wu's method, and syzygy module method — for constructing piecewise algebraic blending surfaces. We also provide many examples to illustrate these methods with comparison. The chapter is concluded with a few remarks.

In this chapter we survey symbolic algorithms for dealing with rational algebraic curves and surfaces as well as some applications. More precisely we describe algorithms for deciding the rationality of algebraic curves and surfaces, and we show how to parametrize them. In addition, we study how to parametrize and repararnetrize curves under different criteria of optimality such as the degree, the field of parametrization, its polynomiality and normality character. Parametrization and reparametrization algorithms for the case of real curves are also considered, and so is the inversion problem for proper parametrizations. Finally, we briefly describe some applications of algebraic curves and surfaces such as plotting, offsetting and blending.

This chapter is intended to present an overview of all major available Symbolic Computation methods for exact implicitization of algebraic curves and surfaces. The methods are discussed in a rigorous theoretical framework and the associated algorithms are illustrated with fully worked out examples in the Computer Algebra system Maple. Implicitization algorithms constitute an essential tool in the arsenal of available methods employed to tackle Geometric Computation problems, for instance, in Computer Aided Design and Computer Aided Geometric Design. An extensive bibliography on the subject of implicitization is included.

Given a geometric object denned by rational parametric equations, we show how to compute a disjunction of implicit equations and inequations that define exactly the same object by means of regular systems. The same technique is applied to the computation of quasi-offsets to algebraic curves and surfaces. Regular systems possess the projection property, are relatively easy to compute, and often have a compact form. Several examples are given to illustrate our approach based on the decomposition of polynomial systems into regular systems. A heuristic method is presented to simplify the output disjunction of polynomial equations and inequations.

This chapter is devoted to showing how to solve the intersection problem for two algebraic surfaces presented implicitly by using algebraic techniques for manipulating polynomial systems of equations, the numerical solution of first order systems of differential equations and the properties of scalar and gradient vector fields.

Based on the viewpoint of topological and geometrical operators, we propose a novel class of subdivision schemes named semi-stationary subdivision for freeform surface design. Compared with traditional stationary methods, their main advantage lies in the use of a parameter changing rule during the subdivision iterations. This facilitates shape control by the user. Local revolving surfaces, directional and bumpy effects can be generated. For practical and theoretical importance, we strictly analyze the convergence properties of cubic subdivision schemes by employing Discrete Fourier Transform and matrix computing techniques to deal with the dynamic subdivision matrix. Additionally, we generalize its basic algorithms by selecting multi-kernel functions. The resulting surfaces are similar to Catmull-Clark subdivision surfaces and have G² continuity except at irregular points. The simplicity in mathematical theory and practical implementation further enhance the usefulness of these schemes in computer aided design and computer graphics.

In CAGD, many curves and surfaces, which we want to design, are the solutions of some partial differential equations. The corresponding discrete equations often appear as Hermite-Birkhoff interpolations. Such equations are very difficult to solve in the function space of piecewise polynomials on mesh, since the solutions of the partial differential equations are very smooth even in C^∞. This chapter discusses a meshless method for numerical solution of PDE by using the Hermite-Birkhoff interpolation with radial basis, which is generalized from the thin plate spline. This method is a direct discretion of collocation type for ordinary and partial differential equations, with possibility of generalization to integral equations or even equations with time delays. If we adopt the results in the discussion of radial basis and the Hermite-Birkhoff interpolation, the solvability of the discrete system of equations can be proven on very weak assumptions. The order of the approximation of the scheme depends on the smoothness of the solution and the order of the differential equation.

Clifford algebra is an important invariant algebra in geometric computing. In this chapter, we first introduce the background and the current status of Clifford algebra, then use five examples to illustrate how Clifford algebras are applied in geometric computation, and provide detailed explanations of the computation techniques. For a systematic study of the general techniques, we encourage further reading into the literature, for which a list is also provided.

Including three aspects: problem solving, theorem proving and theorem discovering, automated deduction in real geometry depends essentially upon semi-algebraic system solving. A semi-algebraic system is a system consisting of polynomial equations, polynomial inequations and polynomial inequalities, where all the polynomials are of integer coefficients. We give three practical algorithms respectively for the three kinds of problems mentioned above. A package based on these algorithms for solving semi-algebraic systems at the three levels has been implemented as Maple programs. The performance of the package on many famous examples is reported.

This chapter introduces the concept of strong regular sets and presents some of their properties. Three algorithms for zero decomposition of polynomial systems are fully described. Based on two of them, we propose two alternative methods for automated derivation of unknown relations and automated determination of geometric loci. Some well-known examples are also discussed.

The concept of guaranteed accuracy computation is a natural one: the user could specify any á priori relative or absolute precision bound on the numerical values which are to be computed in an algorithm. It is a generalization of guaranteed sign computation, a concept originally proposed to solve the ubiquitous problem of non-robustness in geometric algorithms. In this chapter, we investigate some basic properties of such computational mode. We formulate a theory of real computation and approximation to capture guaranteed accuracy computation. We also introduce an algebraic and a numerical model of computation based on Schönhage's pointer machines.

The Dixon formulation for three bivariate polynomials produces explicit pure bracket sparse resultant expressions for several classes of unmixed monomial supports. When the monomial support is a complete rectangle or a corner-cut rectangle, the sparse resultant is the Dixon determinant; when the monomial support is a complete rectangle with corner edge cutting or a corner-cut rectangle with corner point pasting, the sparse resultant is the Dixon determinant divided by a priori known brackets. But the Dixon determinant vanishes with isosceles triangular corner cutting when the isosceles triangle has six or more points. However, if the isosceles triangle consists of exactly six points, we are able to identify all the maximal minors with corresponding brackets such that each maximal minor divided by the product of these corresponding brackets is the sparse resultant. Our approach is interesting because it extends the applicability of the well-known Dixon method and it produces a much smaller determinant than that of other determinantal methods. All proofs are constructive. One of the proofs is done mechanically by a Maple program with the “assume” facility which allows properties of and relationships among symbols to be specified.

Compared with other biometric security technologies, automatic face recognition provides a more natural and easier approach for human identification; however, it also presents more technical challenges. There are always variations existing in face photos of the same subject person, which are caused by different lighting conditions, different poses and expressions of the subject person, different orientations and positions of cameras, and other random factors. A human face can be viewed as a Markov chain system first from top to bottom vertically and then from left-hand to right-hand side within each vertical region, and the morphing face photos are observation sequences of the states of this system. Based on the above principle, a hierarchical or embedded Hidden Markov Model (E-HMM) corresponding to a human face can be built through training procedure and act as the basis in face recognition processing. Two new approaches combined HMM with Artificial Neural Network (ANN) are proposed in this chapter. ANNs can be embedded in an HMM based system as probability density estimators, and/or as a post-processing classifier; both will augment E-HMM system recognition performance. Experimental results show that these hybrid HMM/ANN approaches achieved high recognition rate (>90%) and are also robust.

The following sections are included:

• INDEX

• LIST OF AUTHORS