论文部分内容阅读
函数逼近和基于包围盒的裁剪是计算机图形学的基本问题,在几何造型系统和数值仿真等领域有着较为广泛的应用。本文研究了计算机图形学中基于不等式估算的若干算法,主要包括以下三点:(1)三角不等式的包围盒及应用前景。提出了一种两点Pade逼近方法,用于改进一些著名的三角不等式,包括Jordan不等式,Kober不等式,Becker-Stark不等式和Wu-Srivastava不等式,并为它们提供了简单的证明。数值实例表明,与普遍的方法相比,本文的方法可以获得更好的逼近结果,且得到的结果可望应用于K-均值聚类算法中。(2)研究了基于(1+x)1/x逼近的Carleman估计新方法。(1+z)1/x的边界逼近是提升Carleman估计的主要工具,而寻找界限和证明界限是不等式求解过程中的两个关键问题。本文以(1+x)1/x为例,提出了一种基于Pade逼近的方法,用于找到(1+x)1/x的双边界,它具有更好的逼近效果,并提供了一种新的证明方法。最后的数值结果表明它比已有方法的逼近误差小得多,并改善了 Carleman估计。得到结果同时也可以应用于对数透视阴影贴图算法(LogSM)。(3)研究了点到Bezier曲面的最近距离的计算方法。Bezier曲线、曲面点投影在计算机图形学与几何建模等领域具有广泛的应用。目前已有的细分剪枝算法能保证获得全局最优解,但该方法与快速收敛的牛顿迭代法相比,细分剪枝算法通常耗时更多。由此提出了结合二次曲面逼近的Bezier曲面点投影算法:首先,通过距离函数的控制网格信息,能够得到若干局部的极小控制点;其次,对于极小控制点的局部区域,二次曲面逼近用于估算相应的最小值及其对应的参数,以便更好地筛选和优化相应的初始值;最后,采用牛顿法和其它数值方法进行迭代获得全局最优解。本文使用的方法继承了细分剪枝法的优点,可以获取全局最优解,同时能够避免或显著减少耗时的剪枝过程。数值实例还表明,本文的方法比已有的细分剪枝方法有着更高的计算效率。