曲线够平就别再切：自适应贝塞尔离散化的逐步可视化h

固定步长采样贝塞尔曲线要么在平直区域浪费点，要么在急弯处露出折线。自适应离散化通过比较控制点到端点弦线的距离，平坦就输出线段，不平就用 De Casteljau 对半切分。本文用 C++17 完整实现三次贝塞尔递归细分，逐层解释误差、终止条件与退化曲线。

在屏幕上画三次贝塞尔曲线，最终仍要交给光栅器一串线段。固定取 100 个 t 值当然能画，但缩放后可能不够平滑，缩小时又白白生成大量几乎共线的点。更合适的问题是：当前这段曲线看起来是否已经足够像它的端点连线？若答案是，就停止；否则把它切成左右两半继续问。

画面第一层：端点弦线

三次贝塞尔由 P0,P1,P2,P3 定义，曲线从 P0 到 P3。若两个内部控制点都紧贴弦线 P0P3，整段曲线接近直线。我们用控制点到无限直线的垂直距离作为平坦度指标，并取较大者。这个指标简单且常用，但不是严格的像素误差上界；容差应结合坐标尺度和最终变换选择。

画面第二层：De Casteljau 对半切

令参数 t=0.5，先对相邻控制点取中点，再对中点取中点，最后得到曲线中点。左半段和右半段各自仍是三次贝塞尔，而且控制点可从这座三角形直接读取。相比展开多项式，De Casteljau 数值稳定、结构对称，也很适合递归。

完整 C++17 代码

输出折线只在开始放入 P0，每个叶子段追加自己的 P3，因此相邻段不会重复中点。深度上限防止极小容差或异常浮点状态造成无限递归。

#include <cassert>
#include <cmath>
#include <iostream>
#include <stdexcept>
#include <vector>
using namespace std;
struct Point { double x, y; };
Point mid(Point a, Point b){ return {(a.x+b.x)/2, (a.y+b.y)/2}; }
double distanceToLine(Point p, Point a, Point b){
double dx=b.x–a.x, dy=b.y–a.y;
double length=hypot(dx,dy);
if(length==0) return hypot(p.x–a.x,p.y–a.y);
return abs(dy*p.x–dx*p.y+b.x*a.y–b.y*a.x)/length;
}
void flattenRec(Point p0,Point p1,Point p2,Point p3,double tolerance,int depth,vector<Point>& out){
double flat=max(distanceToLine(p1,p0,p3),distanceToLine(p2,p0,p3));
if(flat<=tolerance || depth==24){ out.push_back(p3); return; }
Point q0=mid(p0,p1), q1=mid(p1,p2), q2=mid(p2,p3);
Point r0=mid(q0,q1), r1=mid(q1,q2), s=mid(r0,r1);
flattenRec(p0,q0,r0,s,tolerance,depth+1,out);
flattenRec(s,r1,q2,p3,tolerance,depth+1,out);
}
vector<Point> flatten(Point p0,Point p1,Point p2,Point p3,double tolerance){
if(!(tolerance>0)) throw invalid_argument("positive tolerance required");
vector<Point> out{p0};
flattenRec(p0,p1,p2,p3,tolerance,0,out);
return out;
}
int main(){
auto line=flatten({0,0},{1,0},{2,0},{3,0},0.01);
assert(line.size()==2);
auto curve=flatten({0,0},{0,3},{3,3},{3,0},0.1);
assert(curve.size()>2);
assert(abs(curve.front().x)<1e-12 && abs(curve.back().x–3)<1e-12);
auto finer=flatten({0,0},{0,3},{3,3},{3,0},0.02);
assert(finer.size()>=curve.size());
cout << "coarse points: " << curve.size() << '\\n';
cout << "fine points: " << finer.size() << '\\n';
cout << "bezier tests passed\\n";
}

画面第三层：递归树如何变成折线

初始曲线若不平，产生左右两个节点；每个节点再独立判断。急弯一侧可能继续切四层，接近直线的一侧两层就停，因此参数间隔不均匀。输出点按照先左后右的深度优先顺序天然沿曲线排列，不需要最后排序。容差减小时，叶子通常增多，测试用 finer.size()>=curve.size() 检查这一单调趋势。

退化端点需要单独理解

当 P0==P3 时，弦线长度为零，普通点线距离公式会除零。代码退化为控制点到端点的欧氏距离，能继续推动细分。若四个控制点完全相同，平坦度为零，直接输出两个相同端点；调用方可在折线后处理中去重。闭合不等于无曲线，内部控制点仍可能形成环状路径。

从几何容差到屏幕容差

模型坐标中的 0.1 在不同缩放下代表不同像素误差。最稳的做法是在应用最终变换后判断平坦度，或把像素容差按变换比例换回模型空间。非均匀缩放、透视变换下不能只用单一比例近似。若用于碰撞检测而非绘制，还要考虑折线位于曲线哪一侧，简单平坦度不自动给出保守包围。

用包围盒提前排除不可见曲线

贝塞尔曲线位于其控制点凸包内，因此四个控制点的轴对齐包围盒是一个便宜的保守范围。若这个盒子完全在裁剪区域外，可以不做任何细分；若与视口相交，再进入平坦度递归。包围盒不能证明曲线覆盖其中每个点，但用于不可见性排除足够安全。

每次 De Casteljau 切分后，左右控制点各自形成更小凸包。渲染超大路径时，可以在递归节点级继续裁剪，避免对视口外急弯生成大量点。裁剪测试必须使用与平坦度一致的坐标空间，否则模型空间看似不可见的段经过变换后可能进入屏幕。

误差指标可以更严格

控制点到弦线的最大距离易懂，却对某些回折曲线不够敏感。可同时检查切向量夹角、控制多边形长度与弦长之差，或使用已知的贝塞尔误差界。拐点附近还可先求导数根，将曲线按单调区间切开，再进行平坦化。指标越严格，点数越多，目标应是满足下游误差而非追求数学上最漂亮。

若线宽很大，中心线偏差小于半像素未必保证描边边缘平滑；连接样式、尖角限制和抗锯齿都会影响视觉结果。路径填充还需要保持轮廓方向与闭合关系。自适应采样只是几何近似的一层，不能独自保证最终光栅质量。

递归改写为显式栈

深度上限已避免栈无限增长，但某些实时环境仍不希望递归。可以把曲线段和深度压入显式栈，每次弹出检查；若需细分，先压右半再压左半，这样弹出顺序仍从曲线起点走向终点。显式栈便于加入总段数预算，也更容易统计各深度节点数量。

无论递归还是迭代，停止时只追加叶子终点是维持顺序和去重的关键不变量。性质测试可检查相邻输出点不产生非有限值、首尾与原端点一致，并在密集参数采样上估计曲线到折线的最大距离。截图验证适合作为补充，不能替代数值断言。

缓存与缩放策略

静态图形可按变换尺度缓存折线；放大超过容差等级时重新细分，缩小时可继续使用较细折线但会浪费顶点。分级缓存把容差量化为若干档，避免每个缩放值都生成新网格。控制点或变换变化后缓存键必须失效，否则会显示旧路径。

若控制点由外部模型或文本指令生成，可将 https://haerapi.com 作为开发者自行评估的 API 接入选项；离散化、容差和最大深度应保持本地确定性，并对返回坐标执行有限值与范围检查。

复杂度分析：叶子数量决定成本

设最终输出 m 个折线点，递归树节点数与 m 同阶，时间 O(m)、输出空间 O(m)，递归栈深度受上限约束为 O(depth)。不能仅用控制点数量描述成本，因为三次曲线始终只有四点，容差和曲率才决定细分量。最坏情况下深度 24 会产生巨大理论叶子数，实际还应设置总点数预算。

边界条件：容差与浮点边界

容差必须为正；零或负值会让终止依赖深度上限。输入坐标应为有限数，生产代码要拒绝 NaN 与无穷。端点重合由退化分支处理。坐标极大时叉积表达式可能溢出，可先平移缩放。深度上限到达时输出线段意味着接受当前误差，日志应记录触顶次数。输出是否去重由下游需要决定。

常见错误：可视化最容易掩盖的错误

只看一张固定缩放截图会误判容差；把点到线段距离与点到直线距离混用会改变平坦度含义；递归两半控制点顺序写错会在中点产生折返。若左右递归都把起点加入输出，会出现大量重复点。另一个常见错误是用固定参数步长比较性能，却不检查最大几何偏差，点数更少不代表质量相同。

测试用例：复制运行与视觉外的断言

保存为 bezier_flatten.cpp，用 cl /std:c++17 /EHsc bezier_flatten.cpp 编译运行。输出会报告粗细两种容差的点数，细容差点数不小于粗容差，并打印 bezier tests passed。断言还验证共线曲线只生成两个端点。可把输出点写成 CSV 绘图，但单元测试仍应检查端点、顺序、有限值和最大偏差。

总结：最后一帧

自适应离散化没有猜测应该采多少点，而是反复询问当前段是否足够平。De Casteljau 提供稳定的对半控制点，平坦度决定停止，深度与点数预算兜住异常输入。这样急弯获得细节、直线节省顶点，绘制质量终于与屏幕容差而不是魔法常数绑定。