如何初始化 Bresenham 算法以显示双曲线

Question

我参加了图形信息学考试，我想了解 Bresenham 算法。我理解显示一条线和一个圆（我认为），但是当我做一个必须显示双曲线函数的练习时，我做不对。

双曲线函数的方程为 y = 100/x，我将其转换为 x*y - 100 = 0。我假设当前显示的像素位于 (x_p, y_p ）屏幕上。我计算了增量，发现 I = 2y_p - 1 当要显示的像素是右边的像素时， I = 2y_p - 2x_p - 5 当要显示的像素位于右下角。但是现在我不知道如何初始化。在我的课程中，一条线的初始化是在 x_0 = 0，y_0 = 0，对于半径为 R 的圆，它是 x_0 = 0，y_0 = R，但我的夸张有什么用？

我想追踪从 x = 10 到 x = 20 的双曲线

void trace (const int x1, const int y1, const int x2)
{
  int x = x1;
  int y = y1;
  int FM = //what to put here ???
  glVertex2i(x,y);

  while (x < x2)
  {
    if (FM < 0)
    {
      ++x; --y;
      const int dSE = 2*y - 2*x - 5;
      FM += dSE;
    }
    else
    {
      ++x;
      const int dE = 2*y - 1;
      FM += dE;
    }

    glVertex2i(x,y);
  }
}

所以我这样调用这个函数:

glBegin(GL_POINTS);
    trace(10,10,20);
glEnd();

我知道它是旧的 OpenGL，我只是为了测试目的使用它。

Answer 1

控制变量FM必须初始化为第一个中点到曲线的距离。在这种情况下，您用隐函数值的两倍来测量距离，即我们有

FM = 2 * F(x1 + 1, y1 + 1/2)
   = 2 * [(x1 + 1) * (y1 + 1/2) - 100]
   = 2 * x1 * y1 + 2 * y1 + x1 - 199

Answer 2

您可能已经知道，Bresenham 式算法背后的基本思想是您采取一系列固定步骤，并且在每一步中您都在做出决定。在这种特殊情况下，步骤是 10 到 20 之间的 x 个位置，决定是下一个 y 值应该是 y 还是 y - 1.

要做出此决定，您需要选择最接近下一个 x 坐标的函数值的 y 值：100 / (x + 1)。因此，如果 dist(y, 100 / (x + 1)) 小于 dist(y - 1, 100 / (x + 1))，则选择 y...否则，选择 y - 1。该决定等同于决定以下表达式是否为负数：

err(x, y) = (y - 100 / (x + 1)) ^ 2 - (y - 1 - 100 / (x + 1)) ^ 2
          = 2 * (y - 100 / (x + 1)) - 1
          = 2 * y - 200 / (x + 1) - 1

由于x + 1对于我们感兴趣的范围是正的，我们可以乘以它得到一个等效的决策值：

err(x, y) = 2 * y * x + 2 * y - 200 - x - 1
          = 2 * y * x + 2 * y - x - 201

这是您要用于每个步骤的决策值，因此它也是您要用来计算初始决策值的公式。然后您可以计算 err(x + 1, y) - err(x, y) 和 err(x + 1, y - 1) - err(x, y) 以获得要在循环中使用的增量更新公式。

当然，还有其他公式也适用，如果您满足以下条件，则任何给定的公式都可能需要进行一些调整：

交换 y 与 y - 1 决定的含义
决定使用 x 和 y
想要绘制中心距函数最近的像素与坐标最近的像素

示例 fiddle：https://jsfiddle.net/0e8fnk5h/

如何初始化 Bresenham 算法以显示双曲线

How to initialise the Bresenham algorithm to display an hyperbole

graphics

bresenham

hyperbolic-function