c++ - Surface creation algorithm using points cloud

I am looking for a realtime algorithm to create a 2D mesh using points. But I am quite confused. It seems that Delaunay triangulation can help me create mesh using point clouds, but Meta-balls seems also useful for isolated points for example. And what about concave shapes ?

I am looking for interesting links, white-papers, code sample, etc...

Here is an example of what I am trying to achieve. As you can see the aim is to create a 2D fluid surface.

In red should be the generated mesh, I tried to reproduce the special condition that could happen like concave shape, isolated points, etc. In black you can see the points used to create the shape.

Thank you.

Answer

You may do what you need in 2 step:

1. 
   

   Clustering: First you can cluster your point. There are many clustering algorithms which will put your points into multiple close-distance group. K-means is one of your options.

   
   


2. 
   

   Convex Hull: Then you can create Convex Hull for each cluster. such as: Gift wrapping algorithm, Quick Hull, Bridge, ...

   
   

There is a trade-off between simplicity and performance issue for named algorithms.

As you run these algorithms in real-time, your case go to performance-intensive category which need some research in order to find best algorithms for your game.