我正在尝试找到/制作一种算法来计算两个任意填充的 2D 对象的交集（一个新的填充对象）。对象使用直线或三次贝塞尔曲线定义，并且可能有孔或自相交。我知道一些现有的算法对多边形做同样的事情，这里列出。但是，我想支持贝塞尔曲线而不将它们细分为多边形，并且在没有交叉点的区域中，输出应该具有与输入大致相同的控制点。
这是一个交互式程序来做一些 CSG，但剪辑不需要是实时的。我已经搜索了一段时间，但没有找到好的起点。
jjrv
问问题
9134 次
4 回答
10
我发现以下出版物是有关 Bezier Clipping 的最佳信息：
TW Sederberg, BYU, 计算机辅助几何设计课程笔记
第 7 章讨论曲线交点可在线获取。它概述了查找交叉点的 4 种不同方法，并详细描述了 Bezier Clipping：
http://www.tsplines.com/technology/edu/CurveIntersection.pdf
于 2010-06-09T11:35:29.583 回答
6
我知道我有被多余的风险，但我正在调查同样的问题并找到了一个我在学术论文中读过但没有找到可行的解决方案的解决方案。
您可以将贝塞尔曲线重写为一组两个双变量三次方程，如下所示：
- Δ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₂</li>
显然，曲线与 (t₁,t₂) 的值相交，其中 Δx = Δy = 0。不幸的是，由于很难在二维中找到根，并且近似方法倾向于（正如另一位作者所说它）炸毁。
但是，如果您使用整数或有理数作为控制点，那么您可以使用Groebner 基将您的双变量 3 阶多项式重写为 (possibly-up-to-order-9-thus-your-nine-可能的交叉点）单变量多项式。之后，您只需要在一个维度中找到您的根（例如 t₂），然后将您的结果重新插入您的原始方程之一以找到另一个维度。
Burchburger 对 Groebner Bases 有一个通俗易懂的介绍，称为“ Gröbner Bases: A Short Introduction for Systems Theorists ”，这对我很有帮助。去谷歌上查询。另一篇很有帮助的论文是 TF Hain 的一篇名为“三次贝塞尔路径和偏移曲线的快速、精确展平”的论文，其中包含许多贝塞尔曲线的实用方程，包括如何找到 x 和 y 方程的多项式系数。
至于贝塞尔剪裁是否有助于这种特定方法，我对此表示怀疑，但贝塞尔剪裁是一种缩小交叉点可能存在的方法，而不是找到它所在位置的最终（尽管可能是近似的）答案。使用这种方法会花费大量时间来寻找单变量方程，而使用裁剪不会使这项任务变得更容易。相比之下，找到根源是微不足道的。
但是，这种方法的优点之一是它不依赖于递归地细分曲线，问题变成了一个简单的一维求根问题，这并不容易，但有据可查。主要缺点是计算 Groebner 基的成本很高，并且如果您正在处理浮点多项式或使用更高阶的 Bezier 曲线，则会变得非常笨拙。
如果你想在 Haskell 中完成一些代码来找到交叉点，请告诉我。
于 2010-02-04T22:44:42.437 回答
3
很久很久以前，我编写了代码来执行此操作。我正在使用作为 PostScipt 路径生成的分段 Bezier 边界来定义 2D 对象的项目。
我使用的方法是：
让曲线 p、q 由 Bezier 控制点定义。它们相交吗？
计算控制点的边界框。如果它们不重叠，则两条曲线不相交。否则：
px(t), py(t), qx(u), qy(u) 是 0 <= t,u <= 1.0 上的三次多项式。距离平方 (px - qx) ** 2 + (py - qy) ** 2 是 (t,u) 上的多项式。使用 Newton-Raphson 尝试将其解决为零。丢弃 0 <= t,u <= 1.0 之外的任何解
NR 可能收敛也可能不收敛。曲线可能不相交，或者当两条曲线几乎平行时，NR 可能会爆炸。因此，如果在任意次数的迭代后没有收敛，则切断 NR。这可能是一个相当小的数字。
如果 NR 不收敛于解，则在 t = 0.5 时将一条曲线（例如 p）分成两条曲线 pa、pb。这很简单，它只是计算中点，如链接文章所示。然后递归地测试 (q, pa) 和 (q, pb) 的交叉点。（请注意，在下一层递归中，q 已变为 p，因此 p 和 q 在递归的每一层上交替拆分。）
大多数递归调用很快返回，因为边界框是不重叠的。
您将不得不在某个任意深度切断递归，以处理两条曲线平行且不完全接触的奇怪情况，但它们之间的距离任意小 - 可能只有 1 ULP 的差异。
当你找到一个交点时，你还没有完成，因为三次曲线可以有多个交叉点。所以你必须在交点处分割每条曲线，并递归检查（pa，qa），（pa，qb），（pb，qa），（pb，qb）之间的更多交点。
于 2009-01-10T18:54:23.107 回答
1
有许多关于进行贝塞尔剪裁的学术研究论文：
http://www.andrew.cmu.edu/user/sowen/abstracts/Se306.html
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.6669
http://www.dm.unibo.it/~casciola/html/research_rr.html
我推荐间隔方法，因为正如您所描述的，您不必划分为多边形，并且可以获得有保证的结果以及为结果集定义自己的任意精度。有关区间渲染的更多信息，您也可以参考http://www.sunfishstudio.com
于 2008-09-20T21:03:10.970 回答