下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、任何一个3D引擎都是通过其内部的数学模型和实现工具来展现它的力量与速度的,Quake III中使用了一个非常有意思的技巧来计算平方根倒数(inverse square root)Carmacks不寻常平方根倒数卡马克算法 第一个跳出来的便是对函数Q_rsqrt中对 0 x5f3759df的使用,这个数计算了一个浮点数的 inverse square root,但是为什么这个函数有这 样的功能呢?观察q_math.c原本的函数:csharp view plaincopyprint?float Q_rsqrt( float number )long i;float x2, y;const floa
2、t threehalfs= 1.5F;x2=number *0.5F;y=number;i=* ( long* ) &y;/ evil floating point bit level hackingi=0 x5f3759df - ( i 1 );y=*(float * ) &i;y=y*( threehalfs-(x2*y*y);/1stiterationy=y*( threehalfs-(x2*y*y);/2nditeration, this can be removedy = y * ( threehalfs - ( x2 * y * y ) );/增加精度值return y;/返回倒数
3、它不仅有效,甚至在某些CPU上,Carmack的Q_rsqrt比(float)(1.0/sqrt(x)的计算快4 倍,尽管sqrt()通常使用的是FSQRT的汇编指令!在另一个文件code/common/cm_trace.c中,我们发现了更简洁的对同样HACK的实 现。这一次,它被用来计算一个fl oat - sqrt(x )的平方根。注意,其中的唯一不同是在返回值 上一一用返回*y取代了返回y。csharp view plaincopyprint?1. float SquareRootFloat(float number) 2.long i;3.float x, y;4.const floa
4、t f = 1.5F;5.x = number * 0.5F;6.y = number;7.i = * ( long * ) &y;8.i = 0 x5f3759df - ( i 1 );9.y = * ( float * ) &i;10.y = y * ( f - ( x * y * y );11.y = y * ( f - ( x * y * y );12.return number * y;/返回开方13. 牛顿对根的近似值上面的代码执行了众所周知的牛顿对根的近似值,像绝大多数其它迭代求近似值的计算 一样,牛顿近似值假定是迭代的;每一次迭代都增强了它的准确度直至达到需要的准确度。在牛顿近
5、似值中的一般想法是我们我们猜测一个数x的平方根值y,我们可能通过一个 简单的操作用x/y来拉平y来取得更好的猜测,使其更接近实际的平方根,例如,我们像下 面这样计算2的平方根,我们假定初始的猜测是1:csharp view plaincopyprint?1.2/1 = 2 ;(2 + 1) / 2 = 1.52.2/1.5 = 1.3333; ( 1.5 + 1.3333 ) / 2 = 1.41673.2/1.4167 = 1.4117;( 1.4167 + 1.4117 ) / 2 = 1.41424.And so on.如前面所提到的,牛顿的近似值是一个大家所熟知的用以快速计算平方根的
6、方法。但是,Carmack在初始的猜测中就选取的不寻常的值,它彻底加强了准确 度并且将Quake III中计算所要的值的迭代次数降到了 1次!魔数这个函数中真正有意思的方面是神奇的常量0 x5f3759df,用来计算初始猜测的,在csharp view plaincopyprint?1. i = 0 x5f3759df - ( i 1 );因此,把输入除以2并从神奇常量中减去。这个常数工作起来几乎是完美的一一对于 一个low relative error of 10A-3来说只要一次牛顿近似值迭代就够了。如评论中第二次迭代 中展示的,这个近似值对Quake III引擎来说已经足够了。结果,这个
7、神奇的常数0 x5f3759df成了一个迷了,在文章Fast In verse Square Root, 普度大学的数学家Chris Lomont研究了这个常数,用了几种精细的技术,Lomont想自己用 数学方法求出这个常数来,结果令人惊奇Lomont用数学方法计算出来的最佳常数(0 x5f37642f)有一点点不同,并且除了理论上强一些之外,它产生的结果并没有源代码中使 用的原始常数好!确实,John Carmack一定用了天才般的黑盒来找到这个常数。只是仅仅从数字上来找的方法中,Lomont找到了一个更好的常数,这个数比原始的那 个强了那么一点点。然而,实践中两个常数产生了大概相同的结果,
8、Lomont提出这个使用 了更好的常数的函数:c-sharpview plaincopyprint?1.float InvSqrt(float x)2.3.float xhalf = 0.5f*x;4.int i = *(int*)&x;5.i = 0 x5f375a86- (i1);6.x = *(float*)&i;7.x = x*(1.5f-xhalf*x*x);8.return x;9.关于本文,东拼西凑来的,今天也已经很晚了。只是最近我在研究图形学算法的过程中, 一些数字的数学的方法常常让我感到震惊,我惊叹于数学竟是如此的神奇。黑盒的应用是一 门大学问,那些伟大的但是并不一定很出名的数学家常常利用黑盒另外开辟了区别于经典算 法的道路,但却能带来非常人能想像的效率。在研究这些强人的作品的时候,能得到一种很 美妙很利落的体会,好的算法就就像好的音乐,当欣赏他们的时候,只想拿起吉它,轻轻的 弹上一首以其说计算机创造了 21世纪,还不如说算法与数据结构创造了 21世纪。前人的智慧 也常让我
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024届山东省临沭县青云镇中心中学中考英语对点突破模拟试卷含答案
- 酒店商业融资计划书
- 高中语文校本资料-金考卷文言文检测三
- 2024年高抗冲击聚苯乙烯专用料行业营销策略方案
- 2024年云南省红河州弥勒市中考数学二模试卷
- 中国香皂行业调研分析及发展趋势预测研究报告2024-2029版
- 中国手动榨汁机行业市场现状分析及竞争格局与投资发展研究报告2024-2029版
- 中国浓缩果汁行业调研分析及发展趋势预测研究报告2024-2029版
- 人美版小学美术一年级上册美术说课稿教案
- 一年级上册美术《画汽车》说课稿(附教案)
- 部编五下语文《刷子李》公开课教案教学设计二【一等奖】
- 2024年版亲子活动中心租赁合同范本
- 第四届国防知识竞赛初赛题-第一场地
- 第3课+追求人生理想+第一框+第3目(教案)【中职专用】2024-2025学年中职思想政治《哲学与人生》(高教版2023基础模块)
- 7-1《风景谈》教学设计 2023-2024学年统编版高中语文选择性必修下册
- 中图版地理七年级上册《第一节 疆域和行政区划》教学设计7
- 09S304 卫生设备安装图集
- DL∕T 5150-2017 水工混凝土试验规程
- (统编2024版)历史七上 第6课 战国时期的社会变革 课件
- 2024年中国社会科学院大学第四批专业技术人员招聘3人历年(高频重点提升专题训练)共500题附带答案详解
- Unit 6 I'm going to study computer science-Section B 1a-1e-教学设计 2023-2024学年人教版英语八年级上册
评论
0/150
提交评论