Metaballs with Marching cubes

Started by
12 comments, last by unbird 10 years, 8 months ago

Hi everyone. I have implemented the marching cubes algorithm and I am trying to render metaballs.

The problem I have is no matter how many metaballs I define, it will always only draw 1, so I guess my question is how to properly integrate the metaballs data with marching cubes.

Each metaball has a position and radius and then stored in a vector container.

Then in my volume function for marching cubes I have this:


 for(i=0; i<m_volume_depth; ++i)
    {
        for(j=0; j<m_volume_height; ++j)
        {

            for(k=0; k<m_volume_width; ++k)
            {
                float x = (float)i/(m_volume_depth) - 0.5; 
                float y = (float)k/(m_volume_width) - 0.5;
                float z = (float)j/(m_volume_height) - 0.5;


                Vec3 p = Vec3(x,y,z);
                m_volumeData[i*m_volume_width*m_volume_height + j*m_volume_width + k] = meta(p);
            }
        }
    }


Then here is the meta function:


 float sum=0;

    for(int x=0; x<m_metaBalls.size(); ++x)
    {
    
        sum +=  m_metaBalls.at(x)->equation_sphere(_pos);
    }

 return sum;

Here is my equation code:


 return ( (_pos.m_x - m_position.m_x)*(_pos.m_x - m_position.m_x)
             + (_pos.m_y - m_position.m_y)*(_pos.m_y - m_position.m_y)
             + (_pos.m_z - m_position.m_z)*(_pos.m_z - m_position.m_z)
             - m_radius*m_radius);

_pos is the passed in position;

m_position is the origin of the metaball;

I don't think there is anything wrong with the metaball class becuase it draws a sphere perfectly but only 1.

How would you integrate the metaball data with marching cubes?

If you require any other parts of the code then please let me know, this has been driving me crazy for a while.

Advertisement

If you are not using marching cubes already how exactly are you rendering the data in m_volumeData at all? You said it draws 1 sphere so it must be drawing something with some type of algorithm. There is a good chance you reinvented a marching cubes type algorithm without realizing it. Obviously there is a bug but from what I've seen so far it's likely an implementation bug not a conceptual one...you appear to have the right idea.

Marching cubes is really simply. The basic premise is that you chop your volume up into voxles and evaluate your potential function at each corner of every voxel. By computing where along a voxel edge you transition form being inside the isosurface (also called the level-set or isocountour) to being outside the isosurface geometry can be generated that approximates the boundary.

Here's a good place to start: http://paulbourke.net/geometry/polygonise/ which also covers a slightly simpler and more aesthetically pleasing variant: Marching Tetrahedrons.

If you are not using marching cubes already how exactly are you rendering the data in m_volumeData at all? You said it draws 1 sphere so it must be drawing something with some type of algorithm. There is a good chance you reinvented a marching cubes type algorithm without realizing it. Obviously there is a bug but from what I've seen so far it's likely an implementation bug not a conceptual one...you appear to have the right idea.

Marching cubes is really simply. The basic premise is that you chop your volume up into voxles and evaluate your potential function at each corner of every voxel. By computing where along a voxel edge you transition form being inside the isosurface (also called the level-set or isocountour) to being outside the isosurface geometry can be generated that approximates the boundary.

Here's a good place to start: http://paulbourke.net/geometry/polygonise/ which also covers a slightly simpler and more aesthetically pleasing variant: Marching Tetrahedrons.

I have marching cubes already implemented and thats how its drawing 1 sphere from the equation.

I dunno how to explain this but basically how would I pass the metaball data to draw multiple spheres instead of just 1.

The marching cubes algorithm works and my equations work.

For example if I just passed the equation of a circle to my volume data

m_volumeData[i*m_volume_width*m_volume_height + j*m_volume_width + k] = x*x + y*y +z*z - r*r

It draws a sphere perfectly, Im just unsure how would I pass multiple spheres to m_volumeData.

I dunno how to explain this but basically how would I pass the metaball data to draw multiple spheres instead of just 1.

The marching cubes algorithm works and my equations work.

For example if I just passed the equation of a circle to my volume data

m_volumeData[i*m_volume_width*m_volume_height + j*m_volume_width + k] = x*x + y*y +z*z - r*r

You just add more point sources of potential which you appear to be doing with this bit of code:


 float sum=0;

    for(int x=0; x<m_metaBalls.size(); ++x)
    {
    
        sum +=  m_metaBalls.at(x)->equation_sphere(_pos);
    }

 return sum;

Adding more balls at different locations should give you a blobby topology, if you have two balls at the same location you should end up with a sphere that's the sum of the radii. Double check you meta(p) function to verify that it is iterating over all the items in m_metaBalls and returning a sum of all the potential functions. If that's in order perhaps you can post some more code or explain what happens when you add items to m_metaBalls.

Unless I've misunderstood your code, there's something wrong with your potential function. It should go to zero as you go further away from the sphere's center, and reach zero at some distance, not be negative inside the sphere and then tend to infinity, otherwise it will be really hard for a sphere to interact with the potential field of another (since the "most negative" value is negative radius squared, whereas far away from the first sphere your potential becomes arbitrarily large).

The basic "metaball" potential function is 1 / (distance to center squared). There are faster/smoother approximations out there, check out http://en.wikipedia.org/wiki/Metaball.

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

According to my pen and paper Bacterius is correct. This is actually very interesting, it never occurred to me that you could pick a simple monotonically increasing potential function that could result in such an intractable field given multiple sources.

This bit of code:


 return ( (_pos.m_x - m_position.m_x)*(_pos.m_x - m_position.m_x)
             + (_pos.m_y - m_position.m_y)*(_pos.m_y - m_position.m_y)
             + (_pos.m_z - m_position.m_z)*(_pos.m_z - m_position.m_z)
             - m_radius*m_radius);

Should be something like this:


float delX  = pos.m_x - m_position.m_x;
float delY  = pos.m_y - m_position.m_y;
float delZ  = pos.m_z - m_position.m_z;
return (m_radius*m_radius) / (delX*delX + delY*delY + delZ*delZ);

?

And you will want to tweak your Marching Cube code such that you tessellate the isocontour at meta(p) = 1 instead of meta(p) = 0. This is a rather naïve potential and has a singularity but it will get the job done. The Wikipedia link Bacterius specified will point you toward a number of better choices.

Thanks guys got it working :) Although I have a couple of queries

Screenshot.png

After changing the equation, I had to reduce the iso value quite alot to 0.008 is it normal to be that low?

Also I can only specify metaball positions between 0 -> 1 anything outside doesn't get drawn and I want to be able to draw them anywhere on screen, Im not sure which part of the algorithm decides the range?

Finally just a general question, eventually I wanted to use this to render fluid. Some people seem to use marching cubes to render fluid, however It took my app like 4seconds just to render those four static metaballs. What kind of technique is good for fluid rendering?

Thanks for the help guys.


After changing the equation, I had to reduce the iso value quite alot to 0.008 is it normal to be that low?

The isovalue really tells you where the limit between solid regions and empty space (the "contour") is to be located. If it is too high or too low, everything will be considered solid or empty, and as you vary it more (or less) of the density field is considered solid, which leads to interesting results. I don't think there is really any "good" value for an isovalue, it depends a lot on your metaball implementation and on the effect you want to achieve, so I wouldn't be worried if you need to tweak it a bit to get good-looking metaballs.


Also I can only specify metaball positions between 0 -> 1 anything outside doesn't get drawn and I want to be able to draw them anywhere on screen, Im not sure which part of the algorithm decides the range?

This shouldn't be a problem with the metaball algorithm itself. I would check your marching cubes code to verify it is working outside the 0..1 unit cube. If it isn't, then obviously everything outside it will never be polygonized, and therefore never rendered. It's not possible to polygonize things arbitrarily far away, unfortunately, there is always a tradeoff between range and resolution, because marching cubes is a discrete algorithm. Other methods like ray marching can sort of scale to arbitrary distances, but have their own set of drawbacks.

To make sure your balls can move around, you can compute the bounding box of your metaballs and use that to define the range for the marching cubes algorithm, but you can't have them go too far away from one another else you will lose in accuracy. You might wonder why, since in that case the marching cubes algorithm would spend most of its time on empty voxels, and, yes, it is possible to do better, but it gets rather nasty as you then need to find an approximate bounding box for every set of connected metaballs and run the marching cubes algorithm on each of them, separately, which sounds great on paper but isn't that efficient in practice. I think most people deal with this by making reasonable tradeoffs between the size of their worlds and how precise the polygonization should be.


Finally just a general question, eventually I wanted to use this to render fluid. Some people seem to use marching cubes to render fluid, however It took my app like 4seconds just to render those four static metaballs. What kind of technique is good for fluid rendering?

Marching cubes can be rather expensive, especially if you want really good resolution. Looking at your screenshot, your mesh is quite smooth, meaning it's probably trying to polygonize up to 128x128x128 voxels, which is *a lot* especially done on the CPU. If you wanted to go interactive - it is possible - you would move the marching cubes code to the GPU, in a shader, and perhaps scale back the resolution a notch. It isn't too hard at all, in fact, and the speed boost is huge since doing the same calculation over a lot of different locations is what the graphics card does best. Then you can add lots of algorithmic optimizations to avoid calculating every single sphere's potential for each voxel - which obviously won't do when you start rendering dozens of metaballs - by using techniques like octrees or spatial hashing. It can get rather efficient, really, but it has its limits. As we all know, the really cool stuff is done by cleverly combining different techniques smile.png

I don't know if metaballs would be my first choice for fluid rendering, though. It stills seems like an inefficient method overall, I would just use a grid-based fluid dynamics system if I wanted to do it properly (though a fractal heightmap or even FFT water works well for static water bodies). Marching cubes itself sounds good to display the results, however. Remember to dissociate what you are rendering (metaballs) from how you are rendering it (marching cubes), the two have nothing in common except being often used together.

... great, now I want to write a metaball renderer tongue.png

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”


After changing the equation, I had to reduce the iso value quite alot to 0.008 is it normal to be that low?

The isovalue really tells you where the limit between solid regions and empty space (the "contour") is to be located. If it is too high or too low, everything will be considered solid or empty, and as you vary it more (or less) of the density field is considered solid, which leads to interesting results. I don't think there is really any "good" value for an isovalue, it depends a lot on your metaball implementation and on the effect you want to achieve, so I wouldn't be worried if you need to tweak it a bit to get good-looking metaballs.


Also I can only specify metaball positions between 0 -> 1 anything outside doesn't get drawn and I want to be able to draw them anywhere on screen, Im not sure which part of the algorithm decides the range?

This shouldn't be a problem with the metaball algorithm itself. I would check your marching cubes code to verify it is working outside the 0..1 unit cube. If it isn't, then obviously everything outside it will never be polygonized, and therefore never rendered. It's not possible to polygonize things arbitrarily far away, unfortunately, there is always a tradeoff between range and resolution, because marching cubes is a discrete algorithm. Other methods like ray marching can sort of scale to arbitrary distances, but have their own set of drawbacks.

To make sure your balls can move around, you can compute the bounding box of your metaballs and use that to define the range for the marching cubes algorithm, but you can't have them go too far away from one another else you will lose in accuracy. You might wonder why, since in that case the marching cubes algorithm would spend most of its time on empty voxels, and, yes, it is possible to do better, but it gets rather nasty as you then need to find an approximate bounding box for every set of connected metaballs and run the marching cubes algorithm on each of them, separately, which sounds great on paper but isn't that efficient in practice. I think most people deal with this by making reasonable tradeoffs between the size of their worlds and how precise the polygonization should be.


Finally just a general question, eventually I wanted to use this to render fluid. Some people seem to use marching cubes to render fluid, however It took my app like 4seconds just to render those four static metaballs. What kind of technique is good for fluid rendering?

Marching cubes can be rather expensive, especially if you want really good resolution. Looking at your screenshot, your mesh is quite smooth, meaning it's probably trying to polygonize up to 128x128x128 voxels, which is *a lot* especially done on the CPU. If you wanted to go interactive - it is possible - you would move the marching cubes code to the GPU, in a shader, and perhaps scale back the resolution a notch. It isn't too hard at all, in fact, and the speed boost is huge since doing the same calculation over a lot of different locations is what the graphics card does best. Then you can add lots of algorithmic optimizations to avoid calculating every single sphere's potential for each voxel - which obviously won't do when you start rendering dozens of metaballs - by using techniques like octrees or spatial hashing. It can get rather efficient, really, but it has its limits. As we all know, the really cool stuff is done by cleverly combining different techniques smile.png

I don't know if metaballs would be my first choice for fluid rendering, though. It stills seems like an inefficient method overall, I would just use a grid-based fluid dynamics system if I wanted to do it properly (though a fractal heightmap or even FFT water works well for static water bodies). Marching cubes itself sounds good to display the results, however. Remember to dissociate what you are rendering (metaballs) from how you are rendering it (marching cubes), the two have nothing in common except being often used together.

... great, now I want to write a metaball renderer tongue.png

Haha you should write one then you can help me make mine better :)

Anyway I have been messing about with it for a while but still cannot draw outside the 0->1 range. I found this source online

https://github.com/kamend/3D-Metaballs-with-Marching-Cubes/tree/master/src (Note its not mine) to try and see how they control range and I see it uses gridX gridY gridZ which is basically the same thing as my m_volume_depth etc...

Can anyone have a look through that source and see which bit alters range so I can draw more than a unit cube.

Thanks

[snip]

Haha you should write one then you can help me make mine better smile.png

Anyway I have been messing about with it for a while but still cannot draw outside the 0->1 range. I found this source online

https://github.com/kamend/3D-Metaballs-with-Marching-Cubes/tree/master/src (Note its not mine) to try and see how they control range and I see it uses gridX gridY gridZ which is basically the same thing as my m_volume_depth etc...

Can anyone have a look through that source and see which bit alters range so I can draw more than a unit cube.

Thanks

Well I don't have time to look into it right now (gotta go in five minutes) but reading your original post's code again, you are normalizing your i, j, k counters so that they always fall in (-0.5 .. 0.5), and are always evaluating the metaballs there (so increasing volume_width and so on only increases resolution but not range). A quick fix is to keep the code the same, but multiply your x, y, z values by some factor like "scale". Then scale = 2 would render in (-1.. 1), scale = 4 between (-2..2) and so on. Try it and see if that works.

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

This topic is closed to new replies.

Advertisement