Hello guys... I'm currently confronted with a pretty tricky problem (at least for me it's tricky9. My team is developing a game which has very specific requirements when it comes to scene rendering. I'm looking for an algorithm (quadtree, octree, ABT, something completely new...) We have a huge world to render so it's out of question to have all the data in memory all the time, thus we have to add and remove scene nodes all the time, depending on player movement. Since this will happen very often it needs to be a cheap operation to add or remove geometry. The world should be continous. This means no "Loading..." screens. Except for maybe the initial one upon entering the game. We have mixed indoor and outdoor geometry. I should be able to stand in the tower of a castle, look outside and fire an arrow out the window to the guy standing on the hill right behind the castle walls. I should also be able to stand inside a house and shoot an arrow through the window at the guy standing in the other house across the road. The outdoor visibility needs to be pretty far. Flying will also be possible so large stretches of land can be seen (of course we'll implement LOD in some shape or form so that far away things are reduced or omitted completely). A nice bonus feature would be deformable geometry so you can shoot holes in walls and dig tunnels and all that but that's not a must. (Though it would be extremely good!) Then again I don't know whether this actually has anything to do with the scenegraph algorithm at all... The world data is stored in a semantics based tree (the apple is a child of the bowl is a child of the table is a child of the house is a child of the district is a child of the city is a child of...). Yea, that's about it. Is this achievable? Is this even reasonable? Has it been done before? How can it be done? I hope I have expressed myself clearly enough... If not: ask! Oh, and please be gentle... I'm kinda new to all this... Thanks a lot in advance!

Yikes, that's pretty ambitious [grin]

Have you read Scott Bilas's paper on how they achieved the continuous world in Dungeon Siege? If not, you should do that right now.

This is also bretty much what is supported by dVPS, if you have a "bit" of money to spend on this.

Thanks for the answers so far! Currently reading that article on Dungeon Siege.

I actually forgot one requirement:
The world data is streamed from a server and might change dynamicaly so it can not be precompiled!

Oh yea, as of now I don't have *any* money to spend on this. Maybe we'll find sponsors in the future, maybe not. So I better don't count on it...

Oh, it will need to be precompiled. It'll just have to be precompiled very quickly such that you can make changes and have those changes available within a matter of seconds. You won't just be streaming vertex data from the server to clients.

This is MMO, isn't it?

Yes, it's MMO and no, we won't be streaming vertex data. The actual media is stored client-side, just the structural info is stored server-side. Maybe terrain, too... but any complex meshes, textures, etc. will be stored on the client and yes they will be precalculated. And the changes have to be available _real_ fast! Either that or we preload so far that we have time to actually do some precalculating and then swap the world model on the fly (which will be quite a hard thing to do, especially memory-wise).

BTW: With precalculated I mean things like geometry splitting the way it is done in most - if not all - binary tree formats. Of course lightmaps and things like that will also be prerendered by our artists...

How about the tiling approach Scott talks about in that paper, then? Perhaps not going for the full 2D thing they've got, but still, borrowing the idea.

You can basically set up a number of predesigned hierarchies. Say you're going to want a number of skyscrapers; you set up your skyscraper and all the objects within it in a hierarchy and save it out. When the server then needs to tell the player about a skyscraper, it can just point them to the hierarchy they already have.

Of course, you don't want a load of hierarchies that are all the same. So, when you transmit from server to client to say "There's a skyscraper here," you also transmit delta information - explaining how this particular hierachy is different from the 'template.' If you've got a load of templates already set up you can apply differences pretty quickly - "Replace all oak_table subtree instances with pine_table_with_fruit" instances, the server can say.

A more common example might be trees - "Replace branch_1 with branch_3" for this tree, "replace branch_6 with branch_2 and branch_3 with branch_5" for this tree.

Changes to the environment are thus naturally simple - you just change the deltas you send out.