多邊形圖像填充算法

Question

我想要一個有效的算法來填充圖像的多邊形，我想填充圖像到梯形。目前我做的兩個步驟
1）首先對圖像進行StretchBlt，
2）柱立式StretchBlt執行列，

是否有實現這個什麼更好的方法？有沒有可以填充任何多邊形的Generic和Fast算法？

感謝， 陽光

Answer 1

我不能幫你失真的部分，但灌裝多邊形是相當簡單的，特別是如果他們是凸的。

對於每個Y掃描行都有一個由Y索引的表，其中包含一個minX和maxX。

對於每條邊，運行DDA線繪圖算法，並使用它填充表條目。

對於每條Y線，現在你有一個minX和maxX，所以你可以填充掃描線的那一段。

困難的部分是精神技巧 - 不要將座標視爲指定像素。想象座標爲之間的像素爲。換句話說，如果你有一個從0,0點到2,2點的矩形，它應該點亮4個像素點，而不是9點。多邊形填充的大多數問題都圍繞着這個問題。

ADDED：好的，聽起來像你真正要問的是如何將圖像拉伸成非矩形（但是梯形）。我會按照參數s和t，從0到1。換句話說，原始矩形中的位置是(x + w0*s, y + h0*t)。然後定義一個函數，使s和t也映射到梯形中的位置，如((x+t*a) + w0*s*(t-1) + w1*s*t, y + h1*t)。這定義了兩個形狀之間的座標映射。然後只掃描x和y，轉換爲s和t，並將映射點從一個映射到另一個。您可能希望有一個平滑過濾器，而不是直接複製。

加入以試圖給出更好的解釋： 我假設您的矩形和梯形的頂邊和底邊都與X軸平行。矩形的左下角是<x0,y0>，梯形的左下角是<x1,y1>。我認爲矩形的寬度和高度是<w,h>。 對於梯形，我認爲它有高度h1，它的較低寬度是w0，而它的上部寬度是w1。我認爲它的左邊緣「偏斜」了一段距離a，所以其左上角的位置是<x1+a, y1+h1>。現在假設你在矩形上迭代<x,y>。在每個點處，計算s = (x-x0)/w和t = (y-y0)/h，它們的範圍均爲0至1。 （我會讓你找出不使用浮點的方法。）然後將其轉換爲梯形座標，如xt = ((x1 + t*a) + s*(w0*(1-t) + w1*t))和yt = y1 + h1*t。然後<xt,yt>是矩形中對應於<x,y>的梯形中的點。現在我讓你弄清楚如何進行復制:-)祝你好運。

P.S.請不要忘記 - 座標位於像素之間，而不是像素。

Answer 2

避開這個問題並使用OpenGL爲你做這件事是否可行？ OpenGL可以渲染到內存上下文，如果你可以利用任何硬件加速，這將完全遏制你可以在CPU上進行的任何代碼調整（儘管在一些較舊的卡上，內存上下文渲染可能無法利用硬件）。

如果你想在軟件中完全做到這一點MESA可能是一個選項。