数据模型——边界表示
?比较著名的有半边数据结构、翼边数
左上边P2右上边据结构、辐射边数据结构等?翼边数据结构
左外环e左下边右外环??最早是由美国斯坦福大学B.G.Baumgart
P1右下边等人
??于1972年提出
??以边为核心来组织数据的一种数据结构??用指针记录每一边的两个邻面（即左外环和右外环）、两个顶点、两侧各自相邻的两个邻边（即左上边、左下边、右上边和右下边）
??用这一数据结构表示多面体模型是完备的，但它不能表示带有精确曲面边界的实体
哈尔滨工业大学计算机学院 苏小红
图6-21 翼边数据结构
41
数据模型——边界表示
?与翼边数据结构的主要区别：??将一条物理边拆成两条边来表示??使其中每条边只与一个邻接面相关
??由于半边数据结构中的边只表示相应物理边的一半信息，所以称其为半边
42
哈尔滨工业大学计算机学院 苏小红
数据模型——分解表示（1/5）
?空间位置枚举表示
??选择一个立方体空间，将其均匀划分
??用三维数组C[I][J][K]表示物体，数组中的元素
与单位小立方体一一对应
当C[I][j][k] = 1时，
表示对应的小立方体被物体占据
当C[I][j][k] = 0时，表示对应的小立方体没有被物体占据
43
哈尔滨工业大学计算机学院 苏小红
数据模型——分解表示（2/5）
?八叉树（octrees）表示
??对空间位置枚举表示的空间分割方法作了
改进：均匀分割 自适应分割
44
哈尔滨工业大学计算机学院 苏小红数据模型——分解表示（3/5）
?八叉树建立过程
??八叉树的根节点对应整个物体空间
??如果它完全被物体占据，将该节点标记为F(Full)，算法结束；??如果它内部没有物体，将该节点标记为E(Empty)，算法结束；??如果它被物体部分占据，将该节点标记为P(Partial)，并将它分
割成8个子立方体，对每一个子立方体进行同样的处理yP0777455xE1E2E3E4E5F6E7P550E1E2E3E4F5F6E7Fz(a)(b)45
哈尔滨工业大学计算机学院 苏小红
计算机图形学-实体几何造型基础
