Procedurally representing lofted surfaces

The use of tensor-product B-spline surfaces to construct lofted surfaces is discussed. It is shown that several problems must be overcome if tensor-product B-splines are to represent complex lofted surfaces. A method that seems to satisfy all the necessary requirements for parametrically describing such a surface is given. It uses a novel type of surface implemented in a production design system     

Quaternion rational surfaces: Rational surfaces generated from the quaternion product of two rational space curves

A quaternion rational surface is a surface generated from two rational space curves by quaternion multiplication. The goal of this paper is to demonstrate how to apply syzygies to analyze quaternion rational surfaces. We show that we can easily construct three special syzygies for a quaternion rational surface from a μ-basis for one of the generating rational space curves. The implicit equation of any quaternion rational surface can be computed from these three special syzygies and inversion formulas for the non-singular points on quaternion rational surfaces can be constructed. Quaternion rational ruled surfaces are generated from the quaternion product of a straight line and a rational space curve. We investigate special μ-bases for quaternion rational ruled surfaces and use these special μ-bases to provide implicitization and inversion formulas for quaternion rational ruled surfaces. Finally, we show how to determine if a real rational surface is also a quaternion rational surface.     

Truchet curves and surfaces

Spanning tree contours, a special class of Truchet contour based upon a random spanning tree of a Truchet tiling's underlying graph, are presented. This spanning tree method is extended to three dimensions to define a Truchet surface with properties similar to its two-dimensional counterpart. Both contour and surface are smooth, have known minimum curvature and known maximum distance to interior points, and high ratios of perimeter to area and area to volume, respectively. Expressions for calculating contour length, contour area, surface area and surface volume directly from the spanning tree are given.     

Plus curves and surfaces

The formulations for parametric curves and surfaces that are based on control points are revised to use control lines and control planes instead. Curves defined by control lines are called control-line curves or plus curves, and surfaces defined by control planes are called control-plane surfaces or plus surfaces; the plus implies that in addition to the control points, gradient vectors at the control points are used to design curves and surfaces. The new curve and surface formulations provide more flexibility than traditional formulations in geometric design. Properties of plus curves and surfaces are investigated and an application of plus surfaces in smooth parametric representation of polygon meshes is introduced.     

B样条曲线曲面的节点消去算法研究

在分析了Tiller给出的B样条曲线节点消去算法的基础上,提出了改进算法。改进算法充分地利用了B样条曲线的局部性质,无需考虑节点消去的顺序,一次消去多个节点。实验表明,与Tiller的算法相比较,改进后的算法效率有较大提高。     

Rational Pythagorean-hodograph space curves

A method for constructing rational Pythagorean-hodograph (PH) curves in R³ is proposed, based on prescribing a field of rational unit tangent vectors. This tangent field, together with its first derivative, defines the orientation of the curve osculating planes. Augmenting this orientation information with a rational support function, that specifies the distance of each osculating plane from the origin, then completely defines a one-parameter family of osculating planes, whose envelope is a developable ruled surface. The rational PH space curve is identified as the edge of regression (or cuspidal edge) of this developable surface. Such curves have rational parametric speed, and also rational adapted frames that satisfy the same conditions as polynomial PH curves in order to be rotation-minimizing with respect to the tangent. The key properties of such rational PH space curves are derived and illustrated by examples, and simple algorithms for their practical construction by geometric Hermite interpolation are also proposed.     

Curvature continuous curves and surfaces

The well-known construction of the Bézier points of a cubic spline curve or surface is generalized to curvature continuous curves and surfaces. Special examples of this kind of new splines are Nu-splines and Beta-splines.     

Curvature continuous curves and surfaces

A simple methods is given for constructing the Bézier points of curvature continuous cubic spline curves and surfaces from their B-spline control points. The method is similar to the well-known construction of Bézier points of C² splines from their B-spline control points. The new construction allows the use of all results of the powerful Bernstein-Bézier technique in the realm of geometric splines.

A simple introduction to nu- and beta-splines is also derived, as well as some simple geometric properties of beta-splines.     

A subdivision scheme for Poisson curves and surfaces

The de Casteljau evaluation algorithm applied to a finite sequence of control points defines a Bézier curve. This evaluation procedure also generates a subdivision algorithm and the limit of the subdivision process is this same Bézier curve. Extending the de Casteljau subdivision algorithm to an infinite sequence of control points defines a new family of curves. Here, limits of this stationary non-uniform subdivision process are shown to be equivalent to curves whose control points are the original data points and whose blending functions are given by the Poisson distribution. Thus this approach generalizes standard subdivision techniques from polynomials to arbitrary analytic functions. Extensions of this new subdivision scheme from curves to tensor product surfaces are also discussed.     

Semi-automatic system for defining free-form curves and surfaces

Among curves and surfaces defined by parametric polynomials, the cases dealt with here are those which only have to comply with the requirement to run through a certain number of points previously located in space. The process can be totally automatic, but the results are liable to be altered by arbitrary decisions.     

Rasterizing algebraic curves and surfaces

A new, recursive, space-subdivision algorithm for rasterizing algebraic curves and surfaces gets its accuracy from a newly devised, computationally efficient, and asymptotically correct test. The approach followed is essentially the interval arithmetic method for rendering implicit curves. The author's contribution is a particularly efficient way to construct inclusion functions for polynomials. An ideal algorithm is given for rendering an algebraic curve Z(f)={(x,y):f(x,y)=0} in a square box of side n. The algorithm scans the square and paints only those pixels cut by the curve. This algorithm is ideal, because every correct algorithm should paint exactly the same pixels, but it is impractical. It requires n² test evaluations, one for each pixel in the square. However, since in general it will be rendering a curve on a planar region, the number of pixels it is expected to paint is only O(n). We need a more efficient algorithm. There are two issues to examine. The first is how to reduce the computational complexity by recursive subdivision. The second is how to test whether the curve Z(f) cuts a square     

Knot removal for parametric B-spline curves and surfaces

This paper is the third in a sequence of papers in which a knot removal strategy for splines, based on certain discrete norms, is developed. In the first paper, approximation methods defined as best approximations in these norms were discussed, while in the second paper a knot removal strategy for spline functions was developed. In this paper the knot removal strategy is extended to parametric spline curves and tensor product surfaces. The method has been implemented and thoroughly tested on a computer. We illustrate with several examples and applications.     

Alternative representation for parametric cubic curves and surfaces

A representation for parametric cubic curves and surfaces is presented which incorporates the polygonal approach popularized by the Bézier and B-spline schemes. Since the curves more closely mimic the polygon than their counterparts employing the Bézier or B-spline schemes, the method is potentially useful for creating and manipulating geometric models. In connection with the logical extension of the approach from curves to surfaces, a discussion of the relationship between continuity and redundant data storage is included.     

Hermite approximation for free-form deformation of curves and surfaces

Free-Form Deformation Techniques (FFD) are commonly used to generate animations, where a polygonal approximation of the final object suffices for visualization purposes. However, for some CAD/CAM applications, we need an explicit expression of the object, rather than a collection of sampled points. If both object and deformation are polynomial, their composition yields a result that is also polynomial, albeit very high degree, something undesirable in real applications. To solve this problem, we transform each curve or surface composing the object, usually expressed in the Bernstein basis, to a modified Newton form. In this representation, the two-point analogue of Taylor expansions, the composition admits a simple expression in terms of discrete convolutions, and degree reduction corresponding to Hermite approximation is trivial by dropping high-degree coefficients. Furthermore, degree-reduction can be incorporated into the composition. Finally, the deformed curve or surface is converted back to the Bernstein form. This method extends to general non-polynomial deformation, such as bending and twisting, by computing a polynomial approximant of the deformation.     

Implicit curves and surfaces in CAGD

The role of implicit curves and surfaces in computer-aided geometric design (CAGD) are described. The ways in which the study of implicit algebraic curves and surfaces draws on algebraic geometry are reviewed. The implicitization of parametric curves and surfaces, parameterization of implicits, and techniques used to circumvent conversions between implicit and parametric representations are discussed     

Parabolic curves of evolving surfaces

In this article we show how certain geometric structures which are also associated with a smooth surface evolve as the shape of the surface changes in a 1-parameter family. We concentrate on the parabolic set and its image under the Gauss map, but the same techniques also classify the changes in the dual of the surface. All these have significance for computer vision, for example through their connection with specularities and apparent contours. With the aid of our complete classification, which includes all the phenomena associated with multi-contact tangent planes as well as those associated with parabolic sets, we re-examine examples given by J. Koenderink in his book (1990) under the title of Morphological Scripts.We also explain some of the connections between parabolic sets and ridges of a surface, where principal curvatures achieve turning values along lines of curvature.The point of view taken is the analysis of the contact between surfaces and their tangent planes. A systematic investigation of this yields the results using singularity theory. The mathematical details are suppressed here and appear in Bruce et al. (1993).The third author was supported by the Esprit grant VIVA while this paper was in preparation.     

Iterative point matching for registration of free-form curves and surfaces

A heuristic method has been developed for registering two sets of 3-D curves obtained by using an edge-based stereo system, or two dense 3-D maps obtained by using a correlation-based stereo system. Geometric matching in general is a difficult unsolved problem in computer vision. Fortunately, in many practical applications, some a priori knowledge exists which considerably simplifies the problem. In visual navigation, for example, the motion between successive positions is usually approximately known. From this initial estimate, our algorithm computes observer motion with very good precision, which is required for environment modeling (e.g., building a Digital Elevation Map). Objects are represented by a set of 3-D points, which are considered as the samples of a surface. No constraint is imposed on the form of the objects. The proposed algorithm is based on iteratively matching points in one set to the closest points in the other. A statistical method based on the distance distribution is used to deal with outliers, occlusion, appearance and disappearance, which allows us to do subset-subset matching. A least-squares technique is used to estimate 3-D motion from the point correspondences, which reduces the average distance between points in the two sets. Both synthetic and real data have been used to test the algorithm, and the results show that it is efficient and robust, and yields an accurate motion estimate.     

Recursive algorithms for the representation of parametric curves and surfaces

Recursive algorithms for the representation of parametric curves and surfaces are presented which are based upon a geometric property of the de Casteljau algorithm. The algorithms work with triangular and pyramidal arrays that provide an easy handling of the curve and the surface ‘in a large’ design.