寻找快速多边形渲染算法

发布于 2024-09-13 18:57:12 字数 697 浏览 4 评论 0原文

我正在使用 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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

小嗲 2024-09-20 18:57:12

Bresenham 线算法怎么样？经过一些设置后，它是纯整数数学，并且可以通过沿多边形边缘简单迭代起点来绘制多边形。

评论后续：

我会尝试用 ASCII 来绘制它，但它可能看起来像 CRUD。 Bresenham 可用于通过选取起始边并在画布上平行于该点迭代移动 Bresenham 线来绘制填充多边形。

假设您有一些像这样的点：

这些点按左右排序优先级编号，因此您选择最左边的起点 (1) 并决定是否要垂直（从 1,2 开始）或水平（ 1,3）。这可能取决于您的 DSP 如何进行显示，但我们选择垂直。

所以...您使用 1-2 线作为布雷森纳姆的起始线。您可以使用线 1-3 和 2-4 作为起点/终点来计算填充线的起点。对每个点开始布雷森纳姆计算，并在这两点之间绘制另一个布雷森纳姆。有点像：

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

等等......直到你到达这两行的末尾。在这种情况下，那就是下起点达到 (4) 时。此时，您开始迭代 4,3 行，直到两个起点都到达点 3，然后就完成了。

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

其中，虚线是沿 1-3 和 2-4 计算的起点，斜线是填充线。

当然，这只有在点被正确排序并且你有一个凸多边形的情况下才有效。如果它是凹的，您必须非常小心，不要让填充线越过边界，或者进行一些预处理并将原始多边形细分为两个或多个凸多边形。

How about Bresenham's Line algorithm? After some setup, it's pure integer math, and can be adapted to draw a polygon by simple iteration of starting points along the polygon edges.

comments followup:

I'll try to draw this in ASCII, but it'll probably look like crud. Bresenham's can be used to draw a filled polygon by picking a starting edge, and iteratively moving a bresenham line across the canvas parallel to that point.

Let's say you've got some points like this:

These are numbered in left-right sort priority, so you pick the left-most starting point (1) and decide if you want to go vertically (start 1,2) or horizontally (1,3). That'd probably depend on how your DSP does its display, but let's go with vertical.

So... You use the 1-2 line as your starting bresenham line. You calculate the starting points of your fill lines by using lines 1-3 and 2-4 as your start/end points. Start a bresenham calculation for each, and draw another Bresenham between those two points. Kinda like:

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

etc... until you reach the end of either of those lines. In this case, that'd be when the lower starting point reaches (4). At that point, you start iterating up the 4,3 line, until you reach point 3 with both starting points, and you're done.

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

Where the dashes are the starting points you calculated along 1-3 and 2-4, and the slashes are the fill lines.

Of course, this only works if the points are properly sorted, and you've got a convex polygon. If it's concave, you'll have to be very careful to not let your fill lines cross over the border, or do some pre-processing and subdivide the original poly into two or more convex ones.

回复收藏 0 原文

蓦然回首 2024-09-20 18:57:12

您可能需要查看 Michael Abrash 的文章，关于 Dobbs 博士有关多边形填充的文章/光栅/等它使用定点数学

回复收藏 0 原文

慕烟庭风 2024-09-20 18:57:12

托马斯，如果您有可用的 Bresenham 线条绘制算法，请使用它作为进一步增强的基础：使用穿过每个顶点的水平切割线将多边形划分为子多边形。然后，使用 Bresenham 开始追踪每个子多边形的 2 个左侧和右侧。这样，您的多边形中就有了每条扫描线的 2 个端点。

回复收藏 0 原文

童话 2024-09-20 18:57:12

我首先将多边形转换为三角形的集合并渲染它们，因为三角形很容易通过扫描线渲染。尽管如此，还是有一些细节。

本质上，draw-triangle 子过程将获得一个原始三角形并继续：

拒绝退化三角形（其中三个顶点中的两个重叠）。
对 Y 中的顶点进行排序（因为只有三个，您可以对排序逻辑进行硬编码）。
现在，你应该知道，三角形分为三种：平顶三角形、平底三角形和“一般”三角形。您希望通过将一般三角形拆分为每种平面类型来处理它。这是因为您不想对每个扫描线进行 if 测试来检测斜率是否发生变化。
要渲染平面三角形，您可以并行运行两个 Bresenham 算法来迭代构成边缘的像素，并使用它们提供的点作为每条水平扫描线的端点。

回复收藏 0 原文

壹場煙雨 2024-09-20 18:57:12

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

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

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