RE: [Algorithms] Current state of shadow maps?

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

Well, you'd probably do in a shader & read multiple SBs instead. Then I
guess you take the minimum of all the lighting results (i.e. so if any =
of
the SBs say it's in shadow, it is). Hmmm... that should work. I seem to
recall a paper by some ATI chaps doing something like this.

I've got a nagging feeling there's a problem with this, but I can't =
remember
what it is at the moment :-(

TomF.

> -----Original Message-----
> From: gda...@li...=20
> [mailto:gda...@li...] On=20
> Behalf Of Rowan Wyborn
> Sent: 05 October 2005 02:49
> To: gda...@li...
> Subject: RE: [Algorithms] Current state of shadow maps?
>=20
>=20
> Okay so the issue with any "sub divided" frustums algorithm=20
> is handling multiple shadow frustums from a light source that=20
> hit a single piece of geometry (why large pieces of geometry=20
> need to be broken up for Tom Fs algorithm).
>=20
> So my thinking is, why not just accumulate the result of=20
> multiple overlapping frustums in dest alpha, and then=20
> modulate lighting by dest alpha in a separate lighting pass?
>=20
> Solves all those nasty border issues, and I don't think it=20
> would be noticeably slower (if you are doing nice PCF=20
> filtering you are going to be shader instruction limited anyways).
>=20
> This provides some opportunities for real sneaky frustum=20
> subdivision when handling a given light source. You could=20
> just choose arbitrary frustums to maximise the buffer=20
> resolution towards the viewpoint without worrying about how=20
> they overlapped scene geometry. Would be a kind of pseudo PSM=20
> algorithm, without any of the nightmare projection issues :)
>=20
> rowan
>=20
> > -----Original Message-----
> > From: Tom Forsyth [mailto:tom...@ee...]
> > Sent: Wednesday, 5 October 2005 3:18 PM
> > To: gda...@li...
> > Subject: RE: [Algorithms] Current state of shadow maps?
> >=20
> > It's a variant - concentrating texels where they're needed=20
> most. But it
> > still requires cube-map hardware. And if you require that,=20
> then life is
> > simple.
> >=20
> > TomF.
> >=20
> > > -----Original Message-----
> > > From: gda...@li...
> > > [mailto:gda...@li...] On
> > > Behalf Of Megan Fox
> > > Sent: 04 October 2005 12:19
> > > To: gda...@li...
> > > Subject: Re: [Algorithms] Current state of shadow maps?
> > >
> > >
> > > I wonder - have you seen this? -
> > > =
http://www.gamedev.net/community/forums/topic.asp?topic_id=3D346786
> > >
> > > Seems this approach might be applied to your problem with
> > > great success.
> > >
> > > On 10/4/05, Tom Forsyth <tom...@ee...> wrote:
> > > > Yep - that's the tricky part. One method is to partition
> > > the large objects
> > > > with user clip planes. Another is to simply decimate them
> > > into smaller and
> > > > smaller chunks of triangles as needed (rather expensive,
> > > but it should only
> > > > happen to a few objects - hopefully!). Another is to=20
> use cube-map
> > > > shadowbuffers, if hardware is available. But I haven't
> > > actually tried any of
> > > > these yet :-) There are some good papers on cube-map
> > > shadowbuffers around
> > > > though - I recall one from some nVidians.
> > > >
> > > > TomF.
> > > >
> > > > -----Original Message-----
> > > > From: gda...@li...
> > > > [mailto:gda...@li...] On
> > > 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
> > > limitation that makes
> > > > it not work for me... "The only places that do not
> > > currently work well are
> > > > large objects with lights close to or inside them."  Any
> > > dude carrying a
> > > > torch on my terrain would describe that... the terrain is a
> > > "large object"
> > > > in that sense.  Ah well.  But stencil shadows are looking
> > > great so far!  I
> > > > hope to combine them with some form of what you are doing
> > > for a nice hybrid
> > > > shadowing approach.
> > > >
> > > > -- David
> > > >
> > > >
> > > > Tom Forsyth wrote:
> > > > I've updated the description of the algorithm and included
> > > some pictures.
> > > > Hopefully it's a bit clearer, but this stuff can be tough
> > > 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
> > > person's head. It
> > > > works pretty well. It's slow, but not absurdly slow,
> > > considering what it's
> > > > doing! I'll try to take some pics some time - it looks=20
> pretty goofy.
> > > >
> > > > You're right that to get "perfect" precision you need to
> > > render twice as
> > > > many shadowbuffer texels as pixels, but in practice you
> > > need a lot less than
> > > > this, even with the horrible alpha-test shadows I'm using
> > > here (I find that
> > > > half as many texels as pixels works well). With PCF, you
> > > can drop it a bit
> > > > more, and if you put in soft-edged shadows with something
> > > like Smoothies or
> > > > Willem's smooth-shadows method
> > > (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=20
> 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
> > > 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=20
> 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
> > > 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
> > > 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=20
> 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
> > > 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
> > > shader, you
> > > > _want_ to turn it down lots! So that dramatically reduces
> > > the fillrate
> > > > required for shadowbuffers.
> > > >
> > > > The second is that you can render a single receiver=20
> 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
> > > 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=20
> 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=20
> 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 -=20
> mind, both would
> > > > probably keel over and die in a slurry of render passes=20
> (and in both
> > > > cases, you'd probably enable your "oh god we're in trouble start
> > > > merging nearby lights into single lights" optimization=20
> code), but it
> > > > seems like neither does terribly well.
> > > >
> > > >
> > > > I'd thought the "big" win scenario for stencil over=20
> buffers was more
> > > > scenes with few occluders and many recievers (that is,=20
> 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=20
> 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=20
> 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=20
> 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,
> > > 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,
> > > 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
> > > >
> > >
> > >
> > > --
> > > -Megan Fox
> > > Lead Developer, Elium Project
> > > http://www.elium.tk
> > >
> > >
> > > -------------------------------------------------------
> > > This SF.Net email is sponsored by:
> > > Power Architecture Resource Center: Free content, 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
> >=20
> > -------------------------------------------------------
> > 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
>=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