贝塞尔的剪切

Question

我试图找出一个算法计算交叉点(一个新的充满对象)的两个任意的，充满2D对象。的对象是使用定义的任一线或立方贝济耶和可能有洞或自相交叉。我知道还有几个现有的算法做同样与多边形， 列出这里.然而，我想支持贝济耶没有细分他们成为多边形，并且输出应该大致相同的控制点输入的地区没有交叉点。

这是一个互动的程序做一些CSG但剪切并不需要实的时间。我已经搜查了一段时间，但还没有找到良好的起点。

Answer 1

我发现以下出版物是关于贝塞尔剪辑的最佳信息：

吨。 W. Sederberg，BYU，计算机辅助几何设计课程笔记

第7章讨论了曲线交叉点，可在线获取。它概述了4种不同的方法来查找交叉点，并详细描述了Bezier Clipping：

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

Answer 2

我知道我在的风险是多余的，但我们正在调查同样的问题，并找到一个解决方案，我会读的学术论文，但没有发现了一个工作方案。

你可以改写的曲曲线作为一个双变量方程是这样的：

• δ 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式进入(可能-起来-到了-9-因此-你的九个可能的交叉口)monovariate多项式。在那之后你只需要找到自己的根源(为，说t₂)在一个层面，插入你的结果回到你原来的公式找到其他层面。

Burchburger有一个门外汉友好的介绍Groebner基地的所谓的"Gröbner基地：一个简短的介绍系统理论家"这是非常有助于我。谷歌。其他文件，是有帮助的是一个叫做"快速、准确平方贝塞尔的道路和偏曲线"通过TF海恩，其中有很多实用的方程为贝塞尔的曲线，包括如何找到多项式系数为x和y的方程式。

至于是否在贝塞尔的剪切将帮助这一特定的方法，我对此表示怀疑，但bezier削是一种缩小在那里交叉点可能是，不是为找到最终(虽然可能近似)的答案在哪里。很多的时间用这种方法将花费在寻找单变量的公式，这项任务没有得到任何更容易使用剪切。寻找根源是通过比较微不足道的。

然而，这种方法的优点是，它不取决于递归细分的曲线，而且该问题成为一个简单的一个维根况调查的问题，这是不容易的，但是，有确凿的文献可以证明。主要缺点是，计算Groebner基地是昂贵的，并变得非常臃肿，难以如果你正在处理的浮点的多项式或使用高了贝塞尔的曲线。

如果你想要一些完成中的代码Haskell找到的交叉点，让我知道。

Answer 3

很久很久以前，我编写代码来做这件事。我正在使用作为PostScipt路径生成的分段Bezier边界来定义2D对象的项目。

我使用的方法是：

让曲线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）上的多项式。 使用Newton-Raphson尝试解决零问题。丢弃0 <！> lt; = t，u <！> lt; = 1.0

之外的任何解决方案

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

如果N-R没有收敛于解，则将一条曲线（例如，p）分成两条曲线pa，pb，t = 0.5。这很容易，它只是计算中点，正如链接文章所示。然后递归测试交叉点的（q，pa）和（q，pb）。 （注意，在递归的下一层中，q已变为p，因此p和q在递归的每一层上交替分开。）

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

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

当你找到一个交叉点时，你没有完成，因为三次曲线可以有多个交叉点。所以你必须在交叉点处分割每条曲线，并递归检查（pa，qa），（pa，qb），（pb，qa），（pb，qb）之间的更多相互作用。

Answer 4

有许多关于做贝塞尔剪裁的学术研究论文：

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