数分算法范文

第一篇：数分算法范文

数分

1.2.2 I[0,]; sin(xy)dxdy,I2 I[0,2]; (xy)dxdy,I3.计算积分Ixdyydx22，其中C为椭圆2x3y1，沿逆时针方向。 22C3x4y4.已知 zf(xz,zy), 其中f(u,v)存在着关于两个变元的二阶连续偏导数，求z关于x,y的二阶偏导数。

x2y2z25.求椭球体2221的体积。

abc6.若l为右半单位圆周，求|y|ds。

l7.计算含参变量积分I(a)0 ln(12acosxa2)dx(a1)的值。

8. 若积分在参数的已知值的某邻域内一致收敛，则称此积分对参数的已知值一致收敛。试讨论积分

I10adx

1a2x2 在每一个固定的a处的一致收敛性。

9. 讨论函数F(y)0 yf(x)dx的连续性，其中f(x)在[0,1]上是正的连续函数。

x2y222210.求球面xyz50与锥面xyz所截出的曲线的点(3, 4, 5)处的切线与法平面方程。

2211.求平面z0，圆柱面xy2x，锥面z222x2y2所围成的曲顶柱体的体积。

12.计算三重积分

I(xyz)dxdydz。其中 V:0x1, 0y1,0z1。

V13. 利用含参变量积分的方法计算下列积分

14. 计算333M ex2dx。

xdydzydzdxzdxdy, 其中M为上半椭球面

x2y2z2221,z0(a,b,c0), 2abc定向取上侧. 15.求I(xy)ds ，此处l为联结三点O(0,0), A(1,0), B(1,1) 的直线段。

l

16.计算二重积分

I(x2y2)dxdy。

其中 是以yx,yxa,ya和y3a (a0)为边的平行四边形。

17.计算三重积分

IVx2y2z2(222)dxdydz。 abcx2y2z2其中V是椭球体2221。

abc18.计算含参变量积分0eaxebx dx (ba0)的值。

xx2u2u19. 已 知uarccos，试确定二阶偏导数与的关系。

yxyyx20. 讨论积分xcosxdx的敛散性。 pqxxxy2. 求limlimf(x,y)和limlimf(x,y). 极限limf(x,y)是否 21. f(x,y)x0y0y0x0x0xyy0存在 ? 为什么 ?

xy22 , xy0 ,2222. f(x,y)xy 验证函数f(x,y)在点( 0 , 0 )处连续 ,偏22 0 , xy0 .导数存在 , 但不可微

2z2z23. 设函数f(u,v)可微 , zf( x , xy ). 求 2 和 2

yx , 1 , 2 )的方向. .24. f(x,y,z)xxyyz, l为从点P0( 2 , 1 , 2 )到点P1( 1求fl(P0). 25.设为单位球面x222y2z21，证明：

1f(axbycz)d2f(a2b2c2t)dt.

126. 求 xydxdy, 其中 D: yD1x , y2x , xy1 , xy3. 2x8x2 dx. 27. 求积分I lnx028.求 yedxdy，其中D是以点( 0 , 0 )、( 1 , 1 )和( 0 , 1 )为顶点的三角形域. D2129. 计算积分 (2xsinLy2)dxx2cosy2dy. 其中L为沿曲线yex1从

点( 0 , 0 )到点( ln2 , 1 )的路径 . 30. V :xy2x , xyz2(xy) . 为V的表面外侧.计算积分 3223(xyz)dydz(xycosz)dzdx(xy22222232z)dxdy. 231.已知 f(x,y)y. 证明极限limf(x,y)不存在 . 2x0xyy032. 设函数u(x,y)和v(x,y)可微 . 证明 grad(uv)u gradvv gradu. 33. 设函数f在有界闭区域D上连续 . 试证明: 若在D内任一子区域DD上都有

f(x,y)dxdy0, 则在D上f(x,y)0. D34. 求极限

(x,y)(0,0)limsin(x2y2)1xy122.

1222(x2y)sin , xy0 ,22xy35. f(x,y)

0 , x2y20 .求fx( 0 , 0 )和fy( 0 , 0 ). 36. 设函数f(u,v)有连续的二阶偏导数 , zf( xy , xy ). 求

22zz、 xy2z和. xy37. f(x,y,z)xyz , 点P0( 1 , 1 , 1 ), 方向l:( 2 , 2 , 1 ). 求

23gradf(P0)和f沿l的方向导数fl(P0). 39. 曲线L由方程组

222 2x3yz9 , 2 22 z3xy 确定 . 求曲线L上点P0( 1 , 1 , 2 )处的切线和法平面方程 40. 求函数f(x,y)xy在约束条件满足极值充分条件 )

111之下的条件极值 . ( 无须验证驻点 xyx2y41. f(x,y)4. 试证明在点( 0 , 0 )处f(x,y)的两个累次极限均存在 , 但

xy2二重极限却不存在 . xy , x2y20 ,22 42. f(x,y)xy 证明函数f(x,y)在点( 0 , 0 )处连续,偏导22 0 , xy0 .数存在 , 但却不可微 43. 设 zlnx2y2, 验证该函数满足Laplace方程

2z2z0. 22xy44. 设函数f(x,y)在点( 0 , 0 )的某邻域有定义 , 且满足条件|f(x,y)|  xy. 试证明 f(x,y)在点( 0 , 0 )可微。

222fxff45. 设f(x,y)xy，求，，;

xyyxy46.设zsin(xcosy)，求全微分dz;

x2yz2xyz0所确定的隐函数的偏导数47. 求由方程

z，xz。 y48. 求函数 zxe2y在点P(1,1)处从P(1,1)到Q(2,1)方向的方向导数。 49.求2ydxdy, D由旋轮线 Dxa(tsint), 0t2 与y0围成; ya(1cost),

50.求0exdx

limx2y2x2y211251.求二重极限 x0y0.

2zz52.zz(x,y)由zexy确定，求xy.

zz1yy3. 53.设zln(xy)，证明：x1313xyf(xy,)x2y2x54.设，则

f(x,y)_____________.

15()()55.已2知，则2=___________.

2256.设函数f(x,y)2xaxxy2y在点(1,1)取得极值，则常数 a________

57.已知f(x,y)xy(x4arctany)2,则fx(1,0)________.

2z2zt220z2cos(x)xt2,证明:t58.设

33f(x,y)x12xy8y59.求函数的极值

zz,z60.求由exyzxy所确定的隐函数zz(x,y)的偏导数xy.

第二篇：13-14-2学期数分期末复习点

第七章： 定义域，基本的二重极限求法(有些可能涉及到一元函数的无穷小等价)，以及判定极限不存在，偏导数，全微分，隐函数的偏导数，极值(条件极值)，曲面的切平面和法线，曲线的切线和法平面。

p. 340:1; p. 349：4，5;p. 355:1;p. 376：1，2，6;p. 398：1;

p. 422：1;p. 441：1，4，5，7;p. 454：1，3，4;p. 468：2，3，4;

第八章： 二重积分的几何意义，估值不等式，比较大小，这三项习题请参照同济大学相关内容)，交换积分次序，直角坐标、极坐标系下计算二重积分。三重积分的球面坐标，截面法的计算方法。(这些重积分的计算可能结合了格林公式，高斯公式)积分中的利用对称性计算方法。

p. 29:2，3(3)，4，5，7(1);p. 55:1~6，7(1);

第九章： 会计算基本的第一类曲线积分，以及利用格林公式计算第二类曲线积分。会计算第一类曲面积分。利用高斯公式计算第二类曲面积分。

p. 82:4，5，6，7;p. 104：1，2，3，5(1)(2);p. 123:1，2，3; p.133:1~4;

第十章： 数项级数收敛的必要条件，等比级数，p-级数，比较判别法的极限形式，比值判别法，根值判别法。交错级数的莱布尼兹定理。

p. 175:1(1)~(4)，(6);p. 197：1(1)(3)(5)(7)(9);

第十一章： 函数列的一致收敛性判别，利用维尔斯特拉斯(优级数)判别法判别函数项级数的一致收敛性，幂级数的收敛半径和收敛域。利用幂级数求和。函数展开成幂级数。

p. 225:1(1)(2)(3)(6)(8)(10)(11); p. 240:1(6)(7);

p. 257：1(1)~(6)，2(1)~(7)(9)，3(1)(2)(4)(5)(6)(7);

p. 269:1(3)(4)(9).

第十二章：广义积分收敛的判别和计算，推论2(书中p.280)，推论(书中p.297)。含参量积分的导数，利用欧拉积分(gamma函数，Beta函数)计算积分。

p. 289:1(1)~(5)(7)(8);p. 306：1，2;p. 315:1，2;

p. 352:1(1)~(3)(5)(7)(9).

第十三章：会求傅里叶级数，正弦级数，余弦级数。

p. 372:1(2)(4)(5)，3;p. 392：1，2.额外要求的：分部积分法。

第三篇：《算法和算法的描述》观课报告

通过观看周思博老师讲授的《算法和算法的描述》一课，我收获颇丰。周老师所体现出的对课堂的掌控能力、扎实的专业知识和过硬的教学基本功，令我折服。整堂课，学生能够积极参与，课堂气氛活跃,很好的体现出快乐课堂效率课堂的特点，下面我就自己的收获谈几点观课感想。

一、导入环节引人入胜

通过“过河”游戏导入新课，可以快速地吸引学生的注意力，激发学生的学习兴趣，充分调动学生学习的主动性。学生在玩的过程中轻松直观的解决了“如何过河”，从而通过亲身体验获得解决问题的方法与步骤——算法的概念，学生也在老师的异动下轻松地掌握了算法的概念，将原本抽象地概念通过游戏赋予了形象化。

二、教学方法灵活多样

在教学过程中，周老师采用了游戏激趣、成功体验激趣、直观教学激趣等方式方法，激发学生的学习兴趣，唤起了学生的学习欲望，从中激发学生学习兴趣。开展小组活动，小组成员对共同学习中发现的问题，利用教师所提供的感性材料，通过分析、比较、抽象和概括与一系列积极的思维活动，实现了认识上的飞跃。小组活动不仅为每个学生表达自己的看法创造机会，而且有利于培养学生的团队精神和创新能力。着重加强了师生互动，想方设法激发学生主动求知的意识和积极进取的精神，给学生创设了自主、合作、探究学习的时间和空间，教好地培养了学生敢于质疑、乐于交流与合作、善于探究的学习习惯。

三、教学案例设计精心。

这节课课堂实例选取典型，分析讨论了生活中的实例，“比较大小”案例让学生知道如何比较两数的大小，“交换酒杯”案例让学生知道如何交换两个变量的值，“累加求和”案例让学生体会累加器的使用。在这三个案例中，第一个案例采用教师展示，学生评论的方法;第二个案例教师仅展示算法，学生动手绘制流程图;第三个案例学生自己描述算法并绘制流程图。由简单到复杂，难度循序渐进，以巩固算法的描述方法。。 整个教学过程体现了以教师为主导，学生为主体的教学理念，把课堂让给学生，让学生活跃于课堂，去发现问题，解决问题。

四、总结归纳

在课堂小结环节中，周老师利用思维导图的方式回顾本节课知识点。将不同的知识点相互联系起来。让学生形成清晰的知识脉络。

学习了周老师的这节课，我获益匪浅。今后在我的课堂中，我会更加注重教学设计，突出重难点，选取合适的教学策略，学生更高效的上好每一节课。

第四篇：预算法及预算法实施条例考试试题

姓名：________________得分：_________

一、单选题(共30分，每题2分)

1.《中华人民共和国预算法》于1994年3月22日经第八届全国人民代表大会第二次会议通过，全文共_____章_______条。()

A.11,79B.10,80C.11,80D.10,79

2.财政部应当自全国人民代表大会批准中央预算之日起()日内，批复中央各部门预算。

A.5日B.7日C.10日D.30日

3.对于预算执行中上下级财政之间按照规定需要清算的事项，应当()。

A.在决算时办理结算B.在发生时办理结算C.一并计入上级财政的决算

D.只需提请上级财政备案

4.各级政府应当在每一预算至少()次向本级人民代表大会或者其常务委员会报告预算的执行情况。

A.1B.2C.3D.4

5.有权决定预算预备费的动用()。

A.同级人大B.同级人大常委会C.同级人民政府D.上一级人民政府

6.根据《预算法》的有关规定有权审查和批准县级决算的机关是()。

A.县级人民代表大会B.县级人民代表大会常务委员会C.县级人民政府

D.县级财政部门

7.《预算法实施条例》于1995年11月2日经国务院第三十七次常务会议通过，1995年11月22日国务院令第186号发布，自发布之日起施行条例共_____章____条。()

A.11,79B.11,80C.8,80D.8,79

8.我国国家预算现设()。

A.中央、省(自治区、直辖市)、市(州)、县(市、区)四级预算

B.中央、省(自治区、直辖市)、市(州)、县(市、区)、乡(镇)五级预算

C.中央、省(自治区、直辖市)、市(州)三级预算

D.中央、省(自治区、直辖市)、市(州)、县(市、区)、乡(镇)、村 六级预算

9.我国国家预算是指()。

A.自公历12月31日起至次年12月31日止B.自公历1月1日起至次年1月1日止

C.自公历1月1日起至12月31日止D.自公历12月31日起至12月31日止

10.下列各项中,不属于政府财政部门预算拨款应遵循的原则的是()。

A.按照预算拨款B.按照规定的预算级次和程序拨款C.按照进度拨款，即根据各

用款单位的实际用款进度和国库库款情况拨付资金D.按照各单位需要拨款

11.按照分享程度划分，我国的预算收入()。

A.仅包括中央预算收入B.仅包括中央预算收入和地方预算收入C.仅包括中央和地方共享收入D.包括中央预算收入、地方预算收入以及中央和地方预算共享收入

12.地方各级预算按照()的原则编制，不列赤字。

A.厉行节约勤俭建国B.量入为出收支平衡C.统筹兼顾确保重点

D.统筹兼顾收支平衡

13.各级人民政府财政部门应在同级人民代表大会会议举行的()前，向同级人民代表大会财政经济委员会或人民代表大会常务委员会财政经济工作委员会汇报预算草案编制情况。

A.60日B.30日C.20日D.45日

14.()是办理预算收入的收纳、划分、留解和库款支拨的专门机构。

A.财政部门B.国库C.税务部门D.海关

15.各级政府预算应当按照本级政府预算支出额的()设置预备费，用于当年预算执行中的自然灾害救灾开支及其他难以预见的特殊开支。

A.1%至3%B.2%至3%C.3%至5%D.5%至6%

二、多选题(共20分，每题2分)

1.行政事业单位国有资产管理坚持()原则。

A.资产管理与预算管理相结合B.预算管理与预算外管理相结合C.资产管理与财务管理相结合D.实物管理与价值管理相结合

2.我国国家预算的组成部门包括()。

A.中央预算B.部门预算C.地方预算D.单位预算E.本级预算

3.下列部门中，属于预算收入征收部门的有()。

A.审计B.税务C.财政D.海关E.工商.

4.预算收入划分为()。

A.中央预算收入B.地方预算收入C.中央和地方预算共享收入D.特殊预算收入E.一般预算收入

5.下列各项中,属于县级人民代表大会常务委员会预算管理职权的有().

A.监督本级总预算执行B.审查和批准本级预算调整方案C.撤销乡级人民代表大会关于预决算的不适当的决定D.定期向省级政府财政部门报告县级总预算的执行情况 E.编制县级预算的调整方案

6.预算管理应当遵循的主要原则有()。

A.一级政府一级预算原则B.分税制原则C.收支平衡原则D.统一管理原则E.集中支付原则

7.下列关于预算调整有关事项的说法中,正确的是()。

A.各级政府对于必须进行的预算调整应当编制预算调整方案B.预算调整方案由政府审计部门负责具体编制C.未经批准而调整预算的,由上级政府应当责令其改变或者撤销D.地方各级政府预算的调整方案经批准后,由本级政府报上一级政府备案

8.预算收入包括()

A.税收收入B.依照规定应当上缴的国有资产收益C.专项收入D.其他

9.下列预算收支变化必须报经本级人民代表大会常务委员会审查批准的有()。

A.预计预算总收入减少额超过预算额5%的B.人民代表大会批准预算决议中强调确保的预算支出项目预计需要调减指标的C.农业、教育、科技、环境保护、计划生育、社会保障预算支出预计需要调减的D.调增调减预算收支涉及科目超过预算科目30%以上的

10.按监督主体划分预决算监督包括()。

A.各级人民代表大会及其常务委员会对预算、决算进行监督B.各级政府对下一级政府预算执行的监督C.各级政府财政部门对本级各部门、各单位和下一级财政部门预算执行的监督检查D.各级政府审计部门对预算执行情况和决算情况实行的审计监督。

三、判断题(共20分，每题2分)

1.县级以上地方各级政府预算的调整方案必须提请本级人民代表大会审查和批准。未经批准，不得调整预算。()

2.各级政府预算预备费的动用方案，由本级政府财政部门提出，报本级政府决定。()

3.各级财政、税务、海关等预算收入征收部门，必须依照有关法律行政法规和财政部的有关规定，积极组织预算收入，按照财政管理体制的规定及时将预算收入缴入中央国库和地方国库，未经本级政府批准，不得将预算收入存入在国库外设立的过渡性帐户。()

4.地方政府依据法定权限制定的规章和规定的行政措施，不得涉及减免中央预算收入、中央和地方共享收入，不得影响中央预算收入、中央和地方共享收入的征收。()

5.地方国库业务应当接受中央国库的指导和监督，对地方财政负责。()

6.在预算执行过程中，因上级政府返还或者给予补助而引起的预算收支变化，属于预算调整。

()

7.全国人民代表大会及其常务委员会对中央和地方预算、决算进行监督。()

8.预算开始后，各级政府预算草案在本级人民代表大会批准前，本级政府可以先按照上一年同期预算支出数额安排支出。()

9.公民或者组织对违反预算的行为，有权向各级人民代表大会及其常务委员会或者其他有关国家机关检举、控告。()

10.各级人民政府对下一级人民政府报送备案的预算，认为有同法律、法规相抵触或者有其他不适当之处，有权撤消批准预算的决议。()

四、简答题(共30分，每题6分)

1、预算收入包括哪些内容

2、预算外资金包括哪些内容

3、地方各级政府预算编制包括哪些内容

4、各级政府编制预算草案的依据包括哪些内容

5、什么是预算调整

第五篇：光线跟踪算法

光线跟踪算法的研究与进展

刘进

摘要：光线跟踪算法是图形绘制技术中的经典算法，但是该算法光线与物体的求交量庞大，严重制约着应用。本文从经典的光线跟踪算法出发，研究了目前光线跟踪算法的国内外研究状况，具体从改进的光线跟踪算法和光线跟踪算法的加速技术，并进行了对比和分析。最后对近几年的光线跟踪方法发展进行了总结，对未来研究热点及应用前景进行了展望。

关键词：可视化;光线跟踪算法;并行绘制;GPU

Research Status and Prospect for ray tracing algorithms Abstract: As an classic algorithms of volume rendering in computer graphics, ray tracing algorithms is hindered by the huge computation cost in ray and volume. This paper summarizes the research status in ray tracing technology from the two main solutions: different extended ray tracing algorithms and the acceleration techniques in ray tracing algorithms. Comparison and analysis the different performance. Both current research focus and the future research prospect are also discussed in recent years.

Key words: visualization; ray tracing algorithms; parallel rendering; GPU

引言

随着科学技术和计算机高速发展，人类已经进入到一个科技支撑的时代，在我们的生活中到处充满了高科技产品和技术，给我们的生活带来了改变和方便，其中计算机图形学的应用已经渗透到了各个工程技术领域，其已经成为计算机科学的重要学科之一，具有相当的重要性和无可替代的作用。计算机图形学自诞生以来得到了飞速发展，其通过计算机的输入设备、显示设备及绘制设备等对图形的表示、绘制、存储、显示等相关理论知识、算法技术进行研究的一门学科。真实感图形绘制是计算机图形学的主要研究内容之一，在虚拟现实、文物保护、影视游戏、三维动画、医学研究、建筑设计和系统仿真等领域中得到广泛应用，它追求对场景的逼真渲染[1]。其中逼真的图形绘制技术是最为活跃的研究领域之一。

光线跟踪算法是真实感图形绘制技术的主要算法之一，其原理简单，能够有效生成具有比较真实视观效果的各种各样的场景。该算法可通过一些光照明模型模拟在光源或环境光照射下物体表面发生的多种光照效果，例如漫反射、高光、镜面映像、场景消隐及阴影等。在计算机中对现实场景或是虚拟场景进行显示，除了要构建场景图形外，还要将场景中的各种光照效果模拟出来，这样生成的场景才能更逼真，光线跟踪算法就是既在几何上相似，也能模拟出大部分的光照效果的生成真实感图形的方法。光线跟踪算法是逆着真实光线的投射方向进行反向跟踪的，从视点向场景发射光线，光线与场景中的物体相交，计算光分量，因为视点向场景的光线较多，因而该算法光线与物体的求交量较大，但是因为其对场景的模拟的逼真，及其可以模拟漫反射、镜面反射、反射折射以及阴影等光照效果[1-2]。

进入90年代，随着计算机技术的发展，光线跟踪技术广泛应用于三维特技电影、电视广告、电子游戏的制作中，其应用领域也正在向如物理、化学、生物等其他学科领域渗透，其应用的范围正不断扩大，很多基于光线跟踪算法的新理论也应运而生，物理学中的相对论、地理中地层的绘图等与光线跟踪算法相结合的研究已经实现，极大的推动其学科的发展。可 以说它已经与我们的生活息息相关了，因此对光线跟踪进行研究具有很现实的重要意义[1-3]。

1.光线跟踪算法原理

对光线跟踪算法研究最早可以追索到 1968 年，Appel 等在对消除隐藏面的研究时运用的光线投射算法，在原理上第一次描述了光线跟踪算法。1979年，Kay与Greenberg对光的折射进行了研究，直到1980年，Whitted综合考虑了多种光照效果，模拟出了漫反射、镜面反射、高光、反射折射以及阴影等光照效果，提出了第一个整体的光照明模型——Whitted 模型[4]。

光线跟踪思路：从视点出发，通过图像平面上每个像素中心向场景发出一条光线，光线的起点为视点，方向为像素中心和视点连线单位向量。光线与离视点最近的场景物体表面交点有三种可能：

1.当前交点所在的物体表面为理想漫射面，跟踪结束。

2.当前交点所在的物体表面为理想镜面，光线沿其镜面发射方向继续跟踪。 3.当前交点所在的物体表面为规则透射面，光线沿其规则透射方向继续跟踪。

图1 三个半透明玻璃球场景跟踪图

如图1中，场景中有三个半透明玻璃球，视点发出光线与场景最近交点为P1，使用任意局部光照模型可以计算出P1点处的局部光亮度Ilocal，为了计算周围环境在P1点处产生的镜面发射光和规则折射光，光线1在P1点处衍生出两支光线：反射光2和折射光3。P1处的光照由三部分组成：

Ilocal + ks * I2 + kt * I

3(1) 其中：I3 为折射光线3的颜色，Kt为折射率，I2 为反射光线2的颜色，Ks为反射率，I3 和 I2 的计算需要递归。

我们知道光源向其四周发射出数不清的光线，从光源对光线进行跟中是永远也跟踪不完的。而光源发出的光线进入人眼的只有少部分直接或是通过场景中的物体表面之间的折射和反射后间接地射入观察者眼中。所以，标准的光线跟踪算法是逆着射入观察者眼中的光线进行跟踪的方法来完成整个跟踪过程的。在光线跟踪的过程中选定视点，将一个与视点位置相当的平面矩形区域当做显示屏幕，将显示屏幕均匀网格划分，每一个网格表示显示屏幕的一个像素，从视点向像素网格中心引射线作为跟踪光线进行跟踪，跟踪该光线得到的光亮度就是显示屏幕对应的像素的光亮度，所有像素点组成场景图形[5]。

光线跟踪的流行来源于它比其它渲染方法如扫描线渲染或者光线投射更加能够现实地模拟光线，象反射和阴影这样一些对于其它的算法来说都很难实现的效果，却是光线跟踪算法的一种自然结果。光线跟踪易于实现并且视觉效果很好，所以它通常是图形编程中首次尝试的领域。光线跟踪的一个最大的缺点就是性能，扫描线算法以及其它算法利用了数据的一致性从而在像素之间共享计算，但是光线跟踪通常是将每条光线当作独立的光线，每次都要重新计算。但是，这种独立的做法也有一些其它的优点，例如可以使用更多的光线以抗混叠现象，并且在需要的时候可以提高图像质量。尽管它正确地处理了相互反射的现象以及折射等光学效果，但是传统的光线跟踪并不一定是真实效果图像，只有在非常近似或者完全实现渲染方程的时候才能实现真正的真实效果图像。由于渲染方程描述了每个光束的物理效果， 所以实现渲染方程可以得到真正的真实效果，但是，考虑到所需要的计算资源，这通常是无法实现的。于是，所有可以实现的渲染模型都必须是渲染方程的近似，而光线跟踪就不一定是最为可行的方法。包括光子映射在内的一些方法，都是依据光线跟踪实现一部分算法，但是可以得到更好的效果[5-6]。

2光线跟踪算法及扩展算法

光线跟踪算法通过模拟光的传播方式，即光从光源出发经过若干次反射或折射到达摄像机的过程来实现全局光照效果。其思想起源于光线投射算法[5]。目前，国内外对光线跟踪算法的研究大部分处于理论研究的水平，集中在对光线跟踪算法的加速，而对于光线跟踪算法在生产生活和科学研究中的应用还是较少的，还处于起步阶段。针对标准的光线跟踪算法的不足，研究者提出了很多基于标准光线跟踪算法的改进算法。

Cook等[7]提出分布式的光线跟踪算法，根据分布函数进行采样而产生一定方向分布的光线，并在场景中进行跟踪而产生运动模糊、景深、半影和模糊反射等光照效果。Kajiya等[8]提出基于分布式光线跟踪的层次采样算法，它适应具有广泛多样性的基于蒙特卡洛方法的光线跟踪。Mitchell[9]将图像的非均匀采样方法应用到高维的分布式的光线跟踪算法中。Walter等[10]通过对光源进行聚类生成相应的树状结构，对多种光源进行光线跟踪，产生丰富的视觉效果。Hachisuka等[11]提出光线跟踪的多维自适应采样与重建技术，通过多维函数的综合进行分布式的绘制效果。在具有复杂的漫反射和镜面反射成分表面的场景中，Ward等[12]提出一个计算全局光照效果的有效方法，即在绘制阶段用蒙特卡洛方法计算间接光照并将其保存起来，提高计算效率。Lafortune等[13]提出双向的路径跟踪算法，即先从人眼与光源两个方向发射光线并在场景中 进行分布式跟踪，然后进行光照计算，达到增强室内间接光照的绘制效果的目的。 Lafortune等[14]描述了种的全局反射分布函数的概念，通过简化光照模型，对射能量和聚集能量进行卡洛绘制方法，提高成像效果。Veach等[15]对优化的光线方向进行采样而计算光照，在增加少量的计算成本下提高成像效果。Veach等[16]提一种新的蒙特卡洛光线跟踪算法，根据光线跟踪的路径对场景中明亮的区域进行密集采样，对多维采样空间进行自适应采样。Möller等[17]提出高效的并且所需内存空间最小的光线与三角形的求交算法;Kajiya [18]和Toth[19]分别提出了光线与参数表面的求交算法;Hanrahan [20]提出光线与代数曲面的求交算法;Hart等[21]提出光线与确定性的不规则碎片形表面的求 交算法;Knoll等[22]提出高效的光线与代数隐式曲面的求交算法;Heckbert等[23]提出光柱和网格模型的求交算法;Amanatides [24]提出光锥和三维模型的求交算法。Reshetov[25]提出以层次性的光束作为光线集合的代理，实现 多级的光线跟踪算法，能极大减少计算量并且能严格保证了方案的几何正确性。Moon等[26]提出光线跟踪的光线重新排序的缓存算法，能有效地匹配光线跟踪中各级缓存的数据，极大地提高了光线跟踪效率，特别就无法全部载入内存的大规模的三维模型而言。Mora[27]提出基于分而治之策略的光线跟踪算法，即在空间细分时直接计算光线与场景的交点，无需存储相关的数据，大大提高动态场景的绘制效率。Hou等[28]提出高效的基于微三角形的光线跟踪的重用算法。

光线跟踪算法简洁灵活且修改移植方便，绘制结果真实感程度高，绘制速度慢一直是一个严峻的问题。对此人们提出了许多改进的算法来加快绘制速度，但由于体数据庞大，单纯的算法改进越来越难以满足现在的需求，随着图形处理器的迅速发展，因此人们开始将目光转向图形硬件，希望借助硬件来实现光线跟踪体绘制，提高实际应用价值。

3基于加速技术的光线跟踪法

光线跟踪需要完成大量的光线与场景的求交测试运算，所以求交计算构成了光线跟踪算 法的瓶颈，因此，要提高光线跟踪的效率就必须提高光线与场景的求交测试效率。近几年，快速发展的图形处理器GPU强大的并行处理能力和高精度的浮点运算能力使得越来越多的应用研究开始利用GPU来完成[29]。目前基于GPU的光线跟踪、交互式体绘制技术是国内外研究热点。

Purcell[30]首先提出完全基于GPU的光线跟踪算法，成为一些基于GPU的光线跟踪渲染器的基础。Cullip等首先将体数据沿投影轴进行切片依次装入GPU纹理内存，在体数据内定义代理几何体元进行重采样、颜色合成等操作。Meiner[31]采取压缩纹理的方式以提高速度，但影响绘制结果准确度。Kruger[32]在GPU上进行光线投射绘制时，将与光线相交的体元从纹理表中取出，计算并更新其透明度和颜色值，利用片段着色沿光线方向采用步进法完成采样进行最终绘制。Chen[33]使用视点相关的层次采样将面向多边形绘制的图形引擎转化为体光线投射算法引擎，提供了基于GPU的一种新的体光线投射绘制方法。Singh等[34]在GPU上实现了实时的光线与代数隐式曲面的求交算法。Zhou等[35]通过在图形硬件上实现光线跟踪的加速结构 k-d树的实时构造，以现对动态场景进行实时地光线跟踪。Woop[36]研制的可编程光线处理芯片RPU(ray processing unit)可用来实时光线跟踪动态绘制复杂的几何场景，达到了理想的交互绘制速度。

在加速光线跟踪体绘制技术中，另一种有效地方法是采用并行技术，利用多个处理单元，将整个绘制任务合理地分成若干个子任务提供给若干个绘制单元分别进行绘制，最后将每个绘制单元得到的结果进行拼接或是合成得到最终的绘制结果，以达到负载均衡和加速绘制的目的。Pfister等[37]给出的Cube4系统是一个比较成功并行体系结构的设计，它能在30帧/秒速率下实现 512 级大小数据场的实时绘制, Knitel等[38]提出将体数据内存组织成 8个可同时访问的内存模块，以支持三线性插值计算中对8个相邻体素的同时存取。2010年等人在文献[39]采用的就是层次包围体加速结构"它将标准的光线跟踪算法分解为一些可以数据并行的多个阶段，采用的是广度优先遍法将这些并行阶段能有效地映射到GPU的并行结构上。

4总结和讨论

光线跟踪算法是计算机图形学中生成真实感图形的核心算法之一，它的研究和应用一直是计算机图形学研究的热点。本文着重论述了国内外体光线跟踪算法、加速的光线跟踪绘制技术等，并讨论了各自特点及其相互联系。目前，基于硬件加速的光线跟踪绘制技术应用越来越广泛，但是如何构造有效的数据结构以及高效的遍历算法一直是研究的重点，使这些数据结构和算法能够在硬件上达到优化配置，如何充分发挥图形硬件的功能、实时生成真实感强的图像将是今后的重点研究方向。随着强大的可编程性GPU高端图形卡的和并行可视化技术的不断发展，具有高度真实感的实时可视化技术将会应用得越来越广泛。

参考文献

[1] 张少帅. 真实感图形中光线跟踪算法及其加速技术的研究[D]. 西安电子科技大学, 2008. [2] 裴雪飞. 光线跟踪体绘制算法的研究[D]. 燕山大学, 2007. [3] 周鹏. 基于光线跟踪的真实感全局光照问题研究[D]. 山东大学, 2012. [4] Whitted T. A scan line algorithm for computer display of curved surfaces[J]. ACM SIGGRAPH Computer Graphics, 1978, 12(SI): 8-13. [5] 彭群生、鲍虎军、金小钢编著. 计算机真实感图形的算法基础[M]. 北京：科学出版社，1999，6 [6] 蔡勋, 曾亮, 刘光国. 光线跟踪方法在体绘制中的应用与发展[J]. 计算机工程与设计, 2009 (21): 4956-4959. [7] Robert Cook, Thomas Porter, and Loren Carpenter Distributed Ray Tracing. Computer Graphics (Proceeding of SIGGRAPH 84), 18(3):137-144, 1984. [8]Kajiya J T. The rendering equation[C]//ACM Siggraph Computer Graphics. ACM, 1986, 20(4): 143-150. [9]Mitchell D P. Spectrally optimal sampling for distribution ray tracing[J]. ACM SIGGRAPH Computer Graphics, 1991, 25(4): 157-164. [10]Walter B, Drettakis G, Parker S. Interactive rendering using the render cache[M]//Rendering techniques’ 99. Springer Vienna, 1999: 19-30. [11] Hachisuka T, Jarosz W, Weistroffer R P, et al. Multidimensional adaptive sampling and reconstruction for ray tracing[C]//ACM Transactions on Graphics (TOG). ACM, 2008, 27(3): 33. [12] Ward G J, Rubinstein F M, Clear R D. A ray tracing solution for diffuse interreflection[J]. ACM SIGGRAPH Computer Graphics, 1988, 22(4): 85-92. [13] Lafortune E P, Willems Y D. Bi-directional path tracing[C]//Proceedings of CompuGraphics. 1993, 93: 145-153. [14] Lafortune E P, Willems Y D. A 5D tree to reduce the variance of Monte Carlo ray tracing[M]//Rendering Techniques’ 95. Springer Vienna, 1995: 11-20. [15] Veach E, Guibas L J. Optimally combining sampling techniques for monte carlo rendering [C]. Computer Graphics Proceedings, Annual Conference Series, 1995: 419–428. [16] Veach E, Guibas L J. Metropolis light transport [C]. Computer Graphics Proceedings, SIGGRAPH 97, 1997: 65-76. [17] Möller T, Trumbore B. Fast, minimum storage ray-triangle intersection [J]. Journal of Graphics Tools, 1997, 2(1): 21-28. [18] Kajiya J T. Ray tracing parametric patches [J]. Computer Graphics, 1982, 16(3): 245-254. [19] Toth D L. On ray tracing parametric surfaces [J]. Computer Graphics, 1985, 19(3): 171-179. [20] Hanrahan P. Ray tracing algebraic surfaces [J]. Computer Graphics, 1983, 17(3): 83-90. [21] Hart J C, Sandin D J, Kauffman L H. Ray tracing deterministic 3-D fractals [J]. Computer Graphics, 1989, 23(3): 289-296. [22] Knoll A. Ray tracing implicit surfaces for interactive visualization. PhD Thesis, University of Utah, May 2009. [23] Heckbert P S, Hanrahan P. Beam tracing polygonal objects [J]. Computer Graphics, 1984, 18(3): 119-127. [24] Amanatides J. Ray tracing with cones [J]. Computer Graphics, 1984, 18(3): 129-135. [25] Reshetov A, Soupikov A, Hurley J. Multi-level ray tracing algorithm [J]. ACM Transactions on Graphics, 2005, 24(3): 1176-1185. [26] Moon B, Byun Y, Kim T-J, Claudio P, Kim H-S, Ban Y-J, Nam S W, Yoon S-Eui. Cache-oblivious ray reordering [J]. ACM Transactions on Graphics, 2010, 29(3): 1-10. [27]Mora B. Naive ray-tracing: A divide-and-conquer approach [J]. ACM Transactions on Graphics, 2011, 30(5): 1-12. [28] Hou Q M, Zhou K. A shading reuse method for efficient micropolygon ray tracing [J]. ACM Transactions on Graphics, 2011, 30(6): 1-8. [29] 柳有权, 张曼. 光线跟踪算法的加速技术研究[J]. 计算机与数字工程, 2013, 41(6): 863-865. [30] Purcell T J, Buck I, Mark W R, et al. Ray tracing on programmable graphics hardware[C]//ACM Transactions on Graphics (TOG). ACM, 2002, 21(3): 703-712. [31] Meiner M,Guthe S,Strasser W.Interactive lighting models and pre-integration for volume rendering on PC graphics accelera-tors[C].Proceedings of Graphics Interface,2002:209-218. [32]Kruger J, Westermann R. Acceleration techniques for GPU-based volume rendering[C]. Proceedings of IEEE Visualization, 2003:114-121. [33] 陈为,彭群生,鲍虎军.视点相关的层次采样:一种新的硬件加速体光线投射算法[J].软件学报, 2006,17(3):587-601. [34] Singh J M, Narayanan P J. Real-time ray tracing of implicit surfaces on the GPU[J]. Visualization and Computer Graphics, IEEE Transactions on, 2010, 16(2): 261-272. [35] Zhou K, Hou Q M, Wang R, Guo B N. Real-time KD-tree construction on graphics hardware [J]. ACM Transactions on Graphics, 2008, 27(5): 1-11. [36] Woop S, Schmittler J.RPU:A programmable ray processing unit for real time ray tracing[C].Proceedings of ACM SIGGRAPH, 2005:221-226. [37] Pfister H, Kreeger K A, Marks J W, et al. Temporal and spatial coherent ray tracing for rendering scenes with sampled and geometry data: U.S. Patent 6,556,200[P]. 2003-4-29. [38] Knittel J, Schnieder L, Buess G, et al. Endoscope-compatible nonlocal microscope using a gradient index-lens system[J]. Optics Communications, 2001, 188(5): 267-273. [39]Garanzha K, Loop C. Fast Ray Sorting and Breadth‐First Packet Traversal for GPU Ray Tracing[C] //Computer Graphics Forum. Blackwell Publishing Ltd, 2010, 29(2): 289-298.