贝塞尔削波

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

T.W.Sederberg,BYU,计算机辅助几何设计课程笔记

第七章是关于曲线相交的在线讨论。它概述了4种不同的交叉点查找方法,并详细描述了贝塞尔剪裁:

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

我知道我有被裁员的危险,但我正在调查同一个问题,发现了一个解决方案,我曾在学术论文中读到,但没有找到有效的解决方案。

您可以将贝塞尔曲线重写为一组两个双变量三次方程,如下所示:

• _墋x=ax墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋
• _____________________

很明显,曲线相交于(t_________y=0的值。不幸的是,由于很难在二维空间中找到根这一事实使其复杂化,而近似方法(如另一位作者所说)往往会爆炸。

但是,如果您使用整数或有理数作为控制点,那么您可以使用 Groebner碱 把你的二元三阶多项式改写成一个(可能是九个可能的交集)一元多项式。之后,你只需要在一个维度中找到你的根(对于,比如t_墈墈),然后把你的结果插回到你原来的方程中,找到另一个维度。

Burchburger对Groebner基地有一个友好的介绍,叫做 系统理论家简介 “这对我很有帮助。谷歌IT。另一篇有用的论文叫做 立方B_)zier路径和偏移曲线的快速、精确展平 由tf-hain提出,它有很多贝塞尔曲线的效用方程,包括如何找到x和y方程的多项式系数。

至于贝塞尔剪裁是否有助于这个特殊的方法,我对此表示怀疑,但贝塞尔剪裁是一种缩小交叉点的方法,而不是找出交叉点所在位置的最终(尽管可能是近似的)答案。这种方法的大量时间将花在寻找单变量方程上,而削波并不能使这项任务变得简单。相比之下,找到根是微不足道的。

然而,这种方法的一个优点是它不依赖于对曲线的递归细分,并且问题变成了一个简单的一维寻根问题,这不容易,但是有很好的文档记录。主要的缺点是计算Groebner基是昂贵的,如果你处理浮点多项式或使用高阶贝塞尔曲线,会变得非常困难。

如果你想在haskell中找到一些已经完成的代码,请告诉我。

很久很久以前,我就编写了这样做的代码。我正在研究的项目是使用分段贝塞尔边界定义的二维对象,这些边界是作为postscipt路径生成的。

我使用的方法是:

让曲线p,q由贝塞尔控制点定义。它们相交吗?

计算控制点的边界框。如果它们不重叠,那么这两条曲线就不会相交。否则:

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)分成两条曲线,p,pb,t=0.5。这很容易,正如链接文章所示,它只是计算中点。然后递归测试(q,pa)和(q,pb)交叉口。(注意,在下一个递归层中,q变成了p,因此p和q在递归的每一层上交替地分开。)

大多数递归调用返回很快,因为边界框不重叠。

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

当你找到一个交叉点时,你没有完成,因为三次曲线可以有多个交叉点。因此,您必须在相交点拆分每条曲线,并递归地检查(pa,qa)、(pa,qb)、(pb,qa)、(pb,qb)之间是否有更多的交互。

有很多关于做贝塞尔剪辑的学术研究论文:

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