Re: [Algorithms] Re: Lightmap Terrain (fast shadow calculation)

[Johan H. <jh...@mw...>]

Hi

I want to bring the subject back to shadow calculation. I have 2 algorithms
in mind, both of which can be acelerated by 3d hardware, that may be of
interest. I need some feedback on this, and maybe it helps some of you.

(To Ben Discoe, I will write this up for the VTP website once the dicussion
is finished if you want. I will probably post this on my website, and you
can refer there, or just copy it.)


1.    RADIOSITY
The fisrt is a radiosity approach. I am going to asume all of you know what
radisity is and basically how it works. The intereseting part is how this
very slow algorithm can be adapted to run in 3d hardware.

By rendering a 180 degree FOV scene (you shoudl use a non standard
projection system, ask me if you want the details) from every point in the
landscape where you want to calculate the shadow, you get the picture of
what is happening there. By locking the bach buffer and reading the values
back, the total amount of light that falls on this point can be calculated.
This is obviosly true for any computer scene, not just landscapes.
By rendering just 32x32 or 64x64 pixels, this can be done at a 100
calculation per second easily.

Another aproxmation for landscapes would be to render a very small FOV
(fraction of a degree) 1x1 pixel scene  in the direction of the sun, and
determine weather the sun is visible or not.

A bonus of both of these approaches is that shadows of clouds, and all
static objects appear automatically and correct



2.    ZBUFFER SHADOWS
This asumes that you know how to generate stencil buffer shadows in real
time (please ask if you dont), and is probably the fastes method of the two
(maybe real-time capable with a bit of caching)

Start off by rendering the area that you want to calculate in a top down
view into a back buffer with Z buffer enabled. The color should be white,
and every pixel in the back buffer should represent a height grid point.

Now you have a backbuffer that is completely white, with a Z buffer, with
the height of the corrsponding terrain in it.

Next, take the grid of heights, that may affect this area. (Note, this may
be the same grid as above, or a bigger area if you are only doing a partial
update) From each of those points, render a black quadrilateral into the
back buffer that has the following properties.
    The quadrilateral is 1 pixel wide.
    On plan view, its direction is in the sun direction
    Its slope is set at the sun angle
    It starts fro the exact position and height as the point that generates
it.

As long as the Z buffer of this quadrilateral is bigger than the Z values in
your Z buffer, it will get drawn, and that area is in the shadow. Thus your
shadow pixels will be black.

Now lock the buffer and read out your shadow map. The drawback to the
radiosity approach is that you will have to add cloud and object shadows
afterwards in some manner.
Also note that you still have to do the dot product lighting  for those
pixels in the light. One soluution may be to render the orriginal height
grid with the dot product lighting, rather than white. I can discuss later
why that wont work.

    POSSIBLE OPTIMIZATIONS FOR REAL TIME OPERATION.
If you are able to cache these shadow pictures, there is a possible
optimization than can get this to run in real-time. Since you don't need the
full shadow resolution over the area that you are drawing (large areas is
too far away to see this), you could start off on a course grid, and
calculate the shadows for a tile, by taking the heights on that tile, and
the 3 possible neighbours in the direction of the sun into acount (note that
this limits the distance that shadows can be thown). Save this low res
shadow.

When you get close to the area, blt this shadow into a bigger surface,
expandinf the pilxels and blurring the image. Thsi blurrign is correct since
through difraction and other processes, mountains do not cast sharp shadows
at a distance. Now take the heigher resolution height grid, (but only for a
smaller area), and add any heigh detil shadows that may arrise from this.

You can probably also optimize, by doing a dot product of the sun vector,
and the normal at each point in the landscape fisrt. Only those which are
very close to zero, are at edges and will through shadows. You dont have to
render a shadow quad far any of the other points.



I hope this helps a lot of you, and I hope to get some feedback on this as I
have to schoose a method of shadow calculation for my own code soon.

Johan Hammes
Nineteenseventyfive
http://mzone.mweb.co.za/residents/jhammes/main.htm