pouët.net

Go to bottom

Progressive poisson disk?

category: offtopic [glöplog]
Any idea on how to create a random point distribution in a disk where with the increasing random number of points they keep a poisson like distribution (~equally spread)?
added on the 2011-07-25 18:47:23 by xernobyl xernobyl
disk or disc?
added on the 2011-07-25 18:49:17 by Gargaj Gargaj
disc. sorry, I was thinking about dicks.
added on the 2011-07-25 18:50:38 by xernobyl xernobyl
basically you want a normal poisson distribution but simply limited, by a circle, right?
added on the 2011-07-25 19:04:40 by Gargaj Gargaj
should this be realtime or for pre-processing?
added on the 2011-07-25 19:28:14 by toxie toxie
pre.
added on the 2011-07-25 20:08:00 by xernobyl xernobyl
Do you need an exact number of points? or you would be ok with a given density ?


added on the 2011-07-25 21:15:49 by T21 T21
Just to give some ideas.
Generate a 50/50 density random distribution of point in a square.
This step is actually trivial.

Then scale the coord to your desired density and reject points outside the disc.
The scale factor is your density, if you started with 32K samples:
1x will represent 25735 samples on the disc 2x 6433, 4x 1608, ...
So just scale to control your density to any levels.

added on the 2011-07-25 22:33:43 by T21 T21
but poisson disk has a better uniform distribution than 'pure' randomness..

this is some new stuff coming out: http://graphics.uni-konstanz.de/publikationen/2011/farthestpoints/Schloemer.etal-2011-FPOPSwMMD.pdf
this is some older, but rather simple stuff: http://www.cc.gatech.edu/~yuting/OtherProjects_files/report.pdf

in general i would recommend to simply use low discrepancy points which are transformed to the disc (polar mapping or concentric mapping)..

another option is to use dart throwing onto the unit square and keeping only these that hit the disc, then some passes of lloyd relaxation afterwards..
added on the 2011-07-25 23:18:07 by toxie toxie
uhm, and answering the progressiveness question: thats what my comment on low discrepancy points/sequences are about.. a simple one would be a rank-1 lattice or using halton or sobol'..
added on the 2011-07-25 23:22:36 by toxie toxie
xernobyl: To add a point to a set, generate n candidate points inside a circle. Then select the one which is the furthest away from all points currently in the set.
added on the 2011-07-26 01:52:22 by kusma kusma
Quote:
furthest away from all points

should that be the max distance, distance sum, average, median?
added on the 2011-07-26 02:09:39 by xernobyl xernobyl
What toxie said. Do it.
added on the 2011-07-26 02:18:28 by las las
I think I'm getting an idea on how to do it. Thanks for the suggestions.
added on the 2011-07-26 02:44:30 by xernobyl xernobyl
I'm not convinced any method more complicated than what I proposed will give you better results...
I will write an implementation later on for reference.



added on the 2011-07-26 05:18:44 by T21 T21
i always use the Sobol sequence for raytracing/sampling 2d spaces
added on the 2011-07-26 13:03:16 by iq iq
xernobyl: The minimum of all distances. Sorry for not being clear.
added on the 2011-07-26 13:04:32 by kusma kusma
xernobyl: Considered just modelling a bunch of particles that repel one another, constrained to a disk of whatever size and shape you need? Like this except you won't need to model velocity or anything, just soft distance constraints.
added on the 2011-07-26 13:38:21 by doomdoom doomdoom
♥: But he was asking for a progressive set, no? So you'd always want to add the point that gives the most possion-like distribution, without having to re-calculate the previous points...
added on the 2011-07-26 13:54:19 by kusma kusma
kusma: I guess it depends what he needs it for. I can imagine cases where you'd prefer to recalculate the whole set if it meant better distribution, or cases where you'd want to select points from a precalculated set so that you'll reach an ideal distribution in the end. Hard to tell what he's actually working on, though.
added on the 2011-07-26 14:48:08 by doomdoom doomdoom
♥: No, it's actually very easy to tell; he used the word "progressive".
added on the 2011-07-26 14:53:47 by kusma kusma
Why don't you use a rectangular Poisson and then you discard points outside the circle? Why do you need Poisson? Any real reason for it?

added on the 2011-07-26 14:58:00 by texel texel
kusma: can't that be done by fixing every n new values? Like adding a few points, repel them, add a few more points, repel only the new ones fixing the old ones where they are. repeat.

I'm not sure how good that looks without implementing it.
added on the 2011-07-26 15:02:06 by xernobyl xernobyl
We're using poisson disc distribution for our incremental super-sampling at work, and the technique I described works fine for this purpose.

I don't see why you want to add points to the solution, just to repel them later. Why not just generate a set of random candidates, and pick the best one?
added on the 2011-07-26 15:24:25 by kusma kusma
Well, you could repel just the best of the random candidates, so it slips into the nearest equilibrium position at least.
added on the 2011-07-26 15:39:23 by doomdoom doomdoom

login

Go to top