• ### What is your GameDev Story?

This topic is 1886 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm trying to implement some of the techniques described in this article for culling objects during shadow map generation. In particular I'm trying to get working the method of computing the projected shadow caster bounding volumes to cull objects that may be visible to a light frustum but don't actually cast a shadow into the camera view frustum. The author describes this as follows:

Therefore, if shadow casting objects are represented as bounding boxes, a frustum can be used to represent the projected shadows, and we can reuse the frustum-frustum culling test developed above.

To build this frustum, the demo computers a tight bounding cone surrounding the light position and each shadow caster's world-space bounding box. This cone is trivially converted into a  centered frustum.

It sounds like he's describing a cone with vertex at the light position that extends towards the object and encloses its bounding box. However this volume definitely will not contain the shadow projected by the object (since the shadow will going to extend beyond the object in the direction of the light).

The attached figure is in the chapter, showing the case that this technique is meant to allow us to cull, complete with a picture of a frustum that looks like the one described which doesn't look very helpful for deciding to cull that object.

I don't have the source code to the demo so I can't be sure what his exact implementation looks like. Does anyone else have another interpretation of this that makes more sense?

Edited by doesnotcompute

##### Share on other sites

The sphere is both outside your camera’s frustum and on the other side of your camera’s frustum from the light source, therefor it should not be added to the set of shadow casters.

This is easy to test.

Take the ray from the point light and circle and call that direction A.

Now go over the planes of the frustum, and for each plane do a dot product with that plane’s normal and the A vector.

If the result is positive (the plane normals should point inward towards the inside of the frustum), skip that plane.

Otherwise, test that plane against the circle.

If the circle is found to be overlapping or in front of that frustum plane, the circle contributes to the shadowing of the scene and you stop testing the remaining frustum planes.

L. Spiro

##### Share on other sites

Ok that makes sense, thanks. I was also just generally interested in understanding what this article was describing because it's presented like: you calculate this special frustum for each object and just do a frustum-frustum test against the view frustum and that's it. I think if you construct the cone/frustum described in those sentences I quoted and then extend it to the light's far clip plane it should enclose any possible shadow cast by the object. But it doesn't account for the case shown in the picture so I guess an extra test like what you described is needed.

##### Share on other sites

Actually what I described is the entire process, not just an extra step, if organized correctly.

Instead of culling the frustum of the light’s current direction plus my added step, you should just build a single frustum out of the 2 (light’s frustum and camera’s frustum).

A frustum is normally thought of as 6 planes that enclose a certain area.

It can in fact have more planes than that and can enclose any shape of convex area.  So what you want to do is make a special type of frustum that can have up to 12 planes (the max you could ever get by combining these 2 sets of frustums) and fill them in as follows:

FOR EACH 6 DIRECTIONS OF LIGHT

First go over the camera’s frustum planes and add the ones that point towards the light source.  That means just doing a point/plane test and adding the planes that return     “FRONT” as a result (the point is in front of the plane).

Then add all 6 of the light’s current directional frustum planes.

Do it in this order to reduce unnecessary plane checks.

From here, using this newly created frustum, culling all scene objects works as normal.  Just run them through each plane and immediately reject any objects that are behind any of the planes.

END FOR

L. Spiro

##### Share on other sites

I see. Your algorithm definitely seems more efficient than what I've been working on. I tried to implement what you just described and I'm getting fewer objects culled than I had previously though. I implemented it like this:

static void GetVisibleForPointLight(BoundingFrustum const & viewfrustum, ForwardPoint const * light, BoundingFrustum const & lightFrustum, GeometryList const & everything, GeometryList & visible)
{
Plane planes[12];
int count = 0;

for (int i = 0 ; i < 6 ; i++)
{
if (viewfrustum.Planes[i].DotCoordinate(light->Position()) > 0.0f)
planes[count++] = viewfrustum.Planes[i];
}

Memory::Copy(&planes[count], lightFrustum.Planes, 6);
count += 6;

for (auto o = everything.Begin() ; o != everything.End() ; ++o)
{
BoundingSphere const & s = (*o)->WorldBound();

int inFront = 0;
for (int i = 0 ; i < count ; i++)
{
break;

++inFront;
}

if (inFront == count)
}
}


I'm calling this once per light direction rather than for all directions at once, otherwise I would have to frustum test the objects again per direction (if I'm not mistaken) since not all the objects are visible in each direction.

In my old method (that I was trying to implement from the ShaderX article) I was computing the light -> object frustum for each object and testing that against the camera frustum and putting everything in one big list and then culling per direction again.

There are about 300 objects in the scene I'm testing and I'm seeing the new version culling anywhere from 20-30 fewer objects up to more than 100 for some camera orientations. In both cases everything looks correct so it's not incorrectly culling anything. Maybe I have an error in my code somewhere though.

Edited by doesnotcompute

##### Share on other sites

I think the part I was missing in the implementation from the article is that the object shadow frustum doesn't have to actually originate at the light position, the near plane can be pushed all the way to the edge of the object's bounding box/sphere, which makes it a much tighter fit to the area where the shadow can be cast.

Here's another picture showing one of these object frusta in green. I think this also shows a case where your algorithm will identify the object as needing to be drawn when it actually casts a shadow that is not visible to the view frustum.

##### Share on other sites

Here's another picture showing one of these object frusta in green. I think this also shows a case where your algorithm will identify the object as needing to be drawn when it actually casts a shadow that is not visible to the view frustum.

There are 2 reasons my routine would not allow that object to be drawn:

1. Its bounding box (your object’s frustum shown in green) would be AABB, not projective.  And if projective, it would project away from the light source, not the camera.
2. The current direction seems to be -Z (if looking down from overhead).  It wouldn’t be included because it correctly does not cast a shadow from that part of the point light.  It would cast a shadow along the -X (assuming +Y = Up and we are looking straight down from overhead) if it cast a shadow at all.

This is a more accurate drawing of yours, drawn entirely by mouse because I am in a bit of a hurry:

If at all, it would be part of the second frustum shown in grey, not the one you showed in your image.  And the shadow must always go away from the light source, not the camera.

If it misses the grey box, there is no shadow because the light casts nothing onto anything distant beyond the outer reaches of the grey box.  No shadow because it is all black.

L. Spiro

##### Share on other sites

To save some cycles and maybe for more precise culling you could save 6bits information from view frustum culling pass and then reuse appropriate results for shadow culling. For view frustum culling it can be beneficial to use bit more expensive but tighter frustum test(like object space frustum vs aabb). So if you save result bit per plane you have this more accurate information for shadow culling as well.

##### Share on other sites

The larger frustum on the right was meant to be the camera, the one on the left was for the light. I guess I should have made that more clear

The algorithm you described earlier says to choose the camera planes that the light is in front of, in this case they are A, B, and C. The red object is also in front of all these planes and it is contained in the light frustum so it would pass all the plane tests and need to be rendered.

##### Share on other sites

I was still thinking about the earlier image in which the bigger frustum was the light’s.

You are correct that what I described above would have that result.

For this image the actual frustum you would want to create is this:

[attachment=18900:post-110845-0-96908200-1385145558 copy.png]

In order to do that you need to determine the actual points of your camera’s frustum and determine silhouette edges between adjacent planes to add the extra planes you need.

This is a lot more advanced than the algorithm I described but only different in how you add the second set of planes (instead of just adding all of the light’s planes).

However, it works the same way as I have already described here:

Tutorial: Tightly Culling Shadow Casters for Directional Lights (Part 1)

Tutorial: Tightly Culling Shadow Casters for Directional Lights (Part 2)

You can use this to replace the part where you copy all of the camera’s planes and then you will be done.

L. Spiro

Edited by L. Spiro

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 10
• 9
• 37
• 16
• ### Forum Statistics

• Total Topics
634128
• Total Posts
3015688
×