1、Rendering Curves and Surfaces1Angel: Interactive Computer Graphics 5E Addison-Wesley 2009原著Ed AngelProfessor of Computer Science, Electrical and Computer Engineering, and Media ArtsUniversity of New Mexico編輯 武漢大學(xué)計算機學(xué)院圖形學(xué)課程組2Angel: Interactive Computer Graphics 5E Addison-Wesley 2009ObjectivesIntrodu

2、ce methods to draw curvesApproximate with linesFinite DifferencesDerive the recursive method for evaluation of Bezier curves and surfacesLearn how to convert all polynomial data to data for Bezier polynomials3Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Evaluating PolynomialsSimplest m

3、ethod to render a polynomial curve is to evaluate the polynomial at many points and form an approximating polylineFor surfaces we can form an approximating mesh of triangles or quadrilateralsUse Horners method to evaluate polynomials p(u)=c0+u(c1+u(c2+uc3)3 multiplications/evaluation for cubic4Angel

4、: Interactive Computer Graphics 5E Addison-Wesley 2009Finite DifferencesFor equally spaced uk we define finite differencesFor a polynomial of degree n, the nth finite difference is constant5Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Building a Finite Difference Tablep(u)=1+3u+2u2+u36

5、Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Finding the Next ValuesStarting at the bottom, we can work up generating new values for the polynomial7Angel: Interactive Computer Graphics 5E Addison-Wesley 2009deCasteljau RecursionWe can use the convex hull property of Bezier curves to ob

6、tain an efficient recursive method that does not require any function evaluationsUses only the values at the control pointsBased on the idea that “any polynomial and any part of a polynomial is a Bezier polynomial for properly chosen control data”8Angel: Interactive Computer Graphics 5E Addison-Wesl

7、ey 2009Splitting a Cubic Bezierp0, p1 , p2 , p3 determine a cubic Bezier polynomialand its convex hullConsider left half l(u) and right half r(u)9Angel: Interactive Computer Graphics 5E Addison-Wesley 2009l(u) and r(u)Since l(u) and r(u) are Bezier curves, we should be able tofind two sets of contro

8、l points l0, l1, l2, l3 and r0, r1, r2, r3that determine them10Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Convex Hullsl0, l1, l2, l3 and r0, r1, r2, r3each have a convex hull thatthat is closer to p(u) than the convex hull of p0, p1, p2, p3This is known as the variation diminishing p

9、roperty.The polyline from l0 to l3 (= r0) to r3 is an approximation to p(u). Repeating recursively we get better approximations.11Angel: Interactive Computer Graphics 5E Addison-Wesley 2009EquationsStart with Bezier equations p(u)=uTMBpl(u) must interpolate p(0) and p(1/2)l(0) = l0 = p0l(1) = l3 = p

10、(1/2) = 1/8( p0 +3 p1 +3 p2 + p3 )Matching slopes, taking into account that l(u) and r(u)only go over half the distance as p(u)l(0) = 3(l1 - l0) = p(0) = 3/2(p1 - p0 )l(1) = 3(l3 l2) = p(1/2) = 3/8(- p0 - p1+ p2 + p3)Symmetric equations hold for r(u)12Angel: Interactive Computer Graphics 5E Addison-

11、Wesley 2009Efficient Forml0 = p0r3 = p3l1 = (p0 + p1)r1 = (p2 + p3)l2 = (l1 + ( p1 + p2)r1 = (r2 + ( p1 + p2)l3 = r0 = (l2 + r1)Requires only shifts and adds!13Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Every Curve is a Bezier CurveWe can render a given polynomial using the recursive

12、 method if we find control points for its representation as a Bezier curve Suppose that p(u) is given as an interpolating curve with control points qThere exist Bezier control points p such thatEquating and solving, we find p=MB-1MIp(u)=uTMIqp(u)=uTMBp14Angel: Interactive Computer Graphics 5E Addiso

13、n-Wesley 2009MatricesInterpolating to BezierB-Spline to Bezier15Angel: Interactive Computer Graphics 5E Addison-Wesley 2009ExampleThese three curves were all generated from the sameoriginal data using Bezier recursion by converting allcontrol point data to Bezier control pointsBezierInterpolatingB S

14、pline16Angel: Interactive Computer Graphics 5E Addison-Wesley 2009SurfacesCan apply the recursive method to surfaces if we recall that for a Bezier patch curves of constant u (or v) are Bezier curves in u (or v)First subdivide in u Process creates new points Some of the original points are discarded

15、original and keptneworiginal and discarded17Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Second Subdivision16 final points for1 of 4 patches created18Angel: Interactive Computer Graphics 5E Addison-Wesley 2009NormalsFor rendering we need the normals if we want to shadeCan compute from

16、parametric equationsCan use vertices of corner points to determineOpenGL can compute automatically19Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Utah TeapotMost famous data set in computer graphicsWidely available as a list of 306 3D vertices and the indices that define 32 Bezier patches20Angel: Interactive Computer Graphics 5E Addison-Wesley 2009QuadricsAny quadric can be written as the quadratic form pTAp+bTp+c=0 where p=x, y, zT with