This paper develops new refinement rules for non-uniform Catmull-Clark surfaces that produce G 1 extraordinary points whose blending functions have a single local maximum. The method consists of designing an "eigen polyhedron" in R 2 for each extraordinary point, and formulating refinement rules for which refinement of the eigen polyhedron reduces to a scale and translation. These refinement rules, when applied to a non-uniform Catmull-Clark control mesh in R 3 , yield a G 1 extraordinary point.

We present a novel method of offline whole-word handwriting recognition. We use automatic image morphing to compute 2-D geometric warps that align the strokes of each word image with the strokes of word images of training examples. Once the strokes of a given word are aligned to a training example, we use distance maps to compare how similar the two words are. Like 1-D Dynamic Programming (DP) methods, our warp-based method is robust to limited variation in word length and letter spacing. However, due to its 2-D nature, our method is also more robust than 1-D DP methods in handling variations caused by additional inconsistencies in character shape and stroke placement. Although we use DP for coarse alignment, the novel contribution of this paper is not 2-D DP, but morphing to automatically discover an actual 2-D mesh-based warp, followed by the use of distance maps to compute similarity between words. Early results are encouraging. On two datasets (1,000 training and 1,000 test words each), we get 88.77% and 89.33% recognition accuracy for in-vocabulary words. These are increases of 7.89% and 17.16% above the results of a 1-D DP approach.

This paper addresses the long-standing problem of the unavoidable gaps that arise when expressing the intersection of two NURBS surfaces using conventional trimmed-NURBS representation. The solution converts each trimmed NURBS into an untrimmed T-Spline, and then merges the untrimmed T-Splines into a single, watertight model. The solution enables watertight fillets of NURBS models, as well as arbitrary feature curves that do not have to follow iso-parameter curves. The resulting T-Spline representation can be exported without error as a collection of NURBS surfaces.

A typical NURBS surface model has a large percentage of superfluous control points that significantly interfere with the design process. This paper presents an algorithm for eliminating such superfluous control points, producing a T-spline. The algorithm can remove substantially more control points than competing methods such as B-spline wavelet decomposition. The paper also presents a new T-spline local refinement algorithm and answers two fundamental open questions on T-spline theory.

This paper presents a generalization of non-uniform B-spline surfaces called T-splines. T-spline control grids permit T-junctions, so lines of control points need not traverse the entire control grid. T-splines support many valuable operations within a consistent framework, such as local refinement, and the merging of several B-spline surfaces that have different knot vectors into a single gap-free model. The paper focuses on T-splines of degree three, which are C 2 (in the absence of multiple knots). T-NURCCs (Non-Uniform Rational Catmull-Clark Surfaces with T-junctions) are a superset of both T-splines and Catmull-Clark surfaces. Thus, a modeling program for T-NURCCs can handle any NURBS or Catmull-Clark model as special cases. T-NURCCs enable true local refinement of a Catmull-Clark-type control grid: individual control points can be inserted only where they are needed to provide additional control, or to create a smoother tessellation, and such insertions do not alter the limit surface. T-NURCCs use stationary refinement rules and are C 2 except at extraordinary points and features.

An inversion equation takes the Cartesian coordinates of a point on a parametric curve or surface and returns the parameter value(s) of that point. A 2D curve inversion equation has the form t = f (x, y)/g(x, y). This paper shows that practical insight into inversion can be obtained by studying the geometry of the implicit curves f (x, y) = 0 and g(x, y) = 0. For example, the relationship between the singular locus of the parametric curve and the lowest possible degree of an inversion equation can be understood in this way. Also, insight is given into what parameter value will be returned if an inversion equation is fed the Cartesian coordinates of a point that does not lie on the curve. The standard method of devising curve and surface inversion equations is a by-product of the implicitization process. This paper presents a new method for finding inversion equations, which allows us to create new inversion equations that have attractive properties. For example, we can create an inversion equation that, to first order approximation, will return the parameter value of the nearest point on the curve if given a point that does not lie precisely on a parametric curve.

In this paper we put forward and study the problem of bounding an interval rational Bezier curve with an interval polynomial Bezier curve. We propose three different methods-hybrid method, perturbation method and linear programming method to solve this problem. Examples are illustrated to compare the three different methods. The empirical results show that the perturbation method and the linear programming method produce much tighter bounds than the hybrid method, though they are computationally several times more expensive.

This paper presents a method for determining a priori a constant parameter interval for tessellating a rational curve or surface such that the deviation of the curve or surface from its piecewise linear approximation is within a specified tolerance. The parameter interval is estimated based on information about second-order derivatives in the homogeneous coordinates, instead of using affine coordinates directly. This new step size can be found with roughly the same amount of computation as the step size in Cheng [1992], though it can be proven to always be larger than Cheng's step size. In fact, numerical experiments show the new step is typically orders of magnitude larger than the step size in Cheng [1992]. Furthermore, for rational cubic and quartic curves, the new step size is generally twice as large as the step size found by computing bounds on the Bernstein polynomial coefficients of the second derivatives function.

Doo-Sabin and Catmull-Clark subdivision surfaces are based on the notion of repeated knot insertion of uniform tensor product B-spline surfaces. This paper develops rules for non-uniform Doo-Sabin and Catmull-Clark surfaces that generalize non-uniform tensor product B-spline surfaces to arbitrary topologies. This added flexibility allows, among other things, the natural introduction of features such as cusps, creases, and darts, while elsewhere maintaining the same order of continuity as their uniform counterparts.

This paper presents a radically new approach to the century old problem of computing the implicit equation of a parametric surface. For surfaces without base points, the new method expresses the implicit equation in a determinant which is one fourth the size of the conventional expression based on Dixon's resultant. If base points do exist, previous implicitization methods either fail or become much more complicated, while the new method actually simplifies.

This paper presents an algorithm for determiningthe paths along which corresponding vertices travel in a 2-D shape blending.Rather than considering the vertex paths explicitly, the algorithm defines the intermediate shapes by interpolating the intrinsic definitions of the initial and final shapes.The algorithm produces shape blends which generally are more satisfactory than those produced using linear or cubic curve paths.Particularly, the algorithm can avoid the shrinkage that normally occurs when rotating rigid bodies are linearly blended, and avoids kinks in the blend when there were none in the key polygons.

This paper presents a new algorithm for smoothly blending between two 2#D polygonal shapes. The algorithm is based on a physical model wherein one of the shapes is considered to be constructed of wire, and a solution is found whereby the #rst shape can be bent and#or stretched into the second shape with a minimum amountofwork. The resulting solution tends to associate regions on the two shapes which look alike. If the two polygons have m and n vertices respectively, the algorithm is O#mn#. The algorithm avoids local shape inversions in whichintermediate polygons self-intersect, if such a solution exists. Categories and Subject Descriptors: I.3.3 #Computer Graphics #: Picture#Image Generation; I.3.5 #Computer Graphics#: Computational Geometry and Object Modeling. General Terms: Algorithms Additional Key Words and Phrases: Computer graphics, shape blending, animation, physically based algorithms. 1 Introduction The topic of this paper is illustrated in Figures 1#3. Given two polygonal...

This paper presents a new algorithm for computing the points at which a ray intersects a rational Bezier surface patch, and also an algorithm for determining if an intersection point lies within a region trimmed by piecewise Bezier curves. Both algorithms are based on a recent innovation known as Bezier clipping, described herein. The intersection algorithm is faster than previous methods for which published performance data allow reliable comparison. It robustly finds all intersections without requiring special preprocessing.

A robust algorithm is presented for scan line display of algebraic surfaces of arbitrary degree and topology. The algorithm correctly displays singularities of any complexity, even those missed by ray tracing or polygonization, and (for surfaces of degree less than eight) offers a significant speed improvement over ray tracing. Antialiasing can generally be accomplished very quickly. In addition to its typical function of shaded raster display, the algorithm is particularly adept at quickly plotting silhouette and intersection curves. A practical use for the algorithm is to display boolean combinations of algebraic half spaces, including blend surfaces.A new polynomial basis is introduced, referred to as the Bernstein pyramid polynomial basis, which enhances numerical stability and which simplifies several computations such as scan planesurface intersection and silhouette detection.

Steiner patches are triangular surface patches for which the Cartesian coordinates of points on the patch are defined parametrically by quadratic polynomial functions of two variables. It has recently been shown that it is possible to express a Steiner patch in an implicit equation which is a degree four polynomial in x,y,z. Furthermore, the parameters of a point known to be on the surface can be computed as rational polynomial functions of x,y,z. These findings lead to a straightforward algorithm for ray tracing Steiner patches in which the ray intersection equation is a degree four polynomial in the parameter of the ray. The algorithm presented represents a major simplification over existing techniques for ray tracing free-form surface patches.

A simple algorithm is presented for processing complex contour arrangements to produce polygonal element mosaics which are suitable for line drawing and continuous tone display. The program proceeds by mapping adjacent contours onto the same unit square and, subject to ordering limitations, connecting nodes of one contour to their nearest neighbors in the other contour. While the mapping procedure provides a basis for branching decisions, highly ambiguous situations are resolved by user interaction. The program was designed to interface a contour definition of the components of a human brain. These brain data are a most complex definition and, as such, serve to illustrate both the capabilities and limitations of the procedures.