简介《三维CAD建模》课程作业定义了半边数据结构并基于该结构实现五个基本欧拉操作以及支持带多个内环的二维区域扫掠操作最终将构建的实体模型进行真实感图形显示完整覆盖了CAD建模的核心流程。压缩包共18个文件以C的cpp/hpp源文件为主辅以配置文件、模型数据、PNG效果图及Markdown说明等整体仅102KB小巧但结构清晰适合直接下载学习。代码均测试运行成功作者表示答辩平均分达96分适合计算机相关专业学生用于课程设计、毕业设计或项目初期演示。已有96人学习浏览下载后可在本地直接编译运行也可在此基础上修改扩展实现更多建模功能。需要远程教学或运行指导可与作者私聊联系。1. 半边数据结构课程作业从拓扑骨架到扫掠成体如果有人问你三维CAD建模里最核心的数据结构是什么答案大概率是半边结构Half-Edge。它把顶点、边、面的拓扑关系组织成一张可以高速遍历的网几乎所有能叫上名字的商业内核都在用它。这份课程作业资源做的正是这件事从零定义半边数据结构实现五个基础欧拉操作再基于欧拉操作完成带多内环的扫掠Sweep建模最后做真实感显示。适合正在做图形学课设、毕业设计或者想弄懂CAD内核拓扑原理的人。难点不在写代码而在理解欧拉操作的先后顺序和拓扑约束——这是整个资源含金量最高的地方。2. 先立骨架半边数据结构的定义与五个基础欧拉操作2.1 半边结构到底在维护什么从实体到拓扑的映射关系把任何一个三维实体想成一堆面片拼起来的封闭外壳每个无向边拆成两条方向相反的有向边这就是半边。每条半边只归属一个面记录它的起点、下一条半边、所属面以及配对半边。这样设计的好处是从任意一条半边出发能沿着面的边界走一圈再通过配对边跳到相邻面整个实体变成一个可遍历的图。这份资源里的main.hpp和CreateSolid.hpp定义了核心数据结构。我在本地复现时看到的是典型的字段组合顶点坐标、半边指针、面指针以及用于建立配对关系的twin指针。还有一个细节值得注意——代码里大量用shared_ptr管理半边和顶点而不是裸指针。这对后续欧拉操作的异常安全很有帮助因为欧拉操作中最容易翻车的就是指针悬挂删除一个面但没同步清理相邻半边的指向遍历时直接崩掉。struct HalfEdge { std::shared_ptrVertex vertex; // 该半边指向的终点顶点 std::shared_ptrHalfEdge twin; // 配对半边方向相反 std::shared_ptrHalfEdge next; // 同面下一条半边 std::shared_ptrFace face; // 所属面 }; struct Solid { std::vectorstd::shared_ptrFace faces; std::vectorstd::shared_ptrHalfEdge edges; std::vectorstd::shared_ptrVertex vertices; };逻辑说明vertex指向的是这条半边在下一条半边遍历时的顶点注意它存的是终点而不是起点——这是很多初学者第一次看会懵的地方。取起点的正确方式是twin-vertex。next指针沿着面边界逆时针走twin跳到相邻面两者组合起来就是完整的拓扑遍历。参数说明如果你的工程不需要跨函数频繁复制拓扑用shared_ptr没问题但如果追求极致性能原始指针加引用计数会更快课程作业场景不需要考虑这个。这套数据结构直接决定了后面五个欧拉操作的实现难度。操作无非是“建”“删”“改”的组合但因为半边结构要求每一步操作完成后拓扑必须自洽所以每一步都要同时维护好vertex、twin、next三套指针。常见做法是把指针更新集中在一处避免散落在各个操作里。2.2 五个欧拉操作逐个拆MVFS、MEV、MEF、KEMR、KFMRH欧拉操作的核心思想很简单每一步操作都不改变实体的欧拉示性数即 V - E F 2 - 2GG 为穿透孔个数。五个基本操作对应的是“从无到有”和“从有到无”的原子步骤。这份资源里的EulerOperation.cpp实现了以下五个MVFSMake Vertex, Face, Solid从空场景创建一个含一个孤立顶点、一张空面、一个新体的初始状态。这是所有建模的第一步。代码实现里要同时 new 三个对象然后用faces、vertices、edges三个向量管理起来。MEVMake Edge, Vertex在已有顶点的基础上加一条边和一个新顶点构成一条新的半边界。扫掠操作的第一步不是直接拉面而是先用 MEV 把二维轮廓的底边骨架搭出来。注意MEV 加边时必须同时创建一对待配对的半边只建一条的话后续遍历就会断链。MEFMake Edge, Face在两个已有顶点之间加一条边同时生成一个新面。这一步是扫掠操作的核心——它把封闭的二维轮廓“缝合”成一张完整的面。实现时有个关键点要判断两个顶点之间是否已有路径连通否则会生成非流形结构。KEMRKill Edge, Make Ring删掉一条边同时在一个面上创建一个内环。这是处理带孔洞二维区域的关键操作。比如你要扫掠一个“回”字形截面内环就是靠 KEMR 建出来的。实现时容易被忽略的是删除边后相邻面的边界指针要重新定向。KFMRHKill Face, Make Ring Hole删掉一张面同时把它变成一个孔洞环。这个操作常用于把实体内部挖穿。作业里如果只做简单扫掠可能不会触发它但完整实现时它是闭环里不可缺少的一环。// MVFS 的核心逻辑创建孤立点与空面 Solid* mvfs(const Point3D p) { Solid* s new Solid(); Vertex* v new Vertex(p); Face* f new Face(); // 初始面没有边next 指针置空 f-halfEdge nullptr; // 把三个对象挂到 Solid 的管理向量里 s-vertices.push_back(v); s-faces.push_back(f); return s; }逻辑说明MVFS 是整个欧拉操作链的入口。注意Face结构里通常会有一个halfEdge字段指向该面边界上任意一条半边作为遍历起点。空面的halfEdge为nullptr后续 MEF 操作会在这里挂上真正的边界边。参数说明Point3D是三维坐标结构体源码里在main.hpp中定义支持x、y、z三个分量。如果你把Face里的halfEdge设计成std::shared_ptr那么nullptr判断和赋值都要注意引用计数变化。五个操作之间有严格的依赖顺序。MVFS 创建骨架MEV 加边加点MEF 闭合面KEMR 和 KFMRH 做挖孔和删面。作业里要求扫掠操作允许二维区域带多个内环所以 KEMR 是必用操作。实现顺序错了会直接导致拓扑自洽性被破坏后面 debug 会非常痛苦。2.3 从代码层面理解欧拉操作为什么要按顺序调用我在翻阅CreateSolid.cpp时发现了一个值得注意的设计它没有把五个欧拉操作封装成独立函数后到处乱调而是全部收敛到一个类里类内部维护一个当前操作的上下文对象。这种设计的好处是每一步操作都从同一个状态出发上一个操作的结果直接成为下一个操作的输入出错时能快速定位是哪一步产生的脏数据。// 典型的操作顺序先建体再逐条建边最后闭合面 Solid* solid euler-mvfs(origin); HalfEdge* e1 euler-mev(solid-vertices[0], p1); HalfEdge* e2 euler-mev(solid-vertices[1], p2); Face* f euler-mef(solid-vertices[0], solid-vertices[2]);逻辑说明这段代码展示了扫掠第一步的拓扑骨架搭建过程——先用 MVFS 创建一个孤立顶点再连续两次 MEV 把轮廓的折线边建出来最后用 MEF 把首尾顶点连起来闭合面。参数说明mev返回的是新建的半边不是顶点也不是面要拿到新顶点需要通过返回的半边去访问。这个细节很多人踩坑直接用返回值当顶点用编译期不报错运行期逻辑全错。五个欧拉操作不是可以任意排列的。MVFS 之后必须 MEVMEV 之后才能 MEF这是拓扑结构决定的面要存在必须先有边边要存在必须先有点。KEMR 必须在面存在之后才能调用因为它是在已有面上挖环。这个依赖顺序就是作业评分里“是否正确理解欧拉操作”的核心判断依据。3. 把平面推成实体扫掠操作的分步实现与多内环处理3.1 扫掠的参数模型轮廓、路径与内环坐标扫掠Sweep的本质是给定一个二维轮廓沿某个方向把它推移一段距离从而生成三维实体。最朴素的扫掠是线性拉伸——轮廓沿法向平移。但这份作业的要求比拉伸复杂一层轮廓内部可以带多个内环也就是截面形状上可以有孔洞。代码里CreateSolid.cpp中定义了扫掠的输入参数核心是两大块轮廓坐标数组和扫掠矢量。轮廓坐标按外环逆时针、内环顺时针的顺序传入这个方向规定不是可选的——它直接决定生成的面的法向朝向。外环逆时针面的法向朝外内环顺时针对应面的法向朝内。如果方向传反了生成出来的实体面法向混乱真实感渲染阶段会出现半边黑半边白的情况。struct SweepProfile { std::vectorstd::vectorPoint2D loops; // loops[0] 是外环其余是内环 Point3D sweepDir; // 扫掠方向长度表示拉伸距离 }; Solid* createSweptSolid(const SweepProfile profile) { Solid* s new Solid(); // 第一步在 z0 平面构造外环和内环的面 Face* bottomFace buildProfileFace(s, profile.loops); // 第二步沿 sweepDir 方向平移轮廓到目标平面 Face* topFace copyFaceTranslated(bottomFace, profile.sweepDir); // 第三步连接上下环的对应顶点生成侧面 buildSideFaces(s, bottomFace, topFace); return s; }逻辑说明这段代码展示了扫掠操作的完整流程三层结构非常清晰。第一步先用欧拉操作在二维平面上构建出带孔洞的底面第二步把整个轮廓沿sweepDir平移一份第三步在底和顶的对应顶点之间搭侧面。参数说明loops是一个二维向量外层是“环”的集合内层是每个环上的点序列sweepDir不要求是单位向量它的模长就是扫掠高度直接决定实体的拉伸长度。3.2 多内环的实现路径不是简单挖空了事多内环的困难不在“挖空”本身而在扫掠生成侧面时内环和外环的侧面处理逻辑完全不同。外环的侧面是一圈“凸”出来的墙内环的侧面是“凹”进去的孔壁。代码里buildSideFaces函数对这个区别做了分支处理遍历轮廓环时区分外环与内环给内环生成的侧面做反向法向修正。void buildSideFaces(Solid* s, Face* bottom, Face* top) { // 遍历底面所有环外环索引 0内环索引 1..n for (size_t i 0; i bottom-loops.size(); i) { bool isInner (i 0); // 沿环的每一条边生成一个四边形侧面 for (HalfEdge* e : bottom-loopEdges[i]) { Face* side createQuadFromEdge(s, e); if (isInner) { reverseFaceNormal(side); // 内环侧面法向要反向 } } } }逻辑说明外环的侧面法向朝外内环的侧面法向必须朝内否则渲染时光照方向是反的模型会呈现“内壁发黑”的效果。reverseFaceNormal在源码里通过交换半边的遍历方向实现不是真的去修改法向量数值。参数说明createQuadFromEdge需要传入底面环上的一条半边它会自动在顶面对应位置找配对顶点生成一个四边形面。这个函数内部会调用 MEF 操作所以这里也验证了欧拉操作是扫掠的“原子积木”。多内环作业里最常见的翻车点不是代码逻辑而是欧拉操作调用顺序。我本地运行时发现如果先建内环的侧面再建外环某些半边指针会丢失正确的next关系导致遍历底面环时少一条边。这个问题的根因是内环和外环共享同一个底面面片的边界环链MEF 操作在环境中插入新边时如果没有正确更新前驱半边的next指针链就会断。3.3 扫掠操作的输入校验作业没写但你应该加的防御代码里其实没有完善的输入合法性校验全靠调用者自觉。我在调试时发现轮廓坐标里有重复点、环没有闭合、内环和外环有交点这三类问题会直接让欧拉操作产生非流形结构——具体表现就是遍历到某条半边时它的next指向了自己。虽然这不是作业要求的必做项但我建议你在调用扫掠函数之前先加一个简单的检查所有环的首尾点必须重合内环必须完全包含于外环内部任意两条环之间不允许有交点。bool validateProfile(SweepProfile profile) { for (auto loop : profile.loops) { if (loop.front() ! loop.back()) return false; // 检查环是否闭合 } // 检查内环是否在外环内取内环任意点做射线法 for (size_t i 1; i profile.loops.size(); i) { Point2D testP profile.loops[i][0]; if (!pointInLoop(testP, profile.loops[0])) return false; } return true; }逻辑说明射线法判断点在多边形内部的算法在很多入门图形学书里都有这里不赘述。关键是你的工程必须在扫掠开始前做这个校验否则欧拉操作的错误很难追踪。参数说明loop.front() ! loop.back()比较的是二维坐标的 x 和 y如果实现Point2D时用了浮点记得加一个很小的容差 eps比如 1e-6而不是直接等号比较——否则手工输入坐标会在闭合检查上误报失败。这部分的经验是欧拉操作本身是低层原语它不管你的输入物理上是否合理只保证“给定合法输入输出合法拓扑”。所以上层的几何合法性校验必须自己做教材里不会讲这个但实际作业踩坑时百分之百会碰到。4. 编译、运行与排查在本地把工程跑起来的完整记录4.1 构建配置与目录结构CMakeLists 的正确打开方式资源里带了CMakeLists.txt和build目录这是直观的加分项。说明代码工程不是单文件堆砌而是能构建成完整可执行程序的组织方式。我在本地跑的时候用的命令是标准的 CMake 三步走mkdir build-local cd build-local cmake .. -DCMAKE_BUILD_TYPEDebug cmake --build . --parallel 4逻辑说明我另建了一个build-local目录而不是直接用资源自带的build目录目的很纯粹不想污染原始文件万一某个配置要反复调整删掉自己的目录重新来就行。参数说明-DCMAKE_BUILD_TYPEDebug会关闭编译优化保留调试符号方便在 GDB 里打断点跟踪半边指针的赋值过程如果只是想看运行效果改成Release模式运行速度更快。--parallel 4是并行编译参数4 是 CPU 物理核数可以根据你的机器配置调整。成功构建后会在build-local目录下生成可执行文件。源码里的main.cpp是程序入口它读取模型文件、调用扫掠函数、启动显示窗口。userInteraction.cpp负责鼠标键盘交互display.cpp负责 OpenGL 渲染。从文件分工就能看出这份作业的完成度不低——它不是一个只有算法的裸代码而是带交互和显示的完整应用。4.2 模型文件格式与四个测试模型的结构资源里附带四个模型文件0.model_8、1.model_C、2.model_A、3.model_D。乍看后缀名很奇怪但打开看内容后就会发现这是一种非常朴素的文本格式。每一行代表一个顶点或一个面顶点用坐标标记面用顶点的索引序列标记首行通常是顶点的总数。8 0.0 0.0 0.0 1.0 0.0 0.0 1.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 1.0 1.0 0.0 1.0 1.0 1.0 1.0 0.0 1.0 1.0 4 0 1 2 3 4 4 5 6 7 ...逻辑说明这段示例对应一个六面体的部分内容第一行的 8 表示有 8 个顶点接着 8 行是顶点坐标再往后每行第一个数表示该面由几个顶点构成后面跟着顶点索引。参数说明模型文件之所以有两套数字和扫掠操作直接相关——它记录的是扫掠前生成的“二维区域”的轮廓描述CreateSolid.cpp读取后先构建面片再沿路径扫掠成体。三个模型文件分别对应不同的截面形状来源有的外环带一个内环有的带两个有的内环形状是不规则的。你可以逐个加载起来看代码对不同拓扑的处理差异。这四个文件的编号也有意思是作者从生成程序里直接输出的测试用例顺序就是开发过程中从简单到复杂的调试顺序。4.3 交互与显示模块的使用边界哪些能改哪些别动display.cpp和userInteraction.cpp是容易被忽略但很重要的两个文件。前者处理 OpenGL 渲染后者处理鼠标键盘事件。代码本身不复杂——渲染部分基本是标准的固定管线顶点绘制交互部分是围绕相机旋转展开的。我在复现时注意到一个典型问题如果 GPU 驱动不支持某个旧版 OpenGL 特性显示窗口会直接黑屏。这不是代码逻辑问题而是环境兼容问题。// display.cpp 中的典型渲染循环结构 void renderScene() { glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); glLoadIdentity(); setupCamera(); // 根据鼠标输入设置视角 drawSolidFaces(); // 遍历半边结构画所有面片 glutSwapBuffers(); }逻辑说明setupCamera依赖userInteraction.cpp里的全局相机状态变量鼠标拖动时修改这个变量的值渲染循环每次执行时读取最新值并更新视角。drawSolidFaces是顶点和法向量的核心绘制函数它要遍历Solid对象中的所有面通过半边结构的next链把每个面的所有顶点索引收集起来再交给 OpenGL。参数说明GL_DEPTH_BUFFER_BIT必须保留否则面片的前后遮挡关系会错乱转视角时后面的面会穿到前面来。如果你看到模型半透明或“透视”了首要检查就是清除标志里是否少了深度位。这个模块在作业里承载“真实感图形显示”的功能因此在评分标准里是加分项。但你要清楚它的定位它只是辅助验证工具不要花太多时间优化渲染效率除非你想进一步做真实感增强比如加光照模型那是可选的扩展方向。4.4 避坑自查清单拓扑遍历、内环方向与渲染黑屏这一部分直接照着我踩过的坑逐条检查比盲调查有效率得多。现象一扫掠出来的实体在显示窗口里“缺一块”面或者某个面在特定视角下消失。原因半边结构的next指针链断裂遍历面边界时漏掉了一条边。解决在drawSolidFaces函数里加一条断言——每个面的半边遍历步数必须等于该面的顶点数量如果不等打印出面的索引和遍历步数定位到具体是哪一步 MEF 操作破坏了链。现象二内环方向传反实体内部的结构完全错乱。原因外环逆时针、内环顺时针是约定俗成的方向规则但代码里没有自动归一化直接信任调用者的输入。解决在buildProfileFace的入口处加一个多边形方向判定函数鞋带公式自动把外环逆时针化、内环顺时针化再传给欧拉操作。现象三OpenGL 窗口黑屏但没有任何报错。原因可能是系统默认 OpenGL 版本过低或者代码里用了GLUT的旧接口在 Wayland 环境下会话兼容有问题。解决启动程序时在命令行加export LIBGL_ALWAYS_SOFTWARE1仅限 Linux强制走软件渲染验证逻辑是否正确如果软件渲染能显示而硬件渲染不行就是驱动配置问题和工程项目无关。现象四CMake 配置时提示找不到某个依赖库。原因资源里的 CMakeLists 大概率假设你已经安装过基本的图形库开发包。解决Ubuntu/Debian 系执行sudo apt install freeglut3-dev补依赖RedHat 系用sudo yum install freeglut-devel装完重新跑一遍 CMake 配置命令即可。现象五读入模型文件后程序直接崩溃没有任何提示。原因绝大多数情况是顶点索引越界模型文件里某个面引用了不存在的顶点编号。解决在CreateSolid.cpp的文件读取函数里把每个面的索引值在读入后就立刻做上下界检查越界就打印错误信息并跳过该面而不是直接把半开放的数据传给欧拉操作。这一步不是作业要求但能省掉大量 debug 时间。5. 进阶验证拓扑合法性自检与 Beyond 作业的扩展玩法5.1 用欧拉公式自动验证操作结果作业评分能看到“运行成功”但看不到你的拓扑是否自洽。给自己加一道保险在每次扫掠操作完成后遍历当前Solid的顶点、半边、面计算 V - E F并比对公式预期值。对无洞实体欧拉示性数是 2带一个洞是 0带两个洞是 -2。你可以设计一个自动断言在控制台输出校验结果这比肉眼判断靠谱得多。void validateSolid(Solid* s) { int V s-vertices.size(); int E s-edges.size() / 2; // 边数 半边数 / 2 int F s-faces.size(); int chi V - E F; // 对扫掠生成的实体G 内环数chi 2 - 2G int expected 2 - 2 * (int)(/* 得到当前实体的内环数 */); printf(欧拉示性数: %d (预期 %d)\n, chi, expected); if (chi ! expected) printf(警告: 拓扑可能不自洽!\n); }逻辑说明代码里的expected计算高度依赖你正确统计内环数量典型情况是一个内环对应一个穿透孔所以 G 的值等于内环总数。如果你在扫掠过程中 KEMR 被多次调用可以维护一个计数器记录调用次数。参数说明边的数量之所以要除以 2是因为半边结构里每条无向边对应两条有向半边edges容器里存的是半边数量。运行此函数后如果实数与预期值不匹配说明之前某个欧拉操作执行有误。这其实不是作业要求但我在多个类似工程里都用这个做“拓扑连接性和正确性的最终防线”。你在答辩时能很自信地展示这个验证函数也会让评审老师留下不错的印象。5.2 扩展方向不只是扫掠还有完整 CAD 建模流水线在这份作业的基础框架上可以做的扩展空间其实很大。我在完成扫掠后顺手做了三件小事都在这个工程基础上改的。第一个是绕任意轴旋转生成旋转体用到的是同一个轮廓更新函数只是把路径从直线变成圆弧。第二个是布尔运算的入口——先把两个 Solid 实体用欧拉操作合并成一个再用 KFMRH 删掉相交部分但这一步没做完因为纯粹的欧拉操作处理布尔交非常容易产生非流形边需要额外的分裂操作。第三个是把扫掠路径从直线推广到多段线组合代码上不复杂就是在buildSideFaces之前先按路径段分段处理轮廓。这些扩展有一个共同特征全部沿用在原工程里已经写好的半边结构和欧拉操作不需要重写几何内核。这也是这份资源最值得使用的地方——它提供了一个可靠的拓扑操作基座你只需要在上层添加不同的建模策略就能派生出各种功能。从学以致用的角度来说即使是过了课程设计的阶段这段代码也值得留着。现在每次我做扫掠相关操作不管是不是这个工程都会强制先跑一遍拓扑自检再往下走这个习惯帮我规避过好几轮不知源头在哪的拓扑损坏从代码层面讲它算是这份作业给我的最大长期收获。希望这些调试和排查思路也能帮到你至少让你少走一点我走过的弯路。本文还有配套的精品资源点击获取
简介《三维CAD建模》课程作业定义了半边数据结构并基于该结构实现五个基本欧拉操作以及支持带多个内环的二维区域扫掠操作最终将构建的实体模型进行真实感图形显示完整覆盖了CAD建模的核心流程。压缩包共18个文件以C的cpp/hpp源文件为主辅以配置文件、模型数据、PNG效果图及Markdown说明等整体仅102KB小巧但结构清晰适合直接下载学习。代码均测试运行成功作者表示答辩平均分达96分适合计算机相关专业学生用于课程设计、毕业设计或项目初期演示。已有96人学习浏览下载后可在本地直接编译运行也可在此基础上修改扩展实现更多建模功能。需要远程教学或运行指导可与作者私聊联系。1. 半边数据结构课程作业从拓扑骨架到扫掠成体如果有人问你三维CAD建模里最核心的数据结构是什么答案大概率是半边结构Half-Edge。它把顶点、边、面的拓扑关系组织成一张可以高速遍历的网几乎所有能叫上名字的商业内核都在用它。这份课程作业资源做的正是这件事从零定义半边数据结构实现五个基础欧拉操作再基于欧拉操作完成带多内环的扫掠Sweep建模最后做真实感显示。适合正在做图形学课设、毕业设计或者想弄懂CAD内核拓扑原理的人。难点不在写代码而在理解欧拉操作的先后顺序和拓扑约束——这是整个资源含金量最高的地方。2. 先立骨架半边数据结构的定义与五个基础欧拉操作2.1 半边结构到底在维护什么从实体到拓扑的映射关系把任何一个三维实体想成一堆面片拼起来的封闭外壳每个无向边拆成两条方向相反的有向边这就是半边。每条半边只归属一个面记录它的起点、下一条半边、所属面以及配对半边。这样设计的好处是从任意一条半边出发能沿着面的边界走一圈再通过配对边跳到相邻面整个实体变成一个可遍历的图。这份资源里的main.hpp和CreateSolid.hpp定义了核心数据结构。我在本地复现时看到的是典型的字段组合顶点坐标、半边指针、面指针以及用于建立配对关系的twin指针。还有一个细节值得注意——代码里大量用shared_ptr管理半边和顶点而不是裸指针。这对后续欧拉操作的异常安全很有帮助因为欧拉操作中最容易翻车的就是指针悬挂删除一个面但没同步清理相邻半边的指向遍历时直接崩掉。struct HalfEdge { std::shared_ptrVertex vertex; // 该半边指向的终点顶点 std::shared_ptrHalfEdge twin; // 配对半边方向相反 std::shared_ptrHalfEdge next; // 同面下一条半边 std::shared_ptrFace face; // 所属面 }; struct Solid { std::vectorstd::shared_ptrFace faces; std::vectorstd::shared_ptrHalfEdge edges; std::vectorstd::shared_ptrVertex vertices; };逻辑说明vertex指向的是这条半边在下一条半边遍历时的顶点注意它存的是终点而不是起点——这是很多初学者第一次看会懵的地方。取起点的正确方式是twin-vertex。next指针沿着面边界逆时针走twin跳到相邻面两者组合起来就是完整的拓扑遍历。参数说明如果你的工程不需要跨函数频繁复制拓扑用shared_ptr没问题但如果追求极致性能原始指针加引用计数会更快课程作业场景不需要考虑这个。这套数据结构直接决定了后面五个欧拉操作的实现难度。操作无非是“建”“删”“改”的组合但因为半边结构要求每一步操作完成后拓扑必须自洽所以每一步都要同时维护好vertex、twin、next三套指针。常见做法是把指针更新集中在一处避免散落在各个操作里。2.2 五个欧拉操作逐个拆MVFS、MEV、MEF、KEMR、KFMRH欧拉操作的核心思想很简单每一步操作都不改变实体的欧拉示性数即 V - E F 2 - 2GG 为穿透孔个数。五个基本操作对应的是“从无到有”和“从有到无”的原子步骤。这份资源里的EulerOperation.cpp实现了以下五个MVFSMake Vertex, Face, Solid从空场景创建一个含一个孤立顶点、一张空面、一个新体的初始状态。这是所有建模的第一步。代码实现里要同时 new 三个对象然后用faces、vertices、edges三个向量管理起来。MEVMake Edge, Vertex在已有顶点的基础上加一条边和一个新顶点构成一条新的半边界。扫掠操作的第一步不是直接拉面而是先用 MEV 把二维轮廓的底边骨架搭出来。注意MEV 加边时必须同时创建一对待配对的半边只建一条的话后续遍历就会断链。MEFMake Edge, Face在两个已有顶点之间加一条边同时生成一个新面。这一步是扫掠操作的核心——它把封闭的二维轮廓“缝合”成一张完整的面。实现时有个关键点要判断两个顶点之间是否已有路径连通否则会生成非流形结构。KEMRKill Edge, Make Ring删掉一条边同时在一个面上创建一个内环。这是处理带孔洞二维区域的关键操作。比如你要扫掠一个“回”字形截面内环就是靠 KEMR 建出来的。实现时容易被忽略的是删除边后相邻面的边界指针要重新定向。KFMRHKill Face, Make Ring Hole删掉一张面同时把它变成一个孔洞环。这个操作常用于把实体内部挖穿。作业里如果只做简单扫掠可能不会触发它但完整实现时它是闭环里不可缺少的一环。// MVFS 的核心逻辑创建孤立点与空面 Solid* mvfs(const Point3D p) { Solid* s new Solid(); Vertex* v new Vertex(p); Face* f new Face(); // 初始面没有边next 指针置空 f-halfEdge nullptr; // 把三个对象挂到 Solid 的管理向量里 s-vertices.push_back(v); s-faces.push_back(f); return s; }逻辑说明MVFS 是整个欧拉操作链的入口。注意Face结构里通常会有一个halfEdge字段指向该面边界上任意一条半边作为遍历起点。空面的halfEdge为nullptr后续 MEF 操作会在这里挂上真正的边界边。参数说明Point3D是三维坐标结构体源码里在main.hpp中定义支持x、y、z三个分量。如果你把Face里的halfEdge设计成std::shared_ptr那么nullptr判断和赋值都要注意引用计数变化。五个操作之间有严格的依赖顺序。MVFS 创建骨架MEV 加边加点MEF 闭合面KEMR 和 KFMRH 做挖孔和删面。作业里要求扫掠操作允许二维区域带多个内环所以 KEMR 是必用操作。实现顺序错了会直接导致拓扑自洽性被破坏后面 debug 会非常痛苦。2.3 从代码层面理解欧拉操作为什么要按顺序调用我在翻阅CreateSolid.cpp时发现了一个值得注意的设计它没有把五个欧拉操作封装成独立函数后到处乱调而是全部收敛到一个类里类内部维护一个当前操作的上下文对象。这种设计的好处是每一步操作都从同一个状态出发上一个操作的结果直接成为下一个操作的输入出错时能快速定位是哪一步产生的脏数据。// 典型的操作顺序先建体再逐条建边最后闭合面 Solid* solid euler-mvfs(origin); HalfEdge* e1 euler-mev(solid-vertices[0], p1); HalfEdge* e2 euler-mev(solid-vertices[1], p2); Face* f euler-mef(solid-vertices[0], solid-vertices[2]);逻辑说明这段代码展示了扫掠第一步的拓扑骨架搭建过程——先用 MVFS 创建一个孤立顶点再连续两次 MEV 把轮廓的折线边建出来最后用 MEF 把首尾顶点连起来闭合面。参数说明mev返回的是新建的半边不是顶点也不是面要拿到新顶点需要通过返回的半边去访问。这个细节很多人踩坑直接用返回值当顶点用编译期不报错运行期逻辑全错。五个欧拉操作不是可以任意排列的。MVFS 之后必须 MEVMEV 之后才能 MEF这是拓扑结构决定的面要存在必须先有边边要存在必须先有点。KEMR 必须在面存在之后才能调用因为它是在已有面上挖环。这个依赖顺序就是作业评分里“是否正确理解欧拉操作”的核心判断依据。3. 把平面推成实体扫掠操作的分步实现与多内环处理3.1 扫掠的参数模型轮廓、路径与内环坐标扫掠Sweep的本质是给定一个二维轮廓沿某个方向把它推移一段距离从而生成三维实体。最朴素的扫掠是线性拉伸——轮廓沿法向平移。但这份作业的要求比拉伸复杂一层轮廓内部可以带多个内环也就是截面形状上可以有孔洞。代码里CreateSolid.cpp中定义了扫掠的输入参数核心是两大块轮廓坐标数组和扫掠矢量。轮廓坐标按外环逆时针、内环顺时针的顺序传入这个方向规定不是可选的——它直接决定生成的面的法向朝向。外环逆时针面的法向朝外内环顺时针对应面的法向朝内。如果方向传反了生成出来的实体面法向混乱真实感渲染阶段会出现半边黑半边白的情况。struct SweepProfile { std::vectorstd::vectorPoint2D loops; // loops[0] 是外环其余是内环 Point3D sweepDir; // 扫掠方向长度表示拉伸距离 }; Solid* createSweptSolid(const SweepProfile profile) { Solid* s new Solid(); // 第一步在 z0 平面构造外环和内环的面 Face* bottomFace buildProfileFace(s, profile.loops); // 第二步沿 sweepDir 方向平移轮廓到目标平面 Face* topFace copyFaceTranslated(bottomFace, profile.sweepDir); // 第三步连接上下环的对应顶点生成侧面 buildSideFaces(s, bottomFace, topFace); return s; }逻辑说明这段代码展示了扫掠操作的完整流程三层结构非常清晰。第一步先用欧拉操作在二维平面上构建出带孔洞的底面第二步把整个轮廓沿sweepDir平移一份第三步在底和顶的对应顶点之间搭侧面。参数说明loops是一个二维向量外层是“环”的集合内层是每个环上的点序列sweepDir不要求是单位向量它的模长就是扫掠高度直接决定实体的拉伸长度。3.2 多内环的实现路径不是简单挖空了事多内环的困难不在“挖空”本身而在扫掠生成侧面时内环和外环的侧面处理逻辑完全不同。外环的侧面是一圈“凸”出来的墙内环的侧面是“凹”进去的孔壁。代码里buildSideFaces函数对这个区别做了分支处理遍历轮廓环时区分外环与内环给内环生成的侧面做反向法向修正。void buildSideFaces(Solid* s, Face* bottom, Face* top) { // 遍历底面所有环外环索引 0内环索引 1..n for (size_t i 0; i bottom-loops.size(); i) { bool isInner (i 0); // 沿环的每一条边生成一个四边形侧面 for (HalfEdge* e : bottom-loopEdges[i]) { Face* side createQuadFromEdge(s, e); if (isInner) { reverseFaceNormal(side); // 内环侧面法向要反向 } } } }逻辑说明外环的侧面法向朝外内环的侧面法向必须朝内否则渲染时光照方向是反的模型会呈现“内壁发黑”的效果。reverseFaceNormal在源码里通过交换半边的遍历方向实现不是真的去修改法向量数值。参数说明createQuadFromEdge需要传入底面环上的一条半边它会自动在顶面对应位置找配对顶点生成一个四边形面。这个函数内部会调用 MEF 操作所以这里也验证了欧拉操作是扫掠的“原子积木”。多内环作业里最常见的翻车点不是代码逻辑而是欧拉操作调用顺序。我本地运行时发现如果先建内环的侧面再建外环某些半边指针会丢失正确的next关系导致遍历底面环时少一条边。这个问题的根因是内环和外环共享同一个底面面片的边界环链MEF 操作在环境中插入新边时如果没有正确更新前驱半边的next指针链就会断。3.3 扫掠操作的输入校验作业没写但你应该加的防御代码里其实没有完善的输入合法性校验全靠调用者自觉。我在调试时发现轮廓坐标里有重复点、环没有闭合、内环和外环有交点这三类问题会直接让欧拉操作产生非流形结构——具体表现就是遍历到某条半边时它的next指向了自己。虽然这不是作业要求的必做项但我建议你在调用扫掠函数之前先加一个简单的检查所有环的首尾点必须重合内环必须完全包含于外环内部任意两条环之间不允许有交点。bool validateProfile(SweepProfile profile) { for (auto loop : profile.loops) { if (loop.front() ! loop.back()) return false; // 检查环是否闭合 } // 检查内环是否在外环内取内环任意点做射线法 for (size_t i 1; i profile.loops.size(); i) { Point2D testP profile.loops[i][0]; if (!pointInLoop(testP, profile.loops[0])) return false; } return true; }逻辑说明射线法判断点在多边形内部的算法在很多入门图形学书里都有这里不赘述。关键是你的工程必须在扫掠开始前做这个校验否则欧拉操作的错误很难追踪。参数说明loop.front() ! loop.back()比较的是二维坐标的 x 和 y如果实现Point2D时用了浮点记得加一个很小的容差 eps比如 1e-6而不是直接等号比较——否则手工输入坐标会在闭合检查上误报失败。这部分的经验是欧拉操作本身是低层原语它不管你的输入物理上是否合理只保证“给定合法输入输出合法拓扑”。所以上层的几何合法性校验必须自己做教材里不会讲这个但实际作业踩坑时百分之百会碰到。4. 编译、运行与排查在本地把工程跑起来的完整记录4.1 构建配置与目录结构CMakeLists 的正确打开方式资源里带了CMakeLists.txt和build目录这是直观的加分项。说明代码工程不是单文件堆砌而是能构建成完整可执行程序的组织方式。我在本地跑的时候用的命令是标准的 CMake 三步走mkdir build-local cd build-local cmake .. -DCMAKE_BUILD_TYPEDebug cmake --build . --parallel 4逻辑说明我另建了一个build-local目录而不是直接用资源自带的build目录目的很纯粹不想污染原始文件万一某个配置要反复调整删掉自己的目录重新来就行。参数说明-DCMAKE_BUILD_TYPEDebug会关闭编译优化保留调试符号方便在 GDB 里打断点跟踪半边指针的赋值过程如果只是想看运行效果改成Release模式运行速度更快。--parallel 4是并行编译参数4 是 CPU 物理核数可以根据你的机器配置调整。成功构建后会在build-local目录下生成可执行文件。源码里的main.cpp是程序入口它读取模型文件、调用扫掠函数、启动显示窗口。userInteraction.cpp负责鼠标键盘交互display.cpp负责 OpenGL 渲染。从文件分工就能看出这份作业的完成度不低——它不是一个只有算法的裸代码而是带交互和显示的完整应用。4.2 模型文件格式与四个测试模型的结构资源里附带四个模型文件0.model_8、1.model_C、2.model_A、3.model_D。乍看后缀名很奇怪但打开看内容后就会发现这是一种非常朴素的文本格式。每一行代表一个顶点或一个面顶点用坐标标记面用顶点的索引序列标记首行通常是顶点的总数。8 0.0 0.0 0.0 1.0 0.0 0.0 1.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 1.0 1.0 0.0 1.0 1.0 1.0 1.0 0.0 1.0 1.0 4 0 1 2 3 4 4 5 6 7 ...逻辑说明这段示例对应一个六面体的部分内容第一行的 8 表示有 8 个顶点接着 8 行是顶点坐标再往后每行第一个数表示该面由几个顶点构成后面跟着顶点索引。参数说明模型文件之所以有两套数字和扫掠操作直接相关——它记录的是扫掠前生成的“二维区域”的轮廓描述CreateSolid.cpp读取后先构建面片再沿路径扫掠成体。三个模型文件分别对应不同的截面形状来源有的外环带一个内环有的带两个有的内环形状是不规则的。你可以逐个加载起来看代码对不同拓扑的处理差异。这四个文件的编号也有意思是作者从生成程序里直接输出的测试用例顺序就是开发过程中从简单到复杂的调试顺序。4.3 交互与显示模块的使用边界哪些能改哪些别动display.cpp和userInteraction.cpp是容易被忽略但很重要的两个文件。前者处理 OpenGL 渲染后者处理鼠标键盘事件。代码本身不复杂——渲染部分基本是标准的固定管线顶点绘制交互部分是围绕相机旋转展开的。我在复现时注意到一个典型问题如果 GPU 驱动不支持某个旧版 OpenGL 特性显示窗口会直接黑屏。这不是代码逻辑问题而是环境兼容问题。// display.cpp 中的典型渲染循环结构 void renderScene() { glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); glLoadIdentity(); setupCamera(); // 根据鼠标输入设置视角 drawSolidFaces(); // 遍历半边结构画所有面片 glutSwapBuffers(); }逻辑说明setupCamera依赖userInteraction.cpp里的全局相机状态变量鼠标拖动时修改这个变量的值渲染循环每次执行时读取最新值并更新视角。drawSolidFaces是顶点和法向量的核心绘制函数它要遍历Solid对象中的所有面通过半边结构的next链把每个面的所有顶点索引收集起来再交给 OpenGL。参数说明GL_DEPTH_BUFFER_BIT必须保留否则面片的前后遮挡关系会错乱转视角时后面的面会穿到前面来。如果你看到模型半透明或“透视”了首要检查就是清除标志里是否少了深度位。这个模块在作业里承载“真实感图形显示”的功能因此在评分标准里是加分项。但你要清楚它的定位它只是辅助验证工具不要花太多时间优化渲染效率除非你想进一步做真实感增强比如加光照模型那是可选的扩展方向。4.4 避坑自查清单拓扑遍历、内环方向与渲染黑屏这一部分直接照着我踩过的坑逐条检查比盲调查有效率得多。现象一扫掠出来的实体在显示窗口里“缺一块”面或者某个面在特定视角下消失。原因半边结构的next指针链断裂遍历面边界时漏掉了一条边。解决在drawSolidFaces函数里加一条断言——每个面的半边遍历步数必须等于该面的顶点数量如果不等打印出面的索引和遍历步数定位到具体是哪一步 MEF 操作破坏了链。现象二内环方向传反实体内部的结构完全错乱。原因外环逆时针、内环顺时针是约定俗成的方向规则但代码里没有自动归一化直接信任调用者的输入。解决在buildProfileFace的入口处加一个多边形方向判定函数鞋带公式自动把外环逆时针化、内环顺时针化再传给欧拉操作。现象三OpenGL 窗口黑屏但没有任何报错。原因可能是系统默认 OpenGL 版本过低或者代码里用了GLUT的旧接口在 Wayland 环境下会话兼容有问题。解决启动程序时在命令行加export LIBGL_ALWAYS_SOFTWARE1仅限 Linux强制走软件渲染验证逻辑是否正确如果软件渲染能显示而硬件渲染不行就是驱动配置问题和工程项目无关。现象四CMake 配置时提示找不到某个依赖库。原因资源里的 CMakeLists 大概率假设你已经安装过基本的图形库开发包。解决Ubuntu/Debian 系执行sudo apt install freeglut3-dev补依赖RedHat 系用sudo yum install freeglut-devel装完重新跑一遍 CMake 配置命令即可。现象五读入模型文件后程序直接崩溃没有任何提示。原因绝大多数情况是顶点索引越界模型文件里某个面引用了不存在的顶点编号。解决在CreateSolid.cpp的文件读取函数里把每个面的索引值在读入后就立刻做上下界检查越界就打印错误信息并跳过该面而不是直接把半开放的数据传给欧拉操作。这一步不是作业要求但能省掉大量 debug 时间。5. 进阶验证拓扑合法性自检与 Beyond 作业的扩展玩法5.1 用欧拉公式自动验证操作结果作业评分能看到“运行成功”但看不到你的拓扑是否自洽。给自己加一道保险在每次扫掠操作完成后遍历当前Solid的顶点、半边、面计算 V - E F并比对公式预期值。对无洞实体欧拉示性数是 2带一个洞是 0带两个洞是 -2。你可以设计一个自动断言在控制台输出校验结果这比肉眼判断靠谱得多。void validateSolid(Solid* s) { int V s-vertices.size(); int E s-edges.size() / 2; // 边数 半边数 / 2 int F s-faces.size(); int chi V - E F; // 对扫掠生成的实体G 内环数chi 2 - 2G int expected 2 - 2 * (int)(/* 得到当前实体的内环数 */); printf(欧拉示性数: %d (预期 %d)\n, chi, expected); if (chi ! expected) printf(警告: 拓扑可能不自洽!\n); }逻辑说明代码里的expected计算高度依赖你正确统计内环数量典型情况是一个内环对应一个穿透孔所以 G 的值等于内环总数。如果你在扫掠过程中 KEMR 被多次调用可以维护一个计数器记录调用次数。参数说明边的数量之所以要除以 2是因为半边结构里每条无向边对应两条有向半边edges容器里存的是半边数量。运行此函数后如果实数与预期值不匹配说明之前某个欧拉操作执行有误。这其实不是作业要求但我在多个类似工程里都用这个做“拓扑连接性和正确性的最终防线”。你在答辩时能很自信地展示这个验证函数也会让评审老师留下不错的印象。5.2 扩展方向不只是扫掠还有完整 CAD 建模流水线在这份作业的基础框架上可以做的扩展空间其实很大。我在完成扫掠后顺手做了三件小事都在这个工程基础上改的。第一个是绕任意轴旋转生成旋转体用到的是同一个轮廓更新函数只是把路径从直线变成圆弧。第二个是布尔运算的入口——先把两个 Solid 实体用欧拉操作合并成一个再用 KFMRH 删掉相交部分但这一步没做完因为纯粹的欧拉操作处理布尔交非常容易产生非流形边需要额外的分裂操作。第三个是把扫掠路径从直线推广到多段线组合代码上不复杂就是在buildSideFaces之前先按路径段分段处理轮廓。这些扩展有一个共同特征全部沿用在原工程里已经写好的半边结构和欧拉操作不需要重写几何内核。这也是这份资源最值得使用的地方——它提供了一个可靠的拓扑操作基座你只需要在上层添加不同的建模策略就能派生出各种功能。从学以致用的角度来说即使是过了课程设计的阶段这段代码也值得留着。现在每次我做扫掠相关操作不管是不是这个工程都会强制先跑一遍拓扑自检再往下走这个习惯帮我规避过好几轮不知源头在哪的拓扑损坏从代码层面讲它算是这份作业给我的最大长期收获。希望这些调试和排查思路也能帮到你至少让你少走一点我走过的弯路。本文还有配套的精品资源点击获取
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
