A new interpolation subdivision scheme for triangle/quad mesh

In this paper, we present a new interpolation subdivision scheme for mixed triangle/quad meshes that is C¹ continuous. The new scheme is capable of reproducing the well-known four-point based interpolation subdivision in the quad region but does not reproduce Butterfly subdivision in the triangular part. The new scheme defines rules that produce surfaces both at the regular quad/triangle vertices and isolated, extraordinary points. We demonstrate the visually satisfying of our surfaces through several examples.     

Scalar multivariate subdivision schemes and box splines

We study scalar d-variate subdivision schemes, with dilation matrix 2I, satisfying the sum rules of order k. Using the results of Möller and Sauer, stated for general expanding dilation matrices, we characterize the structure of the mask symbols of such schemes by showing that they must be linear combinations of shifted box spline generators of some polynomial ideal. The directions of the corresponding box splines are columns of certain unimodular matrices. The ideal is determined by the given order of the sum rules or, equivalently, by the order of the zero conditions.The results presented in this paper open a way to a systematic study of subdivision schemes, since box spline subdivisions turn out to be the building blocks of any reasonable multivariate subdivision scheme.As in the univariate case, the characterization we give is the proper way of matching the smoothness of the box spline building blocks with the order of polynomial reproduction of the corresponding subdivision scheme. However, due to the interaction of the building blocks, convergence and smoothness properties may change, if several convergent schemes are combined.The results are illustrated with several examples.     

Interpolation by geometric algorithm

We present a novel geometric algorithm to construct a smooth surface that interpolates a triangular or a quadrilateral mesh of arbitrary topological type formed by n vertices. Although our method can be applied to B-spline surfaces and subdivision surfaces of all kinds, we illustrate our algorithm focusing on Loop subdivision surfaces as most of the meshes are in triangular form. We start our algorithm by assuming that the given triangular mesh is a control net of a Loop subdivision surface. The control points are iteratively updated globally by a simple local point-surface distance computation and an offsetting procedure without solving a linear system. The complexity of our algorithm is O(mn) where n is the number of vertices and m is the number of iterations. The number of iterations m depends on the fineness of the mesh and accuracy required.     

Sharp Features on Multiresolution Subdivision Surfaces

In this paper we describe a method for creating sharp features and trim regions on multiresolution subdivision surfaces along a set of user-defined curves. Operations such as engraving, embossing, and trimming are important in many surface modeling applications. Their implementation, however, is nontrivial due to computational, topological, and smoothness constraints that the underlying surface has to satisfy. The novelty of our work lies in the ability to create sharp features anywhere on a surface and in the fact that the resulting representation remains within the multiresolution subdivision framework. Preserving the original representation has the advantage that other operations applicable to multiresolution subdivision surfaces can subsequently be applied to the edited model. We also introduce an extended set of subdivision rules for Catmull–Clark surfaces that allows the creation of creases along diagonals of control mesh faces.     

√2 Subdivision for quadrilateral meshes

This paper presents a $\sqrt2$ subdivision scheme for quadrilateral meshes that can be regarded as an extension of a 4-8 subdivision with new subdivision rules and improved capability and performance. The proposed scheme adopts a so-called $\sqrt2$ split operator to refine a control mesh such that the face number of the refined mesh generally equals the edge number and is thus about twice the face number of the coarse mesh. Smooth rules are designed in reference to the 4-8 subdivision, while a new set of weights is developed to balance the flatness of surfaces at vertices of different valences. Compared to the 4-8 subdivision, the presented scheme can be naturally generalized for arbitrary control nets and is more efficient in both space and computing time management. Analysis shows that limit surfaces produced by the scheme are C⁴ continuous for regular control meshes and G¹ continuous at extraordinary vertices.     

Subdivision models for varying-resolution and generalized perturbations

Subdivision schemes are multi-resolution methods used in computer-aided geometric design to generate smooth curves or surfaces. In this paper, we are interested in both smooth and non-smooth subdivision schemes. We propose two models that generalize the subdivision operation and can yield both smooth and non-smooth schemes in a controllable way:

• (1) The ‘varying-resolution’ model allows a structured access to the various resolutions of the refined data, yielding certain patterns. This model generalizes the standard subdivision iterative operation and has interesting interpretations in the geometrical space and also in creativity-oriented domains, such as music. As an infrastructure for this model, we propose representing a subdivision scheme by two dual rules trees. The dual tree is a permuted rules tree that gives a new operator-oriented view on the subdivision process, from which we derive an ‘adjoint scheme’.

• (2) The ‘generalized perturbed schemes’ model can be viewed as a special multi-resolution representation that allows a more flexible control on adding the details. For this model, we define the terms ‘template mask’ and ‘tension vector parameter’.

The non-smooth schemes are created by the permutations of the ‘varying-resolution’ model or by certain choices of the ‘generalized perturbed schemes’ model. We then present procedures that integrate and demonstrate these models and some enhancements that bear a special meaning in creative contexts, such as music, imaging and texture. We describe two new applications for our models: (a) data and music analysis and synthesis, which also manifests the usefulness of the non-smooth schemes and the approximations proposed, and (b) the acceleration of convergence and smoothness analysis, using the ‘dual rules tree’.     

Smooth spline surface generation over meshes of irregular topology

An efficient method for generating a smooth spline surface over an irregular mesh is presented in this paper. Similar to the methods proposed by [1, 2, 3, 4], this method generates a generalised bi-quadratic B-spline surface and achieves C ¹ smoothness. However, the rules to construct the control points for the proposed spline surfaces are much simpler and easier to follow. The construction process consists of two steps: subdividing the initial mesh once using the Catmull–Clark [5] subdivision rules and generating a collection of smoothly connected surface patches using the resultant mesh. As most of the final mesh is quadrilateral apart from the neighbourhood of the extraordinary points, most of the surface patches are regular quadratic B-splines. The neighbourhood of the extraordinary points is covered by quadratic Zheng–Ball patches [6].     

L-system specification of knot-insertion rules for non-uniform B-spline subdivision

Subdivision schemes are based on a hierarchy of knot grids in parameter space. A univariate grid hierarchy is regular if all knots are equidistant on each level, and irregular otherwise. We use L-systems to design a wide class of systematically described irregular grid hierarchies. Furthermore, we give sufficient conditions on the L-system which guarantee that the subdivision scheme, based on the non-uniform B-spline of degree d defined on the initial knot grid, is uniformly convergent. If n is the number of symbols in the alphabet of the L-system, this subdivision scheme is defined with a finite set of masks (at most nd+1) which does not depend on the subdivision step. We provide an implementation of such schemes which is available as a worksheet for Sage software.     

A New Interpolatory Subdivision for Quadrilateral Meshes

This paper presents a new interpolatory subdivision scheme for quadrilateral meshes based on a 1–4 splitting operator. The scheme generates surfaces coincident with those of the Kobbelt interpolatory subdivision scheme for regular meshes. A new group of rules are designed for computing newly inserted vertices around extraordinary vertices. As an extension of the regular masks,the new rules are derived based on a reinterpretation of the regular masks. Eigen‐structure analysis demonstrates that subdivision surfaces generated using the new scheme are C¹ continuous and, in addition, have bounded curvature.     

Incomplete k-ary n-cube and its derivatives

Incomplete or pruned k-ary n-cube, n⩾3, is derived as follows. All links of dimension n−1 are left in place and links of the remaining n−1 dimensions are removed, except for one, which is chosen periodically from the remaining dimensions along the intact dimension n−1. This leads to a node degree of 4 instead of the original 2n and results in regular networks that are Cayley graphs, provided that n−1 divides k. For $\text{n=3}\text{(n=5)}$, the preceding restriction is not problematic, as it only requires that k be even (a multiple of 4). In other cases, changes to the basis network to be pruned, or to the pruning algorithm, can mitigate the problem. Incomplete k-ary n-cube maintains a number of desirable topological properties of its unpruned counterpart despite having fewer links. It is maximally connected, has diameter and fault diameter very close to those of k-ary n-cube, and an average internode distance that is only slightly greater. Hence, the cost/performance tradeoffs offered by our pruning scheme can in fact lead to useful, and practically realizable, parallel architectures. We study pruned k-ary n-cubes in general and offer some additional results for the special case n=3.     

Least Squares Subdivision Surfaces

The usual approach to design subdivision schemes for curves and surfaces basically consists in combining proper rules for regular configurations, with some specific heuristics to handle extraordinary vertices. In this paper, we introduce an alternative approach, called Least Squares Subdivision Surfaces (LS), where the key idea is to iteratively project each vertex onto a local approximation of the current polygonal mesh. While the resulting procedure haves the same complexity as simpler subdivision schemes, our method offers much higher visual quality, especially in the vicinity of extraordinary vertices. Moreover, we show it can be easily generalized to support boundaries and creases. The fitting procedure allows for a local control of the surface from the normals, making LS³ very well suited for interactive freeform modeling applications. We demonstrate our approach on diadic triangular and quadrangular refinement schemes, though it can be applied to any splitting strategies.     

Connected sum of digital closed surfaces

During the past 20 years the research of digital surfaces has proceeded to find their properties in the digital space Zⁿ, such as a topological number, a simple k-point, the 3D-Jordan theorem, a k-separating set, a boundary detecting algorithm and so on. Actually, unlike surfaces in a continuous space, the features of digital surfaces have different characteristics. The aim of this paper is to introduce the notion of a digital closed k-surface in Zⁿ, n ? 3, with the general k-adjacency relations as a generalization of Malgouyres’ and Morgenthaler’s k-surfaces in Z³, to establish some minimal simple closed k-surfaces in Z³ and to find their digital topological properties in relation with the k-fundamental group and k-contractibility. Moreover, a connected sum of two digital closed surfaces is introduced and its digital topological properties are investigated.     

n-Dimensional multiresolution representation of subdivision meshes with arbitrary topology

We present a new model for the representation of n-dimensional multiresolution meshes. It provides a robust topological representation of arbitrary meshes that are combined in closely interlinked levels of resolution. The proposed combinatorial model is formalized through the mathematical model of combinatorial maps allowing us to give a general formulation, in any dimensions, of the topological subdivision process that is a key issue to robustly and soundly define mesh hierarchies. It fully supports multiresolution edition what allows the implementation of most mesh processing algorithms – like filtering or compression – for n-dimensional meshes with arbitrary topologies.We illustrate this model, in dimension 3, with an new truly multiresolution representation of subdivision volumes. It allows us to extend classical subdivision schemes to arbitrary polyhedrons and to handle adaptive subdivision with an elegant solution to compliance issues. We propose an implementation of this model as an effective and relatively inexpensive data structure.     

Total Least Squares Fitting of k-Spheres in n-D Euclidean Space Using an (n+2)-D Isometric Representation

We fit k-spheres optimally to n-D point data, in a geometrically total least squares sense. A specific practical instance is the optimal fitting of 2D-circles to a 3D point set. Among the optimal fitting methods for 2D-circles based on 2D (!) point data compared in Al-Sharadqah and Chernov (Electron. J. Stat. 3:886–911, 2009), there is one with an algebraic form that permits its extension to optimally fitting k-spheres in n-D. We embed this ‘Pratt 2D circle fit’ into the framework of conformal geometric algebra (CGA), and doing so naturally enables the generalization. The procedure involves a representation of the points in n-D as vectors in an (n+2)-D space with attractive metric properties. The hypersphere fit then becomes an eigenproblem of a specific symmetric linear operator determined by the data. The eigenvectors of this operator form an orthonormal basis representing perpendicular hyperspheres. The intersection of these are the optimal k-spheres; in CGA the intersection is a straightforward outer product of vectors. The resulting optimal fitting procedure can easily be implemented using a standard linear algebra package; we show this for the 3D case of fitting spheres, circles and point pairs. The fits are optimal (in the sense of achieving the KCR lower bound on the variance). We use the framework to show how the hyperaccurate fit hypersphere of Al-Sharadqah and Chernov (Electron. J. Stat. 3:886–911, 2009) is a minor rescaling of the Pratt fit hypersphere.     

Decision algorithms for multiplayer noncooperative games of incomplete information

Extending the complexity results of Reif [1,2] for two player games of incomplete information, this paper (see also [3]) presents algorithms for deciding the outcome for various classes of multiplayer games of incomplete information, i.e., deciding whether or not a team has a winning strategy for a particular game. Our companion paper, [4] shows that these algorithms are indeed asymptotically optimal by providing matching lower bounds. The classes of games to which our algorithms are applicable include games which were not previously known to be decidable. We apply our algorithms to provide alternative upper bounds, and new time-space trade-offs on the complexity of multiperson alternating Turing machines [3]. We analyze the algorithms to characterize the space complexity of multiplayer games in terms of the complexity of deterministic computation on Turing machines.In hierarchical multiplayer games, each additional clique (subset of players with the same information) increases the complexity of the outcome problem by a further exponential. We show that an S(n) space bounded k-player game of incomplete information has a deterministic time upper bound of k + 1 repeated exponentials of S(n). Furthermore, S(n) space bounded k-player blindfold games have a deterministic space upper bound of k repeated exponentials of S(n). This paper proves that this exponential blow-up can occur.We also show that time bounded games do not exhibit such hierarchy. A T(n) time bounded blindfold multiplayer game, as well as a T(n) time bounded multiplayer game of incomplete information, has a deterministic space bound of T(n).     

Off-chip communication architectures for high throughput network processors

In this paper, we propose a new interconnection mechanism for network line cards. We project that the packet storage needs for the next-generation networks will be much higher. Such that the number of memory modules required to store the packets will be more than that can be directly connected to the network processor (NPU). In other words, the NPU I/O pins are limited and they do not scale well with the growing number of memory modules and processing elements employed on the network line cards. As a result, we propose to explore more suitable off-chip interconnect and communication mechanisms that will replace the existing systems and that will provide extraordinary high throughput. In particular, we investigate if the packet-switched k-ary n-cube networks can be a solution. To the best of our knowledge, this is the first time, the k-ary n-cube networks are used on a board. We investigate multiple k-ary n-cube based interconnects and include a variation of 2-ary 3-cube interconnect called the 3D-mesh. All of the k-ary n-cube interconnects include multiple, highly efficient techniques to route, switch, and control packet flows in order to minimize congestion spots and packet loss within the interconnects. We explore the tradeoffs between implementation constraints and performance. Performance results show that k-ary n-cube topologies significantly outperform the existing line card interconnects and they are able to sustain higher traffic loads. Furthermore, the 3D-mesh reaches the highest performance results of all interconnects and allows future scalability to adopt more memories and/or processors to increase the line card’s processing power.     

A refined search tree technique for Dominating Set on planar graphs

We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8^kn) and O(8^kk+n³), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.     

Evolving Guide Subdivision

To overcome the well-known shape deficiencies of bi-cubic subdivision surfaces, Evolving Guide subdivision (EG subdivision) generalizes C² bi-quartic (bi-4) splines that approximate a sequence of piecewise polynomial surface pieces near extraordinary points. Unlike guided subdivision, which achieves good shape by following a guide surface in a two-stage, geometry-dependent process, EG subdivision is defined by five new explicit subdivision rules. While formally only C¹ at extraordinary points, EG subdivision applied to an obstacle course of inputs generates surfaces without the oscillations and pinched highlight lines typical for Catmull-Clark subdivision. EG subdivision surfaces join C² with bi-3 surface pieces obtained by interpreting regular sub-nets as bi-cubic tensor-product splines and C² with adjacent EG surfaces. The EG subdivision control net surrounding an extraordinary node can have the same structure as Catmull-Clark subdivision: two rings of 4-sided facets around each extraordinary nodes so that extraordinary nodes are separated by at least one regular node.     

A non-stationary subdivision scheme for the construction of deformable models with sphere-like topology

We present an affine-invariant non-stationary subdivision scheme for the recursive refinement of any triangular mesh that is regular or has extraordinary vertices of valence 4. In particular, when applied to an arbitrary convex octahedron, it produces a G¹-continuous surface with a blob-like shape as the limit of the recursive subdivision process. In case of a regular octahedron, the subdivision process provides an accurate representation of ellipsoids. Our scheme allows us to easily construct a new interactive 3D deformable model for use in the delineation of biomedical images, which we illustrate by examples that deal with the characterization of 3D structures with sphere-like topology such as embryos, nuclei, or brains.     

A free shape 3d modeling system for creative design based on modified catmull-clark subdivision

How to express the designer’s creative intent in a simple and intuitive way is the main problem in 3d modeling, especially for novice designers. This paper presents a free shape 3d modeling system for creative design based on modified Catmull-Clark subdivision. The system contains a series of easy but novel operations which can be used to change the topology of models, such as creating holes and handles. In order to create sharp features, feature marking operations are provided to specify where the sharp feature is. This system also provides surface conversion function to make the modeling results be compatible with the traditional CAD systems. Firstly, a simple but efficient quad domain division scheme is adopted to generate quad sub-meshes. In order to improve the smoothness at the regular vertices, long boundary curves which across multiple sub-meshes are used to be the boundary constraints while fitting. In this way, the smoothness at regular vertex can be C² continuous. We perform experiments for both skilled and novice designers. Results show that our system is easy to operate and can be used to construct complex models with less time.