３次元形状データ生成方法および３次元形状データ生成装置
【課題】工業製品の型紙のもととなるポリゴンモデルを生成することは難しい。
【解決手段】目標とする３次元立体の形状を近似した基準多面体が与えられたとき、基準多面体の表面形状を平滑化した３次元形状データを生成する装置を提供する。判別点生成部１２は、基準多面体の表面近傍に判別点を生成する。占有率算出部１４は、判別点を中心とする近傍球体内に近傍点をランダムに発生させ、近傍球体内の近傍点が基準多面体の内部に含まれる割合を示す占有率を算出する。有効判別点判定部２０は、占有率が判定閾値以上である場合に、判別点は目標とする３次元立体に含まれると判定する。３次元データ生成部２８は、目標とする３次元立体に含まれると判定された判別点を頂点とするポリゴンを生成し、ポリゴンモデルにより目標とする３次元立体を表した３次元形状データを生成する。
【解決手段】目標とする３次元立体の形状を近似した基準多面体が与えられたとき、基準多面体の表面形状を平滑化した３次元形状データを生成する装置を提供する。判別点生成部１２は、基準多面体の表面近傍に判別点を生成する。占有率算出部１４は、判別点を中心とする近傍球体内に近傍点をランダムに発生させ、近傍球体内の近傍点が基準多面体の内部に含まれる割合を示す占有率を算出する。有効判別点判定部２０は、占有率が判定閾値以上である場合に、判別点は目標とする３次元立体に含まれると判定する。３次元データ生成部２８は、目標とする３次元立体に含まれると判定された判別点を頂点とするポリゴンを生成し、ポリゴンモデルにより目標とする３次元立体を表した３次元形状データを生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、３次元立体の形状を表す３次元形状データを生成するための３次元形状データ生成方法および３次元形状生成装置に関する。
【背景技術】
【０００２】
服装、かばん、靴などの工業製品は、型紙を用いて製造される。服飾デザインの分野では、アパレルＣＡＤシステムが用いられている。アパレルＣＡＤシステムでは、型紙のテンプレートが用意され、ユーザはテンプレートを変形して所望のデザインの型紙を作成し、立体表示させて着衣状態をシミュレーションすることができる。
【０００３】
最近では、医療や介護の現場において、一般の既製服とは異なり、患者にとって着脱が容易な服装や、身体不自由の人を車椅子とベッドの間をリフティングにより移動させる際のフックを設けた専用の服など、特殊用途の服が求められている。患者の体型や身体の自由度、使用条件などに合わせて衣服の形状を新たにデザインする必要がある。
【０００４】
アパレルＣＡＤシステムでは、型紙のテンプレートが提供され、ユーザはテンプレートを自由に修正することで所望のデザインの型紙を作成する。顧客の体形が標準からかなりずれている場合や、介護用などの特殊な形状の衣服をデザインする場合、あるいはデザインが個性的で標準的なテンプレートが存在しない場合などには、用意されたテンプレートがほとんど意味をなさず、所望の型紙を作成するのは非常に難しくなる。また、かばんや靴などの型紙を作成する場合においても、流行に合わせて様々な形状をデザインする必要があり、用意されたテンプレートをベースとして型紙を生成する方法ではとても対応しきれない。
【０００５】
このような状況のもと、コンピュータグラフィックス（ＣＧ）技術により立体形状をモデリングし、ＣＧによる３次元モデルの形状を自動的に型紙に展開して製品の工業生産に利用することが求められている。
【０００６】
特許文献１には、衣服を求める顧客が自分の体型に合った衣服のデザイン画を描き、これを基にその衣服の型紙パターンをＣＡＤ／ＣＡＭ技術を応用して敏速・簡易に作成することのできる衣服の型紙パターンの自動作成方法とその自動作成システムが開示されている。
【特許文献１】特開２００１−２４９９５７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
３次元形状のモデリング手法としてポリゴンモデリングが一般的であり、ポリゴンモデルでは、ポリゴンの集まりであるポリゴンメッシュによって３次元形状を表現する。ポリゴンモデルは、ポリゴンを継ぎ合わせることで複雑な形状でも表現可能であるが、インタラクティブな処理が難しく、また滑らかな表面形状を忠実に表現するにはポリゴン数を増やす必要があり、データ量が増大する。ポリゴンメッシュは、形状状態の厳密さを追求するのではなく、形状を多面体として簡素化し表示を高速化するために用いられたり、解析用のモデルとして利用されている。
【０００８】
衣服やかばんなどの工業製品の３次元形状をＣＧによりモデリングする際、曲線や曲面の形状が非常に重要になる。任意の曲面を扱うために、自由曲面が用いられる。自由曲面は、ベジェ曲線、スプライン曲線、ＮＵＲＢＳ曲線を用いて面を定義するものであり、ポリゴンモデルに比べて、任意の滑らかな形状をより厳密に表現することができる。
【０００９】
しかしながら、自由曲面により３次元形状を定義する方法では、目的とする形状を想像しながら制御点などのパラメータを決める必要があり、自由度が高い反面、意図する形状を設計するのは非常に難しい。また、複雑な形状、たとえばフレアスカートのようなものをデザインする場合は、制御点への追従性が悪くなるため、形状が複雑になるほど制御点の数が増大するという問題がある。
【００１０】
細分化曲面（Subdivision Surface）と呼ばれる技法があり、車のデザインなどに使われている。細分化曲面法は、大まかにモデリングされたポリゴンメッシュを細分化して、滑らかで継ぎ目のない形状にする技術である。自由曲面に近い滑らかな形状を表現できるが、ポリゴンメッシュに比べてデータ量が増えるという問題がある。
【００１１】
また、単純な図形を組み合わせて立体形状を表現しておき、後で空間フィルタを用いて整形する方法もあるが、空間フィルタは周波数領域での特性を指定するものであるため、実際の形状にどのように反映されるかが分かりづらく、意図した形状をデザインすることは容易ではない。
【００１２】
本発明はこうした課題に鑑みてなされたものであり、その目的は、工業製品などの任意の形状を容易に設計することのできる３次元形状データ生成装置および３次元形状データ生成方法を提供することにある。
【課題を解決するための手段】
【００１３】
上記課題を解決するために、本発明のある態様の３次元形状データ生成方法は、目標とする３次元立体の形状を近似した基準多面体の表面形状を平滑化した３次元形状データを生成する方法であって、前記基準多面体の表面近傍に判別点を生成する判別点生成ステップと、前記判別点を中心とする所定の半径の近傍球体内に近傍点を乱数により発生させ、前記近傍球体内の前記近傍点が前記基準多面体の内部に含まれる割合を示す占有率を算出する占有率算出ステップと、前記占有率が所定の判定閾値以上である場合に、前記判別点は前記目標とする３次元立体に含まれると判定し、前記占有率が前記判定閾値より小さい場合に、前記判別点は前記目標とする３次元立体に含まれないと判定する判定ステップと、前記判定により前記目標とする３次元立体に含まれると判定された前記判別点を頂点とするポリゴンにより、前記目標とする３次元立体を表した３次元形状データを生成する形状データ生成ステップとを含む。
【００１４】
前記目標とする３次元立体に含まれると判定された判別点により変形された後の前記基準多面体に対して、前記判別点生成ステップ、前記占有率算出ステップ、および前記判定ステップを繰り返すことにより、前記基準多面体の表面形状を段階的に平滑化してもよい。
【００１５】
本発明の別の態様は、３次元形状データ生成装置である。この装置は、目標とする３次元立体の形状を近似した基準多面体の表面形状を平滑化した３次元形状データを生成する装置であって、前記基準多面体の表面近傍に判別点を生成する判別点生成部と、前記判別点を中心とする所定の半径の近傍球体内に近傍点を乱数により発生させ、前記近傍球体内の前記近傍点が前記基準多面体の内部に含まれる割合を示す占有率を算出する占有率算出部と、前記占有率が所定の判定閾値以上である場合に、前記判別点は前記目標とする３次元立体に含まれると判定し、前記占有率が前記判定閾値より小さい場合に、前記判別点は前記目標とする３次元立体に含まれないと判定する有効判別点判定部と、前記判定により前記目標とする３次元立体に含まれると判定された前記判別点を頂点とするポリゴンにより、前記目標とする３次元立体を表した３次元形状データを生成する３次元データ生成部とを含む。
【００１６】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、コンピュータプログラム、データ構造、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１７】
本発明によれば、任意形状の工業製品を容易に設計することができる。
【発明を実施するための最良の形態】
【００１８】
図１は、３次元形状データ生成装置１００の構成図である。同図は機能に着目したブロック図を描いており、これらの機能ブロックはハードウエアのみ、ソフトウエアのみ、またはそれらの組合せによっていろいろな形で実現することができる。
【００１９】
ソリッドモデル生成部１０は、目標とする３次元立体（以下、「目標立体」という）の形状をソリッドモデリングにより生成する。ソリッドモデリングでは、簡単な立体の一部を削除したり、複数の立体を組み合わせるなどの加工処理を繰り返して、目標立体の形状を近似する。
【００２０】
ソリッドモデリングの一例として、関数モデリングと呼ばれる手法により目標立体の形状をモデリングする。関数モデリングでは、物体を３次元空間の座標（ｘ，ｙ，ｚ）の関数ｆ（ｘ，ｙ，ｚ）で表現し、ｆ（ｘ，ｙ，ｚ）＞０なら物体の内側、ｆ（ｘ，ｙ，ｚ）＝０なら物体の表面、ｆ（ｘ，ｙ，ｚ）＜０なら物体の外側であると定義する。
【００２１】
直方体を関数で表現しておき、直方体を平面でカッティングし、任意の多面体を作成する。ここで、切断平面も関数で表現する。カッティングにおいて物体の内部、表面、外部を認識するために物体を木構造で記憶する。
【００２２】
たとえば、直方体を表現する関数をＰ、切断に使用した関数をＱとすると、カッティングによって得られた多面体の内部は、Ｐ＞０∧Ｑ＞０と表現される。同様に、多面体の表面は、Ｐ＝０∧Ｑ＝０と表現され、外部はＰ＜０∧Ｑ＜０と表現される。
【００２３】
このようなカッティング操作を繰り返すことによって、生成される多面体は、ｆ１≧０∧ｆ２≧０∧ｆ３≧０∧ｆ４≧０∧…のように表現される。ここで、ｆ１、ｆ２、ｆ３、ｆ４などは関数である。生成される多面体は関数表現されているため、モデリングの過程で計算誤差が累積することがない。
【００２４】
カッティング操作を繰り返すことで、ユーザは所望の３次元形状を多面体で近似することができる。カッティングにより得られた多面体を「基準多面体」という。
【００２５】
ソリッドモデル生成部１０は、関数表現された基準多面体を基準多面体記憶部４０に記憶する。基準多面体は目標立体を近似したものであるが、多面体であるために角張った形状であり、滑らかさがない。そこで、これから述べるように、基準多面体の表面形状を平滑化する処理を施す。
【００２６】
判別点生成部１２は、基準多面体記憶部４０から基準多面体の関数表現を取得し、基準多面体の表面の近傍に判別点をランダムに生成する。
【００２７】
判別点生成部１２は、基準多面体の表面を与える関数ｆ（ｘ，ｙ，ｚ）を用いて、ｆ（ｘ，ｙ，ｚ）＝０の近傍、すなわちｆ（ｘ，ｙ，ｚ）＝±εを満たす点（ｘ，ｙ，ｚ）を数値解析の手法を用いて、ランダムに生成することで、多面体の表面近傍に判別点を生成する。ここで、εは十分に小さな値である。
【００２８】
関数で定義されている曲面の表面上の点を検出するアルゴリズムについては、次の参考文献にさまざまな手法が紹介されており、本実施の形態において利用することができる。上述のように、曲面ｆ（ｘ，ｙ，ｚ）＝０に対して、ｆ（ｘ，ｙ，ｚ）＝±εを新たな曲面と考えれば、曲面の表面上の点を検出するアルゴリズムを用いて、表面近傍の点を生成することができる。
参考文献：Jules Bloomenthal, "Polygonization of Implicit Surfaces", XEROX PARC, CSL-87-2, May 1987.
【００２９】
占有率算出部１４は、判別点生成部１２により生成された判別点を中心とする所定の半径の近傍球体を設定し、その近傍球体内部の点（以下、「近傍点」という）を生成する。
【００３０】
占有率算出部１４は、近傍球体内部を極座標（ｒ，θ，ρ）で表現し、乱数を用いてｒ、θ、ρを生成することで、近傍球体内部に近傍点をランダムに生成する。後述のように、ｚ軸方向に垂直な平面すなわちｘｙ平面で基準多面体を切断し、その切断平面内で判別点を設ける場合は、判別点を中心とする近傍円を設定し、その近傍円内の点を極座標（ｒ，θ）で表現し、乱数を用いてｒ、θを生成することで、近傍円内部に近傍点をランダムに生成する。
【００３１】
ここで、近傍球体の半径は、基準多面体の表面の曲率に応じて調整される。表面曲率算出部１６は、基準多面体の表面の曲率を算出し、球体半径調整部１８に与える。球体半径調整部１８は、曲率が大きいほど近傍球体の半径が小さくなるように調整する。占有率算出部１４は、球体半径調整部１８により調整された半径で近傍球体を設定する。
【００３２】
多面体の頂点において曲率を定義するために、多面体の頂点Ｖにおけるガウス曲率を次の近似値Ｋにより近似する（参考文献：早野、松岡、植田、「特徴抽出と稜線操作によるポリゴンメッシュの簡単化」、Ricoh Technical Report No.24, November 1988）。近似ガウス曲率Ｋの絶対値が大きい頂点Ｖの形状は尖っている（あるいは凹んでいる）。
【００３３】
Ｋ＝ａ／Ｓ
ａ＝２π−（Ｖに集まる面の隅の角度の総和）
Ｓ＝（Ｖに集まる面の面積の総和）／３
【００３４】
次に、占有率算出部１４は、近傍球体が基準多面体に含まれる割合、すなわち基準多面体内部と近傍球体の論理積部分が近傍球体全体に対して占める割合（以下、「占有率」という）を求める。
【００３５】
占有率算出部１４は、近傍球体内部でランダムに発生させた近傍点が基準多面体内部にあるかどうかを判定し、基準多面体内部にある近傍点の数ｉを求め、発生した近傍点の総数Ｎで割った値ｐ＝ｉ／Ｎを求めることで、占有率を近似的に求める。占有率算出部１４は、近似された占有率ｐを有効判別点判定部２０に与える。
【００３６】
有効判別点判定部２０は、占有率ｐが所定の判定閾値ｔ以上である判別点は、目標立体の表面上または内部にあると判定し、占有率ｐが所定の判定閾値ｔより小さい判別点は、目標立体の外部にあると判定する。判別点が目標立体の表面上または内部にある場合、その判別点は「有効である」といい、判別点が目標立体の外部にある場合、その判別点は「無効である」という。
【００３７】
基準多面体の表面近傍に判別点を発生させ、判別点が目標立体の内部にあるかどうか（すなわち有効であるかどうか）を判定することで、基準多面体が目標立体に近づくように変形することができる。目標立体の外部にあると判定された部分（すなわち無効な判別点が占める部分）については基準多面体の表面から切り取り、目標立体の内部にあると判定された部分（すなわち有効な判別点が占める部分）については基準多面体の表面をふくらませる。基準多面体の頂点近傍でこの操作を行うと、基準多面体の角を丸めて平滑化することができる。これにより、基準多面体の表面形状を滑らかにして目標立体に近づけることができる。
【００３８】
ここで、判定閾値ｔは通常は０．５であるが、基準多面体が平滑化によって必要以上にへこんだときは、判定閾値ｔを小さくし、基準多面体が平滑化によって必要以上にふくらみすぎたときは、判定閾値ｔを大きくする。このために、ソリッドモデル生成部１０は、基準多面体の内部に含まれる「内包多面体」と、基準多面体を包含する「外包多面体」とをあらかじめ生成しておき、内包／外包多面体記憶部４２に記憶する。
【００３９】
内外判定部２４は、有効判別点判定部２０によって目標立体の内部にあると判定された判別点（「暫定有効判別点」という）について、暫定有効判別点が内包多面体の内部もしくは外包多面体の外部にあるかどうかを判定する。内外判定部２４は、暫定有効判別点が内包多面体の内部もしくは外包多面体の外部にある場合は、判定閾値調整部２６にその旨を通知する。
【００４０】
判定閾値調整部２６は、暫定有効判別点が内包多面体の内部にある場合は、判定閾値ｔを小さくし、暫定有効判別点が外包多面体の外部にある場合は、判定閾値ｔを大きくする。判定閾値調整部２６は、調整後の判定閾値ｔを有効判別点判定部２０に与える。
【００４１】
有効判別点判定部２０は、判定閾値調整部２６により調整された判定閾値ｔのもとで判別点の有効／無効の判定をやり直す。判定閾値調整部２６により調整された判定閾値ｔのもとで有効と判定された判別点が最終的に有効な判別点となる。以下、この最終的に有効と判定される判別点を単に「有効判別点」という。有効判別点判定部２０は、有効判別点を有効判別点記憶部４４に記憶する。
【００４２】
このようにして内包／外包多面体を設けて有効判別点を求めることで、外包多面体と内包多面体で挟まれる空間領域内で基準多面体の表面形状を有効判別点を基準にふくらませたり、へこませたりして変形させ、目標立体に近づけることができる。
【００４３】
ここで、基準多面体の表面近傍に１つの有効判別点があるとき、それよりも内側の有効判別点は、基準多面体を変形させる目的では不要であるから、有効判別点判定部２０は、最も外側の有効判別点のみを求めて有効判別点記憶部４４に記憶する。このために、判別点生成部１２は、基準多面体の表面に対して、外側から徐々に内側に近づくように判別点を生成して、判別点列を生成する。そして、有効判別点判定部２０が判別点列内の各判別点の有効／無効を判定し、無効判別点と有効判別点の境界を判定し、最も外側の有効判別点を求める。あるいは、別の方法として、バイナリサーチ（二分探索）の手法を用いて、基準多面体の表面近傍で最も外側にある有効判別点を探索してもよい。
【００４４】
表面形状変形部２２は、有効判別点をもとに基準多面体の表面形状を変形させ、変形後の基準多面体の形状データを基準多面体記憶部４０に記憶する。表面形状変形部２２は、基準多面体の頂点や面上の点などの特徴点を抽出し、特徴点を有効判別点の位置まで移動させることで、基準多面体の表面形状を変形させる。
【００４５】
表面形状変形部２２による変形後の基準多面体はディスプレイに表示され、ユーザは変形後の３次元形状を確認することができる。ユーザは必要であれば、変形後の基準多面体の表面形状の近傍に判別点を設定して、占有率を求め、有効判別点により表面形状を変形させて、目標立体に近づけることができる。このために、判別点生成部１２、占有率算出部１４、表面曲率算出部１６、球体半径調整部１８、有効判別点判定部２０、内外判定部２４、判定閾値調整部２６、表面形状変形部２２の各構成は、変形後の基準多面体を対象として上述の処理を施す。ここで、変形後の基準多面体は、平滑化処理により角の丸みが取れるなどによって、もはや厳密には多面体ではないが、便宜上、多面体と呼ぶことにする。これにより、基準多面体からスタートして、ユーザは変形結果を逐一確認しながら、段階的に平滑化処理を進めることができる。
【００４６】
３次元データ生成部２８は、有効判別点記憶部４４から有効判別点の集合を取得し、隣接する有効判別点を接続していくことにより有効判別点を頂点とするポリゴンを生成し、ポリゴンモデルを生成する。このポリゴンモデルは、目標立体の表面を滑らかに近似した３次元モデルとなっている。３次元データ生成部２８は、生成したポリゴンモデルの情報をポリゴン情報記憶部４６に記憶する。
【００４７】
３次元データ生成部２８は、有効判別点の集合のみを用いてポリゴンを生成するが、基準多面体の特徴点を基準多面体記憶部４０から読み出し、有効判別点と組み合わせて用いることでポリゴンを生成してもよい。
【００４８】
型紙展開部３０は、ポリゴン情報記憶部４６からポリゴンモデルの情報を取得し、ポリゴンモデルを２次元平面に展開することで目標立体の型紙を生成し、得られた型紙データを型紙データ記憶部４８に記憶する。型紙データは製造工場などに送られ、製品を作成するために利用される。
【００４９】
図２は、３次元形状データ生成装置１００による３次元形状データの生成手順の大まかな流れを示すフローチャートである。
【００５０】
３次元形状データ生成装置１００は、木彫りの彫刻のようなイメージで直方体をカッティングしていき、服装、かばん、靴などの工業製品の目標立体の形状を粗く造形する（Ｓ１００）。カッティングの方法として、上述の関数モデリングの他、関数表現などのソリッドモデルにより立体を表現し、２つの立体に和演算や差演算などの集合演算を適用して、凹面を含む立体形状を表現するようにしてもよい。これにより、目標立体の形状を近似した基準多面体が得られる。
【００５１】
次に、３次元形状データ生成装置１００は、基準多面体の表面形状を平滑化する（Ｓ１１０）。この平滑化処理には、基準多面体の角を丸くする他、基準多面体の各面をふくらませたり、へこませることも含まれる。この平滑化処理により基準多面体が目標立体により一層近づく。
【００５２】
最後に、３次元形状データ生成装置１００は、平滑化された基準多面体の３次元形状をポリゴンモデルなどで表現し、型紙に展開する（Ｓ１２０）。型紙データにより工業製品の生産が可能となる。
【００５３】
図３は、図２で示した平滑化処理Ｓ１１０の詳細な手順を示すフローチャートである。
【００５４】
判別点生成部１２は、基準多面体の表面近傍に判別点ｋを生成する（Ｓ１０）。占有率算出部１４は、基準多面体の内部にあると判定される近傍点の数を計数するための変数ｉと、発生した近傍点の総数をカウントするための変数Ｎを０に初期化する（Ｓ１２）。
【００５５】
占有率算出部１４は、判別点ｋを中心とする半径ｒの近傍球体内部に近傍点をランダムに発生させる（Ｓ１４）。占有率算出部１４は、発生した近傍点が基準多面体の内部にあるかどうかを判定し（Ｓ１６）、近傍点が基準多面体の内部にある場合（Ｓ１６のＹ）、カウンタｉを１だけインクリメントし（Ｓ１８）、近傍点が基準多面体の内部にない場合は、カウンタｉをインクリメントしない。
【００５６】
占有率算出部１４は、近傍点の総数Ｎを１だけインクリメントし（Ｓ２０）、占有率ｐをｉ／Ｎによって求める（Ｓ２２）。占有率算出部１４は、求めた占有率ｐの値が収束しているかどうかを判定する（Ｓ２４）。このために、占有率算出部１４は、近傍球体内部で近傍点をランダムに発生させながら求めた占有率ｐの値の履歴を保存しておき、占有率ｐの時間変化にもとづいて占有率ｐが収束しているかどうかを判定する。占有率の変動幅が所定の水準よりも小さくなった場合に占有率ｐは収束したと判定する。
【００５７】
占有率ｐがまだ収束していないと判定された場合（Ｓ２４のＮ）、ステップＳ１４に戻り、近傍球体内部でさらに近傍点を発生させ、占有率ｐを更新する（Ｓ１４〜Ｓ２２）。
【００５８】
占有率ｐが収束したと判定された場合（Ｓ２４のＹ）、有効判別点判定部２０は、占有率ｐが判定閾値ｔ以上であるかどうかを調べる（Ｓ２６）。
【００５９】
有効判別点判定部２０は、占有率ｐが判定閾値ｔ以上である場合（Ｓ２６のＹ）、判別点ｋは目標立体に含まれると判定し（Ｓ２８）、その判別点ｋを有効判別点として有効判別点記憶部４４に記憶する。
【００６０】
有効判別点判定部２０は、占有率ｐが判定閾値ｔより小さい場合（Ｓ２６のＮ）、判別点ｋは目標立体に含まれないと判定し（Ｓ３０）、その判別点ｋは有効判別点記憶部４４に記憶しない。
【００６１】
ユーザにより平滑化処理の終了が指示された場合（Ｓ３２のＹ）、この手順は終了する。平滑化処理がまだ完了していない場合（Ｓ３２のＮ）、ステップＳ１０に戻り、基準多面体表面もしくは既に平滑化された多面体表面の近傍に新たに判別点を設定して、同じ処理を繰り返す。
【００６２】
図４は、基準多面体の表面近傍に設けられる判別点と近傍球体を説明する図である。
【００６３】
基準多面体の表面２００（下側が基準多面体の内部で、上側が基準多面体の外部である）よりも外側に判別点２２０ａが設けられたとする。判定閾値ｔは０．５であるとする。この判別点２２０ａを中心とする半径ｒの近傍球体２１０ａを考えると、基準多面体の内側に含まれる近傍球体２１０ａ（斜線で示した部分２３０ａ）の体積は全体積の半分より小さい。よって、占有率ｐは０．５より小さくなり、判定閾値ｔより小さいから、判別点２２０ａは目標立体に含まれない、すなわち判別点２２０ａは無効であると判定される。以下、無効と判定された判別点は白丸で図示する。
【００６４】
基準多面体の表面２００上に判別点２２０ｂが設けられた場合、この判別点２２０ｂを中心とする近傍球体２１０ｂのちょうど半分（斜線で示した部分２３０ｂ）が基準多面体の内側に含まれる。よって、占有率ｐは０．５となり、判定閾値ｔに等しいから、判別点２２０ｂは目標立体に含まれる、すなわち判別点２２０ｂは有効であると判定される。以下、有効と判定された判別点は黒丸で図示する。
【００６５】
基準多面体の表面２００よりも内側に判別点２２０ｃが設けられた場合、この判別点２２０ｃを中心とする近傍球体２１０ｃの半分以上（斜線で示した部分２３０ｃ）が基準多面体内部に含まれる。よって占有率ｐは０．５より大きくなり、判定閾値ｔより大きいから、判別点２２０ｃは目標立体に含まれる、すなわち判別点２２０ｂは有効であると判定される。
【００６６】
図４の例では、基準多面体の平らな面の近傍に判別点を発生させたので、判定閾値ｔが０．５であれば、表面形状はふくらむこともへこむこともない。しかし、基準多面体の平面でない部分、たとえば、角やへこみの近傍に判別点を発生させると、表面形状がふくらんだり、へこんだりする。
【００６７】
図５（ａ）〜（ｃ）は、基準多面体の角の近傍に設けられる判別点と近傍球体を説明する図である。この例では、基準多面体の角（頂点）の近傍に判別点を発生させる。この例でも判定閾値ｔは０．５であるとする。
【００６８】
図５（ａ）では、基準多面体の角の近傍で、基準多面体の表面２００よりも外側に判別点２２０ａが設けられている。この判別点２２０ａを中心とする近傍球体２１０ａを考えると、基準多面体内部に含まれる近傍球体２１０ａ（斜線で示した部分２３０ａ）の体積は全体積の半分より小さい。よって占有率ｐは０．５より小さいため、判別点２２０ａは目標立体の外部にある、すなわち無効であると判定される。
【００６９】
図５（ｂ）では、基準多面体の角の近傍で、基準多面体の表面２００よりも内側に判別点２２０ｂが設けられている。この判別点２２０ｂを中心とする近傍球体２１０ｂを考えると、基準多面体内部に含まれる近傍球体２１０ｂ（斜線で示した部分２３０ｂ）の体積はまだ全体積の半分より小さい。よって占有率ｐは０．５より小さく、判別点２２０ｂは目標立体の外部にある、すなわち無効であると判定される。
【００７０】
図５（ｃ）では、基準多面体の表面２００に対して図５（ｂ）と比べてさらに内側に判別点２２０ｃが設けられている。この場合、判別点２２０ｃを中心とする近傍球体２１０ｃの半分以上（斜線で示した部分２３０ｃ）が基準多面体内部に含まれる。よって占有率ｐは０．５より大きく、判別点２２０ｂは目標立体の内部にある、すなわち有効であると判定される。
【００７１】
図５（ａ）〜（ｃ）の例では、目標立体の内部に含まれると判定される有効判別点が基準多面体の内側に存在するため、基準多面体の角は有効判別点の位置まで凹み、角が丸く削り取られることになる。
【００７２】
図６は、基準多面体の角における有効判別点を説明する図である。ここでも判定閾値ｔは０．５であるとする。基準多面体の角付近では、有効判別点は角の内側に存在する。基準多面体の平らな面では有効判別点はその面上に存在する。したがって、基準多面体の平らな面は削られることがないが、角付近では、同図の点線に示すように有効判別点が設けられ、角が丸くなる。
【００７３】
図７（ａ）、（ｂ）は、基準多面体の角付近において近傍球体の半径を変えた場合の有効判別点の位置の変化を説明する図である。図７（ａ）は、近傍球体の半径を小さくした場合であり、有効判別点の位置が角に近づく。図７（ｂ）は、近傍球体の半径を大きくした場合であり、有効判別点の位置が角から遠ざかる。このように、近傍球体の半径を変えることで角の削り取りを変えることができる。
【００７４】
図８（ａ）、（ｂ）は、基準多面体の角付近において占有率の判定閾値を変えた場合の有効判別点の位置の変化を説明する図である。図８（ａ）は、占有率ｐの判定閾値ｔを０．５より小さくした場合であり、基準多面体内部に含まれる近傍球体の体積は半分より小さくてよいため、有効判別点は、点線で示すように、基準多面体の表面２００から外側に離れた位置に移動する。
【００７５】
図８（ｂ）は、占有率ｐの判定閾値ｔを０．５より大きくした場合であり、基準多面体内部に含まれる近傍球体の体積は半分より大きくなる必要があるため、有効判別点は、点線で示すように、基準多面体の表面２００よりも内側に入った位置に移動する。
【００７６】
なお、判定閾値ｔを途中で変化させると段差が生まれるため、原則として判定閾値ｔは一定にする。閾値を変える場合は、閾値移行領域を設け、判定閾値ｔを閾値移行領域において連続的に変化させることが好ましい。
【００７７】
図９は、基準多面体の表面２００の形状の複雑度に応じて、近傍球体の半径を変える様子を説明する図である。鋭く尖った角など複雑で細かな表面形状に対しては、符号２１０ａ、２１０ｂに示すように、近傍球体の半径を小さく設定する。尖った角に対して大きな半径の近傍球体を設定すると、角を削ることができないからである。複雑で細かく造形された表面形状に対しては、その形状の細かさに合わせて近傍球体の半径を十分に小さくする必要がある。近傍球体の半径が小さい場合、角の削られ方が少なくなり、元の多面体形状を良く保存することができるからである。
【００７８】
一方、あまり細かく造形されていない表面形状に対しては、符号２１０ｃに示すように、近傍球体の半径を大きく設定する。大まかな形状に対しては、それに合わせて近傍球体の半径を大きくすることで、表面を大きく削ることができる。
【００７９】
もとの形状をなるべく保存するという立場から、近傍球体の半径は小さめでスタートし、角の丸み具合を見ながら半径を徐々に大きくしながら、基準多面体に対して繰り返し平滑化処理を施すことが好ましい。ここで、角の丸み具合は曲率で評価することができる。
【００８０】
図１０（ａ）〜（ｃ）は、判別点を生成する平面と有効判別点を接続することで得られるポリゴンを説明する図である。
【００８１】
図１０（ａ）、（ｂ）は、ｚ軸に垂直な面すなわちｘｙ平面で基準多面体を切断した様子を示す。実線は基準多面体の表面を示す。基準多面体の表面の近傍で判別点を発生させ、有効判別点を求める。有効判別点により、角が削られた様子が点線で示されている。
【００８２】
図１０（ａ）では、ｚ＝１に固定してｘｙ平面で判別点を発生させ、図１０（ｂ）では、ｚ＝２に固定してｘｙ平面で判別点を発生させる。このため、判別点のｘ座標値、ｙ座標値のみをランダムに生成すればよく、判別点の生成処理が簡略化できる。
【００８３】
図１０（ｃ）に、ｚ＝１で切断したｘｙ平面で求めた有効判別点の集合（符号２５０ａ）、ｚ＝２で切断したｘｙ平面で求めた有効判別点の集合（符号２５０ｂ）、ｚ＝３で切断したｘｙ平面で求めた有効判別点の集合（符号２５０ｃ）を示す。これらの切断面間で有効判別点をつないでいくことで、矩形のポリゴンが生成される様子が示されている。
【００８４】
このように、ｚ座標値を離散的に変えながら、ｘｙ平面で有効判別点を求め、各ｘｙ平面の有効判別点をｚ軸方向につないでいくことでポリゴンが生成され、目標立体の３次元形状データをポリゴンモデルで表現することができる。なお、ポリゴンモデルを生成する際、有効判別点を頂点とするポリゴンを生成する以外に、もとの基準多面体の特徴点をポリゴンの頂点として適宜用いてもよい。
【００８５】
判別点の選び方として、多面体を切り出す前の直方体（ふくらみを考えるならば、それよりもやや大きめの直方体）の内部に一様に乱数を発生させて判別点とすることが一般には考えられるが、これでは計算量が膨大になる。そこで、型紙展開を前提とする場合は、図１０（ａ）〜（ｃ）に示すように、基準多面体を高さ方向や奥行き方向などの一定の方向に等間隔で輪切りして、その輪切りされた切断平面内で判別点を発生させることが計算量の面で有利である。また、高さ方向などの一定方向に所定の間隔を空けて頂点が位置する矩形のポリゴンで３次元形状を表すと、ポリゴンモデルを型紙に展開しやすいという利点もある。
【００８６】
以上、本実施の形態の３次元形状データ生成装置１００によれば、目標とする３次元形状を多面体で与えておき、その形状になるべく沿いながら丸みをもたせることができる。最終的な形状データは、有効判別点の集合として確定するため、隣接する有効判別点を接続していくことでポリゴンメッシュが生成され、最終形態を立体表示して確認したり、型紙データに展開することができる。
【００８７】
３次元形状データ生成装置１００では、ユーザが角の丸み具合などをディスプレイで確認しながら、近傍球体の半径や占有率の判定閾値などのパラメータを調整して平滑化処理を繰り返す行うことで、目標とする３次元形状を作成することができる。ユーザが形状の変形結果を確認しながら、意図する曲面形状を実現していくことができるため、インタラクティブ性の高いシステムを提供することができる。
【００８８】
本実施の形態では、目標とする３次元形状を近似する基準多面体を関数表現で与え、その基準多面体をもとにして平滑化処理を行うため、計算誤差の累積が少ない。したがって、本実施の形態の３次元形状データの生成方法は、工業製品の型紙作成のような正確さが要求される分野に特に有効である。
【００８９】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００９０】
実施の形態では、直方体を平面で切断した基準多面体からスタートして平滑化処理を施し、目標立体を近似するポリゴンモデルを生成したが、平滑化処理を施す基準多面体として、ＣＧにより生成されたポリゴンモデルを用いてもよい。
【図面の簡単な説明】
【００９１】
【図１】３次元形状データ生成装置の構成図である。
【図２】３次元形状データ生成装置による３次元形状データの生成手順の大まかな流れを示すフローチャートである。
【図３】図２で示した平滑化処理の詳細な手順を示すフローチャートである。
【図４】基準多面体の表面近傍に設けられる判別点と近傍球体を説明する図である。
【図５】基準多面体の角の近傍に設けられる判別点と近傍球体を説明する図である。
【図６】基準多面体の角における有効判別点を説明する図である。
【図７】基準多面体の角付近において近傍球体の半径を変えた場合の有効判別点の位置の変化を説明する図である。
【図８】基準多面体の角付近において占有率の判定閾値を変えた場合の有効判別点の位置の変化を説明する図である。
【図９】基準多面体の表面形状の複雑度に応じて、近傍球体の半径を変える様子を説明する図である。
【図１０】判別点を生成する平面と有効判別点を接続することで得られるポリゴンを説明する図である。
【符号の説明】
【００９２】
１０ ソリッドモデル生成部、 １２ 判別点生成部、 １４ 占有率算出部、 １６ 表面曲率算出部、 １８ 球体半径調整部、 ２０ 有効判別点判定部、 ２２ 表面形状変形部、 ２４ 内外判定部、 ２６ 判定閾値調整部、 ２８ ３次元データ生成部、 ３０ 型紙展開部、 ４０ 基準多面体記憶部、 ４２ 内包／外包多面体記憶部、 ４４ 有効判別点記憶部、 ４６ ポリゴン情報記憶部、 ４８ 型紙データ記憶部、 １００ ３次元形状データ生成装置。
【技術分野】
【０００１】
この発明は、３次元立体の形状を表す３次元形状データを生成するための３次元形状データ生成方法および３次元形状生成装置に関する。
【背景技術】
【０００２】
服装、かばん、靴などの工業製品は、型紙を用いて製造される。服飾デザインの分野では、アパレルＣＡＤシステムが用いられている。アパレルＣＡＤシステムでは、型紙のテンプレートが用意され、ユーザはテンプレートを変形して所望のデザインの型紙を作成し、立体表示させて着衣状態をシミュレーションすることができる。
【０００３】
最近では、医療や介護の現場において、一般の既製服とは異なり、患者にとって着脱が容易な服装や、身体不自由の人を車椅子とベッドの間をリフティングにより移動させる際のフックを設けた専用の服など、特殊用途の服が求められている。患者の体型や身体の自由度、使用条件などに合わせて衣服の形状を新たにデザインする必要がある。
【０００４】
アパレルＣＡＤシステムでは、型紙のテンプレートが提供され、ユーザはテンプレートを自由に修正することで所望のデザインの型紙を作成する。顧客の体形が標準からかなりずれている場合や、介護用などの特殊な形状の衣服をデザインする場合、あるいはデザインが個性的で標準的なテンプレートが存在しない場合などには、用意されたテンプレートがほとんど意味をなさず、所望の型紙を作成するのは非常に難しくなる。また、かばんや靴などの型紙を作成する場合においても、流行に合わせて様々な形状をデザインする必要があり、用意されたテンプレートをベースとして型紙を生成する方法ではとても対応しきれない。
【０００５】
このような状況のもと、コンピュータグラフィックス（ＣＧ）技術により立体形状をモデリングし、ＣＧによる３次元モデルの形状を自動的に型紙に展開して製品の工業生産に利用することが求められている。
【０００６】
特許文献１には、衣服を求める顧客が自分の体型に合った衣服のデザイン画を描き、これを基にその衣服の型紙パターンをＣＡＤ／ＣＡＭ技術を応用して敏速・簡易に作成することのできる衣服の型紙パターンの自動作成方法とその自動作成システムが開示されている。
【特許文献１】特開２００１−２４９９５７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
３次元形状のモデリング手法としてポリゴンモデリングが一般的であり、ポリゴンモデルでは、ポリゴンの集まりであるポリゴンメッシュによって３次元形状を表現する。ポリゴンモデルは、ポリゴンを継ぎ合わせることで複雑な形状でも表現可能であるが、インタラクティブな処理が難しく、また滑らかな表面形状を忠実に表現するにはポリゴン数を増やす必要があり、データ量が増大する。ポリゴンメッシュは、形状状態の厳密さを追求するのではなく、形状を多面体として簡素化し表示を高速化するために用いられたり、解析用のモデルとして利用されている。
【０００８】
衣服やかばんなどの工業製品の３次元形状をＣＧによりモデリングする際、曲線や曲面の形状が非常に重要になる。任意の曲面を扱うために、自由曲面が用いられる。自由曲面は、ベジェ曲線、スプライン曲線、ＮＵＲＢＳ曲線を用いて面を定義するものであり、ポリゴンモデルに比べて、任意の滑らかな形状をより厳密に表現することができる。
【０００９】
しかしながら、自由曲面により３次元形状を定義する方法では、目的とする形状を想像しながら制御点などのパラメータを決める必要があり、自由度が高い反面、意図する形状を設計するのは非常に難しい。また、複雑な形状、たとえばフレアスカートのようなものをデザインする場合は、制御点への追従性が悪くなるため、形状が複雑になるほど制御点の数が増大するという問題がある。
【００１０】
細分化曲面（Subdivision Surface）と呼ばれる技法があり、車のデザインなどに使われている。細分化曲面法は、大まかにモデリングされたポリゴンメッシュを細分化して、滑らかで継ぎ目のない形状にする技術である。自由曲面に近い滑らかな形状を表現できるが、ポリゴンメッシュに比べてデータ量が増えるという問題がある。
【００１１】
また、単純な図形を組み合わせて立体形状を表現しておき、後で空間フィルタを用いて整形する方法もあるが、空間フィルタは周波数領域での特性を指定するものであるため、実際の形状にどのように反映されるかが分かりづらく、意図した形状をデザインすることは容易ではない。
【００１２】
本発明はこうした課題に鑑みてなされたものであり、その目的は、工業製品などの任意の形状を容易に設計することのできる３次元形状データ生成装置および３次元形状データ生成方法を提供することにある。
【課題を解決するための手段】
【００１３】
上記課題を解決するために、本発明のある態様の３次元形状データ生成方法は、目標とする３次元立体の形状を近似した基準多面体の表面形状を平滑化した３次元形状データを生成する方法であって、前記基準多面体の表面近傍に判別点を生成する判別点生成ステップと、前記判別点を中心とする所定の半径の近傍球体内に近傍点を乱数により発生させ、前記近傍球体内の前記近傍点が前記基準多面体の内部に含まれる割合を示す占有率を算出する占有率算出ステップと、前記占有率が所定の判定閾値以上である場合に、前記判別点は前記目標とする３次元立体に含まれると判定し、前記占有率が前記判定閾値より小さい場合に、前記判別点は前記目標とする３次元立体に含まれないと判定する判定ステップと、前記判定により前記目標とする３次元立体に含まれると判定された前記判別点を頂点とするポリゴンにより、前記目標とする３次元立体を表した３次元形状データを生成する形状データ生成ステップとを含む。
【００１４】
前記目標とする３次元立体に含まれると判定された判別点により変形された後の前記基準多面体に対して、前記判別点生成ステップ、前記占有率算出ステップ、および前記判定ステップを繰り返すことにより、前記基準多面体の表面形状を段階的に平滑化してもよい。
【００１５】
本発明の別の態様は、３次元形状データ生成装置である。この装置は、目標とする３次元立体の形状を近似した基準多面体の表面形状を平滑化した３次元形状データを生成する装置であって、前記基準多面体の表面近傍に判別点を生成する判別点生成部と、前記判別点を中心とする所定の半径の近傍球体内に近傍点を乱数により発生させ、前記近傍球体内の前記近傍点が前記基準多面体の内部に含まれる割合を示す占有率を算出する占有率算出部と、前記占有率が所定の判定閾値以上である場合に、前記判別点は前記目標とする３次元立体に含まれると判定し、前記占有率が前記判定閾値より小さい場合に、前記判別点は前記目標とする３次元立体に含まれないと判定する有効判別点判定部と、前記判定により前記目標とする３次元立体に含まれると判定された前記判別点を頂点とするポリゴンにより、前記目標とする３次元立体を表した３次元形状データを生成する３次元データ生成部とを含む。
【００１６】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、コンピュータプログラム、データ構造、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１７】
本発明によれば、任意形状の工業製品を容易に設計することができる。
【発明を実施するための最良の形態】
【００１８】
図１は、３次元形状データ生成装置１００の構成図である。同図は機能に着目したブロック図を描いており、これらの機能ブロックはハードウエアのみ、ソフトウエアのみ、またはそれらの組合せによっていろいろな形で実現することができる。
【００１９】
ソリッドモデル生成部１０は、目標とする３次元立体（以下、「目標立体」という）の形状をソリッドモデリングにより生成する。ソリッドモデリングでは、簡単な立体の一部を削除したり、複数の立体を組み合わせるなどの加工処理を繰り返して、目標立体の形状を近似する。
【００２０】
ソリッドモデリングの一例として、関数モデリングと呼ばれる手法により目標立体の形状をモデリングする。関数モデリングでは、物体を３次元空間の座標（ｘ，ｙ，ｚ）の関数ｆ（ｘ，ｙ，ｚ）で表現し、ｆ（ｘ，ｙ，ｚ）＞０なら物体の内側、ｆ（ｘ，ｙ，ｚ）＝０なら物体の表面、ｆ（ｘ，ｙ，ｚ）＜０なら物体の外側であると定義する。
【００２１】
直方体を関数で表現しておき、直方体を平面でカッティングし、任意の多面体を作成する。ここで、切断平面も関数で表現する。カッティングにおいて物体の内部、表面、外部を認識するために物体を木構造で記憶する。
【００２２】
たとえば、直方体を表現する関数をＰ、切断に使用した関数をＱとすると、カッティングによって得られた多面体の内部は、Ｐ＞０∧Ｑ＞０と表現される。同様に、多面体の表面は、Ｐ＝０∧Ｑ＝０と表現され、外部はＰ＜０∧Ｑ＜０と表現される。
【００２３】
このようなカッティング操作を繰り返すことによって、生成される多面体は、ｆ１≧０∧ｆ２≧０∧ｆ３≧０∧ｆ４≧０∧…のように表現される。ここで、ｆ１、ｆ２、ｆ３、ｆ４などは関数である。生成される多面体は関数表現されているため、モデリングの過程で計算誤差が累積することがない。
【００２４】
カッティング操作を繰り返すことで、ユーザは所望の３次元形状を多面体で近似することができる。カッティングにより得られた多面体を「基準多面体」という。
【００２５】
ソリッドモデル生成部１０は、関数表現された基準多面体を基準多面体記憶部４０に記憶する。基準多面体は目標立体を近似したものであるが、多面体であるために角張った形状であり、滑らかさがない。そこで、これから述べるように、基準多面体の表面形状を平滑化する処理を施す。
【００２６】
判別点生成部１２は、基準多面体記憶部４０から基準多面体の関数表現を取得し、基準多面体の表面の近傍に判別点をランダムに生成する。
【００２７】
判別点生成部１２は、基準多面体の表面を与える関数ｆ（ｘ，ｙ，ｚ）を用いて、ｆ（ｘ，ｙ，ｚ）＝０の近傍、すなわちｆ（ｘ，ｙ，ｚ）＝±εを満たす点（ｘ，ｙ，ｚ）を数値解析の手法を用いて、ランダムに生成することで、多面体の表面近傍に判別点を生成する。ここで、εは十分に小さな値である。
【００２８】
関数で定義されている曲面の表面上の点を検出するアルゴリズムについては、次の参考文献にさまざまな手法が紹介されており、本実施の形態において利用することができる。上述のように、曲面ｆ（ｘ，ｙ，ｚ）＝０に対して、ｆ（ｘ，ｙ，ｚ）＝±εを新たな曲面と考えれば、曲面の表面上の点を検出するアルゴリズムを用いて、表面近傍の点を生成することができる。
参考文献：Jules Bloomenthal, "Polygonization of Implicit Surfaces", XEROX PARC, CSL-87-2, May 1987.
【００２９】
占有率算出部１４は、判別点生成部１２により生成された判別点を中心とする所定の半径の近傍球体を設定し、その近傍球体内部の点（以下、「近傍点」という）を生成する。
【００３０】
占有率算出部１４は、近傍球体内部を極座標（ｒ，θ，ρ）で表現し、乱数を用いてｒ、θ、ρを生成することで、近傍球体内部に近傍点をランダムに生成する。後述のように、ｚ軸方向に垂直な平面すなわちｘｙ平面で基準多面体を切断し、その切断平面内で判別点を設ける場合は、判別点を中心とする近傍円を設定し、その近傍円内の点を極座標（ｒ，θ）で表現し、乱数を用いてｒ、θを生成することで、近傍円内部に近傍点をランダムに生成する。
【００３１】
ここで、近傍球体の半径は、基準多面体の表面の曲率に応じて調整される。表面曲率算出部１６は、基準多面体の表面の曲率を算出し、球体半径調整部１８に与える。球体半径調整部１８は、曲率が大きいほど近傍球体の半径が小さくなるように調整する。占有率算出部１４は、球体半径調整部１８により調整された半径で近傍球体を設定する。
【００３２】
多面体の頂点において曲率を定義するために、多面体の頂点Ｖにおけるガウス曲率を次の近似値Ｋにより近似する（参考文献：早野、松岡、植田、「特徴抽出と稜線操作によるポリゴンメッシュの簡単化」、Ricoh Technical Report No.24, November 1988）。近似ガウス曲率Ｋの絶対値が大きい頂点Ｖの形状は尖っている（あるいは凹んでいる）。
【００３３】
Ｋ＝ａ／Ｓ
ａ＝２π−（Ｖに集まる面の隅の角度の総和）
Ｓ＝（Ｖに集まる面の面積の総和）／３
【００３４】
次に、占有率算出部１４は、近傍球体が基準多面体に含まれる割合、すなわち基準多面体内部と近傍球体の論理積部分が近傍球体全体に対して占める割合（以下、「占有率」という）を求める。
【００３５】
占有率算出部１４は、近傍球体内部でランダムに発生させた近傍点が基準多面体内部にあるかどうかを判定し、基準多面体内部にある近傍点の数ｉを求め、発生した近傍点の総数Ｎで割った値ｐ＝ｉ／Ｎを求めることで、占有率を近似的に求める。占有率算出部１４は、近似された占有率ｐを有効判別点判定部２０に与える。
【００３６】
有効判別点判定部２０は、占有率ｐが所定の判定閾値ｔ以上である判別点は、目標立体の表面上または内部にあると判定し、占有率ｐが所定の判定閾値ｔより小さい判別点は、目標立体の外部にあると判定する。判別点が目標立体の表面上または内部にある場合、その判別点は「有効である」といい、判別点が目標立体の外部にある場合、その判別点は「無効である」という。
【００３７】
基準多面体の表面近傍に判別点を発生させ、判別点が目標立体の内部にあるかどうか（すなわち有効であるかどうか）を判定することで、基準多面体が目標立体に近づくように変形することができる。目標立体の外部にあると判定された部分（すなわち無効な判別点が占める部分）については基準多面体の表面から切り取り、目標立体の内部にあると判定された部分（すなわち有効な判別点が占める部分）については基準多面体の表面をふくらませる。基準多面体の頂点近傍でこの操作を行うと、基準多面体の角を丸めて平滑化することができる。これにより、基準多面体の表面形状を滑らかにして目標立体に近づけることができる。
【００３８】
ここで、判定閾値ｔは通常は０．５であるが、基準多面体が平滑化によって必要以上にへこんだときは、判定閾値ｔを小さくし、基準多面体が平滑化によって必要以上にふくらみすぎたときは、判定閾値ｔを大きくする。このために、ソリッドモデル生成部１０は、基準多面体の内部に含まれる「内包多面体」と、基準多面体を包含する「外包多面体」とをあらかじめ生成しておき、内包／外包多面体記憶部４２に記憶する。
【００３９】
内外判定部２４は、有効判別点判定部２０によって目標立体の内部にあると判定された判別点（「暫定有効判別点」という）について、暫定有効判別点が内包多面体の内部もしくは外包多面体の外部にあるかどうかを判定する。内外判定部２４は、暫定有効判別点が内包多面体の内部もしくは外包多面体の外部にある場合は、判定閾値調整部２６にその旨を通知する。
【００４０】
判定閾値調整部２６は、暫定有効判別点が内包多面体の内部にある場合は、判定閾値ｔを小さくし、暫定有効判別点が外包多面体の外部にある場合は、判定閾値ｔを大きくする。判定閾値調整部２６は、調整後の判定閾値ｔを有効判別点判定部２０に与える。
【００４１】
有効判別点判定部２０は、判定閾値調整部２６により調整された判定閾値ｔのもとで判別点の有効／無効の判定をやり直す。判定閾値調整部２６により調整された判定閾値ｔのもとで有効と判定された判別点が最終的に有効な判別点となる。以下、この最終的に有効と判定される判別点を単に「有効判別点」という。有効判別点判定部２０は、有効判別点を有効判別点記憶部４４に記憶する。
【００４２】
このようにして内包／外包多面体を設けて有効判別点を求めることで、外包多面体と内包多面体で挟まれる空間領域内で基準多面体の表面形状を有効判別点を基準にふくらませたり、へこませたりして変形させ、目標立体に近づけることができる。
【００４３】
ここで、基準多面体の表面近傍に１つの有効判別点があるとき、それよりも内側の有効判別点は、基準多面体を変形させる目的では不要であるから、有効判別点判定部２０は、最も外側の有効判別点のみを求めて有効判別点記憶部４４に記憶する。このために、判別点生成部１２は、基準多面体の表面に対して、外側から徐々に内側に近づくように判別点を生成して、判別点列を生成する。そして、有効判別点判定部２０が判別点列内の各判別点の有効／無効を判定し、無効判別点と有効判別点の境界を判定し、最も外側の有効判別点を求める。あるいは、別の方法として、バイナリサーチ（二分探索）の手法を用いて、基準多面体の表面近傍で最も外側にある有効判別点を探索してもよい。
【００４４】
表面形状変形部２２は、有効判別点をもとに基準多面体の表面形状を変形させ、変形後の基準多面体の形状データを基準多面体記憶部４０に記憶する。表面形状変形部２２は、基準多面体の頂点や面上の点などの特徴点を抽出し、特徴点を有効判別点の位置まで移動させることで、基準多面体の表面形状を変形させる。
【００４５】
表面形状変形部２２による変形後の基準多面体はディスプレイに表示され、ユーザは変形後の３次元形状を確認することができる。ユーザは必要であれば、変形後の基準多面体の表面形状の近傍に判別点を設定して、占有率を求め、有効判別点により表面形状を変形させて、目標立体に近づけることができる。このために、判別点生成部１２、占有率算出部１４、表面曲率算出部１６、球体半径調整部１８、有効判別点判定部２０、内外判定部２４、判定閾値調整部２６、表面形状変形部２２の各構成は、変形後の基準多面体を対象として上述の処理を施す。ここで、変形後の基準多面体は、平滑化処理により角の丸みが取れるなどによって、もはや厳密には多面体ではないが、便宜上、多面体と呼ぶことにする。これにより、基準多面体からスタートして、ユーザは変形結果を逐一確認しながら、段階的に平滑化処理を進めることができる。
【００４６】
３次元データ生成部２８は、有効判別点記憶部４４から有効判別点の集合を取得し、隣接する有効判別点を接続していくことにより有効判別点を頂点とするポリゴンを生成し、ポリゴンモデルを生成する。このポリゴンモデルは、目標立体の表面を滑らかに近似した３次元モデルとなっている。３次元データ生成部２８は、生成したポリゴンモデルの情報をポリゴン情報記憶部４６に記憶する。
【００４７】
３次元データ生成部２８は、有効判別点の集合のみを用いてポリゴンを生成するが、基準多面体の特徴点を基準多面体記憶部４０から読み出し、有効判別点と組み合わせて用いることでポリゴンを生成してもよい。
【００４８】
型紙展開部３０は、ポリゴン情報記憶部４６からポリゴンモデルの情報を取得し、ポリゴンモデルを２次元平面に展開することで目標立体の型紙を生成し、得られた型紙データを型紙データ記憶部４８に記憶する。型紙データは製造工場などに送られ、製品を作成するために利用される。
【００４９】
図２は、３次元形状データ生成装置１００による３次元形状データの生成手順の大まかな流れを示すフローチャートである。
【００５０】
３次元形状データ生成装置１００は、木彫りの彫刻のようなイメージで直方体をカッティングしていき、服装、かばん、靴などの工業製品の目標立体の形状を粗く造形する（Ｓ１００）。カッティングの方法として、上述の関数モデリングの他、関数表現などのソリッドモデルにより立体を表現し、２つの立体に和演算や差演算などの集合演算を適用して、凹面を含む立体形状を表現するようにしてもよい。これにより、目標立体の形状を近似した基準多面体が得られる。
【００５１】
次に、３次元形状データ生成装置１００は、基準多面体の表面形状を平滑化する（Ｓ１１０）。この平滑化処理には、基準多面体の角を丸くする他、基準多面体の各面をふくらませたり、へこませることも含まれる。この平滑化処理により基準多面体が目標立体により一層近づく。
【００５２】
最後に、３次元形状データ生成装置１００は、平滑化された基準多面体の３次元形状をポリゴンモデルなどで表現し、型紙に展開する（Ｓ１２０）。型紙データにより工業製品の生産が可能となる。
【００５３】
図３は、図２で示した平滑化処理Ｓ１１０の詳細な手順を示すフローチャートである。
【００５４】
判別点生成部１２は、基準多面体の表面近傍に判別点ｋを生成する（Ｓ１０）。占有率算出部１４は、基準多面体の内部にあると判定される近傍点の数を計数するための変数ｉと、発生した近傍点の総数をカウントするための変数Ｎを０に初期化する（Ｓ１２）。
【００５５】
占有率算出部１４は、判別点ｋを中心とする半径ｒの近傍球体内部に近傍点をランダムに発生させる（Ｓ１４）。占有率算出部１４は、発生した近傍点が基準多面体の内部にあるかどうかを判定し（Ｓ１６）、近傍点が基準多面体の内部にある場合（Ｓ１６のＹ）、カウンタｉを１だけインクリメントし（Ｓ１８）、近傍点が基準多面体の内部にない場合は、カウンタｉをインクリメントしない。
【００５６】
占有率算出部１４は、近傍点の総数Ｎを１だけインクリメントし（Ｓ２０）、占有率ｐをｉ／Ｎによって求める（Ｓ２２）。占有率算出部１４は、求めた占有率ｐの値が収束しているかどうかを判定する（Ｓ２４）。このために、占有率算出部１４は、近傍球体内部で近傍点をランダムに発生させながら求めた占有率ｐの値の履歴を保存しておき、占有率ｐの時間変化にもとづいて占有率ｐが収束しているかどうかを判定する。占有率の変動幅が所定の水準よりも小さくなった場合に占有率ｐは収束したと判定する。
【００５７】
占有率ｐがまだ収束していないと判定された場合（Ｓ２４のＮ）、ステップＳ１４に戻り、近傍球体内部でさらに近傍点を発生させ、占有率ｐを更新する（Ｓ１４〜Ｓ２２）。
【００５８】
占有率ｐが収束したと判定された場合（Ｓ２４のＹ）、有効判別点判定部２０は、占有率ｐが判定閾値ｔ以上であるかどうかを調べる（Ｓ２６）。
【００５９】
有効判別点判定部２０は、占有率ｐが判定閾値ｔ以上である場合（Ｓ２６のＹ）、判別点ｋは目標立体に含まれると判定し（Ｓ２８）、その判別点ｋを有効判別点として有効判別点記憶部４４に記憶する。
【００６０】
有効判別点判定部２０は、占有率ｐが判定閾値ｔより小さい場合（Ｓ２６のＮ）、判別点ｋは目標立体に含まれないと判定し（Ｓ３０）、その判別点ｋは有効判別点記憶部４４に記憶しない。
【００６１】
ユーザにより平滑化処理の終了が指示された場合（Ｓ３２のＹ）、この手順は終了する。平滑化処理がまだ完了していない場合（Ｓ３２のＮ）、ステップＳ１０に戻り、基準多面体表面もしくは既に平滑化された多面体表面の近傍に新たに判別点を設定して、同じ処理を繰り返す。
【００６２】
図４は、基準多面体の表面近傍に設けられる判別点と近傍球体を説明する図である。
【００６３】
基準多面体の表面２００（下側が基準多面体の内部で、上側が基準多面体の外部である）よりも外側に判別点２２０ａが設けられたとする。判定閾値ｔは０．５であるとする。この判別点２２０ａを中心とする半径ｒの近傍球体２１０ａを考えると、基準多面体の内側に含まれる近傍球体２１０ａ（斜線で示した部分２３０ａ）の体積は全体積の半分より小さい。よって、占有率ｐは０．５より小さくなり、判定閾値ｔより小さいから、判別点２２０ａは目標立体に含まれない、すなわち判別点２２０ａは無効であると判定される。以下、無効と判定された判別点は白丸で図示する。
【００６４】
基準多面体の表面２００上に判別点２２０ｂが設けられた場合、この判別点２２０ｂを中心とする近傍球体２１０ｂのちょうど半分（斜線で示した部分２３０ｂ）が基準多面体の内側に含まれる。よって、占有率ｐは０．５となり、判定閾値ｔに等しいから、判別点２２０ｂは目標立体に含まれる、すなわち判別点２２０ｂは有効であると判定される。以下、有効と判定された判別点は黒丸で図示する。
【００６５】
基準多面体の表面２００よりも内側に判別点２２０ｃが設けられた場合、この判別点２２０ｃを中心とする近傍球体２１０ｃの半分以上（斜線で示した部分２３０ｃ）が基準多面体内部に含まれる。よって占有率ｐは０．５より大きくなり、判定閾値ｔより大きいから、判別点２２０ｃは目標立体に含まれる、すなわち判別点２２０ｂは有効であると判定される。
【００６６】
図４の例では、基準多面体の平らな面の近傍に判別点を発生させたので、判定閾値ｔが０．５であれば、表面形状はふくらむこともへこむこともない。しかし、基準多面体の平面でない部分、たとえば、角やへこみの近傍に判別点を発生させると、表面形状がふくらんだり、へこんだりする。
【００６７】
図５（ａ）〜（ｃ）は、基準多面体の角の近傍に設けられる判別点と近傍球体を説明する図である。この例では、基準多面体の角（頂点）の近傍に判別点を発生させる。この例でも判定閾値ｔは０．５であるとする。
【００６８】
図５（ａ）では、基準多面体の角の近傍で、基準多面体の表面２００よりも外側に判別点２２０ａが設けられている。この判別点２２０ａを中心とする近傍球体２１０ａを考えると、基準多面体内部に含まれる近傍球体２１０ａ（斜線で示した部分２３０ａ）の体積は全体積の半分より小さい。よって占有率ｐは０．５より小さいため、判別点２２０ａは目標立体の外部にある、すなわち無効であると判定される。
【００６９】
図５（ｂ）では、基準多面体の角の近傍で、基準多面体の表面２００よりも内側に判別点２２０ｂが設けられている。この判別点２２０ｂを中心とする近傍球体２１０ｂを考えると、基準多面体内部に含まれる近傍球体２１０ｂ（斜線で示した部分２３０ｂ）の体積はまだ全体積の半分より小さい。よって占有率ｐは０．５より小さく、判別点２２０ｂは目標立体の外部にある、すなわち無効であると判定される。
【００７０】
図５（ｃ）では、基準多面体の表面２００に対して図５（ｂ）と比べてさらに内側に判別点２２０ｃが設けられている。この場合、判別点２２０ｃを中心とする近傍球体２１０ｃの半分以上（斜線で示した部分２３０ｃ）が基準多面体内部に含まれる。よって占有率ｐは０．５より大きく、判別点２２０ｂは目標立体の内部にある、すなわち有効であると判定される。
【００７１】
図５（ａ）〜（ｃ）の例では、目標立体の内部に含まれると判定される有効判別点が基準多面体の内側に存在するため、基準多面体の角は有効判別点の位置まで凹み、角が丸く削り取られることになる。
【００７２】
図６は、基準多面体の角における有効判別点を説明する図である。ここでも判定閾値ｔは０．５であるとする。基準多面体の角付近では、有効判別点は角の内側に存在する。基準多面体の平らな面では有効判別点はその面上に存在する。したがって、基準多面体の平らな面は削られることがないが、角付近では、同図の点線に示すように有効判別点が設けられ、角が丸くなる。
【００７３】
図７（ａ）、（ｂ）は、基準多面体の角付近において近傍球体の半径を変えた場合の有効判別点の位置の変化を説明する図である。図７（ａ）は、近傍球体の半径を小さくした場合であり、有効判別点の位置が角に近づく。図７（ｂ）は、近傍球体の半径を大きくした場合であり、有効判別点の位置が角から遠ざかる。このように、近傍球体の半径を変えることで角の削り取りを変えることができる。
【００７４】
図８（ａ）、（ｂ）は、基準多面体の角付近において占有率の判定閾値を変えた場合の有効判別点の位置の変化を説明する図である。図８（ａ）は、占有率ｐの判定閾値ｔを０．５より小さくした場合であり、基準多面体内部に含まれる近傍球体の体積は半分より小さくてよいため、有効判別点は、点線で示すように、基準多面体の表面２００から外側に離れた位置に移動する。
【００７５】
図８（ｂ）は、占有率ｐの判定閾値ｔを０．５より大きくした場合であり、基準多面体内部に含まれる近傍球体の体積は半分より大きくなる必要があるため、有効判別点は、点線で示すように、基準多面体の表面２００よりも内側に入った位置に移動する。
【００７６】
なお、判定閾値ｔを途中で変化させると段差が生まれるため、原則として判定閾値ｔは一定にする。閾値を変える場合は、閾値移行領域を設け、判定閾値ｔを閾値移行領域において連続的に変化させることが好ましい。
【００７７】
図９は、基準多面体の表面２００の形状の複雑度に応じて、近傍球体の半径を変える様子を説明する図である。鋭く尖った角など複雑で細かな表面形状に対しては、符号２１０ａ、２１０ｂに示すように、近傍球体の半径を小さく設定する。尖った角に対して大きな半径の近傍球体を設定すると、角を削ることができないからである。複雑で細かく造形された表面形状に対しては、その形状の細かさに合わせて近傍球体の半径を十分に小さくする必要がある。近傍球体の半径が小さい場合、角の削られ方が少なくなり、元の多面体形状を良く保存することができるからである。
【００７８】
一方、あまり細かく造形されていない表面形状に対しては、符号２１０ｃに示すように、近傍球体の半径を大きく設定する。大まかな形状に対しては、それに合わせて近傍球体の半径を大きくすることで、表面を大きく削ることができる。
【００７９】
もとの形状をなるべく保存するという立場から、近傍球体の半径は小さめでスタートし、角の丸み具合を見ながら半径を徐々に大きくしながら、基準多面体に対して繰り返し平滑化処理を施すことが好ましい。ここで、角の丸み具合は曲率で評価することができる。
【００８０】
図１０（ａ）〜（ｃ）は、判別点を生成する平面と有効判別点を接続することで得られるポリゴンを説明する図である。
【００８１】
図１０（ａ）、（ｂ）は、ｚ軸に垂直な面すなわちｘｙ平面で基準多面体を切断した様子を示す。実線は基準多面体の表面を示す。基準多面体の表面の近傍で判別点を発生させ、有効判別点を求める。有効判別点により、角が削られた様子が点線で示されている。
【００８２】
図１０（ａ）では、ｚ＝１に固定してｘｙ平面で判別点を発生させ、図１０（ｂ）では、ｚ＝２に固定してｘｙ平面で判別点を発生させる。このため、判別点のｘ座標値、ｙ座標値のみをランダムに生成すればよく、判別点の生成処理が簡略化できる。
【００８３】
図１０（ｃ）に、ｚ＝１で切断したｘｙ平面で求めた有効判別点の集合（符号２５０ａ）、ｚ＝２で切断したｘｙ平面で求めた有効判別点の集合（符号２５０ｂ）、ｚ＝３で切断したｘｙ平面で求めた有効判別点の集合（符号２５０ｃ）を示す。これらの切断面間で有効判別点をつないでいくことで、矩形のポリゴンが生成される様子が示されている。
【００８４】
このように、ｚ座標値を離散的に変えながら、ｘｙ平面で有効判別点を求め、各ｘｙ平面の有効判別点をｚ軸方向につないでいくことでポリゴンが生成され、目標立体の３次元形状データをポリゴンモデルで表現することができる。なお、ポリゴンモデルを生成する際、有効判別点を頂点とするポリゴンを生成する以外に、もとの基準多面体の特徴点をポリゴンの頂点として適宜用いてもよい。
【００８５】
判別点の選び方として、多面体を切り出す前の直方体（ふくらみを考えるならば、それよりもやや大きめの直方体）の内部に一様に乱数を発生させて判別点とすることが一般には考えられるが、これでは計算量が膨大になる。そこで、型紙展開を前提とする場合は、図１０（ａ）〜（ｃ）に示すように、基準多面体を高さ方向や奥行き方向などの一定の方向に等間隔で輪切りして、その輪切りされた切断平面内で判別点を発生させることが計算量の面で有利である。また、高さ方向などの一定方向に所定の間隔を空けて頂点が位置する矩形のポリゴンで３次元形状を表すと、ポリゴンモデルを型紙に展開しやすいという利点もある。
【００８６】
以上、本実施の形態の３次元形状データ生成装置１００によれば、目標とする３次元形状を多面体で与えておき、その形状になるべく沿いながら丸みをもたせることができる。最終的な形状データは、有効判別点の集合として確定するため、隣接する有効判別点を接続していくことでポリゴンメッシュが生成され、最終形態を立体表示して確認したり、型紙データに展開することができる。
【００８７】
３次元形状データ生成装置１００では、ユーザが角の丸み具合などをディスプレイで確認しながら、近傍球体の半径や占有率の判定閾値などのパラメータを調整して平滑化処理を繰り返す行うことで、目標とする３次元形状を作成することができる。ユーザが形状の変形結果を確認しながら、意図する曲面形状を実現していくことができるため、インタラクティブ性の高いシステムを提供することができる。
【００８８】
本実施の形態では、目標とする３次元形状を近似する基準多面体を関数表現で与え、その基準多面体をもとにして平滑化処理を行うため、計算誤差の累積が少ない。したがって、本実施の形態の３次元形状データの生成方法は、工業製品の型紙作成のような正確さが要求される分野に特に有効である。
【００８９】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００９０】
実施の形態では、直方体を平面で切断した基準多面体からスタートして平滑化処理を施し、目標立体を近似するポリゴンモデルを生成したが、平滑化処理を施す基準多面体として、ＣＧにより生成されたポリゴンモデルを用いてもよい。
【図面の簡単な説明】
【００９１】
【図１】３次元形状データ生成装置の構成図である。
【図２】３次元形状データ生成装置による３次元形状データの生成手順の大まかな流れを示すフローチャートである。
【図３】図２で示した平滑化処理の詳細な手順を示すフローチャートである。
【図４】基準多面体の表面近傍に設けられる判別点と近傍球体を説明する図である。
【図５】基準多面体の角の近傍に設けられる判別点と近傍球体を説明する図である。
【図６】基準多面体の角における有効判別点を説明する図である。
【図７】基準多面体の角付近において近傍球体の半径を変えた場合の有効判別点の位置の変化を説明する図である。
【図８】基準多面体の角付近において占有率の判定閾値を変えた場合の有効判別点の位置の変化を説明する図である。
【図９】基準多面体の表面形状の複雑度に応じて、近傍球体の半径を変える様子を説明する図である。
【図１０】判別点を生成する平面と有効判別点を接続することで得られるポリゴンを説明する図である。
【符号の説明】
【００９２】
１０ ソリッドモデル生成部、 １２ 判別点生成部、 １４ 占有率算出部、 １６ 表面曲率算出部、 １８ 球体半径調整部、 ２０ 有効判別点判定部、 ２２ 表面形状変形部、 ２４ 内外判定部、 ２６ 判定閾値調整部、 ２８ ３次元データ生成部、 ３０ 型紙展開部、 ４０ 基準多面体記憶部、 ４２ 内包／外包多面体記憶部、 ４４ 有効判別点記憶部、 ４６ ポリゴン情報記憶部、 ４８ 型紙データ記憶部、 １００ ３次元形状データ生成装置。
【特許請求の範囲】
【請求項１】
目標とする３次元立体の形状を近似した基準多面体の表面形状を平滑化した３次元形状データを生成する方法であって、
前記基準多面体の表面近傍に判別点を生成する判別点生成ステップと、
前記判別点を中心とする所定の半径の近傍球体内に近傍点を乱数により発生させ、前記近傍球体内の前記近傍点が前記基準多面体の内部に含まれる割合を示す占有率を算出する占有率算出ステップと、
前記占有率が所定の判定閾値以上である場合に、前記判別点は前記目標とする３次元立体に含まれると判定し、前記占有率が前記判定閾値より小さい場合に、前記判別点は前記目標とする３次元立体に含まれないと判定する判定ステップと、
前記判定により前記目標とする３次元立体に含まれると判定された前記判別点を頂点とするポリゴンにより、前記目標とする３次元立体を表した３次元形状データを生成する形状データ生成ステップとを含むことを特徴とする３次元形状データ生成方法。
【請求項２】
前記目標とする３次元立体に含まれると判定された判別点により変形された後の前記基準多面体に対して、前記判別点生成ステップ、前記占有率算出ステップ、および前記判定ステップを繰り返すことにより、前記基準多面体の表面形状を段階的に平滑化することを特徴とする請求項１に記載の３次元形状データ生成方法。
【請求項３】
前記占有率算出ステップは、発生する近傍点の数が増えるにしたがって前記占有率が収束する度合いを評価し、前記占有率の収束度合いが所定の水準になった場合に、前記乱数の発生を打ち切ることを特徴とする請求項１または２に記載の３次元形状データ生成方法。
【請求項４】
前記基準多面体の表面の複雑度が増すにしたがって、その表面近傍に設定される前記近傍球体の半径を小さくするステップをさらに含むことを特徴とする請求項１から３のいずれかに記載の３次元形状データ生成方法。
【請求項５】
前記基準多面体の内側に含まれる内包多面体を設け、前記判定により前記目標とする３次元立体に含まれると判定された前記判別点が前記内包多面体の内側にある場合、前記判定閾値を小さくするステップをさらに含むことを特徴とする請求項１から４のいずれかに記載の３次元形状データ生成方法。
【請求項６】
前記基準多面体を内側に含む外包多面体を設け、前記判定により前記目標とする３次元立体に含まれると判定された前記判別点が前記外包多面体の外側にある場合、前記判定閾値を大きくするステップをさらに含むことを特徴とする請求項１から５のいずれかに記載の３次元形状データ生成方法。
【請求項７】
前記判別点生成ステップ、前記占有率算出ステップ、および前記判定ステップを繰り返す過程で前記基準多面体の角の丸みの度合いを曲率で評価し、角の丸み度合いを高めるために前記近傍球体の半径を段階的に大きくすることを特徴とする請求項１から６のいずれかに記載の３次元形状データ生成方法。
【請求項８】
前記基準多面体の各面は平面方程式で表現されており、前記判別点生成ステップは、前記平面方程式で表される平面上の点を検出する手段を用いて、前記基準多面体の表面近傍に前記判別点を生成することを特徴とする請求項１から７のいずれかに記載の３次元形状データ生成方法。
【請求項９】
前記目標とする３次元立体に含まれると判定された判別点により前記基準多面体の表面形状を変形させる変形ステップをさらに含むことを特徴とする請求項１から８のいずれかに記載の３次元形状データ生成方法。
【請求項１０】
目標とする３次元立体の形状を近似した基準多面体の表面形状を平滑化した３次元形状データを生成する装置であって、
前記基準多面体の表面近傍に判別点を生成する判別点生成部と、
前記判別点を中心とする所定の半径の近傍球体内に近傍点を乱数により発生させ、前記近傍球体内の前記近傍点が前記基準多面体の内部に含まれる割合を示す占有率を算出する占有率算出部と、
前記占有率が所定の判定閾値以上である場合に、前記判別点は前記目標とする３次元立体に含まれると判定し、前記占有率が前記判定閾値より小さい場合に、前記判別点は前記目標とする３次元立体に含まれないと判定する有効判別点判定部と、
前記判定により前記目標とする３次元立体に含まれると判定された前記判別点を頂点とするポリゴンにより、前記目標とする３次元立体を表した３次元形状データを生成する３次元データ生成部とを含むことを特徴とする３次元形状データ生成装置。
【請求項１１】
目標とする３次元立体の形状を近似した基準多面体の表面形状を平滑化した３次元形状データを生成する処理をコンピュータに実行させるためのプログラムであって、
前記基準多面体の表面近傍に判別点を生成する判別点生成ステップと、
前記判別点を中心とする所定の半径の近傍球体内に近傍点を乱数により発生させ、前記近傍球体内の前記近傍点が前記基準多面体の内部に含まれる割合を示す占有率を算出する占有率算出ステップと、
前記占有率が所定の判定閾値以上である場合に、前記判別点は前記目標とする３次元立体に含まれると判定し、前記占有率が前記判定閾値より小さい場合に、前記判別点は前記目標とする３次元立体に含まれないと判定する判定ステップと、
前記判定により前記目標とする３次元立体に含まれると判定された前記判別点を頂点とするポリゴンにより、前記目標とする３次元立体を表した３次元形状データを生成するステップとをコンピュータに実行させることを特徴とするプログラム。
【請求項１】
目標とする３次元立体の形状を近似した基準多面体の表面形状を平滑化した３次元形状データを生成する方法であって、
前記基準多面体の表面近傍に判別点を生成する判別点生成ステップと、
前記判別点を中心とする所定の半径の近傍球体内に近傍点を乱数により発生させ、前記近傍球体内の前記近傍点が前記基準多面体の内部に含まれる割合を示す占有率を算出する占有率算出ステップと、
前記占有率が所定の判定閾値以上である場合に、前記判別点は前記目標とする３次元立体に含まれると判定し、前記占有率が前記判定閾値より小さい場合に、前記判別点は前記目標とする３次元立体に含まれないと判定する判定ステップと、
前記判定により前記目標とする３次元立体に含まれると判定された前記判別点を頂点とするポリゴンにより、前記目標とする３次元立体を表した３次元形状データを生成する形状データ生成ステップとを含むことを特徴とする３次元形状データ生成方法。
【請求項２】
前記目標とする３次元立体に含まれると判定された判別点により変形された後の前記基準多面体に対して、前記判別点生成ステップ、前記占有率算出ステップ、および前記判定ステップを繰り返すことにより、前記基準多面体の表面形状を段階的に平滑化することを特徴とする請求項１に記載の３次元形状データ生成方法。
【請求項３】
前記占有率算出ステップは、発生する近傍点の数が増えるにしたがって前記占有率が収束する度合いを評価し、前記占有率の収束度合いが所定の水準になった場合に、前記乱数の発生を打ち切ることを特徴とする請求項１または２に記載の３次元形状データ生成方法。
【請求項４】
前記基準多面体の表面の複雑度が増すにしたがって、その表面近傍に設定される前記近傍球体の半径を小さくするステップをさらに含むことを特徴とする請求項１から３のいずれかに記載の３次元形状データ生成方法。
【請求項５】
前記基準多面体の内側に含まれる内包多面体を設け、前記判定により前記目標とする３次元立体に含まれると判定された前記判別点が前記内包多面体の内側にある場合、前記判定閾値を小さくするステップをさらに含むことを特徴とする請求項１から４のいずれかに記載の３次元形状データ生成方法。
【請求項６】
前記基準多面体を内側に含む外包多面体を設け、前記判定により前記目標とする３次元立体に含まれると判定された前記判別点が前記外包多面体の外側にある場合、前記判定閾値を大きくするステップをさらに含むことを特徴とする請求項１から５のいずれかに記載の３次元形状データ生成方法。
【請求項７】
前記判別点生成ステップ、前記占有率算出ステップ、および前記判定ステップを繰り返す過程で前記基準多面体の角の丸みの度合いを曲率で評価し、角の丸み度合いを高めるために前記近傍球体の半径を段階的に大きくすることを特徴とする請求項１から６のいずれかに記載の３次元形状データ生成方法。
【請求項８】
前記基準多面体の各面は平面方程式で表現されており、前記判別点生成ステップは、前記平面方程式で表される平面上の点を検出する手段を用いて、前記基準多面体の表面近傍に前記判別点を生成することを特徴とする請求項１から７のいずれかに記載の３次元形状データ生成方法。
【請求項９】
前記目標とする３次元立体に含まれると判定された判別点により前記基準多面体の表面形状を変形させる変形ステップをさらに含むことを特徴とする請求項１から８のいずれかに記載の３次元形状データ生成方法。
【請求項１０】
目標とする３次元立体の形状を近似した基準多面体の表面形状を平滑化した３次元形状データを生成する装置であって、
前記基準多面体の表面近傍に判別点を生成する判別点生成部と、
前記判別点を中心とする所定の半径の近傍球体内に近傍点を乱数により発生させ、前記近傍球体内の前記近傍点が前記基準多面体の内部に含まれる割合を示す占有率を算出する占有率算出部と、
前記占有率が所定の判定閾値以上である場合に、前記判別点は前記目標とする３次元立体に含まれると判定し、前記占有率が前記判定閾値より小さい場合に、前記判別点は前記目標とする３次元立体に含まれないと判定する有効判別点判定部と、
前記判定により前記目標とする３次元立体に含まれると判定された前記判別点を頂点とするポリゴンにより、前記目標とする３次元立体を表した３次元形状データを生成する３次元データ生成部とを含むことを特徴とする３次元形状データ生成装置。
【請求項１１】
目標とする３次元立体の形状を近似した基準多面体の表面形状を平滑化した３次元形状データを生成する処理をコンピュータに実行させるためのプログラムであって、
前記基準多面体の表面近傍に判別点を生成する判別点生成ステップと、
前記判別点を中心とする所定の半径の近傍球体内に近傍点を乱数により発生させ、前記近傍球体内の前記近傍点が前記基準多面体の内部に含まれる割合を示す占有率を算出する占有率算出ステップと、
前記占有率が所定の判定閾値以上である場合に、前記判別点は前記目標とする３次元立体に含まれると判定し、前記占有率が前記判定閾値より小さい場合に、前記判別点は前記目標とする３次元立体に含まれないと判定する判定ステップと、
前記判定により前記目標とする３次元立体に含まれると判定された前記判別点を頂点とするポリゴンにより、前記目標とする３次元立体を表した３次元形状データを生成するステップとをコンピュータに実行させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２００７−２０７０２１（Ｐ２００７−２０７０２１Ａ）
【公開日】平成１９年８月１６日（２００７．８．１６）
【国際特許分類】
【出願番号】特願２００６−２５９３９（Ｐ２００６−２５９３９）
【出願日】平成１８年２月２日（２００６．２．２）
【出願人】（５９３１６５４８７）学校法人金沢工業大学 (202)
【Ｆターム（参考）】
【公開日】平成１９年８月１６日（２００７．８．１６）
【国際特許分類】
【出願日】平成１８年２月２日（２００６．２．２）
【出願人】（５９３１６５４８７）学校法人金沢工業大学 (202)
【Ｆターム（参考）】
[ Back to top ]