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.     

Reverse engineering with subdivision surfaces

Reverse engineering is concerned with the reconstruction of surfaces from three-dimensional point clouds originating from laser-scanned objects. We present an adaptive surface reconstruction method providing a hierarchy of quadrilateral meshes adapting surface topology when a mesh is refined. This way, a user can choose a model with proper resolution and topology from the hierarchy without having to run the algorithm multiple times with different parameters. The multiresolution mesh representation can be used subsequently for view-dependent rendering and wavelet compression.     

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.     

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.     

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.     

Shadow metamorphosis

Any two objects A and B can be viewed as two different projections of their Cartesian product A×B. Rotating and projecting A×B results in a continuous transformation of A into B. During certain rotations, the contour of the Cartesian product remains the same although its projection changes. Based on these properties, we derive a fast and simple morphing algorithm without topological constraints on either object.     

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.     

Hierarchical and adaptive visualization on nested grids

Modern numerical methods are capable to resolve fine structures in solutions of partial differential equations. Thereby they produce large amounts of data. The user wants to explore them interactively by applying visualization tools in order to understand the simulated physical process. Here we present a multiresolution approach for a large class of hierarchical and nested grids. It is based on a hierarchical traversal of mesh elements combined with an adaptive selection of the hierarchical depth. The adaptation depends on an error indicator which is closely related to the visual impression of the smoothness of isosurfaces or isolines, which are typically used to visualize data. Significant examples illustrate the applicability and efficiency on different types of meshes.     

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.     

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.     

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.     

On some union and intersection problems for polygons with fixed orientations

Objects with fixed orientations play an important role in many application areas, for instance VLSI design. Problems involving only rectilinearly oriented (rectangular) objects, as a simplest case, have been studied with the VLSI design application in mind. These objects can be transistors, cells or macros. In reality, they are more suitably represented by polygons rather than just rectangles. In this note we describe how to perform a general decomposition of a set of polygons with fixed orientations in order to solve various computational geometry problems which are important in VLSI design. The decomposition is very simple and efficiently computable, and it allows the subsequent application of algorithms for the rectilinear case, leading to some very efficient and some optimal solutions. We illustrate the technique in detail at the problem of finding the connected components of a set of polygons, for which we derive an optimal solution. The wide applicability of the method is then demonstrated at the problem of finding all pairs of intersecting polygons, yielding an optimal solution.The work of this author was partially supported by the National Science Foundation under Grants MCS 8342682 and ECS 8340031. This work was performed while this author was a summer visitor at the IBM T. J. Watson Research Center.     

Stereoscopic view-dependent visualization of terrain height fields

Visualization of large geometric environments has always been an important problem of computer graphics. We present a framework for the stereoscopic view-dependent visualization of large scale terrain models. We use a quadtree based multiresolution representation for the terrain data. This structure is queried to obtain the view-dependent approximations of the terrain model at different levels of detail. In order not to lose depth information, which is crucial for the stereoscopic visualization, we make use of a different simplification criterion, namely, distance-based angular error threshold. We also present an algorithm for the construction of stereo pairs in order to speed up the view-dependent stereoscopic visualization. The approach we use is the simultaneous generation of the triangles for two stereo images using a single draw-list so that the view frustum culling and vertex activation is done only once for each frame. The cracking problem is solved using the dependency information stored for each vertex. We eliminate the popping artifacts that can occur while switching between different resolutions of the data using morphing. We implemented the proposed algorithms on personal computers and graphics workstations. Performance experiments show that the second eye image can be produced approximately 45 percent faster than drawing the two images separately and a smooth stereoscopic visualization can be achieved at interactive frame rates using continuous multiresolution representation of height fields     

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.     

Scaling techniques for gradient projection-type methods in astronomical image deblurring

The aim of this paper is to present a computational study on scaling techniques in gradient projection-type (GP-type) methods for deblurring of astronomical images corrupted by Poisson noise. In this case, the imaging problem is formulated as a non-negatively constrained minimization problem in which the objective function is the sum of a fit-to-data term, the Kullback–Leibler divergence, and a Tikhonov regularization term. The considered GP-type methods are formulated by a common iteration formula, where the scaling matrix and the step-length parameter characterize the different algorithms. Within this formulation, both first-order and Newton-like methods are analysed, with particular attention to those implementation features and behaviours relevant for the image restoration problem. The numerical experiments show that suited scaling strategies can enable the GP methods to quickly approximate accurate reconstructions and then are useful for designing effective image deblurring algorithms.     

基于运动补偿的三维小波视频编码

提出了一种新的基于运动补偿的三维小波视频编码方案。通过对原始图象序列沿着运动轨迹进行时间维小波分解以及空间上的二维小波分解，得到不同的时间－空间三维频率子带。然后，将这些子带中的小波系数构成三维方向等级树结构，并采用改进的ＳＰＩＨＴ零树编码算法进行压缩。实验表明，此方法不仅提高了视频编码效率，而且易于进行码率控制，以及实现时间、空间分辨率上的可伸缩编码     

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.