How to initialise the Bresenham algorithm to display an hyperbole

Question

I have an exam in graphics informatic and I am trying to understand the Bresenham algorithm. I understand displaying a line and a circle (I think) but when I do an exercise where I have to display a hyperbolic function I can't make it right.

The hyperbolic function has the equation y = 100/x and I converted it to x*y - 100 = 0. I assume that the currently displayed pixel is at (x_p, y_p) on the screen. I calculated the increments and I found I = 2y_p - 1 when the pixel to be displayed is the one at the right, and I = 2y_p - 2x_p - 5 when the pixel to be displayed is at the bottom right. But now I don't know how to initialise. In my courses, the initialisation for a line is made at x_0 = 0, y_0 = 0, for a circle of a radius R, it is x_0 = 0, y_0 = R, but what is it for my hyperbole ?

I want to trace the hyperbole from x = 10 up to 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);
  }
}

so I called this function like that :

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

I know it is old OpenGL, I use it just for testing purposes.

Joe Lee Joe Lee · Accepted Answer · 2019-04-10T04:07:18

As you're probably aware, the basic idea behind Bresenham-style algorithms is that you're taking a series of fixed steps, and at each step you're making a decision. In this particular case, the steps are x positions between 10 and 20, and the decision is whether the next y value should be y or y - 1.

To make this decision, you want to pick the y value that's going to be closest to the function value for the next x coordinate: 100 / (x + 1). So, you pick y if dist(y, 100 / (x + 1)) is smaller than dist(y - 1, 100 / (x + 1))... otherwise, pick y - 1. That decision is equivalent to deciding whether the following expression is negative:

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

Since x + 1 is positive for the range we are interested in, we can multiply through by it to get an equivalent decision value:

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

This is the decision value you want to use for each step, so it's also the formula you'd want to use to calculate the initial decision value. You can then calculate err(x + 1, y) - err(x, y) and err(x + 1, y - 1) - err(x, y) to get the incremental update formulas to be used in the loop.

There are, of course, other formulas that will also work, and any given formula may need some adaption if you:

swap the meaning of the y vs. y - 1 decision
decide to compute the decision value using the pre-update vs. post-update values of x and y
want to draw pixels with the closest centers to the function vs. pixels with the closest coordinate

Sample fiddle: https://jsfiddle.net/0e8fnk5h/

How to initialise the Bresenham algorithm to display an hyperbole

2 Answers