北大计算机系多媒体与人机交互 1
第十讲 三维形体的表示
? 表示形体的两种模型
? 实体的定义
? 正则集合运算
? 特征表示
? 空间分割表示
? 推移表示
? 边界表示
? 构造实体几何表示
? 不规则形体的建模方法
? L系统
北大计算机系多媒体与人机交互 2
表示形体的两种模型（ 1/4）
? 数据模型
– 完全以数据描述
– 例如
? 用以 8个顶点表示的立方体
? 以中心点和半径表示的球
– 以数据文件的形式存在
– 包括 ----特征表示、空间分割表示、推移表示、边界
表示、构造实体几何表示等
– 进一步分为
? 线框模型
– 将形体表示成一组轮廓线的集合
– 简单、处理速度快
– 与形体之间不存在一一对应关系，是真实物体的高度抽象，不适合
真实感显示
北大计算机系多媒体与人机交互 3
表示形体的两种模型（ 2/4）
? 表面模型
– 将形体表示成一组表面的集合
– 形体与其表面一一对应，适合于真实感显示
北大计算机系多媒体与人机交互 4
表示形体的两种模型（ 3/4）
– 实体模型
? 用来描述实体，主要用于 CAD/CAM
? 包含了描述一个实体所需的较多信息，如几何信
息、拓扑信息
? 过程模型
– 以一个过程和相应的控制参数描述
– 例如
? 用一些控制参数和一个生成规则描述的植物
– 以一个数据文件和一段代码的形式存在
– 包括 ----粒子系统,L系统、迭代函数系统等
北大计算机系多媒体与人机交互 5
表示形体的两种模型（ 4/4）
? 模型分类
北大计算机系多媒体与人机交互 6
实体的定义（ 1/4）
? 抽象带来的问题
– 计算机中表示的物体是无效的
– 不能够客观存在
? 为什么要求客观存在
– CAD/CAM的需求
? 什么是客观存在（有效） — 实 体的定义
– 具有一定的形状
– 具有封闭的边界（表面 )
– 内部连通
– 占据有限的空间
– 经过运算后，仍然是有效的物体
北大计算机系多媒体与人机交互 7
实体的定义（ 2/4）
? 内点
? 边界点
? 取内点运算 i
? 取闭包运算 c
? 正则运算 r AicAr ????
北大计算机系多媒体与人机交互 8
实体的定义（ 3/4）
? 正则点集
– 称为 A的正则点集
– 称 A为正则点集，如果它满足
? 问题：正则点集是实体？
Ar?
AAr ??
北大计算机系多媒体与人机交互 9
实体的定义（ 4/4）
? 实体的定义 — 可 计算的条件
– 正则点集
– 表面是二维流形
? 二维流形
– 其上任意一点存在充分小的领域与圆盘同构
（存在连续的一一映射）
北大计算机系多媒体与人机交互 10
正则集合运算（ 1/2）
? 为什么需要正则集合运算
– 集合运算式构造复杂物体的有效方法
– 普通的集合运算会产生无效物体
北大计算机系多媒体与人机交互 11
正则集合运算（ 2/2）
? 正则集合运算的定义
– 正则并
– 正则交
– 正则差
)(* BopArBopA ??
)(* BopArBA ???
)(* BopArBA ???
)(* BopArBA ???
北大计算机系多媒体与人机交互 12
特征表示
? 用一组特征参数表示一组类似的物体
? 特征包括形状特征、材料特征等
? 适用于工业上标准件的表示
北大计算机系多媒体与人机交互 13
空间分割表示（ 1/8）
? 空间位置枚举表示
– 选择一个立方体空间，将他均匀划分
北大计算机系多媒体与人机交互 14
空间分割表示（ 2/8）
– 用三维数组 C[I][J][K]表示物体，数组中的
元素与单位小立方体一一对应
? 当 C[I][j][k] = 1时，表示对应的小立方体被物体占据
? 当 C[I][j][k] = 0时，表示对应的小立方体没有被物体占据
– 优点
? 可以表示任何物体
? 容易实现物体间的集合运算
? 容易计算物体的整体性质，如体积等
– 缺点
? 占用大量的存储空间，如 1024*1024*1024 = 1G bits
? 没有边界信息，不适于图形显示
? 对物体进行几何变换困难，如非 90度的旋转变换
? 是物体的非精确表示
北大计算机系多媒体与人机交互 15
空间分割表示（ 3/8）
? 八叉树表示
– 对空间位置枚举表示的空间分割方法作了改进：均
匀分割 自适应分割
– 八叉树建立过程
?八叉树的根节点对应整个物体空间
?如果它完全被物体占据，将该节点标记为 F(Full)，算法结束；
?如果它内部没有物体，将该节点标记为 E(Empty)，算法结束；
?如果它被物体部分占据，将该节点标记为 P(Partial)，并将它分割成 8
个子立方体，对每一个子立方体进行同样的处理
北大计算机系多媒体与人机交互 16
空间分割表示（ 4/8）
北大计算机系多媒体与人机交互 17
空间分割表示（ 5/8）
北大计算机系多媒体与人机交互 18
空间分割表示（ 6/8）
– 优点
? 可以表示任何物体
? 容易实现物体建的集合运算
? 容易计算物体的整体性质，如体积等
? 较空间位置枚举表示占用的存贮空间少
– 缺点
? 没有边界信息，不适于图形显示
? 对物体进行几何变换困难
? 是物体的非精确表示
北大计算机系多媒体与人机交互 19
空间分割表示（ 7/8）
? 单元分解表示
– 对空间位置枚举表示的空间分割方法作了改进：单
一体素 多种体素
– 三种空间分割方法的比较
? 空间位置枚举表示 ----同样大小 立方体粘合在一起表示物体
? 八叉树表示 ----不同大小的立方体 粘合在一起表示物体
? 单元分解表示 ----多种体素 粘合在一起表示物体
北大计算机系多媒体与人机交互 20
空间分割表示（ 8/8）
– 优点
? 表示简单
? 容易实现几何变换
? 基本体素可以按需选择，表示范围较广
? 可以精确表示物体
– 缺点
? 物体的表示不唯一
? 物体的有效性难以保证
北大计算机系多媒体与人机交互 21
推移表示 (1/3)
? 将物体 A沿着轨迹 P推移得到物体 B，称 B
为 sweep体
? 平移 sweep----将一个二维区域沿着一个
矢量方向推移
北大计算机系多媒体与人机交互 22
推移表示 (2/3)
? 旋转 sweep----将一个二维区域绕旋转轴
旋转一周
例子,3D MAX
北大计算机系多媒体与人机交互 23
推移表示 (3/3)
? 广义 sweep
– 任意物体沿着任意轨迹推移
– 推移过程中物体可以变形
? 优点
– 表示简单、直观
– 适合做图形输入手段
? 缺点
– 作几何变换困难
– 对几何运算不封闭
例子,3D MAX
北大计算机系多媒体与人机交互 24
边界表示（ 1/5）
? 物体的边界与物体一一对应，确定了物
体的边界也就确定了物体本身
? 用于表示物体边界的有 ----平面多边形、
曲面片
? 什么是多面体？
? 平面多面体
– 表面由平面多边形组成的多面体
? 简单多面体
– 与球拓扑同构
北大计算机系多媒体与人机交互 25
边界表示（ 2/5）
? 欧拉公式
– 欧拉公式是必要条件
V-e+f=2
北大计算机系多媒体与人机交互 26
边界表示 (3/5)
? 广义欧拉公式
V-e+f-r=2(s-h)
r,多面体表面上孔的个数
s,相互分离的多面体数
h,贯穿多面体的孔洞个数
北大计算机系多媒体与人机交互 27
边界表示 (5/5)
? 优点
– 精确表示物体
– 表示能力强
– 几何变换容易
– 适于显示处理
? 缺点
– 表示复杂
– 有效性难以保证
– 集合运算复杂
北大计算机系多媒体与人机交互 28
构造实体几何表示（ 1/2）
? 将物体表示成一棵二叉树，称为 CSG树
– 叶节点 ----基本体素，如立方体、圆柱体等
– 中间节点 ----正则集合运算
北大计算机系多媒体与人机交互 29
构造实体几何表示（ 2/2)
? 优点
– 表示简单、直观
– 也是物体的构造方法，可用作图形输入手段
– 容易计算物体的整体性质
– 物体的有效性自动得到保证
? 缺点
– 表示不唯一
– 不能直接用于显示
– 求交计算麻烦
北大计算机系多媒体与人机交互 30
不规则形体的建模方法
? 迭代函数系统
? 基于文法的模型
? 粒子系统
? 动力系统
北大计算机系多媒体与人机交互 31
L系统（ 1/4）
? 由生物学家 Lindenmayer创立
? 基本思想：
– 用文法表示植物的拓扑结构
– 通过图形学方法生成逼真的画面
? DOL系统（确定的上下文无关的 L系统）
– 定义为三元组 <V,w,P>，其中
V----表示字母集合
V*----表示 V上所有单词的集合
w----是一个非空单词，称为公理
P----产生式集合
，使得
如果没有明显的产生式，则令
*,VxVa ???? xa ?
aa ?
北大计算机系多媒体与人机交互 32
L系统（ 2/4）
– 例子 ----Koch 雪花曲线
? V,{F,+,-}
? w,F
? P,F->F-F++F-F
? 几何解释
– F：向前画一条线
– +：右转
– -：左转
?
?
北大计算机系多媒体与人机交互 33
L系统（ 3/4）
? Bracketed L系统
– 增加如下两个字符
[：压栈
]：出栈
– 例子 ----植物
w,F
P,F->F[+F]F[-F]F
北大计算机系多媒体与人机交互 34
L系统（ 4/4）
第十讲 三维形体的表示
? 表示形体的两种模型
? 实体的定义
? 正则集合运算
? 特征表示
? 空间分割表示
? 推移表示
? 边界表示
? 构造实体几何表示
? 不规则形体的建模方法
? L系统
北大计算机系多媒体与人机交互 2
表示形体的两种模型（ 1/4）
? 数据模型
– 完全以数据描述
– 例如
? 用以 8个顶点表示的立方体
? 以中心点和半径表示的球
– 以数据文件的形式存在
– 包括 ----特征表示、空间分割表示、推移表示、边界
表示、构造实体几何表示等
– 进一步分为
? 线框模型
– 将形体表示成一组轮廓线的集合
– 简单、处理速度快
– 与形体之间不存在一一对应关系，是真实物体的高度抽象，不适合
真实感显示
北大计算机系多媒体与人机交互 3
表示形体的两种模型（ 2/4）
? 表面模型
– 将形体表示成一组表面的集合
– 形体与其表面一一对应，适合于真实感显示
北大计算机系多媒体与人机交互 4
表示形体的两种模型（ 3/4）
– 实体模型
? 用来描述实体，主要用于 CAD/CAM
? 包含了描述一个实体所需的较多信息，如几何信
息、拓扑信息
? 过程模型
– 以一个过程和相应的控制参数描述
– 例如
? 用一些控制参数和一个生成规则描述的植物
– 以一个数据文件和一段代码的形式存在
– 包括 ----粒子系统,L系统、迭代函数系统等
北大计算机系多媒体与人机交互 5
表示形体的两种模型（ 4/4）
? 模型分类
北大计算机系多媒体与人机交互 6
实体的定义（ 1/4）
? 抽象带来的问题
– 计算机中表示的物体是无效的
– 不能够客观存在
? 为什么要求客观存在
– CAD/CAM的需求
? 什么是客观存在（有效） — 实 体的定义
– 具有一定的形状
– 具有封闭的边界（表面 )
– 内部连通
– 占据有限的空间
– 经过运算后，仍然是有效的物体
北大计算机系多媒体与人机交互 7
实体的定义（ 2/4）
? 内点
? 边界点
? 取内点运算 i
? 取闭包运算 c
? 正则运算 r AicAr ????
北大计算机系多媒体与人机交互 8
实体的定义（ 3/4）
? 正则点集
– 称为 A的正则点集
– 称 A为正则点集，如果它满足
? 问题：正则点集是实体？
Ar?
AAr ??
北大计算机系多媒体与人机交互 9
实体的定义（ 4/4）
? 实体的定义 — 可 计算的条件
– 正则点集
– 表面是二维流形
? 二维流形
– 其上任意一点存在充分小的领域与圆盘同构
（存在连续的一一映射）
北大计算机系多媒体与人机交互 10
正则集合运算（ 1/2）
? 为什么需要正则集合运算
– 集合运算式构造复杂物体的有效方法
– 普通的集合运算会产生无效物体
北大计算机系多媒体与人机交互 11
正则集合运算（ 2/2）
? 正则集合运算的定义
– 正则并
– 正则交
– 正则差
)(* BopArBopA ??
)(* BopArBA ???
)(* BopArBA ???
)(* BopArBA ???
北大计算机系多媒体与人机交互 12
特征表示
? 用一组特征参数表示一组类似的物体
? 特征包括形状特征、材料特征等
? 适用于工业上标准件的表示
北大计算机系多媒体与人机交互 13
空间分割表示（ 1/8）
? 空间位置枚举表示
– 选择一个立方体空间，将他均匀划分
北大计算机系多媒体与人机交互 14
空间分割表示（ 2/8）
– 用三维数组 C[I][J][K]表示物体，数组中的
元素与单位小立方体一一对应
? 当 C[I][j][k] = 1时，表示对应的小立方体被物体占据
? 当 C[I][j][k] = 0时，表示对应的小立方体没有被物体占据
– 优点
? 可以表示任何物体
? 容易实现物体间的集合运算
? 容易计算物体的整体性质，如体积等
– 缺点
? 占用大量的存储空间，如 1024*1024*1024 = 1G bits
? 没有边界信息，不适于图形显示
? 对物体进行几何变换困难，如非 90度的旋转变换
? 是物体的非精确表示
北大计算机系多媒体与人机交互 15
空间分割表示（ 3/8）
? 八叉树表示
– 对空间位置枚举表示的空间分割方法作了改进：均
匀分割 自适应分割
– 八叉树建立过程
?八叉树的根节点对应整个物体空间
?如果它完全被物体占据，将该节点标记为 F(Full)，算法结束；
?如果它内部没有物体，将该节点标记为 E(Empty)，算法结束；
?如果它被物体部分占据，将该节点标记为 P(Partial)，并将它分割成 8
个子立方体，对每一个子立方体进行同样的处理
北大计算机系多媒体与人机交互 16
空间分割表示（ 4/8）
北大计算机系多媒体与人机交互 17
空间分割表示（ 5/8）
北大计算机系多媒体与人机交互 18
空间分割表示（ 6/8）
– 优点
? 可以表示任何物体
? 容易实现物体建的集合运算
? 容易计算物体的整体性质，如体积等
? 较空间位置枚举表示占用的存贮空间少
– 缺点
? 没有边界信息，不适于图形显示
? 对物体进行几何变换困难
? 是物体的非精确表示
北大计算机系多媒体与人机交互 19
空间分割表示（ 7/8）
? 单元分解表示
– 对空间位置枚举表示的空间分割方法作了改进：单
一体素 多种体素
– 三种空间分割方法的比较
? 空间位置枚举表示 ----同样大小 立方体粘合在一起表示物体
? 八叉树表示 ----不同大小的立方体 粘合在一起表示物体
? 单元分解表示 ----多种体素 粘合在一起表示物体
北大计算机系多媒体与人机交互 20
空间分割表示（ 8/8）
– 优点
? 表示简单
? 容易实现几何变换
? 基本体素可以按需选择，表示范围较广
? 可以精确表示物体
– 缺点
? 物体的表示不唯一
? 物体的有效性难以保证
北大计算机系多媒体与人机交互 21
推移表示 (1/3)
? 将物体 A沿着轨迹 P推移得到物体 B，称 B
为 sweep体
? 平移 sweep----将一个二维区域沿着一个
矢量方向推移
北大计算机系多媒体与人机交互 22
推移表示 (2/3)
? 旋转 sweep----将一个二维区域绕旋转轴
旋转一周
例子,3D MAX
北大计算机系多媒体与人机交互 23
推移表示 (3/3)
? 广义 sweep
– 任意物体沿着任意轨迹推移
– 推移过程中物体可以变形
? 优点
– 表示简单、直观
– 适合做图形输入手段
? 缺点
– 作几何变换困难
– 对几何运算不封闭
例子,3D MAX
北大计算机系多媒体与人机交互 24
边界表示（ 1/5）
? 物体的边界与物体一一对应，确定了物
体的边界也就确定了物体本身
? 用于表示物体边界的有 ----平面多边形、
曲面片
? 什么是多面体？
? 平面多面体
– 表面由平面多边形组成的多面体
? 简单多面体
– 与球拓扑同构
北大计算机系多媒体与人机交互 25
边界表示（ 2/5）
? 欧拉公式
– 欧拉公式是必要条件
V-e+f=2
北大计算机系多媒体与人机交互 26
边界表示 (3/5)
? 广义欧拉公式
V-e+f-r=2(s-h)
r,多面体表面上孔的个数
s,相互分离的多面体数
h,贯穿多面体的孔洞个数
北大计算机系多媒体与人机交互 27
边界表示 (5/5)
? 优点
– 精确表示物体
– 表示能力强
– 几何变换容易
– 适于显示处理
? 缺点
– 表示复杂
– 有效性难以保证
– 集合运算复杂
北大计算机系多媒体与人机交互 28
构造实体几何表示（ 1/2）
? 将物体表示成一棵二叉树，称为 CSG树
– 叶节点 ----基本体素，如立方体、圆柱体等
– 中间节点 ----正则集合运算
北大计算机系多媒体与人机交互 29
构造实体几何表示（ 2/2)
? 优点
– 表示简单、直观
– 也是物体的构造方法，可用作图形输入手段
– 容易计算物体的整体性质
– 物体的有效性自动得到保证
? 缺点
– 表示不唯一
– 不能直接用于显示
– 求交计算麻烦
北大计算机系多媒体与人机交互 30
不规则形体的建模方法
? 迭代函数系统
? 基于文法的模型
? 粒子系统
? 动力系统
北大计算机系多媒体与人机交互 31
L系统（ 1/4）
? 由生物学家 Lindenmayer创立
? 基本思想：
– 用文法表示植物的拓扑结构
– 通过图形学方法生成逼真的画面
? DOL系统（确定的上下文无关的 L系统）
– 定义为三元组 <V,w,P>，其中
V----表示字母集合
V*----表示 V上所有单词的集合
w----是一个非空单词，称为公理
P----产生式集合
，使得
如果没有明显的产生式，则令
*,VxVa ???? xa ?
aa ?
北大计算机系多媒体与人机交互 32
L系统（ 2/4）
– 例子 ----Koch 雪花曲线
? V,{F,+,-}
? w,F
? P,F->F-F++F-F
? 几何解释
– F：向前画一条线
– +：右转
– -：左转
?
?
北大计算机系多媒体与人机交互 33
L系统（ 3/4）
? Bracketed L系统
– 增加如下两个字符
[：压栈
]：出栈
– 例子 ----植物
w,F
P,F->F[+F]F[-F]F
北大计算机系多媒体与人机交互 34
L系统（ 4/4）
