(57)【要約】      （修正有）【課題】  コンピュータベースの印刷システムにおいて、高速印刷用の安価な印刷システムを提供する。【解決手段】  画像を印刷する方法が開示される。この方法は、ホスト１０２において印刷対象の画像から複数の重なり合わないグラフィックオブジェクトを含む視覚的に同等の画像の表示リスト表現を生成することと、ホスト１０２と通信を行なうプリンタ１０８において重なり検出を実行することなく、表示リスト表現を使用してプリンタ１０８において視覚的に同等の画像に対して走査線レンダリングを行なうこととから成る。【選択図】  図１
2004152267.tif 000002
【特許請求の範囲】
【請求項１】
画像を印刷する方法において、
ホストにおいて印刷対象の画像から複数の重なり合わないグラフィックオブジェクトを含む視覚的に同等の画像の表示リスト表現を生成する工程と、
前記ホストと通信を行なうプリンタにおいて重なり検出を実行することなく、前記表示リスト表現を使用して前記プリンタにおいて前記視覚的に同等の画像に対して走査線レンダリングを行なう工程と、
を有することを特徴とする方法。
【請求項２】
第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を、第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する方法であって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類する工程と、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義する工程と、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義する工程と、
を有することを特徴とする方法。
【請求項３】
複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を、単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する方法であって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類する工程と、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義する工程と、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義する工程と、
を有することを特徴とする方法。
【請求項４】
第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を、第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する方法であって、
現在の走査線ごとに、
（ａ）現在の走査方向において前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定する工程と、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する工程と、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する工程と、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復する工程とを有し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成することを特徴とする方法。
【請求項５】
複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する方法であって、
現在の走査線ごとに、
（ａ）現在の走査方向において、前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定する工程と、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する工程と、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する工程と、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復する工程とを有し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成することを特徴とする方法。
【請求項６】
前記第１の組の重なり合うグラフィックオブジェクト及び前記第２の組の重なり合わないグラフィックオブジェクトのうちの少なくとも一方は不透明であることを特徴とする請求項２に記載の方法。
【請求項７】
画像を印刷する装置において、
ホストにおいて印刷対象の画像から複数の重なり合わないグラフィックオブジェクトを含む視覚的に同等の画像の表示リスト表現を生成する手段と、
前記ホストと通信を行なうプリンタにおいて重なり検出を実行することなく、前記表示リスト表現を使用して前記プリンタにおいて前記視覚的に同等の画像に対して走査線レンダリングを行なう手段と、
を有することを特徴とする装置。
【請求項８】
第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する装置であって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類する手段と、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義する手段と、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義する手段と、
を有することを特徴とする装置。
【請求項９】
複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する装置であって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類する手段と、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義する手段と、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義する手段と、
を有することを特徴とする装置。
【請求項１０】
第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する装置であって、
（ａ）現在の走査方向において前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定する手段と、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する手段と、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する手段と、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復する手段とを有し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成することを特徴とする装置。
【請求項１１】
複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する装置であって、
（ａ）現在の走査方向において前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定する手段と、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する手段と、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する手段と、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復する手段とを有し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成することを特徴とする装置。
【請求項１２】
第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する方法を実行するようにプロセッサに指示するコンピュータプログラムであって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類するコードと、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義するコードと、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義するコードと、
を有することを特徴とするコンピュータプログラム。
【請求項１３】
複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する方法を実行するようにプロセッサに指示するコンピュータプログラムであって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類するコードと、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義するコードと、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義するコードと、
を有することを特徴とするコンピュータプログラム。
【請求項１４】
第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する方法を実行するようにプロセッサに指示するコンピュータプログラムであって、
現在の走査線に関して、
（ａ）現在の走査方向において前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定するコードと、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義するコードと、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義するコードと、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復するコードとを有し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成することを特徴とするコンピュータプログラム。
【請求項１５】
複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する方法を実行するようにプロセッサに指示するコンピュータプログラムであって、
現在の走査線に関して、
（ａ）現在の走査方向において前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定するコードと、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義するコードと、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義するコードと、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復するコードとを有し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成することを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、コンピュータベースの印刷システムに関し、特に、高速印刷用の安価な印刷システムに関する。
【背景技術】
【０００２】
図１は、パーソナルコンピュータ（ＰＣ）ベースの印刷用のシステム１００の機能ブロック図を示す。プリンティングプリプロセッサ１０４を有するホストマシン１０２は、接続１０６を介して通信バス１１４と通信を行なう。組込み型プリンティングプロセッサ１１０を有するプリンタ１０８は、接続１１２を介して通信バス１１４と通信を行なう。
【０００３】
図２は、図１のシステムが印刷を実行する際に使用する包括的なプロセス３００のフローチャートを示す。第１のステップ３０２では、ページ記述言語（ＰＤＬ）で記述された入力データを解析する。ステップ３０６では、そこからオブジェクト表現を生成する。後続のステップ３１０では、オブジェクトに対して走査線処理を行なう。ステップ３１４では、最終の印刷ステップ３１８で印刷するために、走査線処理後のデータを一連の画素へとレンダリングする。通常、ステップ３０２から３１０は、矢印３２２により示されるように、ホストマシン１０２においてプリンティングプリプロセッサ１０４により実現されるが、ステップ３１４から３１８は、プリンタ１０８においてプリンティングプロセッサ１１０及びプリントエンジン２２２により実行される（図３参照）。
【０００４】
プリンタシステム１００では、通信バス１１４は、通常、ＵＳＢ（universal serial bus）などの低速のシリアルプロトコルを使用するか、あるいは、ＩＥＥＥ１２８４などのパラレルプロトコルを使用する。
【０００５】
低コストのプリンタでは、プリンタ１０８のコストを最小限に抑えるため、プリンティングプロセッサ１１０を低コストの装置にする必要がある。プロセッサ１１０にはハードウェア的な制約が課されるため、ステップ３１０では、プレレンダリング済のビットマップがホストマシンのプリプロセッサ１０４で生成される手法が用いられる。これはビットマップ手法と呼ばれる。プレレンダリング済のビットマップは、ステップ３１４で一連の画素へのレンダリングを実行するために、プリンタ１０８中のプロセッサ１１０へと送信される。
【０００６】
Ａ４サイズ６色インクバブルジェット方式の１ページ分に対するプレレンダリング済の圧縮ビットマップは、通常、３５から４０メガバイトのデータを消費し、ＵＳＢプロトコルを使用する伝送で４０から５０秒が必要である。これはかなりの遅延ではあるが、安価なプリンタのユーザは、コストと速度との兼ね合いに概ね満足している。
【０００７】
より高価なプリンタでは、計算の負担をホストプロセッサ１０４からプリンタプロセッサ１１０へと移行させることが可能であるので、バス１１４を介するデータ伝送のボトルネックを解消することができ、印刷ジョブの印刷速度が向上する。これは、より効率的なデータ表現を使用してバス１１４を介してページデータを送信することによって達成される。このような構成の一例では、走査線処理ステップ３１０は、印刷対象のデータの「表示リスト」表現を生成する。この表現はプレレンダリング済のビットマップ表現よりもデータの消費が少ない。これは表示リスト手法と呼ばれる。表示リスト手法では、印刷ステップ３１８で印刷するために、表示リストをビットマップへとレンダリングするレンダリングステップ３１４が必要である。場合によっては、表示リストを解釈し、ビットマップに画素を書き込むことなく直接印刷を実行するための画素を提供しても良い。
【０００８】
表示リストはグラフィックオブジェクトをエッジにより表す。このエッジは、直線ベクトル、２次線分などであっても良い。エッジは、エッジレコードにより表示リスト（エッジリストとも呼ばれる）に格納される。例えば、エッジレコードは以下の４つの要素を含んでも良い：
（ｉ）現在の走査線交差座標（Ｘ座標と呼ばれる）、
（ｉｉ）エッジの現在のセグメントがまたがる走査線の本数のカウント（実施例によってはＹ限界と呼ばれる）、
（ｉｉｉ）走査線を通過するごとにエッジレコードのＸ座標に加算される値（ＤＸと呼ばれる）、及び
（ｉｖ）エッジが上向き（＋）及び下向き（−）のいずれの向きで走査線と交差するのかを示す方向（ＤＩＲ）フラグ
表示リスト技術は、レンダリングの既知の順序（特定の走査線Ｙ上のエッジの画素位置Ｘにより判定）を使用して、オブジェクトが最終的に印刷用のビットマップ上にどのようにペイントされるべきかを画素ごとに判定する。ここで考察する例では、印刷されるオブジェクトは不透明である。複数のグラフィックオブジェクトが重なる場合、最後にペイントされたオブジェクトは完全に見えるが、それよりも前にペイントされたオブジェクトは隠れることになる。この動作方式は、一般的に、「painter's algorithm（画家のアルゴリズム）」と呼ばれるが、それは、全てのオブジェクトをペイントすると、最上部のオブジェクトのみが最終的に見える状態になるからである。多数のオブジェクトが同時にページ上に存在する場合、個々の画素が何度もビットメモリに書き込まれる可能性がある。繰り返し、メモリ帯域幅及び処理サイクル時間を消費すると共に、最終的に破棄されるデータを生成することになる。
【０００９】
表示リスト手法の一変形例では、ページ上の全てのオブジェクトに対して表示リストデータが格納される。しかし、各オブジェクトはレイヤ番号でタグ付けされるので、あるオブジェクトのページ上の他のオブジェクトに対する相対的な表示位置を判定することができる。表示リスト変形手法と呼ばれるこの技術は、以下に示すように、表示リスト中のエッジレコードに追加の（第５の）要素を加えることによって実現される：
（ｖ）１つ或はそれ以上の優先番号（Ｐ）（他のページオブジェクトのレイヤ位置に対しての考察中のエッジを有するオブジェクトのレイヤ位置を表す）
この場合、ステップ３１４でのレンダリング中に、プリンティングプロセッサ１１０は、各画素位置に対する画素値を出力する前に、その画素位置においてどのオブジェクトがページの最上部にあるかを評価しながら、ページを水平に走査する。レンダリングステップ３１４では、特定の画素位置における全てのアクティブなオブジェクトを検査し、ページの最上部にあるオブジェクトに対する画素のみを書き込むことによって画素を動的に生成する。従って、各画素位置における出力画素は一度だけ出力される。
【００１０】
表示リスト手法及び表示リスト変形手法の双方を実行するためには、走査線ごとの各オブジェクトに対して、アクティブなエッジのリストがプリンティングプロセッサ１１０により維持されなければならない。特定の画素位置においてペイントされるべきオブジェクトを決定する際には、考察中の走査線上にあるエッジを有するオブジェクトのみが検査される。
【００１１】
要約すると、従来のビットマップ手法は、ホストプロセッサ１０４に高い処理負担を負わせる。それにより、プリンタプロセッサ１１０への処理負担が減少し、結果的に比較的安価なプリンタの製造が可能になる。しかし、ビットマップ手法では、通信バス１１４において利用可能な帯域幅が制限されているために、通常、伝送ボトルネックが発生する。結果として、印刷スループットも低い。表示リスト手法では、プリンティングプロセッサ１１０に対する計算負担が非常に大きく、プリンタのコストも上昇するが、一般的に、印刷スループットにおける性能が高い。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明の目的は、既存の構成の１つ或はそれ以上の欠点をほぼ克服、あるいは、少なくとも改善することである。
【００１３】
ホストにおいて印刷対象の画像から複数の重なり合わないグラフィックオブジェクトを含む視覚的に同等の画像を生成することによって上述の問題に対処しようとする構成が開示される。この視覚的に同等の画像は、ホストと通信するプリンタにおいて重なり検出を実行することなく、プリンタにおいて走査線レンダリングを行なうことができるので、プリンタ側での処理負担が軽減される。
【００１４】
本発明の第１の態様によると、画像を印刷する方法において、
ホストにおいて印刷対象の画像から複数の重なり合わないグラフィックオブジェクトを含む視覚的に同等の画像の表示リスト表現を生成する工程と、
前記ホストと通信を行なうプリンタにおいて重なり検出を実行することなく、前記表示リスト表現を使用して前記プリンタにおいて前記視覚的に同等の画像に対して走査線レンダリングを行なう工程とを有する方法が提供される。
【００１５】
本発明の別の態様によると、第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する方法であって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類する工程と、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義する工程と、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義する工程とを有する方法が提供される。
【００１６】
本発明の別の態様によると、複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する方法であって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類する工程と、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義する工程と、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義する工程とを有する方法が提供される。
【００１７】
本発明の別の態様によると、第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する方法であって、
現在の走査線ごとに、
（ａ）現在の走査方向において前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定する工程と、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する工程と、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する工程と、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復する工程とを有し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成する方法が提供される。
【００１８】
本発明の別の態様によると、複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する方法であって、
現在の走査線ごとに、
（ａ）現在の走査方向において前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定する工程と、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する工程と、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する工程と、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復する工程とを有し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成する方法が提供される。
【００１９】
本発明の別の態様によると、画像を印刷する装置において、
ホストにおいて印刷対象の画像から複数の重なり合わないグラフィックオブジェクトを含む視覚的に同等の画像の表示リスト表現を生成する手段と、
前記ホストと通信を行なうプリンタにおいて重なり検出を実行することなく、前記表示リスト表現を使用して前記プリンタにおいて前記視覚的に同等の画像に対して走査線レンダリングを行なう手段とを具備する装置が提供される。
【００２０】
本発明の別の態様によると、第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する装置であって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類する手段と、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義する手段と、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義する手段とを具備する装置が提供される。
【００２１】
本発明の別の態様によると、複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する装置であって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類する手段と、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義する手段と、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義する手段とを具備する装置が提供される。
【００２２】
本発明の別の態様によると、第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する装置であって、
（ａ）現在の走査方向において前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定する手段と、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する手段と、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する手段と、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復する手段とを有し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成する装置が提供される。
【００２３】
本発明の別の態様によると、複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する装置であって、
（ａ）現在の走査方向において前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定する手段と、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する手段と、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義する手段と、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復する手段とを有し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成する装置が提供される。
【００２４】
本発明の別の態様によると、第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する方法を実行するようにプロセッサに指示するコンピュータプログラムであって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類するコードと、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義するコードと、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義するコードとを具備するコンピュータプログラムが提供される。
【００２５】
本発明の別の態様によると、複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと変換する方法を実行するようにプロセッサに指示するコンピュータプログラムであって、
（ａ）前記第１の組の各グラフィックオブジェクトを（ｉ）完全に見えるグラフィックオブジェクト、（ｉｉ）部分的に見えるグラフィックオブジェクト、及び（ｉｉｉ）見えないグラフィックオブジェクトのうちのいずれか１つとして分類するコードと、
（ｂ）前記第１の組の前記完全に見えるグラフィックオブジェクトの各々に関して、前記第２の組においてほぼ同一のグラフィックオブジェクトを定義するコードと、
（ｃ）前記第１の組の前記部分的に見えるグラフィックオブジェクトの各々の可視領域に関して、前記第２の組において前記部分的に見えるグラフィックオブジェクトと視覚的に同等の１つ或はそれ以上のグラフィックオブジェクトを定義するコードとを具備するコンピュータプログラムが提供される。
【００２６】
本発明の別の態様によると、第１の組の重なり合うグラフィックオブジェクトを有する第１の画像の表現を第２の組の重なり合わないグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する方法を実行するようにプロセッサに指示するコンピュータプログラムであって、
現在の走査線に関して、
（ａ）現在の走査方向において前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定するコードと、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義するコードと、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義するコードと、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復するコードとを具備し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成するコンピュータプログラムが提供される。
【００２７】
本発明の別の態様によると、複数の層にまたがる第１の組のグラフィックオブジェクトを有する第１の画像の表現を単一の層上に第２の組のグラフィックオブジェクトを有する視覚的に同等の第２の画像の表示リスト表現へと走査線ごとに変換する方法を実行するようにプロセッサに指示するコンピュータプログラムであって、
現在の走査線に関して、
（ａ）現在の走査方向において前記第１の組の前記グラフィックオブジェクトのうちの第１のグラフィックオブジェクトの可視領域の先頭エッジ及び遅れエッジを判定するコードと、
（ｂ）（ｉ）前記第１のグラフィックオブジェクトが前記現在の走査方向に前記遅れエッジを越えて延出し、（ｉｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義するコードと、
（ｃ）（ｉ）前記グラフィックオブジェクトのうちの次のグラフィックオブジェクトが前記現在の走査方向と反対の方向に前記遅れエッジを越えて延出し、（ｉｉ）前記次のグラフィックオブジェクトが前記現在の走査方向の前記遅れエッジを越えた直後の位置で見える場合、前記遅れエッジを前記次のグラフィックオブジェクトの先頭エッジとして定義するコードと、
（ｄ）前記走査線上の全ての連続的な対の先頭エッジ及び遅れエッジに対して前記工程（ａ）から（ｃ）を反復するコードとを具備し、
前記対の先頭エッジ及び遅れエッジは、前記現在の走査線に対して前記第２の組の視覚的に同等のグラフィックオブジェクトを作成するコンピュータプログラムが提供される。
【００２８】
本発明のその他の態様も開示される。
【発明を実施するための最良の形態】
【００２９】
添付のいずれか１つ或はそれ以上の図面において、同じ符号を有するステップ及び／又は特徴に言及する場合、特に明記されていない限り、以下の記述においては、これらのステップ及び／又は特徴は、同じ機能又は動作を有するものとする。
【００３０】
本実施の形態では、ホストプロセッサ１０４により実行される走査線処理ステップ３１０が、通信バス１１４を介してプリンタプロセッサ１１０へと送信される簡易なグラフィックオブジェクト表示リスト表現を生成する新規のレンダリングアーキテクチャを開示する。この簡易なオブジェクト表現は、ステップ３０６により生成されたオブジェクト表現を同等の重なり合わない非自己交差のオブジェクト表現へと変換することに基づくものであるが、ステップ３１４において比較的安価なプリンティングプロセッサ１１０によりレンダリングを実行するのに適している。ここで開示される手法によれば、通信バス１１４を介して伝送されるデータは、ビットマップ手法よりも少なくて良く、プリンタプロセッサ１１０は先に説明した表示リスト手法で要求される程に高性能である必要はない。新規のアーキテクチャを使用すれば、プリンタは従来の表示リスト構成よりも低いコストで従来のビットマップ手法よりも大幅に高い印刷スループットを提供することができる。開示される新規のアーキテクチャでは、ホストプロセッサ１０４のことをＰＣプリプロセッサ（ＰＣＰ）と呼ぶ。一方、プリンタ１０８のプリンタプロセッサ１１０は組込み型レンダリングプロセッサ（ＥＲＰ）と呼ばれる。
【００３１】
開示される新規のアーキテクチャは、ホストプロセッサ１０４で「完全な」表示リストを生成し、この完全な表示リストをプリンタへと送信する従来の表示リスト手法と比較して非常に有利である。従来の表示リスト手法では、画素の値を決定する際に、プリンタプロセッサ１１０は特定の走査線Ｙ上の画素位置Ｘにおいて、全てのアクティブなオブジェクトの全てのエッジを考察しなければならない。画素位置Ｘでは、任意の数のオブジェクトがアクティブであるので、従来の表示リスト手法においてプリンタプロセッサ１１０が必要とする計算は、印刷されるページ上にオブジェクトが追加される度に、それに比例して増加する。従って、従来の表示リストプリンタの設計者は、潜在的な処理負担を負いながらも適切に実行することが可能なプリンタプロセッサ１１０を選択しなければならない。新規のアーキテクチャは、プリンタプロセッサ１１０の負担を軽減する。プリンタプロセッサ１１０は、印刷対象のジョブ中のプリントデータと同等であるが、同等の重なり合わない非自己交差のオブジェクト表現として表される「フラットな」オブジェクト表現を考察するだけでよい。新規のアーキテクチャは、高性能なホスト１０２と「弱い」スレーブ１０８との間で効率的で簡潔な表現を利用することで、印刷ジョブのレンダリングを両者間で分配する。
【００３２】
図３は、新規の印刷アーキテクチャが汎用コンピュータシステム２００を使用して好適に実施される方法を示す。図３に示すように、システム２００は、ホスト１０２、ホストプロセッサ（ＰＣＰ）１０４、プリンタ１０８、及びプリントプロセッサ（ＥＲＰ）１１０を含む。図２及び図７から図１１の各プロセスは、コンピュータシステム２００内で実行されるアプリケーションプログラムなどのソフトウェアとして実現されても良い。特に、印刷方法の各ステップは、システムにより実行されるソフトウェア中の命令により実施される。命令は、各々が１つ或はそれ以上の特定のタスクを実行する１つ或はそれ以上のコードモジュールとして形成されても良い。ソフトウェアは、機能的に２つのコード部分に分割されても良い。第１のコード部分は印刷方法の各ステップを実行し、第２の部分は第１の部分とユーザとの間のユーザインタフェースを管理する。ソフトウェアは、ホスト１０２に格納されて処理される部分と、プリンタ１０８に格納されて処理される部分との２つの物理的な部分に分割することもできる。ソフトウェアの物理的な分割は、機能的な分割とほぼ無関係に実行することができる。ソフトウェアは、例えば、後述の記憶装置を含むコンピュータ可読な媒体に格納されても良い。ソフトウェアは、コンピュータ可読な媒体からシステムへとロードされ、システム２００により実行される。このようなソフトウェア又はコンピュータプログラムを記録したコンピュータ可読な媒体は、コンピュータプログラム製品である。このようなコンピュータプログラム製品をシステム２００で使用することにより、新規の印刷アーキテクチャを実現するのに有利な装置を実現するのが好ましい。
【００３３】
コンピュータシステム２００は、ホストコンピュータモジュール１０２、キーボード２０２及びマウス２０３などの入力装置、プリンタ１０８（ＥＲＰ１１０、メモリ２２６、及びプリンタエンジン２２２を含む）を含む出力装置、及び表示装置２１４を具備する。プリンタ１０８は、通信バス１１４によりホストコンピュータ１０２に接続される。ホストコンピュータモジュール１０２は、変復調（モデム）送受信装置２１６を使用して、例えば、電話回線２２１又はその他の機能媒体を介して接続可能な通信ネットワーク２２０との送受信を行なう。このモデム２１６は、インターネット及び構内通信網（ＬＡＮ）又は広域通信網（ＷＡＮ）などのその他のネットワークシステムへのアクセス権を取得するのに使用することができる。
【００３４】
ホストコンピュータモジュール１０２は、通常、少なくとも１つのプロセッサユニット（ＰＣＰ１０４）、例えば、半導体ランダムアクセスメモリ（ＲＡＭ）及び読出し専用メモリ（ＲＯＭ）から形成されるメモリユニット２０６、ビデオインタフェース２０７とキーボード２０２、マウス２０３、及びオプションとしてのジョイスティック（不図示）用のＩ／Ｏインタフェース２１３とを含む入出力（Ｉ／Ｏ）インタフェース、並びにモデム２１６用のインタフェース２０８を含む。記憶装置２０９が設けられるが、この記憶装置２０９は、通常、ハードディスクドライブ２１０及びフロッピーディスクドライブ２１１を含む。磁気テープドライブ（不図示）を使用しても良い。ＣＤ−ＲＯＭドライブ２１２は、通常、不揮発性のデータソースとして設けられる。ホストコンピュータモジュール１０２の構成要素１０４及び２０６から２１３は、通常、相互接続バス２０４を介して、ホストコンピュータシステム１０２の動作モードが、当業者には既知の従来の動作モードになるように通信を行なう。上述の構成が実施されるコンピュータの例としては、ＩＢＭ−ＰＣ及びその互換機、Sun Sparcstation、又はそれを進化させた同様のコンピュータシステムがある。
【００３５】
通常、アプリケーションプログラムは（ｉ）ハードディスクドライブ２１０に常駐し、ＰＣＰ１０４による実行の際に読み出されて制御される。また、（ｉｉ）プリンタメモリ２２６に常駐し、ＥＲＰ１１０による実行の際に読み出されて制御される。プログラムと、ネットワーク２２０から取り込まれるデータとの中間記憶装置は、半導体メモリ２０６を使用し、場合によってはハードディスクドライブ２１０及びプリンタメモリ２２６と協働させるように使用して達成されても良い。アプリケーションプログラムは、ＣＤ−ＲＯＭ又はフロッピーディスク上に符号化された形でユーザに供給され、対応するドライブ２１２又は２１１を介して読み取られる場合もあれば、ネットワーク２２０からモデム装置２１６を介してユーザが読み取る場合もある。更に、このソフトウェアは、他のコンピュータ可読な媒体からコンピュータシステム２００へとロードすることもできる。ここで使用する用語「コンピュータ可読な媒体」は、コンピュータシステム２００に実行及び／又は処理させる命令及び／又はデータの供給に関係する任意の記憶媒体／伝送媒体を指す。記憶媒体の例としては、フロッピーディスク、磁気テープ、ＣＤ−ＲＯＭ、ハードディスクドライブ、ＲＯＭ又は集積回路、光磁気ディスク、又はＰＣＭＣＩＡカードなどのコンピュータ可読なカードがある。これらの媒体がホストコンピュータモジュール１０２の内部にあるか、或は、外部にあるかは関係がない。伝送媒体の例としては、無線又は赤外線の伝送チャネル、別のコンピュータ又はネットワーク化装置とのネットワーク接続、並びに電子メール送受信及びウェブサイトなどに記録された情報などを含むインターネット又はイントラネットがある。
【００３６】
新規の印刷アーキテクチャは、このアーキテクチャに従って印刷する関数又は下位関数を実行する１つ或はそれ以上の集積回路などの専用ハードウェアにおいて実現されても良い。このような専用ハードウェアには、グラフィックプロセッサ、デジタル信号プロセッサ、又は１つ或はそれ以上のマイクロプロセッサ及び関連メモリが含まれても良い。
【００３７】
ＰＣＰ１０４は、ステップ３１０において、ページ上にペイントされるオブジェクトの表示リスト表現を生成する。ＰＣＰにより提供される表示リスト表現は、従来の表示リストプリンタにより提供される完全な表示リストとは対照的に、重なりを考慮せずに出力ページへとペイントされる１組の同等に印刷可能な重なり合わないオブジェクトと関連がある。図４及び図５は、従来のオブジェクト表現とフラットなオブジェクト表現とが同等であることを示す。
【００３８】
図４は、１対の相互に垂直な軸６１８及び６２０を基準として配置される２つのひし形６１４及び６１６を示す。ひし形６１４は、破線のセグメント６１０及び６１２により示されるように、ひし形６１６と部分的に重なり合う。
【００３９】
図５は、同等のひし形６１４’及び６１６’を示す。図５では、重なり合う線分６１０及び６１２は表現から削除されている。図５は、ひし形６１４のエッジ６０４（図４参照）がどのように維持されたかを示し、符号６０４’により描かれている。しかし、エッジ６０４に沿ってひし形６１４とひし形６１６との交差があることを示すために、「新規の」エッジ１１０６が生成されている。同様に、エッジ６２２に沿ってひし形６１４とひし形６１６との交差があることを示すために、新規のエッジ１１０８が生成されている。
【００４０】
図５は、それぞれエッジ６０４及び６２２に沿ってひし形６１４とひし形６１６の交差が存在することを示すために、追加のエッジ１１０６及び１１０８が生成されている構成を示す。エッジセグメント１１１０及び１１１２は、（ｉ）ひし形６１４’のエッジ及び（ｉｉ）ひし形６１６’として機能する２重の目的を達成することができる。実際に図９から図１１を参照して詳細に説明されるのは後者である。重なり合うオブジェクトを同等の重なり合わないオブジェクトとして表すために２つの例示の手法のみを説明したが、重なり合う表現から重なり合わない同等の表現への同様の変換を達成するその他の手法を使用しても良い。
【００４１】
新規に開示される印刷アーキテクチャは、方法ステップ３１０でＰＣＰ１０４において同等の重なり合わないオブジェクト表現を生成し、この重なり合わない表現は通信バス１１４を介してＥＲＰ１１０へと渡される。これは、ステップ３１４においてＥＲＰ１１０により更なる処理を施すためである。ＥＲＰ１１０によれば、重なり合わないオブジェクト表現は、従来の表示リスト手法で必要とされるよりも大幅に低い計算能力でもレンダリングすることができる。ＥＲＰは各画素位置において個々のオブジェクトを処理するだけで良いからである。この重なり合わないオブジェクト表現は、各画素位置の複数のオブジェクトを単一のオブジェクトに置換することにより、処理を画素ごとの既知の最大処理負担に制限する。従って、最悪の場合の計算負担を予め計算することができ、製造対象の特定のプリンタ１０８のＥＲＰ１１０として特定のプロセッサ装置を選択するのに使用することができる。
【００４２】
広い意味において、ＰＣＰ１０４による処理には、特定の走査線Ｙ上のグラフィックオブジェクトのエッジを追跡することが含まれる。ある画素位置Ｘに対して出力される画素値を決定するための決定工程において、ＰＣＰは印刷ジョブからの既存のオブジェクトのエッジ又は新規に合成されたエッジを出力する。新規に合成されたエッジは、図４及び図５を参照して説明してきたように、重なり合うオブジェクト間のエッジ交差において生成される。図５において例証される手法が採用される場合、例えば、エッジセグメント１１０６及び１１０８により例証されるように、新規のエッジが生成される。一方、エッジセグメント１１１０がオブジェクト６１４’に対するエッジセグメント及びオブジェクト６１６’に対するエッジセグメントとして機能する手法が採用される場合、新規に合成されたエッジは、実際には、エッジセグメントが２重の目的を達成することを示すエッジセグメント１１１０にタグ付けされる標識により表される。
【００４３】
元の印刷ジョブが重なり合う及び／又は自己交差のオブジェクトを含むか否かに関わらず、ＰＣＰ１０４は重なり合う及び／又は自己交差のオブジェクトを同等に表す複数の非交差オブジェクトを生成する。この手法には、複数の重なり合わない／非自己交差のオブジェクトを含む印刷ジョブをＥＲＰ１１０に提供するという顕著な効果がある。これにより、ＥＲＰ１１０に対する処理負担が軽減され、ＥＲＰ１１０に対する最大処理負担の包絡線が定義される。
【００４４】
全てのＥＲＰオブジェクトが重なり合わない非自己交差であることは、ＥＲＰジョブ（エッジリストにより表される）におけるオブジェクトの順序が、最初は「Ｙ」位置で固定され、続いて、「Ｘ」走査線順で固定されることを意味する。エッジリスト中の各エッジを再配列する必要はない。これは、複数の重なり合う及び／又は交差のエッジの考察中にエッジリストの再配列が必要である従来の表示リスト手法とは対照的である。
【００４５】
開示される印刷アーキテクチャは複数のエッジリストを利用する。このエッジリストについては図８から図１１を参照して詳細に説明する。しかし、導入の背景としては、元の印刷ジョブにおいてオブジェクト表現を表すのに「入力」又はＰＣＰエッジリストが使用されることに留意すべきである。「アクティブ」エッジリストは現在の走査線に対するエッジを追跡するものであり、「出力」又はＥＲＰエッジリストは、プリンタＥＲＰ１１２による処理及び後続の印刷のためにバス１１４を介してホスト１０２からプリンタ１０８へと送信されるエッジリストである。
【００４６】
図６は、従来の表示リスト構成及び開示される非交差オブジェクトエッジリスト手法の双方において、図４及び図５の走査線３９から４１に対するアクティブエッジリストの内容を示す。エッジ６０２’、６０４’、６０６’、及び６０８’が、図６の最上部の走査線４１から３９と交差するのが描かれている。従来の表示リスト構成に対するアクティブエッジリスト９１２は、走査線４１の場合の走査線識別子９０２及び前述のエッジに対するエッジデータ９０４から９１０を含む。従って、データブロック９０４は、エッジ６０２’と関連付けられるオブジェクトが最上部の（即ち、見える）オブジェクトであることを示す優先情報「Ｐ＝１」を含む。データブロック９０４中の矢印セグメントは、エッジ６０２’の向きに対応する位置に向けられている。隣接するデータブロック９０６はエッジ６０４’に対応し、適切な優先情報及びエッジ向き情報を含む。同様に、データブロック９０８及び９１０は、オブジェクト６１６’がオブジェクト６１４の１つ下のレベルであることを示す優先レベル「Ｐ＝２」を含む。
【００４７】
同様に従来の表示リスト構成で参照されるアクティブエッジリスト９１２’は、走査線３９の場合のエッジ６０２’から６０８’に対応するデータブロック９１４から９２２を含む。データブロック９１８がエッジセグメント６０６’を表し、データブロック９２０がエッジセグメント６０４’を表すように、アクティブエッジリスト９１２’が、再配列されたことは明らかであろう。この再配列は、エッジ６０４’及び６０６’が走査線４１と走査線３９との間で交差する事実を示すのに必要である。再配列を要することが従来の表示リスト手法の特徴であり、プリンタプロセス１１０に相当の計算負担を負わせることにつながる特徴の１つである。
【００４８】
対照的に、開示される重なり合わないオブジェクト手法で使用されるアクティブエッジリスト９１２''は、走査線３９の場合の重なり合わないオブジェクト６１４’及び６１６’に対応する。従って、データブロック９２８及び９３４が、優先フラグは別として前述のアクティブエッジリスト９１２及び９１２’中のデータブロックを反映する一方で、データブロック９３０及び９３２は図５のエッジ１１１０及び１１０６を表す。アクティブエッジリスト９１２''が、幾つかの点において前のアクティブエッジリストとは異なることは明らかであろう。まず、各データブロックにおいて優先レベル「Ｐ＝１」が示されているが、全てのオブジェクトは同じレベルにあるので、この優先フラグは実際のところ冗長である。更に、エッジが消されるときにはアクティブエッジリストから削除され、新規のエッジがアクティブリストの正しい「Ｘ」位置に挿入されるだけであるので、アクティブエッジリストのデータブロックを再配列する必要はない。アクティブなエッジの１ページ当たりの最大数は固定されており、最大の場合には走査線上の画素数に近づけることができる。
【００４９】
ＰＣＰ１０４の走査線がステップ３１０で印刷するページを変換するときには、生成される出力は、通信バス１１４を介してＥＲＰ１１０に送信される、重なり合わない／非交差のＥＲＰオブジェクト（即ち、出力ＥＲＰエッジリスト）の表示リストへと蓄積される。
【００５０】
図７は、オブジェクト６１４及び６１６により例証される重なり合うオブジェクトをオブジェクト６１４’及び６１６’により例証される同等の重なり合わないオブジェクトへと変換するプロセス７００を示す。このプロセス７００はステップ７０２で開始される。ステップ７０２は、現在の画素位置が考察中（任意の走査線に対して）であることを示す。その後、検査ステップ７０４で現在の画素位置にアクティブなエッジが存在するか否かを判定する。アクティブなエッジが存在しない場合、プロセス７００は「ＮＯ」の矢印に従ってステップ７０６へと進む。ステップ７０６では画素位置を増分し、プロセスはステップ７０２へと戻る。
【００５１】
ステップ７０４においてアクティブなエッジが存在する場合、プロセス７００はステップ７１０へと進む。ステップ７１０では、このようなエッジのうちの最上部のエッジを判定する。続く検査ステップでは、検出された最上部のエッジが「アクティブなオブジェクト」以上のレベルであるか否かを検査する。（このアクティブなオブジェクトは、ステップ７３０において「実際の」オブジェクトを配置可能な最低限レベルであるデフォルトのレベルに設定されるか、或は、ステップ７２４及び７２０において実際のオブジェクトになるように設定される）。検出された最上部のエッジがアクティブなオブジェクトのレベル以上である場合、プロセス７００は「ＹＥＳ」の矢印に従って検査ステップ７１８へと進む。このステップでは、エッジが対応するオブジェクトの先頭エッジ（走査線４１上のエッジ６０２’など）であるか、或は、遅れエッジ（図６の走査線４１上のエッジ６０４’など）であるかを検査する。
【００５２】
エッジが開始エッジである場合、プロセス７００は「Ｃ」の矢印に従ってステップ７２４へと進む。ステップ７２４では、対応するオブジェクトがアクティブなオブジェクトとして定義される。エッジが終端エッジである場合、プロセス７００は「Ｔ」の矢印に従ってステップ７３０へと進む。ステップ７３０では、アクティブなオブジェクトを終了し、デフォルトのアクティブなオブジェクトを前述の最低レベルに設定する。
【００５３】
ステップ７２４において、検出された最上部の開始エッジをアクティブなエッジとして一度設定すると、プロセス７００は矢印に従ってステップ７２８へと進む。ステップ７２８では画素位置を増分し、プロセスは矢印７２２に沿ってステップ７０２へと戻る。
【００５４】
ステップ７３０では、検出されたエッジが終端ステップであったためにアクティブなオブジェクトが終了している。この後、プロセス７００は検査ステップ７３４へと進む。このステップでは、先に定義されたアクティブなオブジェクトの下方と、その上方とで走査方向で見えるように別のオブジェクトが突出しているか否かを検査する。そのような突出オブジェクトが存在する場合、プロセス７００は「ＹＥＳ」の矢印に従ってステップ７３８へと進む。ステップ７３８では、前述の終端エッジを、検出された突出オブジェクトの開始エッジとして定義する。これは、図５との関連で説明した方法の変形例として記述されている。続くステップ７２０では、「他の」突出オブジェクトをアクティブなオブジェクトとして定義し、プロセス７００は矢印７１６に従ってステップ７０６へと進む。
【００５５】
ステップ７３４において、前述の終端オブジェクトの下方から見えるように突出しているオブジェクトが他に存在しない場合、プロセス７００は「ＮＯ」の矢印に従ってステップ７０６へと進む。
【００５６】
開示される印刷アーキテクチャは、印刷ページ上のオブジェクト表現のレンダリングを主に目的とするが、ビットマップデータに関して追加の機能をサポートすることもできる。このため、走査変換中、ＰＣＰ１０４はエッジリストにより消費されるメモリを監視することができると共に、ページのビットマップ表現を生成することができる。通常の動作中は、このビットマップ表現は破棄されるであろう。しかし、ＥＲＰ（出力）エッジリスト（即ち、重なり合わない／非自己交差のオブジェクト表現）が同等のビットマップよりも大きいことをＰＣＰ１０４が検出する場合（単一の画素オブジェクトが多数存在する場合などに起こり得る）、ＰＣＰ１０４は、その生成されたビットマップ表現をＥＲＰ１１０用の表示リストの代わりに利用することができる。また、ＰＣＰ１０４はＥＲＰオブジェクト表現により使用されるメモリの量を容易に計算することができ、ＥＲＰ表現が代替表現を必要とする程に大きいか否かを検証した後にビットマップの生成を決定することができる。この最後のステップは、ＥＲＰ表示リストを解釈し、それを破棄することによって実行される。
【００５７】
従って、上述の要素によって、ＥＲＰ表現及びビットマップのいずれかをプリントエンジン２２２へと送信することができる。
【００５８】
別の構成では、ＰＣＰ１０４はバンドで印刷されるページをレンダリングすることができる。この場合、ＥＲＰオブジェクトは固定の垂直なバンドサイズで生成される。この構成では、ＥＲＰオブジェクト及び同等のビットマップのいずれをプリントエンジン２２２に送信すべきかに関する決定はバンドごとに行なうことができる。
【００５９】
図４に示す重なり合うひし形６１４及び６１６は、以下のAdobe社のポストスクリプト記述（記述［１］と呼ばれる）により表すことができる：
/DeviceRGB setcolorspace
255 255 0 setcolor
30 10 moveto
50 30 lineto
30 50 lineto                                      …[1]
10 30 lineto
closepath
fill
255 0 255 setcolor
50 10 moveto
70 30 lineto
50 50 lineto
30 30 lineto
closepath
fill
showpage
このAdobe社のポストスクリプト記述は、図２のステップ３０６で実行されるように、既知の方法（Foley、Van Dam、Feiner、及びHughesの「Computer Graphics Principles and Practice」（Addison-Wesley、ISBN 0-201-12110-7））により以下のオブジェクト表現（記述［２］と呼ばれる）へと変換することができる：
Setting Color:"Color"＜red＞,＜green＞,＜blue＞
Filled Polygon:"FillPoly"＜x,y＞[,＜x,y＞]';'                …[2]
|Color:255,255,0|FillPoly:30,10,50,30,30,50,10,30,30,10;|
|Color:255,0,255|FillPoly:50,10,70,30,50,50,30,30,50,10;|
上述のオブジェクト表現［２］は、図２のステップ３１０の走査線プロセス用の入力（ＰＣＰ）エッジリストを表す。
【００６０】
図８は、ＰＣＰ１０４及びＥＲＰ１１０が使用するエッジリストの生成、更新、及び使用に関するデータフロー図を示す。印刷する入力ページは、ブロック１００２において表される。このページは、ステップ３０６で入力エッジリスト１００６（ＰＣＰエッジリスト［１］により例証される）へと変換される。入力エッジリストは走査線ごとに処理され、走査線ごとのアクティブエッジリスト１０１０が提供される。このアクティブエッジリスト１０１０は更新プロセス１０１４で更新される。アクティブエッジリスト更新プロセス１０１４は、それぞれ矢印１０１２及び破線の矢印１０１８により示されるアクティブエッジリスト自体１０１０及び入力エッジリスト１０１６の双方を利用する。アクティブエッジリストはエッジプロセス１０２２でも処理される。エッジプロセス１０２２では、出力エッジリスト１０２６（後述のＥＲＰエッジリスト［３］により例証される）を生成する。出力エッジリストは出力エッジリスト更新プロセス１０３０で更新される。出力エッジリスト更新プロセス１０３０では、矢印１０２８により示される出力エッジリスト１０２６及び破線の矢印１０３２により示されるアクティブエッジリスト１０１０の双方を利用する。
【００６１】
例示の入力（ＰＣＰ）エッジリスト［２］から得られる出力（ＥＲＰ）エッジリスト［３］は以下の形態をとる。この形態は重なり合わない非交差のエッジとしてオブジェクト６１４’及び６１６’を表す：
Setting Color:"Color"＜red＞,＜green＞,＜blue＞
Polygon Edge:"Edge"＜x,starting-y,ending-y,gradient＞
|Color:255,255,0|Edge:30,50,30,-1|                    …[3]
|Color:255,255,255|Edge:30,50,40,1|
|Color:255,0,255|Edge:50,50,40,-1|
|Color:255,255,255|Edge:50,50,30,1|
|Color:255,0,255|Edge:40,40,30,1|
|Color:255,255,0|Edge:10,30,10,1|
|Color:255,0,255|Edge:50,30,20,-1|
|Color:255,255,255|Edge:70,30,10,-1|
|Color:255,255,255|Edge:40,20,10,-1|
|Color:255,0,255|Edge:40,20,10,1|
図９及び図１０は、２つのフローチャートの部分８００及び８００’から成るフローチャートを示す。これらの部分は、ＰＣＰ１０４が重なり合わないオブジェクトグラフィック記述（［２］により例証される入力エッジリストから得られる出力エッジリスト［３］により例証される）を生成するプロセスのための部分である。プロセス部分８００及び８００’は図２のプロセス３１０を詳細に示す。図９及び図１０に示すプロセスは、付録Ａにおいて擬似コード形式でも提示される。付録Ａは、ホストマシン１０２が関係する範囲、即ち、図２のプロセス３００の境界部３２０までの部分に関する。付録Ａは図２のステップ３０２、３０６、及び３１０に関する。
【００６２】
図９は、プロセス部分８００に関し、入力リスト［２］を読むステップ８０２（付録Ａの１７３行目から１７８行目参照）で開始される。ステップ８０６（付録Ａの１７３行目参照）は、以下のステップが現在の走査線に対して実行されることを示す。後続のステップ８１０（付録Ａの１７４行目から１７７行目参照）は、図６に例証されるアクティブリストを入力リスト［２］から作成する。続いて、ステップ８１４（付録Ａの１８６行目参照）では、アクティブリストを画素（Ｘ）順にソートする。ステップ８１８（付録Ａの１９８行目から３７８行目参照）は、以下のサブステップが現在の画素位置Ｘに対して実行されることを示す。
【００６３】
後続のステップ８２２（付録Ａの１９８行目から３７９行目参照）では、ステップ８１０（付録Ａの１７４行目から１７７行目参照）で作成されるアクティブリストを出力リストと比較する。続く検査ステップ８２６（付録Ａの２０６行目から２１６行目参照）では、出力リストの現在画素位置の出力エッジがアクティブリストの対応するアクティブエッジを有するか否かを決定する。アクティブエッジを有する場合、プロセス部分８００は、「ＹＥＳ」の矢印８３８に従って進む（図１０では矢印のセグメント８３８へと続く）。一方、検査ステップ８２６（付録Ａの２０６行目から２１６行目参照）で「ＮＯ」を返す場合、プロセス部分８００は、矢印８３０に従ってステップ８３２へと進む（付録Ａの２１４行目から２１５行目参照）。ステップ８３２では、考察が終了した出力エッジを終了する。後続のステップ８３６は、図２のステップ３１４で処理するために終了した出力エッジをプリンタ１１０へと送信する（破線の矢印３１２により示される）。矢印３１２により示される出力エッジ［３］は、レンダリングのためにプリンタへと送信される重なり合わないグラフィックオブジェクトを有する画像の（簡易な）表示リスト表現を構成する。この表示リスト表現は、入力リスト［２］により表される画像と視覚的に同等である。
【００６４】
図１０は、継続のプロセス部分８００’を示す。特に、ステップ８４４（付録Ａの２３９行目及び１１６行目から１３１行目参照）は、矢印のセグメント８３８から継続し、考察中のＸのためにアクティブリストにおいて最上部のエッジ（即ち、最高レベルのフラグを有するエッジ）を探し出す。後続の検査ステップ８４８（付録Ａの２９１行目及び３０５行目から３１２行目参照）では、アクティブリスト中の最上部のエッジが対応する出力エッジを有するか否かを判定する。実際に出力エッジを有する場合、プロセス部分８００’は、「ＹＥＳ」の矢印に従ってステップ８５８（付録Ａの１９５行目参照）へと進む。ステップ８５８では、考察中の画素位置（即ち、Ｘ）をチェックする。これに対し、検査ステップ８４８（付録Ａの２９１行目及び３０５行目から３１２行目参照）でアクティブリスト中の最上部のエッジが対応する出力（ＥＲＰ）エッジを有しないと判定する場合、プロセス部分８００’は「ＮＯ」の矢印に従ってステップ８５４（付録Ａの２９２行目から３００行目及び３１３行目から３７７行目参照）へと進む。ステップ８５４では、出力リストにおいて新規のエッジを作成する。図５のエッジ６０４’などの新規の既成のエッジ及びエッジセグメント１１０６又は２重目的のエッジセグメント１１１０などのオブジェクト交差のために得られる新規の合成エッジの双方を作成するのが、このステップ８５４（付録Ａの２９２行目から３００行目及び３１３行目から３７７行目参照）である。
【００６５】
プロセス部分８００’は検査ステップ８６２（付録Ａの１９５行目参照）へと進む。検査ステップ８６２では、現在の走査線が終了したか否かを判定する。走査線が終了していない場合、プロセス部分８００’は「ＮＯ」の矢印（即ち、８４０）に従って図９の矢印のセグメント８４０へと進み、ステップ８１８（付録Ａの１９８行目から３７８行目参照）へと戻る。これに対し、現在の走査線が終了している場合、プロセス部分８００’は「ＹＥＳ」の矢印に従ってステップ８６８（付録Ａの３８３行目）へと進む。ステップ８６８では走査線（Ｙ）を増分する。後続のステップ８７２（付録Ａの３８８行目から４１３行目参照）では、図６で例証されるアクティブリストを現在の走査線（Ｙ）と比較する。その後、検査ステップ８７６（付録Ａの３８９行目参照）では、不要となったアクティブなエッジが存在するか否かを判定する。実際に不要なアクティブなエッジが存在する場合、プロセス部分８００’は「ＹＥＳ」の矢印に従ってステップ８８０へと進む（付録Ａの３９０行目から４０６行目参照）。ステップ８８０では、このようなアクティブなエッジを削除する。これに対し、このように不要なアクティブなエッジが存在しない場合、プロセス部分８００’は「ＮＯ」の矢印に従って矢印のセグメント８４２を介して進み、図９の矢印のセグメント８４２へと戻ってステップ８０６へと到達する（付録Ａの１７３行目参照）。
【００６６】
図１１は、ＥＲＰプロセス３１４のフローチャート５００を示す。ＥＲＰプロセス３１４では、ＰＣＰから受信したＥＲＰオブジェクト表現を一連の画素へとレンダリングする。プロセス５００はステップ５０２で開始される。ステップ５０２では、ＰＣＰからオブジェクト記述を受信する（これらの記述は［３］により例証されるＥＲＰ出力エッジリストレコードである）。後続のステップ５０６では、第１の走査線に対してアクティブエッジリストを作成する。続くステップ５１０では、走査線オブジェクトを画素へと走査変換する。破線の矢印３１６により示されるように、これらの画素値は出力される。後続の検査ステップ５１４では、走査線上の全てのオブジェクトが終了したか否かを判定する。全てのオブジェクトが実際に終了した場合、プロセス５００は「ＹＥＳ」の矢印に従って終了ステップ５１８へと進む。これに対し、全てのオブジェクトが終了していない場合、「ＮＯ」の矢印に従ってステップ５２２へと進む。ステップ５２２では、次の走査線のためにアクティブなエッジを更新する。その後、ステップ５２６において、アクティブエッジリストから終了したエッジを削除し、続くステップ５３０で新規のアクティブなエッジをエッジリストへと挿入する。プロセス５００は矢印５３２に従ってステップ５１０へと進む。
【産業上の利用可能性】
【００６７】
以上の説明から、上述の各構成がデータ処理産業に適用可能であることは明らかである。
【００６８】
説明では、本発明の一実施例のみが記述されているが、本発明の趣旨から逸脱することなく変形及び／又は変更を行なうことができる。実施例は例示のものであり、それに限定すべきではない。このため、上述の方法は、例えば、ネットワークを介したオブジェクトベースのアニメーションなどの動的表示物用のグラフィック素材の伝送を含むように拡張することができる。更に、一様な不透明色を有するオブジェクトの観点から説明が行なわれているが、ＥＲＰが直線傾斜及び／又は１次変換により記述される色及び不透明度を有するビットマップを処理することが可能な場合には、種々の色及び不透明度を有するオブジェクトにも上述の方法を容易に適用することができる。
1    ［付録Ａ］
4  /*
5   *  単純な非合成の場合のＰＣＰエッジ／ＥＲＰエッジアルゴリズム
6   *  の擬似実現。出力ＥＲＰリストはソート要
7   */
8   #include ＜stdlib.h＞
9   #include ＜memory.h＞
10  
11  typedef struct
12  {
13      unsigned char    r;
14      unsigned char    g;
15      unsigned char    b;
16   } rgb;
17
18   #define LEADING     1
19   #define LAGGING     0
20   /*
21    * pcp_edge - アルゴリズムに対するＰＣＰ入力エッジの表現
22   */
23   */
24   typedef struct pcp_edge
25   {
26     struct pcp_edge  *next;
27     double              current_x;
28     double              x_increment;
29     int                starting_y;
30     int                ending_y;
31     int                level_number;
32     rgb                color;
33     int                leading:1;
34    } pcp_edge;
35   /*
36    * erp_edge - アルゴリズムに対するＥＲＰ出力エッジの表現
37    */
38    */
39    typedef struct erp_edge
40    {
41      struct erp_edge      *next;
42      int                      starting_x;
43      int                      starting_y;
44      double                    current_x;
45      double                    x_increment;
46      int                      ending_y;
47      rgb                      color;
48    } erp_edge;
49    /*
50   * sort_pcp_edges_in_x
51   *    pcp_edgesのリストを正しい「ｘ」順にソートし、
52   *    次の走査線ステップに対してもソートを行なう
53   *
54   * 引数:
55   *    pcp_list   ソート対象リスト
56   *
57   * 戻り値:
58   *    ソート済のリストの先頭
59   */
60  static pcp_edge *
61  sort_pcp_edges_in_x
62  (
63      pcp_edge            *pcp_list
64  )
65  {
66      pcp_edge            *e;
67     /*
68      *ほぼ常時、リストはソートされることになるのでバブルソートで良い
69      */
70       */
71      for (;;) {
72          for
73          (
74              e = pcp_list;
75              e != NULL && e-＞next != NULL;
76              e = e-＞next) {
77              if
78              (
79                  e-＞next-＞current_x ＜ e-＞current_x
80                  ||
81                  (
82                      e-＞next-＞current_x == e-＞current_x
83                      &&
84                      e-＞next-＞x_increment ＜ e-＞x_increment
85                  )
86              ) {
87                  pcp_edge    t;
88                  pcp_edge    *np;
89
90                  t = *e-＞next;
91                  np = e-＞next;
92                  *e-＞next = *e;
93                  e-＞next-＞next = t.next;
94                  *e = t;
95                  e-＞next = np;       /* fix the list pointer */
96                  e = pcp_list;       /* force reloop         */
97                  break;
98              }
99          }
100         if (e == NULL || e-＞next == NULL)
101             break;
102     }
103     return pcp_list;
104  }
105  /*
106   * テーブルを使用してどのレベルがアクティブであるかをフラグで示す
107  */
108  #define MAX_LEVELS  32
109  pcp_edge    *level_is_active[MAX_LEVELS];
110  /*
111   *   最上部のアクティブなエッジを探し出す
112   *   最上部のアクティブなレンダリングオブジェクトを探し出す
113   *
114   * 最上部のオブジェクトの先頭エッジを戻す
115  */
116  pcp_edge *
117  find_top_active_edge()
118  {
119    int     i;
120 
121    for
122   (
123     i = sizeof level_is_active / sizeof level_is_active[0] - 1;
124     i ＞ 0 ;
125     i-
126    ) {
127      if (level_is_active[i] != NULL)
128        return level_is_active[i];
129    }
130   return NULL;
131  }
132  /*
133  * generate_erp_from_pcp
134   *    「malloc済の」ＰＣＰエッジのソート済リストを変換・解放し、
135   *    ＥＲＰエッジの連結リストを出力する
136   *
137   * 引数
138   *    in - ｙ順、ｘ順、及び傾斜度順にソートされた
139   *    ＰＣＰエッジの連結リスト
140   * x_per_scanline - 最終画像の「ｘ」次元における画素数
141   * y_per_page - 最終画像の「ｙ」次元における走査線数
142   *
143
144
145   * 戻り値：
146   *    ｅｒｐプリンタに送信するために符号化できる状態にある
147   *    ｅｒｐエッジの連結リスト
148   */
149  erp_edge *
150  generate_erp_from_pcp
151  (
152      pcp_edge      *in,
153      int         x_per_scanline,
154      int         y_per_page
155  )
156  {
157      pcp_edge    *active_pcp;
158      erp_edge    *out_list, **candidate_head;
159      int         current_y, current_x;
160      pcp_edge    *p_pcp, *processed_pcp, *top_active;
161      erp_edge    *p_erp, *pe;
162
163      out_list = NULL;
164      candidate_head = &out_list;
165      active_pcp = NULL;
166      current_y = 0;
167      /*
168      * アクティブリストを作成
169       */
170  build_active:
171      if (current_y ＞= y_per_page)
172       return out_list;
173      while (in != NULL && in-＞starting_y ＜= current_y) {
174          p_pcp = in;
175      in = in-＞next;
176      p_pcp-＞next = active_pcp;
177      active_pcp = p_pcp;
178      }
179     /*
180      * レベル活動化テーブルのクリア
181      */
182     memset(&level_is_active,0,sizeof level_is_active);
183     /*
184      * 理解可能な順にソート
185      */
186     active_pcp = sort_pcp_edges_in_x(active_pcp);
187     /*
188      * アクティブリストを調べてｅｒｐリストと比較し、
189      * 必要に応じてエッジを出力する
190      */
191      for
192      (
193          p_pcp = processed_pcp = active_pcp,
194              p_erp = *candidate_head;
195              p_pcp != NULL && current_x ＜ x_per_scanline;
196              p_pcp = p_pcp-＞next
197      ) {
198              pcp_edge      *p, *top;
199             int          toplevel, changed;
200
201          current_x = (int)p_pcp-＞current_x;
202           /*
203            * 次のアクティブなエッジの前にあるｅｒｐエッジは
204            * 全て終了させられる
205           /* 
206            for
207            (  ;
208               p_erp != NULL
209             &&
210             (p_pcp == NULL ||
211                 p_erp-＞current_x ＜ p_pcp-＞current_x);
212                   p_erp = p_erp-＞next
213                ) {
214              if (p_erp-＞ending_y == 0)
215                      p_erp-＞ending_y = current_y;
216         }
217          /*
218          * この「ｘ」位置に存在するオブジェクトに対する
219           * レベルを活動化（非活動化）する
220            */
221         for
222         (
223             changed = 0, p = processed_pcp;
224              p != NULL;
225              p = p-＞next
226          ) {
227              if (p-＞current_x ＞ current_x)   /* finished */
228                  break;
229              if (p-＞leading == LAGGING)
230                  level_is_active[p-＞level_number] = NULL;
231             else
232                  level_is_active[p-＞level_number] = p;
233            changed++;  /* count crossings at current_x */
234        }
235      /*
236       * このｐｃｐエッジを処理する前に
237       *最上部のアクティブレベルを取得する
238       */
239        top_active = find_top_active_edge();
240        /*
241         * １本以上のエッジと交差する場合、
242         * 全てのｅｒｐエッジをここで終了する
243         */
244         if (changed ＞ 1) {
245             for (p = processed_pcp; p != NULL; p = p-＞next) {
246                 if (p-＞current_x ＞ current_x)   /* finished */
247                    break;
248                  for (; p_erp != NULL; p_erp = p_erp-＞next)
249                     if (p_erp-＞current_x == current_x) {
250                          if (p_erp-＞ending_y == 0)
251                             p_erp-＞ending_y = current_y;
252                     }
253                      else
254                        goto done_terminating_erps;
255             }
256         }
257  done_terminating_erps:
258        /*
259         * このｘ位置で最上部のエッジを探し出し、
260         * ｅｒｐリストと照合する
261         */
262              top = NULL;
263              toplevel = 0;
264              for (p = processed_pcp; p != NULL; p = p-＞next) {
265                  if
266              (
267                  p-＞current_x == current_x
268                  &&
269                  p-＞level_number ＞ toplevel
270              ) {
271                  if
272                  (
273                    top_active == NULL ||
274                      p-＞level_number ＞=
275                          top_active-＞level_number) {
276                              top = p;
277                              toplevel = p-＞level_number;
278                      processed_pcp = top-＞next;
279                  }
280              }
281              }
282        /*
283         * 出力ｅｒｐエッジをチェックするための
284         * 入力ｐｃｐエッジを有する
285         */
286        if(top != NULL){
287        /*
288         * 最上部のｐｃｐエッジを有する。既存のｅｒｐエッジがあれば良いが、
289         * ない場合には生成する
290         */
291          if (out_list == NULL) {
292              p_erp = out_list = malloc(sizeof (erp_edge));
293              p_erp-＞next = NULL;
294              p_erp-＞starting_y = current_y;
295              p_erp-＞starting_x = current_x;
296          p_erp-＞current_x = (double)p_erp-＞starting_x;
297              p_erp-＞x_increment = top-＞x_increment;
298         p_erp-＞color = top-＞color;
299         p_erp-＞ending_y = 0;
300         candidate_head = &out_list;
301          }
302        /*
303         * 新規のエッジ作成をチェックする
304         */
305      else if
306     (
307        p_erp == NULL
308       ||
309        p_erp-＞current_x != top-＞current_x
310       ||
311        p_erp-＞x_increment != top-＞x_increment
312      ) {
313            erp_edge    *h, *prev;
314
315            h = malloc(sizeof (erp_edge));
316      if (p_erp == NULL) {
317         h-＞next = NULL;
318                goto insert_x_sorted_into_out_list;
319      }
320      else {
321        h-＞next = p_erp;
322        if (*candidate_head == NULL) {
323            h-＞next = NULL;
324            *candidate_head = h;
325        }
326       if (*candidate_head == p_erp) {
327           *candidate_head = h;
328        }
329        else {
330  insert_x_sorted_into_out_list:
331         for
332         (
333           prev = *candidate_head == NULL ?
334             out_list : *candidate_head;
335           prev != NULL;
336           prev = prev-＞next
337         ) {
338           if (prev-＞next == p_erp) {
339              if (prev-＞next != NULL) {
340               h-＞next = prev-＞next;
341                  prev-＞next = h;
342              }
343              else {
344                prev-＞next = h;
345              }
346              break;
347          }
348       }
349     }
350  }
351            h-＞starting_y = current_y;
352            h-＞starting_x = current_x;
353     h-＞current_x = (double)current_x;
354            h-＞x_increment = top-＞x_increment;
355    if
356    (
357      top-＞leading == LAGGING && top_active != NULL
358     &&
359     (
360       top-＞current_x ＞ top_active-＞current_x
361       ||
362        (
363          top-＞current_x ==
364           top_active-＞current_x
365          &&
366          top-＞x_increment ＞
367            top_active-＞x_increment
368       )
369    )
370  )
371     h-＞color = top_active-＞color;
372   else
373     h-＞color = top-＞color;
374   h-＞ending_y = 0;
375      p_erp = h;
376   }
377   p_erp = p_erp-＞next;
378    }
379   }
380  /*
381    * 現在の走査線を増分する
382    */
383    current_y++;
384    /*
385    * ２つのエッジリストを更新し、
386   * 新規のエッジの組込みに進む
387    */
388   for (p_pcp = active_pcp; p_pcp != NULL;) {
389       if (p_pcp-＞ending_y ＜= current_y) {
390          pcp_edge          *chuck, *prev;
391
392            chuck = p_pcp;
393       p_pcp = p_pcp-＞next;
394       if (active_pcp == chuck) {
395           active_pcp = p_pcp;
396       }
397       else {
398          for (prev = active_pcp; prev != NULL; prev = prev-＞next) {
399             if (prev-＞next == chuck) {
400                 prev-＞next = p_pcp;
401                 break;
402             }
403        }
404     }
405       free(chuck);
406       }
407     else {
408       p_pcp-＞current_x = p_pcp-＞current_x + p_pcp-＞x_increment;
409                p_pcp = p_pcp-＞next;
410           }
411   }
412   /*
413    * ｐｃｐアクティブリストが空である場合、全てのｅｒｐエッジを
414    * 終了させなければならない
415    */
416    if (active_pcp == NULL) {
417       for (pe = out_list; pe != NULL; pe = pe-＞next) {
418      if (pe-＞ending_y == 0)
419               pe-＞ending_y = current_y;
420       candidate_head = &pe-＞next;
421       }
422   }
423       /*
424       * ｅｒｐに関しても同様
425        */
426      for (pe = out_list; pe != NULL; pe = pe-＞next)
427          pe-＞current_x = pe-＞current_x + pe-＞x_increment;
428
429       goto build_active;
430   }
431
432   （付録Ａの終わり）
【図面の簡単な説明】
【００６９】
【図１】ＰＣベースの印刷システムの機能ブロック図である。
【図２】図１のシステムで使用される印刷プロセスのフローチャートである。
【図３】開示される構成を実施可能な汎用のコンピュータシステムを示す図である。
【図４】重なり合うグラフィックオブジェクトを例示する図である。
【図５】同等の重なり合わないグラフィックオブジェクトを示す図である。
【図６】従来の交差しないオブジェクト構成に対するアクティブエッジリストを示す図である。
【図７】重なり合うグラフィックオブジェクトを同等の重なり合わないグラフィックオブジェクトへと変換するプロセスを示すフローチャートである。
【図８】エッジリストの作成、更新、及び使用のためのデータフローを示す図である。
【図９】、
【図１０】ＰＣＰホストプロセッサにおいて重なり合わないグラフィックオブジェクトを作成するプロセスの部分的なフローチャートである。
【図１１】ＰＣＰから受信した重なり合わないオブジェクト表現をプリンタＥＲＰプロセッサにおける一連の画素へとレンダリングするプロセスのフローチャートである。
【図１】
2004152267.tif 000003
【図２】
2004152267.tif 000004
【図３】
2004152267.tif 000005
【図４】
2004152267.tif 000006
【図５】
2004152267.tif 000007
【図６】
2004152267.tif 000008
【図７】
2004152267.tif 000009
【図８】
2004152267.tif 000010
【図９】
2004152267.tif 000011
【図１０】
2004152267.tif 000012
【図１１】
2004152267.tif 000013
【外国語明細書】
2004152267.tif 000014
2004152267.tif 000015
2004152267.tif 000016
2004152267.tif 000017
2004152267.tif 000018
2004152267.tif 000019
2004152267.tif 000020
2004152267.tif 000021
2004152267.tif 000022
2004152267.tif 000023
2004152267.tif 000024
2004152267.tif 000025
2004152267.tif 000026
2004152267.tif 000027
2004152267.tif 000028
2004152267.tif 000029
2004152267.tif 000030
2004152267.tif 000031
2004152267.tif 000032
2004152267.tif 000033
2004152267.tif 000034
2004152267.tif 000035
2004152267.tif 000036
2004152267.tif 000037
2004152267.tif 000038
2004152267.tif 000039
2004152267.tif 000040
2004152267.tif 000041
2004152267.tif 000042
2004152267.tif 000043
2004152267.tif 000044
2004152267.tif 000045
2004152267.tif 000046
2004152267.tif 000047
2004152267.tif 000048
2004152267.tif 000049
2004152267.tif 000050
2004152267.tif 000051
2004152267.tif 000052
2004152267.tif 000053
2004152267.tif 000054
2004152267.tif 000055
2004152267.tif 000056
2004152267.tif 000057
2004152267.tif 000058
2004152267.tif 000059
2004152267.tif 000060
2004152267.tif 000061
2004152267.tif 000062
2004152267.tif 000063
2004152267.tif 000064
2004152267.tif 000065
2004152267.tif 000066
2004152267.tif 000067
2004152267.tif 000068
2004152267.tif 000069
2004152267.tif 000070
2004152267.tif 000071
2004152267.tif 000072