1

我参加了图形信息学考试，我正在尝试理解 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，我只是将它用于测试目的。

4

2 回答 2

1

正如您可能知道的那样，布雷森汉姆式算法背后的基本思想是您正在采取一系列固定的步骤，并且在每个步骤中您都在做出决定。在这种特殊情况下，步骤是x10 到 20 之间的位置，决定下一个y值应该是y还是y - 1。

要做出此决定，您需要选择最接近下一个x坐标的函数值的 y 值：100 / (x + 1)。因此，您选择yifdist(y, 100 / (x + 1))小于dist(y - 1, 100 / (x + 1))... 否则，选择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交换vs.y - 1决定的含义
  • 决定使用更新前与更新后的值来计算决策值x和y
  • 想要绘制与函数中心最近的像素与坐标最近的像素

小提琴示例：https ://jsfiddle.net/0e8fnk5h/

于 2019-04-10T04:07:18.970 回答
0

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

FM = 2 * F(x1 + 1, y1 + 1/2)
   = 2 * [(x1 + 1) * (y1 + 1/2) - 100]
   = 2 * x1 * y1 + 2 * y1 + x1 - 199
于 2019-04-10T02:50:25.550 回答