可視空間追跡法による高速3D表示：三次元スペースモデルの研究

全文

(1)Vol. 42. No. 5. May 2001. 情報処理学会論文誌. 可視空間追跡法による高速 3D 表示：三次元スペースモデルの研究大. 沢. 晃†. 芦. 川. 宏††. 広く用いられているハードウェア Z–バッファによる三次元表示は，処理量が図形数 N に対し O(N ) のため，ハードウェアがいかに高速化しても建築やプラントのウォークスルーなど大規模図形では速度に限界がある．最近 Visibility Culling と称して，本来不可視な図形の処理を省略する高速表示法が報告されているが，対象図形への制限が強かったり，前処理に長時間を要したりする等の問題があった．今回 CAD 等に用いて高性能が期待できるスペースモデルのデータ構造を活用し，これらの問題を解決する方式を検討した．スペースモデルはソリッドモデルと異なり図形内外を対等な空間として分割し，これをポインタで表現して隣接空間や重なり図形を直接検索可能にする幾何モデルである．三次元表示では，視点から可視面に達するまで可視空間をポインタでたどって検索することで，屋外の景色や極端に疎な図形分布などを除き，可視空間数 V に対し O(V ) と N によらぬ速度が期待できる．本方式は視線をたどる点でレイトレーシングと似ているが，ピクセルごとでなく，分割した空間単位で視線を追跡することで高速化している．現時点では任意形状の三次元モデルの自動生成は未完のため今回は四面体に限定したが，実験の結果 O(V ) を実証し，大規模リアルタイム表示への適用可能性を示した．なお，現在は速度向上のために，スペースモデルの高速衝突検出機能を利用して Z バッファを使用しない高速表示方式を検討中である．. Fast 3D Rendering by Using Visible Space Tracing Technique: Basic Study on Three-Dimensional Space Model Akira Ohsawa† and Hirosh Ashikawa†† In spite of resent progress of hardware, the speed of hardware-Z-buffer that is commonly used for three-dimensional display is not enough for very large objects like buildings, manufacturing plants, and such because the processing time takes O(N ) where N is the total number of figures in the geometry. To cope with this problem, high-speed display methods called “Visibility Culling” that omit essentially invisible objects are recently reported. However, they have problems like too much restriction on the shapes of the objects or too long pre-processing time prier to the display. In this paper, as a kind of “Visibility Culling Methods”, a new display method named “Visible-Space-Tracing” that overcomes the above problems using a CAD data structure called “Three-Dimensional Space Model” is described. In this method, the figures to be displayed are effectively retrieved by tracing only visible spaces in the Three-Dimensional Space Model using pointers. The order of the processing time is O(V ) where V denotes the number of visible divided spaces in the geometry because the range of retrieval of the figures is limited within the visible spaces. The processing time O(V ) and the high-speed only for software algorithm is demonstrated with the results of our experiments. Because, however, it is even too slow for real-time rendering of large geometries, we are now studying faster next generation method.. ハードウェアが高速化しても建築の CAD やプラント. 1. はじめに. のウォークスルーなど大規模図形では速度に限界があ. 広く用いられているハードウェア Z–バッファによる. る．最近 Visibility Culling と称して本来不可視な図. 隠面消去表示は処理量が図形数 N に対し O(N ) で，. 形の処理を省略する高速化法が報告されているが，対. † 中部大学工学部情報工学科 Department of Computer Science, College of Engineering, Chubu University †† 株式会社シーティーアイ CTI Co., Ltd.. たりする等の問題があった．今回 3 章で述べるスペー. 象図形への制限が強かったり，前処理に長時間を要しスモデル（ SPM ）のデータ構造1)∼3)を活用し，これらの問題を解決する方式の基礎検討を行った．図 1 は多少の誇張はあるが，三次元 SPM（ 3DSPM ）によ 1134.

(2) Vol. 42. No. 5. 可視空間追跡法による高速 3D 表示：三次元スペースモデルの研究. 1135. 表面が一部でも可視なら下位を調べ，最下位の立方体表面まで可視部があればその内部の図形を隠面処理し表示する．その途中のどの段階でも，オクツリー立方体表面が完全に不可視なら内部は不可視として一括省略する．市販の Z–バッファ・ハードウェアでは立方体の可視性判定結果をソフトにフィードバックできないため，ピクセルを 4 個ずつまとめる多段階層構造のソフトウェア Z–バッファ（ Z–ピラミッド）を使用する．また，文献 6) では不可視図形を調べるために，ある程度の大きさで視界を遮る可能性の高い図形をまとめて. P.O.（ potential occluder ）として全体から事前にオフラインで抽出しておく．実行時にはソフトウェアによる階層式 Z–バッファを使用し，P.O. に隠される階層型バウンディングボリウムの表面が不可視なら内部図1 Fig. 1. 三次元 SPM の狙いと可能性 The capability of 3DSPM.. を一括省略して効率向上し，火力発電所全体のウォークスルーを行っている．しかしこれらはいずれも事前のオフライン処理に多大の処理時間を要し，CAD 処. る CAD の狙いと可能性を示す．本研究の表示では，. 理とのリアルタイム連携には問題を残している．. SPM の隣接空間高速検索機能を利用し，視点から順. これに対し今回の方式では SPM 構築には O(N ) の. に遠いほうへ視線に沿って可視空間をたどり，可視面. 時間を要するが，SPM によって集合演算や衝突検出. に達したら表示する．可視面の陰に完全に隠れる不可. 等の CAD 処理を行えばただちに表示が可能になる．. 視空間は検索しないことで，屋外の景色や極端に疎な. その他，BSP Tree 7)でも手前から順に図形面を取. 図形分布などを除き，可視空間数 V に対し O(V ) の. り出すことは可能であるが，今回のように可視の可能. 速度を実現する．本方式はレイトレーシングと似てい. 性のない図形の処理を省略することは困難と思われる．. るため「可視空間追跡法（スペーストレーシング）」と. また，上記文献で苦労している Z–バッファは，今. 名付けた．ピクセル単位でなく，分割した可視空間単. 回は 3.2 節で示す高速でエリアシング問題のない二次. 位で視線を追跡することで高速化を図ってはいるが，. 元 SPM によるスペース・Z–バッファを用いて改善し. 4 章に示すように，リアルタイム表示にはまだ低速である点が今後の改良点（ 5 章）として残っている．. た．さらに 5 章に示す次期システムでは Z–バッファ. 現在は基礎研究段階で，3DSPM 構造の自動生成プログラム等が未完のこともあり，今回は四面体に限定し O(V ) の検証にとどめた．以下 2 章では従来の方. 自体を不要にする方向で検討している．. 3. SPM（スペースモデル）の原理 3.1 SPM の概念. 式を，3 章で 2D および 3DSPM の原理を概説，4 章. SPM の概念は二次元，三次元共通である．概説が. で空間追跡法の原理と実験結果，5 章で問題点と今後. 長くなるが，3.2 節で二次元，3.3 節で三次元の原理を. の改良計画「視界膨らせ法」を説明する．. 概説する．なお 3.2 節では今回採用の 2DSPM による. 2. 従来の方式. 隠線消去方式スペース Z–バッファ3)についても説明する．なお，二・三次元 SPM の詳細は文献 1)∼3) を参. 不可視図形の処理を省略して高速化する Visibility Culling の主な手法を概観する．文献 4) は Cells and. 照されたい．. Portals Algorithm と呼ばれ，建物内部のウォークスルーに適した方法で，空間をビルの間仕切りに合わせて区切り，不可視図形の処理を省略している．しかし，. ソリッドモデルなど従来のモデルは個別図形の表現に. 屋外や機械設備等では効率的な区切りが困難で汎用性. と考え，空間の隣接や重なり，すなわちトポロジーを. に欠ける．文献 5) では空間全体をオクツリー階層構. ポインタで表現する．SPM ではトポロジーに矛盾を. 造の立方体に区分し，立方体表面の可視性を階層上位. 起こさない処理だけに限定することで，計算誤差や座. でかつ視点に近い方から Z–バッファで調べ，立方体. 標値の退化にもアルゴリズムの破綻がなく，安定なプ. SPM は CAD 等に用いる幾何モデルの一種である．終始し，図形相互の位置関係は座標値以外では表現していない．これに対し SPM は図形内外を対等な空間.

(3) 1136. 情報処理学会論文誌. Fig. 2. 図 2 重なった三角形の SMP SPM for overlapped triangles.. May 2001. 図 3 2DSPM における隣接図形要素の検索 Fig. 3 Retrieval of the neighborhood in 2DSPM.. ログラムが実現できる．SPM はポインタの分メモリ. SPP には図 2 のように重なりを示す属性を付加す. が多く，2DSPM で 1 頂点 50∼100 バイト，3D では. る（多角形外部の属性値はゼロ）．これを利用すると. 1 頂点 200∼500 バイト（今回は 212 バイト）を要する．しかし，集合演算や衝突検出がオーダー違いに高速であるから，メモリの価格低下で十分にペイすると 3.2 （二次元）2DSPM と隠線/隠面消去. AND，OR 等の図形集合演算や隠面・陰線消去が高速に実行できる．すなわち AB 以外の属性 A と B をすべてゼロとし，両側の空間の属性が相等しい不要辺を消せば AB 部が図形の AND として残る． A ， B ， AB をすべて ‘1’ として不要辺を消せば OR と. 図 2 に重なった三角形を例として 2DSPM のデー. なる．これらは SPM が生成されていれば局所処理で. タ構造を示す．SPM では頂点間で相互に指しあうポ. 思われる．. る鉛直仮想境界線 Bx を想定し，図形内外の空間を Bx. O(1) と高速である．隠面/陰線消去は，2DSPM をスクリーン・バッファとしてスクリーン上の図形 A と B の重なり部の属性 AB を視点から近い面の属性（たとえば A ）に変更して不要辺を消去する．2DSPM. と図形辺とで小空間に分割する．辺と辺の交点は一種. にはつねに Z（奥行き）方向に最も近い面のデータの. の頂点として陽に表現する．Bx は仮想線なので上下. みを持たせるので「スペース・Z–バッファ」と呼ぶ3) ．. の辺との交点は直接には表現せず，Bx の通る頂点に. ピクセル対応の Z–バッファと違い面としてデータ持. 設置された座標値だけで表現する．分割された各小空. つため，後の図形処理に都合が良い．本論文 4 章の可. 間には左右端の頂点間で相互に指しあうポインタ SP. 視空間追跡法ではこの機能を活用する．. インタ EP（ Edge Pointer ）の組 EPP（ EP Pair ）で辺を表現する．次に各頂点を通り上下隣の辺まで伸び. （ Space Pointer ）の組 SPP（ SP Pair：図 2 細矢印）. 図 3 は隣接要素の検索法を示す．図で空間 SPP0 を. を設置する．EPP と SPP には両端頂点の座標値の辞. 与えれば左隣の空間 SPP1 は頂点 V1 を介し検索でき. 書順の大小を表す X 方向フラグを付加する．辞書順. る．+Y 側の辺 EPP1 の端点 c1 には，この辺の下側. では Y にかかわらず X の大きい方を +（右）側，X. 空間の SPP が必ず接続するから，辺 EPP1 は SPP0. が等しいときは Y が大きい方を +側とする．X ，Y. から破線矢印の順に SPP をたどる回転サーチで求め. ともに等しい頂点や，他の辺に重なる頂点，三辺以上. られ，さらに上方への回転サーチで SPP2 が求められ. の同一点での交差は，座標値は同じでもトポロジカル. る．これらは辺長や頂点数が有界でないとか，マイナ. には重ならず，相互に無限小ずれているとする．これ. ス（プラス）X 向きに尖った V1 や V2 のような頂. で鉛直辺はわずかに右傾した斜辺とされ，X 値の等. 点が X 方向に O(N ) 個並んで，EPP1 を求める回. しい 2 頂点のそれぞれを通る Bx は重ならず，間に無. 転サーチの手数が最悪 O(N ) になる等の特殊な場合. 限小幅の空間ができる．以上ですべての小空間の左右. を除けば O(1) と高速である．大規模図形で検索の場. 端には SPP の接続する頂点が必ず 1 個だけ存在する. 所がランダムなら，特殊な場合の発生確率は N の増. ことになり，SPP は小空間を 1 対 1 で表現するとい. 大とともにゼロに近づくとしてよいから，最悪手数が. えるので，これを SPM（スペースモデル）と呼ぶ．. O(N ) でも平均すれば検索手数は O(1) となる．.

(4) Vol. 42. No. 5. 可視空間追跡法による高速 3D 表示：三次元スペースモデルの研究. 1137. 2DSPM は EPP と SPP をブランチ，頂点をノードとする有向平面グラフで，任意図形要素（頂点，辺，小空間）の隣が直接検索できるので二次元のトポロジーを表現するといえる．多角形 N 個の SPM 生成では，前処理として図形の存在領域全体を N/k 個（ k は定数）の格子状に区分し，各区分内に道しるべ点. Gi (i = 1, 2, ..N/k) を SPM 上に設置する．入力多角形ごとに始点 p に最寄りの Gi に直接ジャンプすれば（各図形の頂点数と辺の長さが有限で，かつその分布に極端な偏りがない実用的な図形では，各区分内の頂点数は有限としてよいから）p の位置は Gi から SPP をたどって O(1) で検索できる．p から EPP で表現す. 図 4 四角形 1 個の場合の空間分割と SPP Fig. 4 Space-division and SPP’s for a square.. る辺を伸ばして SPP を更新しながら辺を一巡する多角形の入力も，頂点数や辺長が有界なら 1 多角形平均. O(1)，N 個全体では O(N ) となる1) ．当初の Gi 設置と SPM 生成後の削除は O(N ) で可能である．SPM 生成，多角形挿入・削除，集合演算などの詳細は文献. 1)∼3) を参照されたい． 3.3 （三次元）3DSPM 3DSPM は 2DSPM の拡張形である．空間に四角形面が 1 個ある場合の空間分割と SPP を図 4 に示す．図示してないが辺（稜）は EPP で，面は FPP で表現する2) ．2D では各頂点を通り X 軸に垂直な仮想線. Bx を設置したが，3D では各頂点を通り X 軸に垂直な仮想面 Bx を設置する．また各稜線を含み Z 軸に平行な仮想面 By も設置する．二次元と類似して，Bx 面は ±Y 方向隣の By まで伸びてそこで終わり，Z 方向は ±Z 方向隣りの図形面 Bz（仮想面ではない）まで伸びてそこで終わる．図形面 Bz どうしの交線は稜線の一種として陽に表現する．しかし Bx と By は仮. 図 5 3DSPM における影の交差 Fig. 5 Shadow-intersection in 3DSPM.. 想面なので，Bx と By の交線，Bx と Bz 面の交線，い．Bx は頂点の X 座標値だけで表現され，By はこ. に平行な交線 c1 c 1 が存在し，その上にこれらで挟ま 1，れた小空間（影の空間）を表現する SPP（太破線. れを規定する稜線だけで表現される．Bx ，By ，Bz 面. 2 ）を終端する仮想的頂点 c1 ，c2（影の交点）を設置. および By と Bz 面の交線はいずれも陽には表現しな. により空間は台形柱または三角柱の小空間に分割され. する．影の空間数は全 n 個の辺の相互位置関係によ. る．そのとき，各頂点の座標値 X ，Y ，Z を辞書順に. り，たとえば図形がすべて無限長で相互に不平行な線. 並べて，その大きいものほど +X 側にあると考える．. 分なら最悪値 O(n2 ) になる．しかし機械や建築等の. X ，Y ，Z ともに等しい頂点や交点，他の面に重なる. 実用的な図形では，長さ太さともに有限で，かつ影の. 頂点や稜線は，座標値は同じでもトポロジーは重なら. 交差を起こす By は Z 側隣の図形面 Bz で遮られて. ず，相互に無限小ずれているとする．これで Z 軸に. 遠くには影響しないため（例：図 5 (b) で b1 c 1 を含. 平行な辺はわずかに Y および X 方向に傾斜とされ，. む By は A 面で遮られる）影の空間数はほぼ O(n) と. X 値の等しい 2 頂点のそれぞれを通る Bx は重なら. いえる．. ず，両者の間に無限小幅の空間ができる．. 以上の空間分割により各小空間の ±X 端には SPP. 特に 3D では Z 方向に隣り合い，X–Y 面への射影. が接続する頂点が必ず 1 個ずつ存在し，SPP は 1 対 1. が交差する図 5 の a0 a1 と b0 b1 のような稜線が存. 対応で小空間を表現するといえる．図形間の重なりが. 在する．この稜線を通る各仮想面 By の間には Z 軸. なければ，影の空間以外では SPP はすべて頂点に接.

(5) 1138. May 2001. 情報処理学会論文誌. 図6 Fig. 6. SPP の空間属性 AB による重なり表現 Space-attributes AB show overlaps.. 図8. スペーストレーシング（可視空間追跡法） Fig. 8 Space-Tracing method.. char ei;//相手 Ptr 項番 e と i を 1 バイトに圧縮 char ptyp;//ポインタタイプ SP，EP，FP 等 char dirtag;//ポインタ X 方向＋／−. }; class Ptr3{//3 辺頂点でのポインタ Pt の格納位置 Fig. 7. 図 7 三次元回転サーチによる隣接図形の検索 Retrieval for adjacency by 3D rotary searches.. class Pt *pt; Ptr3(){pt = new Pt;} char Position;//頂点におけるこの Pt の位置. 続し，各頂点に接続する SPP の数は最大 9 個（ 3 辺. char LSidePtr;//この Pt の左隣面/空間を示す. が接続する頂点）と定数のため，影の交差以外の小空. char RSidePtr;//この Pt の右隣面/空間を示す. 間数は O(n)，影の空間との合計の全小空間数 S は最. }; class TVTX:public VTX{//3 辺頂点：3 辺突合せ点. 悪値 O(n2 )，実用上は O(n) となる．図 6 のように SPP に重なり属性を付加（一部の SPP のみ図示）して集合演算ができることは二次元から容易に類推できる．隣接空間が高速検索できることも二次元と同様である．図 7 は面 F1 の上 (+Z) に. 2 つの四面体 P1，P2 がある例で，P2 から Y 側回転. float x, y, z;//頂点座標値 Ptr3 ptr3[3][8];//辺 e と面/空間 i:ptr3[e][i] }. 4. 可視空間追跡法（スペーストレーシング）. サーチで P1 を検索する様子と，P1 から Z 側検索回. 図 8 の可視空間追跡法では 3DSPM の隣接空間検. 転サーチで F1 を検索する様子を示す．この機能によ. 索で，視点から遠い方へ可視面 A に達するまで可視空. り運動図形の衝突検出が平均 O(1) と高速に実現でき. 間をポインタでたどり，A 面に達したら 3.2 節で述べ. る（現時点では未実装）ことも二次元と同様である．. たスペース・Z–バッファ法で 2DSPM によるスクリー. 参考のため 3 辺突合わせ頂点の C++クラス表現を. ンバッファ上で可視性を判定し表示する．完全に A に. 示す．なおポインタ属性，メンバー関数等は省略した．. 隠れる不可視空間は検索しないので処理量は可視空間数 V に対し O(V ) となる．V の最悪値は全小空間数. class VTX{//頂点・交点・影の交点等の親クラス ...... //頂点にも立体，面分，線分等各種あり. S に等しく，S の最悪は辺数 n に対し O(n2 ) となるが，前章で述べたように実際には S はほぼ O(n) で，. };. さらに視界は付近の物体に妨げられるため，機械や建. class Pt{//ポインタ本体 (頂点種類によらない) class VTX *p;//相手頂点先頭を指すポインタ. 築物等，ある程度密な大規模図形では，V はかなり大きな値にはなっても n にはよらない．実際，視界中.

(6) Vol. 42. No. 5. 可視空間追跡法による高速 3D 表示：三次元スペースモデルの研究. 1139. の有限奥行きまでの図形でスクリーンが埋め尽くされるなら，それより遠方には可視空間は存在しない．最も厳しいのは見晴らしの良い屋外の景色等であり，これらは今回の対象から外さざるをえない．以下，3DSPM は生成済みとして空間追跡法のアルゴリズムを示す．なお視点から可視の i 番目の空間 Vi を登録するため，待ち行列 FIFO を準備する．. (1). 初期位置から視点まで SPP をたどり注目点を移動．図形 N 個のランダム分布なら，たどる手数は三次元空間を線状に進む距離によるから √ 平均 O(3 N ) となる．しかし絶対値は小さく，図形数千個程度なら 1 ms 以下で無視できる（無視できないときは 3.2 節の道しるべを使い O(1). 図9 Fig. 9. にできる）．. (2) (3). 高速 O(V ) 表示実験データ上面図 Looking down for the test data.. 到達した視点が物体内ならただちに終了する．視点が物体外なら，これを可視空間 Vi として，待ち行列 FIFO に登録する．. (4). FIFO が空で取り出す空間がなければ終了する．このときスクリーンは可視面で覆われた状態である．. (5) (6). FIFO から 1 個の可視空間 Vi を取り出す． Vi の壁（ X ，Y ，Z 正負側）の中で視点から可視の向きで，かつ視界ピラミッド中にある壁を順次 2DSPM によるスペース Z–バッファに投影する．. (7). 投影された壁が完全不可視なら，何もせずに. ( 4 ) へ． (8). 投影された壁が Bx か By（図 8 面 B ）で一部分でも可視なら，奥の空間の一部は可視なので，次に調べる空間として待ち行列 FIFO に登録し. (9). Fig. 10. 図 10 P1 から 2 個の小型四面体 B が見える Two small tetrahedrons on the screen at P1.. ( 4 ) へ．投影された壁が図形面（図 8 の面 A ）で可視位置にあれば表示し，FIFO には登録せず ( 4 ) へ戻る．. 5. 実験と検討 5.1 実験結果プログラムは VisualC++で作成し，Pentium III 400 MHz，メモリ 128 MB のパソコンで実行した．図 9 は実験データの上面図（ +Z 側から −Z 方向を見た）で，大型四面体 A の左側 2 個の小型四面体 B と，A の右側に斜線状に見える 140 個の微小四面体群 C で構成されている．視点 P1 から矢印方向を見たのが図 10 で，2 個の B を表示後，視線は A の面で遮られ C は検索せず終了，可視空間 43 個，可視面（ A を含み）7 面，処理時間 40 ms であった．視点 P2 から見たもの. 図 11 P2 から微小四面体 C140 個と A の一部を見る Fig. 11 Tiny 140 tetrahedrons and A in the screen at P2..

(7) 1140. May 2001. 情報処理学会論文誌. 図 12 可視空間数と処理時間 Fig. 12 Visible spaces vs. processing time.. 図 13 可視空間追跡方式：一部可視空間もチェック Fig. 13 Space-Tracing: Partially visible spaces must be checked.. は図 11 で，C の列に続き A と無限遠のバックグランドを表示する．この場面では多面体内部以外の空間はほとんどが可視のため，実可視面 125 個に対し可視空間が 2670 個と多く可視判定と表示に約 2.0 秒を要した．図 12 は処理時間の実測値で，O(V ) を確認した．. 5.2 問題点と「視界膨らせ法」による改良計画上記実験の結果，処理時間が O(V ) ではあるが，リアルタイム表示には遅く改良の余地があることが分かった．遅い原因の 1 つを図 13 に二次元的に示す．薄墨部は真の視界，斜線部は一部が可視の空間である．この方式は可視空間の壁を（不可視図形 E も）全部. Z–バッファで調べ（ F は調べない）効率が悪い．時間的コヒーレンシが利用できない点も問題である．. 図 14 視界膨らせ法（可視面衝突方式）：Z–バッファ不要 Fig. 14 Visibility balloon inflation without Z-buffer.. 対策として 3DSPM の高速衝突検出機能（参考：文献 8)：2DSPM の高速衝突検出の説明）を活用する. 中にポインタで直接的に検索するので高速化が. 図 14 の「視界膨らせ法」を検討中である．この方式では視界を視点から奥（同図右）方向へ膨らせる．膨. 見込まれる．. (3). して表示．さらに衝突部分以外を膨らせ，未衝突部分. 三次元クリッピング（視野ピラミッド）処理が不要．. らせ途中で視界の奥の面が図形に衝突したら可視面と. (4). 時間的コヒーレンシの利用：視点移動や図形の. がなくなれば終了する．膨らせの途中では，視界の奥. 運動で視界が変化する場合，視界多面体に出入. の面は広がりながら視点から奥方向に運動する穴を含. りする頂点でトポロジーが変化する部分だけ局. む大きな多角形となり，視界全体が 1 つの巨大な視界. 所的に SPP 等のポインタを更新する．局所更. 多面体となる．膨らせの途中では視界多面体の変形に. 新なので高速である．ただしトポロジーが不変. ともない 3DSPM の空間分割が変化するから，これに. でもスクリーン図形は変形（座標値変化）する. 合わせて逐次 SPP，EPP，FPP 等のデータ構造を更新しつつ衝突検出を行う．視点に近い側から可視面を. ので再表示は必要である．. (5). 視界を視点側から膨らせるので，時間切れで膨. 順に検索するので，一種の「欲張り法」でもある．こ. らせを中断しても近傍図形は表示され，連続表. の具体化には任意方向への視界の膨らみに対するデー. 示では最初のフレームから続くフレームへ順に. タ構造の更新と衝突検出等かなりの技術開発が必要だ. 遠方へ視界が伸びるが，人間の目の特性から違. が，次のような多くの利点が見込まれる．. 和感は少ないと思われる．. (1) (2). Z–バッファが不要でその分高速化する．衝突候補（図 14 E 含む）面は視界膨らせ処理.

(8) Vol. 42. No. 5. 可視空間追跡法による高速 3D 表示：三次元スペースモデルの研究. 6. むすび三次元スペースモデルの基礎検討として，可視空間追跡法による表示を検討し，表示処理時間が可視空間数 V に対して O(V ) であることを実証した．CAD 処理を三次元スペースモデルで行うことにすれば，CAD 処理後特別なオフライン処理なしでただちに本方式による表示ができる点に特徴がある．しかし実験の結果，. 1141. erarchical Occlusion Maps, Proc. SIGGRAPH 97, pp.77–88 (1997). 7) Naylor, B.: Partitioning Tree Image Representation and Generation from 3D Geometric Models, Proc. Graphics Interface 92, pp.201– 212 (1992). 8) 大沢晃，宮地充：二次元多角形の衝突検出と押し詰め：スペースモデルの応用，情報処理学会論文誌，Vol.38, No.3, pp.548–554 (1997). (平成 12 年 9 月 25 日受付) (平成 13 年 3 月 9 日採録). 表示速度がリアルタイム用としては不十分なことも明確になった．今後は 5 章に示した視界膨らせ法による高速化を検討するとともに，3DSPM データ構造の自動生成を実現し，集合演算等の確認を進めていく予定である．. 大沢. 晃（正会員）. 1936 年生．1961 年名古屋大学大. 参考文献 1) 大沢晃：二次元スペース・モデリングの考察，情報処理学会論文誌，Vol.27, No.12, pp.1174– 1185 (1986). 2) 大沢晃：三次元スペース・モデリングの考察，情報処理学会論文誌，Vol.27, No.12, pp.1186– 1196 (1986). 3) 大沢晃：スペース Z–バッファ：安定で高速な隠線・隠面消去：二次元スペースモデルの応用，情報処理学会論文誌，Vol.38, No.4, pp.779–786 (1997). 4) Teller, S.J., et al.: Visibility Preprocessing for Interactive Walkthroughs, Proc. SIGGRAPH 91, pp.61–69 (1991). 5) Green, N., et al.: Hierarchical Z-buffer Visibility, Proc. SIGGRAPH 93, pp.231–240 (1993). 6) Zang, H., et al.: Visibility Culling Using Hi-. 学院工学研究科修士課程応用物理専攻修了．同年（株）日立製作所入社，制御用計算機回路，半導体用 CAD 等開発．1992 年中部大学工学部情報工学科教授．現在に至る．スペースモデルによる図形処理の研究を行う．工学博士．電子情報通信学会会員．芦川. 宏 1974 年生．1999 年中部大学大学院博士課程前期工業物理学専攻修了．大学時代にスペースモデルと出会い. 3 次元図形処理に興味を持つ．現在株式会社シーティーアイ在籍．システムエンジニアとして，Java による Web 系業務システム等の開発を担当．.

(9)