[發明專利]用于對橢圓弧進行柵格化的方法和系統

有效

• 申請號: 201110039950.1
• 申請日: 2011-02-16
• 公開（公告）號: CN102646281A
• 公開（公告）日: 2012-08-22
• 發明（設計）人: 譚志明;白向暉;王琪;洲鐮康
• 申請（專利權）人: 富士通株式會社
• 主分類號: G06T11/00
• 分類號: G06T11/00
• 代理公司: 北京東方億思知識產權代理有限責任公司 11258
• 代理人: 宋鶴

技術領域

本發明涉及計算機圖形處理領域，更具體地涉及一種用于對橢圓弧進行柵格化的方法和系統。

背景技術

柵格化是計算機圖形學中將圖元掃描變換成顯示像素的一種技術，是將矢量圖形格式表示的圖像變換成柵格圖像以用于顯示器或打印機等的輸出的過程。對圖元進行柵格化的過程主要包括兩個步驟：首先，確定顯示平面上哪些像素被圖元覆蓋；然后，將圖元的屬性(顏色、深度、以及紋理等)賦給由該圖元覆蓋的每個像素。

當前，存在兩種用于對橢圓弧進行柵格化的方法：中點法和最小函數值法。在利用中點法對橢圓弧進行柵格化的過程中，以橢圓弧所在橢圓的中心為基準將橢圓弧所在橢圓平均劃分為八個八分圓象限，并且根據在橢圓弧的走向上當前已經完成描畫的像素所在象限中的與當前已經完成描畫的像素相鄰的兩個像素之間的中點相對于橢圓弧所在橢圓的曲線函數的函數值的絕對值來判斷這兩個像素中的哪一個像素將被選擇作為下一個將要描畫的像素。在利用最小函數值法對橢圓弧進行柵格化的過程中，將橢圓弧切線方向的任意一個像素相對于橢圓弧所在橢圓的曲線函數的函數值的絕對值看作該像素到橢圓弧的距離，將當前已經完成描畫的像素的兩個以上相鄰像素中函數值的絕對值最小的一個相鄰像素看作最接近橢圓弧的像素，并將該函數值的絕對值最小的像素作為下一個將要描畫的像素。

利用中點法對橢圓弧進行柵格化存在兩個問題：1)由于該方法將橢圓弧所在橢圓劃分成了八個八分圓象限，所以當從一個象限切換到另一個象限時需要重新計算用于選擇下一個將要描畫的像素的參數，這使得實現中點法的裝置結構設計復雜，并且增加了計算時間；2)當橢圓弧所在橢圓非常細時(即，橢圓的短軸遠小于橢圓的長軸時)，將無法使用中點法來完成對橢圓弧的柵格化。

利用最小函數值法對橢圓弧進行柵格化也存在兩個問題：1)由于像素相對于橢圓弧所在橢圓的曲線函數的函數值的絕對值不是該像素到橢圓弧的精確距離，所以當橢圓弧所在橢圓非常細時，可能會得出錯誤的結果；2)需要一種復雜的追蹤方法來沿著橢圓弧逐像素地進行追蹤。

發明內容

鑒于以上問題，本發明提供了一種新穎的用于對橢圓弧進行柵格化的方法和系統。

根據本發明一個方面的用于對橢圓弧進行柵格化的方法包括：找出與當前已經完成描畫的像素正方形C相鄰的像素正方形A0至A7中在橢圓弧的走向上與橢圓弧相交的一個或多個像素正方形；從所述一個或多個像素正方形中選擇距離橢圓弧最近的像素正方形作為下一個將要描畫的像素正方形。

根據本發明另一方面的用于對橢圓弧進行柵格化的系統包括：相交像素獲取單元，用于找出與當前已經完成描畫的像素正方形C相鄰的像素正方形A0至A7中在橢圓弧的走向上與橢圓弧相交的一個或多個像素正方形；相交像素選擇單元，用于從所述一個或多個像素正方形中選擇距離橢圓弧最近的像素正方形作為下一個將要描畫的像素正方形。

相對于現有的兩種用于對橢圓弧進行柵格化的方法來說，本發明可以涵蓋所有情況，包括橢圓退化成扁平狀(即，長軸遠大于短軸的橢圓的情況)；其次，本發明使用的逐點跟蹤方法簡單有效，相對于中點法來說它不需要分成8個象限并在這些象限中切換，相對于最小函數值法來說它不需要使用弧的梯度向量；最后，本發明使用與像素正方形相交來進行判斷的方法，相對于最小函數法的精度要高一點，前者只需要判斷1到3個像素，而后者需要判斷至少3個像素。

附圖說明

從下面結合附圖對本發明的具體實施方式的描述中可以更好地理解本發明，其中：

圖1示出了根據本發明一個實施例的用于對橢圓弧進行柵格化的系統的框圖；

圖2示出了根據本發明一個實施例的用于對橢圓弧進行柵格化的方法的流程圖；

圖3示出了橢圓弧與當前已經完成描畫的像素正方形的相鄰像素正方形的相交情形；

圖4示出了根據本發明另一實施例的用于對橢圓弧進行柵格化的系統的框圖；以及

圖5示出了橢圓弧與當前已經完成描畫的像素正方形的正方形邊的相交情形。

具體實施方式

下面將詳細描述本發明各個方面的特征和示例性實施例。下面的描述涵蓋了許多具體細節，以便提供對本發明的全面理解。但是，對于本領域技術人員來說顯而易見的是，本發明可以在不需要這些具體細節中的一些細節的情況下實施。下面對實施例的描述僅僅是為了通過示出本發明的示例來提供對本發明更清楚的理解。本發明絕不限于下面所提出的任何具體配置和算法，而是在不脫離本發明的精神的前提下覆蓋了相關元素、部件和算法的任何修改、替換和改進。