Meshing in a Minecraft Game (2012)

http://0fps.wordpress.com/2012/06/30/meshing-in-a-minecraft-game/

by rocky1138 • 13 years ago

70 17 13 years ago

0fps.wordpress.com

exemd2• 13 years ago

In practice you need a texture atlas (http://en.wikipedia.org/wiki/Texture_atlas) to reduce number of meshes. But if you use texture atlas you can't combine surfaces like in the article.

The solution is to create 1 dimensional texture atlas like this: http://manicdigger.sourceforge.net/webgl/data/atlas1.png. Then tile in only 1 direction. Minecraft does it and I first read about it in one of Word of Notch posts - http://notch.tumblr.com/post/176620207/i-rewrote-the-tessela....

It's good enough. Manic Digger (http://manicdigger.sourceforge.net) has great framerate at Pentium 4 and Geforce 2 MX.

But there is one problem: in mipmaps there is bleeding between individual textures. The solution is to use:

     glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAX_LEVEL, 4);

It's good on desktop, but there is no GL_TEXTURE_MAX_LEVEL on OpenGL ES and WebGL! I guess it must be done with custom mipmaps or with a pixel shader?

simias• 13 years ago

Very insightful, thank you.

Are there no alternative to texture atlases? It seems weird to restrict yourself to merging in only one direction just because the representation of your texture won't allow it.

As for the bleeding, I suppose it's because the scaling kernel overlaps between the tiles in the atlas? Won't reducing the level of mipmapping degrade overall performances?

It seems weird to me that there's no better hardware support for texture atlases if it's so popular.

pandaman• 13 years ago

Modern hardware does not need texture atlases as it can use a different texture for every pixel. Texture atlas is a workaround for the API that only allows one set of textures per primitive and imposes a huge overhead on each primitive at the same time (e.g. OpenGL, DirectX).

mbel2• 13 years ago

In practice you need a texture atlas (...)to reduce number of meshes.

I believe you meant "to reduce number of texutre swaps"? Otherwise I fail to find how texture atlas is helping in reducing number of meshes in the drawn scene.

But if you use texture atlas you can't combine surfaces like in the article.

Actually you can, pixel/fragment shader can be used later on to transform texture coordinates just before the texel value will be fetched (obviously this is only possible if you use shaders, but most games nowadays do).

NickPollard• 13 years ago

I think he's suggesting you need a texture atlas if you have multiple terrain types, so that different areas of the merged-quad mesh might need different textures applied to it. You could get around that with multiple texture lookups and shader work, but the atlas is probably better most of the time.

exemd2• 13 years ago

I mean it reduces number of glDrawElements or glCallList calls.

If you have 256 different block types in 1 chunk, using texture atlas there's only 1 mesh instead of 256 different meshes.

https://docs.google.com/viewer?url=http%3A%2F%2Fnvidia.com%2...

atesti• 13 years ago

Wouldn't it be possible to apply a pixel shader that does the tiling even though there is a texture atlas? Then tiling would be possible in both directions! The pixel shader would have to do the wrapping of u and v. Fabian Giesen (rygblog) wrote at http://fgiesen.wordpress.com/2011/07/01/a-trip-through-the-g... "Some of the API state may actually end up being compiled into the shader – to give an example, relatively exotic (or at least infrequently used) features such as texture borders are probably not implemented in the texture sampler, but emulated with extra code in the shader"

picomancer• 13 years ago

You certainly could, but this trades off fill cost against polygon count. I.e. you're using more complex calculations per-pixel for a smaller number of per-vertex/per-polygon computations.

It'd be interesting to look into the question empirically of whether this optimization would be worthwhile.

Also it depends somewhat on the specifics of the application. Two factors come to mind:

(1) Draw distance (drawing many faraway polys that are only a few pixels on-screen probably favors poly-count reduction more)

(2) Extra pixel shader complexity. If you're doing fancy per-pixel stuff with lighting or shadows or whatever, your optimization should become more attractive, because starting with your optimization and adding that extra stuff reduces the percentage of the per-pixel computation that's spent on your optimization.

simcop2387• 13 years ago

You could probably deal with this by using a little extra space in the texture atlas

I don't know how well non-power-of two texture coordinates work in GLES and WebGL, but you could put a single column of pixels from the other side of the texture on both sides.

say you have ABCD and so you store, DABCDA, it'd use up some memory but could result in a speed boost since you could likely avoid breaking the normal mipmapping and such. I don't think you'd have to go as far as having half the texture on either side, but it'd be worth experimenting.

willvarfar• 13 years ago

In C&C Tiberian Sun the voxel models were stored - and drawn - from a RLE sparse array.

And we used the same data-structures in the modder voxel editors.

So its not really an 'open question' as the article says, more just an obvious step.

pavlov• 13 years ago

For anyone looking for an advanced sparse voxel data structure, there's OpenVDB developed by DreamWorks Animation:

http://www.openvdb.org/

It's developed for film applications which naturally have a different set of requirements than realtime game engines. But as PC performance grows, the solutions developed for film rendering will become more directly adaptable for games.

ginko• 13 years ago

This completely ignores the problem of T-vertices.

andrewflnr2• 13 years ago

What? Minecraft "voxels" are huge. And then the cubes on the creatures are a different size. How is it not just using meshes to start with?

bajsejohannes2• 13 years ago

Because there are order of magnitude differences between rendering each voxel in a dense landscape compared to just the borders.

Consider a cube of 10x10x10 voxels. They each have 6 sides, so that's 6000 quads to render. If we only render the sides that can possibly be visible, that's 6 sides on the cube times 10 * 10 voxels on each side, totalling 600 quads.

I'm sure the creatures are not treated like this; they're just meshes.

andrewflnr2• 13 years ago

AFAIK culling like that is standard in any mesh-based 3D engine, and most minecraft landscapes aren't uniform enough to benefit from the adjacent-face merging described. Standard 3D engines handle landscapes with way more polys than I can imagine fitting into a minecraft screen. I don't see what the big deal is here.

bajsejohannes2• 13 years ago

There's a really good writeup of that here as well:

http://codeflow.org/entries/2010/dec/09/minecraft-like-rende...

Less thorough on meshing (or tesselation as he calls it), but a very good read.

Meshing in a Minecraft Game (2012)

Related Stories