2009年06月17日

BSP法の源流を追う〜ジョン・カーマックによるDOOMの実装からQUAKE WARSまで

BSP(Binary Space Partitioning)法とは、壁などの境界を延長して、空間を2分して
行く方法です。3DFPSの原点の一つ(技術的には本当に原点)DOOM(id Software)で
位置解析や、AIのI空間認識、パス探索システムのデータ、などに採用されたことから、Quake シリーズを通して引き継がれています。

 
 bsp.JPG
 
 http://www.beyond3d.com/content/articles/102/2
 http://www.beyond3d.com/images/articles/ingenu-part-2/bsp.png
 
@ Quake Wars における BSP法

intechweb
 http://intechweb.org/

では、無料で、高品質な技術書籍のPDFファイルががダウンロードできるようになっています。
その中でも、

Motion Planning
 http://intechweb.org/book.php?id=74&content=title&sid=1

は、実際のロボットからゲーム内のパス検索までの研究成果を集めた書籍になっています。

この分野は、これからレベルデザインが複雑化するにつれて、AIのための、
地形情報(世界表現)を生成する上で、欠かすことの出来ない技術分野で、
より専門化が進むと予想されます。

例えば、22番目の記事

22  Automated Static and Dynamic Obstacle Avoidance in Arbitrary 3D Polygonal Worlds
J.M.P. van Waveren and L.J.M. Rothkrantz

は、Quake Wars  http://www.enemyterritory.com/
で使用された、AIのためのパスデータ自動生成法が解説されています。

[概説]
@全ての三角形メッシュの傾きを計算する。45度以上のメッシュは通行不可とする。
A通行不可のメッシュを境界として、延長しマップ全体を再分割する(BSP法)。
B動的なパス検索に関しては、落下して来たオブジェクトを床に対して射影し、
 その輪郭をパスとすることで対応する。

J.M.P. van Waveren の一連の論文を読まれていると、より理解が深まることでしょう。
          http://mrelusive.com/publications/pubs_bydate.html

特に、彼の修士論文(CEDEC2006の自分の講演で示唆したことがあるのですが)は、
BSP法が詳しく解説されています。

The Quake III Arena Bot
 J.M.P. van Waveren
   Master of Science thesis, Delft University of Technology, June 2001

   http://www.kbs.twi.tudelft.nl/Publications/MSc/2001-VanWaveren-MSc.html

A 3DFPSにおけるBSP法の源流を訊ねる(有名人大集合…)
以下の、Michael Abrash氏のコラムに情報があります。

Michael Abrash's Graphics Programming Black Book Special Edition
  http://www.phatcode.net/res/224/files/html/index.html

ちょっと面白いので引用してみましょう。
http://www.phatcode.net/res/224/files/html/ch60/60-01.html

In early 1993, I hired Chris Hecker. Later that year, Chris showed me an alpha copy of DOOM, and I nearly fell out of my chair. About a year later, Chris forwarded me a newsgroup post about NEXTSTEP, and said, “Isn’t this the guy you used to know on the DDJ bulletin board?” Indeed it was John Carmack; what’s more, it turned out that John was the guy who had written DOOM. I sent him a congratulatory piece of mail, and he sent back some thoughts about what he was working on, and somewhere in there I asked if he ever came up my way. It turned out he had family in Seattle, so he stopped in and visited, and we had a great time.

1993年、私はクリスヘッカーを雇った。その年の暮れ、クリスは私にDOOMのアルファ版を
見せてくれた。私は、驚いて椅子から転げ落ちそうになった…。

All this is surprisingly closely related to this chapter’s topic, BSP trees, because John is the fellow who brought BSP trees into the spotlight by building DOOM around them. He also got me started with BSP trees by explaining how DOOM worked and getting me interested enough to want to experiment; the BSP compiler in this article is the direct result. Finally, John has been an invaluable help to me as I’ve learned about BSP trees, as will become evident when we discuss BSP optimization.


BSP ツリーは、ジョンカーマックがDOOMに組み込むことで注目を集めた技術なんだ。

posted by miyayou at 02:29| Comment(0) | TrackBack(0) | 日記
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス: [必須入力]

ホームページアドレス: [必須入力]

コメント: [必須入力]

この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/29853941
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック