WISS2011

インタラクティブなビーズデザインと制作支援
Interactive Beadwork Design and Construction

五十嵐 悠紀五十嵐 健夫

三谷 純∗

概要. 我々は 3 次元ビーズ作品のデザインおよび制作のためのインタラクティブなシステムを提案する．
ユーザはまずビーズ作品の構造を表すメッシュモデルを制作する．それぞれのメッシュの辺はビーズ作品のビーズに対応している．システムはユーザのモデリング中に常に近傍のビーズとの物理制約を考慮して辺の長さを調整する．システムは次にメッシュモデルを適切なワイヤーつきのビーズモデルへと変換する．
ワイヤー経路の計算のために我々はメッシュの face stripiﬁcation を利用したアルゴリズムを提案する．シ
ステムは手動でビーズ作品を制作するための 1 ステップごとの制作手順ガイドを提示する．我々は本シス
テムを用いていくつかのビーズ作品を制作し，ユーザテストを行うことで初心者でもオリジナルなビーズ
作品をデザインできることを確認した．

1

はじめに

ビーズ作品はビーズをワイヤーでつなげたアートである．世界的に知られているビーズ作品は 2 次
元であるが，日本や中国においては 3 次元のビーズ
作品も一般的である．しかし，できあがりの形状はビーズとワイヤーの複雑な 3 次元インタラクション
で決定されるため，手動でデザインをするのは非常に難しい．また，ビーズ作品を作るためのワイヤー
通しも手動で考えるのは難しく，こういった事情か
らビーズデザインの専門家しかデザインできないのが現状である．我々は，既存のビーズ作品を観察し，ビーズ作品の構造はいくつかの幾何学的に興味深い構造をしていることを見つけた．このため，ビーズ
作品デザインをコンピュータで行うことは面白い技
術的なチャレンジであると言える．
本論文ではオリジナルなビーズ作品のデザインと制作を支援するインタラクティブなシステムを提案する．図 1 にシステムの概要を示す．ユーザはまず，
デザインモデルとよばれるポリゴンメッシュをデザインする．これはビーズ作品全体の構造を表している (図 1(a))．ビーズ作品のビーズはそれぞれデザイ
ンモデルの頂点ではなく，辺に対応している．シス
テムはデザインモデルに対して辺にビーズをのせて，ワイヤー経路を計算したビーズモデルへと変換する(図 1(c))．最後にユーザは実世界で手作業でビーズ作品を制作する．このための制作手順ガイドも制作
した (図 1(e, f)) ．

2

近年では最先端のグラフィックス技術を用いた実世界の物体のものづくりを支援するシステムがいく
つも提案されている．3 次元モデルを入力として実際の物体を出力するものでは，3 次元ポリノミノパ
ズル [9]，bas-relief [18]，ペーパークラフト [11, 15],
ポップアップカード [7], ぬいぐるみ [6]，あみぐる
み [5] などがある．スケッチ入力でインタラクティ
ブにデザインしていくものとしては，洋服 [1]，ぬいぐるみ [12] などがある. これらのシステムは伝統的な CAD システムとは異なり，非専門家がデザインを行うことに特化しており，紙や布といった物理的制約をモデリング過程に組み込んであることが特徴的である．本研究もこれらの既存研究とゴールは似ているが，結果のモデルが分離した物体の集合から構成されていること，それらがつながりによって定義されていることなどが大きく異なる点である．
実世界の 3 次元物体をコンピュータでデザインする際には物理制約が必要になる．例えば，紙でできたおもちゃであれば，可展面のパッチを用いて表される必要がある．この種の制限は freeform surfaceで作られた建築物などでしばしば論じられている[8, 14]．Pottmann らはこれを新しい研究領域 “architectural geometry” とよんでいる [13]．これらのトレンドに関連して，近年は元のモデルをいくつかの等しいポリゴンメッシュ形状で表す研究 [16, 2, 4]が提案されている．我々の提案システムは自動で変換するのではなく，インタラクティブに構築していく．

3∗

Copyright is held by the author(s).
Yuki Igarashi, 筑波大学 / 日本学術振興会, Takeo
Igarashi, 東京大学 / JST ERATO, Jun Mitani, 筑波
大学 / JST ERATO

関連研究

既存のビーズ作品および制作手法の観察

我々はまず，既存のビーズ作品を書籍やお店などで調査した．その結果，3 次元ビーズ作品は辺の長さがすべて等しい閉じた多様体をしていることがわ

WISS 2011

図 1. システムの概要．(a) ユーザはデザインモデルをデザインする．(b) システムはシミュレーションのための構造モデルを構築する．(c) システムはビーズを制作した際の予想形状 (ビーズモデル) を提示する．(d) システムはワイヤー経路を計算する．(e) システムが制作手順ガイドで 1 ステップごとの手順を提示する．(f ) ユーザが手作業で実際に制作したビーズ作品．

図 3. 基本形状．
図 2. 書籍 [10] のビーズ作品と作成図の例．

かった．ほとんどの面が 4〜6 本の辺で制作されており，三角形はめったにないことがわかった．非多様体の構造をした直線のビーズ列も時折用いられているが，これは主となる多様体にくっついていることが多い．ほとんどのビーズ作品は頭，胴体，腕，足などいくつかのパーツに分解されており，それぞれを 1 本のワイヤーで制作する．ワイヤー経路はそれ
ぞれのビーズを左側の面，右側の面を固定するために 2 回ずつ通る．ほとんどのビーズ作品は 100〜200
個のビーズで制作されており，ビーズの数が 200 個を超えるものは稀であった．
書籍では図 2[10] で示すようにビーズ作品の作成
図に 2 次元が用いられている．この作成図は長いワイヤーの中央にビーズを 1 つ入れるところから始まっており，それぞれのワイヤーの端をビーズに 1
つずつ通していく． 2 つのワイヤーの端は色でわかるように区別されており，一方は青，もう一方は赤である．制作図では，ポリゴンの面に対応するビー
ズを 1 つずつ赤と青のワイヤーを使って閉じて行く
ように制作する．

4
4.1

ユーザインタフェース
形状モデリング本システムはすべての辺の長さが等しいシンプルなポリゴンメッシュをデザインするために特別なモデリングインタフェースを用意した．ユーザはまずおおよその形状をあらかじめ用意された基本形状を組み合わせていくことで制作する．我々は図 3 のような正多面体および半正多面体を基本形状として用いた．すべての基本形状は等しい長さの辺から成る．
次にユーザは基本的なメッシュ編集操作 (面の押し出し，辺の挿入，辺の分割，辺の削除，頂点の併合) を組み合わせて編集していく．本システムでは
これらの編集操作を素早く行うために，図 4 のようなモードレスジェスチャーインタラクションを用いた．これらの操作 (線状突起の追加を除く) はオイ
ラーの多面体定理を満たしており，これらの操作によって編集されるメッシュの位相は常に球と同相であることを保証する．大局的な形状は基本形状の組み合わせで作り，局所的な形状をこれらの操作でデザインしていく．ビーズ作品ではしばしば閉じたポリゴンでは表現できないような部分が存在する．すべてのケースをサポートするのは難しいため，現在のシステムではビーズの列 (線状突起) でできた形
状のみサポートすることとした．これらの操作をした後，全体の形状の制約を保つためにシステムは物
理シミュレーションを行う．
面の押し出し： ユーザは面からスタートして線を描
くと面が法線方向に押し出される．システムは面を四角い strip を用いて持ち上げて生成する．
辺の分割と消去： 辺をクリックすると辺が分割される．辺からスタートして線を描くとその辺が消去される．辺の分割は選択した辺の中央に新しく頂点が追加され，2 つの辺に分割される．辺の消去は選択
した辺を消去して両側の面を 1 つの面に併合する．
辺の追加と頂点の併合： 頂点から違う頂点に向けて線を描くと頂点の併合か辺の追加が行われる．選択された 2 つの頂点が辺で接続していた場合，システ
ムはその辺を消去して 2 つの頂点を併合する．選択された 2 つの頂点が辺で接続はしていないが，同じ面をもつ場合，システムは新しい辺を作成して面を2 つに分割する．その他の場合には何も行わない．

Interactive Beadwork Design and Construction
Primitive addition
Edge insertion

Face extrusion(a)Vertex merger

(b)

(c)

(d)

(e)

(f)

図 6. 制作手順ガイドの例．(a) 初期状態．(b,c,f ) 青い
ワイヤーに新しいビーズを追加．(d) 赤いワイヤーに新しいビーズを追加．(e) 赤いワイヤーがすでに使われているビーズを通る．

Edge split

Chain addition
Edge deletion

図 4. メッシュ編集操作．

ビーズを追加することを示す (図 6(b),(c),(d),(f))．
その他はすでにビーズ作品に使われているビーズをワイヤーで通す (図 6(e))．

5アルゴリズム本システムは 3 つの異なるモデル表現から成る．
1 つ目はデザインモデルでこれはユーザがインタラ

図 5. ペイントモードのスクリーンショット．

線状突起の追加： ユーザが頂点から何もない部分へ
向けて線を描くとシステムはその頂点から辺を生成する．ループや枝のようなものは作れない．

4.2

見た目のデザインと制作ガイド

ユーザは図 5 のようなペイントインタフェースを用いて，それぞれのビーズの色や形状を変更できる．
実際のビーズ作品を制作するために，システムは
1 ステップごとに制作手順を見せる制作手順ガイドを提示する．従来の書籍などでは図 2 のような 2 次
元の作成図が使われているが，ユーザが実際のビーズと 2 次元上のビーズの対応関係を追っていかないといけないため，これは煩雑で難しい．我々が提案する制作手順ガイドはインタラクティブ 3 次元グラフィックスの長所を活かしたもので，これを使うことで制作手順を理解するのが初心者でも容易になる．
この制作手順ガイドは図 6 のようにワイヤー経路
を 3 次元グラフィックスを用いて 1 ステップずつ表示
していく．ユーザはそれぞれのステップを任意の方向から見ることができる．ユーザは “next” ボタンを押すと次のステップに進み，“prev” ボタンを押すことで 1 つ前のステップに戻る．制作手順ガイドは長い
ワイヤーの中央にビーズを通すところから始まる (図6(a))．片方のワイヤーの端が青でもう一方の端が赤である．システムは最初に必要なワイヤーの長さをユーザに提示する．青か赤のワイヤーに新しいビー
ズか既に使われているビーズを通すことを繰り返していく．ループはそのステップで使われている方のワイヤーを示している (図 6(b)-(f))．矢印は新しいクティブにモデリングしている最中に提示されているものである (図 1(a))．デザインモデルのそれぞれの辺はビーズに対応していて，それぞれの頂点はビーズの周りのワイヤーの 1 セットに対応している．2 つ目の表現は構造モデルでこれはより細かい構造をもつメッシュである (図 1(b))．このモデル
はビーズ間の物理的な制約を考慮したビーズ作品の形状を適切に表現する計算に使われる．構造モデル
は bead edge というそれぞれのビーズを表す辺と，
wire edge というそれぞれのビーズ間のワイヤーを表す辺から構成されている．3 つ目の表現はビーズ
モデルである．これは色や形状の情報を持ったビー
ズとワイヤー経路を計算し終わったワイヤーから構成される (図 1(c),(d))．

5.1構造モデルの構築

デザインモデルからビーズモデルへの変換は 2 ス
テップにわけられる．1 ステップ目は形状の計算である．システムはまず構造モデルとよばれる別のポ
リゴンメッシュへと変換する．これはデザインモデ
ル上の隣り合うビーズの部分の局所的なワイヤーも考慮したモデルであり，それぞれの n 価の頂点を n
本の wire edge と n 個の頂点に置き替えたもので
ある．

5.2

構造モデルの物理シミュレーション

システムは構造モデルの形状に物理シミュレー
ションを適応してビーズとワイヤーの物理的なイン
タラクションを考慮したビーズ作品の最終形状を得る．ユーザがインタラクティブにモデリングをしていく間，このシミュレーションは構造モデルに適用され，編集操作を終えるごとにデザインモデルの形
状は更新される．
我々はシミュレーションにおいて構造モデルの頂点に 3 つの力を与えている．1 つ目は辺が望む長さ

WISS 2011
stable bead
unstable bead(a) Design model

図 7. 制作している最中の安定したビーズと安定していないビーズの状態．

(b) Structure model(c) Wire graph(d) An Euler path of (c)34になるようなバネの力である．望む長さには beadedge にはビーズの長さ，wire edge には 0 を設定す
る．2 つ目の力は角のワイヤーがまっすぐになろうとする力である．システムは wire edge と bead edgeの接続角を計算し，それが可能な限りまっすぐになるように力を加える．3 つ目の力は隣り合うビーズが突き刺さらないように反作用の力を加える．

5.3

ワイヤー経路の計算

デザインモデルからビーズモデルへの変換の 2 ス
テップ目はワイヤー経路探索である (図 1(d))．ワイ
ヤー経路はビーズを効率的につなぐために適切に設定されなければならない．我々は確実にワイヤー経路を設定するために構造モデルからオイラーグラフを生成してワイヤー経路の計算を行った．しかし，
1 本のワイヤー経路では手動で制作するには困難な場合もある．そこで我々は，デザインモデルを複数の短い枝付きの face strip(帯状連結面) に分割して，それぞれの face strip において対応するワイヤーを通していくアルゴリズムを提案する．
提案するアルゴリズムは，(1) ビーズを固定するために必要最小限の回数を通ること．(2) ワイヤーの結び目の数を減らすために，ワイヤーの本数を最小限にすること．(3) 制作途中のビーズ作品においてできる限りビーズが安定した状態になること．を満たすようにワイヤー経路を設定する．ワイヤーによってビーズの位置が特定の位置に安定してしっかりと固定されたとき，これを stable の状態とよび，
これは図 7 のように面の全部のビーズを完成させたときである．unstable なビーズはユーザが手で押さえながら制作しなければいけないので，たくさん発
生してしまうと実際に手動で作っていくのには非常に難しくなる．
図 8(b) は局所的なワイヤーのつながりを示している．大局的なワイヤー経路はすべての wire edge
を 1 回とすべての bead edge を 2 回通るループを求めることである．これは bead edge を頂点として引き締めたグラフを作ったときに，ワイヤーはビーズに入ったら反対側から出るという制約付きのオイ
ラーグラフ (図 8(c)) となる．すべての bead edge
は 4 本の wire edge をもつので，このオイラーグラ
フはオイラー回路 (一筆書きの回路) が作れることを保証する．
しかし，図 8(d) のような任意のオイラー回路では手動でビーズ作品を制作している間に図 8(e) のよう

1

2

5
6
(e) Intermediatestatus of (d)(f) Typical wire path(g) Face strip
strucutre of (f)(h) Intermediatestatus of (f)図 8. ワイヤー経路アルゴリズムの詳細．

にたくさんの unstable なビーズが発生してしまうた
め不便である．我々は図 8(f),(g) のような face stripを用いることで unstable な状態のビーズを減らすことができることを発見した．face strip でカバーされたデザインモデルはワイヤー経路を 1 つずつの面を 1 つずつ完成させていけばよい．本手法では制作している間，既にたどり終わった面は常に stableになる (図 8(h))．全体を 1 つの strip では覆えない
モデルの場合，枝を作って strip に戻る (図 9)．この枝の部分は unstable なビーズになるので枝は 1 つまでと制限した．すべての面がカバーされるまで，独立した枝つきの face strip を繰り返し制作して行く．図 10 は stripiﬁcation の結果の例である．最初の face strip でほとんどの面を網羅できており，耳や腕などのパーツを他の strip でカバーする．
枝のない 1 つの face strip を計算することはデザ
インモデルの面を頂点に変えたグラフにおいてハミルトンパスを見つけることと一致するが，パスが存在することは保証されない．実用的に代わりになるものとしては，いくつかの枝付きの spanning treeを構築することであり，いくつかのヒューリスティッ
クな研究として，レンダリングのパフォーマンスを上げる研究 [3] や，データ圧縮 [17] などがある．我々も本研究のためにヒューリスティックな手法を用いた．提案手法では欲張り法にて最初の面から隣り合う面へと strip の最後を広げて行く．我々は候補となるいくつかの面の中から boundary length が最小となるような面を選択する．boundary length は
現在の face strip と残っている面の間のエッジの長さの和で表す．これにより制作途中のビーズ作品モ
デルをコンパクトに保ち，手動での制作を簡単にすることができる．デッドエンドに陥った際にはバックトラッキングを適用する．我々はこの欲張り法による探索を，すべての面から開始して，一番成功した結果を最終結果として得る．

6

結果

プロトタイプシステムはノート PC(1.2GHz CPU,
2GB RAM) を用いて Java で実装した．図 11 の上

Interactive Beadwork Design and Construction

際に手動でビーズ作品を制作した．すべてのビーズ
作品は半日ほどで最後まで作ることができた．
(a)

(b)

(c)

(d)

(e)

図 9. Stripification の過程．(a) 最初の strip．(b)枝を加えた状態．(c) 次の strip と枝．(d)stripのためのワイヤー経路．(e) 枝を考慮したワイヤー
経路に修正したもの．

(34, 0)(95, 4), (4, 0)(149, 3)

図 10. Stripification の結果．厚みのある茶色の線が主の strip で細い線が枝を表す．それぞれの数字
は strip を表す．(strip の面の数，枝の数)

2 段は本システムを用いてデザインされたビーズモ
デルである．デザインの時間はそれぞれ試したりどのようなものを作るか考える時間も合わせて 10-20分だった．制作手順ガイドを見ながら実際に手で作るのには 2-3 時間かかった．くまのビーズ作品だけは例外でお店で買ったビーズ作品を見ながらモデリングを行って約 90 分かかった．これを制作するのは 7 時間かかった．
我々は 5 人のユーザに本システムを使ってデザインしてもらい，フィードバックを得た．ユーザはコンピュータサイエンス専攻の大学生でビーズ制作の経験はない．5 分のチュートリアルのあと，5 分で自由に練習をしてもらった．すべての操作に関して
特に難しくなく学べた．その後，満足するまでそれぞれ好きなものをデザインしてもらった．図 12 に
実際のビーズ作品の写真もしくは CG での描画，それぞれの制作にかかった時間を示す．図 12 の最初の 3 つは，3 人の被験者が制作ガイドを見ながら実7

Limitation と今後の課題

本研究の目的は基本的なビーズ作品を作ることである．実際のビーズ作品はたくさんの技術を駆使して作られている．例えば，異なる大きさのビーズを組み合わせたり，シンプルな線状突起だけでなくさらに複雑な非多様体の構造をしていたりする．今後の課題としてはこれらの技術をサポートすることである．また，ほとんどのビーズ作品は左右対称であるため，モデルをインタラクティブにデザインしている間に自動的に左右対称なモデルを作れるようにすることも助けになるであろう．対称的な形状はき
れいなワイヤー経路を計算するためにも有益である．
複雑な物体をワイヤーつきのシンプルなプリミ
ティブの集まりで作り上げることは一般的なアイデ
アであり，この手法はビーズ作品の他にも物理オブジェクトをデザインするために使われている．例えば，同じユーザインタフェースとアルゴリズムで等しい長さのストローから構成されるストローアート
をデザインすることもできる．ストローモデルの場
合には，四角や五角形は安定しないという点が異なる部分である．我々は本技術を建築学などの形状を含めた，物理オブジェクトのデザインを支援するよう拡張したい．

参考文献[1] P. Decaudin, D. Julius, J. Wither, L. Boissieux,
A. Sheﬀer, and M.-P. Cani. Virtual Garments:
A Fully Geometric Approach for Clothing Design. Comput. Graph. Forum, pp. 625–634,
2006.
[2] M. Eigensatz, M. Kilian, A. Schiftner, N. J. Mitra, H. Pottmann, and M. Pauly. Paneling architectural freeform surfaces. ACM Trans. Graph.,
29:45:1–45:10, July 2010.

seal (20min)

図 11. デザインの例．上段：デザインモデル．中段：
ビーズモデル．下段：実際のビーズ作品．

cat (20min)

bear (25min)CGCG

airplane (25min)flower (25min)

図 12. 被験者によってデザインされたモデルとデザインに必要だった時間．

WISS 2011

[3] F. Evans, S. Skiena, and A. Varshney. Optimizing triangle strips for fast rendering. In Proceedings of the 7th conference on Visualization ’96,
VIS ’96, pp. 319–326, Los Alamitos, CA, USA,1996. IEEE Computer Society Press.
[4] C.-W. Fu, C.-F. Lai, Y. He, and D. CohenOr. K-set tilable surfaces. ACM Trans. Graph.,
29:44:1–44:6, July 2010.
[5] Y. Igarashi, T. Igarashi, and H. Suzuki. Knitting
a 3D Model. Comput. Graph. Forum, pp. 1737–
1743, 2008.
[6] D. Julius, V. Kraevoy, and A. Sheﬀer. D-Charts:
Quasi-DevelopableMesh Segmentation. Comput. Graph. Forum, pp. 581–590, 2005.
[7] X.-Y. Li, C.-H. Shen, S.-S. Huang, T. Ju, and S.M. Hu. Popup: automatic paper architecturesfrom 3D models. ACM Trans. Graph., 29:111:1–
111:9, July 2010.
[8] Y. Liu, H. Pottmann, J. Wallner, Y.-L. Yang,
and W. Wang. Geometric modeling with conicalmeshes and developable surfaces. ACM Trans.
Graph., 25:681–689, July 2006.
[9] K.-Y. Lo, C.-W. Fu, and H. Li. 3D polyomino
puzzle. ACM Trans. Graph., 28:157:1–157:8,
December 2009.
[10] Y. Maki. The Motifs of Puppy. Gakken (inJapanese), 2004.
[11] J. Mitani and H. Suzuki. Making papercraft toys
from meshes using strip-based approximate unfolding. ACM Trans. Graph., 23:259–263, August 2004.
[12] Y. Mori and T. Igarashi. Plushie: an interactive design system for plush toys. ACM Trans.
Graph., 26, July 2007.

未来ビジョン
従来から初心者のための手芸作品デザイン
を CG を用いて支援する研究を行ってきている [1] ．本研究ではデザイン過程を支援するほか，3 次元 CG を使った制作支援を行うこと
でこれまで 2 次元作成図ではあきらめていた
ユーザも 3 次元ビーズ制作に取り込むことに成功した．従来，手芸制作における作成図など
はすべて 2 次元であるが，将来的には 3 次元
CG を用いてインタラクティブに，任意の視点から確認しながら制作していけるコンテンツが普及し，老若男女，プロアマ問わず手芸・工芸などのものづくりを楽しむ世の中になると期待する．
また，今回は既存のビーズ作品の形状を観察することで幾何学的に面白い構造をしている
ことがわかった．ビーズだけでなく，これまでの専門家の知恵や試行錯誤の賜物である手芸・[13] H. Pottmann, Q. Huang, B. Deng, A. Schiftner,
M. Kilian, L. Guibas, and J. Wallner. Geodesic
patterns. ACM Trans. Graph., 29:43:1–43:10,
July 2010.
[14] A. Schiftner, M. Höbinger, J. Wallner, and
H. Pottmann. Packing circles and spheres on
surfaces. ACM Trans. Graph., 28:139:1–139:8,
December 2009.
[15] I. Shatz, A. Tal, and G. Leifman. Paper craftmodels from meshes. Vis. Comput., 22:825–834,
September 2006.
[16] M. Singh and S. Schaefer. Triangle surfaces
with discrete equivalence classes. ACM Trans.
Graph., 29:46:1–46:7, July 2010.
[17] G. Taubin and J. Rossignac. Geometric compression through topological surgery. ACM
Trans. Graph., 17:84–115, April 1998.
[18] T. Weyrich, J. Deng, C. Barnes, S. Rusinkiewicz,
and A. Finkelstein. Digital bas-relief from 3D
scenes. ACM Trans. Graph., 26, July 2007.

アピールチャート

工芸作品から，幾何学的・数学的に面白い知見が得られるのは非常に有意義なことであるた
め，他にも調査してみたい．
高校・大学等の授業では，数学や情報技術の基礎を習う際には教科書の上での知識として習い，試験勉強をして終われば忘れてしまう，ということも多かった．何のために勉強してい
るのか，いつ役に立つのかがわからない高校生等に対して，グラフ理論や幾何学を習う際に実際の手芸・工芸など身近なものに隠れている，使われていることも合わせて紹介できる
仕組み (事例を集めたワークショップの開催や参考書，書籍出版など) を作ることで物事の理解度，その後の興味の持ち方が変わっていくだ
ろうと期待する．

[1] 五十嵐 悠紀．
「コンピュータを用いた手芸
設計支援に関する研究」平成 21 年度 東京大学
大学院工学系研究科 博士学位論文．