(57)【要約】グラフィックシステムにおいて、テクセルグリッド内で複数のテクセルをカバーするフットプリントに係るテクセルのカラー値をカラー計算するための重み付けファクタを決定する方法において、まずフットプリントの形状情報が決定される。その後、フットプリントのエッジが決定され、この決定されたエッジは階段関数で近似される。階段関数により接触されたテクセルグリッドのテクセルが決定され、フットプリントによりカバーされた各テクセルのサブエリアに依存して、階段関数の一部を含む各テクセルのための重み付けファクタが決定される。
2006502475.tif 000002
【特許請求の範囲】
【請求項１】
グラフィックシステムにおいて、テクセルグリッド内で複数のテクセルをカバーするフットプリントに係るテクセルのカラー値(color pix) をカラー計算するための重み付けファクタを決定する方法であって、
（ａ）上記フットプリントの形状情報（ｖi ）を決定する工程と、
（ｂ）上記フットプリントのエッジ（ｓi ）を決定する工程と、
（ｃ）工程（ｂ）において決定されたエッジ（ｓi ）を階段関数で近似する工程と、
（ｄ）上記テクセルグリッドの上記階段関数により接触されたテクセルを決定する工程と、
（ｅ）上記フットプリントによりカバーされた各テクセルのサブエリアに依存して、上記階段関数の一部を含む各テクセルのための重み付けファクタ（ｗ' tex,ｗ’prop ）を決定する工程と、を備えることを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、
上記工程（ｄ）において、上記階段関数に接触されたテクセルは、上記階段関数の垂直部分の始点および／または終点を基にして決定されることを特徴とする方法。
【請求項３】
請求項１または２に記載の方法であって、
上記工程（ｅ）において、上記階段関数により接触されておらず且つ上記フットプリントによりカバーされている上記テクセルグリッドのテクセルに対して、共通の重み付けファクタが関連付けられていることを特徴とする方法。
【請求項４】
請求項１乃至３のいずれかに記載の方法であって、
上記工程（ｅ）において、各テクセルのための重み付けファクタは１つのデータ構造と関連付けられていることを特徴とする方法。
【請求項５】
請求項１乃至４のいずれかに記載の方法であって、
上記フットプリントの各エッジに係る階段関数は、複数のステップ（ｎi , step）と、複数の水平ステップ要素と、複数の垂直ステップ要素とを備え、
各エッジは同一長さを持つ複数の連続的なエッジ部（ｑi ）を含み、
上記エッジのエッジ部（ｑi ）の終点が上記階段関数の水平ステップ要素と交差する時に水平エッジが存在し、
上記エッジのエッジ部（ｑi ）の終点が上記階段関数の垂直ステップ要素と交差する時に垂直エッジが存在し、
１つの水平エッジはいくつかの垂直ステップ要素を含み、この垂直ステップ要素の数は上記階段関数のステップの数（ｎi,step）と同一であり、
１つの垂直エッジはいくつかの垂直ステップ要素を含み、この垂直ステップ要素の数は上記階段関数のステップの数（ｎi,step）よりも追加的な垂直ステップ要素の分だけ多く、
上記追加的な垂直ステップ要素は、同一の垂直位置を持つ近隣のエッジの重み付けファクタを計算するために使用されることを特徴とする方法。
【請求項６】
請求項１乃至５のいずれかに記載の方法であって、
上記工程（ｅ）に続く上記テクセルのサブエリアの決定は、上記階段関数によって決定され且つ上記フットプリントによりカバーされたテクセルサブエリアの決定を含むことを特徴とする方法。
【請求項７】
請求項６に記載の方法であって、
上記工程（ｄ）で決定される重み付けファクタ（ｗ’tex , ｗ’prop, ｗ* tex , ｗ* prop ）は、上記テクセルサブエリアのテクセルエリア全体に対する比率によって決定されることを特徴とする方法。
【請求項８】
請求項１乃至７のいずれかに記載の方法であって、
上記フットプリントに拡大オフセット（ｒ）が関連付けられ、
上記工程（ａ）の後に、この拡大オフセット（ｒ）に基づき、上記フットプリントは上記拡大オフセット（ｒ）に依存する距離分だけ上記フットプリントのエッジ（ｓi ) を外側へオフセットさせることで拡大され、
上記工程（ｂ）でオフセットエッジ（ｓ’i ) が決定され、
上記工程（ｃ）で上記オフセットエッジ（ｓ’i ）が階段関数により近似され、
上記工程（ｅ）では、拡大されたフットプリントによりカバーされた各テクセルのサブエリアに依存して、オフセットエッジ（ｓ’i ）を含む各テクセルのための重み付けファクタ（ｗ’tex,ｗ’prop）が決定されることを特徴とする方法。
【請求項９】
請求項８に記載の方法であって、
上記フットプリントを拡大する結果として生じるギャップ（ｇ* i ）は、水平エッジおよび垂直エッジにより満たされることを特徴とする方法。
【請求項１０】
請求項９に記載の方法であって、
上記工程（ｅ）において、組み込まれた垂直エッジを含む各テクセルのための重み付けファクタ（ｗ* tex,ｗ* prop）が、上記拡大されたフットプリントによってカバーされた各テクセルのサブエリアに依存して決定されることを特徴とする方法。
【請求項１１】
請求項８乃至１０のいずれかに記載の方法であって、
上記フットプリントの拡大は、上記エッジの終点（ｖi ）を、上記拡大オフセット（ｒ）により決定される距離分だけ水平方向および垂直方向にオフセットすることを含むことを特徴とする方法。
【請求項１２】
請求項１乃至１１のいずれかに記載の方法であって、
上記フットプリントの全てのエッジに係る重み付けファクタは、並行して生成されることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概ね、コンピュータで制御されるラスター表示システム上に画像または映像を表示させる方法に関する。特に、本発明は、記憶された離散画像であって後にテクスチャとも呼ぶ離散画像を再構成し、スケールあるいは処理し、ラスターディスプレイ上に高品質で立体的に射影するために必要とされる異方性フィルタリングメカニズムおよびこれに対応する装置に関する。特に、本発明はフットプリントに係るテクセルのカラー値をカラー計算するための重み付けファクタ(weighting factors) を決定する方法に関する。
【背景技術】
【０００２】
従来の技術においては、例えばいわゆるエリアサンプリングと呼ばれるような異方性フィルタリング法が、テクスチャをフットプリントに結合させるものとして知られている。従来の技術では、いわゆる重み付けられたエリアサンプリングと重み付けられていないエリアサンプリングとが知られているが、これら従来技術の方法では、描出された画像の中に、重み付けられたサンプリングと重み付けられていないサンプリングとの境界部において知覚可能なアーチファクト（artifacts）による不連続性が生じるという欠点が知られている。
【０００３】
「フットプリント」とは、オブジェクトの画素（ピクセル）の曲面上での立体的射影である。「フットプリント」は、オブジェクトの正方形の画素（ピクセル）を曲面上に射影したものを標準テクセルグリッド（テクスチャエレメントグリッド）に立体的に射影した近似的な結果を示す、凸状の４辺を持つ（４辺形の）描画であると言うこともできる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
この従来技術とは異なり、本発明の目的は、フットプリントのテクセルのための重み付けを生成する時に、フットプリントのエッジの下側のテクセルを簡単かつ速やかに決定できる、改善された方法を提供することである。
【０００５】
この目的は、請求項１に記載の方法により達成できる。
【課題を解決するための手段】
【０００６】
本発明は、グラフィックシステムにおいて、テクセルグリッド内で複数のテクセルをカバーするフットプリントに係るテクセルのカラー値をカラー計算するための重み付けファクタを決定する方法を提供し、
（ａ）フットプリントの形状情報を決定する工程と、
（ｂ）フットプリントのエッジを決定する工程と、
（ｃ）工程（ｂ）において決定されたエッジを階段関数（staircase function）で近似する工程と、
（ｄ）上記テクセルグリッドの上記階段関数により接触されたテクセルを決定する工程と、
（ｅ）上記フットプリントによりカバーされた各テクセルのサブエリアに依存して、上記階段関数の一部を含む各テクセルのための重み付けファクタを決定する工程と、を備える。
【０００７】
望ましい実施例によれば、階段関数により接触されたテクセルは、階段関数の垂直部分の始点および／または終点を基にして決定される。
【０００８】
上記階段関数により接触されておらず且つフットプリントによりカバーされている上記テクセルグリッドのテクセルには、共通の重み付けファクタが関連付けられ、各テクセルのための重み付けファクタは１つのデータ構造と関連付けられていることが望ましい。
【０００９】
他の望ましい実施例によれば、フットプリントの各エッジのための階段関数は、複数のステップ（階段）と、複数の水平ステップ要素と、複数の垂直ステップ要素とを備え、各エッジは同一長さを持つ複数の連続的なエッジ部を含み、上記エッジのエッジ部の終点が上記階段関数の水平ステップ要素と交差する時に水平エッジが存在し、上記エッジのエッジ部の終点が上記階段関数の垂直ステップ要素と交差する時に垂直エッジが存在し、１つの水平エッジはいくつかの垂直ステップ要素を含み、この垂直ステップ要素の数は上記階段関数のステップの数と同一であり、１つの垂直エッジはいくつかの垂直ステップ要素を含み、この垂直ステップ要素の数は上記階段関数のステップの数よりも追加的な垂直ステップ要素の分だけ多く、上記追加的な垂直ステップ要素は、同一の垂直位置を持つ近隣のエッジの重み付けファクタを計算するために使用される。
【００１０】
さらに他の実施例によれば、上記フットプリントに拡大オフセット（シフト）が関連付けられる。すなわち、上記工程（ａ）の後に、この拡大オフセットに基づき、フットプリントは拡大オフセットに依存する距離分だけフットプリントのエッジを外側へシフトさせることで拡大され、次に、上記工程（ｂ）ではシフトされたエッジが決定され、上記工程（ｃ）ではシフトされたエッジが階段関数により近似され、さらに工程（ｅ）では、拡大されたフットプリントによりカバーされた各テクセルのサブエリアに依存して、シフトされたエッジを含む各テクセルのための重み付けファクタが決定される。
【００１１】
フットプリントは、拡大オフセットにより決定される距離分だけエッジの終点が水平方向および垂直方向にシフトされることで拡大される。結果として生じるギャップは、水平および垂直エッジにより満たされることが望ましく、また、組み込まれた垂直エッジを含む各テクセルのためのさらなる重み付けファクタが、続いて決定されることが望ましい。
【００１２】
本発明の方法は、異方性フィルタリングへの新規なアプローチを提供するものであり、これにより、例えばエリアサンプリングの公知のフィルタリング技術を、立体的に射影された正方形の画素を現し、標準テクセルグリッドの上に貼り付けられた４辺形のフットプリントに対して適応させることが可能となる。より詳細には、本発明によれば、別の入力パラメータ、いわゆる拡大オフセットがエイリアシングアーチファクト（aliasing artifacts）を制御するために使用される。拡大オフセットは、重み付けされたエリアサンプリングまたは重み付けされていないエリアサンプリングが、フットプリントのエリアに適応されるべきか否かを決定し、この場合、特にこれにより、エリアサンプリングに対する重み付けの寄与(weighting contribution)の大きさあるいは重み付けの程度がどれ程であるべきかが決定される。本発明は望ましくは変形フットプリント、例えば小さくて長いフットプリントに対して適応される。
【００１３】
本発明の典型的特性であり本質的な特徴は、しきい値を基にしたハードウエアベースのスイッチがないという点である。すなわち、このスイッチとは、重み付けされたエリアサンプリングまたは重み付けされていないエリアサンプリングが実行されるべき時を決定し、その結果として知覚可能なアーチファクトによる不連続性が生じる可能性もあるスイッチである。これに代えて、重み付けされたエリアサンプリングの大きさはさらに増大されることが望ましい。重み付けの寄与はフットプリントが小さくなればなる程増大することが望ましく、特に、フットプリントがテクセルの幅または高さの伸び量よりも小さくなる時に増大することが望ましい。
【００１４】
本発明の他の態様に従えば、本発明は、グラフィックシステムにおいて、あるテクセルを少なくとも部分的にカバーするフットプリントに係るテクセルのカラー値をカラー計算するための重み付けファクタを決定する方法を提供し、この方法においては、フットプリントの形状情報が決定され、ある拡大オフセットに基づき、フットプリントは拡大オフセットに依存する距離分だけフットプリントのエッジを外側へシフトさせることで拡大され、その結果、複数のテクセルをカバーすることになる。その後、拡大されたフットプリントによりカバーされた各テクセルのサブエリアに依存して、シフトされたエッジを含む各テクセルのための重み付けファクタが決定される。
【００１５】
本発明のこの態様に従えば、極少数のテクセルまたは単一のテクセルをカバーするフットプリントが、フットプリントの拡大により、近隣のテクセルの情報をも考慮に入れることで、さらに広い基礎に基づいてカラー決定されることが可能となる。ここで注目すべき点は、拡大はカラー値を決定するためにだけ起きるという点であり、フットプリントはそれが関係するオブジェクトのその後の描画のために拡大されるのではないという点である。
【発明を実施するための最良の形態】
【００１６】
本発明の望ましい展開は、従属請求項の中で定義される。
【００１７】
本発明の望ましい実施例は、添付図を参照しながら以下に詳細に説明する。
図１Ａおよび図１Ｂは本発明の望ましい実施例のフローチャートであり、
図２はテクスチャスペースにおけるフットプリントを示し、
図３はフットプリントのエッジ配向(edge orientation)の決定方法を示し、
図４Ａおよび図４Ｂは、本発明の実施例に従うエッジ計算の方法を示すフローチャートであり、
図５Ａおよび図５Ｂは、フットプリントのフィルタ拡大に係る２つの実施例を示し、
図６は階段関数によるフットプリントのエッジの近似を示し、
図７はテクセルグリッド内でシフトされたエッジを関連する重み付けテーブルエントリと共に示し、
図８Ａおよび図８Ｂは、本発明の実施例に従うシフトされたエッジの処理方法を示すフローチャートであり、
図９はフットプリントおよび拡大フットプリントを、ステップ拡張（step propagation）と共に示し、
図１０Ａおよび図１０Ｂは、頂点エッジおよびスライス（垂直ステップ要素）の表記を説明するものであり、
図１１Ａおよび図１１Ｂは、ピクセルのカラーを計算する方法を示すフローチャートである。
【実施例１】
【００１８】
以下に本発明の第１実施例を図１を参照しながら説明するが、個々の処理工程については、後段においてさらに詳細に説明する。
【００１９】
詳細な説明の中では、フットプリントの説明のためにベクトルの数学的表記法（本文中では下線付き文字で表記する）が使用されることに気をつけていただきたい。全ての座標(coordinates) および長さの単位長は、オリジナルテクスチャ内またはもし存在するならばミップマップステップ(MipMap step) に従うテクスチャ内におけるテクセルの幅（または高さ、それぞれ）である。エッジ属性(edge attributes) および頂点属性(vertex attributes) は、０から３まで変化する指数(index) ｉを含み、指数の計算の結果でｉ＝０およびｉ＝３を超えた結果は、それぞれ実際のエッジに計算し戻される。つまり、ｉ＝４の結果はｉ＝０となり、ｉ＝−１の結果はｉ＝３となる。
【００２０】
本発明の方法の望ましい実施例によれば、ブロック１００において、入力データすなわち４辺形フットプリントの形状、位置、配向(orientation) を表す情報を受け取り、これはブロック１０２において準備が整った状態となる。より正確には、フットプリントデータｖi in，フットプリントの回転方向ｄ，および拡大オフセットｒがブロック１０２に供給される。追加的な入力パラメータ、すなわち拡大オフセットｒを受け取ることで、本発明によれば、小さなあるいは薄いフットプリント、特に小さなあるいは薄い４辺形フットプリントのために必要となる重み付けされたエリアサンプリングの程度を決定することが可能になる。
【００２１】
ブロック１０４においては、いわゆるエッジ計算が実行される。このエッジ計算は、受け取られた形状情報および拡大パラメータｒを基にしてフットプリントのエッジをオフセットすることでフットプリントを拡大することを含む。エッジ計算ブロック１０４では、垂直エッジはその後、拡大の結果生じたギャップの中に組み入れられていき、限界長方形(limitation rectangle)が計算され、全てのエッジはこのブロック１０４において左と右のエッジに分類される。次に、拡大された頂点エッジに関する属性がブロック１０６に供給され、オフセットエッジに関する属性がブロック１０８に供給される。より詳細には、拡大されたフットプリントに関するフットプリント情報ｖi * ，個々のエッジの配向ａi * ，および結果として生じるギャップｇi * ，がブロック１０６に供給される。また、頂点情報ｖi ' ，オフセットエッジの配向ａi ' ，および対応するエッジベクトルｓi ' がブロック１０８に供給される。ブロック１０８に供給された情報はブロック１１０に送られ、ここではオフセットエッジに関する処理が実行される。他方、ブロック１１０では、ブロック１１２に供給されるべきステップ拡張ｐi * が計算される。ブロック１０６およびブロック１１２に供給されたパラメータは次にブロック１１４に送られ、ここで頂点エッジが処理される。
【００２２】
頂点エッジの処理（ブロック１１４）およびオフセットエッジの処理（１１０）の結果、ブロック１１６およびブロック１１８（図１Ｂ参照）に供給されるべき頂点エッジおよびオフセットエッジのための重み付けテーブルが生成される。
【００２３】
このようにして生成されたテーブルに基づいて、ブロック１２０においてカラー計算が実行される。このとき、ブロック１２０はテクスチャに関する情報をブロック１２２から追加的に受け取る。ブロック１２０におけるカラー計算により、ブロック１２４に供給されブロック１２６で出力されるピクセルカラーが作られる。
【００２４】
もしフットプリントに係る拡大が必要でないかまたは供給されない場合には、フットプリントエッジのオフセットはないであろう。この時、本発明の方法はオリジナルエッジに対してのみ実行される。この場合には、追加的に挿入されたエッジは無いか、あるいは計算のためにゼロに設定される。
【００２５】
フットプリントの各エッジに係る適切なデータ構造がブロック１１０−１１８で生成される。つまり、後述する工程が各エッジのために並行して実行される。最初、エッジは適切な数の簡素なステップにより近似され、左エッジの階段関数により接触された全てのテクセルがサーチされる。発見された各テクセルについて、階段関数より右側に残るテクセルエリアのフラクション(fraction)に対応する重み付けの値が関連付けられる。同様にして、描画されるべき構造の下にあり且つ右エッジの階段関数に接触された全てのテクセルがサーチされる。このようにして見つけられたテクセルに関し、各テクセルの階段関数より左側に残るエリアのフラクションに対応する重み付けの値が関連付けられる。続いて、全ての座標および対応する重み付けは、フットプリントのエッジに関連した適切で唯一のデータ構造の中に記憶される。加えて、≦＋１または≧−１となる重み付け値は、それぞれ全てのテクセルに関連付けられる。すなわち左エッジあるいは右エッジよりもそれぞれ右側のテクセルであって各エッジにより接触されていないテクセルと、限界長方形の右エッジよりも左側のテクセルとに関連付けられる。この情報は、データ構造に追加される。
【００２６】
望ましくは、本発明の望ましい実施例に沿うこの方法で生成されたデータ構造は、効率的に評価され、フットプリントによってカバーされた各テクセルは記憶された座標によって直接的にアドレスされ、その結果、次にそれに対応するカラーが、それに関連した重みによって掛算（重み付け）されることができる。ここで指摘しておくが、各重み付けファクタは、当該テクセルの中に含まれているこれらエッジの重み付けの合計である。
【００２７】
図１Ｂのブロック１２０では、従来技術でも知られた方法でカラー計算が実行される。このカラー計算のために、全ての重み付けファクタは集められ、フットプリントにより使用された全ての重み付けされたテクセルもまた集められ、次に、集められたカラーは集められた重み付けファクタにより割算される。その結果は、テクスチャ画像からフィルタリングされ取り戻された画像の破片(picture fragment)を示し、これは、テクスチャ画像の上に描出または射影されるように意図されていたピクセルと関連付けられる。
【００２８】
図１において説明したｖi ' ，ａi ' ，ｓi ' ，およびｖi * ，ａi * ，ｇi * のそれぞれの値に関しては、アポストロフィを付した値はオフセットエッジに言及し、アステリスクを付した値は頂点エッジに言及することに注意していただきたい。
【００２９】
本発明の長所として、本発明の方法が実際のハードウエア内に実現された時に、本発明固有の特性として、高度の並行処理を使用する可能性を提供できるという点がある。加えて、本発明の方法は、ハードウエアパイプラインの中に実現させることも可能であり、本発明の望ましい実施例によれば、上述の複数の処理工程が異なるパイプラインステージの中のハードウエア内で実現される。上述の処理工程であって各エッジのためのデータ構造を生成している処理工程は、典型的にはハードウエアモジュールとして実現され、各エッジのために並行して例示化（呼出）されることが望ましい。並行して例示化されたモジュールは、それら自体が、ハードウエアパイプライン全体の中の１つのパイプラインステージを表している。
【００３０】
４辺形フットプリントによりカバーされたテクセルアレーからピクセルカラーを取り戻すための基本的な処理は、このフットプリントに関し、重み付けされていないエリアサンプリングを実行することである。これは、テクセルのカラー要素は、まずフットプリントの上で積分され、続いてその結果がフットプリントの合計されたエリアによって割算されることを意味する。この積分の計算には、事前に各テクセルを適切な重み付けファクタによって掛算することが必要であり、その重み付けファクタは、フットプリントの完全に下側に配置されたテクセルについては１．０である。本発明によれば、フットプリントによって部分的にしかカバーされていない各テクセル、すなわちフットプリントのエッジに配置された各テクセルに対しては、カバーされたエリアのサイズに比例する重み付けファクタが関連付けられる。
【００３１】
このように、本発明の方法は、上述の２つのタスクを実行する。すなわち、４辺形フットプリントにより全部または一部をカバーされた全てのテクセルを認識することと、各テクセルのための重み付けを計算してこの重み付けファクタを対応するテクセルに関連付けることである。
【００３２】
加えて、本発明によればフェージング（fading）も実現できる。これは、重み付けされていないエリアサンプリングから重み付けされたエリアサンプリングへのフェージングを実行するための追加的なパラメータ、すなわち拡大パラメータｒによって制御される。
【００３３】
この態様の背景は、フットプリントが強く変形されている場合、例えば非常に薄く非常に長いエリアしか持たない形状である場合には、取り戻された画像内での重み付けされていないエリアサンプリングによって、知覚可能なエイリアシングアーチファクトが生成されるということである。同じことが、フットプリントによってカバーされるエリアがテクセルグリッドの正方形テクセルのエリアよりもかなり小さい場合にも起こる。
【００３４】
これらの場合に発生するアーチファクトを防止するために、本発明によれば、フットプリントの境界を示す４エッジをオフセットすることで、フットプリントのエリアを拡張させる。上述のような場合には、この方法は重み付けされたエリアサンプリングの特徴を満たすフィルタカーネル(filter kernel) の射影として判断されることが可能なフットプリントを近似し、このフィルタカーネルはその隣接するものとオーバーラップし、バイリニア相似分布（bilinear similar distribution ）を持つ。
【００３５】
上述の、図１に示された本発明の望ましい実施例の説明の中で注意すべき点は、本発明の方法はブロック１００〜１０８を含み、これらのブロックは基本的には従来のカラー計算のために必要とされるデータを提供するという点である。さらに、図１に関して注目すべき点は、すべての長方形ブロックは主な処理工程を示し、これらの処理工程については以下に本発明の望ましい実施例に関連してより詳細に説明する。これら処理工程の結果は、図１内に平行四辺形で示されるデータ構造の中に記憶され、次の処理工程のための入力として使用される。
【００３６】
図１においてブロック１００に入力されるデータおよびブロック１０２に供給されるデータは、フットプリントｖi inに関する情報を含み、望ましい実施例によれば、このフットプリントは凸状であり、その中ではいずれのエッジの高さおよび幅も所定の最大値Ｅmax を超えられないよう設定されている。さらに、フットプリントの回転方向ｄも入力され、ここではｄ＝＋１は時計周りの回転方向を表し、ｄ＝−１は反時計周りの回転方向を表す。フットプリントの変形によりこの回転が決定されることが不可能になった時、ｄは０に設定される。加えて、拡大オフセットｒが入力されるが、この値は望ましくは０．０から０．５の間に限定される。
【００３７】
上述の最大エッジ長さＥmax は、望ましくはハードウエアコード化された値であり、２の累乗であることが期待され、ここでは望ましい値として８とする。これより高い値はラスター処理すなわちグラフィックシステムの処理速度を著しく減速させ、必要とされるデータ構造をかなり増大させるであろう。もし２の累乗でない値が使用されたとすれば、最大値Ｅmax に関連する計算は、莫大な費用をかけたハードウエアの中でのみ実現可能となるであろう。
【００３８】
図２は、テクスチャスペース内でのフットプリントの表示例を示す。この例に描かれたテクスチャスペースは、座標ｘおよびｙによって表される。このフットプリントは、ｖ0 からｖ3 までの４個の頂点ベクトルおよびｓ0 からｓ3 までの４個のエッジベクトルにより定義される。さらに、フットプリントの回転方向ｄはｓ0 からｓ3 までのエッジベクトルの方向により定義される。図２はテクスチャスペースにおけるフットプリントの典型的な形を示している。フットプリントはｓ0 からｓ3 までの４個のエッジからなる囲いによって定義されるので、しばしば４辺形要素とも呼ばれる。図２に示された４つのベクトルによりテクスチャスペース内に配置されるｖ0 からｖ3 までの４個の頂点は、ｓ0 からｓ3 までのエッジを定義する。
【００３９】
詳細は後述するが、本発明の主な態様は、水平および垂直の階段関数が各エッジを近似するために適用されるということである。しかし、ｓ0 からｓ3 までの全てのエッジのために並行して処理されることが可能な、一貫した固有の重み付けアルゴリズムを得るために、さらなる計算のためには、エッジは、あるエッジの右側に配置されたテクセルにのみ寄与すると仮定される。よって、左側エッジからの値は、すべてのエッジに関して生成された有効な重み付けファクタに対して加算され、右側エッジからの値は、すべてのエッジに関して生成された有効な重み付けファクタから引き算される。左右および上下のエッジ属性は、図３に示される。
【００４０】
図３から分かるように、左下または右上に分類されるエッジは、それぞれ垂直ステップ要素により近似され、右下または左上に分類されるエッジは、それぞれ水平ステップ要素により近似される。ここでいう水平および垂直ステップについては、後に詳細に説明する。
【００４１】
まず、本発明の望ましい実施例に係る第１メイン処理工程、すなわち図１Ａのブロック１０４に関して概要を説明したエッジ計算について、図４を参照しながら説明する。まずブロック１２８では、エッジ計算に必要なデータ、すなわちブロック１３０および１３２に供給されるべきフットプリントデータｖi inおよび拡大オフセットｒを受け取る。エッジ計算によってフットプリントの近似されたエリアが生成されるが、この時、拡大オフセットｒで示され、ｒ≧０である正のフィルタ拡大（positive filter enlargement)が含まれる。オリジナルフットプリントの各エッジは、サイズｒを持つオフセットを加算することで、中心から遠ざけられる。これらのエッジは、オフセットエッジとして以下に言及される。この「爆発("explosion") 」の結果、フットプリントのオリジナル頂点の間に、水平および垂直のギャップが発生する。本発明の方法でこれまでに記載した実施例に従えば、水平ギャップは無視することが可能であるが、他方、垂直ギャップに関しては、垂直エッジ、いわゆる頂点エッジにより単純に満たされる。
【００４２】
エッジ属性および頂点属性の計算を簡素化し、要求されるハードウエアでの実現に関してその計算を容易にするために、反時計周りの回転方向を持つフットプリントは、ブロック１３４において常に時計周りの回転を持つフットプリントへと変換される（図２参照）。この変換は、下記の計算方法に従って実行される。
【００４３】
【数１】
2006502475.tif 000003
ｖ0,1,2,3 in＝ブロック１２８で受け取られた入力データ。
【００４４】
上記の計算方法に従って受け取られたフットプリントデータｖ0,1,2,3 は、ブロック１３６に供給され、後続の処理に使用される。
【００４５】
ブロック１３６に供給されたフットプリント情報ｖi に基づき、下記の計算式に従ってエッジベクトルが生成される。
【００４６】
【数２】
2006502475.tif 000004
【００４７】
加えて、エッジに係るいわゆる配向ベクトルａi が計算され、対応するエッジを左／右および上／下のエッジに分類する。図３に示された分類に基づいて、各エッジについてそれがどの領域に位置するかが決定される。以下に記載する表の中で、エッジ配向ベクトルａi の２つの要素の値、すなわち要素ａi,x およびａi,y の値が、エッジベクトルｓi の要素ｓi,x およびｓi,y の異なる符号のために示される。
【００４８】
【表１】
2006502475.tif 000005
【００４９】
この表の中で＋１という値は、図３で描かれたテクスチャスペースにおいて、ｘ軸に沿っては右側であり、ｙ軸方向には下側への配向を示す。また、−１という値は、ｘ軸方向には左側の配向を示し、ｙ軸方向には上側への配向を示す。水平エッジおよび垂直エッジは、これら＋１あるいは−１という値と関連付けられる。「０エッジ」（一点において変形されたエッジ）は、ベクトルａ＝０および値ａ＝０という結果になる。
【００５０】
表の中で示された配向は拡大オフセットの方向を決定するために使用される。フットプリントは、４つのシフトされたエッジｖi ',ｓi ' の上に、有限拡大パラメータｒのサイズに依存して拡張される。現実には、各オリジナル頂点は、拡大パラメータｒによって図５Ａ，図５Ｂに示される方法でオフセットされる。その結果、オフセットエッジｓi ' が生じる。全てのエッジは左から右へサンプリングされるべきであるから、下側にあると決定されたエッジに係る始点は終点に、終点は始点に交換されなければならない。この計算は以下に記載の計算式に従って実行される。
【００５１】
【数３】
2006502475.tif 000006
【００５２】
この計算は、図４Ａのブロック１３８の中で実行され、その結果、ブロック１４０に供給されるエッジベクトルｓi ' が生成される。この情報を基にして、オフセットエッジベクトルｓi ' がブロック１４２ａの中で計算され、ブロック１４２ｂに供給され、ブロック１５０で出力される。また、このエッジベクトルｓi ' を基にして、エッジの配向がブロック１４２で計算され、ブロック１４４（図４Ｂ参照）でさらなる処理を受けるために出力される。ブロック１４６では、ブロック１４４に供給された配向ａi ' と、ブロック１３６に供給されたフットプリントデータｖi と、ブロック１３２に供給された拡大パラメータｒとに基づいて、オフセットエッジに係るオフセットが計算され、その結果、オフセットエッジ情報ｖi ' がブロック１４８に供給され、ブロック１５０で出力される。
【００５３】
フットプリントの各頂点のオフセットに伴って生じたギャップは、垂直頂点エッジによって処理される。これらエッジのオフセットは、０よりも大きい長さをもつ２個の隣接するエッジの配向に依存する。これらのエッジはｊ± によって表され、頂点指数ｉに依存し、以下に示す計算式に従うものである。
【００５４】
【数４】
2006502475.tif 000007
【００５５】
修正された配向ベクトルａi * と、ギャップフラグθi * とが、この指数置換(index translation)を用いて以下のように生成される。
【００５６】
【表２】
2006502475.tif 000008
【００５７】
ｘは、後続の計算に影響がなく、よっていずれの値でも可能な値を示す。頂点エッジに係る基本点および拡大ギャップのサイズが、以下に記載する計算式に従って生み出される。
【００５８】
【数５】
2006502475.tif 000009
【００５９】
ａi ＝０という条件は、ｇi * ＝０という結果を生じさせるが、この場合に確かなことは、２個の隣接し、且つ同一の属性を持つ同一の頂点を備えた１つの「０エッジ」からは、後続のテクセル重み付けに係る１つのギャップエッジしか生じないということである。上述の計算工程は、まずブロック１５２で実行される。ここでは、ブロック１４４に供給された配向ａi ' と拡大パラメータｒとに基づいて、頂点エッジの配向が計算され、ブロック１５４に供給される。さらに、同じくブロック１５２での計算により生成されていた拡大ギャップｇi * が、ブロック１５６に供給される。
【００６０】
ブロック１５４に供給された配向ａi * に基づいて、頂点エッジｖi * のオフセットがブロック１５６で計算され、ブロック１５８に供給される。ブロック１５０では、オフセット頂点エッジｖi * と、配向ａi * と、拡大ギャップｇi * と、ブロック１４４に供給された配向ａi ' と、オフセットエッジベクトルｓi ' と、オフセット頂点情報ｖi ' とが出力される。これは図１Ａのブロック１０６および１０８に示されたのと同様である。
【００６１】
次に、出力された属性ｖi ' と、ｓi ' と、ａi ' とを基にして、図１Ａではブロック１１０で示されたオフセットエッジの処理が、第２メイン処理工程として実行される。オフセットエッジの処理のために、それらはいくつかのステップにより近似される。このステップの数は、オフセットエッジのサイズに依存する。ここで指摘しておくが、ａi ＝０という値を持つ０エッジは除かれる。さらに、１つのステップの幅と高さは、ともに１．０という値を超えてはならない。まず、各エッジのステップの数ｎstepが決定されなければならない。これは、以下の計算式に従って実行される。
【００６２】
【数６】
2006502475.tif 000010
【００６３】
上記の式２）で示された計算方法は、次の理由で望ましいと言える。すなわち、これはエッジ長さの最大値Ｅmax についてハードウエアコード化された値によって著しく簡素にされることが可能であり、さらに、後続のステップベクトルｑi の計算内では、複雑な除数を簡素なオフセット操作で置き換えることができるからである。このステップベクトルｑi は、次の式に従って計算される。
【００６４】
【数７】
2006502475.tif 000011
【００６５】
全ての頂点について同一の重み付け方法を得るために、２つの異なるステップ方法が必要となる。右上のエッジおよび左下のエッジに関しては、ステップの必要条件θi'は０、すなわち水平である。左上のステップおよび右下のステップに関しては、ステップの配向θi ' は１、すなわち垂直である。水平ステップとは、ある階段関数と対応するエッジとの、ステップベクトルｑi の末部における水平の交差点と呼ぶことができる。垂直ステップとは、図６から分かるように、その階段関数と各エッジとの、ステップベクトルｑi の末部における垂直の交差点に関すると言える。スライスとは、テクセルの重み付けを決定するために使用される垂直ステップ要素である。以下の計算式がステップ配向θi ' のために適用される。
【００６６】
【数８】
2006502475.tif 000012
【００６７】
１に等しいステップ配向θi ' を持つエッジはステップの数ｎi,stepよりも１個多い数の垂直要素を持つことから、追加的な重み付けサイクルが必要となるであろう。これは、同一のｘ位置を持つ隣接する頂点エッジの処理に置き換えることができ、これは、本発明においてはステップ拡張と呼ばれており、後に図９を参照しながら詳細に説明する。
【００６８】
後に図８を参照しながら詳細に説明するが、スライス処理ループが各エッジについて供給され、各サイクル毎に１個のスライスを処理する。各サイクルは１または２個のテクセルに重み付けすることが可能であり、この場合、処理ループのための入力パラメータはｖ' ，ｑ，ｎstep, ａ' y と、θ' である。ループはデータ構造を生成し、それを以下の表に記載された対応するデータで満たす。
【００６９】
【表３】
2006502475.tif 000013
【００７０】
図７には、上記の表に記載された項目が図式的に示される。望ましい実施例において、ｋおよびｌ のための最高の値は、エッジ長さの最大値Ｅmax に依存し、その結果、次の式が成り立つ。
【００７１】
【数９】
2006502475.tif 000014
【００７２】
次の計算式は、ステップ拡張に適応する。
【００７３】
【数１０】
2006502475.tif 000015
【００７４】
上述のスライス処理ループの望ましい実施例について、図８を参照しながら詳細に説明する。
図８のスライス処理ループについての以下の説明に関し、注意すべきことは、指数ｉは全ての値に表れることになるので、明示することは省略されているということである。１つのエッジに対する処理のみを説明するが、図８を参照しながら説明するこの方法は、通常、全てのエッジについて並行して実行される。図８では、指数ｌは、スライスを処理するためにあるエッジによりヒットされた（図７参照）テクセルの数をカウントするものである。
【００７５】
図９内のベクトルｕi,0 で示されるように、初期部分１６０の中で第１スライスのための座標が初期化される。ブロック１６２では、始点ｕx,ｕyoおよび高さｄｕy （図１０Ｂ参照）の座標が決定される。この時、第１スライスの実際の座標は、当該エッジの開始点すなわち対応するスタート頂点(starting vertex) ｖにより示される開始点と、θ' あるいはａy で示されるエッジの配向とに依存している。つまり、実際の始点を決定するために、まずブロック１６４においては、ブロック１６２で考慮され且つ決定された点に関して水平ステップ配向θ' が有るか否かが決定される。もしステップ配向が水平であれば、本発明の方法はブロック１６６に進み、ここでは始点の座標ｕx がｑx /2という値で増大させられる。ブロック１６２で決定された他の座標またはパラメータには変化はない。
【００７６】
もしブロック１６４で決定されたステップ配向が水平ではなく垂直配向であれば、本発明の方法はブロック１６８に進み、ここで当該エッジの配向ａy がまず決定される。もし、当該エッジが上側のエッジであれば、処理工程はブロック１７０に進み、ここでは座標値ｕx がｑx という値により増大させられる。また、座標値ｕyoも、ｑx /2という値によりブロック１７０内で増大させられる。
【００７７】
もし、ブロック１６８内で当該エッジが下側エッジであると決定された場合には、本発明の方法はブロック１７２に進み、ここでは高さｄｕy が半減させられる。
【００７８】
このようにして決定された当該スライスのためのスタート座標は、ブロック１７４に送られる。ブロック１７４では、使用される指数はまず初期化されるが、ｋはテクセル列をカウントし、ｌは全体的なテクセルをカウントし、ｎはスライスをカウントする。第１テクセル列の座標ｙ’ofs はスライス始点の下のテクセルに対応し、ブロック１７４の第２列では、スタート座標値ｕyoに関し、いわゆる床関数(floor function)が示されている。これはｕyoの値から−∞方向へ出発した次の整数値を表している。
【００７９】
スライスを処理する際に関係する列の数および関係するテクセルの数は、第１列において１から初期化され、これはｙ’num ＝ｘ’num [0] ＝１で示す通りである。加えて、第１列の開始点のｘ座標ｘ’ofs は、スライス位置ｕx に等しくなるであろうし、この場合も、ｕx の値から−∞方向へ出発した次の整数値が選択されるであろう。さらに、第１列および第１テクセルのための重み付け情報ｗ’ofs は、値０に初期化される。
【００８０】
ブロック１７４で初期化された値を基にして、本発明の方法は次に図８Ｂに示されるブロック１７６に進む。ブロック１７６では、この時考慮されるｘの位置が、後の計算によってどれだけ変化してきたのかが検出される。ブロック１７４から出発して、ブロック１７６に示される２個のパラメータが同一か否かが決定され、もし同一である場合には、ブロック１７８に進み、ここでは第１テクセルが重み付けされる。ブロック１７８では、スライスによりヒットされた第１テクセルのための重み付けが決定されるが、この値はブロック１７８内に記載された計算式に従って決定される。ブロック１７８では、まずスライスの終点ｕy1と次に適切な整数テクセル座標ｙ1 int が、−∞方向におけるｕy1の次の整数値に基づいて計算される。次に、図７に示されるように、垂直セクションから導き出されるテクセルフラクションｗx が計算される。さらに、水平セクションから導き出されるフラクションｗy0が計算される。図８Ｂのブロック１７８中に示されたｗyoの分類は、スライスがどちらの方向を持つか（図１０Ｂ参照）という点と、１個または２個のテクセルがヒットされたか否かという点とを考慮に入れるものである。
【００８１】
このようにして決定された水平セクションおよび垂直セクションのフラクションに関する情報に基づき、ブロック１７８では、ｗx にｗy0を掛算した値によって現存の値を増大させることで、当該テクセルに対するスライスの重み付けの寄与ｗ' tex [l] が決定される。最後に、右テクセルに送られる重み付けの寄与ｗ’propが、ｗ’propの現存の値を値ｗy0により増大させることで決定される。
【００８２】
もしブロック１７６でｘ位置が後の計算によって変化したと決定される場合には、すなわち同一列内の新たなテクセルが考慮される場合には、指数ｌおよびこの列の中で既に処理されたテクセルの数ｘ’num は最初増大している。さらに、以前のテクセルの重み付けの寄与が伝えられるように、新たなテクセルのための重み付けｗ' tex [l] がｗ’prop[k] に設定される。
【００８３】
次に本発明の方法はブロック１８０から１７８に進み、ここでは上述と同じ方法で新たなテクセルの同様な重み付けが実行される。
【００８４】
もし１つのテクセルの重み付け計算がブロック１７８で完成している場合には、本発明の方法はブロック１８２に進み、ここではスライスの終点が始点とは別の列にあるか否かが決定される。もし別の列にあると決定された場合には、本発明の方法はブロック１８４に進み、ここでは新たな列内の新たなテクセルが決定される。すなわち、考慮されるべき次の列への処理工程ジャンプが実行され、その結果、列の数ｙ’num と、列の指数ｋと、テクセル指数ｌとが最初増大させられる。さらに、テクセルの数ｘ’num [ ｋ] が再初期化されて１の値となり、この新たな列内の第１テクセルの座標ｘ’ofs が決定される。加えて、ｗtex アレー(array) に関する指数が決定され、この中でこの列の第１テクセルのための重み付けが記憶される。
【００８５】
次に本発明の方法はブロック１８４から１８６に進み、ここでは当該スライスによりヒットされた第２テクセルのための重み付けが計算される。この計算はブロック１７８と同様であるので、ブロック１７８の説明を参照されたい。
【００８６】
ブロック１８６の次は、本発明の方法はブロック１８８に進み、ここでは当該スライスのｘ位置が記憶され、次のスライスに届くように指数ｎが増大させられる。ブロック１９０では、値ｎが値ｎstepよりも小さいか否かが判定され、もし値ｎの方が小さくなければ、最後のスライスが処理されたと決定される。この場合、この方法は終了となる。しかし、もし最後のスライスがまだ処理されていないと決定される場合には、本発明の方法はブロック１９２に進み、ここでは次のスライスのための座標が計算される。この際、座標ｕx は値ｑx により増大させられ、座標ｕyoも、値ｑx で増大させられる。ｄｕy の扱いで記載された分類は、図９に示されたエッジｓ2 およびｓ3 に関する場合を考慮に入れたものであり、これに従えば、最後のスライスは半分の長さしか持っていないことになる。エッジｓ0 およびｓ1 においては、これは既に第１スライスであり、ブロック１６０でのスタート時の初期化の中で既に考慮に入れられていたものである。
【００８７】
ブロック１９２で決定されたデータを基にして、始点のテクセル座標がブロック１９４で再計算され、このスライスのための新たな重み付け計算が実行される。
【００８８】
図１Ａのブロック１１４に示された頂点エッジ処理工程について、以下に詳細に説明する。そこでは、垂直ギャップを満たすために追加された垂直エッジが扱われる。
【００８９】
基本的に、頂点エッジのための重み付けテーブルは、オフセットエッジのために使用されたパラメータと同様のパラメータを提供する。しかし、これらの重み付けテーブルを導入することは、比較的複雑でない。なぜなら、当該エッジの配向は常に垂直となるために、可能性のある列の数はかなり少なくなり、重み付けおよび列の指数には相違がなくなるからである。
【００９０】
以下のテーブルは頂点エッジのための重み付けを示す。
【表４】
2006502475.tif 000016
【００９１】
図１０Ａに示すように、拡大ギャップｇおよびステップ拡張ｐは、頂点エッジの総合的な長さに追加され、その結果、頂点エッジの座標（始点と終点）は、次に記載する計算式に従って計算される。
【００９２】
【数１１】
2006502475.tif 000017
【００９３】
エッジ長さはｇ＋ｐ＝２・ｒ＋ｐであり、ｒおよびｐの最大値＝０．５である。０．５・１．０＋２・０．５＝１．５という最大値が、上述の計算式から導かれるが、この時、テクセル列の数は３に限定される。頂点エッジｉに関する、ｋ＝０，１，２の場合のテーブル要素は、以下の計算式に従って決定される。
【００９４】
【数１２】
2006502475.tif 000018
【００９５】
図１Ｂのブロック１１６と１１８の中で、対応するエッジ、すなわち頂点エッジおよびオフセットエッジのための全ての重み付けテーブルが決定され供給された後に、図１Ｂのブロック１２０における最終カラー計算が実行される。図１に記載の最後に残る処理工程、すなわちブロック１２０の例を、以下に詳細に説明する。このカラー計算は、主に、各オフセットエッジおよび各垂直エッジのために上述の方法で生成され記憶されたデータ構造にアクセスするループで構成される。さらに詳しく言えば、このカラー計算においては、拡大フットプリントによって接触されるかカバーされる全てのテクセルが参照され、これらの各テクセルについて重み付けが決定される。テクセル（ｘ，ｙ）に関し、重み付けファクタｗΣ[ ０，０，１．０] が、重み付けテーブルから読み出された全てのエッジ寄与(edge contributions)の合計に対して計算される。結果として生じるピクセルカラーを計算するための処理は、詳しくは、そのピクセルの周辺領域、例えばテクスチャメモリへのアクセスの構成等に依存する。このカラー計算処理の関数の例は、以下に図１１を参照しながらより詳細に説明する。この図１１に示された処理工程は、関係する全てのテクセルを処理するために複数回に渡って通過されるループである。図１１に関して注意すべきは、指数ｉは、４個のエッジのために示された計算の並行処理を表すものであるという点である。等記号の両側にｉが現れる等式は、４個の等式、すなわち各エッジ（ｉ＝０，１，２，３）について等式を表している。関数引数(function argument) としてｉと示された値は、４個の引数を示す。指数ｌは、１つの列内で１つのエッジによりヒットされたテクセルを示す。
【００９６】
図１１Ａのブロック２００内では、全てのカラー要素と、全てのテクセル重み付けの合計とが、まず０に初期化される。カラー要素は一般的にＲＧＢ（三原色）要素とα要素とであり、等式は抽象要素(abstract component)であるcolor pix のみの計算を示す。カラー要素と全てのテクセル重み付けの合計とを初期化した後に、ブロック２０２では最下のテクセル列と最上のテクセル列とが決定される。この時、上記２つのテーブル内の値によって示された全てのテクセルの、最小のｙ座標と最大のｙ座標とが計算されなければならない。まず、各１つのエッジの最小値および最大値（ｙ' i,min およびｙ’i, max）が上述のオフセットエッジに関するテーブルから決定される。示された等式によって、８個の等式が表されている。つまり、各４つのエッジに係るｙmin およびｙmax を決定するための等式である。アロケーションの中で示された分類は、テーブルがｙ座標を増加させる方向か、あるいは減少させる方向に設定されているかという点を考慮に入れたものである。
【００９７】
さらに、ブロック２０２では、各１つのエッジの最小値および最大値、すなわちｙ* i, minおよびｙ* i,max が、上述の頂点エッジ処理に関するテーブルを基にして決定される。その後、頂点エッジとオフセットエッジのために決定された最小値から、８個の最小値ｙmin が決定され、頂点エッジとオフセットエッジのために決定された最大値から、８個の最大値ｙmax が決定される。最下のテクセル列と最上のテクセル列との決定がこのようにして実行された後、本発明の方法は、次にブロック２０４に進み、ここでは、テクセル列を表すループ値ｙが値ｙmin に初期化される。このループはｙmin からｙmax までｙの値のために通過される。
【００９８】
次に、上記のテーブルに示された値は、その中に含まれるオフセットを補償するためにブロック２０６で使用される。つまり、オフセットエッジに適用するループパラメータｋ’i がまず決定される。対応するテーブルの値は、テクセル列０の整数ｙ座標（ｙofs ）から始まり、ｘnum 列のための値しか含まない。このオフセットはループ値から引き算され、オフセットエッジのためのテーブル内で列指数ｋ’i を得る。同様に、ブロック２０２に関して上述したように、このオフセットエッジのためのテーブルが増加オーダーかあるいは減少オーダーのｙ座標を含んでいるかという点が考慮に入れられなければならない。
【００９９】
次に、このような方法で、頂点エッジテーブルから得られる値に対応するオフセットの移動が実行され、列指数ｋ* i が得られる。さらに、当該エッジが上記ｙよりも上か否か、すなわちテクセルの重みに寄与するか否かを示すフラグΔ’i およびΔ* i の値が決定される。
【０１００】
その後、当該列の中で最も左側のテクセルと最も右側のテクセルがブロック２０８で決定される。当該列について、全てのテクセルの最小ｘ座標および最大ｘ座標がここで決定される。これらはテーブルにより重み付けされたものであり、つまりは、オフセットエッジに係るｘ座標ｘ’i, minおよびｘ’i, maxと、頂点エッジに係る座標ｘ* i, minおよびｘ* i,max が決定される。寄与しないエッジ、すなわちブロック２０６で決定されたフラグΔ’i またはΔ* i が０であるエッジは、対応する最小および最大ｘ値の決定においては考慮されない。これは、形式的には±∞の寄与として表現されている。
【０１０１】
次に、オフセットエッジと頂点エッジのために決定された最小ｘ座標から、最小値ｘ minが選択される。また、オフセットエッジと頂点エッジのために決定された最大ｘ座標から、最大値ｘ maxが選択される。その後、本発明の方法はブロック２１０（図１１Ｂ）に進む。ブロック２１０においては、当該列内の１つのテクセルを示すループ値ｘが最小値ｘ minに初期化される。このループ値はｘ minからｘmax まで変化する。次にブロック２１２に進み、ここではオフセットエッジに対する重み付け寄与が、与えられたテーブルから読み出される。ここでは、座標ｘ，ｙにあるテクセルを重み付けするために、８個のエッジ全ての寄与が決定される。
【０１０２】
まず、対応するエッジに係る列内のテクセルの指数ｌi が考慮される（図７参照）。次に、オフセットエッジに係る重み付け寄与ｗ’i が考慮されるが、この時、各エッジについて４つの場合が分類されなければならない。テクセルはエッジより上でも下でもよく、この場合、値Δ’i は０となり、関係するテクセルは寄与がゼロとなる。加えて、テクセルはエッジの左でも良く、この場合、指数ｌは０よりも小さくなり、全体的な重み付けに対するこのテクセルの寄与はゼロとなる。しかし、もしテクセルがエッジの右にあれば、すなわちｌ≧ｘ numであれば、対応するテーブルの中で準備された値ｗ’propが選択される。もしテクセルがエッジの上に載っていれば、そのテーブルの中で準備された値ｗ’tex が選択される。ファクタａ’i,x は、右エッジに係る結果を無効にする。
【０１０３】
ブロック２１２と平行して、ブロック２１４では、頂点エッジの重み付け寄与に関するテーブルの読み出しが対応して実行され、ここでは対応する寄与ｗ* i が決定される。ブロック２１２と同様に、４つの場合が分類されなければならない。第１の場合には、テクセルはエッジより上か下であり、この場合、対応する値Δ* i は０となる。この場合、全体的な重み付けに対するこのテクセルの寄与はゼロとなる。もしテクセルがエッジの左にあれば、この場合も重み付けに対する寄与はゼロとなる。もしテクセルがエッジの右にあれば、すなわちｘ＞ｘ* i,ofs,であれば、頂点エッジに関するテーブルで決定された値ｗ* propが選択される。もしテクセルがエッジの上に載っていれば、対応する値ｗ* tex が選択される。この場合、右エッジに係る結果もまたファクタａ* i,x により無効にされる。
【０１０４】
ブロック２１２と２１４においてオフセットエッジと頂点エッジに係る重み付けに対するそれぞれの寄与が決定された後に、本発明の方法はブロック２１６に進み、ここでは全ての寄与が合計され、テクセルカラーが重み付けされる。まず、ブロック２１２と２１４で計算された８個の寄与が合計され、重み付けの合計値ｗが得られる。このように得られた重み付け値ｗは、次にテクセルのカラー要素color tex(x,y)により掛算され、ピクセルカラーcolor pix に対して加算される。後のカラー正規化(normalization) のために、テクセル重み付け全体の合計ｗsum が実行される。明確に言えば、値ｗsum がブロック２１６で決定された値ｗによって増大させられる。
【０１０５】
最後に、本発明の方法はブロック２１８に進み、ここでは一方ではループ値ｘが１によって増大させられ、他方では値ｘが最大値ｘ maxを超えるか否かが判断される。もし値ｘが最大値ｘ maxを超えないと判断される場合には、当該列の中に処理されるべきテクセルがまだ存在し、本発明の方法は、ブロック２１８からブロック２１２および２１４へと戻る。その結果、１つのテクセル分だけ右へのジャンプが起こり、このテクセルに関して対応する修正が実行される。もしブロック２１８で、１つの列の全てのテクセルが処理されたと決定された場合には、本発明の方法はブロック２２０に進み、ここではループ値ｙが１により増大させられ、さらに、このループ値ｙが最大値ｙ maxを超えるか否かが判断される。もし値ｙが最大値ｙ maxを超えないと判断される場合には、次の列へのジャンプが実行され、本発明の方法は、ブロック２０６へと戻る。もし最後のテクセル列が処理されたと決定された場合には、本発明の方法はブロック２２０からブロック２２２に進む。ブロック２２２ではピクセルカラーcolor pix の実際のカラーが決定されるが、ここでは、重み付けが存在する場合には、すなわち値ｗsum が０でなく、少なくとも１個のテクセルが当該エッジに接触されていると表れている場合には、カラーピクセル値は合計された重み付け値ｗsum を基にして正規化され、color pix/sum が決定される。いわゆる重み付け０の場合、すなわちフットプリントが１点に縮退し、拡大オフセットが値０を持つ場合、フットプリントの頂点０の下のテクセルのカラーは、変化しないままで引き継がれる（次のフィルタ）。これはつまり、点座標に最も近いテクセルが選択されて１．０という一定の重み付けと関連付けられるということである。
【０１０６】
本発明の上述の望ましい実施例は４辺を持つフットプリントに基づいて説明されてきたが、本発明の方法はどのようなフットプリントに対しても広く適応させることができる。
【０１０７】
さらにここで指摘すべきことは、本発明は、最初にフットプリントの拡大が実行される上述の実施例に限られるものではないということである。もしそのような拡大が望まれない場合には、つまり例えば、受取るフットプリントに拡大オフセットが全く関連付けられない場合には、本発明の方法は、オリジナルフットプリントに関して作用し、エッジの下のテクセルを見つけるための本発明の工程により、結果的にはその処理が加速されたということになる。
【図面の簡単な説明】
【０１０８】
【図１Ａ】本発明の望ましい実施例の前半のフローチャートである。
【図１Ｂ】本発明の望ましい実施例の後半のフローチャートである。
【図２】テクスチャスペースにおけるフットプリントを示す。
【図３】フットプリントのエッジ配向の決定方法を示す。
【図４Ａ】本発明の実施例に従うエッジ計算方法の前半を示すフローチャートである。
【図４Ｂ】本発明の実施例に従うエッジ計算方法の後半を示すフローチャートである。
【図５】フットプリントのフィルタ拡大に係る２つの実施例を示す図である。
【図６】階段関数によるフットプリントのエッジの近似を示す図である。
【図７】テクセルグリッド内でシフトされたエッジを関連付けられた重み付けテーブルエントリと共に示す図である。
【図８Ａ】本発明の実施例に従うシフトされたエッジの処理方法の前半を示すフローチャートである。
【図８Ｂ】本発明の実施例に従うシフトされたエッジの処理方法の後半を示すフローチャートである。
【図９】フットプリントおよび拡大フットプリントをステップ拡張と共に示す図である。
【図１０】（Ａ）および（Ｂ）はそれぞれ頂点エッジおよびスライス（垂直ステップ要素）の表記法を説明する図である。
【図１１Ａ】ピクセルのカラー値を計算する方法を示す前半のフローチャートである。
【図１１Ｂ】ピクセルのカラー値を計算する方法を示す後半のフローチャートである。
【図１Ａ】
2006502475.tif 000019
【図１Ｂ】
2006502475.tif 000020
【図２】
2006502475.tif 000021
【図３】
2006502475.tif 000022
【図４Ａ】
2006502475.tif 000023
【図４Ｂ】
2006502475.tif 000024
【図５】
2006502475.tif 000025
【図６】
2006502475.tif 000026
【図７】
2006502475.tif 000027
【図８Ａ】
2006502475.tif 000028
【図８Ｂ】
2006502475.tif 000029
【図９】
2006502475.tif 000030
【図１０】
2006502475.tif 000031
【図１１Ａ】
2006502475.tif 000032
【図１１Ｂ】
2006502475.tif 000033
【手続補正書】
【提出日】平成16年8月17日(2004.8.17)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００６０
【補正方法】変更
【補正の内容】
【００６０】
ブロック１５４に送られた配向ａi * に基づいて、頂点エッジｖi * のオフセットがブロック１５７で計算され、ブロック１５８に送られる。ブロック１５０では、オフセット頂点エッジｖi * と、配向ａi * と、拡大ギャップｇi * と、ブロック１４４から送られた配向ａi ' と、オフセットエッジベクトルｓi ' と、オフセット頂点情報ｖi ' とが出力される。これは図１Ａのブロック１０６および１０８に示されたのと同様である。
【手続補正２】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2006502475.tif 000034
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図４Ｂ
【補正方法】変更
【補正の内容】
【図４Ｂ】
2006502475.tif 000035
【手続補正４】
【補正対象書類名】図面
【補正対象項目名】図８Ｂ
【補正方法】変更
【補正の内容】
【図８Ｂ】
2006502475.tif 000036
【手続補正５】
【補正対象書類名】図面
【補正対象項目名】図１１Ｂ
【補正方法】変更
【補正の内容】
【図１１Ｂ】
2006502475.tif 000037
【国際調査報告】
2006502475.tif 000038
2006502475.tif 000039
2006502475.tif 000040
2006502475.tif 000041
2006502475.tif 000042
2006502475.tif 000043