java - 实现 Bresenham 的圆形绘制算法

Question

我已经编写了 Bresenham 圆绘制算法的实现。 该算法利用了圆的高度对称性(它仅从第一个八分圆计算点，并利用对称性绘制其他点)。因此我期待它会非常快。图形编程黑皮书，第 35 章的标题是“Bresenham 快，快就是好”，虽然它是关于画线算法的，但我可以合理地期望画圆算法也是快(因为原理是一样的)。

这是我的java，swing实现

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);
    }   
}

此方法使用以下drawPoint方法:

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);
}

getNativeX 和 getNativeY 这两个方法用于将坐标从屏幕左上角的原点切换到以面板中心为原点的系统，具有更经典的轴方向。

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

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

我还创建了一个基于三角公式(x=R*Math.cos(angle)和y= R*Math.sin(angle))的圆绘制算法的实现) 和调用标准 drawArc 方法(在 Graphics 对象上可用)的第三种实现。这些附加实现的唯一目的是将 Bresenham 算法与它们进行比较。

然后我创建了绘制一堆圆圈的方法，以便能够很好地衡量所花费的时间。这是我使用 Bresenham 算法绘制一堆圆圈的方法

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;
    }
}

最后，我重写了我正在使用的 JPanel 的 paint 方法，以绘制一堆圆圈并测量绘制每种类型所花费的时间。这是绘画方法:

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");
}

这是它会生成的渲染类型(每种类型绘制 1000 个圆圈)

不幸的是，我的 Bresenham 的实现速度非常慢。我采取了很多比较措施，Bresenham 的实现不仅比 Graphics.drawArc 慢，而且比三角方法慢。查看以下针对绘制的不同数量的圆圈的度量。

我实现的哪一部分更耗时？有什么解决方法可以用来改进它吗？感谢您的帮助。

[EDITION]:应@higuaro 的要求，这是我画圆的三角算法

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;
    }
}

以及用来画一堆三角圆的方法

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;
    }
}

Answer 1

您的 Bresenham 方法本身并不慢，只是相对较慢。

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

但是，您的三角函数法快得不必要，因为您没有在同等基础上将它与 Bresenham 进行比较。

trig 方法设置的角度分辨率为 PI/36(~4.7 度)，如 for 语句末尾的操作所示:

angle = angle + Math.PI/36  

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

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

在循环之外的某个地方，并增加你的 for ，如下所示:

angle += resolution

由于我们现在将回到像素级分辨率，您实际上可以改进 trig 方法并删除后续的 drawline 调用和分配给 x0 和 y0，消除不必要的转换，并进一步减少对 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);
    }

}

根据 r 的大小，trig 方法现在的执行频率将提高几个数量级。

我很想看看您的结果。