Publications and Presentations

We present a fast algorithm for converting quad meshes on the GPU to smooth surfaces. Meshes with 12,000 input quads, of which 60% have one or more non-4-valent vertices, are converted, evaluated and rendered with 9×9 resolution per quad at 50 frames per second. The conversion reproduces bi-cubic splines wherever possible and closely mimics the shape of the Catmull-Clark subdivision surface by c-patches where a vertex has a valence different from 4. The smooth surface is piecewise polynomial and has well-defined normals everywhere. The evaluation avoids pixel dropout.

We convert any quad manifold mesh into an at least C1 surface consisting of bi-cubic tensor-product splines with localized perturbations of degree bi-5 near non-4-valent vertices. There is one polynomial piece per quad facet, regardless of the valence of the vertices. Particular care is taken to derive simple formulas so that the surfaces are computed efficiently in parallel and match up precisely when computed independently on the GPU.

We complete and bring together two pairs of surface constructions that use polynomial pieces of degree (3,3) to associate a smooth surface with a mesh with polar structures. The two pairs complement each other in that one extends the Catmull-Clark subdivision-modeling paradigm, the other the PCCM NURBS patch approach to free-form modeling. In the process, we also show the curvature boundedness of certain singularly parameterized finite splines using a novel perspective.

The guided spline approach to surface construction separates surface design and surface representation by constructing local guide surfaces and sampling these by splines of moderate degree. This paper explains a construction based on tessellating the domain into V-shaped regions so that the resulting C^2 surfaces have G^2 transitions across the boundaries of the V-shapes and consist of tensor-product splines of degree (6,6) with patches of degree (4,4) forming a central cap.

Good surgical training depends greatly on case experiences that have been difficult to model in software since current training technology does not provide the flexibility to teach and practice uncommon procedures, or to adjust a training scenario on the fly. The TIPS kit aims to overcome these limitations. To the expert, it presents visual and haptic tools that make illustrating procedures easy and can model unusual anatomic variations. For a non-specialist, it provides a locally customized learning environment and repeated practice in a safe environment. We used the toolkit to illustrate removal of the adrenal gland.

Following (Karciauskas and Peters, "Concentric Tesselation Maps and Curvature Continuous Guided Surfaces") below, we analyze surfaces arising as an infinite sequence of guided C^2 surface rings. However, here we focus on constructions of too low a degree to be curvature continuous also at the extraordinary point. To characterize shape and smoothness of such surfaces, we track a sequence of quadratic functions anchored in a fixed coordinate system. These 'anchored osculating quadratics' are easily computed in terms of determinants of surface derivatives. Convergence of the sequence of quadratics certifies curvature continuity. Otherwise, the range of the curvatures of the limit quadratics gives a measure of deviation from curvature continuity.

By separating shape design from representation, the guided approach to surface construction (Karciauskas and Peters, "Concentric tessellation maps and guided surface rings") allows to routinely construct everywhere C^2 surfaces with (infinite) subdivision structure. This paper shows a finite guided C^2 surface construction of degree (6,6), albeit with many pieces, that preserves the good algebraic properties of the construction of k^th order smooth surfaces of least degree in (Peters, "C^2 free-form surfaces of degree (3,5)"), while avoiding geometric degeneration.

A multi-sided hole in a surface can be filled by a sequence of nested, smoothly joined surface rings. We show how to generate such a sequence so that (i) the resulting surface is C^2 (also in the limit), (ii) the rings consist of standard splines of moderate degree and (iii) the hole filling closely follows the shape of and replaces a guide surface whose good shape is desirable, but whose representation is undesirable. To preserve the shape, the guided rings sample position and higher-order derivatives of the guide surface at parameters defined and weighted by a concentric tesselating map. A concentric tesselating map maps the domains of n patches to an annulus in R^2 that joins smoothly with a λ-scaled copy of itself, 0 < λ < 1. The union of λ^m-scaled copies parametrizes a neighborhood of the origin and the map thereby relates the domains of the surface rings to that of the guide. The approach applies to and is implemented for a variety of splines and layouts including the three-direction box spline (with Δ-sprocket, e.g. Loop layout, at extraordinary points), tensor-product splines (quad-sprocket layout, e.g. Catmull-Clark), and polar layout. For different patch types and layout, the approach results in curvature continuous surfaces of degree less or equal 8, less or equal to (6,6), and as low as (4,3) if we allow geometric continuity.

We describe and analyze a subdivision scheme that generalizes bicubic spline subdivision to control nets with polar structure. Such control nets appear naturally for surfaces with the combinatorial structure of objects of revolution and at points of high valence when combined with Catmull-Clark subdivision. The resulting surfaces are $C^2$ except at isolated extraordinary points where the surface is $C^1$ and the curvature is bounded.

We describe a subdivision scheme that acts on control nodes that each carry a vector of values. Each vector defines partial derivatives, referred to as jets in the following and subdivision computes new jets from old jets. By default, the jets are automatically initialized from a design mesh. While the approach applies more generally, we consider here only a restricted class of design meshes, consisting of extraordinary nodes surrounded by triangles and otherwise quadrilaterals with interior nodes of valence four. This polar mesh structure is appropriate for surfaces with the combinatorial structure of objects of revolution and for high valences. The resulting surfaces are curvature continuous with good curvature distribution near extraordinary points. Near extraordinary points the surfaces are piecewise polynomial of degree (6,5), away they are standard bicubic splines.

To support real-time computation with large, possibly evolving point clouds and range data, we fit a trimmed uniform tensor-product spline function from one direction. The graph of this spline serves as a surrogate for the cloud, closely following the data safely in that, according to user choice, the data are always `below' or `above' when viewed in the fitting direction. That is, the point cloud is guaranteed to be completely covered from that direction and can be sandwiched between two matching spline surfaces if required. This yields both a data reduction since only the spline control points need to be further processed and defines a continuous surface in lieu of the isolated measurement points.

We describe the structure and general properties of surfaces with polar layout. Polar layout is particularly suitable for high valences and is, for example, generated by a new class of subdivision schemes. This note gives an high level view of surfaces with polar structure and does not analyze particular schemes.

For planar spline curves and bivariate box-spline functions, the cone of normals of a polynomial spline piece is enclosed by the cone of normals of its spline control polyhedron. This note collects some concrete examples to show that this is not true for subdivision surfaces, both at extraordinary points and in the regular, box-spline setting. A larger set, the cross products of families of control net edges, has to be considered.

Characterizing the linear and local linear independence of the functions that span a linear space is a key task if the space is to be used computationally. Given the control net, the spanning functions of one spatial coordinate of a generalized subdivision surface are called nodal functions. They are the limit, under subdivision, of associating the value one with one node and zero with all others. No characterization of independence of nodal functions has not been published to date, even for the two most popular generalized subdivision algorithms, Catmull-Clark subdivision and Loop's subdivision. This paper provides a road map for the verification of linear and local linear independence of generalized subdivision functions. It proves the conjectured global independence of the nodal functions of both algorithms; disproves local linear independence (for higher valences); and establishes linear independence on every surface region corresponding to a facet of the control net. Subtle exceptions, even to global independence, underscore the need for a detailed analysis to provide a sound basis for a number of recently developed computational approaches.

This paper summarizes the structure and analysis of subdivision surfaces and characterizes the inherent similarities and differences to parametric spline surfaces. Besides presenting well known results in a unified way, we introduce new ideas for analyzing schemes with a linearly dependent generating system, and a significantly simplified test for the injectivity of the characteristic map.

Modern geometric constraint solvers use combinatorial graph algorithms to recursively decompose the system of polynomial constraint equations into generically rigid subsystems and then solve the overall system by solving subsystems, from the leave nodes up, to be able to access any and all solutions. Since the overall algebraic complexity of the solution task is dominated by the size of the largest subsystem, such graph algorithms attempt to minimize the fan-in at each recombination stage. Recently, we found that, especially for 3D geometric constraint systems, a further graph-theoretic optimization of each rigid subsystem is both possible, and often necessary to solve wellconstrained systems: a minimum spanning tree characterizes what partial eliminations should be performed before a generic algebraic or numeric solver is called. The weights and therefore the elimination hierarchy defined by this minimum spanning tree computation depend crucially on the representation of the constraints. This paper presents a simple representation that turns many previously untractable systems into easy exercises. We trace a solution family for varying constraint data.

Automatically generated or laser-scanned surfaces typically exhibit large clusters with a uniform pattern. To take advantage of the regularity within clusters and still be able to edit without decompression, we developed a two-level data structure that uses an enumeration by orbits and an individually adjustable stencil to flexibly describe connectivity. The structure is concise for storing mesh connectivity; efficient for random access, interactive editing, and recursive refinement; and it is flexible by supporting a large assortment of connectity patterns and subdivision schemes.

The Flexible Subdivision Library, FSL, is a policy-based C++ template library for refining geometric meshes. The library is generic and only requires that the underlying mesh data structure provide Euler operations, iterators and circulators, and a point type. Any specific subdivision strategy is efficiently realized by a user-defined geometry policy.

By organizing the control mesh of subdivision in texture memory so that irregularities occur strictly inside independently refinable fragment mesh, all major features of subdivision algorithms can be realized in the framework of highly parallel stream processing. Our implementation of Catmull-Clark subdivision as a GPU kernel in programmable graphics hardware can model features like semi-smooth creases and global boundaries; and a simplified version achieves near-realtime depth-five re-evaluation of moderate-sized subdivision meshes. The approach is easily adapted to other refinement patterns, such as Loop, Doo-Sabin or sqrt3 and it allows for postprocessing with additional shaders.

Curvature continuous surfaces with subdivision structure are constructed by higher-order sampling of a piecewise polynomial guide surface, at positions defined and derivatives weighted by a special, scalable reparametrization. Two variants are developed. One variant applies to the conventional sprocket subdivision layout, say of Catmull-Clark subdivision, i.e. nested rings consisting of N copies of L-shaped segments with three patches. The curvature continuous surfaces are of degree (6,6). A second variant, called polar guided subdivision, is particularly suitable for high valences N and to cap cylindrical structures. It yields curvature continuous surfaces of degree (4,3). Additionally, we discuss a scheme that samples with increasing density to generate a $C^2$ surface of piecewise degree (3,3). Curvature continuity is verified by showing convergence of anchored osculation paraboloids.

This paper characterizes when the normals of a spline curve or spline surface lie in the more easily computed cone of the normals of the segments of the spline control net. (see also http://www.springer.de/comp/lncs/index.html c Springer-Verlag)

A sequence of mesh manipulations that preserves the Euler invariant is called an Euler encoding. We propose new, efficient Euler encodings for primal and dual mesh refinement. The implementations are analyzed and compared to array-based, connectivity-free refinement and to reconstruction of the refined mesh.

A tight estimate on the maximum distance between a subdivision surface and its linear approximation is introduced to guide adaptive subdivision with guaranteed accuracy.

Bezier or B-spline control meshes are quintessential CAGD tools because they link piecewise linear and curved geometry by providing a linear, refinable approximation that exaggerates features and is, up to reparametrization, in 1-1 correspondence with the curved geometry. However, for a given budget of line segments, Bezier and B-spline control meshes are usually far from the 'nearest' piecewise linear approximant to the curved geometry. Subdividable Linear Efficient Function Enclosures, short SLEFEs (pronounced like sleeves), aim at sandwiching the curved geometry as tightly as possible. This paper illustrates how to derive SLEFEs, lists the literature on SLEFEs, discusses SLEFEs for rational functions and tensor-products and analyzes the improvement of SLEFEs under refinement. The average of the upper and lower SLEFE bounds is called mid-structure. Mid-structures come close to being the 'nearest' piecewise linear approximant while retaining the 1-1 correspondence and the computational efficiency of control meshes.

4-3 direction subdivision combines quad and triangle meshes. On quad submeshes it applies a 4-direction alternative to Catmull-Clark subdivision and on triangle submeshes a modification of Loop's scheme. Remarkably, 4-3 surfaces can be proven to be C1 and have bounded curvature everywhere. In regular mesh regions, they are C2 and correspond to two closely-related box-splines of degree four. The box-spline in quad regions has a smaller stencil than Catmull-Clark and defines the unique scheme with a 3 by 3 stencil that can model constant features without ripples both aligned with the quad grid and diagonal to it. From a theoretical point of view, 4-3 subdivision near extraordinary points is remarkable in that the eigenstructure of the local subdivision matrix is easy to determine and a complete analysis is possible. Without tweaking the rules artificially to force a specific spectrum, the leading eigenvalues ordered by modulus of all local subdivision matrices are 1, 1/2, 1/2, 1/4 where the multiplicity of the eigenvalue 1/4 depends on the valence of the extraordinary point and the number of quads surrounding it. This implies equal refinement of the mesh, regardless of the number of neighbors of a mesh node.

Accurate and robust interference detection and ray-tracing of subdivision surfaces requires safe linear approximations. Approximation of the limit surface by the subdivided control polyhedron can be both inaccurate and, due to the exponential growth of the number of facets, costly. This paper shows how a standard intersection hierarchy, such as an OBB tree, can be made safe and efficient for subdivision surface interference detection. The key is to construct, on the fly, optimally placed facets, whose spherical offsets tightly enclose the limit surface. The spherically offset facets can be locally subdivided and they can be efficiently intersected based on standard triangle-triangle interference detection.

An algorithm is presented for approximating a rational multi-sided M-patch by a C^2 spline surface. The motivation is that the multi-sided patch can be assumed to have good shape but is in nonstandard representation or of too high a degree. The algorithm generates a finite approximation of the M-patch, by a sequence of patches of bidegree (5,5) capped off by patches of bidegree (11,11) surrounding the extraordinary point. The philosophy of the approach is (i) that intricate reparametrizations are permissible if they improve the surface parametrization since they can be precomputed and thereby do not reduce the time efficiency at runtime; and (ii) that high patch degree is acceptable if the shape is controlled by a guiding patch.

Given a polygonal channel between obstacles in the plane or in space, we present an algorithm for generating a parametric spline curve with few pieces that traverses the channel and stays inside. While the problem without emphasis on few pieces has trivial solutions, the problem for a limited budget of pieces represents a nonlinear and continuous (`infinite') feasibility problem. Using tight, two-sided, piecewise linear bounds on the potential solution curves, we reformulate the problem as a finite, linear feasibility problem whose solution, by standard linear programming techniques, is a solution of the channel fitting problem. The algorithm allows the user to specify the degree and smoothness of the solution curve and to minimize an objective function, for example, to approximately minimize the curvature of the spline. We describe in detail how to formulate and solve the problem, as well as the problem of fitting parallel curves, for a spline in Bernstein-Bezier form.

Given a planar spline curve and local tolerances, a matched pair of polygons is computed that encloses the curve and whose width (distance between corresponding break points) is below the tolerances. This is the simplest instance of a subdividable linear efficient variety enclosure, short sleve. We develop general criteria, that certify correctness of a global, polygonal enclosure built from a sequence of individual bounding boxes by extending and intersecting their edges. These criteria prove correctness of the sleve construction.

We provide asymptotic expansions for the fundamental forms, the Weingarten map, the principal curvatures, and the principal directions of surfaces generated by linear stationary subdivision schemes. Further, we define the central surface. The central surface is a spline ring that captures basic shape properties of the surface in the vicinity of an extraordinary vertex. Relating the shape properties to the spectrum of the subdivision matrix via the discrete Fourier transform yields conditions for the construction of high-quality subdivision schemes. In particular, the subsub-dominant eigenvalue should be triple and correspond to the Fourier blocks with indices 0,2 and n-2 of the subdivision matrix.

For subdivision surfaces, it is important to characterize local shape near flat spots and points where the surface is not twice continuously differentiable. Applying general principles derived in "[Peters, Reif] Shape Characterization... -- Basic Principles", this paper characterizes shape near such points for the subdivision schemes devised by Catmull and Clark and by Loop. For generic input data, both schemes fail to converge to the hyperbolic or elliptic limit shape suggested by the geometry of the input mesh: the limit shape is a function of the valence of the extraordinary node rather than the mesh geometry. We characterize the meshes for which the schemes behave as expected and indicate modifications of the schemes that prevent convergence to the wrong shape. We also introduce a type of chart that, for a specific scheme, can help a designer to detect early when a mesh will lead to undesirable curvature behavior.

We show how a future graphics processor unit (GPU), enhanced with random read and write to video memory, can represent, refine and adjust complex meshes arising in modeling, simulation and animation. To leverage SIMD parallelism, a general model based on the mesh atlas is developed and a particular implementation without adjacency pointers is proposed in which primal, binary refinement of, possibly mixed, quadrilateral and triangular meshes of arbitrary topological genus, as well as their traversal is supported by user-transparent programmable graphics hardware. Adjustment, such as subdivision smoothing rules, is realized as user programmable mesh shader routines. Attributes are generic and can be defined in the graphics application by binding them to one of several general addressing mechanisms.

This paper surveys a new, computationally efficient technique for linearizing curved spline geometry, bounding such geometry from one side and constructing curved spline geometry that stays to one side of a barrier or inside a given channel. Combined with a narrow error bound, these reapproximations tightly couple linear and nonlinear representations and allow them to be substituted when reasoning about the other. For example, a subdividable linear efficient variety enclosure (SLEVE, pronounced like Steve) of a composite spline surface is a pair of matched triangulations that sandwich a surface and may be used for interference checks. The average of the SLEVE components, the mid-structure, is a good max-norm linearization and, similar to a control polytope, has a well-defined, associated curved geometry representation. Finally, the ability to fit paths through given channels or keep surfaces near but outside forbidden regions, allows extending many techniques of linear computational geometry to the curved, nonlinear realm.

Subdividable linear efficient function enclosures (Slefes) provide, at low cost, a piecewise linear pair of upper and lower bounds f^+, f^-, that sandwich a function f on a given interval: f^- <= f <= f^+. In practice, these bounds are observed to be very tight. This paper addresses the question just how close to optimal, in the max-norm, the slefe construction actually is. Specifically, we compare the width (f^+)-(f^-) of the slefe to the narrowest possible piecewise linear enclosure of f when f is a univariate cubic polynomial.

This paper surveys the key achievements and outstanding challenges of constructing smooth surfaces for geometric design. The focus here is on explicit methods in parametric form. In particular, recent insights into the curvature magnitude and distribution of surfaces generated by existing algorithms, based on generalized subdivision and on splines, are illustrated and corresponding research questions are formulated. These challenges motivate the search for alternative approaches to multi-sided patch constructions.

Optimized Refinable Surface Enclosures are tight, two-sided enclosures of composite spline surfaces. This paper shows how to construct the two hulls whose matched triangle pairs sandwich a given nonlinear, curved surface consisting of tensor-product Bezier patches. The hulls are cheap to compute with linear effort per patch. The width of the enclosure, i,e. the distance between inner and outer hull can be easily measured because the maxima are taken on at the vertices. The width shrinks quadratically under subdivision (uniform knot insertion). Uses of surface envelopes are easier point classification and intersection testing and an improved rule for approximately rendering curved surfaces as triangulations with a known error bound.

This chapter covers geometric continuity with emphasis on a constructive definition for piecewise parametrized surfaces. The examples in Section 1 show the need for a notion of continuity different from the direct matching of Taylor expansions used to define the continuity of piecewise functions. Section 2 defines geometric continuity for parametric curves, and for surfaces, first along edges, then around points, and finally for a whole complex of patches which is called a $G^k$ free-form surface spline. Here $G^k$ characterizes a relation between specific maps while $C^k$ continuity is a property of the resulting surface. The composition constraint on reparametrizations and the vertex-enclosure constraints are highlighted. Section 3 covers alternative definitions based on geometric invariants, global and regional reparametrization and briefly discusses geometric continuity in the context of implicit representations and generalized subdivision. Section 4 explains the generic construction of $G^k$ free-form surface splines and points to some low degree constructions. The chapter closes with a listing of additional literature.   --- corrections: p 7 Fig 5: "p_1" lower left should be "p_2"   --- p 8 Def 2.2: A subdomain is a simple...; ...maps points outside \Delta_1 to points inside \Delta_2   --- p 9 Fig 6: rotate the domain by 90 degrees so that E is aligned with the x-axis.   --- p 10 l-10: "u" in 2 by 1 matrix should be "t"

This paper presents a technique for modeling curvature continuous free-form surfaces of unrestricted patch layout from patches of maximal degree $d+2$,$d>0$ by $3$ with the flexibility of degree $d$, $C^2$ splines at extraordinary points

For a stationary, affine invariant, symmetric, linear and local subdivision scheme that is $C^2$ apart from the extraordinary point the curvature is bounded if the square of the subdominant eigenvalue equals the subsubdominant eigenvalue. This paper gives a technique for quickly establishing an interval to which the curvature is confined at the extraordinary point. The approach factors the work into precomputed intervals that depend only on the scheme and a mesh-specific component. In many cases the intervals are tight enough to be used as a test of shape-faithfulness of the given subdivision scheme; i.e.\ if the limit surface in the neighborhood of the extraordinary point of the subdivision scheme is consistent with the geometry implied by the input mesh.

To improve the visual quality of existing triangle-based art in real-time entertainment, such as computer games, we propose replacing flat triangles with curved patches and higher-order normal variation. At the hardware level, based only on the three vertices and three vertex normals of a given flat triangle, we substitute the geometry of a three-sided cubic B\'ezier patch for the triangle's flat geometry, and a quadratically varying normal for Gouraud shading. These curved point-normal triangles, or PN triangles, require minimal or no change to existing authoring tools and hardware designs while providing a smoother, though not necessarily everywhere tangent continuous, silhouette and more organic shapes.

(Old title: Envelopes for tensor product polynomials) An an optimized refinable enclosure is a two-sided approximation of a uni- or multivariate function b in B by a pair of typically simpler functions b-, b+ in H not equal to B such that b- <= b <= b+ over the domain of of interest. Enclosures are optimized by minimizing the width max_U b+ - b- and refined by enlarging the space H. This paper develops a framework for efficiently computing enclosures for multivariate polynomials and, in particular, derives piecewise bilinear enclosures for bivariate polynomials in tensor-product B'ezier form. Runtime computation of enclosures consists of looking up s < dim B pre-optimized enclosures and linearly combining them with the second differences of b. The width of these enclosures scales by a factor 1/4 under midpoint subdivision.

This paper presents a simple algorithm for associating a smooth, low degree polynomial surface with triangulations whose extraordinary mesh nodes are separated by sufficiently many ordinary, 6-valent mesh nodes. Output surfaces are at least tangent continuous and are $C^2$ sufficiently far away from extraordinary mesh nodes; they consist of three-sided B\'ezier patches of degree 4. In particular, the algorithm can be used to skin a mesh generated by a few steps of Loop's generalization of three-direction box-spline subdivision.

Together with "Smooth Patching of Refined Triangulations", this TR supercedes "Patching Loop Meshes". This technical report supplements the paper ``Smooth Patching of Refined Triangulations'' That paper gives formulas for smoothly filling $n$-sided holes in a 3-direction box-spline (Loop) surface at extraordinary mesh nodes with polynomial pieces of degree 4. If $n\ne 6$ and $n$ is even then alternating sums of the radial neighbors of the extraordinary mesh node have to vanish. This technical report gives simple constructions of degree 5 and of degree 6 that do not require the alternating sums to vanish.

A simple, explicit transformation creates maximally large, smoothly joining Nurbs patches of order 4 from Catmull-Clark subdivision meshes. It can be applied after any of the first subdivision steps and creates patches that are maximally large in the sense that one patch corresponds to one quadrilateral facet of the initial, coarsest quadrilateral mesh before subdivision. The patches join $C^2$ almost everywhere and with tangent continuity in the immediate neighborhood of extraordinary mesh nodes, matching the global smoothness of Catmull-Clark limit surfaces. The transitions between patches are almost all parametric. Named after the title, the PCCM transformation integrates naturally with array-based implementations of subdivision surfaces. You may want to change the basic algorithm to adjust the normal, the construction for higher-order saddle points of even valence and blend ratios (smoothed creases or creased smoothings). See the Siggraph talk slides for remarks -- if enough people ask I will write these points up formally.) See also http://www.cise.ufl.edu/research/SurfLab/pccm_demo/index.html

A version of PCCM (without blend ratios) see also http://www.cise.ufl.edu/research/SurfLab/pccm_demo/index.html

This note discusses some finer points of Patching \CC\ Meshes pointed out in the Siggraph talk. The modifications have been implemented and examples are posted at http://www.cise.ufl.edu/research/SurfLab/pccm_demo/index.html. (1) The normal of the PCCM surface at an extraordinary point is free to choose. In particular, we may choose it as the normal of the \CC\ limit surface in the extraordinary point. We give the corresponding formula below. (2) The perturbation of the mesh for higher-order saddle points of even valence can lead to undesirable flatness of the surface in the neighborhood of the extraordinary point. There is a remedy. (3) Pulling and pushing control meshes after a subdivision step allows the distribution of curvature e.g.\ creating sharper features. This may be viewed,as is common in computer aided design, as adjusting the blend radius between primary surfaces. This note shows how to include blend ratios, i.e.\ control of the sharpness of transitions, into the PCCM framework.

By explicitly deriving the curvature of subdivision surfaces in the extraordinary points, we give an alternative, more direct account of the criteria necessary and sufficient for achieving curvature continuity than earlier approaches that locally parametrize the surface by eigenfunctions. The approach allows us to rederive and thus survey the important lower bound results on piecewise polynomial subdivision surfaces by Prautzsch, Reif, Sabin and Zorin, as well as explain the beauty of curvature continuous constructions like Prautzsch's. The parametrization neutral perspective gives also additional insights into the inherent constraints and stiffness of subdivision surfaces.

A general framework for comparing objects commonly used to represent nonlinear geometry with simpler, related objects, most notably their control polygon, is provided. The framework enables the efficient computation of bounds on the distance between the nonlinear geometry and the simpler objects and the computation of envelopes of nonlinear geometry. The framework is used to compute envelopes for univariate splines, the four point subdivision scheme, tensor product polynomials and Bezier triangles. The envelopes are used to approximate solutions to continuously constrained optimization problems.

An explicit spline representation of smooth free-form surfaces is combined with a hierarchy of meshes to form the basis of an interactive sculpting environment. The environment offers localized hierarchical modeling at different levels of detail, direct surface manipulation, change of connectivity for extrusion and to form holes and bridges, and built-in tangent continuity across the surface where wanted. The free-form surface is represented and can be exported either in NURBS form or as cubic triangular B\'ezier patches. Key characteristics of the approach are: (1) mesh pieces and surface pieces are related by strictly local averaging rules; (2) refinement rules depend only on direct, coarser-level ancestors and not on adjacent submeshes or patches; (3) submeshes at different levels look alike. The underlying data structure is a single winged-edge structure with additional pointers to support the hierarchy. Multiply refined regions may be directly adjacent to unrefined regions, and mesh fragments at different levels of refinement can be connected.

Given a polynomial $p$ in $d$ variables and of degree $n$ we want to find a best $L_2$-approximation over the $d$-simplex from polynomials of degree $m$ less than $n$. This problem is shown to be equivalent to the problem of finding the best Euclidean approximation of the \BB coefficients of $p$ from the space of degree-raised \BB coefficients of polynomials of degree $m$.

The problem, given a polynomial $p$ of degree $d+1$ find a best 2-norm approximation over the unit interval from polynomials of degree $d$, is shown to be equivalent to the problem of finding the best $l^2$ approximation of the vector of \BB coefficients of $p$ from the vector of \BB coefficients of once degree-raised polynomials of degree $d$. Moreover, analogous to repeated degree-reduction in $L^2$, $l^2$ degree reduction one step at a time from degree $n$ to degree $d

We derive an efficiently computable, tight bound on the distance between a uniform spline and its B--Spline control polygon in terms of the second differences of the control points. The bound yields a piecewise linear envelope enclosing the spline and its control polygon. For quadratic and cubic splines, the envelope has minimal possible width at the break points and for all degrees the maximal width shrinks by a factor of $4$ under uniform refinement. We extend the construction to tight envelopes for parametric curves.

We show how to efficiently smooth a polygon with an approximating spline that stays to one side of the polygon. We also show how to find a smooth spline path between two polygons that form a channel. Problems of this type arise in many physical motion planning tasks where not only forbidden regions have to be avoided but also a smooth traversal of the motion path is required. Both algorithms are based on a new tight and efficiently computable bound on the distance of a spline from its control polygon and employ only standard linear and quadratic programming techniques.

A sharp bound on the distance between a spline and its B-spline control polygon is derived. The bound yields a piecewise linear envelope enclosing spline and polygon. This envelope is particularly simple for uniform splines and splines in Bernstein-B\'ezier form and shrinks by a factor of~4 for each uniform subdivision step. The envelope can be easily and efficiently implemented due to its explicit and constructive nature.

We derive a new, efficiently computable bound on the distance between a uniform spline and its B--Spline control polygon in terms of the second differences of the control points. The bound is piecewise linear and sharp for quadratic and cubic splines and decreases by a factor of 4 under uniform refinement. Using this bound, we describe a simple algorithm for enveloping parametric curves.

On the construction of high-quality surfaces...

First International Workshop on Algebraic Geometry and Approximation Theory, April 11 and April 12, 2008 Towson University Towson, Maryland, USA

We show how a future graphics processor unit (GPU), enhanced with random read and write to video memory, can represent, refine and adjust complex meshes arising in modeling, simulation and animation.

see paper

By explicitly deriving the curvature of subdivision surfaces in the extraordinary points, we give an alternative, more direct account of the criteria necessary and sufficient for achieving curvature continuity than earlier approaches that locally parametrize the surface by eigenfunctions. The approach allows us to rederive and thus survey the important lower bound results on piecewise polynomial subdivision surfaces by Prautzsch, Reif and Sabin, as well as explain the beauty of curvature continuous constructions like Prautzsch's. The parametrization neutral perspective gives also additional insights into the inherent constraints and stiffness of subdivision surfaces. The talk gives an example of a ring of subeigenfunctions of degree bi-4 (and no less) such that the determinant of the Jacobian of the subeigenfunctions is of degree bi-5, i.e. lower than the expected degree bi-7.

For any nondecreasing knot sequence, we show how to tightly bound the distance between a spline and its B-spline control polygon. The bound is piecewise linear, and is computed in terms of second differences of the control points and an explicitly computable, in practice small, multiplier. The bound is taken on for a family of splines of the given degree. The bound is particularly simple for uniform splines and splines in Bernstein-B\'ezier form. In these cases the bound decreases by a factor of 4 for each uniform subdivision step. The bound can be easily and efficiently implemented due to its explicit and constructive nature.

A new, efficiently computable bound on the distance between a non-uniform B--spline and its control polygon is introduced. The bound is used to construct coarse, Hölder-type envelopes (H) and tight, modified minmax envelopes (M). Examples compare envelopes of type (H), (M) and the convex hull.

We show how to efficiently smooth a polygon with an approximating spline that stays to one side of the polygon. We also show how to find a smooth spline path between two polygons that form a channel. Problems of this type arise in many physical motion planning tasks where not only forbidden regions have to be avoided but also a smooth traversal of the motion path is required. Both algorithms are based on a new tight and efficiently computable bound on the distance of a spline from its control polygon and employ only standard linear and quadratic programming techniques.

see paper