256位元組3D程序是如何實現3D引擎的呢？

01-04

你們有沒有看過256位元組的3D程序？
比如下面的《TUBE》程序，256位元組
還有下面的《PULS》程序，256位元組
還有下面的《WOLF》程序，128位元組
真的是《麻雀雖小，五臟俱全》。

我第一次看到的時候驚呆了。
256位元組是如何實現3D引擎的呢？

1. 全都不是基於正統3D引擎的多邊形繪製，而是基於少數特定情況的簡化版光線跟蹤演算法

2. 只能渲染特定幾種物體，並不能渲染通用物體。

3. 無資源或者少資源（基本靠生成），重複

4. 16位代碼，COM格式的可執行（沒有PE頭，代碼數據和棧都在一個段內，指針只有兩位元組）

5. 儘可能用彙編來寫

你自己花點時間也能做出來，

具體解釋一下：

簡化版的 raycasting，實現起來的代碼量比通用的多邊形繪製方法至少 N個量級。

基本的光線跟蹤，在 320x200 的解析度下，從攝像機中心射出 320x200條光線，屏幕上每個點對應一條光線，首先碰撞到的物體的位置顏色，就是屏幕上這個點的顏色：

可以描述為下面這段代碼：

for (int y = 0; y &< 200; y++) { for (int x = 0; x &< 320; x++) { DWORD color = RayCasting(x, y); DrawPixel(x, y, color); } }

其中函數 RayCasting(x, y) 就是計算從視點開始穿過屏幕上（x, y）這個點的射線。

所謂簡化版的光線跟蹤，是只需要實現特定物體，以及針對特定條件，比如早年遊戲裡面用的最多的實時光線跟蹤繪製地形高度圖的（比如三角洲特種部隊，xxx直升飛機）：

比如雲風 2002年寫過的文章：3D地表生成及渲染 (VOXEL)

實現上述效果的地形渲染，只需要 200多行 C 代碼

使用標準三角形渲染這樣的地形（軟體渲染），代碼少說也上千行了，使用標準的光線跟蹤少說也要 500行左右。

但是，我們情況比較特殊：

1. 只渲染地形（高度圖）

2. 視角採用水平視角（可以象 doom一樣左右轉動，前後移動，但是不能偏頭）

光線跟蹤的流程可以針對這種情況大大簡化：

（高度圖，白色表示高的地方，黑色表示矮的地方）

由於高度圖的特殊性以及彩用水平視角，屏幕上同一列光線可以只算一條：

沒錯，從屏幕最左邊一列列的向右邊繪製，每一列只需要先從最下方的光線尋找碰撞，找到碰撞以後，就逐步沿山體爬坡，計算出同一列其他光線的交點，這樣的光線跟蹤雖然效果看起來還行，最終代碼寫起來也就200行（C代碼），用16位彙編緊湊點來寫，256個位元組未嘗不可。

嗯，好吧，其實雲風是參考 flipcode 上的這篇文章：

flipcode - Realtime Voxel Landscape Engines

有人用flash實現了一遍，直接可以在瀏覽器上看效果：

http://www.unitzeroone.com/flex_2/voxel_landscape/ （需翻牆）

另一個著名的例子就是類《重返德軍總部》，《DOOM》裡面用到的光線追蹤：

這是 Javascript 實現的類 DOOM 引擎，只有 265行 js代碼：

A first-person engine in 265 lines （文章）

這種地牢渲染情況也比較特殊：

1. 只渲染三種物體：牆壁，地面，天花板，

2. 同樣採用水平視角

先畫地面和天花板：

也是從屏幕最下面投射一次性投射出一排光線出去，相交到地面（或天花板）上的某一行，

從屏幕最下面那一行像素開始，計算那一排光線投射後相交於地面上的線段（x1,y1）-（x2,y2），代表代表地面上相交線段左右兩邊的端點，然後根據屏幕寬度縮放著繪製過去。

接著繪製牆壁，從坐到有右判斷交點就是了，一豎條一豎條的繪製：

注意處理遠小近大（除以z 來決定這一豎條牆壁的縮放比例）

早年不少地牢類 FPS遊戲使用這個方法，實現起來也十分精簡（javascript 才 265行）

上面的幾個例子，都是使用簡化過的 raycasting 進行渲染：

1. 針對特定物體：地形，牆，地板等

2. 採用水平視角（不能歪頭）

通過這種簡化，光線路徑計算十分的簡單，不管是 C實現或者 javascript/ flash 實現，代碼基本可以控制在 200行內。

來看第一個例子：

明顯的光線跟蹤，只需要實現對一種特定的數學曲線/面的碰撞檢測即可，顏色使用黃色，用交點的法向確定下明暗即可，效果十分平滑。

然而，代碼尺寸限制，它只能繪製這種數學曲線/面，並不能繪製其他形狀的東西，所以並不能稱為引擎。

來看另一個例子：

這個牆面只有兩種類型（橫的或者豎的），由於性能可以不用考慮太多，

可以比 doom的例子更簡化一點，只對三種平面求焦點：

1. 地面或者天花板（z=-1，z=1）

2. 橫牆：x坐標不變

3. 豎牆：y坐標不變

算起來應該也很快，C實現的代碼量有可能控制在150行左右。

接下來是代碼壓縮了，選擇 .COM的可執行格式，它沒有 PE頭，純代碼+數據，同時SP, ES, DS, CS 等四個段寄存器都是指向同一個數據段，所有數據都用 16位 near 指針訪問（2位元組）。

最後手工重構成彙編版本（C編譯器產生的代碼實在太龐大了），如果有資源，用256色（8位）或者16色（4位），並且使用 RLE壓縮（解壓代碼很短），或者代碼動態生成資源。

我以前也用純彙編實現過一個 1KB 左右的完整空戰遊戲，16位的手寫彙編，100位元組就能做好多事情了，按照上面的簡化版 raycasting ，邏輯比空戰遊戲簡單不少。

通過不斷的簡化繪製模型，增加限制，以及不斷的代碼優化，

256個位元組內實現題主圖中的幾個 demo應該是可以的。

相關閱讀：

計算機底層是如何訪問顯卡的？ - 韋易笑的回答

想用C++實現一個軟體渲染器，類似DX和OpenGL，除了《3D遊戲編程大師技巧》，或者什麼網站推薦？ - 韋易笑的回答

樓上有說ray-tracing，也有說ray-marching，其實我覺得說的都對，概念名詞不用特意去摳字眼，意思是那個意思就行。

各位對這一技術都有剖析，@韋易笑前輩還列了蠻多的圖片，但是我覺得他沒有完全說出這類代碼思想的核心：過程生成式建模（Procedural Modeling），與之對應的概念還有過程生成式紋理（Procedural Texture）等，旨在通過程序自動生成一系列複雜的形體或紋理圖案。

關於這一主題，曾就職於Pixar的ShaderToy創始人iq大神在NV Scene 2008上有一篇非常棒的presentation：Rendering Worlds with Two Triangles with raytracing on the GPU in 4096 bytes，看名字就知道和這個主題的相關度有多高，好奇居然沒有任何一個人提到這篇。這裡藉助這篇presentation簡單解釋下這類程序的思想，圖片均來自於這個presentation的slides和iq的個人網站。

首先，基於GPU進行渲染的時候，我們都知道可編程的管線被分成了若干個部分，每個部分負責處理光柵化渲染的不同階段，最常用的shader有兩類，即頂點著色器（Vertex Shader）和片段著色器（Fragment Shader），對於傳統的3D引擎來說，頂點著色器是幾何造型的關鍵，而片段著色器則處理了光影顏色方面的邏輯；而對於過程生成式的GPU程序來說，幾乎所有的渲染流程（幾何造型和著色）都發生在片段著色器，頂點著色器只負責輸出一個用於渲染的畫布四邊形，有時候這也叫作Screen Quad。

相較於傳統3D引擎是逐模型處理渲染，這類僅由FS決定的渲染程序必須把場景作為整體來呈現，這不符合光柵化渲染的思路，但是正是光線追蹤的思路：已知整個場景的信息，從攝像機出發向渲染畫布發射無數條射線，每條射線單獨和整個場景進行求交，並在交點處計算光照等信息。光柵化渲染的優勢在於速度快，不需要已知整個場景的信息，並行化程度較高；光線追蹤需要已知整個場景的所有信息，並行化程度不及光柵化渲染，計算量大，速度慢，但由於它先天知道整個場景的所有信息，因此能夠比較容易地處理次級光線，全局照明等問題。

有了基本的光線追蹤的概念，緊接著的一個概念是Ray-marching，Ray-marching在最近幾年實時圖形領域多用於體渲染（Volume Rendering），近年來幾乎所有的體積光效果都是基於Ray-marching的，另外，體渲染也開始逐漸應用於實時大氣和雲彩等介質渲染，關於這方面paper有非常多，我在另一個回答里有提到幾篇：寫基於圖形API（如WebGL）的引擎主要考慮的設計因素有哪些？ - 洛城的回答

ray-marching的基本概念就是把一條光線的投射變成光線從一個點出發按一定的步長前進，每前進一步就看看是不是和場景相交了，沒有就繼續前進，有就停下來求交點，算著色，它和傳統光線追蹤最大的區別就是它沒法一步就和場景求出相交點的解析解，它是一個迭代求交的漸進式方法。

有了基本的渲染框架，下一步是如何確定步長，一個比較慢的做法就是固定步長，一步步走，但是如果我們知道場景的一些額外信息，能否加速這個步驟呢？答案是肯定的。這裡就需要引出另外一個概念：signed distance field，有向距離場，這個技術也不新鮮，比較早期的應用是V社一篇關於如何渲染放大不失真字體，這裡有描述：如何利用shader在文字上添加漸變陰影的效果？ - 洛城的回答

後來Epic在它的風箏的超大場景DEMO裡面，運用了這一技術去加速計算動態的遮蔽和軟陰影：Dynamic Occlusion With Signed Distance Fields。它的核心思想是，算出每個空間點與它在場景中的最近點之間的距離，這個距離用來幹嘛呢？確定ray-marching的步長，具體看這個組圖就明白了：

每次Ray-marching的前進步長就用這個距離，這樣保證每前進一步，都不可能錯過交點，同時也比固定步長求交需要的迭代次數少很多。

以上是基本的渲染框架。

寫過著色器程序的人都知道，通過外部向著色器能夠傳遞的數據量非常有限，因此要在Fragment Shader裡面已知整個場景的信息，就不可能從外部導入龐大的模型數據，因此才引出了過程生成式建模的概念，也就是在FS的程序里去生成一些幾何體。結合我們上面描述的渲染框架可知，我們過程生成的其實不是幾何體的一個個頂點數據，而是幾何體的距離場，即空間任意一點距離這個幾何體的距離的函數。iq大神的blog裡面列舉了一些常用的幾何體（box,sphere,cone,cylinder,triangle）的距離場函數：Inigo Quilez :: fractals, computer graphics, mathematics, demoscene and more

有了基本的幾何體，緊接著需要的就是把它組合起來玩兒出花來~

組合方法也很多，包括交，並，補，重複，以及平移，縮放和旋轉，在iq的blog裡面也都有詳細的代碼說明。

除此之外還有一些複雜的變化，譬如扭曲，置換偏移，融合等：

這些操作基本上可以完成整體的幾何造型，但是光影的計算還需要更多的幾何細節，譬如法線，AO等信息，沒關係，這些也都能做：

法線：

一些distortion+normal：

AO：

軟陰影：

GI：

怎麼樣，夠你玩一陣子了吧。

詳細了解這些技術，你就會發現，光柵化渲染處理幾何造型比較容易，但處理複雜光照比較難，而基於ray-marching的SDF的方法則正好相反。至於過程生成式紋理，那就是另外一個較大的話題了，這裡就不提了。

所以說，多讀Paper多看書才是正道啊。

稍微補充下。

這類效果和體積的Demo一般只會用到 raycasting, raymarching. 但不會用到光線追蹤(raytracing). 概念上區別挺大。

這篇文章[1] 以「圈內人士」的身份很好地闡述了這三者的區別。

順便題主要是真的好奇這類1k以下程序用到的技術點不妨以它文章下面的引用為起點。

至於這3個程序:

第三個程序WOLF的實現相對其他兩個最簡單, 可以直接看這篇分析[2]。

第一第二個程序的圖形變換更為豐富，而體積只增加了一倍，少不了一些奇技淫巧，很顯然難度更大。Puls的作者說自己只花了一周的時間把C程序移植到了asm。但花了整整120個小時來優化到256位元組[2]。

[1] http://www.hugi.scene.org/online/hugi37/hugi%2037%20-%20coding%20adok%20on%20ray%20casting,%20ray%20tracing,%20ray%20marching%20and%20the%20like.htm

[2] https://finalpatch.blogspot.com/2014/06/dissecting-128-byte-raycaster.html

[3] Puls by ?r?ola :: pou?t.net

這樣的程序並不是3d引擎，叫做一個shader更合適，一般只需要實現一個核心函數：

color fragShader(vec2 coord);

就是一個根據屏幕坐標到輸出像素顏色的映射函數，剩下就是寫shader代碼，既可以完成題主的要求。

稍微有窗口編程經驗的實現上述函數毫無難度，有難度的是shader代碼如何寫？一般這樣的shader是一個raycast演算法，演算法核心就是模擬從相機發射ray到每個坐標判斷是否有碰撞，如果有就輸出什麼顏色。

一個簡單入門參考，f_castel

複雜的demo參考Shadertoy BETA，上面很多demo都比題主的demo複雜。

我不知道樓主是否聽說過64K編程比賽，這與之都是類似的原理，在我08年大一的時候，我當時看到老師展示的時候，我也是如樓主一樣，一副沒有見過世面的樣子，眼睛直盯盯的盯著屏幕，感覺那麼的不可思議。當時老師也沒有講原理。後來我懂得多了，知道了這就是用CPU去動態生成的，很多東西也是極限壓縮，如果你打開這樣的程序，你會發現CPU佔用率會瞬間爆炸。這無疑有點類似演算法的空間換時間，時間換空間那樣的感覺。

這種一般都是採用ray-marching做的。有個網站叫做shadertoy，專門用來炫ray-marching技巧的。

我在網上搜了一下，似乎是com文件。

既然是dos下的而非pe，那就不用導入各種函數了，關鍵在於怎麼設計顯示的形式了吧

首先這是我剛寫的小程序的截圖

不知道這算不算答主眼中的3d程序，反正我看著像是兩個立方體啊，但是我保證源代碼裡面沒有一絲3d相關的內容：

#include "stdio.h" int main () { printf (" +----+ +----+ "); printf (" / /| |\ \ "); printf ("+----+ | | +----+ "); printf ("| | + + | | "); printf ("| |/ \| | "); printf ("+----+ +----+ "); return 0; }

同理，題主提到的這類3d程序裡面一般沒有3d引擎，只不過最終展示的畫面有3d的視覺效果罷了。

題主第一張圖那種非互動式展示有明顯重複pattern的畫面，直接通過多層循環生成最終結果是最經濟的做法。一切3d轉換隻存在於作者的腦海里。

想起一句話：計算機圖形就是視覺欺騙的藝術。

這在計算機界是我最感興趣的話題了，demoscene或說crack intros可是計算機界的藝術品，看到的最有名德國的farbrausch有一系列的獲獎作品，搜這些關鍵字就能搜到一大堆不僅64k大賽作品的分享網站，有32b-256k的分類，也有幾十M幾百M未壓縮的作品。都以win平台居多也有amiga，linux，mac等各種計算機平台的。nvidia官方等或其他測試機構出的顯卡的測試程序也屬於這類。國內上一代老程序員也有搞這個的只記的一個團隊名sYcini，很早了。不過大概早解散了，我搜到的時候作品鏈接都失效了，只有幾張圖片。這種團隊一般至少三個人，寫代碼的，搞音樂的，和建模的，三個人基本都是所在領域的大牛，這個搞電子音樂的恐怕在國內能達到製作要求的就很難找（也就上古時代會給FC紅白機寫音樂的人會搞吧），現在的程序員只會套庫，光鏈接調用庫，程序尺寸就撐大了。你要知道流星蝴蝶劍遊戲的程序只有不到2M，剩下的都是數據，如果加殼壓縮一下應該更小。

星際爭霸1，保留了動畫與音樂，被壓縮到20M內，放入遊戲主機，用手柄玩。

雖然20M比64k大得多，但星際爭霸1這種遊戲都能被暴雪壓縮到20M以內，其他的也就不奇怪了。

3D程序的本質就是矩陣變換，說白了就是一些乘法和加法運算，無他。

所以你只要找到一個循環或者迭代正好對應了一段動畫，你就能寫出一個3D程序，多小都有可能。

說到64k（程序大小不超過64k）比賽，我還有一年獲獎的大部分作品。當年大一傻傻的我驚呆了。

隨手找了幾個截圖，可以感受一下，不僅畫面精緻，還有音樂。有需要看看的可以跟我要鏈接。

幽靈古堡

第七天堂

有個開源的96k引擎實現，github上有見過。