5 ms·
Alternative: sample random points on a r*r square, and refuse all the ones outside the distance of the radius. This can be generalized for any shape where we ha
by antirez 4y ago
Alternative: sample random points on a r*r square, and refuse all the ones outside the distance of the radius. This can be generalized for any shape where we have a f(x,y) -> bool that tells us if a point is inside or outside our shape.
- ohgodplsno 4y agoFor certain purposes (like graphics programming), this is not a viable option. Not only are you bounded by time (16ms for a single frame means you have to limit the number of points you sample, which may mean that from one frame to the other, you have way less samples), but checking for the distance is way, way less efficient than a simple math expression that can be easily parallelized.
- antirez 4y agoI think you can avoid taking the square root in the distance formula (by squaring the comparison term), so this actually could be the fastest way possible to reach the effect, because of all the sampling, the points outside are a minority. What the tweets mention instead is you need to take the square root, that is the slowest thing in the expression.
- whyever 4y agoThat is indeed the fastest way in my experience (at least on the CPU). It's very unlikely to have more than a few rejections, so any method that requires evaluating trigonometric functions cannot compete.
- hyperbovine 4y agoThe story on a GPU is much different though, thanks to branch divergence.
- Jarmsy 4y agoIt's not too bad in 2d, but the efficiency of the rejection method gets very bad in higher dimensions.
- jepler 4y agoAnother attempt at a sqrt-free "uniform point nearly in circle": point in regular N-gon. It's easy (work not shown) to sample a point uniformly within a triangle. Sample from the triangle that has (0,0), (1,0) and (cos 2pi/N, sin 2pi/N) as its vertices. Then uniformly pick an integer M from 0 to (N-1) and [by table look-up of sin/cos] rotate this point by the angle M*2pi/N. Even for modest values like N=128, 256 this is very close to a circle (around .1% error). However, I'm not familiar enough with GPU compute to know if this maps well onto the available operations. It seems like a table look-up is a lot like a texture look-up so I'm tempted to assert it should be fast.
- sokoloff 4y agoThere’s a sqrt-free “is this point in the circle?” algorithm as well: sum the squares of each coordinate and compare to the square of the radius.
- dekhn 4y agoding ding ding... this is the right answer (if you don't want to think about inverting the pdf).
- jepler 4y agoyes though as sibling points out rejection can be bad for performance (hard to parallelize). I should have specified that the algorithm I suggested was sqrt-free and rejection-free (but does have a problem with distribution right near the edge of the circle)
- ninepoints 4y agoGraphics programming perspective: We call this “rejection sampling” and may work and is a more general sampling method that can sample from more difficult probability distributions but has significant disadvantages. First the runtime is the worst case across all threads invoking this in a GPU simd unit. Second, you have to evaluate the pdf itself which is easy in this case, and harder in general. The sqrt really doesn’t really amount to much to outweigh the cons in a shader. You can use the rcp sqrt intrinsic if precision is less important, or square the LHS if the ALU is actually a problem (or to conserve more energy)
- olliej 4y agoThis is what I use in my terrible ray tracer, my understanding is that it does bad things to GPU perf because GPUs do not like branching.