12
\$\begingroup\$

I'm new to game/graphics development and I'm playing around with particles (in 2D). I want to draw particles close to each other as a blob, just as liquid/water. I do not want to draw big circles overlapping as the blob won't be smooth (and too big). I don't really know physics but I assume what I want is something looking similar to surface tension.

I haven't been able to find anything on stackexchange or on Google (maybe I do not know the correct keywords?). So far I have found two possible solutions, but I am unable to find any concrete information about algorithms.

One of them is to calculate the concave hull of particles I consider being a blob. I can calculate the blob by creating an equivalence class (on the relation "close to each other"). Strangely enough I haven't been able to find any algorithm explaining how to calculate the concave hull. Many posts (and among stackexchange) links to libraries or commercial products that do this (I need libraries to work in C#), but never any algorithm. Also this solution might have a problem with a circle of particles, which would not detect the empty space in the middle.

While researching concave hull I stumbled upon something called alpha shapes. Which seems to be exactly what I want to do, however just as with concave hull I haven't found any source explaining how they actually work. I have found some presentation materials but not enough to go on. It's like a big secret everyone knows except me :-/

After calculating the concave hull or alpha shape I want to make it a Bézier curve to make it smooth and nice.

Although I do find my approach a bit too complex, maybe I am trying to solve this the wrong way? If you can either suggest any other solution to my problem, or explain the pieces I am missing I would be very happy and grateful :-)

Thanks.

\$\endgroup\$
5
  • \$\begingroup\$ stackoverflow.com/questions/83593/… \$\endgroup\$
    – BlueRaja - Danny Pflughoeft
    Commented Jun 21, 2011 at 19:39
  • \$\begingroup\$ @BlueRaja Thanks for your comment. Although I had already found that post but dismissed it because the answers either links to papers that doesn't directly solve my problem, but their references might or a patent that I cannot use openly (I think, I'm not good with bureaucracy) (I didn't even find the download link anyway). \$\endgroup\$
    – Nömmik
    Commented Jun 21, 2011 at 19:53
  • 1
    \$\begingroup\$ The "marching cubes" patent expired in 2005, most 2D examples are much older and that's why you may have seen them warn you about their use on old web pages. \$\endgroup\$
    – Patrick Hughes
    Commented Jun 21, 2011 at 21:28
  • 1
    \$\begingroup\$ Here's a gamedev article that goes into both metaballs and isosurfaces, with some samples to make the ideas clear: link \$\endgroup\$
    – Patrick Hughes
    Commented Jun 21, 2011 at 21:33
  • \$\begingroup\$ Thanks for enlightening me about metaballs, they seem to do what I want :-) \$\endgroup\$
    – Nömmik
    Commented Jun 21, 2011 at 22:18

3 Answers 3

Reset to default
8
\$\begingroup\$

The keyword you might need is "Metaballs," and ranges from the complex nVidia GPU Gems sample down to the demo scene driven versions designed only to look good and run fast.

\$\endgroup\$
4
  • \$\begingroup\$ Indeed, I didn't know the keyword :-) I will take a closer look at it and if it seems to be what I need, then I will accept your answer. Thanks! \$\endgroup\$
    – Nömmik
    Commented Jun 21, 2011 at 19:55
  • 1
    \$\begingroup\$ +1 for me thinking that was "meatballs" before I read it a second time. \$\endgroup\$
    – James
    Commented Jun 21, 2011 at 23:29
  • 2
    \$\begingroup\$ Could you add a bit more detail to this answer? +1 if you do. \$\endgroup\$
    – AttackingHobo
    Commented Jun 22, 2011 at 1:13
  • \$\begingroup\$ @James I think everyone makes that mistake the first time they see the word! \$\endgroup\$
    – Jeff
    Commented Jun 22, 2011 at 1:28
1
\$\begingroup\$

To convert a group of particles to a mesh to can render, metaballs style, you can take a look at the Marching Cubes algorithm, which generates a polygonal mesh from voxel data. There is a demoscene demo that has a great example of this, with everything generated on the GPU: numb res.

\$\endgroup\$
0
\$\begingroup\$

As mentioned above, you are thinking of Metaballs.

This is a great article on the subject with some basic theory discussion and examples.

Exploring Metaballs and Isosurfaces in 2D

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .