Which data structure is right for the job?

Saem

Veteran
I'm starting to mess around with game coding. I've come up with what I want to achieve. I'd like a Dungeon Siege-esque game. Continious worlds, indoor and outdoor enviroment, with a simillar pace and fairly large viewable distances - standing beside a guy and firing arrows looks dumb.

I'm right now stuck on what I should use to store the world vertices/polygons. I've looked at BSPs, kD trees -where k = 3, a little bit at quad and oct trees and came up with a method of my own.

The world will be partitioned into cubes so that they can be loaded and unloaded as needed so everything seems continious.

BSP's would be an easy task to implement, but this is better for indoor enviroments and don't really suit outdoor enviroments. At least that's my impression.

kD trees seem to be in a simillar category as BSPs, they take up more memory -which could be a problem for me- but I've seen some simple ray casting that can be done with them which can do some fairly good HSR.

Oct and quad trees seem to be pretty versitile, though I'm not sure the back to front nature of poly gone list generated or the radix sorting of said list is a good idea. If I wanna push a large number of polies I could be in a fair bit of trouble, even though radix sort is a linear algorithm.

The other idea I had was to further partition the large cubes into smaller cubes. They'd be 3D tiles of sorts. Each cube would know it's 6 neighbours - if it has that many. I'd track where the view port and which cubes where in the frustrum. Any cube partially within the frustrum or fully would be rendered. There would be hints within each tile that would tell the frustrum culling algorithm whether to avoid certian tiles because there is a block floor, wall, ceiling or some other plane - basically the plane information would be stored and the culling algorthim would work with that. Inside the tile I'd probably use a BSP to quickly get a list of polies that would go into the list of polygons to be rendered. Since the frustrum culling algo would work near to far, the rendering would be roughly front to back. The problem is that I believe I'll be missing out on a fair bit of culling across cubes. I'm not sure if this is worth it but from my understanding front to back rending has rather large performance benifits that could dwarf any possible losses.

I'd like the peoples input on my various comments, whether I'm barking up the wrong tree or missing some vital information. Thanks in advance, if I'm slow to reply I apologize in advance. I'm currently away on a rather long trip and have a rather slow a limited time on the internet.
 
OK, so you want Black & White level of zoom with Dungeon Siege style gameplay.

The tile system you describe is basically what neverwinter nights uses, and it can't take tons of detail from far away. In fact, it's horrible for large outdoor areas, as you end up with vertices between tiles you hardly ever need. I dunno, maybe if you didn't barf stencil shadows all over the place you could get decent performance out of it.

For a huge performance boost, I'd recommend using octrees but doing an ultima style fog of war where you cull scenery based on the player's character's perspective (i.e. stuff the character can't see gets fogged out). I don't know how much this will piss off your players. I'm lousy with gameplay. (Did diablo do this?)

There's also the quake2/3 style of things where you have a bsp with a visibility list on top of it. You can get some incredible speeds with that combination, and it's easy to implement (hell, you could even peek at the now GPL'd quake2 source), but visibility lists for huge outdoor areas can take ages to compile.

Other than that, you're going to have to come up with some sort of dynamic level of detail system.

This time next week you'll have more experience with this problem than I do, so keep us posted :p
 
The tile system you describe is basically what neverwinter nights uses, and it can't take tons of detail from far away. In fact, it's horrible for large outdoor areas, as you end up with vertices between tiles you hardly ever need. I dunno, maybe if you didn't barf stencil shadows all over the place you could get decent performance out of it.

I don't think I'll be barfing. I might, but I'll try and do something nice and cheesey at first, for shadows that is.

For a huge performance boost, I'd recommend using octrees but doing an ultima style fog of war where you cull scenery based on the player's character's perspective (i.e. stuff the character can't see gets fogged out). I don't know how much this will piss off your players. I'm lousy with gameplay. (Did diablo do this?)

Hrm, I'm guessing you're talking about basically cutting off rendering after a certian distance. Yeah, I'm going to do that, I figure when things are too far away, nobody will really notice.

I'm doing more research on oct-trees, they sound promising now that I've figured them out a bit better. Front to back seems possible with them, just the material I was using was all about making the heedless painter method suck less.

As for an LoD system, I'm still banging my head. All I can come up with is static geometry LoD AKA geometric mipmapping. But that costs a fair bit of RAM. GRRRRR!

Oh well, maybe I'll go see if someone came up with a way to efficiently do progressive meshes. Or at least that's what I think they're called.
 
Saem said:
Oh well, maybe I'll go see if someone came up with a way to efficiently do progressive meshes. Or at least that's what I think they're called.
Outdoors? Perhaps you need something like ROAM. (Try google for more links)
 
Thanks, Mr F. ;)

I can't believe I didn't think of that, it's one of the things that was mentioned in the terrian rendering article that I put up.
 
Forget ROAM. Just split your world into chunks and sort them by shader. Then generate a quad tree or kd-tree if you like and use that to do your pvs. ROAM doesn't scale well on modern hardware.

Depending on what your minimum specs are and when the game is coming out, you could also use displacement maps + mipmapping to get "free" LOD.

I wouldn't get too caught up on trying to make it super fast. Just get it working first, then worry about speeding it up. Of course it helps to have some foresight so you design your code/data structures properly for optimization later on.
 
*snip*

Hrm, I'm guessing you're talking about basically cutting off rendering after a certian distance. Yeah, I'm going to do that, I figure when things are too far away, nobody will really notice.

*snip

No, that's not what I mean at all. Most people do scene culling against the camera frustrum. What I suggest is culling the scene based on the character's line of sight (i.e. if no one in your party can see it, you can't see it either). A lot of the old Ultima games did this for the sake of gameplay. For an eye in the sky view hack and slash, it can provide performance increases, as more geometry gets culled than if you were culling off the camera frustrum alone. Of course, you have to come up with some kind of transition effect for the edges of culled scenery. I'd recommend using a pixel shader that checks for whatever color you cleared with (clear with bright pink) and adds a smoke effect in its place, or if shaders aren't your thing, just blend out edge triangles.

It makes the game a lot less pretty when you're outside, but it allows you to add really cool ambushes that the player would otherwise see from a mile away. It also makes dungeon crawling a lot more frightening.
 
saem,

when designing your world's access scheme just keep in mind you generally have two rates of change of visibility locality - let's call them fast and slow locality change. the fast change is determined by the view frustum orientation alone, and it's fast because your character turns around and you have a completely new view locality within a fraction of a second. oth, slow view locality changes naturally depend on the slower transitions in your world - like the character walking/flying (overall moving from point A to point B) in your world.

bottomline being, it's usually beneficial if you provide a robust spatial partitioning scheme for the slow locality changes and leave the fast locality changes to be handled by the frustum clipper alone.
 
Sounds like Portal Rendering.

Sectors are for slow locality changes, and frustrum for fast locality change.

Problem is, it's not really well suited for alien/fantasy landscapes.

Hopefully an Octree allows you to find inside view frustrum nodes fast, which works for your fast locality change, however I don't see how you could handle slow locality change for terrain, and I'm not sure making the difference is usefull...
 
Ingenu said:
Sounds like Portal Rendering.

Sectors are for slow locality changes, and frustrum for fast locality change.

yep. that's an example of what i meant.

Problem is, it's not really well suited for alien/fantasy landscapes.

yes. portal rendering is not suitable for outdoor environments in general. but the principle still holds.

Hopefully an Octree allows you to find inside view frustrum nodes fast, which works for your fast locality change, however I don't see how you could handle slow locality change for terrain, and I'm not sure making the difference is usefull...

generally speaking, making the difference is useful as it allows you to differentiate between 'heavy' visibility state changes (associated with the slow view locality changes) and 'light' visibility state changes (associated with the fast view locality changes).

of course, you're point is valid - you could embed your slow locality tracking within the fast locality tracking sheme (given that such is present). but that usually makes the fast locality tracking scheme heavier (as it has to keep thack of the complete visibility state, rather than being concerned only of the 'more volatile' state components) which sortof defies the purpose of the fast locality tracking scheme - to be fast.
 
I agree, having two simple (and so fast) algo is best than an heavy one.

Unfortunately I don't know any way to care about arbitrary landscape/terrain with two algos...

Do you have any hints, links... ?
 
Ingenu said:
I agree, having two simple (and so fast) algo is best than an heavy one.

Unfortunately I don't know any way to care about arbitrary landscape/terrain with two algos...

Do you have any hints, links... ?

unfortunately i don't know of a universal, arbitrary landscape (i.e. having both closed areas and terrain patches) solution either. i'v worked on some closed areas and some terrain algos but none of them has turned out to be particularly landscape-agnostic :) when the need arises one comes up with a genuine mix of the two.

but here's a sort of a hint. think tiled terrain where the tile is of magnitude several times the view volume, and each tile has a unique, large base texture (e.g. 2k*2k). regardless of what technique you use to solve the fast view locality problem, this technique doesn't need to be aware of the base texture state (hence, track it and be concerned of base texture swapping) while at distances sufficiently far from to the tiles borders. of course, you have to show some inventiveness at close proximity to the tiles borders, but that's another matter.

ed: sorry if the original post sounded uncomprehensible at places - it was written in a haste, as i was too busy with my task at work.
 
Fresh,

Of course it helps to have some foresight so you design your code/data structures properly for optimization later on.

I'm trying to lay a good foundation.

Just split your world into chunks and sort them by shader. Then generate a quad tree or kd-tree if you like and use that to do your pvs.

I'm trying to kill too many birds with one stone, I guess you're right, time to use the right tool(s) for the job(s).

Depending on what your minimum specs are and when the game is coming out, you could also use displacement maps + mipmapping to get "free" LOD.

I think this is what I'm goingto go for...

minimum: GF1
recommended: Radeon

Runitai,

It makes the game a lot less pretty when you're outside, but it allows you to add really cool ambushes that the player would otherwise see from a mile away. It also makes dungeon crawling a lot more frightening.

Ah, this will simplify a few things, Thanks.

darkblu,

The fast and slow visibility locality helps make a lot of sense out of the problem. I'm going to read a few more papers about SP data structures and see if I can find anything that really suits my needs. If not, I'll try stuff until it works. ;)
 
Simon F said:
Outdoors? Perhaps you need something like ROAM. (Try google for more links)

Wow! That paper says the method allows the rendering of the incredible 6000 triangles per frame at 30 fps!!! :LOL:

A GF3 can easily cope with 300.000 triangles per frame at 30 fps...
(Unlike the GF4Ti which has twice the vertex-processing power.)

I don't know how well the algorithm is scaling, but you can easily get heavily CPU limited when you'd try to optimize for todays videocards capabilities.
 
Hyp-X said:
Simon F said:
Outdoors? Perhaps you need something like ROAM. (Try google for more links)

Wow! That paper says the method allows the rendering of the incredible 6000 triangles per frame at 30 fps!!! :LOL:

A GF3 can easily cope with 300.000 triangles per frame at 30 fps...
(Unlike the GF4Ti which has twice the vertex-processing power.)

I don't know how well the algorithm is scaling, but you can easily get heavily CPU limited when you'd try to optimize for todays videocards capabilities.

Exactly. ROAM is totally outdated for todays' video cards. I can render a landscape faster by sending the whole thing to the card as a tristrip, than I can by doing a ROAM implementation (in general). I came to the same conclusion when doing LOD for models. Since I had to do the LOD reduction of the models on the CPU, the GPU wasn't doing anything.

Didn't Abrash say that early optimization was the evil of programming? :)
 
Hyp-X said:
Simon F said:
Outdoors? Perhaps you need something like ROAM. (Try google for more links)

Wow! That paper says the method allows the rendering of the incredible 6000 triangles per frame at 30 fps!!! :LOL:

A GF3 can easily cope with 300.000 triangles per frame at 30 fps...
(Unlike the GF4Ti which has twice the vertex-processing power.)

I don't know how well the algorithm is scaling, but you can easily get heavily CPU limited when you'd try to optimize for todays videocards capabilities.
The original poster asked for a way of doing LOD with terrain and I gave him a pointer to something that allows a continous change of LOD.

As for speed, ROAM has been around for a while and so the figures quoted will naturally date, but FWIW, you wouldn't have to change the LOD with every frame. That should reduce the work load considerably. Secondly, I don't see why it wouldn't adapt reasonably well to an indexed triangle system-progressive mesh cross, which should work efficiently with the most recent batch of graphics chips.

fresh said:
Exactly. ROAM is totally outdated for todays' video cards. I can render a landscape faster by sending the whole thing to the card as a tristrip, than I can by doing a ROAM implementation (in general).
Tristrips are also outdated. Don't you know that optimised indexed triangles are the flavour of the month? ;-) (Seriously though, I saw a great paper on this: "Universal Rendering Sequences for Transparent vertex caching of progressive Meshes". It appears to better than the optimisation methods that are out there in that it doesn't have to be tailored to one particular HW configuration.)

Didn't Abrash say that early optimization was the evil of programming? :)

If he did, then he was paraphrasing/plagiarising Tony Hoare/Donald Knuth. The quote, as I understand it, is "premature optimisation is the root of all evil". (Ahh! I just found the full quote: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." )
 
Simon F said:
Tristrips are also outdated. Don't you know that optimised indexed triangles are the flavour of the month? ;-) (Seriously though, I saw a great paper on this: "Universal Rendering Sequences for Transparent vertex caching of progressive Meshes". It appears to better than the optimisation methods that are out there in that it doesn't have to be tailored to one particular HW configuration.)

Yup, indexed tristrips are awesome. Too bad my main platform *cough*POS2*cough* doesn't support them. Well.. not natively anyway. Thanks for refreshing my memory on that evil optimizations quote :D
 
Didn't Abrash say that early optimization was the evil of programming? :)

If he did, then he was paraphrasing/plagiarising Tony Hoare/Donald Knuth. The quote, as I understand it, is "premature optimisation is the root of all evil". (Ahh! I just found the full quote: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." )

Just imagine having written a huge piece of code without optimization in mind just to find out, that it has to be redone from scratch to get good performance. I think Abrash was rather thinking about inner loop and assembly based optimization when he said that.
 
Barnabas said:
Just imagine having written a huge piece of code without optimization in mind just to find out, that it has to be redone from scratch to get good performance. I think Abrash was rather thinking about inner loop and assembly based optimization when he said that.

that, my friend, is achieved through modularization of the code, i.e. one can write as unoptimal code as one wishes, but as long as modularity is preserved, i.e. it's not just a 'huge piece of code', then subsequent optimizations are not a problem at all ;)
 
that, my friend, is achieved through modularization of the code, i.e. one can write as unoptimal code as one wishes, but as long as modularity is preserved, i.e. it's not just a 'huge piece of code', then subsequent optimizations are not a problem at all


Amen brother!

But down to optimization I must say I am still amazed with the level of code flow optimization that some programmers of an age that should know better (maybe still remembering too much of 6502, 68xxx, 086, 286, 386 assembly era), that spend days optimizing code with obvious flaws in their memory access concepts.

These days, focus on memory access 1st and almost all other optimizations can take a back seat. (Yes a generalization but I just wish people would know their system limitations!!!!).
 
Back
Top