uniform particles on a polygon
Author
Anyone know of a good technique to uniformly distribute an arbitrary number of particles on a convex polygon? Currently, I''m randomly distributing on the polygon, and then running a particle repulsion algorithm on them. But I found this to be way too slow for the number of particles I need.
yeah I saw your post on flipCode's forums and I'm thinking about it. One method would be to tessellate your polygon into triangles and then assign particles according to triangle area... but I'm trying to give this further thought.
Could you define exactly what you mean by "uniformly distribute" and maybe what this is going to be used for? Also, I'm assuming you're working in 2D??
-Si
Edited by - xsi on October 2, 2001 10:32:01 AM
Could you define exactly what you mean by "uniformly distribute" and maybe what this is going to be used for? Also, I'm assuming you're working in 2D??
-Si
Edited by - xsi on October 2, 2001 10:32:01 AM
Your method is actually pretty cool, the particle repulsion algorithm. Its related to "elliptic" mesh generation in the engineering world. There are ways to speed it up, using multigrid methods and partial differential equations, but that''s way trickier than just finding an "algebraic" way of doing uniform distribution---which is what you''re asking for.
Try this quick and dirty method. Uniformly subdivide the circumference of the original polygon into a bunch of new points. Call this point_set(N), where N is the number of sets of particles you want distributed from the centroid to the boundary of the polygon. Then, for i = N-1 to 1 (in that order), duplicate point_set(N) to create point_set(i). Scale point_set(i) by i/N about the polygon centroid. Finally, add one point at the centroid.
That probably won''t look as good or smooth as your repulsion algorithm. But perhaps it will be good enough. If the polygon is not very much like a circle, there is a way to get a distribution that looks *more* uniform than this quick method. But try that for now.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
Try this quick and dirty method. Uniformly subdivide the circumference of the original polygon into a bunch of new points. Call this point_set(N), where N is the number of sets of particles you want distributed from the centroid to the boundary of the polygon. Then, for i = N-1 to 1 (in that order), duplicate point_set(N) to create point_set(i). Scale point_set(i) by i/N about the polygon centroid. Finally, add one point at the centroid.
That probably won''t look as good or smooth as your repulsion algorithm. But perhaps it will be good enough. If the polygon is not very much like a circle, there is a way to get a distribution that looks *more* uniform than this quick method. But try that for now.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
Author
Thanks for the replies, guys...
xSi, I've tried the tessellation thing. The problem with that method is that you have limited control over how many points you end up with on a polygon, and you end up with a big explosion of particles as you tessellate further. When I say uniform, I mean somewhat "evenly" spaced out...kinda like having a really pretty looking delauney triangulation. The particles are defined in 3D...and this is for a painterly rendering engine I'm working on for a research project...(It's pretty close to completion, but I have to tweak a lot of stuff).
grhodes_at_work...Particle relaxation definitely ends up with nicely spaced particles (the algorithm was taken from Greg Turk's dissertation, "Synthetic Textures"). Interesting idea...Although I could imagine this creating a "line" of points from each vertex to the centroid. This would be more apparent for polygons with wide edges. Your method might be tricky to implement, especially if I require a specific number of particles (for instance, I might require 357 points for this polygon, but 127 points for a similar polygon). I'm doing this over an entire model...currently, each particle exerts a force on particles on the same polygon. I'm planning on extending so that particles affect neighboring polygons. Since this is an N-squared algorithm, I might hold off on that. It takes over an hour to run this algorithm on about 50K particles over a few hundred polygons. And this is for a small model too!
Anyways, I think for now I'm gonna stick with particle relaxation since it produces the best end result. Thanks for the help!
Edited by - davidko on October 3, 2001 11:56:19 PM
xSi, I've tried the tessellation thing. The problem with that method is that you have limited control over how many points you end up with on a polygon, and you end up with a big explosion of particles as you tessellate further. When I say uniform, I mean somewhat "evenly" spaced out...kinda like having a really pretty looking delauney triangulation. The particles are defined in 3D...and this is for a painterly rendering engine I'm working on for a research project...(It's pretty close to completion, but I have to tweak a lot of stuff).
grhodes_at_work...Particle relaxation definitely ends up with nicely spaced particles (the algorithm was taken from Greg Turk's dissertation, "Synthetic Textures"). Interesting idea...Although I could imagine this creating a "line" of points from each vertex to the centroid. This would be more apparent for polygons with wide edges. Your method might be tricky to implement, especially if I require a specific number of particles (for instance, I might require 357 points for this polygon, but 127 points for a similar polygon). I'm doing this over an entire model...currently, each particle exerts a force on particles on the same polygon. I'm planning on extending so that particles affect neighboring polygons. Since this is an N-squared algorithm, I might hold off on that. It takes over an hour to run this algorithm on about 50K particles over a few hundred polygons. And this is for a small model too!
Anyways, I think for now I'm gonna stick with particle relaxation since it produces the best end result. Thanks for the help!
Edited by - davidko on October 3, 2001 11:56:19 PM
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
