Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » help with a couple of things

This thread is locked; no one can reply to it. rss feed Print
 1   2 
help with a couple of things
konedima
Member #6,241
September 2005

I could probably more descriptive with the title, but I suck at summarising things.

Anyway, on to the problems I'm having:

Problem #1: There's probably some scientific explanation for this, anyway. I'm making a circle with a gradient by drawing a bunch of circles getting progressively bigger at different colours (not that I think the gradient is the problem).
circleag7.th.jpg
You might have to view the image full size to see it, but there are big bunches of black spots in the circle. Taking all advice for how not to make that happen.

Problem #2: For some reason, at certain sizes and colours (but not others) the green value goes nuts at the end (but the circle still looks fine)... have a look at the second value in the top-left of the picture (but the circle is fine).
bigcirclebb6.th.jpg
Again, all advice welcome.

Here is my code:

1 int circstartr = 0;
2 int circgrow = 250;
3 float circr = 50;
4 float circg = 150;
5 float circb = 255;
6 float circrd = (circr / circgrow);
7 float circgd = (circg / circgrow);
8 float circbd = (circb / circgrow);
9 int circrad = circstartr;
10 int circendr = circstartr + circgrow;
11 while(circrad != circendr){
12 circle(screen,320,240,circrad,makecol(circr,circg,circb));
13 circr = circr - circrd;
14 circg = circg - circgd;
15 circb = circb - circbd;
16 if (circrad > circendr){
17 circrad--;
18 }
19 else{
20 circrad++;
21 }
22 }
23 textprintf(screen,font,0,0,makecol(255,255,255),"Colours: %d,%d,%d",circr,circg,circb);

Sorry if the variable names are a bit hard to grasp, it's one of my bad habits.

War Pong HD! Every time you don't download it, a kitten of hope dies in my heart. Please, save the imaginary kittens.
http://warpong.sourceforge.net

Matthew Dalrymple
Member #7,922
October 2006
avatar

It looks as though each of those black dots is a spot which gets missed because circles aren't perfectly round at the pixel level. I would suggest working the opposite way, start from the outside and work your way in with circlefill().
Edit: That may not be the solution but that's what it looks like is happening to me.

=-----===-----===-----=
I like signatures that only the signer would understand. Inside jokes are always the best, because they exclude everyone else.

Jeff Bernard
Member #6,698
December 2005
avatar

Here are two solutions to making a gradient circle. I would think they'd be faster than doing circlefills since they use putpixel (at least the second one does) and wouldn't have to draw overlapping circles...but I'm not expert on the speed of Allegro functions...

I don't see anything that would make the green value became crazy negative like that, maybe to be on the safe side you could put in:
if (circg > 0)

--
I thought I was wrong once, but I was mistaken.

SiegeLord
Member #7,827
October 2006
avatar

Quote:

Here are two solutions to making a gradient circle.

After spending a lot of time with allegro5's primitive drawing functions, I have gained a better understanding of the circle algorithm and how to eliminate those gaps. I have created a better function for this purpose, one that has absolutely no overdraw(if you note, the function in the linked thread has a 28% overdraw) and uses only addition and subtraction inside its loop, making it much faster than anything that uses the square roots.

Here it is:

1void do_circle_nogap(BITMAP *bmp, int x, int y, int radius, int d, void (*proc)(BITMAP *, int, int, int))
2{
3 int X, Y;
4 float radius2;
5 float radius3;
6 float error;
7 float dX, dY;
8 int ix;
9 int iy;
10 
11 radius2 = radius * radius;
12 radius3 = (radius - 1) * (radius - 1);
13 
14 X = radius;
15 Y = 0;
16
17 dX = -2 * X - 1;
18 dY = -1;
19
20 error = X * X + 1;
21 ix = x;
22 iy = y;
23 
24 #define PROC8 \
25 proc(bmp, ix + X, iy + Y, d); \
26 \
27 if (X) \
28 proc(bmp, ix - X, iy + Y, d); \
29 \
30 if (Y) \
31 proc(bmp, ix + X, iy - Y, d); \
32 \
33 if ((X) && (Y)) \
34 proc(bmp, ix - X, iy - Y, d); \
35 \
36 if (X != Y) \
37 { \
38 proc(bmp, ix + Y, iy + X, d); \
39 \
40 if (X) \
41 proc(bmp, ix + Y, iy - X, d); \
42 \
43 if (Y) \
44 proc(bmp, ix - Y, iy + X, d); \
45 \
46 if (X && Y) \
47 proc(bmp, ix - Y, iy - X, d); \
48 }
49 
50 while (X >= Y)
51 {
52 PROC8
53
54 if(error + dX + 2 >= radius3 && error < radius2 && X != Y)//draw the gap filler pixel
55 {
56 X--;
57 PROC8
58 X++;
59 }
60
61 Y++;
62 dY += 2;
63 error += dY;
64 
65 if (error >= radius2)
66 {
67 X--;
68 dX += 2;
69 error += dX;
70 }
71 }
72 #undef PROC8
73}

Just replace this line in your code:

circle(screen,320,240,circrad,makecol(circr,circg,circb));

With this:

do_circle_nogap(screen,320,240,circrad,makecol(circr,circg,circb), putpixel);

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

konedima
Member #6,241
September 2005

SiegeLord: I tried your code, but it ran veeeeeeeery slowly (I could see each circle being drawn), whereas even a circlefill "solution" is instant.

I'm trying not to sound like an idiot here, but I'm thinking it has something to do with me using an older version of Allegro (4.2.1).

I don't plan to be drawing large gradients (the big circle here is just a test, I probably won't be doing anything more than 100x100) but I will probably need a few objects redrawn every frame so it does need to be fast.

Oh, and in an "I'm an idiot" moment, I found why the colours were being misreported as hugely positive or negative... I was using textprintf(screen,font,0,0,makecol(255,255,255),"Colours: %d,%d,%d",circr,circg,circb); to show the colours, but I just realised... they're floats, not ints, and textprintf(screen,font,0,0,makecol(255,255,255),"Colours: %f,%f,%f",circr,circg,circb); works (my highly unscientific mind guessing %f meant float).

War Pong HD! Every time you don't download it, a kitten of hope dies in my heart. Please, save the imaginary kittens.
http://warpong.sourceforge.net

SiegeLord
Member #7,827
October 2006
avatar

Quote:

SiegeLord: I tried your code, but it ran veeeeeeeery slowly (I could see each circle being drawn), whereas even a cirlefill solution is instant.

I'm trying not to sound like an idiot here, but I'm thinking it has something to do with me using an older version of Allegro (4.2.1).

I don't plan to be drawing large gradients (the big circle here is just a test, I probably won't be doing anything more than 100x100) but I will probably need a few objects redrawn every frame so it does need to be fast.

There is one thing you can do to speed it up (see below) but otherwise, this is as fast as a gradient drawing function will get. You should not compare it to the circlefill, but rather with what you had originally, with a bunch of circles. If you do that you will note that they have basically the same speed. Circlefill has orders of magnitude less calculations to do than a gradient circlefill, so it is naturally much faster.

Also, don't draw directly to screen, it is often much much faster to draw to an intermediate memory buffer first, and then blit that memory buffer onto the screen. I'm talking about 100's to 1000's times faster.

Here is a faster version of the function above (note that the only difference is that I pasted the putpixel directly into the function).

1void circle_nogap(BITMAP *bmp, int x, int y, int radius, int d)
2{
3 int X, Y;
4 float radius2;
5 float radius3;
6 float error;
7 float dX, dY;
8 int ix;
9 int iy;
10 
11 radius2 = radius * radius;
12 radius3 = (radius - 1) * (radius - 1);
13 
14 X = radius;
15 Y = 0;
16
17 dX = -2 * X - 1;
18 dY = -1;
19
20 error = X * X + 1;
21 ix = x;
22 iy = y;
23 
24 #define PROC8 \
25 putpixel(bmp, ix + X, iy + Y, d); \
26 \
27 if (X) \
28 putpixel(bmp, ix - X, iy + Y, d); \
29 \
30 if (Y) \
31 putpixel(bmp, ix + X, iy - Y, d); \
32 \
33 if ((X) && (Y)) \
34 putpixel(bmp, ix - X, iy - Y, d); \
35 \
36 if (X != Y) \
37 { \
38 putpixel(bmp, ix + Y, iy + X, d); \
39 \
40 if (X) \
41 putpixel(bmp, ix + Y, iy - X, d); \
42 \
43 if (Y) \
44 putpixel(bmp, ix - Y, iy + X, d); \
45 \
46 if (X && Y) \
47 putpixel(bmp, ix - Y, iy - X, d); \
48 }
49 
50 while (X >= Y)
51 {
52 PROC8
53
54 if(error + dX + 2 >= radius3 && error < radius2 && X != Y)//draw the gap filler pixel
55 {
56 X--;
57 PROC8
58 X++;
59 }
60
61 Y++;
62 dY += 2;
63 error += dY;
64 
65 if (error >= radius2)
66 {
67 X--;
68 dX += 2;
69 error += dX;
70 }
71 }
72 #undef PROC8
73}

If both of my suggestions still don't make it fast enough for you, then you need to rethink your approach.

EDIT: Fixed weird backslash problems in code...

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

konedima
Member #6,241
September 2005

<sheepish apology>
When I use your new code (or even your old code) drawing to a buffer instead of the screen, it is in fact instant. I use a buffer when I'm actually making a game not just testing things out like I am now, but this is the first instance where drawing to a buffer instead of the screen has made this much of a difference... put it this way, I'm inexperienced.

War Pong HD! Every time you don't download it, a kitten of hope dies in my heart. Please, save the imaginary kittens.
http://warpong.sourceforge.net

Neil Black
Member #7,867
October 2006
avatar

If he can literally see each circle being drawn then it isn't even comparable to the bunch of circles method.

I was wrong.

SiegeLord
Member #7,827
October 2006
avatar

Quote:

<sheepish apology>
When I use your new code (or even your old code) drawing to a buffer instead of the screen, it is in fact instant. I use a buffer when I'm actually making a game not just testing things out like I am now, but this is the first instance where drawing to a buffer instead of the screen has made this much of a difference... put it this way, I'm inexperienced.

Don't feel bad! :)

I only discovered this recently myself, when my program inexplicably slowed down to a halt on Windows, while running rapidly on Linux. In fact, I was doing a lot of putpixel's onto the screen directly, which is a very fast operation on Linux (so I was not aware of the folly of doing this) but is very slow on Windows.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

I have since upgraded my gradient circle function from the thread that Jeff Bernard linked to and it now draws 8 pixels per gradient color calculation at a time based on mirror images instead of 4 in the old version. I profiled it, running it 500 times consecutively for a circle with a radius of 208 and it only takes 1.09 seconds. It averaged 2.18ms for itself and 3.06ms for the entire call. It works for at least 32 bit color depth and perhaps others as well depending on what the allegro function 'geta' does when the color depth is not 32. It works for making a gradient from one 32 bit RGBA color value to another.
Here it is , give it a whirl :

1 
2void alpha_gradient_octo_circle(BITMAP *bmp, int cx, int cy, int rad, int outer_color, int inner_color) {
3 int rel_xpos = 0;
4 int rel_ypos = 0;
5 int rel_ypos_squared = 0;/// for precalculation
6 int hxcl = 0;//half of horizontal chord length;
7 
8 int abs_ypos_top = 0;
9 int abs_ypos_bottom = 0;
10 int abs_xpos_left = 0;
11 int abs_xpos_right = 0;
12 int m_abs_ypos_top = 0;
13 int m_abs_ypos_bottom = 0;
14 int m_abs_xpos_left = 0;
15 int m_abs_xpos_right = 0;
16
17 int oc_red = getr(outer_color);
18 int oc_green = getg(outer_color);
19 int oc_blue = getb(outer_color);
20 int oc_alpha = geta(outer_color);
21 int ic_red = getr(inner_color);
22 int ic_green = getg(inner_color);
23 int ic_blue = getb(inner_color);
24 int ic_alpha = geta(inner_color);
25
26 int gc_red = 0;
27 int gc_green = 0;
28 int gc_blue = 0;
29 int gc_alpha = 0;
30 int gradient_color = 0;
31
32 double oc_to_ic_red_diff = static_cast<double>(oc_red - ic_red);
33 double oc_to_ic_green_diff = static_cast<double>(oc_green - ic_green);
34 double oc_to_ic_blue_diff = static_cast<double>(oc_blue - ic_blue);
35 double oc_to_ic_alpha_diff = static_cast<double>(oc_alpha - ic_alpha);
36
37 double d_radius = static_cast<double>(rad);
38 double d_radial_distance = 0.0;
39 double d_gradient_factor = 0.0;
40
41 // This is the y pos where the radius intersects the circle at a 45 degree angle
42 const int diag_rad_y_pos = static_cast<int>(static_cast<double>(rad)/sqrt(2.0));
43
44 for (rel_ypos = 0 ; rel_ypos <= diag_rad_y_pos ; rel_ypos++) {
45 abs_ypos_top = cy - rel_ypos;
46 abs_ypos_bottom = cy + rel_ypos;
47
48 m_abs_xpos_left = cx - rel_ypos;
49 m_abs_xpos_right = cx + rel_ypos;
50
51 hxcl = rel_ypos;
52 rel_ypos_squared = rel_ypos*rel_ypos;/// New addition
53 for (rel_xpos = 0 ; rel_xpos <= hxcl ; rel_xpos++) {
54 abs_xpos_left = cx - rel_xpos;
55 abs_xpos_right = cx + rel_xpos;
56/// d_radial_distance = sqrt(static_cast<double>(rel_xpos*rel_xpos + rel_ypos*rel_ypos));// now precalculated in outer loop
57 d_radial_distance = sqrt(static_cast<double>(rel_xpos*rel_xpos + rel_ypos_squared));
58 d_gradient_factor = d_radial_distance / d_radius;
59 gc_red = ic_red + static_cast<int>(d_gradient_factor*oc_to_ic_red_diff);
60 gc_green = ic_green + static_cast<int>(d_gradient_factor*oc_to_ic_green_diff);
61 gc_blue = ic_blue + static_cast<int>(d_gradient_factor*oc_to_ic_blue_diff);
62 gc_alpha = ic_alpha + static_cast<int>(d_gradient_factor*oc_to_ic_alpha_diff);
63 gradient_color = makeacol(gc_red , gc_green , gc_blue , gc_alpha);
64 putpixel(bmp , abs_xpos_left , abs_ypos_top , gradient_color);
65 putpixel(bmp , abs_xpos_left , abs_ypos_bottom , gradient_color);
66 putpixel(bmp , abs_xpos_right , abs_ypos_top , gradient_color);
67 putpixel(bmp , abs_xpos_right , abs_ypos_bottom , gradient_color);
68
69 m_abs_ypos_top = cy - rel_xpos;
70 m_abs_ypos_bottom = cy + rel_xpos;
71 putpixel(bmp , m_abs_xpos_left , m_abs_ypos_top , gradient_color);
72 putpixel(bmp , m_abs_xpos_left , m_abs_ypos_bottom , gradient_color);
73 putpixel(bmp , m_abs_xpos_right , m_abs_ypos_top , gradient_color);
74 putpixel(bmp , m_abs_xpos_right , m_abs_ypos_bottom , gradient_color);
75 }
76
77 }
78
79
80 for (rel_ypos = diag_rad_y_pos ; rel_ypos <= rad ; rel_ypos++) {
81 abs_ypos_top = cy - rel_ypos;
82 abs_ypos_bottom = cy + rel_ypos;
83
84 m_abs_xpos_left = cx - rel_ypos;
85 m_abs_xpos_right = cx + rel_ypos;
86
87 rel_ypos_squared = rel_ypos*rel_ypos;/// New addition
88 hxcl = static_cast<int>(sqrt(static_cast<double>(rad*rad - rel_ypos_squared)) + 0.5);/// rel_ypos*rel_ypos is now precalculated
89// hxcl = static_cast<int>(sqrt(static_cast<double>(rad*rad - rel_ypos*rel_ypos)) + 0.5);// Use this for a rounding method for the x position at the edge of the circle
90// hxcl = static_cast<int>(sqrt(static_cast<double>(rad*rad - rel_ypos*rel_ypos)));
91 for (rel_xpos = 0 ; rel_xpos <= hxcl ; rel_xpos++) {
92 abs_xpos_left = cx - rel_xpos;
93 abs_xpos_right = cx + rel_xpos;
94 ///d_radial_distance = sqrt(static_cast<double>(rel_xpos*rel_xpos + rel_ypos*rel_ypos));// now precalculated in outer loop
95 d_radial_distance = sqrt(static_cast<double>(rel_xpos*rel_xpos + rel_ypos_squared));
96 d_gradient_factor = d_radial_distance / d_radius;
97 gc_red = ic_red + static_cast<int>(d_gradient_factor*oc_to_ic_red_diff);
98 gc_green = ic_green + static_cast<int>(d_gradient_factor*oc_to_ic_green_diff);
99 gc_blue = ic_blue + static_cast<int>(d_gradient_factor*oc_to_ic_blue_diff);
100 gc_alpha = ic_alpha + static_cast<int>(d_gradient_factor*oc_to_ic_alpha_diff);
101 gradient_color = makeacol(gc_red , gc_green , gc_blue , gc_alpha);
102 putpixel(bmp , abs_xpos_left , abs_ypos_top , gradient_color);
103 putpixel(bmp , abs_xpos_left , abs_ypos_bottom , gradient_color);
104 putpixel(bmp , abs_xpos_right , abs_ypos_top , gradient_color);
105 putpixel(bmp , abs_xpos_right , abs_ypos_bottom , gradient_color);
106
107 m_abs_ypos_top = cy - rel_xpos;
108 m_abs_ypos_bottom = cy + rel_xpos;
109 putpixel(bmp , m_abs_xpos_left , m_abs_ypos_top , gradient_color);
110 putpixel(bmp , m_abs_xpos_left , m_abs_ypos_bottom , gradient_color);
111 putpixel(bmp , m_abs_xpos_right , m_abs_ypos_top , gradient_color);
112 putpixel(bmp , m_abs_xpos_right , m_abs_ypos_bottom , gradient_color);
113 }
114 }
115}

Indeterminatus
Member #737
November 2000
avatar

Just out of curiosity, Edgar, do you get any speed gains by using the squared radius (instead of calculating sqrt)?

_______________________________
Indeterminatus. [Atomic Butcher]
si tacuisses, philosophus mansisses

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Hmm , not sure how I would (or if I could) do that here. The algorithm builds the square portion of the gradient circle first (first outer for loop) and then the leftovers of each 1/8th pie slice are calculated (second outer for loop). In the first loop sqrt is needed to find the radial distance of the current point so the gradient factor can be determined. In the second loop I use sqrt to find one half of the current x chord length based on the current y position and use sqrt again to determine the gradient factor. I did notice that I can take (rel_ypos*rel_ypos) out of the inner loops and precalculate it though. That should streamline it a little more. Profile results are now 500 calls take 1.02 seconds averaging 2.04ms for its own code and 3.07ms for the entire call so it shaved a little time off its own work but the call still makes it take about the same amount of time. (Updated code in previous post in this thread.)

konedima
Member #6,241
September 2005

I just wrote a function to create a rectangle that fades to black. It's probably been done before, but I figure the more I do the more I'll learn.

You may now proceed to tear it to pieces, making me rewrite half of it and replace the other half with something you've written.

1void gradient_rectangle(BITMAP *bmp, int w, int h, int x, int y, int ow, int oh, float r, float g, float b){
2 float owrs, owgs, owbs, ohrs, ohgs, ohbs;
3 owrs = r / ow;
4 owgs = g / ow;
5 owbs = b / ow;
6 ohrs = r / oh;
7 ohgs = g / oh;
8 ohbs = b / oh;
9 line(bmp,x,y,(x+w),y,makecol(r,g,b));
10 line(bmp,x,y,x,(y+h),makecol(r,g,b));
11 line(bmp,x,(y+h),(x+w),(y+h),makecol(r,g,b));
12 line(bmp,(x+w),y,(x+w),(y+h),makecol(r,g,b));
13 float tr = r;
14 float tg = g;
15 float tb = b;
16 int counter = 0;
17 while (counter != ow){
18 line(bmp,x-counter,y-counter,x-counter,y+h+counter,makecol(tr,tg,tb));
19 tr = tr - owrs;
20 tg = tg - owgs;
21 tb = tb - owbs;
22 counter++;
23 }
24 counter = 0;
25 tr = r;
26 tg = g;
27 tb = b;
28 while (counter != ow){
29 line(bmp,x+w+counter,y-counter,x+w+counter,y+h+counter,makecol(tr,tg,tb));
30 tr = tr - owrs;
31 tg = tg - owgs;
32 tb = tb - owbs;
33 counter++;
34 }
35 counter = 0;
36 tr = r;
37 tg = g;
38 tb = b;
39 while (counter != oh){
40 line(bmp,x-counter,y-counter,x+w+counter,y-counter,makecol(tr,tg,tb));
41 tr = tr - ohrs;
42 tg = tg - ohgs;
43 tb = tb - ohbs;
44 counter++;
45 }
46 counter = 0;
47 tr = r;
48 tg = g;
49 tb = b;
50 while (counter != oh){
51 line(bmp,x-counter,y+h+counter,x+w+counter,y+h+counter,makecol(tr,tg,tb));
52 tr = tr - ohrs;
53 tg = tg - ohgs;
54 tb = tb - ohbs;
55 counter++;
56 }
57}

War Pong HD! Every time you don't download it, a kitten of hope dies in my heart. Please, save the imaginary kittens.
http://warpong.sourceforge.net

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Well , something is not quite right with it yet.
http://www.allegro.cc/files/attachment/595171
So basically you want to draw a rectangular frame that is black on the outer edges and fades into the r,g,b values passed to it over a distance specified by oh and ow?

You might want to just use one variable for the thickness of the frame and limit it to half of the smallest dimension so it doesn't overdraw inwards. I noticed that you use 4 lines to draw a rect at the beginning of the code but the opposite corner coordinates are off by one as the corners should be (x,y) and (x + w - 1 , y + h - 1).

If you just use a single frame thickness you should be able to combine all four of your while loops into one. You can also use hline and vline directly instead of line. This way you'll have one for loop with one color calculation per iteration and you can use four variables for the current positions. I always use tlx , tly , brx , and bry for top left and bottom right x and y and then you can increment tlx and tly and decrement brx and bry and use hline and vline with them.

Of course you may want to do something entirely different in which case I've just been blathering on.

SiegeLord
Member #7,827
October 2006
avatar

My function's still faster. Around 10% faster for large circles, and as much as 90% faster for small circles.

As for the gradient rectangle... any reason why you are not using the rectangle function?

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Quote:

My function's still faster.

And still too difficult to read easily.
How the hell do you find the relative (x,y) position on the edge of a circle without using sine or cosine? I understand everything except for that bit.

- konedima -
I coded up a gradient_rectangle_frame function that lets you draw inwards or outwards by the frame_thickness you pass it and you give it the starting and finishing colors. It starts at (x,y) and draws nested rectangles in the direction you specify with the sign of frame_thickness.

1 
2void gradient_rectangle_frame(BITMAP* bmp , int x , int y , int w , int h , int frame_thickness , int start_color , int finish_color) {
3 /// x and y are the upper left coordinate of the starting edge of the rectangular frame.
4 /// It will be drawn towards (x + frame_thickness) , (y + frame_thickness) (frame_thickness can be negative) ,
5 /// and starting from (x,y) the color will change linearly from start_color to finish_color.
6 /// If frame_thickness is positive it will draw inwards and if negative it will draw outwards from the start point.
7 if (!bmp) {return;}
8
9/* Uncomment to prevent inward overdraw
10 if (w > h) {
11 if (frame_thickness > h/2) {
12 frame_thickness = h/2 + h%2;
13 }
14 } else {
15 if (frame_thickness > w/2) {
16 frame_thickness = w/2 + w%2;
17 }
18 }
19*/
20
21 int (*makecol_func_ptr) (int , int , int) = NULL;
22
23 int bmp_cd = bitmap_color_depth(bmp);
24
25 switch (bmp_cd) {
26 case 32:
27 makecol_func_ptr = makecol32;
28 break;
29 case 24:
30 makecol_func_ptr = makecol24;
31 break;
32 case 16:
33 makecol_func_ptr = makecol16;
34 break;
35 case 15:
36 makecol_func_ptr = makecol15;
37 break;
38 case 8:
39 makecol_func_ptr = makecol8;
40 break;
41 }
42
43 int sc_red = getr(start_color);
44 int sc_green = getg(start_color);
45 int sc_blue = getb(start_color);
46
47 int fc_red = getr(finish_color);
48 int fc_green = getg(finish_color);
49 int fc_blue = getb(finish_color);
50
51 double sc_to_fc_red_delta = static_cast<double>(fc_red - sc_red)/static_cast<double>(abs(frame_thickness - 1));
52 double sc_to_fc_green_delta = static_cast<double>(fc_green - sc_green)/static_cast<double>(abs(frame_thickness - 1));
53 double sc_to_fc_blue_delta = static_cast<double>(fc_blue - sc_blue)/static_cast<double>(abs(frame_thickness - 1));
54
55 int gc_red = 0;
56 int gc_green = 0;
57 int gc_blue = 0;
58
59 int gradient_color = 0;
60
61 int tlx = x;
62 int tly = y;
63 int brx = x + w - 1;
64 int bry = y + h - 1;
65 int frame = 0;
66 double d_frame = 0.0;
67 int num_frames = abs(frame_thickness);
68// int step = 1;
69// if (frame_thickness < 0) {step = -1;}
70 const int step = (frame_thickness < 0) ? -1 : 1;
71 for (frame = 0 ; frame < num_frames ; frame++) {
72 d_frame = static_cast<double>(frame);
73 gc_red = sc_red + static_cast<int>(d_frame*sc_to_fc_red_delta);
74 gc_green = sc_green + static_cast<int>(d_frame*sc_to_fc_green_delta);
75 gc_blue = sc_blue + static_cast<int>(d_frame*sc_to_fc_blue_delta);
76 gradient_color = makecol_func_ptr(gc_red , gc_green , gc_blue);
77 hline(bmp , tlx , tly , brx , gradient_color);
78 hline(bmp , tlx , bry , brx , gradient_color);
79 vline(bmp , tlx , tly , bry , gradient_color);
80 vline(bmp , brx , tly , bry , gradient_color);
81 tlx += step;
82 tly += step;
83 brx -= step;
84 bry -= step;
85 }
86}

SiegeLord
Member #7,827
October 2006
avatar

Nevermind about my suggestion to use rectangles, I misunderstood what the function required.

Quote:

And still too difficult to read easily.

Heh, I wouldn't say that all those useless static_cast's combined with those sentence-long variable names in yours are easy on the eyes either. Comments were made for a reason.

In any event, the algorithm is simple. I use it extensively in the new primitive drawing functions I created for A5.

Basically, a point inside the circle of radius R satisfies the following requirement (we assume the circle is centered at (0,0))

<math>X^2 + Y^2 \le R^2</math>

Now, the algorithm goes as follows:

  1. Start at a point (R, 0).

  2. Increment Y.

  3. Test if the point is still in the circle.

  4. If it isn't, decrement X.

  5. Repeat 2-4 until you draw out the first octant

The code for this would be:

while(X <= Y)//a property of the first quadrant
{
    Y++;//increment Y
    if(X * X + Y * Y > R * R)//are we outside the circle?
    {
        X--;//decrement the X then (and move back inside the circle)
    }
}

This gives you the points in the first octant. Then you naturally mirror that point 7 times to get the rest of the circle, this is what my PROC8 macro does. To fill in the gaps, you just have to test if there is a pixel that is both within the current radius, and outside the old (i.e. smaller) radius and is distinct from the pixel we just drew.

The rest of the differences are just optimizations. Instead of multiplying the X's and Y's each time I use the differentials (dY and dX), and I combine several variables together.

Note that this algorithm is only used to draw filled in circles. If you are just drawing an outline circle you need a different algorithm, called the Bresenham algorithm... it is a little more complicated than this though. You can look it up on the net... although there are like 5 different versions of it, one of which allegro uses right now... and one which I am replacing it with.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Audric
Member #907
January 2001

Siegelord said:

I was doing a lot of putpixel's onto the screen directly, which is a very fast operation on Linux (so I was not aware of the folly of doing this) but is very slow on Windows.

Sorry for the late reaction, in this case I suspect it's the DirectX locking that killed the performance. Allegro has acquire_screen() / release_screen() if you know you're going to use many graphic primitives in a row.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Quote:

Heh, I wouldn't say that all those useless static_cast's combined with those sentence-long variable names in yours are easy on the eyes either. Comments were made for a reason.

static_cast's aren't useless. They mean that you want to explicitly convert from one type to another. Your code doesn't have any comments at all and given your non-descript variable names it makes it hard to follow. My code is easier to follow because the variable names contain the exact description of what they are meant to hold. It also makes it easier to come back to and know what is going on and easier for someone else to edit.

Quote:

The rest of the differences are just optimizations. Instead of multiplying the X's and Y's each time I use the differentials (dY and dX), and I combine several variables together.

I followed along with everything up to here but the logic you use in your while loop escapes me. Specifically , why do you add on to dX and dY and then increment error with them?

See if I am catching on :
Since the x value would normally be cos(angle) then the value of the derivative of cos(angle) would be -sin(angle) which is -y , nevermind I'm still confused. Why do you initialize dX to "dX = -2*radius - 1;"?

Perhaps if you showed me an unoptimized version of the while loop without going back all the way to squaring X and Y to check the distance then I might understand better how you got to this point.

SiegeLord
Member #7,827
October 2006
avatar

Explicitly calling a static_cast is useless, since a C style cast will reduce to a static cast anyway. But w/e. Just because I can't read it, doesn't mean that it's bad.

Here's how the dX's and dY's work:

Define error:

<math>error(X, Y) = X^2 + Y^2</math>

Find error(X - 1, Y)

<math>error(X - 1, Y) = (X - 1)^2 + Y^2</math>

<math>error(X - 1, Y) = X^2 - 2 X + 1 + Y^2</math>

Now, subtract the two errors:

<math>error(X - 1, Y) - error(X, Y) = -2 X + 1</math>

So: dX = -2 * X + 1. The differentials start at X = radius + 1, so dX = -2 * radius - 1 at start. Whenever we decrease the X by one, dX increases by 2.

We can do the same for dY and get that that equals to 2 Y + 1. The differentials actually assume that we start at Y = -1, so dY = -1 at start. Whenever we increase the Y by one, dY increases by 2.

Thus, whenever we move according to the coordinates, we either add the dX or the dY as appropriate and increment the differentials to reflect the changed coordinates.

Error at start then equals to X * X + Y * Y. Error actually starts at (0, -1) so it just equals to X * X + 1.

Hmm. It does seem a little backwards now that I look back at it, it's been awhile since I made this particular version. Here's a version that has everything starting at the same point. If you can see why both versions are the same, then you understand the algorithm.

1void circle_nogap(BITMAP *bmp, int x, int y, int radius, int d)
2{
3 int X, Y;
4 float radius2;
5 float radius3;
6 float error;
7 float dX, dY;
8 int ix;
9 int iy;
10 
11 radius2 = radius * radius;
12 radius3 = (radius - 1) * (radius - 1);
13 
14 X = radius;
15 Y = 0;
16
17 dX = -2 * X + 1;
18 dY = 2 * Y + 1;
19
20 error = X * X + Y * Y;
21
22 ix = x;
23 iy = y;
24 
25 #define PROC8 \
26 putpixel(bmp, ix + X, iy + Y, d); \
27 \
28 if (X) \
29 putpixel(bmp, ix - X, iy + Y, d); \
30 \
31 if (Y) \
32 putpixel(bmp, ix + X, iy - Y, d); \
33 \
34 if ((X) && (Y)) \
35 putpixel(bmp, ix - X, iy - Y, d); \
36 \
37 if (X != Y) \
38 { \
39 putpixel(bmp, ix + Y, iy + X, d); \
40 \
41 if (X) \
42 putpixel(bmp, ix + Y, iy - X, d); \
43 \
44 if (Y) \
45 putpixel(bmp, ix - Y, iy + X, d); \
46 \
47 if (X && Y) \
48 putpixel(bmp, ix - Y, iy - X, d); \
49 }
50 
51 while (X >= Y)
52 {
53 PROC8
54
55 if(error + dX >= radius3 && error < radius2 && X != Y)//draw the gap filler pixel
56 {
57 X--;
58 PROC8
59 X++;
60 }
61
62 Y++;
63 error += dY;
64 dY += 2.0f;//note how this happens after we add the dY
65 
66 if (error >= radius2)
67 {
68 X--;
69 error += dX;
70 dX += 2.0f;//note how this happens after we add the dX
71 }
72 }
73 #undef PROC8
74}

EDIT: Fixed bug.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

konedima
Member #6,241
September 2005

I ask for help with circles, and I get a complex mathematical discussion. It's alright though, you guys go on.

Edgar: The reason it looks like that for you is because ow and oh need to be the same ... I was testing how a longer fade would look horizontally but not vertically or vice versa. The answer... not good. It still has applications of something drawn with it covers the whole width/height of the screen, so I can avoid drawing anything I don't need (which depending on the number of objects could save some time). They're in separate loops because I was tired :).

Audric: Thanks, I'll try doing that to speed up a little demo I have running of my gradient circle changing colour (it looks cool, if you're impressed by shiny things).

All: Thanks for helping a programming noob like me :).

Note to self: Use less smilies next post... :).

Edit (a few hours later):
Here's my updated gradient rectangle:

1void gradient_rectangle(BITMAP *bmp, int w, int h, int x, int y, int fade, int ifade, float r, float g, float b){
2 int tlx, tly, brx, bry;
3 tlx = x;
4 tly = y;
5 brx = x+w;
6 bry = y+h;
7 float fr, fg, fb;
8 fr = r / fade;
9 fg = g / fade;
10 fb = b / fade;
11 int itlx, itly, ibrx, ibry;
12 itlx = x;
13 itly = y;
14 ibrx = x+w;
15 ibry = y+h;
16 float ifr,ifg,ifb;
17 ifr = r / ifade;
18 ifg = g / ifade;
19 ifb = b / ifade;
20 line(bmp,x,y,(x+w-1),y,makecol(r,g,b));
21 line(bmp,x,y,x,(y+h-1),makecol(r,g,b));
22 line(bmp,x,(y+h),(x+w),(y+h),makecol(r,g,b));
23 line(bmp,(x+w),y,(x+w),(y+h),makecol(r,g,b));
24 float tr = r;
25 float tg = g;
26 float tb = b;
27 int counter = 0;
28 while (counter != fade){
29 tlx--;
30 tly--;
31 brx++;
32 bry++;
33 hline(bmp,tlx,tly,brx,makecol(tr,tg,tb));
34 hline(bmp,tlx,bry,brx,makecol(tr,tg,tb));
35 vline(bmp,tlx,tly,bry,makecol(tr,tg,tb));
36 vline(bmp,brx,tly,bry,makecol(tr,tg,tb));
37 tr -= fr;
38 tg -= fg;
39 tb -= fb;
40 counter++;
41 }
42 tr = r;
43 tg = g;
44 tb = b;
45 counter = 0;
46 while (counter != ifade){
47 itlx++;
48 itly++;
49 ibrx--;
50 ibry--;
51 hline(bmp,itlx,itly,ibrx,makecol(tr,tg,tb));
52 hline(bmp,itlx,ibry,ibrx,makecol(tr,tg,tb));
53 vline(bmp,itlx,itly,ibry,makecol(tr,tg,tb));
54 vline(bmp,ibrx,itly,ibry,makecol(tr,tg,tb));
55 tr -= ifr;
56 tg -= ifg;
57 tb -= ifb;
58 counter++;
59 }
60}

I reduced it to one loop (well one for the outer glow and one for the inner glow), added an inner glow, removed the separate oh and ow fades (replace them with fade for outside fade and ifade for inside). Oh and thanks Edgar for your advice.

War Pong HD! Every time you don't download it, a kitten of hope dies in my heart. Please, save the imaginary kittens.
http://warpong.sourceforge.net

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

- konedima -
You've still got a couple off by one errors when finding the bottom right coordinate for things. If you draw a 2X2 rectangle at 0,0 you want it to go to 1,1 but you use w,h instead of w-1,h-1. To speed things up , precalculate the color for the current rectangle you're drawing since all 4 lines will be the same color.

- SiegeLord -
I rewrote your circle_nogap function to help me learn your technique more effectively and I was testing both your version and the revised version I made. I drew concentric circles of alternating color , blending the set of odd radius circles over the set of even radius circles to see if there was any overlap and I found that with your function , one layer overlaps another in places. See attached picture. The lighter green areas are where the adjacent circles overlap. I used stretch_blit onto a blending buffer with an integer magnification to make things easier to see and used the same functions and function calls to draw the concentric circles so the test should be sound.

I used a different technique to determine which pixels to draw using the same method for finding positions that you used. The algorithm I use for drawing pixels is this :
If the radius is 0 , draw one pixel in the center and return.
Start at (x,y) = (radius,0) like you did and draw the four corresponding pixels.
While the relative x position is less than the relative y position {
1. Move up and if necessary move left and then draw the eight corresponding pixels.
2. Check whether to draw the pixel to the left and draw the eight pixels if necessary.
}
Check if rel_x == rel_y and if the distance squared is less than the outer boundary distance squared. If both true then draw the 4 corresponding pixels that are at 45 degrees.

Relative x and y is tracked to know when to stop drawing.
Absolute x and y are tracked to prevent excessive addition/subtraction of the relative position with the center point so only incrementors are used for the 4 pixels that are the vertically/horizontally flipped pixels. When necessary , the pixels mirrored along the line rel_x = rel_y are calculated from the absolute positions and the center point.

So I got rid of the proc_8 macro in favor of procedural processing if that's what it's called and the number of calculations should be reduced overall. I haven't done any profiling yet because I can't get to it until tomorrow and while I checked my version to make sure there are no overlaps between adjacent concentric circles I haven't tested it to make sure there is no over draw but I don't believe there could be any. I'll check tomorrow when I clean up my test code. Right now it's a big mish-mash testing ground for all sorts of stuff.

So here's my revised function :

1 
2/// My implementation of algorithm used by SiegeLord to draw a circle
3/// without using sqrt , sine , or cosine
4void revised_circle_nogap (BITMAP* bmp , int cx , int cy , int radius , int color) {
5
6 ASSERT(bmp);
7
8 /// If any part of circle is outside bitmap , let allegro's putpixel clip it for us (lazy?)
9 void (*putpixelfunc) (BITMAP* , int , int , int) = putpixel;
10 /// If all of circle will be plotted on bitmap , then select inline _putpixel* function
11 /// However , _putpixel* won't work in mode X and this code shouldn't be used unless it's not in mode X
12 /// but I have no idea how to check if it is in mode X or not.
13/* ####### Insert mode X check here ######### */
14/* Uncomment this line to enable _putpixel*
15 if (!( ((bmp->w < (cx + radius)) || (radius < cx)) || ((bmp->h < cy + radius) || (radius < cy)) )) {
16 switch (bitmap_color_depth(bmp)) {
17 case 32 :
18 putpixelfunc = _putpixel32;
19 break;
20 case 24 :
21 putpixelfunc = _putpixel24;
22 break;
23 case 16 :
24 putpixelfunc = _putpixel16;
25 break;
26 case 15 :
27 putpixelfunc = _putpixel15;
28 break;
29 case 8 :
30 putpixelfunc = _putpixel;
31 break;
32 }
33 }
34//*/
35
36 if (bmp == screen) {acquire_screen();}
37 if (!radius) { // radius = 0
38 // radius is 0 so draw one pixel at cx , cy
39 putpixelfunc(bmp , cx , cy , color);
40 if (bmp == screen) {release_screen();}
41 return;
42 }
43 // Outer Radius Squared is the exclusive outer boundary for pixels to be drawn on the circle
44 // Inner Radius Squared is the inclusive inner boundary for pixels to be drawn on the circle
45/// Uncomment next two lines to use strict boundaries
46// const int OuterRadiusSquared = (radius+1)*(radius+1);
47// const int InnerRadiusSquared = radius*radius;
48
49/// Comment next two lines to not use softened boundaries
50 /// Looks pretty nice and the smallest circles don't look so square
51 const int OuterRadiusSquared = (int)((((double)radius)+0.5)*(((double)radius)+0.5) + 0.5);
52 const int InnerRadiusSquared = (int)((((double)radius)-0.5)*(((double)radius)-0.5) + 0.5);
53 
54 
55 // relative x and y positions are for tracking when to stop drawing
56 int rel_right_xpos = radius;
57 int rel_top_ypos = 0;
58
59 // absolute positions to be used in drawing pixels
60 int right_xpos = cx + radius;
61 int left_xpos = cx - radius;
62 int top_ypos = cy;// cy + 0
63 int bot_ypos = cy;// cy - 0
64 
65 int CurrentDistanceSquared = radius*radius;// (radius*radius) + (0*0)
66 
67 // absolute positions of xy mirrored pixels
68 int xymirror_right_xpos = 0;
69 int xymirror_left_xpos = 0;
70 int xymirror_top_ypos = 0;
71 int xymirror_bot_ypos = 0;
72 
73 /// P2 , DistanceSquared (X-1,Y) = X^2 + Y^2 -2*X + 1
74 /// P1 , DistanceSquared (X,Y) = X^2 + Y^2
75 /// (P2 - P1) = -2*X + 1
76 // The amount to add to CurrentDistanceSquared to find what it would be after moving one pixel left
77 // To go from Current Distance Squared to Current Distance Squared of One Pixel Left ,
78 // add (CDS(X-1,Y) - CDS(X,Y)) = -2*X + 1 to the Current Distance Squared
79 int DistSquaredDeltaLeft = -2*radius + 1;
80 
81 // When the current position moves left , the amount to change the squared distance by when moving left one pixel
82 // changes from (-2(X) + 1) to (-2(X-1) + 1) so to update the amount the squared distance would change by
83 // add ((-2X + 2 + 1) - (-2X + 1) = (2) so add 2 to DistSquaredDeltaLeft when X moves left
84 const int DeltaLeftChange = 2;
85 
86 /// P2 , DistanceSquared (X,Y+1) = X^2 + Y^2 + 2*Y + 1
87 /// P1 , DistanceSquared (X,Y) = X^2 + Y^2
88 /// (P2 - P1) = 2*Y + 1
89 // The amount to add to CurrentDistanceSquared to find what it would be after moving one pixel up
90 // To go from Current Distance Squared to Current Distance Squared of One Pixel Up , add (CDS(X,Y+1) - CDS(X,Y)) = 2*Y + 1
91 //int DistSquaredDeltaUp = 2*top_ypos + 1;//top_ypos = 0
92 int DistSquaredDeltaUp = 1;///top_ypos = 0
93 
94 // When the current position moves up , the amount to change the squared distance by when moving up one pixel
95 // changes from (2*Y + 1) to (2*(Y+1) + 1) so to update the amount the squared distance would change by
96 // add ((2Y + 2 + 1) - (2Y + 1)) = 2;
97 const int DeltaUpChange = 2;
98 
99 // Since we're starting at the rightmost pixel of the circle , we can draw
100 // the first pixel mirrored four times for right/left/top/bottom
101 putpixelfunc(bmp , right_xpos , top_ypos , color);// right
102 putpixelfunc(bmp , left_xpos , top_ypos , color);// left
103 /// Mirrored along line (rel_x = rel_y) , Must use relative position here
104/// xymirror_right_xpos = cx + (top_ypos - cy);// cx + relative y position on top
105/// The first y position is zero relative so cx can be used for the mirrored xy position for x
106// putpixelfunc(bmp , cx + (top_ypos - cy) , cy + (right_xpos - cx) , color);// top
107// putpixelfunc(bmp , cx + (top_ypos - cy) , cy + (left_xpos - cx) , color);// bottom
108 putpixelfunc(bmp , cx , cy + (right_xpos - cx) , color);// top
109 putpixelfunc(bmp , cx , cy + (left_xpos - cx) , color);// bottom
110 
111 top_ypos++;
112 rel_top_ypos++;
113 bot_ypos--;
114 CurrentDistanceSquared += DistSquaredDeltaUp;
115 DistSquaredDeltaUp += DeltaUpChange;
116 // y will increase and x will decrease counterclockwise along the circle from
117 // 3'o'clock until they're equal at 45 degrees. Until they're equal , they're
118 // guaranteed to work for 8 different points on the circle using flips and mirrors
119 while (rel_right_xpos > rel_top_ypos) {
120 // just moved up so we need to make sure the current point is still
121 // inside (inclusive) the outer radius , if not , move left
122 if (CurrentDistanceSquared >= OuterRadiusSquared) {
123 /// Since the drawing stops when the angle reaches 45 degrees ,
124 /// the x position can never be more than one pixel outside
125 /// the circle to the right
126 right_xpos--;
127 rel_right_xpos--;
128 left_xpos++;
129 CurrentDistanceSquared += DistSquaredDeltaLeft;
130 DistSquaredDeltaLeft += DeltaLeftChange;
131 // current position could now be across 45 degree line , so check
132 if (rel_right_xpos < rel_top_ypos) {break;}// should already be plotted
133 }
134 
135 /// Exclusively inside the outer circle now , so plot all 8 points
136 /// Plot first 4 points using horizontal/vertical flips of top right pixel
137 putpixelfunc(bmp , right_xpos , top_ypos , color);
138 putpixelfunc(bmp , right_xpos , bot_ypos , color);
139 putpixelfunc(bmp , left_xpos , top_ypos , color);
140 putpixelfunc(bmp , left_xpos , bot_ypos , color);
141 /// 4 points using X=Y mirror of first four points
142 /**!!! Wrong - These are absolute positions , not relative
143 putpixelfunc(bmp , top_ypos , right_xpos , color);
144 putpixelfunc(bmp , bot_ypos , right_xpos , color);
145 putpixelfunc(bmp , top_ypos , left_xpos , color);
146 putpixelfunc(bmp , bot_ypos , left_xpos , color);
147 */
148 /// Must use relative positions to find the mirrored points on the circle
149 xymirror_right_xpos = cx + top_ypos - cy;
150 xymirror_left_xpos = cx + bot_ypos - cy;
151 xymirror_top_ypos = cy + right_xpos - cx;
152 xymirror_bot_ypos = cy + left_xpos - cx;
153 putpixelfunc(bmp , xymirror_right_xpos , xymirror_top_ypos , color);
154 putpixelfunc(bmp , xymirror_right_xpos , xymirror_bot_ypos , color);
155 putpixelfunc(bmp , xymirror_left_xpos , xymirror_top_ypos , color);
156 putpixelfunc(bmp , xymirror_left_xpos , xymirror_bot_ypos , color);
157
158// putpixelfunc(bmp , cx + (top_ypos - cy) , cy + (right_xpos - cx) , color);
159// putpixelfunc(bmp , cx + (top_ypos - cy) , cy + (left_xpos - cx) , color);
160// putpixelfunc(bmp , cx + (bot_ypos - cy) , cy + (right_xpos - cx) , color);
161// putpixelfunc(bmp , cx + (bot_ypos - cy) , cy + (left_xpos - cx) , color);
162 
163 /// Check if there is a pixel in the gap between the inner radius
164 /// and the current pixel
165 if ((CurrentDistanceSquared + DistSquaredDeltaLeft) >= InnerRadiusSquared) {
166 /// There is space to the left , so plot the point without moving the actual position
167 right_xpos--;
168 left_xpos++;
169 // No need to change CurrentDistanceSquared here since x will go back
170 // to it's previous value when done plotting these points
171 
172 /// Inclusively outside the inner circle now , so plot all 8 points
173 /// 4 points using horizontal/vertical flips of top right pixel
174 putpixelfunc(bmp , right_xpos , top_ypos , color);
175 putpixelfunc(bmp , right_xpos , bot_ypos , color);
176 putpixelfunc(bmp , left_xpos , top_ypos , color);
177 putpixelfunc(bmp , left_xpos , bot_ypos , color);
178 /// 4 points using X=Y mirror of first four points
179 /**!!! Wrong - These are absolute positions , not relative
180 putpixelfunc(bmp , top_ypos , right_xpos , color);
181 putpixelfunc(bmp , bot_ypos , right_xpos , color);
182 putpixelfunc(bmp , top_ypos , left_xpos , color);
183 putpixelfunc(bmp , bot_ypos , left_xpos , color);
184 */
185
186 /// Must use relative positions to find the mirrored points on the circle
187/// Only the x changed in plotting the point to the left so only refigure those
188// xymirror_right_xpos = cx + top_ypos - cy;
189// xymirror_left_xpos = cx + bot_ypos - cy;
190 xymirror_top_ypos = cy + right_xpos - cx;
191 xymirror_bot_ypos = cy + left_xpos - cx;
192 putpixelfunc(bmp , xymirror_right_xpos , xymirror_top_ypos , color);
193 putpixelfunc(bmp , xymirror_right_xpos , xymirror_bot_ypos , color);
194 putpixelfunc(bmp , xymirror_left_xpos , xymirror_top_ypos , color);
195 putpixelfunc(bmp , xymirror_left_xpos , xymirror_bot_ypos , color);
196 
197// putpixelfunc(bmp , cx + (top_ypos - cy) , cy + (right_xpos - cx) , color);
198// putpixelfunc(bmp , cx + (bot_ypos - cy) , cy + (right_xpos - cx) , color);
199// putpixelfunc(bmp , cx + (top_ypos - cy) , cy + (left_xpos - cx) , color);
200// putpixelfunc(bmp , cx + (bot_ypos - cy) , cy + (left_xpos - cx) , color);
201 
202 // change the positions back to the current position
203 right_xpos++;
204 left_xpos--;
205 }
206 
207 /// Move the current point up one for the next check
208 top_ypos++;
209 rel_top_ypos++;
210 bot_ypos--;
211 CurrentDistanceSquared += DistSquaredDeltaUp;
212 DistSquaredDeltaUp += DeltaUpChange;
213 } // end of while loop
214
215 /// Need to check if top_ypos and right_xpos are the same /// !Relative , not absolute
216 /// , And that the point is still inside the Outer Radius Squared
217 if (!(rel_right_xpos^rel_top_ypos) && (CurrentDistanceSquared < OuterRadiusSquared)) {
218 /// Need to draw the four points at the 45 degree point
219 putpixelfunc(bmp , right_xpos , top_ypos , color);// top right
220 putpixelfunc(bmp , right_xpos , bot_ypos , color);// bottom right
221 putpixelfunc(bmp , left_xpos , bot_ypos , color);// bottom left
222 putpixelfunc(bmp , left_xpos , top_ypos , color);// top left
223 }
224 if (bmp == screen) {release_screen();}
225}

Here's the way it looks with the same test I used for your function : revised_circle_nogap
The smallest circles look a little square so there's a second option around line 45 or so to use rounded double values for the inner and outer squared boundaries that are centered around the radius. Using these makes the smallest circles rounder at the expense of shifting the boundaries inward some. w/ adjusted boundaries Let me know what you think of it all.

And as a bit of humor , here's what it initially looked like before I fixed all? the bugs. Circle or Square? I had mis-set dX so it didn't move inwards at the right pace. Maybe I'll make it a new function. :D

SiegeLord
Member #7,827
October 2006
avatar

Huh. I retested my function for overlap again, using two methods, and still found no overlap. One method was to use a custom putpixel, that detects what color it is overwriting and reports if that color is the color is the same as the color that it is about to put, which is a sign of overlapping. Also, I counted the number of times this new putpixel was invoked, and then counted the number of filled in pixels in the final image. Both tests showed no overlap, at any value of radius. This is odd at best.

As for the increasing of the radius by 0.5, I shall say this: This algorithm was never meant to draw outlined circles, rather it is meant to draw filled in circles. I guess for this specific function, since it does not use floating point position and radius, it doesn't matter... but generally fiddling with the parameters like that is discouraged. There is another algorithm for outlined circles which produces the most accurate results, and gives reasonably nice looking circles too. Here's a link to it if you are interested: pdf, the implementation provided is shaky at best, but the method is sound.

EDIT: And I tested your function, and I found quite a bit of overlap around the Y = X and Y = -X lines. It was also a tiny, but measurable, bit slower than mine.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Indeterminatus
Member #737
November 2000
avatar

@Edgar: While I usually don't care about optimization on such microscopic level, here is one suggestion because it's damn easy to do: if your code is compiled by a C++ compiler, favor pre-increment and pre-decrement operators over their post-[in|de]crement pendants when you don't need the side-effects. The rationale for this is that with operator overloading, there is no way the C++ compiler can tell and optimize a temporary variable out.

_______________________________
Indeterminatus. [Atomic Butcher]
si tacuisses, philosophus mansisses

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

- Indeterminatus -
Thanks for the suggestion , I'll change the post-increments and decrements to pre ones. If it was up to me I'd get rid of post-incrementation altogether as I think it leads to cram-coding and mistakes where too much code is put together on one line. I would just make the post incrementors do what pre incrementors do since it's much nicer to write x++ then ++x.

- SiegeLord -
I rewrote the test I used in a cleaned up fashion and copied in your latest version of your circle_nogap function and I still get the same results. I attached a picture with the test done using 4X magnification (My screen height is 800 and the test bitmap is 200X200 so it's magnified 4 times for me when I run the program). Results picture. Your proc_8 macro should eliminate overdraw in each individual circle so I think the problem is in your boundary checks somewhere.
Source code for the test :
nogap_circle_test.cpp

1 
2#include <allegro.h>
3 
4void circle_nogap(BITMAP *bmp, int x, int y, int radius, int d);
5 
6 
7int main() {
8 
9 if (allegro_init() != 0) {return 0;}
10 if (install_keyboard() != 0) {return 0;}
11// if (install_timer() != 0) {return 0;}
12// if (install_mouse() == -1) {return 0;}
13
14 int dcd = desktop_color_depth();
15 if (dcd != 0) {
16 set_color_depth(dcd);
17 } else {
18 set_color_depth(32);
19 }
20 if (get_color_depth() != 32) {return 0;}
21
22 int dw = 0;
23 int dh = 0;
24 if (get_desktop_resolution(&dw , &dh) != 0) {
25 dw = 800;
26 dh = 600;
27 }
28 if (set_gfx_mode(GFX_AUTODETECT_FULLSCREEN , dw , dh , 0 , 0) != 0) {return 0;}
29
30 BITMAP* buf = create_bitmap(dw , dh);// buffer for screen blits
31 BITMAP* dbuf = create_bitmap(dw , dh);// double buffer for blending onto the buffer
32 BITMAP* sbuf = create_bitmap(200,200);// stretch buffer for magnifying bitmap
33 if (!((buf) || (dbuf) || (sbuf))) {
34 if (buf) {destroy_bitmap(dbuf);}
35 if (dbuf) {destroy_bitmap(dbuf);}
36 if (sbuf) {destroy_bitmap(dbuf);}
37 }
38 const int sbuf_ratio = (((buf->w)/(sbuf->w)) < ((buf->h)/(sbuf->h)))?((buf->w)/(sbuf->w)):((buf->h)/(sbuf->h));
39 
40 const int opaque_white = makeacol(255,255,255,255);
41 const int clear_black = makeacol(0,0,0,0);
42 const int trans_green = makeacol(0,255,0,127);
43
44 clear_to_color(buf , clear_black);
45
46 set_alpha_blender();
47
48 clear_to_color(sbuf , clear_black);
49 for (int i = 0 ; i < 100 ; i+=2) {
50 circle_nogap(sbuf , sbuf->w/2 , sbuf->h/2 , i , opaque_white);
51 }
52 clear_to_color(dbuf , clear_black);
53 stretch_blit(sbuf , dbuf , 0 , 0 , sbuf->w , sbuf->h , ((buf->w - sbuf_ratio*(sbuf->w))/2) , ((buf->h - sbuf_ratio*(sbuf->h))/2) , sbuf_ratio*sbuf->w , sbuf_ratio*sbuf->h);
54 draw_trans_sprite(buf , dbuf , 0 , 0);
55
56 clear_to_color(sbuf , clear_black);
57 for (int i = 1 ; i < 100 ; i+=2) {
58 circle_nogap(sbuf , sbuf->w/2 , sbuf->h/2 , i , trans_green);
59 }
60 clear_to_color(dbuf , clear_black);
61 stretch_blit(sbuf , dbuf , 0 , 0 , sbuf->w , sbuf->h , ((buf->w - sbuf_ratio*(sbuf->w))/2) , ((buf->h - sbuf_ratio*(sbuf->h))/2) , sbuf_ratio*sbuf->w , sbuf_ratio*sbuf->h);
62 draw_trans_sprite(buf , dbuf , 0 , 0);
63
64 blit(buf , screen , 0 , 0 , 0 , 0 , SCREEN_W , SCREEN_H);
65
66 clear_keybuf();
67 while (!key[KEY_ESC]) {
68 rest(50);
69 }
70
71 return 0;
72}
73END_OF_MAIN()
74 
75/// SiegeLord's gapless circle function
76void circle_nogap(BITMAP *bmp, int x, int y, int radius, int d)
77{
78 int X, Y;
79 float radius2;
80 float radius3;
81 float error;
82 float dX, dY;
83 int ix;
84 int iy;
85 
86 radius2 = radius * radius;
87 radius3 = (radius - 1) * (radius - 1);
88 
89 X = radius;
90 Y = 0;
91
92 dX = -2 * X + 1;
93 dY = 2 * Y + 1;
94
95 error = X * X + Y * Y;
96
97 ix = x;
98 iy = y;
99 
100 #define PROC8 \
101 putpixel(bmp, ix + X, iy + Y, d); \
102 \
103 if (X) \
104 putpixel(bmp, ix - X, iy + Y, d); \
105 \
106 if (Y) \
107 putpixel(bmp, ix + X, iy - Y, d); \
108 \
109 if ((X) && (Y)) \
110 putpixel(bmp, ix - X, iy - Y, d); \
111 \
112 if (X != Y) \
113 { \
114 putpixel(bmp, ix + Y, iy + X, d); \
115 \
116 if (X) \
117 putpixel(bmp, ix + Y, iy - X, d); \
118 \
119 if (Y) \
120 putpixel(bmp, ix - Y, iy + X, d); \
121 \
122 if (X && Y) \
123 putpixel(bmp, ix - Y, iy - X, d); \
124 }
125 
126 while (X >= Y)
127 {
128 PROC8
129
130 if(error + dX + 2 >= radius3 && error < radius2 && X != Y)//draw the gap filler pixel
131 {
132 X--;
133 PROC8
134 X++;
135 }
136
137 Y++;
138 error += dY;
139 dY += 2.0f;//note how this happens after we add the dY
140 
141 if (error >= radius2)
142 {
143 X--;
144 error += dX;
145 dX += 2.0f;//note how this happens after we add the dX
146 }
147 }
148 #undef PROC8
149}

To find and fix the problems in my version of the function I wrote up some classes to log and map all the pixels drawn. Each circle is logged by itself and mapped into a radius and point lists that include unique points drawn and overdrawn points as many times as they occur. I started out by testing your function since it was already in the source code. I altered all the putpixel function calls to use LogPixel and I will post the source code. I don't have enough time left today to test mine so I'll just put up the results I got for your function. Drawing radius's from 0 to 99 with your function , there was no overdraw at all , however , the log reflected the overlapping concentric circles of adjacent radius shown in the earlier test.
I've attached the source code for this test here :
nogap_circle_test2.cpp
and the test log it produced here :
nogap_circle_test2_log.txt.

The first section of the log is where it lists any overdrawn pixels and the second section is where it lists the pixels of overlapping circles. I applied an offset to all the values listed so you could see the relative values instead of the absolute ones. (circles drawn at sbuf->w/2 , sbuf->h/2 which is 100,100).

The test basically narrows it down to the squared radius boundaries. Look at the list of overlapped pixels between indexes (read radii) 2 and 3. The sum of the squares of their xy position is 2 (1^2 + 1^2) which should fall in between radii of [1,2) since their squares are [1,4).

I think one problem is here :

    radius2 = radius * radius;
    radius3 = (radius - 1) * (radius - 1);

Because you're using radius2 as the outer boundary and radius3 as the inner boundary. Making the inner boundary (radius-1)^2 means that for a circle with a radius of 3 you're setting your inner boundary at (3-1)^2 = 4 and your outer boundary at 3^2 = 9. This means that a pixel at (2,0) could qualify even though you start at (3,0). The next pixel that gets checked is the one to the left which is (2,0) (dist^2 = 4) which fails because of

//
        if(error + dX + 2 >= radius3 && error < radius2 && X != Y)//draw the gap filler pixel
//

error starts at radius^2 = 3^2 = 9 ,
dX starts at -2(radius) + 1 = -5
and so passes the first check because
(9 + -5 + 2) = 6 which is greater than or equal to 4 but fails the second check because of && (error < radius2) which is (9 < 9) which is false. If you want to check the current distance^2 against the outer radius^2 there , you should check the current distance^2 that it would be after moving one pixel left in the same way you check against the inner radius^2 except that you shouldn't add the change in dX (2) there because dX doesn't actually change until after the pixel moves.

However , I submit that you don't need to check against the outer radius during the gap test at all because if the plotted point starts at (radius,0) inside the boundaries when it moves up one , the boundary can't be more than one pixel to the left because in this portion (angles [0,PI/4)) of the circle's curve , y is increasing faster than x is decreasing so if you move one pixel left , the outer boundary has shifted up enough to compensate for it.

Quote:

As for the increasing of the radius by 0.5, I shall say this :

I actually shifted the boundary radius range down by 0.5 on each end and rounded the squared result but more on that below.
In response to your view on the boundary values , I think of it like this :
In a normal cartesian environment a circle occupying a radius range of [3.0,4.0) should like wise have a squared radius boundary of [9.0,16.0) since it is centered on 0.0 but in a pixelated environment a circle centered on (0,0) is actually centered on (0.5,0.5) since the (0,0) pixel occupies all of { [0.0,1.0),[0.0,1.0) }

So the radius borders of a pixelated point are actually at [radius - 0.5 , radius + 0.5) which is the distance relative to the center point (0.5,0.5). To show this , consider the relative pixel (1,0) in the following picture.

Radii centered on (0.5,0.5) with pixel border grid using inward radial shift of 0.5
{"name":"595233","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/9\/d99097f067a7e7c7b268ad662b10aa33.png","w":512,"h":384,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/9\/d99097f067a7e7c7b268ad662b10aa33"}595233
You can see that the left pixel boundary of the pixel (1,0) is at x = 0.5 relative to the center where x = 0.5 which puts it at the correct left boundary of 1.0. The right pixel boundary is at x = 1.5 relative to the center which makes the correct right boundary of 2.0.

If you instead use border radii of [radius , radius + 1) like in this image :
{"name":"595232","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/b\/0bd3e1f36f5a599a24c87505c05bc7d5.png","w":512,"h":384,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/b\/0bd3e1f36f5a599a24c87505c05bc7d5"}595232
then the small radius circles are very square from 0 - 4 for the radius as can be seen in this colored in image :
{"name":"595235","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/c\/8c5f870900488ea328275ea07ae98c60.png","w":512,"h":384,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/c\/8c5f870900488ea328275ea07ae98c60"}595235

Now compare it to a colored in image drawn using border radii of [radius - 0.5 , radius + 0.5) :
{"name":"595236","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/9\/e92a1efd05980fff9933c72d5ed285a9.png","w":512,"h":384,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/9\/e92a1efd05980fff9933c72d5ed285a9"}595236

Even if your version is meant to draw filled circles , it makes sense to use the inward shift because it more accurately represents the area they should cover. Also , since the decimal portion of the value is always .5 when using the inward shift then when squared it is 0.25 which when 0.5 is added for rounding it justs gets truncated anyway so my attempt at rounding the number is moot and not useful so I'll take it out. I'll post my revised version tomorrow after I go over it again to get rid of the x=y overdraw. Let me know what you guys think of all this , thanks , Edgar. ;)
[/massive_post]

 1   2 


Go to: