(57)【特許請求の範囲】
【請求項１】
プロセッサにより実行される所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成し、形成された出力パスをメモリに格納するパス処理方法であって、
前記入力パスの各々は少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記方法は、
（ａ）前記２つ以上の入力パスの各々を対応する単純輪郭パスに変換するステップであって、前記単純輪郭パスの各々は前記オリジナルセグメント又はその部分のうちの１つ以上から構成されるステップと、
（ｂ）前記所定の集合演算に基づいて単純輪郭パスと別の単純輪郭パスとを交差させ、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択するステップと、
（ｃ）前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成するステップとを含み、
前記ステップ（ｂ）は前記対応する単純輪郭パス間の各交点に対して、
（ｂ１）前記交点を分類するサブステップと、
（ｂ２）前記分類された点を前記点に対応する前記オリジナルセグメントのいずれかに挿入するサブステップと、
（ｂ３）前記分類及び挿入に基づいて追加のセグメント及び共直線性のあるエッジを識別するサブステップと、
を有することを特徴とするパス処理方法。
【請求項２】
前記ステップ（ａ）は前記入力パスの各々に対して、
（ａ１）前記オリジナルセグメント又はその部分の各々が少なくとも１つの対応するバンドを有するように前記入力パスが定義される空間を複数のバンドに分割するサブステップと、
（ａ２）前記バンドの各々を検査し、対応するバンド内の前記オリジナルセグメントの位置及び／又は方向に基づいて前記バンドの各々の内部に含まれる前記オリジナルセグメント又はその部分の各々を分類するサブステップと、
（ａ３）前記検査に基づいて前記バンドの各々の内部に更なるセグメントを作成するサブステップと、
（ａ４）対応するバンド内に含まれる前記オリジナルセグメント又はその部分の各々及び／又は前記更なるセグメントの位置及び分類に基づいて、前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントのうちの少なくとも１つを境界線セグメントになるように割り当てるサブステップと、
（ａ５）前記境界線セグメントのうちの少なくとも１つを結合して少なくとも１つのエッジを形成し、対応する入力パスに対して前記単純輪郭パスのうちの少なくとも１つを生成するサブステップと、
を有することを特徴とする請求項１に記載のパス処理方法。
【請求項３】
前記分類された点は前記出力パスの一部として選択されることを特徴とする請求項１に記載のパス処理方法。
【請求項４】
前記ステップ（ｂ）は、
（ｂ４）前記識別された追加のセグメント及び共直線性のあるエッジに基づいて、前記出力パスにおいて使用するために前記オリジナルセグメントのうちの１つ以上を選択するサブステップを更に含むことを特徴とする請求項１に記載のパス処理方法。
【請求項５】
前記共直線性のあるエッジは前記エッジの方向及び前記所定の集合演算に基づいて識別されることを特徴とする請求項１乃至４のいずれか１項に記載のパス処理方法。
【請求項６】
前記ステップ（ｂ）は交点ごとに前記対応する単純輪郭パスを交差させ、前記出力パスにおいて使用するために前記オリジナルセグメントのうちの１つ以上を選択するサブステップを更に含むことを特徴とする請求項４に記載のパス処理方法。
【請求項７】
前記オリジナルセグメントのうちの１つ以上は所定の集合演算に基づいて選択されることを特徴とする請求項６に記載のパス処理方法。
【請求項８】
前記ステップ（ｃ）は前記出力パスを形成するために前記入力パスと関連付けられた前記単純輪郭パスの各々に対して、前記サブステップ（ａ１）から（ａ５）を繰り返すサブステップを含むことを特徴とする請求項２に記載のパス処理方法。
【請求項９】
前記サブステップ（ｂ１）において、前記点が、純粋な交点、共直線性のある点の開始、または共直線性のある点の終了のうちの１つとして分類されることを特徴とする請求項１に記載のパス処理方法。
【請求項１０】
前記対応する単純輪郭パス及び前記出力パスは、先に定義されたように単純であるとして分類されることを特徴とする請求項１に記載のパス処理方法。
【請求項１１】
前記入力パスは複数の塗りつぶし規則のうちの１つに従って構成され、前記出力パスは前記複数の塗りつぶし規則の各々に従って構成されることを特徴とする請求項１に記載のパス処理方法。
【請求項１２】
前記塗りつぶし規則は少なくとも奇偶ワインディング塗りつぶし規則及びノンゼロワインディング塗りつぶし規則を含むことを特徴とする請求項１１に記載のパス処理方法。
【請求項１３】
前記バンドの各々は独立して処理されることを特徴とする請求項２に記載のパス処理方法。
【請求項１４】
バンド内に含まれる前記オリジナルセグメント及び前記更なるセグメントの各々は、左側から順に処理されることを特徴とする請求項１３に記載のパス処理方法。
【請求項１５】
前記オリジナルセグメント又はその部分は、現在処理中のバンド内に存在し、格納されることを特徴とする請求項１４に記載のパス処理方法。
【請求項１６】
前記バンドラインの各々が前記入力パスにより定義される少なくとも１つのエッジの少なくとも１つの頂点と交差するように前記バンドの各々は複数のバンドラインにより定義されることを特徴とする請求項２に記載のパス処理方法。
【請求項１７】
繰り返されるバンドラインは破棄されることを特徴とする請求項１６に記載のパス処理方法。
【請求項１８】
プロセッサにより実行される所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成し、形成された出力パスをメモリに格納するパス処理方法であって、
前記入力パスの各々は少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記方法は、
（ａ）前記２つ以上の入力パスの各々を対応する単純輪郭パスに変換するステップであって、前記単純輪郭パスの各々は前記オリジナルセグメント又はその部分のうちの１つ以上から構成されるステップと、
（ｂ）前記所定の集合演算に基づいて単純輪郭パスと別の単純輪郭パスと交差に基づき、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択するステップと、
（ｃ）前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成するステップとを含み、
前記ステップ（ａ）は前記入力パスの各々に対して、
（ａ１）前記オリジナルセグメント又はその部分の各々が少なくとも１つの対応するバンドを有するように前記入力パスが定義される空間を複数のバンドに分割するサブステップと、
（ａ２）前記バンドの各々を検査し、対応するバンド内の前記オリジナルセグメントの位置及び／又は方向に基づいて前記バンドの各々の内部に含まれる前記オリジナルセグメント又はその部分の各々を分類するサブステップと、
（ａ３）前記検査に基づいて前記バンドの各々の内部に更なるセグメントを作成するサブステップと、
（ａ４）対応するバンド内に含まれる前記オリジナルセグメント又はその部分の各々及び／又は前記更なるセグメントの位置及び分類に基づいて、前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントのうちの少なくとも１つを境界線セグメントになるように割り当てるサブステップと、
（ａ５）前記境界線セグメントのうちの少なくとも１つを結合して少なくとも１つのエッジを形成し、対応する入力パスに対して前記単純輪郭パスのうちの少なくとも１つを生成するサブステップとを含み、
前記サブステップ（ａ４）における前記オリジナルセグメント及び／又は前記更なるセグメントの、境界線セグメントとしての割当ては、バンド内に含まれる前記オリジナルセグメント及び／又は前記更なるセグメントの交差に依存することを特徴とするパス処理方法。
【請求項１９】
プロセッサにより実行される所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成し、形成される出力パスをメモリに格納するパス処理方法であって、
前記入力パスの各々は少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記方法は、
（ａ）前記２つ以上の入力パスの各々を対応する単純輪郭パスに変換するステップであって、前記単純輪郭パスの各々は前記オリジナルセグメント又はその部分のうちの１つ以上から構成されるステップと、
（ｂ）前記所定の集合演算に基づいて単純輪郭パスと別の単純輪郭パスとの交差に基づき、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択するステップと、
（ｃ）前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成するステップとを含み、
前記ステップ（ａ）は前記入力パスの各々に対して、
（ａ１）前記オリジナルセグメント又はその部分の各々が少なくとも１つの対応するバンドを有するように前記入力パスが定義される空間を複数のバンドに分割するサブステップと、
（ａ２）前記バンドの各々を検査し、対応するバンド内の前記オリジナルセグメントの位置及び／又は方向に基づいて前記バンドの各々の内部に含まれる前記オリジナルセグメント又はその部分の各々を分類するサブステップと、
（ａ３）前記検査に基づいて前記バンドの各々の内部に更なるセグメントを作成するサブステップと、
（ａ４）対応するバンド内に含まれる前記オリジナルセグメント又はその部分の各々及び／又は前記更なるセグメントの位置及び分類に基づいて、前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントのうちの少なくとも１つを境界線セグメントになるように割り当てるサブステップと、
（ａ５）前記境界線セグメントのうちの少なくとも１つを結合して少なくとも１つのエッジを形成し、対応する入力パスに対して前記単純輪郭パスのうちの少なくとも１つを生成するサブステップとを含み、
前記サブステップ（ａ４）における前記オリジナルセグメント及び／又は前記更なるセグメントの、境界線セグメントとしての割当ては、特定のオリジナルセグメント及び／又は更なるセグメントの方向に依存することを特徴とするパス処理方法。
【請求項２０】
前記オリジナルセグメントの各々は前記バンドラインに対して静止したままであることを特徴とする請求項１６に記載のパス処理方法。
【請求項２１】
前記分類は水平セグメント及び垂直セグメントを含むことを特徴とする請求項２に記載のパス処理方法。
【請求項２２】
プロセッサにより実行される所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成し、形成される出力パスをメモリに格納するパス処理方法であって、
前記入力パスの各々は少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記方法は、
（ａ）前記２つ以上の入力パスの各々を対応する単純輪郭パスに変換するステップであって、前記単純輪郭パスの各々は前記オリジナルセグメント又はその部分のうちの１つ以上から構成されるステップと、
（ｂ）前記所定の集合演算に基づいて前記対応する単純輪郭パスの交差に基づき、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択するステップと、
（ｃ）前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成するステップとを含み、
前記ステップ（ａ）は前記入力パスの各々に対して、
（ａ１）前記オリジナルセグメント又はその部分の各々が少なくとも１つの対応するバンドを有するように前記入力パスが定義される空間を複数のバンドに分割するサブステップと、
（ａ２）前記バンドの各々を検査し、対応するバンド内の前記オリジナルセグメントの位置及び／又は方向に基づいて前記バンドの各々の内部に含まれる前記オリジナルセグメント又はその部分の各々を分類するサブステップと、
（ａ３）前記検査に基づいて前記バンドの各々の内部に更なるセグメントを作成するサブステップと、
（ａ４）対応するバンド内に含まれる前記オリジナルセグメント又はその部分の各々及び／又は前記更なるセグメントの位置及び分類に基づいて、前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントのうちの少なくとも１つを境界線セグメントになるように割り当てるサブステップと、
（ａ５）前記境界線セグメントのうちの少なくとも１つを結合して少なくとも１つのエッジを形成し、対応する入力パスに対して前記単純輪郭パスのうちの少なくとも１つを生成するサブステップとを含み、
前記サブステップ（ａ２）における特定のオリジナルセグメント又は更なるセグメントの分類は、前記特定のオリジナルセグメント又は更なるセグメント中の点に依存することを特徴とするパス処理方法。
【請求項２３】
前記特定のオリジナルセグメント又は更なるセグメントは、前記バンドラインのうちの少なくとも１つに対する点の位置に基づいて、先に定義されたように、複合点又はローカル最小点として分類されることを特徴とする請求項２２に記載のパス処理方法。
【請求項２４】
２つ以上のオリジナルセグメントが特定の点に結合する場合、前記オリジナルセグメントは分割されることを特徴とする請求項２に記載のパス処理方法。
【請求項２５】
バンドライン上の特定の点で開始／終了するオリジナルセグメントが分割されることを特徴とする請求項１６に記載のパス処理方法。
【請求項２６】
前記所定の集合演算は、論理積演算、和演算、及び差演算のうちの１つであることを特徴とする請求項１乃至２５のいずれか１項に記載のパス処理方法。
【請求項２７】
前記対応する単純輪郭パス及び前記出力パスは、単純であるとして分類されることを特徴とする請求項１に記載のパス処理方法。
【請求項２８】
所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成するための装置であって、
前記入力パスの各々は、少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記装置は、
前記２つ以上の入力パスの各々を対応する単純輪郭パスに変換する手段であって、前記単純輪郭パスの各々は前記オリジナルセグメント又はその部分のうちの１つ以上から構成される変換手段と、
前記所定の集合演算に基づいて単純輪郭パスと別の単純輪郭パスとを交差させ、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択する交差手段と、
前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成する結合手段とを備え、
各交点を分類する分類手段と、
前記分類された点を前記点に対応する前記オリジナルセグメントのいずれかに挿入する挿入手段と、
前記分類及び挿入に基づいて追加のセグメント及び共直線性のあるエッジを識別する識別手段とを更に具備することを特徴とする装置。
【請求項２９】
前記オリジナルセグメント又はその部分の各々が少なくとも１つの対応するバンドを有するように、前記入力パスが定義される空間を複数のバンドに分割する分割手段と、
前記バンドの各々を検査し、対応するバンド内の前記オリジナルセグメントの位置及び／又は方向に基づいて前記バンドの各々の内部に含まれる前記オリジナルセグメント又はその部分の各々を分類する検査手段と、
前記検査に基づいて前記バンドの各々の内部に更なるセグメントを作成するセグメント作成手段と、
対応するバンド内に含まれる前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントの各々の位置及び分類に基づいて、前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントのうちの少なくとも１つを境界線セグメントになるように割り当てる割当て手段とを更に具備し、
前記結合手段は前記境界線セグメントのうちの少なくとも１つを結合して少なくとも１つのエッジを形成し、対応する入力パスに対して前記単純輪郭パスのうちの少なくとも１つを生成することを特徴とする請求項２８に記載の装置。
【請求項３０】
前記分類された点は前記出力パスの一部として選択されることを特徴とする請求項２８に記載の装置。
【請求項３１】
前記識別された追加のセグメント及び共直線性のあるエッジに基づいて、前記出力パスにおいて使用するために前記オリジナルセグメントのうちの１つ以上を選択する選択手段を更に具備することを特徴とする請求項２８に記載の装置。
【請求項３２】
前記共直線性のあるエッジは前記エッジの方向及び前記所定の集合演算に基づいて識別されることを特徴とする請求項２９乃至３１のいずれか１項に記載の装置。
【請求項３３】
交点ごとに前記対応する単純輪郭パスを交差させ、前記出力パスにおいて使用するために前記オリジナルセグメントのうちの１つ以上を選択する交差手段を更に具備することを特徴とする請求項３１に記載の装置。
【請求項３４】
前記オリジナルセグメントのうちの１つ以上は所定の集合演算に基づいて選択されることを特徴とする請求項３３に記載の装置。
【請求項３５】
前記点が、純粋な交点、共直線性のある点の開始、または共直線性のある点の終了のうちの１つとして分類されることを特徴とする請求項２８に記載の装置。
【請求項３６】
所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成するためのプログラムであって、
前記入力パスの各々は少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記プログラムは、
（ａ）前記２つ以上の入力パスの各々を対応する単純輪郭パスに変換するためのコードであって、前記単純輪郭パスの各々は前記オリジナルセグメント又はその部分のうちの１つ以上から構成されるコードと、
（ｂ）前記所定の集合演算に基づいて単純輪郭パスと別の単純輪郭パスとを交差させ、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択するためのコードと、
（ｃ）前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成するためのコードとを含み、
前記ステップ（ｂ）は、
前記対応する単純輪郭パス間の各交点に対して、
前記対応する単純輪郭パス間の各交点を分類するためのコードと、
前記分類された点を前記点に対応する前記オリジナルセグメントのいずれかに挿入するためのコードと、
前記分類及び挿入に基づいて追加のセグメント及び共直線性のあるエッジを識別するためのコードとを含むサブステップを有することを特徴とするプログラム。
【請求項３７】
前記オリジナルセグメント又はその部分の各々が少なくとも１つの対応するバンドを有するように前記入力パスが定義される空間を複数のバンドに分割するためのコードと、
前記バンドの各々を検査し、対応するバンド内の前記オリジナルセグメントの位置及び／又は方向に基づいて前記バンドの各々の内部に含まれる前記オリジナルセグメント又はその部分の各々を分類するためのコードと、
前記検査に基づいて前記バンドの各々の内部に更なるセグメントを作成するためのコードと、
対応するバンド内に含まれる前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントの各々の位置及び分類に基づいて、前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントのうちの少なくとも１つを境界線セグメントになるように割り当てるためのコードと、
前記境界線セグメントのうちの少なくとも１つを結合して少なくとも１つのエッジを形成し、対応する入力パスに対して前記単純輪郭パスのうちの少なくとも１つを生成するためのコードと、
を更に含むことを特徴とする請求項３６に記載のプログラム。
【請求項３８】
前記分類された点は前記出力パスの一部として選択されることを特徴とする請求項３６に記載のプログラム。
【請求項３９】
前記識別された追加のセグメント及び共直線性のあるエッジに基づいて、前記出力パスにおいて使用するために前記オリジナルセグメントのうちの１つ以上を選択するためのコードを更に含むことを特徴とする請求項３６に記載のプログラム。
【請求項４０】
プロセッサにより実行される所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成し、形成された出力パスをメモリに格納する装置であって、
前記入力パスの各々は少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記装置は、
前記２つ以上の入力パスの各々を、前記オリジナルセグメント又はその部分のうちの１つ以上から構成される対応する単純輪郭パスに変換する手段と、
前記所定の集合演算に基づいて単純輪郭パスと別の単純輪郭パスとを交差させ、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択する選択手段と、
前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成する手段とを含み、
前記選択手段は前記対応する単純輪郭パス間の各交点に対して、
前記交点を分類す手段と、
前記分類された点を前記点に対応する前記オリジナルセグメントのいずれかに挿入する手段と、
前記分類及び挿入に基づいて追加のセグメント及び共直線性のあるエッジを識別する手段と、
を有することを特徴とする装置。
【請求項４１】
プロセッサにより実行される所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成し、形成された出力パスをメモリに格納する装置であって、
前記入力パスの各々は少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記装置は、
前記２つ以上の入力パスの各々を、前記オリジナルセグメント又はその部分のうちの１つ以上から構成される対応する単純輪郭パスに変換する変換手段と、
前記所定の集合演算に基づいて単純輪郭パスと別の単純輪郭パスと交差に基づき、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択する選択手段と、
前記選択手段により選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成する手段とを含み、
前記変換手段は前記入力パスの各々に対して、
前記オリジナルセグメント又はその部分の各々が少なくとも１つの対応するバンドを有するように前記入力パスが定義される空間を複数のバンドに分割する手段と、
前記バンドの各々を検査し、対応するバンド内の前記オリジナルセグメントの位置及び／又は方向に基づいて前記バンドの各々の内部に含まれる前記オリジナルセグメント又はその部分の各々を分類する手段と、
前記検査に基づいて前記バンドの各々の内部に更なるセグメントを作成する手段と、
対応するバンド内に含まれる前記オリジナルセグメント又はその部分の各々及び／又は前記更なるセグメントの位置及び分類に基づいて、前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントのうちの少なくとも１つを境界線セグメントになるように割り当てる手段と、
前記境界線セグメントのうちの少なくとも１つを結合して少なくとも１つのエッジを形成し、対応する入力パスに対して前記単純輪郭パスのうちの少なくとも１つを生成する手段とを含み、
前記割り当てる手段における前記オリジナルセグメント及び／又は前記更なるセグメントの、境界線セグメントとしての割当ては、バンド内に含まれる前記オリジナルセグメント及び／又は前記更なるセグメントの交差に依存することを特徴とする装置。
【請求項４２】
プロセッサにより実行される所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成し、形成される出力パスをメモリに格納する装置であって、
前記入力パスの各々は少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記装置は、
前記２つ以上の入力パスの各々を、前記オリジナルセグメント又はその部分のうちの１つ以上から構成される対応する単純輪郭パスに変換する変換手段と、
前記所定の集合演算に基づいて単純輪郭パスと別の単純輪郭パスとの交差に基づき、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択する手段と、
前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成する手段とを含み、
前記変換手段は前記入力パスの各々に対して、
前記オリジナルセグメント又はその部分の各々が少なくとも１つの対応するバンドを有するように前記入力パスが定義される空間を複数のバンドに分割する手段と、
前記バンドの各々を検査し、対応するバンド内の前記オリジナルセグメントの位置及び／又は方向に基づいて前記バンドの各々の内部に含まれる前記オリジナルセグメント又はその部分の各々を分類する手段と、
前記検査に基づいて前記バンドの各々の内部に更なるセグメントを作成する手段と、
対応するバンド内に含まれる前記オリジナルセグメント又はその部分の各々及び／又は前記更なるセグメントの位置及び分類に基づいて、前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントのうちの少なくとも１つを境界線セグメントになるように割り当てる手段と、
前記境界線セグメントのうちの少なくとも１つを結合して少なくとも１つのエッジを形成し、対応する入力パスに対して前記単純輪郭パスのうちの少なくとも１つを生成する手段とを含み、
前記割り当てる手段における前記オリジナルセグメント及び／又は前記更なるセグメントの、境界線セグメントとしての割当ては、特定のオリジナルセグメント及び／又は更なるセグメントの方向に依存することを特徴とする装置。
【請求項４３】
プロセッサにより実行される所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成し、形成される出力パスをメモリに格納する装置であって、
前記入力パスの各々は少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記装置は、
前記２つ以上の入力パスの各々を、前記オリジナルセグメント又はその部分のうちの１つ以上から構成される対応する単純輪郭パスに変換する変換手段と、
前記所定の集合演算に基づいて前記対応する単純輪郭パスの交差に基づき、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択する手段と、
前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成する手段とを含み、
前記変換手段は前記入力パスの各々に対して、
前記オリジナルセグメント又はその部分の各々が少なくとも１つの対応するバンドを有するように前記入力パスが定義される空間を複数のバンドに分割する手段と、
前記バンドの各々を検査し、対応するバンド内の前記オリジナルセグメントの位置及び／又は方向に基づいて前記バンドの各々の内部に含まれる前記オリジナルセグメント又はその部分の各々を分類する分類手段と、
前記検査に基づいて前記バンドの各々の内部に更なるセグメントを作成する手段と、
対応するバンド内に含まれる前記オリジナルセグメント又はその部分の各々及び／又は前記更なるセグメントの位置及び分類に基づいて、前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントのうちの少なくとも１つを境界線セグメントになるように割り当てる手段と、
前記境界線セグメントのうちの少なくとも１つを結合して少なくとも１つのエッジを形成し、対応する入力パスに対して前記単純輪郭パスのうちの少なくとも１つを生成する手段とを含み、
前記分類手段による特定のオリジナルセグメント又は更なるセグメントの分類は、前記特定のオリジナルセグメント又は更なるセグメント中の点に依存することを特徴とする装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的に、コンピュータグラフィックに関し、特に、所定の集合演算に基づいて２つ以上の入力パスからの出力パスを判定する方法及び装置に関する。また、本発明は、所定の集合演算に基づいて２つ以上の入力パスから出力パスを判定するためのコンピュータプログラムを記録したコンピュータ可読な媒体を含むコンピュータプログラム製品に関する。
【０００２】
【従来の技術】
ラスタベースグラフィカルシステムでは、ポリゴンは、通常、複数の点、すなわち、頂点により定義される。この頂点はポリゴンを形成する複数本のセグメントにより相互に接続される。パスは複数のエッジから成るので、実質的には一般のポリゴンセットを具備する。各パスは関連する塗りつぶし規則を有し、この塗りつぶし規則によってレンダリングの際にパスの各エッジがどのように塗りつぶされるかが判定される。塗りつぶし規則は、一般的に、パスに対するワインディングカウントに基づいている。ワインディングカウントとは、直線がパスを貫通するときに交差する線分の本数をカウントする値である。
【０００３】
集合演算は、一般に、グラフィカルオブジェクトのその後のダウンストリーム処理を最適化するために、前処理ステップとしてグラフィカルオブジェクトに対して使用される。集合演算は、２つ以上のポリゴンにレンダリング又は三角化を施す前にこれらのポリゴンを結合するのに使用することができる。例えば、集合演算は、一般的に、グラフィカルオブジェクトのクリッピング中に使用される。クリッピングは、グラフィカルオブジェクトの最終表現に含まれるグラフィカルオブジェクトの領域又は部分を選択するプロセスである。また、クリッピングは、対象のグラフィカルオブジェクトの不要な領域又は部分を破棄するのに使用することもできる。破棄部分はグラフィカルオブジェクトの最終表現には含まれない。一般的に、グラフィカルオブジェクトはポリゴンセットにより表現されるが、クリッピングは論理積演算、和演算、及び差演算などの集合演算を使用してグラフィカルオブジェクトに対して実行される。
【０００４】
ポリゴンに対して集合演算を行なう幾つかの既知のパス処理方法がある。これらの方法の大半は、特定の集合演算（論理積など）に基づいており、単純集合演算を使用して正方形又は直線などの単純な形状のパスに対してのみ最適化される。しかし、既知のパス処理方法の中には、種々の集合演算を行なうように構成されるものもある。種々の集合演算を行なう方法は、複雑なデータ構造を必要とし、通常、入力ポリゴンが単純・凸状のような一定の特性に従うことを想定している。更に、これらの既知のパス処理方法の多くは、セグメントの始点／終点が他のセグメント上にある場合及び／又は共直線セグメントのケースなどの縮退した場合を扱うことができない。
【０００５】
更に、「走査変換」及び「三角化」などの既存のパス処理方法の多くは、パスの複雑度及び塗りつぶし規則において制約を受けており、特定の塗りつぶし規則及び複雑度においてのみパスを扱うことができる。このようなパス処理方法は、入力パスが比較的単純であるときにのみ最適な処理速度を達成することが可能であり、常に、単純輪郭パスを生成する訳ではない。
【０００６】
【発明が解決しようとする課題】
本発明の目的は、既存の構成の１つ以上の欠点をほぼ克服するか、あるいは、少なくとも改善することである。
【０００７】
【課題を解決するための手段】
本発明の一態様によれば、
プロセッサにより実行される所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成し、形成された出力パスをメモリに格納するパス処理方法であって、
前記入力パスの各々は少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記方法は、
（ａ）前記２つ以上の入力パスの各々を対応する単純輪郭パスに変換するステップであって、前記単純輪郭パスの各々は前記オリジナルセグメント又はその部分のうちの１つ以上から構成されるステップと、
（ｂ）前記所定の集合演算に基づいて単純輪郭パスと別の単純輪郭パスとを交差させ、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択するステップと、
（ｃ）前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成するステップとを含み、
前記ステップ（ｂ）は前記対応する単純輪郭パス間の各交点に対して、
（ｂ１）前記交点を分類するサブステップと、
（ｂ２）前記分類された点を前記点に対応する前記オリジナルセグメントのいずれかに挿入するサブステップと、
（ｂ３）前記分類及び挿入に基づいて追加のセグメント及び共直線性のあるエッジを識別するサブステップと、を有することを特徴とする。
【０００８】
前記ステップ（ａ）は前記入力パスの各々に対して、
（ａ１）前記オリジナルセグメント又はその部分の各々が少なくとも１つの対応するバンドを有するように前記入力パスが定義される空間を複数のバンドに分割するサブステップと、
（ａ２）前記バンドの各々を検査し、対応するバンド内の前記オリジナルセグメントの位置及び／又は方向に基づいて前記バンドの各々の内部に含まれる前記オリジナルセグメント又はその部分の各々を分類するサブステップと、
（ａ３）前記検査に基づいて前記バンドの各々の内部に更なるセグメントを作成するサブステップと、
（ａ４）対応するバンド内に含まれる前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントの各々の位置及び分類に基づいて、前記オリジナルセグメント又はその部分及び／又は前記更なるセグメントのうちの少なくとも１つを境界線セグメントになるように割り当てるサブステップと、
（ａ５）前記境界線セグメントのうちの少なくとも１つを結合して少なくとも１つのエッジを形成し、対応する入力パスに対して前記入力パス表現のうちの少なくとも１つを生成するサブステップとを含むのが好ましい。
【００１０】
前記ステップ（ｂ）は、
（ｂ４）前記識別された追加のセグメント及び共直線性のあるエッジに基づいて、前記出力パスにおいて使用するために前記オリジナルセグメントのうちの１つ以上を選択するサブステップを更に含むのが好ましい。
【００１１】
本発明の別の態様によると、所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成するための装置であって、
前記入力パスの各々は、少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記装置は、
前記２つ以上の入力パスの各々を対応する単純輪郭パスに変換する手段であって、前記単純輪郭パスの各々は前記オリジナルセグメント又はその部分のうちの１つ以上から構成される変換手段と、
前記所定の集合演算に基づいて単純輪郭パスと別の単純輪郭パスとを交差させ、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択する交差手段と、
前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成する結合手段とを備え、
各交点を分類する分類手段と、
前記分類された点を前記点に対応する前記オリジナルセグメントのいずれかに挿入する挿入手段と、
前記分類及び挿入に基づいて追加のセグメント及び共直線性のあるエッジを識別する識別手段とを更に具備することを特徴とする装置が提供される。
【００１２】
本発明の更に別の態様によると、所定の集合演算に基づいて、２つ以上の入力パスからグラフィカルオブジェクトのレンダリングに使用するための出力パスを形成するためのプログラムであって、
前記入力パスの各々は少なくとも１つのエッジから構成され、前記エッジの各々が１つ以上のオリジナルセグメントから構成され、
前記プログラムは、
（ａ）前記２つ以上の入力パスの各々を対応する単純輪郭パスに変換するためのコードであって、前記単純輪郭パスの各々は前記オリジナルセグメント又はその部分のうちの１つ以上から構成されるコードと、
（ｂ）前記所定の集合演算に基づいて単純輪郭パスと別の単純輪郭パスとを交差させ、前記出力パスにおいて使用するために前記オリジナルセグメント又はその部分のうちの１つ以上を選択するためのコードと、
（ｃ）前記選択されたオリジナルセグメント又はその部分を結合し、前記出力パスを形成するためのコードとを含み、
前記ステップ（ｂ）は、
前記対応する単純輪郭パス間の各交点に対して、
前記対応する単純輪郭パス間の各交点を分類するためのコードと、
前記分類された点を前記点に対応する前記オリジナルセグメントのいずれかに挿入するためのコードと、
前記分類及び挿入に基づいて追加のセグメント及び共直線性のあるエッジを識別するためのコードとを含むサブステップを有するプログラムが提供される。
【００１３】
【発明の実施の形態】
添付のいずれか１つ以上の図面において、同じ符号を有するステップ及び／又は特徴に言及する場合、特に明記されていない限り、以下の記述においては、これらのステップ及び／又は特徴は、同じ機能又は動作を有するものとする。
【００１４】
２つ以上の任意の入力パスから出力パスを判定する方法を以下で説明する。この方法では、２つ以上の任意の入力パスに対して集合演算を行ない、出力パスを判定する。出力パスは単純輪郭パスであり、単純輪郭パスは、ここでは以下の特性を備えたパスとして定義される：
（i）出力パスが、入力パスの元の塗りつぶし規則に従って定義される入力パスの内部の境界となるセグメントである境界線セグメントのみから成るという特性、
（ii）奇偶ワインディング塗りつぶし規則及びノンゼロワインディング塗りつぶし規則のいずれかを使用して輪郭パスの内部を正確に解釈することができるという特性、及び
（iii）ノンゼロワインディング塗りつぶし規則を用いて解釈されるときに輪郭パスが一様なオリエンテーション（時計回り又は反時計回り）を有するという特性（すなわち、輪郭パスの各エッジの方向に従ってエッジと交差するとき、輪郭パスにより定義される全てのエッジの内部は、エッジの全てのセグメントの左側及び右側のいずれかにのみ存在する可能性がある）。
【００１５】
単純輪郭パスの全てのエッジに関して、エッジ内において頂点を共有する非連続セグメントは１対もなく、連続セグメントの各対はちょうど１つの頂点を共有する。エッジ内の非連続セグメントが頂点を共有する場合、例えば、エッジが２つのセグメント（すなわち、２つの別々の頂点）のみを含む線を描く場合、結果として生じるセグメントは交差しない。
【００１６】
上述の特性を有する単純輪郭パスは極めて柔軟性が高く、ノンゼロワインディング塗りつぶし規則及び奇偶ワインディング塗りつぶし規則の双方の最も有利な特性を活用することができる。従って、単純輪郭パスは、新規の方法を開発するときに要求される論理を単純化しながら既存のパス処理方法の多くを再利用する際の柔軟性を高めることができる。また、単純輪郭パスにより各パスの内部は特定のプロセスにとって最も利便性の高い塗りつぶし規則を用いて解釈することが可能になると共に、専門的な所有ハードウェアが従来のパス処理方法よりもはるかに優れた速度的な利点を得るのに必要とされる最小限の努力でパスを処理できるようになる。
【００１７】
説明を簡単にする目的で、以下に記述する方法の各ステップは、ノンゼロワインディング規則及び奇偶ワインディング規則を参照して説明する。しかし、本発明は記載される方法にのみ限定されるものではない。例えば、本発明を「ワインディングカウント」塗りつぶし規則又は「ゼロワインディング」塗りつぶし規則などの他の何らかの塗りつぶし規則に適用しても良い。更に、説明を簡単にする目的で、本明細書に記載する方法に従って処理される入力パスの数を２つに制限する。しかし、当業者はこの方法を使用して任意の数のパスを同時に処理できることを認識するであろう。
【００１８】
ここに記載する方法に従って処理される入力パスのエッジは、どのような種類のポリゴンでも定義することができ、各ポリゴンは、任意の複雑度を有することが可能である。更に、この方法では、パスが定義される空間内の相互に対する各入力ポリゴンの位置は、いかなる形であれ制限されることがない。この方法は、縮退したパスを処理するとき、頂点を移動又はかく乱させたりしない（すなわち、パスが定義される空間内の元の位置において全ての頂点が処理される）。
【００１９】
ここに記載する方法は、図３に示すような汎用コンピュータシステム３００を使用して実施されるのが好ましい。図１から図４５を参照して説明するプロセスは、コンピュータシステム３００内で実行されるアプリケーションプログラムなどのソフトウェアとして実現されても良い。特に、この方法の各ステップは、コンピュータにより実行されるソフトウェア中の命令により実施される。命令は、各々が１つ以上の特定のタスクを行なうためのものである１つ以上のコードモジュールとして形成されても良い。ソフトウェアは、記載された方法を実行する第１の部分と、第１の部分とユーザとの間のユーザインタフェースを管理する第２の部分との２つの別々の部分に分割されても良い。ソフトウェアは、例えば、以下に記述するような記憶装置を含むコンピュータ可読な媒体に格納されても良い。ソフトウェアは、コンピュータ可読な媒体からコンピュータへとロードされ、コンピュータにより実行される。このようなソフトウェア又はコンピュータプログラムを記録したコンピュータ可読な媒体は、コンピュータプログラム製品である。コンピュータにおいてコンピュータプログラム製品を使用することにより、２つ以上の任意のパスから単純輪郭パスを生成するための有利な装置を実現するのが好ましい。
【００２０】
コンピュータシステム３００は、コンピュータモジュール３０１、キーボード３０２及びマウス３０３などの入力装置、並びにプリンタ３１５及び表示装置３１４を含む出力装置を具備する。変復調（モデム）送受信装置３１６は、コンピュータモジュール３０１が、例えば、電話回線３２１又はその他の機能媒体を介して接続可能な通信ネットワーク３２０と通信を行なうのに使用される。モデム３１６は、インターネット及び構内通信網（ＬＡＮ）又は広域通信網（ＷＡＮ）などのその他のネットワークシステムへのアクセス権を取得するのに使用することができる。
【００２１】
コンピュータモジュール３０１は、通常、少なくとも１つのプロセッサユニット３０５、例えば、半導体ランダムアクセスメモリ（ＲＡＭ）及び読出し専用メモリ（ＲＯＭ）から形成されるメモリユニット３０６、ビデオインタフェース３０７とキーボード３０２、マウス３０３、及びオプションとしてのジョイスティック（不図示）用のＩ／Ｏインタフェース３１３とを含む入出力（Ｉ／Ｏ）インタフェース、並びにモデム３１６用のインタフェース３０８を含む。記憶装置３０９が設けられるが、この記憶装置３０９は、通常、ハードディスクドライブ３１０及びフロッピー(登録商標）ディスクドライブ３１１を含む。磁気テープドライブ（不図示）を使用しても良い。ＣＤ−ＲＯＭドライブ３１２は、通常、不揮発性のデータソースとして設けられる。コンピュータモジュール３０１の構成要素３０５から３１３は、通常、相互接続バス３０４を介して、コンピュータシステム３００の動作モードが、当業者には既知の従来の動作モードになるように通信を行なう。上述の構成が実施されるコンピュータの例としては、ＩＢＭ−ＰＣ及びその互換機、Sun Sparcstation、又はそれを進化させた同様のコンピュータシステムがある。
【００２２】
通常、アプリケーションプログラムはハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出されて制御される。プログラムとコンピュータネットワーク３２０から取り込まれるデータとの中間記憶装置は、半導体メモリ３０６を使用し、場合によってはハードディスクドライブ３１０と協働させるように使用して達成されても良い。アプリケーションプログラムは、ＣＤ−ＲＯＭ又はフロッピー(登録商標）ディスク上に符号化された形でユーザに供給され、対応するドライブ３１２又は３１１を介して読み取られる場合もあれば、ネットワーク３２０からモデム装置３１６を介してユーザが読み取る場合もある。更に、このソフトウェアは、他のコンピュータ可読な媒体からコンピュータシステム３００へとロードすることもできる。ここで使用する用語「コンピュータ可読な媒体」は、コンピュータシステム３００に実行及び／又は処理させる命令及び／又はデータの供給に関係する任意の記憶媒体及び伝送媒体を指す。記憶媒体の例としては、フロッピー(登録商標）ディスク、磁気テープ、ＣＤ−ＲＯＭ、ハードディスクドライブ、ＲＯＭ又は集積回路、光磁気ディスク、又はＰＣＭＣＩＡカードなどのコンピュータ可読なカードがある。これらの媒体がコンピュータモジュール３０１の内部にあるか、あるいは、外部にあるかは関係がない。伝送媒体の例としては、無線又は赤外線の伝送チャネル、別のコンピュータ又はネットワーク化装置とのネットワーク接続、並びに電子メール送受信及びウェブサイトなどに記録された情報などを含むインターネット又はイントラネットがある。
【００２３】
ここに記載する方法は、図４から図４５の関数又は下位関数を実行する１つ以上の集積回路などの専用ハードウェアにおいて実現されても良い。このような専用ハードウェアには、グラフィックプロセッサ、デジタル信号プロセッサ、又は１つ以上のマイクロプロセッサ及び関連メモリが含まれても良い。
【００２４】
図１Ａは、パスの構成要素を定義するのに使用可能なツリー構造１００の一例を示す。図１Ｂは、図より明らかであるように４つのエッジを具備するサンプルパス１０２を示す。説明を簡単にする目的で、ここではパスは１つ以上のエッジ（例えば、エッジ１）を具備するものとして定義され、エッジは少なくとも２つのセグメント（例えば、セグメント１、セグメント２）及び３つの頂点を具備する。１つのセグメントを有するエッジは、事実上点となるからである。ここに記載する種々の構成は、任意の本数のセグメントを具備するエッジを使用して実施することが可能である。パスの全てのエッジは閉じており（すなわち、閉じた輪郭を形成）、全てのセグメントは、開始頂点及び終端頂点（例えば、Ｖ1、Ｖ2、Ｖ3など）を有している。例えば、図１Ｂにおいて明らかなように、エッジ３は頂点１０６において開始し終了する閉じた輪郭を形成する。各頂点は頂点のｘ及びｙ座標により定義される。ポリゴンの種類、各ポリゴンの複雑度、及びパスにおける各ポリゴンの相互に対する位置に制限はない。有利な点として、パスは、同じセグメント上で開始し終了する異なるセグメント及び／又は共直線セグメントなどの縮退したケースを含むことができる。これらのセグメントの全ては図１Ｂにおいて、パス１０２として強調表示されている。
【００２５】
ここに記載する方法は、正のｘ軸が左から右へと伸び、正のｙ軸が下から上へと伸びる自然座標空間を利用する。図２は自然座標空間に従って構成された４つの異なるセグメント２００、２０１、２０２及び２０３を示す。セグメント２００は、正のｙ方向に上向きであり、セグメント２０２は負のｙ方向に下向きである。セグメント２０１は正のｘ方向に伸び、セグメント２０３は負のｘ方向に伸びる。ｙ2＞ｙ1、又はｙ4＝ｙ3且つｘ3＜ｘ4が成り立つ場合のみセグメントは上向きになる。同様に、ｙ2＜ｙ1、又はｙ4＝ｙ3且つｘ4＜ｘ3が成り立つ場合のみセグメントは下向きになる。
【００２６】
パス上で実行される集合演算の種類は、そのパスに関連するクリップ規則において規定される。パスのクリップ規則は、パスの内部が関連する塗りつぶし規則に従って解釈されるべきであるか、あるいは、塗りつぶし規則に反して解釈されるべきであるかを指定するように構成される。以下に示す表１は、集合演算とここに記載する方法に従った各演算に関連するクリップ規則とを示す。表１におけるＴＲＵＥ（真）は、パスの内部が関連する塗りつぶし規則に従って解釈されるべきであることを示す。表１におけるＦＡＬＳＥ（偽）は、パスの内部が関連する塗りつぶし規則に反して解釈されるべきであることを示す。しかし、当業者は、本明細書記載の方法に従って付加的な集合演算（例えば、排他的論理和（すなわち、ＸＯＲ））を実施可能であることを認識するであろう。
【００２７】
【表１】
0003796478.tif 000002
【００２８】
図４は２つ以上の任意の入力パスから出力パスを判定するプロセス４００を示すフローチャートである。出力パスは上述のような単純輪郭パスである。プロセス４００は、２つ以上の任意の入力パスに対して集合演算を行ない、出力パスを判定する。プロセス４００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行により読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス４００は、ステップ４０１で開始される。ステップ４０１において、プロセッサ３０５は２つの入力パスを「単純輪郭変換」プロセスを介して２つの単純輪郭パスへと変換する。単純輪郭変換プロセスについては、特に、図６Ａから図３６を参照して詳細に説明する。次のステップ４０３において、単純輪郭パスはプロセッサ３０５により相互に交差させられ、「単純パス交差」プロセスを使用して候補セグメントが生成される。候補セグメントは、最終結果単純輪郭パスに属するセグメントであり、最終結果単純輪郭パスは候補セグメントのみから成る。例えば、図５Ａは２つのパスＥｄｇｅ＿１及びＥｄｇｅ＿２を示す。これらのパスは論理積集合演算（すなわち、Ｅｄｇｅ＿１∩Ｅｄｇｅ＿２）に従って処理される。パスＥｄｇｅ＿１及びＥｄｇｅ＿２の共通部分はセグメント５０１から５０６を含み、これらのセグメントは候補セグメントと呼ばれる。図５ＢはＥｄｇｅ＿１及びＥｄｇｅ＿２の共通部分から生じる最終単純輪郭パス５１０を示す。輪郭パス５１０は候補セグメント５０１から５０６を具備する。単純パス交差プロセスについては、特に、図３７から図４５を参照して詳細に後述する。プロセス４００は次のステップ４０５で終了する。ステップ４０５において、ステップ４０３で生成された候補セグメントはプロセッサ３０５により結合され、「輪郭構築」プロセスを介して単純輪郭パスが形成される。単純輪郭パスはハードディスクドライブ３１０又はメモリ３０６に格納することができる。輪郭パス交差プロセスを以下で詳細に説明する。
【００２９】
図６Ａは、方法４００のステップ４０１で実行されるように、奇偶ワインディング塗りつぶし規則又はノンゼロワインディング塗りつぶし規則に従って構成された入力パスを単純輪郭パスに変換するプロセス６００を示す。プロセス６００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行により読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。図６Ｂは以下の記述を通して使用される各記号の定義を示す。
【００３０】
プロセス６００はステップ６０１で開始される。ステップ６０１において、プロセッサ３０５によりセグメントテーブル（ＳＴ）が構築される。セグメントテーブルは、パスが定義される空間に対する１つ以上のバンドの各々の定義を含み、メモリ３０６に格納されるのが好ましい。セグメントテーブルは、全てのセグメントを含むグローバルテーブルであり、２つのレベルにおいてソートされるのが好ましい。第１のレベルにおいて、パスの各セグメントの開始／終端頂点の相異なるｙ位置を含む「バケット」が作成され、昇順でソートされる。トップダウン処理方法が利用される場合、バケットは降順でソートすることもできる。この場合、バケットは入力パスが定義される空間の全てのバンドラインを含む。バケット内では、セグメントは各々の「レフトネス（leftness）」に従ってソートされる。グラフィカルに説明すると、定義される空間においてセグメントが他のセグメントに比べて事実上左寄りに位置する場合、セグメントは他のセグメントよりもレフトネスが高い（すなわち、より左側に位置する）ものとして分類される。数値的に説明すると、別の頂点よりもｘ座標値が小さいセグメントは、その別の頂点よりも左寄りであると考えられる。
【００３１】
２つのセグメントに対する開始セグメントのｘ座標が等しい場合、関連するバンドラインからセグメントまで時計回りに測定した角度が小さいセグメントはレフトネスが高いと見なされる。各バケットはそのバケットのｙ座標と一致するｙ座標の開始頂点を有する（すなわち、そのバンドラインにおいて開始される）セグメントのみを含む。セグメントの開始頂点は、常に「小さい方の」頂点である。すなわち、全てのセグメント（水平セグメントを含む）は、セグメントの元の方向に関わらずデフォルトの上向きの方向を有するのが好ましい。ノンゼロワインディング塗りつぶし規則の方向を感知する性質により、ノンゼロワインディング塗りつぶし規則に従って構成されたパスの全てのセグメントの元の方向が格納される。
【００３２】
入力パスを変換する上述の方法において、レフトネスの比較が実行され、各セグメントのレフトネスが判定される。各入力セグメントの始点が比較され、各始点において、その始点からの各セグメントの始点の角度が比較される。例えば、図７は６つのセグメント（すなわち、セグメントＡからＦ）を示す。ｘ1＜ｘ3であるため、セグメントＡ及びＦは、セグメントＡからＦのうちで最高のレフトネスを有するものと考えられる。座標(x1,y1)により定義される点において、Ａ°＜Ｆ°であるため、セグメントＡはセグメントＦよりもレフトネスが高いと見なされる。更に、点(x3,y1)において、Ｂ°＜Ｃ°であるため、セグメントＢはセグメントＣよりもレフトネスが高いと見なされ、Ｃ°＜Ｄ°であるため、セグメントＣはセグメントＤよりもレフトネスが高いと見なされ、Ｄ°＜Ｅ°であるため、セグメントＤはセグメントＥよりもレフトネスが高いと見なされる。
【００３３】
図８は、特定の入力パスに対してセグメントテーブル（すなわち、ＳＴ）を構築するプロセス８００を示す。このプロセス８００はステップ６０１で実行される。プロセス８００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス８００は第１のステップ８０１で開始される。ステップ８０１において、プロセッサ３０５によりパスのエッジが選択される。次のステップ８０３において、選択されたエッジのセグメントが選択される。プロセス８００は次のステップ８０５へと続く。ステップ８０５において、ステップ８０３で選択されたセグメントのｙmax及び／又はｙminの値を有するバケットが存在しない場合、次のステップ８０７において、ｙmax及び／又はｙminに対するバケットが作成され、これらのバケットはメモリ３０６又はハードディスクドライブ３１０に格納される。バケットが存在する場合、プロセス８００は次のステップ８０９へと進む。ステップ８０９において、ステップ８０３で選択されたセグメントがレフトネスの降順に値ｙminを有するバケットに挿入される。次のステップ８１１において、エッジ中に更にセグメントが存在する場合、プロセス８００はステップ８０３へと戻る。セグメントが存在しない場合、プロセスはステップ８１３へと進む。ステップ８１３において、パス中に更にエッジが存在する場合、プロセス８００はステップ８０１へと戻る。このため、プロセッサ３０５により、パスの全てのエッジの全てのセグメントに対してステップ８０１から８１３が繰り返される。２つのセグメントが等しく左側にある場合、これらのセグメントはセグメントの発生時間に従って順序付けられる（すなわち、第２セグメントは第１セグメントの後に挿入される）。ステップ８１３においてパスにエッジが存在しない場合、プロセス８００が終了する。
【００３４】
図６Ａのプロセス６００に戻る。ステップ６０３において、プロセッサ３０５によりパスが定義される空間に対して最下部のバケットから最上部のバケットまでの昇順でセグメントテーブルからバケットが選択される。プロセス６００は次のステップ６０５へと進む。ステップ６０５において、プロセッサ３０５により「アクティブセグメントテーブル（ＡＳＴ）」が作成され、更新される。アクティブセグメントテーブルは、全てのアクティブセグメントを格納し、メモリ３０６において構成されるのが好ましい。セグメントは、処理中の現在のバンド内に存在するときにアクティブであると見なされる。このため、アクティブセグメントテーブルにより、各バケットは別々に処理できるようになる。図９のフローチャートを参照してステップ６０５のアクティブセグメントテーブルを更新するプロセス９００を以下で詳細に説明する。
【００３５】
図９はアクティブセグメントテーブルを更新するプロセス９００の各ステップを示すフローチャートである。プロセス９００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス９００はステップ９０１で開始される。ステップ９０１において、プロセッサ３０５により図１０に示す「分割検出」プロセス１０００が実行される。分割検出プロセス１０００は、アクティブセグメントテーブル中の全ての点に対して、その点上のセグメントを分割する必要があるか否かを判定するための検査を行なう。ある点が結合する２つ以上のセグメントを含み、考慮中のセグメントがその点で終了しない（すなわち、セグメントはその点を通過する）場合、点上のセグメントを分割する必要がある。分割検出プロセス１０００については、図１０を参照して詳細に後述する。分割検出プロセス１０００の後、メモリ３０６に格納されたアクティブセグメントテーブルは、セグメントテーブルからの新規のセグメント（すなわち、現在のバンドラインから開始されるセグメント）と共に挿入可能な状態にある。挿入中、アクティブセグメントテーブルに新規の点が導入される可能性があり、新規の点から開始される２つ以上の新規のセグメントが存在する場合、これらの新規のセグメントはレフトネスの降順にソートされる（すなわち、セグメントテーブル内での順序を引き継ぐ）。アクティブセグメントテーブル中の既存の点から開始される既存のセグメントの中に各セグメントが挿入される場合、これらの新規のセグメントはその点における全ての終了セグメントの後に挿入され、その点で開始するセグメントの中でレフトネスの降順にソートされる。
【００３６】
加えて、セグメントを１つだけ有する既存の点に挿入される新規のセグメントが存在し、セグメントがその点上で終了しない場合、新規のセグメントをその点上で挿入する前に既存のセグメントが分割される。上述のように、全ての新規のセグメントは終了セグメントの後に挿入され、レフトネスの降順にソートされなければならない。既存のセグメントの分割は「アクティブセグメントテーブル分割書込み」プロセス１３００により実行される。このプロセスについては図１３を参照して後述する。
【００３７】
プロセス９００の次のステップ９０３において、プロセッサ３０５によりメモリ３０６に格納されたセグメントテーブルから現在のバケットの最左端のセグメントから最右端のセグメントに至る順序でセグメントが選択される。ステップ９０３で選択されるセグメントは、ラベルＳＴ＿ｓｅｇｍｅｎｔを割り当てられるのが好ましい。プロセス９００はステップ９０５へと続き、ここでメモリ３０６に格納されたアクティブセグメントテーブルから最左端のアクティブセグメントから最右端のアクティブセグメントに至る順序でセグメントが選択される。アクティブセグメントテーブルから選択されたセグメントのｘ座標は、現在の点として設定される。ｃｕｒｒｅｎｔ＿ｐｏｉｎｔラベルは、現在の点に割り当てられるのが好ましい。次のステップ９０７において、プロセッサ３０５により検査が実行され、ステップ９０３でセグメントテーブルから選択されたセグメントのｘ座標が現在の点の値（すなわち、ラベルｃｕｒｒｅｎｔ＿ｐｏｉｎｔで表される値）より小さいか否かが判定される。
【００３８】
ステップ９０７の結果が真の場合、プロセス９００はステップ９０９へと進む。ステップ９０９において、プロセッサ３０５により検査が実行され、ステップ９０３でセグメントテーブルから選択された現在のセグメントが水平セグメントであるか否かが判定される。水平セグメントは、ここでは２つ以上の点にまたがるセグメントとして定義される。水平セグメントは、これらの点の各々において分割され、これらの点には、アクティブセグメントテーブル及びセグメントテーブルの双方と異なるもの、あるいは、異ならないものが含まれる。ここに記載する方法では、プロセッサ３０５により実行される水平分割プロセス１５００が、水平セグメントを分割すべき点を判定する。この水平分割プロセス１５００については図１５のフローチャート１５００を参照してより詳細に後述する。水平セグメントの実際の分割は、「水平セグメント分割」プロセス１６００により実行される。「水平セグメント分割」プロセス１６００については図１６のフローチャートを参照して更に詳細に説明する。ステップ９０９の結果が偽の場合、プロセス９００はステップ９１１へと進み、ここで、現在のセグメントがメモリ３０６に格納されたアクティブセグメントテーブルに挿入される。ステップ９０９の結果が真の場合、プロセス９００はステップ９１３へと進む。ステップ９１３において、プロセッサ３０５により水平分割プロセス１５００が実行され、セグメントがまたがる点の各々において水平セグメントが分割される。
【００３９】
プロセス９００は次のステップ９１５へと進む。ここで、メモリ３０６に格納されたセグメントテーブルの現在のバケット中に更にセグメントが存在する場合、プロセス９００はステップ９１７へと進む。セグメントが存在しない場合、セグメントテーブルの更新は終了し、プロセス９００は終了してフローチャート６００のステップ６０７に戻る。
【００４０】
ステップ９１７において、レフトネスの降順のセグメントテーブルから別のセグメントが選択され、プロセス９００はステップ９０７へと戻る。ステップ９０７の結果が偽の場合、プロセス９００はステップ９１９へと進む。ステップ９１９において、プロセッサ３０５により検査が実行され、ステップ９１７でセグメントテーブルから選択されたセグメントのｘ座標が現在の点の値（すなわち、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔ）と等しいか否かが判定される。ステップ９１９の結果が偽の場合、プロセス９００はステップ９２１へと進む。ステップ９２１において、アクティブセグメントテーブルに更に点が存在する場合、プロセス９００はステップ９０５へと戻る。
【００４１】
ステップ９１９の結果が真の場合、プロセス９００はステップ９２３へと進む。ステップ９２３において、アクティブセグメントテーブル分割書込みプロセス１３００が現在の点に対して実行される。上述のように、アクティブセグメントテーブル分割書込みプロセス１３００については図１３のフローチャートを参照して詳細に後述する。
【００４２】
更に、上述のように、セグメントを１つだけ有する既存の点に挿入される新規のセグメントが存在し、セグメントが特定の点上で終了しない場合、新規のセグメントをその点上で挿入する前に既存のセグメントが分割される。従って、アクティブセグメントテーブル中の全ての既存の点を検査しなければならない。しかし、メモリ３０６に格納されるアクティブセグメントテーブルに点が残っていない場合、この検査は省略することが可能であり、アクティブセグメントテーブルは直接塗りつぶされる。アクティブセグメントテーブルの書込みは「アクティブセグメントテーブル書込み」プロセス１４００により実行される。このプロセス１４００については、図１４のフローチャートを参照して詳細に後述する。
【００４３】
図９のプロセス９００は、次のステップ９２５へと続く。ステップ９２５において、プロセッサ３０５により検査が実行され、アクティブセグメントテーブルに更に点が存在するか否かが判定される。メモリ３０６内に構成されたＡ＿ｆｌａｇとラベル付けされたバッファが使用され、アクティブセグメントテーブルに更に点が存在するか否かが示されるのが好ましい。
【００４４】
ステップ９２５の結果が真の場合、プロセス９００はステップ９２７へと進む。ステップ９２７において、プロセッサ３０５により「アクティブセグメントテーブル書込み」プロセス１４００が実行され、プロセス９００はプロセス６００のステップ６０７へと進む。アクティブセグメントテーブルには点が存在しないので、「アクティブセグメントテーブル書込み」プロセス１４００は、自立型「水平セグメント分割点判定」プロセスを有する。また、ステップ９２５の結果が偽の場合、プロセス９００はステップ９２９へと進む。ステップ９２９において検査が実行され、セグメントテーブルの現在のバケットにセグメントが存在するか否かが判定される。メモリ３０６内で構成されたＳ＿ｆｌａｇとラベル付けされたバッファが使用され、セグメントテーブルの現在のバケットにセグメントが存在するか否かが示されるのが好ましい。ステップ９２９での検査の結果が偽の場合、プロセスはステップ９０７へと戻る。検査の結果が真の場合、プロセス９００は終了し、フローチャート６００のステップ６０７へと進む。
【００４５】
図１０は上述の方法に従って特定の点上のセグメントを分割する必要があるか否かを判定する分割検出プロセス１０００の各ステップを示すフローチャートである。プロセス１０００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス１０００はステップ１００１で開始される。ステップ１００１において、プロセッサ３０５によりメモリ３０６に格納されたアクティブセグメントテーブルから最左端のアクティブセグメントから最右端のアクティブセグメントに至る順序でセグメントが選択される。次のステップ１００３において、プロセッサ３０５により検査が実行され、現在のバンドライン上の次のセグメントのｘ座標が現在のバンドライン上の現在のセグメントのｘ座標と等しいか否かが判定される。ステップ１００３での検査の結果が偽の場合、プロセスはステップ１００５へと進む。ステップ１００５において、アクティブセグメントテーブルに更にセグメントが存在する場合、プロセス１０００はステップ１００１へと戻る。ステップ１００３において、現在のバンドライン上の次のセグメントのｘ座標が現在のバンドライン上の現在のセグメントのｘ座標と等しい場合、プロセス１０００はステップ１００７へと進む。ステップ１００７において、現在の点のラベル（すなわち、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔ）が現在のバンドライン上の現在のセグメントのｘ座標に設定される。プロセス１０００はステップ１００９へと続く。ステップ１００９において、プロセッサ３０５により検査が実行され、ステップ１００１で選択されたセグメントが処理中の現在のバケットのｙ座標で終了するか否かが判定される。ステップ１００９での検査の結果が偽の場合、プロセス１０００はステップ１０１１へと進む。ステップ１０１１において、現在の点における選択されたセグメントは図１１に示す「セグメント分割」プロセス１１００を使用して分割される。セグメント分割プロセス１１００は、特定の点上の既存のセグメントを終了した後に新規のセグメントを作成することによって、その特定の点上の終了セグメント及び開始セグメントを分離する。新規のセグメントはその特定の点から開始され、終了したセグメントの元の終端頂点で終了する。新規のセグメントは、レフトネスの降順に並んだ全ての終了セグメントの後に挿入されなければならない。例えば、図１２は、現在のバンドライン１２００の全ての終了セグメント１２０１、１２０２、及び１２０３の後に、新規のセグメント１２０４、１２０５、及び１２０６を挿入した例を示す。図１２に示すように、セグメント分割プロセス１１００（図１２の矢印により表す）が実行された後、３つのセグメント１２０１から１２０３が点Ａにおいて終了させられ、新規のセグメント１２０４から１２０６が挿入される。セグメント分割プロセス１１００については、図１１のフローチャートを参照して詳細に後述する。
【００４６】
ステップ１００９において、ステップ１００１で選択されたセグメントが処理中の現在のバケットのｙ座標で終了する場合、プロセス１０００はステップ１０１３へと進む。ステップ１０１３において、メモリ３０６に格納されたアクティブセグメントテーブルに更にセグメントが存在する場合、プロセスはステップ１０１５へと進む。セグメントが存在しない場合、分割検出プロセス１０００は、プロセス９００のステップ９０３へと進む。ステップ１０１５において、プロセッサ３０５によりメモリ３０６に格納されたアクティブセグメントテーブルから次のセグメントが選択される。プロセス１０００はステップ１０１７へと続く。ステップ１０１７において、プロセッサ３０５により検査が実行され、ステップ１０１５で選択されたセグメントの現在のバンドラインにおけるｘ座標が現在の点と等しいか否かが判定される。ステップ１０１７の結果が真の場合、プロセス１０００はステップ１００９へと戻る。ステップ１０１７の結果が偽の場合、プロセス１０００はステップ１０１９へと進む。ステップ１０１９において、アクティブセグメントテーブルに更にセグメントが存在する場合、プロセス１０００はステップ１００３へと戻る。ステップ１０１９において、アクティブセグメントテーブルに更にセグメントが存在しない場合、分割検出プロセス１０００はプロセス９００のステップ９０３へと進む。
【００４７】
図１１は特定の点でセグメントを分割するセグメント分割プロセス１１００の各ステップを示すフローチャートである。プロセス１１００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。セグメント分割プロセス１１００は、特定の点上で既存のセグメントを終了させた後に新規のセグメントを作成する。プロセス１１００はステップ１１０１で開始される。ステップ１１０１において、座標(Xcur,ybucket)により定義される点で開始し、現在のセグメントの終点で終了する新規のセグメントが作成される。次のステップ１１０３において、現在のセグメントは、座標(Xcur,ybucket)により定義される点で終了させられる。プロセス１１００はステップ１１０５で終了する。ステップ１１０５において、全ての終了セグメントの後の、現在のバンドライン上の現在の点においてレフトネスの降順に新規のセグメントが挿入される。プロセス１１００は終了し、フローチャート１０００のステップ１０１３へと進む。
【００４８】
図１３はアクティブセグメントテーブル分割書込みプロセス１３００の各ステップを示すフローチャートである。プロセス１３００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。既存の点に挿入される新規のセグメントが存在する場合、プロセッサ３０５によりアクティブセグメントテーブル分割書込みプロセス１３００が実行される。プロセス１３００はステップ１３０１で開始される。ステップ１３０１において、メモリ３０６に格納されたＳ＿ｆｌａｇ及びＡ＿ｆｌａｇの双方が、セグメントテーブルの現在のバケットが空でなく、アクティブセグメントテーブルに少なくとももう１つの点が存在することを示すＦＡＬＳＥに設定される。次のステップ１３０３において、プロセッサ３０５により検査が実行され、現在の点の第１のセグメントがｙbucketで終了するか否かが判定される。ステップ１３０３の結果が偽の場合、プロセス１３００はステップ１３０５へと進む。ステップ１３０５において、プロセッサ３０５により現在のバンドラインの第１のセグメント上でセグメント分割プロセス１１００が実行される。プロセス１３００は次のステップ１３０７へと続く。ステップ１３０７において、プロセッサ３０５により検査が実行され、セグメントテーブル（すなわち、ＳＴ＿ｓｅｇｍｅｎｔ）の現在のセグメントが水平セグメントであるか否かが判定される。ステップ１３０７の結果が真の場合、プロセス１３００はステップ１３０９へと進む。ステップ１３０９において、上述したように、プロセッサ３０５により水平分割プロセス１５００が実行される。ステップ１３０７の結果が偽の場合、プロセス１３００はステップ１３１１へと進む。ステップ１３１１において、アクティブセグメントテーブルの現在のバンドラインの全ての終了セグメントの後に開始セグメントのレフトネスの降順に、現在のセグメントが挿入される。
【００４９】
プロセス１３００は次のステップ１３１３へと続く。ステップ１３１３において、プロセッサ３０５により検査が実行され、セグメントテーブルの現在のバケットに更にセグメントが存在するか否かが判定される。ステップ１３１３の結果が偽の場合、プロセス１３００はステップ１３１５へと進む。ステップ１３１５において、Ｓ＿ｆｌａｇがＴＲＵＥに設定される。ステップ１３１３の結果が真の場合、プロセス１３００はステップ１３１７へと進む。ステップ１３１７において、セグメントテーブルの現在のバケットから現在のバケットの最左端のセグメントから最右端のセグメントに至る順序で次のセグメントが選択される。プロセス１３００は次のステップ１３１９へと続く。ステップ１３１９において、プロセッサ３０５により検査が実行され、現在のセグメントに対する現在のバンドライン上のｘ座標が現在の点の値（すなわち、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔ）と等しいか否かが判定される。ステップ１３１９の結果が真の場合、プロセス１３００はステップ１３０７へと戻る。ステップ１３１９の結果が偽の場合、プロセス１３００はステップ１３２１へと進む。ステップ１３２１において、プロセッサ３０５により検査が実行され、メモリ３０６に格納されたアクティブセグメントテーブルに更にセグメントが存在するか否かが判定される。ステップ１３２１の結果が偽の場合、プロセス１３００はステップ１３２３へと進む。ステップ１３２３において、Ａ＿ｆｌａｇはＴＲＵＥに設定される。ステップ１３２１の結果が真の場合、プロセス１３００はステップ１３２５へと進む。ステップ１３２５において、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔの値がアクティブセグメントテーブル中の次の点に設定され、アクティブセグメントテーブル分割書込みプロセス１３００はプロセス９００のステップ９２５へと進む。
【００５０】
図１４はアクティブセグメントテーブルを塗りつぶすアクティブセグメントテーブル書込みプロセス１４００の各ステップを示すフローチャートである。プロセス１４００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス１４００はステップ１４０１で開始される。ステップ１４０１において、プロセッサ３０５により検査が実行され、セグメントテーブル（すなわち、ＳＴ＿ｓｅｇｍｅｎｔ）から選択された現在のセグメントが水平セグメントであるか否かが判定される。ステップ１４０１の結果が真の場合、プロセスはステップ１４０３へと進む。ステップ１４０３において、セグメントテーブル中の現在のセグメントが開始される点に後続する点が選択され、点のｘ座標が割り当てられる。セグメントテーブル中の現在のセグメントが開始される点には、ラベルＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔが割り当てられるのが好ましい。プロセス１４００は次のステップ１４０４へと続く。ステップ１４０４において、プロセッサ３０５により検査が実行され、ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔが現在のセグメントに対する終端頂点のｘ座標より小さいか否かが判定される。ステップ１４０４の結果が真の場合、プロセス１４００はステップ１４０５へと続く。ステップ１４０５において、プロセッサ３０５により現在のセグメント上で水平セグメント分割プロセス１６００が実行される。ステップ１４０４の結果が偽の場合、プロセス１４００はステップ１４０７へと続く。ステップ１４０７において、現在のセグメント（すなわち、ＳＴ＿ｓｅｇｍｅｎｔ）がアクティブセグメントテーブルに挿入される。次のステップ１４０６において、セグメントテーブルに更に点が存在する場合、プロセス１４００はステップ１４０３へと戻る。点が存在しない場合、プロセス１４００はステップ１４０７へと進む。
【００５１】
ステップ１４０１の結果が偽の場合、ステップ１４０７において、現在のセグメントがメモリ３０６に格納されたアクティブセグメントテーブルに挿入され、プロセス１４００は直接ステップ１４０９へと進む。ステップ１４０９において、プロセッサ３０５により検査が実行され、セグメントテーブルの現在のバケットに更にセグメントが存在するか否かが判定される。ステップ１４０９においてセグメントテーブルに更に点が存在する場合、プロセス１４００はステップ１４０８へと進む。ステップ１４０８において、セグメントテーブルの現在のバケットから次のセグメントが選択され、現在のセグメント（すなわち、ＳＴ＿ｓｅｇｍｅｎｔ）として割り当てられる。ステップ１４０８の後、プロセス１４００はステップ１４０１へと戻る。プロセス１４００は、セグメントテーブルの現在のバケットに更にセグメントが存在しないときにはステップ１４０９において終了し、プロセス６００のステップ６０７へと進む。
【００５２】
図１５は水平セグメントを分割すべき点を判定する水平分割プロセス１５００の各ステップを示すフローチャートである。プロセス１５００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス１５００はステップ１５０１で開始される。ステップ１５０１において、プロセッサ３０５により検査が実行され、現在の点が現在のセグメント（すなわち、ＳＴ＿ｓｅｇｍｅｎｔ）に対する現在のバンドライン上のｘ座標と等しいか否かが判定される。ステップ１５０１の結果が偽の場合、プロセス１５００はステップ１５０２へと進む。ステップ１５０２において、現在の点が「アクティブセグメントテーブル分割点」として選択される（ＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔとして割り当てられ、メモリ３０６に格納されるのが好ましい）。プロセス１５００はステップ１５０３へと続く。ステップ１５０３において、プロセッサ３０５により検査が実行され、セグメントテーブルに更にセグメントが存在するか否かが判定される。ステップ１５０３の結果が真の場合、プロセス１５００はステップ１５０４へと進む。ステップ１５０４において、セグメントテーブル中の現在のセグメントが開始される点に後続する点が選択され、この点に点のｘ座標（すなわち、ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔ）が割り当てられる。ステップ１５０３の結果が偽の場合、プロセス１５００はステップ１５０６へと進む。ステップ１５０６において、ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔはプロセッサ３０５により現在のセグメントに対する終端頂点のｘ座標（すなわち、ｘmax）を含むように設定される。次のステップ１５０５において、検査が実行され、ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔがＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔより小さいか否かが判定される。ステップ１５０５の結果が真の場合、プロセス１５００はステップ１５０９へと進む。ステップ１５０９において、ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔが現在のセグメントに対する終端頂点のｘ座標（すなわち、ｘmax）より大きいか、あるいは、それと等しい場合、プロセス１５００はステップ１５３０へと進む。ステップ１５３０において、プロセス９００のステップ９０３又は９１７で選択されたセグメントがメモリ３０６に格納されたアクティブセグメントテーブルに挿入される。ステップ１５３０の後、プロセス１５００は終了し、プロセス９００のステップ９１５へと進む。ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔの方が小さい場合、プロセス１５００はステップ１５１２へと進む。ステップ１５１２において、水平セグメント分割プロセス１６００が現在のセグメント上で実行される。
【００５３】
プロセス１５００の次のステップ１５１４において、メモリ３０６に格納されたＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔが現在のセグメント、すなわち、ＳＴ＿ｓｅｇｍｅｎｔに対する終端頂点のｘ座標（すなわち、ｘmax）より大きいか、あるいは、それと等しい場合、プロセス１５００はステップ１５０８へと進む。ＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔの方が小さい場合、プロセス１５００はステップ１５１５へと進む。ステップ１５１５において、プロセッサ３０５により現在のセグメント（すなわち、ＳＴ＿ｓｅｇｍｅｎｔ）上で水平セグメント分割プロセス１６００が実行される。次のステップ１５１７において、アクティブセグメントテーブルに更に点が存在する場合、プロセス１５００はステップ１５１６へと進む。ステップ１５１６において、アクティブセグメントテーブル中の次の点がＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔとして選択される。点が存在しない場合、プロセス１５００はステップ１５１８へと進む。ステップ１５１８において、ＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔは現在のセグメントに対する終端頂点のｘ座標（すなわち、ｘmax）を含むように設定される。プロセス１５００は次のステップ１５０８へと続く。ステップ１５０８において、セグメントテーブルに更に点が存在しない場合、プロセス１５００はステップ１５０６へと戻る。点が存在する場合、プロセス１５００はステップ１５０７へと進む。ステップ１５０７において、プロセッサ３０５によりＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔとしてセグメントテーブル中の次の点が選択され、プロセス１５００はステップ１５０５へと戻る。
【００５４】
ステップ１５０１の結果が真の場合、プロセス１５００はステップ１５２５へと進む。ステップ１５２５において、アクティブセグメントテーブルに更に点が存在する場合、次のステップ１５２４においてｃｕｒｒｅｎｔ＿ｐｏｉｎｔの後の点がＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔとして選択される。点が存在しない場合、プロセス１５００はステップ１５２６へと進む。ステップ１５２６において、ＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔは、現在のセグメントに対する終端頂点のｘ座標（すなわち、ｘmax）を含むように設定される。
【００５５】
ステップ１５０５の結果が偽の場合、プロセス１５００はステップ１５１０へと進む。ステップ１５１０において、ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔがＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔと等しい場合、プロセス１５００はステップ１５３２へと進む。ステップ１５３２において、ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔが現在のセグメントに対する終端頂点のｘ座標（すなわち、ｘmax）より小さい場合、プロセス１５００はステップ１５１４へと進む。ステップ１５１４において、プロセッサ３０５により現在のセグメント上で水平セグメント分割プロセス１６００が実行される。ステップ１５３２において、ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔが現在のセグメントに対する終端頂点のｘ座標（すなわち、ｘmax）より大きい場合、プロセス１５００はステップ１５３０へと進む。ステップ１５３０において、ステップ６０３（又は１０１７）で選択されたセグメントがメモリ３０６に格納されたアクティブセグメントテーブルに挿入される。ステップ１５３０の後、プロセス１５００は終了し、プロセス９００のステップ９１５へと進む。
【００５６】
ステップ１５１０において、ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔがＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔと等しくない場合、プロセス１５００はステップ１５１１へと進む。ステップ１５１１において、ＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔが現在のセグメントに対する終端頂点のｘ座標（すなわち、ｘmax）より小さい場合、プロセス１５００はステップ１５３４へと進む。現在のセグメントに対する終端頂点のｘ座標より大きいか、あるいは、それと等しい場合、プロセス１５００はステップ１５３０へと進む。ステップ１５３４において、プロセッサ３０５により現在のセグメント上で水平セグメント分割プロセス１６００が実行される。
【００５７】
次のステップ１５１３において、ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔが現在のセグメントに対する終端頂点のｘ座標（すなわち、ｘmax）より小さい場合、プロセスはステップ１５１４へと進む。現在のセグメントに対する終端頂点のｘ座標より大きいか、あるいは、それと等しい場合、プロセスはステップ１５２１へと進む。
【００５８】
ステップ１５１４が現在のセグメント上で実行された後、プロセス１５００は次のステップ１５１９へと続く。ステップ１５１９において、セグメントテーブルに更にセグメントが存在する場合、プロセスはステップ１５２０へと進む。ステップ１５２０において、プロセッサ３０５によりＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔとしてセグメントテーブル中の次の点が選択され、プロセス１５００はステップ１５２１へと進む。ステップ１５１９の結果が偽の場合、ＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔは現在のセグメントに対する終端頂点のｘ座標（すなわち、ｘmax）を含むように設定される。
【００５９】
ステップ１５２１において、アクティブセグメントテーブルに更に点が存在する場合、ステップ１５２２において、プロセッサ３０５によりＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔとしてアクティブセグメントテーブル中の次の点が選択され、プロセス１５００はステップ１５０５へと戻る。点が存在しない場合、プロセス１５００はステップ１５２３へと進む。ステップ１５２３において、ＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔは現在のセグメントに対する終端頂点のｘ座標（すなわち、ｘmax）を含むように設定され、プロセスはステップ１５０５へと進む。
【００６０】
図１６は水平セグメントを分割する水平セグメント分割プロセス１６００の各ステップを示すフローチャートである。プロセス１６００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス１６００はステップ１６０１で開始される。ステップ１６０１において、座標(split_point,ybucket)により定義される点で開始し、現在のセグメント（すなわち、ＳＴ＿ｓｅｇｍｅｎｔ）の終端頂点で終了する新規のセグメントが作成される。ここに記載する方法によると、ラベルｓｐｌｉｔ＿ｐｏｉｎｔにより定義される点は、水平分割プロセス１５００においてどの場所にあったかによって、ＡＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔ及びＳＴ＿ｓｐｌｉｔ＿ｐｏｉｎｔのいずれかの値をとる。プロセス１６００の次のステップ１６０３において、現在のセグメント（すなわち、ＳＴ＿ｓｅｇｍｅｎｔ）は座標(split_point,ybucket)により定義される点において終了させられる。プロセス１６００は次のステップ１６０５へと続く。ステップ１６０５では、プロセッサ３０５によりアクティブセグメントテーブルの始点における全ての終了セグメントの後に、終了したセグメントが挿入される。プロセス１６００はステップ１６０７で終了する。ステップ１６０７において、新規のセグメントがＳＴ＿ｓｅｇｍｅｎｔとして設定される。
【００６１】
図１７は、バンドライン１７００に対するセグメント１７０１上で実行中の水平分割プロセス１５００の一例を示す。図１７に示すように、水平分割プロセス１５００（矢印により表される）がセグメント１７０１上で実行された後、新規のセグメント１７０３、１７０５、及び１７０７が作成される。セグメント１７０３は点Ａで開始し、座標(split_point,ybucket)により定義される点で終了する。
【００６２】
図６Ａのプロセス６００に戻ると、ステップ６０５において、メモリ３０６に格納されたアクティブセグメントテーブルがプロセッサ３０５及び処理される現在のバケットの全てのアクティブセグメントにより更新された後、プロセス６００はステップ６０７へと進む。ステップ６０７において、プロセッサ３０５により図１８に示すような「セグメント割当て／エッジ作成」プロセス１８００が実行される。単純輪郭パスを形成するエッジが作成され、境界線セグメントが作成されたエッジに割り当てられる。セグメント割当て／エッジ作成プロセス１８００は、奇偶ワインディング塗りつぶし規則を用いて構成された入力パスに対してと、ノンゼロワインディング塗りつぶし規則を用いて構成された入力パスに対してでは異なる。
【００６３】
図１８はノンゼロワインディング塗りつぶし規則を用いて構成された入力パスに対して単純輪郭パスを形成するエッジを作成するセグメント割当て／エッジ作成プロセス１８００を示すフローチャートである。プロセス１８００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス１８００は第１のステップ１８０１で開始される。ステップ１８０１において、グローバルカウンタ（ｇ＿ｃｏｕｎｔｅｒとラベル付けされ、メモリ３０６内に格納されるのが好ましい）が０にリセットされる。グローバルカウンタ（すなわち、ｇ＿ｃｏｕｎｔｅｒ）は新規の境界線セグメントを識別するために使用され、ノンゼロワインディング塗りつぶし規則に基づいて常時更新され、セグメントに対する正確なカウンタ値を常に反映する。また、ステップ１８０１において、水平カウンタ（ｈ＿ｃｏｕｎｔｅｒとラベル付けされ、メモリ３０６に格納されるのが好ましい）が現在のバケットにおいて水平セグメントが見出されないことを示すＩＮＡＣＴＩＶＥにリセットされる。ある点において水平セグメントが見出されるときには、水平カウンタ（ｈ＿ｃｏｕｎｔｅｒ）はプロセッサ３０５によりＡＣＴＩＶＥに設定され、水平セグメントが現れるのを待って次のポイントでリセットされる（すなわち、ＩＮＡＣＴＩＶＥになる）。次のステップ１８０３において、プロセッサ３０５によりアクティブセグメントテーブルから点が選択され、その点が現在の点（すなわち、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔ）として割り当てられる。アクティブセグメントテーブルは、ｘ座標の昇順で左から右へと点ごとに処理される。プロセス１８００はステップ１８０５へと続く。ステップ１８０５において、全ての点に対して、点を「複合点」又は「ローカル最小点」として分類するために、プロセッサ３０５により現在の点の第１のセグメントが検査される。複合点は、その上で終了する第１のセグメントを有する点である。ローカル最小点は、そこから開始される第１のセグメントを有する点である。直前の点で開始し、現在の点で終了する水平セグメントも考慮しなければならない。現在の点を通過する単一のセグメントは無視される。ステップ１８０５において、ステップ１８０３で選択された点が複合点であるか、あるいは、前の点が選択された点で終了する水平セグメントを有する場合、プロセス１８００はステップ１８０７へと進む。ステップ１８０７において、ステップ１８０３で選択された点は、ノンゼロワインディング塗りつぶし規則を用いて構成された入力パスに対して「複合点」プロセス２１００により処理される。このプロセス２１００は図２１のフローチャートを参照して説明する。プロセス２１００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。
【００６４】
プロセス２１００のステップ２１０１から２１０７は、現在の点（すなわち、ステップ１８０３で選択され、ラベルｃｕｒｒｅｎｔ＿ｐｏｉｎｔを割り当てられた点）で終了する第１の境界線セグメントを識別する。この処理は検索を伴い、検索は直前の点で開始し、現在の点で終了するいずれかの境界線水平セグメントを含まなければならない。また、ステップ２１０１から２１０７は、現在の点で終了する最後の境界線セグメントを識別する。プロセス２１００のステップ２１０９及び２１１１は、境界線セグメントの全てのエッジに対して新規の頂点を作成する。更に、現在の点で終了するエッジの左右のセグメントにより示される閉じたエッジが、全ての非境界線終了セグメントと共に現在の点から除去される。プロセス２１００はステップ２１０１で開始される。ステップ２１０１において、プロセッサ３０５により検査が実行され、前の点が上述のようにそこから開始される水平セグメントを有するか否かが判定される。ステップ２１０１の結果が真の場合、プロセス２１００はステップ２１０３へと進む。ステップ２１０３において、このような水平セグメントが存在する場合、第１の終了セグメントバッファ（ラベルｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔが割り当てられるのが好ましい）は、第１の境界線水平セグメントを含むように設定される。水平セグメントが存在しない場合、ｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファは現在の点の第１の終了セグメントを含むように設定される。ステップ２１０１の結果が偽の場合、ｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファは、現在の点においてｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｂｏｒｄｅｒセグメントを含むように設定される。次のステップ２１０７において、最後の終了セグメントバッファ（ラベルｌａｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔが割り当てられるのが好ましい）がプロセス１８００のステップ１８０３で選択された点の最後の終了境界線セグメントを含むように設定される。プロセス２１００はステップ２１０９へと続く。ステップ２１０９において、ｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファ及びｌａｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファにより示される両端を含むセグメント間の全ての終了境界線セグメントに対して、各セグメントが「左」の境界線セグメントとして分類されたか、あるいは、「右」の境界線セグメントとして分類されたかによって、点(xcur,ybucket)により定義される頂点を伴うノードが、プロセッサ３０５により第１の終了セグメント及び最後の終了セグメントの各エッジの左ウィング又は右ウィングに挿入される。左境界線セグメント又は右境界線セグメントとしてセグメントを分類するための必要条件を図２０に示す。これに関連して、ここに記載する方法は、メモリ３０６内に構成されるのが好ましいカウンタを利用する。このカウンタは各セグメントに割り当てられる。上述のようにセグメントが上向きのセグメントであり、特定のセグメントと関連付けられたカウンタが０の値を有する場合、あるいは、セグメントが下向きのセグメントであり、セグメントと関連付けられたカウンタが０の値を有する場合、セグメントは左境界線セグメントとして分類される。これに対し、セ���メントが下向きのセグメントであり、セグメントと関連付けられたカウンタが１の値を有する場合、あるいは、セグメントが上向きのセグメントであり、関連付けられたカウンタが−１の値を有する場合、セグメントは右境界線セグメントとして分類される。
【００６５】
プロセス２１００はステップ２１１１へと続く。ステップ２１１１において、プロセッサ３０５によりアクティブセグメントテーブルから同じエッジに属する全ての終了境界線セグメント及び現在の点上の全ての非境界線終了セグメントが除去される。プロセス２１００のステップ２１１３から２１１７において、セグメント結合／エッジ作成プロセス２２００により現在の点から開始されるセグメントが処理される。このセグメント結合／エッジ作成プロセス２２００により、現在の点から開始される各境界線セグメントに対して、新規のエッジが作成される。セグメント結合／エッジ作成プロセス２２００については図２２のフローチャートを参照して後述する。ステップ２１１５において境界線セグメントが残っている場合、セグメント結合プロセス３３００により、残ったセグメントは第１の終了セグメントに結合される。セグメント結合プロセス３３００については図３３のフローチャート３３００を参照して後述する。
【００６６】
プロセス２１００のステップ２１１３において、検査が実行され、現在の点で開始するセグメントが存在するか否かが判定される。ステップ２１１３の結果が偽の場合、ステップ２１１７において、プロセッサ３０５によりアクティブセグメントテーブルから現在の点上の残り全ての終了セグメントが除去される。ステップ２１１３の結果が真の場合、プロセス２１００はステップ２１１５へと進む。ステップ２１１５において、プロセッサ３０５によりセグメント結合／エッジ作成プロセス２２００が実行される。
【００６７】
図２２において明らかなように、プロセス２２００は現在の点で開始するセグメント（以降、選択されたセグメントと呼ぶ）の選択と共にステップ２２０１で開始される。上述のように、プロセッサ３０５により現在のバンドラインに対してレフトネスの降順でセグメントが選択される。次のステップ２２０３において、プロセス２２００はステップ２２０３へと進む。ステップ２２０３において、ステップ２２０１で選択されたセグメントに対してカウンタ更新プロセスが実行される。図３４において明らかなように、カウンタ更新プロセス３４００は、グローバルカウンタ（すなわち、ｇ＿ｃｏｕｎｔｅｒ）の値をステップ２２０１で選択された現在のセグメントに割り当て、セグメントの方向に基づいてグローバルカウンタを更新する。ステップ２２０１で選択されたセグメントが水平セグメントの場合、水平フラグ（すなわち、ｈ＿ｆｌａｇ）はｇ＿ｃｏｕｎｔｅｒの値を含むように設定される。図３４のフローチャートを参照してカウンタ更新プロセス３４００を以下で説明する。
【００６８】
カウンタ更新プロセス３４００は、プロセス２２００中にグローバルフラグ及び水平フラグを更新する。プロセス３４００はステップ３４０１で開始される。ステップ３４０１において、検査が実行され、ステップ２２０１で選択された現在のセグメントが水平セグメントであるか否かが判定される。ステップ３４０１において、ステップ２２０１で選択された現在のセグメントが水平セグメントでない場合、プロセス３４００はステップ３４０３へと進む。ステップ３４０３において、セグメントと関連付けられたカウンタが、メモリ３０６に格納されたｇ＿ｃｏｕｎｔｅｒの値に設定される。ｇ＿ｃｏｕｎｔｅｒの値は、ステップ２２０１で選択されたセグメントの方向に基づいて更新される。ｇ＿ｃｏｕｎｔｅｒが更新されると、プロセス３４００は終了する。
【００６９】
ステップ３４０１において、ステップ２２０１で選択された現在のセグメントが水平セグメントである場合、プロセス３４００はステップ３４０７へと進む。ステップ３４０７において、上述のように、ｈ＿ｆｌａｇがＩＮＡＣＴＩＶＥに設定されている場合、プロセスはステップ３４０９へと進む。ステップ３４０９において、ｈ＿ｆｌａｇはメモリに格納されたｇ＿ｃｏｕｎｔｅｒの値に設定される。ステップ３４０７において、ｈ＿ｆｌａｇがＩＮＡＣＴＩＶＥに設定されていない場合、プロセス３４００は直接次のステップ３４１１へと進む。ステップ３４１１において、ステップ２２０１で選択されたセグメントと関連付けられたカウンタはｈ＿ｆｌａｇを含むように設定される。次のステップ３４１３において、プロセッサ３０５によりステップ２２０１で選択されたセグメントの方向に基づいてｈ＿ｆｌａｇの値が更新され、プロセス３４００は終了する。
【００７０】
プロセス２２００に戻ると、次のステップ２２０５において、プロセッサ３０５によりステップ２２０１で選択されたセグメントと関連付けられたカウンタが検査され、図２０を参照して先に述べたように、ステップ２２０１で選択された現在のセグメントが左境界線セグメントであるか否かが判定される。ステップ２２０５の結果が真の場合、プロセス２２００はステップ２２０７へと進む。ステップ２２０７において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファが空の場合、プロセス２２００はステップ２２０９へと進む。ステップ２２０９において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファはステップ２２０１で選択されたセグメントを指し示すように設定され、選択されたセグメントは左セグメントとしてマーク付けされる。プロセス２２００はステップ２２１１へと続く。ステップ２２１１において、現在の点に更にセグメントが存在する場合、プロセス２２００はステップ２２０１へと戻る。
【００７１】
ステップ２２０５の結果が偽の場合、プロセス２２００はステップ２２１３へと進む。ステップ２２１３において、プロセッサ３０５によりセグメントと関連付けられたカウンタが検査され、図１７を参照して先に述べたように、ステップ２２０１で選択された現在のセグメントが右境界線セグメントであるのか否かが判定される。ステップ２２１３の結果が真の場合、プロセス２２００はステップ２２１５へと進む。ステップ２２１５において、ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファが空の場合、プロセス２２００はステップ２２１７へと進む。ステップ２２１７において、ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファはステップ２２０１で選択されたセグメントを含むように設定され、選択されたセグメントは右セグメントとしてマーク付けされる。ステップ２２１７の後、プロセス２２００はステップ２２１１へと続く。ステップ２２１１において、現在の点に更にセグメントが存在する場合、プロセス２２００はステップ２２０１へと戻る。
【００７２】
ステップ２２０７の結果が偽の場合、プロセス２２００は直接ステップ２２１９へと進む。ステップ２２１９において、ｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファがステップ２２０１で選択されたセグメントを含むように設定され、選択されたセグメントは左セグメントとしてマーク付けされる。次のステップ２２２１において、ｌａｓｔ＿ｓｅｇｍｅｎｔポインタがｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファを指し示すように設定される。同様に、ステップ２２１５の結果が偽の場合、プロセス２２００は直接ステップ２２２３へと進む。ステップ２２２３において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファがステップ２２０１で選択されたセグメントを含むように設定され、選択されたセグメントは右セグメントとしてマーク付けされる。次のステップ２２２５において、ｌａｓｔ＿ｓｅｇｍｅｎｔポインタがｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファを指し示すように設定される。
【００７３】
図２２に示すように、プロセス２２００は次のステップ２２２７へと続く。ステップ２２２７において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファ及びｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファの双方が空でない場合、プロセス２２００はステップ２２１１へと進む。バッファのいずれか又は双方が空の場合、プロセス２２００はステップ２２２９へと進む。ステップ２２２９において、プロセッサ３０５によりバッファリングされたセグメント上でエッジ作成プロセスが実行され、新規のエッジが作成される。エッジ作成プロセス３５００が実行される前に、４つの境界線セグメント（すなわち、２つの左境界線セグメント及び２つの右境界線セグメント）がバッファリングされるのが好ましい。図３５のフローチャートを参照してエッジ作成プロセス３５００を説明する。
【００７４】
新規のエッジを作成するとき、相互に重なったセグメント（すなわち、共直線セグメント）に優先度が与えられる。作成された新規のエッジは、現在の点から開始されるものとしてマーク付けされ、特定のエッジの各々を形成する２つのエッジは、２つのセグメントが形成するエッジが所有するものとして割り当てられる。プロセス３５００はステップ３５０１で開始される。ステップ３５０１において、ｌａｓｔ＿ｓｅｇｍｅｎｔポインタがｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファを指し示す場合、プロセス３５００はステップ３５０３へと進む。ステップ３５０３において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファ及びｌｅｆｔ＿ｓｅｇｍｅｎｔバッファの双方に含まれる各セグメントに共直線性がある場合、プロセス３５００はステップ３５０５へと進む。ステップ３５０５において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファ及びｌｅｆｔ＿ｓｅｇｍｅｎｔバッファにより指し示される各セグメントを伴って新規のエッジが作成される。次のステップ３５０７において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファはｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファに設定され、プロセス３５００は終了する。
【００７５】
ステップ３５０３において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファ及びｌｅｆｔ＿ｓｅｇｍｅｎｔバッファにより指し示される各セグメントに共直線性がない場合、プロセス３５００はステップ３５０９へと進む。ステップ３５０９において、プロセッサ３０５によりｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファ及びｌｅｆｔ＿ｓｅｇｍｅｎｔバッファに含まれる各セグメントを伴って新規のエッジが作成される。次のステップ３５１１において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファはｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファを指し示すように設定され、ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファはｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファに設定され、プロセス３５００は終了する。
【００７６】
ステップ３５０１において、ｌａｓｔ＿ｓｅｇｍｅｎｔポインタがｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファを指し示していない場合、プロセス３５００はステップ３５１３へと進む。ステップ３５１３において、ｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファ及びｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファに共直線性がある場合、プロセス３５００はステップ３５１５へと進む。共直線性がない場合、プロセス３５００はステップ３５０９へと進む。ステップ３５１５において、ｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファ及びｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファにより指し示される各セグメントを伴って新規のエッジが作成される。プロセス３５００は次のステップ３５１７で終了する。ステップ３５１７において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファはｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファに設定される。
【００７７】
プロセス２２００に戻ると、ステップ２２１１において、現在の点に更にセグメントが存在しない場合、プロセス２２００はステップ２２３１へと進む。ステップ２２３１において、プロセッサ３０５によって現在の点に対してセグメント結合プロセス３３００が実行される。上述のように、プロセス３３００は、残りの境界線セグメントを第１の終了セグメントへと結合する。プロセス２２００は次のステップ２２３３で終了する。ステップ２２３３において、ｈ＿ｆｌａｇはＩＮＡＣＴＩＶＥに設定される。ここに記載する方法に従って、セグメント結合プロセス３３００を説明する。プロセス３３００はハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。
【００７８】
プロセス３３００はステップ３３０１で開始される。ステップ３３０１において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファ及びｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファの双方が空でない場合、プロセスはステップ３３０３へと進む。ステップ３３０３において、ｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファ及びｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファのいずれかが空でない場合、プロセス３３００はステップ３３０５へと進む。ステップ３３０５において、プロセッサ３０５により検査が実行され、ｌａｓｔ＿ｓｅｇｍｅｎｔポインタがｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファを指し示すか否かが判定される。ステップ３３０５の結果が真の場合、プロセス３３００はステップ３３０７へと進む。ステップ３３０７において、ｌａｓｔ＿ｓｅｇｍｅｎｔポインタはｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファを指し示すように設定される。ステップ３３０５の結果が偽の場合、プロセス３３００はステップ３３０９へと進む。ステップ３３０９において、ｌａｓｔ＿ｓｅｇｍｅｎｔポインタはｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファを指し示すように設定される。プロセス３３００は次のステップ３３１１へと続く。ステップ３３１１において、残ったセグメントに対してエッジ作成プロセス３５００が実行される。次のステップ３３１３において、残ったセグメントは第１の終了セグメント（ｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔとラベル付けされるのが好ましい）のエッジへと割り当てられる。また、ステップ３３１３において、残ったセグメントは第１の終了セグメントによって左又は右としてマーク付けされる。
【００７９】
ステップ３３０１の結果が偽の場合、プロセス３３００はステップ３３１７へと進む。ステップ３３１７において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファ及びｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファのいずれかが空でない場合、プロセス３３００はステップ３３１３へと進む。ステップ３３０１の結果が真の場合、プロセス３３００は直接ステップ３３１９へと進む。ステップ３３０３の結果が偽の場合、プロセス３３００はステップ３３１９へと進む。ステップ３３１９において、左セグメント（すなわち、ｌｅｆｔ＿ｓｅｇｍｅｎｔ）及び右セグメント（ｒｉｇｈｔ＿ｓｅｇｍｅｎｔ）を伴って新規のエッジが作成される。プロセス３３００はステップ３３１９の終了後に終了する。
【００８０】
プロセス１８００に戻ると、第１の点が複合点でない場合、プロセス１８００はステップ１８０９へと進む。ステップ１８０９において、現在の点（すなわち、ステップ１８０３で選択された点）からの第１のセグメントが現在のバンドラインで開始されない場合、プロセス１８００はステップ１８１５へと進む。ステップ１８１５において、プロセッサ３０５により現在の点（すなわち、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔ）を通過するセグメントの方向に基づいてｇ＿ｃｏｕｎｔｅｒが更新される。次のステップ１８１３において、アクティブセグメントテーブルに更に点が残っている場合、プロセス１８００はステップ１８０３へと戻る。点が残っていない場合、プロセス１８００は終了し、プロセス６００のステップ６０９へと進む。また、ステップ１８０９において、ステップ１８０３で選択された現在の点の第１のセグメントが現在のバンドラインで開始される場合、その点はローカル最小点として分類され、ステップ１８１３に進む前に次のステップ１８１１において、ノンゼロワインディング塗りつぶし規則を用いて構成された入力パスに対するローカル最小点プロセスにより処理される。図１９のフローチャートを参照して、ノンゼロワインディング塗りつぶし規則を用いて構成された入力パスに対するローカル最小点プロセス１９００を説明する。プロセス１９００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。
【００８１】
ローカル最小点プロセス１９００によると、セグメントが配列される順序（すなわち、レフトネスの降順）に一度に１つずつセグメントが処理される。ローカル最小点に対しては、全てのセグメントが新規である（すなわち、全てのセグメントは現在のバンドラインで開始される）。このため、各セグメントに対してグローバルカウンタ（すなわち、ｇ＿ｃｏｕｎｔｅｒ）が割り当てられ、プロセッサ３０５によりカウンタ更新プロセス３４００を利用してローカル最小点で各セグメントの方向に基づいて更新される。プロセス１９００はステップ１９０１で開始される。ステップ１９０１において、プロセッサ３０５によりレフトネスの降順に現在の点（すなわち、ステップ１８０３で選択された点）からのセグメントが選択される。次のステップ１９０３において、プロセス１９００はステップ１９０３へと進む。ステップ１９０３において、ステップ１９０１で選択されたセグメントに対してカウンタ更新プロセス３４００が実行される。
【００８２】
上述のように、カウンタ更新プロセス３４００はステップ１９０１で選択された現在のセグメントと関連付けられたカウンタの値を割り当て、セグメントの方向に基づいてカウンタを更新する。
【００８３】
プロセス１９００の次のステップ１９０５において、ステップ１９０１で選択されたセグメントが左境界線セグメントであるか否かを判定するために、セグメントの方向と共にステップ１９０１で選択されたセグメントと関連付けられたカウンタが検査される（すなわち、ステップ１９０１で選択されたセグメントと関連付けられたカウンタ及び方向が、セグメントが左境界線セグメントか、あるいは、右境界線セグメントかを示す。例えば、セグメントと関連付けられたカウンタが０の値を有し、セグメントが上向きのセグメントである場合、セグメントは上向きの左境界線セグメントとして分類される）。ステップ１９０５の結果が真の場合、プロセス１９００はステップ１９０７へと進む。ステップ１９０７において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファが空の場合、プロセス１９００はステップ１９０９へと進む。ステップ１９０９において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファはプロセッサ３０５によりステップ１９０１で選択されたセグメントを含むように設定され、選択されたセグメントは左セグメントとしてマーク付けされる。プロセスはステップ１９１１へと続く。ステップ１９１１において、現在の点に更にセグメントが存在する場合、プロセス１９００はステップ１９０１へと戻る。
【００８４】
ステップ１９０５の結果が偽の場合、プロセス１９００はステップ１９１３へと進む。ステップ１９１３において、現在のセグメント及び現在のセグメントの方向と関連付けられたカウンタが検査され、図１７を参照して先に述べたように、ステップ１９０１で選択されたセグメントが右境界線セグメントであるか否かを検査するために、プロセッサ３０５によりセグメントの方向が判定される。ステップ１９１３の結果が真の場合、プロセス１９００はステップ１９１５へと進む。ステップ１９１５において、ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファが空の場合、プロセス１９００はステップ１９１７へと進む。ステップ１９１７において、ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファはステップ１９０１で選択されたセグメントを含むように設定され、選択されたセグメントは右セグメントとしてマーク付けされる。ステップ１９１７の後、プロセス１９００はステップ１９１１へと続く。ステップ１９１１において、現在の点に更にセグメントが存在する場合、プロセス１９００はステップ１９０１へと戻る。
【００８５】
ステップ１９０７の結果が偽の場合、プロセス１９００は直接１９１９へと進む。ステップ１９１９において、ステップ１９０１で選択されたセグメントを含むようにｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファが設定され、プロセッサ３０５により選択されたセグメントが左セグメントとしてマーク付けされる。次のステップ１９２１において、プロセッサ３０５によりｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファを指し示すようにｌｅｆｔ＿ｓｅｇｍｅｎｔポインタが設定される。同様に、ステップ１９１５の結果が偽の場合、プロセス１９００は直接ステップ１９２３へと進む。ステップ１９２３において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファはステップ１９０１で選択されたセグメントを含むように設定され、選択されたセグメントは右セグメントとしてマーク付けされる。次のステップ１９２５において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファを指し示すようにｌａｓｔ＿ｓｅｇｍｅｎｔポインタが設定される。
【００８６】
上述のように、新規のエッジを作成するときに、共直線セグメントに優先度が与えられる。作成された新規のエッジは、現在の点から開始されるものとしてマーク付けされ、特定のエッジの各々を形成する２つのエッジは、２つのセグメントが形成するエッジが所有するものとして割り当てられる。共直線セグメントに対して優先度を確立するために、上述のように新規のエッジを作成するに先立って、２つの左セグメント及び２つの右セグメントがバッファリングされる。左セグメント及び右セグメントがバッファリングされるとすぐに、新規のエッジを作成し、現在の点から開始されるものとしてマーク付けすることができる。新規のエッジの左セグメント及び右セグメントはそれぞれ左及び右としてマーク付けされ、新規に作成されたエッジが所有するものとして割り当てられる。当業者は、ローカル最小点における境界線セグメントの本数が常に偶数であり、左セグメントと右セグメントは常に等しい本数であることを理解するであろう。このため、プロセス１９００は図１９に示すように次のステップ１９２７へと続く。ステップ１９２７において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファ及びｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファの双方が空の場合、プロセス１９００はステップ１９１１へと進む。いずれかが空、または、いずれも空でない場合、プロセス１９００はステップ１９２９へと進む。ステップ１９２９において、プロセッサ３０５によりバッファリングされたセグメントに対してエッジ作成プロセス３５００が実行される。
【００８７】
ステップ１９２９においてプロセス３５００が実行された後、プロセス１９００はステップ１９１１へと進む。ステップ１９１１において現在の点にセグメントが残っていない場合、プロセスはステップ１９３１へと進む。ステップ１９３１において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファ及びｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファの双方が空でない場合、プロセスはステップ１９３３へと進む。ステップ１９３３において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファ及びｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファにより指し示されるセグメントを伴って新規のエッジが作成される。ステップ１９３３の後、フローチャート１９００の処理はステップ１９３５へと進む。ステップ１９３５において、水平カウンタ（すなわち、ｈ＿ｃｏｕｎｔｅｒ）はプロセッサ３０５によりＩＮＡＣＴＩＶＥに設定される。ステップ１９３１において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファ及びｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファの双方が空の場合、フローチャート１９００のプロセスは直接ステップ１９３５へと進む。ステップ１９３５において、フローチャート１９００の処理は終了し、フローチャート１８００のステップ１８１３へと進む。
【００８８】
図２３は、奇偶ワインディング塗りつぶし規則を用いて構成された入力パスに対する単純輪郭パスを形成するエッジを作成するセグメント割当て／エッジ作成プロセス２３００を示すフローチャートである。ノンゼロワインディング塗りつぶし規則を用いて構成されたパスに対するフローチャート１８００のセグメント割当て／エッジ作成プロセスとは対照的に、奇偶ワインディング塗りつぶし規則を用いて構成されたパスの全てのセグメントは境界線セグメントである。更に、フローチャート１８００のプロセスではグローバルカウンタ（すなわち、ｇ＿ｃｏｕｎｔｅｒ）が使用されるのに対して、図２３のプロセスではグローバルフラグ（ｇ＿ｆｌａｇとラベル付けされるのが好ましい）が使用される。グローバルフラグは、境界線セグメントをエッジの左／右セグメントに分類するのに使用され、ＲＩＧＨＴに初期化される。プロセス２３００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。
【００８９】
プロセス２３００はステップ２３０１で開始される。ステップ２３０１において、メモリ３０６に格納されたｇ＿ｆｌａｇとしてラベル付けされるバッファがＲＩＧＨＴに初期化される。次のステップ２３０３において、プロセッサ３０５によりアクティブセグメントテーブルから点が選択される。アクティブセグメントテーブルは、ｘ座標の昇順で左から右へと点ごとに処理される。プロセス２３００はステップ２３０４へと続く。ステップ２３０４において、全ての点に対して、その点を「複合点」又は「ローカル最小点」として分類するために、プロセッサ３０５によりその点における第１のセグメントが検査される。その点からの第１のセグメントが現在のバンドラインで終了するか、あるいは、前の点がステップ２３０３で選択された点上で終了する水平セグメントを有する場合、ステップ２３０３で選択された点は複合点として分類される。点を通過する単一セグメントは無視される。次のステップ２３０７において、ステップ２３０３で選択された点からの第１のセグメントが現在のバンドラインで開始される場合、その点はローカル最小点として分類され、ステップ２３１１に進む前に次のステップ２３０９において、奇偶ワインディング塗りつぶし規則を用いて構成された入力パスに対して図２４に示すようなローカル最小点プロセス２４００により処理される。現在のバンドラインで開始されない場合、プロセス２１００はステップ２３１３へと進む。ステップ２３１３において、ｇ＿ｆｌａｇがＲＩＧＨＴに設定されている場合、プロセス２３００はステップ２３１７へと進む。ステップ２３１７において、ｇ＿ｆｌａｇはＬＥＦＴに設定される。ステップ２３１３において、ｇ＿ｆｌａｇがＲＩＧＨＴに設定されていない場合、プロセス２３００はステップ２３１５へと進む。ステップ２３１５において、プロセスがステップ２３１１へと進む前にｇ＿ｆｌａｇがＲＩＧＨＴに設定される。図２４のフローチャート２４００を参照して、奇偶ワインディング塗りつぶし規則を用いて構成された入力パスに対するローカル最小点プロセス２４００の説明を行なう。
【００９０】
ローカル最小点に対して、全てのセグメントは新規である（すなわち、全てのセグメントは現在のバンドラインで開始される）。グローバルフラグ（すなわち、ｇ＿ｆｌａｇ）は、第１のセグメントが左セグメントとしてマーク付けされるか、あるいは、右セグメントとしてマーク付けされるかを判定するのに使用される。左右交互にマーク付けすることによって後続のセグメントがマーク付けされる。現在の点に対する左右のセグメントの各対は、ここに記載する方法により生成される単純輪郭パスにおいてエッジを形成することになる。プロセス２４００はステップ２４０１で開始される。ステップ２４０１において、レフトネスの降順に現在の点（ステップ２３０３で選択された点）からセグメントが選択される。次のステップ２４０３において、第１のセグメントが左セグメントとしてマーク付けされているか、あるいは、右セグメントとしてマーク付けされているかを判定するため及び左右交互にマーク付けすることによって後続のセグメントをマーク付けするために現在の点に対して図３６に示すような境界線セグメント選択プロセス３６００が実行される。図３６のフローチャート３６００を参照して境界線セグメント選択プロセスを説明する。プロセス３６００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。
【００９１】
プロセス３６００はステップ３６０１で開始される。ステップ３６０１において、プロセッサ３０５により検査が実行され、ｇ＿ｆｌａｇがＲＩＧＨＴに設定されているか否かが判定される。ステップ３６０１の結果が真の場合、プロセス３６００はステップ３６０２へと進む。ステップ３６０２において、検査が実行され、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファが空か否かが判定される。ステップ３６０２の結果が真の場合、プロセス３６００はステップ３６０５へと進む。ステップ３６０５において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファはステップ２４０１で選択されたセグメントを含むように設定され、選択されたセグメントは左セグメントとしてマーク付けされる。次のステップ３６０７において、プロセッサ３０５によりレフトネスの降順に現在の点（すなわち、ステップ２３０３で選択された点）からの次のセグメントが選択される。プロセス３６００は次のステップ３６０９へと続く。ステップ３６０９において、ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファはステップ３６０７で選択されたセグメントを含むように設定され、ステップ３６０７で選択されたセグメントは右セグメントとしてマーク付けされる。プロセス３６００は終了し、プロセス２４００のステップ２４０５へと進む。
【００９２】
ステップ３６０２の結果が偽の場合、プロセス３６００はステップ３６１１へと進む。ステップ３６１１において、ｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファはステップ２４０１で選択されたセグメントを含むように設定され、選択されたセグメントは左セグメントとしてマーク付けされる。次のステップ３６１３において、プロセッサ３０５によりレフトネスの降順に現在の点（すなわち、ステップ２３０３で選択された点）からの次のセグメントが選択される。プロセス３６００は次のステップ３６１５へと続く。ステップ３６１５において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファはステップ３６１３で選択されたセグメントを含むように設定され、ステップ３６１３で選択されたセグメントは右セグメントとしてマーク付けされる。次のステップ３６１７において、ｌａｓｔ＿ｓｅｇｍｅｎｔポインタは、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファを指し示すように設定される。プロセス３６００は終了し、プロセス２４００のステップ２４０５へと進む。
【００９３】
ステップ３６０１の結果が偽の場合、プロセス３６００はステップ３６１９へと進む。ステップ３６１９において、プロセッサ３０５により検査が実行され、ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファが空であるか否かが判定される。ステップ３６１９の結果が真の場合、プロセス３６００はステップ３６２１へと進む。ステップ３６２１において、ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファはステップ２４０１で選択されたセグメントを含むように設定され、選択されたセグメントは右セグメントとしてマーク付けされる。次のステップ３６２３において、プロセッサ３０５によりレフトネスの降順に現在の点（すなわち、ステップ２３０３で選択された点）からの次のセグメントが選択される。プロセスは次のステップ３６２５へと続く。ステップ３６２５において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファはステップ３６２３で選択されたセグメントを含むように設定され、ステップ３６２３で選択されたセグメントは右セグメントとしてマーク付けされる。プロセス３６００は終了し、プロセス２４００のステップ２４０５へと進む。
【００９４】
ステップ３６１９の結果が偽の場合、プロセス３６００はステップ３６２７へと進む。ステップ３６２７において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファはプロセッサ３０５によりステップ２４０１で選択されたセグメントを含むように設定され、選択されたセグメントは右セグメントとしてマーク付けされる。次のステップ３６２９において、プロセッサ３０５によりレフトネスの降順に現在の点（すなわち、ステップ２３０３で選択された点）からの次のセグメントが選択される。プロセス３６００は次のステップ３６３１へと続く。ステップ３６３１において、ｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファはステップ３６２９で選択されたセグメントを含むように設定され、ステップ３６２９で選択されたセグメントは左セグメントとしてマーク付けされる。次のステップ３６３３において、ｌａｓｔ＿ｓｅｇｍｅｎｔポインタはｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファを指し示すように設定される。プロセス３６００は終了し、フローチャート２４００のステップ２４０５へと進む。
【００９５】
プロセス２４００へと戻ると、ステップ２４０３において現在の点（すなわち、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔ）に対してプロセス３４００が実行された後、プロセス２４００はステップ２４０５へと進む。ステップ２４０５において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファ及びｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファの双方が空でない場合、プロセス２４００はステップ２４０７へと進む。ステップ２４０５の結果が偽の場合、プロセス２４００は直接ステップ２４０９へと進む。ステップ２４０９において、検査が実行され、現在の点に更にセグメントが存在するか否かが判定される。ステップ２４０７において、プロセッサ３０５により現在の点に対してエッジ作成プロセス３５００が実行され、プロセス２４００はステップ２４０９へと進む。ノンゼロワインディング規則に従って構成されたパスと同様に、プロセス３５００がステップ２４０７で実行される前に４つの境界線セグメント（すなわち、２つの左セグメント及び２つの右セグメント）がバッファリングされるのが好ましい。プロセス２４００は次のステップ２４０９へと続く。ステップ２４０９において、現在の点に更にセグメントが存在する場合、フローチャート２４００の処理はステップ２４０１へと戻る。セグメントが存在しない場合、フローチャート２４００の処理はステップ２４１１へと進む。ステップ２４１１において、検査が実行され、ｌｅｆｔ＿ｓｅｇｍｅｎｔ及びｒｉｇｈｔ＿ｓｅｇｍｅｎｔの双方が空でないか否かが判定される。ステップ２４１１の結果が真の場合、プロセスはステップ２４１３へと進む。ステップ２４１３においてｌｅｆｔ＿ｓｅｇｍｅｎｔ及びｒｉｇｈｔ＿ｓｅｇｍｅｎｔを伴って新規のエッジが作成される。ステップ２４１１の結果が偽の場合、フローチャート２４００のプロセスは終了し、フローチャート２３００のステップ２３１１へと進む。
【００９６】
プロセス２３００に戻ると、ステップ２３０４において、ステップ２３０３で選択された点からの第１のセグメントが現在のバンドラインにおいて終了するか、あるいは、前の点が現在の点で（すなわち、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔ）終了する水平セグメントを有する場合、現在の点（すなわち、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔ）は複合点として分類され、プロセス２３００はステップ２３０５へと進む。ステップ２３０５において、奇偶ワインディング塗りつぶし規則を用いて構成された入力パスに対する複合点プロセス２５００がステップ２３０３で選択された点上で実行される。奇偶ワインディング塗りつぶし規則を用いて構成された入力パスに対する複合点プロセス２５００については図２５のフローチャートを参照して以下の段落で説明する。プロセス２３００はステップ２３１１へと続く。ステップ２３１１において、メモリ３０６に格納されたアクティブセグメントテーブルに更に点が残っている場合、プロセスはステップ２３０３へと戻る。点が残っていない場合、プロセス２３００は終了し、プロセス６００のステップ６０９へと進む。
【００９７】
複合点プロセス２５００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。奇偶ワインディング塗りつぶし規則を用いて構成された入力パスに対する複合点プロセス２５００において、最初にプロセッサ３０５により現在の点の第１の終了セグメント（ｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔとラベル付けされる）及び最後の終了セグメント（ｌａｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔ）が識別される。水平セグメントが存在する場合、ｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファは直前の点から開始され、現在の点で終了する第１の水平セグメントを含むことになる。両端を含むｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔとｌａｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔとの間の各セグメントのエッジに新規の頂点が挿入され、閉じたエッジ（すなわち、現在の点で終了するエッジの左右のセグメントにより表される）が識別され、現在の点から閉じたエッジの各セグメントが除去される。プロセス２５００はステップ２５０１で開始される。ステップ２５０１において、検査が実行され、前の点がそこから開始される水平セグメントを有するか否かが判定される。ステップ２５０１の結果が真の場合、プロセスはステップ２５０２へと進む。ステップ２５０２において、ｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファは前の点から開始される第１の水平セグメントを含むように設定され、プロセス２５００はステップ２５０５へと進む。ステップ２５０１の結果が偽の場合、プロセス２５００はステップ２５０３へと進む。ステップ２５０３において、ｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファは現在の点の第１の終了セグメントを含むように設定される。プロセス２５００はステップ２５０５へと続く。ステップ２５０５において、ｌａｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファはステップ２３０３で選択された点の最後の終了セグメントを含むように設定される。次のステップ２５０７において、両端を含むｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファとｌａｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファとの間の全てのセグメントに対して、各セグメントが左としてマーク付けされるか、あるいは、右としてマーク付けされるかによって点(xcur,ybucket)により定義される頂点を有するノードが、第１のセグメントと最後のセグメントとの間の全てのセグメントに対するエッジの左ウィング又は右ウィングに挿入される。プロセス２５００はステップ２５０９へと続く。ステップ２５０９において、同じエッジに属する終了セグメントの各対がプロセッサ３０５により除去される。
【００９８】
プロセス２５００の次のステップ２５１１において、プロセッサ３０５により検査が実行され、ｌａｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔの後の現在の点において開始されるセグメントが存在するか否かが判定される。ステップ２５１１の結果が偽の場合、プロセス２５００は直接ステップ２５１３へと進む。ステップ２５１３において、現在の点から残り全ての終了セグメントが除去される。プロセス２５００は終了し、プロセス２３００のステップ２３１１へと進む。ステップ２５１１の結果が真の場合、プロセス２５００はステップ２５１５へと進む。ステップ２５１５において、現在のセグメントに対してセグメント結合／エッジ作成プロセスが実行され、フローチャート２５００のプロセスはステップ２５１３へと進む。プロセッサ３０５によりｌａｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔの後の現在の点から開始される任意のセグメントに対してセグメント結合／エッジ作成プロセス２６００が実行される。
【００９９】
図２６は、セグメント結合／エッジ作成プロセス２６００を示すフローチャートである。プロセス２６００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス２６００はステップ２６１５で開始される。ステップ２６１５において、プロセッサ３０５により現在の点（すなわち、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔ）で開始するセグメントが選択される。次のステップ２６０１において、プロセッサ３０５によりステップ２６１５で選択されるセグメントに対して開始境界線セグメント選択プロセス２７００が実行される。開始境界線セグメント選択プロセス２７００は、ｌａｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔの後の現在の点から開始されるあらゆるセグメントを処理し、これらのセグメントを左境界線セグメント又は右境界線セグメントに分類する。開始境界線セグメント選択プロセスについては図２７のフローチャート２７００を参照して以下の段落において更に詳細に説明する。プロセス２６００の次のステップ２６０３において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファ及びｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファの双方が空でない場合、プロセス２６００はステップ２６０７へと進む。ステップ２６０３の結果が偽の場合、プロセス２６００は直接ステップ２６０９へと進む。ステップ２６０９において、プロセッサ３０５により検査が実行され、現在の点に更にセグメントが存在するか否かが判定される。ステップ２６０７において、プロセッサ３０５により現在の点に対してエッジ作成プロセス３５００が実行され、プロセスはステップ２６０９へと進む。ノンゼロワインディング規則に従って構成された各パスと同様に、ステップ２６０７において、プロセス３６００が実行される前に４つの境界線セグメント（すなわち、２つの左セグメント及び２つの右セグメント）がメモリ３０６にバッファリングされるのが好ましい。プロセス２６００はステップ２６０９へと続く。ステップ２６０９において、現在の点に更にセグメントが存在する場合、プロセスはステップ２６０１へと戻る。セグメントが存在しない場合、プロセス２６００はステップ２６１１へと進む。ステップ２６１１において、現在の点に対してセグメント結合プロセス３３００が実行され、プロセス２２００と同様に、残り全てのセグメントはｆｉｒｓｔ＿ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔに結合される。次のステップ２６１３において、ｈ＿ｆｌａｇはＩＮＡＣＴＩＶＥに設定され、プロセス２６００は終了する。
【０１００】
図２７は、最後の終了セグメントの後の現在の点から開始されるあらゆるセグメントを処理し、これらのセグメントを左境界線セグメント又は右境界線セグメントに分類する開始境界線セグメント選択プロセス２７００を示すフローチャートである。プロセス２７００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス２７００はステップ２７０１で開始される。ステップ２７０１において、ステップ２２０１で選択される現在のセグメントが水平セグメントである場合、プロセスはステップ２７０２へと進む。ステップ２７０２において、水平フラグ（すなわち、ｈ＿ｆｌａｇ）がＩＮＡＣＴＩＶＥに設定されている場合、プロセスはステップ２７０３へと進む。ステップ２７０３において、ｈ＿ｆｌａｇはプロセッサ３０５によりｇ＿ｆｌａｇと等しくなるように設定される。ステップ２７０２において水平フラグがＡＣＴＩＶＥである場合、プロセスはステップ２７０５へと進む。ステップ２７０５において、ｈ＿ｆｌａｇがＲＩＧＨＴに設定されている場合、プロセス２７００はステップ２７０７へと進む。ステップ２７０７において、現在のセグメントは左セグメントとしてマーク付けされる。次のステップ２７０９において、ｈ＿ｆｌａｇはＲＩＧＨＴに設定される。また、ステップ２７０５において、ｈ＿ｆｌａｇがＲＩＧＨＴに設定されていない場合、プロセス２７００はステップ２７１１へと進む。ステップ２７１１において、選択されたセグメントは右セグメントとしてマーク付けされる。次のステップ２７１３において、ｈ＿ｆｌａｇはＲＩＧＨＴに設定される。
【０１０１】
ステップ２７１３の後、プロセス２７００はステップ２７１５へと進む。ステップ２７１５において、ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファが空の場合、プロセス２７００はステップ２７１７へと進む。ステップ２７１７において、ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファはプロセッサ３０５により現在のセグメント（すなわち、ステップ２２０１で選択されたセグメント）を含むように設定される。また、ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファが空でない場合、プロセス２７００はステップ２７１９へと進む。ステップ２７１９において、ｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファは選択されたセグメントを含むように設定される。次のステップ２７２１において、ｌａｓｔ＿ｓｅｇｍｅｎｔポインタはｎｅｘｔ＿ｒｉｇｈｔ＿ｓｅｇｍｅｎｔバッファを指し示すように設定される。ステップ２７２１の後、プロセス２７００は終了し、プロセス２６００のステップ２６０３へと進む。
【０１０２】
ステップ２７０１において、ステップ２６０１で選択された現在のセグメントが水平セグメントでない場合、プロセス２７００はステップ２７２３へと進む。ステップ２７２３において、グローバルフラグ（すなわち、ｇ＿ｆｌａｇ）がＲＩＧＨＴに設定される場合、プロセスはステップ２７２５へと進む。ステップ２７２５において、現在のセグメントはプロセッサ３０５により左セグメントとしてマーク付けされる。次のステップ２７２７において、ｇ＿ｃｏｕｎｔｅｒはＬＥＦＴに設定される。ステップ２７２３において、グローバルフラグがＲＩＧＨＴに設定されていない場合、プロセス２７００はステップ２７２９へと進む。ステップ２７２９において、現在のセグメントは右セグメントとしてマーク付けされる。次のステップ２７３１において、ｇ＿ｃｏｕｎｔｅｒはＲＩＧＨＴに設定され、プロセス２７００はステップ２７１５へと進む。
【０１０３】
ステップ２７２７の後、プロセス２７００はステップ２７３３へと進む。ステップ２７３３において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファが空の場合、次のステップ２７３５において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファは現在のセグメントを含むように設定される。ステップ２７３５の後、プロセス２７００は終了し、フローチャート２６００のステップ２６０３へと進む。ステップ２７３３において、ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファが空でない場合、次のステップ２７３７において、ｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファは現在のセグメントを含むように設定される。次のステップ２７３９において、ｌａｓｔ＿ｓｅｇｍｅｎｔポインタはｎｅｘｔ＿ｌｅｆｔ＿ｓｅｇｍｅｎｔバッファを指し示すように設定される。ステップ２７３９の後、プロセス２７００は終了し、プロセス２６００のステップ２６０３へと進む。
【０１０４】
図６Ａのプロセス６００に戻ると、ステップ６０７において、現在のバケットに対してセグメント割当て／エッジ作成プロセス２３００が実行された後、プロセス６００はステップ６０９へと進む。ステップ６０９において、現在のバケットに対して交差検出プロセスが実行される。この点に関して、２つ以上のセグメントの交差は、現在のバケットの上方のバンドラインと下方のバンドラインとの間の領域でのみ起こり得る。全ての交点は、相互に交差する２つのセグメントの結果である。３つ以上のセグメントが相互に交差する交点は、複数の交点が相互に重なり合ったもの（すなわち、同時交点）と見なされる。
【０１０５】
交点は発生時間順に処理される。交差は以下の場合に別の交差に先立って発生する：
（i）先の交点のｙ位置の方が小さい（すなわち、パスが定義される空間の第１のバンドラインに近い）及び／又は
（ii）交点が最初に検出される（すなわち、交点が全く同じ場合）。
【０１０６】
図２８は交差セグメントを検出する交差検出プロセス２８００を示すフローチャートである。プロセス２８００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス２８００はステップ２８０１で開始される。ステップ２８０１において、アクティブセグメントテーブルからの第１のセグメントと共に、アクティブセグメントテーブルと同様に構成されたバッファが初期化される。プロセス２８００の続くステップ２８０３から２８２５において、アクティブセグメントテーブルから一度に１つずつ残ったセグメントが除去され、上方のバンドラインにおけるｘ座標とバッファ中の各セグメントのｘ座標との比較が行なわれる。比較はバッファの最右端（すなわち、最後）のセグメントから開始される。上方のバンドラインにおける除去されたセグメントのｘ座標がバッファ中のセグメントのｘ座標よりも小さい場合、アクティブセグメントテーブルから除去されたセグメントは、バッファ中のセグメントと交差する。アクティブセグメントテーブルから除去されたセグメントが、バッファ中のセグメントと交差することがなくなり、除去されたセグメントが交差しなかったバッファ中のセグメントの右側（すなわち、後）に挿入されると、比較は終了する。
【０１０７】
ステップ２８０３において、プロセッサ３０５によりアクティブセグメントテーブルからセグメントが除去され、バッファに挿入される。プロセスは次のステップ２８０５へと進む。ステップ２８０５において、アクティブセグメントテーブルからレフトネスの降順に次のセグメントが除去される。このセグメントは、ラベルＡＳＴ＿ｓｅｇｍｅｎｔを割り当てられるのが好ましい。次のステップ２８０７において、プロセッサ３０５によりバッファの最右端（すなわち、最後）のエントリセグメントが選択される。このエントリセグメントは、ラベルｂｕｆｆｅｒ＿ｓｅｇｍｅｎｔを割り当てられるのが好ましい。プロセス２８００はステップ２８０９へと続く。ステップ２８０９において、上方のバンドラインにおけるＡＳＴ＿ｓｅｇｍｅｎｔのｘ座標が上方のバンドラインにおけるｂｕｆｆｅｒ＿ｓｅｇｍｅｎｔのｘ座標よりも小さい場合、プロセス２８００はステップ２８１５へと進む。ｂｕｆｆｅｒ＿ｓｅｇｍｅｎｔのｘ座標と等しいか、あるいは、それよりも大きい場合、プロセス２８００はステップ２８１１へと進む。ステップ２８１１において、プロセッサ３０５によりＡＳＴ＿ｓｅｇｍｅｎｔｂｕｆｆｅｒ＿ｓｅｇｍｅｎｔの右側（すなわち、後）にＡＳＴ＿ｓｅｇｍｅｎｔが挿入される。次のステップ２８１３において、アクティブセグメントテーブルに更にセグメントが存在する場合、プロセス２８００はステップ２８０５へと戻る。セグメントが存在しない場合、プロセス２８００はステップ２８２５へと進む。
【０１０８】
ステップ２８１５において、任意の既知の計算方法を使用して、ＡＳＴ＿ｓｅｇｍｅｎｔバッファ及びｂｕｆｆｅｒ＿ｓｅｇｍｅｎｔバッファに含まれるセグメントの交点が計算される。プロセス２８００は次のステップ２８１７へと続く。ステップ２８１７において、交点とＡＳＴ＿ｓｅｇｍｅｎｔバッファ及びｂｕｆｆｅｒ＿ｓｅｇｍｅｎｔバッファの双方への参照とが交差テーブル（ＩＴ）へと挿入される。交差テーブル中の交点及び参照は、上述の方法で交点を処理する必要があるためにソートされる必要がある。ＡＳＴ＿ｓｅｇｍｅｎｔ及びｂｕｆｆｅｒ＿ｓｅｇｍｅｎｔはアクティブセグメントテーブルから除去されたセグメントが最初になる（すなわち、交点の後の最左端のセグメントが最初になる）ように交差テーブルにおいて順序付けられなければならない。次のステップ２８１９において、バッファに更にセグメントが存在する場合、プロセス２８００はステップ２８２１へと進む。ステップ２８２１において、プロセッサ３０５によりバッファ中の次の左エントリセグメントが選択され、ｂｕｆｆｅｒ＿ｓｅｇｍｅｎｔとして割り当てられる。セグメントが存在しない場合、プロセス２８００はステップ２８２３へと進む。ステップ２８２３において、プロセッサ３０５によりバッファの最左端のエントリとしてＡＳＴ＿ｓｅｇｍｅｎｔが挿入される。プロセス２８００はステップ２８１３へと戻る。ステップ２８２５において、バッファはアクティブセグメントテーブルとして割り当てられる（すなわち、バッファがアクティブセグメントテーブルに置き換わる）。
【０１０９】
図６Ａのプロセス６００へと戻ると、ステップ６０９において、現在のバケットに対して交差検出プロセス２８００が実行された後、プロセス６００はステップ６１１へと進む。ステップ６１１において、プロセッサ３０５により現在のバケットのセグメントに対して交差処理プロセス２９００が実行される。これにより、エッジに属するセグメントが交換されるか、あるいは、新規のエッジが作成される。交差処理プロセス２９００において、奇偶ワインディング塗りつぶし規則を用いて構成された各パスに対する交差とノンゼロワインディング塗りつぶし規則を用いて構成された各パスに対する交差とは異なる方法で処理される。
【０１１０】
図２９は、ノンゼロワインディング塗りつぶし規則を用いて構成された入力パスに対する交差処理プロセス２９００を示すフローチャート２９００である。プロセス２９００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。交差は一度に１つずつ処理される。プロセス２９００はステップ２９０１で開始される。ステップ２９０１において、メモリ３０６に格納された交差テーブルから交差テーブル中で交差詳細がソートされている順に現在のバンドラインに対する交差詳細が除去される。上述のように、交差詳細は交点及びその交点において交差するセグメントへの参照を含む。次のステップ２９０３において、交差セグメントと関連付けられたカウンタ値が更新される。これにより、第１の交差セグメント（すなわち、交点の後の最左端のセグメント）は、第２の交差セグメントと関連付けられたカウンタのカウンタ値を引き継ぐ。このため、第２の交差セグメントと関連付けられたカウンタの値が第１の交差セグメントに割り当てられる。更に、第１のセグメントの方向に従って、第２の交差セグメントと関連付けられたカウンタが更新される。
【０１１１】
プロセス２９００のステップ２９１３から２９２５において、双方の交差セグメントが複数のエッジに属する場合、プロセッサ３０５により双方のエッジの各々に対して新規の頂点が作成される。更に、双方の交差セグメントが同じエッジに属する場合、エッジへの各セグメントの割当てが除去され、各交差セグメントから新規のエッジが作成される。複数のエッジに属さない場合、第１の交差セグメントが境界線セグメントであるときには、交差セグメントの対応するエッジ及びその左／右割当てが交換され、第１の交差セグメントが非境界線セグメントであるときには、各エッジから双方の交差セグメントの割当てが解除される。
【０１１２】
プロセス２９００はステップ２９０５へと続く。ステップ２９０５において、第１のセグメント及び第２のセグメントの双方がエッジに属する場合、プロセスはステップ２９１３へと進む。ステップ２９１３において、セグメントが左としてマーク付けされるか、あるいは、右としてマーク付けされるかによって、交点を有するノードが交差セグメントと関連付けられた双方のエッジの左ウィング又は右ウィングにプロセッサ３０５により挿入される。次のステップ２９１５において、第１及び第２の交差セグメントが同じエッジに属する場合、プロセスはステップ２９１７へと進む。ステップ２９１７において、各エッジから第１の交差セグメント及び第２の交差セグメントの双方の割当てが解除される。プロセス２９００はステップ２９１９へと続く。ステップ２９１９において、左右の境界線セグメントが存在する場合、プロセッサ３０５により交点から開始される新規のエッジが作成される。更に、その左右のセグメントは新規に作成されたエッジに割り当てられ、プロセス２９００はステップ２９２７へと進む。
【０１１３】
ステップ２９１５において、第１の交差セグメント及び第２の交差セグメントが同じエッジに属さない場合、プロセス２９００はステップ２９２１へと進む。ステップ２９２１において、プロセッサ３０５により検査が実行され、第１のセグメントが境界線セグメントであるか否かが判定される。図１７を参照して先に述べたように、第１のセグメントが境界線セグメントであるか否かはセグメントの方向及びそのセグメントと関連付けられたカウンタの値によって決まる。ステップ２９２１において、第１のセグメントが境界線セグメントである場合、プロセス２９００はステップ２９２３へと進む。ステップ２９２３において、第１のセグメント及び第２のセグメントの各々と関連付けられたエッジはセグメントの左／右割当てを伴って交換される。第１のセグメントが境界線セグメントでない場合、プロセス２９００はステップ２９２５へと進む。ステップ２９２５において、各エッジから第１のセグメント及び第２のセグメントは割当てを解除される。プロセス２９００はステップ２９２７へと進む。ステップ２９２７において、交差テーブルに更に交差詳細が存在する場合、プロセス２９００はステップ２９０１へと戻る。
【０１１４】
ステップ２９０５において、第１の交差セグメント及び第２の交差セグメントが複数のエッジに属さない場合、プロセス２９００はステップ２９０７へと進む。ステップ２９０７において、交差セグメントのいずれもエッジに属さない場合、プロセス２９００は直接ステップ２９１９へと進む。ステップ２９１９において、交差セグメントが境界線セグメントであるか否かによって交差セグメントから新規のエッジが作成される。ステップ２９０７において、セグメントのうちの少なくとも１つがエッジに属する場合、プロセス２９００は図２９に示すようにステップ２９０９及び２９１１へと進む。ステップ２９０９及び２９１１において、エッジに属する特定の交差セグメントのエッジ割当て及び左／右割当てが、エッジに属さない交差セグメントに割り当てられる。また、ステップ２９０９において、プロセッサ３０５によりエッジに新規の頂点が挿入される。新規の頂点は交点の値をとる。プロセス２９００はステップ２９２７で終了する。ステップ２９２７において、交差テーブルに交差詳細は存在しないときにはプロセス２９００はプロセス６００のステップ６１３へと進む。
【０１１５】
図４６Ａ、図４６Ｂ、及び図４６Ｃは、ノンゼロワインディング塗りつぶし規則を用いて構成された入力パスに対する更なる交差処理プロセス４６００を示すフローチャートである。プロセス４６００と上述のプロセス２９００との主な相違点は、３つ以上のセグメントを伴う交点の処理方法にある。プロセス４６００において、３つ以上のセグメントが交差する交点と交差する全てのセグメントが最初に分割される。続いて、全ての開始境界線セグメントが可能な限り終了境界線セグメントに結合される。残されたセグメント（すなわち、終了境界線セグメントに結合されていない開始境界線セグメント）に対して、新規のエッジが作成される。分割の前は、全てのセグメントが既存の順番で適切なバッファに保持されているものと想定される。
【０１１６】
プロセス４６００は３つ以上のセグメントを伴う交点を複合点として扱う。しかし、開始境界線セグメントから新規のエッジを作成するべく試みることよりも、残された境界線セグメントを第１の終了境界線セグメントに結合することの方に優先度が与えられる。プロセス４６００の各ステップは、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるソフトウェアとして実現されるのが好ましい。
【０１１７】
プロセス４６００はステップ４６０１で開始される。ステップ４６０１において、交差テーブルにおいて交差詳細がソートされた順に交差テーブルから現在のバンドに対する交差詳細が除去される。交差詳細はラベルｃｕｒｒｅｎｔ＿ｉｎｔｅｒｓｅｃｔｉｏｎ＿ｄｅｔａｉｌｓを割り当てられるのが好ましい。上述のように、交差詳細は交点及びその交点で交差するセグメントへの参照を含む。次のステップ４６０３において、交差詳細が同じ交点を有する場合、プロセス４６００はステップ４６２５へと進む。ステップ４６２５において、現在の交点に対して図４７に示すようなセグメント分割割当てプロセス４７００が実行される。セグメント分割割当てプロセス４７００については図４７のフローチャートを参照して詳細に後述する。ステップ４６２３において、ＩＴ（すなわち、交差テーブル）に更に交差詳細が存在する場合、プロセス４６００はステップ４６０１へと戻る。交差詳細が存在しない場合、交差テーブルには交差詳細は存在しないので、プロセス４６００は方法６００のステップ６１３へと進む。次のステップ４６０５において、交差セグメントと関連付けられたカウンタ値が更新され、それにより、第１の交差セグメント（すなわち、交点の後の最左端のセグメント）は第２の交差セグメントと関連付けられたカウンタのカウンタ値を引き継ぐ。このため、第２の交差セグメントと関連付けられたカウンタの値は第１の交差セグメントに割り当てられる。更に、第２の交差セグメントと関連付けられたカウンタは、第１のセグメントの方向に従って更新される。プロセス４６００はステップ４６０７へと続く。ステップ４６０７において、第１の交差セグメント及び第２の交差セグメントの双方が複数のエッジに属する場合、プロセス４６００はステップ４６２７へと進む。複数のエッジに属さない場合、プロセス４６００はステップ４６１１へと進む。ステップ４６２７において、セグメントが左としてマーク付けされるか、あるいは、右としてマーク付けされるかによって、交点を有するノードが交差セグメントと関連付けられた双方のエッジの左ウィング又は右ウィングに挿入される。次のステップ４６０９において、第１の交差セグメント及び第２の交差セグメントが同じエッジに属する場合、プロセス４６００はステップ４６１３へと続く。ステップ４６１３において、各エッジから第１の交差セグメント及び第２の交差セグメントの双方が割当てを解除される。プロセスはステップ４６１７へと続く。ステップ４６１７において、左右の境界線セグメントが存在する場合、交点から開始される新規のエッジが作成される。更に、その左右のセグメントは新規に作成されたエッジに割り当てられ、プロセス４６００はステップ４６２１へと進む。
【０１１８】
ステップ４６０９において、第１の交差セグメント及び第２の交差セグメントが同じエッジに属さない場合、プロセス４６００はステップ４６２９へと進む。ステップ４６２９において、検査が実行され、第１のセグメントが境界線セグメントであるか否かが判定される。図２０を参照して先に述べたように、第１のセグメントが境界線セグメントであるか否かは、セグメントの方向及びそのセグメントと関連付けられたカウンタの値によって決まる。ステップ４６２９において、第１のセグメントが境界線セグメントである場合、プロセス４６００はステップ４６３１へと進む。ステップ４６３１において、第１のセグメント及び第２のセグメントの各々と関連付けられたエッジは各セグメントの左／右割当てと共に交換される。第１のセグメントが境界線セグメントでない場合、プロセス４６００はステップ４６３３へと進む。ステップ４６３３において、各エッジから第１のセグメント及び第２のセグメントの割当てが解除される。その後、プロセス４６００はステップ４６２１へと進む。ステップ４６２１において、交差テーブルに交差詳細が存在する場合、プロセス４６００はステップ４６０１へと戻る。
【０１１９】
ステップ４６０７において、第１の交差セグメント及び第２の交差セグメントの双方が複数のエッジに属さない場合、プロセス４６００はステップ４６１１へと進む。ステップ４６１１において、交差セグメントがエッジに属さない場合、プロセス４６００は直接ステップ４６１７へと進む。ステップ４６１７において、交差セグメントが境界線セグメントであるか否かによって交差セグメントから新規のエッジが作成される。ステップ４６１１において、セグメントのうちの少なくとも１つがエッジに属する場合、プロセス４６００は図４６に示すようにステップ４６１５及び４６１９へと進む。ステップ４６１５及び４６１９において、エッジに属する特定の交差セグメントのエッジ割当て及び左／右割当てが、エッジに属さない交差セグメントに割り当てられる。また、ステップ４６１５において、エッジに新規の頂点が挿入される。新規の頂点は交点の値をとる。ＩＴ（すなわち、交差テーブル）に交差詳細が存在しない場合、プロセス４６００はステップ４６２１で終了し、方法６００のステップ６１３へと進む。
【０１２０】
プロセス４７００の各ステップは、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるソフトウェアとして実現されるのが好ましい。プロセス４７００はステップ４７０１で開始される。ステップ４７０１において、ラベルｃｕｒｒｅｎｔ＿ｉｎｔｅｒｓｅｃｔｉｏｎ＿ｄｅｔａｉｌｓにより表される交点に類似する交点を有する交差セグメントに対する交差詳細が交差テーブルから除去される。次のステップ４７０３において、セグメントが左としてマーク付けされるか、あるいは、右としてマーク付けされるかによって、交点を有するノードが第１の交差セグメント及び第２の交差セグメントと関連付けられた双方のエッジの左ウィング又は右ウィングに挿入される。次のステップ４７０５において、現在の点に対して図４８に示すようなセグメント分割プロセス４８００が実行され、交点上の終了セグメント及び開始セグメントが分離される。セグメント分割プロセス４８００については図４８のフローチャートを参照して後述する。上述の各プロセスと同様に、プロセス４８００の各ステップはハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるソフトウェアとして実現されるのが好ましい。
【０１２１】
プロセス４７００の次のステップ４７０７において、バッファｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔが交差詳細により表される第１の終了セグメントへと初期化される。プロセス４７００は次のステップ４７０９へと続く。ステップ４７０９において、バッファｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔが交差詳細により表された第１の開始セグメントへと初期化される。次のステップ４７１１において、ｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔと関連付けられたカウンタがｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔと関連付けられたカウンタの値に設定される。プロセス４７００は次のステップ４７１３へと続く。ステップ４７１３において、同じエッジに属する全ての境界線セグメント及び全ての非境界線セグメントが削除される。次のステップ４７１５において、現在の交点に未処理の終了セグメントが存在する場合、プロセス４７００はステップ４７１７へと進む。ステップ４７１７において、現在の点に対してセグメント結合プロセス４９００が実行される。それにより、現在の点から開始される各境界線セグメントに対して、新規のエッジが作成される。セグメント結合プロセス４９００については図４９のフローチャートを参照して後述する。プロセス４９００の各ステップは、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるソフトウェアとして実現されるのが好ましい。
【０１２２】
ステップ４７１５において、現在の点に未処理の終了セグメントが存在しない場合、プロセス４７００はステップ４７１９へと進む。ステップ４７１９において、現在の交点に対してエッジ作成プロセス５０００が実行され、それにより、現在の交点から開始される各境界線セグメントに対して、新規のエッジが作成される。エッジ作成プロセス５０００については図５０を参照して詳細に後述する。プロセス５０００の各ステップは、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるソフトウェアとして実現されるのが好ましい。
【０１２３】
プロセス４８００はステップ４８０１で開始される。ステップ４８０１において、ｃｕｒｒｅｎｔ＿ｓｅｇｍｅｎｔとして第１の境界線セグメントが選択される。次のステップ４８０３において、ｃｕｒｒｅｎｔ＿ｓｅｇｍｅｎｔバッファ中のセグメントを複製するが、現在の交点で終了する新規のセグメントが作成される。プロセス４８００は次のステップ４８０５へと続く。ステップ４８０５において、ｃｕｒｒｅｎｔ＿ｓｅｇｍｅｎｔバッファが更新され、現在の交点で開始される。次のステップ４８０７において、ｃｕｒｒｅｎｔ＿ｓｅｇｍｅｎｔバッファにより示されるセグメントは、新規に作成されたセグメントと交換され、ｃｕｒｒｅｎｔ＿ｓｅｇｍｅｎｔは全ての終了セグメントの後に順番に再挿入される。次のステップ４８０９において、交差詳細により表される境界線セグメントが存在する場合、プロセス４８００はステップ４８０１へと戻る。境界線セグメントが存在しない場合、プロセス４８００は終了し、プロセス４７００のステップ４７０７へと進む。
【０１２４】
プロセス４９００はステップ４９０１で開始される。ステップ４９０１において、バッファｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔにより示されるセグメントが境界線セグメントである場合、プロセス４９００はステップ４９０３へと進む。境界線セグメントでない場合、プロセス４９００はステップ４９１１へと進む。ステップ４９０３において、バッファｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔにより示されるセグメントのエッジは、バッファｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔにより表される開始セグメントに割り当てられる。また、ステップ４９０３において、開始セグメントは終了セグメントによって左又は右としてマーク付けされる。次のステップ４９０５において、現在の交点に更にセグメントが存在する場合、プロセス４９００はステップ４９１５へと進む。セグメントが存在しない場合、プロセス４９００は直接プロセス４６００のステップ４６２３へと進む。
【０１２５】
プロセス４９００のステップ４９１５において、バッファｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔは、現在の交点における次の開始セグメントと等しくなるように設定され、次の開始セグメントと関連付けられたカウンタは、上述のように、現在の開始セグメントのカウンタ及び方向に基づいて更新される。次のステップ４９１３において、現在の交点に更に終了セグメントが存在する場合、プロセス４９００はステップ４９０１へと戻る。終了セグメントが存在しない場合、プロセス４９００はステップ４９０７へと進む。ステップ４９０７において、現在の点に対して図５０のエッジ作成プロセス５０００が実行される。
【０１２６】
ステップ４９１１において、現在の交点に更に開始セグメントが存在する場合、プロセス４９００はステップ４９０９へと進む。開始セグメントが存在しない場合、プロセス４９００は直接プロセス４６００のステップ４６２３へと進む。ステップ４９０９において、プロセス４９００はステップ４９０９へと進む。ステップ４９０９において、ｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔバッファは現在の交点において次の開始セグメントと等しくなるように設定され、次の開始セグメントと関連付けられたカウンタは現在の開始セグメントのカウンタ及び方向に基づいて更新される。プロセス４９００はステップ４９０９の終了後にステップ４９０１へと戻る。
【０１２７】
プロセス５０００はステップ５００１で開始される。ステップ５００１において、バッファｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔにより示されるセグメントが境界線セグメントである場合、プロセス５０００はステップ５００３へと進む。境界線セグメントでない場合、プロセス５０００は直接ステップ５００９へと進む。ステップ５００３において、現在の交点における次の開始セグメントが選択され、現在の開始セグメントのカウンタ及び方向に基づいて次の開始セグメントと関連付けられたカウンタが更新される。プロセス５０００は次のステップ５００５へと進む。ステップ５００５において、選択されたセグメントが境界線セグメントである場合、プロセス５０００はステップ５００７へと進む。境界線セグメントでない場合、プロセス５０００はステップ５００５に戻る前にステップ５０１１へと進む。
【０１２８】
プロセス５０００のステップ５０１１において、現在の点における次の開始セグメントが選択され、現在の開始セグメントのカウンタ及び方向に基づいて次の開始セグメントと関連付けられたカウンタが更新される。プロセス５０００は次のステップ５００７へと続く。ステップ５００７において、ｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔ及びステップ５００３で選択されたセグメントから、現在の交点から開始される新規のエッジが作成される。更に、新規に作成されたエッジのセグメントは、図２０で与えられた基準に基づいて左セグメント及び右セグメントとして割り当てられ、プロセス５０００はステップ５００９へと進む。ステップ５００９において、現在の交点に更に開始セグメントが存在する場合、プロセス５０００はステップ５０１３へと進む。開始セグメントが存在しない場合、プロセス５０００はプロセス４６００のステップ４６２３へと進む。
【０１２９】
プロセス５０００の次のステップ５０１３において、ｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔバッファは現在の交点における次の開始セグメントと等しくなるように設定され、次の開始セグメントと関連付けられたカウンタは、現在の開始セグメントのカウンタ及び方向に基づいて更新される。
【０１３０】
図３０は、奇偶ワインディング塗りつぶし規則を用いて構成された入力パスに対する交差処理プロセス３０００を示すフローチャートである。プロセス３０００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス２９００と同様に、交点は一度に１つずつ処理される。プロセス３０００のステップ３００１から３０１１において、交点における交差セグメントに対して双方のエッジに新規の頂点が挿入される。交差セグメントが同じエッジに属する場合、交差セグメントから新規のエッジが作成される。同じエッジに属さない場合、交差セグメントの対応するエッジ及び対応する左／右割当てが交換される。プロセス３０００はステップ３００１で開始される。ステップ３００１において、交差テーブルから交差セグメントに対する交差詳細が除去される。次のステップ３００３において、セグメントが左としてマーク付けされるか、あるいは、右としてマーク付けされるかによって、交点を有するノードが交差セグメントと関連付けられた双方のエッジの左ウィング又は右ウィングにプロセッサ３０５により挿入される。プロセス３０００はステップ３００５へと続く。ステップ３００５において、双方の交差セグメントが同じエッジに属する場合、交点において交差セグメントを伴って新規のエッジが作成される。更に、前は左だったセグメントが右になり、前は右だったセグメントが左セグメントになるように、左右の交差セグメントが新規に作成されたエッジに割り当てられる。次のステップ３０１１において、交差テーブルに更に交差詳細が存在する場合、プロセス３０００はステップ３００１へと戻る。
【０１３１】
ステップ３００５において、双方の交差セグメントが同じエッジに属さない場合、第１の交差セグメント及び第２の交差セグメントの各々と関連付けられたエッジが、セグメントの左／右割当てと共に交換される。プロセス３０００はステップ３０１１で終了する。ステップ３０１１において、交差テーブルに交差詳細が存在しない場合、プロセス３０００はプロセス６００のステップ６１３へと進む。
【０１３２】
図６Ａのプロセス６００に戻ると、ステップ６１１において現在のバケットに対する交差セグメントに対して交差処理プロセスが実行された後、プロセス６００はステップ６１３へと進む。ステップ６１３において、セグメントテーブルにバケットが残っている場合、プロセス６００はステップ６０３へと戻る。バケットが残っていない場合、プロセスはステップ６１５へと進む。ステップ６１５において、ステップ６０１から６１３のプロセスにより生じる開いたエッジが、図３２において示すようなエッジ併合プロセス３２００により結合され、ステップ６１５において、閉じたエッジを形成して単純輪郭パスを構成することになる。最後の左頂点が最後の右頂点と等しくない場合には、エッジは開いていると考えられる。エッジは異なる頂点の組を結合することにより併合される。左の割当てられたエッジの頂点は、右の割り当てられたエッジの頂点と結合される。ここに記載する方法によると、左頂点のみが右頂点と結合可能であると共に、右頂点のみが左頂点と結合可能である。
【０１３３】
図５１は、奇偶ワインディング塗りつぶし規則を用いて構成された入力パスに対する更なる交差処理プロセス５１００を示すフローチャートである。プロセス５１００と上述のプロセス３０００の相違点は、３つ以上のセグメントを伴う交点の処理方法にある。既に説明したプロセス３０００と同様に、プロセス５１００の各ステップは、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるソフトウェアとして実現されるのが好ましい。プロセス５１００において、３つ以上のセグメントが交差する交点と交差する全てのセグメントが最初に分割される。その後、全ての開始境界線セグメントが可能な限り終了境界線セグメントに結合される。残されたセグメントに対して、すなわち、終了境界線セグメントに結合されていない開始境界線セグメントに対して、新規のエッジが作成される。分割の前は、全てのセグメントが既存の順番で適切なバッファに保持されているものと想定される。
【０１３４】
プロセス５１００はステップ５１０１で開始される。ステップ５１０１において、交差テーブルから順番に交差セグメントに対する交差詳細が除去される。交差詳細は、ラベルｃｕｒｒｅｎｔ＿ｉｎｔｅｒｓｅｃｔｉｏｎ＿ｄｅｔａｉｌｓを割り当てられるのが好ましい。次のステップ５１０３において、交差詳細が同じ交点を有する場合、プロセス５１００はステップ５１１５へと進む。交差詳細が同じ交点を有しない場合、プロセスはステップ５１０５へと進む。ステップ５１１５において、現在の交点に対して図５２Ａ及び図５２Ｂで示されるようなセグメント分割割当てプロセス５２００が実行され、プロセス５１００はステップ５１１３へと進む。セグメント分割割当てプロセス５２００については図５２Ａ及び図５２Ｂを参照して後述する。ステップ５１０５において、セグメントが左としてマーク付けされるか、あるいは、右としてマーク付けされるかによって、交点を有するノードが交差セグメントと関連付けられた双方のエッジの左ウィング又は右ウィングに挿入される。次のステップ５１０７において、２つの交差セグメントが同じエッジに属する場合、プロセス５１００はステップ５１０９へと進む。同じエッジに属さない場合、プロセス５１００はステップ５１１１へと進む。ステップ５１１１において、エッジ及びセグメントと関連付けられた左／右割当てが交換される。ステップ５１０９において、交差セグメントから現在の交点から開始される新規のエッジが作成される。更に、左右の交差セグメントが新規に作成されたエッジに割り当てられ、プロセス５１００はステップ５１１３へと進む。前の左セグメントが右セグメントになり、前の右セグメントが左セグメントになる。ステップ５１１３において、交差テーブルに更にセグメントが存在する場合、プロセス５１００はステップ５１０１へと戻る。セグメントが存在しない場合、プロセスは方法６００のステップ６１３へと進む。
【０１３５】
プロセス５２００の各ステップは、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるソフトウェアとして実現されるのが好ましい。プロセス５２００はステップ５２０１で開始される。ステップ５２０１において、ラベルｃｕｒｒｅｎｔ＿ｉｎｔｅｒｓｅｃｔｉｏｎ＿ｄｅｔａｉｌｓにより表される交点に類似する交点を有する交差セグメントに対する交差詳細が交差テーブルから除去される。次のステップ５２０３において、セグメントが左としてマーク付けされるか、あるいは、右としてマーク付けされるかによって、現在の交点の座標である頂点を有するノードが交差セグメントと関連付けられた双方のエッジの左ウィング又は右ウィングに挿入される。次のステップ５２０５において、現在の点に対してセグメント分割プロセス４８００が実行され、点上の終了セグメント及び開始セグメントが分離される。次のステップ５２０７において、ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファが交差詳細により表される第１の終了セグメントへと初期化される。プロセス５２００は次のステップ５２０９へと続く。ステップ５２０９において、ｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔバッファが交差詳細により表された第１の開始セグメントへと初期化される。次のステップ５２１１において、第１の開始セグメントの左右のセグメントが終了セグメントとしてマーク付けされ、同じエッジに属する終了セグメントの全ての対が交差テーブルから削除される。
【０１３６】
次のステップ５２１３において、更に終了セグメントが存在する場合、プロセス５２００はステップ５２１５へと進む。終了セグメントが存在しない場合、プロセス５２００はステップ５２２９へと進む。ステップ５２１５において、バッファｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔにより表される開始セグメントにバッファｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔにより示されるセグメントのエッジが割り当てられる。また、ステップ５２１５において、終了セグメントと関連付けられたカウンタによって開始セグメントは左又は右としてマーク付けされる。次のステップ５２２１において、更に終了セグメントが存在する場合、プロセスはステップ５２１９へと進む。終了セグメントが存在しない場合、プロセス５２００はステップ５２２３へと進む。ステップ５２１９において、ｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔバッファは現在の点における次の開始セグメントに設定される。ステップ５２１７において、ｅｎｄｉｎｇ＿ｓｅｇｍｅｎｔバッファは現在の点における次の開始セグメントに設定され、プロセス５２００はステップ５２１５へと戻る。
【０１３７】
プロセス５２００の次のステップ５２２３において、バッファｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔにより表されるセグメントが左セグメントである場合、プロセス５２００はステップ５２２５へと進む。ステップ５２２５において、次の開始セグメントが右セグメントとしてマーク付けされる。セグメントが右セグメントである場合、プロセス５２００はステップ５２３３へと進む。ステップ５２３３において、次の開始セグメントが左セグメントとしてマーク付けされる。プロセス５２００は次のセグメント５２２７へと続く。ステップ５２２７において、ｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔバッファは現在の交点における次の開始セグメントに設定される。
【０１３８】
ステップ５２２９において、現在の点に対して図５３に示すようなエッジ作成プロセス５３００が実行される。それにより、現在の点から開始される各境界線セグメントに対して、新規のエッジが作成される。エッジ作成プロセス５３００については図５３を参照して詳細に後述する。プロセス５３００の各ステップは、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるソフトウェアとして実現されるのが好ましい。プロセス５２００は次のステップ５２３１で終了する。ステップ５２３１において、交差テーブルから全ての終了セグメントが除去され、プロセス５２００はステップ５１１３へと進む。
【０１３９】
プロセス５３００はステップ５３０１で開始される。ステップ５３０１において、ｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔバッファにより表されるセグメントが左セグメントである場合、プロセス５３００はステップ５３０３へと進む。右セグメントである場合、プロセス５３００はステップ５３０５へと進む。ステップ５３０５においては、次の開始セグメントは左セグメントとしてマーク付けされる。ステップ５３０３においては、次の開始セグメントは右セグメントとしてマーク付けされる。ステップ５３０７において、開始セグメント及び次の開始セグメントから現在の交点から開始される新規のエッジが作成され、プロセス５３００はステップ５３０９へと進む。ステップ５３０９において、ｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔバッファは次の開始セグメントに設定される。
【０１４０】
次のステップ５３１１において、現在の点に更に開始セグメントが存在する場合、プロセス５３００はステップ５３１３へと進む。開始セグメントが存在しない場合、プロセス５３００はプロセス５２００のステップ５２３１へと進む。ステップ５３１３において、バッファ中のセグメント、すなわち、ｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔが左セグメントである場合、プロセス５３００はステップ５３１９へと進む。右セグメントである場合、プロセス５３００はステップ５３１７へと進む。ステップ５３１７において、現在の交点における次の開始セグメントが左セグメントとしてマーク付けされる。ステップ５３１９において、次の開始セグメントが右セグメントとしてマーク付けされる。次のステップ５３１５において、ｓｔａｒｔｉｎｇ＿ｓｅｇｍｅｎｔバッファは次の開始セグメントと等しくなるように設定され、プロセス５３００はステップ５３０１へと戻る。
【０１４１】
図３２は、全ての開いたエッジを併合して単純輪郭パスを形成するエッジ併合プロセス３２００を示すフローチャートである。プロセス３２００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス３２００はステップ３２０１で開始される。ステップ３２０１において、プロセッサ３０５により第１の開いたエッジが選択される。開いたエッジはラベルｏ＿ｅｄｇｅを割り当てられるのが好ましい。プロセス３２００はステップ３２０３から３２０７へと続く。ステップ３２０３から３２０７において、ステップ６０１から６１３により生じる各エッジに対する頂点の座標を比較することによって、エッジ（すなわち、ｏ＿ｅｄｇｅ）と併合するのに適切なエッジがプロセッサ３０５により選択される。上述のように、左エッジの頂点のみが右エッジの頂点と結合可能であると共に、右エッジの頂点のみが左エッジの頂点と結合可能である。このため、プロセス３２００はステップ３２０３へと続く。ステップ３２０３において、プロセッサ３０５により検査が実行され、各エッジに対する頂点の座標を比較することによって、エッジｏ＿ｅｄｇｅの最後の右頂点と等しい最後の左頂点を有する開いたエッジが存在するか否かが判定される。ステップ３２０３の結果が偽の場合、プロセス３２００はステップ３２１１へと進む。ステップ３２１１において、プロセッサ３０５により検索が実行され、エッジｏ＿ｅｄｇｅの最後の左頂点と等しい最後の右頂点を有する開いたエッジが選択される。ステップ３２１１の検索により得られたエッジは、エッジｏ＿ｅｄｇｅに論理的に結合され、ｏ＿ｅｄｇｅの左頂点がステップ３２１１で選択されたエッジの右頂点になり、ｏ＿ｅｄｇｅの最後の右頂点が選択されたエッジの最後の右頂点となるように単一のエッジが得られる。繰り返し使用された最後の左頂点は破棄され、ラベルｏ＿ｅｄｇｅは得られたエッジに割り当てられる。ステップ３２０３の結果が真の場合、プロセスはステップ３２０５へと進む。ステップ３２０５において、ステップ３２０３で見出されたエッジがエッジｏ＿ｅｄｇｅと結合され、結果として単一の統一エッジが得られる。エッジの結合により得られる繰り返し使用された最後の左頂点は再度破棄され、ラベルｏ＿ｅｄｇｅは結果として得られたエッジに割り当てられる。
【０１４２】
プロセス３２００はステップ３２０７へと続く。ステップ３２０７において、ｏ＿ｅｄｇｅの最後の左頂点がｏ＿ｅｄｇｅの最後の右頂点と等しい場合、プロセス３２００はステップ３２０９へと進む。最後の右頂点と等しくない場合、プロセス３２００はステップ３２０３へと戻る。ステップ３２０９において、更に開いたエッジが存在する場合、プロセスはステップ３２０１へと戻る。プロセス６００の各ステップ６０１から６１３により生じる全ての開いたエッジが結合されて単純輪郭パスが形成されるときにプロセス３２００が終了し、プロセス６００も終了する。
【０１４３】
ステップ６１５におけるエッジ併合プロセス３２００中にエッジは単一の方向に交差させられるのが好ましい。例えば、図３１Ａは、７つのエッジ（例えば、３１０１）から構成されるパス３１００を示す。左右の頂点は、「左頂点」及び「右頂点」として参照される矢印により示すように表される。図３１Ａに示すように、右エッジの頂点はＲを用いて参照され、左エッジの頂点はＬを用いて参照される。図３１Ｂは、パス３１００の頂点（例えば、Ｌａ）の全てを有する概念ブロック図である。図３１Ｂに示すように、パス３１００のエッジは、エッジの左ウィングからエッジの右ウィングへと矢印（例えば、３１０３）により示される方向に交差させられるのが好ましい。これにより、エッジがその方向に従って交差させられる場合、エッジの内部が常に左側にあるという規定が確立され、エッジのオリエンテーションが一様になる。
【０１４４】
図４のプロセス４００に戻ると、図３７はステップ４０１により生じた２つの単純輪郭パス上で実行される単純パス交差プロセス３７００を示すフローチャートである。プロセス３７００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス３７００はステップ３７０１で開始される。ステップ３７０１において、２つの単純輪郭パスに対して図３８に示すような新規点作成プロセス３８００が実行される。新規点作成プロセス３８００において、各パスのうちの一方（ラベルＰａｔｈ１が割り当てられるのが好ましい）の全てのエッジが、他方（ラベルＰａｔｈ２が割り当てられるのが好ましい）の全てのエッジにより交差させられる。図３８のフローチャートを参照して新規点作成プロセス３８００を以下で詳細に説明する。
【０１４５】
プロセス３８００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス３８００はステップ３８０１で開始される。ステップ３８０１において、プロセッサ３０５によりＰａｔｈ１からのエッジが選択され、ラベルｅｄｇｅ＿１が割り当てられる。次のステップ３８０３において、プロセッサ３０５によりＰａｔｈ２からエッジが選択され、ラベルｅｄｇｅ＿２が割り当てられる。ステップ３８０５において、図３９に示すようなエッジ交差プロセス３９００が実行される。プロセス３９００において、ｅｄｇｅ＿１からのセグメントがｅｄｇｅ＿２からのセグメントにより交差させられる。ステップ３８０５で実行されるエッジ交差プロセス３９００については図３９のフローチャートを参照してより詳細に後述する。プロセス３８００の次のステップ３８０７において、処理中のパスに更にエッジが存在する場合、プロセス３８００はステップ３８０３へと戻る。エッジが存在しない場合、プロセス３８００はステップ３８０９へと進む。ステップ３８０９において、Ｐａｔｈ１に更にエッジが存在する場合、プロセス３８００はステップ３８０１へと戻る。エッジが存在しない場合、プロセス３８００はプロセス３７００のステップ３７０３へと進む。ステップ３７０３において、Ｐａｔｈ１及びＰａｔｈ２に対してパス交差プロセス４４００が実行される。パス交差プロセス４４００については図４４のフローチャートを参照して詳細に後述する。
【０１４６】
エッジ交差プロセス３９００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。エッジ交差プロセス３９００はステップ３９０１で開始され、ｅｄｇｅ＿１からの未処理のセグメントはラベルｓｅｇｍｅｎｔ＿１を割り当てられる。次のステップ３９０３において、選択されたｅｄｇｅ＿２からプロセッサ３０５により未処理のセグメントが選択され、ラベルｓｅｇｍｅｎｔ＿２が割り当てられる。次のステップ３９０５において、ｓｅｇｍｅｎｔ＿１がｓｅｇｍｅｎｔ＿２と交差する場合、ステップ３９０７の交差分類プロセス４０００においてセグメントの交点が分類される。交点は任意の適切な方法を使用して計算することができる。交点分類プロセス４０００については図４０のフローチャート４０００を参照して詳細に説明する。ステップ３９０５において、ｓｅｇｍｅｎｔ＿１がｓｅｇｍｅｎｔ＿２と交差しない場合、プロセス３９００はステップ３９１１へと進む。ステップ３９１１において、ｅｄｇｅ＿２に更に未処理のセグメントが存在する場合、プロセス３９００はステップ３９０３へと戻る。セグメントが存在しない場合、プロセス３９００はステップ３９１３へと進む。ステップ３９１３において、プロセッサ３０５によりｅｄｇｅ＿２中の全てのセグメントが未処理としてリセットされる。プロセス３９００はステップ３９０９へと進む。ステップ３９０９において、ｅｄｇｅ＿１に更に未処理のセグメントが存在する場合、プロセス３９００はステップ３９０１へと戻る。未処理のセグメントが存在しない場合、プロセス３９００はプロセス３８００のステップ３８０７へと続く。
【０１４７】
交差分類プロセス４０００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。交差分類プロセス４０００において、交点はＩＮＳＴＮ点、ＳＴ＿ＣＯＬ点、又はＥＮＤ＿ＣＯＬ点として分類される。ＩＮＳＴＮ点は純粋な交点を表し、ＳＴ＿ＣＯＬ点及びＥＮＤ＿ＣＯＬ点は共直線性のある点の最初及び最後をそれぞれ表す。プロセッサ３０５によりｓｅｇｍｅｎｔ＿１及びｓｅｇｍｅｎｔ＿２の交点として同じ座標を有する新規のＩＮＳＴＮ点が判定される。ｓｅｇｍｅｎｔ＿１及びｓｅｇｍｅｎｔ＿２が相互に共直線性がない場合、新規のＩＮＳＴＮ点はｅｄｇｅ＿１及びｅｄｇｅ＿２のｓｅｇｍｅｎｔ＿１及びｓｅｇｍｅｎｔ＿２の始点と終点との間に挿入される。その交点はｓｅｇｍｅｎｔ＿１とｓｅｇｍｅｎｔ＿２との間にある。ｓｅｇｍｅｎｔ＿１及びｓｅｇｍｅｎｔ＿２に共直線性がある場合、共直線マーク付けプロセス４１００において、ｓｅｇｍｅｎｔ＿１及びｓｅｇｍｅｎｔ＿２の交点は、ＳＴ＿ＣＯＬ点又はＥＮＤ＿ＣＯＬ点として分類される。共直線マーク付けプロセス４１００については図４１のフローチャート４１００を参照して後述する。
【０１４８】
ｓｅｇｍｅｎｔ＿１がｓｅｇｍｅｎｔ＿２上で終了するか、あるいは、ｓｅｇｍｅｎｔ＿２がｓｅｇｍｅｎｔ＿１上で終了する場合で、後述するように「有効な交差」がある場合、ｅｄｇｅ＿１及びｅｄｇｅ＿２に新規のＩＮＳＴＮ点が挿入される。有効な交差がない場合、交点と同じ座標を有する候補点セグメントが作成され、候補セグメントリストに加えられる。有効な交差という用語については、図４２Ａ及び図４２Ｂを参照して詳細に後述する。ｅｄｇｅ＿１の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿１）が、ｓｅｇｍｅｎｔ＿１がｓｅｇｍｅｎｔ＿２上で終了する場合にｓｅｇｍｅｎｔ＿２と共直線性がある場合、あるいは、ｅｄｇｅ＿２の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿２）が、ｓｅｇｍｅｎｔ＿２がｓｅｇｍｅｎｔ＿１上で終了する場合にｓｅｇｍｅｎｔ＿１と共直線性がある場合、図４１の共直線マーク付けプロセス４１００において、ｓｅｇｍｅｎｔ＿１及びｓｅｇｍｅｎｔ＿２の交点はＳＴ＿ＣＯＬ点又はＥＮＤ＿ＣＯＬ点へと分類される。
【０１４９】
図４２Ａにおいて明らかなように、ｅｄｇｅ＿１の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿１）が領域Ａ（すなわち、矢印４２０３で示される領域）にある場合、点４２０１は「有効な交差」である。逆に、ｅｄｇｅ＿１の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿１）が領域Ｂ（すなわち、矢印４２０５で示される領域）にある場合、点４２０１において有効な交差はない。更に、ｅｄｇｅ＿１の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿１）が領域Ｃ１（すなわち、矢印４２０７で示される領域）にある場合、交点はｅｄｇｅ＿１に対してＳＴ＿ＣＯＬ点として分類され、ｅｄｇｅ＿２に対してＥＮＤ＿ＣＯＬ点として分類される。ｅｄｇｅ＿１の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿１）が領域Ｃ２（すなわち、矢印４２０９で示される領域）にある場合、交点はｅｄｇｅ＿１及びｅｄｇｅ＿２に対してＳＴ＿ＣＯＬ点として分類される。
【０１５０】
図４２Ｂにおいて明らかなように、ｅｄｇｅ＿１の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿１）が領域Ａにある（すなわち、図４２Ｂに示すように）場合、点４２１１は有効な交点として分類される。ｅｄｇｅ＿１の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿１）が領域Ｂにある（すなわち、図４２Ｂに示すように）場合、点４２１１は有効な交差として分類されない。これとは対照的に、ｅｄｇｅ＿１の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿１）が領域Ｃ１にある（すなわち、図４２Ｂに示すように）場合、点４２１１はｅｄｇｅ＿１に対してＳＴ＿ＣＯＬ点として分類され、ｅｄｇｅ＿２に対してＥＮＤ＿ＣＯＬ点として分類される。ｅｄｇｅ＿１の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿１）が領域Ｃ２にある（すなわち、図４２Ｂに示すように）場合、交点４２１１はｅｄｇｅ＿１及びｅｄｇｅ＿２に対してＳＴ＿ＣＯＬ点として分類される。
【０１５１】
プロセス４０００はハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。プロセス４０００はステップ４００１で開始される。ステップ４００１において、ｓｅｇｍｅｎｔ＿１及びｓｅｇｍｅｎｔ＿２が共直線である場合、プロセス４０００はステップ４０２３へと進む。ステップ４０２３において、プロセッサ３０５によりｓｅｇｍｅｎｔ＿１及びｓｅｇｍｅｎｔ＿２に対して共直線マーク付けプロセス４１００が実行され、プロセス４０００はプロセス３９００のステップ３９１１へと続く。共直線マーク付けプロセス４１００は、交点をＳＴ＿ＣＯＬ点又はＥＮＤ＿ＣＯＬ点へと分類する。次のステップ４００３において、ｓｅｇｍｅｎｔ＿１及びｓｅｇｍｅｎｔ＿２の交点がｓｅｇｍｅｎｔ＿１とｓｅｇｍｅｎｔ＿２との間にある場合、プロセス４０００は次のステップ４０２１へと続く。ｓｅｇｍｅｎｔ＿１とｓｅｇｍｅｎｔ＿２との間にない場合、プロセス４０００はステップ４０１９へと進む。ステップ４０２１において、プロセッサ３０５によりｓｅｇｍｅｎｔ＿１及びｓｅｇｍｅｎｔ＿２の始点と終点との間に交点と同じ座標を有する新規のＩＮＳＴＮ点が挿入され、プロセス４０００はプロセス３９００のステップ３９１１へと続く。ステップ４０１９において、交点がｓｅｇｍｅｎｔ＿１間にない場合、プロセス４０００はステップ４０１７へと続く。交点がｓｅｇｍｅｎｔ＿１間にある場合、プロセス４０００はステップ４００５へと進む。ステップ４０１７において、ｅｄｇｅ＿２の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿２）がｓｅｇｍｅｎｔ＿１と共直線である場合、プロセス４０００はステップ４０１５へと進む。ステップ４０１５において、プロセッサ３０５によりｓｅｇｍｅｎｔ＿１及びｓｅｇｍｅｎｔ＿２に対してフローチャート４１００の共直線マーク付けプロセス４１００が実行される。プロセス４０００は、ステップ４０１５の終了後、プロセス３９００のステップ３９１１へと続く。ステップ４０１７において、ｅｄｇｅ＿２の次のセグメントがｓｅｇｍｅｎｔ＿１と共直線でない場合、プロセス４０００は次のステップ４０１１へと続く。ステップ４０１１において、上述のように、有効な交差が存在する場合、プロセス４０００はステップ４０２１へと戻る。有効な交差が存在しない場合、プロセス４０００はステップ４０１３へと進む。ステップ４０１３において、候補点セグメントが作成され、プロセス４０００はステップ３９１１へと続く。
【０１５２】
ステップ４００５において、交差がｓｅｇｍｅｎｔ＿２間にある場合、プロセス４０００はステップ４００７へと進む。交差がｓｅｇｍｅｎｔ＿２間にない場合、プロセス４０００はステップ４００９へと進む。ステップ４００７において、ｅｄｇｅ＿１の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿１）がｓｅｇｍｅｎｔ＿２と共直線関係にある場合、プロセス４０００は次のステップ４０１５へと続く。ｓｅｇｍｅｎｔ＿２と共直線関係にない場合、プロセス４０００はステップ４０１１へと進む。ステップ４００９において、ｅｄｇｅ＿２の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿２）又はｓｅｇｍｅｎｔ＿２がｅｄｇｅ＿１の次のセグメント（すなわち、以下のｓｅｇｍｅｎｔ＿１）又はｓｅｇｍｅｎｔ＿１と共直線関係にある場合、プロセス４０００はステップ４０１５へと進む。共直線関係にない場合、プロセス４０００はステップ４０１１へと進む。
【０１５３】
フローチャート４１００の共直線マーク付けプロセス４１００において、セグメント間のエッジへと挿入される全ての新規の点（すなわち、ＩＮＳＴＮ点、ＳＴ＿ＣＯＬ点、又はＥＮＤ＿ＣＯＬ点）は昇順にソートされる。プロセス４１００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。エッジは文字値に基づいてソートされる。文字値はセグメントの長さに対して、０と１との間の値（両端を含む）にまでスケール変更された新規の点とセグメントの始点との間の距離として定義される。同等の文字値を有する点に対して、既存の点の後に新規の点が挿入されることになる。しかし、同等の文字値を有する点において、ＳＴ＿ＣＯＬ点はＥＮＤ＿ＣＯＬ点の前に常に挿入され、ＥＮＤ＿ＣＯＬ点は常にエッジの端部に挿入される。現在のセグメントの始点が現在のエッジの始点であり、挿入される新規の点が現在のセグメントの始点と同等の座標を有するＳＴ＿ＣＯＬ点として分類される場合を除き、全ての新規の点は現在のセグメント間に挿入される。このような新規のＳＴ＿ＣＯＬ点は現在のエッジの始点より前に挿入される。
【０１５４】
新規のセグメントと共直線性のあるセグメントを明確に識別できるようにするために、上述のように新規の点がソートされる。概念上、始点４３０１及び終点４３０３を有するセグメントに対する図４３の例において明らかであるように、交点は既存のセグメントを２つのセグメントに分割する。
【０１５５】
上述のように、共直線マーク付けプロセス４１００は、交点をＳＴ＿ＣＯＬ点又はＥＮＤ＿ＣＯＬ点へと分類する。共直線マーク付けプロセス４１００において、交点がｅｄｇｅ＿１に対する共直線性のある点の開始を表す場合、新規のＳＴ＿ＣＯＬ点が作成され、ｅｄｇｅ＿１のｓｅｇｍｅｎｔ＿１に挿入される。共直線性のある点の開始を表さない場合、ＥＮＤ＿ＣＯＬ点が作成される。ｅｄｇｅ＿２のｓｅｇｍｅｎｔ＿２に対しても同様のプロセスが繰り返される。続いて、ｅｄｇｅ＿１及びｅｄｇｅ＿２が交差させられ、エッジ間の共直線性が終了する共通の点が識別される。先に行なった交点の分類に基づいてｅｄｇｅ＿１及びｅｄｇｅ＿２の双方に対して、この共通の点はＳＴ＿ＣＯＬ点又はＥＮＤ＿ＣＯＬ点へと分類される。
【０１５６】
また、プロセス４１００中にｅｄｇｅ＿１及びｅｄｇｅ＿２を交差させる間、候補セグメントが作成され、候補セグメントリストに加えられる。共直線セグメントの対ごとに作成される候補セグメントの本数は、ｅｄｇｅ＿１及びｅｄｇｅ＿２の内部によって決まる。ｅｄｇｅ＿１及びｅｄｇｅ＿２の内部が重なる場合、１つの候補セグメントが作成される。重ならない場合、２つの候補セグメントが作成される。ｅｄｇｅ＿１及びｅｄｇｅ＿２と関連付けられたクリップ規則とその方向とが類似している場合及び関連付けられたクリップ規則（表１を参照して上述）とその方向とが異なっている場合、ｅｄｇｅ＿１及びｅｄｇｅ＿２の内部は重なるものと考えられる。それ以外の場合、ｅｄｇｅ＿１及びｅｄｇｅ＿２の内部は重なるものとは考えられない。
【０１５７】
共直線マーク付けプロセス４１００はステップ４１０１で開始される。ステップ４１０１において、交点がｅｄｇｅ＿１に対する共直線性のある点の開始を表す場合、プロセス４１００はステップ４１１３へと進む。共直線性のある点の開始を表さない場合、プロセス４１００はステップ４１０３へと進む。ステップ４１１３において、交点の座標を有する新規のＳＴ＿ＣＯＬ点がｅｄｇｅ＿１のｓｅｇｍｅｎｔ＿１の始点と終点との間にソート済の状態で（すなわち、上述のように）挿入され、プロセス４１００はステップ４１０５へと進む。ステップ４１０３において、交点の座標を有する新規のＥＮＤ＿ＣＯＬ点がｅｄｇｅ＿１のｓｅｇｍｅｎｔ＿１の始点と終点との間にソート済の状態で挿入され、プロセス４１００はステップ４１０５へと進む。ステップ４１０５において、交点がｅｄｇｅ＿２に対する共直線性のある点の開始を表す場合、プロセス４１００はステップ４１１５へと進む。共直線性のある点の開始を表さない場合、プロセス４１００はステップ４１０７へと進む。ステップ４１１５において、交点の座標を有する新規のＳＴ＿ＣＯＬ点がｅｄｇｅ＿２のｓｅｇｍｅｎｔ＿２の始点と終点との間にソート済の状態で挿入され、プロセスはステップ４１０９へと進む。ステップ４１０７において、交点の座標を有する新規のＥＮＤ＿ＣＯＬ点がｅｄｇｅ＿２のｓｅｇｍｅｎｔ＿２の始点と終点との間にソート済の状態で挿入され、プロセス４１００はステップ４１０９へと進む。
【０１５８】
ステップ４１０９において、ｅｄｇｅ＿１のクリップ規則（表１参照）がｅｄｇｅ＿２のクリップ規則と等しい場合、プロセス４１００はステップ４１１７へと進む。ｅｄｇｅ＿２のクリップ規則と等しくない場合、プロセス４１００はステップ４１１１へと進む。ステップ４１１７において、ｅｄｇｅ＿１の方向がｅｄｇｅ＿２の方向と等しい場合、プロセス４１００はステップ４１１９へと進む。ステップ４１１９において、プロセッサ３０５によりメモリ３０６に格納されたフラグ「ｎ＿ｃａｎｓｅｇ」が１と等しくなるように設定される。ｅｄｇｅ＿２の方向と等しくない場合、プロセス４１００はステップ４１２１へと進む。ステップ４１２１において、フラグは２と等しくなるように設定され、プロセス４１００は次のステップ４１２７へと続く。後述するように、メモリに格納されたフラグｎ＿ｃａｎｓｅｇはステップ４１２７で使用され、作成される候補セグメントの本数が判定される。ステップ４１１１において、ｅｄｇｅ＿１の方向がｅｄｇｅ＿２の方向と等しい場合、プロセス４１００はステップ４１２５へと進む。ステップ４１２５において、フラグ「ｎ＿ｃａｎｓｅｇ」は２と等しくなるように設定される。ｅｄｇｅ＿２の方向と等しくない場合、プロセス４１００はステップ４１２３へと進む。ステップ４１２３において、フラグは１と等しくなるように設定され、プロセス４１００は次のステップ４１２７へと続く。
【０１５９】
ステップ４１２７において、プロセッサ３０５により共直線性が終了する点（すなわち、ｃｏｍｍｏｎ＿ｐｏｉｎｔ）が判定されるまで、ｅｄｇｅ＿１及びｅｄｇｅ＿２は交差させられる。ｅｄｇｅ＿１及びｅｄｇｅ＿２の交差中に、エッジの共直線の部分に沿って１つ又は２つの候補セグメント（すなわち、フラグｎ＿ｃａｎｓｅｇの値による）が作成される。プロセス４１００のステップ４１２７の実行中に交差させられるｅｄｇｅ＿１及びｅｄｇｅ＿２からの各セグメントがプロセッサ３０５によりマーク付けされる。フローチャート４１００のプロセスは次のステップ４１２９へと続く。ステップ４１２９において、交点がｅｄｇｅ＿１に対する共直線性のある点の開始を表す場合、プロセス４１００はステップ４１３１へと進む。共直線性のある点の開始を表さない場合、プロセス４１００はステップ４１３３へと進む。ステップ４１３１において、ｃｏｍｍｏｎ＿ｐｏｉｎｔの座標を有する新規のＥＮＤ＿ＣＯＬ点がｅｄｇｅ＿１のセグメントの始点と終点との間にソート済の状態で（すなわち、上述のように）挿入され、プロセスはステップ４１３５へと進む。ステップ４１３３において、ｃｏｍｍｏｎ＿ｐｏｉｎｔの座標を有する新規のＳＴ＿ＣＯＬ点がｅｄｇｅ＿１の共直線性が終了するセグメントの始点と終点との間にソート済の状態で挿入され、プロセスはステップ４１３５へと進む。ステップ４１３５において、交点がｅｄｇｅ＿２に対する共直線性のある点の開始を表す場合、プロセス４１００はステップ４１３７へと進む。共直線性のある点の開始を表さない場合、プロセス４１００はステップ４１３９へと進む。
【０１６０】
ステップ４１３７において、ｃｏｍｍｏｎ＿ｐｏｉｎｔの座標を有する新規のＥＮＤ＿ＣＯＬ点がプロセッサ３０５によってｅｄｇｅ＿２の共直線性が終了するセグメントの始点と終点との間にソート済の状態で（すなわち、上述のように）挿入され、プロセス４１００は終了する。ステップ４１３９において、ｃｏｍｍｏｎ＿ｐｏｉｎｔの座標を有する新規のＳＴ＿ＣＯＬ点がプロセッサ３０５によってｅｄｇｅ＿２の共直線性が終了するセグメントの始点と終点との間にソート済の状態で挿入され、フローチャート４１００のプロセスは終了する。
【０１６１】
フローチャート３７００の単純パス交差プロセスに戻ると、ステップ３７０１に引き続き、プロセス３７００はステップ３７０３へと進む。ステップ３７０３において、図４４のフローチャートにより明らかであるように、プロセッサ３０５によりパス交差プロセス４４００が実行される。パス交差プロセス４４００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。パス交差プロセス４４００は、Ｐａｔｈ１及びＰａｔｈ２中の全てのエッジを交差させる。プロセス４４００において、特定のパス中のエッジが交差させられる前に、パス全体に対して有効である候補フラグ（ラベルｃａｎｄｉｄａｔｅ＿ｆｌａｇを割り当てられるのが好ましい）が初期化される。候補フラグはパスに対するクリップ規則に従って初期化されるので、上述のように、各パスに対して実行される結果の集合演算は影響を受ける。プロセス４４００はステップ４４０１で開始される。ステップ４４０１において、ｃａｎｄｉｄａｔｅ＿ｆｌａｇは初期化される。次のステップ４４０３において、プロセッサ３０５によりＰａｔｈ１からエッジが選択され、ｃｕｒｒｅｎｔ＿ｅｄｇｅとして割り当てられる。プロセス４４００は次のステップ４４０５へと続く。ステップ４４０５において、プロセッサ３０５によりエッジ交差プロセス４５００が実行され、点が対向するパスの内部の内側にあるか、あるいは、外側にあるかを判定するためにｃｕｒｒｅｎｔ＿ｅｄｇｅ中の全ての点が検査される。エッジ交差プロセス４５００については図４５のフローチャートを参照して後述する。プロセス４４００の次のステップ４４０９において、Ｐａｔｈ１に更に未処理のエッジが存在する場合、プロセス４４００はステップ４４０３へと戻る。未処理のエッジが存在しない場合、プロセス４４００はステップ４４１１へと進む。ステップ４４１１において、Ｐａｔｈ２のエッジに対してｃａｎｄｉｄａｔｅ＿ｆｌａｇが初期化される。次のステップ４４１３において、プロセッサ３０５によりＰａｔｈ２からエッジが選択され、ｃｕｒｒｅｎｔ＿ｅｄｇｅとして割り当てられる。プロセス４４００は次のステップ４４１５へと続く。ステップ４４１５において、エッジ交差プロセス４５００が実行され、点が対向するパスの内部の内側にあるか、あるいは、外側にあるかを判定するためにｃｕｒｒｅｎｔ＿ｅｄｇｅ中の全ての点が検査される。次のステップ４４１７において、Ｐａｔｈ２に更に未処理のエッジが存在する場合、プロセス４４００はステップ４４１３へと戻る。未処理のエッジが存在しない場合、プロセス４４００はプロセス４００のステップ４０５へと進む。
【０１６２】
エッジ交差プロセス４５００は、ハードディスクドライブ３１０に常駐し、プロセッサ３０５による実行の際に読み出され制御されるアプリケーションプログラムとして実現されるのが好ましい。エッジ交差プロセス４５００において、現在の点がＳＴ＿ＣＯＬ点として分類される場合、メモリ３０６に格納され、候補セグメントが出力されるのを防止する共直線のカウンタが増分される。共直線カウンタが増分される前にカウンタの値が０である場合、状態フラグ（ラベルｓｔａｔｕｓ＿ｆｌａｇが割り当てられるのが好ましい）の値が切り換えられる。しかし、現在の点がＥＮＤ＿ＣＯＬ点として分類される場合、共直線カウンタは減分され、値が０の場合にはｓｔａｔｕｓ＿ｆｌａｇが再初期化される。状態フラグが候補フラグと一致するとき、候補セグメントが作成される。プロセス４５００はステップ４５０１で開始される。ステップ４５０１において、ｃｕｒｒｅｎｔ＿ｅｄｇｅの始点がＳＴ＿ＣＯＬ点として分類される場合、プロセス４５００はステップ４５０５へと進む。ＳＴ＿ＣＯＬ点として分類されない場合、プロセスはステップ４５０３へと進む。ステップ４５０５において、共直線カウンタは増分され、ｓｔａｔｕｓ＿ｆｌａｇはｃａｎｄｉｄａｔｅ＿ｆｌａｇに合わせて設定される。プロセス４５００はステップ４５０７へと進む。
【０１６３】
ステップ４５０３において、ｓｔａｔｕｓ＿ｆｌａｇは初期化される。次のステップ４５０７において、プロセッサ３０５によりｃｕｒｒｅｎｔ＿ｐｏｉｎｔとしてｃｕｒｒｅｎｔ＿ｅｄｇｅからの未処理の点が選択される。次のステップ４５１１において、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔがＳＴ＿ＣＯＬ点として分類される場合、プロセス４５００はステップ４５１５へと進む。ＳＴ＿ＣＯＬ点として分類されない場合、プロセス４５００はステップ４５０９へと進む。ステップ４５１５において、共直線カウンタが０と等しい場合、プロセス４５００はステップ４５２１へと進む。ステップ４５２１において、ｓｔａｔｕｓ＿ｆｌａｇの値が切り換えられる。共直線カウンタが０と等しくない場合、プロセス４５００は直接ステップ４５２７へと進む。ステップ４５２７において、共直線カウンタが増分され、プロセス４５００はステップ４５０７へと戻る。
【０１６４】
ステップ４５０９において、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔがＥＮＤ＿ＣＯＬ点として分類される場合、プロセス４５００はステップ４５１７へと進む。ステップ４５１７において、プロセッサ３０５により共直線カウンタが減分される。ＥＮＤ＿ＣＯＬ点として分類されない場合、プロセス４５００はステップ４５１３へと進む。次のステップ４５２３において、メモリ３０６に格納された共直線カウンタが０と等しくない場合、プロセスはステップ４５０７へと戻る。共直線カウンタが０と等しい場合、プロセス４５００はステップ４５２９へと進む。ステップ４５２９において、ｓｔａｔｕｓ＿ｆｌａｇは初期化される。
【０１６５】
ステップ４５１３において、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔが交点として分類される場合、プロセス４５００はステップ４５１９へと進む。交点として分類されない場合、プロセス４５００はステップ４５３１へと進む。ステップ４５１９において、共直線カウンタが０と等しい場合、プロセス４５００はステップ４５２５へと進む。ステップ４５２５において、ｓｔａｔｕｓ＿ｆｌａｇの値が切り換えられる。共直線カウンタが０と等しくない場合、プロセス４５００はステップ４５０７へと戻る。
【０１６６】
ステップ４５３１において、ｓｔａｔｕｓ＿ｆｌａｇがｃａｎｄｉｄａｔｅ＿ｆｌａｇと等しい場合、プロセス４５００はステップ４５３３へと進む。ｃａｎｄｉｄａｔｅ＿ｆｌａｇと等しくない場合、プロセス４５００は直接ステップ４５３５へと進む。ステップ４５３３において、ｃｕｒｒｅｎｔ＿ｐｏｉｎｔから開始され、直後の点で終了する候補セグメントが作成される。ステップ４５３５において、ｃｕｒｒｅｎｔ＿ｅｄｇｅに更に未処理の点が存在する場合、プロセス４５００はステップ４５０７へと戻る。未処理の点が存在しない場合、プロセス４５００は終了する。
【０１６７】
フローチャート４００に戻ると、ステップ４０３の単純パス交差プロセス３７００に引き続き、プロセス４００は次のステップ４０５で終了する。
【０１６８】
ステップ４０５において、ステップ４０３の単純パス交差プロセス中に作成された候補セグメントから結果の輪郭パスを形成するために、輪郭構築プロセスが実行される。輪郭構築プロセスはステップ４０１の単純輪郭変換プロセスに類似している。唯一の相違点は、プロセッサ３０５により輪郭構築プロセスに対してステップ６０９の交差検出プロセス、ステップ６１１の処理交差プロセス、及び全ての関連するサブステップが実行されないことにある。その代わりに、ステップ４０５のプロセスにおいて、ステップ６０９及び６１１は次のバンドラインに従ってアクティブセグメントテーブルを更新する単一のステップに置き換えられる。更に、各パスと関連付けられる塗りつぶし規則は、輪郭構築プロセスに対して奇偶ワインディング塗りつぶし規則及びノンゼロワインディング塗りつぶし規則のいずれかであると想定することができる。
【０１６９】
【発明の効果】
上述の各方法は、パスが閉じたエッジ（例えば、ポリゴン）から構成されることのみを必要とし、処理される各エッジの位置に対する制限なしにエッジが任意の複雑度のポリゴンを表すことができるパスを処理することができる。特に、部分的に又は全体的に共直線性を有するセグメントや、別のセグメントで開始及び／又は終了するセグメントや、別のセグメントの開始頂点又は終端頂点で開始及び／又は終了するセグメントや、縮退の場合の交点と一致するセグメント、を有する縮退パスは、全て上述の方法に従って処理することができる。
【０１７０】
また、上述の各方法は、奇偶ワインディング塗りつぶし規則及びノンゼロワインディング塗りつぶし規則のいずれかに従って構成されたパスを処理することができる。当業者は、従来技術において既知の他の塗りつぶし規則に従って構成されたパスを処理するために上述の方法に軽微な変更を加えるだけでよいことを認識するであろう。更に、上述の方法は縮退パスを処理するときにはいずれの頂点も移動又は撹乱させない（すなわち、全ての頂点は元の位置で処理される）ので上述の各方法は非常に正確である。
【０１７１】
最後に、上述の各方法は、従来のパス処理方法よりもかなり単純で高速である。上述の各方法は輪郭パスを生成するが、これは、輪郭パスをもたらす入力パスよりも制限がかなり緩い。このため、入力パスのダウンストリーム処理中には最小限の適合のみ（適合がある場合でも）が必要とされる。更に、結果として生じる輪郭パスが単純であるので、このようなダウンストリーム処理では速度の改善が実現される。
【０１７２】
以上、本発明の幾つかの実施例だけを説明したが、本発明の趣旨から逸脱することなく、変形や変更を行なうことができる。各実施例は例示のためのものであって、限定することを目的としない。例えば、スプラインセグメントが予めベクトル化される場合、上述の方法はスプラインセグメントを用いて実行することができる。
【図面の簡単な説明】
【図１Ａ】パスの構成要素を定義するのに使用されるツリー構造の一例を示す図である。
【図１Ｂ】パスの一例を示す図である。
【図２】上向きのセグメント及び下向きのセグメントの好適な定義を表す４つの異なるセグメントを示す図である。
【図３】記載された構成を実施することが可能な汎用のコンピュータの概略ブロック図である。
【図４】２つ以上の任意の入力パスから単純出力パスを判定する方法を示すフローチャートである。
【図５Ａ】論理積集合演算に従って処理される２つのパスを示す図である。
【図５Ｂ】図５Ａの２つのパスの交差により生成される最終単純輪郭パスを示す図である。
【図６Ａ】奇偶ワインディング塗りつぶし規則又はノンゼロワインディング塗りつぶし規則に従って構成されたパスを単純輪郭パスに変換する方法を示すフローチャートである。
【図６Ｂ】本明細書の記述を通して使用される記号の定義を示す図である。
【図７】レフトネスの比較を表すために使用される６つのセグメント（すなわち、セグメントＡからＦ）を示す図である。
【図８】特定の入力パスに対してセグメントテーブルを構築する方法を示すフローチャートである。
【図９】アクティブセグメントテーブルを更新する方法を示すフローチャートである。
【図１０】特定の点上のセグメントを分割する必要があるか否かを判定するための分割検出プロセスを示すフローチャートである。
【図１１】特定の点上の終了セグメント及び開始セグメントを分離するためのセグメント分割プロセスを示すフローチャートである。
【図１２】バンドラインに対するセグメントの分割の一例を示す図である。
【図１３】アクティブセグメントテーブル分割書込みプロセスを示すフローチャートである。
【図１４】アクティブセグメントテーブル書込みプロセスを示すフローチャートである。
【図１５Ａ】水平セグメントを分割する必要がある点を判定するための水平分割プロセスを示すフローチャートである。
【図１５Ｂ】水平セグメントを分割する必要がある点を判定するための水平分割プロセスを示すフローチャートである。
【図１５Ｃ】水平セグメントを分割する必要がある点を判定するための水平分割プロセスを示すフローチャートである。
【図１５Ｄ】水平セグメントを分割する必要がある点を判定するための水平分割プロセスを示すフローチャートである。
【図１６】水平セグメントを分割するための水平セグメント分割プロセスを示すフローチャートである。
【図１７】バンドラインのセグメント上で実行される図１５の水平分割プロセスの一例を示す図である。
【図１８】ノンゼロワインディング塗りつぶし規則を用いて構成された入力パスに対する単純輪郭パスを形成するエッジを作成するためのセグメント割当て／エッジ作成プロセスを示すフローチャートである。
【図１９Ａ】ノンゼロワインディング塗りつぶし規則を用いて構成された入力パスを処理するためのローカル最小点プロセスを示すフローチャートである。
【図１９Ｂ】ノンゼロワインディング塗りつぶし規則を用いて構成された入力パスを処理するためのローカル最小点プロセスを示すフローチャートである。
【図２０】セグメントを左境界線セグメント又は右境界線セグメントとして分類するための必要条件を示す図である。
【図２１】ノンゼロワインディング塗りつぶし規則を用いて構成された入力パスを処理するための複合点プロセスを示すフローチャートである。
【図２２Ａ】入力パスに対する単純輪郭パスを形成するエッジを作成するためのセグメント結合／エッジ作成プロセスを示すフローチャートである。
【図２２Ｂ】入力パスに対する単純輪郭パスを形成するエッジを作成するためのセグメント結合／エッジ作成プロセスを示すフローチャートである。
【図２３】奇偶ワインディング塗りつぶし規則を用いて構成された入力パスに対する単純輪郭パスを形成するエッジを作成するためのセグメント割当て／エッジ作成プロセスを示すフローチャートである。
【図２４】奇偶ワインディング塗りつぶし規則を用いて構成された入力パスを処理するためのローカル最小点プロセスを示すフローチャートである。
【図２５】奇偶ワインディング塗りつぶし規則を用いて構成された入力パスを処理するための複合点プロセスを示すフローチャートである。
【図２６】エッジを作成するためのセグメント結合／エッジ作成プロセスを示すフローチャートである。
【図２７Ａ】最後の終了セグメントに後続する点から開始されるセグメントを分類するための開始境界線セグメント選択プロセスを示すフローチャートである。
【図２７Ｂ】最後の終了セグメントに後続する点から開始されるセグメントを分類するための開始境界線セグメント選択プロセスを示すフローチャートである。
【図２８Ａ】交差セグメントを検出するための交差検出プロセスを示すフローチャートである。
【図２８Ｂ】交差セグメントを検出するための交差検出プロセスを示すフローチャートである。
【図２９Ａ】ノンゼロワインディング塗りつぶし規則を使用して構成された入力パスに対する交差処理プロセスを示すフローチャートである。
【図２９Ｂ】ノンゼロワインディング塗りつぶし規則を使用して構成された入力パスに対する交差処理プロセスを示すフローチャートである。
【図３０】奇偶ワインディング塗りつぶし規則を使用して構成された入力パスに対する交差処理プロセスを示すフローチャートである。
【図３１Ａ】７つのエッジから構成されるパスの一例を示す図である。
【図３１Ｂ】図３１Ａのパスのラベル付けされた全ての頂点を示す概念ブロック図である。
【図３２】全ての開いたエッジを併合して単純輪郭パスを形成するためのエッジ併合プロセスを示すフローチャートである。
【図３３】境界線セグメントを結合するためのセグメント結合プロセスを示すフローチャートである。
【図３４】グローバルフラグ及び水平フラグを更新するためのカウンタ更新プロセスを示すフローチャートである。
【図３５】ある点においてエッジを作成するためのエッジ作成プロセスを示すフローチャートである。
【図３６Ａ】セグメントが左としてマーク付けされるか、あるいは、右としてマーク付けされるかを判定するための境界線セグメント選択プロセスを示すフローチャートである。
【図３６Ｂ】セグメントが左としてマーク付けされるか、あるいは、右としてマーク付けされるかを判定するための境界線セグメント選択プロセスを示すフローチャートである。
【図３７】２つの単純輪郭パスに対して実行される単純パス交差プロセスを示すフローチャートである。
【図３８】新規点作成プロセスを示すフローチャートである。
【図３９】エッジ交差プロセスを示すフローチャートである。
【図４０Ａ】交差分類プロセスを示すフローチャートである。
【図４０Ｂ】交差分類プロセスを示すフローチャートである。
【図４１Ａ】共直線マーク付けプロセスを示すフローチャートである。
【図４１Ｂ】共直線マーク付けプロセスを示すフローチャートである。
【図４１Ｃ】共直線マーク付けプロセスを示すフローチャートである。
【図４２Ａ】有効な交点の一例を示す図である。
【図４２Ｂ】有効な交点の一例を示す図である。
【図４３】交点により２つのセグメントに分割されるセグメントを示す図である。
【図４４】パス交差プロセスを示すフローチャートである。
【図４５Ａ】エッジ交差プロセスを示すフローチャートである。
【図４５Ｂ】エッジ交差プロセスを示すフローチャートである。
【図４６Ａ】ノンゼロワインディング塗りつぶし規則を使用して構成された入力パスに対する更なる交差処理プロセスを示すフローチャートである。
【図４６Ｂ】ノンゼロワインディング塗りつぶし規則を使用して構成された入力パスに対する更なる交差処理プロセスを示すフローチャートである。
【図４６Ｃ】ノンゼロワインディング塗りつぶし規則を使用して構成された入力パスに対する更なる交差処理プロセスを示すフローチャートである。
【図４７】図４６Ａ、図４６Ｂ、及び図４６Ｃのプロセス中に実行されるセグメント分割割当てプロセスを示すフローチャートである。
【図４８】図４６Ａ、図４６Ｂ、及び図４６Ｃのプロセス中に実行されるセグメント分割プロセスを示すフローチャートである。
【図４９】図４６Ａ、図４６Ｂ、及び図４６Ｃのプロセス中に実行されるセグメント結合プロセスを示すフローチャートである。
【図５０】図４６Ａ、図４６Ｂ、及び図４６Ｃのプロセス中に実行されるエッジ作成プロセスを示すフローチャートである。
【図５１】奇偶ワインディング塗りつぶし規則を使用して構成された入力パスに対する更なる交差処理プロセスを示すフローチャートである。
【図５２Ａ】図５１のプロセス中に実行されるセグメント分割割当てプロセスを示すフローチャートである。
【図５２Ｂ】図５１のプロセス中に実行されるセグメント分割割当てプロセスを示すフローチャートである。
【図５３】図５１のプロセス中に実行されるエッジ作成プロセスを示すフローチャートである。
【符号の説明】
１００…ツリー構造、１０２…サンプルパス、２００、２０１、２０２、２０３、５０１、５０２、５０３、５０４、５０５、５０６、１２０１、１２０２、１２０３、１２０４、１２０５、１２０６、１７０１、１７０３、１７０５、１７０７…セグメント、３００…コンピュータシステム、３０１…コンピュータモジュール、５１０…最終単純輪郭パス、３１００…パス
【図１Ａ】
0003796478.tif 000003
【図１Ｂ】
0003796478.tif 000004
【図２】
0003796478.tif 000005
【図３】
0003796478.tif 000006
【図４】
0003796478.tif 000007
【図５Ａ】
0003796478.tif 000008
【図５Ｂ】
0003796478.tif 000009
【図６Ａ】
0003796478.tif 000010
【図６Ｂ】
0003796478.tif 000011
【図７】
0003796478.tif 000012
【図８】
0003796478.tif 000013
【図９】
0003796478.tif 000014
【図１０】
0003796478.tif 000015
【図１１】
0003796478.tif 000016
【図１２】
0003796478.tif 000017
【図１３】
0003796478.tif 000018
【図１４】
0003796478.tif 000019
【図１５Ａ】
0003796478.tif 000020
【図１５Ｂ】
0003796478.tif 000021
【図１５Ｃ】
0003796478.tif 000022
【図１５Ｄ】
0003796478.tif 000023
【図１６】
0003796478.tif 000024
【図１７】
0003796478.tif 000025
【図１８】
0003796478.tif 000026
【図１９Ａ】
0003796478.tif 000027
【図１９Ｂ】
0003796478.tif 000028
【図２０】
0003796478.tif 000029
【図２１】
0003796478.tif 000030
【図２２Ａ】
0003796478.tif 000031
【図２２Ｂ】
0003796478.tif 000032
【図２３】
0003796478.tif 000033
【図２４】
0003796478.tif 000034
【図２５】
0003796478.tif 000035
【図２６】
0003796478.tif 000036
【図２７Ａ】
0003796478.tif 000037
【図２７Ｂ】
0003796478.tif 000038
【図２８Ａ】
0003796478.tif 000039
【図２８Ｂ】
0003796478.tif 000040
【図２９Ａ】
0003796478.tif 000041
【図２９Ｂ】
0003796478.tif 000042
【図３０】
0003796478.tif 000043
【図３１Ａ】
0003796478.tif 000044
【図３１Ｂ】
0003796478.tif 000045
【図３２】
0003796478.tif 000046
【図３３】
0003796478.tif 000047
【図３４】
0003796478.tif 000048
【図３５】
0003796478.tif 000049
【図３６Ａ】
0003796478.tif 000050
【図３６Ｂ】
0003796478.tif 000051
【図３７】
0003796478.tif 000052
【図３８】
0003796478.tif 000053
【図３９】
0003796478.tif 000054
【図４０Ａ】
0003796478.tif 000055
【図４０Ｂ】
0003796478.tif 000056
【図４１Ａ】
0003796478.tif 000057
【図４１Ｂ】
0003796478.tif 000058
【図４１Ｃ】
0003796478.tif 000059
【図４２Ａ】
0003796478.tif 000060
【図４２Ｂ】
0003796478.tif 000061
【図４３】
0003796478.tif 000062
【図４４】
0003796478.tif 000063
【図４５Ａ】
0003796478.tif 000064
【図４５Ｂ】
0003796478.tif 000065
【図４６Ａ】
0003796478.tif 000066
【図４６Ｂ】
0003796478.tif 000067
【図４６Ｃ】
0003796478.tif 000068
【図４７】
0003796478.tif 000069
【図４８】
0003796478.tif 000070
【図４９】
0003796478.tif 000071
【図５０】
0003796478.tif 000072
【図５１】
0003796478.tif 000073
【図５２Ａ】
0003796478.tif 000074
【図５２Ｂ】
0003796478.tif 000075
【図５３】
0003796478.tif 000076