• Overview
• Research Area Description
• Publications, Manuscripts, and Reports
• Selected Presentations
• Contact Information

Overview

• University of Waterloo's
• Faculty of Math's
• School of Computer Science's
• Computer Graphics Lab.

My main research activities involve:

• Surface design using parametric splines
• Surface fitting using parametric splines
• Wavelets and subdivision
• Code development for the above

Research Area Description

Pasted Spline Surfaces

Pasted spline surfaces consist of two or more spline surfaces that are associated by a particular set of mappings. The characteristics of the mapping are such that if surface B is mapped onto surface A, the general form of B conforms to the shape of A while the finer details of B are retained. This mimics the physical process that would occur if B were made of clay and were to be attached firmly to A. Changes in the form of A are subsequently be propagated to B so that the attachment remains. The process has important applications in the animation industry, where it allows complex, flexible shapes to be constructed in a layered fashion from simpler shapes. The process has important application to industrial design, where it allows features to be designed separately and attached to a base surface with few restrictions on position and orientation. Open problems we intend to address involve controlling the accuracy and quality of the join between surface B and A, investigating methods for constructing pasted surfaces from data through adaptive parametric fitting, and gaining practical experience by attempting some significant applications in industrial design and animation. We have also begun addressing the issues of how the pasting process can be provided to a designer most effectively through 3D interaction.

Subdivision Surfaces and Multiresolutions

A subdivision surface is procedurally defined from a network of points in space and a set of masks. Each mask is a rule that specifies how some number of new points are to be inserted into the network in place of some smaller number of existing points. There are typically only a few basic connection configurations in the network, and there is one mask defined for each such configuration. A subdivision surface is the limit, if it exists, of the repetitive application of the set of masks over the network. Subdivision surfaces are important, because networks of points can conveniently represent arbitrary shapes. The subdivision process has the additional importance that each network created during the process can serve as a simple approximation to the limit surface for the purpose of display, which provides a multi-resolution description of the final surface. By retaining information only about the important differences between one level of subdivision and the next, this can provide a compressed representation of the surface in terms of storage. Our research on subdivision surfaces will proceed in two fundamental directions. Firstly, no generic, interactive editors currently exist for subdivision surfaces. Such editors would accept masks as plug-ins and work in a uniform way no matter what the subdivision rule. We have completed the prototype of one such editor, taking care to use object-oriented abstractions that will permit the editor to work generically on a network with any suitable sets of masks. Secondly, we are exploring ways in which any given mask set can be inverted; that is, ways in which a network having a very high number of points can be successively be replaced by approximating networks of fewer points augmented by the efficient storage of difference information. In brief, this means the construction of a full multiresolution from a given subdivision. We have succeeded in doing this for various subdivisions on 1-D and a variety of 2-D network topologies, and we now believe we have a generalizable, constructive approach.

Hierarchical Spline Surfaces

A hierarchical surface is a special case of surface representation that combines some elemental aspects of pasted surfaces and subdivision surfaces. Spline surfaces are most conveniently defined as linear combinations of spline basis functions with control vertices. The control vertices are organized into regular networks and spline basis functions, in turn, have subdivision properties that can be reflected as a regular sets of masks on those networks. The spline surface itself is the limit of the subdivision process, and spline surfaces represent an important case of subdivision surfaces for which the limit is known in the form of explicit functions. A hierarchical spline surface results when the subdivision rule is carried out at selective locations to yield surface areas of high detail interspersed with areas of low detail. The higher detail portions are then retained as offset information in a way consistent with the process of surface pasting. There are two main benefits of hierarchical spline surfaces: the representation can present the same detail as a highly-subdivided spline surface in a much more compact form, and the surfaces can be edited at any time and in any mixture of broad and fine detail. These surfaces have begun to mature and are beginning to find significant application in the animation industry. We feel there is still progress to be made in the adaptive fitting of data by hierarchical spline surfaces, and we expect to pursue ideas in this area, particularly exploiting relationships that exist between hierarchical splines and spline wavelets. We also intend to explore the extent to which the ideas of hierarchical spline surfaces can be extended to general subdivision surfaces and to non-tensor-product surfaces.

Publications, Manuscripts, and Reports

• Sivalingam, S. and Bartels, R.
  Matrix-nullspace Wavelet Construction
  Box splines are chosen as basis elements, and some preliminary studies of using matrix methods are made to construct known, conventional box-spline wavelets. This unpublished manuscript is a precursor to those below on reversing subdivision rules.


• Samavati, F., Bartels, R.
  Multiresolution Curve and Surface Representation by Reversing Subdivision Rules
  (in compressed PostScript)
  in Computer Graphics Forum
  vol. 18, no. 2, June, 1999, pages 97-119
  Subdivision curves and surfaces begin with a polygonal network of points and edges (and, for surfaces, faces) having a relatively coarse structure. Each type of curve and surface is defined by a set of subdivision rules that replace the coarse network by a finer network to which the rules could again be applied. The subdivision curve or surface is the limit of repeated application. In this paper we explore the possibilities for reversing the subdivision process using least-squares techniques. The approach taken borrows strongly from the framework of wavelets and multiresolution analysis with certain important differences, resulting in new wavelets for B-splines, for example, that have smaller compact support and simpler representations than those previously used for multiresolution curves and surfaces.


• Bartels, R., Samavati, F.,
  Reversing Subdivision Rules: Local Linear Conditions and Observations on Inner Products
  in the Journal of Computational and Applied Mathematics
  vol. 119, nos. 1-2, July, 2000, pages 29-67
  In this work we study biorthogonal systems based upon subdivision rules and local least squares fitting problems that reverse the subdivision. We are able to produce multiresolution structures for some common subdivision rules that have both sparse reconstruction and decompositions filters. We observe that each biorthogonal system we produce can be interpreted as a semiorthogonal system with an inner product induced on the multiresolution that is quite different from that normally used. Some examples of the use of this approach on images and geometry are given.


• Samavati, F., Mahdavi-Amiri, N., Bartels, R.
  Multiresolution Surfaces Having Arbitrary Topologies by a Reverse Doo Subdivision Method
  in Computer Graphics Forum
  vol. 21, no. 2, June, 2002, pages 121-136
  In a paper appearing in Computer Graphics Forum in 1999, we have shown how to construct multiresolution structures for reversing subdivision rules for curves and tensor-product surfaces using global least-squares models. We extended these results to local least-squares models in a paper to appear in 2000 in the Journal of Computational and Applied Mathematics. In this third work of the series, we construct multiresolution surfaces of arbitrary topologies by locally reversing the Doo subdivision scheme.


• Samavati, F., and Bartels, R.
  Reversing Subdivision Using Local Linear Conditions: Generating Multiresolutions on Regular Triangular Meshes
  In the paper listed above that appears in Journal of Computational and Applied Mathematics we constructed multiresolution structures for reversing subdivision rules on curves and tensor-product surfaces using local least-squares. We extended these results to non-tensor-product surfaces here (specifically: regular, triangular-mesh surfaces).


• Samavati, F., and Bartels, R.
  Diagrammatic Tools for Generating Biorthogonal Multiresolutions
  A shorter version of this paper, with new material on how to handle mesh boundaries, appears in the
  International Journal of Shape Modeling, volume 12, number 1, pp. 47-73, June, 2006.


• Bartels, R., Golub, G., and Samavati, F.
  Some Observations on Local Least Squares
  in BIT Numerical Mathematics
  vol. 46, no. 3, pp. 455-477, 2006.
  In this work we use a result by Dahlquist, et. al. on the method of averages to explore how and to what extent our local least-squares estimation approaches a full least-squares approximation. Two main example problem domains are used: data reduction (subdivision) and data approximation. We find in these examples that the extimation rapidly improves with the size of the local least-squares problems, and that the quality of the estimate is largely independent of the size of the full problem in uniform situations.


• Samavati, F., Bartels, R., and Olsen, L.
  Local B-spline Multiresolution with Examples in Iris Synthesis and Volumetric Rendering
  appears as a chapter in Synthesis and Analysis in Biometrics World Scientific Publishing 2006
  This provides a survery overview of our method of constructing multiresolutions from subdivisions. Several example applications are given, including an example of image compression and a comparison with JPEG.


• Samavati, F., Ali Nur, M., Bartels, R., and Wyvill, B.
  Progressive Curve Representation Based on Reverse Subdivision
  in The 2003 International Conference on Computational Science and Its Applications, Lecture Notes in Computer Science 2667, pp. 67-78, 2003.
  We discuss a method to remove points from a curve while keeping track, in a storage-efficient manner, of the error caused by each removal. Localized reverse subdivision (localized biorthogonal multiresolution) is presented.


• Olsen, L., Samavati, F. F., Bartels, R. H.
  Multiresolution B-Splines Based on Wavelet Constraints
  poster presentation at theThird Eurographics Symposium on Geometry Processing
  Vienna, Austria, July 4-6, 2005
  We present a novel method for determining local multiresolution filters for B-spline subdivision curves of any order. Our approach is based on constraining the wavelet coefficients such that the coefficients at even vertices can be computed from the coefficients of neighboring odd vertices. This constraint leads to an initial set of decomposition filters. To increase the quality of these initial filters, we use a line search optimization that reduces the size of the wavelet coefficients. The resulting multiresolution filters are a biorthogonal wavelet system whose construction is similar to the lifting scheme. This approach is demonstrated in depth for cubic B-spline curves. Our filters are shown to perform comparably with established filters.


• Barghiel, C., Bartels, R., and Forsey, D.
  Pasting Spline Surfaces
  in Mathematical Methods for Curves and Surfaces,
  edited by M. Daehlen, T. Lyche, L. L. Schumaker,
  Vanderbilt University Press, Nashville, TN., 1995, pp. 31-40.
  The basic approach for layering spline surfaces, flexibly, one atop another is described (see the Pasted Spline Surfaces Research Area Description for the basic outline of the concept). For some examples look at The CGL Splines Project.


• Bartels, R.
  Object Oriented Spline Software
  in Curves and Surfaces II,
  edited by Laurent, Le Méhauté, and Schumaker,
  A K Peters Ltd., 1994, pp. 27-34.


• Bartels, R., and Forsey, D.
  Constraint Based Curve Manipulation
  in Tutorial Notes: Splines in Computer Graphics
  prepared for Eurographics '94, September 12-16, 1994, pp. 31-36.


• Sheikh, H. and Bartels, R.
  Towards a Generic Editor for Subdivision Surfaces
  in Shape Modeling International '97
  Proceedings of the International Conference on Shape Modeling and Applications
  March 3-6 1997, Aizu-Wakamatsu, Japan,
  IEEE Computer Society Press, 1997, pp. 37-46.
  Subdivision surfaces are defined by a mesh of points and by one or more refinement rules according to which new subsets of points are substituted for existing subsets, which are usually smaller in size, to yield refined meshes. The refinement rules defining a subdivision surface are known collectively as the refinement process defining the surface. Refinement processes of interest are any for which the successively refined meshes can be shown to converge to a subdivision surface with known smoothness properties. In this paper we report on an investigation into software abstractions for refinement, providing for a generic editor to be implemented that can assist in the design of any subdivision surface.


• Bartels, R. H. and Beatty, J. C.
  Connection-Matrix Splines by Divided Differences
  in Curves and Surfaces with Applications in CAGD,
  Proceedings of the Third Chamonix Conference on Curves and Surfaces,
  edited by A. Le Méhauté, Ch. Rabut, L. L. Schumaker,
  Vanderbilt University Press, 1997, pp. 9-16
  We move the classical, divided-difference construction for B-splines into a connection-matrix setting by establishing a one-sided basis for connection-matrix splines together with a differencing process that transforms the one-sided basis into a compact-support basis that partitions unity.

Selected Presentations

• Multiresolution with Image Applications
  Given at Simon Fraser University, 2006.
  (PowerPoint presentation)


• Subdivision, Multiresolution, BiOrthogonal Matrices, Maple
  Given at the Maple Conference, University of Waterloo, 2006.
  (PowerPoint presentation)


• Local Least Squares
  Given at the University of British Columbia, 2003.
  (PowerPoint presentation)


• Introduction to Subdivision and Multiresolution
  Given at the University of British Columbia, 2002.
  (PowerPoint presentation)


• Constructing Multiresolutions from Subdivisions
  Given at the University of British Columbia, 2002.
  (PowerPoint presentation)

Contact