用於渲染凹多邊形的方法和裝置的製作方法

2023-06-01 09:52:41

專利名稱：用於渲染凹多邊形的方法和裝置的製作方法
技術領域：
本發明涉及圖形處理領域，更具體地涉及一種用於渲染凹多邊形的方法和裝置。
背景技術：
在計算機圖形學中，有效地渲染凹多邊形是非常困難的事。由於凹多邊形沒有特 定的形狀且頂點數最少為4最多為無限多，所以不太容易判斷一個像素是否處於凹多邊形 內。同時，使用諸如Gouraud著色或者Phong著色的方法來渲染凹多邊形也很困難。一種常用的著色方法是，首先將一個凹多邊形分解為一系列三角形，然後逐步對 每個三角形進行渲染。到目前為止，沒有一種方法可以在線性時間複雜度內完成一個凹多 邊形的三角化分解，因此這個處理非常耗時。另一種常用的著色方法是，按掃描線依次來填充凹多邊形。具體地，首先使用奇偶 測試來判斷像素是否處於凹多邊形內，然後計算掃描線與凹多邊形的相交邊的起始和終止 點，最後在一個跨距內對像素進行描畫。可以使用活動邊表來加速這個處理。但是通過這種 方法渲染的顏色嚴重依賴於掃描線，並且在掃描線的垂直方向邊改變的地方無法連續。另 一種比較巧妙的方法是，通過從起始頂點連接到另兩個連續的頂點所形成的一系列三角形 來判斷像素是否處於凹多邊形內。具體地，測試有多少個三角形覆蓋了這個像素，如果為奇 數，則這個像素處於凹多邊形內，需要描畫；如果為偶數，則不需要描畫。然而，這種方法在 通過訪問內存來判斷像素是否處於凹多邊形內時代價很大，而且只適合單色著色。

發明內容
鑑於以上所述的一個或多個問題，本發明提供了一個新穎的用於渲染凹多邊形的 方法和裝置。根據本發明實施例的用於渲染凹多邊形的方法包括將凹多邊形分割為多個凸多 邊形；判斷將要渲染的像素位於所述多個凸多邊形中的哪一個中；利用所述像素的坐標信 息、以及所述像素所在的凸多邊形的各個頂點的坐標信息和參數信息，獲取用於渲染所述 像素的參數信息；以及利用用於渲染所述像素的參數信息對所述像素進行渲染。根據本發明實施例的用於渲染凹多邊形的裝置包括多邊形分割單元，用於將凹 多邊形分割為多個凸多邊形；位置判斷單元，用於判斷將要渲染的像素位於所述多個凸多 邊形中的哪一個中；參數獲取單元，用於利用所述像素的坐標信息、以及所述像素所在的凸 多邊形的各個頂點的坐標信息和參數信息，獲取用於渲染所述像素的參數信息；以及像素 渲染單元，用於利用用於渲染所述參數的參數信息對所述像素進行渲染。通過本發明，可以以較小的計算量較快地實現對凹多邊形的渲染。


從下面結合附圖對本發明的具體實施方式
的描述中可以更好地理解本發明，其 中
圖1示出了根據本發明一個實施例的用於渲染凹多邊形的裝置的邏輯框圖；圖2示出了根據本發明一個實施例的用於渲染凹多邊形的方法的流程圖；圖3示出了一個示例凹多邊形的標號示例；圖4示出了包括圖1所示裝置的圖形處理系統的邏輯框圖；圖5示出了將凹多邊形分割為若干個子塊的處理的流程圖；圖6示出了一個具有四個頂點的凹多邊形的示例；圖7示出了三種類型的凹頂點的示意圖；圖8示出了圖3所示的凹多邊形的凹頂點的排序示例；圖9示出了從圖3所示凹多邊形分割出的兩個粗分割子塊以及從圖3所示的凹多 邊形的各凹頂點開始的搜索方向；圖10示出了圖3所示的凹多邊形上的所有相交點；圖11示出了在作為搜索起始點的凹頂點向右凹時在邊0上進行搜索的示例；圖12示出了在作為搜索起始點的凹頂點向下凹時在邊0上進行搜索之前的預搜 索的示例；圖13示出了在作為起始點的凹頂點向下凹時在邊1和邊3上進行搜索的示例；圖14示出了從圖3所示的凹多邊形生成的所有子塊；圖15示出了從粗分割子塊生成多個子塊的示例性實現過程；圖16示出了預搜索過程的實現示例；圖17示出了邊0上的搜索過程的實現示例；圖18示出了邊1上的搜索過程的實現示例；圖19示出了邊2上的搜索過程的實現示例；圖20示出了邊3上的搜索過程的實現示例；圖21示出了生成子塊的分離情況；圖22示出了判斷需要渲染的像素屬於哪個子塊的過程；圖23示出了使用Wachspress坐標進行參數插值的方法；圖24示出了根據本發明另一實施例的用於渲染凹多邊形的裝置的邏輯示圖。
具體實施例方式下面將詳細描述本發明各個方面的特徵和示例性實施例。下述實施例的描述涵蓋 了許多具體細節，以便提供對本發明的全面理解。但是，對於本領域技術人員來說顯而易見 的是，本發明可以在不需要這些具體細節中的一些細節的情況下實施。下面對實施例的描 述僅僅是為了通過示出本發明的示例來提供對本發明更清楚的理解。本發明絕不限於下面 所提出的任何具體配置和算法，而是在不脫離本發明的精神的前提下覆蓋了相關元素、部 件和算法的任何修改、替換和改進。圖1和圖2分別示出了根據本發明一個實施例的用於渲染凹多邊形的裝置和方 法的邏輯框圖和流程圖。如圖1所示，該用於渲染凹多邊形的裝置100包括多邊形分割單 元102、位置判斷單元104、參數獲取單元106以及像素渲染單元108。其中，多邊形分割單 元102將凹多邊形分割為多個凸多邊形(S卩，執行步驟S202)；位置判斷單元104判斷將要 渲染的像素位於所述多個凸多邊形中的哪一個中(即，執行步驟S204)；參數獲取單元106利用所述像素的坐標信息、以及所述像素所在的凸多邊形的各個頂點的坐標信息和參數信 息，獲取用於渲染所述像素的參數信息(即，執行步驟S206)；像素渲染單元108利用用於 渲染所述像素的參數信息對所述像素進行渲染(即，執行步驟S208)。多邊形分割單元102進一步包括凹頂點搜索單元1022、粗分割單元1024、邊搜索 單元1026以及細分割單元1028。其中，凹頂點搜索單元1022找出所述凹多邊形的各凹頂 點；粗分割單元1024利用穿過所述各凹頂點的水平線對所述凹多邊形進行粗分割；邊搜索 單元1026將從所述凹多邊形粗分割出的各粗分割多邊形的下側多邊形邊上的最右側的凹 頂點作為起始點，按照順時針或逆時針的順序依次對所述各粗分割多邊形的多邊形邊進行 搜索，以找出所述水平線與所述凹多邊形的一條或多條多邊形邊的相交點和/或所述水平 線穿過的所述凹多邊形的一個或多個頂點；以及細分割單元1028利用所述相交點和/或所 述水平線穿過的所述凹多邊形的一個或多個頂點對所述各粗分割多邊形進行進一步分割， 以將所述凹多邊形分解為所述多個凸多邊形。下面通過示例詳細描述根據本發明一個實施例的用於渲染凹多邊形的裝置和方 法的具體處理過程。作為一個示例，不失一般性地假定凹多邊形的頂點按照逆時針(CCW) 方向標號，坐標系統的X軸正方向指向右邊，Y軸正方向指向上邊。凹多邊形的各條邊的標 號是其起始頂點的標號，例如，如果一條邊由頂點0和頂點1組成，那麼該條邊的標號是0。 圖3示出了一個示例凹多邊形的標號示例。圖4示出了包括圖1所示裝置的圖形處理系統的邏輯框圖。如圖4所示，該圖形 處理系統包括頂點著色器400和圖1所示的裝置100。其中，頂點著色器400處理凹多邊 形的頂點信息，比如各頂點的坐標信息和參數信息(顏色、法向量、紋理坐標等)。用於渲 染凹多邊形的裝置100中的多邊形分割單元102、位置判斷單元104以及參數獲取單元106 例如可以由一個凹多邊形光柵掃描器實現，該光柵掃描器的輸入包括凹多邊形各頂點的坐 標信息和參數信息。用於渲染凹多邊形的裝置100中的像素渲染單元108例如可以由一個 像素著色器實現。其中，多邊形分割單元102可以根據凹多邊形各頂點的坐標信息找出凹多邊形 中的凹頂點，根據凹頂點的Y軸坐標值按照從上到下、從右到左的順序對凹多邊形的各凹 頂點進行排序，然後根據各凹頂點的排序按照從上到下的順序依次生成子塊(即，凸多邊 形)。位置判斷單元104可以對每個子塊逐行進行掃描，以判斷當前像素(即，需要渲染的 像素)處於哪個子塊內。參數獲取單元106可以根據當前像素所在子塊的頂點信息計算獲 得當前像素的參數信息。最後，當前像素的參數信息計算好之後，此像素被送入像素渲染單 元108進行渲染。圖5示出了將凹多邊形分割為若干個子塊的處理的流程圖。如圖5所示，該分割 子塊的處理包括在步驟S2022，找出凹多邊形的凹頂點。圖6示出了一個具有四個頂點的凹多邊形 的示例。下面以圖6所示的凹多邊形的四個頂點(Vc^VnV2J3)為例，說明找出凹多邊形的 凹頂點的具體處理。這裡假設需要檢查V1的凹凸性。首先，計算邊VtlV1的邊方程係數a01 = Y0-Y1b01 = X1-X0
C01 = Xoy1-X1Yor然後，計算頂點V2相對於邊VtlV1的邊方程值e01 (x2, j2) = a01 · x2+b01 · y2+c01如果e(11 (x2, y2) > 0，那麼V1是凸頂點；如果(x2, y2) < 0，那麼V1是凹頂點；如 果e01(x2，y2) = 0，那麼Vc^V1, V2在同一條邊上。當需要檢查頂點V2的凹凸性時，同樣的計算適合(V1, V2, V3)。在圖6所示的凹多 邊形的邊界上遍歷一圈之後，就可以找出所有的凹頂點。該步驟S2022例如可以由凹頂點 搜索單元1022完成。圖7示出了三種類型的凹頂點的示意圖。如圖7所示，凹頂點可以分為三類向上 凹、向左或向右凹、以及向下凹。其中，頂點Vi向上凹的條件是其Y軸坐標值不大於與其相 鄰的兩個頂點的Y軸坐標值，即Cup =Yi^1彡yi&yi+1彡Yi ；頂點Vi向下凹的條件是其Y軸坐標 值不小於與其相鄰的兩個頂點的Y軸坐標值，即Cd_ =Yi^1 ( yi&yi+1 ( Yi ；頂點Vi向左或向 右凹的條件是其Y軸坐標值大於與其相鄰的一個頂點的Y軸坐標值且小於與其相鄰的另一 個頂點的Y軸坐標值，即Clr ( ！ Cup) &( ！ Cd_)。在步驟S2024，從每個凹頂點開始畫一條凹多邊形內的水平線，該水平線與凹多邊 形的一條或多條邊相交從而將此凹多邊形分割為了若干個粗分割子塊。該步驟S2024例如 可以由粗分割單元1024完成。其中，這些相交點將放在該凹多邊形的頂點後面標號。比如， 如果凹多邊形的頂點是從0到5標號的，那麼添加的相交點將從6開始標號。在步驟S2026，對於從凹多邊形分割出的粗分割子塊，將該粗分割子塊的下側邊上 的最右側凹頂點作為起始點，按照順時針或逆時針的順序依次對該粗分割子塊的各條邊進 行搜索，以找出所述水平線與凹多邊形的一條或多條邊的相交點和/或所述水平線穿過的 凹多邊形的一個或多個頂點。具體地，如果該最右側凹頂點是向上凹的，則先按照逆時針的順序對該最右側凹 頂點所在左側粗分割子塊的多條邊進行搜索，再按照順時針的順序對該最右側凹頂點所在 的右側粗分割子塊的多條邊進行搜索；如果該最右側凹頂點是向左或向右凹的，則以從該 最右側凹頂點開始朝向Y軸正方向的搜索方向開始按照順時針或逆時針的順序對該粗分 割子塊的多條邊進行搜索；如果凹頂點是向下凹的，則按照逆時針的順序對該粗分割子塊 的多條邊進行搜索。圖8示出了圖3所示的凹多邊形的凹頂點的排序示例。為了方便生成子塊，可以 根據Y軸坐標值從大(或上)到小(或下)的順序對凹多邊形的凹頂點進行排序。如果存 在多於一個的凹頂點具有相同的Y軸坐標值，則可以將最右邊的凹頂點放在最前面，這樣 可以保證首先獲得最右邊的凹頂點。每個子塊從一個凹頂點開始，該凹頂點是這個子塊的 根。因為凹頂點是從上到下排序的，因此子塊也是從上到下生成的。圖9示出了從圖3所示的凹多邊形分割出的兩個粗分割子塊以及從圖3所示的凹 多邊形的各凹頂點開始的搜索方向。如圖9所示，可以將每個粗分割子塊看作為由四邊組 成邊0，即左邊或右邊；邊1，即上邊；邊2，即右邊或左邊；邊3，即下邊。其中，位於凹多邊 形最上面或最下面的粗分割子塊可能沒有邊1或邊3。如果粗分割子塊存在邊1和邊3，那 麼在這兩邊的每一條邊上至少存在一個凹頂點。如圖9所示，對於每個粗分割子塊的各邊進行搜索的起始點是該粗分割子塊的下
11側邊的最右側凹頂點。從起始點開始，按照凹多邊形頂點的標號順序對邊0、1、2或3進行 搜索。當遇到一個凹頂點或者一個相交點時，邊的號碼就會加1。因此，這個搜索可以根據 粗分割子塊的四邊分為四個階段。為了描述簡單，這裡將具有和凹多邊形的頂點標號相同順序(比如0 — 1 — 2)的 搜索稱為前向搜索；將具有和凹多邊形的頂點標號相反順序(比如2—1 — 0)的搜索稱為 後向搜索。因為起始點可能在左邊也可能在右邊，因此搜索的方向會不同。如果起始點在右 邊，則對該起始點所在的粗分割子塊的邊進行前向搜索；如果起始點在左邊，則對該起始點 所在的粗分割子塊的邊進行後向搜索。如圖9所示，實際上這兩個粗分割子塊的搜索方向 都可以看作向上。如果起始點是向上凹，則對該起始點所在的左側粗分割子塊進行前向搜 索，然後對該起始點所在的右側粗分割子塊進行後向搜索。如果起始點向下凹，則對該起 始點所在的粗分割子塊進行前向搜索，並且需要添加一個預搜索階段(預搜索總是前向搜 索)。可以使用一個雙向頂點鍊表來記錄粗分割子塊的上邊和下邊的頂點。通過使用這 個鍊表，可以知道頂點的前向和後向頂點的標號。在這裡，前向和後向是相對於頂點的標號 順序定義的，如果一個頂點的標號大於當前頂點的標號，那麼它就是在前面；否則就是在後 面。由於左邊和右邊的頂點已具有順序而無需通過其他方式來標號，所以只需要記住粗分 割子塊的上邊和下邊的前向和後向頂點。如果粗分割子塊中的凹頂點是向上凹或者向下凹 的，則它既有前向頂點也有後向頂點；在其他情況下，前向頂點和後向頂點是一樣的。前向或後向頂點可能為添加的相交點，也可能為穿越點。穿越點是與凹多邊形的 一個凹頂點具有相同Y軸坐標值的凹多邊形的一個或多個頂點。因為添加的相交點在凹多 邊形邊上，所以也需要記住這條邊的標號。對於穿越點來說，邊的標號與頂點的標號相同； 而對於相交點來說，邊的標號和頂點的標號不一樣。這個條件可用於將相交點與穿越點區 分開來。用於實現雙向鍊表的數據結構是
權利要求
1.一種用於渲染凹多邊形的方法，包括 將凹多邊形分割為多個凸多邊形；判斷將要渲染的像素位於所述多個凸多邊形中的哪一個中；利用所述像素的坐標信息、以及所述像素所在的凸多邊形的各個頂點的坐標信息和參 數信息，獲取用於渲染所述像素的參數信息；以及利用用於渲染所述像素的參數信息對所述像素進行渲染。
2.根據權利要求1所述的用於渲染凹多邊形的方法，其特徵在於，將所述凹多邊形分 割為所述多個凸多邊形的處理包括找出所述凹多邊形的各凹頂點；利用穿過所述各凹頂點的水平線對所述凹多邊形進行粗分割； 將從所述凹多邊形粗分割出的各粗分割多邊形的下側多邊形邊上的最右側的凹頂點 作為起始點，按照順時針或逆時針的順序依次對所述各粗分割多邊形的多邊形邊進行搜 索，以找出所述水平線與所述凹多邊形的一條或多條多邊形邊的相交點和/或所述水平線 穿過的所述凹多邊形的一個或多個頂點；以及利用所述相交點和/或所述水平線穿過的所述凹多邊形的一個或多個頂點對所述各 粗分割多邊形進行進一步分割，以將所述凹多邊形分割為所述多個凸多邊形。
3.根據權利要求2所述的用於渲染凹多邊形的方法，其特徵在於，找出所述凹多邊形 的凹頂點的處理包括利用所述凹多邊形的一個頂點的坐標信息和所述頂點的一個相鄰頂點的坐標信息，計 算所述頂點與所述一個相鄰頂點之間的凹多邊形邊的邊方程係數；利用所述凹多邊形邊的邊方程係數和所述頂點的另一個相鄰頂點的坐標信息，計算所 述另一個相鄰頂點相對於所述凹多邊形邊的邊方程值；如果所述邊方程值小於零，則判斷所述頂點為所述凹頂點，如果所述邊方程值大於零， 則判斷所述頂點為所述凹多邊形的凸頂點。
4.根據權利要求2所述的用於渲染凹多邊形的方法，其特徵在於，按照從上到下的順 序依次對所述各粗分割多邊形進行進一步分割。
5.根據權利要求4所述的用於渲染凹多邊形的方法，其特徵在於，對於從所述凹多邊 形粗分割出的每一個粗分割多邊形，分四個階段對所述粗分割多邊形的多邊形邊進行搜 索，所述四個階段包括左側邊搜索階段、右側邊搜索階段、上側邊搜索階段以及下側邊搜索 階段，其中在所述左側邊和右側邊搜索階段，當搜索過程中遇到所述相交點、所述水平線穿過的 所述凹多邊形的一個頂點、或者局部最高點時進行到下一個搜索階段，在所述上側邊和下側邊搜索階段，當搜索過程中遇到所述相交點時進行到下一個搜索 階段。
6.根據權利要求5所述的用於渲染凹多邊形的方法，其特徵在於，如果作為所述起始點的凹頂點的Y軸坐標值大於其在所述凹多邊形上的兩個相鄰頂 點的Y軸坐標值，則按照逆時針的順序對所述粗分割多邊形的多邊形邊進行搜索；如果作為所述起始點的凹頂點的Y軸坐標值小於其在所述凹多邊形上的兩個相鄰頂 點的Y軸坐標值，則先按照逆時針的順序對作為所述起始點的凹頂點所在的一個粗分割多邊形的多邊形邊進行搜索，再按照順時針的順序對作為所述起始點的凹頂點所在的另一個 粗分割多邊形的多邊形邊進行搜索；如果作為所述起始點的凹頂點的Y軸坐標值大於其在所述凹多邊形上的一個相鄰頂 點的Y軸坐標值且小於其在所述凹多邊形上的另一個相鄰頂點的Y軸坐標值，則以從所述 起始點開始朝向Y軸正方向的搜索方向開始按照順時針或逆時針的順序對所述粗分割多 邊形的多邊形邊進行搜索。
7.根據權利要求6所述的用於渲染凹多邊形的方法，其特徵在於，當作為所述起始點 的凹頂點的Y軸坐標值大於其在所述凹多邊形上的兩個相鄰頂點的Y軸坐標值時，在所述右側邊搜索階段，如果所述粗分割多邊形的右側多邊形邊的終止點為所述水平 線穿過的所述凹多邊形的一個頂點或局部最高點，則利用所述起始點和所述終止點之間的 連線對所述粗分割多邊形進行進一步分割，接著進行到所述上側邊搜索階段，否則直接進 行到所述上側邊搜索階段；在所述上側邊搜索階段，如果所述粗分割多邊形的上側多邊形邊上存在所述凹多邊形 的一個或多個凹頂點，則利用所述起始點和所述一個或多個凹頂點之間的連線對所述粗分 割多邊形進行進一步分割，接著進行到所述左側邊搜索階段，否則直接進行到所述左側邊 搜索階段；在所述左側邊搜索階段，找出所述粗分割多邊形的左側多邊形邊上的所述相交點或所 述水平線穿過的所述凹多邊形的一個頂點，接著進行到所述下側邊搜索階段；在所述下側邊搜索階段，如果所述粗分割多邊形的下側多邊形邊上存在除了所述起始 點以外的所述凹多邊形的一個或多個凹頂點，則利用所述一個或多個凹頂點和所述粗分割 多邊形的上側多邊形邊上的最左側的一個凹頂點之間的連線對所述粗分割多邊形進行進 一步分割，並將在所述左側邊搜索階段找出的所述相交點或所述水平線穿過的所述凹多邊 形的一個頂點添加在分割出的所述多個凸多邊形中，另外還要補充搜索處於所述起始點右側的所述粗分割多邊形的下側多邊形邊，以找出處於 所述粗分割多邊形的下側多邊形邊的最右側的所述相交點或所述水平線穿過的所述凹多 邊形的一個頂點，並將補充搜索出的所述相交點或所述水平線穿過的所述凹多邊形的一個 頂點添加在分割出的所述多個凸多邊形中，並且還要將處於所述粗分割多邊形的下側多邊形邊下側的凹多邊形部分作為獨立的凸多 邊形添加到所述多個凸多邊形中。
8.根據權利要求6所述的用於渲染凹多邊形的方法，其特徵在於，當作為所述起始點 的凹頂點的Y軸坐標值大於其在所述凹多邊形上的一個相鄰頂點的Y軸坐標值且小於其在 所述凹多邊形上的另一個相鄰頂點的Y軸坐標值時，在所述左側或右側邊搜索階段，如果所述粗分割多邊形的左側或右側多邊形邊的終 止點為所述水平線穿過的所述凹多邊形的一個頂點或局部最高點，則利用所述起始點和所 述終止點之間的連線對所述粗分割多邊形進行進一步分割，接著進行到所述上側邊搜索階 段，否則直接進行到所述上側邊搜索階段；在所述上側邊搜索階段，如果所述粗分割多邊形的上側多邊形邊上存在所述凹多邊形 的一個或多個凹頂點，則利用所述起始點和所述一個或多個凹頂點之間的連線對所述粗分 割多邊形進行進一步分割，接著進行到所述右側或左側邊搜索階段，否則直接進行到所述右側或左側邊搜索階段；在所述右側或左側邊搜索階段，找出所述粗分割多邊形的右側或左側多邊形邊上的 所述相交點或所述水平線穿過的所述凹多邊形的一個頂點，接著進行到所述下側邊搜索階 段；在所述下側邊搜索階段，如果所述粗分割多邊形的下側多邊形邊上存在除了所述起始 點以外的所述凹多邊形的一個或多個凹頂點，則利用所述一個或多個凹頂點和所述粗分割 多邊形的上側多邊形邊上的最右側或最左側的一個凹頂點之間的連線對所述粗分割多邊 形進行進一步分割，並將在所述右側或左側邊搜索階段找出的所述相交點或所述水平線穿 過的所述凹多邊形的一個頂點添加在分割出的所述多個凸多邊形中。
9.根據權利要求6所述的用於渲染凹多邊形的方法，其特徵在於，當作為所述起始點 的凹頂點的Y軸坐標值小於其在所述凹多邊形上的兩個相鄰頂點的Y軸坐標值時，在所述右側邊搜索階段，如果所述粗分割多邊形的右側多邊形邊的終止點為所述水平 線穿過的所述凹多邊形的一個頂點，則利用所述起始點和所述終止點之間的連線對所述粗 分割多邊形進行進一步分割，接著進行到所述左側邊搜索階段，否則直接進行到所述左側 邊搜索階段；在所述左側邊搜索階段，找出所述粗分割多邊形的左側多邊形邊上的所述相交點或所 述水平線穿過的所述凹多邊形的一個頂點，接著進行到所述下側邊搜索階段；在所述下側邊搜索階段，如果所述粗分割多邊形的下側多邊形邊上存在除了所述起始 點以外的所述凹多邊形的一個或多個凹頂點，則利用所述一個或多個凹頂點和所述粗分割 多邊形的上側多邊形邊上的最左側的一個凹頂點之間的連線對所述粗分割多邊形進行進 一步分割，並將在所述左側邊搜索階段找出的所述相交點或所述水平線穿過的所述凹多邊 形的一個頂點添加在分割出的所述多個凸多邊形中。
10.根據權利要求1至9中任一項所述的用於渲染凹多邊形的方法，其特徵在於，通過 使用Wachspress坐標的參數插值方法獲取用於渲染所述像素的參數信息。
11.一種用於渲染凹多邊形的裝置，包括多邊形分割單元，用於將凹多邊形分割為多個凸多邊形； 位置判斷單元，用於判斷將要渲染的像素位於所述多個凸多邊形中的哪一個中； 參數獲取單元，用於利用所述像素的坐標信息、以及所述像素所在的凸多邊形的各個 頂點的坐標信息和參數信息，獲取用於渲染所述像素的參數信息；以及像素渲染單元，用於利用用於渲染所述像素的參數信息對所述像素進行渲染。
12.根據權利要求11所述的用於渲染凹多邊形的裝置，其特徵在於，所述多邊形分割 單元包括凹頂點搜索單元，用於找出所述凹多邊形的各凹頂點；粗分割單元，用於利用穿過所述各凹頂點的水平線對所述凹多邊形進行粗分割； 邊搜索單元，用於將從所述凹多邊形粗分割出的各粗分割多邊形的下側多邊形邊上的 最右側的凹頂點作為起始點，按照順時針或逆時針的順序依次對所述各粗分割多邊形的多 邊形邊進行搜索，以找出所述水平線與所述凹多邊形的一條或多條多邊形邊的相交點和/ 或所述水平線穿過的所述凹多邊形的一個或多個頂點；以及細分割單元，用於利用所述相交點和/或所述水平線穿過的所述凹多邊形的一個或多個頂點對所述各粗分割多邊形進行進一步分割，以將所述凹多邊形分解為所述多個凸多邊形。
13.根據權利要求12所述的用於渲染凹多邊形的裝置，其特徵在於，所述凹頂點搜索 單元找出所述凹多邊形的凹頂點的處理包括利用所述凹多邊形的一個頂點的坐標信息和所述頂點的一個相鄰頂點的坐標信息，計 算所述頂點與所述一個相鄰頂點之間的凹多邊形邊的邊方程係數；利用所述凹多邊形邊的邊方程係數和所述頂點的另一個相鄰頂點的坐標信息，計算所 述另一個相鄰頂點相對於所述凹多邊形邊的邊方程值；以及如果所述邊方程值小於零，則判斷所述頂點為所述凹頂點，如果所述邊方程值大於零， 則判斷所述頂點為所述凹多邊形的凸頂點。
14.根據權利要求12所述的用於渲染凹多邊形的裝置，其特徵在於，所述粗分割單元 按照從上到下的順序依次對所述各粗分割多邊形進行進一步分割。
15.根據權利要求14所述的用於渲染凹多邊形的裝置，其特徵在於，對於從所述凹多 邊形粗分割出的每一個粗分割多邊形，所述邊搜索單元分四個階段對所述粗分割多邊形的 多邊形邊進行搜索，所述四個階段包括左側邊搜索階段、右側邊搜索階段、上側邊搜索階段 以及下側邊搜索階段，其中在所述左側邊和右側邊搜索階段，當搜索過程中遇到所述相交點、所述水平線穿過的 所述凹多邊形的一個頂點、或者局部最高點時進行到下一個搜索階段，在所述上側邊和下側邊搜索階段，當搜索過程中遇到所述相交點時進行到下一個搜索 階段。
16.根據權利要求15所述的用於渲染凹多邊形的裝置，其特徵在於，如果作為所述起始點的凹頂點的Y軸坐標值大於其在所述凹多邊形上的兩個相鄰頂 點的Y軸坐標值，則所述邊搜索單元按照逆時針的順序對所述粗分割多邊形的多邊形邊進 行搜索；如果作為所述起始點的凹頂點的Y軸坐標值小於其在所述凹多邊形上的兩個相鄰頂 點的Y軸坐標值，則所述邊搜索單元先按照逆時針的順序對作為所述起始點的凹頂點所在 的一個粗分割多邊形的多邊形邊進行搜索，再按照順時針的順序對作為所述起始點的凹頂 點所在的另一個粗分割多邊形的多邊形邊進行搜索；如果作為所述起始點的凹頂點的Y軸坐標值大於其在所述凹多邊形上的一個相鄰頂 點的Y軸坐標值且小於其在所述凹多邊形上的另一個相鄰頂點的Y軸坐標值，則所述邊搜 索單元以從所述起始點開始朝向Y軸正方向的搜索方向開始按照順時針或逆時針的順序 對所述粗分割多邊形的多邊形邊進行搜索。
17.根據權利要求16所述的用於渲染凹多邊形的裝置，其特徵在於，當作為所述起始 點的凹頂點的Y軸坐標值大於其在所述凹多邊形上的兩個相鄰頂點的Y軸坐標值時，在所述右側邊搜索階段，如果所述粗分割多邊形的右側多邊形邊的終止點為所述水平 線穿過的所述凹多邊形的一個頂點或局部最高點，則所述細分割單元利用所述起始點和所 述終止點之間的連線對所述粗分割多邊形進行進一步分割，接著所述邊搜索單元將搜索進 行到所述上側邊搜索階段，否則所述邊搜索單元直接將搜索進行到所述上側邊搜索階段；在所述上側邊搜索階段，如果所述粗分割多邊形的上側多邊形邊上存在所述凹多邊形的一個或多個凹頂點，則所述細分割單元利用所述起始點和所述一個或多個凹頂點之間的 連線對所述粗分割多邊形進行進一步分割，接著所述邊搜索單元將搜索進行到所述左側邊 搜索階段，否則所述邊搜索單元直接將搜索進行到所述左側邊搜索階段；在所述左側邊搜索階段，所述邊搜索單元找出所述粗分割多邊形的左側多邊形邊上的 所述相交點或所述水平線穿過的所述凹多邊形的一個頂點，接著將搜索進行到所述下側邊 搜索階段；在所述下側邊搜索階段，如果所述粗分割多邊形的下側多邊形邊上存在除了所述起始 點以外的所述凹多邊形的一個或多個凹頂點，則所述細分割單元利用所述一個或多個凹頂 點和所述粗分割多邊形的上側多邊形邊上的最左側的一個凹頂點之間的連線對所述粗分 割多邊形進行進一步分割，並將在所述左側邊搜索階段找出的所述相交點或所述水平線穿 過的所述凹多邊形的一個頂點添加在分割出的所述多個凸多邊形中。
18.根據權利要求16所述的用於渲染凹多邊形的裝置，其特徵在於，當作為所述起始 點的凹頂點的Y軸坐標值大於其在所述凹多邊形上的一個相鄰頂點的Y軸坐標值且小於其 在所述凹多邊形上的另一個相鄰頂點的Y軸坐標值時，在所述左側或右側邊搜索階段，如果所述粗分割多邊形的左側或右側多邊形邊的終止 點為所述水平線穿過的所述凹多邊形的一個頂點或局部最高點，則所述細分割單元利用所 述起始點和所述終止點之間的連線對所述粗分割多邊形進行進一步分割，接著所述邊搜索 單元將搜索進行到所述上側邊搜索階段，否則所述邊搜索單元直接將搜索進行到所述上側 邊搜索階段；在所述上側邊搜索階段，如果所述粗分割多邊形的上側多邊形邊上存在所述凹多邊形 的一個或多個凹頂點，則所述細分割單元利用所述起始點和所述一個或多個凹頂點之間的 連線對所述粗分割多邊形進行進一步分割，接著所述邊搜索單元將搜索進行到所述右側或 左側邊搜索階段，否則所述邊搜索單元直接將搜索進行到所述右側或左側邊搜索階段；在所述右側或左側邊搜索階段，所述邊搜索單元找出所述粗分割多邊形的右側或左側 多邊形邊上的所述相交點或所述水平線穿過的所述凹多邊形的一個頂點，接著將搜索進行 到所述下側邊搜索階段；在所述下側邊搜索階段，如果所述粗分割多邊形的下側多邊形邊上存在除了所述起始 點以外的所述凹多邊形的一個或多個凹頂點，則所述細分割單元利用所述一個或多個凹頂 點和所述粗分割多邊形的上側多邊形邊上的最右側或最左側的一個凹頂點之間的連線對 所述粗分割多邊形進行進一步分割，並將在所述右側或左側邊搜索階段找出的所述相交點 或所述水平線穿過的所述凹多邊形的一個頂點添加在分割出的所述多個凸多邊形中。
19.根據權利要求16所述的用於渲染凹多邊形的裝置，其特徵在於，當作為所述起始 點的凹頂點的Y軸坐標值小於其在所述凹多邊形上的兩個相鄰頂點的Y軸坐標值時，在所述右側邊搜索階段，如果所述粗分割多邊形的右側多邊形邊的終止點為所述水平 線穿過的所述凹多邊形的一個頂點，則所述細分割單元利用所述起始點和所述終止點之間 的連線對所述粗分割多邊形進行進一步分割，接著所述邊搜索單元將搜索進行到所述左側 邊搜索階段，否則所述邊搜索單元直接將搜索進行到所述左側邊搜索階段；在所述左側邊搜索階段，所述邊搜索單元找出所述粗分割多邊形的左側多邊形邊上的 所述相交點或所述水平線穿過的所述凹多邊形的一個頂點，接著將搜索進行到所述下側邊搜索階段；在所述下側邊搜索階段，如果所述粗分割多邊形的下側多邊形邊上存在除了所述起始 點以外的所述凹多邊形的一個或多個凹頂點，則所述細分割單元利用所述一個或多個凹頂 點和所述粗分割多邊形的上側多邊形邊上的最左側的一個凹頂點之間的連線對所述粗分 割多邊形進行進一步分割，並將在所述左側邊搜索階段找出的所述相交點或所述水平線穿 過的所述凹多邊形的一個頂點添加在分割出的所述多個凸多邊形中。
20.根據權利要求11至19中任一項所述的用於渲染凹多邊形的裝置，其特徵在於，通 過使用Wachspress坐標的參數插值方法獲取用於渲染所述像素的參數信息。
全文摘要
公開了一種用於渲染凹多邊形的方法和裝置。其中，該用於渲染凹多邊形的方法包括將凹多邊形分割為多個凸多邊形；判斷將要渲染的像素位於所述多個凸多邊形中的哪一個中；利用所述像素的坐標信息、以及所述像素所在的凸多邊形的各個頂點的坐標信息和參數信息，獲取用於渲染所述像素的參數信息；以及利用所述參數信息對所述像素進行渲染。
文檔編號G06T11/20GK101996414SQ200910165928
公開日2011年3月30日 申請日期2009年8月18日 優先權日2009年8月18日
發明者付軒, 洲鐮康, 白向暉, 譚志明 申請人:富士通株式會社