生成圖形目標的方法
2023-08-07 09:02:36
專利名稱：生成圖形目標的方法
技術領域：
本發明總體上涉及生成基於目標的圖像。具體而言，本發明涉及使用多個生成技術的生成圖形目標的方法。
背景技術：
當計算機應用向用於列印和/或顯示的設備提供數據時，經常把頁面的中間描述提供給在頁面描述語言(PDL)中的設備驅動程序軟體，頁面描述語言提供了將在該頁或顯示器上生成的圖形目標的說明。這一些裝置完全不同，在它們中直接由應用程式產生光柵圖象數據並且傳送以列印或顯示。頁數描述語言的例子包括Canon的LIPSTM和HP的PCLTM。
同樣，應用程式可向例如MicrosoftTMWindows GDI的圖形設備接口層提供在函數調用中的圖形目標的一套描述。用於相關目標印表機的印表機驅動程序是從GDI層接收圖形目標描述的軟體。對於每個目標，印表機驅動程序負責以可由目標印表機的生成系統理解的頁面描述語言產生目標的說明。
印表機的生成系統包含PDL解釋器，解釋器解析圖形目標描述，並且建立圖形目標數據的顯示列表。生成系統也包含光柵圖象處理器(RIP)，其處理顯示列表並且將數據生成為包括例如C，M，Y和K信道的像素值。一旦處於此格式，印表機列印頁面。
大多數RIP利用大量的存儲器，如眾所周知的幀存儲或頁緩衝區，保存用於後續印刷和/或顯示的頁或屏幕的基於像素的圖像數據說明。一般地，計算圖形目標的輪廓，用色值充滿輪廓並且將它們寫到幀存儲。對於二維的圖形，簡單地將出現在其它目標前面的目標寫到在背景目標之後的幀存儲裡，從而在一個像素接一個像素的基礎上替換背景目標。這通常稱為「畫具算法(Painter’salgorithm)」。以優先順序考慮從最後的到最前的目標。一般地以掃描線順序光柵掃描(rasterized)每個目標，並且在沿著每個掃描線連續的運行把像素寫到幀存儲。一些RIP允許目標與其它目標合成。例如邏輯或算術運算可以指定並且在一個或多個圖形目標和在幀存儲中已經生成的像素之間執行。在這種情況下，生成原則保持不變按掃描線順序光柵掃描目標(或目標組)，而且在沿著每個掃描線的連續運行，計算指定操作的結果，並把結果寫到幀存儲中。
畫具運算生成法存在許多問題。一個問題是當生成後來的目標時通過生成一個目標而寫到幀存儲的許多像素將被重寫。很清楚在使用資源將像素數據寫到後來將重寫的幀存儲裡時存在不利情況。
另一個問題是當目標要求合成時，一般地從幀存儲中讀取目標下的像素，並且把它們以某種方式與目標像素合併。如果幀存儲中的像素保存在比要求合成的目標更低的位深(bit-depth)，則大多數的合成操作產生不正確的結果。當例如圖形目標是每個信道8位的RGBA位圖且幀存儲保留每個信道一位的半色調像素數據時是這種情況。這可以發生，因為像素值經常以印刷所需的位深保存在幀存儲中。儘管有可能以每個信道全8位來存儲像素，每個信道8位的RGBA幀存儲在600dpi解析度對於一張A4頁面要求大於100MB的存儲器。此外，一旦頁面生成為每個信道8位的幀存儲，必須把它轉換到更低的位深以便列印，這是低效的。
其它RIP利用像素順序生成方法，以便不再需要幀存儲，並且克服過度著色的問題。在這些系統，以光柵順序產生每一個像素。將更繪圖的所有目標保持在顯示列表中。在每個掃描線上，以與掃描線相交的遞增順序來保存與掃描線相交的目標的邊緣。按順序考慮這些相交點，或邊緣交叉線，並且激活或停用在顯示列表中的目標。在考慮的每一對邊緣之間，根據哪些目標沒有由不透明目標模糊化(像素-流程)，為像素的間隔產生位於第一個邊緣和第二邊緣之間的用於每一個像素的顏色數據。在下一個掃描線的準備中，根據每個邊緣的性質更新每個邊緣的相交的坐標，並且把邊緣排序成與那個掃描線相交的遞增順序。此外任何新的邊緣也合併到邊緣列表裡，它被稱作有效邊緣列表。在本說明中，僅僅在一個像素流程中生成沒有由不透明目標模糊化的目標生成方法稱為「像素順序生成方法」。
利用這樣的像素順序生成的圖形系統具有顯著優勢，因為沒有幀存儲或行存貯，且沒有不必要的過度繪圖。在每個像素基礎上使用每個目標的初始顏色數據處理要求合成的目標。
當必須為每個掃描線跟蹤大量邊緣並且把它們保持在由x升序排序順序時，像素順序生成遭遇困難。因為在掃描線中更新每個邊緣，所以通常通過插入排序將邊緣再插入活動邊緣列表中。對於可能包括幾十萬個邊緣的複雜頁面，為每個掃描線保持邊緣排序表所更求的時間變為佔生成複雜頁面的總時間的一大部分。
發明內容
本發明的一個目標是基本上克服，或至少改善，現有裝置的一或多種不利情況。
根據本發明的第一方面，提供了生成由一個圖形目標列表描述的圖像的方法，該方法包括步驟把列表中的目標分配到第一目標集合和第二目標集合中的至少一個；使用第一生成方法生成第一目標集合到圖像存儲器，該第一生成方法確定第一集合中一個目標的一部分是否貢獻於第一目標集合的生成的輸出，並且如果是的話，第一生成方法生成該部分；和使用第二生成方法生成第二目標集合到圖像存儲，第二生成方法獨立於第二集合中的其他目標來生成第二組中的每個目標。
根據本發明的進一步的方面，提供了一種生成基於目標的圖像的方法，該方法包括步驟接收顯示列表，該列表按從最低優先級目標到最高優先級目標的優先順序列出圖像的目標，其中顯示列表具有要求合成的最高優先級目標的最後的合成目標；處理第一生成任務，第一生成任務操作顯示列表中從最低優先級目標直到最後合成目標的目標；和處理至少一個第二生成任務，該任務操作具有比最後合成目標更高優先級的顯示列表中的一個或多個目標，其中第一生成任務確定目標的一部分是否貢獻於由第一生成任務處理的目標的生成的輸出，並且如果是的話，生成該部分，並且其中第二生成任務獨立於由第二生成任務處理的其它目標，生成目標到圖像存儲。
根據本發明的另外方面，提供了生成由表示為圖形目標的數據來描述的圖像的方法，該方法包括步驟(a)接收描述圖像的目標列表，其中按從最低優先級目標到最高優先級目標的優先順序對目標排序；(b)按遞增優先級的順序考慮列表中的目標，並且對於每個當前考慮的目標這樣處理(ba)如果當前考慮的目標不要求合成，使用第一生成方法生成當前考慮的目標到圖像存儲；並且(bb)如果當前考慮的目標要求合成，執行下列步驟(bb)(i)確定列表中具有比當前考慮的目標更低優先級並且具有與當前考慮的目標的邊界框重疊的邊界框的目標；以及bb(ii)使用第二生成方法生成當前考慮的目標和已經確定的目標，該第二生成方法確定一個目標的一部分是否貢獻於由第二生成方法處理的目標集合的生成的輸出，如果是的話，該第二生成方法生成該部分。
根據本發明的進一步的方面，提供了生成基於目標的圖像的方法，該方法包括步驟(a)接收顯示列表，該列表按從最低優先級目標到最高優先級目標的優先順序列出圖像中的目標；(b)根據至少一個預定的標準，把列表中的目標分配到第一目標集合和第二目標集合中的至少一個；(c)使用第一生成方法生成第一目標集合中的目標；並且(d)使用第二生成方法生成第二目標集合中的目標，其中，對於每輪將要生成的順序像素，第一生成方法包括下列步驟(ca)確定第一目標集合中的對於像素的流程是有效的目標；(cb)識別具有已確定的有效目標的最高優先級的不透明目標；以及(cc)生成最高級的不透明目標和具有比最高級的不透明目標更高優先級的非不透明的有效目標；而且其中，對於每輪將要生成的順序像素，第二生成方法包括下列步驟(da)檢查第二目標集合中的當前目標是否是有效的，第二目標集合是按遞增優先級順序考慮的；和(db)如果當前目標是有效的，生成當前目標到圖像存儲。
根據本發明其它方面，提供了生成基於目標的圖像的方法，該方法包括步驟按從最低優先級目標到最高優先級目標的優先順序接收圖像中的目標列表；將列表中的目標分配到至少一個目標集合中，其中集合中的目標在列表中具有連續的優先順序，且其中集合中的每個目標不與集合中的任何其它目標重疊；生成至少一個目標集合到圖像存儲。
根據本發明的進一步方面，提供了生成由一個圖形目標列表描述的圖像的方法，該方法包括步驟把列表中的目標分配到第一目標集合和第二目標集合中的至少一個；使用像素順序生成方法生成第一集合中的目標；並且使用畫具運算生成法生成在第二集合中的目標。
根據本發明的另一個方面，提供了用於生成由一個圖形目標列表描述的圖像的設備，該設備包括第一裝置，使用第一生成方法生成目標到圖像存儲，該第一生成方法確定目標的一部分是否貢獻於由所述第一裝置處理的目標集合的生成的輸出，如果是的話，所述第一裝置生成該部分；第二裝置，使用第二生成方法生成目標到圖像存儲，該第二方法獨立於由所述的第二裝置接收到的其它目標來生成由所述第二裝置接收的每個目標；以及用於把列表中的圖形目標分配到所述第一裝置和所述第二裝置中的至少一個的裝置。
根據本發明的另一個方面，提供了用於生成基於目標的圖像的設備，該設備包括第一裝置，使用第一生成方法生成目標到圖像存儲，該第一生成方法確定目標的一部分是否貢獻於由所述第一裝置處理的目標集合的生成的輸出，如果是的話，所述第一裝置生成該部分；第二裝置，使用第二生成方法生成目標到圖像存儲，該第二生成方法獨立於由所述第二裝置接收到的其它目標生成由所述第二裝置接收到的每個目標；用於接收圖像中的目標列表的裝置，其中按從最低優先級目標到最高優先級目標的優先順序對列表中的目標排序，並且列表具有最後合成的目標，即要求合成的最高優先級的目標；裝置，用於把目標分配到所述用於生成的第一裝置，和所述用於生成的第二裝置，其中所述用於分配的裝置把從最低優先級目標直到最後合成目標的列表的第一部份分配到所述用於生成的第一裝置，並且將一個或多個優先級高於最後合成目標的目標分配到所述用於生成的第二裝置。
根據本發明的其他方面，提供了用於生成基於目標的圖像的設備，該設備包括第一裝置，使用第一生成方法生成目標到圖像存儲，該第一生成方法確定目標的一部分是否貢獻於由所述第一裝置處理的目標集合的生成的輸出，如果是的話，所述第一裝置生成該部分；第二裝置，使用第二生成方法生成目標到圖像存儲，該第二生成方法獨立於其它接收的目標生成由所述第二裝置接收到的每個目標；用於接收圖像中的目標列表的裝置，其中按從最低優先級目標到最高優先級目標的優先順序對目標排序；用於對於一個要求合成的目標確定列表中的目標的裝置，這些目標具有比合成目標更低優先級且具有與合成目標的邊界框重疊的邊界框；用於把非合成目標從列表中分配到用於生成的第二裝置的裝置；和用於從列表中把合成目標的裝置，以及由所述用於確定的裝置為每個合成目標確定的目標分配到用於生成的第一裝置。
根據本發明的其他方面，提供了用於生成基於目標的圖像的設備，該設備包括用於按從最低優先級目標到最高優先級目標的優先順序接收圖像中的目標列表的裝置；用於將列表中的目標分配到至少一個目標集合的裝置，其中集合中的目標在列表中具有連續的優先順序，且其中集合中的每個目標不與集合中的任何其它目標重疊；以及用於生成至少一個目標集合到圖像存儲的裝置。
根據本發明的另一個方面，提供了用於生成基於目標的圖像的系統，該系統包括一個或多個第一生成器，使用第一生成方法生成目標到圖像存儲，該第一生成方法確定目標的一部分是否貢獻於由所述第一裝置處理的目標集合的生成的輸出，如果是的話，所述第一裝置生成該部分；一個或多個第二生成器，使用第二生成方法生成目標到圖像存儲，該第二方法獨立於其它接收的目標來生成由所述第二裝置接收的每個目標；一個顯示列表發生器，產生用於圖像的目標列表，其中按從最低優先級目標到最高優先級目標的優先順序對列表中的目標排序，並且列表具有最後的合成目標，其是要求合成的最高優先級目標；顯示列表存儲器，存儲由所述顯示列表發生器產生的列表；和與所述顯示列表存儲器和所述第一和第二生成器通信的處理器，其中將處理器編程為把從最低優先級目標直到最後合成目標的目標分配到第一生成器中，並且把具有比最後的合成目標更高優先級的目標分配到一個或多個第二生成器。
根據本發明的另外一個方面，提供了用於生成基於目標的圖像的系統，該系統包括一個或多個第一生成器，使用第一生成方法生成目標到圖像存儲，該第一生成方法確定目標的一部分是否貢獻於由第一生成方法處理的一個目標集合的生成的輸出，並且，如果是的話，第一生成方法生成該部分；一個或多個第二生成器，使用第二生成方法生成目標到圖像存儲，該第二方法獨立於其它接收的目標來生成由所述第二裝置接收的每個目標；顯示列表發生器，產生圖像中的一個目標列表，其中按從從最低優先級目標到最高優先級目標的優先順序對列表中的目標排序；顯示列表存儲器，存儲由所述顯示列表發生器產生的列表；以及與所述顯示列表存儲器和所述第一和第二生成器通信的處理器，其中處理器被編程為執行下列步驟(i)按優先級遞增的順序考慮列表中的目標，並且，對優於每個當前考慮的目標這樣處理(ii)如果當前目標不要求合成，將當前目標分配分配到第二生成器；和(iii)如果當前目標要求合成，確定列表中比當前考慮的目標具有更低優先級，並且具有與當前考慮的目標的邊界框重疊的邊界框的目標，並且把當前考慮的目標和確定的目標分配到第一生成器。
根據本發明的另一個方面，提供了包括記錄在機讀記錄介質上的機讀程序代碼的電腦程式產品，用於控制數據處理設備的操作，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟把列表中的目標分配到第一目標集合和第二目標集合中的至少一個；使用第一生成方法生成目標到圖像存儲，該第一生成方法確定第一集合的一個目標的一部分是否貢獻於目標第一集合的生成的輸出，並且，如果是的話，第一生成方法生成該部分；以及使用第二生成方法生成第二目標集合到圖像存儲，該第二方法獨立於第二集合中的其它目標來生成由所述第二裝置接收的每個目標。
根據本發明進一步的方面，提供了包括記錄在機讀記錄介質上的機讀程序代碼的電腦程式產品，用於控制數據處理設備的操作，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟接收顯示列表，其按從最低優先級目標到最高優先級目標的優先順序列出圖像中的目標，其中顯示列表具有最後的合成目標，即要求合成的最高優先級的目標；使用第一生成方法生成第一生成任務，第一個生成任務包括從最低優先級目標直到最後合成目標的顯示列表中的目標；並且使用第二生成方法生成一個或多個第二生成任務，第二生成任務包括顯示列表中具有比最後合成目標更高優先級的一個或多個目標，其中第一生成方法確定目標的一部分是否貢獻於第一生成任務的生成輸出，如果是這樣的話，第一生成的方法生成該部分，並且其中第二生成方法獨立於第二生成任務中的其它目標生成第二生成任務中的每個目標到圖像存儲器。
根據本發明更進一步的方面，提供了一個電腦程式產品，包括記錄在機讀記錄介質上的機讀程序代碼，用於控制該數據處理設備的操作，在數據處理設備上執行基於目標的圖像的生成方法，該方法包括步驟(a)接收描述圖像的目標列表，其中按從最低優先級目標到最高優先級目標的優先順序對目標排序；(b)按優先級遞增的順序考慮列表中的目標，並且，對於每個當前考慮的目標這樣處理
(ba)如果當前考慮的目標不要求合成，使用第一生成方法生成當前考慮的目標到圖像存儲；並且(bb)如果當前考慮的目標要求合成，執行下列步驟(bb)(i)確定列表中具有比當前考慮的目標更低優先級並且具有與當前考慮的目標的邊界框重疊的邊界框的目標；和(bb)(ii)使用第二生成方法生成當前考慮的目標和確定的目標，該第二生成方法確定目標的一部分是否貢獻於由第二生成方法處理的目標集合的生成輸出，並且，如果這樣的話，第二生成方法生成該部分。
根據本發明進一步的方面，提供了包括記錄在機讀記錄介質上的機讀程序代碼的電腦程式產品，用於控制數據處理設備的操作，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟按從最低優先級目標到最高優先級目標的優先順序接收圖像中目標的列表；分配列表中的目標到至少一組目標，其中集合中的目標在列表中具有連續的優先順序，而且其中集合中的每個目標不與集合中任何其它目標重疊；生成至少一個目標集合到圖像存儲。
根據本發明進一步的方面，提供了包括記錄在機讀記錄介質上的機讀程序代碼的電腦程式產品，用於控制數據處理設備的操作，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟把列表中的目標分配到第一目標集合和第二目標聚合中的至少一個；使用第一生成方法生成第一目標集合到圖像存儲器，該第一生成方法確定第一集合中的目標的一部分是否貢獻於第一集合的生成輸出，並且如果是的話，第一生成方法生成該部分；以及使用第二生成方法生成第二目標集合到圖像存儲，該第二生成方法獨立於第二集合中的其它目標生成第二集合中的每個目標。
根據本發明進一步的方面，提供了包括機讀程序代碼的電腦程式，用於控制數據處理設備的操作，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟接收顯示列表，該列表按從最低優先級目標到最高優先級目標的優先順序列出圖像中的目標，其中顯示列表具有最後合成目標，即要求合成的最高優先級的目標；使用第一生成方法生成第一生成任務，第一個生成任務包括從最低優先級目標直到最後合成目標的顯示列表中的目標；並且使用第二生成方法生成一個或多個第二生成任務，第二生成任務包括顯示列表中具有比最後合成目標更高優先級的一個或多個目標，其中第一生成方法確定目標的一部分是否貢獻於第一生成任務的生成輸出，如果是的話，第一生成方法生成該部分，並且其中第二生成方法獨立於第二生成任務中的其它目標，生成第二生成任務中的每個目標到圖像存儲器。
根據本發明進一步的方面，提供了包括用於控制數據處理設備操作的機讀程序代碼的電腦程式，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟(a)接收描述圖像的目標列表，其中按從最低優先級目標到最高優先級目標的優先順序對目標排序；(b)按遞增優先級的順序來考慮列表中的目標，並且，對於每個當前考慮的目標這樣處理(ba)如果當前考慮的目標不要求合成，使用第一生成方法生成當前考慮的目標到圖像存儲；並且(bb)如果當前考慮的目標要求合成，執行下列步驟(bb)(i)確定列表中具有比當前考慮的目標更低優先級，並且具有與當前考慮的目標的邊界框重疊的邊界框的目標；和(bb)(ii)使用第二生成方法生成當前考慮的目標和確定的目標，第二生成方法確定目標的一部分是否貢獻於由第二生成方法處理的目標集合的生成輸出，並且，如果是的話，第二生成方法生成該部分。
根據本發明進一步的方面，提供了包括用於控制數據處理設備操作的機讀程序代碼的電腦程式，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟按從最低優先級目標到最高優先級目標的優先順序接收圖像中目標的列表；分配列表中的目標到至少一個目標集合，其中集合中的目標在列表中具有連續的優先順序，而且其中集合中的每個目標不與集合中任何其它目標相重疊；生成至少一個目標集合到圖像存儲。
現在參考
本發明的一個或多個實施例，其中圖1A是一個顯示在不透明字符「O」上的半透明正方形的圖像的例子；圖1B顯示了圖1A的目標的邊緣；圖1C顯示了圖1A的例子的邊緣列表的示意框圖；圖2是用於確定主邊緣列表的有效邊緣，並且確定應當為其生成的有效邊緣的集合的掃描線的數目的方法的流程圖；圖3A是用於通過由圖2的方法步驟計算的有效邊緣生成掃描線方法的流程圖；圖3B是用於通過由圖2的方法步驟計算的有效邊緣生成掃描線的另一種方法的流程圖；圖4是用於確定在像素順序生成法中哪些目標在像素運行中起作用的方法的流程圖；圖5A顯示了邊界框重疊的兩個目標；圖5B顯示了邊界框不重疊的兩個目標；圖6A顯示了其中兩個三角形剪片剪切矩形的圖片的例子；圖6B顯示了生成圖6A的矩形和剪片的結果；圖6C顯示了圖6A的目標的邊緣；圖6D顯示在圖6A的目標的存儲器中的顯示列表的示意表示；圖7是用於在像素順序生成方法中考慮到剪切確定是否激活或停用目標的方法的流程圖；圖8是用於在改進的畫具運算生成(PARM)中確定哪些目標貢獻於像素的方法的流程圖；圖9(a)和9(b)顯示了說明在為第二和第三裝置生成顯示列表期間如何構造目標表方法的流程圖；圖10A顯示在一個頁面上具有五個目標的圖像；圖10B，10C和10D顯示如何在三個生成任務中生成圖10A的目標；
圖10E顯示在兩個頻帶中生成的10A的頁面；圖11A是顯示目標頁面的示意圖；圖11B顯示了使用專用像素順序生成方法(XPSRM)生成的圖11A的目標；圖11C顯示靠近掃描線S的圖11A的目標的邊緣；圖12是用於激活目標的方法的流程圖，其顯示了當激活目標時如何在XPSRM中增加激活的目標列表中的ExclusiveCount成員，並且當停用目標時減縮；圖13是用於確定在XPSRM中哪些目標貢獻於像素運行的方法流程圖；圖14是使用像素順序生成方法和畫具運算生成法(PSRM和PARM)的第一生成裝置的流程圖；圖15是生成流水線(render pipeline)的示意框圖，在生成流水線中可以實現本公開的生成裝置；圖16是使用像素順序生成方法和改進的畫具運算生成法(PSRM和IPARM)的第二生成裝置的流程圖；圖17是使用專用的像素順序生成方法和改進的畫具運算生成法(XPSRM和IPARM)的第三生成裝置的流程圖；和圖18是說明包括生成裝置的計算機系統的示意性框圖。
表格說明根據在詳細說明書的結尾和權利要求之前的列出的表格列表說明本發明的實施例。
表格A說明了如何將圖2的方法用於圖1所述的實例。
表B說明了如何將圖3A的方法用於圖1A所述實例的掃描線。
表C說明圖7的方法如何被用於圖6C的掃描線662的前三個邊緣。
表D說明將第三裝置應用到圖11的掃描線1130。
具體實施例方式
以在計算機存儲器內的數據上操作的算法和符號表示的形式來明確或隱含地介紹說明書其後的一些部分。這些算法的說明和表示是數據處理技術領域的技術人員所使用的以便最有效地向本領域技術人員表達他們工作的實質的方式。這裡的算法一般地被認為是導致期望的結果的前後照應的步驟的序列。步驟要求物理量的物理操作。通常，儘管不是必須，這些量採用能夠被存儲，轉換，合併，比較以及其他操作的電或磁信號的形式。主要由於通用的原因，有時把這些信號稱為比特，值，元素，碼元，字符，術語，數量等等證明是方便的。
但是應該記住上述和相似的術語將與適當的物理量有關，並且僅僅是應用於這些量的便利的標籤。除非具體地表明，否則，從下文顯而易見，應當理解貫穿本發明公開，利用例如「計算」，「確定」，「替換」，「產生」，「初始化」，「輸出」等等術語的討論指計算機系統或類似電子設備的操作和處理，它們把計算機寄存器和存儲器內表示為物理(電子)的數據量處理和轉換成在計算機系統存儲器或寄存器或其他的這樣的信息存儲，傳輸或顯示設備內部相類似地表示為物理量的其它數據。
本說明還公開了用於執行方法的操作的裝置。這樣的裝置可以是為了要求的目的而特製的，或可包括通用計算機或由保存在計算機中的電腦程式有選擇地激活或重新配置的的其它設備。在這裡提出的算法和顯示不是固有地與任何特定的計算機或其它裝置相關。根據本文的教導，可以使用各種通用的機器。另外地，構造特殊的裝置以執行要求的方法步驟是適當的。
此外，本發明也隱含地公開了電腦程式，因為對所屬技術領域的專業人員來說由計算機代碼實現這裡說明的優選方法的各個步驟是顯而易見。電腦程式不局限於的任何特定的程序設計語言和它的實現。應當理解各種程式語言和它的編碼可能用來實現在這裡包含的公開的教導。此外，電腦程式不局限於任何特定的控制流。存在許多其它電腦程式的變體，在不偏離本發明的精神或範圍的前提下，其可以利用不同的控制流。此外可以並行而不是順序地執行電腦程式的一個或多個步驟。
這樣的電腦程式可以存儲在任何計算機可讀介質上。計算機可讀介質可包括存儲設備，例如磁性或光碟，存儲晶片、或其它適用於與通用計算機接口的存儲設備。計算機可讀介質還可包括硬接線介質，例如在網際網路系統中舉例說明的，或無線介質，例如在GSM行動電話系統中舉例說明的。當在這樣的通用計算機上加載並且執行電腦程式，可有效地產生實現優選方法的步驟的裝置。
在任何一個或多個附圖中以相同的附圖標記索引步驟和/或特徵，那些步驟和/或特徵為了該說明的目的具有相同的功能或操作，除非存在相反的意圖。
下列簡稱用於本發明公開PSRM像素-順序生成方法PARM畫具運算生成法IPARM改進的畫具運算生成法XPSRM專用的像素順序生成方法DL顯示列表OL目標列表CL合成列表AEL有效邊緣列表AOL有效目標列表RT生成任務PART畫具運算生成任務PSRT像素順序生成任務GDI圖形設備接口RIP光柵圖象處理器1.0生成裝置圖18示意地說明了配置為用於生成並且呈現計算計圖形目標圖像的系統1800。系統包括一個與系統隨機存取存儲器(RAM)1803有關的主處理器1802，其可包括非易失硬碟驅動器或類似裝置1805和易失半導體RAM1804。系統1800還包括系統只讀存儲器(ROM)1806，其一般地建立在半導體ROM1807上，且多數情況下可以由高密度磁碟設備(CD ROM)1808補充。系統1800還可包括用於顯示圖象的目標設備1513，例如印表機或以光柵方式操作的視頻顯示單元(VDU)。
上述說明的系統1800的組件經由總線系統1809相互連接，並且以該領域眾所周知的例如IBMPC/AT類型個人電腦和由此演變的裝置的計算機系統的常規運行方式來操作。
此外如圖18所示，圖形生成系統1505(或生成器)連接到總線1809，並且配置為根據經由總線1809由處理器1802提供的指令和數據生成來源於基於圖形目標描述的基於像素的圖像。生成器1505可利用系統RAM 1803用於生成目標描述，儘管優選地生成器1505同時與通常由半導體RAM形成的專用生成存儲裝置1530相關。
生成系統1505可以實現為在主處理器1802上的軟體。可選地，可以在分立的單元上實現生成系統1505，分立單元可以是定製的硬體單元或在通用計算機上運行的軟體。在其它備選方案中，生成系統可以是目標設備1513上的嵌入系統。
在圖15中說明了生成流水線。在主處理器1802上運行的應用程式1501發送圖形數據到主處理器的作業系統的圖形設備接口(GDI)1503。GDI處理圖形數據並且傳遞數據到圖形生成系統1505，圖形生成系統具有顯示列表生成模塊1507和生成模塊1511。
顯示列表生成模塊1507由從GDI1503接收的數據中定義的目標集合產生顯示列表。以z-水平(優先級)順序從最低優先級目標到最高優先級目標對顯示列表中的目標排序。顯示列表保存在顯示列表存儲器1509中。生成模塊1511處理顯示列表，產生像素用於列印。
在生成器1505作為駐留在主機1802上的軟體的情況下，生成器1505產生半色調(half-toned)位圖。壓縮該位圖並發送給目標設備1513，其解壓位圖並生成像素數據的頁面。
在備選方案配置中，顯示列表生成模塊1507駐留在主機1802上，並且生成模塊1511嵌入到目標設備1513。在這種情況下，主處理器1802發送顯示列表到目標設備1513，它生成顯示列表並產生用於列印的像素數據。
生成模塊1511使用多個生成方法，在下文中更詳細地說明該生成方法。模塊1511根據在下文討論的標準來分配顯示列表不同的部分到不同的生成任務，其中不同的生成任務利用不同的生成方法。生成模塊1511可利用生成任務隊列以便對同時執行的生成任務線程排隊。使用的生成方法包括在3.0部分討論的像素順序生成方法(PSRM)，在4.0部分說明的畫具運算生成法(PARM)，在6.0部分說明的改進的PARM(或IPARM)，和在8.0部分說明的專用的PSRM(XPSRM)。說明了三個使用所述生成方法的不同組合的裝置。
2.0數據結構當顯示列表生成模塊1507從GDI層1503接收目標時，它將目標解壓縮成三個成分
-邊緣，目標的輪廓說明；-說明如何在頁面上描繪目標的繪圖信息；和-說明目標顏色的填充信息。
目標的輪廓被分成上邊緣和下邊緣，其中每個邊緣無變化地向下進行頁面。取決於當沿著掃描線掃描時邊緣是否激活或停用目標，將邊緣分配為方向向上或向下。
在軟體中邊緣實現為數據結構。數據結構包含-描述邊緣的輪廓的點；-當前掃描線上的邊緣的X位置；和-邊緣方向。
繪圖信息，或水平數據保存在水平數據結構中。數據結構一般地包含-z-順序整數，稱作優先級；-填充規則，例如奇-偶或非零-卷繞；-有關目的標信息(例如目標是否是文本目標，圖形目標或圖像目標)；-複合算符；-繪圖的填充類型，例如位圖，平鋪顯示，或淺色(flat color)；和-剪切-計數，指示多少剪片在剪切此目標。
填充信息，或填充數據保存在稱作填充數據結構的數據結構中。數據結構的內容取決於填充類型。對於位圖填充，數據結構一般地包含-在頁面上位圖原點的x和y位置；-以像素為單位的位圖的寬度和高度；-頁面到圖像的轉換矩陣；-指示圖像數據格式的值，(例如32bpp RGBA，或24bpp BGR，等等)；和-到圖像數據的指針。
對於淺色填充，數據結構一般地包含單個32位整數——8位用於紅色，8位用於綠色，8位用於藍色和8位用於阿爾法信道。
每個邊緣數據結構一般地具有指向水平數據結構(level data structure)的指針。每個邊緣數據結構還具有指向填充數據結構(fill data structure)的指針。
圖1A顯示了一個具有第一目標O1和第二目標O2的圖像，第一目標是不透明橙色字符「O」，而第二目標是半透明紅色正方形。
圖1B顯示了目標O1和O2的邊緣。目標O1具有邊緣＝E1(下)，E2(上)，E3(上)，E4(下)；-水平數據＝{填充-規則＝非零-卷繞，目標類型＝文本，優先級＝1}；以及-填充數據＝RGBA＝255，128，0，255(不透明的橙色)。
目標O2具有--邊緣＝E5(下降)，E6(上升)；-水平數據＝{填充-規則＝非零-卷繞，目標類型＝圖形，優先級＝2}；以及-填充激據＝RGBA＝255，0，0，128(半透明的紅色)。
圖1C示出了圖1A的圖像的邊緣列表50。邊緣E1和E4指包含有目標O1的製圖信息的水平數據52，邊緣E5和E6指目標O2的製圖信息的水平數據56。水平數據52和56指分別包含有用於目標O1、O2的填充信息的填充數據54和58。
利用所述方式的數據結構，可根據邊緣的列表來生成顯示列表。將其稱為基於邊緣的顯示列表。
在圖1A所示的示例中，顯示列表是邊緣列表{E1，E2，E3，E4，E5，E6}。
首先通過遞升y坐標、然後在y坐標相同時通過遞升x坐標來存儲顯示列表。所存儲的圖1A的顯示列表是{E1，E2，E5，E6，E3，E4}。
3.0像素順序生成方法(PSRM)由生成模塊1511使用的像素順序生成方法以光柵掃描順序一次一個地為像素生成色彩和暗度。在當前正被掃描和處理的任一像素處，像素順序生成方法僅對那些在當前掃描像素處有效的暴露目標進行合成。如果當前被掃描的像素位於目標的邊界之內，則像素順序生成方法就確定在該像素處的目標是有效的。
生成器1505通過參照與那個目標相關聯的填充計數器來實現這一點。填充計數器保持運行填充計數，該計數表明像素是否位於目標的邊界之內。當生成器1505遇上與目標相關聯的邊緣時，它就根據該邊緣的方向來增加或減少填充計數。生成器1505然後能夠根據該填充計數和預定填充規則來確定當前像素是否在目標的邊界之內。關於與有效目標相關的標記，在使用PSRM時生成器1505確定該目標是否被暴露。與目標相關聯的標記表明該目標是否使更低優先級的目標不透明。即，該標記表明該目標是否部分透明，在該情況下，這些更低優先級的目標將對當前像素的顏色和透明性起作用。另外，該標記表明該目標是不透明的，在該情況下，這些更低優先級的目標將對當前掃描的像素的顏色和透明性不起任何作用。如果一個目標是最高的有效目標，或者如果在該目標之上的所有有效目標都使得它們的對應標記被設定為透明，則像素順序生成方法確定該目標暴露。然後生成器1505合成這些暴露的有效目標，以確定並輸出當前掃描像素的顏色和暗度。
3.1 PSRM確定有效邊緣圖2是示出了根據像素順序生成方法中的主邊緣列表來如何確定有效邊緣的流程圖。主邊緣列表包含有待生成的所有邊緣，有效邊緣列表是與當前掃描線交叉的邊緣的臨時列表。
步驟251是初始化步驟，其中將變量CurY設為零，並將有效邊緣列表(ActiveEdgeList)設為空集。然後，在步驟253，生成器1511從主邊緣列表中讀取邊緣。在步驟255，生成器1511檢查主邊緣列表中的所有邊緣是否都被處理過，或者當前讀取的邊緣的y值，即Edge.y是否大於在變量CurY中存儲的值。
如果這些條件中一個都不滿足(步驟255中的否選項)，則處理然後進行到步驟259，在步驟259中將當前邊緣合併到有效邊緣列表中。通過遞升的x值對當前邊緣列表中的邊緣進行排序，即沿著掃描線的順序進行排序。一旦當前邊緣被添加到有效邊緣列表中，處理就返回到步驟253以考慮來自主邊緣列表的下一邊緣。
如果在步驟255中有任一條件滿足(步驟255的YES選項)，則然後在步驟257中，生成器1511確定掃描線的數量以生成N。如果主邊緣列表中的所有邊緣都被處理過，就將N設置成在頁面上保持的掃描線的數量，即頁面高度(PageHeight)和當前掃描線之間的差值N＝頁面高度-CurY然而，如果還有要處理的邊緣，就將N設置成在CurY與在其上開始使當前讀取的邊緣開始的掃描線之間的掃描線的數量N＝Edge.Y-CurY。
一旦確定了掃描線的數量，生成器1511就生成用於N個掃描線的有效邊緣列表，然後更新該當前掃描線CurY＝CurY+N。
對於像素順序生成方法，參照圖3A來進一步說明N條掃描線的生成。
接下來，在步驟261，生成器1511檢查更新的CurY是否等於頁面高度。如果等於，則確定在步驟263有效邊緣的處理終止。然而，如果CurY小於頁面高度(261的NO選項)，則處理流程返回到步驟253，以處理來自主邊緣列表的下一邊緣。
表A示出了如何將圖2的方法用於圖1A至1C的示例。從左至右逐行地讀取該表。每行表示在步驟253處開始的環的一次重複。為了便於表示，略去了步驟251。空框表示步驟不執行。步驟255確定在環的當前重複中執行步驟257至259中的哪一個。
在環的第一次重複中，步驟253從主邊緣列表中讀取邊緣E1。因為CurY被初始化為零，所以E1在其上開始的掃描線E1.Y大於CurY，並因此執行步驟257。頁面的起點和E1.Y之間的掃描線被生成，並且CurY被更新。
在環的最後一次重複中，所有的邊緣都被處理了，因此將N設置成頁面高度和CurY之間的差值。剩餘的掃描線被生成並且CurY被更新。步驟251確定CurY與頁面高度相等，並且該環終止。
3.2 PSRM生成掃描線圖3A的流程圖示出了在像素順序生成方法中如何生成掃描線。通過圖2的步驟257來調用圖3A的處理。
在初始化步驟351中，生成裝置1511將索引CurX設置成零，並將有效目標列表(ActiveObjectList)和臨時有效邊緣列表(TempAEL)設置成空集。然後，在步驟353，處理進入環，該環一直繼續到掃描線的結束，即當CurX等於頁面寬度(PageWidth)時。在步驟353中，生成器1511從有效邊緣列表(AEL)讀取邊緣「Edge」。然後，在步驟355，生成器1511檢查有效邊緣列表中的所有邊緣是否都已經被處理過，或者Edge.X，即當前掃描線和當前讀取的邊緣的交叉是否大於索引CurX。如果這些條件中的任一條件滿足，則處理流程進行到步驟357。如果這些條件不滿足(355步驟中的否選項)，則處理就進行到步驟359。
在步驟359，從AEL中將當前讀取的邊緣刪除，並將當前讀取的邊緣所指向的目標適當地激活或禁用。目標的激活/禁用是基於與該目標相關聯的填充規則。將目標添加到有效目標列表(AOL)或從該列表中去除。參照圖7對用於被剪切的目標的激活/禁用和AAOL更新步驟進行更詳細地說明。
在下面的步驟360中，將Edge.X更新以表示當前讀取的邊緣與下一掃描線的交叉。接下來，在步驟348中，檢測當前讀取的邊緣以查看該邊緣在當前掃面線上是否終止。如果沒有終止，則執行繼續到步驟349，在步驟359中將該邊緣添加到臨時AEL(TempAEL)的適當的位置中，以保持該列表的遞升x順序。否則(步驟348的是選項)，隨後是步驟349，並且處理流程返回到步驟353以從有效邊緣列表中讀取下一邊緣。
在步驟357，確定用於生成N的像素的數量。如果有效邊緣列表中的所有邊緣都已經被處理過，則將N設置成頁面寬度和索引CurX之間的差值。否則將N設置成(Edge.X-CurX)，即當前索引與當前所考慮的有效邊緣的位置之間的差值。
然後，在步驟361中，為N個像素生成有效目標列表，如參照圖4所具體描述的。
在步驟363，將索引CurX更新成(CurX+N)，並且步驟365檢查CurX是否等於頁面寬度。如果是，則在步驟366，將臨時邊緣列表的內容複製到有效邊緣列表中。然後處理循環返回到步驟351以生成下一掃描線，或者將步驟367返回到圖2的步驟257。如果CurX沒有達到頁面寬度(365的否選項)，則然後處理流程返回到步驟353。
表B示出了用於圖1A圖像掃描線的圖3A的方法，圖1A的圖像具有有效邊緣列表＝{E5，E1，E3，E4，E2，E6}，即通過『O』特徵O1的中心孔的任阿掃描線。
與前面所述相同，表格的每一行表示在步驟353處開始的環的一次重複。檢查步驟355確定隨後是路徑359/360還是路徑357/361/363。空框表示在環的當前重複中不執行這些步驟。未明確示出終止步驟365和367。
最初，CurX是零，有效目標列表(AOL)是空的。
3.3 PSRM在掃描線上生成像素圖4的流程圖示出了在掃描線上生成像素的方法，其中僅將最不透明的目標和位於該最不透明目標上方的任何透明目標進行合成並輸出。通過圖3A的步驟361來調用圖4的步驟。
在步驟451，生成器1511檢查有效目標列表(AOL)是否為空。如果是，則生成器1511為N個像素輸出白色(頁面背景)，在步驟470對幀存儲的位深進行半色調調整(如果需要)。在步驟471處理終止並返回步驟363。
如果有效目標列表不空(步驟451的否選項)，則然後處理流程進行到步驟453，其中通過遞減優先級來存儲有效目標列表。。有效目標列表中的項目的數量是NumObjects。
然後，在步驟457，生成器1511檢查在有效目標列表中的第一目標是否為不透明。如果是，則步驟459將AOL
中的目標的填充輸出到幀存儲，在步驟470對幀存儲的位深進行半色調調整(如果需要)，並且在步驟471處理終止。在該情況下，不需要考慮有效目標列表中的任何其它目標，因為最高的目標是不透明的。
如果最高目標不是不透明(步驟457的否選項)，然後生成器在步驟461中設置索引i＝1。在步驟463，將Obj設置成有效目標列表的第I項中的目標。步驟465在有效目標列表中檢查Obj是否不透明，或者索引i是否等於目標的總數，即(NumObjects-1)。
如果有任一條件滿足(步驟457的否選項)，然後生成器1511在步驟469中將AOL
和AOL[i]之間的所有目標的合成結果輸出到幀存儲，在步驟470對幀存儲的位深進行半色調調整(如果需要)。然後處理在步驟471中終止。
如果在步驟465中的條件沒有一項滿足(467的否選項)，然後處理流程進行到步驟467，該步驟使索引增加，i＝i+1。然後處理返回步驟463，以考慮有效目標列表中的下一目標。
作為圖4的處理的應用的示例，考慮圖1A中的目標O1的左半部分的像素在像素E1.X和E3.X之間的掃描線E3.Y(即邊緣E3在其上開始的掃描線)上的運行。對於像素的該運行，兩個目標都是有效的，並且有效目標列表是AOL＝{O1，O2}。
在步驟451，檢查AOL以查看它是否為空。AOL包含有兩項，所以執行進行到步驟453。通過使優先級遞減來存儲AOL，導致AOL＝{O2，O1}。NumObjects是2。步驟457檢查列表中的第一項是否不透明。O2不不透明，所以執行進行到步驟461。在步驟461將計數器i初始化為1，然後在步驟463，將變量obj設置成在位置AOL[i]處的目標。在這種情況下該目標是O1。在步驟465，因為O1是不透明的，所以執行進行到步驟469。將目標O2和O1的填充合成在一起並將結果寫到幀存儲。
3.4 PSRM中的剪切在諸如MicrosoftTMGDL的一些系統中，目標是由剪切域來伴隨的，並且僅在由相應的剪切域限定的區域中輸出目標。
在這些系統中，典型地將每個目標一次生成到幀存儲，通過相應的剪切域進行剪切。一些允許待激活的多個剪切域。因此，可以通過多於一個的剪切域來將目標生成到幀存儲。
在像素順序生成方法(PSRM)中，剪切是典型地通過一組邊緣和水平數據結構的「目標列表」來表示的，其中該列表中的第一項是說明剪切本身的水平數據結構。水平數據結構中的剩餘項描述正被剪切的目標。
圖6A是被剪切的圖像的示例。圖6A中的三個目標是三角形剪切650，倒置的三角形剪切652，和被剪切650和652剪切的的矩形654。圖6B示出了由生成圖6A的目標而產生的六邊形656。
圖6C示出了目標650-654的邊緣。剪切650具有左邊緣E1和右邊緣E2。剪切652具有左邊緣E3和右邊緣E4，以及矩形654是通過左邊緣E5和右邊緣E6來限定的。邊框658為目標650、652、654的外側點劃界。掃描線S662用於表示將圖7的方法應用到圖6A的示例。
圖6D示出了在圖6A的圖像的顯示列表660的存儲器中的優選排列。在圖6D中，各個邊緣指向包含有用於相應目標的繪圖信息的水平數據。對於邊緣E1和E2，這是水平數據L1，對於邊緣E3和E4，這是水平數據L2，以及對於邊緣E5和E6，這是水平數據L3。目標650和652是具有水平數據L1、L2的剪切目標，其指向目標654的水平數據L3。目標654的水平數據L3反過來指向包含有目標654的填充信息的填充數據F3。
水平數據結構包括與目標相關聯的剪切計數，以表明有多少個剪切域剪切相關聯的目標。在該示例中，目標654具有L3。ClipCount＝2，表示目標654被兩個剪切所剪切。
圖7示出了對有效目標列表(AOL)的管理。通過步驟359來調用圖7的步驟。圖7的輸入是有效目標列表和當前邊緣所指向的水平數據結構的列表。圖7的輸出是可以通過添加被激活的目標或去除禁用的目標而進行修改過的有效目標列表。
在步驟751的初始化步驟中，將計數器i初始化為零，並將變量clip_delta初始化為零。然後，在步驟753，生成器1511將變量obj設置成OL[i]，OL[i]是與當前邊緣相關聯的目標列表OL中的第i個目標。在步驟755，生成器1511檢查obj是否是剪切。如果是，則然後在步驟757，生成器1511檢查該剪切是否已變成有效。如果該剪切變成了有效，則在步驟761中將變量clip_delta設置成(-1)。如果該剪切未變成有效，則在步驟753中將變量clip_delta設置成1。
在步驟759或761中設置了變量clip_delta之後，處理流程進行到763，其中將計數器i增加1。然後步驟765檢查與當前邊緣相關聯的所有目標是否都被處理過。如果是，則圖7的處理終止並控制流程返回步驟360。如果還存在與當前邊緣相關聯的目標(步驟765的否選項)，然後處理流程返回到步驟753以處理下一目標。
如果當前正考慮的目標不是剪切域(步驟755的否選項)，然後在步驟768，生成器1511將當前目標的剪切技術增加值clip_deltaObj.ClipCount＝obj.ClipCount+clip_delta。
接下來，在步驟769，生成器1511檢查目標obj是否變成了有效，並且obj的剪切計數是否為零。如果這兩個條件都滿足，則然後在步驟771，生成器1511就將obj添加到有效目標列表(如果obj還沒有在有效目標列表中)。
如果步驟769中的兩個條件都不滿足(769的否選項)，然後，如果目標obj在有效目標列表中，則生成器1511將obj從有效目標列表中去除。
在步驟771或步驟773之後，處理流程轉到步驟763，如上所述，步驟763確定是否存在與當前邊緣相關聯的任何更多的目標。
作為示例，表C示出了圖7的步驟如何在圖6C所示的掃描線662的前面三個邊緣上進行操作。
4.0畫具運算生成法(PARM)使用畫具運算的生成方法與上述的像素順序生成方法類似。PARM和PSRM兩者都要求用於各個掃描線的以遞升的x順序被跟蹤並被保特的邊緣。
如上所述，圖2是用於確定有效邊緣列表的方法。圖2的步驟用於PSRM和PARM兩者。
對於畫具運算生成法，圖2的步驟257調用圖3B以生成由於N條掃描線的運行的有效邊緣列表。除在PARM中僅有一個目標是有效的並因此不需要處理有效目標列表之外，圖3B的處理類似於圖3A的處理。從而，初始化步驟351在圖3B中被步驟371代替，該步驟將有效目標設置為空(NULL)，而不是將有效目標列表設置為空集(NULL set)。圖3A中的步驟361(該步驟調用圖4的步驟)，被圖3B中的步驟369代替，在該步驟中生成器1511在執行PARM時使用有效的(單個)目標的填充來生成N個像素。
圖3B的步驟359a類似圖3A中的步驟359，除不需要新有效有效目標列表之外。
當激活/禁用目標時，使用圖7的方法，除因步驟771和773僅分別對Active標記進行設置或清零而更簡單之外。
4.1 PSRM和PARM之間的區別可將上述的畫具運算生成法(PARM)和像素順序生成法之間的區別總結如下(a)在PARM中，典型地在從GDI層1503一接收到目標就生成目標，而PSRM直到接收到最後一個目標時才開始生成；(b)PARM的顯示列表僅有一個目標，而所有待生成的目標都在PSRM的顯示列表中；(c)在PARM中，僅將目標有效處的像素運行生成到幀存儲，而PSRM在沒有目標有效的位置處典型地生成白色(頁面的顏色)；(d)在PARM中，僅在目標和幀存儲之間進行合成，而PSRM基於像素運行而合成所有起作用的有效目標並將結果寫到幀存儲；以及(e)在PARM中，為每個目標處理與其相關聯的剪切域，而PSRM一次剪切所有目標。
在由剪切域C1剪切的具有三個目標的圖像中，PARM將剪切域C1處理三次，每次處理三個目標中的一個。在PSRM中，僅將剪切域C1一次添加到顯示列表。剪切域C1具有指向三個目標中的每一個的水平列表。各個目標具有為1的剪切計數，確保在生成期間剪切該目標。
當幀存儲以比請求合成的目標的位深更低的位深保持像素值時，在PARM中的合成就成了問題。例如，如果幀存儲包含每像素1比特的CMYK半色調像素值，並且期望將目標合成到每像素32比特的RGBA像素值，那麼在合成時就會存在信息丟失。
5.0 第一方案使用PSRM和PARM的生成參照圖14來說明第一生成方案。第一方案涉及混合方法，在該方法中生成器1505使用了上述畫具運算生成法和像素順序生成法兩者。
如圖15所示，顯示列表生成模塊1507生成基於邊緣顯示列表1509。在該列表中，為各個邊緣分配目標標識符edge.ID，其表明該邊緣所屬的目標。
如果一個目標具有要求該目標的像素以某種方式與該目標下方的像素合併的合成算子，那麼該目標就要求合成。當將目標添加到顯示列表中時，顯示列表生成模塊1507保持對要求合成的最後一個目標的跟蹤。將其稱為最後合成目標。一旦將所有的目標添加到顯示列表，生成模塊1511就開始生成。
就生成任務而言來對圖14的方法進行說明。生成任務(RT)是在執行時根據特定的生成方法來生成基於邊緣的顯示列表的一部分的任務。向生成任務分配來自主顯示列表的一組邊緣。將這些邊緣保存在生成任務自己的本地主邊緣列表和本地有效邊緣列表中。利用PARM的生成任務被稱為PART(畫具運算生成任務)。利用利用PSRM的生成任務被稱為PSRT(像素順序生成任務)。
在第一方案中，生成模塊1511將顯示列表中的第一目標和最後合成目標之間的所有邊緣分配給利用了上述PSRM的像素順序生成任務(PSRT)。生成任務為幀存儲執行並生成包括有白色空間的邊緣集合。
然後，對於顯示列表中的每個剩餘目標，將該目標的邊緣分配給利用了上述PARM的畫具算法生成任務(PSRT)。該生成任務基於幀存儲來執行並生成除白色空間之外的邊緣集合。
因此，將像素順序生成方法應用於要求合成的任何目標，然後基於幀存儲來簡單地生成剩餘(不透明)目標。
參照圖14，在步驟1401，生成模塊1511檢查最後合成目標是否大於或等於零。如果是(步驟1401的是選項)，然後在步驟1403，生成模塊1511將具有邊緣ID＜＝最後_合成_目標(last_compositing_object)分配給像素順序生成任務。然後，在步驟1405，使用在圖2、3A、4和7中所述的方法步驟來執行生成任務。
接下來，在步驟1407，將索引i設置成(最後_合成_目標+1)。在步驟1409，生成器檢查i是否小於N。如果不是這種情況(步驟1409中的否選項)，然後就沒有更多的目標要處理並且在步驟1411中程序終止。然而，如果i小於N，則處理流程繼續到步驟1413，該步驟將具有邊緣ID等於i的所有邊緣分配給畫具算法生成任務。然後，在步驟1415，使用圖2、3B和7來執行生成任務。
在生成任務結束之後，步驟1417使索引i增加1，該方法返回步驟1409，以檢查是否還有目標要檢查。
在最後_合成_目標不大於或等於0的地方(步驟1401的否選項)，處理流程直接進行到步驟1407，繞過步驟1403和1405。在該情況下，不要求像素順序生成，並且顯示列表中的所有目標都可以使用PART來生成。
第一方案的方法可被概括為以下偽代碼，參照圖14使用該方法將36,000個目標的頁面生成在1bpp半色調的單色幀存儲上，其中最後合成目標是5，在具有256MB RAM的Pentium III 667MHz上的生成時間與標準PSRM相比從6秒減小了一半到3秒。
對於本領域的技術人員應該清楚，在具有多處理器的及其上實現生成模塊1511時，可以在獨立的線程中生成各個PART。當在顯示列表中考慮的下一目標不與當前執行的PART交疊時，然後可以創建新的線程來生成新考慮的目標。該處理繼續進行，直到生成所有的目標，或發現一個目標與當前執行的PART交疊。
6.0修改後的畫具算法(IPARM)提出兩種方法來改進上述的PARM。第一修改涉及處理連續的非交疊不透明目標，第二中方法設計剪切多個連續的目標。
6.1 連續非交疊不透明目標畫具算法生成方法事實上可以一次處理很多目標，規定這些目標不具有交疊的邊界框。只要邊界框不交疊，邊緣存儲運動就僅局部地發生在各個目標的邊緣中。
例如，圖5A示出了具有交疊邊界框的兩個目標，即使這些目標自身不交疊。目標802是具有邊框803的多邊形。目標802是由邊緣E1、E2、E3、E4、E5、E6和E7形成，邊緣E3至E6排列成鋸齒圖案。
目標804是具有邊框805的多邊形。目標804是通過邊緣E8、E9、E10、E11和E12的順序形成的。邊緣E11和E12以鋸齒方式排列，由邊緣E8和E12形成的峰位於由邊緣E3和E4形成的空心中，目標804的邊緣E11和E12形成的峰位於由目標802的邊緣E5和E6形成的空心中。儘管目標804與目標802不相遇或相交，但是邊框805與邊框803交疊。
因此，當一起生成目標802和804時，可以看出在掃描線807處，目標804的邊緣E8、E12、E11和E10必須被併入有效邊緣列表{E2、E3、E4、E5、E6、E7}，導致邊緣列表{E2、E3、E8、E12、E4、E5、E11、E10、E6、E7}。
在圖5B中，將目標804從目標802移開，使得邊框803、805不再交疊。使邊緣E8、E12、E11、E10決不與E2、E3、E4、E5、E6、E7相交。
已經發現，生成分配給PART的若干目標(其中沒有兩個目標是通過邊框交疊的)至少與單獨生成各個目標一樣快。在改進的PARM(或IPARM)中，將不通過邊框交疊的連續不透明目標的獨立組優選地分配給獨立的PART。
6.2 剪切多個連續目標在通過一個或多個剪切域對多個連續目標進行剪切時，在典型的PARM中，剪切並生成各個目標。這在剪切域是複雜路徑時並不是有效的。當PART利用PSRM來生成一組通過剪切域剪切的目標時可以改進性能。這就確保了僅一次來處理剪切。
6.3 用於IPARM的程序修改後的PARM利用在圖2中所述的有效邊緣列表確定方法，以及參照圖3A所述的生成掃描線的方法。IPARM還使用參照圖7所述的目標激活。
在步驟361，IPARM為N個像素生成有效目標列表。對於IPARM，這樣的生成如圖8所示。圖8的方法的輸入是一組有效目標。在步驟851，生成器檢查有效目標列表(AOL)是否為空。如果是，該程序在步驟857終止，並且控制流程返回圖3A。這是因為IPARM不生成白色空間。
如果AOL不空(步驟851的否選項)，然後在步驟853，通過遞減優先級值來存儲有效目標列表。該列表中的第一項包括具有最高優先級的有效目標。這是因為僅將不透明目標提交給改進的PARM。執行繼續到步驟855，該步驟將AOL
處的目標的填充輸出到幀存儲。在步驟857路由終止。
將基於改進的PARM(IPARM)的生成任務(RT)稱為IPART。IPART可用於生成以下類型的數據。
1、連續非交疊的不透明目標。
2、一組剪切域加上所有被這些剪切域剪切的不透明目標，提供所有被剪切的不透明的目標。
7.0 第二方案使用PSRM和IPARM生成由生成模塊1511使用的第二生成方案將上述的像素順序生成方法和與部分6.0的IPARM合併。與第一方案相同，使用PSRM生成第一目標和最後合成目標之間的所有目標。保證所有隨後的目標都將是不透明的，並因此這些目標適於候選為通過改進的PARM(IPARM)。在第二方案中，將連續非交疊目標成組以用於通過IPART來生成。
7.1 第二方案目標列表在IPARM的優選實施中，維持被稱為目標列表的新列表。當每個目標被處理時就向目標列表添加一項，並通過顯示列表生成器1507將該項添加到基於邊緣的顯示列表。目標列表中的各項包含-參照描述目標的邊緣列表的開始並結束索引；-目標的邊框；以及-用於表示目標是否要求合成的標記。
在通過一個或多個剪切域剪切一組目標時，第一剪切域和被剪切的最後一個目標之間的完整的邊緣集合被認為是單個目標。在該情況下，邊框是該組目標的所有邊框和一個或更多個剪切域的結合。
因此，例如，將圖6A中的剪切域650、652和矩形654的主邊緣列表{E1，E2，E3，E4，E5，E6}被認為是單個目標。
對於圖5A中的目標802和804，主邊緣列表{E1，E2，E3，E4，E5，E6，E7，E7，E9，E10，E11，E12}和目標列表是兩項-項1具有開始索引＝0(稱為邊緣E1)，結尾索引＝6(稱為邊緣E6)，邊框＝BB1(即框803)，合成標記＝FALSE。
-項2具有開始索引＝7(稱為邊緣E1)，結尾索引＝11，邊框＝BB2(即框805)，合成標記＝FALSE。
7.2 第二方案顯示列表生成圖9(a)和9(b)示出了顯示列表的生成和第二方案顯示列表使用的相應目標列表。該方法假定一個目標可以僅通過一個剪切域來剪切。將剪切域看作是待生成的目標的屬性。這在諸如MS Windows GDI的系統中是通用的。通過顯示列表生成模塊1507來執行圖9(a)和圖9(b)的步驟。
在步驟901，模塊1507將當前剪切城CurClip設置成NULL，並將最後一個合成目標設置成負一(-1)。將計數器i設置成零並將目標列表OL
的第一項分配以下值OL
.Start＝0執行繼續到步驟903，該步驟檢查是否還存在要處理的目標。如果對於頁面沒有更多的要處理的頁面(步驟903的否選項)，然後在步驟919執行終止。否則(步驟903的是選項)，執行繼續到步驟905，在步驟905中，將目標的剪切域分解成邊緣、水平數據和填充數據。模塊1507將這些邊緣添加到邊緣列表。如果該目標要求合成，然後將變量「合成」設置成TRUE，並將最後合成目標設置成計數器i。另外，如果目標不要求合成，然後將變量「合成」設置成FALSE。
接下來，在步驟907，模塊1507檢查目標是否具有剪切域。如果目標不具有伴隨剪切域的目標，然後執行進行到步驟909，在該步驟909中，將變量「bbox」設置成待繪製的目標的邊框。然後，在步驟917，對目標列表中的第i項OL[i]分配以下值OL[i].End＝邊緣列表的當前尺寸減1。
OL[i].BBox＝變量「bbox」。
OL[i].Composites＝變量「合成」。
將計數器i增加1，對目標列表中的第i項OL[i]分配以下值OL[i].Start＝邊緣列表的當前尺寸。
在步驟917之後，執行返回到步驟903，以確定是否還有要處理的目標。
在步驟907，如果目標具有伴隨的剪切域(步驟907的是選項)，然後執行繼續到步驟911，在步驟911中，伴隨的剪切域可與變量「CurClip」。如果剪切域相等(步驟911的是選項)，然後執行繼續到步驟915。
在步驟915，利用以下值來更新目標列表中的「i減1」項目OL[i-1]OL[i].End＝邊緣列表的當前尺寸減1。
OL[i].BBox＝合併後的邊框OL[i-1].BBox與目標的邊框Obj.BoundingBox。
OL[i-1].Composites＝OL[i-1].Composites的值的結果逐位地與「composites」的值相或。這就確保了即使當前目標不要求合併，OL[i-1].Composites也能保持TRUE。
然後模塊1507利用以下值來更新目標列表中的第i項OL[i]OL[i].start＝邊緣列表的當前尺寸。
執行繼續到步驟903，直到所有的目標被處理過。
如果在步驟911，伴隨的剪切域不等於當前剪切域「CurClip」(911步驟的否選項)，然後執行繼續到步驟913。在步驟913，將變量CurClip設置成伴隨剪切值，「Obj.Clip」。將變量bbox設置成目標和剪切域的合併邊框。然後，執行繼續到步驟917，如上所述。執行繼續到步驟903，直到所有的目標都被處理過。
在步驟919的結束處，輸出是未分類整理的主邊緣列表，以及相應的目標列表。另外，識別出了最後合成目標。顯示列表中的目標的總數是計數器「i」的值。
7.3第二方案生成方法圖16示出了第二方案的生成方法。在步驟1601，生成模塊1511檢查最後生成模塊是否大於或等於零。如果是，則然後在步驟1603中，模塊1511將OL
.Start和OL[最後合成模塊].End之間的邊緣分配給PSRT。然後，在步驟1605，使用圖2、3A、4和7的步驟來執成生成任務。然後執行繼續到步驟1607。如果最後合成目標不大於或等於零(步驟1601的否選項)，則然後不要求PSRT，並且執行直接進行到步驟1607，繞過步驟1603和1605。
在步驟1607，模塊1511將索引i的值設置成最後合成目標加1。然後步驟1611檢查i是否小於目標的數量N。如果沒有更多的要生成的目標(步驟1611的否選項)，然後該生成在步驟1609終止。如果還有要處理的目標，則然後在步驟1613，模塊1511設置以下值StartObj＝iTotalBBox＝Obj[i].Bboxi＝i+1。
然後步驟1615檢查Obj[i]在TotalBBox中是否為NOT，並且i是否小於N。如果這些條件滿足(步驟1615的是選項)，然後執行繼續到步驟1617，步驟1617設置以下值TotalBBox＝TotalBBox+Obj[i].Bboxi＝i+1然後執行返回步驟1615。
如果步驟1615中的條件不滿足(步驟1615中的否選項)，然後在步驟1619中，模塊1511將OL[StartObj].Start和OL[i-1].End之間的所有邊緣分配給IPART。在步驟1621，模塊1511使用圖2、3A、7和8的步驟來執行生成任務。然後在步驟1623，索引i被增加1，並且執行返回步驟1611，以檢查是否還有目標要處理。
將第二方案的生成方法總結為以下偽代碼<![CDATA[IFlast-compositing-object＞=0 Assign all edges between OL
.Start and OL[last-compositing-object].End to PSRT. Execute render task.ENDIFSET i=last-compositing-object+1WHILEi＜N SET StartObj=i SET TotalBBox=OL[i].BBox i=i+1 WHILE(OL[i].BBox NOT IN TotalBBBox)AND(i＜N)SET TotalBBox=TotalBBox+OL[i].BBoxi=i+1 ENDWHILE Assign all edges between OL[StartObj].Start and OL[i-1].End toPART. Execute render task.ENDWHILE]]>圖10A中示出了示例，其中圖形950由五個目標951、952、953、954和955形成(以遞升的優先級)。最後合成目標是952。
矩形951位於圖像950的左上方。半透明橢圓952與矩形951部分重疊，但是不與其他目標中的任何一個接觸。矩形954位於圖像950的右上方並且不與其他目標中的任何一個相交。不透明矩形953位於圖像950的下半部分中，並且不透明的梯形955部分地與矩形953重疊。
在第二方案中，使用像素順序生成方法將用於目標951和952的邊緣集合生成到幀存儲。圖10B中示出了該第一生成任務957。
目標953和954不通過邊框重疊，但是目標955與目標953和954的合併後邊框重疊。因此，如圖10C所示，將目標953和954的邊緣分配第一PART959。任務959將目標953和954生成到幀存儲上。
最後，單獨的PART 961用於將目標955生成到幀存儲上，如圖10D中所示。
7.4 分段在某些情況下，整個幀存儲都可以使用，諸如當目標是每像素單色半色調輸出是1比特時可以是這種情況。對於A4紙以每英寸600點(DPI)而言，用於該輸出的幀存儲要求大約4MB。以更大的DPI或在更大的紙上，或者更大的位深，諸如4bpp CMYK，則僅可以分配每線像素的分段(band)等於頁面寬度，並且掃描線的最大數量等於比頁面高度小的多的某一數量，例如256條掃描線。
在全部幀存儲都可用時，生成任務可完全按照順序執行。例如，當處理圖像950時，執行PSRT 957並將所有的像素生成到幀存儲。然後執行剩餘的IPART 959、961中的每一個，並將目標(935-955)生成到幀存儲。當連續的IPRT不重疊時，可並行地生成各個IPART。
僅在分段存儲可以使用時，然後任務才部分地按順序執行，因此就僅生成在當前分段上可見的那部分任務。當連續的IPART在一個分段內不重疊時，就可並行地生成各個IPART。
在圖10A的示例中，存在三個生成任務。任務957生成目標951和952。任務959生成目標953和954，並且任務961生成目標955。如圖10E所示，如果將頁面分成兩段B1和B2，則然後對於分段B1，任務957和959是有效的。對於H1掃描線，任務957被生成到該分段存儲上，然後，對於H2掃描線，任務959被生成到該分段存儲上。然後將該分段存儲發送到印表機。一個任務在存儲器中一直持續著直到所有的邊緣都被處理過。在分段B1內完成任務957，但是任務959還有要處理的邊緣(對於目標953)。在第二分段B2上，任務961是有效的。任務959被生成到分段存儲上，然後任務961被生成到分段存儲上。然後將該分段存儲發送到印表機。
可以將該分段方法在本說明書中描述的所有生成方法。
8.0 排他像素順序生成方法(XPSRM)當最後合成目標的數量與顯示列表中的目標的總數量相比較小時，第二方案的生成方法有用。在最壞情況的情形中，如果顯示列表中的最後目標要求合成，則然後在第二方案中所有目標都將使用PSRM來生成。經常的一種情況是要求合成的目標包含在本地化的區域中並且不與大量的目標重疊。
現在將對被稱為排他像素順序生成法(XPSRM)的修改後的PSRM進行說明，在該方法中僅輸出被命名的目標的像素。
在XPSRM中，向水平數據結構中添加一個新成員。該新成員稱為ExclusiveOutput。當有效目標列表(AOL)包含至少一個其ExclusiveOutput成員被設置成值為一(1)的目標時，才發出像素運行。AOL自己具有稱為ExclusiveCount的新成員。當將目標插入AOL時，AOL.ExclusiveCount被增加object.ExclusiveCount。當從AOL去除一個目標時，將AOL.ExclusiveCount減少object.ExclusiveCount。
XPSRM使用圖2所述的確定方法和圖3A中所述的生成掃描線的方法來確定有效邊緣列表。圖12示出了XPSRM所使用的激活目標的方法(考慮剪切)，該方法是圖7中所示的方法的修改後的版本。
圖13中示出了確定哪些目標對像素運行有用的XPSRM的方法，圖4是其修改後的版本。
圖13的方法包括圖4的很多步驟。具體而言，由步驟453、457、459、461、463、465、467、469、470和471構成的分支未改變。在圖13中初始步驟451被步驟1301取代，該步驟檢查是否「AOL空OR AOL.ExclusiveCount＝0」。如果該條件不滿足(1301的否選項)，執行處理到步驟453並且執行由步驟453-471組成的分支。
如果步驟1301的條件被滿足，則然後執行就直接進行到步驟471。因此，與圖4的方法的第二介變化是在XPSRM中略去了步驟455(輸出白色)。因此，如果有效目標列表是空，或者有效列表不包含其ExclusiveOutput成員已經被設置了的目標，那麼XPSRM就不輸出任何像素。
在圖12中對圖7的目標激活/禁用路線的修改後的版本進行描述。除步驟1223和1221分別取代步驟773和771之外，圖7和12的方法相同。步驟1223和1221包括使有效目標列表的新成員AOL.ExclusiveCount增加或減小的額外任務。
圖12的輸入與圖7相關，該輸入是有效目標列表和被當前邊緣所指的水平數據結構的列表。圖12的輸出是修改後的有效目標列表(AOL)和可能被修改的ExclusiveCount變量。
取代了步驟773的步驟1223從AOL(如果obj在AOL中)中去除obj，從AOL.ExclusiveCount推導出obj.ExclusiveOutput。取代了步驟771的步驟1221將obj插入到AOL中(如果obj不在AOL中)並將obj.ExclusiveOutput添加到AOL.ExclusiveCount。
XPSRM允許將多個目標添加到顯示列表，但是提出了僅有某些明確指定的目標出現。將利用XPSRM的生成任務稱為XPSRT。
圖11A中示出了示例。圖像1100包含在區域1110中的一百個第一目標。第一百個目標是不透明的文本目標。圖像1100還包括五個向量圖形目標，1101、1102、1103、1104和1105，其中目標1105合成到圖像1101、1102和1103上。然後緊隨這些目標的是區域1120中的更多數量的文本目標。在上述第一和第二方案的方法中，將使用PSRM來生成第一文本目標和目標1105之間的所有目標，因為目標1105是最後一個合成目標，即使目標1105對區域1110沒有影響。
相反，使用XPSRM，可將目標1105排他地生成到幀存儲，因此僅輸出1105，但是如圖11B所示，目標1105還是依靠目標1101、1102和1103而生成。
將目標1105的ExclusiveOutput成員設置成1，確保當對目標1105有效時，XPSRT僅輸出像素運行。對於這種像素運行，將目標1101、1102、1103和1105的邊緣提交給XPSRT。目標1101的邊緣是E1和E2，象1102的邊緣是E3和E4，目標1103的邊緣是E5和E6，目標1105的邊緣是E9和E10。圖11C中與掃描線1130相關地示出了這些邊緣。因此，被傳送到XPSRT的這些邊緣是{E1，E2，E3，E4，E5，E6，E9，E10}。E7和E8屬於目標1104，因此不包括在要生成的這些邊緣中。
存儲邊緣列表，導致列表{E1，E2，E3，E4，E9，E10，E5，E6}，並且如圖2和圖3A所示正常地跟蹤邊緣。
對於掃描線1130，有效邊緣列表是{E1，E9，E2，E3，E10，E4}。參照圖3A、圖12和圖13，在步驟351，將CurX設置成0，並將ActiveObjectList設置成空列表。在步驟353，讀取E1。E1.X大於CurX，所以執行繼續到步驟357。將N設置成E1.X，並且在步驟361，執行繼續到1301。因為AOL是空，所以沒有像素被輸出，並且在步驟471，執行返回步驟363。將CurX更新成El.X，並且在步驟363，El.X不等於PageWidth，所以路線返回到步驟353。
在步驟353，讀取El. E1.X＝CurX，所以執行繼續到步驟359，該步驟將E1從AEL中去除，並調用圖12的步驟751。在步驟751，將i設置成0，並將clip_delta設置成0。在步驟753，將obj設置成E1.OL
＝1101。在步驟755，目標1101不是剪切域，所以在步驟768，obj.ClipCount增加零。在步驟769，目標變成有效，並且在步驟1221，將該目標插入AOL，並且AOL.ExclusiyeCount增加1101.ExclusiveCount(該值是零)。在步驟763，i增加1，並且因為在步驟765對所有目標進行處理，所以路線在步驟767結束。然後，在步驟360，為下一掃描線而更新邊緣E1.X。執行返回到步驟353。
表D總結了所發生的關鍵步驟和動作。
9.0第三方案使用XPSRM和IPARM生成第三生成方案使用上述排他像素順序生成方法(XPSRM)和改進的畫具運算生成方法(IPARM)。
9.1 第三方案生成顯示列表在第三方案中，顯示列表生成模塊1507使用圖9所示的方法(對步驟905作了修改)生成顯示列表。
為步驟905添加了這樣的邏輯如果目標要求合成，則為稱為合成列表的第三列表添加新項。對步驟905的修改可總結為如下偽代碼<![CDATA[IF object.Clip合成列表中的每一項是目標列表，其中第一項是合成目標自己，隨後是該合成目標下面的所有目標，其中「下面」意思是「較低優先級並通過邊框重疊」。合成列表是遞升優先級，所以合成列表中的最後一個目標是合成目標下面的Z順序中的最高優先級目標。取決於各個合成目標的目標列表是在生成模塊1511的生成處理其間來構建的。儘管該說明是就列表而言的，但是諸如樹的另選數據結構也可用於捕獲相同信息。
根據圖9(a)和9(b)的修改的方法的輸出是未分類處理的主邊緣列表；相應的目標列表；以及合成列表。
另外，已識別出了最後合成目標，並且顯示列表中的目標的總數是計數器的值「i」。
然後，在生成期間，當將目標列表中的從第一個至最後一個地處理各個目標時，則針對合成列表中的所有項來檢查目標的邊框。如果當前所考慮的目標邊框與合成目標的邊框重疊，則然後將當前所考濾的目標添加到合成列表中的相應項中。
在圖11A的示例中，在第三方案中生成的合成列表包含有一項。反過來該項是由四個目標{1105，1101，1102，1103}構成。
9.2 第三方案生成圖17中示出了第三方案的生成方法。在初始化步驟1701，生成模塊1511將索引i設置成零，並將N設置成顯示列表中的目標的總數。然後步驟1703檢查索引i是否小於N。如果不是該情況，則在步驟1705生成處理終止。
如果i小於N(步驟1703的是選項)，然後執行進行到步驟1707，該步驟檢查是否i＜N並且OL[i].Composites＝FALSE。如果這些條件滿足(步驟1707的是選項)，然後在步驟1709，模塊1511設置以下值StartObj＝iTotalBBox＝OL[i].BBoxi＝i+1步驟1709還基於邊框和優先級，將項i添加到合成列表CL中的大於i的所有項中。
接下來，在步驟1711檢查三個條件。如果OL[i].Bbox不在TotalBBox中，並且i＜N，並且OL[i]不在合成列表CL中，則然後執行進行到步驟1713。否則(1711的否選項)，執行進行到步驟1715。
在步驟1713，生成模塊1511將當前目標OL[i]的邊框添加到總邊框TotalBBox，並增加i。然後步驟1713基於OL[i].Execution將OL[i]添加到合成列表CL中的所有項，然後返回步驟1711以處理下一目標。
在步驟1715，生成模塊1511將OL[StartObj].Start和OL[i-1].End之間的所有邊緣都分配給IPART。然後，在步驟1717，使用圖2、3A、7和8的方法步驟執行生成任務。然後處理流程進行到步驟1719。如果步驟1707中的條件不滿足(步驟1707的否選項)，則步驟1719還要執行。在步驟1719，檢查i是否小於N，並且OL[i].Composites是否為TRUE。如果這些條件不滿足，執行返回步驟1703。如果條件滿足，(1719的是選項)，然後在步驟1721，生成器1511將當前目標OL[i]添加到合成列表中的所有項(基於OL[i])。然後，生成器使用XPSRM(圖2、3A，12和13的方法步驟)來生成CL[OL[i].CompositeIndex]中的所有目標。索引i被增加，並且執行返回步驟1703以考慮下一目標。
還通過以下偽代碼來說明圖17的方法。
在圖11A的示例中，目標列表由以下目標構成O1，...，O100，O101，O102，O103，O104，O105，O106，...O150，當O1-O100是文本目標1110時，目標O101-O105是向量圖形目標1101-1105，並且目標O106-O150是下一目標1120。
合成列表是CL
＝O150。合成列表是通過顯示列表生成模塊1507來確定的。
在生成期間，因為目標O1-O100不通過邊框與CL
重疊，並且根據優先級都低於CL
，使用一個或多個IPARM來生成O1-O100目標中的每一個。
然後在偽代碼的4和15行之間，通過生成器1511來執行以下工作第7行O101的優先級低於CL
，並通過邊框與CL
重疊，所以將O101添加到CL
。
第11行O102的優先級低於CL
，並通過邊框與CL
重疊，所以將O102添加到CL
。
第11行O103的優先級低於CL
，並通過邊框與CL
重疊，所以將O103添加到CL
。
第11行O104的優先級低於CL
，並通過邊框與CL
重疊，所以將O104添加到CL
。
第9行O105是合成目標所以環終止。
第14行使用IPRM將目標O101、102、103和104生成到幀存儲。
第4行O105是合成目標所以環終止。
第16行，OL[i]＝O105，其具有O105.Composite＝TUE。
第17行因為在合成列表中沒有比O105具有更高優先級的項，所以執行繼續到第18行。
第18行CL
中的項是O105、O101、O102、O103。所以目標O101、O102、O103和O105被分配給XPSRT並被生成到幀存儲。
第3行i＝106。並且在第4行和15行之間，使用一個或多個IPARM來生成其他所有的目標1120。
10.0 其他方案在所有這三種方案的變體中，可以看出在生成期間，一旦生成任務開始，另一個生成任務至少能被識別，同時執行當前任務。如果下一個被識別的生成任務具有不與當前執行的生成任務重疊的邊框。該處理可以繼續，直到下一個被識別的生成任務具有與當前執行的生成任務重疊的邊框，或生成完成。
工業實用性根據上述可以顯見，所述方案可用於計算機和圖像處理工業。
前面只是描述了本發明的一些實施例，在不脫離本發明的範圍和精神的情況下，可以對本發明作出修改和/或改變，這些實施例是說明性的，而不是限制性的。
在本說明書的上下文中，詞語「comprising」意思是「原則上包括但不是唯一的」或「具有」或「包括」，而不是「僅由......構成」的意思。詞語「comprising」的變體是諸如「comprise」和「comprises」，具有相應的變型後的意思。
表A將圖2的方法用於圖1的實例
表B將圖3A的方法用於圖1A的掃描線。
表C將圖7的方法應用到掃描線662的前三個邊緣。
用於掃描線662的有效邊緣列表{AEL)是{E5，E1，E3，E4，E2，E6}第一邊緣E5被處理如下在步驟751，將計數器i初始化為零，將變量clip_delta初始化為零
第二邊緣E1被處理如下在步驟751，將計數器i初始化成0，將變量clip_delta初始化成0
表C(繼續)與E3相關聯的對象被處理如下在步驟751，將計數器i初始化為零，並將變量clip_delta初始化成0
就這點而言，AOL包含對象矩形654。E3和E4之間的像素運行現在可以輸出，該像素運行由存儲在填充F3中的像素數據組成。
表D將第三方案應用到圖11的掃描線1130。
權利要求
1.一種生成由一個圖形目標列表描述的圖像的方法，該方法包括步驟把列表中的目標分配到第一目標集合和第二目標集合中的至少一個；使用第一生成方法生成第一目標集合到圖像存儲器，該第一生成方法確定第一集合中一個目標的一部分是否貢獻於第一目標集合的生成輸出，並且如果是的話，第一生成方法生成該部分；和使用第二生成方法生成第二目標集合到圖像存儲，第二生成方法獨立於第二集合中的其他目標來生成第二集合中的每個目標。
2.根據權利要求1的方法，其中列表中的目標具有從最低優先級目標到最高優先級目標的優先順序，並且列表具有要求合成的最高優先級目標的最後合成目標；其中所述分配步驟包括子步驟將列表中的目標分配到目標的第一集合中，這些目標包括從最低優先級直到且包括最終合成目標的目標；以及將列表中具有比最後合成目標更高優先級的目標分配到第二目標集合中。
3.根據權利要求1的方法，其中列表中的目標具有從最低優先級目標到最高優先級目標的優先順序，並且生成目標以形成像素，其中對於一個或多個將要生成的連續的像素的每一個運行，第一生成方法包括步驟確定在目標第一集合中對像素運行有效的目標；識別具有確定的有效目標的最高優先級的不透明目標；以及生成最高不透明目標和具有比最高不透明目標更高優先級的非不透明有效目標。
4.根據權利要求1的方法，其中列表中的目標具有從最低優先級目標到最高優先級目標的優先順序，並且生成目標以形成像素，其中對於將要生成的連續的像素的每一個運行，第二生成方法包括子步驟檢查第二目標集合中的當前目標是否是有效的，第二集合是以優先級遞增的順序來考慮的；以及如果當前目標是有效的，生成當前的目標到圖像存儲。
5.根據權要求4的方法，其中第二生成方法進一步包括子步驟搜索第二目標集合中的連續目標的一個組，使得該組中的目標與該組中的其他目標不重疊；以及如果找到了這樣的組，將該組中的目標同時生成到圖像存儲中。
6.根據權利要求5的方法，其中由邊界框來表示每個目標的最大範圍，其中該組中目標的邊界框與該組中其它目標的邊界框不重疊。
7.根據權利要求4的方法，其中如果由一個剪切目標對第二目標集合中的多個連續目標進行剪切，使用第一生成方法生成該多個目標。
8.根據權利要求1的方法，進一步包括步驟產生目標列表，其中對於每個目標該列表包括由一個或多個描述該目標的邊緣所組成的一個集合；指示目標的最大範圍的邊界框；以及指示目標是否需要合成的標記。
9.根據權要求8的方法，其中如果由一個或多個剪切目標對目標組進行剪切，被剪切的第一剪切目標和目標組的最後目標之間的邊緣被增加到列表中作為一個單獨的目標。
10.根據權利要求1的方法，其中列表中的目標具有從最低優先級目標到最高優先級目標的優先順序，並且其中所述分配步驟包括子步驟以優先級遞增的順序考慮列表中的目標，並且，對於每個當前考慮的目標這樣處理如果當前的目標不要求合成，將當前的目標放置在目標的第二集合中，以及如果當前的目標要合成，執行步驟(i)確定比當前的目標具有更低優先級且具有與當前目標的邊界框重疊的邊界框的目標；以及(ii)把當前考慮的目標和確定的目標放置在第一目標集合。
11.根據權利要求10的方法，其中確定的目標的位於當前目標邊緣內的那些部分被放置在目標的第一集合中。
12.根據權利要求1的方法，其中圖像存儲器是一個分段存儲器，其存儲圖像的當前考慮的部分，並且其中第一和第二生成方法生成出現在圖像的當前考慮的部分中的目標。
13.根據權利要求1的方法，其中所述分配步驟將目標分配到第一生成任務和第二生成任務，用於分別由第一生成方法和第二生成方法進行生成，其中多個生成任務是同時處理的。
14.一種用於生成基於目標的圖像的方法，該方法包括步驟接收顯示列表，其按照從最低優先級到最高優先級的優先級順序列出圖像的目標，其中該顯示列表具有一個最後合成目標，該最後合成目標是要求合成的最高優先級的目標；處理第一生成任務，第一生成任務操作顯示列表中從最低優先級目標直到且包括最後的合成目標的目標；和處理至少一個第二生成任務，該任務操作顯示列表中具有比最後合成目標更高優先級的一個或多個目標，其中第一生成任務確定目標的一部分是否貢獻於由第一生成任務處理的目標的生成輸出，並且如果是的話，生成該部分，並且其中第二生成任務獨立於由第二生成任務處理的其它目標，將目標生成到圖像存儲。
15.根據權利要求14的方法，其中將多個不重疊和具有連續優先級順序的目標分配給一個單個的第二生成任務。
16.一種形成由表示為圖形目標的數據所描述的圖像的方法，該方法包括步驟(a)接收描述圖像的目標的列表，其中按從最低優先級目標到最高優先級目標的優先順序對目標排序；(b)按遞增優先級的順序考慮列表中的目標，並且對於每個當前考慮的目標這樣處理(ba)如果當前考慮的目標不要求合成，使用第一生成方法生成當前考慮的目標到圖像存儲；並且(bb)如果當前考慮的目標要求合成，執行列步驟(bb)(i)確定列表中具有比當前考慮的目標更低優先級且具有與當前考慮的目標的邊界框重疊的邊界框的目標；以及bb(ii)使用第二生成方法生成當前考慮的目標和已經確定的目標，該第二生成方法確定一個目標的一部分是否貢獻於由第二生成方法處理的目標集合的生成輸出，如果是的話，該第二生成方法生成該部分。
17.根據權利要求16的方法，其中步驟(bb)(ii)生成位於當前考慮目標的邊緣內的確定目標的區域。
18.一種生成基於目標的圖像的方法，該方法包括步驟(a)接收顯示列表，該列表按從最低優先級目標到最高優先級目標的優先順序列出圖像中的目標；(b)根據至少一個預定的標準，把顯示列表中的目標分配到第一目標集合和第二目標集合中的至少一個；(c)使用第一生成方法生成第一目標集合中的目標；並且(d)使用第二生成方法生成第二目標集合中的目標，其中，對於每輪將要生成的順序像素，第一生成方法包括下列步驟(ca)確定第一目標集合中的對於像素的運行是有效的目標；(cb)識別具有已確定的有效目標的最高優先級的不透明目標；以及(cc)生成最高級的不透明目標和具有比最高級的不透明目標更高優先級的非不透明的有效目標；而且其中，對於每輪將要生成的順序像素，第二生成方法包括下列步驟(da)檢查第二目標集合中的當前目標是否是有效的，第二目標集合是按遞增優先級順序考慮的；和(db)如果當前目標是有效的，生成當前目標到圖像存儲。
19.一種生成基於目標的圖像的方法，該方法包括步驟按從最低優先級目標到最高優先級目標的優先順序接收圖像中的目標列表；將列表中的目標分配到至少一個目標集合中，其中該集合中的目標在列表中具有連續的優先順序，且其中集合中的每個目標不與集合中的任何其它目標重疊；生成至少一個目標集合到圖像存儲。
20.根據權利要求19的方法，其中該列表具有一個最後合成目標，該目標是要求合成的最高優先級目標，其中所述分配步驟考慮列表中具有比最後合成目標更高優先級的目標，該方法進一步包括步驟使用一個生成方法生成列表中最低優先級目標到最高優先級的目標，該方法確定目標的一部分是否貢獻於列表種目標的生成輸出，如果是的話，該生成方法生成該部分。
21.一種生成由一個圖形目標列表所描述的圖像的方法，該方法包括步驟把列表中的目標分配到第一目標集合和第二目標集合中的至少一個；使用像素順序生成方法生成第一集合中的目標；並且使用畫具運算生成法生成在第二集合中的目標。
22.一種用於生成由一個圖形目標列表所描述的圖像的設備，該設備包括第一裝置，使用第一生成方法生成目標到圖像存儲，該第一生成方法確定目標的一部分是否貢獻於由所述第一裝置處理的目標集合的生成輸出，如果是的話，所述第一裝置生成該部分；第二裝置，使用第二生成方法生成目標到圖像存儲，該第二方法獨立於由所述的第二裝置接收到的其它目標來生成由所述第二裝置接收的每個目標；以及用於把列表中的圖形目標分配到所述第一裝置和所述第二裝置中的至少一個的裝置。
23.根據權利要求22的設備，進一步包括用於生成圖形目標列表的裝置。
24.一種用於生成基於目標的圖像的設備，該設備包括第一裝置，使用第一生成方法生成目標到圖像存儲，該第一生成方法確定目標的一部分是否貢獻於由所述第一裝置處理的目標集合的生成輸出，如果是的話，所述第一裝置生成該部分；第二裝置，使用第二生成方法生成目標到圖像存儲，該第二生成方法獨立於由所述第二裝置接收到的其它目標生成由所述第二裝置接收到的每個目標；用於接收圖像中的目標列表的裝置，其中按從最低優先級目標到最高優先級目標的優先順序對列表中的目標排序，並且列表具有最後合成目標，它是要求合成的最高優先級的目標；用於把目標分配到所述用於生成的第一裝置和用於生成的第二裝置的裝置，其中所述用於分配的裝置把從最低優先級目標到且包括最後合成目標的列表的第一部份分配到所述用於生成的所述第一裝置，並且將一個或多個優先級高於最後合成目標的目標分配到所述用於生成的所述第二裝置。
25.根據權利要求24的設備，其中所述用於分配的裝置同時將多個目標分配到用於生成的第二裝置，其中多個目標不重疊，且在列表中具有連續的優先級位置。
26.一種根據權利要求24的設備，包括多個用於生成的第二裝置。
27.一種用於生成基於目標的圖像的設備，該設備包括第一裝置，使用第一生成方法生成目標到圖像存儲，該第一生成方法確定目標的一部分是否貢獻於由所述第一裝置處理的目標集合的生成輸出，如果是的話，所述第一裝置生成該部分；第二裝置，使用第二生成方法生成目標到圖像存儲，該第二生成方法獨立於其它接收的目標生成由所述第二裝置接收到的每個目標；用於接收圖像中的目標列表的裝置，，其中按從最低優先級目標到最高優先級目標的優先順序對目標排序；用於對於一個要求合成的目標確定列表中目標的裝置，，這些目標具有比合成的目標更低優先級且具有與合成的目標的邊界框重疊的邊界框；用於把非合成目標從列表中分配到用於生成的第二裝置的裝置；和用於從列表中把合成目標，連同由所述用於確定的裝置為每個合成目標確定的目標分配到用於生成的第一裝置的裝置。
28.一種用於生成基於目標的圖像的設備，該設備包括用於按從最低優先級目標到最高優先級目標的優先順序接收圖像中的目標列表的裝置；用於將列表中的目標分配到至少一個目標集合的裝置，其中集合中的目標在列表中具有連續的優先順序，且其中集合中的每個目標不與集合中的任何其它目標重疊；以及用於生成至少一個目標集合到圖像存儲的裝置。
29.一種用於生成基於目標的圖像的系統，該系統包括一個或多個第一生成器，使用第一生成方法生成目標到圖像存儲，該第一生成方法確定目標的一部分是否貢獻於由所述第一裝置處理的目標集合的生成輸出，如果是的話，所述第一裝置生成該部分；一個或多個第二生成器，使用第二生成方法生成目標，該第二方法獨立於其它接收的目標來生成由所述第二裝置接收的每個目標到圖像存儲；一個顯示列表發生器，產生用於圖像中的目標列表，其中按從最低優先級目標到最高優先級目標的優先順序對列表中的目標排序，並且列表具有最後合成目標，該目標是要求合成的最高優先級目標；顯示列表存儲器，存儲由所述顯示列表發生器產生的列表；和與所述顯示列表存儲器和所述第一和第二生成器通信的處理器，其中將處理器編程為把從最低優先級目標直到且包括最後合成目標的目標分配到第一生成器中，並且把具有比最後合成目標更高優先級的目標分配到一個或多個第二生成器。
30.一種用於生成基於目標的圖像的系統，該系統包括一個或多個第一生成器，使用第一生成方法生成目標到圖像存儲，該第一生成方法確定目標的一部分是否貢獻於由第一生成方法處理的一個目標集合的生成輸出，並且，如果是的話，第一生成方法生成該部分；一個或多個第二生成器，使用第二生成方法生成目標，該第二方法獨立於其它接收的目標來生成由所述第二裝置接收的每個目標到圖像存儲；一個顯示列表發生器，產生圖像中的一個目標列表，其中按從從最低優先級目標到最高優先級目標的優先順序對列表中的目標排序；一個顯示列表存儲器，存儲由所述顯示列表發生器產生的列表；以及與所述顯示列表存儲器和所述第一和第二生成器通信的處理器，其中處理器被編程為執行下列步驟(i)按優先級遞增的順序考慮列表中的目標，並且，對於每個當前考慮的目標這樣處理(ii)如果當前目標不要求合成，將當前目標分配到第二生成器；和(iii)如果當前目標要求合成，確定列表中比當前考慮的目標具有更低優先級，並且具有與當前考慮的目標的邊界框重疊的邊界框的目標，並且把當前考慮的目標和確定的目標分配到第一生成器。
31.一種包括記錄在機讀記錄介質上的機讀程序代碼的電腦程式產品，用於控制數據處理設備的操作，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟把列表中的目標分配到第一目標集合和第二目標集合中的至少一個；使用第一生成方法生成目標到圖像存儲，該第一生成方法確定第一集合的一個目標的一部分是否貢獻於目標第一集合的生成輸出，並且，如果是的話，第一生成方法生成該部分；以及使用第二生成方法生成第二目標集合到圖像存儲，該第二方法獨立於第二集合中的其它目標來生成第二集合中的每個目標。
32.一種包括記錄在機讀記錄介質上的機讀程序代碼的電腦程式產品，用於控制數據處理設備的操作，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟接收顯示列表，其按從最低優先級目標到最高優先級目標的優先順序列出圖像中的目標，其中顯示列表具有最後合成目標，它是要求合成的最高優先級的目標；使用第一生成方法生成第一生成任務，第一個生成任務包括顯示列表中從最低優先級目標直到最後合成目標的目標；並且使用第二生成方法生成一個或多個第二生成任務，第二生成任務包括顯示列表中具有比最後合成目標更高優先級的一個或多個目標，其中第一生成方法確定目標的一部分是否貢獻於第一生成任務的生成輸出，如果是這樣的話，第一生成的方法生成該部分，並且其中第二生成方法獨立於第二生成任務中的其它目標生成第二生成任務中的每個目標到圖像存儲器。
33.一種電腦程式產品，包括記錄在機讀記錄介質上的機讀程序代碼，用於控制該數據處理設備的操作，在數據處理設備上執行基於目標的圖像的生成方法，該方法包括步驟(a)接收描述圖像的目標列表，其中按從最低優先級目標到最高優先級目標的優先順序對目標排序；(b)按優先級遞增的順序考慮列表中的目標，並且，對於每個當前考慮的目標這樣處理(ba)如果當前考慮的目標不要求合成，使用第一生成方法生成當前考慮的目標到圖像存儲；並且(bb)如果當前考慮的目標要求合成，執行下列步驟(bb)(i)確定列表中具有比當前考慮的目標更低優先級且具有與當前考慮的目標的邊界框重疊的邊界框的目標；和(bb)(ii)使用第二生成方法生成當前考慮的目標和確定的目標，該第二生成方法確定目標的一部分是否貢獻於由第二生成方法處理的目標集合的生成輸出，並且，如果這樣的話，第二生成方法生成該部分。
34.一種包括記錄在機讀記錄介質上的機讀程序代碼的電腦程式產品，用於控制數據處理設備的操作，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟按從最低優先級目標到最高優先級目標的優先順序接收圖像中目標的列表；分配列表中的目標到至少一組目標，其中集合中的目標在列表中具有連續的優先順序，而且其中集合中的每個目標不與集合中任何其它目標重疊；生成至少一個目標集合到圖像存儲。
35.一種包括記錄在機讀記錄介質上的機讀程序代碼的電腦程式，用於控制數據處理設備的操作，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟把列表中的目標分配到第一目標集合和第二目標聚合中的至少一個；使用第一生成方法生成第一目標集合到圖像存儲器，該第一生成方法確定第一集合中的目標的一部分是否貢獻於第一集合的生成輸出，並且如果是的話，第一生成方法生成該部分；以及使用第二生成方法生成第二目標集合到圖像存儲，該第二生成方法獨立於第二集合中的其它目標生成第二集合中的每個目標。
36.一種包括機讀程序代碼的電腦程式，用於控制數據處理設備的操作，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟接收顯示列表，該列表按從最低優先級目標到最高優先級目標的優先順序列出圖像中的目標，其中顯示列表具有最後合成目標，它是要求合成的最高優先級的目標；使用第一生成方法生成第一生成任務，第一個生成任務包括從最低優先級目標直到並且包括最後合成目標的顯示列表中的目標；並且使用第二生成方法生成一個或多個第二生成任務，第二生成任務包括顯示列表中具有比最後合成目標更高優先級的一個或多個目標，其中第一生成方法確定目標的一部分是否貢獻於第一生成任務的生成輸出，如果是的話，第一生成方法生成該部分，並且其中第二生成方法獨立於第二生成任務中的其它目標，生成第二生成任務中的每個目標到圖像存儲器。
37.一種包括用於控制數據處理設備操作的機讀程序代碼的電腦程式，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟(a)接收描述圖像的目標列表，其中按從最低優先級目標到最高優先級目標的優先順序對目標排序；(b)按遞增優先級的順序來考慮列表中的目標，並且，對於每個當前考慮的目標這樣處理(ba)如果當前考慮的目標不要求合成，使用第一生成方法生成當前考慮的目標到圖像存儲；並且(bb)如果當前考慮的目標要求合成，執行下列步驟(bb(i)確定列表中具有比當前考慮的目標更低優先級，並且具有與當前考慮的目標的邊界框重疊的邊界框的目標；和(bb)(i)使第二生成方法生成當前考慮的目標和確定的目標，第二生成方法確定目標的一部分是否貢獻於由第二生成方法處理的目標集合的生成輸出，並且，如果是的話，第二生成方法生成該部分。
38.一種包括用於控制數據處理設備操作的機讀程序代碼的電腦程式，程序代碼在數據處理設備上執行以便執行生成基於目標的圖像的方法，該方法包括下列步驟按從最低優先級目標到最高優先級目標的優先順序接收圖像中目標的列表；分配列表中的目標到至少一個目標集合，其中集合中的目標在列表中具有連續的優先順序，而且其中集合中的每個目標不與集合中任何其它目標相重疊；生成至少一個目標集合到圖像存儲。
全文摘要
描述了一種生成基於目標的圖像的方法。該方法接收圖像(950)中的目標(951－955)列表，該列表按從最低優先級目標(951)到最高優先級目標(955)的優先級順序排列這些目標。將這些目標分配到第一目標集合(951，952)和/或第二目標集合(953，955)。如果目標的一部分在第一集合中是可見的，則使用僅僅生成部分目標的第一生成方法生成第一目標集合到目標存儲，並且使用第二生成方法生成目標的第二集合到圖像存儲，該第二方法獨立於第二集合中的其他目標生成每個目標。可以基於最高合成目標(952)的優先級順序進行分配。可以基於重疊目標(1101，1102，1103，1105)的組進行分配，其中在該組中的一個目標(1105)請求合成。
文檔編號G06T15/50GK1797432SQ20051013732
公開日2006年7月5日 申請日期2005年6月30日 優先權日2004年6月30日
發明者戴維·C.·史密斯 申請人:佳能株式會社