Bresenham circle drawing algorithm implementation in Java

1
votes

I've implemented Bresenham Circle drawing algorithm in Java. But the output is not correctly drawn! I can't find where the problem is.

My code and output image is given below. Any help is appreciated.

public void display(GLAutoDrawable drawable) {
    final GL2 gl = drawable.getGL().getGL2();
    gl.glBegin (GL2.GL_POINTS);
    double radius = 0.6;//sc.nextDouble();
    double x =0.0;
    double y = radius;
    gl.glVertex2d(0.0,0.0);
    gl.glVertex2d(x,y);
    gl.glVertex2d(-x,y);
    gl.glVertex2d(x,-y);
    gl.glVertex2d(-x,-y);
    gl.glVertex2d(y,x);
    gl.glVertex2d(-y,x);
    gl.glVertex2d(y,-x);
    gl.glVertex2d(-y,-x);
    double d = 5 - 4*radius;
    while(x<y){
        if(d<0){ //dE

            x+=.01;
            d+=(2*x + 3)*4;
        }else{

            x+=.01;
            y-=.01;
            d+=(2*x - 2*y +5)*4;
        }
        gl.glVertex2d(x,y);
        gl.glVertex2d(-x,y);
        gl.glVertex2d(x,-y);
        gl.glVertex2d(-x,-y);
        gl.glVertex2d(y,x);
        gl.glVertex2d(-y,x);
        gl.glVertex2d(y,-x);
        gl.glVertex2d(-y,-x);

    }
    gl.glEnd();
}

enter image description here

3
javaalgorithmopengldrawingbresenham
@christopher clark it didn't work. – Erfan Ahmed
His question is clear @TT. – christopher clark
@christopherclark x++ won't work here because the window size is max 1. and x++ or x+=.01 does the same thing. – Erfan Ahmed
Bresenham's algorithms are famous for working with integers only. Using floating point values for x and y surely is what is breaking here. Try using integers for these, and only divide by your scale (?) just before plotting a point. – Jongware
I didn't read your window size is max 1, you need to work with integers like Jongware said. I thought you were just trying to draw a lot of points lol. – christopher clark

3 Answers

1
votes

Notice that the original Bresenham's circle algorithm works only with integers. Since your update is x_{n+1}=x_n+eps you can modify your y update to 

y_{n+1}^2 = y_n^2 - 2*eps*n-eps*eps

The derivation is the same as the one given at the wiki page.

public void display(GLAutoDrawable drawable) {
    final GL2 gl = drawable.getGL().getGL2();
    gl.glBegin (GL2.GL_POINTS);
    double radius = 0.6;//sc.nextDouble();
    double x =0.0;
    double y = radius;
    gl.glVertex2d(0.0,0.0);
    gl.glVertex2d(x,y);
    gl.glVertex2d(-x,y);
    gl.glVertex2d(x,-y);
    gl.glVertex2d(-x,-y);
    gl.glVertex2d(y,x);
    gl.glVertex2d(-y,x);
    gl.glVertex2d(y,-x);
    gl.glVertex2d(-y,-x);

    double eps = .01;
    double eps2 = eps*eps;
    while(x<y){

        y = Math.sqrt(y*y-2*eps*x-eps2);
        x+= eps;
        gl.glVertex2d(x,y);
        gl.glVertex2d(-x,y);
        gl.glVertex2d(x,-y);
        gl.glVertex2d(-x,-y);
        gl.glVertex2d(y,x);
        gl.glVertex2d(-y,x);
        gl.glVertex2d(y,-x);
        gl.glVertex2d(-y,-x);

    }
    gl.glEnd();
}

Result:

enter image description here

Be also careful of the aspect ratio. This algorithm works properly for ratio 1:1. If, however, your aspect ratio is a:b your equation for the circle would become x^2/a^2+y^2/b^2=r^2. You can change the update accordingly.

1
votes

Here is example with drawing your custom circle by using Bresenham's algorithm. Full code can be found in my repo : https://github.com/Maiakov/algorithms/tree/master/Task40 

/**
 * Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point
 * <p>
 * computations at all.
 */
public class DrawCircleAlgorithm {

    public static void drawCircle(int radius, int centerX, int centerY, Graphics g) {
        int y = radius;
        int x = 0;

        int delta = calculateStartDelta(radius);
        while (y >= x) {
            drawPixelAndReflect(centerX, centerY, x, y, g);

            if (delta < 0) {
                delta = calculateDeltaForHorizontalPixel(delta, x);
            } else {
                delta = calculateDeltaForDiagonalPixel(delta, x, y);
                y--;
            }
            x++;
        }
    }

    private static int calculateStartDelta(int radius) {
        return 3 - 2 * radius;
    }

    private static int calculateDeltaForHorizontalPixel(int oldDelta, int x) {
        return oldDelta + 4 * x + 6;
    }

    private static int calculateDeltaForDiagonalPixel(int oldDelta, int x, int y) {
        return oldDelta + 4 * (x - y) + 10;
    }

    private static void drawPixelAndReflect(int centerX, int centerY, int x, int y, Graphics g) {
        g.drawLine(centerX + x, centerY + y, centerX + x, centerY + y);
        g.drawLine(centerX + x, centerY - y, centerX + x, centerY - y);
        g.drawLine(centerX - x, centerY + y, centerX - x, centerY + y);
        g.drawLine(centerX - x, centerY - y, centerX - x, centerY - y);

        g.drawLine(centerX - y, centerY + x, centerX - y, centerY + x);
        g.drawLine(centerX - y, centerY - x, centerX - y, centerY - x);
        g.drawLine(centerX + y, centerY + x, centerX + y, centerY + x);
        g.drawLine(centerX + y, centerY - x, centerX + y, centerY - x);
    }
}
0
votes

Try this. I don't have java on the computer I am on right now, so let's see if it works. Make sure to work with integers since what you are normalizing are the block sizes!

Edit: Added integers.

public void display(GLAutoDrawable drawable) {
    final GL2 gl = drawable.getGL().getGL2();
    gl.glBegin (GL2.GL_POINTS);
    double radius = 0.6;//sc.nextDouble();
    double x =0.0;
    double y = radius;
    gl.glVertex2d(0.0,0.0);
    gl.glVertex2d(x,y);
    gl.glVertex2d(-x,y);
    gl.glVertex2d(x,-y);
    gl.glVertex2d(-x,-y);
    gl.glVertex2d(y,x);
    gl.glVertex2d(-y,x);
    gl.glVertex2d(y,-x);
    gl.glVertex2d(-y,-x);
    double d = 3 - 2*radius;
    while(x<y){
        x++;
    if(d<0){ //dE

        d= d + 4x + 6;
    }else{

        y--;
        d= d+ 4(x - y) + 10;
    }
    gl.glVertex2d(x,y);
    gl.glVertex2d(-x,y);
    gl.glVertex2d(x,-y);
    gl.glVertex2d(-x,-y);
    gl.glVertex2d(y,x);
    gl.glVertex2d(-y,x);
    gl.glVertex2d(y,-x);
    gl.glVertex2d(-y,-x);

}
gl.glEnd();
}