[perf improvement suggestion] dedupe materials #13

Closed
maxogden opened this Issue Mar 30, 2013 · 14 comments

Projects

None yet

2 participants

@maxogden

heya,

so it turns out that textures are by far the biggest issue in voxel.js performance. I believe that voxel-texture isn't smart about not duplicating textures if the textures are the exact same url, so if you say textures.load('grass') it will make ['grass', 'grass', 'grass', 'grass', 'grass', 'grass'] and duplicate it 6 times

do you have any other ideas for perf improvements beyond this?

@maxogden

oooh I got a tip on IRC that we can combine all of our materials into a and then do new THREE.Texture(canvas) once to get an atlas and then we just need to update the UV mappings in voxel-mesh to use the atlas.

I don't really understand the UV stuff though TBH, do you have any free time to possibly hack on this at any point in the future?

@shama
Owner
shama commented Mar 30, 2013

Yep! I actually already started on this and group textures into atlases based on the texture dimensions. I haven't had much time lately because I'm on family leave but that ends on April 1st. I'll have more time then to finish it up.

@shama
Owner
shama commented Mar 30, 2013

It also might be possible to group them all into one atlas using something like this: http://incise.org/2d-bin-packing-with-javascript-and-canvas.html

Although I think most of the time the textures will be the same dimensions so we could get away with just grouping by dimensions and keep it simple.

Also maybe it makes sense to just turn all of that into a bin script and have voxel-texture just load atlases. Unless there is any benefit to keeping the individual texture loading API?

@maxogden

I think there is a benefit to doing it in pure JS... since then we could support 'drag and drop a texture on the page to load your own custom texture'.

also here is a relevant discussion from IRC:

15:47 < mbalho> mikolalysenko: oh yea also apparently you can do texture atlases by combining your pngs into a single 2d <canvas> and doing new 
                THREE.Texture(<canvas>) and then fixing your uv mapping, seems like a viable stop gap for the time being
15:47 < mikolalysenko> mbalho: ok, though that is not really the main issue I think
15:47 < mikolalysenko> mbalho:  basically it is the wrap around at boundaries
15:48 < chrisdickinson> is that in re: three.js?
15:48 < mikolalysenko> mbalho:  you can either use that approach, or face merging - not both, at least within three.js
15:48 < chrisdickinson> i mean, voxel.js
15:48 < mikolalysenko> yeah
15:48 < chrisdickinson> ah, yeah
15:48 < mikolalysenko> basically three.js doesn't implement texture atlases with uv wrap
15:48 < mikolalysenko> and even doing it the simple way by generating a ton of faces will have some problems
15:48 < mbalho> mikolalysenko: ahh i see
15:48 < mikolalysenko> since at texture boundaries the lod filtering is going to create ugly seams
15:49 < mikolalysenko> which I have seen in many other voxel engines that do it that way
15:49 < mikolalysenko> but it should be faster for sure
15:49 < chrisdickinson> ah, that would require a custom fragment shader to render out of an atlas, right?
15:49 < mikolalysenko> exactly
15:49 < chrisdickinson> a non-three.js-baked-in one, at least
15:49 < mikolalysenko> pretty much
15:50 < mikolalysenko> which is also the main reason I stopped working on voxels myself
15:50 < mikolalysenko> is because I ran into this issue back when I was writing those articles
15:50 < mbalho> hah
15:50 < mikolalysenko> and I could not figure out how to get three.js to obey my will
15:50 < mikolalysenko> so, I just shelved and moved onto other projects
15:51 < mbalho> i wonder if we could write a version of the stupid mesher that only was stupid for exterior vertices and not internal
15:51 < mbalho> cause right now it does this http://i.imgur.com/aNDdMjR.gif
15:52 < mbalho> 1 draw call per texture per chunk, so if it was just 1 draw call per chunk i think we could get way more chunks than we can support now
15:52 < mbalho> i tried with 512 chunks and it was like 40k-50k draw calls :D
15:54 < mikolalysenko> I would guess that using the culled mesher should be faster for within three.js, though mostly because of the way it handles materials
15:54 < mikolalysenko> though asymptotically, the best thing to do would be to switch to a custom fragment shader
15:55 < mikolalysenko> you may also be able to avoid the filtering problems by padding each of the texutres in the canvas when you lay them out
@maxogden

ok some more chat today:

20:25 <@mbalho> i wonder how a mesher that kept visible faces as squares but greedily culled internal voxels would stack up in terms of verts/faces in 
                http://mikolalysenko.github.com/MinecraftMeshes2/
20:25 < mikolalysenko> you can just remove the internal voxels though
20:25 < mikolalysenko> that is what the culled mesher does
20:26 <@mbalho> OH
20:26 < mikolalysenko> use that one if you want to do the three.js style "atlas"
20:26 <@mbalho> how did i not realize that
20:26 <@mbalho> also the other day i left a gas burner on when i left the house. i think im working too hard or something
20:27 < mikolalysenko> haha, maybe you should take a day off
20:27 < mikolalysenko> but, yeah I think that using the culled mesher may be the way to go with three.js
20:28 < mikolalysenko> at least until they get a decent texture atlas implementation up and running
20:28 < mikolalysenko> here is a post on using atlases in a voxel game btw:  http://www.volumesoffun.com/phpBB3/viewtopic.php?f=14&t=269
20:28 <@mbalho> seems like culled is roughly 3-4 times as many vertices for minecraft-like terrain
20:28 < mikolalysenko> if you look online you can find tons of people with the same problems
20:28 < mikolalysenko> yeah, that sounds about right
20:29 <@mbalho> but given that we can decrease our draw calls by like 30x it should be worth it
20:29 < mikolalysenko> I think so
20:29 < mikolalysenko> at least within three.js

so basically if we switch to the culled mesher we are increase verts by 4x but improving overall performance by way more by making texture atlases easy (and also ambient occlusion). I think this is the best way forward for now

I also got mrdoob to demonstrate the texture atlases by implementing it in the three.js minecraft flythrough demo: mrdoob/three.js@8934c44

mikola also explained mimaps to me, sharing here in case you haven't learned about them yet:

20:14 < mikolalysenko> basically mip maps were a hack some guy came up with in the 80s to do filtering with variable sized kernels
20:14 < mikolalysenko> it turns out that if you just draw a texture at full resolution some distance away, then you will get these shimmering aliasing 
                       artefacts
20:14 < mikolalysenko> so the solution to this is to just smooth out the texture, so it isn't so noisy
20:15 < mikolalysenko> however the amount you smooth has to be proportional to the distance
20:15 < mikolalysenko> so what a mip pyramid basically is just a collection of filtered images at different down sampled resolutions
20:15 < mikolalysenko> and you can interpolate between them to approximate a blur by a kernel of variable radius
20:16 < mikolalysenko> here is a wiki page that explains the basics:  http://en.wikipedia.org/wiki/Mipmap
20:16 <@mbalho> oooH
20:16 < mikolalysenko> it basically tells you how they work, but doesn't really tell you why
20:16 < mikolalysenko> here is a good explanation of the why (in a picture:  
                       http://3.bp.blogspot.com/-5AWSsEEiJiE/TprhJMs6_7I/AAAAAAAAAl8/6h_zhBb-19k/s1600/mipmap.jpg)
20:17 < mikolalysenko> right hand side is filtered, left side not so much
20:17 <@mbalho> left looks like moire
20:17 < mikolalysenko> basically no mipmaps = shimmering headache
20:17 < mikolalysenko> yeah, it will generate a moire pattern
20:17 < mikolalysenko> but it will move depending on your view
20:17 <@mbalho> yea
20:17 <@mbalho> this reminds me of LOD
20:17 < mikolalysenko> basically it is a big mess, and it is caused by the irregular sampling
20:18 < mikolalysenko> right, mipmaps are a kind of lod
20:18 < mikolalysenko> but what they are doing really is modeling a physical image process
20:18 < mikolalysenko> in a real camera, pixels don't measure a single photon ray
20:18 <@mbalho> whoa 'texels'
20:18 < mikolalysenko> instead they capture incoming light over some area
20:18 <@mbalho> ahhh
20:18 < mikolalysenko> so they average the observed colors over some region
20:19 < mikolalysenko> that region gets larger as you get farther from the camera
20:19 < mikolalysenko> so if you draw a texture with one texture pixel / screen pixel, you are doing it wrong
20:19 < mikolalysenko> unless the texture is sufficiently close to the screen
20:19 < mikolalysenko> but if it gets far away, then weird rounding issues come into play and you get crappy noisy looking results that are unphysical
20:19 < mikolalysenko> so the solution is to average over all the pixels in a region
20:20 < mikolalysenko> which is what mipmaps try to approximate
20:20 <@mbalho> wow that is cool
20:20 < mikolalysenko> it is a super retro idea, but it is still used today
20:20 < mikolalysenko> however, mip pyramids can mess with texture atlases if you are not careful
20:20 < mikolalysenko> if you read out a pixel at a mip level, you can sometimes get bleeding across a texture seam
20:21 < mikolalysenko> this can appear as weird swatches of color at the boundary of your textures
20:21 <@mbalho> cause of the averaging algorithm in the 3d engine?
20:21 < mikolalysenko> yeah
20:21 <@mbalho> ah i see, hence the buffer you suggested
20:21 < mikolalysenko> basically you are averaging pixels form neighboring textures
20:21 < mikolalysenko> and that is no good
20:21 < mikolalysenko> right
20:21 < mikolalysenko> so if you do a texture atlas, then you also have to build the mip pyramid taking that into account
20:22 < mikolalysenko> otherwise at the boundary you will get crap
20:22 <@mbalho> ah
20:22 < mikolalysenko> and you need to modify your shader to do this too
20:22 < mikolalysenko> now:  in the example mrdoob posted I don't think this would matter
20:22 < mikolalysenko> because he [sneakily](https://github.com/mrdoob/three.js/commit/8934c44b6d261ea2bc3e6e691b397f57c8271bc9) put the green grass texture along the green boundary of the dirt
20:22 <@mbalho> lol

@shama
Owner
shama commented Mar 31, 2013

Wow thanks for the information. Let me know if at any time I'm holding the project back as well. I'm totally game to take this stuff on. I just know I'm going to do it wrong a bunch of times before I get it right. So if a non-amateur wanted to step in to keep the project rolling, I would have no problem giving out access to this module or even transfer it; if you felt it was necessary.

I'll finish up the atlas generator and keep as a lib. Switching to the culled mesher sounds good. I don't think voxel-texture will need to be updated to adjust for it but I'll double check.

Thanks Max!

@maxogden

Getting better perf and AO aren't holding up the project at all, they are just high on the list of nice-to-haves. Take your time!

@maxogden
maxogden commented Apr 4, 2013

Screen Shot 2013-04-04 at 12 27 41 AM

I got minecraft levels loading into voxel.js now... I think I need the texture atlas support before it can handle loading more than that is screenshotted though

@shama
Owner
shama commented Apr 4, 2013

Haha that is amazing. I got the atlas packing module done last night. Im going to add an example and publish it today. Then work on implementing it into voxel-texture.

@shama
Owner
shama commented Apr 11, 2013

Running into a race condition implementing into voxel-texture. In order to pack the atlas, we need the image dimensions. So we need to load all the images before applying to the meshes. But chunks can happen before and after the images are loaded or added. Wanted to know if you have any suggestions.

@maxogden

hmm.... if it makes it easier we can use the culled mesher instead of the
greedy mesher, then each face will be a square instead of the rectangles
that we have now. it will add some vertices to our polys but that doesnt
really matter since we would be getting such a perf boost from having
atlases.

if that doesnt help then i'd be okay restricting chunk rendering to wait
until image dimensions have been set, lemme know what you need and I can
add an API to voxel-engine

On Wed, Apr 10, 2013 at 9:21 PM, Kyle Robinson Young <
notifications@github.com> wrote:

Running into a race condition implementing into voxel-texture. In order to
pack the atlas, we need the image dimensions. So we need to load all the
images before applying to the meshes. But chunks can happen before and
after the images are loaded or added. Wanted to know if you have any
suggestions.


Reply to this email directly or view it on GitHubhttps://github.com/shama/voxel-texture/issues/13#issuecomment-16216291
.

@shama
Owner
shama commented Apr 11, 2013

I think I got it figured out. I'm going to just ignore and put chunk positions into a queue with materials.paint calls as textures are loading. Then when the textures finish, it will paint the chunks in the queue.

I'm using the culled mesher atm because with the texture atlas approach we can't do texture tiling, AFAIK. An idea for later is to cheat and pre-tile textures horizontally and vertically in the atlas. Then we could switch back to the greedy mesher.

I'm going to do a write up about UVs as well, at least the way I understand them. At first I perceived them as coordinates which is misleading. To me they're actually more like a draw by number system. You only use coordinates to plot waypoints for the crayon drawing the picture.

@maxogden

@shama I think culled mesher is gonna be the way to go for now since it will make AO easier too. I believe your past work on AO would be pretty close to done with the culled mesher, right?

the crayon analogy is cool. I dont actually get UVs yet so I'm looking forward to the writeup!

also: npm install and npm start this: https://github.com/maxogden/minecraft-mca

you can tweak the chunkDistance to render more/less of the world. I haven't implemented infinite loading yet but this should be a pretty good test case for your new atlas stuff

@shama
Owner
shama commented Apr 15, 2013

All done and published as 0.5.0. Gives us a huge performance boost :D Thanks!

Related PR: maxogden/voxel-engine#69

Known issue: the edges of voxels bleed a bit. I think for the canvas renderer there is the overdraw setting to fix this. Doesn't seem to work with webgl though. I'll keep looking for a fix.

@shama shama closed this Apr 15, 2013
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment