algorithm - 如何在 “ascending” 三次贝塞尔曲线中以 Δx 的间隔有效地采样 y？

Question

对于由控制点 P0、P1、P2 和 P3 用公式定义的三次贝塞尔曲线

B(t)=(1−t)^3*P0 + 3(1−t)^2t*P1 + 3(1−t)t^2*P2 + t^3*P3

我们可以得到对应于任何t∈[0,1]的点。然而，根据我收集到的信息，代数求解任一坐标都变得非常乏味且成本​​高昂，至少对于通用解决方案而言是这样。

现在，假设我们有一条二维曲线 B(t)=(x,y)，其特定约束条件是对于所有 0 ≤ t ≤ 1，dx/dt > 0，即曲线可以前进到正 x方向，但从不“直接向上/向下”或“向后”，是否有一种有效的算法(/代数操作技巧)相对于可以利用此属性的恒定间隔 Δx 对曲线的 y 进行排序？

Answer 1

我将回答我认为你在问什么，而不是你实际在问什么，所以如果这不包括它(即使它包括)你会想要更新你的帖子以澄清你真正的意思。

Now, suppose we have a two-dimensional curve B(t)=(x,y) with the specific constraint that dx/dt > 0 for all 0 ≤ t ≤ 1, i.e. the curve can progress to the positive x direction, but never "straight up/down" or "backwards", is there an efficient algorithm (/algebraic manipulation trick) to sort of "sample" the y of the curve with respect to a constant interval Δx that can leverage this property?

贝塞尔曲线是仿射变换不变的，因此任何符合此定义的曲线都可以旋转以不再符合该定义。假设您指的是某种规范形式，您通过对其应用旋转/平移来预处理曲线，使得第一个点位于 (0,0)，最后一个点是某个坐标 (>0,R)(即x坐标大于0，y坐标“任意实数”)。

鉴于此，您的约束意味着第一个控制点(确定 t=0 处曲线的切线)必须严格位于 (0,0) 的右侧。 y 坐标是无关紧要的(它只需要是一个实数)，x 坐标可以是任何大于 0 的实数(甚至接近于零的值IEEE float 允许)。

相反，需要类似地逼近结束坐标，因此对于任何结束坐标 (ex,ey)，关联的控制点(确定 t=1 处的曲线切线)需要位于严格位于 (ex,ey) 的左侧；也就是说，y 坐标可以是任何值，x 坐标必须小于 ex，但同样可以接近于可能没有 being ex。

完成，我们现在有一条符合您需求的曲线，它以固定的 x 间隔进行采样:您有三个选项。

1. 在数学上真正做到这一点的方法是重新参数化您的曲线，使 y 成为 x 的表达式，这非常困难。
2. 您知道每个点的切线，并且符合您需要的三次贝塞尔曲线不会振荡，因此您可以计算“下一个 x”的猜测值，然后使用牛顿方法找到您需要的真正的下一个 x 值。或者，
3. 通过编程方式解决这个问题:无论如何你都要画这条曲线，所以在绘制例程中，为需要绘制到屏幕上的曲线点构建 LUT:你现在有一个 x 值与关联的 y 值，您只需要进行简单的查找。

显然，除非您需要绝对的科学精确性，否则选项 3 将是迄今为止的最佳选择。