Taking advantage of the Symmetry of a Circle in Computer Graphics

Eh, late na pero sayang effort kaya sige na lang

If you were to create a program in that draws circle pixel by pixel, what would you do? Well, you can use this equation to get the points of a circle of radius r and centered at (h,k) as basis:

r^2 = (x-h)^2 + (y-k)^2

Or, if we compute for y:

y = k \pm \sqrt{r^2 - (x-h)^2}

Let’s try drawing a circle using C++11, OpenGL, and freeglut. We will use this as the template of our program. Note that we will be using GL_POINTS to represent pixels.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include 
#include 
#include 
#include 

#include <GL/freeglut.h>

#define MAX_FRAMES 100000000

#define WIN_HEIGHT 720
#define WIN_WIDTH 720

using namespace std;

struct Point{
    int x;
    int y;

    Point(int x_0, int y_0): x(x_0), y(y_0) {}; }; 

struct Color{
    float r;
    float g;
    float b;

    Color(float r_0, float g_0, float b_0):
        r(r_0), g(g_0), b(b_0) {};
};

typedef struct Point Point;
typedef struct Color Color;

int r = 350;
int x;
int y;

bool running = false;

vector<Point *> points;

Color black(0.0f, 0.0f, 0.0f);
Color red(1.0f, 0.0f, 0.0f);

// Integer Square root
int int_sqrt(int num){
    int res = 0;
    int bit = 1ul << 30;

    while (bit != 0){
        if( num >= res + bit ){
            num -= res + bit;
            res = (res >> 1) + bit;
        } else
            res >>= 1;
        bit >>= 2;
    }

    return res;
}

void clear_points(){
    for(Point *p : points)
        delete p;

    points.clear();
}

void reset_circle(){
    // Reset circle code here
}

void draw_point(Point *p, Color *c){
    glBegin(GL_POINTS);
        glColor3f(c->r, c->g, c->b);
        glVertex2i(p->x, p->y);
    glEnd();
}

// Draw circle
void draw_circle(){

    // Draw circle code here

}

void init(){

    glClearColor(1.0f,1.0f,1.0f,0.0f);
    glMatrixMode(GL_PROJECTION);
    gluOrtho2D(0.0f, float(WIN_WIDTH), 0.0f, float(WIN_HEIGHT));

}

void mouse_action(int button, int m_state, int m_x, int m_y){
    if (button == GLUT_LEFT_BUTTON && m_state == GLUT_DOWN)
        running = !running;
    else if(button == GLUT_RIGHT_BUTTON && m_state == GLUT_DOWN)
        reset_circle();
    
}

void keyboard_action(unsigned char key, int x, int y){
    switch(key) {
        case ' ': running = !running; break;
    }
}

int main(int argc , char **argv){

    // init GLUT and Create Window
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
    glutSetOption(GLUT_ACTION_ON_WINDOW_CLOSE, GLUT_ACTION_CONTINUE_EXECUTION);
    glutInitWindowSize(WIN_WIDTH,WIN_HEIGHT);
    glutCreateWindow("Circle");

    reset_circle();
    init();

    glutMouseFunc(mouse_action);
    glutKeyboardFunc(keyboard_action);

    glutDisplayFunc(draw_circle);
    glutIdleFunc(draw_circle);

    glutMainLoop();

    cout << "Cleaning up..." << endl;

    clear_points();

    return 0;

}

Let’s try a direct implementation of the equation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void reset_circle(){
    x = -r;
    y = 0;

    clear_points();
}

// Draw circle
void draw_circle(){

    int h = WIN_WIDTH/2;
    int k = WIN_HEIGHT/2;
    
    glClear(GL_COLOR_BUFFER_BIT);
    glPointSize(5.0f);

    for(Point *point : points){
        draw_point(point, &black);
    }

    if(x <= r && running){
        
        y = int_sqrt((r*r) - (x*x));

        Point *new_point = new Point(h + x, k + y);
        draw_point(new_point, &red);
        points.push_back(new_point);
        
        new_point = new Point(h + x, k - y);
        draw_point(new_point, &red);
        points.push_back(new_point);

        x++;
    }

    if( x > r)
        reset_circle();

    glutSwapBuffers();

}

This would be the resulting render.
circle_1

Not quite a circle yet and on top of that slow, but why isn’t the produced render a complete circle? Remember that we only computed the integer parts of the equation and as such, in the areas with enough slope, one pixel won’t be enough to fill that area. Why not use floats then? Remember that pixels are discrete and not dimensionless and on top of that computing the floats part would add more multiplication and square root computations, both of which are relatively heavy operations, to our program. So what can we do? For now, let’ improve our program.

Note that a circle is highly symmetrical, so let’s try to compute 4 points at once instead of just 2 and see what happens.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
void reset_circle(){
    x = 0;
    y = 0;

    clear_points();
}

// Draw circle
void draw_circle(){

    int h = WIN_WIDTH/2;
    int k = WIN_HEIGHT/2;
    
    glClear(GL_COLOR_BUFFER_BIT);
    glPointSize(5.0f);

    for(Point *point : points){
        draw_point(point, &black);
    }

    if(x <= r && running){
        
        y = int_sqrt((r*r) - (x*x));

        Point *new_point = new Point(h + x, k + y);
        draw_point(new_point, &red);
        points.push_back(new_point);
        
        new_point = new Point(h + x, k - y);
        draw_point(new_point, &red);
        points.push_back(new_point);

        new_point = new Point(h - x, k + y);
        draw_point(new_point, &red);
        points.push_back(new_point);

        new_point = new Point(h - x, k - y);
        draw_point(new_point, &red);
        points.push_back(new_point);

        x++;
    }

    if( x > r)
        reset_circle();

    glutSwapBuffers();

}

This is the resulting render:

circle_2

Faster but we still have discontinuities on the left and right side. Let’s improve our code further by computing 8 points at once, this time we add the left and right sides as starting points.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
void reset_circle(){
    x = 0;
    y = r;

    clear_points();
}


// Draw circle
void draw_circle(){

    int h = WIN_WIDTH/2;
    int k = WIN_HEIGHT/2;
    
    glClear(GL_COLOR_BUFFER_BIT);
    glPointSize(5.0f);

    for(Point *point : points){
        draw_point(point, &black);
    }

    if( x <= y && running ){
        
         Point *new_point = new Point(h + x, k + y);
        draw_point(new_point, &red);
        points.push_back(new_point);
        
        new_point = new Point(h + x, k - y);
        draw_point(new_point, &red);
        points.push_back(new_point);
 
        new_point = new Point(h - x, k + y);
        draw_point(new_point, &red);
        points.push_back(new_point);

        new_point = new Point(h - x, k - y);
        draw_point(new_point, &red);
        points.push_back(new_point);
 
        new_point = new Point(h + y, k + x);
        draw_point(new_point, &red);
        points.push_back(new_point);
 
        new_point = new Point(h + y, k - x);
        draw_point(new_point, &red);
        points.push_back(new_point);
 
        new_point = new Point(h - y, k + x);
        draw_point(new_point, &red);
        points.push_back(new_point);
 
        new_point = new Point(h - y, k - x);
        draw_point(new_point, &red);
        points.push_back(new_point);

        x++;
        y = int_sqrt((r*r) - (x*x));
    }

    if( x >= y)
        reset_circle();

    glutSwapBuffers();

}

The resulting render:

circle_3

FINALLY! We have a full circle.

The last code is actually a simplified implementation of the Midpoint circle algorithm, an algorithm that takes advantage of a circle’s symmetry in order to render it fast. This implementation still uses square root and multiplication operations. Actual implementations implements the algorithm such that no multiplication or square root operations are done.

Source code

Advertisements