[Algorithms] LOD terrain and occlusion culling

[Alex P. <res...@gt...>]

Huh, something like that should work?

I too am keeping min/max values for terrain blocks and the entire bintree
below it, well the
top N levels anyhow.  I was planning to use this for hierarchical occlusion
culling.
Why doesn't your idea work?
You basically need to test if one block obscures another, you should be able
to project the 4 corners of the maximum height of a distant block D (in my
case 3 corners
of a bintree element) to the screen, and then do the same for the occluding
block's O
minimum height and then run the following test
if (  max(Dy) < min(Oy) and min(Dx) > min(Ox) and max(Dx) < max(Ox))
 D is occluded by O.

Something I was thinking of is how to determine occluder candidates.
This would probably best be done in a precompute stage.
My idea was to store a list of precomputed good occluders,
basically a list of bintree indexes per block.  Then for the nearby blocks I
could
test each distant block against these good occluders.
I wonder if it would also be useful to include a list good occludees,
probably
not.
The other reason I would like to use this for is culling non terrain like
buildings
behind a hill. To this you might have to adjust the max terrain height for
the
max height of the items on the terrain.

However, occlusion becomes useles if the character can climb a really high
mountain or fly, that is one of the reasons I haven't started on that
project
yet.

If you kept the min/max data down to the leaf nodes you could probably
also do some semi-realtime lighting calculations to create lightmaps
which allow for self shadowing terrain, you would have to spread that
calculation over several frames, but given that the sun generally moves
slowly
(and its shadows) you could afford to do it incrementally perhaps taking a
minute per increment.  Additionally you could do it only in the
vicinity of the viewer.  Also I was wondering if it would be possible to
take the advantage of the day/night border somehow only re-calculate
Along that edge, the problem is when the sun nearly goes down/up
huge areas can light up/go dark, also how would you spawn new unattached
shadows or light areas, perhaps they can get tied to the local maxima on the
terrain. Those good occluders are also the biggest shadow casters, anyhow
I am rambling...

Alex Pfaffe

----- Original Message -----
From: "Klaus Hartmann" <k_h...@os...>
To: <gda...@li...>
Sent: Tuesday, February 27, 2001 10:21 AM
Subject: Re: [Algorithms] LOD terrain


> Never mind... this visibility test won't work, because the maximum
elevation
> of the current block will always be greater than or equal to the minimum
> elevation of the previous block.
>
> Niki
>
> ----- Original Message -----
> From: Klaus Hartmann <k_h...@os...>
> To: <gda...@li...>
> Sent: Tuesday, February 27, 2001 7:16 PM
> Subject: Re: [Algorithms] LOD terrain
>
>
> > Thanks a lot to all who replied :-) I think I'll have a look into TINs
and
> > RTINs.
> >
> > I, too, was thinking about block-to-block visibility. The solution I was
> > thinking about is to cast rays into the scene (using Musgrave's
> grid-tracing
> > algorithm). Of course, there'll be the problem that Tom Forsyth already
> > pointed out: "The problem with tracing rays is that there can be a
valley
> > that shows your node, but still blocks all the raytraces to its
vertices."
> >
> > So what I'll try to do is the following (and I have no idea if this is
> going
> > to work or if it is any good):
> >
> > The grid-tracing algorithm traverses a grid block-by-block. Therefore,
you
> > always know the last block through wich the ray passed. Also, assuming
> that
> > you know the minimum and maximum elevation of each block, you should be
> able
> > to do a coarse visibility test like so:
> >
> > Perform the following test for the 'four corners' of the current block:
> > "Does the ray pass above the maximum elevation of the current block, AND
> > does the ray pass below the minimum elevation of the previous block?".
If
> > this is true for all four corners of a block,  then the block should be
> > invsibile.
> >
> > Do you think that this'll work? It would be nice if it did, because
> > hierarchical grid-tracing can be very fast.
> >
> > Niki
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list