First, let me explain what I'm trying to accomplish. I just bough a new Android phone. Mmmkay. I downloaded a few of the 3D games and I'm impressed with one in particular, Air Arrack HD. I've actually been trying to be create something similar to this on plain old Linux & Windows, but to see it on my phone blew me away.

So I'm trying to figure out how level (3D mesh & stuff data) is drawn. I had a few ideas, so bare with me please! First, I figured on using a 3D tiling system because it would be very simplistic to access geometry in a similar fashion as it's 2D counter part. But not all the geometry was perfectly square so this kinda through me off from that idea. Basically, the only way I seen that working would be because all the geometry conformed to a nice grid structure.

2nd, I thought a BSP tree and frustum culling will work better. The geometry is partitioned with via BSP and I figured, technically, I would only have to frustum cull against the far or top planes using the BSP node's splitter plane as a guide. But what about side to side movement? In the example game above the player could move from side to side revealing more of the level that seams to be off screen. That would be a lot of geometry to waste time rendering. Would it be safe to assume that hardware could cull a few hundred polygons faster then I could?

Now I find my self trying come up with a solution that is a mixture of the two. The levels are pretty much strait from what I seen; like a drag strip. I just wanna know if I'm headed in the right direction here. I assume there are a few of you that have either built or worked on something similar to this. I would like your advice please...

Hey thanks for the reply man. You just validated what I was pondering on. I'm starting to think that a tree structure may be overkill or not as efficient. Unless the world/mesh in question also supports collision detection. In my case it doesn't; objects do, like you said. I'm thinking that a 2D grid can still be used. Each cell just points or references the geometry. They don't have to split it, it shouldn't matter if the geometry overlaps into other cells, it should only matter the in *this* particular region, this geometry is visible. I think for the few instances there will be overlapping geometry shouldn't hurt performance. so thank you again because you validated what I was contiplaiting this morning.

I'm left now with objects and texture groups. I'm thinking I should build a display list of the geometry and objects to render. I should only need to update the list when a grid position changes. Sort of like parallax scrolling when you render by offset and once the offset has reached a limit the map/grid index is incremented/decremented by what ever. I'm thinking it might hurt performance if I constantly change textures back and forth. Oh, and another thing; vertex buffers. Once I have a display list I need to render it using vertex buffers. I want to cut down on the state changes. I think rendering each cell separately would be wasteful and slow. If I have a display list, then I can lock and load each group using the same vertex buffer. I can see a down side to this because I would have to wait for the GPU to finish drawing the first group before I can load the second. So maybe two or a double buffered vertex buffer... so to speak. Using them in a streaming fashion I mean. Load 1, draw it. While it's drawing load 2. Hopefully, 1 is done, not draw two. Reload 1 with new data. Repeating this process until the entire scene is rendered. It should work and be fairly simple to implement, even in Java... hopefully.

Anyways... thank you!

Now that I'm think about it...
I will use a 2D grid that represents(in theory) such as a tile map. The grid is divided evenly by cells. Each cell points to the geometry in the level. At a later date, a node bases BSP tree may be added for collision detections. Cells also contain a list of objects. Objects are part of the level but not part of the level mesh. Hence, a level should have a lookup table for objects that it uses. Objects represent static or dynamic(animated) models that a level(in terms of disk file) may define internally or externally. An example would be special models that are level dependent such as a giant swinging axe vs. an object that represent an enemy or reusable mesh such as a switch. Each object has a unique ID and an instance ID. Using these two IDs each cell can easily distinguishable objects from each other.

I will incorporate a scene graph. The scene graph shall be a hatchery containing the level mesh(in viewable cells) and a list of viewable *currently* objects. When the scene is updates/moved view is updated in the same way a 2D tile map via integer map indices and scrolling offsets. Now I no longer require the view frustum to cull objects because what ever object(s) the cells point to are visible. I also use an object's IDs to block copies of the same object instance(e.g. object A overlaps cell 1 and cell 2, but is uniquely identified with the unique ID and instance ID). So it should be fairly trivial to rendering an object once.

The only thing I have left now is texture groups. Maybe I can handle this in a similar fashion as the objects. But, since cells change and can contain anything, this may not be as feasible as I'd like. Or... then again... maybe it is. Textures can have IDs and the land mass the cover may be used in place of the instance ID object's use. It should be very trivial to just render larger portions first, then to smaller ones. Hmm...

Most of all this computing can be done during developing instead of runtime. I should only have to draw what ever is in an array at such in such index/offset. This makes it very simple and fast so I'm not relying on any recursive structures like trees; just a simple array. With the once exception of a scene graph. Which is nothing more then a collection of lists and some logic precedence for oder of operations like translation, rotation, etc.. Simple! I still may use the double vertex buffer scheme though.

I think I may take your advice actually. I think it would be simple to just build a level the way I want it in some CAD. Then just subdivide the entire mesh using the tile-grid. This way I can just render each cell/tile separately as I would a simple 2D tiler. Sound simple enough. I may be able to optimize it a little by searching and removing tiles in the mesh that are identical with just one mesh.