第三章 揭开几何约束求解的奥秘

上一章我们把几何约束变成了一组非线性方程 f(x) = 0,并指出求解的本质是把当前草图投影到约束流形上。这一章进入工程现场:这个投影,代码里究竟是怎么算出来的?

结论先放在前面:几乎所有成熟求解器用的都是迭代法,没有解析解可用。差别只在于——用哪种迭代、怎么决定步长、以及在约束不足或过多时如何兜底。

一、牛顿法:约束求解的地基

设当前参数为 x,约束残差为 f(x)。目标是找 Δx 使 f(x + Δx) = 0。对 f 做一阶泰勒展开:

f(x + Δx) ≈ f(x) + J · Δx = 0

其中 J 是雅可比矩阵,第 i 行第 j 列是「第 i 个约束对第 j 个参数」的偏导。于是问题变成解一个线性方程组:

J · Δx = -f(x)

解出 Δx,更新 x ← x + Δx,重复直到 |f(x)| 足够小。这就是牛顿-拉夫森迭代。它对好的初值收敛极快(二次收敛),但对坏初值可能发散——这一点在草图里非常常见,因为用户随手画的位置往往离解很远。

二、方程组不方:最小范数步长

注意一个尴尬的事实:J 通常是长方阵。

  • 约束比参数少(欠约束):方程个数 m < 变量个数 n,线性方程组有无穷多解;
  • 约束比参数多(过约束):m > n,很可能无解。

牛顿法本身没说该选哪个。而上一章的「投影」原则给了答案:选范数最小的那个 Δx。这正好对应一个约束最小二乘问题:

minimize  |Δx|²
subject to  J · Δx = -f(x)

它的解用拉格朗日乘子写出来很干净:

Δx = -Jᵀ (J Jᵀ)⁻¹ f(x)

这一步是几何约束求解器里最有「性格」的地方。SolveSpace 的求解器(src/slvs 与 system.cpp)走的就是这条路线:每一步都求最小范数修正,好处是图形只会做「必要的最小移动」,用户拖一个点时,远离约束的实体几乎不动,视觉上非常自然。

代价是 J Jᵀ 可能奇异——当约束之间存在线性相关(冗余)时它会退化。工程上要靠正则化(加一个小量 λI)或先做冗余检测来绕开。

© 版权声明
THE END
喜欢就支持一下吧
点赞2W+赞赏 分享