SurfLab Papers

Publication and Presentations

Jump to year: 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 | 2009 | 2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2002 | 2001 | 2000 | 1999 | before 1999

For material based upon work supported by the National Science Foundation any opinions, findings, and conclusions or recommendations expressed are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
2016
abstract
Polycube G-splines form a 2-manifold guided by a mesh of quadrilateral faces such that at most six quads meet at each vertex. In particular, this replicates the layout of the quad faces of a polycube. Polycube G-splines are piecewise bicubic and polycube Gspline surfaces are almost everywhere tangent-continuous ($G^1$) based on rational linear reparameterization. They can be constructed in two different ways. One construction interprets the quad mesh vertices in the fashion of $C^2$ bicubic splines – this provides for good shape; the other interprets the $2\times2$ inner B´ezier coefficients of each bicubic as $C^1$ bicubic B-spline coefficients – this offers four degrees of freedom per patch and enables adaptive refinement so that the resulting G-spline spaces are nested, i.e. any G-spline surface can be exactly re-represented at different levels of refinement.
abstract
Convolving the output of Discontinuous Galerkin computations with symmetric Smoothness-Increasing Accuracy-Conserving (SIAC) filters can improve both smoothness and accuracy. To extend convolution to the boundaries, several one-sided spline filters have recently been developed. This paper interprets these filters as instances of a general class of position-dependent (PSIAC) spline filters that can have non-uniform knot sequences and skip B-splines of the sequence. PSIAC filters with rational knot sequences have rational coefficients. For prototype knot sequences, such as integer sequences that may have repeated entries, PSIAC filters can be expressed in symbolic form. Based on the insight that filters for shifted or scaled knot sequences are easily derived by non-uniform scaling of one prototype filter, simplifies to forming a scalar product of a short vector with the local output data. Restating one-sided filters in this form improves both stability and efficiency compared to their original formulation via numerical integration. PSIAC filtering is demonstrated for several established and one new boundary filter.
abstract
Building on a result of U. Reif on removable singularities, we construct $C^1$ bi-3 splines that may include irregular points where less or more than four tensor-product patches meet. The resulting space complements PHT splines, is refinable and the refined spaces are nested, preserving for example surfaces constructed from the splines. As in the regular case, each quadrilateral has four degrees of freedom, each associated with one spline and the splines are linearly independent. Examples of use for surface construction and isogeometric analysis are provided.
abstract
Scaffold surfaces bound geometric structures that have a dual characterization as a curve network and a solid. A subset of scaffold surfaces can be modeled with minimal single-valence (MSV) meshes, i.e.\ meshes consisting of vertices of a single irregular valence $n$ two of which are separated by exactly one regular, 4-valent vertex. We present an algorithm for constructing piecewise bi-quartic surfaces that join with curvature continuity to form scaffold surfaces for MSV meshes, for $n=5,\ldots,10$. Additionally, for sphere-like meshes, we exhibit bi-quartic curvature continuous surfaces with polar parameterization.
abstract
Enabling surgeon-educators to themselves create virtual reality (VR) training units promises greater variety, specialization and relevance of the units. This paper describes a software bridge that semi-automates the scene-generation cycle, a key bottleneck in authoring, modeling and developing VR units. Augmenting an open-source modeling environment with physical behavior attachment and collision specifications yields single-click testing of the full force-feedback enabled anatomical scene.
2015
abstract
This paper addresses a gap in the arsenal of curvature continuous tensor-product spline constructions: an algorithm is provided to fill $n$-sided holes in $C^2$ bi-3 spline surfaces using $n$ patches of degree bi-6. Numerous experiments illustrate good highlight line and curvature distribution on the resulting surfaces. The functional $\mathcal{F}_k$ in (14) should read $(\partial^i_s\partial^j_tf)^2$ not $(\partial^i_s f\partial^j_tf)^2$; and in (3) $\partial_u f \partial_v f$ should be $\partial_u\partial_v f$
abstract
Quad meshes can be interpreted as tensor-product spline control meshes as long as they form a regular grid, locally. We present a new option for complementing bi-3 splines by bi-4 splines near irregularities in the mesh layout, where less or more than four quadrilaterals join. These new generalized surface and IGA (isogeometric analysis) elements have as their degrees of freedom the vertices of the irregular quad mesh. From a geometric design point of view, the new construction distinguishes itself from earlier work by a notably better distribution of highlight lines. From the IGA point of view, increased smoothness and reproduction at the irregular point yield fast convergence. The functional $\mathcal{F}_k$ in Sec 2.3 should read $(\partial^i_s\partial^j_tf)^2$ not $(\partial^i_s f\partial^j_tf)^2$
abstract
The discontinuous Galerkin (dG) method outputs a sequence of polynomial pieces. Post-processing the sequence by Smoothness-Increasing Accuracy-Conserving (SIAC) convolution not only increases the smoothness of the sequence but can also improve its accuracy and yield superconvergence. SIAC convolution is considered optimal if the SIAC kernels, in the form of a linear combination of B-splines of degree $d$, reproduce polynomials of degree $2d$. This paper derives simple formulas for computing the optimal SIAC spline coefficients for the general case including non-uniform knots.
abstract
We explore a class of polynomial tensor-product spline surfaces on 3-6 polyhedra, whose vertices have valence $n=3$ or $n=6$. This restriction makes it possible to exclusively use rational linear transition maps between the pieces: transitions between the bi-cubic tensor-product spline pieces are either $C^1$ or they are $G^1$ (tangent continuous) based on one single rational linear reparameterization. The simplicity of the transition functions yields simple formulas for a hierarchy of splines on subdivided 3-6 polyhedra.
abstract
`Class A surface' is a term in the automotive design industry, describing spline surfaces with aesthetic, non-oscillating highlight lines. Tensor-product B-splines of degree bi-3 (bicubic) are routinely used to generate smooth design surfaces and are often the de facto standard for downstream processing. To bridge the gap, this paper explores and gives a concrete suggestion, how to achieve good highlight line distributions for irregular bi-3 tensor-product patch layout by allowing, along some seams, a slight mismatch of normals below the industry-accepted tolerance of one tenth of a degree. Near the irregularities, the solution can be viewed as transforming a higher-degree, high-quality formally smooth surface into a bi-3 spline surface with few pieces, sacrificing formal smoothness but qualitatively retaining the shape.
abstract
For many design applications, where multiple primary surface pieces meet, the distribution of curvature is more important than formally achieving exact curvature continuity. For parametric spline surfaces, when constructing a multi-sided surface cap, we demonstrate a strong link between the uniform variation of the re-parameterization between (boundary) data of the joining pieces and a desirable distribution of curvature. We illustrate this interdependence between parameterization quality and surface quality by developing a $G^1$ bi-quintic surface cap consisting of $n$ pieces that smoothly fills holes in a piecewise bi-cubic tensor-product spline complex. These bi-5 surface caps have arguably better shape than higher-degree, formally curvature continuous alternatives. The functional $\mathcal{F}_k$ in (1) should read $(\partial^i_s\partial^j_tf)^2$
abstract
Geometrically continuous ($G^k$) constructions naturally yield families of finite elements for isogeometric analysis (IGA) that are $C^k$ also for non-tensor-product layout. This paper describes and analyzes one such concrete $C^1$ geometrically generalized IGA element (short: gIGA element) that generalizes bi-quadratic splines to quad meshes with irregularities. The new gIGA element is based on a recently-developed $G^1$ surface construction that recommends itself by its a B-spline-like control net, low (least) polynomial degree, good shape properties and reproduction of quadratics at irregular (extraordinary) points. Remarkably, for Poisson's equation on the disk using interior vertices of valence 3 and symmetric layout, we observe $O(h^3)$ convergence in the $L^\infty$ norm for this family of elements. Numerical experiments confirm the elements to be effective for solving the trivariate Poisson equation on the solid cylinder, deformations thereof (a turbine blade), modeling and computing geodesics on smooth free-form surfaces via the heat equation, for solving the biharmonic equation on the disk and for Koiter-type thin-shell analysis.
2014
abstract
Biquadratic (bi-2) splines are the simplest choice for converting a regular quad meshes into smooth tensor-product spline surfaces. Existing methods for blending three, five or more such bi-2 spline surfaces using surface caps consisting of pieces of low polynomial degree suffer from artifacts ranging from flatness to oscillations. The new construction, based on reparameterization of the bi-2 spline data, yields well-distributed highlight lines for a range of challenging test data. The construction uses n pieces of bi-3 when n=3,5 or n pieces of degree bi-4 when n is larger than 5 and applies both to primal (Catmull-Clark-like) and dual (Doo-Sabin-like) input layouts. The functional $\mathcal{F}_k$ on page 3 should read $(\partial^i_s\partial^j_tf)^2$ not $(\partial^i_s f\partial^j_tf)^2$
abstract
Recently, it was shown that a bi-cubic patch complex with n-sided holes can be completed into a curvature-continuous surface by n-sided caps of degree bi-5 that offer good and flexible shape. This paper further explores the space of n-sided caps of degree bi-5 but focuses on functionals to set degrees of freedom and to optimally propagate and average out curvature from the bi-cubic complex. The functional $\mathcal{F}_k$ in (1) should read $(\partial^i_s\partial^j_tf)^2$ not $(\partial^i_s f\partial^j_tf)^2$
abstract
Shape artifacts, especially for convex input polyhedra, make Doo and Sabin's generalization of bi-quadratic (bi-2) subdivision surfaces unattractive for general design. Rather than tuning the eigenstructure of the subdivision matrix, we improve shape by adding a point and enriching the refinement rules. Adding a guiding point can also yield a polar bi-2 subdivision algorithm. Both the augmented and the polar bi-2 subdivision are complemented by a new primal bi-2 subdivision scheme. All surfaces are $C^1$ and can be combined.
abstract
This paper outlines and qualitatively compares implementations of seven different methods for solving Poisson's equation on the disk. The methods include two classical finite elements, a cotan-formula-based discrete differential geometry approach and four iso-geometric constructions. The comparison reveals numerical convergence rates and, particularly for iso-geometric constructions based on Catmull-Clark elements, the need to carefully choose quadrature formulas. The seven methods include two that are new to iso-geometric analysis. Both new methods yield $O(h^3)$ convergence in the $L^2$ norm, also when points are included where $n\ne 4$ pieces meet. One construction is based on a polar, singular parameterization; the other is a $G^1$ tensor-product construction.
abstract
$G^k$ (geometrically continuous surface) constructions were developed to create surfaces that are smooth also at irregular points where, in a quad-mesh, three or more than four elements come together. Isogeometric elements were developed to unify the representation of geometry and of engineering analysis. We show how matched $G^k$ constructions for geometry and analysis automatically yield $C^k$ isogeometric elements. This provides a formal framework for the existing and any future isogeometric elements based on geometric continuity.
abstract
Current strategies for real-time rendering of trimmed spline surfaces re-approximate the data, pre-process extensively or introduce visual artifacts. This paper presents a new approach to rendering trimmed spline surfaces that guarantees visual accuracy efficiently, even under interactive adjustment of trim curves and spline surfaces. The technique achieves robustness and speed by discretizing at a near-minimal correct resolution based on a tight, low-cost estimate of adaptive domain griding. The algorithm is highly parallel, with each trim curve writing itself into a slim lookup table. Each surface fragment then makes its trim decision robustly by comparing its parameters against the sorted table entries. Adding the table-and-test to the rendering pass of a modern graphics pipeline achieves anti-aliased sub-pixel accuracy at high render-speed, while using little additional memory and fragment shader effort, even during interactive trim manipulation.
abstract
Splines can be constructed by convolving the indicator function of a cell whose shifts tessellate Rn. This paper presents simple, geometric criteria that imply that, for regular shift-invariant tessellations, only a small subset of such spline families yield nested spaces: primarily the well-known tensor-product and box splines. Among the many nonrefinable constructions are hex-splines and their generalization to the Voronoi cells of non-Cartesian root lattices.
2013
abstract
This paper gives a construction to complete, at extraordinary points, an otherwise bi-cubic spline surface - so that the resulting surface is curvature continuous everywhere. To fill the n-sided gap in the bi-cubic surface, a cap is constructed from n spline patches, each consisting of 2x2 pieces of polynomial degree bi-5. Particular care is taken to continue the curvature distribution from the bicubic boundary of the gap into the cap, and gently average out such propagated curvature in the neighborhood of the extraordinary point. The functional $\mathcal{F}_k$ in (16) should read $(\partial^i_s\partial^j_tf)^2$ not $(\partial^i_s f\partial^j_tf)^2$
abstract
The definition of a B-spline is extended to unordered knot sequences. The added flexibility implies that the resulting piecewise polynomials, named U-splines, can be negative and locally linearly dependent. It is therefore remarkable that linear combinations of U-splines retain many properties of splines in B-spline form including smoothness, polynomial reproduction, and evaluation by recurrence.
abstract
This paper presents a non-uniform cubic C2 spline framework that unifies three scenarios for incorporating data from basic curves, such as spirals and conics. In the first scenario, no parameterization of the basic curves is available, only well-spaced samples; in the second, a parameterization is available but cannot be used directly in a spline framework; only in the third scenario can pieces of basic curves be exactly re-represented and included into the spline. In all three cases the output is a cubic C2 spline suitable for standard CAD downstream processing. A key challenge in constructing the spline is to cope with transitions in the presence of strongly differing curvatures. Here we introduce a new form of curvature-sensitive averaging.
Swarm-NG: A CUDA library for Parallel n-body Integrations with focus on simulations of planetary systems
Saleh Dindar, Eric B. Ford, Mario Juric, Young In Yeo, Jianwei Gao, Aaron C. Boley, Benjamin Nelson, Jörg Peters
New Astronomy, Volumes 23-24, October 2013, Pages 6-18
DOI: 10.1016/j.newast.2013.01.002
arXiv:1208.1157v1 [astro-ph.EP].
abstract

We present Swarm-NG, a C++ library for the efficient direct integration of many n-body systems using highly-parallel Graphics Processing Unit (GPU), such as NVIDIA's Tesla T10 and M2070 GPUs. While previous studies have demonstrated the benefit of GPUs for n-body simulations with thousands to millions of bodies, Swarm-NG focuses on many few-body systems, e.g., thousands of systems with 3...15 bodies each, as is typical for the study of planetary systems. Swarm-NG parallelizes the simulation, including both the numerical integration of the equations of motion and the evaluation of forces using NVIDIA's "Compute Unified Device Architecture" (CUDA) on the GPU. Swarm-NG includes optimized implementations of 4th order time-symmetrized Hermite integration and mixed variable symplectic integration, as well as several sample codes for other algorithms to illustrate how non-CUDA-savvy users may themselves introduce customized integrators into the Swarm-NG framework. To optimize performance, we analyze the effect of GPU-specific parameters on performance under double precision.

Applications of Swarm-NG include studying the late stages of planet formation, testing the stability of planetary systems and evaluating the goodness-of-fit between many planetary system models and observations of extrasolar planet host stars (e.g., radial velocity, astrometry, transit timing). While Swarm-NG focuses on the parallel integration of many planetary systems,the underlying integrators could be applied to a wide variety of problems that require repeatedly integrating a set of ordinary differential equations many times using different initial conditions and/or parameter values.

2012
abstract
This paper presents new univariate linear non-uniform interpolatory subdivision constructions that yield high smoothness, C3 and C4, and are based on least-degree spline interpolants. This approach ismotivated by evidence, partly presented here, that constructions based on high-degree local interpolants fail to yield satisfactory shape, especially for sparse, non-uniform samples. While this improves on earlier schemes, a broad consideration of alternatives yields two technically simpler constructions that result in comparable shape and smoothness: careful pre-processing of sparse, non-uniform samples and interlaced fitting with splines of increasing smoothness.We briefly compare these solutions to recent non-linear interpolatory subdivision schemes
abstract
To efficiently animate and render large models consisting of bi-cubic patches in real time, we split the rendering into pose-dependent, view-dependent (Compute-Shader supported) and pure rendering passes. This split avoids recomputation of curved patches from control structures and minimizes overhead due to data transfer - and it integrates nicely with a technique to determine a nearminimal tessellation of the patches while guaranteeing sub-pixel accuracy. Our DX11 implementation generates and accurately renders 141,000 animated bicubic patches of a scene in the movie "Elephant's Dream" at more than 300 frames per second on a 1440x900 screen using one GTX 580 card.
abstract
We show how to automatically join, into one unified spline surface, C2 tensor-product bi-cubic NURBS and G2 bi-cubic rational splines. The G2 splines are capable of exactly representing basic shapes such as (pieces of) quadrics and surfaces of revolution, including tori and cyclides. The main challenge is to transition between the differing forms of continuity. We transform the G2 splines to splines that are C2 in homogeneous space. This yields Hermite data for a transitional strip of tensor-product splines of degree (6, 5) that guarantees overall curvature continuity. We also explain the simpler G1 to C1 transition. Key to the constructions is the C2 parameterization of circles in homogeneous space.
abstract
Changing variables is a useful tool that appears in many guises in computer graphics and geometric modeling. Changing the variables allows us to change the way we traverse a curve or surface, change their derivatives or place or interpret textures and other properties associated with them. In calculus, changing variables miraculously converts hard integration problems into simple standard ones and in algebra, seemingly hard root fnding problems turn into an easy exercises. Even change of coordinates can be interpreted as a change of variables, albeit linear and therefore not our focus below.
abstract
We present a framework for deriving non-uniform interpolatory subdivision algorithms closely related to non-uniform spline interpolants. Families of symmetric non-uniform interpolatory 2n-point schemes of smoothness Cn-1 are presented for n=2,3,4 and even higher order, as well as a variety of non-uniform 6-point schemes with C3 continuity.
Curve networks compatible with G2 surfacing
T. Hermann, Jörg Peters and T. Strotman
Computer Aided Geometric Design, vol. 29, no. 5, pp. 219230, 2012
abstract
Prescribing a network of curves to be interpolated by a surface model is a standard approach in geometric design. Where n curves meet, even when they afford a common normal direction, they need to satisfy an algebraic condition, called the vertex enclosure constraint, to allow for an interpolating piecewise polynomial C1 surface. Here we prove the existence of an additional, more subtle constraint that governs the admissibility of curve networks for G2 interpolation. Additionally, analogous to the first-order case but using the Monge representation of surfaces, we give a sufficient geometric, G2 Euler condition on the curve network. When satisfied, this condition guarantees existence of an interpolating surface.
abstract
A curved or higher-order surface, such as spline patch or a Bézier patch, is rendered pixel-accurate if it displays neither polyhedral artifacts nor parametric distortion. This paper shows how to set the evaluation density for a patch just finely enough so that parametric surfaces render pixel-accurate in the standard graphics pipeline. The approach uses tight estimates, not of the size under screen projection, but of the variance under screen projection between the exact surface and its triangulation. An implementation, using the GPU tessellation engine, runs at interactive rates comparable to standard rendering.
2011
abstract
A polar configuration is a triangle fan in a quad-dominant mesh; it allows for many mesh lines to join at a single polar vertex. This paper shows how a single tensor-product spline of degree (3, 6) can cap a polar configuration with a C2 surface. By design, this C2 polar spline joins C2 with surrounding bi-3 tensor-product splines and thereby complements algorithms that smoothly cap star-like, multi-sided regions.
abstract
The paper develops a rational bi-cubic G2 (curvature continuous) analogue of the non-uniform polynomial C2 cubic B-spline paradigm. These rational splines can exactly reproduce parts of multiple basic shapes, such as cyclides and quadrics, in one by default smoothly-connected structure. The versatility of this new tool for processing exact geometry is illustrated by conceptual design from basic shapes. typo (found by WeiHua Tong) page 2, col 2, $c_3 := w^{i-1}_1 W_i w^i_1$ should be $c_3 := w^{i-1}_2 W_i w^i_1$.
abstract
The promise of modeling by subdivision is to have simple rules that avoid cumbersome stitching-together of pieces. However, already in one variable, exactly reproducing a variety of basic shapes, such as conics and spirals, leads to non-stationary rules that are no longer as simple; and combining these pieces within the same curve by one set of rules is challenging. Moreover, basis func- tions, that allow reading off smoothness and computing curvature, are typically not available. Mimicking subdivision of splines with non-uniform knots allows us to combine the basic shapes. And to analyze non-uniform subdivision in general, the literature proposes interpolating the sequence of subdivision control points by circles. This defines a notion of discrete curvature for interpolatory subdivi- sion. However, we show that this discrete curvature generically yields misleading information for non-interpolatory subdivision and typically does not converge, not even for non-uniform spline subdivision. Analyzing the causes yields three general approaches for solving or at least mitigating the problem: equalizing pa- rameterizations, sampling subsequences and a new skip-interpolating subdivision approach.
abstract
We develop a class of rational, G2 -connected splines of degree 3 that allow modeling multiple basic shapes, such as segments of conics and cir- cle arcs in particular, in one structure. This can be used, for example, to have portions of a control polygon exactly reproduce segments of the shapes while other portions blend between these primary shapes. We also show how to reparameterize the splines to obtain parametrically C2 transitions. [errata: p.12 p^k_{i-1} should be p^k_i]
abstract
To broaden the use of simulation for teaching, in particular of new procedures and of low-volume procedures, we propose an environment and workflow that allows surgeon-educators create teaching modules. Our challenge is to make the simulation tools accessible, modifiable and sharable by users with moderate computer and VR experience. Our contribution is a workflow that promotes consistency between instructional material and measured criteria and makes the authoring process efficient, both for the surgeon, and for computer scientists supporting the simulation environment.
abstract
We develop a rational biquadratic $G^1$ analogue of the non-uniform $C^1$ B-spline paradigm. These $G^1$ splines can exactly reproduce parts of multiple basic shapes, such as cyclides and quadrics, and combine them into one smoothly-connected structure. This enables a design process that starts with basic shapes, re-represents them in spline form and uses the spline form to provide shape handles for localized free-form modification that can preserve, in the large, the initial fair, basic shapes.
abstract
Converting a quadrilateral input mesh into a C1 surface with one bi-3 tensorproduct spline patch per facet is a classical challenge. We give explicit local averaging formulas for the spline control points. Where the quadrilateral mesh is not regular, the patches have two internal double knots, the least number and multiplicity to always allow for an unbiased G1 construction.
2010
abstract
We exhibit the essentially unique projective linear (rational linear) reparameterization for constructing $C^s$ surfaces of genus $g>0$, from tensor-product splines. Conversely, for quadrilaterals and isolated vertices of valence 8, we show constructively for s = 1, 2 that this map yields a projective linear spline space for surfaces of genus greater or equal to 1. This establishes the reparametrization to be the simplest possible transition map.
abstract
There is an essentially unique projective linear (rational linear) reparameterization for constructing $C^s$ surfaces from tensor-product splines. Conversely, for quadrilaterals and isolated vertices of valence 8, constructions for $s=1,2$ with this map yield a projective linear spline space for surfaces.
abstract
Sampling and reconstruction of generic multivariate functions is more efficient on non-Cartesian root lattices, such as the BCC (Body-Centered Cubic) lattice, than on the Cartesian lattice. We introduce a new nxn generator matrix A* that enables, in n variables, efficient reconstruction on the non-Cartesian root lattice An* by a symmetric box-spline family Mr*. A2* is the hexagonal lattice and A3* is the BCC lattice. We point out the similarities and differences of Mr* with respect to the popular Cartesian-shifted box-spline family Mr, document the main properties of Mr* and the partition induced by its knot planes and construct, in n variables, the optimal quasi-interpolant of M2*.
abstract
When interpolating a network of curves to create a C1 surface from smooth patches, the network has to satisfy an algebraic condition, called the vertex enclosure constraint. We show the existence of an additional constraint that governs the admissibility of curve networks for G2 interpolation by smooth patches.
abstract
Polynomial equation systems arising from real applications often have associated combinatorial information, expressible as graphs and underlying matroids. To simplify the system and improve its numerical robustness before attempting to solve it with numeric algebraic techniques, solvers can employ graph algorithms to extract substructures sat- isfying or optimizing various combinatorial properties. When there are underlying matroids, these algorithms can be greedy and efficient. In practice, correct and effective merging of the outputs of different graph algorithms to simultaneously satisfy their goals is a key challenge. This paper merges and improves two highly effective but separate graph-based algorithms that preprocess systems for resolving the relative position and orientation of a collection of incident rigid bodies. Such collections naturally arise in many situations, for example in the recombination of decomposed large geometric constraint systems. Each algorithm selects a subset of incidences, one to optimize algebraic complexity of a parametrized system, the other to obtain a well-formed system that is robust against numerical errors. Both algorithms are greedy and can be proven correct by revealing underlying matroids. The challenge is that the output of the first algorithm is not guaranteed to be extensible to a well-formed system, while the output of the second may not have optimal algebraic complexity. Here we show how to reconcile the two algorithms by revealing well-behaved maps between the associated matroids.
abstract
Graphs of pairwise incidences between collections of rigid bodies occur in many practical applications and give rise to large algebraic systems for which all solutions have to be found. Such pairwise incidences have explicit, simple and rational parametrizations that, in principle, allow us to partially resolve these systems and arrive at a reduced, parametrized system in terms of the rational parameters. However, the choice of incidences and the partial order of incidence resolution strongly determine the algebraic complexity of the reduced, parametrized system, measured primarily in the number of variables and secondarily in the degree of the equations. Using a pairwise overlap graph, we introduce a combinatorial class of incidence tree parametrizations for a collection of rigid bodies. Minimizing the algebraic complexity over this class reduces to a purely combinatorial optimization problem that is a special case of the set cover problem. We quantify the exact improvement of algebraic complexity obtained by optimization and illustrate the improvement by examples that can not be solved without optimization. Since incidence trees represent only a subclass of possible parametrizations, we characterize when optimizing over this class is useful. That is, we show what properties of standard collections of rigid bodies are necessary for an optimal incidence tree to have minimal algebraic complexity. For a standard collections of rigid bodies, the optimal incidence tree parameterization offers lower algebraic complexity than any other known parameterization.
2009
abstract
We assemble triangular patches of total degree at most eight to form a curvature continuous surface. The construction illustrates how separation of local shape from representation and formal continuity yields an effective construction paradigm in partly underconstrained scenarios. The approach localizes the technical challenges and applies the spline approach, i.e. keeping the degree fixed but increasing the number of pieces, to deal with increased complexity when many patches join at a central point.
abstract
This paper derives strong relations that boundary curves of a smooth complex of patches have to obey when the patches are computed by local averaging. These relations restrict the choice of reparameterizations for geometric continuity. In particular, when one bicubic tensor-product B-spline patch is associated with each facet of a quadrilateral mesh with n-valent vertices and we do not want segments of the boundary curves forced to be linear, then the relations dictate the minimal number and multiplicity of knots: For general data, the tensor-product spline patches must have at least two internal double knots per edge to be able to model a G1-conneced complex of C1 splines. This lower bound on the complexity of any construction is proven to be sharp by suitably interpreting an existing surface construction. That is, we have a tight bound on the complexity of smoothing quad meshes with bicubic tensor-product B-spline patches.
  • Lemma 5, proof: planarity means that the curve c(u) lies in the tangent plane since n c(u) = taylor( nc'(0), nc''(0), nc'''(0)) = 0.
  • Lemma 5, proof: saddle is symmetric means the surface is symmetric with respect to the plane through n and c'(0).
  • Lemma 6, proof, last statement: the degree of the derivative along boundary divided by gamma must be greater or equal 1.
  • Thm 1, proof, line 4: (17), respectively (15),
abstract
A key problem when interpolating a network of curves occurs at vertices: an algebraic condition called the vertex enclosure constraint must hold wherever an even number of curves meet. This paper recasts the constraint in terms of the local geometry of the curve network. This allows formulating a new geometric constraint, related to Euler s Theorem on local curvature, that implies the vertex enclosure constraint and is equivalent to it where four curve segments meet without forming an X.
abstract
Lens-shaped surfaces (with vertices of valence 2) arise for example in automatic quad-remeshing. Applying standard Catmull-Clark subdivision rules to a vertex of valence 2, however, does not yield a C1 surface in the limit. When correcting this flaw by adjusting the vertex rule, we discover a variant whose characteristic ring is z2. Since this conformal ring is of degree bi-2 rather than bi-3, it allows constructing a subdivision algorithm that works directly on the control net and generates C2 limit surfaces of degree bi-4 for lens-shaped surfaces. To further improve shape, a number of re-meshing and re-construction options are discussed indicating that a careful approach pays off. Finally, we point out the analogy between characteristic configurations and the conformal maps z4/n, cos z and ez. ("The original publication is available at www.springerlink.com" doi 10.1007/s00607-009-0060-9 )
Efficient substitutes for subdivision surfaces SiGGRAPH course notes, 2009
This is part 1 of 4, part 2 by T Ni and I Castano, NVIDIA Corporation, part 3 by J Mitchell, Valve, part 4 by P Schneider, V Verma, ILM.
abstract
This course provides an introduction to Approximate Subdivision Surfaces, an overview of the most recent theoretical results and their implementations on the current and next-generation GPUs, and a demonstration of these techniques and their applications in the game and movie industries.
abstract
Popular subdivision algorithms like Catmull-Clark and Loop are C2 almost everywhere, but suffer from shape artifacts and reduced smoothness exactly near the so-called "extraordinary vertices" that motivate their use. Subdivision theory explains that inherently, for standard stationary subdivision algorithms, curvature-continuity and the ability to model all quadratic shapes requires a degree of at least bi-6. The existence of a simple-to-implement C2 subdivision algorithm generating surfaces of good shape and piecewise degree bi-3 in the polar setting is therefore a welcome surprise. This paper presents such an algorithm, the underlying insights, and a detailed analysis. In bi-3 C2 polar subdivision the weights depend, as in standard schemes, only on the valence, but the valence at one central polar vertex increases to match Catmull-Clark-refinement.
abstract
For use in real-time applications, we present a fast algorithm for converting a quad mesh to a smooth, piecewise polynomial surface on the Graphics Processing Unit (GPU). The surface has well-defined normals everywhere and closely mimics the shape of CatmullClark subdivision surfaces. It consists of bicubic splines wherever possible, and a new class of patchesc-patcheswhere a vertex has a valence different from 4. The algorithm fits well into parallel streams so that meshes with 12,000 input quads, of which 60% have one or more non-4-valent vertices, are converted, evaluated and rendered with 9 x 9 resolution per quad at 50 frames per second. The GPU computations are ordered so that evaluation avoids pixel dropout.
abstract
We separate the conceptual design and the representation of high quality surfaces by prescribing local shape via guide surfaces and then sampling these guides with a finite number of tensor-product patches. The paper develops a family of algorithms that allow trading polynomial degree for smoothness near the extraordinary points where more or fewer than four tensor-product patches meet. A key contribution are rules for a capping of a multi-sided hole by a small number of polynomial patches. The construction of highest quality creates first a G1 cap of patches of degree (6, 6) and then perturbs it to yield an exact G2 cap of degree (8, 8). Since this perturbation is so small that its effect is typically not perceptible even in curvature display, the unperturbed surface of degree (6, 6) is an excellent alternative. Reducing the degree of the rings to (5, 5), respectively (4, 4), by choice of a different parameterization, increases the number of G1 transition curves within the cap but does not alter the shape appreciably. The functional $\mathcal{F}_k$ in Lemma 2 should read $(\partial^i_s\partial^j_tf)^2$ not $(\partial^i_s f\partial^j_tf)^2$
abstract
We describe a fully interactive, low-overhead and robust peritoneum representation allowing for probing and cutting. The peritoneum implementation has been tested within a surgical illustration environment.
2008
Finite curvature continuous polar patchworks IMA Conference on the Mathematics of Surfaces, 2009
abstract
We present an algorithm for completing a C2 surface of up to degree bi-6 by capping an n-sided hole with polar layout. The cap consists of n tensor-product patches, each of degree 6 in the periodic and degree 5 in the radial direction. To match the polar layout, one edge of these patches is collapsed. We explore and compare with alternative constructions, based on more pieces or using total-degree, triangular patches.
abstract
Graphs of pairwise incidences between collections of rigid bodies occur in many practical applications and give rise to large algebraic systems for which all solu- tions have to be found. Such pairwise incidences have explicit, simple and rational parametrizations that, in principle, allow us to partially resolve these systems and arrive at a reduced, parametrized system in terms of the rational parameters. How- ever, the choice of incidences and the partial order of incidence resolution strongly determine the algebraic complexity of the reduced, parametrized system measured primarily in the number of variables and secondarily in the degree of the equations. Using a pairwise overlap graph, we introduce a combinatorial class of incidence tree parametrizations for a collection of rigid bodies. Minimizing the algebraic com- plexity over this class reduces to a purely combinatorial optimization problem that is a special case of the set cover problem. We quantify the exact improvement of algebraic complexity obtained by optimization and illustrate the improvement by examples that can not be solved without optimization. Since incidence trees represent only a subclass of possible parametrizations, we characterize when optimizing over this class is useful. That is, we show what prop- erties of standard collections of rigid bodies are necessary for an optimal incidence tree to have minimal algebraic complexity. For a standard collections of rigid bodies, the optimal incidence tree parameterization offers lower algebraic complexity than any other known parameterization.
Subdivision Surfaces Springer: Geometry and Computing, Vol. 3,
2008
about this book
Since their first appearance in 1974, subdivision algorithms for generating surfaces of arbitrary topology have gained widespread popularity in computer graphics and are being evaluated in engineering applications. This development was complemented by ongoing efforts to develop appropriate mathematical tools for a thorough analysis, and today, many of the fascinating properties of subdivision are well understood.

This book summarizes the current knowledge on the subject. It contains both meanwhile classical results as well as brand-new, unpublished material, such as a new framework for constructing C²-algorithms.

The focus of the book is on the development of a comprehensive mathematical theory, and less on algorithmic aspects. It is intended to serve researchers and engineers - both new to the beauty of the subject - as well as experts, academic teachers and graduate students or, in short, anybody who is interested in the foundations of this flourishing branch of applied geometry.

abstract
We introduce a non-uniform subdivision algorithm that partitions the neighborhood of an extraordinary point in the ratio σ:1-σ, where σ ; in (0,1). We call σ the speed of the non-uniform subdivision and verify C1 continuity of the limit surface. For σ=1/2, the Catmull-Clark algorithm is recovered. Other speeds are useful to vary the contraction near extraordinary points.
abstract
For standard subdivision algorithms and generic input data, near an extraordinary point the distance from the limit surface to the control polyhedron after m subdivision steps is shown to decay dominated by the mth power of the subsubdominant eigenvalue. Conversely, for Loop subdivision we exhibit generic input data so that the Hausdorff distance at the mth step is greater or equal to the mth power of the subsubdominant eigenvalue.
In practice, it is important to closely predict the number of subdivision steps necessary so that the control polyhedron approximates the surface to within a fixed distance. Based on the above analysis, two such predictions are evaluated. The first is a popular heuristic that analyzes the distance only for control points and not for the facets of the control polyhedron. For a set of test polyhedra this prediction is remarkably close to the distance verified by a posteriori measurement. However, a concrete example shows that the prediction is not safe but can prescribe too few steps. The second approach is to first locally, per vertex neighborhood, subdivide the input net and then apply tabulated bounds on the eigenfunctions of the subdivision algorithm. This yields always safe predictions that are within one step for a set of test surface. ("The original publication is available through doi:10.1016/j.jat.2008.10.012)
abstract
This paper gives an overview of two recent techniques for high-quality surface constructions: polar layout and the guided approach. We demonstrate the chal- lenge of high-quality surface construction by examples since the notion of surface quality lacks an overarching theory. A key ingredient of high-quality constructions is a good layout of the surface pieces. Polar layout simplifies design and is natural where a high number of pieces meet. A second ingredient is separation of shape design from surface representation by creating an initial guide shape and leverag- ing classical approximation-theoretic tools to construct a final surface compatible with industry standards, either as a finite number of polynomial patches or as a subdivision process. An example construction generating guided C2 surfaces from patches of degree bi-3 highlights the power of the approach.
abstract
Determining the least m such that one m×m bi-cubic macro-patch per quadrilateral offers enough degrees of freedom to construct a smooth surface by local operations regardless of the vertex valences is of fundamental interest; and it is of interest for computer graphics due to the impending ability of GPUs to adaptively evaluate polynomial patches at animation speeds.
We constructively show that m = 3 suffices, show that m = 2 is unlikely to always allow for a localized construction if each macro-patch is internally parametrically C 1 and that a single patch per quad is incompatible with a localized construction. We do not specify the GPU implementation.
abstract
We introduce and analyze an efficient reconstruction algorithm for FCC-sampled data. The reconstruction is based on the 6-direction box spline that is naturally associated with the FCC lattice and shares the continuity and approximation order of the triquadratic B-spline. We observe less aliasing for generic level sets and derive special techniques to attain the higher evaluation efficiency promised by the lower degree and smaller stencil-size of the 6-direction box spline over the triquadratic B-spline.
» The work was supported in part by NSF grant CCF-0728797
abstract
Due to their highly symmetric structure, in arbitrary dimensions root lattices are considered as efficient sampling lattices for reconstructing isotropic signals. Among the root lattices the Cartesian lattice is widely used since it naturally matches the Cartesian coordinates. However, in low dimensions, non-Cartesian root lattices have been shown to be more efficient sampling lattices.
For reconstruction we turn to a specific class of multivariate splines. Multivariate splines have played an important role in approximation theory. In particular, box-splines, a generalization of univariate uniform B-splines to multiple variables, can be used to approximate continuous fields sampled on the Cartesian lattice in arbitrary dimensions. Box-splines on non-Cartesian lattices have been used limited to at most dimension three.
This dissertation investigates symmetric box-splines as reconstruction filters on root lattices (including the Cartesian lattice) in arbitrary dimensions. These box-splines are constructed by leveraging the directions inherent in each lattice. For each box-spline, its degree, continuity and the linear independence of the sequence of its shifts are established. Quasi-interpolants for quick approximation of continuous fields are derived. We show that some of the box-splines agree with known constructions in low dimensions.
For fast and exact evaluation, we show that and how the splines can be efficiently evaluated via their BB(Bernstein-Bézier)-forms. This relies on a technique to compute their exact (rational) BB-coefficients. As an application, volumetric data reconstruction on the FCC (Face-Centered Cubic) lattice is implemented and compared with reconstruction on the Cartesian lattice.
abstract
To repeatedly evaluate linear combinations of box-splines in a fast and stable way, in particular along knot planes, the box-spline is converted to and tabulated as piecewise polynomial in BB-form (Bernstein- Bézier-form). We show that the BB-coefficients can be derived and stored as integers plus a rational scale factor and derive a hash table for efficiently accessing the polynomial pieces. This preprocessing, the resulting evaluation algorithm and use in a widely-used ray-tracing package are illustrated for splines based on two trivariate box-splines: the 7-directional box-spline on the Cartesian lattice and the 6-directional box-spline on the Face-Centered Cubic lattice. The work was supported in part by NSF grant CCF-0728797.
»MATLAB® package & movies download page
  • In equation (7), ‘-1’ in M-1 should not be in bold face.
  • In equation (7), all three ks should be italic: k.
  • In the proof of Lemma 1, 2nd paragraph 3rd line, ζ' (lower zeta prime) and Ξ' (upper xi prime) both should be the same symbol Z (upper zeta).
abstract
Polyhedral meshes consisting of triangles, quads, and pentagons and polar configurations cover all major sampling and modeling scenarios. We give an algorithm for efficient local, parallel conversion of such meshes to an everywhere smooth surface consisting of low-degree polynomial pieces. Quadrilateral facets with 4-valent vertices are ‘regular’ and are mapped to bi-cubic patches so that adjacent bi-cubics join as for cubic tensor-product splines. The algorithm can be implemented in the vertex and geometry shaders of the GPU pipeline and does not use the fragment shader. Its implementation in DirectX 10 achieves conversion plus rendering at 659 frames per second with 42.5 million triangles per second on input of a model of 1,300 facets of which 60% are not regular. The work was supported in part by NSF grant CCF-0728797
abstract
Surface constructions of polynomial degree (3,3) come in four flavours that complement each other: one pair extends the subdivision paradigm, the other the NURBS patch approach to free-form modeling.

The first pair, Catmull-Clark and Polar subdivision generalize bi-cubic subdivision: While Catmull-Clark subdivision is more suitable where few facets join, Polar subdivision nicely models regions where many facets join as when capping extruded features. We show how to easily combine (the meshes of) these two generalizations of bi-cubic spline subdivision.

The second pair of surface constructions with a finite number of patches consists of PCCM for layouts where Catmull-Clark would apply and a singularly parameterized NURBS patch for polar layout. A novel analysis shows the latter to yield a $C^1$ surface with bounded curvatures.
GPU Smoothing of Quad Meshes IEEE International Conference on Shape Modeling and Applications (SMI) Stony Brook University, June 4 - 6, 2008
Errata: Table 1 formula for v was corrected. See corrected Myles, Ni, Peters '08 above.
abstract
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. The work was supported in part by NSF grant CCF-0728797.
abstract
We convert any quad manifold mesh into an at least 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. The work was supported in part by NSF grant CCF-0728797.
abstract
Modeling soft tissue for surgery simulation is a challenging task due to the complex way that the tissue can deform and interact with virtual surgical tools manipulated by user. One soft tissue that is ubiquitous but often not modeled, is fatty tissue. Here we present a novel fatty tissue model based on the mass-spring system on the Graphics Processing Unit (GPU) as part of our Toolkit for Illustration of Procedures in Surgery (TIPS). The user can interact with the fatty tissue in real time via a handheld haptic stylus that represents a virtual surgical tool in TIPS environment. The currently available interactions are palpation, grasp, and cut.
abstract
Following (Karciauskas and Peters, “Concentric Tesselation Maps and Curvature Continuous Guided Surfaces”) below, we analyze surfaces arising as an infinite sequence of guided 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.
2007
abstract
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.
abstract
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.
abstract
We have developed a computer based simulation process which allows a surgical expert to create a customized operative environment. This virtual environment, the Toolkit for Illustration of Procedures in Surgery (3D TIPS), is deployed on a low-cost computer system and requires minimal training for the programmer. The learner can be engaged in training immediately and the educator can modify the system and annotate the procedure to highlight specific points using video clips, operative images, and the like. A laparoscopic adrenalectomy is presented as a proof of concept in the accompanying article.
abstract
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 surfaces have 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. The functional $\mathcal{F}_k$ page 7 (1) should read $(\partial^i_s\partial^j_tf)^2$ not $(\partial^i_s f\partial^j_tf)^2$
abstract
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 (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 ℜ² 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.
abstract
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 except at isolated extraordinary points where the surface is and the curvature is bounded.
Surfaces with Polar Structure Computing, Special issue on Geometric Modeling (Dagstuhl 2005), 79, 2, 309-315 Apr. 2007
abstract
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.
abstract
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.
2006
abstract
The rapid development and deployment of novel laparoscopic instruments present the surgical educator and trainee with a significant challenge. Several useful instruments have been particularly difficult to teach the novice. We have developed a platform that allows the combination of the actual instrument handle with a virtual re-creation of the instrument tip. We chose the Autosuture™ Endo Stitch™ device as the prototypical instrument because it satisfies our subjective experience of “useful, but hard to teach.” A software package was developed to support the re-creation of the needle and suture that accompany the device. The apparatus has haptic capabilities and collision detection so that the needle driver is “aware” of suture and instrument contact. The developed virtual environment allows re-creation of the necessary motion to simulate the instrument, the trainee can use the actual instrument handle, and the system can be altered to accommodate other instruments.
abstract
Real-time, plausible visual and haptic feedback of deformable objects without shape artifacts is important in surgical simulation environments to avoid distracting the user. We propose to leverage highly parallel stream processing, available on the newest generation graphics cards, to increase the level of both visual and haptic fidelity. We implemented this as part of the University of Florida's haptic surgical authoring kit.
abstract
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 surfaces with (infinite) subdivision structure. This paper shows a finite guided 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, “ free-form surfaces of degree (3,5)“), while avoiding geometric degeneration. The functional $\mathcal{F}_k$ on page 7 (c) should read $(\partial^i_s\partial^j_tf)^2$ not $(\partial^i_s f\partial^j_tf)^2$
abstract
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.
abstract
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.
abstract
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.
2005
abstract
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.
abstract
In “A realtime GPU subdivision kernel” (SIGGRAPH 2005), Shiue et al. showed that, in principle, all major features of subdivision algorithms can be realized in the framework of highly parallel stream processing. Shiue et al. tested the approach by implementing Catmull-Clark subdivision, with semi-smooth creases and global boundaries, in programmable graphics hardware, at near realtime speed. Here, we report on the challenges when adapting the approach to Loop subdivision.
Pattern-based Data Structure for Manipulating Meshes with Regular Regions
Le-Jeng Shiue and Jörg Peters
Graphics Interface, Victoria, British Columbia, Canada, May 9 - 11, 2005
abstract
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.
abstract
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.
A Realtime GPU Subdivision Kernel
Le-Jeng Shiue , Ian Jones and Jörg Peters
SIGGRAPH, Los Angeles, CA, July 31 - August 4, 2005
abstract
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 √3 and it allows for postprocessing with additional shaders.
abstract
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 surface of piecewise degree (3,3). Curvature continuity is verified by showing convergence of anchored osculation paraboloids.
On Normals and Control Nets Mathematics of Surfaces XI, 11th IMA International Conference, Loughborough, UK, September 5 - 7, 2005
abstract
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.
abstract
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.
abstract
A tight estimate on the maximum distance between a subdivision surface and its linear approximation is introduced to guide adaptive subdivision with guaranteed accuracy.
2004
abstract
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.
abstract
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 and have bounded curvature everywhere. In regular mesh regions, they are 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, ½, ½, ¼ where the multiplicity of the eigenvalue ¼ 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.
abstract
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.
abstract
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-Bézier form. Marcelo Siqueira noticed: Sec 4.1 (1st para) should read $D_i b^p_\mu$ (subscripted). (published: second variable misses a "b") Page 146 (1st col Fig 10): switched $e_s^p$ and $e_{s-1}^p$ in the right drawing. Constraint (3c): should it be $\text{normal}_j^p$ (with $j$ one of $c-1$ or $c+1$) or $\text{normal}_c^p$ in the inequality? (cf (3a) and (3b)) (2) counting: open and closed curve differ (3c) counting: should be (or no 2^\text{dim}?) $K := 2^\text{dim} 2 (n_e + 1)$ inequalities per e-piece where the middle 2 refers to the number of caps per tunnel? This would yield $KN$ inequalities total.
abstract
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.
Marcelo Siqueira found the following (non-lethal) typos: Fig. 13(b) certificate (2) may not be satisfied. Fig. 14(b) caption should read "q2 does not intersect the interior of $\square_2$" Sec. 7 (beginning) could be mis-interpreted as stating that certificate (3) is "sufficient" for the conclusion of Lemma 7.1. (the hypothesis of Lemma 7.1 makes clear that cerificates (1)-(3) together form a "sufficient" condition). Page 624: should be "we negate". Def 5.1 (last sentence): if and only if $d_\mu(v)$ is of one sign
abstract
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.
abstract
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.
abstract
On the construction of high-quality surfaces...
2003
abstract
Bézier 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, Bézier 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.
abstract
An algorithm is presented for approximating a rational multi-sided M-patch by a 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.
abstract
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.
talk: 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.
Efficient One-Sided Linearization of Spline Geometry Mathematics of Surfaces, 10th IMA International Conference, Leeds, UK, September 15-17, 2003
abstract
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.
abstract
subdividable linear efficient function enclosures (slefes) and more
2002
On the Optimality of Piecewise Linear Max-Norm Enclosures Based on Slefes International Conference on Curves and Surfaces, Saint-Malo, France, 2002
abstract
Subdividable linear efficient function enclosures (Slefes) provide, at low cost, a piecewise linear pair of upper and lower bounds ƒ+, ƒ-, that sandwich a function ƒ on a given interval: ƒ- ≤ ƒ ≤ ƒ+. 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 (ƒ+)-(ƒ-) of the slefe to the narrowest possible piecewise linear enclosure of ƒ when ƒ is a univariate cubic polynomial.
abstract
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.
abstract
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.
abstract
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 Gk free-form surface spline. Here Gk characterizes a relation between specific maps while Ck 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 Gk free-form surface splines and points to some low degree constructions. The chapter closes with a listing of additional literature.
errata:
  • p. 7 Fig 5: “p1” lower left should be ‘p2
  • p. 8 Def 2.2: A subdomain is a simple...; ...maps points outside Δ1 to points inside Δ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”
  • p. 12 l-3 (second but last display) \lambda_i → -\lambda_i     \mu_i → -\mu_i,
    the result of [1 \lambda_i; 0 \mu_i]*[0 1; -1 0]
abstract
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, splines at extraordinary points
2001
abstract
For a stationary, affine invariant, symmetric, linear and local subdivision scheme that is 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.
Curved PN Triangles Symposium on Interactive 3D Graphics (I3D), Research Triangle Park NC, USA, March 19 - 21, 2001
abstract
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ézier 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.
Curved PN Quads Tech report 2008 ( The analogue of PN triangles for quadrilateral patches.)
Optimized Refinable Enclosures of Multivariate Polynomial Pieces Computer Aided Geometric Design (CAGD) 18, 9, 851-863, 2001
abstract
(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-bb+ over the domain of of interest. Enclosures are optimized by minimizing the width maxU 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ézier 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 ¼ under midpoint subdivision.
Smooth Patching of Refined Triangulations ACM Transactions on Graphics (TOG) 20, 1, 1-9, Jan. 2001
abstract
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 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.
Modifications of PCCM Technical Report (REP-2001-314), University of Florida, 2001
abstract
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.
Tight Linear Envelopes for Splines Numerische Mathematik, 89, 4, 735-748, Oct. 2001 bsbounds
abstract
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ézier 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.
2000
Higher Order Smooth Patching of Refined Triangulations (Patching Loop Meshes) 2000
abstract
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≠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.
Patching Catmull-Clark Meshes SIGGRAPH, 2000
abstract
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 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
Gaussian and Mean Curvature of Subdivision Surfaces 9th IMA Conference on the Mathematics of Surfaces, September 04 - 07, 2000
abstract
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.
See talk slides.
Envelopes of Nonlinear Geometry Doctoral Dissertation, Purdue University, 2000
abstract
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.
Least Squares Approximation of Bézier Coefficients Provides Best Degree Reduction in the L2-Norm Journal of Approximation Theory 104, 1, 90-97, 2000
abstract
Given a polynomial p in d variables and of degree n we want to find a best L2-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.
1999
Localized-hierarchy surface splines (LeSS)
Carlos Gonzalez-Ochoa and Jörg Peters
Symposium on Interactive 3D Graphics (I3D) Atlanta, Georgia, USA, April 26 - 28, 1999
abstract
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.
Polynomial Degree Reduction in the L2-Norm Equals Best Euclidean Approximation of Bézier coefficients Computer Aided Geometric Design (CAGD), 16, 7, 607-612, Aug. 1999
abstract
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 l2 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 L2, l2 degree reduction one step at a time from degree n to degree d.
Linear Envelopes for Uniform B-spline Curves 4th International Conference on Curves and Surfaces, Saint-Malo, France, July 1 - 7, 1999
abstract
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.
Smooth Paths in a Polygonal Channel 15th Annual Symposium on Computational Geometry (SCG), Miami Beach, FL, USA, June 13 - 16, 1999
abstract
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.
Computing Linear Envelopes for Uniform B-Spline Curves SIAM Student Paper Prize 1999
abstract
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.
Sharp, quantitative bounds on the distance between a polynomial piece and its Bézier control polygon Computer Aided Geometric Design (CAGD), 16, 7, 613-631, 1999
before 1999