Divided differences play a fundamental role in the construction of univariate B-splines over irregular knot sequences. Unfortunately, generalizations of divided differences to irregular knot geometries on two-dimensional domains are quite limited. As a result, most spline constructions for such domains typically focus on regular (or semi-regular) knot geometries. In the planar harmonic case, we show that the discrete Laplacian plays a role similar to that of the divided differences and can be used to define well-behaved harmonic B-splines. In our main contribution, we then construct an analogous discrete bi-Laplacian for both planar and curved domains and show that its corresponding biharmonic B-splines are also well-behaved. Finally, we derive a fully irregular, discrete refinement scheme for these splines that generalizes knot insertion for univariate B-splines.

In this paper, we describe a method for exact evaluation of a limit mesh defined via subdivision on a uniform grid of any size. Other exact evaluation technique either restrict the grids to have subdivision sampling and are, hence, exponentially increasing in size or make assumptions about the underlying surface being piecewise polynomial (Stam's method is a widely used technique that makes this assumption). As opposed to Stam's technique, our method works for both polynomial and non-polynomial schemes. The values for this exact evaluation scheme can be computed via a simple system of linear equation derived from the scaling relations associated with the scheme or, equivalently, as the dominant left eigenvector of an upsampled subdivision matrix associated with the scheme. To illustrate one possible application of this method, we demonstrate how to generate adaptive polygonalizations of a non-polynomial quad-based subdivision surfaces using our exact evaluation method. Our method guarantees a water-tight tessellation no matter how the surface is sampled and is quite fast. We achieve tessellation rates of over 33.5 million triangles/ second using a CPU implementation.

Associating specific gene activity with functional locations in the brain results in a greater understanding of the role of the gene. To perform such an association for the more than 20 000 genes in the mammalian genome, reliable automated methods that characterize the distribution of gene expression in relation to a standard anatomical model are required. In this paper, we propose a new automatic method that results in the segmentation of gene expression images into distinct anatomical regions in which the expression can be quantified and compared with other images. Our contribution is a novel hybrid atlas that utilizes a statistical shape model based on a subdivision mesh, texture differentiation at region boundaries, and features of anatomical landmarks to delineate boundaries of anatomical regions in gene expression images. This atlas, which provides a common coordinate system for internal brain data, is being used to create a searchable database of gene expression patterns in the adult mouse brain. Our framework annotates the images about four times faster and has achieved a median spatial overlap of up to 0.92 compared with expert segmentation in 64 images tested. This tool is intended to help scientists interpret large-scale gene expression patterns more efficiently.

Dual Contouring (DC) is a feature-preserving isosurfacing method that extracts crack-free surfaces from both uniform and adaptive octree grids. We present an extension of DC that further guarantees that the mesh generated is a manifold even under adaptive simplification. Our main contribution is an octree-based topology-preserving vertex-clustering algorithm for adaptive contouring. The contoured surface generated by our method contains only manifold vertices and edges, preserves sharp features, and possesses much better adaptivity than those generated by other isosurfacing methods under topologically safe simplification.

We provide an image deformation method based on Moving Least Squares using various classes of linear functions including affine, similarity and rigid transformations. These deformations are realistic and give the user the impression of manipulating real-world objects. We also allow the user to specify the deformations using either sets of points or line segments, the later useful for controlling curves and profiles present in the image. For each of these techniques, we provide simple closed-form solutions that yield fast deformations, which can be performed in real-time.

Abstract We present a method for contouring an implicit function using a grid topologically dual to structured grids such as octrees. By aligning the vertices of the dual grid with the features of the implicit function, we are able to reproduce thin features of the extracted surface without excessive subdivision required by methods such as Marching Cubes or Dual Contouring. Dual Marching Cubes produces a crack‐free, adaptive polygonalization of the surface that reproduces sharp features. Our approach maintains the advantage of using structured grids for operations such as CSG while being able to conform to the relevant features of the implicit function yielding much sparser polygonalizations than has been possible using structured grids.

Massive amounts of data are being generated in an effort to represent for the brain the expression of all genes at cellular resolution. Critical to exploiting this effort is the ability to place these data into a common frame of reference. Here we have developed a computational method for annotating gene expression patterns in the context of a digital atlas to facilitate custom user queries and comparisons of this type of data. This procedure has been applied to 200 genes in the postnatal mouse brain. As an illustration of utility, we identify candidate genes that may be related to Parkinson disease by using the expression of a dopamine transporter in the substantia nigra as a search query pattern. In addition, we discover that transcription factor Rorb is down-regulated in the barrelless mutant relative to control mice by quantitative comparison of expression patterns in layer IV somatosensory cortex. The semi-automated annotation method developed here is applicable to a broad spectrum of complex tissues and data modalities.

Constructing a function that interpolates a set of values defined at vertices of a mesh is a fundamental operation in computer graphics. Such an interpolant has many uses in applications such as shading, parameterization and deformation. For closed polygons, mean value coordinates have been proven to be an excellent method for constructing such an interpolant. In this paper, we generalize mean value coordinates from closed 2D polygons to closed triangular meshes. Given such a mesh P , we show that these coordinates are continuous everywhere and smooth on the interior of P . The coordinates are linear on the triangles of P and can reproduce linear functions on the interior of P . To illustrate their usefulness, we conclude by considering several interesting applications including constructing volumetric textures and surface deformation.

In this article, we present a subdivision scheme for mixed triangle/quad meshes that is C2 everywhere except for isolated, extraordinary points. The rules that we describe are the same as Stam and Loop's scheme [2003] except that we perform an unzipping pass prior to subdivision. This simple modification improves the smoothness along the ordinary triangle/quad boundary from C1 to C2, and creates a scheme capable of subdividing arbitrary meshes. Finally, we end with a proof based on Levin and Levin's [2003] joint spectral radius calculation to show our scheme is indeed C2 along the triangle/quad boundary.

We present a method for contouring an implicit function using a grid topologically dual to structured grids such as octrees. By aligning the vertices of the dual grid with the features of the implicit function, we are able to reproduce thin features of the extracted surface without excessive subdivision required by methods such as marching cubes or dual contouring. Dual marching cubes produces a crack-free, adaptive polygonalization of the surface that reproduces sharp features. Our approach maintains the advantage of using structured grids for operations such as CSG while being able to conform to the relevant features of the implicit function yielding much sparser polygonalizations than has been possible using structured grids.

As the logical next step after sequencing the mouse genome, biologists have developed laboratory methods for rapidly determining where each of the 30K genes in the mouse genome is synthesizing protein. Applying these methods to the mouse brain, biologists are currently generating large numbers of 2D cross-sectional images that record the expression pattern for each gene in the mouse genome. In this paper, we describe the structure of a geometric database for the mouse brain that allows biologists to organize and search this gene expression data. The central component of this database is an atlas that explicitly partitions the mouse brain into key anatomical regions. This atlas is represented as a Catmull-Clark subdivision mesh with anatomical regions separated by a network of B-spline crease curves. New gene expression images are added to the database by deforming this atlas onto each image using techniques developed for fitting subdivision surfaces to scatter data. Due to this partitioning of the subdivision mesh, user queries comparing expression data between various genes can be restricted to anatomical regions without difficulty while the multi-resolution structure of the subdivision mesh allows these queries to be processed efficiently.

We propose the use of surface subdivision as adaptive and higher-order boundary elements for solving a Helmholtz partial differential equation to calculate accurate acoustic scattering on arbitrary manifolds. Such acoustic transfer functions prove useful for designing and tuning hearing aid devices for hearing impaired individuals. The number of unknowns of the discretized linear system is the same as that in a linear element approach. Our results show that the accuracy of the subdivision approach is much better than that of the linear element approach.

This paper describes a new method for contouring a signed grid whose edges are tagged by Hermite data (i.e; exact intersection points and normals). This method avoids the need to explicitly identify and process "features" as required in previous Hermite contouring methods. Using a new, numerically stable representation for quadratic error functions, we develop an octree-based method for simplifying contours produced by this method. We next extend our contouring method to these simpli£ed octrees. This new method imposes no constraints on the octree (such as being a restricted octree) and requires no "crack patching". We conclude with a simple test for preserving the topology of the contour during simplification.

The motion of fluids has been a topic of study for hundredsof years. In its most general setting, fluid flow is governed by a system of non-linear partial differential equations known as the Navier-Stokes equations. However, in several important settings, these equations degenerate into simpler systems of linear partial differential equations. This paper will show that flows corresponding to these linear equations can be modeled using subdivision schemes for vector fields. Given an initial, coarse vector field, these schemes generate an increasingly dense sequence of vector fields. The limit of this sequence is a continuous vector field defining a flow that follows the initial vector field. The beauty of this approach is that realistic flows can now be modeled and manipulated in real time using their associated subdivision schemes.

This paper presents a probabilistic planner capable of finding paths for a flexible surface patch. The planner is based on the probabilistic roadmap approach to path planning while the surface patch is modeled as a low degree Bezier surface. We assume that we are dealing with an elastic part and define an approximate energy model for the part. The energy function penalizes excessive shear and bending of the part and we assume that low-energy configurations correspond to reversible elastic deformations of the part. The planner captures the connectivity of a space by building a roadmap, a network of simple paths connecting configurations selected in the space using randomized techniques. We report on the implementation of our planner and show experimental results with examples where the surface patch is required to move through a small hole in its workspace. Our work is a first step towards considering the physical properties of parts when planning paths.

Presents an efficient algorithm for the reconstruction of a multivariate function from multiple sets of scattered data. Given N sets of scattered data representing N distinct dependent variables that have been sampled independently over a common domain and N error tolerance values, the algorithm constructs a triangulation of the domain of the data and associates multivariate values with the vertices of the triangulation. The resulting linear interpolation of these multivariate values yields a multivariate function, called a co-triangulation, that represents all of the dependent data up to the given error tolerance. A simple iterative algorithm for the construction of a co-triangulation from any number of data sets is presented and analyzed. The main contribution of this paper lies in the description of a highly efficient framework for the realization of this approximation algorithm. While the asymptotic time complexity of the algorithm certainly remains within the theoretical bounds, we demonstrate that it is possible to achieve running times that depend only linearly on the number of data even for very large problems with more than two million samples. This efficient realization of the algorithm uses adapted dynamic data structures and careful caching in an integrated framework.

Thin plate splines are a well known entity of geometric design. They are defined as the minimizer of a variational problem whose differential operators approximate a simple notion of bending energy. Therefore, thin plate splines approximate surfaces with minimal bending energy and they are widely considered as the standard "fair" surface model. Such surfaces are desired for many modeling and design applications. Traditionally, the way to construct such surfaces is to solve the associated variational problem using finite elements or by using analytic solutions based on radial basis functions. This paper presents a novel approach for defining and computing thin plate splines using subdivision methods. We present two methods for the construction of thin plate splines based on subdivision: A globally supported subdivision scheme which exactly minimizes the energy functional as well as a family of strictly local subdivision schemes which only utilize a small, finite number of distinct subdivision rules and approximately solve the variational problem. A tradeoff between the accuracy of the approximation and the locality of the subdivision scheme is used to pick a particular member of this family of subdivision schemes. Later, we show applications of these approximating subdivision schemes to scattered data interpolation and the design of fair surfaces. In particular we suggest an efficient methodology for finding control points for the local subdivision scheme that will lead to an interpolating limit surface and demonstrate how the schemes can be used for the effective and efficient design of fair surfaces.

Multiresolution analysis and wavelets provide useful and efficient tools for representing functions at multiple levels of detail. Wavelet representations have been used in a broad range of applications, including image compression, physical simulation, and numerical analysis. In this article, we present a new class of wavelets, based on subdivision surfaces, that radically extends the class of representable functions. Whereas previous two-dimensional methods were restricted to functions difined on R 2 , the subdivision wavelets developed here may be applied to functions defined on compact surfaces of arbitrary topological type. We envision many applications of this work, including continuous level-of-detail control for graphics rendering, compression of geometric models, and acceleration of global illumination algorithms. Level-of-detail control for spherical domains is illustrated using two examples: shape approximation of a polyhedral model, and color approximation of global terrain data.

NC algorithms are given for determining the number and degrees of the factors, irreducible over the complex numbers ${\bf C}$, of a multivariate polynomial with rational coefficients and for approximating each irreducible factor. NC is the class of functions computable by logspace-uniform boolean circuits of polynomial size and polylogarithmic depth. The measures of size of the input polynomial are its degree, coefficient length, number of variables (d, c, and n, respectively). If n is fixed, we give a deterministic NC algorithm. If the number of variables is not fixed, we give a random (Monte-Carlo) NC algorithm in these input measures to find the number and degree of each irreducible factor. After reducing to the two-variable, square-free case, we apply the classical algebraic geometry fact that the absolute irreducible factors of $(P(z_1 ,z_2 ) = 0)$ correspond to the connected components of the real surface (or complex curve) $P(z_1 ,z_2 ) = 0$ minus its singular points. In finding the number of connected components of the surface $P = 0$, the surface is projected to the the $z_2 $-plane. The singular points of $P(z_1 ,z_2 )$ lie over the projection’s critical values. The inverse image of a grid isolating the critical values in the $z_2 $-plane lifts to a one-dimensional real curve skeleton on the surface $(P = 0)$ whose number of connected components is precisely the number of connected components of $P = 0$ minus its singular points. The connectivity of this curve skeleton is constructed symbolically using Sturm sequences associated with the various polynomials defining these maps. Given the number of irreducible factors and their degrees, the actual factors can be reconstructed using the recent result of Neff [Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pp. 152–162] on finding zeros of one-variable polynomials in NC.

In this article, we characterize the solution space of low-degree, implicitly defined, algebraic surfaces which interpolate and/or least-squares approximate a collection of scattered point and curve data in three-dimensional space. The problem of higher-order interpolation and least-squares approximation with algebraic surfaces under a proper normalization reduces to a quadratic minimization problem with elegant and easily expressible solutions. We have implemented our algebraic surface-fitting algorithms, and included them in the distributed and collaborative geometric environment SHASTRA. Several examples are given to illustrate how our algorithms are applied to algebraic surface design.

Rational Be´zier surfaces provide an effective tool for geometric design. One aspect of the theory of rational surfaces that is not well understood is what happens when a rational parameterization takes on the value (0/0, 0/0, 0/0) for some parameter value. Such parameter values are called base points of the parameterization. Base points can be introduced into a rational parameterization in Be´zier form by setting weights of appropriate control points to zero. By judiciously introducing base points, one can create parameterizations of four-, five- and six-sided surface patches using rational Be´zier surfaces defined over triangular domains. Subdivision techniques allow rendering and smooth meshing of such surfaces. Properties of base points also lead to a new understanding of incompatible edge twist methods such as Gregory's patch.

We give NC algorithms for determining the number and degrees of the absolute factors (factors irreducible over the complex numbers C) of a multi-variate polynomial with rational coefficients. NC is the class of functions computable by logspace-uniform Boolean circuits of polynomial size and polylogarithmic depth. The measures of size of the input polynomial are its degree d, coefficient length c, number of variables n, and for sparse polynomials, the number of non-zero coefficients s. For the general case, we give a random (Monte-Carlo) NC algorithm in these input measures. If n is fixed, or if the polynomial is dense, we give a deterministic NC algorithm. The algorithm also works in random NC for polynomials represented by straight-line programs, provided the polynomial can be evaluated at integer points in NC. Finally, we discuss a method for obtaining an approximation to the coefficients of each factor whose running time is polynomial in the size of the original (dense) polynomial. These methods rely on the fact that the connected components of a complex hypersurface P(z1…,zn) = 0 minus its singular points correspond to the absolute factors of P.

A new definition of geometric continuity for implicitly defined surfaces is introduced. Under this definition, it is shown that algebraic blending surfaces (surfaces that smoothly join two or more surfaces) have a very specific form. In particular, any polynomial whose zero set blends the zero sets of several other polynomials is always expressible as a simple combination of these polynomials. Using this result, new methods for blending several algebraic surfaces simultaneously are derived.

We show that a pair of quadric surfaces, M and N, may be blended (smoothly joined) using a quadric surface if and only if the pencil of M and N contains either a plane or a pair of planes. Under this condition, we derive the equations of quadric and cubic surfaces that blend M and N.

In this paper we present an intermediate program representation, called the program dependence graph ( PDG ), that makes explicit both the data and control dependences for each operation in a program. Data dependences have been used to represent only the relevant data flow relationships of a program. Control dependences are introduced to analogously represent only the essential control flow relationships of a program. Control dependences are derived from the usual control flow graph. Many traditional optimizations operate more efficiently on the PDG. Since dependences in the PDG connect computationally related parts of the program, a single walk of these dependences is sufficient to perform many optimizations. The PDG allows transformations such as vectorization, that previously required special treatment of control dependence, to be performed in a manner that is uniform for both control and data dependences. Program transformations that require interaction of the two dependence types can also be easily handled with our representation. As an example, an incremental approach to modifying data dependences resulting from branch deletion or loop unrolling is introduced. The PDG supports incremental optimization, permitting transformations to be triggered by one another and applied only to affected dependences.

In this paper, we propose a new dependence baaed program representation.This representation is the union of two previously separate concepts: loop carried dependence and hierarchical abstraction.The resulting form has the property that all information necessary to reorder the set of all executions of the statements contained in a given loop exists in the representation of that loop.Thus, this representation provides an ideal basis for reordering transformations such as vectorisation and loop fusion.As evidence of this, we give efficient algorithms for these two transformations based on this representation.

Program analysis methods, especially those which support automatic vectorization, are based on the concept of interstatement dependence where a dependence holds between two statements when one of the statements computes values needed by the other. Powerful program transformation systems that convert sequential programs to a form more suitable for vector or parallel machines have been developed using this concept [AllK 82, KKLW 80].The dependence analysis in these systems is based on data dependence. In the presence of complex control flow, data dependence is not sufficient to transform programs because of the introduction of control dependences. A control dependence exists between two statements when the execution of one statement can prevent the execution of the other. Control dependences do not fit conveniently into dependence-based program translators.One solution is to convert all control dependences to data dependences by eliminating goto statements and introducing logical variables to control the execution of statements in the program. In this scheme, action statements are converted to IF statements. The variables in the conditional expression of an IF statement can be viewed as inputs to the statement being controlled. The result is that control dependences between statements become explicit data dependences expressed through the definitions and uses of the controlling logical variables.This paper presents a method for systematically converting control dependences to data dependences in this fashion. The algorithms presented here have been implemented in PFC, an experimental vectorizer written at Rice University.