# Evenly distribute points on a triangle mesh

## Recommended Posts

Katachi    131
Hi,

I would like to distribute points evenly on a triangle mesh. So all points kind of have a similar distance to each other on the whole mesh (not just inside of a triangle). Another constraint I have is that I would like to define the amount of points used. Of course the faster the algorithm the better.

All links, resources, code are highly appreciated. Also of course opinions are very welcome.

Best
Katachi

##### Share on other sites
Aqua Costa    3691
But what kind of mesh do you want to create?

##### Share on other sites
Katachi    131
Hi,

I don't want to create a mesh, I have an arbitrary triangle mesh already and would like to place points (or samples, whatever you'd like to call it) evenly on its surface.

##### Share on other sites
osmanb    2082
If you only care about populating the surface of the mesh, the approach I'd take is:

[list=1][*]Compute the area of each triangle in the mesh, sum them to get the complete surface area.[*]Construct a list of normalized area weights for each triangle: (AreaOfTriangle / TotalSurfaceArea).[*]For each point you generate[list=1][*]Generate a random number 'r' (float) in [0,1][*]Walk through the list of weights, accumulating weight until the total is <= r[*]Generate a random point on the surface of the selected triangle. (Via randomized barycentric coordinates or similar).[/list][/list]
This is entirely probabilistic, and isn't going to give reasonable results until you've generated a lot of points relative to the size/complexity of the mesh. But it's very simple to implement, and the memory overhead of that list of normalized area weights is pretty small (compared to the rest of the data for the mesh).

##### Share on other sites
Buckshag    899
What I did sometime for somethign similar was using halton sequences to generate pseudo random positions inside the bounding rect of the triangle as seen in a front view, so in 2D essentially. And then transforming it back into 3D space.

Then checking if these points are inside the triangle or not, and repeating that. This gives you a nicely evenly spaced, yet random looking pattern.

Maybe there are much better solutions. I just know this worked for me

Another idea might be to generate texture coordinates in a texture atlas where you unwrapped the mesh with some algorithm to eliminate texture stretching and give an even distribution. Then generate the sample points inside the texture, maybe again using halton sequences or some fixed grid, and then convert those uv's back into 3D space.

Not sure if this is crazy, as there might be an easier way, but just sharing some ideas.

##### Share on other sites
lauris71    841
[quote name='Katachi' timestamp='1305808768' post='4812973']
I would like to distribute points evenly on a triangle mesh. So all points kind of have a similar distance to each other on the whole mesh (not just inside of a triangle). Another constraint I have is that I would like to define the amount of points used. Of course the faster the algorithm the better.

All links, resources, code are highly appreciated. Also of course opinions are very welcome.
[/quote]
You probably mean, that points have similar distance to certain set of the closest ones? So that if you have triangle mesh topology of the new points, all triangles have similar edge lengths.
I think that even if your initial mesh is sphere, the case is strictly solvable only for 1, 2, 3, 4, 8 and 20 points (simple cases and regular polyhedra composed of triangles).
Probably the best algorithm would be something along the line osmanb suggested, following by iterative step. You will have to construct the topology of the new mesh, then define tensions in edges and try to find local minimum of total tension by moving vertices. Still even the calculation of the best distance between two points on the surface of mesh can be tricky.
Or instead of starting from random placement of points you can construct the topology of the new mesh around the object in question, and then try to iteratively shrink it, vertex-by-vertex, by using some clever tension system calculated from the distances between your points and the vertices in original mesh and the distances between the vertices of the new mesh.

##### Share on other sites
Katachi    131
Hey,

thanks everyone for the ideas and opinions. I think Lauris is closest to what I want and I found a paper that seems to fit very well: http://www.cg.tuwien.ac.at/research/publications/2009/cline-09-poisson/cline-09-poisson-paper.pdf

Thank you everyone!

##### Share on other sites
alvaro    21246
I would start with N random points (using something like osmanb's method) and then modify the points in many small increments, for instance by finding the closest pair of points and moving them away from each other a bit. Since computing distances within the mesh is difficult, I would first try to simply measure the distance in 3D and project the points back to the mesh after moving them, and see if the results are acceptable.

By the way, why do you want to do this?

##### Share on other sites
Katachi    131
[quote name='alvaro' timestamp='1305814296' post='4812997']
I would start with N random points (using something like osmanb's method) and then modify the points in many small increments, for instance by finding the closest pair of points and moving them away from each other a bit. Since computing distances within the mesh is difficult, I would first try to simply measure the distance in 3D and project the points back to the mesh after moving them, and see if the results are acceptable.

By the way, why do you want to do this?
[/quote]

Hi,

if I understand this correctly this is kind of the way the Greg Turk point repulsion works right? I considered this but even if optimised via a KDTree it kind of can become very slow for large point sets so I was looking for a faster way which the Dart throwing paper seems to achieve.

I need an even distribution of particles on the surface.

##### Share on other sites
alvaro    21246
[quote name='Katachi' timestamp='1305817470' post='4813020']
[quote name='alvaro' timestamp='1305814296' post='4812997']

By the way, why do you want to do this?
[/quote]
[...]

I need an even distribution of particles on the surface.
[/quote]

##### Share on other sites
zacaj    667
Unwrap the model and do poisson disk sampling on the 2d (texture?) and then transform the points back to 3d

##### Share on other sites
alvaro    21246
[quote name='zacaj' timestamp='1305835061' post='4813160']
Unwrap the model and do poisson disk sampling on the 2d (texture?) and then transform the points back to 3d
[/quote]

I don't know how to define unwrapping for an arbitrary mesh... Do you have a definition?

##### Share on other sites
osmanb    2082
Unwrapping is fairly easy (assuming you're talking about using the UVs), but going back is going to be difficult (without some kind of helper data that will be larger than my simple list of weights). And it only really works if you actually have UVs, and if the texel density is consistent across the mesh.

One more point about my original suggestion: After computing the normalized triangle weights, you should do a single linear pass to compute the cumulative weight. That will let you switch to binary (rather than linear) search when you need to pick a triangle. Of course, if you really don't care that much, you can just assume that all triangles are weighted evenly, and pick one at random. That also works if you can massage the data coming in (tesselate or weld triangles to get the maximum area difference down to some tolerable threshold).

##### Share on other sites
Katachi    131
[quote name='alvaro' timestamp='1305818404' post='4813024']
[quote name='Katachi' timestamp='1305817470' post='4813020']
[quote name='alvaro' timestamp='1305814296' post='4812997']
By the way, why do you want to do this?
[/quote]
[...]

I need an even distribution of particles on the surface.
[/quote]

[/quote]

That's the answer you have to live with. It's confidential.

##### Share on other sites
alvaro    21246
A few years ago my brother was working for the Namibian government trying to improve the conditions of bushmen that had been given land but didn't know what to do with it (they are nomadic). Through two translators (English <-> Afrikaans and Afrikaans <-> some San language), he spent a full day talking to the elders, trying to understand their situation to see how he could best help them.

The conversation went something like this:
- What is the main problem facing your community?
- We need a well.
- That's not a problem, but one possible solution to a problem. What is the problem?
- We don't understand.
- OK. Let me explain it with an example. If I am growing lettuce and my neighbor has free-roaming cows that eat them, I might think that I need a fence. But that's not really my problem: The problem is that my neighbor's cows are eating my lettuce. A fence is one possible solution, but perhaps we could tie the cows, or we could move them somewhere else.
- Oh, that's a good example.
- So what is the main problem you have?
- That we don't have a well.

Although we don't have the huge language barriers or the deep cultural differences that were probably the cause of the lack of understanding in my brother's case, for a moment there I was feeling his frustration.

In case you are interested in the end of the story, the Ministry of Lands wanted to build wells because the number of wells built is an easy statistic to give the president and it makes them look good, even though wells are often not the most cost-effective way of providing water (one could organize a distribution system and have several villages share a well), and water shortage might not even have been their main problem (not knowing how to farm was probably a bigger long-term concern). So I think they ended up getting their well.

##### Share on other sites
lauris71    841
[quote name='Katachi' timestamp='1305817470' post='4813020']
I need an even distribution of particles on the surface.
[/quote]
Now if I think about it, the optimal algorithm is probably different depending how many particles you plan to add, compared to the complexity of original mesh. If there are many more particles than there are the triangles in original mesh, then equalizing the shortest path between neighboring points is sufficient. If there are less points (or there are parts with vastly different complexity), you have to equalize the surface area of the original mesh covered by each triangle of the new mesh.
For example - take dumbbell mesh, and try to place 8 points over it. You will have a solution, where all points form a "cube" at the one end of dumbbell with the distances between points being equal. But one side of the "cube" will have vastly different area.

##### Share on other sites
alvaro    21246
Yes, you could make the smallest distance be as large as possible, or you could make the largest area of a polygon in the Voronoi diagram be as small as possible, or the smallest angle in a Delaunay triangulation be as large as possible. These all fit "evenly distributed" in some sense, but there is no way to know what the OP means without explaining what he wants the points for. He's already said he cannot tell us, so I don't feel inclined to put any more effort into helping him.