AFFINE ARITHMETIC AND BERNSTEIN HULL METHODS FOR ALGEBRAIC CURVE DRAWING
- 格式：pdf
- 大小：251.34 KB
- 文档页数：13
Chapter1AFFINE ARITHMETIC AND BERNSTEIN HULL METHODS FOR ALGEBRAIC CUR VE DRA WINGHuahao Shou,Guojin WangDepartment of Mathematics,Zhejiang University,Hangzhou,ChinaH.Shou@,wgj@Ralph MartinDepartment of Computer Science,CardiffUniversity,Cardiff,UK.Ralph.Martin@Irina VoiculescuComputing Laboratory,Oxford University,Oxford,UK.irina@Adrian BowyerDepartment of Mechanical Engineering,Bath University,Bath,UK.A.Bowyer@Abstract We compare approaches to location of the algebraic curve f(x,y)=0ina rectangular region of the plane,based on recursive use of conservativeestimates of the range of the function over a rectangle.Previous workshowed that performing interval arithmetic in the Bernstein basis ismore accurate than using the power basis,and that affine arithmetic inthe power basis is better than using interval arithmetic in the Bernsteinbasis.This paper shows that using affine arithmetic with the Bernsteinbasis gives no advantage over affine arithmetic with the power basis.Italso considers the Bernstein coefficient method based on the convex hullproperty,which has similar performance to affine arithmetic. Keywords:Interval arithmetic,affine arithmetic,Bernstein hull,curve drawing121.IntroductionSolving f(x,y)=0in a rectangular area[x,x]×[y,y],where f(x,y)is a polynomial,is a problem with many practical in CAD and computer graphics.One such example is drawing the algebraic curve represented by f(x,y)=0;other applications include surface-surface intersection and silhouette edge detection of a parametric surface[12, 15,17].Let C be an algebraic curve defined by the equation f(x,y)=0.A simple and general technique for computing an approximation of C ona rectangular regionΩas described in[9]is:(1)decomposeΩinto small cells,typically on a rectangular grid;(2)identify which cells intersect C;(3)approximate C within each intersecting cell(e.g.fill the cell if it is a screen pixel).Finding the intersecting cells is usually the most expensive step in this method.The simplest approach is to test all cells,but this is com-putationally very expensive.Several methods exist forfinding the cells intersecting a curve C with-out visiting all the cells in a cellular decomposition of a regionΩ.Con-tinuation methods[4]sample the curve only in the immediate neigh-bourhood of known intersecting cells.They start from one or more seed cells known to contain the curve,and follow it into adjacent cells.The fundamental difficulty of this approach isfinding a complete set of initial seed cells intersecting every connected component of C inΩ.Large portions ofΩcan be discarded quickly and reliably if the ab-sence of C in a particular region can be proved.Hierarchical decomposi-tion methods[6,15,16,17]rely on such a test to exploreΩrecursively, starting withΩitself as the initial cell.If a cell is proved to be empty,it is ignored;otherwise,it is subdivided into smaller cells,which are then explored recursively,until the cells are small enough to approximate C. Range analysis is used to test if the curve passes through a cell.Range analysis methods output a range of values guaranteed to include the val-ues the function takes over a given range of values for x and y.Interval arithmetic(IA)[11]provides a natural tool for range analysis[13].Hi-erarchical decomposition methods based on IA have been widely used in computer graphics applications[6,15,17].The main weakness of IA is that it tends to be too conservative[5,8, 9],i.e.the range for the function output by IA is much wider than the actual range of values the function takes over a given interval.To solve this problem,Comba and Stolfi[5]proposed a new model for numerical computation,called affine arithmetic(AA).Both IA and AA can be usedAffine Arithmetic and Bernstein Hull Methods3 to manipulate imprecise values and to evaluate functions over intervals. Both can also keep track of truncation and round-offerrors.However,in contrast to IA,AA maintains dependencies between the sources of error arising from different variables,and thus manages to compute signifi-cantly tighter error bounds.AA has been used as a replacement for IA in various computer graphics applications,such as ray tracing,intersec-tion testing,enumeration of implicit curves and surfaces,and sampling for procedural shaders[5,8,9,10].As AA computes tighter intervals than IA,it is possible to draw algebraic curves using the former more efficiently and with higher quality than using the latter[9,19].Because of the way arithmetic operators work in IA,the basis used to express the polynomial f(x,y)affects the range for the function output by IA evaluation.IA using the Bernstein basis is more accurate than IA using the power basis.Even more,AA using the power basis is better than IA using the Bernstein basis[18].The same paper[18] asked whether AA using the Bernstein basis would be even better.The current paper shows that AA in the Bernstein basis has no advantage over AA in the power form.Range analysis may also be performed using the Bernstein coefficient (BC)method based on the Bernstein convex hull property[13].If a polynomial is written in the Bernstein basis,its range is bounded by the values of the minimum and maximum Bernstein coefficients.We compare the performance and efficiency of the AA method and the BC method;we also show results of using IA methods using the power basis and Bernstein basis.2.Algebraic curve drawing algorithmThe basic strategy[19]for drawing an algebraic curve f(x,y)=0 in a given rectangular interval[x,x]×[y,y]is to evaluate f(x,y)over the desired interval using some range analysis evaluation method giving a range F=[F,F].If the resulting interval does not contain0,the curve cannot be present.If it does contain0,the region may or may not contain the mathematical curve,so the interval is divided horizontally and vertically at its mid-point,and the pieces are considered in turn. The process stops when an interval consisting of a single pixel is left. In such a case wefill the pixel anyway,even though we are still unsure whether the curve is actually present.This may result in a“fat”curve if the test is too conservative,i.e.pixels may befilled which do not actually contain the curve.43.Interval arithmetic methodTraditional IA methods are used as a reference for comparison in this paper.An interval x=[a,b]is a set of real numbers defined by [a,b]={x|a≤x≤b}.Rules used to perform arithmetic on intervals may be found in[11].The natural interval extension f(x,y)of a bivariate polynomial f(x,y) is obtained by replacing each occurrence of x and y in f(x,y)by intervals x and y,and evaluating the resulting interval expression using the above definitions.The result is itself an interval.As already noted,when using IA,the basis used for the polynomial expression can affect the result[3].Suitably rearranging the function can give tighter bounds on the result,although the result will be still conservative,not exact.3.1IA using the power basisHere we describe how to use IA to evaluate a polynomial in two vari-ables written in the power basis.Letf(x,y)=ni=0mj=0A ij x i y j,(x,y)∈Ω=[x,x]×[y,y].It is helpful to rewrite it in matrix representation:f(x,y)=XAY,where X=(1,x,...,x n),Y=(1,y,...,y m)T.X and Y arefirst computed using IA rules,and then the matrix product is found.The matrix representa-tion of the polynomial power form plays a crucial role in the matrix AA evaluation method[14].3.2IA using the Bernstein basisThe Bernstein basis is widely used for generating B´e zier,B-spline and NURBS curves and surfaces[2].Bowyer,Berchtold,and Voiculescu[1, 2,3,18]have extensively considered the use of IA and multivariate Bernstein-form polynomials in geometric modelling.Conversion from power form to Bernstein form is discussed in[1,2].The Bernstein form often has many more terms than the power form. Furthermore,these contain repeated subexpressions of x,(1−x),y and (1−y).As repeated expressions can lead to excessive conservativeness in interval arithmetic,one might doubt the performance of the Bern-stein form with interval arithmetic.Surprisingly,results show that the Bernstein form generally does better than the much simpler power form.Affine Arithmetic and Bernstein Hull Methods5 4.Affine arithmetic methodAs noted,the main weakness of IA is that it tends to be too conserva-tive.In long computation chains,where the intervals computed by one stage are the inputs to the following stage,the relative accuracy of the computed intervals decreases exponentially.Unfortunately,long compu-tation chains are not uncommon in geometric computing applications.To address the error explosion problem in IA,Comba and Stolfi[5] proposed affine arithmetic(AA).Like IA,AA keeps track automatically of the round-offand truncation errors affecting each computed quantity. Unlike IA,however,AA keeps track of correlations between quantities. For example,in computing x×x,IA treats each x as if it were a separate quantity,and would allow each x independently to be anywhere in its range.In contrast,AA“knows”they are the same variable—if thefirst x is near the lower end of its range,so is the second x.As a result, AA is able to provide much tighter intervals than IA,especially in long computation chains.In AA,an uncertain quantity x is represented by an affine formˆx that is afirst-degree polynomial in a set of noise symbolsεi:x=ˆx=x0+x1ε1+...+x mεm=x0+mi=1x iεi.Here the values of the noise symbolsεi are unknown but are in the range[−1,1],and represent the uncertainty in x.Each corresponding coefficient x i is a real number that determines the magnitude and sign of εi.Eachεi stands for an independent source of uncertainty contributing to the total uncertainty in x.One may make m as large as necessary in order to represent all sources of uncertainty.(When converting an interval to AA form,we start with m=1,but m may increase as nonlinear computations are performed,as explained later.)If the same noise symbolεi appears in two or more affine forms(e.g.in bothˆx and ˆy),it indicates that some dependencies and correlations exist between the underlying quantities x and y.An ordinary interval[x,x]representing a quantity x may be written in affine form as[5,8,9]ˆx=x0+x1εx,where x0=(x+x)/2,x1=(x−x)/2.Conversely,given an affine formˆx=x0+x1ε1+...+x mεm,the range of possible values of the corresponding interval is[x,x]=[x0−ξ,x0+ξ],whereξ=mi=1|x i|.6Various simple arithmetic operations are defined for AA in [5].In AA,ˆx −ˆx =0and (2ˆx +ˆy )−ˆx =ˆx +ˆy ,whereas IA produces wider inter-vals.The multiplication of two affine forms ˆx ׈y produces a quadratic polynomial in the noise symbols εi .The quadratic term is replaced by a suitable coefficient multiplying a new noise symbol εk .This approx-imation may still produce a resulting interval up to four times as wide as the exact range of the quadratic term.Unlike IA,which does not obey the distributive law,AA satisfies all commutative,associative and distributive laws.In this respect,there is no difference between AA and real arithmetic.Now,the various ways of expressing a polynomial function using different bases does nothing other than rearranging the terms.This does not affect the arithmetic of the polynomial,and hence does not affect the result of applying AA to an equivalent polynomial form.Therefore,when AA is involved,we only need to consider the power basis.(One may argue that in practice this is not quite true because of the non–commutativity,associativity and distributivity of computer real arithmetic.However,machine precision is negligible when compared with the length of the intervals used in solving the curve drawing problem.)Since multiplication of affine forms may produce results much larger than the exact range,we use the matrix AA polynomial evaluation method proposed in [14],as below.This provides a better estimate for the range of a polynomial,using AA.This works by first converting the interval forms [x,x ]and [y,y ]to affine forms:ˆx =x 0+x 1εx ,ˆy =y 0+y 1εy .Then letˆX =(1,εx ,...,εn x ),ˆY =(1,εy ,...,εm y )T ,and define matrices B and C such that B ij = j i x j −i 0x i 1,i ≤j 0,i >j,i =0,1,...,n ;j =0,1,...,n,C ij = 0,i <j i j y i −j 0y j 1,i ≥j ,i =0,1,...,m ;j =0,1,...,m.Now,if we compute D from B and C ,and the original coefficient matrix A using D =BAC,we getf (ˆx ,ˆy )=ˆXD ˆY =ni =0m j =0D ij εi x εj yThis is the exact affine form which we now wish to convert back to interval form [F ,F ].The conversion procedure works as follows.If i isAffine Arithmetic and Bernstein Hull Methods7 even and j is even,thenεi xεj y∈[0,1],otherwiseεi xεj y∈[−1,1].Thus:F=D00+mj=1max(0,D0j),if j is even|D0j|,otherwise+ni=1max(0,D i0),if i is even|D i0|,otherwise+ni=1mj=1max(0,D ij),if i,j are both even|D ij|,otherwiseand similarly for F.5.Bernstein coefficient methodA different method for bounding a polynomial over an interval de-pends on the use of the Bernstein convex hull property[13].It guaran-tees that the value of a polynomial in the Bernstein basis is bounded by the values of the minimum and maximum Bernstein coefficients.To utilize the Bernstein convex hull property for evaluation of f(x,y) in the region[x,x]×[y,y],we mustfirst convert the range[x,x]×[y,y] to[0,1]×[0,1].This can be done by a change of variables to˜x and˜y:x=x+(x−x)˜x,y=y+(y−y)˜y.Then f(x,y)=˜X(EAR T)˜Y T where˜X=(1,˜x,...,˜x n),˜Y=(1,˜y,...,˜y n),E ij=jix j−i(x−x)i,i≤j0,i>j,i=0,1,...,n;j=0,1,...,n,andR ij=jiy j−i(y−y)i,i≤j0,i>j,i=0,1,...,m;j=0,1,...,m.Setting G=EAR T,we complete the range conversion using˜f(˜x,˜y)=˜XG˜Y T,(˜x,˜y)∈[0,1]×[0,1].Next we need to convert the above polynomial from the power basis to the Bernstein basis.(This is well-known to be an ill-conditioned prob-lem,but as we will be computing conservative bounds using intervals, we can still arrange to guarantee the correctness of the results.Ill effects will show up as fatter curves when plotting.)8Let˜B (˜X )=(B n 0(˜x ),B n 1(˜x ),...,B n n (˜x )),˜B (˜Y )=(B m 0(˜y ),B m 1(˜y ),...,B m m (˜y )),where B i j (u )= i ju j (1−u )i −j are the Bernstein basis functions.Then ˜B(˜X )=˜XH,˜B (˜Y )=˜Y P,whereH ij =0,i <j (−1)i −j n j n −j i −j ,i ≥j ,i =0,1,...,n ;j =0,1,...,n,P ij =0,i <j (−1)i −j m j m −j i −j ,i ≥j ,i =0,1,...,m ;j =0,1,...,m.Then ˜f (˜x ,˜y )=˜B(˜X )H −1G (P T )−1˜B (˜Y )T ,so,letting Q =H −1G (P T )−1,we obtain ˜f (˜x ,˜y )=˜B (˜X )Q ˜B (˜Y )T ,(˜x ,˜y )∈[0,1]×[0,1].The conversion from the power basis to Bernstein basis is completed.By the Bernstein convex hull property [7]we know that F ≤˜f (˜x ,˜y )≤F ,(˜x ,˜y )∈[0,1]×[0,1],F =min i,j {Q ij },F =max i,j{Q ij },i ∈{0,1,...,n },j ∈{0,1,...,m },and so F ≤f (x,y )≤F ,(x,y )∈[x,x ]×[y,y ],giving the desired bounds of f (x,y )on range [x,x ]×[y,y ].6.ExamplesHere,we briefly compare the accuracy and speed of each method mentioned above using two examples.In each case we plot a curve f (x,y )=0using the algorithm described in Section 2,using a grid of 256×256pixels.In the tables of results,we use the following notation:IAP,IAB (interval arithmetic using the power or Bernstein basis),AA (affine arithmetic matrix method),BC (Bernstein coefficient method).The first example,from [18],shown in Figures 1.1–1.4,plots the curve 0.945xy −9.43214x 2y 3+7.4554x 3y 2+y 4−x 3=0on [0,1]×[0,1].The second example,from [19],shown in Figures 1.5–1.8,plots the curve −1801/50+280x −816x 2+1056x 3−512x 4+1601/25y −512xy +1536x 2y −2048x 3y +1024x 4y =0on [0,1]×[0,1].Affine Arithmetic and Bernstein Hull Methods9Figure 1.1.Example 1drawn using IAand the power basis.Figure 1.2.Example 1drawn using IA and the Bernstein basis.Figure 1.3.Example 1drawn using AA.Figure 1.4.Example 1drawn usingBC.To compare the methods,various quantities were measured:The percentage of the overall area definitely classified as not con-taining the curve:the bigger the better.The number of subdivisions needed:the lower the better,because of overheads incurred in recursion.The number of additions (and subtractions),and multiplications needed:the lower the better.Tables 1.1and 1.2give details of these quantities for both test cases.10Figure1.5.Example2drawn using IAand the power basis.Figure1.6.Example2drawn using IAand the Bernstein basis.Figure 1.7.Example2drawn usingAA.Figure 1.8.Example2drawn usingBC.parison of IAP,IAB,AA and BC methods for thefirst example. Methods Area Classified Subdivisions Additions Multiplications IAP93.8568390914937981876438 IAB97.5906156421493362615424 AA99.07236341355919870189 BC99.096758514296981108000REFERENCES11 parison of IAP,IAB,AA and BC methods for the second example.Methods Area Classified Subdivisions Additions Multiplications IAP15.835619562933663811580850 IAB53.9001127351186274614161596 AA99.292611660781430318 BC99.3042465576289409917We consider the accuracyfirst.As can be seen from the percentage of area definitely classified,IAB is better than IAP,AA is better than IAB(sometimes much better as shown in Example2),and BC is slightly better than AA.Next we consider the number of arithmetic operations.In general, there is no definite order in terms of the number of operations(addi-tions and multiplications)involved.However,we notice IAB behaves worst,probably because of the complexity of the expressions involved in the examples.For simple curves like thefirst,the performance of the AA and BC methods is generally similar to that for the IAP method, although sometimes IAP can be several times faster.However,for more complicated curves,the AA and BC methods are often substantially faster—over20times faster in the case of the second curve.7.ConclusionsFirstly,we have shown that the choice of polynomial basis does not affect results obtained with AA,unlike what happens with IA.Secondly, we conclude from the above examples,and other experiments we have carried out,that the AA and BC methods are roughly similar in accu-racy,and generally more accurate than IAP and IAB methods.Further-more,while there is sometimes a time penalty for using these methods, in tricky cases,they are generally faster than the IA methods. AcknowledgmentsWe would like to thank the China Scholarship Council for funding Huahao Shou.We would also like to thank Bath University and the ORS award scheme for funding Irina Voiculescu.References[1]Berchtold,J.,The Bernstein Form in Set-Theoretic Geometric Mod-elling,PhD Thesis,University of Bath,2000.12[2]Berchtold,J.,Bowyer, A.,Robust Arithmetic for MultivariateBernstein-Form Polynomials,Computer Aided Design,2000,32: 681–689.[3]Bowyer,A.,Berchtold,J.,Eisenthal,D.,Voiculescu,I.,and Wise,K.,Interval Methods in Geometric Modelling,Geometric Modeling and Processing2000,Eds.Martin,R.,Wang,W.,IEEE Computer Society Press,2000,321–327.[4]Chandler,R. E.,A Tracking Algorithm for Implicitly DefinedCurves,IEEE Computer Graphics&Applications,1988,8(2):83–89.[5]Comba,J.L.D.,Stolfi,J.,Affine Arithmetic and its Applicationsto Computer Graphics,Anais do VII SIBGRAPI(Brazilian Sympo-sium on Computer Graphics and Image Processing),Recife,Brazil, 1993,9–18.[6]Duff,T.,Interval Arithmetic and Recursive Subdivision for ImplicitFunctions and Constructive Solid Geometry,Computer Graphics (SIGGRAPH’92Proceedings),1992,26(2):131–138.[7]R.T.Farouki,V.T.Rajan,On the Numerical Condition of Polyno-mials in Bernstein Form,Computer Aided Geometric Design,191–216,1987.[8]de Figueiredo,L.H.,Surface Intersection Using Affine Arithmetic,Proceedings of Graphics Interface’96,Eds.MacKenzie S.,Stewart J.,Morgan Kaufmann,1996,168–175.[9]de Figueiredo,L.H.,Stolfi,J.,Adaptive Enumeration of ImplicitSurfaces with Affine Arithmetic,Computer Graphics Forum,1996, 15(5):287–296.[10]Heidrich,W.,Slusallek,P.,Seidel,H.P.,Sampling of ProceduralShaders using Affine Arithmetic,ACM Transaction on Graphics, 1998,17(3):158–176.[11]Moore,R.E.,Methods and Applications of Interval Analysis,Soci-ety for Industrial and Applied Mathematics,Philadelphia,1979. [12]Mudur,S.P.,Koparkar,P.A.,Interval Methods for ProcessingGeometric Objects,IEEE Computer Graphics&Applications,1984, 4(2):7–17.[13]Ratschek,H.,Rokne,J.,Computer Methods for the Range of Func-tions,Ellis Horwood Ltd.,1984.[14]Shou H.,Martin R.,Voiculescu I.,Bowyer A.,Wang G.,AffineArithmetic in Matrix Form for Algebraic Curve Drawing,Submitted to Progress in Natural Science,2001.REFERENCES13 [15]Snyder,J.M.,Interval Analysis for Computer Graphics,ComputerGraphics(SIGGRAPH’92Proceedings),1992,26(2):121–130. [16]Suffern,K.G.,Quadtree Algorithms for Contouring Functions ofTwo Variables,The Computer Journal,1990,33:402–407.[17]Suffern,K.G.,Fackerell,E.D.,Interval Methods in ComputerGraphics,Computer&Graphics,1991,15:331–340.[18]Voiculescu,I.,Berchtold,J.Bowyer,A.Martin,R.R.,Zhang,Q.,Interval and Affine Arithmetic for Surface Location of Power-and Bernstein-form Polynomials,The Mathematics of Surfaces IX,Eds.Cipolla R.&Martin,R.R.,Springer,2000,410–423.[19]Zhang,Q.,Martin,R.R.,Polynomial Evaluation using Affine Arith-metic for Curve Drawing,Proceedings of Eurographics UK2000, Eurographics UK,Abingdon,2000,49–56.。
