I'm currently making a multiplayer game set in a to-scale solar system. I'm building an Octree system where objects of varying sizes (players, people, asteroids, space stations) are placed into the octree based on their size, this means that a planet could end up at depth 7 but a character end up at depth 27, for example. If it helps to explain scale, Level 0 is 5 billion km wide in my tests, with the smallest node being 4656m at level 30. Yes, this results in an obscenely high number of nodes, but solar systems are 90% empty. The reason for the octree is so that I can deal with dense areas (asteroid fields, large battles) efficiently.

What I want, is for a player at any position within the octree to always be able to see large far away objects (planets), medium objects when closer (space stations, asteroid rings), and small objects when very close (other players, pickups etc), but do so efficiently.

Traversing the octree to the players depth, and collecting a list of potentially visible octree nodes along the way, doesn't satisfy my above requirement as very far away objects (planets) will not necessarily be in that traversal path (if they're in a different depth=0 octree node for example), but still should be visible. I also tried a typical LOD approach, testing each octree node based on a sort of screen-space error metric, but this failed in my tests as it wasn't traversing all the way to the lowest depth (eg 27) before failing the visibility tests.

The more I think about approaches, the more I confuse myself. Can anyone offer some sane insight into what method I would use to get my desired outcome? Maybe some sort of "always traverse" flag on nodes down to a certain depth where planets reside? not sure.

Any input would be appreciated.

>I think you'd need three octrees.

No offence but it sounds quite silly to me - all the point to use octree is to provide the hierarchical structure where each node points to child octree as deep as necessary; once node reaches the level of max-detalization or empty space it stops (becomes a leaf). As a rule the different levels of octree may need different structures to be memory efficient, usually the structure representing the leaf-level-nodes differs from nodes above but generally such "structure-tuning" may be applied for any octree level. Also, often it makes sense to have pointer-based-octree down to some level and below to have pointer-free-octree representation (flat octree); the pointer-based-octree addresses the child explicitly via pointers so empty sub-volumes does not have child sub-octrees, flat-octree requires some extra math to compute the position of child node and it can be done only if all sub-volume is represented as whole (there is no dead ends because of empty sub-volumes).

Stefan

Have you thought about the memory requirements? Or, perhaps the millions of calculations needed to maintain an octree of this magnitude? There isnt a reason to keep something this big in memory at all times. Normally, you would keep in memory only what is needed and dynamically load new data as needed.

>Have you thought about the memory requirements?

Fanny... Does my post really indicate that I have never thought about memory requirements?

>Or, perhaps the millions of calculations needed to maintain an octree of this magnitude?

Octree is just an index structure referencing to an actual data (polygons, voxels... etc); actual data should be stored in conventional flat/array form and it takes majority of memory, octree is a minor part unless developer with special abilities does the job. Once data is modified, octree update can be very fast as soon as data has reference back to correspondent octree leafs, in this case the time complexity of octree update can be T(n,N) ~= n*Log2(N) where "N" is the size of all data and "n" is the size of modified part of data - quite minor overhead. Implied logic it too complex to be implemented effectively solely on GPU. In fact, once data size is getting above some threshold multi-core CPU trashes GPU badly.

Stefan

Not sure who is who here? stefanbanev == vereor ? At any rate, OP suggests a depth of 27, which would mean the number of nodes in the octree would be in excess of 8^27 power, which I wont bother to write out. Vereor, I think you might want to lay out what you want and see which techniques line up and their implications.

For example, if you want to display a large area from a zoomed out view, you couldn't hold everything in ram because the costs would far exceed your available memory. As a person zooms out, objects from the scene should be removed, and as a person zooms in, the opposite should happen. So, your scene would need to be dynamic, loading objects as they come into view and then discarding them after some viewing threshold. Octrees and other tree type structures are used alot in many video games, but they generally only complicate things, not make then easier.
The point of a spacial tree such as an octree is simple, right? It divides the visible area into neat chunks, it sure sounds good to me --I like organization. But, whats the point? What I mean is, what does this give you? How does this make your job easier?
Could you use a quadtree?

If you allow zooming in and out perhaps there can be fixed zoom distances. For example, if a person hits the zoom out, it will zoom out to the solar system view, if he or she hits zoom in again, it would zoom in close to an orbital view of a planet. If a person zooms out of the solar system, it would show the galaxy. In this manner you could manage the number of objects in the scene and provide yourself some consistency --and an easier job programming.

I'm not stefanbanev, he's arguing his own points

My game is a First-person experience inside the scope of a full solar system. I never said that I would be holding everything in memory, each relevant octree node would be streamed to/from disk as necessary, depending on the active observers of the overall octree.

this implementation is from the view of the multiplayer server, so it needs to know about active nodes for a set of observers, unloading/loading nodes as those observers move through the world.

Nodes will contain entities and other information which will be loaded/unloaded at runtime, and also used to determine which entities to send across the network if they change, per observer. It will have other uses, such as limiting collision detection to nodes that observers can see (not the entire solar system).

Because it's true 3d space, a quadtree is the wrong choice, hopefully it's clear based on the info I've provided in the previous couple of sentences.

But, I'm always open to new ideas and if an octree is not the way to solve my problem then I'm willing to learn the best way to do it. So, I'll state my problem, and you can see if an octree is the best response to that, or if something else would fit.

Take a full-scale 3D solar system, place 15 players in it, ranging from floating by themselves to piloting large ships, add orbiting planets and moons and other environmental things (asteroid fields, comets), that is the data set I'll be working with. I want to efficiently organise entities to monitor for changes to update each player, but it must be the entities which matter. For example, a planet is very far away, but it should be always visible and updated to the player, but if a small cargo box is 150km away, it's not visible to the eye so definitely should not be part of the network updates.

One other thing to factor into this equation, is that players can dump objects anywhere in space, construct large buildings or ships, and generally populate things anywhere.


I hope that clears up any confusion and I look forward to your feedback.

[quote name='Vereor' timestamp='1310030946' post='4832183']Traversing the octree to the players depth, and collecting a list of potentially visible octree nodes along the way, doesn't satisfy my above requirement as very far away objects (planets) will not necessarily be in that traversal path

I don't quite understand this. Usually when you traverse an oct-tree, you visit all 8 children of a node, provided that they are visible, and repeat. So starting at the root, visiting it's 8 children, and their 8 (times 8) children, and so on, performing a visibility test for each node, how do some 'visible' nodes not end up being visited?
[/quote]

I figured I'd use propagating entity counts along the nodes to identify if they are worth visiting or not. So, if an entity is added to node B, which is a child of A, nodeB.EntityCount is increased as well as nodeA.EntityCount. A quick check on the entity count of a child will determine if it's worth traversing down that path or not.

The other idea is to only create child nodes if there's something to go in it, or it's (yet-to-be-created) children, so it would end up being a sparse octree, with only some children actually non-null depending on the currently loaded entities.

That's more or less the ideas anyway, implementation may show some issues.

I don't have answers to your questions, but I feel that storing planets (diameter tens of thousands kilometers) and space ships (size of 100's meters) in the same data structure isn't good idea, especially if your data tree would have 27 levels.

Ships with size of 100 meters will disappear from the sight pretty quickly when you move in astronomical scale. Actually, it might be difficult to find your enemy there if you don't have some kind of "scanner" telling where to look for them.

You didn't give much of background details but I wanna ask, how do you solve the coordinate accuracy problem in such a huge space?

I would store planets and other astronomical size bodies in a separate tree. I think that you'll need to have some kind of "local space" for cases where collisions may occur. Ie. If 2 or more ships (or asteroids) are in the same sector, you'll need to start checking for collisions.

Cheers!