Mip-Mapping in Direct3D
by Johnathan Skinner

Introduction

For those of you who don't know, mip-mapping is a form of anti-aliasing that is used in many 3D rendering engines. It prevents the well-known interference pattern that occurs on detailed textures, known as the 'moiré pattern'. This happens because when the texture is far enough away, there are more texels (texture pixels) then there are pixels to be rendered on the screen. This means that some texels get skipped over, and visual information is lost.

The ugly 'bitty' look near the top is the moiré pattern in action.

In a properly anti-aliased rendering, what would happen is all of the texels that land within a single pixel on the screen would be weighted, summed and a final average value is placed on the screen. This could be very processor intensive... just imagine being far away from a small box that has a 256 x 256 texture on it. If this box only covers an 8 x 8 pixel area on the screen, that's 1024 texels per pixel! You would have to sum up and average all those texels just to render one pixel on the screen!!! Obviously this isn't going to happen in real-time.

The idea of mip-mapping is simple: if what you are drawing is really big then use a big texture, and if it's small, use a small texture. The great thing about using a smaller texture when needed is that the texel colours can be averaged from the higher resolution texture. And if you use a texture that has a less or equal number texels for the pixels to be rendered, then there is no moiré pattern.

Same scene rendered using mip-mapping.

Mip-Map Factory

Say you have a detailed texture of size 128 x 128. If you down-sample it by a factor of 2 simply by taking the average of every 2 x 2 texel area, you end up with the same texture at 64 x 64, just with less detail. But you won't need the detail because you will only view it from further away. This becomes our level one mip-map (the original texture is refered to as level zero). If you repeat the process on your newly generated texture, then you get level two, and so on. Generally you stop at a smallest of a 2 x 2 texture (after that, you just have a single solid colour).

Mip-maps generated by averaging 2 x 2 texel areas.

Below is some sample code for generating the image data for the mip-maps.


  /* example C code for generating mip-maps (recursive function) */
  /* NOTE: this is untested (and un-optimal ;) */

  void MakeMipMaps( Texture *parentTexture)
  {
    int width = parentTexture->width / 2;
    int height = parentTexture->height / 2;
    Texture *newTexture;
    int u, v;
    int texel;

    /* we want to stop recursing after 2 x 2 map */
    if (width < 2) return;
    if (height < 2) return;

    newTexture = CreateTexture( width, height);

    /* find the new texture values */
    for (u = 0; u < width; u++)
      for (v = 0; v < height; v++)
      {
        /* sum up 2 x 2 texel area */
        /* for simplicity of example, this doesn't seperate
           the RGB channels like it should */
        texel = GetTexel( parentTexture, u * 2  , v * 2  )
              + GetTexel( parentTexture, u * 2 + 1, v * 2  )
              + GetTexel( parentTexture, u * 2  , v * 2 + 1)
              + GetTexel( parentTexture, u * 2 + 1, v * 2 + 1);

        /* take the average */
        texel /= 4;

        PutTexel( newTexture, u, v, texel);
      }

    /* make a link to the mip map */
    parentTexture->mipMap = newTexture;

    /* recurse until we are done */
    MakeMipMaps( newTexture);
  }

The Rendering Pipeline

Since this article is directed to people using Direct3D, I won't be getting into specific rendering algorithms, but it's always good to have a general idea of what's going on in the lower levels.

In order to render a textured polygon, the rendering engine needs to know how many texels it has to advance to get to the pixel beside it, and how many to get to the line below it. For it to choose a mip-map, it checks if either of these values is greater than 1.0, which means there are texels that will potentially be skipped over, so instead, use the next level (lower resolution) mip-map. Repeat this check until the values are both less than or equal to 1.0, or the lowest resolution mip-map is reached, and you have the one that will be used. And of course, for each time the next level is selected, the texel coordinates are divided by two. This process may sound like an expensive operation, but in the rendering pipeline it can be optimized to simple non-iterative instructions. Granted though, it generally is slower than regular texture mapping (but the results are worth it!).

There are also other algorithms used to figure out where the mip-maps go, such as spliting the polygons at boundries based on the surface angle and distance from the view point, but they all produce basically the same results (though some are faster in certain situations).

This demonstrates where the different mip-map levels are used by inverting the texture colour at each level.

Mip-maps usually can be bilinear filtered just like any other texture, but most 3D hardware also allows for a third level of linear filtering on mip-maps. This level will fade smoothly between the mip-map levels instead of having a sharp break (the break usually isn't very noticable though because you are going between two textures of the same colour composition).

Direct3D Implementation

I am going to assume that you already know how to initialize Direct3D and get textured polygons on the screen. If you don't, there are plenty of good tutorials already written about that, so please refer to those. This will just give you the additional steps required to get your polygons mip-mapped.

The first step is to allocate your mip-maps. This is done in the CreateSurface() call for your texture. By specifying the DDSCAPS_MIPMAP and DDSCAPS_COMPLEX capabilities for your surface, the driver will automatically allocate the appropriate mip-maps and attach them to your surface. You will also need to specify the DDSD_MIPMAPCOUNT flag and set the number of mip-map levels that you want (remember that the original texture also counts as a level).


  /* allocates a texture surface with optional mip-maps */
  /* NOTES: - texture width and height need to be powers of 2 */
  /*        - as a general rule, it's good to have width = height for textures */
  /*        - this is untested (my code is in C++ classes so I re-wrote it here
              in C for simplicity, so there may be some subtle differences or
              typos that prevent it from compiling) */

  LPDIRECTDRAWSURFACE CreateD3DTexture( LPDIRECTDRAW lpDD,
                                        int width, int height,
                                        int mipmap,
                                        DDPIXELFORMAT *pixelFormat)
  {
    LPDIRECTDRAWSURFACE surface;  /* pointer to surface to be created */
    DDSURFACEDESC ddsd;           /* description of surface to create */
    DWORD mipLevels = 1;          /* number of mip-map levels to create
                                     (1 = just original texture) */
    DWORD flags = DDSD_WIDTH | DDSD_HEIGHT | DDSD_PIXELFORMAT | DDSD_CAPS;
    DWORD caps = DDSCAPS_TEXTURE | DDSCAPS_3DDEVICE;
    HRESULT result;

    /* put texture in video memory if driver allows it */
    if (VideoMemoryTexturesAllowed())
      caps |= DDSCAPS_VIDEOMEMORY;
    else
      caps |= DDSCAPS_SYSTEMMEMORY;

    if (mipmap)
    {
      /* count how many mip-map levels we need */
      int mipWidth = width;
      int mipHeight = height;

      /* smallest mip-map we want is 2 x 2 */
      while ((mipWidth > 2) && (mipHeight > 2))
      {
        mipLevels++;
        mipWidth  /= 2;
        mipHeight /= 2;
      }

      if (mipLevels > 1)
      {
        /* tell it we want mip-maps */
        flags |= DDSD_MIPMAPCOUNT;
        caps  |= DDSCAPS_MIPMAP | DDSCAPS_COMPLEX;
      }
    }

    /* set up buffer properties */
    memset(&ddsd, 0, sizeof(ddsd));
    ddsd.dwSize          = sizeof(ddsd);
    ddsd.dwFlags         = flags;
    ddsd.dwWidth         = width;
    ddsd.dwHeight        = height;
    ddsd.ddpfPixelFormat = *pixelFormat;
    ddsd.ddsCaps.dwCaps  = caps;
    ddsd.dwMipMapCount   = mipLevels;

    /* create texture surface and associated mip-maps */
    result = IDirectDraw_CreateSurface( lpDD, &ddsd, &surface, NULL);

    if (result != DD_OK) return NULL;

    return surface;
  }

The CreateSurface() call here will create the number of surfaces you specify in ddsd.dwMipMapCount, but it only returns a pointer to one surface. The mip-map surfaces are accessed by calling GetAttachedSurface(). There is no need to do anything special in clean-up because all auto-generated surfaces are released with the parent surface.

Now that the mip-maps have been created, you will need to put in the texture images. Using the images generated from the code sample in the 'Mip-Map Factory' section of this article, you can copy the images to the mip-maps like so:


  Texture *textureData;
  LPDIRECTDRAWSURFACE surface, mipSurface, nextSurface;
  DDSURFACEDESC ddsd;

  /* generate the mip-maps from the original image */
  MakeMipMaps( originalImage);

  /* create the texture surfaces */
  surface = CreateD3DTexture( lpDD, originalImage->width,
                              originalImage->height, TRUE, pixelFormat);

  /* iterate through the mip-maps and copy the data */
  textureData = originalImage;
  mipSurface = surface;

  while (textureData != NULL)
  {
    /* lock surface so we can write to it */
    memset(&ddsd, 0, sizeof(ddsd));
    ddsd.dwSize = sizeof(ddsd);
    IDirectDraw_Lock( mipSurface, NULL, &ddsd, 0, NULL);

    /* copy data from from image to the texture surface */
    CopyTextureData(
      ddsd.lpSurface, /* pointer to destination surface data */
      ddsd.lPitch,    /* number of bytes per horizontal span in the dest surface */
      textureData);   /* pointer to source image */

    /* done writing surface so unlock the memory */
    IDirectDraw_Unlock( mipSurface, NULL);

    /* follow the links down to through the mip-map levels of texture data */
    textureData = textureData->mipMap;
    if (textureData == NULL)
    {
      /* done the last mip-map, need to release the reference to the surface */
      /* don't want to release the first surface or it will free the whole thing! */
      if (mipSirface != surface)
        IDirectDraw_Release( mipSurface);
      break;
    }

    /* get the surface for the next level mip-map */
    IDirectDraw_GetAttachedSurface( mipSurface, &ddsd.ddsCaps, &nextSurface);

    /* need to release the reference to the parent surface */
    if (mipSirface != surface)
      IDirectDraw_Release( mipSurface);

    mipSurface = nextSurface;
  }

  /* now the textures are loaded, we can grab the handle and start referencing it,
     just like with a regular texture */
    . . .
  IDirectDraw_QueryInterface(surface, IID_IDirect3DTexture, (void**)&D3DTexture);
  IDirect3DTexture_GetHandle( D3DTexture, lpD3DDevice, &handle);
    . . .

Now that the image data for the textures has been loaded, it's pretty much ready to go. The only thing missing is to tell Direct3D that you want it to render the mip-maps. If you were to render it now just like any other texture, it will only use the original full-sized texture. In order to get it to use the mip-maps, we must set the render state D3DRENDERSTATE_TEXTUREMIN to one of the following values:

D3DFILTER_MIPNEAREST - Use mip-maps with point sampling
D3DFILTER_MIPLINEAR - Use mip-maps with bilinear filtering (texture interpolation)
D3DFILTER_LINEARMIPNEAREST - Use mip-maps with point sampling, and apply a linear filter between each mip-map level and the next (smooths transitions between the different levels)
D3DFILTER_LINEARMIPLINEAR - Use mip-maps with bilinear filtering, and apply a linear filter between each mip-map level and the next

Throw that into your Direct3D code, and just like that, your textures are mip-mapped. Remember though, that just like with the rest of Direct3D, you will have to check the capabilities of the driver to make sure it supports these render states before you can use them.

If for some reason you want to render without the mip-maps, you can always set it back to either D3DFILTER_NEAREST or D3DFILTER_LINEAR.

In Closing

Hopefully by now you should have been able to seemlessly integrate mip-mapping into your Direct3D graphics engine, so that some day you can display it to thousands of on-lookers who will say "ooohh, aaahh, smooth..." and stare in wonderment at the absence of moiré patterns :)

Johnathan Skinner
jskinner@beyondvirtual.com

Discuss this article in the forums

Date this article was posted to GameDev.net: 11/9/2000
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Direct3D
Texture Mapping