[發明專利]一種在FPGA中填充非自相交多邊形的填充方法

在審

• 申請號: 201611262966.8
• 申請日: 2016-12-30
• 公開（公告）號: CN106651993A
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 陳修濤;韓非;王運鋼;董輝;吳景舟
• 申請（專利權）人: 江蘇九迪激光裝備科技有限公司
• 主分類號: G06T11/40
• 分類號: G06T11/40;G06T1/20
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種在FPGA中填充非自相交多邊形的填充方法，其特征在于，包括如下步驟：

坐標獲取步驟，獲取多邊形各頂點的Y坐標值，得出各頂點的Y坐標值的最大值點Ymax、最小值點Ymin以及非極值點，并對多邊形各邊進行編號；

交點計算步驟，獲取Y=Ymin的直線與多邊形各邊的交點的X坐標值并記錄交點個數以及交點所在邊的編號；

交點排序及邊排序步驟，對交點的X坐標值進行排序，然后按照X值由小到大的順序對交點進行交點排序，并對交點所在邊依據交點排序的順序進行邊排序，記錄邊排序后各個邊編號的順序；

組合填充步驟，對排序后的交點從x值最小的交點開始每兩個組合為一組，每個交點不重復參加組合，同一組的兩個交點之間進行填充，其余位置不填充；

條件判斷步驟，令Y=Y+1，判斷Y是否大于Ymax，

若Y>Ymax時結束填充過程，

若Y不大于Ymax，則返回并執行交點計算步驟，然后進行極值點判斷，若交點中不存在非極值點的頂點或交點中存在非極值點的頂點但該頂點擁有的兩條邊均在當前Y直線的同一側時，則執行交點排序及邊排序步驟及之后的步驟，直至Y>Ymax時結束填充過程，

若交點中存在非極值點的頂點且該頂點擁有的兩條邊在當前Y直線的兩側時，則進行交點合并及邊替換，然后執行交點排序及邊排序步驟及之后的步驟，直至Y>Ymax時結束填充過程。

2.根據權利要求1所述的一種在FPGA中填充非自相交多邊形的填充方法，其特征在于，當Y>Ymin且Y≤Ymax時，所述交點排序及邊排序步驟存在簡化算法，所述簡化算法首先對當前Y直線與多邊形的交點個數與上一次記錄的交點個數進行比較，然后根據交點個數變化的情況執行相應簡化算法：

當交點個數與上一次記錄的交點個數相同，且上一次記錄的交點不存在極值點的頂點，則交點對應的邊順序就是本次交點排序的順序；

當交點個數與上一次記錄的交點個數相同，且上一次記錄的交點存在極值點的頂點，則對極值點的頂點具有的兩條邊按照對應交點的排序順序進行排序，然后將所述兩條邊排序的結果作為整體參與邊排序；

當交點個數比上一次記錄的交點個數多時，對交點進行排序，以交點排序的結果作為交點所在的邊的排序結果，將此交點所在的邊的排序結果作為整體參與邊排序；

當交點個數比上一次記錄的交點個數少時，將減少的交點對應的邊從邊排序的序列中刪除，剩余的邊排序的序列保持不變，邊排序的結果是對應交點的排序順序。

3.根據權利要求2所述的一種在FPGA中填充非自相交多邊形的填充方法，其特征在于：當交點個數與上一次記錄的交點個數相同，且上一次記錄的交點存在極值點的頂點，對極值點的頂點具有的兩條邊排序的排序結果若保持與上一次記錄的邊排序結果中此兩條邊的排序順序一致時，則無需進行邊排序，上一次記錄的邊排序結果即為本次的邊排序結果。

4.根據權利要求1所述的一種在FPGA中填充非自相交多邊形的填充方法，其特征在于，所述交點合并的方法是：將非極值點的頂點對應的兩個交點合并為一個，然后進行交點排序。

5.根據權利要求1所述的一種在FPGA中填充非自相交多邊形的填充方法，其特征在于，所述邊替換的方法是：使用非極值點的頂點擁有的兩條邊中在當前Y直線未填充一側的邊替換當前Y直線已填充一側的邊參與邊排序。

6.根據權利要求1所述的一種在FPGA中填充非自相交多邊形的填充方法，其特征在于：所述填充方法適用于任意邊數的非自相交多邊形。