复数的物理意义

原文地址:https://www.zhihu.com/question/23234701/answer/26017000

复数最直观的理解就是旋转!

4*i*i = -4

就是“4”在数轴上旋转了180度。

那么4*i就是旋转了90度。

另外,e^t是什么样呢?

但当你在指数上加上i之后呢?

变成了一个螺旋线。是不是和电磁场很像?(想拿欧拉公式去跟女生炫学术的男生注意了:她们,真的,不CARE)

当然,更重要的意义在于复数运算保留了二维信息。

假如我让你计算3+5,虽然你可以轻松的计算出8,但是如果让你分解8你会有无数种分解的方法,3和5原始在各自维度上的信息被覆盖了。
但是计算3+5i的话,你依然可以分解出实部和虚部,就像上图那样。

基于以上两个理由,用复数来描述电场与磁场简直完美到爆棚!
我们即可以让电场强度与复数磁场强度相加而不损失各自的信息,又满足了电场与磁场90度垂直的要求。另外,一旦我们需要让任何一个场旋转90度,只要乘一个“i”就可以了

正弦波在频域可以看作是自然数中的“1”,可以构成其他数字的基础元素。当你需要5的时候,你可以看成是1*5(基础元素的五倍)也看以看成2+3(一个基础元素2倍与基础元素3倍的和)。这些用基础元素构成新元素的运算是线性运算。
但是现在你如何用线性运算吧2sin(wt)变换成4sin(wt+pi/6)呢?

利用欧拉公式,我们可以将任何一个正弦波看作其在实轴上的投影。假如两个不同的正弦波,可以用数学表达为:

好了,现在如果我想用第一个正弦波利用线性变换为第二个,我们就只需要将A乘对应的系数使其放大至B(本例为乘2),然后将θ1加上一定的角度使其变为θ2(本例为加30度),然后将得到的第二个虚数重新投影回实轴,就完成了在实数中完全无法做到的变换。

这种利用复指数来计算正弦波的方法也对电磁波极其适用,因为电磁波都是正弦波,当我们需要一个电磁波在时间上延迟/提前,或是在空间上前移/后移,只需要乘一个复指数就可以完成对相位的调整了。

———————————————————————————–

复数不仅有意义,而且可以用图示来优雅地解释。

1、实函数与数轴变换

[公式]

大家都认识y=e^x,对于这样的初等函数,我们从小就学会使用直角坐标系来刻画它们:


它们的特点都大同小异:把实数轴对应到实数轴。然而,既然是一维函数,用二维图像来描述未免太过奢侈。如果我们把数轴涂上不同颜色,再把一条新数轴上对应的函数值涂上相应颜色,就可以清晰地用数轴-数轴对应来展示函数这一关系:

可以发现每个函数的作用无非是在有些地方把数轴往中间压了压,在有些地方又把数轴往两边扯了扯(观察图中小棒棒之间的间距是变窄还是变宽):

  • e^x越往左越挤压数轴,越往右越拉伸数轴
  • x^2离0越远,对数轴的拉伸越厉害(在图上左半边图像和右半边图像重叠在了一起)。如果有一个小球在实数轴上向右滑行,那么它的像则先向左滑行到0,然后再向右滑行。
  • x^3离0越远,对数轴的拉伸比楼上更厉害,但是不同的是,向右滑行的小球的像也一直向右滑行。

是挤压还是拉伸,就看函数在那一点的导数的绝对值是小于1还是大于1。因此导数大小的意义就是局部小区间在变换下的伸缩倍数。导数正负符号的意义是小区间是否反向,比如第二个函数x^2在x小于0时导数也小于零,那么指向右方的数轴负数部分经过变换指向了左方。

2. 复数与平面变换
既然可以用上面的数轴-数轴对应来描述一维函数,那么类似地,就可以用平面-平面对应来描述二维函数。我们用一个复数表示平面上的点,用字母i区分纵坐标,就可以来研究复数函数w=f(z)的性质,其中z=x+iy,w=u+iv。假设我们已经默认了复数的运算:

  • 加法:z+w=(x+u)+i(y+v)
  • 乘法:zw=(xu-yv)+i(xv+yu)
  • 极坐标分解:z=re^it=rcos(t)+i*rsin(t),其中r是复数代表的平面向量到原点的距离,t是和横轴正方向的夹角。

拿出一个涂色的平面网格(从左上开始逆时针依次涂成红黄蓝绿色),把每个网点的像算出来,按顺序连起来,就可以来研究复函数了。

2.1. 复数的加法:

  • 从图中可知,加法就是平面的平移,平移量恰好是那个复数对应的平面向量。

2.2 复数的乘法:

根据上面的运算法则很容易得到函数w=iz的二维对应关系是[x,y]=>[-y,x],画在图上就是:

仔细看可以发现,各点乘以i的效果是平面逆时针旋转了90度,也就是

[公式]

弧度。

各点乘以e^it的后果是平面逆时针旋转t弧度,这里是30度。

乘以一个一般的复数,就是把整个平面按它对应的角度旋转t弧度,再均匀放大r倍。

因此,复数的加法就是自变量对应的平面整体平移,复数的乘法就是平面整体旋转和伸缩,旋转量和放大缩小量恰好是这个复数对应向量的夹角和长度。二维平移和缩放是一维左右平移伸缩的扩展,旋转是一个至少要二维才能明显的特征,限制在一维上,只剩下旋转0度或者旋转180度,对应于一维导数正负值(小线段是否反向)。

3. 复变函数与伸缩旋转

如果在每一个点处的旋转、放缩和平移量都不同(导数不同),就可以得到比较复杂的复数函数,举个例子:

3.1 

w=e^z

e^z=e^(x+iy)=e^x+e^iy,从上一小节的知识可知,e^z的作用就是把平面上每个点按自己对应的坐标放大e^x倍、旋转y弧度。我们立即可以猜测这个函数在x较大的地方放大的倍数更多,因为放大率e^x更大;在x轴上只伸缩不旋转,因为没有e^iy旋转分量;在y轴上只旋转不伸缩,因为没有e^x放缩分量:

  • 请看左图中的横向中轴,它在右图中的像也是横向中轴,只不过左边压缩,右边扩展,这正是我们一开始就提到的一维指数函数。而这个图,恰好就是一开始那个数轴-数轴对应朝两边扩展形成平面-平面对应的结果
  • 再请看左图中的竖直中轴,它在右图发生了弯曲,贴在了单位圆周上,因此变成了一系列纯旋转的复数乘子。这一点在一维中可完全没有类似物,请谨慎类比。
  • 其他点介于纯粹旋转和纯缩放之间。最后,请你回过头再仔细看看这幅图,你会发现这几段话也适用于图中的每个小正方形。小正方形变换前后的旋转和伸缩比例对应于函数的导数,本例中函数的导数就是原函数自己。

3.2. w=z^3+10

  • 加10就是整体向右平移10个单位,可以最后再看。
  • 咱们来看w=z^3,令z=re^it,可以得到:w=r^3e^i*3t,这说明单位圆以内(r<1)函数压缩,单位圆以外(r>1)函数拉伸,离原点越远拉伸越厉害,正方形网格应该越来越大。
  • 原正方形的四个彩色顶点的角度是135、225、315和45度,分别乘以3再取余360到[0,360]度之间变成45、315、225、135。因此正方形的像从左上逆时针看颜色从红黄蓝绿变成了绿蓝黄红。

图像也和上面的分析完全吻合:

举上面两个例子是想向大家展示伸缩和旋转是优雅地解释复数的有力工具。

4. 复变函数和小正方形
接着我们随便看几个复数函数对应的平面变换图像:

漂亮吧,但是且慢!为什么第二个函数图像比较丑?因为二维函数很复杂,有一小类二维函数的变量之间具有一定关系,导致的结果是虽然整体变换多姿多彩,但是如果只观察局部,这些函数一定把足够小的小正方形变成小正方形,不会压扁它或拆散它,只不过平面不同地方小正方形放缩和旋转程度不同。第二个函数就不属于这种特殊的函数类。

这种性质很好,图像很美的函数称为解析函数,它的变量之间的联系称为柯西黎曼方程,局部小正方形的放缩和旋转幅度恰好等于这个复函数在那一点的导数值(和第一段一维函数的原理极其类似,在那里一维导数用来刻画伸缩和左右方向)。简单的一维函数,可以唯一地向两边扩展成为对应的复解析函数。

如果把初始的正方形网格用极坐标进行参数化,解析函数仍然把小正方形变换为小正方形,与上图对应的图像为:

以后看到复变(准确地说是解析)函数,可要记得它们的本质是对平面局部做旋转和缩放,但保持小正方形形状不变。而一个复数就是一个能把平面进行均匀缩放和旋转的乘子。最后,请记得我的彩色正方形!

傅里叶分析之掐死教程(完整版)

作者:韩昊
原文地址:https://zhuanlan.zhihu.com/p/19763358

知 乎:Heinrich

微 博:@花生油工人

知乎专栏:与时间无关的故事

谨以此文献给大连海事大学的吴楠老师,柳晓鸣老师,王新年老师以及张晶泊老师。

转载的同学请保留上面这句话,谢谢。如果还能保留文章来源就更感激不尽了。

——更新于2014.6.6,想直接看更新的同学可以直接跳到第四章————

我保证这篇文章和你以前看过的所有文章都不同,这是12年还在果壳的时候写的,但是当时没有来得及写完就出国了……于是拖了两年,嗯,我是拖延症患者……

这篇文章的核心思想就是:

要让读者在不看任何数学公式的情况下理解傅里叶分析。

傅里叶分析不仅仅是一个数学工具,更是一种可以彻底颠覆一个人以前世界观的思维模式。但不幸的是,傅里叶分析的公式看起来太复杂了,所以很多大一新生上来就懵圈并从此对它深恶痛绝。老实说,这么有意思的东西居然成了大学里的杀手课程,不得不归咎于编教材的人实在是太严肃了。(您把教材写得好玩一点会死吗?会死吗?)所以我一直想写一个有意思的文章来解释傅里叶分析,有可能的话高中生都能看懂的那种。所以,不管读到这里的您从事何种工作,我保证您都能看懂,并且一定将体会到通过傅里叶分析看到世界另一个样子时的快感。至于对于已经有一定基础的朋友,也希望不要看到会的地方就急忙往后翻,仔细读一定会有新的发现。

————以上是定场诗————

下面进入正题:

抱歉,还是要啰嗦一句:其实学习本来就不是易事,我写这篇文章的初衷也是希望大家学习起来更加轻松,充满乐趣。但是千万!千万不要把这篇文章收藏起来,或是存下地址,心里想着:以后有时间再看。这样的例子太多了,也许几年后你都没有再打开这个页面。无论如何,耐下心,读下去。这篇文章要比读课本要轻松、开心得多……

p.s.本文无论是cos还是sin,都统一用“正弦波”(Sine Wave)一词来代表简谐波。

一、什么是频域

从我们出生,我们看到的世界都以时间贯穿,股票的走势、人的身高、汽车的轨迹都会随着时间发生改变。这种以时间作为参照来观察动态世界的方法我们称其为时域分析。而我们也想当然的认为,世间万物都在随着时间不停的改变,并且永远不会静止下来。但如果我告诉你,用另一种方法来观察世界的话,你会发现世界是永恒不变的,你会不会觉得我疯了?我没有疯,这个静止的世界就叫做频域。

先举一个公式上并非很恰当,但意义上再贴切不过的例子:

在你的理解中,一段音乐是什么呢?

这是我们对音乐最普遍的理解,一个随着时间变化的震动。但我相信对于乐器小能手们来说,音乐更直观的理解是这样的:

好的!下课,同学们再见。

是的,其实这一段写到这里已经可以结束了。上图是音乐在时域的样子,而下图则是音乐在频域的样子。所以频域这一概念对大家都从不陌生,只是从来没意识到而已。

现在我们可以回过头来重新看看一开始那句痴人说梦般的话:世界是永恒的。

将以上两图简化:

时域:

频域:

在时域,我们观察到钢琴的琴弦一会上一会下的摆动,就如同一支股票的走势;而在频域,只有那一个永恒的音符。

所以

你眼中看似落叶纷飞变化无常的世界,实际只是躺在上帝怀中一份早已谱好的乐章。

抱歉,这不是一句鸡汤文,而是黑板上确凿的公式:傅里叶同学告诉我们,任何周期函数,都可以看作是不同振幅,不同相位正弦波的叠加。在第一个例子里我们可以理解为,利用对不同琴键不同力度,不同时间点的敲击,可以组合出任何一首乐曲。

而贯穿时域与频域的方法之一,就是传中说的傅里叶分析。傅里叶分析可分为傅里叶级数(Fourier Serie)和傅里叶变换(Fourier Transformation),我们从简单的开始谈起。

二、傅里叶级数(Fourier Series)的频谱

还是举个栗子并且有图有真相才好理解。

如果我说我能用前面说的正弦曲线波叠加出一个带90度角的矩形波来,你会相信吗?你不会,就像当年的我一样。但是看看下图:

第一幅图是一个郁闷的正弦波cos(x)

第二幅图是2个卖萌的正弦波的叠加cos(x)+a.cos(3x)

第三幅图是4个发春的正弦波的叠加

第四幅图是10个便秘的正弦波的叠加

随着正弦波数量逐渐的增长,他们最终会叠加成一个标准的矩形,大家从中体会到了什么道理?

(只要努力,弯的都能掰直!)

随着叠加的递增,所有正弦波中上升的部分逐渐让原本缓慢增加的曲线不断变陡,而所有正弦波中下降的部分又抵消了上升到最高处时继续上升的部分使其变为水平线。一个矩形就这么叠加而成了。但是要多少个正弦波叠加起来才能形成一个标准90度角的矩形波呢?不幸的告诉大家,答案是无穷多个。(上帝:我能让你们猜着我?)

不仅仅是矩形,你能想到的任何波形都是可以如此方法用正弦波叠加起来的。这是没
有接触过傅里叶分析的人在直觉上的第一个难点,但是一旦接受了这样的设定,游戏就开始有意思起来了。

还是上图的正弦波累加成矩形波,我们换一个角度来看看:

在这几幅图中,最前面黑色的线就是所有正弦波叠加而成的总和,也就是越来越接近矩形波的那个图形。而后面依不同颜色排列而成的正弦波就是组合为矩形波的各个分量。这些正弦波按照频率从低到高从前向后排列开来,而每一个波的振幅都是不同的。一定有细心的读者发现了,每两个正弦波之间都还有一条直线,那并不是分割线,而是振幅为0的正弦波!也就是说,为了组成特殊的曲线,有些正弦波成分是不需要的。

这里,不同频率的正弦波我们成为频率分量。

好了,关键的地方来了!!

如果我们把第一个频率最低的频率分量看作“1”,我们就有了构建频域的最基本单元。

对于我们最常见的有理数轴,数字“1”就是有理数轴的基本单元。

时域的基本单元就是“1秒”,如果我们将一个角频率为的正弦波cos(t)看作基础,那么频域的基本单元就是。

有了“1”,还要有“0”才能构成世界,那么频域的“0”是什么呢?cos(0t)就是一个周期无限长的正弦波,也就是一条直线!所以在频域,0频率也被称为直流分量,在傅里叶级数的叠加中,它仅仅影响全部波形相对于数轴整体向上或是向下而不改变波的形状。

接下来,让我们回到初中,回忆一下已经死去的八戒,啊不,已经死去的老师是怎么定义正弦波的吧。

正弦波就是一个圆周运动在一条直线上的投影。所以频域的基本单元也可以理解为一个始终在旋转的圆

介绍完了频域的基本组成单元,我们就可以看一看一个矩形波,在频域里的另一个模样了:

这是什么奇怪的东西?

这就是矩形波在频域的样子,是不是完全认不出来了?教科书一般就给到这里然后留给了读者无穷的遐想,以及无穷的吐槽,其实教科书只要补一张图就足够了:频域图像,也就是俗称的频谱,就是——

再清楚一点:

可以发现,在频谱中,偶数项的振幅都是0,也就对应了图中的彩色直线。振幅为0的正弦波。

老实说,在我学傅里叶变换时,维基的这个图还没有出现,那时我就想到了这种表达方法,而且,后面还会加入维基没有表示出来的另一个谱——相位谱。

但是在讲相位谱之前,我们先回顾一下刚刚的这个例子究竟意味着什么。记得前面说过的那句“世界是静止的”吗?估计好多人对这句话都已经吐槽半天了。想象一下,世界上每一个看似混乱的表象,实际都是一条时间轴上不规则的曲线,但实际这些曲线都是由这些无穷无尽的正弦波组成。我们看似不规律的事情反而是规律的正弦波在时域上的投影,而正弦波又是一个旋转的圆在直线上的投影。那么你的脑海中会产生一个什么画面呢?

我们眼中的世界就像皮影戏的大幕布,幕布的后面有无数的齿轮,大齿轮带动小齿轮,小齿轮再带动更小的。在最外面的小齿轮上有一个小人——那就是我们自己。我们只看到这个小人毫无规律的在幕布前表演,却无法预测他下一步会去哪。而幕布后面的齿轮却永远一直那样不停的旋转,永不停歇。这样说来有些宿命论的感觉。说实话,这种对人生的描绘是我一个朋友在我们都是高中生的时候感叹的,当时想想似懂非懂,直到有一天我学到了傅里叶级数……

三、傅里叶级数(Fourier Series)的相位谱

上一章的关键词是:从侧面看。这一章的关键词是:从下面看。

在这一章最开始,我想先回答很多人的一个问题:傅里叶分析究竟是干什么用的?这段相对比较枯燥,已经知道了的同学可以直接跳到下一个分割线。

先说一个最直接的用途。无论听广播还是看电视,我们一定对一个词不陌生——频道。频道频道,就是频率的通道,不同的频道就是将不同的频率作为一个通道来进行信息传输。下面大家尝试一件事:

先在纸上画一个sin(x),不一定标准,意思差不多就行。不是很难吧。

好,接下去画一个sin(3x)+sin(5x)的图形。

别说标准不标准了,曲线什么时候上升什么时候下降你都不一定画的对吧?

好,画不出来不要紧,我把sin(3x)+sin(5x)的曲线给你,但是前提是你不知道这个曲线的方程式,现在需要你把sin(5x)给我从图里拿出去,看看剩下的是什么。这基本是不可能做到的。

但是在频域呢?则简单的很,无非就是几条竖线而已。

所以很多在时域看似不可能做到的数学操作,在频域相反很容易。这就是需要傅里叶变换的地方。尤其是从某条曲线中去除一些特定的频率成分,这在工程上称为滤波,是信号处理最重要的概念之一,只有在频域才能轻松的做到。

再说一个更重要,但是稍微复杂一点的用途——求解微分方程。(这段有点难度,看不懂的可以直接跳过这段)微分方程的重要性不用我过多介绍了。各行各业都用的到。但是求解微分方程却是一件相当麻烦的事情。因为除了要计算加减乘除,还要计算微分积分。而傅里叶变换则可以让微分和积分在频域中变为乘法和除法,大学数学瞬间变小学算术有没有。

傅里叶分析当然还有其他更重要的用途,我们随着讲随着提。

—————————————————————————————————

下面我们继续说相位谱:

通过时域到频域的变换,我们得到了一个从侧面看的频谱,但是这个频谱并没有包含时域中全部的信息。因为频谱只代表每一个对应的正弦波的振幅是多少,而没有提到相位。基础的正弦波A.sin(wt+θ)中,振幅,频率,相位缺一不可,不同相位决定了波的位置,所以对于频域分析,仅仅有频谱(振幅谱)是不够的,我们还需要一个相位谱。那么这个相位谱在哪呢?我们看下图,这次为了避免图片太混论,我们用7个波叠加的图。

鉴于正弦波是周期的,我们需要设定一个用来标记正弦波位置的东西。在图中就是那些小红点。小红点是距离频率轴最近的波峰,而这个波峰所处的位置离频率轴有多远呢?为了看的更清楚,我们将红色的点投影到下平面,投影点我们用粉色点来表示。当然,这些粉色的点只标注了波峰距离频率轴的距离,并不是相位。

这里需要纠正一个概念:时间差并不是相位差。如果将全部周期看作2Pi或者360度的话,相位差则是时间差在一个周期中所占的比例。我们将时间差除周期再乘2Pi,就得到了相位差。

在完整的立体图中,我们将投影得到的时间差依次除以所在频率的周期,就得到了最下面的相位谱。所以,频谱是从侧面看,相位谱是从下面看。

注意到,相位谱中的相位除了0,就是Pi。因为cos(t+Pi)=-cos(t),所以实际上相位为Pi的波只是上下翻转了而已。对于周期方波的傅里叶级数,这样的相位谱已经是很简单的了。另外值得注意的是,由于cos(t+2Pi)=cos(t),所以相位差是周期的,pi和3pi,5pi,7pi都是相同的相位。人为定义相位谱的值域为(-pi,pi],所以图中的相位差均为Pi。

最后来一张大集合:

四、傅里叶变换(Fourier Transformation)

相信通过前面三章,大家对频域以及傅里叶级数都有了一个全新的认识。但是文章在一开始关于钢琴琴谱的例子我曾说过,这个栗子是一个公式错误,但是概念典型的例子。所谓的公式错误在哪里呢?

傅里叶级数的本质是将一个周期的信号分解成无限多分开的(离散的)正弦波,但是宇宙似乎并不是周期的。曾经在学数字信号处理的时候写过一首打油诗:

往昔连续非周期,

回忆周期不连续,

任你ZT、DFT,

还原不回去。

(请无视我渣一样的文学水平……)

在这个世界上,有的事情一期一会,永不再来,并且时间始终不曾停息地将那些刻骨铭心的往昔连续的标记在时间点上。但是这些事情往往又成为了我们格外宝贵的回忆,在我们大脑里隔一段时间就会周期性的蹦出来一下,可惜这些回忆都是零散的片段,往往只有最幸福的回忆,而平淡的回忆则逐渐被我们忘却。因为,往昔是一个连续的非周期信号,而回忆是一个周期离散信号。

是否有一种数学工具将连续非周期信号变换为周期离散信号呢?抱歉,真没有。

比如傅里叶级数,在时域是一个周期且连续的函数,而在频域是一个非周期离散的函数。这句话比较绕嘴,实在看着费事可以干脆回忆第一章的图片。

而在我们接下去要讲的傅里叶变换,则是将一个时域非周期的连续信号,转换为一个在频域非周期的连续信号。

算了,还是上一张图方便大家理解吧:

或者我们也可以换一个角度理解:傅里叶变换实际上是对一个周期无限大的函数进行傅里叶变换。

所以说,钢琴谱其实并非一个连续的频谱,而是很多在时间上离散的频率,但是这样的一个贴切的比喻真的是很难找出第二个来了。

因此在傅里叶变换在频域上就从离散谱变成了连续谱。那么连续谱是什么样子呢?

你见过大海么?

为了方便大家对比,我们这次从另一个角度来看频谱,还是傅里叶级数中用到最多的那幅图,我们从频率较高的方向看。

以上是离散谱,那么连续谱是什么样子呢?

尽情的发挥你的想象,想象这些离散的正弦波离得越来越近,逐渐变得连续……

直到变得像波涛起伏的大海:

很抱歉,为了能让这些波浪更清晰的看到,我没有选用正确的计算参数,而是选择了一些让图片更美观的参数,不然这图看起来就像屎一样了。

不过通过这样两幅图去比较,大家应该可以理解如何从离散谱变成了连续谱的了吧?原来离散谱的叠加,变成了连续谱的累积。所以在计算上也从求和符号变成了积分符号。

不过,这个故事还没有讲完,接下去,我保证让你看到一幅比上图更美丽壮观的图片,但是这里需要介绍到一个数学工具才能然故事继续,这个工具就是——

五、宇宙耍帅第一公式:欧拉公式

虚数i这个概念大家在高中就接触过,但那时我们只知道它是-1的平方根,可是它真正的意义是什么呢?

这里有一条数轴,在数轴上有一个红色的线段,它的长度是1。当它乘以3的时候,它的长度发生了变化,变成了蓝色的线段,而当它乘以-1的时候,就变成了绿色的线段,或者说线段在数轴上围绕原点旋转了180度。

我们知道乘-1其实就是乘了两次 i使线段旋转了180度,那么乘一次 i 呢——答案很简单——旋转了90度。

同时,我们获得了一个垂直的虚数轴。实数轴与虚数轴共同构成了一个复数的平面,也称复平面。这样我们就了解到,乘虚数i的一个功能——旋转。

现在,就有请宇宙第一耍帅公式欧拉公式隆重登场——

这个公式在数学领域的意义要远大于傅里叶分析,但是乘它为宇宙第一耍帅公式是因为它的特殊形式——当x等于Pi的时候。

经常有理工科的学生为了跟妹子表现自己的学术功底,用这个公式来给妹子解释数学之美:”石榴姐你看,这个公式里既有自然底数e,自然数1和0,虚数i还有圆周率pi,它是这么简洁,这么美丽啊!“但是姑娘们心里往往只有一句话:”臭屌丝……“

这个公式关键的作用,是将正弦波统一成了简单的指数形式。我们来看看图像上的涵义:

欧拉公式所描绘的,是一个随着时间变化,在复平面上做圆周运动的点,随着时间的改变,在时间轴上就成了一条螺旋线。如果只看它的实数部分,也就是螺旋线在左侧的投影,就是一个最基础的余弦函数。而右侧的投影则是一个正弦函数。

关于复数更深的理解,大家可以参考:

复数的物理意义是什么?

这里不需要讲的太复杂,足够让大家理解后面的内容就可以了。

六、指数形式的傅里叶变换

有了欧拉公式的帮助,我们便知道:正弦波的叠加,也可以理解为螺旋线的叠加在实数空间的投影。而螺旋线的叠加如果用一个形象的栗子来理解是什么呢?

光波

高中时我们就学过,自然光是由不同颜色的光叠加而成的,而最著名的实验就是牛顿师傅的三棱镜实验:

所以其实我们在很早就接触到了光的频谱,只是并没有了解频谱更重要的意义。

但不同的是,傅里叶变换出来的频谱不仅仅是可见光这样频率范围有限的叠加,而是频率从0到无穷所有频率的组合。

这里,我们可以用两种方法来理解正弦波:

第一种前面已经讲过了,就是螺旋线在实轴的投影。

另一种需要借助欧拉公式的另一种形式去理解:

[公式]
[公式]

将以上两式相加再除2,得到:

[公式]

这个式子可以怎么理解呢?

我们刚才讲过,e^(it)可以理解为一条逆时针旋转的螺旋线,那么e^(-it)则可以理解为一条顺时针旋转的螺旋线。而cos(t)则是这两条旋转方向不同的螺旋线叠加的一半,因为这两条螺旋线的虚数部分相互抵消掉了!

举个例子的话,就是极化方向不同的两束光波,磁场抵消,电场加倍。

这里,逆时针旋转的我们称为正频率,而顺时针旋转的我们称为负频率(注意不是复频率)。

好了,刚才我们已经看到了大海——连续的傅里叶变换频谱,现在想一想,连续的螺旋线会是什么样子:

想象一下再往下翻:

是不是很漂亮?

你猜猜,这个图形在时域是什么样子?

哈哈,是不是觉得被狠狠扇了一个耳光。数学就是这么一个把简单的问题搞得很复杂的东西。

顺便说一句,那个像大海螺一样的图,为了方便观看,我仅仅展示了其中正频率的部分,负频率的部分没有显示出来。

如果你认真去看,海螺图上的每一条螺旋线都是可以清楚的看到的,每一条螺旋线都有着不同的振幅(旋转半径),频率(旋转周期)以及相位。而将所有螺旋线连成平面,就是这幅海螺图了。

好了,讲到这里,相信大家对傅里叶变换以及傅里叶级数都有了一个形象的理解了,我们最后用一张图来总结一下:

好了,傅里叶的故事终于讲完了 。

UE5渲染技术简介:Nanite篇

作者:洛城
原文地址:https://zhuanlan.zhihu.com/p/382687738

前言

在今年初Epic放出了UE5技术演示DEMO后,关于UE5的讨论就一直未曾停止,相关技术讨论主要围绕两个新的feature:全局照明技术Lumen和极高模型细节技术Nanite,已经有一些文章[1][2]比较详细的介绍了Nanite技术。本文主要从UE5的RenderDoc分析和源码出发,结合一些已有的技术资料,旨在能够提供对Nanite直观和总览式的理解,并厘清其算法原理和设计思想,不会涉及过多源码级别的实现细节。

次世代模型渲染,我们需要什么?

要分析Nanite的技术要点,首先要从技术需求的角度出发。近十年来,3A类游戏的发展都逐渐趋向于两个要点:互动式电影叙事开放大世界:为了逼真的电影感cutscene,角色模型需要纤毫毕现;为了足够灵活丰富的开放世界,地图尺寸和物件数量呈指数级增长,这两者都大幅度提升了场景精细度和复杂度的要求:场景物件数量既要多,每个模型又要足够精细

复杂场景绘制的瓶颈通常有两个:(1)每次Draw Call带来的CPU端验证及CPU-GPU之间的通信开销;(2)由于剔除不够精确导致的overdraw和由此带来的GPU计算资源的浪费;近年来渲染技术优化往往也都是围绕这两个难题,并形成了一些业内的技术共识:

针对CPU端验证、状态切换带来的开销,我们有了新一代的图形API(Vulkan,DX12,Metal),旨在让驱动在CPU端做更少的验证工作;将不同任务通过不同的queue派发给GPU(Compute/Graphics/DMA Queue);要求开发者自行处理CPU和GPU之间的同步;充分利用多核CPU的优势多线程向GPU提交命令。得益于这些优化,新一代图形API的draw call数量相较于上一代图形API(DX11,OpenGL)提高了一个数量级[3]

另一个优化方向是减少CPU和GPU之间的数据通讯,以及更加精确的剔除对最终画面没有贡献的三角形。基于这个思路,诞生了GPU Driven Pipeline。关于GPU Driven Pipeline以及剔除的更多内容,可以读一读笔者的这篇文章[4]。得益于GPU Driven Pipeline在游戏中越来越广泛的应用,把模型的顶点数据进一步切分为更细粒度的Cluster(或者叫做Meshlet),让每个Cluster的粒度能够更好地适应Vertex Processing阶段的Cache大小,并以Cluster为单位进行各类剔除(Frustum Culling,Occulsion Culling,Backface Culling)已经逐渐成为了复杂场景优化的最佳实践,GPU厂商也逐渐认可了这一新的顶点处理流程。但传统的GPU Driven Pipeline依赖Compute Shader剔除,剔除后的数据需要存储在GPU Buffer内,经由Execute Indirect这类API,把剔除后的Vertex/Index Buffer重新喂给GPU的Graphics Pipeline,无形中增加了一读一写的开销;此外顶点数据也会被重复读取(Compute Shader在剔除前读取以及Graphics Pipeline在绘制时通过Vertex Attribute Fetch读取)。基于以上的原因,为了进一步提高顶点处理的灵活度,NVidia最先引入了Mesh Shader[5]的概念,希望能够逐步去掉传统顶点处理阶段的一些固定单元(VAF,PD一类的硬件单元),并把这些事交由开发者通过可编程管线(Task Shader/Mesh Shader)处理。

Cluster示意图

传统的GPU Driven Pipeline,剔除依赖CS,剔除的数据通过VRAM向顶点处理管线传递

基于Mesh Shader的Pipeline,Cluster剔除成为了顶点处理阶段的一部分,减少没必要的Vertex Buffer Load/Store

这些就够了吗?

至此,模型数、三角形顶点数和面数的问题已经得到了极大的优化改善。但高精度的模型、像素级别的小三角形给渲染管线带来了新的压力:光栅化重绘(overdraw)的压力。

软光栅化是否有机会打败硬光栅化?

要弄清楚这个问题,首先需要理解硬件光栅化究竟做了什么,以及它设想的一般应用场景是什么样的,推荐感兴趣的读者读一读这篇文章[6]。简单来说:传统光栅化硬件设计之初,设想的输入三角形大小是远大于一个像素的。基于这样的设想,硬件光栅化的过程通常是层次式的。以N卡的光栅器为例,一个三角形通常会经历两个阶段的光栅化:Coarse RasterFine Raster,前者以一个三角形作为输入,以8×8像素为一个块,将三角形光栅化为若干块(你也可以理解成在尺寸为原始FrameBuffer 1/8*1/8大小的FrameBuffer上做了一次粗光栅化)。在这个阶段,借由低分辨率的Z-Buffer,被遮挡的块会被整个剔除,N卡上称之为Z Cull;在Coarse Raster之后,通过Z Cull的块会被送到下一阶段做Fine Raster,最终生成用于着色计算的像素。在Fine Raster阶段,有我们熟悉的Early Z。由于mip-map采样的计算需要,我们必须知道每个像素相邻像素的信息,并利用采样UV的差分作为mip-map采样层级的计算依据。为此,Fine Raster最终输出的并不是一个个像素,而是2×2的小像素块(Pixel Quad)。

对于接近像素大小的三角形来说,硬件光栅化的浪费就很明显了:首先,Coarse Raster阶段几乎是无用的,因为这些三角形通常都是小于8×8的,对于那些狭长的三角形,这种情况更糟糕,因为一个三角形往往横跨多个块,而Coarse Raster不但无法剔除这些块,还会增加额外的计算负担;另外,对于大三角形来说,基于Pixel Quad的Fine Raster阶段只会在三角形边缘生成少量无用的像素,相较于整个三角形的面积,这只是很少的一部分;但对于小三角形来说,Pixel Quad最坏会生成四倍于三角形面积的像素数,并且这些像素也包含在pixel shader的执行阶段,使得warp中有效的像素大大减少。

小三角形由于Pixel Quad造成的光栅化浪费

基于上述的原因,在像素级小三角形这一特定前提下,软光栅化(基于Compute Shader)的确有机会打败硬光栅化。这也正是Nanite的核心优化之一,这一优化使得UE5在小三角形光栅化的效率上提升了3倍[7]

Deferred Material

重绘的问题长久以来都是图形渲染的性能瓶颈,围绕这一话题的优化也层出不穷:在移动端,有我们熟悉的Tile Based Rendering架构[8];在渲染管线的进化历程中,也先后有人提出了Z-PrepassDeferred RenderingTile Based Rendering以及Clustered Rendering,这些不同的渲染管线框架,实际上都是为了解决同一个问题:当光源超过一定数量、材质的复杂度提升后,如何尽量避免Shader中大量的渲染逻辑分支,以及减少无用的重绘。有关这个话题,可以读一读我的这篇文章[9]

通常来说,延迟渲染管线都需要一组称之为G-BufferRender Target,这些贴图内存储了一切光照计算需要的材质信息。当今的3A游戏中,材质种类往往复杂多变,需要存储的G-Buffer信息也在逐年增加,以2009年的游戏《Kill Zone 2》为例,整个G-Buffer布局如下:

除去Lighting Buffer,实际上G-Buffer需要的贴图数量为4张,共计16 Bytes/Pixel;而到了2016年,游戏《Uncharted 4》的G-Buffer布局如下:

G-Buffer的贴图数量为8张,即32 Bytes/Pixel。也就是说,相同分辨率的情况下,由于材质复杂度和逼真度的提升,G-Buffer需要的带宽足足提高了一倍,这还不考虑逐年提高的游戏分辨率的因素

对于overdraw较高的场景,G-Buffer的绘制产生的读写带宽往往会成为性能瓶颈。于是学界提出了一种称之为Visibility Buffer的新渲染管线[10][11]。基于Visibility Buffer的算法不再单独产生臃肿的G-Buffer,而是以带宽开销更低的Visibility Buffer作为替代,Visibility Buffer通常需要这些信息:

(1)InstanceID,表示当前像素属于哪个Instance(16~24 bits);

(2)PrimitiveID,表示当前像素属于Instance的哪个三角形(8~16 bits);

(3)Barycentric Coord,代表当前像素位于三角形内的位置,用重心坐标表示(16 bits);

(4)Depth Buffer,代表当前像素的深度(16~24 bits);

(5)MaterialID,表示当前像素属于哪个材质(8~16 bits);

以上,我们只需要存储大约8~12 Bytes/Pixel即可表示场景中所有几何体的材质信息,同时,我们需要维护一个全局的顶点数据和材质贴图表,表中存储了当前帧所有几何体的顶点数据,以及材质参数和贴图。在光照着色阶段,只需要根据InstanceID和PrimitiveID从全局的Vertex Buffer中索引到相关三角形的信息;进一步地,根据像该素的重心坐标,对Vertex Buffer内的顶点信息(UV,Tangent Space等)进行插值得到逐像素信息;再进一步地,根据MaterialID去索引相关的材质信息,执行贴图采样等操作,并输入到光照计算环节最终完成着色,有时这类方法也被称为Deferred Texturing

下面是基于G-Buffer的渲染管线流程:

这是基于Visibility-Buffer的渲染管线流程:

直观地看,Visibility Buffer减少了着色所需要信息的储存带宽(G-Buffer -> Visibility Buffer);此外,它将光照计算相关的几何信息和贴图信息读取延迟到了着色阶段,于是那些屏幕不可见的像素不必再读取这些数据,而是只需要读取顶点位置即可。基于这两个原因,Visibility Buffer在分辨率较高的复杂场景下,带宽开销相比传统G-Buffer大大降低。但同时维护全局的几何、材质数据,增加了引擎设计的复杂度,同时也降低了材质系统的灵活度,有时候还需要借助Bindless Texture[12]等尚未全硬件平台支持的Graphics API,不利于兼容。

Nanite中的实现

罗马绝非一日建成。任何成熟的学术和工程领域孕育出的技术突破都一定有前人的思考和实践,这也是为什么我们花费了大量的篇幅去介绍相关技术背景:Nanite正是总结前人方案,结合现时硬件的算力,并从下一代游戏技术需求出发得到的优秀工程实践。它的核心思想可以简单拆解为两大部分:顶点处理的优化像素处理的优化其中顶点处理的优化主要是GPU Driven Pipeline的思想;像素处理的优化,是在Visibility Buffer思想的基础上,结合软光栅化完成的。借助UE5 Ancient Valley技术演示的RenderDoc抓帧和相关的源码,我们可以一窥Nanite的技术真面目。整个算法流程如图:

Instance Cull && Persistent Cull

当我们详细地解释了GPU Driven Pipeline的发展历程以后,就不难理解Nanite的实现:每个Nanite Mesh在预处理阶段,会被切成若干Cluster,每个Cluster包含128个三角形,整个Mesh以BVH(Bounding Volume Hierarchy)的形式组织成树状结构,每个叶节点代表一个Cluster。剔除分两步,包含了视锥剔除基于HZB的遮挡剔除。其中Instance Cull以Mesh为单位,通过Instance Cull的Mesh会将其BVH的根节点送到Persistent Cull阶段进行层次式的剔除(若某个BVH节点被剔除,则不再处理其子节点)。这就需要考虑一个问题:如何把Persistent Cull阶段的剔除任务数量映射到Compute Shader的线程数量?最简单的方法是给每棵BVH树一个单独的线程,也就是一个线程负责一个Nanite Mesh。但由于每个Mesh的复杂度不同,其BVH树的节点数、深度差异很大,这样的安排会导致每个线程的任务处理时长大不相同,线程间互相等待,最终导致并行性很差;那么能否给每个需要处理的BVH节点分配一个单独的线程呢?这当然是最理想的情形,但实际上我们无法在剔除前预先知道会有多少个BVH节点被处理,因为整个剔除是层次式的、动态的。Nanite解决这个问题的思路是:设置固定数量的线程,每个线程通过一个全局的FIFO任务队列去取BVH节点进行剔除,若该节点通过了剔除,则把该节点的所有子节点也放进任务队列尾部,然后继续循环从全局队列中取新的节点,直到整个队列为空且不再产生新的节点。这其实是一个多线程并发的经典生产-消费者模式,不同的是,这里的每个线程既充当生产者,又充当消费者。通过这样的模式,Nanite就保证了各个线程之间的处理时长大致相同。

整个剔除阶段分为两个Pass:Main PassPost Pass(可以通过控制台变量设置为只有Main Pass)。这两个Pass的逻辑基本是一致的,区别仅仅在于Main Pass遮挡剔除使用的HZB是基于上一帧数据构造的,而Post Pass则是使用Main Pass结束后构建的当前帧的HZB,这样是为了防止上一帧的HZB错误地剔除了某些可见的Mesh。

需要注意的是,Nanite并未使用Mesh Shader,究其原因,一方面是因为Mesh Shader的支持尚未普及;另一方面是由于Nanite使用软光栅化,Mesh Shader的输出仍要写回GPU Buffer再用于软光栅化输入,因此相较于CS的方案并没有太多带宽的节省。

Rasterization

在剔除结束之后,每个Cluster会根据其屏幕空间的大小送至不同的光栅器,大三角形和非Nanite Mesh仍然基于硬件光栅化,小三角形基于Compute Shader写成的软光栅化。Nanite的Visibility Buffer为一张R32G32_UINT的贴图(8 Bytes/Pixel),其中R通道的0~6 bit存储Triangle ID,7~31 bit存储Cluster ID,G通道存储32 bit深度:

Cluster ID
Triangle ID
Depth

整个软光栅化的逻辑比较简单:基于扫描线算法,每个Cluster启动一个单独的Compute Shader,在Compute Shader初始阶段计算并缓存所有Clip Space Vertex Positon到shared memory,而后CS中的每个线程读取对应三角形的Index Buffer和变换后的Vertex Position,根据Vertex Position计算出三角形的边,执行背面剔除和小三角形(小于一个像素)剔除,然后利用原子操作完成Z-Test,并将数据写进Visibility Buffer。值得一提的是,为了保证整个软光栅化逻辑的简洁高效,Nanite Mesh不支持带有骨骼动画、材质中包含顶点变换或者Mask的模型

Emit Targets

为了保证数据结构尽量紧凑,减少读写带宽,所有软光栅化需要的数据都存进了一张Visibility Buffer,但是为了与场景中基于硬件光栅化生成的像素混合,我们最终还是需要将Visibility Buffer中的额外信息写入到统一的Depth/Stencil Buffer以及Motion Vector Buffer当中。这个阶段通常由几个全屏Pass组成:

(1)Emit Scene Depth/Stencil/Nanite Mask/Velocity Buffer,这一步根据最终场景需要的RenderTarget数据,最多输出四个Buffer,其中Nanite Mask用0/1表示当前像素是普通Mesh还是Nanite Mesh(根据Visibility Buffer对应位置的ClusterID得到),对于Nanite Mesh Pixel,将Visibility Buffer中的Depth由UINT转为float写入Scene Depth Buffer,并根据Nanite Mesh是否接受贴花,将贴花对应的Stencil Value写入Scene Stencil Buffer,并根据上一帧位置计算当前像素的Motion Vector写入Velocity Buffer,非Nanite Mesh则直接discard跳过。

Nanite Mask
Velocity Buffer
Scene Depth/Stencil Buffer

(2)Emit Material Depth,这一步将生成一张Material ID Buffer,稍有不同的是,它并未存储在一张UINT类型的贴图,而是将UINT类型的Material ID转为float存储在一张格式为D32S8的Depth/Stencil Target上(稍后我们会解释这么做的理由),理论上最多支持2^32种材质(实际上只有14 bits用于存储Material ID),而Nanite Mask会被写入Stencil Buffer中。

Material Depth Buffer

Classify Materials && Emit G-Buffer

我们已经详细地介绍了Visibility Buffer的原理,在着色计算阶段的一种实现是维护一个全局材质表,表中存储材质参数以及相关贴图的索引,根据每个像素的Material ID找到对应材质,解析材质信息,利用Virtual Texture或者Bindless Texture/Texture Array等技术方案获取对应的贴图数据。对于简单的材质系统这是可行的,但是UE包含了一套极其复杂的材质系统,每种材质有不同的Shading Model,同种Shading Model下各个材质参数还可以通过材质编辑器进行复杂的连线计算,这种基于连连看动态生成材质Shader Code的模式显然无法用上述方案实现。

为了保证每种材质的Shader Code仍然能基于材质编辑器动态生成,每种材质的PS Shader至少要执行一次,但我们只有屏幕空间的材质ID信息,于是不同于以往逐个物体绘制的同时运行其对应的材质Shader(Object Space),Nanite的材质Shader是在Screen Space执行的,以此将可见性计算和材质参数计算解耦,这也是Deferred Material名字的由来。但这又引发了新的新能问题:场景中的材质动辄成千上万,每个材质都用一个全屏Pass去绘制,则重绘带来的带宽压力势必非常高,如何减少无意义的重绘就成为了新的挑战。

为此,Nanite在Base Pass绘制阶段并不是每种材质一个全屏Pass,而是将屏幕空间分成若干8×8的块,比如屏幕大小为800×600,则每种材质绘制时生成100×75个块,每块对应屏幕位置。为了能够整块地剔除,在Emit Targets之后,Nanite会启动一个CS用于统计每个块内包含的Material ID的种类。由于Material ID对应的Depth值预先是经过排序的,所以这个CS会统计每个8×8的块内Material Depth的最大最小值作为Material ID Range存储在一张R32G32_UINT的贴图中:

Material ID Range

有了这张图之后,每种材质在其VS阶段,都会根据自身块的位置去采样这张贴图对应位置的Material ID Range,若当前材质的Material ID处于Range内,则继续执行材质的PS;否则表示当前块内没有像素使用该材质,则整块可以剔除,此时只需将VS的顶点位置设置为NaN,GPU就会将对应的三角形剔除。由于通常一个块内的材质种类不会太多,这种方法可以有效地减少不必要的overdraw。实际上通过分块分类减少材质分支,进而简化渲染逻辑的思路也并非第一次被提出,比如《Uncharted 4》在实现他们的延迟光照时[13],由于材质包含多种Shading Model,为了避免每种Shading Model启动一个单独的全屏CS,他们也将屏幕分块(16×16),并统计了块内Shading Model的种类,根据块内Shading Model的Range给每个块单独启动一个CS,取Range内对应的Lighting Shader,以此避免多遍全屏Pass或者一个包含大量分支逻辑的Uber Shader,从而大幅度提高了延迟光照的性能。

Uncharted 4中分块统计Shading Model Range

在完成了逐块的剔除后,Material Depth Buffer就派上了用场。在Base Pass PS阶段,Material Depth Buffer被设置为Depth/Stencil Target,同时Depth/Stencil Test被打开,Compare Function设置为Equal。只有当前像素的Material ID和待绘制的材质ID相同(Depth Test Pass)且该像素为Nanite Mesh(Stencil Test Pass)时才会真正执行PS,于是借助硬件的Early Z/Stencil我们完成了逐像素的材质ID剔除,整个绘制和剔除的原理见下图:

红色表示被剔除的区域

整个Base Pass分为两部分,首先绘制非Nanite Mesh的G-Buffer,这部分仍然在Object Space执行,和UE4的逻辑一致;之后按照上述流程绘制Nanite Mesh的G-Buffer,其中材质需要的额外VS信息(UV,Normal,Vertex Color等)通过像素的Cluster ID和Triangle ID索引到相应的Vertex Position,并变换到Clip Space,根据Clip Space Vertex Position和当前像素的深度值求出当前像素的重心坐标以及Clip Space Position的梯度(DDX/DDY),将重心坐标和梯度代入各类Vertex Attributes中插值即可得到所有的Vertex Attributes及其梯度(梯度可用于计算采样的Mip Map层级)。

至此,我们分析了Nanite的技术背景和完整实现逻辑。

参考

  1. ^A Macro View of Nanite http://www.elopezr.com/a-macro-view-of-nanite/
  2. ^UE5 Nanite实现浅析 https://zhuanlan.zhihu.com/p/376267968
  3. ^Vulkan API Overhead Test Added to 3DMark https://www.geeks3d.com/20170323/vulkan-api-overhead-test-added-in-3dmark/
  4. ^剔除:从软件到硬件 https://zhuanlan.zhihu.com/p/66407205
  5. ^Mesh Shading: Towards Greater Efficiency of Geometry Processing http://advances.realtimerendering.com/s2019/Mesh_shading_SIG2019.pptx
  6. ^A Trip Through the Graphics Pipeline https://alaingalvan.gitbook.io/a-trip-through-the-graphics-pipeline/chapter6-triangle-rasterization
  7. ^Nanite | Inside Unreal https://www.youtube.com/watch?v=TMorJX3Nj6U&t=1248s
  8. ^Tile-Based Rendering https://developer.arm.com/solutions/graphics-and-gaming/developer-guides/learn-the-basics/tile-based-rendering/single-page
  9. ^游戏引擎中的渲染管线 https://zhuanlan.zhihu.com/p/92165837
  10. ^The Visibility Buffer: A Cache-Friendly Approach to Deferred Shading http://jcgt.org/published/0002/02/04/paper.pdf
  11. ^Triangle Visibility Buffer http://diaryofagraphicsprogrammer.blogspot.com/2018/03/triangle-visibility-buffer.html
  12. ^Bindless Texture https://www.khronos.org/opengl/wiki/Bindless_Texture
  13. ^Deferred Lighting in Uncharted 4 http://advances.realtimerendering.com/s2016/s16_ramy_final.pptx

剔除:从软件到硬件(转)

作者:洛城
原文地址:https://zhuanlan.zhihu.com/p/66407205

前言

剔除是游戏引擎中非常重要的技术:现代引擎需要在十几毫秒的预算里,渲染出数以万计的物体,场景复杂度往往是数千万面的级别,同时还需要处理千计盏灯光和数百种材质。对于开放世界类型的游戏更是如此:场景动辄就是数十公里的延伸,想要通过暴力穷举地方法逐一绘制这些物体是不现实的。因此,如何有效地减少不必要的绘制就显得格外重要。

这是一篇很早就想写的话题,也是我入职腾讯后的第一篇技术文章,这篇文章仅就游戏引擎中用到的各种剔除技术进行一个概述,涵盖了从引擎算法层面到硬件层面的内容。文中会较少涉及细节,感兴趣的同学可以去看文末的引用。

算法层面的剔除

视锥剔除

视锥剔除是所有3D引擎的标配。实时图形学里,摄像机一般是基于针孔模型:光线经过一个小孔(可认为是一个点)照射到小孔背后的传感器阵列(通常是规则的矩形)上,从而形成图像。从小孔出发,只有与传感器阵列有交点的光线才能够真正进入最终的画面,这个区域就是我们一般说的视锥体

由此得到的最基本的剔除思路就是视锥剔除:即简单的判断一个物体是否位于视锥棱台内。在实践中,由于模型往往是比较复杂的,很难精确计算它和视锥体的交集,因此一般是用轴对齐包围盒(AABB)有向包围盒(OBB)或者包围球(BSphere)代替模型本身进行相交计算。

对于复杂场景来说,线性数组的遍历方式往往不够高效,这时候也可以将场景以层次结构组织起来进行剔除(譬如QuadTreeOctree等)。

视锥剔除原理虽然简单,但要做到又快又好仍然不容易,尤其对于性能更严苛的生产环境来说。除了上面提到的场景包围盒的组织结构以外,另一个能够加快剔除速度的方法是利用CPU的SSE指令集,这个指令集的执行方式是SIMD,即单指令多数据,可以同时处理多组浮点数的相同运算。利用这个特性,我们可以同时处理多个包围盒和视锥的相交测试。具体的实现以及性能分析可以参考Frostbite的这篇分享[1]

视锥剔除本质上还是一个场景遍历的过程,通常来说,场景是通过树的形式存储和访问,每个子节点的最终变换由所有父节点的变换和它自身局部变换共同决定,因此如何快速地计算每个节点的变换数据也很重要。这篇文章[2]详细地阐述了面向数据编程(DOP)的思想,包括SoA和AoS两种数据布局的差异以及它们对于缓存和性能的影响。其中就以场景遍历作为例子,解释了如何利用DOP的编程思想去优化场景遍历和视锥剔除。

基于Portal的剔除

相较于视锥剔除的通用性来说,Portal的应用场景更受限制,同时需要更多的手工标定的步骤,但在某些特定环境下能够发挥很好的效果。

Portal的概念很简单,一般来说它适用于封闭的室内空间:假设我们身处一个封闭的大房子里,房子里有很多相连的房间,Portal就类似于房间之间的门。如果每个房间被看作一个孤立的节点,那Portal就是连接这些节点的桥梁。当我们处于某一个房间里(节点)的时候,只有那些和它相连的房间才有可能被我们看到。Portal就是美术/策划在制作关卡过程中人工标记出来的连接。在剔除的时候,我们只需要在标记好的图里找到我们摄像机所处的房间(节点),然后找到所有与它有Portal连接的节点,没有Portal连接的所有节点都可以直接被判定为不可见的从而被剔除。

基于Occlusion Query的遮挡剔除

遮挡剔除的原理也很简单:处于视锥内的模型也未必是可见的,因为它有可能被其他模型完全挡住。如果我们能够用比较低的代价去找到那些被完全遮挡的模型,那么就不需要对它们再进行绘制,从而提高渲染性能。

最早尝试在GPU上执行遮挡剔除应该是在occlusion query被支持之后。简单来说,occlusion query允许你在绘制命令执行之前,向GPU插入一条查询,并且在绘制结束之后的某个时刻,从GPU将查询结果回读到系统内存里。这条查询命令得到的是某次DrawCall中通过Depth Test的Sample数量,当这个Sample的数量大于0时,就表示当前模型是部分可见的,否则当前模型完全被遮挡。

基于这个API,我们就可以得到一个比较简单的遮挡剔除策略:

(1)用一个简单的depth only的pass绘制整个场景

(2)每次绘制前后插入occlusion query的命令,并根据passed sample count去标记某个物体是否被完全挡住

(3)执行正常的渲染流程,并剔除那些被标记为完全遮挡的模型

对于复杂的场景,即使只用简单的depth only pass也有很大的VS开销,一个显而易见的优化策略就是用包围盒代替模型本身去做渲染,为了更加精确,我们也可以用多个紧贴的包围盒或者相对原模型更简单的Proxy Mesh去做occlusion query[3]。此外,可以通过batch多个模型/包围盒去减少occlusion query阶段的draw call数量。

occlusion query的另一个缺点(也是最致命的缺点)是,它需要将查询结果回读到系统内存里,这就意味着VRAM->System RAM的操作,走的是比较慢的PCI-E。同时数据回读可能意味着图形API背后的驱动程序会在回读的位置Flush整个渲染命令缓冲队列并且等待之前所有的渲染命令执行完毕,相当于强制在回读位置插入了一个CPU和GPU的同步点,很可能得不偿失(实际上基于Render To Texture的Object Picking也有类似的性能问题,原理同上)。

CPU和GPU相互等待的示意图

为了解决这个问题,比较常用的的方法是让CPU回读前一帧的occlusion query的结果,用来决定当前帧某个物体是否visible,对于相机运动较快的场景,用上一帧的结果可能会导致出错,但由于一般是用包围盒,本身就是保守的剔除,所以总体来说影响不明显,UE4默认使用的就是这样的遮挡剔除方案。除了这个方法以外,GPU Gems的这篇文章[4]用了一个类似于分支预测的思路,利用两帧图像的连续性假设,把整个渲染队列里的物体分成了上一帧可见的模型上一帧不可见模型。对于上一帧可见的模型,我们就认为它这一帧也可见并且直接渲染它;对于上一帧不可见的模型,我们就插入一个查询到查询队列中然后暂时不处理。当我们没有可以直接用于渲染的模型时,我们再从查询队列里回读查询结果,并根据查询结果去更新被查询物体的可见性状态(用于下一帧的预测),同时若该模型可见,则执行渲染。具体的算法感兴趣的同学可以去看原文,想想这个方法是如何hide stall的。

基于Software Rasterization的遮挡剔除

这个方案最早应该是Frostbite提出来,用于BattleField3[1]的剔除方案。这个方案的思路是,首先利用CPU构造一个低分辨率的Z-Buffer,在Z-Buffer上绘制一些场景中较大的遮挡体(美术设定的一些大物体+地形):

在构造好的Z-Buffer上,绘制小物体的包围盒,然后执行类似于occlusion query的操作,查询当前物体是否被遮挡:

这个方法相对来说比较灵活(对于光源,物体均适用),由于是纯CPU的,集成起来也比较简单。对于主机平台还可能利用SPU之类的多余算力,同时不会有GPU stall的问题。缺点是需要美术指定一些大的遮挡体,对于CPU bound的项目可能会负优化。天涯明月刀的自研引擎中,应该也应用了这个优化策略,效果很好。参见叶老师 @Milo Yip 的这篇分享[5]

GPU Driven Rendering Pipeline[6][7]

这个思路的产生和发展得益于图形API和硬件的发展,具体来说,有两个feature至关重要:Compute Shader以及ExecuteIndirect。前者允许我们在GPU上方便地执行各类和渲染无关的GPGPU运算,并且将计算结果以Buffer或者Texture的形式存储在VRAM上;后者允许我们以GPU Buffer的形式直接构建Draw Command List。这两者结合起来,就表示我们能够在Compute Shader里构造Draw Command List用于绘制,整个过程无需CPU参与

先抛开具体实现细节,回到我们最初引入剔除的初衷:我们希望GPU知道哪些物体是不需要被渲染的(视锥之外,被完全遮挡),这个信息仅供GPU使用;此外,剔除算法的并行性很好,计算过程又相对简单,没有太多的分支和跳转,非常适合GPU去做。为此,我们只需要将场景的所有渲染资源(包括几何信息,材质信息,变换信息,包围盒信息)以一定规则打包存储在Buffer中,然后提供摄像机(视锥)信息和遮挡体绘制的Z-Buffer(类似于Software Rasterization的Z-Buffer),通过Compute Shader去执行视锥剔除和遮挡剔除,并将通过剔除的模型经由ExecuteIndirect提交渲染。

具体执行的时候,得益于GPU强大的浮点数计算能力,我们可以做比模型更细粒度的剔除:将Mesh切分成Cluster,每个Cluster有64个顶点,并且重排IndexedBuffer(Cluster大小的选取以及重排IB主要是为了提高Vertex Fetch时缓存的命中率,进而提高Vertex Fetch的速度),基于Cluster计算包围盒,利用Cluster Bouding Box去做视锥剔除。


对于遮挡剔除,在构造用于剔除的hierarchy Z-buffer的时候,也能够利用比software rasterization更快的hardware rasterization在GPU端去做。

构造Hi-Z的过程,首先基于美术指定的大遮挡体和地形去渲染一个Z-Buffer,然后down sample到低分辨率,混合上一帧Z-Buffer经过reprojection的结果,最后做一系列down sample得到一个层次Z-Buffer的结构

不同于Software Rasterization的方法,Hi-Z意味着我们可以从最粗粒度的Z-Buffer开始进行遮挡查询和剔除,相较于全分辨率的遮挡查询,这样的查询效率更高。

除了常用的Frustum Culling和Occlusion Culling,我们还可以在Compute Shader里去做Backface Culling和Small Primitive Culling,把背面的三角形和面积很小的三角形剔除掉。

在剔除工作完成后,通常会启动一个Compaction的Compute Shader,这个Shader会把通过culling的所有triangle复制到一个更紧凑的Buffer里面,并且执行一些基于材质Batch的合并策略。最后调用ExecuteIndirect来渲染最终场景:

GPU Driven Rendering Pipeline的核心思路是减少CPU和GPU之间的通信,尽量将所有渲染相关的事务(包括提交)都放在GPU端(自己的事情自己做),解放CPU的算力用于构造物理和AI的规则。同时,利用GPU的算力能够更精细粒度地去控制渲染命令队列内的生成和合并。在实际渲染时,除了我们这里提到的基于Compute Shader的Culling和Batching,还需要辅以Virtual Texturing,Mega Texture等技术并对渲染管线做配套改造,对原本的渲染引擎架构改动也较大,想要把这一技术植入引擎中并不容易。这部分更细节的内容,除了育碧和寒霜引擎的两篇分享[6][7],也有非常多的文章具体阐释[8][9][10][11],可以配合阅读。

当然,no pain no gain。基于GPU Driven Rendering Pipeline的性能提升也是非常大的,对于CPU提交端往往能提升一两个数量级的性能,同时得益于更精确的剔除,GPU端渲染也有一定程度的性能提升。

硬件层面的剔除

Clipping&Backface Culling

Graphics Pipeline稍有了解的同学对这两个环节应该都不陌生,Clipping是当一个三角形的顶点位置被变换到NDC后,针对NDC外的三角形和穿过NDC的三角形,会执行剔除或者裁剪的操作,具体的裁剪规则,可以参见这个问题。至于Backface Culling,则是在图元装配阶段结束之后,根据用户指定的手向,把面向摄像机或者背对摄像机(一般是背对摄像机)的三角形剔除[12],剔除后的三角形就不会再进入到Pixel Shader和Rasteriaztion的流程里。

Early-Z

提到Early-Z就必须提对应的Late-Z:在图形管线中,逻辑上Depth Test和Stencil Test是发生在Pixel Shader的执行之后的,因为Pixel Depth在Pixel Shader阶段还有可能被修改,所以Pixel Shader->Depth Test的流程顺序就是Late-Z。但由于Pixel Depth修改的需求非常少(基于深度混合的Impostor和某些粒子效果),所以绝大部分情况下,Pixel Depth在Rasterization之后、Pixel Shader执行之前就可以被确定下来,如果我们能够把Depth Test放在Pixel Shader之前,对那些没通过Depth Test的像素不执行Pixel Shader,就能够一定程度上减少SM的压力,这就是Early-Z这个优化策略的初衷,现在已经是GPU的标配了。默认在Pixel Shader里没有修改Depth的操作时,这个优化就会开启。

Z-Cull

很多人会将Z-Cull和Early-Z弄混,其实它俩并不一样,重点体现在剔除的粒度不同:Z-Cull的剔除是粗粒度的Pixel Tile(比如一个8*8的像素块),而Early-Z是细粒度的2*2的Pixel Quad(可以思考一下为什么是Pixel Quad而不是Pixel)。在Z-Cull进行Depth Test的时候,Pixel Tile会被压缩以加速比较(主要是减少带宽开销),比如用平面方程的系数表示一块Pixel Tile,用平面方程去和Z-Buffer做Coarse Depth Test,而不是Tile内部逐个像素去做Depth Test。正因为如此,常用的Alpha Test会让一个原本完整的平面出现空洞,这就会破坏Pixel Tile的压缩算法,进而导致Z-Cull无法开启。

现代引擎基本都会利用Z-Cull和Early-Z的特性去减少SM的计算压力,具体方法是执行一个Z-Prepass(不论是foward,forward+还是deferred管线都一样):先将不透明物体按照距离摄像机从前向后的顺序排序,然后只开启Z-Buffer write和compare,不执行Pixel Shader进行一遍渲染。在执行完Z-Prepass后,关闭Z-Buffer的写入,将compare function改为equal,然后执行后续复杂Pixel Shader(前向渲染的光照计算或者延迟渲染的G-Buffer填充)。

有关Early-Z和Z-Cull更多的开启条件,可以看这两篇文章[13][14]

总结

这篇文章主要是概述了现代渲染引擎中常用的剔除技术(有关阴影的剔除算法这里没有太多的涉及,我会在未来单独写一篇和阴影相关的主题),我们从上层算法和硬件优化两个大的分类上做了一些具体技术的罗列。总体来说,可以认为从算法剔除到硬件剔除是一个粒度在逐渐变精细的过程(Mesh->Cluster->Triangle->Pixel Tile->Pixel Quad)。而GPU Driven Rendering Pipeline作为一个相对来说比较特殊的存在,它不是一个具体的算法而是一种思路,这种思路代理了某些传统硬件上我们认为是固定管线的功能,同时尽可能地减少CPU和GPU的通信。它的出现符合现代硬件的发展趋势:一是可编程管线的功能日益强大进而代替更多的固定管线单元;二是相较于密集的计算量,现代程序的优化更多地依赖于如何提高硬件的并行程度,减少等待和同步,以及如何优化访存。

参考

  1. ^abCulling the Battlefield: Data Oriented Design in Practice https://www.gamedevs.org/uploads/culling-the-battlefield-battlefield3.pdf
  2. ^Pitfalls of Object Oriented Programming https://www.slideshare.net/EmanWebDev/pitfalls-of-object-oriented-programminggcap09
  3. ^Efficient Occlusion Culling https://developer.download.nvidia.cn/books/HTML/gpugems/gpugems_ch29.html
  4. ^Hardware Occlusion Queries Made Useful https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter06.html
  5. ^为实现极限性能的面向数据编程范式 http://twvideo01.ubm-us.net/o1/vault/gdcchina14/presentations/833779_MiloYip_ADataOrientedCN.pdf
  6. ^abGPU-Driven Rendering Pipelines http://advances.realtimerendering.com/s2015/aaltonenhaar_siggraph2015_combined_final_footer_220dpi.pdf
  7. ^abOptimizing the Graphics Pipeline with Compute https://frostbite-wp-prd.s3.amazonaws.com/wp-content/uploads/2016/03/29204330/GDC_2016_Compute.pdf
  8. ^https://zhuanlan.zhihu.com/p/33881505
  9. ^https://zhuanlan.zhihu.com/p/37084925
  10. ^https://bazhenovc.github.io/blog/post/gpu-driven-occlusion-culling-slides-lif/
  11. ^https://zhuanlan.zhihu.com/p/47615677
  12. ^https://en.wikipedia.org/wiki/Back-face_culling
  13. ^https://zhuanlan.zhihu.com/p/53092784
  14. ^https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter30.html