This document explains how Crystal Space uses lookup tables in the texture
cache and also explains how the texture cache works (more or less).


There are several lookup tables that are used. Here is a summary of all render
systems that Crystal Space supports and the lookup tables that are used for
them:

8-bit display mode:
    - nocolor mixing: in this case no colored lights are supported. This is
      how Quake works. In nocolor mode there is a global 256-color palette for
      all textures. In this case there is a simple lookup table of
      256x256->256 which maps every color from the palette and a light level
      between 0 and 255 to a new color in the palette (0..256).

    - true_rgb mixing with global colormap: use true rgb lights. Here you get
      colored lights. There is still a single global 256-color palette for all
      textures. In this case there is also the simple lookup table of
      256x256->256 which is the same as in the previous case and is used by
      the texture cache when it detects that a part of the polygon is only hit
      by white light (this is an optimization). Otherwise there are three
      lookup tables which add red, green, and blue light to a palette color.
      In other words, these lookup tables are 256x256->65536. So the red lookup
      table adds red light to a palette index and returns a 16-bit truecolor
      value with only the red component set. Similarly for blue and green.
      Finally the three 16-bit truecolor values are ored to get a 16-bit
      color. Finally there is a lookup table from 65536->256 which converts
      the 16-bit truecolor value to a palette index.

    - true_rgb mixing with private colormap: use true rgb lights. Here you get
      colored lights but every texture has it's own private 256-color palette.
      This gives better quality for levels which use a lot of textures which
      have widely different textures. Note that since we're in 8-bit display
      mode that there is still a global palette. It is just that individual
      textures are allowed to have a seperate palette on their own. This mode
      works similarly to the one above except that there is an extra lookup
      table for every texture which maps the private palette to an RGB value:
      256->256*256*256. These rgb values are then fed to the same three
      256x256->65536 lookup tables as in the previous case.

    - fast_wxx mode. This is the original Crystal Space mode which existed
      before anything else. It allows three kinds of lights of which one kind
      always has to be white. So you can have white, red, green, white, red,
      blue, or white, green, blue. This mode could do the three kinds of
      lights with very good quality (even better than 8-bit true_rgb) but it
      had much trouble mixing the three kinds of lights. In this mode there
      are three 256x256->256 lookup tables which map a palette index (global
      palette is used here) and a light level to a new palette index. The
      three lookup tables where just used sequentially which is the reason why
      mixing didn't look very good in this mode. If you start large.zip in 8-bit
      mode it is still using this mode.
      One other advantage of this mode is that it can use a higher quality
      palette calculation which cannot be used in any of the other 8-bit modes.

16-bit display mode:
    In 16-bit display mode there is only true_rgb mixing. However you can
    choose between global, private or 24bit textures. Here is how these work:

    - global colormap. In this mode there is a single global colormap for all
      textures. This mode works very similar to 8-bit display mode with
      true_rgb and global colormap except that there is no need for a final
      lookup table to convert the 16-bit truecolor value to the palette as the
      16-bit truecolor value can be used directly to display the texture.

    - private colormap. In this mode every texture has it's own colormap. This
      mode also works very similar to 8-bit display mode with private
      colormaps except that the final lookup from 16-bit to 8-bit is not needed.

    - 24bit mode. In this case all textures are represented in RGB format.
      This gives the highest possible quality. In this case no lookup tables
      are used but the color is calculated immediatelly with the following
      formula:
             *tm++ = ((RGB >> 16) * (red>>16) >> 11) << 10 |
	             ((RGB >> 8 & 0xff) * (gre>>16) >> 11) << 5 |
		     (RGB & 0xff) * (blu>>16) >> 11;
      (RGB is the color of the unlighted texture in a 32-bit long word.
      red, gre, and blu are bilinear interpolated values of red, green, and
      blue in 16:16 fixed point format. *tm++ puts the result in the lighted
      texture.)

About the texture cache:
------------------------

The unlighted texture maps and static light-maps are just loaded in memory
and are not really put in a cache. Texels of textures in the cache are
calculated as is explained in the above summary.

For every polygon there is the following information:
    - an unlighted texture
    - a static RGB lightmap (which are actually three lightmaps: one for
      every color component).
    - a set of shadowmaps which are used by the pseudo-dynamic lights.
      Pseudo-dynamic lights are static lights that cannot move but the
      intensity/color can change (uses for this are lights that can be
      switched on or off). When the precalculation of the static lightmaps
      is done pseudo-dynamic lights are also calculated but their
      information is not put in the static lightmap. Instead every
      pseudo-dynamic light creates a shadowmap for the polygons that are
      hit. This shadowmap contains information about where and at what
      distance the light hits the polygon. Later on this shadowmap is then
      combined with the static lightmap using the current color/intensity
      of the pseudo-dynamic light.
    - a set of light-patches created by dynamic lights. Light-patches are 3D
      polygons which define where a dynamic lights hits the polygon. A
      light-patch is coplanar with the polygon it belongs too and is always
      convex.
    - finally there is the real RGB lightmap which is the static lightmap
      with all other shadowmaps and light-patches merged. This is the lightmap
      that is finally used in the texture cache.

Whenever a pseudo-dynamic light changes intensity or a real dynamic light
changes state (moves or changes intensity) the real lightmap needs to be
recalculated. To do this, first the static lightmap is copied onto the real
lightmap. Then the shadowmaps are added (using the distance information as
found in the shadowmap and the current color of the light). Finally all the
light-patches are rendered on top of this. Since those are convex polygons
you can easily render them using a scanline drawer (this is not done currently,
it is still on my todo list). So in fact there are no dynamic lightmaps, only
light-patches.

When this is done the texture cache is notified so that it can recalculate
the lighted texture using the new lightmap.

Note that there are several optimizations that are going on as well. For
example, when the real lightmap is calculated that routine also sees where
the lightmaps is REALLY modified compared with the previous time. Only the
modified parts are then recalculated by the texure cache. This greatly
speeds up the rendering time of a small dynamic light hitting a large texture.

Another optimization is that only the sub-textures that are really visible are
recalculated in the texture cache. A sub-texture is a 32x32 part of the real
texture.

Hope this helps a little? I will put this document with Crystal Space as it is
useful enough.  


