情報処理学会論文誌, vol.34 (9), pp.1994-2001, 1993.9

仮想空間における折り紙の対話型操作の実現

宮崎慎也　安田孝美　横井茂樹　鳥脇純一郎

グラフィックスハードウェアの進歩に伴い，グラフィックス環境を用いた人間に親しみやすいヒューマンインタフェイスの構築が可能になってきている．CGによるビジュアルな環境を利用すれば，コンピュータ内に定義された仮想空間中の物体を実物と同じように操作することが可能になる．本論文では，仮想空間中に表現された紙に対し「折り曲げ」「折り返し」「折り込み」の対話操作が可能な折り紙のシミュレーションシステムを開発したので報告する．オペレータはスクリーンモニターに表示された３次元仮想空間内の紙をマウスデバイスにより紙面の頂点を摘まんで移動する感覚で操作できるので，実物を折るような感覚で仮想の紙を自由に折ることができる．この操作は視点移動により紙をあらゆる方向から観測しながら行なうことができ，この操作を繰り返すことにより一枚の紙を複雑な形状に容易に加工できる．また，頂点や辺同士を正確に重ねて折る場合にはそれらの微妙なずれは自動的に補正されるので，実際に紙を折るよりも正確かつ容易に仮想空間の紙を折ることができる．本文ではシステムの実現において特に重要な，紙面の接続や重なり関係等の折り紙の状態を２分木リストにより記述する方法，折り操作に従ってリストを高速に変更する方法，マウス入力により３次元空間内にある紙の頂点の位置を移動するための工夫などについても述べる．

INTERACTIVE MANIPULATION OF ORIGAMI IN 3D VIRTUAL SPACE

Shin-ya Miyazaki, Takami Yasuda, Shigeki Yokoi, and Jun-ichiro Toriwaki

With advance of graphics hardwares, possibility of natural man-machine interface using graphic environments is drawing attention. Visual environments using computer graphics are very effective for virtual object manipulation. This paper describes a visual simulation system of ORIGAMI (paper folding art) which realizes interactive folding operations of paper such as 'Bending,' 'Folding up' and 'Tucking in' in real-time. In the system, a piece of virtual paper is defined in a three dimensional (3D) virtual space and displayed on a graphic screen. An operator can fold it freely and iteratively into complex figure, observing it from an arbitrary direction and manipulating it as if he is folding a real paper, by picking and moving a vertex of the paper using a mouse device. If the position of the picked vertex is different from operator's intentional position delicately, it is corrected automatically in the case of matching the picked vertex to another vertex or matching two edges to each other. This function has the operator fold a virtual paper more rapidly and accurately than folding a real paper. This paper also presents how to represent the state of folded paper such as connectivity and overlap relation between paper faces and how to realize interaction using a mouse device in the system.

1. まえがき

グラフィックスワークステーションの性能が急速に進歩し画像の生成速度が向上するに伴い，グラフィックス環境を利用したヒューマンマシンコミュニケーションの新たな可能性が注目されるようになった．リアルタイムで高速に生成されるコンピュータグラフィックスを利用すれば，オペレータはコンピュータ内に定義された仮想的な３次元世界の物体を実物を操作するような感覚で操作することが可能となり，設計，娯楽，教育，訓練などをはじめとし様々な分野への応用が期待されている．仮想世界の物体に対して実物と同じ様な操作を行なう研究は数多く報告されているが，それらのほとんどは物体とのインタラクションの際に空間内の物体位置を正確に指定したり，力覚をフィードバックしたりするための入力デバイスの開発に重点を置いており，ソフトウェアによる仮想物体の記述や操作などに関しては剛体の移動や切削による塑性素材の加工など単純なものがほとんどである[1] - [8]．このような仮想空間操作を様々な分野へ適用していくために，今後はより複雑な性質を持つ仮想物体をコンピュータ内に定義し，仮想物体との様々なインタラクションを実現していくことが必要と考えられる．

本論文では，紙という比較的単純ではあるが折れ曲がるという性質をもつ非剛体の素材を対象とし，３次元の仮想空間に存在する１枚の紙を自由に折るプロセスをリアルタイム操作で実行できるシミュレーションシステムを開発した．オペレータはリアルタイムで変化していく仮想空間の状態をスクリーンを通してモニターしながら，マウスデバイスで制御される空間内の操作点を使って紙の頂点を摘まんで自由に移動できるので，実物の紙を折るような感覚で仮想の紙を折ることができる．基本的な折り方として「折り曲げ」「折り返し」「折り込み」の３種類を用意し，これを組み合わせることにより紙を複雑な形状に容易に加工できる．視点はボタン操作により常時変更が可能であり，折り紙をあらゆる方向から観察しながら操作が行なえる．更に，頂点や辺同士を正確に重ねて折る場合にはそれらの微妙なずれは自動的に補正されるので，実際に紙を折るよりも正確かつ容易に仮想空間の紙を折ることができる．また，本システムは仮想的な空間に対する自由な操作を実現しているため，データグローブやヘッドマウントディスプレイ (H.M.D.) などのデバイスを用いることにより人工現実感システムへの応用も可能である．

1.1 折り紙を対象とした従来の計算機システム

折り紙を対象とした計算機処理に関しては既にいくつか報告されているが，これらの文献と本論文との関連について述べる．[9] は，あらかじめ入力した何枚かの折り紙のキーフレーム画像から中間画像を生成し紙が折られる過程のアニメーションを作成するものであり，折り紙の状態を記述する必要がないので紙の面同士の重なりや接続の関係を記述する方法に関して触れられていない．[10] は折り紙の展開図から紙の物理的な制約条件をもとに出来上りの状態を推論するものでありタワーと呼ばれるリスト構造による折り紙の表現を提案しているが，１回の折り操作に対応したタワーの変更手順が示されていない．[11] では初めて折り紙の対話型操作を可能にしたが，入力操作がいわゆる仮想空間操作ではなくメニュー選択方式であり，折り紙の状態を表現するためのデータ構造も十分洗練されているとは言えない．これらのシステムとは異なり本システムでは，紙面の接続や重なり関係等の折り紙の状態を折り操作に従って高速に変更可能な表現方法で開発するとともに，実物の操作感覚に近い入力操作を実現している．

2. 折り紙シミュレータ

本システムでは，紙の１つの頂点を移動することにより１回の折り操作を指定する．本章ではこの基本操作により実現される折り方の種類とその入力方法，及びそれらを実現するために必要となるシステムの処理について述べる．

2.1 折り方の種類（図１）

(1) 折り曲げ (Folding up)，折り返し (Bending)
紙の操作の基本単位となる１回の折り操作は，紙面上に定められた，ある１本の線 (折れ線) により紙面を２分割し，そのうち一方の面を折れ線を軸に回転させることで実現される．既に幾度か折られた紙を対象とするとき，面同士の重なり，接続の関係から次の折り操作で複数の面が同時に回転する場合 (多重折り) と１つの面のみが回転する場合 (一重折り) がある．いずれの場合についても移動する全ての面が同一方向に回転する折り方を「折り曲げ」と呼び，そのうちで面の回転角度が180度(平面折り)のものを特に「折り返し」と呼ぶ．

(2) 折り込み (Tucking in)
もう１つの折り方として，ある面を境に面の回転方向が異なる「折り込み」が用意されている．「折り込み」は「折り返し」と同様，平面内の多重折りであるが，紙面同士の関係から「折り込み」が不可能な場合があり，更に多重に重なった「折り込み」では折り方の候補が複数存在する場合がある．本システムでは折り紙を重なり順序を持つ面の集合として表現しており，頂点の移動により折り操作を行なうので，複数候補の「折り込み」からの唯一の選択や，「折り返し」と「折り込み」の選択は頂点の移動先が同一となるためこれらの指定が更に必要となる．実際には折られる全ての面の回転部分の形状が同一で対称的に折り込む場合が多いので，「折り込み」操作をこのような場合に限定した．また，「折り返し」と「折り込み」の選択についてはボタンの On, Off の状態により指定することとした．「折り込み」が可能であるかどうかの判定については，かなり複雑で様々な場合を考慮する必要があり計算処理が膨大となるので行なわないこととした．オペレータは自分の頭の中で折りが可能かどうかをイメージできるので，これは実際の操作においてはそれほど重要な問題とはならなかった．

これらの基本的な折り方を組み合わせることにより複雑な多重折りも実現できる（図２）．


(a) 折り返し	(b) 折り曲げ

(c) 折り込み

図１　３種類の基本折り

図２　基本折りの組み合わせによる複雑な折り方

2.2 仮想マニピュレータの定義

仮想物体操作を行なうシステムでは，仮想空間内の物体を操作するために同空間内に仮想のマニピュレータを定義する必要がある．本システムでは紙面の頂点を摘まんで移動するための３次元座標ポインタ Picker を仮想空間内に定義し，マウスデバイスにより制御する．Picker はマウスの中央ボタンの On, Off にそれぞれ対応する 'PICK' 及び 'RELEASE' の２つの状態を持つ．状態 'PICK' 時には Picker はある頂点を摘まんで (Pickして) おり Picker の移動に伴いその頂点も移動するが，状態 'RELEASE' 時には Picker は紙と離れて単独で移動する．Picker 自身の位置は，スクリーンに平行な２方向についてはスクリーン上のマウスカーソルの位置で与えているが，奥行方向については３つのマウスボタンのうち両サイドの２つのボタンにより制御している．左ボタンが押されている間 Piker は一定の速度で視点から遠ざかる方向に移動し，右ボタンについてはその逆である．Picker の奥行方向の位置は 'PICK' 時には Pick している頂点の位置にあるので折り紙のスクリーンへの投影像から大まかな位置を得ることができるが，'RELEASE' 時にはわからない．現在は Picker を２次元のマウスで制御しているが，3Dディジタイザなどの他の入力デバイスに置き換えることも可能である．

2.3 折れ線及び折り曲げ角度の決定

紙の折りを指定するためには折れ線 (面の回転軸) 及び折り曲げ角度 (面の回転角度) を決定する必要がある．Picker により移動される頂点の，移動元と移動先の２点からの等距離平面と，折られる面との交線が折れ線となり，これら２平面の交角の２倍が折り曲げ角度となる（図３）．頂点の移動先が同じ「折り返し」と「折り込み」は，折れ線と折り曲げ角度は同一となるが，折り結果の面の重なり順序が異なる．

図３　面の折れ線と折り曲げ角度

2.4 マウス入力による基本操作（図４）

本節では実物の紙を折るのに近い感覚で仮想の紙に対するリアルタイム操作を可能にするための，紙の頂点を摘まむ，頂点を摘まんだまま移動する，頂点を離す，動作からなるPickerの基本操作について述べる．

(1) 頂点の選択
マウスの中央ボタンを押した瞬間に Pickerの状態が'PICK'に変わり，紙面の全ての頂点のうちから選択された唯一の頂点 (選択頂点) がPickerによりPickされる．この時Pickerの位置は選択頂点の位置 (選択頂点の移動元) に変更される．Pickerを制御して頂点の空間的な位置を正確に指定することは難しいため，２次元のスクリーン投影像上でPickerから最も近い頂点を選択頂点とすることにする．候補が複数存在する場合は頂点の属する面の順序が視点から最も近いものを選択するようにする．

(2) 頂点の移動
ボタンを押している間 (Pickerの状態'PICK'時) Pickerの移動に伴い自動的かつ逐次的に，選択頂点の移動先座標の獲得，それに従う折れ線と折り曲げ角度の決定，折り結果のスクリーンへの表示が行なわれる．この反復は非常に短い時間間隔で行なわれるので，オペレータはスムーズに変形する折り紙を観測しながら，マウスを操作し頂点を直接移動することにより折れ線と折り曲げ角度をリアルタイムで自由に変化させることができる．

(3) 頂点の解放
ボタンを離した瞬間にPickerの状態が'RELEASE'に変わり，選択頂点の移動先が固定され，この時の折り結果が折り手順のヒストリーに登録される．以後Pickerは頂点と離れて単独で移動する．

図４　マウスデバイスによる基本操作

2.5 選択頂点の移動先の自動補正

マウス操作で頂点を移動させることにより，例えば頂点や辺同士を正確に重ね合わせることは非常に面倒なことである．これらの操作をスムーズに行なうためには，インタラクションの際に頂点がオペレータの意図する位置と微妙にずれている場合これを訂正する必要がある．本システムでは以下の４つの場合において選択頂点の位置を自動的に補正する．

(1) 頂点同士を重ね合わせて折る
選択頂点とある程度近い頂点が存在すれば選択頂点の位置をその頂点の位置に変更する．

(2) 辺同士を重ね合わせて折る
選択頂点を含む辺とある程度近い辺が存在すれば，それら２辺が同一直線上で重なるように頂点の位置を変更する．２辺の距離には一方の辺と，他方の辺の両端点との距離を利用している．

(3) 折れ線がある２つの頂点を通る
折れ線からある程度近い頂点が２点存在すれば，折れ線がその２点を通るように頂点の位置を変更する．

(4) 基準角度で折り曲げる
折り曲げ角度が90°又は180°(基準角度) にある程度近いならば，折り曲げ角度がその基準角度となるように頂点の位置を変更する．基準角度に180°を加えることにより，「折り返し」，「折り込み」の平面折りを容易にしている．また，折り曲げ角度を180°以下に制限し視点側にしか折り曲げられないようにインタラクションを単純化することにより，更に折り操作を容易にしている．

これらの補正機能が働くとオペレータは，例えば頂点や辺同士が互いに引き合うように，頂点に目に見えない引力が働いているかのように感じられる．この結果，実際に紙を折るよりも正確かつ迅速に仮想の紙を折ることが可能になる．また，これらの補正を解除したい場合にはマウスを大きく移動すればよい．

2.6 視点の移動

本システムでは４つの基本的な視点移動の組み合わせにより，仮想空間内の折り紙を任意の角度，距離から自由に観測できる．観測物体 (折り紙) を原点，視点をX軸上に置くとすると，視点のX,Y,Z軸の周りの回転により視線方向が変更され，視点のX軸上の移動により物体との距離が変更される．各操作はそれぞれ２つのキーにより制御される．この操作は頂点を移動しながら行なうこともできる．

3. 折り紙のためのデータ構造

本章では折り操作により変化していく折り紙の状態を正確に記述するためのデータ構造について述べる．折り紙は折れ線により分割された複数の面の集合であり，基本的にサーフェイスモデルで表現している．データ全体は面層，辺層，頂点層と呼ばれる３つのデータ層により構成されている．

3.1 面層について

面層は面の分割を表す面セルツリーと面の重なり順序を与える面セルルックアップテーブルにより構成される（図５(a)）．

(1) 二分木リスト構造
折り紙は１回の折り操作によりいくつかの面が２分割されるので，面情報の記憶には基本的に二分木のリスト構造が適している．１つの面の情報を持つ面セルが木の節に位置し，面の２分割の際には対応するセルに子のセルが２つ生成され，それらが分割後の２つの面を表す．葉のセルの集合が現在の折り紙の状態を，木構造全体が折り操作による面分割の過程の全情報を表している．

(2) 面グループと面スタック
過去の「折り曲げ」により全ての面が同一平面上にない場合，同一平面上の面をグループ化することにより全ての面はいくつかのグループ (面グループ) に分けられる．各グループには同一平面上にある複数の面に重なり順序 (面番号) を与える面スタックがあり，全ての面セルはいずれかのグループの面スタックに属する．図５(d)で３つの面のうち面F1は単独で１つのグループを形成する．面セルルックアップテーブルはグループ番号，面番号により対応する面セルを面セルツリーから高速に検索する．

3.2 辺層について

辺層は辺の分割を表す辺セルツリーから成る（図５(b)）．辺セルツリーは面セルツリーと同様二分木のリスト構造であるが，面の分割に伴って辺は分割されるだけでなく新しく生成もされるので，それに伴い辺セルツリーの総数は増加する．

3.3 頂点層について

頂点層は頂点セルの線形リストと頂点セルルックアップテーブルにより構成される（図５(c)）．頂点セルは対応する頂点の空間座標を保持しており，折り操作に伴う頂点の移動の履歴を頂点セルの線形リストで表す．頂点セルルックアップテーブルは頂点セルリストから頂点番号により対応する頂点の現在の位置を高速に検索する．

図５　１枚の折り紙を表現するためのデータ構造

3.4 データ層間の相互検索

データセルは他の層の関連するセルをポインタにより検索できる．この検索は後述のリストの更新や面のレンダリングの際に高速に行なわれる．例えば面セルはその面を構成する辺セルへのポインタ配列（図６(a)）を，辺セルはその辺を含む面セルへのポインタ及びその辺の両端点の頂点番号（図６(b)）を保持している．

図６　面の分割に伴うセルの更新

4. リストの更新

前章で述べたリスト構造のデータ群は折り操作の際に更新される．本章ではデータリストの更新手続きについて述べる．

4.1 移動面の探索

多重折りにおいて選択された面が折られる際，辺の共有による面の接続，面の重なりから一緒に折られる他の面を探索 (移動面探索) する必要がある．図７の折り返しにおいて，面F2は面F1の移動に伴い一緒に移動する．３つの面のうち面F3だけが不動面である．移動面探索の手順を以下に示す．

①選択頂点を含む面は明らかに移動面である（図７の面F1）．
②ある面が移動面ならその面の移動部分において辺を共有する面は移動面である（図７の面F2）．
③「折り返し」「折り曲げ」の場合，ある面が移動面ならその面と，面の回転していく側で移動部分が重なる面は移動面である．
④「折り込み」の場合，ある２つの面が移動面ならその２面の間にあり，それらの面の移動部分と重なりがある面は移動面である．
⑤ ①～④の手順により移動面とならなかった面は不動面である（図７の面F3）．

図７　折り操作における３種類の面

4.2 移動面の分類

すべての移動面は折れ線の両側にまたがる分割面（図７の面F2）とそうでない非分割面（図７の面F1）に分類される．分割面は折れ線により２分割され一方の面が回転するが，非分割面は分割されず面全体が回転する．これらのうち分割面についてのみ面層，辺層の更新が行なわれる．この分類は面の頂点と折れ線との位置関係を調べることにより行なわれる．

4.3 面の分割に伴う面セル，辺セルの更新

面の分割に伴う面セルと辺セルの更新手続きを図６の三角形の分割面を例に示す．三角形の面 F0 は，頂点 V1, V2, V3 及び辺 E1, E2, E3 により構成され，分割されて面 F1, F2 になる．これに伴い辺 E1 は分割されて辺 E11, E12 になり，新しい辺 E4 及び頂点 V4 が生成される．この時のセルの内容の変更過程を以下に示す．

① F0 の分割に伴い面セル F1, F2 および辺セル E4 が新しく生成され，E4 を含む面が F1, F2 に決定される．ただし E4 は新しい辺セルツリーの根である．
② E1 の分割に伴い辺セル E11, E12 および頂点セル V4 が新しく生成され，E11, E12 の内容と E4 の１つの端点が決定する．また E11, E4 が F1 の構成辺に E4, E12 が F2 の構成辺に加えられる．V4 の座標もこの時に計算され頂点セルルックアップテーブルに登録される．
③ E2 を含む面の１つが F0 から F2 に変更され，E2 が F2 の構成辺に追加される．また E4 の残りの端点が V3 に決定される．
④ E3 を含む面の１つが F0 から F1 に変更され，E3 が F1 の構成辺に追加される．

更新手続きは辺の数が4以上の面についても同じ要領である．また多重折りの際には全ての分割面に対して更新手続きが行なわれる．

4.4 頂点セルの更新

移動面探索における面の重なり判定は頂点を移動する前に行なわれるので，頂点セルの更新は面セル，辺セルの更新後に独立して行なう．全ての移動する頂点について子のセルを生成し，面の回転による頂点の移動後の座標を与える．以後これらの頂点について，頂点セルルックアップテーブルは新しく生成されたセルを検索する．

4.5 面セルルックアップテーブルの更新

１回の操作で折られる面はすべて同一平面上にあり唯一の面グループに属するので，面セルルックアップテーブルの更新はそのグループのみに対して行なわれる．操作前の面の重なり順序と折り方の種類から操作後の新しい面の重なり順序を表すテーブルが決定される．

4.6 リスト更新の逆手続き (Undo)

折り手順を訂正したい時などに紙の状態の履歴情報を保持していれば，初めからではなく折り手順の途中からやり直すことができる．本システムではリストの現在の状態に，更新とは逆の手続きを施すことによりリストの過去の状態を再生する．各セルは何手順目に生成されたかを保持しているので，生成された順序の逆順にセルを消去することができる．面セル，辺セル及び頂点セルルックアップテーブル内のセルポインタが消去されるセルを指示している場合は，消去されるセルの親セルを指すように変更すればよい．例えば図6(b)で面セルF2が消去される際には，辺セルE2内の面セルポインタがF2からF0に変更される．

作成例

本システムはシリコングラフィックス社製 IRIS 4D/70 上で約3000ステップのＣ言語のプログラムにより実現されている．現在本システムにより飛行機，鶴，蝉，兜などの作成に成功しており，そのいくつかの例を図８に示す．


(a) KABUTO	(b) Cicada

(c) Plane	(d) Crane

(e) Yomiuri Press Jun 24, 1994

図８　作成例

5. むすび

本文では，折り紙に対する仮想物体操作を実現し，グラフィックス環境において実物感覚で操作が行なえるマンマシンインタフェイスの可能性を示した．折り紙を二分木リストの構造により簡潔に記述した結果，紙の状態変化に対するデータの更新をリアルタイムで高速に行うことができた．またマウスによる座標入力の曖昧な面を自動的に補正することにより，オペレータが意図する操作を確実に行うことができた．

本システムでは物体の操作点が1点であるため折り方にかなりの制約を与えることになった．将来的には操作点を複数にすることにより折り方のバリエーションを増やしたり，紙自体を弾性などの物理的性質を与えて記述することにより更に実物に近いものにすることなども考えている．

謝辞

日頃熱心に御指導、御討論頂く研究室の皆様に感謝します。

参考文献

館日章, 廣瀬通孝: バーチャル・テック・ラボ, 工業調査会, (1992).
Hiroo Iwata: Artificial Reality with Force-feedback: Development of Desktop Virtual Space with Compact Master Manipulator, Computer Graphics, 24(4), pp.165-170 (1990).
Colin Ware: Using hand position for virtual object placement, The Visual Computer, 6(5), pp.245-253, (1990).
Tinsley A. Galyean, Joho F. Hughes: Sculpting: An Interactive Volumetric Modeling Technique, Computer Graphics, 25(4), pp. 267-274, (1991).
島田哲夫, 多田幸生: 曲面ロケータによる三次元入力手法, 情報処理学会論文誌, 30(3), pp.302-310, (1989).
中村康浩, 吉村哲也: ３次元直接操作に於けるポインティングのためのビームカーソル手法, 電子情報通信学会春季全国大会, D-648, (1991).
福井幸男, 下条誠: 力覚をフィードバックする操作デバイスによる仮想形状のなぞり動作, 電子情報通信学会論文誌, 74DII(8), pp.1052-1059, (1991)
井野秀一, 泉隆, 高橋誠, 伊福部達: 感覚フィードバック型ハンドのための把持感覚に関する心理物理的研究, 電子情報通信学会論文誌, 75DII(11), pp.1909-1916, (1992)
安居院猛, 竹田昌弘, 中嶋正之: 条件付きキーフレームアニメーション, 情報処理学会CG研究会, 1-2, (1981).
内田忠, 伊藤英則: 折り紙過程の知識表現とその処理プログラムの作成, 情報処理学会論文誌, 32(12), pp.1566-1573, (1991).
小森章弘, 安田孝美, 横井茂樹, 鳥脇純一郎: 折り紙の会話型シミュレーションシステム, 情報処理学会グラフィックスとCAD, 50-9, (1991).