贝塞尔剪裁
我正在尝试寻找/制定一种算法来计算两个任意填充的二维对象的交集（一个新的填充对象）。 这些对象是使用直线或三次贝塞尔曲线定义的，并且可能有孔或自相交。 我知道有几种现有算法对多边形执行相同的操作，此处列出。 但是，我想支持贝塞尔曲线而不将它们细分为多边形，并且输出应该与没有交叉点的区域中的输入具有大致相同的控制点。
这是一个交互式程序来执行一些 CSG，但剪辑不需要是实时的。 我已经搜索了一段时间但没有找到好的起点。
I'm trying to find/make an algorithm to compute the intersection (a new filled object) of two arbitrary filled 2D objects. The objects are defined using either lines or cubic beziers and may have holes or self-intersect. I'm aware of several existing algorithms doing the same with polygons, listed here. However, I'd like to support beziers without subdividing them into polygons, and the output should have roughly the same control points as the input in areas where there are no intersections.
This is for an interactive program to do some CSG but the clipping doesn't need to be real-time. I've searched for a while but haven't found good starting points.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我发现以下出版物是有关贝塞尔剪裁的最佳信息：
TW Sederberg，BYU，计算机辅助几何设计课程笔记
第 7 章，其中讨论了曲线相交，可在线获取。 它概述了查找交叉点的 4 种不同方法，并详细描述了贝塞尔剪裁：
https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1000&context=facpub
I found the following publication to be the best of information regarding Bezier Clipping:
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes
Chapter 7 that talks about Curve Intersection is available online. It outlines 4 different approaches to find intersections and describes Bezier Clipping in detail:
https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1000&context=facpub
我知道我有被裁员的风险，但我正在调查同样的问题，并找到了一个我在学术论文中读过的解决方案，但尚未找到可行的解决方案。
您可以将贝塞尔曲线重写为一组两个双变量三次方程，如下所示：
显然，曲线相交对于 (t₁,t2) 的值，其中 Δx = Δy = 0。不幸的是，由于很难在二维中找到根，而且近似方法往往（正如另一位作者所说）会崩溃，因此情况变得很复杂。
但是，如果您使用整数或有理数作为控制点，那么您可以使用 Groebner 基 将双变量 3 阶多项式重写为（可能高达 9 阶） -因此你的九个可能的交点）单变量多项式。 之后，您只需在一个维度中找到根（例如 t2），然后将结果代入原始方程之一即可找到另一个维度。
Burchburger 对 Groebner 基础做了一个通俗易懂的介绍，名为“Gröbner 基础：系统理论家简短介绍”，这对我非常有帮助。 去谷歌上查询。 另一篇有用的论文是 TF Hain 的一篇名为“快速、精确地展平三次贝塞尔路径和偏移曲线”的论文，其中包含许多贝塞尔曲线的实用方程，包括如何查找多项式系数对于 x 和 y 方程。
至于贝塞尔剪裁是否对这种特定方法有帮助，我对此表示怀疑，但贝塞尔剪裁是一种缩小交点可能位置的方法，而不是找到交点位置的最终（尽管可能是近似的）答案。 使用此方法将花费大量时间来查找单变量方程，并且通过裁剪该任务不会变得更容易。 相比之下，寻找根源就显得微不足道了。
然而，这种方法的优点之一是它不依赖于递归地细分曲线，问题变成了一个简单的一维求根问题，这并不容易，但有很好的文档记录。 主要缺点是计算 Groebner 基数成本高昂，并且如果您处理浮点多项式或使用高阶贝塞尔曲线，则变得非常笨重。
如果您想要 Haskell 中的一些完成代码来查找交集，请告诉我。
I know I'm at risk of being redundant, but I was investigating the same issue and found a solution that I'd read in academic papers but hadn't found a working solution for.
You can rewrite the bezier curves as a set of two bi-variate cubic equations like this:
Obviously, the curves intersect for values of (t₁,t₂) where ∆x = ∆y = 0. Unfortunately, it's complicated by the fact that it is difficult to find roots in two dimensions, and approximate approaches tend to (as another writer put it) blow up.
But if you're using integers or rational numbers for your control points, then you can use Groebner bases to rewrite your bi-variate order-3 polynomials into a (possibly-up-to-order-9-thus-your-nine-possible-intersections) monovariate polynomial. After that you just need to find your roots (for, say t₂) in one dimension, and plug your results back into one of your original equations to find the other dimension.
Burchburger has a layman-friendly introduction to Groebner Bases called "Gröbner Bases: A Short Introduction for Systems Theorists" that was very helpful for me. Google it. The other paper that was helpful was one called "Fast, precise flattening of cubic Bézier path and offset curves" by TF Hain, which has lots of utility equations for bezier curves, including how to find the polynomial coefficients for the x and y equations.
As for whether the Bezier clipping will help with this particular method, I doubt it, but bezier clipping is a method for narrowing down where intersections might be, not for finding a final (though possibly approximate) answer of where it is. A lot of time with this method will be spent in finding the mono-variate equation, and that task doesn't get any easier with clipping. Finding the roots is by comparison trivial.
However, one of the advantages of this method is that it doesn't depend on recursively subdividing the curve, and the problem becomes a simple one-dimensional root-finding problem, which is not easy, but well documented. The major disadvantage is that computing Groebner bases is costly and becomes very unwieldy if you're dealing with floating point polynomials or using higher order Bezier curves.
If you want some finished code in Haskell to find the intersections, let me know.
我很久很久以前就写过代码来做到这一点。 我正在处理的项目使用作为 PostScipt 路径生成的分段贝塞尔边界来定义 2D 对象。
我使用的方法是：
让曲线p、q由贝塞尔曲线控制点定义。 它们相交吗？
计算控制点的边界框。 如果它们不重叠，则两条曲线不相交。 否则：
px(t)、py(t)、qx(u)、qy(u) 是 0 <= t,u <= 1.0 上的三次多项式。
距离平方 (px - qx) ** 2 + (py - qy) ** 2 是 (t,u) 上的多项式。
使用牛顿-拉夫森法尝试将其求解为零。 丢弃 0 <= t,u <= 1.0 N-R 之外的任何解，
N-R 可能会收敛，也可能不会收敛。 曲线可能不相交，或者当两条曲线几乎平行时 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) 之间的更多交点。
I wrote code to do this a long, long time ago. The project I was working on defined 2D objects using piecewise Bezier boundaries that were generated as PostScipt paths.
The approach I used was:
Let curves p, q, be defined by Bezier control points. Do they intersect?
Compute the bounding boxes of the control points. If they don't overlap, then the two curves don't intersect. Otherwise:
p.x(t), p.y(t), q.x(u), q.y(u) are cubic polynomials on 0 <= t,u <= 1.0.
The distance squared (p.x - q.x) ** 2 + (p.y - q.y) ** 2 is a polynomial on (t,u).
Use Newton-Raphson to try and solve that for zero. Discard any solutions outside 0 <= t,u <= 1.0
N-R may or may not converge. The curves might not intersect, or N-R can just blow up when the two curves are nearly parallel. So cut off N-R if it's not converging after after some arbitrary number of iterations. This can be a fairly small number.
If N-R doesn't converge on a solution, split one curve (say, p) into two curves pa, pb at t = 0.5. This is easy, it's just computing midpoints, as the linked article shows. Then recursively test (q, pa) and (q, pb) for intersections. (Note that in the next layer of recursion that q has become p, so that p and q are alternately split on each ply of the recursion.)
Most of the recursive calls return quickly because the bounding boxes are non-overlapping.
You will have to cut off the recursion at some arbitrary depth, to handle weird cases where the two curves are parallel and don't quite touch, but the distance between them is arbitrarily small -- perhaps only 1 ULP of difference.
When you do find an intersection, you're not done, because cubic curves can have multiple crossings. So you have to split each curve at the intersecting point, and recursively check for more interections between (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
There are a number of academic research papers on doing bezier clipping:
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
I recommend the interval methods because as you describe, you don't have to divide down to polygons, and you can get guaranteed results as well as define your own arbitrary precision for the resultset. For more information on interval rendering, you may also refer to http://www.sunfishstudio.com