如何将闭合贝塞尔曲线转换为位图？

Question

我需要一种算法将封闭的贝塞尔曲线（可能是自交的）转换为二进制位图：内部像素为0，外部为1。我正在编写一个需要在贝塞尔曲线上实现一些操作的代码，请问是否有人能提供一些关于贝塞尔曲线的资源或教程？维基百科和其他网站没有关于优化、减法、并集、结点插入和删除以及其他操作的说明 :-) alt text http://www.imagechicken.com/uploads/1271001073057545100.jpg

- sorush-r

---

图片链接已经损坏。 - brainjam

Answer 1

这篇论文《Loop和Blinn，使用可编程图形硬件实现分辨率独立的曲线渲染》详细讨论了你的问题。

另一个选择是将Bezier曲线细分为线段，然后使用您喜欢的多边形填充算法。

- brainjam

---

哎呀，链接已经失效了，Jim。这个链接是否相同：http://research.microsoft.com/en-us/um/people/cloop/loopblinn05.pdf - Pierre

现在托管在这里(?): https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf使用可编程图形硬件进行分辨率独立曲线渲染 (2005) - Thompsonmachine

@Thompsonmachine：谢谢！我已经更新了链接，并添加了论文的实际标题，这样下次链接断开时更容易找到。 - brainjam

Answer 2

我想补充的是，镶嵌选项非常高效，可以获得出色的结果。将贝塞尔曲线近似为线段似乎是错误的，因为您认为输出将看起来像多边形。诀窍是使线段足够短，以便误差非常小（例如小于1/10个像素）。

以下是我用来计算步长的公式，以确保最大误差（即线段偏离真实曲线的程度）小于delta：

假设(x1,y1), (x2,y2), (x3,y3), (x4,y4)是贝塞尔曲线的控制点，以像素为单位。

dd0 = 平方(x1-2*x2+x3) + 平方(y1-2*y2+y3); dd1 = 平方(x2-2*x3+x4) + 平方(y2-2*y3+y4); dd = 6*sqrt(max(dd0, dd1));

然后dd是曲线上第二导数的最大值——因为三次导数是线性函数，所以此最大值必须发生在端点处。这里我使用平方（x）作为x * x的缩写。

如果8 * delta > dd，则

epsilon = 1;

否则，

epsilon = sqrt(8 * delta / dd);

然后epsilon就是您的步长：如果您选择t = 0，t = epsilon，t = 2 * epsilon，...的线段端点（并将最后一个端点设置为t = 1），则线段将与原始曲线相差不到delta。

选择delta = 0.1，您将获得与原始曲线在视觉上无法区分的位图输出。

- Peter Selinger