1
\$\begingroup\$

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.

example

Thank you.

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ In the question you ask for a mesh, yet you provide image of convex hull. Can you clarify? \$\endgroup\$
    – wondra
    Aug 5, 2014 at 9:46
  • \$\begingroup\$ The aim is to provide a mesh like this example. But I need to care about isolated points and concave shapes. \$\endgroup\$
    – MaT
    Aug 5, 2014 at 9:58
  • \$\begingroup\$ What is the source and density of this point cloud? What minimum hardware do you want to target? Is this just visual or will objects in 3d/2d space interact with the volume? Can't discuss "real time" without constraints =) Some fluid surface simulations dispense entirely with building points and just go straight from integrating the math underneath to building the mesh for display, for example. \$\endgroup\$
    – Patrick Hughes
    Oct 4, 2014 at 19:43
  • \$\begingroup\$ The aim is to provide a fluid simulation using the points and then construct the surface profile like in 2D using an algorithm. Let's be crazy and target some high end Mobile devices. There will be objects interacting with the point cloud but the mesh generated won't be interactive. It's just to see the slice of the volume, it's only a simple 2D mesh. \$\endgroup\$
    – MaT
    Oct 6, 2014 at 7:07

2 Answers 2

Reset to default
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Thank you for your answer ! Do you have some algorithm reference in mind ? As this needs to be computed in realtime. \$\endgroup\$
    – MaT
    Nov 3, 2014 at 14:16
  • \$\begingroup\$ @MaT I've edited my answer. \$\endgroup\$
    – Emadpres
    Nov 3, 2014 at 14:28
  • \$\begingroup\$ Thank you very much @EMAdpres ! This gives me a huge step concerning my development. \$\endgroup\$
    – MaT
    Nov 3, 2014 at 14:38
  • \$\begingroup\$ @MaT My Pleasure :) \$\endgroup\$
    – Emadpres
    Nov 3, 2014 at 14:49
0
\$\begingroup\$

Metaballs is a good way to think about solving this problem. It's usually the way that people develop implicit surfaces using particle-based fluid simulation like Smoothed Particle Hydrodynamics. There have already been a few questions asked about how to render metaballs:

How to render metaballs?

2D metaball liquid effect - how to feed output of one rendering pass as input to another shader

2d metaballs with shader to give blobs of water effect?

In order to actually generate the implicit surface of the water, there is a very good GPU Gems 3 chapter on the subject:

Point-Based Visualization of Metaballs on a GPU

Improve this answer
\$\endgroup\$

You must log in to answer this question.

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