**0**

# Evenly distribute points on a triangle mesh

###
#1
Members - Reputation: **131**

Posted 19 May 2011 - 06:39 AM

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.

Thank you in advance!!

Best

Katachi

###
#4
Crossbones+ - Reputation: **2076**

Posted 19 May 2011 - 07:16 AM

- 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
- 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).

###
#5
Members - Reputation: **834**

Posted 19 May 2011 - 07:53 AM

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.

###
#6
Members - Reputation: **841**

Posted 19 May 2011 - 07:54 AM

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 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.

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.

First technology demo of my game Shinya is out: http://lauris.kaplinski.com/shinya

Khayyam 3D - a freeware poser and scene builder application: http://khayyam.kaplinski.com/

###
#7
Members - Reputation: **131**

Posted 19 May 2011 - 08:09 AM

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!

###
#8
Crossbones+ - Reputation: **18610**

Posted 19 May 2011 - 08:11 AM

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

###
#9
Members - Reputation: **131**

Posted 19 May 2011 - 09:04 AM

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?

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.

###
#13
Crossbones+ - Reputation: **2076**

Posted 19 May 2011 - 02:28 PM

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).

###
#15
Crossbones+ - Reputation: **18610**

Posted 20 May 2011 - 04:46 AM

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.

###
#16
Members - Reputation: **841**

Posted 20 May 2011 - 05:24 AM

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.I need an even distribution of particles on the surface.

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.

First technology demo of my game Shinya is out: http://lauris.kaplinski.com/shinya

Khayyam 3D - a freeware poser and scene builder application: http://khayyam.kaplinski.com/

###
#17
Crossbones+ - Reputation: **18610**

Posted 20 May 2011 - 07:20 AM