An introduction to some variants of metaballs algorithms ======================================================== Sebastien Loisel, zed@scylla.math.mcgill.ca The key idea here is to let a ball be the volume in space defined by f(x,y,z)>1 or f(x,y)>1 for some function from R^3 or R^2 into R, f>=0 and f vanishes at infinity. Then, when you want multiple metaballs, you get many such f, call them f1, f2, ..., fn, and then the volume defined by everything is (f1+f2+...+fn)>1. The second step of the algorithm is to use some sort of implicit surface rendering algorithm to draw the resulting object. The naive algorithm is of course the Marching Cubes which is not discussed here. One Metaball ============ All you really need to define a single metaball is to have a single f, non-negative, which vanishes at infinity. It is probably best to pick a 'smooth' f, at least continuous, and as differentiable as possible to help in the rendering stage later. Here are some example f's that meet this requirement: f(x,y,z) = R^2 / ((x-a)^2+(y-b)^2+(z-c)^2) for 3d metaballs If you look at f<1, that's the interior of the ball (x-a)^2+(y-b)^2+(z-c)^2=R^2 which is the sphere in 3d centered at (a,b,c) of radius R. f(x,y) = R^2 / ((x-a)^2+(y-b)^2) for 2d metaballs Similarly this is the 2d ball centered at (a,b) of radius R, when f<1. f(x1,x2,...,xn) = R^2/((x1-y1)^2+(x2-y2)^2+...+(xn-yn)^2) This is the n-dimensional ball of radius R centered at (y1,y2,...,yn) These balls are bad because f is strictly positive, eg, things really far away from the ball are affected/deformed (ever so slightly) by the ball. (We will see how that is so in the next section.) In that respect, some people prefer to use balls like these: f(x,y) = 0 if |(x-a,y-b)|>R 1 if |(x-a,y-b)|1. If f1 is 'far' from all other balls so that, near where f1 is centered, f2+f3+...+fn is almost zero then f1+f2+...+fn is approximately equal to f1 and then f1+f2+...+fn>1 near f1 is approximately the volume defined by f1>1. So when the balls are far from one another, they are not significantly deformed. At any rate, f1+f2+...+fn > f1 everywhere. Therefore, the volume f1>1 is always contained in f1+f2+...+fn>1, no matter what. So we know that when the balls are far apart, they're not deformed. When they get closer together, they'll be bigger if anything (by the previous paragraph). So the deformation at least makes some kind of sense. If you're animating the f's and they change with time, but if they change in a nice enough way, it turns out that then the volume f1+...+fn>1 will also change in a nice way. Rendering ========= A simple algorithm is obvious in 2d. Have a 2d array X (say, 1000 by 1000). Then choose a 'window of interest', say [0,1]x[0,1], the unit square in R^2. Then what you'll do is set X[i][j]=(f1+f2+f3+...+fn)(i/1000,j/1000) Now you have a 1000x1000 bitmap which you can draw on the screen by simply putting a white pixel when X[i][j]>1 and a black pixel when X[i][j]<=1. You can also try to antialiase the picture by looking at the value of X[i][j] but this does not always work too well. It is tempting to try to do the same thing in 3d but there are problems. First, a 1000x1000x1000 array is a tad large, forcing you to much coarser approximations. This can make you miss important details in the picture. Furthermore, even when you have the 3d array, rendering it may prove hard. Rendering each 'voxel' as a cube may look bad. There is a patented interpolating algorithm called the 'marching cubes' algorithm which I will not describe. Implicit surfaces drawing (which is what this is) is still being studied furiously today. There are solutions but I don't intend to discuss any of them here. They would complicate significantly this short tutorial.