3 ms·
Another 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 triangl
by jepler 4y ago
Another 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)