Bezier剪辑

我正在尝试找到/制作一个算法来计算两个任意填充的2D对象的交集(一个新的填充对象).使用线或立方贝塞尔定义对象,并且可以具有孔或自相交.我知道几个现有的算法对多边形做了同样的事情,在这里列出.但是,我想支持beziers而不将它们细分为多边形,并且输出应该与没有交叉点的区域中的输入具有大致相同的控制点.

这是一个交互式程序来做一些CSG,但剪辑不需要是实时的.我已经搜索了一段时间,但没有找到好的起点.

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

TW Sederberg,BYU,计算机辅助几何设计课程笔记

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

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

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

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

Δx= ax 1*t 1 ^ 3 + bx 1*t 1 ^ 2 + cx 1*t 1 + dx 1 - ax 2*t 2 ^ 3 - bx 2*t 2 ^ 2 - cx 2*t 2 - dx 2

Δy= ay 1*t 1 ^ 3 +乘1*t 1 ^ 2 + cy 1*t 1 + dy 1 - ay 2*t 2 ^ 3 - 乘以2*t 2 ^ 2 - cy 2*t 2 - dy 2

显然,曲线与(t 1,t 2)的值相交,其中Δx=Δy= 0.不幸的是,由于难以在二维中找到根,并且近似的方法倾向于(如另一位作者所说)它爆炸了.

但是如果你使用整数或有理数作为你的控制点,那么你可以使用Groebner基础将你的双变量3阶多项式重写为(可能是按顺序9 - 因此你的九 -可能的交叉点)单变量多项式.之后你只需要在一个维度上找到你的根(比如说t 2),然后将你的结果插回原来的一个方程中以找到另一个维度.

Burchburger对Groebner Bases的外行友好介绍称为" GröbnerBases:系统理论家简介 ",这对我非常有帮助.谷歌一下.另一篇有用的论文是TF Hain 所说的" 快速,精确的三次Bézier路径和偏移曲线的平坦化 ",它有许多贝塞尔曲线的效用方程,包括如何找到x和y方程的多项式系数.

至于贝塞尔削波是否会对这种特殊方法有所帮助,我对此表示怀疑,但贝塞尔裁剪是一种缩小交叉点可能范围的方法,而不是找到最终(尽管可能是近似的)答案的方法.使用此方法的大量时间将用于查找单变量方程,并且该任务在剪切时不会变得更容易.相比之下,寻找根源是微不足道的.

然而,这种方法的一个优点是它不依赖于递归细分曲线,并且问题变成一个简单的一维寻根问题,这不容易,但有很好的文献记载.主要的缺点是,如果您处理浮点多项式或使用更高阶的Bezier曲线,计算Groebner基础是昂贵的并且变得非常笨重.

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