Re: [Algorithms] General-purpose shadowbuffer implementation.

[Jonathan B. <jo...@nu...>]

Tom Forsyth wrote:

>It's a problem if your chunks are too big to fit in a single SB frustum.=
 I think this is why Jon doesn't keep using smaller and smaller shadow bu=
ffers as he gets closer to the viewer - his smallest SB is easily big eno=
ugh to hold the largest object.
>
> =20
>

Yeah, in mine, an object doesn't actually have to fit into one shadow=20
map, but it has to fit into two.  So my smallest SB is not actually big=20
enough to hold the largest object, but my next biggest one is (and must=20
be, for things to work right).=20

I don't have a separate light/shadow-drawing pass (as one might have in=20
an engine with many light sources simultaneously), so I am fitting the=20
shadow evaluation into the same shader program as all the other lighting=20
stuff for an object.  Right now I only have hardware for 8 textures at=20
once, and no dynamic branches.  So I have two shadow textures, sample=20
them both (single sample right now), and throw one of the samples away.

On the eventual target platform (which will be the best card I can buy=20
around late November), I'll have dynamic branching and hopefully more=20
texture slots (newer cards go over 8 right?).  So probably, I will have=20
3 textures loaded at once, and use a dynamic branch to determine which=20
one to multisample.

[I had been sweeping the dynamic branch idea under the rug because I've=20
heard so many horror stories about how slow it is.  But nvidia has this=20
paper recommending doing it instead of sampling a texture a bunch of=20
times, so I figure hey, why not.]

Given all this, I will probably add one more resolution for stuff=20
reeeeally close to the viewer, which will help take care of surface acne=20
stuff on human-sized characters.

  -J.


>There's two cases here - casters and receivers. Usually objects are both=
, but it's good to think of them is two separate phases.
>
>Rendering casters is easy. You can render any casters to any SB frustum.=
 Worst that happens is it gets clipped off the edge and you wasted some g=
eometry (so hey - you need better culling). But that object casts perfect=
 shadows into that frustum. So there's no problems with objects that cast=
 really long or large shadows that cross multiple SBs - you just render t=
hem each to every SB they intersect, and it all works.
>
>So the problem comes if you want to render a shadow receiver with more t=
han one SB, because you can't make a single SB to fit it. This doesn't ac=
tually happen all that much because I deliberately choose my SBs so that =
they include big objects first, then try ot fit the smaller ones in aroun=
d it. So you don't choose your frustums than worry about fitting objects =
into them (like saying "I use a cubemap"), you choose your frustums so th=
at objects fit into them.
>
>
>When this does happen, the easiest solution I can think of is to chop th=
e object up with user clip planes and put each chunk into its own SB. Ano=
ther version would be to pre-chop (offline) the object into half, then ea=
ch part into half again, etc - and at runtime you keep doing this until o=
ne part does fit into an SB. But I haven't actually tried either of these=
 because for StarTopia (a) retrofitting this would be pretty evil and (b)=
 it's so rare that you can usually just not shadow the object and it look=
s fine.
>
>
>TomF.
>
>
> =20
>
>>-----Original Message-----
>>From: gda...@li...=20
>>[mailto:gda...@li...] On=20
>>Behalf Of Greg Hjelstrom
>>Sent: 28 August 2004 08:32
>>To: Tom Forsyth
>>Subject: Re[2]: [Algorithms] General-purpose shadowbuffer=20
>>implementation.
>>
>>
>>How do you guys handle the case where objects overlap the boundary
>>between multiple shadow buffers?  For example in Tom's GDC demo he
>>had chunks of the "terrain" mesh affected by separate shadow
>>maps meaning that arbitrarily changing chunks of terrain have to be
>>drawn separately.  This seems like a fairly big problem to me but
>>maybe I'm missing a simple solution?
>>
>>Greg Hjelstrom
>>
>>
>>Friday, August 27, 2004, 10:10:56 PM, you wrote:
>>
>>   =20
>>
>>>>This is exactly the problem with PSMs and TSMs: Depending on=20
>>>>where you=20
>>>>point the camera, they are often no better than standard=20
>>>>shadow maps. =20
>>>>So if I have to deal with making my scene look good in this=20
>>>>case, and I=20
>>>>succeed, then I might as well throw away all the PSM and TSM stuff.
>>>>       =20
>>>>
>>TF> Hurrah! Jon joins me in the place of nirvana! Well, not=20
>>quite, but it's the
>>TF> revelation that "none of this single-buffer crap is going to solve
>>TF> everything" that frees you from the stupid mathematical=20
>>distractions of
>>TF> thinking about obscure projections and concentrates the=20
>>mind on solving the
>>TF> _actual_ problem, which is how to allocate multiple shadowbuffer.
>>
>>TF> I do think PSM/TSM methods are useful, but they're tweaks=20
>>and optimisations
>>TF> to whatever higher-level method you use to solve the=20
>>multi-frustum problem.
>>TF> Maybe you can get a bit more performance in the average=20
>>case (and if you
>>TF> have lots of lights, the non-average case is only going=20
>>to happen to one of
>>TF> them at a time, so it's certainly worthwhile). They're=20
>>not, in themselves, a
>>TF> solution.
>>
>>TF> I still don't have a robust solution to the problem of=20
>>the changing frustums
>>TF> causing jitter. The "persistent" case I presented at GDC=20
>>does a lot to help
>>TF> it, but it's not a 100% solution. Because I've only done=20
>>it in cheesy demo
>>TF> apps, I'm still not sure what percentage of cases it lets=20
>>jitter through. So
>>TF> it's the one big problem I have left (but then again,=20
>>every other technique
>>TF> has it too, so I don't feel all that bad :-)
>>
>>TF> Must write my algo up...
>>
>>TF> TomF.
>>
>>
>>   =20
>>
>>>>-----Original Message-----
>>>>From: gda...@li...=20
>>>>[mailto:gda...@li...] On=20
>>>>Behalf Of Jonathan Blow
>>>>Sent: 27 August 2004 12:00
>>>>To: gda...@li...
>>>>Subject: Re: [Algorithms] General-purpose shadowbuffer=20
>>>>       =20
>>>>
>>implementation.
>>   =20
>>
>>>>This is exactly the problem with PSMs and TSMs: Depending on=20
>>>>where you=20
>>>>point the camera, they are often no better than standard=20
>>>>shadow maps. =20
>>>>So if I have to deal with making my scene look good in this=20
>>>>case, and I=20
>>>>succeed, then I might as well throw away all the PSM and TSM stuff.
>>>>
>>>>In fact it often makes the scene look a lot uglier, as the=20
>>>>       =20
>>>>
>>resolution=20
>>   =20
>>
>>>>jitters around while the camera rotates.  It just doesn't=20
>>>>       =20
>>>>
>>feel solid.
>>   =20
>>
>>>>I guess PSM and TSM might have good uses in batch=20
>>>>       =20
>>>>
>>rendering where you=20
>>   =20
>>
>>>>are splatting zillions of shadow maps per frame at real high=20
>>>>resolution=20
>>>>and you can do this kind of case by case thing and it doesn't=20
>>>>matter. =20
>>>>But I just don't see them as being useful for a real-time=20
>>>>       =20
>>>>
>>game that=20
>>   =20
>>
>>>>wants high-quality shadows, not any time soon, anyway.
>>>>
>>>>(Though if there's a demo out there that uses these kind of=20
>>>>systems that=20
>>>>solves the real-world problems that happen in a game, I'd=20
>>>>       =20
>>>>
>>be eager to=20
>>   =20
>>
>>>>see it.  And I'd buy the author a beer -- I sure as hell=20
>>>>       =20
>>>>
>>could never=20
>>   =20
>>
>>>>make PSM or TSM look good, and I tried a lot.)
>>>>
>>>>  -Jonathan.
>>>>
>>>>
>>>>Gary King wrote:
>>>>
>>>>       =20
>>>>
>>>>>I've nearly finished implementing a minor variation on TSMs=20
>>>>>         =20
>>>>>
>>>>in my PSM demo (I still need to implement a=20
>>>>dynamically-computed focus region; however, I've been able to=20
>>>>manually adapt the focus region to generate nice shadows=20
>>>>everywhere I've tried).
>>>>       =20
>>>>
>>>>>Like LSPSMs, the only degeneracy is an easily-handled=20
>>>>>         =20
>>>>>
>>>>uninteresting case (squeezing >N% of the frustum below the=20
>>>>"N% line"), which makes nicer than PSMs in that regard.
>>>>       =20
>>>>
>>>>>A huge view frustum isn't really a problem for TSMs; no more=20
>>>>>         =20
>>>>>
>>>>so than uniform shadow maps, anyway.  The worst-case behavior=20
>>>>for TSMs is when the view frustum(/trapezoid) is fat; in this=20
>>>>case, the best behavior is to fall back toward uniform shadow=20
>>>>maps (set the 80/20 split to 80/20).
>>>>       =20
>>>>
>>>>>As far as the PSM quality in the video; it's been my=20
>>>>>         =20
>>>>>
>>>>experience that PSMs (especially Stamminger & Drettakis PSMs,=20
>>>>as opposed to LSPSMs or Kozlov PSMs) can get into a number of=20
>>>>situations where they look significantly worse than uniform=20
>>>>shadow maps; particularly in large scenes with rough bounding=20
>>>>box approximations.  In these cases, the post-projective view=20
>>>>box could have significant wastage (unnecessary bits of the=20
>>>>scene), and when the light is close to the view-box the large=20
>>>>FoV causes quite a bit of compression even close to the=20
>>>>viewer.  This was the primary reason why my demo forces a=20
>>>>minimum distance between the infinity plane and the view-box.
>>>>       =20
>>>>
>>>>>-----Original Message-----
>>>>>From: gda...@li...
>>>>>[mailto:gda...@li...]On=20
>>>>>         =20
>>>>>
>>>>Behalf Of Tom
>>>>       =20
>>>>
>>>>>Forsyth
>>>>>Sent: Friday, August 27, 2004 2:13 AM
>>>>>To: gda...@li...
>>>>>Subject: RE: [Algorithms] General-purpose shadowbuffer=20
>>>>>         =20
>>>>>
>>>>implementation.
>>>>       =20
>>>>
>>>>>Goodnes - loads of emails off-list, none on-list. Come on=20
>>>>>         =20
>>>>>
>>>>people - don't be
>>>>       =20
>>>>
>>>>>shy!
>>>>>
>>>>>Anyway, due to popular demand I will do a wbe page or a post=20
>>>>>         =20
>>>>>
>>>>about the
>>>>       =20
>>>>
>>>>>implementation details.
>>>>>
>>>>>
>>>>>
>>>>>So I was reading the Trapezoidal Shadow Map paper that=20
>>>>>         =20
>>>>>
>>>>everyone was talking
>>>>       =20
>>>>
>>>>>about ages ago. http://www.comp.nus.edu.sg/~tants/tsm.html =20
>>>>>         =20
>>>>>
>>>>Yeah, I'm slow.
>>>>       =20
>>>>
>>>>>It's interesting reading - it's basically a smarter version=20
>>>>>         =20
>>>>>
>>>>of PSM from what
>>>>       =20
>>>>
>>>>>I can see - selecting a better warping for the shadowmap=20
>>>>>         =20
>>>>>
>>>>that minimises
>>>>       =20
>>>>
>>>>>texel wastage. They take the camera frustum and draw it in=20
>>>>>         =20
>>>>>
>>>>the light's space
>>>>       =20
>>>>
>>>>>(clipping as necessary). Then they approximate that with a=20
>>>>>         =20
>>>>>
>>>>trapezoid. And
>>>>       =20
>>>>
>>>>>then they find a 4x4 projection matrix that maps that to the=20
>>>>>         =20
>>>>>
>>>>unit square.
>>>>       =20
>>>>
>>>>>And that's your shadowbuffer projection.
>>>>>
>>>>>So by definition it doesn't have the divide-by-zero problems=20
>>>>>         =20
>>>>>
>>>>that PSMs have
>>>>       =20
>>>>
>>>>>because all your thinking is done in the light's frustum,=20
>>>>>         =20
>>>>>
>>>>and by definition
>>>>       =20
>>>>
>>>>>if something is outside the light's frustum, it's not lit=20
>>>>>         =20
>>>>>
>>>>anyway and so
>>>>       =20
>>>>
>>>>>can't be shadowed or cast shadows. So that solves that.
>>>>>
>>>>>It's also nice that it's continuous - a small movement of=20
>>>>>         =20
>>>>>
>>>>light, camera or
>>>>       =20
>>>>
>>>>>objects doesn't cause a large change in the trapezoidal=20
>>>>>         =20
>>>>>
>>>>approximation, and
>>>>       =20
>>>>
>>>>>therefore the mapping always changes smoothly, which solves=20
>>>>>         =20
>>>>>
>>>>some of the
>>>>       =20
>>>>
>>>>>abrupt popping of most shadowbuffer methods. (actually,=20
>>>>>         =20
>>>>>
>>objects are
>>   =20
>>
>>>>>irrelevant, unlike PSM, because TSM doesn't consider them at=20
>>>>>         =20
>>>>>
>>>>all - just
>>>>       =20
>>>>
>>>>>camera frustum and light).
>>>>>
>>>>>(The paper also has some interesting (but orthogonal)=20
>>>>>         =20
>>>>>
>>>>comments about picking
>>>>       =20
>>>>
>>>>>a depth epsilon to try to reduce surface acne and=20
>>>>>         =20
>>>>>
>>>>peterpanning, and how a
>>>>       =20
>>>>
>>>>>trapezoidal projection makes this a lot worse and how to=20
>>>>>         =20
>>>>>
>>>>make it not so bad
>>>>       =20
>>>>
>>>>>by de-projecting the epsilon in the shader. But I'm an=20
>>>>>         =20
>>>>>
>>>>ID/priority fanboy,
>>>>       =20
>>>>
>>>>>so I just skimmed that bit)
>>>>>
>>>>>So it's all great for distant lights and shortish view=20
>>>>>         =20
>>>>>
>>>>distances. But it
>>>>       =20
>>>>
>>>>>seems like there's a pretty glaring hole in the algorithm.=20
>>>>>         =20
>>>>>
>>>>If your view is
>>>>       =20
>>>>
>>>>>any decent distance compared to the light, and the light is=20
>>>>>         =20
>>>>>
>>>>not a nice
>>>>       =20
>>>>
>>>>>narrow-cone spotlight (so you can just clip off the large=20
>>>>>         =20
>>>>>
>>>>bits of the view
>>>>       =20
>>>>
>>>>>frustum), then your view frustum in light space is huge. So=20
>>>>>         =20
>>>>>
>>>>your trapezoid
>>>>       =20
>>>>
>>>>>approximation doesn't help you much. Also, it doesn't seem=20
>>>>>         =20
>>>>>
>>>>to help the
>>>>       =20
>>>>
>>>>>duelling frustum case at all that I can see (because I don't=20
>>>>>         =20
>>>>>
>>>>believe there
>>>>       =20
>>>>
>>>>>_is_ a way to solve that with a single buffer projected with=20
>>>>>         =20
>>>>>
>>>>a simple 4x4
>>>>       =20
>>>>
>>>>>matrix).
>>>>>
>>>>>However, there's the stuff about the 80/20 mix that I don't=20
>>>>>         =20
>>>>>
>>>>fully understand
>>>>       =20
>>>>
>>>>>- maybe that somehow compensates for large far-clip-plane=20
>>>>>         =20
>>>>>
>>>>distances. But who
>>>>       =20
>>>>
>>>>>uses a far clip plane that isn't basically infinite these=20
>>>>>         =20
>>>>>
>>>>days? The only
>>>>       =20
>>>>
>>>>>case I can think of is corridor shooters, and 90% of your=20
>>>>>         =20
>>>>>
>>>>lights there are
>>>>       =20
>>>>
>>>>>very close to the view frustum, so again - minimal gain from=20
>>>>>         =20
>>>>>
>>>>TSM (in a
>>>>       =20
>>>>
>>>>>corridor shooter, apart from the omnidirection-light=20
>>>>>         =20
>>>>>
>>>>problem, which is a
>>>>       =20
>>>>
>>>>>different kettle of fish altogether, you can pretty easily=20
>>>>>         =20
>>>>>
>>>>get away with
>>>>       =20
>>>>
>>>>>dumb BB shadowbuffers because the change in texel density=20
>>>>>         =20
>>>>>
>>is fairly
>>   =20
>>
>>>>>moderate, unlike something like the sun outdoors).
>>>>>
>>>>>So it seems like it's better than PSM for some cases, but=20
>>>>>         =20
>>>>>
>>>>doesn't solve any
>>>>       =20
>>>>
>>>>>of the real-world cases (duelling frustums), and as far=20
>>>>>         =20
>>>>>
>>as I can see,
>>   =20
>>
>>>>>pushing the far clip plane out to sensible distances causes=20
>>>>>         =20
>>>>>
>>>>it lots of
>>>>       =20
>>>>
>>>>>trouble.
>>>>>
>>>>>I also don't understand the videos - their PSM=20
>>>>>         =20
>>>>>
>>>>implementation seems to be
>>>>       =20
>>>>
>>>>>performing terribly - far worse than I'd expect. There's no=20
>>>>>         =20
>>>>>
>>>>reason I can see
>>>>       =20
>>>>
>>>>>that it should ever be _worse_ than the relatively dumb BB=20
>>>>>         =20
>>>>>
>>>>case. Another
>>>>       =20
>>>>
>>>>>(rather more minor) quibble I have is that if one of the=20
>>>>>         =20
>>>>>
>>>>Cool Features about
>>>>       =20
>>>>
>>>>>TSM is that the changes in mapping are continuous, so you=20
>>>>>         =20
>>>>>
>>might get
>>   =20
>>
>>>>>aliasing, but you never get pops, then pick a buffer=20
>>>>>         =20
>>>>>
>>>>resoloution that is low
>>>>       =20
>>>>
>>>>>enough to show me the texels not-popping. They've picked one=20
>>>>>         =20
>>>>>
>>>>where I can't
>>>>       =20
>>>>
>>>>>actually see any texels, so they could be popping every=20
>>>>>         =20
>>>>>
>>>>single frame and
>>>>       =20
>>>>
>>>>>you'd never know it.
>>>>>
>>>>>
>>>>>Has anyone actually tried this stuff in a real game? Or has=20
>>>>>         =20
>>>>>
>>>>the experience
>>>>       =20
>>>>
>>>>>of PSMs put everyone off wacky projections for life? I know=20
>>>>>         =20
>>>>>
>>>>I'm a lot more
>>>>       =20
>>>>
>>>>>wary about investing time in this stuff after that (hey -=20
>>>>>         =20
>>>>>
>>>>that's why I'm
>>>>       =20
>>>>
>>>>>posting this message :-).
>>>>>
>>>>>
>>>>>TomF.
>>>>>
>>>>>
>>>>>=20
>>>>>
>>>>>         =20
>>>>>
>>>>>>-----Original Message-----
>>>>>>From: gda...@li...=20
>>>>>>[mailto:gda...@li...] On=20
>>>>>>Behalf Of Tom Forsyth
>>>>>>Sent: 25 August 2004 09:47
>>>>>>To: gda...@li...
>>>>>>Subject: [Algorithms] General-purpose shadowbuffer=20
>>>>>>           =20
>>>>>>
>>implementation.
>>   =20
>>
>>>>>>So a few days ago I finished my StarTopia "patch" that=20
>>>>>>properly and fairly
>>>>>>robustly implements the stuff I talked about in my GDC 2004=20
>>>>>>talk (which was
>>>>>>a fairly blatant hack^H^H^H^H proof of concept with a=20
>>>>>>horrible bug I only
>>>>>>discovered later).
>>>>>>
>>>>>>If you want to actually run it, you need a copy of the=20
>>>>>>           =20
>>>>>>
>>>>game, and then
>>>>       =20
>>>>
>>>>>>download both patches from my site (link below). Probably=20
>>>>>>almost impossible
>>>>>>to find in the shops, but plenty on Ebay and P2Ps and=20
>>>>>>suchlike (for *ahem*
>>>>>>evaluation purposes, obviously)
>>>>>>
>>>>>>http://www.eelpi.gotdns.org/startopia/startopia.html
>>>>>>
>>>>>>There's some pretty pictures and daft text as well. If anyone=20
>>>>>>wants an even
>>>>>>slower version with lots of debugging info on the=20
>>>>>>shadowbuffers, just yell
>>>>>>and I'll see what I can rustle up for you.
>>>>>>  =20
>>>>>>
>>>>>>           =20
>>>>>>
>>>>><snip>
>>>>>
>>>>>
>>>>>
>>>>>-------------------------------------------------------
>>>>>SF.Net email is sponsored by Shop4tech.com-Lowest price on=20
>>>>>         =20
>>>>>
>>>>Blank Media
>>>>       =20
>>>>
>>>>>100pk Sonic DVD-R 4x for only $29 -100pk Sonic DVD+R for only $33
>>>>>Save 50% off Retail on Ink & Toner - Free Shipping and Free Gift.
>>>>>http://www.shop4tech.com/z/Inkjet_Cartridges/9_108_r285
>>>>>_______________________________________________
>>>>>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 BEA Weblogic Workshop
>>>>>FREE Java Enterprise J2EE developer tools!
>>>>>Get your free copy of BEA WebLogic Workshop 8.1 today.
>>>>>http://ads.osdn.com/?ad_idP47&alloc_id=10808&op=C3=8Ck
>>>>>_______________________________________________
>>>>>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
>>>>>
>>>>
>>>>-------------------------------------------------------
>>>>This SF.Net email is sponsored by BEA Weblogic Workshop
>>>>FREE Java Enterprise J2EE developer tools!
>>>>Get your free copy of BEA WebLogic Workshop 8.1 today.
>>>>http://ads.osdn.com/?ad_idP47&alloc_id=10808&op=3Dick
>>>>_______________________________________________
>>>>GDAlgorithms-list mailing list
>>>>GDA...@li...
>>>>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>Archives:
>>>>http://sourceforge.net/mailarchive/forum.php?forum_ida88
>>>>
>>>>       =20
>>>>
>>
>>TF> -------------------------------------------------------
>>TF> This SF.Net email is sponsored by BEA Weblogic Workshop
>>TF> FREE Java Enterprise J2EE developer tools!
>>TF> Get your free copy of BEA WebLogic Workshop 8.1 today.
>>TF> http://ads.osdn.com/?ad_idP47&alloc_id=10808&oplick
>>TF> _______________________________________________
>>TF> GDAlgorithms-list mailing list
>>TF> GDA...@li...
>>TF> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>TF> Archives:
>>TF> http://sourceforge.net/mailarchive/forum.php?forum_ida88
>>
>>
>>
>>--=20
>>Best regards,
>> Greg                            mailto:ghj...@lv...
>>NH=C2=B5=C5=A0=C2=B2=C2=B2u=10n=E2=80=B0=C2=AE=C2=A2=10=C2=BD=C2=B5=C2=AE=
'u=E2=80=93=C2=AE=E2=80=93=C2=B7=C2=ADy=C3=8A=10l=E2=80=B0=C2=AE=C2=A2=C2=
=B6=C3=8A=C2=A7vv=E2=80=BA=E2=80=A0=C3=9Bi=C3=BF=C3=BB(=C2=BA=C2=B7=1E~=C5=
=A0=C3=A0zw=C2=AD=C3=BEf=C2=A2=E2=80=A2=C2=AA=C3=9C=E2=80=A0+=C3=9E=C3=BD=
=C3=BA
>>+=C2=BAja=C2=A5=C3=BA+=C2=BAh=C2=9D=03=C2=AD|
>>
>>   =20
>>
>
>
>
>-------------------------------------------------------
>This SF.Net email is sponsored by BEA Weblogic Workshop
>FREE Java Enterprise J2EE developer tools!
>Get your free copy of BEA WebLogic Workshop 8.1 today.
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>Archives:
>http://sourceforge.net/mailarchive/forum.php?forum_ida88
>
> =20
>