odds are an octree is overkill for both collisions and culling.

Strongly disagree, on what experience do you base that assumption?
I always have had big speed ups using octrees for both culling and collisions in practical cases.

odds are an octree is overkill for both collisions and culling.

Based on my personal experience octrees are not just efficient but also practical. Their structure makes space division natural and intuitive, but these are just bonuses, performance is greatly increased when properly used.

I don't have any personal experience in this area, but I found this article interesting, about DICE rethinking how they do culling when making Battlefield 3.

Most celestial bodies orbit their star(s)/galaxy/etc in a disk. This means that from a distance, a galaxy or star system would appear to be a 2-dimensional object. Even inside a galaxy or star system, they're so relatively 2 dimensional that a quadtree probably makes more sense than an octree. Since objects with fixed orbits on the disk should rarely collide, you only need to worry about objects that have been shifted from their orbit (IE an asteroid the player pulled with their ship) and objects with orbits that cross other orbits (IE comets), maybe this is a better case to optimize for as far as collision goes.

Also, you'll need to adaptively load/unload nodes as the player approaches/leaves them. The number of stars in a galaxy, and the number of objects in a star system, it would be impossible to keep them all in memory. You need to keep as few as possible in memory. Ideally you'd use a PRNG to generate them, and then they can be reliably stored as just the PRNG seed. Then to show the node at a great distance (size <= 1px), you just need a cached hue and absolute magnitude.

About Oort clouds, Kuiper Belts and Astroid Belts - I'd generate them with a PRNG each time the player approaches, separate from the rest of the system. Too big and too much stuff to keep loaded when the player's nowhere near them.

I know that in order to overcome the floating point precision i would have to somehow scale the surrounding cuboids (spaces) in order to keep the depth buffer happy, this should be pretty easy, at least in theory.

You actually have several "space systems". You don't need to account for all of them for every object. Ignoring the player for a second:
1) Satellites (moons, orbiting ships, etc) only need to worry about their location relative to their planet. This can probably be on a 100km scale. Justification: accuracy of IEEE single precision ("float") is 7 digits. Mean distance ISS to earth is 400km = 4.0; mean distance moon to earth is 370,300km = 3703.0; mean distance Callisto to Jupiter = 1,833,000km = 18330.0 [Jupiter has satellites 10x more distant than Callisto, but they're all less than 200km diameter and boring]. This leaves a couple accurate digits behind the decimal point too.
2) Planets and inner solar system interplanetary objects only need to worry about their location relative to their star(s). This can probably be on a .1AU scale. Justification: same as above. Mean distance Mercury to Sun is .39AU = 3.9. Mean distance from Neptune to sun is 30.1 AU = 301.0. Fits very well in single precision.
3) Oort cloud constrained objects only need to worry about their location relative to local objects. This is probably best accomplished using a bounded volume heirarchy, where the bottom-level bounded volume contains some maximum of N objects, and you only compare each of those N objects against objects in the same bounds.
4) Kuiper belt constrained objects only need to worry about local objects. They also need to keep track of their orbit, but this can be a single value (eg in Radians).
5) Oort cloud and kuiper belt objects that enter the inner solar system during their orbits need to worry about inner solar system objects *ONLY* when they're in the inner solar system. There's numerous ways to implement this behavior.
6) If you want high def views of the planets surface from low orbit/high altitude, objects on the planet might also need to keep track of their latitude and longitude, OR you'll need to rig up some clever way to project surface geometry on a sphere.
7) On the galactic scale, you can probably get away with a 10 parsec scale (milky way is 30,000parsecs across = 3000.0; the nearest star to the sun is Proxima Centary, 1.3parsec = 0.13).

Adding in the player, you ALSO need to translate every object visible to the player into "player space" for rendering, culling, etc. Player space while in a ship will probably have a scale of ~10m (the USS Enterprise NC-1701 from the original Star Trek was supposedly 289 meters long=28.9, the T-65B X-wing from the original Star Wars trilogy was 12.5 meters long = 1.25).

Of course I'm assuming here you're going for a hard sci-fi game. If you're looking for mass appeal, using realistic coordinates is counter productive: nobody wants lightyears of nothingness before they hit their next star. So instead, you can probably use double precision and a 10km scale for a solar system which only has a diameter slightly larger than Jupiter (140,000km = 14000.0). For interstellar coordinates, you could just use the same scale, and add an int64_t in front of it (maximum size of galaxy = 9.2*10^18 jupiters), and for intergalactic coordinates just use a single int32 representing n*maximum_galaxy_size = n*9.2*10^18 jupiters = already crazy huge.

>> Strongly disagree, on what experience do you base that assumption?

that you don't model such a large number of stars that you have to partition space to check collisions.
have you tried it yet? at what point (how many stars with how many planets per star on average and how many moons per planet on average) is an oct-tree required? would it apply to my case of 1000 stars with 10 planets and 10 moons per? or can i go 100,000 stars? or 100,000,000? when do i hit oct-tree requirements? if you haven't tried it, it would seem to me to be pre-mature optimization.

Some years back i was able to render about a million point sprites per frame (no culling), but a bright spot on the night sky can be a whole galaxy, not just a star.
For collisions the octree was worth it with less than 100 spheres in a box (much more years back).

With the complexity i have in mind when reading 'procedural infinity' some kind oh hirarchy is needed.
Probably you assumed lower 'good enough for purpuse' complexity.

However - if i'd be a newbie reading your comment (or the Dice paper), i might take conclusion:
"Optimized brute force almost always wins over complex algorithms reducing work. No need to learn this difficult tree stuff properly.",
and that would be a bad thing.

Wow. There's a lot of talk about how it can't be done.

From Earth, most people (including me) can't discern each star in the galaxy or MOST stars for that matter. You only need a general shape of the galaxy and use some form of noise to generate stars within a discernible distance. This may still be a lot to handle for most machines, but it can be done.

I do think the octree idea may not be needed, but the idea of dividing the massive amount of space in the universe is the idea. You will, of course, have to decide on the universe's size and go from there. If you are trying to actually simulate the known universe, that's a tall order. If you just want to generate a random universe, then use perlin noise. Make a "universe scale" noise that just worries about where and what type of galaxies are in the universe. Then make a "galactic scale" noise to govern each galaxy-- this will be more involved as galaxies have varying shapes and sizes, but it can be done. Then you will need some process to create each solar system (only when within range of it)-- this will be even more detailed in that there are huge numbers of variables for planets and asteroid belts. Each planet will have a unique set of textures (use a cube-sphere) http://acko.net/blog/making-worlds-1-of-spheres-and-cubes/

This shows you the basics of making a cube-sphere with 6 textures to create beautiful looking planets and moons.

More specifics:

-use 3D perlin noise (or simplex noise) to generate galaxy "types" and space between galaxies. The actual scale doesn't matter here. Once they are created, you simply use the 3D cube space and densities and multiply by some super astronomical number to get your distances right-- play with it until you get something you like.

-use 3D representations of the different types of galaxies when viewing from a distance and grow in detail as you get closer. This will take some trial and error to get them to look decent.

-Once close enough to a galaxy, you will need more 3D noise to generate the "near" stars. This may take a lot of horsepower to do, but I have been able to show 30,000 stars using instancing on my GPU with great success. I'm sure I could do near 100,000 or even 1,000,000 without too much lag-- this has not been tried..... Most of the stars you see in the night sky are within that 30,000 that I am showing in my game.

-When close enough to a star to start seeing planets, you can generate the planets for that star. This is also complex. The way I do it is I start nearest the star and randomly generate a planet orbit and decide what type of planet it is (and its size) and I go to the next planet. Once I generate all the main planets, I go through each one and generate the moons according to its mass-- more massive planets will likely have more moons than less massive ones (duh). Once all the planets and all the moons are "typed", then I send information to my texture generator to make each planet's/moon's textures on an individual basis. I use multithreading to accomplish this to keep the game moving while I do textures.

this is where I learned how. Be careful when multithreading! You can't access directx outside the main thread, so you will have to create all 6 textures, lock each one and send the texture process a pointer to each of them. When the texture process is complete, unlock the textures and they are ready to render.

-- have fun an program on!