[wouxhrxb] selecting points for an artificial starfield

consider plotting a bunch of random dots in a way that one can efficiently zoom into small regions.  goal is to simulate being an astronomer, zooming into small regions of the sky with a telescope.

recursively divide a square field into quarters, dividing in half twice.  this defines a binary tree.  for each division by one-half, label the halves, perhaps 1 and 2.  children of a node need to have distinct labels, but otherwise labels can be reused.

the sequence of labels on the path from the root give each divided field a unique identifier.  use the identifier to seed a random number generator for that field.

start with N dots in the top level field, N very large.

sample the binomial distribution with N trials and p=1/2 to decide how many stars go in each half.  efficiently sampling the binomial distribution when N is large is non-trivial but well studied, for example, Knuth TAOCP.  (future post vgkevtpx)

repeat with the half that you are interested in, the new N being the number of stars in that half, as calculated in the previous step.

if there are zero stars in a field, you are done.  that field is empty.

if there are one or more stars in a region smaller than a pixel at the current zoom level, you are done.  that pixel is lit.

to determine the brightness of a pixel, first count the number of stars in the region it represents, using the above algorithm.  (when not very zoomed in, all pixels will have some stars in them, reminiscent of Olbers's paradox.)  artistically scale the count to a pixel brightness.  perhaps set pixel brightness by comparing expected number of stars in a pixel versus observed, scaled by standard deviation.  repeat for every pixel in the image.  this may be a little time consuming, though optimization is possible.  this model assumes all stars are the same distance away and all the same brightness, both assumptions scientifically extremely wrong.

future post: coloring stars.

instead of square, perhaps geodesic subdivision of a celestial sphere.  we need the area of each cell to specify the probability for binomial, perhaps a bit messy.  alternatives: HEALpix, Discrete Global Grids, equal-area partition of the surface of a sphere.

is a nice artificial celestial starfield worth the effort for a game?  maybe not if the sky is not the main part of the game.

it is also possible to do this all in 3D, placing stars in space, generating a uniform distribution of stars in a finite or toroidal universe.

perhaps brightness extinction due to intervening dust.

things get boring, empty space, after zooming too much, limited by the value of N chosen initially.  is there a way to avoid having a limit?  maybe some modification of fractal terrain (which limits zooming out).

consider letting stars move over time (proper motion).