Rotational and helical surface approximation for reverse engineering

Given a surface in 3-space or scattered points from a surface, we investigate the problem of deciding whether the data may be fitted well by a cylindrical surface, a surface of revolution or a helical surface. Furthermore, we show how to compute an approximating surface and put special emphasis to basic shapes used in computer aided design. The algorithms apply methods of line geometry to the set of surface normals in combination with techniques of numerical approximation. The presented results possess applications in reverse engineering and computer aided manufacturing.     

Hybrid curve fitting

We consider a parameterized family of closed planar curves and introduce an evolution process for identifying a member of the family that approximates a given unorganized point cloud {p _i } _{i =1,..., N} . The evolution is driven by the normal velocities at the closest (or foot) points (f _i ) to the data points, which are found by approximating the corresponding difference vectors p _i -f _i in the least-squares sense. In the particular case of parametrically defined curves, this process is shown to be equivalent to normal (or tangent) distance minimization, see [3], [19]. Moreover, it can be generalized to very general representations of curves. These include hybrid curves, which are a collection of parametrically and implicitly defined curve segments, pieced together with certain degrees of geometric continuity.     

Evolutions of Polygons in the Study of Subdivision Surfaces

We employ the theory of evolving n-gons in the study of subdivision surfaces. We show that for subdivision schemes with small stencils the eigenanalysis of an evolving polygon, corresponding either to a face or to the 1-ring neighborhood of a vertex, complements in a geometrically intuitive way the eigenanalysis of the subdivision matrix. In the applications we study the types of singularities that may appear on a subdivision surface, and we find properties of the subdivision surface that depend on the initial control polyhedron only.     

Multiresolution morphing for planar curves

We present a multiresolution morphing algorithm using ``as-rigid-as-possible' shape interpolation combined with an angle-length based multiresolution decomposition of simple 2D piecewise curves. This novel multiresolution representation is defined intrinsically and has the advantage that the details' orientation follows any deformation naturally. The multiresolution morphing algorithm consists of transforming separately the coarse and detail coefficients of the multiresolution decomposition. Thus all LoD (level of detail) applications like LoD display, compression, LoD editing etc. can be applied directly to all morphs without any extra computation. Furthermore, the algorithm can robustly morph between very large size polygons with many local details as illustrated in numerous figures. The intermediate morphs behave natural and least-distorting due to the particular intrinsic multiresolution representation.     

The Bézier Tangential Surface System: a Robust Dual Representation of Tangent Space

This paper develops a robust dual representation for the tangent space of a rational surface. This dual representation of tangent space is a very useful tool for visibility analysis. Visibility constructs that are directly derivable from the dual representation of this paper include silhouettes, bitangent developables and kernels. It is known that the tangent space of a surface can be represented by a surface in dual space, which we call a tangential surface. Unfortunately, a tangential surface is usually infinite. Therefore, for robust computation, the points at infinity must be clipped from a tangential surface. This clipping requires two complementary refinements, the first to allow clipping and the second to do the clipping. First, three cooperating tangential surfaces are used to model the entire tangent space robustly, each defined within a box. Second, the points at infinity on each tangential surface are clipped away while preserving everything that lies within the box. This clipping only involves subdivision along isoparametric curves, a considerably simpler process than exact trimming to the box. The isoparametric values for this clipping are computed as local extrema from an analysis using Sederbergs piecewise algebraic curves. A construction of the tangential surface of a parametric surface is outlined, and it is shown how the tangential surface of a Bézier surface can be expressed as a rational Bézier surface.     

The Convex Hull of Freeform Surfaces

We present an algorithm for computing the convex hull of freeform rational surfaces. The convex hull problem is reformulated as one of finding the zero-sets of polynomial equations; using these zero-sets we characterize developable surface patches and planar patches that belong to the boundary of the convex hull.     

Efficient Collision Detection for Moving Ellipsoids Using Separating Planes

We present a simple, accurate and efficient algorithm for collision detection among moving ellipsoids. Its efficiency is attributed to two results: (i) a simple algebraic test for the separation of two ellipsoids, and (ii) an efficient method for constructing a separating plane between two disjoint ellipsoids. Inter-frame coherence is exploited by using the separating plane to reduce collision detection to simpler subproblems of testing for collision between the plane and each of the ellipsoids. Compared with previous algorithms (such as the GJK method) which employ polygonal approximation of ellipsoids, our algorithm demonstrates comparable computing speed and much higher accuracy.     

Implicitization and parametrization of quadratic and cubic surfaces by μ-bases

Parametric and implicit forms are two common representations of geometric objects. It is important to be able to pass back and forth between the two representations, two processes called parameterization and implicitization, respectively. In this paper, we study the parametrization and implicitization of quadrics (quadratic parametric surfaces with two base points) and cubic surfaces (cubic parametric surfaces with six base points) with the help of μ-bases – a newly developed tool which connects the parametric form and the implicit form of a surface. For both cases, we show that the minimal μ-bases are all linear in the parametric variables, and based on this observation, very efficient algorithms are devised to compute the minimal μ-bases either from the parametric equation or the implicit equation. The conversion between the parametric equation and the implicit equation can be easily accomplished from the minimal μ-bases.     

Length Preserving Multiresolution Editing of Curves

In this paper a method for multiresolution deformation of planar piecewise linear curves that preserves the curve length is presented. In a wavelet based multiresolution editing framework, the curve can be deformed at any level of resolution through its control points. Enforcing the length constraint is carried out in two steps. In a first step the multiresolution decomposition of the curve is used in order to approximate the initial curve length. In a second step the length constraint is satisfied exactly by iteratively smoothing the deformed curve. Wrinkle generation is an application the paper particularly focuses on. It is shown how the multiresolution definition of the curve allows to explicitly and intuitively control the scale of the generated wrinkles.     

Implicitization of Parametric Curves via Lagrange Interpolation

A simple algorithm for finding the implicit equation of a parametric plane curve given by its parametric equations is presented. The algorithm is based on an efficient computation of the Bézout resultant and Lagrange interpolation. One of main features of our approach is the fact that it considerably reduces the problem of computing intermediate expressions.     

Quantifying the effect of a control point on the sign of curvature

We present a method for computing the domain, where a control point is free to move so that the corresponding planar curve is regular and of constant sign of curvature along a subinterval of its parametric domain of definition. The approach encompasses all curve representations that adopt the control-point paradigm and is illustrated for a quintic Bézier curve and a B-spline curve of degree 10.     

Bounding the Distance between 2D Parametric Bézier Curves and their Control Polygon

Employing the techniques presented by Nairn, Peters and Lutterkort in [1], sharp bounds are firstly derived for the distance between a planar parametric Bézier curve and a parameterization of its control polygon based on the Greville abscissae. Several of the norms appearing in these bounds are orientation dependent. We next present algorithms for finding the optimal orientation angle for which two of these norms become minimal. The use of these bounds and algorithms for constructing polygonal envelopes of planar polynomial curves, is illustrated for an open and a closed composite Bézier curve.     

Robust Spherical Parameterization of Triangular Meshes

Parameterization of 3D mesh data is important for many graphics and mesh processing applications, in particular for texture mapping, remeshing and morphing. Closed, manifold, genus-0 meshes are topologically equivalent to a sphere, hence this is the natural parameter domain for them. Parameterizing a 3D triangle mesh onto the 3D sphere means assigning a 3D position on the unit sphere to each of the mesh vertices, such that the spherical triangles induced by the mesh connectivity do not overlap. This is called a spherical triangulation. In this paper we formulate a set of necessary and sufficient conditions on the spherical angles of the spherical triangles for them to form a spherical triangulation. We formulate and solve an optimization procedure to produce spherical triangulations which reflect the geometric properties of a given 3D mesh in various ways.     

Splat representation of parametric surfaces

Point and splat-based representations have become a suitable technique both for modeling and rendering complex 3D shapes. Converting other kinds of models as parametric surfaces to splat-based representations will allow to mix surface and splat-based models and to take advantage of the existing point-based rendering methods. In this work, we present an approach to convert a parametric surface into a splat-based representation. It works in parametric space, performs an adaptive sampling based on the surface curvature and a given error tolerance and uses power Voronoi diagrams. The goal is to approximate the surface with an optimized set of elliptical splats.     

Surface Compression Using a Space of C 1 Cubic Splines with a Hierarchical Basis

A method for compressing surfaces associated with C¹ cubic splines defined on triangulated quadrangulations is described. The method makes use of hierarchical bases, and does not require the construction of wavelets.     

Geometric modeling of spatial constraints: objectives, methods and solid-modeling requirements

Robust Product Lifecycle Management (PLM) technology requires availability of informationally- complete models for all parts of a design-project including spatial constraints. This is the subject of the present investigation, leading to a new model for spatial constraints, the ``virtual solid', which generalizes a similar concept used by Sapidis and Theodosiou to model ``required free-spaces' in plants [14]. The present research focuses on the solid-modeling aspects of the virtual-solid methodology, and derives new solid-modeling problems (related to object definition and to object processing), whose robust treatment is a prerequisite for developing efficient models for complex spatial constraints.     

Anamorphic 3D geometry

An anamorphic image appears distorted from all but a few viewpoints. They have been studied by artists and architects since the early fifteenth century. Computer graphics opens the door to anamorphic 3D geometry. We are not bound by physical reality nor a static canvas. Here we describe a simple method for achieving anamorphoses of 3D objects by utilizing a variation of a simple projective map that is well-known in the computer graphics literature. The novelty of this work is the creation of anamorphic 3D digital models, resulting in a tool for artists and architects.     

Analysis and avoidance of singularities for local G 1 surface interpolation of Bézier curve network with 4-valent nodes

We propose a local method of constructing piecewise G ¹ Bézier patches to span a Bézier curve network with odd- and 4-valent node points. We analyze all possible singular cases of the G ¹ condition that is to be met by the curve network interpolation and propose a new G ¹ continuity condition using linear and quartic scalar weight functions. Using this condition, a curve network can be interpolated without modification at 4-valent nodes with two collinear tangent vectors, even in the presence of singularities. We demonstrate our approach by generating G ¹ surfaces over the curve network which includes singularities at its node vertices and edges.     

Wavelet-Based Multiresolution with

Multiresolution methods are a common technique used for dealing with large-scale data and representing it at multiple levels of detail. We present a multiresolution hierarchy construction based on subdivision, which has all the advantages of a regular data organization scheme while reducing the drawback of coarse granularity. The -subdivision scheme only doubles the number of vertices in each subdivision step regardless of dimension n. We describe the construction of 2D, 3D, and 4D hierarchies representing surfaces, volume data, and time-varying volume data, respectively. The 4D approach supports spatial and temporal scalability. For high-quality data approximation on each level of detail, we use downsampling filters based on n-variate B-spline wavelets. We present a B-spline wavelet lifting scheme for -subdivision steps to obtain small or narrow filters. Narrow filters support adaptive refinement and out-of-core data exploration techniques.     

Line Segment Intersection Testing

A method for accurately determining whether two given line segments intersect is presented. This method uses the standard floating-point arithmetic that conforms to IEEE 754 standard. If three or four ending points of the two given line segments are on a same vertical or horizontal line, the intersection testing result is obtained directly. Otherwise, the ending points and their connections are mapped onto a 3×3 grid, and the intersection testing falls into one of the five testing classes. The intersection testing method is based on our method for floating-point dot product summation, whose error bound is 1ulp. Our method does not have the limitation in the method of Gavrilova and Rokne (2000) that the product of two floating-point numbers is calculated by a twice higher precision floating-point arithmetic than that of the multipliers. Furthermore, this method requires less than one-fifth of the running time used by the method of Gavrilova and Rokne (2000), and our new method for calculating the sign of a sum of n floating-point numbers requires less than one-fifteenth of the running time used by ESSA.