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.”
Part 1
Part 2
Thank you,
L. Spiro
Tutorial: Tightly Culling Shadow Casters for Directional Lights
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.
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.
Author
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.
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.
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.
Agreed, splitting and warping techniques are largely independant of what it being discussed here.
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.
Yes, that is what I was referring to.
The shadow map resolution is not defined by the shape of the k-DOP.
Ok, that's the bit I misunderstood.
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.
But can you just clarify, you only need to consider receiving objects when determing the size of the shadow map, rather than casting 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?
Author
But can you just clarify, you only need to consider receiving objects when determing the size of the shadow map, rather than casting 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?
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
Hi,
looking at your code and the description "A frustum is basically a specialized form of a k-DOP with 6 sides or planes" 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 here (html cached version 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 fixed number of normal vectors in fixed 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.
looking at your code and the description "A frustum is basically a specialized form of a k-DOP with 6 sides or planes" 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 here (html cached version 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 fixed number of normal vectors in fixed 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.
Author
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
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
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.
I don't think I agree with either of these statements. The pages of RTCD you refer to say "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."
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.
Author
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
