Search

In the field of CAGD/CAD, interpolation curve plays an important role in shape representation and shape design. Based on the traditional quintic Hermite interpolation curve, this paper proposes a novel class of quintic generalized Hermite interpolation curve (QG-Hermite interpolation curve, for short) with local shape parameters, which can satisfy C2 continuity automatically. Since each segment of the constructed curve has independent shape parameters, and its shape can be adjusted locally or globally by modifying the shape parameters. First, to obtain an interpolation curve satisfying certain specific geometric requirements such as the approximate shortest arc length, the strain energy minimization or the curvature variation energy minimization, etc., three shape optimization models of the QG-Hermite interpolation curve are established. Second, an improved gray wolf optimization (I-GWO) algorithm is used to solve the shape optimization models so as to determine the optimal shape parameters. Finally, the modeling examples show that the proposed method is effective and applicable in shape designing. [ABSTRACT FROM AUTHOR]

The goal of Point Distance Solving Problems is to find 2D or 3D placements of points knowing distances between some pairs of points. The common guideline is to solve them by a numerical iterative method (e.g. Newton-Raphson method). A sole solution is obtained whereas many exist. However the number of solutions can be exponential and methods should provide solutions close to a sketch drawn by the user. Geometric reasoning can help to simplify the underlying system of equations by changing a few equations and triangularizing it. This triangularization is a geometric construction of solutions, called construction plan. We aim at finding several solutions close to the sketch on a one-dimensional path defined by a global parameter-homotopy using a construction plan. Some numerical instabilities may be encountered due to specific geometric configurations. We address this problem by changing on-the-fly the construction plan. Numerical results show that this hybrid method is efficient and robust. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to show how to use the Gauss map to produce efficient triangulations of parametric surfaces. The central idea is to invert canonical triangulations of the sphere using the Gauss map. The main problem is that the inverse of the Gauss map is not in general well defined. We show how to overcome this problem and formulate an algorithm to generate the desired triangulation. [ABSTRACT FROM PUBLISHER]

Abstract: We give an efficient algorithm for partitioning the domain of a numeric function into segments. The function is realized as a polynomial in each segment, and a lookup table stores the coefficients of the polynomial. Such an algorithm is an essential part of the design of lookup table methods Ercepovac et al. (2000) , Lee et al. (2003) , Nagayama et al. (2007) , Paul et al. (2007) and Sasao et al. (2004) for realizing numeric functions, such as , , and . Our algorithm requires many fewer steps than a previous algorithm given in Frenzen et al. (2010) and makes tractable the design of numeric function generators based on table lookup for high-accuracy applications. We show that an estimate of segment width based on local derivatives greatly reduces the search needed to determine the exact segment width. We apply the new algorithm to a suite of 15 numeric functions and show that the estimates are sufficiently accurate to produce a minimum or near-minimum number of computational steps. [Copyright &y& Elsevier]

Surface multiresolution processing is an important subject in CAGD. It also poses many challenging problems including the design of multiresolution algorithms. Unlike images which are in general sampled on a regular square or hexagonal lattice, the meshes in surfaces processing could have an arbitrary topology, namely, they consist of not only regular vertices but also extraordinary vertices, which requires the multiresolution algorithms have high symmetry. With the idea of lifting scheme, Bertram (Computing 72(1-2):29-39, ) introduces a novel triangle surface multiresolution algorithm which works for both regular and extraordinary vertices. This method is also successfully used to develop multiresolution algorithms for quad surface and $\sqrt 3$ triangle surface processing in Wang et al. (Vis Comput 22(9-11):874-884, ; IEEE Trans Vis Comput Graph 13(5):914-925, ) respectively. When considering the biorthogonality, these papers do not use the conventional $L^2({{\rm I}\kern-.2em{\rm R}}^2)$ inner product, and they do not consider the corresponding lowpass filter, highpass filters, scaling function and wavelets. Hence, some basic properties such as smoothness and approximation power of the scaling functions and wavelets for regular vertices are unclear. On the other hand, the symmetry of subdivision masks (namely, the lowpass filters of filter banks) for surface subdivision is well studied, while the symmetry of the highpass filters for surface processing is rarely considered in the literature. In this paper we introduce the notion of 4-fold symmetry for biorthogonal filter banks. We demonstrate that 4-fold symmetric filter banks result in multiresolution algorithms with the required symmetry for quad surface processing. In addition, we provide 4-fold symmetric biorthogonal FIR filter banks and construct the associated wavelets, with both the dyadic and $\sqrt 2$ refinements. Furthermore, we show that some filter banks constructed in this paper result in very simple multiresolution decomposition and reconstruction algorithms as those in Bertram (Computing 72(1-2):29-39, ) and Wang et al. (Vis Comput 22(9-11):874-884, ; IEEE Trans Vis Comput Graph 13(5):914-925, ). Our method can provide the filter banks corresponding to the multiresolution algorithms in Wang et al. (Vis Comput 22(9-11):874-884, ) for dyadic multiresolution quad surface processing. Therefore, the properties of the scaling functions and wavelets corresponding to those algorithms can be obtained by analyzing the corresponding filter banks. [ABSTRACT FROM AUTHOR]

Abstract: This paper is about the construction of univariate wavelet bi-frames with each framelet being symmetric. As bivariate filter banks are used for surface multiresolution processing, it is required that the corresponding decomposition and reconstruction algorithms have high symmetry so that it is possible to design the corresponding multiresolution algorithms for extraordinary vertices. For open surfaces, special multiresolution algorithms are designed to process boundary vertices. When the multiresolution algorithms derived from univariate wavelet bi-frames are used as the boundary algorithms, it is desired that not only the scaling functions but also all framelets be symmetric. In addition, the algorithms for curve/surface multiresolution processing should be given by templates so that they can be easily implemented. In this paper, first, by appropriately associating the lowpass and highpass outputs to the nodes of , we show that both biorthogonal wavelet multiresolution algorithms and bi-frame multiresolution algorithms can be represented by templates. Then, using the idea of the lifting scheme, we provide frame algorithms given by several iterative steps with each step represented by a symmetric template. Finally, with the given templates of algorithms, we obtain the corresponding filter banks and construct bi-frames based on their smoothness and vanishing moments. Two types of symmetric bi-frames are studied in this paper. In order to provide a clearer picture on the template-based procedure for bi-frame construction, in this paper we also consider the template-based construction of biorthogonal wavelets. The approach of the template-based bi-frame construction introduced in this paper can be extended easily to the construction of bivariate bi-frames with high symmetry for surface multiresolution processing. [ABSTRACT FROM AUTHOR]

Most of graph drawing algorithms draw graphs on unbounded planes. However, there are applications that require graphs to be drawn on the plane inside a given polygon. In this paper, a new algorithm for planar orthogonal drawing of complete binary trees inside rectilinear polygons is presented. Uniform distribution of nodes of graphs on drawing regions is one of the aesthetics criteria in graph drawing. The goal of this paper is to produce planar orthogonal drawings with a relatively uniform node distribution and few edge bends. The proposed algorithm can be considered as a generalization of the H-tree layout method for rectilinear polygons. A new linear time algorithm is also given for bisecting rectilinear polygons into two equi-area rectilinear sub-polygons. [ABSTRACT FROM AUTHOR]

Abstract: When bivariate filter banks and wavelets are used for surface multiresolution processing, it is required that the decomposition and reconstruction algorithms for regular vertices derived from them have high symmetry. This symmetry requirement makes it possible to design the corresponding multiresolution algorithms for extraordinary vertices. Recently lifting-scheme based biorthogonal bivariate wavelets with high symmetry have been constructed for surface multiresolution processing. If biorthogonal wavelets have certain smoothness, then the analysis or synthesis scaling function or both have big supports in general. In particular, when the synthesis low-pass filter is a commonly used scheme such as Loop’s scheme or Catmull–Clark’s scheme, the corresponding analysis low-pass filter has a big support and the corresponding analysis scaling function and wavelets have poor smoothness. Big supports of scaling functions, or in other words big templates of multiresolution algorithms, are undesirable for surface processing. On the other hand, a frame provides flexibility for the construction of “basis” systems. This paper concerns the construction of wavelet (or affine) bi-frames with high symmetry. In this paper we study the construction of wavelet bi-frames with 4-fold symmetry for quadrilateral surface multiresolution processing, with both the dyadic and refinements considered. The constructed bi-frames have 4 framelets (or frame generators) for the dyadic refinement, and 2 framelets for the refinement. Namely, with either the dyadic or refinement, a frame system constructed in this paper has only one more generator than a wavelet system. The constructed bi-frames have better smoothness and smaller supports than biorthogonal wavelets. Furthermore, all the frame algorithms considered in this paper are given by templates so that one can easily implement them. [Copyright &y& Elsevier]

Simple criteria for the existence of rational rotation-minimizing frames (RRMFs) on quintic space curves are determined, in terms of both the quaternion and Hopf map representations for Pythagorean-hodograph (PH) curves in ℝ. In both cases, these criteria amount to satisfaction of three scalar constraints that are quadratic in the curve coefficients, and are thus much simpler than previous criteria. In quaternion form, RRMF quintics can be characterized by just a single quadratic (vector) constraint on the three quaternion coefficients. In the Hopf map form, the characterization is in terms of one real and one complex quadratic constraint on the six complex coefficients. The identification of these constraints is based on introducing a “canonical form” for spatial PH curves and judicious transformations between the quaternion and Hopf map descriptions. The simplicity of these new characterizations for the RRMF quintics should help facilitate the development of algorithms for their construction, analysis, and practical use in applications such as animation, spatial motion planning, and swept surface constructions. [ABSTRACT FROM AUTHOR]

This paper develops a discrete methodology for approximating the so-called convex domain of a NURBS curve, namely the domain in the ambient space, where a user-specified control point is free to move so that the curvature and torsion retains its sign along the NURBS parametric domain of definition. The methodology provides a monotonic sequence of convex polyhedra, converging from the interior to the convex domain. If the latter is non-empty, a simple algorithm is proposed, that yields a sequence of polytopes converging uniformly to the restriction of the convex domain to any user-specified bounding box. The algorithm is illustrated for a pair of planar and a spatial Bézier configuration. [ABSTRACT FROM AUTHOR]

This paper is concerned with the re-representation of a G1 composite rational Bézier curve. Although the rational Bézier curve segments that form the composite curve are G1 continuous at their joint points, their homogeneous representations may not be even C0 continuous in the homogeneous space. In this paper, an algorithm is presented to convert the G1 composite rational Bézier curve into a NURBS curve whose nonrational homogeneous representation is C1 continuous in the homogeneous space. This re-representation process involves reparameterization using Möbius transformations, smoothing multiplication and parameter scaling transformations. While the previous methods may fail in some situations, the method proposed in this paper always works. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we analyze the problem of partitioning a continuous curve into n parts with equal successive chords, the curve EquiPartition problem (EP). The goal is to locate consecutive curve points, so that the curve can be divided into n segments with equal chords under a distance function. We adopt a level set approach to prove that for any continuous injective curve in a metric space and any number n there always exists at least one n-equipartition (EP). A new approximate algorithm, that is the first EP algorithm, inspired from the level set approach is proposed for finding all solutions with high accuracy. Finally, EP based applications are presented and special properties of their solutions are discussed. [Copyright &y& Elsevier]

Dupin cyclides, their applications in geometric modelling and their parametrization using bi-quadratic patches bounded by lines of curvature, have been investigated in recent years by a number of authors such as Martin, de Pont and Sharrock in 1986, Boehm in 1990, Pratt in 1990, and Degen in 1994. However, no completely reliable and general algorithm for the determination of bi-quadratic cyclide patches has appeared in the literature. This paper presents a new approach that produces any required bi-quadratic patch, bounded by lines of curvature, without non-intrinsic geometric constraints or restrictions. Specifically, if a bi-quadratic parametrization exists for the specified region of the cyclide, then it is correctly determined. Explicit formulae are given for the Bernstein weights and vectors of the parametrizations. The method is neither cyclide specific nor specific to the construction of bi-quadratic rational parametrizations - it may therefore be applied to other surfaces and to higher degree rational constructions. [ABSTRACT FROM AUTHOR]

Abstract: The biarc is a curve made by joining two circular arcs in a fashion. There is a one-parameter family of biarcs that can match given planar, two-point Hermite data. This note considers the range of Hermite data that can be matched, identifies the region in which the members of the family of biarcs lie, and shows that there is exactly one member biarc passing through each point in that region. [Copyright &y& Elsevier]

Abstract: Algorithms are developed, based on topological principles, to evaluate the boundary and “internal structure” of the Minkowski sum of two planar curves. A graph isotopic to the envelope curve is constructed by computing its characteristic points. The edges of this graph are in one-to-one correspondence with a set of monotone envelope segments. A simple formula allows a degree to be assigned to each face defined by the graph, indicating the number of times its points are covered by the Minkowski sum. The boundary can then be identified with the set of edges that separate faces of zero and non-zero degree, and the boundary segments corresponding to these edges can be approximated to any desired geometrical accuracy. For applications that require only the Minkowski sum boundary, the algorithm minimizes geometrical computations on the “internal” envelope edges, that do not contribute to the final boundary. In other applications, this internal structure is of interest, and the algorithm provides comprehensive information on the covering degree for different regions within the Minkowski sum. Extensions of the algorithm to the computation of Minkowski sums in , and other forms of geometrical convolution, are briefly discussed. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

An algorithm for constructing arbitrary parametric quadratic quadric triangles in rational Bézier form is presented. The algorithm does not require the knowledge of the underlying quadric, an important property in view of applying this method for the interpolation of triangulated 3D data points. The algorithm consists of four steps starting with the arbitrary choice of the three corner points and corner weights of the patch, by then constructing a certain triangle and a tetrahedron by means of which the remaining inner control points and weights are obtained guaranteeing the resulting patch to lie on a quadric surface. [ABSTRACT FROM AUTHOR]

Current surface reconstruction algorithms focus on complex surfaces or irregular surfaces. However, surfaces of revolution are very important in industrial applications and reconstruction of rotating surfaces are often required. To reconstruct a surface of revolution is to determine its axis and generatrix. The main obstacle is derived from, different from surfaces used in current surface reconstruction, the data of a surface of revolution are typically partially sampled. It makes the reconstruction of rotating surfaces a real interesting problem. In this paper, we present an algorithm to compute the axis and generatrix of a surface of revolution in such partially sampled case. [Copyright &y& Elsevier]