|
#2
RockCarry2007-12-01 17:28
|
贝塞尔曲线在计算机图形学中有详细的介绍，但是许多教材写得太过晦涩难懂，而且基本上是纯理论的研究。我曾经认真研读过计算机图形学中有关贝塞尔曲线的相关内容，但是书本上并没有给出有效的工程化实现的方法。许多书本上给出的算法或者是通用性不强或者就是效率低下。在网上搜索了很久，也始终没有找到一个真正高效的贝塞尔曲线绘制算法。
因此，我在仔细研究和分析了贝塞尔曲线的相关理论和算法以后，实现了以下的几个贝塞尔曲线的绘制算法：
PolyBezierPD: 基于 casteljau 算法，采用了浮点运算和递归实现
FastPolyBezierPD: 基于 casteljau 算法，采用了整数运算和递归实现
NonRecurPolyBezierPD: 基于 casteljau 算法，采用了整数运算和非递归实现（效率最高）
PolyBezierPN: 基于 casteljau 算法，采用了浮点运算和参数化的计算方法
这四个算法都是基于 casteljau 实现的，因为 casteljau 方法可以很容易的实现任意阶的贝塞尔曲线，而普通的参数方程计算方法则只能实现固定阶数的贝塞尔曲线。最容易理解的应该是 PolyBezierPN 算法，它采用了 casteljau 的参数计算形式，根据参数 t 来计算出每一个曲线上的点。而其他三个算法都是采用了控制多边形的无限分割和逼近的思想。这个分割的思想很容易通过递归函数来实现。但是在许多情况下，递归实现的效率不高，并且可能会带来某些不确定的问题，因此，我又实现了一个非递归的版本。NonRecurPolyBezierPD 应该是效率最高的实现了，非递归的实现，并且将桴点运算改为了整数运算。
其中参数 pd 的含义是指曲线上两个相邻点之间的距离，如果 pd == 1, 则将绘制出连续的曲线参数 pn 的含义是在曲线上绘制的总的点数，PolyBezierPN 函数需要传入这个参数，这个参数可以根据控制多边形的长度来估算。
如果是要用于工程上，效率最好，最实用的还是 NonRecurPolyBezierPD 算法。代码写得很清晰，也不需要太多的注释。许多地方是极为巧妙的，请大家认真品味，一定会有收获的。注意体会从浮点运算转为整数运算的方法，以及从递归转为非递归实现的方法。
RockCarry
2007-12-1