{"id":517,"date":"2016-12-13T11:23:52","date_gmt":"2016-12-13T10:23:52","guid":{"rendered":"http:\/\/www.renaudpradenc.com\/?p=517"},"modified":"2016-12-20T09:57:27","modified_gmt":"2016-12-20T08:57:27","slug":"megatexture","status":"publish","type":"post","link":"https:\/\/www.renaudpradenc.com\/?p=517","title":{"rendered":"Megatexture"},"content":{"rendered":"<p>In the last two years and half, I have been working for <a href=\"http:\/\/meteoconsult.fr\/\">Meteo Consult<\/a> on an internal application running on a Mac, to create 3D\u00a0meteorological maps, broadcast on the TV channel <a href=\"http:\/\/lachainemeteo.com\">La Cha\u00eene M\u00e9t\u00e9o<\/a>.<\/p>\n<figure id=\"attachment_537\" aria-describedby=\"caption-attachment-537\" style=\"width: 638px\" class=\"wp-caption aligncenter\"><a href=\"https:\/\/www.renaudpradenc.com\/?attachment_id=537\" rel=\"attachment wp-att-537\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-537 size-full\" src=\"https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/MegaTextureWholeEarth.jpg\" width=\"638\" height=\"629\" srcset=\"https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/MegaTextureWholeEarth.jpg 638w, https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/MegaTextureWholeEarth-300x296.jpg 300w\" sizes=\"auto, (max-width: 638px) 100vw, 638px\" \/><\/a><figcaption id=\"caption-attachment-537\" class=\"wp-caption-text\">A sphere, colour-mapped with NASA&#8217;s Blue Marble Next Generation. The Blue Marble measures 86400 by 43200 pixels, which is too big for most hardware, and too long to load anyway.<\/figcaption><\/figure>\n<h1>A detailed texture is needed<\/h1>\n<p>One major problem we have\u00a0since the beginning is how to cover the Earth with a texture, since the texture has to be huge\u00a0to\u00a0be detailed enough. Currently we are stuck with a smaller texture, which presents\u00a0two drawbacks:<\/p>\n<ul>\n<li>The Earth is hardly\u00a0detailed enough, so the minimum altitude of the camera is limited. For example, La\u00a0Martinique or La\u00a0Guadeloupe are only small blurry dots. We currently rely on 2D maps instead.<\/li>\n<li>Even with its low resolution, the texture takes a lot of time to load on the GPU; about 3 s on my MacBook Pro 2013.<\/li>\n<\/ul>\n<p>Hopefully, the application runs on a Mac Pro, which has a lot of GPU RAM; but even if we could load a big texture, GPU generally don&#8217;t handle textures larger than 16384 pixels, so we would be stuck anyway.<\/p>\n<h1>Tiles<\/h1>\n<p>Probably the solution was obvious to you: use tiles, Boy !\u00a0Of course, we thought of that\u00a0since the beginning of the project, and I even tried to make something work, but to no avail. The major difficulty was to determine which tiles were visible. It&#8217;s rather easy on a flat\u00a02D surface, but I could not find a reliable solution for the\u00a0round 3D surface of the Earth.<\/p>\n<h1>Megatexture<\/h1>\n<p>Megatexture, also known as &#8220;Sparse Virtual Texture&#8221;, is a technique to compose a big virtual texture using tiles. The term was coined by <a href=\"https:\/\/en.wikipedia.org\/wiki\/John_Carmack\">John Carmack<\/a>, who imagined this technique. I&#8217;ll stick with &#8220;Megatexture&#8221; since it sounds much cooler than &#8220;Virtual Texture&#8221;.<\/p>\n<figure id=\"attachment_538\" aria-describedby=\"caption-attachment-538\" style=\"width: 599px\" class=\"wp-caption aligncenter\"><a href=\"https:\/\/www.renaudpradenc.com\/?attachment_id=538\" rel=\"attachment wp-att-538\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-538 size-full\" src=\"https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/MegaTextureTiles.jpg\" width=\"599\" height=\"327\" srcset=\"https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/MegaTextureTiles.jpg 599w, https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/MegaTextureTiles-300x164.jpg 300w\" sizes=\"auto, (max-width: 599px) 100vw, 599px\" \/><\/a><figcaption id=\"caption-attachment-538\" class=\"wp-caption-text\">The virtual texture is made of tiles, which number\u00a0varies with the Mipmap level.<\/figcaption><\/figure>\n<h2>Determining visible tiles<\/h2>\n<p>The great\u00a0insight is how visible tiles are determined: the scene is rendered to an offscreen buffer, with a special fragment shader. In my case, the Megatexture is at most 256 by 256 tiles, and has a maximum of 8 mipmap levels, so the\u00a0shader stores the tile&#8217;s x in the red component, the tile&#8217;s y in the green component, the mipmap level in the blue\u00a0component, and the Texture ID in the alpha component. The scene is rendered to\u00a0a RGBA8 offscreen buffer.<\/p>\n<h3>Texture ID<\/h3>\n<p>There may be several megatextures in a same scene. The texture ID permits to differentiate them in the Cache and in the Indirection Table\u00a0later. Since objects which are not megatextured won&#8217;t be processed in the shader, you need to reserve a special Texture ID to mean &#8220;No texture&#8221;. It must corresponds to the buffer&#8217;s clear color, therefore\u00a0I advise you choose the value 0x00, so it corresponds to a transparent\u00a0color (since the texture Id is saved to the alpha channel).<\/p>\n<h3>Tiles determination shader<\/h3>\n<p>I&#8217;m sorry but I can&#8217;t provide my own code, so I&#8217;ll give you\u00a0Sean Barrett&#8217;s instead, who was a pioneer in the technique, and made his\u00a0code public:<\/p>\n<pre class=\"lang:default decode:true\">    const float readback_reduction_shift = 2.0;\r\n    const float vt_dimension_pages = 128.0;\r\n    const float vt_dimension = 32768.0;\r\n    uniform float mip_bias;\r\n    \/\/ analytically calculates the mipmap level similar to what OpenGL does\r\n    float mipmapLevel(vec2 uv, float textureSize)  {\r\n        vec2 dx = dFdx(uv * textureSize);\r\n        vec2 dy = dFdy(uv * textureSize);\r\n        float d = max(dot(dx, dx), dot(dy, dy));\r\n        return 0.5 * log2(d)   \/\/ explanation: 0.5*log(x) = log(sqrt(x)) + mip_bias - readback_reduction_shift;\r\n    }<\/pre>\n<p>This first part determines the mipmap level. The formula is copied\u00a0straight from OpenGL&#8217;s implementation, so everyone uses the same.<\/p>\n<ul>\n<li>vt_dimensions_pages is the size of a Tile\u00a0(what Barrett\u00a0and a number of people call a &#8220;Page&#8221;, but which I find inappropriate).<\/li>\n<li>vt_dimension is the size the megatexture at the most detailed level (mipmap 0).<\/li>\n<li>you&#8217;ll see below that the CPU is going\u00a0to read the pixels of the offscreen buffer. To save a lot of processing power, the scene is not rendered at full size. readback_reduction_shift is a power of two; since it equals to 2 here, the offscreen buffer is a quarter of the width and height of the final rendering. I personally set this value to 4, and set the width and height of the buffer to 1\/16th of the size of my view.<\/li>\n<li>I&#8217;m not sure what mip_bias is. I believe this is a way to make the shader less agressive in its changes of mipmap levels, at the cost of the texture being a little blurry at times. (I don&#8217;t use it my own implementation).<\/li>\n<\/ul>\n<p>The second part determines the Tile&#8217;s x and y and renders them in the color buffer:<\/p>\n<pre class=\"lang:default decode:true \">    void main() {\r\n        \/\/ the tile x\/y coordinates depend directly on the virtual texture coords\r\n        gl_FragColor.rg = floor(gl_TexCoord[0].xy * vt_dimension_pages) \/ 255.0;\r\n        gl_FragColor.b = mipmapLevel(gl_TexCoord[0].xy, vt_dimension) \/ 255.0;\r\n        gl_FragColor.a = 1.0; \/\/ BGRA: mip, x, y, 255\r\n    }<\/pre>\n<p>Note that there is a mistake here: the mipmap level must be floored! Otherwise there will be a discrepancy between the level determined here, and the one determined in the Texturing shader.<\/p>\n<h3>Result<\/h3>\n<p>A small image:<a href=\"https:\/\/www.renaudpradenc.com\/?attachment_id=526\" rel=\"attachment wp-att-526\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-526\" src=\"https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/Feedback-buffer.png\" alt=\"\" width=\"50\" height=\"37\" \/><\/a><\/p>\n<p>I changed the way colours are rendered so the image is\u00a0visible, but the size is real. If the OpenGL view renders at 800 x 600, then the offset buffer is rendered at 1\/16th of that, that is 50 x 37.<\/p>\n<h2>Loading tiles in the Cache<\/h2>\n<h3>Reading back the offscreen buffer<\/h3>\n<p>I use glReadPixels to get the pixels. Every pixel corresponds to what I call a &#8220;Tile Id&#8221;: texture Id, x, y, mipmap level. Pixels with the &#8220;None&#8221; texture ID are discarded immediately. Others are converted to TileId objects, which are added to a NSMutableSet, in order to\u00a0remove duplicates: since a same tile shows\u00a0at several places, its TileId will appear several times.<\/p>\n<p>It is not necessary to read the buffer, and therefore determine visible tiles, at every draw cycle. I do it\u00a0only once every 4 frames (at 60fps\u00a0=\u00a0every 15th of second).<\/p>\n<h3>Determine the tiles to load<\/h3>\n<p>Now we have a list of visible tiles, we can compare them to the ones already in the Cache. The difference is\u00a0the tiles to load.<\/p>\n<p>In my implementation, tiles are loaded as\u00a0background tasks, but\u00a0textures\u00a0are loaded in GPU memory on the main thread, because we have to with OpenGL. This textures obviously don&#8217;t have mip maps, but do use interpolation.<\/p>\n<p>While the tile\u00a0is loading, you will like\u00a0to replace it with a &#8220;parent&#8221; tile\u2014 one with lower details\u00a0\u2014\u00a0already in the cache. This is not too difficult, since the replacement only consists in a substitution in the Table of Indirection. Since the parent\u00a0might not be in the Cache either, you should look for the grand-parent or grand-grand-parent, etc. I add the &#8220;base tile&#8221; (the lowest resolution one)\u00a0to the set of visible tiles, so I&#8217;m always sure that at least the Base tile is in the Cache.<\/p>\n<h3>The Cache<\/h3>\n<p>The Cache itself is simply a texture (not mipmapped, but interpolated), which forms a grid of tiles. You need somewhere a table of correspondance between a position in the Cache and a TileId. I use a dictionary, indexed by the TileId. Use\u00a0glTexSubImage2D() to replace\u00a0only the part of the texture which contains the new tile.<\/p>\n<p>When the Cache is full, some tiles must be dropped. People and I use a simple Least Recently Used mechanism to determine which ones. It&#8217;s simple, it works. I tried other heuristics, based on the mipmap level, to drop the least detailed tiles in last resort, but it did not work great, leading to load the most detailed tiles too frequently.<\/p>\n<p>Dropping a Tile consists in marking its position as free in the table of correspondance. Since it does not perform OpenGL calls,\u00a0it\u00a0can be done at any time.<\/p>\n<p>The Cache\u00a0does not have to be huge: 16 x 16 tiles works. In my experience\u00a08 x 8 tiles is\u00a0not big enough on a Retina display: the program loads\u00a0tiles and drops them continually. Make the Cache bigger if you want to remove some burden on the CPU, or have several Megatextures.<\/p>\n<p>A 256 x 256 tile takes 250 KB of memory, so a 16 x 16 tiles cache takes 64 MB. That is very reasonable.<\/p>\n<h2>Table of Indirection<\/h2>\n<p>The Texturing Shader\u00a0needs to know what are the coordinates of a Tile in the Cache texture. For that purpose, it is provided a\u00a0Table of Indirection, which is a mip mapped texture.<\/p>\n<p>A pixel of the\u00a0texture contains the following information:<\/p>\n<ul>\n<li>x position in the cache (stored in .r)<\/li>\n<li>y position (in .g)<\/li>\n<li>mipmap level (in .b).<\/li>\n<\/ul>\n<p>For a particular mipmap level, this table has\u00a0one\u00a0pixel\u00a0per\u00a0tile. For instance, say that my megatexture measures 256 x 256 tiles at mipmap 0, then the texture measures 256 x 256 pixels at mipmap 0. There are only 128 x 128 tiles at mipmap 1, and hence the table measures 128 x 128 pixels at mipmap 1. There is a straight correspondance, so the Texturing Shader determines the tiles x and y according to the texture coordinate, and does a simple look up. (In other words, there is a table of indirection for every mipmap level. All these\u00a0tables are combined in a single mipmapped texture).<\/p>\n<p>You might wonder why the mipmap level is stored in the table, since it can be determined by\u00a0the shader. Actually, this is what allows\u00a0to substitute a parent tile; in that case, the pixel contains the x, y, and mipmap of the parent \u2014 not the child. The mipmap level of the parent\u00a0tile is needed to determine correctly the position within the parent tile.<\/p>\n<h2>Texturing Shader<\/h2>\n<p>Finally, we arrive at the end of the chain !<\/p>\n<pre class=\"lang:default decode:true\">const float phys_tex_dimension_pages = 32.0;\r\nconst float page_dimension = 256.0;\r\nconst float page_dimension_log2 = 8.0;\r\nuniform float mip_bias;\r\nuniform sampler2D pageTableTexture;\r\nuniform sampler2D physicalTexture;\r\n\/\/ converts the virtual texture coordinates to the physical texcoords\r\nvec2 calulateVirtualTextureCoordinates(vec2 coord) {\r\n        float bias = page_dimension_log2 - 0.5 + mip_bias;\r\n        vec4 pageTableEntry = texture2D(pageTableTexture, coord, bias) * 255.0;\r\n        float mipExp = exp2(pageTableEntry.a); \/\/ alpha channel has mipmap-level\r\n        vec2 pageCoord = pageTableEntry.bg; \/\/ blue-green has x-y coordinates\r\n        vec2 withinPageCoord = fract(coord * mipExp);\r\n        return ((pageCoord + withinPageCoord) \/ phys_tex_dimension_pages);\r\n    }\r\n    void main(void) {\r\n        vec2 coord = calulateVirtualTextureCoordinates(gl_TexCoord[0].xy);\r\n        vec4 vtex = texture2D(physicalTexture, coord);\r\n        gl_FragColor = vtex;\r\n    }<\/pre>\n<p>Let&#8217;s first see the main() function: you&#8217;ll notice that texturing of the object is done as usual, using the boring texture2D() function.<\/p>\n<ul>\n<li>phys_tex_dimension_page is the size of the megatexture at the maximum mipmap level, expressed in Tiles<\/li>\n<li>page_dimension is the size of a Tile, it is not used directly because\u2026<\/li>\n<li>\u2026 page_dimension_log2 is the same size, but expressed as a power of two (2^8 = 256)<\/li>\n<li>pageTableTexture is the Indirection Table texture<\/li>\n<li>physicalTexture is the Cache texture<\/li>\n<\/ul>\n<p>Now, I would like to focus on this:<\/p>\n<pre class=\"lang:default decode:true\">float bias = page_dimension_log2 - 0.5 + mip_bias;\r\nvec4 pageTableEntry = texture2D(pageTableTexture, coord, bias) * 255.0;<\/pre>\n<p>Older versions of OpenGL (like the one I&#8217;m constrained to use, because of Apple), did not allow to sample the texture for a particular mip map level. However, texture2D() may take a third parameter, which is a value added to the implicit mipmap level (the one computed by OpenGL). I don&#8217;t know why 0.5 is substracted, but it works better this way.<\/p>\n<p>I must say that I had a lot of problems with this principle because\u00a0it assumes that:<\/p>\n<ol>\n<li>Tiles are square<\/li>\n<li>The megatexture is square<\/li>\n<\/ol>\n<p>Since I had to cover the Earth, my megatexture was not square, but had a 2:1 ratio instead. And my tiles were 512 x 256 pixels. If this is not the case, you will run into troubles, because the computation of the mipmap level is right vertically, but not horizontally, and you will have visual artifacts, since the wrong mipmap level is sampled from the indirection texture.So, don&#8217;t do that: make your tiles square and stretch your megatexture if needed. It will save you a lot of pain.<\/p>\n<p>(With a more recent version of GLSL, you might use texture2DLod(), and compute the mipmap level like in the Determination Shader, and not have this problem).<\/p>\n<figure id=\"attachment_539\" aria-describedby=\"caption-attachment-539\" style=\"width: 416px\" class=\"wp-caption aligncenter\"><a href=\"https:\/\/www.renaudpradenc.com\/?attachment_id=539\" rel=\"attachment wp-att-539\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-539\" src=\"https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/RichatsStructure.jpg\" alt=\"\" width=\"416\" height=\"256\" srcset=\"https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/RichatsStructure.jpg 416w, https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/RichatsStructure-300x185.jpg 300w\" sizes=\"auto, (max-width: 416px) 100vw, 416px\" \/><\/a><figcaption id=\"caption-attachment-539\" class=\"wp-caption-text\">The MegaTexture is precise enough so the Richat Structure (\u201cThe Eye of Sahara\u201d) can be seen.<\/figcaption><\/figure>\n<p>&nbsp;<\/p>\n<h1>Generating Tiles<\/h1>\n<p>We&#8217;re not done yet! Remember that the megatexture is a huge image that must be cut into tiles. I personally wrote a Python program that uses Image Magick to cut tiles and resize them. I won&#8217;t go into details here, but you must know that Image Magick is slow, and not very user friendly (and that by default, rescaling is proportional). You may do it otherwise, maybe using a Photoshop script or whatever.<\/p>\n<h3>Seams<\/h3>\n<p>There is one final problem with the principle of the megatexture itself. Because tiles are all stored in the Cache texture in a random order, a tile\u00a0is unrelated with its\u00a0neighbours.\u00a0This causes visual problems because of the linear interpolation of tiles, which will cause half a pixel of neighbour textures to show:<\/p>\n<figure id=\"attachment_532\" aria-describedby=\"caption-attachment-532\" style=\"width: 759px\" class=\"wp-caption aligncenter\"><a href=\"https:\/\/www.renaudpradenc.com\/?attachment_id=532\" rel=\"attachment wp-att-532\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-532 size-full\" src=\"https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/TilesSeams.jpg\" alt=\"Tiles Seams\" width=\"759\" height=\"529\" srcset=\"https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/TilesSeams.jpg 759w, https:\/\/www.renaudpradenc.com\/wp-content\/uploads\/2016\/12\/TilesSeams-300x209.jpg 300w\" sizes=\"auto, (max-width: 759px) 100vw, 759px\" \/><\/a><figcaption id=\"caption-attachment-532\" class=\"wp-caption-text\">Borders of tiles are visible<\/figcaption><\/figure>\n<p>The solution is well known: leave\u00a0a margin of 1 pixel on each side, and sample at this size. Hence the actual usable size is 254 x 254 pixels on my 256 x 256 tiles.<\/p>\n<h1>Further reading<\/h1>\n<p>I could not have made my Megatexture work without the following resources:<\/p>\n<ul>\n<li><a href=\"http:\/\/www.noxa.org\/blog\/2009\/11\/29\/megatextures-in-webgl-2\/\">http:\/\/www.noxa.org\/blog\/2009\/11\/29\/megatextures-in-webgl-2\/<\/a><br \/>\nThis was\u00a0my main source of inspiration, because it is very synthetic, covers most issues and guides toward a practical implementation. I don&#8217;t use\u00a0his principle for the\u00a0Indirection Tables though, which I find awkward. Maybe he could not do otherwise in WebGL.<\/li>\n<li><a href=\"http:\/\/silverspaceship.com\/src\/svt\/\">The example of Sean Barrett<\/a><br \/>\nThere is a video, but I found it rather difficult to follow. It does not explain the basic technique well, but it might be interesting if you want to handle tri-linear filtering (which I don&#8217;t). You might also like to take a look at the source code, since most shaders written by other folks are based on it.<\/li>\n<li><a href=\"https:\/\/www.cg.tuwien.ac.at\/research\/publications\/2010\/Mayer-2010-VT\/\">Thesis by Albert Julian Mayer<\/a><br \/>\nThis is really interesting as it sums up\u00a0a lot of the techniques that are known for virtual texturing. You should definitely take a look if there are details you did not understand in my post, or if you want to push the technique\u00a0further.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>In the last two years and half, I have been working for Meteo Consult on an internal application running on a Mac, to create 3D\u00a0meteorological maps, broadcast on the TV channel La Cha\u00eene M\u00e9t\u00e9o. A detailed texture is needed One major problem we have\u00a0since the beginning is how to cover the Earth with a texture, [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89],"tags":[112,109,111,113,110],"class_list":["post-517","post","type-post","status-publish","format-standard","hentry","category-english","tag-glsl","tag-megatexture","tag-opengl","tag-shader","tag-sparse-virtual-texture"],"_links":{"self":[{"href":"https:\/\/www.renaudpradenc.com\/index.php?rest_route=\/wp\/v2\/posts\/517","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.renaudpradenc.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.renaudpradenc.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.renaudpradenc.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.renaudpradenc.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=517"}],"version-history":[{"count":20,"href":"https:\/\/www.renaudpradenc.com\/index.php?rest_route=\/wp\/v2\/posts\/517\/revisions"}],"predecessor-version":[{"id":543,"href":"https:\/\/www.renaudpradenc.com\/index.php?rest_route=\/wp\/v2\/posts\/517\/revisions\/543"}],"wp:attachment":[{"href":"https:\/\/www.renaudpradenc.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=517"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.renaudpradenc.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=517"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.renaudpradenc.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=517"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}