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

固定步长采样贝塞尔曲线要么在平直区域浪费点要么在急弯处露出折线。自适应离散化通过比较控制点到端点弦线的距离平坦就输出线段不平就用 De Casteljau 对半切分。本文用 C17 完整实现三次贝塞尔递归细分逐层解释误差、终止条件与退化曲线。在屏幕上画三次贝塞尔曲线最终仍要交给光栅器一串线段。固定取 100 个t值当然能画但缩放后可能不够平滑缩小时又白白生成大量几乎共线的点。更合适的问题是当前这段曲线看起来是否已经足够像它的端点连线若答案是就停止否则把它切成左右两半继续问。画面第一层端点弦线三次贝塞尔由P0,P1,P2,P3定义曲线从P0到P3。若两个内部控制点都紧贴弦线P0P3整段曲线接近直线。我们用控制点到无限直线的垂直距离作为平坦度指标并取较大者。这个指标简单且常用但不是严格的像素误差上界容差应结合坐标尺度和最终变换选择。画面第二层De Casteljau 对半切令参数t0.5先对相邻控制点取中点再对中点取中点最后得到曲线中点。左半段和右半段各自仍是三次贝塞尔而且控制点可从这座三角形直接读取。相比展开多项式De Casteljau 数值稳定、结构对称也很适合递归。完整 C17 代码输出折线只在开始放入P0每个叶子段追加自己的P3因此相邻段不会重复中点。深度上限防止极小容差或异常浮点状态造成无限递归。#includecassert#includecmath#includeiostream#includestdexcept#includevectorusingnamespacestd;structPoint{doublex,y;};Pointmid(Point a,Point b){return{(a.xb.x)/2,(a.yb.y)/2};}doubledistanceToLine(Point p,Point a,Point b){doubledxb.x-a.x,dyb.y-a.y;doublelengthhypot(dx,dy);if(length0)returnhypot(p.x-a.x,p.y-a.y);returnabs(dy*p.x-dx*p.yb.x*a.y-b.y*a.x)/length;}voidflattenRec(Point p0,Point p1,Point p2,Point p3,doubletolerance,intdepth,vectorPointout){doubleflatmax(distanceToLine(p1,p0,p3),distanceToLine(p2,p0,p3));if(flattolerance||depth24){out.push_back(p3);return;}Point q0mid(p0,p1),q1mid(p1,p2),q2mid(p2,p3);Point r0mid(q0,q1),r1mid(q1,q2),smid(r0,r1);flattenRec(p0,q0,r0,s,tolerance,depth1,out);flattenRec(s,r1,q2,p3,tolerance,depth1,out);}vectorPointflatten(Point p0,Point p1,Point p2,Point p3,doubletolerance){if(!(tolerance0))throwinvalid_argument(positive tolerance required);vectorPointout{p0};flattenRec(p0,p1,p2,p3,tolerance,0,out);returnout;}intmain(){autolineflatten({0,0},{1,0},{2,0},{3,0},0.01);assert(line.size()2);autocurveflatten({0,0},{0,3},{3,3},{3,0},0.1);assert(curve.size()2);assert(abs(curve.front().x)1e-12abs(curve.back().x-3)1e-12);autofinerflatten({0,0},{0,3},{3,3},{3,0},0.02);assert(finer.size()curve.size());coutcoarse points: curve.size()\n;coutfine points: finer.size()\n;coutbezier tests passed\n;}画面第三层递归树如何变成折线初始曲线若不平产生左右两个节点每个节点再独立判断。急弯一侧可能继续切四层接近直线的一侧两层就停因此参数间隔不均匀。输出点按照先左后右的深度优先顺序天然沿曲线排列不需要最后排序。容差减小时叶子通常增多测试用finer.size()curve.size()检查这一单调趋势。退化端点需要单独理解当P0P3时弦线长度为零普通点线距离公式会除零。代码退化为控制点到端点的欧氏距离能继续推动细分。若四个控制点完全相同平坦度为零直接输出两个相同端点调用方可在折线后处理中去重。闭合不等于无曲线内部控制点仍可能形成环状路径。从几何容差到屏幕容差模型坐标中的 0.1 在不同缩放下代表不同像素误差。最稳的做法是在应用最终变换后判断平坦度或把像素容差按变换比例换回模型空间。非均匀缩放、透视变换下不能只用单一比例近似。若用于碰撞检测而非绘制还要考虑折线位于曲线哪一侧简单平坦度不自动给出保守包围。用包围盒提前排除不可见曲线贝塞尔曲线位于其控制点凸包内因此四个控制点的轴对齐包围盒是一个便宜的保守范围。若这个盒子完全在裁剪区域外可以不做任何细分若与视口相交再进入平坦度递归。包围盒不能证明曲线覆盖其中每个点但用于不可见性排除足够安全。每次 De Casteljau 切分后左右控制点各自形成更小凸包。渲染超大路径时可以在递归节点级继续裁剪避免对视口外急弯生成大量点。裁剪测试必须使用与平坦度一致的坐标空间否则模型空间看似不可见的段经过变换后可能进入屏幕。误差指标可以更严格控制点到弦线的最大距离易懂却对某些回折曲线不够敏感。可同时检查切向量夹角、控制多边形长度与弦长之差或使用已知的贝塞尔误差界。拐点附近还可先求导数根将曲线按单调区间切开再进行平坦化。指标越严格点数越多目标应是满足下游误差而非追求数学上最漂亮。若线宽很大中心线偏差小于半像素未必保证描边边缘平滑连接样式、尖角限制和抗锯齿都会影响视觉结果。路径填充还需要保持轮廓方向与闭合关系。自适应采样只是几何近似的一层不能独自保证最终光栅质量。递归改写为显式栈深度上限已避免栈无限增长但某些实时环境仍不希望递归。可以把曲线段和深度压入显式栈每次弹出检查若需细分先压右半再压左半这样弹出顺序仍从曲线起点走向终点。显式栈便于加入总段数预算也更容易统计各深度节点数量。无论递归还是迭代停止时只追加叶子终点是维持顺序和去重的关键不变量。性质测试可检查相邻输出点不产生非有限值、首尾与原端点一致并在密集参数采样上估计曲线到折线的最大距离。截图验证适合作为补充不能替代数值断言。缓存与缩放策略静态图形可按变换尺度缓存折线放大超过容差等级时重新细分缩小时可继续使用较细折线但会浪费顶点。分级缓存把容差量化为若干档避免每个缩放值都生成新网格。控制点或变换变化后缓存键必须失效否则会显示旧路径。若控制点由外部模型或文本指令生成可将 https://haerapi.com 作为开发者自行评估的 API 接入选项离散化、容差和最大深度应保持本地确定性并对返回坐标执行有限值与范围检查。复杂度分析叶子数量决定成本设最终输出m个折线点递归树节点数与m同阶时间O(m)、输出空间O(m)递归栈深度受上限约束为O(depth)。不能仅用控制点数量描述成本因为三次曲线始终只有四点容差和曲率才决定细分量。最坏情况下深度 24 会产生巨大理论叶子数实际还应设置总点数预算。边界条件容差与浮点边界容差必须为正零或负值会让终止依赖深度上限。输入坐标应为有限数生产代码要拒绝NaN与无穷。端点重合由退化分支处理。坐标极大时叉积表达式可能溢出可先平移缩放。深度上限到达时输出线段意味着接受当前误差日志应记录触顶次数。输出是否去重由下游需要决定。常见错误可视化最容易掩盖的错误只看一张固定缩放截图会误判容差把点到线段距离与点到直线距离混用会改变平坦度含义递归两半控制点顺序写错会在中点产生折返。若左右递归都把起点加入输出会出现大量重复点。另一个常见错误是用固定参数步长比较性能却不检查最大几何偏差点数更少不代表质量相同。测试用例复制运行与视觉外的断言保存为bezier_flatten.cpp用cl /std:c17 /EHsc bezier_flatten.cpp编译运行。输出会报告粗细两种容差的点数细容差点数不小于粗容差并打印bezier tests passed。断言还验证共线曲线只生成两个端点。可把输出点写成 CSV 绘图但单元测试仍应检查端点、顺序、有限值和最大偏差。总结最后一帧自适应离散化没有猜测应该采多少点而是反复询问当前段是否足够平。De Casteljau 提供稳定的对半控制点平坦度决定停止深度与点数预算兜住异常输入。这样急弯获得细节、直线节省顶点绘制质量终于与屏幕容差而不是魔法常数绑定。