are available for checking interference between components as the
`user interactively assembles the object.
`(Alternatively, interference
`detection can be disabled.) The first method is the fastest and least
`accurate, as it uses only protruding (peg, dovetail, etc.) features and
`ray Casting to determine whether the feature intersects the other
`component where there is no hole.
`It is easy to see that surface-sun
`face intersections will be missed unless one of the surfaces is a peg
`feature. The second method is slightly slower but somewhat more
`accurate.
`It looks at the corners of all the surfaces making up the
`components being connected. For each comer, a ray is cast to deter-
`mine whether the comer is inside or outside the other component. If
`any comer is inside the other component, interference is detected.
`This method may miss some intersections between curved elements.
`The third method performs a true booiean intersection between
`every surface in the first component and every surface in the second
`component. However, this operation is slow and becomes slower as
`the number of surfaces in the components increases (which is guar-
`anteed to happen as the assembly grows more and more complex),
`even when bounding box checking is used to eliminate pairs of sur-
`faces which definitely do not interfere.
`Determining a part’s translational degrees of freedom is
`closely related to being able to determine whether or not the part
`is removable from the assembly by a single translation.
`It is also
`sometimes important to check that a given part is constricted in
`such a way that it cannot be removed. For example, if a user is
`designing a fixture for machining, he may wish to make sure that
`all the degrees of freedom of the stock being held in the fixture are
`constrained and the stock cannot accidentally slide out of the fix-
`ture while being machined.
`The user can choose a component or set of components cur-
`rently in the assembly for examination (if more than one compo-
`nent is selected, they are examined as a group), and initiate the
`computation of translational degrees of freedom from the mated
`features by selecting a menu option.
`If a component’s motion is
`not constrained, the direction vectors representing the directions in
`which the component is free to move form a sphere.
`If the com-
`ponent mates with a single flat surface on some side, that mating
`reduces the degrees of freedom to half a sphere, because all the
`direction vectors with a factor in the direction of the constraining
`surface’s normal are eliminated. Similarly, if the component mates
`with a surface that is not flat, all the direction vectors with a com-
`ponent in the direction of any normal on the constraining surface
`are eliminated. This situation is illustrated in Figure 6, which
`shows a two-dimensional analogue to the preceding explanation.
`
`nits
`mam
`
`Figure 6.
`
`Determining how a two-dimensional component’s
`translational freedom is constrained by two flat-edge
`matings.
`(a, b) Each mating constrains the movement
`of the shaded component to any direction in the shad-
`ed semicircle.
`(c) The final set of directions is deter-
`mined by intersecting all the semicircles.
`
`
`
`Figure 7.
`
`A component, axis of rotation, and the outer and inner
`contours for determining rotational freedom. Our sys-
`tem computes a polyline approximation to such a con-
`tour.
`
`All the feature matings of the component(s) being analyzed are
`examined.
`Flat surfaces add a single half-sphere constraint.
`Hole/hole matings add a single half sphere constraint since a sur-
`face is assumed to be present whenever a hole is, even if that sur-
`face is not specifically given as a mating feature. Sculptured sur-
`faces’ normals are sampled, and each normal adds a half-sphere
`constraint. A hole/peg mating constrains the two components to
`move only along the axis line of the peg and hole. All of these con-
`straints are intersected to determine a section of a sphere, a single
`direction, or two opposing directions which satisfy all the con-
`straints. The set of valid directions of motion is displayed as a col-
`lection of vectors.
`-
`Similarly, the user may wish to determine if a component (or
`group of components) can rotate in place.
`In order to be able to
`rotate a component, the component must participate in a mating
`involving a round peg and hole. This condition is necessary to be
`able to determine an axis of rotation for the component. The axis
`of rotation is taken to be that of the mated peg and hole. There is
`no graphical display for the results of rotational freedom analysis,
`but the user is shown a message summarizing the result.
`If the component participates in more than one peg/hole mat-
`ing, rotation is obviously not possible. Otherwise, a polyline
`approximation to the outlines which would be swept out by rotat-
`ing the components about the axis of rotation is found. Each con-
`trol point of each surface is examined, and its distances from the
`axis of rotation and from the lowest point on the component are
`determined. An outer and inner contour are then computed from
`these points for the rotating component (see Figure 7). Likewise,
`an outer and inner contour are computed for the stationary compo-
`nent. If the outer contour of the rotating component is everywhere
`closer to the axis of rotation than the inner contour of the station-
`
`ary component, we may conclude that free rotation is possible.
`The same conclusion can be made if the inner contour of the rotat-
`ing component is outside the outer contour of the stationary com-
`ponent. A more accurate algorithm should be developed for this
`step, since the existing one involves too much approximation.
`However, it serves to illustrate the usefulness of rotational analy-
`SIS.
`
`6. Exploded View Illustration
`
`Exploded view illustrations are common in technical docu-
`mentation because they are easy to understand even by people with-
`out area expertise. Yet, while they are easy to understand, they are
`deceptively difficult and time consuming to create manually. We
`use information about part geometries, mated features, and disas-
`sembly directions indicated by the mating of features to automate
`much of the process of creating such illustrations.
`As part of the assembly design system, a tool has been devel-
`oped to create an exploded view of a completed assembly when that
`
`31
`
`BUNGIE - EXHIBIT 1006 - PART 3 OF 14
`
`BUNGIE - EXHIBIT 1006 - PART 3 OF 14
`
`

`
`ExploIir.-
`
`_
`
`ll:-*.ti:»r=|
`
`le:Fl.--
`
`Figure 8. The exploded view tool.
`
`assembly had been created and put together using the otherparts of
`the system. Even though the creation of exploded views is largely
`automated, a good deal of user control is allowed, because even the
`most clever algorithm can sometimes generate results which are aes-
`thetically unpleasing or otherwise not exactly what the user wants.
`The difficult or repetitive operations, such as keeping track of part
`connections, computing a perspective view of the geometry, and
`finding the approximate locations for the parts in the final illustra-
`tion are done by the algorithm. The user decides whether the illus-
`tration should be an exploded view of the whole assembly or of a
`subassembly, and can also alter the distance of explosion of any part
`or subassembly, hide or show any component in the current illustra-
`tion, cause any subassembly to be shown exploded or unexploded,
`request enlarged views of small subassemblies, and specify which
`parts should have text labels.
`(A screen capture of the utility is
`shown in Figure 8.) The explosion of the assembly is generated in
`three dimensions, but the view can be manipulated by the user until
`it is satisfactory, then the geometry and view can be saved for out-
`put to a rendering program.
`Several preprocessing steps are involved in creating an explod-
`ed view illustration. Although the geometries of the parts are ini-
`tially stored in their own coordinate systems (the coordinate systems
`in which they have been modeled), for the generation of exploded
`views it is more convenient to store all geometries relative to the
`coordinate system of the completed assembly. Since each compo-
`nent stores the transformation which assembles it to its parent, this
`is easily accomplished. The next step involves figuring out the
`minimum distance each component must be exploded from its par-
`ent subassembly to completely remove it from that subassembly.
`This distance only needs to be computed once for each component,
`since the basic relationships among the assembly components do
`not change. Bounding boxes are computed for the component and
`for its parent subassembly minus the component. Then the mini-
`mum distance to separate the bounding boxes along the direction
`of explosion is found. (The explosion direction is indicated by the
`mating conditions present between the two components.)
`
`The creation of an exploded view is a recursive operation.
`Each child of the main assembly is translated out from the assem-
`bly’s origin along its removal direction by its minimum explosion
`distance plus some additional value. (This extra distance serves to
`further separate the parts, giving the “exploded” look.) Each com-
`ponent of each of these subassemblies is, in turn, translated along
`its removal direction out from the origin of the exploded parent
`subassembly. The process continues until
`individual parts are
`reached. The transformations are accumulated through the levels
`of recursion, so each component has applied to it all of its ances-
`tor subassemblies’ translations, then finally, its own.
`However, an exploded view illustration does not consist sim-
`ply of a set of parts separated in space. Leader lines are drawn
`between parts, indicating from where each component was explod-
`ed. Parts may also exhibit identification labels. Leader lines are
`computed after the exploded geometries of all the components
`have been found. A single line per part is not enough to clearly
`show how that part connects to the other assembly components, so
`leader lines are drawn between every pair of mated features.
`Labels help identify parts in the illustration. Each label consists of
`a text string (the part’s name, first assigned in the assembly plan-
`ner) and a leader line connecting the label to the bounding box of
`the part.
`
`7. Data Structure
`
`All of the tools described here use a common basic data struc-
`ture for the assembly. We have already mentioned that this struc-
`ture stores the assembly hierarchically, as a tree (the approach is
`similar to that of Lee and Gossard [4]). This section summarizes
`what data is stored.
`Each node representing an assembly component is capable of
`storing the information below; different pieces of information are
`added throughout the design process:
`
`32
`
`
`
`

`
`burdening the designer. Exploded view illustration has also been
`explored.
`
`Acknowledgements
`
`We would like to thank the students and staff of the Alpharl
`project, within which this work was developed. Thanks also go to
`Dr. Richard Riesenfeld, for his help in editing this paper. This
`work was supported in part by ARPA, under grant N00014-92—J-
`4113. All opinions, findings, conclusions, or recommendations
`expressed in this document are those of the authors and do not nec-
`essarily reflect the views of the sponsoring agencies.
`
`References
`
`[1]
`
`[2]
`
`[3]
`
`[4]
`
`[5]
`
`[6]
`
`[7]
`
`[8]
`
`[9]
`
`[10]
`
`[11]
`
`[12]
`
`De Fazio, Thomas L. and Daniel E. Whitney, Simplified
`Generation of All Mechanical Assembly Sequences, IEEE
`Transactions on Robotics and Automation, RA-3(6), 1987,
`pp. 640-658.
`Eastman, Charles M., The Design of Assemblies, SAE
`Technical Paper No. 810197, Society of Automotive
`Engineers, Inc., 1981.
`Functional
`Gui,
`Jin-Kang
`and Martti Mantyla,
`Understanding of Assembly Modelling, Computer-Aided
`Design, June 1994, pp. 435-451.
`Lee, Kunwoo and David C. Gossard, A Hierarchical Data
`Structure for Representing Assemblies: Part 1, Computer
`Aided Design, 17(1), 1985, pp. 15-19.
`Lee, Sul-than and Yeong Gil Shin, Assembly Planning
`Based on Subassembly Extraction, Proceedings of the
`1990 IEEE International Conference on Robotics and
`Automation, 1990, pp. 1606-1611.
`Lieberman, L.
`I. and M. A. Wesley, AUTOPASS: An
`Automatic Programming System for Computer Controlled
`Mechanical Assembly,
`IBM Journal.’ of Research and
`Development, 21(4), 2977, pp. 321-333.
`Mattikalli, Raju S., Pradeep K. Khosla, and Yangsheng Xu,
`Subassembly Identification and Motion Generation for
`Assembly: A Geometric Approach, Engineering Design
`Research Center, Carnegie Mellon University, preprint.
`Shah, Jami J'., Conceptual Development of Form Features
`and Feature Modelers, Research in Engineering Design,
`(2) 2991, pp. 93-108.
`Strip, David and Anthony A. Maciejewski, Archimedes: an
`Experiment
`in Automating Mechanical Assembly,
`preprint, to be presented at the International Symposium
`on Robotics and Automation, July 1990, Vancouver, B.C.
`Talukdar, Sarosh N. and Sergio W. Sedas, A Disassembly
`Planner, Technical Report EDRC-05-10-8'7, Engineering
`Design Research Center, Carnegie Mellon University,
`1987.
`
`Tilove, Robert B., Extending Solid Modeling Systems for
`Mechanism Design and Kinematic Simulation, IEEE
`Computer Graphics and Applications, May/June 1983, pp.
`9-19.
`
`and Debasish Dutta, Automatic
`Woo, Tony C.
`Disassembly and Total Ordering in Three Dimensions,
`preprint,
`to appear in ASME Transactions, Journal of
`'-‘Mechanical Design, (during or after 1989, exact year
`unknown).
`
`- The name of the component, given by the designer.
`a A pointer to the subassembly of which the component is a
`part. The main assembly is the only one which has no parent.
`- A direction in which the component can be removed from its
`parent assembly, determined from mating conditions.
`. Textual comments about the component, entered by and use-
`ful for the designer.
`- A list of the assembly features of the component.
`-
`Information to create the transformation used to move this
`component from its geometry’s local coordinate system into
`the coordinate system of its immediate parent subassembly.
`o A list of component parts, if any.
`Individual parts have no
`components.
`o The name of the file, if any, where the geometry of the com-
`ponent is stored. Usually, only individual parts have geome-
`try. The geometries of subassemblies are derived from the
`geometries of their component parts.
`- The geometry of the component.
`
`Each assembly feature stores the following information:
`
`- The geometric description of the feature. This includes the
`feature location and orientation, depth, radius, cross-section
`curve, number of threads per unit of length, and so on, as
`appropriate to the type of feature. Hole features also indicate
`whether or not they go all the way through the material and
`are open on both ends. The geometry is specified in the coor-
`dinate system of the component to which the feature belongs;
`- Transformation information used for mating the feature with
`its matching feature.
`- A back pointer to the component whose feature this is.
`0 The matching feature (if any) on some other component.
`- The inheritance history of the feature. This includes the next
`and previous history links, as mentioned previously, and links
`to other features (if any) which were coalesced to create this
`one.
`
`8. Future Work
`
`A number of open issues still remain. First, a better mecha-
`nism for making design revisions should be created. Currently, the
`three clients we have described communicate through ‘data files. It
`would be useful to be able to make changes in the assembly plan-
`ner and have these changes propagate to the other clients, auto-
`matically updating the assembly components’ geometries and con-
`nections. This is not an easy problem, however, especially if the
`topology of the assembly or of any of the parts changes. Next,
`more accurate and reliable assembly analysis algorithms should be
`developed. Also, the system currently only tests whether a part is
`removable along paths consisting of a single translation. Methods
`for dealing with more complex removal paths should be examined.
`We can also envision extensions which would increase the
`
`usefulness of the system. For example, incorporating full-fledged
`kinematic analysis would enable designers to examine mecha-
`nisms to see if they perform as expected.
`
`9. Conclusions
`
`A system has been developed which integrates a number of
`design aids which have not been previously available together in
`order to help users design assemblies of mechanical parts. This
`research has shown how, by integrating initial and more detailed
`design into a single system,
`the designer’s knowledge can be
`extracted in a natural way during the design process without over-
`
`33
`
`

`
`

`
`Hierarchical and Variational
`
`Geometric Modeling with Wavelets
`
`Steven J. Gortlerl
`
`and
`
`Michael F. Cohen?‘
`
`Department of Computer Science
`Princeton University
`
`Abstract
`
`This paper discusses how wavelet techniques may be
`applied to a variety of geometric modeling tools.
`In
`particular, wavelet decompositions are shown to be
`useful for hierarchical control point or least squares
`editing.
`In addition, direct curve and surface manip-
`ulation inethods using an underlying geometric varia-
`tional principle can be solved more efficiently by using
`a wavelet basis. Because the wavelet basis is hier-
`archical, iterative solution methods converge rapidly.
`Also, since the wavelet coefficients indicate the degree
`of detail in the solution, the number of basis func-
`tions needed to express the variational minimum can
`be reduced, avoiding unnecessary computation. An
`implementation of a curve and surface modeler based
`on these ideas is discussed and experimental results are
`reported.
`
`1
`
`Introduction
`
`Wavelet analysis provides a set of tools for representing functions
`hierarchically. These tools can be used to facilitate a number of
`geometric modeling operations easily and efficiently. In particular,
`this paper explores three paradigms for free-form curve and surface
`construction: control point editing, direct manipulation using least
`squares, and direct manipulation using variational minimization
`techniques. For each of these paradigms, the hierarchical nature
`of wavelet analysis can be used to either provide a more intuitive
`modeling interface or to provide more efficient numerical solutions.
`In control point editing, the user sculpts a free-form curve or
`surface by dragging a set of control points. A better interface
`allows the user to directly manipulate the curve or surface itself,
`which defines a set of constraints.
`In a least squares paradigm,
`given a current curve or surface, the modeling tool returns the curve
`
`1Currently at Microsoft Corp. and the Department of C.S., University of Washing-
`ton. sjg@cs.washington.edu
`2Cll1T€liIl}' at Microsoft Corp. mcohen @rnicrosofi.com
`
`» Permission to copy withoutfee all or part of this material is
`Granted provided that the copies are not made or distributed for
`direct commercial advanta
`ge, the ACM copyright notice and the
`title of the publication and i
`_
`I
`_
`_ ts date appear, and notice is given
`that
`copying is by permission of the Association of Computing
`Mac
`hinery. To copy othenivise, or to republish, requires a fee
`and/or specific permission.
`1995 Sym
`posium on Interactive 3D Graphics, Monterey CA USA
`© 1995 ACM O-89791-736-7/95/0004..
`.$3.5O
`
`35
`
`or surface that meets the constraints by changing the current control
`points by the leastsquares amount [1, 11].
`The behavior of the modeling tool is determined by the type
`of control points and basis functions used to describe the curve
`or surface. With the unifomi cubic B-spline basis, for example,
`the user's actions result in local changes at a predetermined scale.
`This is not fully desirable; at times the user may want to make fine
`changes of detail, while at other times he may want to easily make
`broad changes. Hierarchical B-splines offer a representation that
`allows both control point and least squares editing to be done at
`multiple resolutions [9]. Hierarchical B-splines, though, form an
`over-representation for_ curves and surface {i.e., any curve has mul-
`tiple representations using hierarchical B-splines). As a result, the
`same curve may behave differently to a user depending on the partic-
`ular underlying representation. In contrast, B-spline wavelets form
`a hierarchical basis for the space of B-spline curves and surfaces
`in which every object has a unique representation. Wavelet meth-
`ods in conjunction with hierarchical B-splines provide amethod for
`constructing a useful geometric modeling interface. This approach
`is similar to the one described by Finkelstein and Salesin [8]. In this
`paper we will discuss some of the various issues that are relevant to
`building such a modeling tool.
`Variational modeling is a third general paradigm for geometric
`modeling[2, 28, 21]. In this setting, a user alters a curve or surface
`by directly manipulation, as above, defining a set of constraints. The
`variational modeling paradigm seeks the “best” solution amongst all
`answers that meet the constraints. The notion of best, which is for-
`mally defined as the solution that minimizes some energy function,
`is often taken to mean the smoothest solution.
`In theory, the desired solution is the curve or surface that has
`the minimum energy of all possible curves or surfaces that meet the
`constraints. Unfortunately there is little hope to find a closed form
`solution 1. Therefore, in practice, the “space” of parametric curves
`or surfaces is restricted to those represented by a linear combination
`of a fixed set of basis functions such as cubic B-splines. Given a set
`of in basis functions, the goal of finding the best curve or surface is
`then reduced to that of finding the best set of rt coefficients. This
`reduction is referred to as the finite element method [27].
`The general case requires solving a non-linear optimization
`problem.
`In the best case, the energy function is quadratic and
`the constraints are linear leading to a single linear system to solve.
`But even this can be costly when n is large since direct methods for
`matrix inversion require O(n3) time. To accelerate this process it is
`tempting to use gradient-type iterative methods to solve the linear
`system; these methods only take O(n) time per iteration, due to
`the O(n) matrix sparsity created by the finite element formulation.
`‘But see [20].
`
`

`
`1024
`
`Figure 1: Minimum energy solutions subject to three constraints, found by the B-spline and wavelet methods after various numbers (04024)
`of iterations. (65 variables, 3 constraints}. This illustrates the ill conditioning of the B-spline optimization problem.
`
`Unfortunately, the linear systems arising from a finite element for-
`mulation are often expensive to solve using iterative methods. This
`is because the systems are ill-conditioned, and thus require many
`iterations to converge to a minimum [26, 25]. Intuitively speaking
`this occurs because each basis function represents a very narrow
`region of the answer; there is no basis function which can be moved
`to change the answer in some broad manner. For example, chang-
`ing one coefficient in a cubic B-spline curve during an iteration
`alters the curvature in a local region only.
`In order to produce a
`broad smooth curve, the coefficients of the neighboring B-splines
`will move in next few iterations. Over the next many iterations, the
`solution process will affect wider and wider regions, and the effect
`will spread out slowly like a wave moving along a string. The result
`is very slow convergence (see Figure (1)). One method used to
`combat this problem is multigridding [26, i0], where a sequence of
`problems at different resolution levels are posed and solved.
`An alternative approach, is to use a wavelet basis instead of a
`standard finite element basis [25, 23, 15, 22].
`In a wavelet basis,
`the answer is represented hierarchically. This allows the solution
`method to alter the answer at any desired resolution by altering
`the proper basis function, and thus the ill-conditioning is avoided.
`ln this paper we show how to use a wavelet construction, which
`is based on cubic B-splines, to quickly solve variational modeling
`problems in an elegant fashion.
`Another problem with the finite element approach is choosing
`the density of the basis functions. If too few basis functions (too
`few B-spline segments or tensor product B-spline patches) are used
`then the solution obtained will be far from the actual minimum. If
`too many basis functions are used then unnecessary computation
`will be performed during each iteration (11 is too big). In order to
`successfully choose a proper density, one must know how much
`detail exists in the variational minimum answer. Since, a priori, this
`is unknown, an efficient solver must be able to adaptively change
`the basis’-during the solution process [28], one needs an easy way
`to detect that too many or too few basis functions are being used.
`In addition, one needs a basis for which adding more detail, (i.e.,
`refinement), is easy. Wavelets offer a basis where this task can be
`accomplished quickly and elegantly.
`The work presented in this paper combines the wavelet ap
`proaches of [25], [12], and [16]. Like [25], this paper uses hierar-
`chical basis functions as a pre—conditioner, so that fewer iterations
`are needed for convergence. Similar to [12] and [16], wavelets are
`also used as a method for limiting the solution method to the proper
`level of detail.
`
`2 Geometric Representation
`
`This paper will restrict itself to parametric representations of curves
`and surfaces.
`In this representation, a curve is defined as a 3
`
`dimensional trajectory parameterized by t,
`
`alt) = (X(t),Ytt),Z(t)}
`and a surface is defined as
`
`'r(Sat) = (X(s,t),Y(3:t)»Z(S=t))
`
`{1}
`
`(2)
`
`which defines a three dimensional location for every parameter pair
`(8, 15)-
`The parametric representation of a curve or surface is made
`up of three functions X, Y, Z, which are represented as a linear
`combination of basis functions.
`lust focusing on the X function,
`for curves this becomes
`
`X(t) = Zn,-«’,e’>L,j(tl
`J'
`
`and for surfaces
`
`X(s,u = Ens,-,r«:>r,,,i(s.t)
`331:
`
`(3)
`
`‘
`(4)
`
`In geometric modeling the
`where the :1: are scalar coefficients.
`univariate basis 45,-,_y(t} is typically some “piecewise” basis, such
`as a cubic B-spline or the Bernstein (Bézier) basis, and the bivari—
`ate basis used for surfaces is the associated tensor product basis
`¢L,j,k(S1t)E <I5L,j(S)¢L.tv(t)-
`
`3 Hierarchical Geometric Descriptions
`
`In this section we will briefly review some ways that curves and
`surfaces may be represented hierarchically.
`Let us begin by discussing curves. For simplicity we will deal
`with the uniform cubic B-spline basis over the interval [0 .
`.
`. 2L]
`made up of translations of a single basis shape denoted r,i5(t). The
`cubic B-spline function qb(t) is supported over the interval [0, . .4]
`and is made up of 4 cubic polynomial pieces joined with 02 con-
`tinuity. The complete uniform cubic B-spline basis is made up of
`translated copies g15g,,j (t) of the basis shape ¢(t) (see Figure 2).
`
`¢L,: (if) = <:5(t r j)
`
`(5)
`
`The index j represents the translation of a specific basis from the
`canonical B-spline left justified at zero, and L is the level or resolu-
`tion of the basis. There are roughly 2L functions in this basis 2. In
`wavelet terminology, the space (or family) of curves spanned by all
`linear combinations ofthese basis functions is denoted VL (e.g., V;
`~ contains all functions that are piecewise cubic, with simple knots at
`the integers}.
`
`1A few extra basis functions are needed at the boundary. This paper will not discuss
`the technical details needcdto handle all ofthe boundary constraints. This is discussed
`in many places including [4, 16, 8, 1'3].
`
`
`
`

`
`3.1 Hierarchical B-splines
`
`Forsey and Bartels [9] introduced hierarchical B-splines as away of
`representing and modeling geometric objects hierarchically. Instead
`of using only B-spline basis functions at a single resolution L, they
`use a hierarchy of Wider and wider B-spline functions
`
`as (n = ¢>{2L"'t — j}
`
`(6)
`
`for O S 1' S L. For example, the basis functions gi5L_i,,- at reso-
`lution level L — 1 (with a support size of 8), are twice as wide as
`the basis functions ¢L,J- at level L (with a support size of 4). These
`basis functions, ¢«;,_ 1 J, span the space of piecewise cubic functions
`with knots at all even integers; in wavelet terminology, this space is
`called VL_1. On each coarser level, the space V; has half as many
`basis functions, and they are all twice as wide.
`According to the well known B-spline knot insertion algo-
`rithm [6, 9, 3] one can define double width B-spline basis functions
`as linear combinations of single width B-spline basis functions.
`
`¢5t—1,j = Elli--21‘ <i>z',k
`it
`
`where the sequence .71 is
`
`4 6 4 1
`l
`[L4 : — — — -- —
`3,8.8.8.8}
`]
`
`at
`
`(7)
`
`(8)
`
`(see Figure (2)). As a result of Equation (7) the set of functions in
`l/,_] is a subset of the functions in V,-.
`
`V«;—1 C Vi
`
`(9)
`
`The basic idea of Forsey and Bartels is to allow the user to control
`the coefficient of each of these basis functions or-,,i by exposing a
`control mesh at each level i.
`
`3.2 Wavelets
`
`l-lierarchical B-splines {r,i5.;,_.,} do not form a basis for the function
`space 1/5;
`they form an overrepresemanbn for all the curves in
`l/L.
`In other words,
`there‘ are many linear combinations of the
`basis functions defining the same curve or surface. Wavelets are a
`representation related to hierarchical B-splines, that form a basis;
`in a wavelet basis, alt curves in V1, have a unique representation.
`Rather than add a new finer set of B-splines at each level of the
`hierarchy, the idea is to look for a set of functions 1,‘),-,5 that “fills
`in" the space between the adjacent B-spline spaces, V; and V,-+1.
`These wavelet functions 1,1’),-,3 represent the detail of the curve that
`cannot be represented by the double width B-splines, qé,-__,-. For each
`i, the space of functions spanned by the ab,-J is called W,-.
`There is actuafly quite a bit of freedom in choosing these 1,b,-,_,-
`functions, and hence the space W..-, as long as every function in
`1/1+; can be written as a combination of some function in V; and
`some function in W,—. This is notated as
`'
`
`Vi-H = Vt-l-W1‘
`
`(10)
`
`Just like the Hierarchical B-splines are all scales and translates
`of a single shape (f>(t), (see Equation (5)) in a wavelet basis, the
`basis functions 1,b,-_,- are all translates and scales of a single function
`Mt)
`L
`,
`(11)
`1%,: (t) = W2 -3 — J)
`Also similar to hierarchical B-splines, in a wavelet basis, the
`basis functions on one level can he defined by linearly combining
`B-spline functions on the next finer resolution,
`
`¢li—lJ = Zg;._2,¢.-,i.
`it
`
`(12)
`
`And as a result W1-ai C V}. There is some degree of freedom
`in choosing the sequence g, as long as the property expressed by
`Equation (10) holds. One such sequence given by Cohen et al. [5]
`is 3 (see Figure (3)).
`
`5
`20
`-70 e961
`[O 101%: 2_o _1_ is :73 230
`"
`‘ 25s‘2ss'25s‘ 256 ‘ 255 ’255’fi"2'5"eTm_s’fi’§5"6}
`
`5'
`
`Due to the relationships of Equations (7) and (12), if some
`function X(t} in V,- has been expressed as a linear combination of
`the B-spline basis function at level i — I and wavelet basis functions
`at level 1' — 1, using coefficients notated by a2¢:._m. and :L‘.),‘._1'J.,
`
`Xltl = E "'C¢3i—1,_7' ¢1:"1aj
`1'
`
`+ "'U1»l«':‘—:,;.‘
`
`'l:"}I'—ls.1' (t)
`
`(13)
`
`then, mg“, the coefficients of the same function, with respect to
`the B-spline basis at level 2' may be found with
`
`5'5¢;,_«; = Zhi-2k w¢i—l,k + 2193'-3* x'§l"i—1,Je
`J:
`k
`
`(14)
`
`and now X(t) = 29.11:“). <;b.:,,-(t)
`inversely, if some function has been expressed with respect to
`B-spline functions at level 2', then the representation of Equation
`(13) may be found using the formula
`
`"”¢i—1,j
`
`a;,,,,_,’,.
`
`2 ‘E’-’€—2.?' m<i5i,:a
`is
`
`Z §k—2:' $¢»;,i.-
`In
`
`£15)
`
`(16)
`
`using the proper inverse sequences § and fa. Equation (15)projects
`the high resolution curve from 17.; into the lower resolution space
`V,--1‘, this is, in some sense, a smoother approximation of the object
`in V,-. Equation (16) captures the detail thatis lostin this projection,
`and represents it using a basis for the space l/V1-1.
`When using the it and g sequences given by Cohen et al [5], the
`proper inverse sequences ft and 51 are
`-96 70
`280
`70
`/5
`20
`—l
`“H--71=tmm—fi»fi=§e=mm=mng~r§a-533}
`
`-4 6 -4 1
`1
`~3..7=-4-—————
`] {8.8.8.8.8}
`at
`
`17
`()
`
`3.3 The Basis
`
`Every function in VL, expressed as a combination of the B-spline
`basis functions {¢L,]‘}, can be expressed uniquely in the wavelet
`basis is made up by the functions
`
`{¢5n.j,¢h,i} US i S L—1
`
`(13)
`
`In the wavelet representation, the function is expressed hierarchi-
`Cally.
`Transforming afunction's representation from B-spline to wavelet
`coefficients may be done with the pyramid procedure :2: oef -pynn_