Modeling arbitrary smooth objects with algebraic surfaces

Representing, manipulating, and reasoning about physical objects is a central area of research in a wide range of applications, including solid modeling, computer-aided design, computer graphics, and robotics. In these applications, complex physical objects are modeled using free-form surfaces, surfaces that are smooth but otherwise arbitrary. Traditionally, free-form surfaces are constructed from parametric patches, which are very successful as far as design and rendering are concerned. However, manipulating and reasoning about physical objects with parametric patches poses fundamental difficulties. For example, the difficulty of evaluating and representing the intersection of parametric patches has hindered the development of solid modeling systems based on parametric patches alone.; This thesis addresses the problem of constructing free-form surfaces using low-degree implicit patches, which facilitate manipulating and reasoning about physical objects. We establish the fact that quadric patches and cubic patches are flexible enough for free-form surface constructions: (i) given an arbitrary polyhedron, we show how to fit a smooth piecewise quadric surface through the vertices of the polyhedron without splitting its facets; (ii) given an arbitrary polyhedron with arbitrarily prescribed tangent planes at its vertices, we present an algorithm that fits a smooth piecewise cubic surface through the vertices of the polyhedron so that the surface is tangent to the prescribed tangent plane at each vertex. In constructing free-form surfaces, we also study three related issues. First, we examine the power and limitations of blending techniques. We show that on the one hand, blending techniques can be used to improve the efficiency of free-form surface constructions; on the other, blending techniques have their fundamental limitations. Second, we provide a complete understanding of the weight functions for quadric surfaces meeting with geometric continuity. Finally, we tackle some shape control issues of implicit patches. In particular, we demonstrate how to achieve the convexity of a quadric or cubic patch by manipulating its control points.