【手続補正書】
【提出日】平成18年9月11日(2006.9.11)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】  ラスター画素イメージを形成するべく、グラフィックオブジェクトを処理する方法であって、該処理は、ラスタライズされた表示順における現在のスキャンラインのための対応する辺レコードを評価することにより、前記グラフィックオブジェクトの辺間の交差順序を判断し、後続のスキャンラインのための各辺に関する辺交差値を決定するものであって、該処理は前記辺レコードの処理の間に、
限られた数の処理された辺レコードを順序付けされていない第１バッファに保持し、順序付け可能な処理済の辺レコードが前記第１バッファに加えられたのに応じて、順序付け可能な前記辺レコードを漸進的に順次に第２バッファへ送るステップと、
順序付けできない処理済の辺を、第３バッファにおいて並べるために該第３バッファへ送るステップと、
前記第２及び第３バッファからの辺レコードを選択的に処理し、後続のスキャンラインに対する並べられた交差を決定するステップとを備えることを特徴とする方法。
【請求項２】  前記第３バッファにおける前記辺レコードの順序付けは、前記第３バッファへ前記辺を追加する際になされることを特徴とする請求項１に記載の方法。
【請求項３】  前記辺レコードは、前記第３バッファへ挿入され、ソートされることを特徴とする請求項２に記載の方法。
【請求項４】  前記第３バッファ内の辺は、前記現在のスキャンラインの処理の完了時に順序付けられることを特徴とする請求項３に記載の方法。
【請求項５】  前記第２及び第３バッファは結合されて、前記選択的処理に用いられる第４バッファのそれぞれの部分を形成し、それにより、前記部分からの順序付けられた辺が漸進的に比較され、前記処理に対する次の変を決定することを特徴とする請求項２に記載の方法。
【請求項６】  前記現在hのスキャンラインの処理の完了時において、前記第２及び第３バッファの内容と前記第４バッファの内容をスワップすることを特徴とする請求項５に記載の方法。
【請求項７】  前記第２、第３、第４バッファの各々は、そのスタート位置及びエンド位置のポインタを含み、前記現在のスキャンラインの終了時に、バッファをスワップするために該ポインタをスワップすることを特徴とする請求項６に記載の方法。
【請求項８】  前記第１バッファは、メモリに形成された辺プールを備え、前記方法は、前記メモリに形成された複数のアクティブ辺レコードから、前記現在のスキャンラインのためのアクティブ辺値を決定し、前記アクティブ辺値の各々に対し、対応する辺レコードを前記辺プールへ送るステップを更に備えることを特徴とする請求項１に記載の方法。
【請求項９】  前記第２バッファは、前記メモリに形成される現在辺出力リストを備え、前記方法は、前記アクティブ辺値の各々に対して、前記辺プール内のレコードと前記辺レコードの対応する辺レコードを調べ、該辺レコードの順序付けられたものを前記現在辺リストに送るステップを更に備えることを特徴とする請求項８に記載の方法。
【請求項１０】  前記第３バッファは、前記メモリ内に形成された現在スピル出力リストを備え、前記方法は、前記現在のスピルリストへ順次に前記辺プールからの前記現在辺リストに並べることのできない辺レコードを送るステップを更に備えることを特徴とする請求項９に記載の方法。
【請求項１１】  前記方法は、前記スキャンラインの処理の完了時において、前記後続のスキャンラインの処理のために前記出力リストの対応する一つへ順次に前記辺プールからの辺レコードをフラッシュするステップと、ここで、このフラッシュに際しては前記出力リストは現在辺入力リスト及び現在辺入力スピルリストとしてそれぞれ割り当てられるものであり、該後続のスキャンラインに対する前記アクティブ辺値を決定するために前記入力リストから順次に辺レコードを前記アクティブ辺レコードの対応する一つに転送するステップとを備えることを特徴とする請求項１０に記載の方法。
【請求項１２】  グラフィックオブジェクト描画システムにおいて、ラスター画素イメージを形成するべくグラフィックオブジェクトを処理する方法であって、該処理は、前記グラフィックオブジェクトの辺と前記ラスター画素イメージの現在のスキャンラインとの交差の順序を決定する第１処理を備え、
前記システムが、
現在のスキャンラインと後続のスキャンラインの各々に関する複数の辺レコードと、該辺レコードの各々は少なくとも対応するスキャンライン上の対応する辺の画素位置の値を保持し、前記現在の辺レコード及び後続の辺レコードの各々は、少なくとも主部分とスピル部分に分割され、少なくとも前記現在の辺レコードの主部分はラスター画素順に並べられ、
少なくとも一つの現在のアクティブ辺レコードと、
スピルアクティブ辺レコードと、
制限された所定数の辺レコードを含むプールとを備え、
前記方法が、
（ａ）前記現在の辺レコードの前記主部分及びスピル部分の各々からの第１の辺レコードを対応するアクティブ辺レコードに送るステップと、
（ｂ）前記ラスタ画素順において最も低い値を有するアクティブ辺レコードを決定し、現在の辺の値及びレコードとしてその値とレコードを出力するために、前記アクティブ辺レコードの値を比較するステップと、
（ｃ）前記現在の辺レコードを、前記後続のスキャンラインのための対応する辺の値で更新するステップと、
（ｄ）更新された辺の値を前記プール内の辺の値と比較するステップと、ここで、更新された辺の値が前記プール内の辺の値より小さい場合に、
（ｄａ）前記更新された現在の辺レコードが後続の辺レコードのスピル部分へ送られ、さもなければ、
（ｄｂ）（ｄｂａ）最小の辺値を有する辺レコードが前記プールから、前記後続の辺レコードの主部分の次のレコードへ送られ、
（ｄｂｂ）前記更新された辺レコードは、前記サブステップ（ｄｂａ）で殻になった前記プールのレコードへ送られ、
（ｄｃ）更なる辺レコードが、現在の辺レコードの対応する部分から更新された辺レコードによって空にされたアクティブ辺レコードへ送られ、
（ｅ）前記プール内の前記レコードの各々が占領されるまで、ステップ（ｂ）乃至（ｄ）を繰り返すステップと、これによって前記プールの最小の辺値レコードが前記後続の辺レコードの前記主部分へ送られ、
（ｆ）前記現在のレコードの全てのレコードが更新されるまで前記ステップ（ｂ）乃至（ｅ）を繰り返し、次いで、前記プールからのレコードを順次に前記後続のレコードの前記主部分内の次のレコードへフラッシュするステップと、
（ｇ）前記レコードを、前記後続のレコードにおける前記スピル部分において、ラスタ画素順にソートするステップと、
（ｈ）前記後続の辺レコードを前記現在の辺レコードへ送るステップと、
（ｉ）前記ラスタ画素イメージの更なるスキャンラインの各々に関して、前記ステップ（ａ）乃至（ｈ）を繰り返すステップとを備えることを特徴とする方法。
【請求項１３】  ラスター画素イメージを形成するべく、グラフィックオブジェクトを処理する装置であって、該処理は、ラスタライズされた表示順における現在のスキャンラインのための対応する辺レコードを評価することにより、前記グラフィックオブジェクトの辺間の交差順序を判断し、後続のスキャンラインのための各辺に関する辺交差値を決定するものであって、
未整列の第１バッファ、第２バッファ及び第３バッファを有するメモリと、
限られた数の処理された辺レコードを順序付けされていない前記第１バッファに保持し、順序付け可能な処理済の辺レコードが前記第１バッファに加えられのに応じて順序付け可能な前記辺レコードを漸進的に順次に前記第２バッファへ送り、順序付けできない処理済の辺を前記第３バッファにおいて並べるために該第３バッファへ送り、前記第２及び第３バッファからの辺レコードを選択的に処理し、後続のスキャンラインに対する並べられた交差を決定するプロセッサとを備えることを特徴とする装置。
【請求項１４】  前記第１バッファは、メモリに形成された辺プールを備え、前記プロセッサは、前記メモリに形成された複数のアクティブ辺レコードから、前記現在のスキャンラインのためのアクティブ辺値を決定し、前記アクティブ辺値の各々に対し、対応する辺レコードを前記辺プールへ送るように構成されることを特徴とする請求項１３に記載の装置。
【請求項１５】  前記第２バッファは、前記メモリに形成される現在辺出力リストを備え、前記プロセッサは、前記アクティブ辺値の各々に対して、前記辺プール内のレコードと前記辺レコードの対応する辺レコードを調べ、該辺レコードの順序付けられたものを前記現在辺リストに送るように構成されることを特徴とする請求項１４に記載の装置。
【請求項１６】  前記第３バッファは、前記メモリ内に形成された現在スピル出力リストを備え、前記プロセッサは、前記現在のスピルリストへ順次に前記辺プールからの前記現在辺リストに並べることのできない辺レコードを送るように構成されることを特徴とする請求項１５に記載の装置。
【請求項１７】  前記プロセッサは、前記スキャンラインの処理の完了時において、前記後続のスキャンラインの処理のために前記出力リストの対応する一つへ順次に前記辺プールからの辺レコードをフラッシュし、ここで、このフラッシュに際しては前記出力リストは現在辺入力リスト及び現在辺入力スピルリストとしてそれぞれ割り当てられるものであり、該後続のスキャンラインに対する前記アクティブ辺値を決定するために前記入力リストから順次に辺レコードを前記アクティブ辺レコードの対応する一つに転送するように構成されることを特徴とする請求項１６に記載の装置。
【請求項１８】  ラスター画素イメージを形成するべく、グラフィックオブジェクトを処理する装置であって、該処理は、ラスタライズされた表示順における現在のスキャンラインのための対応する辺レコードを評価することにより、前記グラフィックオブジェクトの辺間の交差順序を判断し、後続のスキャンラインのための各辺に関する辺交差値を決定するものであって、
限られた数の処理された辺レコードを順序付けされていない第１バッファに保持し、順序付け可能な処理済の辺レコードが前記第１バッファに加えられたのに応じて、順序付け可能な前記辺レコードを漸進的に順次に第２バッファへ送る手段と、
順序付けできない処理済の辺を、第３バッファにおいて並べるために該第３バッファへ送る手段と、
前記第２及び第３バッファからの辺レコードを選択的に処理し、後続のスキャンラインに対する並べられた交差を決定する手段とを備えることを特徴とする装置。
【請求項１９】  ラスター画素イメージを形成するべくグラフィックオブジェクトを処理するグラフィックオブジェクト描画システムの一部を形成する装置であって、該処理は、前記グラフィックオブジェクトの辺と前記ラスター画素イメージの現在のスキャンラインとの交差の順序を決定する第１処理を備え、
前記装置が、
現在のスキャンラインと後続のスキャンラインの各々に関する複数の辺レコードと、該辺レコードの各々は少なくとも対応するスキャンライン上の対応する辺の画素位置の値を保持し、前記現在の辺レコード及び後続の辺レコードの各々は、少なくとも主部分とスピル部分に分割され、少なくとも前記現在の辺レコードの主部分はラスター画素順に並べられ、
少なくとも一つの現在のアクティブ辺レコードと、
スピルアクティブ辺レコードと、
制限された所定数の辺レコードを含むプールと、
辺レコード処理のために、
（ａ）前記現在の辺レコードの前記主部分及びスピル部分の各々からの第１の辺レコードを対応するアクティブ辺レコードに送り、
（ｂ）前記ラスタ画素順において最も低い値を有するアクティブ辺レコードを決定し、現在の辺の値及びレコードとしてその値とレコードを出力するために、前記アクティブ辺レコードの値を比較し、
（ｃ）前記現在の辺レコードを、前記後続のスキャンラインのための対応する辺の値で更新し、
（ｄ）更新された辺の値を前記プール内の辺のああ痛いと比較し、ここで、更新された辺の値が前記プール内の辺の値より小さい場合に、
（ｄａ）前記更新された現在の辺レコードが後続の辺レコードのスピル部分へ送られ、さもなければ、
（ｄｂ）（ｄｂａ）最小の辺値を有する辺レコードが前記プールから、前記後続の辺レコードの主部分の次のレコードへ送られ、
（ｄｂｂ）前記更新された辺レコードは、前記サブステップ（ｄｂａ）で殻になった前記プールのレコードへ送られ、
（ｄｃ）更なる辺レコードが、現在の辺レコードの対応する部分から更新された辺レコードによって空にされたアクティブ辺レコードへ送られ、
（ｅ）前記プール内の前記レコードの各々が占領されるまで、ステップ（ｂ）乃至（ｄ）を繰り返し、これによって前記プールの最小の辺値レコードが前記後続の辺レコードの前記主部分へ送られ、
（ｆ）前記現在のレコードの全てのレコードが更新されるまで前記ステップ（ｂ）乃至（ｅ）を繰り返し、次いで、前記プールからのレコードを順次に前記後続のレコードの前記主部分内の次のレコードへフラッシュし、
（ｇ）前記レコードを、前記後続のレコードにおける前記スピル部分において、ラスタ画素順にソートし、
（ｈ）前記後続の辺レコードを前記現在の辺レコードへ送り、
（ｉ）前記ラスタ画素イメージの更なるスキャンラインの各々に関して、前記ステップ（ａ）乃至（ｈ）を繰り返す構成を有することを特徴とする装置。
【請求項２０】  ラスター画素イメージを形成するべく、グラフィックオブジェクトを処理する装置のためのプログラムを格納するコンピュータ可読媒体であって、該処理は、ラスタライズされた表示順における現在のスキャンラインのための対応する辺レコードを評価することにより、前記グラフィックオブジェクトの辺間の交差順序を判断し、後続のスキャンラインのための各辺に関する辺交差値を決定するものであって、該プログラムが、
限られた数の処理された辺レコードを順序付けされていない第１バッファに保持し、順序付け可能な処理済の辺レコードが前記第１バッファに加えられのに応じて、順序付け可能な前記辺レコードを漸進的に順次に第２バッファへ送る保持ステップのコードと、
順序付けできない処理済の辺を、第３バッファにおいて並べるために該第３バッファへ送る転送ステップのコードと、
前記第２及び第３バッファからの辺レコードを選択的に処理し、後続のスキャンラインに対する並べられた交差を決定する処理ステップのコードとを備えることを特徴とするコンピュータ可読媒体。
【請求項２１】  グラフィックオブジェクト描画システムにおいて、ラスター画素イメージを形成するべくグラフィックオブジェクトを処理するためのコンピュータプログラム製品を備えたコンピュータ可読媒体であって、該処理は、前記グラフィックオブジェクトの辺と前記ラスター画素イメージの現在のスキャンラインとの交差の順序を決定する第１処理を備え、該コンピュータ製品は、
現在のスキャンラインと後続のスキャンラインの各々に関する複数の辺レコードと、該辺レコードの各々は少なくとも対応するスキャンライン上の対応する辺の画素位置の値を保持し、前記現在の辺レコード及び後続の辺レコードの各々は、少なくとも主部分とスピル部分に分割され、少なくとも前記現在の辺レコードの主部分はラスター画素順に並べられ、
少なくとも一つの現在のアクティブ辺レコードと、
スピルアクティブ辺レコードと、
制限された所定数の辺レコードを含むプールと関連し、
前記第１処理が、
（ａ）前記現在の辺レコードの前記主部分及びスピル部分の各々からの第１の辺レコードを対応するアクティブ辺レコードに送るステップと、
（ｂ）前記ラスタ画素順において最も低い値を有するアクティブ辺レコードを決定し、現在の辺の値及びレコードとしてその値とレコードを出力するために、前記アクティブ辺レコードの値を比較するステップと、
（ｃ）前記現在の辺レコードを、前記後続のスキャンラインのための対応する辺の値で更新するステップと、
（ｄ）更新された辺の値を前記プール内の辺のああ痛いと比較するステップと、ここで、更新された辺の値が前記プール内の辺の値より小さい場合に、
（ｄａ）前記更新された現在の辺レコードが後続の辺レコードのスピル部分へ送られ、さもなければ、
（ｄｂ）（ｄｂａ）最小の辺値を有する辺レコードが前記プールから、前記後続の辺レコードの主部分の次のレコードへ送られ、
（ｄｂｂ）前記更新された辺レコードは、前記サブステップ（ｄｂａ）で殻になった前記プールのレコードへ送られ、
（ｄｃ）更なる辺レコードが、現在の辺レコードの対応する部分から更新された辺レコードによって空にされたアクティブ辺レコードへ送られ、
（ｅ）前記プール内の前記レコードの各々が占領されるまで、ステップ（ｂ）乃至（ｄ）を繰り返すステップと、これによって前記プールの最小の辺値レコードが前記後続の辺レコードの前記主部分へ送られ、
（ｆ）前記現在のレコードの全てのレコードが更新されるまで前記ステップ（ｂ）乃至  （ｅ）を繰り返し、次いで、前記プールからのレコードを順次に前記後続のレコードの前記主部分内の次のレコードへフラッシュするステップと、
（ｇ）前記レコードを、前記後続のレコードにおける前記スピル部分において、ラスタ画素順にソートするステップと、
（ｈ）前記後続の辺レコードを前記現在の辺レコードへ送るステップと、
（ｉ）前記ラスタ画素イメージの更なるスキャンラインの各々に関して、前記ステップ（ａ）乃至（ｈ）を繰り返すステップとを実行するように構成されてなることを特徴とするコンピュータ可読媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
本発明の一つの態様によれば、ラスター画素イメージを形成するべく、グラフィックオブジェクトを処理する方法であって、該処理は、ラスタライズされた表示順における現在のスキャンラインのための対応する辺レコードを評価することにより、前記グラフィックオブジェクトの辺間の交差順序を判断し、後続のスキャンラインのための各辺に関する辺交差値を決定するものであって、該処理は前記辺レコードの処理の間に、
限られた数の処理された辺レコードを順序付けされていない第１バッファに保持し、順序付け可能な処理済の辺レコードが前記第１バッファに加えられたのに応じて、順序付け可能な前記辺レコードを漸進的に順次に第２バッファへ送るステップと、
順序付けできない処理済の辺を、第３バッファにおいて並べるために該第３バッファへ送るステップと、
前記第２及び第３バッファからの辺レコードを選択的に処理し、後続のスキャンラインに対する並べられた交差を決定するステップとを備える方法が開示される。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
また、本発明の他の態様によれば、グラフィックオブジェクト描画システムにおいて、ラスター画素イメージを形成するべくグラフィックオブジェクトを処理する方法であって、該処理は、前記グラフィックオブジェクトの辺と前記ラスター画素イメージの現在のスキャンラインとの交差の順序を決定する第１処理を備え、
前記システムが、
現在のスキャンラインと後続のスキャンラインの各々に関する複数の辺レコードと、該辺レコードの各々は少なくとも対応するスキャンライン上の対応する辺の画素位置の値を保持し、前記現在の辺レコード及び後続の辺レコードの各々は、少なくとも主部分とスピル部分に分割され、少なくとも前記現在の辺レコードの主部分はラスター画素順に並べられ、
少なくとも一つの現在のアクティブ辺レコードと、
スピルアクティブ辺レコードと、
制限された所定数の辺レコードを含むプールとを備え、
前記方法が、
（ａ）前記現在の辺レコードの前記主部分及びスピル部分の各々からの第１の辺レコードを対応するアクティブ辺レコードに送るステップと、
（ｂ）前記ラスタ画素順において最も低い値を有するアクティブ辺レコードを決定し、現在の辺の値及びレコードとしてその値とレコードを出力するために、前記アクティブ辺レコードの値を比較するステップと、
（ｃ）前記現在の辺レコードを、前記後続のスキャンラインのための対応する辺の値で更新するステップと、
（ｄ）更新された辺の値を前記プール内の辺の値と比較するステップと、ここで、更新された辺の値が前記プール内の辺の値より小さい場合に、
（ｄａ）前記更新された現在の辺レコードが後続の辺レコードのスピル部分へ送られ、さもなければ、
（ｄｂ）（ｄｂａ）最小の辺値を有する辺レコードが前記プールから、前記後続の辺レコードの主部分の次のレコードへ送られ、
（ｄｂｂ）前記更新された辺レコードは、前記サブステップ（ｄｂａ）で殻になった前記プールのレコードへ送られ、
（ｄｃ）更なる辺レコードが、現在の辺レコードの対応する部分から更新された辺レコードによって空にされたアクティブ辺レコードへ送られ、
（ｅ）前記プール内の前記レコードの各々が占領されるまで、ステップ（ｂ）乃至（ｄ）を繰り返すステップと、これによって前記プールの最小の辺値レコードが前記後続の辺レコードの前記主部分へ送られ、
（ｆ）前記現在のレコードの全てのレコードが更新されるまで前記ステップ（ｂ）乃至（ｅ）を繰り返し、次いで、前記プールからのレコードを順次に前記後続のレコードの前記主部分内の次のレコードへフラッシュするステップと、
（ｇ）前記レコードを、前記後続のレコードにおける前記スピル部分において、ラスタ画素順にソートするステップと、
（ｈ）前記後続の辺レコードを前記現在の辺レコードへ送るステップと、
（ｉ）前記ラスタ画素イメージの更なるスキャンラインの各々に関して、前記ステップ（ａ）乃至（ｈ）を繰り返すステップとを備える方法が開示される。