(57)【特許請求の範囲】
【請求項１】
製品データ管理のための方法であって、該方法は、データ処理システムによって実施され、以下のステップを含む、すなわち、
それぞれ１つの基底ジオメトリを有する複数のエンティティ（７０２）を含むＣＡＤモデル（７００）を受け取るステップ（６０５）と、
前記複数のエンティティのうち第１のエンティティに対応する第１のオフセットペアチェーン（７０２／７０４）を識別するステップ（６２０）であって、同じオフセットペアの一部である第１のパートナエンティティ（７０４）を識別するステップを含むステップと、
前記第１のオフセットペアチェーンが強いチェーンであるか否かを判定するステップ（６３０）と、
前記第１のオフセットペアチェーンが強いチェーンである場合には、前記第１のエンティティを１つのオフセットペアの一部分としてマークするステップ（６４０）と、
マークされた前記第１のエンティティを含むＣＡＤモデルを記憶するステップ（６４５）と
を含む、製品データ管理のための方法において、
前記第１のオフセットペアチェーンを、前記第１のエンティティと前記第１のパートナエンティティの基底ジオメトリのジオメトリックタイプに基づき、強いチェーンであると判定する、
製品データ管理のための方法。
【請求項２】
前記第１のエンティティ（７０２）および前記第１のパートナエンティティ（７０４）は、前記オフセットペアチェーンを含む、
請求項１記載の方法。
【請求項３】
前記第１のオフセットペアチェーンが強いチェーンではなければ、前記システムは、該第１のオフセットペアチェーンと連結された付加的なオフセットペアを識別し（６３５）、該付加的なオフセットペアを使用して、前記判定ステップ（６３０）と前記マーキングステップ（６４０）と前記記憶ステップ（６４５）とを反復する、
請求項１記載の方法。
【請求項４】
データ処理システムであって、プロセッサと、アクセス可能なメモリとを含み、
該データ処理システムは特に以下のように構成されている、すなわち、
それぞれ１つの基底ジオメトリを有する複数のエンティティ（７０２）を含むＣＡＤモデル（７００）を受け取り（６０５）、
前記複数のエンティティのうち第１のエンティティに対応する第１のオフセットペアチェーン（７０２／７０４）を識別し（６２０）、該識別において、同じオフセットペアの一部である第１のパートナエンティティ（７０４）を識別し、
前記第１のオフセットペアチェーンが強いチェーンであるか否かを判定し（６３０）、
前記第１のオフセットペアチェーンが強いチェーンである場合には、前記第１のエンティティを１つのオフセットペアの一部分としてマークし（６４０）、
マークされた前記第１のエンティティを含むＣＡＤモデルを記憶する（６４５）、
ように構成されている、データ処理システムにおいて、
前記第１のオフセットペアチェーンは、前記第１のエンティティと前記第１のパートナエンティティの基底ジオメトリのジオメトリックタイプに基づき、強いチェーンであると判定される、
データ処理システム。
【請求項５】
前記第１のエンティティ（７０２）および前記第１のパートナエンティティ（７０４）は、前記オフセットペアチェーンを含む、
請求項４記載のデータ処理システム。
【請求項６】
前記第１のオフセットペアチェーンが強いチェーンではなければ、前記システムは、該第１のオフセットペアチェーンと連結された付加的なオフセットペアを識別し（６３５）、該付加的なオフセットペアを使用して、前記判定（６３０）と前記マーキング（６４０）と前記記憶（６４５）とを反復する、
請求項４記載のデータ処理システム。
【請求項７】
実行可能な命令が記憶された非一時的なコンピュータ読み取り可能媒体であって、前記命令が実行されると、１つまたは複数のデータ処理システムは、請求項１から３までのいずれか１項記載の方法を実行する、
非一時的なコンピュータ読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的に言えば、コンピュータ支援による設計、視覚化および製造システム("CAD system")、製品ライフサイクルマネージメント（"PLM"）システム、ならびに製品および他の項目のデータを管理する同等のシステム（これらをまとめて「製品データ管理」システムまたはＰＤＭシステムと称する）に関する。
【０００２】
発明の背景
ＰＤＭシステムはＰＬＭおよび他のデータを管理し、ＣＡＤシステムはモデリングに役立つ。この場合、改善されたシステムが望まれている。
【０００３】
発明の概要
ここで開示される種々の実施形態には、ＣＡＤモデルにおけるオフセットペアのメンバーを識別するシステムおよび方法が含まれる。本発明による方法には、各々が基底ジオメトリを有する複数のエンティティを含むＣＡＤモデルを受け取るステップが含まれる。この方法には、複数のエンティティにおける第１のエンティティに対応する第１のオフセットペアチェーンを識別するステップが含まれ、さらにこのステップには、同じオフセットペアの一部分である第１のパートナエンティティを識別するステップが含まれる。この方法には、第１のオフセットペアチェーンが強いチェーンであるか否かを判定するステップが含まれる。この方法には、第１のオフセットペアチェーンが強いチェーンである場合には、第１のエンティティを１つのオフセットペアの一部分としてマークするステップが含まれる。さらにこの方法には、マークされた第１のエンティティを含むＣＡＤモデルを記憶するステップが含まれる。
【０００４】
これまでの記載は、以下の詳細な説明を当業者がよりよく理解できるよう、本発明の特徴および技術的な利点をどちらかと言えば大雑把に略述したものである。各請求項の要旨を成す本発明のその他の特徴および利点については、以下で述べることにする。当業者であれば理解できるように、当業者は本明細書で開示する着想や特定の実施形態を、本発明と同じ目的を成し遂げるための変更または異なる構造設計のベースとして、ただちに利用することができる。さらに当業者であれば、最も広い形態で開示した本発明の着想および範囲を逸脱することなく、上述のような等価の構造を実現することもできる。
【０００５】
以下の発明の詳細な説明に入る前に、本明細書全体を通して用いられるいくつかの用語や表現について、ここで定義しておくのがよいと思われる。「を含む」および「を有する」なる表現ならびにそれらの派生語は、制限のない包含を表す。「または」なる表現は、「および／または」の意味も含む。「と関連する」および「それと関連する」ならびにそれらの派生語は、「含む」、「の中に含まれる」、「と相関した」、「を含有する」、「の中に含有される」、「に接続する」または「と接続する」、「に結合する」または「と結合する」、「と伝達可能である」、「と共働する」、「をはさむ」、「に並置する」、「のすぐ近くにある」、「に結び付けられる」または「と結び付けられる」、「有する」、「の所有物」等を意味する場合もある。さらに「コントローラ」なる用語は、ハードウェアで実装されていようと、ファームウェア、ソフトウェア、またはそれらのうち少なくとも２つの組み合わせで実装されていようと、少なくとも１つのオペレーションを制御する何らかのデバイス、システムまたはそれらの一部分を表す。さらにここで留意しておきたいのは、いずれかの特定のコントローラと結び付けられた機能を、ローカルであろうとリモートであろうと、集中させてもよいし分散させてもよい、ということである。いくつかの用語および表現に対する定義は、本明細書全体にわたって規定されるものであり、当業者であれば理解できるように、この種の定義は、大部分の事例ではないにしても数多くの事例において、ここで定義した用語および表現の以前の使用にも将来の使用にも適用される。いくつかの用語は、幅広い種類の形態を含むことができるけれども、添付の特許請求の範囲では、それらの用語が特定の形態に明確に制限されてもよい。
【０００６】
本発明およびその利点について、いっそう完璧に理解できるようにする目的で、添付の図面を参照しながら本発明について以下で説明する。なお、図中、対象が同じであれば同じ参照符号が付されている。
【図面の簡単な説明】
【０００７】
【図１】１つの実施形態を実現可能なデータ処理システムを示すブロック図
【図２】本発明の実施形態による各基底ジオメトリ間のジオメトリックオフセットの例を示す図
【図３】本発明の実施形態によるオフセットペアを示す図
【図４】本発明の実施形態による連結オフセットペアを示す図
【図５】本発明の実施形態によるオフセットチェーンの例を示す図
【図６】本発明の実施形態によるプロセスを示すフローチャート
【図７】本発明の実施形態によるＣＡＤモデルの例を示す図
【図８】本発明の実施形態による薄壁特性の例を示す図
【図９】本発明の実施形態によるパートナ消滅の例を示す図
【図１０】本発明の実施形態によるオーバラップ消滅を示す図
【図１１】本発明の実施形態による複数のチェーンにおけるエンティティを示す図
【０００８】
詳細な説明
以下で述べる図１〜図１１および種々の実施形態を用いて、本明細書における本発明の開示内容の基本原理を説明するが、それらは例示の目的で用いたにすぎず、いかなる点においても本発明の範囲を限定しようというものではない。当業者であれば理解できるように、本発明の開示内容の基本原理を、適切に構成された任意の装置において実現することができる。本発明の数多くの革新的な着想について、具体例として挙げた非限定的な実施形態を参照しながら説明する。
【０００９】
二次元（２Ｄ）または三次元（３Ｄ）のジオメトリックモデルのコンテキストの場合、システムにとって役立つことが多いのは、ユーザが保守または他の処理を当然のように望む可能性のあるオフセットジオメトリのペアを自動的に認識する能力があることである。つまり１つのモデルは、一定の距離をおいて互いにオフセットしている２つのジオメトリたとえば線分、曲線分または物体などを含むことが多い。多くのケースでは、他のオペレーションの実行中に、このようなオフセット関係がそのモデル内で保守されることが望ましい。本発明の実施形態には、この種のオフセット関係を自動的に認識して処理するためのインテリジェント型のシステムおよび方法が含まれる。
【００１０】
いくつかのシステムによれば、ジオメトリックオフセット条件の基本的な低レベル検出を、たとえば２つのジオメトリが相互間の設定距離に制約されていることを単に認識するだけで、実行することができる。さらに別のシステムによれば、本願の同一出願人による米国特許第８，２６０，５８３号明細書（United States Patent 8,260,583）に記載されているように、オブジェクトモデル内の壁フィーチャを、対向する壁面の識別によって同定することができる。なお、上記文献は、ここでの参照をもってその開示内容が本願に取り込まれたものとする。
【００１１】
ただし多くのシステムは、特定の制約なしではオフセット関係を認識することはなく、または、互いに接近していることから、オフセット関係を有するものとして過剰に多くのジオメトリを識別してしまう。オフセット「ペア」の過剰認識は、その結果として、システムとのユーザインタラクションが緩慢で非生産的なものとなってしまうことから、特に問題である。ここで開示する実施形態によれば、どのオフセットペアを認識すべきであるのかを判定するヒューリスティックなインテリジェント型の技術を採用している。
【００１２】
図１には、１つの実施形態を実現可能なデータ処理システムのブロック図が示されている。これはたとえば、特に以下で述べるようなプロセスを実行するためのソフトウェアまたは他の手段によって構築されたＣＡＤまたはＰＤＭシステムとして実現可能であり、特に、以下で説明するように、相互接続され通信を行う複数のシステムのうちのそれぞれ１つとして実現可能である。図示されているデータ処理システムには、レベル２キャッシュ／ブリッジ１０４と接続されたプロセッサ１０２が含まれており、キャッシュ／ブリッジ１０４自体はローカルシステムバス１０６と接続されている。たとえばローカルシステムバス１０６を、ＰＣＩ（peripheral component interconnect）アーキテクチャのバスとすることができる。図示の実施例ではローカルシステムバスにさらに、メインメモリ１０８とグラフィックアダプタ１１０も接続されている。グラフィックアダプタ１１０を、ディスプレイ１１１と接続することができる。
【００１３】
ローカルエリアネットワーク（ＬＡＮ）／ワイドエリアネットワーク／ワイヤレス（たとえばWiFi）アダプタ１１２などといった他の周辺機器を、ローカルシステムバス１０６と接続することもできる。拡張バスインタフェース１１４によって、ローカルシステムバス１０６が入出力（Ｉ／Ｏ）バス１１６と接続されている。Ｉ／Ｏバス１１６は、キーボード／マウスアダプタ１１８、ディスクコントローラ１２０、およびＩ／Ｏアダプタ１２２と接続されている。ディスクコントローラ１２０を記憶装置１２６と接続することができ、この記憶装置１２６を、機械で利用可能または機械で読み取り可能な任意の適切な記憶媒体とすることができ、このような記憶媒体には、以下に限定されるわけではないが、リードオンリーメモリ（ＲＯＭ）など不揮発性の変更不可能な媒体、または消去可能であり電気的にプログラミング可能なリードオンリーメモリ（ＥＥＰＲＯＭ）、磁気テープ媒体、ユーザが記録可能なタイプの媒体たとえばフロッピーディスク、ハードディスクドライブ、およびコンパクトディスク型リードオンリーメモリ（ＣＤ−ＲＯＭ）、またはディジタル多用途ディスク（ＤＶＤ）、さらに他の公知の光学的、電気的または磁気的な記憶媒体が含まれる。記憶装置１２６は、ここで述べるオペレーションに必要とされるどのようなデータであっても記憶することができ、あとで詳しく説明するようにそれらのデータには、ＣＡＤモデル１５２およびキャッシュ１５４が含まれる。
【００１４】
図示されているこの実施例では、Ｉ／Ｏバス１１６にオーディオアダプタ１２４も接続されており、サウンド再生のためにこのアダプタにスピーカ（図示せず）を接続することができる。キーボード／マウスアダプタ１１８によって、マウス、トラックボール、トラックポインタ、タッチスクリーンなどポインティングデバイス（図示せず）のための接続を行うことができる。
【００１５】
当業者であれば理解できるように、図１に描かれているハードウェアを個々の実現形態に合わせて変更できる。たとえば、図示されているハードウェアに加えて、またはその代替として、光ディスクドライブなどのような他の周辺機器を使用してもよい。図示されている実施例は、例示目的で挙げられているにすぎず、本発明に関して構造上の制限を意図したものではない。
【００１６】
本発明の１つの実施形態によるデータ処理システムには、グラフィックユーザインタフェースを用いるオペレーティングシステムが含まれている。このオペレーティングシステムによれば、同時に複数のディスプレイウィンドウをグラフィックユーザインタフェースとして表示させることができ、各ディスプレイウィンドウによって、それぞれ異なるアプリケーションに対するインタフェースが提供され、または同じアプリケーションの異なるインスタンスに対するインタフェースが提供される。ユーザはポインティングデバイスを利用して、グラフィックユーザインタフェースのカーソルを操作することができる。その際、カーソルのポジションを変更することができ、および／または、望ましいレスポンスを生じさせるために、マウスボタンのクリックなどのイベントを発生させることができる。
【００１７】
適切に変更を加えれば、様々な市販のオペレーティングシステムのうちの１つを採用することができ、たとえば、Washington州RedmondのMicrosoft社の製品であるMicrosoft Windows（登録商標）の１つのバージョンを採用することができる。オペレーティングシステムは、ここで説明する本発明に従って変更または作成される。
【００１８】
ＬＡＮ／ＷＡＮ／ワイヤレスアダプタ１１２を（データ処理システム１００の一部ではない）ネットワーク１３０に接続することができ、このネットワークを、当業者に周知のように、公用または専用のデータ処理システムネットワークあるいはそれらの組み合わせとすることができ、これにはインターネットが含まれる。データ処理システム１００は、ネットワーク１３０を介してサーバシステム１４０と通信することができ、このサーバシステムもデータ処理システム１００の一部ではないが、たとえば別個の異なるデータ処理システム１００として実装してもよい。
【００１９】
本発明の実施形態には、「現実的な」オフセットジオメトリをインテリジェントに識別して処理するためのシステムおよび方法が含まれ、全体的にフレキシブルな枠組みとして具現化することができ、これにはさらに別のヒューリスティクスを加えることができる。ここでいう「現実的な」オフセットとは、人間のユーザであるならば見なすであろうオフセットジオメトリに相応するオフセットのことを指す。種々の実施形態はそれぞれ異なるモードで動作可能であり、それらのモードには、バッチ／グローバルモードと、ローカルなセレクションドリブン型のオン・ザ・フライ・モードとが含まれる。バッチ／グローバルモードは、１つのモデルにおけるすべての現実的なオフセットを認識し、以降で利用するためにこの情報を記憶する。オン・ザ・フライ・モードは、最小限のオフセットペアだけを見つければよいインタラクティブなオペレーションのためのモードである。
【００２０】
種々の実施形態は、絶対的なまたはコンテキストに依存しない判定基準を使用することができ、それによって、あるエンティティがオフセットであるか否かの判定が、バッチモードが採用されていようがセレクションモードが採用されていようが、常に同じものとなり、どのような処理順序にも依存しなくなる。種々の実施形態において、連結された複数のオフセットのチェーンをまとめて考察することができ、このようなチェーンは、典型的なモデルにおいて人間がオフセットを判断する手法にいっそう整合している。さらに種々の実施形態によれば、この傾向に限られるものではないが、いくつかの「長くかつ薄い」ペアを含むオフセットのチェーンを優先させることができる。その理由は、それらのペアは、ＣＡＤモデリングにおいては薄壁（thin-wall）と隙間（clearance）が存在する状況において典型的だからである。
【００２１】
説明の一貫性のため、種々の用語は本明細書において特定の用法を有している。「エンティティ」（entity）とは、根底を成す基底ジオメトリ（underlying geometry）の有界部分のことを指す。二次元で実装した場合、エンティティはエッジないしは稜線（edge）であり、基底ジオメトリは曲線であり、他方、３次元で実装した場合、エンティティはフェースないしは面分（face）であり、基底ジオメトリはサーフェスないしは曲面（surface）である。
【００２２】
「ジオメトリックオフセット」（geometric offset）は、２つのエンティティの各基底ジオメトリ間に存在し、この場合、各基底ジオメトリは、すべての対応ポイントでそれぞれ他方の基底ジオメトリから等距離である。これら２つのエンティティのことをここでは「オフセットペア」と称し、ペア中の各エンティティを他方の「パートナ」と呼ぶ場合もある。二次元の実装であれば、１つのオフセットペアをたとえば、平行線、同心円、近似的スプライン曲線のオフセット、またはベース曲線と手続き的に定義されたオフセット曲線とから成るものとすることができる：
OffsetCurve(t) = BaseCurve(t) + distance * NormalToBaseCurve(t)
【００２３】
三次元の実装であれば、１つのオフセットペアをたとえば、平行平面、同心球、同軸円柱、複数の同じスパイン円環体（spine tori）、同心かつ同一角度の円錐、近似的なスプライン曲面オフセット、またはベース曲面と手続き的に定義されたオフセット曲面とから成るものとすることができる：
OffsetSurface(t) = BaseSurface(t) + distance * NormalToBaseSurface(t)
【００２４】
図２には、２本の平行線（上の行）と２つの同心円（下の行）の各基底ジオメトリ間のジオメトリックオフセットの例が示されている。この図によれば、エンティティ２０２が実線で示されている一方、それらの個々の基底ジオメトリ２０４は破線で示されている。この図には、各エンティティの基底ジオメトリがそれぞれ１つのジオメトリックオフセットを有するにしても、一方のエンティティが他方のエンティティと完全にオーバラップする可能性があること（１列目）、部分的に他方とオーバラップする可能性があること（２列目）、または、各エンティティが互いにまったくオーバラップしない可能性もあること（３列目）、が例示されている。
【００２５】
ここでいう「オーバラップ」は、２つのジオメトリックオフセットエンティティ間に少なくとも１つの投影ポイントが存在する場合、それら２つのエンティティ間に存在するものである。図２の場合、１列目と２列目では、一方のエンティティの曲面からの法線を他方のエンティティに投影させることができるが、３列目では不可能である。よって、１列目と２列目のエンティティはオーバラップ部分を有しているが、３列目のエンティティはオーバラップ部分を有していない。
【００２６】
「オフセットペア」とは、互いにオーバラップした最も近いジオメトリックオフセットである２つのエンティティのことを指す。図３には、本発明の実施形態によるオフセットペアが示されている。この例によれば、エンティティ２とエンティティ３だけがオフセットペアを成している。その理由は、これらのエンティティは、各々が他方とオーバラップした最も近いジオメトリックオフセットである唯一の組み合わせだからである。
【００２７】
さらにここでいう、２つのオフセットペアまたはオフセットペアチェーンが「連結されている」というのは、それらが同じオフセット距離を有し、かつ同じ側において各エンティティ間で隣接部分を有している、またはそれらが同じ側において１つのエンティティを共有している場合のことである。図４Ａ〜図４Ｆには、本発明の実施形態による連結オフセットペアが示されている。
【００２８】
図４Ａ〜図４Ｄには、隣接による連結の例が示されている。これらの例の各々において、エンティティ１および２は第１のオフセットペアであり、エンティティ３および４は第２のオフセットペアである。各例において、エンティティ１および４が互いに隣接しており、さらに図４Ａおよび図４Ｂの例では、エンティティ２および３が互いに隣接していることから、これらのオフセットペアは連結されている。連結のためには、一方の側の隣接で十分である。
【００２９】
図４Ｅ〜図４Ｆには、共有による連結の例が示されている。これらの例の各々において、エンティティ１と２は１つのオフセットペアであり、エンティティ１と３も１つのオフセットペアである。エンティティ２と３は各々、「共有された」エンティティ１と共に１つのオフセットペアを成していることから、これらのオフセットペアは連結されている。
【００３０】
ここでいう「オフセットチェーン」または「オフセットペアチェーン」とは、１つまたは複数の連結されたオフセットペアのことである。図５Ａ〜図５Ｃには、ＣＡＤモデル５００におけるオフセットチェーン５０２の例が実線で示されている一方、残りのエンティティは破線で示されている。図５Ａには、ただ１つのオフセットペアだけしか含まれていない最小のオフセットチェーンが示されている。図５Ｂには、複数の連結オフセットペアから成る１つの部分的なオフセットチェーンが示されている。ただしこのオフセットチェーンには、図示されているオフセットペアに連結されたオフセットペアすべてが含まれているわけではない。図５Ｃには、１つの完全のオフセットチェーンが示されており、この場合には、複数のオフセットペアから成る完全なチェーンが実線で示されている。
【００３１】
本発明の実施形態によれば、エンティティが「強い」オフセットチェーンの一部である場合には、それらのエンティティを「現実的な」オフセットと呼ぶ場合もある。１つのチェーンの強さまたは弱さを、多数の複合的な尺度基準を用いて判定することができる。
【００３２】
いくつかのケースにおいて、あるオフセットチェーンが長くかつ薄ければ、そのオフセットチェーンを「強い」と見なすことができる。この尺度基準は、１つのモデルの壁状およびスロット状の部分は、想定可能なオフセットの遠く離れたまたは短いセクションよりも強い、という人間の解釈をコーディングしたものである。種々の実施形態において、この尺度基準が個々のペアに適用され、少なくとも１つのペアが強ければ、１つのチェーンは強いと見なされる。これをチェーン全体に適用することもできる。この尺度基準は、オーバラップの長さとオフセット距離値との比である。二次元の実装の場合、オーバラップの長さは、稜線のオーバラップしている部分として計算される。三次元の実装の場合、長さは、オーバラップしているボックスの対角線などのようなオーバラップの妥当な長さの何らかの測定によって形成される。この場合、可変の閾値を使用して、ペアが強いか否かを判定することができる。一部の実施形態によれば、５：１の比（オーバラップの長さ：オフセット）が、ペアが強いと判定するための閾値として用いられるが、他の実施形態によれば他の比を用いてもよい。
【００３３】
いくつかのケースにおいて、あるオフセットチェーンが明示的にラベリングされている場合、そのオフセットチェーンを「強い」と見なすことができる。あるオフセットペアが明示的にオフセットペアであると表されているならば、そのオフセットペアは強いと見なされることになる。
【００３４】
いくつかのケースにおいて、オフセットペアが他のエンティティによって「ブロック」されているならば、オフセットチェーンをさほど「強くない」と見なすことができる。オーバラップ領域内で邪魔をするエンティティは、１つのペアの強さを弱めるものと見なすことができ、あるいはそれどころか１つのペアをまるっきり無視するものと見なすことができる。この尺度基準を用いるか否かは、アプリケーションドメインと特定のインプリメンテーションとに大きく依存する可能性がある。
【００３５】
いくつかのケースによれば、１つのオフセットチェーンを、ジオメトリのジオメトリックタイプに基づき「強い」と見なすことができる。種々のジオメトリックタイプを、それらの出現の希少さに鑑みいっそう強いと見なすことができる。たとえば、線分と平面が平行であることは多いし、円と円柱が同心であることは多いけれども、近似的なオフセットにおけるスプラインジオメトリまたは手続き的なオフセットジオメトリが、偶然にオフセットになる見込みはない。このことは、強さの尺度基準の明示的なオーバーライドとして用いることができ、またはさもなければ、認識に必要とされるオーバラップ比を減少させるために用いることができる。
【００３６】
いくつかのケースによれば、オフセットチェーンを特定の値に基づき「強い」と見なすことができる。いくつかの状況において、ユーザにより明示的に入力されたことから、または場合によってはドメイン標準値のセットが既知であるかもしれないことから、特定の絶対値が重要となる場合もある。
【００３７】
さらにいくつかのケースでは、他のインプリメンテーション仕様に基づき、あるオフセットチェーンを「強い」と見なすことができる。既述のように、本発明による技術はフレキシブルであり、どのようなドメイン仕様またはインプリメンテーション仕様であっても、ある１つのペアまたはチェーン全体を強いと推測するために用いることができる。
【００３８】
図６には、本発明の実施形態によるプロセスのフローチャートが示されている。このフローチャートはたとえば、ここで説明している１つまたは複数のＣＡＤシステム（総称的に「システム」と称する）により実行することができる。
【００３９】
システムは、各々１つの基底ジオメトリを有する複数のエンティティを含むＣＡＤモデル（６０５）を受け取る。なお、同一の基底の線分ジオメトリにおける２つの連結された線分エンティティのように、複数のエンティティが１つの基底ジオメトリを共有してもよい。ＣＡＤモデルは、ＣＡＤモデル１５２として記憶させることができる。ＣＡＤモデルは、一部のエンティティについてオフセットとチェーンの情報を蓄積することもでき、これには、どのエンティティが強いオフセットチェーンの一部であるのか、どのケースにおいてこれらのエンティティをここで述べるように再処理する必要がないか、が含まれている。
【００４０】
図７Ａおよび図７Ｂには、受け取る可能性のあるＣＡＤモデル７００の例が示されており、このモデルは、図７Ａのエンティティ７０２のように複数のエンティティを有しており、これらのエンティティは各々１つの基底ジオメトリ（図示せず）を有し、図６のプロセスを例証するために用いられる。この例は２Ｄ ＣＡＤモデル表現であるが、ここで説明するプロセスは３Ｄ ＣＡＤモデルにも適用される。
【００４１】
このシステムは、チェーンキャッシュを初期化することができる（６１０）。チェーンキャッシュは、処理されたエンティティおよび発見されたそれらのチェーンを記録することができる。チェーンキャッシュを、キャッシュ１５４として記憶することができる。
【００４２】
システムは、処理すべきエンティティを識別することができる（６１５）。このエンティティをたとえば、オン・ザ・フライ・モードであれば単一のエンティティとすることができるし、バッチモードであればＣＡＤモデルにおけるすべてのエンティティとすることができる。図７Ａの例によれば、処理すべきエンティティとしてエンティティ７０２が選択され、この場合、アプリケーションまたはユーザは、選択されたエンティティ７０２をオフセットとして処理するか否かを把握する必要がある。処理すべきエンティティを識別するステップに、処理すべき１つまたは複数のエンティティについてのユーザ選択を受け取るステップを含めてもよい。
【００４３】
処理すべき各エンティティについて、そのエンティティがキャッシュに記憶されたオフセットペアにはまだ含まれていないならば、システムは１つのオフセットペアを識別する（６２０）。ステップ６２０の一部としてシステムは、そのエンティティが１つのオフセットペアの一部であるか否かを判定し（６２０）、さらにこれには少なくとも１つのパートナエンティティを識別するステップが含まれる。現在のエンティティが１つのオフセットペアの一部でなければ、それは１つのオフセットペアチェーンの一部ではないことから、そのエンティティについてさらに後続処理する必要はない。図７Ａの例によれば、エンティティ７０４はエンティティ７０２に対するオフセットエンティティとして識別され、この場合、エンティティ７０２と７０４は、１つのオフセットペアおよび１つのオフセットペアチェーンを含む（その理由は、１つのオフセットペアチェーンはただ１つのオフセットペアを有していればよいからである）。
【００４４】
システムはこのオフセットペアを、１つのオフセットペアチェーンとしてチェーンキャッシュに追加する（６２５）。システムはキャッシュ内で、この中間的なオフセットペアと共に１つの新たなチェーンを生成することができ、または（あとで述べるようにこのプロセスが反復される場合には）、このオフセットペアチェーンを、キャッシュ内にすでに蓄積されている１つの連結オフセットペアチェーンに加えることができる。
【００４５】
システムは、オフセットペアチェーンが強いチェーンであるか否か、を判定することができる（６３０）。オフセットペアチェーンが強いチェーンであるならば、キャッシュ内においてそのオフセットペアチェーンが強いものとしてマークされる。したがってエンティティ７０２は、認識されたオフセットであり、かつキャッシュ内で強いとマークされたチェーンであると判定されたからには、オン・ザ・フライ・モードのケースでは、オフセットペアチェーンが強いチェーンとしてマークされるとただちに、処理をステップ６４０へ進めることができる。バッチモードでは通常、いずれのケースでもすべてのエンティティが処理されることになる。
【００４６】
ただし図７Ａの例の場合、エンティティ７０２と７０４との間のオーバラップは、オフセット距離に対する比が不十分であるので、初回通過の際、このチェーンは強くない。
【００４７】
システムは、キャッシュ内に蓄積されたオフセットペアチェーンと連結された付加的なオフセットペアを識別することができ（６３５）、このプロセスはステップ６２５に戻って繰り返される。連結されたオフセットペアがそれ以上存在しなければ、プロセスはステップ６４０に進む。
【００４８】
図７Ａの例の場合には初回通過後、エンティティ７０６と７０８が連結オフセットペアとして識別され、このオフセットペアは同様に強くない。さらに繰り返されて、エンティティ７１０と７１２が、連結オフセットペアとしてオフセットペアチェーンに加えられるが、それらは強くない。エンティティ７２０と７２２は、連結オフセットペアとしてオフセットペアチェーンに加えられるが、それらは強くない。エンティティ７１４と７１６は、連結オフセットペアとしてオフセットペアチェーンに加えられるが、それらは必ずしも強くない（用いられるオーバラップと距離との比に依存する）。エンティティ７１４と７１８は、連結オフセットペアとしてオフセットペアチェーンに加えられるが、それらは必ずしも強くない（用いられるオーバラップと距離との比に依存する）。ただし、あとで詳しく説明するように、エンティティ７１６および７１８とエンティティ７１４とのオーバラップが組み合わせられると、１つの強いオフセットペアチェーンが存在することが明確になる。
【００４９】
システムは、選択されたエンティティが１つの強いチェーンの一部であるならば、そのエンティティを１つのオフセットペアの一部としてマークする（６４０）。選択されたエンティティが１つの強いチェーンの一部ではなければ、そのエンティティは１つのオフセットペアの一部としてマークされない。なお、選択されたエンティティについて結果を判定する目的で、チェーン全体を探索する必要はない。図７Ａの例によれば、強いオフセットペアチェーンがいったん識別されたならば、エンティティ７０２は１つのオフセットペアの一部分としてマークされる。
【００５０】
システムは、マークされたエンティティを含むＣＡＤモデルを記憶する（６４５）。これらのオフセットペア、オフセットペアチェーン、または上述のその他の情報のいずれであっても、記憶させることができる。
【００５１】
当業者に自明のとおり、オペレーションシーケンスにより特に指示または要求がなされないかぎり、上述のプロセスにおけるいくつかのステップを省略してもよいし、同時に実施しても逐次実施してもよく、あるいは異なる順序で実施してもよい。
【００５２】
図７Ｂには、上述のようにして実施されたバッチモードプロセスの結果が示されている。バッチモードによれば、モデル７００において３つの完全なチェーンが認識されており、それらのチェーンは図７Ｂにおいて実線で示されている一方、チェーンではないエンティティは破線で示されている。この図面の場合、１つのチェーンは参照符号７３０が付された実線であり、さらに別のチェーンは参照符号７４０が付された実線であり、最後のチェーンは残りの実線である。
【００５３】
種々の実施形態によれば、システムはオーバラップ計算において、複数のエンティティの組み合わせを考慮する。図７Ａにおいてエンティティ７１６と７１８がエンティティ７１４を共有しているように、複数のオフセットペアが１つのエンティティを共有している場合、ペアすべてのオーバラップの加算によって、オフセット比の計算を改善することができる。このケースは、単一のオフセットペアの一方の側を分割した結果として発生することが多く、これはしばしば人間がこのケースを知覚する手法である。上述のように図７Ａの例の場合には、エンティティ７１４／７１６と７１４／７１８との間のオーバラップの和が、オフセットの差と比較され、その結果、強いオフセットチェーンが生成されているか否かの考察にあたり、いっそう大きい比が得られることになる。かかる組み合わせは、他の１つのエンティティを共有する２つのエンティティに限られるものではなく、１つの共通のエンティティを共有する任意の個数のエンティティを、かかるオーバラップ計算のために組み合わせることができる。つまりオーバラップを、
ｉ）第１のエンティティと、第１のパートナエンティティを共有する少なくとも１つの別のエンティティとが、第１のパートナエンティティとオーバラップしている長さの和と、
ｉｉ）第１のエンティティと第１のパートナエンティティとの間のオフセット距離と
の比に基づき、計算することができる。
【００５４】
種々の実施形態によれば、オフセットペアをフィルタリングすることもできる。一部のインプリメンテーションおよび一部のドメインについては、オフセットのいくつかの部分集合を認識するだけでもよい。たとえば、「内側」や「外側」など特定の意味合いをエンティティの各側に割り当てることができるならば、各側が一直線に並んでいる他の組み合わせが役に立たないかもしれない一方で、薄壁または内壁の隙間の特性を有するオフセットを要求することができる。図８には、薄壁特性８０２の一例が示されており、この場合、エンティティペアによってオブジェクト８２０内部に薄壁が形成されている。図８にはさらに、隙間特性８０４の一例が示されており、この場合、エンティティペアは、収容されているオブジェクト８１０と収容しているオブジェクト８２０との間でオフセットを成している。図８には、整列特性８０６の一例も示されており、この場合、エンティティペアは、オブジェクト８３０とオブジェクト８２０の境界間で整列オフセットを成している。この場合、所与のエンティティペアをフィルタリングして、かかる特性に基づきプロセスに含めるかまたは除外することができる。
【００５５】
種々の実施形態によれば、システムはパートナの消滅を処理することができる。オフセットを扱うときの一般的な問題点は、曲率半径がオフセット距離といつ等しくなり、さらにオフセット距離よりもいつ小さくなるのか、ということである。これが等しくなると、パートナエンティティが陥没して半径ゼロの点となり、それがさらに減少すると、パートナの半径は実際には負となり、モデルのリアルな部分では表現されなくなる。
【００５６】
図９には、半径が減少したときにパートナが消滅していく例が、図面の左から右に向かって示されている。左側の図面では、外側のエンティティの曲率半径Ｒは、内側のエンティティと外側のエンティティとの間の距離ｄよりも大きく、したがって内側のエンティティの曲率半径ｒはゼロよりも大きい。中央の図面では、Ｒはｄと等しくｒはゼロと等しく（ただしｄは一定保持）、したがって内側のエンティティは陥没して１つの点になっている。右側の図面では、Ｒはｄよりも小さく、したがってｒはゼロよりも小さく（ただしｄは一定保持）、内側のエンティティは可視のモデルからまるっきり消滅してしまっている。
【００５７】
これは全く一般的な状況であるため、ここで説明する種々のオフセット認識プロセスは、近隣のジオメトリを考慮することによってこのことを明示的に検出する。この状況を表現するために、仮想のパートナ（つまりモデル内に生成されるがモデル内には見えないパートナ）およびゼロまたは負の半径を有するオフセットペアが用いられ、これによってそのペアを１つのオフセットチェーンの一部とすることができる。ついでこのモデルが編集されて、大きい方の半径が増大されるか、または距離が低減されると（図面の右側から左側に向かうと）、パートナの半径は再び正になることができ、これを再びモデル内に出現させることができる。
【００５８】
種々の実施形態によれば、システムはオーバラップの消滅を処理することができる。ある候補オフセットエンティティペアの長さが、オフセット距離の値よりも短くなると、オーバラップが消滅することになる。
【００５９】
図１０Ａおよび図１０Ｂには、本発明の実施形態によるオーバラップ消滅が示されている。この場合、エンティティがオフセット値に比べて小さいときに、オーバラップが消滅する例である。図１０Ａの例について述べると、一番左側の図においてオフセットチェーンのエンティティ１００２と１００４とがオーバラップしている。この場合、エンティティ１００２と１００４は次第に小さくなると見なされているので、一番右側の図ではオーバラップが見えなくなるように、オーバラップが消滅する。距離ｄが一定であるとするならば、ユーザは一番左側のケースについては、まだオフセットペアチェーンとして見なしたがることが多い。
【００６０】
このことに対処するため、システムは「オーバラップ」の要求を、オフセット距離に至るまでの隙間を含むものと定義することができる。図１０Ｂには、オーバラップに所定の距離の隙間が存在する場合にオフセットペアを許容する一例が示されている。このケースでは、エンティティ１００６と１００８との間のオーバラップにおける隙間は、オフセットの距離ｄよりも小さく、したがってシステムはオフセットペアを識別するときに、それらをオーバラップしているものと見なすことができる。
【００６１】
なお、このことは必ずしも、多少なりとも強さの尺度が変更されるという意味を含むものではない。なぜならばこのようなペアは、一般的にはいまだ強いとは見なされないはずだからである。この場合、基本的なチェックではペアが含まれていればよく、チェーンのどこか他の個所で強さを求めることができれば十分である。
【００６２】
種々の実施形態において、このシステムは明示的なラベルを処理することができる。あるペアをオフセットペアと見なすべきであるとする明示的なラベルが存在するならば、少なくともローカルな編集用途においては一般的に、オーバラップの要件または最も近くで隣り合っているという要件を満たしているか否かにかかわらず、処理中にそのペアがオフセットペアとして含まれることが要求される。なお、ここで言及した明示的なラベル付けを、他の点で有効なオフセットペアの強さの尺度を強めるものと混同しないよう留意されたい。
【００６３】
種々の実施形態において、システムは同一のエンティティに対し複数のチェーンを処理することができる。このアルゴリズムの枠組みは、複数のチェーンにおいて複数のエンティティを処理する能力があるものである。図１１には、複数のチェーンにおけるエンティティが示されている。たとえばこの図の場合、第１のオフセットチェーンは、エンティティ１１０２／１１０６／１１１２とそれらのパートナエンティティ１１０４／１１０８／１１１０とを含むものとすることができる。また、第２のオフセットチェーンは、エンティティ１１０４とパートナエンティティ１１１０とを含むものとすることができる。このことは、第１のオフセットチェーンにおける各ペア間のオフセット距離が、第２のオフセットチェーンにおける各ペア間の距離と等しいか否か、または異なっているか否か、によらずに成り立つ可能性がある。好ましくはこのような包含は、オフセットペアが過剰に見つかるのを回避するために制限され、したがってシステムは、インプリメンテーション固有のヒューリスティクスと、ドメイン知識とを使用して、過剰なペアが見つかるのを制限することができる。
【００６４】
種々の実施形態によれば、特有の長くかつ薄いシード（seeds）を含む複数のペアの発見によって、チェーン全体が認識されることになり、単独の状態では弱いであろうオフセットとしての複数のペアの発見は、チェーンの連結ゆえにオフセットと見なされる。種々の実施形態によれば、相互にオーバラップしている最も近いオフセットであるオフセットペアを見つけることができ、遮るエンティティが存在するならば、オフセットペアの発見を回避することができる。
【００６５】
種々の実施形態は、オフセットペア条件の基本的な検出、望ましくないオフセットペアのフィルタリング、チェーンを構築する連結の種類、およびペアおよびチェーン全体の強度インジケータに含められる、ここで開示した技術の枠組みの中で、ドメイン知識とインプリメンテーション拡張を使用することができる。
【００６６】
さらに当業者に理解できるとおり、簡単かつ明瞭にするため、本願の開示内容による使用に適したあらゆるデータ処理システムの構造および操作を完全に描いたまたは説明したわけではない。そうではなく、データ処理システムのうち、本願の開示内容に特有のところだけを、または本願の開示内容の理解に必要なところだけを描いて説明したにすぎない。データ処理システム１００の構造および操作のその他の部分は、この分野で周知の現在行われている様々な実装形態および実施手法の任意のものに適合させることができる。
【００６７】
ここで特に述べておきたいのは、本願の開示内容には、完全に機能的なシステムに関連した説明が含まれているけれども、当業者に自明であるとおり、本願の開示内容におけるメカニズムの少なくとも一部分は、機械で使用可能な媒体、コンピュータで使用可能な媒体、またはコンピュータで読み取り可能な媒体に記憶された命令として、任意の種類の形態で配布可能なものであること、さらに本願の開示内容は、特定のタイプの命令、信号担体または記憶媒体が使用されようとも、そのような配布物を実際に実行するために等しく適用されることである。機械で使用可能／読み取り可能な媒体、またはコンピュータで使用可能／読み取り可能な媒体の例として、以下のものが含まれる：リードオンリーメモリ（ＲＯＭ）など不揮発性で変更不可能にコーディングされた媒体、または消去可能であり電気的にプログラミング可能なリードオンリーメモリ（ＥＥＰＲＯＭ）、ならびにユーザが記録可能なタイプの媒体たとえばフロッピーディスク、ハードディスクドライブ、およびコンパクトディスク型リードオンリーメモリ（ＣＤ−ＲＯＭ）、またはディジタル多用途ディスク（ＤＶＤ）。
【００６８】
これまで本発明の実施例について詳しく説明してきたが、当業者であれば理解できるように、最も広い形態で開示した本発明の着想および範囲を超えることなく、様々な変更、置き換え、変形ならびに本明細書で開示した改善を行うことができる。
【００６９】
本願の記載内容のいずれも、何らかの特定の部材、ステップまたは機能が特許請求の範囲に含まれなければならない必須の要素である、という趣旨で読まれるべきではない。本発明の範囲は、特許付与された請求項によってのみ定められるものである。しかも、厳密な語「〜のための手段」の次に分詞が続かないのであれば、これらの請求項のいずれも、米国特許法第１１２条第６項が適用されることを意図したものではない。
【図１】
0006320561.tif 000002
【図２】
0006320561.tif 000003
【図３】
0006320561.tif 000004
【図４Ａ】
0006320561.tif 000005
【図４Ｂ】
0006320561.tif 000006
【図４Ｃ】
0006320561.tif 000007
【図４Ｄ】
0006320561.tif 000008
【図４Ｅ】
0006320561.tif 000009
【図４Ｆ】
0006320561.tif 000010
【図５Ａ】
0006320561.tif 000011
【図５Ｂ】
0006320561.tif 000012
【図５Ｃ】
0006320561.tif 000013
【図６】
0006320561.tif 000014
【図７Ａ】
0006320561.tif 000015
【図７Ｂ】
0006320561.tif 000016
【図８】
0006320561.tif 000017
【図９】
0006320561.tif 000018
【図１０Ａ】
0006320561.tif 000019
【図１０Ｂ】
0006320561.tif 000020
【図１１】
0006320561.tif 000021