Approximating digital 3D shapes by rational Gaussian surfaces

A method for approximating spherical topology digital shapes by rational Gaussian (RaG) surfaces is presented. Points in a shape are parametrized by approximating the shape with a triangular mesh, determining parameter coordinates at mesh vertices, and finding parameter coordinates at shape points from interpolation of parameter coordinates at mesh vertices. Knowing the locations and parameter coordinates of the shape points, the control points of a RaG surface are determined to approximate the shape with a required accuracy. The process starts from a small set of control points and gradually increases the control points until the error between the surface and the digital shape reduces to a required tolerance. Both triangulation and surface approximation proceed from coarse to fine. Therefore, the method is particularly suitable for multiresolution creation and transmission of digital shapes over the Internet. Application of the proposed method in editing of 3D shapes is demonstrated.     

Offsets of curves on rational B-spline surfaces

The construction of offset curves is an important problem encountered often in design processes and in interrogation of geometric models. In this paper the problem of construction of offsets of curves lying on the same parametric surface is addressed. A novel algorithm is introduced, whose main feature is the use of geodesic paths to determine points of the offset. The offset is then approximated in the underlying surface parameter space by B-splines interpolating data points obtained by traveling a known distance along the geodesics departing from corresponding points of the progenitor in a direction perpendicular to the latter. A comprehensive error checking scheme has been devised allowing adaptive improvement of the approximation of the offset. The applicability of the algorithm is demonstrated by number of numerical examples.     

Automatic parameterization of rational curves and surfaces III: Algebraic plane curves

We present algorithms to compute the genus and rational parametric equations, for implicitly defined irreducible plane algebraic curves of arbitrary degree. Rational parameterizations exist for all irreducible algebraic curves of genus 0. The genus is computed by a complete analysis of the singularities of plane algebraic curves, using affine quadratic transformations. The rational parameterization techniques, essentially, reduce to solving symbolically systems of homogeneous linear equations and the computation of polynomial resultants.     

Perception of 3-D surfaces from 2-D contours

Inference of 3-D shape from 2-D contours in a single image is an important problem in machine vision. The authors survey classes of techniques proposed in the past and provide a critical analysis. They show that two kinds of symmetries in figures, which are known as parallel and skew symmetries, give significant information about surface shape for a variety of objects. They derive the constraints imposed by these symmetries and show how to use them to infer 3-D shape. They also discuss the zero Gaussian curvature (ZGC) surfaces in depth and show results on the recovery of surface orientation for various ZGC surfaces     

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.     

Retrieving articulated 3-D models using medial surfaces

We consider the use of medial surfaces to represent symmetries of 3-D objects. This allows for a qualitative abstraction based on a directed acyclic graph of components and also a degree of invariance to a variety of transformations including the articulation of parts. We demonstrate the use of this representation for 3-D object model retrieval. Our formulation uses the geometric information associated with each node along with an eigenvalue labeling of the adjacency matrix of the subgraph rooted at that node. We present comparative retrieval results against the techniques of shape distributions (Osada et al.) and harmonic spheres (Kazhdan et al.) on 425 models from the McGill Shape Benchmark, representing 19 object classes. For objects with articulating parts, the precision vs recall curves using our method are consistently above and to the right of those of the other two techniques, demonstrating superior retrieval performance. For objects that are rigid, our method gives results that compare favorably with these methods. A preliminary version of this article was published in EMMCVPR 2005. In this extended version we have included results on the significantly larger McGill Shape Benchmark, making a stronger case for the advantages of our method for models with articulating parts. We have also included expanded introduction, medial surface computation, matching, indexing, experimental results, and discussion sections, along with several new figures.     

Interpolation on quadric surfaces with rational quadratic spline curves

Given a sequence of points {X_i}_i=1ⁿ on a regular quadric S: X^TAX = 0 ⊂ E^d, d ⩾ 3, we study the problem of constructing a G¹ rational quadratic spline curve lying on S that interpolates {X_i}_i=1ⁿ. It is shown that a necessary condition for the existence of a nontrivial interpolant is (X₁^TAX₂)(X_i^TAX_i+1) > 0, i = 1,2…,n − 1. Also considered is a Hermite interpolation problem on the quadric S: a biarc consisting of two conic arcs on S joined with G¹ continuity is used to interpolate two points on S and two associated tangent directions, a method similar to the biarc scheme in the plane (Bolton, 1975) or space (Sharrock, 1987). A necessary and sufficient condition is obtained on the existence of a biarc whose two arcs are not major elliptic arcs. In addition, it is shown that this condition is always fulfilled on a sphere for generic interpolation data.     

3-D shape recovery using distributed aspect matching

An approach to the recovery of 3-D volumetric primitives from a single 2-D image is presented. The approach first takes a set of 3-D volumetric modeling primitives and generates a hierarchical aspect representation based on the projected surfaces of the primitives; conditional probabilities capture the ambiguity of mappings between levels of the hierarchy. From a region segmentation of the input image, the authors present a formulation of the recovery problem based on the grouping of the regions into aspects. No domain-independent heuristics are used; only the probabilities inherent in the aspect hierarchy are exploited. Once the aspects are recovered, the aspect hierarchy is used to infer a set of volumetric primitives and their connectivity. As a front end to an object recognition system, the approach provides the indexing power of complex 3-D object-centered primitives while exploiting the convenience of 2-D viewer-centered aspect matching; aspects are used to represent a finite vocabulary of 3-D parts from which objects can be constructed     

Canal surfaces with rational contour curves and blends bypassing the obstacles

In this paper, we will present an algebraic condition, see (20), which guarantees that a canal surface, given by its rational medial axis transform (MAT), possesses rational generalized contours (i.e., contour curves with respect to a given viewpoint). The remaining computational problem of this approach is how to find the right viewpoint. The canal surfaces fulfilling this distinguished property are suitable for being taken as modeling primitives when some rational approximations of canal surfaces are required. Mainly, we will focus on the low-degree cases such as quadratic and cubic MATs that are especially useful for applications. To document a practical usefulness of the presented approach, we designed and implemented two simple algorithms for computing rational offset blends between two canal surfaces based on the contour method which do not need any further advanced formalism (as e.g. interpolations with MPH curves). A main advantage of the designed blending technique is its simplicity and also an adaptivity to choose a suitable blend satisfying certain constrains (avoiding obstacles, bypassing other objects, etc.). Compared to other similar methods, our approach requires only one SOS decomposition for the whole family of rational canal surfaces sharing the same silhouette, which significantly simplifies the computational complexity.     

Automatic parameretization of rational curves and surfaces 1: conics and conicoids

Given the implicit equation for degree two curves (conics) and degree two surfaces (conicoids), algorithms are described here, which obtain their corresponding rational parametric equations (a polynomial divided by another). These rational parameterizations are considered over the fields of rationals, reals and complex numbers. In doing so, solutions are given to important subproblems of finding rational and real points on the given conic curve or conicoid surface. Further polynomial parameterizations are obtained whenever they exist for the conics or conicoids. These algorithms have been implemented on a VAX-780 using VAXIMA.     

Automatic parametrization of rational curves and surfaces II: cubics and cubicoids

Algorithms that can obtain rational and special parametric equations for degree three algebraic curves (cubics) and degree three algebraic surfaces (cubicoids), given their implicit equations are described. These algorithms have been implemented on a VAX8600 using VAXIMA.     

Three-dimensional face recognition using shapes of facial curves

We study shapes of facial surfaces for the purpose of face recognition. The main idea is to 1) represent surfaces by unions of level curves, called facial curves, of the depth function and 2) compare shapes of surfaces implicitly using shapes of facial curves. The latter is performed using a differential geometric approach that computes geodesic lengths between closed curves on a shape manifold. These ideas are demonstrated using a nearest-neighbor classifier on two 3D face databases: Florida State University and Notre Dame, highlighting a good recognition performance     

Reduction of 2-D rational functions

This paper presents a method of reducing a two-dimensional (2-D) rational function to an irreducible one. It is achieved by searching the first linearly dependent row, in order from top to bottom, of a generalized resultant. Some properties of the resultant are discussed. The result can be used to compute the greatest common divisor (g.c.d.) of two 2-D polynomials by carrying out one additional division. This procedure does not require the computation of primitive polynomials, which is required by all existing methods, and thus provides a potentially attractive method of computing g.c.d. The method can be readily extended to three-or higher-dimensional cases.     

Matching 3-D anatomical surfaces with non-rigid deformations using octree-splines

This paper presents a new method for determining the minimal non-rigid deformation between two 3-D surfaces, such as those which describe anatomical structures in 3-D medical images. Although we match surfaces, we represent the deformation as a volumetric transformation. Our method performs a least squares minimization of the distance between the two surfaces of interest. To quickly and accurately compute distances between points on the two surfaces, we use a precomputed distance map represented using an octree spline whose resolution increases near the surface. To quickly and robustly compute the deformation, we use a second octree spline to model the deformation function. The coarsest level of the deformation encodes the global (e.g., affine) transformation between the two surfaces, while finer levels encode smooth local displacements which bring the two surfaces into closer registration. We present experimental results on both synthetic and real 3-D surfaces.     

A method for registration of 3-D shapes

The authors describe a general-purpose, representation-independent method for the accurate and computationally efficient registration of 3-D shapes including free-form curves and surfaces. The method handles the full six degrees of freedom and is based on the iterative closest point (ICP) algorithm, which requires only a procedure to find the closest point on a geometric entity to a given point. The ICP algorithm always converges monotonically to the nearest local minimum of a mean-square distance metric, and the rate of convergence is rapid during the first few iterations. Therefore, given an adequate set of initial rotations and translations for a particular class of objects with a certain level of `shape complexity', one can globally minimize the mean-square distance metric over all six degrees of freedom by testing each initial registration. One important application of this method is to register sensed data from unfixtured rigid objects with an ideal geometric model, prior to shape inspection. Experimental results show the capabilities of the registration algorithm on point sets, curves, and surfaces     

Bisector curves of planar rational curves

This paper presents a simple and robust method for computing the bisector of two planar rational curves. We represent the correspondence between the foot points on two planar rational curves C₁(t) and C₂(r) as an implicit curve (t,r)=0, where (t,r) is a bivariate polynomial B-spline function. Given two rational curves of degree m in the xy-plane, the curve (t,r)=0 has degree 4m−2, which is considerably lower than that of the corresponding bisector curve in the xy-plane.     

Self-assembly of 3-D structures using 2-D folding tiles

Natural Computing - Self-assembly is a process which is ubiquitous in natural, especially biological systems. It occurs when groups of relatively simple components spontaneously combine to form...