实施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()实现是依赖于机器的，使用本机代码。使用 Java 永远无法打败它，所以不必费心去尝试。（实际上，我很惊讶 Java Bresenham 方法与 相比，速度如此之快drawArc()，这证明了执行 Java 字节码的虚拟机的质量。）

然而，您的三角方法不必要地快，因为您没有将其与布雷森纳姆在平等的基础上进行比较。

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其递增 your ，如下所示：

angle += resolution

由于我们现在将回到像素级分辨率，因此您实际上可以改进 trig 方法并删除对和的后续drawline调用和赋值，消除不必要的强制转换，并进一步减少对 的调用。这是新方法的全部内容：x0y0Math

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。

我很想看看你的结果。

Answer 2

您的问题在于布雷森纳姆算法根据圆的大小进行可变次数的迭代，而您的三角方法始终进行固定次数的迭代。

这也意味着布雷森纳姆算法将始终产生看起来平滑的圆，而随着半径的增加，三角方法将产生看起来更差的圆。

为了使其更加均匀，更改三角方法以产生与 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 点