JPH11175767A - コンピュータにおけるグラフィック表現生成方法 - Google Patents

コンピュータにおけるグラフィック表現生成方法

Info

Publication number
JPH11175767A
JPH11175767A JP10264788A JP26478898A JPH11175767A JP H11175767 A JPH11175767 A JP H11175767A JP 10264788 A JP10264788 A JP 10264788A JP 26478898 A JP26478898 A JP 26478898A JP H11175767 A JPH11175767 A JP H11175767A
Authority
JP
Japan
Prior art keywords
elements
link
value
computer
generating
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP10264788A
Other languages
English (en)
Inventor
Sarah F Gibson
サラ・エフ・ギブソン
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Mitsubishi Electric Information Technology Corp
Mitsubishi Electric Research Laboratories Inc
Original Assignee
Mitsubishi Electric Information Technology Corp
Mitsubishi Electric Research Laboratories Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Mitsubishi Electric Information Technology Corp, Mitsubishi Electric Research Laboratories Inc filed Critical Mitsubishi Electric Information Technology Corp
Publication of JPH11175767A publication Critical patent/JPH11175767A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three-dimensional [3D] modelling for computer graphics

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Computer Graphics (AREA)
  • Geometry (AREA)
  • Software Systems (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Processing Or Creating Images (AREA)
  • Image Processing (AREA)

Abstract

(57)【要約】 【課題】 グラフィックオブジェクトを表すリンクされ
た立体表現をオブジェクトの切断、結合、断裂を示す物
理的にリアルなモデリング手法と共に提示。 【解決手段】 各の要素は６つの最も近い隣接要素と、
その要素のデータ構造の中に隣接要素に対するポインタ
を格納することでリンクできる。２要素間のリンクは切
断ツールのグラフィック表現が要素間を通過した時、２
要素の適当な隣接ポインタを互いに対してでなくＮＵＬ
Ｌ値を示す如くセットすることで切断できる。オブジェ
クト変形のシミュレーション中、２要素間のリンクの材
料限界値が範囲を超えると２要素の適当な隣接ポインタ
をＮＵＬＬにセットすることでリンクを断裂できる。密
接した２立体オブジェクトに結合ツールが用いられると
ＮＵＬＬにセットされた相補的隣接ポインタを有する２
つのオブジェクトのエッジ要素はこれらの欠落した隣接
を互いに指示するようにセットされて結合される。

Description

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

Claims (19)

    【特許請求の範囲】
  1. 【請求項１】 コンピュータのビデオディスプレイ上で
    グラフィックとして表示され、シミュレートされたツー
    ルを使用して操作できるオブジェクトのグラフィック表
    現を生成するコンピュータにおけるグラフィック表現生
    成方法であって、 メモリ内のマップに、前記マップ内の選択された記憶位
    置における前記オブジェクトに対応する複数の要素の存
    在を示す複数個の第１インデックスを格納する工程と、 少なくとも一組の前記複数の要素の中の各々と関連し
    て、前記オブジェクトのグラフィック表現を形成するた
    めに前記一組の要素間のリンクを表現する第２インデッ
    クスを生成する工程と、 前記マップの前記一組の要素の各々のための前記第２イ
    ンデックスを格納する工程と、 前記メモリ内部の前記マップの内容に基づいて前記オブ
    ジェクトのグラフィック表現を前記ビデオディスプレイ
    上に表示する工程と、 を有することを特徴とするコンピュータにおけるグラフ
    ィック表現生成方法。
  2. 【請求項２】 前記第２インデックスの各々が前記一組
    の要素の相手の値を有することを特徴とする請求項１に
    記載のコンピュータにおけるグラフィック表現生成方
    法。
  3. 【請求項３】 ユーザーによってシミュレートされたツ
    ールのアプリケーションに応じてコンピュータのディス
    プレイ上に前記オブジェクトに対する変更を示すグラフ
    ィック表現を生成する工程と、 前記表示工程に影響を与えるために前記ユーザー入力に
    応じて前記第１及び第２インデックスを操作する工程
    と、 をさらに含むことを特徴とする請求項１に記載のコンピ
    ュータにおけるグラフィック表現生成方法。
  4. 【請求項４】 前記生成工程が、 シミュレートされた切断ツールを用いて前記オブジェク
    トの中を通る経路に沿った１本の線描を表すグラフィッ
    ク表現を表現する第３インデックスを生成する工程と、 前記マップ内の前記要素の中の選択された要素を示す前
    記第１及び第２インデックスに前記第３インデックスを
    相互関連させる工程と、 前記マップ内の前記第１及び第２インデックスの中の選
    択されたインデックスを修正し、前記要素の中の選択さ
    れた要素及びリンクが除去されたことを示す工程と、 を含むことを特徴とする請求項３に記載のコンピュータ
    におけるグラフィック表現生成方法。
  5. 【請求項５】 前記生成工程が、 シミュレートされた溶解ツールを用いて前記ディスプレ
    イ上で前記オブジェクトの中を通る経路に沿った１本の
    線描を表すグラフィック表現を表現する第３インデック
    スを生成する工程と、 前記マップ内の前記要素の中の選択された要素を示す前
    記第１及び第２インデックスに前記第３インデックスを
    相互関連させる工程と、、 前記相互関連工程に応じて、前記マップ内の選択された
    位置における前記第１及び第２インデックスの値を修正
    する工程と、 を含むことを特徴とする請求項３に記載のコンピュータ
    におけるグラフィック表現生成方法。
  6. 【請求項６】 前記修正工程が、少なくとも１つのリン
    クに対する前記第２インデックスの値を前記相互関連工
    程に応じて第１の値から第２の値へ変更し、前記相互関
    連工程に応じてそれぞれのリンクが弱められていること
    を示す工程を有することを特徴とする請求項５に記載の
    コンピュータにおけるグラフィック表現生成方法。
  7. 【請求項７】 前記修正工程が、少なくとも１つのリン
    クに対応する前記マップ内の少なくとも１つの記憶位置
    の値を第１の値から第２の値へ変更し、前記相互関連工
    程に応じてそれぞれのリンクが切断されていることを示
    す工程を有することを特徴とする請求項５に記載のコン
    ピュータにおけるグラフィック表現生成方法。
  8. 【請求項８】 それぞれのリンクへの印加時に、それぞ
    れの閾値を超える力がシミュレーションで示された場
    合、それぞれのリンクが切断されるようにシミュレート
    される力の閾値が前記リンクの中の対応するリンクと関
    連する前記第２インデックスの中の少なくともいくつか
    に含まれ、 前記生成工程が 前記オブジェクトの選択された要素に印加された力を表
    す前記コンピュータへのユーザー入力に応じて、前記リ
    ンクの少なくともいくつかに印加された力を表現する値
    を生成する工程と、 前記印加された力を、前記リンクの中の前記少なくとも
    いくつかのそれぞれについての対応する力の閾値と比較
    する工程と、 この比較工程において印加された力がそれぞれの力の閾
    値を超えたことが示されるそれぞれのリンクに対して前
    記第２インデックスを第１の値から第２の値へ変更しそ
    れぞれのリンクが切断されてしまったことを示す工程
    と、 を含むことを特徴とする請求項３に記載のコンピュータ
    におけるグラフィック表現生成方法。
  9. 【請求項９】 前記リンクの中の対応するリンクと関連
    する、前記第２インデックスの中の少なくともいくつか
    が、それぞれのリンクと関連する距離閾値を含み、 前記オブジェクトの選択された要素に印加された力を表
    す前記コンピュータへのユーザー入力に応じて、前記そ
    れぞれのリンクの長さを表現する値を生成する工程と、 それぞれのリンクの前記長さをそれぞれのリンクの各々
    に対する距離の閾値と比較する工程と、 この比較工程によってそれぞれのリンクの長さが距離の
    閾値を超えていることが示されているそれぞれのリンク
    に対して前記第２インデックスを第１の値から第２の値
    へ変更し、それぞれのリンクが切断されてしまっている
    ことを示す工程と、 をさらに含むことを特徴とする請求項３に記載のコンピ
    ュータにおけるグラフィック表現生成方法。
  10. 【請求項１０】 前記要素の中の少なくともいくつかが
    ４つの隣接要素との関連リンクを有することを特徴とす
    る請求項１に記載のコンピュータにおけるグラフィック
    表現生成方法。
  11. 【請求項１１】 前記第２インデックス格納工程が更
    に、前記マップ内の前記要素の中の少なくとも１つの要
    素と４つの隣接要素との間のリンクを表現する第２イン
    デックスを前記メモリに格納する工程を有することを特
    徴とする請求項１に記載のコンピュータにおけるグラフ
    ィック表現生成方法。
  12. 【請求項１２】 前記第２インデックス格納工程が更
    に、前記マップ内の前記要素の中の少なくとも１つの要
    素と６つの隣接要素との間のリンクを表現する第２イン
    デックスを前記メモリに格納し、立体を含む前記オブジ
    ェクトの部分のグラフィック表現を形成する工程を有す
    ることを特徴とする請求項１に記載のコンピュータにお
    けるグラフィック表現生成方法。
  13. 【請求項１３】 前記生成工程が、 シミュレートされた結合ツールの経路を表現する前記オ
    ブジェクトの中を通る経路のグラフィック表現を前記デ
    ィスプレイ上に生成する工程と、 前記経路を前記占有マップ内の前記要素の記憶位置と比
    較し、前記経路の反対側にリンクされていない隣接要素
    の対を確認する工程と、 前記リンクされていない隣接要素対に対して、第１の値
    から第２の値へ第２インデックスを修正し、シミュレー
    トされた結合ツールを間に通過させた結果として以前は
    リンクしていなかった前記隣接要素対がリンクされてい
    ることを示す工程と、 を有することを特徴とする請求項３に記載のコンピュー
    タにおけるグラフィック表現生成方法。
  14. 【請求項１４】 表示のためのオブジェクト、およびシ
    ミュレートされたツールを用いてコンピュータのビデオ
    ディスプレイ上でのグラフィック化されたオブジェクト
    のシミュレートされた操作のグラフィック表現を生成す
    るコンピュータにおけるグラフィック表現生成方法であ
    って、 前記オブジェクトのそれぞれの要素に対応する複数個の
    データ構造をメモリに格納する工程であって、前記デー
    タ構造の各々が、前記メモリ内のそれぞれの要素の位置
    及び他の記憶位置に対する複数個のポインタを示すデー
    タ表現を有し、前記記憶位置が前記複数の要素の中の他
    の要素と関連しているものと、 前記複数のデータ構造の中の第１のデータ構造の前記ポ
    インタの１つと関連する前記メモリ内の記憶位置に前記
    複数のデータ構造の中の第２のデータ構造の値を格納
    し、かつ、前記複数のデータ構造の中の前記第２のデー
    タ構造の前記ポインタの１つと関連する前記メモリ内の
    記憶位置に前記複数のデータ構造の中の前記第１のデー
    タ構造の値を格納して、前記第１及び第２要素が前記オ
    ブジェクトの内部で一緒にリンクされていることを示す
    第２格納工程と、 前記データ構造の内容に基づいて前記オブジェクトのグ
    ラフィック表現を前記ビデオディスプレイ上に表示する
    工程と、 を有することを特徴とするコンピュータにおけるグラフ
    ィック表現生成方法。
  15. 【請求項１５】 前記第２格納ステップが更に、前記複
    数のデータ構造の中の前記第１のデータ構造の前記ポイ
    ンタの中の前記ポインタと関連する前記メモリの前記記
    憶位置、第１の値を上書きし、前記複数のデータ構造の
    中の前記第２のデータ構造の前記ポインタの中の前記ポ
    インタと関連する前記メモリの前記記憶位置、第２の値
    を格納する工程を有し、以って前記第１及び第２の値に
    よって、それぞれの要素が前記要素のもう一方の要素と
    リンクされていないことが示されることを特徴とする請
    求項１４に記載のコンピュータにおけるグラフィック表
    現生成方法。
  16. 【請求項１６】 前記第１及び第２の値が前記要素の他
    方の要素を識別しないＮＵＬＬ値を有することを特徴と
    する請求項１５に記載のコンピュータにおけるグラフィ
    ック表現生成方法。
  17. 【請求項１７】 前記複数のデータ構造の中の第１のデ
    ータ構造の前記ポインタの中の１つと関連する前記メモ
    リの記憶位置に前記要素のカラーを示すデータを格納す
    る工程を更に含むことを特徴とする請求項１４に記載の
    コンピュータにおけるグラフィック表現生成方法。
  18. 【請求項１８】 前記要素の前記カラーを示す前記デー
    タが更に前記カラーを定義する赤、緑、青を表現する値
    を有することを特徴とする請求項１７に記載のコンピュ
    ータにおけるグラフィック表現生成方法。
  19. 【請求項１９】 前記ポインタの１つと関連する前記メ
    モリの記憶位置に力の閾値を示す値を格納する工程と、 前記オブジェクトに対する力のアプリケーションをシミ
    ュレートし、前記ポインタの中の少なくとも１つに対応
    するそれぞれのリンク上にシミュレートされた力を生成
    する工程と、 前記ポインタの中の前記少なくとも１つに対応するそれ
    ぞれのリンクに対してそれぞれのリンク上のシミュレー
    トされた力が力の閾値を超えている場合、前記複数のデ
    ータ構造の少なくとも前記第２のデータ構造の前記値を
    前記メモリから除去する工程と、 を更に有することを特徴とする請求項１４に記載のコン
    ピュータにおけるグラフィック表現生成方法。
JP10264788A 1997-09-19 1998-09-18 コンピュータにおけるグラフィック表現生成方法 Pending JPH11175767A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/933,393 US6054992A (en) 1997-09-19 1997-09-19 cutting, jointing and tearing volumetric objects
US08/933393 1997-09-19

Related Child Applications (1)

Application Number Title Priority Date Filing Date
JP2008159486A Division JP2008251044A (ja) 1997-09-19 2008-06-18 コンピュータにおけるグラフィック表現生成方法

Publications (1)

Publication Number Publication Date
JPH11175767A true JPH11175767A (ja) 1999-07-02

Family

ID=25463862

Family Applications (2)

Application Number Title Priority Date Filing Date
JP10264788A Pending JPH11175767A (ja) 1997-09-19 1998-09-18 コンピュータにおけるグラフィック表現生成方法
JP2008159486A Pending JP2008251044A (ja) 1997-09-19 2008-06-18 コンピュータにおけるグラフィック表現生成方法

Family Applications After (1)

Application Number Title Priority Date Filing Date
JP2008159486A Pending JP2008251044A (ja) 1997-09-19 2008-06-18 コンピュータにおけるグラフィック表現生成方法

Country Status (3)

Country Link
US (1) US6054992A (ja)
EP (1) EP0903697A3 (ja)
JP (2) JPH11175767A (ja)

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2003085585A (ja) * 2001-09-10 2003-03-20 Namco Ltd 画像生成システム、プログラム及び情報記憶媒体
JP2008250978A (ja) * 2007-03-05 2008-10-16 Nagaoka Univ Of Technology 触覚の視覚的表現方法および触覚の視覚的表現装置
JP2008292534A (ja) * 2007-05-22 2008-12-04 Mitsubishi Precision Co Ltd 手術切断運動模擬方法とその装置及び模擬手術接触判定方法とその装置並びに手術切断運動模擬用のデータベース構造
JP2009178575A (ja) * 2009-05-18 2009-08-13 Namco Bandai Games Inc ゲームシステム及び情報記憶媒体
WO2013012042A1 (ja) * 2011-07-19 2013-01-24 株式会社東芝 画像処理システム、装置、方法及び医用画像診断装置
US9153146B2 (en) 2001-01-24 2015-10-06 Surgical Science Sweden Ab Method and system for simulation of surgical procedures

Families Citing this family (18)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2771202B1 (fr) * 1997-11-19 2000-01-21 Inst Nat Rech Inf Automat Dispositif electronique de traitement de donnees-image, pour la simulation du comportement deformable d'un objet
US6219060B1 (en) * 1998-10-15 2001-04-17 General Electric Company Rendering of surfaces from volumetric data employing both dividing and stretching cubes
JP4278073B2 (ja) * 1999-06-25 2009-06-10 株式会社バンダイナムコゲームス 画像生成システム及び情報記憶媒体
JP4144773B2 (ja) * 1999-07-21 2008-09-03 株式会社バンダイナムコゲームス 画像生成システム及び情報記憶媒体
CN1386200A (zh) * 2000-06-29 2002-12-18 目标储油层公司 有限元模型中的特征建模方法
US7369973B2 (en) 2000-06-29 2008-05-06 Object Reservoir, Inc. Method and system for representing reservoir systems
US7363198B2 (en) * 2001-10-29 2008-04-22 The Board Of Trustees Of The Leland Stanford Junior University Long elements method for simulation of deformable objects
US7850456B2 (en) * 2003-07-15 2010-12-14 Simbionix Ltd. Surgical simulation device, system and method
US7589720B2 (en) * 2004-08-04 2009-09-15 Microsoft Corporation Mesh editing with gradient field manipulation and user interactive tools for object merging
US8560047B2 (en) * 2006-06-16 2013-10-15 Board Of Regents Of The University Of Nebraska Method and apparatus for computer aided surgery
US9498231B2 (en) 2011-06-27 2016-11-22 Board Of Regents Of The University Of Nebraska On-board tool tracking system and methods of computer assisted surgery
WO2013052187A2 (en) 2011-06-27 2013-04-11 Board Of Regents Of The University Of Nebraska On-board tool tracking system and methods of computer assisted surgery
US11911117B2 (en) 2011-06-27 2024-02-27 Board Of Regents Of The University Of Nebraska On-board tool tracking system and methods of computer assisted surgery
DE102012214307B4 (de) * 2012-08-10 2024-09-05 Robert Bosch Gmbh Verfahren und Vorrichtung zum Modellieren eines Umfelds
US10105149B2 (en) 2013-03-15 2018-10-23 Board Of Regents Of The University Of Nebraska On-board tool tracking system and methods of computer assisted surgery
US20150049085A1 (en) * 2013-08-16 2015-02-19 Schlumberger Technology Corporation Pixel-based or voxel-based mesh editing
US9710156B2 (en) * 2014-09-25 2017-07-18 Disney Enterprises, Inc. Three-dimensional object sculpting and deformation on a mobile device
WO2024185315A1 (ja) * 2023-03-03 2024-09-12 ソニーグループ株式会社 シミュレータ及びシミュレーションデータ生成方法

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4719585A (en) * 1985-08-28 1988-01-12 General Electric Company Dividing cubes system and method for the display of surface structures contained within the interior region of a solid body
US4987554A (en) * 1988-08-24 1991-01-22 The Research Foundation Of State University Of New York Method of converting continuous three-dimensional geometrical representations of polygonal objects into discrete three-dimensional voxel-based representations thereof within a three-dimensional voxel-based system
US4985856A (en) * 1988-11-10 1991-01-15 The Research Foundation Of State University Of New York Method and apparatus for storing, accessing, and processing voxel-based data
US5734384A (en) * 1991-11-29 1998-03-31 Picker International, Inc. Cross-referenced sectioning and reprojection of diagnostic image volumes
JP3203160B2 (ja) * 1995-08-09 2001-08-27 三菱電機株式会社 ボリューム・レンダリング装置及び方法

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9153146B2 (en) 2001-01-24 2015-10-06 Surgical Science Sweden Ab Method and system for simulation of surgical procedures
JP2003085585A (ja) * 2001-09-10 2003-03-20 Namco Ltd 画像生成システム、プログラム及び情報記憶媒体
JP2008250978A (ja) * 2007-03-05 2008-10-16 Nagaoka Univ Of Technology 触覚の視覚的表現方法および触覚の視覚的表現装置
JP2008292534A (ja) * 2007-05-22 2008-12-04 Mitsubishi Precision Co Ltd 手術切断運動模擬方法とその装置及び模擬手術接触判定方法とその装置並びに手術切断運動模擬用のデータベース構造
JP2009178575A (ja) * 2009-05-18 2009-08-13 Namco Bandai Games Inc ゲームシステム及び情報記憶媒体
WO2013012042A1 (ja) * 2011-07-19 2013-01-24 株式会社東芝 画像処理システム、装置、方法及び医用画像診断装置

Also Published As

Publication number Publication date
EP0903697A3 (en) 1999-06-09
EP0903697A2 (en) 1999-03-24
JP2008251044A (ja) 2008-10-16
US6054992A (en) 2000-04-25

Similar Documents

Publication Publication Date Title
JP2008251044A (ja) コンピュータにおけるグラフィック表現生成方法
Bielser et al. A state machine for real-time cutting of tetrahedral meshes
Montgomery et al. Spring: A general framework for collaborative, real-time surgical simulation
Paulus et al. Virtual cutting of deformable objects based on efficient topological operations
Jeřábková et al. Volumetric modeling and interactive cutting of deformable bodies
De et al. Physically realistic virtual surgery using the point-associated finite field (PAFF) approach
Bielser et al. Open surgery simulation
CN115087983A (zh) 使用几何面片进行混合建模的方法和系统
Wang et al. A review of virtual cutting methods and technology in deformable objects
Mor Progressive cutting with minimal new element creation of soft tissue models for interactive surgical simulation
KR101275938B1 (ko) 가상 수술 시뮬레이션 방법 및 장치
Nienhuys et al. A Delaunay approach to interactive cutting in triangulated surfaces
Forest et al. Removing tetrahedra from a manifold mesh
Zhang et al. On cutting and dissection of virtual deformable objects
Chen et al. A displacement driven real-time deformable model for haptic surgery simulation
KR101166554B1 (ko) 소작 애니메이션 효과 생성 장치 및 방법
CN110491517A (zh) 一种三维模型局部半透明显示操作实现方法及装置
CN115984507A (zh) 一种多维时序生物力学有限元结果沉浸式可视化方法
Zhang et al. Simulation of progressive cutting on surface mesh model
Kraut et al. Temporal bone surgical simulation employing a multicore architecture
Brodlie¹ Real-time soft tissue modelling for web-based surgical simulation: SurfaceChainMail
Viet et al. An algorithm for cutting 3d surface meshes
Qi et al. Split and join: An efficient approach for simulating stapled intestinal anastomosis in virtual reality
Chacko et al. Virtual surgery on geometric model of real human organ data
Gutiérrez et al. Xfem framework for cutting soft tissue-including topological changes in a surgery simulation

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20050825

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20080318

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20080618

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20080826

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20081125

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20081128

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20081224

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20090105

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20090126

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20090129

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20090220

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20090421