第五章 大規模グラフィックスデータの高速表示
5.3 グラフィックスデータの階層化と削減方法の評価
前節及び前々節で述べた二つのデータ削減方法（頂点マージ法及び複数頂点マージ法）を用いて一 つのグラフィックスデータに対して複数のデータ削減を行い, その削減されたデータの量に応じて 段階的に表示を行うと, グラフィックスデータの階層化表示を行うことができる. 本章における研究 では, 対象とするグラフィックスデータとして, VRML(Virtual Reality Modeling Language)[21]を用 いることにした. VRML とは, インターネット上の表記言語であるHTML(HyperText Markup Language) の３次元グラフィックス版であり, インターネットを介して３次元コンピュータグラフィックスを 扱う上での業界標準となるデータ形式である. VRML は元々, SGI 社の Open Inventor を基にしたもの であるが, 現在では, SGI, IBM, SUN など主なコンピュータメーカが参画する VAG(VRML Architecuture Group)により, その仕様が決定されている. VRML は単なるグラフィックスデータの形式を定めたも のではなく, インターネット上での動きを記述することもできる言語であるが, 本研究ではデータ形 式だけを用いてデータの削減と階層化の実験を行った.
図 5‑3 に示すドルフィンは 285 頂点, 563 三角形から構成される VRML 形式のグラフィックスデータ である. 図 5‑4 及び 5‑5 に頂点マージ法及び複数頂点マージ法により階層化されたデータの表示結果 を示す.
図5-3 ドルフィン（285頂点, 563三角形）
(b) 150頂点296三角形
(c) 100頂点196三角形 (d) 50頂点96三角形 (a) 200頂点395三角形
図5-4 頂点マージ法によるグラフィックスデータの階層化
(b) 147頂点289三角形
(c) 100頂点194三角形 (d) 50頂点92三角形 (a) 198頂点391三角形
図5-5 複数頂点マージ法によるグラフィックスデータの階層化
図 5‑4 では, グラフィックスデータの削減に伴いドルフィンの形状も徐々に劣化しており, ほぼ予 想通りの階層化を実現することができた. しかしながら, 一度に複数の頂点を削除した複数頂点マー ジ法では図 5‑5 に示すように, データを削減するにつれてドルフィンの形状が急激に劣化しているの が分かる. これは, 一度に複数の頂点を削除するために新たな頂点を生成したことから, データ削減 を重ねるにつれて新たに生成された頂点の影響により, ドルフィン形状が元形状から急激に離れて いったものと推測される. そこで, 頂点マージ法及び複数頂点マージ法をもう少し定量的に評価する ために, 各方法を用いた場合のデータ削減に要する時間及びデータ削減に伴い発生する誤差の解析 を行った.
頂点マージ法 複数頂点マージ法
頂点数
0 50 100 150 200 250 300
2 4 10
6 8 データ削減時間
(分）
図5-6 頂点マージ法及び複数頂点マージ法に要するデータ削減時間
頂点マージ法 複数頂点マージ法
頂点数 誤差
50 100 150 200 250 300
0 20 40 60 80 100 120
図5-7 頂点マージ法及び複数頂点マージ法の誤差
データ削減プログラムは Lisp を用いて作成し, Sun Workstaion(SPARC Station 1)にて実行させた 結果が図 5‑6 である. 複数頂点マージ法は新たな頂点を生成することにより一度に複数の頂点削除を 目的としたものであるため, 一度に一つの頂点しか削除できない頂点マージ法に比べてデータ削減 時間が短いことが分かる. しかしながら図 5‑7 に示すように, 同じ頂点数まで削減したデータを比較 した場合, 元の頂点から新たに生成される面までの距離誤差が, 頂点マージ法に比べて複数頂点マー ジ法の方が大きいことが分かる. つまり, 図 5‑4 及び図 5‑5 を比較した際に, 複数頂点マージ法のグ ラフィックスデータの方が頂点マージ法のグラフィックスデータに比べて形状の劣化が大きい定量 的な裏付けが出来たことになる.
結局, 新たな頂点を生成して一度に複数の頂点削除を行うよりも, 元の頂点座標を変更することな く一度に一つの頂点削除を行った方が, 最終的な誤差及び形状の劣化が少ないことが分かった. そこ で次節では, 頂点マージ法により削減及び階層化されたデータを基に, 粗い形状データから詳細な形 状データへと徐々に復元する階層化表示方法について検討する.