JPH08241437A - ボクセルに基づくオブジェクト表現のための衝突回避システム - Google Patents

ボクセルに基づくオブジェクト表現のための衝突回避システム

Info

Publication number
JPH08241437A
JPH08241437A JP7327530A JP32753095A JPH08241437A JP H08241437 A JPH08241437 A JP H08241437A JP 7327530 A JP7327530 A JP 7327530A JP 32753095 A JP32753095 A JP 32753095A JP H08241437 A JPH08241437 A JP H08241437A
Authority
JP
Japan
Prior art keywords
voxel
objects
data
occupancy map
virtual space
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.)
Granted
Application number
JP7327530A
Other languages
English (en)
Other versions
JP2726811B2 (ja
Inventor
Gibson Sarah F Frisken
サラ・エフ・フリスケン・ギブソン
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 Research Laboratories Inc
Original Assignee
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 Research Laboratories Inc filed Critical Mitsubishi Electric Research Laboratories Inc
Publication of JPH08241437A publication Critical patent/JPH08241437A/ja
Application granted granted Critical
Publication of JP2726811B2 publication Critical patent/JP2726811B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T15/00—Three-dimensional [3D] image rendering
    • G06T15/10—Geometric effects

Landscapes

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

Abstract

(57)【要約】 【課題】 グラフィカルオブジェクトの移動中の衝突を
検出しかつグラフィカルオブジェクトが互いの中に侵入
するのを防ぐようにオブジェクトを操作する。 【解決手段】 表示画面上への表示のためにボクセルに
基づく占有マップが仮想空間を表すオブジェクト生成手
段、個別のオブジェクトをデータとして占有マップにマ
ッピングするマッピング手段、仮想空間においてオブジ
ェクトを移動させる移動手段、任意のオブジェクトに対
応するデータを上記データによって以前に占められてい
たものとは異なる場所に書き込むことによって占有マッ
プを更新する更新手段、任意のオブジェクトの仮想空間
における移動中に別のデータが既に存在する記憶場所に
書き込まれようとしている場合を検出する衝突検出手
段、既に占有されている占有マップの場所の検出によっ
て任意のオブジェクトに付随する画面上の表現の画面上
の動きを阻止する阻止手段を備えた。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】この発明は、仮想空間におけ
るグラフィカルオブジェクト間の移動及び相互作用を可
能にするシステムに関し、特に、ボクセルに基づくフォ
ーマットで表現される二次元及び三次元のグラフィカル
オブジェクト間の衝突を検出し、かつグラフィカルオブ
ジェクトが互いの中に侵入するのを防ぐようにされたボ
クセルに基づくオブジェクト表現のための衝突回避シス
テムに関する。
【０００２】
【従来の技術】三次元オブジェクトモデル間の実時間対
話を必要とするコンピュータグラフィックス及び仮想現
実における幾つかの興味深いアプリケーションがある。
例えば、グラフィカルオブジェクトが仮想環境において
動かされ、コンピュータ画面上で見られる対話式仮想ア
センブリタスクにおいて、オペレータは、入力トラッカ
デバイスを用いて、仮想作業空間におけるいろいろなオ
ブジェクトモデルが一緒になって複合構造を作り出すま
で、それらを選択かつ操作する。これらのオブジェクト
モデルは、ユーザに現実感をもたらすために、物理的に
現実的な動作をしなければならない。例えば、２つの異
なる固体オブジェクトモデルは、それらが移動するのに
したがって互いに入り込むべきではない。
【０００３】第２の例として、物理的に現実的なシミュ
レーションまたはアニメーションにおいて、各オブジェ
クトモデルは、それらが接触した際には互いに対して反
発しなければならない。各オブジェクトモデルが互いに
入り込むことを防がなければならず、全システムが運動
量及びエネルギーを保存するように物理の法則に従わな
ければならない。
【０００４】これらの問題は共に、移動するオブジェク
トモデル間の衝突及び接触を検出することを必要とす
る。対話式システムにおいては、実時間でアプリケーシ
ョンを実行できるように、接触及び衝突を迅速に計算し
なければならない。しかしながら、衝突の検出は、大部
分の従来のオブジェクトフォーマットにとって、極めて
計算上集中的なタスクである。
【０００５】極めて簡単なアプリケーション及びコンピ
ュータゲームにおいては、オブジェクトの位置が空間中
の単一点によって示される。２つのオブジェクト点の間
の距離がそれら２つのオブジェクトの平均の大きさより
小さくなった場合に、これら２つのオブジェクトの間の
衝突が検出される。オブジェクトの点の位置がある制約
を犯した場合に、オブジェクトと環境の境界との間の衝
突が検出される。例えば、オブジェクトは、その高さが
負の値になった場合に、その環境の床と衝突する。この
方法は簡単で速いが、複雑な形状または込み入った表面
を有するオブジェクト間の相互作用をモデル化すること
はできない。
【０００６】動力学的シミュレーションの中には、シス
テムダイナミックスの中に動きの制約を組み込むことに
よって衝突を避けたものがある。例えば、システムモデ
ルの中に関節の角度の制限を組み込むことによって、人
間モデルの手または足が体部分を横断することを防げる
場合がある。その同じ手または足の端の単一点が負の値
を有するか否かを判定するために検査を行うことによっ
て、その手または足が床と交差するのを防げる場合があ
る。これらの方法はダイナミックシミュレーションに対
して有用なものとなり得るが、ダイナミックシステムモ
デルが創出される時に、幾何学的形状及び所望の動作に
ついての完全な知識を必要とする。この方法は、複雑な
環境において任意の形状にされたオブジェクトに対して
は、取扱い不能となる。
【０００７】従来のグラフィカルフォーマットにおい
て、オブジェクトは、多辺形または単純表面のリストと
して、単純な立体形状のリストとして、またはこれらの
何等かの組み合わせとしてモデル化される。このフォー
マットにおいて、各リストの構成要素が、本質的には数
学的等式または条件の集合となる。例えば、多辺形表現
における１個の３辺形は、３つの多辺形頂点をある順序
で並べたリストでなっている。この多辺形によって表さ
れる面は、その点と線の３つの組み合わせによって定義
される３つの半平面の交差によって定義される。２つの
オブジェクト間の衝突の可能性を検出するためには、第
１のオブジェクトのリストにおける各単純要素を、第２
のオブジェクトのリストにおける総ての単純要素との共
通部分についてチェックしなければならない。このこと
は、リストの要素の可能な組み合わせのそれぞれについ
て、数学的等式及び条件の２つの集合間の共通部分を求
めることに相当する。
【０００８】各オブジェクトがかなり複雑な場合、それ
ぞれのオブジェクトが数万または数十万の要素を含むこ
とがある。従って、衝突があったか否かを判定するため
には、オブジェクトが動かされるごとに何百万もの方程
式を解かなければならない。共通部分についてチェック
をしなければならない要素対の数を低減するアルゴリズ
ムが導入されているが、複雑なオブジェクト間の衝突の
検出が、依然として、物理的にリアルなモデル化または
シミュレーションを行うとするコンピュータアプリケー
ションにおける大きな時間的妨害要素の１つとなってい
る。
【０００９】特に、二次元及び三次元のグラフィカルオ
ブジェクトの対話式操作を伴うタスクにおいては、アプ
リケーションの速度すなわち対話の程度が、物理に基づ
くモデル化及び三次元環境の視覚化のために必要な計算
によって限定されたものになる。グラフィックス描画ハ
ードウェアの進歩が、従来のグラフィカルオブジェクト
の視覚化のための描画速度を大きく向上させてきた。し
かし、オブジェクト間の衝突を検出するため及びこれら
の衝突から生じる反作用の力及び動きを求めるために必
要な計算が、それぞれ、対話式グラフィックスアプリケ
ーションにおいて表現することのできるオブジェクトの
数及び複雑さを制限している。
【００１０】オブジェクトがより複雑になるにしたがっ
て、衝突を検出するために必要な計算の量が指数関数的
に増大し得る。オブジェクト空間を区分したりバウンデ
ィングボックスまたは特別なデータ構造を用いたりする
アルゴリズムによって、必要とされる計算の数を減らす
ことができる。しかし、各オブジェクトが仮想空間の中
を自由に動き回る場合、オブジェクトが複雑または入り
組んだ形状でなる場合、またはオブジェクトが密に接触
している場合は、これらのアルゴリスムは効果的ではな
い。したがって、衝突の検出は、対話式コンピュータグ
ラフィックスアプリケーションに重大な制約をもたらし
得るものであり、自由に動き回る複雑なオブジェクト間
の実時間の衝突検出を行うためのより良い方法が求めら
れている。
【００１１】さらなる背景として、新しい撮像及びデー
タサンプリング技術はデータの多次元アレーを大量に結
果としてもたらした。この容量分析またはボクセルに基
づくデータは、一般に数十万または数百万のデータポイ
ントを含んでいる。このフォーマットのデータを視覚化
しかつ探る必要が、ボリューム視覚化の分野の開発につ
ながった。例えば、磁気共鳴イメージングＭＲＩやコン
ピュータ断層写真撮影法ＣＴ等の医療撮像技術は、生き
ている患者の体内構造の三次元イメージを生成すること
ができる。これらの三次元イメージは、腫瘍、骨折部分
及び数多くの他の病状を見つけるために用いることので
きる組織の密度または構成についての詳細な情報を含む
ものである。多次元的にサンプリングされたデータの他
のソースとしては、地震のイメージ、気象観測気球によ
る温度、天候及び圧力の測定値、及び流体の流れまたは
分子モデル化のシミュレーションにおいて生じる多次元
データが含まれる。
【００１２】これらの大きなデータボリュームによって
もたらされる問題の１つは、二次元イメージで、または
二次元コンピュータ画面上において、どのように多次元
データを視覚化するかということにある。三次元または
容量分析データに対して、データを表す３つの基本的方
法がある。
【００１３】第１の方法は、三次元データを通じての二
次元断面の集合をユーザに呈示するものである。ユーザ
は、対象の構造を視覚化するために、頭の中で三次元イ
メージを再構成しなければならない。ほとんどの放射線
科の検査室においては、この方法が依然として選択さ
れ、ＭＲＩまたはＣＴイメージが一連の二次元画像とし
て外科医または放射線医に呈示される。しかし、それら
のイメージが複合骨折等の複雑な三次元構造を示す場
合、この方法を用いて骨折の程度を視覚化することは極
めて困難となり得る。
【００１４】第２の呈示の方法は、容量分析データを、
従来のグラフィックスアプリケーションを用いて操作す
ることのできる従来のグラフィックス上のモデルに変換
するものである。モデルを生成するためには、対象物の
造作上の表面点を検出し、対象物の構造の表面を描く多
辺形または単純面のリストを作り出すのに用いる。この
方法は、骨の表面がＣＴイメージにおいて周囲の組織か
ら容易に分離され、かつ骨及び骨折のグラフィックス上
の表現を移植または筋・関節補強回復装置の大きさを求
めるための測定に用いることができることから、整形外
科の用途において特に有用であった。
【００１５】しかし、この方法は、グラフィカルオブジ
ェクトを作り出す際に、どこに面が存在するかについて
仮定をしなければならないことから限定されたものとな
る。このことが、イメージの正確さに大きく影響する誤
差をオブジェクトモデルに持ち込むことになり得る。例
えば、面を作り出す際に、面検出アルゴリズムの感度を
変化させることによって、骨折部分が、グラフィックス
表示において、過度に強調されるかまたは見落とされる
ことになり得る。また、面上の各点を除いたすべてのデ
ータが捨てられる。このことは、基本的には、豊富な容
量分析データを、対象物の構造の回りの表面の殻の集合
に変換することである。
【００１６】ボリューム描画が、容量分析データを視覚
化するための第３の方法である。これは１９７０年代に
提起され、１９８０年代の終りごろから普及してきたも
のである（例えば、A.Kaufman,“Volume Visualizatio
n”,IEEE Comp.Society,Society Press, 1991年 参
照）。この方法においては、データボリュームにおける
各点に色と透明度が割り当てられる。全データボリュー
ムを通過する光線上の個別のボリューム要素の効果を積
み上げることによって、イメージを通しての二次元図が
形成される。オブジェクトが透明である場合、データを
通じて内部構造を二次元図において見ることができる。
色及び透明度を調節することによって、データにおける
異なる構造及び特徴をよく見えるようにも、見えないよ
うにもすることができる。
【００１７】ボリューム描画が上述した種類の容量分析
データを視覚化するための強力な武器であることは実証
されている。しかし、また、これが他の幾つかのグラフ
ィックスアプリケーションに対しても有用であることが
実証されている。例えば、ボリューム描画法を、煙、
霧、滝を流れる水等の無定形の物質のリアルなイメージ
を生成するために用いることができる。１９９０年代の
初めにおいて、テーブルと椅子、グラスまたは反射をす
る球面等の一般的なグラフィカルオブジェクトを表現す
るアイディアが提起された（その概観について、A.Kauf
man,D.Cohen,andR.Yagel,“Volume Graphics”,Compute
r,July,1993,pp.51-64 を参照）。一般的なグラフィカ
ルオブジェクトを容量分析フォーマットで表現すること
は、ボリュームグラフィックスと名付けられた。
【００１８】すなわち、ボクセルに基づくオブジェクト
モデル化表現においては、各オブジェクトは、多辺形ま
たは単純な面または形状のリストとしてではなく、規則
的または不規則的にサンプリングされたボリューム要素
の二次元または三次元のアレーとして表現される。ボク
セルとも呼ばれるこれらのボリューム要素は、一般に、
オブジェクトのその点における色及び透明度についての
情報を含んでいる。しかし、オブジェクトの種類の識別
子、材料の性質、サンプリングされた点において垂直な
面、及び隣接する各点への接続についての情報等の他の
情報も、各ボクセルに符号化して入れることができる。
最近になるまで、ある程度の大きさのボリュームを描く
のには、上位のワークステーションにおいて数分間を要
した。
【００１９】しかし、ボクセルに基づくデータの性質に
より、ボリューム描画アルゴリズムは、極めて並列化し
易いものである。ボリューム描画のためのより高速のア
ルゴリズム及び特殊目的ハードウェアが、かなりの大き
さ及び解像度のデータの実時間ボリューム描画を可能に
している。したがって、ボリュームグラフィックスにお
ける記憶装置の必要量は一般的なグラフィカルオブジェ
クトのための記憶装置の必要量よりもずっと大きなもの
となるが、記憶装置がより安価になり、かつボリューム
描画アルゴリズム及びハードウェアが向上するのにした
がって、容量分析データ表現の鮮やかさ及び規則正しさ
が、ボリュームグラフィックスをグラフィックスの用途
においてより魅力的なものにしている。
【００２０】ボリュームグラフィックスを用いて、一般
的なグラフィカルオブジェクトを、ボクセルに基づくフ
ォーマットで表現することができる。依然として残って
いる重要な問題の１つが、ボクセルに基づくオブジェク
トが物理的にリアルに相互に作用するようにどのように
それらを操作するかである。例えば、容量分析医療用イ
メージにおいて、ボクセルに基づくフォーマットで表現
された個別の骨の構造を、一般的なグラフィックスフォ
ーマットに変換された場合にできるのと同じように操作
することができれば有用である。例えば、外科医は、骨
のモデルをそのソケット関節の中で回転して、骨のモデ
ルが関節の側部に接触した場合に動きを制限するものを
検出することができ、あるいは、外科医は、手術のシミ
ュレーションにおいてボクセルに基づく骨のモデルの中
を予定の切開路にそって管の挿入のテストをすることが
できる。
【００２１】したがって、ボリュームグラフィックスを
その現在具現化されているボクセルに基づくグラフィカ
ルオブジェクトの視覚化からボクセルに基づくオブジェ
クトの物理的にリアルな操作を含むものに拡張すること
ができるように、ボクセルに基づくフォーマットで表現
されたオブジェクトが互いに対しかつそれらの環境とど
のように相互作用するかを明確にするシステムまたは機
械が求められている。特に、ボクセルに基づくオブジェ
クト間の物理的にリアルな相互作用をモデル化する方法
の必要は、実時間アプリケーションにおける複雑なオブ
ジェクト間の衝突の検出を条件としている。
【００２２】特に、手術前の計画のために開発されたシ
ステムには、オブジェクト及び手術における切開の形状
を表すボクセルに基づくモデルを操作するものがある。
これらの中には、異なるオブジェクト間またはオブジェ
クトと切開形状との間の共通部分を検出することができ
るシステムがある。“Representation,Display,and Man
ipulation of 3D digital screens and their Medical
Applications”(L.Chen and M.Sontag,Computer Visio
n,Graphics,and Image Processing,48,1989,pp.190-21
6)によるものにおいては、ユーザによって定められた切
除ボリュームを対象オブジェクトと交差させて、その切
除ボリュームの手術による取り除きのシミュレーション
を行う。しかし、オクトリーに基づくオブジェクト表現
はボリュームグラフィックスのボクセルアレーに基づく
表現とは異なっており、このシステムはオブジェクトの
動きを制御または制限するために共通部分を用いること
はない。
【００２３】同様に、“Manipulation of Volume data
for Surgical Simulation”(in “3D Imaging in Medic
ine”,S.Arridge,eds.K.Hohne et al,Springer-Verlag,
1990)による第２のシステムにおいては、オブジェクト
ボリュームは、ボクセルに基づく表現ではなくオクトリ
ー表現で格納される。オブジェクト間の重なりは、異な
るオブジェクトのオクトリーについてのブール演算によ
って検出される。また、これらの重なりは、オブジェク
トの動きを制御または制限するために用いられるもので
はない。
【００２４】“Computer System for Craniofacial Sur
gical Planning based on CT images”(Yasuda et al,I
EEE Trans. on Med.Imaging,9,1990,pp.270-280)による
第３のシステムにおいては、データは、二次元イメージ
平面の連続としてボクセルに基づくフォーマットで格納
される。しかし、切除ボリュームは多辺形形状に深さを
加えたものによって定義される。オブジェクトと切除ボ
リュームとの間の重なりの検出は、ボクセル毎になされ
るのではなく、代わりに、多辺形を走査によって変換す
ることによって各データ平面において切除ボリュームを
取り除き、切除ボリューム内にあるデータポイントを判
定する。
【００２５】“Simulating Femoral Repositioning wit
h Three-dimensional CT” (J.Gerber et al.,J.Comput
er Assisted Tomography,15,1991,pp.121-125)による第
４のシステムにおいては、個別のボクセルに基づくオブ
ジェクトが表現され、移動させられる。移動が完了した
後に、ボリューム描画のために総てのオブジェクトを含
む複合ボリュームを再生成する。しかし、その論文に記
載されるシステムは、オブジェクトの配置または移動を
制御するために重なり領域を用いることを考慮していな
い。
【００２６】従来のグラフィックスモデルから衝突及び
干渉を検出する２つの関連したシステムがある。“Inte
ractive Inspections of Solids:Cross-sections and I
nterference”(J.Rossignac et al.,Computer Graphic
s,26,1992,pp.353-360)による第１のものにおいては、
固体モデルを通しての二次元断面におけるオブジェクト
間の共通部分が、二次元断面を画面ピクセルに走査変換
し、異なるオブジェクトのピクセルマップ間の重なりを
探すことによって見つけ出される。ボクセルに基づくオ
ブジェクトモデルと異なり、この干渉検出方法は、対象
となる各断面について固体幾何学的モデルから二次元ピ
クセル表現へのデータ変換を必要とする。
【００２７】“Solving theCollision Detection Probl
em”(A.Garcia-Alonso et al.,IEEEComputer Graphics
and Animation,May,1994, pp.36-43)による第２のシス
テムにおいては、システムが、多辺形オブジェクトモデ
ルの面間の衝突検出のための探索空間を限定するための
“ボクセル”に基づく方法を含んでいる。しかし、この
システムにおいて述べられている“ボクセル”は、オブ
ジェクトをほぼ８×８×８の面の集まりに空間的に再区
分するものであり、したがって、ボリュームグラフィッ
クスのサンプリングされたデータボクセルとは極めて異
なるものである。
【００２８】要約していうと、グラフィカルオブジェク
ト間の衝突の検出は、コンピュータグラフィックス、コ
ンピュータアニメーション及び仮想現実における重要か
つ興味深い問題である。多辺形、単純面または単純な固
体の幾何学形状を用いる従来のグラフィックス表現には
２つの大きな制限がある。まず、それらは医療イメージ
等のある種のデータを表現するのには適当ではなく、そ
して、第２に、任意のグラフィカルオブジェクト間の衝
突の検出は、本質的に数学的に極限的なものである。
【００２９】一方、ボクセルに基づくデータ表現は、内
部及び表面の両方のデータ構造を表現するための簡単で
なおかつ強力な手段を提供する。切除ボリュームとボク
セルに基づくオブジェクトとの間または２つの多辺形モ
デルの間の重なりを横断面において重複するピクセルを
用いて判定するために用いることのできるシステムが幾
つか存在するが、これらのシステムは、衝突または共通
部分を判定するためにボクセルに基づくオブジェクト表
現間のボクセル毎の比較を用いるものではない。
【００３０】さらに、ほとんどの場合、用いられるデー
タ構造は、ボリュームグラフィックスの単純ボクセルア
レー構造とは異なる。また、これらのシステムは、オブ
ジェクトの動きを制限または制御するためにオブジェク
ト間の重なりまたは共通部分についての情報を用いるも
のではない。そして、これらのシステムは、グラフィカ
ルオブジェクトの静止形態に対する重なりまたは共通部
分の計算を行うものであり、移動しているオブジェクト
の実時間の衝突検出を行ったり表示しようとする試みは
なされていない。
【００３１】
【発明が解決しようとする課題】上述したように、従来
のグラフィックスにおいては、衝突の検出は、計算的に
集中的なものであることからその速さが遅くなる。従来
のグラフィックスにおいて、各オブジェクトは、多辺
形、単純面または単純な幾何学的形状のリストによって
表現される。複雑なオブジェクトは、数万から数十万の
これらの幾何学的単純要素からなることがある。あるオ
ブジェクトが仮想空間内で移動した場合、要素の共通部
分について数学的に解くことによって、他の総てのオブ
ジェクトの要素に対してそのオブジェクトの各要素を検
査しなければならない。各オブジェクトがより複雑にな
るにしたがってオブジェクト間の衝突を検出するために
必要な計算の量が指数関数的に増大することがわかる。
計算しなければならない数学的共通部分の数を低減する
ためのアルゴリズムは存在するが、それらは、密に接触
している自由に移動する複雑なオブジェクトに対しては
比較的有効ではない。
【００３２】この発明は上述した課題を解決するために
なされたもので、ボクセルに基づくフォーマットで表現
された自由に動き回る複雑なオブジェクト間の実時間の
衝突を検出可能にし、かつ仮想空間におけるグラフィカ
ルオブジェクトが互いの中に侵入するのを防ぐようにグ
ラフィカルオブジェクト間の移動及び相互作用を可能に
するボクセルに基づくオブジェクト表現のための衝突回
避システムを得ることを目的とするものである。
【００３３】
【課題を解決するための手段】この発明に係るボクセル
に基づくオブジェクト表現のための衝突回避システム
は、ボクセルに基づくグラフィカルオブジェクトが表示
画面を動き回る場合に互いの中に入り込むのを防ぐボク
セルに基づくオブジェクト表現のための衝突回避システ
ムにおいて、上記表示画面上への表示のためにボクセル
に基づくオブジェクトを生成する手段であって、上記オ
ブジェクトが動かされる仮想空間を表し、上記仮想空間
中のオブジェクトが対応する画面上の場所において対応
する画面上のオブジェクトを有する記憶アレーと、この
記憶アレーにボクセルに基づくオブジェクトに対応する
ボクセルに基づくデータを格納する手段とを含み、上記
記憶アレーの一部が上記格納されたオブジェクトのボク
セルに基づく占有マップを表し、上記ボクセルに基づく
占有マップが上記仮想空間を表すようになされたオブジ
ェクト生成手段と、上記記憶アレー内の対応する記憶場
所において個別のオブジェクトをデータとして上記占有
マップにマッピングするマッピング手段と、上記仮想空
間において上記オブジェクトを移動させる移動手段と、
任意のオブジェクトに対応するデータを上記データによ
って以前に占められていたものとは異なる場所に書き込
むことによって、オブジェクトが上記仮想空間を動き回
るのにしたがって上記占有マップを更新する更新手段
と、上記任意のオブジェクトの上記仮想空間における移
動中に、上記任意のオブジェクトに付随するデータが上
記オブジェクトの別の１つからのデータが既に存在する
記憶場所に書き込まれようとしている場合を検出する衝
突検出手段と、上記移動を実現するために上記オブジェ
クトに対するデータが書き込まれようとしている既に占
有されている占有マップの場所の検出によって、上記任
意のオブジェクトに付随する画面上の表現の画面上の動
きを阻止する阻止手段とを備えたことを特徴とすること
により、ボクセルに基づくフォーマットで表現された自
由に動き回る複雑なオブジェクト間の実時間の衝突を検
出可能にし、かつ仮想空間におけるグラフィカルオブジ
ェクトが互いの中に侵入するのを防ぐようにグラフィカ
ルオブジェクト間の移動及び相互作用を可能にするもの
である。
【００３４】また、上記オブジェクト生成手段、上記マ
ッピング手段、上記更新手段、上記衝突検出手段及び上
記阻止手段を、ユーザインタフェースと相互に作用する
ための入力装置に接続されたグラフィックスワークステ
ーションに備えられると共に、上記移動手段を、上記グ
ラフィックスワークステーションに接続され該グラフィ
ックスワークステーションの表示画面上でグラフィカル
オブジェクトの位置及び配向を変化させる入力トラッカ
で構成したことにより、簡単なハードウエアでシステム
を構成するものである。
【００３５】さらに、上記入力トラッカを、二次元のグ
ラフィックス上のオブジェクトの位置及び配向を変化さ
せる２自由度のコンピュータマウスまたは三次元のグラ
フィックス上のオブジェクトの位置及び配向を変化させ
る６自由度のトラッカで構成することにより、グラフィ
カルオブジェクトとして二次元及び三次元の適用範囲に
拡大可能にするものである。
【００３６】
【発明の実施の形態】図１はこの発明に係るボクセルに
基づくオブジェクト表現のための衝突回避システムを説
明するためのもので、ボクセルに基づくグラフィカルオ
ブジェクトを視覚化しかつ操作する対話式環境において
必要とされる主要なハードウェア要素を図式的に表す図
である。図１において、この発明において用いられるハ
ードウェアは、計算、記憶格納及び画像表示のためのハ
イエンドグラフィックスワークステーション１０と、ハ
イレベルプログラム制御のためにユーザインタフェース
と相互に作用するためのキーボード１２（または他の入
力装置）と、グラフィカルオブジェクト１６及び１８の
位置及び配向を変化するために用いることのできる入力
トラッカ１４とで構成されている。
【００３７】実施の形態の１つにおいては、この入力ト
ラッカ１４は、二次元オブジェクトの位置または配向、
三次元オブジェクトのうちの６自由度のうちの２つを制
御するために用いることのできる２自由度のコンピュー
タマウスでなっている。第２の実施の形態においては、
６自由度トラッカ２０を用いて、三次元のグラフィカル
オブジェクトの位置及び配向を制御する。
【００３８】また、図２はハイエンドグラフィックスワ
ークステーション１０において必要とされる３つの記憶
構造を図式的に表す図である。図２について、実施の形
態の１つにおいては、オブジェクト及び仮想空間につい
ての情報は、３つの別個のデータ構造２４、２５及び２
６において維持される。これらの３つの別個のデータ構
造は、最近のグラフィックスワークステーション１０の
記憶の限界及びメモリアクセスパターンで機能すること
を必要とする。しかし、別の記憶アーキテクチャでは、
この３つのデータ構造における情報の総てを、衝突検
出、オブジェクト操作及び視覚化を行うために、例えば
並行記憶アーキテクチャで迅速にアクセスすることので
きる１つの大きなアレーに組み込むことを可能にするこ
とがわかる。
【００３９】ここで、データ構造２４は、どのボクセル
がどのオブジェクトによって占められているかを符号化
するのに用いられる占有マップと呼ばれる仮想空間の大
きさを有するアレーである。占有マップ２４の各要素
は、オブジェクトのコード番号または空のボクセルを示
すコード番号を含んでいる。
【００４０】また、データ構造２５は、オブジェクトア
レーと呼ばれ、各オブジェクト毎に存在し、そのオブジ
ェクトにおける各サンプリングされた点についてのボク
セルの色、透明度、及び他の視覚的、構造的、及び材料
的特性を含んでいる。実施の形態の１つにおいては、オ
ブジェクトアレー２５は、ボクセルの色、透明度、サー
フェス法線ベクトルを含んでいる。オブジェクトアレー
２５のボクセルの内容は、運動の誤りが蓄積されること
のないようにオブジェクトが移動するのにつれて変化す
ることはない。オブジェクトアレー２５は、ボリューム
描画のためのデータソースとして用いられる。各オブジ
ェクトを通しての二次元図が計算され、全仮想空間を通
しての図が作られるときに合成される。イメージ平面か
らの各オブジェクトの相対的距離を用いて合成の順序を
決定する。
【００４１】さらに、データ構造２６は、仮想空間内の
各オブジェクトについて存在し、占有マップ２４を埋め
るために用いられる各点の最初及び現在の位置を含むエ
ッジリストである。実施の形態の１つにおいては、この
エッジリスト２６は、各オブジェクトの縁または表面上
の点で構成されている。第２の実施の形態においては、
このリストが内部及び面上の点の両方を含んでおり、そ
れぞれのオブジェクトの動きの途中において、飛んでい
るうちにオブジェクトアレー２５から作り出される。な
お、エッジリスト２６は、アプリケーションによって、
縁または表面の点及び／または内部のオブジェクト点で
構成することができる。
【００４２】次に、図３はグラフィカルオブジェクトの
オブジェクトアレー表現への変換を図式的に表す図であ
り、これが次に衝突検出の目的で占有マップ内の場所に
変換される。図３において、一般に、占有マップ２４
は、グラフィカルオブジェクト３３から生成が開始され
る。このグラフィカルオブジェクト３３におけるオリジ
ナルデータまたはオブジェクト記述を、図示のようにア
レーが位置Ｐ１及び配向Ｑ１を有するオブジェクトアレ
ー３７のボクセルに基づく表現３５に変換する。各ボク
セル３６は、とりわけ、色、透明度及び反射率のパラメ
ータを含む属性を有することができる。したがって、オ
ブジェクトアレー３５における各ボクセルは、特定の位
置及び配向を有することに加えて、いくつかの属性のい
ずれをも示すデータを備えることができる。
【００４３】オブジェクト３３’で示すように、オブジ
ェクトアレー３７のデータを、二次元画面３９上のグラ
フィカルオブジェクトの描画に用いることができる。こ
れは、オブジェクトアレー３７からの三次元のボクセル
に基づく表現からオブジェクトの二次元描画に変換する
ボリューム描画装置４１を利用することによって達成さ
れる。あらかじめ描画されたオブジェクト３３’に隣接
して第２のグラフィカルオブジェクト４３を配置するこ
とが重要な場合、第２のオブジェクト４３の移動に際し
て、それがすでに存在するオブジェクトに接触するかま
たは入り込むならば、そのような描画を禁止することが
重要である。
【００４４】そのような衝突を検出するために、オブジ
ェクトアレー３７におけるボクセルは座標変換器４５で
占有マップ座標に変換され、オブジェクトを表すアドレ
スまたは符号は占有マップ２４において領域４７に格納
される。なお、実施の形態の１つにおいては、占有マッ
プ２４における１ボクセルの位置を（ｉ，ｊ，ｋ）で示
す。この位置データは、したがって、オブジェクトアレ
ーの各離散ボクセルに対して入れられる。なお、処理を
簡単にするため、オブジェクトアレー３７のすべてのボ
クセルを占有マップ２４に入れる必要はなく、前述した
ように、オブジェクトの縁を表すボクセルのみを考慮す
る必要がある。そのようなボクセルは、上述のオブジェ
クトのためのエッジリストから得ることができる。
【００４５】オブジェクトアレー５１に示されるよう
に、このオブジェクトアレー５１にはオブジェクト３３
に対して移動させることが望ましい第２のオブジェクト
４３の表現を含んでいる。そのため、座標変換器５３に
示すように、オブジェクトデータが占有マップ座標に変
換され、それが次に領域５５に示すように、占有マップ
２４に入れられる。図３に見られるように、領域４７及
び５５の占有マップコードまたはアドレスが領域５７に
おいて重なり、衝突検出手段５９において検出される衝
突を示している。この衝突の検出によって、二次元画面
３９上に描画される第２のオブジェクト４３の動きを移
動禁止手段６１に示すように禁止することができ、ボリ
ューム描画装置６３によるこの第２のオブジェクト４３
の三次元から二次元の描画を禁止する。
【００４６】本システムを、衝突検出によるオブジェク
トの動きの禁止に関して説明するものであるが、状況に
よってはあるオブジェクトの別のものへの相互侵入を許
すことが可能であることがわかるはずである。そのよう
なアプリケーションには、オブジェクトの縁におけるボ
クセルに付随する力ベクトルに基づいて相互侵入をさせ
るものが含まれる。
【００４７】次に、図４はボクセルに基づくグラフィカ
ルオブジェクト間の衝突を検出するこの発明の一実施の
形態において必要とされる基本的各段階を概略的に示す
フローチャートである。図４において、この発明のソフ
トウェアの一実施の形態の主要な構成要素は、初期化シ
ーケンスＳ２７と、オブジェクトの配置の対話式制御を
行う主ループ（対話式オブジェクト制御シーケンス）Ｓ
２８と、対話セッションを終了するための出口シーケン
スＳ２９とで構成されている。
【００４８】初期化シーケンスＳ２７では、ステップＳ
３０において、３つのデータ構造のそれぞれに対して記
憶装置が割り当てられる。ステップＳ３４において、格
納されたオブジェクトデータが図２のオブジェクトアレ
ー２５に読み込まれ、ボリュームデータを初期化する。
この時点で、エッジリスト２６は、オブジェクトアレー
２５から計算されるかまたはステップＳ３４において記
憶装置から読み込まれる。次に、個別のオブジェクトの
エッジリスト２６及び最初の位置及び配向を用いて、占
有マップ２４を初期化する。そして、ステップＳ３８に
おいてワークステーション１８のグラフィックス表示装
置が初期化され、ステップＳ４０において入力トラッカ
２０が初期化される。
【００４９】動作において、システムは４つの主要な機
能を実施する。第１には、ステップＳ５２においてユー
ザインタフェース３１からの入力をチェックして、高レ
ベルプログラム制御を求める。第２の機能は、ステップ
Ｓ５６及びＳ５８において、入力トラッカ２０の動きを
求めるものである。第３の機能は、衝突検出機能６０に
おいて示されるように、仮想空間における選択された移
動しているオブジェクトと他のオブジェクトとの間の衝
突の検出である。第４の機能は、オブジェクト移動機能
６２において示されるように、衝突が起きないと判定さ
れたときに、選択されたオブジェクトを移動し、ユーザ
に対して新しいシーンを表示することである。
【００５０】第１の機能においては、ステップＳ５２に
おいて、ユーザインタフェース３１を入力についてチェ
ックする。入力が発生した場合、ステップＳ６４におい
てエスケープシーケンスが検出されると、プログラムは
出口シーケンス２９へと分岐する。出口シーケンス２９
においては、ステップＳ６６に示すように入力トラッカ
２０がクローズされ、ステップＳ６８において示すよう
に記憶装置が割り当てを解除され、ステップＳ７０にお
いて示すようにプログラムを出る。ステップＳ７２にお
いてオブジェクト選択入力が検出された場合、示された
オブジェクトがステップＳ７４において選択されたオブ
ジェクトになり、トラッカ２０の旧位置及び旧配向が、
トラッカ２０の現在の位置及び配向に設定される。この
実施の形態においては他の総てのシステム入力が無視さ
れる。
【００５１】第２の機能においては、ステップＳ５４に
おいてオブジェクトが現在選択されている場合、ステッ
プＳ５６において入力トラッカ２０の位置及び配向が読
まれる。新しい位置及び配向がトラッカ２０の旧位置及
び旧配向から有意に異なると、ステップＳ５８において
装置の動きが検出され、プログラムが衝突検出機能６０
へ分岐し、所望の新しい位置及び配向における衝突を求
める。オブジェクトが選択されない場合またはトラッカ
の有意の動きが検出されない場合、プログラムは、ステ
ップＳ５２において、メインボディの第１機能にループ
して戻る。
【００５２】衝突検出機能６０においては、ステップＳ
８０において望ましい位置ステップが、トラッカ２０の
新しい位置とその旧位置との差として定義される。選択
されたオブジェクトの望ましい位置は、ステップＳ８２
において、選択されたオブジェクトの現在位置プラス位
置ステップとして計算される。望ましい配向ステップ
は、ステップＳ８０において、トラッカ２０をその旧配
向からその新しい配向にする回転として定義される。こ
の実施の形態においては、配向は四元数によって表され
る。四元数は、それらが回転マトリックスに比較して蓄
積誤差を生じにくいことから、回転を符号化するために
グラフィックスにおいてよく用いられる。それらは、定
数と三次元ベクトルとの２つの部分でなり、１８４３年
にSir William R.Hamiltonによって最初にとり入れられ
た。配向及び配向の変化を表すために四元数を用いる
と、所望の配向を、ステップＳ８２において、配向ステ
ップによって現在の配向四元数をあらかじめ乗ずること
によって得ることができる。しかし、回転を配向マトリ
ックスによって表し、所望の配向マトリックスを、現在
の配向マトリックスに配向ステップマトリックスをあら
かじめ乗ずることによって計算するようにすることもで
きる。
【００５３】選択されたオブジェクトの所望の配向及び
位置が与えられると、ステップＳ８４においてリストの
各要素の現在位置を更新することによって新しいエッジ
リスト２６が造り出され、ステップＳ８６において新エ
ッジリスト２６の各点に対応する点において占有マップ
２４がチェックされる。占有マップの対応する点のいず
れかが他のオブジェクトによって占有されている場合、
衝突が生じ、ステップＳ８８において二等分法を用い
て、衝突を生じない所望のステップ以下の最大の位置及
び配向ステップが見つかるまで、位置ステップ及び配向
ステップの両方を小さくする。衝突を起こさない位置及
び配向ステップが見つかると、プログラムはオブジェク
ト移動機能６２に進む。
【００５４】オブジェクト移動機能６２では、ステップ
Ｓ９０において、旧エッジリストを減算し、かつ所望の
位置及び配向の近辺に選択されたオブジェクトを移動さ
せて衝突を引き起こさなかった位置及び配向ステップに
対応する最新のエッジリストを加算えることによって、
占有マップ２４を更新する。選択されたオブジェクトの
現在位置及び配向を更新し、トラッカの旧位置及び旧配
向を、最終の位置ステップ及び配向ステップを用いてリ
セットする。そして、ステップＳ９２において、選択さ
れたオブジェクトのボリューム描画イメージを、シーン
における他のオブジェクトのボリューム描画イメージと
共にその新しい位置及び配向においてオブジェクトアレ
ーに合成することによってシーンを再描画する。ステッ
プＳ９４において、このシーンをコンピュータ画面に表
示し、対話式レートでユーザに視覚的フィードバックを
与える。
【００５５】なお、本システムを、衝突検出の目的でエ
ッジリストを生成することによってオブジェクトを特徴
づけるものに関して説明してきたが、オブジェクトのボ
クセル表現は内部構造も含むものである。フレキシブル
または変形可能なオブジェクトを調和させるためまたは
あるオブジェクトの他のオブジェクトへの制御された侵
入を可能にするために、オブジェクトアレー全体を用い
て占有マップを更新することができることがわかるはず
である。しかし、占有マップに内部ボクセルを含むめる
ことは、計算量及び記憶必要量を増大する。
【００５６】次に、図５〜図８を参照して、この発明に
したがった衝突検出を二次元オブジェクトについて図式
的に示す。図５〜図８において、陰影をつけたオブジェ
クト８７及び８９が、離散した占有マップセル９１及び
９３において占有マップにマッピングされる。オブジェ
クトが仮想空間において動かされると、セル９１及び９
３が、図６、図７及び図８において示すように更新され
る。これらの図のすべてにおいて、陰影をつけた領域８
８は、マッピングを起こすグラフィカルオブジェクトを
表している。オブジェクトの動きが静止オブジェクトに
よって以前から占められていた記憶装置の点のオーバー
ライトを引き起こす場合、図８の領域９５に示すよう
に、セル９３の１セルがセル９１の１セルに重なり、衝
突が検出される。衝突を検出し、オブジェクトが互いに
侵入するのを防ぐ簡略化されたアルゴリズムは図９に示
される。
【００５７】この実施の形態においては、衝突の検出
は、衝突が起きなくなるまで所望のステップの大きさを
減少させる結果となる。衝突に対するこの反応の結果
は、２つのオブジェクトが相互に侵入することを許すこ
とは絶対に無いということである。なお、衝突に対して
他の反応をすることも可能である。例えば、特定のオブ
ジェクト間の衝突に対する反作用を無視することができ
る。第２の例として、オブジェクトが相互に侵入するこ
とを許す一方で、仮想空間の視覚化において衝突の位置
を示すことによって視覚的、聴覚的、または入力トラッ
カがフォースフィードバックシステムを備えている場合
には触覚的にユーザに衝突を示すことができる。第３の
例として、衝突の位置を、物理に基づくモデル化を用い
るグラフィックスシステムにおける反作用の力を計算す
るために用いることができる。例えば図１０に示すよう
に、グラフィカルオブジェクト９９及び１０１の検出さ
れた衝突点９８における衝撃力９６及び９７の計算を行
うために用いる。なお、エッジリスト及びオブジェクト
アレーにおいて法線ベクトル及び／または材料特性を含
むことによって、この力の計算を容易にする。
【００５８】また、図１１はこの発明の第１の二次元実
施の形態を図式的に示す図であり、複雑な二次元迷路に
おけるその利用を示す図である。図１１のＡ〜Ｄにおい
て、この発明の実施の形態の１つは二次元迷路１００で
あり、侵入することのできない葉の領域１０６によって
定められる迷路を通る通路１０４を含む領域１０２でな
っている。迷路１００に、二次元コンピュータマウス
（この図においては示さず）の制御の下に動き回ること
のできる雨蛙１０８を住ませる。迷路の壁及び蛙の足指
の複雑さが、この迷路の従来のグラフィックス表現にお
ける衝突検出計算を手が付けられないほどに大変なもの
にしている。しかし、迷路壁及び蛙の両方をボクセルに
基づくフォーマットで表した場合、迷路の壁と蛙との衝
突をこの発明を用いて容易に検出することができ、した
がって、蛙を実時間で動き回らせることができる。
【００５９】また、図１２はこの発明の第２の二次元実
施の形態を図式的に示す図であり、二次元ジグソーパズ
ルを組み立てる際のその利用を示す図である。図１２の
Ａ〜Ｄにおいて、この発明の第２の実施の形態は、二次
元ジグソーパズル１２０でなっている。衝突を検出する
ためにパズルピース１２２のボクセルに基づくデータ表
現及びこの発明を用いれば、縁の形状がかなり複雑な場
合においても、パズルを対話式に組み立てることができ
る。
【００６０】また、図１３はこの発明の第３の用途を示
し、図１２のＡ〜Ｄの第２の二次元実施の形態を図式的
に示す図であり、提案されたデザインが物理的に組み立
て得るものであるか否かをテストする際のその利用を示
す図である。図１３のＡ〜Ｄに示したパズル１２８の４
つのピース１３０、１３２、１３４及び１３６は、それ
ぞれそれに隣接するものと個別に適合する。しかし、パ
ズルの平面からそれらの１つを持ち上げることなしに、
４つのピースを一体にに組み立てる方法はない。なお、
この図によって呈示される問題は、設計及び製造におい
て「アセンブラビリティー」として知られている。簡単
にいって、システムの各部分すべてが一体に適合するの
に、そのシステムを組み立てる方法がないというシステ
ムを設計することが可能である。二次元システムにおい
てこの問題を避けることを助けるヒューリスティックス
を生成することは可能であるが、三次元システムにおい
ては問題がずっと複雑になる。この発明の応用の一例と
して、システムのアセンブラビリティーをそれらが製造
される以前にテストするための手段がある。
【００６１】また、図１４はこの発明の三次元実施の形
態を図式的に説明するもので、オブジェクトの配向及び
位置制御を示す図、図１５は図１４のＡ〜Ｃの三次元実
施の形態を図式的に説明するもので、オブジェクトと環
境の壁及び他のオブジェクトとの衝突を示す図、図１６
は図１４のＡ〜Ｃの三次元実施の形態を図式的に説明す
るもので、２つのボクセルに基づくオブジェクトの相互
組み立てを示す図である。図１４のＡ〜Ｃ、図１５のＡ
〜Ｃ及び図１６のＡ〜Ｃにおいて、この発明の別の実施
の形態は、三次元対話式アセンブリシステムである。こ
の実施の形態において、図示したナット１４０、ボルト
１４２及びワッシャー１４４等のオブジェクトはボクセ
ルに基づくフォーマットで表現され、６自由度の位置及
び配向トラッカ２０によって対話式に制御される。図１
４のＡ、Ｂ及びＣは、ボルト１４２の位置及び配向の制
御を示している。図１５のＡ、Ｂ及びＣは、ナット１４
０の制御を示し、図１５のＣにみられるようなナット１
４０とボルト１４２との衝突を示している。この位置制
御及び衝突検出は実時間で行われる。図１６のＡ、Ｂ及
びＣは、ワッシャー１４４及びボルト１４２の対話式ア
センブリを示している。
【００６２】ボクセルに基づく衝突検出及び回避アルゴ
リズムの直接的なアプリケーションの１つは、仮想オブ
ジェクトの三次元面を触感的に探査または“感じる”シ
ステムにある。触感的または手触りの探査は、複雑なデ
ータのための視覚化方法をの価値を増し、変形可能なオ
ブジェクトのシミュレーションにおける貴重なフィード
バックをもたらす。提案されたデータ構造をユーザの手
または指先の比較的小さなボクセルに基づくモデルと共
に用いることによって、ユーザの手とデータとの間の衝
突を検出かつ回避するために必要な計算量は、データそ
れ自体が極めて大きくかつ複雑なものであったとしても
小さなものとなる。触感的な探査のためのボクセルに基
づくシステムにおいては、オブジェクトデータが大きな
静止データアレーに格納される。
【００６３】ユーザの手または指先を表す小さなボクセ
ルに基づくオブジェクトはデータアレー中をシフトさ
れ、ユーザの手の動きをトラッキングする。手のモデル
のボクセルがオブジェクトに属するボクセルに遭遇する
と、フォースフィードバック装置を用いて、手のモデル
による仮想オブジェクトへの侵入を回避するように手の
動きを制限する。オブジェクトに基づくボリューム描画
を用いれば、ボリュームデータのあらかじめ計算された
高画質イメージを、手のダイナミックに計算されたイメ
ージと合成することができる。手のモデルが高速描画の
ために十分に小さいものである限りにおいては、このシ
ステムの視覚化は、対話式利用のために十分な速さのも
のとなる。
【００６４】例として、人間のヒップの例えば高解像度
三次元ＣＴスキャンの触感的探査を考えてみる。このよ
うなシステムにおいては、フォースフィードバックシス
テムを用いて、仮想環境におけるユーザの指先の位置を
トラッキングする。この指先の位置は、占有マップにお
ける単一のボクセルによって表される。指先がヒップ面
に属するボクセルに遭遇すると、フォースフィードバッ
ク装置が、ユーザの指先が仮想オブジェクトに侵入する
であろう方向に動くのを防ぎ、ユーザにヒップ面を“感
じ”させる。ヒップデータと指先の三次元ボリューム描
画イメージの立体写真が、立体ゴーグルを介してユーザ
に呈示される。ヒップデータのあらかじめ計算されたボ
リューム描画イメージを用いて、視点のある程度の制御
を実時間で可能にしている。
【００６５】上述したように、この発明を要約すると次
のようになる。この発明においては、ボクセルに基づく
オブジェクトに対する衝突検出が数学的解析をまったく
必要とせず、したがって簡単で速い。各オブジェクト
は、記憶装置における等間隔の位置において物理的に格
納されるサンプリングされたデータポイントによって表
現される。オブジェクトが仮想世界の中で移動すると、
そのデータが記憶装置内でシフトされる。あるオブジェ
クトからのデータボクセルが別のオブジェクトのボクセ
ルによって占められた記憶セルに書き込みをしようとし
た場合に衝突が自動的に検出される。これらの衝突検出
を、オブジェクトの移動を制限または制御するために用
いることができる。この発明は、ハイエンドグラフィッ
クスワークステーションにおいて、比較的複雑な三次元
のボクセルに基づくグラフィカルオブジェクト間の衝突
の実時間検出を可能にするものである。
【００６６】実施の形態の１つにおいては、ボクセルに
基づくオブジェクトが、オブジェクトの移動中に衝突が
自動的に検出され、グラフィカルオブジェクトが互いに
対して入り込むのを防ぐように制御、走査される。この
用途には、複雑な三次元オブジェクトモデル間の実時間
相互作用を必要とするコンピュータグラフィックス及び
アニメーション、ＣＡＤ／ＣＡＭ、及び仮想現実アプリ
ケーションが含まれる。
【００６７】実施の形態の１つにおいては、ボクセルに
基づくオブジェクト間の衝突検出が、仮想空間全体のボ
クセルに基づく占有マップが維持されることを必要とす
る。仮想空間における個別のオブジェクトのボクセルは
占有マップにマッピングされる。オブジェクトが仮想空
間に対して移動すると、各ボクセルが空となるかまたは
そこに存在するオブジェクトのコードを含むようにこの
占有マップが更新される。仮想空間において移動してい
るオブジェクトは、占有マップのメモリにおける符号化
されたボクセルのシフトを伴い、あるオブジェクトから
のデータが別のオブジェクトによって占有されたメモリ
セルに書き込みをしようとした場合に衝突が自動的に検
出される。したがって、従来のグラフィックスとは異な
り、ボリュームグラフィックスにおける衝突検出はオブ
ジェクトの複雑さとは無関係であり、オブジェクトにお
けるサンプリングされたデータポイントの数にのみ左右
される。ボリュームグラフィックス表現における衝突検
出の速度は、メモリアクセスレートによってのみ限定さ
れる。
【００６８】実施の形態の１つにおいては、２つの別個
のデータ構造を用いて、記憶必要量を最小にし、仮想環
境に対して容易に更新される構造を設定する一方で、移
動している複雑なオブジェクトの統合性を維持する。仮
想環境の次元を有する占有マップを用いてオブジェクト
間の相互作用及びその環境における大域的変化を監視す
る。占有マップの各エレメントは１アドレスに対して十
分な大きさのものであり、ゼロポインタまたはオブジェ
クトボクセルデータ構造のアドレスを含んでいる。色、
不透明度、反射率係数、ベクトルの傾き、材料の性質、
位置、近接のアドレス等で構成されるボクセルデータ構
造が、圧縮したオブジェクトアレーに格納される。占有
マップは、オブジェクト空間座標におけるボクセルの位
置及びオブジェクト空間から仮想環境空間へのマッピン
グ変換を用いて各オブジェクトのボクセルのアドレスを
占有マップにマッピングすることによって初期化され
る。
【００６９】つまり、仮想環境においてオブジェクトを
モデル化した場合、オブジェクト間の相互作用を物理的
にリアルにモデル化することが重要である。例えば、多
くの場合、オブジェクトが互いに入り込むことを防がな
ければならないし、それらが、運動量とエネルギーとを
交換することによって、また可能なら衝撃に際しての変
形によって衝突に対して反応すべきである。オブジェク
ト間の相互作用をモデル化する第１の段階は、移動する
オブジェクト間の衝突の検出を必要とする。
【００７０】面に基づくグラフィックスフォーマットに
おいては、オブジェクトは、多辺形または他の単純な面
要素のリストとしてモデル化される。このフォーマット
においては、各要素が基本的には数学的等式または条件
の集合である。例えば、１つの三辺形は、３つの頂点の
順序だったリストで構成される。多辺形平面要素は、各
多辺形頂点によって定義される３つの半平面の共通部分
である。２つのオブジェクト間の衝突の可能性を検出す
るためには、第１のオブジェクトにおける各要素を、第
２のオブジェクトにおける多数の要素との共通部分につ
いて検査しなければならない。このことは、オブジェク
ト要素の可能な組み合わせのそれぞれについて数学的等
式及び条件の２つの集合間の共通部分について解くこと
に相当する。ある程度複雑なオブジェクトは、数千の面
要素で構成される場合がある。共通部分について検査し
なければならない要素対の数を低減するアルゴリズムが
導入されているが、複雑なオブジェクト間の衝突検出
は、物理的にリアルなモデル化またはシミュレーション
を行うコンピュータアプリケーションにおける主要な計
算動作の１つとして依然と存在する。
【００７１】対照的に、ボクセルに基づくオブジェクト
に対する衝突検出は概念的に簡単であり、数学的解析を
必要としない。オブジェクトが仮想環境において移動さ
せられるのにしたがって、オブジェクトボクセルアドレ
スは占有マップアレー内において単にシフトされる。あ
るオブジェクトからのボクセルアドレスが他のオブジェ
クトのボクセルアドレスによって既に占められている占
有マップセルに書き込みをしようとした場合に衝突が自
動的に検出される。
【００７２】この発明の好ましい実施の形態を上述した
ことにより、当業者には、この発明の本旨の内で変更及
び変化をなし得ることが明らかであろう。したがって、
この発明の範囲を、請求の範囲において示されるような
ものにのみ定義しようとするものである。
【００７３】
【発明の効果】以上のように、この発明によれば、ボク
セルに基づくグラフィカルオブジェクトが表示画面を動
き回る場合に互いの中に入り込むのを防ぐボクセルに基
づくオブジェクト表現のための衝突回避システムにおい
て、上記表示画面上への表示のためにボクセルに基づく
オブジェクトを生成する手段であって、上記オブジェク
トが動かされる仮想空間を表し、上記仮想空間中のオブ
ジェクトが対応する画面上の場所において対応する画面
上のオブジェクトを有する記憶アレーと、この記憶アレ
ーにボクセルに基づくオブジェクトに対応するボクセル
に基づくデータを格納する手段とを含み、上記記憶アレ
ーの一部が上記格納されたオブジェクトのボクセルに基
づく占有マップを表し、上記ボクセルに基づく占有マッ
プが上記仮想空間を表すようになされたオブジェクト生
成手段と、上記記憶アレー内の対応する記憶場所におい
て個別のオブジェクトをデータとして上記占有マップに
マッピングするマッピング手段と、上記仮想空間におい
て上記オブジェクトを移動させる移動手段と、任意のオ
ブジェクトに対応するデータを上記データによって以前
に占められていたものとは異なる場所に書き込むことに
よって、オブジェクトが上記仮想空間を動き回るのにし
たがって上記占有マップを更新する更新手段と、上記任
意のオブジェクトの上記仮想空間における移動中に、上
記任意のオブジェクトに付随するデータが上記オブジェ
クトの別の１つからのデータが既に存在する記憶場所に
書き込まれようとしている場合を検出する衝突検出手段
と、上記移動を実現するために上記オブジェクトに対す
るデータが書き込まれようとしている既に占有されてい
る占有マップの場所の検出によって、上記任意のオブジ
ェクトに付随する画面上の表現の画面上の動きを阻止す
る阻止手段とを備えたことを特徴とすることにより、ボ
クセルに基づくフォーマットで表現された自由に動き回
る複雑なオブジェクト間の実時間の衝突を検出可能に
し、かつ仮想空間におけるグラフィカルオブジェクトが
互いの中に侵入するのを防ぐようにグラフィカルオブジ
ェクト間の移動及び相互作用を可能にすることができ
る。
【００７４】また、上記オブジェクト生成手段、上記マ
ッピング手段、上記更新手段、上記衝突検出手段及び上
記阻止手段を、ユーザインタフェースと相互に作用する
ための入力装置に接続されたグラフィックスワークステ
ーションに備えられると共に、上記移動手段を、上記グ
ラフィックスワークステーションに接続され該グラフィ
ックスワークステーションの表示画面上でグラフィカル
オブジェクトの位置及び配向を変化させる入力トラッカ
で構成したことにより、簡単なハードウエアでシステム
を構成することができる。
【００７５】さらに、上記入力トラッカを、二次元のグ
ラフィックス上のオブジェクトの位置及び配向を変化さ
せる２自由度のコンピュータマウスまたは三次元のグラ
フィックス上のオブジェクトの位置及び配向を変化させ
る６自由度のトラッカで構成することにより、グラフィ
カルオブジェクトとして二次元及び三次元の適用範囲に
簡単に拡大することができる。
【図面の簡単な説明】
【図１】 ボクセルに基づくグラフィカルオブジェクト
を視覚化かつ操作する対話式環境において必要とされる
主要なハードウェア要素を図式的に表す図である。
【図２】 この発明の１実施の形態において必要とされ
る３つの記憶構造を図式的に表す図である。
【図３】 グラフィカルオブジェクトのオブジェクトア
レー表現への変換を図式的に表す図であり、これが次に
衝突検出の目的で占有マップ内の場所に変換される。
【図４】 ボクセルに基づくグラフィカルオブジェクト
間の衝突を検出するこの発明の１実施の形態において必
要とされる基本的各段階を概略的に示すフローチャート
である。
【図５】 この発明に衝突検出を二次元オブジェクトに
ついて図式的に示す図である。
【図６】 図５においてオブジェクトが仮想空間におい
て動かされることによりセルが更新される様子を示す図
である。
【図７】 図６のセルがさらに更新される様子を示す図
である。
【図８】 図７のセルがさらに更新されて重なり衝突が
検出される様子を示す図である。
【図９】 衝突を検出し、オブジェクトが互いに侵入す
るのを防ぐ簡略化されたアルゴリズムのプログラムリス
ト図である。
【図１０】 衝突が検出された後の相互に作用するオブ
ジェクト間の力を計算するためにこの発明をどのように
拡張するかを図式的に示す図である。
【図１１】 この発明の二次元実施例を図式的に示す図
であり、複雑な二次元迷路におけるその利用を示す図で
ある。
【図１２】 この発明の第２の二次元実施例を図式的に
示す図であり、二次元ジグソーパズルを組み立てる際の
その利用を示す図である。
【図１３】 図１２のＡ〜Ｄの第２の二次元実施の形態
を図式的に示す図であり、提案されたデザインが物理的
に組み立て得るものであるか否かをテストする際のその
利用を示す図である。
【図１４】 この発明の三次元実施の形態を説明する図
式的説明図であり、オブジェクトの配向及び位置制御を
示す図である。
【図１５】 図１４のＡ〜Ｃの三次元実施の形態を図式
的に説明する図であり、オブジェクトと環境の壁及び他
のオブジェクトとの衝突を示す図である。
【図１６】 図１４のＡ〜Ｃの三次元実施の形態を図式
的に説明する図であり、２つのボクセルに基づくオブジ
ェクトの相互組み立てを示す図である。
【符号の説明】
１０ ハイエンドグラフィックスワークステーション、
１２ キーボード、１４ 入力トラッカ、１５ ２自由
度コンピュータマウス、１６、１８ グラフィカルオブ
ジェクト、２０ ６自由度トラッカ、２４ 占有マッ
プ、２５ オブジェクトアレー、２６ エッジリスト、
３１ 占有マップ、３３ グラフィカルオブジェクト、
３７、５１ オブジェクトアレー、３６ ボクセル、３
９ 二次元画面、４１、６３ ボリューム描画装置、３
３’ あらかじめ描画されたオブジェクト、４３ 第２
のオブジェクト、４５、５３ 座標変換器、６０ 衝突
検出手段、６１ 移動禁止手段、２７ 初期化シーケン
ス、２８ 対話式オブジェクト制御シーケンス、２９
出口シーケンス、６２ オブジェクト移動機能。
───────────────────────────────────────────────────── フロントページの続き (71)出願人 595151497 201 ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩ ＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ 02139， Ｕ．Ｓ．Ａ.

Claims (3)

    【特許請求の範囲】
  1. 【請求項１】 ボクセルに基づくグラフィカルオブジェ
    クトが表示画面を動き回る場合に互いの中に入り込むの
    を防ぐボクセルに基づくオブジェクト表現のための衝突
    回避システムにおいて、 上記表示画面上への表示のためにボクセルに基づくオブ
    ジェクトを生成する手段であって、上記オブジェクトが
    動かされる仮想空間を表し、上記仮想空間中のオブジェ
    クトが対応する画面上の場所において対応する画面上の
    オブジェクトを有する記憶アレーと、この記憶アレーに
    ボクセルに基づくオブジェクトに対応するボクセルに基
    づくデータを格納する手段とを含み、上記記憶アレーの
    一部が上記格納されたオブジェクトのボクセルに基づく
    占有マップを表し、上記ボクセルに基づく占有マップが
    上記仮想空間を表すようになされたオブジェクト生成手
    段と、 上記記憶アレー内の対応する記憶場所において個別のオ
    ブジェクトをデータとして上記占有マップにマッピング
    するマッピング手段と、 上記仮想空間において上記オブジェクトを移動させる移
    動手段と、 任意のオブジェクトに対応するデータを上記データによ
    って以前に占められていたものとは異なる場所に書き込
    むことによって、オブジェクトが上記仮想空間を動き回
    るのにしたがって上記占有マップを更新する更新手段
    と、 上記任意のオブジェクトの上記仮想空間における移動中
    に、上記任意のオブジェクトに付随するデータが上記オ
    ブジェクトの別の１つからのデータが既に存在する記憶
    場所に書き込まれようとしている場合を検出する衝突検
    出手段と、 上記移動を実現するために上記オブジェクトに対するデ
    ータが書き込まれようとしている既に占有されている占
    有マップの場所の検出によって、上記任意のオブジェク
    トに付随する画面上の表現の画面上の動きを阻止する阻
    止手段とを備えたことを特徴とするボクセルに基づくオ
    ブジェクト表現のための衝突回避システム。
  2. 【請求項２】 請求項１記載のボクセルに基づくオブジ
    ェクト表現のための衝突回避システムにおいて、上記オ
    ブジェクト生成手段、上記マッピング手段、上記更新手
    段、上記衝突検出手段及び上記阻止手段は、ユーザイン
    タフェースと相互に作用するための入力装置に接続され
    たグラフィックスワークステーションに備えられると共
    に、上記移動手段は、上記グラフィックスワークステー
    ションに接続され該グラフィックスワークステーション
    の表示画面上でグラフィカルオブジェクトの位置及び配
    向を変化させる入力トラッカでなることを特徴とするボ
    クセルに基づくオブジェクト表現のための衝突回避シス
    テム。
  3. 【請求項３】 請求項２記載のボクセルに基づくオブジ
    ェクト表現のための衝突回避システムにおいて、上記入
    力トラッカは、二次元のグラフィックス上のオブジェク
    トの位置及び配向を変化させる２自由度のコンピュータ
    マウスまたは三次元のグラフィックス上のオブジェクト
    の位置及び配向を変化させる６自由度のトラッカでなる
    ことを特徴とするボクセルに基づくオブジェクト表現の
    ための衝突回避システム。
JP7327530A 1995-01-31 1995-12-15 ボクセルに基づくオブジェクト表現のための衝突回避システム Expired - Lifetime JP2726811B2 (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US08/381108 1995-01-31
US8/381108 1995-01-31
US08/381,108 US5548694A (en) 1995-01-31 1995-01-31 Collision avoidance system for voxel-based object representation

Publications (2)

Publication Number Publication Date
JPH08241437A true JPH08241437A (ja) 1996-09-17
JP2726811B2 JP2726811B2 (ja) 1998-03-11

Family

ID=23503692

Family Applications (1)

Application Number Title Priority Date Filing Date
JP7327530A Expired - Lifetime JP2726811B2 (ja) 1995-01-31 1995-12-15 ボクセルに基づくオブジェクト表現のための衝突回避システム

Country Status (2)

Country Link
US (1) US5548694A (ja)
JP (1) JP2726811B2 (ja)

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2009233240A (ja) * 2008-03-28 2009-10-15 Univ Waseda 手術支援システム、接近状態検出装置及びそのプログラム
JP2010086040A (ja) * 2008-09-29 2010-04-15 Kubota Systems Inc 画像生成装置、画像解析システム及びコンピュータプログラム
KR101011401B1 (ko) * 2008-12-29 2011-01-28 이화여자대학교 산학협력단 물체의 형상 이미지를 이용한 물체간의 교차판단 방법
JP2021082275A (ja) * 2019-11-18 2021-05-27 ダッソー システムズＤａｓｓａｕｌｔ Ｓｙｓｔｅｍｅｓ デジタル的にモデル化された空間に関してデジタル的にモデル化されたオブジェクトを位置特定するための、およびボリュメトリッククエリを実行するための方法
JP2021128808A (ja) * 2017-05-11 2021-09-02 富士フイルムビジネスイノベーション株式会社 三次元形状データの編集装置、及び三次元形状データの編集プログラム
JP2022522730A (ja) * 2019-03-18 2022-04-20 ソニーグループ株式会社 ポイントクラウドグローバルテトリスパッキング
JP2024007703A (ja) * 2022-07-06 2024-01-19 株式会社カプコン 仮想空間生成プログラム、および仮想空間生成装置
JP2024090213A (ja) * 2022-12-22 2024-07-04 日本電子株式会社 衝突判定装置、プログラム及び衝突判定方法

Families Citing this family (138)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5629594A (en) * 1992-12-02 1997-05-13 Cybernet Systems Corporation Force feedback system
US5848260A (en) * 1993-12-10 1998-12-08 Exa Corporation Computer system for simulating physical processes
JP3486461B2 (ja) * 1994-06-24 2004-01-13 キヤノン株式会社 画像処理装置及び方法
US7110587B1 (en) * 1995-05-31 2006-09-19 Ge Medical Systems Israel Ltd. Registration of nuclear medicine images
US6108704A (en) * 1995-09-25 2000-08-22 Netspeak Corporation Point-to-point internet protocol
JP3138423B2 (ja) * 1996-02-20 2001-02-26 株式会社ナムコ シミュレーション装置
US6374255B1 (en) * 1996-05-21 2002-04-16 Immersion Corporation Haptic authoring
US6064749A (en) * 1996-08-02 2000-05-16 Hirota; Gentaro Hybrid tracking for augmented reality using both camera motion detection and landmark tracking
US5694013A (en) * 1996-09-06 1997-12-02 Ford Global Technologies, Inc. Force feedback haptic interface for a three-dimensional CAD surface
US6016439A (en) * 1996-10-15 2000-01-18 Biosense, Inc. Method and apparatus for synthetic viewpoint imaging
US6154723A (en) * 1996-12-06 2000-11-28 The Board Of Trustees Of The University Of Illinois Virtual reality 3D interface system for data creation, viewing and editing
JPH10198816A (ja) * 1997-01-13 1998-07-31 Mitsubishi Electric Corp 情報処理システム及びネットワーク型情報処理システム
JPH10247252A (ja) * 1997-03-04 1998-09-14 Sharp Corp 衝突判定処理装置
JP3689226B2 (ja) * 1997-03-13 2005-08-31 富士通株式会社 分解経路生成装置
US5910902A (en) * 1997-03-28 1999-06-08 Exa Corporation Computer simulation of physical processes
US5818469A (en) * 1997-04-10 1998-10-06 International Business Machines Corporation Graphics interface processing methodology in symmetric multiprocessing or distributed network environments
US7472047B2 (en) * 1997-05-12 2008-12-30 Immersion Corporation System and method for constraining a graphical hand from penetrating simulated graphical objects
US6014145A (en) * 1997-07-07 2000-01-11 International Business Machines Corporation Navagation with optimum viewpoints in three-dimensional workspace interactive displays having three-dimensional objects with collision barriers
US6100899A (en) * 1997-10-02 2000-08-08 Silicon Graphics, Inc. System and method for performing high-precision, multi-channel blending using multiple blending passes
US6035014A (en) * 1998-02-11 2000-03-07 Analogic Corporation Multiple-stage apparatus and method for detecting objects in computed tomography data
US6272230B1 (en) 1998-02-11 2001-08-07 Analogic Corporation Apparatus and method for optimizing detection of objects in computed tomography data
US6078642A (en) * 1998-02-11 2000-06-20 Analogice Corporation Apparatus and method for density discrimination of objects in computed tomography data using multiple density ranges
US6128365A (en) * 1998-02-11 2000-10-03 Analogic Corporation Apparatus and method for combining related objects in computed tomography data
US6111974A (en) * 1998-02-11 2000-08-29 Analogic Corporation Apparatus and method for detecting sheet objects in computed tomography data
US6067366A (en) * 1998-02-11 2000-05-23 Analogic Corporation Apparatus and method for detecting objects in computed tomography data using erosion and dilation of objects
US6075871A (en) * 1998-02-11 2000-06-13 Analogic Corporation Apparatus and method for eroding objects in computed tomography data
US6317509B1 (en) 1998-02-11 2001-11-13 Analogic Corporation Computed tomography apparatus and method for classifying objects
WO1999041676A1 (en) * 1998-02-11 1999-08-19 Analogic Corporation Computed tomography apparatus and method for classifying objects
US6076400A (en) * 1998-02-11 2000-06-20 Analogic Corporation Apparatus and method for classifying objects in computed tomography data using density dependent mass thresholds
US6026171A (en) * 1998-02-11 2000-02-15 Analogic Corporation Apparatus and method for detection of liquids in computed tomography data
US6026143A (en) * 1998-02-11 2000-02-15 Analogic Corporation Apparatus and method for detecting sheet objects in computed tomography data
US6407748B1 (en) * 1998-04-17 2002-06-18 Sandia Corporation Method and apparatus for modeling interactions
US6175761B1 (en) 1998-04-21 2001-01-16 Bechtel Bwxt Idaho, Llc Methods and computer executable instructions for rapidly calculating simulated particle transport through geometrically modeled treatment volumes having uniform volume elements for use in radiotherapy
US6421048B1 (en) * 1998-07-17 2002-07-16 Sensable Technologies, Inc. Systems and methods for interacting with virtual objects in a haptic virtual reality environment
US6266733B1 (en) * 1998-11-12 2001-07-24 Terarecon, Inc Two-level mini-block storage system for volume data sets
US7216348B1 (en) 1999-01-05 2007-05-08 Net2Phone, Inc. Method and apparatus for dynamically balancing call flow workloads in a telecommunications system
US6195625B1 (en) * 1999-02-26 2001-02-27 Engineering Dynamics Corporation Method for simulating collisions
US6839663B1 (en) * 1999-09-30 2005-01-04 Texas Tech University Haptic rendering of volumetric soft-bodies objects
US7454439B1 (en) * 1999-11-24 2008-11-18 At&T Corp. System and method for large-scale data visualization
US6895583B1 (en) 2000-03-10 2005-05-17 Wind River Systems, Inc. Task control block for a computing environment
WO2001074440A2 (en) * 2000-03-21 2001-10-11 Bechtel Bwxt Idaho, Llc Methods and computer readable medium for improved radiotherapy dosimetry planning
DE10044844A1 (de) * 2000-09-11 2002-04-04 Siemens Ag Verfahren ,Vorrichtung und Software zur Trennung der Einzelobjekte einer aus 3D-Datensätzen medizinischer Untersuchungsverfahren segmentierten anatomischen Struktur
WO2002029723A1 (en) * 2000-10-02 2002-04-11 The Research Foundation Of State University Of Newyork Enhanced virtual navigation and examination
US6873944B1 (en) 2000-10-11 2005-03-29 Ford Global Technologies, Llc Method of real time collision detection between geometric models
GB0104931D0 (en) * 2001-02-28 2001-04-18 Univ Leeds object interaction simulation
JP4629255B2 (ja) * 2001-03-27 2011-02-09 株式会社富士通長野システムエンジニアリング 構造解析処理方法および構造解析処理プログラム
US6836562B2 (en) * 2001-04-09 2004-12-28 Mitsubishi Electric Research Laboratories, Inc. Method for determining the shape of objects directly from range images
US20050114831A1 (en) * 2001-04-18 2005-05-26 Andres Callegari Volume body renderer
EP2362346B1 (en) * 2001-04-18 2013-07-10 Landmark Graphics Corporation Method and computer program product for volume rendering
IL143255A (en) 2001-05-20 2015-09-24 Simbionix Ltd Endoscopic ultrasonography simulation
US8300042B2 (en) 2001-06-05 2012-10-30 Microsoft Corporation Interactive video display system using strobed light
US7259747B2 (en) 2001-06-05 2007-08-21 Reactrix Systems, Inc. Interactive video display system
US8035612B2 (en) 2002-05-28 2011-10-11 Intellectual Ventures Holding 67 Llc Self-contained interactive video display system
GB0127941D0 (en) * 2001-11-21 2002-01-16 Prophet Control Systems Ltd 3D virtual manufacturing process
US7839400B2 (en) * 2002-01-25 2010-11-23 Autodesk, Inc. Volume management system for volumetric displays
US7068288B1 (en) * 2002-02-21 2006-06-27 Xerox Corporation System and method for moving graphical objects on a computer controlled system
WO2003094114A1 (en) * 2002-05-03 2003-11-13 Koninklijke Philips Electronics N.V. Method of producing and displaying an image of a 3 dimensional volume
US7348963B2 (en) * 2002-05-28 2008-03-25 Reactrix Systems, Inc. Interactive video display system
US7710391B2 (en) * 2002-05-28 2010-05-04 Matthew Bell Processing an image utilizing a spatially varying pattern
US7191104B2 (en) * 2002-07-11 2007-03-13 Ford Global Technologies, Llc Method of real-time collision detection between solid geometric models
SE0203567D0 (sv) * 2002-12-03 2002-12-03 Mentice Ab An interventional simulator control system
AU2003301043A1 (en) 2002-12-13 2004-07-09 Reactrix Systems Interactive directed light/sound system
JP2004199496A (ja) * 2002-12-19 2004-07-15 Sony Corp 情報処理装置および方法、並びにプログラム
GB2399703B (en) * 2003-02-04 2006-09-27 British Broadcasting Corp Method and system for providing a volumetric representation of a three-dimensional object
US7348989B2 (en) * 2003-03-07 2008-03-25 Arch Vision, Inc. Preparing digital images for display utilizing view-dependent texturing
US7850456B2 (en) 2003-07-15 2010-12-14 Simbionix Ltd. Surgical simulation device, system and method
US7173265B2 (en) * 2003-08-12 2007-02-06 Loma Linda University Medical Center Modular patient support system
US7536032B2 (en) 2003-10-24 2009-05-19 Reactrix Systems, Inc. Method and system for processing captured image information in an interactive video display system
CN1902930B (zh) 2003-10-24 2010-12-15 瑞克楚斯系统公司 管理交互式视频显示系统的方法和系统
US20050152588A1 (en) * 2003-10-28 2005-07-14 University Of Chicago Method for virtual endoscopic visualization of the colon by shape-scale signatures, centerlining, and computerized detection of masses
FR2861857B1 (fr) * 2003-10-29 2006-01-20 Snecma Moteurs Deplacement d'un objet articule virtuel dans un environnement virtuel en evitant les collisions internes entre les elements articules de l'objet articule
FR2861858B1 (fr) * 2003-10-29 2014-09-05 Snecma Moteurs Deplacement d'un objet articule virtuel dans un environnement virtuel en evitant les collisions entre l'objet articule et l'environnement
US7537523B2 (en) * 2004-06-30 2009-05-26 Microsoft Corporation Dynamic player groups for interest management in multi-character virtual environments
KR20070064319A (ko) * 2004-08-06 2007-06-20 유니버시티 오브 워싱톤 가변 응시 시거리 주사 광 디스플레이
US7397475B2 (en) * 2004-09-02 2008-07-08 Siemens Medical Solutions Usa, Inc. Interactive atlas extracted from volume data
US20060177122A1 (en) * 2005-02-07 2006-08-10 Sony Computer Entertainment Inc. Method and apparatus for particle manipulation using graphics processing
US9128519B1 (en) 2005-04-15 2015-09-08 Intellectual Ventures Holding 67 Llc Method and system for state-based control of objects
US8081822B1 (en) 2005-05-31 2011-12-20 Intellectual Ventures Holding 67 Llc System and method for sensing a feature of an object in an interactive video display
US7545379B2 (en) * 2005-10-28 2009-06-09 Dreamworks Animation Llc Artist directed volume preserving deformation and collision resolution for animation
US8098277B1 (en) 2005-12-02 2012-01-17 Intellectual Ventures Holding 67 Llc Systems and methods for communication between a reactive video system and a mobile communication device
WO2007121357A2 (en) * 2006-04-13 2007-10-25 Fanuc Robotics America, Inc. Dynamic space check for multi-arm system moving on a rail
US20070262988A1 (en) * 2006-05-09 2007-11-15 Pixar Animation Studios Method and apparatus for using voxel mip maps and brick maps as geometric primitives in image rendering process
US8560047B2 (en) 2006-06-16 2013-10-15 Board Of Regents Of The University Of Nebraska Method and apparatus for computer aided surgery
US8238678B2 (en) * 2006-08-30 2012-08-07 Siemens Medical Solutions Usa, Inc. Providing representative image information
JP2008165488A (ja) * 2006-12-28 2008-07-17 Fujitsu Ltd 組立操作性評価装置、方法及びプログラム
WO2008087629A2 (en) 2007-01-16 2008-07-24 Simbionix Ltd. Preoperative surgical simulation
US8543338B2 (en) 2007-01-16 2013-09-24 Simbionix Ltd. System and method for performing computerized simulations for image-guided procedures using a patient specific model
US8102389B2 (en) * 2007-02-14 2012-01-24 International Business Machines Corporation Box casting using an integrated acceleration data structure
KR101141087B1 (ko) 2007-09-14 2012-07-12 인텔렉츄얼 벤처스 홀딩 67 엘엘씨 제스처-기반 사용자 상호작용의 프로세싱
US8159682B2 (en) 2007-11-12 2012-04-17 Intellectual Ventures Holding 67 Llc Lens system
US8259163B2 (en) 2008-03-07 2012-09-04 Intellectual Ventures Holding 67 Llc Display with built in 3D sensing
EP2104046A1 (de) 2008-03-17 2009-09-23 Volkswagen AG Verfahren und Vorrichtung zur rechnergestützten Überprüfung der Baubarkeit eines Produkts
US8315738B2 (en) * 2008-05-21 2012-11-20 Fanuc Robotics America, Inc. Multi-arm robot system interference check via three dimensional automatic zones
US8595218B2 (en) 2008-06-12 2013-11-26 Intellectual Ventures Holding 67 Llc Interactive display management systems and methods
TWI370418B (en) * 2008-10-27 2012-08-11 Ind Tech Res Inst Computer system and controlling method thereof
JP5073065B2 (ja) 2009-01-15 2012-11-14 三菱電機株式会社 衝突判定装置および衝突判定プログラム
US8497875B2 (en) * 2009-01-21 2013-07-30 Siemens Product Lifecycle Management Software Inc. System, method, and computer program product for determining a translation vector
WO2010096490A1 (en) * 2009-02-17 2010-08-26 Disney Enterprises, Inc. Methods, systems and media for simulating contact scenarios
WO2010141419A2 (en) * 2009-06-01 2010-12-09 Raytheon Company Non-kinematic behavioral mapping
US9643316B2 (en) 2009-10-27 2017-05-09 Battelle Memorial Institute Semi-autonomous multi-use robot system and method of operation
FR2954518B1 (fr) * 2009-12-18 2012-03-23 Aripa Service Innovation Ind " systeme anticollision pour le deplacement d'un objet dans un environnement encombre."
US8487252B2 (en) 2010-09-29 2013-07-16 Carl Zeiss Nts Gmbh Particle beam microscope and method for operating the particle beam microscope
US8227752B1 (en) 2011-02-17 2012-07-24 Carl Zeiss Nts Gmbh Method of operating a scanning electron microscope
GB2484197A (en) * 2010-09-29 2012-04-04 Zeiss Carl Nts Gmbh Particle beam microscope and method of operating the particle microscope
DE102012103830B4 (de) 2011-05-05 2022-05-25 Fanuc Robotics America Corp. Verfahren und computerlesbare Medien zur automatischen Verbindung von gegenseitiger Blockierung in Mehrfachrobotersytemen
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
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
JP6069923B2 (ja) * 2012-07-20 2017-02-01 セイコーエプソン株式会社 ロボットシステム、ロボット、ロボット制御装置
CN103150722B (zh) * 2013-01-17 2015-09-16 东南大学 应用四元数分割与图论优化的外周血白细胞边缘提取方法
US9164653B2 (en) 2013-03-15 2015-10-20 Inspace Technologies Limited Three-dimensional space for navigating objects connected in hierarchy
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
AU2014293027A1 (en) * 2013-07-24 2016-02-18 Exa Corporation Lattice boltzmann collision operators enforcing isotropy and galilean invariance
JP6263917B2 (ja) * 2013-09-17 2018-01-24 ソニー株式会社 情報処理装置、情報処理方法及びコンピュータプログラム
US9869785B2 (en) 2013-11-12 2018-01-16 Schlumberger Technology Corporation Systems and methods for speed-adjustable model navigation
US9452531B2 (en) * 2014-02-04 2016-09-27 Microsoft Technology Licensing, Llc Controlling a robot in the presence of a moving object
US9384528B2 (en) * 2014-05-28 2016-07-05 EchoPixel, Inc. Image annotation using a haptic plane
US9283678B2 (en) * 2014-07-16 2016-03-15 Google Inc. Virtual safety cages for robotic devices
JP6748088B2 (ja) 2015-02-25 2020-08-26 マコ サージカル コーポレーション 外科手術中の追跡中断を低減するナビゲーションシステム及び方法
DE102015007395A1 (de) * 2015-06-08 2016-12-08 Kuka Roboter Gmbh Verfahren und System zum Betreiben und/oder Überwachen einer Maschine, insbesondere eines Roboters
US10117713B2 (en) 2015-07-01 2018-11-06 Mako Surgical Corp. Robotic systems and methods for controlling a tool removing material from a workpiece
US9940689B2 (en) 2015-11-02 2018-04-10 Nvidia Corporation Latency-resistant sparse simulation technique, system and method
US11024481B2 (en) 2016-03-04 2021-06-01 Fei Company Scanning electron microscope
NL2016367B1 (en) * 2016-03-04 2017-09-19 Phenom-World Holding B V Scanning electron microscope
CN119251375A (zh) * 2016-08-19 2025-01-03 莫维迪厄斯有限公司 矩阵操作的动态剔除
US10131053B1 (en) * 2016-09-14 2018-11-20 X Development Llc Real time robot collision avoidance
AU2018212812A1 (en) 2017-01-26 2019-08-15 Dassault Systemes Simulia Corp. Multi-phase flow visualizations based on fluid occupation time
US10766140B2 (en) 2017-04-13 2020-09-08 Battelle Memorial Institute Teach mode collision avoidance system and method for industrial robotic manipulators
US12205473B2 (en) * 2017-06-16 2025-01-21 FLIR Belgium BVBA Collision avoidance systems and methods
WO2019061202A1 (en) * 2017-09-28 2019-04-04 Shenzhen United Imaging Healthcare Co., Ltd. SYSTEM AND METHOD FOR PROCESSING COLON IMAGE DATA
US10676022B2 (en) 2017-12-27 2020-06-09 X Development Llc Visually indicating vehicle caution regions
US11714040B2 (en) 2018-01-10 2023-08-01 Dassault Systemes Simulia Corp. Determining fluid flow characteristics of porous mediums
US11530598B2 (en) 2018-08-21 2022-12-20 Dassault Systemes Simulia Corp. Determination of oil removed by gas via miscible displacement in reservoir rock
DE102018133472B3 (de) * 2018-12-21 2020-03-12 Franka Emika Gmbh Bewegungsüberwachung eines Robotermanipulators
US11455894B2 (en) * 2019-10-28 2022-09-27 Skydio, Inc. Structure scan using unmanned aerial vehicle
US12169669B2 (en) 2019-10-30 2024-12-17 Dassault Systemes Americas Corp. Computer system for simulating physical process using lattice Boltzmann based scalar transport enforcing Galilean invariance for scalar transport
US11847391B2 (en) 2020-06-29 2023-12-19 Dassault Systemes Simulia Corp. Computer system for simulating physical processes using surface algorithm
US11907625B2 (en) 2020-12-29 2024-02-20 Dassault Systemes Americas Corp. Computer simulation of multi-phase and multi-component fluid flows including physics of under-resolved porous structures

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
IL89484A (en) * 1989-03-03 1992-08-18 Nct Ltd Numerical Control Tech System for automatic finishing of machined parts
US5187660A (en) * 1989-12-01 1993-02-16 At&T Bell Laboratories Arrangement for displaying on a display volumetric data
US5442733A (en) * 1992-03-20 1995-08-15 The Research Foundation Of State University Of New York Method and apparatus for generating realistic images using a discrete representation
US5347459A (en) * 1993-03-17 1994-09-13 National Research Council Of Canada Real time collision detection
US5458125A (en) * 1994-01-28 1995-10-17 Board Of Directors Of The Leland Standford Jr. University Treatment planning method and apparatus for radiosurgery and radiation therapy

Cited By (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2009233240A (ja) * 2008-03-28 2009-10-15 Univ Waseda 手術支援システム、接近状態検出装置及びそのプログラム
JP2010086040A (ja) * 2008-09-29 2010-04-15 Kubota Systems Inc 画像生成装置、画像解析システム及びコンピュータプログラム
KR101011401B1 (ko) * 2008-12-29 2011-01-28 이화여자대학교 산학협력단 물체의 형상 이미지를 이용한 물체간의 교차판단 방법
JP2021128808A (ja) * 2017-05-11 2021-09-02 富士フイルムビジネスイノベーション株式会社 三次元形状データの編集装置、及び三次元形状データの編集プログラム
JP2022522730A (ja) * 2019-03-18 2022-04-20 ソニーグループ株式会社 ポイントクラウドグローバルテトリスパッキング
US11605184B2 (en) 2019-03-18 2023-03-14 Sony Corporation Point cloud global tetris packing
JP2021082275A (ja) * 2019-11-18 2021-05-27 ダッソー システムズＤａｓｓａｕｌｔ Ｓｙｓｔｅｍｅｓ デジタル的にモデル化された空間に関してデジタル的にモデル化されたオブジェクトを位置特定するための、およびボリュメトリッククエリを実行するための方法
JP2024007703A (ja) * 2022-07-06 2024-01-19 株式会社カプコン 仮想空間生成プログラム、および仮想空間生成装置
JP2024090213A (ja) * 2022-12-22 2024-07-04 日本電子株式会社 衝突判定装置、プログラム及び衝突判定方法

Also Published As

Publication number Publication date
JP2726811B2 (ja) 1998-03-11
US5548694A (en) 1996-08-20

Similar Documents

Publication Publication Date Title
JP2726811B2 (ja) ボクセルに基づくオブジェクト表現のための衝突回避システム
Gibson Beyond volume rendering: visualization, haptic exploration, and physical modeling of voxel-based objects
Teschner et al. Collision detection for deformable objects
Lombardo et al. Real-time collision detection for virtual surgery
US7084869B2 (en) Methods and apparatus for detecting and correcting penetration between objects
Weller New geometric data structures for collision detection and haptics
Vilanova et al. VirEn: A virtual endoscopy system
Wagner et al. Collision detection and tissue modeling in a vr-simulator for eye surgery
Chan et al. Deformable haptic rendering for volumetric medical image data
Vlasov et al. Haptic rendering of volume data with collision detection guarantee using path finding
McCrae et al. Exploring the design space of multiscale 3D orientation
Peng et al. Bone surgery simulation with virtual reality
Peng et al. Interactive Solid Modelling in a Virtual Environment with a Haptic Interface
Peng et al. A virtual sculpting system based on triple Dexel models with haptics
Gibson Linked volumetric objects for physics-based modeling
Noon A volume rendering engine for desktops, laptops, mobile devices and immersive virtual reality systems using GPU-based volume raycasting
Leu et al. Creating freeform model by carving virtual workpiece with haptic interface
Lin et al. Realistic visualization for surgery simulation using dynamic volume texture mapping and model deformation
Basdogan et al. 3-DOF haptic rendering
Peng et al. Freeform modelling using sweep differential equation with haptic interface
Xie et al. Fast collision detection based on nose augmentation virtual surgery
Madi et al. Modeling and visualization of layered objects
Liu et al. A Haptic System for Drilling into Volume Data with Polygonal Tools.
McDonnell et al. Dynamic subdivision-based solid modeling
Eriksson et al. A haptic and virtual reality temporal bone surgery simulator

Legal Events

Date Code Title Description
R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20081205

Year of fee payment: 11

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20091205

Year of fee payment: 12

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20101205

Year of fee payment: 13

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20111205

Year of fee payment: 14

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20121205

Year of fee payment: 15

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20131205

Year of fee payment: 16

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

EXPY Cancellation because of completion of term