VoxelSpace: 20行未満のコードで実装された地形レンダリングアルゴリズム（2020）
(github.com/s-macke)- Voxel Spaceは、1992年のNovaLogicのComancheで使われた2.5D地形レンダリング手法で、GPUアクセラレーションが存在しないか高価だった時代に、CPUだけで質感のある山や谷を表現した
- 地形はハイトマップとカラーマップで表現され、Comancheでは1024×1024の1バイトハイトマップと1024×1024の1バイトカラーマップを使用した
- カラーマップにはすでに陰影と影が含まれているため、レンダリング中にライティング計算は不要だが、マップ上の各位置は1つの高さしか持てないため、建物や木のような複雑なジオメトリ構造は表現しにくい
- 基本レンダリングは、奥から手前へマップの線分をラスタライズし、各画面列ごとに高さと色を読み取って垂直線を描く方式で、視野角90°と透視投影を数行のコードで実装している
- 性能改善は、手前から奥へ描画しながら列ごとのy-bufferで隠れた部分をスキップし、遠距離では詳細度を下げる方式で可能になる
Voxel Spaceが登場した背景
- 1992年当時のCPUは現在より1000倍遅く、GPUアクセラレーションは知られていないか導入が難しかった
- 3DゲームはCPUだけで計算され、レンダリングエンジンは単色で塗りつぶしたポリゴンを描く方式が一般的だった
- NovaLogicは1992年にComancheを発売し、山や谷のテクスチャ、陰影、影の表現は当時のゲームグラフィックの中で際立っていた
- READMEではWeb Demo of the Voxel Space Engineを提供している
地形表現: ハイトマップとカラーマップ
- Voxel Spaceで地形を表現する最も簡単な方法は、height mapとcolor mapを使うことだ
- Comancheは次の2つのマップを使っている
- 1024×1024の1バイトハイトマップ
- 1024×1024の1バイトカラーマップ
- これらのマップは周期的に繰り返される形になっている
- 各マップ位置は1つの高さしか持てない
- 建物や木のような複雑なジオメトリ構造は表現できない
- その代わり、カラーマップにすでに陰影と影が含まれているため、レンダリング過程でライティングを計算しなくてよい
基本レンダリングアルゴリズム
- Voxel Spaceエンジンは、ハイトマップとカラーマップをラスタライズし、画面に垂直線を描く方式で地形をレンダリングする
- 基本手順は次の通り
- 画面をクリアする
- オクルージョン処理を保証するために奥から手前へ描く
- 観測者から同じ光学的距離にあるマップ上の線を見つける
- 視野角と透視投影を考慮する
- その線を画面列数に合わせて分割する
- 各線分位置で高さと色を2Dマップから読み取る
- 高さ座標に透視投影を適用する
- 投影された高さとカラーマップの色で垂直線を描く
- 最も単純なPython形式のコアループは、
zを遠距離から近距離へ減らしながら、画面列ごとにDrawVerticalLineを呼び出す - 呼び出し例では、位置、カメラ高さ、水平線位置、高さスケール、最大距離、画面の幅と高さを渡す
回転の追加
- 基本アルゴリズムでは北方向しか見られない
- 別の方向を見るには、座標を回転するためのコードを追加する
- 回転版では
phiを視野角として受け取り、sin(phi)とcos(phi)を事前計算する - 左右の視界境界点の計算に回転後の座標を適用し、各画面列に沿って
xとyを一緒に増加させる - レンダリングの中核構造は同じまま維持される
- 距離ごとの線分計算
- 画面列に合わせたラスタライズ
- ハイトマップとカラーマップの参照
- 透視投影後に垂直線を描画
性能改善の方法
- 奥から手前へ描く代わりに手前から奥へ描けば、隠れる領域を減らせる
- この方式では、各画面列ごとに最も高いy位置を保存するy-bufferが必要になる
- 初期y-buffer値は画面の高さに設定する
- 新たに計算した
height_on_screenが既存のy-bufferより上にあるときだけ、見える部分を描く - 描画後、y-bufferをより高い位置に更新する
- 距離
zは近い場所から遠い場所へ増加する dzを徐々に大きくすると、遠距離ではより大きな間隔でサンプリングでき、Level of Detail効果が得られる- 近距離はより詳細に、遠距離はより粗くレンダリングする方式だ
提供資料とライセンス
- リポジトリには複数のカラーマップとハイトマップの組が含まれている
- ソフトウェア部分はMITライセンス
- Voxel Space技術は、一部の国ではまだ特許が残っている可能性がある
- カラーマップとハイトマップはComancheゲームからリバースエンジニアリングされた資料のため、ライセンス対象外となっている
- 関連資料として、Voxel terrain engine - an introductionへのリンクが提供されている
1件のコメント
Hacker Newsの意見
すごく素晴らしい。こういう新しくてエレガントなアルゴリズムが魔法のような体験を生み出してくれた時代が懐かしい
年を取ったからそう感じるのかもしれないけれど、ハードウェア資源が限られていた時代のゲームには、今よりも大きな魔法があった気がする。80年代、90年代、2000年代初頭には、ほぼ毎年、少なくとも世代ごとにゲームがメディアそのものを前へ押し進め、開発者たちは新しい手法と純粋に魔法のような最適化でハードウェア性能を限界まで絞り出していた
最近はAAAスタジオの反復的な新作よりも、PICO-8のようなファンタジーコンソールのほうがずっと面白いし、実質的にアセットを差し替えただけのゲームが毎年あれほど成功する理由がよく分からない
ただ、今ははるかに複雑で、目立ちにくいだけ。昔は賢い数学トリックによって、平たい三角形からテクスチャへと進化する様子が見えたとすれば、今は部屋の隅の陰影をより良くするような進歩になっている。テクスチャの改善は誰でもすぐ気づくが、隅の影は業界の人でなければ明確には指摘しにくい。それでもこうした要素が積み重なって全体のグラフィックを良くしているものの、昔ほど印象的ではない
AAAゲーム業界は大きなビジネスで、ゲーム制作費は莫大であり、投資家は利益を求める。そのため通常は市場を調査し、売れているものを見て、それに近い方向で作る。独創性は下がってもリスクは低くなる
逆にインディーゲーム業界には何千ものスタジオがあり、コンテンツ量や完成度でAAAに勝てないので、群れから抜け出すために独創的なアイデアのような別の武器が必要になる。ただし今では、技術的制約を克服することが主な原動力ではない場合が多い。制約が昔ほど多くないからだ。むしろコスト的に手が届かないため、AAA作品ほど技術的に攻めないことがよくある
PICO-8のシーンはよく知らないが、そのうちどれほどが人工的な技術制約を克服することにあり、どれほどがプラットフォームを意図された形で使い、ゲームプレイに集中することにあるのかは気になる
昔にも本当に、本当に、本当にひどいゲームがたくさんあったことも覚えている
プロトタイプの一つはこれ: https://youtu.be/9Z8Bm8ZmWKI
プロトタイプの一つはこれ: https://media.discordapp.net/attachments/953383695908216843/...
Tiny Gladeの最近の技術発表には魔法のような内容が詰まっている: https://youtu.be/jusWW2pPnA0?si=IE-6W0Z1VCBld0AT
より基礎的なレベルのエンジンやフレームワークでも素晴らしい技術が出てきている。たとえばUE5のNanite/Lumen/MegaLightsがある
関連リンク。ほかにもあるだろうか？
VoxelSpace – Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=38051859 - 2023年10月、コメント2件
Voxel Space: Comanche's terrain rendering in less than 20 lines of code (2020) - https://news.ycombinator.com/item?id=26631995 - 2021年3月、コメント71件
Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=21944573 - 2020年1月、コメント116件
Terrain rendering in fewer than 20 lines of code - https://news.ycombinator.com/item?id=15772065 - 2017年11月、コメント93件
Show HN: Voxel Space – terrain rendering in less than 20 lines of code - https://news.ycombinator.com/item?id=15339016 - 2017年9月、コメント2件
mars.comをすぐに思い出した。ドメインではなくプログラムのほう。動画: https://www.youtube.com/watch?v=_zSjpIyMt0k
追記: Pouetにもある: https://www.pouet.net/prod.php?which=4662
当時はかっこいいと思ったけれど、デモシーンやプログラミングをまったく知らない子どもだったので、完全なゲームではないことにがっかりした。振り返ると、メールで出回っていたしょぼいDirectXデモくらいにしか思っていなかったが、実在していたものだとは知らなかった
レンダリング方式はきれいだが、これをボクセルと呼べるのかは分からない。任意の体積をレンダリングできないし、データの保存方式も、与えられたx,yに対して位置を1つしか持てない
単にハイトマップレンダラの見事な実装ではないのか？
張り出しのないオクトリーは、これとまったく同じ形になるはず
このレンダリング方式では各列が3Dの箱なので、2x2ボクセル行列と呼んでも特に問題ないと思う
1990年代に高校で必要な三角法を学びながら、こうした地形ビューアを作っていた記憶は本当に良いものだ。最初はPascalで、その次はCとAssemblyで作った
当時は動かすために、ありとあらゆる低レベル最適化が必要だった
参考にできる本やインターネットなしで実装方法を突き止め、最適化したことは、個人的に最もやりがいのあったことの一つだ
この手法でゲームを作った: https://eri0o.itch.io/i-rented-a-boat
Adventure Game Studioで作ったもので、まだ最適化していなかった以前のバージョンのエンジンで制作した。itchページを更新するのが面倒でそのままにしているが、いつかはやるつもりだ
そこにどう作ったかを書いてあり、AGSフォーラムにはさらに詳しい内容がある
タイトルに**[2020]**を入れてもよさそうで、下の議論リンクの他のコメントを見ると[2017]でもよさそうだ
同じリポジトリについての2021年の議論もあった: https://news.ycombinator.com/item?id=26631995
そのスレッドからも別の議論へリンクが続いている
まったく同じではないが、プログラミングを学び始めたころ、地形のハイトマップを生成し、似た手法でアイソメトリック風のレンダリングをするプログラムを書いた記憶がある。QBasicで作り、中学校にあった386時代のDOSマシンで動かし、グラフィックメモリを一時作業領域として使っていた
とてつもなく遅かったが、出力結果に魅了され、プログラミングを続けるきっかけの一つになった
以前どこかでこれを読んだ記憶があるが、今回は失くさないようにコメントを残しておく
フライトシミュレータのファンとして、Comancheを初めてプレイしたときの衝撃は今でも覚えている。未来か映画から来たもののようで、本当にコンピュータの時代に生きているのだと感じた
Comanche 4とオリジナルのBlack Hawk Downでは、この方式をやめてポリゴンエンジンへ移行したようだ: https://en.wikipedia.org/wiki/Comanche_4#Reception
[0] https://www.youtube.com/watch?v=FbZ-chrOgGg 地球への着陸シーンは1:00に出てくる
本当にすごい
現代のゲームの多くでは、変なカメラアングルやクリッピングの問題で、山が中空構造だとたまに見えてしまう
しかしこの方式では、山はしっかり詰まっている >:)
こういうソフトウェアレンダラを趣味で作ってみることを強くおすすめする。レイトレーサはよくあるプロジェクトだが、こうしたレトロ風のリアルタイムレンダリングコードも週末プロジェクトに向いている
かなり昔に、ほぼ同じアルゴリズムを実装したことがある。正確には、canvas2dを学ぶ練習としてSDLコードを移植した: http://namuol.github.io/earf-html5/
もちろん、リンク先の実装のほうが私のものよりずっと速く、ずっと単純なので、参考資料を探しているなら、私の古いCoffeeScriptコードはおすすめしない…