説明

情報検索装置、情報検索プログラム及び情報検索方法

【課題】3Dモデルの部分形状を簡単な操作で検索することを課題とする。
【解決手段】情報検索装置1は、3Dモデル(three dimensional model)の類似部分の検索時に利用者による指定点を含む複数の断面を求め、最小の断面を部品の体積が小さい方に移動させ、移動前後の断面が挟む部分形状を比較範囲とする。そして、情報検索装置1は、3Dモデルにおける部分形状を表す部分モデルを記憶する部分モデル記憶部2bに記憶された部分モデルの中から、比較範囲とした部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、情報検索装置、情報検索プログラム及び情報検索方法に関する。
【背景技術】
【0002】
近年、商品の多品種少量化が進むに伴って類似する製品の開発が並行して進行することが多くなっている。かかる開発体制下では、ある製品の開発で得られた技術や知識などのノウハウ(know-how)を他の製品の開発においても有効に活用することが開発効率を向上させるために重要である。
【0003】
このようなノウハウを共有するための仕組みとして、ナレッジマネージメントシステム(knowledge management system)と呼ばれる情報提供システムが知られている。ナレッジマネージメントシステムは、各種のノウハウを記述した知識情報をデータベース(data base)に蓄積する。例えば、ナレッジマネージメントシステムは、3Dモデル(three dimensional model)で表現された部品と、その部品の不具合などを示す障害情報などが記載された文書とを関連付けてデータベースに保存する。
【0004】
このナレッジマネージメントシステムによれば、利用者は、自身が指定する部品に関する知識情報をデータベースから検索することができる。これを説明すると、ナレッジマネージメントシステムでは、利用者が設計に使用する部品の3Dモデルを検索キー(key)として受け付ける。そして、ナレッジマネージメントシステムでは、検索キーとして受け付けた部品に類似する部品をデータベース内の3Dモデルから検索し、検索した3Dモデルとともにその3Dモデルに関連付けられた障害情報を出力する。このような障害情報の検索により、利用者は、過去の障害情報をもとに新製品設計時に予めその不具合を回避するような設計を行うことができる。なぜなら、製品の不具合の多くは、製品に含まれる部分の3次元的な形状に由来することが多く、過去に不具合の原因となった部分と形状が類似する部分を使用すると、同じような障害が出る可能性が高くなるからである。
【0005】
ここで、検索キーの最小単位を3Dモデル全体としたのでは、その3Dモデルに含まれる複数の部位に異なる障害情報がデータベースに登録されていた場合に目的とする障害情報とともにそれ以外の障害情報も検索結果として出力されることになる。この場合、利用者は、検索結果の中から目的の部位に関する障害情報を選別して検索結果を閲覧する必要がある。このため、3Dモデルの中でも目的とする部位以外の障害情報が含まれる事態を避けるために、3Dモデルに含まれる部分形状を検索する仕組みが提案されている。
【0006】
このように3Dモデルの部分形状を検索するための手法としては、利用者に検索キーとする3Dモデルの部分形状を直接指定させる従来技術1が存在する。また、セグメンテーション(segmentation)方式で3Dモデルが予め分割された部分モデルを利用者に選択させる従来技術2が存在する。
【先行技術文献】
【特許文献】
【0007】
【特許文献1】特開2000−222428号公報
【発明の概要】
【発明が解決しようとする課題】
【0008】
しかしながら、上記の従来技術1及び2は、以下に説明するように、3Dモデルの部分形状を簡単な操作で検索することができないという問題がある。
【0009】
一例として、ポリゴンモデル(polygon model)によって形成される3Dモデルが表示された画像上で利用者に部分形状を指定または選択させる場合を想定する。例えば、従来技術1の場合には、利用者が目的とする部分形状が選択された状態になるまでポリゴンを1つずつ指定する操作を繰り返す必要があり、検索キーを入力するための操作が煩雑となる。また、従来技術1では、利用者がポインティングデバイス(pointing device)を用いて目的とする部分形状を範囲指定する操作を行うこともできる。ところが、この場合には、3Dモデルに含まれる3次元の部分形状を2次元の枠で囲うように指定する必要があるので、利用者が意図する部分形状を選択するまで何度も繰り返し範囲指定を行う必要がある。また、従来技術2の場合には、セグメンテーション方式で分割された部分モデルと、利用者が目的とする部分形状とが必ずしも一致するとは限らない。このため、結局は、従来技術1のように利用者が3Dモデルの部分形状を直接指定する必要がある。
【0010】
なお、この問題は、3Dモデルがポリゴンモデルによって表現される場合だけに生じるものではない。例えば、3Dモデルが曲面によるサーフィスモデル(surface model)やボリュームデータ(volume data)形式によって表現される場合にも同様に生じる問題である。
【0011】
開示の技術は、上記に鑑みてなされたものであって、3Dモデルの部分形状を簡単な操作で検索することができる情報検索装置、情報検索プログラム及び情報検索方法を提供することを目的とする。
【課題を解決するための手段】
【0012】
本願の開示する情報検索装置は、部品を表す3Dモデルを記憶する3Dモデル記憶部と、前記3Dモデルにおける部分形状を表す部分モデルを記憶する部分モデル記憶部とを有する。さらに、前記情報検索装置は、表示部に表示された3Dモデル上で、起点とする位置の指定を受け付ける受付部を有する。さらに、前記情報検索装置は、前記3Dモデル記憶部に記憶された3Dモデルのうち前記受付部によって指定が受け付けられた起点の法線方向に所在する3Dモデルを対象に3Dモデルを分断する複数の断面を算出する断面算出部を有する。この断面算出部は、前記受付部によって指定が受け付けられた起点の法線方向を指す直線が当該3Dモデルと交わる交点を含む前記3Dモデルを分断する複数の断面を算出する。さらに、前記情報検索装置は、前記断面算出部によって算出された断面によって前記3Dモデルが分断される立体それぞれの大きさを示す指標を算出する指標算出部を有する。さらに、前記情報検索装置は、前記複数の断面のうち大きさが最小である断面を基準断面とし、当該基準断面と直交する2方向のうちいずれの方向に断面を移動させるのかを決定する移動方向決定部を有する。この移動方向決定部は、基準断面と、該基準断面によって分断される立体のうち前記指標算出部による指標の算出結果が最小となる立体との位置関係に基づき、断面の移動方向を決定する。さらに、前記情報検索装置は、前記移動方向決定部によって決定された方向へ断面を移動させることにより前記基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出する部分モデル抽出部を有する。さらに、前記情報検索装置は、前記部分モデル抽出部によって抽出された部分モデルの特徴量を算出する特徴量算出部を有する。さらに、情報検索装置は、前記部分モデル記憶部に記憶された部分モデルのうち、前記特徴量算出部によって算出された部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する検索部を有する。
【発明の効果】
【0013】
本願の開示する情報検索装置の一つの態様によれば、3Dモデルの部分形状を簡単に検索することができるという効果を奏する。
【図面の簡単な説明】
【0014】
【図1】図1は、実施例1に係る情報検索装置の構成を示すブロック図である。
【図2】図2は、実施例2に係る情報検索装置の構成を示すブロック図である。
【図3】図3は、特徴量テーブルに記憶される情報の構成例を示す図である。
【図4】図4は、モデルテーブルに記憶される情報の構成例を示す図である。
【図5】図5は、点テーブルに記憶される情報の構成例を示す図である。
【図6】図6は、面テーブルに記憶される情報の構成例を示す図である。
【図7】図7は、交差判定テーブルに記憶される情報の構成例を示す図である。
【図8】図8は、辺テーブルに記憶される情報の構成例を示す図である。
【図9】図9は、輪郭拡張候補テーブルに記憶される情報の構成例を示す図である。
【図10】図10は、断面候補の取得要領を説明するための説明図である。
【図11】図11は、断面候補の取得要領を説明するための説明図である。
【図12】図12は、輪郭点テーブルに記憶される情報の構成例を示す図である。
【図13】図13は、輪郭辺テーブルに記憶される情報の構成例を示す図である。
【図14】図14は、輪郭点、輪郭辺及び輪郭距離の算出要領を説明するための説明図である。
【図15】図15は、輪郭テーブルに記憶される情報の構成例を示す図である。
【図16】図16は、輪郭計算テーブルに記憶される情報の構成例を示す図である。
【図17】図17は、部分面テーブルに記憶される情報の構成例を示す図である。
【図18】図18は、部分点テーブルに記憶される情報の構成例を示す図である。
【図19】図19は、検索結果テーブルに記憶される情報の構成例を示す図である。
【図20】図20は、実施例2に係る全体処理の手順を示すフローチャートである。
【図21】図21は、実施例2に係る基準断面輪郭取得処理の手順を示すフローチャートである。
【図22】図22は、実施例2に係る拡張方向決定処理の手順を示すフローチャートである。
【図23】図23は、実施例2に係る拡張処理の手順を示すフローチャートである。
【図24】図24は、実施例2に係る部分モデル生成処理の手順を示すフローチャートである。
【図25】図25は、実施例2に係る類似検索処理の手順を示すフローチャートである。
【図26】図26は、実施例2に係る検索結果選択処理の手順を示すフローチャートである。
【図27】図27は、実施例2に係る輪郭取得処理の手順を示すフローチャートである。
【図28】図28は、実施例2に係る効果を説明するための説明図である。
【図29】図29は、実施例2に係る効果を説明するための説明図である。
【図30】図30は、実施例2に係る効果を説明するための説明図である。
【図31】図31は、実施例2に係る効果を説明するための説明図である。
【図32】図32は、実施例3に係る情報検索プログラムを実行するコンピュータの一例について説明するための図である。
【発明を実施するための形態】
【0015】
以下に、本願の開示する情報検索装置、情報検索プログラム及び情報検索方法の実施例を図面に基づいて詳細に説明する。なお、この実施例は開示の技術を限定するものではない。
【実施例1】
【0016】
図1は、実施例1に係る情報検索装置の構成を示すブロック図である。図1に示す情報検索装置1は、3Dモデル記憶部2aと、部分モデル記憶部2bと、受付部3と、断面算出部4と、指標算出部5と、移動方向決定部6と、部分モデル抽出部7と、特徴量算出部8と、検索部9とを有する。
【0017】
このうち、3Dモデル記憶部2aは、部品を表す3Dモデルを記憶する。部分モデル記憶部2bは、3Dモデルにおける部分形状を表す部分モデルを記憶する。また、受付部3は、表示部に表示された3Dモデル上で、起点とする位置の指定を受け付ける。
【0018】
断面算出部4は、3Dモデル記憶部2aに記憶された3Dモデルのうち受付部3によって指定が受け付けられた起点の法線方向に所在する3Dモデルを対象に3Dモデルを分断する複数の断面を算出する。この断面算出部4は、受付部3によって指定が受け付けられた起点の法線方向を指す直線が当該3Dモデルと交わる交点を含む3Dモデルを分断する複数の断面を算出する。
【0019】
指標算出部5は、断面算出部4によって算出された断面によって3Dモデルが分断される立体それぞれの大きさを示す指標を算出する。
【0020】
移動方向決定部6は、複数の断面のうち大きさが最小である断面を基準断面とし、当該基準断面と直交する2方向のうちいずれの方向に断面を移動させるのかを決定する。この移動方向決定部6は、基準断面と、該基準断面によって分断される立体のうち指標算出部5による指標の算出結果が最小となる立体との位置関係に基づき、断面の移動方向を決定する。
【0021】
部分モデル抽出部7は、移動方向決定部6によって決定された方向へ断面を移動させることにより基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出する。特徴量算出部8は、部分モデル抽出部7によって抽出された部分モデルの特徴量を算出する。また、検索部9は、部分モデル記憶部2bに記憶された部分モデルのうち、特徴量算出部8によって算出された部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する。
【0022】
このように、情報検索装置1では、利用者が3Dモデルの類似部分を検索する場合に入力させる操作を起点を指定させる操作に集約した。このような操作の集約を実現するために、情報処理装置1では、利用者が3Dモデルの部分形状を指定するにあたって行う操作感覚を利用している。
【0023】
すなわち、利用者は、3Dモデル全体から自身が比較範囲としたい部分形状を区切るのに、3Dモデルの中側から部分形状の境界を始めに指定し、その境界から端に向かって拡大することにより、全体から部分を区切る操作を直感的に行う。なぜなら、中側から端に区切る操作を行った方が、既に指定した部分から比較範囲から除外したい特定の部分を除く操作を行う手間がなく、意図しない部位の形状を含まない最小の部分形状を指定しやすいからである。このような操作を利用者が行う場合には、利用者が始めに指定した位置が区切る複数の立体のうち利用者がより小さい立体の方を全体から区切る意図を持つ可能性が高いことがわかる。なぜなら、大きい立体には、利用者が指定を意図しない部分形状が含まれる可能性が高く、利用者がより大きい立体に含まれる部分形状の方を全体から区切る意図を持つ場合には、3Dモデル上で別の位置を指定すると想定されるからである。
【0024】
このことから、情報検索装置1では、3Dモデルの類似部分の検索時に利用者による指定点を含む複数の断面を求め、最小の断面を部品の体積が小さい方に移動させ、移動前後の断面が挟む部分形状を検索キーとする。このため、情報検索装置1では、利用者から3Dモデル上で起点とする位置を受け付けるだけで、検索キーとする部分モデルを抽出して部分モデル記憶部2bに対する検索を実行できる。したがって、本実施例に係る情報検索装置1によれば、3Dモデルの部分形状を簡単な操作で検索することができる。
【実施例2】
【0025】
[情報検索装置10の構成]
続いて、実施例2に係る情報検索装置10について説明する。図2は、実施例2に係る情報検索装置の構成を示すブロック図である。図2に示す情報検索装置10は、3Dモデル(three dimensional model)を用いて製品を製図する設計支援アプリを搭載した情報処理装置であり、入力部11と、表示部12と、記憶部13と、制御部14とを有する。なお、以下では、ポリゴンモデルによって表現される3Dモデルの部分形状を検索する場合を例示するが、3Dモデルが曲面によるサーフィスモデル(surface model)やボリュームデータ(volume data)形式によって表現される場合にも同様に適用できる。
【0026】
このうち、入力部11は、各種情報、例えば3Dモデル上で起点とする位置の指定を受け付ける入力デバイスであり、例えば、キーボードやマウスなどである。この入力部11は、後述の表示部12と協働して、ポインティングデバイス機能を実現する。また、表示部12は、各種の情報、例えば実際の部品がポリゴンモデルで表現された3Dモデルなどを表示する表示デバイスであり、例えば、モニタ、ディスプレイやタッチパネルなどである。なお、ここでは、マウスによってポインティングデバイス機能が実現される場合を説明するが、タッチパッドなどの他の入力デバイスによりポインティングデバイス機能が実現される場合にも同様に適用できる。
【0027】
かかる「起点」とする位置の指定は、利用者が3Dモデル全体から自身が比較範囲としたい部分形状を区切るのに際して、3Dモデルの中側から部分形状の境界を指定する意義を含み得る。この起点に基づき、後述の制御部14内の各種機能部によって部分形状の検索を行う比較範囲が部分モデルとして抽出される。
【0028】
記憶部13は、例えば、フラッシュメモリ(flash memory)などの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。なお、記憶部13は、上記の種類の記憶装置に限定されるものではなく、RAM(Random Access Memory)、ROM(Read Only Memory)であってもよい。
【0029】
この記憶部13は、制御部14で実行される各種プログラム、例えばOS(Operating System)や設計支援アプリやそのプログラムの実行に必要なデータを記憶する。このほか、記憶部13は、例えば部分モデルデータ13aと、3Dモデルデータ13cと、各種テーブルデータ13cとを記憶する。
【0030】
部分モデルデータ13aは、3Dモデルにおける部分形状を表す部分モデルに関するデータである。ここで、かかる部分モデルデータ13aとしては、各種部品の3Dモデルに含まれる部分モデルのうち、例えば過去に不具合が発見された部分モデルに関する情報が新製品設計時の被検索対象として予め登録される。なお、被検索対象の部分モデルの登録要件は、過去に不具合が発見されたことに限らず、過去のノウハウから推奨される部分モデルなどの他の要件であってもかまわない。
【0031】
この部分モデルデータ13aは、部分モデルを一意に特定する部分モデルID(identification)ごとにその部分モデルの特徴量を記憶した特徴量テーブルを含む。図3は、特徴量テーブルに記憶される情報の構成例を示す図である。図3の例で言えば、部分モデルIDが「0」である部分モデルの3次元形状の特徴量として「・・・」が記憶された例を示す。この図3に示す例では、特徴量をブランクで表現したが、実際には部分モデルのベクトル情報などが記憶される。
【0032】
なお、ここでは、被検索対象の部分モデルに関する情報として部分モデルの特徴量を記憶する特徴量テーブルを例示したが、開示の装置では、特徴量以外の情報を記憶することとしてもよい。例えば、開示の装置では、部分モデルの画像のほか、部分モデルの不具合などを示す障害情報などが記載された文書をさらに記憶することもできる。また、ここでは、部分モデルの特徴量を記憶する場合を説明したが、必ずしも部分モデルの特徴量を予め記憶しておく必要はない。例えば、開示の装置は、部分モデルの形状を定義するポリゴンの頂点と各頂点の組合せとを記憶し、検索時には被検索対象の部分モデルの形状から部分モデルの特徴量を随時算出することとしてもよい。
【0033】
3Dモデルデータ13bは、部品を表す3Dモデルに関するデータである。この3Dモデルデータ13bは、3Dモデルを一意に特定するモデルIDごとにその3Dモデルのモデルデータを記憶したモデルテーブルを含む。図4は、モデルテーブルに記憶される情報の構成例を示す図である。図4に示す例では、モデルIDが「0」である部分モデルのモデルデータとして「・・・」が記憶されたことを示す。この図4に示すモデルデータとしては、3Dモデルを形成するポリゴンに関する情報が記憶される。このモデルデータの一例としては、3角形ポリゴンを定義する3つの頂点と頂点の組合せを特定する2つのテーブル、すなわちポリゴンの頂点を定義する点テーブルと、ポリゴンの面を定義する面テーブルとが含まれる。
【0034】
このうち、点テーブルは、ポリゴンの頂点を一意に特定するための点IDごとにその頂点のX座標、Y座標及びZ座標を記憶したテーブルである。図5は、点テーブルに記憶される情報の構成例を示す図である。図5に示す例では、点ID「0」の頂点の座標が(10,15,−20)であることを示す。さらに、点ID「1」の頂点の座標が(15,50,−30)であることを示す。また、点ID「2」の頂点の座標が(5,−10,20)であることを示す。
【0035】
面テーブルは、ポリゴンの面を一意に特定するための面IDごとにその面に含まれる頂点の点IDを記憶したテーブルである。図6は、面テーブルに記憶される情報の構成例を示す図である。図6に示す例では、面ID「0」の面が点ID「0」、点ID「1」及び点ID「2」の3つの頂点を含んで構成される面であることを示す。つまり、図5で示した点IDの「0」、「1」及び「2」の3点が同一の3角形ポリゴンを定義する各頂点に対応することを示す。なお、この図6で点IDの末尾に付される括弧付きの番号は、テーブルへ登録された順序を指し、(1)であれば1つ目、(2)であれば2つ目、(3)であれば3つ目であること示す。かかる登録順序は、面テーブル使用時の処理結果に及ぼすものではなく、必ずしも区別して登録される必要はない。
【0036】
なお、ここでは、3Dモデルが3角形ポリゴンで表現される場合を想定して以下の説明を行うが、開示の装置の適用範囲が3角形ポリゴンに限定されるものではなく、3Dモデルが任意の多角形ポリゴンで表現される場合に同様に適用できる。
【0037】
各種テーブルデータ13cは、後述の制御部14内の各機能部の処理過程で生成されるテーブル群である。なお、各テーブルの詳細はそれぞれのテーブルがどのようにして生成されるか、或いはテーブルがどのような処理に使用されるかについては後述の制御部14内の各機能部の説明で述べる。また、各テーブルは、必ずしもテーブルの形式を取る必要はなく、テーブルの構成以外のデータベースを用いてもよい。
【0038】
制御部14は、例えば、ASIC(Application Specific Integrated Circuit)やFPGA(Field Programmable Gate Array)などの集積回路、または、CPU(Central Processing Unit)やMPU(Micro Processing Unit)などの電子回路である。
【0039】
この制御部14は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。制御部14は、図2に示すように、起点対応面取得部14aと、輪郭取得部14bと、基準断面輪郭取得部14cと、拡張方向決定部14dと、拡張処理部14eと、部分モデル生成部14fと、類似検索部14gと、結果選択部14hとを有する。
【0040】
このうち、起点対応面取得部14aは、入力部11を介して指定を受け付けた起点の法線方向を指す直線と交わる3Dモデルのポリゴンの面を取得する処理部である。すなわち、起点対応面取得部14aは、利用者により指定された起点から3Dモデルの視点方向へ向かう直線と、記憶部13に3Dモデルデータ13bとして記憶された面テーブルの全ての面IDの面との間で交差判定を行う。これによって、起点対応面取得部14aは、直線と交わるポリゴンの面IDを取得する。
【0041】
ここで、利用者により入力部11を介して指定される起点が2次元座標である一方で、面テーブルで面IDに対応付けて記憶される点IDは3次元座標である。このため、起点対応面取得部14aは、面テーブルで面IDに対応付けて記憶された3つの点ID(1)〜点ID(3)を点テーブルから取り出し、これら3つの点ID(1)〜点ID(3)の3次元座標を投影座標である2次元座標へ変換する。
【0042】
この3次元座標から2次元座標へ変換する式は、x´、y´を点の2次元座標とし、x、y、zを3次元座標とし、fを焦点距離としたとき、下記の式(1)及び式(2)で表される。なお、焦点距離fは、予め定めた値であり、視点の画角に依存するものである。
【0043】
【数1】

【0044】
【数2】

【0045】
上記の式(1)及び式(2)のx、y、zへ点ID(1)の3次元座標を代入することにより、点ID(1)の2次元座標(x´,y´)を得ることができる。同様にして、起点対応面取得部14aは、式(1)及び式(2)を用いることにより、点ID(2)及び点ID(3)の2次元座標を得ることができる。このようにして、起点対応面取得部14aは、各面IDに対応する3つの頂点の点IDの2次元座標を得る。なお、ここでは、上記の式(1)及び(2)を用いて2次元座標を算出する例を説明したが、点テーブルに記憶された各点IDの3次元座標を予め2次元座標に変換して記憶部13に登録しておくこととしてもよい。
【0046】
このようにしてポリゴンを定義する頂点の座標を投影座標である2次元座標へ変換した上で、起点対応面取得部14aは、利用者により指定された起点及び3Dモデルの注視点を通る直線との間で交差判定を行う。かかる直線と面の交差判定は、下記の式(3)〜式(5)を用いて、内積に基づき判定することができる。なお、下記の式(3)〜式(5)では、x´、y´は起点の2次元座標であるものとする。同様に、x´、y´は、ポリゴンの3つの頂点のうち1つ目の頂点である点ID(1)の投影座標である。同様に、x´、y´は、2つ目の頂点である点ID(2)の投影座標である。同様に、x´、y´は、3つ目の頂点である点ID(3)の投影座標であるものとする。
【0047】
【数3】

【0048】
【数4】

【0049】
【数5】

【0050】
上記の式(3)〜式(5)それぞれに起点の2次元座標及び点ID(1)〜(3)の投影座標を代入することによりf、f、fの値が得られる。そして、起点対応面取得部14aは、このようにして得られたf、f、fの値の中に異なる符号を持つものが存在するか否かによって直線と面が交差しているか否かを判定する。このとき、起点対応面取得部14aは、f、f、fの値の中に異なる符号を持つものが存在しない場合には、直線と面が交差するものと判定する。つまり、f≧0、f≧0かつf≧0である場合、またはf≦0、f≦0かつf≦0である場合に、起点対応面取得部14aは、直線と面が交差するものと判定する。
【0051】
このようにして交差判定を行った後に、起点対応面取得部14aは、直線と面が交差する場合には、その交点を算出する。例えば、直線と面の交点のZ座標を求める場合を想定する。ここで、3点p、p、pを通る平面の方程式は、法線ベクトルnをn=(p−p)×(p−p)として、n(p−p)で表される。このとき、直線と面の交点の座標を(x、y、z)とし、n(p−p)をx、y、zの各成分に分解すると、下記の式(6)となる。なお、式(6)におけるp1xは点pのX座標を指し、p1yは点pのY座標を指し、また、p1zは点pのZ座標を指す。
【0052】
【数6】

【0053】
さらに、上記の式(1)及び(2)に示した3次元座標に交点(x、y、z)をあてはめてx及びyを求める下記の式(7)及び(8)へ変形した上で、これら式(7)及び式(8)を上記の式(6)へ代入すると式(9)が得られる。
【0054】
【数7】

【0055】
【数8】

【0056】
【数9】

【0057】
上記の式(9)に既知である値それぞれを代入することにより、起点対応面取得部14aは、交点のZ座標の値zを得る。同様にして、起点対応面取得部14aは、交点のX座標の値x及び交点のY座標の値yの値を得る。
【0058】
そして、起点対応面取得部14aは、このようにして得られた交点(x、y、z)を直線と交差する面の面IDに対応付けた交差判定テーブルを生成し、生成した交差判定テーブルを記憶部13の各種テーブルデータ13cへ登録する。なお、交差判定テーブルが既に生成されている場合には、新たにレコードを追加する形で面ID及び交点の座標を含むレコードが追加される。
【0059】
この交差判定テーブルは、直線と交差するポリゴンの面IDごとにその交点のX座標、Y座標及びZ座標を記憶したテーブルである。図7は、交差判定テーブルに記憶される情報の構成例を示す図である。図7に示す例で言えば、図6に示した面テーブル及び図5に示した点テーブルを用いて交差判定を行った結果、面ID「0」のポリゴンが座標(10,15,−10)で直線と交わることを示す。
【0060】
このように、起点対応面取得部14aは、利用者により指定された起点から3Dモデルの視点方向である注視点へ向かう直線と、面テーブルに記憶された全ての面IDの面との間で交差判定を行い、両者が交差する場合にはその交点を交差判定テーブルに登録する。なお、ここでは、起点から3Dモデルの視点方向へ向かう直線としたが、起点から画面に対する鉛直方向に向かう直線と面との間で交差判定及び交点の算出を行うようにしてもよい。
【0061】
そして、直点と交差する面IDが交差判定テーブルに複数登録されている場合には、起点対応面取得部14aは、交差判定テーブルに記憶された交点のZ座標のうち最もZ座標が大きい面IDを輪郭取得部14b及び/又は基準断面輪郭取得部14cへ出力する。このように、交点のZ座標のうち最もZ座標が大きい面IDを選択して出力するのは、利用者が画面の奥側に表示される部分形状を指定する意図を持っている事態は想定されにくいからである。なお、以下では、利用者によって指定された起点から3Dモデルの視点方向へ向かう直線のことを「起点対応線」と呼ぶ。さらに、以下では、起点対応線と交わるポリゴンのうち、最もZ座標が大きいポリゴンのことを「起点対応面」と呼ぶ。
【0062】
また、起点対応線と起点対応面との交点が起点対応面の頂点または辺である場合には、同一の交点で1つの起点対応線に対し、複数の起点対応面が発生することになる。この場合には、起点対応面の中で最も面が大きいものや交点となった頂点が共有する二辺の角度が最も大きい起点対応面だけに交点が含まれるように起点の2次元座標をシフトさせた上で交差判定テーブルのテーブル値が再計算されるものとする。
【0063】
図2の説明に戻り、輪郭取得部14bは、起点対応面取得部14aによって取得された面IDを持つポリゴンから派生する輪郭を取得する処理部である。すなわち、輪郭取得部14bは、起点対応面取得部14aによって取得された起点対応面であるポリゴンから派生する輪郭がなだらかである限りは、1つの部分モデルとして纏めるに相応しい形状が続くものとしてその輪郭を取得する。なぜなら、3Dモデルでは、略平行な面が凸凹によって分割された状態で部分モデルとして区分けされるのが好ましいからである。この輪郭取得部14bによる輪郭の取得結果は、後述の基準断面輪郭取得部14cによって取得された基準断面を後述の拡張処理部14eが拡張するにあたってどこまで拡張するのかを決定する基準として用いられる。
【0064】
これを説明すると、輪郭取得部14bは、面テーブルを用いて辺テーブルを生成し、さらには、辺テーブルを用いて輪郭テーブルを生成することにより、1つの部分モデルとして纏めるに相応しい形状が続く輪郭を取得する。
【0065】
辺テーブルは、ポリゴンの一辺を一意に特定するための辺IDごとにその線分を定義する2つの頂点の点ID、一辺を共有する2つのポリゴンの面IDを記憶したテーブルである。図8は、辺テーブルに記憶される情報の構成例を示す図である。図8に示す例では、辺ID「0」の辺が点ID「0」及び点ID「1」の2つの頂点によって定義されるとともに、面ID「0」及び面ID「1」の2つのポリゴンによって共有されることを示す。なお、この図9で点ID及び面IDの末尾に付される括弧付きの番号は、テーブルへ登録された順序を指し、(1)であれば1つ目、(2)であれば2つ目であること示す。かかる登録順序は、テーブル使用時の処理結果に及ぼすものではなく、必ずしも区別して登録される必要はない。
【0066】
ここで、3Dモデルが3角形ポリゴンによって表現される場合には、ポリゴンの一辺を3つの面が共有した状態、いわゆる三面稜線が存在しない。このため、3Dモデルに空洞がなく閉じていれば、ポリゴンの一辺は、隣接する2つのポリゴンによって共有される。それゆえ、三辺を含む1つのポリゴンは、3つの隣り合う面を併せ持つ。
【0067】
このような3角形ポリゴンの特性から、輪郭を取得するに際して一方のポリゴンと隣接する他方のポリゴンを検索するに際して、2つのポリゴンが共有する辺を予め保持しておけば、隣接するポリゴンの検索効率を高めることができる。これを実現するために、輪郭取得部14bは、輪郭テーブルを生成する前段階として、面テーブルから辺テーブルを生成する。
【0068】
これを説明すると、まず、輪郭取得部14bは、図6に示した面テーブルから2つの点IDを抽出する。例えば、辺テーブルの生成処理の開始段階では、輪郭取得部14bは、任意の面IDに記憶された任意の点IDのペアを抽出することができる。そして、輪郭取得部14bは、先に抽出した2つの点IDを持つレコードが辺テーブルへ既に登録されているか否かを判定する。なお、面テーブルは、記憶部13に3Dモデルデータ13bとして予め記憶されたものである。
【0069】
このとき、辺テーブルに既に登録されていた場合には、辺テーブルに1つの辺を重複登録することになる。このため、輪郭取得部14bは、今回抽出した点IDのペアについては辺テーブルへの登録を行わない。
【0070】
一方、辺テーブルに未だ登録されていない場合には、輪郭取得部14bは、先に2つの点IDを抽出した面IDとは別の面IDを持ち、かつ先に抽出した2つの点IDの両方をレコード内に含む面IDを面テーブルから抽出する。続いて、輪郭取得部14bは、新しい辺IDを採番する。そして、輪郭取得部14bは、新たに採番した辺IDに対応付けて同一の点IDのペアをレコードに含む2つの面IDを辺テーブルへ登録する。
【0071】
その後、輪郭取得部14bは、抽出対象とした面IDに対応する3つの頂点の点IDから全3通りを対象に点IDのペアの抽出を終了するまで、上記の辺テーブルへの登録を繰り返し行う。そして、抽出対象とした面IDから全3通りの点IDのペアの抽出が終了すると、輪郭取得部14bは、未だ点IDのペアの抽出対象としていない面IDを対象に点IDのペアの抽出を行い、上記の辺テーブルへの登録を繰り返し行う。その後、点IDのペアの抽出対象としていない面IDが面テーブルになくなった場合に、輪郭取得部14bは、辺テーブルの生成を終了する。
【0072】
なお、ここでは、輪郭取得部14bが面テーブルから辺テーブルを作成する場合を説明したが、開示の装置の適用範囲は、利用者からの操作受付時に辺テーブルを動的に生成することを限定されない。例えば、開示の装置または外部装置を含む他の装置によって予め生成された辺テーブルを記憶部13に格納しておくこともできる。
【0073】
次に、輪郭拡張候補テーブルの生成について説明する。まず、輪郭取得部14bは、起点対応面取得部14aによって取得された面IDのポリゴンが有する三辺の辺IDそれぞれを図8に示した辺テーブルから抽出する。続いて、輪郭取得部14bは、抽出した3つの辺IDを図示しない未処理の辺リストへ追加するとともに、面IDを図示しない処理済みの面リストへ追加する。なお、未処理の辺リスト及び処理済みの面リストは、制御部14内または記憶部13内の作業記憶領域に保持される。
【0074】
その後、輪郭取得部14bは、未処理の辺リストに含まれる1つの辺IDを対象に、辺テーブルから隣接する2つのポリゴンの面IDを抽出する。このとき、輪郭取得部14bは、辺テーブルから面IDを抽出する際にキーとした辺IDを未処理の辺リストから削除する。
【0075】
そして、輪郭取得部14bは、2つの面IDそれぞれに対応する3つの頂点の座標位置を図5に示した点テーブルから抽出し、各面IDのポリゴンごとにその法線ベクトルを算出する。続いて、輪郭取得部14bは、2つのポリゴンの法線ベクトルから隣接する2つのポリゴンの内積を算出し、算出した内積が閾値以下であるか否かを判定する。なお、かかる法線ベクトルは、ポリゴンを形成する二辺のベクトルの外積によって求めることができる。例えば、3角形ポリゴンの3次元座標を(a,b,c)としたとき、法線ベクトルは、(a−b)×(c−b)で表される。なお、点テーブルは、記憶部13に3Dモデルデータ13bとして予め記憶されたものである。
【0076】
ここで、隣接する2つのポリゴンの内積が閾値未満である場合には、2つのポリゴンが略平行に近い角度にあるので、2つのポリゴンによってなだらかな形状が形成されていると推定できる。このため、輪郭取得部14bは、2つのポリゴンが共有する辺IDを1つの部分モデルとする輪郭とみなす。そして、輪郭取得部14bは、1つの部分モデルとみなす輪郭を一意に特定するための輪郭拡張候補IDにその輪郭とみなした辺ID及び面IDを対応付けたレコードを有する輪郭拡張候補テーブルを生成する。輪郭取得部14bは、このようにして生成した輪郭拡張候補テーブルを記憶部13の各種テーブルデータ13cへ登録する。なお、輪郭拡張候補テーブルが既に生成されている場合には、面ID及び辺IDを含んでなるレコードが新たに追加される。
【0077】
この輪郭拡張候補テーブルは、輪郭拡張候補IDごとにその輪郭に含まれるポリゴンの面ID及び辺IDを記憶したテーブルである。図9は、輪郭拡張候補テーブルに記憶される情報の構成例を示す図である。図9に示す例では、輪郭拡張候補ID「0」の輪郭の一部が面ID「0」の一辺をなす辺ID「0」によって形成されることを示す。なお、ここでは、辺IDが共有される輪郭のうち識別番号が小さい方の面IDのみを登録することとしたが、識別番号が大きい方の面IDを登録してもよいし、両方を登録することとしてもかまわない。
【0078】
一方、隣接する2つのポリゴンの内積が閾値以上である場合には、2つのポリゴンが略平行からは遠い角度にあるので、2つのポリゴンによってなだらかな形状が形成されていないと推定できる。このため、輪郭取得部14bは、2つのポリゴンが共有する辺IDを1つの部分モデルとする輪郭とはみなさない。この場合には、輪郭取得部14bは、輪郭拡張候補テーブルへの登録は行わない。
【0079】
なお、隣接する2つのポリゴンの内積と比較する閾値は、2つのポリゴンがなす角度をどの程度許容するかによって設計支援アプリの開発者または利用者が任意に設定することができる。かかる閾値は、その値を「1」に近付けるほど2つのポリゴンの間でなだらかな形状の変化しか認めずに輪郭を取得し、その値を「0」に近づけるほど2つのポリゴンの間で急峻な形状の変化も認めるように輪郭を取得することができる。
【0080】
その後、輪郭取得部14bは、隣接する2つのポリゴンの面IDの中に処理済みの面リストに未登録である面IDが存在するか否かを判定する。このとき、処理済みの面リストに未登録である面IDがある場合には、輪郭取得部14bは、その面IDのポリゴンを形成する三辺のうち、今回に辺テーブルから面IDを抽出する際にキーとした辺IDを除く、残りの二辺の辺IDを未処理の辺リストへ追加する。そして、輪郭取得部14bは、未処理の辺リストへ辺IDを追加するのに使用した面IDを処理済みの面リストへ登録する。その後、輪郭取得部14bは、未処理の辺リストに登録された辺IDが空になるまで、未処理の辺リストに登録された辺IDを用いて輪郭拡張候補テーブルへの面ID及び辺IDの登録を繰り返し行う。
【0081】
なお、輪郭取得部14bは、1つの輪郭を取得した後にさらなる拡張を行った輪郭を得るために拡張後の輪郭に新たな輪郭拡張候補IDを採番した上で1つの部分モデルとみなす辺ID及び面IDを新たに探索する。かかる探索は、3Dモデル上の全ての辺ID及び面IDが輪郭拡張候補テーブルに登録されるまで繰り返し行われる。
【0082】
また、後述の拡張処理部14eでは、輪郭取得部14bによる輪郭の取得結果を用いずとも他の拡張手法を適用することも可能であるため、輪郭取得部14bを省略して情報検索装置10を構成することもできる。
【0083】
図2の説明に戻り、基準断面輪郭取得部14cは、3Dモデルを分断する基準断面の輪郭を取得する処理部である。ここで言う基準断面とは、起点対応線と起点対応面の交点を含む断面の中でも、後述の拡張処理部14eによって断面が移動される際に初期位置とさせる断面のことを指す。また、基準断面の輪郭とは、基準断面とポリゴンの辺とが交わる輪郭点を隣り合う輪郭点間で結合することにより形成される図形の形状を指す。
【0084】
これを説明すると、基準断面輪郭取得部14cは、起点対応線と起点対応面の交点を含む断面は無数に存在するので、所定の取得基準にしたがって基準断面の候補とする断面候補を取得する。かかる断面候補の取得基準の一例としては、起点対応線を回転軸とした面を回転軸を中心に所定の角度ずつ回転させることにより得られた断面を断面候補とすることが挙げられる。また、別の取得基準の一例としては、X軸に平行な断面、Y軸に平行な断面、さらにはZ軸に平行な断面を断面候補とすることが挙げられる。なお、断面候補の取得時には、各断面候補に断面候補の輪郭を一意に特定するための輪郭IDが採番される。
【0085】
図10及び図11は、断面候補の取得要領を説明するための説明図である。図10及び図11に示す符号20A及び符号20Bは、3Dモデルの一例を示す。図10及び図11に示す符号P1及び符号P2は、起点対応線が起点対応面に交わる交点を示す。図10に示す符号aは、断面候補を得るために使用する起点対応線と同軸の回転軸を示す。図10に示す符号22A、符号23A、符号24A、符号22B、符号23B及び符号24Bは、3Dモデル20Aまたは20Bを分断する断面の一例を示す。
【0086】
例えば、図10に示す例で言えば、基準断面輪郭取得部14cは、回転軸aを中心に面を所定の角度ずつ回転させることにより得られる断面を得る。このようにして得られた断面22A、断面23A及び断面24Aは、基準断面輪郭取得部14cによって断面候補とされる。これら断面22A、断面23A及び断面24Aは、いずれも回転軸aとともに交点P1を含む。このとき、基準断面輪郭取得部14cは、制御部14内または記憶部13内の作業記憶領域へ各断面候補の法線ベクトルを保存する。なお、図10に示す例では、所定の角度ずつ回転させることにより得た断面のうち3つの断面を図示したものであり、この断面候補の取得基準で得られる断面の数を限定するものではない。このように、回転軸aを中心に回転させて断面を得る場合には、回転させる角度を細かくするほど多くの断面を断面候補として得ることができる。
【0087】
また、図11に示す例で言えば、基準断面輪郭取得部14cは、交点P2を含む断面であり、X軸に平行な断面22B、Y軸に平行な断面23B及びZ軸に平行な断面24Bを取得する。このようにして得られた断面22B、断面23B及び断面24Bが基準断面輪郭取得部14cによって断面候補とされる。このとき、基準断面輪郭取得部14cは、制御部14内または記憶部13内の作業記憶領域へ各断面候補の法線ベクトルを保存する。なお、図11に示す例では、X軸、Y軸及びZ軸に平行な面3つを図示したものであり、この断面候補の取得基準で得られる断面の数を限定するものではなく、また、断面候補を得るための軸を上記の3つの軸に限定するものでもない。このように、所定の軸に平行な断面を得る場合には、任意の方向に任意の数の軸を設定することができる。
【0088】
このようにして断面候補を取得した後に、基準断面輪郭取得部14cは、断面候補とポリゴンの辺とが交わる交点を算出する。この交点は、断面候補の輪郭の一部を形成する点であるから以下では「輪郭点」と呼ぶこととする。そして、基準断面輪郭取得部14cは、断面候補上で1つのポリゴンの二辺が交わる輪郭点同士をそれぞれ結合することにより、断面候補の輪郭を取得する。
【0089】
かかる断面候補の輪郭の取得要領を説明する。まず、基準断面輪郭取得部14cは、起点対応面と断面候補とが交わる輪郭点を算出する。これを説明すると、基準断面輪郭取得部14cは、起点対応面取得部14aによって取得された起点対応面の面IDに紐付けられた3つの頂点の点IDを図6に示した面テーブルから取り出す。続いて、基準断面取得部14cは、面テーブルから取り出した3つの頂点の点IDの座標を図5に示した点テーブルから取り出す。そして、基準断面輪郭取得部14cは、点テーブルから取り出した3つの点IDの座標を用いて、起点対応面と断面候補との輪郭点を算出する。
【0090】
このように、起点対応面が断面候補と交わる輪郭点を始めに算出するのは、起点対応面及び断面候補が交点を含むことから、起点対応面であるポリゴンを形成する三辺のうち二辺が断面候補と交わることが明らかであるからである。これによって、基準断面輪郭取得部14cは、3Dモデルを形成するポリゴンの中から断面候補と交わる辺を有するポリゴンを検索する手順を省略する。
【0091】
このとき、起点対応面のポリゴンが有する三辺の中で少なくとも一辺は、断面候補とは交差しない。また、起点対応面取得部14aの説明で述べたように、起点対応面取得部14aは、同一の交点で1つの起点対応線に対し、複数の起点対応面が発生しないように起点をシフトさせるので、起点対応面の頂点や辺だけが断面候補と交わることもない。したがって、起点対応面のポリゴンが有する三辺のうち二辺が断面候補と交わることになる。それゆえ、起点対応面の各辺と断面候補との輪郭点を算出する際には、起点対応面の三辺のうちどの二辺が断面候補との間で交わるのかを確認するのが好ましい。
【0092】
例えば、起点対応線と起点対応面との交点の座標が(p,p,p)であるとしたとき、断面候補の方程式は、下記の式(10)になる。なお、下記の式(10)における(a,b,c)は、基準断面輪郭取得部14cが断面候補の取得基準により取得した方線ベクトルである。
【0093】
【数10】

【0094】
そして、ポリゴンの一辺の線分を形成する2つの頂点の座標を(Ax,Ay,Az)、(Bx,By,Bz)としたとき、上記の式(10)を変形することにより下記の式(11)が得られる。基準断面輪郭取得部14cは、下記の式(11)を用いることにより、断面候補とポリゴンの辺とが交わるか否かの交差判定を行うことができる。
【0095】
【数11】

【0096】
例えば、点テーブルから取り出した起点対応面を形成する一辺のうち、一方の頂点の座標が(Ax,Ay,Az)であり、他方の頂点の座標が(Bx,By,Bz)であるとする。この場合、基準断面輪郭取得部14cは、これら2つの頂点の座標(Ax,Ay,Az)及び(Bx,By,Bz)を式(11)に代入することにより、断面候補と起点対応面の辺との交差判定を行う。このとき、基準断面輪郭取得部14cは、式(11)で算出されたtの値が0≦t≦1の場合には、断面候補と起点対応面の辺とが交わるものと判定する。
【0097】
このように、基準断面輪郭取得部14cは、起点対応面を形成する三辺それぞれについて交差判定を行った上で、起点対応面の三辺のうち断面候補と交わる二辺の輪郭点及び輪郭辺を算出する。
【0098】
その後、基準断面輪郭取得部14cは、輪郭点、輪郭辺及びその算出に使用した面IDなどの情報を用いて、図示しない処理済み面リスト、輪郭点テーブル及び輪郭辺テーブルを更新する。
【0099】
かかる更新の一例を挙げれば、基準断面輪郭取得部14cは、今回に輪郭点及び輪郭辺を算出し終えた起点対応面の面IDを図示しない処理済み面リストへ登録する。この処理済み面リストは、断面候補の輪郭点及び輪郭辺の算出に使用し終わったポリゴンの面IDのリストである。処理済み面リストは、制御部14内または記憶部13内の作業記憶領域に保持される。
【0100】
さらに、基準断面輪郭取得部14cは、輪郭点を一意に特定するための輪郭点ID及び輪郭辺を一意に特定するための輪郭点IDを今回に算出した輪郭点及び輪郭辺に採番する。そして、基準断面輪郭取得部14cは、採番した輪郭点IDに断面候補と交わる辺の辺ID及び輪郭点の座標を対応付けたレコードを有する輪郭点テーブルを記憶部13の各種テーブルデータ13cへ登録する。また、基準断面輪郭取得部14cは、現在に輪郭を取得中である断面候補の輪郭IDに対し、新たに採番した輪郭辺の輪郭辺ID、輪郭辺が含まれるポリゴンの面ID及び輪郭辺を定義する2つの輪郭点の輪郭点IDを対応付けたレコードを生成する。そして、基準断面輪郭取得部14cは、このようにして生成したレコードを有する輪郭辺テーブルを記憶部13の各種テーブルデータ13cへ登録する。なお、輪郭点テーブルまたは輪郭辺テーブルが既に生成されている場合には、輪郭点ID、辺ID及び輪郭点の座標を含んでなるレコード、或いは輪郭ID、輪郭辺ID、面ID、2つの輪郭点IDを含んでなるレコードが各テーブルに追加される。
【0101】
輪郭点テーブルは、輪郭点IDごとに辺ID及び輪郭点の座標を記憶したテーブルである。図12は、輪郭点テーブルに記憶される情報の構成例を示す図である。図12に示す例では、輪郭点ID「0」の輪郭点が辺ID「0」の辺と断面候補とが交わる交点であり、その座標が(10,15,−5)であることを示す。また、輪郭点ID「1」の輪郭点が辺ID「1」の辺と断面候補とが交わる交点であり、その座標が(10,5,0)であることを示す。
【0102】
輪郭辺テーブルは、輪郭IDごとに輪郭辺ID、面ID、輪郭辺を定義する2つの輪郭点の輪郭点IDを記憶したテーブルである。図13は、輪郭辺テーブルに記憶される情報の構成例を示す図である。図13に示す例では、輪郭ID「0」を持つ断面候補の輪郭の一部を形成する輪郭辺ID「0」の輪郭辺が、面ID「0」のポリゴンに内包されるとともに輪郭点ID「0」及び輪郭点ID「1」の2つの点により定義されることを示す。なお、この図13で輪郭点IDの末尾に付される括弧付きの番号は、テーブルへ登録された順序を指し、(1)であれば1つ目、(2)であれば2つ目であること示す。かかる登録順序は、テーブル使用時の処理結果に及ぼすものではなく、必ずしも区別して登録される必要はない。
【0103】
これら処理済み面リスト、輪郭点テーブル及び輪郭辺テーブルの更新を終えると、基準断面輪郭取得部14cは、起点対応面の三辺のうち断面候補と交わる二辺について各辺が共有される面の面IDを図8に示した辺テーブルから取り出す。このように、断面候補と交わる二辺が共有される面を取り出すのは、その二辺が共有されるポリゴンを探索すれば、3Dポリゴンの全ての辺を対象に交差判定を行わずとも断面候補と交わる二辺を有するポリゴンを見つけ出すことができるからである。
【0104】
そして、基準断面輪郭取得部14cは、辺テーブルから取り出した面IDのうち処理済み面リストに登録がない面IDだけを図示しない未処理の面リストへ登録する。この未処理の面リストは、断面候補の輪郭点及び輪郭辺を含むポリゴンでありながらも未だ算出に使用されていないポリゴンの面IDのリストである。この未処理の面リストは、制御部14内または記憶部13内の作業記憶領域に保持される。
【0105】
このように、基準断面輪郭取得部14cは、未処理の面リストの面IDが空になるまで、起点対応面に行ったように、処理済みの面リスト、輪郭点テーブル、輪郭辺テーブル及び未処理の面リストを更新し続ける。その後、未処理の面リストの面IDが空になった場合には、断面候補と交わる全てのポリゴンを対象にその輪郭を取得したことになるので、基準断面輪郭取得部14cは、各輪郭辺の長さを足し合わせることにより、断面候補の輪郭距離を算出する。なお、断面候補の輪郭距離とは、断面候補が各ポリゴンと交わる輪郭辺の集計値を指す。
【0106】
ここで、輪郭点、輪郭辺及び輪郭距離の算出要領について説明する。図14は、輪郭点、輪郭辺及び輪郭距離の算出要領を説明するための説明図である。図14に示す符号40は、断面候補の一例を示す。図14に示す符号41は、断面候補40の方線ベクトルを示す。図14に示す符号42は、3Dモデルに含まれるポリゴンのうち断面候補40と交わるポリゴンを示す。図14に示す符号43A、符号43B及び符号43Cは、ポリゴン42の3つの頂点のうち断面候補40と交わる線分を形成する頂点を示す。図14に示す符号P及び符号Pは、断面候補40とポリゴン42の辺とが交わる輪郭点を示す。図14に示す符号Lは、輪郭点P及び輪郭点Pを結ぶ直線である輪郭辺を示す。なお、図14に示す例では、断面候補40と交わるポリゴンであれば起点対応面でなくとも輪郭点及び輪郭辺が算出される方法に違いはないので、符号42が指すポリゴンが断面候補40と交わるポリゴン全般を指すものとして以下の説明を行うこととする。
【0107】
図14に示す例で言えば、基準断面輪郭取得部14cは、上述した交差判定により、断面候補40と頂点43A及び頂点43Bを結ぶポリゴン42の辺とが輪郭点Pで交わることを確認する。さらに、基準断面輪郭取得部14cは、断面候補40と頂点43C及び頂点43Bを結ぶポリゴン42の辺とが輪郭点Pで交わることを確認する。そして、基準断面輪郭取得部14cは、頂点43Aの座標、頂点43Bの座標及び式(11)で求めたtの値を用いて、輪郭点Pの座標(Ax+t(Bx−Ax),Ay+t(By−Ay),Az+t(Bz−Az))を算出する。さらに、基準断面輪郭取得部14cは、頂点43Cの座標、頂点43Bの座標及び式(11)で求めたtの値を用いて、輪郭点Pの座標(Cx+t(Bx−Cx),Cy+t(By−Cy),Cz+t(Bz−Cz))を算出する。
【0108】
これら輪郭点P及び輪郭点Pの算出後に、基準断面輪郭取得部14cは、下記の式(12)が示すユークリッド距離の算出式を用いて、輪郭点P及び輪郭点Pを結ぶ輪郭辺Lの長さd、すなわち輪郭点間の距離を算出する。
【0109】
【数12】

【0110】
上記の式(12)に輪郭点Pの座標及び輪郭点Pの座標それぞれを代入することにより、基準断面輪郭取得部14cは、輪郭辺の長さdを算出する。その後、断面候補40と交わる全てのポリゴン42について輪郭点及び輪郭辺の長さを算出した場合には、各輪郭辺Lの長さを集計することにより、断面候補40の輪郭距離を算出する。そして、基準断面輪郭取得部14cは、断面候補40の輪郭IDに断面候補40の法線ベクトル及び輪郭距離を対応付けたレコードを有する輪郭テーブルを記憶部13の各種テーブルデータ13cへ登録する。なお、輪郭テーブルが既に生成されている場合には、輪郭ID、法線ベクトル及び輪郭距離を含んでなるレコードが新たに追加される。
【0111】
この輪郭テーブルは、断面候補の輪郭IDごとに断面候補の法線ベクトル及び輪郭距離を記憶したテーブルである。図15は、輪郭テーブルに記憶される情報の構成例を示す図である。図15に示す例で言えば、輪郭ID「0」を持つ断面候補の法線ベクトルが(0.5,0.2,−0.3)であり、断面候補の輪郭距離が15.5であることを示す。
【0112】
なお、ここでは、ユークリッド距離を用いて輪郭距離を算出する場合を説明したが、他の方法を用いて輪郭距離を算出することもできる。例えば、断面候補の法線ベクトルを等間隔に設定したり、図9に示した輪郭拡張候補テーブルを利用したり、また、各輪郭辺に水平または垂直であるベクトルであり、かつ断面候補の法線ベクトルにも垂直なベクトルだけを利用する方法もある。例えば、法線ベクトルを等間隔に設定する場合には、法線ベクトル(a,b,c)をa=cosθcosφ、b=cosθsinφ、c=sinφへ置き換えると、角度θ、角度φの2つの変数を等間隔に設定することで、等角度で法線を決定できる。
【0113】
このようにして、基準断面輪郭取得部14cは、全ての断面候補の輪郭距離を算出するまで、輪郭点、輪郭辺、ひいては輪郭距離の算出を繰り返し行う。その上で、基準断面輪郭取得部14cは、全断面候補の輪郭距離のうち最も輪郭距離が小さい断面候補を基準断面と決定する。図10に示した例で言えば、基準断面輪郭取得部14cは、断面候補22A、断面候補23A及び断面候補24Aのうち輪郭距離が最も小さい断面候補24Aを基準断面として決定する。また、図11に示した例で言えば、基準断面輪郭取得部14cは、断面候補22B、断面候補23B及び断面候補24Bのうち輪郭距離が最も小さい断面候補24Bを基準断面として決定する。これによって、3Dモデルを分断する断面候補の中でも断面候補22A、断面候補23A、断面候補22B及び断面候補23Bのように歪な断面候補が基準断面として決定される事態を防止できる。
【0114】
このとき、基準断面輪郭取得部14cは、基準断面に決定した断面候補の輪郭ID以外の輪郭IDに関する情報を輪郭点テーブル、輪郭辺テーブル及び輪郭テーブルから消去し、基準断面の輪郭IDの輪郭に関する情報だけを残す。なお、ここでは、輪郭距離が最も小さい断面候補を基準断面とする場合を説明したが、各断面候補の断面積を求め、断面積が最も小さい断面候補を基準断面としてもかまわない。
【0115】
図2の説明に戻り、拡張方向決定部14dは、基準断面輪郭取得部14cによって決定された基準断面と直交する2方向のうちいずれの方向に断面を拡張させるのかを決定する処理部である。すなわち、拡張方向決定部14dは、基準断面によって3Dモデルが分断された複数の立体のうち最も小さい立体へ向かう方向を拡張方向として決定する。なお、ここでは、3Dモデルが2つの立体に分断される場合を想定し、2つの立体の大きさを比較する基準として各立体の体積を求める場合を例示して以下の説明を行う。また、以下では、基準断面によって分断された3Dモデルのうち一方の立体を第1の立体と呼び、他方の立体を第2の立体と呼ぶこととする。
【0116】
例えば、拡張方向決定部14dは、下記の式(13)を用いて、立体の体積を算出する。下記の式(13)では、Pi1、Pi2、Pi3が立体に含まれる任意のポリゴンiの3つの頂点を指し、Cが立体の重心点を指し、また、Vが立体の体積を指すものとする。なお、上記の式(13)は、空洞がなく閉じたモデルに好適に使用できる算出式である。このため、基準断面によって分断される第1の立体及び第2の立体に適用するには、基準断面輪郭取得部14cによって取得された基準断面の輪郭を閉じるのが好ましい。この輪郭を閉じる処理の詳細は、後述の部分モデル生成部14fで説明することとし、ここでは基準断面が閉じられたものとして説明を進める。なお、重心点Cの座標については、既知の任意の方法を用いて算出できる。
【0117】
【数13】

【0118】
上記の式(13)に第1の立体に含まれるポリゴンiの各頂点の座標及び重心点Cの座標を代入して各ポリゴンiの体積を足し合わせることにより、拡張方向決定部14dは、第1の立体の体積V1を算出する。
【0119】
これを説明すると、拡張方向決定部14dは、図13に示した輪郭辺テーブルに登録されている面IDの面、すなわち基準断面の輪郭辺を含むポリゴンを体積の算出対象から除外する。かかる算出対象からの除外は、既にポリゴンの体積の足し合わせが終了したポリゴンの面IDを記憶する図示しない計算済み面リストに基準断面の輪郭辺を含むポリゴンの面IDを処理開始段階から登録することにより実現される。なお、輪郭辺テーブルは、記憶部13に各種テーブルデータ13cとして基準断面輪郭取得部14cにより登録されたものである。また、計算済み面リストは、制御部14内または記憶部13内の作業記憶領域に保持される。
【0120】
その上で、拡張方向決定部14dは、基準断面よりも第1の立体側に所在するポリゴンの面IDを図8に示した辺テーブルから取り出す。そして、拡張方向決定部14dは、辺テーブルから取り出したポリゴンが基準断面よりも第1の立体側に存在するか否かを確認する。なお、辺テーブルは、記憶部13に各種テーブルデータ13cとして登録されたものである。
【0121】
かかる確認手法の一例としては、上記の式(10)に示した基準断面の方程式へポリゴンの3次元座標を代入することにより容易に確かめることができる。すなわち、式(10)にポリゴンの3次元座標を代入することにより得られた算出結果が「正」、「負」または「0」のいずれであるかによって第1の立体側、基準断面及び第2の立体側のいずれにポリゴンの頂点が存在するかを特定できる。
【0122】
ここでは、仮に算出結果が「正」である場合にポリゴンの頂点が第1の立体側に所在するものとして説明を続ける。この場合には、算出結果が「正」であるならばポリゴンの頂点が第1の立体側に存在し、算出結果が「0」であるならばポリゴンの頂点が基準断面上に存在し、また、算出結果が「負」であるならばポリゴンの頂点が第2の立体側に存在することが判明する。このような確認を辺テーブルから取り出した面IDに対応する全ての点IDに対して行い、3つの頂点を式(10)に代入した時の算出結果が3つとも「正」であるポリゴンを体積の算出対象として使用する。この辺テーブルから取り出すポリゴンは、基準断面よりも第1の立体側に存在するものであれば任意のポリゴンでかまわない。なお、第2の立体の体積を算出する場合には、3つの頂点を式(10)に代入した時の算出結果が3つとも「負」であるポリゴンを体積の算出対象として使用すればよい。
【0123】
その後、拡張方向決定部14dは、式(13)を用いて、辺テーブルから取り出したポリゴンが持つ体積を算出し、算出した体積を前回までに累積された累積値に加算する。そして、拡張方向決定部14dは、今回に体積の加算を行ったポリゴンの面IDを計算済み面リストへ登録する。これを説明すると、拡張方向決定部14dは、辺テーブルから取り出した面IDに対応する3つの点ID(1)、点ID(2)及び点ID(3)を図6に示した面テーブルから取り出す。さらに、拡張方向決定部14dは、面テーブルから取り出した3つの点IDに対応する座標を図5に示した点テーブルから取り出す。その上で、拡張方向決定部14dは、今回に取り出したポリゴンの3つの頂点の座標を式(13)に代入してそのポリゴンの体積を前回までに累積されていた累積値に加算する。
【0124】
続いて、拡張方向決定部14dは、今回に体積の加算を行ったポリゴンの面IDと隣り合うポリゴンの面IDの中に計算済み面リストに登録がない面IDが存在するか否かを判定する。その後、隣り合うポリゴンの面IDが全て計算済み面リストに登録されたと判定するまで処理を繰り返し行う。すなわち、拡張方向決定部14dは、隣り合うポリゴンの面IDのうち計算済み面リストに登録がない面IDのポリゴンを対象にそのポリゴンの体積の算出及びその体積の累積値への加算を行う。そして、隣り合うポリゴンの面IDが全て計算済み面リストに登録された場合には、拡張方向決定部14dは、第1の立体に含まれるポリゴンの体積が全て加算された状態となるので、それまでに加算された累積値を第1の立体の体積V1として保存する。
【0125】
このようにして第1の立体の体積V1を算出した後に、拡張方向決定部14dは、同様にして、第2の立体の体積V2を算出する。なお、ここでは、第1の立体の体積V1を算出してから第2の立体の体積V2を算出することとしたが、必ずしも第1の立体の体積を算出する必要はない。例えば、第2の立体の体積を先に算出することもできる。また、第1の立体の体積と第2の立体の体積とを並列的に算出することもできる。
【0126】
ここで、拡張方向決定部14dは、第1の立体の体積と第2の立体の体積と比較し、第1の立体及び第2の立体のうち体積が小さい立体を特定し、基準断面から体積が小さい立体へ向かう方向を拡張方向として決定する。なお、ここでは、3Dモデルが基準断面によって2つに分断される場合を例示したが、開示の装置の適用範囲がこれに限定されるものではない。例えば、3Dモデルが3つ以上に分断される場合にも、基準断面から最も体積が小さい立体へ向かう方向を拡張方向とすればよい。
【0127】
また、ここでは、第1の立体及び第2の立体の体積を算出する場合を例示したが、必ずしも立体の体積を求める必要はない。例えば、拡張方向決定部14dは、立体の体積の代わりに立体の表面積を算出することもできる。このように立体の表面積を算出する場合には、下記の式(14)を用いることにより、第1の立体及び第2の立体の表面積を算出することができる。下記の式(14)では、Pi1、Pi2、Pi3が立体に含まれる任意のポリゴンiの3つの頂点を指し、また、Sが立体の体積を指すものとする。
【0128】
【数14】

【0129】
上記の式(14)に第1の立体に含まれるポリゴンiの各頂点の座標を代入して各ポリゴンiの表面積を足し合わせることにより、拡張方向決定部14dは、第1の立体の表面積S1を算出する。また、同様にして、拡張方向決定部14dは、第2の立体の表面積S2を算出することができる。このように、立体の表面積を算出することとした場合には、立体の算出する場合よりも演算量をさらに削減できる。
【0130】
図2の説明に戻り、拡張処理部14eは、所定の拡張規定にしたがって、基準断面輪郭取得部14cによって決定された基準断面から拡張方向決定部14dによって決定された拡張方向へ断面を拡張させる処理部である。ここで言う拡張規定としては、例えば基準断面と拡張後の断面との間で面の向きがズレるズレ許容度や断面を拡張させる拡張量などが規定される。
【0131】
例えば、面の向きのズレ許容度がゼロに規定されている場合には、拡張処理部14eは、基準断面から拡張方向へ断面を平行移動させる。このように断面を平行移動させる場合には、上記の式(10)に示した基準断面の方程式を規定する点(p,p,p)を法線ベクトル(a,b,c)の方向に移動させる。つまり、拡張処理部14eは、基準断面の向きを法線ベクトルの方向に固定したままで断面を移動させることになる。例えば、拡張処理部14eは、拡張量を規定するパラメータ(parameter)をtとし、上記の式(10)を下記の式(15)に示すように変形することができる。これによって断面を平行移動した断面の方程式を得ることができる。
【0132】
【数15】

【0133】
上記の式(15)を用いて、拡張処理部14eは、平行移動後の断面の輪郭について輪郭点テーブル、輪郭辺テーブル及び輪郭テーブルを生成する。これら輪郭点テーブル、輪郭辺テーブル及び輪郭テーブルは、基準断面のものとは別に拡張後断面用のテーブルとして構成される。なお、かかる移動後の断面の輪郭は、基準断面の輪郭を取得する場合と同じ要領で取得できるので、ここではその説明を省略する。
【0134】
なお、拡張量パラメータtには、固定値を予め規定したり、また、3Dモデルの規模や部品の種類に応じてデフォルト(default)値を適切に補正した値を規定したりすることもできる。例えば、デフォルト値を変更する場合には、3Dモデルの規模が大きいほどデフォルト値も大きくなるように補正する。これによって、後述の部分モデル生成部14fにより生成される部分モデルが極小なものとなり、3Dモデルを特徴付ける部分形状を含まない部分モデルが生成されることを防止できる。
【0135】
また、面の向きのズレ許容度がゼロ以外に設定されている場合には、拡張処理部14eは、基準断面との間で面の向きが所定の角度まで変化することを許容しながら断面を拡張させる。すなわち、拡張処理部14eは、基準断面の向きを法線ベクトルの方向に固定せずに、基準断面の法線ベクトルとの間で差分が設けられた複数の法線ベクトルを持つ断面それぞれを移動させることになる。この場合には、拡張処理部14eは、拡張量を規定するパラメータ(parameter)をtとし、上記の式(10)を下記の式(16)に示すように変形する。これによって面の向きのズレを許容した複数の断面の方程式を得ることができる。
【0136】
【数16】

【0137】
ここで、上記の式(16)に示すa´、b´及びc´は、基準断面の法線ベクトルと拡張後の法線ベクトルとの間で差分を設けるための法線差分である。これら法線差分a´、法線差分b´及び法線差分c´は、基準断面の法線ベクトルからX方向、Y方向及び/又はZ方向にどの程度傾けるかを複数の組合せに分けて設定することができる。かかる法線差分は、設計支援アプリの利用者または開発者が任意の値及び任意の組合せ数を設定できる。
【0138】
上記の式(16)を用いて、拡張処理部14eは、法線ベクトルに法線差分を設けた断面ごとに、拡張後の断面の輪郭について輪郭点テーブル、輪郭辺テーブル及び輪郭テーブルを生成する。ここで、かかる拡張後の断面の輪郭は、基準断面の輪郭を取得する場合と同じ要領で取得できる。ただし、拡張処理部14eは、拡張後の断面の輪郭が複数得られるので、法線差分を設けた各断面の輪郭距離を図16に示す輪郭計算テーブルへ登録する。そして、拡張処理部14eは、輪郭計算テーブルに記憶された断面の中で最も輪郭距離が小さい断面を部分モデルの生成対象として採用する。
【0139】
この輪郭計算テーブルは、法線ベクトル、法線差分及び輪郭距離を対応付けて記憶したテーブルである。図16は、輪郭計算テーブルに記憶される情報の構成例を示す図である。図16に示す例では、基準断面の法線ベクトル(0.5,0.2,−0.3)に法線差分(0.1,0,0)を設けた場合には、断面の拡張後の輪郭距離が16であったことを示す。また、図16に示す例では、基準断面の法線ベクトル(0.5,0.2,−0.3)に法線差分(0,0.1,0)を設けた場合には、断面の拡張後の輪郭距離が14.2であったことを示す。これら2つのレコードから部分モデルの生成対象とする断面を選択する場合には、拡張処理部14eによって2つ目のレコードが選択される。
【0140】
ここで、拡張処理部14eは、拡張後の断面の輪郭を1度取得しただけで断面の拡張を終えるわけではない。すなわち、拡張処理部14eは、未だ移動が完了していない3Dモデルの輪郭が存在する限りは、前回の拡張に使用した拡張量よりも大きい拡張量に今回の拡張量を増加させた上で断面の拡張を継続する。なお、拡張量を増加させる割合は、固定値を予め規定したり、また、3Dモデルの規模や部品の種類に応じてデフォルト値を適切に補正した値を規定したりすることができる。
【0141】
これを説明すると、拡張処理部14eは、断面の拡張後に輪郭が存在するか否かを判定する。すなわち、拡張処理部14eは、今回に生成した輪郭点テーブルに輪郭点が登録されているか否かを判定する。なお、ここでは、輪郭点IDを用いて拡張後の断面における輪郭の有無を判定することとしたが、輪郭辺ID或いは輪郭距離を用いて、拡張後の断面における輪郭の有無を判定することとしてもよい。
【0142】
このとき、今回に生成した輪郭点テーブルに輪郭点IDが登録されている場合には、3Dモデルの拡張方向に未だ輪郭が取得されていないポリゴンが存在する余地がある。それゆえ、拡張処理部14eは、前回の拡張よりも拡張量を増加させた上で基準断面から拡張方向への断面をさらに拡張させる。
【0143】
一方、今回に生成した輪郭点テーブルに輪郭点IDが登録されていない場合には、3Dモデルの拡張方向には輪郭が未取得であるポリゴンが存在しない。したがって、拡張処理部14eは、拡張方向決定部14dによって決定された拡張方向、すなわち最初に拡張を行った拡張方向とは反対の方向に拡張方向を再決定する。その上で、拡張処理部14eは、基準断面から再決定後の拡張方向へ断面を拡張させ、拡張後の断面の輪郭について輪郭点テーブル、輪郭辺テーブル及び輪郭テーブルを取得する。その後、輪郭処理部14eは、再決定後の拡張方向に断面を拡張させ、断面の拡張後に輪郭が存在しなくなるまで断面の拡張を継続する。
【0144】
なお、ここでは、拡張量パラメータtを用いて断面を拡張させる場合を説明したが、必ずしも断面の方程式に拡張量パラメータtを組み込む必要はない。例えば、拡張処理部14eは、隣接する2つのポリゴンにおける面の曲率が所定値以下であるか否かによって断面の拡張を継続するか否かを判別することもできる。2つのポリゴンの面と面の角度は、下記の式(17)に示すように、面の法線ベクトルの内積から算出することができる。なお、下記の式(17)に示すθは、2つのポリゴンがなす角度を指す。
【0145】
【数17】

【0146】
上記の式(17)により、拡張処理部14eは、隣接する2つのポリゴンがなす角度θを算出できる。そして、拡張処理部14eは、起点対応面から拡張方向へ向かって角度θの算出を開始する。その後、拡張処理部14eは、角度θが所定値以下である限りは断面の拡張を継続し、角度θが所定値を超えるポリゴンが出現した時点でその直前に角度θを算出したポリゴンまでを基準断面の拡張量として決定することもできる。
【0147】
また、拡張処理部14eは、図9に示した輪郭拡張候補テーブルを用いて、断面を拡張することもできる。例えば、輪郭拡張候補テーブルに記憶された同一の輪郭拡張候補IDを取り出し、その輪郭拡張候補IDに対応する面IDのうち基準断面よりも拡張方向側に存在し、かつ起点対応線と起点対応面の交点から最も遠い頂点を持つポリゴンまでを拡張量としてもよい。
【0148】
図2の説明に戻り、部分モデル生成部14fは、基準断面輪郭取得部14cによって取得された基準断面と、拡張処理部14eによって移動された断面との間に形成される3Dモデルの部分形状を部分モデルとして生成する処理部である。
【0149】
これを説明すると、部分モデル生成部14fは、図13に示した輪郭辺テーブルに登録されている面IDの面、すなわち基準断面の輪郭辺を含むポリゴンを部分モデルとする対象から除外する。かかる対象除外は、既に部分形状の候補として探索したポリゴンの面IDを記憶する図示しない探索済みリストに基準断面の輪郭辺を含むポリゴンの面IDを処理開始段階から登録することにより実現される。なお、輪郭辺テーブルは、記憶部13に各種テーブルデータ13cとして基準断面輪郭取得部14cにより登録されたものである。また、探索済みリストは、制御部14内または記憶部13内の作業記憶領域に保持される。
【0150】
その上で、部分モデル生成部14fは、基準断面よりも拡張方向側に存在し、かつ拡張後の断面よりも拡張方向の反対側に存在するポリゴンの面IDを図8に示した辺テーブルから取り出す。そして、部分モデル生成部14fは、辺テーブルから取り出したポリゴンが基準断面よりも拡張方向側に存在し、かつ拡張後の断面よりも拡張方向の反対側に存在するか否かを確認する。なお、辺テーブルは、記憶部13に各種テーブルデータ13cとして登録されたものである。
【0151】
かかる確認手法の一例としては、上記の式(10)に示した基準断面の方程式及び上記の式(15)に示した拡張後の断面の方程式へポリゴンの3次元座標を代入することにより容易に確かめることができる。すなわち、式(10)及び式(15)にポリゴンの3次元座標を代入することにより得られた算出結果が「正」、「負」または「0」のいずれであるかによってポリゴンの頂点が3Dモデルのどの範囲に存在するかを特定できる。
【0152】
ここでは、仮に算出結果が「正」である場合にポリゴンの頂点が基準断面または拡張後の断面の拡張方向に所在するものとして説明を続ける。この場合には、式(10)における算出結果が「正」であるならばポリゴンの頂点が基準断面よりも拡張方向側に存在することが判明する。式(10)における算出結果が「0」であるならばポリゴンの頂点が基準断面上に存在することが判明する。また、式(10)における算出結果が「負」であるならばポリゴンの頂点が基準断面よりも拡張方向の反対側に存在することが判明する。一方、式(15)における算出結果が「正」であるならばポリゴンの頂点が拡張後の断面よりも拡張方向側に存在することが判明する。式(15)における算出結果が「0」であるならばポリゴンの頂点が拡張後の断面上に存在することが判明する。また、式(15)における算出結果が「負」であるならばポリゴンの頂点が拡張後の断面よりも拡張方向の反対側に存在することが判明する。
【0153】
このような確認を辺テーブルから取り出した面IDに対応する全ての点IDに対して行う。ここで、部分モデル生成部14fは、3つの頂点を式(10)に代入した時の算出結果が3つとも「正」であり、かつ3つの頂点を式(15)に代入した時の算出結果が3つとも「負」であるポリゴンを使用する。なお、拡張方向が再決定された場合には、3つの頂点を式(10)に代入した時の算出結果が3つとも「負」であり、かつ3つの頂点を式(15)に代入した時の算出結果が3つとも「正」であるポリゴンを使用すればよい。
【0154】
その後、部分モデル生成部14fは、部分モデルの候補とするポリゴンの面IDを記憶する図示しない部分モデル候補リストに辺テーブルから取り出したポリゴンの面IDを登録するとともにそのポリゴンの面IDを探索済みリストに登録する。なお、部分モデル候補リストは、制御部14内または記憶部13内の作業記憶領域に保持される。
【0155】
続いて、部分モデル生成部14fは、今回に探索したポリゴンの面IDと隣り合うポリゴンの面IDの中に探索済みリストに登録がない面IDが存在するか否かを判定する。その後、隣り合うポリゴンの面IDが全て探索済みリストに登録されたと判定するまで、部分モデル生成部14fは、隣り合うポリゴンの面IDのうち探索済みリストに登録がない面IDのポリゴンを対象に部分モデル候補リスト及び探索済みリストへの登録を行う。そして、隣り合うポリゴンの面IDが全て探索済みリストに登録された場合には、基準断面よりも拡張方向側に存在するポリゴンの面IDが全て探索された状態となる。なお、この時、探索済みリストに登録されていた面IDは消去される。
【0156】
その後、部分モデル生成部14fは、拡張後断面用の輪郭辺テーブルに登録されている面IDの面、すなわち拡張後の断面の輪郭辺を含むポリゴンの面IDを探索済みリストに登録する。続いて、部分モデル生成部14fは、拡張後の断面よりも拡張方向に存在するポリゴンの面IDを図8に示した辺テーブルから取り出す。なお、この場合には、ポリゴンの3つの頂点を式(15)に代入した時の算出結果が3つとも「正」であれば、ポリゴンが拡張後の断面よりも拡張方向に存在することが確認できる。
【0157】
そして、部分モデル生成部14fは、辺テーブルから取り出したポリゴンの面IDを部分モデル候補リストから消去する。続いて、部分モデル生成部14fは、辺テーブルから取り出したポリゴンの面IDを探索済みリストに登録する。
【0158】
続いて、部分モデル生成部14fは、今回探索したポリゴンの面IDと隣り合うポリゴンの面IDの中に探索済みリストに登録がない面IDが存在するか否かを判定する。その後、隣り合うポリゴンの面IDが全て探索済みリストに登録されたと判定するまで、部分モデル生成部14fは、隣り合うポリゴンの面IDのうち探索済みリストに登録がない面IDのポリゴンを対象に探索を繰り返す。すなわち、部分モデル生成部14fは、隣り合うポリゴンの面IDを部分モデル候補リストから消去するとともにその面IDを探索済みリストに登録する。そして、隣り合うポリゴンの面IDが全て探索済みリストに登録された場合には、拡張後の断面よりも拡張方向に存在するポリゴンの面IDが全て探索された状態となる。
【0159】
このように、基準断面に対する面の探索では、部分モデル候補リストへの登録を行う一方で、拡張後の断面に対する面の探索では、部分モデル候補リストからの削除を行うのは、面が閉じていない拡張後の断面に対して面の探索を行うのを防止するためである。これによって、基準断面以外は3Dモデルが閉じた状態で面の探索を行うことができ、面の探索し漏れが生じるのを防止できる。
【0160】
ここで、部分モデル生成部14fは、基準断面及び拡張後の断面には穴があいたままであるので、これらの断面の輪郭をふさぐ面を生成する。この輪郭をふさぐ手法の一例としては、3角形分割の方法が挙げられる。すなわち、基準断面または拡張後の断面の輪郭の形状が凸多角形の場合には、多角形の任意の2点を結ぶ線分が常にその多角形に含まれるので、1つの輪郭点と、それに隣接する輪郭点以外の全ての輪郭点との間で線分を生成する。
【0161】
これを説明すると、部分モデル生成部14fは、輪郭辺テーブルを探索することにより、輪郭点を隣り合う順番に整列させる。このとき、任意の輪郭点をp(x)とし、輪郭点がN個あるとすると、p(0)、p(1)及びp(2)と、p(0)、p(2)及びp(3)と、・・・、p(0)、p(N−2)及びp(N−1)というように3点を組み合わせることにより3角形を生成する。これによって基準断面及び拡張後の断面をふさぐ面を生成できる。
【0162】
ただし、元の輪郭が非凸多角形の場合は、この3角形分割手法では重複ができるので、辺の重なりのチェックをする必要がある。この場合、まず、p(0)及びp(2)の線分と、輪郭をなす成分p(0)及びp(1)、p(1)及びp(2)、p(3)及びp(4)、・・・、p(N−2)及びp(N−1)という線分が交わるかどうかの判定を行う。かかる線分の交差は、pとpを判定する際には、下記の式(18)及び式(19)の2つの不等号式を満たす場合に交差しているとみなすことができる。
【0163】
【数18】

【0164】
【数19】

【0165】
このとき、上記の式(18)及び式(19)の算出結果が2つの不等号式を満たさない場合、すなわち交差する線分がない場合には、そのまま凸多角形の場合と同様に輪郭をふさぐ。一方、上記の式(18)及び式(19)の算出結果が2つの不等号式を満たす場合、交差する成分がある場合は、起点となるp(0)を変更するか、もしくは接続先のp(2)を変更する。かかる変更を行うことにより、交差しない線分の組合せを探索する。この線分で多角形が2つの多角形に分割されるので、この多角形も同様に個別に三角形分割の処理を行う。これによって分割された3角形に新たに面IDを採番する。
【0166】
この輪郭をふさぐ面を生成した後に、部分モデル生成部14fは、部分モデル候補リストに消去されずに残っている面ID、3角形分割で生成された面ID、基準断面の輪郭辺を含むポリゴンの面ID、拡張後の断面の輪郭辺を含む面IDを特定する。
【0167】
そして、部分モデル生成部14fは、このようにして特定した面IDに対応する3つの点IDを面テーブルから取り出し、面IDに3つの点IDを対応付けたレコードを有する部分面テーブルを生成する。続いて、部分モデル生成部14fは、生成した部分面テーブルを記憶部13の各種テーブルデータ13cへ登録する。なお、部分面テーブルが既に生成されている場合には、面ID及び3つの点IDを含んでなるレコードが新たに追加される。
【0168】
この部分面テーブルは、部分モデルに含まれるポリゴンの面IDごとにその面に含まれる頂点の点IDを記憶したテーブルである。図17は、部分面テーブルに記憶される情報の構成例を示す図である。図17に示す例では、面ID「0」の面が点ID「0」、点ID「1」及び点ID「2」の3つの頂点を含んで構成される面であることを示す。なお、この図17で点IDの末尾に付される括弧付きの番号は、テーブルへ登録された順序を指し、(1)であれば1つ目、(2)であれば2つ目、(3)であれば3つ目であること示す。かかる登録順序は、部分面テーブル使用時の処理結果に及ぼすものではなく、必ずしも区別して登録される必要はない。
【0169】
また、部分モデル生成部14fは、面テーブルから取り出した点IDに対応する座標を図5に示した点テーブルから取り出し、点IDにその座標を対応付けたレコードを有する部分点テーブルを生成する。そして、部分モデル生成部14fは、生成した部分点テーブルを記憶部13の各種テーブルデータ13cへ登録する。なお、部分点テーブルが既に生成されている場合には、点ID及び座標を含んでなるレコードが新たに追加される。
【0170】
この部分点テーブルは、部分モデルに含まれるポリゴンの点IDごとにその頂点のX座標、Y座標及びZ座標を記憶したテーブルである。図18は、部分点テーブルに記憶される情報の構成例を示す図である。図18に示す例では、点ID「0」の頂点の座標が(10,15,−20)であることを示す。さらに、点ID「1」の頂点の座標が(15,50,−30)であることを示す。また、点ID「2」の頂点の座標が(5,−10,20)であることを示す。
【0171】
このようにして生成された部分面テーブル及び部分点テーブルは、部分モデルの部分形状を示す。
【0172】
ここで、拡張処理部14eによって拡張後の断面からさらなる再拡張が行われた時に生成された輪郭点テーブルに輪郭点が登録されていなかった場合には、断面の拡張が3Dモデルの拡張方向の末尾に至ったものとみなすことができる。この場合には、部分モデル生成部14fは、基準断面に対する面の探索だけを実行する。なぜなら、3Dモデルの拡張方向の末尾を終端として断面を拡張すればよく、拡張後の断面に対する面の探索を実行する必要がないからである
【0173】
また、部分モデル生成部14fは、拡張方向の再決定後には、基準断面に対する面の探索及び拡張後の断面に対する面の探索を初期の拡張方向の反対方向に行う。このため、部分モデル生成部14fは、基準断面から初期の拡張方向に向かって3Dモデルの末尾まで拡張した時に生成した部分面テーブル及び部分点テーブルの内容を以降の拡張時に算出した部分面テーブル及び部分点テーブルに付加する。これによって3Dモデルの部分形状を未拡張の部分形状がなくなるまで段階的に拡張を行って部分モデルを生成することができる。
【0174】
図2の説明に戻り、類似度検索部14gは、記憶部13に部分モデルデータ13aとして記憶された部分モデルのうち、部分モデル生成部14fによって生成された部分モデルとの間で特徴量が所定値以上の類似度を有する部分モデルを検索する処理部である。
【0175】
まず、類似度検索部14gは、部分モデル生成部14fによって生成された部分モデルの特徴量を抽出する。すなわち、類似度検索部14gは、図17に示した部分面テーブル及び図18に示した部分点テーブルに記憶された3Dモデルの部分形状を1つの部分モデルとみなして、3次元形状に関する特徴量を抽出する。かかる特徴量抽出手法の一例としては、特開2009−80796号広報で開示される技術の他、各種の公知の技術を適用することができる。
【0176】
その上で、類似度検索部14gは、記憶部13に部分モデルデータ13aとして記憶された部分モデルのうち、3Dモデルの部分形状から抽出した部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する。例えば、同じ次元数のベクトル間の距離は、ユークリッド距離で算出することができる。ここで、非検索対象とする部分モデルの特徴量ベクトルをf(n)とし、検索キーとする部分モデルの特徴量ベクトルをg(n)とし、次元数をmとしたとき、類似検索部14gは、下記の式(20)を用いて、ユークリッド距離dを算出できる。
【0177】
【数20】

【0178】
そして、類似度検索部14gは、検索キーとする部分モデルとの間での距離の大きさが示す類似度が所定値以上である非検索対象の部分モデルを検索する。ここで、2つの部分モデルの距離が小さいほど類似度が高いとみなすことができる。この類似度検索部14gは、今回に断面が拡張された段階を一意に特定するための拡張IDを採番し、採番した拡張IDに対して類似度が高い順に部分モデルID及びその類似度を対応付けたレコードを有する検索結果テーブルを生成する。続いて、類似度検索結果14gは、生成した検索結果テーブルを記憶部13の各種テーブルデータ13cへ登録する。なお、検索結果テーブルが既に生成されている場合には、拡張ID、部分モデルID及び類似度を含んでなるレコードが新たに追加される。
【0179】
この検索結果テーブルは、拡張IDごとに部分モデルID及び類似度を記憶したテーブルである。図19は、検索結果テーブルに記憶される情報の構成例を示す図である。図19に示す例は、拡張IDがいずれも1であり、断面を始めて拡張した段階での検索結果であることを示す。この図19の例では、部分モデルID「14」の部分モデルが検索キーとした部分モデルとの間の類似度が0.4であり、また、部分モデルID「2」の部分モデルが検索キーとした部分モデルとの間の類似度が0.35であることを示す。なお、拡張IDが表す数字は、断面の拡張が行われた回数に対応しているものとする。
【0180】
図2の説明に戻り、結果選択部14hは、類似検索部14gによって検索された各部分モデルの検索結果の中から、表示部12に表示させる部分モデルの検索結果を選択する処理部である。
【0181】
この結果選択部14hは、類似検索部14gによって拡張段階ごとに検索された検索結果の数、類似度が所定の最適値に近い度合いを示す評価値を算出する。これを説明すると、結果選択部14hは、検索結果テーブルの中から部分モデルの類似度を部分モデルIDごとに取得する。さらに、結果選択部14hは、検索結果テーブルの中から拡張IDごとの検索結果の数を取得する。ここで、結果選択部14hは、下記の式(21)に示す評価関数を用いて、部分モデルごとの評価値を算出する。なお、検索結果テーブルは、記憶部13に各種テーブルデータ13cとして類似検索部14gにより登録されたものである。
【0182】
【数21】

【0183】
上記の式(21)では、特徴量ベクトル間の距離がdであり、その距離の最大値がmであり、検索結果の数がcであり、類似度の重みがwであり、検索結果の数の重みがwであるものとする。なお、類似度の重みw及び検索結果の数の重みwは、設計支援アプリの利用者または開発者が任意の値を設定できるものとする。
【0184】
この式(21)の評価関数に既知である距離d、最大値m、検索結果の数c、類似度の重みw検索結果の数の重みwを各部分モデルIDごとに代入することにより、結果選択部14hは、各部分モデルごとの評価値を得ることができる。
【0185】
この評価値の算出後に、結果選択部14hは、評価値が高い部分モデルの部分モデルIDから順に所定の件数を表示部12に表示させたり、また、最も評価値が高い部分モデルの部分モデルIDを表示部12に表示させたりする。
【0186】
また、検索キーとした部分モデルとの間で類似する部分モデルの数が所定の上限値を超える場合には、結果選択部14hは、検索結果の数を用いて、検索結果の数ができるだけ少ない場合を利用することもできる。
【0187】
また、断面を拡張する回数が増えるにつれて検索結果の数は増減するが、一般に汎用すぎるモデルの場合には、検索結果の数が多くなり、逆に特殊すぎる形状の場合には、検索結果の数が0件になる傾向にある。
【0188】
そこで、結果選択部14hは、検索結果の数が所定の数よりも多く、かつ一番少ない拡張IDの検索結果を使用することもできる。このような結果選択を行う場合には、式(21)の関数fは、検索結果の数cが閾値以上で最も少ない場合にはf(c)を1とし、それ以外の場合にはf(c)を0と設定することもできる。
【0189】
また、結果選択部14hは、下記の式(22)を用いて、部分モデルの類似度とその拡張IDにおける検索結果の数から評価値を算出し、その評価値を部分モデルに割り当てることもできる。
【0190】
【数22】

【0191】
上記の式(22)では、検索結果の数の重みを設定した関数がfであり、利用者が想定する検索結果の数がaであるものとする。この式(22)を用いて評価値を算出した場合には、利用者が想定する検索結果の数aに近付くほど評価値の値が高くなるように部分モデルの評価値を算出できる。
【0192】
[処理の流れ]
次に、本実施例に係る情報検索装置の処理の流れを説明する。なお、ここでは、情報検索装置10によって行われる(1)全体処理、(2)基準断面輪郭所得処理、(3)拡張方向決定処理、(4)拡張処理、(5)部分モデル生成処理、(6)類似検索処理、(7)検索結果選択処理、(8)輪郭取得処理の順に説明する。
【0193】
(1)全体処理
図20は、実施例2に係る全体処理の手順を示すフローチャートである。この全体処理は、利用者がポインティングデバイス等を用いて3Dモデル上で点を指定した場合に開始される。
【0194】
図20に示すように、起点対応面取得部14aは、利用者により指定された起点から視点方向へ向かう直線と交わる3Dモデルのポリゴン、すなわち起点対応面を取得する(ステップS101)。そして、基準断面輪郭取得部14cは、基準断面の輪郭を取得する「基準断面輪郭取得処理」を行う(ステップS102)。
【0195】
そして、拡張方向決定部14dは、基準断面を拡張する拡張方向を決定する「拡張方向決定処理」を行い(ステップS103)、拡張処理部14eは、基準断面から拡張方向へ断面を拡張する「拡張処理」を行う(ステップS104)。続いて、部分モデル生成部14fは、後述する「部分モデル生成処理」を行う(ステップS105)。
【0196】
その後、類似検索部14gは、部分モデル生成部14fによって生成された部分モデルの特徴量を抽出する(ステップS106)。続いて、類似検索部14gは、3Dモデルの部分形状から抽出した部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する「類似検索処理」を行う(ステップS107)。
【0197】
このとき、3Dモデルの輪郭のうち未だ移動が完了していない輪郭が存在する場合(ステップS108肯定)には、情報検索装置10は、上記のステップS104〜ステップS107までの処理を繰り返し行う。
【0198】
その後、3Dモデルの全ての輪郭を移動し終えた場合(ステップS108否定)に、結果選択部14hは、各部分モデルの検索結果の中から表示部12に表示させる部分モデルの検索結果を選択する「結果選択処理」を行い(ステップS109)、処理を終了する。
【0199】
(2)基準断面輪郭取得処理
図21は、実施例2に係る基準断面輪郭取得処理の手順を示すフローチャートである。この処理は、図20に示したステップS102の処理に対応しており、起点対応面が取得された場合に起動する。
【0200】
図21に示すように、基準断面輪郭取得部14cは、基準断面の候補とする断面候補を取得する(ステップS201)。続いて、基準断面輪郭取得部14cは、断面候補と交わるポリゴンの輪郭点及び輪郭辺を算出する(ステップS202)。そして、基準断面輪郭取得部14cは、輪郭点、輪郭辺及びその算出に使用した面IDなどの情報を用いて、処理済み面リスト、輪郭点テーブル及び輪郭辺テーブルを更新する(ステップS203)。
【0201】
その後、基準断面輪郭取得部14cは、断面候補と交わる二辺について各辺が共有される面の面IDを辺テーブルから取り出す(ステップS204)。続いて、基準断面輪郭取得部14cは、辺テーブルから取り出した面IDのうち処理済み面リストに登録がない面IDだけを未処理の面リストへ登録する(ステップS205)。
【0202】
そして、基準断面輪郭取得部14cは、未処理の面リストの面IDが空になるまで(ステップS206肯定)、上記のステップS202〜S205までの処理を繰り返し行う。
【0203】
その後、未処理の面リストの面IDが空になった場合(ステップS206否定)には、基準断面輪郭取得部14cは、各輪郭辺の長さを足し合わせることにより、断面候補の輪郭距離を算出する(ステップS207)。
【0204】
そして、全ての断面候補の輪郭距離を算出するまで(ステップS208否定)、基準断面輪郭取得部14cは、上記のステップS201〜S207までの処理を繰り返し行う。その後、全ての断面候補の輪郭距離を算出した場合(ステップS208肯定)には、基準断面輪郭取得部14cは、全断面候補の輪郭距離のうち最も輪郭距離が小さい断面候補を基準断面と決定し(ステップS209)、処理を終了する。
【0205】
(3)拡張方向決定処理
図22は、実施例2に係る拡張方向決定処理の手順を示すフローチャートである。この処理は、図20に示したステップS103の処理に対応しており、基準断面の輪郭が取得された場合に起動する。
【0206】
図22に示すように、拡張方向決定部14dは、基準断面の輪郭辺を含むポリゴンの面IDを計算済み面リストに登録する(ステップS301)。そして、拡張方向決定部14dは、基準断面よりも第1の立体側に所在するポリゴンの面IDを辺テーブルから取り出す(ステップS302)。
【0207】
その後、拡張方向決定部14dは、辺テーブルから取り出したポリゴンが持つ体積を算出し、算出した体積を前回までに累積された累積値に加算する(ステップS303)。そして、拡張方向決定部14dは、今回に体積の加算を行ったポリゴンの面IDを計算済み面リストへ登録する(ステップS304)。
【0208】
続いて、拡張方向決定部14dは、今回に体積の加算を行ったポリゴンの面IDと隣り合うポリゴンの面IDの中に計算済み面リストに登録がない面IDが存在するか否かを判定する(ステップS305)。
【0209】
その後、隣り合うポリゴンの面IDが全て計算済み面リストに登録されたと判定するまで(ステップS305肯定)、拡張方向決定部14eは、上記のステップS303及びS304の処理を繰り返し行う。そして、隣り合うポリゴンの面IDが全て計算済み面リストに登録された場合(ステップS305否定)には、第1の立体に含まれるポリゴンの体積が全て加算された状態となる。このため、拡張方向決定部14dは、それまでに加算された累積値を第1の立体の体積V1として保存する(ステップS306)。
【0210】
また、拡張方向決定部14eは、基準断面よりも第2の立体側に所在するポリゴンの面IDを辺テーブルから取り出す(ステップS307)。続いて、拡張方向決定部14dは、辺テーブルから取り出したポリゴンが持つ体積を算出し、算出した体積を前回までに累積された累積値に加算する(ステップS308)。そして、拡張方向決定部14dは、今回に体積の加算を行ったポリゴンの面IDを計算済み面リストへ登録する(ステップS309)。
【0211】
続いて、拡張方向決定部14dは、今回に体積の加算を行ったポリゴンの面IDと隣り合うポリゴンの面IDの中に計算済み面リストに登録がない面IDが存在するか否かを判定する(ステップS310)。
【0212】
その後、隣り合うポリゴンの面IDが全て計算済み面リストに登録されたと判定するまで(ステップS310否定)、拡張方向決定部14eは、上記のステップS308及びS309の処理を繰り返し行う。そして、隣り合うポリゴンの面IDが全て計算済み面リストに登録された場合(ステップS310肯定)には、第2の立体に含まれるポリゴンの体積が全て加算された状態となる。このため、拡張方向決定部14dは、それまでに加算された累積値を第2の立体の体積V2として保存する(ステップS311)。
【0213】
最後に、拡張方向決定部14dは、第1の立体の体積と第2の立体の体積と比較し、第1の立体及び第2の立体のうち体積が小さい立体を特定し、基準断面から体積が小さい立体へ向かう方向を拡張方向として決定し(ステップS312)、処理を終了する。
【0214】
(4)拡張処理
図23は、実施例2に係る拡張処理の手順を示すフローチャートである。この処理は、図20に示したステップS104の処理に対応しており、拡張方向が決定された場合に起動する。
【0215】
図23に示すように、拡張処理部14eは、基準断面輪郭取得部14cによって決定された基準断面から拡張方向決定部14dによって決定された拡張方向へ断面を拡張させる(ステップS401)。
【0216】
続いて、拡張処理部14eは、拡張後の断面と交わるポリゴンの輪郭点及び輪郭辺を算出する(ステップS402)。そして、拡張処理部14eは、輪郭点、輪郭辺及びその算出に使用した面IDなどの情報を用いて、処理済み面リスト、輪郭点テーブル及び輪郭辺テーブルを更新する(ステップS403)。
【0217】
その後、拡張処理部14eは、拡張後の断面と交わる二辺について各辺が共有される面の面IDを辺テーブルから取り出す(ステップS404)。続いて、拡張処理部14eは、辺テーブルから取り出した面IDのうち処理済み面リストに登録がない面IDだけを未処理の面リストへ登録する(ステップS405)。
【0218】
そして、拡張処理部14eは、未処理の面リストの面IDが空になるまで(ステップS406肯定)、上記のステップS402〜S405までの処理を繰り返し行う。その後、未処理の面リストの面IDが空になった場合(ステップS406否定)には、拡張処理部14eは、各輪郭辺の長さを足し合わせることにより、拡張後の断面の輪郭距離を算出する(ステップS407)。
【0219】
最後に、拡張処理部14eは、拡張後の断面の輪郭ID、法線ベクトル及び輪郭距離を含んでなる輪郭テーブルを生成し(ステップS408)、処理を終了する。
【0220】
(5)部分モデル生成処理
図24は、実施例2に係る部分モデル生成処理の手順を示すフローチャートである。この処理は、図20に示したステップS105の処理に対応しており、拡張後の断面について輪郭が取得された場合に起動する。
【0221】
図24に示すように、部分モデル生成部14fは、基準断面の輪郭辺を含むポリゴンの面IDを探索済みリストに登録する(ステップS501)。その上で、部分モデル生成部14fは、基準断面よりも拡張方向側に存在し、かつ拡張後の断面よりも拡張方向の反対側に存在するポリゴンの面IDを辺テーブルから取り出す(ステップS502)。
【0222】
その後、部分モデル生成部14fは、辺テーブルから取り出したポリゴンの面IDを部分モデル候補リストに登録する(ステップS503)。一方、部分モデル生成部14fは、そのポリゴンの面IDを探索済みリストに登録する(ステップS504)。
【0223】
続いて、部分モデル生成部14fは、今回に探索したポリゴンの面IDと隣り合うポリゴンの面IDの中に探索済みリストに登録がない面IDが存在するか否かを判定する(ステップS505)。その後、隣り合うポリゴンの面IDが全て探索済みリストに登録されたと判定するまで(ステップS505否定)、上記のステップS503及びS504の処理を繰り返し行う。
【0224】
そして、隣り合うポリゴンの面IDが全て探索済みリストに登録された場合(ステップS505肯定)には、部分モデル生成部14fは、拡張後の断面の輪郭辺を含むポリゴンの面IDを探索済みリストに登録する(ステップS506)。続いて、部分モデル生成部14fは、拡張後の断面よりも拡張方向に存在するポリゴンの面IDを辺テーブルから取り出す(ステップS507)。
【0225】
そして、部分モデル生成部14fは、辺テーブルから取り出したポリゴンの面IDを部分モデル候補リストから消去する(ステップS508)。続いて、部分モデル生成部14fは、辺テーブルから取り出したポリゴンの面IDを探索済みリストに登録する(ステップS509)。
【0226】
続いて、部分モデル生成部14fは、今回探索したポリゴンの面IDと隣り合うポリゴンの面IDの中に探索済みリストに登録がない面IDが存在するか否かを判定する(ステップS510)。その後、隣り合うポリゴンの面IDが全て探索済みリストに登録されたと判定するまで(ステップS510否定)、上記のステップS508及びS509の処理を繰り返し行う。
【0227】
そして、隣り合うポリゴンの面IDが全て探索済みリストに登録された場合(ステップS510肯定)には、部分モデル生成部14fは、基準断面及び拡張後の断面の輪郭をふさぐ面を生成する(ステップS511)。その後、部分モデル生成部14fは、部分面テーブル及び部分点テーブルを生成し(ステップS512)、処理を終了する。
【0228】
(6)類似検索処理
図25は、実施例2に係る類似検索処理の手順を示すフローチャートである。この処理は、図20に示したステップS107の処理に対応しており、部分モデルの特徴量が抽出された場合に起動する。
【0229】
図25に示すように、類似検索部14gは、記憶部13に部分モデルデータ13aとして記憶された被検索対象の部分モデルの特徴量を読み出す(ステップS601)。そして、類似検索部14gは、被検索対象の部分モデルの特徴量と、検索キーとする部分モデルの特徴量との間で類似度を算出する(ステップS602)。
【0230】
このとき、被検索対象の部分モデルと検索キーとする部分モデルとの類似度が所定値以上である場合(ステップS603肯定)には、類似検索部14gは、拡張ID、部分モデルID及び類似度を検索結果テーブルに保存する(ステップS604)。なお、類似度が所定値未満である場合(ステップS603否定)には、検索結果を保存せずにそのままステップS605に移行する。
【0231】
そして、被検索対象の部分モデルの特徴量を全て読み出すまで(ステップS605否定)、類似検索部14gは、上記のステップS601〜S604の処理を繰り返し行う。なお、被検索対象の部分モデルの特徴量を全て読み出した場合には(ステップS605肯定)、そのまま処理を終了する。
【0232】
(7)検索結果選択処理
図26は、実施例2に係る検索結果選択処理の手順を示すフローチャートである。この処理は、図20に示したステップS109の処理に対応しており、3Dモデルの全ての輪郭を移動し終えた場合に起動する。
【0233】
図26に示すように、結果選択部14hは、検索結果テーブルの中から部分モデルの類似度を部分モデルIDごとに取得する(ステップS701)。さらに、結果選択部14hは、検索結果テーブルの中から拡張IDごとの検索結果の数を取得する(ステップS702)。
【0234】
そして、結果選択部14hは、下記の式(21)に示す評価関数を用いて、部分モデルごとの評価値を算出し(ステップS703)、最も評価値が高い部分モデルの部分モデルIDを表示部12に表示させ(ステップS704)、処理を終了する。
【0235】
(8)輪郭取得処理
図27は、実施例2に係る輪郭取得処理の手順を示すフローチャートである。この処理は、上記の拡張処理の前処理として実行される処理であり、起点対応面が取得された段階で起動できる。
【0236】
図27に示すように、まず、輪郭取得部14bは、起点対応面取得部14aによって取得された面IDのポリゴンが有する三辺の辺IDそれぞれを辺テーブルから抽出する(ステップS801)。続いて、輪郭取得部14bは、抽出した3つの辺IDを未処理の辺リストへ追加するとともに、面IDを処理済みの面リストへ追加する(ステップS802)。
【0237】
その後、輪郭取得部14bは、未処理の辺リストに含まれる1つの辺IDを対象に、辺テーブルから隣接する2つのポリゴンの面IDを抽出する(ステップS803)。このとき、輪郭取得部14bは、辺テーブルから面IDを抽出する際にキーとした辺IDを未処理の辺リストから削除する。
【0238】
そして、輪郭取得部14bは、2つの面IDそれぞれに対応する3つの頂点の座標位置を点テーブルから抽出し、各面IDのポリゴンごとにその法線ベクトルを算出する。続いて、輪郭取得部14bは、2つのポリゴンの法線ベクトルから隣接する2つのポリゴンの内積を算出し(ステップS804)、算出した内積が閾値以下であるか否かを判定する(ステップS805)。
【0239】
ここで、隣接する2つのポリゴンの内積が閾値未満である場合(ステップS805肯定)には、輪郭取得部14bは、輪郭拡張候補ID、辺ID及び面IDを対応付けたレコードを有する輪郭拡張候補テーブルを生成する(ステップS806)。隣接する2つのポリゴンの内積が閾値以上である場合(ステップS805否定)には、ステップS806を行わずにステップS807に移行する。
【0240】
その後、輪郭取得部14bは、隣接する2つのポリゴンの面IDの中に処理済みの面リストに未登録である面IDが存在するか否かを判定する(ステップS807)。このとき、処理済みの面リストに未登録である面IDがある場合(ステップS807肯定)には、輪郭取得部14bは、その面IDのポリゴンを形成する三辺のうち二辺の辺IDを未処理の辺リストへ追加する(ステップS808)。そして、輪郭取得部14bは、未処理の辺リストへ辺IDを追加するのに使用した面IDを処理済みの面リストへ登録する。なお、処理済みの面リストに未登録である面IDがない場合(ステップS807否定)には、ステップS808を行わずにステップS809に移行する。
【0241】
その後、未処理の辺リストに登録された辺IDが空になるまで(ステップS809否定)、輪郭取得部14bは、上記のステップS803〜S808までの処理を繰り返し行う。未処理の辺リストに登録された辺IDが空になった場合(ステップS809肯定)には、そのまま処理を終了する。
【0242】
[実施例2の効果]
上述してきたように、本実施例に係る情報検索装置10は、3Dモデルの類似部分の検索時に利用者による指定点を含む複数の断面を求め、最小の断面を部品の体積が小さい方に移動させ、移動前後の断面が挟む部分形状を検索キーとする。このため、本実施例に係る情報検索装置10では、利用者から3Dモデル上で起点とする位置を受け付けるだけで、検索キーとする部分モデルを抽出して部分モデル記憶部2bに対する検索を実行できる。したがって、本実施例に係る情報検索装置10によれば、3Dモデルの部分形状を簡単な操作で検索することが可能である。
【0243】
また、本実施例に係る情報検索装置10は、基準断面と平行に断面を移動させるか、或いは基準断面との間で面の向きが所定の角度まで変化することを許容して断面を拡張させる。そして、本実施例に係る情報検索装置10は、断面の拡張ことにより、基準断面と拡張後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出する。これにより、本実施例に係る情報検索装置10によれば、3Dモデルの部分形状に追従させながら断面を拡張させることが可能である。
【0244】
さらに、本実施例に係る情報検索装置10は、3Dモデルの輪郭のうち未だ移動が完了していない輪郭に沿って断面をさらに移動させることにより他の部分モデルを抽出する。その上で、本実施例に係る情報検索装置10は、部分モデルとともに抽出された他の部分モデルの特徴量をさらに算出し、記憶した部分モデルのうち、各部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する。それゆえ、本実施例に係る情報検索装置10では、3Dモデルの部分形状を未拡張の部分形状がなくなるまで段階的に拡張を行って部分モデルを生成できる。したがって、本実施例に係る情報検索装置10によれば、利用者が目的とする部分形状が検索結果に含まれる可能性を高めることができる。
【0245】
図28及び図29は、実施例2に係る効果を説明するための説明図である。図28及び図29に示す符号30A及び符号30Bは、3Dモデルの一例を示す。図28及び図29に示す符号31A及び符号31Bは、基準断面の一例を示す。図28及び図29に示す符号32A、符号33A、符号34A、符号32B、符号33B及び符号34Bは、いずれも部分モデルの一例を示す図である。なお、図28は、図10で示した例と同じ基準断面を有し、また、図29は、図11で示した同じ基準断面を有する。
【0246】
図28に示す例で言えば、断面の拡張を1度も行っていない初期段階では、基準断面31Aから拡張方向へ断面を拡張することにより部分モデル32Aを抽出する。次の段階では、基準断面31Aから再決定後の拡張方向へ断面を拡張することにより部分モデル33Aを抽出する。さらに、次の段階では、基準断面31Aから再決定後の拡張方向へ断面をさらに拡張することにより部分モデル34Aを抽出する。図29に示す例で言えば、初期段階では、基準断面31Bから拡張方向へ断面を拡張することにより部分モデル32Bを抽出する。次の段階では、基準断面31Bから再決定後の拡張方向へ断面を拡張することにより部分モデル33Bを抽出する。さらに、次の段階では、基準断面31Bから再決定後の拡張方向へ断面をさらに拡張することにより部分モデル34Bを抽出する。これら図28及び図29の例で示したように、3Dモデル上で異なる起点が指定されたとしても、3Dモデルの部分形状を未拡張の部分形状がなくなるまで段階的に拡張を行って部分モデルを生成することができる。
【0247】
また、本実施例に係る情報検索装置10は、各部分モデルごとに検索した検索結果の数が所定の最適値に近い度合いを示す評価値を算出し、各部分モデルの検索結果のうち、算出した評価値が最も高い部分モデルの検索結果を選択する。このため、本実施例に係る情報検索装置10では、利用者に最適な数の検索結果を提示できる。したがって、本実施例に係る情報検索装置10によれば、検索結果に含まれる部分モデルが汎用的過ぎたり、また、特殊な形状であったりなど、極端な検索結果を提示する可能性を低減することが可能である。
【0248】
さらに、本実施例に係る情報検索装置10は、検索結果として得られた部分モデルのうち、最も高い類似度を有する部分モデルを選択する。このため、本実施例に係る情報検索装置10によれば、目的とする部分モデルである可能性が最も高い部分モデルを利用者に提示することが可能である。
【0249】
また、本実施例に係る情報検索装置10は、部分形状の開口部を閉じた上で部分モデルを抽出する。このため、本実施例に係る情報検索装置10では、部分モデルの特徴量を抽出する際に精度が低下することがない。したがって、本実施例に係る情報検索装置10によれば、利用者が意図したままの部分形状を部分モデルとして検索を行うことが可能である。
【0250】
図30及び図31は、実施例2に係る効果を説明するための説明図である。図30及び図31に示す符号50及び符号60は、3Dモデルの一例を示す。図30及び図31に示す符号P3及び符号P4は、利用者によって指定された起点である。図30に示す符号51は、起点を中心に拡張した場合の拡張範囲を示す。図30に示す符号51Aは、拡張範囲51における部分形状を示す。図30に示す符号52は、部分形状51Aの欠落部分をふさいだ部分モデルを示す。図30に示す符号53は、起点を中心にさらに拡張した場合の拡張範囲を示す。図31に示す符号61は、起点P4を含む基準断面から断面を拡張した場合の拡張範囲を示す。図31に示す符号61Aは、拡張範囲61における部分形状を示す。図31に示す符号62は、部分形状61Aの欠落部分をふさいだ部分モデルを示す。図31に示す符号63は、起点P4を含基準断面から断面をさらに拡張した場合の拡張範囲を示す。
【0251】
図30に示す例では、利用者によって指定された起点P3を中心に拡張を行うと、起点P3に近い部分だけが拡張範囲51となる。このため、拡張範囲51から得られる部分形状51Aが歪な形になってしまう。このような部分形状51Aの欠落を補って部分モデル52を生成したとしても、部分モデル52の特徴量の算出時にはその精度が低下してしまう。そして、起点P3を中心にさらに拡張した場合にも、起点P3に近い部分だけが拡張範囲53となることは変わらず、その部分形状はより歪になる。
【0252】
図31に示す例では、利用者によって指定された起点P4を含む基準断面から断面を拡張した場合には、3Dモデル60を輪切りにした状態の拡張範囲61が得られる。このため、拡張範囲61から得られる部分形状61Aの切断面を平面とすることができる。このような部分形状61Aは、基準断面と拡張後の断面がいずれも平面であるので、部分モデル62を生成したとしても、部分モデル62の特徴量の算出時にはその精度が低下しない。さらには、起点P4を含む基準断面からさらに断面を拡張した場合にも、3Dモデル60を輪切りにした状態の拡張範囲63となることは変わらず、その部分形状の切断面を平面に維持できる。
【実施例3】
【0253】
さて、これまで開示の装置に関する実施例について説明したが、開示の装置は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、開示の装置に含まれる他の実施例を説明する。
【0254】
[適用例]
例えば、上記の実施例2では、未拡張の3Dモデルのポリゴンがなくなるまで断面を拡張することとしたが、必ずしも3Dモデルの全てを対象に拡張する必要はない。一例としては、拡張済みの部分モデルの体積または表面積が上限値または3Dモデル全体に占める一定の割合を超えた場合に、断面の拡張を終了することとしてもよい。
【0255】
また、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。一例としては、起点対応面取得部14aは、利用者の指示入力に頼ることなく、起点を自動的に取得するようにしてもかまわない。例えば、起点対応面取得部14a、輪郭取得部14b、基準断面輪郭取得部14c、拡張方向決定部14d、拡張処理部14eの全部または一部の機能を情報検索装置10の外部装置としてネットワーク経由で接続するようにしてもよい。また、部分モデル生成部14f、類似検索プロセス14g、結果選択プロセス14hの全部または一部の機能を情報検索装置10の外部装置としてネットワーク経由で接続するようにしてもよい。そして、情報検索装置10の設計支援アプリが外部装置を呼び出すことにより、情報検索機能を発揮することとしてもよい。
【0256】
[情報検索プログラム]
また、上記の実施例2で説明した各種の処理は、予め用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図32を用いて、上記の実施例2と同様の機能を有する情報検索プログラムを実行するコンピュータの一例について説明する。なお、図32は、実施例3に係る情報検索プログラムを実行するコンピュータの一例について説明するための図である。
【0257】
図32に示すように、実施例3におけるコンピュータ100は、操作部110aと、マイク110bと、スピーカ110cと、ディスプレイ120と、通信部130とを有する。さらに、このコンピュータ100は、CPU150と、ROM160と、HDD(Hard Disk Drive)170と、RAM(Random Access Memory)180と有する。これら110〜180の各部はバス140を介して接続される。
【0258】
ROM160には、上記の実施例2で示した起点対応面取得部14aと、輪郭取得部14bと、基準断面輪郭取得部14cと、拡張方向決定部14dと、拡張処理部14eと同様の機能を発揮する制御プログラムが予め記憶される。さらに、ROM160には、部分モデル生成部14fと、類似検索プロセス14gと、結果選択プロセス14hと同様の機能を発揮する制御プログラムが予め記憶される。つまり、ROM160には、図32に示すように、起点対応面取得プログラム160aと、輪郭取得プログラム160bと、基準断面輪郭取得プログラム160cと、拡張方向決定プログラム160dと、拡張処理プログラム160eとが記憶される。さらに、ROM160には、部分モデル生成プログラム160fと、類似検索プログラム160gと、結果選択部160hとが記憶される。なお、これらのプログラム160a〜160hについては、図2に示した情報検索装置10の各構成要素と同様、適宜統合又は分離しても良い。
【0259】
そして、CPU150が、これらのプログラム160a〜160eをROM160から読み出して実行する。これによって、CPU150は、図32に示すように、各プログラム160a〜160cについては、起点対応面取得プロセス150a、輪郭取得プロセス150b及び基準断面輪郭取得プロセス150cとして機能するようになる。さらに、CPU150は、拡張方向決定プロセス150d、拡張処理プロセス150e、部分モデル生成プロセス150f、類似検索プロセス150g及び結果選択プロセス150hとして機能するようになる。なお、各プロセス150a〜150eは、図2に示した、起点対応面取得部14aと、輪郭取得部14bと、基準断面輪郭取得部14cと、拡張方向決定部14dと、拡張処理部14eとにそれぞれ対応する。さらに、各プロセス150f〜150hは、拡張処理部14eと、部分モデル生成部14fと、類似検索プロセス14gと、結果選択プロセス14hとにそれぞれ対応する。
【0260】
そして、HDD170には、部分モデルデータ170aと、3Dモデルデータ170bと、各種テーブルデータ170cとが設けられる。なお、これらのデータ170a〜170cは、図2に示した部分モデルデータ13a、3Dモデルデータ13b及び各種テーブルデータ13cに対応する。
【0261】
そして、CPU150は、部分モデルデータ170a、3Dモデルデータ170b及び各種テーブルデータ170cを読み出してRAM180に格納する。さらに、CPU150は、RAM180に格納された部分モデルデータ180aと、3Dモデルデータ180bと、各種テーブルデータ180cとを用いて、情報検索プログラムを実行する。
【0262】
なお、上記した情報検索プログラムについては、必ずしも最初からHDD170やROM160に記憶させておく必要はない。例えば、コンピュータ100に挿入されるフレキシブルディスク(FD)、CD−ROM、DVDディスク、光磁気ディスク、ICカードなどの「可搬用の物理媒体」に各プログラムを記憶させる。そして、コンピュータ100がこれらの可搬用の物理媒体から各プログラムを取得して実行するようにしてもよい。また、公衆回線、インターネット、LAN、WANなどを介してコンピュータ100に接続される他のコンピュータまたはサーバ装置などに各プログラムを記憶させておき、コンピュータ100がこれらから各プログラムを取得して実行するようにしてもよい。
【0263】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【0264】
(付記1)部品を表す3Dモデルを記憶する3Dモデル記憶部と、
前記3Dモデルにおける部分形状を表す部分モデルを記憶する部分モデル記憶部と、
表示部に表示された3Dモデル上で、起点とする位置の指定を受け付ける受付部と、
前記3Dモデル記憶部に記憶された3Dモデルのうち前記受付部によって指定が受け付けられた起点の法線方向に所在する3Dモデルを対象に、前記起点の法線方向を指す直線が当該3Dモデルと交わる交点を含む前記3Dモデルを分断する複数の断面を算出する断面算出部と、
前記断面算出部によって算出された断面によって前記3Dモデルが分断される立体それぞれの大きさを示す指標を算出する指標算出部と、
前記複数の断面のうち大きさが最小である断面と、該断面によって分断される立体のうち前記指標算出部による指標の算出結果が最小となる立体との位置関係に基づき、当該大きさが最小である断面を基準断面とし、当該基準断面と直交する2方向のうちいずれの方向に断面を移動させるのかを決定する移動方向決定部と、
前記移動方向決定部によって決定された方向へ断面を移動させることにより前記基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出する部分モデル抽出部と、
前記部分モデル抽出部によって抽出された部分モデルの特徴量を算出する特徴量算出部と、
前記部分モデル記憶部に記憶された部分モデルのうち、前記特徴量算出部によって算出された部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する検索部と
を有することを特徴とする情報検索装置。
【0265】
(付記2)前記部分モデル抽出部は、前記基準断面と平行に前記断面を移動させるか、或いは前記基準断面との間で面の向きが所定の角度まで変化することを許容して前記断面を移動させることにより前記基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出することを特徴とする付記1に記載の情報検索装置。
【0266】
(付記3)前記部分モデル抽出部は、前記3Dモデルの輪郭のうち未だ移動が完了していない輪郭に沿って前記断面をさらに移動させることにより他の部分モデルを抽出し、
前記特徴量算出部は、前記部分モデル抽出部によって前記部分モデルとともに抽出された他の部分モデルの特徴量をさらに算出し、
前記検索部は、前記部分モデル記憶部に記憶された部分モデルのうち、前記特徴量算出部によって算出された各部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索することを特徴とする付記2に記載の情報検索装置。
【0267】
(付記4)前記検索部によって各部分モデルごとに検索された検索結果の数が所定の最適値に近い度合いを示す評価値を算出する評価値算出部と、
前記検索部によって検索された各部分モデルの検索結果のうち、前記評価値算出部によって算出された評価値が最も高い部分モデルの検索結果を選択する検索結果選択部とをさらに有することを特徴とする付記3に記載の情報検索装置。
【0268】
(付記5)前記検索部による検索結果として得られた部分モデルのうち、最も高い類似度を有する部分モデルを選択する検索結果選択部をさらに有することを特徴とする付記3に記載の情報検索装置。
【0269】
(付記6)前記部分モデル抽出部は、前記部分形状の開口部を閉じた上で前記部分モデルを抽出することを特徴とする付記1〜5のいずれか一つに記載の情報検索装置。
【0270】
(付記7)表示部に表示された部品を表す3Dモデル上で、起点とする位置の指定を受け付ける受付手順と、
前記3Dモデルを記憶する3Dモデル記憶部に記憶された3Dモデルのうち前記受付手順によって指定が受け付けられた起点の法線方向に所在する3Dモデルを対象に、前記起点の法線方向を指す直線が当該3Dモデルと交わる交点を含む前記3Dモデルを分断する複数の断面を算出する断面算出手順と、
前記断面算出手順によって算出された断面によって前記3Dモデルが分断される立体それぞれの大きさを示す指標を算出する指標算出手順と、
前記複数の断面のうち大きさが最小である断面と、該断面によって分断される立体のうち前記指標算出手順による指標の算出結果が最小となる立体との位置関係に基づき、当該大きさが最小である断面を基準断面とし、当該基準断面と直交する2方向のうちいずれの方向に断面を移動させるのかを決定する移動方向決定手順と、
前記移動方向決定手順によって決定された方向へ断面を移動させることにより前記基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出する部分モデル抽出手順と、
前記部分モデル抽出手順によって抽出された部分モデルの特徴量を算出する特徴量算出手順と、
前記3Dモデルにおける部分形状を表す部分モデルを記憶する部分モデル記憶部に記憶された部分モデルのうち、前記特徴量算出手順によって算出された部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する検索手順と
をコンピュータに実行させることを特徴とする情報検索プログラム。
【0271】
(付記8)前記部分モデル抽出手順は、前記基準断面と平行に前記断面を移動させるか、或いは前記基準断面との間で面の向きが所定の角度まで変化することを許容して前記断面を移動させることにより前記基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出することを特徴とする付記7に記載の情報検索プログラム。
【0272】
(付記9)前記部分モデル抽出手順は、前記3Dモデルの輪郭のうち未だ移動が完了していない輪郭に沿って前記断面をさらに移動させることにより他の部分モデルを抽出し、
前記特徴量算出手順は、前記部分モデル抽出手順によって前記部分モデルとともに抽出された他の部分モデルの特徴量をさらに算出し、
前記検索手順は、前記部分モデル記憶部に記憶された部分モデルのうち、前記特徴量算出手順によって算出された各部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索することを特徴とする付記8に記載の情報検索プログラム。
【0273】
(付記10)前記検索手順によって各部分モデルごとに検索された検索結果の数が所定の最適値に近い度合いを示す評価値を算出する評価値算出手順と、
前記検索手順によって検索された各部分モデルの検索結果のうち、前記評価値算出手順によって算出された評価値が最も高い部分モデルの検索結果を選択する検索結果選択手順とをさらにコンピュータに実行させることを特徴とする付記9に記載の情報検索プログラム。
【0274】
(付記11)前記検索手順による検索結果として得られた部分モデルのうち、最も高い類似度を有する部分モデルを選択する検索結果選択手順をさらにコンピュータに実行させることを特徴とする付記9に記載の情報検索プログラム。
【0275】
(付記12)前記部分モデル抽出手順は、前記部分形状の開口部を閉じた上で前記部分モデルを抽出することを特徴とする付記7〜11のいずれか一つに記載の情報検索プログラム。
【0276】
(付記13)表示部に表示された部品を表す3Dモデル上で、起点とする位置の指定を受け付ける受付ステップと、
前記3Dモデルを記憶する3Dモデル記憶部に記憶された3Dモデルのうち前記受付ステップによって指定が受け付けられた起点の法線方向に所在する3Dモデルを対象に、前記起点の法線方向を指す直線が当該3Dモデルと交わる交点を含む前記3Dモデルを分断する複数の断面を算出する断面算出ステップと、
前記断面算出ステップによって算出された断面によって前記3Dモデルが分断される立体それぞれの大きさを示す指標を算出する指標算出ステップと、
前記複数の断面のうち大きさが最小である断面と、該断面によって分断される立体のうち前記指標算出ステップによる指標の算出結果が最小となる立体との位置関係に基づき、当該大きさが最小である断面を基準断面とし、当該基準断面と直交する2方向のうちいずれの方向に断面を移動させるのかを決定する移動方向決定ステップと、
前記移動方向決定ステップによって決定された方向へ断面を移動させることにより前記基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出する部分モデル抽出ステップと、
前記部分モデル抽出ステップによって抽出された部分モデルの特徴量を算出する特徴量算出ステップと、
前記3Dモデルにおける部分形状を表す部分モデルを記憶する部分モデル記憶部に記憶された部分モデルのうち、前記特徴量算出ステップによって算出された部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する検索ステップと
をコンピュータが実行することを特徴とする情報検索方法。
【0277】
(付記14)前記部分モデル抽出ステップは、前記基準断面と平行に前記断面を移動させるか、或いは前記基準断面との間で面の向きが所定の角度まで変化することを許容して前記断面を移動させることにより前記基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出することを特徴とする付記13に記載の情報検索方法。
【0278】
(付記15)前記部分モデル抽出ステップは、前記3Dモデルの輪郭のうち未だ移動が完了していない輪郭に沿って前記断面をさらに移動させることにより他の部分モデルを抽出し、
前記特徴量算出ステップは、前記部分モデル抽出ステップによって前記部分モデルとともに抽出された他の部分モデルの特徴量をさらに算出し、
前記検索ステップは、前記部分モデル記憶部に記憶された部分モデルのうち、前記特徴量算出ステップによって算出された各部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索することを特徴とする付記14に記載の情報検索方法。
【0279】
(付記16)前記検索ステップによって各部分モデルごとに検索された検索結果の数が所定の最適値に近い度合いを示す評価値を算出する評価値算出ステップと、
前記検索ステップによって検索された各部分モデルの検索結果のうち、前記評価値算出ステップによって算出された評価値が最も高い部分モデルの検索結果を選択する検索結果選択ステップとをさらにコンピュータが実行することを特徴とする付記15に記載の情報検索方法。
【0280】
(付記17)前記検索ステップによる検索結果として得られた部分モデルのうち、最も高い類似度を有する部分モデルを選択する検索結果選択ステップをさらにコンピュータが実行することを特徴とする付記15に記載の情報検索方法。
【0281】
(付記18)前記部分モデル抽出ステップは、前記部分形状の開口部を閉じた上で前記部分モデルを抽出することを特徴とする付記13〜17のいずれか一つに記載の情報検索方法。
【符号の説明】
【0282】
1 情報検索装置
2a 3Dモデル記憶部
2b 部分モデル記憶部
3 受付部
4 断面算出部
5 指標算出部
6 移動方向抽出部
7 部分モデル抽出部
8 特徴量算出部
9 検索部
10 情報検索装置
11 入力部
12 表示部
13 記憶部
13a 部分モデルデータ
13b 3Dモデルデータ
13b 各種テーブルデータ
14 制御部
14a 起点対応面取得部
14b 輪郭取得部
14c 基準断面輪郭取得部
14d 拡張方向決定部
14e 拡張処理部
14f 部分モデル生成部
14g 類似検索部
14h 結果選択部

【特許請求の範囲】
【請求項1】
部品を表す3Dモデルを記憶する3Dモデル記憶部と、
前記3Dモデルにおける部分形状を表す部分モデルを記憶する部分モデル記憶部と、
表示部に表示された3Dモデル上で、起点とする位置の指定を受け付ける受付部と、
前記3Dモデル記憶部に記憶された3Dモデルのうち前記受付部によって指定が受け付けられた起点の法線方向に所在する3Dモデルを対象に、前記起点の法線方向を指す直線が当該3Dモデルと交わる交点を含む前記3Dモデルを分断する複数の断面を算出する断面算出部と、
前記断面算出部によって算出された断面によって前記3Dモデルが分断される立体それぞれの大きさを示す指標を算出する指標算出部と、
前記複数の断面のうち大きさが最小である断面と、該断面によって分断される立体のうち前記指標算出部による指標の算出結果が最小となる立体との位置関係に基づき、当該大きさが最小である断面を基準断面とし、当該基準断面と直交する2方向のうちいずれの方向に断面を移動させるのかを決定する移動方向決定部と、
前記移動方向決定部によって決定された方向へ断面を移動させることにより前記基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出する部分モデル抽出部と、
前記部分モデル抽出部によって抽出された部分モデルの特徴量を算出する特徴量算出部と、
前記部分モデル記憶部に記憶された部分モデルのうち、前記特徴量算出部によって算出された部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する検索部と
を有することを特徴とする情報検索装置。
【請求項2】
前記部分モデル抽出部は、前記基準断面と平行に前記断面を移動させるか、或いは前記基準断面との間で面の向きが所定の角度まで変化することを許容して前記断面を移動させることにより前記基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出することを特徴とする請求項1に記載の情報検索装置。
【請求項3】
前記部分モデル抽出部は、前記3Dモデルの輪郭のうち未だ移動が完了していない輪郭に沿って前記断面をさらに移動させることにより他の部分モデルを抽出し、
前記特徴量算出部は、前記部分モデル抽出部によって前記部分モデルとともに抽出された他の部分モデルの特徴量をさらに算出し、
前記検索部は、前記部分モデル記憶部に記憶された部分モデルのうち、前記特徴量算出部によって算出された各部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索することを特徴とする請求項2に記載の情報検索装置。
【請求項4】
前記検索部によって各部分モデルごとに検索された検索結果の数が所定の最適値に近い度合いを示す評価値を算出する評価値算出部と、
前記検索部によって検索された各部分モデルの検索結果のうち、前記評価値算出部によって算出された評価値が最も高い部分モデルの検索結果を選択する検索結果選択部とをさらに有することを特徴とする請求項3に記載の情報検索装置。
【請求項5】
前記検索部による検索結果として得られた部分モデルのうち、最も高い類似度を有する部分モデルを選択する検索結果選択部をさらに有することを特徴とする請求項3に記載の情報検索装置。
【請求項6】
表示部に表示された部品を表す3Dモデル上で、起点とする位置の指定を受け付ける受付手順と、
前記3Dモデルを記憶する3Dモデル記憶部に記憶された3Dモデルのうち前記受付手順によって指定が受け付けられた起点の法線方向に所在する3Dモデルを対象に、前記起点の法線方向を指す直線が当該3Dモデルと交わる交点を含む前記3Dモデルを分断する複数の断面を算出する断面算出手順と、
前記断面算出手順によって算出された断面によって前記3Dモデルが分断される立体それぞれの大きさを示す指標を算出する指標算出手順と、
前記複数の断面のうち大きさが最小である断面と、該断面によって分断される立体のうち前記指標算出手順による指標の算出結果が最小となる立体との位置関係に基づき、当該大きさが最小である断面を基準断面とし、当該基準断面と直交する2方向のうちいずれの方向に断面を移動させるのかを決定する移動方向決定手順と、
前記移動方向決定手順によって決定された方向へ断面を移動させることにより前記基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出する部分モデル抽出手順と、
前記部分モデル抽出手順によって抽出された部分モデルの特徴量を算出する特徴量算出手順と、
前記3Dモデルにおける部分形状を表す部分モデルを記憶する部分モデル記憶部に記憶された部分モデルのうち、前記特徴量算出手順によって算出された部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する検索手順と
をコンピュータに実行させることを特徴とする情報検索プログラム。
【請求項7】
表示部に表示された部品を表す3Dモデル上で、起点とする位置の指定を受け付ける受付ステップと、
前記3Dモデルを記憶する3Dモデル記憶部に記憶された3Dモデルのうち前記受付ステップによって指定が受け付けられた起点の法線方向に所在する3Dモデルを対象に、前記起点の法線方向を指す直線が当該3Dモデルと交わる交点を含む前記3Dモデルを分断する複数の断面を算出する断面算出ステップと、
前記断面算出ステップによって算出された断面によって前記3Dモデルが分断される立体それぞれの大きさを示す指標を算出する指標算出ステップと、
前記複数の断面のうち大きさが最小である断面と、該断面によって分断される立体のうち前記指標算出ステップによる指標の算出結果が最小となる立体との位置関係に基づき、当該大きさが最小である断面を基準断面とし、当該基準断面と直交する2方向のうちいずれの方向に断面を移動させるのかを決定する移動方向決定ステップと、
前記移動方向決定ステップによって決定された方向へ断面を移動させることにより前記基準断面と移動後の断面との間に形成される3Dモデルの部分形状を部分モデルとして抽出する部分モデル抽出ステップと、
前記部分モデル抽出ステップによって抽出された部分モデルの特徴量を算出する特徴量算出ステップと、
前記3Dモデルにおける部分形状を表す部分モデルを記憶する部分モデル記憶部に記憶された部分モデルのうち、前記特徴量算出ステップによって算出された部分モデルの特徴量との間で所定値以上の類似度を有する部分モデルを検索する検索ステップと
をコンピュータが実行することを特徴とする情報検索方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate