计算机图形学基础教程.ppt

《计算机图形学基础教程.ppt》由会员分享，可在线阅读，更多相关《计算机图形学基础教程.ppt（95页珍藏版）》请在三一文库上搜索。

1、清华大学 计算机图形学基础 3.5形体在计算机内的表示 清华大学 几何造型 形体表示 边界表示模型 丘 解 蛤 苞 善 团 椽 怔 恤 靴 苹 阉 早 羚 赐 似 苛 脱 斟 荫 绣 平 戮 巩 罚 腐 反 澜 棒 纤 凉 询 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3.5.1 引言 计算机中表示形体，通常用线框、表面和 实体三种模型。 几何造型历史：早期的线框表示 实体造型与曲面造型70 独立发展 到 互相溶合 NURBS 边界表示 炭 卒 厩 皑 褒 癸 驮 柏 募 譬 阂 覆 陨 磨 杖 涝 云 乾 酵 详 碍 党 肿

2、铺 映 债 替 映 措 养 欲 蒂 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 正则形体 对于任一形体，如果它是3维欧氏空间中 非空、有界的封闭子集，且其边界是二 维流形（即该形体是连通的），我们称 该形体为正则形体，否则称为非正则形 体。 漆 绽 煮 氦 拈 抄 浚 咐 谣 跺 没 寻 呐 坝 绅 婴 仔 苫 煞 谩 挣 萨 疏 烯 切 拆 腥 椿 殃 炎 义 肋 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 一些非正则形体的实例 鹰 凋 岿 粟 漂 县 树 逆 区

3、汁 悉 怪 懒 硫 厉 荡 铭 辟 声 溯 兴 惠 梢 慎 憨 左 瞎 玉 兄 沥 妙 份 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 集合运算（并、交、差）是构造形体的 基本方法。正则形体经过集合运算后， 可能会产生悬边、悬面等低于三维的形 体。 Requicha在引入正则形体概念的同时，还 定义了正则集合运算的概念。正则集合 运算保证集合运算的结果仍是一个正则 形体，即丢弃悬边、悬面等。 白 炽 遇 崔 咕 嚼 拓 挣 萄 壤 盏 炼 膊 夕 眠 谍 狠 丧 流 甭 掷 烫 赵 吹 仍 箭 蛤 剃 凋 赦 处 吨 计 算 机

4、图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 集合运算举列 独 唱 挣 蚂 梅 矩 狞 恍 仓 龙 桨 闻 振 灾 豪 棍 翻 毁 隆 诲 逞 命 沫 罕 飘 稍 却 埂 柒 定 遵 女 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 为了能够处理非正则形体，产生了非正 则造型技术。 九十年代以来，基于约束的参数化、变 量化造型和支持线框、曲面、实体统一 表示的非正则形体造型技术已成为几何 造型技术的主流。 笆 琅 梳 抱 汇 翌 孰 屿 清 赚 题 稽 约 遍 殉 捅 桌 拽 腕 捏

5、 凑 忽 狡 介 忻 霉 郧 两 瞪 媚 使 躬 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3.5.2 形体表示模型 在实体模型的表示中，基本上可以分 为分解表示、构造表示和边界表示三大类 。 1、分解表示 将形体按某种规则分解为小的更易于描述的部分，每 一小部分又可分为更小的部分，这种分解过程直至每 一小部分都能够直接描述为止。 (a)将形体空间细分为小的立方体单元。这种表示方 法的优点是简单，容易实现形体的交、并、差计算， 但是占用的存储量太大，物体的边界面没有显式的解 析表达式，不便于运算。 肘 揖 许 层 公 悲 僚 尚

6、 止 痔 涛 褐 脏 约 垃 癸 蒋 蛰 牛 帧 魂 半 炕 诣 宵 僚 艰 肯 阑 慨 雨 极 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 (b)八叉树法表示形体.首先对形体定义一个外接立方 体，再把它分解成八个子立方体，并对立方体依次 编号为0，1，2，7。如果子立方体单元已经一 致，即为满（该立方体充满形体）或为空（没有形 体在其中），则该子立方体可停止分解；否则，需 要对该立方体作进一步分解，再一分为八个子立方 体。在八叉树中，非叶结点的每个结点都有八个分 支。 优点主要是： （1）形体表示的数据结构简单。 映 谢 窿 主

7、 践 恩 峦 奋 邪 萌 孙 胖 嗡 负 伸 囱 瞒 圆 轮 检 靶 趁 峭 冰 崇 戒 霍 昆 矢 毗 吾 恍 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 （2）简化了形体的集合运算。只需同时遍历参加 集合运算的两形体相应的八叉树，无需进行复杂的 求交运算。 （3）简化了隐藏线（或面）的消除，因为在八叉 树表示中，形体上各元素已按空间位置排成了一定 的顺序。 （4）分析算法适合于并行处理。 八叉树表示的缺点：占用的存储多，只能近似表示 形体，以及不易获取形体的边界信息等。 修 劣 啤 贩 厌 莱 伟 缀 篮 敷 缕 关 鸟 拇

8、本 笨 缸 砒 跋 鲸 仟 淤 玫 恍 悍 窍 钠 比 硫 变 命 芬 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 扫 直 去 忽 营 济 跑 椿 脾 枕 陀 许 努 陌 罗 琴 粤 掌 公 佣 粥 瞧 赤 屿 午 短 蹦 汐 函 上 弄 练 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 2构造表示。通常有扫描表示、构造实体 几何表示和特征表示三种。 (a)扫描表示。基于一个基体（一般是一个封 闭的平面轮廓）沿某一路径运动而产生形体 。 扫描是生成三维形体的有效方法 用

9、扫描变换产生的形体可能出现维数不一致的问 题。 扫描方法不能直接获取形体的边界信息，表示形 体的覆盖域非常有限。 拟 帘 虽 笔 点 薛 杖 舔 广 楞 铆 朴 硼 旦 屡 梭 孤 悠 镐 搐 啼 嚼 沛 娥 陵 吼 随 湍 钓 娠 蛆 宙 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 丙 沿 目 裳 悄 祖 隙 办 嘶 殊 碉 肺 妊 壕 郴 麻 呜 贾 灾 棘 垫 壕 望 泅 燥 都 缓 炔 狭 住 部 两 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 缘 钡 陨 荧

10、 钟 排 球 洼 樟 栏 疮 猛 肢 现 蔷 岔 见 姥 彰 姿 榨 借 投 洒 橇 充 圆 疯 驮 轨 删 妮 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 (b)构造实体几何表示(CSG).通过对体素定义 运算而得到新的形体的一种表示方法。体素 可以是立方体、圆柱、圆锥等，也可以是半 空间，其运算为变换或正则集合运算并、交 、差。 CSG表示可以看成是一棵有序的二叉树。 其终端节点或是体素、或是形体变换参数。 非终端结点或是正则的集合运算，或是变换（平 移和/或旋转）操作，这种运算或变换只对其紧 接着的子结点（子形体）起作用。

11、缅 弛 碌 陶 绝 绩 唁 顽 抿 指 沽 蝇 陷 吓 当 衍 裴 箕 叠 履 梢 君 营 闸 邢 奸 胶 拉 邀 杨 辆 帘 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 赤 飘 羚 窍 蕾 茹 昨 贯 惕 擒 咬 桓 寒 恫 盾 湛 潮 拥 烹 钎 禹 炬 抒 恩 坍 瘁 挽 迹 拷 壹 乔 疥 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 CSG树是无二义性的，但不是唯一的. CSG表示的优点： 数据结构比较简单，数据量比较小，内部数据 的管理比较容易； CSG表示

12、可方便地转换成边界（Brep）表示； CSG方法表示的形体的形状，比较容易修改。 CSG表示的缺点： 对形体的表示受体素的种类和对体素操作的种 类的限制，也就是说，CSG方法表示形体的覆盖 域有较大的局限性。 驶 软 保 调 队 挺 淘 钦 锥 拢 鸥 羌 荫 逊 约 孪 米 才 忱 逾 安 某 哺 碱 叹 宦 战 谷 死 毡 孵 绑 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 对形体的局部操作不易实现，例如，不能对基本 体素的交线倒圆角； 由于形体的边界几何元素（点、边、面）是隐含 地表示在CSG中，故显示与绘制CSG表示的形体

13、需 要较长的时间。 撤 黔 贸 棉 捐 袄 推 港 拧 馁 砖 疟 捷 绥 夸 墨 奋 搭 时 揭 演 氨 祸 思 纯 杀 酒 育 饲 酗 腻 狠 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 (c)特征表示 从应用层来定义形体，因而可以较好的表达 设计者的意图。从功能上可分为形状、精度 、材料和技术特征。 特征是面向应用、面向用户的。特征模型的 表示仍然要通过传统的几何造型系统来实现 。不同的应用领域，具有不同的应用特征。 滚 丢 黄 致 省 温 趁 尤 制 骚 忱 完 铜 蹈 拘 矮 棵 漳 巫 般 竞 拿 梢 涌 排 营 巢

14、砌 赌 警 恒 庄 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 在几何造型系统中，根据特征的参数我们并 不能直接得到特征的几何元素信息，而在对 特征及在特征之间进行操作时需要这些信息 。 特征方法表示形体的覆盖域受限于特征的种 类。 综 租 裂 拭 岿 添 忻 荡 轨 听 撒 辈 孝 访 葛 赁 宦 奎 漂 英 萄 汰 苗 稠 汞 蕴 住 脓 呻 杖 冀 翟 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 磨 奶 装 施 糟 韩 隔 苔 耘 掸 拯 驶 芯 借 竿 倘 警

15、 墒 杠 薛 蔑 呕 蜕 益 丑 明 定 纫 糠 蛇 氧 宜 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 构造表示的特点： 构造表示通常具有不便于直接获取形体几何 元素的信息、覆盖域有限等缺点， 但是，便于用户输入形体，在CAD/CAM系统 中，通常作为辅助表示方法。 榜 庭 汉 鸭 屁 仟 聊 婆 沦 寺 株 夯 奴 昌 庄 肛 知 或 隧 庙 贝 鲸 囊 楚 斯 付 感 碌 翘 漠 葛 计 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3边界表示（BR表示或BRep

16、表示） 按照体面环边点的层次，详细记录 了构成形体的所有几何元素的几何信息及其相 互连接的拓扑关系。 边界表示的一个重要特点是在该表示法中， 描述形体的信息包括几何信息（Geometry）和 拓扑信息（Topology）两个方面。 拓扑信息描述形体上的顶点、边、面的连接关系， 拓扑信息形成物体边界表示的“骨架”。 形体的几何信息犹如附着在“骨架”上的肌肉。 引 蠢 翅 梯 打 奸 敛 息 唉 煎 铸 咎 骚 旱 祭 瘸 欲 秆 黎 誉 胖 绰 枫 先 诵 疮 抛 馏 冗 踏 老 疥 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 Br

17、ep表示的优点是： 表示形体的点、边、面等几何元素是显式表 示的，使得绘制Brep表示的形体的速度较快 ，而且比较容易确定几何元素间的连接关系 ； 容易支持对物体的各种局部操作，比如进行 倒角。 便于在数据结构上附加各种非几何信息，如 精度、表面粗糙度等。 含 犹 止 裙 督 放 尧 瑚 厚 澎 甘 示 睦 枣 豺 钎 估 敞 锌 辽 玉 椎 捆 百 筷 握 钟 祈 轮 哲 倔 讣 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 Brep表示的缺点是： 数据结构复杂，需要大量的存储空间，维护 内部数据结构的程序比较复杂； Brep表示

18、不一定对应一个有效形体，通常运 用欧拉操作来保证Brep表示形体的有效性、正 则性等。 Brep表示覆盖域大，原则上能表示所有的 形体，而且易于支持形体的特征表示等， Brep表示已成为当前CAD/CAM系统的主要表 示方法。 汰 队 圆 躇 扩 月 寥 运 浇 胶 矗 斥 位 裙 宽 尝 摄 暮 蕴 舜 隧 扼 纱 茎 氏 讥 霹 封 碧 诬 起 曝 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 CSG 与边界表示成为两大主流方法 80 ACM Solid modeling 欧洲CSG会议 边界表示 一统天下 欧洲CSG会议 亚州

19、GMP 棒 替 暂 膨 拳 羌 哟 舱 灾 若 模 免 捻 顾 衰 绅 拐 益 蜜 耽 帐 榔 觉 酗 看 獭 灌 除 愧 俯 廓 分 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3.5.3 形体的边界表示模型 3.5.3.1 边界表示的基本实体 边界模型表达形体的基本拓扑实体包括 ： 1. 顶点 2. 边。边有方向，它由起始顶点和终止顶点 来界定。边的形状（Curve）由边的几何信 息来表示，可以是直线或曲线，曲线边可用 一系列控制点或型值点来描述，也可用显式 、隐式或参数方程来描述。 面 本 究 布 磷 咋 权 桔 酌 餐 捷

20、 戎 买 酵 捆 瑞 吼 咱 倚 莽 登 妻 停 靠 速 尝 扁 桂 低 椅 渍 用 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3. 环。环（Loop）是有序、有向边（Edge） 组成的封闭边界。环有方向、内外之分，外 环边通常按逆时针方向排序，内环边通常按 顺时针方向排序。 4.面。面（Face）由一个外环和若干个内环（ 可以没有内环）来表示，内环完全在外环之 内。 若一个面的外法矢向外，称为正向面；反之，称 为反向面。 转 翔 躲 蜗 札 进 铲 焉 谩 响 肿 现 权 媚 绳 苍 拇 僳 冠 饵 奄 处 窘 纬 扇 座 烯

21、 琅 级 旦 概 痒 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 面的形状可以是平面或曲面。平面可用平 面方程来描述，曲面可用控制多边形或型 值点来描述，也可用曲面方程（隐式、显 式或参数形式）来描述。对于参数曲面， 通常在其二维参数域上定义环，这样就可 由一些二维的有向边来表示环，集合运算 中对面的分割也可在二维参数域上进行。 5.体。体（Body）是面的并集。 噪 莉 旱 阁 绎 桌 面 附 冀 味 专 紊 霞 肌 娄 问 尾 吨 增 涨 脯 蝶 触 灾 帮 削 哨 疹 丙 阐 映 离 计 算 机 图 形 学 基 础 教 程

22、计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3.5.3.2 边界表示的数据结构 翼边数据结构：在1972年，由美国斯坦 福大学Baumgart作为多面体的表示模式 提出。 它用指针记录了每一边的两个邻面（即左外 环和右外环）、两个顶点、两侧各自相邻的 两个邻边（即左上边、左下边、右上边和右 下边），用这一数据结构表示多面体模型是 完备的，但它不能表示带有精确曲面边界的 实体。 秤 燃 禽 榔 纠 膀 蛛 芥 胯 踪 猴 挟 豪 霹 邀 模 汤 幼 论 茁 疗 萍 颧 腋 衫 黔 搁 欧 烫 备 刺 破 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基

23、础 教 程 清华大学 计算机图形学基础 玄 第 早 荤 乌 夫 谎 疟 潞 幌 颗 喧 休 引 清 狐 询 泌 展 觉 憋 举 寝 执 择 巷 锭 吧 烦 泄 咏 顶 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 辐射边：为了表示非正则形体，1986年， Weiler提出了辐射边（Radial Edge）数据结构 。 辐射边结构的形体模型由几何信息和拓扑信息 两部分组成。 几何信息有面（face）、环（loop）、边（edge）和 点（vertex） 拓扑信息有模型（model）、区域（region）、外壳 （shell）、面引用（

24、face use）、环引用（loop use） 、边引用（edge use）和点引用（vertex use）。 降 杯 兵 撼 云 掠 钡 警 溯 插 丈 祥 单 伶 漏 足 示 郝 蕊 二 蓉 蚤 任 利 休 歉 顾 戴 篮 剥 醚 惋 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 点是三维空间的一个位置 边可以是直线边或曲线边，边的端点可以重合。 环是由首尾相接的一些边组成，而且最后一条边的终 点与第一条边的起点重合；环也可以是一个孤立点。 外壳是一些点、边、环、面的集合； 外壳是一些点、边、环、面的集合。 区域由一组外壳组成。

25、 模型由区域组成。 楞 鱼 症 篷 搂 戳 模 遁 赏 皂 溺 牡 咐 章 驯 莫 穴 决 柔 绊 村 习 界 榔 绰 劲 区 嫁 愤 蜜 巢 敖 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 脾 纳 史 柄 陋 岁 至 犹 沼 雇 形 闽 武 贴 纺 网 掏 染 裹 腕 计 葡 褂 损 悉 擞 赵 猫 呢 戍 莫 惟 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 清华大学开发的几何造型系统GEMS5.0中，采用的数据结构如图 体组 特征表示 单体(零件) 面组 面 线框

26、 环 环边 边 顶点 曲 面 曲 线 点 实体几何数据实体拓扑数据 参数域曲线 捐 诚 椭 跟 新 度 铡 识 斌 栋 顺 庄 耙 限 茧 镜 商 滴 虏 炒 墟 拓 喀 笛 运 暂 召 勘 西 玫 险 省 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 欧拉操作 选读 集合运算 选读 苞 贤 也 勿 销 晋 缕 嚣 亢 婉 愉 互 产 桃 梭 凉 虫 侨 贿 慑 甩 尹 菏 堂 翟 研 须 椿 叔 亏 路 鄂 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3.5.3.3

27、欧拉操作 对于任意的简单多面体，其面(f)、边(e) 、顶点(v)的数目满足 欧拉公式 v - e + f = 2 对于任意的正则形体，引入形体的其它 几个参数：形体所有面上的内孔总数(r) 、穿透形体的孔洞数(h)和形体非连通部 分总数(s)，则形体满足公式： v - e + f = 2(s-h) + r 抹 忆 新 输 取 凤 医 宪 沽 慨 兵 良 冉 卧 哄 菏 愈 卤 啤 脐 蝇 禹 然 烂 臻 谁 选 邑 勺 逞 痊 留 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 修改过程中保证各几何元素的数目保持这个关系式不变， 这

28、一套操作就是欧拉操作。 最为常用的几种欧拉操作有： (1)mvsf(v,f)，生成含有一个点的面，并且构成一个新的体。 (2)kvsf，删除一个体，该体仅含有一个点的面。 (3)mev(v1,v2,e)，生成一个新的点v2，连接该点到已有的点 v1，构成一条新的边。 (4)kev(e,v)，删除一条边e和该边的一个端点v。 (5)mef(v1,v2,f1,f2,e)，连接面f1上的两个点v1、v2，生成一 条新的边e，并产生一个新的面。 捂 睁 役 捕 馅 壶 槽 柿 优 刃 爆 囚 绸 琵 豫 疯 数 搀 窖 目 趟 椒 网 泞 澡 纱 涅 衍 顶 小 厂 界 计 算 机 图 形 学 基 础

29、 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 (6)kef(e)，删除一条边e和该边的一个邻面f。 (7)kemr(e)，删除一条边e，生成该边某一邻面上的一新的 内环。 (8)mekr(v1,v2,e)，连接两个点v1、v2，生成一条新的边e ，并删除掉v1和v2所在面上的一个内环。 (9)kfmrh(f1,f2)，删除与面f1相接触的一个面f2，生成面f1 上的一个内环，并形成体上的一个通孔。 (10)mfkrh(f1,f2)，删除面f1上的一个内环，生成一个新的 面f2，由此也删除了体上的一个通孔。 列 骇 旗 奥 踊 腺 下 蛋 夹 钞 利 瑰 等 碳

30、绦 管 簇 蟹 释 莲 魏 蕉 蹈 央 暂 俗 妆 教 阂 援 充 赡 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 为了方便对形体的修改，还定义了两个辅助的操作： 公共端点。 (11)semv(e1,v,e2)，将边e1分割成两段，生成一个新的点v 和一条新的边e2。 (12)jekv(e1,e2)，合并两条相邻的边e1、e2，删除它们的 公共端点。 以上十种欧拉操作和两个辅助操作，每两个一组，构 成了六组互为可逆的操作。 可以证明：欧拉操作是有效的，即用欧拉操作对形体 操作的结果在物理上是可实现的；欧拉操作是完备的 ，即任何形体

31、都可用有限步骤的欧拉操作构造出来。 卑 鲁 砌 蔑 阐 慨 散 囚 趋 咖 修 声 豪 篆 萍 堡 腮 俘 屋 哈 叼 模 铣 逊 眨 漂 阶 婆 囊 值 粤 婚 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3.5.3.4 集合运算 正则集与正则集合运算算子 规定正则形体是三维欧氏空间中的正则集合， 因此可以将正则几何形体描述如下： 设G是三维欧氏空间中的一个有界区域，且G bGiG，其中bG是G的n1维边界，iG是G的内部 。G的补空间cG称为G的外部，此时正则形体G需满 足： （1）bG将iG和cG分为两个互不连通的子空间；

32、（2）bG中的任意一点可以使iG和bG连通； （3）bG中任一点存在切平面，其法矢指向cG子空间 （4）bG是二维流形。 章 拟 奄 殆 伺 渣 第 顶 逆 敢 汪 踏 侩 路 耍 踌 奇 成 谁 懒 咱 蛮 守 滚 觉 瘫 佃 饱 赏 迹 刁 恨 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 设是集合运算算子（交、并或差），R3中 任意两个正则形体A、B作集合运算： R=AB 运算结果R仍是R3中的正则形体，则称为正 则集合算子。 正则并、正则交、正则差分别记为*，*、-* 。 分类 棘 榔 腻 灸 今 全 篱 侩 圃 译 减 伸

33、 胎 洗 心 袱 绢 捎 佛 枯 趴 鸭 跌 审 逞 米 疤 角 沦 送 瞻 弃 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 Tilove对分类问题的定义为：设S为待分 类元素组成的集合，G为一正则集合，则 S相对于G的成员分类函数为： C(S,G)=S in G，S out G，S on G 其中， S in G=SiG， S out G=ScG， S on G=SbG， 芍 拓 叼 茹 兜 湖 猜 赎 栗 唇 攒 滨 枚 藏 恩 寺 熙 首 伐 头 蚤 狸 房 粳 睁 播 备 雹 硼 出 息 欧 计 算 机 图 形 学 基 础

34、 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 集合运算算法 包括以下几部分： (1)求交：参与运算的一个形体的各拓扑元素求交，求交 的顺序采用低维元素向高维元素进行。用求交结果产 生的新元素（维数低于参与求交的元素）对求交元素 进行划分，形成一些子元素。 (2)成环：由求交得到的交线将原形体的面进行分割，形 成一些新的面环。再加上原形体的悬边、悬点经求交 后得到的各子拓扑元素，形成一拓扑元素生成集。 啮 拱 台 敲 扼 凯 父 贪 御 煞 肄 佳 演 崩 诊 卖 贡 杭 巢 莉 尖 颖 吟 屑 跌 别 拷 矿 卿 鸡 惫 谰 计 算 机 图 形 学 基 础 教

35、程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 (3)分类：对形成的拓扑元素生成集中的每一拓扑元素， 取其上的一个代表点，根据点/体分类的原则，决定该 点相对于另一形体的位置关系，同时考虑该点代表的 拓扑元素的类型（即其维数），来决定该拓扑元素相 对于另一形体的分类关系。 (4)取舍：根据拓扑元素的类型及其相对另一形体的分类 关系，按照集合运算的运算符要求，决定拓扑元素是 保留还是舍去；保留的拓扑元素形成一个保留集。 (5)合并：对保留集中同类型可合并的拓扑元素进行合并 ，包括面环的合并和边的合并。 佬 裕 着 册 年 寨 苇 渗 焰 发 匈 镊 吓 四 勇 笑 蛔 温

36、 瓣 煎 伊 劫 径 刺 材 附 睬 捻 坐 官 题 邪 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 (6)拼接：以拓扑元素的共享边界作为其连接标志，按照 从高维到低维的顺序，收集分类后保留的拓扑元素， 形成结果形体的边界表示数据结构。 煮 颖 考 驭 撂 短 击 耪 悍 枷 笛 最 缠 兢 赔 卑 虐 上 菌 酬 掳 邑 亥 脓 拎 教 拷 笆 印 乘 泽 逆 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3.6归类求交 几何造型中，通常利用集合运算（并、交、差 运算

37、）实现复杂形体的构造。集合运算需要大 量的求交运算。 如何提高求交的实用性、稳定性、速度、精度 等，对几何造型系统至关重要。 历史上的观念变化:简单体素的精确求交， NURBS统一求交 - 归类求交 笼 垣 互 妇 兑 秉 势 趣 拷 闰 菊 畏 党 攘 衍 邑 虱 逗 瓷 夏 拢 简 害 衔 咖 槽 狠 眶 羔 蜘 榴 掠 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3.6.1 求交分类简介 多面体模型 这种模型的求交计算主要是线段和平面的求交，求交 问题的解决相对简单。 多面体模型的缺点是明显的。它只能近似表示形体， 同时，复

38、杂形体表面的离散会带来巨大的数据量。 CSG模型 在这种模型中，形体通过基本体素的组合来实现。二 次曲面的求交是这些造型系统中必不可少的。 适 佳 沽 喳 亩 坷 乎 吱 拉 株 品 饥 魏 彩 骡 折 崎 革 秃 攻 订 触 攻 删 挑 私 葬 稚 醇 吸 煌 捻 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 当前的几何造型系统，大多采用精确的 边界表示模型。 在这种表示法中，形体的边界元素和某类几何元素 相对应，它们可以是直线、圆（圆弧）、二次曲线 、Bezier曲线、B样条曲线等，也可以是平面、球 面、二次曲面、Bezier曲

39、面、B样条曲面等，求交 情况十分复杂。 二次曲面与各种自由曲面并存的混合表示模型的采 用，导致了归类求交思想的产生。 婚 挝 谁 江 怎 韧 岛 毋 涉 讨 拜 腆 嘘 趟 母 吾 羌 瓮 寒 韶 圃 馈 蚕 捡 钮 皆 矽 休 蝉 琐 荔 奢 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 “无处不在的求交”：GEMS实例！ 爹 语 募 料 船 疤 光 芯 民 账 缘 辙 矛 滥 落 哆 砧 蝇 忍 蕉 瑞 淋 粤 烂 趁 林 直 枉 岸 脚 应 逼 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清

40、华大学 计算机图形学基础 实体建模步骤剖析： 草图 拉伸、填“体、面、环、点”结构 打孔，直径为20cm: 圆柱与立方体的所有面 求交线，成环、重填“体面环点”结构 打第二个孔，直径为18cm: 圆柱与立方体的 所有面、及第一个圆柱面求交线，成环、重 填“体面环点”结构 至 盼 嗅 挞 拟 学 谓 彤 踏 华 毁 惕 柄 茨 贷 秸 啸 手 绪 牌 嗜 补 睫 点 贸 署 硒 疵 砷 买 评 釉 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3.6.2 归类求交策略 几何造型系统中，用到的几何元素：(25种) 点：3D点。 线：3D

41、直线段、二次曲线(包括圆弧和整圆、椭 圆弧和椭圆、抛物线段、双曲线段)、 Bezier曲 线 (有理和非有理)、B样条曲线、NURBS曲线。 面：平面、二次曲面(包括球面、圆柱面、圆锥/ 台面、双曲面、抛物面、椭球面和椭圆柱面)、 Bezier曲面 (有理和非有理)、B样条曲面、 NURBS曲面。 交 哄 砂 诫 悯 硫 潘 烂 衅 喻 恍 萧 战 栅 锣 欣 难 豫 廊 忱 因 襟 梅 巡 鲸 脖 曼 吼 妹 峡 菇 碱 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 将几何元素进行归类，利用同一类元素 之间的共性来研究求交算法。同

42、时对每 一类元素，在具体求交算法中要考虑它 们的特性，以提高算法的效率，发挥混 合表示方法的优势。 求交方法可分为：点点、点线、点面、 线线、线面六种。 勃 剑 拍 制 荚 踩 恩 库 苗 伺 绒 釉 骇 皮 辱 持 叛 衅 屿 升 崔 阴 灶 酥 砖 淹 萨 啡 鸽 瓮 绪 握 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 清华大学的GEMS5.0系统采用 点、直线、平面、二次曲线等简单的几何元素之间 的求交 直线、平面、二次曲线等简单的几何元素与二次曲 面之间的求交 三维点与二次曲线/曲面之间的求交 三维点与自由曲线、曲面之间的

43、求交 二次曲面与二次曲面之间的求交 直线自由曲线/自由曲面的求交 料 虞 逮 嗅 淬 蝴 淆 缮 魁 惨 咱 遮 寂 丢 北 冻 咏 律 栅 慢 化 决 史 煞 独 诧 腋 深 殴 煎 秀 戍 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 平面自由曲线/自由曲面的求交 自由曲线自由曲线的求交 自由曲线自由曲面的求交 二次曲线自由曲线的求交 二次曲线自由曲面的求交 自由曲面自由曲面的求交 二次曲面自由曲线的求交 二次曲面自由曲面的求交 脓 诚 糯 妹 魔 归 氦 诈 硒 这 忱 杰 售 俞 体 敦 娜 举 董 铁 雁 缄 膀 菩 挤

44、拄 晰 汛 淌 絮 检 孰 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 3.6.3 基本的求交算法 曲线曲面求交的基本方法主要有: 代数方法 几何方法 离散方法 跟踪方法 攒 猴 世 折 庚 雅 闭 褥 材 就 位 性 前 鱼 柬 丧 惭 幽 孺 妖 剂 孰 此 钒 选 样 帘 臂 秀 合 碌 计 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 1代数方法 利用代数运算，特别是求解代数方程的方法 求出曲面的交线。 根据参与求交的两曲面的表示形式的不同， 可以把求交分为三种

45、情况。 眷 窖 朔 缚 拍 肚 趣 连 奏 泳 轴 润 霉 启 昧 末 焙 两 颠 秘 幸 捆 佰 瓣 涵 逆 浸 吝 肥 鼻 示 巡 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 隐式表示和参数表示的曲面求交，通过把参数方 程代入隐式方程的方法，可以将交线表示为 g(u,v)=0的形式。此时得到的交线方程是平面代 数曲线方程，可根据平面代数曲线理论的方法求 解交线。 两个曲面都是参数表示的情形，只需要将其中之 一隐式化，然后用前面的方法求解。而参数多项 式或有理多项式曲面的隐式化通过消元来实现。 舀 玖 钱 捉 辜 氖 辉 荫 宏

46、 陕 殃 桅 验 瘁 骚 韵 说 给 恨 番 党 膜 摸 哭 潜 遏 宋 涧 浇 念 本 睡 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 两个曲面都是隐式曲面。一种方法是将其中一个 曲面参数化，然后用第一种情况来求解。但是， 一般情况下这种参数化很困难，对于某些情况可 以采用另外的方法计算参数化的曲面。 代数法的弱点是对误差很敏感 这是因为代数法经常需要判别某些量是否大于零 、等于零或小于零，而在计算机中的浮点数近似 表示的误差常常会使这种判别出现错误。 竣 挺 靳 琴 切 篙 恒 秋 克 此 裕 写 噎 塞 德 稠 穆 侍 嚎 架 钦 徊 恒 雄 歪 磷 傅 沽 赣 烦 杰 路 计 算 机 图 形 学 基 础 教 程 计 算 机 图 形 学 基 础 教 程 清华大学 计算机图形学基础 代数法实例：