algorithm - 如何将封闭的贝塞尔曲线转换为位图？

Question

我需要一种算法来将封闭的贝塞尔曲线（可能是自交叉）转换为二进制位图：内部像素为 0，外部像素为 1。我正在编写一个需要在贝塞尔曲线上实现一些操作的代码，有人可以给我一些关于贝塞尔曲线的资源或教程吗？维基百科和其他人没有说优化、减法、并集、节点插入和删除等操作:-)

score 4 · Accepted Answer

Charles Loop 和 Jim Blinn的这篇论文详细介绍了您的问题。

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

score 2 · Accepted Answer

我想补充一点，镶嵌选项非常有效并且效果很好。用线段近似贝塞尔曲线听起来是错误的，因为您认为输出看起来像一个多边形。诀窍是使线段足够短，以使误差非常小（例如，小于像素的 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 是曲线上二阶导数的最大值 - 因为三次的二阶导数是线性函数，所以这个最大值必须出现在端点处。这里我使用 square(x) 作为 x*x 的缩写。

  if (8*delta > dd) {
    ε = 1;
  } 别的 {
    epsilon = sqrt(8*delta/dd);
  }

那么 epsilon 是您的步长：如果您选择线段的端点 t=0, t=epsilon, t=2*epsilon, ..., （以及 t=1 的最后一个端点），那么线段将在原始曲线的 delta 范围内。

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

2 回答 2