形的凸包内。
证明:由引理 1 知,测地 B 样条子曲线:
位于 个控制顶点
的凸包 内,整条曲线
位于
这些凸包 的并集
之内。
性质 2 测地 B 样条曲线具有局部调整性,即变动控制多边
形的一个顶点,只影响测地 B 样条曲线在该点的附近部分。
证明:改动一个控制顶点
,曲线上仅有点 参加
控制的那 段曲线
(其参数
)的形状发生变化。
性质 3 测地 B 样条曲线具有保凸性,即若控制多边形
为凸,则 阶测地 B 样条曲线也是凸的。
证明:在 阶测地 B 样条曲线上任取一点,设此点对应着参
数
。 在 t' 处嵌入一个节点。
则新的控制多边形
为原控制多边形的
内接多边形,所以由定义 1、2 知,仍是凸的。 再在 处依次嵌入
个节点,则
仍是凸多边形。
个节点, 将与边 和边 相交,从而得到修正后的路径将与
创 新
《PLC 技术应用 200 例》
邮局订阅号：82-946 360 元 / 年 - 229 -
软件时空
空间直线 , 相交,取两空间直线 和 公垂线与直线 的
交点作为两空间直线 与 的交点, 这样得到的路径将会是最
短的,将新点连同所在边的信息,添加入路径,然后把这个新得到
模型上自由曲线的设计。 其次,证明了测地 B 样条曲线的一些重要性质,如凸包性,局部调整性和保凸性等性质。 最后,在
Visual C++6.0 语 言 环 境 下 , 利 用 OpenGL 图 形 库 给 出 网 格 模 型 上 B 样 条 曲 线 生 成 的 一 些 实 例 。 实 验 结 果 表 明 , 本 文 提 出 的 算
Boor 算法定义的主要不同是:控制多边形的边不再是直线段,而
是离散测地线,即用离散测地线来连接控制顶点。这就要求必须
修改经典的 de Boor 算法 。 在曲面几何上线性插值等价于沿着
离散测地线插值。 算法 1 的 Step3 描 述 了 在流 形 n 边 形剖 分 里
的插值步骤。 算法 1 定义的曲线称为测地 B 样条曲线。
且测地线
的第一段 (在网格面内)
是在
处的切线,根据测地 B 样条曲线的凸包性,曲线
段
必落在凸多边形
中,
因而必位于切线
之同侧,即其为凸。
4 结束语
本文提出任意拓扑网格化曲面上 B 样条曲线的生成算 法— ——de Boor 算 法 。 测地 B 样 条 曲 线 可 用 于 网 格 模 型 上 自 由 曲线的设计。 证明了测地 B 样条曲线的一些重要性质。 最后,在 Visual C++6.0 语言 环 境下, 利 用 OpenGL 图形 库 在 离 散 曲 面 上 进行了一些实验。 实验结果表明,本文提出的算法正确,快速,易 实 现 且仿 真 效 果好 。 本 文 的算 法 可 加入 计 算 机 辅 助 设 计(CAD) 和 计 算 机 辅 助 制 造(CAM)系 统 中 ,成 为 计 算 几 何 中 曲 面 上 曲 线 造型的有力工具。 因此这种算法在计算机辅助设计和图形学中 具有广阔的应用前景。
- 230 - 360元 / 年 邮局订阅号：82-946
《现场总线技术应用 200 例》
您的论文得到两院院士关注
反之, 曲线上每点
仅与 个控制
顶点
有关。
定义 1 若曲面上连续曲线是曲面上某一凸集的边界或边
界的一部分,则称连续曲线为凸曲线。
定义 2 称曲面上多边形
为凸,是指用曲面上的线连
接其两端点 和 后,所围成的曲面上的区域为凸集。
术
引言
设计自由曲线是几何造型中的一个基本操作。 在欧几里得 空 间 里 已 得 到 广 泛 研 究 , 并 形 成 了 以 Bézier、B 样 条 为 主 流 , NURBS 为 STEP 工业标准的设计方法。 随后,一些学者将 Bézier、B 样 条 方法 推 广 到 球 、李 群 等 测 地 线 较 容 易 计 算 的 Riemannian 流 形 上,然 而,在 任意 拓 扑 网格 曲 面 这类 离 散 曲 面 上 设 计 测 地自由曲线变得很困难。 现有的大部分工作是基于一个适当的 参数化,常导致一系列“试验和误差”的操作。要在任意拓扑网格 曲面上构造测地 B 样条曲线需要将欧氏空间的 de Boor 算法推 广到任意拓扑网格曲面上 。 而将 de Boor 算法推广到任意拓扑 网格曲面上的关键点是要将欧氏距离修正为离散测地线。因此, 任意拓扑网格曲面上离散测地线算法是要解决的首要问题。 文 献详 细 阐述 了 该 问题 的 解 决 方 法 。 即 对 基 于 Sethian 快 速 前 进 式 方 法 (Fast Marching Method) 和 Polthier 最 直 测 地 线 理 论 的 Dimas Martínez Morera 的 三 角 化 曲 面 上 测 地 线 计 算 方 法 进 行 了改进,提出一个更有效,且是任意拓扑网格化曲面上的测地 线算法。
Visual C ++6.0, B -spline curve on meshes were given by OpenGL. Examples show that the algorithm are correct, stable, fast and
easy in implementation. There is a good effect of simulation for all examples. Key words: geodesic B-spline curve; topological mesh; algorithm
离散测地线算法计算 n 边形网格化曲面上的离散测地线
Step1:根据给定的散乱数据点,建立 边形网格化曲面 ;
Step2:任取 上两点 ,用 FMM 方法计 算 上 每点 到
的距离
;
Step3: 将加入初始曲线 ,令
,
while 不等于 , 等于距离 最短的 的邻近点,
将 加入 ,
,获得初始逼近 ;
本文在文献的基础上,将欧氏距离修正为离散测地线,给出 任意拓扑网格 化 曲面 上 的 de Boor 算法, 成 功 地实 现 了 任意 拓 扑网格化曲面上 B 样条曲线的设计。 这给出了直接构造离散曲 面上自由曲线的新途径。
1 测地 B 样条曲线生成的算法步骤
内蕴 B 样条曲线是通过经典 B 样条曲线的 de Boor 算法定
DU Hong-yun TANG Yue-hong WANG Jun-hai DU Jin-long
摘要: 本 文 首 先 提 出 流 形 网 格 上 的 de Boor 算 法 。 此 算 法 可 用 于 生 成 网 格 模 型 上 的 B 样 条 曲 线 。 测 地 B 样 条 曲 线 适 用 于 网 格
Step4: 的起 点 和终 点 不 用修 正, 中 间 节 点 根 据 下 面①修
正与网格顶点重合的节点和②修正与网格边重合的节点两种
情况进行修正,这样修正 为 ;
Step5:重 复 Step4 的 修 正 过 程 ,获 得 一 个 新 曲 线 。 计 算
长度,直到误差
小 于 容 许 误 差 (如 0.0001), 迭 代 修
杜宏云: 讲师 硕士 基金项目: 基金申请人: 唐月红; 项目名称: 关于 GC-B 样条曲 线的计算; 基金颁发部门: 国家自然科学基金委(60711240471)
义的。 给定离散曲面 S 上的 n 个控制顶点
,计算 S 上
不插值两端点 和 的一条曲线, 而曲线的形状却受到点
的位置的控制。
该 曲 线 可 用 “de Boor 算 法 ”定 义,与 经 典 B 样 条 曲 线 的 de
正终止,得到离散测地线 的一个带任意精度的逼近 。
①修正与网格顶点重合的节点
根据两点之间,直线最短的原理,以需要被修正的节点为中
心展开,连接其上下节点,得到的直线一定比通过该节点的路径
短。对顶点相邻的网格面展开,根据得到的夹角大小以及点的顺
序,得到展开后的平面上与连接前后节点所在的直线相交的边,
如 图 1a 中 为 一 个与 网 格 顶点 重 合 的节 点, 为 的前 后 两
的点与点 看成节点 的新的前后节点, 继续上面的方法得到
与空间直线 的交点。 删除需要修正的节点。
②修正与网格边重合的节点
根据节点记录的所在边的信息,即边的两个端点,得到一条
空间直线。 另外根据节点的前后两个节点也可以得到一条空间
直线。 如图 1b 中的两条空间直线 和 , 取其公垂线与 直
线的交点作为新的 点,代替原来的节点。
算法 1 边形网格曲面上的 阶 B 样条曲线的生成
Step1:在 边形网格曲 面 S 上任 取 点
,
;
Step2:用文 献 离 散 测 地 线 算 法 计 算 测 地 线
,
技
;
Step3:任 取术,,计算 上的点 满足,
创
注:
是计算沿着测地线 的
Step4:对新 点 (
的距离。 )连成的多边
新 形,重复 Step3 Step5:
图 1a
图 1b
图 1 修正原理图
图 2 de-Boor 算法的割角过程
《微计算机信息》(管控一体化 )2010 年第 26 卷第 2-3 期
图 3 人脸模型上五阶均匀 B 样条曲线
图 4 人脸模型上五阶非均匀 B 样条曲线
图 5 狮子模型上的五阶非均匀 B 样条曲线 2.2 离散曲面上的 B 样条曲线 用算法 1 在 Visual C++6.0 环境下, 利用 OpenGL 图 形 库绘 制人脸离散模型、狮子离散模型上控制多边形和均匀(相同节点 距)、非均匀(不相同节点距) B 样条曲线,如图 3-5 所示。