-Continuous Composite Bicubic Bezier Spline SurfaceComputer Graphics & Geometry
-Continuous Composite Bicubic Bezier Spline SurfaceA. Vermel
Moscow Institute of Physics and Technology
Department of Aeromechanics and Flying Machines
140160 Zhukovsky Russia
Tel.: 007 ( 095 ) 556 4362
E-mail: vermel@gemma.ru
Abstracts: The problem of automatic construction of a composite bicubic Bezier surface approximating a given parametric surface to a required tolerance is discussed in this paper.
Algorithms for Bezier patch boundaries construction and iterative optimization of internal patch control points are developed to construct an approximating surface. The approximating surface is constructed to be approximatelycontinuous at patch boundaries which allows to achieve higher global smoothness. The required approximation tolerance and patch junction smoothness is achieved by means of iterative subdivision.
The technique is designed for conversion of parametric surfaces of special type to a universal surface representation format - bicubic Bezier spline surface. This is necessary both for uniformity of surface representation within a single CAD system and for data exchange between different CAD systems.
Industrial implementation of the technique was made within a system for computer-aided design of aerodynamic models of the Central Aero-Hydrodynamic Institute GeMMa-3D.
Keywords: surface approximation; surface conversion; Bezier surface; data reduction; bicubic patches, approximate tangent continuity
Introduction
A number of universal geometric data representation standards such as IGES, STEP and some others are generally accepted to be used for data exchange between different CAD systems. They have a set of means for description of geometric objects. Transfer of objects beyond this set requires their conversion to a representation within the set of supported types of geometric objects. Quite often no exact conversion exists. Possible solution is to find an approximate representation, that is approximation within a certain tolerance. Again, support of a large set of different types of parametric surfaces within a CAD system implies some overhead, namely, the need to support data persistence, conversions and geometric operations for all different types of surfaces. This overhead may be reduced if immediately after construction any surface is approximated by some selected type of surface and all the subsequent work is done with the surfaces of this type. While approximation of curves is by now thoroughly studied and presents no significant difficulties, high quality surface approximation is still an important problem. This paper describes a suit of algorithms for local approximation of arbitrary two-parametric surfaces defined on a rectangular region {(s0, t0), (s1, t1)} with a composite cubic Bezier spline surface, which is supported by all popular standards of data exchange. Two requirements are to be taken into account during surface construction. Firstly, not only the surface should fit to the initial surface within the specified tolerance, but also it should have no unwanted waves and wiggles. Secondly, the patches the surface is composed of should join with certain smoothness conditions being valid. The conventional approach to surface construction and approximation is to provide the best assembly of patches possible with the type of surface representation in use (
continuity for cubic Bezier). It often leaves limited freedom to improve the surface shape quality. During development of the approximation technique presented here a different strategy was followed [1]. As long as the priority is to ensure good shape of the surface, the approximating surface is constructed to be approximately continuous at patch boundaries, so that angle between surface normals at the boundaries is below a specified limit. The resulting surface should be acceptable for such applications as NC-machining considering finite part surface finishing tolerance.
The main design requirements for this technique were the following:
- representation of approximating surface is composite cubic Bezier spline
- minimization of waves of a Bezier patch size to improve the surface shape
- compact surface representation, data reduction
1. Initial and resulting surface representations. Approximation technique outline
is defined so that at any point ( s, t) of the parameter range we can obtain 
.
The resulting surface is [2], Fig.1 a rectangular patchwork of ( m x n) Bezier patches 
, where k=1,...,m, l=1,...,n , and parameters of any patch 
lie within ranges 
, 
. Each patch is a tensor product 
, where 
- 3-d degree Bernstein polynomials , 
- Bezier control points , that is, a Bezier patch is defined by 16 points (4 x4) . Total net of control points of a composite Bezier surface is formed by , i=0,...3m, j=0,...,3n. Patches are bounded by Bezier curves with control polygons consisting of points of each 3-d row/column of the net.
|
|
|
Fig.1 Composite bicubic Bezier spline surface. Control polyhedron of a Bezier patch. |
2. Preliminary construction of boundaries of surface patches
It is necessary to construct a net of two families of Bezier curves, approximating parametric lines of the initial surface, so that cells of the net were bounded by four Bezier segments. Then after supplying any cell with four internal control points we shall obtain a complete Bezier patch. To fulfill this construction we make use of the algorithm of joint local approximation of a family of curves, presented in [2]. Given a family of curves
, this algorithm constructs a family of composite cubic Bezier curves 
approximating them with a specified tolerance . The resulting curves 
have equal number of Bezier segments q . Ends of the segments lie on the curves 
of the initial family and values of parameters of corresponding ends of segments on curves are equal. In other words 
for all ends of segments 
of all curves 
, where 
- parameter of i- th ends of segments of all curves of the resulting family.
We define two families of parametric lines of the initial surface using two sets of fixed values of parameters 
and 
, 
, 
, where 
and 
are of the parameter sets , M, N - the numbers of parametric lines in the families . The algorithm of joint approximation will be applied to these families of curves, Fig. 2.
|
|
|
Fig.2 Joint approximation of a family of parametric curves with composite Bezier curves. |
Initially let's select a set several parameter values uniformly distributed between
and 
, and define on its base a family of parametric lines 
. The family 
is then approximated with a specified tolerance to give a family of Bezier curves 
each consisting of a certain number of segments 
. Ends of Bezier curves segments have corresponding parameter values 
. On base of the new set of parameter values a family of curves 
is defined. Approximation of it produces a family of Bezier curves 
with ends of segments at parameter values 
.
Then we subsequently consider families of pieces of parametric lines corresponding to the set of parameter values . The pieces are bounded by adjacent parametric lines of the other family, which was approximated on the previous step: 
, 
, 
, where k and k+1 - the numbers of adjacent parametric lines 
. Joint approximation of each of the families of pieces of parametric lines results in families of Bezier curves .
If curves of any of the obtained families contain over 1 Bezier segment, then the set of parameters is expanded to include new parameter values, corresponding to ends of segments. In this case we need to reconstruct curves 
as the number of parametric lines increased . This reconstruction is done by means of approximation of pieces of parametric lines bounded by adjacent parametric lines of the family 
. This may lead to expansion of set of parameter values which in its turn will require reconstruction of curves 
.
This procedure is to be repeated until we obtain two final sets of parameter values and defining families of parametric lines such that the approximating Bezier curves form a net with cells bounded by four Bezier segments.
3. Construction of internal control points of Bezier patches
The choice of internal control points of Bezier patches should provide both maximum closeness to the initial surface and satisfactory assembly of segments (in terms of directions of surface normals at patch boundaries). Let's require that a patch under construction has cross derivatives at middle points (parameters equal to 0.5) of the boundaries parallel to the corresponding derivatives on the initial surface, Fig. 3 , which is a simplified condition suggested at [4]. Validity of this requirement provides coincidence of normals to adjacent Bezier patches at the middle point of their common boundary. Suppose initial surface is
.
|
|
|
Fig. 3 Construction of internal Bezier points of a surface patch. |
is given by :
Boundary cross derivatives being parallel imply:
, 
- parameter value such that 
is the closest point of curve 
to the point 
, i=0, 1
- parameter value such that 
is the closest point of curve 
to the point 
, j=0, 1
It follows that we have 4 vector equations to determine internal Bezier control points 
,
,
,
with 4 extra scalar unknowns 
,
,
,
.
With respect to internal Bezier control points the set of equations can be written as:
(1)
where:
- constant vectors, depending on known boundary Bezier control points,
.
Since 
, then 
and sum of the rows of matrix A multiplied by {1, -1, -1, 1} is equal to 0.
Matrix A is singular , so in order to provide existence of solution of the equation set (1) we require that its right-hand side is consistent with matrix A, that is:
, or
(2)
Rank of the coefficient matrix of the equation set (2) may be equal to 3 or 2. In case of stronger degeneration ( all vectors 
are linearly dependent ), no solution can be found for the given patch boundaries.
If rank is equal to 3 , then the equation set (2) has one homogeneous solution .
Let's consider the case when rank is equal to 2 and the equation set (2) has two homogeneous solutions. This takes place when and only when vectors are coplanar . In particular, such degeneration occurs during approximation of a planar surface. Consequently, the equation set (2) has no solution when it's right-hand side, which is a linear combination of vectors 
, does not lie in the plane of tangent vectors . In the important case of approximation of a planar surface vectors are in the same plane as the initial surface and the equation set (2) has a solution. Yet if the equation set (2) is inconsistent, we can use as a solution such 
that minimize the residual of the equation set, and if the resulting patch is out of tolerance, it will be ruled out during subsequent subdivision.
To solve linear equations we employ a singular value decomposition technique [5] which is a numerically stable way to find solutions of degenerate equations and it provides a residual minimizing solution when no solution exists. With its aid the solution of the equation set (2) can be found as:
(3a) , when rank of coefficient matrix of equation set (2) is equal to 3
(3b), when rank is equal to 2
- nonhomogeneous solution , 
, 
- free coefficients at homogeneous solutions 
, 
.
When L is defined according to (3) , 1- st equation of the equation set (1) is a linear combination of the three others so it can be eliminated . The equation set (1) can be rewritten as :
(4), where
- right bottom minor of matrix À.
Matrix 
is well conditioned and can be easily inverted . Then we have :
(5)
Equation (5) together with (3a , b) expresses 
in terms of 
, or 
when vectors 
are coplanar .
To optimize approximation of points of initial surface we have following free variables : 
. When vectors are coplanar there is one more free variable - 
.
Optimization of these variables is a nonlinear problem. We solve it by iterations between least-squares optimization and parameter correction. .
Suppose a number of points is selected on the part of initial surface being approximated by a Bezier patch: 
. To find the internal Bezier points we need to minimize the sum of square deviations of points 
from the patch . Let's select the points uniformly distributed along the approximated part of surface . We define n parameter values 
uniformly distributed inside region [0, 1]. These parameter values determine n points on each of boundary curves of the patch. We then find points, which are closest to them, on boundary curves of the part of the initial surface. They have corresponding sets of surface parameters: 
,
, i=1,...,n, k=0,1. Surface points are defined as:
Then parameters of closest points of Bezier patch can be evaluated as:
from the corresponding points of Bezier patch is given by:
(6), where
is the part of 
defined by boundary Bezier points ,
is the part of defined by internal Bezier points .
D is minimal when 
. If are coplanar there is one more condition: 
.
(7a), when are not coplanar,
(7b), when are coplanar , where
- vectors and 
- scalar , determined by 
and boundary Bezier points .
Then substitution of (7) into (6) gives the following condition of minimum of D:
(8).
Equation set (8) represents the more general case of substitution of (7b). In case of substitution of (7a) we need to eliminate the last equation and the last column of the matrix on the left.
After solving (8) and substituting the solution into (5) we obtain the internal Bezier points of the Bezier patch 
.
4. Parameter correction
In the previous section we used approximate parameter values
of points of the Bezier patch under construction , which are closest to the approximated points 
of the initial surface . After the Bezier patch is constructed these values need to be corrected and the patch reconstructed giving a closer approximation . This operation should be repeated until convergence.
To correct the values of parameters we use a procedure described in [4].
On each step of correction we apply increments given by following expressions:
During iterations the residual vectors between the approximated points and the corresponding points of the Bezier patch tend to become normal to the patch.
After the iterations have converged, we can find the tolerance of approximation, which is the largest distance between the approximated points and the corresponding points of the Bezier patch.
5. Subdivision scheme to provide approximation tolerance
To make sure that the approximating surface fulfills the requirements 5, 6 of the 1-st section, which demand the surface to conform to the specified approximation tolerance and to the limit value of patch boundary normal discontinuity , we need to find the patches violating the requirements and subdivide the rows/columns of patches, which contain them. . The subdivision is done in two stages . 1. Determine all rows/columns of patches of the current approximating surface, which require subdivision. If normal discontinuity on a boundary between two patches is too large, then the subdivision should be done across the boundary, i.e. the row/column which contains both patches is to be subdivided. If a patch deviates from the initial surface beyond the tolerance, we need to decide on the subdivision direction. For this purpose let's approximate with composite Bezier curves the two parametric lines, passing through the parametric centre of the approximated part of the initial surface. The subdivision should be done along the parametric line, which is approximated with fewer number of Bezier segments. 2. Subdivide the determined rows/columns of patches. Bisection of the rows/columns of patches yield new parameter values to be added to the current sets of parameter values and , which are used to construct the net of patch boundaries. Using the new sets of parameter values, reconstruct the net of patch boundaries, as it was done in section 2. This may lead to additional iterative expansion of the sets. Then construct internal Bezier points of the patches to get a new approximating surface.
Repeating these two operations we finally get a surface conforming to the tolerance requirements 5, 6.
References
[2] I. D. Faux, M. J. Pratt : Computational Geometry for Design and Manufacture . Ellis Horwood, 1981
[3] A. Vermel : Approximation of framework curves with a bicubic Bezier spline surface. Technical Report. TsAGI , 1998
[4] J. Hoschek , D. Lasser: Fundamentals of Computer Aided Geometric Design . A K Peters , 1993
[5] G. E. Forsythe , Ì. A. Malcolm , C . B. Moler : Computer Methods for Mathematical Computations. Prentice-Hall, 1997Computer Graphics & Geometry
-continuous interpolation of a rectangular network of rational cubic curves. CAD , Vol. 28, No12, pp.1008-1016, 1996 .