四百萬(wàn)個(gè)三角形面片的模型

上面這張圖主要是用來(lái)吸引人的，跟本文內(nèi)容沒啥關(guān)系（偷笑~）

還是跟之前一樣，本文是閱讀《基于物理的渲染：從理論到實(shí)踐》的總結(jié)，文中不會(huì)涉及到方方面面，只會(huì)整理筆者認(rèn)為重要的一兩個(gè)點(diǎn)。本文關(guān)注的重點(diǎn)是誤差，尤其是舍入誤差（Rounding Error），主要來(lái)源書中的3.9節(jié)。

由于作者水平所限，文中如果有錯(cuò)誤或者沒有解釋到位的地方，還請(qǐng)讀者不吝指正。

誤差的來(lái)源

首先我們必須認(rèn)識(shí)到，沒有任何方法可以避免誤差，我們能做的就只能是減少誤差。為啥？從誤差的來(lái)源我們就可以看出來(lái)了。

誤差會(huì)來(lái)自兩個(gè)方面：

第一，用于計(jì)算的數(shù)據(jù)（即輸入數(shù)據(jù)）本身就不是精確的，即輸入數(shù)據(jù)本身就帶有誤差。
第二，保存數(shù)據(jù)的工具會(huì)產(chǎn)生誤差。這個(gè)怎么理解？我們用計(jì)算機(jī)來(lái)保存數(shù)據(jù)，計(jì)算機(jī)是二進(jìn)制的，我們用來(lái)保存數(shù)據(jù)的大小也有限制，不可能表示數(shù)學(xué)上類似于“實(shí)數(shù)”這種無(wú)限精度的數(shù)字。

從誤差的來(lái)源我們就可以看出，誤差無(wú)法避免，無(wú)論是哪個(gè)方面的誤差我們都無(wú)法避免，只能盡可能的減少誤差。這就意味著，當(dāng)我們進(jìn)行計(jì)算的時(shí)候（尤其是要進(jìn)行光線和表面交點(diǎn)這種精度要求非常高的計(jì)算），我們必須把誤差考慮進(jìn)去，否則渲染出來(lái)的場(chǎng)景會(huì)和理想中的場(chǎng)景相差很大。而輸入數(shù)據(jù)本身的精確性我們沒法控制，就當(dāng)它是精確的吧！我們要讓第二個(gè)誤差，也就是保存數(shù)據(jù)的工具產(chǎn)生的誤差減少！

舍入誤差

舍入誤差，英文名叫rounding error，是用計(jì)算機(jī)保存實(shí)數(shù)的時(shí)候，由于精度有限，導(dǎo)致的保存的數(shù)據(jù)和原來(lái)的數(shù)據(jù)的差距。這個(gè)差距，就是舍入誤差。

就拿32位浮點(diǎn)數(shù)來(lái)說。IEEE的標(biāo)準(zhǔn)（下面講的內(nèi)容都是IEEE標(biāo)準(zhǔn)）是32位浮點(diǎn)數(shù)，首位用來(lái)保存符號(hào)+/-（用s表示），接下來(lái)的8位用來(lái)保存指數(shù)值e，最后的23位用來(lái)保存有效數(shù)字m（二進(jìn)制0或者1），即：

32位浮點(diǎn)數(shù)

于是，我們的數(shù)字可以表示成。如果你的觀察夠敏銳的話，會(huì)發(fā)現(xiàn)，這種表示方式無(wú)法表示0，這是不能容忍的，所以IEEE又規(guī)定，如果指數(shù)e是0，那么表示的數(shù)字將是，這樣，如果m等于0的話，我們就能表示0了，雖然有+0和-0之分。當(dāng)然，這時(shí)候IEEE又跳出來(lái)了，規(guī)定說+0和-0的表現(xiàn)必須是一樣的，這樣才有了唯一的0值。

絕大多數(shù)情況下，我們的指數(shù)e不會(huì)等于0，所以我們可以放心大膽地只考慮第一種情況?？紤]這樣一個(gè)問題，浮點(diǎn)數(shù)1和離1最近的比1大的浮點(diǎn)數(shù)之間的間隔是多少呢？

我們來(lái)看一下，表示1的時(shí)候，m值是00...00，然后e是127，這樣求出來(lái) $1.0*2^0=1$ 。而比這個(gè)數(shù)稍微大點(diǎn)的數(shù)就是 $m=0...01$ 在第23位的地方是1，這就比1大了，也是比1大的最小數(shù)，它比1大了 $2^{-23}$ 。這也就說明了，我們沒法表示 $1$ 和 $1+2^{-23}$ 之間的數(shù)字。而這個(gè) $2^{-23}$ 就是通常所說的機(jī)器精度（machine epsilon），我們用 $\epsilon$ 表示。

很少有數(shù)字正好落在浮點(diǎn)數(shù)能精確表示的位置上，不在這個(gè)位置上的數(shù)怎么辦呢？就比如說 $1+2^{-25}$ 怎么表示？有兩種方法可以采用，一是多出來(lái)的精度我就不管了，直接舍棄。二是我先看看這個(gè)精確的數(shù)字更接近哪個(gè)數(shù)，然后表示成那個(gè)數(shù)。 $1$ 和 $1+2^{-23}$ 的中間量是 $1+2^{-24}$ ， $1+2^{-25}$ 顯然要比這個(gè)中間量小，所以它會(huì)被表示成 $1$ 。

那么，正好落在中間的數(shù)怎么辦？比如說 $1+2^{-24}$ ?這又是一個(gè)麻煩事，還是得寄出IEEE大法：

IEEE舍入最近法則：
如果第24位,為1，第24位后的所有已知位是0，那么如果第23位是1，就往第23位加1，如果第23位為0，就不加。
如果第24位為1，第24位之后還有至少一個(gè)1，那么就往第23位上加1.
如果第24位為0，那么就舍棄之后的所有位數(shù)，保持第23位的數(shù)不變。

很繞的一個(gè)方法，解釋一下。

情況一、表示 $1+2^{-25}$
因?yàn)檫@個(gè)數(shù)第24位是0，第25位是1，根據(jù)IEEE舍入最近法則，第24位為0的話，保持第23位數(shù)不變的原則，第25位會(huì)被舍棄，而這個(gè)數(shù)就會(huì)被舍入成 $1$ 。

情況二、表示 $1+2^{-24}$
這個(gè)數(shù)第24位是0，之后的所有數(shù)位都是0，而 $1$ 的第23位是0，所以不會(huì)進(jìn)位，導(dǎo)致它也會(huì)被表示成 $1$ 。

情況三、表示 $1+2^{-23}+2^{-24}$
這個(gè)數(shù)的第24位是1，并且之后所有的數(shù)位都是0，而 $1+2^{-23}$ 的第23位是1，所以它會(huì)進(jìn)位，導(dǎo)致最后表示成 $1+2^{-22}$ 。

神奇吧？

誤差的表示

知道舍入誤差產(chǎn)生的原因之后，接下來(lái)就要表示誤差了。在分析誤差的時(shí)候，我們需要兩個(gè)概念：絕對(duì)誤差（absolute error）和相對(duì)誤差（relative error）。

令 $a$ 是精確值，而 $\tilde{a}$ 是浮點(diǎn)值
絕對(duì)誤差 $\delta_a$ 表示為
$\delta_a=|\tilde{a}-a|$
即，浮點(diǎn)值與精確值之差的絕對(duì)值。
相對(duì)誤差 $\delta_r$ 表示為
$\delta_r=|\frac{\tilde{a}-a}{a}|$
即，絕對(duì)誤差與精確值絕對(duì)值之比。

由于舍入的規(guī)則，精確值和浮點(diǎn)值之間的相對(duì)誤差不會(huì)超過半個(gè)機(jī)器精度，即 $\frac{\epsilon}{2}$ ，大小是 $2^{-24}$ 。

用 $fl(x)$ 表示將精確值 $x$ 舍入成浮點(diǎn)值，舍入后的浮點(diǎn)值通常表示成 $\tilde{x}$ ，就是在上面加個(gè)波浪線。然后，用符號(hào)來(lái)表示浮點(diǎn)算術(shù)運(yùn)算：
$a\oplus=fl(a+b)$
$a\ominus=fl(a-b)$
$a\otimes=fl(a\times)$
$a\oslash=fl(a/b)$

誤差計(jì)算

確定了符號(hào)之后，緊接著進(jìn)行誤差的計(jì)算。標(biāo)準(zhǔn)的誤差計(jì)算模型是
$fl(x\quad op\quad y)=(x\quad op\quad y)(1+\mu), \quad \quad |\mu|\leq \frac{\epsilon}{2}, \quad\quad op=+,-,*,/$
每當(dāng)發(fā)生一次浮點(diǎn)運(yùn)算的時(shí)候，引入一個(gè) $\mu$ 的相對(duì)誤差，這個(gè)誤差的大小不超過機(jī)器精度的一半。這是一個(gè)非常合理的模型，用來(lái)分析誤差大小非常合適。

誤差的累積

考慮這樣一個(gè)計(jì)算： $a\oplus b\oplus c\oplus d$ ，假設(shè) $a,b,c,d$ 都是精確值。在計(jì)算機(jī)中，我們可以認(rèn)為它的計(jì)算順序是這樣的 $(((a\oplus b)\oplus c)\oplus d)$ ，于是它的誤差可以表示成：
$(((a+b)(1+\mu)+c)(1+\mu)+d)(1+\mu)$
展開式子可得
$(a+b)(1+\mu)^3+c(1+\mu)^2+d(1+\mu)$
這個(gè)式子的最大誤差是
$|a+b|(1+\mu)^3+|c|(1+\mu)^2+|d|(1+\mu)$
但是這個(gè)表示過于繁瑣，我們考慮誤差不想這么復(fù)雜大計(jì)算這么一個(gè)長(zhǎng)式子，所以把它簡(jiǎn)化為：
$(|a+b|+|c|+|d|)(1+\mu)^3$
雖然擴(kuò)大了誤差，但是簡(jiǎn)化了計(jì)算。還有就是要注意，這里必須要有絕對(duì)值，因?yàn)槿绻?img class="math-inline" src="https://math.jianshu.com/math?formula=a%2Bb%2C%20c%2C%20d" alt="a+b, c, d" mathimg="1">中有負(fù)數(shù)的話，那么相加之后的誤差會(huì)減少，只有當(dāng)這些數(shù)的符號(hào)都相同的時(shí)候，它才是最大誤差，所以我們?cè)谶@里加上絕對(duì)值符號(hào)。比如說，考慮如下的情況：

假設(shè)有兩個(gè)數(shù)相加， $a=3,b=-2,\mu=0.001$ ，計(jì)算表達(dá)式為： $a(1+\mu)^3+b(1+\mu)^2$ ，我們可以得到最終結(jié)果是 $1.005007003$ ，誤差是 $0.005007003$ ，用絕對(duì)值限制的誤差結(jié)果是 $0.015015005$ ，真實(shí)誤差在絕對(duì)值限制誤差之內(nèi)，而如果沒有絕對(duì)值，得到的誤差會(huì)是 $0.003003001$ ，顯然真實(shí)誤差要超過限制了，這是不允許的。

這里要指出書上的一處錯(cuò)誤，書上說如果 $a(1+\mu)^i\oplus b(1+\mu)^j$ 中，a和b的符號(hào)相同的話，那么最大誤差為 $|a+b|(1+\mu)^{i+j+1}$ ，這很明顯太大了。從它的實(shí)現(xiàn)代碼來(lái)看，它用的也不是這個(gè)范圍，而是我上面說的那個(gè)。

對(duì)乘法的計(jì)算來(lái)說，考慮誤差的計(jì)算非常直觀:
$a(1+\mu)^i\otimes b(1+\mu)^j\subset ab(1+\mu)^{i+j+1}$
因?yàn)楸旧?img class="math-inline" src="https://math.jianshu.com/math?formula=a%5Cotimes%20b" alt="a\otimes b" mathimg="1">就要引入 $1+\mu$ 的誤差，所以最后的誤差指數(shù)需要 $i+j$ 再加 $1$ 。

除法的計(jì)算就不那么直觀了：
$\frac{a(1+\mu)^i}{b(1+\mu)^j}\subset \frac{a}(1+\mu)^{i+j+1}$
你沒看錯(cuò)，是 $i+j$ 而不是 $i-j$ ，因?yàn)檫@里的 $\mu$ 有正有負(fù)，它是一個(gè)范圍，所以不能把它消掉，它的誤差和相乘的誤差是一樣的！

一個(gè)簡(jiǎn)潔的記號(hào)

根據(jù)從其他書上借來(lái)的引理，如果 $|\mu|<\frac{\epsilon}{2}$ ，并且對(duì)正整數(shù)n有 $n\mu<1$ ，可以得到以下式子：
$(1+\mu)^n=1+\theta_n，\quad 且|\theta_n|\leq\frac{n\mu}{1-n\mu}=\gamma_n$
這樣， $a(1+\mu)^n$ 就可以簡(jiǎn)單地記作 $a(1+\gamma_n)$ 了。

誤差計(jì)算的實(shí)例

根據(jù)上面的原理，我們可以看到pbrt中有正確的誤差，有錯(cuò)誤的誤差，還有不知道是不是正確的誤差（-_-）！

先看正確的誤差：
用計(jì)算公式計(jì)算出球表面和光線的交點(diǎn)后，還需要執(zhí)行一步，把交點(diǎn)投射到球表面上去，因?yàn)橛捎谡`差的緣故，計(jì)算出來(lái)的交點(diǎn)可能不在表面上。這個(gè)投射的過程是
$x'=x\frac{r}{\sqrt{x^2+y^2+z^2}}$
$x'$ 是投射后的x坐標(biāo)，投射y和z坐標(biāo)的方式一樣。我們來(lái)分析一下這個(gè)操作的誤差
$\begin{equation} \begin{split} x'&=x\otimes r\oslash sqrt((x\otimes x)\oplus(y\otimes y)\oplus(z\otimes z))\\ &\subset \frac{xr(1+\gamma_1)}{\sqrt{x^2(1+\gamma_3)+y^2(1+\gamma_3)+z^2(1+\gamma_2)}(1+\gamma_1)}\\ &\subset\frac{xr(1+\gamma_1)}{\sqrt{(x^2+y^2+z^2)(1+\gamma_4)}(1+\gamma_1)}\\ &=\frac{xr(1+\gamma_1)}{\sqrt{x^2+y^2+z^2}(1+\gamma_3)}\\ &\subset \frac{xr}{\sqrt{x^2+y^2+z^2}}(1+\gamma_5) \end{split} \end{equation}$
其中, $\sqrt{}$ 操作引入的誤差為 $\gamma_1$ ，然后為了開根號(hào)，我們把分母內(nèi)的誤差擴(kuò)大了 $\gamma_1$ ，使得最后的式子非常簡(jiǎn)潔?？梢圆榭磒brt-v3的代碼，我們可以看到：

// Compute error bounds for sphere intersection
Vector3f pError = gamma(5) * Abs((Vector3f)pHit);

沒錯(cuò)，就是 $\gamma_5$ 。

再來(lái)看個(gè)錯(cuò)誤的誤差：
在用矩陣轉(zhuǎn)換頂點(diǎn)的時(shí)候，代碼是這樣的

T xp = m.m[0][0] * x + m.m[0][1] * y + m.m[0][2] * z + m.m[0][3];

而書中的式子是這樣的

注意這里在后面加了個(gè)括號(hào)，代碼中是沒有這個(gè)括號(hào)的，有了括號(hào)之后，計(jì)算出來(lái)的誤差和沒有括號(hào)計(jì)算的誤差是不一樣的。

我們先來(lái)看有括號(hào)之后的計(jì)算過程是什么
$\begin{equation} \begin{split} x'&=((m_{0,0}\otimes x)\oplus(m_{0,1}\otimes y))\oplus((m_{0,2}\otimes z)\oplus m_{0,3})\\ &\subset m_{0,0}x(1+\gamma_3)+m_{0,1}y(1+\gamma_3)+m_{0,2}z(1+\gamma_3)+m_{0,3}(1+\gamma_2)\\ &\subset (|m_{0,0}x|+|m_{0,1}y|+|m_{0,2}z|+|m_{0,3}|)(1+\gamma_3) \end{split} \end{equation}$
最終引入的誤差是 $\gamma_3$ 。

不加括號(hào)是什么樣子？
$\begin{equation} \begin{split} x'&=(m_{0,0}\otimes x)\oplus (m_{0,1}\otimes y)\oplus (m_{0,2}\otimes z)\oplus m_{0,3}\\ &\subset m_{0,0}x(1+\gamma_1)\oplus m_{0,1}y(1+\gamma_1)\oplus m_{0,2}z(1+\gamma_1)\oplus m_{0,3}\\ &\subset (((m_{0,0}x(1+\gamma_1)+m_{0,1}y(1+\gamma_1))(1+\gamma_1)+m_{0,2}z(1+\gamma_1))(1+\gamma_1)+m_{0,3})(1+\gamma_1)\\ &=m_{0,0}x(1+\gamma_4)+m_{0,1}y(1+\gamma_4)+m_{0,2}z(1+\gamma_2)+m_{0,3}(1+\gamma_1)\\ &\subset (|m_{0,0}x|+|m_{0,1}y|+|m_{0,2}z|+|m_{0,3}|)(1+\gamma_4) \end{split} \end{equation}$
沒錯(cuò)，最終引入的誤差是 $\gamma_4$ 。而它的代碼中，引入的誤差卻仍然是 $\gamma_3$ ：

T xAbsSum = (std::abs(m.m[0][0] * x) + std::abs(m.m[0][1] * y) +
            std::abs(m.m[0][2] * z) + std::abs(m.m[0][3]));
*pError = gamma(3) * Vector3<T>(xAbsSum, yAbsSum, zAbsSum);

最后是不知道正確不正確的誤差：
計(jì)算光線和三角形交點(diǎn)的時(shí)候，涉及到的計(jì)算非常復(fù)雜，最終的計(jì)算公式是

但是里面的所有參數(shù)，都是從別的地方計(jì)算出來(lái)的，也就是說這些參數(shù)本身就包含誤差在里面。誤差的計(jì)算過程也弄不清楚，為啥要分別計(jì)算x，y，z分量的絕對(duì)誤差值，然后再計(jì)算t值的誤差，完全搞不懂??！

總結(jié)

說了這么多，你一定覺得誤差非?？植?。其實(shí)不然，因?yàn)椴还苷`差怎么累積，它的量級(jí)也不會(huì)太大，除非你放大誤差。跟分析誤差相比，更應(yīng)該關(guān)注的是算法的穩(wěn)定性和精確度，因?yàn)槿绻惴ú缓茫鼤?huì)放大某些誤差，導(dǎo)致結(jié)果完全不一樣。所以，更多地關(guān)注算法，在算法出現(xiàn)問題的時(shí)候，從誤差的角度去思考一下，是一個(gè)不錯(cuò)的方法。

參考資料

Physically Based Rendering
pbrt源碼，版本3
Accuracy and Stability of Numerical Algorithm
數(shù)值分析（第二版）
Rounding Errors in Algebraic Processes

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【PBRT】《基于物理的渲染：從理論到實(shí)踐》梳理III

【PBRT】《基于物理的渲染：從理論到實(shí)踐》梳理III

誤差的來(lái)源

舍入誤差

誤差的表示

誤差計(jì)算

誤差的累積

一個(gè)簡(jiǎn)潔的記號(hào)

誤差計(jì)算的實(shí)例

總結(jié)

參考資料

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

【PBRT】《基于物理的渲染：從理論到實(shí)踐》梳理III

誤差的來(lái)源

舍入誤差

誤差的表示

誤差計(jì)算

誤差的累積

一個(gè)簡(jiǎn)潔的記號(hào)

誤差計(jì)算的實(shí)例

總結(jié)

參考資料

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av