Abstract When moving along 3D curves, one may require local coordinate frames for visited points, such as for animating virtual cameras, controlling robotic motion, or constructing sweep surfaces. Often, consecutive coordinate frames should be similar, avoiding sharp twists. Previous work achieved this goal by using various methods to approximate rotation minimizing frames (RMFs) with respect to a curve's tangent. In this work, we use Householder transformations to construct preliminary tangent‐aligned coordinate frames and then optimize these initial frames under the constraint that they remain tangent‐aligned. This optimization minimizes the weighted sum of squared distances between selected vectors within the new frames and fixed vectors outside them (such as the axes of previous frames). By selecting different vectors for this objective function, we reproduce existing RMF approximation methods and modify them to consider additional objectives beyond rotation minimization. We also provide some example computer graphics use cases for this new frame tracking.

We have shown how to construct multiresolution structures for reversing subdivision rules using global least squares models (Samavati and Bartels, Computer Graphics Forum, 18(2):97–119, June 1999). As a result, semiorthogonal wavelet systems have also been generated. To construct a multiresolution surface of an arbitrary topology, however, biorthogonal wavelets are needed. In Bartels and Samavati (Journal of Computational and Applied Mathematics, 119:29–67, 2000) we introduced local least squares models for reversing subdivision rules to construct multiresolution curves and tensor product surfaces, noticing that the resulting wavelets were biorthogonal (under an induced inner product). Here, we construct multiresolution surfaces of arbitrary topologies by locally reversing the Doo subdivision scheme. In a Doo subdivision, a coarse surface is converted into a fine one by the contraction of coarse faces and the addition of new adjoining faces. We propose a novel reversing process to convert a fine surface into a coarse one plus an error. The conversion has the property that the subdivision of the resulting coarse surface is locally closest to the original fine surface, in the least squares sense, for two important face geometries. In this process, we first find those faces of the fine surface which might have been produced by the contraction of a coarse face in a Doo subdivision scheme. Then, we expand these faces. Since the expanded faces are not necessarily joined properly, several candidates are usually at hand for a single vertex of the coarse surface. To identify the set of candidates corresponding to a vertex, we construct a graph in such a way that any set of candidates corresponds to a connected component. The connected components can easily be identified by a depth first search traversal of the graph. Finally, vertices of the coarse surface are set to be the average of their corresponding candidates, and this is shown to be equivalent to local least squares approximation for regular arrangements of triangular and quadrilateral faces.

This work explores how three techniques for defining and representing curves and surfaces can be related efficiently. The techniques are subdivision, least‐squares data fitting, and wavelets. We show how least‐squares data fitting can be used to “reverse” a subdivision rule, how this reversal is related to wavelets, how this relationship can provide a multilevel representation, and how the decomposition/reconstruction process can be carried out in linear time and space through the use of a matrix factorization. Some insights that this work brings forth are that the inner product used in a multiresolution analysis in uences the support of a wavelet, that wavelets can be constructed by straightforward matrix observations, and that matrix partitioning and factorization can provide alternatives to inverses or duals for building efficient decomposition and reconstruction processes. We illustrate our findings using an example curve, grey‐scale image, and tensor‐product surface.

Subdivision surfaces are defined by a mesh of points and by one or more refinement rules that substitute new, larger subsets of points for existing subsets 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. The authors report on the progress of their investigations into software abstractions for refinement, providing for a generic editor to be implemented that can assist in the design of any subdivision surface.

We consider the fitting of tensor-product parametric spline surfaces to gridded data.The continuity of the surface is provided by the basis chosen.When tensor-product splines are used with gridded data, the surface-fitting problem decomposes into a sequence of curve-fitting processes, making the computations particularly efficient.The use of a hierarchical representation for the surface adds further efficiency by adaptively decomposing the fitting process into subproblems involving only a portion of the data.Hierarchy also provides a means of storing the resulting surface in a compressed format.Our approach is compared to multiresolution analysis and the use of wavelets, Categories and Subject Descriptors: 1

There are a variety of spline formulations for specifying smooth curves.In theory, many of these are equivalent in terms of the families of curves that can be obtained.In practice, each formulation encourages the implementation of certain styles of interaction in a curve editor and discourages other styles.This paper presents the design, implementation, and analysis of four experiments to illustrate a general shape-matching paradigm for studying interactive curve manipulation.We introduce the new shape-matching paradigm as a methodology for analyzing user performance.We then report on a series of studies that employ this paradigm to explore the relationship between a commonly used interaction style for curve design and various spline formulations, Controlled experiments were performed to test the hypothesis that the style of interaction implicit in the movement of single design points will influence the ease with which curve manipulation can be performed using a variety of spline formulations.Although such interactions are of a simple form, the experience gained in these studies has already enabled us to undertake more extensive experiments with more sophisticated interaction styles.The specific experiments reported here compare five formulations of cubic splines (B-splines, B6zier splines, Catmull-Rom splines, and two versions of interpolating splines with C 2 continuity), Data from the experiments show that, for the particular shape-matching tasks investigated, there is a significant performance difference among the five formulations.The B-spline formulation was best for the task, both in terms of match quality and in terms of the time required to Financial support for this research was provided by the

We have investigated the use of computer algebra as the basis for software tools for floating-point error

This paper is concerned with the development, numerical implementation, and testing of an algorithm for solving constrained nonlinear least squares problems. The algorithm is an adaptation of the least squares case of an exact penalty method for solving nonlinearly constrained optimization problems due to Coleman and Conn. It also uses the ideas of Nocedal and Overton for handling quasi-Newton updates of projected Hessians, those of Dennis, Gay, and Welsch for approaching the structure of nonlinear least squares Hessians, and those of Murray and Overton for performing line searches. This method has been tested on a selection of problems listed in the collection of Hock and Schittkowski. The results indicate that the approach taken here is a viable alternative for least squares problems to the general nonlinear methods studied by Hock and Schittkowski.

Refinement is usually advocated as a means of gaining finer control over a spline curve or surface during editing. For curves, refinement is a local process. It permits the change of control vertices and subsequent editing of the detail in one region of the curve while leaving control vertices in other regions unaffected. For tensor-product surfaces, however, refinement is not local in the sense that it causes control vertices far from a region of interest to change as well as changing the control vertices that influence the region. However, with some care and understanding it is possible to restrict the influence of refinement to the locality at which an editing effect is desired. We present a method of localizing the effect of refinement through the use of overlays, which are hierarchically controlled subdivisions. We also introduce two editing techniques that are effective when using overlays: one is direct surface manipulation through the use of edit points and the other is offset referencing of control vertices.

This paper reports on an interactive system for manipulating a tensor-product B-spline approximation to field data for applications in which contours are of interest. The features of the system are: an interpolation technique for approximating fields defined from scattered or gridded data by tensor-product B-splines, an interactive display providing control-vertex manipulation of the resulting B-spline approximation, and a contouring algorithm that is designed specifically for B-spline surfaces.

Forsythe has given a method for generating basis polynomials in a single variable that are orthogonal with respect to a given inner product. Weisfeld later demonstrated that Forsythe's approach could be extended to polynomials in an arbitrary number of variables. In this paper we sharpen Weisfeld's results and present a method for computing weighted, multinomial, least-squares approximations to given data.

article Free AccessArtifacts AvailableArtifacts Evaluated & Reusable Share on Algorithm 634: CONSTR and EVAL: routines for fitting multinomials in a least-squares sense Authors: Richard H. Bartels Department of Computer Science, University of Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Ontario, Canada N2L 3G1View Profile , John J. Jezioranski Ontario Cancer Institute, 500 Sherbourne St., Toronto, Ontario, Canada M4X 1K9 Ontario Cancer Institute, 500 Sherbourne St., Toronto, Ontario, Canada M4X 1K9View Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 11Issue 3Sept. 1985 pp 218–228https://doi.org/10.1145/214408.214412Online:01 September 1985Publication History 2citation329DownloadsMetricsTotal Citations2Total Downloads329Last 12 Months9Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper presents a new method for using cubic interpolating splines in a key frame animation system. Three control parameters allow the animator to change the tension, continuity, and bias of the splines. Each of these three parameters can be used for either local or global control. Our technique produces a very general class of interpolating cubic splines which includes the cardinal splines as a proper subset.

An algorithm for solving the problem minimize II A T x --bill subject to optional constraints of the form GTx ffi h, CTx >_ d, is given, together with an waplementation m Fortran.The algorithm generalizes one given earlier by the same authors for the unconstrained l~ problem.

indicates a Fortran module with n records NAMET(n): indicates "NAME" is included for testing purposes NAMED(n): indicates "NAME" contains test data

article Free Access Share on Hermite Interpolation Using a Triangular Polynomial Basis Authors: Richard Bartels Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, MD Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, MDView Profile , Alec Steingart Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, MD Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, MDView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 2Issue 3Sept. 1976 pp 252–256https://doi.org/10.1145/355694.355698Published:01 September 1976Publication History 2citation423DownloadsMetricsTotal Citations2Total Downloads423Last 12 Months21Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF