JP2000222601A - グラフィックオブジェクトの生成方法及び生成システム - Google Patents

Abstract

(57)【要約】 【課題】 モデル化とレンダリングの単純化を可能にす
るグラフィックオブジェクトの生成方法を得る。 【解決手段】 メモリ中のグラフィックオブジェクトを
表現する方法が提供される。オブジェクトの１つの面
が、像面分解能に関連する格子分解能を有する複数のセ
ル２００に分割される。各セル２００は像面分解能に関
連する８つの格子点２０１によって囲まれている。単一
ゼロ次元面エレメントはオブジェクトの面上に定位され
た各セル２００についてメモリに記憶される。隣接セル
の面エレメント１００はリンクによって連結され、セル
に含まれるオブジェクトの部分の属性は各面エレメント
と各リンクに対して割当てられる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はグラフィックオブジ
ェクトの生成方法及び生成システムに関し、特に、連結
したゼロ次元点によって表現されるグラフィックオブジ
ェクトの生成を行うためのグラフィックオブジェクトの
生成方法及び生成システムに関する。

【０００２】

【従来の技術】コンピュータ・グラフィックでは、種々
の基本的グラフィックエレメントを用いて様々な方法で
三次元空間にオブジェクトを表現することができる。グ
ラフィックオブジェクトを表現するために一般に用いら
れるよく知られた公知の表現として、暗黙表現、幾何学
表現、立体表現、粒子表現がある。これらについて説明
する。

【０００３】暗黙表現（Implicit） 暗黙表現を用いて、任意の数学的及び／又は物理的関数
からグラフィックオブジェクトを生成することができ
る。例えば、中空球面のアウトラインを描くためには、
レンダリングエンジンに関数(直交座標系で)x²＋y²+z²
＝rを与えるだけでよく、また、固体球面を描くための
関数はx²＋y²+z²≦rとなる。色やその他の材料特性も同
様の合成を行うことによって生成することができる。関
数を用いて、種々の幾何学的形状、物理オブジェクト、
および実在のモデルや仮想上のモデルを描くことができ
る。陰関数は人の容姿などの複雑なオブジェクトの合成
には適していない。

【０００４】幾何学表現（Geometric Representation） 古典的には、三次元オブジェクトはポリゴン・ファセッ
ト（polygonal facets）のメッシュとして幾何学的にモ
デル化されてきた。通常ポリゴンは三角形である。各フ
ァセットのサイズはファセットの領域におけるオブジェ
クトの曲率の程度に対応する。オブジェクトが高度の曲
率を有する場合には多くのポリゴンが必要になるが、比
較的平坦な領域についてはポリゴンの数は少なくなる。
ポリゴンモデルは仮想訓練環境、三次元モデル作成ツー
ル、ビデオ・ゲームのような多くのアプリケーションで
使用されている。１つの特徴として、幾何学表現だけで
グラフィックオブジェクトの表面特徴を処理することが
できる。

【０００５】しかしながら、ポリゴンモデルが変形され
ると、その変形されたオブジェクトでは、もはやファセ
ットのサイズが曲率の局所的程度に対応できないために
問題が生じる。さらに、変形によっては局所領域の相対
的分解能が変化する場合もある。いずれの場合にも、変
形した曲率に応じるオブジェクトの再メッシュ化が必要
となる。再メッシュ化(ポリゴン化)は、計算時間という
点から比較的費用がかかるので、前処理ステップとして
行われるのが一般的である。その結果、ポリゴンモデル
は動的変形を行う必要のあるオブジェクトについてはあ
まり適していない。

【０００６】立体表現（Volumetric Representation） 新しい表現では、オブジェクトは三次元空間でサンプリ
ングされ、MRIやCTスキャンなどの立体データ集合（立
体データセット）が生成される。各サンプルはボクセル
と呼ばれる。一般にデータ集合には１００万のボクセル
を含む場合もある。立体データ集合をレンダーするため
にオブジェクトは通常セグメント化される。等表面が特
定され、特定立体領域に焦点を合わせることができる。
例えば、人間の頭部の立体データ集合は骨と軟組織のよ
うな材料特性に応じてボクセルの分割を行うことができ
る。

【０００７】ボクセル数が多いために、立体データ集合
を物理ベースでモデル化し変形することはまだ計算に多
大の費用を必要とするオペレーションである。多くの場
合、表面特徴にのみ関心があるのでオブジェクトの内部
は実際上無視できる場合が多い。

【０００８】粒子表現（Particle Representation） オブジェクトの粒子表現は、風洞シミュレーションなど
の流体の流れをモデル化するために使用される場合が多
い。流体の流れの中で個々の粒子を追跡するために、あ
るいは、完全な流れを視覚化するために、配向速度のよ
うな一定の属性が粒子に与えられる。

【０００９】粒子表現の別のアプリケーションは、煙、
ほこり、霧のような“雲状”オブジェクトの視覚化の中
に見られる。陰影づけモデルは、光を放射して雲状オブ
ジェクトをレンダーする粒子に適用することができる。
また、粒子表現は、エネルギー関数の助けを借りて部分
空間に制約を設けて面をモデル化することができる。粒
子雲の利点はこの雲が非常に変形しやすいことである。
不利な点として、雲の中の粒子は、連結されていないた
め力に曝されると個々に振る舞うということがある。さ
らに、粒子は固体オブジェクトやモデルの表面構造を表
現するにはきわめて不適切である。

【００１０】モデル化についての検討 種々の表現でグラフィックオブジェクトの非物理的モデ
ル化および物理的モデル化を行うためのいくつかの方法
が知られている。非物理ベースのモデル化では、スプラ
イン、ベジエ(Bezier)曲線などがよく用いられる。その
場合、制御点が処理されて所望の程度の変形を行うこと
ができる。

【００１１】物理的方法は一般に剛体力学と動的変形の
２つのカテゴリに分かれる。剛体力学はニュートン力学
から生じる微分方程式の解を求めるために一般に使われ
る。コンピュータシステムでは微分方程式を解くために
数値積分計を使用することができる。動的変形は有限要
素法(FEM)または質量バネシステムによってモデル化す
ることができる。

【００１２】レンダリングについての検討 これらの従来型のプリミティブ(基本形状オブジェクト)
のレンダリング時間は、モデル化の対象となるオブジェ
クトの複雑さに依存する。例えば、複雑なオブジェクト
の幾何学表現の場合には、ポリゴンは通常ほぼピクセル
サイズで非常にサイズが小さくなり、多くのポリゴンに
よってオブジェクトが表現される。ポリゴンは通常三角
形を定義する頂点を用いて表現される。

【００１３】ポリゴンをレンダーするために、三角形の
投影がスキャン変換(ラスター化)され、投影の内部に入
る各ピクセルの輝度が計算される。この計算は、約１つ
のピクセルまたはそれより少ないピクセルがポリゴンに
よってカバーされているとき、比較的時間のかかる演算
となる。ポリゴンの点サンプルとの交換およびスクリー
ンへの点サンプルの投影をさらに効率的なオブジェクト
のレンダー方法にすることが可能である。

【００１４】ボリュームレンダリングを行うためのいく
つかの方法が知られている。一般に、ボリュームレンダ
リングはきわめて複雑である。ボクセル数が限定されて
いない場合、リアルタイムレンダリングは時間のかかる
ものになる。

【００１５】米国特許第５,７８１,１９４号公報“ボク
セルベースオブジェクトのリアルタイム投影”(１９９
８年７月１４日に発行、発明者 Ponomarov 他)に記載さ
れている従来のリアルタイム・レンダリングシステム
は、面ボクセル間の増分ベクトルを利用して一続きの面
ボクセルを組立てるものである。この表現方法は非常に
詳細な表面領域を示すオブジェクトのモデル化と表示に
成功している。剛体の運動のモデル化はスクリプティン
グ機構の助けを借りて行うことができるが、このモデル
化は物理ベースの方法が使用されないので現実味に欠け
る。このアプローチにはオブジェクトの現実味を出す変
形の可能性は含まれない。これらのオブジェクトは、衝
突と他の変形力に反応しない空間中の剛体として振る舞
う。

【００１６】また、Levoy他“表示プリミティブとして
の点の利用”(ノースカロライナ大学テクニカル・レポ
ート８５-０２２、１９８５年参照)に記載されている他
の従来技術では、個別の粒子または点は、グラフィック
システムのメタプリミティブ(metaprimitive)として使
われている。この論文には、オブジェクトの点表現への
変換処理が記載されている。この場合各点は位置と色と
を有する。該論文には、滑らかな面として点をレンダー
する処理についても記載されている。

【００１７】これらの点はゼロ次元密度サンプルとして
モデル化され、オブジェクトオーダー投影を利用してレ
ンダーされる。レンダリングを行うとき、同じピクセル
に対して複数の点を投影することができ、これらの点の
輝度をフィルタリングして考慮中のピクセルの最終輝度
を得ることができる。スクリーン上の投影された点位置
から、対応するピクセル中心までの距離に比例して輝度
に重み付けを行うことによりこのフィルタリングを行う
ことができる。この重み付けはガウスフィルタを用いて
モデル化される。強調濃度・バッファ(Zバッファ)によ
って、色の濃度値を示す狭い領域の点の混合を許容する
許容誤差との濃度比較が行われる。１つの利点として、
これらの濃度を点表現で表すことによってビューの任意
の視点からオブジェクトのレンダーが可能になる。

【００１８】Grossman他の“サンプルレンダリング”
(ユーログラフィック・ワークショップ'９８の会報、レ
ンダリング技術、１９９８年、Drettakis、G.、Max、N.
(eds.)、p.１８１〜１９２、１９９８年)に記載されて
いるような別の方法で、二等辺三角形格子上への三角形
メッシュの正投影をサンプリングすることにより点サン
プルを得ることができる。三角形メッシュの投影によっ
てカバーされる格子の各三角形について、サンプルポイ
ントが追加される。二等辺三角形格子を選択し、少なく
とも１つのサンプルが各ピクセルをカバーすることを保
証できるほどに密集した十分なサンプリングが必要であ
る。

【００１９】

【発明が解決しようとする課題】上述したように、以上
説明した従来のいずれの方法においても、グラフィック
オブジェクトの表現にはなんらかの限定があった。すな
わち、暗黙表現においては、幾何学的形状については容
易に表現できるが、人の容姿等の複雑な形状になると極
めて困難になってしまい、また、幾何学表現において
は、オブジェクトの表面上に特徴を処理するのに適して
いるが、動的変形を行う必要のあるオブジェクトを表現
することには適していない、といったように、特定の目
的にのみしか使用することができないという問題点があ
った。

【００２０】この発明は、かかる問題点を解決するため
になされたものであり、種々の特徴を有し、それらのう
ちの最も好適な特徴を組み合わせ、モデル化とレンダリ
ングを単純化して、グラフィックオブジェクトの表現を
行うことが可能なグラフィックオブジェクトの生成方法
及び生成システムを得ることを目的とする。

【００２１】

【課題を解決するための手段】この発明においては、メ
モリ中のグラフィックオブジェクトを表現する方法が提
供される。オブジェクトの表面は像面（image-plane）
の分解能に関連する格子分解能を有する複数のセルに分
割される。各セルは、像面分解能に関係する８つの格子
点によって囲まれる。単一ゼロ次元面エレメントは、オ
ブジェクトの表面に定位された各セルのメモリに記憶さ
れる。隣接セルの面エレメントはリンクによって連結さ
れ、セルに含まれるオブジェクトの部分の属性は各面エ
レメントと各リンクへ割当てられる。

【００２２】各面エレメントに割当てられるオブジェク
ト属性には、オブジェクトの表面にある面エレメントの
位置と、対応するセル中のオブジェクトの部分の色およ
び不透明度と、対応するセルにある面に対する法線と、
隣接セルにおけるサーフェル(surfel＝面エレメント)の
オフセットとが含まれる。

【００２３】この発明は、メモリ中のグラフィックオブ
ジェクトの表現を生成するためのグラフィックオブジェ
クトの生成方法であって、オブジェクトの面を、像面分
解能に関連する格子分解能を有する複数のセルに分割す
るステップと、オブジェクトの面上に定位された各セル
についてメモリに単一ゼロ次元面エレメントを記憶する
ステップと、リンクによって隣接セル中の面エレメント
を連結するステップと、セルに含まれるオブジェクトの
部分の属性を各面エレメントと各リンクへ割り当てるス
テップと、を備えたグラフィックオブジェクトの生成方
法である。

【００２４】また、各セルが像面分解能に関連する８つ
の格子点によって囲まれている。

【００２５】また、各面エレメントに割当てられている
オブジェクトの属性が、オブジェクトの面上の面エレメ
ントの位置と、対応するセル中のオブジェクトの部分の
色と不透明度と、対応するセル中の面に対する法線と、
隣接セル中のサーフェルに対するオフセットとを含んで
いる。

【００２６】また、各面エレメントに対して割当てられ
るオブジェクトの属性が、対応するセル中のオブジェク
トの部分の速度と質量とを含んでいる。

【００２７】また、各リンクに対して割当てられるオブ
ジェクトの属性がリンクによって連結された２つの隣接
する面エレメント間の距離の残りの長さを含んでいる。

【００２８】また、各セルに対して割当てられるオブジ
ェクトの属性がリンクと関連する弾性係数と減衰定数を
含んでいる。

【００２９】また、６つの隣接する面エレメントが８連
結されている。

【００３０】また、各面エレメントが解析関数から生成
される。

【００３１】また、各面エレメントがオブジェクトの面
を表現するポリゴンから生成される。

【００３２】また、生成に、ポリゴンをラスター化する
ための三次元デジタル微分アナライザを用いる。

【００３３】また、生成に、オブジェクトの面の距離マ
ップを用いる。

【００３４】また、オブジェクトを表現するボリューム
データ集合の面においてボクセルから各面エレメントが
生成される。

【００３５】また、オブジェクトを表現する粒子雲から
各上記面エレメントが生成される。

【００３６】また、面エレメントが各ポリゴンのベース
エッジに平行なラインの三次元スキャン変換であって、
ラインが上記ポリゴンのガイダンス・エッジによって囲
まれている。

【００３７】また、ポリゴンが三角形である。

【００３８】また、６つの隣接する面エレメントの間に
８連結性を設けるために各エレメントの内部に追加の面
エレメントを生成することをさらに含んでいる。

【００３９】また、距離マップが各面エレメントについ
てオブジェクトの面までの最短距離を記憶する。

【００４０】また、距離マップ中の勾配が面法線の方向
を定義する。

【００４１】また、オブジェクトを表す面ポリゴンを推
定するステップであって、面ポリゴンが上記メモリ中で
三角形からなるトリ・ストリップとして記憶されている
ステップと、推定された面ポリゴンのためにバウンディ
ング・ボックスを決定するステップと、トリ・ストリッ
プの周りに、像面分解能を有する格子であって、バウン
ディング・ボックスより大きい格子を画定するステップ
と、各整数格子点位置について各三角形までの最短距離
を決定するステップと、１/２×２^1/2（すなわち、１／
２×（ルート２））以下の距離を有する各格子位置につ
いて面エレメントをシーケンシャル・リストに加えるス
テップと、をさらに有する。

【００４２】また、属性を与えられた面エレメントと属
性を与えられたリンクをメモリのシーケンシャル・リス
ト中に配列することを含んでいる。

【００４３】また、グラフィックオブジェクトを表す複
数の表現を生成することを含み、複数の表現の各々が様
々なレベルの細部を有する。

【００４４】また、さらに高いレベルの細部表現からさ
らに低いレベルの細部表現を生成するために、隣接サー
フェルを組み合わせて低い分解能のサーフェルに変える
ステップをさらに有する。

【００４５】また、４つの隣接サーフェルの属性値が平
均化される。

【００４６】また、この発明は、メモリ中のグラフィッ
クオブジェクトの表現を生成するグラフィックオブジェ
クトの生成システムであって、オブジェクトの面を、像
面分解能に関連する格子分解能を有する複数のセルへ分
割する手段と、オブジェクトの面上に定位された各上記
セルについて単一ゼロ次元面エレメントを記憶するメモ
リと、隣接セル中の面エレメントを連結するためのリン
クと、セル中に含まれるオブジェクトの部分の属性を各
面エレメントと各リンクに対して割当てるための手段
と、を備えている。

【００４７】また、属性を与えられた面エレメントと属
性を与えられたリンクとをシーケンシャル・リストとし
てメモリ中に記憶する。

【００４８】

【発明の実施の形態】１．序論と概観 本発明では、面エレメント（サーフェスエレメント）す
なわち“サーフェル(surfel)”として表現されるグラフ
ィックオブジェクト（グラフィックオブジェクト）の生
成、モデル化およびレンダリングについて説明を行う。
サーフェルは、三次元サーフェル格子の中で連結したゼ
ロ次元点サンプルとして定義される。本発明に準拠する
三次元格子（三次元グリッド）は、オブジェクト空間中
への像面分解能の投影であり、その結果、サーフェルの
ピクセル・サイズのスペーシングを備えた三次元ボリュ
ームが生成される。これと対照的に、従来技術によるレ
ンダリングプリミティブは通常オブジェクト空間中でサ
ンプリングされる。

【００４９】各サーフェルは像面（image-plane）のピ
クセルに対して投影を行う。サーフェルは、整数格子位
置である８ノードによって定義される“セル”の中のい
ずれかに定位している。これは、水平スキャンラインと
垂直スキャンラインの交点を整数ピクセル位置と見な
し、そのような４つの位置の間の領域をピクセルとして
示す像面におけるピクセルの定義に類似している。

【００５０】サーフェルは、その位置、色、不透明度お
よびその点位置における面法線に関する情報(属性)を記
憶する。速度および静止質量のような追加属性は物理的
オブジェクトまたはモデルを表現するサーフェルに帰属
させることができる。

【００５１】隣接サーフェルは“リンク”によって相互
に接続し、リンクの残りの長さによってサーフェルの相
対的スペーシングが定義される。セルのどこにでもサー
フェルを定位できることに留意されたい。オブジェクト
が変形可能である場合、弾性および減衰のような追加属
性はリンクに帰属させることができる。サーフェルとリ
ンク属性を記憶するデータ構造はポインタによって連結
されるアイテムのリストである。６つの隣接サーフェル
が８連結される。

【００５２】本発明の表現では、サーフェルとピクセル
との間で１対１のマッピング定義を行うことによりオブ
ジェクト空間と画像空間とが組み合わされる。サーフェ
ルはスクリーン分解能に従って生成される。したがっ
て、各サーフェルが１ピクセルへマップするときピクセ
ルより小さい細部は配慮されない。

【００５３】本発明でオブジェクト空間と画像空間を組
み合わせる理由は、単純で、効率の良い高速レンダリン
グを行うためである。

【００５４】サーフェルは一般的レンダリングプリミテ
ィブとして使用することができる。本発明は、従来技術
による表現(暗黙、幾何学、ボクセルおよび粒子)からサ
ーフェルの生成方法を提供するものである。本発明は最
近傍補間を利用するオブジェクトオーダー投影処理を提
案するものであり、この投影処理ではサーフェルの対応
するピクセルに対してサーフェルが投影される。

【００５５】本発明の表現では、サーフェルオブジェク
トは相互作用して結果として“物理的に曖昧な変形”を
生み出すことができる。変形を可能にするために、質量
バネシステムとしてサーフェルオブジェクトをモデル化
することができる。質量バネシステムでは、各サーフェ
ルに質量が割当てられ、各サーフェルはバネによって隣
接サーフェルと連結する。

【００５６】本明細書では、回転あるいは内力と外力な
どによってサーフェルがサーフェルのセルの中から“引
き出され”たことに起因して、“ホール”が表面に現れ
るとき、画像品質を高める方法についての説明も行う。
これらの方法には、視野変換の剪断変形(shear-warp)、
オブジェクトのスーパーサンプリングあるいはスケーリ
ングおよびスプラッティング（splatting）が含まれ
る。

【００５７】１.１ サーフェル 図１に図示のように、オブジェクトを表し、モデル化
し、レンダーするために使用できるグラフィック・プリ
ミティブについて説明する。このプリミティブを面エレ
メントすなわち略して“サーフェル”１００と呼ぶこと
にする。上述の表現、すなわち陰関数１０１、ポリゴン
１０２、ボクセル１０３、粒子１０４にサーフェルを関
連づけることができる。像面の分解能を有する三次元格
子によって境界を定義するセル中のゼロ次元点サンプル
としてサーフェル１００を定義する。位置、色および質
量のような属性をサーフェルに割当てることができる。

【００５８】複数のサーフェルを互いに連結させて、オ
ブジェクトの任意の二次元面などの二次元多様体を形成
することができる。サーフェル多様体を相互に連結して
さらに複雑な二次元多様体を形成することができる。多
様体は、実在のものであれ想像上のものであれ任意のオ
ブジェクトを“アウトライン”することができる。

【００５９】１.２ スクリーン分解能 図２に図示のように、サーフェル１００(固体)は、整数
格子位置である８ノード２０１(開いた)によって境界を
定義するセル２００のどこかに定位することができる。
図３に図示のように、各サーフェルは６つの隣接サーフ
ェルを有し、各セル２００の面に隣接する各セルについ
て１つの隣接サーフェルがある。これらの格子位置は、
サイズとロケーションが像面２０３からなるピクセル２
０２に対応する。言い換えれば、ゼロ次元サーフェルの
ロケーションに接する境界(bound)を定義する格子は像
面あるいは表示スクリーンの分解能によって定義するこ
とができるる。

【００６０】スクリーン分解能に準拠するサンプリング
は、オブジェクト空間と画像空間との間で直接対応す
る。このようにサーフェルの境界を定義することによっ
て、オブジェクトの変形は再サンプリングを必要としな
いという意味でさらに容易になる。“面エレメント化さ
れた”オブジェクトの処理に費やす時間はさらに少なく
なる。また、ピクセル・サイズの間隔を備えたサーフェ
ル格子によって、オフセットと共にサーフェルを記憶す
る可能性が与えられる。事前に計算した視野変換された
オフセットを利用して効率良くサーフェルオブジェクト
をレンダーする可能性が与えられる。

【００６１】１.３ サーフェルリンク 図４に図示のように、リンク３００によって連結された
サーフェル１００の三次元コレクションとしてグラフィ
ックオブジェクトが表現される。このように６つの隣接
サーフェルが８連結される。言い換えれば、サーフェル
がセル中のどこかにあれば、セルの６つの面の中を通っ
て、かつ、対角線に沿ってサーフェルが連結する。対角
線に沿った連結リンクによって、メッシュの“潰れ(col
lapsing)”を防止することができる。６隣接し８連結し
たサーフェルによって、グラフィックオブジェクトの面
すなわち二次元多様体が表現される。

【００６２】表１は、従来技術のポリゴン、ボクセルお
よび粒子（パーティクル）を本発明に準拠するサーフェ
ルと比較するものである。この表は、本発明のサーフェ
ルが公知の従来技術による表現プリミティブと同様の属
性を持っていることを示している。

【００６３】

【表１】

【００６４】何らかの方法で、ポリゴンがほぼ１ピクセ
ルのサイズを持っているとき、サーフェルは変換された
ポリゴンのピクセルの属性を有する。また、サーフェル
は抽出された８連結面ボクセル（サーフェスボクセル）
と考えることもできる。この場合、サーフェルが定位さ
れているセルは１×１×１のピクセルからなる大きさを
有し、６つの隣接サーフェルを有する。サーフェルオブ
ジェクトは、スクリーンすなわち画像格子（画像グリッ
ド）の分解能によって定義される粒子雲のマッピングと
考えることもできる。

【００６５】またサーフェルは相違点も有する。例え
ば、サーフェルはその幾何学形状においてボクセルや粒
子（パーティクル）に似ていない。サーフェルは、格子
（グリッド）に関してポリゴンや粒子に似ていない。サ
ーフェルは、そのリンクのされ方においてボクセルや粒
子に似ていない。また、サーフェルはその変形方法にお
いてポリゴンやボクセルに似ていない。

【００６６】従来技術のプリミティブ(基本形状オブジ
ェクト)と比較すると、面エレメントの定義方法という
点で最も重要な相違点は、サーフェルがスクリーン分解
能に従ってサンプリングされるという点である。ボクセ
ルと粒子は通常オブジェクトの分解能に従ってサンプリ
ングされる。ポリゴンはスクリーン分解能でサンプリン
グすることができる。しかし、オブジェクトを変形する
とき投影あるいはレンダリングの直前にサンプリングを
行わなければならない。サーフェルの場合には、スクリ
ーン分解能に従うサンプリングは前処理ステップで一回
行えばよい。

【００６７】本発明に準拠するスクリーン分解能サンプ
リングでは、ちょうど十分な数のサーフェルがグラフィ
ックオブジェクトに含まれていて、これらのサーフェル
が最も近傍の各ピクセルに対する各サーフェルを単射影
することによってオブジェクトの表面を復元することが
できる。例えば、１００×１００のサーフェルからなる
矩形のサーフェルポリゴンによって、１００×１００の
ピクセルからなる像面がスクリーンに生成される。本発
明では、サーフェルは直接ピクセルへマップされる。サ
ーフェルのスクリーンへの貢献値(contribution)は１つ
のピクセルより大きくも小さくもない。

【００６８】２. サーフェルオブジェクトのデータ構造 図５に図示のように、各サーフェル１００は一組の関連
するサーフェル属性４０１を有し、各リンク３００はリ
ンク属性４０３を有する。オブジェクトをモデル化し、
レンダーするために用いる属性をさらに詳細に図６に示
す。

【００６９】サーフェル属性４０１には、ポジション
(x)、オフセット(o)、色(rgb)、不透明度(∝)、法線
(n)、角速度(ｗ)、質量(m)及び８個までのリンクを含む
ことができる。リンク属性４０３には、残りの長さ
(l)、弾性定数(e)、減衰（ダンピング）定数(d)および
左右のサーフェルポインタ(p_lとp_r)を含むことができ
る。

【００７０】法線を各サーフェルと一緒に記憶する理由
は、レンダリング中法線の補間を避けるためである。代
わりに法線はサーフェルの生成中補間される。法線を記
憶することはレンダリング速度とサーフェルオブジェク
トに必要な記憶容量との間で交換を行うことである。

【００７１】各サーフェルは、モデル化を行っている間
サーフェルオブジェクトの動的状態を記述する追加属性
を持つこともできる。これらについては図１７と図１９
を参照してさらに詳細に後述する。

【００７２】２.１ サーフェル・リスト 図７に図示のように、本発明では処理中走査を最少化す
るためにシーケンシャル・リスト６００としてサーフェ
ルデータの組織化が行われる。リスト６００では、リス
ト中の隣接する２つのサーフェルがサーフェルオブジェ
クトの中でも隣接している。リスト６００を生成するた
めに、サーフェルS₀から処理が開始される。位置(x,y)
の“第一の”サーフェルとしてサーフェルS₀から始め
て、各隣接サーフェルがリストに追加され、最後のサー
フェルでS_nで終了する。オフセットによってリスト６０
０中のサーフェルへアクセスが行われる。オフセットと
は２つのサーフェル位置間の差ベクトルである。

【００７３】前のサーフェルに対するオフセットが記憶
され、サーフェルが高速に投影を行う能力が与えられ
る。オフセットが記憶されれば、ビューイング・マトリ
ックスを用いて各サーフェルのビュー座標を計算する必
要はなくなる。オフセットを記憶することによって、シ
ーケンシャル・リストあるいは配列としてサーフェルを
記憶することができる。リスト中で隣接しているサーフ
ェルはオブジェクト中でも隣接している。

【００７４】サーフェルは８連結されているので、サー
フェルがピクセル間隔（ピクセル空間）に位置している
とき、オフセットは、{±１,０,０}、{０,±１,０}、
{０,０,±１}のいずれかである。オフセットは特定のビ
ューについて予め計算することができ、ルックアップ・
テーブルに記憶することができる。サーフェルのオブジ
ェクト座標は、リンクされたリスト６００の前回のサー
フェル位置にオフセットを加えることによって生成する
ことができる。

【００７５】どのサーフェルを第一に選択するかはオブ
ジェクトに依存する。例えば、球面については、第一サ
ーフェルを球面の“最上部”に置くことができ、リスト
がその球面“の周りを包む”。“左”および“右”の隣
接サーフェルは、リストの中でも隣接していてもよい
が、“上”と“下”の隣接サーフェルはシーケンシャル
・リストのどこにでも定位できるということに留意すべ
きである。リスト中の隣接サーフェルがオブジェクト中
で隣接していない場合、サーフェルをリスト６００のど
こに定位してもよい。

【００７６】サーフェルは６辺の“セル”、つまりピク
セル・サイズの間隔をもつ三次元格子の中でゼロ次元点
として定義されているので、隣接サーフェルのセル間の
オフセットは多くのサーフェルについて同じになる。像
面への投影を高速化するために、各オフセットはスクリ
ーン−空間のオフセットへ一回だけ変換され、次いでル
ックアップ・テーブル（検索テーブル）に記憶される。
ルックアップ・テーブルは再計算することができる。投
影中、各サーフェルの各ビュー座標をテーブル検索を用
いて見つけることができる。

【００７７】３. サーフェルとサーフェルオブジェクト
の生成 サーフェルとサーフェルオブジェクトを生成するため
に、いくつかの可能な方法について説明を行う。

【００７８】３.１ 合成 暗黙面からの合成は、球面、平面および立方体、あるい
は解析的に定義できる他のオブジェクトなどのオブジェ
クトに対して通常使用することができる。本明細書で説
明したデータ構造を詳細に調査した後であれば、本発明
のデータ表現に準拠する合成サーフェルオブジェクトの
生成は当業者には明らかなことであろう。キーとなる概
念は、サーフェルの合成が像面分解能で行われ、隣接サ
ーフェルがリンクによって連結されるということであ
る。

【００７９】３.２ 変換 ポリゴンのような任意の幾何学オブジェクトは、変換に
よるポリゴンの生成を必要とする。この処理を変換と呼
ぶ。

【００８０】図８は、単一二次元平面７１０についてサ
ーフェルを生成できる順序を図示する。この順序は、格
子位置(x,y)から始まり、その後に(x+１,y)が続く等々
の順序である。矢印７１１は、隣接列に対して交互方向
を用いる、前後の、１列毎の生成順序を図示するもので
ある。第一列は左から右へサーフェルの生成を開始す
る。次列のサーフェルは右から左へ生成される。この順
序によって、各サーフェルのオフセットは各方向につい
ての単位ステップの範囲内に保持される。リスト６００
についてサーフェルが連続的に生成される。そして隣接
サーフェルのセル間のオフセットはx,yで(１,０,０)か
(０,１,０)のいずれかである。

【００８１】３.２.１ 三次元デジタル微分アナライザ
による変換 三次元スキャン変換を用いて従来技術のポリゴンオブジ
ェクトを本発明に準拠するサーフェルオブジェクトへ変
換することができる。Kaufman他の“ボクセルベースグ
ラフィックのための三次元スキャン変換処理”(対話型
三次元グラフィックに関する１９８６年ワークショップ
の会報、Crow F.、Pfizer S.M. (eds.)、p.４５〜７
５、１９８６年)に記載されているような方法の改造を
行った。Kaufmanの方法ではポリゴンがボクセルへ変換
される。Kaufmanは、大きな平面に平行な円を描くアル
ゴリズムを用いている。円は赤道地域と極地域の２つの
領域に描かれ、その一方で、対称変換を用いて、両半球
体を同時に生成することによりアルゴリズムの単純化が
行われている。これとは対照的に、本発明ではポリゴン
はシーケンシャル・リストに記憶された６つの隣接する
８連結されたサーフェルに変換される。

【００８２】本発明のポリゴンの三次元スキャン変換で
は、ポリゴンのエッジの三次元ラインスキャン変換が用
いられる。エッジ間のサーフェルの連続は充たされて最
適の連結性が与えられる。スキャン−ラインはy座標軸
に平行であるため、本発明の方法ではポリゴンのエッジ
をyでソートする必要がある。

【００８３】ＤＤＡ処理は二次元ディスプレイ上でライ
ンをラスター化するために元々開発されたものである。
特定のラインについて、開始点および終了のピクセル位
置およびΔxとΔyが計算される。次いでΔxとΔyを２つ
のデルタ値のうちの最大値で割り、この処理に要するス
テップ数をこの最も大きいデルタに等しくセットする。
この最も大きいデルタの方向の各ステップについて、も
う一方の方向のデルタ値に従ってピクセル位置を計算す
る。この処理は単純でかつ効率的である。

【００８４】図８に図示のように、ＤＤＡ処理は次のよ
うにポリゴン７００に適用される。三角形７００の３つ
のエッジのうちの１つを“ベース・エッジ”７０１とし
て選択し、一方、残りの２つのエッジ７０２と７０３を
“ガイダンス・エッジ”として選択する。処理がガイダ
ンス・エッジに沿って別の増加ステップに進むたびに、
ベース・エッジに平行な線７０４が三次元でラスター化
される。

【００８５】本発明の処理は、本発明のベース・エッジ
が三次元で任意の方向をとることができるのでKaufman
のアルゴリズムとは異なる。Kaufmanのアルゴリズムで
は、ポリゴンがxz座標平面と一致しない限りベース・エ
ッジは常にy座標軸に対して平行であり、一致する場合
ベース・エッジはx座標軸に平行かz座標軸に平行かのい
ずれかである。

【００８６】ポリゴン面の法線を計算し、ポリゴンが長
軸によってスパンされた平面に平行かどうかを検出す
る。この場合、一定の最適化処理を行うことができる。

【００８７】ベース・エッジ７０１について、Δx、Δ
y、Δzの値を計算し、これら３つのデルタ値の中の最も
大きいΔ_maxを決定する。３つの増分、すなわち、 x_incr＝Δx/Δ_max、 y_incr＝Δy/Δ_max、 z_incr＝Δz/Δ_max の合計を計算する。

【００８８】x、y、zに沿って最も大きいデルタの方向
に進むことはその結果としてベース・エッジに沿った三
次元のサンプル位置を生じることになる。三角形７００
のスキャン変換を行うために、２つのガイダンス・エッ
ジのx、y、z方向のデルタ値を同様に決定する。再度１
エッジ当たり３つの増分の合計を計算するが、今度は両
ガイダンスエッジの最も大きいデルタでこれらのデルタ
値を割る。これを行う理由は、ガイダンス・エッジに沿
うステップが、スキャン変換される平行エッジの各々に
対してベース・エッジの方向を維持することを保証する
ためである。

【００８９】２つのガイダンス・エッジに沿う各増加ス
テップの後、このベース・エッジに平行なエッジの三次
元ラスター化を行う。ガイダンスエッジに沿う各増加ス
テップは結果としてそのエッジの長さの減少を生じる。
エッジの三次元ラスター化中得られる各サンプル位置
に、その位置に対するサーフェルが記憶される。

【００９０】図９に図示のように、８連結性を与えるた
めに加えられるサーフェルは、三角形７００の内部にだ
け加えられる。図９では、サーフェル８０１と８０２の
いずれかをリスト６００に加えることができる。どのサ
ーフェルが内部に存在するかを決定するために、ベース
・エッジ７０１に対する頂点７１０の相対的位置を決定
する。この位置は、頂点７１０を指すとともにベース・
エッジ７０１に対して垂直な内部方向ベクトル７２０に
よって達成することができる。内部方向ベクトル７２０
に応じて、２つの候補サーフェルのうちの一方、この例
ではサーフェル８０１を選択する。

【００９１】サーフェルがシーケンシャル・リストに加
えられるたびに、サーフェルの位置はその位置に応じて
ハッシュ・テーブルに記憶される。サーフェルが加えら
れる前に、ハッシュテーブルに対するチェックが行われ
その位置におけるサーフェルがすでに存在するかどうか
が決定される。

【００９２】３.２.２ 距離マップによる変換 従来技術では、距離マップを使用して、サンプリングさ
れたボリューム中で正確に面ボクセルを表現してきた。
ボリュームの距離マップはそれ自身三次元ボリュームで
ある。各格子位置について、距離マップはオブジェクト
の面までの最短距離を記憶する。これらの距離は、解析
的記述から計算するか、ボリューム中のバイナリセグメ
ント化データから抽出するかのいずれかで求めることが
できる。

【００９３】距離マップは、ボリュームからオブジェク
トの表面の正確な復元を行う特性を有する。距離マップ
の勾配によって面法線の方向が得られる。距離の符号に
よってボリュームの内部と外部が識別される。オブジェ
クトの面は距離マップ中でゼロ距離に定位される。距離
マップは、オブジェクトの表面にわたって滑らかに変化
するので、高い空間周波数が回避され、それによって比
較的に低価格の復元フィルタを用いる表面の復元が可能
になる。

【００９４】図１０は、距離マップを用いてオブジェク
トを面エレメント化する処理９００のステップを示すも
のである。ステップ９１０で、面ポリゴン（サーフェス
ポリゴン）(例えば、図１１に図示のような三角形１０
００)はサンプリングされたボリュームデータ９０１か
ら推定される。ポリゴン１０００はトリ・ストリップを
用いて記憶することができる。三角形メッシュ中の各ポ
リゴンは１００１から１００３などの３つの頂点からな
る。n個の三角形を記憶するためには、n+２個のノード
が必要となる。

【００９５】ステップ９２０で、トリ・ストリップデー
タが読み込まれ、トリ・ストリップ用の境界ボックス
(バウンディング・ボックス、bounding box)がステップ
９３０で決定される。ピクセル・サイズの間隔を有する
ボリュームはステップ９４０でバウンディング・ボック
スに従ってトリ・ストリップの周りで定義される。ボリ
ュームの大きさはバウンディング・ボックスの大きさよ
りわずかに大きいが、これはトリ・ストリップがボリュ
ームの境界のいずれとも一致しないようにするためであ
る。この条件によって、オブジェクトの面がどこに定位
しているかを決定することができるが、これについては
以下でさらに説明する。

【００９６】以下に詳細に説明するように、ステップ９
５０で、ボリュームの各整数格子点の位置の三角形まで
の最短距離が決定される。ステップ９６０で、ボリュー
ムの中を走査して、１/２×２^1/2（すなわち、ルート２
の１／２の値）以下の距離を含む格子点のサーフェルが
加えられる。この距離はサーフェルを含むセルの面・対
角線の１/２である。以下さらに詳しく説明するよう
に、本発明では、ホールの発生を防止するために１/２
×２^1/2のスケーリング係数が選択される。

【００９７】距離計算 上述したように、トリ・ストリップ１０００中の各三角
形について距離を計算するために、さらに大きなボリュ
ームの一部であるサブボリューム(拡大した境界ボック
ス)が三角形の周りで定義される(図１２も参照された
い)。サブボリュームの各格子位置について、三角形ま
での距離が計算される。この方法によって、点Pから頂
点V₀、V₁、V₂を有する三角形１１００までの三次元の最
短距離と法線Nが計算される。

【００９８】点Pからこの三角形までの三次元距離を計
算するために、平坦な三角形によって定義される平面上
への点Pの垂直投影が三角形の内部にあるかどうかが決
定される。Pの投影が三角形の外部にある場合には、三
次元の最短距離はエッジまたは頂点の１つに対して垂直
なPからのベクトルの大きさである。Pの投影が三角形の
内部にある場合には、三次元の最短距離は、Pから三角
形の中にその投影された点P'までのベクトルの大きさで
ある。三角形の平面上へのPの投影を決定するために、P
₁とNの点乗積を計算することによってPは法線N上へ投影
される。Pから投影されたベクトルを減じて投影された
点P'が得られる。

【００９９】図１３と図１４は三角形１１００の二次元
投影を示す。投影された点P'は図１３の三角形の内部に
ある。エッジに対して垂直なすべてのベクトルもこの場
合内部を指向する。図１４で、ボールド体の矢印で表さ
れたエッジV₀V₁に対して垂直なベクトルは外部を指向す
るのに対して、もう一方の２つのベクトルは内部を指向
する。この図は、P'がエッジV₀V₁に対して最短の所にあ
ることも示している。三次元の場合これは次のように決
定される。

【０１００】ベクトルPV_iとV_jV_i(V_jはエッジの終点、V_i
は始点)によって法線N'を決定する平面が定義される。
P'が内部にある場合この法線は三角形の内部の“方へ向
かって”指向し、内部にない場合には三角形から離れる
方向へ指向する。P'が内部にあるか外部にあるかは三角
形の法線NとN'の点乗積の符号を用いて検出することが
できる。この計算を行うためのCスタイル擬似符号とし
てこれらのステップが図４２に詳述されている。

【０１０１】ストリップ中の各三角形のサブボリューム
の格子位置のすべてについて、および、オブジェクトの
すべての三角形ストリップについて距離計算を行う。サ
ブボリュームがオーバーラップするので、いくつかの位
置は複数の計算した距離を有していてもよい。この場合
最短距離が使用される。

【０１０２】面オブジェクトは距離がゼロの位置に定位
されている。このゼロ距離は、８格子位置によって囲ま
れているセルの内部のどこかにある。したがって、ボリ
ュームの中を走査するとき、ボリュームの中で距離の絶
対最小値に出会うときはいつでも、サーフェルが加えら
れる。この理由はオブジェクトがボリュームの境界のい
ずれとも一致しないためである。面まで１/２×２^1/2の
距離またはそれより近い距離にある各格子位置について
サーフェルが８連結性の中に加えられることを保証する
ために、サーフェルが加えられる。

【０１０３】図１５は１/２×２^1/2値を選択する理由を
例示する図である。８つの格子点１３０１〜１３０８に
よって囲まれているボリュームに６面からなるセル１３
００を考える。セル１３００は、斜めの(奇数の)格子点
を少し外れたオブジェクト面１３１０によって斜めに分
割される。言い換えれば、斜めの格子点における距離は
ほとんどゼロであるが、正確にはゼロではない。これら
の位置にサーフェルを生成する必要がある。しかし、こ
れらのサーフェルは８連結されない。そのため、偶数位
置１３０２と１３０６、あるいは位置１３０４と１３０
８のいずれかの位置に追加サーフェルを生成しなければ
ならない。例えば、この面が、奇数の格子点“の左の”
セルの中を切って通る場合、格子点１３０４と１３０８
の距離は１/２×２^1/2より少し短くなり、これらの位置
に対してサーフェルが加えられ８連結性が与えられる。

【０１０４】しかし、この面が正確に奇数の格子点の中
を切って通り、それらの点における距離がゼロで、か
つ、偶数の格子点についての距離が１/２×２^1/2である
場合、すべての８つの格子点でサーフェルを加える必要
がある。これは最悪の場合である。これがオブジェクト
の全面について生じる場合、その結果生じる面はセルの
面／対角線の長さなどのような一定の厚さ(２^1/2)を有
する。

【０１０５】３.２.３ 距離マップと比較したＤＤＡ 三次元DDA面エレメント化の利点はこの面エレメント化
を単純化できることである。ラインに沿って新しい位置
を計算する整数演算による処理が可能である。距離マッ
プを用いる面エレメント化はさらに複雑でまた一層多く
のメモリを必要とする。距離計算に使用するボリューム
は、面エレメント化を行っている間メモリに記憶しなけ
ればならない。これらのボリュームは非常に大きなもの
になる場合がある。

【０１０６】距離マップを用いる変換はあらゆる整数格
子位置について三角形までの距離計算を必要とするけれ
ども、ボリュームの１セルの中を再三走査することはな
いので、サーフェルがすでに存在するかどうかをチェッ
クする必要はなくなる。このようなチェックは三次元DD
Aについての変換に必要とされるものである。

【０１０７】上述したように、レンダリングを行うため
にサーフェルのリスト中を効率良く走査するために、サ
ーフェルは連続的にリスト６００に記憶される。三次元
DDA処理を加えた結果、各増加ステップで“左から右
へ”から“右から左へ”というようにスキャン変換の方
向を単に交互に変更することによって、各三角形につい
てサーフェルのシーケンシャル・リストが得られる。距
離マップを用いる面のエレメント化によって、サーフェ
ルがリストへ加えられる順序はボリュームが走査される
順序に準拠する。この順序はスライス毎に行われ、各ス
ライスの内部ではサーフェルの順序で行われる。

【０１０８】図１６は、ポリゴンが凸型である限り、任
意のポリゴン１４００を面エレメント化するために三次
元DDA処理を拡張する方法を図示するものである。この
目標に達するために、ポリゴンの頂点１４０１〜１４０
６はある順序、例えば時計回りで配列される。ベース・
エッジ１４１０と２つのガイダンス・エッジ１４１１〜
１４１２が選択される。面エレメント化ラインが頂点１
４０５に達したとき、ガイダンスエッジ１４１３がエッ
ジ１４１２に替わる。同様に、頂点１４０２に達したと
き、エッジ１４１４がエッジ１４１１に替わる。このよ
うにして最終的にエッジ１４１５が使用される。

【０１０９】距離マップは任意の凸型ポリゴンについて
利用することもできる。三角形について三次元距離を計
算する同じ処理を適用することができる。この処理によ
って、最短エッジまたは頂点を決定するために、より多
くのエッジと頂点に対して格子位置をチェックする余分
のコストが導入される。

【０１１０】３.３ボクセルからのサーフェルの抽出 以下のようにボリュームデータ集合からサーフェルを生
成することができる。第一のステップで、像面の分解能
に合わせてボクセルの再サンプリングを行う。第二に、
オブジェクトの面境界のボクセルを抽出し、次いでボク
セルを点サンプルあるいはサーフェルへ変換する。第三
に、リンクによって６隣接サーフェルを連結する。この
ステップで、追加ボクセルを抽出し８連結性の生成を要
求してもよい。最後のステップで、ボリュームデータの
欠如に起因して生じる表面のいずれのギャップも補間に
よって充たすことができる。

【０１１１】３.４ 粒子雲のサーフェルへのマッピング 以下のように粒子雲をサーフェルへマップすることがで
きる。まず、雲の周りにスクリーン分解能で格子を配置
する。各セルを調べる。セルが正確に１つの粒子を含む
場合、粒子を直接サーフェルへマップすることができ
る。セルが２つ以上の粒子を含む場合、粒子を単一サー
フェルにマージする必要がある。セルが粒子を含まない
場合、隣接セルの粒子からサーフェルを補間する必要が
ある。

【０１１２】３.５ 細部レベルの生成 サーフェル表現は、細部を様々なレベルに設定して“ズ
ーミング”つまり投影中に像面とオブジェクト間の距離
の変更を容易にすることができる。サーフェルの生成後
あるいはその生成中、フィルタを利用して細部を様々な
レベルに設定することができる。通常これはレンダリン
グを行う前の前処理ステップとして行われる。フィルタ
リングとダウンサンプリングを行って、さらに低い(さ
らにきめの粗い)分解能のサーフェルオブジェクトを生
成することができるし、アップサンプリングとフィルタ
リングを行ってさらに高い(さらにきめの細かい)分解能
サーフェルオブジェクトを生成することもできる。例え
ば、図２に図示の４つの隣接サーフェル１００に対する
属性値を平均化して細部オブジェクトについてさらに低
いレベルのサーフェルにすることができる。他のフィル
タリングやサンプリング方法をサーフェルの様々な組み
合わせに適用し、種々のレベルの細部(１６、４、１、
１/４、１/１６、１/２５６等々)を提供することができ
る。

【０１１３】４. グラフィックオブジェクトの物理ベー
スのモデル化 グラフィックオブジェクト間の相互作用を示す物理ベー
スの実際のシミュレーションでは、剛体力学によるモデ
ル化と動的変形によるモデル化の２つのタイプのモデル
化が通常利用される。

【０１１４】剛体力学モデルについては、グラフィック
オブジェクトは、外力やトルクを受け易いということは
あるものの、そのまま剛性状態にとどまる。位置、方
向、速度、質量の中心、慣性係数のようなパラメータを
用いてニュートン力学に従って時空中のオブジェクトの
経路のシミュレーションが行われる。剛体力学の１つの
特徴は、オブジェクトの形状が常時変化しないままに保
たれることである。

【０１１５】さらに、この力学には制約を設けることも
できるし無制約のままにすることもできる。制約を設け
た剛体力学では、オブジェクト間の相互作用(衝突など)
を発生させることができる。無制約の剛体力学では、他
のオブジェクトの運動とは無関係にオブジェクトが運動
する。

【０１１６】動的変形モデルについては、オブジェクト
はオブジェクト中の潜在的にすべての面エレメントの質
量、位置、速度を利用する内力と外力に支配される。本
発明では、サーフェルオブジェクトへの動的変形を行う
物理ベースのモデル化を適用する質量バネシステムが利
用される。サーフェルは点質量であり、サーフェルを連
結するリンクは質量の実際の物理的振る舞いをモデル化
するバネとして振る舞う。

【０１１７】４.１ サーフェルオブジェクトに関する剛
体力学 剛体の物理ベースの力学を示すシミュレーションによっ
て、自然法則に従って実世界で振る舞うようなオブジェ
クトの振る舞いが処理される。オブジェクトが重力とト
ルクのような力を受けたときの実際の振る舞いが模擬さ
れる。この振る舞いに制約を設けないとき、他のオブジ
ェクトとの衝突を心配することなくサーフェルオブジェ
クトは完全に自由にどこへでも移動することができる。
本発明では、衝突のような制約を設けた剛体シミュレー
ションを処理するためにこのモデルが拡張される。

【０１１８】図１７に図示のように、剛性状態を利用し
てサーフェルオブジェクトに対して剛体力学が適用され
る。

【０１１９】位置および方向 ある時刻tにおける剛体サーフェルオブジェクトの位置
をベクトルx(t):(X,Y,Z)と記述する。このベクトルによ
って、“ワールド空間”座標系の原点からオブジェクト
の現在位置へのオブジェクトの平行移動が指定される。
オブジェクトの方向は、“四元数算法”呼ばれる４つの
変数の組によって定義される。この組は回転マトリック
スR(t)(３×３マトリックス)を反映し、このマトリック
スはそれ自身の局所座標系の３つの軸の回りでオブジェ
クトを回転させる。

【０１２０】

【数１】

【０１２１】上式によって、ワールド座標系での点Pに
対する、回転マトリックスの局所座標系における剛体サ
ーフェルオブジェクトの面上の点p₀の位置が定義され
る。

【０１２２】本発明では通常の回転マトリックスの代わ
りに四元数算法が使用される。四元数算法とは、q(t)＝
(q_s,q_x,q_y,q_z)と表記される４つの数からなるリストで
ある。本発明では、四元数算法を現実の部分q_sと仮想の
部分(X,Y,Z)とに分ける。２つの理由から四元数算法が
使用される。

【０１２３】第一の理由は、回転マトリックスで必要と
する９つの変数の代わりに、四元数算法では４つの変数
しか必要としない。そのため状態ベクトルのサイズが小
さくなり、必要な計算が少なくなるという理由である。
第二の理由は、状態ベクトルは数値によって積分され時
間毎に解が進むので、変数は数値のずれに支配されるこ
とになる。これは数値誤差が蓄積することを意味する。
四元数算法は、回転マトリックスに比べてはるかにずれ
がすくない。また、四元数算法の大きさは正規化されて
いるので、本発明では、四元数算法を繰り込ませること
によって誤差を容易に回復することができる。

【０１２４】四元数算法には他の利点もある。現実部分
と仮想部分とに四元数算法を分けることは回転角と軸を
識別するのに役立つ。四元数算法が正規化されていると
いうことは四元数算法の大きさが１に等しいことを意味
する。仮想部分はオブジェクトが回転する軸を定義す
る。回転部分はラジアンで表される。例えば、単位軸u
の回りのθラジアンの回転は、次式（２）によって表さ
れる。

【０１２５】

【数２】

【０１２６】四元数算法は数値積分の中で用いられる。
レンダリングを行うために実際の回転マトリックスが必
要となるとき、四元数算法は回転マトリックスへ変換さ
れる。積分を用いて一組の微分方程式の解を求める必要
があるとき、この回転マトリックスは四元数算法へ再度
変換される。

【０１２７】速度および角速度 時間毎のオブジェクトの位置はその速度に依存する。オ
ブジェクトの速度はx(t)の導関数をとることによって決
定される。

【０１２８】

【数３】

【０１２９】サーフェルオブジェクトの方向が固定して
いる場合、ワールド空間の中を通るオブジェクトの運動
はその線速度に起因する。オブジェクトが回転する場
合、x'(t)が得られるとq'(t)に対して類似のパラメータ
が決定される。

【０１３０】ｗ(t)をサーフェルオブジェクトの角速度
と呼ぶことにする。ｗ(t)は、サーフェルオブジェクト
が回りを回転している軸方向を有するベクトルである。
ｗ(t)の大きさ(|ｗ(t)|)はオブジェクトの回転速度を示
す。q(t)の導関数q'(t)は、仮想部分をｗ(t)としてと
り、ｗ(t)から四元数算法を生成し、ゼロ値の現実部分
を加えることによって得られる。

【０１３１】

【数４】

【０１３２】

【数５】

【０１３３】但し、q_w(t)q(t)は、四元数算法q_w(t)とq
(t)とを乗じたものである。

【０１３４】位置、方向、速度および角速度は一緒にな
って剛体シミュレーションの状態ベクトルを構成する。
状態ベクトルには、次式（６）に示すように、合計１３
個の変数が含まれる。

【０１３５】

【数６】

【０１３６】これらの１３個の変数は積分中時間ステッ
プ毎に更新される。サーフェルオブジェクトの振る舞い
を記述する微分方程式を組立てるとき、すなわち、時間
毎の状態ベクトルの値を記述するとき、数値積分を用い
てこの式の解を求めることができる。

【０１３７】

【数７】

【０１３８】ここで、関数fによって、x(t)の導関数を
計算する。関数fは、時間t後の状態ベクトルxの状態を
記述する。一旦関数fがわかると、ワールド空間の中に
あるサーフェルオブジェクトの新しい位置、方向、速度
および角速度を導き出すことができる。関数fを解くた
めに状態ベクトルxの導関数を計算する。

【０１３９】他の量 本発明ではx(t)からx'(t)を計算するために何らかの追
加の状態変数が用いられる。オブジェクトが加速を受け
ているとき、サーフェルオブジェクトの新しい速度が計
算される。本例の力はユーザー入力の結果から生じる重
力である。速度vは加速度aに等しいので、本発明では、
次式（８）を使用する。

【０１４０】

【数８】

【０１４１】加速度aを計算するためには、サーフェル
オブジェクトの質量を知る必要がある。サーフェルオブ
ジェクトの質量は本発明のシミュレーション中変化しな
いので、シミュレーションの前処理状態のすべてのサー
フェルの質量を累積することによって、サーフェルオブ
ジェクトの総質量を計算することができる。

【０１４２】角加速の計算を行うための力Fと等しい力
はトルクである。トルクはオブジェクトを回転させるよ
うに働く。この力が質量の中心と一直線上に並んでいる
ときは何も生じないが、この力がオブジェクト上のどこ
か他の場所の点に印加されるやいなやこの力はオブジェ
クトを回転させる。

【０１４３】角加速度を計算するために、本発明では角
速度の導関数を用いる。本発明では質量に類似したエン
ティティを用いてサーフェルオブジェクト上に働いてい
るトルクから角加速度を決定する。このエンティティは
慣性テンソルI(t)と呼ばれる３×３マトリックスであ
る。テンソルは、時間毎に変化しないのでシミュレーシ
ョンの開始前に通常計算される。テンソルはサーフェル
オブジェクトの質量をどのようにオブジェクトのボリュ
ームに沿って配分するかを記述する。実際には、この３
×３マトリックスを３つのエントリのベクトルへ演繹す
ることができる。

【０１４４】角加速度を表す式を導き出すために、本発
明では次式（９）の角運動量L(t)を用いる。

【０１４５】

【数９】

【０１４６】また、次式（１０）で与えられる角運動量
L(t)の導関数を用いて、ｗ'(t)を表す次式（１１）が導
き出される。

【０１４７】

【数１０】

【０１４８】

【数１１】

【０１４９】剛体シミュレーション 図１８に図示のように、時間に依存しているオブジェク
ト１６０１の剛性状態１６００が状態ベクトル１６０２
へコピーされる。この状態ベクトルは、時間ステップh
の新しい状態ベクトル１６０３を生成する数値積分器１
６１０の入力としての役割を果たす。状態ベクトル１６
０３は、時空中のオブジェクトの新しい位置と方向が後
続処理ステップとして認識できるように再びサーフェル
オブジェクトの状態１６００中へコピーされる。

【０１５０】衝突検出と接触力 無制約剛体サーフェルオブジェクト運動について今まで
説明を行った。衝突に対してオブジェクトを反応させた
いとき、物理法則に従って２つのオブジェクト間のエネ
ルギーと運動量の交換が計算される。この結果剛体の振
る舞いが生じ、オブジェクトは衝突後空間中の新しい経
路を辿るようになる。計算された力はオブジェクトによ
って吸収されず、すべての力は、新しい速度で新しい方
向へオブジェクトを向けるために使われる。材料特性に
よってオブジェクトの動的変形が可能な場合にも、エネ
ルギーの交換が計算される。これは、衝突中エネルギー
が放散し吸収することがあるためである。

【０１５１】１つのオブジェクト中のすべてのサーフェ
ルをもう一方のオブジェクトと比較しなければならない
場合があるので、２つのサーフェルオブジェクト間の衝
突検出には多額の計算費用が必要となる場合がある。こ
の問題を避けるために、本発明では、各サーフェルオブ
ジェクトについて、球面の代わりに十二面体などの多面
体バウンディング・ボックスを生成する。適正な量のポ
リゴンを備えたバウンディング・ボックスによってサー
フェルオブジェクトの表面を一定の正確さに近似するこ
とができる。そして衝突のチェックを必要とするポリゴ
ンの数を減らすことができる。

【０１５２】２つのサーフェルオブジェクト間での衝突
を検出したとき、これらのオブジェクトの面上に関心の
対象である領域(ポリゴン)を決め、実際の衝突サーフェ
ルを探索する本発明のサーチを開始する。それによって
１つ１つのサーフェルをすべての他のサーフェルについ
てチェックする初期タスクを減らすことができる。衝突
に参加しているサーフェルを見つけたとき、サーフェル
オブジェクトの状態ベクトル中の属性から接触力を導き
出すことができる。

【０１５３】サーフェルレベルで接触力を決定後、新し
い速度や方向のような、衝突の結果生じる状態の変化を
計算することができる。また、次に説明する質量バネシ
ステムなどを利用してサーフェルオブジェクトの変形を
開始することができる。

【０１５４】４.２ サーフェルオブジェクトにおける変
形の動的モデル化 剛体モデル化はオブジェクトの動的変形を処理するもの
ではない。オブジェクトに働く力に応じてオブジェクト
がその形状を変えるとき、本発明ではサーフェルオブジ
ェクトの内部で個々のサーフェルを処理するモデルを用
いる。サーフェルオブジェクトは個別の点サンプルから
組立てられるので、オブジェクト中のすべてのサーフェ
ルの運動シミュレーションを行うことによって、サーフ
ェルオブジェクトの動的変形を示すシミュレーションを
行う。

【０１５５】特に、すべてのサーフェルは、図１９に図
示のようにサーフェルに対して働く位置、速度、力およ
び質量を有する。したがって、すべてのサーフェルにつ
いて、次式（１２）及び（１３）により定義する。これ
らは上記の剛体力学の場合と同じである。

【０１５６】

【数１２】

【０１５７】

【数１３】

【０１５８】また、剛体力学の場合と同じように、サー
フェルオブジェクトの状態を示すスナップ写真を撮影し
てシミュレーションを生成することができる。サーフェ
ルオブジェクト中に存在するすべての単一サーフェルの
状態を反映する状態ベクトルを生成する。剛体力学の場
合と同様、この状態ベクトルを数値積分計に入力し、時
間間隔hの終点におけるすべてのサーフェルの新しい状
態を反映する新しい状態ベクトルを計算する。

【０１５９】図１９は、変形シミュレーション中サーフ
ェルオブジェクト１７０２の各サーフェル１７０１と関
連づける変数１７００を示すものである。サーフェルは
ゼロ次元点としてモデル化されるので、サーフェルの方
向を記憶する必要はない。サーフェル状態の時間に依存
する内容から状態ベクトルを以下のように定義する。

【０１６０】

【数１４】

【０１６１】サーフェルが変位するとき力が出現し、こ
の力の出現によって２つのサーフェル間の自然の距離に
分裂(disruption)が生じる。この分裂はサーフェルリン
クによってモデル化される。そのようなサーフェルの変
位はユーザー入力によるサーフェルオブジェクト間の衝
突という結果を招来する場合がある。

【０１６２】４.２.１ 質量バネシステム 図２０は質量バネシステムにおいてリンク１８０２によ
って連結されたサーフェル１８０１の格子としてモデル
化されるサーフェルオブジェクト１８００の一部を図示
するものである。サーフェル１８０１は質量を担持し、
リンクはオブジェクト全体にわたって力を伝える。力が
一時的なものであるとき、オブジェクトは力が印加され
る前に持っていたそれ自身の元の形へ戻ろうとして動
く。この場合、オブジェクトは記憶（メモリ）を持って
いる。

【０１６３】記憶（メモリ）はリンクに記憶される。サ
ーフェルオブジェクトを生成するとき、共通リンクを共
有する２つのサーフェル間の自然の距離が決定される。
この距離は、サーフェルリンクの属性の中の１つとして
記憶される残り長さ４２０である(図５参照)。リンクを
共有する２つのサーフェル間の距離が乱れることは、自
然のリンクの長さを決める法則に違反することを意味す
る。この結果サーフェルレベルに力が生じる。この力は
単一サーフェルについて計算されるのでバイナリ力と呼
ばれる。この力の計算はバネについてのフックの法則を
適用して行うことができる。

【０１６４】

【数１５】

【０１６５】

【数１６】

【０１６６】ここでf_iはサーフェルiに働く力であり、k
_sはリンクの弾性成分であり、k_dは減衰（ダンピング）
係数である。残りの長さはl₀である。リンクは２つのサ
ーフェルを連結するので、もう一方の端部にあるサーフ
ェルjに対して逆向きの力が印加される。d＝(x_i−x_j)を
計算して、リンクの両終点間のベクトルが定義される。

【０１６７】値|d|は そのベクトルの長さを定義し、d^*
＝d/|d|はその方向の単位ベクトルである。最終的に、|
d'|は同時的長さの変化である。それらの速度の差を取
り、その結果に単位ベクトルdを乗じることによってこ
の変化を計算する：(v_i−v_j)d ^*。

【０１６８】残りの長さl₀が有効でないとき、量(|d|−
l₀)はゼロとなる。この値は、ゼロでない場合には、違
反(violation)の量を乗じたリンクの弾性係数に依存す
ることになる。

【０１６９】リンクを共有する２つのサーフェルが様々
な方向へ動くとき、２つのサーフェル間の距離の変化が
得られる。この距離が残りの長さと異なるとき、リンク
の自然の長さが乱れる(disturbed)ので、力が両サーフ
ェルに対して働くことになる。リンクは、これら２つの
サーフェルを適切に再記憶しようとする。

【０１７０】図２１は、８つまでの他のサーフェルと連
結（接続）したサーフェル力を蓄積するために利用でき
る手順１９００を示す図である。この手順は、シーケン
シャル・リスト６００(図７)中のサーフェル毎に適用さ
れ、既存リンクのチェックが行われる。

【０１７１】あるリンクが見つかると、関数コンピュー
ト・フォース（Compute_Force）が呼び出され共通リン
クによって連結した両サーフェルに働いている力が計算
される。すべての単一サーフェル中のすべての力が決定
された後、積分計用の導関数が生成される。

【０１７２】リンク中の弾性係数と減衰（ダンピング）
係数の両方を用いて、モデル化されたサーフェルオブジ
ェクトの材料特性を調整することができる。自然の張力
の振る舞いを考慮し、弾性係数を適宜選択しながら、試
行錯誤を通じてこれらの量を見つけることができる。

【０１７３】減衰（ダンピング）は弾性係数と相関して
振動に起因して材料が壊れることのないようにしなけれ
ばならない。k_d＝２(m'k_s)^1/2のとき、システムは決定
的に減衰すると言われている。値m'は等価質量である。
リンクはリンクの各端部のサーフェルによって重み付け
が行われるので、リンクはただこれら２つの質量、つま
り、m'＝m/２を“理解している”と想定することができ
る。実際、リンクは積分計を介してリンクの貢献値(con
tribution)を他のサーフェルへ移すので、等価質量は大
きくなる。

【０１７４】両方の係数を選択する際注意する必要があ
る。弾性と減衰がきちんと一致しないと振動が生じるこ
とがあり、この振動によってすべての積分ステップで激
しくなる力の連鎖反応が引き起こされ、最終的結果とし
て面の引き裂きを伴う場合がある。この現象は、減衰係
数が十分に大きくないために、お互いから離れて動いて
いくサーフェルを制御できないときに生じる。

【０１７５】シミュレーションの実行 図２２は、衝突などに起因するサーフェルオブジェクト
の物理ベースの動的変形を行う処理２０００を示すもの
である。サーフェルオブジェクト２００１には、リンク
２００３によって連結した複数のサーフェル２００２が
含まれる。多くのサーフェルがサーフェルオブジェクト
中にあるので、各サーフェルの状態ベクトルが鎖状に繋
がれ、完全なサーフェルオブジェクト２００１のサーフ
ェル位置と速度からなる１つの大きな状態ベクトル２０
１０が形成される。

【０１７６】この結果、長さ６nの組み合わされた状態
ベクトルが生じる。但し、nはオブジェクト中のサーフ
ェル数である。これらの力は手順１９００によって蓄積
され、ステップ２０２０で統合されて新しい状態ベクト
ル２０３０が生成される。この新しい状態ベクトル２０
３０を用いて個々のサーフェル２００２の状態を更新す
ることができる。

【０１７７】図２３は、図２２の処理２０００で使用で
きるラッパー手順２１００を示すものである。この手順
によって状態ベクトル２０１０が生成され、すべてのサ
ーフェルで力を蓄積する処理１９００が呼び出される。
ラッパー２１００によって積分計２０２０も呼び出され
る。誤差スケールによって許容誤差の量が測定される。

【０１７８】４.２.２ 変形後のサーフェル法線の決定 変形が行われている間サーフェルにはピクセル格子に対
する制約がもはや設けられていないので、変形後のサー
フェルオフセットと法線について再考しなければならな
い場合もある。サーフェルオフセットはシーケンシャル
・リスト中の前のサーフェルまでの距離を測るものであ
るため、これらのオフセットは変化する場合がある。こ
れらのオフセットは新しい位置を持つ任意のサーフェル
について再計算することができる。

【０１７９】さらに大きな問題は、図２４〜２６に図示
のように変形シミュレーション中サーフェル法線が変化
しないという事実である。図２４は、サーフェル法線２
２１１を備えた面エレメント化されたポリゴンの部分２
２１０を図示するものである。図２５に図示のように変
形部分２２２０を備えていても、サーフェル法線２２２
１は依然としてシミュレーション前の状態と同じであ
る。サーフェルオブジェクトがレンダーされるとき、上
記の事実は、明らかに誤った表現を結果としてもたらす
ことになろう。この部分に対する正しい法線２２２１は
図２６に示されている。

【０１８０】法線２２２１は、変形サーフェルの中を通
過する接線平面から得ることができる。サーフェルは連
結（接続）しているので、接線平面に存在する２つの非
共線ベクトルを２つの最近傍隣接サーフェルについて得
ることができる。この最近傍隣接サーフェルはサーフェ
ルリンクから得ることができる。

【０１８１】５. 面エレメントのレンダリング サーフェルオブジェクトは、モデル化を行った後、表示
装置やプリンタ上にレンダーすることができる。上述し
たように、サーフェルは(面)ボクセルと近い類似点を有
する。両方とも格子上に定義される。ボクセルの典型的
定義は、ボクセルを、ボリュームの整数格子位置に定位
される値あるいはサンプルであると考えるものである。
本発明に準拠する各サーフェルは像面上に１ピクセルを
投影する。本発明では全体として、オブジェクトオーダ
ーレンダリング投影処理が用いられる。ピクセルに対し
て１対１マッピングが行われるためラスター化を必要と
しない。

【０１８２】ズーミング、すなわち、種々のレベルの細
部でサーフェル表現を行うことによって、サーフェルオ
ブジェクトと像面との間の距離の変更が容易になる。こ
の場合、ほぼ１ピクセルが１ピクセルに対して投影する
とき、対応するレベルの細部を有する表現が選択され、
サーフェルとピクセルとの間に１対１のマッピングが維
持される。

【０１８３】図２７は、サーフェルオブジェクトのため
のレンダリングパイプライン２３００を示す図である。
パイプライン２３００には対応する座標空間で働く５段
階２３０１〜２３０５がある。レンダリング中、各サー
フェルＳは１３組のベクトルとして定義することがで
き、その中には以下のものが含まれる。

【０１８４】

【数１７】

【０１８５】ここで、XYZはサーフェルのポジション
（位置）、oはオフセット、nは面法線、rgbはサーフェ
ルの色、そしてαはサーフェルの不透明度である(図５
参照)。

【０１８６】レンデラー２３００は図７のリスト６００
中の第一サーフェルから開始される。このサーフェルが
カメラ位置のためにクリップされなかった場合、サーフ
ェルの位置はビューイング・マトリックスMに応じてワ
ールド座標からビュー座標へ変換される。

【０１８７】平行投影のみを考えるので、これらの変換
はアフィン変換であり、透視分割(perspective divisio
n)を必要としない。第一サーフェルについて、カメラが
決定するクリッピング境界に対してビュー座標がクリッ
プされる。クリッピング境界には遠近平面、カメラの仕
様によって決まるビューポートの大きさが含まれる。サ
ーフェルがそれらのクリッピング境界の内部にある場
合、デプス・バッファによってサーフェルがチェックさ
れる。

【０１８８】光源による表面の照明のシミュレーション
を行うために、陰影づけ計算がサーフェルについて行わ
れる。光源の照明をモデル化する１つの方法は各サーフ
ェルについて局所的照明モデルを適用する方法である。
本発明で使用する有名なフォーン（Phong）陰影づけを
用いて局所的照明モデルの最良の結果を得ることができ
る。フォーン（Phong）陰影づけではこの計算でオブジ
ェクトの材料特性が利用され、オブジェクトに対する高
品質の陰影づけが行われる。

【０１８９】５.１ オブジェクトオーダー投影 サーフェルがどのピクセルに対して投影するかを決定す
るために、本発明では０番目のオーダー、すなわち最近
傍補間を実行する。ピクセル(x,y)の中心が(x+０.５,y+
０.５)に定位していると考えると、この場合、最近傍補
間は、サーフェルのx,yビュー座標の整数部分のみを考
慮することによってピクセル位置が得られることを意味
する。

【０１９０】サーフェルのオフセットをスクリーン空間
オフセットへ変換することによって連続する各サーフェ
ルのビュー座標が得られる。考慮中のサーフェルのビュ
ー座標はその時前のサーフェルの座標と関連づけられ
る。上述したように、これらのオフセットの多くは同じ
になるため、すでに変換したオフセットをルックアップ
・テーブルに記憶しておき、必要とするときに検索する
ことができる。インデックスを計算してこのルックアッ
プ・テーブルに入れておくことで、ビューイング・マト
リックスを直接用いるビュー座標計算と比べて少ない計
算量しか必要としない。直接平行投影によって同次座標
をビュー座標へ変換するには、合計１８回の演算(乗算
と加算)が必要となる。

【０１９１】オフセットを用いてサーフェルのビュー座
標を決定するには、ビューイング・マトリックスを使用
する第一サーフェルの変換が必要となる。正射影を行う
ために、視野変換されたオフセットを加算することによ
って各々次のサーフェルのビュー座標を得ることができ
る。８連結性を有するサーフェルについて、可能なオフ
セットの組み合わせは{±１,０,０}、{０,±１,０]、
{０,０,±１}である。

【０１９２】視野変換されたオフセットを予め計算し、
下記のような独自の索引付けを行ったルックアップ・テ
ーブルに記憶することができる。

【０１９３】

【数１８】

【０１９４】ここでＯはオフセットを意味する。このル
ックアップでは２回の乗算と３回の加算しか必要としな
い。視野変換したオフセットを加算してビュー座標を得
るために別に３回の加算を必要とするため、１サーフェ
ルにつき合計８回の演算が必要である。

【０１９５】５.２ ギザギザのエッジ、テラスおよびホ
ール サーフェル表現から生成される画像は、ギザギザのエッ
ジと図２８に図示するようなテラス効果(terracing eff
ect)２４００のような折返しアーティファクトを受け
る。これには２つの理由がある。第一の理由は、サーフ
ェルが、ピクセルの大きさをもつ１セル中に定位された
点サンプルと考えられているためである。ギザギザのエ
ッジなしに形状を再構成できるほど投影のサンプリング
・レートが高くないのである。

【０１９６】第二の理由は、たった１つのサーフェルし
かピクセルに対して投影を行わないことである。但し、
オブジェクトのある方向に対して、さらに多くのサーフ
ェルがピクセルに対して投影を行うけれども、結局はた
った１つのサーフェルしかピクセルのサーフェル値とし
ては役に立たないのであるが。その他のサーフェルはデ
プス・バッファによって除去される。ギザギザのエッジ
はデプス・バッファの使用に関する公知の問題である。
“ジャギー”とテラスは、オブジェクトの色の中の高い
空間周波数をもつ領域に出現する場合もある。エイリア
シングをもたらすアーティファクトは以下さらに詳しく
説明するスプラッティング技術によって低減することが
できる。

【０１９７】図２９と図３０に図示のように、最近傍の
隣接補間投影を用いる変形サーフェルのレンダリングに
関するもう１つの問題は、ホールである。ホールが出現
するのは、視野方向に最も平行な軸の周りをオブジェク
トが回転するとき、あるいは、オブジェクトが変形を受
けるときである。“ホール”問題に対しては以下の解決
策が講じられる。

【０１９８】図２９で、オープン・サーフェルをもつ破
線で示す格子が最初の位置にあり、固体サーフェルをも
つ実線で示す格子が再配向後の位置にある。配向後、中
央格子位置(ピクセル)にはもはや対応するサーフェルは
存在しない。この結果レンダーされた画像にホールが生
じることになる。図３０で、格子の一部が２つの方向に
変形されスクリーン(ピクセル)位置にホールが残ること
になる。

【０１９９】ホールは、隣接サーフェルを用いて“充た
さ”なければならないので、本発明のサーフェルマッピ
ングへの１対１像面にとって重大な欠点となる。これに
よって、１サーフェル当たりさらに多くの演算が必要と
なる場合もあるので、処理時間が増加することになる。
以下の説明でこの“ホール”問題に対する解決策を提供
する。

【０２００】５.３ サーフェルの剪断変形(shear-warp)
レンダリング １つの解決策は、剪断変形(shear-warp)要素化を用いて
サーフェルオブジェクトをレンダーする方法である。剪
断変形(shear-warp)要素化は、可視化変換が２つの別の
段階(剪断の後に変形が続く)に分けることができるとい
う観察に基づくものである。

【０２０１】

【数１９】

【０２０２】ここで、Pは順列・マトリックスと呼ば
れ、Sは剪断マトリックスであり、M_warpは変形マトリッ
クスである。剪断されたオブジェクト空間では、ベース
平面への投影はいわゆるベース平面に直交する。

【０２０３】図３１に図示のように、一般にこの要素化
には３つのステップが含まれる。まず、任意のボリュー
ム２５００に対して、視野方向２５０１に対して最も平
行な長軸(x₀)が決定され、次いで長軸に垂直なベース平
面２５０２すなわち中間画像が定義される。この軸に対
してベース平面の視野方向が割当てられる。Pを用いる
順列によってこの空間に座標の定義が行われる。この空
間は並べ替え空間と呼ばれる。ベース平面は、バウンデ
ィング・ボックスの面の中の１つと一致し、したがって
オブジェクトの一部分と一致する。

【０２０４】ベース平面とボクセルのすべてのスライス
に対して垂直な視野方向向を定義するには、図３２〜３
３に図示のようにオブジェクトを剪断することが必要と
なる。図３２〜３３で、線２６０１は視野方向であり、
平行ライン２６０２はスライスである。剪断は−V_x/V_z
に従って計算される。三次元でこの剪断はy方向にも行
われる。オブジェクト座標はSを用いて剪断された座標
空間へ変換される。ボリュームの剪断にはボクセルの再
サンプリングが必要となる。

【０２０５】第二に、オブジェクトはベース平面２５０
２上へ投影され、その結果中間画像が生じる。剪断変形
(shear-warp)変換を最初に展開したオブジェクトに対し
て、レンダリング速度を改善しながら剪断されたボリュ
ームのいくつかの特性を利用することができる。そのよ
うな特性の１つとして、スライスがベース平面上でピク
セルの連続に対して平行であるということがある。

【０２０６】第三に、図３４に図示のように、中間画像
は変形マトリックスに従って最終画像まで変形する。図
３４で、矢印２７０１は剪断、矢印２７０２は投影、矢
印２７０３は変形、楕円形２７００はオブジェクト(最
初は球面)、線２７０４はベース平面、そして線２７０
５は像面である。

【０２０７】本発明では、次のようにサーフェルオブジ
ェクトに対して剪断変形(shear-warp)要素化が適用され
る。剪断ステップによってオブジェクトの形状が変化を
受ける。しかし、ベース平面画像にはホールは存在しな
くなる。これは図３２及び３３を用いて説明することが
できる。二次元の視野方向の勾配は、V_xとV_zが等しいと
き、１.０というその最大値を示す。言い換えれば、オ
ブジェクトに対して垂直な方向に対するビューイング方
向の角度はは最大４５°である。なぜなら、この角が大
きくなるにつれて、様々な長軸がオブジェクトに対する
垂直軸として選ばれるからである。

【０２０８】オブジェクトが勾配に従って剪断されるの
で、ある方向への剪断はやはり最大１.０であり、した
がってすべてのピクセルは図３５〜３６に図示のように
サーフェルから貢献値(contribution)を受けることにな
る。図３５〜３６で、ライン２８０１はベース平面、矢
印２８０２は視野方向であり、格子２８１０はオブジェ
クト空間中に存在し、格子２８０２は剪断された空間中
のピクセル格子である。剪断変形(shear-warp)の様々な
段階を実行することにより最終結果として可視化変換を
生じることになる。

【０２０９】ホールを含まないベース平面画像をテクス
チャマップ（texture map）になるように定義すること
によって、最終画像中にホールが生じないようにするこ
とができる。次いで平面をテクスチャマッピングする際
にこのテクスチャマップを使用し、この平面が変形され
て最終画像となる。この変形はそのオブジェクト空間で
定義されたある平面と考えることができる。このオブジ
ェクト空間は変形マトリックスに従って変換される。こ
の変換されテクスチャマップされた平面は次いでスクリ
ーンへレンダーされる。

【０２１０】５.４ スケーリング 像面上のサーフェルオブジェクトの範囲の内部にあるす
べてのピクセルが、最近傍隣接値フィルタリングを保持
しながら、ピクセルと関連する少なくとも１つのサーフ
ェルを持つことを保証するために、オブジェクトをスケ
ールすることもできる。このスケーリングは、３つの方
向すべてにピクセル・サイズの間隔を維持するために均
一にしなければならない。決定すべきことは、そのオブ
ジェクトを最少にスケールする倍率である。

【０２１１】あるオブジェクト中のホールのパターンは
回転角に依存する。４５°と９０°との間の回転と共に
出現するこれらのパターンは、４５°回転の線に関して
鏡像反射する点を除いて０°と４５°との間の回転と共
に出現するパターンと同じである。これは全３６０°回
転についても事実であり、その場合、各４５°の回転間
隔について、間隔０°〜４５°に対するパターンと全く
同じか、鏡像反射されたパターンと全く同じかのいずれ
かでホールのパターンが再び出現する。

【０２１２】さて、セルにマップされたサーフェルを含
むセルを持つピクセルを考えることによって倍率を決定
することができる。セルの二次元投影は、セルが回転し
ないとき、ピクセルのサイズに正確に一致する。しか
し、セルの二次元投影がピクセルの中心の回りを回転す
る場合、セルのコーナーはピクセル境界の外部に出るこ
とになる(図３７〜３９参照)。

【０２１３】図３７でサーフェルはピクセルへマップさ
れ、図３８でサーフェルは４５°だけ回転し、図３９で
サーフェルは１/２×２^1/2だけスケールされる。

【０２１４】タイルピクセル境界へのセルの二次元投影
のコーナーの最大距離は４５°の回転と共に生じること
になる。ピクセルが単位正方形であると仮定して、ピク
セルの中心からコーナーまでの距離は、その場合１/２
×２^1/2である。この投影のコーナーがピクセル境界上
に存在することを保証するためには、倍率も１/２×２^1
/2でなければならない。この係数によってスケールする
とき、ピクセルの中心からセルの投影のコーナーまでの
距離は１/２である。これによって、各ピクセルについ
てあるオブジェクトの範囲で１ピクセルにつき少なくと
も１つのサーフェルが値に貢献することが保証される。

【０２１５】明らかに、スケーリングの結果スクリーン
上に小さなオブジェクトが生じるので、オブジェクトの
サイズを保持するためには、それより大きなオブジェク
トを生成することが望ましい。例えば、１００サーフェ
ルの半径の球面はスケーリングを行わずに１００ピクセ
ルの半径を有する。この球面をスケールする場合、１０
０ピクセルの半径をもつレンダーされた球面を得るため
に、球面の半径は１００×２^1/2でなければならなくな
る。

【０２１６】さらに高い分解能のオブジェクトを生成
し、次いでオブジェクトのさらに小さい分解能をレンダ
リングする原理はスーパーサンプリングを行うことに等
しい。ここで、スケーリングという語は、スーパーサン
プリングがサーフェルオブジェクトに対して適用される
ことを示すために使用されている。

【０２１７】５.５ スプラッティング エイリアシング問題とホール問題とを解決する第三の方
策は図４０及び４１に図示のようなスプラッティングを
利用する方法である。図４０で、ピクセル格子３０００
はサーフェル３００１に対してマップする。格子ロケー
ション３００２には“ホール”がある。図４１で、サー
フェルは比例して拡大されそのホールを充たす。

【０２１８】スプラッティングによってサーフェルの貢
献値(contribution)は復元“カーネル”に従って複数の
ピクセルへ拡大すなわち“広げ”られる。この処理は、
サンプリングされたデータから信号を復元するために復
元関数を利用するデジタル画像処理から得た方法に基づ
くものである。

【０２１９】１つのサンプルの周りに、単位球面(単位
領域球面)が定義される。この球面は三次元の復元カー
ネルを表現する。スクリーンへサンプルを投影するとき
球面の範囲は円となる。この円の内部のすべてのピクセ
ル(x,y)に対して、z軸、すなわちビューイング軸に沿っ
て復元カーネルを積分することによってサンプルの貢献
値(contribution)が計算される。オフセットを除いて、
これらの範囲はサンプルについてすべて類似している。
したがって積分値をいわゆる汎用フットプリントテーブ
ルと交換することができる。

【０２２０】復元フィルタの積分は式 eｘｐ(−ｘ²＋ｙ
²/２σ²)のガウス関数に近似する。この関数は回転対称
的でありかつ線形分離的である。このことはこの関数が
各方向に個々に積分可能であり、その結果を掛けあわせ
て総積分値を得ることができることを意味する。これら
の特性は、ガウス関数を用いて汎用フットプリントテー
ブルを構築するために必要とされる特性である。

【０２２１】汎用テーブルを構築するために、三次元カ
ーネル、すなわち単位領域球面が平面上へ投影される。
この投影は円(単位領域円)となる。次いでこの単位領域
円は、ガウスフィルタを用いて、１００×１００などの
多くのエントリを持つテーブルによってサンプリングさ
れるが、その場合単位領域円の内部にいっぱいにならな
いテーブルエントリはゼロ値を持つことにする。

【０２２２】ボリュームは、３つの方向すべてに必ずし
も均等割り付けされるわけではないので、単位領域球面
を特定のビューのための楕円面へ変換することもでき
る。したがって特定のビューのためのフィルタの投影は
楕円となることもある。楕円用の汎用フットプリントテ
ーブルを使用する代わりに、いわゆる視野変換されたフ
ットプリントテーブルが汎用フットプリントテーブルか
ら一度組立てられる。

【０２２３】視野変換されテーブルを利用するために、
レンデラーは２回の計算を行う必要がある。まず、視野
変換されたフットプリントテーブルのためにピクセル中
の範囲を計算しなければならない。第二に、視野変換さ
れたフットプリントテーブルから汎用フットプリントテ
ーブルへのマッピングを計算しなければならない。

【０２２４】カーネルの幅すなわち広がりを利用してピ
クセルの範囲が計算される。視野変換されたテーブルか
ら汎用テーブルへのマッピングは、円から円へのマッピ
ングであるか、あるいは領域球面が特定のビュー用に偏
楕円面へ変換される場合には、マッピングは楕円から円
へのマッピングのいずれかである。

【０２２５】レンダリング中、視野変換されたフットプ
リントテーブルはサンプルの画像位置の中心に位置す
る。視野変換されたフットプリントを利用するためには
１つの追加パラメータを必要とする。それはテーブルの
大きさである。この大きさはテーブルの範囲とは異な
る。テーブルの大きさは視野変換されたテーブル用のエ
ントリ数を決定するものである。視野変換されたテーブ
ルの大きさは、テーブルがカバーするピクセル数より大
きくするほうがよい。さもないと、エイリアシングをも
たらすアーティファクトが画像中に生じることになる。
広い大きさのみならず幅広い範囲をもつ視野変換された
テーブルは、結果的にオブジェクトの不鮮明な画像を生
み出すことになる。視野変換されたフットプリントテー
ブルの範囲内にあるピクセルの各ピクセル中心を求める
ために、視野変換されたフットプリントテーブルがサン
プリングされる。そして、特定のテーブルエントリでの
重みを用いてピクセルへの貢献値(contribution)が計算
される。

【０２２６】一般的スプラッティング処理はサーフェル
に対して次のように適用される。すなわち、ボリューム
中では、図４０に図示のように、格子スペーシングは必
ずしも３つの方向すべてに等しいというわけではなく、
取り込み(acquisition)のタイプに依存する。また、出
力サンプル(ピクセル)の分解能は入力サンプル(ボクセ
ル)の分解能より一般に高い。この理由のために格子倍
率とピクセル／ボクセル比とが式に導入され視野変換テ
ーブルの範囲が計算される。

【０２２７】しかし、サーフェルについては、これら２
つの係数は両方とも等しい。したがって、視野変換され
たフットプリントテーブルの大きさは比較的に小さくす
ることができる。１.５の放射状範囲をもつ復元カーネ
ルによって３ピクセルからなるスクリーン範囲が結果と
して生じる。５×５〜１０×１０の大きさでサーフェル
に適用する分割には十分である。

【０２２８】レンデラーはサーフェルをスクリーンへ投
影することによって開始され、視野変換されたフットプ
リントテーブルがスクリーン上のx,y位置の中心に配置
される。テーブルの範囲内に入る各ピクセル中心につい
て、そのピクセルのテーブルエントリが決定され、その
エントリにおける重みがピクセルの値に適用される。

【０２２９】剪断変形(shear-warp)、スケーリングおよ
びスプラッティングの比較 剪断変形(shear-warp)は、ベース平面と軸配列した三次
元格子を用いてベース平面へのオブジェクトの投影を常
に行えるという利点がある。ホールが最終画像に現れな
いようにするために、歪められたベース平面画像はその
ピクセル値を補間する必要がある。剪断変形(shear-war
p)の不利な点は、場面中の各オブジェクトを別の画像へ
レンダしなければならず、その結果生じる画像を混合し
て最終場面を構成しなければならないという点である。
これは複雑であり経費の導入を必要とする。

【０２３０】レンダリングに先立ちオブジェクトをスケ
ーリングすることによって、複数のサーフェルが単一ピ
クセルへ投影を行うことができる。オブジェクトをレン
ダーするために最初のレンダリング処理を適用し、たっ
た１つのサーフェルが最終的にその値によってピクセル
に貢献し(contribute)、そのサーフェルが最小デプス値
を持つサーフェルになるという特性がある。本発明で
は、係数１/２×２^1/2でオブジェクトをスケーリングす
る結果、１ピクセル当たり少なくとも１つのサーフェル
が生じると信じられる。スケーリングの結果小さなオブ
ジェクトが像面上に生じるので、スケーリングには最初
大きめのオブジェクトを生成する必要がある。

【０２３１】ホール問題に対する本発明の最後の解決策
はピクセルの近傍に対するサーフェルの貢献値(contrib
ution)をスプラットする方法である。サーフェルの値は
各サーフェルと関連するフィルタに応じて重み付けが行
われ、この重み付け値はピクセルへ割当てられる。ピク
セルに対するすべての貢献値(contribution)の累積結果
として画像が生じる。このように、ホールは、周りのサ
ーフェルの広がりが十分に大きければ、周りのサーフェ
ルのピクセルに対する貢献値(contribution)によって充
たされることになる。スプリッティング(splitting)は
本質的にオブジェクトの色をぼやけさせるものなので、
これによってオブジェクトの表面上のギザギザのエッジ
とテラスに対してアンチ・エイリアシング（anti-alias
es）が行われる。サーフェルの広がりがあまりに大きく
なりすぎるとぼやけの量も多くなる。

【０２３２】このスプリッティング方法を利用してサー
フェル表現に高速のレンダリング方法と、絶えず再サン
プリングを行わずにオブジェクトを変形する能力とを与
えることができる。最初オブジェクトのサーフェルは８
連結され、したがって、長くて最大で１ピクセルの距離
だけお互いから離れているので、分割の際に使われるテ
ーブルを比較的小さく保つことができる。６×６と８×
８ピクセルの範囲を持つテーブルでホールを充たすのに
十分である。

【０２３３】オブジェクトが変形しその変形に起因して
大きなホールがその表面に生じるとき、オブジェクトを
即座に再サンプリングする必要はない。第一に、カーネ
ルを分割する範囲を拡大してもっと大きなホールを充た
すことができる。範囲があまりに大きすぎる場合にはレ
ンダリングが著しく遅くなり、したがって、オブジェク
トを時折再サンプリングしたり、表面の大きなホールの
位置にサーフェルを局所的に生成することが必要となる
場合もある。

【０２３４】本発明は特別の用語と実施例を用いて説明
されている。本発明の精神と範囲内で種々の他の適合と
改造を行うことができることは理解できよう。したがっ
て、本発明の真の精神と範囲に入るようなすべての変更
例と改造例を包括することが添付の請求項の目的であ
る。

【０２３５】

【発明の効果】この発明においては、上述してきたよう
に、オブジェクトの表面は像面（image-plane）の分解
能に関連する格子分解能を有する複数のセルに分割さ
れ、各セルは、像面分解能に関係する８つの格子点によ
って囲まれ、単一ゼロ次元面エレメントは、オブジェク
トの表面に定位された各セルのメモリに記憶され、隣接
セルの面エレメントはリンクによって連結されて、セル
に含まれるオブジェクトの部分の属性は各面エレメント
と各リンクへ割当てられるようにしたので、モデル化と
レンダリングを単純化することができるとともに、従来
技術のように限られたグラフィックオブジェクトの表現
だけでなく、複雑な形状を有するものや動的変形を行う
もの、立体データ集合で与えられるもの、及び、流体や
雲状物体等の種々のグラフィックオブジェクトの表現に
適用することができ、汎用性があり、良好なグラフィッ
クオブジェクトの生成が行え、利便性が向上するという
効果が得られる。

【図面の簡単な説明】

【図１】 暗黙表現、ポリゴン表現、ボクセル表現、粒
子表現から、合成、変換、マッピングおよび抽出によっ
て生成できる面エレメントをそれぞれ示した説明図であ
る。

【図２】 隣接セルとの境界を定めるためにオブジェク
トの中へ投影された像面分解能を有する格子を示した斜
視図である。

【図３】 隣接セルとの境界を定めるためにオブジェク
トの中へ投影された像面分解能を有する格子を示した斜
視図である。

【図４】 ６隣接８連結サーフェルのメッシュを示した
説明図である。

【図５】 サーフェルのデータ構造のブロック図であ
る。

【図６】 サーフェル属性のブロック図である。

【図７】 サーフェルリストのブロック図である。

【図８】 ポリゴンをサーフェルへスキャン変換するた
めのポリゴンを示した説明図である。

【図９】 内側と外側のサーフェルを備えたポリゴンを
示した説明図である。

【図１０】 距離マップを用いる面エレメント化処理を
示す流れ図である。

【図１１】 ポリゴンからなるトリ・ストリップを示し
た説明図である。

【図１２】 投影された距離を示すグラフである。

【図１３】 内側の投影された点を示すグラフである。

【図１４】 外側の投影された点を示すグラフである。

【図１５】 平坦面によってセル分割されたサーフェル
のグラフである。

【図１６】 面エレメント化する任意のポリゴンのグラ
フである。

【図１７】 剛体の状態を示すブロック図である。

【図１８】 サーフェルオブジェクトの剛体のモデル化
を行う処理を示す流れ図である。

【図１９】 変形可能なサーフェルオブジェクトの動的
状態を示す図である。

【図２０】 質量バネシステムとしてモデル化されるサ
ーフェルオブジェクトのメッシュを示した図である。

【図２１】 サーフェルオブジェクトにかかる力を蓄積
する手順を示した図である。

【図２２】 サーフェルオブジェクトを変形する処理を
示す流れ図である。

【図２３】 動的状態ベクトルを生成する手順を示した
図である。

【図２４】 変形前の面法線を図示した図である。

【図２５】 変形中の面法線を図示した図である。

【図２６】 変形中の面法線を図示した図である。

【図２７】 サーフェルレンダリングパイプラインの流
れ図である。

【図２８】 レンダリングアーティファクトを示した図
である。

【図２９】 レンダリングアーティファクトを示した図
である。

【図３０】 レンダリングアーティファクトを示した図
である。

【図３１】 剪断変形(shear-warp)要素化を示すグラフ
である。

【図３２】 剪断前のボクセルスライスを示すグラフで
ある。

【図３３】 剪断後のボクセルスライスを示すグラフで
ある。

【図３４】 像面への変形を示すグラフである。

【図３５】 剪断変形された(shear-warped)ピクセル格
子を示すグラフである。

【図３６】 剪断変形された(shear-warped)ピクセル格
子を示すグラフである。

【図３７】 スケールされたサーフェルを示すグラフで
ある。

【図３８】 スケールされたサーフェルを示すグラフで
ある。

【図３９】 スケールされたサーフェルを示すグラフで
ある。

【図４０】 スプラットされたサーフェルを示した図で
ある。

【図４１】 スプラットされたサーフェルを示した図で
ある。

【図４２】 図１３及び１４に示された投影された点が
内部にあるか外部にあるかを検出するためのステップを
示した図である。

【符号の説明】

１００ サーフェル、１０１ 陰関数、１０２ ポリゴ
ン、１０３ ボクセル、１０４ 粒子、２００ セル、
２０２ ピクセル、２０３ 像面、３００ リンク、４
０１ サーフェル属性、４０３ リンク属性、６００
シーケンシャル・リスト、１０００ トリ・ストリッ
プ、１３００ セル、１３１０ オブジェクト面、１４
００ ポリゴン、１４１０ ベース・エッジ、１４１
１，１４１２ガイダンス・エッジ、１６０１ サーフェ
ルオブジェクト、１６００ 剛性の状態、１６０２，１
６０３ 状態ベクトル、１６１０ 積分器、１７０２，
２００１ サーフェルオブジェクト、２００２ サーフ
ェル、２００３ リンク、２０１０，２０３０ 状態ベ
クトル、２７０１ 剪断、２７０２ 投影、２７０３変
形、２７０４ ベース平面、２７０５ 像面、２８０１
ベース平面、２８０２ 視野方向、２８１０ 格子
（グリッド）、３０００ ピクセル格子、３００１ サ
ーフェル、３００２ 格子ロケーション。

フロントページの続き (71)出願人 597067574 201 ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩ ＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ 02139， Ｕ．Ｓ．Ａ. (72)発明者 ハンスピーター・フィスター アメリカ合衆国、マサチューセッツ州、サ マービル、パーク・ストリート 60 (72)発明者 ジェロン・ヴァン・バール オランダ国、1788 ヴェーエル・デン・ヘ ルダー、ウィールバルグ、2906 (72)発明者 コリン・イー・オーステルバーン オランダ国、2461 エスカー・ランゲラー ル、ウェー・オンツィフトストラート 41

Claims (25)

【特許請求の範囲】
1. 【請求項１】 メモリ中のグラフィックオブジェクトの
   表現を生成するためのグラフィックオブジェクトの生成
   方法であって、 上記オブジェクトの面を、像面分解能に関連する格子分
   解能を有する複数のセルに分割するステップと、 上記オブジェクトの面上に定位された各上記セルについ
   て上記メモリに単一ゼロ次元面エレメントを記憶するス
   テップと、 リンクによって隣接セル中の上記面エレメントを連結す
   るステップと、 上記セルに含まれる上記オブジェクトの部分の属性を各
   上記面エレメントと各上記リンクへ割り当てるステップ
   と、 を備えたことを特徴とするグラフィックオブジェクトの
   生成方法。
2. 【請求項２】 各上記セルが上記像面分解能に関連する
   ８つの格子点によって囲まれていることを特徴とする請
   求項１記載のグラフィックオブジェクトの生成方法。
3. 【請求項３】 各上記面エレメントに割当てられている
   上記オブジェクトの属性が、上記オブジェクトの面上の
   上記面エレメントの位置と、上記対応するセル中の上記
   オブジェクトの上記部分の色と不透明度と、上記対応す
   るセル中の上記面に対する法線と、上記隣接セル中のサ
   ーフェルに対するオフセットとを含むことを特徴とする
   請求項１記載のグラフィックオブジェクトの生成方法。
4. 【請求項４】 各上記面エレメントに対して割当てられ
   る上記オブジェクトの属性が、上記対応するセル中の上
   記オブジェクトの上記部分の速度と質量とを含むことを
   特徴とする請求項１記載のグラフィックオブジェクトの
   生成方法。
5. 【請求項５】 各上記リンクに対して割当てられる上記
   オブジェクトの属性が上記リンクによって連結された２
   つの隣接する面エレメント間の距離の残りの長さを含む
   ことを特徴とする請求項１記載のグラフィックオブジェ
   クトの生成方法。
6. 【請求項６】 各上記セルに対して割当てられる上記オ
   ブジェクトの属性が上記リンクと関連する弾性係数と減
   衰定数を含むことを特徴とする請求項１記載のグラフィ
   ックオブジェクトの生成方法。
7. 【請求項７】 ６つの隣接する面エレメントが８連結さ
   れていることを特徴とする請求項１記載のグラフィック
   オブジェクトの生成方法。
8. 【請求項８】 各上記面エレメントが解析関数から生成
   されることを特徴とする請求項１記載のグラフィックオ
   ブジェクトの生成方法。
9. 【請求項９】 各上記面エレメントが上記オブジェクト
   の上記面を表現するポリゴンから生成されることを特徴
   とする請求項１記載のグラフィックオブジェクトの生成
   方法。
10. 【請求項１０】 上記生成に、上記ポリゴンをラスター
    化するための三次元デジタル微分アナライザを用いるこ
    とを特徴とする請求項９記載のグラフィックオブジェク
    トの生成方法。
11. 【請求項１１】 上記生成に、上記オブジェクトの上記
    面の距離マップを用いることを特徴とする請求項９記載
    のグラフィックオブジェクトの生成方法。
12. 【請求項１２】 上記オブジェクトを表現するボリュー
    ムデータ集合の面においてボクセルから各面エレメント
    が生成されることを特徴とする請求項１記載のグラフィ
    ックオブジェクトの生成方法。
13. 【請求項１３】 上記オブジェクトを表現する粒子雲か
    ら各上記面エレメントが生成されることを特徴とする請
    求項１記載のグラフィックオブジェクトの生成方法。
14. 【請求項１４】 上記面エレメントが各ポリゴンのベー
    スエッジに平行なラインの三次元スキャン変換であっ
    て、上記ラインが上記ポリゴンのガイダンス・エッジに
    よって囲まれていることを特徴とする請求項９記載のグ
    ラフィックオブジェクトの生成方法。
15. 【請求項１５】 上記ポリゴンが三角形であることを特
    徴とする請求項９記載のグラフィックオブジェクトの生
    成方法。
16. 【請求項１６】 ６つの隣接する面エレメントの間に８
    連結性を設けるために各エレメントの内部に追加の面エ
    レメントを生成することをさらに含むことを特徴とする
    請求項９記載のグラフィックオブジェクトの生成方法。
17. 【請求項１７】 上記距離マップが各上記面エレメント
    について上記オブジェクトの上記面までの最短距離を記
    憶することを特徴とする請求項１１記載のグラフィック
    オブジェクトの生成方法。
18. 【請求項１８】 上記距離マップ中の勾配が面法線の方
    向を定義することを特徴とする請求項１１記載のグラフ
    ィックオブジェクトの生成方法。
19. 【請求項１９】 請求項１１記載のグラフィックオブジ
    ェクトの生成方法において、 上記オブジェクトを表す面ポリゴンを推定するステップ
    であって、上記面ポリゴンが上記メモリ中で三角形から
    なるトリ・ストリップとして記憶されているステップ
    と、 上記推定された面ポリゴンのためにバウンディング・ボ
    ックスを決定するステップと、 上記トリ・ストリップの周りに、上記像面分解能を有す
    る格子であって、上記バウンディング・ボックスより大
    きい格子を画定するステップと、 各整数格子点位置について各三角形までの最短距離を決
    定するステップと、 １/２×２^1/2以下の距離を有する各格子位置について面
    エレメントをシーケンシャル・リストに加えるステップ
    と、 をさらに有することを特徴とするグラフィックオブジェ
    クトの生成方法。
20. 【請求項２０】 属性を与えられた上記面エレメントと
    属性を与えられた上記リンクを上記メモリのシーケンシ
    ャル・リスト中に配列することを含むことを特徴とする
    請求項１記載のグラフィックオブジェクトの生成方法。
21. 【請求項２１】 上記グラフィックオブジェクトを表す
    複数の表現を生成することを含み、上記複数の表現の各
    々が様々なレベルの細部を有することを特徴とする請求
    項１記載のグラフィックオブジェクトの生成方法。
22. 【請求項２２】 さらに高いレベルの細部表現からさら
    に低いレベルの細部表現を生成するために、隣接サーフ
    ェルを組み合わせて低い分解能のサーフェルに変えるス
    テップをさらに有することを特徴とする請求項２１記載
    のグラフィックオブジェクトの生成方法。
23. 【請求項２３】 ４つの隣接サーフェルの属性値が平均
    化されることを特徴とする請求項２２記載のグラフィッ
    クオブジェクトの生成方法。
24. 【請求項２４】 メモリ中のグラフィックオブジェクト
    の表現を生成するグラフィックオブジェクトの生成シス
    テムであって、 上記オブジェクトの面を、像面分解能に関連する格子分
    解能を有する複数のセルへ分割する手段と、 上記オブジェクトの面上に定位された各上記セルについ
    て単一ゼロ次元面エレメントを記憶するメモリと、 隣接セル中の上記面エレメントを連結するためのリンク
    と、 上記セル中に含まれる上記オブジェクトの上記部分の属
    性を各上記面エレメントと各上記リンクに対して割当て
    るための手段と、 を備えたことを特徴とするグラフィックオブジェクトの
    生成システム。
25. 【請求項２５】 上記属性を与えられた面エレメントと
    上記属性を与えられたリンクとをシーケンシャル・リス
    トとして上記メモリ中に記憶することを特徴とする請求
    項２４記載のグラフィックオブジェクトの生成システ
    ム。