# How to render infinite universe?

I'm curious what are the best practices in game development industry to render 3d universe?

To be more specific:

• The data points are given and static. Each point has position, color and size;
• The entire data set is much larger than available memory;
• User should be able to "zoom out" to see bigger picture at once;

The most naive approach would be to split universe into cubes and render only what's visible. I'm not sure how in this scenario should I implement the "zoom out". Should I precompute cubes for each possible zoom level? Or maybe there are better approaches?

I'm looking for technology agnostic solution.

• Do you plan on having some kind of a maximum view distance, or do you have some way of merging distant points so that you don't have to render them individually, or are the "points" opaque and arranged so that most of them will be hidden from any given viewpoint? Because if none of the above hold, I don't see any way to prevent the user from finding camera angles from which most of the points (or at least a significant fraction of them) will be visible at the same time. – Ilmari Karonen May 24 '15 at 19:46
• By the way, a bit exotic, but have you considered procedurally generated data? You don't have the benefit of custom crafting areas, but the upshot is that content is based on equations, not large amounts of data. With some creativity, that could simplify a lot of things (: – Alan Wolfe May 25 '15 at 2:09
• Zoom-out/zoom-in for an infinite universe could be similar to tracking relationships between two points on some Mandelbrot curve after zooming to different levels. At some level, you can lose precision and be unable to distinguish them or even locate them again. – user2338816 May 25 '15 at 4:47
• @AlanWolfe Custom crafting is still possible - the prime example being the old Frontier games, which had real star positions for some 1000 stars or so closest to Sol (including Sol and its actual planets and moons). You just make sure they are in places that are not procedurally generated, and add them as another "layer". – Luaan May 25 '15 at 13:13
• @IlmariKaronen yes, you are right. I have maximum view distance, and I thought I will merge distance points by following Ming-Tang's answer – Anvaka May 25 '15 at 23:06

This is based on my speculation and skimming through Celestia's source code.

Celestia allows you to fly around a planet and zoom out to see the whole galaxy. I browsed its source code and found it used an octree, a structure to recursively divide space into 8 octants.

The renderer would render the environment by traversing the octree, and don't traverse far objects deeply.

Celestia also keep track of absolute magnitude of an octant, where the absolute magnitude of an octant is based on the absolute magnitude of the stars inside the octant. If the octant is close together, Celestia renders the stars individually, and if the octant is far away Celestia renders the octant as one star of the octant's magnitude.

Also, there can be meaningful hierarchy attached to objects. For example, if you are close (radius declared in database) to a star, its planets are rendered. If a planet is close enough (a cutoff of pixels on screen), its 3D model is drawn.

Other space games I can name of are Orbiter and Kerbal Space Program, which are closed-source. I also looked into Frontier Galaxy, which has procedurally generated star map. There is a website analyzing how the game works by its disassembly: http://www.jongware.com/galaxy1.html

There's a number of pieces to this puzzle, each of which will provide a deep and interesting rabbit hole of exploration. Some of them are:

• Level of Detail -- automatically (or "manually") choosing detailed or simplified models, or even sprites or just dots, or for objects as they are further away.
• Culling -- choosing to only draw what's needed. This might be what's in the field of view (frustum culling), what's not hidden behind other things (occlusion culling), or other ad hoc methods. (@Alan Wolfe's answer describes some of the ways to organize your data that help facilitate culling.)
• Streaming -- pulling world-data from storage into memory as needed, if it doesn't all fit in memory at once
• Sky box -- very distant objects can be pre rendered onto a sphere that is at "infinite distance" from the camera.

And your own secret sauce will be what combination of these, and other, techniques you use, and when, based on your particular application needs.

Anything that is either hierarchical and/or sparse should help you out here.

There's a lot of empty space, so not having to use storage to represent empty space is a must. A typical hierarchical approach would be something like an Oct tree which recursively subdivides space into 8 smaller cubes, and you can store objects in the smallest cube that they can completely occupy.

An octree is also pretty good for you being able to query it for a list of all objects in a view frustum which will let you get a list of only the objects that are within your viewing angle and aren't too distant. A sparse solution could be something like a sparse grid where you can ask for information about any x,y,z location, but you only have to store information for cells that aren't empty space.

Other common hierarchical approaches used include bsp trees (they split space into 2 half spaces recursively) as well as k-d trees which do similar.

I personally think an octree could be a good start for you, making sure to subdivide only as deeply as needed so you don't waste memory on empty space. also, you might end up wanting a different solution for your static objects versus your dynamic objects.

Some solutions (like bsp) can be very efficient, but take a long time to construct so aren't usually a good choice for moving / changing objects.

Hope that helps, let me know if you have any questions about the details!