两条B样条曲线求交的高效计算方法

曲线曲面间求交计算在CG和CAD中有着广泛的应用.牛顿法等迭代法计算效率高但需要良好的初始值;裁剪法具有良好的鲁棒性但计算效率不理想,尤其是对于相切情况的求交问题.为此,提出一种计算2条B样条曲线交点的混合方法.首先提出一种高效的线性复杂度裁剪方法,用于获得良好的初始值;然后提出一种与导数无关且效率更高的改进的割线法,用于验证贯穿性相交情况;最后提出一个相切情况下收敛阶为2的迭代公式,其性能远优于现有的牛顿法和裁剪法.理论上,混合方法若与根隔离法相结合,可以应用于更多类型曲线间的求交问题.数值实验结果表明,与现有的同类方法相比,在贯穿情况下,所提方法的计算效率提高约10%,在相切情况下则提高约100%~300%.

圆环面/球面求交算法

将圆环面看成中心在大圆上的一族圆,从而将球面圆环面求交的问题转化为球面与一族圆的求交问题.该算法不需要跟踪交线.首先利用点圆最近距离的理论,直接判断是否无交、相切于一点、交于一个圆或交于两个圆等简单的情况;其他情况下,通过求解关于圆环面大圆的参数的一元四次方程的根,然后对该参数区间[0,2π]进行划分,并通过简单的符号判断来确定有交的参数子区间,在这些有交的子区间上直接给出所有交曲线段的参数表示形式.

直线/NURBS曲线等基于曲线束的求交方法

病态情形的求交问题中,求交对象的判定以及如何精确求解交点是其中的两大难点.文中讨论了直线和直线、圆、平面NURBS曲线等病态情形下的求交问题,提出了基于曲线束理论的求解方法.该方法借助于曲线束中的一条曲线,将病态情形的求交判定问题转化为非病态的情形,从而在无交的情形下可以通过简单的方法准确地得出无交的结论,在相交的情形下转化为可以精确求解的非病态问题.最后通过实例说明了该方法求解结果的稳定性与精确性.

平面代数曲线间最近距离的计算

通过几何观察,指出一条曲线上的最近点是另一条曲线的等距曲线与该曲线的切点这一事实,同时提出基于等距思想的方法来求解2条平面代数曲线间的最近距离.该方法几何意义明显,可同时用来计算代数曲线/参数曲线间的最近距离.对于平面二次曲线,采用文中方法得到的单变量多项式方程次数比已有类似方法中结果方程的次数更低,从而可以降低方程求解的计算复杂度或提高求解的稳定性.

平面椭圆与二次曲线间位置关系的判别式

平面实体间的碰撞检测中,经常需要讨论二次曲线间的位置关系.根据切点既是交点,又是最近/最远距离点的性质,结合结式理论推导出若干代数多项式,并用来判定平面椭圆与二次曲线间的位置关系.该方法直观简单,仅需要简单四则运算,可以直接应用于判别运动曲线间的位置关系.最后的实例及其比较表明,该方法应用范围广,结果也稳定.

Bézier曲线/曲面间最近距离的几何裁剪算法

曲线、曲面间距离的计算问题在CAD/CAM、计算机图形学中有着广泛的应用.为了精确计算Bézier曲线/曲面间的最近距离,结合稳定的曲线、曲面分裂技术提出一种基于offset滚动球裁剪的几何算法.首先给出判定条件来裁剪去落在曲面的滚动球外的曲线段,或者落在曲线的滚动球外的曲面片,以摒弃大部分不包含最近点的曲线段或曲面片,为后续可能的Newton方法提供较好的初始点;然后给出判定最近点是否落在曲线的端点或曲面的边界曲线上的条件,将曲线/曲面间的距离计算问题转化为点/曲面或曲线/曲线间的距离计算问题,简化了问题的复杂度,提高了计算效率.实例结果表明,文中算法具有较好的稳定性和较高的效率.

2条有理三次Bézier曲线的部分重合条件

当2条曲线重合或几乎重合时,基于曲线分裂的求交算法或因为过多次数的分裂而导致内存不足而系统奔溃,或最后的计算结果因分裂次数的不足而未能满足精度要求.2条曲线重合检测技术可以帮助求交算法来避开上述问题.本文以2条有理三次Bézier曲线为例,提出并证明了重合检测基于曲线控制多边形的如下判定方法,即2条有理三次Bézier曲线重合的条件为或者两条曲线退化为同一条一或二次的曲线,或者在首末权因子为1的限制下,2条曲线的控制多边形重合且对应的权因子相等.当2条曲线部分重合时,本文给出了简便的方法来确定相应的重合位置,从而将部分重合的判定问题转化为完全重合的判定问题.实例表明了本文方法的正确性及简单有效性.

多项式方程区间内求根基于R^2空间的3次裁剪方法

多项式方程的求根问题在求交、最近距离计算等方面有着广泛的应用.3次裁剪求根方法充分利用了Bernstein基函数较好的计算稳定性,避免了数值迭代求解的不稳定性,同时具有4次收敛的速度.不同于传统的基于R1空间内的3次裁剪方法,提出了基于R2空间内的3次裁剪方法.首先引入R2空间中一条曲线(t,f(t)),在该曲线给定的区间上选取3个点,并计算这3个点及其对应的切向;然后求解3次多项式曲线Ai(u),满足同时插值这3个点及其中2个点处的切向;最后选择适当的重新参数化函数φ(t),使得Ai(φ(t))和f(t)之间具有5次逼近阶.若给定的参数区间Φ充分小,A1(φ(t))和A2(φ(t))可以在区间Φ内直接包住f(t),从而节省了用于求解包围多项式的大量计算.实例结果表明,该方法具有更好的逼近效果、更快的收敛速度和更高的计算效率.

奇异情况下两个二次曲面间的求交

曲面求交是几何造型系统的核心之一,奇异情况下求交算法的稳定性直接关系到后续的布尔运算乃至整个系统的稳定性.提出2种二次曲面间对应特征多项式有重根情形下鲁棒的求交算法.首先给出精确求解特征多项式重根的方法,若交线中存在奇异交点,则给出奇异交点关于特征多项式重根的显式表达式,从而稳定地求解出对应的奇异交点;同时给出一种交曲线有理参数化的构造性方法,可以弥补Farouki相应有理参数化方法中的缺陷.最后通过实例进一步说明了文中算法的求解稳定性及有理参数化的构造性方法的实用性.

B样条曲面方向投影问题的几何计算方法

B样条曲面方向投影问题可以通过求解方程组的方法来解决.由于方程组所有根中往往只有一个或甚至没有根与待求解的最近点对应,因而绝大多数的求根计算量是不必要的.为此讨论了B样条曲面的方向投影问题,提出一种简单且高效稳定的几何计算方法.该方法充分利用了B样条函数的凸包性,同时结合B样条函数稳定可靠的分裂算法给出了相应的几何剪枝方法.与传统的求解非线性方程组的计算方法相比,文中方法可以剪除绝大部分非线性方程组对应的根,且不需要Newton迭代,可以应用于平面/B样条曲面间的求交测试问题及B样条曲面包围盒的计算问题.实例结果表明,该方法具有比传统的相关方法更高的计算效率和更好的稳定性.

基于Hausdorff距离的曲线降阶算法

Hausdorff距离常被用于衡量两条曲线间的逼近效果。该文以Bézier曲线为例,提出了基于分段二次函数重新参数化的新算法,用于求解平面或空间曲线的降阶逼近问题。理论上该文算法同样适用于B样条曲线等的逼近问题。数值例子表明了新算法可以具有Hausdorff距离下更好的逼近效果。

基于重新参数化技术的新Cusa-Huygens不等式

以Cusa-Huygens不等式为例,结合Padé逼近方法和重新参数化技术,提出新Cusa-Huygens不等式,从而得到更为精确的逼近估算。与同类已有的Cusa-Huygens不等式相比,新不等式的上下界约束更为紧凑。

自由变形技术及其应用

物体变形一直是计算机图形学和辅助设计中的一个热点问题.自由变形方法作为物体变形的核心技术,已被成功集成到当今主流的造型软件及动画软件中.对20年来自由变形技术的发展作了详细的综述,对现有技术进行了系统的分类,即将其分为非精确自由变形和精确自由变形,并根据所使用的变形工具的不同,将非精确自由变形技术分为4类:基于体的变形、基于曲面的变形、基于曲线的变形、基于点的变形.进一步比较了各类技术在变形工具的创建、参数化效率、变形工具的修改、多功能性等方面的优缺点,并分析了它们之间的内在联系.最后对其应用及未来工作进行了简要的介绍.该综述不仅对于该领域的研究人员具有重要的参考价值,而且对于三维造型师及三维动画师也有一定的指导意义.

单圆弧样条保形插值算法

该文以插值具有偶数个点的闭多边形为例提出了一种新的圆弧样条插值算法 .这种算法具有以下 3个特点 :(1)生成的圆弧样条曲线具有保形的特点 ;(2 )圆弧样条中圆弧的段数与型值点个数相同 ;(3)圆弧段之间的连接点不一定在插值的型值点上 ,这样就能用更多的自由度来控制拟合曲线的形状 .由此文中还提出了一个优化的算法来得到光顺的插值曲线 。

基于空间分解的三角网格模型求交方法

三角网格模型间的求交问题是计算机辅助设计与制造领域的关键问题之一。分析了已有空间分解技术和包围盒方法等的优缺点,并在此基础上提出了改进的空间分解求交方法。该算法能够精确定位三角形所占的空间网格,一定程度上减少了需要求交的三角形的数量。实验的结果表明,改进的算法提高了采用空间分解进行三角网格求交的计算效率。

改进的非线性全局映射灰度化方法

彩色图像灰度化的一个重要目标就是尽量保持原始彩色图像的边缘特征.基于三角级数逼近的非线性全局映射灰度化方法虽能较好地保持颜色顺序,且在很多情况下也保持了特征区分度,但在某些情况下仍会丢失或模糊边缘特征.为此,基于三角级数混合多项式逼近的思路,提出了改进的非线性全局映射灰度化方法.首先在三角级数逼近的基础上继续引入参数t和t2组合成最终的混合逼近函数,当t和t2前面的系数均为0时即为传统的灰度化方法;然后同时优化三角级数、t和t2前面的系数,以增强灰度图像的边缘特征.实验结果表明,在传统方法丢失或模糊边缘特征的情况下,采用文中方法也可以保持较好的边缘特征.

一种解析的反向运动学方法

针对多关节的反向运动学(IK)提出一种解析的求解方法,直接给出公式来求解关节链中所有待求关节的位置和旋转变量。同传统的迭代方法相比,该方法省却了繁琐的迭代计算,具有更高的求解效率,可以应用于角色动作、运动轨迹的设计、编辑及优化等交互性强和实时性要求高的应用中。

三角域上的Plateau-Bézier问题求解新方法

从极小曲面上平均曲率处处为零出发求解三角域上的Plateau-Bézier问题.首先提出了一种新的线性能量函数,称之为平均曲率平方能量.基于该能量函数的极小化,推导出了内部控制顶点应满足的充要条件.通过造型实例,与基于Dirichlet能量极小化的求解方法进行了比较,发现两者各有千秋.特别地,若给定的边界曲线恰巧为三角域上的调和Bézier曲面的边界曲线,则按照该方法所构造出的曲面便为调和曲面;若给定的边界曲线恰好为等温参数多项式极小曲面的边界曲线,则按照该方法便可重构出该极小曲面.

B样条曲线的等距算法及应用

等距曲线的拓扑结构是等距算法中的核心因素之一。该文以B样条曲线为例,给出了一种基于关键点的等距算法。它应用了自适应离散等手段并给出了关键点的求解方法,同时利用关键点确定等距线各个分段的取舍,从而有效地去除自交的情况,使得计算出的等距曲线有着正确的拓扑结构。该文的算法已应用于商业软件OpenCAD中。

旋转圆锥网格及其在玻璃/钢结构中的应用

圆锥网格是计算机辅助建筑设计中一类新的平面四边形网格,具有良好的等距性质,非常适用于玻璃/钢结构,而旋转曲面是建筑设计中的常用形状.通过引入旋转圆锥网格的概念,并利用圆锥网格的定义,给出了构造旋转圆锥网格的简单方法.证明了只在旋转曲面r(u,v)=(f(u)cosv,f(u)sinv,g(u))的v参数方向进行均匀分割,而在u参数方向进行任意分割,则所产生的平面四边形网格为圆锥网格;并研究了旋转曲面为圆锥曲面和圆柱曲面的特殊情况;最后给出了基于旋转圆锥网格的玻璃结构造型实例.该方法简单易行,对计算机辅助建筑设计中的玻璃/钢结构造型有一定的实际应用价值.