Computer Graphics Computer Graphics Lecture 13 Curves and Surfaces I Computer Graphics Types of Curves / Surfaces Explicit: y = mx + b z = A x + By + C Implicit: Ax + By + C = 0 (x x0)2 + (y y0)2 r2 = 0

Parametric: x = x0 + (x1 x0)t x = x0 + rcos y = y0 + (y1 y0)t y = y0 + rsin 10/10/2008 Lecture 5 2 Computer Graphics Today Implicit Surfaces

Metaball Parametric surfaces Hermite curve Bezier curve Biubic patches Tessalation 10/10/2008 Lecture 5 3 Computer Graphics Implicit Surfaces Functions in the form of F(x,y,z) = 0 i.e. Quadric functions Sphere: f(x,y,z) = x2+ y2+ z 2 = 0

3/10/2008 Lecture 3 4 Computer Graphics Metaballs One type of implicit surface Also known as blobby objects Negative volume to produce hollows Can be used to model smooth surfaces, liquid

Computer Graphics Metaballs (2) A point surrounded by a density field The density decreases with distance from the point The density of multiple particles is summed A surface is implied by sampling the area where the density is a predefined threshold Computer Graphics An Example of the density function

1 f ( x, y , z ) 2 2 2 ( x x0 ) ( y y0 ) ( z z0 ) where (x0,y0,z0) is the centre of the metaball Computer Graphics Metaballs (3) The surface points are sampled and approximated by polygonal meshes for rendering Demo animation of metaballs

http://www.youtube.com/watch?v=UWvGyK olkho&feature=related http://www.youtube.com/watch?v=Nf_OlfW MRaA&NR=1 Computer Graphics Today Implicit Surfaces Metaball Parametric surfaces Hermite curve Bezier curve Biubic patches Tessalation 10/10/2008 Lecture 5

9 Computer Graphics Why parametric? Parametric curves are very flexible. Parameter count gives the objects dimension. (x(u,v), y(u,v), z(u,v)) : 2D surface Coord functions independent. 10/10/2008 Lecture 5 10 Computer Graphics

Specifying curves Control Points: A set of points that influence the curves shape. Interpolating curve: Curve passes through the control points. Control polygon: Control points merely influence shape. 10/10/2008 Lecture 5 11

Computer Graphics Piecewise curve segments We can represent an arbitrary length curve as a series of curves pieced together. But we will want to control how these curves fit together 10/10/2008 Lecture 5 12 Computer Graphics Continuity between curve segments If the tangent vectors of two cubic curve segments are equal at the join point, the curve has first-degree continuity, and is said to be C1 continuous

If the direction and magnitude of d n/ dt n[Q(t)] through the nth derivative are equal at the join point, the curve is called Cn continuous If the directions (but not necessarily the magnitudes) of two segments tangent vectors are equal at the join point, the curve has G1 continuity Computer Graphics Example The curves Q1 Q2 Q3 join at point P Q1 and Q2 have equal tangent vectors at P and hence C1 and G1 continuous Q1 and Q3 have tangent vectors in the same direction but Q3 has twice magnitude, so they are only G1 continuous at P Computer Graphics Parametric Cubic Curves

In order to assure C2 continuity our functions must be of at least degree 3. Cubic has 4 degrees of freedom and can control 4 things. Use polynomials: x(t) of degree n is a function of t. n x (t ) ai t n i 0 y(t) and z(t) are similar and each is handled independently 10/10/2008 Lecture 5 15 Computer Graphics

Hermite curves A cubic polynomial Polynomial can be specified by the position of, and gradient at, each endpoint of curve. Determine: x = X(t) in terms of x 0, x0, x1, x1 Now: X(t) = a3t3 + a2t2 + a1t + a0 /(t) = 3a t2 + 2a t + a and X 3 5 2 1 10/10/2008 Lecture 16

Computer Graphics Finding Hermite coefficients Substituting for t at each endpoint: x0 = X(0) = a0 x0= X/(0) = a1 x1 = X(1) = a3 + a2 + a1 + a0 x1= X/(1) = 3a3 + 2a2+ a1 And the solution is: a 0 = x0 a2 = -3x0 2x0+ 3x1 x1 10/10/2008 a1 = x0 a3 = 2x0 + x0 - 2x1 + x1

Lecture 5 17 Computer Graphics The Hermite matrix: MH The resultant polynomial can be expressed in matrix form: X(t) = tTMHq X (t ) t 3 t 2 ( q is the control vector) 2 1 2 1 x0 3 2 3 1 x ' 0

t 1 0 1 0 0 x1 0 0 0 x1 ' 1 We can now define a parametric polynomial for each coordinate required independently, ie. X(t), Y(t) and Z(t) 10/10/2008 Lecture 5 18

Computer Graphics Hermite Basis (Blending) Functions 1 2 1 x0 2 3 2 3 1 x ' 0 3 2 X (t ) t t t 1 0 1 0 0 x1

0 0 0 x1 ' 1 (2t 3 3t 2 1)x0 (t 3 2t 2 t )x0 '( 2t 3 3t 2 )x1 (t 3 t 2 )x1 ' Computer Graphics Hermite Basis (Blending) Functions X (t ) (2t 3 3t 2 1)x0 (t 3 2t 2 t )x0 '( 2t 3 3t 2 )x1 (t 3 t 2 )x1 ' The graph shows the shape of the four basis functions often called blending functions.

x0 x1 They are labelled with the elements of the control vector that they weight. Note that at each end only position is non-zero, so the curve must touch the endpoints 10/10/2008 x0' Lecture 5 x1/ 20

Computer Graphics Family of Hermite curves. y(t) Note : Start points on left. x(t) 10/10/2008 Lecture 5 21 Computer Graphics Displaying Hermite curves. Simple :

Select step size to suit. Plug x values into the geometry matrix. Evaluate P(t) x value for current position. Repeat for y & z independently. Draw line segment between current and previous point. Joining curves: Coincident endpoints for C0 continuity Align tangent vectors for C1 continuity 10/10/2008 Lecture 5 .

22 Computer Graphics Bzier Curves Hermite cubic curves are difficult to model need to specify point and gradient. More intuitive to only specify points. Pierre Bzier (an engineer at Renault) specified 2 endpoints and 2 additional control points to specify the gradient at the endpoints. Can be derived from Hermite matrix: Two end control points specify tangent 10/10/2008 Lecture 5

23 Computer Graphics Bzier Curves P2 Note the Convex Hull has been shown as a dashed line used as a bounding extent for intersection purposes. P4 P1 P3 P1

P3 P4 P2 10/10/2008 Lecture 5 24 Computer Graphics Bzier Matrix The cubic form is the most popular X(t) = tTMBq (MB is the Bzier matrix) With n=4 and r=0,1,2,3 1 3 3 1we

q get: X (t ) t 3 t 2 3 6 t 1 3 3 0 1 10/10/2008 Similarly for Y(t) and Z(t) Lecture 5

0 3 0 0 0 q1 0 q2 0 q3 25 Computer Graphics Bzier blending functions This is how they look The functions sum to 1 at

any point along the curve. q0 Endpoints have full weight q3 q1 q2 The weights of each function is clear and the labels show the control points being weighted. 10/10/2008 Lecture 5

26 Computer Graphics Joining Bezier Curves G 1 continuity is provided at the endpoint when P2 P3 = k (Q1 Q0) if k=1, C1 continuity is obtained Computer Graphics Bicubic patches The concept of parametric curves can be extended to surfaces The cubic parametric curve is in the form of Q(t)=tTM q where q=(q1,q2,q3,q4) : qi control points, M is the basis matrix (Hermite or Bezier, ), tT=(t3, t2, t, 1)

Computer Graphics Now we assume qi to vary along a parameter s, Qi(s,t)=tTM [q1(s),q2(s),q3(s),q4(s)] qi(s) are themselves cubic curves, we can write them in the form Computer Graphics Bicubic patches Q( s, t ) t T . M .( s T . M .[q11 , q12 , q13 , q14 ],..., s T . M .[q 41 , q 42 , q 43 , q 44 ]) t T . M .q. M T .s q11 q 12 q13

q14 q21 q22 q23 q24 q31 q32 q33 q34 q41 q42 q43 q44 where q is a 4x4 matrix

Each column contains the control points of q1(s),,q4(s) x,y,z computed by x( s, t ) t T . M .q x . M T .s y ( s, t ) t T . M .q y . M T .s z ( s, t ) t T . M .q z . M T .s Computer Graphics Bzier example We compute (x,y,z) by x( s, t ) t T . M B .q x . M BT . s q x is 4 4 array of x coords y ( s, t ) t T . M B .q y . M BT . s q y is 4 4 array of y coords z ( s, t ) t T . M B .q z . M BT . s q z is 4 4 array of z coords 14/10/2008 Lecture 6

31 Computer Graphics Continuity of Bicubic patches. Hermite and Bzier patches C0 continuity by sharing 4 control points between patches. C1 continuity when both sets of control points either side of the edge are collinear with the edge. 14/10/2008 Lecture 6 32

Computer Graphics Displaying Bicubic patches. Need to compute the normals vector cross product of the 2 tangent vectors. Need to convert the bicubic patches into a polygon mesh tessellation 14/10/2008 Lecture 6 33 Computer Graphics

Normal Vectors Q( s, t ) (t T . M .q. M T . s ) t T . M .q. M T . ( s ) s s s t T . M .q x . M T .[3s 2 ,2 s,1,0]T Q ( s, t ) (t T . M .q. M T . s ) (t T ). M .q. M T . s t t t [3t 2 ,2t ,1,0]T . M .q. M T .s

Q( s, t ) Q( s, t ) ( y s zt yt z s , z s xt zt xs , xs yt xt y s ) s t The surface normal is biquintic (two variables, fifthdegree) polynomial and very expensive Can use finite difference to reduce the computation Computer Graphics Tessellation We need to compute the triangles on the surface The simplest way is do uniform tessellation, which samples points uniformly in the parameter space Adaptive tessellation adapt the size of triangles to the shape of the surface i.e., more triangles where the surface bends more On the other hand, for flat areas we do not need many triangles 14/10/2008

Lecture 6 35 Computer Graphics Adaptive Tessellation For every triangle edges, check if each edge is tessellated enough (curveTessEnough()) If all edges are tessellated enough, check if the whole triangle is tessellated enough as a whole (triTessEnough()) If one or more of the edges or the triangles interior is not tessellated enough, then further tessellation is needed Computer Graphics

Adaptive Tessellation When an edge is not tessellated enough, a point is created halfway between the edge points uv-values New triangles are created and the tessellator is once again called with the new triangles as input Four cases of further tessellation Adaptive Tessellation Computer Graphics AdaptiveTessellate(p,q,r) tessPQ=not curveTessEnough(p,q) tessQR=not curveTessEnough(q,r) tessRP=not curveTessEnough(r,p) If (tessPQ and tessQR and tessRP)

AdaptiveTessellate(p,(p+q)/2,(p+r)/2); AdaptiveTessellate(q,(q+r)/2,(q+p)/2); AdaptiveTessellate(r,(r+p)/2,(r+q)/2); AdaptiveTessellate((p+q)/2,(q+r)/2,(r+p)/2); else if (tessPQ and tessQR) AdaptiveTessellate(p,(p+q)/2,r); AdaptiveTessellate((p+q)/2,(q+r)/2,r); AdaptiveTessellate((p+q)/2,q,(q+r)/2); else if (tessPQ)

AdaptiveTessellate(p,(p+q)/2,r); AdaptiveTessellate(q,r,(p+q)/2); Else if (not triTessEnough(p,q,r)) AdaptiveTessellate((p+q+r)/3,p,q); AdaptiveTessellate((p+q+r)/3,q,r); AdaptiveTessellate((p+q+r)/3,r,p); end; Computer Graphics curveTessEnough Say you are to judge whether ab needs tessellation You can compute the midpoint c, and compute its distance l from ab

Check if l/||a-b|| is under a threshold Can do something similar for triTessEnough Sample at the mass center and calculate its distance from the triangle c a d b Computer Graphics Other factors to evaluate

Inside the view frustum Front facing Occupying a large area in screen space Close to the sillhouette of the object Illuminated by a significant amount of specular lighting Computer Graphics Demo http://www.nbb.cornell.edu/neurobio/land/ OldStudentProjects/cs490-96to97/anson/ BezierPatchApplet/ Computer Graphics Reading for this lecture Foley et al. Chapter 11, section 11.2 up to and including

11.2.3 Introductory text Chapter 9, section 9.2 up to and including section 9.2.4 Foley at al., Chapter 11, sections 11.2.3, 11.2.4, 11.2.9, 11.2.10, 11.3 and 11.5. Introductory text, Chapter 9, sections 9.2.4, 9.2.5, 9.2.7, 9.2.8 and 9.3. Real-time Rendering 2nd Edition Chapter 12.1-3 10/10/2008 Lecture 5 42