🚀 go-pugleaf

"Let there be light"
--------------------
  "...and colour?"

by Steve McCrea, s...@eng.cam.ac.uk, 2nd February 1995

Following on from "Speedy free direction texture mapping, and other
neat tricks", by Hakan 'Zap' Andersson, z...@lysator.liu.se, posted to
comp.graphics.algorithms on 2/2/95.

0. Introduction

Zap left the question of source lighting polygons in a 3D game open.
Here's my stab at filling in the information gap. Having read Zap's
article, in the spirit of Zap I gave the problem some thought...

1. Theory

Here are the assumptions used in the document:
(1) Light in 3D games comes in two forms: ambient and point light sources.
(2) At any vertex, the local light level is given by
	ambient + sum of contributions of point light sources

The ambient light level is stored at the vertex. The contribution of
a point light source depends only on its brightness and distance from
the vertex. A distance calculation, then a simple lookup. So no
problems there.

OK, you may have guessed, we're just going to interpolate the brightness
between the vertices, so on average we only need one actual light calc
per polygon. This should look fine as long as the polygons are small;
for example the extreme cases would be

(a) a light source over a vertex - very bright there, but fades quickly
    towards the far edges of the polygons sharing the vertex.
(b) a light source in the centre of a polygon - all vertices have
    approximately the same brightness.

On large polygons, however, a light source would produce no noticeable
lighting effect unless the source was near one of the vertices. Check
this out in Descent, for example: go to the big room next to the
entrance of the second mine. Get close to the roof (the big dark wall)
and fire a flare from the centre towards one of the corners. Oh dear.

2. Implementation

So how do we implement it in practice? Referring to that other
document (see above), in the skewed scanconverted quad, we can just
use a simple DDA technique both to find the local light levels at the
'left' and 'right' edges of the scanconverted quad, and subsequently
along the 'horizontal' lines. Only four divisions needed, one per
polygon edge. Finally we know that each 'horizontal' line is at a
constant Z coordinate, and one lookup per pixel gives the perceived
brightness.

There will be some distortion of the lighting so that it isn't
linear with world distance within a quad, but so what? It's pretty
rough anyway...

It might be possible to correct the large polygon problem to some
degree by brightening the vertices of polygons by an amount relative
to the distance of the point source from the plane of the polygon,
and the area of the polygon. But I suspect it may overly light
adjacent polygons... Some fine tuning is probably required here :)

3. Colour

That hint of colour... The ambient and point sources could easily be
made to be coloured light, with each having hue, saturation, and
brightness values. Then we need to use the DDA technique on the
individual h,s,b elements of the colours in the scan conversion, and
to have a further lookup to determine the final colour.

Just guessing here, but a big quantisation of hue, saturation, and
brightness to say 64, 16, and 64 levels would I think work. So a 64k
lookup table, with an expensive lookup (including some shifts and
ORs) per pixel.  Tricky to choose an appropriate 256 colour
palette... (Whatever happened to h,s,b graphics cards? :) I hear that
the Atari Jaguar uses h,s,b. Nice.) Alternatively we could use rgb
(and brightness?) and make the scan conversion even harder to
optimise, with loads of digital differences etc in the inner loop. :(

Maybe the random dithering mentioned in that other document could
reduce the need for an optimal palette greatly, although I have my
doubts about the speed of a chaotic random number generator.

Steve McCrea, Trinity College, Cambridge
s...@eng.cam.ac.uk