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

 This thread is locked; no one can reply to it. 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).

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).

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

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:

 1 void 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

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).

 1 void 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 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 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 Quote: 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

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 :

 Indeterminatus Member #737 November 2000 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 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.

 1 void 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 Well , something is not quite right with it yet.http://www.allegro.cc/files/attachment/595171So 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 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

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 2 void 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(fc_red - sc_red)/static_cast(abs(frame_thickness - 1)); 52 double sc_to_fc_green_delta = static_cast(fc_green - sc_green)/static_cast(abs(frame_thickness - 1)); 53 double sc_to_fc_blue_delta = static_cast(fc_blue - sc_blue)/static_cast(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(frame); 73 gc_red = sc_red + static_cast(d_frame*sc_to_fc_red_delta); 74 gc_green = sc_green + static_cast(d_frame*sc_to_fc_green_delta); 75 gc_blue = sc_blue + static_cast(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 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)) Now, the algorithm goes as follows: Start at a point (R, 0).Increment Y.Test if the point is still in the circle.If it isn't, decrement X.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 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

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:

Find error(X - 1, Y)

Now, subtract the two errors:

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.

 1 void 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):

 1 void 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

- 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 :

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.

 SiegeLord Member #7,827 October 2006 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 @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

- 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 3 4 void circle_nogap(BITMAP *bmp, int x, int y, int radius, int d); 5 6 7 int 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 } 73 END_OF_MAIN() 74 75 /// SiegeLord's gapless circle function 76 void 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;
```

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
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.