graphics - 吴小林算法中的端点计算是做什么的？

Question

Xiaolin Wu 算法在两点之间绘制抗锯齿线。这些点可以是亚像素，即非整数坐标。我假设读者熟悉算法并且只记得重要的特征。我们遍历这条线的长轴（长轴），假设它是 x 轴，基本上是逐列进行的。在每一列中，我们为两个像素着色。计算等价于：将一个 1x1 正方形以在线为中心放置在其 x 坐标为给定像素列的中心的点处。让我们称它为 S。如果我们将每个像素视为平面中的 1x1 正方形，我们现在计算 S 与其跨越的两个像素中的每一个之间的相交面积，并将这些面积用作为每个像素着色的强度.

这很好，很清楚，但是端点的计算发生了什么？因为端点可以在非整数位置，所以它们必须被视为一种特殊情况。这是来自链接的 Wikipedia 文章的伪代码，用于处理第一个端点 x0、y0：

// handle first endpoint
xend := round(x0)
yend := y0 + gradient * (xend - x0)
xgap := rfpart(x0 + 0.5)
xpxl1 := xend // this will be used in the main loop
ypxl1 := ipart(yend)
plot(ypxl1,   xpxl1, rfpart(yend) * xgap)
plot(ypxl1+1, xpxl1,  fpart(yend) * xgap)

我编辑了if (steep)条件，所以这是直线斜率小于 1 的情况的代码。rfpart是1-fpart，fpart是 小数部分。ipart是整数部分。

我只是不知道这个计算应该做什么，我在网上找不到任何解释。我可以看到这yend是上面那条线的 y 坐标xend，xend也是起点所在像素的 x 坐标(x0, y0)。为什么我们还要费心计算yend？就好像我们将这条线延伸到最接近的整数 x 坐标。

我意识到我们正在使用某些强度为端点所在的像素以及紧接其上方或下方的像素着色。我只是不明白这些强度的来源背后的逻辑。

标签： graphicsgeometryrasterantialiasingbresenham

Answer 1

使用 Xiaolin Wu 算法（以及一般的亚像素渲染技术），我们想象屏幕是一个连续的几何平面，每个像素都是该平面的 1x1 正方形区域。我们将像素的中心标识为具有整数坐标的点。

首先，我们找到线的所谓“长轴”，即线最长的轴。假设它是x轴。我们现在遍历该线通过的每个 1 像素宽的列。对于每一列，我们找到位于该列中心的线上的点，即 x 轴是一个整数。我们想象有一个 1x1 的正方形以该点为中心。该正方形将完全填满该列的宽度，并将重叠两个不同的像素。我们根据正方形和像素之间的重叠区域对这些像素中的每一个进行着色。

对于端点，我们做的事情略有不同：我们仍然画一个以直线与柱子中心线相交的地方为中心的正方形，但是我们在直线的端点沿水平方向切掉了这个正方形。如下图所示。

这是四个像素的放大视图。黑色十字代表这些像素的中心，红线是我们要绘制的线。红色圆圈(x0, y0)是直线的起点，直线应从该点向右延伸。

您可以看到以红十字为中心的灰色方块。每个像素将根据与这些正方形的重叠区域进行着色。但是，在左侧栏中，我们在 x-coordinate 处截断了正方形x0。浅灰色可以看到整个正方形，但只有深灰色的部分用于面积计算。可能还有其他方法可以处理端点，例如我们可以将深灰色区域向上移动一点，使其垂直居中于 y-coordinate y0。大概它不会产生太大的明显差异，而且这在计算上是有效的。

我使用维基百科上的伪代码中的变量名称对绘图进行了注释。