Sign in to follow this  
L. Spiro

Tutorial: Tightly Culling Shadow Casters for Directional Lights

Recommended Posts

I have posted a 2-part tutorial on making air-tight k-DOP’s for use with directional lights’ bounding volumes on my site.
I would like any input, especially if I have messed up the algorithm while altering it slightly for my tutorial. But also I would like to know if the subject matter is presented clearly enough and if it is easy to follow.
If my diagrams are easy to understand, etc.

Of course, any other input welcome. Aside from “your coding style is fugly.”

[url="http://lspiroengine.com/?p=153"]Part 1[/url]
[url="http://lspiroengine.com/?p=187"]Part 2[/url]


Thank you,
L. Spiro

Share this post


Link to post
Share on other sites
Thanks, this is very interesting. I didn't look in detail at the code or implementation details (as I don't expect to actually use this in the foreseeable future) but I did read about the principles.

Firstly, I didn't know what the term 'k-DOP' was, and I'm a reasonably experienced graphics programmer. Of course, it only took two minutes to find out from Wikipedia, but since you use the term a lot it might be worth explaining as it only takes a paragraph.

Next, I would like to point out that there are two seperate reasons why we want to keep our bounds tight. The first reason it to maximise shadow resolution, and the second reason is to minimise the number of casters we draw into the shadow map. When we compare your apprach to simply taking the bounding 'square' of the view frustum projected into light space, we find that it does reduce the number of casters but does not increase the shadow resolution any further. I think... am I right?

I think also the system can be further improved. For example, consider that you have a caster which is in the view frustum, but the recieving object is outside the view frustum. In this case your caster does not need to be drawn into the shadow map, even though it is visible from both the light and the camera. I think you can improve you system by also considering which receivers are visible and finding the bounds of those. In the example above, no receiver is visible so the bounds shrink to zero and the caster does not get drawn.

Those are just my thoughts, and I think overall it's an excellent article. Shadow mapping sounds so simple ('just render the scene from the light and compare depths...') but it can be very complex in practice so it's good to see it documented.

Share this post


Link to post
Share on other sites
Thank you for your input.

I will add a note as to what a k-DOP is.

Maximizing shadow resolution is actually a bit of a separate topic, because once you have the minimum number of objects you need to draw, you have a few options as to how to proceed from there. Cascaded shadow maps and other techniques are designed to maximize shadow resolution nearer to the camera by partitioning the objects off and making different-sized maps for the partitions closer to the camera.

However there is one constant between all algorithms: The first step towards maximizing the map’s resolution is to cull objects that don’t need to be drawn.
The shadow map resolution is not defined by the shape of the k-DOP. The next step is to run over every object in the k-DOP and check the bounds of their bounding spheres (or less trivially their OBB’s).
You basically determine the resolution of the shadow map based off the spread of the objects in the k-DOP. If your k-DOP is huge but there is only one object sitting in the middle of it, you will wrap your texture dimensions just around that object, not the whole k-DOP volume.

And if you use the rectangular k-DOP for culling, you could end up adding a miscellaneous object over to the far lower-left, and suddenly the shadow texture would have to be stretched to cover both objects, and suddenly your resolution has gone to hell.


The last part is not really trivial, and typically more overhead than it is worth. It is going to be faster to just render the object needlessly rather than performing an exhaustive check between every object in the light’s k-DOP against every object in the view frustum, creating a k-DOP for each in the light’s view, etc. And can even cause faulty results on animated objects, which can’t always be correctly defined by their bounding volumes.

Even occluders are not worth the time, because generating the shadow map only means sending vertex data (not normals, UV’s, etc.) The bandwidth cost is minimal and there is no shader swapping nor texture swapping.


L. Spiro


PS: I checked the modifications I had made to my code and found that I had indeed made an error. It has been fixed and I can now verify the accuracy of the code itself.
My code contains typedefs for every primitive, but for anyone who is copying my code into their own projects, this is a simple Ctrl-Alt-F to change.

Share this post


Link to post
Share on other sites
[quote name='YogurtEmperor' timestamp='1319262498' post='4875267']
Maximizing shadow resolution is actually a bit of a separate topic, because once you have the minimum number of objects you need to draw, you have a few options as to how to proceed from there. Cascaded shadow maps and other techniques are designed to maximize shadow resolution nearer to the camera by partitioning the objects off and making different-sized maps for the partitions closer to the camera.[/quote]

Agreed, splitting and warping techniques are largely independant of what it being discussed here.

[quote name='YogurtEmperor' timestamp='1319262498' post='4875267']However there is one constant between all algorithms: The first step towards maximizing the map’s resolution is to cull objects that don’t need to be drawn.[/quote]

Yes, that is what I was referring to.

[quote name='YogurtEmperor' timestamp='1319262498' post='4875267']The shadow map resolution is not defined by the shape of the k-DOP. [/quote]

Ok, that's the bit I misunderstood.

[quote name='YogurtEmperor' timestamp='1319262498' post='4875267']The next step is to run over every object in the k-DOP and check the bounds of their bounding spheres (or less trivially their OBB’s).
You basically determine the resolution of the shadow map based off the spread of the objects in the k-DOP. If your k-DOP is huge but there is only one object sitting in the middle of it, you will wrap your texture dimensions just around that object, not the whole k-DOP volume.[/quote]

But can you just clarify, you only need to consider [i]receiving [/i]objects when determing the size of the shadow map, rather than [i]casting [/i]objects? That is, you set your shadow map size to be big enough only to cover the receiving objects, because these are the only ones which need the shadow map applied. If you have a caster and a receiver both in your view frustum, but the caster does not overlap the receiver from the light's point of view, then the shadow map does not need to be big enough to contain the caster?

Share this post


Link to post
Share on other sites
[quote name='PolyVox' timestamp='1319478902' post='4876378']
But can you just clarify, you only need to consider [i]receiving [/i]objects when determing the size of the shadow map, rather than [i]casting [/i]objects? That is, you set your shadow map size to be big enough only to cover the receiving objects, because these are the only ones which need the shadow map applied. If you have a caster and a receiver both in your view frustum, but the caster does not overlap the receiver from the light's point of view, then the shadow map does not need to be big enough to contain the caster?
[/quote]
I can confirm this for conceptual clarification, as long as it is also stated that the implementation of this is almost guaranteed to be slower than not.


L. Spiro

Share this post


Link to post
Share on other sites
Hi,

looking at your code and the description [i]"A frustum is basically a specialized form of a k-DOP with 6 sides or planes"[/i] leads me to think your usage of k-DOP does not agree with the standard one. The definition presented originally in Klosowski et al. in [url="ftp://ftp.ams.sunysb.edu/pub/geometry/cd-tvcg-97.ps.gz"]here[/url] ([url="http://webcache.googleusercontent.com/search?q=cache:CCSZS60Oln8J:ftp://ftp.ams.sunysb.edu/pub/geometry/cd-tvcg-97.ps.gz+ftp://ftp.ams.sunysb.edu/pub/geometry/cd-tvcg-97.ps.gz&cd=1&hl=fi&ct=clnk&gl=fi&client=opera"]html cached version[/url] if you are .ps-allergic), and Christer Ericson's Real-Time Collision Detection, p. 117, refer to k-DOP being a closed polyhedron with a [b]fixed[/b] number of normal vectors in [b]fixed[/b] directions. This allows each k-DOP object to not require storing full plane equations (the normal and scalar for each plane), only the min and max distance of the object along each normal. This effectively means that a k-DOP is a polyhedron shape which always consists of pairs of "slabs", i.e. if it has a face pointing towards p, it also has a face pointing towards -p (unless it's degenerated to a single vertex). Hence, a perspective frustum would be a 10-DOP (stores 5 pairs of min&max scalars), and an orthographic frustum would be a 6-DOP (stores 3 pairs of min&max scalars).

The major idea with k-DOPs is this decoupling and uniformization of the plane normal directions between all k-DOPs (making the fixed choices ahead of time, e.g. at compile time), which makes testing k-DOPs for intersection a lot easier than testing the intersection of arbitrary polyhedrons.

In your usage, I think the term closed and convex polyhedron (or polytope) would probably be more standard.

Share this post


Link to post
Share on other sites
You are referring to specialized forms of k-DOP’s that have been given certain restrictions or properties to make them more efficient for certain cases.
In Klosowski et al., what is being presented is a middle-ground solution between the lack of tightness offered by other forms of bounding volumes and the slow update speed involved with traditional k-DOP’s.

Fixing the plane directions is a restriction designed to reduce the amount of data needed to represent the planes, as you noted. This is a “discretely oriented” form of k-DOP.
Pairing of planes is called slabs.
Refer to pages 116 and 119 of Christer Ericson's Real-Time Collision Detection.
On page 119, he explains that keeping a restriction on the number of planes and the directions they can face makes a hard-coded function for computing the k-DOP less expensive than for those k-DOP’s that allow any directions.


So a standard k-DOP is actually the one that allows any number of planes and at any orientation. From there, non-standard forms are derived to improve performance in certain well defined case.


L. Spiro

Share this post


Link to post
Share on other sites
[quote name='YogurtEmperor' timestamp='1319609538' post='4877071']
This is a “discretely oriented” form of k-DOP.
So a standard k-DOP is actually the one that allows any number of planes and at any orientation. From there, non-standard forms are derived to improve performance in certain well defined case.


[/quote]

I don't think I agree with either of these statements. The pages of RTCD you refer to say [i]"These k-DOPs are convex polytopes, almost identical to the [Kay-Kajiya's] slab-based volumes except that the normals are defined as a fixed set of axes shared among all k-DOP bounding volumes." [/i]

The term "DOP" comes from "discrete oriented polytope", and I don't think there exists a (more) "discretely oriented" form of the k-DOPs that is different than what is given in RTCD. I think the standard form of k-DOP is one that specifies the number and the directions of the plane normals ahead of time, so that the data structure can be stored like given in p. 117 of RTCD.


Share this post


Link to post
Share on other sites
Now that you mention it, DOP does mean “discretely oriented polytope”.
Perhaps I should use the term n-OP (as k is also noted for indicating a fixed amount). I am open to suggestions.

Than you for catching that and re-correcting me. Sometimes my orientation suffers from floating-point imprecision.


L. Spiro

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this