ウェブ上の仮想形状生成

福井幸男(fukui＠cs.tsukuba.ac.jp),　三谷純(mitani＠cs.tsukuba.ac.jp)

はじめに

本実験課題は3次元形状をウェブ上に載せるための基礎実験を行う。手順は大きく分けて次の3段階で行う。

3次元形状データの取得(計測)
3次元形状データ処理（データ量削減）
3次元形状データのWebへの掲載

本実験を通じてウェブ上での形状表現手法と形状データ処理のアルゴリズムを学ぶ。

実験の流れ

実験の流れは次に示す通りである。

実験室3C315室の3次元形状測定機NextEngineを用いて3次元形状を計測する。
NextEngineに付属のソフトウェアを用いて3次元形状データを構築する。
3次元形状データをOBJ形式で保存し、自身のアカウントのディスクに転送する。
OBJ形式のデータをJavaアプレットで表示できることを確認する。
OBJ形式で表現された3次元形状データに対してデータ量削減用のプログラムを作成する。
データ量を削減した形状データをWeb上で閲覧できるようにWebページを作成する。

上記の流れの5番目が本実験で主となる課題である。本実験を通じてウェブ上での形状表現手法と形状データ処理のアルゴリズムを学ぶことを目的とする。

【注意】
以下の説明は、3C113室のMac上で実験を行うことを前提としているが、自身で自由に使える環境が別にあるのであれば、任意の環境で行って構わない。各種ツールはJavaで作成されているため、プラットフォームに依存しないようになっている。ただし、3C113室のMac以外を使用する場合は、Javaを動作させる環境は各自の責任で確認し、必要に応じて各自で整備すること。また、プログラムの開発はC,C++,Javaなど自分の得意な言語を用いてよい。
なお、毎回3C113室に置いてある出席表にサインを記入すること。

課題提出要領はこちらを参照すること

3次元データの取得(計測)

3次元形状計測機NextEngineの操作について

実験室3C315室の3次元形状測定機(NextEngine)を用いて、対象物の3次元形状データを取得する。測定機はPCから制御して行う。基本的にはTAが操作をサポートするが、添付のマニュアルを参照して基本操作を理解すること。マニュアルは接続されているPCでも参照できる。計測用コンピュータのパスワードは実験初日の説明の時に伝える。

計測機の原理

微弱なレーザ光線を対象物に走査しながら照射し、このスポット反射光を別の角度からビデオカメラで撮影する。スポット像の位置から三角測量の原理で奥行き量を含めた3次元的な位置情報を取得する。このとき、レーザ光のスポット像ばかりでなく、物体形状、物体上のテクスチャも同時にビデオ撮影する。したがって、後で立体像を生成したときに、テクスチャを載せることも可能である。ただし、本実験ではデータ量が多くなるので、実物のテクスチャは利用しないことにする。

測定対象物に関する注意

本実験で使う被測定対象物は各自で準備すること。計測対象物として不適当なものは以下のようなものであるのでこれらの特徴を持つ形状は避けること。

外形の大きさ、重さに関して

大きさが極端に大きいもの(20cm立方以上)、または極端に小さいもの(5cm立方未満)
極端に重いもの(数kg以上)(回転テーブルに載せることができなくなる恐れがあるから)

表面状態に関して

色が極度に濃い(黒い)物体(反射するレーザ光を撮影して位置計測するので、色が濃いと反射光が撮影できなくなる)
鏡面反射する物体(反射したレーザ光がカメラの方向に返ってこないため)
表面の位置を識別する模様やテクスチャ、しわが全くない状態(複数画像の位置合わせができない)

形状に関して

レーザ光が陰となって見えなくなるような、深いくぼみ、穴のある取手、入り組んだ形状等

データ出力

計測し、補正、修正などを施したデータをVRML形式のオプションを選んでファイルに出力する。ファイル出力先はDドライブ上の一時ファイルフォルダとする。このファイルを各自の作業領域（例えばcoinsのアカウント領域）へ転送する。

注意点

測定機は1台なので交代で使うこと。
測定機を使う順番がまわって来ない間は自分のデータが得られないので、その間はサンプルデータを使用して、先のステップに進んでおく。

3次元形状データの表示

データの形式

3次元の形状を面の集合で表現するためのデータには、多面体の幾何情報を表す各頂点の3次元座標値(x,y,z)と、面がどのような頂点で構成されているかを表す位相情報が含まれる（3次元の形状を曲面の集合や中身の詰まった立方体（ボクセル）の集合で表現する方法などもあるが、これらはそれぞれデータの表現方法が異なる）。

一般に多面体をコンピュータ内で表現するためには、頂点、稜線、面を区別し、それらの接続関係を記述した位相情報を用いる。さらに、頂点の3次元座標値(幾何情報)も別途保持しており、相互に参照できるデータ構造をもつ。

図1の三角柱の例で、位相情報がどのように表現されているかを説明する。

図1　三角柱

図1では頂点に1から6までの番号を振って識別している。面は（）で囲まれた数字(1)～(5)で表わす。3次元形状を表現するファイル形式の一つとして、OBJ形式というものがある。OBJ形式では、頂点座標値が1番の頂点から順に記述されている。そして、稜線の記述は無く、各面がどの頂点で構成されているかを表す頂点番号のリスト(頂点ループリストと呼ぶことにする)を保持している。表1を参照すると、1番の面(上面の三角形)は頂点1,2,3の順で面が構成されていることがわかる。

表1　三角柱のOBJ表現

2番の面は四角形であるので、頂点は4つとなる。実際のデータは次のように1行ごとに頂点または面の情報が記述されている。

v 0.000000 100.000000 100.000000
v 86.602547 100.000000 -49.999989
v -86.602539 100.000000 -50.000004
v 0.000000 -100.000000 100.000000
v 86.602547 -100.000000 -49.999989
v -86.602539 -100.000000 -50.000004
f 1 2 3
f 1 4 5 2
f 2 5 6 3
f 4 6 5
f 1 3 6 4

行頭の記号「v」と「f」で頂点情報と面情報を区別し、「v」で始まる行には頂点のx,y,z座標が、「f」で始まる行には、面を構成する頂点の番号が空白区切りで並べられる。頂点の番号は、ファイル中に登場する頂点情報を上から順番に見てきた時の順番を表す1以上の整数である。

ここで重要なことは、頂点ループの順番である。頂点ループは面の表から見て、左回りに順番に頂点番号を並べていることである。これを右回りに記述すると面の向きが逆である（物体の内側から面を見ている）と解釈される。

Javaアプレットでモデルを表示する

OBJ形式の3次元形状を表示するために、OBJViewというJavaアプレットを用いる。

アプレットの入手

アプレット用のクラスファイルファイルはOBJView.jarというファイルでアーカイブ化されている。このファイルをこちらからダウンロードして入手すること（jarファイルは解凍せずにそのまま任意のディレクトリに保存する）。

AppletViewerでアプレットを実行する

次の内容のテキストファイルを作成し、上記jarファイルの存在するディレクトリに保存する。ファイル名は自由でよいが、ここでは仮にapplettag.txtとする。ただし、このテキストファイル中の「model.obj」の部分は、表示するOBJファイルのファイル名にすること。

<applet
   code=OBJView.class
   archive="OBJView.jar"
   width=400
   height=400 >
   <param name="filename" value="model.obj">
</applet>

上記と同じディレクトリにOBJファイルをコピーしておき、次のようにコマンドを入力する。

%appletviewer applettag.txt

すると、アプレットビューワが起動し、OBJファイルに記述された3次元モデルが表示される。

参考までに、OBJViewのJavaソースコードがこちらから入手可能である。Javaのプログラム、および3次元形状の扱いの参考にしてよい。

3次元形状データ処理：データ量削減

ネットワーク上で3次元形状データを扱うときは、記憶容量や転送スピードを考慮すると、可能な限り少ないデータ量が望ましい。そこで、本実験ではデータ量の削減をメインテーマとしてプログラムを作成することを課題とする（以下のアルゴリズムを開発する段階では、大量の実験データでは処理時間がかかりデバッグの効率が悪くなるため、三角柱などの簡単なデータ構造を手作業で作成して頂点座標値、および頂点ループの表を用いると便利な場合がある）。

面の削減

データ量を減らす方針として、面の数を減らすことを行う。面を削除する際には全体の形状を大きく変化させないように気をつける必要がある。

面の削減方針

面を削減するために、図2のように隣接する面の共通稜線ACに注目して、その長さを無限小に縮めるという操作を行う。これによって頂点C、稜線AC、2面(△ABC,△ACD)の削減を行うことができる。このように稜線を削除することで2つの面を同時に削減する方法をEdge collapseという。 OBJ形式のデータの場合、データの中に稜線の情報は明記されていないが、面を構成する頂点のループから稜線を決定することができ、また同一の稜線を共有する面が2つあれば、その2つの面は互いに隣接関係にあることがわかる。

図2　稜,面,頂点の削減

削除する稜線を選ぶ

上記のEdge collapseを繰り返すことで面の数を減らすことができる。しかし、ランダムに削除するのではなく、元の形がなるべく維持されるような戦略を考える必要がある。例えば、削減される面に隣接した近傍の面が、削減される面とほとんど同じ方向を向いていればそのうちの一つの面を消去して残りの面の面積を大きくして、おきかえても全体の形状の変化は少ないだろうと考える。
図2の例では△ABC、△AEB、△BFCの3つの面がほぼ同じ向きで、一方、△ACD、△ADI、△DCHの3つの面が互いにほぼ同じ向きであれば(このとき、△ABCと△ACDは必ずしも同じ向きである必要はない)△ABC、△ACDを図2の一番下の図のように削減しても、全体の形状の変化は小さいはずである。また、稜線の長さが短いものを選ぶ、または面積の小さい面を消すようにを選ぶ、というような戦略も有効である。どの稜線を優先的に削除すると効果的であるかは、複数のケースで実験を行い比較すること。

このEdge collapseのステップを他の部分にも適用していくことで、全体の面数、頂点数を削減してゆく。

特殊なケース

面の接続関係が特殊な図3のような場合は、稜線ACの長さを0にして2面△ABC、△ACDを消去しても、△AKB、△BKCは消去されずに、重なって△A'KB、および、△A'BKとなって存在することになる。一般的に、1つの稜線が属する面は2つ（境界部分では1つ）であるが、この場合は4つの面に属することになってしまう。このままだと後の処理で問題を起こすことがあるため、物体からはみ出したこれらの2つの面も消去しておく必要がある（または、そもそもこのような特殊なケースではEdge collapseを行わない、という方法もある）。

各面の法線方向

複数の面が同じ向きになっているかどうかを調べるには、面の単位法線ベクトルを求め、それらの内積が1に近くなれば、ほぼ同じ向きなっていると見なすことができる。一般に3次元空間内にある3個の頂点P_i(x_i,y_i,z_i)(i=0,1,2)からなる三角形の法線方向をn(n_x,n_y,n_z)とすると、nは次式で表される。
　　　n_x=y₀z₁-y₁z₀+y₁z₂-y₂z₁+y₂z₀-y₀z₂
　　　n_y=z₀x₁-z₁x₀+z₁x₂-z₂x₁+z₂x₀-z₀x₂
　　　n_z=x₀y₁-x₁y₀+x₁y₂-x₂y₁+x₂y₀-x₀y₂

　参考のために、n個の頂点P_i(x_i,y_i,z_i)(i=0,1,..,n-1)からなる多角形の場合の法線方向n(n_x,n_y,n_z)は次式で表される。(稜線を左回りにベクトル積を繰り返すことで得られる。)

ただし、

、

とする。

(注意：この法線ベクトルは単位ベクトルではないので、改めて単位ベクトルにする必要がある。また、多角形の場合、各頂点は同一平面上に存在することを前提としている。)

注目する隣接する3角形対に隣接した面を取り出す

削減しようとしている隣接する面対の各面(図2では△ABC、△ACD)に隣接する面、合計4つの面(△BAE、△BFC、および△DCH、△ADI)を見つける。見つけ方は、面を構成する頂点ループ(たとえば辺BC)をみて、同じ頂点対(この場合は辺CB)があるかどうかを探索する。同じ頂点対がある面ループを持つ面が目的の面となる。

隣接する面の平面度の計算

各面の単位法線方向ベクトルから、面の相互の傾き具合を調べる。相互の傾き角が少ない(同一平面内に近い)と各面の単位法線ベクトルは近い方向にあるので、内積が1に近くなる。この内積を平面度と定義する。
2つのベクトルm(m_x,m_y,m_z),n(n_x,n_y,n_z)の内積は
　　　m_xn_x+m_yn_y+m_zn_z
で求まる。

面の削減

平面度がある閾値より大きいとほぼ同一平面内にあると見なす。従って、注目する面対の片側の3つの面(△ABC、△EBA、△BFC)がほぼ同一平面内にあり、他の片側の3つの面(△ACD、△ADI、△DCH)もほぼ同一平面内にあることがわかれば、面対(△ABC、△ACD)を消去しても形状の変化は少ないはずであるから消去する。
　面を消去する手続きは次の通りである。

稜線ACの長さを0にする操作であるから、点A、点Cのどちらか一方を残して、他方を消去することにする。一方を消去後、残された頂点は元の2頂点A、Cの中点とするのが適当である。
仮に点Cを消去するとした場合、面を定義する頂点ループのリストの中で、頂点Cを参照している部分を探して、全て頂点Aを参照するように変更する。

削減の繰り返し

　隣接する面対を選択して消去する操作を繰り返すことで、面と頂点のデータ量を削減する。このとき、形状全体を考慮して選択する稜線を探索する場所が均等に散らばるように工夫が必要である。消去する面対が局所的に偏ると全体としての形状がひずむ場合がある。

3次元形状データのWebへの掲載

HTMLファイルの作成

公開用のWebページとなるHTMLファイルを作成する。アプレットを配置したい場所に、AppletViewerで用いたタグを挿入すると、その場所に3次元形状を表示するアプレットが埋め込まれた形でWebページが表示される。

ファイルの配置

アプレット用のクラスファイル全てと、HTMLファイル、およびモデルデータのOBJファイルを公開用の同一のディレクトリに配置する（例：~/public_html/applet/）。以上で、設置作業は完了する。ブラウザでHTMLファイルを閲覧すると、アプレットが表示されるはず。

発展課題

以下の課題への取り組みは任意である。余力のある学生はチャレンジすること。

前処理としての形状平滑化

計測機で取得されるデータは、一般的にノイズを多く含み、滑らかでない（激しい凹凸を含む）形が得られることが多い。そこで、データ量削減の前処理として、形状を滑らかにする「平滑化処理」を行うことを考える。

この平滑化は、面の削減などは行わず（位相変化を伴わない）、単に頂点を移動させることだけで実現する「ラプラシアンスムージング」の手法を用いることとする。このアルゴリズムの次のように極めて単純なものである。

「各頂点Pを、Pの1近傍頂点の重心に移動する」

これは下図のように、点Pに着目した場合、点Pから1つの稜線を介して隣接する位置にある点V(1～5)の重心Gに点Pを移動させる操作を、全ての頂点に対して行う、ということである。

ラプラシアンスムージングは極めて単純なアルゴリズムであるため、次のようなケースでは面が反転して好ましくない結果になることがある。さらに余力がある場合は、この問題への対処方法も考慮すること。

補足

開発についてのヒント

開発言語には何を用いても構わないが、C++/C#/Javaなどのオブジェクト指向型言語を用いる場合は、以下のようなクラスを作成し、物体←面←頂点の階層構造にするとよい。
- Model: 物体を表す。内部に複数のFaceおよびVertexを保持する。
- Face: 面を表す。内部に、面の輪郭を構成するVertexを保持する。
- Vertex: 頂点を表す。x,y,z座標を保持する。
- (Edge: 無くてもよいが、あると便利な場合もある。始点と終点のVertex、左右のFaceを保持する。）
C/C++言語を使用する場合、複数の頂点や面の情報を格納するのに配列を用いてもよいが、後で削除処理によって面の数や頂点の数が変化することを考慮すると、STL(Standard Template Library)のVectorまたはListを使用すると便利である（STLを知らない場合は各自で検索して調べること）。

レポート提出時の注意

最終結果は外部からブラウザで確認できるように、必要なファイル一式を各自のcoins上のpublic_htmlディレクトリ以下に配置し、そのURLも報告すること。
ソースコードを印刷するときは、紙の消費が少なくなるように、文字を小さくすること。
C++/C#/Java言語のclassまたはC言語のstructの定義部分には、それぞれの変数が何を意味するか必ずコメントを入れること。

概要に戻る