Rendering many small objects - voxel-like world

Problems building or running the engine, queries about how to use features etc.
Post Reply
User avatar
AndiNo
Halfling
Posts: 46
Joined: Wed May 30, 2007 7:57 pm
x 2

Rendering many small objects - voxel-like world

Post by AndiNo »

Hi there!
I'm trying to implement a game world similar to this one:
Image
Info: The player is able to dig into the ground.

I already have a plan on how to do the game logic but I didn't come up with a good idea regarding the rendering of such a world. As you can see the whole level consists of thousands of small cubes. Every single one of them can be destroyed at will. For rendering this world my ideas were:
(I haven't tested these so I can only assume they are too slow/bad)

1. Create an Entity for every single cube.
-> Of course not, batch count / memory usage much too high.

2. Create a huge StaticGeometry (SG) with all cubes.
-> Bad, because when a single cube gets destroyed the whole SG has to be rebuilt -> too slow.

3. Create more but smaller SGs by dividing the world in smaller parts, something like an Octree. The SGs have to be small enough so that the player doesn't notice the rebuild after removing a cube.
-> Bad, because the SGs have to be so small that there will be too much of them (high batch count again).

4. Find out every frame which cubes can be seen by the player, then create an Entity for all of those remaining cubes.
-> Still batch count too high?

What can I do to render such a huge amount of small cubes while still being able to remove/create a cube at any place?

Thanks for your attention!
esset
Kobold
Posts: 31
Joined: Mon Jun 14, 2010 2:53 pm

Re: Rendering many small objects - voxel-like world

Post by esset »

Im no expert but i honestly doubt that Ogre is capable of doing that. Mincecraft's engine is designed for that scenario and that one only afaik
User avatar
betajaen
OGRE Moderator
OGRE Moderator
Posts: 3447
Joined: Mon Jul 18, 2005 4:15 pm
Location: Wales, UK
x 58
Contact:

Re: Rendering many small objects - voxel-like world

Post by betajaen »

User avatar
AndiNo
Halfling
Posts: 46
Joined: Wed May 30, 2007 7:57 pm
x 2

Re: Rendering many small objects - voxel-like world

Post by AndiNo »

Thanks! I didn't use the term "cube" in my forum searches :)
User avatar
Kojack
OGRE Moderator
OGRE Moderator
Posts: 7157
Joined: Sun Jan 25, 2004 7:35 am
Location: Brisbane, Australia
x 534

Re: Rendering many small objects - voxel-like world

Post by Kojack »

Is anybody not playing minecraft these days?
:)
Here's my quick version I wrote at 1am last thursday, in about an hour:

Image

Image

That's 256x256x256 cubes (16777216 total) being rendered with 256 possible cube types, using only 3072 triangles and one batch. Frame rate dropped at bit, but this was my first attempt and there's no visibility code yet.

The way it's working is that I've got sliced the world into 512 planes per axis (256 facing +axis and 256 facing -axis). Each plane is 2 triangles, giving 3072 triangles total. So each face of each cube is shared by 65535 other cubes.
I've got 2 textures. One is a 16x16 texture atlas of tiles, which I "borrowed" from a minecraft mod page. The second is a 256x256x256 3d texture. I have a shader which uses the 3d position of each pixel to look up the second texture, take that colour and treat the green and blue channels as tile index values in the texture atlas. So if the 3d texture had 0x00000204 as it's colour, the matching cube would use the tile at 2,4 in the 16x16 atlas. It's based on a font shader I wrote a while ago.

Changing the map (digging or building) doesn't require any geometry changes. All you have to do is modify a pixel in the voxel texture to chang what cube is rendered at that location, give it the index of a transparent cube and alpha rejection will cull it out.

But 256x256x256 isn't really good enough. The overdraw is insane, since hidden cubes are always rendered. I've got some more ideas I'm going to try when I get time (damn it, getting minecraft then having Evochron Mercenary released a few days later means no free time).
I think my next attempts will be (just for the hell of it) geometry shader spawning of cubes (been meaning to try a geometry shader for ages), and raycasting through larger cubes (like 8x8x8) to simulate lots of smaller cubes. Plus I've got some ideas for visibility checking, but that will come later.

Minecraft needs boulders. I used to love making maps for Emerald Mine (awesome clone of Boulder Dash) on the amiga. :)
User avatar
AndiNo
Halfling
Posts: 46
Joined: Wed May 30, 2007 7:57 pm
x 2

Re: Rendering many small objects - voxel-like world

Post by AndiNo »

After reading your numbers I nearly fell of my chair. :shock:
So after all there is a *tremendously* better idea than all the ones I had. Unfortunately I only understood half of your explanations. Would you mind sharing some code, especially some having to do with those shaders? I have absolutely no experience in writing shaders, my OGRE/graphics knowledge only sufficed for my ideas mentioned above.

BTW, my face is still looking like this: :shock:
User avatar
Kojack
OGRE Moderator
OGRE Moderator
Posts: 7157
Joined: Sun Jan 25, 2004 7:35 am
Location: Brisbane, Australia
x 534

Re: Rendering many small objects - voxel-like world

Post by Kojack »

Here's a slightly easier to see pic, graphing a mathematical function using sand blocks. :)
That's the full 256x256 horizontal range, but the height of the peak is only around 128 at the moment (minecraft has a 128 height limit).

Image


And here it is viewed from the peak.
Image

But minecraft has a visibility of around 360x360, and does it in java, so I'm not happy with this version.
Code may follow, if I can get it working faster, clean it up and I don't try to cash in on the craze. :)

The annoying speckle pixels are z fighting where edges of the planes meet as a t junction (which shouldn't be done).
User avatar
AndiNo
Halfling
Posts: 46
Joined: Wed May 30, 2007 7:57 pm
x 2

Re: Rendering many small objects - voxel-like world

Post by AndiNo »

Haha, you could create an OGRE addon library which handles Minecraft-voxel-worlds ;)
Kojack wrote:Code may follow, if I can get it working faster, clean it up and I don't try to cash in on the craze. :)
I would use it even if it's as "slow" as it is now. But if you can make it faster (which you said wouldn't be hard) I could be persuaded to spend some money on this (although it wouldn't be hundreds of dollars obviously as I'm only a student).
Kojack wrote:The annoying speckle pixels are z fighting where edges of the planes meet as a t junction (which shouldn't be done).
Will you be able to fix these? I have seen something like this happen in Minecraft before, too, but only rarely.

Oh, and could you please post your computer specs so I can compare the performance to my system?

edit:
While thinking about optimizations I came up with these improvements (just to see if I understand your method right):
- In Minecraft you always stand in the middle of the "world", so you would only need to draw/update the planes which are facing your direction and no planes which are behind you. So you could bring the plane count down to 128+256+256 = 640 each frame.
- When you're not moving (specifically no new level chunks need to be loaded) you could calculate the texture of every plane once and then save it so no more calculations would be needed. Only some of them would be needed if new level parts get loaded and so new planes new to be drawn.
But seeing your graphics knowledge I assume you already thought of those, right? :)
peacemaker
Gnoblar
Posts: 15
Joined: Wed Sep 15, 2010 10:51 am

Re: Rendering many small objects - voxel-like world

Post by peacemaker »

Great job Kojack, I'd also really like to see the code for this!
LBDude
Gnome
Posts: 389
Joined: Mon Jul 26, 2010 10:53 pm
x 22

Re: Rendering many small objects - voxel-like world

Post by LBDude »

Hey I'm working on something similar. I'm using PolyVox (thermite3d.org). What I'm doing is doing it according to the One True Way in Thermite which is divide the Volume data into chunks (32 by 32 by 32 in my case) and ask PolyVox to extract the surfaces for me. I then create a Manual Object using the extracted surface which contains vertices and indices buffer (so it's super easy to use with Manual Object). I was worried a little bit about batch count but the performance is great, I get 600 fps. Okay I'm not finished yet I still haven't implemented the shader code which texturize the mesh using a texture atlas. So what kind of hardware are you running this on? I'm running this on a quad core AMD box with ATI 4870x2. I like your method but I may need to do things to the data on the CPU so I can't do what you are doing which is sampling on the GPU. For one thing I plan to have A.I be able to modify the volume data. Maybe I can do it all on the GPU. Or something with Geomtry shaders.

I will let you know about the performance once I actually finish it and throw some more test cases at it. My test right now I'm using the sample from PolyVox which renders a bunch of spheres and cubes.
My blog here.
Game twitter here
User avatar
AndiNo
Halfling
Posts: 46
Joined: Wed May 30, 2007 7:57 pm
x 2

Re: Rendering many small objects - voxel-like world

Post by AndiNo »

I'm still interested in any updates, too. Did you (Kojack) work any more on this? Or are you busy playing Minecraft? ;)
User avatar
Kojack
OGRE Moderator
OGRE Moderator
Posts: 7157
Joined: Sun Jan 25, 2004 7:35 am
Location: Brisbane, Australia
x 534

Re: Rendering many small objects - voxel-like world

Post by Kojack »

I'm still interested in any updates, too. Did you (Kojack) work any more on this? Or are you busy playing Minecraft? ;)
Busy teaching 3d maths, helping 4 different teams working on ogre based games, and playing some minecraft. :)
Plus I found an open source clone is already available, called Manic Digger: http://manicdigger.sourceforge.net/news
Oh, and could you please post your computer specs so I can compare the performance to my system?
I'm on a radeon 5870 and core i7 940, win7.

I'll play around with it soon, too busy so far this week.

I was worried a little bit about batch count but the performance is great, I get 600 fps
Cool. I really need to play with thermite sometime. I'm a voxel fan and the demos were awesome, but I never had a practical use for it. Now I have some ideas (work related) which would benefit from a cube based world.
LBDude
Gnome
Posts: 389
Joined: Mon Jul 26, 2010 10:53 pm
x 22

Re: Rendering many small objects - voxel-like world

Post by LBDude »

Yeah I basically have gotten together a quick test using PolyVox (Thermite is based on this), extracting my surfaces using it's CubicSurfaceExtractor. I've gotten a 512**3 volume to render decently at 200fps, and rendering around 1000 batches. Surprised at the performance given the amount of batches, then again I'm running a decent system. I will write some more test cases to test it. Before I do that I need to fix an off by one error with my texture coords.

I'm not making an exact Minecraft clone...actually I guess you can call it Minecraft clone because part of the game play consists of building things. But I also have some crowd code I've coded. I don't care though, I'm just trying to make the game I want to make and right now Minecraft's got a lot of things that I like. Plus Dawrf Fortress too. I don't care if people accuse me of copying them. So what!
My blog here.
Game twitter here
User avatar
AndiNo
Halfling
Posts: 46
Joined: Wed May 30, 2007 7:57 pm
x 2

Re: Rendering many small objects - voxel-like world

Post by AndiNo »

Hey, Minecraft copied from Infiniminer. So what? ;)

Could you upload a screenshot of your program? Do you only have single-coloured voxel-blocks or are they textured? Or is it entirely different? Can't really imagine right now :)
LBDude
Gnome
Posts: 389
Joined: Mon Jul 26, 2010 10:53 pm
x 22

Re: Rendering many small objects - voxel-like world

Post by LBDude »

Well I sort of have an initial implementation. Tomorrow I'm going to implement some procedural noise. Then after that maybe see if I can hack in the SSAO compositor. And after that? I need to start work on tower defense / zombie game-play.


512x512x512 world
http://imgur.com/iAx3R.jpg

256x256x256
http://imgur.com/6DxCT.jpg
My blog here.
Game twitter here
LBDude
Gnome
Posts: 389
Joined: Mon Jul 26, 2010 10:53 pm
x 22

Re: Rendering many small objects - voxel-like world

Post by LBDude »

I did some more work on it and added a simple generator using LibNoise. Also added in SSAO compositor. The world gen is not completely working yet, however, it does represent a typical scenario for a "Minecraft" like game. Also I only have a simple directional light implemented in shaders. I plan on getting better lighting soon.

http://www.youtube.com/watch?v=YUgSd8rwv1o
My blog here.
Game twitter here
User avatar
AndiNo
Halfling
Posts: 46
Joined: Wed May 30, 2007 7:57 pm
x 2

Re: Rendering many small objects - voxel-like world

Post by AndiNo »

This looks very promising! What framerate do you have when not recording any videos? Can you show the creation/destruction of blocks in a possible next video?
LBDude
Gnome
Posts: 389
Joined: Mon Jul 26, 2010 10:53 pm
x 22

Re: Rendering many small objects - voxel-like world

Post by LBDude »

For A 256**3 world varies between 90 to 600. For a 512**3 world varies between below 30 to 600. I could probably improve on this by doing some sort of LOD scheme, better batching, and occlusion. World generation for 256 world takes maybe 10 seconds for the entire thing. So doing it in "chunks" this is probably equivalent to what Minecraft is doing. For 512 world it takes at least a min (I think, I didn't really time this).

Oh yeah check some new screens with the Spherical harmonics shader directly from OpenGL orange book.:
http://imgur.com/Rqhx3.jpg
http://imgur.com/HJcVX.jpg

First thing next week I will add the ability to update regions. BTW, if you are interested I will upload the code at an later date. It's not too much ATM, really just using PolyVox, which has a nice and simple interface. :)
My blog here.
Game twitter here
User avatar
Kojack
OGRE Moderator
OGRE Moderator
Posts: 7157
Joined: Sun Jan 25, 2004 7:35 am
Location: Brisbane, Australia
x 534

Re: Rendering many small objects - voxel-like world

Post by Kojack »

That looks damn cool.


Here's another version I just got working.
There's no textures or lighting at the moment, I didn't want to make the shader any more complicated until I saw if it works. :)

Image
Image

So... what's different?
This time the 256x256x256 world is being rendered with only 92 triangles.
I created 8 cubes (2x2x2), each of which is 128m per side. Then I wrote a shader which performs raycasting through each pixel on the cubes, testing against a voxel texture. So each of my 8 cubes contains 32768 virtual cubes.

Having 8 huge cubes means there's poor frustum culling so framerate doesn't vary much. If I make the cubes smaller (so I need more of them, and each contains less virtual cubes) then culling can throw more away (I can reach 900+fps while looking at small regions) but the performance degrades when everything is within the view of the camera.
The raycasting is pretty horrible at the moment, lots of ifs and stuff which shaders hate. It's also performing 387 plane intersect equations and texture samples per pixel. I should be able to cut that way down now that I've got a working base.

The second pix is using what I think is the worst case for the polyvox style: a 3d checkerboard of cubes and gaps. If all cubes are only touching on the corners, there's no common faces to be eliminated. I estimated that just the index buffer of the extracted mesh would take up 1GB of video memory.
(2^23 cubes * 12 triangles * 3 indices * 4 bytes per index)
Mine is slower (and looks much worst), but only needs a consistent 64MB of video ram plus 96 triangles * 3 indices * 4 bytes.
On the other hand, mine ray casts the same if a cube is there or not, whereas the polyvox style would become faster when there's either bigger gaps or bigger groups of cubes side by side.
At least if I understand how it works, having never actually used it. :)
LBDude
Gnome
Posts: 389
Joined: Mon Jul 26, 2010 10:53 pm
x 22

Re: Rendering many small objects - voxel-like world

Post by LBDude »

Yeah. Well, I was going to test that but haven't gotten around to doing, since I figure in a real game situation you won't have that (but who knows, crazy people out there). And I'm not sure at what point the performance will drastically degrade due to having generating surfaces. I haven't really thought too much about it I guess I should. From what I understand PolyVox only generate visible surfaces, meaning that if the face of a cube touches air, then it is extracted (which means I have to modify it to take into account transparency. What about if I have a huge empty interior and I punch a single block out to look inside...hmmm). And I'm dividing the regions into 32x32 blocks, don't know how that play into the performance question for the 2nd case. I haven't even calculated the memory footprint yet. I was just trying to get something to work. Another thing, with occlusion culling one doesn't have to send all of it to the graphics card, especially with the 2nd case. The 2nd case a vast amount of interior would be occluded. Like I said, I haven't really thought about it too hard yet.

Other than that, I've seen another post on Gamedev.net which talks about this, and the guy implement does something similar to PolyVox, but he merges blocks that are the same.

WOw it's late.

BTW: I may use your method in the end. To modify the terrain I simply can queue up cube destruction commands for the GPU. A.I entities can do this too. Another thing would be pathin-finding. How would you do path-finding if all your data is on the GPU?
My blog here.
Game twitter here
User avatar
AndiNo
Halfling
Posts: 46
Joined: Wed May 30, 2007 7:57 pm
x 2

Re: Rendering many small objects - voxel-like world

Post by AndiNo »

I'm curious which method will be the better in the end or if both achieve similar results.
LBDude wrote:BTW, if you are interested I will upload the code at an later date.
That would be really nice! :)
User avatar
Kojack
OGRE Moderator
OGRE Moderator
Posts: 7157
Joined: Sun Jan 25, 2004 7:35 am
Location: Brisbane, Australia
x 534

Re: Rendering many small objects - voxel-like world

Post by Kojack »

Another thing would be pathin-finding. How would you do path-finding if all your data is on the GPU?
The mesh visualisation is purely gpu, but it uses a voxel texture to control where cubes are placed and what they look like. The actual world map I'd be using for physics/pathfinding would be the same thing, I just upload small chunks of it as textures for each region of the world. Changing the world requires updating only the voxel texture, no geometry has to change.

Next I think I'll try a geometry shader. I may even be able to get it to handle run length encoding of the voxel map. I've never used a geometry shader before though. Time to switch to the directx11 renderer I guess.
(We should probably move this discussion over to Using Ogre or somewhere, help topics tend to get covered up pretty quickly)
marchingcubes
Kobold
Posts: 35
Joined: Sun Jul 26, 2009 10:19 am

Re: Rendering many small objects - voxel-like world

Post by marchingcubes »

I wrote a minecraft->sauerbraten exporter, I've yet to experiment with large world sizes, but sauerbraten seems to do a pretty good job rendering minecraft worlds.

It pretty much evaluates its octree structure and creates a static polygonal 'shell' - removing anything non-visible. This would appear to be done by more or less flood-filling empty-spaces and filling in a shell around them. texture indexing would appear to be used, so the geometry could be rendered in a few batches. The octree structure makes it easy to do localised updates, at whatever granularity makes sense - but it has a number of drawbacks - mostly the difficulty of doing any kind of 'paging' of new geometry for really big worlds, as there is one octree and is encompasses the whole world, giving a practical limit of 1024x1024x1024 cubes - i believe there is a reliance on integer cube size - and its reliance on lightmaps for lighting, which break as soon as the geometry of the level changes. The code is kind of dense and I havent spent enough time with it.

http://www.minecraftforum.net/viewtopic ... 25&t=42602

My current thinking is to use a different shader that implements simplified dynamic lighting in place of the lightmapping, and use the existing co-op editing support to handle network-enabled destructible terrain and make a fun little 'blow up the monsters and scavenge the loot from the smoking craters' game set in the 'minecraft universe'. I'd like to wirte my own engine with al the bells and whistles in Ogre, but i'd also like to get it done in a few weeks so sauerbraten looks pretty good to me at this point.
Post Reply