计算机图形学 12：三角网格怎样保存邻接
两个三角形组成一个方形，渲染时只需依次提交顶点。若要把方形对角线换成另一条，就必须知道这条边属于哪两个面、两侧相对的顶点是谁，以及修改后每个顶点周围是否仍连成一片。图像数组和三角形列表本身没有直接回答这些问题。
本篇在累计光栅器前增加网格邻接结构。一个方形用于检查边界与翻边，一个四面体用于检查闭合一环，非法输入用于验证拒绝路径。图像展示连接变化，连接表与数值不变量负责验收。
索引相同才表示同一个顶点
索引网格保存一份位置数组和一份三角形索引数组。方形四点为：
两个面分别为(0,1,2)、(0,2,3)。共有四个顶点、五条无向边、两个面。边(0,2)属于两面，其余四条边各属于一面。
邻接按索引识别，而不是比较坐标是否近似相等。两个不同索引可以保存完全相同的位置，但仍表示两个拓扑顶点。导入时是否焊接重合点需要独立规则，不能在建立邻接时悄悄用任意容差合并，否则薄缝、硬边属性和不相连表面可能被错误连接。
本实现仅接收有限、绝对值不超过一百万的坐标，拒绝越界索引、同面重复顶点、重复三角形和零面积面。面积检查使用第01篇叉积，检查其平方长度是否为零；它不是精确几何谓词，没有保证近退化三角形在任意尺度下都稳定。
一条边为什么需要两个方向
每个三角形产生三条有向半边。面(a,b,c)对应a→b、b→c、c→a。半边记录起点origin、同面下一条next、反向半边twin与面编号face。终点可由下一条半边的起点取得，无需重复存储。
在方形中，第一面的2→0和第二面的0→2互为twin。对内部边，这要求两个相邻面沿公共边的绕行方向相反。若两个面都沿0→1使用同一条边，当前构造器拒绝输入，提示绕序不一致或非流形边，而不替调用者猜测该翻转哪一个面。
构造时用有向顶点对作为映射键。第一次遍历建立全部半边，重复键立即失败；第二次查找反向键并连接twin。这样也能拒绝三面共用同一无向边：三个方向中至少两个相同，必然出现重复有向键。
边界边没有反向半边，本实现将twin设为−1。Berkeley课程的示例采用虚拟边界面，使边界也有完整的反向环；两种约定都能实现，但遍历不能混用。这里不创建虚拟面，所以一个有边界的网格总半边数仍为3F。
设边界无向边数为B，内部边各贡献两条半边，边界边只贡献一条，因此：
方形F=2、B=4，得到E=5。不能直接用3F/2计算带边界网格的边数。
内部顶点的一环怎样走
固定顶点v，从一条起点为v的半边h出发。h到达邻点w；转到twin后变成w→v，再执行next，得到同一顶点v出发的下一条半边。重复twin.next便绕v访问邻点。
对闭合单扇区，遍历应回到起始半边，每条出边恰好访问一次。四面体的顶点0有三个邻点，实际遍历得到三个不同邻点；网格V=4、E=6、F=4、B=0。
实现保存已访问半边编号，若在回到起点前重复进入其他半边就报错；结束后还比较访问数与该顶点全部出边数。后一项很重要：绕完一个小环并不证明顶点附近只有这一个环。两个闭合外壳若只共用一个顶点索引，局部可能有两个不连通的扇区。
当前为每个顶点扫描半边表寻找出边，优先保持检查可读，未保存每个顶点的入口指针。因此批量构造的一环验证不是线性总复杂度。后续需要处理大网格时，可以保留出边入口和关联计数，但不能删除单扇区验收。
边界一环不是闭合环
边界顶点的一环是一条开放链。若任意挑一条出边，不停执行twin.next，可能在中途遇到−1，还漏掉另一侧邻点。当前先找所在三角形前一条半边没有twin的出边，以此作为链起点。
对三角形，前一条半边等于next.next。它从边界邻点进入v；先记录这条入边的起点，再从选定出边开始访问终点。遇到没有twin的出边时停止，这时到达另一端边界邻点。
方形顶点0的入边界是3→0，选定出边0→2；因此邻点顺序为3、2、1。这个顺序由当前面绕序和遍历方向决定，不是按顶点编号排序。翻边之后，顶点0不再连接顶点2，一环应变为3、1。
若一个顶点出现两个这样的边界起点，说明它附近存在多个开放扇区，当前直接拒绝。即使每条边至多属于两个面，也仍可能有这种问题。例如两个三角形(0,1,2)和(0,3,4)只共用顶点0，各边都只有一面，但顶点0周围不是单一圆盘或半圆盘。它是本次明确拒绝的bow-tie输入。
无面引用的孤立顶点也拒绝。这个选择让每个被接收顶点都有非空一环，不表示所有网格库都必须禁止孤立点。不同连通分量可以共存，只要各顶点局部仍满足约定。
翻对角线需要更换哪两个面
设内部半边为a→b，两侧有序面为(a,b,c)与(b,a,d)。翻边删除对角线(a,b)，新增(c,d)，两个新面可写为：
本次调用flip(0,2)，相对顶点为3和1。得到同一个方形的另一条对角线(1,3)。顶点位置完全不变，面数量也不变，但邻接和面覆盖范围改变。
两图来自实际DepthImage渲染，原始256×256，面编号对应橙色和蓝色，沿用正交投影与线性颜色后sRGB编码。外轮廓保持方形，颜色分界改向。它们没有画人工覆盖的对角线，分界就是实际三角形覆盖结果。
教学实现先复制面索引，替换这两个面，完整构造候选网格，再验证新面与原面法线点积为正，最后才替换原对象。候选构造失败或方向检查失败时，原网格保持不变。这里的“局部操作”描述改了哪部分拓扑，不表示实现达到了常数时间；重建会扫描整个网格，也会重新编号半边，外部不能保留旧半边编号继续使用。
这个实现没有检测远处三角形的全局自相交。法线点积检查也只是拒绝翻转超过90°或退化的局部候选，不是任意曲面翻边的完整质量标准。本篇验收限定于平面凸方形和明确列出的非法操作。
计数相同不足以证明连接正确
方形翻边前后都有V=4、E=5、F=2、B=4，欧拉示性数V−E+F=1。一环从3、2、1变成3、1，验证对角线确实改变。若程序什么也没做，计数照样通过，因此这两类检查不能互相代替。
每条内部半边还要满足twin.twin返回自身，两个方向的起终点互换；每个面沿next走三步返回原半边。构造器和翻边候选都执行这些连接检查，并要求每个顶点全部出边由同一个开放链或闭合环覆盖。
这些连接检查依赖构造器已建立合法索引，不是对任意损坏内存的安全解析器。教学类公开了数组便于观察，调用者不应直接改写halfedges后再期待validate_links修复或安全诊断所有破坏。
四面体的V−E+F=2与其闭合拓扑一致，但欧拉示性数只是统计量，不是流形性的充分条件。局部连接有误时，某些顶点、边和面的数量仍可能碰巧抵消。不能用一个全局数字取代一环检查。
十个拒绝样本分别覆盖越界索引、同面重复顶点、同向公共边、重复面、三面共边、bow-tie、零面积、NaN坐标，以及边界翻边和四面体翻边。四面体中尝试新增的对角线已经存在，候选会产生重复面，必须拒绝。两个失败翻边都逐项比较原面索引，确认失败没有留下半更新状态。
复跑与练习
1 | |
累计检查复跑00–11，本篇原始日志在writing-plans/computer-graphics/evidence/12-cpu.txt。输出mesh-before.ppm、mesh-after.ppm，PNG由真实结果转换。没有随机过程、性能计时或GPU执行。新增代码为mesh.hpp与mesh_check.cpp，后续细分和简化将复用这份索引网格及其拓扑约束。
练习一：一个单三角形有多少半边、无向边与边界边？在当前约定下，从任意半边开始无条件执行twin.next会发生什么？
答案：三条半边、三条无向边、三条边界边。所有twin都是−1，第一步就不能继续索引。应按开放一环处理，或整体改用配套的虚拟边界半边结构，不能只把−1随意换成自身。
练习二：两个三角形只共用一个顶点时，每条边都至多有两个邻面，为什么仍拒绝？仅检查V−E+F能否替代这个拒绝条件？
答案：共享顶点的邻域分成两个扇区，一环不能覆盖为单一链或环，因此不符合当前流形约定。欧拉示性数没有记录邻接的具体连接方式，相同统计量可能来自不同局部结构，必须遍历并检查连通扇区。
系列导航与资料
前篇：11：沿管线定位一张错误图像。系列入口。下一篇：13：少量控制点怎样生成曲线。
Berkeley CS184：A Primer on the HalfEdgeMesh class，Getting Started、Mesh Boundary、Possible Pitfalls与Debugging Aid，核对起点半边、顶点扇区、边界表示和操作后引用有效性。2026-09-20再次读取，来源记录见evidence/research-12-16.md。本篇选择空twin边界和候选重建，未复制课程的虚拟边界面与指针更新实现。
