《辽大07几何造型》PPT课件

2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 1 第 七 章 几 何 造 型 通 过 对 点 、 线 、 面 、 体 等 图 形 元 素 进 行 几 何 变换 和 并 、 交 、 差 等 集 合 运 算 ， 在 计 算 机 内 表 示 、 构造 三 维 形 体 的 技 术 ， 即 为 几 何 造 型 技 术 。 它 是 计 算机 图 形 学 的 一 个 重 要 组 成 部 分 ， 是 CAD/CAM和 各种 计 算 机 辅 助 制 作 技 术 的 基 础 。 几 何 造 型 包 括 曲 面造 形 和 实 体 造 型 等 技 术 。 曲 面 造 形 所 涉 及 到 的 基 础内 容 诸 如 自 由 曲 线 和 曲 面 的 表 示 我 们 已 经 讨 论 过 。下 面 将 介 绍 有 关 实 体 造 型 的 基 础 知 识 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 2 7.1 形 体 在 计 算 机 内 的 表 示 如 何 在 计 算 机 内 定 义 和 表 示 由 基 本 图 元 的 集 合 所决 定 的 形 体 ， 是 几 何 造 形 中 最 基 本 的 问 题 。7.1.1 几 何 元 素 的 定 义 在 计 算 机 内 通 常 用 点 、 边 、 面 、 环 、 体 等 作 为 基 本几 何 元 素 。1. 点 点 是 0维 几 何 元 素 ， 分 端 点 、 交 点 、 切 点 等 ， 如 边 的端 点 。 但 在 形 体 定 义 中 ， 点 不 允 许 孤 立 地 存 在 于 实 体内 部 或 外 部 ， 只 能 存 在 于 实 体 边 界 上 。 在 自 由 曲 线 和曲 面 的 描 述 中 常 用 三 种 类 型 的 点 ， 即 控 制 点 、 型 值 点 、插 值 点 。 在 计 算 机 内 ， 点 用 其 位 置 坐 标 表 示 。 点 是 几何 造 型 中 的 最 基 本 元 素 ， 用 计 算 机 存 储 、 管 理 、 输 出形 体 的 实 质 就 是 对 点 集 及 其 连 接 关 系 的 处 理 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 3 2. 边 边 是 1维 几 何 元 素 ， 由 端 点 或 曲 线 方 程 定 义 ， 如 直 线 边 、二 次 曲 线 边 、 三 次 样 条 曲 线 边 等 。 曲 线 边 也 可 由 一 系 列 型值 点 或 控 制 点 表 示 。3. 面 面 是 2维 几 何 元 素 ， 是 形 体 上 一 个 有 限 、 非 零 的 区 域 ， 由数 学 方 程 定 义 。 面 具 有 方 向 性 ， 一 般 用 其 外 法 线 方 向 作 为面 的 正 向 。 它 用 一 个 外 环 和 若 干 内 环 界 定 其 有 效 范 围 ， 面可 以 无 内 环 ， 但 必 须 有 外 环 。 在 几 何 造 型 中 常 分 平 面 、 二次 面 、 双 三 次 参 数 曲 面 等 形 式 。4. 环 环 是 有 序 、 有 向 边 组 成 的 面 上 封 闭 边 界 ， 环 中 各 条 边 不能 自 交 ， 相 邻 两 条 边 共 享 一 个 端 点 。 环 有 内 环 与 外 环 之 分 ，确 定 面 的 最 大 外 边 界 的 环 称 为 外 环 ， 每 个 面 有 且 仅 有 一 个外 环 。 若 面 内 有 空 ， 则 还 有 内 环 。 通 常 外 环 的 边 按 逆 时 针方 向 排 序 ， 而 内 环 的 边 按 顺 时 针 方 向 排 序 。 这 样 定 义 后 ， 在 面 上 沿 一 个 环 前 进 ， 其 左 侧 总 是 面 内 ， 右 侧 总 是 面 外 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 4 5. 体 体 是 3维 几 何 元 素 ， 是 由 封 闭 表 面 围 成 的 维 数 一 致 的有 效 空 间 。 为 了 保 证 几 何 造 型 的 可 靠 性 和 可 加 工 性 ， 要求 形 体 上 任 意 一 点 的 足 够 小 的 邻 域 在 拓 扑 上 应 是 一 个 等价 的 封 闭 圆 ， 即 围 绕 该 点 的 形 体 邻 域 在 二 维 空 间 中 可 构成 一 个 单 连 通 域 。 把 满 足 这 个 定 义 的 形 体 称 之 为 正 则 形体 。 形 体 的 正 则 性 限 制 任 何 面 必 须 是 形 体 表 面 的 一 部 分 ，不 能 是 悬 面 ； 每 条 边 有 且 只 能 有 两 个 邻 面 ， 不 能 是 悬 边 ；点 至 少 和 三 条 边 邻 接 。 图 1示 出 几 个 非 正 则 形 体 的 例 子 。 有 悬 面 有 悬 边 1条 边 有 4个 邻 面图 1 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 5 7.1.2 三 维 形 体 表 示 的 三 种 模 型 我 们 可 以 通 过 对 一 个 三 维 空 间 形 体 进 行 近 似 的 描 述来 表 示 和 构 造 相 应 的 三 维 图 形 。 在 计 算 机 中 常 用 的 是 线框 、 表 面 和 实 体 三 种 表 示 模 型 。 1. 线 框 模 型 线 框 模 型 是 最 早 用 来 表 示 形 体 的 模 型 ， 并 且 至 今 仍在 广 泛 地 应 用 。 线 框 模 型 由 顶 点 表 示 几 何 位 置 ， 相 邻 顶点 连 接 构 成 棱 边 表 示 几 何 形 状 特 征 。 图 2是 一 个 长 方 体的 例 子 ， 8个 顶 点 和 12条 棱 边 表 示 出 这 一 形 体 。图 2 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 6 线 框 模 型 是 表 面 模 型 和 实 体 模 型 的 基 础 。 它 具 有结 构 简 单 、 易 于 理 解 、 数 据 量 少 的 特 点 ， 因 此 计 算 机处 理 速 度 快 。 但 用 线 框 模 型 表 示 形 体 不 充 分 ， 无 法 进行 剖 切 、 消 隐 、 明 暗 等 图 形 处 理 ， 也 很 难 表 示 圆 柱 体 、球 体 等 曲 面 形 体 。2. 表 面 模 型 表 面 模 型 是 用 有 向 棱 边 围 成 的 部 分 来 定 义 形 体 表 面 ，由 面 的 集 合 来 定 义 形 体 。 表 面 模 型 是 在 线 框 模 型 的 基础 上 ， 通 过 增 加 由 哪 些 棱 边 按 何 种 顺 序 连 接 等 内 容 定义 出 表 面 ， 从 而 可 以 满 足 面 面 求 交 、 线 面 消 隐 、 明 暗处 理 等 应 用 需 要 。 这 种 模 型 通 常 用 于 构 造 复 杂 的 曲 面形 体 。 表 面 模 型 完 整 地 定 义 了 形 体 的 边 界 ， 但 是 形 体的 实 心 部 分 在 边 界 哪 一 侧 并 不 明 确 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 7 图 3是 在 线 框 模 型 的 基 础 上 增 加 各 表 面 的 信 息 。图 3 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 8 3. 实 体 模 型 如 果 要 处 理 完 整 的 三 维 形 体 ， 最 终 必 须 使 用 实 体 模型 ， 实 体 模 型 明 确 定 义 了 表 面 的 哪 一 侧 存 在 实 体 。 在表 面 模 型 的 基 础 上 ， 使 用 表 面 的 外 法 线 矢 量 方 向 来 指明 实 体 存 在 的 一 侧 ， 例 如 规 定 正 向 指 向 体 外 。 通 常 用有 向 棱 边 隐 含 地 表 示 表 面 的 外 法 线 矢 量 方 向 。 在 定 义表 面 时 ， 有 向 棱 边 按 右 手 法 则 取 向 ， 沿 着 闭 合 的 棱 边所 得 的 方 向 与 表 面 外 法 线 矢 量 方 向 一 致 。 图 4是 在 表 面模 型 的 基 础 上 增 加 定 义 了 表 面 外 环 的 棱 边 方 向 。 用 此方 法 还 可 检 查 形 体 的 拓 扑 一 致 性 ， 拓 朴 合 法 的 形 体 在相 邻 两 个 面 的 公 共 边 界 上 ， 棱 边 的 方 向 正 好 相 反 。图 4 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 9 4. 三 种 模 型 的 数 据 结 构 线 框 模 型 的 数 据 信 息 是 顶 点 和 棱 边 ， 其 数 据 结 构 一 般 使用 两 组 数 据 ， 或 称 两 表 结 构 。 一 张 表 表 示 顶 点 ， 一 张 表 表示 棱 边 。 以 图 2为 例 ， 假 定 长 方 体 的 长 是 2， 宽 是 1， 高 是 1，则 数 据 组 织 如 表 1和 表 2所 示 。 表 面 模 型 是 在 线 框 模 型 的 基础 上 增 加 定 义 表 面 信 息 ， 所 以 其 数 据 结 构 也 是 在 线 框 模 型两 表 结 构 的 基 础 上 增 加 一 面 表 ， 如 表 3所 示 。 表 1 表 2 表 3 坐 标 值顶 点 编 号 x y z 棱 边 编 号 顶 点 编 号 表 面 编 号 棱 边 编 号 1 0 1 2 1 1 2 1 1 4 3 2 2 0 1 0 2 2 3 2 3 12 7 11 3 1 1 0 3 3 4 3 5 6 7 8 4 1 1 2 4 4 1 4 1 10 5 9 5 0 0 2 5 5 6 5 4 9 8 12 6 0 0 0 6 6 7 6 2 11 6 10 7 1 0 0 7 7 8 8 1 0 2 8 8 5 9 1 5 10 2 6 11 3 7 12 4 8 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 10 实 体 模 型 是 在 表 面 模 型 的 基 础 上 增 加 定 义 了 表 面 的哪 一 侧 存 在 实 体 ,并 且 使 用 有 向 边 表 示 表 面 的 外 法 线 矢量 方 向 。 不 同 于 表 面 模 型 的 是 ， 实 体 模 型 在 定 义 表 面 时 ，需 要 按 右 手 法 则 取 向 安 排 组 成 表 面 的 边 顺 序 。 表 3中 边的 顺 序 已 经 符 合 这 一 要 求 ， 也 可 以 作 为 实 体 模 型 的 面 表 。 三 个 表 中 除 了 所 列 的 基 本 几 何 数 据 外 ， 还 可 以 扩 充增 加 属 性 信 息 。 比 如 边 表 和 面 表 中 可 以 包 括 颜 色 属 性 ，面 表 中 还 可 包 括 透 明 度 、 纹 理 特 征 等 。 对 上 述 三 表 还 可 以 进 行 数 据 的 一 致 性 和 完 整 性 检 验 ，内 容 诸 如 每 个 顶 点 至 少 是 二 条 边 的 端 点 ； 每 条 边 至 少 是一 个 面 的 组 成 部 分 ； 每 个 面 的 边 界 都 是 封 闭 的 ； 每 个 面至 少 有 一 条 同 其 它 面 的 公 共 边 等 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 11 7.2 实 体 模 型 的 构 造 前 面 介 绍 的 表 示 形 体 的 线 框 、 表 面 和 实 体 模 型 是 一种 广 义 的 概 念 ， 并 不 反 映 形 体 在 计 算 机 内 部 所 用 的 具 体表 示 方 式 。 为 适 应 不 同 的 形 体 情 况 和 应 用 要 求 ， 已 发 展了 多 种 具 体 的 实 体 造 型 方 法 。 目 前 常 用 有 扫 描 表 示 法 、边 界 表 示 法 、 构 造 实 体 几 何 法 和 八 叉 树 表 示 法 等 。7.2.1 扫 描 表 示 法 扫 描 (Sweeping)表 示 法 是 一 个 得 到 较 广 泛 应 用 的 表 示三 维 物 体 的 方 法 。 它 的 基 本 原 理 十 分 简 单 ， 即 空 间 中 的一 个 点 ， 一 条 线 或 一 个 面 沿 着 某 一 路 径 移 动 时 ， 所 形 成的 轨 迹 将 产 生 一 个 一 维 的 、 二 维 的 或 三 维 的 图 形 。 用 扫描 法 表 示 或 形 成 一 个 形 体 需 要 定 义 作 扫 描 运 动 的 曲 线 或曲 面 ， 以 及 扫 描 运 动 的 路 径 。 在 三 维 形 体 的 表 示 中 ， 应用 得 最 多 的 是 平 移 扫 描 法 和 旋 转 扫 描 法 两 种 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 12 平 移 扫 描 法 是 所 定 义 的 扫 描 体 沿 着 直 线 路 径 作 移 动而 形 成 扫 描 轨 迹 。 如 图 5中 是 一 个 平 移 扫 描 例 子 ， 扫 描体 是 一 个 圆 ， 扫 描 路 径 是 一 条 直 线 ， 扫 描 后 得 到 一 个 圆柱 体 。 图 5 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 13 旋 转 扫 描 法 是 所 定 义 的 扫 描 体 绕 某 一 轴 线 旋 转 某 一角 度 形 成 扫 描 轨 迹 。 如 图 6中 是 一 条 曲 线 绕 垂 直 轴 线 旋转 后 得 到 的 三 维 形 体 。 旋 转 扫 描 法 构 成 物 体 的 都 是 轴 对称 的 物 体 。 图 6 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 14 一 般 地 ,可 以 沿 任 何 路 径 来 作 扫 描 移 动 。 对 旋转 扫 描 可 以 沿 从 0到 的 角 范 围 内 的 路 径 移 动 。 对非 圆 形 路 径 ， 可 以 给 定 描 述 路 径 的 曲 线 函 数 和 沿路 径 移 动 的 距 离 。 另 外 可 以 沿 扫 描 路 径 变 化 曲 线或 曲 面 的 形 状 和 大 小 及 相 对 于 扫 描 路 径 的 方 向 。 在 扫 描 表 示 法 中 ， 只 需 定 义 二 维 平 面 及 曲 线 ，三 维 空 间 的 实 体 和 曲 面 就 可 分 别 由 二 维 平 面 及 曲线 通 过 扫 描 来 实 现 。 这 对 于 许 多 领 域 的 实 体 造 型是 很 方 便 的 ， 因 此 ， 扫 描 表 示 法 在 许 多 造 型 系 统得 到 应 用 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 15 7.2.2 边 界 表 示 法 一 个 形 体 可 以 用 面 、 环 、 边 、 点 来 定 义 其 位 置 和 形状 ,这 些 面 、 环 、 边 、 点 构 成 形 体 的 边 界 。 如 图 2中 ， 长方 体 由 六 个 面 围 成 ， 对 应 有 六 个 环 ， 每 个 环 由 四 条 边组 成 ， 每 条 边 又 由 两 个 端 点 定 义 。 一 个 形 体 的 边 界 将该 形 体 划 分 为 形 体 中 的 点 和 形 体 外 的 点 ， 它 也 是 形 体与 周 围 环 境 之 间 的 分 界 面 。 很 显 然 ， 只 要 完 整 地 定 义了 形 体 的 边 界 ， 那 么 该 形 体 就 被 唯 一 定 义 了 。 边 界 表 示 法 （ Boundary Representation， B-Rep）就 是 以 物 体 边 界 为 基 础 定 义 和 描 述 几 何 形 体 的 方 法 。所 描 述 的 物 体 由 有 限 个 面 构 成 ， 每 个 面 可 以 由 有 限 条边 围 成 的 有 限 个 封 闭 区 域 定 义 。 用 边 界 表 示 法 描 述 实体 ， 要 求 其 表 面 必 须 满 足 一 定 条 件 ， 如 连 通 、 有 界 、可 定 向 、 不 自 交 和 闭 合 连 接 等 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 16 由 于 边 界 是 以 面 、 边 、 点 为 基 础 的 ， 所 采 用 的 数 据结 构 是 否 便 于 对 实 体 进 行 面 、 边 、 点 的 存 放 、 查 找 或修 改 ， 是 一 个 十 分 关 键 的 问 题 。 边 界 表 示 详 细 记 录 了构 成 形 体 所 有 的 几 何 信 息 和 拓 扑 信 息 。 几 何 信 息 描 述形 体 的 大 小 、 尺 寸 、 位 置 、 形 状 等 ， 而 拓 扑 信 息 则 描述 形 体 的 表 面 、 棱 边 、 顶 点 等 相 互 间 的 连 接 关 系 ， 二者 构 成 一 个 有 机 的 整 体 ， 共 同 形 成 对 形 体 的 完 整 的 描述 。 有 了 几 何 信 息 和 拓 扑 信 息 ， 可 以 直 接 对 构 成 形 体的 各 个 面 、 边 、 顶 点 的 参 数 进 行 存 取 ， 有 利 于 以 面 、边 、 点 为 基 础 的 各 种 几 何 运 算 和 操 作 。 边 界 表 示 法 中 最 为 典 型 的 数 据 结 构 是 翼 边 结 构 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 17 在 以 表 面 、 棱 边 、 顶 点 组 成 形 体 的 三 要 素 中 ， 翼 边 结构 以 边 为 核 心 来 组 织 数 据 ,如 图 7所 示 。图 7 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 18 与 一 条 边 相 连 的 有 这 条 边 的 上 下 两 个 顶 点 ， 左 右 两 个 邻面 以 及 上 下 左 右 四 条 邻 边 。 棱 边 的 数 据 结 构 中 包 含 有 2个 顶 点指 针 ， 分 别 指 向 该 边 的 起 点 和 终 点 ， 每 一 个 顶 点 也 有 一 个 指针 ， 反 过 来 指 向 以 该 顶 点 为 端 点 的 边 。 棱 边 被 看 作 一 个 从 起点 指 向 终 点 的 有 向 线 段 ， 如 果 形 体 是 多 面 体 ， 其 棱 边 为 直 线段 ， 由 它 的 起 点 和 终 点 唯 一 确 定 。 当 形 体 为 曲 面 体 时 ， 其 棱边 可 能 为 一 曲 线 段 ， 这 时 必 须 增 添 一 项 指 针 来 指 向 所 在 曲 线边 的 数 据 。 此 外 ， 在 翼 边 结 构 中 还 设 有 两 个 环 指 针 ， 分 别 指向 棱 边 所 邻 接 的 两 个 表 面 上 的 环 。 由 这 种 边 环 关 系 就 能 确 定棱 边 与 相 邻 面 之 间 的 拓 扑 关 系 ， 为 了 能 从 棱 边 出 发 搜 索 到 所在 的 任 一 闭 环 上 的 其 它 棱 边 ， 数 据 结 构 中 又 增 设 四 个 指 向 边的 指 针 ， 它 们 分 别 是 左 上 边 、 左 下 边 、 右 上 边 、 右 下 边 。 如右 下 边 表 示 该 棱 边 在 右 面 环 中 沿 逆 时 针 方 向 所 连 接 的 下 一 条棱 边 ， 而 左 上 边 则 为 棱 边 在 左 面 环 中 沿 逆 时 针 方 向 所 连 接 的下 一 条 边 等 。 每 一 个 面 也 有 一 个 指 针 ， 反 过 来 指 向 它 的 一 条 边 。 通 过 这 种 翼 边 结 构 ， 可 以 方 便 地 查 找 各 元 素 之 间 的 连 接关 系 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 19 边 界 表 示 法 的 优 点 是 ， 表 示 形 体 的 点 、 边 、 面 等几 何 元 素 是 显 式 表 示 的 ， 比 较 容 易 确 定 几 何 元 素 间 的连 接 关 系 。 有 关 形 体 的 操 作 运 算 可 以 直 接 用 面 、 边 、顶 点 的 数 据 来 实 现 ， 使 得 绘 制 形 体 的 速 度 较 快 。 边 界表 示 法 的 缺 点 是 数 据 结 构 复 杂 ， 需 要 大 量 的 存 储 空 间 ，修 改 形 体 的 操 作 比 较 难 以 实 现 ， 对 实 体 的 整 体 描 述 能力 弱 。7.2.3 构 造 实 体 几 何 法 (CSG) 构 造 实 体 几 何 法 (Constructive Solid Geometry，CSG)， 是 在 实 体 的 表 示 、 构 造 中 得 到 广 泛 应 用 的 一种 方 法 。 它 的 基 本 思 想 是 将 简 单 几 何 形 体 （ 体 素 ）通 过 正 则 集 合 运 算 组 合 成 所 需 要 的 复 杂 实 体 。 因 此 ，这 种 方 法 称 为 构 造 实 体 几 何 法 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 20 1. 正 则 集 合 运 算 构 造 实 体 几 何 法 中 采 用 的 集 合 运 算 包 括 并 、 交 、 差 运算 ， 但 对 两 个 有 效 实 体 进 行 普 通 的 集 合 运 算 产 生 的 结 果并 不 一 定 是 有 效 实 体 ， 即 可 能 产 生 悬 边 、 悬 面 等 。 如 图8(a)所 示 , 设 二 维 平 面 上 有 物 体 A及 B， 将 它 们 如 图 8(b)所 示 的 位 置 作 交 运 算 。 如 果 以 通 常 的 集 合 运 算 规 则 求 ，则 得 到 图 8(c)中 的 结 果 ， 它 有 一 条 悬 边 ， 不 具 有 维 数 的一 致 性 ， 所 以 不 符 合 正 则 形 体 的 条 件 ， 不 是 有 效 的 二 维形 体 。 图 8(d)中 的 结 果 才 是 一 个 有 效 的 二 维 形 体 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 21 为 此 ， 把 能 够 产 生 正 则 形 体 的 集 合 运 算 称 为 正 则集 合 运 算 。 其 相 应 的 正 则 集 合 算 子 以 * (正 则 交 )、 * (正 则 并 )、 -*( 正 则 差 )表 示 。 首 先 ， 正 则 形 体 的 表 面 具 有 连 通 性 、 有 界 性 、 非 自相 交 性 、 可 定 向 性 和 闭 合 性 。 三 维 正 则 形 体 可 以 用 它的 边 界 面 及 内 部 来 表 示 ， 即 ： G=bG,iG 式 中 ， G为 正 则 形 体 ， bG为 G的 边 界 面 ， iG为 G的 内 部 。 在 三 维 空 间 中 ， 给 定 一 个 实 体 G后 ， 空 间 点 集 就 被分 为 三 个 子 集 ， 一 是 该 实 体 的 内 部 点 集 ， 二 是 该 实 体边 界 上 的 点 集 ， 三 是 该 实 体 之 外 的 点 集 。 若 给 定 一 个实 体 G及 一 个 有 界 面 S， 那 么 S也 可 能 被 G分 割 为 三 部分 ， 即 位 于 G内 的 面 ， 位 于 G外 的 面 以 及 位 于 G的 边 界上 的 面 。 以 C(S,G)表 示 这 三 种 关 系 ， P代 表 空 间 的 点 ，则 有 C(S,G)=S in G,S out G,S on G 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 22 其 中 S in G =P|PS,PiG S out G=P|PS,PG S on G =P|PS,PbG 由 于 实 体 G的 边 界 面 是 可 定 向 的 ， 有 界 面 S也 是 可 定向 的 ， 比 如 按 右 手 法 则 取 法 线 方 向 。 以 -S表 示 有 界 面 S的反 向 面 ， 即 -S和 S是 同 一 个 有 界 面 ， 只 是 有 界 面 -S上 任 何一 点 的 法 向 均 和 有 界 面 S上 该 点 的 法 向 相 反 。 也 就 是 说 ，如 有 界 面 S在 P点 的 法 向 为 NP(S)， 那 么 ， 有 界 面 -S在 P点 的法 向 就 是 -N P(S)。 同 样 -bG表 示 G边 界 面 的 反 向 。 于 是 可以 进 一 步 分 为 两 种 情 况 ： 有 界 面 S在 G边 界 面 上 同 为 正 向的 点 的 集 合 和 一 个 为 正 向 一 个 为 反 向 的 点 的 集 合 ， 即 S on G=S on(bG),S on(-bG) 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 23 其 中 S on (bG)=P|PS,PbG,Np(s)=Np(bG) S on (-bG)=P|PS,PbG,Np(s)=-Np(bG)因 此 ， C(S,G)可 以 修 改 为 C(S,G)=S in G, S out G,S on (bG),S on (-bG) 由 于 正 则 形 体 可 以 由 它 的 边 界 来 表 示 ， 得 到 了 它 的边 界 ， 也 就 定 义 了 该 形 体 。 设 A和 B为 两 个 正 则 形 体 ， 则正 则 集 合 运 算 算 子 定 义 如 下 b(A *B)=bA out B,B out A,bA on bB b(A *B)= bA in B,B in A,bA on bB b(A-*B)= bA out B,-(bB in A),bA on (-bB) 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 24 可 以 证 明 ， 通 过 上 面 定 义 的 正 则 集 合 算 子 运 算 后得 到 的 新 形 体 仍 为 正 则 形 体 ， 运 算 的 结 果 定 义 出 新 形体 的 边 界 。 最 后 一 式 中 -(bB in A)表 示 得 到 点 集 (bB in A)后 取 反 向 作 为 新 形 体 的 有 向 边 界 。 对 于 二 维 的 情 况 ， 其 形 体 的 边 界 由 直 线 段 或 曲 线构 成 。 运 算 是 指 两 边 界 线 走 向 相 同 的 部 分 ， bA on (-bB)是 指 两 边 界 线 走 向 相 反 的 部 分 。 仍 然 用 图 8的 例 子来 说 明 正 则 集 合 算 子 运 算 ， 其 结 果 如 图 9表 示 。 图 中 实线 表 示 运 算 后 所 生 成 的 新 形 体 边 界 。图 9 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 25 2 实 体 模 型 的 构 造 构 造 实 体 几 何 法 利 用 上 面所 述 的 正 则 集 合 运 算 ， 将 简 单几 何 形 体 (体 素 )组 合 成 所 需 要的 复 杂 实 体 。 在 这 一 方 法 中 ，常 用 的 体 素 有 长 方 体 、 圆 柱 体 、圆 锥 体 、 圆 台 体 、 环 、 球 和 封闭 样 条 曲 面 等 。 基 本 体 素 本 身可 用 建 模 算 法 、 扫 描 方 法 或 样条 方 法 构 造 形 成 。 图 10表 示 了用 构 造 实 体 几 何 法 形 成 新 的 实体 的 例 子 。 在 图 中 ， 两 个 不 同的 长 方 形 作 并 操 作 后 再 同 一 个圆 柱 体 作 差 操 作 ， 得 到 图 中 的实 体 。 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 26 在 实 体 构 造 过 程 中 ， 通 过 基 本 体 素 经 集 合 运 算 得到 新 的 形 体 ， 它 又 可 以 继 续 用 来 构 造 形 成 另 一 形 体 ，这 样 利 用 基 本 体 素 和 每 一 步 新 创 建 形 体 的 组 合 ， 不 断构 造 直 到 形 成 最 后 的 实 体 。 实 体 的 构 造 过 程 可 以 用 一棵 二 叉 树 （ 称 为 CSG树 ） 来 描 述 。 如 图 11所 示图 11 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 27 7.2.4 八 叉 树 表 示 法 八 叉 树 (Octrees)表 示 法 是 将 实 体 所 在 空 间 进 行 递归 划 分 ， 分 割 成 由 立 方 体 组 成 的 网 格 。 于 是 ， 一 个 实体 可 以 由 它 所 占 用 的 立 方 体 序 列 来 表 示 。 当 分 割 后 的立 方 体 越 来 越 小 时 ， 就 逐 步 接 近 用 空 间 点 的 集 合 来 表示 实 体 了 。 三 维 空 间 的 八 叉 树 表 示 方 法 是 二 维 空 间 四 叉 树（ Guadtree） 表 示 方 法 的 扩 展 。 四 叉 树 表 示 是 将 二 维区 域 递 归 细 分 成 小 方 域 为 基 础 的 ， 每 个 节 点 代 表 平 面上 的 一 个 小 方 域 。 如 图 12所 示 。图 12 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 28 三 维 空 间 的 划 分 描 述 使 用 八 叉 树 表 示 。 类 似 于 二 维空 间 的 四 叉 树 表 示 ， 八 叉 树 表 示 将 三 维 空 间 区 域 递 归 地划 分 成 8个 子 空 间 ， 图 13是 其 示 意 图 。 八 叉 树 表 示 的 每个 节 点 对 应 于 一 三 维 子 空 间 ， 这 种 表 示 方 法 可 以 提 供 形体 内 部 信 息 ， 便 于 形 体 截 面 显 示 的 应 用 需 要 。图 13 2021-5-2 计 算 机 图 形 学 演 示 稿 纪 玉 波 制 作(C) 29 一 旦 对 一 实 体 建 立 起 八 叉 树 表 示 ， 可 将 各 种 操 作应 用 到 该 实 体 。 比 如 对 一 个 八 叉 树 进 行 平 移 、 旋 转 和缩 放 等 几 何 变 换 ， 可 以 产 生 一 个 新 的 八 叉 树 。 对 同 一空 间 区 域 不 同 实 体 的 两 个 八 叉 树 表 示 ， 可 进 行 并 、 交 、差 等 集 合 运 算 ， 产 生 一 个 新 的 八 叉 树 。 用 八 叉 树 表 示 空 间 实 体 的 优 点 是 数 据 结 构 简 单 划一 ， 易 于 实 现 实 体 之 间 的 集 合 运 算 ， 易 于 计 算 实 体 的几 何 特 性 ， 由 于 具 有 层 次 结 构 ， 易 于 实 现 消 隐 。 但 这种 方 法 不 是 一 种 精 确 的 表 示 法 ， 其 近 似 程 度 完 全 取 决于 分 割 精 度 ， 与 几 何 形 体 的 复 杂 程 度 无 关 。 将 八 叉 树表 示 转 换 为 精 确 的 边 界 表 示 是 困 训 摹 谑 堤 逶 型 系 统中 ， 一 般 将 它 用 作 一 种 辅 助 表 示 形 式 。