Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
    
@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). –  Nömmik Jun 21 '11 at 19:53
1  
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. –  Patrick Hughes Jun 21 '11 at 21:28
1  
Here's a gamedev article that goes into both metaballs and isosurfaces, with some samples to make the ideas clear: link –  Patrick Hughes Jun 21 '11 at 21:33
    
Thanks for enlightening me about metaballs, they seem to do what I want :-) –  Nömmik Jun 21 '11 at 22:18
add comment

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
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! –  Nömmik Jun 21 '11 at 19:55
1  
+1 for me thinking that was "meatballs" before I read it a second time. –  James Jun 21 '11 at 23:29
2  
Could you add a bit more detail to this answer? +1 if you do. –  AttackingHobo Jun 22 '11 at 1:13
    
@James I think everyone makes that mistake the first time they see the word! –  Jeff Jun 22 '11 at 1:28
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.