Hello,

This is my first time posting here, so nice to meet you everyone!

For some time now i'm trying to find a good solution for rendering a procedural generated universe.

I've read most of the articles on the subject (or at least what Google provided me) and i'm still satisfied with the information i have.

Since tutorials on this subject are almost non existent or outdated, i began trying to think my way out of this.

I was thinking that if we can use Octrees for collision detection, frustum culling and raytracing, why can't we use this beautiful data

structure to solve the universe rendering problem.

So, for what we know, we have 4 types of "spaces":

1. Intergalactic space

2. Interstellar space

3. Interplanetary space

4. Planet surface

The root cuboid of the universe would be the universe itself, using the parsec scale.

The children cuboids would represent the intergalactic space, using the lyghtyear scale, recursing all the way down to the surface of the planet.

Now i know that i would have to somehow interpolate the scales and camera projection settings between these spaces in order to have a smooth transition.

After getting inside a cuboid (interplanetary space), i would render the surroundings in a cubemap and use it as my "skybox".

Using the octree method i believe would give me plenty of advantages one of it being the ease with which i can generate galaxies, star systems and planets. For instance i could use a noise function to generate children for the root cuboid, thus generating procedural galaxies. I could apply the same algorithm for generating interplanetary bodies, so on and so forth.

While inside a planetary space cuboid, i could project the distant stars on the cubemap based on their luminosity. For instance bright stars would get rendered as bright spots on the cubemap, i think you get the point here.

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.

Now the real problem is the transition of the camera from a high level space to a lower level space. Some interpolation should be used here in order to make it smooth so that when we get from the root cuboid inside a children cuboid objects should not just instantly scale up.

I was thinking to subdivide the universe to a point where a cuboid space could give me enough floting point precision to render it's content without any unpleasant surprises and use the logarithmic depth buffer in order to overcome z fighting at very large distances.

The interplanetary space cuboid would use doubles for positioning giving me precision ranging from 1 mm to about1 trillion km, as Sean O'Neill states in one of his articles on the subject.

I'm sorry if i was not clear enough on some of the things i said here, its just that there's so many things inside my head right know, i can't really synthesize this into a better question.

Now, what do you people think of this? Is it doable, was it done before? What would be the challenges, the good and the bad?

Thank you for taking your time to read this.

My own experience may not be very relevant here, and I don't consider myself a top-level programmer, but I'll chime in anyway. Maybe it will give you some ideas - or at least eliminate some.

My own experience with this is limited to making a "to scale" version of our solar system. Even here, the floating point problems arise too.

I basically had 2 scales. A 'solar scale' and 'world' scale. The player would move around the 'world' at a very slow rate (like .0001 per second). The 'world' was an area that was at a scale that it wouldn't produce floating-point position errors. Each object in the world would then have a 'solar position/scale', which was it's real-world size (which also had to be scaled to a fraction of it's real value due to the massive numbers involved ).

When the player moved, that info would be relayed to objects to change their scale/position to make them appear to move.

Since I was only doing the solar system, I didn't really have to mess with LOD/luminosity, although at a small enough scale most objects would be too small to even render a single pixel. If I had continued the prototype, I would have swapped them out for 2d sprites at some point.


I should note that overall though, this wasn't a very good system. I'm using unity, but I immagine similar problems woud arise in any engine. Since I was using a non-standard scale movement, physics and collisions were useless since they don't scale well. Physics don't work well when you're applying super-tiny forces (like .00001 velocity) and collision and rendering also doesn't work right on ultra-large-scale objects either.

Another problem I ran into was my player's speed. When you're inbetween planets/objects, the ultra-low speed felt horribly slow, but when you were close to objects, the ultra-low speed was insanely fast. There was no way to make the speed small enough to be even vaguely realistic since it would run into floating point errors on the huge number of zeros.

Basically, I started out overly concerned errors of the too-large scale, but ran into them at the too-small scale :-\ I briefly flirted with the idea of a double-scaling system.. but I could only summon the vaguest idea of how to go about that.

Ultimately though, i dropped the idea because the solar system is fairly boring and 99.9% empty and the technical problems I was facing wouldn't have been worth fixing for a 99.9% empty gameworld.

I've had some of the same aspirations. The problem is scale. I came up with a different vector system than the D3D vector. I use __int64 paired with a float. I have posted examples somewhere on this forum .... or was it another forum? Anyway, the idea is to use the __int64 as the top level of the vector and the float as the lower precision (0.0f-1000.0f). This will allow you to have 2^64 km worth of distance. You would have to write your own operators of course, but that's not a problem. Once everything (from galaxy size down to planet size and even further) is using this coordinate system, you can make a relative vector to the camera and render using D3D as normal. You WILL have to use scaling methods to show everything correctly....

This is a link to one of my posts:

http://www.gamedev.net/topic/649931-progress-on-my-current-game-no-name-yet/

I'm at work right now, so I'm not sure it's what I think it is.....

In general, I have a small number of stars around Sol (30,000) that can be explored. The only "transition" that I will have is traveling between star. This is not because the coordinate system can't handle the size, it simply gives me time to generate the textures (procedurally) for the solar system the player is traveling to. I have since that post been converting everything to DX11.

Your "universe model" sounds like a good way to go. There is no limit to how large your coordinate system is. You can make a __int64,__int64,float system that would give you 2^128km scale--that's freak'n HUGE! That would give you a distance of 3.6x10^20 of our galaxy side-by-side in each direction. If you did it further, you can't even imagine the scale.

Using your method, each "intergalactic space" could be the top __int64 and within the "interstellar space" would be the rest...... Man, that's not a bad idea you have.

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

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.

Now it's all a matter of perspective i believe, i do agree that there may be many other techniques just as efficient as octrees, but as a programmer i always preferred intuitive algorithms and techniques because most of the times these are also fast.

Thank you!

That is an awful lot of space.

Your scales are a good start but will need tuning based on actual scales. If you are operating on a meter scale for the 'planet scale', an Earth-sized planet is about 6.4 million meters which blows your scale.

You mention building new galaxies procedurally and drawing a quick rendering of the brightest stars. How many stars do you have in a galaxy? 100 billion? 500 billion? Or something game-like? Then you repeat for each galaxy, we've got over 100 billion galaxies in our observable universe.

Obviously rendering something lifelike on the order 10^22 stars for your background sky box is out of the question.

On the matter of quadtrees, when you are talking about such immense areas of sparsely-populated space you will be better off starting with hashes or similar for the enormous areas, probably hashing them again multiple times until you get down to clusters of interesting objects, then using an octree once you've got it pruned down small enough to no longer be sparse.

But still, having an illusion of infinity means both high repetition and sparse specific content. Few designs handle such things well. An Earth-sized world is difficult enough to fill with interesting stuff.