RE: [Algorithms] Current state of shadow maps?

[Tom F. <tom...@ee...>]

It's a variant - concentrating texels where they're needed most. But it
still requires cube-map hardware. And if you require that, then life is
simple.

TomF.

> -----Original Message-----
> From: gda...@li...=20
> [mailto:gda...@li...] On=20
> Behalf Of Megan Fox
> Sent: 04 October 2005 12:19
> To: gda...@li...
> Subject: Re: [Algorithms] Current state of shadow maps?
>=20
>=20
> I wonder - have you seen this? -
> http://www.gamedev.net/community/forums/topic.asp?topic_id=3D346786
>=20
> Seems this approach might be applied to your problem with=20
> great success.
>=20
> On 10/4/05, Tom Forsyth <tom...@ee...> wrote:
> > Yep - that's the tricky part. One method is to partition=20
> the large objects
> > with user clip planes. Another is to simply decimate them=20
> into smaller and
> > smaller chunks of triangles as needed (rather expensive,=20
> but it should only
> > happen to a few objects - hopefully!). Another is to use cube-map
> > shadowbuffers, if hardware is available. But I haven't=20
> actually tried any of
> > these yet :-) There are some good papers on cube-map=20
> shadowbuffers around
> > though - I recall one from some nVidians.
> >
> > TomF.
> >
> > -----Original Message-----
> > From: gda...@li...
> > [mailto:gda...@li...] On=20
> Behalf Of David
> > Whatley
> > Sent: 03 October 2005 23:30
> > To: gda...@li...
> > Subject: Re: [Algorithms] Current state of shadow maps?
> >
> >
> > Tom,
> >
> > That stuff is great!  Just wish it didn't have the one=20
> limitation that makes
> > it not work for me... "The only places that do not=20
> currently work well are
> > large objects with lights close to or inside them."  Any=20
> dude carrying a
> > torch on my terrain would describe that... the terrain is a=20
> "large object"
> > in that sense.  Ah well.  But stencil shadows are looking=20
> great so far!  I
> > hope to combine them with some form of what you are doing=20
> for a nice hybrid
> > shadowing approach.
> >
> > -- David
> >
> >
> > Tom Forsyth wrote:
> > I've updated the description of the algorithm and included=20
> some pictures.
> > Hopefully it's a bit clearer, but this stuff can be tough=20
> to explain. The
> > odd toroidal topology of StarTopia doesn't help :-)
> >
> > http://www.eelpi.gotdns.org/papers/shadowbuffer_pseudocode.html
> >
> >
> > The army-with-lots-of-short-range-torches example is an
> >
> > interesting one for
> >
> > shadowbuffers.
> >
> > Just include it in your demo *g*
> >
> >
> > I did this - just hacked in a light floating above every=20
> person's head. It
> > works pretty well. It's slow, but not absurdly slow,=20
> considering what it's
> > doing! I'll try to take some pics some time - it looks pretty goofy.
> >
> > You're right that to get "perfect" precision you need to=20
> render twice as
> > many shadowbuffer texels as pixels, but in practice you=20
> need a lot less than
> > this, even with the horrible alpha-test shadows I'm using=20
> here (I find that
> > half as many texels as pixels works well). With PCF, you=20
> can drop it a bit
> > more, and if you put in soft-edged shadows with something=20
> like Smoothies or
> > Willem's smooth-shadows method=20
> (http://www.whdeboer.com/writings.html), then
> > you need even fewer texels.
> >
> > TomF.
> >
> >
> >
> > From: Christian Sch=FCler
> >
> >
> > Creating a lot of frustrums, but not necessarily 1 per reciever per
> > light - it's very likely you could merge quite a few of those
> > frustrums together, given an army is usually walking in close
> > formation
> >
> > That'd be lossy compression then ... but this opportunity to
> > short-cut is not restricted to shadowbuffers, is applies to
> > stencil too (Each unique "frustum" translates to an extrusion
> > center). Besides I can see the danger of popping if the
> > merger is inconsitent between frames.
> >
> >
> > The army-with-lots-of-short-range-torches example is an
> >
> > interesting one for
> >
> > shadowbuffers.
> >
> > Just include it in your demo *g*
> >
> >
> >
> > Here's some really really rough back-of-the-envelope
> >
> > figures to compare the
> >
> > two. Warning - lots of assumptions ahead!
> >
> > I don't want to start a war. I just would not equate the
> > overall performance to the # of Z reads/writes.
> > I have experience with the "army of torches" scenario with
> > stencils, and you can get decent performance if the average
> > screen space area was just small enough.
> > So there is little cost associated "per light" and large
> > costs for "screen space covered" and "vertices touched". In
> > the dynamic environment where all the recievers / casters
> > were moving, guess the limiting factor for the CPU work was
> > (for me) ---> the scene database queries to just get the
> > objects for each light! With shadow buffers I can see
> > shifting the cost more towards per light while per pixel and
> > per vertex costs may be smaller, with added penalties of
> > constant costs, like this:
> >
> >
> > stencil:
> > n lights =3D n passes
> > where n being the # of scene database queries
> >
> > shadow buffers
> > n lights =3D 2 * n passes (minimum) + n / c * ( render target
> > switches + stall penalty for leaving the framebuffer / coming
> > back to the framebuffer, etc etc)
> > where c being how much buffers you can pack into a=20
> shadowbuffer atlas
> >
> >
> > My experience also says that in order to over a 100^2 pixel
> > screen area, you need a 200^2 shadow buffer, because on
> > average the projected texels are stretched out due to the
> > light hitting at grazing angles. A 1024'er screen would need
> > a 2048'er shadow map. But that's a minor issue.
> >
> >
> > -----Original Message-----
> > From: gda...@li...
> > [mailto:gda...@li...] On
> > Behalf Of Tom Forsyth
> > Sent: Friday, September 09, 2005 7:38 AM
> > To: gda...@li...
> > Subject: RE: [Algorithms] Current state of shadow maps?
> >
> >
> > Interestingly:
> >
> >
> > Stencil volumes win the indoor/urban, night scenarios
> > (think doom3, or neverwinter nights for the record)
> > - shadows from vegetation can be neglected.
> > - many omnidirectional light sources, or lightsources with
> > large frustra, for which shadowbuffer is unoptimal (too many render
> >
> > targets)
> >
> > - most light sources have small screen space extent
> > and world extent, so stencil is not expensive
> >
> > ...actually describes your average StarTopia scene=20
> moderately well :-)
> > http://www.eelpi.gotdns.org/startopia/startopia_pictures.html
> >
> > (yes, I will get the demo version done soon, I promise!)
> >
> >
> >
> > The army-with-lots-of-short-range-torches example is an
> > interesting one for
> > shadowbuffers. When the range of a light is small compared=20
> to the view
> > frustum (as will be the case with >90% of the torches), then
> > my scheme will
> > just reduce to essentially a cube map per light. Actually, it
> > gets slightly
> > better - if there's nothing above the torch in range of it
> > (likely), then
> > that face never gets created, and also the face view angles
> > can be opened up
> > to about 120 degrees and still remain efficient - this
> > typically means you
> > lose another face and only need four frustums per light
> > rather a cube-map's
> > six.
> >
> >
> > Here's some really really rough back-of-the-envelope figures
> > to compare the
> > two. Warning - lots of assumptions ahead!
> >
> > Assume the shadowbuffers are the type that only write to a Z/stencil
> > surface, not a colour buffer as well. Remember that my scheme
> > allocates
> > shadowbuffer texels so that you get 1 texel per screen pixel
> > for the area it
> > covers, if you turn the detail to "max", i.e. pixel-perfect.
> >
> > Let's also assume that each light's radius sphere covers=20
> 10k pixels (a
> > 100x100 pixel area - not unreasonable). Also approximate the
> > shadowbuffer
> > coverage - in practice many pixels in that area won't have
> > receivers, and
> > many others will have multiple receivers. Let's call it even
> > for the sake of
> > argument. Also assume that in any rendering pass, all the
> > pixels get tested,
> > and half get rejected because of overdraw (an entire scene
> > will have more
> > overdraw, but my experience is that shadowbuffer/volume
> > shadows, because of
> > their limited range, get lower overdraw, and 2x is reasonable).
> >
> > Shadowbuffers:
> >
> > Per light, rendering shadowbuffers: 10,000 Z tests + 5,000 Z
> > writes =3D 15k
> > reads/writes.
> >
> > Per light, rendering actual scene: 10,000 shadowbuffer reads.
> >
> > Total =3D 25k reads/writes.
> >
> >
> > Volume shadows:
> >
> > Per light, rendering volumes (remembering that volumes have
> > two sides!):
> > 2*10,000 Z tests + 2*5,000 Z writes =3D 30k reads/writes.
> >
> > Per light, rendering actual scene: the stencil tests come
> > free with the Z
> > reads. No extra cost.
> >
> > Total =3D 30k reads/writes.
> >
> >
> > So in terms of fillrate, it's pretty close - shadowbuffering
> > slightly ahead,
> > but I made a lot of assumptions. But shadowbuffering has some
> > big aces up
> > its sleeve:
> >
> > The first is that I said the quality slider was on "best" -
> > one texel per
> > screen pixel. But you can turn that down - you can easily
> > halve it without
> > any quality loss. In fact, if you have a soft-edged shadow=20
> shader, you
> > _want_ to turn it down lots! So that dramatically reduces=20
> the fillrate
> > required for shadowbuffers.
> >
> > The second is that you can render a single receiver with multiple
> > shadowbuffers in one pass - because you're just sampling a
> > texture and doing
> > a comparison. So you can do more than one of these per
> > shader. Let's say you
> > can do two - that's totally realistic for PS2.0 hardware. So
> > you've now
> > halved the number of passes you do when rendering the scene
> > (I didn't list
> > those reads/writes in the above). This can't be done with
> > volume shadows
> > (that I know of) - it can only reject the pixel or accept=20
> it, it can't
> > half-shade it. That's a huge win!
> >
> >
> > Also, the process of extruding volume shadows is far more
> > expensive than the
> > equivalent shadowbuffer thing, which is just rendering the
> > object from a
> > different POV. I believe most people using VS-driven
> > extrusion find that
> > they are frequently limited by triangle throughput rather
> > than fillrate. And
> > people using CPU-driven extrusion wish they were doing
> > VS-driven extrusion
> > :-)
> >
> >
> >
> > TomF.
> >
> >
> >
> >
> > -----Original Message-----
> > From: gda...@li...
> > [mailto:gda...@li...] On
> > Behalf Of Megan Fox
> > Sent: 08 September 2005 13:07
> > To: gda...@li...
> > Subject: Re: [Algorithms] Current state of shadow maps?
> >
> >
> > Well, let's take the army with torches but apply stencil shadows
> > instead (and let's say they're on a field of battle, a heightmap) -
> > how is that still not a nightmare scenario?
> >
> > With shadow buffers (using Tom's method), you'd end up:
> >
> > - Creating a lot of frustrums, but not necessarily 1 per
> >
> > reciever per
> >
> > light - it's very likely you could merge quite a few of those
> > frustrums together, given an army is usually walking in close
> > formation
> >
> > With stencil, you'd end up:
> >
> > - Casting your extrusions back for every light/occluder pair.  You
> > can't really merge (I don't think?), so that's "it."
> >
> >
> > Especially after using Tom's handy-dandy frustum
> >
> > merge-o-matic method,
> >
> > it seems like the two methods would be comperable - mind, both would
> > probably keel over and die in a slurry of render passes (and in both
> > cases, you'd probably enable your "oh god we're in trouble start
> > merging nearby lights into single lights" optimization code), but it
> > seems like neither does terribly well.
> >
> >
> > I'd thought the "big" win scenario for stencil over buffers was more
> > scenes with few occluders and many recievers (that is, your average
> > FPS environment)?
> >
> >
> > Stencil volumes win the indoor/urban, night scenarios
> >
> > (think doom3, or neverwinter nights for the record)
> >
> > - shadows from vegetation can be neglected.
> > - many omnidirectional light sources, or lightsources with
> >
> > large frustra, for which shadowbuffer is unoptimal (too many
> > render targets)
> >
> > - most light sources have small screen space extent and
> >
> > world extent, so stencil is not expensive
> >
> > However shadowbuffers have other qualities that make them
> >
> > attractive (image based, soft edges), so it would be
> > desireable to use them for all purposes. It's just a pity
> > that they are so unfeasible for omni lights (I imagine an
> > army with torches here ...).
> >
> >
> > -------------------------------------------------------
> > SF.Net email is Sponsored by the Better Software Conference & EXPO
> > September 19-22, 2005 * San Francisco, CA * Development
> > Lifecycle Practices
> > Agile & Plan-Driven Development * Managing Projects & Teams *
> > Testing & QA
> > Security * Process Improvement & Measurement *
> > http://www.sqe.com/bsce5sf
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > Archives:
> > http://sourceforge.net/mailarchive/forum.php?forum_ida88
> >
> >
> >
> > -------------------------------------------------------
> > SF.Net email is Sponsored by the Better Software Conference & EXPO
> > September 19-22, 2005 * San Francisco, CA * Development
> > Lifecycle Practices
> > Agile & Plan-Driven Development * Managing Projects & Teams *
> > Testing & QA
> > Security * Process Improvement & Measurement *
> > http://www.sqe.com/bsce5sf
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > Archives:
> > http://sourceforge.net/mailarchive/forum.php?forum_ida88
> >
> >
> > -------------------------------------------------------
> > SF.Net email is Sponsored by the Better Software Conference & EXPO
> > September 19-22, 2005 * San Francisco, CA * Development
> > Lifecycle Practices
> > Agile & Plan-Driven Development * Managing Projects & Teams *
> > Testing & QA
> > Security * Process Improvement & Measurement *
> > http://www.sqe.com/bsce5sf
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > Archives:
> > http://sourceforge.net/mailarchive/forum.php?forum_ida88
> >
> >
> >
> >
> >
> > -------------------------------------------------------
> > This SF.Net email is sponsored by:
> > Power Architecture Resource Center: Free content,=20
> downloads, discussions,
> > and more. http://solutions.newsforge.com/ibmarch.tmpl
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > Archives:
> > http://sourceforge.net/mailarchive/forum.php?forum_ida88
> >
> >
> >
> >
> > -------------------------------------------------------
> > This SF.Net email is sponsored by:
> > Power Architecture Resource Center: Free content,=20
> downloads, discussions,
> > and more. http://solutions.newsforge.com/ibmarch.tmpl
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > Archives:
> > http://sourceforge.net/mailarchive/forum.php?forum_ida88
> >
>=20
>=20
> --
> -Megan Fox
> Lead Developer, Elium Project
> http://www.elium.tk
>=20
>=20
> -------------------------------------------------------
> This SF.Net email is sponsored by:
> Power Architecture Resource Center: Free content, downloads,=20
> discussions,
> and more. http://solutions.newsforge.com/ibmarch.tmpl
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_ida88
>=20