Bezier曲面的适应性细分和三角形化的四叉树方法

年第 期 计算机辅助设计与图形学学报 曲面的适应性细分和三角形化的 四叉树方法 姚承第 苏州丝拥工学院计算机中心 , 趾 。。 摘要 计葬机生成具有浓淡的参数 曲 面的方法之一是先对 曲 面进行适应性细分 , 并对所得到 、 的 曲 面细分三 角形化 , 得到曲 面的三 角形 网 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示 , 从而 可 以对每个三 角形施行通常的浓淡处理葬 法 。 本文介绍 了适应性细分双三次 曲 面的方法及 曲 面细分的四叉树表示 , 在此基础止给 出 了一个将 曲 面细分三 角形化的葬法 该葬法防止 了由 于适应性细分而可能产生的 曲 面上的裂缝 。 关性词 计算机图形学 , 算法 , 参数曲面 , 四叉树 , 三角形化 一 己 自、 二 二 参数曲面在计算机图形学和计算机辅助设计中具有广泛的应用 参数曲面 由三个二元函数来 定义 一 , 一 , , 其中 , 为参数 , 它们在 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 化后在 与 之间变化 。 这些由数学 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 定义的曲面的形状通常具 有连续性与光顺性的良好性质 如何用计算机显示这些 曲面 已经为许多人所研究 〔川给 出了直接从双三次曲面的数字描述来显示这种曲面的第一个算法 他的算法递归地将一个曲面片 分割成四个子曲面片 , 直到子曲面片的大小约为光栅显示设备的一个象素为止 这个方法使得隐 面消除和浓淡处理都简化了 继之 , 人们设计了许多计算机显示参数曲面的算法 〔, · ’, , ‘ , ‘ , ” , , 而 递归地细分曲面片则是这些算法的第一步 当一个子曲面片在递归细分过程中被判定为在给定的 误差 允 许 限 度 内是 局 部 平 坦 时 , 即停 止 对 它 的进 一 步 细 分 , 称 作 适 应 性 细 分 这些局部平坦的子曲面片可以用四边形来近似 通常为了便于进行浓淡处理 , 这些 平坦的子曲面片又被分割成落干个三角形 , 这个过程称作曲面细分的三角形化 。。 。 。 于是曲面被表示成一个三角形 网 由于三角形为最简单的平面多边形 , 常用的平面 多边形浓淡处理的方法可应用于每个三角形 。 这些算法一般地减少了曲面分割的次数 , 并且易子 进行反混淆 的处理 。 基于适应性细分的曲面显示算法中的一个典型问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 是有可能判定一个子曲面片平坦了 , 而对 其相邻的子曲面片则需要进一步细分 , 这就使得在曲面上可能出现裂缝 见图 裂缝间 题已为许多人所研究〔, ·‘ , ‘ , ” , ‘。 , 并且可以通过适当的三角形化方法来解决 和 ‘幻 给出了一个避免裂缝的十分漂亮的算法 在他们的算法中 , 四叉树 被用来表示 曲面递 归细分的层次结构 四叉树的根代表原曲面片 , 它在参数空间被分割成四个子曲面片 , 从而根结 点有四个子结点 , 如果一个子曲面片不是平坦的 , 或者尽管它 已是平坦的 , 但它有一个相邻的子 曲面片在细分的四叉树表示中比它低两个或两个以上的层次 , 则这个子曲面片继续被分割 。 即对 本文于 年 月收到 姚承弗 , 年生 , 年毕业于南京大学计算机科学系 , 年获中国纺织大学硕士学位 , 讲 师 , 主要研究领城为计算机图形学 、 计算机辅助几何设计和计算几何 。 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 应的四叉树结点又生出四个子结点 , 四叉树的叶结点对应于那些无箱继续分割的平坦的子曲面 片 。 对应这样的细分规则所得到的四叉树称作受限 四叉树 受限四叉树的方 法可以平缓地改变在参数曲面上的采样叔率 , 从而减小适应性细分时采样撅率的改变而可能 造成的曲面形状的失真 由于四叉树保留了平 坦的子曲面片之间相邻关系的信息 , 所以在将 一个平坦的子曲面片进一步分侧成三角形时可 以根据其相邻的曲面片的分侧情况而淮免在其 图 由于细分造成的裂缝 边界处出现裂缝 在受限四叉树的方法中 , 每个平坦的子曲面片沿其每条边分割出一个或两个三 角形 如在这条边的另一侧的平坦的子曲面片在四元树中比它高一个层次 , 则沿着这条边生成一 个三角形 否则生成两个三角形 。 图 表示在受限四叉树方法下一个适应性曲面细分如何转化为 三角形网的 。 注意 , 在这里可能出现的裂缝也被进免 。 扣卜 匕 口口口口口 匕 口口口口口 冈冈冈冈冈 美美美米米米米试试试试 图 曲面细分三角形化的受限四又树方法 尽管受限四叉树的方法可以产生较精确的曲面细分因而得到较好的曲面近似 , 但它似乎产生 了过多的三角形 , 从而增加了浓淡处理时的计算 并且 , 维护一裸受限四叉树在时空上均比维 护普通的四叉树来得娜贵 本文先根据 和 〔, 。的算法介绍适应性细分 曲 面 〔, , ”的方法 , 在此基础上给出一个应用普通四叉树将曲面细分三角形化而避免产生裂缝的算法 算法沿着平坦的子曲面片的每一条边 , 通过递归地查看该边另一侧的同层次的或较低层次的子曲 面片直至对应于叶结点的平坦的子曲面片来生成一个或多个三角形 由于使用了普通的四叉树 , 降低了递归细分的时空开梢 , 三角形化后生成较少的三角形但仍能得到较好的曲面近似 。 另一方 面 , 三角形化算法也遴免了裂桂的产生 。 二 、 曲面的递归细分 认 曲钱和曲面的分创 和 在文献 〔 〕中基于细分定理 给出 曲线和曲 面进归细分的方法 。 这里筒单介绍分侧三次 泛幼 曲线和双三次 幼 曲面的方法 。 设 , 《 《 , 是一条三次 曲线 , 科 , , , , , 是 的四个控侧点 。 记 代六 , 巩代 , 盆 的中点分别为 受, 界 和 孟, 盆是 受毛的中点 , 经是 毛 , 的中点 , 砚 是 玲 护的 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 二 · 中点 , 则 弓是 在 冬处的分割点 图 表示分割点的获得 有意义的是根据细分定理知了 ” 一 一 、 一 ‘ 一 一 产一 叨 产 一 , 奋 ’ , , ’ 一 一 一 , 尹 , 曰 心 , ’一 , , 妞 , , 二 ‘ , 尹 、 ”心 甲曰 一 ‘ , 一 一 产 ’ 一 被分割后的前半部分是由 、 、 盖和 孟作为控制点生成的三次 曲线 , 而后半部分则是 由 聋、 乳 二和 雪作为控制点生成的三次 曲线 我们将上述从原来的四个控制点产生两组 新的控制点的过程称为曲线分裂操作 注意 , 产生的第一组控制点中的最后一个点同时是第二组 控制点中的第一个点 , 即原曲线在参数空间的中点 不难将上述的曲线分裂操作推广到双三次 曲面 。 双三次 曲面 , , 成 , 《 , 由一个 的控制点阵列护 , 生成 。 等 参 数曲线 , 专和 专 , 将原曲面片分割 成四个子 曲面片 , 它们又分别是双三次 曲面片 。 曲面分裂操作从原来的 控制点阵 列得到与四个子曲面片相对应的四个 控制 点阵列 。 其处理过程如下 首先对原控制点阵 列的每一列实施曲线分裂操作 , 从而得到 “ 穿 一 。 ” 罗 图 三次 曲线的分割 的控制点阵列 然后对这个 的阵列的每一行实施 曲线分裂操作 , 得到 的控制点阵列 , 这个 的阵列被分为四个 的子阵列 , 如图 所示 。 分裂每一列 扣卜 勺浏 口 忆忆 、日 枯 忆忆 〕 〕 、、 产卜 尸、 厂厂、 产卜 产卜 厂厂夕夕 咭护 、奋 七七 目 目 气气 〕〕 〕 〕〕 〕 、、 厂、 尸、 厂厂、 凸 乃 图 对 控制点阵列施行的曲面分裂操作 「 平坦性检验和适应性细分 从上面讨论的 曲线和曲面分割的算法不难看出 , 曲线和曲面的分割可以递归地 进行下去 。 如果我们将一个子曲面片为局部平坦作为终止对这个子曲面片细分的条件 , 则我们可 以对整个曲面片进行适应性细分 递归地将曲面片分割成四个子曲面片 , 直至每个子曲面片都为 局部平坦 由于 曲线或曲面上的每一个点都位于相应的控制点集的凸包 内 , 并且从文〔 〕知准细分过程中产生的新的控制点收敛于 曲线或曲面 , 因此有一个子曲面片 的平坦性“ 检验的十分简单有效的方法 。 对于一个具有四条边的子曲面片的平坦性检验 包括对其四条边的直线性的检验以及其平面性的检验 对于双三次 曲面 , 子曲面片的每条 边都是由四个控制点定义的三次 曲线 , 由 曲线的凸包性质知 , 当四个控制点在一直 线上时 , 它们所定义的 曲线成为一直线段 注意到 曲线的两个端与首 、 末两个控制 点重合 , 因此在进行直线性检验时 , 当中间两个控制点到连结首末两个控制点的线段的距离小于 误差允许值 。 时 , 则可以认为这条边为直线段 子 曲面片平面性检查的方法与此类似 当 控 制点阵列中的中间四个控制点到 由任意三个位于角上的控制点所确定的平面的距离小于误差允许 值 。 时 , 即可认为该子 曲面片上的所有点位于同一平面上 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 。 护 礴 三 、 曲面细分的三角形化 适应性细分的四叉树表示 当一个子曲面片在递归分割过程中通过平坦性检验时 , 我们尚不知道如何把它分割成三角 形 , 因为我们必须考虑与之相邻的子曲面片以防止出现裂缝 。 这意味着直至曲面细分完毕 , 我们 方能知道如何将每个平坦的子 曲面片分割成三角形 。 因此需要一种数据结构来记录递归分割过 程 。 这种数据结构必须能反映分割的层次结构以及分割后得到的子曲面片之间的相邻关系 。 四叉 树 〔日 · ’。 , 自然地是能满足上述 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 的一种数据结构 。 口口口口口口 门门门田田田 曰曰曰曰叮叮 口口口口口口 图 曲面适应性细分的四叉树表示 四叉树用于描述一类具有层次的数据结构 , 这种层次关系是基于对空间的递归分割得封的 。 在参数 曲面的适应性细分中 , 对参数空间的有层次的细分对应于对 曲面在模型空间 的有层次的细分 , 整个分割的层次结构可以表示为一棵四叉树 。 四叉树的根对应于被细分 的曲面片 , 除根结点外的其余非叶结点对应于分割的不同层次中得到的需进一步细分的子 曲面 片 , 而叶结点则对应于那些平坦的子曲面片 。 图 给出了一个曲面在参数空间适应性细分及相应 的四叉树表示的例子 。 为了进行下面将讨论的三角形化处理 , 四 叉树的每个非叶结点包含五个指针 一个指针 指向其父结点 , 其余四个分别指向它的四个儿 子 , 分别以 , , , 记之 每个叶结点 除包含一个指向其父结点的指针外 , 还存放着 对应的平坦的子 曲面片的四个角点 。 在将平坦 的子 曲面片分割成三角形时 , 我们要用到它的 中心点 , 这个点可以通过计算四个角点的平均 值来近似地得到 。 刁 图 一个子曲面片的边和角点的命名 三角形化算法 三角形化的目的是将每个平坦的子曲面片分割成若干个三角形 , 使得沿着相邻的子曲面片的 边界没有裂缝 , 从而得到整个曲面的三角形 网表示 我们定义四个方向 、 、 、 , 一个 子 曲 飞 面片的四条边分别称作它的 、 、 、 边 见图 。 在这四个方向上分别与一个子曲面片相邻的 其它子曲面片分别称作它的 、 、 、 邻居 , 或者称作这个子曲面片在这些方向上的邻居 。 在以 后的叙述中 , 当我们谈到四叉树的一个结点时 , 我们同时也指相应的子曲面片 , 反之亦然 。 若 和 为两相邻的子曲面片 , 并且它们在四叉树中位于同一层次 , 则称它们互为同层次邻居 我们先对文 〔的 中给出的四叉树的找邻居算法略加修改 , 给出一个寻找同层次 邻居的算法 , 然后进一步讨论三角形化方法 。 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net · 对于给定的结点 和方向 , 一 , , , , 我们的算法要找 的在方向 的同层次邻居 。 如果这样的邻居不存在 , 算法返回 。 注意如同层次邻居存在 , 它可以与 有相同的或不相 同的父结点 , 若它与 有相同的父结点 , 则我们称它们是兄弟 当算法返 回 时 , 也有两种 情况 在 方向的邻居在四叉树中位于较 高的层次上 , 或 在 方向的边是原曲面片在 方 向的边界的一部分 , 因而 在 方向已不存在邻居 下面用类似 语言的伪代码的过程来描述算 法 。 为描述简单起见 , 一个变量 , 例如 , 既可代表四叉树的一个结点 , 又可代表指向四叉树结点 的指针 , 它的意义可以由上下文来确定 。 、 一 一 , 比 冈 肠 《 二 , 有一个兄弟只 是 在 方向的邻居 , 毛 设 为 的父结点 一 一 , , 为叶结点 , 二 的一个儿子 , 它是 在 方向的邻居 , 注意在执行 的一个儿子 , 它是 在 方向的邻居 时 , 射规则 。 为节省篇幅 , 这里不再细述 , 请读者参考文献〔 。〕。 下面给出一个例子来说明上面的算法是如何寻 找同层次邻居的 。 在图 中 , 在 和 方向分 别有同层次邻居 和 , 它 们都是 的兄弟 。 在 方向 , 有同层次邻居 , 由于 不是 的兄弟 , 因此算法首先找到 的父结点在 方 向的同层次邻居 , 然后因为 是其父亲的 儿子 , 根据反射规则返回 的 儿子 , 即 。 在 方向的同层次邻居为 。 图 要用到文 〔 。〕中所介绍的所谓反 ,,,,,, ‘‘‘ ·· 十十魂 子曲面片 的同层次邻居 在将平坦的子 曲面片 分割成若干个三角形时 , 为防止裂缝的产生 , 我们沿着 的每条边来 产生三角形 。 如果我们将 的同层次邻居或较低层次邻居 在四叉树中位于较 低的层次上的邻 居 统称为非高层邻居 , 那么 在某个方向不存在同层次邻居隐含 在这个方向不存在非高层次 邻居 。 我们以方向 为例来说明如何沿着 的 边来产生三角形的 如 在 方向不存在非高层次邻居 , 那么沿 的 边只产生一个三角形 , 此三角形的三 个顶点分别是 的中心以及 的 边的两个端点 。 如 在 方向有非高层次邻居 , 那么 如果 是叶结点 , 产生一个以 的中心以 及 的 边的两个端点为顶点的三角形 如果 不是叶结点 , 则其 和 儿子都是 的 方向的非高层次邻居 , 对于 的这两个儿子 , 递归地执行步骤 。 我们将平坦的子 曲面 片的四个角点按图 编号 , 分别记之为 〔 〕、 〔 〕、 。 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net · 〔幻 、 〔 〕, 它们存放在叶结点中 下面我们给出三角形化算法的伪代码 。 创 冈 勺卜 《 民 目 , , 。 , 尹 , 龟 是叶结点 一 一 “ 司 , 。二 。 一 一 , , 二 一 一 闭 , 一 一 “ 司 , 了 肚 一 血 司 , , ‘ 一 血 司 , , , ‘ 一 ‘ 司 , , 一 血 , 目 , , 叱 认 卜抽 司 叩 一 司 一 , 认 ‘ 目 一 司 , 一 尽 。 , ,理 闭 令 , 、 肠作 石 , 飞卜 俐 卜 《 一 二 粉出一个 以 一 , 〕, 的中心 , 一 〔 〕为顶点的三角形 , 是叶结点 翰出一个 以 。 〔幻 , 一 〔 〕, 的中心为顶点的三角形 考 一 , , 一 , ‘ 一 ‘ 。 , , 二 粉出一个 以 二 〔 〕, 的中心 , 〕为琪点的三角形 , 是叶结点 粉出一个 〔 〕, 一 〔 〕, 的中心为顶点的三角形 《 一 , 一 。 , , , 比 , “ 一 枪出一个 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 碑 , — 以 , 〔 〕, 的中心 , 二 〔。〕为玻点的三角形 是叶结点 抽出一个 以 〔 〕, 。 , 幻 , 的中心为班点的三角形 姗 一 明 】 , 二 , 砂 一 。闹 一 , 计 抽出一个 以 一 , 〔幻 , 的中心 , 〔幻为顶点的三角形 , 《 是叶绪点 翰出一个 以 一〔幻 , 一〔 。〕, 的中心为议点的三角形 一 《 一 血哈 , 仰 , 日 一 血 砂 , ‘ 。 , , ‘ 设 为指向四叉树根结点的指针 , 则整个 曲面的三角形化可通过过程调用 。 来实现 图 为一个双三次 滋 曲面片 , 对它进行了适应性细分后再用上述算法进行了 三角形化处理 。 可以看出 , 相邻的平坦的子曲面片之何由于细分的层次不同而可能出现的裂缝由 于三角形化而被避免 。 本算法比 和 的算法产生较少的三角形 , 但是一般地形成 的三角形网已经是原曲面的较好的近似 。 丫 丫 图 一个适应性细分和三角形化后的双三次 血 曲面片 四 、 结 束 语 本文介绍了适应性细分双三次 幻 曲面的方法 , 在此墓础上给出了将曲面细分三角形化的 四叉树方法 。 文中所述的算法在加拿大 , 大学计算机系图形实脸室实现 , 并被用于该实验 室的计算机动画系统 中的造型系统 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net · · 参 考 文 献 尹车 〔 〕 , “ 众 即 ‘ ‘ ” , 块 , ” 〔 〕 , “ 朋 “ 朗 ” , 卜司 阮 , 〔 〕 , “ 氏 , , 〔 〕 , 氏 肠 , “ ” , , 众 , ,于 〔 〕 , “ 司 ‘ 而 ” , , , 〔 〕 , “ ” , 卜 。 , , 〔 〕 , “ ” , , 八 〔 〕 , “ ” , , , 〔的 , “ ” , 一 , , 。。 〔 〕 , “ 匆 , , 〔 〕 , “ 氏 ” , , 〔 〕 , 印 , “ 卜司 众 氏 ” , , , 〔 〕 , “ 反 一 ‘ 石 ‘ ” , , , , 〔 〕 , “ 反 以 ” , , · · 〔 〕 , “ 肠 ” , , 勺,卜︸ 漏 ‘ 。扮 , “ 二彻 知“如 “ ‘工 以‘ “ , , 加 城 , 云 俪 卜 、 粉 , 的 , , , 姐 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net