Shape Modeling Description

New Computation Techniques for Shape Modeling and Design:
Overview

Contents:
Project Summary Motivation Background Interproximation B-Spline Filters Automatic Smoothing and Joining Objectives Interproximation B-Spline Filters Automatic Smoothing Automatic Joining Approaches Interproximation B-Spline Filters Automatic Smoothing Automatic Joining Work Plan Consultant's Work Impact of the Proposed Research Transfer of Resulting Technologies

Project Summary:
The techniques of shape modeling and design in the following four areas will be broadened and improved.

First, we will develop computation techniques that combine interpolation and approximation into a single process (called Iinterproximation [16,17]) for both the curve and surface design problems. The curve and surface representations that will be considered here include B-splines, NURBS, Beta-splines and rational Beta-splines [4,5,8].

Second, we will further study different ways of building polynomial (integral) and rational B-spline curves and surfaces as well as their properties when viewed as digital filters [33]. We will especially focus on even-degree B-spline curves and surfaces whose joints are at half integer values instead of integer values. This is of interest because it is known that, when viewed as digital filters, the former behave in a similar fashion to odd degree B-spline curves and surfaces with joints at integer values [56]. Consequently, fitting using even degree B-spline curves and surfaces, and the smoothness of the resulting curves and surfaces, deserve further study as well.

Third, we will build a general model for the automatic smoothing of sharp corners and edges formed by intersecting parametric surfaces in the design and modeling process. The number of intersecting surfaces can be any integer. The work performed here will also include filling an n-sided hole with an n-sided patch [15,51,66] with n >= 3.

Finally, a general model will be developed for the automatic smooth connection of disjoint parametric surfaces. The number of surfaces is not limited. The work will also include the computation of intersection curves of multiple parametric surfaces. The automatic smoothing and joining models will be built for piecewise surfaces that can be converted into composite Bezier surfaces, these include B-spline, Beta-spline, NURB and rational Beta-spline surfaces.

The interproximation problem will be solved by minimizing the energy of the curves or surfaces to achieve "fairness" of the resulting interpolating curves or surfaces [16,40,43-45,49]. The second problem will be studied from the point of view of "digital filters" [33,56] to find the most appropriate form of even-degree B-spline basis functions and even-degree B-spline curves and surfaces first, and then develop (parallel) interpolation algorithms based both on the Iinverse filtering process [33] and the traditional method of solving a system of equations [9,10,18]. The automatic smoothing and joining models will be built on top of a blending technique [12] similar to that of Catmull-Rom splines [14,23] that constructs a blending surface smoothly connecting n surfaces along n "rail curves" determined by the blending area control data.

The proposed research will be carried out at the University of Kentucky in three years with Prof. Brian A. Barsky at the University of California, Berkeley, as a consultant.

1. Motivation

Computational techniques for shape modeling and design are rapidly becoming important tools for modern industrial design and manufacture. Computer models are replacing physical models. They are cheaper to construct, easier to change, and simpler to analyze. Computer-generated images increase productivity by allowing rapid and accurate visualization during design. This permits the early detection of errors which avoids the fabrication of erroneous components and costly redesign during the manufacturing phase. Applications include the design and manufacture of car bodies, ship hulls, airplane wings, and mechanical parts as well as a large variety of ducts, blends, and fillets. Factory automation is being revolutionized by this methodology.

Underlying this technology are mathematical techniques for the representation, specification, manipulation, and analysis of free-form curves and curved surfaces in an interactive computer environment. A large variety of mathematical formulations are used, such as Gordon surfaces, Coons surfaces, Bezier curves and surfaces, B-splines/NURBs, Beta-splines, etc. Background information on these issues can be found in [4]. Despite these advances, the problems of representing and manipulating freeform curves and surfaces is nonetheless far from solved. Instead, it is the case that still many important open theoretical and practical issues need to be explored to provide effective tools for industrial design.

2. Background

Interpolation, Boolean operations, automatic smoothing (or rounding) and joining are major techniques in shape design/modeling and related areas.

Interpolation is the process of constructing a parametric curve or surface that passes through a set of data points (called interpolation points) sampled from existing objects or determined by some design criteria. The resulting curve or surface should faithfully reflect the shape of the desired image or object. Boolean operations are operations such as union, intersection and difference that are used in synthesizing complicated objects from simple ones [34]. Surface intersection is the core procedure in performing these operations. Automatic smoothing is the process of smoothing the intersection of two (or more) distinct surfaces (Figure 1) [64]. It is intended to remove sharp edges and corners from an object. Automatic joining is the process of smoothly joining two (or more) distinct surfaces (Figure 2) [64]. It serves to connect disjoint features of an object that are constructed separately.

file f-smooth.grn width 6 height 2 Figure 1. Smoothing the intersection of two surfaces file f-join.grn width 7 height 1.5 Figure 2. Joining two disjoint surfaces

These techniques have been extensively studied before. However, none of them are completely developed to meet the requirements of today's applications.

In the following, we will review and discuss problems in four areas that require further work, with the surface intersection problem treated as a subset of the automatic joining problem.

2.1 Interproximation

Modeling the shape of an image or an object frequently uses techniques of parametric curve and surface interpolation. The result of the specific interpolation process depends on two factors: the interpolation points and the interpolation method.

A good interpolation method should generate a curve or surface that faithfully reflects the shape of the desired image or object using a relatively small number of interpolation points. Given the interpolation points, this is usually achieved through the selection of an appropriate curve/surface representation and interpolating parametric knots (parameter spacing). Spline curves and surfaces are frequently used in the interpolation process due to their local control property [4,22], small energy [39,43,49], and numerical stability [4,22]. The first property enables local modification of the resulting curve or surface [4,22], while the second one facilitates its geometric smoothness [49]. Interpolation using B-spline curves and surfaces has been extensively studied with efficient algorithms being developed for both sequential and parallel environments [9-10,18].

file f-inter-1.grn width 6 height 2 Figure 3. Cubic B-spline interpolating curves obtained with (a) uniform, (b) chord length, and (c) centripetal parametrization.

Actually, the geometric smoothness of the resulting interpolating curve and surface depends on the parameter spacing as well. Appropriately spaced interpolating knots not only reduce the energy of the resulting curve or surface, but also avoid the occurrence of "oscillations" and "loops" [49].

Oscillations and loops can also be removed by applying "tension" to the interpolating curves and surfaces [7,20,28,55,58,59]. However, an appropriate parametrization process should always be considered first.

It is generally believed that the knots should be chosen as proportional to the cumulative chord lengths of the data polygon [1,22]. However, according to results obtained by E. T. Y. Lee [48,50], a more appropriate way would be to use the so-called "centripetal model" to define the knots. The resulting interpolating curves usually are "fairer" than those obtained with the uniform or the chord length parametrization, see Figure 3.

Interpolation points also have a major impact on the "shape" of the resulting curves and surfaces. These points, either sampled from existing objects or determined by some design criteria, should be selected so that shape of the data polygon would be close to the shape of the desired image or object. On the other hand, the number of interpolation points should be kept low to avoid extensive computation cost. A rule of thumb is to choose more points in regions with large curvature and fewer points in regions with small curvature. Unfortunately, no precise criterion has yet been given on this particular issue.

A problem commonly encountered in the selection of interpolation points is uncertainty [16,17]. This is especially true in the reconstruction of natural phenomena or digitized images, motion detection, and CAD applications. For instance, in sampling data from a digitized picture, one usually obtains only a range of the data points, instead of the exact "locations" and "numerical values". In the design process (using fitting techniques) of 2D and 3D shapes, it is also quite common that the designer would know the location of only a few critical points with the remaining points to be created (or arranged) in certain regions through trial-and-error. Consequently, the fitting data may exist in two forms: "points" and "regions". The regions specify the possible ranges of the uncertain data.

Typical spline curve and surface interpolation techniques are not appropriate for these applications as they only deal with exact data points. We need a fitting method that can do a combination of interpolation and approximation; that is, the method should interpolate the data points that are exact and approximate the uncertain ones by passing through the regions that bound the uncertain data points (Figure 4). In addition, the generated curve should be "fairer" than the other curves that satisfy the above fitting condition. Such a process is called "interproximation" as it is a combination of interpolation and approximation [16,17].

file f-inter-2.grn width 2 height 2 Figure 4. A curve that interproximates the given data.

Previous work in this area has been done by Ritter [57], who presented a method to the generalized Hermite-Birkhoff interpolation problem in Sobolev space for spline functions. Simply stated, his solution allows both the function itself and its derivatives to interproximate the given data at the given knots. Ritter's solution is general. However, for applications in computer-aided geometric design (CAGD) and related areas, fitting derivatives to given data usually is not required. Two more specific algorithms for the construction of a cubic spline curve and a cubic B-spline curve that interproximate the given data, respectively, have been recently presented [16,17]. The basic idea is to minimize the "energy" on both the x and y components of the possible interproximating curves, and then convert to a "minimization problem" for some "quadratic form". Therefore, geometric smoothness of the curve is guaranteed. One advantage of this technique over the ordinary curve interpolating techniques is that it can be used to design a curve with desired shape in fewer steps. It can also be used to remove undesired oscillations generated on an ordinary interpolating curve. This is achieved by specifying a few regions between interpolation points to bound the behavior of the interpolating curve. The surface interproximation problem has not yet been studied.

Further study of the interproximation problem is needed for several purposes. These include interproximation using more flexible curve representations such as Beta-splines [5], and NURBS, as well as the surface interproximation problem. The study of these problems is essential for two reasons. First, and obviously, there is a need for such techniques in fitting uncertain data, as mentioned before. Second, we believe that current approach in 2D and 3D geometric design is not the best possible; one ought to use the techniques of interproximation instead of the traditional "interpolate-and-adjust" method [3,24]. Note that when designing the shape of a 2D or 3D object, a designer does not know all the details of the object but probably has only a rough sketch of its would-be shape.

Hence, in addition to a few critical points, most of the points are still uncertain, waiting to be determined through the design process. That is, the designer might know the exact locations of a few critical points, but a lot of them are still uncertain.

Using the current approach, since the designer is required to explicitly specify all the interpolation points to generate a curve or surface, if an interpolation point is uncertain, it would have to be "estimated" (or, "guessed" at). Such an approach certainly would take the designer many trial-and-error iterations to achieve a desired shape since the estimated interpolation points do not provide any flexibility at all for the system to seek an alternative. A better approach would be to let the user specify the locations of the "certain" points as well as a possible range for each of the remaining points, and then let the system determine the smoothest curve or surface that interproximates these data. The resulting curve or surface can be improved by reducing the ranges of the uncertain points to further confine the curve's shape (reducing the possible range of a data point to a single point forces the curve or surface to interpolate that point). Since the resulting curve or surface of each iteration of this process has more room to achieve its smoothness than the curve that would interpolate explicitly specified points, and the result of the iterations is cumulative, this consequently facilitates the design of an object.

2.2 B-spline Filters

Another problem with the current B-spline curve/surface interpolation techniques is that even-degree B-spline curve/surface interpolation is completely overlooked because it is believed that even-degree B-spline curves and surfaces are not appropriate for the curve and surface interpolation problem [1]. Indeed, given the joints of an even-degree B-spline curve, one may not be able to determine the control vertices of the curve [33]. This follows from the observation that the transfer functions of even-degree and odd-degree B-splines behave differently when viewed as digital filters.

B-spline curves and surfaces have wide applications in image processing as well [25,41].

The transfer function of a filter is obtained from the Fourier transform of the filter and describes the behavior of the filter under all input frequencies. Fig. 5 shows the transfer functions of filters generating B-spline curves of degrees 2, 3, 4, and 5.

Figure 5. Transfer functions of B-spline filters of order (= degree+1) 3, 4, 5, and 6.

The odd-degree B-splines behave like a low-pass filter, passing zero-frequency signals with no attenuation and other signals with more and more attenuation as the frequency of the signal increases. The even-degree B-splines attenuate the low and high frequencies only slightly. Therefore, even-degree B-splines generate curves and surfaces containing high magnitude high frequencies. This means that odd-degree B-splines generate smoother curves.

Besides, even-degree B-splines attenuate the mid-frequencies considerably. Actually, they attenuate certain frequencies completely such as frequency 1/4 for B-splines of degree 2. In terms of B-spline curves, this means that given the joints of an even-degree B-spline curve, we may not be able to determine the control vertices of the curve, since information about the original signal at least at one frequency is lost. The odd-degree B-splines do not have this problem. Hence, odd-degree B-spline curves and surfaces are more appropriate for interpolation problem while even-degree B-splines should be avoided. This is consistent with the comment made by Ahlberg, Nilson and Walsh: "polynomial splines of even degree interpolating to a prescribed function at mesh points need not exist" (see Chapter 4 of Ahlberg, Nilson and Walsh [1]).

A recent result by Rabut [56], however, shows that the above observation does not hold if the even degree B-splines are defined with joints at half integer values instead of integer values. According to his result, even degree uniform B-splines defined this way, when viewed as digital filters, behave in a similar fashion to odd degree B-splines (with joints at the integer values) (Figure 6). The study was based on "central" B-splines [63] instead of B-splines defined using the Cox-de Boor recurrence relation or divided differences [22]. Note that central B-splines have their joints at half integer values when the degrees are even while B-splines defined using the Cox-de Boor recurrence relation or divided differences will always have their joints at integer values.

Figure 6. Transfer functions of B-spline filters where even degree B-splines are defined with joints at half integer values.

Rabut's result is surprising but does not conflict with our previous observation which was based on even-degree curves and surfaces defined with joints at integer values. However, his result does raise an important point, i.e., the traditional way of building even-degree B-spline curves and surfaces is not appropriate for certain applications such as the curve and surface interpolation problem. The construction process of even degree spline curves and surfaces ought to be reconsidered. Besides, the problem of interpolation using even degree B-spline curves and surfaces deserves serious study since our previous observation about even degree curves and surfaces does not hold any longer if the joints are at the parametric knots.

We believe that even-degree spline curves and surfaces should be able to play a more significant role in various applications than just being "introduced principally in situations in which they combine with odd-degree splines to help clarify the total picture", as Ahlberg, Nilson and Walsh put it (see Chapter 4 of Ahlberg, Nilson and Walsh [1]). One particular reason is that conics and quadrics, two important primitives in geometric modeling, can be represented precisely by even degree rational spline curves and surfaces [42]. Note that representing conics and quadrics using even-degree (rational) B-spline curves and surfaces requires less time and effort in computation, visualization and performing surface operations than using cubic NURB curves and surfaces.

2.3 Automatic Smoothing and Joining

The smoothing of intersecting surfaces is achieved by constructing an auxiliary surface to smoothly connect the given surfaces along some "rail curves" close to their intersection [64,65] (Figure 1(a)). The surface used for this purpose is called a "smoothing surface". This process is intended to remove sharp edges and corners from an object and, consequently, may dissipate stress concentration, enhance fluid flow, and improve aesthetics in the resulting object [64, 65]. A typical example is shown in Figure 1(b) where a surface is used to smooth the intersection of two intersecting pipes.

In the joining process, a surface is used to smoothly connect the given disjoint surfaces along rail curves close to their boundary curves [64,65] (Figure 2(a)). A surface used for this purpose is called a "joining surface". This process serves to connect disjoint features of an object. An example is shown in Figure 2(b) where a surface is used to join two coaxial pipes with different radii.

The surfaces to be smoothed or joined are collectively called "base surfaces" while smoothing surfaces and joining surfaces are sometimes collectively called "blending surfaces". The smoothness of the smoothing and joining process is usually established by requiring tangent continuity between the blending surface and the base surfaces at the rail curves. The rail curves in some cases are not isoparametric lines thereby posing additional difficulties in the smoothing and joining process. Automatically providing the smoothing and joining capability is important since the mathematical complications in guaranteeing the smoothness and correct placement of the required blending surfaces may consume a large part of the designer's time [65].

Automatic joining on implicit surfaces was first studied by Hoffmann and Hopcroft [35]. They describe a so-called potential method for connecting two coaxial cylinders using quartic implicit surfaces. This work was later generalized by Warren on arbitrary quartic implicit surfaces [64,65].

Automatic smoothing on implicit surfaces has been studied by Rossignac and Requicha [61,62]. In addition, Middleditch and Sears [54], Hoffmann and Hopcroft [37], and Rockwood and Owen [60] have also made substantial contributions in this problem. A more recent result in this topic was presented by Kosters [47] in which he considered the smoothing of a corner formed by n hyperplanes in n-dimensional space. Unfortunately, these methods do not have apparent application to parametric surfaces which are more widely used in practice.

Automatically smoothing edges and corners of solids using parametric blending surfaces was first studied by Chiyokura [19]. This work, implemented in the Ricoh Co.'s solid modeling system, Designbase, allows a designer to perform rounding operation on solids with free-form surfaces. A sharp corner is replaced with a Gregory patch [15] to guarantee smoothness. The corner may be the intersection of arbitrary number of planes.

Automatically smoothing sharp edges formed by parametric surfaces was first discussed by Filip [27], a former student of Barsky at Berkeley [26]. This work, developed at Automation Technology Products, avoids the \fIgaps\fR between the base surfaces and the blending surface by constructing the rail curves in the parameter space rather than the model space.

It requires the computation of tangent vectors on the "base surfaces" to guarantee the smooth connection of the base surfaces with the blending surface. The technique can also be used to handle the smooth join of two disjoint parametric surfaces. A novel approach of treating the smoothing surfaces as solutions to differential equations with boundary conditions has been reported by Bloor and Wilson [13]. A more recent result based on pointwise interpolation of rail curves is presented by Koparkar [46]. A guiding trajectory has to be used to rectify undesirable cross section shape of the smoothing surface. This work cannot handle the smoothing of sharp corners.

As far as automatic joining of parametric surfaces is concerned, most of the parametric surface patches used in CAGD are examples of joining surfaces (by viewing the boundary curves as the rail curves in the joining process). The S-patch [51,52] and Gregory Patch [15] can also smoothly join multiple surface patches. The construction of these surface patches, as well as the method proposed by Filip, Bloor and Wilson, and Koparkar, all require the tangential data at the rail curves to guarantee the smoothness of the joining process.

A comprehensive summary of blending techniques in general can be found in Woodwark [67]. A

Smoothing and joining techniques for parametric surfaces are not mature yet. The main reason is that it has not been recognized that smoothing and joining are actually a blending process [12]. Instead, the blending surfaces are constructed by solving some interpolation conditions [13,19,27,46]. A direct consequence of this, since the blending surfaces do not inherit much geometric features of the base surfaces, is that they do not provide a natural and smooth transition of the shape of the base surfaces. Furthermore, they also require the tangential data at the rail curves to guarantee the smoothness of the joining process. A blending model that can be used for both problems has been reported recently [12]. The concept employeed in this blending model is similar to that of Catmull-Rom spline (this was originally proposed in [14] and a geometrically-continuous generalization was later developed by DeRose and Barsky [23]); the control vertices of a parametric surface are replaced with appropriate control curves or surfaces. The smoothing or joining surface will implicitly interpolate the rail curves and the tangents of the rail curves, to fulfill the requirements of the smoothing or joining process. However, the smoothing or joining surface is not the result of solving some interpolation conditions; rather, it is generated by blending the base surfaces using appropriate blending functions. Therefore, no tangential information is required from the user, and the smoothing or joining surface automatically provides a smooth transition of the shape of the base surfaces (Figure 7) because the resulting blending surfaces inherit more geometric features of the base surfaces through the blending process than they would by solving the interpolation conditions. This approach does not depend on any particular surface representation; it is easy to incorporate in a geometric modeling system. It smooths the sharp edges and corners simultaneously.

Currently, smoothing technique based on this blending model has been developed for three intersecting surfaces (Figure 8) and joining technique based on this blending model has been developed for two disjoint surfaces (Figure 7). The smoothing process covers not just the corner but the adjacent sharp edges as well. The blending model also provides new approaches to both the n-sided hole filling problem [15,51] and the parametric surface/surface intersection problem. The technique has also been used to provide a new approach to solve the parametric surface/surface intersection problem. The surface/surface intersection problem is solved by adjusting the intersecting surfaces instead of the computed intersection curve(s). to get an exact representation of the intersection curve(s). The results developed here can be used with the loop detection criterion-based intersection algorithms developed by Hohmeyer [38], a Ph.D. student of Barsky, to get exact representation of the intersection curve(s). General models should be developed so that smoothing and joining of arbitrary number of parametric surfaces can also be performed. These functions are essential for a CAD system as a designer may indicate only a few critical surfaces, with the remaining surfaces to be chosen by the system so as to make the surface of the resulting object smooth.

Figure 7. Smooth transition of the shape of two disjoint base surfaces.

Figure 8. Smoothing a sharp corner formed by three surfaces.

3. Objectives

We propose to broaden and improve the computation techniques of shape modeling and design in the following four areas.

3.1 Interproximation

First, we will develop interproximation techniques that combine interpolation and approximation into a single process for both the curve and surface design problems. The problems will be considered for different curve and surface representations. The performance of the interproximation processes using different curve and surface representations will be compared.

First, we will further investigate the curve interproximation problem and study the surface interproximation problem. The problems will be studied using different curve and surface representations. The performance of the interproximation processes using different curve and surface representations will be compared.

The curve and surface representations to be considered here include cubic B-splines, Beta-splines [5] and NURBS.

The investigation of the interproximation process will comprise two aspects: the "computation techniques" and "geometric smoothness". The first aspect is focused on the development of efficient algorithms whereas the second one is based on examining the $"fairness"$ of the resulting curves and surfaces.

Actually the second aspect is our main task here since a fairer curve or surface will reduce the designer's effort required to find the optimal design. Therefore, the factors that would affect the geometric smoothness of the resulting curves and surfaces will also be considered. These include parametrization methods and input format.

The study of the surface interproximation problem also includes studying the solvability of the problem for different data types (scattered data and gridded data).

The comparison of performance for different curve and surface representations includes

numerical stability;

computational efficiency;

smoothness of the resulting curve or surface; and

suitability for a particular data type (for the surface case only).

The performance of our previous results [16,17] will also be compared with the algorithms developed for the curve representations considered here.

3.2 B-spline Filters

Second, we propose to do a thorough study on how to build even degree polynomial (integral) and rational B-spline curves and surfaces and, based on the findings, perform a thorough study of the even-degree B-spline curve and surface interpolation problem.

The study of the first part is aiming at finding the best way to build even degree spline curves and surfaces so that they would behave in a similar fashion to their odd degree counterparts. The study will be performed in the general sense, i.e., based on non-uniform knot sequences. The findings obtained here should apply to other spline representations such as Beta-splines as well.

The study of the even degree spline curve and surface interpolation problem is aiming at finding the most efficient (parallel) algorithms for B-splines and Beta-splines. The study will be performed based on the curve and surface representations obtained in the first part.

The performance of the algorithms such as the rate of convergence will be investigated and compared with the odd degree counterparts, and the "smoothness" (from the digital filter point of view [25,33,41]) of the generated curves and surfaces will also be studied.

The study of the interpolation problem will also include the suitability of even degree spline curves and surfaces in various applications.

3.3 Automatic Smoothing

Third, we will build a general computation model for the smoothing of sharp corners and edges formed by intersecting parametric surfaces in the design and modeling process.

The work will focus on the smoothing of sharp corners formed by n surfaces with n >= 4. This problem will be called n-sided smoothing. It includes the smoothing of the corner and the adjacent edges. The study will be performed in a general sense, i.e., we will consider an object with several corners. Therefore, the smoothing of one corner should be coordinated with the smoothing process of the remaining ones.

The techniques developed here will also be used to "fill" an n-sided hole [15,51] with an n-sided patch only that, in this case, the patch will be interpolating rail curves close to but different from the boundary of the hole. The generated patch should be a blend of the adjacent patches so it provides a smooth transition of their shapes.

The computation model will be built for piecewise surfaces that can be converted into composite Bezier surfaces such as B-spline, Beta-spline and NURB surfaces.

3.4 Automatic Joining

Finally, a general computation model will be developed for the smooth connection of disjoint parametric surface, such as the joining of several pipes centered at the same point. The work will be concentrated on the smooth joining of three or more disjoint surfaces. This problem will be called n-sided joining.

Since the surface/surface intersection problem can be viewed as a curve/surface joining problem [12], The study of the n-sided joining problem will also include computing the intersection curves of multiple parametric surfaces.

The automatic joining model will also be built for piecewise surfaces that can be converted into composite Bezier surfaces such as B-spline, Beta-spline and NURB surfaces.

4. Approaches

4.1 Interproximation

The interproximation techniques to be developed for B-spline, Beta-spline, NURB and rational Beta-spline [8] curves and surfaces will be performed in three steps:

the selection of parametrization methods,

the selection of "end" and " boundary conditions", and

minimization of the curve or surface "energy" to achieve "fairness" of the resulting interpolating curve or surface.

E. Lee's centripetal model [48] will be used to define the parametric knots for the interproximating curve (hence, the knots will in general be non-uniformly spaced) in that it reduces the energy of the resulting curve and avoids the occurrence of "oscillations" and "loops". However, the centripetal model cannot be used for the surface interproximation problem directly. A study will be performed to determine the parametrization scheme for the surface interproximation problems.

In our previous work [16], the user is required to specify the derivative of the interproximating curve at the left most data point (or region). This is bothersome and not easy to estimate precisely. The user should not be imposed any extra burden other than inputing the fitting data. Therefore, appropriate "end" and "boundary" "conditions" need to be selected to make the problem solvable. The traditional ways of setting the end and boundary conditions [6] are not appropriate here as the fitting data at the end or the boundary of the data range are not necessary to be points [17].

The "fairness" of the resulting interproximating curve will be achieved by minimizing the "energy" of the curve. Two different ways of defining the energy will be used here: using "second derivative" [45] and using "curvature" [40,43-44]. A comprehensive discussions on the definition of energy can be found in Lee [49]. The "fairness" of the interproximating surface for gridded data will be achieved through a two-stage process: first, minimize the energy of the "interproximating curves" that interproximate the given data in u direction, then minimize the energy of the "interpolating curves" that interpolate the control vertices of the interproximating curves constructed in the first stage in the v direction. This is motivated by the observation that a tensor product spline surface fitting problem can be separated into a two-stage curve fitting problem [18,22]. Further study is needed for "fairing" surface which interproximates scattered data. Related work in this area can be found in [29-32].

The minimization of energy will be performed as a conversion process of the problem into a minimization problem for some quadratic form [2] as the unknowns (namely, control vertices) in the energy definition satisfy a quadratic form [16,57].

Criteria for the comparison of performance in numerical stability, computational efficiency, smoothness of the resulting curves and surfaces, and suitability for particular data type will be created. We shall also consider the overall performance by mixing multiple criteria in a single interproximation case.

4.2 B-spline Filters

The development of even-degree B-spline curve/surface interpolation techniques will be performed in two steps:

build a new model for representing even-degree B-spline curves and surfaces, and

find even-degree B-spline curve and surface interpolation algorithms based on the new representation.

The first step involves two tasks:

finding the parameter values where the joints of the curves and surfaces should be defined, and
finding the appropriate form of even-degree B-spline basis functions.

Two possibilities will be explored for the second task. First, use the existing B-spline basis functions but translate them accordingly. Second, construct new even-degree B-spline basis functions whose joints are defined at the parameters identified above.

Regarding the interpolation algorithms, we need to study two problems: (1) How should the parameter domain be defined? (2) How should end and boundary conditions be constructed? These problems are directly related to the smoothness of the resulting curves and surfaces. They also affect the mathematical work of the interpolation process.

The computation of control vertices of the interpolating curve or surface when the knots are uniformly spaced will be carried out in two approaches: the inverse filtering process [33] and the traditional method of solving a system of equations [9,10]. The possibility of using parallel techniques in the "convolution process" [33] will be explored.

The computation of control vertices of the interpolating curve or surface when the knots are non-uniformly spaced will be carried out only in the traditional approach since the inverse filtering process does not work for non-uniformly spaced data. The technique of cyclic reduction [18] will be applied to the traditional approach to achieve parallelism.

Build criteria of suitability for interpolation using even degree spline curves and surfaces for different applications. This includes comparing the smoothness of the resulting curves and surfaces using both odd degree and even degree spline curves and surfaces for conics and quadrics.

4.3 Automatic Smoothing

The automatic smoothing model will be built on top of a blending technique that constructs a blending surface smoothly connecting n surfaces along n rail curves determined by the blending area control data [12]. The rail curves are connected endpoint to endpoint.

The construction of the blending surface requires the development of two major techniques: (1) the design of n-sided blending functions, and (2) local parametrization. The n-sided blending functions allow an n-sided blending surface to be constructed on a "virtual" basis whereas the local reparametrization process maps the virtual n-sided blending surface into an "actual" blending surface.

An n-sided blending functions can be constructed as the composition of n Bezier triangular functions. However, we will also study the possibility of constructing an n-sided blending function by manipulating an S-patch [52] to satisfy certain boundary conditions.

The local reparametrization process requires reparametrization functions to be constructed for each of the blending areas involved in the blending process. The basic tools to be used here include 2D B-spline interpolation techniques and Coons patches [21].

The consideration of a general smoothing problem will be achieved through the design of an appropriate I/O interface which will not only build a description of the topological relationship of the base surfaces, but also the blending area control data to be input by the user.

The construction of the blending surface will be carried out in three steps: (1) find the virtual intersection curves (2) construct the rail curves, and (3) construct the reparametrization functions. The first step is also required in the multiple surface intersection problem.

The construction of the virtual intersection curves will employ a new loop detection criterion [38] to find a sequence of discrete points along the actual curves between any two intersecting surfaces and then interpolate the pre-images of these points in the parameter space of the surfaces.

Two rail curves will be constructed for each actual intersection curve. These rail curves will be constructed using the virtual intersection curves constructed in the first step and the blending area control data input by the user.

The virtual intersection curves and the rail curves constructed in the first two steps are then used to construct reparametrization functions for the blending areas. This step will also construct the intermediate maps required in the subsequent mapping process (mapping triangles generated in the domains of the base surfaces into the modeling space).

The technique developed here will also be used to fill an n-sided hole with an n-sided patch [15,51,66]. The patch will be interpolating rail curves close to but different from the boundary of the hole. The generated patch will be a blend of the adjacent patches so that it would provide a smooth transition of their shapes.

4.4 Automatic Joining