該樓層疑似違規已被系統折疊 隐藏此樓檢視此樓
Hi, I'm Carrie Anne, and welcome to Crash Course Computer Science!
嗨，我是 Carrie Anne \N 歡迎收看計算機科學速成課！
Over the past five episodes,
在過去五集
we've worked up from text-based teletype interfaces to pixelated bitmapped graphics.
我們從基于電傳打字機的指令行界面 \N 講到圖形怎麼顯示到螢幕上
Then, last episode,we covered Graphical User Interfaces and all
再到上集的 圖形使用者界面(GUI)
their "Ooey Gooey" richness.
以及圖形界面的美味
All of these examples have been 2D. But of course "we are living in a 3D world
之前的例子都是2D, 但我們生活的世界是3D的
and I'm a 3 dimensional girl!
我也是個三維 girl~
So today, we're going to talk about some fundamental methods in 3D computer graphics
是以今天，我們講3D圖形的基礎知識
and how you render them onto a 2D screen.
以及如何渲染 3D 圖形到 2D 螢幕上
As we discussed in episode 24 we can write functions that draw a line between any two points like A and B.
24集中說過 \N 可以寫一個函數，從A到B畫一條線
By manipulating the X and Y coordinates of points A and B, we can manipulate the line.
通過控制 A 和 B 的(X,Y)坐标，可以控制一條線
In 3D graphics, points have not just two coordinates, but three -- X, Y and Z.
在3D圖像中, 點的坐标不再是兩點, 而是三點, X,Y,Z
Or "zee" but I'm going to say "zed".
或讀"Zee"，但我之後會讀成"Zed"
Of course, we don't have X/Y/Z coordinates on a 2D computer screen
當然，2D的電腦螢幕上\N不可能有 XYZ 立體坐标軸
so graphics algorithms are responsible for "flattening" 3D coordinates onto a 2D plane.
是以有圖形算法 \N 負責把3D坐标"拍平"顯示到2D螢幕上
This process is known as 3D Projection.
這叫"3D投影"
Once all of the points have been converted from 3D to 2D
所有的點都從3D轉成2D後
we can use the regular 2D line drawing function to connect the dots… literally.
就可以用畫2D線段的函數 來連接配接這些點
This is called Wireframe Rendering.
這叫 "線框渲染"
Imagine building a cube out of chopsticks, and shining a flashlight on it.
想象用筷子做一個立方體，然後用手電筒照它
The shadow it casts onto your wall - its projection - is flat.
牆上的影子就是投射，是平的
If you rotate the cube around
如果旋轉立方體
you can see it's a 3D object, even though it's a flat projection.
投影看起來會像 3D 物體，盡管是投影面是平的
This transformation from 3D to 2D is exactly what your computer is doing
電腦也是這樣3D轉2D
just with a lot more math… and less chopsticks.
隻不過用大量數學，而不是筷子
There are several types of 3D Projection.
3D投影有好幾種
What you're seeing right now is an Orthographic Projection
你現在看到的，叫 正交投影
where, for example, the parallel sides in the cube appear as parallel in the projection.
立方體的各個邊，在投影中互相平行
In the real 3D world through, parallel lines converge as they get further from the viewer
在真實3D世界中,平行線段會在遠處收斂于一點
like a road going to the horizon.
就像遠處的馬路彙聚到一點
This type of 3D projection is called Perspective Projection .
這叫 透視投射
It's the same process, just with different math.
過程是類似的，隻是數學稍有不同
Sometimes you want perspective and sometimes you don't --
有時你想要透視投影，有時不想
the choice is up to the developer.
具體取決于開發人員
Simple shapes, like cubes, are easily defined by straight lines.
如果想畫立方體這種簡單圖形，直線就夠了
But for more complex shapes, triangles are better
但更複雜的圖形，三角形更好
-- what are called polygons in 3D graphics.
在3D圖形學中 \N 我們叫三角形"多邊形"(Polygons)
Look at this beautiful teapot made out of polygons.
看看這個多邊形組成的 漂亮茶壺
A collection of polygons like this is a mesh
一堆多邊形的集合叫 網格
The denser the mesh, the smoother the curves and the finer the details.
網格越密，表面越光滑，細節越多
But, that also increases the polygon count, which means more work for the computer
但意味着更多計算量
Game designers have to carefully balance model fidelity vs. polygon count,
遊戲設計者要平衡角色的真實度 \N 和多邊形數量
because if the count goes too high
如果數量太多 \N 幀率會下降到肉眼可感覺，使用者會覺得卡
the framerate of an animation drops below what users perceive as smooth.
如果數量太多 \N 幀率會下降到肉眼可感覺，使用者會覺得卡
For this reason, there are algorithms for simplifying meshes.
是以有算法用來簡化網格
The reason triangles are used,
之是以三角形更常用 \N 而不是用正方形，或其它更複雜的圖形
and not squares, or polygons, or some other more complex shape
之是以三角形更常用 \N 而不是用正方形，或其它更複雜的圖形
is simplicity:
是因為三角形的簡單性
three points in space unambiguously define a plane.
空間中 三點定義一個平面
If you give me three points in a 3D space, I can draw a plane through it
如果給3個3D點，我能畫出一個平面
there is only one.. single.. answer.
而且隻有這一個答案
This isn't guaranteed to be true for shapes with four or more points.
4個或多于4個點就不一定了
Also two points aren't enough to define a plane, only a line,
而2個點不夠定義平面，隻能定義線段
so three is the perfect and minimal number. Triangles for the win!
是以3是最完美的數字，三角形萬歲
Wireframe rendering is cool and all - sorta retro - but of course 3D graphics can also be filled.
線框渲染 雖然很酷，但3D圖像需要填充
The classic algorithm for doing this is called Scanline Rendering,
填充圖形的經典算法叫 掃描線渲染 (Scanline Rendering) \N 于1967年誕生在猶他州大學
first developed in 1967 at the University of Utah
填充圖形的經典算法叫 掃描線渲染 (Scanline Rendering) \N 于1967年誕生在猶他州大學
For a simple example, let's consider just one polygon.
為了例子簡單，我們隻看一個多邊形
Our job here is to figure out how this polygon translates to filled pixels on a computer screen
我們要思考 \N 這個多邊形如何轉成一塊填滿像素的區域
so let's first overlay a grid of pixels to fill
我們先鋪一層像素網格
The scanline algorithm starts by reading the three points that make up the polygon
掃描線算法 先讀多邊形的3個點
and finding the lowest and highest Y values. It will only consider rows between these two points.
找最大和最小的Y值，隻在這兩點間工作
Then, the algorithm works down one row at a time.
然後算法從上往下，一次處理一行
In each row, it calculates where a line running through
計算每一行和多邊形相交的2個點
the center of a row - intersects with the side of the polygon.
計算每一行和多邊形相交的2個點
Because polygons are triangles, if you intersect one line, you have to intersect with another.
因為是三角形,如果相交一條邊, 必然相交另一條
It's guaranteed!
因為是三角形,如果相交一條邊, 必然相交另一條
The job of the scanline algorithm is to fill in the pixels between the two intersections.
掃描線算法 會填滿2個相交點之間的像素
Let's see how this works.
來看個具體例子
On the first row we look at we intersect here and here.
第一行 相交于這裡和這裡
The algorithm then colors in all pixels between those two intersections.
算法把兩點間填滿顔色
And this just continues, row by row, which is why it's called Scan... Line... Rendering.
然後下一行，再下一行，是以叫 掃描..線..渲染
When we hit the bottom of the polygon, we're done.
掃到底部就完成了
The rate at which a computer fills in polygons is called the fillrate.
填充的速度叫 fillrate(填充速率)
Admittedly, this is a pretty ugly filled polygon. It has what are known as "Jaggies" rough edges.
當然 這樣的三角形比較醜，邊緣滿是鋸齒
This effect is less pronounced when using smaller pixels.
當像素較小時 就不那麼明顯
But nonetheless, you see these in games all the time, especially on lower powered platforms.
但盡管如此 \N 你肯定在遊戲裡見過這種效果，特别是低配電腦
One method to soften this effect is Antialiasing.
一種減輕鋸齒的方法叫\N 抗鋸齒(Antialiasing)
Instead of filling pixels in a polygon with the same color,
與其每個像素都塗成一樣的顔色
we can adjust the color based on how much the polygon cuts through each pixel
可以判斷多邊形切過像素的程度，來調整顔色
If a pixel is entirely inside of a polygon,it gets fully colored.
如果像素在多邊形内部，就直接塗顔色
But if the polygon only grazes a pixel, it'll get a lighter shade.
如果多邊形劃過像素，顔色就淺一些
This feathering of the edges is much more pleasant to the eyes.
這種邊緣羽化的效果 看着更舒服些
Antialiasing is used all over the place, including in 2D graphics, like fonts and icons.
抗鋸齒 被廣泛使用，比如字型和圖示
If you lean in real close to your monitor..
如果你把臉貼近螢幕
Closer, Closer.
近點..再近點
You'll see all the fonts in your browser are Antialiased. So smooth!
你能看到浏覽器裡字型是抗鋸齒的，超平滑
In a 3D scene, there are polygons that are part objects in the back, near the front,and just about everywhere.
在3D場景中，多邊形到處都是
Only some are visible,
但隻有一部分能看見
because some objects are hidden behind other objects in the scene
因為其它的被擋住了
-- what's called occlusion .
這叫 遮擋
The most straightforward way to handle this is to use a sort algorithm,
最直接的處理辦法是用排序算法
and arrange all the polygons in the scene from farthest to nearest, then render them in that order.
從遠到近排列，然後從遠到近渲染
This is called the Painter's Algorithm , because painters also have to start with the background
這叫 畫家算法 因為畫家也是先畫背景
and then increasingly work up to foreground elements.
然後再畫更近的東西
Consider this example scene with three overlapping polygons.
看這個例子，有3個重疊的多邊形
To make things easier to follow, we're going to color the polygons differently.
為了簡單，我們畫成不同顔色
Also for simplicity, we'll assume these polygons are all parallel to the screen
同時，假設3個多邊形都和螢幕平行
but in a real program, like a game,
但在實際應用中, 比如遊戲裡\N多邊形可能是傾斜的
the polygons can be tilted in 3D space.
但在實際應用中, 比如遊戲裡\N多邊形可能是傾斜的
Our three polygons, A B and C… are at distance 20, 12 and 14.
3個多邊形A,B,C，距離20,12,14
The first thing the Painter's Algorithm does is sort all the polygons, from farthest to nearest.
畫家算法的第一件事，是從遠到近排序
Now that they're in order, we can use scanline rendering to fill each polygon, one at a time.
現在有序了，我們可以用 掃描線算法 填充多邊形，一次填一個
We start with Polygon A, the farthest one away.
我們從最遠的A開始
Then we repeat the process for the next farthest polygon, in this case, C.
然後重複這個過程，填充第二遠的C
And then we repeat this again, for Polygon B.
然後是 B
Now we're all done, and you can see the ordering is correct. The polygons that are closer, are in front!
現在完成了，可以看到順序是對的，近的多邊形在前面！
An alternative method for handling occlusion is called Z-Buffering .
還有一種方法叫 深度緩沖
It achieves the same output as before, but with a different algorithm.
它和之前的算法做的事情一樣，但方法不同
Let's go back to our previous example, before it was sorted.
我們回到之前的例子，回到排序前的狀态
That's because this algorithm doesn't need to sort any polygons, which makes it faster.
因為這個算法不用排序，是以速度更快
In short, Z-buffering keeps track of the closest distance
簡而言之，Z-buffering 算法會記錄
to a polygon for every pixel in the scene.
場景中每個像素和錄影機的距離
It does this by maintaining a Z-Buffer, which is just a matrix of values that sits in memory.
在記憶體裡存一個數字矩陣
At first, every pixel is initialized to infinity.
首先，每個像素的距離被初始化為"無限大"
Then Z-buffering starts with the first polygon in its list. In this case, that's A.
然後 Z-buffering 從清單裡第一個多邊形開始處理，也就是A
It follows the same logic as the scanline algorithm, but instead of coloring in pixels,
它和掃描線算法邏輯相同，但不是給像素填充顔色
it checks the distance of the polygon versus what's recorded in its Z-Buffer.
而是把多邊形的距離\N和 Z-Buffer 裡的距離進行對比
It records the lower of the two values.
它總是記錄更低的值
For our Polygon A, with a distance of 20, it wins against infinity every time.
A距離20，20小于"無限大"，是以緩沖區記錄20
When it's done with Polygon A, it moves on to the next polygon in its list, and the same thing happens.
算完A之後算下一個，以此類推
Now, because we didn't sort the polygons,
因為沒對多邊形排序
it's not always the case that later polygons overwrite high values.
是以後處理的多邊形并不總會覆寫前面的
In the case of Polygon C,
對于多邊形C
only some of the values in the Z-buffer get new minimum distances.
緩沖區裡隻有一部分值會被多邊形C的距離值覆寫
This completed Z-buffer is used in conjunction with a fancier version of scanline rendering
Z緩沖區完成後，會和"掃描線"算法的改進進階版配合使用
that not only tests for line intersection,
不僅可以勘測到線的交叉點
but also does a look up to see if that pixel will even be visible in the final scene.
還可以知道某像素是否在最終場景中可見
If it's not, the algorithm skips it and moves on.
如果不可見，掃描線算法會跳過那個部分
An interesting problem arises when two polygons have the same distance,
當兩個多邊形距離相同時 \N 會出現一個有趣問題
like if Polygon A and B are both at a distance of 20. Which one do you draw on top?
比如多邊形 A 和 B 距離都是 20, 哪個畫上面?
Polygons are constantly being shuffled around in memory and changing their access order.
多邊形會在記憶體中移來移去，通路順序會不斷變化
Plus, rounding errors are inherent in floating point computations.
另外,計算浮點數有舍入誤差
So, which one gets drawn on top is often unpredictable.
是以哪一個畫在上面, 往往是不可預測的
The result is a flickering effect called Z-Fighting, which if you've played 3D games no doubt encountered.
導緻出現 Z-fighting 效果 \N 如果你玩過3D遊戲，肯定見過
Speaking of glitches, another common optimization in 3D graphics is called Back-Face Culling.
說起 故障，3D遊戲中有個優化叫 背面剔除
If you think about it, a triangle has two sides, a front and a back.
你想想,三角形有兩面,正面和背面
With something like the head of an avatar, or the ground in a game,
遊戲角色的頭部或地面，隻能看到朝外的一面
you should only ever see one side -- the side facing outwards.
遊戲角色的頭部或地面，隻能看到朝外的一面
So to save processing time, the back-side of polygons are often ignored in the rendering pipeline
是以為了節省處理時間，會忽略多邊形背面
which cuts the number of polygon faces to consider in half.
減了一半多邊形面數
This is great, except when there's a bug that lets you get inside of those objects,and look outwards.
這很好,但有個bug是 如果進入模型内部往外看
Then the avatar head or ground becomes invisible.
頭部和地面會消失
Moving on. We need to talk about lighting -- also known as shading
繼續，我們講燈光，也叫 明暗處理
because if it's a 3D scene, the lighting should vary over the surface of objects.
因為3D場景中, 物體表面應該有明暗變化
Let's go back to our teapot mesh.
我們回到之前的茶壺網格
With scanline rendering coloring in all the polygons, our teapot looks like this.
用"掃描線"算法渲染所有多邊形後，茶壺看起來像這樣
Not very 3D.
沒什麼 3D 感
So, let's add some lighting to enhance the realism!
我們來加點燈光，提高真實感
As an example, we'll pick 3 polygons from different parts of our teapot.
為了舉例，我們從茶壺上挑3個不同位置的多邊形
Unlike our previous examples, we're now going to consider how these polygons are oriented in 3D space
和之前的例子不同，這次要考慮這些多邊形面對的方向
they're no longer parallel to the screen, but rather tilted in different 3D directions.
它們不平行于螢幕，而是面對不同方向
The direction they face is called the Surface Normal ,
他們面對的方向叫 " 表面法線 "
and we can visualize that direction with a little 3D arrow that's perpendicular to the polygon's surface.
我們可以用一個垂直于表面的小箭頭\N來顯示這個方向
Now let's add a light source.
現在加個光源
Each polygon is going to be illuminated a different amount. Some will appear brighter
每個多邊形被照亮的程度不同 有的更亮
because their angle causes more light to be reflected towards the viewer.
因為面對的角度\N導緻更多光線反射到觀察者
For example, the bottom-most polygon is tilted downwards,
舉個例子，底部的多邊形向下傾斜
away from the light source, which means it's going to be dark.
遠離光源，是以更暗一些
In a similar way, the rightmost polygon is slightly facing away from the light,
類似的，最右的多邊形更背對光源
so it will be partially illuminated.
是以隻有部分照亮
And finally, there's the upper-left polygon.
最後是左上角的多邊形
Its angle means that it will reflect light from the light source towards our view.
因為它面對的角度 意味着會把光線反射到我們這裡
So, it'll appear bright.
是以會顯得更亮
If we do this for every polygon, our teapot looks like this which is much more realistic!
如果對每個多邊形執行同樣的步驟，看上去會更真實!
This approach is called Flat Shading, and it's the most basic lighting algorithm.
這叫 平面着色，是最基本的照明算法
Unfortunately, it also makes all those polygon boundaries really noticeable
不幸的是，這使多邊形的邊界非常明顯，看起來不光滑
and the mesh doesn't look smooth.
不幸的是，這使多邊形的邊界非常明顯，看起來不光滑
For this reason, more advanced lighting algorithms were developed,
是以開發了更多算法
such as Gouraud Shading and Phong Shading .
比如 高洛德着色 和 馮氏着色
Instead of coloring in polygons using just one colour,
不隻用一種顔色給整個多邊形上色
they vary the colour across the surface in clever ways,
而是以巧妙的方式改變顔色
which results in much nicer output.
得到更好的效果
We also need to talk about textures ,
我們還要說下" 紋理 "
which in graphics refers to the look of a surface,rather than its feel.
紋理在圖形學中指外觀，而不是手感
Like with lighting, there are many algorithms with all sorts of fancy effects.
就像照明算法一樣，\N 紋理也有多種算法，來做各種花哨效果
The simplest is texture mapping .
最簡單的是 紋理映射
To visualize this process,let's go back to our single polygon.
為了了解紋理映射，回到單個多邊形
When we're filling this in, using scanline rendering,
用"掃描線算法"填充時
we can look up what color to use at every pixel according to a texture image saved in memory.
可以看看記憶體内的紋理圖像 決定像素用什麼顔色
To do this, we need a mapping between the polygon's coordinates and the texture's coordinates.
為了做到這點，\N 需要把多邊形坐标和紋理坐标對應起來
Let's jump to the first pixel that scanline rendering needs to fill in.
我們來看看"掃描線算法"要填充的第一個像素
The texturing algorithm will consult the texture in memory,
紋理算法會查詢紋理
take the average color from the corresponding region, and fill the polygon accordingly.
從相應區域取平均顔色，并填充多邊形
This process repeats for all pixels in the polygon, and that's how we get textures.
重複這個過程，就可以獲得紋理
If you combine all the techniques we've talked about this episode, you get a wonderfully funky little teapot.
如果結合這集提到的所有技巧 \N 會得到一個精美的小茶壺
And this teapot can sit in an even bigger scene, comprised of millions of polygons.
這個茶壺可以放進更大的場景裡 \N 場景由上百萬個多邊形組成
Rendering a scene like this takes a fair amount of computation.
渲染這樣的場景需要大量計算
But importantly, it's the same type of calculations being performed
但重要的是，再大的場景，過程都是一樣的 \N 一遍又一遍，處理所有多邊形
over and over and over again for many millions of polygons –
但重要的是，再大的場景，過程都是一樣的 \N 一遍又一遍，處理所有多邊形
scanline filling, antialiasing, lighting, and texturing.
掃描線填充, 抗鋸齒, 光照, 紋理化
However there are a couple of ways to make this much faster!
然而，有幾種方法可以加速渲染
First off, we can speed things up by having special hardware
首先，我們可以為這種特定運算 \N 做專門的硬體來加快速度，讓運算快如閃電
with extra bells and whistles just for these specific types of computations, making them lightning fast.
首先，我們可以為這種特定運算 \N 做專門的硬體來加快速度，讓運算快如閃電
And secondly,we can divide up a 3D scene into many smaller parts,
其次，我們可以把3D場景分解成多個小部分
and then render all the pieces in parallel,rather than sequentially.
然後并行渲染，而不是按順序渲染
CPU's aren't designed for this, so they aren't particularly fast.
CPU不是為此設計的，是以圖形運算不快
So, computer engineers created special processors just for graphics
是以，計算機工程師為圖形做了專門的處理器
– a GPU, or Graphics Processing Unit.
叫 GPU "圖形處理單元"
These can be found on graphics cards inside of your computer, along with RAM reserved for graphics.
GPU 在顯示卡上，周圍有專用的 RAM
This is where all the meshes and textures live,
所有網格和紋理都在裡面
allowing them to be accessed super fast by many different cores of the GPU all at once.
讓 GPU 的多個核心可以高速通路
A modern graphics card, like a GeForce GTX 1080 TI,
現代顯示卡，如 GeForce GTX 1080 TI
contains 3584 processing cores, offering massive parallelization.
有3584個處理核心，提供大規模并行處理
It can process hundreds of millions of polygons every second!
每秒處理上億個多邊形！
Ok, that concludes our whistle stop tour of 3D graphics.
好了，本集對3D圖形的介紹到此結束
Next week, we switch topics entirely.
下周我們聊全新的主題
I'll ping you then.
我到時會 ping 你~