Editing Mipmap

{{short description|Memory-saving rendering technique in which resolution of farther-away images is lowered}}
{{Distinguish|Minimap}}
{{More citations needed|date=June 2009}}

In [[computer graphics]], '''mipmaps''' (also '''MIP maps''') or '''pyramids'''<ref>{{cite web |url=https://docs.microsoft.com/en-us/windows/win32/direct3d9/texture-filtering-with-mipmaps |title=Texture Filtering with Mipmaps (Direct3D 9)|publisher=Microsoft |work=microsoft.com}}</ref><ref>{{cite web|url=https://docs.microsoft.com/en-us/previous-versions/aa921432(v=msdn.10) |title=Texture Filtering with Mipmaps |date=April 8, 2010 |work=microsoft.com |publisher=[[Microsoft]]}}</ref><ref>{{cite web |url=https://cgl.ethz.ch/teaching/former/vc_master_06/Downloads/Mipmaps_1.pdf |title=Mipmap Texturing |access-date=December 10, 2019}}</ref> are pre-calculated, [[optimization (computer science)|optimized]] sequences of [[digital image|images]], each of which is a progressively lower [[image resolution|resolution]] representation of the previous. The height and width of each image, or level, in the mipmap is a factor of two smaller than the previous level. Mipmaps do not have to be square. They are intended to increase [[rendering (computer graphics)|rendering]] speed and reduce [[aliasing]] artifacts. A high-resolution mipmap image is used for high-density samples, such as for objects close to the camera; lower-resolution images are used as the object appears farther away. This is a more efficient way of [[Image scaling|downscaling]] a [[texture mapping|texture]] than sampling all [[texel (graphics)|texels]] in the original texture that would contribute to a screen [[pixel]]; it is faster to take a constant number of samples from the appropriately downfiltered textures. Mipmaps are widely used in 3D [[computer game]]s, [[flight simulator]]s, other 3D imaging systems for [[texture filtering]], and 2D and 3D [[geographic information system|GIS software]]. Their use is known as '''mipmapping'''. The letters ''MIP'' in the name are an acronym of the [[Latin]] phrase ''multum in parvo'', meaning "much in little".<ref name="staff">{{cite web |title=Pyramidal Parametrics |last=Williams |first=Lance |url=http://staff.cs.psu.ac.th/iew/cs344-481/p1-williams.pdf |access-date=2012-09-25 |url-status=dead |archive-url=https://web.archive.org/web/20140414134825/http://staff.cs.psu.ac.th/iew/cs344-481/p1-williams.pdf |archive-date=2014-04-14}}</ref>

Since mipmaps, by definition, are [[memory management|pre-allocated]], additional [[computer data storage|storage space]] is required to take advantage of them. They are also related to [[wavelet compression]]. Mipmap textures are used in 3D scenes to decrease the time required to render a scene. They also improve [[image quality]] by reducing aliasing and [[Moiré pattern]]s that occur at large viewing distances,<ref>{{Cite web|url=https://textureingraphics.wordpress.com/what-is-texture-mapping/anti-aliasing-problem-and-mipmapping/|title=Anti-Aliasing Problem and Mipmapping|date=2011-12-13|website=textureingraphics|language=en|access-date=2019-02-21}}</ref> at the cost of [[1/4 + 1/16 + 1/64 + 1/256 + ⋯|33%]] more memory per texture.

==Overview==
[[File:Mipmap Aliasing Comparison.png|alt=Image showing how mipmaps reduce aliasing at large distances.|thumb|440x440px|Image showing how mipmaps reduce [[aliasing]] at large distances (Aliasing causes a [[Moiré pattern]] in the left image.)]]
Mipmaps are used for:
* [[Level of detail (computer graphics)|Level of detail]] (LOD)<ref>{{Cite web|url=http://people.cs.clemson.edu/~dhouse/courses/405/notes/OpenGL-mipmaps.pdf|title=Multiple levels of Detail}}</ref><ref>{{cite web|url=http://msdn.microsoft.com/en-us/library/windows/desktop/ff476207(v=vs.85).aspx|title=D3D11_SAMPLER_DESC structure|publisher=Microsoft|work=microsoft.com}}</ref>
* Improving image quality. Rendering from large textures where only small, discontiguous subsets of [[texel (graphics)|texels]] are used can easily produce [[Moiré pattern]]s;
* Speeding up rendering times, either by reducing the number of texels sampled to render each pixel, or increasing the memory locality of the samples taken;
* Reducing stress on the [[GPU]] or [[CPU]].
* Water surface reflections<ref>{{cite web |url=https://blog.mecheye.net/2018/03/deconstructing-the-water-effect-in-super-mario-sunshine |title=Deconstructing the water effect in Super Mario Sunshine |date=3 March 2018 |access-date=25 February 2023}}</ref>

==Origin==
Mipmapping was invented by [[Lance Williams (graphics researcher)|Lance Williams]] in 1983 and is described in his paper ''Pyramidal parametrics''.<ref name="staff" /> From the abstract: "This paper advances a 'pyramidal parametric' prefiltering and sampling geometry which minimizes aliasing effects and assures continuity within and between target images." The referenced pyramid can be imagined as the set of mipmaps stacked in front of each other.

The first patent issued on Mipmap and texture generation was in 1983 by Johnson Yan, Nicholas Szabo, and Lish-Yann Chen of Link Flight Simulation (Singer). Using their approach, texture could be generated and superimposed on surfaces (curvilinear and planar) of any orientation and could be done in real-time. Texture patterns could be modeled suggestive of the real world material they were intended to represent in a continuous way and free of aliasing, ultimately providing level of detail and gradual (imperceptible) detail level transitions. Texture generating became repeatable and coherent from frame to frame and remained in correct perspective and appropriate occultation. Because the application of real time texturing was applied to early three dimensional flight simulator CGI systems, and texture being a prerequsite for realistic graphics, this patent became widely cited and many of these techniques were later applied in graphics computing and gaming as applications expanded over the years.<ref>{{cite web |last1=Johnson K. Yan, Nicholas S. Szabo, Lish-Yann Chen |title=Texture Generation |url=https://patentimages.storage.googleapis.com/9d/3b/9f/603a55c4b7f692/US4615013.pdf}}</ref>

The origin of the term mipmap is an initialism of the Latin phrase ''multum in parvo'' ("much in little"), and map, modeled on bitmap.<ref name="staff" /> The term ''pyramids'' is still commonly used in a [[geographic information system|GIS]] context. In GIS software, pyramids are primarily used for speeding up rendering times.

==Mechanism==
[[File:MipMap Example STS101.jpg|thumb|Example mipmap image storage: the principal image on the left is accompanied by filtered copies of reduced size.]]

Each bitmap image of the mipmap set is a downsized duplicate of the main [[texture mapping|texture]], but at a certain reduced level of detail. Although the main texture would still be used when the view is sufficient to render it in full detail, the renderer will switch to a suitable mipmap image (or in fact, [[interpolation (computer graphics)|interpolate]] between the two nearest, if [[trilinear filtering]] is activated) when the texture is viewed from a distance or at a small size. Rendering speed increases since the number of texture pixels (''[[texel (graphics)|texels]]'') being processed per display pixel can be much lower for similar results with the simpler mipmap textures. If using a limited number of texture samples per display pixel (as is the case with [[bilinear filtering]]) then artifacts are reduced since the mipmap images are effectively already [[spatial anti-aliasing|anti-aliased]]. Scaling down and up is made more efficient with mipmaps as well.

If the texture has a basic size of 256 by 256 pixels, then the associated mipmap set may contain a series of 8 images, each one-fourth the total area of the previous one: 128×128 pixels, 64×64, 32×32, 16×16, 8×8, 4×4, 2×2, 1×1 (a single pixel). If, for example, a scene is rendering this texture in a space of 40×40 pixels, then either a scaled-up version of the 32×32 (without [[trilinear interpolation]]) or an interpolation of the 64×64 and the 32×32 mipmaps (with trilinear interpolation) would be used. The simplest way to generate these textures is by successive averaging; however, more sophisticated algorithms (perhaps based on [[signal processing]] and [[Fourier transform]]s) can also be used.

{{Multiple image
| image1=Mipmap illustration2.png
| image2=Mipmap illustration1.png
| footer=Showing each color channel of each level of an RGB mipmap as a separate plane (left) demonstrates that the whole mipmap forms a square of 4 times the area. As each plane requires {{frac|1|3}} the storage, mipmaps therefore require {{frac|4|3}} the memory; i.e., {{frac|1|3}} ≈ 33% more.
}}
The increase in storage space required for all of these mipmaps is a third of the original texture, because the sum of the areas [[1/4 + 1/16 + 1/64 + 1/256 + ⋯]] converges to 1/3. In the case of an RGB image with three channels stored as separate planes, the total mipmap can be visualized as fitting neatly into a square area twice as large as the dimensions of the original image on each side (twice as large on each side is four times the original area - one plane of the original size for each of red, green and blue makes three times the original area, and then since the smaller textures take 1/3 of the original, 1/3 of three is one, so they will take the same total space as just one of the original red, green, or blue planes). This is the inspiration for the tag ''multum in parvo''.

==Anisotropic filtering==
{{main|Anisotropic filtering}}
When a texture is viewed at a steep angle, the filtering should not be uniform in each direction (it should be [[anisotropic]] rather than [[isotropic]]), and a compromise resolution is required. If a higher resolution is used, the [[cache coherence]] goes down, and the aliasing is increased in one direction, but the image tends to be clearer. If a lower resolution is used, the cache coherence is improved, but the image is overly blurry. This would be a tradeoff of MIP level of detail (LOD) for aliasing vs blurriness. However anisotropic filtering attempts to resolve this trade-off by sampling a non isotropic texture footprint for each pixel rather than merely adjusting the MIP LOD. This non isotropic texture sampling requires either a more sophisticated storage scheme or a summation of more texture fetches at higher frequencies.<ref>{{cite web |url=https://www.csee.umbc.edu/~olano/papers/vbat/vbat.pdf |title=Vertex-based Anisotropic Texturing |last1=Olano |first1=Marc |last2=Mukherjee |first2=Shrijeet]] |last3=Dorbie |first3=Angus}}</ref>

==Summed-area tables==
[[Summed-area table]]s can conserve memory and provide more resolutions. However, they again hurt cache coherence, and need wider types to store the partial sums, which are larger than the base texture's word size. Thus, modern graphics hardware does not support them.

==See also==
* [[Anisotropic filtering]]
* [[Hierarchical modulation]] – similar technique in broadcasting
* [[Pyramid (image processing)]]
* [[Scale space]]
* [[Spatial anti-aliasing]]

==References==
{{Reflist}}

[[Category:Computer graphics data structures]]
[[Category:Texture filtering]]