Publication and Presentations

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.

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² surface. By design, this C² polar spline joins C² with surrounding bi-3 tensor-product splines and thereby complements algorithms that smoothly cap star-like, multi-sided regions.

The paper develops a rational bi-cubic G² (curvature continuous) analogue of the non-uniform polynomial C² 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.

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.

We develop a class of rational, G² -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 C² transitions. [errata: p.12 p^k_{i-1} should be p^k_i]

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.

Converting a quadrilateral input mesh into a C¹ 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 G¹ construction.

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.

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 A_n^* by a symmetric box-spline family M_r^*. A₂^* is the hexagonal lattice and A₃^* is the BCC lattice. We point out the similarities and differences of M_r^* with respect to the popular Cartesian-shifted box-spline family M_r, document the main properties of M_r^* and the partition induced by its knot planes and construct, in n variables, the optimal quasi-interpolant of M₂^*.

When interpolating a network of curves to create a C¹ 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 G² interpolation by smooth patches.

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.

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.

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.

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.

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.

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¹ surface in the limit. When correcting this flaw by adjusting the vertex rule, we discover a variant whose characteristic ring is z². 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 C² 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 z^4/n, cos z and e^z. ("The original publication is available at www.springerlink.com" doi 10.1007/s00607-009-0060-9 )

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.

Popular subdivision algorithms like Catmull-Clark and Loop are C² 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 C² 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 C² 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.

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.

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.

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.

We present an algorithm for completing a C² 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.

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.

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

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)

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.

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 ¹ and that a single patch per quad is incompatible with a localized construction. We do not specify the GPU implementation.

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.

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.

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.

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

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.

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.

We convert any quad manifold mesh into an at least C¹ 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.

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.

Following (Karciauskas and Peters, “Concentric Tesselation Maps and Curvature Continuous Guided Surfaces”) below, we analyze surfaces arising as an infinite sequence of guided C² 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.

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.

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.

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.

The guided spline approach to surface construction separates surface design and surface representation by constructing local guide surfaces and sampling these by splines of moderate degree. This paper explains a construction based on tessellating the domain into V-shaped regions so that the resulting C² surfaces have G² 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.

A multi-sided hole in a surface can be filled by a sequence of nested, smoothly joined surface rings. We show how to generate such a sequence so that (i) the resulting surface is C² (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.

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

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

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

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.

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.

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

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

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

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

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

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.

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

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

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

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

This paper characterizes when the normals of a spline curve or spline surface lie in the more easily computed cone of the normals of the segments of the spline control net.

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

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

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.

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 C¹ and have bounded curvature everywhere. In regular mesh regions, they are C² 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.

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.

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.

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

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

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

On the construction of high-quality surfaces...

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.

An algorithm is presented for approximating a rational multi-sided M-patch by a C² 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.

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

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

Subdividable linear efficient function enclosures (Slefes) provide, at low cost, a piecewise linear pair of upper and lower bounds ƒ⁺, ƒ^-, 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.

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

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

This chapter covers geometric continuity with emphasis on a constructive definition for piecewise parametrized surfaces. The examples in Section 1 show the need for a notion of continuity different from the direct matching of Taylor expansions used to define the continuity of piecewise functions. Section 2 defines geometric continuity for parametric curves, and for surfaces, first along edges, then around points, and finally for a whole complex of patches which is called a G^k free-form surface spline. Here G^k characterizes a relation between specific maps while C^k continuity is a property of the resulting surface. The composition constraint on reparametrizations and the vertex-enclosure constraints are highlighted. Section 3 covers alternative definitions based on geometric invariants, global and regional reparametrization and briefly discusses geometric continuity in the context of implicit representations and generalized subdivision. Section 4 explains the generic construction of G^k free-form surface splines and points to some low degree constructions. The chapter closes with a listing of additional literature.

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

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

To improve the visual quality of existing triangle-based art in real-time entertainment, such as computer games, we propose replacing flat triangles with curved patches and higher-order normal variation. At the hardware level, based only on the three vertices and three vertex normals of a given flat triangle, we substitute the geometry of a three-sided cubic Bé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.

(Old title: Envelopes for tensor product polynomials) An an optimized refinable enclosure is a two-sided approximation of a uni- or multivariate function b in B by a pair of typically simpler functions b^-, b⁺ in H not equal to B such that b^- ≤ b ≤ b⁺ over the domain of of interest. Enclosures are optimized by minimizing the width max_U b⁺ - b^- and refined by enlarging the space H. This paper develops a framework for efficiently computing enclosures for multivariate polynomials and, in particular, derives piecewise bilinear enclosures for bivariate polynomials in tensor-product Bé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.

This paper presents a simple algorithm for associating a smooth, low degree polynomial surface with triangulations whose extraordinary mesh nodes are separated by sufficiently many ordinary, 6-valent mesh nodes. Output surfaces are at least tangent continuous and are C² 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.

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.

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.

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.

A simple, explicit transformation creates maximally large, smoothly joining Nurbs patches of order 4 from Catmull-Clark subdivision meshes. It can be applied after any of the first subdivision steps and creates patches that are maximally large in the sense that one patch corresponds to one quadrilateral facet of the initial, coarsest quadrilateral mesh before subdivision. The patches join C² 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).

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

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

Given a polynomial p in d variables and of degree n we want to find a best L₂-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.

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.

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

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

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

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.