Fast Metaball Surface Estimation

Using modeling techniques such as Constructive Solid Geometry (CSG), and others, a great number of 3D designs can be quickly and easily created.  Although I have found CSG to be a quite productive tool, I also find there are limitations when you want to produce shapes that can not be easily described by combinations of basic primitives such as cubes, cylinders, and spheres.

A long time ago, Jim Blinn created the “Blobby” technique of forming what appear to be more organic looking shapes.  This technique was created for computer graphic rendering, not for 3D modeling.  There was a later refinement of the technique which took on the name “Metaball”.  In both cases, the technique is a subclass of ‘isosurface’, whereby the surface of the object is described through mathematical combinations of various surface equations.

The easiest way to think about what these things are is to consider what happens with droplets of honey that get really close to each other.  Individually, each droplet might look like a perfect little circle sitting on a table.  Get them close enough, and their boundaries begin to merge, and they become some nice amorphous shape.  Metaballs are like that.  Balls individually will just be balls.  But, as soon as they start to get close to each other, they begin to form a unified blobby looking surface.

Although there is great flexibility in using metaballs for modeling, it can be fairly challenging to try and construct reasonable models in a short amount of time.  Once you have the set of balls that will be used to describe your object, it must be rendered, and meshed, so it can become a 3D solid.  Since metaballs are more typically used for onscreen graphics, rather than modeling for 3D printing, the renderers can take short cuts.  All a renderer needs to do is cast rays into the void, and see where it hits the surface that describes the shape.  Once it hits a point, it can be done, and  move onto the next point, without having to connect them in any meaningful way.

When constructing a 3D model, it is convenient to be able to create a mesh, preferably one that can be enclosed, so that we can generate solids which can be printed.

What I have been struggling with is how to efficiently construct that mesh, without having to do a brute force calculation of the entire space within the volume where the metaball lives.  What I was looking for was a way to cast beams into the metaball equation, and at the same time connect the points to form a nice triangle mesh.  So, first is the beam casting.

The metashape is described by an equation,  f(x,y,z).  The way the equation works, any value that is < 1, is ‘outside’ the surface.  Any value > 1 is ‘inside’ the surface.  Any value that == 1, is ‘on’ the surface.  So, what I’d like to do is search a space, and for each point in this space, figure out the value of the function.  Where the value is 1, I know I have hit the surface.

This is the very crux of the problem.  How do you efficiently choose x,y,z values such that you don’t waste a bunch of time running the calculation for points that are nowhere near the surface.

The novelty that occured to me was that if I assume the whole of the metaball structure is in the middle of a sphere of sufficent radius, I could run a later beam around the surface of that sphere, casting beams towards the metaball structure.  Essentially, what I would like to do is cast a beam towards the conter of the sphere.  From there, if I’m ‘inside’, then cast again, only go half way between our last point, and the point from which I started the last cast.  If I land ‘outside’, then do the same thing, but cast inward.

This amounts to a binary search of the surface, along a particular path from a location outside the surface, in towards the center.  It seems to be fairly  efficient in practice, primarily governed by the original search radius, the number of balls, and the number of rays you want to cast.  In addition, how tolerant you are in terms of getting close to ‘1’ for the function will have an impact on both the quality and the time it takes.

So, now we have an efficient beam search routine.  How to drive it?  The easiest way is is to simply go around a sphere, progressively from the ‘south pole’ to the north, making a full circumnavigation at each latitude.  So, just imagine again, that laser beam (which we know is doing a binary search to find the surface intersection), and run it around the sphere.  Since there is coherence in how we navigate around the sphere, I can connect one point to the next, and easily triangulate between the points.  What you get in the end is not just a point cloud, but a direct calculation of all the interesting vertices, already formed into a nice mesh that can be a solid.

Here, you can clearly see the facets, and perhaps imagine the trace of the beams from bottom to top, and around the circumferance.  This will not work for all metaball networks.  It will not work in cases where there is a separation of the balls.  In that case, two networks need to be formed, or at least the two need to be healed where there is a hole between them.

Similarly, this technique will not work where the is some sort of concave part where the “laser beam” can not see at the surface.  Basically, if you imagine yourself flaying around the object, if you can not see some part of it from the outside, then it will not render correctly.  This can possibly be remedied by getting in closer in such situations, but that’s another exercise.

Creating your own metaball object is fairly straight forward:

local anifrac = 0.95

local balls = {{0,0,0,5}, {0, 1, 19.95*anifrac, 5}}
local isosurface = shape_metaball.new({
balls = balls,
radius = 50,
Threshold = 0.001,

USteps = 15,
WSteps = 15,
})

addshape(isosurface)

You can control a few things here.  First, is the ball network itself.  You can put in as many balls as you want.  Of course, the more balls, the slower the calculations.  It might require quite a few balls to make an interesting structure.  It’s just something to play around with.

Next is the radius.  This value determines the size of the enclosing search space.  It doesn’t have to be hugely accurate, but within an order of magnitude is nice.

The Threshold value determines how tight the calculation is.  0.001 is a good starting point.  This will give you a fairly tight surface.  If you go with a larger value, the calculations will be quicker, but your object will beging to look fairly coarse.  An even smaller value, 0.0001, would make for an even tighter fit to the surface, and thus a smoother object.

The last part has to do with how many facets you want to generate.  This completely depends on the size of your model.  Basically, it determines how many stops there are around the circumferance of the sphere.  USteps is how many longitudinal steps, and WSteps is how many latitudinal steps.

When modeling, it’s probably good to go with looser values, that way you can play around quickly.  As you get closer to wanting to generate your final model, you up all the numbers, and go get coffee.

In this final picture, I’ve set the Threshold to 0.00001, the USteps to 360, and the WSteps to 360.  That’s fairly fine detail, and the generated model will be quite large, but very smooth and accurate to the model.

The conslusion of this little exercise?  Metaballs are a very interesting and valuable tool for the 3D modeling of shapes that are not easily described by standard CSG operations.  Banate CAD has a metaball module that have the speed to render models in real-time, and the flexibility to allow you to dial in as much detail as you want.  This makes modeling with metaballs in Banate CAD a relatively painless prospect, which opens up the possibility of much more organic shapes for modeling.  The beamsearch algorithm makes it practical.

---