The mixed directional difference-summation algorithm for generating the B´ezier net of a trivariate four-direction Box-spline

The mixed directional difference-summation

algorithm for generating the B´

ezier net of

a trivariate four-direction Box-spline

G. Casciola

_{E. Franchini}

_{L. Romani}

∗

a_{Department of Mathematics, University of Bologna,}

P.zza di Porta San Donato 5, 40127 Bologna, Italy.

b_{Department of Pure and Applied Mathematics, University of Padova,}

Via G. Belzoni 7, 35131 Padova, Italy.

Abstract

Trivariate Box-splines lack an efficient and general exact evaluation technique. This paper presents one possible and underexploited approach to solving this problem. The algorithm we propose is based on mixed directional differences and summations

for computing the B´ezier net coefficients of all trivariate four-direction Box-splines

of any degree over tetrahedral tessellations of the domain.

A Matlab package, called MDDS, for computing the B´ezier net both in the trivariate

and bivariate cases, is also provided.

Key words: Trivariate Box-splines, Recurrence Relations, Exact Evaluation,

Tetrahedral B´ezier Volume Decomposition, B-net.

AMS Classification: 65D17 68U05 33F99 65D07

1 Introduction

During the past twenty years, much research has been undertaken to study B´ezier

representations of bivariate Box-spline basis functions ([6], [7], [8], [24]). In contrast,

B´ezier representation of higher dimensional Box-splines has received much less

at-tention as an effective and powerful exact evaluation tool.

∗ Corresponding author.

Email addresses: [email protected] (G. Casciola),

In this paper we focalize our attention on trivariate Box-splines and we propose a new efficient computational scheme for exact evaluating the four-direction class of

such functions by computation of their B´ezier net over a tetrahedral tessellation of

the domain.

Trivariate Box-splines are a trivariate extension of uniform univariate B-splines. Tri-variate Box-spline evaluation is, in general, more difficult than uniTri-variate B-spline evaluation. General evaluation algorithms can exploit one or more of the following properties of Box-splines: (i) two-scale subdivision, (ii) Fourier transform, (iii)

re-currence definition formula, or (iv) tetrahedral B´ezier volume decomposition.

Subdivision leads to an approximate iterative technique which converges quadra-tically. The continuous inverse Fourier transform of the Box-spline can only be approximated with a discrete inverse Fourier transform, so inverse FFT evaluation is also an approximation [22]. Both of the two first techniques share the property that a large number of samples are computed at once and have similar asymptotic complexity measures.

While procedures (i) and (ii) provide an efficient computational scheme only if an approximate Box-spline is required, of the relevant evaluation techniques, just (iii) and (iv) are exact. Unfortunately, (iii) can be very expensive: the value of every Box-spline at any point is in fact computed one at a time. Only fairly low degrees Box-splines can be computed without too much difficulty and for completely general Box-splines the cost increases combinatorically with the number of direction vec-tors. With care, on restricted classes of Box-splines, this explosion can be contained somewhat, but a large amount of arithmetic is still needed for every sample.

Strangely, evaluation via tetrahedral B´ezier volume decomposition has not been

looked at in the literature. Although for graphic display purposes it is worthwhile using an approximate evaluation procedure, for analytical purposes it is sometimes necessary to know the exact formulation of the polynomial pieces of a trivariate Box spline basis function. Additionally, in computer aided geometric design it is

com-mon to represent a polynomial on an interval or triangle by its B´ezier points, since

this is very useful (both in theory and in applications) as the appropriate piecewise linear interpolant of the B´ezier points, the so-called B´ezier net, reflects the shape of the polynomial curve or surface. Curiously, these results have not previously been extended to more than two dimensions. Therefore it is worthwhile to investigate this approach in the trivariate case too. Additionally, once the B-net of each poly-nomial piece is available, the box can be evaluated and its exact value at any point

can be determined by using the regular B´ezier polynomial evaluator ([25], [30]).

For the purpose of graphically displaying the volume, it is worthwhile implementing the B-net subdivision algorithm, not only for efficiency reasons, but also for the reason that in using B-net subdivision, we have exact values of the volume at all the vertices of the subdivided tetrahedra. Thus, any interpolating volume based on translates of a trivariate Box-spline, could be displayed by our algorithm to preserve its interpolatory property.

four-direction Box-splines belong, while Section 3 acquaints the reader with triva-riate polynomials on tetrahedra, underlining the properties we need to work out the mathematics of our algorithm. In Section 4 we describe our computational scheme

for generating the B´ezier net coefficients of an arbitrary trivariate four-direction

Box-spline. Details of computation and clarifying examples are presented. Then in Section 5 we show that a restriction of our computational scheme to the two-dimensional case provides an alternative procedure to the computational scheme

proposed by Lai [24], Chui and Lai [6], [7], [8], for computing the B´ezier net of

bivariate three-direction Box-splines. Finally Section 6 is concerned with the de-scription of a Matlab implementation of our algorithm for generating the B-nets of both trivariate and bivariate Box-splines.

2 Trivariate Box-spline volumes: notations and preliminary details

Box-splines represent a generalization of univariate uniform B-splines to several variables. Therefore we can think about a Box-spline as a multivariate piecewise polynomial function of some chosen degree, i.e. as a function that consists of diffe-rent polynomial pieces of the same degree, defined over diffediffe-rent parts of its domain, that join together with a certain order of continuity.

Since Box-splines were introduced by de Boor and De Vore [13], a rich theory has been developed and collected in “the box spline book” [18] which serves as a refe-rence for the following exposition of these piecewise polynomial functions.

As underlined in this book there are many ways to derive Box-splines. Here we choose the recurrence definition and we confine ourselves to analyze the trivariate case only.

Definition 1 Let the degree-m, m ≥ 0, trivariate Box-spline M_Dm_n : R3 _{→ R,}

associated with the direction matrix Dn= [d1 d2 ... dn]∈ R3×n, n = m + 3, with

span(Dn)≡ span(d1, d2, ..., dn) =R3, dh ∈ R3\{0} ∀h = 1, ..., n,

be defined ∀n > 3 (m > 0) by the recurrence relation

M_Dm_n(x) = 1 n − 3 n
h=1 [th M_Dm−1_n\{dh}(x) + (1− t_h) M_Dm−1_n\{dh}(x− d_h)] (1)

the columns {d_h}_h=1,...,n of Dn, e.g. the least norm solution      t1 t2 .. . tn     = Dtn(DnDnt)−1  x_x1₂ x3  _.

The base case of this recursion occurs when the matrix Dn is square, that is n =

3 (m = 0). In this case M_D30 is the normalized characteristic function of the projected

half-open parallelepiped H3, spanned by the three columns of D3:

M_D30 (x) =    1 |det(D3)| if x∈ H3 0 otherwise. (2)

This Box-spline is piecewise constant, has degree m = 0 and is discontinuous. In

general, by the n columns of Dn(which may be interpreted as directions in R3) we

can determine the support of the piecewise polynomial and its continuity properties. In particular it has been proved that:

• The support of Mm

Dn is the set sum of the columns contained in Dn.

• Mm

Dn is a piecewise polynomial of degree m = n − 3.

• Mm

Dn is ρ − 2 times continuously differentiable, where ρ is the minimal number of

columns that need to be removed from Dn to obtain a matrix whose columns do

not span R3.

• Mm

Dn reproduces all polynomials of degree ρ − 1 and none of degree higher than

m = n − 3.

The class of trivariate Box-splines we are going to analyze is that defined by the direction vectors e1 =  10 0  _{, e2}=  01 0  _{, e3} =  00 1  _{, e123= e1+ e2+ e3} =  11 1   (3)

which form a regular partition ofR3 into regular tetrahedra.

E3 ≡ {e1, e2, e3, e123} is only a subset of the complete direction set

     1 0 0  _,   0 1 0  _,   0 0 1  _,   1 1 1    −11 1     1 −1 1    −1₋₁ 1     

3 _e 123

e

e₁ e₂

Fig. 1. The seven directions of the trivariate Box-spline.

The direction matrices Dn that we will associate with E3 are therefore matrices

that contain the vectors e1, e2, e3, e123 with their repetitions. More precisely, we will

use the symbol M_ν1ν2m _ν3ν4 to denote the four-direction Box-spline M_Dm_n associated

with the direction matrix

Dn= [e_{  }1, ..., e1 ν1 , e_{  }2, ..., e2 ν2 , e_{  }3, ..., e3 ν3 , e_123, ..., e_ 123_ ν4 ] where n = ν1+ ν2+ ν3+ ν4, νh∈ Z+\{0} ∀h = 1, ..., 4.

In the bivariate case, the analogous of this class of Box-splines is the class of the three-direction Box-splines studied in [7], [8], which are defined by the direction vectors E2=  1 0  ,  0 1  ,  1 1 

(see figure 2 right).

Fig. 2. Unit vectors on faces (left) - The bivariate three-direction set (right).

To represent a four-direction Box-spline by its B´ezier net, we partition its support

1 2 3 4 5 6 Fig. 3. Tetrahedral tessellation of a unit cube.

3 B-form of trivariate polynomials on tetrahedra: TB volumes

Given a trivariate Box-spline, i.e. a piecewise trivariate polynomial defined on a col-lection of tetrahedra, one can have the B-form of each polynomial piece restricted to one tetrahedron. In this section we acquaint the reader with the Bernstein repre-sentation of polynomials on tetrahedra. An introduction to this topic can be found in [16].

Definition 2 Let v0, v1, v2, v3 be four vertices inR3, whose Cartesian coordinates

(xh, yh, zh) = vh, h = 0, ..., 3, satisfy      1 x0 y0 z0 1 x1 y1 z1 1 x2 _y2 _z2 1 x3 y3 z3      = 0. (4)

Thus, any non-degenerate tetrahedron T , with non-zero (signed) volume

vol(T ) = 1 6      1 x0 y0 z0 1 x1 y1 z1 1 x2 y2 z2 1 x3 y3 z3      , (5)

is defined by the convex hull of the four affine independent vertices v0_{, v}1_{, v}2_{, v}3_{, as}

follows: T :=< v0, v1, v2, v3 >=  v∈ R3 : v = 3
h=0 λhvh, 0 ≤ λh ≤ 1 ∀h, 3
h=0 λh= 1  . (6)

The quadruple (λ0, λ1, λ2, λ3) in (6) identifies the so-called barycentric coordinates of

Remark 3 Since each

λh:= λh(v) = vol( ˆTh)

vol(T ), h = 0, ..., 3 (7)

with ˆTh denoting the tetrahedron of vertices v0, ..., vh−1, v, vh+1, ..., v3, is a linear

polynomial in v = (x, y, z) with value 1 at the vertex vh, which vanishes on the face opposite to vh, in the interior of the tetrahedron T we have λh> 0, ∀h = 0, ..., 3. We next introduce the trivariate Bernstein polynomials as follows:

B_i,j,k,lm (λ) = (i + j + k + l)!

i!j!k!l! λ

i

0λj1λk2λl3, m = i + j + k + l. (8)

Since each λh is a linear polynomial, clearly Bi,j,k,lm are polynomials of degree m. In

fact we have that the set{B_i,j,k,lm (λ), i + j + k + l = m} is a basis for the space of

all polynomials of total degree ≤ m. As a consequence any polynomial p of degree

m on T can be written uniquely in terms of B_i,j,k,lm ’s i.e.,

p(v) =

i,j,k,l≥0 i+j+k+l=m

P_i,j,k,lm B_i,j,k,lm (λ), P_i,j,k,lm ∈ R. (9)

The representation (9) for polynomials is referred to as the B´ezier form (B-form for

short) of p over T . The P_i,j,k,lm are the B´ezier coefficients of p with respect to T .

Remark 4 To simplify notation, we use p(v), p(x, y, z), p(λ) and p(λ0, λ1, λ2, λ3)

to denote the same trivariate function p. p(v) is also commonly called a tetrahedral B´ezier volume (TB volume).

Remark 5 It is interesting to notice a property of trivariate Bernstein B´ezier

volumes. Let inner B´ezier control vertices denote control points P_i,j,k,lm with all i, j, k, l = 0. The outer control points consequently denote points on the faces of the tetrahedron. We can state that all tetrahedral B´ezier volumes of degree m have no inner control points for m ≤ 3. This follows trivially since i + j + k + l = m implies one of i, j, k, l equal to zero if m ≤ 3.

Since the indeces i, j, k, l are respectively associated with the vertices v0, v1, v2, v3

in T , then we can associate each polynomial p(v) with its B´ezier coefficients set

{Pm

i,j,k,l, i + j + k + l = m} (see figures 4-5 as example).

Definition 6 The ordinates P_i,j,k,lm ∈ R associated with the barycentric abscissae

ξi,j,k,l= iv0+jvi+j+k+l1+kv2+lv3 ∈ R3 with i, j, k, l ≥ 0, i + j + k + l = m,

constitute the B´ezier net of p(v) in R4, which uniquely determines the polynomial p(v) and contains information about the geometric feature of the volume.

In fact, like in the univariate/bivariate cases, the appropriate piecewise linear in-terpolant of the four dimensional B´ezier points (ξi,j,k,l, Pi,j,k,lm ) ∈ R4 (obtained by connecting them with straight lines according to their natural order), commonly

called the B´ezier net, reflects the shape of the polynomial volume. This is one of the

reasons that polynomials in B´ezier form have been widely used in Computer Aided

Geometric Design. 1 v v v (v + v )/2 v (v + v )/2 (v + v )/2 (v + v )/20 0 2 2 3 3 1 3 2 0 3 (v + v )/20 1 (v + v )/21 2 0200 2000 1100 1010 0110 1001 P P P P P P 0002 P 0011 P 0020 P 0101 P

Fig. 4. Domain points on a degree-2 tetrahedron (left) and the corresponding B´ezier

coefficients (right). 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Fig. 5. A degree-2 trivariate matrix corresponding to tetrahedron no 5 in Fig.3. Because of the linear dependence of the barycentric coordinates, the partial deriva-tives of a TB volume do not have an obvious geometric interpretation; indeed, the partial derivatives with respect to λ0, λ1, λ2, λ3, do not coincide with the derivatives along parametric lines. Instead of working with partial derivatives, we must there-fore use directional derivatives. Now we are going to give formulas for the directional derivatives of p in a direction defined by a vector w. In particular, for

p(v) =
i,j,k,l≥0 i+j+k+l=m P_i,j,k,lm B_i,j,k,lm (λ) we have Dwp(v) = m
i,j,k,l≥0 i+j+k+l=m−1

with a = (a1, a2, a3, a4), a1+ a2+ a3+ a4 = 0, and the following recurrence relation on the coefficients:

∆P_i,j,k,lm−1(a) = a1Pi+1,j,k,lm + a2Pi,j+1,k,lm + a3Pi,j,k+1,lm + a4Pi,j,k,l+1m . (11) Here the ah, h = 1, ..., 4 are the so-called T -coordinates of w. That is, if w = w2−w1 is a direction vector with (β1, β2, β3, β4) and (γ1, γ2, γ3, γ4) being the barycentric

coordinates of w1 and w2 with respect to T , the T -coordinates of w are a =

(γ1− β1, γ2− β2, γ3− β3, γ4− β4) = (a1, a2, a3, a4).

4 The mixed directional difference-summation (MDDS) algorithm

As mentioned in the introduction, algorithms for evaluating Box-spline functions can be classified into three types, depending on

• it is computed the value of the Box-spline function exactly for each fixed point

using the recurrence definition in (1);

• it is given an efficient approximation scheme which is based on another recurrence

relation, obtained via two-scale subdivision or inverse FFT;

• it is given an explicit representation, say in terms of the B´ezier net, of each

polynomial piece.

Algorithms of the third type depend on yet another form of recurrence relation (11). In this section we represent a trivariate Box-spline basis function over a

regu-lar tetrahedron partition ∆ of its polygonal domain Ω∈ R3, with piecewise planar

boundary ∂Ω, and we give a computational scheme to determine the B´ezier coeffi-cients of each polynomial piece of the trivariate function.

To be more precise, trivariate Box-spline basis functions M_ν1ν2ν3ν4m , ν1+ν2+ν3+ν4 =

n, are piecewise polynomials in three variables that consist of 6 ∗ (ν1 + ν4)(ν2 +

ν4)(ν3+ ν4) different polynomial pieces of the same degree m = n − 3, defined over

a tetrahedral tesselation of their domain.

Let x0 < . . . < xp < xp+1 < . . . < xν1+ν4−1, y0 < . . . < yq < yq+1 < . . . < yν2+ν4−1 ,

z0 < . . . < zr < zr+1 < . . . < zν3+ν4−1 and let the planes x = xp, y = yq, z = zr,

p = 0, . . . , ν1+ ν4 − 1, q = 0, . . . , ν2+ ν4 − 1, r = 0, . . . , ν3+ ν4 − 1 partition the 3D space into cubic cells. Drawing in all cells, the tetrahedral partition described in figure 3, we get a tetrahedral tessellation of the Box-spline domain.

Consider the cube of vertices (xp, yq, zr), (xp, yq, zr+1), (xp, yq+1, zr), (xp, yq+1, zr+1), (xp+1, yq, zr), (xp+1, yq, zr+1), (xp+1, yq+1, zr), (xp+1, yq+1, zr+1) and denote by Pi,j,k,lm ,

i + j + k + l = m, the B´ezier coefficients of the degree-m trivariate polynomial p(v),

defined by restricting Mν1ν2ν3ν4, ν1+ν2+ν3+ν4= m+3, to one of the six tetrahedra

in the cube.

Hence it trivially follows

DdhMDn(x) =

i, j, k, l ≥ 0 i + j + k + l = m − 1

Qm−1_i,j,k,lB_i,j,k,lm−1(λ)

where λ ≡ (λ0, λ1, λ2, λ3) are the barycentric coordinates associated with x ∈ T .

Now recalling that a Box-spline is a linear combination of B´ezier basis functions,

we can exploit (10)-(11) and write

m

i, j, k, l ≥ 0 i + j + k + l = m − 1

∆P_i,j,k,lm−1(a) B_i,j,k,lm−1(λ) =

i, j, k, l ≥ 0 i + j + k + l = m − 1

Qm−1_i,j,k,lB_i,j,k,lm−1(λ). (12)

From (12) it can be easily derived

Qm−1_i,j,k,l= m(a1Pi+1,j,k,lm + a2Pi,j+1,k,lm + a3Pi,j,k+1,lm + a4Pi,j,k,l+1m ) (13)

where a ≡ (a₁, a2, a3, a4) is a vector with the T-coordinates of the direction dh =

x− (x − d_h):

ai = γi− βi i = 1, . . . , 4,

with (γ1, γ2, γ3, γ4) and (β1, β2, β3, β4) being the barycentric coordinates of x and

x− d_h respectively1. The construction of the B-net requires to work out the

un-knowns P_i,j,k,lm from equation (13). From now on, the factor m is omitted in order

to keep the numbers integral (see Prop.7).

In conclusion, the mathematical ideas and formulations of finding the B-nets of a trivariate four-direction Box-spline can be summerized as follows.

Starting with the B-net of the degree-1 Box-spline M₁₁₁₁1 , (see figure 6) we can

compute the B-net of any other Box-spline M_ν1ν2ν3ν4m , with ν1+ ν2+ ν3+ ν4 > 4, by applying the algorithm summarized in the following steps:

(1) Express each polynomial piece of the Box-spline in (unknown) B´ezier

represen-tation;

(2) Use the recurrence (see [29])

1 _{Since we always integrate along the directions e}

DdhMDmn(x) = MDm−1n\{dh}(x)− M m−1

Dn\{dh}(x− dh) h = 1, . . . , n (14) to represent the degree-m Box-spline with respect to the degree-(m − 1) one

generated by the direction matrix Dn\{dh}, with span(Dn\{dh}) = R3;

(3) Determine the coefficients Pm in the B-net of M_Dm_n by using the derivative

formula of TB-polynomials in (11), with (a1, a2, a3, a4) being the T-coordinates of d_h and Qm−1 the coefficients of the B-net of M_Dm−1_n\{dh}.

0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 Fig. 6. B-net of M₁₁₁₁1 .

Thus, starting with the known B-net of M₁₁₁₁1 , the key idea to construct the B-net of

an arbitrary degree Box-spline, is applying the derivative formula (14) recursively. In this way the B´ezier coefficients Qm−1_i,j,k,l of DdhMDmn can be obtained by applying a shift and subtract procedure on the B-net of M_Dm−1_n\{dh}(x).

Note that the B-nets of all trivariate four-direction Box-splines generated by the procedure described above can be computed once for all. This derives from the following proposition.

Proposition 7 Let M_Dm_n be a trivariate four-direction Box-spline. Then the B-net

of its polynomial pieces consists of rational numbers.

Proof. This trivially derives from the fact that we start our method from the linear

B-net with all integral coefficients and we combine the _m1 factors, coming from (13),

into a single _m!1 which can be carried out at the end of a sequence of operations

which are indeed only integer additions and subtractions.

Corollary 8 Thus we can compute the B-net of those Box-splines in exact

arith-metic. This guarantees the numerical stability property of the proposed algorithm.

To clarify the presentation, we first illustrate the procedure above with the following example and successively we present a Matlab package for computing the B-net coefficients of an arbitrary trivariate four-direction Box-spline (see Section 6).

Example. Consider the degree-2 Box-spline defined by the direction matrix D5 =

{e1, e1, e2, e3, e123}. Following the algorithm given above, the B-net of MD52 turns

out to be defined by shifting and subtracting the B-net of M_D41 (see figure 6), with

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 −1 1

Fig. 7. Shift and subtraction of the coefficients of the linear Box-spline M1

D4. the resulting coefficients along the same direction. This last step (which allows

us to work out the B´ezier coefficients of M_D52 ) is expressed in relation (13) with

(a1, a2, a3, a4) being the T-coordinates of e1, that is

a1 = γ1− β1 = 0− 1 = −1

a2 = γ2− β2 = 1− 0 = 1

a3 = γ3− β3 = 0− 0 = 0

a4 = γ4− β4 = 0− 0 = 0. In other words, relation (13) results simplified as follows:

Q1₁₀₀₀ = P₁₁₀₀2 − P₂₀₀₀2 Q1₀₁₀₀ = P₀₂₀₀2 − P₁₁₀₀2 Q1₀₀₁₀ = P₀₁₁₀2 − P₁₀₁₀2 Q1₀₀₀₁ = P₀₁₀₁2 − P₁₀₀₁2 (15) and thus P₁₁₀₀2 = Q1₁₀₀₀+ P₂₀₀₀2 P₀₂₀₀2 = Q1₀₁₀₀+ P₁₁₀₀2 P₀₁₁₀2 = Q1₀₀₁₀+ P₁₀₁₀2 P₀₁₀₁2 = Q1₀₀₀₁+ P₁₀₀₁2 . (16)

Since the integral of a TB-volume of degree 1 is a TB-volume of degree 2, equation

(16) can be viewed as an integration of the Q1 coefficients, starting along the

trian-gular face of the tetrahedron with vertices P₂₀₀₀2 , P₁₀₁₀2 , P₁₀₀₁2 , P₀₀₂₀2 , P₀₀₁₁2 , P₀₀₀₂2 . However, since the value of such constants of integration is unknown, we make them assume the coefficient values in the adjacent tetrahedron sharing the face containing those constants, until we get the box boundary, where the coefficients are equal to zero (as we are looking for basis functions with a bounded non-zero region). In this

P₀₁₁₀2 , P₀₁₀₁2 by a sequence of successive additions, like:

P₁₁₀₀2 = Q1₁₀₀₀+ P₂₀₀₀2

P₀₂₀₀2 = Q1₀₁₀₀+ Q1₁₀₀₀+ P₂₀₀₀2

P₀₁₁₀2 = Q1₀₀₁₀+ P₁₀₁₀2

P₀₁₀₁2 = Q1₀₀₀₁+ P₁₀₀₁2 .

Applying these equalities to the whole Box-spline M_D52 and exploiting adjacencies

of tetrahedra, we are capable to work out all the B´ezier coefficients of its B-net.

From now on we will use the double apex 2, (c1, c2) to denote the B´ezier coefficients

of the c2-th degree-2 tetrahedral volume belonging to the cube c1. For example, in

order to compute the coefficient P₀₁₀₁2,(1,5) of the 5-th tetrahedron in cube 1 (the one

on the right in figure 8), we exploit the relation

P₀₁₀₁2,(1,5) = Q1,(1,5)₀₀₀₁ + P₁₀₀₁2,(1,5)

where P₁₀₀₁2,(1,5) coincides with the coefficient P₀₁₀₁2,(2,1) of the 1-st tetrahedron in the 2-nd cube (the one on the left in figure 8).

and going on substituting until integration constant reaches the box boundary, we get

P₀₁₀₁2,(1,5) = Q1,(1,5)₀₀₀₁ + Q1,(2,1)₀₀₀₁ + Q₀₀₀₁1,(2,5)+ Q1,(3,1)₀₀₀₁ + Q1,(3,5)₀₀₀₁ + P₁₀₀₁2,(3,5). (17)

In this way all the intermediate coefficients are easily computed: Q1,(3,5)₀₀₀₁ Q1,(3,1)₀₀₀₁ Q1,(2,5)₀₀₀₁ Q1,(2,1)₀₀₀₁ Q1,(1,5)₀₀₀₁ + _= _+ _= _+ _= _+ _= _+ _= P10012,(3,5) P01012,(3,5) P10012,(2,5) P01012,(2,5) P10012,(1,5) P01012,(1,5). 2,(3,5) 2,(2,5) 2,(1,5) 0101 P 0101 P 0101 P 1001 P2,(1,5) 2,(2,5) P1001 1001 2,(3,5) P Q1,(3,1) 0001 Q0001 1,(2,1) 1,(1,5) 0001 Q 1,(2,5) Q 0001 1,(3,5) 0001 Q

Fig. 9. The mixed direction worked out for determining the B´ezier coefficients

P₁₀₀₁2,(3,5), P₀₁₀₁2,(3,5), P₁₀₀₁2,(2,5), P₀₁₀₁2,(2,5), P₁₀₀₁2,(1,5), P₀₁₀₁2,(1,5) of M₂₁₁₁2 .

The coefficients Q1_i,j,k,l in (17) identify a particular mixed direction inR3(see figure

9). Such direction allows us to store the Q1

i,j,k,lcoefficients in a vector that has to be

integrated by applying a sequence of summations (that starts with the integration constant P₁₀₀₁2,(3,5)), in order to generate the P₀₁₀₁2,(1,5) coefficient of the degree-2

Box-spline M₂₁₁₁2 . The name ”mixed direction” derives from the fact that the direction

of integration, identified by the coefficients Q1_i,j,k,l, is a composition of some linear

combinations of the directions e1, e2, e3, e123 (e123, e2+ e3 in this case). The same procedure can be applied for determining all the mixed directions we need to work

out all the B-net coefficients of M₂₁₁₁2 . Obviously, the mixed directions by which

they are determined are not always the same, although there is a common pattern for all of them. In figure 10 you can see the mixed directions set originating the B-net of M₂₁₁₁2 .

The number and path of such directions depend on the degree of the Box. As you can see, the mixed directions set is composed of one uni-dimensional direction (figure 10-a), two two-dimensional directions (with two branches each), respectively on the planes y = constant (figure 10-b) and z = constant (figure 10-c), and one three-dimensional direction (figure 10-d) composed of four branches. Each branch is just a translation in the vertices indicated in the pictures, of the given mixed direction with origin in the vertex marked by 0. The uni-dimensional one, defined

we are integrating. For this reason we are going to refer to such direction by the term main direction. In the given example, such direction identifies the coefficient

P₀₂₀₀2,(1,5), since its value is computed in the following way:

Q1,(3,5)₀₀₀₁ Q1,(3,5)₀₁₀₀ Q1,(2,5)₁₀₀₀ Q1,(2,5)₀₁₀₀ Q1,(1,5)₁₀₀₀ Q1,(1,5)₀₁₀₀

+ _= _+ _= _+ _= _+ _= _+ _= _+ _=

P₂₀₀₀2,(3,5) P₁₁₀₀2,(3,5) P₂₀₀₀2,(2,5) P₁₁₀₀2,(2,5) P₂₀₀₀2,(1,5) P₁₁₀₀2,(1,5) P₀₂₀₀2,(1,5)

As it can be observed, because Q1,(3,5)₀₁₀₀ = Q1,(2,5)₁₀₀₀ and Q1,(2,5)₀₁₀₀ = Q1,(1,5)₁₀₀₀ , the main direction contains two duplicated coefficients. In general, a main direction for gene-rating a degree-m Box-spline, contains exactly m duplicated coefficients.

a b 0 1 c 0 1 0 1 2 3 d

Fig. 10. All the integration paths (mixed directions) sufficient for computing the

B-net of the quadratic trivariate Box-spline M₂₁₁₁2 .

5 Restricting the scheme to the two-dimensional case

In this section we are going to show that a restriction of our computational scheme to the two-dimensional case provides an alternative procedure to the computational

scheme proposed by Lai [24], Chui and Lai [6], [7], [8], for computing the B´ezier net

of bivariate three-direction Box-splines. In fact following the Box-spline definition proposed in [29] we can use mathematical induction on the degree m to prove that

M_11νν3+ν_3ν44−1(x, y, z)

x=y = M

ν3+ν4−1

1ν3ν4 (x, z).

We now confine ourselves to the first case and for sake of simplicity we choose

ν3 = 1, focusing our attention on the restriction of the trivariate Box-spline Mν1ν1111 to the plane y = 1. The initial step is the linear case:

M_E31 (x, y, z)

y=1= M

1

E2(x, z).

According to the recurrence Box-spline definition given in Section 2,

M_E31 (x, y, z) = t1ME3\{e1}0 (x, y, z) + (1 − t1)ME3\{e1}0 (x − 1, y, z) (18) + t2ME3\{e2}0 (x, y, z) + (1 − t2)ME3\{e2}0 (x, y − 1, z)

+ t3ME3\{e3}0 (x, y, z) + (1 − t3)ME3\{e3}0 (x, y, z − 1)

+ t4ME3\{e123}0 (x, y, z) + (1 − t4)ME3\{e123}0 (x − 1, y − 1, z − 1).

Figure 11 illustrates the computation in (18).

Fig. 11. The four branches related to t1, t2, t3, t4 contributions.

Applying relation (1) we get M_E31 (x, y, z)

y=1 = x.

In a similar way we have evaluated the bivariate Box-spline in the same triangle, obtaining

M_E21 (x, z) = x.

Exploiting the inductive definition suggested in [29] we have

M_E3∪{e1}2 (x, y, z) y=1= 1  0 M_E31 (x − t, y, z)dt y=1 = 1  0 M_E31 (x − t, y, z) y=1dt (∗)

and for the inductive hypothesis M_E31 (x − t, 1, z) = M_E21 (x − t, z),

(∗) = 1

0

M_E21 (x − t, z)dt = M_E2∪{e1}2 (x, z).

From this property it easily derives that the B-net of a bivariate three-direction Box-spline M_ν1,ν2,ν3m (with one of the multiplicities ν1, ν2, ν3 set equal to 1) can

be obtained by restriction of the B´ezier coefficients of the corresponding trivariate

four-direction Box-spline to a specified plane. For example the B-net of M₂₁₁2

1 2               0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 2 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0              

is exactly the restriction of the B-net of M₂₁₁₁2 to the plane y = 1. This is explained

6 The MDDS package

This section is concerned with the description of a Matlab package, called MDDS (available in the NUMERALGO library [4]), designed to compute the B-net coeffi-cients of all trivariate four-direction Box-splines and additionally to exact evaluate and visualize them.

The user interface is provided by three main functions:

1. the function bnet_mdds() that allows to compute the B´ezier net coefficients of

trivariate four-direction Box-splines of any degree;

2. the function pointeval_mdds3d() that allows to exact evaluate any trivariate four-direction Box-spline in an arbitrary set of 3D points;

3. the function visual_mdds3d() that allows to visualize any trivariate four-direction

Box-spline M_ν1m_ν2ν3ν4 either through the s-set (s ∈ Imm(M_ν1ν2ν3ν4m )) extraction

of the Box-spline volume or through the contour lines of the regions obtained by intersecting the Box-spline volume with three families of planes respectively parallel to yz, xz, xy.

The function bnet_mdds() implements the algorithm presented in Section 4 for

generating the mixed directions set of M_ν1ν2ν3ν4m and computing its B´ezier net.

The general procedure proposed consists in representing the B-net of the linear

Box-spline M₁₁₁₁1 by the tri-dimensional array

B(:,:,1)=        0 0 0 0 0 0 0 0 0        B(:,:,2)=        0 0 0 0 1 0 0 0 0        B(:,:,3)=        0 0 0 0 0 0 0 0 0       ,

and generating the B-net of M_ν1ν2ν3ν4m by successive differences-summations of the

linear Box-spline along the four directions e1, e3, e2, e123, respectively ν1, ν3, ν2, ν4 times:

M₁₁₁₁1 −→I M_ν1ν1₁₁₁ −→II M_ν1ν1_1ν+ν₃3−1₁ −→III M_ν1ν1_ν2ν3+ν2+ν₁ 3−2 −→IV M_ν1ν2ν3ν4m .

At the end of these four steps, the B´ezier coefficients of M_ν1ν2ν3ν4m are stored in the

tri-dimensional array A(iA, jA, kA), where 1 ≤ iA ≤ m(ν3 + ν4) + 1, 1 ≤ jA ≤

m(ν1+ ν4) + 1, 1 ≤ kA ≤ m(ν2 + ν4) + 1 (noting that we have zero coefficients

outside of the support of M_ν1ν2ν3ν4m ). Steps I, II, III, IV are summarized respectively

in the four function modules step1_mdds3d(), step2_mdds3d(), step3_mdds3d(), step4_mdds3d(). They are devised to generate the mixed directions set MD needed

to work out the intermediate B´ezier coefficients set A, starting with the one degree

I. First step: _{M1111 −→ Mν1111} for i=1, . . . , ν1 A=step1_mdds3d(i, 1, 1, 1, B) B=A end Number of MD:m2 Number of branches: (2ν1− 1)2

II. Second step: _{Mν1111−→ Mν11ν31}

for i=1, . . . , ν3 A=step2_mdds3d(ν1, 1, i, 1, B) B=A end Number of MD: m2 Number of branches: (2m − 1)(m(ν1+ 1)− 1)

III. Third step: _{Mν11ν31 −→ Mν1ν2ν31}

for i=1, . . . , ν2 A=step3_mdds3d(ν1,i, ν3, 1, B) B=A end Number of MD:m2 Number of branches: (m(ν3+ 1)− 1)(m(ν1+ 1)− 1)

IV. Fourth step: _{Mν1ν2ν31 −→ Mν1ν2ν3ν4}

for i=1, . . . , ν4 A=step4_mdds3d(ν1, ν2, ν3, i, B) B=A end Number of MD: 3m(m − 1) + 1 Number of branches: m2(ν1ν2+ ν2ν3+ ν1ν3)− m(ν1+ ν2+ ν3) + 1

computation of the duplicated coefficients in the main mixed directions (as previou-sly explained at the end of Section 4), the second one is required to compute the integration step along any direction.

To exact evaluate any trivariate four-direction Box-spline in an arbitrary set of 3D points, an additional function, named pointeval_mdds3d(), is provided. This func-tion is supported by the funcfunc-tion modules findcube_mdds3d() and findtetra_mdds 3d(), which respectively identify the unit cube and the tetrahedron type (see figure 3) that contain the evaluation point.

If, instead, there is an interest to visualize a trivariate four-direction Box-spline, the function visual_mdds3d() will make the job. Exploiting the trivariate

Bernstein-B´ezier polynomials evaluation procedure in computebez_mdds3d(), it allows to

vi-sualize a s-set extraction (with s ∈ Imm(M_ν1ν2ν3ν4m )) of the Box-spline volume

M_ν1ν2m _ν3ν4 and (if required) its contour lines.

To demonstrate the use of all such functions, the M-file demo_mdds3d.m is included.

Three examples of four-direction Box-splines on R3 are examined: the cubic

Box-spline M₂₁₁₂3 , the quintic Box-spline M₂₂₂₂5 and the sextic Box-spline M₃₂₂₂6 . Their

B´ezier coefficients matrix and their evaluation in an arbitrary point of the domain

are provided. Furthermore a visualization through the s-set extraction and the three families of contour lines is available. We show here the 0-set and 0.01-set extraction

of the Box-spline volume M₂₁₁₂3 (figure 12), the 0-set and the 0.005-set extraction

of M₂₂₂₂5 (figure 13) and the 0-set and the 0.001-set extraction of M₃₂₂₂6 (figure 14).

−1 0 1 2 3 4 5 −1 0 1 2 3 4 −1 −0.5 0 0.5 1 1.5 2 2.5 3 3.5 4 x y z −1 0 1 2 3 4 5 −1 0 1 2 3 4 −1 −0.5 0 0.5 1 1.5 2 2.5 3 3.5 4 x y z

Fig. 12. Visualization through 0-set extraction (left) and 0.01-set extraction (right)

of the Box-spline volume M₂₁₁₂3 .

−1 0 1 2 3 4 5 −1 0 1 2 3 4 5 −1 0 1 2 3 4 5 x y z −1 0 1 2 3 4 5 −1 0 1 2 3 4 5 −1 0 1 2 3 4 5 x y z

Fig. 13. Visualization through 0-set extraction (left) and 0.005-set extraction (right)

of the Box-spline volume M₂₂₂₂5 .

0 2 4 6 −1 0 1 2 3 4 5 −1 0 1 2 3 4 5 x y z 0 2 4 6 −1 0 1 2 3 4 5 −1 0 1 2 3 4 5 x y z

Fig. 14. Visualization through 0-set extraction (left) and 0.001-set extraction (right)

of the Box-spline volume M₃₂₂₂6 .

Indeed, through our mixed directional difference-summation algorithm, we can ob-tain also the B-net of any arbitrary bivariate three-direction Box-spline (see Section

5). In fact, also for computing the B-net of the very general Box-spline M_ν1,ν2,ν3m

we can exploit the idea proposed for generating the B´ezier coefficients of an

a (1) (1) A B B A 0 1A 0B 1 b 2 3 (2)B A (2) 0 0 2 3 A A A B B B 1B 1A c (3)B (3)A A A 0 1 B B 0 1 d (4) (4)_B A A 3 A A A 3 2 1 0B B B B 0 1 2 e (5)B (5)A f (6)B A (6) 0A 1A A 4 5A 2 3 2A 3A B B B B B B 4 5 1 0

Fig. 15. The 2D mixed-directions set used for computing the B-net of the cubic trivariate Box-spline M₂₁₁₂3 . a (1) (1) (2) b (4) (4) (3) (3) c (6) (5) (5)

Fig. 16. The 3D mixed-directions set used for computing the B-net of the cubic

trivariate Box-spline M3

2112.

added a Matlab code [4] that exploits the mixed directions set procedure to compute the B-net coefficients of all bivariate three-direction Box-splines and additionally to exact evaluate and visualize them.

More precisely, the computation of the B´ezier net coefficients of bivariate

three-direction Box-splines of any degree, is performed by the main function bnet_mdds() itself. In fact, if the input parameter is a three-component vector with the

mul-tiplicities of the directions in E2, the three function modules step1_mdds2d(),

step2_mdds2d(), step3_mdds2d() are called in order to generate the mixed

di-rections set MD in R2.

arbitrary set of 2D points, is implemented in the function pointeval_mdds2d(), by means of the functions findsquare_mdds2d() and findtria_mdds2d(), where the unit square and the triangle type (see figure 2, right) containing the evalua-tion point are respectively identified. Finally, the visualizaevalua-tion of a bivariate three-direction Box-spline and its B-net, is carried out in the function visual_mdds2d(), which exploits the function computebez_mdds2d() for the evaluation of bivariate

Bernstein-B´ezier polynomials. The use of all such functions is demonstrated in the

M-file demo_mdds2d.m, where the quadratic Box-spline M₂₁₁2 , the quartic Box-spline

M₂₂₂4 and the quintic Box-spline M₃₂₂5 are taken as examples for the computation

of the B´ezier coefficients matrix and the evaluation in an arbitrary point of the

domain. Furthermore a visualization of these Box-spline surfaces and their B-nets is provided, as shown in figures 17, 18 and 19. Figure 20, instead, illustrates the

mixed directions set used to generate the B-net of M₂₂₂4 .

0 0.5 1 1.5 2 2.5 3 0 0.5 1 1.5 2 0 0.2 0.4 0.6 0.8 1 x y z 0 0.5 1 1.5 2 2.5 3 0 0.5 1 1.5 2 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 x y z

Fig. 17. B-net (left) and surface graph (right) of the bivariate quadratic

three-direction Box-spline M2 211. 0 1 2 3 4 0 1 2 3 4 0 0.1 0.2 0.3 0.4 0.5 x y z 0 1 2 3 4 0 1 2 3 4 0 0.1 0.2 0.3 0.4 0.5 x y z

0 1 2 3 4 5 0 1 2 3 4 0 0.1 0.2 0.3 0.4 0.5 x y z 0 1 2 3 4 5 0 1 2 3 4 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 x y z

Fig. 19. B-net (left) and surface graph (right) of the bivariate quintic three-direction Box-spline M₃₂₂5 .

Fig. 20. Generation of the B-net of M4

222by successive summations of the coefficients

of De1M₁₁₁1 , De2M₂₁₁2 , De12M₂₂₁3 along the marked mixed directions.

7 Conclusions

In this work we have proposed a new computational scheme for determining the

B´ezier net of any trivariate four-direction Box-spline and we have given a concise

Matlab implementation of it [4]. The results obtained show that our algorithm is stable and efficient and, although reproducing consisting results with the existing evaluation algorithms [20], it has no comparison in the field of exact evaluation techniques.

In addition, if restricted to the two-dimensional case, it provides a novel and

sim-plified procedure for computing the B´ezier net coefficients of any bivariate

Acknowledgements

This research was supported by MIUR-PRIN 2004 and by University of Bologna ”Funds for selected research topics”.

References

[1] T. Asahi, K. Ichige and R. Ishii, A new formulation for discrete box splines reducing computational cost and its evaluation, IEICE Trans. Fundamentals, Vol. E84-A, No. 3, March 2001.

[2] J. Berchtold, I. Voiculescu and A. Bowyer, Multivariate Bernstein-form polynomials, Technical Report No. 31/98, School of Mechanical Engineering, University of Bath.

[3] W. Boehm, Calculating with box splines, Computer Aided Geometric Design

1(2) (1984), pp. 149-162.

[4] G. Casciola, E. Franchini, L. Romani, The MDDS package, available at www.netlib.org/numeralgo/na23.

[5] Y.-S. Chang, K.T. McDonnell and H. Qin, A new solid subdivision scheme based on box splines, Proceedings of the 7th ACM Symposium on Solid Modeling and Applications (2002), pp. 226-233.

[6] C.K. Chui and M.J. Lai, Computation of box-splines and B-splines on triangulations of nonuniform rectangular partitions, Approximation Theory & its Applications 3 (1987), pp. 37-62.

[7] C.K. Chui, Multivariate Splines, CBMS Lectures Series 54, SIAM, Philadelphia (1988).

[8] C.K. Chui and M.J. Lai, Algorithms for generating B-nets and graphically displaying spline surfaces on three- and four- directional meshes, Computer Aided Geometric Design 8 (1991), pp. 479-493.

[9] E. Cohen, T. Lyche and R. Riesenfeld, Discrete box splines and refinement algorithms, Computer Aided Geometric Design 1 (1984), pp. 131-141.

[10] M. Dæhlen, On the evaluation of box splines, in: Mathematical Methods

in Computer Aided Geometric Design T. Lyche and L. Schumaker (Eds.),

Academic Press N.Y. (1989), pp. 167-179.

[11] W. Dahmen and C.A. Micchelli, Recent progress in multivariate splines, in:

Approximation Theory IV C.K. Chui, L.L. Schumaker and J.D. Ward (Eds.),

[12] W. Dahmen, Bernstein-B´ezier representation of polynomial surfaces, in:

Extension of B-spline curve algorithms to surfaces Siggraph 86 Lecture Notes,

ACM New York.

[13] C. de Boor, R. De Vore, Approximation by smooth multivariate splines, Trans. Amer. Math. Soc. 276 (1983), pp. 775-788.

[14] C. de Boor and K. H¨ollig, Recurrence relations for multivariate B-splines, Proc.

Amer. Math. Soc. 85 (1982), pp. 397-400.

[15] C. de Boor and K. H¨ollig, B-splines from parallelepipeds, J. Analyse Math. 42

(1982), pp. 99-115.

[16] C. de Boor, B-form basics, in: Geometric Modeling: Applications and New

Trends G. Farin (Ed.), SIAM Publication, Philadelphia (1987), pp. 131-148.

[17] C. de Boor, On the evaluation of box splines, Numerical Algorithms 5 (1993), pp. 5-23.

[18] C. de Boor and K. H¨ollig and S. Riemenschneider, Box splines, Springer Verlag,

Berlin, 1993.

[19] K. H¨ollig, Box splines, in: Approximation Theory V C.K. Chui, L.L. Schumaker

and J.D. Ward (Eds.), Academic Press, New York (1986), pp. 71-95.

[20] L. Kobbelt, Stable evaluation of box splines, Numerical Algorithms 14(4) (1997), pp. 377-382.

[21] D. Lasser, Bernstein-B´ezier representation of volumes, Computer Aided

Geometric Design 2(1-3) (1985), pp. 145-150.

[22] M.D. Mc Cool, Optimized evaluation of Box splines via the inverse FFT, Proceedings of Graphics Interface, Canadian Information Processing Society,

Qu´ebec (1995), pp. 34-43.

[23] T. Goodman and J. Peters, B´ezier nets, convexity and subdivision on higher

dimensional simplices, Computer Aided Geometric Design 12(1) (1995), pp. 53-65.

[24] M.J. Lai, Fortran subroutines for B-nets of box splines on three- and four-directional meshes, Numerical Algorithms 2 (1992), pp. 33-38.

[25] J. Peters, Evaluation of multivariate Bernstein polynomials, CMS Technical Report No. 91-1, University of Wisconsin.

[26] J. Peters, Evaluation and approximate evaluation of the multivariate

Bernstein-B´ezier form on a regularly partitioned simplex, ACM Trans. Math. Softw. 20(4)

(1994), pp. 460-480.

[27] J. Peters, C2 surfaces built from zero sets of the 7-direction box spline,

[28] J. Peters and M. Wittman, Blending basic implicit shapes using trivariate box splines, Proceedings of the fourth ACM Symposium on Solid Modeling and Applications (1997), pp. 195-205.

[29] H. Prautzsch and W. Boehm, Box Splines, in: Handbook of Computer Aided

Geometric Design G. Farin, J. Hoschek and M.-S. Kim (Eds.), (2002), Chapter

10.

[30] L.L. Schumaker and W. Volk, Efficient evaluation of multivariate polynomials, Computer Aided Geometric Design 3(2) (1986), pp. 149-154.

[31] J. Sun and K. Zhao, On the structure of B´ezier nets, J. Computational Math.