2D Graphics

Graphics

Graphics是繪畫、製圖的意思。左圖是2D繪圖、右圖是3D繪圖,相信大家一眼就能看出差異:

Image的演算法著重於讓既有圖片產生變化,Graphics的演算法專注於從無到有產生圖片。兩者相輔相成、密不可分。

2D Graphics

先前已經介紹過「像素Pixel」。2D繪圖就是逐步設定每個像素的RGB值,呈現我們想要的圖案。

以人工方式,一點一點設定每個像素的RGB值,稱作Pixel Art,常常出現於電玩遊戲及牆壁磁磚。

以演算法,一點一點設定每個像素的RGB值,則是這裡要談的重點。

2D Graphics相關資源

C與C++沒有2D繪圖的函式庫。更高階的程式語言都有內建2D繪圖函式庫,例如Qt的QPaint、C#的Graphics、Java的Graphics。作業系統也有內建2D繪圖函式庫,例如Windows的GDI+

知名的2D繪圖工具,例如HTML5 Canvas

知名的2D繪圖軟體,諸如Microsoft PaintAutoCADMicrosoft VisioAdobe Illustrator等等。

Shape Rendering

Shape Rendering

前言

想要畫一張複雜的圖,無論是藝術家還是數學家,都是從簡單的幾何形狀:直線、方、圓開始。本篇文章將介紹如何繪製簡單的幾何形狀。

Shape Rendering的演算法已經在顯示卡上燒成電路、並且包裝成函式庫。前人種樹後人乘涼,我們大可不必痛下苦功編寫程式碼。然而本篇文章不談函式庫。

Shape Rendering擁有相關的檔案格式SVG。然而本篇文章不談資料結構。

操控鍵盤滑鼠即時繪製圖形,我們需要了解監聽和處理事件的機制。然而本篇文章不談事件處理。

繪製直線、曲線、方形、圓形等等圖形,管理鍵盤、滑鼠、視窗等等介面,我們需要規劃編排大量程式碼。然而本篇文章不談物件導向。

Shape Rendering的軟體已經發展成熟。然而本篇文章不談如何製作軟體,也不談如何使用軟體。

像素

直線

給定線段的兩個端點,如何找到線段對應的像素呢?

腦筋靈活的讀者肯定馬上聯想到線性內插。不過像素看起來零零散散的,根本沒有連成一線。

DDA Algorithm則是計算兩個端點在X軸、Y軸上的差距,取較大者作為像素數量,使得像素互相碰觸。另一方面,從逐點內插,改為預先計算斜率、逐步累加,大幅降低了運算量。

Bresenham's Algorithm搞定了浮點數誤差。

Wu's Algorithm加入了抗鋸齒效果。

曲線

大家習慣使用Bézier Curve

參數:窮舉各種參數值,根據貝茲曲線的特性,相鄰控制點,反覆取加權平均值,直到得出一點。缺點是曲線不連續。

中點:分治法,貝茲曲線從中切開,分頭遞迴下去。詳情是,相鄰控制點,反覆取中點,直到得出分界點,切開曲線;分頭遞迴下去,直到分界點停留在相同像素。

外插:以泰勒級數得到外插公式。優點是計算速度快,缺點是曲線不連續。

解方程式:窮舉水平線,求得水平線與曲線的交點。

還有加粗的貝茲曲線演算法抗鋸齒的貝茲曲線演算法

手繪線

其實就是一大堆的滑鼠座標位置,通常會斷斷續續不相連。

可視作Polyline的頂點。然後套用減少頂點的演算法,甚至以Bézier Curve做為模型。一方面平滑線條、一方面節省記憶體。

畫四條直線。或者視作簡單多邊形!

Bresenham's Algorithm。可以推廣為橢圓和拋物線。

簡單多邊形(窮舉法)

分為空心和實心。空心很簡單,多邊形每條邊分別畫直線。

實心複雜多了。填充一個多邊形裡面所有的像素,讓整塊多邊形擁有顏色。多邊形以頂點座標的形式儲存,頂點座標是浮點數。像素座標則是整數。

最簡單的方式是試誤法:窮舉畫面上所有像素,運用「判斷點在多邊形內部」的演算法,若在內部則填色。

時間複雜度是O(XYN)。其中X與Y是畫面的長與寬,N是簡單多邊形的頂點數目。

簡單多邊形(Flood Fill Algorithm)

還有沒有更好的方法呢?我們可以把問題分成兩個步驟:一、先鉤勒多邊形的邊界;二、再填充多邊形的內部。一旦有了邊界,就不必費心判斷像素是否在多邊形內。

鉤勒的部分,運用畫直線演算法即可。填墨的部分,讀者應該馬上就聯想到「Flood Fill Algorithm」,遞迴往四方向填墨。

鉤勒需時O(N+B),填墨需時O(B+4A),總共的時間複雜度是O(N+B+A)。其中N是多邊形的頂點數目,B是多邊形邊界的像素數目,A是多邊形內部的像素數目。

凸多邊形(Scanline Fill Algorithm)

一、求出凸多邊形的最低像素和最高像素,把凸多邊形的邊,分為左邊界和右邊界。二、建立兩條陣列,陣列大小等同於凸多邊形的垂直高低差,用來儲存垂直方向各個像素的左邊界與右邊界。三、依序窮舉凸多邊形的邊,把每條邊碰到的像素位置算出來,作為邊界值,存到陣列。四、水平方向,一條一條填滿多邊形。

鉤勒需時O(N+2B),填墨需時O(2B+A),總共的時間複雜度是O(N+B+A)。

雖然表面上Flood Fill Algorithm與Scanline Fill Algorithm的時間複雜度一模一樣,但是實際上Scanline Fill Algorithm的速度比較快。

UVa 143 356

簡單多邊形(Scanline Fill Algorithm)

http://alienryderflex.com/polygon_fill/

Font Rendering

Font Rendering

Character

Character就是電腦符號。譯作「字元」或「字符」。

電腦符號都有編號。世界公定的編號方式是Unicode。例如第30399號是「算」,第9775號是「☯」。電腦符號包括了世界各國文字、數字、圖示、表情符號等等。

電腦符號必須編碼,節省儲存空間。Unicode有著UTF-8和UTF-16兩種主流的編碼方式。

字元編碼,是編碼理論的範疇。字元操作,是字串理論的範疇。字元顯示,是計算機繪圖的範疇,是我們現在要談的內容。

Font

Font就是文字的造型。譯作「字體」或「字型」。

從書寫的觀點:中文字體有楷書、行書、草書、隸書、篆書等五大類,有名的楷書如顏真卿、柳公權等等。字體是書法家發明的。

從電腦的觀點:繁體中文字型有標楷體、細明體、微軟正黑體等等。英文字型有Times New Roman、Verdana、Arial等等。字型是美術設計師和程式設計師發明的。

只要有文字的地方,通常都能更換字型,例如文字編輯器、瀏覽器、作業系統、命令提示字元。電腦可供使用的字型,主要是看你的電腦安裝了哪些字型。有專門製作字型、販售字型的公司,例如專精繁體中文字型的JustFont文鼎華康。亦有人號召製作字型,例如文泉驛

電腦顯示字元,必須透過字型。每一套字型都只替一部分的字元設計造型,例如Times New Roman只設計了英文字母、拉丁字母、少量的特殊符號,例如微軟正黑體只設計了英文字母、中文字、少量的特殊符號。一套字型當中,沒有設計造型的字元,就無法顯示,或者是顯示問號、空白方格等等莫名其妙的符號。儘管現今沒有任何一套字型涵蓋Unicode規定的所有字元,不過其實也不需要一套萬能的字型。對於沒有設計造型的字元,作業系統將另尋其他字型。

字型由作業系統控管。想要讓視窗程式顯示特定字型,土法煉鋼的方式是Windows API,輕鬆寫意的方式是程式語言內建的函式庫。想要讓網頁顯示特定字型,利用CSS的font-family即可。

Glyph

接著到了本篇文章的主角「字形」。首先玩個小遊戲吧!拖曳控制點,按Enter評分。美感和眼力必須很傑出。設計師的日常。

「字形」就是單獨一個字元的形狀。由演算法自動調整形狀,或由文字設計師手動調整形狀。

Glyph的資料結構

三種:點陣字dot-matrix、筆畫字stroke、輪廓字outline。

點陣字:用黑色方格(像素)拼成字形。

電腦已經淘汰點陣字型了,例如Fixedsys。然而有些字型為了支援極小尺寸,仍會搭配點陣字型,例如文泉驛點陣宋

點陣字使用最多的地方不是電腦,而是大眾運輸的LCD跑馬燈。

筆劃字:直覺的方式。特別適合漢字。

記錄起點座標、終點座標、寫法(永字八法:側勒努趯策掠啄磔)(英文字母筆劃剖析)、曲率參數、變換矩陣。最後以演算法加粗筆劃,生成字型。優點是容易創造新字型,缺點是美感不佳。累死工程師、悶死設計師。

可惜的是,我們無法獲得筆劃資料。中文筆畫資料,屬於商業機密,更有專利保護。大家不得其門而入。例如王漢宗字型侵權案,個人猜測是從神秘管道得到筆劃資料,再自創加粗筆劃的演算法。

可惜的是,我們無法得知筆劃加粗的演算法。即便是開源字型,也從未公開演算法。必須跟字型公司簽技術合作。

這多少阻礙了組字造字文字資料庫筆劃檢索手寫辨識的進展。

輪廓字:公定的方式。現今字型皆是輪廓字。

輪廓由許多線條組成,線條一律是「直線線段:兩個端點」和「Bézier Curve:兩個端點與兩個控制點」。最後以演算法填充輪廓內部,生成字型。

幸運的是,我們可以獲得輪廓資料。安裝免費開源的字形編輯軟體FontForge,下載免費開源的字型思源黑體文泉驛正黑,將字形匯出成.eps或.svg檔案即得。上面的「算」就是這樣來的。

注意到,字型都有著作權,未經授權不可使用字型檔案裡面的數據,即使免費。讀者做實驗時,一定要記得選擇免費且開源的字型,以免觸法。

輪廓字的檔案格式主要有兩種:囊括所有格式的OpenType(.otf)、早期的TrueType(.ttc .ttf)。OpenType是當今主流,網路上有不少資訊。如果你有志鑽研字型渲染,可以自己寫程式存取OpenType檔案,也可以參考開源的字型渲染引擎FreeType

em square:字形的編輯區域

活字印刷當中,em是指鉛字寬度。電腦字型當中,em square是指字形的編輯區域。就這樣。

outlining:描繪輪廓

運用上個章節的繪製直線與繪製曲線演算法即可。

描繪輪廓目前沒有公定標準。即便是相同字型相同字形,在Firefox、Chrome、Windows、OS X的顯示結果通常略有不同。不同的字型渲染引擎,呈現不同結果。你也可以自己寫一個。

為了讓輪廓座標變成像素座標,這裡介紹一下pt和dpi。

電腦字型大小,單位是pt (PostScript point),是長度單位。72pt = 1英吋,pt除以72得到英吋。電腦字型通常預設12pt。

長度變成像素數量,單位是dpi (dot per inch),每英吋多少點(像素)。電腦螢幕通常是96dpi,實體印刷至少是300dpi。

比方說,12pt字型,96dpi解析度,一個字形的邊長含有12 ÷ 72 × 96 = 16個像素。

假設em square的邊長是1024。輪廓座標(x,y),等比例縮放得到像素座標(round(x÷1024×16), round(y÷1024×16))。

filling:填充輪廓

運用上個章節的Scanline Fill Algorithm。輪廓不能交叉重疊,以利判斷內外。

如果讓輪廓具有方向性,順時針為正,逆時針為負,則得以設計聯集與差集。

overlap removing:重疊的輪廓,簡化成一個輪廓

為了順利填充輪廓,凡是輪廓交叉重疊,就必須重新整合。

有兩種狀況:一個輪廓自身交叉、兩個輪廓互相重疊。

需要處理的事情:求交點、求聯集或差集、重新安排頂點順序。需要的演算法:線段交點Bézier Curve交點多邊形交集。不太容易實作,讀者可以挑戰看看。

字形編輯軟體有此功能,節省設計師的作業時間。

hinting / grid fitting:微調字形位置

像素座標只能是整數。座標四捨五入變成整數,可能往左往下跑、可能往右往上跑,筆畫粗細有所改變。尤其是字形縮放大小,例如從12pt到14pt,問題更加嚴重。

像素大小固定。當字形縮小至非常小,例如6pt,所有筆劃通通黏結在一起。此時整個字形都得重新設計,甚至改成點陣字。

目前已經有演算法,可以自動微調字形位置。不過凡事總有例外,仍需設計師人工檢視、手動微調。各種常見縮放尺寸,都得一一檢視。中文數萬字,一字一字做,一日一日做,愚公移山、精衛填海!

anti-aliasing:微調字形邊緣的像素數值

在字形邊緣設定漸層顏色,使得字形邊緣柔順、清晰。

像素整齊排列。對於一條斜線,黑白顯示器,無可避免地,一定有鋸齒;灰階顯示器、彩色顯示器,則可以微調鄰近像素數值,達到平滑效果。

三種演算法:面積、距離、分割像素。

面積:像素視作正方形。如果字形佔據40%的面積,就將數值設定為40%,也就是255 - (255 × 40%) = 153。

距離:像素到輪廓的最短距離。貝茲曲線轉換成多項式,再解方程式(求根)求得最短距離。也可以用分治法

分割像素:彩色顯示器,一個像素由RGB三個元件組成,調整RGB亮度比重,強調邊緣。缺點是邊緣五顏六色,相當刺眼,不是每個人都喜歡。知名演算法是微軟ClearType。

metrics:設定字形間距

http://www.freetype.org/freetype2/docs/glyphs/glyphs-3.html

字形的部分已經介紹完畢了,接下來是排版的部分。

FreeType的說明文件已經有精美圖片。這裡就不重畫了。

ligature / kerning:微調字形間距

比方來說,AV合在一起時,視覺感受是留白太多,需要更緊密一點。AB、AD不需要更緊密,保持原本排版即可。

解法是事先設定特殊組合。OpenType支援此設定。屬於文字處理的範疇。

另外還有一種情況,出現於阿拉伯文、泰文等等。這些語言根據語意,銜接或斷開字形。

解法是剖析語意。OpenType沒有此設定,由排版引擎自行實作。屬於自然語言處理的範疇。

未涉及的主題

因為我沒有跟字型公司簽技術合作,所以知道的事情有限。

一、輪廓字的編輯介面。

二、輪廓字、筆劃字、點陣字之間的轉換。華康有個專利,演算法是迴歸

三、拆字組字。簡化字型製作流程。

四、調字。根據環境、根據版面,自動調整字形

五、手寫字形。工程師詳細演算法)和設計師詳細流程)有著不同的策略。

六、壓縮。減少字型檔案大小。例如Compact Table Format和MicroType Express。

七、列印文字。印表機韌體設計。

Font Design

這是設計師的專業。已有人寫書拍片,我就不班門弄斧了。

演算法生成的字形太過呆板例如墨字的四個點如何點)。目前的作業流程是:先由工程師產生大致輪廓,再由設計師調整細節。

繁體中文的筆劃寫法,台灣政府有訂立標準。不過政府標準不見得是好看的也不代表是正統的

Typeface Design / Typography Design

也許可以看看spiro curve文字雲筆劃裝飾

Math Rendering

畫數學式子與畫字形,原理相同,只是還要再解決一個問題:數學式子的資料結構為何?目前最流行的方式,是用純文字記錄一道算式,所採用的文法是TeX的語法。

讀者可以參考MathJax。

Web Rendering

https://en.wikipedia.org/wiki/Web_browser_engine

3D Graphics

3D Graphics

當今科技,沒有任何設備可以清楚呈現3D物體。

退而求其次,以2D圖片呈現3D物體。目前公認的做法:將3D模型投射到2D圖片上面,逐一設定每個像素的RGB值。

3D物體投射到2D圖片,兩種方式。

Orthogonal Projection:平行投射至圖片,夾角是垂直90度。這個方式非常簡單,卻有一個嚴重的問題:物體不論遠近都一樣大,缺乏真實感。

Perspective Projection:聚焦於圖片後方一點:遠的物體小、近的物體大,稍微符合人類視覺觀感。它是主流的方式,此處只介紹它。

聰明的讀者肯定馬上聯想到物理課的「針孔成像」及「攝影機」。雖然Perspective Projection與「針孔成像」都有聚焦的概念,但是兩者不盡相同。

抑或聯想到美術課的「透視圖」。雖然Perspective Projection與「一點透視圖」的外觀相同、原理相似,但是兩者的製作方式截然不同。

Perspective Projection細分兩種實作方式:

相機到物體:窮舉每一個像素,從焦點朝像素射出射線,找到對應的物體。速度極慢,用於電影動畫、擬真圖片。

物體到相機:窮舉每一個物體,從物體射出射線至焦點,找到對應的像素。速度較快,用於電玩遊戲、虛擬實境。

Camera」與「Model」的觀念,源自其他領域。

ICPC 5100

3D Graphics相關資源

3D繪圖廣泛應用於電腦遊戲、電影特效、電視廣告、模型設計、建築設計、醫學影像等等。像是李安引進台灣的Rhythm & Hues Studios公司、比如CG Taiwaner教學網站,都屬於3D繪圖領域。

知名的3D繪圖函式庫,例如OpenGL與Vulkan與GLFWDirect3DPBRT。瀏覽器的3D繪圖函式庫,例如WebGLthree.js。程式語言通常沒有內建3D繪圖函式庫,必須另外安裝。

知名的3D模型資料,例如Infinite-Realities

知名的3D渲染軟體,例如Maxwell Render、LuxRender、Octane Render。

http://www.cmlab.csie.ntu.edu.tw/~ming/courses/icg/
http://www.csie.ntu.edu.tw/~cyy/courses/rendering/
http://www.raytracegroundup.com/
http://www.scratchapixel.com/
http://www.crcpress.com/p/book/9781439827376
http://graphics.csie.ntu.edu.tw/~robin/courses/gm13/
http://cs.brown.edu/courses/cs123/lectures.html
http://graphics.stanford.edu/courses/
http://graphics.csail.mit.edu/courses

Mesh Rendering: Camera to Model

Mesh Rendering

這裡再提供一個更清楚的動畫

Model

將物體表面簡化成大量的平坦的多邊形,再運用「多邊形三角剖分」切割成大量的三角形,得到Mesh。

替現實生活的物體建立Mesh,是一套複雜的學問。所幸我們已經有現成的模型可以使用。例如此處的模型是Utah Teapot

Mesh由許多三角形組成。一個三角形擁有三個頂點座標(暨法向量)、正面顏色、背面顏色。

三角形的頂點順序,決定了三角形的正面:正視三角形的正面,我們習慣讓三角形頂點呈逆時針順序。依照頂點順序計算「叉積」,得到三角形的正面的法向量。這是大家約定俗成、心照不宣的規矩。

Mesh的資料結構通常是:一個陣列記錄每個點(暨法向量)、一個陣列記錄每個三角形的三個點的編號。由於三角形經常共用頂點,因此兩層式的資料結構,得以節省記憶體空間。

不過為了方便起見,以下採用笨蛋方法。

UVa 10711

Camera

替相機設定三個單位向量:長的方向、寬的方向、面對方向。

求得Mesh中心點,倒退一萬步,作為焦點的位置。

Ray Casting

建立焦點往像素的射線,找出第一個射中的三角形。

一、以相機的三個單位向量,建立焦點往像素的射線。

二、窮舉三角形。針對每一個三角形,以「平面與直線交點」求得交點和距離,隨時記錄最短距離。為了避免緩慢的sqrt運算,我們不求直線距離,而是求dirz方向的距離、也就是深度。

最後一行程式碼可以簡化。* dt / dv可以提到dot外面。view是由dirx、diry、dirz組成,這三個向量互相垂直;view投影到dirz上,不需要看dirx和diry,只需要看dirz方向有多少投影量,點積結果顯然是depth。

depth是定值。有些人為了加速,甚至不乘上depth,只求倍率。倍率1.0剛好位於圖片上。

以倍率輕鬆求得交點。

三、以「判斷點在凸多邊形內部」,判斷交點是否在三角形內部。三維版本,叉積改為三重積,三角形面積改為四面體體積。

Ray Casting: Bounding Volume Hierarchy

若想加速,將所有三角形存入「Bounding Volume Hierarchy」資料結構,依照區域分類所有三角形。

若想繼續加速,每個像素平行計算。實務上是運用顯示卡的GPU,撰寫CUDA程式碼,大幅加速。

UVa 12312

繪製三角形!

此處的模型是Cornell Box。運用OpenGL建立視窗,將模型畫在圖片上。

窮舉每個像素,建立焦點往像素的射線;窮舉每個三角形,找出第一個射中的三角形,取得三角形顏色。

相機、矩陣、圖片函式庫,三種不同的座標系統,必須小心。

Mesh Rendering: Illumination

Illumination

直接取用三角形的原始顏色,外觀呆板,缺乏層次。真實世界,顏色繽紛,是因為光線照射。現在我們要引進一套光線系統,讓三角形華麗動人、閃閃發光!

一、Light。光線的來源。

二、Optics。光線射中物體之後,物體影響光線的機制。

三、Material。光線射中物體之後,光線亮度與彩度變化。

四、Ray Tracing。追蹤光線軌跡。運算量最大的地方。

五、Sampling。設定光線數量、方向,使圖片外觀柔順。

這套光線系統源自物理,源自人類對於世界現象的觀察。如果你熟悉物理理論、擅長物理實驗,可以創造更細膩的方式。

Light

point light (omni light):點光源。例如燭火、燈泡。
cone light (spotlight):圓椎光源。例如聚光燈。
directional light (collimated light):有向光源。例如遙遠的太陽。
area light:區域光源。光源們組成一大片面積。
model:物體當作光源,表面發光。
environment light:環境光源。光源們組成球面,包覆在場景外圍。

實際範例請見此。數量、位置、方向(張開角度)、亮度、彩度,五個要素。光源還可進一步組成面,添增變化。

妥善設置光源,精心營造氣氛。甚至可以實地拍攝天空的照片作為光源,諸如朝霧夕霞、天光雲彩,營造真實感。

Optics

emission:發光。例如螢光棒。
absorption:吸收。日常生活常見物體都是。
reflect:反射。例如鏡子、水中倒影。
refract:折射。例如魚缸、晶鑽。
scatter:散射。例如葉隙光、雲隙光、頭髮。
diffract:繞射。很少見。

物體影響光線。或者簡單想成:光線碰撞物體,產生變化。

光波有兩個要素:頻率(彩度)和振幅(亮度)。

一道光通常由大量頻率組成,各種頻率有各種振幅。物體影響光線,不會改變頻率,而會改變各種頻率的振幅大小、行進方向。

發光吸收是振幅大小變化,反射折射散射繞射是行進方向變化。

Optics的數學模型

一、考慮反射角(等於入射角)、折射角(根據介質係數)。入射折射反射都在同一平面。適合當作業。

二、考慮各種反射方向、折射方向。此模型稱作BSDF = BRDF + BTDF。雖然光線遵守物理定律、光線隨從明確軌跡,但是混雜了大量複雜結果,才是人類視覺觀感:光線不是一條而是一束,照射處不是一點而是一塊,介面不是一個平面而是很多曲折,射出不僅一個方向而是很多方向。例如虹彩

三、考慮地點差異。此模型稱作BSSRDF。光線在介質內不斷散射,從別處散逸而出。光線的散射、粒子的擴散,兩者有著異曲同工之妙。距離交點越遠,射出機率越小,近似常態分布。亦可想成表面套用Gaussian filter。例如濁液、皮肉、頭髮。

四、考慮時間差異。光線被介質吸收,緩緩射出。例如磷光、螢光。

五、考慮各種頻率。白光反射時,部分頻率消失(光的吸收);白光折射時,各種頻率錯開(光的色散)。接近真實了。例如dichroismpleochroism

考慮越多,運算量、記憶量越大。四和五,當今硬體設備難以即時實現,除非取巧。

Material

人類視覺透過複雜機制,揉合振幅和頻率,得到顏色。

工程師便宜行事,將光的要素,從頻率和振幅,換成顏色和亮暗程度。再瞎掰出:顏色×亮暗程度=呈現顏色。儘管不切實際,但是容易計算。

工程師便宜行事,反射光、折射光,顏色不變動,亮暗程度才變動。一種入射方向,擁有多種反射方向、折射方向,每種方向各有亮暗程度。方向以經緯度表示,亮暗程度以函數表示。函數有形容詞。

  diffuse / matte:漫射。霧面、粗糙表面。
                   反射光分散,朝不同方向。例如路面、牆壁、紙張。
specular / glossy:鏡射。鏡面、光滑表面。
                   反射光集中,朝同一方向。例如金屬、塑膠、磁磚。

給定一種素材,有物理儀器可以測量函數。採用實體的測量數據,便可模仿真實世界。

除了採用實體的測量數據,亦可採用虛擬的數學模型。現今已有多種數學模型,各有不同視覺效果。

Ray Tracing

一、光線接觸介面才有變化,產生反射折射。適用固體,例如居家擺設。演算法原理類似狀態空間搜尋

   ray tracing: 焦點出發。
                光學:僅考慮反射角、折射角。
  path tracing: 焦點出發(亦可焦點和光源雙向出發)。
                光學:考慮各種反射方向、折射方向。
     radiosity: 光源出發,走K步,每步皆留下一些光子。
                焦點出發,走一步,以附近光子數量,決定像素亮度。
               (實作:每步結束後,另走一步到焦點,累加像素亮度。)
               (I^1 + I^2 + I^3 + ... + I^k)
photon mapping: 光源出發,走一步,留下一個光子。
                焦點出發,走K步,以附近光子數量,決定該步的光線亮度。
一、從焦點、光源出發,持續反射、折射,追蹤光線軌跡。
  每次接觸介面當作一步。
二、從焦點出發時,每一步窮舉所有可能的入射方向。
  從光源出發時,每一步窮舉所有可能的出射方向。
  由於不可能完全窮舉,所以採用取樣,後面章節會介紹。
三、焦點、點光源僅有一點,通常瞄不準、追蹤不到。
  因此最後一步必須無視物理定律,刻意走向焦點、點光源。(global illumination)
  區域光源則無此問題。
四、為了減低計算量,通常只走K步。
  又為了減少bias,以固定機率決定要不要走下一步。(Russian roulette)
  又為了增加實感,累計一步、兩步、……、K步的結果。

二、光線接觸介質即有變化,於介質中不斷反射折射散射。適用氣體液體,例如雲霧、牛奶。依照濃度不同,有著各種演算法,但是皆昧於物理事實。

稀薄:視作濾心。穿過越多介質,亮暗程度變化越大。
   以介質厚度當作亮暗變化程度。
中等:視作粒子。氣體處處都是完美漫射。光線為直線,只散射(轉折)一次。
   窮舉視線的每一個位置,嘗試轉折至光源。
濃稠:視作固體。光學模型:考慮入射、出射地點差異。
   測量BSSRDF,套用固體的演算法。

Ray Tracing的常見伎倆

    ambient occlusion: 遮光。擋住光線,產生陰影。
                       例如鼻翼的陰影、門縫。
subsurface scattering: 透光。光線於半透明介質內散射,深層與淺層的光線重疊。
                       例如白裡透紅的肌膚、透光的窗簾、濁液、葉片、玉。
soft light/shadow: 柔光、柔影。
從交點發出大量射線,判斷打中多少光源,決定亮度。
volumetric light/shadow: 光芒、陰暗。例如百葉窗散落的光、積雨雲散落的陰影。
從光源發出大量光線。再從焦點發出大量射線,判斷打中多少光線,決定亮度。
environment mapping: 物體周圍擺放素材圖片,映射在物體上。
shadow mapping: 預先計算物體陰影範圍,貼上陰影圖片。

電腦所能繪製的現象十分稀少。至今仍有許多光學現象,繪製尚未成功,同志仍須努力。

UVa 12313

Sampling

一、反射折射:追蹤光線軌跡,列舉數種可能的方向。

二、發射:增加焦點射向像素的光線數量,射中的顏色們取平均值,產生平滑、模糊、抗鋸齒效果。

anti-alias: 增加亂數數量,取平均值。
motion blur: 根據物體速率,決定亂數偏移量。
depth of field: 根據物體遠近,決定亂數偏移量。

射線數量是一個自訂常數,射線方向的偏移量是一群二維亂數。光線反射折射,採用球形;光線發射,採用正方形。

繪製三角形!

光源:一個點光源。光學:僅反射(入射角等於反射角)、無折射。材質:完美漫射。光線追蹤演算法:Ray Tracing。無取樣。

圖片很陽春。如果想看更逼真的圖片,可以上網搜尋,或者自己動手畫畫看吧!

Mesh Rendering: Texture

Texture

以上介紹了光線照明系統,以下介紹表面紋路系統。

物體表面通常不是均一顏色、不是均一高低。工程師的解決之道:自訂表面紋理。紋理包括了顏色、高度、法向量等類型。

Texture Generation

製造紋理的方法有:請攝影師拍攝實際照片,請設計師繪製美工圖片,請工程師研發演算法。

製造紋理屬於圖片處理的範疇。原理是運用雜訊,產生紋理的顏色、高度、法向量等等,營造逼真畫面。讀者不想自行製作紋理的話,亦可下載現成的紋理(但是只有顏色)

Texture Mapping

將紋理貼上物體表面。物體表面、紋理,建立座標對應關係。請參考這篇文章

簡易的方式是:物體的每個三角形(四邊形),各使用一片正方形紋理。直接實施三角形內插(四邊形內插),得到座標對應關係。請參考Image Warping,屬於圖片處理的範疇。

Texture Mapping: Texture Coordinates

將紋理布置於物體周圍。重設紋理的座標系統。

正方體:使用六片紋理,作為正方體的六個面。
圓柱體:使用一片紋理,左右銜接。(座標對應:長寬對應高度和角度)
半球體:使用一片紋理,中央凸出。(座標對應:長寬對應經緯)

Texture Mapping: Mesh Parameterization

將紋理映射至物體表面。重設物體表面的座標系統。

攤平:物體從某處剪開、攤平,得到對應關係。
   周界可以盡量調整成紋理形狀、內界可以盡量調整成整齊網格。
中心:源自物體中心的放射線,擊中表面和紋理,得到對應關係。
光學:源自焦點的射線,經由反射擊中紋理,得到對應關係。

Texture Filtering

bilinear filtering:只有一張紋理。採用image warping改變紋理形狀。
trlinear filtering:考慮相機遠近,預先製作各種大小的紋理。scale transform。
anisotropic filtering:考慮相機角度,預先製作各種視角的紋理。shear transform。

二維紋理的映射當中,紋理與表面的大小形狀,經常不相符,必須調整紋理的大小形狀。

改變紋理的大小形狀,紋理可能出現鋸齒、可能失真。仿效內插的觀念,讓紋理柔順平滑。

Texture Data Structure / Texture Atlas

   mipmap: 紋理預先縮放成各種比率,以應付各種遠近距離的呈現觀感。
heightmap: 附帶高度資訊。

紋理的資料結構。我沒有研究,請參考這篇文章Wavefront的obj檔案格式

Texture Embossing

重新設定表面法向量、表面高度,令表面凹凸不平、有立體感、有陰影,宛如壓印。請參考這篇文章這篇文章

bump mapping: 表面是平面,重新設定每一處的高低。
normal mapping: 表面是平面,重新設定每一處的法向量。
displacement mapping: 三角形頂點沿法向量移動。
parallax mapping: http://exibeo.net/docs/parallax_mapping.pdf
relief mapping: http://graphics.cs.brown.edu/games/SteepParallax/index.html

Normal Interpolation

重新設定表面法向量,使其圓滑。

想得到三角形上某一點的法向量:

一、求得三角形的正面的法向量。三個頂點叉積,即得。

二、求得三角形的三個頂點的法向量。一個頂點有許多個相鄰的三角形。相鄰三角形的法向量相加之後,當作該頂點的法向量。然而模型本身多半已經提供精準的頂點的法向量,可以省略這兩步驟。

三、求得三角形的任意一點的法向量。想要求得內插比重,直覺的方式是:將線性內插重新表示成線性變換矩陣,然後求反矩陣──然而當三角形與原點共平面,反矩陣就不存在了。推薦的方式是「Barycentric Interpolation」,三塊小三角形的面積,就是內插比重。

法向量們方向漸層改變。打光後,三角形表面彷彿圓滑凸起。

形狀看似改變了,但是實際位置沒變。物體邊緣會產生破綻。

Normal Encoding

將一個法向量重新表示成一個浮點數,節省儲存空間。請參考這篇文章

Mesh Rendering: Model to Camera

Perspective Projection

如何計算三維空間的一個點,在圖片上對應的XY座標呢?

先以「點積」求得三個方向的投影量、即是真實距離x y z。

再以「相似三角形邊長成比例」的原理,藉由z和depth的比例,求得投影距離x' y'。x z構成的三角形,縮小為depth/z倍,得到x';y z構成的三角形,縮小為depth/z倍,得到y'。

注意到,真實距離和投影距離都是以圖片中心為基準,距離可以是負值。最後我們調整投影距離成為圖片座標。

繪製空心三角形!

此處的模型是台大資訊系

窮舉每個三角形,把三角形三個頂點投射到圖片上,求得圖片座標。運用OpenGL畫出每個三角形的外框,最後形成了「線框(wireframe)圖」。

Polygon Filling

大家應該會畫空心三角形了。現在來畫實心三角形吧!

把三角形三個頂點投射到圖片上,求得圖片座標。套用填充多邊形演算法,把三角形畫到圖片上。

鉤勒線段的部分,採用了「線性內插」,求得準確的三角形邊界;然後運用ceil和floor函數,讓相鄰三角形的接縫密合。

Visible Surface Determination

近的三角形,必須擋住遠的三角形。求得三角形與焦點的距離,才能判斷誰近誰遠。

從焦點往圖片像素的射線,射向三角形,以「三角形與直線交點」求得距離。為了避免緩慢的sqrt運算,我們不求直線距離,而是求dirz方向的距離、也就是深度。

最後一行程式碼可以簡化。* dt / dv可以提到dot外面。view是由dirx、diry、dirz組成,這三個向量互相垂直;view投影到dirz上,只需要看dirz方向有多少投影量,點積結果顯然是depth。

depth是定值。有些人為了加速,甚至不乘上depth,只求個縮放倍率。倍率1.0剛好位於圖片上。

一邊填充三角形,一邊判斷深度。三角形的交接處,可以優先選擇靠近焦點的三角形,或者為了爭取速度而不做判斷。

古人曾經使用另一種演算法:運用「BSP Tree」預先排序所有三角形,依照先後順序繪製,就不必判斷遠近。但是無法處理三角形互疊、無法處理相機移動,速度也極慢,現今沒人用。

Illumination

此處介紹懶惰的打光方式。

光線與表面垂直,感覺最亮;光線與表面平行,感覺最暗。光線與表面的夾角大小,決定了亮暗。更精準來說,光線的垂直分量大小,決定了亮暗。

光線向量與法向量的點積,即是亮暗程度。設定為單位向量,亮暗程度就是0.0~1.0之間的數字。至於法向量可以使用上個章節提到的演算法求得。

ambient:物體發光,亮度為定值。
diffuse:光線向量與法向量的點積,作為亮暗程度。
specular:視線向量與反射向量的點積,作為亮暗程度。
          取k次方,夾角越小、亮度驟升。
modified specular:「視線向量與光線向量的中垂線」與法向量的點積,作為亮暗程度。
                   取k次方,夾角越小、亮度驟升。
Phong model = c1⋅ambient + c2⋅diffuse + c3⋅specular
Blinn-Phong model = c1⋅ambient + c2⋅diffuse + c3⋅modified specular

Shading

素描的shading,著重線條樣式;電腦繪圖的shading,著重填充方式。

flat shading:求三角形任一點的顏色(例如重心),其餘通通一樣。
Gouraud shading:求三角形三頂點的顏色,其餘線性內插。
Phong shading: 求三角形每一點的顏色,法向量內插。

繪製實心三角形!

Culling

backface culling:預先剔除物體背後的三角形。
occlusion culling:預先剔除被其他物體遮住的三角形。
visibility culling:預先剔除視野範圍(field of view)之外的三角形。

culling有三種,這裡只介紹backface culling。

如果物體有著密封外殼,背向焦點的三角形一定被遮住;如果物體有著破洞外殼、物體是一張薄紙,背向焦點的三角形才有機會露臉。

如果物體有著密封外殼,我們可以剔除背向焦點的三角形,避免無謂的填充,加快程式速度。

UVa 12628

Clipping

裁切有兩種。第一種是設定視野範圍(Field of View)。

我們可以設定左、右、上、下、遠、近邊界,設定六個平面作為邊界、裁切物體。值得一提的是,以近平面裁切物體,讓我們可以瞧見物體內部(此時就不應該實施backface culling了)。我們習慣讓近平面等於圖片位置。

當然也可以設定不規則形狀的邊界。

裁切有兩種。第二種是阻止三角形伸展至焦點背後。

三角形頂點位於焦點背後,投射到圖片上就會歪斜!先前我們倒退一萬步,巧妙避開這個議題;現在我們想瞧瞧物體內部、讓圖片與焦點靠近物體、裁切物體,就必須解決這個議題。

解決方式是:運用「多邊形裁切」,以近平面裁切三角形,去除太近的部分,之後才投射、填充。裁切之後剩下的多邊形,通常會再剖分成三角形,方便套用原本的投射、填充程式碼。

第一種裁切,對象是圖片像素;第二種裁切,對象是三角形。

3D Transformation

物體平移、縮放、旋轉;相機平移、縮放、旋轉。一共六種。

物體旋轉。物體自轉,換個角度想,就是相機繞物體公轉。與其搬動大量三角形,不如只搬動一個相機。旋轉dirx、diry、dirz三個向量,重新倒退一萬步,就完成物體旋轉。

相機旋轉。相機自轉,換個角度想,就是物體繞相機公轉。其實不必想太多,直接旋轉相機就好了。

物體旋轉通常用於3D繪圖軟體,相機旋轉通常用於第一人稱射擊遊戲,焦點旋轉則不常使用。由於clipping的關係,焦點旋轉時會看不見近身景色。第一人稱射擊遊戲的角色是站在相機中心、採用相機旋轉,而不是站在焦點、採用焦點旋轉。

物體縮放。以物體中心為原點,縮放三角形頂點座標。

相機縮放。以相機焦點為原點,縮放三角形頂點投射之後的圖片座標。

物體縮放是先縮放再投影,相機縮放是先投影再縮放,兩者的視覺效果並不相同。物體縮放有鏡頭拉近拉遠的效果,相機縮放則是整張畫面等比例放大縮小。

物體平移、相機平移。懶的講了,兩者視覺效果相同。

繪製動感三角形!

Volume Rendering

Volume Rendering(Voxel Rendering)

Voxel

「像素Pixel」和「體素Voxel」兩者概念相仿,二維與三維的差別而已。

像素數值,通常代表RGB顏色;體素數值,通常代表物質密度。物質密度越高,體素數值越高。

替現實生活的物體建立體素,是一套複雜的學問。所幸網路上已經有電腦斷層掃描的資料。此處使用的CTHead是8bit TIFF圖片檔案,圖片一張張疊起來,像素成了體素。

這份資料中,皮肉密度低、體素數值低,骨骼密度高、體素數值高。我不清楚物質密度與體素數值是否恰好成正比

Normal Vector

以「梯度gradient」的單位向量,當作法向量。梯度的計算過程很簡單:右邊減左邊、遠處減近處、上面減下面,除以兩個間距,分別得到XYZ三個方向的變化程度。

Ray Marching(Ray Casting)

http://web.eecs.utk.edu/~huangj/CS594S02/raycasting.ppt

體素視作固體solid、液體liquid、氣體gas,有著不同的光線追蹤演算法。此處先介紹固體的演算法:

一、找到射線從容積的哪裡射入、哪裡射出。

二、套用鉤勒直線演算法,求得射線碰到的體素們。

三、設定臨界值,求得射線無法穿越的那個體素,即為所求。

設定不同的臨界值,就得到不同器官。皮肉密度低、骨骼密度高,因此臨界值低就得到皮肉,臨界值高就穿越皮肉、得到骨骼。

最困難的地方,就是如何讓電腦自動找到臨界值、讓電腦自動畫出最顯眼的圖片。這屬於影像辨識、人工智慧的領域,讀者可以自行尋找相關資料

一種臨界值,得到一種器官。採用半透明顏色,就可以同時畫出很多器官。

Ray Marching(Ray Casting)

此處介紹液體、氣體的演算法:

一、體素一共有256種數值(以此模型為例,其他模型不見得皆如此),替每一種數值設定顏色、暨透明程度。

二甲、由遠往近讀取體素,揉合顏色:遠方顏色與當前顏色,依照比例(當前顏色的透明程度)揉合,遞推下去。

二乙、亦得由近往遠讀取體素:透明程度增加一個次方,乘上當前顏色,累加下去。

概念等同於Mesh Rendering章節的extinction。

設定不同的顏色暨透明程度,得到不同的視覺感受。

Ray Marching: Sparse Voxel Octree

若想加速,將所有體素存入「Octree」資料結構,依照區域分類所有體素。適用於體素數量稀少、遠少於容積大小的情況。

Isosurface Rendering

Isosurface Rendering

Isosurface(Implicit Surface)

isosurface: f(x,y,z) = t , f(x,y,z) - t = 0 , g(x,y,z) = 0
g(x,y,z) > 0: point (x,y,z) is outside
g(x,y,z) = 0: point (x,y,z) is coincide
g(x,y,z) < 0: point (x,y,z) is inside

「等值表面」和「體素」概念相仿,連續與離散的差別而已。

訂立一個連續函數,讓空間中每個地點皆有數值。再訂立一個臨界值,做為表面。請參考這篇文章

臨界值移項,使右式為零。左式的正、負、零,恰好代表該地點位於表面的外部、內部、上面。

找到射線與表面的交點,有兩種方式:一、鉤勒直線演算法,一步一步走,隨時判斷內外。二、解聯立方程式,二分法求根。

另外,記得訂立場景範圍,讓射不中物體的射線停止行進。

找到表面的法向量:使用梯度當作法向量,如同體素。

Distance Field(Signed Distance Field)

distance field: f(x,y,z) = signed distance from point (x,y,z) to surface

union        of f and g: min(f, g)
intersection of f and g: max(f, g)
complement   of f      : -f
difference   of f and g: f - g

「距離場」。等值表面究極進化。函數值恰是輸入座標點到表面的最短距離!請參考這篇文章的參考文獻、這篇文章的模型範例。

當模型是距離場,多個模型的聯集、交集、差集非常好算!聯集:最小值。交集:最大值。補集:負值。差集:減法。

找到射線與表面的交點:當前位置代入函數,得到當前最短距離。走一步,步伐是當前最短距離,頂多碰到表面,而不會穿越表面。就算因為浮點數誤差穿越表面也無妨,下一步會得到負的距離,依舊持續接近表面。反覆行走,直到足夠靠近表面,或者直到超出場景範圍。

找到表面的法向量:使用梯度當作法向量,如同體素。

Ray Marching(Ray Casting)

當模型是距離場,射線與表面的交點,計算過程比較特別。

朝向表面:最短距離越來越小,迅速逼近。偏離表面:起初最短距離越來越小,掠過表面之後,最短距離越來越大,迅速遠離。

當表面平滑柔順,最短距離越來越小,逼近速度大致穩定。

當表面凹凸起伏,最短距離忽大忽小,逼近速度不穩定。

利用逼近速度,可以製做粗糙的ambient occlusion。當逼近速度不穩定,表示該處附近有物體凸出,迫近射線,遮擋交點。

沿著射線小步小步走,累計每一步當中,理想的、實際的最短距離的差值,作為陰影強度。

範例:Blobby Surface

範例:Fractal Surface