gdalgorithms-list

[Algorithms] Re: Lightmap Terrain (dynamic range)

[Fredo D. <fr...@gr...>]

Right, displaying the high dynamic range of real conditions on a CRT
display (at best limited to a 1-100 contrast) is a hard problem.
See the thesis by Tumblin
http://www.cc.gatech.edu/gvu/people/jack.tumblin/
for very interesting discussions about the problem.

For dynamic conditions, one way is to try to simulate human visual
adaptation to attempt to provide a visual impression as close as
possible. 
There is a paper at siggraph this year on the subject
http://www.graphics.cornell.edu/pubs/2000/PTY+00.html
and I have done something on the subject too:
http://graphics.lcs.mit.edu/~fredo/PUBLI/EGWR2000/index.htm
(a much more comprehensive version should be available soon at the same
address)

But right, flares are crucial and very efficient at increasing the
subjective dynamic range of images.

Bottomline: the problem is exactly the same for cinema and video, so if
you're happy with the "sun impression" that you get on films, there is
no physical limitation with your CRT display that will prevent you from
getting teh same with 3D games. 

Fredo

--
Fredo Durand,  MIT-LCS Graphics Group
NE43-255, Cambridge, MA 02139 
phone : (617) 253 7223  fax : (617) 253 4640 
http://graphics.lcs.mit.edu/~fredo/

Re: [Algorithms] Re: Lightmap Terrain (dynamic range)

[Tom H. <to...@3d...>]

At 02:52 PM 8/25/2000, you wrote:
>Bottomline: the problem is exactly the same for cinema and video, so if
>you're happy with the "sun impression" that you get on films, there is
>no physical limitation with your CRT display that will prevent you from
>getting teh same with 3D games.

Very true. I for one don't really want a CRT capable of emitting energy 
ranges equal to real life. I mean, staring into the sun hurts :)

I did a lot of work on dynamic range management for digital cameras a 
little while back. The techniques I used where based on pixel statistics 
(histograms) of the luminance values of the image in a feedback system 
(calc statistics for current frame, adjust next frames exposure time and 
digital gains to compensate). I came up with a pretty sweet system that 
would converge on an answer in very few frames, and was very resistant to 
oscillations (even with the optimizations required to be workable in cheap 
hardware).

Adjusting gamma values will not give you the desired result however. A 
couple of reasons:
1. You'll get banding as you stretch or squish the range by any significant 
amount. Applying any gamma value other than 1.0 (identity) throws away bits 
of color resolution.
2. Going from inside to outside is a HUGE range shift ... on the order of 
~200 Lux for a normally lit office inside to ~5000 lux for outside at noon 
in the summer on a clear day. Not something that will scale well with just 
a gamma change.

My biggest problem is finding a good way to extract intensity information 
from the scene. The simplest method is to read the pixels back from the 
frame, calculate the statistics I've mentioned above and scale the 
lightmaps accordingly (which means everything gets a light map ... even the 
sky). Of course, reading back the frame buffer into system memory to 
perform the calculation is slow at best.

Another possibility would be to attach intensity information to surfaces 
and accumulate the statistics on those as they're added to the scene. 
Unfortunately this doesn't give you very good information about occlusion.

Another idea I just had would be to create low-res imposters for the items 
in the scene (people and cars would be cubes, etc) and render these with 
software into an intensity image with proper occlusion tests (zbuffer ... 
span buffer .. whatever). The result could then be used to get a coarse 
approximation of the scene intensity. With something like a span buffer you 
would never need to generate the image itself as you could calculate pixel 
statistics from the spans and still have proper occlusion.

Tom

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

[Algorithms] It looks terrible (was: Lightmap Terrain)

[Klaus H. <k_h...@os...>]

Hi all,

Please have a look at the following image (~310 KB):
http://www.thecore.de/TheCore/shadows.jpg

This lightmap looks majorly terrible, and I'm looking for ways to enhance
this. I use the simple dot-product approach, and I have two light source.
One light source (sun) is to the east, and the other ('anti' sun) is to the
west. I use two light sources, because I don't like ambient. I compute the
light for each texel, and then I cast a ray towards the sun (directional
light). If this ray intersect with the surface before it reaches the sun,
then I decrease the texel's intensity by some amount. I don't reflect or
refract rays. I figured, that reflection probably wouldn't make much sense,
because there's only a few cases where the reflected ray would hit the
terrain again (or am I wrong?).

How can I make this look better? For example, is there a way to have real
penumbrae in the shadows. Of course, I could blur the image, but that just
wouldn't be the same.

Any ideas? Honestly... a simple dot-product (without shadows) looks more
than twice as good (I can upload the same scene without shadows, if
requested).
Niki