gdalgorithms-list

[Algorithms] Unattainable effects?

[Michael S. H. <mic...@ud...>]

"...it may be hopeless to simulate them realistically on a computer screen"

b**lsh*t

:-)

And there will never be more than five computers in the entire world.  (check your computer history if you don't recognize that statement).

I completely agree with you that the effects you mention are important to realistic simulation of our world, and they will be possible someday.  With the way that technology is progressing, that day may not be more than a few years (decade?) away.

It's possible to do those effects now, as long as you don't want interactive frame rates.  The frame rates will continue to go up though, and with them, the effects to bring the rates right back down. :-)

At 10:22 AM 8/25/00, you wrote:

>The more I look at real outdoor environments (eg. life) the
>more I feel that it may be hopeless to simulate them realistically
>on a computer screen.  The problem is the sun.  The sun is so
>bright, and so strongly affects our experience outdoors, that you
>can't make a realistic outdoor enviroment without a blindingly
>bright sun, sharp specular reflections on water and cars, etc.
>These are very bright, very high frequency effects that are very
>very hard to model.  Also, back-lighting by the sun, such as the
>halo around an opaque object, or the glow of the sun through a
>tree's leaves (take a look at that, it's amazing, and happens
>quite often).  
>
>IMHO this is orders of magnitude more important to visual realism
>than radiosity on landscapes.  Diffuse lighting looks reasonable
>with just the parrallel light from the sun (properly shadowed,
>of course, perhaps with a slower-than-Lambertian angle dependence)
>and ambient.
>
>-------------------------------------------------------
>Charles Bloom    cb...@cb...    http://www.cbloom.com
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list 

RE: [Algorithms] Lightmap Terrain

[Bernd K. <bk...@lo...>]

Charles Bloom writes:
 > The more I look at real outdoor environments (eg. life) the
 > more I feel that it may be hopeless to simulate them realistically
 > on a computer screen.  The problem is the sun. 

Isn't the Sun just a special case of a general problem:
the way we handle dynamic range between graphics card and CRT's? 

Quake3 has a concept of "overbright" (subdividing the dynamic
range to reserve some for intense light sources). Extending the 
color channel range in processing paths in 3D accelerators, 
or using e.g. 16bit float per color channel in framebuffers
might be a way to do this for real. Ultimately, if you want to 
model a flash grenade, you might find this even more 
difficult - and you might not want to model its effects to 
accurately anyway.


 > IMHO this is orders of magnitude more important to visual 
 > realism than radiosity on landscapes.  

Radiosity was used for Q2, and dropped for Q3, seemingly
because it made the job of the map designer harder. One
example that creating environments is still seen to be 
more about control than consistency.

I am not sure how far you want to push visual realism
(and I am confident that it is a red herring at best,
and a hazard at worst, when it comes to creating immersive
environments), but IMO games have already done good jobs 
with these effects. Personally I find the Halo/Sun effects
in Heretic2 well done. You can use particles to do specular
glitter on water or snow. What's missing is the intensity,
a bigger dynamic range at the top, isn't it?

I also think that physiology simulation might be just as 
essential for the reaslism you strive for: if the player 
moves from bright outdoors to dimly lit indoors, do you 
gamma correct to account for the adaptation period? Do 
you change gamma to create pale outdoors when the Sun comes 
out behind a cloud, or blend to change colors? Simulating 
the eye might be more effective than simulating the world.

Anyway, I would expect effects like refraction and 
dispersion to be more challenging. Not to mention 
relativistic FOV distortion and Doppler shift ;-).
Realism is such a wide scope, you gotta fence it 
with relevance...



                                         b.

[Algorithms] VDPM vs ROAM

[Kevin L. <lac...@in...>]

Which algorithm is a smaller O. VDPM or ROAM. I am looking at fractally
creating a height map for an entire planet and would like to know which of
the two common terrain techniques is less computationally intense.

Kevin

-- 

RE: [Algorithms] Lightmap Terrain

[Charles B. <cb...@cb...>]

The more I look at real outdoor environments (eg. life) the
more I feel that it may be hopeless to simulate them realistically
on a computer screen.  The problem is the sun.  The sun is so
bright, and so strongly affects our experience outdoors, that you
can't make a realistic outdoor enviroment without a blindingly
bright sun, sharp specular reflections on water and cars, etc.
These are very bright, very high frequency effects that are very
very hard to model.  Also, back-lighting by the sun, such as the
halo around an opaque object, or the glow of the sun through a
tree's leaves (take a look at that, it's amazing, and happens
quite often).  

IMHO this is orders of magnitude more important to visual realism
than radiosity on landscapes.  Diffuse lighting looks reasonable
with just the parrallel light from the sun (properly shadowed,
of course, perhaps with a slower-than-Lambertian angle dependence)
and ambient.

-------------------------------------------------------
Charles Bloom    cb...@cb...    http://www.cbloom.com

RE: [Algorithms] Lightmap Terrain

[<sro...@te...>]

>I guess you mean the grid-tracing algorithm...

Yes, well grid tracing is a sort of ray tracing :)

>Especially the initial "error" (see paper) is very confusing. Musgrave
says,
>that this "error" variable needs to be initialized with an octant-specific
>value, but he doesn't actually say what exactly that error variable does.
>Well, I figured it out, but IMO it needs to be initialized with a
>quadrant-specific value, and not with an octant-specific value.

Okay

>I hope to see some ray-traced terrain soon :)
>Niki

Me too i hope :)

Meaby that can interrest some people to know but my terrain
use sort of "Level-of-detail Management for Real-Time
Rendering of Phototextured Terrain" from Peter Lindstrom...
http://www.gvu.gatech.edu/people/peter.lindstrom/papers/tr/
and get better perforance with this technique on my old and
new computer than CLOD/ROAM(from demo i see, sounds weird but it's true).

The main difference is sending big indexed striped data is better then
simple fan or triangle list and the cpu do nothing (not like roam).
The result is good FPS and better terrain quality. Well my terrain is
not perfect and not finish :) but i think this is one technique
people need to try.

The main difference now i dont show all data just a
part(33% of 1025x1025 from the view frustum with fog) so meaby
my FPS will drop if i show all the terrain :) but anyway i added
a planet curve on the terrain so the mountain begin to disapear after 33%...

Corrosif

RE: [Algorithms] Lightmap Terrain

[Pallister, K. <kim...@in...>]

Which could probably be hacked pretty well by calculating the directional
lighting/shadows, and the blurring the texture once or twice. Also, turning
up the ambient a little would help too.

Kim Pallister

We will find a way or we will make one.
                     - Hannibal


> -----Original Message-----
> From: Martin Fuller [mailto:mf...@ac...]
> Sent: Friday, August 25, 2000 3:18 AM
> To: 'gda...@li...'
> Subject: RE: [Algorithms] Lightmap Terrain
> 
> 
> The trouble with outdoor area's is the sky. If you have a 
> clear day you will
> get very hard edged shadows as the sun light comes down more or less
> parrallel. However if you have lots of cloud then the 
> sunlight that is not
> reflected back into space by the cloud layer tends to get 
> diffused alot on
> the ground. Thus there are no really hard shadows. 
> 
> Radiosity deals well with reflected light in shadowy areas it 
> does not deal
> very well with direct light. The best renders I have seen yet 
> in computer
> graphics are hybrid raytracing radiosity engines utilising 
> raytracing only
> for the specular light component and radiosity for the 
> diffuse. (I did see a
> paper on view depedant radiosity once but that thread of 
> though seems to
> have died)
> 
> A landscape is for all intensive purposes flat, the average 
> variation in
> altitude is pretty insignifcant compared to the size of the 
> planet. For most
> of the day except extremes of sunrise and sunset most things 
> will be in
> direct sunlight without shadow. Even during sunrise and 
> sunset because the
> world is nominally flat there is going to be very little 
> reflection where
> energy would bounce more than once of the world. The first 
> radiosity bounce
> is more likely than not to send energy straight back into 
> space or cloud. If
> you consider how much our atmosphere protects us from the 
> direct sun (in the
> first hit) any energy bounced back to the cloud layer and 
> then back to earth
> will have diminished to insignificant levels. Radiosity only 
> noticably works
> well in areas of shadow with flat surfaces. Texture (such as 
> grass) tends to
> scatter / average the light.
> 
> The trouble with the classic radiosity algorithm is that to 
> work it requires
> an enclosed environment from which energy cannot escape. 
> Trying to deal with
> this condition on a kind of universal scale provides all 
> sorts of headaches.
> A lamp in an entirely enclosed room with good flat surfaces 
> is much more
> trivial case. How Quake2 delt with energy loss from sky boxes 
> I don't know
> but I expect this was fudged and the sky box was allowed to 
> reflect energy.
> Certainly oudoor areas in Quake have always looked wrong 
> while the enclosed
> environments have been very convincing.
> 
> I would expect for outdoor situations raytracing to be the 
> most successful
> technique. For cloudy simply dropping the raycast and performing an
> averaging fudge (don't like that word but..) on the light 
> calculation to
> simulate radiosity bleed might be sufficient to give 
> convincing results. A
> full blown radiosity solution is likely to be expensive in terms to
> development time and processing and is IMO not going to give you good
> results.
> 
> Cheers,
> Martin
> 3D Programmer
> Shadowman2
> 
> 
> 
> -----Original Message-----
> From: Ivan-Assen Ivanov [mailto:as...@ha...]
> Sent: 25 August 2000 02:02
> To: gda...@li...
> Subject: Re: [Algorithms] Lightmap Terrain
> 
> 
> Neither embossing the heightmap nor dot-products work well. 
> The resulting lightmap doesn't give you any clue of where the depths
> and heights are (e.g. inverting the heightmap and moving the 
> sun at the
> opposite azimute produces the same image).
> I'm currently thinking about a simple raytrace, but I feel it will be
> effective
> only with low elevations of the sun over the horizon. We don't have
> any sharp features in the heightmap.
> 
> Has anybody tried "full" radiosity (whatever that means - 
> e.g. different
> reflectance/
> absorption for textures/ecosystems) on heightfields? Do you 
> think it would
> be worth the trouble?
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] Lightmap Terrain

[Pallister, K. <kim...@in...>]

I don't know that a radiosity solution would buy you that much in an outdoor
type environment, depending on how many light sources you have other than
the sun. 

If it's only the sun, I'd do the lightmap generation in two passes. First,
run over the texture and do the usual ambient + diffuse calculation using
the normals at each texel. Secondly, I'd run over the map doing a sort of
line tracing scheme to determine whether the given texel falls within shadow
of a mountain or not (from the texel, step towards the sun, increasing from
the texels height a bit, and if you hit a texel with a higher heightmap
value, you are in shadow). If you find a shadow, reset the color from the
first pass to ambient value.

Kim Pallister

We will find a way or we will make one.
                     - Hannibal


> -----Original Message-----
> From: sro...@te... [mailto:sro...@te...]
> Sent: Thursday, August 24, 2000 12:54 PM
> To: gda...@li...
> Subject: [Algorithms] Lightmap Terrain
> 
> 
> Hi!
> 
> I trying to find how to generate a lightmap/illumination/shadow on a
> terrain.
> Do you know some good tutorial/code/links talking about that?
> 
> I want something to generate a lightmap on a (1025x1025 
> terrain). A good
> generation
> if possible like compute the the light from a point. I want 
> generate the
> lightmap
> just before the use of the terrain and i dont want something 
> that i need to
> pre-calculate and put the result on a file or something like.
> 
> Thanks,
> Corrosif
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] Lightmap Terrain

[<sro...@te...>]

Now my light is static (sun dont move) but i will modify that for use
dynamic soon like
you re-calculate only the visible chunk when and only when the sun change
about 5 degree
You dont really need to calculate that on each frame and each degree, that
could be a solution
and store the lightmap on lightmap array to track your data anytime. so just
put
the color(lightmap) on the vertex when rendering

for static object this could be added into the lightmap easyly i think :)

Corrosif

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Leigh
McRae
Sent: Friday, August 25, 2000 9:29 AM
To: gda...@li...
Subject: Re: [Algorithms] Lightmap Terrain


  I have seen people reply with many good ideas on this lightmap thing so I
am guessing that many people are going with lightmaps for terrain.  I am
wondering if these people have a fixed position for the main light source
such as a sun.  I am currently using vertex lighting as it was very quick to
get going and it looks good even with a LOD algorithm.  Are lightmaps being
generated as the sun moves?   Do the lightmaps light static objects also?  I
was also worried of loosing a multi-texture to lighting when I could use it
for noise or something else.  What about DOT3, does anyone have an idea how
fast it would be?

Leigh
----- Original Message -----
From: <sro...@te...>
To: <gda...@li...>
Sent: Thursday, August 24, 2000 3:54 PM
Subject: [Algorithms] Lightmap Terrain


> Hi!
>
> I trying to find how to generate a lightmap/illumination/shadow on a
> terrain.
> Do you know some good tutorial/code/links talking about that?
>
> I want something to generate a lightmap on a (1025x1025 terrain). A good
> generation
> if possible like compute the the light from a point. I want generate the
> lightmap
> just before the use of the terrain and i dont want something that i need
to
> pre-calculate and put the result on a file or something like.
>
> Thanks,
> Corrosif
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

[Algorithms] Rolling Ball Algorithm GGemsIII

[Dave S. <Dav...@sd...>]

I'm trying to implement the Rolling Ball Algorithm
for viewing objects, and I'm having a problem getting
it right.

If I have a view camera represented as a three
axis coordinate system <X,Y,Z> at location <P>.

I construct the matrix ,M, as described in the GemsIII
article.

If I want to apply the matrix to my coordinate
system,

1)  Does that make sense?  I want to apply above rotation
to a coordinate system. 

Translate coordinate system to the origin
Apply M to the <X,Y,Z>.  This involves inverting
M. 

X' = INV(M) * X   
Y' = INV(M) * Y  
Z' = INV(M) * Z   

Translate back to coordinate system location, <P>.

2)  Is the M in the algorithm supposed to be orthogonal?
Since it's a pure rotation, I would hope so. (Right?)
(ie.  So that it would be nice for INV(M) = Transpose(M))

Are there other types of algorithms similar to this
for viewing objects in 3D that involve the camera being
focused on an object and the mouse motions rotating
about that object.  I've done some crude things in this
area but would like to find a better one, similar to 
what most CAD tools use.

Thanks for any help,
-DaveS

Re: [Algorithms] Lightmap Terrain

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

> Sorry for the response delay. I sended a response but from a other mail
> address so i think
> I need to rewrite this mail anyway. I will response for all reply answered
> about this thread.
>
> Thanks Niki it's exaclty a sort a raytracing a was thinking. I will check
> the doc carefully.

I guess you mean the grid-tracing algorithm... I'm currently implementing it
myself. For now I use a simple GDI test program (no terrain engine), because
you need to see that the ray is properly traced through the grid. I've got
the x-driven, and y-driven DDAs working now, but it was a major pain. The
main problem is the pseudo-code in Appendix A in the paper, because there
are a couple of variables without any useful explanation of what they do.
Especially the initial "error" (see paper) is very confusing. Musgrave says,
that this "error" variable needs to be initialized with an octant-specific
value, but he doesn't actually say what exactly that error variable does.
Well, I figured it out, but IMO it needs to be initialized with a
quadrant-specific value, and not with an octant-specific value.

I hope to see some ray-traced terrain soon :)
Niki

RE: [Algorithms] Lightmap Terrain

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

It is a classical misunderstanding to believe that radiosity needs
closed environments.
There is no problem (neither theoretical nor practical) with unbounded
scenes.

Francois Sillion has a paper about hierarchical radiosity for terrains
and sky:
Hierarchical Lighting Simulation for Outdoor Scenes 
http://www-imagis.imag.fr/Membres/Francois.Sillion/Papers/Index.html

I had also seen some work that simulated the interreflexions between
mountains to simulate the snow coverage. Can't remember where though.

if you want radiosity code:
http://www.graphics.lcs.mit.edu/~fredo/Book/code.html
under global illumination

But this won't give you real-time.
I guess you could accelerate this by doing only one bounce, and by
gathering light only from nearby vertices.

See also the paper by Heidrich et al. at Siggraph this year, it is in
fact very related (they compute interreflections for bump maps, and bump
maps are height fields). It is also quite related to the horizon map
idea discussed in a previous e-mail.
http://www.ag2.mpi-sb.mpg.de/~heidrich/

But, as already said, there is no way you can in a cheap way integrate
smoothly the illumination coming from the sky.

I guess you could use a simple heuristic for the sky illumination from a
vertex. What you want to do is to integrate the light coming from the
whole sky, that is, a hemisphere, taking shadowing into account.
Assume that only the adjacent faces and the global terrain hide the sky.
Thus, for each face you subtract the corresponding wedge from the
hemisphere (I have made a figure at
http://graphics.lcs.mit.edu/~fredo/sky.jpg)
I'm sure that this has been already used somehere, but I have no idea
where.

For the shadowing of direct lighting from the sun, I don't know if
Musgrave describes such an optimization, but you could also sweep
"shadowing horizons" from the parallel light source direction to compute
the illumination along parallel lines on the terrain. Sounds not clear?
See the figure http://graphics.lcs.mit.edu/~fredo/shadow.jpg
Note that because the light direction is not a multiple of 45 degrees,
the sweep lines don't fall on all the vertices. Well, I'm sure that you
can find a way to deal with that with weights or something else.

To summarize, you have three problems:
- illumination from the sun (the most important light source): use the
cosine law, parallel light source and maybe try my sweep idea
- illumination from the sky (very important for overcast days), nasty
but intersecting the wedges from the hemisphere may give you something.
- interreflexion from the neighbouring terrain: I propose to consider
only one bounce from the adjacent vertices. Of course add an ambient
term too.

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] Lightmap Terrain

[Leigh M. <lei...@ro...>]

  I have seen people reply with many good ideas on this lightmap thing so I
am guessing that many people are going with lightmaps for terrain.  I am
wondering if these people have a fixed position for the main light source
such as a sun.  I am currently using vertex lighting as it was very quick to
get going and it looks good even with a LOD algorithm.  Are lightmaps being
generated as the sun moves?   Do the lightmaps light static objects also?  I
was also worried of loosing a multi-texture to lighting when I could use it
for noise or something else.  What about DOT3, does anyone have an idea how
fast it would be?

Leigh
----- Original Message -----
From: <sro...@te...>
To: <gda...@li...>
Sent: Thursday, August 24, 2000 3:54 PM
Subject: [Algorithms] Lightmap Terrain


> Hi!
>
> I trying to find how to generate a lightmap/illumination/shadow on a
> terrain.
> Do you know some good tutorial/code/links talking about that?
>
> I want something to generate a lightmap on a (1025x1025 terrain). A good
> generation
> if possible like compute the the light from a point. I want generate the
> lightmap
> just before the use of the terrain and i dont want something that i need
to
> pre-calculate and put the result on a file or something like.
>
> Thanks,
> Corrosif
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

RE: [Algorithms] Lightmap Terrain

[<sro...@te...>]

Sorry for the response delay. I sended a response but from a other mail
address so i think
I need to rewrite this mail anyway. I will response for all reply answered
about this thread.

Thanks Niki it's exaclty a sort a raytracing a was thinking. I will check
the doc carefully.

Basicly, i want pre-calculate the "radiance" just before the use of the
terrain. I know
my terrain will be sort of static but i want just some default shadow on the
terrain at the startup.

>Have a look at my article at http://www.tashco.com/terraintexturing.html
>Mark Allen

Well thanks but i dont have problem with texturing now :)


>Hi,
>http://www.dgp.toronto.edu/people/JamesStewart/papers/tvcg97.html

I already see that and contact the author, btw it's not that i want with
this technique
calculate a terrain of 1025x1025 take too much time and if you want be
faster you must
use a pre-calculed file(horizon file) to be fast but this file is more big
than the heightfield.
Finaly it's a very good solution for non-realtime application.

>The trouble with outdoor area's is the sky. If you have a clear day you
will
>get very hard edged shadows as the sun light comes down more or less
>parrallel. However if you have lots of cloud then the sunlight that is not
>reflected back into space by the cloud layer tends to get diffused alot on
>the ground. Thus there are no really hard shadows.

Well basicly my terrain if for a game, i dont want make a extreme realist
terrain now :)
just something very good for a game.

>Radiosity deals well with reflected light in shadowy areas it does not deal
>very well with direct light. The best renders I have seen yet in computer
>graphics are hybrid raytracing radiosity engines utilising raytracing only
>for the specular light component and radiosity for the diffuse. (I did see
a
>paper on view depedant radiosity once but that thread of though seems to
have died)

A simple raytracing can do the job for me now i think :).
For the hybrid raytracing i will take a look never heard this technique
thanks

Regards,
Corrosif

RE: [Algorithms] Lightmap Terrain

[Martin F. <mf...@ac...>]

The trouble with outdoor area's is the sky. If you have a clear day you will
get very hard edged shadows as the sun light comes down more or less
parrallel. However if you have lots of cloud then the sunlight that is not
reflected back into space by the cloud layer tends to get diffused alot on
the ground. Thus there are no really hard shadows. 

Radiosity deals well with reflected light in shadowy areas it does not deal
very well with direct light. The best renders I have seen yet in computer
graphics are hybrid raytracing radiosity engines utilising raytracing only
for the specular light component and radiosity for the diffuse. (I did see a
paper on view depedant radiosity once but that thread of though seems to
have died)

A landscape is for all intensive purposes flat, the average variation in
altitude is pretty insignifcant compared to the size of the planet. For most
of the day except extremes of sunrise and sunset most things will be in
direct sunlight without shadow. Even during sunrise and sunset because the
world is nominally flat there is going to be very little reflection where
energy would bounce more than once of the world. The first radiosity bounce
is more likely than not to send energy straight back into space or cloud. If
you consider how much our atmosphere protects us from the direct sun (in the
first hit) any energy bounced back to the cloud layer and then back to earth
will have diminished to insignificant levels. Radiosity only noticably works
well in areas of shadow with flat surfaces. Texture (such as grass) tends to
scatter / average the light.

The trouble with the classic radiosity algorithm is that to work it requires
an enclosed environment from which energy cannot escape. Trying to deal with
this condition on a kind of universal scale provides all sorts of headaches.
A lamp in an entirely enclosed room with good flat surfaces is much more
trivial case. How Quake2 delt with energy loss from sky boxes I don't know
but I expect this was fudged and the sky box was allowed to reflect energy.
Certainly oudoor areas in Quake have always looked wrong while the enclosed
environments have been very convincing.

I would expect for outdoor situations raytracing to be the most successful
technique. For cloudy simply dropping the raycast and performing an
averaging fudge (don't like that word but..) on the light calculation to
simulate radiosity bleed might be sufficient to give convincing results. A
full blown radiosity solution is likely to be expensive in terms to
development time and processing and is IMO not going to give you good
results.

Cheers,
Martin
3D Programmer
Shadowman2



-----Original Message-----
From: Ivan-Assen Ivanov [mailto:as...@ha...]
Sent: 25 August 2000 02:02
To: gda...@li...
Subject: Re: [Algorithms] Lightmap Terrain


Neither embossing the heightmap nor dot-products work well. 
The resulting lightmap doesn't give you any clue of where the depths
and heights are (e.g. inverting the heightmap and moving the sun at the
opposite azimute produces the same image).
I'm currently thinking about a simple raytrace, but I feel it will be
effective
only with low elevations of the sun over the horizon. We don't have
any sharp features in the heightmap.

Has anybody tried "full" radiosity (whatever that means - e.g. different
reflectance/
absorption for textures/ecosystems) on heightfields? Do you think it would
be worth the trouble?

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Lightmap Terrain

[Ivan-Assen I. <as...@ha...>]

Neither embossing the heightmap nor dot-products work well. 
The resulting lightmap doesn't give you any clue of where the depths
and heights are (e.g. inverting the heightmap and moving the sun at the
opposite azimute produces the same image).
I'm currently thinking about a simple raytrace, but I feel it will be effective
only with low elevations of the sun over the horizon. We don't have
any sharp features in the heightmap.

Has anybody tried "full" radiosity (whatever that means - e.g. different reflectance/
absorption for textures/ecosystems) on heightfields? Do you think it would
be worth the trouble?

RE: [Algorithms] Lightmap Terrain

[Mark A. <MA...@ac...>]

Have a look at my article at http://www.tashco.com/terraintexturing.html

Mark Allen

> -----Original Message-----
> From: sro...@te... [mailto:sro...@te...]
> Sent: 24 August 2000 20:54
> To: gda...@li...
> Subject: [Algorithms] Lightmap Terrain
> 
> 
> Hi!
> 
> I trying to find how to generate a lightmap/illumination/shadow on a
> terrain.
> Do you know some good tutorial/code/links talking about that?
> 
> I want something to generate a lightmap on a (1025x1025 
> terrain). A good
> generation
> if possible like compute the the light from a point. I want 
> generate the
> lightmap
> just before the use of the terrain and i dont want something 
> that i need to
> pre-calculate and put the result on a file or something like.
> 
> Thanks,
> Corrosif
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Lightmap Terrain

[Nikolay S. <ni...@we...>]

Hi,

http://www.dgp.toronto.edu/people/JamesStewart/papers/tvcg97.html

This basically involves precomputing the horizon for the points of the
landscape. It is simpler than radiosity, I think. Another idea would be to
do it as T. Ulrich does, by running the Emboss filter on the heightmap :-)

Niki

Re: [Algorithms] Lightmap Terrain

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

Sylvain was talking about lightmaps for *terrain*, and not about lightmaps
for games that play in a closed environment (like indoor games)

I've never heard about radiosity algorithms for open-environment terrain.
However, if there are any such algorithms, then I'd like to know, before I
finish my ray tracer for terrain...

Niki

----- Original Message -----
From: Akbar A. <sye...@ea...>
To: <gda...@li...>
Sent: Thursday, August 24, 2000 11:25 PM
Subject: RE: [Algorithms] Lightmap Terrain


> this has been discussed before, and since the archives aren't working i'l
> give you a drop.
> >Do you know some good tutorial/code/links talking about that?
> no.
>
> most often this is precalculate with a radiosity solution.
> use google (www.google.com) it's your friend.
> you will probably run into lots of new math in your adventure (it's worth
> it)
> this is a good math site http://mathworld.wolfram.com/
> Micheal Cohen has written a few good books on radiosity, you migt want to
> look into those.
>
> there is also an application which you can buy, it's called lightscape, i
am
> pretty sure a lot of pc companies as well as console have used this.
>
> peace.
> akbar A.
>
> "We want technology for the sake of the story, not for its own sake. When
> you look back, say 10 years from now, current technology will seem quaint"
> Pixars' Edwin Catmull.

Re: [Algorithms] OpenGL LockArrayEXT ... workaround

[Brian S. <br...@gl...>]

By the way, I just realized that this is on the algorithms list.  This 
should be moved to the Ope...@fa... list, in the interest 
of actually keeping lists' meanings intact.  Off-topic threads cause the 
kind of traffic volumes that inspire me to delete all the messages instead 
of read them.  Speaking purely hypothetically; my silence in the past few 
months is totally unrelated.  I swear.  ;-)

-Brian
==========
GLSetup, Inc.

Re: [Algorithms] OpenGL LockArrayEXT ... workaround

[Brian S. <br...@gl...>]

you wrote:
> > are you sure 4096 is the maxium size for optimized compiled vertex arrays?
> > I just though it was 1024, since q3 uses 1K vertex buffers (according to
>Brian Sharp's conference).

My conference?

Any information I have on Q3A is pretty much hearsay from Brian Hook.  Or 
maybe you're referring to Brian Hook, not Brian Sharp?  We're more 
different than our last names: I never worked for id. ;-)

At 11:30 AM 8/25/00 +0800, you wrote:
>It depends on the accelerator generally. Remember Brian worked on the 3dfx
>ogl drivers, which may mean his 1k number was based on those, rather than
>other drivers. I think most of the T&L cards are 4/8k.

So first of all, I don't see any actual defined limit (in the 
EXT_compiled_vertex_array spec) to the number of vertices you can 
lock.  The original poster should have no problem locking 100,000 
vertices.  If it's an issue of what implementations optimize for, that's 
kind of lame to write to that, especially because that's totally volatile 
and will probably change in most drivers before you ship.

In the existing 3dfx driver, at least, it'll optimize whatever you throw at 
it.  Sure, that's transformation happening on the CPU, but it guarantees 
that you don't end up retransforming verts.

The downside to that is the hypothetical case where someone locks a 30 
million vert array, and the driver allocates a ton of memory.  It can't be 
any more than the app already has allocated, but it's nonetheless potential 
for a lot of memory allocation.  So for future work it's being donw a 
different way, but it won't "not optimize" the arrays if they're over some 
size.

I'm not really sure what the motivation would be for a driver to not 
optimize arrays over a certain size.  I mean, they could only pretransform 
a set number and treat any more as regular verts to be 
transformed.  Hmm.  Especially if it's a hardware T&L implementation, where 
you'd obviously want to have a tiered caching system in the driver already, 
capable of locked arrays on the host bigger than your hardware cache.  I'm 
confused.

So, what was the original poster asking about?  Why couldn't he lock all 
his verts?  A driver crash?  A slowdown?  A spec misreading?

-Brian
==========
GLSetup, Inc.

Re: [Algorithms] OpenGL LockArrayEXT ... workaround

[Conor S. <cs...@tp...>]

It depends on the accelerator generally. Remember Brian worked on the 3dfx
ogl drivers, which may mean his 1k number was based on those, rather than
other drivers. I think most of the T&L cards are 4/8k.

Conor Stokes

> Conor Stokes wrote:
> > First of all, that is a vertex limit. Indices are generally unlimited.
> > Second of all, that limit is really only the limit at which the
extension
> > "optimises" the array via locking. Otherwise, its just like calling a
normal
> > vertex array call.
>
> are you sure 4096 is the maxium size for optimized compiled vertex arrays?
> I just though it was 1024, since q3 uses 1K vertex buffers (according to
Brian Sharp's conference).
>
>
> Ignacio Castano
> ca...@cr...
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

RE: [Algorithms] Lightmap Terrain

[Akbar A. <sye...@ea...>]

what algo did q3 use to light it's textures?

peace,
akbar A.

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Klaus
Hartmann
Sent: Thursday, August 24, 2000 5:30 PM
To: gda...@li...
Subject: Re: [Algorithms] Lightmap Terrain


Sylvain, :)

> Hi!
>
> I trying to find how to generate a lightmap/illumination/shadow on a
> terrain.
> Do you know some good tutorial/code/links talking about that?

Unfortunately, no, I don't know of any such papers and good code is also
very rare (I wasn't able to find any good code, yet). The only useful
related paper I know of is "Grid Tracing: Fast Ray Tracing for Height
Fields", by famous Mr. F. Kenton Musgrave. The paper does, however, not
explain how to light a surface, it only describes a fast algorithm to trace
a ray and intersect it with a height field. It is useful for many things.
Shadow feelers are a nice example. If you want to know, if a point on the
height field surface lies in shadow, then you can cast a ray from that point
to the light source, and then use the algorithm to trace the ray, and test
wheter it intersects with the height field (or any other object) before it
reaches the light source. If there is an intersection then the point lies in
shadow, and you decrease the intensity at that point.

> I want something to generate a lightmap on a (1025x1025 terrain). A good
> generation
> if possible like compute the the light from a point.

A simple, but not perfect, way to calculate the light at a point on the
height field is to use the dot product:
[1] Calculate the unit vertex normal, N, at the point, P, you want to
illuminate
[2] Calculate the unit direction vector, L, that points from point P towards
the point light source (or pre-calculate the single unit direction vector
for a directional light source).
[3] If the dot product I = L _dot_ N is smaller or equal to 0, then angle
between N and L is >= 90 degree, and the light source has no effect on point
P. If I is greater than 0, then the angle between L and N is smaller than 90
degree, and you can use I to illuminate the point:
point.r  = material.r * I * lightSource.r;
point.g = material.g * I * lightSource.g;
point.b = material.b * I * lightSource.b;

Note, that I actually is the cosine of the angle between the two *unit*
vectors, L and N. In general:
U _dot_ V = |U| * |V| * cos(angle(U, V))

where, U and V are two vectors, and angle(U, V) is the angle between the two
vectors U, and V. If U and V are both unit vectors, then:
U _dot_ V = 1 * 1 * cos(angle(U, V))
<=>
U _dot_ V = cos(angle(U, V))

So, if in the above example, N and L are not unit vectors, then you need to
compute I as follows:
I = (L _dot_ N) / ( |L| * |N|)

Here's a small performance tip w.r.t. point light sources (and spot lights).
If you use a point light source, then you need to re-compute L all the time,
because L depends on the point P. However, normalizing L all the time is
really expensive, and it is a waste of performance to normalize L, if the
light has no effect at the point P (the angle between N and L is greater
than 90°). You can speed this up as follows:

L = compute NON-normalized vector L
I = L _dot_ N;
if (I <= 0) then return; /light has no effect*/
I /= |L|;
point.r  = material.r * I * lightSource.r;
point.g = material.g * I * lightSource.g;
point.b = material.b * I * lightSource.b;

> I want generate the lightmap
> just before the use of the terrain and i dont want something that i need
to
> pre-calculate and put the result on a file or something like.

Not sure what you mean here...

HTH,
Niki


_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Lightmap Terrain

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

Sylvain, :)

> Hi!
>
> I trying to find how to generate a lightmap/illumination/shadow on a
> terrain.
> Do you know some good tutorial/code/links talking about that?

Unfortunately, no, I don't know of any such papers and good code is also
very rare (I wasn't able to find any good code, yet). The only useful
related paper I know of is "Grid Tracing: Fast Ray Tracing for Height
Fields", by famous Mr. F. Kenton Musgrave. The paper does, however, not
explain how to light a surface, it only describes a fast algorithm to trace
a ray and intersect it with a height field. It is useful for many things.
Shadow feelers are a nice example. If you want to know, if a point on the
height field surface lies in shadow, then you can cast a ray from that point
to the light source, and then use the algorithm to trace the ray, and test
wheter it intersects with the height field (or any other object) before it
reaches the light source. If there is an intersection then the point lies in
shadow, and you decrease the intensity at that point.

> I want something to generate a lightmap on a (1025x1025 terrain). A good
> generation
> if possible like compute the the light from a point.

A simple, but not perfect, way to calculate the light at a point on the
height field is to use the dot product:
[1] Calculate the unit vertex normal, N, at the point, P, you want to
illuminate
[2] Calculate the unit direction vector, L, that points from point P towards
the point light source (or pre-calculate the single unit direction vector
for a directional light source).
[3] If the dot product I = L _dot_ N is smaller or equal to 0, then angle
between N and L is >= 90 degree, and the light source has no effect on point
P. If I is greater than 0, then the angle between L and N is smaller than 90
degree, and you can use I to illuminate the point:
point.r  = material.r * I * lightSource.r;
point.g = material.g * I * lightSource.g;
point.b = material.b * I * lightSource.b;

Note, that I actually is the cosine of the angle between the two *unit*
vectors, L and N. In general:
U _dot_ V = |U| * |V| * cos(angle(U, V))

where, U and V are two vectors, and angle(U, V) is the angle between the two
vectors U, and V. If U and V are both unit vectors, then:
U _dot_ V = 1 * 1 * cos(angle(U, V))
<=>
U _dot_ V = cos(angle(U, V))

So, if in the above example, N and L are not unit vectors, then you need to
compute I as follows:
I = (L _dot_ N) / ( |L| * |N|)

Here's a small performance tip w.r.t. point light sources (and spot lights).
If you use a point light source, then you need to re-compute L all the time,
because L depends on the point P. However, normalizing L all the time is
really expensive, and it is a waste of performance to normalize L, if the
light has no effect at the point P (the angle between N and L is greater
than 90°). You can speed this up as follows:

L = compute NON-normalized vector L
I = L _dot_ N;
if (I <= 0) then return; /light has no effect*/
I /= |L|;
point.r  = material.r * I * lightSource.r;
point.g = material.g * I * lightSource.g;
point.b = material.b * I * lightSource.b;

> I want generate the lightmap
> just before the use of the terrain and i dont want something that i need
to
> pre-calculate and put the result on a file or something like.

Not sure what you mean here...

HTH,
Niki

RE: [Algorithms] Lightmap Terrain

[Akbar A. <sye...@ea...>]

this has been discussed before, and since the archives aren't working i'l
give you a drop.
>Do you know some good tutorial/code/links talking about that?
no.

most often this is precalculate with a radiosity solution.
use google (www.google.com) it's your friend.
you will probably run into lots of new math in your adventure (it's worth
it)
this is a good math site http://mathworld.wolfram.com/
Micheal Cohen has written a few good books on radiosity, you migt want to
look into those.

there is also an application which you can buy, it's called lightscape, i am
pretty sure a lot of pc companies as well as console have used this.

peace.
akbar A.

"We want technology for the sake of the story, not for its own sake. When
you look back, say 10 years from now, current technology will seem quaint"
Pixars' Edwin Catmull.


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of
sro...@te...
Sent: Thursday, August 24, 2000 2:54 PM
To: gda...@li...
Subject: [Algorithms] Lightmap Terrain


Hi!

I trying to find how to generate a lightmap/illumination/shadow on a
terrain.
Do you know some good tutorial/code/links talking about that?

I want something to generate a lightmap on a (1025x1025 terrain). A good
generation
if possible like compute the the light from a point. I want generate the
lightmap
just before the use of the terrain and i dont want something that i need to
pre-calculate and put the result on a file or something like.

Thanks,
Corrosif

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] OpenGL LockArrayEXT ... workaround

[Joe A. <jo...@ti...>]

> are you sure 4096 is the maxium size for optimized compiled vertex arrays?
> I just though it was 1024, since q3 uses 1K vertex buffers (according to Brian
> Sharp's conference).
Hi,

I wrote a little test app to find this out.
And at least on my G4 with an ATI Rage128, the maximum size depends on the
vertex data you use.
The buffer seems to be 64kb big.
So if you pass 2 TextureUV and one Vertex with 3 floats you get
65536 / (4*(3+2+2)) = 2340 vertices.

bye joe