Jump to content
  • Advertisement
Sign in to follow this  
Katachi

Evenly distribute points on a triangle mesh

This topic is 2619 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
If you only care about populating the surface of the mesh, the approach I'd take is:

  1. Compute the area of each triangle in the mesh, sum them to get the complete surface area.
  2. Construct a list of normalized area weights for each triangle: (AreaOfTriangle / TotalSurfaceArea).
  3. For each point you generate
    1. Generate a random number 'r' (float) in [0,1]
    2. Walk through the list of weights, accumulating weight until the total is <= r
    3. 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).

Share this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!