gdalgorithms-list

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

[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

[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

[<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

[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

[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

[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.

RE: [Algorithms] Lightmap Terrain

[Stephen J B. <sj...@li...>]

On Fri, 25 Aug 2000, Bernd Kreimeier wrote:

> 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? 

Yes...and it's a hard problem.  CRT's are getting brighter
and other display technologies (direct laser-on-retina displays
for example) could actually produce real-world brightnesses (DANGEROUS!)

It's notable, however, that nobody complains about unrealistic
Television images - and they have the same brightness range as
your computer screen.

With the right combination of tricks like lens flare, you can
reproduce the *effect* of that extra brightness without actually
emitting more photons.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

Re: [Algorithms] Lightmap Terrain

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

> It's notable, however, that nobody complains about unrealistic
> Television images - and they have the same brightness range as
> your computer screen.

Yes, but please don't compare us to the brainwashed television masses out
there ................. :-)

Johan

[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 

[Algorithms] Building BSPs Robustly

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

A question for the BSP experts : what do you do to make
your BSP building robust (eg. numerically safe) ?
Is there an article on these issues? (still working on
that BSP article, Angel?).

Now for more detail.  Let me stick to two dimensions for
simplicity.  I'm building a 2d BSP from convex polygons.
To do that, you just take the polygon and send it down
the tree, clipping it against each plane in the tree.
Eventually you arrive at a leaf.  At that point I take
all the segments of the clipped polygon which arrives
at that leaf, and add them to the tree if and only if
the plane they create isn't already in the tree.  This
make it so that if you have a little empty leaf in
the tree and you add a polygon that covers it completely
you don't end up adding any planes, you just mark that
leaf is solid now.

Now, we run into robustness problems.  The first problem
is just with tiny segments.  Sometimes after clipping you
end up with very short segments in your leaves, that you
can't do a reliable cross product on to make a normal for
use in the plane.  I just throw out these short segments
(seems reasonable).

All of the remaining problems come from numerical errors
on the plane clipping.  This arises because when you take
a point, find the distance to a plane, and push it by
that distance, you don't end up with a point right on that
plane.

   d = plane.DistanceToPoint( point );
   point += d * plane.normal;
   d = plane.DistanceToPoint( point );

Now d is small, but not zero !  The point is slightly off
the plane in some direction.  This will always happen, no
matter how you do your plane clipping, and whether you
use floats or doubles (I use floats).

The result is that you can end up with non-convex polygons
in the leaves.  These can happen in 2 major ways (
see http://www.cbloom.com/bsp_problems.gif "):

1. "bend-ins".  This is when you have three verts that
are very nearly co-linear.  If the clipping had been perfect,
they would have been colinear.  Instead, the middle one fell
a bit to the inside of the other two, creating a very mild
star-trek-symbol shape.  I get rid of these by finding the
triangles that have very small areas and deleting their middle
vertex.

2. "fish-tails".  Take a triangle.  Duplicate one of the verts
to make it a quad with two verts right on top of eachother.
Take one of the duplicated verts and pull it across its twin
so that the segments of the quad intersect.  This makes a
segment with the wrong winding, two triangles with upside
down normals.  This is a big crisis for a BSP, because that
wrong-facing segment will make a plane facing the wrong way.
Most of the time, this will be fixed by deleting the very
short segments, but I still seem to get it once in a rare
while.  The rest of the time, I fix it by turning the segments
in to planes.  In my convention, proper planes will have
all the other verts of the polygon on its front side.  Thus,
any plane which has verts of the polygon on its back side
is simply tossed out, and its end-points are snapped together.

So, I find this all a bit scary (if I "fix" my leaf polygons
in the wrong way, I'll end up getting a BSP different than I
intended), and what's worse, I'm building these BSP's in real
time, and all this testing for convexity of the leaf polygons
is one of my biggest bottlenecks.  Help appreciated.

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

Re: [Algorithms] Building BSPs Robustly

[Angel P. <ju...@bi...>]

> A question for the BSP experts : what do you do to make
> your BSP building robust (eg. numerically safe) ?
> Is there an article on these issues?
>(still working on  that BSP article, Angel?).
Not yet, too busy right now. I hope to finish it next month.
 
> Now for more detail.  Let me stick to two dimensions for
> simplicity.  I'm building a 2d BSP from convex polygons.
> To do that, you just take the polygon and send it down
> the tree, clipping it against each plane in the tree.
> Eventually you arrive at a leaf. 

If you just want to create a BSP from all convex polygons - then
first put all edge segments from all polygons in the root node of the
BSP.

Then pick a hyperplane from one of the stored edges (polys in 3D ) and move
all edges in front of the plane to node->Front and all edges behind the
plane to node->Back. If node->Front or node->Back is NULL and an
edge has to be put in it - then create that leaf.
Handling edges that lie on the plane depends on the kind of BSP tree
you want to do:
1. If it's a solid BSP with polygons(3D) in the BSP leaves forming solid convex
clumps then move the edge to node->Back.
2. If it's a solid BSP with polygons(3D) in the BSP leaves forming hollow convex
clumps then move the edge to node->Front, this kind of BSP
is used for automatic portalization.
3. If it's a classic BSP with polygons(3D) in the BSP nodes - then just store that
polygon there.
Recurse through node->Front and node->Back.


The approach you described is more suitable to CSG operations using BSP
trees (this is actually quite fast and can be done in realtime).

You can safely delete the clipped polygons which arive in
"IN" NULL leaf. See this picture:
http://thegeleto.tripod.com/bsp-figure1.jpg
This will clip away the polygons that are inside the current BSP.

For the edges that end in "OUT" NULL leaf - create a new
BSP leaf and store the edge and it's hyperplane in it.

For edges that arrive at a BSP node and lie on the separating
hyperplane  for that node - for now just store it there (although it's
not that simple, see below)

You have to clip the BSP line segments to the convex hull (or BSP if
the polygon is concave) of the polygon. Because clipping ALL BSP
line segments can be very slow you can use the bounding circle of the
polygon to visit only nodes that potentially intersect it.

The result will be a classic BSP with edges stored at nodes

There are two optimizations that can be done with this:
1. When all edges from a BSP node were clipped to the polygon
- this node can be safely removed from the BSP if either node->Front
or node->Back is NULL (the node that is not NULL replaces the
current node in the BSP and the current node is deleted). If that node
is a leaf - simply delete that leaf.
2. When the BSP edges are clipped to the BSPed polygon they may
get split quite a lot even if nothing is clipped away. You can keep a binary
tree with the split history of the edge and restore the unclipped parts from it.
This is quite beneficial in 3D where merging polygons can be tedious.

> At that point I take
> all the segments of the clipped polygon which arrives
> at that leaf, and add them to the tree if and only if
> the plane they create isn't already in the tree.  
> This make it so that if you have a little empty leaf in
> the tree and you add a polygon that covers it completely
> you don't end up adding any planes, you just mark that
> leaf is solid now.

In my explanation on doing CSG above I said that when the edge lies on
a node's hyperplane it should be stored in that node. This is partially
true except that before doing that you have to clip that edge to both
node->Front and node->Back. If you want to handle decals properly
this becomes quite complicated ( you have to be careful how you clip
the BSP segments to the polygon, etc )
 
> Now, we run into robustness problems.  The first problem
> is just with tiny segments.  Sometimes after clipping you
> end up with very short segments in your leaves, that you
> can't do a reliable cross product on to make a normal for
> use in the plane.  I just throw out these short segments
> (seems reasonable).

Calculate the planes for the original polygons and store them with
the polygon. When it is split - set the same plane for the splitted
polys. If you use EPSILON aware polygon splitting routine(see below)
you should not have such short segments.

> All of the remaining problems come from numerical errors
> on the plane clipping.  This arises because when you take
> a point, find the distance to a plane, and push it by
> that distance, you don't end up with a point right on that
> plane.
> 
>    d = plane.DistanceToPoint( point );
>    point += d * plane.normal;
>    d = plane.DistanceToPoint( point );
> 
> Now d is small, but not zero !  The point is slightly off
> the plane in some direction.  This will always happen, no
> matter how you do your plane clipping, and whether you
> use floats or doubles (I use floats).

You should assume that a polygon/segment lies on a plane
if it's verts lie on less than some small (EPSILON = 0.001) distance
away from the plane. This hould not be a problem if your polygon
splitting routine is EPSILON aware.
Here is my one:

A few notes:
The CVertex class contains a fourth comonent called dist that stores the distance
of the point from the Plane. This is calculated in PlaneSide. So PlaneSplit can
be safely used only after PlaneSide was called for the polygon:

if( poly-->PlaneSide( plane )==SIDE_Intersect )
{
    CPolygon *frontPoly, *backPoly;
    poly->PlaneSplit( frontPoly, backPoly );
    .............
}

int CPolygon::PlaneSide( CPlane &P )
{
 vfloat d;
 bool vertexInFront=false, vertexBehind=false;
 for( int i=0; i<NumSides; i++ )
 {
  d = P.DistToVert( Verts[i] );
  if( d>EPSILON )
   vertexInFront=true;
  else
   if( d<-EPSILON )
    vertexBehind=true;
  Verts[i].dist = d;//will need it in PlanesSplit
 }
 if( vertexInFront )
 {
  if( vertexBehind )
   return SIDE_Intersect;
  else
   return SIDE_Front;
 }
 else
 {
  if( vertexBehind )
   return SIDE_Back;
  else
   return SIDE_OnPlane;
 }
}


void CPolygon::PlaneSplit( CPolygon *&FrontPoly, CPolygon *&BackPoly )
{
 int numFrontVerts=0, numBackVerts=0;
 vfloat d;
 vfloat prevd = Verts[NumSides-1].dist;
 for( int i=0; i<NumSides; i++ )
 {
  d = Verts[i].dist; //calculated in PlaneSide()
  if( myabs( d ) < EPSILON )
  {
   numBackVerts++;
   numFrontVerts++;
  }
  else
  {
   if( d < 0 )
   {
    if( prevd > EPSILON )
    {//intersection point
     numFrontVerts++;
     numBackVerts++;
    }
    numBackVerts++;
   }
   if( d > 0 )
   {
    if( prevd < -EPSILON )
    {//intersection point
     numFrontVerts++;
     numBackVerts++;
    }
    numFrontVerts++;
   }
  }
  prevd = d;
 }

 FrontPoly = new CPolygon( numFrontVerts, this );
 BackPoly = new CPolygon( numBackVerts, this );

 int backindex=0, frontindex=0;
 int previ = NumSides-1;
 prevd = Verts[previ].dist;//calculated in PlaneSide()
 for( i=0; i<NumSides; i++ )
 {
  d = Verts[i].dist;
  if( myabs( d ) < EPSILON )
  {
   FrontPoly->Verts[frontindex] = Verts[i];
   frontindex++;
   BackPoly->Verts[backindex] = Verts[i];
   backindex++;
  }
  else
  {
   if( d < 0 )
   {
    if( prevd > EPSILON )
    {//intersection point
     FrontPoly->Verts[frontindex].Interpolate( Verts[previ], Verts[i], prevd/(prevd-d) );
     BackPoly->Verts[backindex] = FrontPoly->Verts[frontindex];
     frontindex++;
     backindex++;
    }
    BackPoly->Verts[backindex] = Verts[i];
    backindex++;
   }
   if( d > 0 )
   {
    if( prevd < -EPSILON )
    {//intersection point
     FrontPoly->Verts[frontindex].Interpolate( Verts[previ], Verts[i], prevd/(prevd-d) );
     BackPoly->Verts[backindex] = FrontPoly->Verts[frontindex];
     frontindex++;
     backindex++;
    }
    FrontPoly->Verts[frontindex] = Verts[i];
    frontindex++;
   }
  }
  prevd = d;
  previ = i;
 }
}

> The result is that you can end up with non-convex polygons
> in the leaves.  These can happen in 2 major ways (
> see http://www.cbloom.com/bsp_problems.gif "):
> 
> 1. "bend-ins".  This is when you have three verts that
> are very nearly co-linear.  If the clipping had been perfect,
> they would have been colinear.  Instead, the middle one fell
> a bit to the inside of the other two, creating a very mild
> star-trek-symbol shape.  I get rid of these by finding the
> triangles that have very small areas and deleting their middle
> vertex.
> 
> 2. "fish-tails".  Take a triangle.  Duplicate one of the verts
> to make it a quad with two verts right on top of eachother.
> Take one of the duplicated verts and pull it across its twin
> so that the segments of the quad intersect.  This makes a
> segment with the wrong winding, two triangles with upside
> down normals.  This is a big crisis for a BSP, because that
> wrong-facing segment will make a plane facing the wrong way.
> Most of the time, this will be fixed by deleting the very
> short segments, but I still seem to get it once in a rare
> while.  The rest of the time, I fix it by turning the segments
> in to planes.  In my convention, proper planes will have
> all the other verts of the polygon on its front side.  Thus,
> any plane which has verts of the polygon on its back side
> is simply tossed out, and its end-points are snapped together.

The above algho should take care of these cases.

[Algorithms] Building BSPs Robustly

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

Charles Bloom writes:
 > make your BSP building robust (eg. numerically safe) ?

Snapping the original vertices to a grid of integral 
coordinates? The split vertices won't be integral, but 
you might get a better error estimate.

If you can find an upper bound on the error, could you 
shift newly created vertices by that amount along the 
normal, by default? The deeper your tree, the more such 
changes you will accumulate, but if you find a sufficently 
low upper bound maybe you can make sure that you err on 
the right side without introducing a visible error?

Minimizing splits is a good start. Maybe reject splits 
too close to existing vertices, or splits that create 
to big an error (sign?) with respect to

   d = plane.DistanceToPoint( split_vertex );

Investing cycles into a good heuristic might come cheaper 
than checking correctness?

                                       b.



Side question: if you don't use the BSP for depth sorting 
(rendering) but just for hierarchical culling and collision 
detection, do you have to split polygons (i.e. create new 
vertices) at all? With respect to point-vs.-plane tests, 
isn't your leaf is essentially just a list of planes to 
test against, so does it matter whether a plane (that can 
cover all coplanar polygons) appears in more than one leaf 
(flip sign for orientation)?

I am not sure how big the penalty for a depth buffer clear 
and a more or less unsorted z read/write pass (as opposed 
to back-to-front z fill) is these days, especially as 
moving objects approach polygon budgets larger than the 
visible part of the scene.

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

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
> 

[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] VDPM vs ROAM

[Mark D. <duc...@ll...>]

Kevin,

It depends on how much effort you put in on each.  ROAM is easier to
get going for height maps, and is theoretically faster when you completely
optimize the mesh each frame.  Hoppe describes an idea of partially
optimizing in sweeps over the output mesh, so that a complete
optimization happens over the coarse of say ten frames.  ROAM
automagically takes advantage of frame-to-frame coherence to
get the best quality in your time budget, and take time proportionate
to the number of LOD changes.  ROAM thus gives you the best possible
quality in minimum theoretical time, whereas VDPM can cause
uncontrolled errors (example: you suddenly put your nose
right on top of some interesting geometry and it takes
a full second to pop to full detail).

I'm happy to give lot's of implementation details/suggestions
to you or anyone else who wants to give ROAM a try.
There are a number of other sources of information on various
approaches to ROAM-like systems out there (Alex Pfaffe
http://ddg.sourceforge.net/, Seumas McNally
http://www.longbowdigitalarts.com/seumas/ for example,
Ben Disoe has a good page http://vterrain.org/LOD/published.html).

Kevin Lackey wrote:

> 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
>
> --
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

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

[<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

[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.