Well, I just wasn't happy with that old point generator (did I write on this already?) so today I changed it completely. Now it exploits topological locality:
Imagine a 2D circle located on a local point on the 3D sphere. As we move that local point along the sphere we can linearly slide the points on the circle in some direction, and it will closely approximate the motion on the sphere. Thus, if the 2D points on the circle start out uniform, they will end up uniform after we slide (translate) them. Of course, there is a little bit more to it but really not much.
Anyhow, the algorithm then basically consists of keeping track of those random points, in this case distributed uniformly within a square, which we offset as we move around. They stay uniformly distributed. Then we check which points are inside our target shape (a cheerio/doughnut/ring/what-have-ye) and then put a simple transformation back and forth and voila, works!
It might be a bit slower than before, because we have always extra points to consider. But you know, I can maybe end up splitting this across a few frames or something, and/or the speed difference won't really matter. Unfortunately, because of the requirement that we translate the points and they remain uniform, it does seem to me that we have to keep it a square. I may be mistaken.
Anyhow, the amazing thing is, I got this thing implemented and replaced the pre-existing core of the algorithm and it works! I'm just adding some misc. features, namely lofting (to fix depth buffer issues) and alpha blending (absolutely neccesary to get even a slightly good look).
So there! =)