第05章 半边数据结构摘要半边数据结构Half-Edge Data StructureHE是边界表示法中流形表面拓扑表示的事实标准。其核心思想是将每条无向边拆分为两个方向相反的有向半边并通过对向、后继、所属面等指针把邻接查询转化为常数时间操作。本文从图论、曲面拓扑与实体造型理论出发系统阐述半边结构的形式化定义、不变量体系、邻接查询复杂度、欧拉操作对应、变体比较与工程实现。在此基础上提出半边六元组模型、不变量验证清单、邻接查询复杂度定理、广义半边模型、欧拉操作—半边操作对应表、半边结构的信息论下界与并行遍历依赖图等分析工具并以 OpenCASCADE、CGAL、ACIS 等主流实现为对照给出可操作的工程指南。关键词半边数据结构B-Rep拓扑邻接欧拉操作流形表面辐射边OpenCASCADECGAL文章目录第05章 半边数据结构学习目标5.1 引言拓扑邻接查询为何成为核心问题5.2 历史演进与学术脉络5.2.1 翼边结构开创与复杂5.2.2 半边结构拆分与简化5.2.3 辐射边与 DCEL非流形与平面细分5.2.4 现代内核实现5.3 形式化定义与核心概念5.3.1 半边六元组模型5.3.2 核心概念5.3.3 不变量验证清单5.3.4 流形假设与局限5.4 技术原理邻接查询的常数化5.4.1 邻接查询复杂度定理5.4.2 方向一致性5.4.3 顶点星形遍历5.4.4 面环遍历与孔处理5.5 数学基础5.5.1 图的边定向5.5.2 曲面可定向性5.5.3 欧拉操作与半边不变量5.5.4 绕数与点在面内5.5.5 信息论下界与存储复杂度5.6 数据结构与算法5.6.1 类定义5.6.2 创建立方体的半边结构5.6.3 遍历面所有边5.6.4 遍历顶点星形5.6.5 分裂面MEF5.6.6 合并面KEF5.6.7 半边结构操作复杂度5.7 变体比较翼边、半边、辐射边与 DCEL5.7.1 广义半边模型5.8 主流内核中的实现5.8.1 OpenCASCADE5.8.2 CGAL5.8.3 ACIS5.8.4 Parasolid、CGM 与 Granite5.9 操作步骤教程在 FreeCAD 与 CGAL 中观察半边步骤一遍历面边步骤二找共享边的两面步骤三遍历顶点星形步骤四用 CGAL 体验显式半边步骤五验证方向一致性5.10 应用场景与案例5.10.1 布尔运算找共享边5.10.2 缝合5.10.3 渲染画边5.10.4 网格划分5.10.5 法向计算5.10.6 拓扑验证5.10.7 特征识别5.10.8 拓扑命名5.11 常见问题与调优问题一非流形边导致半边失效问题二方向不一致问题三next/prev 指针断问题四孔环方向错问题五遍历性能差问题六共享边判错问题七内存占用高5.12 发展趋势与展望5.12.1 非流形扩展5.12.2 并行遍历5.12.3 内存紧凑5.12.4 动态更新5.12.5 与图数据库结合5.12.6 AI 与拓扑5.13 小结5.14 练习题参考答案要点5.15 参考文献与延伸阅读学习目标理解半边数据结构的基本动机以预存邻接指针把 B-Rep 邻接查询降为 (O(1)) 或 (O(\text{局部规模}))。掌握半边结构的六元组形式化定义与七条核心不变量能够手工验证一个简单多面体的半边结构合法性。掌握边—面、面—边、顶点—星形、边—端点等典型邻接查询的半边实现及其复杂度。掌握半边结构与欧拉操作MVFS、MEV、MEF、KEV、KEF、KFMRGH的对应关系能够用半边指针更新实现面分裂与面合并。理解半边结构的流形假设及其局限掌握辐射边结构与广义半边模型对非流形的扩展思路。能够在 OpenCASCADE、CGAL 或自研代码中实现半边结构的创建、遍历、修改与验证。5.1 引言拓扑邻接查询为何成为核心问题在 B-Rep 几何内核中几何计算与拓扑查询密不可分。布尔运算需要找共享边、缝合需要配对缝隙边、渲染需要遍历面边、网格划分需要沿边布点、法向计算需要知道面的环走向、特征识别需要匹配拓扑模式。这些操作的共同底层问题是给定一个拓扑实体如何快速找到与它相邻的拓扑实体若内核只存储“边表”和“面表”回答“这条边两侧是哪两个面”只能遍历所有面复杂度为 (O(F))回答“这个面由哪些边围成”需要遍历所有边复杂度为 (O(E))。对几千个面的零件这种查询会迅速成为性能瓶颈。半边数据结构通过预存邻接指针解决这一问题。其基本思想可概括为把每条无向边拆成两个有向半边每个半边只记录自己一侧的信息半边在面内按环顺序链接。由此一条边的两侧面、一条边的两个端点、一个面的边序列、一个顶点的邻接面都可以在常数或局部时间内获得。半边结构由 Kevin Weiler 在 1986 年系统化其思想可追溯到 Baumgart 1975 年的翼边结构。今天它已成为 OpenCASCADE、CGAL、大量网格处理库与教学用几何内核的拓扑基础。本章的组织如下5.2 回顾历史5.3 给出形式化定义与不变量5.4 分析技术原理与复杂度5.5 讨论数学基础5.6 给出数据结构与算法5.7 比较半边、翼边、辐射边、DCEL 与 OpenCASCADE 实现5.8 分析主流内核实现5.9 提供操作教程5.10 讨论应用5.11 总结常见问题5.12 展望趋势5.13 小结5.14 练习题5.15 参考文献。5.2 历史演进与学术脉络半边结构的演进是拓扑数据结构不断简化的历史。5.2.1 翼边结构开创与复杂1975 年MIT 的 Bruce Baumgart 在其博士论文中提出翼边结构Winged-EdgeWE。翼边结构是第一个系统化的多面体拓扑数据结构。每条边记录四个邻面邻边两端点处顺时针与逆时针的下一条边以及两侧的两个面。翼边结构查询灵活但更新复杂插入或删除一条边需要更新多个邻边的多个指针容易出错。翼边结构是开创性的但其复杂度促使后续研究寻求更简洁的表示。5.2.2 半边结构拆分与简化1986 年Kevin Weiler 在《Topology as a Framework for Computational Geometry》中提出半边结构。其核心洞察是与其在一条边上同时存储两侧信息不如把边拆成两个有向半边每个半边只存储自己一侧的信息。每个半边记录起始顶点对向半边环内下一条半边环内上一条半边所属面。更新时只需修改局部几个指针远比翼边简单。半边结构迅速成为流形表面拓扑表示的主流。5.2.3 辐射边与 DCEL非流形与平面细分同一时期Weiler 还提出辐射边结构Radial EdgeRADIAL以支持非流形每条边可关联任意多个面用“边使用edge use”层次组织。ACIS 采纳辐射边作为基础。在计算几何领域双向连通边表DCELDoubly Connected Edge List是半边结构在平面细分中的变体用于平面图、Voronoi 图与多边形剖分。DCEL 与半边本质相同命名差异源于不同社区。5.2.4 现代内核实现OpenCASCADE 的TopoDS_*体系采用类似半边的思想每条边在环中通过TopoDS_Edge加方向引用面的环通过边序列表达。OCCT 不直接称“半边”但拓扑遍历机制一致。CGAL 的Polyhedron_3显式使用半边结构HalfedgeDS概念是教学与研究的经典实现。ACIS 使用COEDGE有向边类似半边加辐射边层。至今半边结构仍是流形表面拓扑表示的事实标准翼边已基本淘汰辐射边用于非流形场景DCEL 在计算几何中保持生命力。5.3 形式化定义与核心概念5.3.1 半边六元组模型为统一描述不同实现本文提出半边结构的六元组模型[\mathcal{H} \langle V, HE, F, O, M, N, \Phi \rangle]其中(V)顶点集合(HE)半边集合(F)面集合(O: HE \to V)起点映射(O(h)) 为半边 (h) 的起始顶点(M: HE \to HE)对向映射(M(h)) 为 (h) 的对向半边(N: HE \to HE)后继映射(N(h)) 为同一环内 (h) 的下一条半边(\Phi: HE \to F \cup {\bot})所属面映射(\Phi(h)\bot) 表示边界半边。前驱映射可定义为 (N^{-1})在环内局部存在。5.3.2 核心概念半边。一条无向边被拆成两个有向半边方向相反互为对向。半边是半边结构的基本单元。对向关系。一条边的两个半边互为 mate[M(M(h)) h, \quad M(h) \neq h]环。面上首尾相接的半边循环。后继映射 (N) 在环内链接[N^k(h) h]对某个正整数 (k) 成立(k) 为该环的半边数。面。关联一个外环与零个或多个内环以及曲面几何支撑。外环定义面主体边界内环定义孔。顶点。关联一个三维坐标。从顶点出发的所有半边可通过“对向后继”链遍历形成顶点星形。边连续条件。对任意半边 (h)有[O(M(h)) O(N(h))]即对向半边的起点等于后继半边的起点。这一条件保证半边沿环连续。5.3.3 不变量验证清单本文提出半边结构七条核心不变量编号不变量含义I1(M(M(h))h)对向关系自反I2(M(h) \neq h)半边不与自身对向I3(O(M(h))O(N(h)))边连续条件I4(N) 在每个环上形成有限循环环闭合I5每条边恰好两个半边流形假设I6外环逆时针内环顺时针方向一致性I7(\Phi(h)) 与 (\Phi(M(h))) 为共享该边的两个面面—边关联正确其中 I5 是流形假设非流形结构需扩展。I6 是可定向曲面一致定向的体现。5.3.4 流形假设与局限半边结构默认每条边恰好被两个面共享即[|{h \in HE \mid \text{边}(h)e}| 2]这对应二维流形表面。若三个或更多面沿同一条边汇合非流形半边结构无法直接表示。典型非流形场景包括多面沿一边汇合嵌入式界面多材质边界仿真一体化中的非流形网格。非流形扩展方案包括辐射边结构、广义半边模型与分体表示。5.4 技术原理邻接查询的常数化半边结构的高效性来自预存邻接指针使典型查询在常数或局部时间内完成。5.4.1 邻接查询复杂度定理本文提出如下复杂度定理。定理 5.1半边邻接查询复杂度在合法半边结构中查询一条边的两个端点(O(1))查询一条边的两侧面(O(1))查询一个面的所有边(O(k))(k) 为该面环的半边数查询一个顶点的所有邻接面(O(d(v)))(d(v)) 为顶点度数查询两个面是否共享边(O(\min(k_1,k_2)))全局遍历所有半边(O(E))全局遍历所有面(O(F))。证明思路边端点由 (O(h)) 与 (O(M(h))) 直接得到边两侧面由 (\Phi(h)) 与 (\Phi(M(h))) 直接得到面环通过 (N) 链遍历环长 (k)顶点星形通过 (h \leftarrow M(h).N) 遍历度数 (d(v))遍历较小面的环查对向面半边总数为 (2E)线性遍历面表线性遍历。该定理说明半边结构把 B-Rep 最频繁的邻接查询从 (O(E \times F)) 降为 (O(1)) 或局部线性是内核性能的基础保障。5.4.2 方向一致性半边结构要求外环逆时针、内环顺时针从面法向观察。这使面法向可由环走向用右手法则确定。定理 5.2方向一致性对可定向流形表面存在全局一致的法向场使得每个面的外环在法向观察下为逆时针内环为顺时针。证明思路可定向曲面存在全局一致的定向半边结构通过 mate 关系保证相邻面在共享边处方向相反因此可逐面传播法向保持一致性。不可定向曲面如莫比乌斯带无法一致定向半边结构不直接支持。5.4.3 顶点星形遍历从顶点 (v) 的任一出半边 (h)(O(h)v)出发绕顶点一周的遍历为[h \leftarrow M(h).N]重复直到回到起始半边。其正确性来自边连续条件[O(M(h).N) O(h) v]顶点星形遍历用于计算顶点法向邻面法向平均判断顶点是否为边界点特征识别中的角点检测网格划分中的顶点邻域查询。5.4.4 面环遍历与孔处理面由外环与若干内环组成。遍历面边界需分别遍历外环与所有内环。点在面内判定可化为参数域绕数[\text{inside}(p,F) \iff \text{winding}(p,\text{outer}) \neq 0 \land \forall \text{inner}_i,\ \text{winding}(p,\text{inner}_i)0]半边结构的环遍历支持高效绕数计算。5.5 数学基础半边结构本身是数据结构但其设计基于图论、曲面拓扑与代数拓扑。5.5.1 图的边定向无向图 (G(V,E)) 可通过把每条无向边替换为两条有向边得到有向图。半边结构正是这一技巧的拓扑实现每条无向边 (e) 对应两个半边 (h) 与 (M(h))方向相反。环是这些有向半边的循环序列。后继映射 (N) 定义环上的置换。5.5.2 曲面可定向性可定向曲面可一致选择法向。半边结构中外环逆时针、内环顺时针即一致定向的体现。可定向性条件可用欧拉公式与边界算子表达。对闭合可定向曲面[V - E F 2 - 2G]其中 (G) 为亏格。半边结构中 (E) 为边数半边数的一半(F) 为面数(V) 为顶点数。5.5.3 欧拉操作与半边不变量欧拉操作保持欧拉–庞加莱公式不变。半边结构的不变量(M(M(h))h)、(N) 成环、边连续等正是欧拉操作合法性的数据结构保证。本文提出欧拉操作–半边操作对应表欧拉操作含义半边实现要点拓扑变化MVFS创建孤立顶点、面、壳创建面环与顶点(V1, F1, S1)MEV加边与顶点在顶点处加半边与顶点(V1, E1)MEF加边分裂面在面内两顶点间加半边拆环(E1, F1)KEV删边与顶点删半边与顶点(V-1, E-1)KEF删边合并面删半边合并两环(E-1, F-1)KFMRGH删面、加环、加亏格删面调整环与亏格(F-1, L1, G1)5.5.4 绕数与点在面内点 (p) 在面 (F) 内的判定可化为参数域上 (p) 对各环的绕数[\text{inside}(p,F) \iff \text{winding}(p,\text{outer}) \neq 0 \land \forall \text{inner}_i,\ \text{winding}(p,\text{inner}_i)0]绕数可用射线计数或角度和计算。半边结构的环遍历支持高效绕数计算。5.5.5 信息论下界与存储复杂度命题 5.1存储下界对流形半边结构半边数为 (2E)。每个半边至少需存储对向、后继、起点与所属面四类信息。若用指针实现每半边至少 4 个指针若用索引实现每半边至少 4 个整数索引。因此半边结构的存储复杂度为[S_{\text{HE}} \Theta(E)]与边数线性。相比翼边结构每边存储更多邻接指针半边结构在流形场景下更紧凑。5.6 数据结构与算法5.6.1 类定义classHalfEdge:origin:Vertex# 起始顶点mate:HalfEdge# 对向半边next:HalfEdge# 环内下一半边prev:HalfEdge# 环内上一半边face:Face# 所属面None 表示边界classVertex:point:Point3D# 坐标halfEdge:HalfEdge# 任一出发半边用于遍历星形classFace:outerLoop:HalfEdge# 外环任一半边innerLoops:list[HalfEdge]# 内环surface:Surface# 几何支撑normal:Vector3D# 法向5.6.2 创建立方体的半边结构defbuild_box_halfedge(width,height,depth):# 1. 创建 8 个顶点verts[Vertex((x,y,z))forxin[0,width]foryin[0,height]forzin[0,depth]]# 2. 创建 12 条边每条边两个半边half_edges{}for(i,j)inedge_pairs:he1HalfEdge(originverts[i])he2HalfEdge(originverts[j])he1.matehe2 he2.matehe1 half_edges[(i,j)]he1 half_edges[(j,i)]he2# 3. 创建 6 个面每面建环forface_definface_defs:he_list[half_edges[(v[k],v[k1])]forkinrange(4)]forkinrange(4):he_list[k].nexthe_list[(k1)%4]he_list[k].prevhe_list[(k-1)%4]he_list[k].faceface face.outerLoophe_list[0]# 4. 验证不变量assertall(he.mate.mateheforheinall_half_edges)assertall(he.mate.next.originhe.originforheinall_half_edges)returnstructure5.6.3 遍历面所有边defiterate_face_edges(face):heface.outerLoop starthewhileTrue:yieldhe hehe.nextifhestart:break5.6.4 遍历顶点星形defiterate_vertex_star(vertex):hevertex.halfEdge starthewhileTrue:yieldhe.face hehe.mate.nextifhestart:break5.6.5 分裂面MEFdefsplit_face(face,v1,v2):# 在面内 v1、v2 间加边把面分裂为两个he_newHalfEdge(originv1)he_new_mateHalfEdge(originv2)he_new.matehe_new_mate he_new_mate.matehe_new# 找原环中 v1、v2 处的半边he1find_halfedge_at(face,v1)he2find_halfedge_at(face,v2)# 更新 next/prev把原环拆为两环he_new.nexthe2 he_new.prevhe1.prev he_new_mate.nexthe1 he_new_mate.prevhe2.prev he1.prev.nexthe_new he1.prevhe_new_mate he2.prev.nexthe_new_mate he2.prevhe_new# 创建新面关联一环原面关联另一环new_faceFace(outerLoophe_new_mate)he_new.faceface he_new_mate.facenew_facereturnnew_face5.6.6 合并面KEF合并面是分裂面的逆操作删除一条边及其两个半边把两侧环合并为一个环。实现时需正确更新next、prev与face指针并保证不变量。5.6.7 半边结构操作复杂度操作复杂度说明查询边端点(O(1))直接读取查询边两侧面(O(1))直接读取遍历面环(O(k))(k) 为环长遍历顶点星形(O(d(v)))(d(v)) 为顶点度数分裂面(O(1))局部指针更新合并面(O(1))局部指针更新加顶点(O(1))边拆分全局验证(O(EF))遍历所有实体5.7 变体比较翼边、半边、辐射边与 DCEL结构提出者/代表基本单元邻接查询非流形更新复杂度典型应用翼边Baumgart 1975边灵活弱高早期多面体半边Weiler 1986有向半边(O(1))不支持低CGAL、教学辐射边Weiler/ACIS边使用强强中ACIS、仿真DCEL计算几何有向边(O(1))平面细分低Voronoi、平面图OCCT TopoDSOpenCASCADE边方向良部分中FreeCAD、Salome5.7.1 广义半边模型为统一流形与非流形本文提出广义半边模型[\mathcal{GHE} \langle V, HE, F, O, M, N, \Phi, R \rangle]其中 (R) 为辐射关系允许一条边关联 (k \ge 2) 个半边。当 (k2) 时退化为经典半边结构当 (k2) 时支持非流形。辐射关系 (R) 把同一边的多个半边组织为循环便于沿边遍历所有相邻面。该模型可作为理解半边与辐射边统一框架的工具。5.8 主流内核中的实现5.8.1 OpenCASCADEOCCT 的TopoDS_*体系采用类似半边的思想。TopoDS_Edge在TopoDS_Wire中通过Orientation正向/反向引用等价于选择半边。遍历面环用BRepTools_WireExplorer。OCCT 的TShape共享机制使同一条边在多环中复用类似半边的 mate。OCCT 不显式存next/prev环通过边序列表达遍历靠序列顺序。这比纯半边略低效但更灵活支持非流形与共享。5.8.2 CGALCGAL 的Polyhedron_3显式使用半边结构HalfedgeDS概念是教学经典。CGAL 半边有next、prev、mate、vertex、face指针API 清晰。CGAL 严格流形不支持非流形。5.8.3 ACISACIS 使用COEDGE有向边类似半边加RAIAL辐射边。COEDGE有next、prev、mate辐射边层支持多面沿一边。这是半边向非流形的扩展。5.8.4 Parasolid、CGM 与 GraniteParasolid、CGM 与 Granite 不公开内部数据结构但都基于类似半边的有向边遍历机制。Parasolid 的状态机在半边基础上增加状态管理。CGM 的容差拓扑在边结构中引入容差边与容差顶点。Granite 把特征历史嵌入拓扑结构。5.9 操作步骤教程在 FreeCAD 与 CGAL 中观察半边步骤一遍历面边importPart boxPart.makeBox(10,10,10)facebox.Faces[0]wireface.OuterWireforedgeinwire.Edges:print(edge.Vertexes[0].Point,edge.Vertexes[1].Point)这遍历一个面的所有边等价于半边环遍历。步骤二找共享边的两面edgebox.Edges[0]faces_with_edge[fforfinbox.Facesifedge.isIn(f.OuterWire)]print(len(faces_with_edge))# 流形应为 2这等价于he.face与he.mate.face查询。步骤三遍历顶点星形vbox.Vertexes[0]adj_faces[fforfinbox.Facesifany(v.isSame(vx)forvxinf.Vertexes)]print(len(adj_faces))# 立方体角点应有 3 面相邻这等价于顶点星形遍历。步骤四用 CGAL 体验显式半边#includeCGAL/Polyhedron_3.hPolyhedron P;for(autoheP.halfedges_begin();he!P.halfedges_end();he){autovhe-vertex();autofhe-facet();automatehe-opposite();autonexthe-next();}这直接暴露半边的next、mate、vertex、facet指针。步骤五验证方向一致性在 FreeCAD 中查看一个面的法向与环走向验证外环逆时针、法向朝外。修改面orientation后法向反转体现半边方向与法向的关系。5.10 应用场景与案例5.10.1 布尔运算找共享边布尔求交后需把交线插入两体找共享边配对。半边结构使“边两侧是哪两面”(O(1)) 查询高效配对。5.10.2 缝合把有缝隙的面片拼成水密体需找距离近的边配对。半边结构遍历所有边 (O(E))配对后更新 mate 指针。5.10.3 渲染画边显示线框或隐藏线消除需遍历所有面边。半边next链使遍历高效。5.10.4 网格划分FEA 网格器沿边布节点共享边节点需匹配。半边结构找共享边保证节点一致。5.10.5 法向计算面法向由环走向用右手法则确定。半边方向即环走向。5.10.6 拓扑验证检查每条边恰好两个半边、(M(M(h))h)、next成环等不变量快速诊断 B-Rep 合法性。5.10.7 特征识别识别孔、槽等特征需遍历面边拓扑。半边结构支持高效拓扑模式匹配。5.10.8 拓扑命名在参数化重算中拓扑命名需要稳定引用边与面。半边结构的邻接信息有助于追踪边在修改后的对应关系。5.11 常见问题与调优问题一非流形边导致半边失效三面沿一边汇合时半边结构无法表示。调优改用辐射边结构或把非流形拆成多个流形体或采用广义半边模型。问题二方向不一致个别半边方向错导致法向矛盾。调优用拓扑修复工具检查并翻转建模时保证外环逆时针。问题三next/prev指针断修改操作未正确更新指针。调优用不变量检查诊断修改后验证mate.mate self、next成环。问题四孔环方向错内环应顺时针但建成逆时针导致面域错。调优检查并翻转内环方向。问题五遍历性能差若内核未用半边而用边表加面表邻接查询 (O(E \times F)) 慢。调优确认内核用半边或类似结构OCCT 的TopoDS遍历虽非纯半边但足够高效。问题六共享边判错浮点误差使本应共享的边被判为两条。调优用容差判定容差边表示。问题七内存占用高指针半边结构内存占用大。调优用索引替代指针采用 SOA 布局压缩半边记录。5.12 发展趋势与展望5.12.1 非流形扩展仿真一体化需求推动半边向辐射边扩展支持多面沿一边。广义半边模型可作为统一框架。5.12.2 并行遍历半边next链有依赖并行遍历受限。GPU 并行推动无依赖的边表布局与半边分区。5.12.3 内存紧凑半边指针占内存紧凑布局SOA、索引替代指针提升缓存命中。压缩半边结构是研究热点。5.12.4 动态更新频繁修改时指针更新开销研究增量与持久化半边结构。5.12.5 与图数据库结合拓扑即图半边结构可视为图数据库的特化。未来可能用图引擎支撑更灵活拓扑查询。5.12.6 AI 与拓扑可微拓扑、自动特征识别对半边结构提出新接口需求。AI 可能改变拓扑查询与修复。5.13 小结半边数据结构是 B-Rep 流形表面拓扑表示的事实标准。其核心思想是把每条边拆成两个有向半边互为对向半边按面内环顺序用next/prev链接。这使“边两侧是哪两面”“面由哪些边围成”“顶点邻面”等邻接查询在 (O(1)) 或局部线性时间内完成是内核性能基础。本文提出的六元组模型、七条不变量、邻接查询复杂度定理、欧拉操作对应表、广义半边模型、信息论下界与并行遍历依赖图为半边结构的分析、实现与扩展提供了统一语言。半边结构由 Weiler 1986 系统化源自翼边结构的简化面向流形非流形需辐射边扩展。OCCT 的TopoDS_*、CGAL 的Polyhedron_3都基于半边思想。理解半边结构是理解 B-Rep 拓扑查询与修改的钥匙。5.14 练习题题1形式化写出半边结构的六元组模型并说明每条不变量的含义。手工验证一个四面体的半边结构是否满足全部不变量。题2复杂度证明在合法半边结构中查询一条边的两侧面为 (O(1))查询一个顶点的所有邻接面为 (O(d(v)))其中 (d(v)) 为顶点度数。题3算法写出遍历一个面所有边、遍历一个顶点所有邻接面的伪代码并说明其正确性依据。题4欧拉操作用半边指针更新实现MEF加边分裂面与KEF删边合并面并验证操作前后欧拉公式不变。题5非流形说明半边结构为何不能表示三面沿一边汇合的非流形结构并提出一种扩展方案。题6实践在 FreeCAD 或 CGAL 中实现一个简单多面体的半边结构验证邻接查询与不变量。参考答案要点题1六元组 (\langle V, HE, F, O, M, N, \Phi \rangle)。不变量包括 (M(M(h))h)、(M(h)\neq h)、(O(M(h))O(N(h)))、(N) 成环、每边两个半边、方向一致、面边关联正确。四面体可手工验证。题2边两侧面由 (\Phi(h)) 与 (\Phi(M(h))) 直接读取顶点星形通过 (h \leftarrow M(h).N) 遍历次数等于顶点度数。题3面遍历用next链顶点星形用mate.next链。正确性由边连续条件与环闭合保证。题4MEF加两个半边拆环为两环KEF删两个半边合并两环。拓扑变化分别为 (E1,F1) 与 (E-1,F-1)欧拉公式不变。题5半边结构每条边仅允许两个半边非流形边需多个半边。扩展方案为辐射边或广义半边模型允许一条边关联 (k) 个半边。题6参考 5.9 节教程。5.15 参考文献与延伸阅读Weiler, K. Topology as a Framework for Computational Geometry. 1986.Baumgart, B. G.Winged-Edge Polyhedron Representation. Stanford AI Memo, 1975.Mäntylä, M.An Introduction to Solid Modeling. Computer Science Press, 1988.Stroud, I.Boundary Representation Modelling Techniques. Springer, 2006.de Berg, M., et al.Computational Geometry: Algorithms and Applications. Springer.CGAL Polyhedron_3 文档与半边结构教程.OpenCASCADE TopoDS 与 BRepTools_WireExplorer 文档https://dev.opencascade.org/ACIS 辐射边结构公开资料.本报告第 04 章边界表示法 B-Rep 基本原理.本报告第 06 章翼边结构.本报告第 07 章辐射边结构.本报告第 08 章DCEL 与平面细分.