Octree with distant but visible objects

I think you'd need three octrees. The parent nodes need to have some idea of what size objects are in them for that to work. Otherwise, you're wasting the whole point of the octree.
1. Different octrees for each size object. Then you just calc the dist to the node from the player before checking, compare with the size of objects in the octree, and quit if you're low enough. The downside to this is that you need to have preset octree sizes. This shouldn't really be a problem though
2. Similar to 1, but with only one octree, and you also store a bit in each node for each size you have, and give each their own cutoff for node depth/distance. Sill has limited sizes though.
3. Just don't have a cutoff for depth. Test any objects that pass he octree test based on their size and distance as a second culling step, and maybe replace culled objects with imposters to prevent popin. I'm not sure how many of each kind of object you have, but this doesn't seem that inefficient...

Anway, your third paragraph makes me wonder if you're using the octree correctly, unless you're explaining in badly and I'm reading it badly.

>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? 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? I have seen many people want to use a spacial tree just because they thought it would benefit them to divide their world up --and everyone else does it, right? I thought the same and wrote an octree that has extremly fast find/insert/remove, but i stopped writing the code after seeing it just complicated everything.
Could you use a quadtree? Or make up a different type of way to divide your viewing area?

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.

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.

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? Can you explain this part of the problem?

[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!

[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? Can you explain this part of the problem?
[/quote]

>Usually when you traverse an oct-tree, you visit all 8 children of a node

Well, apparently it is not necessarily for the ray-octree-traversal since ray may cross some subset of 8 sub-volumes so no need to validate all 8 of them. If you just scan octree (to find min,max, to update octree etc...) then it makes sense to look through all 8 sub-volumes.

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? I have seen many people want to use a spacial tree just because they thought it would benefit them to divide their world up --and everyone else does it, right? I thought the same and wrote an octree that has extremly fast find/insert/remove, but i stopped writing the code after seeing it just complicated everything.
Could you use a quadtree? Or make up a different type of way to divide your viewing area?

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.

> [color=#1C2837][size=2]At any rate, OP suggests a depth of 27, which would mean the number
[color=#1C2837][size=2]> of nodes in the octree would be in excess of 8^27 power,
[color=#1C2837][size=2]> which I wont bother to write out.
[color="#1c2837"]

[color="#1c2837"]For such sparsely populated volume as space 99.99% of volume is empty the number of leafs is very low.
[color="#1c2837"]

[color="#1c2837"]However, 27 levels are not enough to represent solar system if lowest level represent 0.1km then 44 light-second volume can be indexed (8 light-minutes is the distance from Earth to Sun), besides the diff data structures for diff levels are advisable (see my post above).
[color="#1c2837"]

[color="#1c2837"]Stefan
[color="#1c2837"]