Search code examples
algorithmmeshapproximation

Distribute points on mesh according to density


Given a (possibly open) mesh with a density texture and a number of points I need to distribute these points according to the density on the mesh.

So far I have made up several solutions some of which worked and others did not. One of the algorithms I tried was to have the points being connected by springs and simulate the distribution until equilibrium (or until the solution fits for the users needs). Source Retiling Polygonal Surfaces Unfortunately this is somewhat slow for higher number of points (>2k) so I need a feasible solution for higher numbers.

I already have some ideas but I would like to hear if there are some standard solutions for this. I tried google but the keywords I used (distribution density discrete) only turned up pages that handle with other problems than mine. So I would already be happy if you point me to the right words to search for.


Solution

  • In general, across an arbitrary space with an arbitrary density function, you could get a reasonable approximation via rejection sampling.

    • Find your maximum density D.
    • Pick a random point p.
    • Pick a random number r from the range [0,D).
    • If the density at p is greater than r, accept p as one of your points.

    I'm not sure how easy this will be to apply to your case. Generating random, uniformly distributed points across a mesh sounds like a tricky problem in itself. The only solution I can think of is to calculate the area of every triangle in your mesh, randomly pick a triangle with probability proportional to its area, and pick a random point within the triangle. I believe you could do this selection in O(logN) on N triangles.

    But considering that you might be throwing most of these points away, this could turn out much worse than your current approach, given a large enough mesh and an unpleasant enough density function (i.e. one with a maximum much greater than the average).


    Like any kind of random sampling, it takes quite a few points before it will start to resemble the underlying distribution; a small set of points will probably look more or less random. But you might be able to get around this with some kind of quasi-random method of point placement (and even with a large set, it might give better results).

    One thing which comes to mind is a hybrid of the above approach and @BlackBear's algorithm. You could calculate the area and average density for each triangle, and use this to decide how many points each one must contain. Then, to actually place the points within the triangle, use the rejection sampling method.