JP6753180B2

JP6753180B2 - 最短経路特定プログラム、最短経路特定方法および情報処理装置

Info

Publication number: JP6753180B2
Application number: JP2016136429A
Authority: JP
Inventors: 国平孫; 雄田中
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2016-07-08
Filing date: 2016-07-08
Publication date: 2020-09-09
Anticipated expiration: 2036-07-08
Also published as: US10297069B2; CN107590300A; US20180012396A1; JP2018005861A; KR102035763B1; CN107590300B; KR20180006304A; EP3267342A1

Description

本発明の実施形態は、最短経路特定プログラム、最短経路特定方法および情報処理装置に関する。

コンピュータ技術を活用して製品の設計、製造や工程設計の事前検討の支援を行う技術の一例として、ＣＡＥ（Computer Aided Engineering）が知られている。ＣＡＥ分野では、自動車などの設計対象とする製品の３次元形状の形状データをもとにシミュレーションすることで、対象製品の設計段階から組み立て工程などを検証可能としている。

特開２００６−２７７６７２号公報

しかしながら、上記の従来技術では、３次元形状の形状データより設計対象とする製品の空き領域を通る２点間の最短経路を求める際に、処理負荷が増大する場合がある。

例えば、自動車などの製造現場では、製品の空き領域に電装ケーブルなどの製品を他社に委託して通してもらうことがある。このように他社に委託する場合は、製品についての３次元形状の形状データより空き領域を特定し、特定された空き領域の中で電装ケーブルを通す最短経路を求める。しかしながら、自動車などの製品においては、製品を示す３次元形状を示す面要素のサイズが細かく、要素数が多くなることから、最短経路を求める時に多大な処理負荷がかかることとなる。

１つの側面では、３次元形状から空き領域を通る２点間の最短経路を容易に求めることができる最短経路特定プログラム、最短経路特定方法および情報処理装置を提供することを目的とする。

第１の案では、最短経路特定プログラムは、３次元形状をボクセル化して３次元形状に対応するボクセルを生成する処理をコンピュータに実行させる。また、最短経路特定プログラムは、生成したボクセルを含む３次元空間の領域について、ボクセルとして設定された領域とボクセルとして設定されていない領域を反転させる反転処理をコンピュータに実行させる。また、最短経路特定プログラムは、反転処理後にボクセルとして設定された領域のうち、特定の２点を含み、所定の大きさの球の中心が通過可能な領域を抽出する処理をコンピュータに実行させる。また、最短経路特定プログラムは、抽出した所定の大きさの球の中心が通過可能な領域内の特定の２点を通る最短経路を、所定の大きさの球の中心が通過可能な領域内で特定し、特定した最短経路を出力する処理をコンピュータに実行させる。

本発明の１実施態様によれば、３次元形状から空き領域を通る２点間の最短経路を容易に求めることができる。

図１は、実施形態にかかる情報処理装置の機能構成例を示すブロック図である。図２は、実施形態にかかる情報処理装置の動作例を示すフローチャートである。図３は、３次元形状のボクセル化を説明する説明図である。図４は、反転を説明する説明図である。図５は、始点、終点を含む球の中心が通る領域の抽出を説明する説明図である。図６は、最短経路の特定を説明する説明図である。図７−１は、表示画面を説明する説明図である。図７−２は、表示画面を説明する説明図である。図７−３は、表示画面を説明する説明図である。図８は、実施形態にかかる情報処理装置のハードウエア構成例を示すブロック図である。

以下、図面を参照して、実施形態にかかる最短経路特定プログラム、最短経路特定方法および情報処理装置を説明する。実施形態において同一の機能を有する構成には同一の符号を付し、重複する説明は省略する。なお、以下の実施形態で説明する最短経路特定プログラム、最短経路特定方法および情報処理装置は、一例を示すに過ぎず、実施形態を限定するものではない。また、以下の各実施形態は、矛盾しない範囲内で適宜組みあわせてもよい。

図１は、実施形態にかかる情報処理装置の機能構成例を示すブロック図である。図１に示す情報処理装置１は、例えばＰＣ（パーソナルコンピュータ）等を適用できる。情報処理装置１は、例えば、計算機上の３次元ＣＡＤ（Computer Aided Design）で作成した製品の３次元形状データを受け付ける。そして、情報処理装置１は、受け付けた３次元形状データをもとに製品における外装の抽出などの処理を行い、処理結果をディスプレイなどに出力する。

ここで、３次元形状データは、製品を構成する各部品の形状を示すデータであり、ＢＲＥＰ（Boundary REPresentation）、ファセットなどを適用できる。ＢＲＥＰは、位相情報（Ｂｏｄｙ、Ｆａｃｅ、Ｌｏｏｐ、ＣｏＥｄｇｅ、Ｅｄｇｅ、Ｖｅｒｔｅｘなど）および幾何情報（ＢａｓｅＳｕｒｆａｃｅ、ＢａｓｅＣｕｒｖｅ、ＢａｓｅＰｏｉｎｔなど）で製品の３次元形状を表現する。ファセットは、微小な三角形（Ｂｏｄｙ、Ｆａｃｅ、Ｔｒｉａｎｇｌｅｓなど）の集まりで製品の３次元形状を表現する。

図１に示すように、情報処理装置１は、ボクセル化部１０、反転部２０、領域抽出部３０、経路特定部４０、出力部５０および設定部６０を有する。

ボクセル化部１０は、製品の３次元形状データが示す製品の３次元形状をボクセル化して３次元形状に対応するボクセルを生成する。

ボクセルは、ＸＹＺ空間の微小立体（格子）の集まりで３次元形状を表現する。このように、ボクセルは、ＸＹＺ空間上の微小立体の有無により単純に３次元形状を表現できることから、ＢＲＥＰやファセットなどの３次元形状データと比較して各種演算にかかる処理負荷を抑えることができる。

反転部２０は、ボクセル化部１０が生成したボクセルを含む３次元空間の領域（例えば立方体または直方体など）について逆ボクセル化を行う。すなわち、反転部２０は、ボクセルとして設定された領域とボクセルとして設定されていない領域を反転させる反転処理を実行する。この逆ボクセル化により、３次元形状に対応する領域以外の空き領域がボクセル化される（ボクセルとして設定される）こととなる。

領域抽出部３０は、逆ボクセル化後にボクセルとして設定された領域のうち、最短経路を求めるための始点および終点を含み、予め設定された大きさの球の中心が通過可能な領域を抽出する。経路特定部４０は、領域抽出部３０が抽出した領域内で、始点および終点の２点を通る最短経路を特定する。

出力部５０は、経路特定部４０の処理結果、すなわち経路特定部４０により特定された、３次元形状の空き領域内で始点および終点の２点を通る最短経路を出力する。一例として、出力部５０は、最短経路の表示を行う表示データを出力する。これにより、ユーザは、３次元形状の空き領域内において始点および終点の２点を通る最短経路を確認できる。

設定部６０は、ユーザからの各種設定を受け付けるユーザ・インタフェースである。例えば、設定部６０は、ＧＵＩ（グラフィカル・ユーザ・インタフェース）をディスプレイに表示してユーザからの操作をＧＵＩで受け付けることで、各種設定を行う。一例として、設定部６０は、ボクセル化部１０、反転部２０、領域抽出部３０および経路特定部４０において最短経路の特定を行う際の条件設定を受付ける。また、設定部６０は、出力部５０において出力する表示データについての設定などの表示設定を受け付ける。

次に、情報処理装置１における処理の詳細について説明する。図２は、実施形態にかかる情報処理装置１の動作例を示すフローチャートである。

図２に示すように、処理が開始されると、設定部６０は、設定画面におけるユーザの操作をもとに、最短経路の特定を行う際の条件設定を受付ける（Ｓ１）。

具体的には、設定部６０は、ボクセル化部１０におけるボクセル化の条件（例えばボクセルのピッチ）の設定値を受付ける。また、設定部６０は、最短経路の特定を行うための始点および終点、最短経路上の中心位置からのマージンであり、例えば最短経路に沿って設置する管材（パイプ）の径などの設定値を受付ける。

Ｓ１に次いで、ボクセル化部１０は、製品の３次元形状データが示す製品の３次元形状を、Ｓ１で設定された条件でボクセル化する（Ｓ２）。

図３は、３次元形状のボクセル化を説明する説明図である。図３に示すように、ボクセル化部１０は、３次元形状データが示す３次元形状３００についてボクセル化を行い、３次元形状３００に対応するボクセル３０１を生成する。このボクセル化については、例えば３次元形状データに含まれるファセットの各三角形が通る領域を”１（ボクセルあり）”と設定するなどの公知のアルゴリズムを用いて行う。

次いで、反転部２０は、ボクセル化部１０が生成したボクセル３０１を含む所定の３次元空間の領域、すなわちボクセル３０１を囲む立方体または直方体などの領域についてボクセルの反転処理（逆ボクセル化）を行う（Ｓ３）。

図４は、反転（逆ボクセル化）を説明する説明図である。反転部２０は、ボクセル化部１０が生成したボクセル３０１を含む立体３０１ａ内において、ボクセル３０１として設定された領域とボクセル３０１として設定されていない領域を反転させる。この反転により、３次元形状に対応するボクセル３０１以外の空き領域がボクセル３０２として抽出される。

次いで、領域抽出部３０は、Ｓ３の反転後にボクセル３０２として設定された領域内の、Ｓ１により設定された始点、終点を含む領域で、Ｓ１などで予め設定されたサイズの球が通る領域を特定（抽出）する（Ｓ４）。次いで、領域抽出部３０は、特定した球が通る領域の中で球の中心が通る領域を抽出する（Ｓ５）。

図５は、始点、終点を含む球の中心が通る領域の抽出を説明する説明図である。具体的には、図５では、図４のボクセル３０２におけるＡ−Ａ方向の断面を示している。

図５に示すように、３次元形状に対応するボクセル３０１以外の空き領域に対応するボクセル３０２において、始点３１０、終点３１１が予め設定されているものとする。領域抽出部３０は、始点３１０、終点３１１を含む領域で、Ｓ１などで予め設定されたサイズの球３２０が通る領域３３０を特定（抽出）する。具体的には、領域抽出部３０は、ボクセル３０２内で球３２０を連続して移動させ、球３２０がボクセル３０２よりはみ出ることなく連続して通過可能な領域３３０を特定する。

次いで、領域抽出部３０は、領域３３０を球３２０が移動した軌跡より、球３２０の中心が通る領域３４０を抽出する。抽出された領域３４０は、球３２０の中心が通る領域なので、球３２０の半径分ボクセル３０２の縁よりも離れている（マージンを有する）。また、ボクセル３０２の中で球３２０が通らない隙間、すなわち球３２０の径に対応する管材（パイプ）が通らない領域は、抽出されない。したがって、領域３４０の中で最短経路の特定を行うことで、最短経路に沿って管材を配置する場合において、管材が３次元形状３００などに干渉することがない。

Ｓ５に次いで、経路特定部４０は、領域抽出部３０により抽出された領域３４０内において始点３１０、終点３１１の２点を通る最短経路を特定する（Ｓ６）。

図６は、最短経路の特定を説明する説明図である。図６に示すように、経路特定部４０は、領域３４０内において始点３１０から終点３１１に至る最短経路３１２を、八分木とダイクストラ法を組み合わせるなどした公知の手法により特定する。具体的には、経路特定部４０は、領域３４０の八分木構造を求め、八分木構造の末端を頂点としてグラフ構造を作成する。次いで、経路特定部４０は、作成したグラフ構造について、グラフ構造の２ノード間の最短距離を求めるアルゴリズムであるダイクストラ法を適用することで、最短経路３１２を特定する。

この最短経路３１２は、領域３４０内で特定することで、ボクセル３０２の縁よりも球３２０の半径分のマージンを有する。したがって、図６における３次元形状３００およびボクセル３０１と、最短経路３１２および最短経路３１２に沿った管材３１３との重ね合わせからも明らかなように、管材３１３は、ボクセル３０１（３次元形状３００）に干渉しない。

Ｓ６に次いで、出力部５０は、経路特定部４０の処理結果、すなわち３次元形状３００に干渉せずに始点３１０、終点３１１の２点を通る最短経路３１２を出力する（Ｓ７）。具体的には、出力部５０は、最短経路３１２を表示画面などに出力する。

図７−１〜図７−３は、表示画面を説明する説明図である。図７−１〜図７−３に示すように、表示画面４００は、操作領域４０１と、ツリー表示領域４０２と、３次元形状表示領域４０３とを有する。

操作領域４０１は、各種の操作ボタンを有する領域であり、ユーザからの操作指示を受付ける。ツリー表示領域４０２は、３次元形状表示領域４０３に表示する表示部材をツリー形式に表示する領域である。ツリー表示領域４０２のツリー４０２ａには、３次元形状表示領域４０３に表示する表示部材ごとのブランチ４０２ｂが設定されている。ユーザは、ブランチ４０２ｂにおけるチェックボックスをオン／オフすることで、３次元形状表示領域４０３における表示部材の表示のあり／なしを指示できる。

図７−１に示すように、ユーザは、３次元形状３００が３次元形状表示領域４０３に表示された表示画面４００から操作領域４０１での操作を行うことで、まずボクセル化の設定を行う。具体的には、ユーザは、設定画面２０１を呼び出してボクセル化の条件設定を行い、３次元形状３００のボクセル化を実行する。

これにより、３次元形状３００のボクセル化が行われ、図７−２に示すように、３次元形状表示領域４０３に３次元形状３００に対応するボクセル３０１が表示される。したがって、ユーザは、３次元形状３００に対応するボクセル３０１の状態を確認できる。次いで、ユーザは、設定画面２０２を呼び出して最短経路３１２（最短経路３１２で設置する管材３１３の経路）の特定にかかる条件設定を行い、最短経路を特定する処理を実行させる。

これにより、最短経路３１２で設置する管材３１３の経路の特定が行われ、図７−３に示すように、３次元形状表示領域４０３に特定された経路で管材３１３が表示される。したがって、ユーザは、最短経路３１２で設置する管材３１３の経路を容易に確認できる。

以上のように、情報処理装置１は、３次元形状３００をボクセル化して３次元形状３００に対応するボクセル３０１を生成し、ボクセル３０１を含む立体３０１ａについて逆ボクセル化を実行する。次いで、情報処理装置１は、逆ボクセル化後のボクセル３０２として設定された領域のうち、始点３１０および終点３１１の２点を含み、所定の大きさの球３２０の中心が通過可能な領域３４０を抽出する。ついで、情報処理装置１は、抽出した領域３４０内において、始点３１０および終点３１１の２点を通る最短経路３１２を特定し、特定した最短経路３１２をディスプレイなどに出力する。このように、情報処理装置１は、単純に３次元形状を表現できるボクセル３０１、３０２を用いて３次元形状以外の空き領域より最短経路３１２を特定することから、ＢＲＥＰやファセットなどの３次元形状データと比較して各種演算にかかる処理負荷を抑えることができる。

なお、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。

また、情報処理装置１で行われる各種処理機能は、ＣＰＵ（またはＭＰＵ、ＭＣＵ（Micro Controller Unit）等のマイクロ・コンピュータ）上で、その全部または任意の一部を実行するようにしてもよい。また、各種処理機能は、ＣＰＵ（またはＭＰＵ、ＭＣＵ等のマイクロ・コンピュータ）で解析実行されるプログラム上、またはワイヤードロジックによるハードウエア上で、その全部または任意の一部を実行するようにしてもよいことは言うまでもない。また、情報処理装置１で行われる各種処理機能は、クラウドコンピューティングにより、複数のコンピュータが協働して実行してもよい。

ところで、上記の実施形態で説明した各種の処理は、予め用意されたプログラムをコンピュータで実行することで実現できる。そこで、以下では、上記の実施形態と同様の機能を有するプログラムを実行するコンピュータ（ハードウエア）の一例を説明する。図８は、実施形態にかかる情報処理装置１のハードウエア構成例を示すブロック図である。

図８に示すように、情報処理装置１は、各種演算処理を実行するＣＰＵ１０１と、データ入力を受け付ける入力装置１０２と、モニタ１０３と、スピーカ１０４とを有する。また、情報処理装置１は、記憶媒体からプログラム等を読み取る媒体読取装置１０５と、各種装置と接続するためのインタフェース装置１０６と、有線または無線により外部機器と通信接続するための通信装置１０７とを有する。また、情報処理装置１は、各種情報を一時記憶するＲＡＭ１０８と、ハードディスク装置１０９とを有する。また、情報処理装置１内の各部（１０１〜１０９）は、バス１１０に接続される。

ハードディスク装置１０９には、上記の実施形態で説明したボクセル化部１０、反転部２０、領域抽出部３０、経路特定部４０、出力部５０および設定部６０における各種の処理を実行するためのプログラム１１１が記憶される。また、ハードディスク装置１０９には、プログラム１１１が参照する各種データ１１２（例えば３次元形状データなど）が記憶される。入力装置１０２は、例えば、情報処理装置１の操作者から操作情報の入力を受け付ける。モニタ１０３は、例えば、操作者が操作する各種画面（例えば設定画面２０１、２０２、表示画面４００など）を表示する。インタフェース装置１０６は、例えば印刷装置等が接続される。通信装置１０７は、ＬＡＮ（Local Area Network）等の通信ネットワークと接続され、通信ネットワークを介した外部機器との間で各種情報をやりとりする。

ＣＰＵ１０１は、ハードディスク装置１０９に記憶されたプログラム１１１を読み出して、ＲＡＭ１０８に展開して実行することで、各種の処理を行う。なお、プログラム１１１は、ハードディスク装置１０９に記憶されていなくてもよい。例えば、情報処理装置１が読み取り可能な記憶媒体に記憶されたプログラム１１１を読み出して実行するようにしてもよい。情報処理装置１が読み取り可能な記憶媒体は、例えば、ＣＤ−ＲＯＭやＤＶＤディスク、ＵＳＢ（Universal Serial Bus）メモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、ＬＡＮ等に接続された装置にこのプログラム１１１を記憶させておき、情報処理装置１がこれらからプログラム１１１を読み出して実行するようにしてもよい。

１…情報処理装置
１０…ボクセル化部
２０…反転部
３０…領域抽出部
４０…経路特定部
５０…出力部
６０…設定部
１０１…ＣＰＵ
１０２…入力装置
１０３…モニタ
１０４…スピーカ
１０５…媒体読取装置
１０６…インタフェース装置
１０７…通信装置
１０８…ＲＡＭ
１０９…ハードディスク装置
１１０…バス
１１１…プログラム
１１２…各種データ
２０１、２０２…設定画面
３００…３次元形状
３０１、３０２…ボクセル
３０１ａ…立体
３１０…始点
３１１…終点
３１２…最短経路
３１３…管材
３２０…球
３３０、３４０…領域
４００…表示画面
４０１…操作領域
４０２…ツリー表示領域
４０３…３次元形状表示領域
４０２ａ…ツリー
４０２ｂ…ブランチ

Claims

３次元形状をボクセル化して前記３次元形状に対応するボクセルを生成し、
生成した前記ボクセルを含む３次元空間の領域について、ボクセルとして設定された領域とボクセルとして設定されていない領域を反転させる反転処理を実行し、
前記反転処理後にボクセルとして設定された領域のうち、特定の２点を含み、前記所定の大きさの球の中心が通過可能な領域を抽出し、
抽出した前記所定の大きさの球の中心が通過可能な領域内の前記特定の２点を通る最短経路を、前記所定の大きさの球の中心が通過可能な領域内で特定し、
特定した前記最短経路を出力する、
処理をコンピュータに実行させることを特徴とする最短経路特定プログラム。
前記特定の２点は、入力に応じて設定される、ことを特徴とする請求項１に記載の最短経路特定プログラム。
前記抽出する処理は、径の設定を受け付け、設定された前記径に基づく大きさの前記球の中心が通過可能な領域を抽出する、ことを特徴とする請求項１に記載の最短経路特定プログラム。
３次元形状をボクセル化して前記３次元形状に対応するボクセルを生成し、
生成した前記ボクセルを含む３次元空間の領域について、ボクセルとして設定された領域とボクセルとして設定されていない領域を反転させる反転処理を実行し、
前記反転処理後にボクセルとして設定された領域のうち、特定の２点を含み、前記所定の大きさの球の中心が通過可能な領域を抽出し、
抽出した前記所定の大きさの球の中心が通過可能な領域内の前記特定の２点を通る最短経路を、前記所定の大きさの球の中心が通過可能な領域内で特定し、
特定した前記最短経路を出力する、
処理をコンピュータが実行することを特徴とする最短経路特定方法。
３次元形状をボクセル化して前記３次元形状に対応するボクセルを生成し、
生成した前記ボクセルを含む３次元空間の領域について、ボクセルとして設定された領域とボクセルとして設定されていない領域を反転させる反転処理を実行し、
前記反転処理後にボクセルとして設定された領域のうち、特定の２点を含み、前記所定の大きさの球の中心が通過可能な領域を抽出し、
抽出した前記所定の大きさの球の中心が通過可能な領域内の前記特定の２点を通る最短経路を、前記所定の大きさの球の中心が通過可能な領域内で特定し、
特定した前記最短経路を出力する、
処理を実行する機能を有するプロセッサを備えることを特徴とする情報処理装置。