简介面向《三维CAD建模》课程的完整结课作业方案围绕半边数据结构展开先定义网格拓扑与五个基本欧拉操作再实现支持二维区域多内环的扫掠造型并对扫掠实体做真实感显示源码采用C编写代码、说明文档与样例模型一并打包适合计算机图形学与CAD方向的课程设计、毕业设计或自学进阶。压缩包共18个文件、仅102KB包含5个cpp与5个hpp工程源码、CMake构建配置、README与License文档、多个model_*样例数据及效果预览图结构紧凑可直接编译查看。项目代码已完整测试且运行稳定答辩评价较高具备图形学基础者可借此理解半边结构、欧拉操作与扫掠建模的完整链路也可在此基础上扩展新的功能。平台已有96人浏览学习适合正在准备课设、毕设或需要参考网格拓扑编辑与真实感显示代码的开发者。1. 半边数据结构三维CAD建模课程作业的核心枢纽拿到这样一个课程作业第一反应往往是半边结构是什么欧拉操作为什么是五个扫掠又该怎么跟前面两者接上这门课程设计的本质是用代码把一条完整的几何建模流水线跑通底层是网格的拓扑表示中间是靠欧拉操作做增量式修改上层是用扫掠生成真实可用的三维实体。对于正在学计算机图形学或CAD原理的开发者来说这条路走一遍比读十遍教材都管用。这个作业适合两类人一类是正在被课程作业卡住的学生需要一份能跑通、能讲清楚的实现思路另一类是想补网格建模基础的应用开发者想搞清楚建模内核里最经典的拓扑数据结构长什么样。半边结构的核心价值在于它把“顶点、边、面”的邻接关系全部显式记录下来让遍历邻居、检查拓扑、修改网格都变得高效且可控。接下来我就按自己做过同类项目的经验把数据定义、欧拉操作、扫掠实现和调试方法一条条拆开讲。2. 半边数据结构定义从原理到C实现2.1 为什么是半边而不是顶点或边三维网格的表示方式有好多桩顶点-面列表、翼边结构、半边结构还有现在流行的四叉树或者稀疏体素。课程作业指定半边是因为它给每一条无向边拆成了两条方向相反的有向半边每一半边只属于一个面。这样一来从一个面绕一圈访问所有边、从一个顶点出发遍历所有相邻面、检查一条边的两个邻接面都是O(1)的操作。翼边结构虽然也能做这些事情但它对顶点和面的引用方式比较绕实现起来不如半边直观。半边结构在建模软件的内核里常见像一些开源的B-Rep内核和网格处理库核心拓扑都是半边或其变体。如果你以后要去读那些开源库的源码这个作业打的基础能直接平移过去。2.2 核心结构体设计与代码实现我一般用C来写这类作业因为指针操作直接适合表达拓扑关系。先定义六个核心结构体顶点、半边、边、环、面、壳。这里壳可以先用一个简单的容器表示不必做得太重。// halfedge.h // 顶点存储三维坐标和一条从该点出发的半边 struct Vertex { float x, y, z; HalfEdge* out; // 从该顶点出发的任意一条半边 // 构造时把out置为nullptr后面每次插入半边时更新 }; // 半边核心拓扑单元 struct HalfEdge { Vertex* origin; // 起始顶点 HalfEdge* twin; // 对偶半边同一条无向边的另一半 HalfEdge* next; // 当前面内下一条半边逆时针 HalfEdge* prev; // 当前面内上一条半边 Face* face; // 该半边所属的面 Edge* edge; // 该半边所属的无向边 }; // 无向边持有两条半边 struct Edge { HalfEdge* he0; HalfEdge* he1; }; // 环首尾相连的半边序列表示面的外边界或孔洞边界 struct Loop { HalfEdge* first; // 环的第一条半边 Loop* next; // 同一个面上的下一个环孔洞 }; // 面包含一个或多个环 struct Face { Loop* outer; // 外环 Loop* inner; // 内环链表 float nx, ny, nz; // 法向计算或手动指定 }; // 壳一组面的集合这里用链表简单表达 struct Shell { Face* faces; int faceCount; };这里有几个关键点twin指针必须成对出现next和prev要构成循环链表origin指向半边的起点而不是终点。这三个约定是整个数据结构不出bug的基础我见过太多翻车案例都是因为其中一个约定没守死。Loop结构体在实现欧拉操作时用来表示“带孔的面”比如一个矩形面中间挖一个洞外环和孔洞环都在同一个面上。2.3 边界处理与不变量检查半边结构有两条必须时刻满足的不变量第一twin-twin this即对偶关系是对称的第二从任意一条半边出发沿着next指针走一定能回到起点且走过的半边都属于同一个面。我写代码时习惯在每次欧拉操作后调用一个checkInvariants()函数把整个网格扫一遍验证上述规则。这个习惯在调试时救了我很多次。另一个常见问题是边界边网格如果有开放边界边界边的twin指向nullptr。但课程作业一般是闭合实体所以我们可以规定所有边都有对偶半边。如果你的场景里有开放面记得在半边结构里额外加一个isBoundary标志否则遍历面的时候会崩溃。3. 五个基本欧拉操作拓扑修改的原子指令3.1 欧拉操作是干什么的欧拉操作是修改网格拓扑的最小原子操作它保证操作前后实体仍然满足欧拉公式V - E F - H 2(C - G)。其中V是顶点数E是边数F是面数H是孔洞数C是连通体数G是穿透孔数。课程作业要求“五个基本欧拉操作”最常用的集合是mvfs、mev、mef、kemv、kfmh。这五个操作可以组合出任意拓扑变化。它们的含义分别是mvfs创建一个包含孤立顶点的实体mev从某个顶点伸出一条新边mef在两条边之间构建一个新面kemv是mev的逆操作删除一条边并合并两个端点kfmh是删除一个面并生成一个孔洞。前三个负责“加”后两个负责“减”。整个扫掠操作本质上就是反复调用mvfs、mev、mef的过程。3.2 mvfs、mev、mef三个增加型操作以下代码按“我偏向的实现方式”给出核心是操作完成后立即恢复不变量。// 操作1: mvfs - make vertex, face, solid // 创建一个新实体包含一个孤立顶点和一个空面后续向面内添加边 Solid* mvfs(float x, float y, float z) { Solid* s new Solid(); Vertex* v new Vertex(x, y, z); Face* f new Face(); // 空面没有环外环置空后续mef会往里加环 s-vertices.push_back(v); s-faces.push_back(f); return s; } // 操作2: mev - make edge, vertex // 从顶点v1出发创建一条新边连接到新顶点v2 // 新边挂在v1所在面f的某个环上 HalfEdge* mev(Vertex* v1, float x, float y, float z, Face* f) { Vertex* v2 new Vertex(x, y, z); Edge* e new Edge(); HalfEdge* he1 new HalfEdge(); // v1 - v2 HalfEdge* he2 new HalfEdge(); // v2 - v1对偶 // 设置对偶关系 he1-twin he2; he2-twin he1; he1-edge e; he2-edge e; e-he0 he1; e-he1 he2; // 设置归属 he1-origin v1; he2-origin v2; he1-face f; // he2的face暂时归属同一个面稍后可能需要修正 v1-out he1; v2-out he2; // 将he1插入f的环中插在环首之前 Loop* loop f-outer; if (loop nullptr) { // 新建环 loop new Loop(he1); he1-next he1; he1-prev he1; // 自环 f-outer loop; } else { HalfEdge* first loop-first; HalfEdge* last first-prev; // 在first前面插入he1 he1-next first; he1-prev last; first-prev he1; last-next he1; } return he1; } // 操作3: mef - make edge, face // 在同一个面的两条半边he1和he2之间创建一条新边生成一个新面 // 常用于给多边形“切一刀”或者封闭一个环 Face* mef(HalfEdge* he1, HalfEdge* he2) { // 两条半边必须属于同一个面 Face* oldFace he1-face; Face* newFace new Face(); Edge* e new Edge(); HalfEdge* newHe1 new HalfEdge(); HalfEdge* newHe2 new HalfEdge(); // 设置对偶、归属 newHe1-twin newHe2; newHe2-twin newHe1; newHe1-edge e; newHe2-edge e; newHe1-origin he1-origin; newHe2-origin he2-origin; newHe1-face newFace; newHe2-face newFace; // 将新半边插入环路中 // 从he1到he2的路径归新面从he2到he1的路径归旧面 HalfEdge* walk he1; do { walk-face newFace; // 改归新面 walk walk-next; } while (walk ! he2); // 在he1前插入newHe2在he2前插入newHe1 // 详细插入逻辑省略核心是维护next/prev return newFace; }参数说明mvfs的三个坐标是孤立顶点的位置调用后实体里有一个面但没有边这个面后续通过mef逐步“长”出边界。mev的新边插入到指定面的环上这意味着它同时改变面的拓扑——这是初学者最容易忽略的mev不是只加一条边它还把边“缝”到了面上。mef的返回是新生成的面指针调用前要确认两条目标半边在同一个环上否则会出现两个面共用边界但拓扑不一致的问题。3.3 kemv、kfmh两个减少型操作// 操作4: kemv - kill edge, make vertex // 删除一条边把它的两个端点合并成一个顶点 // 返回合并后的顶点 Vertex* kemv(Edge* e) { HalfEdge* he1 e-he0; HalfEdge* he2 e-he1; Vertex* v1 he1-origin; Vertex* v2 he2-origin; // 删除边e和两条半边 // 将v2合并到v1所有以v2为起点的半边改以v1为起点 HalfEdge* walk v2-out; do { walk-origin v1; walk walk-twin-next; } while (walk ! v2-out); // 如果v1没有出边则把v1-out指向v2-out if (v1-out nullptr) v1-out v2-out; // 删除he1和he2修正环结构he1-prev-next he1-nexthe2同理 removeHalfEdgeFromLoop(he1); removeHalfEdgeFromLoop(he2); delete e; delete he1; delete he2; delete v2; return v1; } // 操作5: kfmh - kill face, make hole // 删除一个面使它的边界变成相邻面的孔洞 void kfmh(Face* faceToKill) { Loop* loop faceToKill-outer; HalfEdge* walk loop-first; // 把该面上所有半边归属到相邻面 do { walk-face walk-twin-face; walk walk-next; } while (walk ! loop-first); // 将该环作为孔洞加入相邻面 Face* adjFace loop-first-twin-face; loop-next adjFace-inner; adjFace-inner loop; // 从solid的faces列表删除faceToKill }kemv的合并逻辑有个陷阱遍历v2的出边时必须用twin-next推进因为直接next会跨越到另一个面去。kfmh最典型的使用场景是把一个内部面删除让两个相邻区域连通——比如做布尔运算时的部分操作。注意合并顶点时v1和v2不能是同一个点否则walk循环会死循环。3.4 组合欧拉操作构造基本体素有了这五个原子操作就可以像搭积木一样构造任何多面体。比如构造一个四面体先mvfs创建点A然后三次mev创建B、C、D三条边最后用mef分别闭合ABC、ACD、ABD三个面。每个面闭合时注意选择正确的两条半边路径。常见的错误是mef执行完一次后原来的面被分割成两个面之前的半边归属已经变了再操作时容易拿到已经“属于新面”的半边。我建议每调完一个欧拉操作都把那部分网格的面-边关系打印出来核对一遍这是最笨但最有效的办法。4. 扫掠操作从轮廓到实体的完整流程4.1 扫掠的基本原理与分类扫掠sweep是把一个二维轮廓沿一条路径移动扫过的空间形成一个三维实体。最基础的是平移扫掠轮廓沿直线方向拉伸得到棱柱体。进阶的是旋转扫掠轮廓绕固定轴旋转得到旋转体。更复杂的还有沿任意曲线路径扫掠这时需要计算路径上每个点的切向量和法向量用来确定轮廓在截面处的朝向。课程作业的常见要求是平移扫掠加上旋转扫掠。平移扫掠实现简单适合跑通整套数据结构和欧拉操作旋转扫掠则能检测你对“截面变换”的理解因为旋转后的轮廓平面会跟着变。如果作业文档里有“实现扫掠操作”这样一句话通常两个都得做。4.2 平移扫掠的完整实现步骤平移扫掠的算法思路先把轮廓多边形用半边结构建好用欧拉操作然后沿着法线方向复制N层轮廓每层之间用mef生成侧面对。代码可以这样拆// sweep_translate.cpp // 输入轮廓顶点列表按逆时针拉伸方向dir层数layers Solid* sweepTranslate(vectorVertex* contour, Vec3 dir, int layers) { // 第一步用mvfs创建第一个顶点 Solid* solid mvfs(contour[0]-x, contour[0]-y, contour[0]-z); // 第二步用mev创建轮廓的其余顶点建立底面的边 vectorHalfEdge* baseEdges; HalfEdge* prev nullptr; for (int i 1; i contour.size(); i) { HalfEdge* he mev(contour[i]-vert, contour[i]-x, contour[i]-y, contour[i]-z, solid-faces[0]); baseEdges.push_back(he); prev he; } // 第三步用mef闭合底面 Face* bottomFace mef(baseEdges.front(), baseEdges.back()); // 第四步逐层生成平移副本 vectorVertex* prevLayer contour; for (int layer 1; layer layers; layer) { // 对新一层每个顶点执行mev vectorVertex* currLayer; for (auto v : prevLayer) { Vertex* nv new Vertex(v-x dir.x * layer, v-y dir.y * layer, v-z dir.z * layer); currLayer.push_back(nv); mev(v, nv-x, nv-y, nv-z, solid-faces[0]); } // 用mef连接相邻层的对应顶点生成侧面四边形 for (int i 0; i contour.size(); i) { int j (i 1) % contour.size(); // 在prevLayer[i]-prevLayer[j]-currLayer[j]-currLayer[i]之间创建面 HalfEdge* he1 findHalfEdge(prevLayer[i], prevLayer[j]); HalfEdge* he2 findHalfEdge(currLayer[j], currLayer[i]); mef(he1, he2); } prevLayer currLayer; } // 第五步封闭顶面 Face* topFace mef(/* 顶层轮廓的两条半边 */); return solid; }这里有几个关键参数要调layers决定实体的细分精度层数越多侧面越平滑但面数也线性增长dir是拉伸方向向量如果方向不垂直于轮廓平面生成的是斜棱柱几何上没问题但底面和顶面的法向量计算会变复杂。代码里的findHalfEdge函数需要额外实现它的作用是根据两个顶点找到对应的半边——最直接的方式是遍历顶点out指针绕一圈找。4.3 旋转扫掠截面变换与法向量修正旋转扫掠的差异点在每层的截面位置不再是用向量平移而是绕旋转轴旋转固定角度。变换矩阵是这个环节的核心。绕Z轴旋转的矩阵在最简单场景下长这样// 绕Z轴旋转角度theta void rotateZ(Vertex* v, float theta) { float x v-x, y v-y; v-x x * cos(theta) - y * sin(theta); v-y x * sin(theta) y * cos(theta); }但更一般的旋转变换应该用四元数或3x3矩阵实现因为旋转轴可能是任意方向。我推荐把变换统一封装成一个applyTransform(Vertex* v, Mat4 m)函数后续扩展沿路径扫掠时能直接复用。旋转体的拓扑结构和平移扫掠基本一致区别是最后一层要和第一层闭合即“旋转360度”后轮廓回到起点。这时候有个特殊处理如果旋转轴穿过轮廓那么轴上的顶点扫掠后仍然在轴上这些顶点会被多层截面共用直接套用逐层生成会创建重复顶点。需要先检测哪些顶点在轴上对这些顶点单独处理要么只生成一次要么生成后合并。合并操作正好可以用kemv完成这也是为什么欧拉操作和扫掠要放在同一个作业里——它们的组合天然能处理这类拓扑修正。4.4 扫掠结果的欧拉公式验证无论用哪种扫掠生成完实体后都要用欧拉公式做一次校验。我通常这样写// validate.cpp bool checkEuler(Solid* s) { int V s-vertices.size(); int E s-edges.size(); // 半边数除以2才是无向边数 int F s-faces.size(); // 闭合流形V - E/2 F 2 return (V - E/2 F) 2; }如果是带孔洞的实体公式扩展为V - E F - H 2(C - G)H是环的总数减面数孔洞环数G是穿透孔的个数。课程作业做扫掠出来的都是凸实体或简单凹实体一般用第一条公式就够了。如果校验不过不代表代码一定错也可能是实体本身有边界比如你没封顶面这时先检查是不是漏了最后一个mef。5. 半边与欧拉操作的常见问题排查四条血泪经验5.1 现象next指针死循环程序卡住或栈溢出原因某条半边的next没有正确指向环内的下一条或者prev-next没有同步更新。最常见的是在mev插入新半边时只改了next没改prev导致环断开。 解决写一个validateLoop(Loop* loop)函数遍历环上的半边计数如果数量超过顶点数的两倍立即报错并打印环首地址。每次操作后调用能快速定位是哪一步破坏了环路。5.2 现象执行mef后面的法向量方向反了原因mef创建新面时半边的方向没有和原有面的环绕方向保持一致。如果新面的半边路径是顺时针而旧面是逆时针面的朝向就反了。显示的时候背面被剔除看起来面消失。 解决在mef里强制检查新面的半边路径必须满足next的方向与法向量成右手定则。简单做法是mef完成后计算新面中心用叉积验证法向如果法向与期望方向相反交换新边的两条半边。5.3 现象扫掠后侧面出现三角形“裂缝”原因相邻两层轮廓的顶点数量不一致或者mef时选择的半边对不对应。常见于旋转扫掠时轴上的顶点被合并导致某一层比另一层少了顶点。 解决在扫掠前先统计每层顶点数若发现不一致打印出具体是哪一层的哪个顶点缺失。轴上的顶点应该在生成前标记为isAxisVertex在层间连接时跳过这些顶点改用特殊的“扇形闭合”策略。5.4 现象欧拉公式验证通过但模型渲染错乱原因拓扑正确但几何坐标有误。比如mev创建新顶点时坐标传错了或者旋转扫掠的变换矩阵乘反了。 解决把顶点的坐标直接打印出来用外部脚本画成点云和理论形状对比。如果点云对但渲染不对问题在面片顶点索引映射如果点云就不对检查变换矩阵或mev的传参顺序。这里有个技巧给每个顶点加上id并打印到OBJ文件里可以快速追踪顶点在拓扑和几何上的双重状态。5.5 现象kemv后出现悬空半边程序访问空指针原因kemv删除边时没有处理与它相邻的半边引用。特别是当被删除边的某一个端点是孤立顶点时它out指针可能仍然指向已经删除的半边。 解决kemv执行后遍历所有邻接顶点把它们的out指针重置为新顶点的out。同时检查被删除边的邻接面是否还有完整环如果没有就说明拓扑被破坏了需要回滚或重建。6. 用OBJ导出加拓扑可视化调试验证扫掠结果扫掠做完最直观的验证方式是把实体导出成OBJ格式用外部查看器观察。这一步能同时验证几何和拓扑几何错误在渲染时一眼可见拓扑错误则常以“破面”“错乱面片”的形式暴露。我习惯为调试写一个独立的导出函数参数里加一个开关控制是否输出半边的origin顶点编号。导出OBJ的代码很简单先写顶点再写面。但要注意OBJ的面索引是从1开始的而且法向量需要从半边方向计算。写出来大约40行。导出后在查看器里旋转模型观察每个面的朝向是否一致、有没有内凹导致的遮挡问题。如果发现某个面始终显示为黑色说明它的法向反了回头检查这个面是由哪次mef生成的基本能定位到欧拉操作里方向处理的漏洞。另一个更进阶的验证是程序化测试随机生成一组欧拉操作序列每执行一步就调用欧拉公式校验和环路完整性检查。这个方法能一次性发现所有五个操作里的隐藏bug。我自己做过一个模拟项目X当时就是用这种随机操作加断言的方式把二十多个逻辑错误一次性揪干净。做完扫掠后再回头审视整个作业你会发现半边数据结构其实是一种“用空间换时间”的设计每个顶点都记住一条出边每个面都记住一条半边的入口所有修改都是在指针之间绕来绕去。初写时觉得绕写多了就觉得顺手。最后给你的建议不要一上来就写扫掠先把五个欧拉操作全测一遍确保任意组合后欧拉公式成立再动扫掠。这一步踏稳了扫掠只是把轮廓切开、逐层调用欧拉操作而已。希望这篇笔记能帮你少走几步弯路。本文还有配套的精品资源点击获取