Archived

This topic is now archived and is closed to further replies.

deryk

theory behind metaballs?

Recommended Posts

while waiting for a response to my metaball help post in another forum, i thought i''d confirm my ideas regarding the theories behind metaball construction. so, can anyone explain to me the theory behind their construction? in English please, heheh. a lot of other tutorials out there explain things a little too deep. i''d really like to learn the concept from the ground up so i can create my own implementation of the algorithm, since a lot of the sample programs out there are pretty complex without gaining a very firm grasp of the concept. thanks! i''m gonna use these concepts to create a liquid metal type demo.

Share this post


Link to post
Share on other sites
Didn´t read the links posted by the others but since you said that most tutorial are too much into detail i´ll give you a short summary of the marching cubes algorithm (what I think is what you are talking about):

what you want to do is displaying a certain isolevel r0 of a function r = f(x,y,z). This function should have a first derivative. In the case of metaballs the function will be something like the potential of a number of mass-points but it can be any other function (there are a lot of nice objects shown on Paul Bourkes homepage).

To display the isolevel (which should be a surface) you split up an area that you know to contain the whole isolevel into several uniform geometric objects. Easiest thing to explain here is splitting it up into cubes. Then, for each frame you check each cube:

A cube has 8 edges. For each edge n you check if rn = f(xn, yn, zn) is bigger or smaller than r0. Since each value can be bigger or smaller than r0 (2 possibilities, neglegt equality here) and there are 2^8 = 256 possible combinations that can occur. All values above/below r0 is trivial. Every other case indicates that your cube is intersected by the surface.
In this case you draw triangles accordingly.
This point will propably be where the articles go into detail so I´ll skip this here. I´ll just say that the triangles vertices are usually determined by using linear interpolation between the edges because it´s the fastest way of doing so.

If you got any special questions about the marching cubes feel free to ask, I like talking about that topic

Share this post


Link to post
Share on other sites
okay guys, i''ve done some research. let''s start with creating just a basic sphere using an equation.

apparently, according to http://www.dev-gallery.com/programming/opengl/water_drops/main.htm, the formula for creating a perfect isosurface sphere is:

F(x,y,z) = x^2 + y^2 + z^2 + C.

now, my question is, how do i implement this formula in an openGL program? first of all, is the formula correct?

if i create a function containing the above formula, returning its result to a drawing function defined later on, what does it return? a vertex(meaning i have to loop over and over again), or complete sphere? what i''m trying to do is generate a complete sphere model only, using the above formula. if i can get this to run first, then i''ll get on with the physics involved later.

as you can see, i''m not very much of a math wiz. in fact, it''s one of my weaker areas. but i love the graphics, so i''m willing to learn.

thanks everybody.

Share this post


Link to post
Share on other sites
I dont know much about OGL, but I know all about meta-objects and such, so I think I can help a little. What that formula tells you (your formula is correct) is whether point A is inside or outside of the surface. With OpenGL, I assume, you work with mesh structures..? So what you need to do is scan the volume (march through your cubes) and determine which discrete lattice points are on the surface (or very nearly on). After you march through your cubes, you will have a set of points that are on the surface. These points must be correctly connected. In reality, you will not produce points one by one, but faces of the object one by one. This is about where the tutorials can take over...

This is the basic idea; the tutorials do a much better job of explaining how to actually produce the faces than I can right now.

Share this post


Link to post
Share on other sites
so it''s not possible to just create a sphere via that formula?

plus i have the problem of the searching algorithm too(marching through the cubes), so i''m trying to start with basic generation of the sphere first.

can anyone tell me how to do that?

sorry, but dumb-ass math guy here..

Share this post


Link to post
Share on other sites
No offense, but you can''t just shove OGL a formula of a sphere and expect it to draw a sphere for you.
OGL expects triangles, (or quads?) so you have to create triangles to _represent_ a sphere.

kind rgds,
Nik

Share this post


Link to post
Share on other sites
yup i know

...which is why i''m asking for help on how to represent the sphere. from the research i do while waiting for responses here, i know that surfaces are generated after determining which points on a 3-dimensional grid of cubes are inside and outside a figure, thus formed by trianges and/or quads.

what bugs me though is how to tell GL, for example, that a sphere occupies this many cubes, since i have to know which vertices are inside or outside a sphere, and from there, connected the vertices on the outside to produce a surface.

as vanillacoke said, i currently have the formula to tell whether a point is inside a figure or not. my question for now is, how do i implement the formula? from where do i get the x, y, and z parameters that go in function F(x,y,z)?

thanks for the replies everyone.

Share this post


Link to post
Share on other sites
ok so that''s used to determine if a point on the grid is within the figure or not? once my function F(x,y,z) = x^2 + y^2 + z^2 + C yields a value, how do i use it to determine its being on out of or in the figure?

Share this post


Link to post
Share on other sites
i think i got a start right here
using Nik02's formula, i tried using some random stuff i found from various metaball resources. using the code below, with CalculatePoints returning the value of x^2 + Y^2 + Z^2 + C (i just made C zero) to InOutVal, i managed to generate all the vertices of a mesh of cubes. although i have no idea how InOutVal being greater than 1 affects the point generation. i just read it somewhere.

for (x=0; x < GRIDROOT; x++)

for (y=0; y < GRIDROOT; y++)

for (z=0; z < GRIDROOT; z++)

{ CalculatePoints(x, y, z);

if(InOutVal > 1)

glBegin(GL_POINTS);

glVertex3f(x, y, z);

glEnd();
}

now from this, can anyone get me started on drawing a simple figure like a cube, or a sphere?

thanks you guys. learning a lot from all of you.

[edited by - deryk on July 28, 2003 3:42:44 AM]

[edited by - deryk on July 28, 2003 3:43:46 AM]

Share this post


Link to post
Share on other sites
You basically need to insert geometry to cells which are on a given treshold value (though the treshold check should be per vertex on the cell). The treshold is defined as 'what energy level is the border of in/outside', and is up to you for decide.

EDIT: And you seem to have realized that, the InOut value in your code looks like the energy/influence value, and treshold is defined as 1.

[edited by - Nik02 on July 28, 2003 3:54:25 AM]

Share this post


Link to post
Share on other sites
Yes, generate surface geometry on the cells where the treshold is crossed. You got it! Now, adding more than one sphere is trivial, just calculate their combined influence and compare _it_ to the treshold.

EDIT: Read the tuts again, they'll make much more sense now

[edited by - Nik02 on July 28, 2003 4:02:13 AM]

Share this post


Link to post
Share on other sites
hey thanks Nik02!

i''m gonna experiment with defining threshold constants for a while.. and see what i can come up with. i''ll report right back here soon. thanks heheh.

Share this post


Link to post
Share on other sites
hello again!

i did what Nik02 said and reread the tut over at exaflop.org. i really do understand it better now, but i have one more question from reading it over again. their basic implementation of the algorithm states to compare point with a shape, and test whether the vertices of the cubes in the cube grid are inside or outside the bounds, or, threshold(i assume?) of the shape you wish to approximate.

if that''s the case, then from where to i get this sample shape to compare my cube grid''s vertices with?

and, using my F(x,y,z) = x^2 + Y^2 + Z^2 + C function, how do i compare the result of that with the points on the sample shape to determine the "in"-ness or "out"-ness of the cube vertices?

thanks again! just a little more to go...

Share this post


Link to post
Share on other sites
you got that right man.

this is my first time to venture into something like this. all my past graphics ventures have been strictly manual programming of shapes and all that stuff. it's led me to some good figures, but only after hours upon hours upon hours of long hard work.

EDIT:
the problem i think here is that the modelling paradigm is very different, which is why i'm seeing the sphere shape i'm trying to make as one that is programmed like quads or triangles

[edited by - deryk on July 28, 2003 4:32:31 AM]

Share this post


Link to post
Share on other sites
The paradigm may be different to all others, but why should that stop you?
In all your ventures, don''t be put off by how difficult something looks. Just research it, and someday it''ll make sense.

Glad i could help!

Nik

Share this post


Link to post
Share on other sites
ok here''s how my program looks so far. i''ve tried to define a threshold of .65 (just some random small value).


for (x=0; x < GRIDROOT ; x++)
for (y=0; y < GRIDROOT ; y++)
for (z=0; z < GRIDROOT ; z++)
{ CalculatePoints(x, y, z);
if(InOutVal == THRESHOLD)

glBegin(GL_POINTS);
glVertex3f(x, y, z);
glEnd();
}

now, as i''ve said, CalculatePoints subjects the x, y, and z values to the formula F(x,y,z) = x^2 + y^2 + z^2 + C (but i just make C be zero). that function then assigns the final value of the formula to InOutVal. just to clarify, what, then, is InOutVal exactly?

i read at a resource that the surface of an object is generated when the "strength matches the threshold exactly." i know i''m missing something from this code, but still not sure what it is. is InOutVal the strength that i''m supposed to be comparing THRESHOLD with? if not, then, what is?

thanks AGAIN and AGAIN.

Share this post


Link to post
Share on other sites
Yes, the InOutVal seems to be the influence on any given point.
I also guess that CalculatePoints routine sums the sphere''s influences to that variable.
By all means, see CalculatePoint''s source!
If these assumptions are correct, then the surface _is_ found on treshold of the influence field. Therefore, you are correct!

Now, off to work... see ya in the forums

Share this post


Link to post
Share on other sites
this is my CalculatePoints() function. all it does is take each x, y, and z point and compute for, according to geisswerks.com, the strength of the electric field due to a point
charge at the origin.

void CalculatePoints(float x, float y, float z)
{
InOutVal = 1.0/(pow(x,2) + pow(y,2) + pow(z,2));
}

all i get with my current program is a blank screen, when i use this formula.

Share this post


Link to post
Share on other sites
Ouch.

Never ever ever use pow(n, 2). Or 3, or 4, or any whole number for that matter. Just use x*x. You WILL notice a serious speed increase when you avoid the pow() function.

That said, there are a few concerns when implementing metaballs (I just implemented an adaptive marching cubes algorithm in about an hour). Most of them depend on your implementation method, but here''s a quick list of things to look at.

1. Proper storage. A sphere of influence in a metaball should have a center, a power, and a radius of influence. The radius of influence is used as a quick and dirty bounding sphere, and believe me, the performance difference is worth it.

2. Proper summation of charges. Only sum charges of spheres which are closer than effective_radius from the current cube''s center. Also, sum them using the formula point_influence = (power of point) * (1-(distance / effective_radius)^2)^2. I tried several other formulas and got odd/no results until I picked up that one from the POVRay documentation (which is where I first learned of metaballs).

3. Proper construction of polygons. I was lazy and used a voxel-based method in my approach, so I can''t help you here. However, I do know that it is very easy to misconstruct the polygons and vertices in a marching cubes algorithm.

4. Proper threshold. Your metaball has a surface whenever the sum of all influences is equal to some threshold. Changing this threshold will control the look -- and sometimes the existence -- of the metaball itself.


Finally, make sure you only have one point charge at the origin with an influence of 1.0, a radius of 1.0, and a threshold of 0.5. See how that works.

Share this post


Link to post
Share on other sites
deryk:
The sample code you presented is quite close to what you are trying to do yet quite far from what the marching cubes do:
Generally it would give give you the correct result if your steps (which are 1 by now) were infinitely small. in the case of finite steps you cannot expect to hit all points on your isosurface. As a first try (to get something on the screen at all) you could replace "if(InOutVal == THRESHOLD)" by "if(InOutVal > THRESHOLD)". This would give you all points that are inside your sphere (oh, and let the coordinates range from -max to +max not from 0 to max to get the whole sphere).

To get all points on the surface of your sphere you take points that lay next to each other. If the value of one of these points is bigger than your THRESHOLD while the other value is smaller you assume that a point (x,y,z) with CalculatePoints(x,y,z)=THRESHOLD lies inbetween these points. This point is usually determined by linear interpolation (it´s the fastest and -what might be even more important- easiest method of doing so).

One important thing that might not be obvious to you: It is not possible do determine all the points that fir your condition f(x,y,z) = THRESHOLD since it´s an infinite number of them. So instead of calculating them all you calculate a few of them and draw polygons (triangles) between them. This is where the marching cubes come in but maybe it´s best for you to try finding a few correct points first before proceeding to this.


[edited by - Atheist on July 28, 2003 11:00:41 AM]

Share this post


Link to post
Share on other sites