We introduce an extremely scalable and efficient yet simple palette-based image decomposition algorithm. Given an RGB image and set of palette colors, our algorithm decomposes the image into a set of ...additive mixing layers, each of which corresponds to a palette color applied with varying weight. Our approach is based on the geometry of images in RGBXY-space. This new geometric approach is orders of magnitude more efficient than previous work and requires no numerical optimization. We provide an implementation of the algorithm in 48 lines of Python code. We demonstrate a real-time layer decomposition tool in which users can interactively edit the palette to adjust the layers. After preprocessing, our algorithm can decompose 6 MP images into layers in 20 milliseconds.
Object deformation with linear blending dominates practical use as the fastest approach for transforming raster images, vector graphics, geometric models and animated characters. Unfortunately, ...linear blending schemes for skeletons or cages are not always easy to use because they may require manual weight painting or modeling closed polyhedral envelopes around objects. Our goal is to make the design and control of deformations simpler by allowing the user to work freely with the most convenient combination of handle types. We develop linear blending weights that produce smooth and intuitive deformations for points, bones and cages of arbitrary topology. Our weights, called bounded biharmonic weights, minimize the Laplacian energy subject to bound constraints. Doing so spreads the influences of the controls in a shape-aware and localized manner, even for objects with complex and concave boundaries. The variational weight optimization also makes it possible to customize the weights so that they preserve the shape of specified essential object features. We demonstrate successful use of our blending weights for real-time deformation of 2D and 3D shapes.
•Use polynomials of Wachspress GBCs to construct smooth vertex splines over convex quadrilaterals.•The derivation of the construction is aided by MATHEMATICA and MATLAB to ensure the ...correctness.•These smooth vertex splines are locally supported which can be used to adjust and mend a surface.•Quasi-interpolatory operators are constructed and their approximation properties are shown.•These vertex splines are used to construct smooth surfaces such as suitcase corners.
In this paper we construct smooth bivariate spline functions over a polygonal partition, e.g. a convex quadrilateral partition by using vertex spline techniques. Vertex splines, introduced in Chui and Lai (1985) are smooth piecewise polynomial functions supported over a collection of triangles sharing a vertex. In this paper, we extend the concept of vertex splines to the partition of polygons and describe how to construct C1 vertex polygonal splines over a collection of quadrilaterals. We begin with our construction of C1 vertex splines over a collection of parallelograms, although they may not be axis-orientated. Then the construction is generalized to the setting of general convex quadrilaterals. We will use various monomials of Wachspress GBC functions of degrees 5 and 7 to explain how to construct C1 vertex splines together with additional special splines called edge and face splines. With these splines at hand, we construct quasi-interpolatory formulas, whose approximation properties will be shown. Numerical interpolation and approximation results will be presented. Finally, three applications of these splines are explained: the first one is to form smooth locally supported GBC functions, the second one is to construct smooth suitcase corners, and the third one to construct C1 surfaces over quadrilateral partitions with extraordinary points (EP). Several examples will be demonstrated to show the convenience of using these splines.
In recent years, there has been growing interest in the representation of volumes within the field of geometric modeling (GM). While polygonal patches for surface modeling have been extensively ...studied, there has been little focus on the representation of polyhedral volumes. Inspired by the polygonal representation of the Generalized Bézier (GB) patch proposed by Várady et al. (2016), this paper introduces a novel method for polyhedral volumetric modeling called the Generalized Bézier (GB) volume.
GB volumes are defined over simple convex polyhedra using generalized barycentric coordinates (GBCs), with the control nets which are a direct generalization of those of tensor-product Bézier volumes. GB volumes can be smoothly connected to adjacent tensor-product Bézier or GB volumes with G1 or G2 continuity. Besides, when the parametric polyhedron becomes a prism, the GB volume also degenerates into a tensor-product form. We provide some practical examples to demonstrate the advantages of GB volumes. Suggestions for future work are also discussed.
•We propose a novel polyhedral volumetric representation method, called Generalized Bézier (GB) volume.•A GB volume behaves as a tensor-product Bézier volume along each quadrilateral boundary surface and a tensor-product GB volume along each multi-sided boundary surface.•A GB volume can be easily connected to adjacent tensor-product Bézier or (tensor-product) GB volume with high order geometric continuity (G1 or G2).•A GB volume will reproduce a tensor-product GB volume when the domain polyhedron becomes a prism.•We also present a polyhedral Bézier extraction algorithm that enables the construction of a globally smooth volume from any input hexmesh with arbitrary irregularities or from input simple-convex-polyhedral meshes.
We construct H(\mathrm {curl}) and H(\mathrm {div}) conforming finite elements on convex polygons and polyhedra with minimal possible degrees of freedom, i.e., the number of degrees of freedom is ...equal to the number of edges or faces of the polygon/polyhedron. The construction is based on generalized barycentric coordinates and the Whitney forms. In 3D, it currently requires the faces of the polyhedron be either triangles or parallelograms. Formulas for computing basis functions are given. The finite elements satisfy discrete de Rham sequences in analogy to the well-known ones on simplices. Moreover, they reproduce existing H(\mathrm {curl})- H(\mathrm {div}) elements on simplices, parallelograms, parallelepipeds, pyramids and triangular prisms. The approximation property of the constructed elements is also analyzed by showing that the lowest-order simplicial Nédélec-Raviart-Thomas elements are subsets of the constructed elements on arbitrary polygons and certain polyhedra.
The finite element method stands out as a powerful tool for modelling engineering problems. They are particularly well suited thanks to adaptive discretization techniques involving mesh size (h) or ...polynomial degree (p) or a combination of both (hp). In the case of p-adaptiveness, high-order function bases are required on the elements.
For polygonal elements in 2D, Wachspress proved that, in the general case, it is not possible to construct a set of Lagrange finite elements with polynomial functions. Instead, this can be achieved through a popular set of basis functions which are generalized barycentric coordinates. One such family of functions is the Wachspress functions which are well suited for strictly convex polygons.
While recent work has led to the construction of quadratic approximations from first-order Wachspress functions, there exists no approach for generalizing to higher orders for any strictly convex polygon. This work provides a general method to develop k-order Wachspress bases for any m-face polygon, where k<m. This method relies on symbolic computation for the assembly of a linear system whose numerical solution gives the values of the unknown coefficients of the Wachspress functions, and can be viewed as a generalization of Dasgupta's GADJ algorithm.
This work originates from the development of a high-order Discontinuous Galerkin (DG) scheme for the solution of a linear transport equation over honeycomb meshes. As such, the regular hexagon is the strictly convex polygon taken as an example to describe the proposed method. We ensure that the functions obtained enforce the constraints required for their application in a finite element approach. Furthermore, we have successfully applied these functions to a finite element discretization of the Poisson equation and provided a test case for the linear transport equation on honeycomb meshes.
In addition, further results are provided for an irregular pentagon to show the generality of the approach.
•The finite element method is a powerful tool for engineering problems.•In 2D, it is not possible to construct Lagrange elements with polynomial functions.•No previous work for higher orders for any strictly convex polygons exists.•This method relies on symbolic computation to obtain high-order bases.•It can be viewed as a generalization of Dasgupta's GADJ algorithm.
It is known that generalized barycentric coordinates can be used to form Bernstein polynomial-like functions over a polygon with any number of sides. We propose to use these functions to form a space ...of continuous polygonal splines (piecewise defined functions) of order d over a partition consisting of polygons which is able to reproduce all polynomials of degree d. Locally supported basis functions for the space are constructed for order d ≥ 2. The construction for d = 2 is simpler than the "serendipity" quadratic finite elements that have appeared in the recent literature. The number of basis functions is similar to, but fewer than, those of the virtual element method. We use them for the numerical solution of the Poisson equation on two special types of nontriangular partitions to present a proof of concept for solving PDEs over polygonal partitions. Numerical solutions based on quadrangulations and pentagonal partitions are demonstrated to show the efficiency of these polygonal spline functions. They can lead to a more accurate solution by using fewer degrees of freedom than the traditional continuous polynomial finite element method if the solutions are smooth although assembling the mass and stiffness matrices can take more time.
We derive upper and lower bounds on the gradients of Wachspress coordinates defined over any simple convex d-dimensional polytope P. The bounds are in terms of a single geometric quantity h*, which ...denotes the minimum distance between a vertex of P and any hyperplane containing a nonincident face. We prove that the upper bound is sharp for d = 2 and analyze the bounds in the special cases of hypercubes and simplices. Additionally, we provide an implementation of the Wachspress coordinates on convex polyhedra using MATLAB and employ them in a three-dimensional finite element solution of the Poisson equation on a nontrivial polyhedral mesh. As expected from the upper bound derivation, the H1-norm of the error in the method converges at a linear rate with respect to the size of the mesh elements.
Anisotropic mesh quality measures and adaptation are studied for convex polygonal meshes. Three sets of alignment and equidistribution measures are developed, based on least squares fitting, ...generalized barycentric mappings, and the singular value decomposition, respectively. Numerical tests show that all three sets of mesh quality measures provide good measurements for the quality of polygonal meshes under given anisotropic metrics. Based on the second set of quality measures and using a moving mesh partial differential equation, an anisotropic adaptive polygonal mesh method is constructed for the numerical solution of second-order elliptic equations. Numerical examples are presented to demonstrate the effectiveness of the method.