小智 6
我曾经写过一个工具来完成类似的任务.贝塞尔样条通常是参数三次多项式.要计算立方体段和直线之间距离的平方,这只是两个多项式函数之间距离的平方,它本身只是另一个多项式函数!请注意,我说距离的平方,而不是平方根.
基本上,对于立方体片段上的任何点,可以计算从该点到该线的距离的平方.这将是一个6阶多项式.我们可以最小化距离的平方吗？是.最小值必须发生在该多项式的导数为零的地方.因此,区分,得到五阶多项式.使用您最喜欢的根查找工具,以数字方式生成所有根.詹金斯和特劳布,无论如何.从该组根中选择正确的解决方案,排除任何复杂的解决方案,并且只有当它位于相关的立方体段内时才选择解决方案.确保排除与距离的局部最大值对应的点.
所有这些都可以有效地完成,并且除了多项式根查找器之外不需要使用迭代优化器,因此不需要使用需要起始值的优化工具,仅找到接近该起始值的解.
例如,在3-d图中我显示了由3-d(红色)中的一组点生成的曲线,然后我采取了另一组位于外面的圆,我计算了内部的最近点每条曲线,向下绘制一条直线到该曲线.这些最小距离点由上面概述的方案产生.
我只是想给你一些提示，对于 QBCurve//segment 的情况：为了获得足够快的计算，我认为你应该首先考虑为你的算法使用一种“边界框”。假设 P0 是 QB 曲线的第一个点，P2 是第二个点，P1 是控制点，P3P4 是线段，则：
- 计算从 P0、P1、P2 到 P3P4 的距离
- 如果 P0 或 P2 是最近的点 --> 这是曲线上距 P3P4 最近的点。结束:=)。
- 如果 P1 是最近的点，Pi（i=0 或 1）是第二个最近的点，则 PiPC 和 P3P4 之间的距离是您所寻求的距离的估计值，该估计值可能足够精确，具体取决于您的需要。
- 如果您需要更准确：计算 P1'，它是 QB 曲线上距离 P1 最近的点：您会发现它应用了 t=0.5 的 BQC 公式。--> 从 PiP1' 到 P3P4 的距离是一个更准确的估计 - 但成本更高 -。
- 请注意，如果 P1P1' 定义的线与 P3P4 相交，则 P1' 是 QBC 距 P3P4 最近的点。
- 如果 P1P1' 不与 P3P4 相交，那么你就不走运了，你必须走一条艰难的路......
现在，如果（以及何时）您需要精度：
考虑对曲线参数使用分而治之算法：哪一条最接近 P3P4？P0P1' 或 P1'P2 ??? 如果是 P0P1' --> t 介于 0 和 0.5 之间，因此计算 t=0.25 时的 Pm。现在哪个离 P3P4 最近？P0Pm 或 PmP1' ?? 如果是 PmP1' --> 计算 t=0.25+0.125=0.375 的 Pm2 那么哪一个最接近？PmPm2 或 Pm2P1' ??? 等你很快就会得到准确的解决方案，比如 6 次迭代，你的 t 精度是 0.004！当两点之间的距离低于给定值时，您可能会停止搜索。（而不是两个参数之间的差异，因为参数的微小变化，点可能会很远）实际上，该算法的原理是每次越来越精确地用分段逼近曲线。
对于曲线/曲线的情况，我首先将它们“装箱”以避免无用的计算，因此首先使用线段/线段计算，然后（可能）线段/曲线计算，并且仅在需要曲线/曲线计算时才使用。
对于曲线/曲线，分而治之也有效，更难以解释，但你可能会弄清楚。:=)
希望你能找到速度/准确性的良好平衡:=)
编辑：认为我在一般情况下找到了一个很好的解决方案:-)您应该迭代每个 BQC 的（内部）边界三角形所以我们有三角形 T1，点 A、B、C 具有“t”参数 tA、tB、tC 。以及三角形T2，点D、E、F，具有t参数tD、tE、tF。最初我们有 tA=0 tB=0.5 tC= 1.0 T2 tD=0, tE=0.5, tF=1.0 同样的想法是递归调用一个过程，将 T1 和/或 T2 分割成更小的矩形，直到我们确定为止达到的精度。第一步是计算 T1 到 T2 的距离，跟踪每个三角形上最近的线段。第一个“技巧”：如果 T1 上的线段是 AC，则停止 T1 上的递归，曲线 1 上最近的点是 A 或 C。如果 T2 上最近的线段是 DF，则停止 T2 上的递归，曲线 1 上最近的点Curve2 是 D 或 F。如果我们停止两者的递归性 -> 返回距离 = min (AD, AF, CD, CF)。那么如果我们在 T1 上有递归性，并且线段 AB 最近，则新 T1 变为： A'=AB= 曲线一的点，其中 tB=(tA+tC)/2 = 0.25，C=旧 B。 T2 也是如此：如果需要，应用递归并在新 T1 和新 T2 上调用相同的算法。当T1和T2之间找到的距离减去先前T1和T2之间找到的距离低于阈值时，停止算法。该函数可能类似于 ComputeDistance(curveParam1, A, C, ShouldSplitCurve1, curveParam2, D, F, ShouldSplitCurve2, previousDistance)，其中点还存储其 t 参数。
请注意，距离（曲线，线段）只是该算法的一个特例，您应该实现距离（三角形，三角形）和距离（线段，三角形）才能使其工作。玩得开心。