(57)【要約】【課題】構造物データの検索に利用可能な点の座標を取得すること。【解決手段】記憶部１ａは、３次元で構造物２を表す複数の多角形の頂点の座標を含む構造物データを記憶する。演算部１ｂは、構造物データを参照して、複数の多角形の空間内での配置に応じて、複数の多角形の頂点とともに構造物データをグラフ化したときの特徴量の計算に用いられる点Ｐ１の座標を算出する。演算部１ｂは、算出した点Ｐ１の座標を構造物データに関連付けて記憶装置に格納する。【選択図】図１
2015194909.tif 000002
【特許請求の範囲】
【請求項１】
３次元で構造物を表す複数の多角形の頂点の座標を含む構造物データを参照して、前記複数の多角形の空間内での配置に応じて、前記複数の多角形の頂点とともに前記構造物データをグラフ化したときの特徴量の計算に用いられる点の座標を算出し、
算出した点の座標を前記構造物データに関連付けて記憶装置に格納する、
処理をコンピュータに実行させる管理プログラム。
【請求項２】
前記算出では、前記複数の多角形の頂点の座標を用いた主成分分析の結果を用いて前記点の座標を算出する、請求項１記載の管理プログラム。
【請求項３】
前記算出では、前記構造物の重心、各多角形の重心および各多角形の法線ベクトルに基づいて前記点の座標を算出する、請求項１記載の管理プログラム。
【請求項４】
前記算出では、空間内の複数の領域における多角形の個数の密度に基づいて前記点の座標を算出する、請求項１記載の管理プログラム。
【請求項５】
前記算出では、構造物データの検索クエリで指定された検索目的に応じて、前記点の座標の算出方法を選択する、請求項１乃至４の何れか１項に記載の管理プログラム。
【請求項６】
前記記憶装置を参照して、前記点および前記構造物の各頂点をノード、前記点と前記構造物の各頂点とを結ぶ辺をエッジとして含み、辺の長さに応じた重みをエッジの重みとするグラフを生成し、前記グラフに基づいて前記特徴量を計算する、請求項１乃至５の何れか１項に記載の管理プログラム。
【請求項７】
３次元で構造物を表す複数の多角形の頂点の座標を含む構造物データを記憶する記憶部と、
前記構造物データを参照して、前記複数の多角形の空間内での配置に応じて、前記複数の多角形の頂点とともに前記構造物データをグラフ化したときの特徴量の計算に用いられる点の座標を算出し、
算出した点の座標を前記構造物データに関連付けて記憶装置に格納する、演算部と、
を有する管理装置。
【請求項８】
コンピュータが、
３次元で構造物を表す複数の多角形の頂点の座標を含む構造物データを参照して、前記複数の多角形の空間内での配置に応じて、前記複数の多角形の頂点とともに前記構造物データをグラフ化したときの特徴量の計算に用いられる点の座標を算出し、
算出した点の座標を前記構造物データに関連付けて記憶装置に格納する、
管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は管理プログラム、管理装置および管理方法に関する。
【背景技術】
【０００２】
現在、３次元モデルの描画を支援するソフトウェアが利用されている。例えば、製図を支援する技術として、ＣＡＤ（Computer Aided Design）がある。ＣＡＤのソフトウェアを実行するコンピュータは、入力デバイスを用いたユーザの入力操作に応じて３次元の構造物を描画し、ディスプレイに表示させる。ユーザは、ディスプレイに描画された内容を視認することで、構造物の立体的なイメージを把握しながら製図を行える。
【０００３】
例えば、コンピュータでは、３次元の座標情報を用いて３次元の形状を表し得る。３次元の形状を表すデータ形式の一例にＳＴＬ（Standard Triangulated Language）がある。ＳＴＬでは、複数の三角形の組合せで３次元モデルの形状を表す。ＳＴＬデータは、１つの三角形に対し、３つの頂点の座標と三角形の面に対する法線ベクトルとの情報を含む。
【０００４】
ところで、ある３次元モデルに対する別の３次元モデルを検索することがある。例えば、製品の設計において、ある部品に類似する形状の部品を設計済であるかを確認して重複設計を抑える場合である。そこで、３次元モデルに対して形状が類似する他の３次元モデルを検索する方法が考えられている。例えば、３次元モデルの形状の特徴を定量化する。特徴を表す量（特徴量）が近似する３次元モデル同士は、形状も類似していると考えられる。複数の種類の特徴量（特徴ベクトル）を用いて検索を行うこともある。
【０００５】
例えば、モデルの重心とモデル面との距離の分布をモデルの形状を表す特徴量とする、または、モデルのクリーズ角（２つの隣接面の法線に対する交差角度）の平均値を特徴量とする提案がある。また、３次元形状のモデルを構成するパッチに対応付けて生成された形状解析木のノードのうち、幾何的な隣接関係にあるノードの間にエッジを生成することにより近傍グラフを生成し、モデル間の形状の差異の検出に用いる提案もある。
【０００６】
更に、複雑な３次元モデルを、スケルトンと呼ばれるより簡単な表現に縮小し、３次元モデルおよびスケルトンとから重要な際立った特徴を抽出して、データベース内に特徴ベクトルとして保存する提案もある。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０００−２２２４２８号公報
【特許文献２】特開２００１−３０７１１１号公報
【特許文献３】特表２００６−５２０９４８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記のように構造物の３次元形状を多角形の組合せとして表すことがある（例えば、ＳＴＬデータ）。この場合、構造物の頂点は多角形の頂点により表され、構造物の２つの頂点を結ぶ辺は多角形の辺により表される。このとき、構造物の頂点をノード、構造物の２つの頂点を結ぶ辺をエッジとして構造物データをグラフ化し、グラフから特徴量を計算して類似の形状の検索に利用することが考えられる。しかし、グラフの情報はエッジ同士の角度の情報を含まないため、凹凸形状の差異を特徴量に反映させにくいという問題がある。また、エッジ同士の角度の情報をグラフの情報に含めることも考えられるが、その情報量は膨大であり、グラフに角度の情報を含めることは難しい。
【０００９】
１つの側面では、本発明は、構造物データの検索に利用可能な点の座標を取得できる管理プログラム、管理装置および管理方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
１つの態様では、コンピュータによって実行される管理プログラムが提供される。この管理プログラムは、コンピュータに、３次元で構造物を表す複数の多角形の頂点の座標を含む構造物データを参照して、複数の多角形の空間内での配置に応じて、複数の多角形の頂点とともに構造物データをグラフ化したときの特徴量の計算に用いられる点の座標を算出し、算出した点の座標を構造物データに関連付けて記憶装置に格納する、処理を実行させる。
【００１１】
また、１つの態様では、管理装置が提供される。この管理装置は、記憶部と演算部とを有する。記憶部は、３次元で構造物を表す複数の多角形の頂点の座標を含む構造物データを記憶する。演算部は、構造物データを参照して、複数の多角形の空間内での配置に応じて、複数の多角形の頂点とともに構造物データをグラフ化したときの特徴量の計算に用いられる点の座標を算出し、算出した点の座標を構造物データに関連付けて記憶装置に格納する。
【００１２】
また、１つの態様では、管理方法が提供される。この管理方法では、コンピュータが、３次元で構造物を表す複数の多角形の頂点の座標を含む構造物データを参照して、複数の多角形の空間内での配置に応じて、複数の多角形の頂点とともに構造物データをグラフ化したときの特徴量の計算に用いられる点の座標を算出し、算出した点の座標を構造物データに関連付けて記憶装置に格納する。
【発明の効果】
【００１３】
１つの側面では、構造物データの検索に利用可能な点の座標を取得できる。
【図面の簡単な説明】
【００１４】
【図１】第１の実施の形態の管理装置を示す図である。
【図２】第２の実施の形態の管理装置のハードウェア例を示す図である。
【図３】第２の実施の形態の構造物およびポリゴンの例を示す図である。
【図４】第２の実施の形態のポリゴンに対するベクトルの例を示す図である。
【図５】第２の実施の形態のグラフ化の例を示す図である。
【図６】第２の実施の形態の管理装置の機能例を示す図である。
【図７】第２の実施の形態のＳＴＬデータの例を示す図である。
【図８】第２の実施の形態の参照点テーブルの例を示す図である。
【図９】第２の実施の形態のグラフデータの例を示す図である。
【図１０】第２の実施の形態の参照点の設定例を示す図である。
【図１１】第２の実施の形態の登録時の処理例を示すフローチャートである。
【図１２】第２の実施の形態の参照点の設定例を示すフローチャートである。
【図１３】第２の実施の形態の検索時の処理例を示すフローチャートである。
【図１４】第２の実施の形態の参照点の設定の他の例を示す図である。
【図１５】第３の実施の形態のポリゴンに対するベクトルの例を示す図である。
【図１６】第３の実施の形態の参照点の設定例を示すフローチャートである。
【図１７】第３の実施の形態の参照点の設定例を示す図である。
【図１８】第４の実施の形態の参照点の設定例を示すフローチャートである。
【図１９】第４の実施の形態の参照点の設定例を示す図である。
【図２０】第５の実施の形態の特徴ベクトルテーブルの例を示す図である。
【図２１】第５の実施の形態の参照点の設定例を示すフローチャートである。
【図２２】第５の実施の形態の参照点の他の設定例を示すフローチャートである。
【図２３】第５の実施の形態の参照点の他の設定例を示す図である。
【発明を実施するための形態】
【００１５】
以下、本実施の形態を図面を参照して説明する。
【００１６】
［第１の実施の形態］
図１は、第１の実施の形態の管理装置を示す図である。管理装置１は、３次元で構造物を表す構造物データを管理する。管理装置１は、ユーザによって指定された構造物データを含む検索クエリを受け付けると、指定された構造物データに対応する構造物と形状の類似する他の構造物を検索する。管理装置１は、構造物データをグラフ化し、グラフから計算された特徴量を構造物データの特徴量（グラフ特徴量ということもある）とする。管理装置１は、特徴量（あるいは、複数の特徴量を含む特徴ベクトル）に基づいて検索を行える。管理装置１は、検索結果を、管理装置１に接続されたディスプレイに表示させたり、ユーザが利用する端末装置に送信したりする。
【００１７】
管理装置１が特徴量を計算するタイミングは２種類ある。第１には、ライブラリ内の構造物データに対して検索用の特徴量を予め付与するときである。第２には、ユーザから指定された検索クエリに含まれる構造物データに対して検索用の特徴量を計算するときである。管理装置１は、後者で求めた特徴量を、前者で求めたライブラリ内の構造物データの特徴量と照合することで、検索クエリで指定された構造物データと形状が類似する他の構造物データを検索できる。以下に示す処理は上記第１，第２の両方の場合に適用できる。
【００１８】
管理装置１は、記憶部１ａおよび演算部１ｂを有する。記憶部１ａは、ＲＡＭ（Random Access Memory）などの揮発性記憶装置でもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性記憶装置でもよい。演算部１ｂは、例えば、プロセッサを含む。プロセッサは、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）でもよいし、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路でもよい。また、プロセッサは、複数のプロセッサの集合（マルチプロセッサ）でもよい。プロセッサは、例えば、記憶部１ａに記憶されたプログラムを実行するものでもよい。
【００１９】
記憶部１ａは、構造物データを記憶する。構造物データは、複数の多角形の組合せにより構造物の３次元での形状を表す。具体的には、構造物表面における曲面を多角形の平面により近似的に表す。ここで、多角形を意味するポリゴン（polygon）という用語を、物体を３次元で表現する際の要素としての多角形を示す用語として用いることもある。例えば、ポリゴンを三角形とするデータ形式としてＳＴＬがある。ただし、四角形や五角形など他の多角形でもよい。
【００２０】
演算部１ｂは、記憶部１ａに記憶された構造物データを参照して、複数の多角形の空間内での配置に応じて、複数の多角形の頂点とともに構造物データをグラフ化したときの特徴量の計算に用いられる点の座標を算出する。演算部１ｂは、算出した点の座標を構造物データに関連付けて記憶装置に格納する。記憶装置は管理装置１に内蔵されていてもよいし、管理装置１の外部に設けられ、管理装置１から（例えば、ネットワークを介して）アクセス可能なものでもよい。当該記憶装置の一部の記憶領域が記憶部１ａでもよい。
【００２１】
例えば、記憶部１ａは、構造物２を示す第１の構造物データおよび構造物３を示す第２の構造物データを記憶する。構造物２は上面（図１の紙面上側の面）に凸部を有する多面体である。構造物３は上面に凹部を有する多面体である。構造物２，３の形状は、複数の多角形により形成される。構造物の頂点は多角形の頂点により表され、構造物の２つの頂点を結ぶ辺は多角形の辺により表される。具体的には、構造物２の１つの頂点は、３以上の多角形により共有される頂点に対応する。構造物２の２つの頂点を結ぶ１つの辺は隣接する２つの多角形により共有される辺に対応する。
【００２２】
演算部１ｂは、第１の構造物データで示される複数の多角形の空間内での配置に応じて、点Ｐ１の座標を算出する。点Ｐ１は、構造物２の頂点とは異なる点である。例えば、点Ｐ１は、構造物２の密度を一定と考えたときの、構造物２の重心でもよい。構造物２の重心は、構造物２を形成する複数の多角形の配置から求まる。演算部１ｂは、算出した点Ｐ１の座標を第１の構造物データ（構造物２のデータ）に関連付けて記憶装置に格納する。
【００２３】
同様に、演算部１ｂは、第２の構造物データで示される複数の多角形の空間内での配置に応じて点Ｐ２（例えば、構造物３の重心）の座標を算出する。演算部１ｂは、算出した点Ｐ２の座標に第２の構造物データ（構造物２のデータ）に関連付けて記憶装置に格納する。
【００２４】
管理装置１によれば、３次元の構造物を表す複数の多角形の頂点の座標を含む構造物データが参照されて、複数の多角形の空間内での配置に応じて複数の多角形の頂点とともに構造物データをグラフ化したときの特徴量の計算に用いられる点の座標が算出される。算出された点の座標が構造物データに関連付けて記憶装置に格納される。これにより、構造物の検索に利用可能な点の座標を取得できる。
【００２５】
例えば、点Ｐ１は、構造物２の頂点とともにノードとして扱われ、構造物２の２つの頂点を結ぶ辺をエッジとして構造物２をグラフ化したときの特徴量の計算に用いられる。グラフ化では、例えば、形状の回転不変性を保つために、ノードに固定の座標をもたせずに、エッジに重みをもたせる（例えば、辺の長さに応じた量をエッジの重みとする）。ノードの重みを一定（例えば、“１”）とする。
【００２６】
例えば、点Ｐ１が構造物２の全ての頂点との間に辺をもつと考えれば、点Ｐ１と構造物２の各頂点との位置関係をグラフに反映させることができる。構造物２の場合、上面の凸型形状を形成する各頂点と点Ｐ１との位置関係の情報をグラフに反映させることができる。図１では構造物２の凸部の頂点を含む面および構造物２の下面（図１の紙面下側の面）の各頂点と点Ｐ１とを結ぶ線分（辺）を表記している。ただし、構造物２の他の頂点と点Ｐ１とを結ぶ線分（辺）を設けてもよい。同様に、構造物３の場合、凹型形状を形成する各頂点と点Ｐ２との位置関係の情報をグラフに反映させることができる。図１では構造物３の凹部の頂点を含む面および構造物３の下面の各頂点と点Ｐ２とを結ぶ線分（辺）を表記している。ただし、構造物３の他の頂点と点Ｐ２とを結ぶ線分（辺）を設けてもよい。
【００２７】
点Ｐ１を考慮して得られる構造物２の第１のグラフは、構造物２の凸型形状の特徴が強く反映された情報となる。点Ｐ２を考慮して得られる構造物３の第２のグラフは、構造物３の凹型形状の特徴が強く反映された情報となる。第１のグラフから所定の演算により求めた特徴量（または、特徴ベクトル）と、第２のグラフから所定の演算により求めた特徴量（または、特徴ベクトル）とを用いれば凹凸形状の差異を適切に区別できる。
【００２８】
なお、点Ｐ１，Ｐ２の座標の決定方法には種々の方法が考えられる。例えば、複数の多角形の空間内での配置の偏りに応じて重心からずらした位置に新たな点を設けてもよい。例えば、構造物２の主成分方向の２次以上のモーメント（積率）に応じた距離だけ重心からずらした位置としてもよい。あるいは、構造物２の内部または外部の空間のうち、局所的に（例えば、所定半径の球内における）多角形の個数密度が大きいと判断される領域を検索し、その領域内に新たな点を設けてもよい。構造物２の比較的平坦な表面では多角形の数の削減が図られていることもあり、多角形の密度が大きい箇所ほど、凹凸形状が際立っていると考えられる。凹凸形状が際立っていると考えられる箇所に新たな点を設けることで、当該箇所の形状の特徴をグラフに反映させることができ、形状の特徴をより顕著に表した特徴量をグラフから求めることができる。
【００２９】
また、回転不変性を保つために、ノードに固定の座標をもたせずに、エッジに重みをもたせる場合、構造物の任意の２ノード間にエッジが存在する完全グラフを生成することも考えられる。しかし、この場合、グラフの情報量が膨大となり、特徴量を計算する演算コストが増大してしまう。この問題は、エッジ同士の角度の情報をグラフに含める場合にも生ずる。一方、管理装置１００は、構造物の頂点とは異なる点を設けて、構造物の形状の特徴をグラフに保持させることで、完全グラフを生成したり、エッジ同士の角度の情報をグラフに含めたりするよりもグラフの情報量を削減でき、特徴量の計算を高速化できる。
【００３０】
［第２の実施の形態］
図２は、第２の実施の形態の管理装置のハードウェア例を示す図である。管理装置１００は、ＣＡＤによる３次元での構造物の設計を支援する。管理装置１００は、ユーザによる操作入力を受け付けると、当該操作入力に応じた３次元の図形を管理装置１００に接続されたディスプレイに表示させる。ユーザは、管理装置１００に対して既存の（設計済の）構造物のデータの検索を依頼できる。
【００３１】
例えば、ユーザは、管理装置１００を用いて、所定の３次元構造を描き、当該構造に類似する他の構造物を管理装置１００に検索させる。管理装置１００は、指定された構造物に形状が類似する他の構造物をライブラリから検索し、ユーザに提示する。ライブラリは、設計済である種々の構造物データを格納したデータベースである。ライブラリは、管理装置１００に内蔵された記憶装置に格納される。ライブラリは、管理装置１００が接続するネットワーク１０に接続された記憶装置に格納されていてもよい。以下の説明では、構造物の形状を示す３次元モデル（多面体）を指して、単に構造物と称することがある。
【００３２】
管理装置１００は、プロセッサ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、読み取り装置１０６および通信インタフェース１０７を有する。各ユニットは管理装置１００のバスに接続されている。
【００３３】
プロセッサ１０１は、管理装置１００の情報処理を制御する。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ、ＤＳＰ、ＡＳＩＣまたはＦＰＧＡなどである。プロセッサ１０１は、ＣＰＵ、ＤＳＰ、ＡＳＩＣ、ＦＰＧＡなどのうちの２以上の要素の組み合わせであってもよい。
【００３４】
ＲＡＭ１０２は、管理装置１００の主記憶装置である。ＲＡＭ１０２は、プロセッサ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部を一時的に記憶する。また、ＲＡＭ１０２は、プロセッサ１０１による処理に用いる各種データを記憶する。
【００３５】
ＨＤＤ１０３は、管理装置１００の補助記憶装置である。ＨＤＤ１０３は、内蔵した磁気ディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。管理装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の補助記憶装置を備えてもよく、複数の補助記憶装置を備えてもよい。
【００３６】
画像信号処理部１０４は、プロセッサ１０１からの命令に従って、管理装置１００に接続されたディスプレイ１１に画像を出力する。ディスプレイ１１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどを用いることができる。
【００３７】
入力信号処理部１０５は、管理装置１００に接続された入力デバイス１２から入力信号を取得し、プロセッサ１０１に出力する。入力デバイス１２としては、例えば、マウス、デジタイザおよびタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。
【００３８】
読み取り装置１０６は、記録媒体１３に記録されたプログラムやデータを読み取る装置である。記録媒体１３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。また、記録媒体１３として、例えば、フラッシュメモリカードなどの不揮発性の半導体メモリを使用することもできる。読み取り装置１０６は、例えば、プロセッサ１０１からの命令に従って、記録媒体１３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
通信インタフェース１０７は、ネットワーク１０を介して他の装置と通信を行う。
【００３９】
図３は、第２の実施の形態の構造物およびポリゴンの例を示す図である。以下の説明では、構造物の形状をＳＴＬ形式の構造物データ（ＳＴＬデータ）により表すことを想定する。ＳＴＬデータで扱うポリゴンは三角形である。ただし、他の多角形のポリゴンでもよい。
【００４０】
図３（Ａ）は構造物の例を示している。構造物５０は直方体である。構造物５０の形状は、構造物５０の表面の複数の三角形で表される。図３（Ａ）の例では、構造物５０の１つの面を２つの三角形で表している。構造物５０の１つの頂点は、３つの三角形の頂点に対応する。構造物５０の２つの頂点を結ぶ１つの辺は、２つの三角形の辺に対応する。
【００４１】
図３（Ｂ）はポリゴンの例を示している。ポリゴン５１は、三角形の３つの頂点Ｋ１，Ｋ２，Ｋ３の座標およびポリゴン５１の表側の表面に対する法線ベクトルｒの情報を含む。法線ベクトルｒの長さは単位長さでもよい。座標および法線ベクトルは、直交するｘ，ｙ，ｚの３軸に対する座標値を用いて表される。
【００４２】
なお、ポリゴン５１の表裏は、ＳＴＬデータにおける３つの頂点Ｋ１，Ｋ２，Ｋ３の座標の定義の順番により区別することもできる。頂点Ｋ１，Ｋ２，Ｋ３はポリゴン５１の表側から見たときに、１つ目の頂点から反時計周りに２つ目の頂点、３つ目の頂点と順番に定義される。以下の説明では、ポリゴンという場合、三角形を示すものとする。
【００４３】
図４は、第２の実施の形態のポリゴンに関するベクトルの例を示す図である。構造物の形状はＮ（Ｎは４以上の整数）個のポリゴンにより表される。例えば、ｉ（ｉは１≦ｉ≦Ｎの整数）個目のポリゴンに関する種々の位置ベクトルを次のように定義する。
【００４４】
ベクトルｐ1，ｐ2，ｐ3は、原点Ｏを起点としたｉ番目のポリゴンの３つの頂点を示すベクトルである。ここで、ベクトルｐ1，ｐ2，ｐ3は各ポリゴンによって異なるセットとなるが、ｉの添え字を省略する。
ベクトルηiは、原点Ｏおよびｉ番目のポリゴンの３つの頂点によって形成される四面体の重心を示すベクトルである。
【００４５】
図５は、第２の実施の形態のグラフ化の例を示す図である。構造物５０の８つの頂点をノードとし、２つの頂点を結ぶ１つの辺をエッジとして構造物５０をグラフ化すると、グラフ６０を得る。一方、管理装置１００は、構造物５０の８つの頂点に、特徴量の計算に用いる１つ以上の点Ｐ（参照点という）を設ける。図５では、一例として、構造物５０の８つの頂点と参照点Ｐとを結ぶ８つの辺を加えてグラフ化したグラフ６０ａも図示している。グラフ６０ａは、参照点Ｐに対応するノードを含む。また、グラフ６０ａは、参照点Ｐに対応するノードと他のノードとの間の８つのエッジを含む。
【００４６】
図６は、第２の実施の形態の管理装置の機能例を示す図である。管理装置１００は、記憶部１１０、参照点設定部１２０、グラフ合成処理部１３０、特徴量計算部１４０および検索部１５０を有する。参照点設定部１２０、グラフ合成処理部１３０、特徴量計算部１４０および検索部１５０は、プロセッサ１０１によって実行されるプログラムのモジュールであってもよい。
【００４７】
記憶部１１０は、各部の処理に用いられる情報を記憶する。記憶部１１０が記憶する情報は、ＳＴＬデータ、参照点テーブル、グラフデータおよび特徴ベクトルテーブルを含む。ＳＴＬデータは、構造物の形状を示す構造物データである。ＳＴＬデータは、作図された構造物毎に記憶部１１０に複数格納される。記憶部１１０に記憶された複数のＳＴＬデータ（ＳＴＬデータ群）を指して、ライブラリと称することもある。参照点テーブルは、構造物毎の参照点の座標を管理するための情報である。グラフデータは、構造物データおよび参照点から生成されたグラフを表すデータである。特徴ベクトルテーブルは、構造物に対してグラフデータから計算された特徴ベクトルを管理するための情報である。ただし、ネットワーク１０を介して管理装置１００からアクセス可能な記憶装置がある場合、記憶部１１０に記憶されるこれらの情報を当該記憶装置に格納してもよい。
【００４８】
参照点設定部１２０は、ＳＴＬデータに含まれる複数のポリゴンの情報に基づいて、参照点の座標を算出する（ＳＴＬデータに対して参照点を設定するともいえる）。第２の実施の形態では、参照点設定部１２０は、ＳＴＬデータに含まれる複数のポリゴンについて主成分分析を行い、ＳＴＬデータから求まる構造物の重心と重心に対する主成分方向の２次以上のモーメントとに基づいて参照点の座標を算出する。参照点設定部１２０は、算出した参照点の座標をＳＴＬデータに対応付けて、参照点テーブルに登録する。
【００４９】
グラフ合成処理部１３０は、構造物のＳＴＬデータと参照点テーブルに登録された当該構造物に対する参照点の座標とに基づいて、グラフデータを生成する。例えば、図５で例示したように、グラフデータは、参照点に対応するノードを含む。また、グラフデータは、構造物の各頂点と参照点とを結ぶ辺に対応するエッジを含む。
【００５０】
特徴量計算部１４０は、グラフデータに基づく所定の演算により、構造物の形状の特徴を表す特徴量を計算する。グラフの特徴量の計算方法としては、既存の方法を利用できる。特徴量計算部１４０は、複数の種類の演算を行うことで、１つの構造物に対して複数の種類の特徴量を計算する。特徴量計算部１４０は、複数の種類の特徴量のセットを、当該構造物に対する特徴ベクトルとする。特徴量計算部１４０は、当該構造物のＳＴＬデータに対応付けて特徴ベクトルを特徴ベクトルテーブルに登録する。
【００５１】
検索部１５０は、構造物の検索クエリを受け付ける。例えば、ユーザは、入力デバイス１２を操作して、所定の検索クエリを管理装置１００に入力できる。また、検索部１５０は、ネットワーク１０を介して接続された他の情報処理装置から検索クエリを受け付けてもよい。検索クエリは、ユーザにより指定された構造物の形状を示すＳＴＬデータを含む。検索部１５０は、参照点設定部１２０、グラフ合成処理部１３０および特徴量計算部１４０を用いて検索クエリのＳＴＬデータに対する特徴ベクトルを求める。検索部１５０は、求めた特徴ベクトルと、記憶部１１０に記憶された特徴ベクトルテーブルとを照合して、ユーザにより指定された形状に類似する形状をもつ構造物を検索する。検索部１５０は、検索結果をディスプレイ１１に表示させるなどして、ユーザに提示する。
【００５２】
図７は、第２の実施の形態のＳＴＬデータの例を示す図である。ＳＴＬデータ１１１は、次のようなフォーマットである。なお、ＳＴＬデータ１１１の左側に付した番号は行番号である。“ｓｏｌｉｄ”の文字列の後には、構造物の識別情報（例えば、“構造物Ａ”）が設定される（１行目）。
【００５３】
“ｆａｃｅｔ  ｎｏｒｍａｌ”の文字列の後には、法線ベクトルの成分が設定される（２行目）。“ｆａｃｅｔ  ｎｏｒｍａｌ”の行（２行目）から“ｅｎｄｆａｃｅｔ”の行（８行目）までが１つのポリゴンの情報に相当する。“ｖｅｒｔｅｘ”の文字列の後には、ポリゴンの頂点の座標が設定される。三角形のポリゴンを考えているから、１つのポリゴンに対し、“ｖｅｒｔｅｘ”の文字列を用いて３つの頂点の座標が設定されることになる。
【００５４】
また、ＳＴＬデータ１１１によれば、法線ベクトルでもポリゴンの表裏を区別できるし、ポリゴンの頂点の座標の設定順によってもポリゴンの表裏を区別できる。同様にして、９行目以降に他のポリゴンが順次定められる。ＳＴＬデータ１１１の末尾行は“ｅｎｄｓｏｌｉｄ”の文字列が設定される（１５行目）。
【００５５】
図８は、第２の実施の形態の参照点テーブルの例を示す図である。参照点テーブル１１２は、構造物および参照点の項目を含む。構造物の項目には、構造物の識別情報が登録される。参照点の項目には、参照点の座標が登録される。
【００５６】
例えば、参照点テーブル１１２には、構造物の識別情報“構造物Ａ”に対して、参照点“Ｐ１，・・・”という情報が登録される。１つのＳＴＬデータに対して設定される参照点の数は１つでもよいし複数でもよい。
【００５７】
図９は、第２の実施の形態のグラフデータの例を示す図である。ここでは、グラフデータ１１３をＧｒａｐｈＭＬ形式と呼ばれるフォーマットで表すことを想定する。ＧｒａｐｈＭＬでは、ＸＭＬ（eXtensible Markup Language）の記法を用いてノードおよびエッジを記述する。ただし、他の形式のフォーマットとしてもよい。また、無向グラフを想定するが有向グラフとしてもよい。後述するように、有向グラフとすることで、形状の特徴をグラフにより顕著に反映させ得るからである。なお、グラフデータ１１３の左側に付した番号は行番号である。
【００５８】
例えば、３行目の記述は、エッジに対するキー“ｋｅｙ０”を定義している。ｋｅｙ  ｉｄ“ｋｅｙ０”のタグにより、エッジの重み（“ｗｅｉｇｈｔ”）に相当する属性をエッジに付与する。例えば、エッジの重みは、エッジに対応する辺の長さである。
【００５９】
４行目の記述は、ノードに対するキー“ｋｅｙ１”を定義している。ｋｅｙ  ｉｄ“ｋｅｙ１”のタグによりノードを定義し、“ｉｓＳａｎｓｙｏｕ”フラグにより、当該ノードが参照点に対応するものであるか否かを定める。“ｉｓＳａｎｓｙｏｕ”フラグが“ｔｒｕｅ”であれば、当該ノードは参照点に対応するノードである。“ｉｓＳａｎｓｙｏｕ”フラグが“ｆａｌｓｅ”であれば、当該ノードは参照点に対応するノードではない。
【００６０】
グラフデータ１１３の例では、ノードＩＤ“ｎ０”のノード（７行目〜９行目）およびノードＩＤ“ｎ５”のノード（１１行目〜１３行目）は、参照点に対応するものではない。それぞれのノードの“ｋｅｙ１”で指定される“ｉｓＳａｎｓｙｏｕ”フラグが“ｆａｌｓｅ”だからである。ノードＩＤ“ｎ６”のノード（１４行目〜１６行目）は、参照点に対応するものである。ノードＩＤ“ｎ６”のノードの“ｉｓＳａｎｓｙｏｕ”フラグが“ｔｒｕｅ”だからである。
【００６１】
また、エッジについては、エッジｉｄ“ｅ０”のエッジは、ノードｉｄ“ｎ１”のノードとノードｉｄ“ｎ０”のノードとを結ぶエッジであり、重みは“１．５”である（１７行目〜１９行目）。他のエッジも同様に表される。
【００６２】
特に、エッジｉｄ“ｅ８”のエッジは、ノードｉｄ“ｎ６”のノードとノードｉｄ“ｎ５”のノードとを結ぶエッジであり、重みは“１４”である（２７行目〜２９行目）。前述のように、ノードｉｄ“ｎ６”は、参照点に対応するものである。したがって、エッジｉｄ“ｅ８”のエッジは、構造物の頂点と参照点とを結ぶ辺に対応するエッジである。
【００６３】
図１０は、第２の実施の形態の参照点の設定例を示す図である。図１０（Ａ）は、構造物７０の重心を参照点Ｐ１として設定した場合を例示している。図１０（Ｂ）は、構造物７０の重心と重心に対する主成分方向の２次モーメントとに基づいて参照点Ｐ１，Ｐ２，Ｐ３を設定した場合を例示している。
【００６４】
具体的には、図１０（Ａ）と同様に、重心が参照点Ｐ１である。主成分方向の２次モーメントの平均値（分散）の２乗根（標準偏差σ）の分だけ重心から主成分方向にずらした点に参照点を設定する。構造物７０の主成分方向の単位ベクトルをベクトルｈとすれば、重心（参照点Ｐ１）の座標μに対し、μ＋σｈで示される座標を参照点Ｐ２、μ−σｈで示される座標を参照点Ｐ３とする。
【００６５】
すると、重心に参照点Ｐ１を１つ設ける場合に比べて、構造物７０の端側の構造をより詳細にグラフに反映させることができる。すなわち、グラフは当該構造をより顕著に表した情報となる。具体的には、主成分方向は構造物が特に広がっている方向である。中でも第１主成分方向の広がりは、第２、第３主成分方向に比べて大きい。例えば、図１０（Ａ）のように、重心に参照点Ｐ１を設けるのみとすると、参照点Ｐ１に対して、主成分方向に広がっている構造物７０の端点の立体角が小さくなる。このため、構造物７０の端点の情報（参照点Ｐ１と各端点とを結ぶ辺の長さ）に差異が現れにくくなり、構造物７０の端点の差異に鈍感になる恐れがある。
【００６６】
そこで、主成分方向の標準偏差を、構造物の主成分方向の広がりと考え、重心から±σｈの座標に参照点を設定する。これにより、構造物７０の参照点Ｐ２側の各端点と参照点Ｐ２とを結ぶ辺の長さの差異が参照点Ｐ１のみを用いる場合よりも明瞭になる。同様に、構造物７０の参照点Ｐ３側の各端点と参照点Ｐ３とを結ぶ辺の長さの差異が参照点Ｐ１のみを用いる場合よりも明瞭になる。このため、構造物７０の形状の特徴をより詳細にグラフに反映させることができる。
【００６７】
次に、第２の実施の形態の処理手順を説明する。まず、既存の構造物のＳＴＬデータに対する特徴ベクトルを予め算出して、記憶部１１０に登録する処理について説明する。
図１１は、第２の実施の形態の登録時の処理例を示すフローチャートである。以下、図１１に示す処理をステップ番号に沿って説明する。
【００６８】
（Ｓ１１）参照点設定部１２０は、記憶部１１０に記憶されたＳＴＬデータ１１１を読み出す。なお、記憶部１１０には複数のＳＴＬデータが予め登録され得る。ステップＳ１１〜Ｓ１５の処理は、ＳＴＬデータの分だけ繰り返される。
【００６９】
（Ｓ１２）参照点設定部１２０は、ＳＴＬデータ１１１を参照し、構造物を形成する複数のポリゴンの空間内での配置に応じて参照点の座標を算出する。参照点設定部１２０は、ＳＴＬデータ１１１に関連付けて参照点の座標を参照点テーブル１１２に登録する。処理の詳細については後述する。
【００７０】
（Ｓ１３）グラフ合成処理部１３０は、ＳＴＬデータ１１１およびステップＳ１２で設定された参照点の座標に基づいて、構造物のグラフ化を実行し、グラフデータ１１３を生成し、記憶部１１０に格納する。
【００７１】
（Ｓ１４）特徴量計算部１４０は、グラフデータ１１３を用いた所定の演算により、構造物に対する特徴量を計算する。特徴量計算部１４０は、複数の種類の演算により、複数の種類の特徴量を計算することで、構造物に対する特徴ベクトルを計算する。
（Ｓ１５）特徴量計算部１４０は、ＳＴＬデータ１１１に関連付けて特徴ベクトルを記憶部１１０に格納する。
【００７２】
図１２は、第２の実施の形態の参照点の設定例を示すフローチャートである。以下、図１２に示す処理をステップ番号に沿って説明する。以下に示す処理は、図１１のステップＳ１２の処理に相当する。なお、以下の説明において、ベクトルまたは行列をボールド表記で表す。また、転置を示す添え字Ｔが付されていないベクトルは３行１列の列ベクトルである。添え字Ｔが付されているベクトルは１行３列の行ベクトルである。参照点設定部１２０は、参照点の設定に、主成分分析の手法を用いる。
【００７３】
（Ｓ２１）参照点設定部１２０は、ＳＴＬデータ１１１から構造物の重心の座標μを計算する。具体的には、ｉ番目のポリゴンの３つの頂点と原点Ｏとを頂点とする四面体の符号付きの体積Ｖiは、式（１）で表せる。
【００７４】
【数１】
2015194909.tif 000003
【００７５】
ポリゴンの数はＮ個だから、構造物の全体積Ｖは式（２）で表せる。
【００７６】
【数２】
2015194909.tif 000004
【００７７】
また、ポリゴンの３つの頂点が原点Ｏを基準とした位置ベクトルで表されているとき、ｉ番目のポリゴンの３つの頂点と原点Ｏとを頂点とする四面体の重心の座標ηiは、式（３）で表せる。ただし、構造物の密度は一定であるとする。
【００７８】
【数３】
2015194909.tif 000005
【００７９】
よって、構造物の重心の座標μは、式（４）により求まる。
【００８０】
【数４】
2015194909.tif 000006
【００８１】
（Ｓ２２）参照点設定部１２０は、重心の座標μに関する２次モーメント行列Ｃ（共分散行列ということもある）を計算する。２次モーメント行列Ｃは３行３列の対称行列である。ここでは、複数のポリゴンの頂点の空間内の偏りを示す２次モーメント行列Ｃを求める。ただし、複数のポリゴンの重心（各ポリゴンの頂点の座標から求まる）の空間内の偏りを示す２次モーメント行列を求めてもよい。何れの方法を用いても、複数のポリゴンの空間内の偏りを評価できる。２次モーメント行列Ｃは、式（５）で表せる。
【００８２】
【数５】
2015194909.tif 000007
【００８３】
ここで、ｎはＳＴＬデータ１１１に含まれるポリゴンの頂点の総数である。ベクトルｐjは、総数ｎのポリゴンの頂点のうち、ｊ番目の頂点の位置ベクトルである。２次モーメント行列Ｃの全成分は、ベクトルｐjT＝（ｘj，ｙj，ｚj）、ベクトルμT＝（μx，μy，μz）として、式（６）で表せる。
【００８４】
【数６】
2015194909.tif 000008
【００８５】
（Ｓ２３）参照点設定部１２０は、２次モーメント行列Ｃを対角化することで、３軸で無相関となる新たな直交座標系における２次モーメント行列を求める。座標変換用の行列を行列Ｘとすれば、新たな２次モーメント行列ＸＣＸTは、式（７）で表せる。
【００８６】
【数７】
2015194909.tif 000009
【００８７】
ここで、λ1，λ2，λ3（λ1≧λ2≧λ3）は、２次モーメント行列Ｃの固有値である。λ1，λ2，λ3それぞれに対応する２次モーメント行列Ｃの固有ベクトルは、構造物の主成分方向を示す単位長さのベクトルである。そのうち、λ1に対する固有ベクトル（偏りの度合いの最大の軸方向）は第１主成分の方向を示す。λ2に対する固有ベクトルは第２主成分の方向を示す。λ3に対する固有ベクトルは第３主成分の方向を示す。λ1，λ2，λ3は、３次の固有方程式（８）の解である（行列Ｉは単位行列である）。
【００８８】
【数８】
2015194909.tif 000010
【００８９】
このとき、第１主成分方向の標準偏差は式（９）により求まる。また、第１主成分方向を示す単位固有ベクトルｈのｘ，ｙ，ｚ成分は、３元連立１次方程式（１０）の解として求まる。
【００９０】
【数９】
2015194909.tif 000011
【００９１】
【数１０】
2015194909.tif 000012
【００９２】
（Ｓ２４）参照点設定部１２０は、μ−σｈ，μ，μ＋σｈで示される座標を参照点の座標と決定する。参照点設定部１２０は、算出した参照点をＳＴＬデータ１１１に関連付けて、参照点テーブル１１２に登録する。
このようにして、管理装置１００は、参照点を設定する。なお、図１２の例では、主に第１主成分方向を例示したが、第２、第３主成分方向に対しても同様に参照点を設定できる。
【００９３】
図１３は、第２の実施の形態の検索時の処理例を示すフローチャートである。以下、図１３に示す処理をステップ番号に沿って説明する。
【００９４】
（Ｓ３１）検索部１５０は、検索クエリを受け付ける。検索クエリは、ユーザによって指定された構造物のＳＴＬデータを含む。例えば、前述のように検索クエリは、ユーザにより管理装置１００に直接入力されてもよいし、ネットワーク１０を介して他の装置から入力されてもよい。
【００９５】
（Ｓ３２）参照点設定部１２０は、検索クエリに含まれるＳＴＬデータに基づいて、参照点を設定する。設定の手順は、図１２の手順と同様である。
【００９６】
（Ｓ３３）グラフ合成処理部１３０は、検索クエリに含まれるＳＴＬデータおよびステップＳ３２で設定された参照点の座標に基づいて、検索クエリの構造物のグラフ化を実行し、当該構造物に対するグラフデータを生成する。
【００９７】
（Ｓ３４）特徴量計算部１４０は、ステップＳ３３で生成したグラフデータを用いた所定の演算により、検索クエリに含まれる構造物に対する特徴量を計算する。特徴量計算部１４０は、複数の種類の演算により、複数の種類の特徴量を計算することで、構造物に対する特徴ベクトルを計算する。
【００９８】
（Ｓ３５）検索部１５０は、ステップＳ３４で計算された特徴ベクトルと、設計済の構造物に対して記憶部１１０に登録済の特徴ベクトルとを照合して、設計済の構造物の中から、検索クエリの構造物に形状が類似するものを検索する。
【００９９】
（Ｓ３６）検索部１５０は、検索結果を出力する。例えば、検索部１５０は、ディスプレイ１１に検索結果を表示させる。または、検索部１５０は、ネットワーク１０を介して、検索クエリの送信元の装置に検索結果を送信する。
【０１００】
図１４は、第２の実施の形態の参照点の設定の他の例を示す図である。図１３までは、主に２次モーメントに基づいて参照点を設定する例を説明したが、３次以上（３次、４次、５次、・・・）のモーメントに基づいて参照点を設定してもよい。なお、２次以上のモーメントを指して高次モーメントということもある。
【０１０１】
例えば、第１主成分方向の軸をｘ’軸とし、ｘ’軸における重心μのｘ’座標に関するｋ（ｋは２以上の整数）次のモーメントの平均λ’を式（１１）により算出する。そして、式（１２）によりλ’に対応するσkを算出する。
【０１０２】
【数１１】
2015194909.tif 000013
【０１０３】
【数１２】
2015194909.tif 000014
【０１０４】
図１２のステップＳ２４において、μ−σkｈ，μ＋σkｈを参照点に設定する。μ−σｈ，μ＋σｈの参照点とともに、μ−σkｈ，μ＋σkｈを追加して設定してもよい。μ−σｈ，μ＋σｈの参照点に代えて、μ−σkｈ，μ＋σkｈを設定してもよい。第１主成分方向について説明したが、第２，第３主成分に対しても、同様にして参照点を設定してもよい。例えば、より高い次数のモーメントを用いることで、図１４に示す構造物８０のように、第１主成分方向の構造物８０の端部にポリゴンが偏在している場合に、参照点をより端部側に設けることができ、形状の特徴をより詳細にグラフに反映できる。
【０１０５】
このように、管理装置１００は、構造物８０の重心と構造物を形成する複数のポリゴンの主成分方向の配置のばらつきにより参照点を設定する。これにより、構造物８０の形状の特徴をより詳細にグラフに反映させることができる。
【０１０６】
なお、第２の実施の形態では、特徴量の計算に用いるグラフとして無向グラフを想定したが、有向グラフとしてもよい。例えば、構造物の頂点と参照点とを結ぶ辺に対応するエッジに対して向きを設定することで、構造物の当該頂点が構造物の外側に凸の形状の先端であるか、構造物の内側に凸の形状の先端であるかを識別可能とすることが考えられる。
【０１０７】
具体的には、構造物の重心μと構造物の頂点を含む複数のポリゴンの各法線ベクトルとの内積をとり、各内積値のうち正の内積値の数が負の内積値の数以上あれば、当該頂点を外側に凸の形状の先端であるとする。他方、正の内積値の数が負の内積値の数よりも少なければ、当該頂点を内側に凸の形状の先端であるとする。外側に凸の形状であれば、例えば参照点を始点、当該先端の頂点を終点とする向きをエッジに付与する。一方、内側に凸の形状であれば、当該先端の頂点を始点、参照点を終点とする向きをエッジに付与する。
このように、構造物の表面の凹凸形状をより詳細にグラフに反映して、特徴量を計算することも考えられる。
【０１０８】
［第３の実施の形態］
以下、第３の実施の形態を説明する。前述の第２の実施の形態と相違する事項を主に説明し、共通する事項の説明を省略する。第３の実施の形態では、第２の実施の形態で算出した重心の座標をずらすことで、参照点を設定する点が、第２の実施の形態と異なる。
【０１０９】
ここで、第３の実施の形態の管理装置のハードウェア例およびソフトウェア例は、第２の実施の形態の管理装置１００のハードウェア例およびソフトウェア例と同様である。そこで、第３の実施の形態でも第２の実施の形態と同じ符号・名称を用いて各要素を指し示す。
【０１１０】
図１５は、第３の実施の形態のポリゴンに対するベクトルの例を示す図である。重心Ｒiは、構造物を形成するｉ番目のポリゴンの重心である。重心Ｒiの座標は、ポリゴンの３つの頂点に対する位置ベクトルの和を３で割ることで求まる。ベクトルｑiは、構造物の重心μを始点とし、ｉ番目のポリゴンの重心Ｒiを終点とするベクトル（Ｒi−μ）である。
【０１１１】
図１６は、第３の実施の形態の参照点の設定例を示すフローチャートである。以下、図１６に示す処理をステップ番号に沿って説明する。以下の手順は、図１１のステップＳ１２および図１３のステップＳ３２に相当する。
（Ｓ４１）参照点設定部１２０は、ＳＴＬデータ１１１から構造物の重心の座標μを計算する。計算方法は、図１２のステップＳ２１と同様である。
【０１１２】
（Ｓ４２）参照点設定部１２０は、重心μからｉ番目のポリゴン（ポリゴンｉ）の重心Ｒiへ向かうベクトルｑiを計算する。参照点設定部１２０は、構造物を形成する全てのポリゴンについて、ベクトルｑiを計算する。
【０１１３】
（Ｓ４３）参照点設定部１２０は、ベクトルｑiとポリゴンｉの法線ベクトルｒiとの内積ｍiを計算する。内積ｍiは式（１３）で表せる。
【０１１４】
【数１３】
2015194909.tif 000015
【０１１５】
（Ｓ４４）参照点設定部１２０は、ポリゴンｉの重心Ｒiに内積ｍiを割り当てる。
【０１１６】
（Ｓ４５）参照点設定部１２０は、ポリゴンｉの重心Ｒiに割り当てられた内積ｍiを質量とみなしたときの構造物の重心の座標νを算出する。ここで、νの計算において、構造物の内部は中空であるとみなす（すなわち、構造物の表面を張るポリゴンｉの重心Ｒiのみが質量をもつとみなす）。このとき、構造物の質量は式（１４）で表せる。
【０１１７】
【数１４】
2015194909.tif 000016
【０１１８】
よって、構造物の重心の座標νは式（１５）で表せる。
【０１１９】
【数１５】
2015194909.tif 000017
【０１２０】
座標νは、内積ｍiの３次元空間内での分布を反映した座標であるといえる。内積ｍiは、ポリゴンｉの重心に割り当てられる。このため、内積ｍiの分布は、複数のポリゴンの空間内での配置に応じて決まる。
【０１２１】
（Ｓ４６）参照点設定部１２０は、ステップＳ４５で算出した重心の座標νを参照点の座標と決定する。参照点設定部１２０は、参照点の座標をＳＴＬデータ１１１に関連付けて、参照点テーブル１１２に登録する。
【０１２２】
図１７は、第３の実施の形態の参照点の設定例を示す図である。第３の実施の形態では、ポリゴンの重心に対して内積ｍiを与え、当該内積に基づいて構造物の重心μ（第２の実施の形態の参照点Ｐ１に相当）をずらした重心νを求める。このようにすると、ポリゴンの面積の大小は関係なく、ポリゴンの数の比較的多い領域が大きな内積をもつことになる。特に、第３の実施の形態の方法で、構造物の当初の重心μから見て表面が外向きであるポリゴンが多い領域、または当該領域に近い領域に参照点Ｐ４を設定できる。これにより、構造物の外側に突出した形状の特徴（例えば、構造物７０の端部の凸型形状）を、より詳細にグラフに反映させることができる。
【０１２３】
［第４の実施の形態］
以下、第４の実施の形態を説明する。前述の第２，第３の実施の形態と相違する事項を主に説明し、共通する事項の説明を省略する。第４の実施の形態では、ポリゴンが配置された密度が比較的大きな領域を判別する。ポリゴンの密度とは、所定の半径の球の内部に含まれるポリゴンの重心の個数を球の体積で割った値である。管理装置１００は、ポリゴンの密度が比較的大きな箇所を、局所探索法（例えば、山登り法）を用いて探索する。
【０１２４】
ここで、第４の実施の形態の管理装置のハードウェア例およびソフトウェア例は、第２の実施の形態の管理装置１００のハードウェア例およびソフトウェア例と同様である。そこで、第４の実施の形態でも第２の実施の形態と同じ符号・名称を用いて各要素を指し示す。
【０１２５】
図１８は、第４の実施の形態の参照点の設定例を示すフローチャートである。以下、図１８に示す処理をステップ番号に沿って説明する。以下の手順は、図１１のステップＳ１２および図１３のステップＳ３２に相当する。
（Ｓ５１）参照点設定部１２０は、構造物を形成する各ポリゴンの重心の座標を計算する。
【０１２６】
（Ｓ５２）参照点設定部１２０は、構造物の近傍のａ（ａは１以上の整数）個の点Ｐi（ここで、ｉは１以上ａ以下の整数である）の座標と各点Ｐiに付随する正の実数ｄiとを決定する。例えば、第２の実施の形態で求めた重心μに対する主成分方向の標準偏差σを用いて、μ±σの領域を構造物の近傍領域と考えて、近傍領域内にａ個の点Ｐiを乱数などにより設けることが考えられる。この場合、σは３つの主成分に対して求まるので、構造物の近傍領域の形状は楕円体となる。また、参照点設定部１２０は、平均（√λ1）／１００、標準偏差（√λ1）／１０のガウシアンからサンプリングすることで実数ｄiを決定してもよい。あるいは、重心μに対して所定半径の球内を構造物の近傍領域とし、実数ｄiとして、所定値を予め与えてもよい。
【０１２７】
（Ｓ５３）参照点設定部１２０は、点Ｐiを中心とした半径ｄiの球に含まれるポリゴンの重心の数Ａiを計算する。
（Ｓ５４）参照点設定部１２０は、以降のステップＳ５５，Ｓ５６を所定回数繰り返したか否かを判定する。所定回数繰り返した場合、処理をステップＳ５７に進める。所定回数繰り返していない場合、処理をステップＳ５５に進める。繰り返しの回数は、参照点設定部１２０に対して予め指定される。
【０１２８】
（Ｓ５５）参照点設定部１２０は、各点Ｐiの近傍点を乱数により求める。各点Ｐiの近傍点は、例えば、各点Ｐiから所定の距離以内の領域にランダムに設けられる。参照点設定部１２０は、近傍点を中心とした半径ｄiの球に含まれるポリゴンの重心の数Ｂiを計算する。
【０１２９】
（Ｓ５６）参照点設定部１２０は、Ｂi＞Ａiであれば、ステップＳ５５で求めた近傍点をＰiとして設定する（Ｐiの座標を更新する）。参照点設定部１２０は、Ｂi≦Ａiであれば、何もしない。そして、処理をステップＳ５４に進める。
【０１３０】
（Ｓ５７）参照点設定部１２０は、各点Ｐiの座標を参照点の座標と決定する。参照点設定部１２０は、参照点の座標をＳＴＬデータ１１１に関連付けて、参照点テーブル１１２に登録する。
【０１３１】
図１９は、第４の実施の形態の参照点の設定例を示す図である。第４の実施の形態では、球ＳＰ１，ＳＰ２，ＳＰ３，ＳＰ４に対して初期の中心位置と半径とを与えて、局所探索法（山登り法）を用いてポリゴンの密度が高い位置を探索する。図１９において、点Ｐ１１は球ＳＰ１の中心である。点Ｐ１２は球ＳＰ２の中心である。点Ｐ１３は球ＳＰ３の中心である。点Ｐ１４は球ＳＰ４の中心である。半径ｄ１は球ＳＰ１の半径である。半径ｄ２は球ＳＰ２の半径である。半径ｄ３は球ＳＰ３の半径である。半径ｄ４は球ＳＰ４の半径である。
【０１３２】
各球の半径を変えない場合、球の中心の位置によって、球内部に含まれるポリゴンの重心の数が変化する。例えば、球ＳＰ３の内部に含まれるポリゴンの重心の数がより大きな位置（すなわち、ポリゴンの密度が大きいと考えられる位置）を発見した場合、その位置を球ＳＰ３の中心として更新していく。これを、各球に対して実行する。前述のように、ポリゴンの密度が比較的大きい箇所は、構造物の凹凸の形状が他の箇所に比べて際立っていると考えられるからである。ポリゴンの密度が相対的に大きい領域内（ここでは、球ＳＰ１，ＳＰ２，ＳＰ３，ＳＰ４内）に参照点を設定することで、構造物の形状の特徴をより詳細にグラフに反映させることができる。
【０１３３】
［第５の実施の形態］
以下、第５の実施の形態を説明する。前述の第２，第３，第４の実施の形態と相違する事項を主に説明し、共通する事項の説明を省略する。第５の実施の形態では、検索の目的（検索目的）に応じて参照点の設定方法を変更する。
【０１３４】
ここで、第５の実施の形態の管理装置のハードウェア例およびソフトウェア例は、第２の実施の形態の管理装置１００のハードウェア例およびソフトウェア例と同様である。そこで、第５の実施の形態でも第２の実施の形態と同じ符号・名称を用いて各要素を指し示す。ただし、第５の実施の形態では、管理装置１００は、ライブラリ内のＳＴＬデータに対して、参照点の種類に応じた複数の種類の特徴ベクトルを予め計算し、記憶部１１０に格納しておく。
【０１３５】
図２０は、第５の実施の形態の特徴ベクトルテーブルの例を示す図である。特徴ベクトルテーブル１１４は、記憶部１１０に記憶される。特徴ベクトルテーブル１１４は、構造物、パターン１（２次モーメント）、パターン２（重心ν）、パターン３（ポリゴン密度）の項目を含む。
【０１３６】
構造物の項目には、構造物の識別情報が登録される。パターン１（２次モーメント）の項目には、第２の実施の形態の方法を用いて求めた特徴ベクトルが登録される。パターン２（重心ν）の項目には、第３の実施の形態の方法を用いて求めた特徴ベクトルが登録される。パターン３（ポリゴン密度）の項目には、第４の実施の形態の方法を用いて求めた特徴ベクトルが登録される。
【０１３７】
例えば、特徴ベクトルテーブル１１４には、識別情報“構造物Ａ”に対して、パターン１の特徴ベクトル“Ｖ１１”、パターン２の特徴ベクトル“Ｖ１２”、パターン３の特徴ベクトル“Ｖ１３”が登録されている。各パターンに対応する特徴ベクトルは、第２〜第４の実施の形態の方法を用いて、既存のＳＴＬデータに対して予め計算され、特徴ベクトルテーブル１１４に登録される。
【０１３８】
管理装置１００は、これらの特徴ベクトルを、検索目的に応じて使い分ける。管理装置１００は、検索クエリに含まれる情報に応じて、検索目的を判断する。例えば、ユーザは、検索を行いたい形状を示すＳＴＬデータとともに、検索目的（全体構造が類似するものを検索、部分的な構造が類似するものを検索など）を検索クエリとして管理装置１００に指定できる。
【０１３９】
図２１は、第５の実施の形態の参照点の設定例を示すフローチャートである。以下、図２１に示す処理をステップ番号に沿って説明する。以下の手順は、図１３のステップＳ３２に相当する。
【０１４０】
（Ｓ６１）参照点設定部１２０は、検索クエリから検索目的を特定する。参照点設定部１２０は、検索目的が、検索クエリに含まれる構造物と全体構造が類似する他の構造物の検索（全体構造に対する類似検索）であるか否かを判定する。検索目的が、全体構造に対する類似検索である場合、処理をステップＳ６２に進める。検索目的が、全体構造に対する類似検索でない場合、処理をステップＳ６３に進める。
【０１４１】
（Ｓ６２）参照点設定部１２０は、検索クエリに含まれる構造物のＳＴＬデータに基づいて、２次モーメントにより参照点を設定する（パターン１）。設定方法の手順として、図１２で例示した第２の実施の形態の手順を適用できる。なお、ここでは２次モーメントを用いるものとしたが、第２の実施の形態で例示したように、３次以上のモーメントを用いて参照点を決定してもよい。その場合、特徴ベクトルテーブル１１４にも３次以上のモーメントを用いて決定された参照点に応じた特徴ベクトルが予め登録される。そして、処理を終了する。
【０１４２】
（Ｓ６３）参照点設定部１２０は、検索目的が、突起物が複数ある構造物の検索であるか否かを判定する。検索目的が、突起物が複数ある構造物の検索である場合、処理をステップＳ６４に進める。検索目的が、突起物が複数ある構造物の検索でない場合、処理をステップＳ６５に進める。
【０１４３】
（Ｓ６４）参照点設定部１２０は、検索クエリに含まれる構造物のＳＴＬデータに基づいて、ポリゴン密度により参照点を設定する（パターン３）。設定方法の手順として、図１８で例示した第４の実施の形態の手順を適用できる。そして、処理を終了する。
【０１４４】
（Ｓ６５）参照点設定部１２０は、検索クエリに含まれる構造物のＳＴＬデータに基づいて、重心νにより参照点を設定する（パターン２）。設定方法の手順として、図１６で例示した第３の実施の形態の手順を適用できる。そして、処理を終了する。
【０１４５】
以後、グラフ合成処理部１３０および特徴量計算部１４０は、検索クエリに含まれる構造物のＳＴＬデータと、図２１の手順により設定された参照点とに基づいて、グラフ化、特徴ベクトルの計算を行う（図１３のステップＳ３３，Ｓ３４）。参照点設定部１２０は、何れのパターンを選択して参照点の設定を行ったかを検索部１５０に通知する。
【０１４６】
そして、図１３のステップＳ３５では、検索部１５０は、選択されたパターンに応じた特徴ベクトルを特徴ベクトルテーブル１１４から特定する。検索部１５０は、特徴ベクトルテーブル１１４から特定した特徴ベクトルと、検索クエリに対して求められた特徴ベクトルとを照合する。
【０１４７】
このように、検索目的に応じて、参照点の設定方法を選択して特徴ベクトルを求めることが考えられる。例えば、全体構造の類似検索であれば、主成分方向の形状の特徴を基に検索を行うことで、全体構造が類似する構造物を適切に検索できる。
【０１４８】
また、例えば、突起物が複数ある構造物の検索では、ポリゴンの密度が比較的大きい箇所に突起物の形状の特徴が現れると考えられるので、第４の実施の形態の方法により、当該突起物の形状の特徴が保持されるように参照点を設定する。そして、突起物の特徴を基に検索を行うことで、突起物が複数ある構造物を適切に検索できる。その他の検索目的では、全体および部分の構造の特徴に対してバランスのとれた検索を行うため、第３の実施の形態の方法を用いる。
上記のように検索目的に応じて参照点の設定方法を選択する他、検索対象物に応じて参照点の設定方法を選択することも考えられる。
【０１４９】
図２２は、第５の実施の形態の参照点の他の設定例を示すフローチャートである。以下、図２２に示す処理をステップ番号に沿って説明する。以下の手順は、図１３のステップＳ３２に相当する。
【０１５０】
（Ｓ７１）参照点設定部１２０は、検索クエリから検索対象（検索目的の一例と考えることができる）を特定する。参照点設定部１２０は、検索対象がネジであるか否かを判定する。検索対象がネジである場合、処理をステップＳ７２に進める。検索対象がネジでない場合、処理をステップＳ７３に進める。
【０１５１】
（Ｓ７２）参照点設定部１２０は、検索クエリに含まれる構造物のＳＴＬデータに基づいて、２次モーメントにより参照点を設定する（パターン１）。設定方法の手順として、図１２で例示した第２の実施の形態の手順を適用できる。なお、ここでは２次モーメントを用いるものとしたが、第２の実施の形態で例示したように、３次以上のモーメントを用いて参照点を決定してもよい。その場合、特徴ベクトルテーブル１１４にも３次以上のモーメントを用いて決定された参照点に応じた特徴ベクトルが予め登録される。そして、処理を終了する。
【０１５２】
（Ｓ７３）参照点設定部１２０は、検索対象がバネであるか否かを判定する。検索対称がバネである場合、処理をステップＳ７４に進める。検索対象がバネでない場合、処理をステップＳ７５に進める。
【０１５３】
（Ｓ７４）参照点設定部１２０は、検索クエリに含まれる構造物のＳＴＬデータに基づいて、構造物（ここではバネの形状）をボクセル化し、モルフォルジーを用いて細線化して得た端点を参照点として設定する。そして、処理を終了する。
【０１５４】
（Ｓ７５）参照点設定部１２０は、検索クエリに含まれる構造物のＳＴＬデータに基づいて、重心νにより参照点を設定する（パターン２）。設定方法の手順として、図１６で例示した第３の実施の形態の手順を適用できる。そして、処理を終了する。
【０１５５】
以後、グラフ合成処理部１３０および特徴量計算部１４０は、検索クエリに含まれる構造物のＳＴＬデータと、図２２の手順により設定された参照点とに基づいて、グラフ化、特徴ベクトルの計算を行う（図１３のステップＳ３３，Ｓ３４）。参照点設定部１２０は、何れのパターンを選択して参照点の設定を行ったかを検索部１５０に通知する。
【０１５６】
そして、図１３のステップＳ３５では、検索部１５０は、選択されたパターンに応じた特徴ベクトルを特徴ベクトルテーブル１１４から特定する。検索部１５０は、特徴ベクトルテーブル１１４から特定した特徴ベクトルと、検索クエリに対して求められた特徴ベクトルとを照合する。なお、この場合、管理装置１００は、既存の構造物に対して、ステップＳ７４で例示したパターンに対応する特徴ベクトルも予め求めておき、特徴ベクトルテーブル１１４に格納しておく。
【０１５７】
例えば、ネジの構造物では、ネジの頭（頭部）と軸とが重要であるため、参照点がネジの頭と軸とにより近い位置に参照点が設定される方法を選択することで、ネジの形状の特徴をより詳細に反映した特徴ベクトルによる検索を行える。その結果、ネジの検索の精度を向上できる。
【０１５８】
図２３は、第５の実施の形態の参照点の他の設定例を示す図である。図２３では、図２２のステップＳ７４における参照点の設定方法を例示している。図２３（Ａ）では、細線化する前のバネを例示している。図２３（Ｂ）では細線化した後のバネを例示している。図２３（Ｂ）において、参照点Ｐ２１，Ｐ２２は、細線化して得られたバネの端点に設定された参照点である。
【０１５９】
バネは中空であるため、重心の位置は構造物の内部ではない。そのため、バネのスケルトンを求めて参照点を設定する。これにより、バネの柱状の形状の特徴をより詳細に反映した特徴ベクトルによる検索を行える。その結果、バネの検索の精度を向上できる。
【０１６０】
ネジやバネ以外の構造物については、図２１と同様に、全体および部分の構造の特徴に対してバランスのとれた検索を行うため、第３の実施の形態の方法を用いる。このように、検索目的に応じて、参照点の設定方法を選択することで、検索目的に合った特徴ベクトルによる検索を行える。これにより、構造物の検索の精度を向上できる。
【０１６１】
なお、第１の実施の形態の情報処理は、演算部１ｂにプログラムを実行させることで実現できる。また、第２〜第５の実施の形態の情報処理は、プロセッサ１０１にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体１３に記録できる。
【０１６２】
例えば、プログラムを記録した記録媒体１３を配布することで、プログラムを流通させることができる。また、プログラムを他のコンピュータに格納しておき、ネットワーク経由でプログラムを配布してもよい。コンピュータは、例えば、記録媒体１３に記録されたプログラムまたは他のコンピュータから受信したプログラムを、ＲＡＭ１０２やＨＤＤ１０３などの記憶装置に格納し（インストールし）、当該記憶装置からプログラムを読み込んで実行してもよい。
【０１６３】
以上の第１〜第５の実施の形態を含む実施形態に関し、更に以下の付記を開示する。
（付記１）  ３次元で構造物を表す複数の多角形の頂点の座標を含む構造物データを参照して、前記複数の多角形の空間内での配置に応じて、前記複数の多角形の頂点とともに前記構造物データをグラフ化したときの特徴量の計算に用いられる点の座標を算出し、
算出した点の座標を前記構造物データに関連付けて記憶装置に格納する、
処理をコンピュータに実行させる管理プログラム。
【０１６４】
（付記２）  前記算出では、前記複数の多角形の頂点の座標を用いた主成分分析の結果を用いて前記点の座標を算出する、付記１記載の管理プログラム。
（付記３）  前記算出では、前記構造物の重心に関する主成分方向の２次以上のモーメントに基づいて前記点の座標を算出する、付記２記載の管理プログラム。
【０１６５】
（付記４）  前記算出では、前記構造物の重心、各多角形の重心および各多角形の法線ベクトルに基づいて前記点の座標を算出する、付記１記載の管理プログラム。
【０１６６】
（付記５）  前記算出では、前記構造物の重心から多角形の重心へ向けたベクトルと当該多角形の法線ベクトルとの内積を算出して当該多角形の重心に割り当てる処理を多角形毎に行い、前記内積の分布に基づいて前記点の座標を算出する、付記４記載の管理プログラム。
【０１６７】
（付記６）  前記算出では、空間内の複数の領域における多角形の個数の密度に基づいて前記点の座標を算出する、付記１記載の管理プログラム。
（付記７）  前記算出では、前記複数の領域のうち、多角形の個数の密度が他の領域よりも大きな領域を局所探索法により検索し、検索された領域内に前記点の座標を設定する、付記６記載の管理プログラム。
【０１６８】
（付記８）  前記算出では、構造物データの検索クエリで指定された検索目的に応じて、前記点の座標の算出方法を選択する、付記１乃至７の何れか１つに記載の管理プログラム。
【０１６９】
（付記９）  所定の構造物に類似する形状の他の構造物の検索を要求する検索クエリを受け付けた際に前記点の座標の前記算出を実行し、
前記算出では、前記点の座標の複数の算出方法のうち、前記検索クエリで指定された検索目的に応じた算出方法を選択し、選択した算出方法を用いて前記点の座標を算出する、付記８記載の管理プログラム。
【０１７０】
（付記１０）  前記記憶装置を参照して、前記点および前記構造物の各頂点をノード、前記点と前記構造物の各頂点とを結ぶ辺をエッジとして含み、辺の長さに応じた重みをエッジの重みとするグラフを生成し、前記グラフに基づいて前記特徴量を計算する、付記１乃至９の何れか１つに記載の管理プログラム。
【０１７１】
（付記１１）  ３次元で構造物を表す複数の多角形の頂点の座標を含む構造物データを記憶する記憶部と、
前記構造物データを参照して、前記複数の多角形の空間内での配置に応じて、前記複数の多角形の頂点とともに前記構造物データをグラフ化したときの特徴量の計算に用いられる点の座標を算出し、
算出した点の座標を前記構造物データに関連付けて記憶装置に格納する、演算部と、
を有する管理装置。
【０１７２】
（付記１２）  コンピュータが、
３次元で構造物を表す複数の多角形の頂点の座標を含む構造物データを参照して、前記複数の多角形の空間内での配置に応じて、前記複数の多角形の頂点とともに前記構造物データをグラフ化したときの特徴量の計算に用いられる点の座標を算出し、
算出した点の座標を前記構造物データに関連付けて記憶装置に格納する、
管理方法。
【符号の説明】
【０１７３】
１  管理装置
１ａ  記憶部
１ｂ  演算部
２，３  構造物
Ｐ１，Ｐ２  点
【図１】
2015194909.tif 000018
【図２】
2015194909.tif 000019
【図３】
2015194909.tif 000020
【図４】
2015194909.tif 000021
【図５】
2015194909.tif 000022
【図６】
2015194909.tif 000023
【図７】
2015194909.tif 000024
【図８】
2015194909.tif 000025
【図９】
2015194909.tif 000026
【図１０】
2015194909.tif 000027
【図１１】
2015194909.tif 000028
【図１２】
2015194909.tif 000029
【図１３】
2015194909.tif 000030
【図１４】
2015194909.tif 000031
【図１５】
2015194909.tif 000032
【図１６】
2015194909.tif 000033
【図１７】
2015194909.tif 000034
【図１８】
2015194909.tif 000035
【図１９】
2015194909.tif 000036
【図２０】
2015194909.tif 000037
【図２１】
2015194909.tif 000038
【図２２】
2015194909.tif 000039
【図２３】
2015194909.tif 000040