点到三维隐式曲线的正交投影算法.pdf

第 21 卷第 17 期 系 系 统统 仿仿 真真 学学 报报 vol 21 no 17 2009 年 9 月 journal of system simulation sep 2009 5388 点到三维隐式曲线的正交投影算法点到三维隐式曲线的正交投影算法 徐海银 方雄兵 华中科技大学计算机科学与技术学院 武汉 430074 摘摘 要要 针对点到三维 3d 隐式曲线的正交投影问题 提出了一种稳定的几何迭代算法稳定的几何迭代算法 算法首先 给出了基于二阶泰勒逼近的投影点追踪公式 通过将给定点向初始点处的曲率圆作投影 提出了基 于曲率的步长控制策略 基 于曲率的步长控制策略 考虑到迭代过程中存在的误差 给出了基于梯度的迭代误差矫正方法基于梯度的迭代误差矫正方法 最后 给出了计算点到三维隐式曲线的正交投影的完整算法实现步骤 仿真结果表明 算法对初始 值的敏感性较低 算法稳定 高效 收敛性良好 关键词关键词 正交投影 隐曲线 曲率圆 步长 中图分类号中图分类号 tp391 文献标识码文献标识码 a 文章编号文章编号 1004 731x 2009 17 5388 03 algorithm for orthogonal projection onto 3d implicit curves xu hai yin fang xiong bing school of computer science implicit curves curvature circle step 引引 言言1 正交投影在几何建模 计算机动画以及计算机视觉方面 有着广泛的应用 pegna 等最早提出了正交投影的概念 并 讨论了空间参数曲线在参数曲面和隐曲面上的正交投影曲 线的计算问题 1 所谓正交 就是在曲线上找到一点 使得 该点与给定点的连线与曲线在该点处的切线是垂直的 由于 正交投影和距离投影之间具有一定的联系 1 因此距离投影 的研究在一定程度上有助于正交投影的研究 国内外相关学 者在这两方面均做了大量的工作 hartmann 提出了一种一阶方法来计算点到参数曲线 曲面的正交投影 2 hu 等提出了一种二阶的几何迭代算法 来逼近给定点在参数曲线 曲面上的正交投影点 3 ma 等 研究了点在 nurbs 曲线和曲面上的投影问题 首先将 nurbs 曲线 曲面细分成小的曲线段或曲面块 然后找出 曲线段或曲面块的控制多边形与测试点之间的关系 并在此 基础上找出候选的曲线段或曲面块以及近似投影点 最后通 过比较测试点与这些近似投影点的距离来得到最终的投影 点 4 xu 等研究了数控加工中隐式曲线的线性和旋转插补 问题 5 同时 国内外学者在距离投影方面也作了一些研究 收稿日期 收稿日期 2008 04 03 修回日期 修回日期 2008 08 28 基金项目 基金项目 湖北省国际科技合作重点项目 hzw0050 作者简介 徐海银作者简介 徐海银 1968 男 湖北浠水人 博士 副教授 研究方向为 计算机图形学 计算机动画以及计算机辅助设计 方雄兵方雄兵 1983 男 湖 北麻城人 博士生 研究方向为几何计算及计算机动画 由于最小距离通常发生在两个几何体上的一对特殊点之间 文献 6 8 均利用该性质研究了各种特定几何体之间的最小距 离并取得了一些满意的结果 然而 上述工作都没有就点到 隐式曲线的正交投影问题作专门的研究 由于隐式曲线 曲 面难于精确控制 因此要在隐式曲线上找到满足精度要求的 正交投影点是较为困难的 同时几何建模 计算机动画以及 计算机视觉中很多问题都可以归结为点到曲线的正交投影 问题 因此研究点到隐式曲线的正交投影具有重要意义 本文在上述两方面工作基础上 提出了点到空间 3d 隐式曲线的正交投影算法 首先 给出了投影点的迭代公式 进一步提出了基于曲率的步长控制策略 考虑到迭代过程中 存在的误差 文中给出了一种基于梯度的迭代误差矫正方 法 最后 给出了完整的计算点到 3d 隐式曲线的正交投影 算法 实验结果表明 文中提出的算法具有良好的收敛性 可以满足任意精度要求 同时算法对初始值的敏感性较低 1 点到点到 3d 隐式曲线的正交投影算法隐式曲线的正交投影算法 计算点在 3d 隐式曲线上的正交投影的问题简述为 设 3d 曲线 的方程由一隐式函数给出 p为隐式曲线 外的 一点 要求在隐式曲线 上找到一点h 使得向量ph与 隐式曲线 在点h处的切矢量垂直 针对该问题 本文提 出了一种稳定的几何迭代算法 首先 建立了基于二阶泰勒 方法的投影点迭代公式 在此基础上 提出了基于曲率的步 长控制策略 同时 考虑到迭代过程中存在的误差 给出了 一种基于梯度的误差矫正方法 最后 给出了完整的计算点 第 21 卷第 17 期 vol 21 no 17 2009年9月 徐海银 等 点到三维隐式曲线的正交投影算法 sep 2009 5389 到 3d 隐式曲线的正交投影算法 1 1 投影点的追踪投影点的追踪 设 p m n l是空间中的一点 又设 3d 隐式曲线 以 0 0 f x y z g x y z 1 的形式给出 dydxdz dt dt dt t 为沿着 3d 隐式曲线的单位切 向量 1 式对弧长参数s求导数得到 0 0 tf tg 2 其中 xyz 为 hamilton 算子 xyz f f f f xyz g g g g分别为两隐式曲面在点 x y z处的梯度 考虑到t为单位矢量 求解上述方程组得到 fg t fg 进一步 设 222 222 d yd xd z dtdtdt c为 3d 隐式曲线 的曲率矢 量 将 2 式对弧长参数s求导数得 tt 2 tt 2 t 0 0 0 tf tf c tg tg c tc 3 其中 2 xxxyxz yxyyyz zxzyzz fff fff fff f 2 xxxyxz yxyyyz zxzyzz ggg ggg ggg g 求解方程组 3 得曲率矢量为 ttt 222 0 ctf ttg tw 其中 2 xyz xyz sss fff ggg xyz w 由文献 9 知 1 式定义的3d隐式曲线 在点 x y z处 的曲率为 3 k x y z fgfgfg fg 设 点 0000 xyzg处 的 曲 率 圆 圆 心o坐 标 为 000 xyz ooo 则有 000 0000 xyz oooxyzk 0 其中 000 c c 为3d隐式曲线 在点 0 g处的主法矢量 0 k为3d隐式曲线在点 0 g处的曲率 隐式曲线 在点 0 g处 的副法矢量为 00 00 tc tc 故 0 g点处的曲率圆的方程为 000 000 2222 0 1 0 xyz xyz xoyozok xoyozo 下面将空间中一给定点 p m n l向3d隐式曲线 在 点 0 g处的曲率圆作正交投影 得到垂足点q 如图1所示 可以证明 曲率圆所在平面的法向量 曲率圆圆心o以及 空间点p所在的平面ii与曲率圆的交点即为垂足点q 点 m为平面ii与曲率圆的交点 而平面ii的方程为 000 0 xyz xoyozo po 则q点可以通过求解下面的方程组得到 000 000 000 2222 0 1 0 0 xyz xyz xyz xoyozok xo yo zo xo yo zo po 由于平面ii与曲率圆有两个交点 1 q和 2 q 这里取离 0 g点较近的一个交点作为q点 p m n l m q o 0 t 0 c 0 g ii 图 1 空间点p向 3d 隐式曲线在初始点 0 g处的曲率圆作投影 设3d曲线 上任意一点的坐标为 x y z g 则利用 二阶taylor公式有 2 000 1 2 ss ggtc 4 即当s 较小的时 可以通过 4 式来计算3d隐式曲线上的 一点g 通过适当的误差矫正之后 可以将g点作为下一 次迭代的初始点 0 g 并迭代出3d隐曲线上新的一点g 如 此迭代计算下去 直到找到一点h 使得该点即为所要求 的正交投影点 然而 直接将上述s 取恒定值时并不能保 证迭代的点一定收敛到目标点h 因此 有必要进一步讨 论步长的控制问题 使得迭代点能最终收敛到目标点h 1 2 基于曲率的步长控制策略基于曲率的步长控制策略 当向初始点的曲率圆作投影时 可以考虑将隐曲线段 0 g m 曲率圆的小圆弧 0 g q或者弦长 0 g q作为步长s 的 大小 然而计算隐曲线段 0 g m或小圆弧 0 g q的长度比较困 难 本文考虑将弦长 0 g q作为步长s 的大小 因此有 0 s g q 5 这里 规定步长的符号始终与 00 g p t的符号相同 即 0000 sign s sign x y z pt 6 显然步长s 的大小随着 0 g点变化而变化 同时 0 sk 向量 0 og与oq的夹角 满足 02 然而 直接将公式 5 中的步长s 代入 4 中计算得到的 点g往往偏离3d隐式曲线 较远 同时考虑到二阶泰勒逼 第 21 卷第 17 期 vol 21 no 17 2009 年 9 月 系 统 仿 真 学 报 sep 2009 5390 近方法的收敛条件以及保证每一步计算出来的点g偏离3d 隐式曲线 较小 因此需要控制每一步的步长s 通常 取01 时 作如 下处理 令 0s nn g q 其中 n为正整数 考虑到曲率圆的小圆弧 0 g q与弦长 0 g q满足下面关系 00 g q g q 这里作放大处理 0 00 2nk nk n g qg q g q g q 7 同时步长s 的符号满足 6 式 利用该步长计算出来的 点g能不断逼近目标点h 1 3 基于梯度的基于梯度的 3d 隐式曲线误差矫正方法隐式曲线误差矫正方法 对于3d隐式曲线的情形 利用 4 式计算出来的点g可 能会偏离3d隐曲线 即点g不在两个隐式曲面上 f fe g 0 0 g ge g 又 0 ggg 其中 2 00 1 2ss gtc为 迭代增矢量 误差矫正的基本思想是 当点g偏离两个隐式曲面较远 时 利 用 矫 正 矢 量 xyz g 来 修 正 点g 即 ggg g和 g分别为矫正前后的迭代值 并且使得 fle g gleg 利用1 3节方法对g点进行误差矫正 得到 g 并令 new gg else new gg step4 判断 new g是否为目标投影点h 即判断s 是 否满足精度值ls if sls 令 new h g 转step5 else 令 0new g g 并转step1 step5 输出正交投影点h的值 程序结束 需要说明的是 在上述迭代过程中 步长s 逐渐趋于 0 因此最终可以在曲线上找到一点h 使得该点与给定点 p的连线ph与隐曲线在h点处的曲率圆以及切平面正 交 因此 当步长s 小于某一给定的微小量ls时 ls通常 取为 6 10 认为计算出来的点即为所要求的正交投影点h 2 算法仿真与实验结果分析算法仿真与实验结果分析 下面对算法进行仿真 并对实验结果进行分析 设空间3d隐式曲线 由方程组 222 22 91691 4 xyz xyz 给出 设空间点p的坐标为 4 4 3 6 10ls 计算 结果保留8位小数 表1结果表明 文中算法对3d隐式曲线上的正交投影 点计算具有良好的收敛性 算法对初始点的依赖性较低 点 p到3d隐式曲线 的正交投影如图2所示 表表 1 3d 隐式曲线初始点位置以及隐式曲线初始点位置以及 值均发生变化时的情形值均发生变化时的情形 初始点位置 值 迭代次数正交投影点的位置 0 000000 2 883749 2 079001 0 6 46 1 72849496 2 11769030 1 86807676 0 000000 2 883749 2 079001 0 8 32 1 72849496 2 11769030 1 86807672 1 000000 2 653288 2 009984 0 6 33 1 72849496 2 11769030 1 86807676 1 000000 2 653288 2 009984 0 8 22 1 72849496 2 11769030 1 86807676 2 000000 1 397237 1 488068 0 6 19 1 72849496 2 11769030 1 86807676 2 000000 1 397237 1 488068 0 8 14 1 72849496 2 11769030 1 86807676 下转第5395页 第 21 卷第 17 期 vol 21 no 17 2009 年 9 月 惠毅 等 一种基于业务优先级的跨层资源分配算法 sep 2009 5395 为0 01 从图5中可以看出 在非实时业务用户和尽力而为 用户的数量为50时 max rate算法的系统吞吐量为 87mbits s m lwdf算法的系统吞吐量为74mbits s 本文 算法的系统吞吐量为70mbits s 因此本文算法的综合性能 是最优的 能够在满足各种业务用户的qos需求和服务质 量的情况下 根据信道条件动态调整分配给各种业务的资 源 有效提高系统的吞吐量 参考文献 参考文献 1 zhang y j liew s c link adaptive largest weighted throughput packet scheduling for real time traffics in wireless ofdm networks c ieee globecom 05 s1054 5921 usa ieee 2005 5 2490 2494 2 berry r a yeh e m cross layer wireless resource allocation j ieee signal processing magazine s1053 5888 2004 21 5 59 68 3 entrambasaguas j t aguayo torres m c gomez g paris j f multiuser capacity and fairness evaluation of channel qos aware multiplexing algorithms j ieee network s0890 8044 2007 21 3 24 30 4 li y g winters j h sollenberger n r signal detection for mimo ofdm wireless communications c ieee icc s1875 0710 helsinki finland june 2001 usa ieee 2001 3077 3081 5 blum r s li y g winters j h yan q improved space time coding for mimo ofdm wireless communications j ieee transactions on communications s0090 6778 2001 49 11 1873 1878 6 cheng p yu g d zhang z y qiu p l a cross layer fair resource allocation algorithm for ofdma systems c icccas 06 s1 4244 1474 1 guilin china june 2006 1342 1346 7 tang j zhang x effective bandwidth based qos provisioning for real time audio video streaming over mimo ofdm wireless networks c ipdps 05 s0 7695 2132 0 denver ca usa april 2005 1 8 8 tang j zhang x cross layer design of dynamic resource allocation with diverse qos guarantees for mimo ofdm wireless networks c wowmom 2005 s0 7695 2342 0 taormina italy june 2005 205 212 9 卢小峰 朱光喜 伍仁勇 等 基于多用户 mim0 ofdm 系统的 空间子信道分配算法 j 通信学报 2006 27 9 34 39 10 zhang y j khaled b l cross layer adaptive resource management for wireless packet networks with ofdm signaling j ieee trans on wireless commun s1536 1276 2006 2 11 3244 3254 11 kong z wang j z kwok y k a new cross layer approach to qos aware proportional fairness packet scheduling in the downlink of ofdm wireless systems c ieee icc2007 s1875 0710 glasgow scotland june 2007 usa ieee 2007 5695 5700 12 唐岚 王树勋 梁应敞 多入多出 mimo 系统中的可变速率多用 户分集技术 j 科学技术与工程 2004 4 4 275 281 13 wang j qiu l zhu j k a priority based scheduler for mimo ofdm downlink system c ieee gmc2007 s1557 0622 shanghai china usa ieee 2007 1 6 1 上接第5390页 图 2 空间点p在 3d 隐式曲线上的正交投影 3 结论结论 本文针对点到3d隐式曲线的正交投影问题 提出了一 种稳定的几何迭代算法 首先给出了基于二阶泰勒逼近的投 影点迭代公式 进一步通过向初始点处曲率圆作投影获得迭 代步长 提出了基于曲率的步长控制策略 同时 考虑到迭 代过程中产生的误差 最后给出了一种基于梯度的误差矫正 方法 实验结果表明 算法收敛性良好 同时算法对初始值 的敏感性较低 当初始点距离目标投影点较远时 上述算法 需要的迭代次数较多 进一步优化迭代步长对于减小迭代误 差 提高效率具有重要意义 本文提出的正交投影算法 为 研究曲线在曲面上的正交投影奠定了基础 该算法也可以进 一步应用在求最小距离以及几何建模和计算机动画方面 参考文献参考文献 1 pegna j wolter f e surface curve design by orthogonal projection of space curves onto free form surfaces j journal of mechanical design s1050 0472 1996 118 1 45 52 2 hartmann erich on the curvature of curves and surfaces defined by normalforms j computer aided geometric design s0167 8396 1999 16 5 355 376 3 hu shi min wallner johannes a second order algorithm for o