(57)【要約】本発明は、グラフィックス画面の離散グリッド上の、第１の頂点（A）と第２の頂点（B）と第３の頂点（C）と第４の頂点（D）とを備える平行四辺形（ABCD）をその頂点の座標の情報からトレースし、フィル・インする方法に関する。本発明による方法は、第１の頂点（A）と第２の頂点（B）との間の第１の線分（AB）上の点の座標を計算する工程(10)と、第１の頂点（A）と第３の頂点（C）との間の第２の線分（AC）上の点の座標を計算する工程(11)と、第２の頂点（B）と第４の頂点（D）との間の第３の線分（BD）上の点の座標を計算する工程(13)と、線分ABに対して平行であり、平行四辺形ABCD内に備えられる線分上の点の座標を計算する反復工程(20)とを備える。効果的には、線分上の点の座標の工程は、いわゆる中点アルゴリズム又はブレセンハムのアルゴリズムを用いる。
2006524384.tif 000002
【特許請求の範囲】
【請求項１】
第１の頂点と第２の頂点と第３の頂点と第４の頂点とを備える平行四辺形をフィル・インする方法であって：
前記第１の頂点と前記第２の頂点との間の第１の線分上の点の座標を計算する工程と、
前記第１の頂点と前記第３の頂点との間の第２の線分上の点の座標を計算する工程と、
前記第２の頂点と前記第４の頂点との間の第３の線分上の点の座標を計算する工程と、
前記第１の線分に対して平行であり、前記平行四辺形内に備えられる線分上の点の座標を計算する反復工程を備えることを特徴とする、平行四辺形をフィル・インする方法。
【請求項２】
請求項1記載の、平行四辺形をフィル・インする方法であって、前記第１の線分に対して平行である線分上の点の座標を計算する反復工程は、前記第２の線分に属する点と前記第３の線分に属する点との間に位置している線分の点の座標を計算するサブ工程も備え、前記第２の線分に属する点と前記第３の線分に属する点は、水平又は垂直の好適な方向において、前記第１の頂点からも前記第２の頂点からも同じ距離のところに位置していることを特徴とする、平行四辺形をフィル・インする方法。
【請求項３】
請求項1記載の、平行四辺形をフィル・インする方法であって、前記第１の線分に対して平行である線分の座標を計算する反復工程は、前記第１の線分を水平又は垂直の好適な方向に平行移動させる、前記平行四辺形に備えられる平行移動される線分を供給することを意図しているサブ工程と、前記平行移動される線分上の点が前記平行四辺形に備えられるか否かを検査することを意図している検査サブ工程とを備えることを特徴とする、平行四辺形をフィル・インする方法。
【請求項４】
請求項3記載の、平行四辺形をフィル・インする方法であって、前記第１の線分に対して平行である線分上の点の座標を計算する反復工程は更に、
前記好適な方向に対して平行である、前記第１の線分の延長部分上の、前記第３の頂点の射影の座標を計算するサブ工程と、
前記射影と前記第１の頂点によって形成される線分の点の座標を計算するサブ工程と、
該線分を前記好適な方向に平行移動させる、該線分に対して平行である線分を供給することを意図しているサブ工程と、
前記射影と前記第１の頂点によって形成される線分から平行移動される線分上の点が前記平行四辺形に備えられるか否かを検査することを意図している検査サブ工程とを備えることを特徴とする、平行四辺形をフィル・インする方法。
【請求項５】
請求項1記載の、平行四辺形をフィル・インする方法であって、線分上の点の座標を計算する工程は、中点アルゴリズムを用いることを特徴とする、平行四辺形をフィル・インする方法。
【請求項６】
グラフィックス画面の平行四辺形をトレースし、フィル・インする、前記平行四辺形に備えている点の座標を第１の頂点と第２の頂点と第３の頂点と第４の頂点との座標から供給することを意図しているシステムであって：
前記第１の頂点と前記第２の頂点との間の第１の線分上の点の座標を計算する手段と、
前記第１の頂点と前記第３の頂点との間の第２の線分上の点の座標を計算する手段と、
前記第２の頂点と前記第４の頂点との間の第３の線分上の点の座標を計算する手段と、
前記第１の線分に対して平行であり、前記平行四辺形内に備えられる線分上の点の座標を計算する反復手段を備えることを特徴とするシステム。
【請求項７】
コンピュータ・プログラム・プロダクトであって、回路にロードされると、請求項1記載の方法を該回路に実行させる命令群を備えることを特徴とするコンピュータ・プログラム・プロダクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、平行四辺形をフィル・インする方法に関する。本発明は、そのような方法を実施するシステムにも関する。最後に、本発明は、そのような方法を実施するコンピュータ・プログラムに関する。
【０００２】
本発明は、画像合成の分野、2次元又は3次元におけるビデオ・ゲームの分野、及びMPEG-4標準によるビデオ・オブジェクトの処理の分野における応用が見出されている。
【背景技術】
【０００３】
ビデオ・ゲームの分野において、更に一般的には画像の合成の分野において、通常、2次元空間ではピクセル（画素）として呼ばれ、3次元空間ではボクセルとして呼ばれる離散点グリッドを備える、やや複雑な形状を備えている対象オブジェクトをグラフィカル画面上に表示する課題が提起されている。この目的で、対象オブジェクトは、一般的に三角形である1次形態に分解され、これは、画面上にある離散グリッド上でその頂点の座標の情報から、トレースされ、フィル・インされ、その頂点にはテクスチャ値が割り当てられる。したがって、課題の１つとしては、離散グリッド上の点を、非整数の実座標を1次形状上に有する点に相当させるということがある。このことに対処する手法が開発されており、その大半は、いわゆる「中点」アルゴリズム又はブレセンハムのアルゴリズムの原理に基づいている。このアルゴリズムは当初、Jack  E.  Bresenham  による「Algorithm  for  Computer  Control  of  a  Digital  Plotter」と題する、IBM  Systems  Journal,  Volume  4(1),  page  25-30において西暦1965年に公表された文献によって開示されており、特に、斜線分をすばやくかつ効果的にトレースすることを可能にする。そのようなアルゴリズムは画像合成の分野において広く用いられている。この場合も又当業者に周知である他の手法が、三角形をフィル・インするか多角形をもフィル・インするよう、このアルゴリズムから後に導き出されている。
【０００４】
これらの手法は、水平走査又は垂直走査によって三角形をフィル・インするか多角形をもフィル・インすることを提案するという共通の特徴を有する。そのような走査によく適応した三角形の種類の１つとして、線分、すなわち水平方向又は垂直方向の線分を備える三角形がある。図1は、三角形IJKを表し、その線分JKは水平方向である。この場合、そのような三角形をフィル・インする方法は：
線分IJをブレセンハムのアルゴリズムによってトレースする工程を備える。この工程は、参照フレーム（Jx,Jy）における線分IJの点Jiの座標を計算することを意図している。この座標が分かっている場合、この点をトレースし、この点にテクスチャ値を割り当てることが可能である。
【０００５】
上記方法は更に、線分IKをブレセンハムのアルゴリズムによってトレースする工程を備える。この工程は、参照フレーム（Jx,Jy）における線分IKの点Kiの座標を計算することを意図している。
【０００６】
上記方法は更に、三角形を備える対象領域RI上を進むことを意図している、三角形IJKの水平走査の工程を備え、
更に、領域RI上の点が三角形IJKに属するか否かを線分IJ及びIKの点の座標によって検査する検査工程を備える。例えば、線分JiKi上に位置している点Pは、その横座標xpがxJi<xP<xKiであるような場合に三角形IJKに属する。
【０００７】
この方法の利点の１つとして、高速であり、かつ計算量が少ないということがある。これは、ブレセンハムのアルゴリズムは整数と加算とだけを用いて実施することが可能であるからである。したがって、この方法は、ハードウェア実施形態によく適しており、これは、ビデオ・ゲームの分野において特に効果的である。これは、この分野では、リアル・タイムで行うために、例えば、２つの既知点間の斜線分のトレースなどの正則計算を加速させるよう特に企図されたプロセッサによって実施される一層複雑な処理を対象オブジェクトが経るからである。
【０００８】
そのような方法は、特にMPEG-4標準（「動画像専門家グループ」）によって、ビデオ圧縮の分野においても効果的に用いられる。これは、この標準が、ビデオ・シーケンスにおける対象オブジェクトを、このシーケンスのバックグラウンドとは別個に考慮する特色を有するからである。そのようなオブジェクトは、形状及びテクスチャを備え、これらは別個に符号化される。形状は、一般的に矩形のバウンディング・ボックスによって符号化される。ボックス内のこの形状のフィル・インも、ブレセンハムのアルゴリズムを用いて行われる。
【０００９】
しかし、ビデオ・ゲーム・シーンにおける対象オブジェクトを、三角形のモザイクに分解することは常に可能であるが、ビデオ・シーンは多くの場合、多数の平行四辺形を有する。これは、2次元において非常に広範にわたっている矩形形状が、3次元における透視図では平行四辺形になるからである。
【００１０】
MPEG-4標準において用いるバウンディング・ボックスは、同じ種類の変換にかけられ、透視図において平行四辺形となる。
【００１１】
矩形を描写するには線分を備えている２つの三角形で十分であるが、平行四辺形の場合には少なくとも４つが必要である。したがって、平行四辺形は、４つの三角形と、これらの三角形の連結とを描写したものによって表現される。そのような表現は、グラフィカル画面上でこの平行四辺形をトレースし、フィル・インする場合に、計算量が大きく、メモリ空間の点で費用がかかり、用いるのにあまり実用的でない。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明の目的は、これらの４つの頂点の座標のみを用いて、より単純でかつすばやい方法で平行四辺形をトレースし、フィル・インする解決策を提案することにある。
【００１３】
この目的は、第１の頂点と第２の頂点と第３の頂点と第４の頂点とを備える平行四辺形をフィル・インする方法によって達成され、この方法は：
第1の頂点と第2の頂点との間の第1の線分の座標を計算する工程と、
第1の頂点と第3の頂点との間の第2の線分の座標を計算する工程と、
第2の頂点と第4の頂点との間の第3の線分の座標を計算する工程と、
第１の線分に対して平行であり、平行四辺形内に備えられる線分の座標を計算する反復工程とを備える。
【００１４】
本発明による方法によって、平行四辺形内に位置している点の座標をその４つの頂点の座標から計算し、よって、それをいくつかの三角形に分解する必要なくそれをトレースし、フィル・インすることが可能である。そのような方法は、平行四辺形の第1の線分をトレースする工程と、次に、お互いに平行であり、第1の線分の両側に位置している第２の線分及び第3の線分をトレースする工程と、最後に、第2の線分と第3の線分との間に備えられる、第1の線分に対する考えられる平行線全てをトレースする工程とを備える。
【００１５】
第1の実施例では、第1の線分に対して平行である線分の座標を計算する反復工程は、好適な水平方向又は垂直方向において、2点が第1の頂点と第2の頂点との各々から等距離であるところに位置するように第2の線分上の点と第3の線分上の点とを選択する工程と、２点間に位置している線分の点の座標を計算する工程とを備える。
【００１６】
効果的には、線分上の点の座標を計算する種々の工程は、中点アルゴリズムとも呼ばれる、ブレセンハムのアルゴリズムを用いる。この理由は、それによって、2点間の斜線分を単純にかつすばやくトレースすることが可能になるからである。
【００１７】
平行四辺形が備える点の座標を、その４つの頂点の情報だけから備えることによって、本発明による方法は、平行四辺形を三角形に分解しなくてよいようにし、メモリ空間を節減することを可能にする。これは、三角形全ての頂点と、平行四辺形内のこれらの三角形の連結の表現との代わりに、４つの頂点の座標だけをメモリに記憶すればよいからである。
【００１８】
第2の実施例では、第1の線分に対して平行である線分の座標を計算する反復工程は、第1の線分を好適な方向に一定の増分、平行四辺形内で平行移動させる工程を備える。この増分が分かっている場合、得られる、平行移動線分上の点の座標は、第1の線分のものから容易に推定される。この処理は、平行四辺形の表面全体を網羅するように繰り返される。
【００１９】
第2の実施例の主たる利点は、平行四辺形のフィル・インを網羅的に、すなわち穴が何らなしで、備えることにある。線分を平行移動させることは、誤差の積み重ねを何らもたらさない。しかし、平行移動される線分は、同一であるので、横に並べればお互いにぴったり合う。
【発明を実施するための最良の形態】
【００２０】
本発明は、添付図面に示す実施例の例を参照しながら更に説明することとする。しかし、本発明はこの例に制限されない。
【００２１】
本発明による方法は、グラフィックス画面上にある離散グリッド上の平行四辺形のフィル・インに関する。この方法は、2次元表現にも3次元表現にも同様にあてはまる。以降、2次元の場合のみを記載する。しかし、3次元の場合への拡張は、当業者にとって特段の問題を何ら、もたらさないものである。
【実施例】
【００２２】
図1bは、本発明による平行四辺形ABCDを、その第1の頂点A、その第2の頂点B、その第3の頂点C及びその第4の頂点Dの情報だけからフィル・インする例を表す。フィル・インは、平行四辺形ABCDを第1の線分ABに対して平行に連続して走査することによって行われる。
【００２３】
本発明による方法は、図2aに機能的に表す。この方法は、第1の線分ABの点の座標を計算する工程10を備える。以降、記述を単純にする理由で、参照フレーム（Ax,Ay）における、第１の頂点Aをその起点とする線分ABを形成する点の全ての座標{(ｘA,yA),(x1,y1),(x2,y2),…,(xB,yB)}に項ABを示すこととする。したがって、第１の線分AB上の点によって構成される集合は：AB={(0,0),(x1,y1),(x2,y2),…,(xB,yB)}として表す。
【００２４】
本発明による方法は、第２の線分AC上の点の座標を計算する工程11及び第3の線分BD上の点の座標を計算する工程12も備える。
【００２５】
効果的には、この座標計算は、ブレセンハムのアルゴリズム又は中点アルゴリズムとして知られているアルゴリズムによって行われる。そのようなアルゴリズムによって、特に、グラフィクス画面の離散グリッド上の斜線分をトレースすることが可能になる。「トレースする」の動詞は、本明細書及び特許請求の範囲では、斜線分の離散近似を形成する、離散グリッド上の点を判定することを意味する。
【００２６】
ブレセンハムのアルゴリズムの原理は、図3a及び図3bに表す。図3aでは、参照フレーム（Ox,Oy）によって参照され、斜線分2によって切断される離散グリッド1を表す。アルゴリズムは以下の通り、図3bによって示すように進む。
【００２７】
好適な方向を選択する。この選択は、線分2の傾きの測定値αによって変わってくる。この傾きが45度よりも小さい場合、軸Oxが選択され、さもなければ軸Oyが選択される。図2bの例では、軸Oxが選択される。
【００２８】
線分の一端S1から開始し、座標XS1を好適な方向Oxの軸に沿って増やす。xS=xS1+1であるような、線分2に属する点Sが検討される。これは、Sに最も近い、グリッド1上の点を判定するケースである。２つの点が候補となる。この2つの点はすなわち、xC1=xS1+1であり、yC1=yS1+1であるような、S1の北東方向に位置している点C1と、xC2=xS1+1であり、yC2=yS1であるような、S1の東方向に位置している点Eである。
【００２９】
線分C1C2の中点Mを考慮に入れて、差Δ1=yC1−yM及びΔ2=yM−yC2が評価される。Δ1<Δ2である場合、C1が点Sの近似として選択され、さもなければ、C2が点Sの近似として選択される。
【００３０】
この処理は、斜線分2上の点全てについて繰り返される。破線3が、関連性8、すなわち、隣接する８つのものを点が有しているとみなす関連性、の意味合いで関連する点の連続として得られる。
【００３１】
ブレセンハムのアルゴリズムを用いて線分をトレースすることを意図している「line」関数の実施例を以下にC言語で表す：
【００３２】
【数１】
2006524384.tif 000003
この例は、このアルゴリズムが単純であることを示しており、このアルゴリズムは、整数値しか用いず、乗算は何ら用いず、数コード行で要約されている。ブレセンハムのアルゴリズムの利点の１つとして、ハードウェア実施形態によく適応されたものであるということがある。
【００３３】
しかし、本発明は、このアルゴリズムを用いることに限定されない一方、斜線分をトレースする何れかの他の方法に関する。ワードをこの線分と関連付ける線分トレース手法が存在し、このワードの計算は、この線分上の２つの連続した点間の接続のフリーマン・コードに基づいている。この手法のうち、「Fundamental  Algorithms  in  Computer  Graphics、Spring-Verlag,  1985,  page  135-139」に公表されている、Castleによる、
「An  application  of  Euclid’s  algorithm  to  drawing  straight  lines」と題する文献にキャッスル手法が記載されている。このような手法の欠点の１つとして、実施するうえでの計算量が、ブレセンハムのアルゴリズムを実施するよりも大きくなるということがある。
【００３４】
図2bは、平行四辺形ABCDの例を示し、その第１の線分AB、第2の線分AC及び第3の線分BDはブレセンハムのアルゴリズムによってトレースされる。この例では、第１の線分ABは平行軸Axを好適な方向として利用することによってトレースされる一方、第２の線分AC及び第３の線分BDは、垂直軸Ayを好適な方向として利用することによってトレースされる。
【００３５】
３つの工程11,12及び13の終了時には、第１の線分AB、第２の線分AC及び第3の線分BDのトレースが分かる。したがって、これらの３つの線分を構成する、離散グリッド上の点は全て、参照フレーム(Ax,Ay)における座標によって完全に判定される。
【００３６】
最後に、本発明による方法は、第１の線分ABに対して平行であり、平行四辺形ABCD内に備えられる線分を全てトレースする工程20を備える。
【００３７】
図4における機能図によって表され、図2bにおける例によって示される、本発明の第１の実施例では、工程20は、第２の線分ACに属する点Aiと第3の線分BDに属する点Biとの間に備えられる線分の座標を計算するサブ工程21を備え、Ai及びBiは各々、A及びBから同じ距離のところに位置している。サブ工程21は、平行四辺形ABCD内に位置しており、水平又は垂直の好適な方向において、AとBとの各々から等距離のところに位置している線分AiBi全てをトレースするために繰り返される。図2bにおける例では、線分AC及びBDの好適な方向は垂直軸Ayである。xAから開始して、yA1=yA+1であるように第２の線分ACの点A1が検討され、yB1=yB+1であるように第3の線分BDの点B1
が検討される。第２の線分ACと第３の線分BDは平行であるので、点A1及びB1は、軸Ayに沿ってAとBとの各々から等距離のところにある。
【００３８】
効果的には、サブ工程21は、線分A1B1上の点の座標を計算するブレセンハムのアルゴリズムを用いる。この処理は、yAi≦yCであるような線分AiBi全てについて、すなわち、平行四辺形全体を巡るまで繰り返される。
【００３９】
平行四辺形を上記「line」関数を用いてフィル・インすることが意図されている「parallelogram」関数の実施例を以下に表す。
【００４０】
【数２】
2006524384.tif 000004
【００４１】
【数３】
2006524384.tif 000005
本発明のこの第１の実施例の利点の１つとして、この実施例が非常に単純であるということがある。以下に示す「parallelogram」関数の例が表すように、ブレセンハムのアルゴリズムは、整数値並びに、加算及び比較テストに限定された単純な演算しか用いない。したがって、そのようなアルゴリズムは、例えば、リアル・タイムでの実行との互換性を有し、ビデオ・ゲームの制作に必要であるようなハードウェア実施形態によく適応されたものである。
【００４２】
本発明のこの第１の実施例の欠点の１つとして、この実施例が、平行四辺形において用いる、離散グリッド上の点全てを網羅的に巡ることを保証しないということがある。これは、ブレセンハムのアルゴリズムが、誤差をもたらす近似に基づいているからである。図3bでは、線分2の点Sの縦座標ySは整数の縦座標yC1によって置き換えられる。生じる誤差はyC1−ySに等しい。横に並んだいくつかの斜線分をブレセンハムのアルゴリズムによって生成するうえで、サブ工程21はこの種の誤差を積み重ね、それは、離散グリッド上の特定の点は、平行四辺形内に備えられるが、何れの線分AiBiのトレース上にもないということを意味する。そのような誤差は図5によって示す。点A1と点B1との間でトレースされる線分と、点Aと点Bとの間でトレースされる線分との間に、平行四辺形ABCDに属するが、平行四辺形ABCDの何れの線分も通らない点が存在する。
【００４３】
図6に機能的に表す、本発明の第２の実施例では、工程20は、平行四辺形ABCDに備えられる平行移動される線分を供給することを意図している、第１の線分ABを水平及び垂直の好適な方向において水平移動させるサブ工程22を備える。この平行移動サブ工程22は、水平又は垂直の好適な方向に平行移動させることによって第１の線分ABに対して平行である線分の座標を計算する工程を備える。図7aは、線分ABの、水平方向の平行移動を軸Axに沿って平行四辺形ABCD内で行う例を表す。そのような平行移動は、実施するのが非常に単純である。実際に、線分A’1B’1を1単位分水平方向に、正のxの方向に水平移動させることを検討する。これは、ｘA’1=ｘA+1であり、yA’1=yAであることをもたらすに過ぎない。このようにして、xA<ｘA’≦xCであるなどの、考えられる平行移動線分
A’iB’iの全てがトレースされる。平行四辺形6が形成される。平行四辺形6と平行四辺形ABCDとに共通の表面5に属する点しか考慮しなくてよい。これを行うよう、工程20は、平行移動される線分A’iB’i上の点Pが平行四辺形ABCDに属するか否かを検査することを意図している検査サブ工程23を備える。この工程は、点Pの縦座標xPが線分BDの点Biの縦座標yBiよりも、ｘBi=ｘB+(ｘAi−ｘA’1)であるように小さいことを検証する工程を備える。図7aに示すように、第１の線分ABの好適な方向におけるそのような水平移動は、平行四辺形ABCDの全てをフィル・インすることを可能にする訳ではない。図7aでは、軸AXの線分CDとの交点Hを検討する。頂点ACHによって形成される三角形はこれからフル・インされなければならない。この目的で、図7bを参照しながら、第3の頂点Cを線分ABの延長部分上に射影させることによって得られる点Eを検討し、この延長部分は直線（AB）によって好適な方向Axにおいて表すことになる。工程20は、この射影点Eの座標を計算するサブ工程24も備える。この計算は種々の方法で行い得る。第1の解決策は、
【００４４】
【数４】
2006524384.tif 000006
のベクトル及び
【００４５】
【数５】
2006524384.tif 000007
のベクトルを検討する工程を備える。
【００４６】
【数６】
2006524384.tif 000008
のベクトルと
【００４７】
【数７】
2006524384.tif 000009
のベクトルが平行である場合、当業者に周知である、−xB・yE−yB・(−xE)=0の式が満たされる。yE=yCであることが分かっている場合は、EはCの軸Axに沿った射影であるため、Eの横座標は、xE=(xB・yC)/yBである。この解決策の利点の１つとしては、非常に単純な関係に基づいているということがある。主な欠点は、この解決策が、プロセッサ上の計算サイクルの点で費用が非常に高くつく除算を用いるということである。代替策として、２つの工程を備える、よりアルゴリズム的な方法を用い得る。例を図8に示す。第１の工程は、Eの直線（AB）上の非最適位置ENOを判定する工程を備える。これは、
【００４８】
【数８】
2006524384.tif 000010
に表す。
【００４９】
点Bと、点Aに対して対称である点E’を検討する。この点E’がCの縦座標よりも絶対値で大きな縦座標を有する場合、ENOを点E’に等しいものとし、さもなければ、条件
│yENO│≦│yC│が満たされるまで、Aと、点E’に対して対称である点E’’を検討するなどの工程を行う。
【００５０】
第２の工程は、線分ENO  Aの点の座標をブレセンハムのアルゴリズムによって判定することによって直線（AB）上の点Eの位置を精緻化する工程を備える。Aから開始し、線分AENO上を点Eまで、すなわち、線分ENO  A上のycに等しい縦座標の点まで、進むということである。
【００５１】
この第２の方法の利点の１つとして、除算を用いないということがある。
【００５２】
次に、工程20は、射影E及び第１の頂点Aによって形成される線分EAの点の座標を計算するサブ工程25を備える。斜線分をトレースする、上記で実施された工程のように、このサブ工程25は効果的に、ブレセンハムのアルゴリズムを用いる。
【００５３】
線分EAを好適な方向に平行移動させるサブ工程26は、線分ABを平行移動させる工程22の前述の原理に同様な原理によって、線分EAに対して平行である線分EiA’  iを供給することを意図している。前述の線分ABと同様に、サブ工程26が、EAから平行移動される線分EiA’  i上の点Pが平行四辺形ABCDにおいて備えられるか否かを検査するよう意図している検査サブ工程27と組み合わせられる。
【００５４】
線分AB及びEAの軸Axに沿った、線分ACに相当する距離にわたって連続して平行移動させることによって、平行四辺形ABCD上の点全てを巡ることが可能となる。この第２の実施例の利点の１つとしては、この実施例が、平行四辺形ABCD全体をフィル・インすることを備えるということがある。線分の平行移動を行い、その点が平行四辺形に備えられているか否かを検査するのに用いる処理が、２つの既知点間の斜線分をトレースするブレセンハムのアルゴリズムが用いる計算量と同等の計算量を有するといるものとみなし得る。一方、射影点Eを計算する工程によって、この第２の実施例の計算量が第１の実施例の計算量よりも少し大きくなる。しかし、以下に表す実施例によって示すように、第2の実施例は依然として、実施するのが比較的に単純である。
【００５５】
【数９】
2006524384.tif 000011
【００５６】
【数１０】
2006524384.tif 000012
【００５７】
【数１１】
2006524384.tif 000013
【００５８】
【数１２】
2006524384.tif 000014
【００５９】
【数１３】
2006524384.tif 000015
本発明による処理方法を適切にプログラムされる回路によって実施することが考えられる。プログラミング・メモリ内に備えられるコンピュータ・プログラムは、図4及び図6を参照しながら前述した種々の処理を回路に行わせることが可能である。コンピュータ・プログラムは、例えば、このプログラムを備えるディスク、などのデータ媒体を読み取ることによってプログラミング・メモリにロードしてもよい。読み取りは、例えばインターネットなどの通信ネットワークによって行ってもよい。この場合、サービス・プロバイダは、コンピュータ・プログラムを関係者にダウンロード可能な信号の形式で利用可能にさせることになる。
【００６０】
本発明は、例として表したに過ぎない実施例に限定されるものでない。修正や改善をこのような実施例に、本発明の範囲内に留まりながら行うことが可能である。特に、磁気共鳴イメージングやポジトロン放出トモグラフィなどの他のイメージング・モードを用いることが可能である。本明細書及び特許請求の範囲の原文では、「comprise」の動詞は、他の構成要素、手段又は工程を用いることが排除されないということを意味するのに用いられている。
【図面の簡単な説明】
【００６１】
【図１ａ】従来技術による、直線エッジを有する三角形のフィル・インを示す図である。
【図１ｂ】本発明による、平行四辺形のフィル・インを示す図である。
【図２ａ】本発明による、平行四辺形をフィル・インする方法を表す機能図である。
【図２ｂ】本発明の第1の実施例による、平行四辺形をフィル・インする例を示す図である。
【図３ａ】離散グリッド上の斜線分をトレースするブレセンハムのアルゴリズムの原理を示す図である。
【図３ｂ】離散グリッド上の斜線分をトレースするブレセンハムのアルゴリズムの原理を示す図である。
【図４】本発明の第1の実施例を示す機能図である。
【図５】本発明の第1の実施例による、平行四辺形のフィル・イン中の穴の形成を示す図である。
【図６】本発明の第2の実施例を示す機能図である。
【図７ａ】本発明の第2の実施例による、平行四辺形のフィル・インの例を示す図である。
【図７ｂ】本発明の第2の実施例による、平行四辺形のフィル・インの例を示す別の図である。
【図８】本発明の第2の実施例による、点Eの座標を計算する方法の原理を示す図である。
2006524384.tif 000016
2006524384.tif 000017
2006524384.tif 000018
【図４】
2006524384.tif 000019
【図５】
2006524384.tif 000020
【図６】
2006524384.tif 000021
2006524384.tif 000022
【図８】
2006524384.tif 000023
【国際調査報告】
2006524384.tif 000024
2006524384.tif 000025