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.
Thank you in advance!!
Best
Katachi
Evenly distribute points on a triangle mesh
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.
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.
If you only care about populating the surface of the mesh, the approach I'd take is:
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).
- 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).
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).
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.
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.
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.
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.
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!
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!
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?
By the way, why do you want to do this?
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.
[quote name='alvaro' timestamp='1305814296' post='4812997']
By the way, why do you want to do this?
[...]
I need an even distribution of particles on the surface.
[/quote]
That's not an answer.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement