Allegro.cc - Online Community

Allegro.cc Forums » Game Design & Concepts » EasyToUse Dynamic Color Gradiant Generator

This thread is locked; no one can reply to it. rss feed Print
EasyToUse Dynamic Color Gradiant Generator
Dennis
Member #1,090
July 2003
avatar

[EDIT]
(to make sure you don't download a buggy version)related posts:
Miran's latest version with GUI,[url http://www.allegro.cc/forums/view_thread.php?_id=518074#target]
version3 with all *fixes*(the attachment of that post)[/url]
[/EDIT]

Twinkle, twinkle little star..., looks nice:).

I'm going to write an experimental version3 now.(will preserve the previous one again and i will not change your code miran, it's easier for me if you just grab my changes later that is if it turns out that you like them;))

What i will add:
-polynomial attractors/absorbers (unit will be freely selectable)

I don't know how long it'll take for me to implement it, but in fact after thinking about this while i was asleep, i found out that it won't be too hard to do.
I expect to have them up and running in about 5 maybe 7 hours.

(sidenote: yay, "pearls" is the IOTD)
---

[EDIT](a few hours(five and a half to be precise) later and after a mindtwisting coding session(ha, it's not like i do things like these every day:P)*phew*...)

http://homepages.compuserve.de/DennisTapier/allegroforum/COLGRAD3.PNG

Showing example one of the old version2 plus two of the new CA_POLYNOMIAL attractor types.

New version 3 is attached(sources + precompiled statically linked win32 binary).
(Check readme.txt and new comments):)

NEW Features:
-Polynomial Attractors/Detractors with a freely choosable origin and unit
(both given in pixels)

miran
Member #2,407
June 2002

Very nice! I don't think I'll be able to update the GUI though (I'm busy with other things), but you have the code and it's not very difficult. I suggest you make a polynom editor dialog and put a button that opens it in the main dialog, sort of like the colour selector, otherwise everything will get too crammed....

--
sig used to be here

Dennis
Member #1,090
July 2003
avatar

miran said:

I suggest you make a polynom editor dialog and put a button that opens it in the main dialog

I'll start learning MASkinG tomorrow. Thanks again for all the work you put into it.:)

da_flo
Member #1,907
February 2002
avatar

I just took a look at your new version, since I found the new screenshot nice and yet weird.

Digging into your code, I found what I was quite sure to find : in distance_to_ca3, if you have a CA_POLYNOMIAL, you don't really compute the distance to the polynomial ca, hence the weird shape of your polynomial gradients. For the other types of ca, you actually compute the true distance to the objects.

If your polynomial is called P, distance_to_ca3 returns P(x) - y, whereas the distance the polynomial should be the minimum of all the distances from (x,y) to any point on the polynomial curve. That will be quite slow to compute. I don't know if there's an easy way to get such a distance, like there is for lines. :-/

Well, it still looks good that way, but I just felt like pointing this out, to stay consistent with the first versions of your algorithm.

Then, a few remarks about your make_plut function, where you compute the lookup table.

First, why do you compute cy using -= instead of += ? Please explain, I must be missing something. :-/
Also, it seems that for each monomial (does this word exist in english ? ???), you compute x^j using pow. That's a naive and slow way to do polynomial computations. Take a look at the Horner algorithm. It's easy to code, and does less calculations than the naive way (although the difference would be hardly noticeable with degree 2 or 3... but it's just an habit ;)). Well, I do not have links right now, but google is our friend, or I can even write the code for you, it won't take much time.

Dennis
Member #1,090
July 2003
avatar

da_flo said:

[..]you don't really compute the distance to the polynomial ca[..]
[..]That will be quite slow to compute.

Yes, I know about that. It was intentional to make the computation easier and faster.
Snippet from my header file:

CA_POLYNOMIAL /* v3, a color attractor based on a polynomial function 
                   in distance computations the value of that function at that
                   x position is used, so any points of the polynomial
                   that might be nearer to the current pixel will be ignored*/

da_flo said:

First, why do you compute cy using -= instead of += ? Please explain, I must be missing something.:-/

It's to invert the y, so that x^2 e.g. will look the same as if you draw that on a piece of paper, where you normally want y to increase to the top, whereas on bitmap coordinates in computers y increase towards the bottom...ah i know now what you mean. It's inconsistent with the interpretation of the HBAR y values and it will be changed.

da_flo said:

Also, it seems that for each monomial (does this word exist in english ? ), you compute x^j using pow. That's a naive and slow way to do polynomial computations. Take a look at the Horner algorithm.

In german it's called 'Monom', i think.
Found HornerScheme:)

After all, i see that it'll not be that easy to update the GUI for me(I even think of just totally dropping the idea of having a GUI at all.), i've decided that i will clean up my code first(and removing those inconsistencies mentioned) and then port everything to cpp using proper classes and so on and after that...oh well i don't know what i'm going to do after that as i do realize that my interest in the thing is already fading very quickly.:P (It's always the same with me: Just quickly doing a few tests and stuff, experimenting a little is always great fun but then it slowly starts degenerating into work, rather than a just-for-fun freetime project.;))

During the process of porting i'll just drop support for older versions, because this is the only way i see to make code and functionality clean and consistent in itself. But i don't think this will be much a problem for anyone(How many people did actually use the thing to create sth.?Not many i guess.) as the old version is still there.

I hope nobody gets angry with me over this(especially not Miran who already did so much work on his GUI).:-/

miran
Member #2,407
June 2002

Yeah, I know exactly what you mean. Anyway, another small update from me: v1.10 now has LUT optimized effect modifier function again (exp and p in range 0.0-4.0, definable with sliders, not editboxes) and a randomize function. That last thing is really fun. A lot of times it generates a totally black or white image or something else equally uninteresting, but if you press the "Random" button for long enough, you're bound to find something goo looking... :)

Sorry, I didn't incorporate test v3 yet :(

--
sig used to be here

Dennis
Member #1,090
July 2003
avatar

miran:
That's no problem;) as v3 is not yet in it's final state and i plan on making several convenience improvements(from a developers point of view) in the cpp port, that is each attractor will be inherited from a base attractor class and then override its' own methods for distance computations, writing and reading a single attractor to a file pointer and such nice things. Also each attractor will have access methods that allow for setting relative values and absolute ones and in each of them the other values will then be generated automagically.(Saving will always be done as relative values and the head of each save file will incorporate original resolution settings, basically because i want to support bitmap sizes other than standard screen resolutions.)
I also plan on doing the save methods in a way that the generated file will be a human readable text file that can even be hand edited and will be parsed by the programm.

I'll check your new version now. Randomizing sounds interesting.:)

da_flo:
I already implemented horner scheme now, but it's a so small change i won't upload an entire new version.

/* using "Horner Scheme" to compute function value */
   cy=PN->co[PN->he]*cx;
   for(j=(int)PN->he-1; j>0; j--)
     cy = (PN->co[j] + cy)*cx;
   cy = cy + PN->co[0];

(and y is interpreted as growing downwards now, so it's the same way as in HBAR)

[edit]
The random button rocks.:D It created a mystical planetary sunset scenery.(attached) Looks like you turned our PCs into abstract artists and they certainly do better in that than any ape;).

miran
Member #2,407
June 2002

Glad you like it. There's just one question now: which one to use as my new wallpaper? :)

--
sig used to be here

Dennis
Member #1,090
July 2003
avatar

I would throw a dice to select either 11(flashy) or 13(green).:)

Martin Cerny
Member #3,931
October 2003

Hi,
I liked the thing...Can't run that now, since I don't have a compiler on this machine:(
The problem of distance to a polynomial curve got my interest, I spent some three hours with pencil and paper, but to me (I might be missing something, I still have not left high school) it seems that you can't directly (without calculating distance to all points on the screen) compute a distance to a polynomial of n-th degree (hope, that's the right terminology) without solving an equation of (2n-1)th degree - that would mean that for a cubic curve you would have to solve an equation of 5th degree, which is impossible. (if anyone's interested in the math background to this, I can send it here, but it seems most people here don't like math too much)
But you can in quite a fast way compute the 'distance map' for whole screen - the idea is this. The closest distance of a point to a curve is always at right angle to the tangent at the closest point of the curve (hope that's right premise, otherwise everything below is crap). So for each point of the curve you calculate the distance to all points lying on the normal to tangent in this point, which would be quite fast. If the distance to any point on the normal has already been computed, you overwrite it in case the new one is lower.
Mathematically: (too bad I don't have a scanner at home, it's hard to rewrite the math formulas)
let's have a polynomial of n-th degree
f(x)=a(n)*x^n + a(n-1)*x^(n-1)+ ... + a(1)*x + a(0) , where a(b) is the factor for x^b
the tangent in a point of a curve is defined by the derivative of the curve, which is
f'(x) = n*a(n)*x^(n-1) + (n-1)*a(n-1)*x^(n-2) + ... + 2*a(2)*x + a(1)
so the tangent in point X is defined as
t: y = f'(X)*x + c
after conversion to a common line formula:
t: f'(X)*x - y + c = 0
we chose a line p so that p is at right angle to t
p: x + f'(X)*y + d = 0
point [X,f(X)] lies on p so:
X + f'(X)*f(X) + d = 0
and thus
d = -X -f'(X)*f(X)
so the complete formula for p stands:
p: x + f'(X)*y -X -f'(X)*f(X)
we qualify x coordinate:
p: x = -f'(X) + X + f'(X)*f(X)
so now, for each point on y axis we can find a point lying on p
now the distance d from point [X,f(X)] to point A[-f'(X) + X + f'(X)*f(X), y] on p is described by point's A y - coordinate as follows:
d(y) = abs( (y - f(X)) / cos(alpha) )
where alpha is the angle between p and y axis:
alpha = atan(-f'(X))

Hope It was not totally confusing. I would implement that myself, but I don't have a compiler on this machine and won't have acces to one probably for next few days (the other PC broke) I'll try to write the code without compiling it:

1float polynomial[degree]; //this is a parameter
2float derivative[degree-1];
3float distance_map[SCREEN_W][SCREEN_H];
4 
5float x,y,next_y,next_x,step,derivative_y;
6float normal_linear,normal_absolute,distance,cos_alpha;
7int map_x,map_y,i,j;
8 
9for(i=0; i<SCREEN_W; i++)
10 for(j=0; j< SCREEN_H; j++) distance_map<i>[j]= SCREEN_W * SCREEN_H //-that should be higher than any real distance
11 
12for(i=0;i < degree-1; i++) derivative<i>=polynomial[i+1]*i+1;
13 
14//the counting should start before and end after the edge of the screen, the range is just a guess
15for(next_x=-SCREEN_W,x=0; x< 2 *SCREEN_W;) {
16 x=next_x;
17 next_x+=1;
18 y = evaluate(polynomial,x); //counts the value of a polynomial for the argument
19 next_y = evaluate(polynomial,x+1);
20 step = 1 / (abs(next_y / y) * (SCREEN_W/10)); //the step needs to be small enough, so that no pixels on screen stay untouched, the coefficient SCREEN_W / 10 is just an approximation, maybe it should be higher
21 for(;abs(x-next_x) >= step;x+=step) {
22 //calculate the normal to tangent
23 y = evaluate(polynomial,x);
24 derivative_y = evaluate(derivative,x);
25 normal_linear = -derivative;
26 normal_absolute = x + (y * derivative_y);
27 cos_alpha = cos(atan(normal_linear)_;
28 for(map_y=0;map_y<SCREEN_H; map_y++){
29 //for each point on the normal, calculate the distance
30 distance = abs( (map_y - y) / cos_alpha);
31 map_x=floor( (normal_linear * map_y) + normal_absolute);
32 if(distance_map[map_x][map_y] > distance) distance_map[map_x][map_y]=distance;
33 }
34 }
35}

Well that should be it... Hope there are no mistakes.
Maybe my effort was totally useless, but it was fun to me.

And yes, I love math.

Baba
---------------
Smile, it's gonna be worse.

da_flo
Member #1,907
February 2002
avatar

Quote:

(if anyone's interested in the math background to this, I can send it here, but it seems most people here don't like math too much)

I do like maths. ;)

Indeed Abel showed that polynomial equations of degree 5 and above (degree 4 as well ? I don't remember) can't be solved algebrically, but here that's not really a problem. We're interested in numerical solutions. But solving numerically could be quite slow, too. Depends on the algorithm and the accuracy wanted.

I only read your distance map algorithm quickly, so I didn't get much into it, but is it really worth it ?

Dennis
Member #1,090
July 2003
avatar

Martin said:

The closest distance of a point to a curve is always at right angle to the tangent at the closest point of the curve (hope that's right premise, otherwise everything below is crap). So for each point of the curve you calculate the distance to all points lying on the normal to tangent in this point, which would be quite fast. If the distance to any point on the normal has already been computed, you overwrite it in case the new one is lower.

That would be awfully slow, as even for a simple x*x polynomial, every pixel position above the curve would unnecessarily be used at least twice(lots of tangent normals crossing in that area) in distance computations.

It would be much faster(yet still painfully slow) for every pixel to just compute the distance from that pixel to all points on the polynomial(which are already stored in a lookup table) and then just pick the smallest.

That would always lead to a constant number of (width*height)*width distance calculations, no matter what type of polynomial used.

But still it would not make sense to store those distances to the polynomial for all pixels in a lookuptable, because in one go of the algorithm, every pixel is just once processed so there would be no gain from that at all.

Neil Walker
Member #210
April 2000
avatar

Hello,
Why not add to the GUI a text export option to export your attracters as text in the format of the function declarations so you can just copy/paste into code ?

Neil.

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

Martin Cerny
Member #3,931
October 2003

Quote:

It would be much faster(yet still painfully slow) for every pixel to just compute the distance from that pixel to all points on the polynomial(which are already stored in a lookup table) and then just pick the smallest.

That would always lead to a constant number of (width*height)*width distance calculations, no matter what type of polynomial used.

I disagree - in the algorithm as I implemented it, there are NO distance calculations using pythagora's theorem. For every point on the curve, you evaluate two polynoms,compute two goniometric functions and do SCREEN_H * 2 floating point operations, plus SCREEN_H * comparison.

But maybe it would be better, not to count so much normals (bigger steps), and if a pixel was left untouched, aproximate it's distance linearly from two closest neighbours.

Than the resulting difficulty would be about SCREEN_W * SCREEN_H for linear function up to SCREEN_W * SCREEN_H^2 for a polynomial covering every pixel on the screen...

Without a lookup table, this method won't be possible, so that's the reason for the table.

And the number of operations in your method would have been also a bit bigger, because there could be more than one point of the curve for a pixel in x-axis, so you get SCREEN_W^2 * SCREEN_H up to SCREEN_W^2 * SCREEN_H^2 operations. I win ;D

Quote:

(degree 4 as well ? I don't remember)

As far as I remember, my math teacher told me, there is a formula to solve 4th degree equations. And yes, solving numerically would be painfully slow... I don't have much time now, but I could send you my sketches for the distance computing...

Baba
---------------
Smile, it's gonna be worse.

Dennis
Member #1,090
July 2003
avatar

Martin said:

And the number of operations in your method would have been also a bit bigger, because there could be more than one point of the curve for a pixel in x-axis,[..]I win;D

You're not trying to tell me that for a fixed x value there might be two different y function values for any polynomial...(or at least you should not try to tell me so, because it is just wrong).

There is always and exactly one y value associated to every x in a polynomial of the form y(x)=a(n)*x^(n)+a(n-1)*x^(n-1)+...+a(1)*x+a(0), where a(.) are the coefficients. You lose, your Math-FU is weak, as some people around here would say.;D

Martin Cerny
Member #3,931
October 2003

Oh no - you misunderstood.
If you have y=x^2, then between point [2,4] and [3,9] which are one pixel far away on x axis lie 5 pixels of the curve, so five distances have to be calculated, not one.

Baba
---------------
Smile, it's gonna be worse.

Dennis
Member #1,090
July 2003
avatar

myself said:

It would be much faster(yet still painfully slow) for every pixel to just compute the distance from that pixel to all points on the polynomial(which are already stored in a lookup table) and then just pick the smallest.
That would always lead to a constant number of (width*height)*width distance calculations, no matter what type of polynomial used.

See on a bitmap there is a width*height number of pixels. And for each pixel along the width there's exactly one function value. So that'll be exactly (width*height)("for every pixel...") * width("to all points...") distance computations, or what???

Martin Cerny
Member #3,931
October 2003

OK, I haven't read the source code, so you do not count whole curve, but only the points where x is a whole number? So if you have curve x^4, then the distance of point [1,6] to the curve would be 5 (Nearest points are [1,1],[0,0] and [2,16])? Because that's obviously not true, for the distance is less than 1.

EDIT: Sorry for others, my argument with DB is getting a bit off-topic.

Baba
---------------
Smile, it's gonna be worse.

Dennis
Member #1,090
July 2003
avatar

Martin said:

EDIT: Sorry for others, my argument with DB is getting a bit off-topic.

No not at all and it has got nothing to do with the way it is implemented in my code. I do fully understand what you're doing...we might have a communication problem though.([edit]In my current code i am NOT calculating the true distance but that is what we're arguing about: We want to find the fastest way to calculate the true distance.[/edit])

Here's two sketches to illustrate the problem i see in your method and that i mentioned in my first reply to your post.(You might want to closely reread that first reply while comparing it to these sketches.
First the example i gave above(slightly inaccurate in places;)):
http://homepages.compuserve.de/DennisTapier/allegroforum/mathex1.png

Now an example where the issue matters even more:
http://homepages.compuserve.de/DennisTapier/allegroforum/mathex2.png

Martin Cerny
Member #3,931
October 2003

I understand that - but while I was asleep I found out what my first reply should have been. If you calculate the distance to all points on the curve, you get num_points_on_curve * width * height. My algorithm uses num_points_on_curve * height. Well, my step is maybe a bit slower than yours (you have two multiplications, addition and a square root for a loop, I have two additions, two multiplications and an if)
I don't think that lots of normals crossing is a problem, the speed of algorithm is not affected by that - no matter how many times the normals cross, you count the same amount of them. And it won't be too much, for I think that any point can't have more than polynom_degree + 1 normals crossing it - well a pixel covers more than one point, but still...
Yes, I think we had just communication problems.

The argument before was about the fact, that num_points_on_curve may vary from width to width * height, depending on the complexity of the curve - with which I hope you agree.

Baba
---------------
Smile, it's gonna be worse.

Dennis
Member #1,090
July 2003
avatar

Martin said:

Yes, I think we had just communication problems.

And i think these communication problems are still going on.:(

Martin said:

The argument before was about the fact, that num_points_on_curve may vary from width to width * height, depending on the complexity of the curve - with which I hope you agree.

Independent of the complexity of the curve: num_points_on_curve==width, always. It does not vary.(There are also y offsets that are not inside the bitmap you know but still to every x position there is one and only one y offset associated: points_on_curve==width.)

I'm not sure anymore which method would be faster(yours or mine) but now i see other problems in yours. In the -x^2 example above take a pixel that lies on the left side of the bitmap and on the curve, how does your algorithm ever realize that none of the pixels of the tangents normal in that point is ever touching any pixel on the bitmap area. Will it just forever go on examining the points on that line?
It might also be the case that i don't understand your code, because it looks very odd to me. Maybe you could prepare a graphic in paint to explain it a little better. That would help a lot.:)

I think, we need a third opinion here.

Martin Cerny
Member #3,931
October 2003

Sorry, don't have any place to upload the image to, so it's attached.

If you count only one point of the curve for a point on x-axis an x^2 curve would contain only pixels that are black on the image. But it should also contain those green pixels - if you would count distance only from black pixels, you'll get that red pixel's distance from the curve is 2 (nearest point would be [2,4]) but that's obviously stupid, since red pixel's distance to the curve is 1. Do you follow me?
So instead of width pixels (7 on the image) the curve has to contain 17 pixels. So you have to count (in both yours and mine algorithm) more than width steps.

Baba
---------------
Smile, it's gonna be worse.

Dennis
Member #1,090
July 2003
avatar

I can follow you, no problem and now i can even see our communication problem. You're right with your drawing, but realize that this programm is not one to render polynomial curves(If that was the case i would draw a simple line from every of my [x,y] pairs to the next...) and usually the "unit" used here is not a single pixel but more likely 100 pixels or 200 or even more. That alone would still lead to a few pixels on the curve not rendered, but again, this programm does not render the true polynomial.(The fact that one is able to see an idea of the actual polynomial results from the illusion created by mixing the colors.) And also the "range" attribute which describes the area around the polynomial(but not the true one, just the area around every "theoretically" rendered pixel) is usually not set to 1.(If "range" is set to one(pixel) and "unit" also to one(pixel) then it creates exactly the drawing you described with pixels staying black, but this can be neglected here, because a gadient along a thickness of 1 pixel is not a gradient, just a single color anyway.)

However, i went over the whole thing again, starting at your first post. Your premise was:
"The closest distance of a point to a curve is always at right angle to the tangent at the closest point of the curve (hope that's right premise, otherwise everything below is crap)."

With a little thinking i found an example point "a"(in fact a whole Area "A" with lots of such points) for which your premise seems to be false.
I in no way want to claim that the following drawing, which i prepared, is a proof that your premise is false but it looks valid to me.
Here:
http://homepages.compuserve.de/DennisTapier/allegroforum/mathex3.png
[EDIT]NOTE FOR LATER READERS: This pic has already been proven to be wrong later in the thread so there is no need to comment on it anymore.[/EDIT]

Martin Cerny
Member #3,931
October 2003

The picture definitely is not a proof ... I wish I had a scanner or a digital camera... MS Paintbrush sucks. But well I have an image. Look, there is a point A and it's distance to curve's peak P. But because AP is not at right angel to the tangent, a circle with center in A and r = |AP| has to have more than one intersect with the curve - C (unmathematically : in a very close place around a point the function value is nearly equal to the tangent. Since the tangent is not at right angle to the distance, you get closer to A by moving right over it, so by moving right a bit on the curve you also get closer to point A) the closest point then lies between those two - B. I understand that's not a mathematical proof, but I think one could base the proof upon this idea.
Was I clear?

EDIT:
The problem with "spaces" between pixels is not limited to drawing - as I've shown, if you omit them, than the distance calculation is inaccurate. But yes, basically both algorithms can omit them with a slight loss of precision (mine would loose more)

Baba
---------------
Smile, it's gonna be worse.

Trezker
Member #1,739
December 2001
avatar

Random is the shit!
Seriously, check this out! :o



Go to: