In order to study differential properties of a subdivision surface at a markpoint, it is necessary to parametrise it over a so-called characteristic map defined as the infinite union of C k -parametrised rings. Construction of this map is known when a single step of the subdivision scheme does not rotate a regular lattice. Otherwise, two steps are considered as they realign the lattice and its subdivided version. We present a new subdivision scheme which rotates the lattice and nevertheless allows a direct construction of the characteristic map. It is eigenanalysed with techniques introduced in a companion article and proved to define a C 1 2 -algorithm around a face-centre. This scheme generalises Loop's scheme, allowing the designer to choose between extraordinary vertices or faces in regard to the shape of the mesh, the location of the extraordinary elements, and the aimed limit shape.

This paper describes a method for adding surface details to existing CAD models. Our approach is based on truncated powers, which allows us to align the added details with curved knot lines on the surface. Additionally, (truncated) powers give us precise control over the continuity of the perturbed surface across the (curved) knot lines. Our representation is compatible with current CAD/CAM practise and standards, and we showcase it on several examples.

Among the bivariate subdivision schemes available, spline-based schemes, such as Catmull-Clark and Loop, are the most commonly used ones. These schemes have known continuity and can be evaluated at arbitrary parameter values. In this work, we develop a C1 spline-based scheme based on cubic half-box splines. Although the individual surface patches are triangular, the associated control net is three-valent and thus consists in general of mostly hexagons. In addition to introducing stencils that can be applied in extraordinary regions of the mesh, we also consider boundaries. Moreover, we show that the scheme exhibits ineffective eigenvectors. Finally, we briefly consider architectural geometry and isogeometric analysis as selected applications.

CAD models generally consist of multiple NURBS patches, both trimmed and untrimmed. There is a long-standing challenge that trimmed NURBS patches cause unavoidable gaps in the model. We address this by converting multiple NURBS patches to a single untrimmed NURBS-compatible subdivision surface in a three stage process. First, for each patch, we generate in domain space a quadrangulation that follows boundary edges of the patch and respects the knot spacings along edges. Second, the control points of the corresponding subdivision patch are computed in model space. Third, we merge the subdivision patches across their common boundaries to create a single subdivision surface. The converted model is gap-free and can maintain inter-patch continuity up to C2.

Traditionally, modelling using spline curves and surfaces is facilitated by control points. We propose to enhance the modelling process by the use of control vectors. This improves upon existing spline representations by providing such facilities as modelling with local (semi-sharp) creases, vanishing and diagonal features, and hierarchical editing. While our prime interest is in surfaces, most of the ideas are more simply described in the curve context. We demonstrate the advantages provided by control vectors on several curve and surface examples and explore avenues for future research on control vectors in the contexts of geometric modelling and finite element analysis based on splines, and B-splines and subdivision in particular.

Automatic feature recognition aids downstream processes such as engineering analysis and manufacturing planning. Not all features can be defined in advance; a declarative approach allows engineers to specify new features without having to design algorithms to find them. Naive translation of declarations leads to executable algorithms with high time complexity. Database queries are also expressed declaratively; there is a large literature on optimizing query plans for efficient execution of database queries. Our earlier work investigated applying such technology to feature recognition, using a testbed interfacing a database system (SQLite) to a CAD modeler (CADfix). Feature declarations were translated into SQL queries which are then executed. The current paper extends this approach, using the PostgreSQL database, and provides several new insights: (i) query optimization works quite differently in these two databases, (ii) with care, an approach to query translation can be devised that works well for both databases, and (iii) when finding various simple common features, linear time performance can be achieved with respect to model size, with acceptable times for real industrial models. Further results also show how (i) lazy evaluation can be used to reduce the work performed by the CAD modeler, and (ii) estimating the time taken to compute various geometric operations can further improve the query plan. Experimental results are presented to validate our main conclusions.

This paper introduces a novel method to convert trimmed NURBS surfaces to untrimmed subdivision surfaces with Bézier edge conditions. We take a NURBS surface and its trimming curves as input, from this we automatically compute a base mesh, the limit surface of which fits the trimmed NURBS surface to a specified tolerance. We first construct the topology of the base mesh by performing a cross-field based decomposition in parameter space. The number and positions of extraordinary vertices required to represent the trimmed shape can be automatically identified by smoothing a cross field bounded by the parametric trimming curves. After the topology construction, the control point positions in the base mesh are calculated based on the limit stencils of the subdivision scheme and constraints to achieve tangential continuity across the boundary. Our method provides the user with either an editable base mesh or a fine mesh whose limit surface approximates the input within a certain tolerance. By integrating the trimming curve as part of the desired limit surface boundary, our conversion can produce gap-free models. Moreover, since we use tangential continuity across the boundary between adjacent surfaces as constraints, the converted surfaces join with G1 continuity.

Abstract We deal with subdivision schemes based on arbitrary degree B‐splines. We focus on extraordinary knots which exhibit various levels of complexity in terms of both valency and multiplicity of knot lines emanating from such knots. The purpose of truncated multiple knot lines is to model creases which fair out. Our construction supports any degree and any knot line multiplicity and provides a modelling framework familiar to users used to B‐splines and NURBS systems.

Abstract We explore a method for generalising Pixar semi‐sharp creases from the univariate cubic case to arbitrary degree subdivision curves. Our approach is based on solving simple matrix equations. The resulting schemes allow for greater flexibility over existing methods, via control vectors. We demonstrate our results on several high‐degree univariate examples and explore analogous methods for subdivision surfaces.

Our goal is to find subdivision rules at creases in arbitrary degree subdivision for piece-wise polynomial curves, but without introducing new control points e.g. by knot insertion. Crease rules are well understood for low degree (cubic and lower) curves. We compare three main approaches: knot insertion, ghost points, and modifying subdivision rules. While knot insertion and ghost points work for arbitrary degrees for B-splines, these methods introduce unnecessary (ghost) control points. The situation is not so simple in modifying subdivision rules. Based on subdivision and subspace selection matrices, a novel approach to finding boundary and sharp subdivision rules that generalises to any degree is presented. Our approach leads to new higher-degree polynomial subdivision schemes with crease control without introducing new control points.

Abstract Given an n‐sided region bounded by a loop of n polylines, we present a general algorithm to fill such a region by a quad mesh suitable for a subdivision scheme. Typically, the approach consists of two phases: the topological phase and the geometrical phase. In the first part, the connectivity of the mesh is based on determining a partitioning of the region into rectangular subregions across which regular grid could be constructed. The geometrical phase generalizes discrete Coon's patches to position the vertices in the 3D space. The generated mesh could be taken as input to any quad‐based subdivision scheme, such as that of Catmull–Clark or Doo–Sabin to generate the corresponding limit surface. The goal of the algorithm is to generate smooth meshes with minimum number and less valence of extraordinary vertices deemed undesirable in such subdivision schemes.

We present a subdivision framework that adds extraordinary vertices to NURBS of arbitrarily high degree. The surfaces can represent any odd degree NURBS patch exactly. Our rules handle non-uniform knot vectors, and are not restricted to midpoint knot insertion. In the absence of multiple knots at extraordinary points, the limit surfaces have bounded curvature.

Abstract We present a method for tuning primal stationary subdivision schemes to give the best possible behaviour near extraordinary vertices with respect to curvature variation. Current schemes lead to a limit surface around extraordinary vertices for which the Gaussian curvature diverges, as demonstrated by Karčiauskas et al. [ KPR04 ]. Even when coefficients are chosen such that the subsubdominant eigenvalues, μ , equal the square of the subdominant eigenvalue, λ , of the subdivision matrix [ DS78 ] there is still variation in the curvature of the subdivision surface around the extraordinary vertex as shown in recent work by Peters and Reif [ PR04 ] illustrated by Karčiauskas et al. [ KPR04 ]. In our tuning method we optimise within the space of subdivision schemes with bounded curvature to minimise this variation in curvature around the extraordinary vertex. To demonstrate our method we present results for the Catmull‐Clark [ CC78 ], 4‐8 [ Vel01 , VZ01 ] and 4‐3 [ PS03 ] subdivision schemes. We compare our results to previous work on the tuning of these schemes and show that the coefficients derived with this method give a significantly smaller curvature variation around extraordinary vertices. Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling, I.3.6 [Computer Graphics]: Methodology and Techniques

We study the support of subdivision schemes: that is, the region of the subdivision surface that is affected by the displacement of a single control point. Our main results cover the regular case, where the mesh induces a regular Euclidean tesselation of the local parameter space. If n is the ratio of similarity between the tesselations at steps k and k − 1 of the refinement, we show that n determines the extent of this region and largely determines whether its boundary is polygonal or fractal. In particular if n = 2 (or n2 = 2 because we can always take double steps) the support is a convex polygon whose vertices can easily be determined. In other cases, whether the boundary of the support is fractal or not depends on whether there are sufficient points with non-zero coefficients in the edges of the convex hull of the mask. If there are enough points on every such edge, the support is again a convex polygon. If some edges have enough points and others do not, the boundary can consist of a fractal assembly of an unbounded number of line segments.

Abstract Current methods for building models using implicit volume techniques present problems defining accurate and controllable blend shapes between implicit primitives. We present new methods to extend the freedom and controllability of implicit volume modeling. The main idea is to use a free‐form curve to define the profile of the blend region between implicit primitives. The use of a free‐form implicit curve, controlled point‐by‐point in the Euclidean user space, allows us to group boolean composition operators with sharp transitions or smooth free‐form transitions in a single modeling metaphor. This idea is generalized for the creation, sculpting and manipulation of volume objects, while providing the user with simplicity, controllability and freedom in implicit modeling. ACM CSS: I.3.5 Computational Gemoetry and Object Modeling—Curve, surface, solid, and object representations

We present a data structure for three-dimensional fields C/sup 1/ continuous in the modelling space. Regular grids storing the field values discretely are combined with a triquadratic approximation filter to define volume objects. This association of a grid and an approximation/interpolation filter allows the field to be defined by a C/sup 1/ continuous real function and the surface to be directly visualised from its own equation. We show how accurate and high quality interactive visualisation is obtained during the modelling process, and we explain why the visualisation is faithful to the object definition. We also describe, as an example of application of our data structure, how advanced Boolean operators realised with soft or "functionally controlled" transitions are performed under the influence of an interactive modelling tool.

We describe a method for efficient calculation of coefficients for subdivision schemes. We work on the unit sphere and we express the z-coordinate of all the existing points as power series in the variable cos /spl theta/. Any linear combination of them is also a power series in cos /spl theta/ and, by solving a linear system, we determine the linear combination that will give the smoothest interpolation of the sphere at a particular point.

Doo-Sabin and Catmull-Clark subdivision surfaces are based on the notion of repeated knot insertion of uniform tensor product B-spline surfaces. This paper develops rules for non-uniform Doo-Sabin and Catmull-Clark surfaces that generalize non-uniform tensor product B-spline surfaces to arbitrary topologies. This added flexibility allows, among other things, the natural introduction of features such as cusps, creases, and darts, while elsewhere maintaining the same order of continuity as their uniform counterparts.

Djinn is an API for solid modelling which is defined in the language of point-sets and is thus independent of any particular modelling data-structure (e.g. boundary representations or CSG trees). In designing this API, several significant and interesting questions have arisen, including: the basic feasibility of the approach; deciding how to support cellular models; providing facilities for navigation without traditional data-structures; addressing the problems of 'tweaks' and blends; ensuring that labels are preserved under geometric operations; permitting regions in which changes to a model have taken place to be identified; coping with approximate models; deciding whether to support variational models; keeping sweeps and transforms within a reasonable domain; and providing facilities to handle the many types of parametric surface. These questions are not all fully answered, but progress continues towards a published interface and C++ language binding.

The concept of virtual input devices, enunciated by Wallace, has been the accepted basis for producing device-independent interactive graphics systems. It was used by GSPC for the Core System, and it underlies the draft international standard GKS.

Much effort has been spent in defining a standard call interface for a library of routines with display primitives embedded in a three-dimensional space. This paper argues that this is now an inappropriate target. There is too much diversity in the three-dimensional things we want to draw and in the kinds of picture we want to draw of them for any single standard to be both broadly acceptable and specifically useful.If the decision is made to go for a set of specialized standards for wire frame and for rendered graphics for data presentation, for sculptured surfaces and for object models, it becomes apparent that far more can be gained from a higher level standard, at the data presentation or object modelling level.In the object modelling community, at least, there is indeed work toward such a standard based on the IGES proposals. This has very few concepts in common with the graphics standard effort, and it is not clear at present what contribution the graphics community has to make in this area.The suggestion made here is that there may well be a number of paragraphs or sections common to more than one of the graphics-related and higher level standards. One such is the coordinate transformation (the dreaded 4 × 4 matrix). Its definition and its use both for modelling and viewing concepts are suggested which resolve some of the black art associated with transformation in the past. These could become the conceptual basis for a short simple standard in this area.

Summary Few of the arguments deployed above have been either device dependent or application area dependent. Even if further discussion leads to a resolution of these and future issues differnt from the author's, the case is made that a Transformations chapter could be written which would be naturally included in most application‐oriented 3D graphics standards.

article Free Access Share on Piecewise Quadratic Approximations on Triangles Authors: M. J. D. Powell Department of Applied Math and Theoretical Physics, University of Cambridge, Silver St., Cambridge CB3 9EW, England Department of Applied Math and Theoretical Physics, University of Cambridge, Silver St., Cambridge CB3 9EW, EnglandView Profile , M. A. Sabin Kongsberg, U.K., Box 105, Maidenhead, Berkshire, England Kongsberg, U.K., Box 105, Maidenhead, Berkshire, EnglandView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 3Issue 4Dec. 1977 pp 316–325https://doi.org/10.1145/355759.355761Published:01 December 1977Publication History 297citation1,661DownloadsMetricsTotal Citations297Total Downloads1,661Last 12 Months128Last 6 weeks17 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A representation of algebraic curves not widely known is shewn to be highly appropriate for calculating views of curves such as the intersections of general second order surfaces (quadrics), a problem approached by Luh and Krolak (1965), by Weiss (1966), and by Woon and Freeman (1971). By allowing the repetitive calculation to be performed in the picture plane it reduces the number of degrees of freedom involved from three to two. This representation gives an algorithm with rather different characteristics from the usual methods of drawing such curves, and these differences are discussed.

Abstract During the development of a portable problem‐oriented language processor a number of unexpected difficulties and incompatibilities in various FORTRAN compilers were encountered. These are related, and an approach which minimizes the problems suggested.