先说个实在话计算机图形学这门课理论听的时候觉得“就这”真到头歌平台上一关一关敲代码的时候才发现处处是坑。这套“计算机图形学头歌合集题集附解”整理的就是我在实训过程中反复踩坑、反复调试后沉淀下来的完整题解和思路拆解。不管你是正在被 OpenGL 环境配置折磨的新手还是画线画圆算法总差几个像素的老兄或者光照模型调出来一片死黑的倒霉蛋这份合集应该都能帮上忙。1. 题集全貌与整体解题思路1.1 这套题集到底覆盖了哪些内容头歌平台上的计算机图形学实训不同学校、不同老师配置的关卡顺序可能略有差异但核心知识点基本是固定的。我整理这套合集时把题目按照图形学经典的“输入-处理-输出”流水线重新归了类方便你建立整体认知。实操下来题目大致分为五个模块第一个模块是 OpenGL 基础环境搭建与第一个三角形主要卡在环境配置和坐标理解第二个模块是光栅化算法包括 DDA、Bresenham 画线、中点画圆、Bresenham 画圆第三个模块是区域填充与裁剪扫描线填充、种子填充、Cohen-Sutherland 编码裁剪、Liang-Barsky 参数化裁剪第四个模块是几何变换与投影二维三维平移旋转缩放、正交投影和透视投影的矩阵推导第五个模块是曲线曲面与光照Bezier 曲线、B样条曲线、Phong 光照模型、Blinn-Phong 光照模型。每一类题目在头歌上的考核方式也不同有的要求你补全关键函数有的要求你直接用 OpenGL 绘制出正确图形还有的是纯数学推导后输出计算结果。我见过很多同学在画线算法上花了一下午结果卡在了“输出格式不对”这种提交问题上所以这套合集里不光是算法代码还有针对不同评测方式的提交流程提醒。1.2 刷这套题集的正确姿势我必须先泼一盆冷水这套题集不适合零基础的同学直接上手“抄答案”。头歌平台的实训设计通常是“代码补全 本地验证 平台评测”三段式它希望你先理解框架再填核心逻辑。如果你直接对着题解抄一遍确实能过评测但到了期末考试或者面试手撕算法的时候你会发现自己什么都不会。我的建议是三步走。第一步先自己读一遍题目给的框架代码搞清楚每个参数的含义和函数之间的调用关系第二步自己尝试写核心函数写到实在卡住了再翻题解重点看卡住的这一小段第三步通过评测之后回头用自己的话把算法流程写一遍能默写出来才算真正掌握。这套合集里每道题我都按这个逻辑组织的先讲题目在考什么、给出关键原理和公式推导再给完整的可提交代码最后附上我在调试中遇到的典型问题和解决方案。你完全可以把题解当成“带 debug 注释的参考实现”来用而不是单纯的答案。2. 光栅化算法题画线画圆的核心解法2.1 DDA 与 Bresenham 画线浮点累加与整数决策画线算法是整套题集里最基础也最容易出问题的地方。DDADigital Differential Analyzer算法的思路很直白从起点到终点沿着主位移方向每次步进一个单位另一个方向按斜率 k 累加。核心代码框架如下void DDALine(int x0, int y0, int x1, int y1) { int dx x1 - x0, dy y1 - y0; int steps (abs(dx) abs(dy)) ? abs(dx) : abs(dy); float xIncrement dx / (float)steps; float yIncrement dy / (float)steps; float x x0, y y0; for (int i 0; i steps; i) { glVertex2i(round(x), round(y)); x xIncrement; y yIncrement; } }DDA 的实现最简单但头歌的评测里有不少坑。第一steps必须取abs(dx)和abs(dy)中的较大值否则斜率大于 1 或小于 -1 时画出来的线会出现断点第二坐标要用round()而不是直接强转成int因为浮点数的舍入误差会导致像素偏移一个单位第三glVertex2i接收的是整数坐标所以循环内部必须先把浮点坐标取整再传进去顺序不能反。Bresenham 画线则是完全基于整数运算核心思想是维护一个决策参数 p根据 p 的符号决定下一个像素是走“右上”还是“正右”。这个算法的推导过程在题解里非常重要因为头歌有时候会直接考“请写出决策参数 p 的更新公式”。以斜率 0 到 1 的情况为例void BresenhamLine(int x0, int y0, int x1, int y1) { int dx abs(x1 - x0), dy abs(y1 - y0); int sx (x0 x1) ? 1 : -1; int sy (y0 y1) ? 1 : -1; int err dx - dy; while (true) { glVertex2i(x0, y0); if (x0 x1 y0 y1) break; int e2 2 * err; if (e2 -dy) { err - dy; x0 sx; } if (e2 dx) { err dx; y0 sy; } } }上面这版是“对称版”Bresenham它能处理任意方向的直线是头歌题目里最通用的写法。注意err的初始值是dx - dy这个不是随便写的它对应着中点算法里 F(M) 0 的初始判断。每次迭代先计算e2 2 * err再分别判断是否在 x 方向和 y 方向上前进这比教材上只针对第一象限的写法更实用。2.2 中点画圆与 Bresenham 画圆八分对称性圆的光栅化算法比直线稍微绕一点但核心都是利用圆的八分对称性——只要生成第一象限 45 度到 90 度之间的一段圆弧其他部分通过对称变换就能补全。中点画圆的关键在于维护决策参数 d初始值d 1 - r然后根据 d 的符号判断下一个点是正右还是右下。void MidPointCircle(int r) { int x 0, y r; int d 1 - r; while (x y) { glVertex2i(x, y); glVertex2i(y, x); glVertex2i(-x, y); glVertex2i(y, -x); glVertex2i(x, -y); glVertex2i(-y, -x); glVertex2i(-x, -y); glVertex2i(-y, x); if (d 0) { d 2 * x 3; } else { d 2 * (x - y) 5; y--; } x; } }这里最容易错的是决策参数 d 的更新公式。当 d 0 时中点位于圆内选择正右点d 增量是2*x 3当 d 0 时中点位于圆外或圆上选择右下点d 增量是2*(x - y) 5同时 y 要减 1。这个“3”和“5”不是拍脑袋定的它们是根据增量计算推导出来的正右点时新决策参数等于旧值加2*(x1) 1即加2*x 3右下点时等于旧值加2*(x1) - 2*(y-1) 1即加2*(x-y) 5。2.3 画线画圆题的核心排错技巧我做这套题集时总结了一个规律画线和画圆题在头歌上报错绝大多数不是算法逻辑错而是坐标系搞混。OpenGL 默认的剪裁坐标系是 [-1, 1] × [-1, 1]但很多学校的实训题用的是窗口像素坐标比如 800×600 的窗口。如果不做坐标映射画出来的图形要么只在左下角一小块要么直接超出窗口看不见。另一个常见坑是 OpenGL 渲染模式。头歌的框架代码里通常已经写好了glBegin(GL_POINTS)和glEnd()你只需要在中间调用glVertex2i即可。但有同学会在循环里误写glBegin和glEnd导致 OpenGL 报 “GL_INVALID_OPERATION” 错误。记住画点模式下所有顶点必须在一个glBegin和glEnd之间循环外面开、循环外面关。提示头歌平台的图形学题目大部分会在评测时自动截图或者比对像素点所以输出坐标的精度很重要。本地调试时画出来的线如果断断续续先检查是不是步进方向判断写反了如果整条线偏了检查坐标系映射和 round 取整。3. 填充、裁剪与变换最容易丢分的三类题3.1 扫描线填充和种子填充的考点差异多边形区域填充在头歌题集里一般有两种实现方式扫描线填充和种子填充。扫描线填充是考点中的重点因为它涉及数据结构边表 ET 和活动边表 AET的维护代码量明显大于其他题目。核心思路是先把多边形的每条边按照“交点的 x 坐标”挂到对应的扫描线上构建边表然后从上到下逐条扫描线处理维护活动边表按 x 坐标排序后配对填充区间。我在做这题的时候发现最容易被坑的地方是边表构建时的“奇点处理”。对于水平边直接跳过不处理对于局部极值点比如三角形的顶点需要把该边在交点计数时少计一次。处理方法是构建边表时对每条非水平边取ymin min(y1, y2)ymax max(y1, y2)并且只在ymin到ymax-1这一范围内记录边。如果你不加这个ymax-1在顶点处会重复填充或漏填一行像素。种子填充相对简单一些通常用递归实现从头歌评测来说也能过但要注意递归深度。如果多边形内部像素非常多超过系统栈限制会爆栈。我一般建议用显式栈模拟递归或者直接改成扫描线种子填充以区间为单位入栈这样一次性填充一行栈的规模很小。头歌的测试用例有时候会故意给一个超大多边形来检验你的算法鲁棒性递归版本很容易超时或者运行时错误。3.2 编码裁剪与参数化裁剪本质都是求交点区间Cohen-Sutherland 编码裁剪是必考题。它用四位编码表示端点相对于窗口的位置上、下、右、左分别对应二进制位 0001、0010、0100、1000。算法流程是先计算两端点的编码 c1 和 c2如果(c1 | c2) 0说明整条线在窗口内直接保留如果(c1 c2) ! 0说明两端点在同一窗口外侧区域整条线在窗口外直接舍弃否则就需要求交裁剪。求交时要注意编码裁剪是按“窗口边界”逐一求交一次裁剪掉一个方向。比如先右边界、再左边界、再上边界、再下边界。每一轮裁剪后要重新计算新端点的编码这一步千万别漏。我见过有同学只算了一次编码就开始循环结果死循环出不来了。Liang-Barsky 参数化裁剪是另一种思路它把直线表示为参数方程x x0 u * dxy y0 u * dy然后通过四个不等式求出参数 u 的有效区间[u1, u2]。初始u1 0, u2 1逐条判断四条边界不断收缩区间。如果u1 u2说明线段完全在窗口外。这题的优势是计算量小而且不用反复求交点在头歌评测里通过率更高。3.3 二维三维变换与投影的矩阵推导变换类的题目里最核心的是搞清楚齐次坐标和矩阵乘法顺序。二维变换中平移、旋转、缩放分别是平移: [1 0 tx; 0 1 ty; 0 0 1] 旋转: [cosθ -sinθ 0; sinθ cosθ 0; 0 0 1] 缩放: [sx 0 0; 0 sy 0; 0 0 1]复合变换的大坑在于矩阵乘法的顺序。假如要求“先旋转再平移”变换矩阵是T * R而不是R * T。因为点 p 在列向量表示时最右侧的矩阵最先作用于点。很多同学搞反之后图形旋转后平移的距离就不对——在头歌上会直接表现为图形位置偏了一大截。三维变换和投影就更复杂了。透视投影矩阵的推导是个重点核心是“相似三角形”原理。视点位于原点观察平面在 z -d 处那么空间点 (x, y, z) 投影到观察平面上的坐标为(x * d / (-z), y * d / (-z))。为了把它写成矩阵形式要用齐次坐标中的 w 分量。头歌中通常会给你一个 4×4 的矩阵框架让你填入正确的投影矩阵元素。注意在 OpenGL 中gluPerspective已经封装了透视矩阵的计算但头歌出于考核目的往往要求你手算并填入矩阵或者自己实现一个myPerspective函数。这时候不要偷懒直接用 GLU 函数老老实实推导一遍对理解图形学管线很有帮助。4. 曲线曲面与光照模型公式记忆与应用要点4.1 Bezier 曲线与 B样条曲线的代码实现Bezier 曲线在头歌中的常规考法是给定控制点计算曲线上 t 从 0 到 1 范围内若干个采样点的坐标。最稳妥的实现方式是 de Casteljau 递推算法而不是直接从 Bernstein 基函数展开。de Casteljau 的代码简洁且不容易出错Point deCasteljau(vectorPoint pts, float t) { vectorPoint tmp pts; int n tmp.size(); for (int k 1; k n; k) { for (int i 0; i n - k; i) { tmp[i].x (1 - t) * tmp[i].x t * tmp[i 1].x; tmp[i].y (1 - t) * tmp[i].y t * tmp[i 1].y; } } return tmp[0]; }这个算法本质是重复线性插值把相邻控制点两两连线在新连线上按比例 t 取点生成新的控制点序列直到只剩一个点。头歌的评测一般会比对离散点的坐标所以采样密度要足够大至少 100 个点以上否则曲线看起来会有明显折线感。B样条曲线比 Bezier 复杂的地方在于节点向量knot vector和基函数的递推计算。考试题一般给定均匀节点向量就够了。实现时可以用 Cox-de Boor 递推公式递归计算基函数 N(i,k)(t)也可以直接预计算。递归版本的代码量小但要注意递归深度k 阶基函数在 t 的每一段上最多递归 k 层一般不会爆栈。我写题解时用的是迭代预计算的方式虽然代码长一点但运行速度更快评测超时的风险也低。4.2 Phong 光照与 Blinn-Phong 光照的必背公式光照模型是图形学题集里公式最密集的部分。Phong 光照模型把光照拆成环境光、漫反射、镜面反射三项I ka * Ia kd * Il * max(0, N·L) ks * Il * max(0, R·V)^n其中 ka、kd、ks 分别是环境光、漫反射、镜面反射系数N 是法向量L 是光源方向R 是反射方向V 是视线方向n 是高光指数。注意这里的“·”是点积且所有向量都要归一化——这是最容易忽略的点。OpenGL 中如果 glEnable(GL_NORMALIZE) 没有开启法向量不归一化会直接导致光照效果出现明显的亮暗分界。Blinn-Phong 模型是 Phong 的一个改进版本它用半程向量 H 代替了反射向量 R 的计算H normalize(L V) I ka * Ia kd * Il * max(0, N·L) ks * Il * max(0, N·H)^n表面上看只是把R·V换成了N·H但计算量和物理合理性都更好。头歌题目有时会让你在同一个场景中比较两种光照模型如果你只改了半程向量而忘了把指数 n 调整效果会差别很大。Blinn-Phong 的高光区域更大更柔和Phong 则更尖锐实际调参时 Phong 的 n 要取大一些才能得到相似的观感。5. 头歌平台提交避坑与调试实录5.1 评测机制与常见报错速查头歌的图形学实训评测方式比较特殊有的关卡是比对输出图片的像素有的关卡是比对函数返回值或控制台输出。我整理了实操中最高频的几类报错和对应解法做成表格方便你快速查阅报错现象常见原因解决方案图形空白或只有部分显示坐标超出剪裁范围检查投影设置坐标除以合适比例使图形居中线段断断续续步进方向判断错误或 steps 取值有误按主位移方向取 steps确保 x/y 增量绝对值不超过 1图形位置整体偏移矩阵乘法顺序错误或坐标系映射错误确认复合变换是 TR 还是 RT用中点坐标验证光照一片黑或一片花法向量未归一化开启 glEnable(GL_NORMALIZE)或手动 normalize填充出现少量空隙扫描线填充奇点处理错误边表中 ymax 取值减 1跳过水平边提交后显示运行超时递归填充或采样点过密改用显式栈/扫描线填充降低采样点数5.2 我用下来的调试技巧与心得我调试图形学题时最常用的方法是在关键位置加临时的printf输出中间计算结果。比如画线算法中把每个像素坐标打印出来和标准的 Bresenham 逐点结果对比很容易定位是哪一步决策参数算错了。头歌的在线评测环境一般支持标准输出所以这个调试方法在本地和平台都适用。第二个技巧是先用小规模数据验证。比如画圆时先画半径 5 的圆把点打印出来手动检查八分对称性验证通过后再提交半径 50 的用例。这样既节省时间又能快速定位问题。头歌的测试用例有时候会包含多组数据小半径能过的算法在大半径下不一定没问题比如 Bresenham 画圆的决策参数是 int 类型半径很大时 d 值可能溢出需要改用 long long。第三个技巧也是最重要的本地编译环境要和头歌的环境尽量保持一致。头歌的图形学实训一般在 Linux 环境用 freeglut 库Windows 上默认的 glut 库和它有一些细微差异比如glutInitDisplayMode的参数不同可能导致窗口显示效果不一致。我在本地统一用 MinGW freeglut 配置这样提交之前就能保证和评测环境行为一致。5.3 关于“题集附解”的正确打开方式最后说点掏心窝的话。这份合集的价值不在于让你“秒过”头歌的所有关卡而在于让你在卡住的时候能有一个参照系。我整理题解时特意把每个算法背后的推导过程、每个令我抓狂的坑都写了进去。比如画圆那个“d 增量是 3 还是 5”的问题课本上只有一句话但真正自己推导一遍、跑一遍才会明白为什么正右点时中点的相对位置变化量是2x3。如果你正在头歌平台上被某道图形学题目折磨我的建议是先别看题解给自己 30 分钟把草稿纸拿出来画一画、推一推推不出来再翻题解看卡住的那一行然后合上题解继续写。这套流程走下来你对图形学算法的理解会比直接抄答案深刻得多。我个人在实际操作中的体会是图形学这门课代码只是表象数学才是灵魂。头歌上的每道题本质上都在逼你把“为什么这么做”想清楚。等你把画线、填充、变换、光照这四关都打通了回头再看 OpenGL 那些 API会突然有一种“原来如此”的通透感。这套合集就是一个带你过关的拐杖拐杖使完记得扔掉才能真正跑起来。
先说个实在话计算机图形学这门课理论听的时候觉得“就这”真到头歌平台上一关一关敲代码的时候才发现处处是坑。这套“计算机图形学头歌合集题集附解”整理的就是我在实训过程中反复踩坑、反复调试后沉淀下来的完整题解和思路拆解。不管你是正在被 OpenGL 环境配置折磨的新手还是画线画圆算法总差几个像素的老兄或者光照模型调出来一片死黑的倒霉蛋这份合集应该都能帮上忙。1. 题集全貌与整体解题思路1.1 这套题集到底覆盖了哪些内容头歌平台上的计算机图形学实训不同学校、不同老师配置的关卡顺序可能略有差异但核心知识点基本是固定的。我整理这套合集时把题目按照图形学经典的“输入-处理-输出”流水线重新归了类方便你建立整体认知。实操下来题目大致分为五个模块第一个模块是 OpenGL 基础环境搭建与第一个三角形主要卡在环境配置和坐标理解第二个模块是光栅化算法包括 DDA、Bresenham 画线、中点画圆、Bresenham 画圆第三个模块是区域填充与裁剪扫描线填充、种子填充、Cohen-Sutherland 编码裁剪、Liang-Barsky 参数化裁剪第四个模块是几何变换与投影二维三维平移旋转缩放、正交投影和透视投影的矩阵推导第五个模块是曲线曲面与光照Bezier 曲线、B样条曲线、Phong 光照模型、Blinn-Phong 光照模型。每一类题目在头歌上的考核方式也不同有的要求你补全关键函数有的要求你直接用 OpenGL 绘制出正确图形还有的是纯数学推导后输出计算结果。我见过很多同学在画线算法上花了一下午结果卡在了“输出格式不对”这种提交问题上所以这套合集里不光是算法代码还有针对不同评测方式的提交流程提醒。1.2 刷这套题集的正确姿势我必须先泼一盆冷水这套题集不适合零基础的同学直接上手“抄答案”。头歌平台的实训设计通常是“代码补全 本地验证 平台评测”三段式它希望你先理解框架再填核心逻辑。如果你直接对着题解抄一遍确实能过评测但到了期末考试或者面试手撕算法的时候你会发现自己什么都不会。我的建议是三步走。第一步先自己读一遍题目给的框架代码搞清楚每个参数的含义和函数之间的调用关系第二步自己尝试写核心函数写到实在卡住了再翻题解重点看卡住的这一小段第三步通过评测之后回头用自己的话把算法流程写一遍能默写出来才算真正掌握。这套合集里每道题我都按这个逻辑组织的先讲题目在考什么、给出关键原理和公式推导再给完整的可提交代码最后附上我在调试中遇到的典型问题和解决方案。你完全可以把题解当成“带 debug 注释的参考实现”来用而不是单纯的答案。2. 光栅化算法题画线画圆的核心解法2.1 DDA 与 Bresenham 画线浮点累加与整数决策画线算法是整套题集里最基础也最容易出问题的地方。DDADigital Differential Analyzer算法的思路很直白从起点到终点沿着主位移方向每次步进一个单位另一个方向按斜率 k 累加。核心代码框架如下void DDALine(int x0, int y0, int x1, int y1) { int dx x1 - x0, dy y1 - y0; int steps (abs(dx) abs(dy)) ? abs(dx) : abs(dy); float xIncrement dx / (float)steps; float yIncrement dy / (float)steps; float x x0, y y0; for (int i 0; i steps; i) { glVertex2i(round(x), round(y)); x xIncrement; y yIncrement; } }DDA 的实现最简单但头歌的评测里有不少坑。第一steps必须取abs(dx)和abs(dy)中的较大值否则斜率大于 1 或小于 -1 时画出来的线会出现断点第二坐标要用round()而不是直接强转成int因为浮点数的舍入误差会导致像素偏移一个单位第三glVertex2i接收的是整数坐标所以循环内部必须先把浮点坐标取整再传进去顺序不能反。Bresenham 画线则是完全基于整数运算核心思想是维护一个决策参数 p根据 p 的符号决定下一个像素是走“右上”还是“正右”。这个算法的推导过程在题解里非常重要因为头歌有时候会直接考“请写出决策参数 p 的更新公式”。以斜率 0 到 1 的情况为例void BresenhamLine(int x0, int y0, int x1, int y1) { int dx abs(x1 - x0), dy abs(y1 - y0); int sx (x0 x1) ? 1 : -1; int sy (y0 y1) ? 1 : -1; int err dx - dy; while (true) { glVertex2i(x0, y0); if (x0 x1 y0 y1) break; int e2 2 * err; if (e2 -dy) { err - dy; x0 sx; } if (e2 dx) { err dx; y0 sy; } } }上面这版是“对称版”Bresenham它能处理任意方向的直线是头歌题目里最通用的写法。注意err的初始值是dx - dy这个不是随便写的它对应着中点算法里 F(M) 0 的初始判断。每次迭代先计算e2 2 * err再分别判断是否在 x 方向和 y 方向上前进这比教材上只针对第一象限的写法更实用。2.2 中点画圆与 Bresenham 画圆八分对称性圆的光栅化算法比直线稍微绕一点但核心都是利用圆的八分对称性——只要生成第一象限 45 度到 90 度之间的一段圆弧其他部分通过对称变换就能补全。中点画圆的关键在于维护决策参数 d初始值d 1 - r然后根据 d 的符号判断下一个点是正右还是右下。void MidPointCircle(int r) { int x 0, y r; int d 1 - r; while (x y) { glVertex2i(x, y); glVertex2i(y, x); glVertex2i(-x, y); glVertex2i(y, -x); glVertex2i(x, -y); glVertex2i(-y, -x); glVertex2i(-x, -y); glVertex2i(-y, x); if (d 0) { d 2 * x 3; } else { d 2 * (x - y) 5; y--; } x; } }这里最容易错的是决策参数 d 的更新公式。当 d 0 时中点位于圆内选择正右点d 增量是2*x 3当 d 0 时中点位于圆外或圆上选择右下点d 增量是2*(x - y) 5同时 y 要减 1。这个“3”和“5”不是拍脑袋定的它们是根据增量计算推导出来的正右点时新决策参数等于旧值加2*(x1) 1即加2*x 3右下点时等于旧值加2*(x1) - 2*(y-1) 1即加2*(x-y) 5。2.3 画线画圆题的核心排错技巧我做这套题集时总结了一个规律画线和画圆题在头歌上报错绝大多数不是算法逻辑错而是坐标系搞混。OpenGL 默认的剪裁坐标系是 [-1, 1] × [-1, 1]但很多学校的实训题用的是窗口像素坐标比如 800×600 的窗口。如果不做坐标映射画出来的图形要么只在左下角一小块要么直接超出窗口看不见。另一个常见坑是 OpenGL 渲染模式。头歌的框架代码里通常已经写好了glBegin(GL_POINTS)和glEnd()你只需要在中间调用glVertex2i即可。但有同学会在循环里误写glBegin和glEnd导致 OpenGL 报 “GL_INVALID_OPERATION” 错误。记住画点模式下所有顶点必须在一个glBegin和glEnd之间循环外面开、循环外面关。提示头歌平台的图形学题目大部分会在评测时自动截图或者比对像素点所以输出坐标的精度很重要。本地调试时画出来的线如果断断续续先检查是不是步进方向判断写反了如果整条线偏了检查坐标系映射和 round 取整。3. 填充、裁剪与变换最容易丢分的三类题3.1 扫描线填充和种子填充的考点差异多边形区域填充在头歌题集里一般有两种实现方式扫描线填充和种子填充。扫描线填充是考点中的重点因为它涉及数据结构边表 ET 和活动边表 AET的维护代码量明显大于其他题目。核心思路是先把多边形的每条边按照“交点的 x 坐标”挂到对应的扫描线上构建边表然后从上到下逐条扫描线处理维护活动边表按 x 坐标排序后配对填充区间。我在做这题的时候发现最容易被坑的地方是边表构建时的“奇点处理”。对于水平边直接跳过不处理对于局部极值点比如三角形的顶点需要把该边在交点计数时少计一次。处理方法是构建边表时对每条非水平边取ymin min(y1, y2)ymax max(y1, y2)并且只在ymin到ymax-1这一范围内记录边。如果你不加这个ymax-1在顶点处会重复填充或漏填一行像素。种子填充相对简单一些通常用递归实现从头歌评测来说也能过但要注意递归深度。如果多边形内部像素非常多超过系统栈限制会爆栈。我一般建议用显式栈模拟递归或者直接改成扫描线种子填充以区间为单位入栈这样一次性填充一行栈的规模很小。头歌的测试用例有时候会故意给一个超大多边形来检验你的算法鲁棒性递归版本很容易超时或者运行时错误。3.2 编码裁剪与参数化裁剪本质都是求交点区间Cohen-Sutherland 编码裁剪是必考题。它用四位编码表示端点相对于窗口的位置上、下、右、左分别对应二进制位 0001、0010、0100、1000。算法流程是先计算两端点的编码 c1 和 c2如果(c1 | c2) 0说明整条线在窗口内直接保留如果(c1 c2) ! 0说明两端点在同一窗口外侧区域整条线在窗口外直接舍弃否则就需要求交裁剪。求交时要注意编码裁剪是按“窗口边界”逐一求交一次裁剪掉一个方向。比如先右边界、再左边界、再上边界、再下边界。每一轮裁剪后要重新计算新端点的编码这一步千万别漏。我见过有同学只算了一次编码就开始循环结果死循环出不来了。Liang-Barsky 参数化裁剪是另一种思路它把直线表示为参数方程x x0 u * dxy y0 u * dy然后通过四个不等式求出参数 u 的有效区间[u1, u2]。初始u1 0, u2 1逐条判断四条边界不断收缩区间。如果u1 u2说明线段完全在窗口外。这题的优势是计算量小而且不用反复求交点在头歌评测里通过率更高。3.3 二维三维变换与投影的矩阵推导变换类的题目里最核心的是搞清楚齐次坐标和矩阵乘法顺序。二维变换中平移、旋转、缩放分别是平移: [1 0 tx; 0 1 ty; 0 0 1] 旋转: [cosθ -sinθ 0; sinθ cosθ 0; 0 0 1] 缩放: [sx 0 0; 0 sy 0; 0 0 1]复合变换的大坑在于矩阵乘法的顺序。假如要求“先旋转再平移”变换矩阵是T * R而不是R * T。因为点 p 在列向量表示时最右侧的矩阵最先作用于点。很多同学搞反之后图形旋转后平移的距离就不对——在头歌上会直接表现为图形位置偏了一大截。三维变换和投影就更复杂了。透视投影矩阵的推导是个重点核心是“相似三角形”原理。视点位于原点观察平面在 z -d 处那么空间点 (x, y, z) 投影到观察平面上的坐标为(x * d / (-z), y * d / (-z))。为了把它写成矩阵形式要用齐次坐标中的 w 分量。头歌中通常会给你一个 4×4 的矩阵框架让你填入正确的投影矩阵元素。注意在 OpenGL 中gluPerspective已经封装了透视矩阵的计算但头歌出于考核目的往往要求你手算并填入矩阵或者自己实现一个myPerspective函数。这时候不要偷懒直接用 GLU 函数老老实实推导一遍对理解图形学管线很有帮助。4. 曲线曲面与光照模型公式记忆与应用要点4.1 Bezier 曲线与 B样条曲线的代码实现Bezier 曲线在头歌中的常规考法是给定控制点计算曲线上 t 从 0 到 1 范围内若干个采样点的坐标。最稳妥的实现方式是 de Casteljau 递推算法而不是直接从 Bernstein 基函数展开。de Casteljau 的代码简洁且不容易出错Point deCasteljau(vectorPoint pts, float t) { vectorPoint tmp pts; int n tmp.size(); for (int k 1; k n; k) { for (int i 0; i n - k; i) { tmp[i].x (1 - t) * tmp[i].x t * tmp[i 1].x; tmp[i].y (1 - t) * tmp[i].y t * tmp[i 1].y; } } return tmp[0]; }这个算法本质是重复线性插值把相邻控制点两两连线在新连线上按比例 t 取点生成新的控制点序列直到只剩一个点。头歌的评测一般会比对离散点的坐标所以采样密度要足够大至少 100 个点以上否则曲线看起来会有明显折线感。B样条曲线比 Bezier 复杂的地方在于节点向量knot vector和基函数的递推计算。考试题一般给定均匀节点向量就够了。实现时可以用 Cox-de Boor 递推公式递归计算基函数 N(i,k)(t)也可以直接预计算。递归版本的代码量小但要注意递归深度k 阶基函数在 t 的每一段上最多递归 k 层一般不会爆栈。我写题解时用的是迭代预计算的方式虽然代码长一点但运行速度更快评测超时的风险也低。4.2 Phong 光照与 Blinn-Phong 光照的必背公式光照模型是图形学题集里公式最密集的部分。Phong 光照模型把光照拆成环境光、漫反射、镜面反射三项I ka * Ia kd * Il * max(0, N·L) ks * Il * max(0, R·V)^n其中 ka、kd、ks 分别是环境光、漫反射、镜面反射系数N 是法向量L 是光源方向R 是反射方向V 是视线方向n 是高光指数。注意这里的“·”是点积且所有向量都要归一化——这是最容易忽略的点。OpenGL 中如果 glEnable(GL_NORMALIZE) 没有开启法向量不归一化会直接导致光照效果出现明显的亮暗分界。Blinn-Phong 模型是 Phong 的一个改进版本它用半程向量 H 代替了反射向量 R 的计算H normalize(L V) I ka * Ia kd * Il * max(0, N·L) ks * Il * max(0, N·H)^n表面上看只是把R·V换成了N·H但计算量和物理合理性都更好。头歌题目有时会让你在同一个场景中比较两种光照模型如果你只改了半程向量而忘了把指数 n 调整效果会差别很大。Blinn-Phong 的高光区域更大更柔和Phong 则更尖锐实际调参时 Phong 的 n 要取大一些才能得到相似的观感。5. 头歌平台提交避坑与调试实录5.1 评测机制与常见报错速查头歌的图形学实训评测方式比较特殊有的关卡是比对输出图片的像素有的关卡是比对函数返回值或控制台输出。我整理了实操中最高频的几类报错和对应解法做成表格方便你快速查阅报错现象常见原因解决方案图形空白或只有部分显示坐标超出剪裁范围检查投影设置坐标除以合适比例使图形居中线段断断续续步进方向判断错误或 steps 取值有误按主位移方向取 steps确保 x/y 增量绝对值不超过 1图形位置整体偏移矩阵乘法顺序错误或坐标系映射错误确认复合变换是 TR 还是 RT用中点坐标验证光照一片黑或一片花法向量未归一化开启 glEnable(GL_NORMALIZE)或手动 normalize填充出现少量空隙扫描线填充奇点处理错误边表中 ymax 取值减 1跳过水平边提交后显示运行超时递归填充或采样点过密改用显式栈/扫描线填充降低采样点数5.2 我用下来的调试技巧与心得我调试图形学题时最常用的方法是在关键位置加临时的printf输出中间计算结果。比如画线算法中把每个像素坐标打印出来和标准的 Bresenham 逐点结果对比很容易定位是哪一步决策参数算错了。头歌的在线评测环境一般支持标准输出所以这个调试方法在本地和平台都适用。第二个技巧是先用小规模数据验证。比如画圆时先画半径 5 的圆把点打印出来手动检查八分对称性验证通过后再提交半径 50 的用例。这样既节省时间又能快速定位问题。头歌的测试用例有时候会包含多组数据小半径能过的算法在大半径下不一定没问题比如 Bresenham 画圆的决策参数是 int 类型半径很大时 d 值可能溢出需要改用 long long。第三个技巧也是最重要的本地编译环境要和头歌的环境尽量保持一致。头歌的图形学实训一般在 Linux 环境用 freeglut 库Windows 上默认的 glut 库和它有一些细微差异比如glutInitDisplayMode的参数不同可能导致窗口显示效果不一致。我在本地统一用 MinGW freeglut 配置这样提交之前就能保证和评测环境行为一致。5.3 关于“题集附解”的正确打开方式最后说点掏心窝的话。这份合集的价值不在于让你“秒过”头歌的所有关卡而在于让你在卡住的时候能有一个参照系。我整理题解时特意把每个算法背后的推导过程、每个令我抓狂的坑都写了进去。比如画圆那个“d 增量是 3 还是 5”的问题课本上只有一句话但真正自己推导一遍、跑一遍才会明白为什么正右点时中点的相对位置变化量是2x3。如果你正在头歌平台上被某道图形学题目折磨我的建议是先别看题解给自己 30 分钟把草稿纸拿出来画一画、推一推推不出来再翻题解看卡住的那一行然后合上题解继续写。这套流程走下来你对图形学算法的理解会比直接抄答案深刻得多。我个人在实际操作中的体会是图形学这门课代码只是表象数学才是灵魂。头歌上的每道题本质上都在逼你把“为什么这么做”想清楚。等你把画线、填充、变换、光照这四关都打通了回头再看 OpenGL 那些 API会突然有一种“原来如此”的通透感。这套合集就是一个带你过关的拐杖拐杖使完记得扔掉才能真正跑起来。
