(57)【要約】      （修正有）【課題】３次元物体モデルの動径関数と動径分布を従来よりも速く求める。【解決手段】３次元物体モデルの動径関数と動径分布を求める方法において、ＣＡＤシステム内で３次元物体モデルを検索し（205）、前記ＣＡＤシステムにより前記物体モデルの表面の任意の点をサンプリングし（210）、前記ＣＡＤシステムにより前記任意点の各々に対応する法線ベクトルを求め（215）、前記ＣＡＤシステムにより各法線ベクトルと各任意点とに対応する動径関数を求め、前記ＣＡＤシステムにより前記動径関数のうちの少なくとも２つに対応する動径分布を求め、該動径分布と前記動径関数の平均値を前記ＣＡＤシステムに記憶する（225）。【選択図】図２
2010079907.tif 000002
【特許請求の範囲】
【請求項１】
３次元物体モデルの動径関数と動径分布を求める方法において、
ＣＡＤシステム内で３次元物体モデルを検索し、
前記ＣＡＤシステムにより前記物体モデルの表面の任意の点をサンプリングし、
前記ＣＡＤシステムにより前記任意点の各々に対応する法線ベクトルを求め、
前記ＣＡＤシステムにより各法線ベクトルと各任意点とに対応する動径関数を求め、
前記ＣＡＤシステムにより前記動径関数のうちの少なくとも２つに対応する動径分布を求め、
該動径分布と前記動径関数の平均値を前記ＣＡＤシステムに記憶する、ことを特徴とする３次元物体モデルの動径関数と動径分布を求める方法。
【請求項２】
さらに、前記動径分布をＣＡＤ物体記述子として前記物体モデルに関連付ける、請求項１記載の方法。
【請求項３】
前記任意点を一様分布を用いてサンプリングする、請求項１記載の方法。
【請求項４】
前記任意点の球面への射影によって前記動径関数を求める、請求項１記載の方法。
【請求項５】
前記動径関数を求める際に、球面上に射影されたサンプリング点の非一様分布に合わせるための補正項を用いる、請求項１記載の方法。
【請求項６】
前記動径関数を３次元空間上の関数と前記３次元物体モデルに関連付ける、請求項１記載の方法。
【請求項７】
原点から予め決められた法線距離内にあるサンプリング点を無視する、請求項１記載の方法。
【請求項８】
前記動径分布を第１の動径関数と第２の動径関数との商として３次元空間および３次元物体モデル上の関数に関連付ける、ここで前記第２の動径関数は３次元空間上の定関数に対応しており、１に等しい、請求項１記載の方法。
【請求項９】
前記物体モデルに対応する前記動径関数と前記動径分布を球面の分割の要素における平均値として前記ＣＡＤシステムに記憶する、請求項１記載の方法。
【請求項１０】
プロセッサとアクセス可能メモリとを含むデータ処理システムであって、
該データ処理システムはＣＡＤシステムを実現しており、
３次元物体モデルを検索するステップ、
前記物体モデルの表面の任意の点をサンプリングするステップ、
前記任意点の各々に対応する法線ベクトルを求めるステップ、
各法線ベクトルと各任意点とに対応する動径関数を求めるステップ、
前記動径関数のうちの少なくとも２つに対応する動径分布を求めるステップ、および
前記動径分布と、前記動径関数の平均値を記憶するステップを実行するように構成されている、ことを特徴とするデータ処理システム。
【請求項１１】
さらに、前記動径関数をＣＡＤ物体記述子として前記物体モデルに関連付けるステップを実行するように構成されている、請求項１０記載のデータ処理システム。
【請求項１２】
前記任意点は一様分布を用いてサンプリングされる、請求項１０記載のデータ処理システム。
【請求項１３】
前記動径関数は前記任意点の球面への射影によって求められる、請求項１０記載のデータ処理システム。
【請求項１４】
前記動径関数を求める際に、球面上に射影されたサンプリング点の非一様分布に合わせるための補正項が用いられる、請求項１０記載のデータ処理システム。
【請求項１５】
前記動径関数は３次元空間上の関数と前記３次元物体モデルとに関連付けられる、請求項１０記載のデータ処理システム。
【請求項１６】
原点から予め決められた法線距離内にあるサンプリング点は無視される、請求項１０記載のデータ処理システム。
【請求項１７】
前記動径分布は第１の動径関数と第２の動径関数との商として３次元空間および３次元物体モデル上の関数に関連付けられ、前記第２の動径関数は３次元空間上の定関数に対応しており、１に等しい、請求項１０記載のデータ処理システム。
【請求項１８】
前記物体モデルに対応する前記動径関数と前記動径分布が球面の分割の要素における平均値として前記ＣＡＤシステムに記憶される、請求項１０記載のデータ処理システム。
【請求項１９】
コンピュータ実行可能な命令が符号化された物理的なコンピュータ可読媒体において、
前記命令が実行時に
３次元物体モデルを検索するステップ、
前記物体モデルの表面の任意の点をサンプリングするステップ、
前記任意点の各々に対応する法線ベクトルを求めるステップ、
各法線ベクトルと各任意点とに対応する動径関数を求めるステップ、
前記動径関数のうちの少なくとも２つに対応する動径分布を求めるステップ、および
前記動径分布と、前記動径関数の平均値を記憶するステップをデータ処理システムに実行させる、ことを特徴とする物理的なコンピュータ可読媒体。
【請求項２０】
実行時に、前記動径分布をＣＡＤ物体記述子として前記物体モデルに関連付けるステップを前記データ処理システムに実行させるコンピュータ実行可能な命令がさらに符号化されている、請求項１９記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００８年９月２５日に提出したアメリカ合衆国特許仮出願第６１／１００，１４３号の優先権を主張するものであり、前記アメリカ合衆国特許仮出願は参照により本願にて援用される。
【０００２】
本開示は、全体的に、コンピュータ支援による設計、製図、製造および視覚化のシステム（個別的、集合的には「ＣＡＤシステム」）に関係している。
【背景技術】
【０００３】
ＣＡＤシステムは２次元（２Ｄ）および３次元（３Ｄ）両方の幾何モデルのデータベースを使用することが多い。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の課題は３次元物体モデルの動径関数と動径分布を従来よりも速く求めることである。
【課題を解決するための手段】
【０００５】
上記課題は、３次元物体モデルの動径関数と動径分布を求める方法において、ＣＡＤシステム内で３次元物体モデルを検索し、前記ＣＡＤシステムにより前記物体モデルの表面の任意の点をサンプリングし、前記ＣＡＤシステムにより前記任意点の各々に対応する法線ベクトルを求め、前記ＣＡＤシステムにより各法線ベクトルと各任意点とに対応する動径関数を求め、前記ＣＡＤシステムにより前記動径関数のうちの少なくとも２つに対応する動径分布を求め、該動径分布と前記動径関数の平均値を前記ＣＡＤシステムに記憶するようにすることで解決される。
【図面の簡単な説明】
【０００６】
【図１】ある実施形態を実現するデータ処理システムのブロック図を示す。
【図２】開示された実施形態に従ったプロセスのフローチャートを示す。
【図３】開示された実施形態に従ったプロセスのフローチャートを示す。
【図４ａ】射影された点の非一様分布を示す。
【図４ｂ】射影された点の非一様分布を示す。
【発明を実施するための形態】
【０００７】
種々の実施形態には、３次元物体モデルの動径関数と動径分布を求めるシステム、方法およびプログラム製品が含まれている。ある１つの方法は、ＣＡＤシステム内で３次元物体モデルを検索し、この物体モデルの表面の任意の点をサンプリングすることを含んでいる。またこの方法には、任意点のそれぞれに対応する法線ベクトルを求め、各法線ベクトルと各任意点とに対応する動径関数を求めることも含まれている。さらにこの方法には、前記動径関数のうちの少なくとも２つに対応する動径分布をＣＡＤシステムにより求め、この動径分布と前記動径関数の平均値をＣＡＤシステムに記憶することも含まれている。
【０００８】
いくつかの実施形態では、動径分布をＣＡＤ物体記述子として物体モデルに付与することも含まれている。様々な実施形態において、任意点は一様分布を用いてサンプリングされ、動径関数は球面への任意点の射影に従って求められる、および／または、動径関数は球面上に射影されたサンプリング点の非一様分布に合わせるための補正項を用いて求められる。様々な実施形態において、動径関数は３次元空間および３次元物体モデル上の関数に対応し、原点から予め選択された法線距離内にあるサンプル点は無視され、動径分布は第１の動径関数と第２の動径関数との商として３次元空間および３次元物体モデル上の関数に対応し、第２の動径関数は３次元空間上の定関数に対応し、ゼロに等しい、および／または、物体モデルに対応する動径関数および動径分布が球面の分割の要素上での平均値としてＣＡＤシステムに記憶される。
【０００９】
上記は、当業者が以下の詳細な説明をより良く理解できるように本開示の技術上の特徴および利点をかなり大雑把に述べたものである。以下では、特許請求の範囲のテーマとなる本開示のその他の特徴および利点を説明する。当業者であれば、開示された着想と特定の実施形態を、変更または本開示と同じ目的を果たす他の構造を設計するための基礎として容易に使用することができるであろう。また、当業者であれば、このような等価物はその最も広い形態においても本開示の趣旨および範囲を超えるものでないことを理解されるであろう。
【実施例】
【００１０】
以下の詳細な説明の前に、本特許文献で使用されるいくつかの用語またはフレーズの定義を示すことが有利であろう。「含む」およびこれから派生した語は限定的でない包含を意味し、「または」という語は包含的、すなわち、および／またはを意味し、「関連した」および「それと関連した」ならびにこれらから派生した語は、含む、中に含まれる、相互に接続されている、〜にまたは〜と結合する、〜と通じている、協働する、交互配置する、並置する、近接している、〜とまたは〜に結び付けられている、有する、〜の性質を有する等を意味し、「コントローラ」という語は、ハードウェア、ファームウェア、ソフトウェア、またはこれらのうちの少なくとも２つの組合せのどれによって実施されていようと、少なくとも１つの動作を制御する任意のデバイス、システムまたはその一部を意味する。何か特定のコントローラに関連した機能は、局所的であれ遠隔的であれ、集中していてもよいし、分散していてもよいことに注意されたい。本特許文献全体を通じていくつかの語およびフレーズの定義が示されるが、当業者であれば、このような定義は、ほとんどではないにしろ、多くの場合、このように定義された語およびフレームの以前の用法および将来の用法にも当てはまることを理解されるであろう。いくつかの語は多様な実施形態を含んでいるが、添付された請求項はこれらの語を特定の実施形態に明示的に限定している。
【００１１】
以下で論じる図１〜４と本特許文献中の本開示の原理の説明に用いられる様々な実施形態は説明のためだけのものであり、本開示の範囲を限定するものと解釈されてはならない。当業者であれば、本開示の原理は適切に構成された任意のデバイスによって実現されることを理解されるであろう。以下では、非限定的な実施例を参照しつつ、本出願の多くの革新的な思想を説明する。
【００１２】
３Ｄモデルをデータベース内で素速く検索するには、これらのモデルを記述子で表すことが必要である。関連する動径関数および動径分布がこのような記述子である。このような記述子は当業者には公知であり、例えば、Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors, M. Kazhdan, T. Funkhouser, Szymon Rusinkiewicz; Eurographics Symposium on Geometry Processing (2003)に記載されている。なお、上記文献は参照により本出願に含まれる。
【００１３】
これらの記述子をスケールと並進の両方に対して不変にすることは一般的であるが、回転不変とすることはもっと難しい。Kazhdan論文には、これらの記述子を回転不変なものに変換する方法が示されている。一般に、この方法のためには、球面上での動径関数または動径分布の値を知らなければならない。多くの場合、球面上のある複数の点における動径関数または動径分布の値を知るだけで十分である。ＣＡＤシステムが球面上の例えばＮ個の点における動径分布の値を知る必要があり、この曲面が例えばＴ個の三角形によって与えられるならば、Ｎ個の値を計算する直接的かつ素朴な方法では、Ｏ（Ｎ×Ｔ）の演算が必要になる（各三角形は原点とＮ個の点の各々によって定まる光線と交差するかテストされる）。開示された実施形態は、この演算数を遥かに速いＯ（Ｎ＋Ｔ＋Ｋ）で置き換えるプロセス、データ処理システムおよびコンピュータプログラム製品を含んでいる。なおここで、ＫはＮおよびＴとは関係のない固定された数である。
【００１４】
図１には、ある実施形態を実現するデータ処理システムの、例えば、本明細書に記載された方法、プロセスおよび機能を実行するよう構成されたある特定のマシーンまたはＣＡＤシステムの、ブロック図が示されている。図示されたデータ処理システムはレベル２キャッシュ／ブリッジ１０４に接続されたプロセッサ１０２を有しており、レベル２キャッシュ／ブリッジ１０４はローカルシステムバス１０６に接続されている。ローカルシステムバス１０６は例えば周辺機器相互接続（ＰＣＩ）アーキテクチャバスであってよい。また、図示の例では、メインメモリ１０８とグラフィックスアダプタ１１０もローカルシステムバス１０６に接続されている。グラフィックスアダプタ１１０はディスプレイ１１１に接続されていてもよい。
【００１５】
ローカルエリアネットワーク（ＬＡＮ）／ワイドエリアネットワーク／ワイヤレス（例えばＷｉＦｉ）アダプタ１１２のような他の周辺機器もローカルシステムバス１０６に接続されていてよい。拡張バスインタフェース１１４はローカルシステムバス１０６を入出力（Ｉ／Ｏ）バス１１６に接続している。Ｉ／Ｏバス１１６はキーボード／マウスアダプタ１１８、ディスクコントローラ１２０およびＩ／Ｏアダプタ１２２に接続されている。ディスクコントローラ１２０はストレージ１２６に接続させてもよい。ストレージ１２６は、読み出し専用メモリ（ＲＯＭ）や電気的にプログラム可能な消去できる読み出し専用メモリ（ＥＥＰＲＯＭ）のような不揮発性のハードコーディングされたタイプの媒体、磁気テープストレージ、および、フロッピーディスク、ハードディスクドライブおよびコンパクトディスク読出し専用メモリ（ＣＤ−ＲＯＭ）やディジタル万能ディスク（ＤＶＤ）のようなユーザ記録可能なタイプの媒体、ならびに他の周知の光学的、電気的または磁気的ストレージデバイスを含むがこれらに限定されない適切なマシーンにより使用可能なまたはマシーン可読な記憶媒体であってよい。
【００１６】
また、図示の例では、オーディオアダプタ１２４もＩ／Ｏバス１１６に接続されている。オーディオアダプタ１２４には、音声再生用にスピーカ（図示なし）を接続してもよい。キーボード／マウスアダプタ１１８は、マウス、トラックボール、トラックポインタなどのようなポインティングデバイス（図示なし）のための接続を提供する。
【００１７】
当業者は図１に示されたハードウェアは個々のケースで変更しうることを理解されるであろう。例えば、光学ディスクドライブなどのような他の周辺デバイスを図示されたハードウェアに加えてまたは代わりに使用してもよい。図示された例は説明目的のためのみに与えられているものであり、本開示に関するアーキテクチャ上の限定を含意するものではない。
【００１８】
本開示の実施形態に従ったデータ処理システムはグラフィカルユーザインタフェースを用いたオペレーティングシステムを含んでいる。このオペレーティングシステムはグラフィカルユーザインタフェースに同時に複数のディスプレイウィンドウを提示することができ、各ディスプレイウィンドウが異なるアプリケーションまたは同一アプリケーションの異なるインスタンスへのインタフェースを提供する。ユーザはポインティングデバイスを通してグラフィカルユーザインタフェース内のカーソルを操作することができる。所望の反応を起こさせるために、カーソルの位置を変えたり、および／または、マウスボタンのクリックのようなイベントを発生させてもよい。
【００１９】
適切に手を加えるならば、様々な商用オペレーティングシステムのうちの１つ、例えばワシントン州レッドモンドにあるマイクロソフト社の製品であるマイクロソフトウィンドウズTMなどを使用してもよい。オペレーティングシステムは本開示に従い記載されている通りに改変または作成される。
【００２０】
ＬＡＮ／ＷＡＮ／ワイヤレスアダプタ１１２はネットワーク１３０（データ処理システム１００の一部ではない）に接続させることができる。なお、ネットワーク１３０は公的もしくは私的なデータ処理システムネットワーク、または、インターネットを含む当業者に知られているネットワークの組合せであってよい。データ処理システム１００はネットワーク１３０を介してサーバシステム１４０と通信することができる。サーバシステム１４０もデータ処理システム１００の一部ではないが、例えば別個のデータ処理システム１００として実施することができる。
【００２１】
ＣＡＤシステムが既存部分を効率良く検索できるようにするためのツールは非常に価値がある。従来、このようなツールはテキストベースであり、複雑な部分を処理する場合または単純に多言語環境で作業する場合にはすぐに限界に達してしまう。
【００２２】
部分それ自体のジオメトリを検索することは可能であるが、これは高度に技術的な解決手段を要する難しい問題である。ここで、１つの問題は、部分のジオメトリはその部分を並進、回転または時にはスケーリングする場合でさえも不変であると見なされなければならないことにある。このような変換は無限に存在するので、並進、回転またはスケーリングの下での可能なすべての変換を考慮することによって２つのジオメトリを比較する効率的なアルゴリズムを設計することは望めない。
【００２３】
上記の問題に対する１つの解決手段は、それ自体並進、回転またはスケーリングの下で不変なジオメトリから記述子を抽出し、これらの記述子を用いてジオメトリにインデックスを付与することである。この解決手段は、ジオメトリから記述子を抽出するオフライン段階と記述子を比較するオンライン段階の２つの段階に作業を効率よく分けるので魅力的である。
【００２４】
３Ｄ形状から記述子を抽出するオフライン段階はかなり遅い演算である。ＵＧＳ  シーメンス製品ライフサイクル管理ソフトウェア社の"Geolus Search"ソフトウェアコンポーネントのような３Ｄジオメトリ検索エンジンを使用できるようにするためには、顧客は所有するあらゆる部分から記述子を抽出しなければならない。数十万以上の部分になることもあるデータベースの場合、これは非常に遅いプロセスとなりうるので、記述子をできる限り速く抽出するようにあらゆる配慮が為されなければならない。特に、本明細書に開示されているような、Ｏ（Ｎ×Ｔ）の計算時間を線形なＯ（Ｎ＋Ｔ＋Ｋ）に換えるプロセスは、非常に有用なツールである。なお、ここでＫは固定値であり、ＮおよびＴに依存しない。
【００２５】
開示された種々の実施形態に従い、
空間はベクトル空間Ｒ3であると定義する。
distをユークリッド距離として定義する。
ノルムをユークリッドノルムとして定義する。
＜，＞をユークリッド内積として定義する。
Ｓ2をＲ3内の単位球面として定義する。
集合σに対し、♯σをその基数と定義する。
【００２６】
分割Ω＝｛ω，ω∈Ｓ2｝をＳ2の互いに素な開部分集合から成る集合として定義する。なお、これら開部分集合の閉包の和集合はＳ2に等しい。
【００２７】
空間内の点ｐに対し、その光線を次のように定義する。
ρ(p)={λρ,λ>ο}
したがって、ｐを通る光線はｐを通り原点を端点とする半直線である。
【００２８】
Ｒ3内の曲面Δが選択されたとしよう。ｆをＲ3上の関数とする。関連する動径関数φfを、あらゆる点ｐに前記曲面と光線ρ（ｐ）の交点におけるｆの値の和を対応付けるＳ2上の関数と定義する。
【数１】
2010079907.tif 000003
【００２９】
Ｒ3内の曲面Δが選択されたと仮定しよう。ｆをＲ3上の関数とする。関連する動径関数をφfとする。φf（ω）をωにおけるφfの平均値と定義する、すなわち、
【数２】
2010079907.tif 000004
ここで、αωはωの面積である。
【００３０】
Ｒ3内の曲面Δが選択されたと仮定しよう。ｆをＲ3上の関数とする。関連する動径分布ψfを、あらゆる点ｐに前記曲面と光線ρ（ｐ）の交点におけるｆの平均値を対応付けるＳ2上の関数と定義する。
【数３】
2010079907.tif 000005
【００３１】
Ｒ3内の曲面Δが選択されたと仮定しよう。ｆをＲ3上の関数とする。関連する動径関数をψfとする。ψf（ω）をωにおけるψfの平均値と定義する、すなわち、
【数４】
2010079907.tif 000006
十分に小さいωについては
【数５】
2010079907.tif 000007
であることに注意されたい。ここで、１は１に等しい定関数を表している。
【００３２】
Ｒ3内の曲面Δ、Ｒ3上の関数ｆおよび球面Ｓ2の分割Ωに関して、開示された実施形態はΩの各要素における関連する動径関数の平均値と動径分布を推定する高速のプロセスを含んでいる。動径関数φfと動径分布ψfを計算するための直接的なアプローチは、球面上の様々な点ｐについて集合
【数６】
2010079907.tif 000008
を見つけることである。Ｎ個の点が存在し、曲面ΔがＴ個の三角形によって与えられるものとすると、Ｏ（Ｎ×Ｔ）の演算が必要となるので、これは遅い。
【００３３】
与えられた光線に関して、この光線と曲面との交点を求めることはコストのかかる演算である。しかし、曲面上の点について、この点を通る光線を求めることはトリビアルな演算である。開示された実施形態はこの事実を利用して関連する動径関数／分布を高速で計算している。
【００３４】
図２には、開示された実施形態に従ったプロセスのフローチャートが示されている。
【００３５】
まず、ＣＡＤシステムがデータベースから３Ｄ物体モデルを検索する（ステップ２０５）。
【００３６】
次に、ＣＡＤシステムは（好ましくは一様分布を用いて）３Ｄ物体モデルの曲面Δ上でＫ個の点｛ｐk，ｋ＝１，．．，Ｋ｝をランダムにサンプリングする（ステップ２１０）。
【００３７】
次に、ＣＡＤシステムはこれらの点においてΔに対する法線ベクトル｛ｖk，ｋ＝１，．．，Ｋ｝を求める（ステップ２１５）。
【００３８】
次に、ＣＡＤシステムは、サンプリングされた点と法線ベクトルを用いて、Ωの中の射影されたそれぞれの弧ωにおける動径関数φfの平均を求める（ステップ２２０）。いくつかの実施形態では、動径関数は球面上の任意の点の射影に従って求められ、球面に射影されたサンプリング点の非一様分布に合わせるために補正項を使用することを含んでいる。
【００３９】
ＣＡＤシステムは、Ω内の各ωにおけるφfの平均を３Ｄ物体モデルに関連した動径分布ψとしてデータベースに格納する（ステップ２２５）。動径関数と動径分布を格納し、データベースで３Ｄ物体モデルを識別するための物体記述子として使用することもできる（ステップ２３０）。動径分布は動径関数φfのうちの少なくとも２つに相当する。動径分布と動径関数の平均値を物体モデルに対応しているＣＡＤシステムに格納してもよい。
【００４０】
いくつかの実施形態では、動径関数は上で求めたような球面上の一連の点における動径関数の値または動径分布に基づいて３Ｄ物体モデルのための回転不変な記述子を計算するために用いてもよい。
【００４１】
以下に、様々なステップをより詳しく説明する。
【００４２】
曲面上の点のサンプリング：曲面上の任意のＫ個の点を探すことは良く知られた問題であり、当業者には周知の解決手段が存在している。曲面がＴ個の三角形で表されるならば、サンプリングはＯ（Ｔ＋Ｋ）の演算で行うことができる。
【００４３】
φfの計算：ＮをΩの基数とする。ｐkが曲面Δ上の点ならば、ｐkにおけるこの曲面に対する法線はｖkで表されることを思い出してもらいたい。
【００４４】
図３には、すべてのφf（ω）を求めるためにＣＡＤシステムが行うプロセスのフローチャートが示されている。
【００４５】
ＣＡＤシステムはまずすべての動径関数φf（ω）をゼロに初期化する（ステップ３０５）。
【００４６】
次に、物体モデルの各部分集合ωについて、ＣＡＤシステムはαωをωの面積に設定する（ステップ３１０）。
【００４７】
次に、ＣＡＤシステムはαΔを選択された曲面の分割Δの面積に設定する（ステップ３１５）。
【００４８】
次に、ＣＡＤシステムはカウンタｋを１にセットする（ステップ３２０）。
【００４９】
次に、ｐkが原点ならば（ステップ３２５）、ＣＡＤシステムは下のステップ３４０へとスキップする。ｐkが原点でなければ（ステップ３２５）、ＣＡＤシステムはρ（ｐk）がωと交差するような射影された弧ωを探す（ステップ３３０）。
【００５０】
次に、ＣＡＤシステムは補正関数
【数７】
2010079907.tif 000009
をφf（ω）に加える（ステップ３３５）。
【００５１】
ＣＡＤシステムはｋをｋ＋１にセットする（ステップ３４０）。
【００５２】
システムは、ｋ＜Ｋであるか否かを調べることにより、すべての点が処理されたか否かを判定する。すべての点が処理されていなければ（ｋ＜Ｋが真ならば）、システムはステップ３２５に戻る。ｋ≧Ｋならば、各ωについて、システムはφf（ω）を
【数８】
2010079907.tif 000010
にセットすることにより、すべての部分集合ωについて動径関数を求め（ステップ３５０）、プロセスは終了する（ステップ３５５）。
【００５３】
上記ステップ３３５は一般に一定の時間内に遂行される。特に、例えばΩが球面の単純なボクセル化である場合にそうである。ステップ３３５を一定時間内に行える場合、上記プロセスはＯ（Ｎ＋Ｋ）の演算しか要さない。
【００５４】
動径分布ψfを計算するには、ωが十分に小さければ、
【数９】
2010079907.tif 000011
であることに留意するだけでよい。
【００５５】
当業者であれば、本明細書に開示されたプロセスの解析的な基礎を理解できるであろう。φf（ω）の正確な値は式１において決められている。いくつかの実施形態では、動径分布は第１の動径関数と第２の動径関数との商として３次元空間および３次元物体モデル上の関数に対応している。ここで、第２の動径関数は３次元空間上の定関数に対応し、１に等しい。この積分はω上のＭ個のランダムに生成された点ｑ1，．．，ｑMにより近似することができ、値
【数１０】
2010079907.tif 000012
をとる。
【００５６】
開示されたプロセスの基礎となるアプローチは、ωにわたる式１の積分を、ωの下でのΔの部分、すなわち原点を頂点としωをその底とする錐とΔとの共通部分にわたる積分で置き換えるというものである。
【００５７】
専門用語で言えば、これは球面上の積分から曲面Δ上の積分へのプルバックである。これを達成するため、このプロセスは、各ωについてω内でランダムに点を選択する代わりに、曲面Δ上の任意の点ｐ1，．．，ｐKを選択し、これらの点の球面Ｓ2への射影を用いる。この射影された点の集合は球面上にランダムに分布してはいない。
【００５８】
いくつかの実施形態では、物体モデルに対応する動径関数と動径分布が球面の分割の要素における平均値としてＣＡＤシステムに記憶される。
【００５９】
図４ａおよび４ｂには、球面４２０上に射影された曲面Δ４１５の点４１０の非ランダム分布４０５が示されている。Δの領域内にある点ｐは、図４ａに示されているように、他の点に比べて分布が疎な領域に射影されている。なお、Δの領域では、Δの法線は原点と点ｐとによって形成された直線と平行である。原点に近い点は、図４ｂに示されているように、他の点に比べて分布が疎な領域に射影されている。
【００６０】
ステップ３３５の補正項
【数１１】
2010079907.tif 000013
とステップ３５０の正規化項
【数１２】
2010079907.tif 000014
の根拠はこれら２つの効果である。
【００６１】
もちろん、当業者であれば、開示された実施形態の範囲内に入る上記プロセスの様々な変更やバリエーションが考えられうることは理解されるであろう。例えば、ｐkが原点に近ければ、上記プロセスのステップ３３５は数値的な不安定性をもたらす可能性がある。
【００６２】
これを補正するためには、原点近傍に「ブラックボックス」効果を加えることが考えられる。より詳しく言えば、εをnorm(pk)が問題を起こしそうな値と定義するのである。そうすれば、ＣＡＤシステムはステップ３０５より前にＬ＝Ｋと設定する（ステップ３０２、図示なし）。ステップ３２５は、ｐkが原点である場合にnorm（ｐk）＜εならば、ステップ３４０へとスキップする前にＬ＝Ｌ−１と設定するように変更される。そして、ステップ３５０は、各ωについて、ＣＡＤシステムが
【数１３】
2010079907.tif 000015
と設定するように変更される。これはεよりも小さな法線を有するすべての点を無視するという効果をもつ。
【００６３】
種々の実施形態には、３次元物体モデルの動径関数と分布を求めるシステム、方法およびプログラム製品が含まれている。ある１つの方法は、ＣＡＤシステム内で３次元物体モデルを検索し、この物体モデルの表面の任意の点をサンプリングすることを含んでいる。またこの方法には、任意点のそれぞれに対応する法線ベクトルを求め、各法線ベクトルと各任意点とに対応する動径関数を求めることも含まれている。また、この方法には、物体モデルに対応する正規分布として動径関数の平均をＣＡＤシステムに記憶することも含まれている。
【００６４】
当業者には気付かれるであろうが、ここでは、簡潔さと明瞭さのために、本開示とともに使用するのに適したすべてのデータ処理システムの完全な構造と動作を図示または説明することはしていない。その代わりに、本開示に特有の、または本開示の理解に必要な部分についてのみ、データ処理システムを図示し、説明している。データ処理システム１００の残りの部分の構造および動作は当業者に知られている現在の様々な実施形態のいずれかに従うものとする。
【００６５】
ここで述べておくべき重要なことは、本開示には完全に機能的なシステムの文脈での説明が含まれているが、当業者であれば、本開示のメカニズムの少なくとも一部は様々な形態のマシン可用、コンピュータ可用またはコンピュータ可読の媒体に収容された命令の形態で配布可能であること、また本開示は実際にこの配布の実行に使用される特定のタイプの命令または信号を担う媒体または記憶媒体に関係なく適用可能であることを理解されるであろうということである。マシン可用／可読またはコンピュータ可用／可読媒体の例としては、読み出し専用メモリ（ＲＯＭ）や電気的にプログラム可能な消去できる読み出し専用メモリ（ＥＥＰＲＯＭ）のような不揮発性のハードコーディングされたタイプの媒体、磁気テープストレージ、および、フロッピーディスク、ハードディスクドライブおよびコンパクトディスク読出し専用メモリ（ＣＤ−ＲＯＭ）やディジタル万能ディスク（ＤＶＤ）のようなユーザ記録可能なタイプの媒体が挙げられる。
【００６６】
本開示の実施例を詳細に説明してきたが、当業者であれば、本明細書に開示された様々な変更、置換、バリエーションおよび改良はその最も広い形態においても本開示の趣旨と範囲を逸脱せずに可能であることを理解されるであろう。
【００６７】
本願における説明を、いずれの特定の要素、ステップまたは機能も請求の範囲に含まれなければならない不可欠の要素であることを含意するものとして理解してはならない。さらに、どの請求項も、"means for"という語の後に分詞が続かないかぎり、３５ＵＳＣ§１１２の第６パラグラフに訴えることを意図するものではない。
【図１】
2010079907.tif 000016
【図２】
2010079907.tif 000017
【図３】
2010079907.tif 000018
【図４ａ】
2010079907.tif 000019
【図４ｂ】
2010079907.tif 000020
【外国語明細書】
2010079907.tif 000021
2010079907.tif 000022
2010079907.tif 000023
2010079907.tif 000024
2010079907.tif 000025
2010079907.tif 000026
2010079907.tif 000027
2010079907.tif 000028
2010079907.tif 000029
2010079907.tif 000030
2010079907.tif 000031
2010079907.tif 000032
2010079907.tif 000033
2010079907.tif 000034
2010079907.tif 000035
2010079907.tif 000036
2010079907.tif 000037
2010079907.tif 000038
2010079907.tif 000039
2010079907.tif 000040
2010079907.tif 000041
2010079907.tif 000042
2010079907.tif 000043
2010079907.tif 000044