ࡱ> `!y7'(Y(-#@ ~ GxmQJA}3{I%ED/"(x&.i)"vA, +ٽ` {{oʀIC2爉,"NԠXe_;5AGM!bxe.ҊTq^wFH4ؐg'1N( u~7SN^&E{Er ӟ&@`=jo. ڪSgjh~|wOu_\њ|^{_n)7bXlZOk{0BCɰg| Q:X/[$^MT`!73=)n65k@}" uxcdd``n`d``baV d,FYzP1n:&&1! KA?H110l UXRY`7&,e`abM-VK-WMcs>Q. NUsi#/ EAZM*a < 9D@Aah `k` S&D_k݄TNPĂj# PM`%4 \P&+! -a[,m|nTXц0C习i M) `p ddbR ,.IAD !M1 w]`!etCZMk< ݻ@ 3xڕQ1K@}ߵ5ADS"JQAp0`B1šcWnUp{޻;BhHW[, 2D]ӆu~txcbe>e > N FixToFloat(i) = ((float)i) * 2.0-N Conversion to int can lose precisionY!8%$ 2 !5 %t$ - 'Basic Fixed-Point Math  For A and B, both M.N fixed point values, A+B = (int)A + (int)B A-B = (int)A  (int)B where (int)A is simply the fixed point treated bitwise as an integer This works because the binary points line up when A and B are both M.N<*-*-b1   6Multiplication  Basic Idea  ^Multiplication is a bit more complex, but it is analogous to the grade-school base 10 trick: ^   Multiplication  Challenges with Fixed Point  Range (Overflow) In the previous multiplication example, if we compute 1.0x1.0=1.0 using the given method, the intermediate value overflows Precision (Underflow) If we pre-shift numbers down to avoid overflow, we can end up shifting to 0 Extra shifting required for mul/div`{L${L$*        Fixed Point Help  Some CPUs have special instructions ARM9 (common in handhelds) Has a 32-bit X 32-bit ! 64-bit multiply Also has similar 64 + 32 x 32 ! 64 Can avoid overflow or underflow in intermediate values Allows a free shift in every ALU operationJ??X   3 *4        Fixed Point Summary   Allows fractional math to be done quickly with integer hardware Requires careful range and precision analysis Is the only option on many embedded and handheld devices, which don t have FPU hardware   Floating Point NumbersUsed to represent general non-integers Often thought of as the set of Reals This is far from the truth, as you ll see Most of this discussion will be about IEEE 754 32-bit single-precision Known in C/C++ as float Mention of doubles later tL*&SL&3FFP and Scientific NotationFP is analogous to scientific notation Scientific notation is: D.DDDD x 10E, where D.DDDD has a nonzero leading digit D.DDDD has fixed # of fractional digits E is a signed integer valueB?}?  (o FP/Sci Notation Range/Precision "(Precision is not fixed: Precision of 1.000x10-2 is 100 times more fine-grained than that of 1.000x100 Precision and range are related The larger the number, the less precise 32-bit int is not a subset of float Nm  (5 (P ! ! FP/Sci Notation Components *Sign Mantissa Normalized  has a nonzero integer digit Limited precision  fixed number of digits Exponent Chosen so that the mantissa is normalizedTT * T   * SignFP numbers have an explicit sign bit Float has both 0.0f and -0.0f By the standard, 0.0f = -0.0f But the bits are different Do not memcmp floats! This is only one of many reasonsJ! !*ExponentLike the exponent in scientific notation But, the exponent s base is 2, not 10 Stored as a biased number: ExponentBits = Exponent  Bias For float, Bias = 127 For float, -125 d" Exponent d" 128 Exponent term is )&V)& 9 j ]MantissaLRepresented as 1-dot-23 fixed point Store the 23 fractional bits explicitly Integer bit is implied ( hidden bit ) Generally, mantissa is normalized In other words, mantissa is 1.MantissaBits Similar to the scientific notation standard In the smallest numbers, the integer bit is assumed to be 0~LZ&Z"ZWZ<ZL&" ,<Binary RepresentationPut together, the representation is: S=Sign bit E=Exponent bits (8) M=Fractional mantissa bits (23) We will write as A = (SA,EA,MA) H|Special Values20: S=0, E=All 0s, M=All 0s -0: S=1, E=All 0s, M=All 0s +": S=0, E=All 1s, M=All 0s Ex: 1.0f / 0.0f = +" "": S=1, E=All 1s, M=All 0s Ex: -1.0f / 0.0f = -"S    "   "  Not a Number pRepresents undefined results 0.0f / 0.0f = NaN ACOS(2.0f) = Nan Two kinds  Quiet and Signaling Quiet can be passed on to other ops Signaling traps the code NaN: E=All 1s, M=Not all 0sj# = #   =  ,+oVery Small Numbers What happens when we run out of smaller and smaller exponents? Could flush to zero But, this can lead to the following problem X-Y=0 does not imply X=Y! Need to gradually underflow to zero FP does this by allowing denormals<SFGS F G   Denormals A denormal is an FP number whose hidden mantissa bit is 0, not 1 Indicated by E=0, M=Not all 0s A denormal is equal to (-1)S x 2-126 x 0.MantissaBits This allows precision to gradually roll off to zero.H{ 5,XaFloating-point Add BasicsTo add two positive floating point numbers A (EA, MA) and B (EB, MB): Swap as needed so A has the greater exponent, i.e. EB d" EA Shift MB to the right by EA-EB bits Add MA+MB and use as the new mantissa Adjust the new exponent up or down to re-normalize the result.F/ 4  \ FP Add NotesNot a simple process (even for pos # s) If A>>B, then B can be shifted to 0 Repeatedly adding small numbers to an accumulator (i.e. A+=B) can gradually lead to huge error At some point, A stops growing, no matter how many times B is added!@Fun with Floats  The Real World!!(Can t discuss every FP issue here: this is an example of why you should care 3D engine saw a spike in basic FP code Code (SLERP) was +,-,* only No loops, no complex functions What could be the problem?Breaking Down the ProblemInput values looked valid (no NaN) After a  while , in a demo, the spike hit We saved the values, along with timing In a small app, ran the slow and fast cases in tight loops The slow cases all had some tiny numbers (~1.0x10-43)6Tiny `" 0.0f(  Slow cases were denormals We assumed these numbers to be 0 But FPU was taking care to be accurate Denormal ops seemed to be slow, IDenormal Performance Did some more timing tests Even loading a denormal was slow! Pentium takes a big hit on denormals True even with exceptions masked! FPU pipeline gets flushed on denormals Little things matter HbI ;I>*& @  6 Don t Doubles Solve this? Doubles do help with most range and many precision problems. But: Need twice the memory of floats (duh) Frequently, significantly slower than floats Some platforms don t support them Avoid switching to them without tracking down the problem first@Cu@Cu:!Floating Point Wrap-uphFloats `" Reals Understand the limits of FP Analyze your FP issues Don t just jump to doubles at the first sign of trouble Be willing to rework your math functions to be FP-friendly(  /   ` f33` 3f3` ___>?" dd@,?" dd@  " @ `"  n?" dd@   @@``@n?" dd@  @@``PR    @ ` ` p>>D$ 0Essential Math for Games r(    N4lgֳgֳ ?P l X Click to edit Master title style!!  2  HL7lgֳgֳ ? l RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S    Z;l1 ?`` l b* 2    Z8Bl1 ?`  l X*(2    ZFl1 ?`  l Z*(2  N  6޽h? ? 33  Lecture TemplateE D$ 0Essential Math for Games 0 3(     N.gֳgֳ ?p  X Click to edit Master title style!!    H0gֳgֳ ? p  [#Click to edit Master subtitle style$$    Z51 ?``  d* 2    Z91 ?`   \*(2    Zh=1 ?`   \*(2  N  6޽h? ? 333D 0 ( ~@K@   BtN 1?P%  N X* 2     B N 1? % N Z*(2   p  0 ?*P  N,  BhN 1? @2 N RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S    H<N 1?P  N X* 2     H8N 1?  N Z*(2   H  0h0 ? ̙33 XP( \@d@   B @ 1?P%  @ X* 2     B%@ 1? % @ Z*(2     H3@ 1?P  @ X* 2     HK 1?  @ Z*(2   H  0h0 ? ̙33  4(  4l 4 C pE p  l 4 C ,F  @   H 4 0޽h ? 333  @t$(  tr t S ZP   r t S Z  H t 0޽h ? 330  P0(  x  c $\lP  l x  c $H]l l H  0޽h ? 3380___PPT10.lo0  `0(  x  c $lP  l x  c $l l H  0޽h ? 3380___PPT10.mP0  p0(  x  c $cP   x  c $j  H  0޽h ? 3380___PPT10.n+(   }++(  x  c $oP   x  c $p  n @   # #"*) pp  <Ph ?   L1/16 @`  < ?   K1/8 @`  << ?   K1/4 @`  <p ?f  K1/2 @`   <t ? f  L"   @`   < ?  I1 @`   <Ī ?   I2 @`   < ?   I4 @`   <  ?   I8 @`  < ?   MValue @`  <  ?@   I0 @`  <  ?@   I1 @`  <' ? @   I2 @`  </ ?f @  I3 @`  <6 ? @ f  L"   @`  <= ?@  I4 @`  <? ?@   I5 @`  <F ?@   I6 @`  <N ?@   I7 @`  <U ?@   KBit @`fB  6o ?@ @ fB  6o ?  fB  6o ?@  `B  0o ?@  `B  01 ?@  `B  01 ?@  `B  01 ?@  `B   01 ? @ `B ! 01 ?@  `B " 01 ?@  fB # 6o ? @  fB $ 6o ?  `B % 01 ?  `B & 0o ? @ f @ fB ' 6o ?@ @ fB ( 6o ?f @ @ `B ) 0o ? f fB * 6o ? fB + 6o ?f  H  0޽h ? 3380___PPT10.gЩE0  0(  x  c $dP   x  c $ğ  H  0޽h ? 3380___PPT10.g6\#0  0(  x  c $TlP  l x  c $l l H  0޽h ? 3380___PPT10.g0â0  0(  x  c $=lP  l x  c $o l H  0޽h ? 3380___PPT10.g0  0(  x  c $xP   x  c $`y  H  0޽h ? 3380___PPT10.g`0  0(  x  c $~lP  l x  c $,l l H  0޽h ? 3380___PPT10.hл<   ~ v  (  x  c $hJP  J x  c $-J J   TA  #?  ?Pa  #  c Z0e0e    B C`DEF @  jJ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| 0```0`0@  "`0  c Z0e0e    B C`DEF @  jJ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| 0```0`0@  "`0  H@ jJ? @p ZWe multiply the numbers as integers, and then slide the decimal point to the left by 1+1=2 [0 2[H  0޽h ? 3380___PPT10.i0:  %::gg9(  x  c $P    j  0 v # #"  0  v  < ?0 v G0 @`  < ?0v G0 @`  <D. ?0v G0 @`  <4 ?0v G1 @`  6< ? 0v P  @`   <C ?0 v G0 @`   <8? ?0v G0 @`   <" ?0v G0 @`   <# ? 0v G0 @`fB   6o ? 0 v`B  01 ?0v`B  01 ?0v`B  01 ?0v`B  01 ? 0 v`B  01 ?0v`B  01 ?0v`B  01 ?0v`B  01 ?0vfB  6o ? 0 v`B  0o ? 00`B  0o ? vvfB  6o ? 0 0fB  6o ?0 0fB  6o ? v vfB  6o ?v vH j   # #" P0   << ? G0 @`  <@ ? G0 @`   <@ ? G0 @` ! <0 ?e G0 @` " 6 ?Ke P  @` # < ?0K G1 @` $ <0 ? 0 G0 @` % < ?   G0 @` & <x ?   G0 @`fB ' 6o ? fB ( 6o ? fB ) 6o ?  `B * 01 ?  `B + 01 ?  `B , 01 ?00`B - 01 ?KK`B . 01 ?ee`B / 01 ?`B 0 01 ?`B 1 01 ?fB 2 6o ? 3 0tܗ`   ;X0 2 4 0̗  `&We want to compute 0.5f x 1.0f = 0.5f.'0 2' 5 0З0 VIn 4.4 fixed-point, this is:0 2 6 0ӗp0  h.After the integer multiply, we get (8x16=128):/0 2/ j  P  7# #" P   8 <$֗ ?P   G0 @` 9 <X ?P  G0 @` : < ?P   G0 @` ; <Hȗ ?P   G0 @` < <z ?P   G0 @` = 6z ? P   P  @` > <z ?P   G0 @` ? <z ?P   G0 @` @ <z ? P   G1 @``B A 0o ? P  `B B 01 ?P  `B C 01 ?P  `B D 01 ?P  `B E 01 ?P  `B F 01 ?P  `B G 01 ?P  `B H 01 ?P  fB I 6o ? P `B J 01 ? P  `B K 0o ? P P `B L 0o ?   fB M 6o ?P P fB N 6o ?  O 0Lz `  $Then, we need to shift right by 4 (not 8  we don t want an integer result, we want a 4.4 result, not 8.0)4k0 2#C j  P  P# #" P !  Q < z ?P   G0 @` R <z ?P  G0 @` S <dz ?P   G0 @` T <z ?P   G0 @` U <ܮz ?P   G1 @` V 6z ? P   P  @` W <z ?P   G0 @` X <z ?P   G0 @` Y <`z ? P   G0 @``B Z 0o ? P  `B [ 01 ?P  `B \ 01 ?P  `B ] 01 ?P  `B ^ 01 ?P  `B _ 01 ?P  `B ` 01 ?P  `B a 01 ?P  fB b 6o ? P `B c 01 ? P  `B d 0o ? P P `B e 0o ?   fB f 6o ?P P fB g 6o ? H  0޽h ? 3380___PPT10.iRV0  0(  x  c $P   x  c $  H  0޽h ? 3380___PPT10.jݚ-0   0(   x   c $XP   x   c $  H   0޽h ? 3380___PPT10.j00   0(  x  c $zP  z x  c $z z H  0޽h ? 3380___PPT10.kVL0  00(  x  c $!zP  z x  c $#z z H  0޽h ? 3380___PPT10.eЁ<0  @0(  x  c $P)zP  z x  c $ *z z H  0޽h ? 3380___PPT10.83's  80P(  x  c $0zP  z x  c $0z z   TA  $?  ?g r  $H  0޽h ? 3380___PPT10.eP&0  ` 0(   x   c $7zP  z x   c $48z z H   0޽h ? 3380___PPT10.b90  p$0(  $x $ c $>zP  z x $ c $>z z H $ 0޽h ? 3380___PPT10.8ւ  80((  (x ( c $DzP  z x ( c $Ez z  ( TA  %?  ? ', %H ( 0޽h ? 3380___PPT10.8r0  ,0(  ,x , c $dNzP  z x , c $ Oz z H , 0޽h ? 3380___PPT10.8@N  ia 0(  0x 0 c $4oJP  J x 0 c $oJ J j `P 0# #"  0 NSz jJ?`P `MMMMMMMMMMMMMMMMMMMMMMMM @` 0 NUz jJ?e`P PEEEEEEEE   @` 0 N(Wz jJ?`eP IS @`lB 0 <o ?``lB  0 <o ?PPlB  0 <o ?`PfB  0 61 ?e`ePlB  0 <o ?`PfB  0 61 ?`PH 0 0޽h ? 3380___PPT10.X>0  40(  4x 4 c $luzP  z x 4 c $(vz z H 4 0޽h ? 3380___PPT10.80  80(  8x 8 c $$|zP  z x 8 c $|z z H 8 0޽h ? 3380___PPT10.^0  <0(  <x < c $NP  N x < c $PN N H < 0޽h ? 3380___PPT10._*0  @0(  @x @ c $XNP  N x @ c $N N H @ 0޽h ? 3380___PPT10.`0^0  D0(  Dx D c $NP  N x D c $xN N H D 0޽h ? 3380___PPT10.oڕ0  H0(  Hx H c $NP  N x H c $N N H H 0޽h ? 3380___PPT10.p^0  L0(  Lx L c $NP  N x L c $N N H L 0޽h ? 3380___PPT10.8%`0   P0(  Px P c $hNP  N x P c $vޛ7Nn>z0\ j+W*_iQSɁ #z ]s[.K{fݍ*H0O݄iץMpޏyݠuLw~{{ӁeJ#0sC'p)<=YF&lŝ'e>t=J& :070?x=^XТCt\mX(V)_Wu[BCx¿E^PMM/$'Ӑ`6kgx-]zB+;BK֊1$Cq߉HAkOHB7x!'I`*~ Cky)]\ n!wKj%>D2ft.ay.g5=Φr\,H#ƫmo͸ך7Qd\>Wġs{ bי1E ./9,D-m? ΰ45ELF?/E/=RS!jZ9#޶;ܛ?iK=0Z32l#fDp3e-e)Md[^5'UP RxXFju14# ʬOs=M>|< Le|!V8~ZF#?BN}D#h& GdT[|8T1E,L"`s)]Cp:5irLzpZ/^b/3sڙ:9j!)J3Rb3~ag{Y^Qo\76\KKeK$➧w)=`[/kHDVr.ŸBnk*)B@BHmd6&΄CLYRrxF {dM{?PgFcIG^f`kume/!MU{{??f\aS%iZVʣ2~noE'173![Jś[a{Dq6zofjgu8(:N;#$h~1.2!?KxP,a/a/a/aV/!RBx2O}$⺧绽"*zQo FxND}Fr>+Ռ>l{ ڱN(;AB6u,g@5M/ͨwxMOQp+`Y& Nz0X_j`b5[[J=ɛW~x ЃrI!IYƋY%We>wq=jR+F:YDuCDav>W6nIz JIw#Y2C,2V\, y.T~"#:x'q~nhZZ8)=`G .W eWAJM@EiXvpx$g}ֹ _^ӓ D֦|NSǵtv&ei"bdwvt:vFi "uTi6so2 "uHYv_gcwA +w׼;4DiPrcE!Wr0E1 ~ʕ ZI0KO}S &^Τ#[F~."$6'7/o1358O:<>@/CgEG4:V>WOh+'0 hp  ( 4 @LTMath for ProgrammersPJim Van Vertham9C:\Program Files\MSOffice\Templates\Lecture Template.potejimvvgr67vMicrosoft PowerPointfic@U8@htq@TGfg  .& &&#TNPP82OMi & TNPP &&TNPP    3--- !-----iyH--wc ~@  ~ ~ ~0- @"Arial ~@u  ~ ~ ~0- ..2 Essential Mathematics for '!! ! 1!! 1! !. .!2 BGames Programmers.!1 ' ! 11 . .(2 (Fixed/Float Tutorial)$ !!$ !$!! ! .---- @"Arial ~@  ~ ~ ~0- .2 K Lars Bishop    .@"Arial ~@u  ~ ~ ~0- . 2 9( . . 2 Elmb. . 2 @&. . 2 ndl. .2 .com)  .--"System !H ~-&TNPP &՜.+,0    ]On-screen ShowRed Storm Entertainmentg$2 +Times New RomanArial WingdingsSymbol Courier NewLecture TemplateMicrosoft Equation 3.0CEssential Mathematics for Games Programmers (Fixed/Float Tutorial)Number SpacesNumerical RepresentationsApproximating RealsFinite RepresentationsFixed Point NumbersFixed-Point NomenclatureFixed Point BenefitsFixed-point vs. Floating-pointFloating-point ↔ Fixed-pointBasic Fixed-Point MathMultiplication – Basic IdeaMultiplicationChallenges with Fixed PointFixed Point HelpFixed Point SummaryFloating Point NumbersFP and Scientific Notation FP/Sci Notation Range/PrecisionFP/Sci Notation ComponentsSign Exponent MantissaBinary RepresentationSpecial Values Not a NumberVery Small Numbers DenormalsFloating-point Add Basics FP Add Notes#Fun with Floats – The Real WorldBreaking Down the ProblemTiny ≠ 0.0fDenormal Performance"“Don’t Doubles Solve this?”Floating Point Wrap-up  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles$_W@jimvvjimvv  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)PicturesCurrent UserSummaryInformation(PowerPoint Document(WDocumentSummaryInformation8Root EntrydO) PicturesCurrent UserGSummaryInformation(%_W Jim Van VerthJim Van Verth