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.

abstract

T-junctions occur where surface strips start or terminate. This paper de-
velops a new way to create smooth piecewise polynomial free-form spline
surfaces from quad-meshes that include T-junctions. All mesh nodes are
interpreted as control points of GT-splines, i.e. geometrically smoothly
joined piecewise polynomials. GT-splines are akin to and compatible with
B-splines and cover simple T-junctions by two polynomial pieces of degree
bi-4 and more complex ones by four such patches. They complement multi-
sided surface constructions in generating free-form surfaces with adaptive
layout.
Since GT-splines do not require a global coordination of knot intervals,
GT-constructions are easy to deploy and can provide smooth surfaces with
T-junctions where T-splines can not have a smooth parameterization. GT-
constructions display a uniform highlight line distribution on input meshes
where alternatives, such as Catmull-Clark subdivision, exhibit oscillations.
abstract

Convolving the output of Discontinuous Galerkin (DG) computations
using spline filters can improve both smoothness and accuracy
of the output. At domain boundaries, these filters have to be
one-sided for non-periodic boundary conditions. Recently,
position-dependent smoothness-increasing
accuracy-preserving (PSIAC) filters were shown to be
a superset of the well-known one-sided RLKV and SRV filters.
Since PSIAC filters can be formulated symbolically, PSIAC
filtering amounts to forming linear products with local DG output
and so offers a more stable and efficient implementation.
The paper introduces a new class of PSIAC filters NPabstract

To date, singularly-parameterized surface constructions suffer from
poor highlight line distributions, ruling them out as a surface
representation of choice for primary design surfaces.
This paper explores graded, many-piece, everywhere $C^1$
singularly-parameterized surface caps
that mimic the shape of a high-quality guide surface.
The approach illustrates the
trade-off between polynomial degree and surface quality.
For bi-degree 5, minor flaws in the highlight line distribution
are still visible when zooming in on the singularity,
but the distribution is good at the macroscopic level.
Constructions of degree bi-4 or bi-3 may require one or more steps
of guided subdivision to reach the same macroscopic quality.
Akin to subdivision surfaces, singularly-parameterized functions
on the surfaces are straightforward to refine.
abstract

For two high-quality piecewise polynomial geometrically smooth ($G^1$)
surface constructions, explicit $G^1$ functions are derived
that form the basis of a functions space on the $G^1$ surfaces.
The spaces are refinable and nested, i.e. the functions can be
re-represented at a finer level. By choosing all basis functions
to be first order smooth a maximal set of degrees of freedom is
obtained that have small support and near-uniform layout.
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.
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.
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.
A comparative study of several classical, discrete differential and
isogeometric methods for solving Poisson’s equation on the disk
Axioms,
2014
talk (2013)

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.
Matched $G^k$-constructions always yield $C^k$-continuous
isogeometric elements
CAGD
2015
talk (2013)

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.
Correct resolution rendering of trimmed spline surfaces
Computer-Aided Design, (SPM 14: 1st prize, Best paper award)
2014
talk

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.
Refinability of splines derived from regular tessellations
Computer Aided Geometric Design (CAGD), vol. 31, May, pp. 141--147,
2014

abstract

Splines can be constructed by convolving the indicator function of
a cell whose shifts tessellate Rabstract

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$
Splines and unsorted knot sequences
Computer Aided Geometric Design, vol. 30, no. 7, pp. 733-741, Oct.
2013

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.
Curvature-sensitive splines and design with basic curves
Computer-Aided Design, vol. 45, no. 2, pp. 415423,
2013

abstract

This paper presents a non-uniform cubic C
Swarm-NG: A CUDA library for Parallel n-body Integrations with focus on simulations of planetary systems
New Astronomy, Volumes 23-24, October 2013, Pages 6-18

DOI: 10.1016/j.newast.2013.01.002

arXiv:1208.1157v1 [astro-ph.EP].

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.

Non-uniform interpolatory subdivision based on local interpolants of minimal degree
8th International Conference on Mathematical Methods for Curves and Surfaces, Oslo,
2012

abstract

This paper presents new univariate linear non-uniform interpolatory
subdivision constructions that yield high smoothness, C
Efficient Pixel-accurate Rendering of Animated Curved Surfaces
8th International Conference on Mathematical Methods for Curves and Surfaces, Oslo,
2012

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.
Free-form splines combining NURBS and basic shapes
GMOD (Graphical Models), vol. 74, no. 6, pp. 351360,
2012

abstract

We show how to automatically join, into one unified spline surface, Cabstract

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.
Non-uniform interpolatory subdivision via splines
Journal of Computational and Applied Mathematics, vol. 240, pp. 3141,
2012

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 C
Curve networks compatible with G^{2} surfacing
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 C
Efficient Pixel-Accurate Rendering of Curved Surfaces
Symposium on Interactive 3D Graphics and Games(I3D),
2012
Talk
.
Code
* patch_tess_pass.cs.glsl(line 297): change to
float max_[]_panel_width[3] = {0,0,0}; *

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.
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 C
Rational bi-cubic G^{2} splines for design with basic shapes
SGP (Symposium on Geometry Processing),
Computer graphics forum, vol. 30, no. 5,
2011

abstract

The paper develops a rational bi-cubic Gabstract

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, G
Enabling Surgeons to Create Simulation-Based Teaching Modules
Proceedings of Medicine Meets Virtual Reality (MMVR) 18 ,
163,
723-729,
Newport Beach, CA,
Feb.8-12
2011

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 C
The projective linear transition map
for constructing smooth surfaces
IEEE INTERNATIONAL CONFERENCE ON SHAPE MODELING AND APPLICATIONS (SMI) 2010),
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.
Symmetric Box-Splines on the A^{*}_{n} Lattice
Jounal of Approximation Theory,
162,
9,
1607-1630,
Sep.,
2010

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
abstract

When interpolating a network of curves to create a C
Reconciling conflicting combinatorial preprocessors for geometric
constraint systems
Itl J of Computational Geometry & Applications ,
2010

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.
Optimized parametrization of systems of
incidences between rigid bodies
Journal of Symbolic Computation,
45 ,
4,
481-498
April 2010

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.
Assembling curvature continuous surfaces from
triangular patches
IEEE International Conference on Shape Modeling and Applications (SMI)
Tsinghua University, Beijing, China, June 26-28
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.
On the Complexity of Smooth Spline Surfaces from
Quad Meshes
Computer Aided Geometric Design (CAGD)
27,
1,
96-105,
2010

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 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
C
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.

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 C
Parallel smoothing of quad meshes
The
Visual Computer: International Journal of Computer
Graphics,
25,
8,
757-769,
Aug.
2009

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$
Interactive Peritoneum in a Haptic Surgery Illustration Environment
Proceedings of Medicine Meets Virtual Reality (MMVR) 17 ,
142,
221-223,
Long Beach, CA,
Jan.19-22
2009

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.
abstract

We present an algorithm for completing a C
Optimized parametrization of systems of incidences
between rigid bodies
Journal of Symbolic Computation,
,
,
,
2008

abstract

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
The Distance of a Subdivision Surface to its Control
Polyhedron
Journal of Approximation Theory
2009

abstract

For standard subdivision algorithms and generic input data,
near an extraordinary point the distance
from the limit surface to the control polyhedron after 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)

An introduction to guided and polar surfacing
Mathematics
of Curves and Surfaces,
Seventh International Conference on Mathematical Methods for
Curves and Surfaces, Toensberg, Norway,
1-26, June 26-July 1,
2008
talk

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 simpliﬁes 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 ﬁnal surface compatible
with industry standards, either as a ﬁnite 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.
On Smooth Bicubic Surfaces from Quad Meshes
Advances in Visual Computing, 4th International Symposium, ISVC 2008,
87-96,
Las Vegas, NV, USA, December 1-3, 2008. Proceedings

abstract

Determining the least We constructively show that

Box Spline Reconstruction on the Face-Centered Cubic Lattice
IEEE
Transactions on Visualization and Computer Graphics
(Proceedings
Visualization / Information Visualization 2008),
14,
6,
1523-1530,
Nov./Dec.,
2008

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.

Fast and Stable Evaluation of Box-splines via the BB-form
Numerical Algorithms
50,
4,
381-399,
Apr.
2009

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**should not be in bold face.^{-1} - In equation (7), all three
*k*s 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).

Fast Parallel Construction of Smooth Surfaces from Meshes with Tri/Quad/Pent Facets
Symposium on Geometry Processing (SGP)
Copenhagen, Denmark,
January 2 - 4,
2008
[Errata
updated 2009-02-24]

Source code

Movie (9.2MB)

Source code

Movie (9.2MB)

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
Pairs of Bi-Cubic Surface Constructions Supporting Polar Connectivity
Computer Aided Geometric Design (CAGD)
25,
8,
621-630,
Feb.
2008

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.

Errata: Table 1 formula for

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.
GPU Conversion of Quad Meshes to Smooth Surfaces
ACM Solid and Physical Modeling Symposium (SPM)
Stony Brook University, June 2 - 4,
2008

abstract

We convert any quad manifold mesh into an at least
Fatty Tissue in a Haptic Illustration Environment
Proceedings of Medicine Meets Virtual Reality (MMVR) 16
,
132,
384-386,
Long Beach, CA,
Jan.29-Feb.1
2008

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
Some Solved and Unsolved Problems in
Subdivision, Surface Parametrization
and Algebraic Constraint Elimination
talk at
First International Workshop on Algebraic Geometry and Approximation Theory,
Towson University Towson, Maryland, USA,
April 11 - 12,
2008

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.
A Haptic-enabled Toolkit for Illustration of Procedures in Surgery (TIPS)
Proceedings of Medicine Meets Virtual Reality (MMVR) 15
,
125,
209-214,
Long Beach, CA,
Feb.6-9
2007

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.
Developing a Multimedia Environment for Customized Teaching of an Adrenalectomy
Surgical Endoscopy,
21,
6,
1012-1016,
Jun. 2007

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.
Guided *C²* Spline Surfaces with V-shaped tessellation
Mathematics of Surfaces XII
4647,
233-244,
2007

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
Concentric Tesselation Maps and Curvature Continuous Guided Surfaces
Computer Aided Geometric Design (CAGD)
24,
2,
99-111,
Feb.
2007

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 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
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.
Normals of Subdivision Surfaces and Their Control Polyhedra
Computer Aided Geometric Design (CAGD),
24,
2,
112-116,
Feb.
2007

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.
Simulation for Training with the Autosuture™ Endo Stitch™ Device
Surgical Innovation,
13
4,
283-287,
Dec.
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.
Exploiting Graphics Hardware for Haptic Authoring
Proceedings of Medicine Meets Virtual Reality (MMVR) 14
,
119,
255-260,
Long Beach, CA,
Jan.25-27
2006

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.
Parameterization Transition for Guided *C²* Surfaces of Low Degree
6^{th} International Conference on
Curves and Surfaces
Avignon, France,
June 29 - July 5,
2006

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
A *C²* Polar Jet Subdivision
Eurographics Symposium on Geometry processing (SGP)
Cagliari, Sardinia, Italy,
June 26 - 28,
2006

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.
Fast Safe Spline Surrogates for Large Point Clouds
Third International Symposium on 3D Data Processing, Visualization and Transmission (3DPVT)
University of North Carolina, Chapel Hill, USA,
June 14-16,
2006

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.
On the Local Linear Independence of Generalized Subdivision Functions
SIAM Journal on Numerical Analysis (SINUM)
44,
6,
2389-2407,
Jan.
2006

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.
Structural Analysis of Subdivision Surfaces - A Summary
Topics in Multivariate Approximation and Interpolation, Volume 12,
Nov.
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.
Real-Time Loop Subdivision on the GPU
SIGGRAPH 2005 poster,
SIGGRAPH '05: ACM SIGGRAPH 2005 Posters,
Los Angeles, California,
123,
Jul.31-Aug.4
2005

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
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.
Mesh Refinement Library based on Generic Design
43rd Annual ACM Southeast Conference,
Kennesaw, Georgia,
March 18 - 19,
2005

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.
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
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.
An Accurate Error Measure for Adaptive Subdivision Surfaces
International Conference on Shape Modeling and Applications
2005

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.
Elimination in Generically Rigid 3D Geometric Constraint Systems
Algebraic Geometry and Geometric Modeling,
Nice, France,
September 27 - 29,
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.
Combining 4- and 3-Direction Subdivision
ACM Transactions on Graphics (TOG)
23,
4,
980-1003,
Oct.
2004

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 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.
Shape Characterization of Subdivision Surfaces - Basic Principles
Computer Aided Geometric Design (CAGD),
21,
6,
585-599,
Jul.
2004

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
Shape Characterization of Subdivision Surfaces - Case Studies
Computer Aided Geometric Design (CAGD)
21,
6,
601-614,
2004

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...
Mid-Structures Linking Curved and Linear Geometry
SIAM Conference on Geometric Design and Computing (GD03),
Seattle, Washington, US,
Nov. 10 - 13,
2003
Talk Slefe
Talk Mid

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.
Polynomial *C²* Spline Surfaces Guided by Rational Multisided Patches
Computational Methods for Algebraic Spline Surfaces (COMPASS),
Schloβ Weinberg, Kefermarkt (Austria),
September 29 - October 3,
2003

abstract

An algorithm is presented for approximating a rational multi-sided M-patch
by a
Mesh Mutation in Programmable Graphics Hardware
ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware,
San Diego, CA, USA,
July 26 - 27,
2003

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.
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
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
ƒ
Smoothness, Fairness and the Need for Better Multi-Sided Patches
Topics in Algebraic Geometry and Geometric Modeling: Workshop on Algebraic Geometry and Geometric Modeling,
Vilnius University, Lithuania
July 29 - August 2,
2002

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
errata:

- p. 7 Fig 5: “p
_{1}” lower left should be ‘p_{2}” - p. 8 Def 2.2: A subdomain is a simple...; ...maps points outside Δ
_{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
Computing Curvature Bounds for Bounded Curvature Subdivision
Computer Aided Geometric Design (CAGD)
18,
5,
455-461,
2001

abstract

For a stationary, affine invariant, symmetric, linear and local subdivision scheme
that is
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.
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 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 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.
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.
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 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
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

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.
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 *L*_{2}-Norm
Journal of Approximation Theory
104,
1,
90-97,
2000

abstract

Given a polynomial
Localized-hierarchy surface splines (LeSS)
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 *L*_{2}-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
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.
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.