bezier shape-fill：为相交测试寻找根的问题

Question

我将 this shadertoy 改编成 Unity 着色器并注意到，虽然它通常按预期工作，但会出现某些瑕疵，我将进一步解释。我相信它们与贝塞尔曲线的根计算有关。

下面是工件的可视化。第一张图片显示了带有伪影的贝塞尔曲线，第二张图片显示了早期动画帧中的贝塞尔曲线，工作正常：

我似乎已经将神器的起源缩小到计算贝塞尔根的函数。当我只看到形状轮廓时，没有伪影。在应用使用 偶-奇交集测试 填充形状的方法时引入伪影。

Bezier 形状是动画的：换句话说，定义 Bezier 曲线控制点的 Vector2 位置随时间变化（它们在两个定义的位置之间线性插值）。在大多数帧行为是预期的，但是，在某些帧（或位置）出现伪影。

填充规则基本上计算每个 uv.y 坐标处贝塞尔曲线和水平线之间的交点，其中给定的水平线充当贝塞尔函数的 x 轴，函数的根表示与此 x 相交的点-轴。然而，一些根将是复数（即它们具有实部和虚部，a + bi），我认为这可能会导致问题。然而，计算根的函数（从第 74 行开始）显然丢弃了复杂的根，因为我阅读了它们链接来源的注释，其中一个来源 显然是 shadertoy 作者从中获得此函数的地方：引用的文章描述此函数如何丢弃复根。请参阅“实现 Cardano 的算法以查找所有实根”大约 1/4 的方式。

我摸不着头脑。有没有人阅读过贝塞尔函数的经验？见过这样的神器吗？非常感谢任何见解。

谢谢！

我已经尝试解决“近乎未命中”的问题，并在段的开始和结束处重复计算段，因为这是段可能重叠的地方（例如，定义一个贝塞尔曲线段末端的点与定义下一段的开始）。这并没有解决问题。

Answer 1

问题肯定是计算三次多项式的实根。

第一个误解是中间值的范围。在产生错误的段中，扩展和归一化多项式的系数在

3*1500

范围内。例如在

y = 4.84400272369

的值是

a = -1117.05571565802, b = 1706.85975024015, c = -1828.09125840538

对于多项式

t^3 + 3*a*t^2 + 3*b*t + c

.

在我的版本

s^3 - 3*p*s +q

中，在示例中

，这导致约化多项式的系数在百万和十亿范围内的系数

p = 1246106.61213401, q = -2782036197.45853

判别式然后获得更大的值，例如

-178627039216.052

。这是接近双根的

y

水平，这意味着这是一个“小”判别值。

这里的三个实根是

0: 3349.63861387448, 1: 0.568446220187752, 2: 0.960086879399569

这种大根和小根的组合会对根的精度产生影响。上面引用的值用于双精度计算。

---

我用于上述值的实现采用典型的更改来计算更准确的解决方案，以避免灾难性的取消。

• 使用

  atan2

  方法计算角度（在着色器数学函数中重载

  atan

  ）
• 二次方程解的稳定计算，
• 立方根的稳定组合，使用二项式定理

  A^3+B^3=(A+B)*(A^2-A*B+B^2)

  如果

  A*B<0

  .

这消除了对象形状的错误。通过将牛顿步应用于单位间隔内和接近单位间隔的根，可以消除一两条扫描线的偶尔闪烁。

---

更好的办法是避免这种数字规模的升级。

为此转换输入多项式

A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3

情况

abs(A) < abs(D)

到

A/D + 3*(B/D)*s + 3*(C/D)*s^2 + s^3  with  s = t/(1-t),  t = s/(1+s)

在相反的情况下

s^3 + 3*(B/A)*s^2 + 3*(C/A)*s + D/A  with  s = (t-1)/t,  t = 1/(1+s)