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.
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.