ࡱ> `!8P N/7  ȽXJtxcdd``a!0 ĜL  312Ec21BUs30)0)0Qcgb  P#7T obIFHeA*CT f0 PeCK Jyw Ib*!!ȽXJ#xcb&EFEA< 10p2C0\hIza9C_iyuU( ww`!6mTk1@`h $0xڝ1K1_;޵ڪPE*..B]ES+xVhfsq/: 78~~g."xB# j\/^x@ F(8 -JH`ylgJ]h-D ,ΏܺG 4 jh`IA`5[ضݎ>QO! h_kΠg<rU]yb",[ޯ:]ҙFE|:\M!%?9~oxy]7xT7 ߛ{?ug]'V,_bq%2)C7F30- 1/8@|<;|~F0r 0dw-` 5 !d.`<ɇ_UnTgP/bG?U ~;&T6ypa$1^!Di=-A8,1Ty5aT>ZTjnT&6T]|7 [`Bܤr2NĦ{I m=DA|]8?KUޖU~?'|+3o[ͭ\ q/ `pĤ\Y\ t08eH ;h(   (#AEquation Equation.30,Microsoft Equation 3.00$C,Microsoft Equation 3.0 Equation.30,Microsoft Equation 3.00%DEquation Equation.30,Microsoft Equation 3.00&EEquation Equation.30,Microsoft Equation 3.0/ 0DTimes New Roman50Wo 0DArialNew Roman50Wo 0" DWingdingsRoman50Wo 0c(.2  @n?" dd@  @@`` ::H!                   $ ,                         , 3'        )  ,h/                   +   O              Y L$$$$$$$$$$$$$$$$$$$$$$2$K Jyw Ib$$$$$r$9C_iyuUi$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$2$6mTk1n2$aFCjtD2$'qP$YkZc $0e0e     A@ AjJ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||@d g4AdAd04ppp@ <4BdBd 0L6g4VdVd0zpu pp<4!d!d 0L6~kʚ;a3ʚ;<4ddddЁ 0r0___PPT10 2___PPT9/ 0?D$ 0Essential Math for GamesO =%Curves<  &Jim Van Verth (jim@essentialmath.com) 'F           t AnimationProblem: want to replay stored set of transformations Generated by artist Generated by motion capture Two main issues Replaying position Replaying orientationL60)60)uAnimation of PositionSet of points representing position Three issues to handle Frame rate higher than sample rate Reduce number of samples to save memory Blend between two animation sets&;l;lvAnimation of PositionIdea: use set of points to define a function Can then sample points along that function to find new positions Two possibilities: Interpolation (passes through points) Approximation (passes near points)&IIwParametric CurveFunction Q(t) Maps parameter t to point on curve Q Commonly broken into ( x(t), y(t), z(t) ) Called space curve Derivative is tangent ( x'(t), y'(t), z'(t) )  xLinear Interpolation>Two points define a line Can generate new points between themyLinear Interpolation\Do this using parameterization of line Q(t) = P0 + t (P1  P0) = (1  t) P0 + t P1 Parameter t controls position on line Curve only defined where t in [0,1])<J)      3)<  JzMultiple Points~Can linearly interpolate from point to point (piecewise linear curve) Problem: get discontinuity at each point I.e. not smooth$.;{ ContinuityContinuous function has no  gaps C-continuity Number indicates derivative continuity I.e. C1 means 1st derivative continuous Tangents equal at joins G-continuity Tangents point in same direction~/g !/, / !|Hermite Curves}One solution Idea: Cubic curve between each point Tangents at each point specify how curve should go Piecewise Hermite spline}Hermite Curves2For points P0,P1 and tangents P'0,P'1 function is:3   ! ! ~Hermite CurvesxAt each sample, two tangents  in and out For smooth curve (C1) Make them equal Smooth curve but change in speed (G1) Same direction, different lengths For crease (C0) Different directions@ZZ&Z"ZZZ< " "   Computing TangentsExport from commercial tools May have to tweak to guarantee results Export from homemade tools Clamped, natural, cyclic, acyclic splines Maintain C2 continuity Solution to system of linear equationsp'E>'E  3y>Computing TangentsdCatmull-Rom spline Tangent half vector between neighboring points Tangent undefined at end points&RR^ Bezier CurveTInstead of two tangents, have two approximating control points Curve doesn t pass through control points Their position controls shape of curve Curve lies in convex hull&@k@k Bezier Curve'For points P0, P1, P2, P3 function is: (      Bezier CurveeControl points provide good user interface Align control points between curve segments for continuityDe Castlejau's method Fast Bezier subdivision Find percentage along each segment, then along resulting segments Result is control pts for two subcurves,m *De Castlejau s Method Useful for rendering Subdivide until only  straight subcurves Straight if P1 & P2 are close to P0P3 Useful for measuring length Subdivide until ||P0P1|| + ||P1P2|| + ||P2P3|| is close to ||P0P3|| Add up all the sublengthsP^6             ,5   B-splinesGenerally curve approximates points, i.e. doesn t pass through them Continuous through 2nd derivative Provides local controlNURBSNon-Uniform Rational B-Splines Non-uniform = curve segments have unequal spacing by parameter Rational = can apply weights to sample points (good for conic sections) Result: very useful, but not cheap Mostly used for parametric surfaces Yg References   zParent, Rick, Computer Animation: Algorithms and Techniques, Morgan Kaufmann, 2002. Bartels, Beatty, Barsky, An Introduction to Splines for use in Computer Graphics & Geometric Modelling, Morgan Kaufmann, 1987. Rogers and Adams, Mathematical Elements for Computer Graphics, McGraw-Hill, 1989. Rogers, An Introduction to NURBS: With Historical Perspective, Morgan Kaufmann, 2000.l{-2M++5D)      ` f33` 3f3` ___>?" dd@,?" dd@  " @ `"  n?" dd@   @@``@n?" dd@  @@``PR    @ ` ` p>>D$ 0Essential Math for Games r(    Nvgֳgֳ ?P  X Click to edit Master title style!!  2  Hygֳgֳ ?  RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S    Z}1 ?``  b* 2    Z1 ?`   X*(2    Z䇺1 ?`   Z*(2  N  6޽h? ? 33  Lecture Template 0 @( ~@K@   Bdj 1?P%   X* 2     Bn 1? %  Z*(2   p  0 ?*P  ,  Bl 1? @2  RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S    Hv 1?P   X* 2     Hz 1?   Z*(2   H  0h0 ? ̙3380___PPT10.QA9 XPP( \@d@   B` 1?P%   X* 2     B 1? %  Z*(2     H( 1?P   X* 2     H4 1?   Z*(2   H  0h0 ? ̙3380___PPT10.Qp {Gf 0 f(   ~  s *T>    Tgֳgֳ ?) )  H  0޽h ? 3380___PPT10.#\z  ` 0(   x  c $P   x  c $L  H  0޽h ? 33  p 0(   x  c $P   x  c $P  H  0޽h ? 33   0(   x  c $ԨP   x  c $  H  0޽h ? 33   0(   x  c $P   x  c $`  H  0޽h ? 33    (   pB  HD8c? 0 x  c $,P   x  c $趗  v2  N1??2  v2  N1?? > 2   A,1??Light upward diagonal @ ,$D 02   A,1??Light upward diagonal n^ ,$D 0H  0޽h ? 33___PPT10+q6D~' = @B D9' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* |%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* |%(+P    (   x  c $lŗ  x  c $(ƗP   B  ZD8c?  B   `D8c? 2  Tdɗ1??G Z F(2  2  T̗1??P P  F(2    Hϗ 1?2M I   PP02 2    Hԗ 1? ~ RP14 2  H  0޽h ? 33  `X  (   pB  HD8c?  pB  HD8c?  P pB  HD8c?p PP x  c $ۗP   x  c $ܗ  v2  N1?? N~ 2  N1??p n. ,$D 02   N1??  ,$D 02   N1?? N ,$D 0   T jJ?Vz 8Demo 2H  0޽h ? 33___PPT10+ID' = @B Du' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(+   0(   x  c $P   x  c $  H  0޽h ? 33   z   (   vB  NDjJ?. P@~ vB  NDjJ?. ^vB  NDjJ?>  vB  NDjJ?     b0e0e    B` CDE(F @  8c 8c8c     ?A)BCD|E|| PX `h ` ` ` @   ~ Pnx  c ${P   x  c $pn  v2  N1?? N2  N1??~ n< ,$D 02  N1??  ,$D 02  N1?? N ,$D 0  TD jJ?Vz 8Demo 2H  0޽h ? 33___PPT10+ID' = @B Du' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(+    $  (  $  $ c j0e0e    BChDE(F @  jJ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| lDH8XhHh @     vB $ NDjJ? p vB $ NDjJ? x $ c $DP  D x $ c $D D v2 $ N1?? N~ 2 $ N1?? 0 ^ ,$D 0`  $  c $A ??, c  r  $  6A  ??( r  $  6A  ??    $ HD 1? n  RP04 2    $ HD 1?E ,  RP14 2   $ H@ D 1?d E iK  QP'12 2"  $ H$D 1? &J  QP'02 2" H $ 0޽h ? 33~___PPT10^+HfDB' = @B D' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(+  ( 0(  ( x ( c $P1DP  D x ( c $ 2D D H ( 0޽h ? 33  , 0(  , x , c $d8D D x , c $ 9DP  D H , 0޽h ? 33N    0 (  0 x 0 c $LD D x 0 c $tMDP  D v2 0 N1??J b 2 0 N1?? ,$D 02 0 N1??z b8 ,$D 0 0 H?D 1? |  VPi-16 2   0 HBD 1?   TPi6 2    0 H1 1? '  VPi+16 2  vB  0 ND8c? Z vB  0 ND8c?a f H 0 0޽h ? 33$   F > 0 4 (  4 x 4 c $pcDP  D x 4 c $,dD D v2 4 N1?? p  4 c j0e0e    BPC`DE(F @  jJ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| `t(PP` @   ~ p2 4 N1??r0,$D 0v2 4 N1??"v2 4 N1?? 0 pB  4 HDjJ? %pB  4 HDjJ? } E pB  4 HDjJ?' pB  4 HDjJ?wy}H 4 0޽h ? 33~___PPT10^+ DB' = @B D' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(+    @8  (  8 pB 8 HDjJ?i H x 8 c $>DP  D x 8 c $* D r 8  6A  ??  8 Hh/ 1?y -)`  RP04 2  pB 8 HDjJ?Y   8 s p0e0e    B`CDE(F @  jJ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| x, Xh(0Pp( `x @    p 2  8 N1?? I ,$D 0v2  8 N1?? %e pB  8 HDjJ?2 nOv2  8 N1??/ pB  8 HDjJ?_ 4m v2 8 N1??{ 8 H qD 1?P'#7 RP14 2   8 H8vD 1?b I  RP24 2   8 HzD 1?} d  RP34 2  H 8 0޽h ? 33~___PPT10^+-|DB' = @B D' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$%(+    P <  (  <  < c j0e0e    B`CDE(F @  jJ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| x, Xh(0Pp( `x @    `  < c j0e0e    BCDE(F @  jJ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| 8pP(p(xP @   x @ |B < TD3|? ` Lx < c $DP  D x < c $LD D v2 < N1?? ^p 2 < N1??0 ^ ,$D 0v2  < N1??0  v2  < N1?? 8 v2  < N1??0 v2  < N1??4 p v2  < N1?? L XH < 0޽h ? 33~___PPT10^+|3DB' = @B D' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*(%(+  x`@ (  @  @  0e0e    B[ CDE(F @  jJ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| r"][  @    Ex @ c $DP  D x @ c $ԔD D v2 @ N1??! " 2 @ N1?? {,$D 0v2 @ N1?? " pB @ HDjJ? : pB  @ HDjJ?  Z pB  @ HDjJ?2  pB  @ HDjJ?:  pB  @ HDjJ?*  pB  @ HDjJ?  2 @ N1?? 7,$D 0v2 @ N1?? y v2 @ N1?? l= 2 @ N1?? N S ,$D 0v2 @ N1?? P  v2 @ N1??N T  @ HD 1?  RP04 2   @ HĠD 1?k ;7R  RP14 2   @ H0D 1?] -)D  RP24 2   @ HD 1? n RP34 2  H @ 0޽h ? 33H  p D (  D x D c $xDP  D x D c $4D D pB D HDjJ?wpB D HDjJ? U  pB  D HDjJ? pB  D HDjJ? 7 pB  D HDjJ? i H D 0޽h ? 33  NF H (  H x H c $DP  D x H c $D D v2 H N1?? ^ v2 H N1??@v2 H N1?? N v2 H N1?? ~ v2 H N1??0 0 v2  H N1?? N   H c 0e0e    BChDE@F  @  jJ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||@D(@Xphp`X PP( @       H H 0޽h ? 33  L 0(  L x L c $DP  D x L c $dD D H L 0޽h ? 33   0(  x  c $8P   x  c $ȘP0  H  0޽h ? 33 xUNAvAD4F X 6?Qk41?&t'ҿB}[ݛ 36*evngӋ+:0,;&X4dݲm5=*|]`ez0E~khuE_U?RۯEqpus-BJnOY> 80 7FS9UT1W;<}H?9p~u7[|oGW?oC+{)!ɽrqVwf7咙I 1]%eUSW<7KMR\?2=]ZU"$m-)1-RwLҔPLEKitFBZc8\Bnc5w*cB'?,᩵(gQEyE%XaWW6ݛO~O2'4~3'?LixWMLSAx-Ж¡` R=` @<)R~nF"H<`BCg514֙}/okCZcT~;ggo^o4<:dss1\.gONXl>C^5cN8 `GR=V=r]y /Ag)a%t )Z~\h@X$?\?+_Ԩ`|=ʛ{SjʰcZc?JlUتA\Z&>5-UO[pN&h|-2JN/`-gs)k/S $-VRt:ZtEE) L8slg,=궨c!\&Wb 'TTL;&J6p[*#iHuF5w|5PşUCsp!LOZxM]&[Q_'{3m]kr!=:U:|BIy߭D3Ru$n^/~dXo?3L٫r]Yyq3'nϘc_'otO:߫*!QÅ3yXÉAy&N*uh.?gL;LP=(gb1['t}{n`wGQԫ,WHQD{P`T?MOixWOSAW }-V$!^ F ¡ŔXC[EăՋ1@ F GOC:^mVJ4켝ݾyYh{%t 4(]j\BX4}S S:5.cd A9ȗ0fM9}*;p6l18S.4$ji%8Sw`?`현5~:ɧjs#,ůzjU;jO;丠Z5b ֈ&WbpPq('ZާmycT>׾w,JdB`$1 EMWZɫslf*璙t 48jDz/ Z-S.]h"SB 'ϔLՀP>a&kb2ōb1ZSXM9UeQgJl1,.+d<0]!:wƱVPdM_qم3a3NO]:.} fUBٙ7y&>&e9]c]j*0gָJi3j qi|oƧM[mz;L2ͧ&3Ӱ05>QF5{Lsqf?r^WU:m^q{8gs!J^P?sC StB%Y0m0|]{0!_c_hx}J+!LH._~;}'J0p@nMeV,RŜ)Z/%o`!/$(tWYWnJDݪFJU;UxWMLSAW~ci BA HM?x0b5&x4Ơc4x37z 1{-_FIfx;;3;;]pRg(`@r[S,(/ fwa6}G.Wkorxn[i@z!߳-> 6ZD9-R}nx P qDI183~柄)()9~H99OcUX@TSX*!>KjZJd7P>m~*WjP ہ0! yۢ5Z]F~wq O$3ld0+uoLz,>LSXGT@Ȑ'e 1}8mQg*JS\3a=`&  s.!CmZB-hL`a||/7˫Oel=Aqc}pv u= 7{Y"v&$o$M̪ |ԓEv-LPwo/ܺb5Hzn:d.Ty.yPv&HD^"kjϩP1061B)4Ys_>ׂ^Tt9r8rV \_1yXh0z)FY2^sǗRWyGF'\K3Tj?M9~1$% gQz!.ۀ $_=t;c[Qͦ8~~v|ns<r Ch /rx}#@')8-0t@هGݻ=1=#Y%4\tOh+'0 hp  0 < HT\Math for ProgrammersPJim Van Vertham9C:\Program Files\MSOffice\Templates\Lecture Template.poteJim Van Verthes232Microsoft PowerPointfic@ukI@htq@')sCGDg  & &&#TNPPD2OMi & TNPP &&TNPP    --- !-----{yH--j}w@ P}ww0- @"Arialw@ n}ww0- .2 KaCurves:,),(.---- @"Arialw@ Y}ww0- .2 Jim Van Verth  $    .@"Arialw@ p}ww0- . 2 ( . . 2 jimY . . 2 @&. .2 ? essentialmath   . .2 &.com)  .--"System 0-&TNPP &՜.+,D՜.+,    0On-screen ShowRed Storm Entertainment>E Times New RomanArial WingdingsLecture TemplateMicrosoft Equation 3.0Curves AnimationAnimation of PositionAnimation of PositionParametric CurveLinear InterpolationLinear InterpolationMultiple Points ContinuityHermite CurvesHermite CurvesHermite CurvesComputing TangentsComputing Tangents Bezier Curve Bezier Curve Bezier CurveDe Castlejau's methodDe Castlejaus Method B-splinesNURBS References  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles8_AdHocReviewCycleID_EmailSubject _AuthorEmail_AuthorEmailDisplayNameL5SlidesE lmb@ndl.comLars M. Bishopp%_5 Jim Van VerthJim Van Verth  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)PicturesCurrent UserSummaryInformation(PowerPoint Document(>5DocumentSummaryInformation8