实体的表示

点集拓扑表示

• 有效物体（实体）：具有一定形状，具有确定的封闭边界（表面），是一个内部连通的三维点集
  • 内点：点集中完全包含于该点集充分小邻域的点
  • 边界点
• 正则运算 $r$：先对物体取内点再取闭包
  • 边界 $b$
  • 内点 $i$
• 正则点集：$A=rA$
• 实体的可计算性：对于一个占据空间的正则点集，如果其表面是二维流形，则该正则点集为实体
• 正则集合运算 $A \text{ op}^*\ B=r(A \text{ op } B)$
  • 只需计算 $b(A\text{ op}^*\ B)$
  • $b(A\cap^* B)=(bA\cap iB)\cup(bB\cap iA)\cup(bA\cap bB)_{\text{same side}}$

形体表示

• 形体信息
  • 集合信息：欧式空间中位置和大小
  • 拓扑信息：各分量数目及其互相间的连接关系
• 习题表面：封闭，有向，非自交，有界，连续
• 形体自身：刚性，三维一致性，表示有限性
• 几何元素
  • 体：欧式空间中非空有界的封闭子集
  • 体素：能用有限个尺寸参数定义一个简单封闭空间
    • 长方体，圆柱体，球体，代数半空间，参数定义的截面旋转
  • 壳：在观察方向上所能看到的形体的最大外轮廓线
  • 面：有限非零的区域，有一个外环和若干个内环界定范围
  • 环：由有序有向边组成的封闭边界
    • 面上沿环前进，左侧面内
  • 边：两个邻面或多个邻面的交界
  • 点：不允许孤立点
• 拓扑关系表示：相邻性，包含性

实体的造型

• 多边形表面表示：用一组包围物体内部的表面多边形描述边界

  • 多边形边表表示：顶点表，边表，面表
  • 多边形平面方程：$Ax+By+Cz+D=0$
  • 多边形表面方向：从里向外以右手系逆时针方向选择 $V_1,V_2,V_3$，$N=(V_2-V_1)\times(V_3-V_1)$

• 空间分割表示：实体被分割表示为互不相交的粘合在一起的体素

  • 空间位置枚举表示法：单一立方体
  • 八叉树表示法：每个结点为立方体，根据 Full, Partial, Empty 继续划分 Partial
  • 单元分解表示法：不同类型基本体素粘合

• 扫掠几何/推移表示 (sweep representation)

  • 广义平移 sweep：允许二维区域大小变换，轨道可以不垂直与二维区域所在平面
  • 旋转 sweep
  • 广义 sweep：允许带推移物体在推移过程中任意变换
  • 正则集合运算困难

• 边界表示：描述实体边界描述实体

  • 最简单：多边形表面表示
  • 半边数据结构：以边为核心
    • 将边表示成拓扑意义上相反的两条半边
    • 顶点 -> 半边 -> 环 -> 面 -> 多边形
  • 二维流形：每条边值严格属于两个多边形
  • 简单多面体：与球拓扑同构的多面体
    • 满足欧拉公式：$v-e+f=2$
  • 广义欧拉公式：$v-e+f-r=2(s-h)$
    • $r$：多面体上环的个数
    • $h$：贯穿多面体的洞的个数
    • $s$：相互分离的多面体数
  • 欧拉运算操作
    • m: 生成
    • k: 删除
  • 正则集合运算
    • 相交检测：预检查两个物体是否相交，包围盒技术
    • 交线计算
    • 表面分类
    • 结果表示

• 构造实体几何表示 (CSG)：将一些简单的基本体素通过正则集合运算构造和表示新实体

  • CSG 树：中间结点为正则集合运算，叶节点为基本体素
  • 不唯一，不便于输出显示，获取实体信息需要大量计算

• 特征模型表示：用一组特征参数定义一簇类似的物体