Edg ebreaker 算法的网格遍历过程是基于区域增长原理的: 在遍历网格过程中要始终维持一个由边组成的有向边界, 这个边界把网格分成已遍历部分和未遍历部分, 然后每遍历一个多边形, 则输出一个该多边形和边界的拓扑关系操作( 符) , 并把该多边形归入已编码部分􀀁 其具体遍历过程如下: 先选择任意一个三角形形成最初的边界, 再选择任意一条边为当前边Edgebreaker 算法采用5 个操作符C , L , E , R 和S 记录当前三角形与边界的拓扑关系, 其中, C 表示第3 顶点不在边界上的拓扑情况;L 和R 表示第3 顶点在边界上且当前三角形除了当前边外还有一条边( e) 在边界上, L 和R 分别表示e 在当前边的不同方向; 使用S 把图形分成2 部分, 同时需要用额外的偏移或其他操作记录分支信息; E 表示三角形的3 条边都在边界上 图1 所示为C, L , E , R 和S , 其中, 深灰色部分为网格已遍历部分, 白色部分为网格未遍历部分, 深灰色和白色的分界线为边界; 黑实边为当前边; 浅灰色三角形为当前三角形, 其被遍历后归入深灰色部分; 黑色大圆点为第3 顶点; 黑虚线表示下一个当前边􀀁 图2 所示为该算法压缩过程示意图, 图中带箭头黑色线段表示三角网格遍历顺序, 其中有分支的地方是S 操作( 把图形分成2 部分) 图2 的最后遍历结果为CCRCRSERCSCRRCRRRERC RCRCRRRLL R L ( 最后的E 操作可省略) , 共有31个操作符􀀁 获取操作符序列后,Edgebreaker 算法采用霍夫曼编码对其压缩得到最终的压缩结果