(57)【要約】【課題】オブジェクト、ツールを用いグラフィック化されたオブジェクトのシミュレートされた操作のグラフィック表現を生成する方法を提供する。【解決手段】オブジェクトの要素に対応する複数個のデータ構造をメモリに格納し、データ構造の各々がメモリ内の各それぞれの要素の位置及び他の記憶位置に対する複数個のポインタを示すデータ表現を有し記憶位置が複数の要素で関連している工程、複数のデータ構造中の第１データ構造のポインタの１つと関連するメモリ内の記憶位置に複数のデータ構造中の第２データ構造の値を格納しかつ複数のデータ構造中の第２データ構造のポインタの１つと関連するメモリ内の記憶位置に複数のデータ構造中の第１データ構造の値を格納し第１及び第２要素のオブジェクト内でのリンクを示す第２格納工程、データ構造の内容に基づきオブジェクトのグラフィック表現をディスプレイ上に表示する工程を含む。【選択図】図１０
2008251044.tif 000002
【特許請求の範囲】
【請求項１】
表示のためのオブジェクト、およびシミュレートされたツールを用いてコンピュータのビデオディスプレイ上でのグラフィック化されたオブジェクトのシミュレートされた操作のグラフィック表現を生成するコンピュータにおけるグラフィック表現生成方法であって、
前記オブジェクトのそれぞれの要素に対応する複数個のデータ構造をメモリに格納する工程であって、前記データ構造の各々が、前記メモリ内のそれぞれの要素の位置及び他の記憶位置に対する複数個のポインタを示すデータ表現を有し、前記記憶位置が前記複数の要素の中の他の要素と関連しているものと、
前記複数のデータ構造の中の第１のデータ構造の前記ポインタの１つと関連する前記メモリ内の記憶位置に前記複数のデータ構造の中の第２のデータ構造の値を格納し、かつ、前記複数のデータ構造の中の前記第２のデータ構造の前記ポインタの１つと関連する前記メモリ内の記憶位置に前記複数のデータ構造の中の前記第１のデータ構造の値を格納して、前記第１及び第２要素が前記オブジェクトの内部で一緒にリンクされていることを示す第２格納工程と、
前記データ構造の内容に基づいて前記オブジェクトのグラフィック表現を前記ビデオディスプレイ上に表示する工程と、
を有することを特徴とするコンピュータにおけるグラフィック表現生成方法。
【請求項２】
前記第２格納ステップが更に、前記複数のデータ構造の中の前記第１のデータ構造の前記ポインタの中の前記ポインタと関連する前記メモリの前記記憶位置、第１の値を上書きし、前記複数のデータ構造の中の前記第２のデータ構造の前記ポインタの中の前記ポインタと関連する前記メモリの前記記憶位置、第２の値を格納する工程を有し、以って前記第１及び第２の値によって、それぞれの要素が前記要素のもう一方の要素とリンクされていないことが示されることを特徴とする請求項１に記載のコンピュータにおけるグラフィック表現生成方法。
【請求項３】
前記第１及び第２の値が前記要素の他方の要素を識別しないＮＵＬＬ値を有することを特徴とする請求項２に記載のコンピュータにおけるグラフィック表現生成方法。
【請求項４】
前記複数のデータ構造の中の第１のデータ構造の前記ポインタの中の１つと関連する前記メモリの記憶位置に前記要素のカラーを示すデータを格納する工程を更に含むことを特徴とする請求項１に記載のコンピュータにおけるグラフィック表現生成方法。
【請求項５】
前記要素の前記カラーを示す前記データが更に前記カラーを定義する赤、緑、青を表現する値を有することを特徴とする請求項４に記載のコンピュータにおけるグラフィック表現生成方法。
【請求項６】
前記ポインタの１つと関連する前記メモリの記憶位置に力の閾値を示す値を格納する工程と、
前記オブジェクトに対する力のアプリケーションをシミュレートし、前記ポインタの中の少なくとも１つに対応するそれぞれのリンク上にシミュレートされた力を生成する工程と、
前記ポインタの中の前記少なくとも１つに対応するそれぞれのリンクに対してそれぞれのリンク上のシミュレートされた力が力の閾値を超えている場合、前記複数のデータ構造の少なくとも前記第２のデータ構造の前記値を前記メモリから除去する工程と、
を更に有することを特徴とする請求項１に記載のコンピュータにおけるグラフィック表現生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は立体画像グラフィクスに関し、特に、コンピュータグラフィックによる立体の任意の切断経路に沿った切断、任意の形状の立体の任意の面での結合、及び、変形可能な立体モデルが引き裂かれるときの断裂(tearing)のモデル化のための、コンピュータにおけるグラフィック表現生成方法に関する。
【背景技術】
【０００２】
コンピュータによるシミュレーションは多くのことに適用可能である。そのような適用例の一つとして外科手術シミュレーションがある。外科手術の訓練、教育、外科手術計画に、また、内部手術の補助としてコンピュータによる外科手術シミュレーションを適用することができる。医学教育や医学上の訓練において外科手術シミュレーションを用いることによって、解剖用死体標本に関連するコストを削減することができ、また、実地の場で通常遭遇する様々な種類の病理学的症状や合併症に関する経験が与えられ、訓練の手順を繰り返したりやり直したりすることが可能となる。外科手術計画においては、シミュレータによって患者に対する特定の解剖を含む外科手術の難しい手順又は計画のリハーサルを行うことができる。内部手術においては、コンピュータ・モデリングを用いることにより、患者の解剖についてより全体的な視野でもって狭い外科的分野を広く見渡すことにより手術の進み具合を補助し、例えば、危害が患者に生じ得る領域への侵入に関して警告することにより将来の外科医にガイダンスを提供することもできる。
【０００３】
ユーザーに対して有用なフィードバックを提供するために、外科用シミュレータは適切なリアリズムを与えなければならない。組織モデルに対する操作が行われたときリアルな反応がなければならない。外科分野について与えられる画像は注目せずにはいられないほどリアルでなければならない。触覚あるいは力によるフィードバックは実生活で経験する力に似せなければならない。なぜなら、触感は外科手術の重要な手がかりを与えるものであるからである。これらの要件は外科用シミュレータに重要な要求を課すものとなり、特に、軟組織変形、組織切断、断裂あるいは結合のシミュレーションを行う肉体的にリアルなモデル化技術が要求される。
【０００４】
コンピュータ・モデリングでは、物理的オブジェクトのデジタルモデルは現実世界の行動をシミュレートしたり、予測したりするために操作される。物理学をベースにしたグラフィクスでは、物理法則が用いられ、オブジェクトモデルや柔オブジェクトの変形の間の衝突のような相互作用がモデル化される。物理的にもっともらしいということは、厳密に言えば正確ではないにも拘らず物理的モデリングがリアルである外観を備えていることを意味する。物理的にもっともらしいシミュレーションは、物理的に写実的なシミュレーションに比べると計算上はずっと大まかではあるが、アニメーションや、ハイレベルのデザインや教育のような分野で適用するにはそれで十分であることが多い。
【０００５】
面ベースのグラフィクスでは、グラフィックオブジェクトは多角形やスプライン曲線パッチのような一組の連続した面要素によって表現される。面ベースのオブジェクトの切断のモデリングは難しい。その理由は、新しい連続面を切断経路に沿って描かなければならないからである。モデルの任意の位置で切断を行う場合、切断平面の作図は極めて困難になる。更に、面モデルではオブジェクト内部が表現されないので切断が写実的に見えるように切断面にわたって切断箇所の内部構造を作り上げなければならない。
【０００６】
三次元グラフィクス(立体グラフィクス)では、オブジェクトはサンプル値データ要素の三次元配列として表現される。立体モデルではオブジェクト面とオブジェクト内部の双方が表現される。オブジェクト内部が表現されるので、立体変形をモデル化することが可能である(非特許文献１：S. Gibson著「3D ChainMail、立体変形高速アルゴリズム」、Proc. CVRMed/MRCAS 97,pp. 369-378, Grenoble, Fr. 1997参照)。また、内部の詳細を利用して切断経路に影響を与えたり(例えば、切断経路がオブジェクト内部の高密度の構造に行き当たった場合)、切断によって曝される面の外観を修正することもできる。
【０００７】
非特許文献２：Galyean & Hughes著「彫刻：  対話式立体モデル化技術」、Proc. SIGGRAPH 91, Las Vegas, NV, pp. 267-274, July, 1991; 非特許文献３：S. Wang & A. Kaufman著「立体彫刻、Proc. 1995 対話式３Ｄグラフィクスシンポジウム」、Monterey, CA, pp. 151-156, May, 1995；  及び非特許文献４：R. Avala及びL. Sobierajski著「立体の視覚化のための触覚による対話的方法」、Proc. IEEE Visualization 96, pp.197-204, San Francisco, CA, October, 1996のような人々によって立体の彫刻が行われている。これらの方法では、オブジェクトは、規則的間隔で配置された黒化度値(明暗度値)(intensity values)の静的配列によって表現され、この黒化度は組織の厚さ又はその標本点における材料の量に対応する。(例えば、黒化度１を固体材料又は''フル''標本に該当させ、黒化度０を自由空間に該当させることができる。)立体の彫刻又は編集は彫刻ツールの近くの標本の黒化度値を変更することによって行う。例えば、''彫刻''はツールの下にある配列の要素の黒化度値をゼロにセットする。''溶解''は、ツールが配列要素に対して使われる時間に比例してツールの下でボクセルの黒化度を減少させ、''吹き付け''はツールの下で最大黒化度１までボクセルの黒化度を増大させることにより材料を追加する。
【０００８】
これらの立体彫刻手法には立体編集及び幾何学的デザインに適用できる可能性がある一方で、黒化度値の結果として生じる配列には物体らしさという物理的感覚が欠けていることに留意することは重要である。ひとたび立体の残りの部分から配列のピースが''彫刻''され取り除かれると、それらのピースは個々のオブジェクトとして操作することはできなくなる。材料が創出され跡形もなく分解される結果これらを用いても実際の彫刻を写実的にモデル化したものとはならなくなる。更に、変形可能な材料を彫刻するためにこの表現をどのように拡大できるかがはっきりしない。
【０００９】
有限要素法を用いて変形可能なオブジェクトをモデル化することができる。三次元的方法と同様、有限要素法では三次元メッシュ節点が用いられる。離散モデル中のノード数に比例する次元数をもつ同時的常微分方程式の大きな系を解くことによって、これらのシステムの力学を予測することができる。有限要素法は物理的に写実的な行動を与えるが、計算量は膨大になる。更に、三次元メッシュの任意の切断にはモデルの再メッシュ化が必要となる。この再メッシュ化は正確なシミュレーションにとって必要である。なぜなら、より小さなメッシュが高い応力点(例えばナイフの先端)で必要となるからである。
【００１０】
非特許文献５：「非弾性変形モデリング：  粘弾性、可塑性、フラクチャ」(Proc. SIGGRAPH 88, コンピュータグラフィクス、Vol. 22, pp. 269-278, 1988)において、TerzopoulosとFleischerは、変形可能組織の離散メッシュ表現のフラクチャリングをモデル化している。しかし、彼らのモデルでは、フラクチャリングは、２つのリンクされた要素間の連結をはっきりと除去する本発明の主題とは異なり、材料特性重みづけ関数を特定のメッシュノードにおいてゼロにする結果から生じるものである。
【００１１】
立体のモデリング、切断又は断裂は面ベースの表現については難しい。それは、任意のナイフ経路に沿って新しい面を作図しなければならないからである。更に、面ベースのモデルはオブジェクト内部が表現されていないので、これらのモデルによる切断又は断裂には、切断面のカラーや手触りを出すために内部構造を作り上げる必要がある。
【００１２】
【非特許文献１】S. Gibson著「3D ChainMail、立体変形高速アルゴリズム」、Proc. CVRMed/MRCAS 97,pp. 369-378, Grenoble, Fr. 1997
【非特許文献２】Galyean & Hughes著「彫刻：  対話式立体モデル化技術」、Proc. SIGGRAPH 91, Las Vegas, NV, pp. 267-274, July, 1991
【非特許文献３】S. Wang & A. Kaufman著「立体彫刻、Proc. 1995 対話式３Ｄグラフィクスシンポジウム」、Monterey, CA, pp. 151-156, May, 1995
【非特許文献４】R. Avala及びL. Sobierajski著「立体の視覚化のための触覚による対話的方法」、Proc. IEEE Visualization 96, pp.197-204, San Francisco, CA, October, 1996
【非特許文献５】Terzopoulos, Fleischer：「非弾性変形モデリング：粘弾性、可塑性、フラクチャ」(Proc. SIGGRAPH 88, コンピュータグラフィクス、Vol. 22, pp. 269-278, 1988)
【発明の開示】
【発明が解決しようとする課題】
【００１３】
従来の立体彫刻方法すなわちコンピュータにおけるグラフィック表現生成方法ではオブジェクトは黒化度値を示す静的三次元配列であると仮定されている。材料の追加又は除去を表現するためにこれらの黒化度値は増減されるが、切断、断裂又は結合という行動を物理的にシミュレートする方法はない。創出され、切り離され、結合されるオブジェクトには物理学ベースのモデリングに使用できる物理的性質は備わっていない。
【００１４】
本発明によって、任意の面におけるオブジェクトの切断、オブジェクトの断裂又はオブジェクトの結合のような、オブジェクトとの相互作用を示す物理的にもっともらしいモデルを生成するコンピュータにおけるグラフィック表現生成方法を提供する。
【００１５】
オブジェクト表現の操作を容易にする手法とともにオブジェクト表現を開示し、オブジェクトの切断、断裂及び結合のような手順をモデル化することができるようにする。これらの行動のシミュレーションは物理的に写実的なモデリングにとって重要であり、外科的シミュレーション、アニメーションや縫製用衣服のモデリングのような分野に適用できる。
【課題を解決するための手段】
【００１６】
本発明は、表示のためのオブジェクト、およびシミュレートされたツールを用いてコンピュータのビデオディスプレイ上でのグラフィック化されたオブジェクトのシミュレートされた操作のグラフィック表現を生成するコンピュータにおけるグラフィック表現生成方法であって、前記オブジェクトのそれぞれの要素に対応する複数個のデータ構造をメモリに格納する工程であって、前記データ構造の各々が、前記メモリ内のそれぞれの要素の位置及び他の記憶位置に対する複数個のポインタを示すデータ表現を有し、前記記憶位置が前記複数の要素の中の他の要素と関連しているものと、前記複数のデータ構造の中の第１のデータ構造の前記ポインタの１つと関連する前記メモリ内の記憶位置に前記複数のデータ構造の中の第２のデータ構造の値を格納し、かつ、前記複数のデータ構造の中の前記第２のデータ構造の前記ポインタの１つと関連する前記メモリ内の記憶位置に前記複数のデータ構造の中の前記第１のデータ構造の値を格納して、前記第１及び第２要素が前記オブジェクトの内部で一緒にリンクされていることを示す第２格納工程と、前記データ構造の内容に基づいて前記オブジェクトのグラフィック表現を前記ビデオディスプレイ上に表示する工程と、を有することを特徴とするコンピュータにおけるグラフィック表現生成方法にある。
【００１７】
また、前記第２格納ステップが更に、前記複数のデータ構造の中の前記第１のデータ構造の前記ポインタの中の前記ポインタと関連する前記メモリの前記記憶位置、第１の値を上書きし、前記複数のデータ構造の中の前記第２のデータ構造の前記ポインタの中の前記ポインタと関連する前記メモリの前記記憶位置、第２の値を格納する工程を有し、以って前記第１及び第２の値によって、それぞれの要素が前記要素のもう一方の要素とリンクされていないことが示されることを特徴とするコンピュータにおけるグラフィック表現生成方法にある。
【００１８】
また、前記第１及び第２の値が前記要素の他方の要素を識別しないＮＵＬＬ値を有することを特徴とするコンピュータにおけるグラフィック表現生成方法にある。
【００１９】
また、前記複数のデータ構造の中の第１のデータ構造の前記ポインタの中の１つと関連する前記メモリの記憶位置に前記要素のカラーを示すデータを格納する工程を更に含むことを特徴とするコンピュータにおけるグラフィック表現生成方法にある。
【００２０】
また、前記要素の前記カラーを示す前記データが更に前記カラーを定義する赤、緑、青を表現する値を有することを特徴とするコンピュータにおけるグラフィック表現生成方法にある。
【００２１】
また、前記ポインタの１つと関連する前記メモリの記憶位置に力の閾値を示す値を格納する工程と、前記オブジェクトに対する力のアプリケーションをシミュレートし、前記ポインタの中の少なくとも１つに対応するそれぞれのリンク上にシミュレートされた力を生成する工程と、前記ポインタの中の前記少なくとも１つに対応するそれぞれのリンクに対してそれぞれのリンク上のシミュレートされた力が力の閾値を超えている場合、前記複数のデータ構造の少なくとも前記第２のデータ構造の前記値を前記メモリから除去する工程と、を更に有することを特徴とするコンピュータにおけるグラフィック表現生成方法にある。
【発明の効果】
【００２２】
現在開示されているモデル化技術では、隣接要素間でリンクを連結することで立体モデルを大きくしている。対話式オブジェクト操作手法はこの表現を用いて、切断ツールや結合ツールのようなシミュレートされたツールによって横断経路に従ってリンクを創出したり破壊することが可能になる。これらの手法によってオブジェクトの切断、断裂及び結合の物理的にもっともらしいシミュレーションが可能になる。
【００２３】
オブジェクト表現の中に内部構造が格納されているので、立体の表現を用いて切断又は断裂によって顕になる内部構造を作りだす必要はない。リンクされた要素の配列としてオブジェクトを表現することによって、オブジェクトは実際の材料の持つ特性を帯びることが可能になる。すなわち、力が加わったときオブジェクトを変形し、切り離されたオブジェクトを２つの別々のオブジェクトとして個々に操作し、指定限界を超えてオブジェクトが引き伸ばされて分離したときオブジェクトの断裂を操作し、別々のオブジェクトを任意の点又は面で結合することが可能となる。
【発明を実施するための最良の形態】
【００２４】
本発明は、関連図面とともに以下の本発明の実施の態様を参考にすることにより十分に理解できるであろう。
【００２５】
図１でわかるように、グラフィックオブジェクトの切断、断裂及び結合のためのシステムには、シミュレーションを視覚化するためのコンピュータモニター２、モニター２に表示されたオブジェクト８を制御するためのキーボード４及び／他の入力装置６の少なくともいずれか一方、切断ツール１０のような処理ツール１０及びコンピュータ１２が含まれる。
【００２６】
図２の(ａ)は、グラフィックツール１８を使用したトレーシング経路１６に沿うグラフィックオブジェクト１４の切断を例示する。図２の(ｂ)は、グラフィックツール１８でスライス後の図２の(ａ)のオブジェクトを例示する。面ベースのオブジェクトの場合結果としてそれぞれ第１及び第２の中空のピース２０と２２が生じるが、そのピースに対してオブジェクトの切断の結果として創出される面を生成しなければならない。
【００２７】
図３の(ａ)に、隣接面パッチ、例えばパッチ２６、２８、３０により面ベースのオブジェクト２４が表現されている。グラフィック切断ツール３４によって経路３２に沿ってこのオブジェクトがスライスされると図３の(ｂ)に示すように新しい目に見える面３６を創出しなければならない。この新しい面３６は、グラフィックツール３４の切断経路３２によって決定される面上にある新しい隣接面パッチ、例えば図３の(ｃ)に示す３８、４０、４２によって定義される。この切断面に対して良好な一組の面パッチを定義することは難しい。更に、この切断によって、例えば図３の(ｂ)に示す４４、４６のような小さな不規則な次善の面パッチピースが元の古いオブジェクト面上に残る可能性がある。更に、オブジェクトの内部が元のオブジェクトに表現されていないので、切断面の面パッチのカラー及び他の特性を作り出さなければならない。
【００２８】
図４では、彫刻用立体データのための先行技術による方法は、そのデータが三次元要素からなる規則的な、静的ブロック４８、例えば三次元ブロック５０、５２、５４、５６及び５８(各要素に黒化度値(明暗度値)が割り当てられている)から成ることを前提としている。黒化度１はその要素がフルである(例えば要素５０及び５２)ことを意味し、一方黒化度ゼロはその要素がエンプティである(例えば要素５４と５６)ことを示す。０と１との間の黒化度は部分的フル要素(例えば三次元ブロック５８)を示す。この”フルの度合”は、モデル化されたオブジェクトあるいはオブジェクト材料を構成するそれぞれのブロックの断片の材料の黒化度に対応して定義することができる。
【００２９】
図５でわかるように、彫刻用立体データのための先行技術による方法では例示の彫刻ツールのような立体ツールが用いられることが多い。このようなモデルでは、ツールが存在する立体(例えば６０)の要素は黒化度１を持ち、ツールが存在しない立体(例えば６２)の要素は黒化度０を持つ。したがって、このツールは本質的には、作業オブジェクトを修正するために関心のあるグラフィック作業オブジェクトの中を通過するオブジェクトである。修正は、シミュレートされたツールが作業オブジェクトの中を通過するときオブジェクト内部の相関的位置で作業オブジェクトの値からツールの値を差し引くことによって行うことができる。このツールは、作業オブジェクトの中をツールが通過した後作業オブジェクトの部分的フルブロックに結果としてなる可能性のある部分的フル要素を持つ場合もある。
【００３０】
図６の(ａ)に、彫刻用立体データのための先行技術による方法の二次元バージョンによって、フル要素(例えば６６)とエンプティ要素(例えば６８)をもつ二次元ツール６４、及び黒化度値を示す静的配列７０が示されている。
【００３１】
図６の(ｂ)では、切断ツール７２が切断経路７４に沿って配列７０の中を通り抜け、切断ツール経路７４に沿って存在する全ての要素の黒化度がゼロにセットされている(例えばブロック７６、７８)。
【００３２】
図７の(ａ)では、溶解ツール８０が溶解経路８２に沿って配列７０の中を通り抜け、溶解経路に沿って溶解ツールの下にある全ての要素の黒化度は部分的フルからエンプティへ(例えばブロック８４)あるいはフルから部分的フル(例えば８６)へ減少している。
【００３３】
図７の(ｂ)では、吹き付けツール８８が吹き付け経路９０に沿って配列７０の中を通り抜け、吹き付けツールの経路に沿って存在する全ての要素の黒化度はエンプティから部分的フル(例えば９２)へ、また部分的フルからフルへ(例えば９４)増加している。
【００３４】
図８に描かれているように彫刻用立体データのための先行技術による方法では、非エンプティ要素の別々のクラスタ(例えば９６及び９８)が創出されることが知られている。しかし、これらのクラスタは同じ静的データ配列１００の一部のままであり、これらのクラスタを別々のオブジェクトと考えるための、また、そのようなクラスタ間の相互作用をシミュレートするための手段は提供されていない。
【００３５】
本発明によって、図９の(ａ)に描かれているように、オブジェクトは、複数個のリンクされた要素(例えば１０４、１０６、１０８など)を含む立体配列１０２として表現される。もっと具体的に言えば、図９の(ｂ)に見られるように、要素１１０は、上部隣接要素１１２、底部隣接要素１１４、右部隣接要素１１６、左部隣接要素１１８、前部隣接要素１２０及び後部隣接要素１２２から成るその６つのもっとも近い隣接要素にリンクされている。
【００３６】
図１０に、Ｃコンピュータ言語による典型的データ構造を例示する。但し、適切なプログラミング言語で書かれた適切なデータ構造であればどのようなデータ構造を用いてもかまわない。このデータ構造にはまず、定義された要素を表すＸ、Ｙ及びＺ座標を指定する”フロート”構造形式のインデックスが含まれる(図１０の１０５参照)。従って、個々の要素を任意の位置に配置すればよく、所定のマトリックス上に画一的な間隔で配置する必要はない。この典型的データ構造には要素のカラーのインデックスも含まれる。もっと具体的に言えば、Ｃ言語の”ｃｈａｒ”構造によって８ビット値が指定される。これによって、要素カラー種別の赤、緑及び青の内容をこれらの変数に割り当てた値に基づく混合として指定することができる(図１０の１０３参照)。このデータ構造は更に筋肉、骨、皮膚、靭帯、軟骨などのような関連組織の定義から成る”種別(ｔｙｐｅ)”を”ｃｈａｒ”構造として指定する(図１０の１０１参照)。最後に、これらの要素の各々を表すデータ構造には隣接要素のポインタ、あるいは、隣接要素に関してリンクが創出されていないことを示すＮＵＬＬインディケータが含まれる。もっと具体的に言えば各ポインタによって、隣接リンク要素のインデックスのような情報を含み、またそれぞれのリンク、変形係数などの破損限界値を含むことができるアドレスが同定される。ポインタの各々に関連するデータには、印加された力に対する伸び、破損限界値などのようなそれぞれのリンクの特性を定義する基準を含めることもできる。各々の要素にはそのもっとも近い隣接要素の数に対する明白なポインタが含まれる。本発明で開示された実施の形態では、データ構造の中に、６つまでのもっとも近い隣接要素に対するポインタが含まる。これらのポインタは、この典型的データ構造では、＊右、＊左、＊上部、＊底部、＊後部及び＊前部として同定される(図１０の１０７参照)。各々の要素内の多くの異なる属性を符号化できる能力によって異なる材料、構造及び行動のモデリングが可能になる。例えば、図１０のデータ構造では、ある要素とその右隣の要素との間の連結は適当な隣接ポインタをＮＵＬＬにセットすることによって断ち切ることができる。同様に、ある要素とその隣接要素の１つは、その適当な隣接ポインタを互いに指示し合うようにセットすることによって結合することができる。
【００３７】
図１１に、立体グラフィックオブジェクトを操作するためのグラフィックシステムのフローチャートを示す。このシステムはユーザー入力１２６を待つユーザー・インターフェースから成る。ユーザー入力が検出されると、そのような入力は、質問ステップ１３６、１３８、１４０、１４２にそれぞれ例示されているようにそれが切断ツール、結合ツール、変形ツール、あるいは、彫刻ツール、翻訳ツール、指示ツールなどのような他の定義されたツールのいずれであるかがチェックされる。ツールが切断ツール１３６であれば、以下の関連図１２〜１４により詳しく説明されているように切断手順が起動される。結合ツールであれば、関連図１５〜１６により詳しく説明されているように結合手順が起動される。ツールが変形ツールであれば、関連図１７〜１８により詳しく説明されているように変形手順が起動される。もし変形の間、質問ステップ１３５に述べられているように材料限界値がその限界を超える場合にはステップ１３６に例示されているように断裂手順１４４が起動される。本明細書に説明されている以外の典型的ツールを用いることもできる。
【００３８】
図１２は、本発明による切断手順のフローチャートを描いたものである。まず、場面においてグラフィックオブジェクトによって占有されている空間の離散的表現である占有マップがステップ１４８に書かれているようにクリアされて初期化される。ステップ１５０に例示されているようにオブジェクト要素が占有マップ中へマップされ、次いでステップ１５２に示すように占有マップの要素間の連結マップが創出される。質問ステップ１５４に対する肯定応答に反映されているようにナイフの動きが検出されると、ステップ１５６に例示されているようにナイフの経路の下の占有マップの要素又は連結ラインのチェックが行われる。質問ステップ１５８に対する肯定応答によって反映されるように連結ラインと出会うと、ステップ１６０に述べられているように、連結された要素の適当なポインタをＮＵＬＬにセットすることにより、連結リンクは除去される。質問ステップ１５８に対する否定応答に反映されているように連結ラインと出会わなかった場合は、質問ステップ１６２にあるように何らかの要素と出会ったかどうかについて更に質問がなされる。質問ステップ１６２に対する肯定応答に反映されているように何らかの要素と出会った場合には、その要素は占有マップから除去され、ステップ１６４に述べられているようにその要素の隣接要素の全てに対する適当なポインタがＮＵＬＬにセットされる。いったん切断が完了すると、ステップ１６６に例示されているように占有マップは更新され、システムは別のナイフの動きを検出したかどうかをチェックする。すなわち制御が再び質問ステップ１５４へ移る。切断行動以外の行動が検出された場合には、ステップ１７０に述べられているように検出された行動に対応する処理ルーチンが起動される(ステップ１７１)。
【００３９】
図１３の(ａ)に、リンクされた要素(例えば１７４)から成る二次元配列１７２が、切断ツール１７８の経路１７６と共に描かれている。図１３の(ｂ)に、切断の結果として生じた別々のリンクされたオブジェクト１８０と１８２が描かれている。
【００４０】
図１４の(ａ)に、リンクされた要素の二次元配列と切断ツールの切断経路１８４とが描かれている。図１４の(ｂ)に、占有マップ１８６が切断経路１８７と重ねられて描かれている。オブジェクトの要素は黒いセル(例えば１８８と１９０)としてマップされ、隣接要素を連結する線は、線描アルゴリズムを用いて明るいセル(例えば１９２と１９４)としてマップされている。切断経路１８７と交差する占有セル(例えば１９６と１９８)は丸印で示されている。これらの交差は、どの要素又は連結リンクをオブジェクトモデルから除去しなければならないかを示すものである。
【００４１】
図１４の(ｃ)に、占有マップから派生した、第１と第２オブジェクトピース２００と２０２から成る結果として生じたオブジェクトを例示する。
【００４２】
図１５は、本発明によって開示された立体表現を用いて立体を結合する手法を例示するフローチャートである。ステップ２０６に例示されているように占有マップはメモリーをクリアすることによって初期化される。次いで、ステップ２０８に述べられているように、オブジェクト要素が占有マップ中へマップされる。質問ステップ２１０に対する肯定応答によって反映されるように結合ツールの動きが検出されると、ステップ２１１に示されるように結合ツール経路によるセル交差が確認される。ステップ２１２に例示されるように、結合ツール経路に沿った占有マップの位置が、ＮＵＬＬ隣接ポインタを持つエッジ要素を求めて検索される。エッジ要素は、ＮＵＬＬ値(又は''連結なし''の指示を与える任意の値)を有する隣接ポインタを持つものとして定義される。質問ステップ２１６に対する否定応答によって反映されているようにもしエッジ要素が発見されなければ、制御はステップ２１０へ移り、システムは更なるツールの動きを待つ。質問ステップ２１６に対する肯定応答に反映されているように、もし結合ツールの経路に沿ってエッジ要素が検出されれば、ステップ２１８に例示されるように対応する欠落した隣接を有する隣接要素を求めてエッジ要素が検索される。質問ステップ２２０に対する否定応答に反映されているように、マッチするものが発見されなければ、ステップ２１０へ制御は移り、システムは更なるツールの動きを待つ。質問ステップ２２０に対する肯定応答によって反映されているように、もしマッチするものが発見されれば、ステップ２２４に述べられているように、その適当な隣接ポインタを互いに指示し合うようにセットすることによってマッチした要素間で新しいリンクが創出される。結合される要素のために新しいリンクが作られた後、ステップ２１０へ制御は移り、システムは更なるツールの動きを待つ。質問ステップ２３０に対する肯定応答によって反映されているように、もし結合ツールの動きが検出されず、別の入力行動が検出された場合には結合手順は終了となり、その別の入力行動を処理する処理ルーチンが起動される。
【００４３】
図１６の(ａ)に、二次元リンクされたオブジェクト２３２と２３４が密着して描かれている。結合ツールの下の領域が点線状の輪郭２３６によって描かれている。図１６の(ｂ)に、対応する欠落した隣接を持っていたこの２つのオブジェクトのエッジポイントをマッチさせることによって作られた２つの新しいリンク２３８と２４０が示されている。
【００４４】
変形オブジェクトを断裂する手法を示すフローチャートが図１７に描かれている。ステップ２４４に述べられているように、オブジェクトを変形するとき、質問ステップ２４６によって例示されているように材料限界値を超えているかどうかの判定のためにリンクがテストされる。質問ステップ２４６に対する肯定応答によって反映されているように、もし材料限界値を超えている場合には、ステップ２５０によって例示されているようにオブジェクトは断裂する。もっと具体的に言えば、連結された要素の適当な隣接ポインタをＮＵＬＬにセットすることによって占有マップの材料限界値を超えた場所で連結は断ち切られる。
【００４５】
図１８の(ａ)〜(ｄ)に、二次元リンクされた要素オブジェクトの断裂が描かれている。図１８の(ａ)には、２つの力２５２と２５４が、一般的に２５６と命名したオブジェクトの２つの上部コーナーの反対方向に加えられている。図１８の(ｂ)では、オブジェクトは要素２５８と２６０との間のリンクの最大限界値まで引き伸ばされている。リンクを断ち切る力の形であるいは距離の閾値としてこの限界値を確定することもできる。もし連結された要素間の距離が距離閾値を超えていればリンクは断ち切られると考えられる。図１８の(ｃ)では、隣接要素２５８と２６０との間、及び２６２と２６４との間の連結リンクは断ち切られている。図１８の(ｄ)では、オブジェクトは断裂して２つの別々のピース２６６と２６８になっている。
【００４６】
本発明で開示された、グラフィックオブジェクトのモデル化の手法、及びオブジェクトの切断、結合及び断裂によって生成されるようなオブジェクトの操作シミュレーション手法の変形及び修正を行うことは、本出願に開示された発明の概念から逸脱しなければ可能であるということは当業者にとって明らかである。従って、本出願に開示する本発明は、典型的実施の形態に限定されるものではなく、添付の特許請求の範囲と精神によってのみ限定されるものである。
【００４７】
本発明によるコンピュータにおけるグラフィック表現生成方法では、１つの実施の形態として、各々の要素は６つのもっとも近い隣接要素と、その要素のデータ構造の中にそれらの隣接要素に対するポインタを格納することによって、明白にリンクすることができる。２つの要素間のリンクは、切断ツールのグラフィック表現が要素の間を通過した時、２つの要素の適当な隣接ポインタを互いに対してでなくＮＵＬＬ値を示すようにセットすることで切断することができる。オブジェクト変形のシミュレーション中２つの要素間のリンクの材料限界値がその範囲を超えると、２つの要素の適当な隣接ポインタをＮＵＬＬにセットすることによりリンクを断裂することができる。密接した２つの立体オブジェクトに対して結合ツールが用いられると、ＮＵＬＬにセットされた相補的隣接ポインタを有する２つのオブジェクトのエッジ要素は、これらの欠落した隣接を互いに指示するようにセットすることによって結合することができる。これにより、グラフィックオブジェクトを表すリンクされた立体表現を、オブジェクトの切断、結合及び断裂を示す物理的にもっともらしいモデリング手法と共に提示することができる。
【図面の簡単な説明】
【００４８】
【図１】グラフィックオブジェクトの彫刻、断裂又は結合をシミュレートするためのシステムの概略図である。
【図２】(ａ)はグラフィック切断ツールの三次元グラフィックオブジェクト及び切断経路の概略図、(ｂ)は凹面ベースのグラフィックオブジェクトが切断されたときその結果としてできるオブジェクトの概略図である。
【図３】(ａ)は面ベースのオブジェクトを表現するために用いられる面パッチの図、(ｂ)は切断されたグラフィックオブジェクト上に重ねられた切断ツールによる切断結果を示す面を示す図、(ｃ)は面パッチに分割後の切断ツールの切断面を示す図である。
【図４】従来の標本化された黒化度値の三次元配列によって表現された立体を示す図である。
【図５】従来の立体デジタル切断ツールを示す図である。
【図６】(ａ)は標本化された黒化度値の配列の二次元描写図及びデジタル切断ツールの二次元描写図、(ｂ)は指示された経路に沿って彫刻ツールをドラッグした結果図である。
【図７】(ａ)は指示された経路に沿って溶解ツールをドラッグした結果図、(ｂ)は指示された経路に沿って吹き付けツールをドラッグした結果図である。
【図８】従来の別々のオブジェクトクラスタに配列されているが同じデータ配列に属する標本化された黒化度値の二次元配列の概略図である。
【図９】(ａ)データ配列の各オブジェクトがその隣接要素に対する明白なリンクを含むこの発明のコンピュータにおけるグラフィック表現生成方法によるオブジェクト表現の一例を示す図、(ｂ)は(ａ)における６つのもっとも近い隣接要素に三次元要素がリンクしている一例を示す図である。
【図１０】この発明のコンピュータにおけるグラフィック表現生成方法におけるリンクされた立体のＣプログラミング言語で書かれた典型的データ構造を示す図である。
【図１１】この発明のコンピュータにおけるグラフィック表現生成方法におけるオブジェクトの切断、結合及び断裂を可能にする立体グラフィックオブジェクトを操作するためのシステムの概略を示すフローチャート図である。
【図１２】この発明のコンピュータにおけるグラフィック表現生成方法におけるリンクされた立体の切断手順の概略を示すフローチャート図である。
【図１３】(ａ)はこの発明のコンピュータにおけるグラフィック表現生成方法におけるリンクされた要素の二次元配列及び切断ツールの経路について説明するための図、(ｂ)は所定の切断経路から結果として生じた２つの同様の要素オブジェクトを描写した図である。
【図１４】(ａ)はこの発明のコンピュータにおけるグラフィック表現生成方法におけるリンクされた要素の二次元配列及び切断ツールの経路について説明するための図、(ｂ)はオブジェクト要素間の衝突、連結リンク、及び切断経路が検出された空間を表現した図、(ｃ)は所定の切断経路に沿って切り離された結果生じたオブジェクトを示す。
【図１５】この発明のコンピュータにおけるグラフィック表現生成方法における２つのリンクした立体を結合する手順の概略を示すフローチャート図である。
【図１６】(ａ)はこの発明のコンピュータにおけるグラフィック表現生成方法における互いに近くに配置された２つの異なる二次元リンクオブジェクト及び結合用コンポーネントが加えられた領域を描いた図、(ｂ)は２つのグラフィックオブジェクトを結合するために形成された新しいリンクを示す図である。
【図１７】この発明のコンピュータにおけるグラフィック表現生成方法におけるオブジェクト変形中にオブジェクトを断裂する手順の概略を示すフローチャート図である。
【図１８】(ａ)はこの発明のコンピュータにおけるグラフィック表現生成方法におけるリンクされた要素の二次元配列及びオブジェクトを引っ張って分離するためにオブジェクトの上部コーナーに加えられた力を描写した図、(ｂ)はコーナーに加えられた力によって引き伸ばされ分離しているオブジェクトを示す図、(ｃ)は２組の近接要素間のリンク距離が材料限界値を超えたところで形成され始めている断裂を示す図、(ｄ)は断裂の完了後の断裂したオブジェクトの２つの別々のピースを示す図である。
【符号の説明】
【００４９】
２  コンピュータモニター、４  キーボード、６  入力装置、８  オブジェクト、１０，１７８  切断ツール、１２  コンピュータ、１４  グラフィックオブジェクト、１６  トレーシング経路、１８  グラフィックツール、２０，２２，２６６，２６８  ピース、２４，１８０，１８２，２３２，２３４，２５６  オブジェクト、２６、２８、３０  パッチ、３２，１７６  経路、３４  グラフィックツール、３６  新しい面、３８，４０，４２  隣接面パッチ、４４，４６  面パッチピース、１０２  立体配列、１０４，１０６，１０８，１１０，１７４  要素、１１２  上部隣接要素、１１４  底部隣接要素、１１６  右部隣接要素、１１８  左部隣接要素、１２０  前部隣接要素、１２２  後部隣接要素、１７２  二次元配列、１８４，１８７  切断経路、１８６  占有マップ、１８８，１９０，１９２，１９４  セル、１９６，１９８  占有セル、２００，２０２  オブジェクトピース、２３８，２４０  新しいリンク、２５２、２５４  力、２５８，２６０，２６２，２６４  隣接要素。
【図１】
2008251044.tif 000003
【図２】
2008251044.tif 000004
【図３】
2008251044.tif 000005
【図４】
2008251044.tif 000006
【図５】
2008251044.tif 000007
【図６】
2008251044.tif 000008
【図７】
2008251044.tif 000009
【図８】
2008251044.tif 000010
【図９】
2008251044.tif 000011
【図１０】
2008251044.tif 000012
【図１１】
2008251044.tif 000013
【図１２】
2008251044.tif 000014
【図１３】
2008251044.tif 000015
【図１４】
2008251044.tif 000016
【図１５】
2008251044.tif 000017
【図１６】
2008251044.tif 000018
【図１７】
2008251044.tif 000019
【図１８】
2008251044.tif 000020