寻找快速多边形渲染算法

Question

我正在使用Microchip dsPIC33FJ128GP802.它是一个基于DSP的小型微控制器,它没有太多的功率(每秒4000万条指令).我正在寻找一种渲染凸(即简单)多边形的方法.我只处理2D形状,整数数学,以及设置或清除像素(即每像素1位).我已经有用于绘制快速水平和垂直线的例程(在88个周期内写入多达16个像素),所以我想使用扫描线算法.

但是,我发现的所有算法似乎都依赖于除法(在这个处理器上需要18个周期)和浮点数学(在软件中模拟,因此非常慢;它也占用了大量的ROM),或者假设我有大量的记忆.我只剩下2K,~14K用于我16K的图形RAM.那么有没有人知道任何好的嵌入式机器算法他们可以用简单的C或伪代码实现指向我,我可以在汇编中实现它？最好是在网上,我不住在附近有很多编程书籍的好书店附近.

谢谢.:)

编辑:澄清,这是我正在寻找的多边形填充算法.我可以使用Bresenham的线条绘制算法实现多边形轮廓算法(正如Marc B建议的那样).

编辑#2:我想让每个人都知道我在Python中得到了一个基本的算法.这是代码的链接.公共域代码.

http://dl.dropbox.com/u/1134084/bresenham_demos.py

Answer 1

如何布氏线算法？在一些设置之后,它是纯整数数学,并且可以通过沿多边形边缘的起始点的简单迭代来适应绘制多边形.

评论后续:

我将尝试用ASCII绘制它,但它可能看起来像crud.Bresenham可用于通过选择起始边缘绘制填充多边形,并在平行于该点的画布上迭代移动bresenham线.

假设你有这样的观点:

*(1)
                      *(3)

    *(2)         
                 *(4)

它们以左右排序优先级编号,因此您选择最左侧的起点(1)并决定是要垂直(开始1,2)还是水平(1,3).这可能取决于你的DSP如何显示它,但让我们选择垂直.

所以...你用1-2线作为你的起始线.您可以使用第1-3和第2-4行作为起点/终点来计算填充线的起点.开始每个人的bresenham计算,并在这两个点之间绘制另一个Bresenham.有点像:

1.1 -> 2.1, then 1.2 -> 2.2, then 1.3 -> 2.3

等......直到你到达任何一条线的末尾.在这种情况下,那就是当较低的起点达到(4)时.此时,你开始迭代4,3线,直到你用两个起点到达第3点,然后你就完成了.

*-------
 \\\\\\\\              *
  \\\\\\\\ 
   *-----\\         
         -------  *

短划线是您沿1-3和2-4计算的起点,斜线是填充线.

当然,这只适用于正确排序的点,并且你有一个凸多边形.如果它是凹的,你必须非常小心,不要让你的填充线跨越边界,或做一些预处理并将原始多边形细分为两个或多个凸面.