[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP2015075839A - Image processing apparatus, image processing method, and program - Google Patents

Image processing apparatus, image processing method, and program Download PDF

Info

Publication number
JP2015075839A
JP2015075839A JP2013210458A JP2013210458A JP2015075839A JP 2015075839 A JP2015075839 A JP 2015075839A JP 2013210458 A JP2013210458 A JP 2013210458A JP 2013210458 A JP2013210458 A JP 2013210458A JP 2015075839 A JP2015075839 A JP 2015075839A
Authority
JP
Japan
Prior art keywords
group
processing
edge
composite
groups
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP2013210458A
Other languages
Japanese (ja)
Inventor
盛一 伊藤
Morikazu Ito
盛一 伊藤
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Canon Inc
Original Assignee
Canon Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Canon Inc filed Critical Canon Inc
Priority to JP2013210458A priority Critical patent/JP2015075839A/en
Publication of JP2015075839A publication Critical patent/JP2015075839A/en
Pending legal-status Critical Current

Links

Images

Landscapes

  • Accessory Devices And Overall Control Thereof (AREA)
  • Image Generation (AREA)

Abstract

PROBLEM TO BE SOLVED: To provide an image processing apparatus configured to execute composite processing between groups at a high speed, to increase overall printing speed.SOLUTION: An image processing apparatus includes: means for interpreting a display list to load an object; means for determining whether the loaded object is non-transmissive and is located higher in order than an object already acquired; means for holding a group number of a group to which the loaded object belongs and coordinates of left and right edges of the object in a current scan line when the loaded object is non-transmissive and is located higher in order than the object already acquired; and means for skipping composite processing in a section indicated by the coordinates of the left and right edges when the composite processing is executed between groups which are lower in order than a group to which the current uppermost object belongs.

Description

本発明は、画像処理装置、画像処理方法、及びプログラムに関する、具体的には、本発明は、レンダリングにおけるピクセルのコンポジット処理を実行する画像処理装置、画像処理方法、及びプログラムに関する。   The present invention relates to an image processing device, an image processing method, and a program. Specifically, the present invention relates to an image processing device, an image processing method, and a program that execute pixel composite processing in rendering.

印刷データを主走査方向に1ライン毎に読み込んでレンダリングを行うスキャンラインレンダリングという方法がある(特許文献1参照)。スキャンラインレンダリングでは、ページ内に描画する画像オブジェクト(以下「オブジェクト」と称する)と、オブジェクトとの境目又はオブジェクトと、背景画像との境目を指すエッジに関する情報(エッジデータ)に従ってレンダリングを行う。特許文献1は、スキャンラインレンダリングを行うために、1ライン分のエッジデータをメモリにロードすることを開示する。   There is a method called scan line rendering in which print data is read for each line in the main scanning direction and rendered (see Patent Document 1). In scanline rendering, rendering is performed according to information (edge data) about an image object (hereinafter referred to as an “object”) to be drawn in a page and a boundary between the object or an edge indicating a boundary between the object and the background image. Patent Document 1 discloses loading edge data for one line into a memory in order to perform scan line rendering.

アプリケーションソフトウェアを用いたユーザによって作成される、レンダリング対象となる印刷データは、アプリケーションソフトウェアの描画能力向上に伴い、含まれるエッジ数が多く、複雑なものになってきている。そのため、レンダリングシステムのメモリリソースが不足することや、レンダリング処理に時間がかかること等が問題になっている。   The print data to be rendered created by the user using the application software has become complicated due to an increase in the number of edges included as the rendering performance of the application software increases. For this reason, there are problems such as a shortage of memory resources in the rendering system and a long time for rendering processing.

このような大量エッジを含む印刷データのレンダリング処理方法として、特許文献2は、処理を行うページ記述言語(PDL)データが含むオブジェクトをレベル毎にグループ化して複数のディスプレイリストを生成するフォールバックと呼ばれる処理を開示する。   As a rendering processing method for print data including a large amount of edges, Japanese Patent Application Laid-Open No. H10-228707 discloses a fallback method in which objects included in page description language (PDL) data to be processed are grouped for each level to generate a plurality of display lists. Disclosed process is called.

特開2000−137825号公報JP 2000-137825 A 特開2002−169668号公報JP 2002-169668 A

特許文献1が開示するスキャンラインレンダリング処理によって大量エッジを含む印刷データをレンダリングする際、特許文献2が開示するフォールバック処理を実行することで、限られたメモリリソースを用いてのディスプレイリストの生成が可能となる。   When print data including a large amount of edges is rendered by the scanline rendering process disclosed in Patent Document 1, a fallback process disclosed by Patent Document 2 is executed to generate a display list using limited memory resources. Is possible.

しかし、この方法では、生成したディスプレイリストにCPUキャッシュ内に格納できないだけのエッジが含まれる場合、CPUキャッシュのキャッシュミスヒットの頻発を引き起こし、これにより、レンダリング処理、特にエッジ処理に時間がかかることがある。   However, in this method, when the generated display list includes edges that cannot be stored in the CPU cache, it causes frequent occurrence of cache misses in the CPU cache, which takes time for rendering processing, particularly edge processing. There is.

本願発明は、ディスプレイリストに対するビットマップを生成してレンダリング処理を実行する画像処理装置であって、ディスプレイリストを解釈しオブジェクトをロードするロード手段と、当該ロードしたオブジェクトが不透過であり現在把握しているオブジェクトより上位であるか否か判定する判定手段と、前記ロードしたオブジェクトが不透過であり現在把握しているオブジェクトより上位である場合に、ロードしたオブジェクトの属するグループのグループナンバー及び現在処理中のスキャンラインにおける当該オブジェクトの左右のエッジの座標を保持する保持手段と、コンポジット処理がグループ間のコンポジット処理であり、現在把握している最上位のオブジェクトが属するグループより下位のグループ同士で実行される場合に、前記左右のエッジの座標で表される区間内でコンポジット処理をスキップするスキップ手段とを備えたことを特徴とする。   The present invention is an image processing apparatus that generates a bitmap for a display list and executes a rendering process. The image processing apparatus interprets the display list and loads an object, and the loaded object is opaque and currently grasped. A determination means for determining whether or not the loaded object is higher than the current object, and the group number of the group to which the loaded object belongs and the current process when the loaded object is opaque and higher than the currently known object The holding means that holds the coordinates of the left and right edges of the object in the middle scan line, and the composite process is a composite process between groups, and is executed between groups lower than the group to which the highest-level object currently grasped belongs When to , Characterized in that a skip means for skipping composite processed within a section indicated by the left and right edge coordinates.

本発明により、エッジ数が多い複雑なデータをレンダリング処理する場合であっても、グループ毎にエッジを処理することにより高速にエッジ処理を行うことが可能になる。また、本発明により、グループ間のコンポジット処理も高速に行うことが可能になり、トータルの印刷処理を高速に行うことが可能になる。   According to the present invention, even when complex data having a large number of edges is subjected to rendering processing, edge processing can be performed at high speed by processing edges for each group. Further, according to the present invention, it is possible to perform composite processing between groups at high speed, and it is possible to perform total printing processing at high speed.

実施例1に係る画像処理システムの構成を示すブロック図である。1 is a block diagram illustrating a configuration of an image processing system according to Embodiment 1. FIG. 実施例1に係るMFPの構成を示すブロック図である。1 is a block diagram illustrating a configuration of an MFP according to a first embodiment. 実施例1に係るスキャンラインレンダリング処理を示す図である。FIG. 6 is a diagram illustrating scan line rendering processing according to the first embodiment. 実施例1に係る大量エッジがディスプレイリストに含まれていた場合のエッジ処理を示す図である。It is a figure which shows the edge process when the mass edge which concerns on Example 1 is contained in the display list. 実施例1に係るエッジのグループ分割処理を示す図である。FIG. 10 is a diagram illustrating edge group division processing according to the first embodiment. 実施例1に係るグループ内のコンポジット処理と、グループ間のコンポジット処理とを示す図である。It is a figure which shows the composite process in the group which concerns on Example 1, and the composite process between groups. 実施例1に係るグループ間のコンポジットスキップ処理を示す図である。It is a figure which shows the composite skip process between the groups which concern on Example 1. FIG. 実施例1に係るグループ間のコンポジットスキップ処理を示すフローチャートである。7 is a flowchart illustrating composite skip processing between groups according to the first embodiment. 実施例2に係る複数の区間におけるグループ間のコンポジットスキップ処理を示す図である。It is a figure which shows the composite skip process between the groups in the some area which concerns on Example 2. FIG. 実施例2に係る複数の区間におけるグループ間のコンポジットスキップ処理を示すフローチャートである。12 is a flowchart illustrating composite skip processing between groups in a plurality of sections according to the second embodiment. 実施例3に係る最適オブジェクトの選択を伴うグループ間のコンポジットスキップ処理を示す図である。It is a figure which shows the composite skip process between groups with selection of the optimal object based on Example 3. FIG. 実施例3に係る最適オブジェクトの選択を伴うグループ間のコンポジットスキップ処理を示すフローチャートである。12 is a flowchart illustrating a composite skip process between groups with selection of an optimal object according to the third embodiment. 実施例4に係る矩形以外のオブジェクトのスパンにおけるグループ間のコンポジットスキップ処理を示す図である。It is a figure which shows the composite skip process between the groups in the span of objects other than the rectangle which concerns on Example 4. FIG. 実施例4に係る矩形以外のオブジェクトのスパンにおけるグループ間のコンポジットスキップ処理のフローチャートである。14 is a flowchart of composite skip processing between groups in a span of an object other than a rectangle according to the fourth embodiment. 実施例5に係る矩形以外のオブジェクトのスパンにおけるグループ間の簡易コンポジットスキップ処理を示す図である。It is a figure which shows the simple composite skip process between groups in the span of the objects other than the rectangle which concerns on Example 5. FIG. 実施例5に係る矩形以外のオブジェクトのスパンにおけるグループ間の簡易コンポジットスキップ処理のフローチャートである。16 is a flowchart of a simple composite skip process between groups in a span of an object other than a rectangle according to the fifth embodiment. 本発明に係るエッジのグループ分割処理と、先行技術との関連を示すフローチャートである。It is a flowchart which shows the relationship between the edge group division | segmentation process based on this invention, and a prior art.

以下、本発明の実施形態について図面を用いて説明する。   Hereinafter, embodiments of the present invention will be described with reference to the drawings.

<システム構成>
図1は、実施例1に係る画像処理システムの構成を示すブロック図である。このシステムでは、1台のホストコンピュータ(以下「PC」と称する)130と、2台の画像処理装置100、110とがLAN140に接続されている。ただし、本発明における画像処理システムにおいて、ホストコンピュータや画像処理装置の接続数がこれらに限られることはない。また、本実施例では接続手段としてLANを適用しているが、接続手段はこれに限られることはない。例えば、WAN(公衆回線)などの任意のネットワーク、USBなどのシリアル伝送方式、又はセントロニクスやSCSIなどのパラレル伝送方式なども適用可能である。
<System configuration>
FIG. 1 is a block diagram illustrating the configuration of the image processing system according to the first embodiment. In this system, one host computer (hereinafter referred to as “PC”) 130 and two image processing apparatuses 100 and 110 are connected to a LAN 140. However, in the image processing system according to the present invention, the number of connections of the host computer and the image processing apparatus is not limited to these. In this embodiment, the LAN is applied as the connection means, but the connection means is not limited to this. For example, an arbitrary network such as a WAN (public line), a serial transmission method such as USB, or a parallel transmission method such as Centronics or SCSI can be applied.

PC130は、パーソナルコンピュータの機能を有している。PC130は、LAN140やWANを介してFTPやSMBプロトコルを用いてファイルを送受信したり電子メールを送受信したりすることができる。さらに、PC130は、画像処理装置100、110に対して、プリンタドライバを介した印刷命令を行うことも可能となっている。   The PC 130 has a function of a personal computer. The PC 130 can send and receive files and send and receive e-mails using the FTP and SMB protocols via the LAN 140 and WAN. Further, the PC 130 can issue a print command to the image processing apparatuses 100 and 110 via a printer driver.

画像処理装置100及び画像処理装置110は同じ構成であり、ともにスキャナ部を有する画像処理装置である。以下では、説明の簡単のために、画像処理装置100、110のうちの画像処理装置110に注目して、その構成を詳細に説明する。   The image processing apparatus 100 and the image processing apparatus 110 have the same configuration, and both are image processing apparatuses having a scanner unit. For the sake of simplicity, the configuration will be described in detail below with a focus on the image processing apparatus 110 of the image processing apparatuses 100 and 110.

画像処理装置110は、画像入力デバイスであるスキャナ部113と、画像出力デバイスであるプリンタ部114と、画像処理装置110全体の動作制御を司るコントローラ111と、ユーザインターフェース(UI)である操作部112とから構成される。   The image processing apparatus 110 includes a scanner unit 113 that is an image input device, a printer unit 114 that is an image output device, a controller 111 that controls operation of the entire image processing apparatus 110, and an operation unit 112 that is a user interface (UI). It consists of.

<コントローラユニットの構成>
図2は、実施例1に係るMFP(Multifunction Peripheral)のコントロールユニット(コントローラ)の構成を示すブロック図である。図2は、図1におけるコントローラ101やコントローラ111の詳細な構成を示した図である。コントロールユニット200は、画像入力デバイスであるスキャナ部201や画像出力デバイスであるプリンタ部202と接続されており、画像データの読み取りやプリント出力のための制御を行う。また、コントロールユニット200は、LAN N1や公衆回線204と接続されており、画像情報やデバイス情報をLAN N1や公衆回線204経由で入出力するための制御を行う。プリンタ部202は、デバイスI/F217と接続されており、プリンタ部202が有するプリンタエンジンが、コントロールユニット200で生成された描画データを紙に出力する処理を行う。
<Configuration of controller unit>
FIG. 2 is a block diagram illustrating a configuration of a control unit (controller) of an MFP (Multifunction Peripheral) according to the first embodiment. FIG. 2 is a diagram showing a detailed configuration of the controller 101 and the controller 111 in FIG. The control unit 200 is connected to a scanner unit 201 that is an image input device and a printer unit 202 that is an image output device, and performs control for reading image data and printing output. The control unit 200 is connected to the LAN N1 and the public line 204, and performs control for inputting and outputting image information and device information via the LAN N1 and the public line 204. The printer unit 202 is connected to the device I / F 217, and the printer engine included in the printer unit 202 performs a process of outputting the drawing data generated by the control unit 200 to paper.

CPU205は、MFP全体を制御するための中央処理装置である。RAM206は、CPU205が動作するためのシステムワークメモリであり、入力された画像データを一時記憶するための画像メモリでもある。ROM207は、ブートROMであり、システムのブートプログラムを格納する。HDD208は、ハードディスクドライブであり、各種処理のためのシステムソフトウェア及び入力された画像データ等を格納する。操作部I/F209は、画像データ等を表示可能な表示画面を有する操作部210に対するインタフェース部であり、操作部210に対して操作画面データを出力する。また、操作部I/F209は、操作部210からユーザが入力した情報をCPU205に伝える役割をする。ネットワークI/F211は、例えばLANカード等で実現され、LAN N1と接続されて外部装置との間で情報の入出力を行う。モデム212は、公衆回線204と接続され、外部装置との間で情報の入出力を行う。CPU205、RAM206、ROM207、HDD208、操作部I/F209、ネットワークI/F211、及びモデム212がシステムバス213上で接続されている。   A CPU 205 is a central processing unit for controlling the entire MFP. A RAM 206 is a system work memory for the CPU 205 to operate, and is also an image memory for temporarily storing input image data. The ROM 207 is a boot ROM and stores a system boot program. The HDD 208 is a hard disk drive, and stores system software for various processes, input image data, and the like. The operation unit I / F 209 is an interface unit for the operation unit 210 having a display screen capable of displaying image data and the like, and outputs operation screen data to the operation unit 210. Also, the operation unit I / F 209 serves to transmit information input by the user from the operation unit 210 to the CPU 205. The network I / F 211 is realized by, for example, a LAN card or the like, and is connected to the LAN N1 to input / output information to / from an external device. A modem 212 is connected to the public line 204 and inputs / outputs information to / from an external device. A CPU 205, a RAM 206, a ROM 207, an HDD 208, an operation unit I / F 209, a network I / F 211, and a modem 212 are connected on a system bus 213.

イメージバスI/F214は、システムバス213と、画像データを高速で転送する画像バス215とを接続するためのインタフェースであり、データ構造を変換するバスブリッジである。画像バス215上には、ラスタイメージプロセッサ(RIP)216、デバイスI/F217、スキャナ画像処理部218、プリンタ画像処理部219、画像編集用画像処理部220、及びカラーマネージメントモジュール(CMM)230が接続される。   The image bus I / F 214 is an interface for connecting the system bus 213 and an image bus 215 that transfers image data at high speed, and is a bus bridge that converts a data structure. Connected to the image bus 215 are a raster image processor (RIP) 216, a device I / F 217, a scanner image processing unit 218, a printer image processing unit 219, an image editing image processing unit 220, and a color management module (CMM) 230. Is done.

RIP216は、ページ記述言語(PDL)データコードやベクトルデータをイメージに展開する。デバイスI/F217は、スキャナ部201やプリンタ部202と、コントロールユニット200とを接続するためのインタフェースであり、画像データの同期系/非同期系の変換を行う。スキャナ画像処理部218は、スキャナ部201から入力された画像データに対して、補正、加工、編集等の各種処理を行う。プリンタ画像処理部219は、プリント出力する画像データに対して、プリンタエンジンに応じた補正、解像度変換等の処理を行う。画像編集用画像処理部220は、画像データの回転や、画像データの圧縮伸長処理等の各種画像処理を行う。CMM230は、画像データに対して、プロファイルやキャリブレーションデータに基づいた、色変換処理(色空間変換処理ともいう)を施す専用ハードウェアモジュールである。プロファイルとは、機器に依存した色空間で表現したカラー画像データを機器に依存しない色空間(例えばLab等)に変換するための関数のような情報である。キャリブレーションデータとは、画像処理装置におけるスキャナ部201やプリンタ部202の色再現特性を修正するためのデータである。   The RIP 216 expands a page description language (PDL) data code and vector data into an image. The device I / F 217 is an interface for connecting the scanner unit 201 or printer unit 202 to the control unit 200, and performs synchronous / asynchronous conversion of image data. The scanner image processing unit 218 performs various processes such as correction, processing, and editing on the image data input from the scanner unit 201. The printer image processing unit 219 performs processing such as correction and resolution conversion according to the printer engine on the image data to be printed out. The image editing image processing unit 220 performs various types of image processing such as image data rotation and image data compression / decompression processing. The CMM 230 is a dedicated hardware module that performs color conversion processing (also referred to as color space conversion processing) on image data based on a profile and calibration data. A profile is information such as a function for converting color image data expressed in a device-dependent color space into a device-independent color space (eg, Lab). The calibration data is data for correcting the color reproduction characteristics of the scanner unit 201 and the printer unit 202 in the image processing apparatus.

<本明細書における用語の定義>
ここでは本明細書で使用する用語の定義について説明する。
<Definition of terms in this specification>
Here, definitions of terms used in this specification will be described.

「ディスプレイリスト」とは、各種PDLから変換され生成される、RIPが処理できる共通フォーマットである。ディプレイリストには、インストラクションと呼ばれるどのオブジェクトをどの場所に書くかという描画命令、各オブジェクトにひも付けられるエッジ情報、レベル情報、レベル情報にひも付けられるフィル情報、及びROP情報が記載されている。   The “display list” is a common format that can be processed by the RIP, generated by conversion from various PDLs. In the display list, a drawing command indicating which object called an instruction is written in which location, edge information associated with each object, level information, fill information associated with level information, and ROP information are described. .

「エッジ」とは、ページ内に描画するオブジェクトと、オブジェクトとの境目又はオブジェクトと、背景との境目を指す。オブジェクトは左右のエッジにより形状が形成される。処理中のスキャンラインにおける左右エッジのX座標を左右のX座標と呼ぶ。   “Edge” refers to a boundary between an object drawn in a page and an object or a boundary between an object and a background. The shape of the object is formed by the left and right edges. The X coordinates of the left and right edges in the scan line being processed are referred to as the left and right X coordinates.

「スパン」とは、エッジ間で囲まれる閉領域を指す。   “Span” refers to a closed region surrounded by edges.

「レベル」とは、ページ内に描画するオブジェクト同士の上下関係を示すもので、必ずオブジェクト毎にレベル番号が割り振られている。なお、上記のとおりオブジェクトは左右のエッジにより形状が形成されるので、ページ内に描画するエッジ同士の上下関係もレベルによって示されることとなる。   “Level” indicates the vertical relationship between objects drawn in a page, and a level number is always assigned to each object. As described above, since the shape of the object is formed by the left and right edges, the vertical relationship between the edges drawn in the page is also indicated by the level.

「フィル」とは、スパンに対する塗りのことで、Bitmap画像やシェーディングのように1ピクセル毎に異なる色値を持つフィルや、ベタ塗りのようにスパン中で色値の変化がないフィル等が存在する。   “Fill” means painting on the span, and there are fills with different color values for each pixel, such as Bitmap images and shading, and fills with no color value change in the span, such as solid painting. To do.

「スキャンライン」とは、それに沿ってスキャン処理が実行される用紙搬送方向の各ラインである。1スキャンラインの2次元平面における高さは1ピクセルとなっている。また、複数のスキャンラインを束ねたものをバンドと呼ぶ。   A “scan line” is a line in the paper conveyance direction along which a scan process is executed. The height of one scan line in the two-dimensional plane is 1 pixel. A bundle of a plurality of scan lines is called a band.

「グループ」とは、オブジェクト又はオブジェクトを形成する複数のエッジがレベル昇順にグループ化された集合である。一例として、レベル番号が1から3001までのエッジが1つずつ存在し、1つのグループに最大1000エッジ含まれる場合を検討する。この場合、最背面のグループにはレベル番号が1から1000までのエッジが含まれる。次に一つ上位のグループにはレベル番号が1001から2000までのエッジが含まれる。更に一つ上位のグループにはレベル番号が2001から3000までのエッジが含まれる。最上位のグループにはレベル番号が3001のエッジが含まれる。グループの上下関係を保持するために、各グループにはグループナンバー(本明細書ではグループNOと略記される)が割り振られている。例えば、最背面のグループのグループNOが1、その上のグループのグループNOが2等とすることができる。グループNOは、グループ管理構造体の中で管理されている。   A “group” is a set in which an object or a plurality of edges forming an object are grouped in ascending level order. As an example, consider a case where there is one edge with level numbers 1 to 3001, and a maximum of 1000 edges are included in one group. In this case, the rearmost group includes edges with level numbers 1 to 1000. The next higher group includes edges with level numbers 1001 to 2000. Further, an upper group includes edges having level numbers 2001 to 3000. The highest group includes an edge having a level number of 3001. In order to maintain the hierarchical relationship of groups, each group is assigned a group number (abbreviated as group NO in this specification). For example, the group NO of the backmost group can be 1, the group NO of the group above it can be 2, and so on. The group NO is managed in the group management structure.

<ディスプレイリストのレンダリング処理について>
図3は、スキャンラインレンダリングと呼ばれるレンダリング処理について説明した図である。以下の処理は、コントローラ101によって実行される。具体的には、以下の処理は、コントローラ101のCPU205が、HDD208に格納されているスキャンラインレンダリングのプログラムをRAM206にロード及び実行することで、実行される。
<About display list rendering>
FIG. 3 is a diagram illustrating a rendering process called scanline rendering. The following processing is executed by the controller 101. Specifically, the following processing is executed when the CPU 205 of the controller 101 loads and executes a scan line rendering program stored in the HDD 208 into the RAM 206.

図3(a)は、本実施例に係るスキャンラインレンダリング処理の処理フローについて説明するブロック図である。スキャンラインレンダリング処理は大きく分けて、エッジ処理、レベル処理、フィル処理、コンポジット処理の4つに分かれている。以下に各処理の詳細を記載する。なお、CPU205が複数のCPUで構成されている場合、それぞれのCPUに別々の処理を実行させてもよい。具体的には、1つ目のCPUにエッジ処理だけを実行させ、2つ目のCPUにレベル処理だけを実行させ、3つ目のCPUにフィル処理だけを実行させ、4つ目のCPUにコンポジット処理だけを実行させてもよい。   FIG. 3A is a block diagram illustrating a processing flow of scanline rendering processing according to the present embodiment. The scan line rendering process is roughly divided into four processes: edge processing, level processing, fill processing, and composite processing. Details of each process are described below. In addition, when CPU205 is comprised by several CPU, you may make each CPU perform a separate process. Specifically, only the edge processing is executed by the first CPU, only the level processing is executed by the second CPU, only the fill processing is executed by the third CPU, and the fourth CPU is executed. Only the composite processing may be executed.

<エッジ処理>
エッジ処理は大きく分けて5つの処理からなっている。5つの処理とは、エッジロード処理、エッジ削除処理、X座標算出処理、エッジソート処理、及びエッジトラッキング処理である。
<Edge processing>
Edge processing is roughly divided into five processes. The five processes are an edge load process, an edge deletion process, an X coordinate calculation process, an edge sort process, and an edge tracking process.

エッジロード処理とは、DL(ディスプレイリスト)メモリに格納されているディスプレイリストから、オブジェクトのアウトラインを示すエッジデータをメインメモリ上へロードする処理のことをいう。なお、エッジロード処理は、エッジデータを後述のリンクリストとして管理すべく、エッジデータをエッジリストにロードする処理とも言い換えることができる。   Edge load processing refers to processing for loading edge data indicating the outline of an object onto a main memory from a display list stored in a DL (display list) memory. The edge loading process can also be referred to as a process of loading edge data into the edge list in order to manage the edge data as a link list described later.

X座標算出処理とは、ロードされたエッジデータに対して、スキャンライン毎に、エッジの傾きや塗りルールに基づいてエッジの位置を示すX座標を算出する処理である。   The X coordinate calculation process is a process for calculating the X coordinate indicating the position of the edge based on the inclination of the edge and the paint rule for each scan line with respect to the loaded edge data.

処理中のスキャンラインに現れるエッジは、ActiveEdgeList(AEL)と呼ばれるリンクリスト(エッジリスト)によって、スキャンライン毎にエッジリストの先頭からエッジのX座標昇順でソートされている。N番目のスキャンラインにおけるエッジリストに含まれるエッジデータは、直前に走査したスキャンラインであるN−1番目のスキャンラインにおけるエッジリストを用いてソートされる。   Edges appearing on the scan line being processed are sorted in ascending order of the X coordinate from the head of the edge list for each scan line by a link list (edge list) called ActiveEdgeList (AEL). The edge data included in the edge list in the Nth scan line is sorted using the edge list in the (N−1) th scan line, which is the scan line scanned immediately before.

具体的には、N番目のスキャンラインのエッジリストにおいてエッジデータが、それぞれのX座標に従ってエッジE1、E2、E3の順でソートされていると仮定する。そして、スキャンラインが変わった際に、N+1番目のスキャンライン上のエッジE1、E2、E3のX座標をX座標算出処理によって求める。そして、N番目のスキャンラインのエッジリスト及びX座標算出処理によって求められたエッジE1、E2、E3のX座標に従って、N+1番目のスキャンラインエッジリストにおいてエッジE1〜E3のソートを実行する。   Specifically, it is assumed that the edge data is sorted in the order of the edges E1, E2, and E3 according to the respective X coordinates in the edge list of the Nth scan line. When the scan line changes, the X coordinates of the edges E1, E2, and E3 on the (N + 1) th scan line are obtained by the X coordinate calculation process. Then, according to the edge list of the Nth scan line and the X coordinates of the edges E1, E2, and E3 obtained by the X coordinate calculation process, the sorting of the edges E1 to E3 is executed in the N + 1th scan line edge list.

ここでN番目のスキャンラインのエッジリストにおいてはエッジE1、E2、E3の順でソートされているので、まず、エッジE3のX座標と、N番目のスキャンラインのエッジリストにおいては1つ前のエッジであったエッジE2のX座標とを比較する。これによって、N+1番目のスキャンラインのエッジリストにおいて、エッジE3がエッジE2よりも前にあるかどうかを判定する。エッジE3がエッジE2より前にある場合に、エッジE3のX座標は、N番目のスキャンラインのエッジリストにおいてエッジE2よりさらに前のエッジE1のX座標と比較される。これにより、N+1番目のスキャンラインのエッジリストにおいてエッジE3がエッジE1よりも前にあるかどうかが判定される。   Here, since the edge list of the Nth scan line is sorted in the order of the edges E1, E2, and E3, first, the X coordinate of the edge E3 and the edge list of the Nth scan line are the previous one. The X coordinate of the edge E2 that was the edge is compared. Thus, it is determined whether or not the edge E3 is before the edge E2 in the edge list of the (N + 1) th scan line. When the edge E3 is before the edge E2, the X coordinate of the edge E3 is compared with the X coordinate of the edge E1 before the edge E2 in the edge list of the Nth scan line. Thus, it is determined whether or not the edge E3 is before the edge E1 in the edge list of the (N + 1) th scan line.

そして、これらの比較判定の結果に従ってN+1番目のスキャンラインのエッジリストにおけるエッジE3の順番が決定され、決定された順番となるようにエッジリストのリンク構造を更新する。この処理はそれぞれのエッジに対しても実行され、N+1番目のスキャンラインのエッジリストが更新される。   Then, the order of the edge E3 in the edge list of the (N + 1) th scan line is determined according to the result of the comparison determination, and the link structure of the edge list is updated so as to be the determined order. This process is also executed for each edge, and the edge list of the (N + 1) th scan line is updated.

なお、エッジのX座標同士の比較が行われる際に、エッジデータがCPUキャッシュ上になければメインメモリ上のエッジデータにアクセスする必要がある。しかし、エッジデータがCPUキャッシュにコピーされている場合には、メインメモリではなくCPUキャッシュ上のエッジデータにアクセスすることで処理が高速化される。このような動作は、CPUキャッシュと接続するCPU205の動作として一般的である。   When the edge X coordinates are compared, if the edge data is not on the CPU cache, it is necessary to access the edge data on the main memory. However, when the edge data is copied to the CPU cache, the processing is speeded up by accessing the edge data on the CPU cache instead of the main memory. Such an operation is a general operation of the CPU 205 connected to the CPU cache.

以上説明したように、スキャンラインが変わってエッジのX座標の前後が逆転した場合、新たにエッジが出現した場合、又はエッジが消滅した場合等に、エッジリストのリンク構造を更新する必要が生じる。このエッジリストを更新する処理をエッジソート処理と呼んでいる。   As described above, it is necessary to update the link structure of the edge list when the scan line changes and the front and back of the X coordinate of the edge are reversed, when an edge newly appears, or when an edge disappears, etc. . This processing for updating the edge list is called edge sorting processing.

エッジソート処理が終わったエッジリストはレベル処理部に渡されて、X座標昇順でのエッジデータ及びレベルデータがレベル処理部に渡される。この処理をエッジトラッキング処理と呼んでいる。   The edge list after the edge sort processing is passed to the level processing unit, and the edge data and level data in the ascending order of the X coordinates are passed to the level processing unit. This processing is called edge tracking processing.

最後に、描画が終了したエッジは、メモリから削除される。この処理をエッジ削除処理と呼んでいる。   Finally, the edge for which drawing has been completed is deleted from the memory. This processing is called edge deletion processing.

<レベル処理>
レベル処理は大きく分けて3つの処理からなっている。3つの処理とは、レベル追加処理、レベル削除処理、及びレベルソート処理である。
<Level processing>
Level processing is roughly divided into three processes. The three processes are a level addition process, a level deletion process, and a level sort process.

レベル追加処理において、エッジ処理から送られてきたエッジデータに含まれるエッジの向きやクリップ情報に基づいてエッジが描画対象のエッジであるか否かが判定される。エッジが描画対象であると判定された場合、ActiveLevelList(ALL)と呼ばれるリンクリストに、該当するレベルデータが追加される。   In the level addition process, it is determined whether the edge is a drawing target edge based on the edge direction and the clip information included in the edge data sent from the edge process. When it is determined that the edge is a drawing target, the corresponding level data is added to a link list called Active Level List (ALL).

レベル削除処理は、レベル追加処理と逆の処理である。レベルの削除処理において、エッジの向きやクリップ情報に基づいてそれまで描画対象だったエッジが描画対象でなくなったと判定された場合、ALLから該当するレベルデータが削除される。   The level deletion process is the reverse of the level addition process. In the level deletion processing, when it is determined that the edge that has been the drawing target is no longer the drawing target based on the edge direction and the clip information, the corresponding level data is deleted from the ALL.

ALLはレベル番号昇順に常にソートされており、レベル追加処理やレベル削除処理があった場合、レベルソート処理と呼ばれるALLのソート処理が行われる。レベル追加処理、レベル削除処理、及びレベルソート処理を行ったレベルデータは、スパン単位でフィル処理に渡される。   ALL is always sorted in ascending order of level numbers, and when there is a level addition process or a level deletion process, an ALL sort process called a level sort process is performed. The level data that has been subjected to the level addition process, the level deletion process, and the level sort process is passed to the fill process in units of spans.

<フィル処理>
フィル処理は大きく分けて3つの処理からなっている。3つの処理とは、画像拡縮処理、画像回転処理、及びピクセル生成処理である。
<Fill processing>
The fill process is roughly divided into three processes. The three processes are an image enlargement / reduction process, an image rotation process, and a pixel generation process.

画像拡縮処理は、ディスプレイリストに含まれているビットマップ画像に拡大率が指定されていた場合に、指定された拡大率に従って各ピクセルの色値を生成する処理である。   The image enlargement / reduction process is a process for generating a color value of each pixel according to a specified enlargement ratio when an enlargement ratio is specified for a bitmap image included in the display list.

画像回転処理は、ディスプレイリストに含まれているビットマップ画像に回転情報が指定されていた場合に、指定された回転情報に従って各ピクセルの色値を生成する処理である。   The image rotation process is a process for generating the color value of each pixel according to the specified rotation information when the rotation information is specified in the bitmap image included in the display list.

ピクセル生成処理は、ディスプレイリストにおいて、ある色値をある色値に変化させる変化情報が指定されていた場合に、指定された変化情報に従って各ピクセルの色値を生成する処理である。   The pixel generation process is a process of generating the color value of each pixel according to the specified change information when change information for changing a certain color value to a certain color value is specified in the display list.

<コンポジット処理>
コンポジット処理とは、レベル処理で確定したレベルの上下関係及びフィル処理で生成したピクセル値に基づいて実行される、ディスプレイリストに指定されている重ね合わせ処理である。
<Composite processing>
The composite process is an overlay process specified in the display list, which is executed based on the level relationship determined by the level process and the pixel value generated by the fill process.

<並列処理されるエッジ処理、レベル処理、フィル処理、及びコンポジット処理>
上で説明した各処理は、スパンを単位としてパイプラインで並列に処理される。この並列処理について、図3(b)、(c)を用いて説明する。
<Edge processing, level processing, fill processing, and composite processing that are processed in parallel>
Each process described above is processed in parallel in the pipeline in units of spans. This parallel processing will be described with reference to FIGS.

図3(b)は、1枚のページ画像データを示す。オブジェクト403はオブジェクト401乃至403のうちで最背面のオブジェクトであり、最背面にあることを示すレベル番号が割り当てられている。オブジェクト403の上位にオブジェクト402が重なり、さらにオブジェクト402の上位にオブジェクト401が重なっている。これら3つのオブジェクトはすでにディスプレイリスト化されている。このようなページ画像データに対してスキャンライン毎にスキャンラインレンダリング処理を行う。   FIG. 3B shows one page image data. The object 403 is the backmost object among the objects 401 to 403, and is assigned a level number indicating that it is at the backmost. An object 402 overlaps above the object 403, and an object 401 overlaps above the object 402. These three objects are already in the display list. A scan line rendering process is performed on such page image data for each scan line.

詳細に図3(b)を説明すると、ページ画像データの1スキャンライン目は、オブジェクトが存在しないのでスパン1−1が処理される。2スキャンライン目は、オブジェクト402が存在し、2つのエッジが検出されるので、スパン2−1、2−2、2−3が処理される。3スキャンライン目は、オブジェクト401、402、403が存在し、6つのエッジが検出されるので、スパン3−1、3−2、3−3、3−4、3−5、3−6、3−7が処理される。4スキャンライン目以降も同様である。   Explaining FIG. 3B in detail, since the first scan line of the page image data has no object, span 1-1 is processed. In the second scan line, since the object 402 exists and two edges are detected, spans 2-1, 2-2, and 2-3 are processed. In the third scan line, objects 401, 402, and 403 exist and six edges are detected, so spans 3-1, 3-2, 3-3, 3-4, 3-5, 3-6, 3-7 is processed. The same applies to the fourth and subsequent scan lines.

このような各スキャンラインのスパンは、図3(c)に示されるように、エッジ処理、レベル処理、フィル処理、コンポジット処理の順でパイプライン処理される。   As shown in FIG. 3C, the span of each scan line is pipelined in the order of edge processing, level processing, fill processing, and composite processing.

図3(b)の例で言うと、図3(c)に示されるように、まず1スキャンライン目の1番目のスパン1−1がエッジ処理で処理され、続いてレベル処理に渡される。次に2スキャンライン目の1番目のスパン2−1がエッジ処理され、レベル処理に渡されるのと同時にスパン1−1がレベル処理され、フィル処理に渡される。以下同様に図3(c)で示すように各スパンが各処理で並列に処理される。   In the example of FIG. 3B, as shown in FIG. 3C, the first span 1-1 of the first scan line is first processed by edge processing, and then passed to level processing. Next, the first span 2-1 of the second scan line is subjected to edge processing and passed to level processing, and at the same time, the span 1-1 is subjected to level processing and passed to fill processing. Similarly, as shown in FIG. 3C, each span is processed in parallel in each process.

<大量エッジが含まれているディスプレイリストのエッジ処理>
図3ではオブジェクト401、402、403が1つずつだった場合のレンダリング処理について説明した。ここではオブジェクト402、403がそれぞれ1000個ずつ重なった場合の、エッジ処理におけるエッジソート処理について図4を用いて説明する。図4(a)は、見た目上、図3(b)と同じ画像を示す画像データである。しかし図4(a)では、1000個のオブジェクト402が同じ位置に重なっており、また1000個のオブジェクト403が同じ位置に重なっている。
<Edge processing for display lists that contain a large number of edges>
In FIG. 3, the rendering processing in the case where there are one object 401, 402, and 403 has been described. Here, edge sort processing in edge processing when 1000 objects 402 and 403 overlap each other will be described with reference to FIG. FIG. 4A is image data that visually shows the same image as FIG. However, in FIG. 4A, 1000 objects 402 overlap at the same position, and 1000 objects 403 overlap at the same position.

図4(b)は、図4(a)のスパン3−2付近の破線で表される円内のオブジェクトの配置を拡大した図である。図4(b)中の縦線で表された部分がオブジェクト401の領域である。また、X0は、4スキャンライン目のオブジェクト401の左側のエッジのX座標である。X1は、オブジェクト402の左側のエッジのX座標である。X2は、オブジェクト403の左側のエッジのX座標である。X3は、3スキャンライン目のオブジェクト401の左側のエッジのX座標である。すなわち、3スキャンライン目から4スキャンライン目へとスキャンラインが変わると、オブジェクト401の左側のエッジが1000個のオブジェクト402及び1000個のオブジェクト403を横切ることになる。したがって、図4(c)に示されるように、エッジソート処理によって、3スキャンライン目のエッジリスト上のオブジェクト401のエッジデータは、1000個のオブジェクト402のエッジデータ及び1000個のオブジェクト403のエッジデータを辿る。そして、4スキャンライン目のエッジリストの状態になるように、エッジリストの先頭へオブジェクト401のエッジデータが移される。   FIG. 4B is an enlarged view of the arrangement of objects in a circle represented by a broken line near the span 3-2 in FIG. A portion represented by a vertical line in FIG. 4B is an area of the object 401. X0 is the X coordinate of the left edge of the object 401 on the fourth scan line. X1 is the X coordinate of the left edge of the object 402. X2 is the X coordinate of the left edge of the object 403. X3 is the X coordinate of the left edge of the object 401 on the third scan line. That is, when the scan line changes from the third scan line to the fourth scan line, the left edge of the object 401 crosses 1000 objects 402 and 1000 objects 403. Therefore, as illustrated in FIG. 4C, the edge data of the object 401 on the edge list of the third scan line is converted into the edge data of 1000 objects 402 and the edges of 1000 objects 403 by the edge sorting process. Trace the data. Then, the edge data of the object 401 is moved to the head of the edge list so as to be in the state of the edge list of the fourth scan line.

つまり、図4(c)では、前述したように、処理中に現れるエッジデータはAELとしてX座標昇順でリンクされている。3スキャンライン目ではオブジェクト402の左側のエッジが1000個分リンクで繋がっており、次にオブジェクト403の左側のエッジが1000個分リンクで繋がっており、最後にオブジェクト401の左側のエッジがリンクされている。   That is, in FIG. 4C, as described above, edge data appearing during processing is linked as AEL in ascending X coordinate order. In the third scan line, the left edge of the object 402 is linked by 1000 links, then the left edge of the object 403 is linked by 1000 links, and finally the left edge of the object 401 is linked. ing.

スキャンラインが3スキャンライン目から4スキャンライン目に移る際、オブジェクト401の左側のエッジはX座標がX3からX0に変化する。X0<X1<X2<X3であるから、オブジェクト401の左側のエッジは、エッジソート処理でオブジェクト402の左側のエッジ及びオブジェクト403の左側のエッジをそれぞれ1000個ずつ辿って所定の位置にリンクされることになる。   When the scan line moves from the third scan line to the fourth scan line, the X coordinate of the left edge of the object 401 changes from X3 to X0. Since X0 <X1 <X2 <X3, the left edge of the object 401 is linked to a predetermined position by following the left edge of the object 402 and the left edge of the object 403 by the edge sorting process. It will be.

リンクを辿る際は、メインメモリ上のエッジデータに順次アクセスして、各エッジのX座標と、ソート対象エッジのX座標とを比較する。エッジ数が少ない場合は、エッジデータへのアクセスの際、全スキャンラインを通して1回以上アクセスされるエッジデータの全てがCPUキャッシュに格納された状態となるので高速に処理できる。   When following the link, the edge data on the main memory is sequentially accessed, and the X coordinate of each edge is compared with the X coordinate of the sorting target edge. When the number of edges is small, all the edge data accessed at least once through all the scan lines is stored in the CPU cache when accessing the edge data, so that it can be processed at high speed.

しかし、図4で示した例のようにエッジリストに含まれるエッジデータ数が大量だった場合、全てのエッジデータはCPUキャッシュに収まりきらない。そのため、CPUキャッシュに存在しないエッジデータへのアクセスのために、メインメモリに直接アクセスしなければならず、処理時間が極端に遅くなることがある。特にこの例で挙げたように局所的にエッジが密集した場合(オブジェクト402の左側のエッジのX座標近傍に2000エッジが集中する場合)、少しのエッジの移動でも大量のエッジにアクセスしてエッジソート処理を行わなければならない。これにより、処理時間が極端に遅くなるという問題が生じる。   However, when the number of edge data included in the edge list is large as in the example shown in FIG. 4, not all edge data can fit in the CPU cache. Therefore, in order to access edge data that does not exist in the CPU cache, the main memory must be accessed directly, and the processing time may be extremely slow. In particular, as shown in this example, when edges are concentrated locally (when 2000 edges are concentrated in the vicinity of the X coordinate of the left edge of the object 402), even if a few edges are moved, a large number of edges are accessed and the edges are accessed. Sort processing must be performed. This causes a problem that the processing time becomes extremely slow.

<エッジのグループ分割処理>
図5を用いて、本実施例におけるエッジのグループ分割処理について説明する。ここでも、<大量エッジが含まれているディスプレイリストのエッジ処理>の項目で説明した場合、すなわちオブジェクト402、403がそれぞれ1000個ずつ同一箇所に重なっている場合を例に挙げて説明する。
<Edge grouping process>
The edge group division processing in this embodiment will be described with reference to FIG. Here, the description will be given by taking as an example the case described in the item <edge processing of a display list including a large amount of edges>, that is, a case where 1000 objects 402 and 403 overlap each other at the same location.

入力されたディスプレイリストには、レベル番号1〜1000が振られた1000個のオブジェクト403、レベル番号1001〜2000が振られた1000個のオブジェクト402、及びレベル番号2001が振られた1個のオブジェクト401が含まれる。一つのオブジェクトは、左側のエッジと、右側のエッジとからなっている。このディスプレイリストには2001個のオブジェクトが含まれるので、エッジデータ数は4002個となる。   The input display list includes 1000 objects 403 assigned level numbers 1-1000, 1000 objects 402 assigned level numbers 1001-2000, and one object assigned level number 2001. 401 is included. One object consists of a left edge and a right edge. Since this display list includes 2001 objects, the number of edge data is 4002.

ここでCPUキャッシュのメモリが、2000エッジ分のエッジデータまではCPUキャッシュ内に保持でき、エッジデータ数が2001個以上の場合はCPUキャッシュから溢れてしまうとする。この場合、1つのグループには1000個のオブジェクト(2000個のエッジデータに相当)まで含まれるようにすればよいことになる。なお、この「エッジデータ数」はCPUキャッシュのメモリサイズ及びエッジデータのデータサイズによって異なるので、画像処理装置100が異なれば、CPUキャッシュに保持できるエッジデータ数も異なることになる。   Here, it is assumed that the CPU cache memory can hold up to 2000 edge data in the CPU cache, and if the number of edge data is 2001 or more, the CPU cache overflows. In this case, it is sufficient to include up to 1000 objects (corresponding to 2000 edge data) in one group. Since the “number of edge data” varies depending on the memory size of the CPU cache and the data size of the edge data, the number of edge data that can be held in the CPU cache varies depending on the image processing apparatus 100.

まず、コントローラ101は、入力されたディスプレイリストに含まれるオブジェクトのエッジと、このエッジのレベル番号とを確認することで、各々のエッジ(エッジデータ)がどのグループに属するべきか判定する。図5の例では、レベル番号1〜1000のオブジェクト403を形成するエッジがグループ1に、レベル番号1001〜2000のオブジェクト402を形成するエッジがグループ2に、オブジェクト401を形成するエッジがグループ3に属する。   First, the controller 101 determines which group each edge (edge data) should belong to by checking the edge of the object included in the input display list and the level number of this edge. In the example of FIG. 5, the edge that forms the object 403 with level numbers 1 to 1000 is in group 1, the edge that forms the object 402 with level numbers 1001 to 2000 is in group 2, and the edge that forms the object 401 is in group 3. Belongs.

各グループに対して生成されることになるビットマップは、背面のグループから重ね合わせる必要があるので必ず下位のグループ(本例ではグループ1)から順番にレンダリングしていく必要がある。しかし、各グループ内のオブジェクトに関してはレベル処理が行われるので、オブジェクトのレベル番号の小さい順に処理する必要はなくエッジが現れる順に処理すればよい。   Since the bitmap to be generated for each group needs to be overlaid from the rear group, it is necessary to always render in order from the lower group (group 1 in this example). However, since the level processing is performed on the objects in each group, it is not necessary to perform the processing in ascending order of the level numbers of the objects, and the processing may be performed in the order in which edges appear.

各グループでの処理はに対し、<ディスプレイリストのレンダリング処理方法について>の項目に記載したレンダリング処理方法を行うがが実行される、。ディスプレイリストを解釈する際、処理中のグループに属するエッジデータのみをメインメモリCPUキャッシュにロードして処理を行う実行する点が、本発明の特徴の一つである。   For the processing in each group, the rendering processing method described in the item <About display list rendering processing method> is performed. One feature of the present invention is that when interpreting the display list, only the edge data belonging to the group being processed is loaded into the main memory CPU cache for processing.

図5の1グループ目のページ画像の生成で示すように1グループ目のレンダリング処理によってビットマップ画像が生成された後(図5上段)に、2グループ目の処理に取り掛かる。2グループ目も1グループ目と同様、2グループ目に属するエッジのみをCPUキャッシュにロードしてレンダリング処理を行い、2グループ目のビットマップ画像を生成する。その後、1グループ目のビットマップ画像と、2グループ目のビットマップ画像との重ね合わせを行い、1グループ目のビットマップ画像と、2グループ目のビットマップ画像とが重ねあわされた画像が生成される(図5中段)。以下同様に、最上位グループまでレンダリング処理と、重ね合わせ処理とを繰り返し、最終的に、オブジェクト403の上位にオブジェクト402が重なり、オブジェクト402の上位にオブジェクト401が重なったビットマップ画像を生成する(図5下段)。   As shown in the generation of the page image of the first group in FIG. 5, after the bitmap image is generated by the rendering processing of the first group (the upper part of FIG. 5), the processing of the second group is started. Similarly to the first group, the second group loads only the edges belonging to the second group to the CPU cache and performs rendering processing to generate a bitmap image of the second group. Then, the bitmap image of the first group and the bitmap image of the second group are overlapped to generate an image in which the bitmap image of the first group and the bitmap image of the second group are overlapped. (Middle of FIG. 5). Similarly, the rendering process and the superimposition process are repeated up to the highest group, and finally a bitmap image in which the object 402 overlaps the object 403 and the object 401 overlaps the object 402 is generated ( FIG. 5 bottom).

<エッジのグループ分割後のコンポジット処理についての検討>
図6を用いて、図5を用いて説明したエッジのグループ分割後のコンポジット処理について検討する。コンポジット処理には、グループ内のコンポジット処理と、グループ間のコンポジット処理とがある。グループ内のコンポジット処理に関しては、エッジが一度にロードされレベル処理まで行われ、描画に必要のないレベルは削除されるため、必要最低限のコンポジットですむ。一方、グループ間のコンポジット処理は、図6に示すように、グループ間の全面ピクセル同士でコンポジット処理が行われることになり、また、グループが多ければその分グループ間のコンポジット処理回数も多くなる。したがって、グループが多い場合に処理速度のボトルネックになる可能性がある。よって、さらなる処理速度の向上のためには、グループ間のピクセルのコンポジット処理を効率良く行うことが求められる。
<Examination of composite processing after edge grouping>
The composite processing after the edge group division described with reference to FIG. 5 will be considered with reference to FIG. Composite processing includes composite processing within a group and composite processing between groups. For composite processing within a group, edges are loaded at once and level processing is performed, and levels not required for drawing are deleted, so that the minimum required composite is sufficient. On the other hand, as shown in FIG. 6, the composite processing between the groups is performed on the entire pixels between the groups, and if there are many groups, the number of composite processings between the groups increases accordingly. Therefore, when there are many groups, it may become a bottleneck of processing speed. Therefore, in order to further improve the processing speed, it is required to efficiently perform the pixel composite processing between groups.

<エッジのグループ分割後のグループ間のコンポジットスキップ処理>
図7を用いて、エッジのグループ分割後のグループ間のコンポジットスキップ処理について説明する。
<Composite skip processing between groups after edge grouping>
A composite skip process between groups after edge group division will be described with reference to FIG.

図7を参照すると、例示されるページには、最下位に三角形のオブジェクトを含むグループが存在し、このグループの上には大きな四角形のオブジェクトを含むグループが存在し、最上位には不透過の小さな四角形のオブジェクトを含むグループが存在する。あるスキャンラインAを処理する際、不透過の小さな四角形のオブジェクトがロードされる。   Referring to FIG. 7, in the illustrated page, there is a group that includes a triangular object at the bottom, a group that includes a large square object above this group, and an opaque object at the top. There is a group that contains small square objects. When processing a certain scan line A, an opaque small rectangular object is loaded.

この不透過の小さな四角形のオブジェクトは、最終的な描画結果として他のオブジェクトに上書きされずに表示される。言い換えれば、この不透過の小さな四角形のオブジェクトによって上書きされるより下のオブジェクトは描画されないことになる。   This opaque opaque rectangular object is displayed without being overwritten on other objects as a final drawing result. In other words, the object below the object that is overwritten by this opaque small rectangular object is not drawn.

本実施例では、不透過の小さな四角形のオブジェクトの左右のエッジのX座標(x、x)及びこのオブジェクトが属するグループのグループNo(本例では3)を保持する(図7のステップA−1参照)。オブジェクトのグループNoは、オブジェクトをレベルに応じてグループ分けする際にオブジェクト毎に割り当てられる。また、グループNoは、下位から上位になるにつれて昇順に設定される。つまり、上位のグループNoのグループに属するオブジェクトは、下位のグループNoのグループに属するオブジェクトを覆うことがあるが、その逆はない。具体的には、例えば、グループNo3のグループに属するオブジェクトは、グループNo1のグループに属するオブジェクトを覆って、上書きすることがある。しかし、グループNo1のグループに属するオブジェクトが、グループNo3のグループに属するオブジェクトを覆って、上書きすることはない。 In this embodiment, the X coordinates (x 1 , x 2 ) of the left and right edges of the small opaque object that is opaque and the group number (3 in this example) of the group to which this object belongs are retained (step A in FIG. 7). -1). The object group number is assigned to each object when the objects are grouped according to the level. Further, the group numbers are set in ascending order from the lower level to the higher level. That is, an object belonging to a higher group No group may cover an object belonging to a lower group No group, but not vice versa. Specifically, for example, an object belonging to the group No. 3 may cover and overwrite an object belonging to the group No. 1. However, the object belonging to the group No. 1 does not overwrite the object belonging to the group No. 3.

オブジェクトのエッジのX座標及びオブジェクトのグループNoを保持した後、スキャンラインAに隣接する次のスキャンラインBにおける処理を実行する。背面(白色)から生成されるBMPと、三角形のオブジェクトを含む最下位グループから生成されるBMPとをコンポジットする際、背面及び最下位グループは、ステップA−1における処理でグループNoを保持したグループより下位にある。したがって、X座標のxからxまでの区間(x、x)ではグループ間のコンポジット処理は行わず、その他の所のみグループ間のコンポジット処理を行う(図7のステップB−1参照)。 After holding the X coordinate of the edge of the object and the group number of the object, the process on the next scan line B adjacent to the scan line A is executed. When the BMP generated from the back (white) and the BMP generated from the lowest group including the triangular object are composited, the back and the lowest groups are groups in which the group No. is retained in the process in step A-1. It is lower. Therefore, the inter-group composite processing is not performed in the section (x 1 , x 2 ) from x 1 to x 2 of the X coordinate (see step B-1 in FIG. 7). ).

次のステップB−2においても同様に、区間(x、x)ではグループ間のコンポジット処理を行う必要はなく、その他の所のみグループ間のコンポジット処理を行う。 Similarly, in the next step B-2, it is not necessary to perform the inter-group composite processing in the section (x 1 , x 2 ), and the inter-group composite processing is performed only in other places.

最終的にステップB−3において、区間(x、x)は最上位グループから生成されるBMPにより上書きされ、最終的に出力されるBMPが生成される。 Finally, in step B-3, the section (x 1 , x 2 ) is overwritten by the BMP generated from the highest group, and the BMP to be finally output is generated.

<コンポジットスキップ処理フロー>
図8を用いて、図7に例示したコンポジットスキップ処理について詳細に説明する。図8に示す一連の処理は、図2のRIP216内のRAMにプログラムがロードされ、RIP216内のCPU上で動作することで実行される。
<Composite skip processing flow>
The composite skip process illustrated in FIG. 7 will be described in detail with reference to FIG. A series of processing shown in FIG. 8 is executed by loading a program into the RAM in the RIP 216 in FIG. 2 and operating on the CPU in the RIP 216.

ステップS800において、処理は開始される。次いで、処理は、ステップS802に進む。   In step S800, the process is started. Next, the process proceeds to step S802.

ステップS802において、RIP216内のCPUは、レンダリングを行うディスプレイリスト及びこのディスプレイリストに含まれるエッジ数を受信し、RIP216内のRAMに格納する。ディスプレイリストに含まれるエッジ数は、DL生成部がPDLからDLを生成しながらカウントすることによって得られる。合わせて、ステップS802において、キャッシュサイズ及びエッジデータのデータサイズから、エッジ処理においてキャッシュミスヒットが発生しないエッジ数(1個のグループが含み得る最大のエッジ数)を算出する。キャッシュミスヒットが発生しないエッジ数の算出方法は、下記<エッジ数算出方法>の項目に記載する。ディスプレイリストに含まれるエッジ数を、キャッシュミスヒットが発生しないエッジ数で割ることによって、グループ数を算出する。次いで、処理は、ステップS803に進む。   In step S <b> 802, the CPU in the RIP 216 receives the display list for rendering and the number of edges included in the display list, and stores the received display list in the RAM in the RIP 216. The number of edges included in the display list is obtained by the DL generation unit counting while generating DL from PDL. In addition, in step S802, from the cache size and the data size of the edge data, the number of edges (maximum number of edges that can be included in one group) that does not cause a cache miss hit in the edge processing is calculated. The method for calculating the number of edges at which no cache miss occurs is described in the item <Method for calculating the number of edges> below. The number of groups is calculated by dividing the number of edges included in the display list by the number of edges where no cache miss occurs. Next, the process proceeds to step S803.

ステップS803において、RIP216内のCPUは、エッジをグループ毎に分割する必要があるか否かを判定する。具体的には、ステップS802で算出したグループ数が1より多い場合は、グループ分割の必要があると判定し、処理は、ステップS809に進む。ステップS802で算出したグループ数が1以下の場合は、グループ分割の必要がないと判定し、処理は、ステップS804に進む。   In step S803, the CPU in the RIP 216 determines whether it is necessary to divide the edge into groups. Specifically, if the number of groups calculated in step S802 is greater than 1, it is determined that group division is necessary, and the process proceeds to step S809. If the number of groups calculated in step S802 is 1 or less, it is determined that group division is not necessary, and the process proceeds to step S804.

ステップS804において、RIP216内のCPUは、グループ分割を伴わない通常のRIP処理を実行する。次いで、処理は、ステップS820に進む。   In step S804, the CPU in the RIP 216 executes normal RIP processing that does not involve group division. Next, the process proceeds to step S820.

ステップS809において、RIP216内のCPUは、ディスプレイリストの解釈及びオブジェクトのロードを行う。次いで、処理は、ステップS810に進む。   In step S809, the CPU in the RIP 216 interprets the display list and loads an object. Next, the process proceeds to step S810.

ステップS810において、RIP216内のCPUは、ロードしたオブジェクトより下の領域でコンポジット処理が省略可能かを判定するために、ロードしたオブジェクトが不透過且つ矩形であり現在把握しているオブジェクトより上位であるか否かを判定する。オブジェクトが不透過且つ矩形であり現在把握しているオブジェクトより上位であると判定された場合、処理は、ステップS811に進む。オブジェクトが不透過且つ矩形であり現在把握しているオブジェクトより上位ではないと判定された場合、処理は、ステップS812に進む。   In step S810, the CPU in the RIP 216 determines whether the composite process can be omitted in an area below the loaded object, and the loaded object is opaque and rectangular, and is higher than the currently grasped object. It is determined whether or not. If it is determined that the object is opaque and rectangular and is higher than the currently recognized object, the process proceeds to step S811. If it is determined that the object is opaque and rectangular and is not higher than the currently recognized object, the process proceeds to step S812.

ステップS811において、RIP216内のCPUは、オブジェクトが属するグループのグループNo及びオブジェクトの左右のエッジのX座標を更新する。この更新処理は、RIP216内のCPUが、オブジェクトが属するグループのグループNo及びオブジェクトの左右のエッジのX座標をRIP216内のRAMに記憶することで行われる。次いで、処理は、ステップS812に進む。   In step S811, the CPU in the RIP 216 updates the group number of the group to which the object belongs and the X coordinates of the left and right edges of the object. This update process is performed by the CPU in the RIP 216 storing the group number of the group to which the object belongs and the X coordinates of the left and right edges of the object in the RAM in the RIP 216. Next, the process proceeds to step S812.

ステップS812において、RIP216内のCPUは、エッジ処理、レベル処理、及びフィル処理を行う。次いで、処理は、ステップS813に進む。   In step S812, the CPU in the RIP 216 performs edge processing, level processing, and fill processing. Next, the process proceeds to step S813.

ステップS813において、RIP216内のCPUは、行われるコンポジット処理がグループ間のコンポジット処理であるか否かを、コンポジット処理を行うオブジェクトの属するグループに基づいて判定する。行われるコンポジット処理がグループ間のコンポジット処理であると判定された場合、処理は、ステップS815に進み、行われるコンポジット処理がグループ間のコンポジット処理ではないと判定された場合、処理は、ステップS814に進む。   In step S813, the CPU in the RIP 216 determines whether the composite process to be performed is a composite process between groups based on the group to which the object that performs the composite process belongs. If it is determined that the composite process to be performed is a composite process between groups, the process proceeds to step S815. If it is determined that the composite process to be performed is not a composite process between groups, the process proceeds to step S814. move on.

ステップS814において、RIP216内のCPUは、<コンポジット処理>の項目で説明したコンポジット処理を行う。次いで、処理は、ステップS818に進む。   In step S814, the CPU in the RIP 216 performs the composite process described in the <Composite process> item. Next, the process proceeds to step S818.

ステップS815において、RIP216内のCPUは、ステップS811で把握しているオブジェクトが属するグループより下位のグループ同士のコンポジット処理が行われるか否かを判定する。この判定は、ステップS811における更新により記憶されたグループNoと、RIP216内のRAMが保持するグループNoとを比較することで実行される。例えば、ステップS811における更新により記憶されたグループNoよりも処理されるオブジェクトのグループNoが小さい場合、ステップS811で把握しているオブジェクトが属するグループより下位のグループ同士のコンポジット処理が行われると判定する。一方、ステップS811における更新により記憶されたグループNoよりも処理されるオブジェクトのグループNoが大きい場合、ステップS811で把握しているオブジェクトが属するグループより上位のグループ同士のコンポジット処理が行われると判定する。ステップS811で把握しているオブジェクトが属するグループより下位のグループ同士のコンポジット処理が行われると判定された場合、処理は、ステップS816に進む。ステップS811で把握しているオブジェクトが属するグループより下位のグループ同士のコンポジット処理が行われないと判定された場合、処理は、ステップS814に進む。   In step S815, the CPU in the RIP 216 determines whether or not composite processing is performed between groups lower than the group to which the object grasped in step S811 belongs. This determination is performed by comparing the group number stored by the update in step S811 with the group number held in the RAM in the RIP 216. For example, when the group number of the object to be processed is smaller than the group number stored by the update in step S811, it is determined that the composite processing is performed between the groups lower than the group to which the object grasped in step S811 belongs. . On the other hand, when the group number of the object to be processed is larger than the group number stored by the update in step S811, it is determined that the composite processing is performed between the groups higher than the group to which the object grasped in step S811 belongs. . In the event that determination is made in step S811 that composite processing of groups lower than the group to which the object that is grasped belongs is performed, the processing proceeds to step S816. If it is determined in step S811 that the composite processing of groups lower than the group to which the object grasped is not performed is performed, the process proceeds to step S814.

ステップS816において、RIP216内のCPUは、ステップS811で更新したX座標間でグループ間のコンポジット処理が行われているか否かを判定する。具体的には、この判定は、現在処理中のグループ間のコンポジット処理が実行される区間と、ステップS811で更新された区間とを比較することにより実行される。例えば、ステップS811で把握しているオブジェクトの左側のエッジのX座標が100、右側のエッジのX座標が500だとする。そして、現在処理中のコンポジット処理がX=150〜300の区間で実行される場合、コンポジット処理が実行される区間はステップS811で把握している区間内に含まれるので、この部分のコンポジット処理は省略できると判定される。ステップS811で更新したX座標間でグループ間のコンポジット処理が行われると判定された場合、処理は、ステップS818に進む。ステップS811で更新したX座標間でグループ間のコンポジット処理が行われないと判定された場合、処理は、ステップS817に進む。   In step S816, the CPU in the RIP 216 determines whether or not composite processing between groups is performed between the X coordinates updated in step S811. Specifically, this determination is executed by comparing the section in which the composite process between the groups currently being processed is executed with the section updated in step S811. For example, assume that the X coordinate of the left edge of the object grasped in step S811 is 100, and the X coordinate of the right edge is 500. When the composite process currently being processed is executed in the section of X = 150 to 300, since the section in which the composite process is executed is included in the section grasped in step S811, the composite process of this part is It is determined that it can be omitted. If it is determined that the inter-group composite process is performed between the X coordinates updated in step S811, the process proceeds to step S818. If it is determined that composite processing between groups is not performed between the X coordinates updated in step S811, the process proceeds to step S817.

ステップS817において、RIP216内のCPUは、グループ間のコンポジット処理を行う。次いで、処理は、ステップS818に進む。   In step S817, the CPU in the RIP 216 performs composite processing between groups. Next, the process proceeds to step S818.

ステップS818は、オブジェクト毎の処理のループ端である。ステップS818において、RIP216内のCPUは、処理中のスキャンラインにおけるオブジェクトの処理が全て終了したか否かを判定する。処理中のスキャンラインにおけるオブジェクトの処理が全て終了したと判定された場合、処理は、ステップS819に進む。処理中のスキャンラインにおけるオブジェクトの処理が全て終了していないと判定された場合、処理は、ループ端であるステップS808に飛ぶ。   Step S818 is a loop end of processing for each object. In step S818, the CPU in the RIP 216 determines whether or not the processing of all objects on the scan line being processed has been completed. If it is determined that the processing of all objects on the scan line being processed has been completed, the processing proceeds to step S819. If it is determined that the processing of all objects in the scan line being processed has not been completed, the processing jumps to step S808, which is the loop end.

ステップS819は、スキャンライン毎の処理のループ端である。ステップS819において、RIP216内のCPUは、処理中のページにおけるスキャンラインの処理が全て終了したか否かを判定する。処理中のページにおけるスキャンラインの処理が全て終了したと判定された場合、処理は、ステップS820に進み、処理中のページにおけるスキャンラインの処理が全て終了していないと判定された場合、処理は、ループ端であるステップS807に飛ぶ。   Step S819 is a loop end of processing for each scan line. In step S <b> 819, the CPU in the RIP 216 determines whether all scan line processing for the page being processed has been completed. If it is determined that all the scan line processes on the page being processed have been completed, the process proceeds to step S820. If it is determined that all the scan line processes on the page being processed have not been completed, the process proceeds to step S820. Then, the process jumps to step S807 which is a loop end.

ステップS820において、一連の処理は、終了する。   In step S820, the series of processing ends.

<エッジ数算出方法>
ここで、キャッシュミスヒットが発生しないエッジ数の算出方法を、具体例を挙げて説明する。例えば、CPUキャッシュサイズが32Kbyteで、1つのエッジデータのデータサイズが64byteだった場合、CPUキャッシュサイズを1つのエッジデータのデータサイズで割った値、512個がキャッシュミスヒットが発生しないエッジ数となる。
<Edge number calculation method>
Here, a method for calculating the number of edges at which no cache miss hit occurs will be described with a specific example. For example, if the CPU cache size is 32 Kbytes and the data size of one edge data is 64 bytes, the value obtained by dividing the CPU cache size by the data size of one edge data, 512 is the number of edges at which no cache miss occurs. Become.

<複数の区間におけるグループ間のコンポジットスキップ処理>
実施例1では1スキャンラインにおいてコンポジットスキップする区間は一つだけだったが、1スキャンラインにおいて複数の区間に対してコンポジットスキップ処理を実行しても構わない。
<Composite skip processing between groups in multiple sections>
In the first embodiment, only one section is subjected to composite skip in one scan line. However, composite skip processing may be executed for a plurality of sections in one scan line.

図9を用いて、複数の区間におけるグループ間のコンポジットスキップ処理について説明する。   A composite skip process between groups in a plurality of sections will be described with reference to FIG.

図9に例示するページには、最下位に三角形のオブジェクトを含むグループが存在し、このグループの上には大きな四角形のオブジェクトを含むグループが存在する。また、当該グループの一つ上のグループとして中くらいの四角形のオブジェクトを含むグループが存在する。さらに、最上位には不透過の小さな四角形のオブジェクトを2つ含むグループが存在する。   In the page illustrated in FIG. 9, a group including a triangular object exists at the bottom, and a group including a large rectangular object exists above this group. In addition, there is a group including a medium rectangular object as a group above the group. In addition, there is a group including two non-transparent small square objects at the top.

スキャンラインAを処理する際、不透過の小さな四角形のオブジェクトが2つロードされる。この2つの不透過の小さな四角形のオブジェクトによって最終的に上書きされるので、この2つの不透過の小さな四角形のオブジェクトによって上書きされるそれより下のオブジェクトは描画されないことになる。   When processing the scan line A, two opaque small rectangular objects are loaded. Since these two opaque small square objects are finally overwritten, the objects below that overwritten by the two opaque small square objects will not be drawn.

本実施例では、不透過の小さな四角形のオブジェクトのそれぞれについて、左右のエッジのX座標及びグループNoを保持する。具体的には、1つ目の不透過の小さな四角形のオブジェクトについて、左右のエッジのX座標として(x、x)、グループNoとして4が保持される。また、2つ目の不透過の小さな四角形のオブジェクトについて、左右のエッジのX座標として(x、x)、グループNoとして4が保持される(図9のステップA−1参照)。 In the present embodiment, the X coordinate and the group number of the left and right edges are held for each of the small opaque objects. Specifically, with respect to the first opaque small rectangular object, X coordinates of the left and right edges are (x 1 , x 2 ), and 4 is held as the group number. For the second opaque small rectangular object, the X coordinate of the left and right edges is (x 3 , x 4 ), and 4 is held as the group number (see step A-1 in FIG. 9).

オブジェクトのエッジのX座標及びオブジェクトのグループNoを保持した後、スキャンラインAに隣接する次のスキャンラインBにおける処理を実行する。ステップB−1において、背面(白色)から生成されるBMPと、三角形のオブジェクトを含む最下位グループから生成されるBMPとをコンポジットする。このとき、背面及び最下位グループは、ステップA−1における処理でグループNoを保持したグループより下位にある。したがって、区間(x、x)及び区間(x、x)ではグループ間のコンポジット処理は行わず、その他の所のみグループ間のコンポジット処理を行う。 After holding the X coordinate of the edge of the object and the group number of the object, the process on the next scan line B adjacent to the scan line A is executed. In step B-1, the BMP generated from the back surface (white) and the BMP generated from the lowest group including the triangular object are composited. At this time, the back surface and the lowest group are lower than the group holding the group number in the process in step A-1. Therefore, the inter-group composite processing is not performed in the section (x 1 , x 2 ) and the section (x 3 , x 4 ), and the inter-group composite processing is performed only in other places.

続くステップB−2、B−3においても同様に、区間(x、x)及び区間(x、x)ではグループ間のコンポジット処理を行う必要はなく、その他の所のみグループ間のコンポジット処理を行う。 Similarly, in the subsequent steps B-2 and B-3, it is not necessary to perform the inter-group composite processing in the section (x 1 , x 2 ) and the section (x 3 , x 4 ), and only between other groups. Perform composite processing.

最終的にステップB−4において、区間(x、x)及び区間(x、x)は最上位グループから生成されるBMPにより上書きされる。 Finally, in step B-4, the section (x 1 , x 2 ) and the section (x 3 , x 4 ) are overwritten by the BMP generated from the highest group.

<複数の区間におけるグループ間のコンポジットスキップ処理フロー>
図10を用いて、図9に例示した複数の区間におけるコンポジットスキップ処理について詳細に説明する。図10に示す一連の処理は、図2のRIP216内のRAMにプログラムがロードされ、RIP216内のCPU上で動作することで実行される。なお、本実施例に係る一連の処理は、実施例1に係る処理と一部同一である。具体的には、図8のステップS800〜S809の処理及びステップS812〜S820の処理に関して、本実施例の処理は、実施例1の処理と同一である。したがって、以下の説明では、実施例1と同一の処理については説明を省略し、ステップS1000(図8のS809)の後のステップS1001以降の処理について説明する。
<Composite skip processing flow between groups in multiple sections>
The composite skip process in the plurality of sections illustrated in FIG. 9 will be described in detail with reference to FIG. A series of processing shown in FIG. 10 is executed by loading a program into the RAM in the RIP 216 in FIG. 2 and operating on the CPU in the RIP 216. A series of processing according to the present embodiment is partially the same as the processing according to the first embodiment. Specifically, with respect to the processing of steps S800 to S809 and the processing of steps S812 to S820 of FIG. 8, the processing of the present embodiment is the same as the processing of the first embodiment. Therefore, in the following description, the description of the same processing as that in the first embodiment is omitted, and the processing after step S1001 after step S1000 (S809 in FIG. 8) will be described.

ステップS1001において、RIP216内のCPUは、ロードしたオブジェクトより下の領域でコンポジット処理が省略可能かを判定するために、ロードしたオブジェクトが不透過且つ矩形であり現在把握しているオブジェクトより上位であるか否かを判定する。オブジェクトが不透過且つ矩形であり現在把握しているオブジェクトより上位であると判定された場合、処理は、ステップS1002に進む。オブジェクトが不透過且つ矩形であり現在把握しているオブジェクトより上位ではないと判定された場合、処理は、ステップS1005に進む。   In step S1001, the CPU in the RIP 216 determines whether the composite process can be omitted in the area below the loaded object, and the loaded object is opaque and rectangular, and is higher than the currently grasped object. It is determined whether or not. If it is determined that the object is opaque and rectangular and is higher than the currently grasped object, the process proceeds to step S1002. If it is determined that the object is opaque and rectangular and is not higher than the currently recognized object, the process advances to step S1005.

ステップS1002において、RIP216内のCPUは、グループ間のコンポジットスキップ処理の対象となる区間の数が保持できる個数以内か否かを判定する。保持可能な、グループ間のコンポジットスキップ処理の対象となる区間の数は、予め設定されている。グループ間のコンポジットスキップ処理の対象となる区間の数が保持できる個数以内である場合、処理は、ステップS1003に進む。グループ間のコンポジットスキップ処理の対象となる区間の数が保持できる個数より多い場合、処理は、ステップS1004に進む。   In step S1002, the CPU in the RIP 216 determines whether or not the number of sections to be subjected to composite skip processing between groups is within the number that can be held. The number of sections that can be retained and subjected to composite skip processing between groups is set in advance. If the number of sections targeted for composite skip processing between groups is within the number that can be held, the process proceeds to step S1003. If the number of sections to be subjected to composite skip processing between groups is larger than the number that can be held, the processing proceeds to step S1004.

ステップS1003において、RIP216内のCPUは、エッジのロード時に取得したオブジェクトが属するグループNoと、当該オブジェクトの左右のエッジのX座標とを追加登録する。次いで、処理は、ステップS1005(図8のS812)に進む。   In step S1003, the CPU in the RIP 216 additionally registers the group number to which the object acquired when loading the edge belongs and the X coordinates of the left and right edges of the object. Next, the process proceeds to step S1005 (S812 in FIG. 8).

ステップS1004において、RIP216内のCPUは、保持しているオブジェクトの中で最も背面に近いオブジェクトに関するデータを削除して、ステップS1001でロードしたオブジェクトに関するデータを追加登録する。具体的には、エッジのロード時に取得したオブジェクトが属するグループNoと、当該オブジェクトの左右のエッジのX座標とを追加登録する。次いで、処理は、ステップS1005(図8のS812)に進む。   In step S1004, the CPU in the RIP 216 deletes the data related to the object closest to the back surface among the held objects, and additionally registers the data related to the object loaded in step S1001. Specifically, the group number to which the object acquired when loading the edge belongs and the X coordinates of the left and right edges of the object are additionally registered. Next, the process proceeds to step S1005 (S812 in FIG. 8).

<最適オブジェクトの選択を伴うコンポジットスキップ処理>
上述した実施例では、最上位のグループに属する不透過オブジェクトのスパンにおいて、グループ間のコンポジットスキップ処理を実行した。しかし、オブジェクトの形状によっては、最上位グループより低位のグループに属する不透過オブジェクトのスパンにおいて、グループ間のコンポジットスキップ処理を実行しても構わない。
<Composite skip processing with optimal object selection>
In the above-described embodiment, the composite skip process between groups is executed in the span of the opaque object belonging to the highest group. However, depending on the shape of the object, the composite skip processing between groups may be executed in the span of the opaque object belonging to the lower group than the highest group.

図11を用いて、最適オブジェクトの選択を伴うグループ間のコンポジットスキップ処理について説明する。   With reference to FIG. 11, a composite skip process between groups with selection of an optimal object will be described.

図11に例示するページには、最下位に三角形のオブジェクトを含むグループが存在し、このグループの上には大きな四角形のオブジェクトを含むグループが存在する。また、当該グループの一つ上のグループとして不透過の中くらいの四角形のオブジェクトを含むグループが存在する。さらに、最上位には不透過の小さな四角形のオブジェクトを含むグループが存在する。   In the page illustrated in FIG. 11, a group including a triangular object exists at the bottom, and a group including a large rectangular object exists above this group. In addition, there is a group including a non-transparent middle square object as a group above the group. Further, there is a group including a small opaque object that is opaque at the top.

スキャンラインAを処理する際、最上位グループに属する不透過の小さな四角形のオブジェクトがロードされる。しかし、このオブジェクトによって描画される四角形は所定の大きさより小さいので、本実施例では、当該オブジェクトを、コンポジットスキップを実行する際の基準にセットしない。本実施例では、コンポジットスキップを実行する際の基準に、最上位グループの下位のグループに属する不透過の中くらいの四角形のオブジェクトをセットする。この不透過の中くらいの四角形のオブジェクトによって上書きされる、それより下のオブジェクトは描画されないことになる。   When processing the scan line A, an opaque small square object belonging to the highest group is loaded. However, since the quadrangle drawn by this object is smaller than a predetermined size, in this embodiment, the object is not set as a reference for executing the composite skip. In the present embodiment, a non-transparent medium rectangular object belonging to a lower group of the highest group is set as a reference for executing composite skip. Any objects below it that are overwritten by this opaque medium square object will not be drawn.

本実施例では、中くらいの四角形のオブジェクトについて、左右のエッジのX座標及びグループNoを保持する。具体的には、左右のエッジのX座標として(x、x)、グループNoとして3が保持される。 In the present embodiment, the X coordinate and group No. of the left and right edges are held for a medium square object. Specifically, (x 1 , x 2 ) is held as the X coordinate of the left and right edges, and 3 is held as the group number.

オブジェクトのエッジのX座標及びオブジェクトのグループNoを保持した後、スキャンラインAに隣接する次のスキャンラインBにおける処理を実行する。ステップB−1において、背面(白色)から生成されるBMPと、三角形のオブジェクトを含む最下位グループから生成されるBMPとをコンポジットする。このとき、背面及び最下位グループは、ステップA−1における処理でグループNoを保持したグループより下位にある。したがって、区間(x、x)ではグループ間のコンポジット処理は行わず、その他の所のみグループ間のコンポジット処理を行う。 After holding the X coordinate of the edge of the object and the group number of the object, the process on the next scan line B adjacent to the scan line A is executed. In step B-1, the BMP generated from the back surface (white) and the BMP generated from the lowest group including the triangular object are composited. At this time, the back surface and the lowest group are lower than the group holding the group number in the process in step A-1. Therefore, the inter-group composite processing is not performed in the section (x 1 , x 2 ), and the inter-group composite processing is performed only in other places.

続くステップB−2においても同様に、区間(x、x)ではグループ間のコンポジット処理を行う必要はなく、その他の所のみグループ間のコンポジット処理を行う。 Similarly, in the subsequent step B-2, it is not necessary to perform the inter-group composite processing in the section (x 1 , x 2 ), and the inter-group composite processing is performed only in other places.

続くステップB−3においても同様に、区間(x、x)ではグループ間のコンポジット処理を行うことなく上書きされる。 Similarly, in the subsequent step B-3, overwriting is performed without performing composite processing between groups in the section (x 1 , x 2 ).

最終的にステップB−4において、小さな四角形が上書きされる。このとき、グループ間のコンポジット処理が行われるが、小さな四角形のオブジェクトのスパンは短いので、エッジ処理にそれほど時間を要さない。   Finally, in step B-4, the small rectangle is overwritten. At this time, composite processing between groups is performed. However, since the span of a small square object is short, the edge processing does not require much time.

<最適オブジェクトの選択を伴うコンポジットスキップ処理フロー>
図12を用いて、図11に例示した最適オブジェクトの選択を伴うコンポジットスキップ処理について詳細に説明する。図12に示す一連の処理は、図2のRIP216内のRAMにプログラムがロードされ、RIP216内のCPU上で動作することで実行される。なお、本実施例に係る一連の処理は、実施例1に係る処理と一部同一である。具体的には、図8のステップS800〜S809の処理及びステップS812〜S820の処理に関して、本実施例の処理は、実施例1の処理と同一である。したがって、以下の説明では、実施例1と同一の処理については説明を省略し、ステップS1200(図8のS809)の後のステップS1201以降の処理について説明する。
<Composite skip processing flow with optimal object selection>
With reference to FIG. 12, the composite skip process involving selection of the optimum object illustrated in FIG. 11 will be described in detail. A series of processing shown in FIG. 12 is executed by loading a program into the RAM in the RIP 216 in FIG. 2 and operating on the CPU in the RIP 216. A series of processing according to the present embodiment is partially the same as the processing according to the first embodiment. Specifically, with respect to the processing of steps S800 to S809 and the processing of steps S812 to S820 of FIG. 8, the processing of the present embodiment is the same as the processing of the first embodiment. Therefore, in the following description, the description of the same processing as in the first embodiment is omitted, and the processing after step S1201 after step S1200 (S809 in FIG. 8) will be described.

ステップS1201において、RIP216内のCPUは、ロードしたオブジェクトより下の領域でコンポジット処理が省略可能かを判定するために、ロードしたオブジェクトが不透過且つ矩形であり現在把握しているオブジェクトより上位であるか否かを判定する。ロードしたオブジェクトが不透過且つ矩形であり現在把握しているオブジェクトより上位であると判定された場合、処理は、ステップS1202に進む。ロードしたオブジェクトが不透過且つ矩形であり現在把握しているオブジェクトより上位ではないと判定された場合、処理は、ステップS1204に進む。   In step S1201, the CPU in the RIP 216 determines whether the composite process can be omitted in the area below the loaded object, and the loaded object is opaque and rectangular, and is higher than the currently recognized object. It is determined whether or not. If it is determined that the loaded object is opaque and rectangular and is higher than the currently recognized object, the process proceeds to step S1202. If it is determined that the loaded object is opaque and rectangular and is not higher than the currently grasped object, the process proceeds to step S1204.

ステップS1202において、RIP216内のCPUは、ロードされたオブジェクトの大きさが所定の大きさより大きいか否か(ロードされたオブジェクトのスパンの長さが所定の長さより長いか否か)を判定する。ロードされたオブジェクトの大きさが所定の大きさより大きいと判定された場合、処理は、ステップS1203に進み、ロードされたオブジェクトの大きさが所定の大きさ以下であると判定された場合、処理は、ステップS1204(図8のS812)に進む。   In step S1202, the CPU in the RIP 216 determines whether the size of the loaded object is larger than a predetermined size (whether the span length of the loaded object is longer than a predetermined length). If it is determined that the size of the loaded object is larger than the predetermined size, the process proceeds to step S1203. If it is determined that the size of the loaded object is equal to or smaller than the predetermined size, the process is performed. The process proceeds to step S1204 (S812 in FIG. 8).

ステップS1203において、RIP216内のCPUは、オブジェクトが属するグループのグループNo及びオブジェクトの左右のエッジのX座標を更新する。次いで、処理は、ステップS1204(図8のS812)に進む。   In step S1203, the CPU in the RIP 216 updates the group number of the group to which the object belongs and the X coordinates of the left and right edges of the object. Next, the process proceeds to step S1204 (S812 in FIG. 8).

<矩形以外のオブジェクトのスパンにおけるグループ間のコンポジットスキップ処理>
上述した実施例では、矩形のオブジェクトのスパンにおいて、グループ間のコンポジットスキップ処理を実行した。しかし、矩形以外のオブジェクトのスパンにおいて、グループ間のコンポジットスキップ処理を実行しても構わない。
<Composite skip processing between groups in non-rectangular object spans>
In the embodiment described above, the composite skip process between groups is executed in the span of a rectangular object. However, composite skip processing between groups may be executed in a span of an object other than a rectangle.

図13を用いて、矩形以外のオブジェクトのスパンにおけるグループ間のコンポジットスキップ処理について説明する。   A composite skip process between groups in a span of an object other than a rectangle will be described with reference to FIG.

図13に例示するページには、最下位に三角形のオブジェクトを含むグループが存在し、このグループの上には大きな四角形のオブジェクトを含むグループが存在する。また、最上位には不透過の台形のオブジェクトを含むグループが存在する。   In the page illustrated in FIG. 13, a group including a triangular object exists at the bottom, and a group including a large rectangular object exists above this group. In addition, a group including an opaque trapezoidal object exists at the top.

スキャンラインAを処理する際、最上位グループに属する不透過の台形のオブジェクトがロードされる。この不透過の台形のオブジェクトにより最終的に上書きされるので、この上書き部より下のオブジェクトは描画されないことになる。   When processing the scan line A, an opaque trapezoidal object belonging to the highest group is loaded. Since the object is finally overwritten by the opaque trapezoidal object, the object below the overwriting portion is not drawn.

本実施例では、不透過の台形のオブジェクトについて、左右のエッジのX座標及びグループNoを保持する。具体的には、左右のエッジのX座標として(x、x)、グループNoとして3が保持される。合わせて、台形のオブジェクトのエッジ処理を行う際、スキャンラインAに隣接する次のスキャンラインBにおけるスパン(x’、x’)も保持する(図13のステップA−1参照)。 In this embodiment, the X coordinate and group No. of the left and right edges are held for the opaque trapezoidal object. Specifically, (x 1 , x 2 ) is held as the X coordinate of the left and right edges, and 3 is held as the group number. In addition, when performing the edge processing of the trapezoidal object, the span (x 1 ′, x 2 ′) in the next scan line B adjacent to the scan line A is also held (see step A-1 in FIG. 13).

次いで、スキャンラインBにおける処理が実行される。ステップB−1において、背面(白色)から生成されるBMPと、三角形のオブジェクトを含む最下位グループから生成されるBMPとをコンポジットする。このとき、背面及び最下位グループは、ステップA−1における処理でグループNoを保持したグループより下位にある。したがって、区間(x’、x’)ではグループ間のコンポジット処理は行わず、その他の所のみグループ間のコンポジット処理を行う。 Next, processing in the scan line B is executed. In step B-1, the BMP generated from the back surface (white) and the BMP generated from the lowest group including the triangular object are composited. At this time, the back surface and the lowest group are lower than the group holding the group number in the process in step A-1. Therefore, the inter-group composite processing is not performed in the section (x 1 ′, x 2 ′), and the inter-group composite processing is performed only in other places.

続くステップB−2においても同様に、区間(x’、x’)ではグループ間のコンポジット処理を行う必要はなく、その他の所のみグループ間のコンポジット処理を行う。 Similarly, in the subsequent step B-2, it is not necessary to perform the inter-group composite processing in the section (x 1 ′, x 2 ′), and the inter-group composite processing is performed only in other places.

最終的にステップB−3において、区間(x’、x’)は最上位グループから生成されるBMPにより上書きされる。 Finally, in step B-3, the section (x 1 ′, x 2 ′) is overwritten by the BMP generated from the highest group.

<矩形以外のオブジェクトのスパンにおけるコンポジットスキップ処理フロー>
図14を用いて、図13に例示した矩形以外のオブジェクトのスパンにおけるコンポジットスキップ処理について詳細に説明する。図14に示す一連の処理は、図2のRIP216内のRAMにプログラムがロードされ、RIP216内のCPU上で動作することで実行される。なお、本実施例に係る一連の処理は、実施例1に係る処理と一部同一である。具体的には、図8のステップS800〜S809の処理及びステップS813〜S820の処理に関して、本実施例の処理は、実施例1の処理と同一である。したがって、以下の説明では、実施例1と同一の処理については説明を省略し、ステップS1400(図8のS809)の後のステップS1401以降の処理について説明する。
<Composite skip processing flow for spans of objects other than rectangles>
The composite skip process in the span of an object other than the rectangle illustrated in FIG. 13 will be described in detail with reference to FIG. A series of processing shown in FIG. 14 is executed by loading a program into the RAM in the RIP 216 in FIG. 2 and operating on the CPU in the RIP 216. A series of processing according to the present embodiment is partially the same as the processing according to the first embodiment. Specifically, with respect to the processing of steps S800 to S809 and the processing of steps S813 to S820 in FIG. 8, the processing of the present embodiment is the same as the processing of the first embodiment. Therefore, in the following description, the description of the same processing as that in the first embodiment will be omitted, and the processing after step S1401 after step S1400 (S809 in FIG. 8) will be described.

ステップS1401において、RIP216内のCPUは、ロードしたオブジェクトより下の領域でコンポジット処理が省略可能かを判定するために、ロードしたオブジェクトが不透過且つ現在把握しているオブジェクトより上位であるか否かを判定する。ロードしたオブジェクトが不透過且つ現在把握しているオブジェクトより上位であると判定された場合、処理は、ステップS1402に進む。ロードしたオブジェクトが不透過且つ現在把握しているオブジェクトより上位ではないと判定された場合、処理は、ステップS1403に進む。   In step S1401, the CPU in the RIP 216 determines whether or not the loaded object is higher than the object that is opaque and currently grasped in order to determine whether the composite processing can be omitted in the area below the loaded object. Determine. If it is determined that the loaded object is opaque and higher than the currently recognized object, the process proceeds to step S1402. If it is determined that the loaded object is not transparent and not higher than the currently recognized object, the process advances to step S1403.

ステップS1402において、RIP216内のCPUは、オブジェクトが属するグループのグループNo及びオブジェクトの左右のエッジのX座標を更新する。次いで、処理は、ステップS1403に進む。   In step S1402, the CPU in the RIP 216 updates the group number of the group to which the object belongs and the X coordinates of the left and right edges of the object. Next, the process proceeds to step S1403.

ステップS1403において、RIP216内のCPUは、保持しているオブジェクトのエッジ処理か否かを判定する。保持しているオブジェクトのエッジ処理と判定された場合、処理は、ステップS1404に進み、保持しているオブジェクトのエッジ処理ではないと判定された場合、処理は、ステップS1405に進む。   In step S1403, the CPU in the RIP 216 determines whether it is edge processing of the held object. If it is determined that the process is an edge process for a held object, the process proceeds to step S1404. If it is determined that the process is not an edge process for a held object, the process proceeds to step S1405.

ステップS1404において、RIP216内のCPUは、次のスキャンラインにおけるオブジェクトのエッジのX座標を算出し保持する。次いで、処理は、ステップS1405に進む。   In step S1404, the CPU in the RIP 216 calculates and holds the X coordinate of the edge of the object in the next scan line. Next, the process proceeds to step S1405.

ステップS1405において、RIP216内のCPUは、エッジ処理、レベル処理、及びフィル処理を行う。次いで、処理は、ステップS1406(図8のS813)に進む。   In step S1405, the CPU in the RIP 216 performs edge processing, level processing, and fill processing. Next, the process proceeds to step S1406 (S813 in FIG. 8).

<矩形以外のオブジェクトのスパンにおける簡易コンポジットスキップ処理>
実施例4では次のラインでスキップする区間(x’、x’)を現在処理中のラインにおける処理でライン毎に算出した。しかし、本実施例では、一旦ロードしたオブジェクトの左右のエッジによるスパン(x、x)を常にコンポジットスキップできる区間としてコンポジット処理を実行する。なお、本実施例は、あるスキャンラインから次のスキャンラインに処理が進む際にオブジェクトの左側のエッジがx軸マイナス方向に伸張し、右側のエッジがx軸プラス方向に伸張する場合を想定している。
<Simple composite skip processing for spans of objects other than rectangles>
In Example 4, the section (x 1 ′, x 2 ′) to be skipped in the next line was calculated for each line in the process on the currently processed line. However, in this embodiment, the composite processing is executed by setting the spans (x 1 , x 2 ) due to the left and right edges of the once loaded object as a section in which composite skip can always be performed. Note that this embodiment assumes a case where the left edge of the object extends in the x-axis minus direction and the right edge extends in the x-axis plus direction when processing proceeds from one scan line to the next. ing.

図15を用いて、矩形以外のオブジェクトのスパンにおけるグループ間の簡易コンポジットスキップ処理について説明する。   A simple composite skip process between groups in a span of an object other than a rectangle will be described with reference to FIG.

図15に例示するページには、最下位に三角形のオブジェクトを含むグループが存在し、このグループの上には大きな四角形のオブジェクトを含むグループが存在する。また、最上位には不透過の小さな台形のオブジェクトを含むグループが存在する。   In the page illustrated in FIG. 15, a group including a triangular object exists at the bottom, and a group including a large rectangular object exists above this group. In addition, there is a group including trapezoidal objects that are small and opaque at the top.

スキャンラインAを処理する際、最上位グループに属する不透過の台形のオブジェクトがロードされる。スキャンラインAの処理からスキャンラインBの処理に進む際、不透過の台形の左側のエッジは、x軸マイナス方向に進み、右側のエッジは、x軸プラス方向に進む。本実施例では、この不透過の台形のオブジェクトにより最終的に上書きされるので、この上書き部より下のオブジェクトは描画されないことになる。   When processing the scan line A, an opaque trapezoidal object belonging to the highest group is loaded. When proceeding from scan line A processing to scan line B processing, the left edge of the opaque trapezoid proceeds in the x-axis minus direction, and the right edge proceeds in the x-axis plus direction. In the present embodiment, the object is finally overwritten by the opaque trapezoidal object, so that the object below the overwritten portion is not drawn.

本実施例では、ロードされた台形のオブジェクトについて、左右のエッジによるスパンのうち最も上部のスパン及びグループNoを保持する。具体的には、スパンとして(x、x)、グループNoとして3が保持される。図15から分かるように、スパン(x、x)は、台形の上底を表す。 In the present embodiment, for the loaded trapezoidal object, the uppermost span and the group number among the spans by the left and right edges are held. Specifically, (x 1 , x 2 ) is retained as the span, and 3 is retained as the group number. As can be seen from FIG. 15, the span (x 1 , x 2 ) represents the upper base of the trapezoid.

次いで、スキャンラインBにおける処理が実行される。ステップB−1において、背面(白色)から生成されるBMPと、三角形のオブジェクトを含む最下位グループから生成されるBMPとをコンポジットする。このとき、背面及び最下位グループは、ステップA−1における処理でグループNoを保持したグループより下位にある。したがって、ステップA−1で保持した区間(x、x)ではグループ間のコンポジット処理は行わず、その他の所のみグループ間のコンポジット処理を行う。 Next, processing in the scan line B is executed. In step B-1, the BMP generated from the back surface (white) and the BMP generated from the lowest group including the triangular object are composited. At this time, the back surface and the lowest group are lower than the group holding the group number in the process in step A-1. Therefore, the inter-group composite processing is not performed in the section (x 1 , x 2 ) held in step A-1, and the inter-group composite processing is performed only in other places.

続くステップB−2においても同様に、区間(x、x)ではグループ間のコンポジット処理を行う必要はなく、その他の所のみグループ間のコンポジット処理を行う。 Similarly, in the subsequent step B-2, it is not necessary to perform the inter-group composite processing in the section (x 1 , x 2 ), and the inter-group composite processing is performed only in other places.

最終的にステップB−3において、不透過の台形のオブジェクトにより上書きされる。   Finally, in step B-3, the object is overwritten by the opaque trapezoidal object.

<矩形以外のオブジェクトのスパンにおける簡易コンポジットスキップ処理フロー>
図16を用いて、図15に例示した矩形以外のオブジェクトのスパンにおける簡易コンポジットスキップ処理について詳細に説明する。図16に示す一連の処理は、図2のRIP216内のRAMにプログラムがロードされ、RIP216内のCPU上で動作することで実行される。なお、本実施例に係る一連の処理は、実施例1に係る処理と一部同一である。具体的には、図8のステップS800〜S809の処理及びステップS812〜S820の処理に関して、本実施例の処理は、実施例1の処理と同一である。したがって、以下の説明では、実施例1と同一の処理については説明を省略し、ステップS1600(図8のS809)の後のステップS1601以降の処理について説明する。
<Simple composite skip processing flow for spans of objects other than rectangles>
The simple composite skip process in the span of an object other than the rectangle illustrated in FIG. 15 will be described in detail with reference to FIG. A series of processing shown in FIG. 16 is executed by loading a program into the RAM in the RIP 216 in FIG. 2 and operating on the CPU in the RIP 216. A series of processing according to the present embodiment is partially the same as the processing according to the first embodiment. Specifically, with respect to the processing of steps S800 to S809 and the processing of steps S812 to S820 of FIG. 8, the processing of the present embodiment is the same as the processing of the first embodiment. Therefore, in the following description, the description of the same processing as in the first embodiment is omitted, and the processing after step S1601 after step S1600 (S809 in FIG. 8) will be described.

ステップS1601において、RIP216内のCPUは、ロードしたオブジェクトが不透過且つ現在把握しているオブジェクトより上位であるか否か判定する。また、RIP216内のCPUは、ロードしたオブジェクトに関して、カレントスキャンラインが次のスキャンラインに進む際、左側のエッジがx軸マイナス方向に伸張し、右側のエッジがx軸プラス方向に伸張する台形か否かを、エッジの傾きに基づいて判定する。これらの条件を全て満たす場合、処理は、ステップS1602に進み、これらの条件を一つでも満たさない場合、処理は、ステップS1603(図8のS812)に進む。   In step S1601, the CPU in the RIP 216 determines whether or not the loaded object is higher than the object that is opaque and currently grasped. Also, the CPU in the RIP 216 is a trapezoid in which the left edge extends in the x-axis minus direction and the right edge extends in the x-axis plus direction when the current scan line advances to the next scan line for the loaded object. Is determined based on the inclination of the edge. If all of these conditions are satisfied, the process proceeds to step S1602, and if none of these conditions is satisfied, the process proceeds to step S1603 (S812 in FIG. 8).

ステップS1602において、RIP216内のCPUは、オブジェクトが属するグループのグループNo及びロードしたオブジェクトの左右のエッジのX座標を保持する。次いで、処理は、ステップS1603(図8のS812)に進む。   In step S1602, the CPU in the RIP 216 holds the group number of the group to which the object belongs and the X coordinates of the left and right edges of the loaded object. Next, the process proceeds to step S1603 (S812 in FIG. 8).

<エッジのグループ分割処理と、先行技術との関連について>
図17を用いて、本発明に係るエッジのグループ分割処理と、先行技術との関連について説明する。図17に示す一連の処理は、図2のRIP216内のRAMにプログラムがロードされ、RIP216内のCPU上で動作することで実行される。
<Relationship between edge grouping and prior art>
The relationship between the edge group division processing according to the present invention and the prior art will be described with reference to FIG. A series of processing shown in FIG. 17 is executed by loading a program into the RAM in the RIP 216 in FIG. 2 and operating on the CPU in the RIP 216.

エッジのグループ分割処理とは、実施例1で説明したように、ディスプレイリストを入力としビットマップを出力とした処理であり、CPUキャッシュサイズと、ディスプレイリストに含まれるエッジとに基づいて、エッジをグループに分割して行う処理である。   As described in the first embodiment, the edge group division process is a process in which the display list is input and the bitmap is output, and the edge is determined based on the CPU cache size and the edges included in the display list. This process is performed by dividing into groups.

また、本説明で登場する「フォールバック」とは背景技術で述べた処理のことである。入力されたPDLデータのデータサイズが大きい場合、ディスプレイリストを生成するためのメモリサイズが不足する場合がある。この場合、メモリサイズに収まるサイズのディスプレイリストをPDLデータから生成しレンダリングを行う。一度にディスプレイリストが生成できなかった残りのPDLデータも同様にメモリサイズに収まるようなディスプレイリストを生成し、既にレンダリングしたデータがある場合、重ね合わせを行う。   Further, “fallback” appearing in this description is the processing described in the background art. When the data size of the input PDL data is large, the memory size for generating the display list may be insufficient. In this case, a display list having a size that fits in the memory size is generated from the PDL data and rendered. A display list is generated so that the remaining PDL data for which the display list could not be generated at once also fits in the memory size. If there is already rendered data, superimposition is performed.

PDLのレンダリング処理は、ステップS1701で開始される。次いで、処理は、ステップS1703に進む。   The PDL rendering process starts in step S1701. Next, the process proceeds to step S1703.

ステップS1703において、RIP216内のCPUは、レンダリングを行うPDLを受信し、RIP216内のRAMに格納する。次いで、処理は、ステップS1704に進む。   In step S1703, the CPU in the RIP 216 receives the PDL for rendering and stores it in the RAM in the RIP 216. Next, the process proceeds to step S1704.

ステップS1704において、RIP216内のCPUは、PDLを解釈しディスプレイリストを生成する。次いで、処理は、ステップS1705に進む。   In step S1704, the CPU in the RIP 216 interprets the PDL and generates a display list. Next, the process proceeds to step S1705.

ステップS1705において、RIP216内のCPUは、処理中のページにおいてフォールバックが発生したか否かを判定する。フォールバックが発生したと判定された場合、処理は、ステップS1706に進み、フォールバックが発生していないと判定された場合、処理は、S1709に進む。   In step S1705, the CPU in the RIP 216 determines whether a fallback has occurred in the page being processed. If it is determined that a fallback has occurred, the process proceeds to step S1706. If it is determined that no fallback has occurred, the process proceeds to S1709.

ステップS1706において、RIP216内のCPUは、エッジをグループに分割した上でレンダリング処理を行う。次いで、処理は、ステップS1707に進む。   In step S1706, the CPU in the RIP 216 performs rendering processing after dividing the edges into groups. Next, the process proceeds to step S1707.

ステップS1707において、RIP216内のCPUは、ページの重ね合わせ処理を行う。ページの重ね合わせ処理については、<フォールバックにおける重ね合わせ処理>の項目で詳細を記載する。次いで、処理は、ステップS1708に進む。   In step S1707, the CPU in the RIP 216 performs page overlay processing. Details of the page overlay processing will be described in the <Fallback overlay processing> item. Next, the process proceeds to step S1708.

ステップS1708において、RIP216内のCPUは、入力された1ページ分のPDL処理が全て完了したか否かを判定する。入力された1ページ分のPDL処理が全て完了したと判定された場合、処理は、ステップS1711に進み、入力された1ページ分のPDL処理が全て完了していないと判定された場合、処理は、ステップS1704に戻る。   In step S1708, the CPU in the RIP 216 determines whether or not all the input one page of PDL processing has been completed. If it is determined that all the input PDL processes for one page have been completed, the process proceeds to step S1711. If it is determined that all of the input PDL processes for one page have not been completed, the process is Return to step S1704.

ステップS1709において、RIP216内のCPUは、エッジをグループに分割した上でレンダリング処理を行う。次いで、処理は、ステップS1711に進む。   In step S1709, the CPU in the RIP 216 performs rendering processing after dividing the edge into groups. Next, the process proceeds to step S1711.

ステップS1711において、RIP216内のCPUは、入力された全ページ分のPDL処理が全て完了したか否かを判定する。入力された全ページ分のPDL処理が全て完了したと判定された場合、処理は、ステップS1712に進み、入力された全ページ分のPDL処理が全て完了していないと判定された場合、処理は、ステップS1704に戻る。   In step S1711, the CPU in the RIP 216 determines whether all the PDL processes for all input pages have been completed. If it is determined that all the input PDL processes for all pages have been completed, the process proceeds to step S1712, and if it is determined that all the input PDL processes for all pages have not been completed, the process is Return to step S1704.

PDLのレンダリング処理は、ステップS1712で終了する。   The PDL rendering process ends in step S1712.

<フォールバックにおける重ね合わせ処理>
ここで、図17のステップS1707のページ重ね合わせ処理について説明する。フォールバックにおけるページ重ね合わせ処理では、1ページ分のレンダリング画像が生成される際、レンダリング処理部は、生成したビットマップを圧縮してデータサイズを小さくし、圧縮後のビットマップを背景イメージのDLとして、DLメモリに格納する。換言すると、領域情報が送られたディスプレイリスト生成部は、圧縮されたビットマップが背景として含まれるように次のディスプレイリストを生成する。ディスプレイリストに背景画像が含まれている場合、レンダリング処理部は、圧縮画像を展開して背景画像として現在処理中のディスプレイリストのレンダリング時に重ね合わせ処理を行う。
<Overlay processing in fallback>
Here, the page overlay processing in step S1707 of FIG. 17 will be described. In the page overlay processing in fallback, when a rendering image for one page is generated, the rendering processing unit compresses the generated bitmap to reduce the data size, and the compressed bitmap is converted to the background image DL. Is stored in the DL memory. In other words, the display list generation unit to which the region information is sent generates the next display list so that the compressed bitmap is included as the background. When the display list includes a background image, the rendering processing unit expands the compressed image and performs a superimposition process when rendering the display list currently being processed as a background image.

一方、上述した図8のステップS814やステップS817では、生成されたレンダリング画像はレンダリング処理部で圧縮されず保持され、次のグループのレンダリング時に下位グループのレンダリング画像と重ね合わせを行う。したがって、この点において、フォールバックにおける重ね合わせ処理と、上述した図8のステップS814やステップS817におけるコンポジット処理とは異なる。   On the other hand, in step S814 and step S817 in FIG. 8 described above, the generated rendering image is held without being compressed by the rendering processing unit, and is superimposed on the rendering image of the lower group when rendering the next group. Therefore, in this respect, the overlay process in the fallback is different from the composite process in step S814 or step S817 in FIG. 8 described above.

<他の実施形態>
以上、様々な実施形態を詳述したが、本発明は、複数の装置から構成されるシステムに適用してもよいし、また、一つの装置に適用してもよい。例えば、スキャナ、プリンタ、PC、複写機、複合機、及びファクシミリ装置並びにこれらを組み合わせたシステムに対して、本発明を適用することができる。
<Other embodiments>
Although various embodiments have been described in detail above, the present invention may be applied to a system constituted by a plurality of devices, or may be applied to a single device. For example, the present invention can be applied to a scanner, a printer, a PC, a copier, a multifunction peripheral, a facsimile machine, and a system combining these.

本発明は、前述した実施形態の各機能を実現するソフトウェアプログラムを、システム若しくは装置に対して直接又は遠隔から供給し、そのシステム等に含まれるコンピュータが該供給されたプログラムコードを読み出して実行することによっても達成される。   The present invention supplies a software program that implements the functions of the above-described embodiments directly or remotely to a system or apparatus, and a computer included in the system reads and executes the supplied program code. Can also be achieved.

従って、本発明の機能・処理をコンピュータで実現するために、該コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、上記機能・処理を実現するためのコンピュータプログラム自体も本発明の一つの態様である。   Accordingly, since the functions and processes of the present invention are implemented by a computer, the program code itself installed in the computer also implements the present invention. That is, the computer program itself for realizing the functions and processes is also one aspect of the present invention.

その場合、コンピュータプログラムはプログラムの機能を有してさえいればよく、オブジェクトコード、インタプリタにより実行されるプログラム、OSに供給するスクリプトデータ等、プログラムの形態を問わない。   In that case, the computer program only needs to have the function of the program, and the form of the program such as an object code, a program executed by an interpreter, script data supplied to the OS, etc. is not limited.

プログラムを供給するための記録媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、MO、CD−ROM、CD−R、CD−RW等がある。また、記録媒体としては、磁気テープ、不揮発性のメモリカード、ROM、DVD(DVD−ROM、DVD−R)等もある。   Examples of the recording medium for supplying the program include a flexible disk, hard disk, optical disk, magneto-optical disk, MO, CD-ROM, CD-R, and CD-RW. Examples of the recording medium include a magnetic tape, a nonvolatile memory card, a ROM, a DVD (DVD-ROM, DVD-R), and the like.

また、プログラムは、クライアントコンピュータのブラウザを用いてインターネット/イントラネットのウェブサイトからダウンロードしてもよい。すなわち、該ウェブサイトから本発明のコンピュータプログラムそのものを若しくは圧縮され自動インストール機能を含むファイルをハードディスク等の記録媒体にダウンロードしてもよい。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるウェブサイトからダウンロードすることによっても、本発明を実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるWWWサーバも、本発明の構成要件となる場合がある。   The program may be downloaded from an Internet / intranet website using a browser of a client computer. That is, the computer program itself of the present invention or a compressed file including an automatic installation function may be downloaded from the website onto a recording medium such as a hard disk. The present invention can also be realized by dividing the program code constituting the program of the present invention into a plurality of files and downloading the respective files from different websites. That is, a WWW server that allows a plurality of users to download a program file for realizing the functional processing of the present invention on a computer may be a constituent requirement of the present invention.

また、本発明のプログラムを暗号化してCD−ROM等の記憶媒体に格納してユーザに配布してもよい。この場合、所定条件をクリアしたユーザにのみ、インターネット/イントラネットを介してウェブサイトから暗号化を解く鍵情報をダウンロードさせ、その鍵情報で暗号化されたプログラムを復号して実行し、プログラムをコンピュータにインストールしてもよい。   Further, the program of the present invention may be encrypted and stored in a storage medium such as a CD-ROM and distributed to users. In this case, only the user who has cleared the predetermined condition is allowed to download the key information to be decrypted from the website via the Internet / intranet, decrypt the program encrypted with the key information, and execute the program. You may install it on

また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現されてもよい。なお、そのプログラムの指示に基づき、コンピュータ上で稼動しているOSなどが、実際の処理の一部又は全部を行ってもよい。もちろん、この場合も、前述した実施形態の機能が実現され得る。   Further, the functions of the above-described embodiments may be realized by the computer executing the read program. Note that an OS or the like running on the computer may perform part or all of the actual processing based on the instructions of the program. Of course, also in this case, the functions of the above-described embodiments can be realized.

さらに、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれてもよい。そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるCPU等が実際の処理の一部又は全部を行ってもよい。このようにして、前述した実施形態の機能が実現されることもある。   Furthermore, the program read from the recording medium may be written in a memory provided in a function expansion board inserted into the computer or a function expansion unit connected to the computer. Based on the instructions of the program, the CPU or the like provided in the function expansion board or function expansion unit may perform part or all of the actual processing. In this way, the functions of the above-described embodiments may be realized.

Claims (9)

ディスプレイリストに対するビットマップを生成してレンダリング処理を実行する画像処理装置であって、
ディスプレイリストを解釈しオブジェクトをロードするロード手段と、
当該ロードしたオブジェクトが不透過であり現在把握しているオブジェクトより上位であるか否か判定する判定手段と、
前記ロードしたオブジェクトが不透過であり現在把握しているオブジェクトより上位である場合に、ロードしたオブジェクトの属するグループのグループナンバー及び現在処理中のスキャンラインにおける当該オブジェクトの左右のエッジの座標を保持する保持手段と、
コンポジット処理がグループ間のコンポジット処理であり、現在把握している最上位のオブジェクトが属するグループより下位のグループ同士で実行される場合に、前記左右のエッジの座標で表される区間内でコンポジット処理をスキップするスキップ手段と
を備えたことを特徴とする画像処理装置。
An image processing device that generates a bitmap for a display list and executes a rendering process,
Loading means to interpret the display list and load the object;
A determination means for determining whether the loaded object is opaque and is higher than the currently grasped object;
When the loaded object is opaque and is higher than the currently grasped object, the group number of the group to which the loaded object belongs and the coordinates of the left and right edges of the object in the currently processed scan line are stored. Holding means;
When the composite process is a composite process between groups and is executed between groups lower than the group to which the highest-level object currently grasped belongs, the composite process is performed within the section represented by the coordinates of the left and right edges. An image processing apparatus comprising: skipping means for skipping.
前記判定手段は、前記ロードしたオブジェクトが台形であるか否かを、エッジの傾きに基づいて判定し、
前記保持手段は、前記ロードしたオブジェクトが不透過且つ台形であり現在把握しているオブジェクトより上位である場合に、前記ロードしたオブジェクトの属するグループのグループナンバー及び当該オブジェクトの左右のエッジの座標を保持する
ことを特徴とする請求項1に記載の画像処理装置。
The determination means determines whether or not the loaded object is a trapezoid based on an inclination of an edge,
The holding means holds the group number of the group to which the loaded object belongs and the coordinates of the left and right edges of the object when the loaded object is opaque and trapezoidal and is higher than the currently grasped object. The image processing apparatus according to claim 1, wherein:
エッジ処理においてキャッシュミスヒットが発生しないエッジ数を算出し、当該算出したエッジ数に基づいてエッジを分割するグループの数を算出する手段と、
当該算出したグループの数に基づいてエッジをグループ毎に分割するか否か判定する手段と
を更に備えたことを特徴とする請求項1に記載の画像処理装置。
Means for calculating the number of edges in which a cache miss hit does not occur in edge processing, and calculating the number of groups into which edges are divided based on the calculated number of edges;
The image processing apparatus according to claim 1, further comprising: a unit that determines whether to divide the edge into groups based on the calculated number of groups.
前記判定手段は、前記ロードしたオブジェクトが不透過且つ矩形であり現在把握しているオブジェクトより上位であるか否か判定し、
前記保持手段は、前記ロードしたオブジェクトが不透過且つ矩形であり現在把握しているオブジェクトより上位である場合に、ロードしたオブジェクトの属するグループのグループナンバー及び現在処理中のスキャンラインにおける当該オブジェクトの左右のエッジの座標を保持する
ことを特徴とする請求項1に記載の画像処理装置。
The determination means determines whether the loaded object is opaque and rectangular and is higher than the currently grasped object,
When the loaded object is opaque and rectangular and is higher than the currently grasped object, the holding means includes the group number of the group to which the loaded object belongs and the right and left of the object in the scan line currently being processed. The image processing apparatus according to claim 1, wherein coordinates of edges of the image are held.
前記ロードしたオブジェクトが不透過であり現在把握しているオブジェクトより上位である場合に、グループ間のコンポジットスキップ処理の対象となる区間の数が保持できる個数以内であるか否かを判定する手段と、
グループ間のコンポジットスキップ処理の対象となる区間の数が保持できる個数以内ではない場合に、保持しているオブジェクトの中で最も背面に近いオブジェクトに関するデータを削除して、当該ロードしたオブジェクトに関するデータを登録する手段と
を更に備えたことを特徴とする請求項1に記載の画像処理装置。
Means for determining whether or not the number of sections subject to composite skip processing between groups is within a holdable number when the loaded object is opaque and is higher than the currently known object; ,
If the number of sections subject to composite skip processing between groups is not within the number that can be retained, delete the data related to the object closest to the back of the objects held, and the data related to the loaded object The image processing apparatus according to claim 1, further comprising: a registering unit.
前記ロードしたオブジェクトが不透過であり現在把握しているオブジェクトより上位である場合であって、前記ロードしたオブジェクトの大きさが所定の大きさより大きい場合に、前記保持手段は、前記ロードしたオブジェクトの属するグループのグループナンバー及び現在処理中のスキャンラインにおける当該オブジェクトの左右のエッジの座標を保持することを特徴とする請求項1に記載の画像処理装置。   If the loaded object is opaque and is higher than the currently known object, and the size of the loaded object is greater than a predetermined size, the holding means The image processing apparatus according to claim 1, wherein the group number of the group to which the image belongs and the coordinates of the left and right edges of the object in the scan line currently being processed are held. エッジ処理が、左右のエッジの座標を保持しているオブジェクトのエッジ処理である場合に、現在処理中のスキャンラインの次のスキャンラインにおける当該オブジェクトの左右のエッジの座標を保持する手段を更に備えたことを特徴とする請求項1に記載の画像処理装置。   When the edge process is an edge process of an object that holds the coordinates of the left and right edges, the apparatus further comprises means for holding the coordinates of the left and right edges of the object in the scan line next to the scan line currently being processed The image processing apparatus according to claim 1. ディスプレイリストに対するビットマップを生成してレンダリング処理を実行する画像処理方法であって、
ディスプレイリストを解釈しオブジェクトをロードするステップと、
当該ロードしたオブジェクトが不透過であり現在把握しているオブジェクトより上位であるか否か判定するステップと、
前記ロードしたオブジェクトが不透過であり現在把握しているオブジェクトより上位である場合に、ロードしたオブジェクトの属するグループのグループナンバー及び現在処理中のスキャンラインにおける当該オブジェクトの左右のエッジの座標を保持するステップと、
コンポジット処理がグループ間のコンポジット処理であり、現在把握している最上位のオブジェクトが属するグループより下位のグループ同士で実行される場合に、前記左右のエッジの座標で表される区間内でコンポジット処理をスキップするステップと
を備えたことを特徴とする画像処理方法。
An image processing method for generating a bitmap for a display list and executing a rendering process,
Interpreting the display list and loading the object;
Determining whether the loaded object is opaque and higher than the currently known object;
When the loaded object is opaque and is higher than the currently grasped object, the group number of the group to which the loaded object belongs and the coordinates of the left and right edges of the object in the currently processed scan line are stored. Steps,
When the composite process is a composite process between groups and is executed between groups lower than the group to which the highest-level object currently grasped belongs, the composite process is performed within the section represented by the coordinates of the left and right edges. An image processing method comprising: a step of skipping.
コンピュータを請求項1乃至7の何れか1項に記載の画像処理装置として機能させるためのプログラム。   A program for causing a computer to function as the image processing apparatus according to any one of claims 1 to 7.
JP2013210458A 2013-10-07 2013-10-07 Image processing apparatus, image processing method, and program Pending JP2015075839A (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP2013210458A JP2015075839A (en) 2013-10-07 2013-10-07 Image processing apparatus, image processing method, and program

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2013210458A JP2015075839A (en) 2013-10-07 2013-10-07 Image processing apparatus, image processing method, and program

Publications (1)

Publication Number Publication Date
JP2015075839A true JP2015075839A (en) 2015-04-20

Family

ID=53000674

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2013210458A Pending JP2015075839A (en) 2013-10-07 2013-10-07 Image processing apparatus, image processing method, and program

Country Status (1)

Country Link
JP (1) JP2015075839A (en)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2018063557A (en) * 2016-10-12 2018-04-19 キヤノン株式会社 Image forming device, method, and program
JP2019010817A (en) * 2017-06-30 2019-01-24 キヤノン株式会社 Image processing apparatus, image processing method, and program

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2018063557A (en) * 2016-10-12 2018-04-19 キヤノン株式会社 Image forming device, method, and program
JP2019010817A (en) * 2017-06-30 2019-01-24 キヤノン株式会社 Image processing apparatus, image processing method, and program

Similar Documents

Publication Publication Date Title
US8274667B2 (en) Image processing apparatus, control method thereof, and storage medium storing a program for converting raster image data into block vector image format
JP4995057B2 (en) Drawing apparatus, printing apparatus, drawing method, and program
US7680358B2 (en) Image processing apparatus and control method thereof, and program
JP5209953B2 (en) Image data supply apparatus and image data supply method
US8466921B2 (en) Image processing apparatus and method for load balancing of plural types of image processing in plural processors
US8339664B2 (en) Image processing method, image processing apparatus, and control method thereof
US20090303550A1 (en) Image processing apparatus and image processing method
US8223387B2 (en) Image data processor and image data processing program storage medium
US6975416B2 (en) Print control apparatus and method
US9443174B2 (en) Image processing apparatus, image processing method, and storage medium
JP5644214B2 (en) Print control program, information processing apparatus, storage medium, printing apparatus, printing system
JP2015075839A (en) Image processing apparatus, image processing method, and program
JP6135329B2 (en) Print data processing apparatus, program, and system
KR20170099211A (en) Method for enhancing quality of image object included in compound document and apparatus for performing the same
JP4461361B2 (en) Drawing processing method and program, drawing command output device and image forming apparatus
JP6904717B2 (en) Image processing equipment, its control method, and programs
JP2014194635A (en) Image forming apparatus, image forming method, and program
JP2008107970A (en) Image forming device
JP4475680B2 (en) Image processing apparatus, control method therefor, and program
JP2016206934A (en) Image processing device, image processing method and program
JP2010111099A (en) Image processing apparatus and its control method
US8756491B2 (en) PDL data processing device
JP4398361B2 (en) OUTPUT CONTROL DEVICE, OUTPUT CONTROL METHOD, PROGRAM, AND RECORDING MEDIUM
JP2019111677A (en) Image processing device, image processing device control method, image forming device and program
JP2006031160A (en) Graphic object processing method