next »

[akumagaki]

Hey everyone!

here is my code : http://pastebin.com/m22906638
It's extremely slow. If anyone ever did meta-balling, please, help me 

This is written in C++ with the SFML library


PS : the vecDistance function is here : http://pastebin.com/m6885e6f5 , and sqroot is, atm, just the sqrt function from math.h


Thank you for your attention!

[powly]

Okay, since metaballs are an effect and not a simulation, you don't need to worry about being mathematically correct - the first thing I'd do is remove the square root and instead divide one by the stuff you had under the root. (sqroot(asd)->1.0/(asd)) You'll have to scale the radiuses up a lot, but a squareroot per pixel per ball is already a great speedup.

I've never worked with SFML (and seeing this I think the guys who praise it are completely wrong, but won't judge them before I try it myself) but I rather highly doubt that you really should allocate the memory and an image on the fly. Also your cell system seems a bit of an overkill when the only thing you actually need is going through every pixel and doing a few calculations there.

So, 1.0/(), allocate your memory only once and try to simplify it.

EDIT: Just to mention it, metaballs have always been a slow effect; the best (well, the only good) CPU-based one I've seen myself was a friends system working nicely with 100 balls at 1024x768 - but it needed a hell great amount of inline assembly magic, he said.

[akumagaki]

Sorry?

sqrt(asdf) => 1/asdf ?

Seriously, this makes NO fucking sense...

[powly]

Actually, it does because metaballs are often thought of as a visualisation of an electric fields strength which is calculated like that (I actually don't remember anything about this part of physics, I might have just written complete bullshit.. search the internets for the formula - also I'm referencing a book written in finnish and can't translate it too accurately). The more important reason to use that is that it's very very fast compared to the sqrt version.

The wikipedia article on metaballs also uses it.

EDIT: Okay, it seems to be the potential in an electric field - the formula, of course, has some weird constants but you can just assume them to be one and tweak the radius of the ball (wiki)

EDIT2: Okay, I'm too tired for this, there you'd divide by the distance which would need a square root anyways.. bottom line: use the 1.0/, it works and is fast. Trust me.

LAST EDIT (promise >:3): Okay, so of course you just need the energy which has a r² as a divisor, as in here. This only leaves the constant at a nice q for the charge (aka radius) divided by 4*pi*(electric constant) so you'll basically just have to multiply your ball radius by 4*pi*(electric constant) and you'll be even physically correct - if you want to.

[Zaphos]

The huge arrays allocated every time the function is called are probably a big part of the problem.

But also you can probably precompute the metaball function as a (2*radius) by (2*radius) sprite and just blit it once per cell (eg with additive blending) where you want it.

Also are you doing the same thing for both branches of that if statement (with the threshold)?  If so ... remove the if statement?

[Glaiel-Gamer]

Do it on the gpu

Simply render a bunch of gradient circles with an ADD blend mode onto a texture.

Then render the texture with a shader that does

if(pixelcolor < threshold) color = 0x00000000
else color = 0xFFFFFFFF //or whatever other color you want, or the original color

[raigan]

Then render the texture with a shader

You should be able to do this without shaders as well, via alpha-test.

[powly]

Generally you should use shaders whenever you can because a small specialized shader tends to be a lot faster than using the fixed-function pipeline (with OpenGL, that is) because it's usually just implemented with a bloaty shader in the driver anyways.

[Zaphos]

Fixed function stuff usually works on more computers though?

[powly]

Fixed function stuff usually works on more computers though?

Well, the program reverts to fixed function pipeline anyways if you can't get shader support. My point was that even something the fixed pipeline can do, custom shader does better.

Also, GLSL has been around for over five years. If you have a computer you use for gaming it should support shaders.

[slembcke]

I've done this effect before using blended radial gradients and an alpha test. Works great and is pretty simple. You could use a shader I guess, but I don't see how that would make it better or simpler unless you also did some antialiasing in it.

[Epitaph64]

This might help: http://www.programmersheaven.com/2/Fast-metaballs

[LemonScented]

Your code looks exactly like my code did the first time I tried this, until I learned the trick do doing this in 2D. You can do this in the fixed-function pipeline. You just make a sprite with an alpha channel which fades out, to represent each metaball. Setup a texture the size of the screen to render to, clear it to black, set up an additive alpha blend, and then draw quads at appropriate positions and sizes to represent your metaballs. Once you've done that, you should have a texture full of fuzzy blobs. Draw one quad across the screen with this texture, but set the alpha test to reject anything below a certain alpha threshold (0.5f works fine in my code).

This is basically exactly how we did it in early builds of PaintWorks (Ooold video:

) - it's a bit different now, since I use a shader to mess around with the colours and do the alpha cutoff, but the principle is the same.

[akumagaki]

Ok, thank you for all your replies, LemonScented, you're OEcake like thing is really neat 

First of all, i'm using a sqrt table. I just stored 99999 sqrt values into an array(it's generated in less that one second anyway). Also i free'd the mapArray and newPixels, which stop making the memory go exponential(... Really, it reached up to 1,5 gb of memory used in like 10 seconds...).

But when is see how fast can be flash with all those metaballs...
So some question :

-What is a fixed function pipeline? I know this is related to graphical thingies, but I really don't know what is it and how to use it =/
-What do you mean by "draw one quad", Sorry, my frenchieness just make it worse for me to understand...
-Also... Shaders. It's related to the programmable pipeline right? Someone has a full tutorial starting on beginning for me to understand that? Would even be better if it was linked to SFML 

[LemonScented]

-What is a fixed function pipeline? I know this is related to graphical thingies, but I really don't know what is it and how to use it =/

The fixed function pipeline basically relates to how graphics cards performed graphics calculations before shaders arrived. It's basically talking about using graphics APIs (OpenGL, DirectX etc) without shaders (the shaders being programmable parts of the pipeline). So in this context we're talking about using a standard graphics API to produce this effect without the need for shaders.

-What do you mean by "draw one quad", Sorry, my frenchieness just make it worse for me to understand...

Quad = quadrilateral... A four-sided shape. So for each metaball, you draw a textured square, where the texture fades out from solid in the middle to transparent at the outside, in a way that resembles the falloff of the metaball density. Essentially you take all of that falloff calculation, and produce an image for just one metaball, put it in a texture, and then all you have to do is draw that texture over and over again. Much faster.

A friend of mine once made a
demo that shows how to do this. Might be of interest to you.

-Also... Shaders. It's related to the programmable pipeline right? Someone has a full tutorial starting on beginning for me to understand that? Would even be better if it was linked to SFML  Durr...?

There are shader tutorials out there which I'm sure people can point you towards, but what we've been saying is that you don't actually *need* to use shaders to make this work in 2D, so you might want to just not bother.

[Loren Schmidt]

But when is see how fast can be flash with all those metaballs...

I've played around with this sort of thing a bit in Flash:
http://vacuumflowers.com/metaballs/metaball_toy.html

It sounds like I'm using the same approach that others are- the balls are all precomputed and drawn as sprites, then the colors are remapped once the balls are all rendered. I'll post my source if it will be of use.

Morre and a friend of his did a similar thing recently. I believe they used a similar approach in OpenGL.

[magnum_opus]

just a general optimization tip:

Code:

for(int y=offset.y-radius ; y<offset.y+radius ; y++){
     if(vecDistance(x,y,Cells[i].Pos().x,Cells[i].Pos().y) < radius){
         mapArray[x+(y*WIDTH)] += 255-vecDistance(x,y,Cells[i].Pos().x,Cells[i].Pos().y)* 255/radius);
     }
}

should be:

Code:

for(int y=offset.y-radius ; y<offset.y+radius ; y++){
     dist = vecDistance(x,y,Cells[i].Pos().x,Cells[i].Pos().y);
     if(dist < radius){
         mapArray[x+(y*WIDTH)] += 255-dist* 255/radius);
     }
}

obviously the importance of that depends on how expensive vecDistance is, but it's still a good idea