Converting standard bivariate

polynomials to Bernstein form

over arbitrary triangular regions
Warren N Waggenspack Jr and David C Anderson

triangular surface patch z = BN(x,y), and the establishment

An efficient, robust algorithm is presented for converting of a convenient bounding scheme for segments of the
a bivariate polynomial expressed in the power basis directly
implicit curve.
to its equivalent Bernsteln (B~zier) form over an arbitrary Because both the power and Bernstein forms are bases
triangular region. It represents an improvement over exist- for the space of all bivariate degree IV polynomials, there
ing algorithms which, in the course of transforming the must exist, at least theoretically, a means of transforming
polynomial, may encounter degeneracy problems that between the two representations. Conversion algorithms
must be handled with additional logic. exist for transforming univariate polynomials, for mapping
the bivariate power basis to the Bernstein basis over the
mathematics, geometry, bivariate polynomials, triangularpatches standard triangle, for mapping a Bernstein polynomial over
one triangular region to an equivalent representation over
a second trtangle having a common edge with the first 6 ,
Parametric polynomial curves {x=x (t), y = y (t)} have held and for converting between the triangular Bernstein and
a dominant position in computer-aided geometric design rectangular tensor product Bernstein bases~'s. Combining
(CAGD) studies for over a decade. The reasons for this these ideas enables one to build an algorithm which first
are well documented 1-3 . More recently, however, interest converts to Bernstein form over the standard triangle, and
in the study of implicit algebraic curves has been rekindled 4, then successively maps each vertex from the standard
and the relative advantages of one form over the other are triangle to the arbitrary triangle. However, the mapping
being re-evaluated. In addition, many CAGD applications may fail if care is not taken to avoid degenerate inter-
that use parametric curves and surfaces extensively, still
mediate trtangles, i.e. where all three vertices are colinear.
resolve a number of interrogations to the study of implicit
The new algorithm, which is based on Homer's rule for
algebraic curves s .
polynomial evaluation, extends a method developed for
An implicit, planar algebraic curve is defined as the set
univariate polynomials and provides a direct mapping from
of all points that satisfy the bivariate polynomial equation
the power basis to the Bernstein basis over an arbitrary
f(x,y) = 0. The standard power basis is the most familiar
triangular regton. It is more efficient than the mdtrect
form of this equation
method mentioned, and encounters no dtfficulttes with
degenerate triangles. The next section of this paper des-
I+J~N
f N (x, y) = ~, ai, j xly j cribes the algorithm for univariate polynomials. The section
i,/=0 following details its extension and application to bivariate
polynomials.
Its equivalent Bernstein (B6zier) form over the standard
triangle [(0,0), (1,0), (0,1)] is CONVERSION ALGORITHM FOR
UNIVARIATE POLYNOMIALS
fN (x,y) = BN (x,y) =
Given a univariate polynomial expressed in the power
basis,
//,/:0
J,N
~, IN]
i,/
bljxly ] (1 -x-y)N - i - j
N
pN = ~ alxi
where i=0

I N N~ Geisow s discusses algorithms for converting to an equi-

i,j / ! j ! (IV-i-j)! valent univariate Bernstein form over an arbitrary para-
meter range [X0, XN] where
is the multinominal coefficient. Using barycentric coordi-
nates e, it is also possible to construct a Bernstein represen- x = (1 - t ) X o + t X N
tation over arbitrary triangular regions. The advantages of
this form include geometric interpretation of the poly- Direct substitution into the power basis yields
nomial coefficients, blj, as control point coordinates of a
N
School of Mechanical Engineering,Purdue University, West pN = ~ ai{(1 - t ) X a + t X N } i
Lafayette, IN 47907, USA /=0

volume 18 number I 0 december 1986 0 0 1 0 - 4 4 8 5 / 8 6 / 1 0 0 5 2 9 - 0 4 $03.00 © 1986 Butterworth & Co (Publishers) Ltd 529
The bracketed terms are expanded using the binomial ((1-t)+t) #=1 fork=2,3,.. , N, leads to the follow I
theorem, and, after regrouping, can be equated to a degree ing algorithm s
N Bernstein polynomial in t with unknown coefficients b i.
Geisow shows this result as d_kl --dk+l --=0 k=O,_ ,N

['] do 0 = o N

bI = Xo',XN-Xolr ,( : + + [:] oN-j

I/=I,...,N
j=O,...~/

The resulting triangular array of values (d/k) contains a

or set of scaled Bernstein polynomial coefficients (d/N) which
are then extracted using

bi = --
/=O,I,...,N

Polynomials expressed m the power basis are more effi- E X T E N D I N G THE A L G O R I T H M T O

ciently evaluated using Homer's rule BIVARIATE POLYNOMIALS

pN = ( ( . . . ((aN x + aN_l) x + aN_2) x . . . The univariate algorithm has been directly applied to creat-
ing tensor product Bernstein polynomials over general
+a,)x+.o) rectangular regions. It can also be extended to generating
a Bernstein representation for bivariate polynomials of
As Geisow points out, this also leads to a conversion algo- total degree N over arbitrary triangular regions
rithm between polynomial bases that is more efficient than
those noted above. Using the identity ((1 - t) + t) = 1 and i+j< N
substituting for x in the innermost pair of parenthesis pN = ~ GI,j x l y l
generates I,J:O

{aN (Xo (1 -t) + t X N ) + aN- 1 ((1 -t) + t)} By grouping all terms with like powers of x, the bivanate
polynomial can be expressed as univariate in x with coeffi-
= (aNXo + a N _ l ) (1-t) + (#NXN + aN_l) t
cients that are polynomials in y
= do 1 (1 -t) + d l I t
N / N
In the next group of terms, the binomial expansion of pN= ~ ~ ai,jyJx/= ~ aN-i(y)xl
((1 - t) + t) 2 = 1 is used to represent aN_ 2 as a quadratic t=0 1=0 /=0
polynomial in t, enabling one to combine it wtth those
resulting from expansion of the next x Homer's rule can now be applied to the univariate poly-
nomial coefficient at (y) at each step, and then to the result-
{do' (1-t) + d,' t} (Xo(1-t) + X N t) + eN_2((1-t) = ing polynomial in x

+ 2 t ( 1 - t ) + t =) = (Xodo ' +aN_2) ( l - t ) = pN = [ [ . . . [[aN,0X + (aN-lAY + aN-'l,0)] X

+ (Xodl I + X N d o I + 2aN_2) t ( l - t ) + ( X N d l j + a N _ 2 ) t =
+ ((#N-2,2Y + aN-2,1) Y + aN-2,0)] X.
= do= (1 - t) 2 + d t = t (1 -t) + d== t =
... ] X + {(... ((eO,NY + a0,N_ 1) y + a0,N_2) y
Continuing in this manner and expressing each new aN_ k +- -

as a degree k polynomial using the binomial expansion of

W Barycentric coordinates (also known as area or trilinear
coordinates) are used to map this bivariate polynomial over
an arbitrary triangular region 6'9. Barycentric coordinates
1, O, O)
consist of three parameters u, v, w and a single constraint
equation (u + v+ w = 1 ) resulting in two independent
(0, 1,0 variables. Within the boundary of this triangle defined by
the three points {P00, PNo, PoN}, the barycentnc coordi-
nates are all positive (0 ~ u, v, w ~ 1.0).
An arbitrary point P = {x,y} in the plane is expressed
in terms of its barycentric coordinates as
%
P=wPoo+UPNo+VPoN
(0,0, 1)
Following the algorithm for univariate polynomials, substi-
tutions are made in sequence, first), then x, in the bivariate
equation. This time a tetrahedral array of values di, j k is
Figure I. Barycentric coordinate system generated corresponding to each expansion of x and an

530 computer-a.ded design

analogous set of arrays c r,s h,m are created in the expansion c~l~=cr,I - ll~-I
, j Y No + C/,j.
r , * -1l , ,toN l h =O,...,r
of each ak 0'). or, k_1 [ h] i,j;)O
Examining the inner most pair of square brackets and + i,j Yoo + i,j aN-r'r-h i+j(~k
making use of the constraint (u + v + w = 1)
These results can now be included in the expansion of the
[aN, o(XooW+ XNoU + XoN v) + {¢N-1,1 (Yoow next x term. In an analogous fashion, the algorithm for
+ YNou + YON v) +aN.1,0(U+V+W)}] di, j h emerges

= aN, oXoow + aN,oXNoU + aN, oXoNV

l i , j < 0; k=0,... N
di~ = 0 i+j>h; '
+ (aN-1,1 Yoo + aN-1,0) W + (aN. 1 ,1 }"No + aN-1,0) u
+ (aN-1,1 Yoo + aN-1,0) v d.~. _ d k -1 X + d ~ -1 l k=O,...,N
t, I - I-1,1 NO Ij]-IXoN
= aN, OXoow + aN,OXNoU + aN,oXo N + Coo l l w i,j;~O
+dih, j-lXoo + cijh,h
i+j<h
+ ClottU + c01 tt v
=doo t w + dtolU + dol I v At the kth level, eli k, k must be computed prior to evaluat-
ing di] k. When completed, the dl] N represent scaled bi-
After k levels of substitution, expansion, and regrouping variate Bernstein polynomial coefficients. The true Bernstein
coefficients are retrieved as shown below
i+l~k h+1
' w k-i-l) x + aN_(h+l)(y))
(...(( z dll #ulvi . ..
i,J =0
i,j i+j~N
+ o~(y) )
This algorithm was encoded and tested against the indirect
The polynomtal a N_(/~ + 1 ) (Y) is at most degree k +1 in y. mapping algorithm introduced earlier. For low degree poly-
Let r=# +1, and rearrange this polynomial in y according to nomials (1-5), it ran 20-70% faster, and its performance
Homer's rule advantage increased with polynomial degree. Direct conver-
sion of degree ten polynomials required less than a third,
arN_r(y) = ( ( . . . ((aN_r, rY + aN-r,r-l) Y + aN-r,r-2) Y and degree fifteen less than a fifth, of the time taken by
+" • • +aN-r, 1)Y + aN-r, 0) the indirect algorithm.

Substituting f o r y and expanding the innermost pair of

CONCLUSIONS
parenthesis using (u + v + w) = 1 to express aN_r, r - 1 as a
linear polynomial yields A more efficient and robust algorithm has been presented
for converting a bivariate polynomial expressed in "the
aN-r,r(Yoow + YNoU + YoNV) + aN-r,r-1 (tl+v+w) standard power basis directly to a barycentric coordinate
based Bemstein form over an arbitrary triangular region.
= (aN_r,rYoo +aN-r,r-])w+ (aN-r, rYNo +aN-r,r-1) u This represents an improvement over existing algorithms
+ (aN_r, rYo N +aN_r,r.1) v which first convert to a Bernstein form over the standard
triangle and then map one vertex at a time to the arbitrary
= 4 0 l w + 4 o 1 M't-Co1
. ,,1 V triangular region, possibly having to avoid degenerate
intermediate triangles in the process. Studies of bivariate
Using the multinomial expansion of (u + v+ w) 2 = 1 to algebraic equations may now include this more robust
express aN_r, r -2 as a quadratic polynomial and combining technique in the library of algorithms already available for
with terms from expanding the n e x t y reduces to working with Bernstein polynomials ~'l't°'ll'12.
(c~oI w + C;'oI u + c;', 1 v) (Yoow + YNoU + YoN v)
ACKNOWLEDGEMENTS
+ aN_r,r_2(U 2 + V2 + w 2 + 2UV + 2UW + 2VW)
The authors would like to express their appreciation for
= (cr~d Yoo +aN-,,r-2)w 2 + (C~o1 YNo +aN-r,,-2)" 2 the support provided by Control Data Corporation under
•
+ (c;', 1 YoN + aN-r, r-2) V2 + (C;'o1 YNo ~" 61,.
Clo 1"oo grant 81 P04 and to the Purdue Engineering Research Center
established by the National Science Foundation research
+ 2aN_r,r_2)UW + (C~;o] YoN + c~11YNo + 2aN-r,r-2)uv grant CDR8500022.
+ (4ol YoN + c;'J Yoo + 2aN_,,r_2) ~
= ,,2 ,,2 + cr,?~ REFERENCES
+ ' + + clo +
1 Faux, I D and Pratt, M J Computationalgeometry for
i+1 < 2 design and manufacture Ellis Horwood Publishers, UK
= ~: c~,/2Jv/w2-i-J
i,j=O (1981)
2 Mortenson, M E Geometric modeling John Wiley &
Continuing in this manner, a pattern emerges Sons, New York, USA (1985)
3 Rogers, D A and Adams, ] A Mathematical elements
C~)O0 =aN.r, r , c~ h-~O I Ii ,+j <] O for computer graphics McGraw Hill, New York, USA
>h (1979)

volume 18 number 10 december 1986 531

4 Sederberg,Thomas W 'Planar piecewlse algebraic curves' Farin, G 'B~zier polynomials over triangles and the
Comput. Aided Geometric Des. Vol 1 No 4 (1985) construction of plecewise Cr polynomials' TR/91
pp 24"1-256 Department of Mathematics, Brunel Unwersky,
5 Geisow, A 'Surface interrogations', PhD Dissertation, Uxbridge, Middlesex, UK (1980)
School of Computing Studies and Accountancy,
10 Goldman, R N 'Using degenerate B~zJer triangles and
UnJversity of East Angha, UK (1983)
tetrahedra to subdivide B~zier curves' Comput. Aided
6 Farin, G Trlangu/ar Bernstein-B#zlerpatches Depart- Geometric Des. Vol 14 No 6 (1982) pp 307-311
ment of Mathematics, University of Utah, Salt Lake
City, UT, USA (1986) 11 Goldman, R N 'Subdivision algorithms for B~zier
7 Filip, D 'Practical considerations for triangular patch triangles' Comput. Aided Geometric Des. Vol 15
surfaces' MS Thesis, University of California, Berkeley, No 3 (1983) pp 159-166
CA, USA (December 1985) 12 Filip, D 'Adaptive subdivision algorithms for B~zmr
8 Goldman, R N and Filip, D J 'Conversion from B6zier triangles' Comput.-Aided Des. Vol 18 No 2 (March
rectangles to B~zier triangles' (preprint 1986) 1986)

532 computer-aided design