最短経路探索方法及び装置
【課題】３次元モデル上の最短経路を探索する。
【解決手段】３次元モデルを三角形メッシュによりメッシングした上で、三角形要素の辺に補間点を設ける。但し、グラフ理論における補間点間のアークを生成・利用することない。そして、三角形メッシュの頂点及び補間点を、出発点又は出発線から到達点又は到達線まで三角形メッシュの位相情報に基づき探索する。これによって、膨大な数の補間点間のアークを生成する場合よりも計算時間を短くすることができ、補間点間のアークを生成するよりデータ量を減らすことができる。
【解決手段】３次元モデルを三角形メッシュによりメッシングした上で、三角形要素の辺に補間点を設ける。但し、グラフ理論における補間点間のアークを生成・利用することない。そして、三角形メッシュの頂点及び補間点を、出発点又は出発線から到達点又は到達線まで三角形メッシュの位相情報に基づき探索する。これによって、膨大な数の補間点間のアークを生成する場合よりも計算時間を短くすることができ、補間点間のアークを生成するよりデータ量を減らすことができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、３次元モデル上における経路出発線（点に縮退している場合を含む）と経路到達線（点に縮退している場合を含む）との間の最短経路を探索するための技術に関する。
【背景技術】
【０００２】
例えば、電子機器の表面に露出した導体間を当該表面に沿って放電するような場合があるため、電子機器の設計時には、導体間の最短経路及び最短距離を自動的に算出する必要がある。特に大きな電力を必要とする電子機器でも小型化が避けられない場合が増加しているため、自動的に計算できると設計時間を短縮することができる。
【０００３】
なお、例えば図１（ａ）及び（ｃ）に示すように、２つの導体１００１及び１００２の間に１ｍｍ未満のくぼみがある場合には、当該くぼみを無視した状態における最短経路を特定し、当該最短経路の経路長を沿面距離と呼ぶ。また、図１（ｂ）に示すように、導体１００１及び１００２の間に１ｍｍ以上のくぼみの場合には、くぼみ内部をも沿うようにして最短経路を特定し、当該最短経路の経路長も沿面距離である。一方、図１（ｄ）に示すように、導体１００１及び１００２間に突起がある場合にも、当該突起をも沿うようにして最短経路を特定する。
【０００４】
従来から、ＣＡＤモデルなどの３次元モデルの三角形メッシュにおける経路出発点と経路到達点との間の最短経路算出技術がいくつか存在している。その中でも重要と思われる１つの手法に、重み付きグラフ探索法がある。例えば図２に示すように物体表面をグラフで近似してそのグラフの中の２つの頂点間の最短経路を探索する手法である。図２では、頂点と頂点は重み付きの辺で接続されており、頂点間は辺が定義されている場合にのみ移動可能であって、その際のコストが重みである。具体的な最短経路探索アルゴリズムには、例えばダイクストラ（Dijkstra）法などを用いる。
【０００５】
ダイクストラ法は、グラフＧ（Ｎ，Ａ）の１つのノードｓから他のノードｔに至るアークの重みの和が最小となる経路を探索する手法の一つである。なお、Ｎはノード（又は節と呼ぶ）の集合を表し、Ｅはノードを結ぶアーク（又は稜線と呼ぶ）の集合を表す。以下、ダイクストラ法のアルゴリズムの概略を示す。
前提：グラフＧは連結しており、アークに付された重みｗは正である。ノードａiには開始ノードｓからの距離ｄ(vi)と復帰ノード（直前のノード）ｒ(vi)を随伴させる。
アルゴリズム：
１．初期処理 ノードの集合Ｎを次の２つの集合に分ける。
計算完了ノード集合 Ｃ＝｛ｓ｝
計算未了ノード集合 Ｕ＝Ｖ−｛ｓ｝
距離を次のように設定する。
ｄ(s)＝０
ｄ(v)＝∞ 但し、ｖ∈Ｕ
２．演算 最大の距離ｄを有するノードｘ∈Ｃに隣接する全てのｙ∈Ｕに対して
if ｄ(x)＋ｗxy＜ｄ(y)
then ｄ(y)＝ｄ(x)＋ｗxy
最小の距離ｄを有するノードｚ∈Ｕを一つ探索し、Ｕ＝Ｕ−｛ｚ｝，
Ｃ＝Ｃ∪｛ｚ｝とする。
復帰ノードｒ(z)＝ｘを保存する。
この処理をｚ＝ｔになるまで繰り返す。
最短経路については、保存しておいた復帰ノード情報を辿ることによって特定する。
【０００６】
ダイクストラ法は、最初に、隣接するノード間にアークを全て静的に用意しておく必要がある。すなわち、図２に示したようなグラフが完成してからでなければ探索を行うことはない。しかしながら、ノード間には必ずアーク及び重みが定義されるため、ノードが増加するとデータ量が膨大になるという問題がある。
【０００７】
そこで、このような問題点に着目した技術が存在している。すなわち、この技術では、グラフを探索しながら、探索に必要な部分だけ動的にグラフを作成していく。まず（１）問題領域を分割し、（２）開始ノードを含む領域だけグラフを作成し、（３）この領域から最短経路の探索を始め、領域の境界のノードに探索が進んだら隣接する領域のグラフを作る。また、同時に現探索領域と作成した隣接領域のグラフをマージする。そして（３）の処理を探索が終了ノードに到達するまで繰り返す。このような処理では、領域の分割やグラフのマージなど処理が複雑化する問題がある。
【０００８】
なお、図２のようなグラフは、３Ｄモデルの表面に適合した形で形成されるが、必ずしもノードやアークの配置が最適でない場合もある。従って、単純に最短経路として特定されたノード間に設定されているアークをたどるだけでは、真に最短距離で開始ノードと終了ノードとをつなぐことができない場合もある。このような問題に対処するような技術も存在している。その中には、開始ノードと終了ノードとの最短経路を求めた後に、開始ノードと終了ノードとを含む面を平面展開して、開始ノードから終了ノードへの直線距離を算出すると共に、その間のノードについても変更するという技術がある。例えば、図３（ａ）に示す六面体の表面に設定されたグラフを例えばダイクストラ法で探索して開始ノードから終了ノードへの初期最短経路を算出する。図３（ａ）では、開始ノード、Ｉ１、Ｖ、Ｉ２、終了ノードという順番の初期最短経路が特定される。その後、図３（ｂ）に示すように、初期最短経路に含まれる、六面体の頂点Ｖの周りで最初の平面展開を実施する。具体的には、三角形Ｔ５、Ｔ２、Ｔ３及びＴ４を１つの平面に展開する。そして、三角形Ｔ２に含まれる最も開始ノードに近いノードＩ１から終了ノードを直線で結ぶことによって、頂点Ｖ経由よりも短い経路を特定する。ここでは、開始ノード、Ｉ１、Ｉ３、Ｉ４、終了ノードという順番の経路が特定される。ノードＩ３及びＩ４が新たに特定されている。その後、開始ノードを含む三角形Ｔ１、Ｔ２、Ｔ３及びＴ４を１つの平面に展開する。そして、開始ノードと終了ノードとを直線で結ぶことによって、経路は新たに特定されたノードＩ１’、Ｉ３’、Ｉ４’を含むようになる。しかしながら、この技術では２段階で経路を最適化しており、処理が複雑になっている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００６−１７２３１８号公報
【特許文献２】特開２００８−１３４９４８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
以上述べたように従来技術には様々な問題があるが、特に問題なのは、経路出発線と経路到達線との間の最短経路を特定するような技術は存在していないということである。ダイクストラ法等の手法は、２ノード間の最短経路を特定するにはよいが、このように２曲線間の最短経路を特定するのには適していない。
【００１１】
従って、本技術の目的は、出発線（点に縮退している場合を含む）と到達線（点に縮退している場合を含む）との間の最短経路を探索するための新規な技術を提供することである。
【課題を解決するための手段】
【００１２】
３次元モデル上における最短経路をコンピュータにより探索する最短経路探索方法は、３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する三角形及び辺のデータに当該三角形の頂点及び補間点のデータを関連付けて探索管理データ格納部に格納するステップと、３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付けるステップと、出発点又は出発線から到達点又は到達線に至るまで、補間点及び頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である補間点又は頂点について出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、最短距離探索対象点である補間点又は頂点に関連付けて距離を探索管理データ格納部に格納する探索ステップとを含む。
【図面の簡単な説明】
【００１３】
【図１】図１（ａ）乃至（ｄ）は、沿面距離を説明するための図である。
【図２】図２は、重み付きグラフの一例を示す図である。
【図３】図３（ａ）乃至（ｃ）は、従来技術を説明するための図である。
【図４】図４は、３次元モデル上で経路出発線から経路到達線までの経路を示した例を示す図である。
【図５】図５は、最短経路探索装置の機能ブロック図である。
【図６】図６は、メッシュの位相構造を説明するための図である。
【図７】図７は、三角形メッシュの一例を示す図である。
【図８】図８は、点テーブルの一例を示す図である。
【図９】図９は、三角形テーブルの一例を示す図である。
【図１０】図１０は、位相テーブルの一例を示す図である。
【図１１】図１１は、余弦テーブルの一例を示す図である。
【図１２】図１２は、辺長テーブルの一例を示す図である。
【図１３】図１３は、最短経路探索処理の処理フローを示す図である。
【図１４】図１４は、補間点について説明するための図である。
【図１５】図１５は、補間点データテーブルの一例を示す図である。
【図１６】図１６は、補間点管理テーブルの一例を示す図である。
【図１７】図１７は、復帰点を説明するための図である。
【図１８】図１８は、補間点間のアークデータを生成しない理由を説明するための図である。
【図１９】図１９は、前線候補点集合テーブルの一例を示す図である。
【図２０】図２０は、ヒープ構造を採用する場合における前線候補点集合テーブルの一例を示す図である。
【図２１】図２１は、最短経路探索処理の処理フローを示す図である。
【図２２】図２２は、探索すべき三角形要素を説明するための図である。
【図２３】図２３は、探索すべき三角形要素を説明するための図である。
【図２４】図２４は、探索すべき三角形要素を説明するための図である。
【図２５】図２５は、探索すべき三角形要素を説明するための図である。
【図２６】図２６は、探索すべき三角形要素を説明するための図である。
【図２７】図２７は、探索すべき三角形要素を説明するための図である。
【図２８】図２８は、三角形内距離の算出について説明するための図である。
【図２９】図２９は、最短経路探索処理の具体例を説明するための図である。
【図３０】図３０は、最短経路探索処理の具体例を説明するための図である。
【図３１】図３１は、最短経路探索処理の具体例を説明するための図である。
【図３２】図３２は、最短経路探索処理の具体例を説明するための図である。
【図３３】図３３は、最短経路探索処理の具体例を説明するための図である。
【図３４】図３４は、最短経路探索処理の具体例を説明するための図である。
【図３５】図３５は、最短経路探索処理の具体例を説明するための図である。
【図３６】図３６は、最短経路探索処理の具体例を説明するための図である。
【図３７】図３７は、最短経路探索処理の具体例を説明するための図である。
【図３８】図３８は、最短経路探索処理の具体例を説明するための図である。
【図３９】図３９は、最短経路探索処理の具体例を説明するための図である。
【図４０】図４０は、最短経路探索処理の具体例を説明するための図である。
【図４１】図４１は、最短経路探索の際の問題を説明するための図である。
【図４２】図４２は、平面展開区間について説明するための図である。
【図４３】図４３は、平面展開区間端点についての条件を説明するための図である。
【図４４】図４４は、平面展開区間端点についての条件を説明するための図である。
【図４５】図４５は、平面展開経路距離修正処理の処理フローを示す図である。
【図４６】図４６は、補間点管理テーブルの他の例を示す図である。
【図４７】図４７は、平面展開区間生成処理の処理フローを示す図である。
【図４８】図４８は、平面展開区間生成処理を説明するための図である。
【図４９】図４９は、平面展開区間生成処理の処理フローを示す図である。
【図５０】図５０は、補間点位置補正処理の処理フローを示す図である。
【図５１】図５１は、位置補正処理の処理フローを示す図である。
【図５２】図５２は、位置補正処理を説明するための図である。
【図５３】図５３は、位置補正処理の処理フローを示す図である。
【図５４】図５４は、位置補正処理を説明するための図である。
【図５５】図５５は、位相情報について説明するための図である。
【図５６】図５６は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１４】
本実施の形態では、図４に示すように、ある３次元モデルＭ上の経路出発線ｓから経路到達線ｔまでの最短経路Ｌを特定し、当該最短経路Ｌの長さである最短距離を算出するものとする。この際、３次元モデル上には周知の方法で三角形メッシュを形成して、さらに三角形メッシュにおける個々の三角形の辺には、精度向上のため補間点を設ける。但し、補間点間を結ぶアークを予め形成して保持及び利用することはない。三角形メッシュの頂点や補間点を探索して最短経路を特定する場合に、補間点や三角形メッシュの頂点間の距離が必要となるが、必要になった際に必要なものだけ計算する。このように補間点間を結ぶアークを予め用意しないことによって、処理時間を短縮すると共に、データ量の増加を最小限に抑えることができる。
【００１５】
さらにオプションとして、初期的に生成する補間点の位置をベースに距離を算出すると、必ずしも始点と終点の距離は最短とはならない。従って、可能な範囲で三角形メッシュの三角形を平面展開して直線で結ぶことによって、より精度の高い最短距離を算出する。また、直線で結ぶ場合には補間点の位置も変更する。
【００１６】
以下、このような処理を実現するための具体的な構成について説明する。
【００１７】
本実施の形態に係る最短経路探索装置の機能ブロック図を図５に示す。最短経路探索装置は、例えばユーザによって指示された３次元モデルについて周知の技術によって形成された三角形メッシュのデータを格納する三角形メッシュデータ格納部１１と、例えば三角形メッシュデータ格納部１１に格納されているデータを用いてユーザから経路探索の経路出発線及び経路到達線の入力を行うためのデータ入力部１４と、データ入力部１４から入力された経路出発線及び経路到達線のデータを格納する開始終了データ格納部１５と、三角形メッシュデータ格納部１１に格納されているデータを用いて三角形の辺に補間点を生成する処理などを実施する補間点データ生成部１２と、補間点データ生成部１２によって生成されたデータを格納する補間点データ格納部１３と、補間点データ格納部１３と三角形メッシュデータ格納部１１と開始終了データ格納部１５とに格納されているデータを用いて最短経路を探索するための処理を実施する探索処理部１６と、探索処理部１６の処理に用いるデータを一時的に保持する処理データ格納部１７と、探索処理部１６の処理結果である最短距離のデータ及び最短経路のデータを格納する出力データ格納部１８と、例えば三角形メッシュデータ格納部１１と出力データ格納部１８と補間点データ格納部１３とを用いてユーザに対して最短距離及び最短経路を提示する出力部１９とを有する。
【００１８】
探索処理部１６は、少なくとも一部の経路区間について距離を補正する処理を実施する距離補正部１６１と、少なくとも一部の経路区間について距離を補正する際に補間点位置をも補正する処理を実施する補間点位置補正部１６２とを有する。
【００１９】
次に、三角形メッシュデータ格納部１１に格納されるデータについて説明する。最初に、メッシュについて説明する。複雑な対象物の形状を厳密に表現するのは実際的でないので、一般的には物体を多面体メッシュで表現する。特に三角形メッシュは、生成及び取り扱いが容易なので多用される。後に述べる、平面展開を用いた処理を実施する上でも有利である。
【００２０】
三角形は３つの頂点によって定まる。メッシュは、三角形の集合であり、境界でない辺は２つの三角形によって共有される。頂点は、１又は複数の三角形によって共有される。
【００２１】
図６に示すように、三角形Ｔiに識別子を与え、三角形Ｔi毎に、頂点及び辺に対してｖij，ｊ∈［１，３］，ｅij，ｊ∈［１，３］を与えることによってメッシュの位相構造（要素の接続関係）を表現する。図６の白抜き矢印のように三角形に向きを与えると、向きはメッシュ全体で同調するので、一意に矛盾無く隣接する頂点、辺、三角形要素を定めることができるようになる。また、図６の黒矢印で示すように、三角形は辺を介して隣接する三角形が一意に定まる。また、頂点についても同一の識別子を有する頂点を用いれば、隣接する三角形を特定することができる。なお、辺については頂点が定まれば特定できるので、辺自身を管理しない場合もある。
【００２２】
三角形メッシュについては、様々な周知技術にて生成することができるが、例えば有限要素法（ＦＥＭ：Finite Element Method）用に生成した三角形メッシュが好ましい。このように生成された三角形メッシュはアスペクト比が良好であるので、発生する誤差が少くなる。
【００２３】
本実施の形態では、このような前提の下、三角形メッシュ・データは、点テーブル、三角形テーブル及び位相テーブルを含む。ここでは例えば図７に示すような三角形メッシュが存在する場合を説明する。図７では、頂点が６個で、４つの三角形が特定されている。このような三角形メッシュについての点テーブルの一例を図８に示す。図８の例では、頂点の識別子毎に、Ｘ座標値、Ｙ座標値及びＺ座標値が登録される。
【００２４】
また、三角形テーブルの一例を図９に示す。図９の例では、三角形の識別子毎に、該当する３頂点の識別子が登録される。さらに、位相テーブルの一例を図１０に示す。図１０の例では、三角形の識別子毎に、各辺に隣接する他の三角形の識別子が登録される。なお、辺１、辺２、辺３の順番は図６の白抜き矢印で示したように一定の順番となっている。
【００２５】
以上のようなテーブルに加え、以下のようなテーブルを保持することによって距離の計算を高速化することができるようになる。但し必須ではない。高速化のための第１のテーブルは、図１１に示すような余弦テーブルである。図１１の例では、各三角形の各頂点について、その頂点における角度に応じた余弦値が登録されるようになっている。このようなデータを予め用意しておけば、１つの三角形の２辺の頂点又は補間点との距離計算が高速化される。
【００２６】
また、高速化のための第２のテーブルは、図１２に示すような辺長テーブルである。図１２の例では、各三角形について各辺の辺長が登録されるようになっている。このようなデータを保持すれば、三角形内部における距離計算が高速化される場合がある。
【００２７】
なお、三角形メッシュデータ格納部１１には、三角形メッシュ毎に絶縁度に相当する屈折率が登録されている場合もある。物体上の最短距離（すなわち沿面距離）を算出する場合には、経路上に存在する三角形毎に素材が異なり、絶縁度が異なる場合がある。そのような場合には、絶縁度に応じた距離を算出する必要があり、絶縁度に相当する屈折率を登録しておけば、以下で述べる距離計算において、該当部分については屈折率を乗じて距離を換算する。
【００２８】
なお、本実施の形態では、既に三角形メッシュデータ格納部１１に、上で述べたような三角形メッシュのデータを予め用意することを前提にして説明するが、最短経路探索装置が、３次元モデルのデータ（例えば、ベジエ曲面、B-Spline曲面、NURBS曲面などの自由曲面で記述されている三次元モデルであったり、複数部品の組み合わせで構成される３次元モデルのデータ）から、上で述べたような三角形メッシュのデータを生成するような機能を持つようにしても良い。
【００２９】
次に、図１３乃至図５４を用いて、最短経路探索装置の処理内容について説明する。まず、補間点データ生成部１２は、三角形メッシュデータ格納部１１に格納されている三角形メッシュ・データを用いて補間点データ生成処理を実施する（図１３：ステップＳ１）。この処理は、三角形メッシュに含まれる各三角形の辺に補間点（Steiner点とも呼ぶ）を追加する処理である。三角形メッシュがある程度の正規性を有する場合、すなわち三角形の最小角度が閾値以上である場合には、１辺の補間点数を一定にするように、補間点を均等配置することが実際的である。但し、辺の長さに応じて補間点数を決定して、均等間隔に配置するようにしても良い。
【００３０】
例えば図１４に示すように三角形Ｔ1及びＴ2が存在する場合、それぞれの辺には補間点１乃至３が追加される。補間点１乃至３の位置データについては、図１５に示すように、該当する三角形、辺及び補間点のＩＤに対応してＸ座標値、Ｙ座標値及びＺ座標値を登録するようにしてもよい。但し、補間点は、例えば辺に３つの補間点を設ける場合には当該辺の１／４、１／２、３／４の位置に存在するということさえ確定していれば、三角形内距離は算出できるので座標位置を予め算出しておかなくても問題はない。辺毎に補間点の数が変化する場合等には、図１５のデータを用意する方が良い場合もある。
【００３１】
なお、図６の白抜き矢印で示したように、一定の方向にＩＤを付与するようにする。すなわち、図１４において矢印で示すように反時計回りで辺に対して番号（１乃至３）を付与すると共に、辺の中の補間点についても反時計回りで番号（１乃至３）を付与する。但し、以下の処理で頂点（黒丸）についても、補間点と統一的に処理する方が好ましいので、頂点については「０」という補間点番号が付与されている。
【００３２】
また、図１４からも分かるように、三角形Ｔ1の辺１と、三角形Ｔ2の辺３とは同じ辺を共有しており、補間点も同じである。従って、図１５のような位置データにおいても、三角形、辺及び補間点のＩＤについては異なるが実際には同一の補間点を表している場合には、同じ位置データが登録されることになる。
【００３３】
そして、補間点データとしては、以下で述べる探索処理において当該探索処理の管理に用いられる補間点管理テーブルを生成する。
【００３４】
補間点管理テーブルについては例えば図１６に示すようなテーブルである。図１６の例では、三角形、辺及び補間点のＩＤに対応して、当該補間点に至る直前の補間点（頂点の場合あり）である復帰点を含む三角形である復帰点三角形のＩＤ、復帰点を含む辺である復帰点辺のＩＤ、復帰点である補間点のＩＤ、当該補間点までの経路距離及び補間点属性を登録するようになっている。
【００３５】
復帰点は、例えば図１７に示すように、黒丸の補間点から、同じ三角形の辺上の補間点（頂点を含む）を探索した場合には、白丸の探索先補間点にとって黒丸の補間点が復帰点となる。但し、以下で述べる処理でも分かるように、その探索先補間点にとって経路距離が最短でなければ復帰点及び経路距離は登録されないので、その探索先補間点について復帰点はその時点における最短経路についての１つ手前の補間点である。これによって経路を逆方向に辿ることができるようになる。
【００３６】
補間点属性は、初期状態からスタートして、前線候補、前線通過完了と順に遷移する。探索前は初期状態であり、最初に、以下で述べる経路出発線上の補間点が、前線候補という状態に変化する。前線候補から次の補間点へ探索を実施する。前線候補として探索が完了すると前線通過完了に遷移する。また、補間点属性は、例えば経路距離や復帰点情報の符号（正又は負）を用いて表現する場合もある。
【００３７】
本ステップでは、復帰点三角形ＩＤ、復帰点辺ＩＤ、復帰補間点ＩＤについては「０」を初期的に登録し、経路距離については無限大に相当するような値を設定する。
【００３８】
また、図１４に示すように、三角形Ｔ1と三角形Ｔ2では、辺を共有しているので、当然補間点も共有することになる。図１６のように全ての三角形について３つの辺についてデータを保持すると、同一の補間点について２つ以上のレコードがテーブル内に存在する場合がある。このような場合には、両方のレコードを同期して更新する必要がある。なお、一方を常に代表として取り扱い、残余のレコードについては更新しないようにしても良い。
【００３９】
また、経路距離については、以下で説明する前線候補点集合テーブルに登録することによって、補間点管理テーブルにおいて保持しないようにする場合もある。
【００４０】
なお、本補間点管理テーブルでは、経路を逆方向に辿るための復帰点情報は登録されているが、補間点同士を繋ぐアーク及びその距離自体は規定しない。これによって、アーク及びその距離自体を計算する処理時間を節約できると共に、保持すべきデータ量を大幅に削減できる。特に、図１８に示すように、矢印方向に探索が行われ、現在補間点Ａに到達しているとすると、出発線から補間点Ａを経由して補間点Ｂに到達した場合の距離は、補間点Ａまでの距離ｄと補間点Ａ及びＢの距離ＡＢとの和であり、出発線から補間点Ａを経由して補間点Ｃに到達した場合の距離は、補間点Ａまでの距離ｄと補間点Ａ及びＣの距離ＡＣとの和である。補間点Ａから補間点Ｂを経由して補間点Ｃに至ることも考えられるが、補間点Ａから補間点Ｃに直接ゆく方が必ず距離は短くなるので、補間点Ａ、Ｂ及びＣという経路は採用し得ない。従って、以下で述べる探索処理ではこのような三角形内の探索は行われず、予め補間点ＢとＣの間のアークを規定して距離を計算する処理自体無駄である。本実施の形態では、このような無駄な処理を行わずに高速に最短経路探索を行うことができる。
【００４１】
図１３の処理の説明に戻って、データ入力部１４は、ユーザに対して経路出発線の指定を促し、ユーザから経路出発線の指定を受け付け、経路出発線を特定するためのデータを、開始終了データ格納部１５に格納する（ステップＳ３）。例えば、メッシュデータ格納部１１からメッシュ・データを読み出して、３次元モデルの表示データを生成して表示し、ユーザに経路出発線を指定させるようにしてもよい。経路出発線は、三角形メッシュの境界である。なお、ユーザが点を指定して、当該指定された点に最も近いメッシュの境界を探索して特定し、閉じた辺の列として取得してもよい。
【００４２】
導体の境界は、図４の経路出発線ｓや経路到達線ｔのように、三角形メッシュでは閉じた辺の列で表現される。もし非常に細い導体を理想化して表現する必要があるならば、閉じた辺の列を空の三角形要素の境界として表現することによって、閉じた辺の列間の最短経路（すなわち沿面経路）を計算することができる。また更に閉じた辺の列は１点に縮退させることもできる。この場合は、出発点という１点からの経路探索の問題に縮退する。
【００４３】
データとしては、三角形ＩＤと辺ＩＤのセットで特定される。テーブル形式で保持しても良いし、ハッシュ構造を利用しても良い。
【００４４】
さらに、データ入力部１４は、ユーザに対して経路到達線の指定を促し、ユーザから経路到達線の指定を受け付け、経路到達線を特定するためのデータを、開始終了データ格納部１５に格納する（ステップＳ５）。例えば、メッシュデータ格納部１１からメッシュ・データを読み出して、３次元モデルの表示データを生成して表示し、ユーザに経路到達線を指定させるようにしてもよい。経路到達線は、三角形メッシュの境界である。なお、ユーザが点を指定して、当該指定された点に最も近いメッシュの境界を探索して特定し、閉じた辺の列として取得してもよい。
【００４５】
データとしては、三角形ＩＤと辺ＩＤのセットで特定される。テーブル形式で保持しても良いし、ハッシュ構造を利用しても良い。
【００４６】
なお、経路出発線及び経路到達線としては、一般化して、三角形メッシュの境界でないものを選択するようにしても良い。
【００４７】
次に、探索処理部１６は、前線候補点集合テーブルに経路出発線の補間点を設定する（ステップＳ７）。前線候補点とは、図１７における黒丸の補間点のように、最短経路を探索するための起点（経路出発線の補間点の場合を除き中間的な起点）の候補である補間点である。前線候補点集合テーブルは、例えば処理データ格納部１７に格納する。
【００４８】
本実施の形態において、出発線からの経路距離は、経路距離の拡大を波とみなしたときの波頭であるHuygens（ホイヘンス）前線上の補間点からの２次波で決定される。すなわち、Huygens前線が補間点を通過したとき、２次波は、当該補間点が帰属し且つ波の進行方向に存在する三角形要素の補間点に伝播する。そして、２次波が伝播した補間点の中で、最小の経路距離を有する補間点を次のHuygens前線の通過点とする。前線候補点は、このようなHuygens前線の通過点の候補となる補間点である。
【００４９】
前線候補点集合テーブルは、例えば図１９に示すようなテーブルである。すなわち、前線候補点毎に、三角形ＩＤ、辺ＩＤ及び補間点ＩＤを登録するものである。前線候補点集合テーブルに登録した場合には、補間点管理テーブル（図１６）についても更新しなければならない。すなわち、該当する補間点についての候補点属性を「前線候補」に変更する。また、経路距離についても該当する経路距離に変更する。但し、初回の場合、経路出発線の補間点は、当然経路距離「０」であるから、「０」を経路距離に登録する。
【００５０】
以下において、前線候補点集合テーブルに補間点を追加する場合には、例えばテーブルの最後のレコードに追加する。また、前線候補点集合テーブルから前線候補点を削除する場合には、該当レコードを削除した後、最後のレコードを移動させる。
【００５１】
なお、以下の処理において、前線候補点集合から、最小の経路距離を有する前線候補点を抽出する処理を頻繁に実施することになる。前線候補点の数が小さければ補間点管理テーブルを順次探索によって最小の経路距離の前線候補点を特定する処理で問題はない。しかしながら、前線候補点の数が大きくなると、順次探索は時間がかかるという問題がある。この場合、前線候補点集合テーブルの該当アドレスを管理するヒープ構造を使用することが望ましい。但し、前線候補点集合テーブル及び経路距離は動的に変化するので、ヒープ構造と前線候補点集合テーブルの間で同期をとる必要がある。
【００５２】
ヒープ構造を採用する場合には、前線候補点集合テーブルについては、図２０に示すようなデータ・フォーマットを採用する。図２０の例では、図１９に示したテーブルに加えてヒープ・アドレスが登録されるようになっている。
【００５３】
ヒープ構造は、連続した番号をもつ節点で構成される２進木であり、次の三つの規則を有するデータ構造である。
（１）アドレス１をルートとする。
（２）アドレスｋの左の子はアドレス２ｋに、右の子はアドレス２ｋ＋１に格納する。
（３）親の節点は子の節点より常に小さなデータを有する。
ヒープ構造からルート（すなわち根）を取り出すことによって、最小の経路距離をもつ補間点が高速に取り出すことができる。すなわち、データ数をＮとすると、ルートのデータを削除した場合、最後のアドレスＮに存在するデータをルートに移動する。規則（３）を満足するために、親と子の間のデータ交換を行うが、親子のアドレス探索は２の乗除算で可能であり、データ交換の回数はlog2Ｎに過ぎない．これによって高速な探索が可能になる。詳細は、浅野哲夫著「データ構造」（近代科学社 p.30）などを参照されたい。
【００５４】
図２０に示したように、前線候補点集合に属する補間点毎にヒープ・アドレスを取得できる構造にしておく。この構造を採用することによって経路距離が更新された場合も、ヒープ・アドレスを直接参照することによって、高速にヒープの経路距離を親と子の間で比較して入れ換えを行い、ヒープの順序関係を常に正常に保つことができる。また、前線候補点集合テーブルの該当レコードのアドレスが変わっても、ヒープ・アドレスが管理する前線候補点集合テーブルの該当レコードのアドレスを更新することによって同期を取ることができる。これによって、最小の経路距離を有し且つ前線候補点集合に含まれる補間点が取り出されることが保証される。
【００５５】
さらに、探索処理部１６は、前線候補点集合の中で、経路距離が最短である補間点を前線上存在補間点として探索する（ステップＳ９）。この処理は、Huygens前線上に存在する（すなわち前線の通過点たる）補間点を特定するための処理である。前線候補点集合テーブルに登録されている補間点で、補間点管理テーブル（図１６）を検索して経路距離を取得し、取得された経路距離の中で最短の補間点を特定する。ヒープ構造を用いる場合には上で述べたとおりの処理を実施する。
【００５６】
なお、最初にこのステップを実施する場合には、経路出発線上の補間点が経路距離０で前線候補点集合に登録されるので、そのうちのいずれか１つ補間点が選択される。
【００５７】
また、本ステップＳ９の直後に、オプションとして後に述べる平面展開による距離の補正を実施する場合がある。
【００５８】
そして、探索処理部１６は、前線上存在補間点が、開始終了データ格納部１５に格納されている経路到達線上にあるか、すなわち経路到達線に係る三角形の辺に含まれる補間点（頂点を含む）であるかを判断する（ステップＳ１１）。前線上存在補間点が、経路到達線上に存在していない場合には、端子Ａを介して図２１の処理に移行する。
【００５９】
一方、前線上存在補間点が、経路到達線上に存在していると判断されると、探索処理部１６は、前線上存在補間点についての経路距離を最短距離として特定すると共に、前線上存在補間点についての復帰点情報（復帰三角形、復帰辺及び復帰補間点）を補間点管理テーブルから読み出し、さらに復帰点についてのさらに前の復帰点を読み出しといったように順次遡ることによって最短経路上の補間点を特定し、最短距離（すなわち沿面距離）及び最短経路上の補間点の情報（ＩＤ及び位置データ）を出力データ格納部１８に格納する（ステップＳ１３）。なお、本ステップでは、以下で述べる、平面展開による最短経路の修正処理を実施する場合がある。
【００６０】
そして、出力部１９は、出力データ格納部１８に格納された最短距離及び最短経路上の補間点のデータを、表示装置などの出力装置に出力する（ステップＳ１５）。例えば、３次元モデルの三角形メッシュ・データを三角形メッシュデータ格納部１１から読み出して、三角形メッシュ上で、最短経路上の補間点を結んで最短経路を明示するような図（例えば図４）を生成して、表示装置に表示するようにしても良い。
【００６１】
次に、端子Ａの後の処理について図２１乃至図４０を用いて説明する。まず、探索処理部１６は、前線上存在補間点が帰属する三角形の補間点のうち未処理の補間点を探索する（図２１：ステップＳ１７）。本ステップにおいては、前線上存在補間点が保有する復帰点情報に基づいて、経路距離増大方向にある三角形のみを探索の対象とするのが望ましい。全ての三角形を探索の対象にしても処理は可能であるが、対象の限定によって、不要な探索が実行されなくなり、高速な処理が可能になる。
【００６２】
具体的には、図２２に示すように、三角形の辺上に前線上存在補間点ｈが存在する場合には、復帰点ｒ及び前線上存在補間点ｈが属する三角形と、前線上存在補間点ｈが存在する辺を共有する三角形Ｔsの実線矢印の辺に属する補間点を探索対象とする。一方、図２３乃至図２７に示すように、前線上存在補間点ｈが三角形の頂点である場合には、様々なパターンが存在する。図２３に示すように、例えば５つの三角形によって共有される頂点が前線上存在補間点ｈである場合には、復帰点ｒが属する三角形を除く共有三角形Ｔs1乃至Ｔs4の各辺（実線矢印の示す辺。但し復帰点ｒを含む三角形と共有される辺を除く）に属する補間点を探索対象とする。また、図２４に示すように、復帰点ｒと前線上存在補間点ｈとが三角形メッシュの頂点であり、経路が三角形要素の辺に沿って設定されており、前線上存在補間点ｈが経路上の辺を共有する２つの三角形及びそれ以外の例えば３つの三角形Ｔs1乃至Ｔs3に共有される場合には、経路上の辺を共有する三角形以外の三角形Ｔs1乃至Ｔs3の各辺（実線矢印の示す辺。経路上の辺を共有する三角形に属する辺を除く。）に属する補間点が探索対象となる。
【００６３】
さらに、図２５に示すように、復帰点ｒ及び前線上存在補間点ｈが属する三角形及び三角形Ｔs1乃至Ｔs3が前線上存在補間点ｈを共有しているが、図２３とは異なり前線上存在補間点ｈの周り３６０°に三角形が存在するわけではない場合でも、図２３の考え方と同様に、復帰点ｒが属する三角形を除く共有三角形Ｔs1乃至Ｔs3の各辺（実線矢印の示す辺。但し復帰点ｒを含む三角形と共有される辺を除く）に属する補間点を探索対象とする。また、図２６に示すように、復帰点ｒ及び前線上存在補間点ｈとが三角形メッシュの頂点であり、経路が三角形要素の辺に沿って設定されており、経路上の辺を共有する三角形及び例えば三角形Ｔs1及びＴs2が前線上存在補間点ｈを共有しているが、図２４とは異なり前線上存在補間点ｈの周り３６０°に三角形が存在するわけではない場合でも、図２４の考え方と同様に、三角形Ｔs1及びＴs2の各辺（実線矢印の示す辺。但し経路上の辺を共有する三角形に属する辺を除く。）に属する補間点が探索対象となる。
【００６４】
図２７のケースは、三角形メッシュが形成されていない領域の境界を沿って復帰点ｒから前線上存在補間点ｈへ経路が延びており、頂点である前線上存在補間点ｈを共有する三角形が複数存在している場合を示しており、このような場合には、経路がのっている辺が属する三角形以外の三角形で前線上存在補間点ｈを共有する三角形Ｔs1乃至Ｔs3の各辺（実線矢印の示す辺。但し復帰点ｒを含む三角形と共有される辺を除く）に属する補間点を探索対象とする。
【００６５】
なお、上で述べたような探索対象を特定するために、本実施の形態ではメッシュ構造の位相情報を用いる。具体的には、図１０に示したような位相テーブルを用いれば、辺をはさんで隣接する三角形要素を特定することができる。さらに図９の三角形テーブルを用いれば、三角形の頂点も特定できる。頂点と辺については、例えば反時計回りで番号を付与するなどの規則を採用すれば対応付けが可能である。三角形及び辺が特定できれば補間点管理テーブルを用いて補間点も特定できる。このように、位相情報を用いることによって探索対象を把握できるので、ダイクストラ法などで用いられるグラフ構造において連結先を示すポインタを保有しないで済む。従ってその分データ量を減らすことができる。
【００６６】
図２３乃至図２７のようなポリシーで探索先三角形を特定し、その中で未処理の補間点を探索するが、例えば全ての該当補間点を処理してしまって、未処理の補間点が存在しない場合（ステップＳ１９：Ｎｏルート）、探索処理部１６は、前線上存在補間点を前線候補点集合（すなわち前線候補点集合テーブル）から除外し、補間点管理テーブル（図１６）において前線上存在補間点ｈについての補間点属性を「前線通過完了」に変更する（ステップＳ２９）。このようにして、Huygens前線が通過したことになるので、以後の処理の対象から外すことができる。処理は端子Ｂを介して図１３のステップＳ９に戻る。
【００６７】
一方、探索先三角形を特定してその中で未処理の補間点が存在する場合には（ステップＳ１９：Ｙｅｓルート）、探索処理部１６は、補間点管理テーブル（図１６）において、特定された補間点が前線通過完了という補間点属性の補間点であるか判断する（ステップＳ２１）。特定された補間点が、前線通過完了という補間点属性の補間点である場合には、ステップＳ１７に戻る。
【００６８】
一方、特定された補間点が、前線通過完了という補間点属性の補間点ではない場合には、探索処理部１６は、特定された補間点が、前線候補点集合に属するか、すなわち前線候補点集合テーブルに登録されているか判断する（ステップＳ２３）。登録されていれば、再度登録する必要はないのでステップＳ２７に移行する。一方、登録されていなければ、特定された補間点を前線候補点集合に追加、すなわち前線候補点集合テーブルに登録する（ステップＳ２５）。補間点管理テーブルの補間点属性も前線候補に変更する。次の探索処理の起点候補とするためである。
【００６９】
ステップＳ２５の後又はステップＳ２３で既に前線候補点集合テーブルに登録されていると判断された場合には、探索処理部１６は、特定された補間点までの経路距離を算出する。図２８に示すように、まず経路距離ｄ*を有する前線上存在補間点ｃ*から探索した補間点（前線候補点）ｃまでの三角形内距離Δｄを計算する。三角形内距離Δｄは、前線上存在補間点ｃ*と補間点ｃの座標値から、その間の距離を求める。さらに、前線上存在補間点ｃ*の経路距離ｄ*と三角形内距離Δｄとを加算すれば、補間点（前線候補点）の経路距離が得られる。
【００７０】
なお、上で述べたように余弦テーブルや辺長テーブルが用意されている場合には、次のように余弦定理を用いると三角形内距離Δｄを高速に計算できる。すなわち、以下の式で算出できる。
【数１】
【００７１】
このような式で算出する方が、補間点が属する辺の両端の頂点の座標値を内分し、２つの補間点の座標成分の２乗和の平方根を計算するより計算量が少ない。
【００７２】
なお、補間点の座標値を図１５のように予め計算しておく場合には、その値を用いて距離を算出するようにしても良い。
【００７３】
さらに、三角形要素に屈折率が与えられている場合は、三角形内距離Δｄに対して該当する三角形要素の屈折率から定まる係数を乗じて、三角形内距離Δｄを修正する。
【００７４】
その後、今回算出された経路距離が（ｄ*＋Δｄ）が、特定された補間点（前線候補点）の現在の経路距離より短いか判断し、短い場合には、補間点管理テーブルにおいて、特定された補間点の経路距離を今回算出された経路距離に置き換えると共に、復帰点情報を今回の前線上存在補間点についての三角形ＩＤ、辺ＩＤ及び補間点ＩＤに置き換える（ステップＳ２７）。このようにすれば、特定された補間点には、処理時点における最短経路の最短距離及び経路上１つ前の補間点の情報が登録されるようになる。
【００７５】
なお、前線候補点の経路距離をヒープ構造で管理する場合は、ノード間の交換を行い、ヒープ構造に矛盾が生じないようにする。また、補間点管理テーブルにおいて実体が同一の補間点が異なる識別子で複数存在する場合にも、同期をとっておく必要がある。
【００７６】
処理はステップＳ１７に戻って、上で述べた処理を繰り返す。
【００７７】
上で述べたような処理を実施するようにすれば、図１３のステップＳ９で特定された前線上存在補間点が経路到達線上の補間点に到達した時、当該前線上補間点における経路距離には最短距離が登録されているので、容易に最短距離が特定される。また復帰点情報も補間点管理テーブルにおいて管理されているので、復帰点情報を辿ることによって最短経路も容易に特定できる。
【００７８】
以下、図２９乃至図４０を用いて、処理の具体例を示すことによって、上で述べた処理をわかりやすくする。例えば各辺に２つの補間点が設定され且つ三角形要素Ｔ１乃至Ｔ３を含む、図２９のような三角形メッシュを前提とする。図２９において太線は経路出発線を示している。三角形Ｔ１は、辺（Ｔ１，Ｅ１）、（Ｔ１，Ｅ２）（＝（Ｔ２，Ｅ３））及び（Ｔ１，Ｅ３）を有しており、三角形Ｔ２は、辺（Ｔ２，Ｅ１）（＝（Ｔ３，Ｅ３））、（Ｔ２，Ｅ２）及び（Ｔ２，Ｅ３）（＝Ｔ１，Ｅ２）を有しており、三角形Ｔ３は、辺（Ｔ３，Ｅ１）、（Ｔ３，Ｅ２）及び（Ｔ３，Ｅ３）（＝（Ｔ２，Ｅ１））を有している。補間点は、反時計回りに識別番号が付与されている。
【００７９】
このような三角形メッシュが存在する場合に、補間点管理テーブルは図３０に示すような状態となる。まだ探索が行われていないので、各補間点の復帰点情報は全て「０」となる。また、初期的には経路距離は全ての補間点について無限大であるが、既に経路出発線が指定されているので、経路出発線上の補間点（辺（Ｔ１，Ｅ１）及び（Ｔ３，Ｅ１）上の補間点）については経路距離「０」が登録されている。同様に、ステップＳ７において経路出発線上の補間点は前線候補点として前線候補点集合に登録されるので、経路出発線上の補間点の補間点属性は、初期状態から前線候補に変更される。
【００８０】
次に、辺（Ｔ１，Ｅ１）の左端の頂点が前線上存在補間点ｈに選択された場合について図３１及び図３２を用いて説明する。この場合、図３１で点線矢印で示すように、三角形Ｔ１の辺（Ｔ１，Ｅ３）及び（Ｔ１，Ｅ２）を探索対象の辺として特定し、それらの辺上の５つの補間点を順に探索する。そうすると、補間点管理テーブルは、図３０の状態から図３２の状態に変化する。図３２において、（三角形ＩＤ，辺ＩＤ，補間点ＩＤ）の組み合わせで表すと、（１，２，１）（１，２，２）（１，３，０）（１，３，１）（１，３，２）の補間点について、復帰点情報として（１，１，０）が登録され、それぞれの経路距離が登録され、さらに補間点属性が「前線候補」に変更される。三角形Ｔ２については、同一補間点について同期をとるための更新が行われている。
【００８１】
そして最後に、前線上存在補間点ｈである補間点（１，１，０）は、補間点属性が前線通過完了と変更される。
【００８２】
その後、補間点属性が「前線候補」である補間点の中から経路距離が最短の補間点（１，１，１）が、前線上存在補間点ｈとして選択される。この場合、図３３で点線矢印で示すように、三角形Ｔ１の辺（Ｔ１，Ｅ３）及び（Ｔ１，Ｅ２）を探索対象の辺として特定し、それらの辺上の５つの補間点を順に探索する。そうすると、補間点管理テーブルは、図３２の状態から図３４の状態に変化する。すなわち、（１，２，１）（１，２，２）（１，３，０）（１，３，１）（１，３，２）の補間点について補間点（１，１，１）からの経路距離を算出すると、（１，３，２）の補間点以外の補間点（１，２，１）（１，２，２）（１，３，０）（１，３，１）については経路距離が短くなっていることが分かる。そのため、それらの補間点（図３４の星印の行）については、経路距離が今回の算出値に変更される。さらに、それらの復帰点情報は、前線上存在補間点ｈの補間点情報（１，１，１）に変更される。なお、探索された補間点の補間点属性は、既に「前線候補」に変更されているので、ここでは変更されない。
【００８３】
さらに、三角形Ｔ２については、同一補間点について同期をとるための更新が行われている。
【００８４】
そして最後に、前線上存在補間点ｈである補間点（１，１，１）は、補間点属性が前線通過完了と変更される。
【００８５】
さらに、補間点属性が「前線候補」である補間点の中から経路距離が最短の補間点（１，１，２）が、前線上存在補間点ｈとして選択される。この場合、図３５で点線矢印で示すように、三角形Ｔ１の辺（Ｔ１，Ｅ３）及び（Ｔ１，Ｅ２）を探索対象の辺として特定し、それらの辺上の５つの補間点を順に探索する。そうすると、補間点管理テーブルは、図３４の状態から図３６の状態に変化する。すなわち、（１，２，１）（１，２，２）（１，３，０）（１，３，１）（１，３，２）の補間点について補間点（１，１，２）からの経路距離を算出すると、補間点（１，２，１）及び（１，２，２）については経路距離が短くなっていることが分かる。そのため、それらの補間点（図３６の星印の行）については、経路距離が今回の算出値に変更される。さらに、それらの復帰点情報は、前線上存在補間点ｈの補間点情報（１，１，２）に変更される。なお、探索された補間点の補間点属性は、既に「前線候補」に変更されているので、ここでは変更されない。
【００８６】
さらに、三角形Ｔ２については、同一補間点について同期をとるための更新が行われている。
【００８７】
そして最後に、前線上存在補間点ｈである補間点（１，１，２）は、補間点属性が前線通過完了と変更される。
【００８８】
その後、補間点属性が「前線候補」である補間点の中から経路距離が最短の補間点（２，１，０）（＝（１，２，０））が、前線上存在補間点ｈとして選択される。この場合、図３７で点線矢印で示すように、三角形Ｔ２の辺（Ｔ２，Ｅ３）、（Ｔ２，Ｅ２）及び（Ｔ２，Ｅ１）を探索対象の辺として特定し、それらの辺上の８つの補間点を順に探索する。そうすると、補間点管理テーブルは、図３６の状態から図３８の状態に変化する。すなわち、（２，１，１）（２，１，２）（２，２，０）（２，２，１）（２，２，２）（２，３，０）（２，３，１）（２，３，２）の補間点について補間点（２，１，０）からの経路距離を算出すると、補間点（２，１，１）（２，１，２）（２，２，０）（２，２，１）（２，２，２）については経路距離が短くなっていることが分かる。そのため、それらの補間点（図３８の星印の行）については、経路距離が今回の算出値に変更される。さらに、それらの復帰点情報は、前線上存在補間点ｈの補間点情報（２，１，０）に変更される。さらに、それらの補間点の補間点属性は、「前線候補」に変更されている。
【００８９】
このような処理を繰り返し実施して、経路出発線上の補間点について探索処理が完了して前線候補点集合から除去された後に、経路距離が最も短い前線候補点は、補間点（１，２，１）（＝（２，３，２））である。この補間点（１，２，１）が前線上存在補間点ｈとして選択される。この場合、図３９で点線矢印で示すように、三角形Ｔ２の辺（Ｔ２，Ｅ１）及び（Ｔ２，Ｅ２）を探索対象の辺として特定し、それらの辺上の５つの補間点を順に探索する。そうすると、補間点管理テーブルは、図３８の状態から図４０の状態に変化する。すなわち、（２，１，１）（２，１，２）（２，２，０）（２，２，１）（２，２，２）の補間点について補間点（１，２，１）からの経路距離を算出すると、いずれの補間点についても経路距離が短くならない。そのため、経路距離が更新されるものはない。また、復帰点情報も補間点属性も今回は変更されない。但し、補間点（１，２，１）（＝（２，３，２）の補間点属性は、「前線通過完了」に変更される。
【００９０】
以上のような処理を繰り返し実施することによって、三角形メッシュの三角形要素に補間点を導入するが、補間点間のアークを規定・利用することなく探索を実施するので、データ量は削減され、処理も高速化される。
【００９１】
上で述べた方法でも実施可能であるが、最短距離の算出についてはさらに工夫が可能である。図４１に示すように、経路上のある補間点ｐから、補間点ｒ1及びｒ2を経由して、前線上存在補間点ｈに至った場合において、これらの補間点が属する三角形Ｔ1乃至Ｔ3が例えば三角形Ｔ1の属する平面に展開できたとする。そうすると、予め設定されている補間点ｒ1及びｒ2を経由すると補間点ｐから前線上存在補間点ｈまでの経路Ｘは、補間点ｐから前線上存在補間点ｈの直線距離Ｙよりも長くなってしまう。従って、前線上存在補間点ｈについての経路距離を登録する際には、例えば経路Ｘではなく経路Ｙの直線距離を用いて経路距離を算出する方が正確である。
【００９２】
このような平面展開による経路距離の算出及び平面展開による経路距離を算出した際に採用されるべき補間点の位置修正（すなわち図４１ではｒ1からｒaへの変更、ｒ2からｒbへの変更）については、以下で説明するような処理によって実現される。
【００９３】
Ａ．平面展開経路距離修正処理
本処理については図４２乃至図４９を用いて説明する。なお、本処理は、ステップＳ９において前線上存在補間点を特定する毎に実施する。
【００９４】
処理の具体的な説明を行う前に、平面展開区間及び平面展開区間端点について説明しておく。上で述べたように三角形メッシュにおいて経路上の三角形要素を平面に展開して直線で結ぶ必要があるため、経路上の三角形要素全てを平面に展開できるわけではなく、また平面に展開することが好ましくない場合もある。従って、以下で述べる条件を満たす補間点（頂点を含む）を検出した場合には、その補間点まで又はその一つ手前の補間点で平面展開を一旦停止するものとし、その補間点を平面展開区間端点と呼ぶことにする。また、図４２に示すように、経路上隣接する平面展開区間端点間（例えばＰ１とＰ２の間及びＰ２とＰ３の間）及び前線存在補間点ｈと経路上直前の平面展開区間端点Ｐ３との間を平面展開区間と呼ぶこととする。前線存在補間点ｈと平面展開区間端点Ｐ３の間の平面展開区間については、次の平面展開区間端点が検出されるまで長くなる。
【００９５】
平面展開区間端点と特定する条件は、２通りある。条件Ａは以下のとおりである。
（１）新たに進んだ前線上存在補間点が三角形の頂点に到達した場合
（２）新たに進んだ前線上存在補間点から平面展開区間端点への線分が途中の全ての辺と交差する状態ではない場合
（３）区間を構成する補間点の数が予め定めた条件を満たさなくなった場合
この３つのうちいずれかを満たしている場合には、平面展開区間端点と判断される。
【００９６】
一方、条件Ｂは以下のとおりである。
（１）新たに進んだ前線上存在補間点から平面展開区間端点への線分が途中の全ての辺と交差する状態ではない場合
（２）区間を構成する補間点の数が予め定めた条件を満たさなくなった場合
この２つのうちいずれかを満たしている場合には、平面展開区間端点と判断される。
【００９７】
条件Ａ（２）及びＢ（１）は、例えば図４３に示すような状況を示している。なお、以下では既に１平面上に辺や補間点が展開されているものとする。図４３では、辺ｅ1上に平面展開区間端点Ｐ１が属しており、辺ｅ2上に経路上の補間点ｒ1が属しており、辺ｅ3上に経路上の補間点ｒ2が属しており、辺ｅ4上の経路上の補間点ｒ3が属しており、辺ｅ5上に経路上の補間点ｈ、すなわち前線上存在補間点が属している場合を想定する。この際、補間点ｒ1と平面展開区間端点Ｐ１とは互いに隣接する経路上の補間点なので必ず条件Ａ（２）及びＢ（１）を満たさなくなってしまうので判定外であるが、補間点ｒ2と平面展開区間端点Ｐ１とを結ぶ線分は、辺ｅ2と交差し、補間点ｒ3と平面展開区間端点Ｐ１とを結ぶ線分は、辺ｅ2及びｅ3と交差するので、条件Ａ（２）及びＢ（１）を満たしていない。しかしながら、前線上存在補間点ｈと平面展開区間端点Ｐ１とを結ぶ線分は、辺ｅ4とは交差しているが、辺ｅ3及びｅ2については交差していないので、条件Ａ（２）及びＢ（１）を満たすようになる。このように平面展開区間端点Ｐ１から見てある程度の幅で前線上存在補間点が特定されて経路が伸びていく限りにおいては特に問題が生じない。しかし、図４３の例のように、経路が曲がったような場合にまで直線で結んだ経路を採用してしまうと、途中の補間点ｒ1、ｒ2及びｒ3を同じ辺上に定義できなくなり、復帰点が正しく規定できないという問題が生ずる。すなわち、２点を結ぶ直線が最短経路を形成しない。そこで、このような条件Ａ（２）及びＢ（１）に該当するような前線上存在補間点ｈを検出した場合には、経路上直前の補間点ｒ3（すなわち前線上存在補間点ｈの復帰点）を平面展開区間端点として特定する。
【００９８】
なお、条件Ａ（１）については、２点を結ぶ直線が最短経路を形成しない場合にはその補間点を平面展開区間端点として特定する。しかしながら、必ずしも特徴的な点でない場合もあり、平面展開しても問題ないこともあるので、条件Ｂでは採用していない。例えば図４４に示すように、平面展開区間端点Ｐ１から前線上存在補間点ｈまで平面展開を実施した場合に、辺ｅ1と辺ｅ2との頂点が平面展開区間端点Ｐ１であり、辺ｅ3上に経路上の次の補間点ｒ1が存在し、辺ｅ4上に経路上の次の補間点ｒ2が存在し、辺ｅ5とｅ6との交点が経路上の頂点ｒ3であり、辺ｅ7上に経路上の前線上存在補間点ｈが存在するものとする。このとき、条件Ａを採用する場合には、頂点ｒ3が平面展開区間端点として特定されるようになる。しかしながら、頂点ｒ3と平面展開区間端点Ｐ１とを結ぶ線分は、途中の辺ｅ3及びｅ4と交差する。すなわち途中の辺においても補間点を規定して復帰点を特定できる。そこで、条件Ｂを採用して、頂点ｒ3では平面展開区間を終了させず、前線上存在補間点ｈと平面展開区間端点Ｐ１への線分について確認すると、途中の辺と交差するので、前線上存在補間点ｈまで平面展開区間を延ばせる。これによって、直線距離を算出できる長さが長くなるので、経路距離の精度向上が可能となる。但し、条件Ａ（１）についても、３次元モデルの形状によっては必要な場合もある。
【００９９】
以上のような前提を下に、図４５乃至図４９を用いて具体的な処理内容を説明する。
【０１００】
まず、距離補正部１６１は、前線上存在補間点を特定する（図４５：ステップＳ３１）。ステップＳ９と同じである。そして、直前の平面展開区間端点を特定する（ステップＳ３３）。例えば、図１６に示した補間点管理テーブルのデータ・フォーマットを、例えば図４６に示すようなデータ・フォーマットに変更する。すなわち、図１６のテーブルに、平面展開区間端点であるか否かを表すフラグである端点フラグの列を追加している。端点フラグは、以下で述べる処理で平面展開区間端点であると判断された場合にセットされ、さらに経路出発線上の補間点については初期的にセットする。図４６は、初期設定が完了した状態を示している。
【０１０１】
そして、距離補正部１６１は、直前の平面展開区間端点が、前線上存在補間点の直前の復帰補間点であるか判断する（ステップＳ３５）。この条件を満たす場合には、直線的に前線上存在補間点と平面展開区間端点とが結ばれているので、処理を行う必要はない。従って、この条件を満たす場合には元の処理に戻る。一方、この条件を満たさない場合には、平面展開区間生成処理を実施する（ステップＳ３７）。この処理については以下に詳細に述べる。そして、元の処理に戻る。
【０１０２】
次に、平面展開区間生成処理について図４７乃至図４９を用いて説明する。まず、距離補正部１６１は、前線上存在補間点に係る復帰三角形を平面展開基準平面として特定する（ステップＳ４１）。例えば図４８のような状況を想定する。前線上補間点ｈと経路上直前の補間点ｒ1とを含む復帰三角形Ｔ1（頂点ＡＢＣ）を平面展開基準平面として特定する。復帰三角形は、補間点管理テーブル（図４６）において復帰点情報として登録されている。そして、次の復帰三角形を特定する（ステップＳ４３）。図４８の例では、三角形Ｔ2を特定する。また、次の復帰三角形の平面展開行列を算出し、例えば処理データ格納部１７に格納する（ステップＳ４５）。次の復帰三角形の平面展開行列の算出方法を、説明する。まず、次の復帰三角形Ｔ2の頂点Ｑから辺ＡＢへ下ろした垂線からの足を点Ｈをする。この点Ｈから頂点Ｑの平面展開基準平面への投影点Ｑtへの単位ベクトルをｖ1とし、点Ｈから頂点Ａへの単位ベクトルをｖ3とすると、ｖ2＝ｖ3×ｖ1となる。また、ベクトルＨＱとｖ1がなすｖ2方向の角をθとする。そして以下のような行列を定義する。
【数２】
【数３】
【０１０３】
このような前提の下、次の復帰三角形Ｔ2上の任意の点Ｘの、平面展開基準平面への平面展開は以下の式で表される。
Ｘt＝ＭＲＭTＸ＋（Ｅ−ＭＲＭT）Ｈ （１）
但し、Ｈは点Ｈの位置ベクトルである。
【０１０４】
この式の詳細な説明は省略するが、ｖ1、ｖ2、ｖ3で張られる局所座標系における軸ＡＢの角θの回転を、世界座標系に戻す演算を表したものである。
【０１０５】
なお、本ステップで算出される平面展開行列ＭＲＭT及び（Ｅ−ＭＲＭT）Ｈについては後の演算でも用いるので、例えば処理データ格納部１７に格納しておく。
【０１０６】
上の説明では平面展開基準平面である三角形Ｔ1と次の復帰三角形である三角形Ｔ2との関係を表したものであって、平面展開区間端点にたどり着かない場合には、三角形Ｔ2とさらに次の復帰三角形Ｔ3との関係を表す平面展開行列を算出する。また、それでも平面展開区間端点にたどり着かない場合には、三角形Ｔ3とさらに次の復帰三角形Ｔ4との関係を表す平面展開行列を算出する。このように平面展開区間端点にたどり着くまで繰り返し平面展開行列を算出する。平面展開区間端点にたどり着いた場合には、その前の復帰三角形Ｔn-1と平面展開区間端点ｈ及び経路上直前の補間点に係る三角形Ｔnとについての平面展開行列を算出することになる。
【０１０７】
その後、距離補正部１６１は、平面展開行列を用いて復帰補間点ｒ1を含む辺ＡＢの両端の頂点Ａ及びＢと復帰補間点ｒ1を平面展開基準平面に展開し、処理結果である座標値を例えば処理データ格納部１７に格納する（ステップＳ４７）。
【０１０８】
本ステップでは、（１）式に従って座標値を算出するわけであるが、通常は図４８の例のように１回で平面展開区間端点ｈに到達する訳ではない。２回目は、直前のステップＳ４５で算出された平面展開行列を用いて（１）式に従って演算した後に、得られた座標値と１回前のステップＳ４５で算出された平面展開行列とを用いて（１）式に従って演算する。
【０１０９】
３回目は、直前のステップＳ４５で算出された平面展開行列を用いて（１）式に従って演算し、得られた座標値と１回前のステップＳ４５で算出された平面展開行列とを用いて（１）式に従って演算し、さらに得られた座標値と２回前のステップＳ４５で算出された平面展開行列とを用いて（１）式に従って演算する。このような処理が繰り返されることとなる。
【０１１０】
その後、距離補正部１６１は、平面展開区間端点ｈまで処理が進んだか、すなわち次の復帰三角形が平面展開区間端点ｈが属する三角形要素になったか判断する（ステップＳ４９）。平面展開区間端点ｈまで処理が進んでいない場合にはステップＳ４３に戻る。
【０１１１】
一方、平面展開区間端点ｈまで処理が進んでいる場合には、距離補正部１６１は、前線上存在補間点と平面展開区間端点の平面展開点とを結ぶ直線が、平面展開された全ての辺と交差するか検査する（ステップＳ５１）。図４３に示した前線上存在補間点ｈについては、平面展開された全ての辺と交差するわけではないことが分かる。
【０１１２】
そして、距離補正部１６１は、前線上存在補間点と平面展開区間端点の平面展開点とを結ぶ直線が、平面展開された全ての辺と交差するか判断し（ステップＳ５３）、平面展開されたいずれかの辺と交差しない場合には、補間点管理テーブル（図４６）において前線上存在補間点の経路上直前の復帰補間点を、平面展開区間端点に設定する（ステップＳ５５）。このようにステップＳ５３で条件を満たさないと判断された場合には、平面展開区間端点と前線上存在補間点とを直線で結ぶことはないので、距離を補正する必要はない。具体的には、前回の距離補正がそのまま利用でき、前線上存在補間点と経路上直前の補間点（すなわち復帰点）との間は三角形内部距離Δｄとして算出されたものを用いれば、前線上存在補間点ｈまでの距離が得られる。
【０１１３】
一方、ステップＳ５３の条件を満たしていると判断された場合には、処理は端子Ｃを介して図４９の処理に移行する。
【０１１４】
そして、距離補正部１６１は、平面展開区間端点と前線上存在補間点との間の距離を算出し、例えばメインメモリなどの記憶装置に格納する（図４９：ステップＳ５７）。点間の距離の計算は周知なので、ここでは述べない。そして、補間点管理テーブルに格納されている、平面展開区間端点における距離に、ステップＳ５７で算出した距離を加算して、前線上存在補間点の経路距離として補間点管理テーブルに登録する（ステップＳ５９）。そして、前線上存在補間点が平面展開区間端点の条件Ａ又はＢを満たすか判断する（ステップＳ６１）。条件Ａであれば、条件Ａ（１）及び（３）を満たしているか、条件Ｂであれば、条件Ｂ（２）を満たしているか判断する。満たしている場合には、補間点管理テーブルにおいて、前線上存在補間点を平面展開区間端点に設定する（ステップＳ６３）。そして元の処理に戻る。満たしていない場合には、ステップＳ５９は不要なので元の処理に戻る。
【０１１５】
以上のような処理を実施することでより精度のよい経路距離の算出が可能となる。
【０１１６】
なお、平面展開経路距離修正処理は、上で述べた最短経路探索処理だけではなく、ダイクストラ法にも適用可能である。すなわち、ダイクストラ法における「最小の距離ｄをもつノードｚ∈Ｕを１つ探索」という処理において、重み付きグラフとは別に三角形メッシュを保持しておき、この三角形メッシュに対して同一の処理を行って距離ｄを補正すればよい。
【０１１７】
Ｂ．補間点位置補正処理
平面展開経路距離修正処理を実施すると、経路上の補間点の位置は初期的に設定した位置（又は想定した位置）とは異なる位置となる。従って、平面展開経路距離修正処理を実施する場合には、補間点位置補正処理を実施することが好ましい。しかし、補間点位置補正処理は、平面展開経路距離修正処理のようにステップＳ９で実施せずとも、経路到達線に前線上存在補間点が到達したときに１回実施すれば十分である。以下では、ステップＳ１３で実施する場合を前提に説明する。但し、平面展開経路距離修正処理と共に実施しても良い。
【０１１８】
補間点位置補正部１６２は、経路到達線上の前線上存在補間点を第１平面展開区間端点として特定する（図５０：ステップＳ７１）。また、補間点管理テーブル（図４６）において、経路到達線上の前線上存在補間点の復帰点から順次経路を遡ることによって、第１平面展開区間端点に最も近い平面展開区間端点を第２平面展開区間端点として特定する（ステップＳ７３）。
【０１１９】
そして、補間点位置補正部１６２は、位置補正処理を実施する（ステップＳ７５）。この処理については図５１乃至図５４を用いて説明する。まず、補間点位置補正部１６２は、第１平面展開区間端点の復帰三角形を平面展開基準平面として特定する（図５１：ステップＳ８１）。ステップＳ４１と同様である。そして、次の復帰三角形を特定する（ステップＳ８３）。これもステップＳ４３と同様である。さらに、次の復帰三角形の平面展開行列を算出し、例えば処理データ格納部１７に格納する（ステップＳ８５）。これもステップＳ４５と同様である。
【０１２０】
その後、補間点位置補正部１６２は、平面展開行列を用いて復帰補間点を含む辺の両端の頂点を平面展開基準平面に展開し、処理結果である座標値を例えば処理データ格納部１７に格納する（ステップＳ８７）。これもステップＳ４７とほぼ同様である。但し、復帰補間点の展開点は不要である。
【０１２１】
その後、補間点位置補正部１６２は、第２平面展開区間端点まで処理が進んだか、すなわち次の復帰三角形が第２平面展開区間端点が属する三角形要素になったか判断する（ステップＳ８９）。このステップも実質的にステップＳ４９と同様である。第２平面展開区間端点まで処理が進んでいない場合にはステップＳ８３に戻る。
【０１２２】
一方、第２平面展開区間端点まで処理が進んだ場合には、補間点位置補正部１６２は、第１及び第２の平面展開区間端点の平面展開点を結ぶ直線を含み、平面展開基準平面に直交するパラメタ算出平面を算出する（ステップＳ９１）。具体的には、例えば図５２に示すように、平面展開基準平面Ｋに第１平面展開区間端点Ｐ１及び第２の平面展開区間端点Ｐ２の展開点Ｐ２tとが属しており、それらを結ぶ線分ｍをとおり且つ平面展開基準平面Ｋに直交する平面Ｌがパラメタ算出平面である。なお、平面展開基準平面Ｋ上には、経路上の補間点ｒが属する辺ＡＢの展開点Ａt及びＢtも存在しており、線分ＡtＢtとパラメタ算出平面の交点ｒnewtは、辺ＡＢ上の新たな補間点ｒnewの展開点となる。処理は端子Ｄを介して図５３の処理に移行する。
【０１２３】
図５３の処理に移行して、補間点位置補正部１６２は、第１の平面展開区間端点から順に、未処理の次の復帰補間点を特定する（ステップＳ９３）。そして、特定された復帰補間点は第２の平面展開区間端点であるか判断する（ステップＳ９５）。特定された復帰補間点が第２の平面展開区間端点であれば、元の処理に戻る。
【０１２４】
一方、特定された復帰補間点が第２の平面展開区間端点でない場合には、補間点位置補正部１６２は、特定された復帰補間点が属する復帰辺をパラメタ算出平面で切断したときの辺のパラメタｘを算出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ９７）。すなわち、ｒnewt＝（１−ｘ）Ａt＋ｘＢtという関係があり、ｒnewtを算出すると共に、上記式を満たすｘを算出する。
【０１２５】
その後、補間点位置補正部１６２は、平面展開前の復帰辺（すなわち特定された復帰補間点が属する辺）をパラメタ値ｘにより分割して、特定された補間点の新たな座標値を算出し、例えば補間点データ格納部１３に格納する（ステップＳ９９）。すなわち、図５４に示すように、ｒnew＝（１−ｘ）Ａ＋ｘＢという関係から新たな座標値が算出される。処理はステップＳ９３に戻り、さらに次の復帰補間点を特定して処理を実施する。
【０１２６】
以上のような処理を実施することによって、補間点位置を、平面展開区間において補正することができる。
【０１２７】
図５０の処理の説明に戻り、補間点位置補正部１６２は、ステップＳ７５の後に、第２平面展開区間端点が経路出発線上の補間点であるか判断する（ステップＳ７７）。第２平面展開区間端点が経路出発線上の補間点でない場合には、第２平面展開区間端点を第１平面展開区間端点として設定し、次に近い平面展開区間端点を第２平面展開区間端点に設定する（ステップＳ７９）。補間点管理テーブルで復帰点を探索することによって次の平面展開区間端点は見つけることができる。そしてステップＳ７５に戻る。一方、第２平面展開区間端点が経路出発線上の補間点である場合には、元の処理に戻る。
【０１２８】
以上のような処理を実施することによって、経路上の補間点位置を、平面展開経路距離修正処理における経路距離に従った形で補正することができるようになる。
【０１２９】
以上本技術の一実施の形態を説明したが、本技術はこれに限定されるものではない。すなわち、例えば図５に示した機能ブロック図は一例であって、必ずしも実際のプログラムモジュール構成と一致しない場合もある。また、複数台のコンピュータで機能分担を行うようにしても良い。
【０１３０】
また、処理結果が変わらない限り、処理ステップの実行順番を入れ替えたり、並列実行するようにしても良い。
【０１３１】
さらに、上では図１０を用いて位相テーブルの例を示したが、位相情報は図１０の位相テーブルに限定されるわけではない。メッシュの位相情報は、メッシュを構成する三角形、辺、頂点の接続関係を表現するものであり、多くの表現方法が知られている。メッシュの位相表現は、境界表現（boundary representation, B-Rep）と呼ばれる立体表面の面分、辺、頂点を表現する位相構造の特別なものである。
【０１３２】
よく知られている境界表現による物体表現方法に、１９７４年にBruce Guenther Baumgartによって発表されたウイングドエッジ構造がある。これは、図５５に示すように、物体表面のフェース（面分。ここでは三角形に対応する）、辺、頂点にそれぞれ識別子を付し、各辺から両端の頂点、両側のフェース、両端の頂点に接続する両側のフェースに帰属する合計４個の辺へのポインタを保有することによって、物体表面の位相構造を表現するものである。
【０１３３】
ウイングドエッジ構造は辺がベースになっており、辺とフェース、辺と頂点の間の隣接関係を用いて、物体全ての位相要素の接続関係を表現している。Weilerによれば隣接関係の選択方法は９通りあるので、位相表現のバリエーションは多数存在することが知られている。”Kevin Weiler: Edge-Based Data Structure for Solid Modeling in Curved-Surface Environments, IEEE CG&A 1985 Jan. p.21-40”を参照のこと。なお、本実施の形態で挙げたメッシュの表現方法は三角形メッシュの場合に限ると、データ量がウイングドエッジ構造よりも小さいのが特徴である。
【０１３４】
なお、最短経路探索装置は、コンピュータ装置であって、図５６に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納される。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１３５】
以上本実施の形態をまとめると以下のようになる。
【０１３６】
３次元モデル上における最短経路をコンピュータにより探索する最短経路探索方法は、３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する三角形及び辺のデータに当該三角形の頂点及び補間点のデータを関連付けて探索管理データ格納部に格納するステップと、３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付けるステップと、出発点又は出発線から到達点又は到達線に至るまで、補間点及び頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である補間点又は頂点について出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、最短距離探索対象点である補間点又は頂点に関連付けて距離を探索管理データ格納部に格納する探索ステップとを含む。
【０１３７】
このように三角形メッシュに含まれる各三角形要素の辺に補間点を追加することによって精度向上を図ることができる。また、補間点間のアークを生成することもないので、保持すべきデータ量を著しく削減できる。さらに補間点間のアークを生成することがないので、その分の計算時間をも削減することができる。
【０１３８】
なお、上で述べた探索ステップが、最短距離探索対象点である補間点又は頂点に関連付けて最短距離探索対象点の経路上直前の補間点又は頂点を特定するためのデータを、探索管理データ格納部に格納するステップを含むようにしてもよい。その場合、本最短経路探索方法は、探索管理データ格納部において到達点又は到達線上の補間点又は頂点に関連付けて出発点又は出発線からの最短距離が登録された場合には、探索管理データ格納部において、到達点又は到達線上の補間点又は頂点から出発点又は出発線上の補間点又は頂点まで、経路上の補間点又は頂点に関連付けて格納されている経路上直前の補間点又は頂点を特定するためのデータを抽出することによって最短経路を特定する経路特定ステップをさらに含むようにしてもよい。これによって、最短距離だけではなく、最短経路も特定できるようになる。
【０１３９】
さらに、上で述べた探索ステップが、最短距離探索対象点である補間点又は頂点に関連付けて最短距離探索対象点の経路上直前の補間点又は頂点を特定するための復帰情報を、探索管理データ格納部に格納するステップを含むようにしてもよい。その際には、探索ステップにおいて、三角形メッシュの位相情報と復帰情報とに基づき予め定められるルールに従って、探索先の補間点又は頂点を特定するようにしてもよい。これによって、適切な探索先が特定されるので、網羅的な探索よりも高速に処理が行われるようになる。
【０１４０】
また、上で述べた探索ステップが、探索管理データ格納部に距離が格納済みであって且つ最短距離探索対象点の探索元の候補点となる補間点及び頂点を管理するデータを格納する候補管理データ格納部に格納されている候補点から、探索管理データ格納部に登録されている距離が最短の候補点を、最短距離探索対象点の探索元点として特定するステップと、探索元点を含む三角形に係る補間点又は頂点を最短距離探索対象点として特定して、候補管理データ格納部に格納する特定ステップと、最短距離探索対象点の探索が完了した場合、候補管理データ格納部から探索元点を削除する削除ステップとを含むようにしてもよい。このようにすることによって探索が効率的に実施される。
【０１４１】
また、上で述べた削除ステップが、探索元点に関連付けて通過完了を示すデータを探索管理データ格納部に登録するステップを含むようにしてもよい。その際、特定ステップにおいて、通過完了を示すデータが登録されている補間点又は頂点を除外して最短距離探索対象点を特定するようにしてもよい。効率的な探索が可能となる。
【０１４２】
さらに、上で述べた探索ステップが、最短距離探索対象点を含む経路の少なくとも一部区間について、補間点又は頂点間の距離の和から、一部区間に係る三角形を平面展開した場合における一部区間両端の直線距離へ修正する距離修正ステップを含むようにしてもよい。これによって距離の精度を高めることができるようになる。
【０１４３】
さらに、探索管理データ格納部において、直線距離を算出できる区間の端点である補間点又は頂点に関連付けて平面展開区間端点を示すデータを登録していてもよい。その際 距離修正ステップが、最短距離探索対象点及び当該最短距離探索対象点の経路上直前の補間点又は頂点を含む三角形を包含する平面に、最短距離探索対象点から最も近い平面展開区間端点までの経路区間上の補間点又は頂点及び当該補間点又は頂点に係る三角形の辺を投影するステップと、平面上において、最短距離探索対象点と、平面展開区間端点とを結ぶ直線が、当該経路区間上の補間点又は頂点がのっている三角形の全ての辺と交差するか判断する判断ステップと、判断ステップの条件を満たす場合には、最短距離探索対象点から平面展開区間端点までの直線距離を算出し、探索管理データ格納部において平面展開区間端点に関連付けて格納されている距離と直線距離を加算して、探索管理データ格納部において最短距離探索対象点に関連付けて加算結果を登録するステップとを含むようにしてもよい。これによって距離の精度を高めることができるようになる。
【０１４４】
また、上で述べた距離修正ステップが、判断ステップの条件を満たさない場合には、最短距離探索対象点の経路上直前の補間点に関連付けて平面展開区間端点を示すデータを、探索管理データ格納部に登録するステップと、判断ステップの条件を満たす場合には、予め定められた平面展開区間端点の条件を最短距離探索対象点が満たすか判断し、満たすと判断された場合には、最短距離探索対象点に関連付けて平面展開区間端点を示すデータを、探索管理データ格納部に登録するステップとを含むようにしてもよい。このようにすれば、適切な範囲で平面展開を実施することができるようになる。
【０１４５】
なお、上で述べた判断ステップの条件が、三角形メッシュの頂点であるという条件を含む場合もある。頂点というものは形状上の特徴点となりうるからである。
【０１４６】
また、上で述べた経路特定ステップが、最短距離探索対象点を含む経路の少なくとも一部区間について、一部区間に係る三角形を平面展開した場合における一部区間両端をつなぐ直線を含み且つ平面展開後の平面に直交する第２の平面と上記一部区間に係る三角形の辺との交点に、一部区間における補間点を変更するステップを含むようにしてもよい。これによって適切な補間点位置を特定できるようになる。
【０１４７】
さらに、上で述べた三角形メッシュにおける三角形に屈折率が設定されるようにしてもよい。この場合、上記距離を、経路上の三角形の屈折率を用いて算出するようにする。例えば絶縁率が３次元モデルの部分毎に異なる場合に、当該絶縁率を勘案した形で距離を算出することによって、適切に沿面距離を算出するものである。
【０１４８】
なお、上で述べたような処理をハードウエアに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。
【０１４９】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１５０】
（付記１）
３次元モデル上における最短経路をコンピュータにより探索する最短経路探索方法であって、
前記３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する前記三角形及び前記辺のデータに当該三角形の頂点及び前記補間点のデータを関連付けて探索管理データ格納部に格納するステップと、
前記３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付けるステップと、
前記出発点又は出発線から前記到達点又は到達線に至るまで、前記補間点及び前記頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である前記補間点又は前記頂点について前記出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記距離を前記探索管理データ格納部に格納する探索ステップと、
を含む最短経路探索方法。
【０１５１】
（付記２）
前記探索ステップが、
前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記最短距離探索対象点の経路上直前の前記補間点又は前記頂点を特定するためのデータを、前記探索管理データ格納部に格納するステップ
を含み、
前記探索管理データ格納部において前記到達点又は到達線上の前記補間点又は前記頂点に関連付けて前記出発点又は出発線からの最短距離が登録された場合には、前記探索管理データ格納部において、前記到達点又は到達線上の前記補間点又は前記頂点から前記出発点又は出発線上の前記補間点又は前記頂点まで、経路上の前記補間点又は前記頂点に関連付けて格納されている前記経路上直前の前記補間点又は前記頂点を特定するためのデータを抽出することによって最短経路を特定する経路特定ステップ
をさらに含む、付記１記載の最短経路探索方法。
【０１５２】
（付記３）
前記探索ステップが、
前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記最短距離探索対象点の経路上直前の前記補間点又は前記頂点を特定するための復帰情報を、前記探索管理データ格納部に格納するステップ
を含み、
前記探索ステップにおいて、
前記三角形メッシュの位相情報と前記復帰情報とに基づき予め定められるルールに従って、探索先の前記補間点又は前記頂点を特定する
付記１記載の最短経路探索方法。
【０１５３】
（付記４）
前記探索ステップが、
前記探索管理データ格納部に前記距離が格納済みであって且つ前記最短距離探索対象点の探索元の候補点となる前記補間点及び前記頂点を管理するデータを格納する候補管理データ格納部に格納されている前記候補点から、前記探索管理データ格納部に登録されている前記距離が最短の候補点を、前記最短距離探索対象点の探索元点として特定するステップと、
前記探索元点を含む前記三角形に係る前記補間点又は前記頂点を前記最短距離探索対象点として特定して、前記候補管理データ格納部に格納する特定ステップと、
前記最短距離探索対象点の探索が完了した場合、前記候補管理データ格納部から前記探索元点を削除する削除ステップと、
を含む付記１又は２記載の最短経路探索方法。
【０１５４】
（付記５）
前記削除ステップが、
前記探索元点に関連付けて通過完了を示すデータを前記探索管理データ格納部に登録するステップ
を含み、
前記特定ステップにおいて、前記通過完了を示すデータが登録されている前記補間点又は前記頂点を除外して前記最短距離探索対象点を特定する
付記４記載の最短経路探索方法。
【０１５５】
（付記６）
前記探索ステップが、
前記最短距離探索対象点を含む経路の少なくとも一部区間について、前記補間点又は前記頂点間の距離の和から、前記一部区間に係る三角形を平面展開した場合における前記一部区間両端の直線距離へ修正する距離修正ステップ
を含む付記１乃至５のいずれか１つ記載の最短経路探索方法。
【０１５６】
（付記７）
前記探索管理データ格納部において、直線距離を算出できる区間の端点である補間点又は頂点に関連付けて平面展開区間端点を示すデータを登録しており、
前記距離修正ステップが、
前記最短距離探索対象点及び当該最短距離探索対象点の経路上直前の前記補間点又は前記頂点を含む三角形を包含する平面に、前記最短距離探索対象点から最も近い前記平面展開区間端点までの経路区間上の前記補間点又は前記頂点及び当該補間点又は前記頂点に係る三角形の辺を投影するステップと、
前記平面上において、前記最短距離探索対象点と、前記平面展開区間端点とを結ぶ直線が、当該経路区間上の補間点又は頂点がのっている前記三角形の全ての辺と交差するか判断する判断ステップと、
前記判断ステップの条件を満たす場合には、前記最短距離探索対象点から前記平面展開区間端点までの直線距離を算出し、前記探索管理データ格納部において前記平面展開区間端点に関連付けて格納されている前記距離と前記直線距離を加算して、前記探索管理データ格納部において前記最短距離探索対象点に関連付けて加算結果を登録するステップと、
を含む付記６記載の最短経路探索方法。
【０１５７】
（付記８）
前記距離修正ステップが、
前記判断ステップの条件を満たさない場合には、前記最短距離探索対象点の経路上直前の前記補間点に関連付けて前記平面展開区間端点を示すデータを、前記探索管理データ格納部に登録するステップと、
前記判断ステップの条件を満たす場合には、予め定められた前記平面展開区間端点の条件を前記最短距離探索対象点が満たすか判断し、満たすと判断された場合には、前記最短距離探索対象点に関連付けて前記平面展開区間端点を示すデータを、前記探索管理データ格納部に登録するステップと、
をさらに含む付記７記載の最短経路探索方法。
【０１５８】
（付記９）
前記判断ステップの条件が、前記三角形メッシュの頂点であるという条件を含む
付記７又は８記載の最短経路探索方法。
【０１５９】
（付記１０）
前記経路特定ステップが、
前記最短距離探索対象点を含む経路の少なくとも一部区間について、前記一部区間に係る三角形を平面展開した場合における前記一部区間両端をつなぐ直線を含み且つ前記平面展開後の平面に直交する第２の平面と前記一部区間に係る三角形の辺との交点に、前記一部区間における前記補間点を変更するステップ
を含む付記２記載の最短経路探索方法。
【０１６０】
（付記１１）
前記三角形メッシュにおける三角形に屈折率が設定されており、
前記距離を、前記経路上の三角形の屈折率を用いて算出する
付記１乃至１０のいずれか１つ記載の最短経路探索方法。
【０１６１】
（付記１２）
付記１乃至１１のいずれか１つ記載の最短経路探索方法をコンピュータに実行させるためのプログラム。
【０１６２】
（付記１３）
３次元モデル上における最短経路を探索する最短経路探索装置であって、
探索管理データ格納部と、
三角形メッシュの位相情報を含む、当該三角形メッシュのデータを格納する三角形メッシュデータ格納部と、
前記三角形メッシュデータ格納部に格納されている、前記３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する前記三角形及び前記辺のデータに当該三角形の頂点及び前記補間点のデータを関連付けて前記探索管理データ格納部に格納する手段と、
前記３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付ける手段と、
前記出発点又は出発線から前記到達点又は到達線に至るまで、前記補間点及び前記頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である前記補間点又は前記頂点について前記出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記距離を前記探索管理データ格納部に格納する探索手段と、
を有する最短経路探索装置。
【符号の説明】
【０１６３】
１１ 三角形メッシュデータ格納部 １２ 補間点データ生成部
１３ 補間データ格納部 １４ データ入力部
１５ 開始終了データ格納部 １６ 探索処理部
１７ 処理データ格納部 １８ 出力データ格納部
１９ 出力部
１６１ 距離補正部 １６２ 補間点位置補正部
【技術分野】
【０００１】
本技術は、３次元モデル上における経路出発線（点に縮退している場合を含む）と経路到達線（点に縮退している場合を含む）との間の最短経路を探索するための技術に関する。
【背景技術】
【０００２】
例えば、電子機器の表面に露出した導体間を当該表面に沿って放電するような場合があるため、電子機器の設計時には、導体間の最短経路及び最短距離を自動的に算出する必要がある。特に大きな電力を必要とする電子機器でも小型化が避けられない場合が増加しているため、自動的に計算できると設計時間を短縮することができる。
【０００３】
なお、例えば図１（ａ）及び（ｃ）に示すように、２つの導体１００１及び１００２の間に１ｍｍ未満のくぼみがある場合には、当該くぼみを無視した状態における最短経路を特定し、当該最短経路の経路長を沿面距離と呼ぶ。また、図１（ｂ）に示すように、導体１００１及び１００２の間に１ｍｍ以上のくぼみの場合には、くぼみ内部をも沿うようにして最短経路を特定し、当該最短経路の経路長も沿面距離である。一方、図１（ｄ）に示すように、導体１００１及び１００２間に突起がある場合にも、当該突起をも沿うようにして最短経路を特定する。
【０００４】
従来から、ＣＡＤモデルなどの３次元モデルの三角形メッシュにおける経路出発点と経路到達点との間の最短経路算出技術がいくつか存在している。その中でも重要と思われる１つの手法に、重み付きグラフ探索法がある。例えば図２に示すように物体表面をグラフで近似してそのグラフの中の２つの頂点間の最短経路を探索する手法である。図２では、頂点と頂点は重み付きの辺で接続されており、頂点間は辺が定義されている場合にのみ移動可能であって、その際のコストが重みである。具体的な最短経路探索アルゴリズムには、例えばダイクストラ（Dijkstra）法などを用いる。
【０００５】
ダイクストラ法は、グラフＧ（Ｎ，Ａ）の１つのノードｓから他のノードｔに至るアークの重みの和が最小となる経路を探索する手法の一つである。なお、Ｎはノード（又は節と呼ぶ）の集合を表し、Ｅはノードを結ぶアーク（又は稜線と呼ぶ）の集合を表す。以下、ダイクストラ法のアルゴリズムの概略を示す。
前提：グラフＧは連結しており、アークに付された重みｗは正である。ノードａiには開始ノードｓからの距離ｄ(vi)と復帰ノード（直前のノード）ｒ(vi)を随伴させる。
アルゴリズム：
１．初期処理 ノードの集合Ｎを次の２つの集合に分ける。
計算完了ノード集合 Ｃ＝｛ｓ｝
計算未了ノード集合 Ｕ＝Ｖ−｛ｓ｝
距離を次のように設定する。
ｄ(s)＝０
ｄ(v)＝∞ 但し、ｖ∈Ｕ
２．演算 最大の距離ｄを有するノードｘ∈Ｃに隣接する全てのｙ∈Ｕに対して
if ｄ(x)＋ｗxy＜ｄ(y)
then ｄ(y)＝ｄ(x)＋ｗxy
最小の距離ｄを有するノードｚ∈Ｕを一つ探索し、Ｕ＝Ｕ−｛ｚ｝，
Ｃ＝Ｃ∪｛ｚ｝とする。
復帰ノードｒ(z)＝ｘを保存する。
この処理をｚ＝ｔになるまで繰り返す。
最短経路については、保存しておいた復帰ノード情報を辿ることによって特定する。
【０００６】
ダイクストラ法は、最初に、隣接するノード間にアークを全て静的に用意しておく必要がある。すなわち、図２に示したようなグラフが完成してからでなければ探索を行うことはない。しかしながら、ノード間には必ずアーク及び重みが定義されるため、ノードが増加するとデータ量が膨大になるという問題がある。
【０００７】
そこで、このような問題点に着目した技術が存在している。すなわち、この技術では、グラフを探索しながら、探索に必要な部分だけ動的にグラフを作成していく。まず（１）問題領域を分割し、（２）開始ノードを含む領域だけグラフを作成し、（３）この領域から最短経路の探索を始め、領域の境界のノードに探索が進んだら隣接する領域のグラフを作る。また、同時に現探索領域と作成した隣接領域のグラフをマージする。そして（３）の処理を探索が終了ノードに到達するまで繰り返す。このような処理では、領域の分割やグラフのマージなど処理が複雑化する問題がある。
【０００８】
なお、図２のようなグラフは、３Ｄモデルの表面に適合した形で形成されるが、必ずしもノードやアークの配置が最適でない場合もある。従って、単純に最短経路として特定されたノード間に設定されているアークをたどるだけでは、真に最短距離で開始ノードと終了ノードとをつなぐことができない場合もある。このような問題に対処するような技術も存在している。その中には、開始ノードと終了ノードとの最短経路を求めた後に、開始ノードと終了ノードとを含む面を平面展開して、開始ノードから終了ノードへの直線距離を算出すると共に、その間のノードについても変更するという技術がある。例えば、図３（ａ）に示す六面体の表面に設定されたグラフを例えばダイクストラ法で探索して開始ノードから終了ノードへの初期最短経路を算出する。図３（ａ）では、開始ノード、Ｉ１、Ｖ、Ｉ２、終了ノードという順番の初期最短経路が特定される。その後、図３（ｂ）に示すように、初期最短経路に含まれる、六面体の頂点Ｖの周りで最初の平面展開を実施する。具体的には、三角形Ｔ５、Ｔ２、Ｔ３及びＴ４を１つの平面に展開する。そして、三角形Ｔ２に含まれる最も開始ノードに近いノードＩ１から終了ノードを直線で結ぶことによって、頂点Ｖ経由よりも短い経路を特定する。ここでは、開始ノード、Ｉ１、Ｉ３、Ｉ４、終了ノードという順番の経路が特定される。ノードＩ３及びＩ４が新たに特定されている。その後、開始ノードを含む三角形Ｔ１、Ｔ２、Ｔ３及びＴ４を１つの平面に展開する。そして、開始ノードと終了ノードとを直線で結ぶことによって、経路は新たに特定されたノードＩ１’、Ｉ３’、Ｉ４’を含むようになる。しかしながら、この技術では２段階で経路を最適化しており、処理が複雑になっている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００６−１７２３１８号公報
【特許文献２】特開２００８−１３４９４８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
以上述べたように従来技術には様々な問題があるが、特に問題なのは、経路出発線と経路到達線との間の最短経路を特定するような技術は存在していないということである。ダイクストラ法等の手法は、２ノード間の最短経路を特定するにはよいが、このように２曲線間の最短経路を特定するのには適していない。
【００１１】
従って、本技術の目的は、出発線（点に縮退している場合を含む）と到達線（点に縮退している場合を含む）との間の最短経路を探索するための新規な技術を提供することである。
【課題を解決するための手段】
【００１２】
３次元モデル上における最短経路をコンピュータにより探索する最短経路探索方法は、３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する三角形及び辺のデータに当該三角形の頂点及び補間点のデータを関連付けて探索管理データ格納部に格納するステップと、３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付けるステップと、出発点又は出発線から到達点又は到達線に至るまで、補間点及び頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である補間点又は頂点について出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、最短距離探索対象点である補間点又は頂点に関連付けて距離を探索管理データ格納部に格納する探索ステップとを含む。
【図面の簡単な説明】
【００１３】
【図１】図１（ａ）乃至（ｄ）は、沿面距離を説明するための図である。
【図２】図２は、重み付きグラフの一例を示す図である。
【図３】図３（ａ）乃至（ｃ）は、従来技術を説明するための図である。
【図４】図４は、３次元モデル上で経路出発線から経路到達線までの経路を示した例を示す図である。
【図５】図５は、最短経路探索装置の機能ブロック図である。
【図６】図６は、メッシュの位相構造を説明するための図である。
【図７】図７は、三角形メッシュの一例を示す図である。
【図８】図８は、点テーブルの一例を示す図である。
【図９】図９は、三角形テーブルの一例を示す図である。
【図１０】図１０は、位相テーブルの一例を示す図である。
【図１１】図１１は、余弦テーブルの一例を示す図である。
【図１２】図１２は、辺長テーブルの一例を示す図である。
【図１３】図１３は、最短経路探索処理の処理フローを示す図である。
【図１４】図１４は、補間点について説明するための図である。
【図１５】図１５は、補間点データテーブルの一例を示す図である。
【図１６】図１６は、補間点管理テーブルの一例を示す図である。
【図１７】図１７は、復帰点を説明するための図である。
【図１８】図１８は、補間点間のアークデータを生成しない理由を説明するための図である。
【図１９】図１９は、前線候補点集合テーブルの一例を示す図である。
【図２０】図２０は、ヒープ構造を採用する場合における前線候補点集合テーブルの一例を示す図である。
【図２１】図２１は、最短経路探索処理の処理フローを示す図である。
【図２２】図２２は、探索すべき三角形要素を説明するための図である。
【図２３】図２３は、探索すべき三角形要素を説明するための図である。
【図２４】図２４は、探索すべき三角形要素を説明するための図である。
【図２５】図２５は、探索すべき三角形要素を説明するための図である。
【図２６】図２６は、探索すべき三角形要素を説明するための図である。
【図２７】図２７は、探索すべき三角形要素を説明するための図である。
【図２８】図２８は、三角形内距離の算出について説明するための図である。
【図２９】図２９は、最短経路探索処理の具体例を説明するための図である。
【図３０】図３０は、最短経路探索処理の具体例を説明するための図である。
【図３１】図３１は、最短経路探索処理の具体例を説明するための図である。
【図３２】図３２は、最短経路探索処理の具体例を説明するための図である。
【図３３】図３３は、最短経路探索処理の具体例を説明するための図である。
【図３４】図３４は、最短経路探索処理の具体例を説明するための図である。
【図３５】図３５は、最短経路探索処理の具体例を説明するための図である。
【図３６】図３６は、最短経路探索処理の具体例を説明するための図である。
【図３７】図３７は、最短経路探索処理の具体例を説明するための図である。
【図３８】図３８は、最短経路探索処理の具体例を説明するための図である。
【図３９】図３９は、最短経路探索処理の具体例を説明するための図である。
【図４０】図４０は、最短経路探索処理の具体例を説明するための図である。
【図４１】図４１は、最短経路探索の際の問題を説明するための図である。
【図４２】図４２は、平面展開区間について説明するための図である。
【図４３】図４３は、平面展開区間端点についての条件を説明するための図である。
【図４４】図４４は、平面展開区間端点についての条件を説明するための図である。
【図４５】図４５は、平面展開経路距離修正処理の処理フローを示す図である。
【図４６】図４６は、補間点管理テーブルの他の例を示す図である。
【図４７】図４７は、平面展開区間生成処理の処理フローを示す図である。
【図４８】図４８は、平面展開区間生成処理を説明するための図である。
【図４９】図４９は、平面展開区間生成処理の処理フローを示す図である。
【図５０】図５０は、補間点位置補正処理の処理フローを示す図である。
【図５１】図５１は、位置補正処理の処理フローを示す図である。
【図５２】図５２は、位置補正処理を説明するための図である。
【図５３】図５３は、位置補正処理の処理フローを示す図である。
【図５４】図５４は、位置補正処理を説明するための図である。
【図５５】図５５は、位相情報について説明するための図である。
【図５６】図５６は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１４】
本実施の形態では、図４に示すように、ある３次元モデルＭ上の経路出発線ｓから経路到達線ｔまでの最短経路Ｌを特定し、当該最短経路Ｌの長さである最短距離を算出するものとする。この際、３次元モデル上には周知の方法で三角形メッシュを形成して、さらに三角形メッシュにおける個々の三角形の辺には、精度向上のため補間点を設ける。但し、補間点間を結ぶアークを予め形成して保持及び利用することはない。三角形メッシュの頂点や補間点を探索して最短経路を特定する場合に、補間点や三角形メッシュの頂点間の距離が必要となるが、必要になった際に必要なものだけ計算する。このように補間点間を結ぶアークを予め用意しないことによって、処理時間を短縮すると共に、データ量の増加を最小限に抑えることができる。
【００１５】
さらにオプションとして、初期的に生成する補間点の位置をベースに距離を算出すると、必ずしも始点と終点の距離は最短とはならない。従って、可能な範囲で三角形メッシュの三角形を平面展開して直線で結ぶことによって、より精度の高い最短距離を算出する。また、直線で結ぶ場合には補間点の位置も変更する。
【００１６】
以下、このような処理を実現するための具体的な構成について説明する。
【００１７】
本実施の形態に係る最短経路探索装置の機能ブロック図を図５に示す。最短経路探索装置は、例えばユーザによって指示された３次元モデルについて周知の技術によって形成された三角形メッシュのデータを格納する三角形メッシュデータ格納部１１と、例えば三角形メッシュデータ格納部１１に格納されているデータを用いてユーザから経路探索の経路出発線及び経路到達線の入力を行うためのデータ入力部１４と、データ入力部１４から入力された経路出発線及び経路到達線のデータを格納する開始終了データ格納部１５と、三角形メッシュデータ格納部１１に格納されているデータを用いて三角形の辺に補間点を生成する処理などを実施する補間点データ生成部１２と、補間点データ生成部１２によって生成されたデータを格納する補間点データ格納部１３と、補間点データ格納部１３と三角形メッシュデータ格納部１１と開始終了データ格納部１５とに格納されているデータを用いて最短経路を探索するための処理を実施する探索処理部１６と、探索処理部１６の処理に用いるデータを一時的に保持する処理データ格納部１７と、探索処理部１６の処理結果である最短距離のデータ及び最短経路のデータを格納する出力データ格納部１８と、例えば三角形メッシュデータ格納部１１と出力データ格納部１８と補間点データ格納部１３とを用いてユーザに対して最短距離及び最短経路を提示する出力部１９とを有する。
【００１８】
探索処理部１６は、少なくとも一部の経路区間について距離を補正する処理を実施する距離補正部１６１と、少なくとも一部の経路区間について距離を補正する際に補間点位置をも補正する処理を実施する補間点位置補正部１６２とを有する。
【００１９】
次に、三角形メッシュデータ格納部１１に格納されるデータについて説明する。最初に、メッシュについて説明する。複雑な対象物の形状を厳密に表現するのは実際的でないので、一般的には物体を多面体メッシュで表現する。特に三角形メッシュは、生成及び取り扱いが容易なので多用される。後に述べる、平面展開を用いた処理を実施する上でも有利である。
【００２０】
三角形は３つの頂点によって定まる。メッシュは、三角形の集合であり、境界でない辺は２つの三角形によって共有される。頂点は、１又は複数の三角形によって共有される。
【００２１】
図６に示すように、三角形Ｔiに識別子を与え、三角形Ｔi毎に、頂点及び辺に対してｖij，ｊ∈［１，３］，ｅij，ｊ∈［１，３］を与えることによってメッシュの位相構造（要素の接続関係）を表現する。図６の白抜き矢印のように三角形に向きを与えると、向きはメッシュ全体で同調するので、一意に矛盾無く隣接する頂点、辺、三角形要素を定めることができるようになる。また、図６の黒矢印で示すように、三角形は辺を介して隣接する三角形が一意に定まる。また、頂点についても同一の識別子を有する頂点を用いれば、隣接する三角形を特定することができる。なお、辺については頂点が定まれば特定できるので、辺自身を管理しない場合もある。
【００２２】
三角形メッシュについては、様々な周知技術にて生成することができるが、例えば有限要素法（ＦＥＭ：Finite Element Method）用に生成した三角形メッシュが好ましい。このように生成された三角形メッシュはアスペクト比が良好であるので、発生する誤差が少くなる。
【００２３】
本実施の形態では、このような前提の下、三角形メッシュ・データは、点テーブル、三角形テーブル及び位相テーブルを含む。ここでは例えば図７に示すような三角形メッシュが存在する場合を説明する。図７では、頂点が６個で、４つの三角形が特定されている。このような三角形メッシュについての点テーブルの一例を図８に示す。図８の例では、頂点の識別子毎に、Ｘ座標値、Ｙ座標値及びＺ座標値が登録される。
【００２４】
また、三角形テーブルの一例を図９に示す。図９の例では、三角形の識別子毎に、該当する３頂点の識別子が登録される。さらに、位相テーブルの一例を図１０に示す。図１０の例では、三角形の識別子毎に、各辺に隣接する他の三角形の識別子が登録される。なお、辺１、辺２、辺３の順番は図６の白抜き矢印で示したように一定の順番となっている。
【００２５】
以上のようなテーブルに加え、以下のようなテーブルを保持することによって距離の計算を高速化することができるようになる。但し必須ではない。高速化のための第１のテーブルは、図１１に示すような余弦テーブルである。図１１の例では、各三角形の各頂点について、その頂点における角度に応じた余弦値が登録されるようになっている。このようなデータを予め用意しておけば、１つの三角形の２辺の頂点又は補間点との距離計算が高速化される。
【００２６】
また、高速化のための第２のテーブルは、図１２に示すような辺長テーブルである。図１２の例では、各三角形について各辺の辺長が登録されるようになっている。このようなデータを保持すれば、三角形内部における距離計算が高速化される場合がある。
【００２７】
なお、三角形メッシュデータ格納部１１には、三角形メッシュ毎に絶縁度に相当する屈折率が登録されている場合もある。物体上の最短距離（すなわち沿面距離）を算出する場合には、経路上に存在する三角形毎に素材が異なり、絶縁度が異なる場合がある。そのような場合には、絶縁度に応じた距離を算出する必要があり、絶縁度に相当する屈折率を登録しておけば、以下で述べる距離計算において、該当部分については屈折率を乗じて距離を換算する。
【００２８】
なお、本実施の形態では、既に三角形メッシュデータ格納部１１に、上で述べたような三角形メッシュのデータを予め用意することを前提にして説明するが、最短経路探索装置が、３次元モデルのデータ（例えば、ベジエ曲面、B-Spline曲面、NURBS曲面などの自由曲面で記述されている三次元モデルであったり、複数部品の組み合わせで構成される３次元モデルのデータ）から、上で述べたような三角形メッシュのデータを生成するような機能を持つようにしても良い。
【００２９】
次に、図１３乃至図５４を用いて、最短経路探索装置の処理内容について説明する。まず、補間点データ生成部１２は、三角形メッシュデータ格納部１１に格納されている三角形メッシュ・データを用いて補間点データ生成処理を実施する（図１３：ステップＳ１）。この処理は、三角形メッシュに含まれる各三角形の辺に補間点（Steiner点とも呼ぶ）を追加する処理である。三角形メッシュがある程度の正規性を有する場合、すなわち三角形の最小角度が閾値以上である場合には、１辺の補間点数を一定にするように、補間点を均等配置することが実際的である。但し、辺の長さに応じて補間点数を決定して、均等間隔に配置するようにしても良い。
【００３０】
例えば図１４に示すように三角形Ｔ1及びＴ2が存在する場合、それぞれの辺には補間点１乃至３が追加される。補間点１乃至３の位置データについては、図１５に示すように、該当する三角形、辺及び補間点のＩＤに対応してＸ座標値、Ｙ座標値及びＺ座標値を登録するようにしてもよい。但し、補間点は、例えば辺に３つの補間点を設ける場合には当該辺の１／４、１／２、３／４の位置に存在するということさえ確定していれば、三角形内距離は算出できるので座標位置を予め算出しておかなくても問題はない。辺毎に補間点の数が変化する場合等には、図１５のデータを用意する方が良い場合もある。
【００３１】
なお、図６の白抜き矢印で示したように、一定の方向にＩＤを付与するようにする。すなわち、図１４において矢印で示すように反時計回りで辺に対して番号（１乃至３）を付与すると共に、辺の中の補間点についても反時計回りで番号（１乃至３）を付与する。但し、以下の処理で頂点（黒丸）についても、補間点と統一的に処理する方が好ましいので、頂点については「０」という補間点番号が付与されている。
【００３２】
また、図１４からも分かるように、三角形Ｔ1の辺１と、三角形Ｔ2の辺３とは同じ辺を共有しており、補間点も同じである。従って、図１５のような位置データにおいても、三角形、辺及び補間点のＩＤについては異なるが実際には同一の補間点を表している場合には、同じ位置データが登録されることになる。
【００３３】
そして、補間点データとしては、以下で述べる探索処理において当該探索処理の管理に用いられる補間点管理テーブルを生成する。
【００３４】
補間点管理テーブルについては例えば図１６に示すようなテーブルである。図１６の例では、三角形、辺及び補間点のＩＤに対応して、当該補間点に至る直前の補間点（頂点の場合あり）である復帰点を含む三角形である復帰点三角形のＩＤ、復帰点を含む辺である復帰点辺のＩＤ、復帰点である補間点のＩＤ、当該補間点までの経路距離及び補間点属性を登録するようになっている。
【００３５】
復帰点は、例えば図１７に示すように、黒丸の補間点から、同じ三角形の辺上の補間点（頂点を含む）を探索した場合には、白丸の探索先補間点にとって黒丸の補間点が復帰点となる。但し、以下で述べる処理でも分かるように、その探索先補間点にとって経路距離が最短でなければ復帰点及び経路距離は登録されないので、その探索先補間点について復帰点はその時点における最短経路についての１つ手前の補間点である。これによって経路を逆方向に辿ることができるようになる。
【００３６】
補間点属性は、初期状態からスタートして、前線候補、前線通過完了と順に遷移する。探索前は初期状態であり、最初に、以下で述べる経路出発線上の補間点が、前線候補という状態に変化する。前線候補から次の補間点へ探索を実施する。前線候補として探索が完了すると前線通過完了に遷移する。また、補間点属性は、例えば経路距離や復帰点情報の符号（正又は負）を用いて表現する場合もある。
【００３７】
本ステップでは、復帰点三角形ＩＤ、復帰点辺ＩＤ、復帰補間点ＩＤについては「０」を初期的に登録し、経路距離については無限大に相当するような値を設定する。
【００３８】
また、図１４に示すように、三角形Ｔ1と三角形Ｔ2では、辺を共有しているので、当然補間点も共有することになる。図１６のように全ての三角形について３つの辺についてデータを保持すると、同一の補間点について２つ以上のレコードがテーブル内に存在する場合がある。このような場合には、両方のレコードを同期して更新する必要がある。なお、一方を常に代表として取り扱い、残余のレコードについては更新しないようにしても良い。
【００３９】
また、経路距離については、以下で説明する前線候補点集合テーブルに登録することによって、補間点管理テーブルにおいて保持しないようにする場合もある。
【００４０】
なお、本補間点管理テーブルでは、経路を逆方向に辿るための復帰点情報は登録されているが、補間点同士を繋ぐアーク及びその距離自体は規定しない。これによって、アーク及びその距離自体を計算する処理時間を節約できると共に、保持すべきデータ量を大幅に削減できる。特に、図１８に示すように、矢印方向に探索が行われ、現在補間点Ａに到達しているとすると、出発線から補間点Ａを経由して補間点Ｂに到達した場合の距離は、補間点Ａまでの距離ｄと補間点Ａ及びＢの距離ＡＢとの和であり、出発線から補間点Ａを経由して補間点Ｃに到達した場合の距離は、補間点Ａまでの距離ｄと補間点Ａ及びＣの距離ＡＣとの和である。補間点Ａから補間点Ｂを経由して補間点Ｃに至ることも考えられるが、補間点Ａから補間点Ｃに直接ゆく方が必ず距離は短くなるので、補間点Ａ、Ｂ及びＣという経路は採用し得ない。従って、以下で述べる探索処理ではこのような三角形内の探索は行われず、予め補間点ＢとＣの間のアークを規定して距離を計算する処理自体無駄である。本実施の形態では、このような無駄な処理を行わずに高速に最短経路探索を行うことができる。
【００４１】
図１３の処理の説明に戻って、データ入力部１４は、ユーザに対して経路出発線の指定を促し、ユーザから経路出発線の指定を受け付け、経路出発線を特定するためのデータを、開始終了データ格納部１５に格納する（ステップＳ３）。例えば、メッシュデータ格納部１１からメッシュ・データを読み出して、３次元モデルの表示データを生成して表示し、ユーザに経路出発線を指定させるようにしてもよい。経路出発線は、三角形メッシュの境界である。なお、ユーザが点を指定して、当該指定された点に最も近いメッシュの境界を探索して特定し、閉じた辺の列として取得してもよい。
【００４２】
導体の境界は、図４の経路出発線ｓや経路到達線ｔのように、三角形メッシュでは閉じた辺の列で表現される。もし非常に細い導体を理想化して表現する必要があるならば、閉じた辺の列を空の三角形要素の境界として表現することによって、閉じた辺の列間の最短経路（すなわち沿面経路）を計算することができる。また更に閉じた辺の列は１点に縮退させることもできる。この場合は、出発点という１点からの経路探索の問題に縮退する。
【００４３】
データとしては、三角形ＩＤと辺ＩＤのセットで特定される。テーブル形式で保持しても良いし、ハッシュ構造を利用しても良い。
【００４４】
さらに、データ入力部１４は、ユーザに対して経路到達線の指定を促し、ユーザから経路到達線の指定を受け付け、経路到達線を特定するためのデータを、開始終了データ格納部１５に格納する（ステップＳ５）。例えば、メッシュデータ格納部１１からメッシュ・データを読み出して、３次元モデルの表示データを生成して表示し、ユーザに経路到達線を指定させるようにしてもよい。経路到達線は、三角形メッシュの境界である。なお、ユーザが点を指定して、当該指定された点に最も近いメッシュの境界を探索して特定し、閉じた辺の列として取得してもよい。
【００４５】
データとしては、三角形ＩＤと辺ＩＤのセットで特定される。テーブル形式で保持しても良いし、ハッシュ構造を利用しても良い。
【００４６】
なお、経路出発線及び経路到達線としては、一般化して、三角形メッシュの境界でないものを選択するようにしても良い。
【００４７】
次に、探索処理部１６は、前線候補点集合テーブルに経路出発線の補間点を設定する（ステップＳ７）。前線候補点とは、図１７における黒丸の補間点のように、最短経路を探索するための起点（経路出発線の補間点の場合を除き中間的な起点）の候補である補間点である。前線候補点集合テーブルは、例えば処理データ格納部１７に格納する。
【００４８】
本実施の形態において、出発線からの経路距離は、経路距離の拡大を波とみなしたときの波頭であるHuygens（ホイヘンス）前線上の補間点からの２次波で決定される。すなわち、Huygens前線が補間点を通過したとき、２次波は、当該補間点が帰属し且つ波の進行方向に存在する三角形要素の補間点に伝播する。そして、２次波が伝播した補間点の中で、最小の経路距離を有する補間点を次のHuygens前線の通過点とする。前線候補点は、このようなHuygens前線の通過点の候補となる補間点である。
【００４９】
前線候補点集合テーブルは、例えば図１９に示すようなテーブルである。すなわち、前線候補点毎に、三角形ＩＤ、辺ＩＤ及び補間点ＩＤを登録するものである。前線候補点集合テーブルに登録した場合には、補間点管理テーブル（図１６）についても更新しなければならない。すなわち、該当する補間点についての候補点属性を「前線候補」に変更する。また、経路距離についても該当する経路距離に変更する。但し、初回の場合、経路出発線の補間点は、当然経路距離「０」であるから、「０」を経路距離に登録する。
【００５０】
以下において、前線候補点集合テーブルに補間点を追加する場合には、例えばテーブルの最後のレコードに追加する。また、前線候補点集合テーブルから前線候補点を削除する場合には、該当レコードを削除した後、最後のレコードを移動させる。
【００５１】
なお、以下の処理において、前線候補点集合から、最小の経路距離を有する前線候補点を抽出する処理を頻繁に実施することになる。前線候補点の数が小さければ補間点管理テーブルを順次探索によって最小の経路距離の前線候補点を特定する処理で問題はない。しかしながら、前線候補点の数が大きくなると、順次探索は時間がかかるという問題がある。この場合、前線候補点集合テーブルの該当アドレスを管理するヒープ構造を使用することが望ましい。但し、前線候補点集合テーブル及び経路距離は動的に変化するので、ヒープ構造と前線候補点集合テーブルの間で同期をとる必要がある。
【００５２】
ヒープ構造を採用する場合には、前線候補点集合テーブルについては、図２０に示すようなデータ・フォーマットを採用する。図２０の例では、図１９に示したテーブルに加えてヒープ・アドレスが登録されるようになっている。
【００５３】
ヒープ構造は、連続した番号をもつ節点で構成される２進木であり、次の三つの規則を有するデータ構造である。
（１）アドレス１をルートとする。
（２）アドレスｋの左の子はアドレス２ｋに、右の子はアドレス２ｋ＋１に格納する。
（３）親の節点は子の節点より常に小さなデータを有する。
ヒープ構造からルート（すなわち根）を取り出すことによって、最小の経路距離をもつ補間点が高速に取り出すことができる。すなわち、データ数をＮとすると、ルートのデータを削除した場合、最後のアドレスＮに存在するデータをルートに移動する。規則（３）を満足するために、親と子の間のデータ交換を行うが、親子のアドレス探索は２の乗除算で可能であり、データ交換の回数はlog2Ｎに過ぎない．これによって高速な探索が可能になる。詳細は、浅野哲夫著「データ構造」（近代科学社 p.30）などを参照されたい。
【００５４】
図２０に示したように、前線候補点集合に属する補間点毎にヒープ・アドレスを取得できる構造にしておく。この構造を採用することによって経路距離が更新された場合も、ヒープ・アドレスを直接参照することによって、高速にヒープの経路距離を親と子の間で比較して入れ換えを行い、ヒープの順序関係を常に正常に保つことができる。また、前線候補点集合テーブルの該当レコードのアドレスが変わっても、ヒープ・アドレスが管理する前線候補点集合テーブルの該当レコードのアドレスを更新することによって同期を取ることができる。これによって、最小の経路距離を有し且つ前線候補点集合に含まれる補間点が取り出されることが保証される。
【００５５】
さらに、探索処理部１６は、前線候補点集合の中で、経路距離が最短である補間点を前線上存在補間点として探索する（ステップＳ９）。この処理は、Huygens前線上に存在する（すなわち前線の通過点たる）補間点を特定するための処理である。前線候補点集合テーブルに登録されている補間点で、補間点管理テーブル（図１６）を検索して経路距離を取得し、取得された経路距離の中で最短の補間点を特定する。ヒープ構造を用いる場合には上で述べたとおりの処理を実施する。
【００５６】
なお、最初にこのステップを実施する場合には、経路出発線上の補間点が経路距離０で前線候補点集合に登録されるので、そのうちのいずれか１つ補間点が選択される。
【００５７】
また、本ステップＳ９の直後に、オプションとして後に述べる平面展開による距離の補正を実施する場合がある。
【００５８】
そして、探索処理部１６は、前線上存在補間点が、開始終了データ格納部１５に格納されている経路到達線上にあるか、すなわち経路到達線に係る三角形の辺に含まれる補間点（頂点を含む）であるかを判断する（ステップＳ１１）。前線上存在補間点が、経路到達線上に存在していない場合には、端子Ａを介して図２１の処理に移行する。
【００５９】
一方、前線上存在補間点が、経路到達線上に存在していると判断されると、探索処理部１６は、前線上存在補間点についての経路距離を最短距離として特定すると共に、前線上存在補間点についての復帰点情報（復帰三角形、復帰辺及び復帰補間点）を補間点管理テーブルから読み出し、さらに復帰点についてのさらに前の復帰点を読み出しといったように順次遡ることによって最短経路上の補間点を特定し、最短距離（すなわち沿面距離）及び最短経路上の補間点の情報（ＩＤ及び位置データ）を出力データ格納部１８に格納する（ステップＳ１３）。なお、本ステップでは、以下で述べる、平面展開による最短経路の修正処理を実施する場合がある。
【００６０】
そして、出力部１９は、出力データ格納部１８に格納された最短距離及び最短経路上の補間点のデータを、表示装置などの出力装置に出力する（ステップＳ１５）。例えば、３次元モデルの三角形メッシュ・データを三角形メッシュデータ格納部１１から読み出して、三角形メッシュ上で、最短経路上の補間点を結んで最短経路を明示するような図（例えば図４）を生成して、表示装置に表示するようにしても良い。
【００６１】
次に、端子Ａの後の処理について図２１乃至図４０を用いて説明する。まず、探索処理部１６は、前線上存在補間点が帰属する三角形の補間点のうち未処理の補間点を探索する（図２１：ステップＳ１７）。本ステップにおいては、前線上存在補間点が保有する復帰点情報に基づいて、経路距離増大方向にある三角形のみを探索の対象とするのが望ましい。全ての三角形を探索の対象にしても処理は可能であるが、対象の限定によって、不要な探索が実行されなくなり、高速な処理が可能になる。
【００６２】
具体的には、図２２に示すように、三角形の辺上に前線上存在補間点ｈが存在する場合には、復帰点ｒ及び前線上存在補間点ｈが属する三角形と、前線上存在補間点ｈが存在する辺を共有する三角形Ｔsの実線矢印の辺に属する補間点を探索対象とする。一方、図２３乃至図２７に示すように、前線上存在補間点ｈが三角形の頂点である場合には、様々なパターンが存在する。図２３に示すように、例えば５つの三角形によって共有される頂点が前線上存在補間点ｈである場合には、復帰点ｒが属する三角形を除く共有三角形Ｔs1乃至Ｔs4の各辺（実線矢印の示す辺。但し復帰点ｒを含む三角形と共有される辺を除く）に属する補間点を探索対象とする。また、図２４に示すように、復帰点ｒと前線上存在補間点ｈとが三角形メッシュの頂点であり、経路が三角形要素の辺に沿って設定されており、前線上存在補間点ｈが経路上の辺を共有する２つの三角形及びそれ以外の例えば３つの三角形Ｔs1乃至Ｔs3に共有される場合には、経路上の辺を共有する三角形以外の三角形Ｔs1乃至Ｔs3の各辺（実線矢印の示す辺。経路上の辺を共有する三角形に属する辺を除く。）に属する補間点が探索対象となる。
【００６３】
さらに、図２５に示すように、復帰点ｒ及び前線上存在補間点ｈが属する三角形及び三角形Ｔs1乃至Ｔs3が前線上存在補間点ｈを共有しているが、図２３とは異なり前線上存在補間点ｈの周り３６０°に三角形が存在するわけではない場合でも、図２３の考え方と同様に、復帰点ｒが属する三角形を除く共有三角形Ｔs1乃至Ｔs3の各辺（実線矢印の示す辺。但し復帰点ｒを含む三角形と共有される辺を除く）に属する補間点を探索対象とする。また、図２６に示すように、復帰点ｒ及び前線上存在補間点ｈとが三角形メッシュの頂点であり、経路が三角形要素の辺に沿って設定されており、経路上の辺を共有する三角形及び例えば三角形Ｔs1及びＴs2が前線上存在補間点ｈを共有しているが、図２４とは異なり前線上存在補間点ｈの周り３６０°に三角形が存在するわけではない場合でも、図２４の考え方と同様に、三角形Ｔs1及びＴs2の各辺（実線矢印の示す辺。但し経路上の辺を共有する三角形に属する辺を除く。）に属する補間点が探索対象となる。
【００６４】
図２７のケースは、三角形メッシュが形成されていない領域の境界を沿って復帰点ｒから前線上存在補間点ｈへ経路が延びており、頂点である前線上存在補間点ｈを共有する三角形が複数存在している場合を示しており、このような場合には、経路がのっている辺が属する三角形以外の三角形で前線上存在補間点ｈを共有する三角形Ｔs1乃至Ｔs3の各辺（実線矢印の示す辺。但し復帰点ｒを含む三角形と共有される辺を除く）に属する補間点を探索対象とする。
【００６５】
なお、上で述べたような探索対象を特定するために、本実施の形態ではメッシュ構造の位相情報を用いる。具体的には、図１０に示したような位相テーブルを用いれば、辺をはさんで隣接する三角形要素を特定することができる。さらに図９の三角形テーブルを用いれば、三角形の頂点も特定できる。頂点と辺については、例えば反時計回りで番号を付与するなどの規則を採用すれば対応付けが可能である。三角形及び辺が特定できれば補間点管理テーブルを用いて補間点も特定できる。このように、位相情報を用いることによって探索対象を把握できるので、ダイクストラ法などで用いられるグラフ構造において連結先を示すポインタを保有しないで済む。従ってその分データ量を減らすことができる。
【００６６】
図２３乃至図２７のようなポリシーで探索先三角形を特定し、その中で未処理の補間点を探索するが、例えば全ての該当補間点を処理してしまって、未処理の補間点が存在しない場合（ステップＳ１９：Ｎｏルート）、探索処理部１６は、前線上存在補間点を前線候補点集合（すなわち前線候補点集合テーブル）から除外し、補間点管理テーブル（図１６）において前線上存在補間点ｈについての補間点属性を「前線通過完了」に変更する（ステップＳ２９）。このようにして、Huygens前線が通過したことになるので、以後の処理の対象から外すことができる。処理は端子Ｂを介して図１３のステップＳ９に戻る。
【００６７】
一方、探索先三角形を特定してその中で未処理の補間点が存在する場合には（ステップＳ１９：Ｙｅｓルート）、探索処理部１６は、補間点管理テーブル（図１６）において、特定された補間点が前線通過完了という補間点属性の補間点であるか判断する（ステップＳ２１）。特定された補間点が、前線通過完了という補間点属性の補間点である場合には、ステップＳ１７に戻る。
【００６８】
一方、特定された補間点が、前線通過完了という補間点属性の補間点ではない場合には、探索処理部１６は、特定された補間点が、前線候補点集合に属するか、すなわち前線候補点集合テーブルに登録されているか判断する（ステップＳ２３）。登録されていれば、再度登録する必要はないのでステップＳ２７に移行する。一方、登録されていなければ、特定された補間点を前線候補点集合に追加、すなわち前線候補点集合テーブルに登録する（ステップＳ２５）。補間点管理テーブルの補間点属性も前線候補に変更する。次の探索処理の起点候補とするためである。
【００６９】
ステップＳ２５の後又はステップＳ２３で既に前線候補点集合テーブルに登録されていると判断された場合には、探索処理部１６は、特定された補間点までの経路距離を算出する。図２８に示すように、まず経路距離ｄ*を有する前線上存在補間点ｃ*から探索した補間点（前線候補点）ｃまでの三角形内距離Δｄを計算する。三角形内距離Δｄは、前線上存在補間点ｃ*と補間点ｃの座標値から、その間の距離を求める。さらに、前線上存在補間点ｃ*の経路距離ｄ*と三角形内距離Δｄとを加算すれば、補間点（前線候補点）の経路距離が得られる。
【００７０】
なお、上で述べたように余弦テーブルや辺長テーブルが用意されている場合には、次のように余弦定理を用いると三角形内距離Δｄを高速に計算できる。すなわち、以下の式で算出できる。
【数１】
【００７１】
このような式で算出する方が、補間点が属する辺の両端の頂点の座標値を内分し、２つの補間点の座標成分の２乗和の平方根を計算するより計算量が少ない。
【００７２】
なお、補間点の座標値を図１５のように予め計算しておく場合には、その値を用いて距離を算出するようにしても良い。
【００７３】
さらに、三角形要素に屈折率が与えられている場合は、三角形内距離Δｄに対して該当する三角形要素の屈折率から定まる係数を乗じて、三角形内距離Δｄを修正する。
【００７４】
その後、今回算出された経路距離が（ｄ*＋Δｄ）が、特定された補間点（前線候補点）の現在の経路距離より短いか判断し、短い場合には、補間点管理テーブルにおいて、特定された補間点の経路距離を今回算出された経路距離に置き換えると共に、復帰点情報を今回の前線上存在補間点についての三角形ＩＤ、辺ＩＤ及び補間点ＩＤに置き換える（ステップＳ２７）。このようにすれば、特定された補間点には、処理時点における最短経路の最短距離及び経路上１つ前の補間点の情報が登録されるようになる。
【００７５】
なお、前線候補点の経路距離をヒープ構造で管理する場合は、ノード間の交換を行い、ヒープ構造に矛盾が生じないようにする。また、補間点管理テーブルにおいて実体が同一の補間点が異なる識別子で複数存在する場合にも、同期をとっておく必要がある。
【００７６】
処理はステップＳ１７に戻って、上で述べた処理を繰り返す。
【００７７】
上で述べたような処理を実施するようにすれば、図１３のステップＳ９で特定された前線上存在補間点が経路到達線上の補間点に到達した時、当該前線上補間点における経路距離には最短距離が登録されているので、容易に最短距離が特定される。また復帰点情報も補間点管理テーブルにおいて管理されているので、復帰点情報を辿ることによって最短経路も容易に特定できる。
【００７８】
以下、図２９乃至図４０を用いて、処理の具体例を示すことによって、上で述べた処理をわかりやすくする。例えば各辺に２つの補間点が設定され且つ三角形要素Ｔ１乃至Ｔ３を含む、図２９のような三角形メッシュを前提とする。図２９において太線は経路出発線を示している。三角形Ｔ１は、辺（Ｔ１，Ｅ１）、（Ｔ１，Ｅ２）（＝（Ｔ２，Ｅ３））及び（Ｔ１，Ｅ３）を有しており、三角形Ｔ２は、辺（Ｔ２，Ｅ１）（＝（Ｔ３，Ｅ３））、（Ｔ２，Ｅ２）及び（Ｔ２，Ｅ３）（＝Ｔ１，Ｅ２）を有しており、三角形Ｔ３は、辺（Ｔ３，Ｅ１）、（Ｔ３，Ｅ２）及び（Ｔ３，Ｅ３）（＝（Ｔ２，Ｅ１））を有している。補間点は、反時計回りに識別番号が付与されている。
【００７９】
このような三角形メッシュが存在する場合に、補間点管理テーブルは図３０に示すような状態となる。まだ探索が行われていないので、各補間点の復帰点情報は全て「０」となる。また、初期的には経路距離は全ての補間点について無限大であるが、既に経路出発線が指定されているので、経路出発線上の補間点（辺（Ｔ１，Ｅ１）及び（Ｔ３，Ｅ１）上の補間点）については経路距離「０」が登録されている。同様に、ステップＳ７において経路出発線上の補間点は前線候補点として前線候補点集合に登録されるので、経路出発線上の補間点の補間点属性は、初期状態から前線候補に変更される。
【００８０】
次に、辺（Ｔ１，Ｅ１）の左端の頂点が前線上存在補間点ｈに選択された場合について図３１及び図３２を用いて説明する。この場合、図３１で点線矢印で示すように、三角形Ｔ１の辺（Ｔ１，Ｅ３）及び（Ｔ１，Ｅ２）を探索対象の辺として特定し、それらの辺上の５つの補間点を順に探索する。そうすると、補間点管理テーブルは、図３０の状態から図３２の状態に変化する。図３２において、（三角形ＩＤ，辺ＩＤ，補間点ＩＤ）の組み合わせで表すと、（１，２，１）（１，２，２）（１，３，０）（１，３，１）（１，３，２）の補間点について、復帰点情報として（１，１，０）が登録され、それぞれの経路距離が登録され、さらに補間点属性が「前線候補」に変更される。三角形Ｔ２については、同一補間点について同期をとるための更新が行われている。
【００８１】
そして最後に、前線上存在補間点ｈである補間点（１，１，０）は、補間点属性が前線通過完了と変更される。
【００８２】
その後、補間点属性が「前線候補」である補間点の中から経路距離が最短の補間点（１，１，１）が、前線上存在補間点ｈとして選択される。この場合、図３３で点線矢印で示すように、三角形Ｔ１の辺（Ｔ１，Ｅ３）及び（Ｔ１，Ｅ２）を探索対象の辺として特定し、それらの辺上の５つの補間点を順に探索する。そうすると、補間点管理テーブルは、図３２の状態から図３４の状態に変化する。すなわち、（１，２，１）（１，２，２）（１，３，０）（１，３，１）（１，３，２）の補間点について補間点（１，１，１）からの経路距離を算出すると、（１，３，２）の補間点以外の補間点（１，２，１）（１，２，２）（１，３，０）（１，３，１）については経路距離が短くなっていることが分かる。そのため、それらの補間点（図３４の星印の行）については、経路距離が今回の算出値に変更される。さらに、それらの復帰点情報は、前線上存在補間点ｈの補間点情報（１，１，１）に変更される。なお、探索された補間点の補間点属性は、既に「前線候補」に変更されているので、ここでは変更されない。
【００８３】
さらに、三角形Ｔ２については、同一補間点について同期をとるための更新が行われている。
【００８４】
そして最後に、前線上存在補間点ｈである補間点（１，１，１）は、補間点属性が前線通過完了と変更される。
【００８５】
さらに、補間点属性が「前線候補」である補間点の中から経路距離が最短の補間点（１，１，２）が、前線上存在補間点ｈとして選択される。この場合、図３５で点線矢印で示すように、三角形Ｔ１の辺（Ｔ１，Ｅ３）及び（Ｔ１，Ｅ２）を探索対象の辺として特定し、それらの辺上の５つの補間点を順に探索する。そうすると、補間点管理テーブルは、図３４の状態から図３６の状態に変化する。すなわち、（１，２，１）（１，２，２）（１，３，０）（１，３，１）（１，３，２）の補間点について補間点（１，１，２）からの経路距離を算出すると、補間点（１，２，１）及び（１，２，２）については経路距離が短くなっていることが分かる。そのため、それらの補間点（図３６の星印の行）については、経路距離が今回の算出値に変更される。さらに、それらの復帰点情報は、前線上存在補間点ｈの補間点情報（１，１，２）に変更される。なお、探索された補間点の補間点属性は、既に「前線候補」に変更されているので、ここでは変更されない。
【００８６】
さらに、三角形Ｔ２については、同一補間点について同期をとるための更新が行われている。
【００８７】
そして最後に、前線上存在補間点ｈである補間点（１，１，２）は、補間点属性が前線通過完了と変更される。
【００８８】
その後、補間点属性が「前線候補」である補間点の中から経路距離が最短の補間点（２，１，０）（＝（１，２，０））が、前線上存在補間点ｈとして選択される。この場合、図３７で点線矢印で示すように、三角形Ｔ２の辺（Ｔ２，Ｅ３）、（Ｔ２，Ｅ２）及び（Ｔ２，Ｅ１）を探索対象の辺として特定し、それらの辺上の８つの補間点を順に探索する。そうすると、補間点管理テーブルは、図３６の状態から図３８の状態に変化する。すなわち、（２，１，１）（２，１，２）（２，２，０）（２，２，１）（２，２，２）（２，３，０）（２，３，１）（２，３，２）の補間点について補間点（２，１，０）からの経路距離を算出すると、補間点（２，１，１）（２，１，２）（２，２，０）（２，２，１）（２，２，２）については経路距離が短くなっていることが分かる。そのため、それらの補間点（図３８の星印の行）については、経路距離が今回の算出値に変更される。さらに、それらの復帰点情報は、前線上存在補間点ｈの補間点情報（２，１，０）に変更される。さらに、それらの補間点の補間点属性は、「前線候補」に変更されている。
【００８９】
このような処理を繰り返し実施して、経路出発線上の補間点について探索処理が完了して前線候補点集合から除去された後に、経路距離が最も短い前線候補点は、補間点（１，２，１）（＝（２，３，２））である。この補間点（１，２，１）が前線上存在補間点ｈとして選択される。この場合、図３９で点線矢印で示すように、三角形Ｔ２の辺（Ｔ２，Ｅ１）及び（Ｔ２，Ｅ２）を探索対象の辺として特定し、それらの辺上の５つの補間点を順に探索する。そうすると、補間点管理テーブルは、図３８の状態から図４０の状態に変化する。すなわち、（２，１，１）（２，１，２）（２，２，０）（２，２，１）（２，２，２）の補間点について補間点（１，２，１）からの経路距離を算出すると、いずれの補間点についても経路距離が短くならない。そのため、経路距離が更新されるものはない。また、復帰点情報も補間点属性も今回は変更されない。但し、補間点（１，２，１）（＝（２，３，２）の補間点属性は、「前線通過完了」に変更される。
【００９０】
以上のような処理を繰り返し実施することによって、三角形メッシュの三角形要素に補間点を導入するが、補間点間のアークを規定・利用することなく探索を実施するので、データ量は削減され、処理も高速化される。
【００９１】
上で述べた方法でも実施可能であるが、最短距離の算出についてはさらに工夫が可能である。図４１に示すように、経路上のある補間点ｐから、補間点ｒ1及びｒ2を経由して、前線上存在補間点ｈに至った場合において、これらの補間点が属する三角形Ｔ1乃至Ｔ3が例えば三角形Ｔ1の属する平面に展開できたとする。そうすると、予め設定されている補間点ｒ1及びｒ2を経由すると補間点ｐから前線上存在補間点ｈまでの経路Ｘは、補間点ｐから前線上存在補間点ｈの直線距離Ｙよりも長くなってしまう。従って、前線上存在補間点ｈについての経路距離を登録する際には、例えば経路Ｘではなく経路Ｙの直線距離を用いて経路距離を算出する方が正確である。
【００９２】
このような平面展開による経路距離の算出及び平面展開による経路距離を算出した際に採用されるべき補間点の位置修正（すなわち図４１ではｒ1からｒaへの変更、ｒ2からｒbへの変更）については、以下で説明するような処理によって実現される。
【００９３】
Ａ．平面展開経路距離修正処理
本処理については図４２乃至図４９を用いて説明する。なお、本処理は、ステップＳ９において前線上存在補間点を特定する毎に実施する。
【００９４】
処理の具体的な説明を行う前に、平面展開区間及び平面展開区間端点について説明しておく。上で述べたように三角形メッシュにおいて経路上の三角形要素を平面に展開して直線で結ぶ必要があるため、経路上の三角形要素全てを平面に展開できるわけではなく、また平面に展開することが好ましくない場合もある。従って、以下で述べる条件を満たす補間点（頂点を含む）を検出した場合には、その補間点まで又はその一つ手前の補間点で平面展開を一旦停止するものとし、その補間点を平面展開区間端点と呼ぶことにする。また、図４２に示すように、経路上隣接する平面展開区間端点間（例えばＰ１とＰ２の間及びＰ２とＰ３の間）及び前線存在補間点ｈと経路上直前の平面展開区間端点Ｐ３との間を平面展開区間と呼ぶこととする。前線存在補間点ｈと平面展開区間端点Ｐ３の間の平面展開区間については、次の平面展開区間端点が検出されるまで長くなる。
【００９５】
平面展開区間端点と特定する条件は、２通りある。条件Ａは以下のとおりである。
（１）新たに進んだ前線上存在補間点が三角形の頂点に到達した場合
（２）新たに進んだ前線上存在補間点から平面展開区間端点への線分が途中の全ての辺と交差する状態ではない場合
（３）区間を構成する補間点の数が予め定めた条件を満たさなくなった場合
この３つのうちいずれかを満たしている場合には、平面展開区間端点と判断される。
【００９６】
一方、条件Ｂは以下のとおりである。
（１）新たに進んだ前線上存在補間点から平面展開区間端点への線分が途中の全ての辺と交差する状態ではない場合
（２）区間を構成する補間点の数が予め定めた条件を満たさなくなった場合
この２つのうちいずれかを満たしている場合には、平面展開区間端点と判断される。
【００９７】
条件Ａ（２）及びＢ（１）は、例えば図４３に示すような状況を示している。なお、以下では既に１平面上に辺や補間点が展開されているものとする。図４３では、辺ｅ1上に平面展開区間端点Ｐ１が属しており、辺ｅ2上に経路上の補間点ｒ1が属しており、辺ｅ3上に経路上の補間点ｒ2が属しており、辺ｅ4上の経路上の補間点ｒ3が属しており、辺ｅ5上に経路上の補間点ｈ、すなわち前線上存在補間点が属している場合を想定する。この際、補間点ｒ1と平面展開区間端点Ｐ１とは互いに隣接する経路上の補間点なので必ず条件Ａ（２）及びＢ（１）を満たさなくなってしまうので判定外であるが、補間点ｒ2と平面展開区間端点Ｐ１とを結ぶ線分は、辺ｅ2と交差し、補間点ｒ3と平面展開区間端点Ｐ１とを結ぶ線分は、辺ｅ2及びｅ3と交差するので、条件Ａ（２）及びＢ（１）を満たしていない。しかしながら、前線上存在補間点ｈと平面展開区間端点Ｐ１とを結ぶ線分は、辺ｅ4とは交差しているが、辺ｅ3及びｅ2については交差していないので、条件Ａ（２）及びＢ（１）を満たすようになる。このように平面展開区間端点Ｐ１から見てある程度の幅で前線上存在補間点が特定されて経路が伸びていく限りにおいては特に問題が生じない。しかし、図４３の例のように、経路が曲がったような場合にまで直線で結んだ経路を採用してしまうと、途中の補間点ｒ1、ｒ2及びｒ3を同じ辺上に定義できなくなり、復帰点が正しく規定できないという問題が生ずる。すなわち、２点を結ぶ直線が最短経路を形成しない。そこで、このような条件Ａ（２）及びＢ（１）に該当するような前線上存在補間点ｈを検出した場合には、経路上直前の補間点ｒ3（すなわち前線上存在補間点ｈの復帰点）を平面展開区間端点として特定する。
【００９８】
なお、条件Ａ（１）については、２点を結ぶ直線が最短経路を形成しない場合にはその補間点を平面展開区間端点として特定する。しかしながら、必ずしも特徴的な点でない場合もあり、平面展開しても問題ないこともあるので、条件Ｂでは採用していない。例えば図４４に示すように、平面展開区間端点Ｐ１から前線上存在補間点ｈまで平面展開を実施した場合に、辺ｅ1と辺ｅ2との頂点が平面展開区間端点Ｐ１であり、辺ｅ3上に経路上の次の補間点ｒ1が存在し、辺ｅ4上に経路上の次の補間点ｒ2が存在し、辺ｅ5とｅ6との交点が経路上の頂点ｒ3であり、辺ｅ7上に経路上の前線上存在補間点ｈが存在するものとする。このとき、条件Ａを採用する場合には、頂点ｒ3が平面展開区間端点として特定されるようになる。しかしながら、頂点ｒ3と平面展開区間端点Ｐ１とを結ぶ線分は、途中の辺ｅ3及びｅ4と交差する。すなわち途中の辺においても補間点を規定して復帰点を特定できる。そこで、条件Ｂを採用して、頂点ｒ3では平面展開区間を終了させず、前線上存在補間点ｈと平面展開区間端点Ｐ１への線分について確認すると、途中の辺と交差するので、前線上存在補間点ｈまで平面展開区間を延ばせる。これによって、直線距離を算出できる長さが長くなるので、経路距離の精度向上が可能となる。但し、条件Ａ（１）についても、３次元モデルの形状によっては必要な場合もある。
【００９９】
以上のような前提を下に、図４５乃至図４９を用いて具体的な処理内容を説明する。
【０１００】
まず、距離補正部１６１は、前線上存在補間点を特定する（図４５：ステップＳ３１）。ステップＳ９と同じである。そして、直前の平面展開区間端点を特定する（ステップＳ３３）。例えば、図１６に示した補間点管理テーブルのデータ・フォーマットを、例えば図４６に示すようなデータ・フォーマットに変更する。すなわち、図１６のテーブルに、平面展開区間端点であるか否かを表すフラグである端点フラグの列を追加している。端点フラグは、以下で述べる処理で平面展開区間端点であると判断された場合にセットされ、さらに経路出発線上の補間点については初期的にセットする。図４６は、初期設定が完了した状態を示している。
【０１０１】
そして、距離補正部１６１は、直前の平面展開区間端点が、前線上存在補間点の直前の復帰補間点であるか判断する（ステップＳ３５）。この条件を満たす場合には、直線的に前線上存在補間点と平面展開区間端点とが結ばれているので、処理を行う必要はない。従って、この条件を満たす場合には元の処理に戻る。一方、この条件を満たさない場合には、平面展開区間生成処理を実施する（ステップＳ３７）。この処理については以下に詳細に述べる。そして、元の処理に戻る。
【０１０２】
次に、平面展開区間生成処理について図４７乃至図４９を用いて説明する。まず、距離補正部１６１は、前線上存在補間点に係る復帰三角形を平面展開基準平面として特定する（ステップＳ４１）。例えば図４８のような状況を想定する。前線上補間点ｈと経路上直前の補間点ｒ1とを含む復帰三角形Ｔ1（頂点ＡＢＣ）を平面展開基準平面として特定する。復帰三角形は、補間点管理テーブル（図４６）において復帰点情報として登録されている。そして、次の復帰三角形を特定する（ステップＳ４３）。図４８の例では、三角形Ｔ2を特定する。また、次の復帰三角形の平面展開行列を算出し、例えば処理データ格納部１７に格納する（ステップＳ４５）。次の復帰三角形の平面展開行列の算出方法を、説明する。まず、次の復帰三角形Ｔ2の頂点Ｑから辺ＡＢへ下ろした垂線からの足を点Ｈをする。この点Ｈから頂点Ｑの平面展開基準平面への投影点Ｑtへの単位ベクトルをｖ1とし、点Ｈから頂点Ａへの単位ベクトルをｖ3とすると、ｖ2＝ｖ3×ｖ1となる。また、ベクトルＨＱとｖ1がなすｖ2方向の角をθとする。そして以下のような行列を定義する。
【数２】
【数３】
【０１０３】
このような前提の下、次の復帰三角形Ｔ2上の任意の点Ｘの、平面展開基準平面への平面展開は以下の式で表される。
Ｘt＝ＭＲＭTＸ＋（Ｅ−ＭＲＭT）Ｈ （１）
但し、Ｈは点Ｈの位置ベクトルである。
【０１０４】
この式の詳細な説明は省略するが、ｖ1、ｖ2、ｖ3で張られる局所座標系における軸ＡＢの角θの回転を、世界座標系に戻す演算を表したものである。
【０１０５】
なお、本ステップで算出される平面展開行列ＭＲＭT及び（Ｅ−ＭＲＭT）Ｈについては後の演算でも用いるので、例えば処理データ格納部１７に格納しておく。
【０１０６】
上の説明では平面展開基準平面である三角形Ｔ1と次の復帰三角形である三角形Ｔ2との関係を表したものであって、平面展開区間端点にたどり着かない場合には、三角形Ｔ2とさらに次の復帰三角形Ｔ3との関係を表す平面展開行列を算出する。また、それでも平面展開区間端点にたどり着かない場合には、三角形Ｔ3とさらに次の復帰三角形Ｔ4との関係を表す平面展開行列を算出する。このように平面展開区間端点にたどり着くまで繰り返し平面展開行列を算出する。平面展開区間端点にたどり着いた場合には、その前の復帰三角形Ｔn-1と平面展開区間端点ｈ及び経路上直前の補間点に係る三角形Ｔnとについての平面展開行列を算出することになる。
【０１０７】
その後、距離補正部１６１は、平面展開行列を用いて復帰補間点ｒ1を含む辺ＡＢの両端の頂点Ａ及びＢと復帰補間点ｒ1を平面展開基準平面に展開し、処理結果である座標値を例えば処理データ格納部１７に格納する（ステップＳ４７）。
【０１０８】
本ステップでは、（１）式に従って座標値を算出するわけであるが、通常は図４８の例のように１回で平面展開区間端点ｈに到達する訳ではない。２回目は、直前のステップＳ４５で算出された平面展開行列を用いて（１）式に従って演算した後に、得られた座標値と１回前のステップＳ４５で算出された平面展開行列とを用いて（１）式に従って演算する。
【０１０９】
３回目は、直前のステップＳ４５で算出された平面展開行列を用いて（１）式に従って演算し、得られた座標値と１回前のステップＳ４５で算出された平面展開行列とを用いて（１）式に従って演算し、さらに得られた座標値と２回前のステップＳ４５で算出された平面展開行列とを用いて（１）式に従って演算する。このような処理が繰り返されることとなる。
【０１１０】
その後、距離補正部１６１は、平面展開区間端点ｈまで処理が進んだか、すなわち次の復帰三角形が平面展開区間端点ｈが属する三角形要素になったか判断する（ステップＳ４９）。平面展開区間端点ｈまで処理が進んでいない場合にはステップＳ４３に戻る。
【０１１１】
一方、平面展開区間端点ｈまで処理が進んでいる場合には、距離補正部１６１は、前線上存在補間点と平面展開区間端点の平面展開点とを結ぶ直線が、平面展開された全ての辺と交差するか検査する（ステップＳ５１）。図４３に示した前線上存在補間点ｈについては、平面展開された全ての辺と交差するわけではないことが分かる。
【０１１２】
そして、距離補正部１６１は、前線上存在補間点と平面展開区間端点の平面展開点とを結ぶ直線が、平面展開された全ての辺と交差するか判断し（ステップＳ５３）、平面展開されたいずれかの辺と交差しない場合には、補間点管理テーブル（図４６）において前線上存在補間点の経路上直前の復帰補間点を、平面展開区間端点に設定する（ステップＳ５５）。このようにステップＳ５３で条件を満たさないと判断された場合には、平面展開区間端点と前線上存在補間点とを直線で結ぶことはないので、距離を補正する必要はない。具体的には、前回の距離補正がそのまま利用でき、前線上存在補間点と経路上直前の補間点（すなわち復帰点）との間は三角形内部距離Δｄとして算出されたものを用いれば、前線上存在補間点ｈまでの距離が得られる。
【０１１３】
一方、ステップＳ５３の条件を満たしていると判断された場合には、処理は端子Ｃを介して図４９の処理に移行する。
【０１１４】
そして、距離補正部１６１は、平面展開区間端点と前線上存在補間点との間の距離を算出し、例えばメインメモリなどの記憶装置に格納する（図４９：ステップＳ５７）。点間の距離の計算は周知なので、ここでは述べない。そして、補間点管理テーブルに格納されている、平面展開区間端点における距離に、ステップＳ５７で算出した距離を加算して、前線上存在補間点の経路距離として補間点管理テーブルに登録する（ステップＳ５９）。そして、前線上存在補間点が平面展開区間端点の条件Ａ又はＢを満たすか判断する（ステップＳ６１）。条件Ａであれば、条件Ａ（１）及び（３）を満たしているか、条件Ｂであれば、条件Ｂ（２）を満たしているか判断する。満たしている場合には、補間点管理テーブルにおいて、前線上存在補間点を平面展開区間端点に設定する（ステップＳ６３）。そして元の処理に戻る。満たしていない場合には、ステップＳ５９は不要なので元の処理に戻る。
【０１１５】
以上のような処理を実施することでより精度のよい経路距離の算出が可能となる。
【０１１６】
なお、平面展開経路距離修正処理は、上で述べた最短経路探索処理だけではなく、ダイクストラ法にも適用可能である。すなわち、ダイクストラ法における「最小の距離ｄをもつノードｚ∈Ｕを１つ探索」という処理において、重み付きグラフとは別に三角形メッシュを保持しておき、この三角形メッシュに対して同一の処理を行って距離ｄを補正すればよい。
【０１１７】
Ｂ．補間点位置補正処理
平面展開経路距離修正処理を実施すると、経路上の補間点の位置は初期的に設定した位置（又は想定した位置）とは異なる位置となる。従って、平面展開経路距離修正処理を実施する場合には、補間点位置補正処理を実施することが好ましい。しかし、補間点位置補正処理は、平面展開経路距離修正処理のようにステップＳ９で実施せずとも、経路到達線に前線上存在補間点が到達したときに１回実施すれば十分である。以下では、ステップＳ１３で実施する場合を前提に説明する。但し、平面展開経路距離修正処理と共に実施しても良い。
【０１１８】
補間点位置補正部１６２は、経路到達線上の前線上存在補間点を第１平面展開区間端点として特定する（図５０：ステップＳ７１）。また、補間点管理テーブル（図４６）において、経路到達線上の前線上存在補間点の復帰点から順次経路を遡ることによって、第１平面展開区間端点に最も近い平面展開区間端点を第２平面展開区間端点として特定する（ステップＳ７３）。
【０１１９】
そして、補間点位置補正部１６２は、位置補正処理を実施する（ステップＳ７５）。この処理については図５１乃至図５４を用いて説明する。まず、補間点位置補正部１６２は、第１平面展開区間端点の復帰三角形を平面展開基準平面として特定する（図５１：ステップＳ８１）。ステップＳ４１と同様である。そして、次の復帰三角形を特定する（ステップＳ８３）。これもステップＳ４３と同様である。さらに、次の復帰三角形の平面展開行列を算出し、例えば処理データ格納部１７に格納する（ステップＳ８５）。これもステップＳ４５と同様である。
【０１２０】
その後、補間点位置補正部１６２は、平面展開行列を用いて復帰補間点を含む辺の両端の頂点を平面展開基準平面に展開し、処理結果である座標値を例えば処理データ格納部１７に格納する（ステップＳ８７）。これもステップＳ４７とほぼ同様である。但し、復帰補間点の展開点は不要である。
【０１２１】
その後、補間点位置補正部１６２は、第２平面展開区間端点まで処理が進んだか、すなわち次の復帰三角形が第２平面展開区間端点が属する三角形要素になったか判断する（ステップＳ８９）。このステップも実質的にステップＳ４９と同様である。第２平面展開区間端点まで処理が進んでいない場合にはステップＳ８３に戻る。
【０１２２】
一方、第２平面展開区間端点まで処理が進んだ場合には、補間点位置補正部１６２は、第１及び第２の平面展開区間端点の平面展開点を結ぶ直線を含み、平面展開基準平面に直交するパラメタ算出平面を算出する（ステップＳ９１）。具体的には、例えば図５２に示すように、平面展開基準平面Ｋに第１平面展開区間端点Ｐ１及び第２の平面展開区間端点Ｐ２の展開点Ｐ２tとが属しており、それらを結ぶ線分ｍをとおり且つ平面展開基準平面Ｋに直交する平面Ｌがパラメタ算出平面である。なお、平面展開基準平面Ｋ上には、経路上の補間点ｒが属する辺ＡＢの展開点Ａt及びＢtも存在しており、線分ＡtＢtとパラメタ算出平面の交点ｒnewtは、辺ＡＢ上の新たな補間点ｒnewの展開点となる。処理は端子Ｄを介して図５３の処理に移行する。
【０１２３】
図５３の処理に移行して、補間点位置補正部１６２は、第１の平面展開区間端点から順に、未処理の次の復帰補間点を特定する（ステップＳ９３）。そして、特定された復帰補間点は第２の平面展開区間端点であるか判断する（ステップＳ９５）。特定された復帰補間点が第２の平面展開区間端点であれば、元の処理に戻る。
【０１２４】
一方、特定された復帰補間点が第２の平面展開区間端点でない場合には、補間点位置補正部１６２は、特定された復帰補間点が属する復帰辺をパラメタ算出平面で切断したときの辺のパラメタｘを算出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ９７）。すなわち、ｒnewt＝（１−ｘ）Ａt＋ｘＢtという関係があり、ｒnewtを算出すると共に、上記式を満たすｘを算出する。
【０１２５】
その後、補間点位置補正部１６２は、平面展開前の復帰辺（すなわち特定された復帰補間点が属する辺）をパラメタ値ｘにより分割して、特定された補間点の新たな座標値を算出し、例えば補間点データ格納部１３に格納する（ステップＳ９９）。すなわち、図５４に示すように、ｒnew＝（１−ｘ）Ａ＋ｘＢという関係から新たな座標値が算出される。処理はステップＳ９３に戻り、さらに次の復帰補間点を特定して処理を実施する。
【０１２６】
以上のような処理を実施することによって、補間点位置を、平面展開区間において補正することができる。
【０１２７】
図５０の処理の説明に戻り、補間点位置補正部１６２は、ステップＳ７５の後に、第２平面展開区間端点が経路出発線上の補間点であるか判断する（ステップＳ７７）。第２平面展開区間端点が経路出発線上の補間点でない場合には、第２平面展開区間端点を第１平面展開区間端点として設定し、次に近い平面展開区間端点を第２平面展開区間端点に設定する（ステップＳ７９）。補間点管理テーブルで復帰点を探索することによって次の平面展開区間端点は見つけることができる。そしてステップＳ７５に戻る。一方、第２平面展開区間端点が経路出発線上の補間点である場合には、元の処理に戻る。
【０１２８】
以上のような処理を実施することによって、経路上の補間点位置を、平面展開経路距離修正処理における経路距離に従った形で補正することができるようになる。
【０１２９】
以上本技術の一実施の形態を説明したが、本技術はこれに限定されるものではない。すなわち、例えば図５に示した機能ブロック図は一例であって、必ずしも実際のプログラムモジュール構成と一致しない場合もある。また、複数台のコンピュータで機能分担を行うようにしても良い。
【０１３０】
また、処理結果が変わらない限り、処理ステップの実行順番を入れ替えたり、並列実行するようにしても良い。
【０１３１】
さらに、上では図１０を用いて位相テーブルの例を示したが、位相情報は図１０の位相テーブルに限定されるわけではない。メッシュの位相情報は、メッシュを構成する三角形、辺、頂点の接続関係を表現するものであり、多くの表現方法が知られている。メッシュの位相表現は、境界表現（boundary representation, B-Rep）と呼ばれる立体表面の面分、辺、頂点を表現する位相構造の特別なものである。
【０１３２】
よく知られている境界表現による物体表現方法に、１９７４年にBruce Guenther Baumgartによって発表されたウイングドエッジ構造がある。これは、図５５に示すように、物体表面のフェース（面分。ここでは三角形に対応する）、辺、頂点にそれぞれ識別子を付し、各辺から両端の頂点、両側のフェース、両端の頂点に接続する両側のフェースに帰属する合計４個の辺へのポインタを保有することによって、物体表面の位相構造を表現するものである。
【０１３３】
ウイングドエッジ構造は辺がベースになっており、辺とフェース、辺と頂点の間の隣接関係を用いて、物体全ての位相要素の接続関係を表現している。Weilerによれば隣接関係の選択方法は９通りあるので、位相表現のバリエーションは多数存在することが知られている。”Kevin Weiler: Edge-Based Data Structure for Solid Modeling in Curved-Surface Environments, IEEE CG&A 1985 Jan. p.21-40”を参照のこと。なお、本実施の形態で挙げたメッシュの表現方法は三角形メッシュの場合に限ると、データ量がウイングドエッジ構造よりも小さいのが特徴である。
【０１３４】
なお、最短経路探索装置は、コンピュータ装置であって、図５６に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納される。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１３５】
以上本実施の形態をまとめると以下のようになる。
【０１３６】
３次元モデル上における最短経路をコンピュータにより探索する最短経路探索方法は、３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する三角形及び辺のデータに当該三角形の頂点及び補間点のデータを関連付けて探索管理データ格納部に格納するステップと、３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付けるステップと、出発点又は出発線から到達点又は到達線に至るまで、補間点及び頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である補間点又は頂点について出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、最短距離探索対象点である補間点又は頂点に関連付けて距離を探索管理データ格納部に格納する探索ステップとを含む。
【０１３７】
このように三角形メッシュに含まれる各三角形要素の辺に補間点を追加することによって精度向上を図ることができる。また、補間点間のアークを生成することもないので、保持すべきデータ量を著しく削減できる。さらに補間点間のアークを生成することがないので、その分の計算時間をも削減することができる。
【０１３８】
なお、上で述べた探索ステップが、最短距離探索対象点である補間点又は頂点に関連付けて最短距離探索対象点の経路上直前の補間点又は頂点を特定するためのデータを、探索管理データ格納部に格納するステップを含むようにしてもよい。その場合、本最短経路探索方法は、探索管理データ格納部において到達点又は到達線上の補間点又は頂点に関連付けて出発点又は出発線からの最短距離が登録された場合には、探索管理データ格納部において、到達点又は到達線上の補間点又は頂点から出発点又は出発線上の補間点又は頂点まで、経路上の補間点又は頂点に関連付けて格納されている経路上直前の補間点又は頂点を特定するためのデータを抽出することによって最短経路を特定する経路特定ステップをさらに含むようにしてもよい。これによって、最短距離だけではなく、最短経路も特定できるようになる。
【０１３９】
さらに、上で述べた探索ステップが、最短距離探索対象点である補間点又は頂点に関連付けて最短距離探索対象点の経路上直前の補間点又は頂点を特定するための復帰情報を、探索管理データ格納部に格納するステップを含むようにしてもよい。その際には、探索ステップにおいて、三角形メッシュの位相情報と復帰情報とに基づき予め定められるルールに従って、探索先の補間点又は頂点を特定するようにしてもよい。これによって、適切な探索先が特定されるので、網羅的な探索よりも高速に処理が行われるようになる。
【０１４０】
また、上で述べた探索ステップが、探索管理データ格納部に距離が格納済みであって且つ最短距離探索対象点の探索元の候補点となる補間点及び頂点を管理するデータを格納する候補管理データ格納部に格納されている候補点から、探索管理データ格納部に登録されている距離が最短の候補点を、最短距離探索対象点の探索元点として特定するステップと、探索元点を含む三角形に係る補間点又は頂点を最短距離探索対象点として特定して、候補管理データ格納部に格納する特定ステップと、最短距離探索対象点の探索が完了した場合、候補管理データ格納部から探索元点を削除する削除ステップとを含むようにしてもよい。このようにすることによって探索が効率的に実施される。
【０１４１】
また、上で述べた削除ステップが、探索元点に関連付けて通過完了を示すデータを探索管理データ格納部に登録するステップを含むようにしてもよい。その際、特定ステップにおいて、通過完了を示すデータが登録されている補間点又は頂点を除外して最短距離探索対象点を特定するようにしてもよい。効率的な探索が可能となる。
【０１４２】
さらに、上で述べた探索ステップが、最短距離探索対象点を含む経路の少なくとも一部区間について、補間点又は頂点間の距離の和から、一部区間に係る三角形を平面展開した場合における一部区間両端の直線距離へ修正する距離修正ステップを含むようにしてもよい。これによって距離の精度を高めることができるようになる。
【０１４３】
さらに、探索管理データ格納部において、直線距離を算出できる区間の端点である補間点又は頂点に関連付けて平面展開区間端点を示すデータを登録していてもよい。その際 距離修正ステップが、最短距離探索対象点及び当該最短距離探索対象点の経路上直前の補間点又は頂点を含む三角形を包含する平面に、最短距離探索対象点から最も近い平面展開区間端点までの経路区間上の補間点又は頂点及び当該補間点又は頂点に係る三角形の辺を投影するステップと、平面上において、最短距離探索対象点と、平面展開区間端点とを結ぶ直線が、当該経路区間上の補間点又は頂点がのっている三角形の全ての辺と交差するか判断する判断ステップと、判断ステップの条件を満たす場合には、最短距離探索対象点から平面展開区間端点までの直線距離を算出し、探索管理データ格納部において平面展開区間端点に関連付けて格納されている距離と直線距離を加算して、探索管理データ格納部において最短距離探索対象点に関連付けて加算結果を登録するステップとを含むようにしてもよい。これによって距離の精度を高めることができるようになる。
【０１４４】
また、上で述べた距離修正ステップが、判断ステップの条件を満たさない場合には、最短距離探索対象点の経路上直前の補間点に関連付けて平面展開区間端点を示すデータを、探索管理データ格納部に登録するステップと、判断ステップの条件を満たす場合には、予め定められた平面展開区間端点の条件を最短距離探索対象点が満たすか判断し、満たすと判断された場合には、最短距離探索対象点に関連付けて平面展開区間端点を示すデータを、探索管理データ格納部に登録するステップとを含むようにしてもよい。このようにすれば、適切な範囲で平面展開を実施することができるようになる。
【０１４５】
なお、上で述べた判断ステップの条件が、三角形メッシュの頂点であるという条件を含む場合もある。頂点というものは形状上の特徴点となりうるからである。
【０１４６】
また、上で述べた経路特定ステップが、最短距離探索対象点を含む経路の少なくとも一部区間について、一部区間に係る三角形を平面展開した場合における一部区間両端をつなぐ直線を含み且つ平面展開後の平面に直交する第２の平面と上記一部区間に係る三角形の辺との交点に、一部区間における補間点を変更するステップを含むようにしてもよい。これによって適切な補間点位置を特定できるようになる。
【０１４７】
さらに、上で述べた三角形メッシュにおける三角形に屈折率が設定されるようにしてもよい。この場合、上記距離を、経路上の三角形の屈折率を用いて算出するようにする。例えば絶縁率が３次元モデルの部分毎に異なる場合に、当該絶縁率を勘案した形で距離を算出することによって、適切に沿面距離を算出するものである。
【０１４８】
なお、上で述べたような処理をハードウエアに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。
【０１４９】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１５０】
（付記１）
３次元モデル上における最短経路をコンピュータにより探索する最短経路探索方法であって、
前記３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する前記三角形及び前記辺のデータに当該三角形の頂点及び前記補間点のデータを関連付けて探索管理データ格納部に格納するステップと、
前記３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付けるステップと、
前記出発点又は出発線から前記到達点又は到達線に至るまで、前記補間点及び前記頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である前記補間点又は前記頂点について前記出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記距離を前記探索管理データ格納部に格納する探索ステップと、
を含む最短経路探索方法。
【０１５１】
（付記２）
前記探索ステップが、
前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記最短距離探索対象点の経路上直前の前記補間点又は前記頂点を特定するためのデータを、前記探索管理データ格納部に格納するステップ
を含み、
前記探索管理データ格納部において前記到達点又は到達線上の前記補間点又は前記頂点に関連付けて前記出発点又は出発線からの最短距離が登録された場合には、前記探索管理データ格納部において、前記到達点又は到達線上の前記補間点又は前記頂点から前記出発点又は出発線上の前記補間点又は前記頂点まで、経路上の前記補間点又は前記頂点に関連付けて格納されている前記経路上直前の前記補間点又は前記頂点を特定するためのデータを抽出することによって最短経路を特定する経路特定ステップ
をさらに含む、付記１記載の最短経路探索方法。
【０１５２】
（付記３）
前記探索ステップが、
前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記最短距離探索対象点の経路上直前の前記補間点又は前記頂点を特定するための復帰情報を、前記探索管理データ格納部に格納するステップ
を含み、
前記探索ステップにおいて、
前記三角形メッシュの位相情報と前記復帰情報とに基づき予め定められるルールに従って、探索先の前記補間点又は前記頂点を特定する
付記１記載の最短経路探索方法。
【０１５３】
（付記４）
前記探索ステップが、
前記探索管理データ格納部に前記距離が格納済みであって且つ前記最短距離探索対象点の探索元の候補点となる前記補間点及び前記頂点を管理するデータを格納する候補管理データ格納部に格納されている前記候補点から、前記探索管理データ格納部に登録されている前記距離が最短の候補点を、前記最短距離探索対象点の探索元点として特定するステップと、
前記探索元点を含む前記三角形に係る前記補間点又は前記頂点を前記最短距離探索対象点として特定して、前記候補管理データ格納部に格納する特定ステップと、
前記最短距離探索対象点の探索が完了した場合、前記候補管理データ格納部から前記探索元点を削除する削除ステップと、
を含む付記１又は２記載の最短経路探索方法。
【０１５４】
（付記５）
前記削除ステップが、
前記探索元点に関連付けて通過完了を示すデータを前記探索管理データ格納部に登録するステップ
を含み、
前記特定ステップにおいて、前記通過完了を示すデータが登録されている前記補間点又は前記頂点を除外して前記最短距離探索対象点を特定する
付記４記載の最短経路探索方法。
【０１５５】
（付記６）
前記探索ステップが、
前記最短距離探索対象点を含む経路の少なくとも一部区間について、前記補間点又は前記頂点間の距離の和から、前記一部区間に係る三角形を平面展開した場合における前記一部区間両端の直線距離へ修正する距離修正ステップ
を含む付記１乃至５のいずれか１つ記載の最短経路探索方法。
【０１５６】
（付記７）
前記探索管理データ格納部において、直線距離を算出できる区間の端点である補間点又は頂点に関連付けて平面展開区間端点を示すデータを登録しており、
前記距離修正ステップが、
前記最短距離探索対象点及び当該最短距離探索対象点の経路上直前の前記補間点又は前記頂点を含む三角形を包含する平面に、前記最短距離探索対象点から最も近い前記平面展開区間端点までの経路区間上の前記補間点又は前記頂点及び当該補間点又は前記頂点に係る三角形の辺を投影するステップと、
前記平面上において、前記最短距離探索対象点と、前記平面展開区間端点とを結ぶ直線が、当該経路区間上の補間点又は頂点がのっている前記三角形の全ての辺と交差するか判断する判断ステップと、
前記判断ステップの条件を満たす場合には、前記最短距離探索対象点から前記平面展開区間端点までの直線距離を算出し、前記探索管理データ格納部において前記平面展開区間端点に関連付けて格納されている前記距離と前記直線距離を加算して、前記探索管理データ格納部において前記最短距離探索対象点に関連付けて加算結果を登録するステップと、
を含む付記６記載の最短経路探索方法。
【０１５７】
（付記８）
前記距離修正ステップが、
前記判断ステップの条件を満たさない場合には、前記最短距離探索対象点の経路上直前の前記補間点に関連付けて前記平面展開区間端点を示すデータを、前記探索管理データ格納部に登録するステップと、
前記判断ステップの条件を満たす場合には、予め定められた前記平面展開区間端点の条件を前記最短距離探索対象点が満たすか判断し、満たすと判断された場合には、前記最短距離探索対象点に関連付けて前記平面展開区間端点を示すデータを、前記探索管理データ格納部に登録するステップと、
をさらに含む付記７記載の最短経路探索方法。
【０１５８】
（付記９）
前記判断ステップの条件が、前記三角形メッシュの頂点であるという条件を含む
付記７又は８記載の最短経路探索方法。
【０１５９】
（付記１０）
前記経路特定ステップが、
前記最短距離探索対象点を含む経路の少なくとも一部区間について、前記一部区間に係る三角形を平面展開した場合における前記一部区間両端をつなぐ直線を含み且つ前記平面展開後の平面に直交する第２の平面と前記一部区間に係る三角形の辺との交点に、前記一部区間における前記補間点を変更するステップ
を含む付記２記載の最短経路探索方法。
【０１６０】
（付記１１）
前記三角形メッシュにおける三角形に屈折率が設定されており、
前記距離を、前記経路上の三角形の屈折率を用いて算出する
付記１乃至１０のいずれか１つ記載の最短経路探索方法。
【０１６１】
（付記１２）
付記１乃至１１のいずれか１つ記載の最短経路探索方法をコンピュータに実行させるためのプログラム。
【０１６２】
（付記１３）
３次元モデル上における最短経路を探索する最短経路探索装置であって、
探索管理データ格納部と、
三角形メッシュの位相情報を含む、当該三角形メッシュのデータを格納する三角形メッシュデータ格納部と、
前記三角形メッシュデータ格納部に格納されている、前記３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する前記三角形及び前記辺のデータに当該三角形の頂点及び前記補間点のデータを関連付けて前記探索管理データ格納部に格納する手段と、
前記３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付ける手段と、
前記出発点又は出発線から前記到達点又は到達線に至るまで、前記補間点及び前記頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である前記補間点又は前記頂点について前記出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記距離を前記探索管理データ格納部に格納する探索手段と、
を有する最短経路探索装置。
【符号の説明】
【０１６３】
１１ 三角形メッシュデータ格納部 １２ 補間点データ生成部
１３ 補間データ格納部 １４ データ入力部
１５ 開始終了データ格納部 １６ 探索処理部
１７ 処理データ格納部 １８ 出力データ格納部
１９ 出力部
１６１ 距離補正部 １６２ 補間点位置補正部
【特許請求の範囲】
【請求項１】
３次元モデル上における最短経路をコンピュータにより探索する最短経路探索方法であって、
前記３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する前記三角形及び前記辺のデータに当該三角形の頂点及び前記補間点のデータを関連付けて探索管理データ格納部に格納するステップと、
前記３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付けるステップと、
前記出発点又は出発線から前記到達点又は到達線に至るまで、前記補間点及び前記頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である前記補間点又は前記頂点について前記出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記距離を前記探索管理データ格納部に格納する探索ステップと、
を含む最短経路探索方法。
【請求項２】
前記探索ステップが、
前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記最短距離探索対象点の経路上直前の前記補間点又は前記頂点を特定するためのデータを、前記探索管理データ格納部に格納するステップ
を含み、
前記探索管理データ格納部において前記到達点又は到達線上の前記補間点又は前記頂点に関連付けて前記出発点又は出発線からの最短距離が登録された場合には、前記探索管理データ格納部において、前記到達点又は到達線上の前記補間点又は前記頂点から前記出発点又は出発線上の前記補間点又は前記頂点まで、経路上の前記補間点又は前記頂点に関連付けて格納されている前記経路上直前の前記補間点又は前記頂点を特定するためのデータを抽出することによって最短経路を特定する経路特定ステップ
をさらに含む、請求項１記載の最短経路探索方法。
【請求項３】
前記探索ステップが、
前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記最短距離探索対象点の経路上直前の前記補間点又は前記頂点を特定するための復帰情報を、前記探索管理データ格納部に格納するステップ
を含み、
前記探索ステップにおいて、
前記三角形メッシュの位相情報と前記復帰情報とに基づき予め定められるルールに従って、探索先の前記補間点又は前記頂点を特定する
請求項１記載の最短経路探索方法。
【請求項４】
前記探索ステップが、
前記探索管理データ格納部に前記距離が格納済みであって且つ前記最短距離探索対象点の探索元の候補点となる前記補間点及び前記頂点を管理するデータを格納する候補管理データ格納部に格納されている前記候補点から、前記探索管理データ格納部に登録されている前記距離が最短の候補点を、前記最短距離探索対象点の探索元点として特定するステップと、
前記探索元点を含む前記三角形に係る前記補間点又は前記頂点を前記最短距離探索対象点として特定して、前記候補管理データ格納部に格納する特定ステップと、
前記最短距離探索対象点の探索が完了した場合、前記候補管理データ格納部から前記探索元点を削除する削除ステップと、
を含む請求項１又は２記載の最短経路探索方法。
【請求項５】
前記探索ステップが、
前記最短距離探索対象点を含む経路の少なくとも一部区間について、前記補間点又は前記頂点間の距離の和から、前記一部区間に係る三角形を平面展開した場合における前記一部区間両端の直線距離へ修正する距離修正ステップ
を含む請求項１乃至４のいずれか１つ記載の最短経路探索方法。
【請求項６】
前記探索管理データ格納部において、直線距離を算出できる区間の端点である補間点又は頂点に関連付けて平面展開区間端点を示すデータを登録しており、
前記距離修正ステップが、
前記最短距離探索対象点及び当該最短距離探索対象点の経路上直前の前記補間点又は前記頂点を含む三角形を包含する平面に、前記最短距離探索対象点から最も近い前記平面展開区間端点までの経路区間上の前記補間点又は前記頂点及び当該補間点又は前記頂点に係る三角形の辺を投影するステップと、
前記平面上において、前記最短距離探索対象点と、前記平面展開区間端点とを結ぶ直線が、当該経路区間上の補間点又は頂点がのっている前記三角形の全ての辺と交差するか判断する判断ステップと、
前記判断ステップの条件を満たす場合には、前記最短距離探索対象点から前記平面展開区間端点までの直線距離を算出し、前記探索管理データ格納部において前記平面展開区間端点に関連付けて格納されている前記距離と前記直線距離を加算して、前記探索管理データ格納部において前記最短距離探索対象点に関連付けて加算結果を登録するステップと、
を含む請求項５記載の最短経路探索方法。
【請求項７】
前記経路特定ステップが、
前記最短距離探索対象点を含む経路の少なくとも一部区間について、前記一部区間に係る三角形を平面展開した場合における前記一部区間両端をつなぐ直線を含み且つ前記平面展開後の平面に直交する第２の平面と前記一部区間に係る三角形の辺との交点に、前記一部区間における前記補間点を変更するステップ
を含む請求項２記載の最短経路探索方法。
【請求項８】
請求項１乃至７のいずれか１つ記載の最短経路探索方法をコンピュータに実行させるためのプログラム。
【請求項９】
３次元モデル上における最短経路を探索する最短経路探索装置であって、
探索管理データ格納部と、
三角形メッシュの位相情報を含む、当該三角形メッシュのデータを格納する三角形メッシュデータ格納部と、
前記三角形メッシュデータ格納部に格納されている、前記３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する前記三角形及び前記辺のデータに当該三角形の頂点及び前記補間点のデータを関連付けて前記探索管理データ格納部に格納する手段と、
前記３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付ける手段と、
前記出発点又は出発線から前記到達点又は到達線に至るまで、前記補間点及び前記頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である前記補間点又は前記頂点について前記出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記距離を前記探索管理データ格納部に格納する探索手段と、
を有する最短経路探索装置。
【請求項１】
３次元モデル上における最短経路をコンピュータにより探索する最短経路探索方法であって、
前記３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する前記三角形及び前記辺のデータに当該三角形の頂点及び前記補間点のデータを関連付けて探索管理データ格納部に格納するステップと、
前記３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付けるステップと、
前記出発点又は出発線から前記到達点又は到達線に至るまで、前記補間点及び前記頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である前記補間点又は前記頂点について前記出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記距離を前記探索管理データ格納部に格納する探索ステップと、
を含む最短経路探索方法。
【請求項２】
前記探索ステップが、
前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記最短距離探索対象点の経路上直前の前記補間点又は前記頂点を特定するためのデータを、前記探索管理データ格納部に格納するステップ
を含み、
前記探索管理データ格納部において前記到達点又は到達線上の前記補間点又は前記頂点に関連付けて前記出発点又は出発線からの最短距離が登録された場合には、前記探索管理データ格納部において、前記到達点又は到達線上の前記補間点又は前記頂点から前記出発点又は出発線上の前記補間点又は前記頂点まで、経路上の前記補間点又は前記頂点に関連付けて格納されている前記経路上直前の前記補間点又は前記頂点を特定するためのデータを抽出することによって最短経路を特定する経路特定ステップ
をさらに含む、請求項１記載の最短経路探索方法。
【請求項３】
前記探索ステップが、
前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記最短距離探索対象点の経路上直前の前記補間点又は前記頂点を特定するための復帰情報を、前記探索管理データ格納部に格納するステップ
を含み、
前記探索ステップにおいて、
前記三角形メッシュの位相情報と前記復帰情報とに基づき予め定められるルールに従って、探索先の前記補間点又は前記頂点を特定する
請求項１記載の最短経路探索方法。
【請求項４】
前記探索ステップが、
前記探索管理データ格納部に前記距離が格納済みであって且つ前記最短距離探索対象点の探索元の候補点となる前記補間点及び前記頂点を管理するデータを格納する候補管理データ格納部に格納されている前記候補点から、前記探索管理データ格納部に登録されている前記距離が最短の候補点を、前記最短距離探索対象点の探索元点として特定するステップと、
前記探索元点を含む前記三角形に係る前記補間点又は前記頂点を前記最短距離探索対象点として特定して、前記候補管理データ格納部に格納する特定ステップと、
前記最短距離探索対象点の探索が完了した場合、前記候補管理データ格納部から前記探索元点を削除する削除ステップと、
を含む請求項１又は２記載の最短経路探索方法。
【請求項５】
前記探索ステップが、
前記最短距離探索対象点を含む経路の少なくとも一部区間について、前記補間点又は前記頂点間の距離の和から、前記一部区間に係る三角形を平面展開した場合における前記一部区間両端の直線距離へ修正する距離修正ステップ
を含む請求項１乃至４のいずれか１つ記載の最短経路探索方法。
【請求項６】
前記探索管理データ格納部において、直線距離を算出できる区間の端点である補間点又は頂点に関連付けて平面展開区間端点を示すデータを登録しており、
前記距離修正ステップが、
前記最短距離探索対象点及び当該最短距離探索対象点の経路上直前の前記補間点又は前記頂点を含む三角形を包含する平面に、前記最短距離探索対象点から最も近い前記平面展開区間端点までの経路区間上の前記補間点又は前記頂点及び当該補間点又は前記頂点に係る三角形の辺を投影するステップと、
前記平面上において、前記最短距離探索対象点と、前記平面展開区間端点とを結ぶ直線が、当該経路区間上の補間点又は頂点がのっている前記三角形の全ての辺と交差するか判断する判断ステップと、
前記判断ステップの条件を満たす場合には、前記最短距離探索対象点から前記平面展開区間端点までの直線距離を算出し、前記探索管理データ格納部において前記平面展開区間端点に関連付けて格納されている前記距離と前記直線距離を加算して、前記探索管理データ格納部において前記最短距離探索対象点に関連付けて加算結果を登録するステップと、
を含む請求項５記載の最短経路探索方法。
【請求項７】
前記経路特定ステップが、
前記最短距離探索対象点を含む経路の少なくとも一部区間について、前記一部区間に係る三角形を平面展開した場合における前記一部区間両端をつなぐ直線を含み且つ前記平面展開後の平面に直交する第２の平面と前記一部区間に係る三角形の辺との交点に、前記一部区間における前記補間点を変更するステップ
を含む請求項２記載の最短経路探索方法。
【請求項８】
請求項１乃至７のいずれか１つ記載の最短経路探索方法をコンピュータに実行させるためのプログラム。
【請求項９】
３次元モデル上における最短経路を探索する最短経路探索装置であって、
探索管理データ格納部と、
三角形メッシュの位相情報を含む、当該三角形メッシュのデータを格納する三角形メッシュデータ格納部と、
前記三角形メッシュデータ格納部に格納されている、前記３次元モデルの三角形メッシュにおける各三角形の各辺に補間点を設けて、該当する前記三角形及び前記辺のデータに当該三角形の頂点及び前記補間点のデータを関連付けて前記探索管理データ格納部に格納する手段と、
前記３次元モデルにおける出発点又は出発線と、到達点又は到達線との指定を受け付ける手段と、
前記出発点又は出発線から前記到達点又は到達線に至るまで、前記補間点及び前記頂点を当該三角形メッシュの位相情報に基づき順番に探索して、探索における最短距離探索対象点である前記補間点又は前記頂点について前記出発点又は出発線からの距離を算出し、当該距離が全経路の中で最短であれば、前記最短距離探索対象点である前記補間点又は前記頂点に関連付けて前記距離を前記探索管理データ格納部に格納する探索手段と、
を有する最短経路探索装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３】
【図４４】
【図４５】
【図４６】
【図４７】
【図４８】
【図４９】
【図５０】
【図５１】
【図５２】
【図５３】
【図５４】
【図５５】
【図５６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３】
【図４４】
【図４５】
【図４６】
【図４７】
【図４８】
【図４９】
【図５０】
【図５１】
【図５２】
【図５３】
【図５４】
【図５５】
【図５６】
【公開番号】特開２０１０−１７６３４７（Ｐ２０１０−１７６３４７Ａ）
【公開日】平成２２年８月１２日（２０１０．８．１２）
【国際特許分類】
【出願番号】特願２００９−１７６６５（Ｐ２００９−１７６６５）
【出願日】平成２１年１月２９日（２００９．１．２９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２２年８月１２日（２０１０．８．１２）
【国際特許分類】
【出願日】平成２１年１月２９日（２００９．１．２９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]