• Advertisement

Archived

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

Realtime Slime

This topic is 5503 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been toying with a method for creating real-time metaballs recently. There is a Gamasutra article which uses marching cubes to step through an energy field and determine the threshold surface; my approach creates a mesh for each sphere and deforms them based on attraction to each-other with an exponential fall-off function (which the Gamasutra article used too if I'm not mistaken). I did a search on our friendly neighborhood Google and didn't come up with many programming resources (there were alot of 3dsMax turtorials); the only thing I found was the Gamasutra article, so I was wondering is this method new? I've become kind of cynical lately so I have a hard time believing this; I suspect (A) the information is well hidden, (B) there's a good reason people don't use my method, or (C) metaballs are considered too processor-intensive for games so my method was never considered. Which do you think it is; if you've written code to create metaballs, what algorithm did you use? Just in case you're not familiar with metaballs, they're sphere's that "grow" together (a film begins to fill the space between them) as they are brought into proximity with one another. [edited by - bob_the_third on January 29, 2003 12:19:14 AM]

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
nah, metaballs have been used for ages in demos. if i remember correctly, since 96/97.. so it cannot be too cpu intensive.. i''ve never seen them in games tho.. there is plenty of info on the net. even full sourcecodes. especially on the marchingcubes algo, since this is quite old, but also on the metaball field itself (tho i discovered the info isn''t always accurate!).

i recommend some more googling.

however, i don''t think i use your method.. basicly i add the fields of each sphere, add those.. and then i use marchingcubes.
which to me sounds like a more simple way of doing it?

earx

Share this post


Link to post
Share on other sites
I think the advantages of mine are speed and flexibility. It iterates through a vertex list instead of a 2D or 3D space, so you don''t have those granularity problems (especially if you use adaptative subdivision) and you can create groups of influence so that, for example, the ear would be a group and it wouldn''t be deformed at all by any other part of the body except at the point(s) where it attaches to the head. This allows for both an optimization and a modeling advantage.

Share this post


Link to post
Share on other sites
Can you give any screenshots of this working. And a bit more detailed description would be welcome.

You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites
I'll try to get some screenshots posted somewhere (do you know of a free hosting service I could use; Homestead went pay.). A more detailed description follows:


Without diagrams this is tough to explain; let's see.

Each metaball is made up of an inner and an outer circle. The radius of the outer circle is equal to the (1+GOO_FACTOR) times the radius of the inner_circle. An algorithm in pseudo-code follows:


For each metaball M
For each vertex V in M.outer_circle do
D=f(GOO_FACTOR), where GOO_FACTOR determines the metaballs' affinity to eachother (0,+infinity)
For each metaball N such that M<>N do
let d=distance(V,N.center)-N.inner_radius
D=D+f(d), where f(x) is the weighting function
End For

let w=f(d1)/D, where w is the weight used in the interpolation.


x=w*M.inner_circle.x
y=w*M.inner_circle.y

For each metaball N such that M<>N do
let d2=distance(V,N.center)-N.inner_radius
w=f(d2)/D
let p2 be a vector equal to N.center+unit_vector(V-N.center)*N.inner_radius
x=x+w*p2.x
y=y+w*p2.y
End for

plot x, y
End for
End for


Note that this pseudo-code does not take into account some artifacts such as the special case when outer circle point is within the outer circle of a metaball; however I didn't feel like typing that much. I'll save that for an article if there's any interest.

[edited by - bob_the_third on January 23, 2003 4:01:08 PM]

Share this post


Link to post
Share on other sites
when ever you have some image or smaller file to post, go to http://davepermen.net click on free and upload there, then copy the link in here..

this was a shameless plug (and don''t tell me i don''t update anymore. i''m currently less at home than sleeping, okay?:D)

"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites
Thanks davepermen! That's awesome.

Okay, I've got screenshots now. Maybe this will make more sense!


Above is a screenshot of my current 2D metaball demo. It's not totally finished; I'm going to remove all the inside stuff and leave only the outer surface eventually.


Okay the diagram above should clear up some details of my algorithm.

1. Take any one of the red dots.
2. Find the distance between the red dot and the inner circle of each of the other undeformed metaballs.
3. Generate a weight for each metaball using the function (1.1^d)/D where d are the distances we just calculated, and D is the sum over all metaballs.
4. Now using the weight for each metaball and the corresponding BLUE point on the inner circle, interpolate to find the coordinates for the vertex in the metaball mesh after deformation.

As you can see from the diagram, the smaller the difference between the outer radius and the inner radius of a metaball, the greater the influence that metaball has on its own vertices and the less affinity metaballs will have toward each other; the greater the difference, the higher the affinity.

[edited by - bob_the_third on January 24, 2003 12:06:39 PM]

Share this post


Link to post
Share on other sites

AFAICS your method does not produce "real" metaballs. When you use marching cubes, you get a continous surface. Your algorithm produces three surfaces so there will be a crease where they intersect.

Share this post


Link to post
Share on other sites
Should be able to smooth the seams if necessary; however I think they look pretty good as is even if they''re not pure metaballs.

Share this post


Link to post
Share on other sites

Yeah, I was just suggesting a reason for why people haven''t used your algorithm instead of marching cubes. Anyways, metaballs are real cool, I look forward to seeing your implementation ! I haven''t really done much myself except played around with some source-code I downloaded.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Search on "implicit surfaces" for more information than you want.

Marching cubes computes a polygonal approximation to an implicit surface (i.e., an isovalue of a scalar field). Your method deforms independent polyhedra, the *union* of which (assuming your method works) gives that approximation (for the scalar field resulting from the summation of the field functions associated with each particle/sphere). The union operation here is performed by depth testing which can cause problems, e.g., the degenerate case of two co-incident spheres results in worst-case z-fighting.

Your method is O(N^2) for N "metaballs" and also scales linearly with the number of vertices used for each metaball. Marching cubes is linear in the number of grid nodes and screamingly fast in practice due to lookup-tables. Scan-converting metaballs to a grid is, of course, linear in the number of metaballs.

So, yes, there are good reasons people don''t use your method: marching cubes is more general, faster, and topologically correct.

Don''t be discouraged, though, there''s been over 15 years of research on this stuff.

Share this post


Link to post
Share on other sites
Thanks for the constructive criticism. I''m not discouraged because I think it''s cool and that''s all that really counts.

Just a minor clarification (is it possible to write sentences like this with it sounding snide or sarcastic?! I''m really not trying to...): when used in character modeling, for example, you aren''t going to have every metaball influence every other metaball, because you aren''t going to want the character''s earlobes and toes stretching toward each other. Granted they''re too far apart to matter anyway, but the general idea is to make self-contained metaball groups, like a finger for example, where the metaballs in that group are influenced by eachother but not by any of the other metaballs in the model except for few metaballs that are designated as "join sites," e.g. the finger joint that attaches to the hand. This allows the computations to be lessened and provides a more controlable modeling experience. The resulting run-time is O(kV) where V is the total number of vertices in the model and k is the average number of metaballs in a group.

Of course this still scales up linearly as you increase the number of vertices. But it should provide great control. For example, you could use the system to build volume-correct bones, connect those with tendons (or is it ligaments?), then build muscles and attach them to the bones with ligaments/tendons, and then either skin the whole thing, or simply allow the muscles to blend with eachother which would result in a skin. The bones would be created at design time and the muscles would deform and the skin would blend in real time; the connection sites for ligaments/tendons would be assigned to bone vertices in the modeler. You could also have fat by creating a 3D spring mesh and attaching massy metaballs to it. Most of the metaballs in this implementation wouldn''t be rendered; their vertices would be calculated and used to render the top layer, i.e. the skin unless there''s a compound fracture. I imagine this would be processor heavy, but it would also be awesome. Anyway, this is my vision. Don''t know if I''ll ever actually code a demo, but I want to.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Been done. Check out "blobtree" and other implicit surface modeling techniques.

Share this post


Link to post
Share on other sites
I did a Google search on Blobtrees and it looked like it went back to Marching Cubes for polygonization which is what I was trying to avoid in the first place.

Share this post


Link to post
Share on other sites
Marching Cubes is a patented algorithm, and I think that''s why nobody has made commercial use of it.

Share this post


Link to post
Share on other sites
Okay, fair enough. But my point is that I''m trying to find alternatives to marching cubes. Instead of marching through a volume (3D), I want to march across a surface (2D) and deform it based on a reasonable approximation to a metaball field. I''m working on a second approach that should be faster than the first algorithm I posted, but homework comes first.

Have you seen or heard of metaball rendering algorithms that DO NOT use marching cubes (or any similar algorithm)?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Blobtrees are a method for modelling implicit surfaces. You can polygonize them any way you want. You were talking about grouping metaballs to limit their influence; blobtrees are a generalization of this idea.

There are many methods of implicit surface polygonization. Search on "implicit surface polygonization" or similar for info.

Share this post


Link to post
Share on other sites

  • Advertisement