|
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). 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:
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. |
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(). =-----===-----===-----= |
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: -- |
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:
Just replace this line in your code: With this:
"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18 |
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. |
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).
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 |
konedima
Member #6,241
September 2005
|
<sheepish apology> War Pong HD! Every time you don't download it, a kitten of hope dies in my heart. Please, save the imaginary kittens. |
Neil Black
Member #7,867
October 2006
|
I was wrong.
|
SiegeLord
Member #7,827
October 2006
|
Quote:
<sheepish apology> 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 |
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.
My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
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)? _______________________________ |
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.) My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
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.
War Pong HD! Every time you don't download it, a kitten of hope dies in my heart. Please, save the imaginary kittens. |
Edgar Reynaldo
Major Reynaldo
May 2007
|
Well , something is not quite right with it yet. 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. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
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 |
Edgar Reynaldo
Major Reynaldo
May 2007
|
Quote: My function's still faster.
And still too difficult to read easily. - konedima -
My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
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:
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 |
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 : 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. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
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.
EDIT: Fixed bug. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18 |
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):
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. |
Edgar Reynaldo
Major Reynaldo
May 2007
|
- konedima - - SiegeLord - 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 : Relative x and y is tracked to know when to stop drawing. 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 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. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
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 |
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. _______________________________ |
Edgar Reynaldo
Major Reynaldo
May 2007
|
- Indeterminatus - - SiegeLord -
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. 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 , 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. 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 If you instead use border radii of [radius , radius + 1) like in this image : Now compare it to a colored in image drawn using border radii of [radius - 0.5 , radius + 0.5) : 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. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
|
1
2
|