logo标签列表

贝塞尔裁剪

graphicsgeometry2dbeziercsg
16

我正试图找到/创建一种算法，用于计算两个任意填充的2D对象之间的交集(一个新的填充物体)。这些对象是使用线条或立方贝塞尔曲线定义的，可能具有空洞或自相交。我知道有几种现有的算法可以使用多边形完成相同的工作，在此列出。然而，我希望支持贝塞尔曲线，而不需要将它们细分为多边形，并且输出结果应该在没有相交的区域中具有大致相同的控制点。

这是为了一个交互式程序进行一些CSG，但剪辑并不需要实时完成。我已经搜索了一段时间，但没有找到好的起点。

4个回答
12
2
链接已过期。 - Jeff T.
新链接：https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1000&context=facpub - Pranav Totla
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₂
显然，当 ∆x = ∆y = 0 时，曲线相交。不幸的是，由于在二维空间中很难找到根，因此近似方法往往会失效。
但是，如果您在控制点中使用整数或有理数，则可以使用Groebner基来将双变量三次方程组重写为（最多达到第9阶，因此有九个可能的交点）单变量多项式。之后，只需要在一维中找到根（例如t₂），并将结果插入到原始方程中的另一个维度中即可找到另一个维度。
Burchburger的Groebner Bases介绍书《Gröbner Bases: A Short Introduction for Systems Theorists》对我很有帮助。谷歌它。另一个有用的论文是TF Hain的《Fast, precise flattening of cubic Bézier path and offset curves》 ，其中包括如何找到x和y方程的多项式系数等贝塞尔曲线的实用公式。
至于贝塞尔剪辑是否能帮助解决此特定方法，我表示怀疑。bezier剪辑是一种缩小交点可能存在的范围的方法，而不是找到最终（虽然可能是近似的）答案。这种方法的大部分时间将用于寻找单变量方程，这项任务即使使用剪辑也更加困难。相比之下，找到根就相对容易。
但是，这种方法的优点之一是它不依赖于递归地细分曲线，并且问题变成了一个简单的一维根查找问题，这很困难，但是有很好的文档记录。主要缺点是计算Groebner基耗费很高，并且如果您处理浮点多项式或使用更高阶的Bezier曲线，则会变得非常笨重。
如果您需要Haskell中的完成代码以查找交点，请告诉我。
4
我很久以前写了一些代码来实现这个功能。我当时正在开发一个项目，用分段贝塞尔边界定义二维对象，并生成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。这可以是相当小的数字。
如果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）之间是否有更多的交点。
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接