计算机图形学入门20:加速光线追踪

1.前言

       前文说了Whitted-style光线追踪技术的原理以及光线与平面的交点计算方式,对于现在应用最广的Polygon Mesh显式曲面来说,一个复杂场景中的多边形面总数可能达到千万甚至亿万以上,如果每个像素发射光线都和场景中每个平面进行求交点计算,那么会进行像素数量 x 光线弹射次数 x 多边形平面数量次光线与平面交点计算,计算会非常庞大,非常慢。

        例如下图中的经典场景San Miguel,面数达到10.7M,渲染一张1080P图片,光线平均3次弹射,共需要进行66万亿次交点计算。

        这样庞大的计算量是完全不能接受的,而一条光线在场景中弹射时和绝大多数平面是不会相交的,因此需要通过一些算法进行优化,这个算法就是包围盒技术(Bounding Box)

2.轴对齐包围盒(Axis-Aligned Bounding Box)

        用简单的方盒子称为包围盒(Bounding Box)将物体完全包裹,如果光线与包围盒没有交点,那显然不会与物体中任何三角面有交点,那也就没必要去遍历物体的三角面了。

        在几种包围盒方式中,AABB即轴对齐包围盒因为包围盒三组对面分别与三个空间坐标轴平行,便于计算而使用最为广泛(下图中间)。

        那么AABB包围盒就可以理解为三个不同的对面形成的交集,这样可以方便进行光线与包围盒的求交运算。如下图所示。

        那么到底如何求光线与包围盒的交点呢?先将问题简化成直线与x_{0}x_{1}y_{0}y_{1}两对平面的交点,将三维转化成二维。

        如上图最左边所示,求光线与一对 平面(左右无限远)的交点,将先进入的交点(距离光线起点 最近的那个)记为 tmin,后出去的交点记为 tmax。紧接着如中间图所示计算出光线与 平面(上下无限远)的两个交点同样记为另外一组 tmin, tmax注意:如果任意的 t < 0,那么这代表的是光线反向传播与对应平面的交点。

        那么如何知道光线在什么时候进入盒子,又在什么时候出去了盒子呢?

        对于二维来说,如上图最右边所示,在 tmin 时间进入了盒子,在 tmax 时间出去了盒子。这实际就是求两组交点构成的线段的交集。那么这个结论是怎么得出的呢?

        回想三维的情况,三维的盒子就是三个对面,最重要的核心思想:

        1.只有当光线进入了所有的平面才算是真正进入了盒子中。

        2.只要当光线离开了任意平面就算是真正离开了盒子。

        那么,就可以得到一种算法,在三维中三组不同的对面各计算一次进入对面的最小时间 tmin 和离开对面最大时间 tmax ,时间不管是正还是负。最后算出三对进入和离开对面的时间交集,就得出了进入盒子时间 t_{enter}和离开盒子时间 t_{exit}。如下图所示。

        但光线不一定会与包围盒有交点,那么什么条件下才会有交点呢?

        如果 t_{enter}< t_{exit} 的时候,说明光线所在直线一定在盒子中待过一段时间,也必然存在交点。但光线并不是直线,而是射线,除了保证t_{enter}< t_{exit}(光线在盒子待过一段时间),还要考虑时间 t 是否为负,保证物理正确性。具体如下:

        1.如果 t_{exit}< 0,说明包围盒在光线背后,就不会有交点。

        2.如果 t_{exit}>= 0 并且 t_{enter}< 0,说明光线是从包围盒内发射出来的,就有一个交点。

        3.如果 t_{exit}>= 0 并且 t_{enter}>= 0,说明包围盒在光线前面,有两个交点。

        因此,只要满足 t_{enter}< t_{exit} 并且 t_{exit}>= 0 ,光线就一定和包围盒有交点。

        根据前文中光线与平面的交点算法,光线和包围盒的求交也很容易写出,如下图下半部分所示。

        以一对 轴的平面为例,两个平面肯定垂直于 轴,因此可以直接求光线在 轴方向的分量,代入公式从而直接得到 值,计算过程比光线与任意平面交点的算法要快速得多,这也是AABB包围盒得到广泛使用的原因。

3.使用AABB加速光线追踪

3.1 AABB划分方法

        虽然对场景中的每个物体使用AABB包围盒技术已经可以大幅加快光线追踪效率,但实际使用中难免遇到以下两种极端情况:

  • 整个场景主要只有一个极其复杂的单一模型,那么只对这一个物体做包围盒的话,相当于对效率没有提升。
  • 整个场景充斥着大量的细小模型,如植物、建筑之类的,每个模型可能只有很少的面,如果此时对每个物体求包围盒,得到的包围盒数量会非常多,效率提升有限。

        基于以上两点考虑,AABB不应只局限于以物体模型为单位,可以更加精细的划分成以一定数量的三角面为单位,并且对于场景的许许多多包围盒来说应该要有一种数据结构将其统一起来。

        因此为了更好地划分场景形成不同的AABB,使得划分之后的AABB能够更好的加速光线追踪,在AABB的基础上出现了多种划分方法。

3.2 均匀网格划分(Uniform Grids Partitions)

3.2.1 步骤和定义

        先从最简单的均匀网格划分开始。步骤如下。

        1.创建一个包裹整个场景的大包围盒。如下图所示。

        2.在大包围盒中创建均匀分布的网格。如下图所示。

        3.将每个物体对象存储在重叠的单元格中。判定哪些小方格有物体信息,也就是与物体表面相交的小方格。注意:下图中右上角没涂对。

        以上就是在光线追踪之前进行了预处理,然后就可以进行光线追踪了。在光线追踪计算时,根据光线的方向找到所有相交的小方格,倘若小方格中存储有物体,再进一步与方格中的物体模型或是三角形面求交(假设光线与小方格求交是很快的,与物体求交比较慢)。如下图所示。

        均匀网格划分将空间划分为多个均匀的小的AABB,再根据光线方向找出相交的小方格(这一步并不需要判断所有方格,可以用类似brenham的方法来做),再判断小包围盒中是否存储了模型信息,若有则进一步求交。

3.2.2 网格分辨率影响

        这种划分方法假设了找出相交方格要比直接判断与物体求交相对容易,因此划分方格数的数量也是影响性能的关键,方格太少就没有加速效果,方格太多则判断与方格的求交可能会拖累效率。如下图所示,左侧是方格只有一个,没有加速效果,而右侧是方格太过密集,反而增加了判断影响效率。

        所以网格的数量(分辨率)应该有一个平衡,不能太稀疏也不能太密集。

        所以这种方法最适合的场景就是大型对象集合,并且大小在空间中均匀分布。如下图这种场景。

        如果场景较为空旷,物体较小且相互距离较远,那么均匀分割的效果就会很差了,因为会有很多无效的方格与光线的求交过程。

3.3 空间划分(Spatial Partitions)

3.3.1 定义

        均匀网格划分适合场景中密集且均匀分布,那么当场景中存在大量空白区域就不适合了。所以就需要使用空间划分,密集的区域用小方格,空白区域用大方格。

3.3.2 分类

        空间划分主要有Oct-Tree、KD-Tree以及BSP-Tree等划分方法。如下图所示。注意:这些划分在2D和3D中都可以使用,以下以2D为例。

        1.Oct-Tree也就是八叉树,每次将空间分为8个相等的部分(三维空间横竖平各切一刀,因为图中是二维显示,所以看起来只划分了4部分),再递归的对子空间进行划分。当划分的子空间足够小或是空间中三角形面的数量很少的时候会停止划分。这种方法的显著缺点是,随着维度的上升划分的空间数量会呈指数级增长。

        2.KD-Tree其每次将空间划分为两部分,且划分依次沿着 x 轴,轴,轴,即如图中所示。第一次横着将二维空间分为上下,第二次再竖着将上下两个子空间分别划分为左右部分,依次交替划分,划分时不是按空间大小而是按模型数量或者三角形数量进行均匀划分,终止条件与八叉树类似。

        3.BSP-Tree其与KD-Tree类似,唯一不同的是划分不再沿着固定一轴,可以任意方向划分。缺点自然是划分的空间没有规则性,求交比较困难。

        同样,空间划分也是在光线追踪之前进行预计算。

        接下来从一个例子具体介绍KD-Tree。

3.3.3 详解KD-Tree

3.3.3.1 划分过程

        1.空间分为左右两部分。如下图所示。

        2.对左右两个子空间换个方向再分为两部分(这里为方便展示,只画出了右半部分,其实左边也是一样)。如下图所示。

        3.如此递归的划分下去,如下图所示。

3.3.3.2 KD-Tree的数据结构

        通过上述划分之后中遵循这样几点。

           1 依次沿着x轴,y轴,z轴划分,使得空间被划分的更加平衡。

           2 划分的位置由空间中三角面的分布决定,具体细节不展开。

           3 叶子节点存储对应空间的所有物体或三角面信息,中间节点仅存储指针指向两个子空间。

           4 当划分空间太小或是子空间内只有少量三角形则停止划分。

        当KD-Tree建立完成之后,如何进行光线与物体求交判断呢?

3.3.3.3 求光线与物体交点

        如下图所示,假设有一条光线进入场景,里面的圆圈代表物体。那么如何去计算光线与物体的交点呢?

        1.判断光线是否与最外层的包围盒(A)相交。如下图所示。

        2.如果相交,则进一步判断是否与对应的两个子包围盒相交。

        上图是为了显示方便,所以左侧没有进行进一步的显示划分情况,实际会继续划分下去的,所以左半部分对应的 1号空间是叶子节点,如果光线与之相交,进一步判断与存储与叶子节点的所有物体求交。左半边判断完之后,接着判断右半部分,显然光线与左右两侧包围盒都相交。

        对于左右两侧的所有子包围盒,递归的执行这个步骤即可。

        更加详细的过程就不再赘述。

3.3.3.4 优缺点

        优点: 

        利用KD-Tree的结构来构建AABB的好处是倘若光线与哪一部分空间不相交,那么则可以省略该部分空间所有子空间的判断过程,在原始的纯粹的AABB之上更进一步提升了加速效率。

        缺点: 

        1.判断包围盒与三角面的是否相交较难,因此划分的过程不是那么想象的简单。

        2.其次同一个三角面可能被不同的包围盒同时占有,这两个不同包围盒内的叶节点会同时存储这一个三角形面。

        基于KD-Tree的以上两个缺点,这种方法渐渐地不再被广泛使用。

3.4 对象划分(Object Partitions)

3.4.1 BVH对象划分

        对象划分与前几种方法最显著的区别就是,不再以空间作为划分依据,而是从对象的角度考虑,即三角形面。而这种划分形成的加速结构就称为BVH对象划分(Bounding Volume Hierarchy Object Partitions)。

        BVH对象划分得到非常广泛的应用。在现代图形学里无论是实时的光线追踪,还是离线的光线追踪,几乎都使用了这种方法,因为它解决了KD-Tree的两个缺点。

        具体划分步骤如下。

        1.找出场景的整体包围盒作为根节点。

        2.找到合适的划分点,将最大包围盒内的三角形面分为两部分,再分别重新计算新的包围盒。

        注意:包围盒会重叠,但一个三角形面只会被存储在唯一的包围盒内,而这也就解决了KD-Tree的缺点。

        3.接下来与KD-Tree的建立类似,递归的对所有子空间重复该步骤。

        最终可以建立出如上图的所示的树形结构,同样为了画图方便,只进行了左半部分的划分,右半部分其实同理。

        划分细节:每次划分一般选择最长的那一轴划分,假设是x轴,那么划分点选择所有三角面的重心坐标在x坐标上的中位数进行划分(快速选择算法找中位数),如此便能保证划分的三角形左右两边三角形数量尽可能差不多。当然也就使得树形结构建立的更加平衡,深度更小,平均搜索次数更少,提高效率

        而与KD-Tree一样,中间节点不存储物体三角面信息,只在叶节点中存储,划分终止条件为当前包围盒内三角形数量足够少(例如5个)。

        光线与物体求交点与KD-Tree求交点是一样的,如下图伪代码所示。

3.5 空间划分与对象划分的区别

        空间划分(如kd -tree)

                1.将空间划分为不重叠的区域。

                2.一个对象可以包含在多个区域。

        对象划分(如BVH)

                1.将对象的集合划分为不相交的子集。

                2.每个集合的边界框在空间上可能重叠。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/361271.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

关于WebSocket

WebSocket 与传统的 HTTP 协议对比 在实时通信领域&#xff0c;传统的 HTTP 协议存在以下一些问题&#xff1a; 频繁的请求和响应&#xff1a;每次通信都需要建立和关闭连接&#xff0c;带来额外的开销。高延迟&#xff1a;每次通信都需要经过多个网络层的传输&#xff0c;延…

Android焦点机制结合WMS

文章前提&#xff1a; 了解WMS基本作用了解window的概念&#xff0c;phoneWindow&#xff0c;rootViewImpl了解view的事件分发 开始&#xff1a; 讲三件事情&#xff1a; window的创建&#xff0c;更新焦点的更新事件的分发 Window的创建&#xff0c;更新&#xff1a; wi…

完整代码Python爬取豆瓣电影详情数据

完整代码Python爬取豆瓣电影详情数据 引言 在数据科学和网络爬虫的世界里&#xff0c;豆瓣电影是一个丰富的数据源。在本文中&#xff0c;我们将探讨如何使用Python语言&#xff0c;结合requests和pyquery库来爬取豆瓣电影的详情页面数据。我们将通过一个具体的电影详情页面作…

农村经济与科技杂志社农村经济与科技编辑部2024年第8期目录

视点 数字经济驱动农业产业链升级路径研究——以河南省为例 王媛媛; 1-4 城乡融合视角下农村集体产权制度改革研究 齐建丽; 4-7 农业生态系统结构美建设内涵及实现路径 张鹏程; 8-13《农村经济与科技》投稿&#xff1a;cnqikantg126.com 农户宅基地退出政策加权…

【C++】——二叉搜索树(详解)

一 二叉搜索树概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树: ✨若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值 ✨若它的右子树不为空&#xff0c;则右子树上所有节点的值都大于根节点的值 …

在数字化转型中,数字孪生技术的作用和价值几何?

引言&#xff1a;随着全球化和市场竞争的加剧&#xff0c;企业需要通过数字化转型来提高生产效率、优化产品质量、降低成本&#xff0c;以增强自身竞争力。企业需要通过数字化转型更好地理解客户需求&#xff0c;提供个性化、定制化的产品和服务&#xff0c;从而满足客户的多样…

Axios-入门

介绍 Axios对原生Ajax进行了封装&#xff0c;简化书写&#xff0c;快速开发 官网&#xff1a;Axios中文文档 | Axios中文网 (axios-http.cn) 入门 1引入Axios的js文件 <script src"js/axios.js"></script> 2使用Axios发送请求&#xff0c;并获取响应…

链式队列算法库构建

学习贺利坚老师课程,构建链式队列算法库 数据结构之自建算法库——链队&#xff08;链式队列&#xff09;_数据结构函数链队列的算法框架有哪些-CSDN博客文章浏览阅读6.2k次&#xff0c;点赞3次&#xff0c;收藏9次。本文针对数据结构基础系列网络课程(3)&#xff1a;栈和队列…

在win7系统电脑安装node16的版本(已成功安装运行)

很多银行的项目行方都要求内网开发&#xff0c;但是我遇到的几个银行基本都是win7系统的电脑&#xff0c;而前端的项目又是需要高版本的node才能跑起来&#xff0c;所有就记录此解决方案文章&#xff01; 这是下载node安装包的地址&#xff1a;Index of /dist/ 在这里先下载自…

树形结构的勾选、取消勾选、删除、清空已选、回显、禁用

树形结构的勾选、取消勾选、删除、清空已选、回显、禁用 基本页面&#xff1a; 分为上传文件和编辑的页面 代码实现要点&#xff1a; 上传文件页面&#xff1a; 点开选择范围弹窗&#xff0c;三个radio单选框都为可选状态&#xff0c;默认显示的是第一个单选框&#xff08;按…

晶方科技:台积电吃饱,封装迎春?

半导体产业链掀起涨价潮&#xff0c;先进封装迎接利好。 这里我们来聊国内先进封装企业——晶方科技。 近期&#xff0c;由于产能供不应求&#xff0c;台积电决定上调先进封装产品价格&#xff0c;还表示订单已经排到2026年。 大哥吃不下了&#xff0c;剩下的订单全都是空间。…

Shell编程规范与变量-01

一、Shell脚本概述 在一些复杂的 Linux 维护工作中&#xff0c;大量重复性的输入和交互操作不仅费时费力&#xff0c;而且容易出错&#xff0c;而编写一个恰到好处的 Shell 脚本程序&#xff0c;可以批量处理、自动化地完成一系列维护任务&#xff0c;大大减轻管理员的负担。 1…

在Ubuntu上安装Python3

安装 python3 pip sudo apt -y install python3 python3-pip升级 pip python3 -m pip install --upgrade pip验证查看版本 python3 --version

web渗透-SSRF漏洞及discuz论坛网站测试

一、简介 ssrf(server-side request forgery:服务器端请求伪造&#xff09;是一种由攻击者构造形成由服务端发起请求的一个安全漏洞。一般情况下&#xff0c;ssrf是要目标网站的内部系统。(因为他是从内部系统访问的&#xff0c;所有可以通过它攻击外网无法访问的内部系统&…

excel字符串列的文本合并

excel表有两列&#xff0c;第一列是“姓名”&#xff0c;第二列是“诊断”&#xff0c;有高血压、糖尿病等。我想出一个统计表&#xff0c;统计“姓名”&#xff0c;把某一个姓名的诊断不重复的用、拼接起来&#xff0c;比如“张三”的诊断为“点高血压”、糖尿病。我们可以用T…

适用于轨道交通专用的板卡式网管型工业以太网交换机

是网管型 CompactPCI板卡式冗余环网交换机。前面板带有6个 10/100/1000Base-T(X)M12接口。后面的CPCI接口有 8个10/100/1000Base-T (X) 以太网接口。 是特别为轨道交通行业EN50155标准要求而设计的坚固型交换机。它同时具有以下特性&#xff1a; ● 支持2线以太网距离扩展端口&…

springcloud第4季 springcloud-alibaba之nacos+openfegin+gateway+sentinel熔断限流【经典案例】

一 说明 1.1 架构说明 本案例实现原理&#xff1a; 采用alibaba的nacos&#xff0c;openfegin&#xff0c;sentinel&#xff0c;gateway等组件实现熔断限流。 主要理解sentinel的ResouceSentinel和fallback的区别联系。 ResourceSentinel 主要是页面配置熔断限流规则&#…

试析C#编程语言的特点及功能

行步骤&#xff0c;而不必创建新方法。其声明方法是在实例化委托基础上&#xff0c;加一对花括号以代表执行范围&#xff0c;再加一个分号终止语句。 2.3.3 工作原理 C#编译器在“匿名”委托时会自动把执行代码转换成惟一命名类里的惟一命名函数。再对存储代码块的委托进行设…

【干货】Vue3 组件通信方式详解

前言 毫无疑问&#xff0c;组件通信是Vue中非常重要的技术之一&#xff0c;它的出现能够使我们非常方便的在不同组件之间进行数据的传递&#xff0c;以达到数据交互的效果。所以&#xff0c;学习组件通信技术是非常有必要的&#xff0c;本文将总结Vue中关于组件通信的八种方式…

【博士每天一篇文献-算法】Fearnet Brain-inspired model for incremental learning

阅读时间&#xff1a;2023-12-16 1 介绍 年份&#xff1a;2017 作者&#xff1a;Ronald Kemker&#xff0c;美国太空部队&#xff1b;Christopher Kanan&#xff0c;罗切斯特大学 期刊&#xff1a; arXiv preprint 引用量&#xff1a;520 Kemker R, Kanan C. Fearnet: Brain-…