寻找一种快速的多边形渲染算法

Question

我正在使用Microchip dsPIC33FJ128GP802进行工作。它是一个小型的基于DSP的微控制器，功率不足（每秒40亿条指令）。我正在寻找一种渲染凸多边形（即简单多边形）的方法。我只涉及2D形状、整数运算和设置或清除像素（即每个像素1比特）。我已经有了快速绘制水平和垂直线的例程（在88个周期内写入多达16个像素），所以我想使用扫描线算法。

然而，我找到的所有算法似乎都依赖于除法（在这个处理器上需要18个周期）和浮点数学（在软件中模拟，因此非常慢；它还占用了很多ROM），或者假定我有大量的内存。我只剩下2K，我的16K中有约14K用于图形RAM。那么，有没有人知道任何好的、嵌入式机器算法，他们可以指向一个简单的C或伪代码实现，我可以在汇编中实现呢？最好是在互联网上，我住的地方附近没有好的书店有很多编程书籍。

谢谢。:)

编辑：澄清，我正在寻找的是多边形填充算法。我可以使用Bresenham的线绘制算法实现多边形轮廓算法（如Marc B所建议的）。

编辑#2：我想让大家知道，我在Python中实现了一个基本算法。这里是代码链接。公共领域代码。 http://dl.dropbox.com/u/1134084/bresenham_demos.py

- Thomas O

---

请看我的评论，针对Marc的回答。 - Heath Hunnicutt

不是完整的答案，但是http://www.cpp-home.com/tutorials/221_1.htm看起来并不太复杂或资源密集。 - Earlz

Answer 1

您觉得使用Bresenham直线算法如何？在一些设置后，这是纯整数运算，并且可以通过沿着多边形边缘的起始点进行简单迭代来适应绘制多边形。

评论如下：

我将尝试用ASCII画出来，但可能看起来很糟糕。可以通过选择一个起始边缘，并迭代地将Bresenham线平行移动到该点来使用Bresenham绘制填充多边形。

假设您有以下一些点：

*(1)
                      *(3)

    *(2)         
                 *(4)

这些数字按从左到右的优先级排序，因此您选择最左边的起点（1），然后决定是要垂直移动（从1开始，2结束）还是水平移动（从1开始，3结束）。这可能取决于DSP显示方式，但我们选择垂直移动。 所以...您使用1-2行作为起始bresenham线。通过使用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的起点，斜杠代表填充线。

当然，这仅适用于正确排序的点和凸多边形。如果是凹多边形，则必须非常小心，以免填充线越过边界，或进行一些预处理并将原始多边形细分为两个或更多凸多边形。

- Marc B

---

哎呀，我想我表达不够清楚。我需要一个多边形填充算法。我会编辑帖子以反映这一点。 - Thomas O

@Thomas - 我希望Marc能得到被接受的答案。如果我使用Bresenham的建议，我会感觉像是偷窃他的建议。在我的长评论中，你永远不会渲染除了垂直线以外的任何东西。你使用Bresenham计算边缘的y1和y2，但你正在为相同的x计算--一条垂直线。这可能导致需要特殊处理具有垂直线的邻居，因此我也加入了这个。但关键点是你沿着边缘进行Bresenham（你必须已经以某种方式迭代），并且只通过垂直光栅来渲染。你可以轻松地将其转换为... - Heath Hunnicutt

再次感谢您的澄清。我将阅读一些相关内容，希望能尽快实现基本版本。为了澄清，我正在开发一个基于软件的PAL/NTSC视频叠加项目。256x192像素水平排列，每个单词以小端方式存储，有两个6KB的帧缓冲区。这个项目很可能也会成为一个开源硬件/软件项目。如果要获得图形OSD，需要花费约259英镑，但我只用了大约10英镑的零件和几周的编码就建立了一个。 - Thomas O

我可以悄悄地插进来说一声，这是一个史诗般、令人愉悦和富有洞见的帖子。这就是为什么我喜欢 Stack Overflow！ :-) - corsiKa

@Thomas -- 听起来你已经有了一个产品。需要美国的分销商吗？ :) - Heath Hunnicutt

Answer 2

你可能想看看Michael Abrash在Dr Dobbs上关于多边形填充/光栅化等的文章。它使用固定点数学。

- Jaime

Answer 3

如果你有Bresenham线绘制算法可用，那么请将其用作进一步增强的基础：通过每个顶点进行水平切割，将多边形分成子多边形。然后，使用Bresenham跟踪每个子多边形的左右两侧。这样，你就可以得到多边形中每条扫描线的两个端点。

- ysap

Answer 4

将问题分为两个部分可能更容易。首先，找到/编写一个绘制和填充三角形的算法。其次，编写一个算法将任意多边形分解成三角形（使用不同顶点的组合）。

要绘制/填充三角形，请使用 Bresenham 的线算法，在点 0 和点 1 之间以及点 1 和点 2 之间同时绘制一条线。对于每个输入点 x，如果它等于或在两条线生成的 y 点之间，则绘制像素。当到达一个端点时，通过使用未完成的边和尚未使用的边来继续。

编辑： 要将凸多边形分解成三角形，请按顺序排列点并称其为P1、P2、......PN。让P1成为您的“根”点，并使用该点和相邻点的组合构建三角形。例如，一个五边形会产生三个三角形P1-P2-P3，P1-P3-P4和P1-P4-P5。通常，一个具有N条边的凸多边形将分解为N-2个三角形。

- bta

---

OP说他想渲染凸多边形；在这种情况下三角剖分很容易。 - lhf

@lhf- 一个凸多边形可以被分解成三角形。如果你有一个优化的三角形绘制例程，并且你可以将你的形状分解成三角形，那么你就可以绘制这个形状。 - bta

Answer 5

我会先将多边形转换为三角形集合并渲染它们，因为三角形很容易通过扫描线进行渲染。尽管即使如此还有一些细节需要注意。

基本上，draw-triangle子过程将接收一个原始三角形并进行以下操作：

1. 拒绝退化的三角形（其中三个顶点中有两个重叠）。
2. 按Y值对顶点进行排序（由于只有三个顶点，您可以硬编码排序逻辑）。
3. 现在，在这一点上，您应该知道将有三种类型的三角形：具有平顶部分的、具有平底部分的和“一般”三角形。您希望通过将其分成每种平面类型的一个来处理一般的三角形。这是因为您不想在每个扫描线上都进行一个if测试以检测斜率是否改变。
4. 要渲染一个平面三角形，您将同时运行两个Bresenham算法来迭代组成边缘的像素，并使用它们给出的点作为每个水平扫描线的端点。

- Nietzche-jou