Which data structure is right for the job?

Thanks for all the help thus far.

I was planning out an area of the world I'm going to have and realized that there will be heavily forested areas. The actors will either be in the forest walking around or flying above.

For the flying above I'd just plaster a canopy texture on some quads to make them look like trees and only properly render the trees that are very close to the player view.

What I'm wondering is what I should do with actors running around in this forest, is there an efficient way to handle it without killing rendering performance. Thinking back about dungeon siege, I don't remember any area with a decent amount of trees, then again I could be mistaken since the game wasn't that memorable.

I'm not really looking for code at the moment, just algorithms that can help in the various tasks.

PS. I'm not keen on limiting camera movement. I'd like the player to be able to see in which ever direction they choose.
 
I think that with a huge amount of trees your best bet is a good LOD scheme (including impostors), because it's not practicable to do any visibility culling, except for the view frustum. That way, you can still have some nice detail on the nearby trees while rendering, say, 100 of them.
 
I was thinking about culling and I figured, the best I can do is take the "normal" trees (straight trunks) create a rectangle which roughly underestimates the area the trunk ocludes and then not render anything that is behind that rectangle. I'm uncertian if this is worth the computaion.

I'm thinking the tiling scheme that I came up with prior to this wouldn't be that bad. The nice thing is that I could do a lot of geometry recycling, I could also embedded information about occluding sufaces (walls, floors, ceilings, doors, tree trunks...) in each tile and even portals within those surfaces. This would rapidly remove any surfaces being blocked by a wall. I'd also be able to put the polyies in order of shader and then depth, with minimal effort. I might being see this through rose colour glasses, I know that this scheme means a fair amount of stuff that isn't visible will be drawn unless I figure out a way to efficiently remove that.
 
Littlepenny,

I had a look. It's a neat scheme, but that's not what I was going for.

Right now, I'm looking at what I'll have to do if I want to draw and army.
 
As a side note, it seems kind of surprising to me that nobody has yet come up with a much better way of storing data for games. It most certainly seems possible, but nobody has yet to do it.

Just from the top of my head, it seems like it would be possible (although very complex to find out the specifics of implementation) to create an algorithm that would step through world-space objects, which are stored in some form related to position, in a form that usually results in rendering in the desired order (usually front to back). The challenge would obviously be in encoding 3D-position data into a 1D or 2D array (1D better...if it can be done). I imagine the technique would be somewhat related to swizzling.
 
Well,

I doubt creating "one structure to store them all" would be used any time soon.

1/ Graphics technology is changing too often to make a good prediction about the future: aka. it used to be super to cull every wall with bsp's etc in games like Doom ... now it's much much better to just send over everything you got and let the graphics card decide what to render.
2/ As CPU resources are actually still quite limited, people must consider what the specific needs for their storage are. [Fast inserts - Fast lookups - Low memory - ...] Compare it too sorting algorithms, there isn't an algo which is just better than all the others. (Well everyone knows it's selection sort ;) , anyway ...)

Maybe in the future when we don't need to worry about resources anymore we could unify the data storage, untill then, I will hold on to my octree ;)


Jurgen
 
Back
Top