13

I have written an implementation of Bresenham's circle drawing algorithm. This algorithms takes advantage of the highly symmetrical properties of a circle (it only computes points from the 1st octant and draws the other points by taking advantage of symmetry). Therefore I was expecting it to be very fast. The Graphics programming black book, chapter #35 was titled "Bresenham is fast, and fast is good", and though it was about the line drawing algorithm, I could reasonably expect the circle drawing algorithm to also be fast (since the principle is the same).

Here is my java, swing implementation

public static void drawBresenhamsCircle(int r, double width, double height, Graphics g) {
    int x,y,d;
    y = r;
    x = 0;

    drawPoint(x, y, width, height,g);
    d = (3-2*(int)r);
    while (x <= y) {
        if (d <= 0) {
            d = d + (4*x + 6);
        } else {
            d = d + 4*(x-y) + 10;
            y--;
        }
        x++;

        drawPoint(x, y, width, height,g);

        drawPoint(-x, y, width, height,g);
        drawPoint(x, -y, width, height,g);

        drawPoint(-x, -y, width, height,g);
        drawPoint(y, x, width, height,g);
        drawPoint(-y, x, width, height,g);
        drawPoint(y, -x, width, height,g);

        drawPoint(-y, -x, width, height,g);
    }   
}

This method uses the following drawPointmethod:

public static void drawPoint(double x, double y,double width,double height, Graphics g) {
    double nativeX = getNativeX(x, width);
    double nativeY = getNativeY(y, height);
    g.fillRect((int)nativeX, (int)nativeY, 1, 1);
}

The two methods getNativeX and getNativeY are used to switch coordinates from originating in the upper left corner of the screen to a system that has it origin in the center of the panel with a more classic axis orientation.

public static double getNativeX(double newX, double width) {
    return newX + (width/2);
}

public static double getNativeY(double newY, double height) {
    return (height/2) - newY;
}

I have also created an implementation of a circle drawing algorithm based on trigonometrical formulaes (x=R*Math.cos(angle)and y= R*Math.sin(angle)) and a third implementation using a call to the standard drawArc method (available on the Graphics object). These additional implementations are for the sole purpose of comparing Bresenham's algorithm to them.

I then created methods to draw a bunch of circles in order to be able to get good measures of the spent time. Here is the method I use to draw a bunch of circles using Bresenham's algorithm

public static void drawABunchOfBresenhamsCircles(int numOfCircles, double width, double height, Graphics g) {
    double r = 5;
    double step = (300.0-5.0)/numOfCircles;

    for (int i = 1; i <= numOfCircles; i++) {
        drawBresenhamsCircle((int)r, width, height, g);
        r += step;
    }
}

Finally I override the paint method of the JPanel I am using, to draw the bunch of circles and to measure the time it took each type to draw. Here is the paint method:

public void paint(Graphics g) {
    Graphics2D g2D = (Graphics2D)g;

    g2D.setColor(Color.RED);

    long trigoStartTime = System.currentTimeMillis();
    drawABunchOfTrigonometricalCircles(1000, this.getWidth(), this.getHeight(), g);
    long trigoEndTime = System.currentTimeMillis();
    long trigoDelta = trigoEndTime - trigoStartTime;

    g2D.setColor(Color.BLUE);

    long bresenHamsStartTime = System.currentTimeMillis();
    drawABunchOfBresenhamsCircles(1000, this.getWidth(), this.getHeight(), g);
    long bresenHamsEndTime = System.currentTimeMillis();
    long bresenDelta = bresenHamsEndTime - bresenHamsStartTime;

    g2D.setColor(Color.GREEN);

    long standardStarTime = System.currentTimeMillis();
    drawABunchOfStandardCircles(1000, this.getWidth(), this.getHeight(),g);
    long standardEndTime = System.currentTimeMillis();
    long standardDelta = standardEndTime - standardStarTime;

    System.out.println("Trigo : " + trigoDelta  + " milliseconds");
    System.out.println("Bresenham :" + bresenDelta +  " milliseconds");
    System.out.println("Standard :" + standardDelta +  " milliseconds");
}

Here is the kind of rendering it would generate (drawing 1000 circles of each type)

Bresenham and other methods

Unfortunately my Bresenham's implementation is very slow. I took many comparatives measures, and the Bresenham's implementation is not only slower than the Graphics.drawArcbut also slower than the trigonometrical approach. Take a look at the following measures for a various number of circles drawn.

What part of my implementation is more time-consuming? Is there any workaround I could use to improve it? Thanks for helping.

Comparing Bresenham to other implementations

[EDITION]: as requested by @higuaro, here is my trigonometrical algorithm for drawing a circle

public static void drawTrigonometricalCircle (double r, double width, double height, Graphics g) {

    double x0 = 0;
    double y0 = 0;
    boolean isStart = true;

    for (double angle = 0; angle <= 2*Math.PI; angle = angle + Math.PI/36) {

        double x = r * Math.cos(angle);
        double y = r * Math.sin(angle);

        drawPoint((double)x, y, width, height, g);

        if (!isStart) {
            drawLine(x0,  y0, x, y, width, height, g);
        }

        isStart = false;

        x0 = x;
        y0 = y;
    }
}

And the method used to draw a bunch of trigonometrical circles

public static void drawABunchOfTrigonometricalCircles(int numOfCircles, double width, double height, Graphics g) {

    double r = 5;
    double step = (300.0-5.0)/numOfCircles;

    for (int i = 1; i <= numOfCircles; i++) {
        drawTrigonometricalCircle(r, width, height, g);
        r += step;
    }
}
4

3 回答 3

4

您的 Bresenham 方法本身并不慢,只是比较慢。

Swing 的drawArc()实现依赖于机器,使用本机代码。你永远不会用 Java 打败它,所以不要费心去尝试。(实际上,我很惊讶 Java Bresenham 方法与它相比的速度如此之快,这drawArc()证明了执行 Java 字节码的虚拟机的质量。)

但是,您的三角法速度过快,因为您没有在同等基础上将其与 Bresenham 进行比较。

trig 方法具有(~4.7 度)的设置角分辨率,如语句PI/36末尾的此操作:for

angle = angle + Math.PI/36  

同时,您的 Bresenham 方法依赖于半径,在每个像素变化时计算一个值。当每个八分圆产生sqrt(2)点时,将其乘以8除以2*Pi将为您提供等效的分辨率。因此,要与 Bresenham 方法处于同等地位,您的 trig 方法应该具有:

resolution = 4 * r * Math.sqrt(2) / Math.PI;

在循环之外的某个地方,并for通过它增加你的值,如下所示:

angle += resolution

由于我们现在将回到像素级分辨率,因此您实际上可以改进 trig 方法并减少对 and 的后续drawline调用和分配x0y0消除不必要的强制转换,并进一步减少对 的调用Math。这是整个新方法:

public static void drawTrigonometricalCircle (double r, double width, double height, 
    Graphics g) {

    double localPi = Math.PI;
    double resolution = 4 * r * Math.sqrt(2) / Math.PI;

    for (double angle = 0; angle <= localPi; angle += resolution) {
        double x = r * Math.cos(angle);
        double y = r * Math.sin(angle);
        drawPoint(x, y, width, height, g);
    }

}

trig 方法现在的执行频率将增加几个数量级,具体取决于r.

我很想看看你的结果。

于 2015-04-08T02:41:40.483 回答
3

您的问题在于 Bresenham 的算法根据圆的大小进行可变次数的迭代,而您的三角法总是进行固定次数的迭代。

这也意味着 Bresenham 的算法总是会产生一个看起来很光滑的圆,而随着半径的增加,你的三角法会产生看起来更差的圆。

为了使它更均匀,改变三角法以产生大约与 Bresenham 实现一样多的点,您将看到它的速度有多快。

我编写了一些代码来对此进行基准测试并打印产生的点数,这是初始结果:

三角函数:181 毫秒,平均 73 分
Bresenham:120 毫秒,平均 867.568 分

在修改三角函数类以进行更多迭代以获得更平滑的圆之后:

    int totalPoints = (int)Math.ceil(0.7 * r * 8);
    double delta = 2 * Math.PI / totalPoints;
    for (double angle = 0; angle <= 2*Math.PI; angle = angle + delta) {

这些是结果:

三角函数:2006 毫秒,平均 854.933 分
Bresenham:120 毫秒,平均 867.568 分

于 2015-04-08T03:23:28.963 回答
0

我最近为 sprite rasterizer 自己编写了一个 bresenham circle 绘图实现,并尝试对其进行一些优化。我不确定它是否会比你做的更快或更慢,但我认为它应该有一个相当不错的执行时间。

不幸的是,它是用 C++ 编写的。如果我明天有时间,我可能会使用移植的 Java 版本和结果的示例图片来编辑我的答案,但现在你必须自己做,如果你愿意(或者其他想花时间编辑它的人) .)

基本上,它所做的是使用 bresenham 算法获取圆外边缘的位置,然后对圆的 1/8 执行该算法,并通过从中心绘制直线来镜像其余 7 个部分到外边缘。

Color只是一个 rgba 值

Color* createCircleColorArray(const int radius, const Color& color, int& width, int& height) {
  // Draw circle with custom bresenham variation
  int decision = 3 - (2 * radius);
  int center_x = radius;
  int center_y = radius;
  Color* data;

  // Circle is center point plus radius in each direction high/wide
  width = height = 2 * radius + 1;
  data = new Color[width * height];

  // Initialize data array for transparency
  std::fill(data, data + width * height, Color(0.0f, 0.0f, 0.0f, 0.0f));

  // Lambda function just to draw vertical/horizontal straight lines
  auto drawLine = [&data, width, height, color] (int x1, int y1, int x2, int y2) {
    // Vertical
    if (x1 == x2) {
      if (y2 < y1) {
        std::swap(y1, y2);
      }

      for (int x = x1, y = y1; y <= y2; y++) {
        data[(y * width) + x] = color;
      }
    }

    // Horizontal
    if (y1 == y2) {
      if (x2 < x1) {
        std::swap(x1, x2);
      }

      for (int x = x1, y = y1; x <= x2; x++) {
        data[(y * width) + x] = color;
      }
    }
  };

  // Lambda function to draw actual circle split into 8 parts
  auto drawBresenham = [color, drawLine] (int center_x, int center_y, int x, int y) {
    drawLine(center_x + x, center_y + x, center_x + x, center_y + y);
    drawLine(center_x - x, center_y + x, center_x - x, center_y + y);
    drawLine(center_x + x, center_y - x, center_x + x, center_y - y);
    drawLine(center_x - x, center_y - x, center_x - x, center_y - y);
    drawLine(center_x + x, center_y + x, center_x + y, center_y + x);
    drawLine(center_x - x, center_y + x, center_x - y, center_y + x);
    drawLine(center_x + x, center_y - x, center_x + y, center_y - x);
    drawLine(center_x - x, center_y - x, center_x - y, center_y - x);
  };

  for (int x = 0, y = radius; y >= x; x++) {
    drawBresenham(center_x, center_y, x, y);

    if (decision > 0) {
      y--;
      decision += 4 * (x - y) + 10;
    }
    else {
      decision += 4 * x + 6;
    }
  }

  return data;
}

//编辑
哦,哇,我才意识到这个问题有多老了。

于 2020-02-18T01:52:51.570 回答