家装设计软件中光线跟踪算法的加速方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利(10)授权公告号CN105117533B(45)授权公告日2018.05.22(21)申请号201510483861.4(56)对比文件(22)申请日2015.08.03CN101527052A,2009.09.09,CN102282591A,2011.12.14,(65)同一申请的已公布的文献号US2007/0182732A1,2007.08.09,申请公布号CN105117533A徐莉等.室内设计中的光照效果的多算法(43)申请公布日2015.12.02实现.《科技通报》.2015,第31卷(第1期),129-(73)专利权人常州赞云软件科技有限公司132.地址213022江苏省常州市新北区太湖东晋国涛.基于MapReduce的光线跟踪算法研路9-2号407室究.《中国优秀硕士学位论文全文数据库信息科技辑》.2012,(第10期),第3-6页.(72)发明人姜晓彤丁来平审查员谢琳(74)专利代理机构南京天翼专利代理有限责任公司32112代理人奚铭(51)Int.Cl.G06F17/50(2006.01)G06T15/06(2011.01)权利要求书2页说明书7页附图12页(54)发明名称家装设计软件中光线跟踪算法的加速方法(57)摘要家装设计软件中光线跟踪算法的加速方法，对光线跟踪算法进行了优化，将对光线跟踪算法的优化与GPU的硬件加速结合，通过CUDA编程实现优化过了的光线跟踪算法，并在支持递归的高档GPU，以及不支持递归的低档GPU上实现基于CUDA加速的光线跟踪算法，通过算法优化和GPU硬件加速的软硬件结合，用来加速光线跟踪算法的渲染。本发明充分发挥包围盒算法和空间剖分算法的优点，解决了光线与包围盒遍历的盲目性问题，方法简单，加速效果明显；本发明实现简单，避免了在CPU和GPU之间传递大量数据，充分利用了GPU自身的内存，为运行于CUDA上的光线跟踪算法等需要递归的算法提供了一个绝佳的实现方案。CN105117533BCN105117533B权利要求书1/2页1.家装设计软件中光线跟踪算法的加速方法，其特征是对光线跟踪算法进行优化，包括：1)减少递归次数：光线跟踪算法是递归的算法，需要递归计算反射/折射光线的颜色，如果像素颜色中的红绿蓝三原色的值都要比多次反射率或折射率的乘积大一百倍的时候，则自动终止光线的继续递归，实现加速；2)通过包围盒算法减少面片相交盲目性：在光线跟踪算法中，为了找到与光线相交最近的面片需要依次计算各面片与光线的交点，采用包围盒方法，用一个简单的几何体将一个物体的所有面片围起来形成一个整体，如果光线不与该包围盒相交，那么光线必然不会与包围盒内部的面片相交，只有当光线与包围盒相交时才需要计算光线与包围盒中面片是否相交，通过包围盒算法判断出必然不会与光线相交的面片，用于减少面片相交的计算；3)通过均匀空间剖分算法减少包围盒相交盲目性：均匀空间剖分方法将整个场景空间均分为八个子空间，坐标原点位于场景中心，各个子空间中包含数量不等的包围盒，沿着光线方向寻找与光线相交的子空间，根据光线的方向矢量，得出光线可能进入的子空间是哪几个，如果光线可能进入多个子空间，分别求出光线进入这几个子空间的距离，找出光线最先进入距离最近的子空间，在最近的子空间的包围盒内计算面片相交，寻找与光线相交最近的面片；优化后的光线跟踪算法的运行步骤如下七个步骤：1)构建场景并解析文件，在场景中放置物品，场景中的大部分物品都是3ds文件，渲染之前需要对3ds文件进行解析从而获取点线面以及纹理等信息；2)用包围盒将每一个3ds模型文件都围起来，包围盒采用的是球体；3)将整个场景空间均分成八个子空间，依次找到这八个子空间中的所有包围盒，构建三维矩阵s[2][2][2]，矩阵中存储的是指针，指向对应子空间中的包围盒；4)初始光线生成，各像素产生一条或多条初始光线，光线方向垂直屏幕射入场景；5)运行光线跟踪算法，找到光线经过的第一个空间，依次遍历其中包围盒，直到找到与光线交点最近的包围盒，遍历该包围盒中所有面片，找到与光线交点最近的面片，如果所有面片都不相交，就找到与光线相交的下一个包围盒，如果该空间中所有包围盒中的面片都不与光线相交，就找到与光线相交的下一个子空间，依此类推，直到找到与光线交点最近的面片，如果所有面片都不与光线相交，就返回背景色，该光线遍历结束；6)找到与光线最近的交点后，首先计算由漫反射、环境光产生的颜色值，若与光线相交的物体表面材质反射或折射光线，就生成新的折射、反射光线，递归计算该新的光线的颜色；如果光线射出场景、光线与光源相交、光线与完全漫反射物体相交、递归次数达到上限时停止递归，而且若新的光线对像素颜色值可忽略不计的时候也停止递归；7)将各像素的颜色值转化为计算机