(57)【要約】【課題】近似の精度を維持しながら、チャートの数を削減することを目的として、メッシュの分割および可展形状への近似を行なう。【解決手段】本発明に係る多面体メッシュの可展化方法は、メッシュ分割処理と、可展化処理と、を備えている、メッシュ分割処理は、多面体メッシュを頂点周りの角度による可展制約をほぼ満たすような複数のチャートに分割する処理である。可展化処理は分割されたチャートが正確に可展制約をみたすようにメッシュを変形する処理である。本発明により、「折り目」、「切れ目」が許容されるチャートが得られる。【選択図】図３Ａ
2014219899.tif 000002
【特許請求の範囲】
【請求項１】
多面体メッシュから可展性の高い部分領域（以下、「チャート」という）を生成する方法であって、
頂点周りの角度による可展制約を用いて、あるチャートの外縁に位置する複数の境界頂点の各頂点を基準として拡大した複数の拡大チャート候補の可展性を算出し、当該複数の拡大チャート候補から最も可展性の高い候補を拡大チャートとして選択するチャート拡大ステップを繰り返すものであり、
チャートの拡大過程において、拡大チャートの基準となった境界頂点は内部頂点となり、拡大チャートの基準とされず拡大チャート内部に取り残された境界頂点を通る辺が切れ目として生成される、方法。
【請求項２】
頂点周りの角度による可展制約は、以下の評価関数によって計算され、
2014219899.tif 000020
チャートの可展性は、以下の評価関数によって計算される、
2014219899.tif 000021
請求項１に記載の方法。
ここで、
viはメッシュ上の頂点、
θi,kは頂点周りで隣り合う２辺のなす角、
miは頂点vi周りの角の総数、
VI(C)はチャートCの内部頂点集合を表す。
【請求項３】
拡大チャートの可展性が予め設定された閾値に達するまで、チャート拡大ステップが繰り返される、請求項２に記載の方法。
【請求項４】
生成されたチャートにおいて、可展性に与える影響が少ない切れ目を閉鎖する切れ目閉鎖ステップを備えている、請求項２、３いずれか１項に記載の方法。
【請求項５】
前記切れ目閉鎖ステップは、可展性に与える影響が少ない切れ目について、切れ目の先端部分から、切れ目を閉鎖して、次第に短くしていくものであり、切れ目の先端から数えてl番目の頂点vlまでを閉鎖する際の、切れ目の可展性は、以下の評価関数により計算される、請求項４に記載の方法。
2014219899.tif 000022
ここで、E(vi)は式(2)で定義された頂点viの可展性を表し、||ej||は辺ejの長さを表す。
【請求項６】
前記方法は、
頂点周りの角度による可展制約を用いて、多面体メッシュの全頂点から可展性の高い１つの頂点をシードとして選択するステップと、
シードとして選択された頂点の周りの複数の面を統合して初期チャートを形成するステップと、
を備え、
前記初期チャートから出発してチャート拡大ステップが繰り返される、請求項１〜５いずれか１項に記載の方法。
【請求項７】
多面体メッシュの全頂点から可展性の最も高い１つの頂点を第１シードとして選択し、当該第１シードに基づいて拡大を繰り返して第１チャートを作成するステップと、
第１チャートに含まれていない頂点から可展性の最も高い頂点を第２シードとして選択し、当該第２シードに基づいて拡大を繰り返して第２チャートを作成するステップと、
を備え、
いずれのチャートにも含まれていない頂点から可展性の最も高い頂点をシードとして選択し、当該シードに基づいて拡大を繰り返してチャートを作成するステップを、全ての頂点がいずれかのチャートに属するまで繰り返すことで、ｎ個のチャートを作成する、請求項６に記載の方法。
【請求項８】
前記ｎ個のチャートのシードとして選択されたｎ個の頂点の周りの複数の面を統合してｎ個の初期チャートを形成し、
前記ｎ個の初期チャートから出発して、全ての頂点がいずれかの拡大チャートに属するまで、チャートの大きさを均等に保ちつつチャート拡大ステップを順次繰り返すことで、前記ｎ個のシードに基づいてｎ個のチャートを作成する、請求項７に記載の方法。
【請求項９】
前記方法は、
可展性の高い複数のｎ個の頂点をシードとして選択するステップと、
シードとして選択されたｎ個の頂点の周りの複数の面を統合してｎ個の初期チャートを形成するステップと、
前記ｎ個の初期チャートから出発して、全ての頂点がいずれかの拡大チャートに属するまで、チャートの大きさを均等に保ちつつチャート均等拡大ステップを順次繰り返すことで、前記ｎ個のシードに基づいてｎ個のチャートを作成する、請求項１、２、４、５（請求項３に従属するものを除く）いずれか１項に記載の方法。
【請求項１０】
作成された前記ｎ個のチャートにおいて最も小さいチャートのシードを除いたｎ−１個のシードから出発してチャート均等拡大ステップを実行することで、ｎ−１個のチャートを作成する、請求項８、９いずれか１項に記載の方法。
【請求項１１】
作成されるチャートの数が予め設定された数に減少するまで、請求項１０のステップを繰り返し実行する、請求項１０に記載の方法。
【請求項１２】
多面体メッシュの持つ全ての頂点が生成されたチャートのいずれかに属する一方、どのチャートにも属さない面が、隣接するチャート同士の間に発生する場合には、前記面をいずれかのチャートに属させる、請求項７〜１１いずれか１項に記載の方法。
【請求項１３】
請求項７〜１２いずれか１項に記載の方法により生成された各チャートを可展化する多面体メッシュの可展化方法であって、
各チャートの全ての内部頂点が可展となるように、全てのチャートの持つ頂点座標の最適解を同時に算出し、
算出した座標値を各頂点の座標値とすることでチャートを可展化する、方法。
【請求項１４】
処理の対象となる多面体メッシュの全頂点の座標値を、
2014219899.tif 000023
とベクトルで表し（nvはメッシュの全頂点数で、ベクトルの次元は3nvとなる）、
生成された各チャートの内部頂点に対応して、以下の評価関数群F(V)を生成し（nIはメッシュ全体におけるチャートの内部頂点数）、
2014219899.tif 000024
2014219899.tif 000025
を満たすVを最適化計算により求めることで、多面体メッシュを構成する拡大チャートを可展化する、請求項１３に記載の方法。
【請求項１５】
多面体メッシュから可展性の高い部分領域（以下、「チャート」という）を生成するために、請求項１〜請求項１２いずれか１項に記載の方法をコンピュータに実行させるためのコンピュータプログラム。
【請求項１６】
多面体メッシュを可展化近似するために、請求項１３、１４いずれかに記載の方法をコンピュータに実行させるためのコンピュータプログラム。
【請求項１７】
多面体メッシュから可展性の高い部分領域（以下、「チャート」という）を生成する装置であって、
拡大チャート候補取得手段と、
拡大チャート候補の可展性算出手段と、
拡大チャート選択手段と
を備え、
前記拡大チャート候補取得手段は、あるチャートの外縁に位置する複数の境界頂点の各頂点を基準として当該チャートを拡大して複数の拡大チャート候補を取得し、
前記拡大チャート候補の可展性算出手段は、頂点周りの角度による可展制約を用いて、各拡大チャート候補の可展性を算出し、
前記拡大チャート選択手段は、前記複数の拡大チャート候補から最も可展性の高い候補を拡大チャートとして選択し、
前記拡大チャート候補取得手段、前記拡大チャート候補の可展性算出手段、前記拡大チャート選択手段によるチャート拡大処理を繰り返すものであり、
チャートの拡大過程において、拡大チャートの基準となった境界頂点は内部頂点となり、拡大チャートの基準とされず拡大チャート内部に取り残された境界頂点を通る辺が切れ目として生成される、装置。
【請求項１８】
頂点周りの角度による可展制約は、以下の評価関数によって計算され、
2014219899.tif 000026
チャートの可展性は、以下の評価関数によって計算される、
2014219899.tif 000027
請求項１７に記載の装置。
ここで、
viはメッシュ上の頂点、
θi,kは頂点周りで隣り合う２辺のなす角、
miは頂点vi周りの角の総数、
VI(C)はチャートCの内部頂点集合を表す。
【請求項１９】
前記装置は、チャート拡大処理終了判定手段を備えており、
前記チャート拡大処理終了判定手段は、拡大チャートの可展性と予め設定された閾値とを比較し、拡大チャートの可展性が予め設定された閾値に達した時にチャート拡大処理を終了させる、請求項１８に記載の装置。
【請求項２０】
前記装置は、生成されたチャートにおいて、可展性に与える影響が少ない切れ目を閉鎖する切れ目閉鎖手段を備えている、請求項１８、１９いずれか１項に記載の装置。
【請求項２１】
前記切れ目閉鎖手段は、可展性に与える影響が少ない切れ目について、切れ目の先端部分から、切れ目を閉鎖して、次第に短くしていくものであり、切れ目の先端から数えてl番目の頂点vlまでを閉鎖する際の、切れ目の可展性は、以下の評価関数により計算される、請求項２０に記載の装置。
2014219899.tif 000028
ここで、E(vi)は式(2)で定義された頂点viの可展性を表し、||ej||は辺ejの長さを表す。
【請求項２２】
前記装置は、
頂点周りの角度による可展制約を用いて、多面体メッシュの全頂点から可展性の高い１つの頂点をシードとして選択するシード選択手段と、
シードとして選択された頂点の周りの複数の面を統合して初期チャートを形成する初期チャート形成手段と、
を備え、
前記初期チャートから出発して、前記拡大チャート候補取得手段、前記拡大チャート候補の可展性算出手段、前記拡大チャート選択手段によるチャート拡大処理が繰り返される、請求項１７〜２１いずれか１項に記載の装置。
【請求項２３】
前記シード選択手段は、いずれのチャートにも含まれていない頂点（チャートが作成されていない場合には、多面体メッシュの全頂点）から可展性の最も高い頂点をシードとして選択するものであり、
前記シード選択手段によるシードの選択と、前記拡大チャート候補取得手段、前記拡大チャート候補の可展性算出手段、前記拡大チャート選択手段によるチャート拡大処理と、を全ての頂点がいずれかのチャートに属するまで繰り返すことで、ｎ個のチャートが作成される、請求項２２に記載の装置。
【請求項２４】
前記初期チャート形成手段は、前記ｎ個のチャートのシードとして選択されたｎ個の頂点の周りの複数の面を統合してｎ個の初期チャートを形成し、
前記ｎ個の初期チャートから出発して、全ての頂点がいずれかの拡大チャートに属するまで、前記拡大チャート候補取得手段、前記拡大チャート候補の可展性算出手段、前記拡大チャート選択手段により、チャートの大きさを均等に保ちつつチャート均等拡大処理を順次繰り返すことで、前記ｎ個のシードに基づいてｎ個のチャートが作成される、請求項２３に記載の装置。
【請求項２５】
前記装置は、
可展性の高い複数のｎ個の頂点をシードとして選択するシード選択手段と、
シードとして選択されたｎ個の頂点の周りの複数の面を統合してｎ個の初期チャートを形成する初期チャート形成手段と、
前記ｎ個の初期チャートから出発して、全ての頂点がいずれかの拡大チャートに属するまで、前記拡大チャート候補取得手段、前記拡大チャート候補の可展性算出手段、前記拡大チャート選択手段により、チャートの大きさを均等に保ちつつチャート均等拡大処理を順次繰り返すことで、前記ｎ個のシードに基づいてｎ個のチャートが作成される、請求項１７、１８、２０、２１（請求項１９に従属するものを除く）いずれか１項に記載の装置。
【請求項２６】
作成された前記ｎ個のチャートにおいて最も小さいチャートのシードを除いたｎ−１個のシードから出発してチャート均等拡大処理を実行することで、ｎ−１個のチャートを作成する、請求項２４、２５いずれか１項に記載の装置。
【請求項２７】
作成されるチャートの数が予め設定された数に減少するまで、請求項２５の処理を繰り返し実行する、請求項２６に記載の装置。
【請求項２８】
前記装置は、穴埋め処理手段を備えており、
前記穴埋め処理手段は、多面体メッシュの持つ全ての頂点が生成されたチャートのいずれかに属する一方、どのチャートにも属さない面が、隣接するチャート同士の間に発生する場合には、前記面をいずれかのチャートに属させる、請求項２３〜２７いずれか１項に記載の装置。
【請求項２９】
請求項２３〜２８いずれか１項に記載の装置により生成された各チャートを可展化する多面体メッシュの可展化装置であって、
各チャートの全ての内部頂点が可展となるように、全てのチャートの持つ頂点座標の最適解を同時に算出する数値計算手段と、
算出した座標値を各頂点の座標値とすることでチャートを可展化する手段と、
を備えた可展化装置。
【請求項３０】
前記数値計算手段は、
処理の対象となる多面体メッシュの全頂点の座標値を、
2014219899.tif 000029
とベクトルで表し（nvはメッシュの全頂点数で、ベクトルの次元は3nvとなる）、
生成された各チャートの内部頂点に対応して、以下の評価関数群F(V)を生成し（nIはメッシュ全体におけるチャートの内部頂点数）、
2014219899.tif 000030
2014219899.tif 000031
を満たすVを最適化計算により求めることで、多面体メッシュを構成する拡大チャートを可展化する、請求項２９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多面体メッシュの可展形状近似に関する。
【背景技術】
【０００２】
コンピュータグラフィクス技術の発達により、様々な場面において3次元の立体物をコンピュータ上で表現・処理する機会が増えた。多面体によるメッシュモデル(以下、メッシュ）はその表現手法のひとつであり、立体形状を非常に多くの小さな平面によって表現したものである。滑らかな曲面を平面の集合によって再現していることが、メッシュの大きな特徴である。
【０００３】
一方、コンピュータ上で表現された立体形状を物理的に具現化する有効な方法のひとつとして、紙を組み合わせて形状を構成するペーパークラフトがある。実際、ペーパークラフトは娯楽としての用途の他、紙を金属板などのシート材料におきかえることで、建築や機械部品の製造にも応用可能である。しかし、メッシュで表現された様々な形状を、ペーパークラフトで実現するためには問題もある。それは、紙によって表現できる形状が限られるということである。これは、伸縮しない素材という紙の性質に由来している。この問題を解決するために、ペーパークラフトに関して多くの研究がなされている。
【０００４】
紙によって立体形状を再現するためには、対象となる立体形状を一平面に展開した展開図が必要である。既存の研究ではこの展開図を得るために様々なアプローチがあるが、一般的に多く採られる手法は、メッシュを領域で分割し、それぞれの分割した領域(「チャートと呼ばれることが多い」)を可展形状として近似する、というものである。ペーパークラフトでは、オリジナルの形状をできる限り高い精度で近似しながら、組み立てやすいことが求められる。これまで「組み立てやすさ」として主に、チャート数が少ないことと、チャートが単純な形状であること、が指標とされてきた。ここでいう単純な形状とは、チャートが円形に近い形状や、チャートの境界部分に凹凸が少ない形といったものを指す。
【０００５】
より詳細に説明すると、一般に立体形状を紙によって再現したいとき、その形状の可展性が非常に重要である。可展性とは、対象の形状を伸縮させることなく平面に展開できる性質のことを示す。本研究では、可展性を持つ形状のことを可展形状と呼ぶ。平面、柱面、錐面、接線曲面などの可展面は、可展形状の一種と考えられる。
【０００６】
紙によって立体形状を構築する手法では、対象の立体形状をいくつかのチャートにわけ、それぞれを平面に展開した展開図を作成し、それらに折り目を加えたり切り貼りしたりして立体形状全体を再構成する、のが一般的である。そのため、紙を用いて組み立てる立体形状は、立体形状そのものが単一の可展形状であるか、もしくは可展性を持つ形状の集合である必要がある。多くの立体形状は複数の様々な平面や曲面の集合であるが、元の立体形状自体が可展であるとか、可展である領域のみから構成されるという場合は非常に限られている。そのため、対象の立体形状を可展形状の集合となるように近似することが必要となる。
【０００７】
一方で、メッシュは膨大な数の平面（一般的には三角形）から構成されている。メッシュの各面は平面であり、可展面ではあるが、一般には面の数があまりに多いため、メッシュを元の形状のまま展開することは、組み立ての観点からは非現実的である。そこで、Hoppe（非特許文献１やGarlandら（非特許文献２）のメッシュ簡略化手法を用いることが考えられる。これはメッシュ形状が持つ特徴を維持したまま、メッシュを構成する三角形面を互いに結合し、その面数を減らすものである。しかし、新たに作成されるメッシュは、一般に角張った粗い形をしており、元のメッシュの形状が持つ滑らかさは失われてしまう。そこで、柱面や錐面などの可展面を用いてメッシュの分割や近似を行なう手法が、Juliusら（非特許文献３）、Shatzら（非特許文献４）、Fadyら（非特許文献５）などによって提案された。
【０００８】
Juliusらが提案したD-Charts法は、擬可展面によってメッシュを分割する手法である。この手法は、メッシュを可展面に近い擬可展面による領域で分割する。しかし、D-Charts法によって分割されたチャートは正確な可展形状ではないため、平面への展開は不可能である。そこで、Shatzらは対象とするメッシュを正確な可展形状の集合で表現できるように、メッシュの分割に加えてチャートを平面、錐面、柱面の3種類の可展面で近似する手法を提案した。このとき作成されたチャートは元のメッシュ形状とは異なるため、隣接するチャート間の境界線も元のメッシュから大きく逸れてしまう可能性がある。そこで、作成したチャート同士の境界を再計算をして、チャート同士の接続を保証している。また、この手法では、各チャートは上記3種類の可展面のいずれかひとつに対応するため、一般的にチャートは小さく分割されるとともに大きさが均一になりにくい。
【０００９】
Mitaniら（非特許文献６）は、連続した三角形によって構成される帯状のメッシュであるstripを用いることで、元のメッシュが持つ滑らかさを維持した形状近似を実現した。各stripは内部に頂点を持たないため展開性が保証される。一方で、strip同士は三角形の底辺を介して接続され、形状全体を近似する。さらにstripの一部に切り込みを入れることで、より柔軟に元のメッシュ形状を近似することも可能となっている。しかしながら、stripという特定の曲面を用いることから、表現能力に制約があり、近似の精度が低くなる傾向にある。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Hoppe H., “Progressive Meshes”, SIGGRAPH 96  Conference Proceedings,ACM SIGGRAPH (1996),  pp. 99-108.
【非特許文献２】Garland M. and Heckbert P. S., “Surface simplification usingquadric error metrics”,  SIGGRAPH 97 Conference Proceedings, ACM SIGGRAPH(1997), pp. 209-216.
【非特許文献３】Julius D., Kraevoy V. and Sheffer A., “D-Charts: Quasi-Developable  MeshSegmentation”, Computer Graphics Forum, Vol. 24, No. 3  (2005),pp. 581-590.
【非特許文献４】ShatzI., Tal A. and Leifman G., “Papercraft models from meshes”,Visual  Computer, Vol. 22, No. 9 (2006), pp. 825-834.
【非特許文献５】MassarwiF., Gotsman C. and Elber G.,  “Papercraft Models using GeneralizedCylinders”,  Proceedings of the 15th Pacific Conference on Computer Graphicsand Applications (2007), pp. 148-157.
【非特許文献６】MitaniJ. and Suzuki H., “Making papercraft toys from meshes using strip-basedapproximate unfolding”, ACM Transactions on Graphics, Vol. 23, No. 3 (2004),pp. 259-263.
【非特許文献７】TachiT., “Freeform Variations of Origami”,  Journal for Geometry andGraphics, Vol. 14, No. 2 (2010), pp. 203-215.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明では近似の精度を維持しながら、チャートの数を削減することを目的として、メッシュの分割および可展形状への近似を行なう。この際、チャートに、いわゆる「折り目」や「切れ目」を含めることで、個々のチャートで表現できる形状の自由度を上げる。そのために本発明では、従来の研究でよく利用されていた柱面や錐面などの可展面による制約の代わりに、頂点周りの角度による可展制約を用いる。
【課題を解決するための手段】
【００１２】
本発明が採用した技術手段は、多面体メッシュから可展性の高い部分領域（以下、「チャート」という）を生成する方法であって、
頂点周りの角度による可展制約を用いて、あるチャートの外縁に位置する複数の境界頂点の各頂点を基準として拡大した複数の拡大チャート候補の可展性を算出し、当該複数の拡大チャート候補から最も可展性の高い候補を拡大チャートとして選択するチャート拡大ステップを繰り返すものであり、
チャートの拡大過程において、拡大チャートの基準となった境界頂点は内部頂点となり、拡大チャートの基準とされず拡大チャート内部に取り残された境界頂点を通る辺が切れ目として生成される、方法、である。
本発明では、頂点周りの角度による可展制約を用いてチャートを生成することで、折り目を許容するチャートが作成される。拡大チャートの基準とされず拡大チャート内部に取り残された境界頂点を通る辺は切れ目として生成され、切れ目上の境界頂点はチャート拡大ステップにおいて内部頂点（拡大チャートの基準頂点とならない）とはならない。
本発明の１つの特徴は、チャートの拡大を頂点単位で行う点にある。
１つの態様では、拡大チャートの可展性が予め設定された閾値に達するまで、チャート拡大ステップが繰り返される。
１つの態様では、チャート拡大ステップは、可展性の高い複数の頂点（シード）の周囲の初期チャートから同時に均等拡大される。この場合、チャート拡大ステップは、全ての頂点がいずれかのチャートに属するまで繰り返される。１つの態様では、可展性の高い複数の頂点（シード）は、後述するメッシュの初期分割ステップによって取得される。
【００１３】
多面体メッシュを構成する多数の多角形は、典型的には三角形である。本発明は、四角形以上の多角形を排除するものではないが、最初に与えられたデータが四角形以上の面を含んでおり、それらの四角形が正確に平面上に載っているデータであれば、後述する可展化計算において、面上の頂点が同一平面上に載るという制約を加える必要がある。
【００１４】
１つの態様では、頂点周りの角度による可展制約は、以下の評価関数によって計算され、
2014219899.tif 000003
チャートの可展性は、以下の評価関数によって計算される。
2014219899.tif 000004
ここで、
viはメッシュ上の頂点、
θi,kは頂点周りで隣り合う２辺のなす角、
miは頂点vi周りの角の総数、
VI(C)はチャートCの内部頂点集合を表す。
【００１５】
１つの態様では、生成されたチャートにおいて、可展性に与える影響が少ない切れ目を閉鎖する切れ目閉鎖ステップを備えている。
１つの態様では、前記切れ目閉鎖ステップは、可展性に与える影響が少ない切れ目について、切れ目の先端部分から、切れ目を閉鎖して、次第に短くしていくものであり、切れ目の先端から数えてl番目の頂点vlまでを閉鎖する際の、切れ目の可展性は、以下の評価関数により計算される。
2014219899.tif 000005
ここで、E(vi)は式(2)で定義された頂点viの可展性を表し、||ej||は辺ejの長さを表す。
【００１６】
１つの態様では、前記方法は、
頂点周りの角度による可展制約を用いて、多面体メッシュの全頂点から可展性の高い１つの頂点をシードとして選択するステップと、
シードとして選択された頂点の周りの複数の面を統合して初期チャートを形成するステップと、
を備え、
前記初期チャートから出発してチャート拡大ステップが繰り返される。
１つの態様では、多面体メッシュの全頂点から可展性の最も高い１つの頂点を第１シードとして選択し、当該第１シードに基づいて拡大を繰り返して第１チャートを作成するステップと、
第１チャートに含まれていない頂点から可展性の最も高い頂点を第２シードとして選択し、当該第２シードに基づいて拡大を繰り返して第２チャートを作成するステップと、
を備え、
いずれのチャートにも含まれていない頂点から可展性の最も高い頂点をシードとして選択し、当該シードに基づいて拡大を繰り返してチャートを作成するステップを、全ての頂点がいずれかのチャートに属するまで繰り返すことで、ｎ個のチャートを作成する。
【００１７】
１つの態様では、前記ｎ個のチャートのシードとして選択されたｎ個の頂点の周りの複数の面を統合してｎ個の初期チャートを形成し、
前記ｎ個の初期チャートから出発して、全ての頂点がいずれかの拡大チャートに属するまで、チャートの大きさを均等に保ちつつチャート拡大ステップを順次繰り返すことで、前記ｎ個のシードに基づいてｎ個のチャートを作成する。
より具体的には、前記ｎ個のチャートのシードとして選択されたｎ個の頂点の周りの複数の面を統合してｎ個の初期チャートを形成するステップと、
各初期チャート毎に、当該初期チャートの各境界頂点について、周囲の複数の面を当該初期チャートに結合して複数の拡大チャート候補を取得し、頂点周りの角度による可展制約を用いて、各拡大チャート候補の可展性を算出し、最も可展性の高い拡大チャート候補を拡大チャートとして選択することで、ｎ個の拡大チャートを得るステップと、
各拡大チャート毎に、当該拡大チャートの各境界頂点について、周囲の複数の面を当該拡大チャートに結合して複数の拡大チャート候補を取得し、頂点周りの角度による可展制約を用いて、各拡大チャート候補の可展性を算出し、最も可展性の高い拡大チャート候補を新たな拡大チャートとして選択することで、ｎ個の新たな拡大チャートを得るステップと、を備え、
全ての頂点がいずれかの拡大チャートに属するまで、チャートの拡大を繰り返すことで、前記ｎ個のシードに基づいてｎ個のチャートを作成する。
１つの態様では、前記方法は、
可展性の高い複数のｎ個の頂点をシードとして選択するステップと、
シードとして選択されたｎ個の頂点の周りの複数の面を統合してｎ個の初期チャートを形成するステップと、
前記ｎ個の初期チャートから出発して、全ての頂点がいずれかの拡大チャートに属するまで、チャートの大きさを均等に保ちつつチャート均等拡大ステップを順次繰り返すことで、前記ｎ個のシードに基づいてｎ個のチャートを作成する。
【００１８】
１つの態様では、作成された前記ｎ個のチャートにおいて最も小さいチャートのシードを除いたｎ−１個のシードから出発して上記ステップを実行することで、ｎ−１個のチャートを作成する。
１つの態様では、作成されるチャートの数が予め設定された数に減少するまで、上記ステップを繰り返し実行する。
【００１９】
１つの態様では、多面体メッシュの持つ全ての頂点が生成されたチャートのいずれかに属する一方、どのチャートにも属さない面が、隣接するチャート同士の間に発生する場合には、前記面をいずれかのチャートに属させる。
【００２０】
本発明は、上記方法により生成された各チャートを可展化する多面体メッシュの可展化方法であって、
各チャートの全ての内部頂点が可展となるように、全てのチャートの持つ頂点座標の最適解を同時に算出し、
算出した座標値を各頂点の座標値とすることでチャートを可展化する、方法、である。
１つの態様では、処理の対象となる多面体メッシュの全頂点の座標値を、
2014219899.tif 000006
とベクトルで表し（nvはメッシュの全頂点数で、ベクトルの次元は3nvとなる）、
生成された各チャートの内部頂点に対応して、以下の評価関数群F(V)を生成し（nIはメッシュ全体におけるチャートの内部頂点数）、
2014219899.tif 000007
2014219899.tif 000008
を満たすVを最適化計算により求めることで、多面体メッシュを構成する拡大チャートを可展化する。
【００２１】
本実施形態は、（Ａ）多面体メッシュモデルを複数の部分領域（チャート）に分割する分割ステップと、（Ｂ）メッシュ分割ステップによって得られた各チャートを可展化する可展化ステップ、とからなる。メッシュ分割ステップ（Ａ）は、チャートの淘汰ステップ（Ａ−１）を備えてもよく、この場合、ステップ（Ａ−１）の後に可展化ステップ（Ｂ）が実行され、（Ａ）→（Ａ−１）→（Ｂ）となる。メッシュ分割ステップ（Ａ）の後に、切れ目の閉鎖ステップ（Ｃ）を備えてもよい。この場合、（Ａ）→（Ｃ）→（Ｂ）となる。切れ目を効率良く閉鎖するためには、可展化ステップ（Ｂ）の後に、切れ目の閉鎖ステップ（Ｃ）を実行することが有利である。この場合、切れ目閉鎖ステップ（Ｃ）の後に再可展化ステップ（Ｂ´）が実行され、（Ａ）→（Ｂ）→（Ｃ）→（Ｂ´）となる。なお、（Ａ）メッシュ分割ステップにおいて、どのチャートにも属さない面が、隣接するチャート同士の間に発生する場合には、前記面をいずれかのチャートに属させる穴埋め処理（Ｄ）が分割ステップ（Ａ）または淘汰ステップ(Ａ-１)の最後に実行される。
【００２２】
本発明は、さらに、多面体メッシュにおけるチャートの生成方法及び多面体メッシュの可展化方法をコンピュータに実行させるためのコンピュータプログラム、あるいは、当該コンピュータプログラムが記録された記録媒体としても定義される。さらに、本発明は、特許請求の範囲に記載の通り、多面体メッシュから可展性の高い部分領域を生成する装置、当該装置を用いた多面体メッシュの可展化装置としても規定されるものである。本発明に係る生成方法及び可展化方法は、１つあるいは複数のコンピュータによって実行され、本発明に係る生成装置及び可展化装置は、１つあるいは複数のコンピュータから構成される。１つの態様では、コンピュータは、各種計算を行う演算処理部、多面体メッシュデータや計算結果等の各種データを格納する記憶部、元の多面体メッシュ及び各ステップにおける処理後の多面体メッシュ、得られたチャートの展開図等を表示する表示部、コンピュータを操作するための入力部、計算結果等のデータを出力する出力部、を備えている。
【発明の効果】
【００２３】
本発明では、近似の質を維持しながら要素数の削減を目指して、折り目と切れ目を含むような分割と可展形状化によって形状を近似する手法を提案する。折り目と切れ目を積極的に用いることで、少ない分割数ながら高い精度で与えられた形状を近似することが可能となる。
【図面の簡単な説明】
【００２４】
【図１】頂点における可展性の評価を説明する図である。
【図２】ハーフエッジ構造を説明する図である。
【図３】本実施形態の手法の流れを示す図であり、（ａ）は初期分割、（ｂ）はチャートの淘汰、（ｃ）は可展化、（ｄ）は切れ目の閉鎖、（ｅ）は再可展化、（ｆ）はチャートの展開を示している。
【図３Ａ】本実施形態に係るメッシュ分割及びチャートの可展化を示すフローチャートである。
【図３Ｂ】図３Ａにおけるチャートの淘汰ステップを示すフローチャートである。
【図４】チャートを構成する頂点を説明する図である。
【図５】チャートの拡大を説明する図である。（ａ）は元のチャート、（ｂ）（ｃ）（ｄ）は境界頂点のうちの１つを選択して、その周りの三角形をチャートに結合したチャートであり、これらが拡大チャートの候補となる。
【図５Ａ】図５（ａ）と類似の図である。
【図５Ｂ】図５（ｂ）（ｃ）（ｄ）と類似の図である。
【図６】チャートの拡大に伴う切れ目の発生と成長の過程を示す図である。
【図７】図６と類似の図であり、切れ目の生成を説明する図である。
【図８】初期分割の結果を示す図である。
【図９】穴埋めパターンを示す図である。
【図１０】初期分割後の穴埋め処理の結果を示す図である。
【図１１】均等拡大と穴埋め処理の結果を示す図である。
【図１２】式5.1、5.4で用いられる要素を示す図であり、三角形v0, v1, v2において、頂点v0の角度をθ、法線ベクトルをn とする。
【図１３】可展化の結果を示す図である（チャート数２０）。
【図１４】切れ目における可展性の評価を説明する図である。
【図１５】切れ目の閉鎖結果を示す図である。
【図１６】再可展化の結果を示す図である。
【図１７】チャートの展開例を示す。チャートの一部に自己交差が生じている（図の○印の部分）。
【図１８】チャートの分割結果を示す。図１７のチャートに対して分割を施したものである。
【図１９】本実施形態に係るペーパークラフトの作成例を示す。
【図２０】本実施形態により作成したStanford Bunnyの展開図の例（図３（ｆ）を拡大したもの）である。
【図２１】チャート数を変化させた結果を示す図である。（ａ）はチャート数５、（ｂ）はチャート数１０、（ｃ）はチャート数２０、をそれぞれ与えた結果である。
【図２２】FanDiskにチャート分割と可展化処理を施した結果を示す。チャート数は５である。
【発明を実施するための形態】
【００２５】
[Ａ]本実施形態の概要
一般にペーパークラフトは平面に展開可能な複数のチャートを組み立てることで作成される。その際に、最終的な形状の近似の質とその組み立てやすさを共存させることが重要である。この組み立てやすさは、チャートの性質に依存する。既存研究では、組み立てやすさの指標として、チャート数の少なさやチャート形状の単純さを用いている。本実施形態では、近似の精度を保ちつつチャートの数を減らすことを最大の目標とする。チャートの数が減ることで、チャート同士の接続における辺の組み合わせも少なくなり、組み立てやすさも改善されるものと考えられる。
【００２６】
ここで、紙を用いた造形の一例として折り紙を考える。折り紙では、折り目を加えることで一枚の紙で表現できる形状の自由度を上げ、複雑な立体形状を表現している。本実施形態では、チャートに折り目を取り込むとともに、切れ目も積極的に利用した分割法を目指す。折り目を入れることで複数種類の可展面をひとつの連続したチャートにまとめることが可能となる。また切れ目によって近似精度を向上させられるとともに、切れ目部分の接続関係が自明であるため比較的組み立てやすくなることが予想される。つまり、折り目と切れ目を取り入れることで、既存手法に比べてチャート数を大幅に削減できるうえに、組み立てやすさについても改善が期待できる。しかし、既存手法のように柱面や錐面などの可展面を用いた分割手法では、チャートの形状に、折り目や切れ目を取り込むことは難しい。
【００２７】
そこで、可展形状が持つ制約として、Tachi（非特許文献７）の研究などでも用いられている角度による可展制約を利用する。この制約は、図1のようにメッシュ上の頂点viについて、その周りで隣り合う2辺のなす角をθi,kとした場合に、可展となる頂点が次式を満たすというものである。
2014219899.tif 000009
ここでmiは頂点vi周りの角の総数を表す。この角度による可展制約は折り目を許容するため、チャートに折り目を取り込むことが可能となる。また、頂点周りの局所的な制約であるため、チャート内の切れ目も問題にならない。さらに、この角度による可展制約はチャートの可展化にも利用可能である。特に、角度による制約に基づいた可展化は、位相を維持したまま頂点の座標のみを変化させることで実現できる。そのため、Shatzらの手法で問題となっていたチャート同士の接続も自然に達成できる。
【００２８】
本実施形態に係る手法の特徴をまとめると、以下のようになる。
(1)折り目を含んだチャートを作成する。
(2)切れ目を含んだチャートを作成する。
(3) メッシュの位相を変えずに、チャート同士の接続を保持しながら可展化処理を行なう。
(4)チャートの個数をユーザが指定できるものとし、チャートの大きさをなるべく均等にする。
(1)〜(3)は既存手法（既存手法は、可展面でない曲面を、いかに柱面や錐面などの可展面で表現するかを主眼としており、１つのチャートについて、「折り目」、「切れ目」といった概念はない）にはない新たな試みであり、近似の精度を保ちながらチャート数の大幅な削減を可能とする。また、(4)によってユーザの希望するチャート数に抑えることも可能とする。
【００２９】
(1)については、角度による可展制約を用いることで、チャート形状に自然に折り目が含まれる。本実施形態に係るチャートは折り目を許容する点において、従来の手法の曲面から形成されるチャートと異なる。本実施形態において、Shatzらの手法において異なるチャートに分割されていた領域は、折りを含むことで同じチャートに結合できる可能性がある。
【００３０】
(2)については、メッシュをチャートに分割する際に、可展化しにくい頂点をチャートの境界として残すことで実現される。残された境界頂点が境界のままチャートの内部に残されることで、自然に切れ目が生じるとともに成長していく。切れ目によって、チャートの可展性を高く維持したまま、チャートをより大きく拡大することが可能となる。チャートへの分割の後、可展性への影響が少ない切れ目に対しては、切れ目を閉じる処理を適用する。この閉鎖処理によって切れ目が必要以上に残らないようにする。切れ目の閉鎖処理には、角度による可展制約に加えて、切れ目の長さにも依存した評価を用いる。
【００３１】
(3)については、メッシュ全体の頂点に対して同時に可展化処理を施すことで実現する。この際、メッシュの位相は変えずに頂点位置のみを変えるため、チャートの境界を再評価する必要はなくなる。本実施形態では、チャート単位ではなく、メッシュ全体の頂点に対して可展化する処理を施す点において従来手法と異なる。Shatzらの手法では個々のチャートに対し、独立に可展面への近似を行なっていた。そのため、チャートを可展面に近似したあとでチャートの境界部分を操作し、互いに接続するようにチャートの形状を変形させる処理が必要であった。本手法では、頂点位置のみを変更するため、チャート同士の接続を保持しながらチャートを可展化する。そのため、Shatz らの手法にあるような、チャートの境界接続のための処理が不要である。
【００３２】
(4)については、拡大しにくいチャートを淘汰することによってチャートの個数を調整する。この際、チャートの大きさが均等になるようにメッシュを分割する。拡大しにくいチャートは、メッシュ上の三角形の中でチャートとして拡大しにくいシードを見つけることにより実現する。そのようなシードはチャートの起点から外し、拡大しやすいシードを用いてチャートを作成することで、チャートの個数を減らしていくことができる。これは、扱うメッシュの形状やユーザが求めるチャートの数のために、必要に応じて加えることのできる任意処理である。
【００３３】
ここで、多面体メッシュを記述するデータファイル形式の一例について説明する。多面体メッシュは、多面体メッシュを構成する頂点データの個数、各頂点（例えば、頂点番号で規定される）の座標（x座標, y座標, z座標）、多面体メッシュを構成する面データの個数、各面データ（例えば、面を形成する複数の頂点の頂点番号で規定される）、から特定される。頂点番号は、頂点座標で記述された順序を表し、典型的には、最初から0番、1番…と番号づけられる。例えば、原点 (0,0,0) と、(1, 0, 0)、(0, 1, 0)、(0, 0, 1)の4点からなる四面体（三角錐）のデータは、次のようになる。
4（頂点数=4）
0.0  0.0  0.0  （頂点0）
1.0  0.0  0.0  （頂点1）
0.0  1.0  0.0  （頂点2）
0.0  0.0  1.0  （頂点3）
4（面数=4）
0  2  1  （面0）
0  3  2  （面1）
0  1  3  （面2）
1  2  3  （面3 ）
【００３４】
本実施形態で用いた多面体メッシュのデータ構造について説明する。多面体メッシュモデルは、平面同士の連結によって成り立っている。連結部に存在する頂点(vertex)、稜線(edge)、面(face)の間の隣接関係が重要となる。例えば、１つの面は頂点と稜線によって囲まれており、面の頂点と稜線を辿ると、最終的に元の頂点に戻ってくる。また、１つの頂点からは放射状に稜線が延びており、隣り合った稜線の間に面が１つ存在している。稜線は２つの頂点を端点として持ち、２枚の面に隣接していることになる。ここで、多面体メッシュ（ポリゴンモデル）の表現に用いられるデータ構造として、広く用いられているものとして、面を基準としたデータ構造、稜線を基準としたデータ構造、ハーフエッジ構造、が知られている（Computer Graphics Gems JP 2012 -コンピュータグラフィックス技術の最前線  株式会社ボーンデジタル）。
【００３５】
本実施形態では、上記位相的な隣接関係をハーフエッジ(halfrdge)構造で表現する。ハーフエッジには向きがあり、ハーフエッジ間にはいくつかの隣接関係が存在する。例えば、稜線によって対となるハーフエッジ同士の間にはedgemate、ひとつの面を反時計回りに巡る関係はccwFace (counter-clockwise
face)、一つの頂点周りで反時計回りに巡る関係をccwVertex (counter-clockwize vertex)とする。すなわち、多面体メッシュをハーフエッジ構造によって構成することにより、任意のハーフエッジを指定すれば、そこから巡回し周囲の面や頂点を取得することができる（Computer Graphics Gems JP 2012 -コンピュータグラフィックス技術の最前線）。表１に本実施形態で用いたハーフエッジ構造の要素を示す。図２にハーフエッジ構造を示す。
【表１】
2014219899.tif 000010
【００３６】
本実施形態における各処理を実行するための計算において、幾何学的には、各面の法線ベクトル（面に垂直なベクトル）が利用され、面を構成する頂点の並びが重要になる。頂点の並び方や、面と面の隣接具合などを表す情報を位相情報と呼ぶ。法線ベクトルや位相情報などは、多面体メッシュを構成するファイルを読み込んだ際に演算手段によって計算することで取得され、取得されたデータは、記憶手段に記憶される。
【００３７】
[Ｂ]アルゴリズム
本実施形態に係る手法は大きく2つの処理から構成されている。ひとつはメッシュ分割であり、もうひとつは可展化である。メッシュ分割処理は、多面体メッシュを可展制約をほぼ満たすような複数のチャートに分割する処理である。一方、可展化処理は分割されたチャートが正確に可展制約をみたすようにメッシュ（チャート）を変形する処理である。提案手法の流れを図3、図3Ａに示す。
【００３８】
まず、メッシュの初期分割を行なう(図3(a))。角度の可展制約に基づいて、最も可展性の高い頂点を起点として、可能な限りチャートを拡大する。残された頂点に同様の操作を繰り返し適用することで、メッシュは複数のチャートに分割される。この処理の詳細については、[Ｂ−１]項で説明する。
【００３９】
次に、チャートの淘汰を行なう(図3(b))。初期分割の段階では評価関数の閾値によって、各チャートの拡大停止判定を行なう。このため作成されるチャート数は結果的に定まり、与えられた数に納めることは難しい。そこで、まずチャートを多めに作成した上で、ユーザが指定したチャート数になるまでチャートを減らしていく。その際に各チャートができるだけ均等な大きさになるようにする。この処理の詳細は[Ｂ−２]項に述べる。
【００４０】
メッシュの分割が終了したところで、チャートの可展化を行なう(図3(c)）。ここでは、メッシュ全体を可展形状の集合に変形する。そのために、チャートの境界上にある頂点(以下、境界頂点)を除いた、チャート内部にある頂点(以下、内部頂点)が可展制約を満たすようにメッシュ全体の頂点座標を調整する。境界頂点には可展性の制約を与えず、内部頂点と一緒に移動することで、チャート間の接続を維持しつつメッシュ全体を可展化する。この処理の詳細については、[Ｂ−３]項で説明する。なお、図4において、境界頂点を●、内部頂点を■で示す。
【００４１】
可展化されたチャートに、切れ目の閉鎖処理を施す(図3(d))。メッシュ分割時に作成された切れ目のうち、可展性にあまり影響を与えないものを選んで閉じる。切れ目の効果を適切に評価することで、本当に必要な切れ目のみを残すことが可能となる。切れ目の閉鎖処理については、[Ｂ−４]項で詳述する。
【００４２】
切れ目の閉鎖処理によって、可展性を失ったメッシュを再度可展化し(図3(e))、最後に各チャートを平面に展開することで、最終的な展開図を得る(図3(f))。それぞれの処理について、[Ｂ−５]項と[Ｂ−６]項で詳しく説明する。
【００４３】
[Ｂ−１]初期分割
メッシュの初期分割においては、各チャートの起点となる頂点(以下、シード)を選択し、そのシードから始めて、可展制約を満たす範囲でチャートを拡大していく。シードには、いずれのチャートにも含まれていない頂点の中で、可展性の最も高いものを選択する。頂点の可展性は、式(1)の角度による可展制約に基づいて、次の式(2)を用いる。
2014219899.tif 000011
【００４４】
シードを選択した後に、シードとして選択された頂点の周りの三角形面をすべて結合して、初期チャートを作成する(図5(a))。
【００４５】
ここで、チャートの可展性を以下の評価関数によって定義する。
2014219899.tif 000012
ここで、VI(C)はチャートCの内部頂点集合を表す。チャートの拡大は、図5(b)〜(d)のようにチャートの境界頂点のひとつについて、その周囲の三角形をチャートに結合したチャートを拡大チャートの候補とする。このとき当該の境界頂点は拡大チャート候補の内部頂点となる。全拡大チャートの候補の可展性を式(3)によって算出し、最も値が小さいものを新たなチャートとする。チャートの可展性が一定の閾値に達するまで、拡大を繰り返すことで、初期分割でのチャートが一つ作成される。
【００４６】
チャートの拡大の過程では、チャートの内部に取り残された境界頂点はそれ以降の拡大の対象から外すものとする。これによって、一旦、切れ目ができると、その切れ目は保存されて、自然に切れ目が成長していく。図6に切れ目の発生と成長の過程の例を示す。初期分割では、チャートの作成を、シードとなりうる頂点がなくなるまで繰り返す。このため、メッシュの持つすべての頂点は、いずれかのチャートに属すことになるが、どのチャートにも属さない三角形がチャートの境界付近に発生する場合がある。これらの三角形は、隣接するチャートの中で、境界が最も滑らかになるように結合する。図3(a)は初期分割の例である。
【００４７】
このように、初期分割ステップでは、メッシュを複数のチャートに分割するためのチャートの拡大を行なう。メッシュを構成する頂点のうちの１つであるシードを起点として、そのシードから可展制約を満たすようにチャートを拡大していく。初期分割ステップについて、さらに詳細に説明する。
【００４８】
［ステップ１］シードの決定
多面体メッシュの持つすべての頂点について、その頂点周りの可展性を調べる。メッシュの持つ全頂点についてその頂点周りの可展性を、式(2)を用いて定量化する。このとき式(2)によって算出される値のうち、一番小さい値を算出した頂点がメッシュの中で最も可展性の高い頂点である。すなわち、この頂点を起点(シード) としてチャートを広げることで、より可展性の高いチャートが得られるものと考える。
【００４９】
［ステップ２］チャートの拡大・切れ目の形成
可展性の最も高い頂点、すなわち平面により近い頂点を起点とし、ある閾値に到達するまでチャートの拡大を行なう。このとき角度による可展制約に基づいた評価関数を用い、閾値の範囲内でチャートを拡大する。
【００５０】
先ず初期頂点の頂点周りの三角形をすべて結合することで、初期チャートのCinitialを作成する(図5A)。このチャートの初期状態から段階的にチャートを拡大していくこととなる。チャートを拡大する際は、式(3)で示した評価関数を用いる。チャートの拡大方法を、図5Bに示す。チャートはある境界頂点を内部頂点とすべく、その頂点周りの三角形をすべてチャートに結合することで広げていく。ここで、内部頂点とする頂点はチャートCの境界頂点vj∈VB(C)の中から評価関数の増加量が最小となるものを選ぶ。図5B(b)はチャートC(図5B(a))の境界頂点のひとつv0を中心としてチャートを広げて作られるチャートCnew0を表している。
【００５１】
同様にして、v1からはチャートCnew1が(図5B (c))、vjからはチャートCnew,jが(図5B (d)) 作られている。すべてのチャートの候補について式(3)で示した評価関数の値を算出し、新しいチャートCnewとする。このようにしてチャートCは可展性がなるべく高くなるようにチャートCnewへとその領域を拡大する。チャートの拡大は、そのチャートの持つ評価関数Cost(C)の値が、与えられた閾値を超えるまで繰り返し行なわれる。
【００５２】
チャートCの境界頂点集合VB(C)は、チャートを拡大しチャートCnewを作成するための候補となる頂点である。しかし実際に拡大の対象となるためには一定の条件を満たす必要がある。その条件とは、境界の外側で隣接三角形がすべていかなるチャートにも属していないことである。なぜならば、拡大によって境界頂点は内部頂点となるためである。
【００５３】
チャートの拡大過程において、平面化しにくい頂点は切れ目としてチャートの境界部分に残すことにより、チャートに自然な切れ目を作成する(切れ目の作成)。チャート作成の際に平面化しにくい境界頂点を内部頂点へと取り込まず、チャート内に取り残された境界頂点を通る辺をそのままチャートの境界の一部として残すことで自然な流れでチャートに切れ目を作成することができる。具体的にチャートに切れ目ができる過程を以下に述べる。
【００５４】
図7は、チャートに切れ目が加わる過程を示したものである。図7(a)の状態のチャートCから、チャートを拡大することを考える。チャートCの持つ境界頂点のうちのひとつであるvjが、チャートCを次に拡大するための頂点として選ばれたとする。このとき頂点vj周りの三角形をチャートCと結合させ、新しくできたチャートCnewが図7(b)である。１回のチャートの更新で境界頂点から内部頂点へと変化する頂点は、チャートの拡大の基準となった頂点のみであり、この場合vjが内部頂点となる。このとき、viはチャートCnewの内部に入ってしまうが、内部頂点ではなく境界頂点として残される。チャート内部に取り残された境界頂点を通る縁は切れ目として扱われる。
【００５５】
［ステップ３］新たなシードの決定
閾値によってチャートの拡大が止まったところで、残っている頂点の中で一番可展性の高い頂点を起点とし、同様の処理を行なう。あるシードから初期チャートを作成し、チャートCost(C)が閾値に到達するまでチャートの拡大を行なう。チャートの拡大が終了すると、メッシュの持つすべての頂点のうち、それまでに作成されたチャートの頂点に属さない頂点に対して、再び頂点周りの可展性を式(2)を用いて調べる。その中で最も小さな値を持つ頂点を新たなシードとし、これをもとに再びチャートの作成を行なう。
【００５６】
［ステップ４］ステップ２、３の繰り返し
ステップ２、ステップ３を、チャートに属さない頂点がなくなるまで繰り返し行なう。
シードの決定とチャートの拡大を繰り返し行なうことで、複数のチャートが作成される。メッシュ全体をたどり、もうこれ以上新たなチャートが作成できなくなったところ、すなわちすべての頂点がいずれかのチャートにも属すようになったところで全体の処理を終了する。ここまでの処理の結果を図8に示す。
【００５７】
［ステップ５］穴埋め処理
ステップ４までの処理において、もしいずれのチャートにも属していない三角形が存在するような場合は、当該三角形を周囲のいずれかのチャートに属させる処理を行なう。チャートの拡大は、シードとなりうる頂点がなくなるまで行なわれるため、メッシュの持つ頂点はすべていずれかのチャートに属すことになるが、どのチャートにも属さない三角形が発生する場合がある(図8に、黒塗りの三角形として例示する)。これは、隣接するチャート同士の間に三角形が孤立してしまう場合に生じる。この三角形を穴とよぶことにする。穴となっている各三角形をチャートに属させることで、穴埋め処理を行なう。穴埋め梅処理の際には、穴埋めによって新たに更新されるチャートの境界部分がより滑らかになるように考慮する。
【００５８】
穴のでき方には図9の7パターンが存在し、それぞれに対して処置を行なう必要がある。図9は穴埋めのパターンを示し、Ciは穴に隣接するチャートを表している。図9 (a)は穴が1つのチャートC0に囲まれている場合である。穴となっている三角形のうち一番長い辺が切れ目として残るようにC0に穴を結合させる。図9 (b)は穴が2つのチャートC0，C1に囲まれている場合である。穴となっている三角形と共有している辺が多い方のチャートと結合させる。この場合、C0と結合する。図9
(c)は穴が3つのチャートC0，C1，C2に囲まれている場合である。穴となっている三角形のうち一番長い辺を共有しているチャートと結合させる。この場合、C1と結合する。図9
(d)は一辺が別の穴と隣接し、残りの辺がチャートC0と共有している場合である。C0 と共有している二辺のうち、長い方の辺でチャートと結合させる。図9 (e)は一辺が別の穴と隣接し、残りの辺がチャートC0，C1とそれぞれ共有している場合である。チャートと共有している二辺のうち長い辺を共有しているチャートと結合させる。この場合、C1と結合する。図9(f)は二辺がそれぞれ別の穴と隣接し、一辺がチャートC0と共有している場合である。辺を共有しているチャートC0と結合させる。図9 (g)はすべての辺がそれぞれ別の穴と隣接している場合である。このとき、隣接する穴の処理が先になされるように、処理を後回しにする。図8の結果に以上の穴埋め処理を行なった結果が図10である。
【００５９】
この結果、多面体メッシュはn個のチャートに分割される。角度による可展制約を用いたことにより、折り目を含む形でチャートが作成される。
【００６０】
[Ｂ−２]チャートの淘汰（図３Ｂ参照）
[Ｂ−１]で得られるチャートは、平面性の高い領域を優先してチャートを拡大するため、最初に作成されるチャートは大きく、最後に作成されるチャートは小さくなりやすい。また、与えられたメッシュの形状や拡大停止の判定に用いる閾値によって、結果的にチャートの数が決まる。そこで初期分割のチャートは直接用いず、このプロセスで得られたシードのみを利用し、ユーザによって指定された個数にまでチャートを減らすことを考える。
【００６１】
[Ｂ−１]で得られたn個のチャートのシード群からn個の初期チャートCi（i=1,2,...,n）を作成する。式(3)による評価値が最も小さいチャート、すなわちn個のチャートの中で最も可展性の高いものを１回だけ拡大する。この操作を繰り返すことで、すべてのチャートをできるだけ均等に拡大していく。メッシュの持つ頂点すべてがいずれかのチャートに属したところで、チャートの拡大を終了する。
【００６２】
得られたチャートのうち、最も小さな（チャートを構成する三角形の数が少ない）チャートのシードをシード群から取り除く。これにより、シード、すなわちチャートの数をひとつ減らせられる。この操作を繰り返すことによって、ユーザが指定したチャート数になるまでシードを減らしていく。図3(b)は、このようにしてチャートを淘汰した結果である。図3(a)の初期分割の結果に対して、チャート数が大幅に減るとともに、チャートの大きさもほぼ均等になっている。
【００６３】
チャートの淘汰についてさらに詳細に説明する。[Ｂ−１]で得られたチャートは、角度による可展制約にのみ依存してチャートを拡大して作成したものである。そのため、対象のメッシュの形状やチャート拡大の際に用いる閾値によってチャートの数が変化する。また、平面性の高い領域を探してチャートの拡大を行なっているため、最初に作成されるチャートが大きく、最後に作成されるチャートは大きさが小さくなりやすい。対象となる形状をペーパークラフトによって実現する際に、チャートの大きさが均一である方が組み立てやすい場合がある。また、より少ない個数のチャートからメッシュを構成できれば、それだけ組立てが容易となる。そこで、[Ｂ−１]で作成したn個のチャートをもとにチャートを再び作成し直すことで、チャートの個数を減らすとともに、チャートの大きさを均等にすることを試みる。チャートは、[Ｂ−１]で用いた評価関数を再び用いて、次の流れによって作成する。
【００６４】
［ステップ１］シード群の初期化
[Ｂ−１]で得られたn個のチャートについて、それぞれの起点となった頂点であるn個のシードをシード群とする。[Ｂ−１]で得られたn 個のチャートそれぞれの起点となった頂点すなわちシードからなるシード群を得る。シードは、その付近の領域の中でもっとも可展性の高い頂点であると言える。すなわち、その点を起点としてチャートを拡大することで、より広い領域にチャートが拡大しうる。
【００６５】
[ステップ２]均等拡大
シード群のすべてのシードそれぞれを起点としてチャートの拡大を行なう。チャートは評価関数による値が最も小さいものを選び、そのチャートについてチャートの拡大を行なう。この操作を繰り返し行なうことで、チャートの大きさに偏りが生じることをさける。シード群の各シードを起点として、初期チャートのCiを作成する。これは[Ｂ−１]に記載した流れと同様に作成する。ここで作成されたn個の初期チャートCi,i=0,1,…,n-1をできるだけ均等に拡大することを試みる。チャートCiの中から、現在の評価関数Cost(Ci)の値が最も小さいチャートCi＊を得る。Ci＊について、チャートの拡大を１回だけ行ない、Ci＊の評価関数Cost(Ci＊)の値も更新する。
【００６６】
このようにして、ｎ個のチャートを同時に順次拡大していく。これにより、チャートの大きさに偏りが生じることを防ぐ。メッシュの持つ全ての頂点がいずれかのチャートに属した時点で、チャートの拡大を終了する。この後、必要に応じて、穴埋め処理を行なうことで、メッシュの持つすべての三角形がいずれかのチャートに属するようになる。図10の結果に対して、均等拡大を適応した例を図11に示す。均等拡大の結果、図10と比較して、チャート間の大きさのばらつきが少なくいることが分かる。
【００６７】
[ステップ３]シードの削減
作成されたn個のチャートのうち最も小さいもの、すなわち、最も含まれる三角形の個数が少ないチャートについて、その起点となったシードをシード群から外す。[Ｂ−１]に示したチャートの拡大の処理によって作成されるチャートの数は、メッシュの形状と閾値に依存する。すなわち、メッシュが可展性が低く、閾値が小さい場合には作成されるチャートの数は多くなる。ユーザの意図によって、チャート数を削減して、任意のチャート数を実現する。均等拡大によって作成された新しいチャートのうち、一番小さいチャートを選ぶ。ここでいう小さいとは、チャートを構成する三角形の数によって定義するものとする。この一番小さいチャートのシードをシード群から外し、新たにn−1個のシード群とする。このシード群を用いて、均等拡大でチャートの拡大を行なう。この操作を繰り返し行なうことでシードを削減し、最終的にユーザが指定したチャート数にすることができる。ステップ２、ステップ３を繰り返すことでチャートを減らしていき、最終的にユーザが指定するチャート数k個になったところで、チャート作成の処理を終了する。作成されたチャートはユーザの指定した個数の範囲で、角度の可展制約に基づいて、可展面に近くなるように分割されていることとなる。図21において、(a)はチャート数５、(b)はチャート数１０、(c)はチャート数２０、である。
【００６８】
[Ｂ−３]チャートの可展化
初期分割、あるいはチャートの淘汰によって作成されたチャートは、あくまで可展性がより高くなるようにメッシュを分割した部分領域にすぎず、正確な可展形状ではない。チャートを１つの平面に展開するためには、各チャートが正確に可展な形状とならなくてはいけない。そこで、各チャートが可展となるように、チャートの持つ頂点座標を数値計算によって求める。すなわち、すべての内部頂点が式(1)を満たすような頂点座標を求める。
まず、処理の対象となるメッシュの全頂点の座標値を
2014219899.tif 000013
とベクトルで表す。このときnvはメッシュの全頂点数で、ベクトルの次元は3nvとなる。チャートの内部頂点に対応して、以下の評価関数群F(V)を作る。
2014219899.tif 000014
ここで、nIはメッシュ全体におけるチャートの内部頂点数である。この評価関数群は、各内部頂点の頂点周りの角度和を2πから引いた値となっている。つまり、これは各頂点における可展性を表しているので、
2014219899.tif 000015
を満たすVを求めることで、メッシュを構成するチャートをすべて可展化できる。
【００６９】
本実施形態では、ニュートン・ラプソン法(Newton-Raphson
Method)および共役勾配法(Conjugate Gradient Method)を用いて、解Vを求める。具体的な算出法としては、Tachi（非特許文献７）の手法を用いることができ、必要に応じて非特許文献７の内容を参照することができる。与えられるチャートが充分に可展形状に近ければ、式(5)を解くことが可能であり、メッシュ全体を可展化できる。なお、このとき境界頂点には制約が与えられておらず、内部頂点に関する制約を満たすように自由に移動する。ただし、隣り合ったチャートは境界頂点を共有しているので、チャート同士の接続は維持される。図3(c)はチャートの可展化を施した結果の例を示したものである。この操作によって、メッシュの曲率が切れ目とチャート境界部分に集中する。
【００７０】
より詳細に説明すると、チャートの可展化の流れは次の通りである。
1. チャートの持つ頂点に対し最適化処理をおこない、チャートが可展となるための微小変形を求める。
2. 1．で求めた微小変形をチャートの頂点に施す。
これによりチャートの可展化を実現する。このとき、各チャート同士が境界となる頂点を共有しながらすべてのチャートの形状変形を計算する。これによりShatzらの手法において必要であった、チャートの境界部分の再計算が不要となる。
【００７１】
チャートが可展となるように、チャートの持つ頂点座標の最適解を数値計算によって算出する。算出した値を頂点の新しい座標値とすることで、チャートを可展化する。またこのとき、チャートごとに可展化するのではなくメッシュの持つ全頂点に対して同時に可展化を施す。これにより、チャート同士の接続関係が維持されたまま、各チャートが可展化できる。Shatzらの手法では、チャートを個別に可展に近似をするため、近似処理のあとにチャート同士の接続を保証すべく、チャートの形状を変形させるとともに境界を再計算する処理が必要であった。
【００７２】
チャートが可展であるかどうかは、チャートの内部頂点についての頂点周りの角度和と2πとの残差の総和によって決定され、総和が0であるとき、このチャートは可展になる。この残差を数値計算によって消去することができれば、このチャートを可展にできる。すなわち、残差を0とするような内部頂点の座標を求め、チャートの内部頂点の座標を更新することによって、チャートの可展化が実現できる。
【００７３】
式(5)を満たすメッシュ全体の頂点の座標V を新たに求め、これを新しい頂点座標とする。本手法では，ニュートン・ラプソン法(Newton-Raphson Method) および共役勾配法
(Conjugate Gradient Method)を用いて、解V を求める。ニュートン・ラプソン法にて用いる∂F/∂Vの算出方法について示す。∂F/∂Vは次式のように算出される。
2014219899.tif 000016
ここで、∂F/∂θは、式(4)と(5)より該当するθiに関して−１、そうでないθiに関しては0となる。したがって、∂θ/∂Ｖを求める必要がある。メッシュの三角形を図12のように表すと、式5.1の要素である[∂θ/∂Ｖ] の各要素は、対象となる頂点の位置関係によって次のように求められる（非特許文献７）。
2014219899.tif 000017
与えられるチャートが充分に可展形状に近ければ、式(5)を解くことで可展化が実現される。このとき境界頂点には制約を与えない。これにより、境界頂点はチャート同士の接続を維持しながら、座標値を変えることができる。以上の数値計算を適応させた結果を図13に示す。
【００７４】
[Ｂ−４]切れ目の閉鎖
ここまでの段階では、チャート拡大の際に発生した切れ目が多く存在する。切れ目があることで、チャートの可展性は高く維持されているものの、可展性に与える影響が少ない切れ目は削除することが望ましい。そこで、切れ目の先端部分から、切れ目を閉鎖して、次第に短くしていく。このときに用いる評価関数には、頂点周りの角度だけではなく切れ目の長さも考慮する。図14のように切れ目の先端から数えてl番目の頂点vlまでを閉鎖する際の、切れ目の可展性を表す評価関数を次のように定義する。
2014219899.tif 000018
ここで、E(vi)は式(2)で定義された頂点viの可展性を表し、||ej||は辺ejの長さを表す。すなわち式(6)は切れ目上の頂点が可展となるための残差と、閉鎖する切れ目の長さとを加味した評価関数となっている。
【００７５】
より具体的には、チャートを拡大する際に残したチャートの切れ目を閉じる処理を行うにあたり、切れ目をどこまで閉じるかを決定する閾値を与える。処理の流れは次の通りである。
1. チャート内の切れ目の先端に位置する頂点すべてについて可展性に関する評価関数の値を算出する。
2. 評価関数値の最も小さい頂点から辺一つ分だけ、切れ目を閉じる。この際、切れ目を閉じることで生じた評価値を新しい先端の頂点に加える。下記の漸化式を用いる。EA(vi)は累積残差である。
2014219899.tif 000019
3. 1と2を評価値が閾値を超えるまで繰り返し行なう。
この結果、切れ目を閉じたチャートが実現する。
【００７６】
[Ｂ−５]再可展化
切れ目の閉鎖処理では、切れ目の評価関数が閾値に達するまで切れ目を閉じていく。この結果、一度可展化したメッシュが、再び可展形状ではなくなる。そこで、切れ目の閉鎖処理の後に、もう一度、上記可展化処理を施して、メッシュを正確な可展形状の集合にする。図16に可展化の結果を示す。
【００７７】
[Ｂ−６]チャートの展開と分割
最後に、再可展化された各チャートを平面に展開する。チャートを展開した結果の例を図17に示す。折り目として角度が大きな（π/8以上の）ものには、赤ないし青の色をつけている。赤線は山折り、青線は谷折りに対応している。折り目の角度や向きは、チャートを構成する各三角形の法線ベクトルから計算することができる。なお、図面においてカラー画像を用いることができないため、グレースケールで表示されている点に留意されたい。この展開図は、図3(e)に示したStanford Bunnyの前足部分にある赤茶色のチャートに対応するものである。
【００７８】
平面に展開した際に、チャート内で自己交差が生じる可能性がある。このように自己交差するチャートについては、自己交差を解消するように複数のチャートに分割する。図17のチャートを分割した結果を図18に示す。ここでの分割は、ユーザの手作業で行なったが、チャートの分割を自動で行なえれば、ユーザに対する負荷を軽減できる。また、自己交差がより少なくなるように、メッシュ分割自体を制御してもよい。本実施形態では、チャートが自己交差を含む場合には、自己交差の解消によって、最終的にユーザが指定した値よりもチャート数が多くなりうる。メッシュ分割の段階で自己交差を考慮すれば、ユーザが指定したチャート数に近い数での分割が実現できる。
【００７９】
[Ｃ]結果
本実施形態に係る手法を実際のメッシュデータ（Stanford Bunny）に適用した結果を、図3に沿ってまとめる。まず初期分割によって、57のチャートに分割された(図3(a))。この時、拡大終了の判定に用いた評価関数（式(2)）の閾値は1.0であった。この初期分割の結果にチャート淘汰を適用することで、チャート数を15に削減した(図3(b))。その後、可展化(図3(c))、切れ目の閉鎖(図3(d))、再可展化(図3(e))を施した。切れ目の閉鎖処理では、式(6)の切れ目に関する評価関数の閾値として1.0を与えた。展開した各チャートのうち、自己交差が生じているものについて、手作業でチャートを分割し、最終的に図3(f)ならびに図20に示す27のチャートを得た。これはShatzらの手法によるチャート数35よりも少ない個数になっている。提案手法により作成した展開図を組み立てたペーパークラフトの例を図19に示す。
【００８０】
本実施形態に係る手法の特徴のひとつとして、ユーザがチャート数を指定できる点が挙げられる。Stanford Bunnyのデータでチャート数を変化させた結果の例を図21に示す。チャート数を減らした場合、相対的に切れ目を増やすことで近似を維持しようとしている。しかし、チャート数が少ないと、可展化を施す際にメッシュ全体の整合性を維持することが難しくなるため、最終的な近似精度が少しずつ低下していることが見てとれる。また、１つのチャートが大きくなることで、展開したときに自己交差を生じる可能性も高くなるため、必ずしも最終的なチャート数を減らせるわけでないことには注意が必要である。
【００８１】
別のメッシュデータの例として、Fan Diskに対して、チャートの分割と可展化を施した結果を図22に示す。機械部品などの形状は、平面や円筒面などで構成されることが多く、折り目を有効に利用することで、チャート数を大幅に減らすことが可能となる。この例の場合には、チャート数は5に抑えられている。
【００８２】
本実施形態では、ペーパークラフトの作りやすさという観点で最も重要と考えられるチャート数の削減を最大の目的として、メッシュの分割および可展化手法について考察した。本実施形態では、角度による可展制約を利用することで、
(1)チャート内に折り目を含むことを許容する;
(2)チャート内に自然に切れ目が入るようにする;
(3)メッシュの位相を変えずに、チャート同士の接続を保持しながら可展化する；
(4)チャートの個数はユーザが任意に指定することが可能であるとともに、結果のチャートの大きさが均等になるようにする；
を実現した。折り目によって個々のチャートで表現できる形状の自由度は向上し、切れ目によって既存の研究では複数に分割されるような領域をより少数のチャートで近似できるようになった。その結果、既存手法と比べると、より少ないチャート数で可展形状化することが可能となった。可展化の処理においても、角度による可展制約を用いて、各チャートの境界頂点を共有しながらメッシュ全体の接続性を維持しつつ、メッシュ全体を可展化する頂点座標の算出法を提案した。
【産業上の利用可能性】
【００８３】
本発明は、高速かつ安定して実行することができ、十分に実用化に供することができる。主な用途として考えられるペーパークラフトは趣味だけでなく、試作にも適しているほか、金属板などのシート材料に適用することで、建築や機械部品などの製造にも利用され得る。
【図１】
2014219899.tif 000032
【図２】
2014219899.tif 000033
【図３Ａ】
2014219899.tif 000034
【図３Ｂ】
2014219899.tif 000035
【図１２】
2014219899.tif 000036
【図１４】
2014219899.tif 000037
【図３】
2014219899.tif 000038
【図４】
2014219899.tif 000039
【図５】
2014219899.tif 000040
【図５Ａ】
2014219899.tif 000041
【図５Ｂ】
2014219899.tif 000042
【図６】
2014219899.tif 000043
【図７】
2014219899.tif 000044
【図８】
2014219899.tif 000045
【図９】
2014219899.tif 000046
【図１０】
2014219899.tif 000047
【図１１】
2014219899.tif 000048
【図１３】
2014219899.tif 000049
【図１５】
2014219899.tif 000050
【図１６】
2014219899.tif 000051
【図１７】
2014219899.tif 000052
【図１８】
2014219899.tif 000053
【図１９】
2014219899.tif 000054
【図２０】
2014219899.tif 000055
【図２１】
2014219899.tif 000056
【図２２】
2014219899.tif 000057