Bezier裁剪

Question

我正在尝试寻找/创建一个算法来计算两个任意填充的2D对象的交点(一个新的填充对象)。这些对象是使用直线或三次贝塞尔曲线定义的，并且可以具有孔或自相交。我知道有几个现有的算法对多边形做了同样的处理，listed here。但是，我希望支持beziers，而不是将它们细分为多边形，并且输出应该与没有交集的区域中的输入具有大致相同的控制点。

这是一个交互式程序做一些CSG，但剪辑不需要是实时的。我已经寻找了一段时间，但还没有找到好的起点。

Answer 1

我发现下面的出版物是关于Bezier剪辑的最好的信息：

沈大伟，计算机辅助几何设计课程笔记

关于曲线相交的第7章可以在网上找到。它概述了4种不同的寻找交点的方法，并详细描述了Bezier裁剪：

http://www.tsplines.com/technology/edu/CurveIntersection.pdf

Answer 2

我知道我有被裁员的风险，但我正在调查同样的问题，并找到了一个解决方案，我在学术论文中读到过，但没有找到一个可行的解决方案。

您可以将bezier曲线重写为一组两个二元立方方程，如下所示：

∆x= ax₁*t₁^3 + bx₁*t₁^2 + cx₁*t₁+ dx₁- ax₂*t₂^3 - bx₂*t₂^2 - cx₂*t₂- dx₂₁∆y= ay₁*t₁^3 + by₁*t₁^2 + cy₁*t₁+ dy₁- ay₂*t₂^3 - by₂*t₂^2 - cy₂*t₂-dy₂₁

显然，曲线与(t₁，t₂)的值相交，其中∆x =∆y = 0。不幸的是，由于难以在二维中找到根的事实，这一点变得复杂，并且近似方法往往(正如另一位作者所说的那样)失败。

但是如果您使用整数或有理数作为控制点，那么您可以使用Groebner基将您的二元3阶多项式重写为(possibly-up-to-order-9-thus-your-nine-possible-intersections)一元多项式。在此之后，您只需在一个维度中找到您的根(例如t₂)，然后将结果重新插入到一个原始方程中，以找到另一个维度。

汉堡有一个对Groebner Bases的外行友好的介绍，叫做"Gröbner Bases: A Short introduction for Systems Theorists“，这对我非常有帮助。用谷歌搜索一下。另一篇有帮助的论文是TF Hain的“快速，精确展平三次贝塞尔轨迹和偏移曲线”，其中有许多贝塞尔曲线的实用方程，包括如何找到x和y方程的多项式系数。

至于Bezier裁剪是否会对这种特定的方法有所帮助，我对此表示怀疑，但bezier裁剪是一种缩小交叉点范围的方法，而不是为了找到它所在位置的最终(尽管可能是近似的)答案。使用这种方法将花费大量时间来寻找单变量方程，而使用裁剪并不会使这项任务变得更容易。相比之下，找到根是微不足道的。

然而，这种方法的一个优点是它不依赖于递归细分曲线，并且该问题变成了一个简单的一维寻根问题，这并不容易，但有很好的文档记录。主要的缺点是，如果您正在处理浮点多项式或使用高阶Bezier曲线，则计算Groebner基的成本很高，并且变得非常笨拙。

如果你想在Haskell中找到一些已完成的代码来找到交叉点，请告诉我。

Answer 3

我很久很久以前就写过这样的代码。我工作的项目使用分段贝塞尔曲线边界定义了2D对象，这些边界是作为PostScipt路径生成的。

我使用的方法是：

设曲线p，q由Bezier控制点定义。它们相交吗？

计算控制点的边界框。如果它们不重叠，则两条曲线不相交。否则：

p.x(t)，p.y(t)，q.x(u)，q.y(u)是0 <= t，u <= 1.0上的三次多项式。距离平方(p.x - q.x) ** 2+ (p.y - q.y) ** 2是(t，u)上的多项式。使用牛顿-拉夫森算法来解决这个问题。丢弃0 <= t，u <= 1.0之外的任何解决方案

N-R可能收敛，也可能不收敛。曲线可能不相交，或者当两条曲线几乎平行时，N-R可能会爆炸。因此，如果在经过任意次数的迭代后仍不收敛，则切断N-R。这可能是一个相当小的数字。

如果N-R不收敛于某个解，则将一条曲线(例如，p)在t= 0.5处拆分为两条曲线pa，pb。这很简单，它只是计算中间点，如链接文章所示。然后递归测试交叉点的(q，pa)和(q，pb)。(请注意，在下一层递归中，q已变为p，因此p和q在递归的每一层上交替拆分。)

大多数递归调用都会快速返回，因为边界框是不重叠的。

你必须在任意深度截断递归，以处理两条曲线平行且不完全接触的奇怪情况，但它们之间的距离任意小--可能只有1ULP的差异。

当您找到一个交叉点时，您还没有完成，因为三次曲线可以有多个交叉点。因此，您必须在交点处分割每条曲线，并递归检查(pa，qa)，(pa，qb)，(pb，qa)，(pb，qb)之间的更多交集。