   Efficient 2D Metaballs
  I'm playing around with a bit of code that renders 2D metaballs. I got it up and running fairly quickly, because the theory and maths behind metaballs is fairly straightforward (at least in 2D it is) ;) My code uses the inverse-square law for working out how much influence a metaball has on any given pixel depending on the distance, scales it by a "mass" given to the metaball (I tend to think of a metaball's area of influence as being akin to a gravity field - I render everything inside an arbitrary fixed "event horizon", in this case 1.0).Here's my first-pass at the code:typedef struct{float r, g, b;} Colour;typedef struct{float x, y;float mass;} MetaBall;MetaBall metaballs[NUM_METABALLS];float influence[WINDOW_WIDTH][WINDOW_HEIGHT];Colour pixels[WINDOW_WIDTH][WINDOW_HEIGHT];void CalculateMetaballs(){// Process metaball positions and stufffor (int ball = 0; ball < NUM_METABALLS; ++ball){// ... Update the metaballs mass and position ...}// Reset the influence mapmemset(influence, 0, WINDOW_WIDTH * WINDOW_HEIGHT * sizeof(float));// 1st pass: Recalculate the "gravity" fieldfor (int x = 0; x < WINDOW_WIDTH; ++x){for (int y = 0; y < WINDOW_HEIGHT; ++y){for (int ball = 0; ball < NUM_METABALLS; ++ball){float xDist = (x - metaballs[ball].x);float yDist = (y - metaballs[ball].y);float xDistSq = xDist * xDist;float yDistSq = yDist * yDist;// Inverse square law... 1 / (distance^2)// Here it's being scaled by the metaball's "mass", which affects its size onscreenfloat g = metaballs[ball].mass / (xDistSq + yDistSq);// Add this to the influence mapinfluence[x][y] += g;}}}// 2nd pass: Copy to texturefor (int x = 0; x < WINDOW_WIDTH; ++x){for (int y = 0; y < WINDOW_HEIGHT; ++y){float currInfl = influence[x][y];// Test to see if this pixel falls inside or outside a metaball boundaryif (currInfl >= 1.0f){// Flat shading for the purposes of this example, although my code// can also do some extra maths which turns the influence value into something// that looks nicely shaded onscreencurrInfl = 1.0f;}else{currInfl = 0.0f;}// set the pixel colour (greyscale in this case)pixels[x][y].r = pixels[x][y].g = pixels[x][y].b = currInfl;}}// Bind the pixel buffer to a texture, and render it as a 2D quad}I have a 2D array of "influence" values, and I iterate through every one of them adding up the influence on that pixel from all of my metaballs, and then I do a second pass, ignoring everything below the threshold value (colouring it black), and generating a good colour for everything above it (in the cut-down code above, it just renders it white). It works, but it's not very efficient. Increasing the number of metaballs slows it down - increasing the screen resolution slows it down a LOT.My question is: What would you do to optimise this?- Is there a clever trick I can do in the first pass to help me avoid doing WINDOW_WIDTH * WINDOW_HEIGHT * NUM_METABALLS bits of calculation? This function gets called every frame, and the movement of the metaballs is fairly arbitrary so I'm not sure what (if anything) I can predict or cache.- Is there a way I can fold both passes into a single pass? Would it help?- Is this as simple as it gets, and my only option from here is to rewrite this in assembly? (I don't really know assembly, but I'd have a stab at learning it if it was the best way to do this)- Is this a suitable job for some kind of shader? (again, I haven't really played with shaders but would be willing to try)Any thoughts would be much appreciated. Cheers.   
  The way I'd do this now is by just rendering the balls into a texture with additive blending using the 3D hardware. So instead of having a RAM buffer that stores the influence per pixel, you just have a large texture in VRAM that you use as a render target. Each ball would be rendered as a quad using a smaller texture with a circular gradient (bright in the center, fading out toward the edges). Changing the influence attenuation function would be a simple matter of switching to a different ball texture. Once you've rendered the balls into the large texture, you'd render it as a full screen quad with a shader (or even just alpha testing) that makes it only draw the pixels with a high enough influence value.I used this concept (but implemented in software) to create the nebulae in Strange Adventures in Infinite Space a while back. I used several different "attenuation sprites" to create more complex and interesting shapes; for example, rings and double rings in addition to ball shapes.edit: Even if you want to stick with the software implementation, drawing the balls like "sprites" (i.e. limiting the area influenced by each ball) will vastly improve your performance. So instead of "for each pixel loop through each ball" you'd do "for each ball loop through the pixels within an N*N square" where N is twice the distance at which the influence becomes negligible. Even if the average "influence box" is half the width of the screen, you'll only touch 25% the number of pixels and therefore run four times as fast as before.[Edited by - Fingers_ on February 27, 2008 11:24:05 PM];  That's a great approach, Fingers_! That has set a lot of ideas in motion for me.The main thing I have trouble getting my head around is that although I want my "attenuation sprites" to define which bits of the texture get drawn solid and which are transparent, I wouldn't want to use them for shading the colour of the bits that actually get drawn. Right now I'm applying a bit of maths to every pixel to turn the influence value at that point into something that looks nicer shaded (rather than just setting it to 1.0f and having completely flat-shaded things).I think what I'd like to do is to either have two sprites for each metaball (one being the "attenuation sprite", and one being some shading for the bits you'll see onscreen), render both sets of sprites to seperate textures and then do some graphics API jiggery-pokery to merge the two together... Or better still (and I can't remember if OpenGL can do this or not, I'm rusty) have my sprite textures be RGBA ones, where the RGB value reflects the shading you'll see onscreen and the alpha is used to build up the "attenuation map". I forget whether openGL will let you set a texture render target that will also store an alpha value or not, but I can check that.Great advice though, that gives me lots of interesting new ways to think about doing this. Also, Strange Adventures In Infinute Space is a very cool game. Kudos! :o)   ;  I think the most straightforward way to turn the influence values into colors these days is with a fragment shader. So the influence texture would be just one channel and the shader uses some magical math to turn it into RGBA values. It's certainly possible to use an RGBA texture as a render target, and you can even do this in OpenGL 1.1 (if you're in a 32-bit video mode) by copying from the frame buffer into a 32-bit texture. Alpha values blend just like the RGB's so you could first draw your color layer, then draw the influence additively into the alpha by using sprites that are black in RGB with the attenuation blob in the alpha channel (so it only modifies the alpha, not the color). I've tested additive blending in the alpha before and it does work.Note that with the RGBA texture you will probably need a fragment shader if you want to do both the color and alpha in one pass with one sprite texture, and then it's most likely faster to go with the one channel influence texture + shader to color it. Of course, you might want to do something more complex with the colors...   ;  I just had the urge to whip up a proof of concept :)  This should run on any hardware that supports 32-bit frame buffers (aka "destination alpha"). It uses four different sprites packed into "blobs.tga" and actually renders the colors and alpha all in one pass using glBlendFunc(GL_ONE, GL_ONE). The render target (influence + color texture) is 512x512 pixels, and is magnified when rendered... The edge detail still looks per-pixel accurate because of bilinear filtering.;  That proof-of-concept is pretty, but I'm not entirely sure I understand what it is I'm seeing or how you did it. I can see the edges between the coloured sections and the black non-coloured bits, and see how that looks pretty metaball-ish, but I'm a bit confused about how that relates to how the colours shift around. Is there any connection between the shapes and positions of the blobs you're writing into the alpha channel, and the shapes and positions of the blobs you're writing into the RGB channels?I may end up looking into fragment shaders, just because they sound interesting (I've not worked with shaders before, I'll need to hunt down some good resources to get started on teaching myself). Am I right in reading what you say about them as meaning that once I've written all the attenuation sprites into the alpha channel of a texture, I'd use a fragment shader to iterate through every texel, check it's current alpha value, set it to 0 if it's below the threshold, and if it's about do magic maths on the value to generate an RGB colour value, and then set the alpha to 1?My hunch is still that I'd rather get my RGB values from sprites just for the flexibility that changing the textures would give me (rather than changing the shader maths), but I suppose I could still use a fragment shader just as a quick way to patch up the alpha channel.   ;  The program creates a hundred randomly moving "blobs", each of which uses one of the four different sprites in blobs.tga. I guess it'd look more like standard metaballs if you changed the texture to only have fuzzy spheres rather than rings etc.In the render to texture pass, each sprite is simply drawn additively into all four channels (with glBlendFunc(GL_ONE, GL_ONE)). So each sprite adds to the RGB color, as well as the "influence" (alpha).In the final render pass, the program draws a single quad using the previously generated texture with glBlendFunc(GL_ONE_MINUS_SRC_ALPHA, GL_ZERO), glEnable(GL_ALPHA_TEST) and glAlphaFunc(GL_GREATER, 0.5). The alpha testing causes the sharp cutoff between the "inside" and "outside" of the blob, and the blendfunc  just creates the gradient inside this edge (to make it look more interesting than just flat color).edit: to answer your question.. yes, that's more or less what you'd do in the fragment shader approach. For each pixel drawn, you evaluate the influence channel and determine the RGBA output based on that. Cutting off parts below the influence threshold can be done either with the discard command or by setting the output alpha to zero. Some say that discard is faster on newer hardware.[Edited by - Fingers_ on March 2, 2008 7:55:52 PM];  Okay, so I've set aside the stuff about shading the "insides" of the metaballs for now, in favour of getting a flat-colour set of metaballs running based on attenuation sprites. There's obviously still room for improvement here, but my code looks a little bit like this right now (I hope this isn't getting too openGL for a general graphics programming thread):#define WINDOW_SIZE 256#define CHANNELS 4#define NUM_METABALLS 3GLuint AttenSpriteTex;GLuint RenderTex;float pTexture[WINDOW_SIZE * WINDOW_SIZE * CHANNELS];// ... Some stuff ...void RenderMetaballs(){// ... Process metaball positions ...glClearColor(0.0f, 0.0f, 0.0f, 0.0f);glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT | GL_STENCIL_BUFFER_BIT);glDisable(GL_DEPTH_TEST);glEnable(GL_BLEND);glBlendFunc(GL_ONE, GL_ONE);// ... Setup a suitable camera, reset the matrices, etc ...// AttenSpriteText is the attenuation sprite texture, loaded from a TGA during initialisation, and// give this handle by OpenGLglBindTexture(GL_TEXTURE_2D, AttenSpriteTex);for (int ball = 0; ball < NUM_METABALLS; ++ball){// ... Draw the ball sprite (in immediate mode for now, but I'm not drawing a huge amount right now) ...}// Another texture handle I created earlier: This is the texture I want to render toglBindTexture(GL_TEXTURE_2D, RenderTex);// Copy the screen buffer to RenderTexglCopyTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, 0, 0, WINDOW_SIZE, WINDOW_SIZE, 0);// I want to monkey around with RenderTex, so give me a pointer to it.glGetTexImage(GL_TEXTURE_2D, 0, GL_RGBA, GL_FLOAT, pTexture);// Step through every texel, and patch up the valuesfor (int i = 0; i < WINDOW_SIZE * WINDOW_SIZE * CHANNELS; i += CHANNELS){float r = pTexture;float g = pTexture[i+1];float b = pTexture[i+2];float a = pTexture[i+3];// TODO: Get this from the alpha value of a 32 bit sprite!// (I'm using the red channel rather than the alpha here because pTexture seems to only// have alpha values of 1.0f)if (r >= 1.0f){// This will eventually be cunningly shaded - Solid white for nowpTexture = pTexture[i+1] = pTexture[i+2] = 1.0f;pTexture[i+3] = 1.0f;}else{pTexture[i+3] = 0.0f;}}// Dark purple background for testing the alpha worksglClearColor(0.2f, 0.0f, 0.2f, 1.0f); glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT | GL_STENCIL_BUFFER_BIT);// Make sure we're using the monkeyed-with textureglTexImage2D(GL_TEXTURE_2D, 0, CHANNELS, WINDOW_SIZE, WINDOW_SIZE, 0, GL_RGBA, GL_FLOAT, pTexture); glEnable(GL_DEPTH_TEST);glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);// ... Draw the single quad with the texture on it ...glutSwapBuffers();glutPostRedisplay();}I have a few problems:1 - Although the TGA texture I'm loading is suitably 32-bit, with an alpha channel, the texture I'm rendering to seems to have an alpha of 1.0f for every texel, so I'm having to use a different channel just to get the tests working. I'm pretty sure my TGA loading code is fine, given that I brought it over from an old project where it had been specifically written for loading particle textures, so I presume I'm doing something wrong in the rendering to the texture.2 - My attenuation texture, being a render of 1/(dist_from_centre^2) doesn't actually fade to black on the edges (and can't have values above 1 towards the centre), which is causing a few artifacts. I presume the only way to fix this is with a better choice of texture.3 - Most annoyingly, this code still runs painfully slowly (as in, not noticeably faster than my original brute-force and ignorance method) at higher resolutions (say, if I set WINDOW_SIZE to 1024). I presume this must be because one or more of the OpenGL calls is really expensive - it's slow even when I don't do the second pass to patch up the alphas and the colours in pTexture.   ;  I'm not sure what you're doing there.. Why are you transferring the texture back and forth between RAM and VRAM and modifying it on the CPU? That's always going to be horribly slow. If you want speed, you need to use the GPU for everything. Do you understand what a fragment shader is?Here's the rendering code from my test program, which only uses the fixed function pipeline:// RENDER TO TEXTURE PASS// the "blend factor" here is set just below the influence threshold so single blobs// won't be visible, only when multiple blobs combine they produce a visible shape.bf = 0.45f;glColor4f(1, 1, 1, bf);glEnable(GL_BLEND);glBlendFunc(GL_ONE, GL_ONE);glBegin(GL_QUADS);for (i = 0; i < 100; i++){// get UV coordinates based on blob type (0-3)u = (bb.t & 1) * 0.5f;v = (bb.t & 2) * 0.25f;// draw the quad // the xy coordinates are between 0 and 512glTexCoord2f(u, v);glVertex2f(bb.x - 64.0f, bb.y - 64.0f);glTexCoord2f(u + 0.5f, v);glVertex2f(bb.x + 64.0f, bb.y - 64.0f);glTexCoord2f(u + 0.5f, v + 0.5f);glVertex2f(bb.x + 64.0f, bb.y + 64.0f);glTexCoord2f(u, v + 0.5f);glVertex2f(bb.x - 64.0f, bb.y + 64.0f);}glEnd();// copy the frame into the "influence texture"gfx_bindasset(blobrender);glCopyTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, 0, 0, 512, 512);   // RENDER TO SCREEN PASS// clear the screen so we can actually display the thingglClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);// use alpha test to give it hard edges   glDisable(GL_BLEND);   glEnable(GL_ALPHA_TEST);glAlphaFunc(GL_GREATER, 0.5f);// draw fullscreen quadglBegin(GL_QUADS);glColor4f(1,1,1,1);glTexCoord2f(0, 0);glVertex2f(0, 0);glTexCoord2f(1, 0);glVertex2f(1024, 0);glTexCoord2f(1, 0.75f);glVertex2f(1024, 768);glTexCoord2f(0, 0.75f);glVertex2f(0, 768);glEnd();The most likely reason why the alpha in your framebuffer is not working is that you haven't requested any alpha bits (in addition to red, green and blue bits) when you initialize the OpenGL context.   ;  Hi again, thanks for sticking with me so far :)I realised the error of my ways in copying the texture back to the CPU to patch up the alpha values. I do know what fragment shaders are, and what they can do, but I've never actually written one. What I was trying to do there was a "poor man's" replacement for a fragment shader (ie, just passing the texture back to the CPU to do the work there until I figured out how fragment shaders work and could write one to shift all of the work back to the GPU and avoid the copy). Evidently I had no idea just how expensive that operation would be (I knew it'd be slow but I'm amazed at just how slow - I suppose in hindsight I should have realised that your average graphics pipeline really isn't set up to efficiently copy data from the GPU to the CPU though).I see what you're doing with the glAlphaFunc thing using the fixed function pipeline, and I think that could work for me if it wasn't for the first problem that I listed in my last post, namely that my call to glCopyTexImage2D sets the alpha to 1.0f in any texture I use it to copy into. I ran some tests in which I called glTexImage2D to grab the data from other textures so I could check it in in the debugger (ie, my attenuation sprite texture, and the texture I intended to render into but without actually calling glCopyTexImage2D to copy stuff into it), and the alpha channels of those seemed to do exactly what I expected. So, to be clear, the texture I'm rendering to does not have an alpha value of 1.0f, and my code in general has no problem with alpha channels. The alpha of a texture is only set to 1.0f when I call glCopyTexImage2D on it.You said that this might be because I'm initialising my OpenGL context wrong. I hope you don't mind me being a bit slow and dumb here (I'm really rusty at graphics coding), but I'm not sure exactly what I'm doing wrong. The program currently uses glut to setup the window and rendering context, and my initialisation code looks like this:glutInit(&argc, argv);glutInitDisplayMode(GLUT_DEPTH | GLUT_RGBA | GLUT_DOUBLE);glutInitWindowSize(WINDOW_SIZE,WINDOW_SIZE);glutCreateWindow("2D Metaballs");Nowhere in the code references GL_RGB, it's all GL_RGBA. Am I missing something? My antiquated copy of the Red Book (version 1.2) mentions that calls to glPixelTransfer* can affect stuff like glCopyTexImage2D , but I'm not calling that because the defaults in the book look like they default to sensible values for the alpha channel anyway.   