時空間ウォークスルーのためのデータ構造
西田研究室 池本 和生
1. はじめに
近年，CG技術の進歩により，かなり大規模な3次元仮想世界の構築が可能となってきている．しかし，将来，時間的変化まで考慮した4次元の世界を扱うことになるとその規模はさらに増大するため，その効率的なデータ管理および高速なデータ検索が大きな課題となってくる．
本研究では，3次元空間＋時間的変化の4次元の仮想世界を対象とし，その時空間に対してリアルタイムなウォークスルーを実現するデータ管理方式を提案する．
2. ウォークスルーへの木構造の適用
時空間に対するリアルタイムなウォークスルーを実現するためには，膨大な時空間データの中から描画に必要なデータのみを高速に切り出す技術が必要となる．そこで，本研究では時空間範囲検索を効率化したAT構造を用いて仮想世界を管理し，描画する時空間の視野領域を検索範囲に対応させることで，空間に加え時間まで含めたクリッピングを実現する．AT構造とは，時間情報によるデータ構造（時間木）と空間情報によるデータ構造（空間木）の2つの木構造を作成し，検索要求に応じて検索木決定ロジック部で適応的に検索する木構造（全範囲に対する検索範囲の割合の小さい方の木構造）を切り換える手法である（図1(a)参照）．なお，従来の研究により，ST・3D管理構造に比べて検索効率の点で優れていることが知られている．そして，連続的な時空間移動（入力）に対して逐次検索範囲を更新して検索を実行し，検索されたオブジェクトを描画するといった操作を再帰的に繰り返すことによりウォークスルーが可能となる（図1(b)参照）．
図１
3. 提案するデータ管理方式
本研究では，管理対象として設備や建物などの複数状態を有する静止物体を考える．そこで，「全状態を対象とした描画」，「特定状態を対象とした描画」の2つを考え，各描画方式に合致したデータ管理方式をAT構造をベースとして構築する．複数状態を有するデータを管理するには，「複数状態を1つにまとめた管理」，「状態ごとに分割した管理」の2つの管理方式が考えられ、「特定状態描画（全状態数:N）」の場合には，AT構造の時間木，空間木ともに「状態ごとの管理」を適用した（図2(b)参照）．一方，「全状態描画」の場合には，計算機実験を行い，時間木，空間木ともに「1つにまとめた管理」の方が検索効率がよいという結果が得られ，こちらを適用した．また，視野領域の遠景部分では多くの場合高層なオブジェクトしか見えず，低層なオブジェクトの描画を省略するため，オブジェクトの高さに応じて階層的に木構造で管理するレイヤ構造（レイヤ数:M）を「全状態描画」に導入した（図2(a)参照）．
図２
4. 評価実験
本提案方式のレイヤ構造の導入による有効性の評価実験を行った．具体的には，本提案方式と2つのサンプル方式，Ⅰ:「クリッピングなし（全空間を対象）」，Ⅱ:「レイヤ管理なし（全視野領域を対象）」の3方式に対して，同様なテスト経路を50フレーム分（前半:空間移動，後半:時間移動）ウォークスルーした場合のフレーム更新時間（検索時間＋描画時間）を求めた．表1に50フレーム分の結果を平均したものを示す．
表１
本提案方式と方式Ⅱ:「レイヤ管理なし」に着目すると，レイヤ構造を導入することで確実に描画ポリゴン数を減少し，フレーム更新時間を若干ではあるが短縮できることが確認できる．しかし，レイヤ数を増やしすぎると検索する木構造の数も増加するため，省略されるポリゴン数が全体に対して若干なものであれば効率が悪くなると考えられる．
5. 結論
本研究では，3次元空間＋時間的変化の4次元の仮想世界を対象とし，その時空間移動に対してリアルタイムな描画を実現するため，AT構造にレイヤ構造を導入したデータ管理方式を提案した．実際に構築した仮想世界の時空間をウォークスルーする評価実験では，レイヤ構造導入の有効性が確認された．今後の課題としては，評価対象についての検討，動的データへの拡張，直接操作を可能とするインタフェースの構築などが挙げられる．