CS-184: Computer GraphicsLecture #13: Curves and Surfaces Prof. James O’BrienUniversity of California, BerkeleyV2011-F-13-1.02Today•General curve and surface representations•Splines and other polynomial bases3Geometry Representations•Constructive Solid Geometry (CSG)•Parametric•Polygons•Subdivision surfaces•Implicit Surfaces•Point-based Surface•Not always clear distinctions•i.e. CSG done with implicits4Geometry RepresentationsObject made by CSGConverted to polygons5Geometry RepresentationsObject made by CSGConverted to polygonsConverted to implicit surface6Geometry RepresentationsacmTransactionson GraphicsOctober 2002Volume 21 Number 4CSG on implicit surfaces7Geometry RepresentationsPoint-based surface descriptionsOhtake, et al., SIGGRAPH 20038Geometry RepresentationsSubdivision surface(different levels of refinement)Images from Subdivision.org9Geometry Representations•Various strengths and weaknesses•Ease of use for design•Ease/speed for rendering•Simplicity•Smoothness•Collision detection•Flexibility (in more than one sense)•Suitability for simulation•many others...10Parametric Representationsx = x(u)x 2<nu 2<x = x(u)u 2<2u, v 2<u, v, w 2<u 2<3x = x(u, v, w)Curves:Surfaces:x = x(u, v)x 2<nx = x(u)Volumes:x 2<nand so on...Note: a vector function is really n scalar functions11•Same curve/surface may have multiple formulaeParametric Rep. Non-unique-1 0 1 2 3-10123-1 0 1 2 3-10123x(u)=[u, u]x(u)=[u3,u3]12Simple Differential Geometry•Tangent to curve•Tangents to surface•Normal of surface•Also: curvature, curve normals, curve bi-normal, others...•Degeneracies: or t(u)=@x@uutu(u, v)=@x@uu,vtv(u, v)=@x@vu,v@x/@u =0tu⇥ tv=0ˆn =tu⇥ tv||tu⇥ tv||Non Orthogonal Tangents13cos(2) cos(pi/2)sin(2) cos(/2)sin( /2)cos(2) cos1212(1 ||) cos(6) + cos1212(1 ||) cos(6) + sin(2)sin1212(1 ||) cos(6) + [0..1] [1..1]14Discretization•Arbitrary curves have an uncountable number of parameters-1 0 1 2 3-10123i.e. specify function value at all points on real number line15Discretization•Arbitrary curves have an uncountable number of parameters•Pick complete set of basis functions•Polynomials, Fourier series, etc.•Truncate set at some reasonable point•Function represented by the vector (list) of•The may themselves be vectorsx(u)=1Xi=0cii(u)x(u)=3Xi=0cii(u)=3Xi=0ciuicicix(u)=3Xi=0cii(u)16Polynomial Basis•Power Basisx(u)=dXi=0ciuix(u)=C · PdC =[c0,c1,c2,...,cd]Pd= [1, u, u2,...,ud]The elements of are linearly independant! i.e. no good approximationPduk6⇡Xi6=kciuiSkipping something would lead to bad results... odd stiffness17Specifying a Curveu0u1tu(u0)tu(u1)x(u0)x(u1)Given desired values (constraints) how do we determine the coefficients for cubic power basis?u0=0 u1=1For now, assume 18Specifying a Curvetu(u0)tu(u1)x(u0)x(u1)Given desired values (constraints) how do we determine the coefficients for cubic power basis?01x(0) = c0= x0x(1) =Pci= x1x0(0)= c1= x00x0(1)=Pici= x0119Specifying a Curvetu(u0)tu(u1)x(u0)x(u1)Given desired values (constraints) how do we determine the coefficients for cubic power basis?012666666666666666666666666666666664x0x1x00x013777777777777777777777777777777775=266666666666666666666666666666666410001111010001233777777777777777777777777777777775·2666666666666666666666666666666664c0c1c2c33777777777777777777777777777777775p = B · c20Specifying a Curvetu(u0)tu(u1)x(u0)x(u1)Given desired values (constraints) how do we determine the coefficients for cubic power basis?01c = H· pH= B1=26666666666666666666666666666666641000001033212 211377777777777777777777777777777777521Specifying a CurveGiven desired values (constraints) how do we determine the coefficients for cubic power basis?c = H· pH= B1=26666666666666666666666666666666641000001033212 2113777777777777777777777777777777775tu(u0)tu(u1)x(u0)x(u1)01x(u)=P3· c = P3Hp=26666666666666666666666666666666641+0u 3u2+2u30+0u +3u2 2u30+1u 2u2+1u30+0u 1u2+1u33777777777777777777777777777777775p22Specifying a CurveGiven desired values (constraints) how do we determine the coefficients for cubic power basis?c = H· ptu(u0)tu(u1)x(u0)x(u1)01x(u)=26666666666666666666666666666666641+0u 3u2+2u30+0u +3u2 2u30+1u 2u2+1u30+0u 1u2+1u33777777777777777777777777777777775px(u)=3Xi=0pibi(u)Hermite basis functions23Specifying a CurveGiven desired values (constraints) how do we determine the coefficients for cubic power basis?x(u)=3Xi=0pibi(u)Hermite basis functionsx(u)=26666666666666666666666666666666641+0u 3u2+2u30+0u +3u2 2u30+1u 2u2+1u30+0u 1u2+1u33777777777777777777777777777777775p24Hermite Basis•Specify curve by •Endpoint values•Endpoint tangents (derivatives)•Parameter interval is arbitrary (most times)•Don’t need to recompute basis functions•These are cubic Hermite•Could do construction for any odd degree• derivatives at end points(d 1)/225Cubic Bézier•Similar to Hermite, but specify tangents indirectlyx0= p0x1= p3x00=3(p1 p0)x01=3(p3 p2)Note: all the control points are points in space, no tangents.26Cubic Bézier•Similar to Hermite, but specify tangents indirectlyx0= p0x1= p3x00=3(p1 p0)x01=3(p3 p2)266666666410001111010001233777777775c =26666666641000000133 0 000333777777775pc =2666666664100033 0 03 63 013 313777777775pc = Zp27Cubic BézierBézier basis functionsc = Zpc =2666666664100033 0 03 63 013 313777777775px(u)=26641 3u +3u2 1u30+3u 6u2+3u30+0u +3u2 3u30+0u +0u2+1u33775px(u)=P3· c28Changing Bases•Power basis, Hermite, and Bézier all are still just cubic polynomials•The three basis sets all span the same space•Like different axes in •Changing basis<3<4c = ZpZc = HpHpZ= 1ZHpH29Useful Properties of a Basis•Convex Hull•All points on curve inside convex hull of control points•Bézier basis has convex hull propertyXibi(u)=1 bi(u) 0 8u 2 ⌦30Useful Properties of a Basis•Invariance under class of transforms•Transforming curve is same as transforming control points• Bézier basis invariant for affine transforms•Bézier basis NOT invariant for perspective
View Full Document