寻找一种快速的多边形绘制算法

Bresenham's

后续意见:

我试着用ASCII来画这个,但它可能看起来像积垢。Bresenham's可以用来绘制一个填充多边形,方法是拾取一个起始边,然后在画布上迭代移动一条与该点平行的Bresenham线。

*(1)
                      *(3)

    *(2)         
                 *(4)

所以。。。你用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计算的起点,斜线是填充线。

你可以看看 Michael Abrash's articles 关于Dobbs博士关于多边形填充/光栅等,它使用定点数学

托马斯,如果你有一个Bresenham线绘制算法可用,那么使用它作为进一步增强的基础:用一条横切线穿过每个顶点,将多边形划分为子多边形。然后,使用Bresenham开始跟踪这些子多边形的左右两侧。这样你就有了多边形中每条扫描线的2个端点。

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

draw-triangle

1. 拒绝退化三角形(三个顶点中的两个重叠)。
3. if
4. 要渲染一个平面三角形,您可以并行运行两个Bresenham算法来迭代包含边的像素,并使用它们提供给您的点作为每个水平扫描线的端点。

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

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

编辑: P1, P2, ... PN . 让 P1 P1-P2-P3 , P1-P3-P4 ,和 P1-P4-P5 . 一般来说,凸多边形 N N-2 三角形。