(57)【要約】【課題】３Ｄ（３次元）モデル化オブジェクトを設計する方法を提供すること。【解決手段】３次元モデル化オブジェクトを設計するコンピュータ実装方法が提供され、その方法は、モデル化オブジェクトの複数の２次元ビューと、３次元ワイヤーフレームグラフとを提供する（Ｓ１０）ステップと、ワイヤーフレームグラフの各頂点に対し、頂点に入射するすべてのエッジ間の局所半径方向順序を関連付ける（Ｓ２０）ステップと、頂点に関連付けられた局所半径方向順序に従ってワイヤーフレームグラフを閲覧することによってエッジサイクルを決定する（Ｓ３０）ステップとを備える。このような方法は、３Ｄモデル化オブジェクトの設計を改善する。【選択図】図１
2014235756.tif 000002
【特許請求の範囲】
【請求項１】
３次元モデル化オブジェクトを設計するためのコンピュータ実装方法は、
ビュー上で規定されるカーブとポイントとを有する前記モデル化オブジェクトの複数の２次元ビューを提供するステップであって、３次元ワイヤーフレームグラフは、頂点を結合するエッジ、および前記ビュー上のそれぞれカーブとポイントについて前記エッジと前記頂点間のコレスポンデンスを備えるステップと、
前記ワイヤーフレームグラフの各頂点に対し、前記頂点に対応する前記ポイントに対してそれぞれのビュー上の前記エッジに対応する前記カーブ間の局所部分半径方向順序に従って、前記頂点に入射するすべてのエッジ間の局所半径方向順序を関連付けるステップと、
前記頂点に関連付けられた前記局所半径方向順序に従って前記ワイヤーフレームグラフを閲覧することによって、エッジサイクルを決定するステップと、
を備えることを特徴とするコンピュータ実装方法。
【請求項２】
前記ワイヤーフレームグラフの各頂点に対し、それぞれの頂点に入射するすべてのエッジ間の局所半径方向順序を関連付けるステップは、各それぞれの頂点に対し、
各ビューに対し、前記ビュー上で規定され、および前記それぞれの頂点に入射するエッジに対応するカーブ間の前記それぞれの頂点に対応する前記ポイントについて前記局所部分半径方向順序を決定するステップと、
前記すべての局所部分半径方向順序を統合するステップと、
前記それぞれの頂点に入射するすべてのエッジを含むサイクルを検出するために、前記すべての局所部分半径方向順序の前記統合するステップの結果をトラバースするステップであって、前記サイクルは、前記それぞれの頂点に関連付けられた前記局所半径方向順序を構成するステップと、
を備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記局所部分半径方向順序は、ノードがエッジを特定し、および円弧がエッジ間のサブシーケンスを特定するグラフとして決定されること
を特徴とする請求項２に記載の方法。
【請求項４】
前記ワイヤーフレームグラフの各頂点に対し、それぞれの頂点に入射するすべてのエッジ間の局所半径方向順序を関連付けるステップは、前記すべての局所部分半径方向順序の前記統合するステップの結果をトラバースするステップが、前記それぞれの頂点に入射するすべてのエッジを含むいくつかのサイクルを検出することを導く時、検出された前記それぞれの頂点の前記サイクルのうちの１つを選択するステップをさらに備えることであって、前記それぞれの頂点は、特異頂点であることを特徴とする請求項２または３に記載の方法。
【請求項５】
検出された前記サイクルのうちの１つを選択するステップは、すべての特異頂点のセット上で正則化プロセスを実行することを備え、前記正則化プロセスは、
開始特異頂点と前記開始特異頂点の開始出力エッジとを選択するステップと、
前記開始特異頂点においてエッジサイクルを検出するために前記頂点と関連付けられた前記局所半径方向順序に従って前記ワイヤーフレームグラフを閲覧するステップと、
その結果
別の特異頂点に到達するのであれば、新しい開始特異頂点および／または新しい開始出力エッジを用いて前記正則化プロセスを反復するステップと、
そうでなければ、前記すべての局所部分半径方向順序の前記統合するステップの結果をトラバースするステップが、前記開始出力エッジと閲覧された前記最終エッジとの間の順序に準拠していることを導いた時に検出される、前記開始特異頂点に関連付けて、前記すべての特異頂点のセットから前記開始特異頂点を除去し、そして特異頂点がなくなるまで前記正則化プロセスを反復することを備えること
を特徴とする請求項４に記載の方法。
【請求項６】
前記ワイヤーフレームグラフを閲覧することによってエッジサイクルを決定するステップは、
頂点を選択するサブステップと、
前記選択された頂点から開始して、それらの頂点が交わる時に前記頂点に関連付けられる前記局所半径方向順序に従ってエッジリストを形成し、そして前記エッジリストがエッジサイクルを形成するまで、次に続くエッジを前記エッジリストに新規に追加するサブステップと、
前のサブステップを反復するサブステップと、
を備えることを特徴とする請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
前記ビューはイメージであり、および前記ワイヤーフレームグラフは、前記イメージに基づく前記モデル化オブジェクトの３次元構成であること
を特徴とする請求項１乃至６のいずれか１項に記載の方法。
【請求項８】
方法は、前記ビュー、前記ワイヤーフレーム、および前記コレスポンデンスを提供するステップの前に
同じ物理的な製品のイメージをキャプチャするステップと、
前記イメージ上のカーブとポイントを規定するステップであって、それによって前記ビューを形成するステップと、
前記他のイメージ上のそれぞれカーブとポイントについて各イメージの前記カーブとポイント間のコレスポンデンスを規定するステップと、
前記ビューおよび前記コレスポンデンスに基づいて前記ワイヤーフレームグラフを構成するステップであって、それによって構成される前記ワイヤーフレームグラフは、頂点を結合するエッジ、および前記ビュー上のそれぞれカーブとポイントについて前記エッジと前記頂点間のコレスポンデンスを備えるステップと、
をさらに備えることを特徴とする請求項７に記載の方法。
【請求項９】
前記イメージは、写真であることを特徴とする請求項７または８に記載の方法。
【請求項１０】
前記決定されたエッジサイクルに基づいて前記ワイヤーフレームグラフとサーフェスを一致させることをさらに備えることを特徴とする請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
請求項１乃至１０のいずれか１項における方法を実行する命令を備えることを特徴とするコンピュータプログラム。
【請求項１２】
請求項１１の前記コンピュータプログラムを記録しているデータ記憶媒体。
【請求項１３】
メモリとグラフィカルユーザインタフェースに結合されたプロセッサを備えるＣＡＤシステムであって、前記メモリは、請求項１１の前記コンピュータプログラムを記録していることを特徴とするＣＡＤシステム。
【請求項１４】
請求項１乃至１０のいずれかにおける前記方法によって取得可能な３次元モデル化オブジェクト。
【請求項１５】
請求項１４の前記３次元オブジェクトを格納するデータファイル。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムおよびシステムの分野に関し、より詳細には、３次元（以下「３Ｄ」と記す）モデル化オブジェクトを設計する方法、システムおよびプログラム、ならびに前記方法によって取得可能な３Ｄモデル化オブジェクトおよび上記３Ｄモデル化オブジェクトを格納するデータファイルに関する。
【背景技術】
【０００２】
オブジェクトの設計、技術開発および製造を行う多くのシステムおよびプログラムが市場に提供されている。ＣＡＤは、コンピュータ支援設計(Computer-Aided Design)の頭字語であり、例えば、オブジェクトを設計するソフトウェアソリューションに関わる。ＣＡＥは、コンピュータ支援エンジニアリング(Computer-Aided Engineering)の頭字語であり、例えば、今後出される製品の物理的な挙動をシミュレートするソフトウェアソリューションに関わる。ＣＡＭは、コンピュータ支援製造(Computer-Aided Manufacturing)の頭字語であり、例えば、製造プロセスおよび作業を規定するソフトウェアソリューションに関わる。そのようなシステムにおいて、グラフィカルユーザインタフェース（ＧＵＩ）は、この支援技術の効率に関して重要な役割を果たす。このような技術は、製品ライフサイクル管理（ＰＬＭ）システムに組み込むことが可能である。ＰＬＭは、事業拡大の概念のもと、企業が製品データを共有し、そのデータを共通プロセスに適用し、そして構想から寿命までの製品開発に関する企業知識を活用するのに資する経営戦略を指す。
【０００３】
ダッソーシステムズ社が提供するＰＬＭソリューション（登録商標ＣＡＴＩＡ、ＥＮＯＶＩＡおよびＤＥＬＭＩＡに基づく）は、製品エンジニアリング知識を組織化するエンジニアリングハブ、製造エンジニアリング知識を管理する製造ハブ、および事業を統合してエンジニアリングハブと製造ハブの両方の接続を可能にする事業ハブを提供する。このシステム全体で、製品、プロセスおよびリソースがリンクして、製品規定、製造準備、生産およびサービスを最適に推進する動的で知識ベースの製品創造および意思決定サポートを可能にする、オープンオブジェクトモデルを実現する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】欧州特許出願公開第２７５０１０７号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
現在一部のＣＡＤシステムは、例えば、写真などのモデル化される実際のオブジェクトの２次元（以下「２Ｄ」と記す）ピクチャのセットに基づいて、ユーザが３Ｄモデル化オブジェクトを設計できるようにさせる。既存の方法は、実際のオブジェクトを異なる角度から表現するいくつかの重複するピクチャをシステムに提供することを含む。その後、ユーザは、ピクチャに対して同一のポイント、ラインおよびエッジを合致させることに関与する。任意には、ユーザは、重複の一貫性を保ちながらピクチャにカーブを付加する。次のステップは、システムがオブジェクトの３Ｄバージョンを自動的に計算することである。このオブジェクトの形状は、特徴的なエッジを表現する３Ｄのポイント、カーブおよびラインのセットである。それは、ワイヤーフレーム形状となる。任意には、ユーザは、３Ｄカーブをこのワイヤーフレーム形状に付加する。ユーザは、前のステップで計算されたカーブで境界されたサーフェスを作成することに再度関与する。各サーフェスの境界カーブは、ユーザによって選択される。アプリケーションにより、ワイヤーフレームモデル、サーフェスモデルまたは立体モデルでさえも最初のピクチャから作成されることもあり得るが、この作成は、先行技術文献によって完全には明らかにされていない。
【０００６】
以上のように、この先行技術では、２つのステップにおいてユーザが関与する。第１のステップは、重複ピクチャに対するマッチングを構成することである。このステップは、不可避であると思われる。システムが３Ｄカーブを作成した後、他方のステップでは、システムがサーフェスを作成するためにユーザが境界カーブを選択する。先行技術のシステムが３Ｄカーブからサーフェスを自動的に作成することができないので、この手作業による選択が必要となる。この手作業によるプロセスは、ユーザから見れば非常に長く退屈なものである。さらに、誤って選択した結果、サーフェスのねじれまたは重複が生じる。このような病的サーフェスの特定および修復は、ユーザの責任であり、仮想３Ｄオブジェクトの工程が再度長引く。
【０００７】
以上説明した通り、本発明は、２Ｄビューに基づく３Ｄモデル化オブジェクトの設計を改善することを目的とする。
【課題を解決するための手段】
【０００８】
本発明における一態様に従って、３次元モデル化オブジェクトを設計するためのコンピュータ実装方法が与えられる。この方法は、規定されたカーブとポイントとを有する、モデル化オブジェクトの複数の２次元ビュー、および頂点を結ぶエッジと、２次元ビュー上のそれぞれカーブとポイントについてエッジと頂点間のコレスポンデンスとを備える３次元ワイヤーフレームグラフを提供するステップを備える。方法は、ワイヤーフレームグラフの各頂点に対し、頂点に対応するポイントについてそれぞれのビュー上のエッジに対応するカーブ間の局所部分半径方向順序(a local partial radial order)に従って、頂点に入射するすべてのエッジ間の局所半径方向順序(a local radial order)を関連付けるステップも備える。その後、方法は、頂点に関連付けられた局所半径方向順序に従ってワイヤーフレームグラフを閲覧することによって、エッジサイクルを決定するステップを備える。
【０００９】
方法は、以下のうちの１または複数を備えることができる。
【００１０】
ワイヤーフレームグラフの各頂点に対し、それぞれの頂点に入射するすべてのエッジ間の局所半径方向順序を関連付けるステップは、各それぞれの頂点に対し、ビュー上で規定されおよびそれぞれの頂点に入射するエッジに対応するカーブ間のそれぞれの頂点に対応するポイントについて局所部分半径方向順序をビューごとに決定するステップと、局所部分半径方向順序をすべて統合するステップと、すべての局所部分半径方向順序を統合した結果をトラバースして、それぞれの頂点に入射するすべてのエッジを含むサイクルを検出することを備えるステップであって、前記サイクルは、それぞれの頂点に関連付けられた局所半径方向順序を構成する。
【００１１】
局所部分半径方向順序は、ノードがエッジを特定するグラフおよび円弧がエッジ間のサブシーケンスを特定するグラフとして決定される。
【００１２】
ワイヤーフレームグラフの各頂点に対し、それぞれの頂点に入射するすべてのエッジ間の局所半径方向順序を関連付けるステップは、すべての局所部分半径方向順序を統合した結果をトラバースする時に、それぞれの頂点に入射するすべてのエッジを含むいくつかのサイクルの検出を導き、前記それぞれの頂点のために検出されるサイクルのうちの１つを選択するステップをさらに備えることであって、前記それぞれの頂点は、特異頂点(a singular vertex)である。
【００１３】
検出されるサイクルのうちの１つを選択するステップは、すべての特異頂点のセットに正則化プロセスを実行するステップを備えることであって、正則化プロセスは、開始特異頂点および前記開始特異頂点の開始出力エッジを選択するステップと、前記開始特異頂点においてエッジサイクルを検出するために頂点に関連付けられた局所半径方向順序に従ってワイヤーフレームグラフを閲覧するステップと、そして別の特異頂点に到達すれば、新しい開始特異頂点および／または新しい開始出力エッジを用いて正則化プロセスを反復するステップと、そうでなければ、前記開始特異頂点に対し、すべての局所部分半径方向順序を統合した結果をトラバースする時に導く、閲覧される開始出力エッジと最終エッジとの間の順序に準拠していることが検出されたサイクルを関連付けるステップと、すべての特異頂点のセットから開始特異頂点を除去するステップと、その後特異頂点がなくなるまで正則化プロセスを反復するステップとを備える。
【００１４】
ワイヤーフレームグラフを閲覧することによってエッジサイクルを決定するステップは、頂点を選択するサブステップと、選択された頂点から開始して、頂点が交わる時にそれらの頂点に関連付けられる局所半径方向順序に従ってエッジリストを形成し、エッジリストがエッジサイクルを形成するまで次に続くエッジをエッジリストに新規に追加するサブステップと、前のサブステップを反復するサブステップを備える。
【００１５】
ビューは、イメージであり、ワイヤーフレームグラフは、イメージに基づくモデル化オブジェクトの３次元構成である。
【００１６】
方法は、ビューを提供する前に、同じ物理的な製品のイメージをキャプチャし、イメージ上のカーブとポイントを規定する、ワイヤーフレームグラフおよびコレスポンデンスをさらに備え、それらによって、ビューを形成し、他方のイメージのそれぞれカーブとポイントについて各イメージのカーブとポイントのコレスポンデンスを規定し、そしてそのビューとコレスポンデンスに基づいてワイヤーフレームグラフを構成するステップであって、それによって構成されたワイヤーフレームグラフは、頂点を結ぶエッジ、およびビュー上のそれぞれカーブとポイントについてエッジと頂点間のコレスポンデンスを備える。
【００１７】
イメージは、写真である。および／または方法は、決定されたエッジサイクルに基づいてワイヤーフレームグラフとサーフェスを一致させるステップをさらに備える。
【００１８】
上記の方法によって３次元モデル化オブジェクトが取得可能であることがさらに提案される。
【００１９】
前記３次元オブジェクトを格納するデータファイルがさらに提案される。
【００２０】
上記の方法を実行する命令を備えるコンピュータプログラムがさらに提案される。このコンピュータプログラムは、コンピュータ可読記憶媒体に記録されるように適応される。
【００２１】
上記のコンピュータプログラムが記録されているコンピュータ可読記憶媒体がさらに提案される。
【００２２】
メモリとグラフィカルユーザインタフェースに結合されたプロセッサを備えるＣＡＤシステムであって、メモリは、上記のコンピュータプログラムを記録していることがさらに提案される。
【００２３】
発明の実施形態は、限定されない例として、添付図面を参照しながら説明される。
【図面の簡単な説明】
【００２４】
【図１】方法の一例のフローチャートを示す図である。
【図２】エッジサイクルの決定に関する問題を示す図である。
【図３】エッジサイクルの決定に関する問題を示す図である。
【図４】グラフィカルユーザインタフェースの例を示す図である。
【図５】クライアントコンピュータシステムの例を示す図である。
【図６】方法の例を示す図である。
【図７】方法の例を示す図である。
【図８】方法の例を示す図である。
【図９】方法の例を示す図である。
【図１０】方法の例を示す図である。
【図１１】方法の例を示す図である。
【図１２】方法の例を示す図である。
【図１３】方法の例を示す図である。
【図１４】方法の例を示す図である。
【図１５】方法の例を示す図である。
【図１６】方法の例を示す図である。
【図１７】方法の例を示す図である。
【図１８】方法の例を示す図である。
【図１９】方法の例を示す図である。
【図２０】方法の例を示す図である。
【図２１】方法の例を示す図である。
【図２２】方法の例を示す図である。
【図２３】方法の例を示す図である。
【図２４】方法の例を示す図である。
【図２５】方法の例を示す図である。
【図２６】方法の例を示す図である。
【図２７】方法の例を示す図である。
【図２８】方法の例を示す図である。
【図２９】方法の例を示す図である。
【図３０】方法の例を示す図である。
【図３１】方法の例を示す図である。
【図３２】方法の例を示す図である。
【図３３】方法の例を示す図である。
【図３４】方法の例を示す図である。
【図３５】方法の例を示す図である。
【図３６】方法の例を示す図である。
【図３７】方法の例を示す図である。
【図３８】方法の例を示す図である。
【図３９】方法の例を示す図である。
【図４０】方法の例を示す図である。
【発明を実施するための形態】
【００２５】
図１は、３Ｄモデル化オブジェクトを設計するためのコンピュータ実装方法の例のフローチャートを示している。この方法は、モデル化オブジェクトの複数の２Ｄビューを提供するステップＳ１０を備える。このビューは、ビュー上で規定されるカーブとポイントを有する。方法は、Ｓ１０において３Ｄワイヤーフレームグラフも提供する。３Ｄワイヤーフレームグラフは、頂点を結ぶエッジ、およびビュー上のそれぞれカーブとポイントについてエッジと頂点間のコレスポンデンス(corrspondences)を備える。方法は、ワイヤーフレームグラフの各頂点に対し、頂点に入射するすべてのエッジ間の局所半径方向順序を関連付けるＳ２０も備える。Ｓ２０は、頂点に対応するポイントについてそれぞれのビュー上のエッジに対応するカーブ間の局所部分半径方向順序に従って実行される。その後、方法は、エッジサイクルを決定するＳ３０を備える。Ｓ３０は、Ｓ２０において頂点に関連付けられた局所半径方向順序に従ってワイヤーフレームグラフを閲覧することによって実行される。これによって、モデル化オブジェクトの２Ｄビューに基づく３Ｄモデル化オブジェクトの設計が改善される。
【００２６】
上記に説明したとおり、背景技術は、設計される３Ｄモデル化オブジェクトの２Ｄビューに対応する３Ｄワイヤーフレームグラフのプロビジョンを考慮に入れている。しかしながら、ユーザはその後、ワイヤーフレームグラフとサーフェスを手作業で一致させなければならず、双方とも困難であり、場合によっては不明瞭になる場合がある。方法は、Ｓ３０において３Ｄワイヤーフレームグラフのエッジサイクルの決定を導く時に、プロセスのロバストオートメーション(robust automation)を可能にする。本技術分野で周知のように、規定されたエッジサイクルを有するこのような３Ｄワイヤーフレームグラフは、決定されたエッジサイクルに基づいてワイヤーフレームグラフとサーフェスを一致させることによって、サーフェスの設計を導くことができる。方法は、それを周知の任意の技術に従って行うことができるが、本実施形態における議論の主題ではない。
【００２７】
３Ｄカーブネットワークからサーフェス作成を自動化するアルゴリズムの調査は、各エッジサイクルがサーフェスの境界をカーブの閉ループとして規定する、エッジサイクルの適切なセットを見つけるという問題をもたらす場合がある。この分野の既存のアルゴリズムは、組み合わせアルゴリズムか位相アルゴリズムのいずれかである。組み合わせアルゴリズムは実際、サイクル単位で計算し、典型的には基本サイクル単位で計算する。サーフェスの重複を避けるために、最小サイクル単位が有利である。残念ながら、この計算は、以下の理由で実用的でない。アルゴリズムの複雑度は多項式によるものであり、最小サイクルの単位は単一ではなく、図２−３に示されるように、同じワイヤーフレームグラフ２０に対してエッジサイクルの２つの異なるペア（２２および２４）または（２２および２６）のように、再度重複サーフェスを導く場合がある。一方、位相アルゴリズムは、３Ｄカーブネットワーク（主にこのネットワークは「ほぼ」平面である）上で空間仮定を必要とし、産業の実情に照らして現実的でない。
【００２８】
方法は、適切な順序（Ｓ２０において関与する局所半径方向順序）で各頂点の周囲のエッジをソートすることによってこの問題を回避する。この局所的なソーティングは、各局所半径方向順序がそれぞれのビュー上のカーブ間の局所部分半径方向順序に従っている時に、Ｓ１０において提供された入力２Ｄビューを再使用することによって計算される。Ｓ３０において局所的なソーティングに従うすべての３Ｄカーブネットワークをトラバースすることは、最終的にエッジサイクルのセットを提供する。各エッジサイクルは、カーブの閉ループであり、サーフェスの境界を規定する。さらに、サイクルの隣接が知られているので、上述の一致したサーフェスによって得られた接線を計算するために、この方法によって接触制約にさらに対処できる。
【００２９】
方法により、サーフェス作成のために境界を手作業による選択する必要がなくなる。このことは、ＣＡＤシステムで仮想３Ｄオブジェクトを入手する時間を短縮し、従って生産性を改善する。さらにこの方法の結果得られるスキンは、閉有向スキンであることが保証され、今度は品質を改善し、もはや事後検査の必要がなくなったので再度時間を短縮する。標準の入力オブジェクトを処理する場合、方法のアルゴリズムの複雑度は線形であり、これは最適である。その結果、この方法の実装は、見込まれる最高の性能をＣＡＤシステムに提供する。
【００３０】
モデル化オブジェクトは、データファイル（即ち、特定の書式を有する１つのコンピュータデータ）および／またはコンピュータシステムのメモリに格納できる構造化データによって規定／記述される任意のオブジェクトである。拡大解釈すれば、「モデル化オブジェクト」という表現は、データ自体を指すことができる。方法によって取得されるモデル化オブジェクトは、Ｓ３０において決定されたエッジサイクルを有するワイヤーフレームグラフがオブジェクトを規定するデータ内にあるので、固有の構造を有する。さらに、モデル化オブジェクトは、Ｓ２０において関与する局所半径方向順序および／または局所部分半径方向順序を備えることもできるが、ひとたびエッジサイクルがＳ３０において決定されると、方法は、上記局所的な順序のいずれかまたは両方の削除を含むことができる。
【００３１】
方法は、３Ｄモデル化オブジェクトを設計する方法であり、例えば、方法のステップは、そのような設計のうちの少なくともいくつかのステップを構成する。「３Ｄモデル化オブジェクトの設計」は、３Ｄモデル化オブジェクトを作り上げるプロセスの少なくとも一部である任意のアクションまたは一連のアクションを指す。従って、方法は、３Ｄモデル化オブジェクトをゼロから作成することを備える場合もある。あるいはまた、方法は、以前に作成した３Ｄモデル化オブジェクトを提供し、その後３Ｄモデル化オブジェクトを変更することを備える場合もある。
【００３２】
３Ｄモデル化オブジェクトは、ＣＡＤモデル化オブジェクトまたはＣＡＤモデル化オブジェクトの一部であってよい。いずれにせよ、方法によって設計される３Ｄモデル化オブジェクトは、ＣＡＤモデル化オブジェクトまたは少なくともその一部、例えば、ＣＡＤモデル化オブジェクトによって占有される３Ｄ空間を表現することができる。ＣＡＤモデル化オブジェクトは、ＣＡＤシステムのメモリに格納されたデータによって規定される任意のオブジェクトである。システムのタイプにより、モデル化オブジェクトは、異なる種類のデータによって規定され得る。ＣＡＤシステムは、ＣＡＴＩＡなどの、モデル化オブジェクトのグラフィカル表現に基づいて少なくともモデル化オブジェクトを設計するのに適した任意のシステムである。従って、ＣＡＤモデル化オブジェクトを規定するデータは、モデル化オブジェクトの表現（例えば、空間の相対位置を含む幾何学的データ）を担うデータを備える。
【００３３】
方法は、方法を実行した後、モデル化オブジェクトに対応する物理的な製品の生産を備えることができる、製造プロセスに含むことができる。いずれにせよ、方法によって設計されるモデル化オブジェクトは、製造オブジェクトを表現できる。モデル化オブジェクトは従って、モデル化された立体（即ち、立体を表現するモデル化オブジェクト）とすることができる。製造オブジェクトは、部品または部品のアセンブリなどの、製品とすることができる。方法は、モデル化オブジェクトの設計を改善するので、方法は、製品の製造も改善し、従って製造プロセスの生産性が高まる。方法は、ＤＥＬＭＩＡなどの、ＣＡＭシステムを使用して実装することができる。ＣＡＭシステムは、製造プロセスおよび作業を少なくとも規定し、シミュレートして制御するのに適した任意のシステムである。
【００３４】
方法は、コンピュータ実装される。これは、方法が少なくとも１つのコンピュータ、または類似の任意のシステム上で実行されることを意味する。例えば、方法は、ＣＡＤシステムに実装されてもよい。従って、方法のステップ（例えば、ユーザによってトリガされるステップおよび／またはユーザインタラクションを伴うステップ）は、コンピュータによって、場合により完全に自動的に、または半自動的に実行される。特に、Ｓ１０は、ユーザによってトリガされ得る。方法の他のステップは、自動的に（即ち、ユーザの介入がない）、または半自動的に（即ち、例えば、結果を認証するための、少しのユーザ介入を伴う）実行され得る。
【００３５】
方法をコンピュータ実装する典型的な例は、この目的に適したシステムを用いて方法を実行することである。当該システムは、方法を実行する命令を記録しているメモリを備えることができる。換言すれば、ソフトウェアは、直ちに使用できるようにメモリにすでに用意されている。システムは従って、その他のソフトウェアをインストールせずに方法を実行するのに適している。そのようなシステムは、命令を実行するためにメモリに結合された少なくとも１つのプロセッサも備えることができる。換言すれば、システムは、プロセッサに結合されたメモリ上でコード化される命令を備え、その命令は、方法を実行する手段を提供する。そのようなシステムは、３Ｄモデル化オブジェクトを設計するのに十分なツールである。
【００３６】
そのようなシステムは、ＣＡＤシステムであってよい。システムは、ＣＡＥおよび／またはＣＡＭシステムであってもよいし、ＣＡＤモデル化オブジェクトは、ＣＡＥモデル化オブジェクトおよび／またはＣＡＭモデル化オブジェクトであってもよい。実際、ＣＡＤ、ＣＡＥおよびＣＡＭシステムは、モデル化オブジェクトがこれらのシステムの任意の組み合わせに対応するデータによって規定されるので、互いに排他的でない。
【００３７】
システムは、例えば、ユーザによる命令の実行を開始する少なくとも１つのＧＵＩを備えることができる。特に、ＧＵＩは、ユーザが、Ｓ１０のステップをトリガできるようにさせ、そしてユーザが例えば、特定の機能を開始することによってステップを行うことを決定すれば、残りの方法もトリガできるようにさせることができる。
【００３８】
３Ｄモデル化オブジェクトは、３Ｄ（即ち、３次元）である。これは、モデル化オブジェクトが、そのオブジェクトに３Ｄ表現をさせるデータによって規定されることを意味する。特に、ワイヤーフレームグラフは、３Ｄ（即ち、ワイヤーフレームグラフは平面とならない）である。３Ｄ表現は、あらゆる角度からの表現のビューを可能にさせる。例えば、３Ｄ表現されると、３Ｄモデル化オブジェクトが表示されている画面でモデル化オブジェクトを操作して、オブジェクトの軸のいずれかを、またはいずれの軸をも回転させることができる。これは特に、３Ｄモデル化されていない、２Ｄアイコンを排除し、ある物を２Ｄ視点で表現する場合でも排除する。３Ｄ表現の表示は、設計を容易にする（即ち、設計者が統計的にタスクを完了する速度を上げる）。これは、製品の設計も製造プロセスの一部であるので、産業における製造プロセスを加速させる。
【００３９】
図４は、典型的なＣＡＤシステムのＧＵＩの例を示している。
【００４０】
ＧＵＩ２１００は、標準のメニューバー２１１０、２１２０、ならびに下側と横側のツールバー２１４０、２１５０を有する典型的なＣＡＤに似たインターフェースであってよい。そのようなメニューおよびツールバーは、ユーザ選択可能なアイコンのセットを包含し、各アイコンは、当該技術分野で周知のように、１または複数の動作または機能と関連付けられている。これらのアイコンの一部は、ＧＵＩ２１００で表示される３Ｄモデル化オブジェクト２０００の編集および／または作業に適応された、ソフトウェアツールと関連付けられる。ソフトウェアツールは、ワークベンチにグループ化できる。各ワークベンチは、ソフトウェアツールのサブセットを備える。具体的には、ワークベンチのうちの１つは、モデル化された製品２０００の幾何学的特徴を編集するのに適した、編集ワークベンチである。操作において、設計者は、例えば、３Ｄモデル化オブジェクト２０００の一部を事前に選択し、その後操作（例えば、彫刻操作、または次元、色その他の変更などの、その他の操作）を開始するか、または適切なアイコンを選択することによって幾何学的制約を編集できる。例えば、典型的なＣＡＤ操作は、画面に表示される３Ｄモデル化オブジェクトの穴あけ(punching)または折り曲げ(folding)のモデリングである。
【００４１】
ＧＵＩは、例えば、表示された製品２０００に関連するデータ２５００を表示できる。図４の例において、「フィーチャーツリー」として表示されたデータ２５００、およびその３Ｄ表現は、ブレーキキャリパーおよびディスクを含むブレーキ部品に関する。ＧＵＩは、例えば、オブジェクトの３Ｄ定位を容易にし、編集された製品の操作のシミュレーションをトリガし、または表示された製品２０００のさまざまな属性をレンダリングするための、さまざまなタイプのグラフィックツール２１３０、２０７０、２０８０をさらに示すことができる。カーソル２０６０は、ユーザがグラフィックツールと対話できるようにさせるハプティックデバイスによって制御できる。
【００４２】
図５は、クライアントコンピュータシステム、例えば、ユーザのワークステーションとしてのシステムのアーキテクチャの例を示している。
【００４３】
クライアントコンピュータは、内部通信ＢＵＳ１０００に接続されたＣＰＵ（中央処理装置）１０１０を備え、ＲＡＭ（ランダムアクセスメモリ）１０７０もＢＵＳに接続されている。クライアントコンピュータは、ＢＵＳに接続されたビデオランダムアクセスメモリ１１００と関連付けられたＧＰＵ（画像処理装置）１１１０をさらに備える。ビデオＲＡＭ１１００もフレームバッファとして当該技術分野で周知である。大容量記憶デバイスコントローラ１０２０は、ハードドライブ１０３０などの大容量メモリデバイスへのアクセスを管理する。コンピュータプログラム命令およびデータを明示的に具体化するのに適した大容量メモリデバイスは、あらゆる形態の不揮発性メモリを含み、例として、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリなどの半導体メモリデバイスと、内部ハードディスクおよびリムーバブルディスクなどの磁気ディスクと、光磁気ディスクと、ＣＤ−ＲＯＭディスク１０４０とを含む。上述のメモリのいずれかは、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補完されるか、または組み込むことができる。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータは、カーソル制御デバイス、キーボードなどのハプティックデバイス１０９０も含むことができる。カーソル制御デバイスをクライアントコンピュータで用いることによって、図４を参照して述べたように、ユーザがカーソルをディスプレイ１０８０の所望の任意の場所に選択的に位置付けすることが可能となる。コンピュータモニタなどの画面によって、表示を実行できることのについて任意にサポートされることを意味する。さらに、カーソル制御デバイスは、ユーザがさまざまなコマンドを選択して、制御信号を入力できるようにさせる。カーソル制御デバイスは、制御信号をシステムに入力するいくつかの信号生成デバイスを含む。典型的には、カーソル制御デバイスをマウスにして、信号を生成するのにマウスのボタンを用いることができる。
【００４４】
システムに方法を実行させるために、コンピュータによって実行する命令を備えるコンピュータプログラムが提供され、その命令は、この目的の手段を備える。プログラムは、例えば、デジタル電子回路に実装するか、またはコンピュータハードウェア、ファームウェア、ソフトウェアまたはそれらの組み合わせに実装できる。発明の装置は、プログラマブルプロセッサによって実行される機械可読記憶デバイスに明示的に具体化されるコンピュータプログラム製品に実装でき、そして発明の方法ステップは、入力データで動作して出力データを生成することによって発明の機能を実行する命令のプログラムを実行するプログラマブルプロセッサによって実行できる。命令は、プログラマブルシステムで実行可能である１または複数のコンピュータプログラムに有利に実装でき、プログラマブルシステムは、データ記憶システムにデータおよび命令を送受信するために結合された少なくとも１つのプログラマブルプロセッサと、少なくとも１つの入力デバイスと、少なくとも１つの出力デバイスを含む。アプリケーションプログラムは、ハイレベルの手続型言語またはオブジェクト指向プログラミング言語か、または必要に応じてアセンブリ言語または機械語で実装でき、いずれにせよ、それらの言語は、コンパイラ型言語またはインタープリタ型言語であってよい。プログラムは、フルインストールプログラムまたは更新プログラムであってよい。後者の場合、プログラムは、システムが方法を実行するのに適した状態になるように既存のＣＡＤシステムを更新する。
【００４５】
前述の通り、図１の方法は、モデル化オブジェクトの複数の２Ｄビューから開始して、Ｓ３０におけるエッジサイクルの決定によって３Ｄワイヤーフレームグラフを対応させて３Ｄモデル化オブジェクトを設計する方法である。前述の通り、当該技術分野で周知の可能なアクションの中から、エッジサイクルを使用して、周知の任意の方法に従って、エッジサイクルに基づいてワイヤーフレームグラフとサーフェスを一致させることができる。特に、サーフェスは、例えば、欧州特許出願第１２３０６７２．９号明細書に記載の特定のＢ−Ｒｅｐ形式に従って境界表現（Ｂ−Ｒｅｐ）を形成でき、この開示内容は、参照により本明細書に組み込まれる。方法は、Ｓ３０においてワイヤーフレームグラフの１タイル当たり１エッジサイクル（以下「最小エッジサイクル」と呼ぶ）を決定して、エッジサイクルの全セットが最終的に全ワイヤーフレームグラフを重複せずにカバーできるようにする。
【００４６】
Ｓ１０において提供されるビューは、設計に従った３Ｄモデル化オブジェクトの任意の２Ｄ表現である。このビューは、イメージであってもよい。方法は特に、Ｓ１０の前に、以下で説明されるように、潜在的にイメージのいくつかの変更／追加を含む、ビューを構成できる同じ単一の物理的な製品のいくつかのイメージをキャプチャできる。これは、例えば、写真をキャプチャするカメラによって行うことができる。例えば、同じ物理的な製品を異なる角度から撮影でき、従って、結果となる写真は異なる視点による製品を表現する。一例において、物理的な製品の外面は、複数のビューを介して一体的に表現される。方法は、このような場合、物理的な製品の総合的な３Ｄ設計（または一般にビューによって表現される任意のオブジェクト）、即ち、複数であるがより少ない情報（２Ｄビュー）に基づく３Ｄモデル化オブジェクトを再構成または構築できる。
【００４７】
これを達成するための第１のステップは、後述の説明するやり方で複数の２Ｄビューに対応する３Ｄワイヤーフレームグラフを考慮に入れることである。３Ｄワイヤーフレームグラフを、Ｓ１０においてすでに準備して提供してもよいし、または周知の任意の技術に従った方法によって、例えば、２Ｄビューに基づいて、それよりも前のステップにおいてワイヤーフレームグラフを構成してもよい。
【００４８】
例えば、方法がキャプチャイメージ、例えば、同じ物理的な製品の写真を備える場合では、方法は、ビューを形成するためにイメージ上でカーブおよびポイントを規定することを備えることができる。換言すれば、ビューは、２Ｄカーブおよび２Ｄポイントがイメージ上で規定された標準のイメージを含むデータである。カーブとポイントは、物理的な製品のイメージ、ラインおよびコーナーがイメージ上に現れる時に、それらに従って、周知の任意のやり方で規定できる。ユーザは、前述の通り、このようなステップに関与できる。周知の自動化アルゴリズムも使用できる。その後、方法は、それぞれ他方のイメージのカーブとポイントについて、各イメージのカーブとポイント間とのコレスポンデンス（コンピュータ実装の場合、コレスポンデンスは、リンクまたはポインタなどの、２つのデータを関連付けるデータである）を規定することを備える。基本的に、物理的な製品の同じラインおよびコーナーを表現する異なるイメージのカーブおよびポイントは、そのような情報をハイライトするために、コレスポンデンスに正確に組み入れられる。これは、周知の任意の方法に従って実行できる。ユーザは、前述の通り、このようなステップに関与できる。周知の自動化アルゴリズムも使用できる。
【００４９】
最後に、Ｓ１０の前に、方法は、そのような例においてビューとコレスポンデンスに基づいて３Ｄワイヤーフレームグラフを構成する。３Ｄワイヤーフレームグラフは、方法に従って、特定の構造を有するグラフである。特に、ワイヤーフレームグラフは、すべてのグラフに頂点を結ぶエッジ、およびビュー上のそれぞれカーブとポイントについてエッジと頂点間のコレスポンデンスを備える。さらに、当該技術分野で周知のように、３Ｄワイヤーフレームグラフのエッジは、３Ｄカーブ（以下エッジとも呼ぶ）と関連付けられ、そして３Ｄワイヤーフレームグラフの頂点は、３Ｄポイントまたは位置（以下頂点とも呼ぶ）と関連付けられる。この意味では、３Ｄカーブであるエッジと、カーブがその終了で交わる場所を規定する３Ｄポイントである頂点を有する、ワイヤーフレームグラフは、３次元モデル化オブジェクトである。
【００５０】
３Ｄエッジおよび３Ｄ頂点は、（方法がワイヤーフレームグラフの構成を備える場合）以前に規定されたビューおよびコレスポンデンスに基づいて決定される。これは、当該技術分野で周知の任意の方法に従って行われてもよく、これは、ユーザインタラクションおよび／または周知の自動化アルゴリズムを伴ってもよい。従って、それ自体が周知であるものとして、イメージに包含される同じ物理的な製品についての異なる２Ｄ情報を使用して、製品に対応する３Ｄワイヤーフレームグラフを再構成するという意味で、ワイヤーフレームグラフは、イメージに基づいているモデル化オブジェクトの構成である。これらのステップの比較的簡単な実行では、物理的な製品を不透明化処理して、製品のラインおよびコーナーがはっきり定まるようにし、そして異なる２Ｄビューにおいて曖昧さをなくすようにできる。
【００５１】
方法は、ワイヤーフレームグラフの各頂点に対し、頂点に入射するすべてのエッジ間の局所半径方向順序を関連付けるＳ２０（即ち、このような関連付けを表現するデータ、例えば、リンクおよび／またはポインタが作成される）も備える。換言すれば、ワイヤーフレームグラフの頂点ごとに、頂点に入射するすべてのエッジが企図されて、そのエッジ間の（頂点に局所的な）順序が決定されて格納される。局所的な順序は、半径方向であり、エッジが頂点の周囲を回る時に交わる順序を表すという意味である。例えば、局所半径方向順序は、入射頂点を包含する平面上のエッジのプロジェクション（例えば、入射頂点におけるエッジの接線のプロジェクション）を半径方向に順序付けできる。
【００５２】
Ｓ２０は、頂点に対応するポイントについてそれぞれのビュー上のエッジに対応するカーブ間の局所部分半径方向順序に従って実行される。各ワイヤーフレームのエッジは、少なくとも１つのビュー上のそれぞれのカーブに対応する。実際、所与のビューによって適用される視点により、いくつかのエッジは、ビュー上に提示されない場合もある。しかしながら、エッジごとに、ビューがそのビュー上で規定されたエッジに対応するカーブを有するような視点の少なくとも１つのビューが存在する。次に、Ｓ２０の各企図された頂点に入射するエッジのセットを考慮に入れて、すべてのエッジは、（ビュー上で規定された対応する２Ｄカーブを経由して）それぞれのエッジの複数のビューのうちの少なくとも１つに提示される。このような各ビューに対し、「局所部分半径方向順序」と呼ばれる半径方向順序を、２Ｄであるビューの上記カーブ間で直接既定できる。Ｓ２０は、企図された頂点に入射するエッジのセットに対応するこのようなすべての局所部分半径方向順序を考慮に入れて、それに応じてすべてのエッジ間の局所半径方向順序を、自動化を可能にする系統的なやり方で（例えば、方法は、関連付けを実行する所定のアルゴリズムに従ってもよい）決定する。これを実装するやり方の例は後に提供される。従って、方法は、ワイヤーフレームグラフを決定するビューの潜在的な以前の使用に加えて、Ｓ２０においてビューを使用して、ワイヤーフレームグラフのすべての頂点に対するこのような局所半径方向順序を決定する。この意味では、ビューは、この部分のプロセスの自動化に効率的に再使用される。
【００５３】
そして、方法は、Ｓ３０のエッジサイクルを備える。Ｓ３０は、Ｓ２０において頂点に関連付けられた局所半径方向順序に従ってワイヤーフレームグラフを閲覧することによって実行される。換言すれば、グラフは、局所半径方向順序に従って一体的にトラバースされる（即ち、エッジは、ワイヤーフレームグラフのすべてのタイルが１回サイクルされるまで従う）。即ち、ワイヤーフレームグラフを閲覧する時、頂点に到着すると、Ｓ２０において頂点に関連付けられた局所半径方向順序は、どのエッジが従う（次の頂点に移行する）のかを決定するために考慮に入れられる。方法は、エッジが従う順序を格納し、そしてサイクル（既に閲覧済みの頂点に至る度に）のインスタンスを規定できる。これは、後に説明される。従って、Ｓ３０は系統的なやり方で実行可能であり、そのため（計算およびメモリリソースに関して）比較的単純な方法で、エッジサイクルの決定の重要な自動化を導くことができる。前記エッジサイクルを使用して、前述の通り、ワイヤーフレームグラフと、サーフェス、例えば、Ｂ−Ｒｅｐとを一致させることができる。
【００５４】
方法の例は、図６を参照して論じられ、図６では、論じられる例のすべての方法を表すフローチャートを示している。
【００５５】
ＣＡＤシステムのモデルの物理的な製品の例は、Ｌ字形の立体６０である。「Ｌ」の内部エッジは面取りされて丸くされている
ユーザは、Ｓ０５においてキャプチャされた、カーブとポイントが規定されているこの立体（図７−図１１）の５つの２Ｄピクチャ（例えば、写真）を、Ｓ０５においてＣＡＤシステムにフィードする。ピクチャと関連付けられるカメラ位置も例示したＣＡＤシステムに送られる。  方法の次のステップの例では、Ｓ０６およびＳ０７においてユーザが重複するピクチャに対してポイントを規定して合致させる（それに応じてカーブが合致する）。結果となるビューは、それぞれ図７−図１１の５つのピクチャに対応する数字ラベルによって図１２−図１６に示されている。ポイントは、１から１４までの番号が付いている。ポイントは、可視である形状の上に番号で区別されている。
【００５６】
この情報によって、ＣＡＤシステムは、Ｓ０８において３Ｄカーブ（エッジ）のネットワーク、換言すれば、図１７に示されているように、ワイヤーフレームグラフ１７０を計算できる。最新技術でこの３Ｄワイヤーフレームグラフを計算できる。３Ｄワイヤーフレームグラフ上の各頂点および各エッジは、それぞれが少なくとも２つの入力ピクチャ上で可視であるポイントとカーブに対応する。これは、上記オブジェクトの２以上の２Ｄビュー／ピクチャからのオブジェクトの３Ｄ位置および形を読み出すのにまさに有利である。
【００５７】
方法の例の目的は、サーフェスの境界を周知のアルゴリズムに従って潜在的に規制できるように、Ｓ３０においてこのグラフのすべての最小エッジサイクルを最終的に計算することである。方法の例の文脈において、「最小エッジサイクル」は、以下ように規定される。最初のピクチャにプロジェクトされる時に、同じ最小サイクルの有向エッジ(oriented edge)は、同じ２Ｄ面の境界カーブに対応する。
【００５８】
定義によれば、平面の単純ループ（以下「ループ」とする）は、平面を厳密に二分する平面の閉カーブである。境界されていない部分は「外側」ループと呼ばれ、境界された部分は「内側」ループと呼ばれる。
【００５９】
定義によれば、平表面は、「外部ループ」と呼ばれる１つのループと、「内部ループ」と呼ばれるループのセットを含む。外部ループは、強制的である一方、内部ループは、強制的ではない。ループは、以下の条件に従って配置される。
・すべての内部ループは、外部ループの内側に含まれる。
・どの内部ループも別の内部ループの内側に含まれない。
・ループのセットを平面グラフと見なして、Ｌをループ数とし、Ｅをエッジ数とし、Ｖを頂点数とし、Ｋをグラフの結合コンポーネント数として表記すると、以下の関係が成立する。
Ｌ＝Ｅ−Ｖ＋Ｋ
【００６０】
図１８は、そのような５つの最小エッジサイクルを示している。図１９は、最小サイクルではないサイクルを示しており、一部のエッジは、Ｌ字形立体の底表面の境界カーブである一方、他のエッジは、Ｌ字形立体の後表面の境界エッジである。
【００６１】
方法は、２つのステップを介してすべての最小エッジサイクルを計算する。第１のステップでは、Ｓ２０における適切な位相局所半径方向順序に従って各頂点の周りのエッジをソートする。第２のステップでは、Ｓ３０におけるこれらの半径方向順序付けを使用することによって３Ｄグラフをトラバースする。
【００６２】
位相局所半径方向順序が曖昧な時、これは境界の場合に起こり得るが、方法の例は、その困難を克服するための戦略（後で論じられる図６の「正則化する」ステップＳ２８を）を提供して、産業状況において合理的な効率効果をもたらす。
【００６３】
図６の方法に実装されるＳ２０の例は、図６−図２６を参照して論じられる。
【００６４】
この例において、ワイヤーフレームグラフの各頂点に対し、それぞれの頂点に入射するすべてのエッジ間の局所半径方向順序を関連付けるＳ２０は、各それぞれの頂点に対して特定のアクションを備え、それは簡単に自動化可能であり、かなり良い結果をもたらす。Ｓ２０は、各それぞれの頂点に対し、ビュー上で規定され、およびそれぞれの頂点に入射するエッジに対応するカーブ間のそれぞれの頂点に対応するポイントについて局所半径方向順序をビューごとに決定するＳ２２を備える。換言すれば、方法は、それぞれの頂点に入射するエッジに対応する２Ｄビュー上の２Ｄカーブを考慮に入れて、そしてＳ２２において各ビュー上のそのカーブの半径方向順序を決定する。その後、方法は、すべての局所部分半径方向順序を統合するＳ２４を実行する。すべての局所部分半径方向順序は従って、１つのグラフに収集される。最後に、方法は、それぞれの頂点に入射するすべてのエッジを含む（１または複数の）サイクルを検出するために、Ｓ２４の結果（統合グラフのエッジが従う）をＳ２６においてトラバースし、上記サイクルは、それぞれの頂点に関連付けられた局所半径方向順序を構成する。本例において、ノードがエッジを特定して、円弧がエッジ間のサブシーケンスを特定する（即ち、ワイヤーフレームグラフ上で互いに後続である２つのエッジが「局所部分順序の」グラフ上の有向円弧によってリンクされる）時に、局所部分半径方向順序がＳ２２において決定される。
【００６５】
頂点ｘの入射エッジの順序付けは、２つのステップを介して実行される。第１のステップでは、Ｓ２２およびＳ２４において可視であるピクチャから計算されたすべての部分的半径方向順序を頂点ｘの周りに収集する。第２のステップでは、Ｓ２６（および場合によってはＳ２８）においてそれらのすべての部分的半径方向順序から一意の局所半径方向順序を抽出する。
【００６６】
頂点ｘが与えられると、方法の例は、可視であるすべてのビューを検索する。このような各ビューに対し、方法は、ｘに入射する可視のエッジを入手し、ピクチャの平面位相によって誘発される所定の順序（例えば、ＣＣＷ：反時計回り）でこれらのエッジを頂点ｘの周りでソートし、そしてこの部分的順序を適切なデータ構造に格納する。例えば、立体６０の頂点１２は、エッジ（１２，５）、（１２，１１）および（１２，１３）に結合されている。図８および図１３のビューでは、すべての頂点がエッジと結合され、加えて可視である頂点１２が特徴付けられている。図８および図１３のビューの平面位相に従って、ＣＣＷ半径方向順序は、図２０で示されているように（（（１２，５），（１２，１３），（１２，１１））である。
【００６７】
頂点ｘに結合された同じエッジを特徴付ける別のピクチャ／ビューを選択すること（頂点１２の例における図１０および図１５のピクチャ）によって、同じ半径方向順序を算出する。これは、現実世界の３Ｄオブジェクトが有向スキンによって境界されるという事実による。この位相プロパティは、ビューを介してキャプチャされる。
【００６８】
Ｌ字形立体の例において、少なくとも１つのピクチャからの頂点のすべての入射エッジが合わさった各頂点は、可視であり、（Ｓ２４が一意に順序付けられたサイクルを導くので）特に半径方向順序の計算を簡易にする。
【００６９】
この状況は常に発生するわけではなく、図２１−図２６は、Ｓ２４およびトラバースするＳ２６がＳ２２において決定された情報を組み合わせるのに役立つ例を示している。
【００７０】
図２１−図２２は、Ｖ字ベースの錐体の２つのピクチャを示している。エッジａ，ｂ，ｃ，ｄは、錐体の最上頂点ｖに入射している。点線は、不可視のエッジであり、それらはピクチャ上に現れるはずがないが、説明の目的で表現されている。
【００７１】
図２１のピクチャにおいて、入射エッジａ，ｂ，ｄが合わさった頂点ｖは、可視であり、エッジｂは、隠れている。図２３で説明されているように、局所部分半径方向順序２３０は（ａ，ｃ，ｄ）である。
【００７２】
図２２のピクチャにおいて、入射エッジａ，ｂ，ｃが合わさった頂点ｖは、可視であり、エッジｄは、隠れている。図２４で説明されているように、局所部分半径方向順序２４０は（ａ，ｂ，ｃ）である。
【００７３】
最後に、２つの局所部分半径方向順序：順序（ａ，ｃ，ｄ）と順序（ａ，ｂ，ｃ）とは、頂点ｖに結合される。丸括弧表記から理解され得るように、開始ポイントの順序は存在しないことに留意されたい。この例では循環リストである。
【００７４】
各頂点に対し、局所半径方向順序は、Ｓ２６において局所部分半径方向順序を結合して分析することによって、Ｓ２０において取得される。Ｖ字ベースの錐体の例に戻り、頂点ｖは、局所部分半径方向順序（ａ，ｃ，ｄ）および（ａ，ｂ，ｃ）に関連付けられる。第１のステップでは、図２５に示されているように、Ｓ２６においてすべての局所部分半径方向順序を単一のグラフ２５０に統合する。部分的半径方向順序グラフの頂点ａ，ｂ，ｃ，ｄは、３Ｄワイヤーフレームグラフのエッジであり、そして部分的半径方向順序グラフの有向円弧は、頂点ｖの周りの部分的半径方向順序をキャプチャすることを理解されたい。
【００７５】
次に、結果となる有向グラフは、最大で一意のサイクル（「最大」は、サイクルがすべてのノードを含むという意味である）を含むかどうかを検査するために分析される。アルゴリズムは、任意のノードから開始するグラフトラバーサルを構築する。図２６は、ノードａから開始するグラフトラバーサルを示し、ノードａをルートとするツリー２６０を算出する。古典的には、現在の枝（枝は、ルートノードから開始する円弧のパスである）のノードが以前にビジット(visit)された場合、グラフトラバーサルは、中断される。結果となるルートツリー２６０は、図２６に示されている。
【００７６】
ツリー２６０は、以下のようにグラフのすべてのサイクルを集め、ルートノードから葉ノードへの各パスがサイクルである。この例において、１つのみの最大サイクルが存在することは明白であり、このサイクルは、（ａ，ｂ，ｃ，ｄ）であり、囲み文字で示されている。このサイクルは、方法の例によって保持された頂点ｖの周りのエッジの局所半径方向順序である。最大サイクルは一意ではなく、従って曖昧さを導くことも起こり得る。この状況は、後に詳述される。
【００７７】
図６の方法に実装されるＳ３０の例が論じられる。
【００７８】
この例において、ワイヤーフレームグラフを閲覧することによってエッジサイクルを決定するＳ３０は、頂点を選択するサブステップと、選択された頂点から開始するエッジリストを形成するサブステップと、前記サブステップを反復するサブステップを備える。換言すれば、頂点は、反復的に選択され、エッジリストは、頂点が選択される度に形成される。例えば、すべての最小エッジリストが決定されるまで選択される。
【００７９】
エッジリストの形成は、選択された頂点から開始して、頂点が交わる時にその頂点に関連付けられる局所半径方向順序に従って実行される。換言すれば、アルゴリズムが頂点で動作する時、アルゴリズムは、前記頂点に関連付けられた局所半径方向順序によって提供される第１のエッジを読み出す（例えば、方法は、局所半径方向順序のエッジを使用済みとマークして、アルゴリズムが局所半径方向順序の第１の未使用エッジを読み出せるようにする）。その後、アルゴリズムは、前記エッジに結合された他の頂点に移行する。アルゴリズムは、エッジリストがエッジサイクルを形成するまで、このように次に続くエッジをエッジリストに新規に追加する。これによって、Ｓ３０において高速で効率的な決定が可能となる。
【００８０】
図２７を参照して詳細な実施形態が与えられる。
【００８１】
図に示すように、図２７の実装において、ワイヤーフレームグラフを閲覧することによってエッジサイクルを決定するＳ３０は、以下のサブステップを備える。
・未使用とマークされた頂点ｘを選択する。
・頂点ｘから開始するエッジｅを選択することによってエッジリストＬを初期化する。
・前記頂点ｘの出力エッジｅをエッジリストＬに追加して、追加された出力エッジｅを使用済みとマークする。
・前記頂点の追加された出力エッジｅが前記頂点ｘの最後の使用済み出力エッジであれば、前記頂点ｘを使用済みとマークする。
・エッジリストがエッジサイクルを形成するまで、頂点が交わる時にその頂点に関連付けられる局所半径方向順序に従ってエッジが次に続くことによってエッジリストＬに新規に追加する。
・前のサブステップを反復し、使用済みとマークされた頂点およびエッジを廃棄する。
【００８２】
３Ｄワイヤーフレームグラフをトラバーサルする入力データは、各頂点において局所半径方向順序が合わさった３Ｄワイヤーフレームグラフである。出力データは、３Ｄグラフのすべての最小サイクルのリストである。後続の前処理は有利であり、３Ｄグラフのすべてエッジは、複製されて反対方向に向けられる。定義によれば、有向エッジは、最小サイクルで関与するのであれば「使用済み」である。頂点は、そのすべての出力エッジが最小サイクルで使用されるのであれば「使用済み」である。アルゴリズムが開始する前、すべてのエッジおよびすべての頂点は、「未使用」である。アルゴリズムの終了において、各有向エッジは、１つの最小サイクルにただ１つ関与する。グラフトラバーサルアルゴリズムは、図２７の図形内に記述されている。
【００８３】
命令「ｅ：＝Ｎｅｘｔ（ｅ，ｙ）」は、頂点の周りのエッジの局所半径方向順序を使用する。関数「ｂ＝Ｎｅｘｔ（ａ，ｖ）」は、頂点「ｖ」の周りのエッジの局所半径方向順序に従って、頂点「ｖ」から開始するエッジ「ｂ」と前のエッジ「ａ」を算出する。
【００８４】
図に示すように、方法は、局所半径方向順序を利用して、頂点およびエッジを使用済みまたは未使用とする単純だがスマートなマーキング（複製した後）を用いて、方法がすべての最小エッジサイクルの決定Ｓ３０を容易に効率的に実行できるようにする。
【００８５】
一意でない局所半径方向順序の特殊な例が図２８−図４０を参照して論じられる。
【００８６】
これは、すべての局所部分半径方向順序を統合するＳ２４の結果をトラバースするＳ２６を行う時に、それぞれの頂点に入射するすべてのエッジを含むいくつかの（異なる）サイクルの検出を導く例である。
【００８７】
一意でない局所半径方向順序は、以下の説明のとおりに発生し得る。図２８に示されるように、例示的な立体は、４面体である。４面体の４つのピクチャは、１つのみの表面が各ピクチャ上で可視であるようなやり方で与えられている。各可視である表面は、図２９に示されるように、4面体の他の３つのすべての表面を隠す。
【００８８】
頂点ｖが与えられると、各ピクチャ上で２つのみの入射エッジが可視である。頂点ｖの３つの入射エッジａ，ｂ，ｃと局所部分半径方向順序は、図３０−図３２で示しているように、局所部分半径方向順序３００、３１０および３２０を示す２つのオブジェクトの循環リストを組織化するので、それらは無意味である。
【００８９】
すべての局所部分半径方向順序の統合は、図３３で示しているように、サイクル分析が２つのサイクルの反対順序（ａ，ｂ，ｃ）および（ａ，ｃ，ｂ）を見つける有向グラフを算出する。明らかに、これは完全ではない。
【００９０】
方法の例は、頂点に（潜在的に）関連付けられたいくつかの異なる局所半径方向順序を有し、「特異」頂点と呼ばれるこのような頂点のために検出されるサイクルのうちの１つを選択するＳ２８によってこの問題を解決できる。方法は、従ってＳ３０において、使用される局所半径方向順序として１つのサイクルを選択する。方法は、このような情報を後で使用するために（Ｓ２６の後）その頂点を特異頂点としてマークすることをさらに備える。
【００９１】
特に、選択するＳ２８を間接的に実行できる。検出されるサイクルのうちの１つを選択するＳ２８は実際、すべての特異頂点のセットに（反復的である）正則化プロセスを実行することを備えることができる。
【００９２】
正則化プロセスは、開始特異頂点を選択し、そして前記開始特異頂点の開始出力エッジ（選択された特異頂点に入射するエッジ）を開始することを備える。この選択は、任意のやり方で実行されてもよい。その後正則化プロセスは、前記開始特異頂点においてエッジサイクルを検出するために、頂点に関連付けられた局所半径方向順序に従ったワイヤーフレームグラフの閲覧（即ち、エッジに関連付けられた局所半径方向順序の第１のエッジは、アルゴリズムが頂点に到着する度に従う）を備える。その後、閲覧が別の特異頂点に到達する／つながる場合、方法は、新しい開始特異頂点および／または新しい開始出力エッジを用いて正則化プロセスを反復する（閲覧が実際、曖昧さに直面し、この曖昧さを解決するために提案された方法が他のどこかで再開される）。そうでなければ（即ち、エッジサイクルが交わる他の特異頂点を用いずに検出されるのであれば）、方法は、Ｓ２６において検出され、そして開始出力エッジと閲覧された最終エッジとの間の順序に準拠しているサイクルを上記開始特異頂点に関連付けることができる（Ｓ２６において競合して検出された他のサイクルによって提供される他の潜在的な局所半径方向順序は、廃棄される）。換言すれば、保持される局所半径方向順序は、正則化中に検出されたサイクルの開始エッジと終了エッジが正しく順序付けされた（即ち、検出されたサイクルと同じ順序）半径方向順序である。その後、方法は、すべての特異頂点のセットから開始特異頂点を除去し（実際、特異頂点は、一意の局所半径方向順序がその特異頂点に保持されているように正則化されている）、その後正則化プロセスを反復する。このアルゴリズムは、特異頂点がなくなるまで実行される。例は下記で論じられる。
【００９３】
一意でない局所半径方向順序を特徴付ける頂点が実在のオブジェクトのイメージの限界であっても、その頂点を無視しないほうがよいであろう。実際、概して数がそれほど多くなければ、その頂点を処理することが可能である（明らかに、方法がワイヤーフレームグラフをうまく正則化できない場合、グラフは簡単に廃棄される）。一意でない半径方向順序を特徴付ける頂点は、以下において特異頂点と呼ばれる。
【００９４】
原理は、次の通りである。見込まれるすべての局所半径方向順序が計算されて、特異頂点ｘにおいてサイクル計算を開始すると仮定する。サイクルの開始エッジは、ｕと表記され、ｘの出力の中から任意に選択されるので、特異性は問題とならない。サイクルを計算している間にどの特異頂点にも交わらない場合、アルゴリズムは、頂点ｘの入力エッジであるエッジｖを用いて上記サイクルを終了する。従って、頂点ｘの周りの適した半径方向順序は、シーケンスｖ，ｕを特徴付ける方向順序とは反対の、シーケンスｕ，ｖを特徴付ける方向順序であることは明白である。結果的に、正しい局所半径方向順序を設定することによって頂点ｘを正則化することが可能である。その後、戦略は、局所半径方向順序を計算している間に特異頂点を特定することと、できるだけその特異頂点を正則化することである。
【００９５】
アルゴリズムの正則化は、図３４に示されているとおりである。局所半径方向順序が計算された後、すべての特異頂点は、初期のリストＬに格納される。メインループは、リストＬから特異頂点を反復的に除去することである。反復は、除去される特異頂点がなくなった時に停止される。
【００９６】
結果となるリストが空でなければ、そのリストは、回避不能な特異頂点を含み、サイクル計算は不可能である。リストが空であれば、すべての特異頂点は除去されて、すべての局所半径方向順序は一意である。以前に説明したサイクル計算は、成功する。
【００９７】
関数Ｒｅｇ（Ｌ）は、入力リストＬの各特異頂点の正則化を試みる。関数は、要素を除去してそのサイズを縮小することによってリストＬを変更する。少なくとも１つの頂点が正則化されるのであれば、新しい試みが反復を認証する他の頂点を正則化する機会が存在する。関数Ｒｅｇ（Ｌ）は、以下のとおりである。
【００９８】
Ｆｕｎｃｔｉｏｎ  Ｒｅｇ（Ｌ）
Ｆｏｒ  ｅａｃｈ  ｖｅｒｔｅｘ  ｘ∈Ｌｄｏ  ｂｅｇｉｎ
Ｉｆ  ｖｅｒｔｅｘ  ｘ  ｉｓ  ｒｅｇｕｌａｒｉｚｅｄ  ｔｈｅｎ
Ｒｅｍｏｖｅ  ｘ  ｆｒｏｍ  ｌｉｓｔ  Ｌ
Ｅｎｄ  ｉｆ
Ｅｎｄ  ｆｏｒ
Ｒｅｔｕｒｎ  Ｌ
関数Ｒｅｇ（Ｌ）による頂点ｘの正則化は、ｘ以外の通常の頂点のみを含む頂点ｘから開始するサイクルを検索することである。これは、図３５の図形内に記述されたとおりに実行される。
【００９９】
正則化は、図３６の立体３６０によって例示されている。
【０１００】
図３７−図３９は、図３６の立体３６０の３つの入力イメージを示している。隠れたラインは、明確にするために点線で表されており、イメージ上に現れるはずのないラインである。頂点４は、図３７のイメージ上では不可視である。頂点３は、図３８のイメージ上では不可視である。頂点２は、図３９のイメージ上では不可視である。
【０１０１】
計算された局所半径方向順序は、図４０に示されている。頂点１および頂点５は、半径方向順序を方向付けできない可能性があるので特異である。通常の頂点におけるサイクル計算の初期化は、どのサイクルも頂点１か頂点５のいずれかを含み、それらがかなり離れた特異頂点であるので常に失敗することに留意されたい。
【０１０２】
特異頂点のリストは、頂点１および頂点５を含む。正則化は、頂点１から開始する。エッジ（１，３）の選択は、通常頂点である頂点３を導く。頂点３における局所的な順序付けのおかげで、次のエッジは（３，４）となり、通常頂点である頂点４を導く。頂点４における局所的な順序付けのおかげで、次のエッジは（４，１）となり、頂点１においてサイクルを閉じる。明らかに、頂点１における適切な局所的な順序付けは、（１，３）、（１，４）、（１，２）であり、頂点１を通常の頂点に変更する。特異頂点５は、同じやり方で正則化される。それにより、すべてのサイクルの計算が可能である。
【０１０３】
方法のアルゴリズムの複雑度が論じられる。
【０１０４】
Ｖ、Ｅをそれぞれ３Ｄワイヤーフレームグラフの頂点数とエッジ数とし、Ｆを入力オブジェクトの表面の数とする。Ｆは、最小サイクルの数でもある。Ｅｍａｘを頂点に入射するエッジの最大数とする。Ｅｍａｘを特定の立体のＥに比例させることもできるが、実在のオブジェクトの形は少さく、定数Ｅｍａｘを用いる。以前に論じたＬ字形立体６０を
Ｅｍａｘ＝３
とし、以前のＶ字ベースの錐体を
Ｅｍａｘ＝４
とする。局所的な順序付けのアルゴリズムの複雑度は、関数Ｓｏｒｔｉｎｇ（・）がソーティングアルゴリズムの複雑度、典型的には、
Ｓｏｒｔｉｎｇ（ｎ）＝ｎｌｏｇｎ
または
Ｓｏｒｔｉｎｇ（ｎ）＝ｎ２
である
Ｖ×Ｓｏｒｔｉｎｇ（Ｅｍａｘ）
によって境界される。グラフトラバーサルのアルゴリズムの複雑度は、各エッジが２回ビジットされるので、Ｅに比例する。最後に、通常の入力オブジェクトを処理する場合、アルゴリズム全体の複雑度は、線形であり、
ａＥ＋ｂＶ
に比例することを意味する。ここでのａ，ｂは、定数である。
【０１０５】
特異性の管理は、
Ｓ×Ｖｍａｘ×Ｆ
で境界されるのであれば、正則化の複雑度のために限界的に線形性に影響を与える。ここでのＳは、特異頂点の数である。
【０１０６】
結合された位相グラフ
Ｖ−Ｅ＋Ｆ＝２（１−Ｇ）
（数Ｇは種数である）のオイラー関係のおかげで、（最小サイクルの数である）表面の数は、頂点数とエッジ数との線形結合である。これは、アルゴリズムの複雑度の観点から本方法のアルゴリズムが最適であることを証明する。
【図１】
2014235756.tif 000003
【図２】
2014235756.tif 000004
【図３】
2014235756.tif 000005
【図４】
2014235756.tif 000006
【図５】
2014235756.tif 000007
【図６】
2014235756.tif 000008
【図７】
2014235756.tif 000009
【図８】
2014235756.tif 000010
【図９】
2014235756.tif 000011
【図１０】
2014235756.tif 000012
【図１１】
2014235756.tif 000013
【図１２】
2014235756.tif 000014
【図１３】
2014235756.tif 000015
【図１４】
2014235756.tif 000016
【図１５】
2014235756.tif 000017
【図１６】
2014235756.tif 000018
【図１７】
2014235756.tif 000019
【図１８】
2014235756.tif 000020
【図１９】
2014235756.tif 000021
【図２０】
2014235756.tif 000022
【図２１】
2014235756.tif 000023
【図２２】
2014235756.tif 000024
【図２３】
2014235756.tif 000025
【図２４】
2014235756.tif 000026
【図２５】
2014235756.tif 000027
【図２６】
2014235756.tif 000028
【図２７】
2014235756.tif 000029
【図２８】
2014235756.tif 000030
【図２９】
2014235756.tif 000031
【図３０】
2014235756.tif 000032
【図３１】
2014235756.tif 000033
【図３２】
2014235756.tif 000034
【図３３】
2014235756.tif 000035
【図３４】
2014235756.tif 000036
【図３５】
2014235756.tif 000037
【図３６】
2014235756.tif 000038
【図３７】
2014235756.tif 000039
【図３８】
2014235756.tif 000040
【図３９】
2014235756.tif 000041
【図４０】
2014235756.tif 000042
【外国語明細書】
2014235756000001.pdf