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) = (1t)³ P1 + 3t(1t)² P2 + 3t²(1t) P3 + t³ P4 2Bernstein Polynomials • For Bézier curves, the basis polynomials/vectors are Bernstein polynomials • For cubic Bezier curve: B1(t)=(1t)³ B2(t)=3t(1t)² B3(t)=3t²(1t) 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 • BSplines • 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 BYSA. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faqfairuse/. 11Velocity • First derivative w.r.t. t • Can you compute this for Bezier curves P(t) = (1t)³ P1 + 3t(1t)² P2 + 3t²(1t) 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) = (1t)³ P1 + 3t(1t)² P2 + 3t²(1t) P3 + t³ P4 • P’(t) = 3(1t)2 P1 Sanity check: t=0; t=1 + 3(1t) 2 6t(1t) P2 + 6t(1t)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 lowerorder 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 BSplines • ≥ 4 control points • Locally cubic – Cubics chained together, again. Courtesy of Seth Teller. 25Cubic BSplines • ≥ 4 control points • Locally cubic – Cubics chained together, again. Courtesy of Seth Teller. 26Cubic BSplines • ≥ 4 control points • Locally cubic – Cubics chained together, again. Courtesy of Seth Teller. 27Cubic BSplines • ≥ 4 control points • Locally cubic – Cubics chained together, again. Courtesy of Seth Teller. 28Cubic BSplines • ≥ 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 BSplines: Basis These sum to 1, too B3 B2 A BSpline curve is also bounded by the convex B1 B4 hull of its control points. 30Cubic BSplines: Basis B2 B3 B1 B4 31 3 1 Cubic BSplines: Basis B2 B3 B1 B4 32 3 2 Cubic BSplines • Local control (windowing) • Automatically C2, and no need to match tangents Courtesy of Seth Teller. Used with permission. 33BSpline Curve Control Points Default BSpline BSpline with BSpline which passes derivative through discontinuity end points Repeat interior control point Repeat end points 34Bézier ≠ BSpline Bézier BSpline 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 (B21B2) T(t)= (G B1 B21) B2 T(t) • G B1 B21 are the control points for the segment in new basis. 36Converting between Bézier BSpline original new control BSpline points as control points to Bézier match Bézier new Bézier control points to original match control BSpline points as MIT EECS 6.837, Popović BSpline 37NURBS (Generalized BSplines) • Rational cubics – Use homogeneous coordinates, just add w • Provides an extra weight parameter to control points • NURBS: NonUniform Rational BSpline – nonuniform = 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) = (1t)³ P1 What’s the + 3t(1t)² P2 dimensionality of a + 3t²(1t) P3 curve 1D + t³ P4 What about a surface 42How to Build Them Here’s an Idea • P(u) = (1u)³ P1 (Note We relabeled + 3u(1u)² P2 t to u) + 3u²(1u) P3 + u³ P4 43How to Build Them Here’s an Idea • P(u) = (1u)³ P1 (Note We relabeled + 3u(1u)² P2 t to u) + 3u²(1u) P3 + u³ P4 44How to Build Them Here’s an Idea • P(u) = (1u)³ P1 (Note We relabeled + 3u(1u)² P2 t to u) + 3u²(1u) P3 + u³ P4 45How to Build Them Here’s an Idea • P(u) = (1u)³ P1 (Note We relabeled + 3u(1u)² P2 t to u) + 3u²(1u) P3 + u³ P4 46Here’s an Idea • P(u, v) = (1u)³ P1(v) + 3u(1u)² P2(v) + 3u²(1u) P3(v) v=0 v=1 + u³ P4(v) • Let’s make the Pis move along curves 47Here’s an Idea • P(u, v) = (1u)³ P1(v) + 3u(1u)² P2(v) + 3u²(1u) P3(v) v=0 v=1 + u³ P4(v) • Let’s make the Pis move along curves 48Here’s an Idea • P(u, v) = (1u)³ P1(v) + 3u(1u)² P2(v) + 3u²(1u) 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) = (1u)³ P1(v) + 3u(1u)² P2(v) + 3u²(1u) 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) = (1u)³ P1(v) + 3u(1u)² P2(v) + 3u²(1u) 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) = (1u)³ P1(v) + 3u(1u)² P2(v) A 2D surface patch + 3u²(1u) 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) © AddisonWesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faqfairuse/. 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 © AddisonWesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faqfairuse/. 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 © AddisonWesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faqfairuse/. 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/Multilinearalgebra 68Tensor Product BSpline Patches • Bézier and BSpline curves are both cubics – Can change between representations using matrices • Consequently, you can build tensor product surface patches out of BSplines just as well – Still 4x4 control points for each patch – 2D basis functions are pairwise products of BSpline basis functions – Yes, simple © AddisonWesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faqfairuse/. 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: NonUniform Rational BSplines • Like curves: ratio of polynomials, nonuniform location of control points, etc. 70Utah Teapot: Tensor Bézier Splines • Designed by Martin Newell Image courtesy of Dhatfield on Wikimedia Commons. License: CCBYSA. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faqfairuse/. 6.837 – Durand 71Cool: Displacement Mapping • Not all surfaces are smooth... © AddisonWesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faqfairuse/. 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 © AddisonWesley. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faqfairuse/. 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/faqfairuse/. 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/faqfairuse/. 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/faqfairuse/. – Simple representation – Numerical stability, wellbehaved meshes – Code simplicity • Little disadvantage: – Procedural definition – Not parametric – Tricky at special vertices 89 Warren et al. Flavors of Subdivision Surfaces • CatmullClark – Quads and triangles – Generalizes bicubics to arbitrary topology • Loop, Butterfly Image courtesy of Romainbehar on Wikimedia Commons. License: CCBYSA. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faqfairuse/. – Triangles • DooSabin, 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/faqfairuse/. 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 BYSA. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faqfairuse/. 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: CCBY SA. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faqfairuse/. 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/faqfairuse/. 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/faqfairuse/ . 106Ohtake et al. 2003 Point Set Surfaces • Modern take on implicit surfaces • Cool math: Moving Least Squares (MLS), partitions of unity, etc. From MultiLevel 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/faqfairuse/. • 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.