多边形图像填充算法

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可能是一个选项。