Re: [Algorithms] Current state of shadow maps?

[David W. <da...@pl...>]

Not quite sure I get this one... so you draw the same object N number of=20
times where N is the number of frustums that ultimately touched that bad=20
boy?  Or do you try and pass in N shadow maps?  I guess the second way=20
is... um... easier?  Assuming your using a shading model that supports=20
variable iteration so N can be anything up to the number of textures you=20
can use.  Of course you wouldn't need to accumulate in that case... you=20
could just test them all and any says shadow then it's shadow.

-- David


Rowan Wyborn wrote:

>Okay so the issue with any "sub divided" frustums algorithm is handling =
multiple shadow frustums from a light source that hit a single piece of g=
eometry (why large pieces of geometry need to be broken up for Tom Fs alg=
orithm).
>
>So my thinking is, why not just accumulate the result of multiple overla=
pping frustums in dest alpha, and then modulate lighting by dest alpha in=
 a separate lighting pass?
>
>Solves all those nasty border issues, and I don't think it would be noti=
ceably slower (if you are doing nice PCF filtering you are going to be sh=
ader instruction limited anyways).
>
>This provides some opportunities for real sneaky frustum subdivision whe=
n handling a given light source. You could just choose arbitrary frustums=
 to maximise the buffer resolution towards the viewpoint without worrying=
 about how they overlapped scene geometry. Would be a kind of pseudo PSM =
algorithm, without any of the nightmare projection issues :)
>
>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?
>>
>>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.
>>
>>   =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:
>>>     =20
>>>
>>>>Yep - that's the tricky part. One method is to partition
>>>>       =20
>>>>
>>>the large objects
>>>     =20
>>>
>>>>with user clip planes. Another is to simply decimate them
>>>>       =20
>>>>
>>>into smaller and
>>>     =20
>>>
>>>>smaller chunks of triangles as needed (rather expensive,
>>>>       =20
>>>>
>>>but it should only
>>>     =20
>>>
>>>>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
>>>     =20
>>>
>>>>these yet :-) There are some good papers on cube-map
>>>>       =20
>>>>
>>>shadowbuffers around
>>>     =20
>>>
>>>>though - I recall one from some nVidians.
>>>>
>>>>TomF.
>>>>
>>>>-----Original Message-----
>>>>From: gda...@li...
>>>>[mailto:gda...@li...] On
>>>>       =20
>>>>
>>>Behalf Of David
>>>     =20
>>>
>>>>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
>>>     =20
>>>
>>>>it not work for me... "The only places that do not
>>>>       =20
>>>>
>>>currently work well are
>>>     =20
>>>
>>>>large objects with lights close to or inside them."  Any
>>>>       =20
>>>>
>>>dude carrying a
>>>     =20
>>>
>>>>torch on my terrain would describe that... the terrain is a
>>>>       =20
>>>>
>>>"large object"
>>>     =20
>>>
>>>>in that sense.  Ah well.  But stencil shadows are looking
>>>>       =20
>>>>
>>>great so far!  I
>>>     =20
>>>
>>>>hope to combine them with some form of what you are doing
>>>>       =20
>>>>
>>>for a nice hybrid
>>>     =20
>>>
>>>>shadowing approach.
>>>>
>>>>-- David
>>>>
>>>>
>>>>Tom Forsyth wrote:
>>>>I've updated the description of the algorithm and included
>>>>       =20
>>>>
>>>some pictures.
>>>     =20
>>>
>>>>Hopefully it's a bit clearer, but this stuff can be tough
>>>>       =20
>>>>
>>>to explain. The
>>>     =20
>>>
>>>>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
>>>     =20
>>>
>>>>works pretty well. It's slow, but not absurdly slow,
>>>>       =20
>>>>
>>>considering what it's
>>>     =20
>>>
>>>>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
>>>     =20
>>>
>>>>many shadowbuffer texels as pixels, but in practice you
>>>>       =20
>>>>
>>>need a lot less than
>>>     =20
>>>
>>>>this, even with the horrible alpha-test shadows I'm using
>>>>       =20
>>>>
>>>here (I find that
>>>     =20
>>>
>>>>half as many texels as pixels works well). With PCF, you
>>>>       =20
>>>>
>>>can drop it a bit
>>>     =20
>>>
>>>>more, and if you put in soft-edged shadows with something
>>>>       =20
>>>>
>>>like Smoothies or
>>>     =20
>>>
>>>>Willem's smooth-shadows method
>>>>       =20
>>>>
>>>(http://www.whdeboer.com/writings.html), then
>>>     =20
>>>
>>>>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
>>>     =20
>>>
>>>>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 :-)
>>>     =20
>>>
>>>>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
>>>     =20
>>>
>>>>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
>>>     =20
>>>
>>>>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
>>>     =20
>>>
>>>>_want_ to turn it down lots! So that dramatically reduces
>>>>       =20
>>>>
>>>the fillrate
>>>     =20
>>>
>>>>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
>>>     =20
>>>
>>>>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,
>>>     =20
>>>
>>>>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,
>>>     =20
>>>
>>>>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
>>>>
>>>--
>>>-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
>>>
>>
>>-------------------------------------------------------
>>This SF.Net email is sponsored by:
>>Power Architecture Resource Center: Free content, downloads, discussion=
s,
>>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
>>
>
>
>
>-------------------------------------------------------
>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
>