algorithm - 从样条/曲线生成最小顶点集

Question

在我的项目中，我使用样条线表示几何体。对于物理和渲染，我预处理样条并将它们转换为线，然后通过定期对样条进行采样来将它们转换为多边形。但是，我想通过忽略已经足够好的线表示的样本来减少顶点/线的数量。

搜索时遇到问题，我想知道是否有任何传统技术可以将曲线转换为一组顶点，同时减少由此产生的错误。

编辑:澄清一下，我想要得到的结果是一些顶点/线段，这些顶点/线段最能代表具有最少数量的顶点/线段的样条曲线。我不确定如何定义“最能代表样条曲线”的真正含义，但目标是尽可能难以区分样条曲线和近似值之间的差异。

Answer 1

这可以通过递归地细化部分末端之间不靠近段的部分来完成。

如果我们有曲线(样条)C:[0,1]->R^n。比第一个近似值是曲线端点 [C(0), C(1)] 之间的段 S。获取点 C(0.5) 并检查它与线段 S 的距离。如果它远远超过我们必须将其离散化，如果不是S 是很好的近似值。如果 C(0.5) 很远，则下一个近似值是折线 [C(0), C(0.5), C(1)]，我们使用相同的过程部分 [C(0), C(0.5)] 和 [C(0.5), C(1)]。

如果您使用 >= 3 阶的多项式样条曲线(例如三次样条曲线)，那么它可以有拐点。在那种情况下，一半的曲线点可能会“落在”线段上，但会远离线段。在这种情况下，最好多检查一层子部分。