Culling inner-cubes

[xDonny]

My game is coming along quite nicely. Right now I have a plane of cubes rendered (20x20) and performance is great. However, when I add a lot of cubes to the scene, the frame rate slows down and eventually it becomes unplayable.

I had tried to use picking to get objects from the scene that are currently "on top" but this is even slower (<1 fps).

Does anybody have any experience with culling interior objects like this?

I have generated a new test (10x10x10) and when you look at the center the framerate drops very quickly, but if you look at a glancing angle the framerate is fine.

All the objects share compiled-data with a single cube, the only thing that changes is the texture.

Thanks for your help again,

Donny

[Thomas.]

My first idea: Create 3 dimensional array of boolean, true if contents box, false if not. Use seed recursive algorithm and find outsides boxes and only them render...

Edit: 488 boxes will be rendered instead of 1000

[xDonny]

Thanks for the reply, I'll give it a shot.

Any other theories are still welcome!

[aZen]

Pretty much what I had to do with my voxel editor.

So what Thomas said is the easiest step (render only the outside "hull").

However you can improve it further by minimizing the amount of triangles that build the surface area. The only downside are hit detection and that you need to generate textures "on the fly". But it can drastically reduce the triangle count (e.g. for 21x21x21 voxel the outside hull would consist of 5292 triangles. After reduction it would only need 12 triangles!).

[xDonny]

So I tried the first Idea and I liked the result, it had a few bugs that I need to work out so I'm back to my original, (this time I'll make a backup before I go on these excursions ).

So what I tried was having 16x16x16 blocks, in each block only the top-most cubes were set to "visible". If a block on top is destroyed, the corresponding block underneath is set to visible, if there is a block beside it which isn't visible, that is set to visible. However by creating objects to do this instead of a boolean array, it turned out to be just as intensive memory wise.

[EDIT]
I was unclear above, the FPS was dramatically increased from my current model which I was very pleased. I also rendered all cubes currently visible. I was unable to make a working algorithm to detet hidden-faces. Therefore I was still unable to place as many cubes as I would like.
[/EDIT]

I'll try again with the boolean idea. Perhaps I can find some documentation on an algorithm to detect hidden-faces quickly

I like this triangle reduction idea. How would you go about it?

My Theory:

Have two worlds, the main world has the singular cubes but doesn't render them (for collisions), the second world is a copy, where I merge all of the objects and then draw the singularity(will this reduce faces automatically?)

I think that sounds good

The only problem with this is the memory consumption, on previous games I've had to expand the allowed heap. This hasn't hindered anybody from playing my games (that I'm aware, only around 50 unique devices have tried them)

Perhaps implementing both methods would be beneficial?

I'm thinking of a 3 dimensional array of booleans and integers, and an enumeration for the type (for setting textures on the fly)


Let me know what you gentlemen think,
Donny

[aZen]

So let me clarify some stuff.

First of all, I'm assuming that you're working on some kind of mine-craft style game. If that is not the case you would need to clarify. Secondly, the idea that Thomas had is actually not what I had in mind. I apparently didn't read his post carefully enough.

So here is the idea (I have implemented this and it is not super "easy", but certainly doable): You would need a class that manages the boxes, e.g. you can add and remove boxes (I'll call them voxel from here on to avoid confusion). This class can then be used to update your world (i.e. update triangles in the world) - you could use a refresh() function.

You shouldn't use cubes to render the voxels (since not all sides of a voxel might be visible), but rather determine which sides are visible and draw only these. Voxel that are "inside" have no visible side and are hence not drawn.

The tricky part is now to maintain a fast structure to keep track of the voxel that are currently in the world, which sides are visible and which triangles need to be changed. I have implemented this by updating the neighbors when adding/removing a voxel and also keeping a "toUpdate" list that indicates which voxel need updating.

The triangle reduction should then be implemented in a second stage (when what I just described is fully working). For that have a look at http://code.google.com/p/poly2tri/

Please let me know if you have any questions!

[aZen]

The triangle count in this scene was reduced by more than 90% (!). So if you have performance problems, hull triangle reduction is certainly the way to go.