Question? Leave a message!




Curve Properties & Conversion, Surface Representations

Curve Properties & Conversion, Surface Representations
6.837 Computer Graphics Curve Properties & Conversion, Surface Representations vectorportal.com 6.837 – Matusik 1Cubic Bezier Splines • P(t) = (1-t)³ P1 + 3t(1-t)² P2 + 3t²(1-t) P3 + t³ P4 2Bernstein Polynomials • For Bézier curves, the basis polynomials/vectors are Bernstein polynomials • For cubic Bezier curve: B1(t)=(1-t)³ B2(t)=3t(1-t)² B3(t)=3t²(1-t) B4(t)=t³ (careful with indices, many authors start at 0) • Defined for any degree 3General Spline Formulation • Geometry: control points coordinates assembled into a matrix (P1, P2, …, Pn+1) • Power basis: the monomials 1, t, t2, ... • Cubic Bézier: 4Questions? 5Linear Transformations & Cubics • What if we want to transform each point on the curve with a linear transformation M? P’(t)= M 6Linear Transformations & Cubics • What if we want to transform each point on the curve with a linear transformation M? – Because everything is linear, it is the same as transforming only the control points P’(t)= M = M 7Affine Transformations • Homogeneous coordinates also work – Means you can translate, rotate, shear, etc. – Note though that you need to normalize P’ by 1/w’ P’(t)= M 1 1 1 1 = M 1 1 1 1 8Questions? 9The Plan for Today • Differential Properties of Curves & Continuity • B-Splines • Surfaces – Tensor Product Splines – Subdivision Surfaces – Procedural Surfaces – Other 10Differential Properties of Curves • Motivation – Compute normal for surfaces – Compute velocity for animation – Analyze smoothness Image courtesy of Kristian Molhave on Wikimedia Commons. License: CC- BY-SA. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 11Velocity • First derivative w.r.t. t • Can you compute this for Bezier curves? P(t) = (1-t)³ P1 + 3t(1-t)² P2 + 3t²(1-t) P3 + t³ P4 • You know how to differentiate polynomials... 12Velocity • First derivative w.r.t. t • Can you compute this for Bezier curves? P(t) = (1-t)³ P1 + 3t(1-t)² P2 + 3t²(1-t) P3 + t³ P4 • P’(t) = -3(1-t)2 P1 Sanity check: t=0; t=1 + 3(1-t) 2 -6t(1-t) P2 + 6t(1-t)-3t 2 P3 + 3t 2 P4 13Linearity? • Differentiation is a linear operation – (f+g)’=f’+g’ – (af)’=a f’ • This means that the derivative of the basis is enough to know the derivative of any spline. • Can be done with matrices – Trivial in monomial basis – But get lower-order polynomials 14Tangent Vector • The tangent to the curve P(t) can be defined as T(t)=P’(t)/P’(t) – normalized velocity, T(t) = 1 • This provides us with one orientation for swept surfaces later Courtesy of Seth Teller. 15Curvature Vector • Derivative of unit tangent – K(t)=T’(t) – Magnitude K(t) is constant for a circle – Zero for a straight line • Always orthogonal to tangent, ie. 16Geometric Interpretation • K is zero for a line, constant for circle – What constant? 1/r • 1/K(t) is the radius of the circle that touches P(t) at t and has the same curvature as the curve 17Curve Normal • Normalized curvature: T’(t)/T’(t) 18Questions? 19Orders of Continuity • C0 = continuous C0 – The seam can be a sharp kink • G1 = geometric continuity – Tangents point to the same direction at the seam G1 • C1 = parametric continuity – Tangents are the same at the seam, implies G1 C1 • C2 = curvature continuity – Tangents and their derivatives are the same 20Orders of Continuity • G1 = geometric continuity – Tangents point to the same direction at the seam – good enough for modeling • C1 = parametric continuity G1 – Tangents are the same at the seam, implies G1 – often necessary for animation C1 21Connecting Cubic Bézier Curves • How can we guarantee C0 continuity? • How can we guarantee G1 continuity? • How can we guarantee C1 continuity? • C2 and above gets difficult 22Connecting Cubic Bézier Curves • Where is this curve – C0 continuous? – G1 continuous? – C1 continuous? • What’s the relationship between: – the of control points, and the of cubic Bézier subcurves? 23Questions? 24Cubic B-Splines • ≥ 4 control points • Locally cubic – Cubics chained together, again. Courtesy of Seth Teller. 25Cubic B-Splines • ≥ 4 control points • Locally cubic – Cubics chained together, again. Courtesy of Seth Teller. 26Cubic B-Splines • ≥ 4 control points • Locally cubic – Cubics chained together, again. Courtesy of Seth Teller. 27Cubic B-Splines • ≥ 4 control points • Locally cubic – Cubics chained together, again. Courtesy of Seth Teller. 28Cubic B-Splines • ≥ 4 control points • Locally cubic – Cubics chained together, again. Courtesy of Seth Teller. • Curve is not constrained to pass through any control points 6.837 – Durand 29Cubic B-Splines: Basis These sum to 1, too B3 B2 A B-Spline curve is also bounded by the convex B1 B4 hull of its control points. 30Cubic B-Splines: Basis B2 B3 B1 B4 31 3 1 Cubic B-Splines: Basis B2 B3 B1 B4 32 3 2 Cubic B-Splines • Local control (windowing) • Automatically C2, and no need to match tangents Courtesy of Seth Teller. Used with permission. 33B-Spline Curve Control Points Default B-Spline B-Spline with B-Spline which passes derivative through discontinuity end points Repeat interior control point Repeat end points 34Bézier ≠ B-Spline Bézier B-Spline But both are cubics, so one can be converted into the other 35Converting between Bézier & BSpline • Simple with the basis matrices – Note that this only works for a single segment of 4 control points • P(t) = G B1 T(t) = G B1 (B2-1B2) T(t)= (G B1 B2-1) B2 T(t) • G B1 B2-1 are the control points for the segment in new basis. 36Converting between Bézier & B-Spline original new control BSpline points as control points to Bézier match Bézier new Bézier control points to original match control B-Spline points as MIT EECS 6.837, Popović B-Spline 37NURBS (Generalized B-Splines) • Rational cubics – Use homogeneous coordinates, just add w • Provides an extra weight parameter to control points • NURBS: Non-Uniform Rational B-Spline – non-uniform = different spacing between the blending functions, a.k.a. “knots” – rational = ratio of cubic polynomials (instead of just cubic) • implemented by adding the homogeneous coordinate w into the control points. 38Questions? 39Representing Surfaces • Triangle meshes – Surface analogue of polylines, this is what GPUs draw • Tensor Product Splines – Surface analogue of spline curves • Subdivision surfaces • Implicit surfaces, e.g. f(x,y,z)=0 • Procedural – e.g. surfaces of revolution, generalized cylinder • From volume data (medical images, etc.) 40Triangle Meshes • What you’ve used so far in Assignment 0 • Triangle represented by 3 vertices • Pro: simple, can be rendered directly • Cons: not smooth, needs many triangles to approximate smooth surfaces (tessellation) This image is in the public domain. Source: Wikimedia Commons. 41Smooth Surfaces? • P(t) = (1-t)³ P1 What’s the + 3t(1-t)² P2 dimensionality of a + 3t²(1-t) P3 curve? 1D + t³ P4 What about a surface? 42How to Build Them? Here’s an Idea • P(u) = (1-u)³ P1 (Note We relabeled + 3u(1-u)² P2 t to u) + 3u²(1-u) P3 + u³ P4 43How to Build Them? Here’s an Idea • P(u) = (1-u)³ P1 (Note We relabeled + 3u(1-u)² P2 t to u) + 3u²(1-u) P3 + u³ P4 44How to Build Them? Here’s an Idea • P(u) = (1-u)³ P1 (Note We relabeled + 3u(1-u)² P2 t to u) + 3u²(1-u) P3 + u³ P4 45How to Build Them? Here’s an Idea • P(u) = (1-u)³ P1 (Note We relabeled + 3u(1-u)² P2 t to u) + 3u²(1-u) P3 + u³ P4 46Here’s an Idea • P(u, v) = (1-u)³ P1(v) + 3u(1-u)² P2(v) + 3u²(1-u) P3(v) v=0 v=1 + u³ P4(v) • Let’s make the Pis move along curves 47Here’s an Idea • P(u, v) = (1-u)³ P1(v) + 3u(1-u)² P2(v) + 3u²(1-u) P3(v) v=0 v=1 + u³ P4(v) • Let’s make the Pis move along curves 48Here’s an Idea • P(u, v) = (1-u)³ P1(v) + 3u(1-u)² P2(v) + 3u²(1-u) P3(v) v=1/3 v=0 v=1 + u³ P4(v) • Let’s make the Pis move along curves 49Here’s an Idea • P(u, v) = (1-u)³ P1(v) + 3u(1-u)² P2(v) + 3u²(1-u) P3(v) v=1/3 v=0 v=1 v=2/3 + u³ P4(v) • Let’s make the Pis move along curves 50Here’s an Idea • P(u, v) = (1-u)³ P1(v) + 3u(1-u)² P2(v) + 3u²(1-u) P3(v) v=1/3 v=0 v=1 v=2/3 + u³ P4(v) • Let’s make the Pis move along curves 51Here’s an Idea • P(u, v) = (1-u)³ P1(v) + 3u(1-u)² P2(v) A 2D surface patch + 3u²(1-u) P3(v) v=1/3 v=0 v=1 v=2/3 + u³ P4(v) • Let’s make the Pis move along curves 52Tensor Product Bézier Patches • In the previous, Pis were just some curves • What if we make them Bézier curves? 53Tensor Product Bézier Patches • In the previous, Pis were just some curves • What if we make them Bézier curves? • Each u=const. and v=const. v=0 v=1 v=2/3 curve is a Bézier curve • Note that the boundary control points (except corners) are NOT interpolated 54Tensor Product Bézier Patches A bicubic Bézier surface 55Tensor Product Bézier Patches The “Control Mesh” 16 control points 56Bicubics, Tensor Product • P(u,v) = B1(u) P1(v) + B2(u) P2(v) + B3(u) P3(v) P4,2 P4,1 P4,4 P4,3 + B4(u) P4(v) P3,2 • Pi(v) = B1(v) Pi,1 P3,1 P3,4 + B2(v) Pi,2 P3,3 + B3(v) Pi,3 P2,3 P2,1 P2,2 P2,4 + B4(v) Pi,4 P1,4 P1,3 P1,1 P1,2 57Bicubics, Tensor Product • P(u,v) = B1(u) P1(v) + B2(u) P2(v) + B3(u) P3(v) + B4(u) P4(v) • Pi(v) = B1(v) Pi,1 + B2(v) Pi,2 + B3(v) Pi,3 + B4(v) Pi,4 58Bicubics, Tensor Product • P(u,v) = B1(u) P1(v) + B2(u) P2(v) + B3(u) P3(v) + B4(u) P4(v) 16 control points Pi,j • Pi(v) = B1(v) Pi,1 16 2D basis functions Bi,j + B2(v) Pi,2 + B3(v) Pi,3 + B4(v) Pi,4 59Recap: Tensor Bézier Patches • Parametric surface P(u,v) is a bicubic polynomial of two variables u & v • Defined by 4x4=16 control points P1,1, P1,2.... P4,4 • Interpolates 4 corners, approximates others • Basis are product of two Bernstein polynomials: B1(u)B1(v); B1(u)B2(v);... B4(u)B4(v) © Addison-Wesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 60Questions? 61Tangents and Normals for Patches • P(u,v) is a 3D point specified by u, v • The partial derivatives and are 3D vectors • Both are tangent to surface at P © Addison-Wesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 62Tangents and Normals for Patches • P(u,v) is a 3D point specified by u, v • The partial derivatives and are 3D vectors • Both are tangent to surface at P • Normal is perpendicular to both, i.e., n is usually not unit, so must normalize © Addison-Wesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 63Questions? 64Recap: Matrix Notation for Curves • Cubic Bézier in matrix notation point on curve (2x1 vector) Canonical “power basis” “Geometry matrix” “Spline matrix” of control points P1..P4 (Bernstein) (2 x 4) 65Hardcore: Matrix Notation for Patches • Not required, but convenient x coordinate of surface at (u,v) Column vector of basis functions (v) Row vector of 4x4 matrix of x coordinates basis functions (u) of the control points 66Hardcore: Matrix Notation for Patches • Curves: • Surfaces: A separate 4x4 geometry matrix for x, y, z • T = power basis B = spline matrix G = geometry matrix 67Super Hardcore: Tensor Notation • You can stack the Gx, Gy, Gz matrices into a geometry tensor of control points – I.e., Gki,j = the kth coordinate of control point Pi,j – A cube of numbers • “Definitely not required, but nice – See http://en.wikipedia.org/wiki/Multilinear_algebra 68Tensor Product B-Spline Patches • Bézier and B-Spline curves are both cubics – Can change between representations using matrices • Consequently, you can build tensor product surface patches out of B-Splines just as well – Still 4x4 control points for each patch – 2D basis functions are pairwise products of B-Spline basis functions – Yes, simple © Addison-Wesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 69Tensor Product Spline Patches • Pros – Smooth – Defined by reasonably small set of points • Cons – Harder to render (usually converted to triangles) – Tricky to ensure continuity at patch boundaries • Extensions – Rational splines: Splines in homogeneous coordinates – NURBS: Non-Uniform Rational B-Splines • Like curves: ratio of polynomials, non-uniform location of control points, etc. 70Utah Teapot: Tensor Bézier Splines • Designed by Martin Newell Image courtesy of Dhatfield on Wikimedia Commons. License: CC-BY-SA. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 6.837 – Durand 71Cool: Displacement Mapping • Not all surfaces are smooth... © Addison-Wesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 72Cool: Displacement Mapping • Not all surfaces are smooth... • “Paint” displacements on a smooth surface – For example, in the direction of normal • Tessellate smooth patch into fine grid, then add displacement D(u,v) to vertices • Heavily used in movies, more and more in games © Addison-Wesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 73Displacement Mapping Example This image is in the public domain. Source: Wikimedia Commons. Smooth base surface Displaced Surface 74Questions? 75Subdivision Surfaces • Start with polygonal mesh • Subdivide into larger number of polygons, smooth result after each subdivision – Lots of ways to do this. • The limit surface is smooth © IEEE. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 6.837 – Durand 76Corner Cutting 77Corner Cutting 78Corner Cutting 79Corner Cutting 80Corner Cutting 81Corner Cutting 82Corner Cutting 83Corner Cutting ∞ 84Corner Cutting 85Corner Cutting It turns out corner cutting (Chaikin’s Algorithm) produces a quadratic B- Spline curve (Magic) 86Corner Cutting (Well, not totally unexpected, remember de Casteljau) 87Subdivision Curves and Surfaces • Idea: cut corners to smooth • Add points and compute weighted average of neighbors • Same for surfaces – Special case for irregular vertices • vertex with more or less than 6 neighbors in a triangle mesh © IEEE. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 88 Warren et al. Subdivision Curves and Surfaces • Advantages – Arbitrary topology – Smooth at boundaries © IEEE. All rights reserved. This content is excluded from our Creative Commons license. For more information, see – Level of detail, scalable http://ocw.mit.edu/help/faq-fair-use/. – Simple representation – Numerical stability, well-behaved meshes – Code simplicity • Little disadvantage: – Procedural definition – Not parametric – Tricky at special vertices 89 Warren et al. Flavors of Subdivision Surfaces • Catmull-Clark – Quads and triangles – Generalizes bicubics to arbitrary topology • Loop, Butterfly Image courtesy of Romainbehar on Wikimedia Commons. License: CC-BY-SA. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. – Triangles • Doo-Sabin, sqrt(3), biquartic... – and a whole host of others • Used everywhere in movie and game modeling • See http://www.cs.nyu.edu/dzorin/sig00course/ 90Subdivision + Displacement Original mesh with Original mesh with Original rough mesh subdivision and subdivision displacement © source unknown. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 91Questions? 92Specialized Procedural Definitions • Surfaces of revolution – Rotate given 2D profile curve • Generalized cylinders – Given 2D profile and 3D curve, sweep the profile along the 3D curve • Assignment 1 93Surface of Revolution • 2D curve q(u) provides one dimension – Note: works also with 3D curve • Rotation R(v) provides 2nd dimension v s(u,v)=R(v)q(u) where R is a matrix, s(u,v) q a vector, and s is a point on the surface 94General Swept Surfaces c • Trace out surface by moving a q profile curve along a trajectory. – profile curve q(u) provides one dim s – trajectory c(u) provides the other • Surface of revolution can be seen as a special case where trajectory is a circle s(u,v)=M(c(v))q(u) where M is a matrix that depends on the trajectory c 95General Swept Surfaces c • How do we get M? q – Translation is easy, given by c(v) – What about orientation? s • Orientation options: – Align profile curve with an axis. – Better: Align profile curve with frame that “follows” the curve s(u,v)=M(c(v))q(u) where M is a matrix that depends on the trajectory c 96Frames on Curves: Frenet Frame • Frame defined by 1st (tangent), 2nd and 3rd derivatives of a 3D curve • Looks like a good idea for swept surfaces... Image courtesy of Kristian Molhave on Wikimedia Commons. License: CC- BY-SA. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 97Frenet: Problem at Inflection • Normal flips • Bad to define a smooth swept surface An inflection is a point where curvature changes sign 98Smooth Frames on Curves • Build triplet of vectors – include tangent (it is reliable) – orthonormal – coherent over the curve • Idea: – use cross product to create orthogonal vectors – exploit discretization of curve – use previous frame to bootstrap orientation – See Assignment 1 instructions 99Normals for Swept Surfaces c • Need partial derivatives w.r.t. q both u and v s s s – Remember to normalize • One given by tangent of profile curve, the other by tangent of trajectory s(u,v)=M(c(v))q(u) where M is a matrix that depends on the trajectory c 100Questions? 101Implicit Surfaces • Surface defined implicitly by a function This image is in the public domain. Source: Wikimedia Commons. 102Implicit Surfaces • Pros: – Efficient check whether point is inside – Efficient Boolean operations – Can handle weird topology for animation – Easy to do sketchy modeling • Cons: – Does not allow us to easily generate a point on the surface Image courtesy of Anders Sandberg on Wikimedia Commons. License: CC-BY- SA. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 103Questions? 104Point Set Surfaces • Given only a noisy 3D point cloud (no connectivity), can you define a reasonable surface using only the points? – Laser range scans only give you points, so this is potentially useful © IEEE. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. From Point Set Surfaces, (Alexa et al. 2001). 105From Point Set Surfaces, used with permission from ACM, Inc Point Set Surfaces Alexa et al. 2001 © IEEE. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/ . 106Ohtake et al. 2003 Point Set Surfaces • Modern take on implicit surfaces • Cool math: Moving Least Squares (MLS), partitions of unity, etc. From Multi-Level Partition of Unity Implicits © ACM, Inc. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. • Not required in this class, but nice to know. 107Questions? 108That’s All for Today • Further reading – Buss, Chapters 7 & 8 • Subvision curves and surfaces – http://www.cs.nyu.edu/dzorin/sig00course/ 6.837 – Durand 109 0 9 MIT OpenCourseWare http://ocw.mit.edu 6.837 Computer Graphics Fall 2012 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.
Website URL
Comment