EasyToUse Dynamic Color Gradiant Generator
Dennis

[EDIT]
Read the entire thread to find the newest version...;D
or if you're lazy and not interested in any background information, here are 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]

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

The above pic was created by just these few lines: :D

init_ca_list(&test1);
add_to_ca_list(&test1,POINT,0,0, 255,255,0, 500);
add_to_ca_list(&test1,POINT,639,479,0,255,0,500);
add_to_ca_list(&test1,POINT,320,240,0,0,255,500);
add_to_ca_list(&test1,GLOBAL,40,0,255,255,255,0); 
render_col_grad_to_bitmap(backb,&test1);
kill_ca_list(&test1);

Fully self documented C-sources + precompiled win32 binary(with more examples) is attached.

Share your creations by posting your own EXAMPLE BLOCKS(see inside "main" in code).8-).
[edit]
Hehe, <b>forget about those code blocks. Miran created a GUI for the thing.</b> Scroll further down, grab it and then just post your saved files for everyone to enjoy!;)
[/edit]

Have fun!

Edward Sheets

Looks good, Dennis :)

Maybe you can tweak your code to make it do some funky gradients like Phipps does in Sunny Ball :D

Dennis

I've downloaded SunnyBall to see them...(but i will be too tired today to check it out...yawn, will, go, to, sleep, in, a ,minute...)

[edit]
After a healthy and relaxing sleep of about 8 hours, i played through the demo version of SunnyBall(:D"Fun game Richard!":D) but i'm afraid i could not see any gradients that could not easily be created by my generator... I think it's just a matter of choosing the right bitmap dimensions and setting the correct "color attractors".:) But i might be wrong. Please specify what exact gradiants in SunnyBall you were referring to(the backdrops?,the borders?,the message windows?).

miran

Nice. I made a GUI for this thing: here (535 kB). It's based on my own attempt to figure out how Sunny Ball gfx were made (I was way off btw.) It's C++ source code + statically linked Windows binary + all the original examples :) EDIT: + some of my own examples which are also attached in one of the posts below.

EDIT: Forgot to mention it. I changed x,y and range from absolute values to relative ones typically in the range 0-1 so the gradients can be scaled more easily.

Neil Walker

So how do you change any of the values, it always enters values of .5 .5 .5 no matter what you enter as the positions/range.

Neil.

miran

First you add an attractor or two. Then select the attractor whose values you want to change. Then you type new values in with the keyboard. When you're finished typing you press enter.

Dennis
miran said:

Nice. I made a GUI for this thing: here (529 kB).

Great miran!
I can't await to play around with it.:D Got to check it out...:):):)

miran said:

I changed x,y and range from absolute values to relative ones typically in the range 0-1 so the gradients can be scaled more easily.

Have not tried the GUI yet... i hope it's possible to enter values outside that range because the generator supports "color attractors" that are outside of the actual bitmap.;)
(btw: Changing the values to relative ones also was on my mind for future versions and improvements, looks like you've read my mind;))

miran

Yeah, it's possible to enter any value. Btw, I didn't change your code (other than to separate it into .h and .cpp files and make it compile as C++), I just added an extra layer between the GUI and your code.

Oh and attached are a few more examples :)

Dennis

Wooohooo, Miran, I love your GUI.:) Attached is my newest creation "pearls", which is now(thanks to the cool export feature) my desktop background.8-)

crits and usability improvement suggestions(i know lots of work;D):

  • pressing "add" should also change the selected attractor to the one just added, because most time that is the one that will be edited next

  • a "duplicate" button might come in handy

  • would be cool if position could be adjusted by directly clicking the image

  • would also be cool if the used colors would be shown next to each list entry

  • a credits section "GUI by Miran Amon, gradiant algorithm by Dennis Busch"

  • option that the user can save "author" "title" "creation date" text fields into his files

After all, i think your GUI is so cool that actually the whole thing could already be considered a very useful utility.
You should add that to the depot!8-)

da_flo

I quickly read the source, and the concept is simple and yet the result is impressive ! :D

When I am less tired I'll really look at it. That might motivate me to play myself with my own graphics effect. Yeah I haven't coding in a while, that ought to make me in the mood for speedhack. :)

Dennis

Make sure you don't miss Miran's GUI for it. It really makes creation easier.;)

da_flo

Indeed. I used Miran's GUI right from the beginning. :)

I had never tried MASkinG before... I have a program based on the allegro GUI, and I'm now considering using MASkinG instead of porting it to wxWidgets. (and yeah I know, Qt4 rules too, but I got through all the hassle learning wxWidgets, so I might stick with it too :P)

[EDIT] (I hope this will be noticeable enough :-/)

Hey I had an idea to play with your gradient algorithm, Dennis. :)

I love maths and when I have a model or an algorithm, I like to generalize it and play with various parameters.

I was thinking to let the user choose the distance function used in the algorithm. We could use a distance function pointer, and let the user choose between several examples of distances, shown in a listbox.

I have some examples of classical distances in topology :
Norm 1 :

N1(x,y) = |x| + |y|

Norm 2 (euclidian distance) :

N2(x,y) = sqrt(x^2 + y^2)

Norm p :

Np(x,y) = (|x|^p + |y|^p)^(1/p)

Norm infinity :

Ninfinity(x,y) = max(|x|,|y|)

I we use only those norms, we can even use a N(p, x, y) function rather than a function pointer, passing p=-1 for Ninfinity.
The only problem is that it works easily for points, but it becomes tricky we using bars or other objects. I don't know how to compute the distance from a point to a line with non-euclidian distances.
In fact, if I work on the maths, I can perhaps find a formula for the distance to a line with Np, but it might become quite heavy.

What do you think of this idea ? :)
If I find some time, I could do a small program using those norms with points, using the allegro GUI. But if Miran of anyone is motivated to try it, don't wait for me... ;)

miran

Dennis: Updated to version 1.02. Redownload from the link in my first post! :) All your wishes have been implemented, except for number 3. That would take a bit more time (I'm lazy).

da_flo: Won't be too difficult to add. Just add another field to the CA_DESC struct, modify distance_to_ca() and update the GUI :)

Edward Sheets
Quote:

i could not see any gradients that could not easily be created by my generator

Yeah, I was probably wrong. I was referring to the tiles and background gfx in SunnyBall. There's been speculation as to how Phipps creates those gfx. Maybe gradient is the wrong word for that effect..? Anyhow, it's probably best if we don't anger Phipps by trying to hack into his mind and emulate his methods. ;D

Richard Phipps

I'm constantly surprised by people's interest in the gfx engine used in Sunny Ball. I suppose I should be flattered! :)
The engine originally was intended to be used for a flip screen puzzle-platformer in the style of an old game called 'Journey to the Planets'

This was several years ago (sorry guys!), here is one of the first mock up images I did (dated 18th March 2002):

http://www.reflectedgames.com/Images/mockup_screen.png

Unfortunately there would have been a lot of art to do and I am not an artist. Perhaps some day.. :D

Anyway, the technique is not too difficult to do and pretty easy to figure out how it works IMHO. Having said that, while it is useful it does have some limitations so I wouldn't use it for many types of games.

Neil Walker

I guess two questions.

1. How fast is it in realtime for generating a full screen bitmap (as in does it have to be pre-rendered to a bitmap outside of any timer loop)

2. Has anyone tried doing any blending over images? I'm thinking something like this effect would be cool:

http://images.amazon.com/images/P/B000002LRJ.01._SCLZZZZZZZ_.jpg

Attached is my closest rendition

[edit]
It would be nice to be able to move the attracters up/down as I added black at the end but it never shows, I need it to be at the start.

Neil.

Dennis

da_flo:
I will examine your post more closely when i'm offline.

Richard(thanks for following the invitation):
Looking at your screenshot, i guess i know how it works:
I think you're computing gradiants on several bitmaps and then copy only
polygonal areas of them in a certain blit order to get these nicely layered, color faded screens.;)

miran said:

All your wishes have been implemented, except for number 3.

Thanks alot, i will try it out.:)

Neil said:

It would be nice to be able to move the attracters up/down as I added black at the end but it never shows, I need it to be at the start.

The position of any attractor inside the list has no effect to the result. Black never shows because of the mixing method that my attractors only evers ADDS fractions of colors. But i could invent detractors that would take away fractions of colors but then list position would matter and that would require too much work for now(i'm even more lazy than miran;)) [edit]hm...maybe list position would not matter if i let negative color values stay valid until the call to putpixel...[/edit]
On your questions:
1: depends on resolution and bitdepth(32bpp fastest, 8bpp slowest due to color conversion).
2: the current algorithm does not support that(because its not "blending" anything), but you could do it in any image manipulation programm, using the exported image.

miran
Quote:

The position of any attractor inside the list has no effect to the result. Black never shows because of the mixing method that my attractors only evers ADDS fractions of colors. But i could invent detractors that would take away fractions of colors but then list position would matter and that would require too much work for now(i'm even more lazy than miran;)

I already added the ability to move attractors up and down in the list. It's just that I disabled it (as in commented the relevant code out) because I realized the order has no effect.

As for different blenders, that would be a good idea. Having just ADD is kind of limiting, because you can't darken a part of the image. Every attractor just adds to the colour and moves it towards white. I don't know exactly how those blenders I have in my PSP work, but there are many of them: multiply, screen, dissolve, dodge, burn, overlay, hard light, soft light, etc.

Another thing that you could make is add linearity to POINT, VBAR and HBAR (I don't know if linearity is the right word). Right now the gradients are fully linear, that is, at the centre of the point you have full colour, then it fades linearly towards the edge. You'd get a lot more flexibility if you could define how fast or slow the gradinet should fade. If you know what I mean :-/ (Maybe that's what da_flo was talkin about. I'm not good at this advanced maths stuff.)

Dennis

I think i know what you mean miran(it involves calculus, in which i'm not very good...) you want a function for each attractor that calculates its' intensity influence in relation to distance(currently this is linear because just the plain distance is calculated).
(i know i should not but i fear that particular field of math)

For a first small improvement, i will look into adding support for SUBTRACT(color "absorbers") now, so that areas can be darkened(i will implement this in a way that list positions will not matter) and the funny thing will be that the absorber will work like mixing but in the opposite direction(as in: I'm an absorber and i'm very selective about what color fractions i'll take away.:))

I think i've found a BUG:( in the FileSaving Dialog:
When i press enter inside the FileTextEditField it always(?or only if the file does not exist,but even if a proper ending .wcol is entered) assumes that the entered text is a directory and places a \ behind it and then nothing happens, pressing enter again sometimes crashes the thing(my by hand avoid crash method: Enter Text and then use mouse to press OK).

da_flo:
Maybe your suggestions would be the same as having individual intensity(distance) functions for each attractor? I'm a little puzzled.

Attached are some more simple examples and an iconized version of miran's "flair" to replace that AlexAllegator icon.

miran

I added linearity settings :) This time I did modify your code (in wcolgradgen.h and wcolgradgen.cpp) so if you work on it some more, it'd be best if you didn't loose my changes :)

About the file selector bug, I know about that, I've know abotu it for a long time. Will fix some day...

EDIT: And now version 1.04 is up. You can now place attractors by clicking on the preview. Left click moves the attractor, right click defines range. You can only move inside the image though...

Neil Walker

Lovely.

Now, don't get me wrong here, but while Masking looks very pretty, the interface is crap. Unless its just a coding thing?

What I see thats wrong is the focus automatically selects a field when you go over it. so, you're typing into a box and nudge the mouse, all of a sudden you're typing into the next box! the other annoying this is whenever I select a field to start typing I always two characters of the key I've pressed.

Neil.

miran

This is configurable. For key repeat and delay open allegro.cfg and modify the relevant fields. For example:

keyDelay = 300
keyRepeat = 150

For focus changing when mouse moves open the skin file (skins/kde2.ini) and change focus=1 to focus=2.

Btw, this is very similar as in the built-in Allegro GUI...

Dennis

I will check your code later miran(to see if i can incorporate your changes into mine).
Unfortunately:( i was working on my new version the last few hours and thus did not see you already changed it.
(Should not be too difficult to inc your changes though as my changes do fully preserve the entire version1 codebase;D.)

(i'll just post what i have made while i was offline)
http://homepages.compuserve.de/DennisTapier/allegroforum/COLGRAD2.PNG

Showing example one of the old version plus an added ABSORBER absorbing everything(color(255,255,255)).

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

NEW Features:
-Color ABSORBER
-Effect Modifier (*experiment with this to find out how it affects the colors*)
 Where in the previous version "distance" was used to calculate the effect,
 now "effect_modifier" is used.
 It is calculated as effect_modifier = p * distance^exp.
 p and exp are set individually for each ATTRACTOR.
 (set p=1.0 and exp=1.0 to get the same behaviour as in version1)

miran

Heh, your exp in the effect modifier is my linearity :) Except I did it with a look-up table, otherwise it is too slow and I don't have the p coefficient yet.

Dennis

Does that eliminate my need to look at your code?;)

miran

Yes, probably. :)

Dennis

Good(i hope i didn't cause too much trouble).:)

miran

Not at all. In fact version 1.05 is already up :)

Btw, you can now move attractors with the mouse too. Right mouse button changes range :)

Neil Walker

How do you achieve smoother gradients? The only way I could achieve it was adding more of the same in the same place, but this has the effect of turning it towards white.

Neil.

miran

Smoother? I always get very smooth gradients. Make sure you're running the program at 32bpp. This can be set in allegro.cfg...

EDIT: And one more (small) update. Version 1.06 is now uploaded :)

Dennis
miran said:

Not at all. In fact version 1.05 is already up

Wow that was quick, maybe even a little too quick...Where did my p and exp go?:' (I wanted to play around with them, preferably in a way that they are also text input fields that take floats.(The formula "eff_mod=p*dist^exp" could be shown next to that fields to give the user a hint what they do.)
(Could you not just have used my version2? I don't think that it is that much a speed loss with it compared to lookup tables and also version1 is included so that loading of previously generated files would not be broken.)

How easy is your MASkinG to learn? Maybe i should look into it, so i could make the GUI myself. (You'd still be credited for GUI, of course.:))

Neil said:

How do you achieve smoother gradients?

I'm afraid that question can't be answered easily but it greatly helps if you understand how the RGB scheme works, because then it is possible to actually plan the result and place colors in a way that they will mix as you expect them to.

[edit]
version 1.06
That's cool miran you're spitting new versions like a highly active volcano;)...hope it does what i just posted...checking it.

miran
Quote:

Where did my p and exp go?

As I said, exp is in fact linearity. And p, I didn't think it was very useful. Or maybe I'm missing something? I'll do some more experiments :)

Quote:

Could you not just have used my version2? I don't think that it is that much a speed loss with it compared to lookup tables and also version1 is included so that loading of previously generated files would not be broken.

Well, calling the pow() function in a tight loop is always going to be very slow.

Quote:

How easy is your MASkinG to learn?

Hmm, it comes with full documentation, about 20 examples and a short tutorial. Whether it's easy or not depends on what you're used to, but I'd say it's not too difficult. Maybe it just requires a bit of time to get started, but then it's very easy...

Dennis
miran said:

And p, I didn't think it was very useful.

I thought having a coefficient could be a nice thing to experiment with and i still want it.

miran said:

Well, calling the pow() function in a tight loop is always going to be very slow.

This might be true, but in fact i did not notice any hit in performance in my example.
I would still greatly prefer it if my version2 would be used, because it was done in a way that version1 was not touched.

What i wanted to achieve with this:

  • previously created files can be loaded and generated using the old functions and structs, thus not rendering older files useless

  • saving would always be done in version2

  • if a version1 file was loaded it could easily be resaved(without affecting the result) by setting the version2 modes of the attractors to CA_ATTRACT and putting 1.0 to p and exp(these values could even be changed on the fly during loading)

  • other light changes for future versions that only have new CA_MODEs would be "file compatible" to version2 and only the render...2 function would have to be changed

  • i had in mind that major changes to the CA_DESCx would always be made by having a new version of each of the functions, so that all versions would be downward compatible(could this not also easily be incorporated in your classes by just writing one load method for each version? saving would always be done to the latest version format, same goes for rendering)

I will start looking into your MASkinG, though it would be very helpful if you'd still be working on the GUI, because you're probably much faster on it than i could ever be.;)

miran

There's still full downwards compatibility. The last version still loads and properly renders all files that were saved with v1.00 and all other versions after that. Besides, there's virtually no difference between your v2 code my modified v1 code, except that mine is optimized with LUT (and I did notice a MAJOR performance hit; as in your code is like 20 times slower!) and I don't have p. I'll put that in too so you can play with it, it's not difficult. But as I said, it's not very useful either, at least from what I've seen...

EDIT: There, v1.07 has p in. It's called multiplier. I'll give you an award if you can do anything useful with it though. Btw in render_col_grad_to_bitmap() you can comment out the lines where d is calculated and uncomment the lines that call your code (that does exactly the same). If you can compile that, you'll see the difference in speed. My version is slow, but yours is painful...

Dennis
miran said:

There's still full downwards compatibility.

That's good, i did not recognize it, because i wrote my post before examining your latest version.:P

miran said:

Besides, there's virtually no difference between your v2 code my modified v1 code, except that mine is optimized with LUT (and I did notice a MAJOR performance hit; as in your code is like 20 times slower!) and I don't have p.

Ok you're right about the speed then(i was just judging from one example without actually comparing any timings) but i still would like my effect_modifier in, because it allows for greater flexibility and experimenting, being able to enter just any float value for p and exp(even negative ones!). Your linearity allows only ranges from 0 to 2.0 as i see it. I want to also experiment with negative exp and p and values greater than 2.
(Also the effect modifier was done with future expansion in mind, so only that function needs to be adjusted and not every 'case'branch.)
It was not intended for realtime(as in high FPS) use and so i for my part would not care about the speed loss that much. (You could still use look up tables for values inside the range 0.0 to 2.0 and maybe just fall back to pow() for values outside of that range.)

miran said:

I'll put that in too so you can play with it, it's not difficult.

Great, i'm looking forward to the next version.:)
(Now i got to download "alfont" because i was unable to compile MASkinG.)

[edit]
What coincidence, you're always editing while i post!:D
[edit]

miran said:

It's called multiplier. I'll give you an award if you can do anything useful with it though.

I can already think of something: It can be used to quickly change the intensity value of a color, without the need to go into the color editor and sliding the intensity down(and that's not the same as changing your linearity). For my award i choose that you incorporate what i suggested above in this post;D.

miran

OK, I tested a bit now and for some reason the speed difference is hardly noticable. I swear it was much more before!

And you do have a point about that modifier function. It makes things more flexible. I think I'll do that in the next version. And I'll change those sliders into text boxes so you can type in anything you want :)

da_flo
Quote:

Maybe your suggestions would be the same as having individual intensity(distance) functions for each attractor? I'm a little puzzled.

Quote:

(Maybe that's what da_flo was talkin about. I'm not good at this advanced maths stuff.)

Your linearity modifiers are nice. :D Using custom interpolation functions like this instead of linear interpolation is nice. I haven't thought about it :) (When I wrote my post, I was really tired, since I spent the whole previous night with friends, and was really stoned when I wrote it...)

But in fact that's not quite the same as what I was talking about.
Using distances defined from norms (as in my examples... every norm defines a distance, but not all distances are defined from norms), we still have the linearity. Mathematically, if N is a norm, for lamba a real number and u a vector we have :

N(lambda*u) = |lambda|*N(u)

In fact, a good way to visualize the differences between norms is to see the shape of a circle for those norms (a circle being of course defined as the set of points at a given distance of the center, according to the norm choosen). I've attached a picture of circles with a radius of 1, for N_1, N_2 and Ninfinity. For N_p, with p>2, you get a round square, which becomes sharper as p gets bigger. (in fact one can show that lim(p->infinity) N_p(u) = N_infinity(u). It doesn't matter if you don't get this though ;)).

So, I think I should try it, to see what kind of gradients we get with those new distances, because I can't say it without trying. And custom distances and linearity modifiers can be combined together, giving even more possibility ;)

However, since I still don't know how to compute the distance from a point to a line with non-euclidian distances, it can't be added to the program right now.

I hope you get it now. :) It was only a remark, I don't know if that's really useable.

Dennis
miran said:

OK, I tested a bit now and for some reason the speed difference is hardly noticable. I swear it was much more before!

Oh well, if that is the case then you might as well completely forget about the look up tables.(will also save a lot of memory;))

You're doing a great job on the GUI, just wanted to say that again as it can't be stressed enough!:D

[edit]

da_flo said:

However, since I still don't know how to compute the distance from a point to a line with non-euclidian distances, it can't be added to the program right now.
I hope you get it now. It was only a remark, I don't know if that's really useable.

All remarks and suggestions are highly welcome. Nothing beats several brains thinking in different directions. Maybe the problem with your thinking about the distance lies in the fact that there is no such thing as a "point" or a "line" in 'non-euclidean'-space?!(just a thought...) If it's not defined you'd have to invent that space yourself and write a function that transforms from there to cartesian coordinates...(no i don't really know what i'm talking about;D)

miran

OK, changed sliders to textboxes so you can type in any value you want and I switched to Dennis' code. Version 1.08 already uploaded :)

da_flo: I almost understand what you're talking about and I vaguely remember that from some math class I had some 3 or 4 years ago. But the memory is all blured :)

EDIT: About the speed issue. I figured it out. The speed of the pow() function depends on the parameters. If the exponent is a whole number, it's very fast, but if it's a fraction, it's very slow :(

Dennis

Is that that thing with generic-"topologies" in arbitrary "vector"-algebras(<-can be anything, not necessarily analytical geometry vectors)?(my terms may be incorrect as i only know the german terms: "Allgemeine Vektorraumtheorie", "Topologien in allgemeinen Vektorräumen")

Will check Version 1.08 now...:)

da_flo
Quote:

Maybe the problem with your thinking about the distance lies in the fact that there is no such thing as a "point" or a "line" in 'non-euclidean'-space?!(just a thought...) If it's not defined you'd have to invent that space yourself and write a function that transforms from there to cartesian coordinates...(no i don't really know what i'm talking about

Be aware that I'm not really talking about non-euclidian geometry, such as hyperbolic geometry or other fancy stuff, where lines have an odd behaviour and all. Here I am still talking about basic space, with cartesian coordinates, but I'm trying to use some other kinds of distance. That's no geometry, only basic topology. The norms I've described (except N2) are called non-euclidian because they are not defined from a dot product.

Well, I'm getting a bit off-topic... Ahem. I will try to do some coding as soon as I get motivated enough.

Dennis
miran said:

About the speed issue. I figured it out. The speed of the pow() function depends on the parameters. If the exponent is a whole number, it's very fast, but if it's a fraction, it's very slow :(

Ok, fractions should only be used with great care then;) and the default values(i guess it's already that way) should always be 1.0.:)
[edit](so old versions and defaults will render at almost same speed as before and for other values(that are indeed new features) we can easily fake ms-mentality: new version==hardware requirements explode!)[/edit]

da_flo:
Then in theorie it would be easy: For every point on the line compute the distance(using whatever norm) between that point and the attractor, then choose the one that has the smallest result.(will probably be slow but should be right)

da_flo

Now that I think about it, if you look at the image I have attached (2 posts ago), you will notice that for hbar and vbar the distance is the same, whether we use the usual euclidian distance or a distance obtained from any N_p. Thus those norms can easily be implemented, and we can get gradients shaped differently that way. :)

It only becomes tricky if we use bars which are neither horizontal nor vertical.

Dennis

da_flo:
I will look into that, other bars than the ones already there will be put aside for now.

miran:
I noticed a BUG in my render function (It's also in yours because i already missed it on my very first release.).
The variables fr,fg,fb should be floats(that's why i put the f)! And on the calculations they should NOT be converted to (int). That conversion should only be done afterwards, where thos r=fr, g=fr... lines are placed. This should make things a little smoother.

Richard Phipps

There is too much math in this thread. My head hurts! :P

da_flo

Dennis, forget what I just said. I was still in the maths stuff, so I was assuming lines were infinite lines. :-X

With bars, which have 2 extremities, this becomes a bit more complicated. It might actually be quite simple, but I need to take a piece of paper and work on it.

[EDIT]
Sorry Richard. I am the one to be blamed for the maths hell. But I can't help it. I'm doing maths studies, and will probably become a maths teacher or do research... ;)

Dennis

These lines actually don't have two extremities... they are just either an x(vertical bar) or an y(horizontal bar) offset, so can they not already be treated as infinite ones?

da_flo

Oh okay Dennis. Then it works, no problem. :)

I'll dig into the maths issues anyway, for fun and to see if this can be used with fancier attractors/absorbers.

Dennis

Would be cool to have polynomial attractors/absorbers with an arbitray unit(given in pixels):-X or circular ones where range will be seen as range from every point on the circle:-X

However, i'll be experimenting with miran's v1.08 now... see y'all tomorrow.:)

miran

I've been experimenting with different distance functions. Attached is a picture of the default point with Norm p: Np(x,y) = (|x|^p + |y|^p)^(1/p) with p=0.3. Looks nice but is awefully slow without lookup tables :-/

Norm infinity looks similar but a bit more square. Norm 1 isn't much different either, except that it's rotated by 45 degrees, so it makes diamonds instead of squares...

Dennis

[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

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

Dennis
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

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

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

Dennis

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

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

Dennis

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

Martin Cerny

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.

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

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.

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

Dennis
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

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.

Dennis
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

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.

Dennis
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

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.

Dennis
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

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.

Dennis

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

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)

Trezker

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

Dennis

Martin: I wanted to edit my post, but now that you already answered, i'll just post what i wanted to add to my previous one;))
(i'll look at your picture and read yours afterwards)

Time to clean up the mess, i created:
From your point of view(which i can see now) there are several things i said that are wrong for that point of view.
More specifically:
-"for each pixel along the width there's exactly one function value" (true, but there can be more than one pixel required to correctly render a closed curve(which this programm does not do)
-"it has got nothing to do with the way it is implemented in my code" (wrong, it HAS got sth. to do with the way it is implemented)
-Confusional: I mixed up x function values with x-pixel position sometimes.
-Confusional: You were also mixing these up by mixing points with pixels, which i later adopted in my first sketch, leading to even more confusion.
That lead to: When you were talking about points on curve, you really meant all pixel positions that would render to be set on the curve, while i was mixing it up with just every [x,y] function value point pair, ignoring any "vertically next to each other"-pixels, not seeing that those pixels are the important detail here.
-"num_points_on_curve==width, always", (wrong, true if function values was used instead of points)

Now i understand that my (width*height)*width distance calculations would still be wrong, because all your green pixels would be ignored in it(regardless if the were to be rendered or not).
So my algorithm is a little inaccurate(but i think it'll only be visible, if using a unit of very few pixels(<5 or so) but still right in its' general idea,
while your algorithm could be accurate but might be wrong in its' general idea, because the premise could be wrong as i pointed out above and also you did not answer my other question.

Please verify the following:
To make my algorithm 100% accurate all i'd need to do is calculate straight lines from every [x,y]pixel i already have to the following [x+1,y] pixel and then store all points along that line as additional "pixels"_on_curve.
In distance calculations also check the distances to these additional points.(That will be very slow indeed and as said above probably not affect the result much on units>5 pixels or so.)

Those assumptions about how the units would (positively) affect inaccuracy are just rough guesses for a simple x*x. Of course it depends a lot on the f'(x)(the higher that, the less the accuracy of the unoptimized algorithm) values in every point.

to make sure the fun aspect of the whole thing is not forgotten :)
Heres two -x^3 laid onto each other(first attracts, second absorbs) embedded in a simpler non polynomial gradient:
http://homepages.compuserve.de/DennisTapier/allegroforum/fungrad.png

init_ca_list3(&test3);
add_to_ca_list3(&test3,CA_POINT,CA_ATTRACT,1.0,1.0,0,0, 200,200,0, 500,NULL);
add_to_ca_list3(&test3,CA_POINT,CA_ATTRACT,1.0,1.0,639,479,0,200,0,500,NULL);
add_to_ca_list3(&test3,CA_POINT,CA_ATTRACT,1.0,1.0,320,240,0,0,200,500,NULL);
add_to_ca_list3(&test3,CA_GLOBAL,CA_ATTRACT,1.0,1.0,40,0,255,255,255,0,NULL); 
add_to_ca_list3(&test3,CA_POLYNOMIAL,CA_ATTRACT,1.0,1.0,0,0,255,200,0,200,
                make_polynomial(3,320,320,240,-1.0,0,0,0));
add_to_ca_list3(&test3,CA_POLYNOMIAL,CA_ABSORB,1.0,1.0,0,0,0,255,128,100,
                make_polynomial(3,320,320,240,-1.0,0,0,0)); 
render_col_grad_to_bitmap3(backb,&test3); /* backb must be a valid 32bpp bitmap 640x480 in dimensions */
save_tga("./fun.tga",backb,NULL);
kill_ca_list3(&test3);

[EDIT]

Martin said:

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

That is clear but there is a flaw in that argument. Your point "a" is very close to the peak P, while my point "a" is far away, you would have to put your point way off above your image, if you were to assume for it the same position as my point "a".(You can't just zoom in on the peak and move "a". You have to have "a" stay where it was and thus it won't be visible on the area you zoomed in.) Also i'm sure that your point "a" would NOT lay inside my area "A". It would more likely be to the right of it, so the closest point to that would indeed not be at the peak but i did never say so. It only applies for points in Area "A".

[[EDIT 2]
Trezker, that looks nice.:)

Martin Cerny
DB said:

That is clear but there is a flaw in that argument.

Not true - the image is not important, however it's scaled or points moved, the premise for the argument is that tangent is not at right angle to the distance. I though about it a bit and I think I could make serious mathematical proof of the fact that if the tangent is not at right angle to the distance, then there is a point on the curve, which is closer. Hence the only situation when there is no point closer is when the tangent is at right angle to distance.

da_flo
Quote:

I though about it a bit and I think I could make serious mathematical proof of the fact that if the tangent is not at right angle to the distance, then there is a point on the curve, which is closer. Hence the only situation when there is no point closer is when the tangent is at right angle to distance.

Proving that The closest distance of a point to a curve is always at right angle to the tangent at the closest point of the curve is quite easy. I made it in a few minutes this morning, just let me some time to write it in english and upload it. ;)

Dennis
Martin said:

Not true - the image is not important, however it's scaled or points moved, the premise for the argument is that tangent is not at right angle to the distance. I though about it a bit and I think I could make serious mathematical proof of the fact that if the tangent is not at right angle to the distance, then there is a point on the curve, which is closer.

No need to prove it. I reconsidered my drawing to be totally wrong. I can see that myself now. Your argument with the circle around "a" that will intersect with the curve another time has opened my eyes now.
You're right.:)

[edit]
Still i have no idea which algorithm will be better.:(

[edit2]
Still your point is not lying in my area A but that's not your fault. It's mine, 'cause if properly calculated one would find that my area A is indeed empty;D. And the way i wildly constructed that supposed area A in my picture is complete and utter nonsense, as for every point in that area i can find another point on the curve that is closer even if i don't calculate it and just use your described method with the circle. My Math-FU is weak. You win.:)

Martin Cerny
Quote:

Still i have no idea which algorithm will be better.

The simplest way would be to try. When you finish the object version, I can easily extend your object for polynomial attractor and override it's distance method and constuctor and then we will be able to do some FPS checks.

EDIT: Ain't it funny we spent a very big part of this thread arguing about such an unimportant minor thing? And nearly noone interrupted us.;D

Dennis

I edited while you posted.

I don't know when the object version will be done, i wanted to start today but i spend the entire day arguing with you.;)

Martin said:

Ain't it funny we spent a very big part of this thread arguing about such an unimportant minor thing? And nearly noone interrupted us.;D

Funny yes, unimportant no. You did a good job defending your algorithm and proved me wrong several times, which is good, because otherwise i would have never even bothered to think of your method as a considerable alternative.:)

da_flo
Quote:

No need to prove it.

Well, I went through all the hassle writing it and scanning it while you answered, so I'm posting it anyway. :P

Sorry for the hand-written proof, that was the easier way for me do to that. I hope it's clear and readable enough. I'm not used to writing maths in english. ;D

Well, you probably don't care, but here it is. By the way, I followed the thread by didn't read all the explanations, so if you want a third point of view, tell me and I'll try to go deep into it. ;)

Dennis

da_flo:
I'd still like a third party opinion but not on the general math, as Martin already showed me that i was wrong with my last drawing(and with some other arguments) but it would be great if you could dig into it and answer the questions regarding the algorithms that are still left unanswered.:)

Martin Cerny

da_flo: you seem to better in math than I am, so I'll try to explain my ideas with calulating the distance directly - maybe you could find a way out:

notation: f'(x) is a derivative of function f(x) //hope derivative is the right term
[a,b] is point with x-coordinate a and y-coordinate b
if A is a point, than A1 is it's x coordinate and A2 it's y coordinate

I tried two ways to calculate the distance - first I tried to qualify the function of distance from point A to a point on the curve according to it's x coordinate d(x) and then find a minimum through derivation. That leads quickly to problems, because for polynomial of n-th degree d(x) is of 2n-th degree and so it's derivation (which you have to solve) is of (2n-1)-th degree.
The other way was similar to my algorithm - assuming that the distance lies on a normal to tangent you find all those points on the curve and then calculate their distances and compare them.
We evaluate the vector of a tangent in a point
v = (1,f'(x))
and the 'distance' vector u = [x,f(x)] - A = (x - A1, f(x) - A2)
and then compare the dot product (hope that's the right term) u.v to zero.
u.v = x - A1 + f'(x)*f(x) - A2*(f'x)
but since f'(x)*f(x) is of (2n-1)th degree we are in the same trouble :(
I tried one other method but it led to exactly the same equation -
for f(x)= a*x^2 + b*x +c the result was:
2*a^2*x^3 + 3*a*b*x^2 + (2*a*c - 2*a*A2 + 1)*x + b*c - A1 - b*A2
which I wasn't able to solve without using the formula for 3rd degree equations which is a bit difficult to count in hand.

Other idea was to start with x=A1 and calculate the derivation f'(x) and move 'left' (substract a little number from x) if (f'(x) > 0) && (f(x) > A1) or (f'(x) < 0) && (f(x) < A1) and move 'right' otherwise. And continue doing this until the distance |A,[x,f(x)]| will stop getting lower. Thus you could get quite good result within good time.

Hope everything was clear enough. I can't figure out anything better now.

Richard Phipps

Just checked the program out, looks great! This could come in very useful for some menu backgrounds. :D

Dennis

Thanks:), that's one of the things i also had in mind for the generator. I hope you did not miss that the latest version3 has a small inconsistency in it for the polynomials.
Inside "make_plut" you must replace the calculation with this one to have it compute faster and also to have y growing downwards:

/* 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];

[edit]
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]

da_flo

Okay, I tried to look at it, Martin.

I didn't spend much time, and didn't find any efficient way to do it.
In fact, solving the polynomial equation of degree (2n-1) seems almost the best solution. For each point, you then have to solve an equation, but with some methods it can be done with very few iterations, depending on the accuray wanted. For example, the Newton-Raphson method is quite simple and gives very good and quick results in most cases. But in some particuliar cases (for example because of the function's minima), it can have a chaotic behaviour. See the newton fractals shown at the bottom of the wikipedia page. I didn't read the article, but they should explain the practical problems of the method.

So I really don't know how to do. I'm not really used to numerical computing. I'm learning rather theorical maths, not engineering maths. ;) (and besides I still have a lot to learn... ::))

Dennis' suggestion of computing the distance to SCREEN_W points of the curve and taking the minimum is quite heavy, and is still an approximation (and using as many points as the screen width is quite arbitrary anyway. It's only quite accurate because SCREEN_W is big enough). Besides, if we want to be rigorous, we have to consider a part of the polynomial which is outside the screen, otherwise we could have some strange effects near the screen borders for some polynomials.

As a conclusion, there seems to be no fast way to do it. If we want to keep the graphical fun (as Dennis said), we should forget the mathematical aspect a bit.

I'll try to play with Dennis' code and add some accurate distance computation, regardless of speed. I'll post screenshots of the 2 versions, to see if the difference is really worth it. ;)

-----------------------------------------------------------------------------------------------

I was also thinking of a new kind of attractors/absorbers : You could use circles. :)

There the distance will be easy to compute. Let's assume you have a circle of radius R.

If d is the distance from the point to the center of the circle, then the distance to the circle is abs(d-R). :)

I'll try to test it if I can, but if you feel like adding it yourself, Dennis, don't hesitate.

miran
Quote:

You could use circles.

Good idea. That will make nice rings :)

Dennis
da_flo said:

I'll try to test it if I can, but if you feel like adding it yourself, Dennis, don't hesitate.

I will not add any features/attractors until i have ported the entire old version3 to CPP using proper class hierarchy, as this will make adding new attractor types easier in the future. Circles are a good idea.(i already mentioned it on page2 of this thread;))

Now i got to read the rest of all post offline, because my online bill is exploding(already 67€ only for this month...yeah dial up sucks:-/).

da_flo
Quote:

(i already mentioned it on page2 of this thread;))

Oooops. ;D

Also, we might have to types of circles : circles (like the ones I've describes), giving rings, and "plain circles" where the distance is d-R if d > R, and 0 otherwise. That could give nice gradients, like sun effects or other things...

Off-topic :

That's my 666th post. I'm doomed. :o

;D

Dennis
da_flo said:

and "plain circles" where the distance is d-R if d > R, and 0 otherwise.

That's also a nice idea. In the current version sun effects can be achieved by having two or more point attractors at the same position with different ranges and selecting clever color combinations so they get mixed like you want them to in the center.;)

This was my 685th post, i did not pay attention to my 666th, but i don't feel doomed, however i'll probably stay away from allegro.cc for a day or two now, so that i'll hopefully find the time to do the CPP port.:)

da_flo

I started looking at the gradient generator more closely. Well, in fact I never played much with the GUI, and didn't really get the working of the algo. (I know, shame on me :-[)

I saw the role the distance to the ca played, but didn't see the ca had a range. That leads to really neat results, but I don't know why but I was rather expecting rather some kind of infinite range, with color interpolation towards infinity, with an interpolation fonction like f(d) = (d/(d+1))^n, which interpolates from 0 for d=0 to 1 for d=infinity.

Well, perhaps is it I that has a twisted mind. ;D That's just the way I would have created a gradient generator.

Then I tried the linearity and multiplier parameters. Since the modifiers are applied to the distance before checking for the range, it's messing a with the range. The linearity factor doesn't cause many problems, but the multiplier is more worrying.
If multiplier>1, then it artificially shrinks the range of the ca. If multiplier<1, then beyond the range everything is of the same color as on the range (I hope I'm clear here :-/). It acts as if one added a global attractor with that color.
I don't know if these are bugs are rather "features" ;), but it just seems wrong to me. I wouldn't expect it to behave like that, since the range is now irrelevant, and with multiplier<1 it even screws up the hole bitmap. :-/

I think you should apply the modifiers to d/next->range rather than d, after the range check, and drop the multiplier (keep only the linearity parameter).
d/next->range < 1, so applying the linearity parameter will give a number between 0 and 1, usable for the interpolation.
(I think this change is useful, because even the linearity messes with the range to some extent in the current version)

I hope I was clear enough. So was this behaviour intended or not ? I'm not asking you to change it, it's just a (useful, IMO) suggestion. ;)

Dennis

[edit] added more fixes from two posts below, redownload attachment[/edit]

It is both feature and bug.:)
It is a "bug" as in "it leads to visually odd and useless behaviour".:(
It is a "feature" as in "it does exactly what is described in the header file" and i used it to create some bars with sharp edges to justify it for myself.;)
(But i found that sharp bordered bars could be easily created by cutting a portion out from a smooth one so...)

A "visually" fixed version3 with much more useful behaviour is attached.;D
http://homepages.compuserve.de/DennisTapier/allegroforum/COLGRAD3F.PNG
(As you can see, p(==multiplier in Miran's version) is not useless, as it does something different than exp.)

Snippet from the new readme:
[edit]

Version 3fix2 (Aug. 10th 2005) (version 1 and 2 stripped(==declared obsolete))
   Whereas in the unfixed version p and exp did exactly what was described,
   their behaviour lead to "visually odd" results.
   In this fixed version p is used to modify the intensity of the color.
   And exp is used to modify the "falloff" behaviour of the intensity in
   respect to the distance from the attractor.
   (Check the three examples in "main" to see the difference.)
   Changes in detail:
   -The old "effect_modify" was deleted
   -And "render_col_grad_to_bitmap3" was changed
   *-*-*
   -in PN_DESC the coefficient type was changed to double grrrr to the ellipse(...)
   -make sure you place a "." before the variables pass as coefficients to "make_polynomial",
    even if you want to pass just 0 or else you'll get wrong behaviour, because of stupid
    type promotion in the ellipse grrr (bet your donkey that the next version
    will not use the ellipse but rather a pointer to a dynamic length array!)
   *-*-*
   (Still the original behaviour of version1 can be achieved by setting p=1.0,exp=1.0)

   Version 3: (Aug. 6th 2005) (introducing polynomial attractors CA_POLYNOMIAL)
   Check newly defined PN_DESC starting at line 156 and the accompanied support

da_flo

Okay. I played with your code yesterday night and did some things for fun.

First, I must say that I had some trouble to get your code to work.
First, I'm working with gcc, so in make_polynomial, in work->co<i>=va_arg(marker,float);, the float args get promoted to double, which caused a segmentation fault. I change the co array to double, and it worked.
Then, I spent a lot of time getting the polynomials to actually work. This was a nasty and stupid bug, and as it was late and the values used confused me even more during debbuging, it took me a lot of time. Here it is :

for(i=(int)he+1; i>=0; i--)
       work->co<i>=va_arg(marker,double);

It has to be he, not he+1, otherwise it cannot work ! >:( It should even sigsev with he+1, but it didn't ! (that would have helped me >:(). No offense intended, but I really hated you when I finally figured it out. ;)

I wanted to make some comments on your code too. At first, the polynomial code seemed quited messy, and I was confused because you use ints everywhere, for the coordinates as well as for the lookup table, and your unit. Of course I understand it's for a matter of efficiency, and that you won't loose much accuracy that way. But hey I often make some kinds of image generating programs, and I'm often not concerned by speed, and use floats everywhere... ;) For example, I would rather have used floats and used a 'scale' parameter to convert everything to screen coordinates when drawing. Well, I'm not trying to criticize your work, I'm only describing the way I usually work. ;)

Then, I implemented an algorithm to actually compute the distance to the polynomial curve. I used your first idea in a slightly optimized and more rigorous way.
For each point on screen, I must get the minimal distance to the polynomial. Then there's often no need to check all the points on screen. If you already have the distance d to one of the points of the curve, for example

d=abs(P(x)-y)

, then the distance is less than d, and we only have to check the points in a circle of radius d. Then I check the points of the curve from x-d to x+d, and take the minimum.

This method has some drawbacks. First, we have to check some points which are outside the screen. To do that, I create an extended plut table, with a plut_offset parameter giving the number of points outside the screen on the left and on the right. The real problem is that, for example for P(x) = -x^2, the curves decreases very quickly, therefor for some points,

d=abs(P(x)-y)

is very big, which leads to a huge lookup table and a huge number of calculations.

But there's a way to speed it up, now that you have fixed the range/modifier problem. In fact, if the distance is greater than the range, it's useless. Thus if the first d is greater than range, we can check the points from x-range to x+range only.
That's a bit hackish, and could lead to bugs if the range system was changed in the rendering, but it will really speed it up. That way for each point we have less than range*2 calculations, compared to the fixed SCREEN_W number of calculations in your initial method.

So, I rendered your example using my own distance calculation, and attached the result, just so that we can compare the two methods, for fun. I'm not saying that we should use that algorithm. It depends on your priorities, whether you're concerned with speed, like if you want your algorithm to be used almost in real time in games (and in that case after all, people are free not to use polynomials if they want full speed ::)), or if you want to do prerendered gradients where the speed doesn't matter as long as you have the picture (That's usually my way of thinking. I'm a computer barbarian and I love it ;D).
I made it only for fun. The choices are all up to you.

If you're interested (even just for fun), I can post my code later, with a new version using the range to optimize it a bit.
I might improve it a bit too. Because using integer coordinates from 0 to SCREEN_W-1 for x is only arbitrary and related to the pixels and to your integer parameters. So I could make my lookup table with a custom precision, since it's no longer used to get P(x) for x on the screen. Then we could tune the precision, whether we want speed or accuracy. :)

Dennis
da_flo said:

It has to be he, not he+1, otherwise it cannot work ! >:( It should even sigsev with he+1, but it didn't ! (that would have helped me >:(). No offense intended, but I really hated you when I finally figured it out.;)

Uhhh of course slaps hand at his head. My stupid mistake.:o
I wonder why MSVC did not crash and i wonder even more why it still rendered the correct polynomials, because after properly changing it to "he", also the function value computation with horner scheme(also the naive method) had to be adjusted.[edit2](*wrong*, see below)[/edit2]:-/

You can't blame me for the float to double thing though, that's your stupid compilers fault. If it promotes one float to double it should promote all float through the entire programme, imho.>:(
However, i'll keep that in mind for the CPP version and will use doubles all the way.

Here's a hotifx-replacement for "make_plut" and "make_polynomial"(left float as float but will be changed in the CPP port):

[EDIT]FORGET about the hotfix, it made things even worse as polynomials totally ignored all "co"s except the first one...GIMME A BREAK!:P [/EDIT]
[EDIT2]
Ok, this time it is really fixed, please redownload my previous attachment. I found out that also in MSVC the float gets promoted to double(I really hated MS when i found about that.>:() and so i changed the coefficient type to double. The function value calculation did in fact not need a change. The odd behaviour, i experienced in the edit above, resulted from the fact that if a simple number like 0,1,5 or so without a "." in it was passed to the ellipse, it also got promoted but NOT TO DOUBLE grrr, resulting in very wrong behaviour of the polynomials. But now it works correct if you pay attention to what i mention in the readme.:) THE CPP VERSION WILL DEFINITELY USE A POINTER TO A VARIABLE LENGTH ARRAY AND NOT THAT !#*$5'ED UP ELLIPSE(...):)
[/EDIT2]

But that REALLY was the last fix to the old version.;)
About the rest of your post i can't say anything now, i just quickly overflew it, but i understand the improvements. However i must recommend that you give me a break from the old version now, or else i'll never finish the port.;)(I already started this morning but then i made the other range p,exp fix first because it bugged me so much.)

da_flo

Okay, first, comments on your message :

Quote:

You can't blame me for the float to double thing though, that's your stupid compilers fault

Go say that to all the people using various flavours of gcc. ;)
And I was not blaming you. I was just trying to get it to work on my compiler and to point out compatibility and portability issues, since you probably want as many people as possible to use your algorithm.

Quote:

[EDIT]FORGET about the hotfix, it made things even worse as polynomials totally ignored all "co"s except the first one...GIMME A BREAK!:P [/EDIT]
[EDIT2]
Ok, this time it is really fixed, please redownload my previous attachment.

I don't know what your fix is, since I didn't read your new code. But my fixed version seems to work. ??? You can take a look at the one I'll attach "later" in this post if you want.

Quote:

THE CPP VERSION WILL DEFINITELY USE A POINTER TO A VARIABLE LENGTH ARRAY AND NOT THAT !#*$5'ED UP ELLIPSE(...)

I nearly always code in C++ but almost never used the STL (shame on me...), but most C++ guys would tell you to use STL vectors to do that. ;)

Quote:

However i must recommend that you give me a break from the old version now, or else i'll never finish the port.;)

Sorry if I prevent you from working on the C++ version. :-/ That was not my goal.
Well, the bugs I pointed out were asking for a fix, I must admit. ;D
But for the distance to a polynomial, I'm not requestiong you to add it to the current version. Concentrate on your port, I did it because I thought it was fun, and so that you and other people can play with it to see the differences with your previous algorithm.

Here I come to the distance to the polynomial curve. ;D (wow. That was seamless... ;D)

So I rewrote my code, now using the ca range to make it easier and faster. And the code really is simple now ! :o
I must have been really tired yesterday night. Past 4am, my code-fu is somehow weaker ;D. I did stupid things that were useless and slowed everything down. Go figure. ::)

So, to do it, I needed to make the polynomial aware of the range of the ca. Because of your structures, I had to had a 'range' member to 'PN_DESC' and make an ugly hack :

/* In wcolgradgen.cpp */
void set_pn_range(ppolynomial PN,int range)
{
  if(PN)
  {
    PN->range=range;
    PN->changed=1;
  }
}

/* in void render_col_grad_to_bitmap3(BITMAP *bmp, col_att_list3* pcal) */
if(next->PN)
      {
        if( (next->PN->w) != bmp->w) /* if target bitmap has different width than lookup table... */
          set_pn_w(next->PN,bmp->w); /* makes sure that the lookup table will
                                        be calculated for evey x-pixel position */
        if( (next->PN->range) != next->range )
          set_pn_range(next->PN, next->range);
      }

Then I modified the make_plut function :

1/* create new table : size w + 2*range.*/
2 /* 'range' is the offset of x=0 in the table */
3 /* There are 'range' values on the left of the screen, and 'range' on the right */
4 PN->plut=NULL;
5 PN->plut=(int *)malloc((PN->w+2*PN->range) * sizeof(int));
6 if(!PN->plut) return -1; /* error not enough memory */
7 
8 /* calculate the values for the width of the bitmap, and the part on the left and on the right needed*/
9 for(i=-PN->range; i<PN->w+PN->range; i++)
10 {
11 cx = (-(PN->x - i)) / (float)PN->unit;
12 
13 /* using "Horner Scheme" to compute function value */
14 cy=PN->co[PN->he]*cx;
15 for(j=(int)PN->he-1; j>0; j--)
16 cy = (PN->co[j] + cy)*cx;
17 cy = cy + PN->co[0];
18 
19 PN->plut[i + PN->range]=PN->y+(int)(cy*PN->unit); /* finally add the value to the table */
20 }

And finally of course I modified distance_to_ca3 : :)

1if (ca->t==CA_POLYNOMIAL)
2 {
3 /* uses lookup table for calculation if available else returns 0
4 to fall back to weird but at least uncrashing behaviour */
5 if(ca->PN)
6 if(ca->PN->plut)
7 {
8 /* calculates the distances to all the points on the curve in the given range */
9 /* and takes the minumum */
10 int i, r;
11 double dmin, d, dx, dy;
12 dmin = abs((ca->PN->plut[x + ca->PN->range])-y);
13 if (ca->PN->range < dmin) r = ca->PN->range;
14 else r = (int)(dmin);
15 for (i = -r; i<= r; ++i)
16 {
17 dx = i;
18 dy = ca->PN->plut[x+i + ca->PN->range] - y;
19 d = sqrt(dx*dx + dy*dy);
20 if (d<dmin) dmin = d;
21 }
22 return dmin;
23 }
24 else return 0;
25 }

My whole modified and fixed code is attached to the post.
I made it render your example with polynomials, and it gives the same picture than the one attached in my previous post (which was made with the stupid yet accurate version I made before ::)).

Feel free to play with it, so that we can see if it's worth adding it to the new version. Personnaly I like it, but I don't know about the speed concerns. :-/

And I almost forgot : I didn't add the 'custom lookup table precision' thing, because it would have been quite messy, with ugly coordinates conversion, and because I just didn't feel like it. Later perhaps. :P

Dennis
da_flo said:

Sorry if I prevent you from working on the C++ version. That was not my goal.
Well, the bugs I pointed out were asking for a fix, I must admit.

Oh, no need for excuses. Bugs are there to get fixed, and especially the weird behaviour of p and exp had already bugged(!) me for some longer time(and judging from Miran's earlier comments about it, i think he was not too happy with that behaviour either).
And the typo(resulting from laze copy/pasting) with he+1 would probably have gone unnoticed if you had not found it.:) I think it is better these bugs are fixed already in the old version than if they were ported to the new one.

da_flo said:

Feel free to play with it, so that we can see if it's worth adding it to the new version. Personnaly I like it, but I don't know about the speed concerns.:-/

We can test it, as soon as the new version is done. There you'll not need to hack, because the polynomial derived class will of course have access to the range attribute. All you'd need to do is inherit it and override the distance method and probably the lookuptablecreation method. ...maybe i'll even test your function later this evening, but i really need a pause from the stuff now...;)
(The picture rendered with your version looks nice.)

[edit]

da_flo said:

Go say that to all the people using various flavours of gcc.

Yes, i already said in my edit that it is also the same way with MSVC, so MSVC is also a stupid compiler and as i also said a better(as in "less error prone" solution will be used in the port.

da_flo said:

I don't know what your fix is.

Multiple things. First the p and exp behaviour, second the he+1 bug and last but not least speed improvements by saving a few unnecessary calculations in the render function.:)

da_flo

Hey, I was playing with the polynomials "fun" example at the top of the 4th page, using my distance calculation and changing parameters, and I noticed some strange behaviour of the polynomial attractors, even using my supposed-to-be-accurate method.

Then I tried it with very simple examples, with only one polynomial attractor and a global attractor for the background. And what I found was really disturbing. Look at the picture I attached. When the range is big enough, you can see darker lines where the radius of curvature of the polynomial curve has a minimum value.
There are 3 pictures in the file. The top picture is made with P(x) = x^3 - x (a friend of mine to whom I showed that picture and who knew nothing about this gradient generator told me "What's that ? A small intestine viewed with X-rays ?" ;D), the middle one is P(x) = -x^2, the bottom picture is the middle one viewed from further back. (Note : the polynomials are actually -x^3+x and x^2, but to hell with those silly screen coordinates. ;))

When I saw that, I was really disturbed, and couldn't say if it was a bug in my code (which would have surprised me, since it seemed to work well with the first examples, and I couldn't see how such a "bug" could occur :P), or mathematical properties, or an optical illusion... or several of these things at the same time ! ;D

Now I'm quite sure it's not a bug, and I can somehow feel what the mathematical reasons are, but thats still bugging me, because it just doesn't feel natural. And also, the contrast might have been accentuated, by some kind of optical illusion, and my laptop screen shifts the colors and the constrast of the gradients, especially when I look my screen from further back.

What do you guys think of it ? Can you see what I mean ? Does it disturb you ? Does it feel natural ? Do you think that maths and polynomials are great ? ;D

Richard Phipps

You know if the random element was combined with some kind of 'genetic breeding' it could be even easier to get good results, by selecting your favourite pictures to combine and mutate from a pool. :)

Dennis
da_flo said:

What do you guys think of it ? Can you see what I mean ? Does it disturb you ? Does it feel natural ?

If you observe your pictures closely(don't know why i immediately spotted it), you will find that those "dark lines" are appearing along curves of other pixels that are not on the polynomial but for which there are always at least TWO points on the polynomial with EQUAL distance to the points on the "dark line".
(I hope you see it. It's easier to see at the x^2 but its also the same with the curved "dark lines" on the -x^3-x.)
Don't know what is causing it though, but i suppose your algorithm could be reporting a wrong distance(too far, hence the darker color) for those points.
It could also be caused by the inaccuracy, Remember: we're still completely neglecting those "vertically next to each other" pixels on the curve in distance computations.

Disturbing?
NO. Actually it looks pretty cool nonetheless, like bending flexible and soft rubber bars.
(Whatever you do, keep a version of that distance algorithm to preserve that effect.)
(I'll also keep my version where only the distance to the function value at the x position is used, because i like the effect resulting from that a lot.)
Note too self: Must..stay..away..from..allegro.cc..to..get..port..done..argh

da_flo
Quote:

If you observe your pictures closely(don't know why i immediately spotted it), you will find that those "dark lines" are appearing along curves of other pixels that are not on the polynomial but for which there are always at least TWO points on the polynomial with EQUAL distance to the points on the "dark line".

Yes. I immediatly noticed that. :)

Quote:

Don't know what is causing it though, but i suppose your algorithm could be reporting a wrong distance

I thought it was that at first, but I can't see where my algo would fail. It's behaving as expected in the other cases. Well, I know that's no proof ;D, but I just think it works correctly. (I can't really explain)

Quote:

It could also be caused by the inaccuracy

I somehow doubt it. I thought of it too, but I have difficulty to see why. And I'm quite sure there is a mathematical reason to this, which is perhaps visually accentuated by the algorithm and the inaccuracy of the lookup table.

Anyway, I have thought of an algorithm which will get rid of the inaccuracy of my current method when the slope of the polynomial is too high, but I'll have to drop the lookup tables. It will be reliable in all cases, and will have a custom precision. I'll code it and try it if I find enough time (damn... Speedhack is beginning tomorrow :()

In fact, the inaccuracy problem appears above all when the range is small and the slope of the curve is big. Here are some pictures which show it quite nicely :
poly1int.png
poly2int.png
By the way, in a new version (I keep a backup before every major change) I changed the lookup table to floats, just to see. Of course we still have the same problem, but it smoothes things up :). See:
poly1float.png
poly2float.png

Also, I tried to play with funky polynomials, which have lots of extrema (so necessarily of higher degree), so with several areas where 2 points have the smallest distance, and sometimes even 3. I thought it will be fun. And it was. See :
funkypoly1.png
funkypoly2.png
funkypoly3.png
funkypoly4.png

In the fourth picture, I played with the exp modifier so that we can see things better (I was still using the old modifier code, by the way). It caused some nice bug because of the lookup table and the accuracy of the distance calculation method, as you can see... ;D

________________________________________________________________________

I also had some nice ideas about your C++ port, Dennis. Well, don't worry, normally this won't disturb your current development ;) (otherwise I'll begin to feel guilty ;)).

First, your whole code isn't really specifically related to allegro. You only use a putpixel and a bitmap in the rendering function. So I think it would be nice to keep the core module (the one which handle the ca list, and has the rendering method) independent of allegro or any graphics API. You could have a 'virtual void plot(int x, int y, int r, int g, int b)' virtual method which will be called from by rendering method. Then all we have to do is to derive a new graphics API specific class from the core class, which will have the bitmap or the device context as a member and implement the plot method. That way the gradient generator can easily be used with allegro, wxwidgets, or any other graphics/GUI API. :)
[EDIT]
According to that post, have a virtual plot function which will be called a lot of time will probably add much overhead and be slow. :( Well, there might be another way to achieve this, but won't be as elegant.
[/EDIT]

Then, for the polynomial thing, I think you should have a generic functional curve ca class, which will handle the distance calculation and the stuff, and have a virtual method to compute the coordinates of the points on the curve. That way we can easily have derived class for polynomials or any other kind of functions. We could have cool sine waves, or anything the user/programmer will think of. :) (easy to use since all the user has to do is derive a new class and implement the value calculation. It's just a few lines).

Also, since you want to keep different kinds of distance calculations for those functionnal curves, you'll probably want the distance calculation to be virtual, so that we can have different derived classes depending on the algorithm wanted, no ? :)

The more I think about your C++ port, the more I think it's going to be great. It will be really nice to use, it will be a true new API that programmers will be able to use. :) I don't know how you're going to handle it though. Do you think you'll make it a lib, or only header files and source modules the user will have to add to their project ? Well, perhaps a lib is a bit too much for it... I don't know.

:). I'm really enjoying playing with your code (the old C version ;)), and I'm really getting interested in this project. If you need help, I'd be really happy to contribute. If you want me to code some modules, such as the functionnal curves and other fancy maths object, I'd be glad to help you. :)

Richard Phipps

too..many..smilies..

:P

da_flo

Ooops. I didn't notice. I just put them when I felt like it (eh, I was perhaps feeling really happy in this post. :P). And I forgot I put that much... :o

Sorry. ;D

Dennis

Don't worry the C++ port, will be excellent.
Targetsystem stays Allegro, so the thing will be crossplatform.
The first release will include a GUI(using Allegro's GUI functions).
It will support different languages and the user will be able to make own translations by adding a language specific textfile.

There is really no need in giving me hints on how to do the class hierarchy(I even felt a little insulted when you pointed on those obvious things with virtual functions. Again don't worry about that. Each attractor class will have just one single function(and that is NOT the distance function;)) that is called by the render method of the gradient class and it will of course be virtual and by that every derived attractor will be free to add thousands of other functions to its' private scope and then act on the given pixel as weird or cool as it wants.)

Other features that i have planned:
-blending over images (can already easily be put into the C-version by getting initial color values from the target bitmap inside the render function, instead of setting them to 0(the fr,fg,fb values))
-arbitrary size rendering at arbitrary position (like calling with a starting point and a width and height attribute, so you can even render to bitmaps without covering their whole area)
-export gradient as code (I already wanted to have this on the first C version, but after seeing my first image i got so excited that i could not resist publishing it)
-saving and loading to and from textfiles (will even be hand-editable)
...this list will probably grow during the process of porting, as it will not just be a 1:1 port...

And now, please wait patiently for the port. It will take a lot longer than i originally thought, because there are so many NEW features i think of, that i want to have in it and also i won't release it until the GUI is done and everything is working. (Will take at least a week if not longer, because also i can't stop playing around with the old version sometimes.;D And thanks for offering but i don't want your help, because i want to code everything myself.(at least for the initial release))

Your polynomial tests are looking interesting, especially those where the polynomials are "dotted".:)
I also made another cool polynomial.(Watch out for the image of the day for tomorrow;))

da_flo
Quote:

Don't worry the C++ port, will be excellent.

I'm not worrying. ;)

Quote:

Targetsystem stays Allegro, so the thing will be crossplatform.

Okay then. But I still think it would be better if it did not directly depend on allegro, and if we could use any graphics or GUI API with it.

Quote:

There is really no need in giving me hints on how to do the class hierarchy(I even felt a little insulted when you pointed on those obvious things with virtual functions.

I didn't intend to insult you. Sorry if I there was a misunderstanding. :-[
I was not giving you hints, I was only describing in details how I would implement some ideas that just came to my mind and that I found worthwhile.

Quote:

Each attractor class will have just one single function(and that is NOT the distance function;))

Quote:

every derived attractor will be free to add thousands of other functions to its' private scope and then act on the given pixel as weird or cool as it wants.

Uh ? What will this single function be ? ??? I can't really see your class design, and I'm really curious about it. :)
I just hope that with this new design adding new attractors will remain as simple for the programmer... But then again I'm not criticizing your work, and I totally trust your C++ fu. :)

Quote:

And now, please wait patiently for the port.

But I am waiting patiently for it. :P

Quote:

And thanks for offering but i don't want your help, because i want to code everything myself.(at least for the initial release)

I understand. That's pretty normal.

Sorry, I was really getting excited about your work and about this gradient generator, and I've perhaps gone a bit too far in my previous post. ;D

( PS : I don't want to look stubborn, but I still think some of my ideas were really interesting. And also you didn't say anything about the fact having an abstract class for functionnal curves, so that we can have any functionnal curve, and not only polynomial attractors. :-/)

______________________________________________________________________________

In other news, I kept playing with the polynomial attractors, and I now have an accurate distance calculation algorithm. :)
In fact, the idea I said I had was really bullsh*t. But then I found a true idea ;D, using 3 clever lookup tables. I didn't add custom precision yet, but that won't be too hard, IMO.

So rendered the same example as before, y=x^2 with a range of 10, and here is the result : yay.png.
I even tried to use a range of 1, and it perfectly plotted the polynomial curves. See : thin2.png.
Nice. :)

Then I still have to improve it, because it has some serious problems, particularly when the polynomial curve goes really far beyond the y bounds of the screen, for example for high degrees and/or small units. I quickly becomes a memory hell and either it's awfully (and uselessly) slow or it screws everythings up.
I'll add x and y bounds to the part of the curve handled. That way I'll get rid of my problem, and I'll be able to use small bits of curves as attractors, which will be quite nice to play with. :) I began to code it very late yesterday night, so I couldn't do it. I'll be able to work on it once speehack is over (or once I have withdrawn from speedhack ;D).

Dennis
da_flo said:

Uh ? What will this single function be ????
I just hope that with this new design adding new attractors will remain as simple for the programmer...

The function will be cleverly choosen.;)
Your hopes will not be dissapointed. It will be even easier for the programmer than it is now. (And i did not say there would be no distance method at all, just in case you wondered about that.;))

da_flo said:

I still think some of my ideas were really interesting. And also you didn't say anything about the fact having an abstract class for functionnal curves, so that we can have any functionnal curve, and not only polynomial attractors.

I'm not saying that i will not add that. Also i'm not saying that i will add it. But if i add it, it would be done properly, so that the user can enter the function definition in a freeform string, just like if he'd write it down to paper. That would require writing an advanced string parser though and usage of clever operator and operands stacks and trees. Since the other features i planned will already be taking more time, it is more likely that it will not be in. But of course, i you still want to, you can later add it yourself.8-)

But i don't want to distract you from speedhack now, and as i already said the C++ port is not nearly done yet. (Some parts of it are still in the planning phase...;))

da_flo
Quote:

But i don't want to distract you from speedhack now, and as i already said the C++ port is not nearly done yet. (Some parts of it are still in the planning phase...;))

Well, I'm having annoying computer problems, particularly with my network connection. All of this is pissing me off, and I haven't started speedhack yet. I'm in such a bad mood that i don't even know if I'm going to do it, finally. >:(

And you're not distracting me at all. You're only answering to my questions and my ideas. It's rather me that have been distracting you from your C++ port for the past few days. ;)

And the fact that the C++ port isn't nearly quite done isn't a problem. I still have many things to do with functionnal curves attractors and my distance calculation algorithms ;D. (by the way, did you look at my new pictures and what I said about my new accurate algo ?)

Dennis
da_flo said:

It's rather me that have been distracting you from your C++ port for the past few days.

yes...>:( (don't take that too seriously;))

da_flo said:

by the way, did you look at my new pictures and what I said about my new accurate algo ?

I looked at the pictures and i think you did not post your new algo.
By the way: Is it really necessary to have 3 look up tables. Would it not be sufficient to have one additional table where for each y it holds a list including multiple values for the missing x pixels?;) (or maybe the other way round, does not matter too much...except that the table will be easier to calculate if having an x table with lists for the missing y values)

da_flo
Quote:

Would it not be sufficient to have one additional table where for each y it holds a list including multiple values for the missing x pixels?

hmm. I thought about it in my bed yesterday night (I didn't even had this idea before...), and I didn't think it would really work easily. But after all, if I look at it more closely, perhaps it would work.

But my method is not really more complicated or eats much more computing or memory power, and is really elegant mathematically speaking, IMO. :)

Dennis

I think i just found the best and fastest method of all(:)):
(look at the piccy then read the description)
http://homepages.compuserve.de/DennisTapier/allegroforum/distance.png
The Algo-Idea to that:
first: Compute distance to function value.
second: Simultaneously trace in whole pixel steps a line to the left and one to the right.
break conditions:
If one trace hits an y position where it is smallerOrEqual than "function value at that position plus the 'rise' value" or bigger than "function value at that position minus 'fall' value", you can stop tracing into the opposite direction and break the trace loop.
If traces in both directions hit the end of the lookup table without any result you can stop tracing as well.
result: if the trace did not find anything the calc from first is the distance.
if the trace did hit anything(there is always just one candidate for a smaller distance found from tracing, cause if one side is succesfull the other is automatically farther away!) take the smaller value of (trace distance,distance to function value).

Hope it gets clear, I was too lazy to give a more detailed explaination.:)

[edit] Because of the y rising downwards you have to switch some plus and minus and blah in the above description but the idea stays the same. The fun thing: NO squareroots are involved!!! ('cause the tracelength-count can directly be taken...;))[/edit]

[edit2]it can be optimized even more by just storing a 'high' and a 'low' for each x position(don't extra store 'rise' and 'fall') then for the trace position a simple low<=y<high(or high<=y<low for y rising downwards) will do sufficient for stopping the trace[/edit2]

[edit3]
Trace in either direction can also stop if that directions' tracelengthcount exceeds the 'range' of the polynomial or if that directions tracelengthcount exceeds the distance to the function value.[/edit3]

[EDIT4](too bad i spotted a flaw: For a pixel to the bottem right or left of the minimum in the above example, it would report a wrong distance...>:()[/edit4]

[edit5]
...ok but coming around that flaw is easy:). If the trace was unsuccesfull in both directions:
store the distance to the function value as current result
then calculate the distance to x-1's function value and the distance to x+1's function value (euclidean distance)
if both are bigger than the current result, stop
if one of them is smaller than the current result, store the smaller one as the current result and go on calculating the distance to subsequent function values but only in that direction where the distance was smaller
as soon as you find a distance that is bigger than the current result you can stop and return the current result!:)
If i don't overlook sth. this algo should now be absolutely flawless and very quick in most cases and still quick in cases where the trace was unsuccesfull.
Damn, i'm good! ;D
[/edit5]

da_flo

Okay. I'll take a closer look at it later. :)

(Must... stay... away... from... allegro.cc)
(Luckily, I currently cannot access to the internet from my coding computer ;D)

Dennis
da_flo said:

Must... stay... away... from... allegro.cc

Yeah, i must say i'm really becoming obsessed about the thing.:D

Make sure you don't miss my edits above as they describe pitfalls you could encounter, if you were very tired already.;)

------------------
[edit](should have been an additional post)
I thought about portability again and i plan now, as you suggested, to keep the core functionality system independent.
But i will not use a virtual putpixel function. I found a better solution: The gradient generator class will be a template, in which the exchangable type will be a customized bitmap type, that the programmer has to supply(i will supply one for the allegro version).
That customized bitmap type will be required to have some specific methods then(like get_width, get_pixel, put_pixel...) but basically be kept simple.
By that, virtual function calls to pixel putting functions are avoided, because the platform specific code for the gradient generator is already generated at compile-time.
The attractors and the gradient generator classes will use an internally device-independent pixel format, which the customized bitmap will be responsible for to convert correctly.(Will be very easy to implement for the allegro specific bitmap type, because of makecol.:))
So far so good. The basic planning phase should be completed soon.(Playing around with the old version and writing so much around here and thinking of other things, kept me from making any major progress with the implementation.;D)

da_flo
Quote:

da_flo said:
Must... stay... away... from... allegro.cc

Yeah, i must say i'm really becoming obsessed about the thing.:D

I meant : I must stay away from allegro.cc. ;D For speedhack reasons...

Quote:

I thought about portability again and i plan now, as you suggested, to keep the core functionality system independent.

:) :) (Nothing more to add)

Quote:

So far so good. The basic planning phase should be completed soon.

Okay. Keep going and good luck ! :D

PS : Hey, you will be able to post new message now ;)
I'm currently busy with speedhack, so I can wait a while for the code for the IOTD. That way you won't be stuck again if you want to post a new message apart from the IOTD code. ;)

Dennis

Well then here's the IOTD code:

col_att_list3 test;
  init_ca_list3(&test);
  add_to_ca_list3(&test,CA_POINT,CA_ABSORB,1.8,1.0,320,240,0,255,255,200,NULL);
  add_to_ca_list3(&test,CA_VBAR,CA_ATTRACT,1.8,0.33,320,0,255,255,100,320,NULL);
  add_to_ca_list3(&test,CA_HBAR,CA_ATTRACT,1.8,0.33,0,240,255,255,100,240,NULL);
  add_to_ca_list3(&test,CA_POLYNOMIAL,CA_ABSORB,1.8,0.39,0,0,100,100,0,200,
                  make_polynomial(5,100,320,240,-1.0,0.0,5.0,0.0,-4.0,0.0));
  add_to_ca_list3(&test,CA_POLYNOMIAL,CA_ATTRACT,1.8,0.39,0,0,50,150,255,200,
                  make_polynomial(5,100,320,240,-1.0,0.0,5.0,0.0,-4.0,0.0));
  render_col_grad_to_bitmap3(backb,&test); /* backb must be a valid 32bpp bitmap 640x480 in dimensions */
  save_tga("./polycool.tga",backb,NULL);
  kill_ca_list3(&test);

(you can make backb 1600x1200 but then you must also multiply all positions and ranges by 2.5)

I'll try to resist coming back for a whole week.:)

Edward Sheets
Dennis said:

I'll try to resist coming back for a whole week.:)

Don't do that! This has been one of the most educational and productive threads ever :D

Good job with the Dynamic Color Gradient Generator. It's very kool.

Dennis

Hey, thanks a lot!:)

But i definitely need to cut back on my visits, or else nothing ever gets done.
Maybe i'll report my progress once a day or so.

(As everyone can see i could not even resist coming back for a few hours:P)

[edit sunday 14th]
Progress:
-implemented customRGB type meant for greater precision during color mixing
-implemented the GLOBAL attractor type as the base class from which all other attractor types will be derived from
(thats all for today as the lord said sth. like "Men shalt rest on the seventh day!";))

[edit Monday 15th]
Progress:
-implemented the HBAR and VBAR attractor classes
-the "it will be easier than it is now to write new attractor types"-feature fell victim to the polymorphic design and to my effort in making the maintenance and extendability of the gradient generator itself easier, but the good thing about it is, that writing new attractor types will be somewhat normed, not hacky and finally introducing the new types to the gradient generator will be easier

[edit Wednesday 17th]
Progress:
-implemented POINT, CIRCLE and FCIRCLE attractor classes
-made plans and calculations for a POINTE class(point attractor with an elliptic range)
-also played with the thought of a rotated ELLIPTIC attractor class and thought of making POINTE rotated as well

da_flo

Okay I'm back after this exhausting speedhack and a small break.

As for the distance calculation, I'll post a detailed comment once I'm motivated enough to analyse your method in details and give a good explanation of mine.;) (Seems like I'm getting tired of writing long and complicated posts. But be sure I'll do it !). I'll just say now that my method is flawless too, quite quick too, and above all mathematically very clear and elegant ! ;D (well, that's why it seems appealing to me. We don't have quite the same concerns sometimes ;)

Quote:

made plans and calculations for a POINTE class(point attractor with an elliptic range)

Nice idea. That way of generalizing is really the one I like to play with. :)

Quote:

also played with the thought of a rotated ELLIPTIC attractor class and thought of making POINTE rotated as well

In fact, I was thinking of making every attractor rotated, even POINT for consitency.
The attractors, instead of being defined by a (x,y) pair of coordinates, would then be defined by (alpha, x', y'), where (x', y') are the coordinates relative to the axes rotated by the angle alpha around the origin ( x==x' and y==y' for alpha = 0 mod 2*Pi). That way it will be really general and quite elegant. All you'd have to do when doing the distance calculation would be converting the (x,y) coordinates of the current point to (x',y') and do the calculation as usual in the new coordinates. And if you're concerned with speed, you can always use sin and cos lookup tables, of course. ;)
(Note : I am not giving you hints, just explaining my method in details ;))

Also, having elliptic attractors will be quite nice. And there should be a way to easily calculate the distance to an ellipse, using the properties of the normals to an ellipse. (I would have to dig into my geometry courses, though ;D)

Dennis
da_flo said:

And there should be a way to easily calculate the distance to an ellipse,

It is in fact easy and i already made all the calculations, generalized for rotated ellipse and point"e".
(I'll not write it down here, because it's just basic trigonometry combined with some simple IR^2-vector math and i hate writing math in ascii(and in english) and besides it would almost already look like the code itself, so it would be twice the work in half the time.;)(another reason **))
For the pointe the calculations are almost the same, just a little different, because the distance to the ellipse is in the case of the elliptic range around a point not of any matter.
In the pointe case, only the distance to the center of the ellipse matters and its' relative percentage of the length of the vector to the point "on the ellipse" at the same angle inside the ellipses' rotated system.(Sounds a little odd, but if you could see what i see in my (slightly messy)sketch it becomes obvious.)

I think you don't even need to dig in any geometry books for that. Just draw a sketch of a cartesian coordinate system(y grows downwards) then put a rotated(angle grows clockwise) ellipse somewhere with attributes "center(x0,y0)","width","height","angle(rotation around its center)", then start using your brain.:)

(**see the difference: ..I don't feed you every (annoying) detail, by that i give you the chance to find a way(which may turn out to be different from mine) yourself and i don't already lead your thoughts into any specific direction.)

da_flo said:

(Note : I am not giving you hints, just explaining my method in details;))

Very wise of you to put that comment.(Kept me from exploding into 1000 pieces, but maybe it is just me who gets angry that easily.);)

[edit]
I hope your silence does not mean that you hate me now, because you might have misunderstood me. It is not that i would not appreciate your or anyone's help in general. It is just that i (for some weird reason i don't even know myself) get annoyed if i'm swamped with lot's of detailed help, which i did not explicitely ask for and especially if it is for a topic i (think i) perfectly know well enough myself. I don't know, there is probably no excuse for my harsh response to you.:-/

[progress Thursday 18th]
-implemented the POINTE (rotated elliptic range) color attractor type
-fixed lots of conceptual errors in all other types
(i have not yet tested a single attractor, because the gradient_gen class is not implemented yet. because of that, i decided that after implementing the polynomial type and the ellipse type i will put a "new attractor lock" onto me, and then write the gradient generator class first, so i can at least test, if the attractors so far are actually working, because coding without actually seeing something from time to time is starting to get boring:))

[progress Saturday 20th]
-implemented rotated ELLIPSE color attractor type
-decided to make a rotated BAR and a rotated POLYNOMIAL attractor(of course the rotated bar would already be included in the POLYNOMIAL but for a simple bar, distance calculations can be made less complicated and faster)
(rotations pivot will always be the center of the attractors themselves)

[progress Thursday 23rd]
-did not do anything since saturday, hoping to implement the POLYNOMIAL attractor today, if i can finally manage to stop playing "Bunkermaster":o

Thread #515585. Printed from Allegro.cc