I’m working on a multiplayer server design, and I’d like to generate a serverside scenegraph in the shape of an octree. I have several reasons for doing so which I’ll quickly outline before getting to the details of my question.
While I’m aware that a serverside scenegraph is often considered bad practice, I need serverside physics, ray casts, and a fast way to organize a large number of simulated objects so that I can do extremely fast, cheap, and approximate distance estimates between objects (so that network messages can only sent to clients within a variable interest radius from the object). Octrees in particular provide a handy way to handle the latter need, especially since large objects remain in nodes lower in the tree and thus can be quickly chosen as part of an interest set even if they are not technically within the interest radius. For example, A mountain might be 10 kilometers away, but it’s big enough that you want to know about it if you’re close enough to see the mountain. Unless you’re up close, however, you don’t want information about the castle at the base of the mountain cluttering up your network connection. Really, the interest radius doesn’t correctly determine what you’re interested in - you’re really interested in what’s within your interest radius + anything else big enough and close enough to care about.
In the interest of not needlessly reinventing the wheel, I’d like to use jME classes wherever reasonable. Since I really need the scenegraph for physics and for ray casts I’d like to keep octree organization in there too to make keeping everything consistent easier and less error-prone.
Now that I’ve (hopefully) justified why doing this rather silly-sounding thing isn’t perhaps as silly as it at first may seem, here’s my question: is an octree the best way to take care of this, or is there a more general/flexible way to do this that is preferable?
a) you do not at all need the scene graph to do physics, really. It’s just a crutch.
b) you don’t really need it for ray casts either.
c) you might find it way easier (and way faster) to use multiple levels of fixed size sparse grids. Octrees can be pretty horrible in the worst case for leaf neighbor checks.
Personally, I think a scene graph would also be a pretty horrible way to implement an octree. Ideally, you’d want something with a fixed set of children, something that was smart about splits, etc…
(Not to mention, if you aren’t implementing your own physics engine then you will likely be at the mercy of whatever it is doing to manage it’s broad phase.)
If you feel like looking at sparse grids instead then you can see the implementation in SimEthereal. It already does zone radius interest management though only with one layer of zone spacing (so far). I will need exactly the same thing you mention eventually myself so it’s always been on the roadmap.
If nothing else, it might give you some ideas. It has a very advanced system of syncing objects that can pack a lot of data into very small buffers… and uses a reliable UDP protocol for high speed performance.
@Ali_RS, thanks, I was not aware that Bullet had its own ray casting functionality. Unfortunately I won’t be able to rely solely on Bullet’s ray casting as objects that need to be ray-visible won’t always be in the physics space (even as static objects).
@pspeed, thank you very much for the information. As far as (a) goes, you’re right, I don’t need the scene graph to do physics.
I’m using jME’s Bullet build - I’m just extracting the native libs and then setting up individual PhysicsSpace instances the same way BulletAppState does (just integrated with my server’s ecosystem more tidily than cramming in an appstate would be - the server is not a jME application and runs its own heartbeat loop). You’re absolutely right about being at the mercy of Bullet’s broadphase, and I will freely admit that I failed to consider that (or considered it a long time ago and forgot about it ;)). However, physics computation is run in parallel to the heartbeat loop and other systems using a mechanism almost identical to the one used by BulletAppState while running in parallel mode. I do have a little bit more leeway than if I had to divide one tick worth of time between everything in the heartbeat loop (most systems are highly independent and can/do carry out their heavy lifting in a thread pool).
My biggest concern about setting aside the scenegraph is handling parenting transforms and ray casts myself. Entities in the world need to be parentable in a manner identical to jME scenegraph nodes. (Note: for ray casts, I can’t depend on Bullet’s ray casting for everything since some objects may need to be “ghosts” - non-physical but still detectable by rays). Computing transformation matrices to account for parenting isn’t that big a deal, but by the time I’ve implemented parent->child transforms, ray casting through a custom structure, and optional physics syncing it seems like I would have just reinvented the scenegraph wheel. If I have to do that, I’ll do it, but if there’s a reasonable way to avoid that and get the result I need I’d prefer to avoid duplicating that much functionality on my own.
You’re absolutely right - it’s messy. Right now I’m trying to alleviate that by putting 100% of octree logic in a control and having that control manage nodes itself. Right now the control actually creates the node that it manages. That’s kind of backwards, but I intended to make note that by convention these nodes are strictly not to be touched in any way except to attach the octree root to the rest of the scenegraph (although conventions like that are fragile and easier broken than kept).
My point in explaining all this is not to tell you that I’m right and I’m doing it my way - my point is to (hopefully) make it a little clearer why I’m setting out to do this in the first place since my first post wasn’t super detailed. I’m hoping that there’s some better way to do exactly what I want and that you’ll talk me out of making an octree out of scenegraph nodes because it is so messy and error-prone.
Thank you for linking the SimEthereal sources - I took a good look at the zone functionality. I must say… wow. In a million years I wouldn’t have thought of using bit twiddling to place objects into the correct zones. The BoundingBox/BoundingSphere code that I just wrote for determining the right octree level for an object is fairly efficient (no temporary objects, just addition/subtraction and logical operations) but I’m going to venture a guess that your bit manipulation would beat the socks off of it by a factor of 20x or more in a speed test, and that’s not counting the cost to move objects to the right node. I love how clean and efficient the sparse grid is. Seems like several levels of sparse grid zones could provide all the features of an octree at a small fraction of the complexity and runtime cost.
I’m especially intrigued by SimEthereal since I already wanted to use it for syncing physics-enabled objects. I have my own entity system (it’s kind of an ECS turned inside out - entities have agents that are unique to them and control them rather than the world having systems that processes all entities having certain components). Obviously if I can sync physics simulation and entity system updates directly with SimEthereal it would be a lot less overhead than tossing a scenegraph into the mix too. I’m going to take a good hard look at the SimEth-ES examples and see if I can come up with something better than an octree.
Do you mind elaborating on that? I haven’t been able to turn up any relevant information via either Google or my bookshelf, and I was not aware of any major shortfallings of octrees for neighbor checks.
For an octree leaf, if you want to check those objects against the neighbor leaf then you may have to traverse all the way up to the root and all the way back down in the worst case. Versus a grid where things are just a super-simple math function to determine which cell you are in.
A true octree would split infinitely which I can pretty much guarantee you aren’t planning to do. So once you’ve decided “No, this is the smallest I will split”… then you’ve just got a sparse fixed size grid that is implemented really inefficiently (log time for cell access versus constant time).
Yeah, I realized after my initial post that I may have been using the term “octree” a little bit loosely - I had planned to stop subdividing in the several tens of world units range.
Which when you think about it means you end up with a sparse grid but the only way to get to the cells is through octree traversal.
Quadtrees and octrees have their place but it’s generally when you have a pyramid of stuff. For example, a quadtree can be very popular for terrain imagery because you probably have imagery at every level on the way down… and when you don’t then you stop.
But for just organizing stuff, there is no advantage to subdividing space by arbitrary splits if you are just going to stop at an arbitrary level.
Ok, I think you’ve convinced me on using multiple levels of a sparse grid to group objects of similar sizes. I haven’t had time to investigate implementation details yet, but I can say now that I’d 1000x rather use SimEthereal than roll my own - especially since I already want to use it for physics synchronization.
This leaves me two big ticket items (that I’ve thought of so far) that I don’t get for free from the scenegraph anymore: raycasts and parent->child transforms.
If I’m visualizing this correctly, the cost to ray cast is linear in the number of items in the subdivisions of space that you need to consider. In terms of a multi-level sparse grid, that means repeating the ray cast at each level and considering each object in every grid zone intersected by the ray. I don’t see any obvious way to lower this time cost. My gut instinct is to use some sort of a bounding volume hierarchy, but we’ve already been through all the reasons why that’s a bad fit for this case. Does this sound like an accurate assessment?
I also don’t see any way around doing parent->child transforms except manually. I don’t like it, but without a scene graph that’s kind of my only option - and it’s a rather small price to pay all things considered.
My two cents: doing spatial operations in a large set of moving objects are a complicated problem. Physics in another hand is a another complicated problem. For game programming, most of the time we simplify things to mimic a real life behaviour or natural phenomena.
Do NOT think tooo much …better take a toolset, a library, any thing and try to run some lines of code before the headache and the old age comes
@atomixnmc, thanks for the link - I’ve taken a long look at Parallel Universe’s Quasar fibers, but I was not familiar with SpaceBase. It looks very powerful, and if I ever needed advanced spatial queries I will check it out more.
Very true, and it’s a bad habit I have. For the moment I’m going to get started with SimEthereal and see how far I get.
@pspeed, while studying SimEthereal’s code I realized that I probably do not need multiple levels of zone sizes at all. I assumed that an object could only be in one zone at a time and that the object’s center point would determine which zone it was in - meaning that large objects that intersect many small zones would only “pop in” when the observer passed into the zone that the large object’s center lay in. In hindsight, that’s a rather silly assumption and a poor design. This was why I planned to use multiple levels of zone sizes - large objects would be placed in the larger zone size levels and observers would be subscribed to all zone levels. However, while studying SimEthereal’s code I found that you already dealt with this problem with ZoneRanges, eliminating my need for multiple size levels. Of course you already know this, but I wanted to leave a note for others with similar needs.
