# Getting perspective Frustum in world coordinates

## Recommended Posts

Tispe    1468

Hi

I want to implement Shadow Mapping using orthogonal projection for directional lighting. The shadow map orthogonal frustum shall wrap around the Scene perspective frustum.

To calculate the projection transfrom for the shadow map I will use the D3DXMatrixOrthoOffCenterLH function. This function takes the vertices from view space (camera pointing in the lights direction) to projection space for the shadow map.

But in order to fill out the parameters correctly I need to get the Scene frustum vertices which are in Scene projection space, transform them back to world space, and forward into shadow map view space. Then I will max(), min() the x and y values, maybe I need w-division first?

How do I get the scene frustum vertices? Are they the simply the cube corners in clip space (-1, -1, 0) (1, -1, 0) (1,1,0) (-1, 1 ,0), (-1, -1, 1) (1, -1, 1) (1,1,1) (-1, 1 ,1) ? Do I have to perspective (divide)/multiply them with a w-value to get them to projection space from clip space? When I have them in perspective projection space I can use the inverse camera matrix to get them to world coordinates.

Cheers!

##### Share on other sites
BornToCode    1185
Why don't you extract the 6 planes after you multiply world by projection. That would give you the enclosed frustum in world space.

##### Share on other sites
Tispe    1468

Well I could, but then I would have to calculate 8 intersecting points of those planes. I want to know if perhaps I can get the clip space cube frustum transformed into world space.

##### Share on other sites
unbird    8335

You're almost there: You take these eight points and transform them with the inverse view-projection. This is done in homogenous space, so the points are (-1,1,0,1), (1,1,0,1), etc. After that, you divide the results by w.

It doesn't matter what transformations you use (inverse or not), the change from homogenous to cartesian is always a divide by w - after the transformation.

##### Share on other sites
L. Spiro    25620

Well I could, but then I would have to calculate 8 intersecting points of those planes. I want to know if perhaps I can get the clip space cube frustum transformed into world space.

You don’t need points. I am not sure why you think you need points or “frustum vertices”, but you need planes and nothing more.

“How far left, right, up, down, near, and far is the box containing the scene?”
This is answered by planar equations, not points.

You answer these questions by using all the objects’ bounding spheres and dot products in each of the 6 directions with the object positions that are in the culled area.
You’ve then created 6 planes that enclose the area. For a tighter fit you can add more planes.

The planar equations themselves determine how you make the matrix. You already know which planes represent the left and right, so you know how wide to make the box and its left-right center point.

http://lspiroengine.com/?p=153
http://lspiroengine.com/?p=187

L. Spiro Edited by L. Spiro

##### Share on other sites
Tispe    1468

I am not frustum culling, I am wrapping my shadow map frustum to cover the scene frustum. So I need to find the max and min X and Y values of the scene frustum vertices as seen from the light.

You're almost there: You take these eight points and transform them with the inverse view-projection. This is done in homogenous space, so the points are (-1,1,0,1), (1,1,0,1), etc. After that, you divide the results by w.

It doesn't matter what transformations you use (inverse or not), the change from homogenous to cartesian is always a divide by w - after the transformation.

So I transform the 8 vertices (-1, -1, 0 ,1) (1, -1, 0, 1) (1,1,0, 1) (-1, 1 ,0, 1), (-1, -1, 1, 1) (1, -1, 1, 1) (1,1,1, 1) (-1, 1 ,1, 1) using the inverse view-transform? Then forward into light shadow map camera space, then divide by w?

##### Share on other sites
Jason Z    6434

So I transform the 8 vertices (-1, -1, 0 ,1) (1, -1, 0, 1) (1,1,0, 1) (-1, 1 ,0, 1), (-1, -1, 1, 1) (1, -1, 1, 1) (1,1,1, 1) (-1, 1 ,1, 1) using the inverse view-transform? Then forward into light shadow map camera space, then divide by w?

To get the points that you originally asked for, yes, you would do the inverse of the view-projection matrix.  Transforming these points will give you the world space locations of the 8 corners of your view frustrum.  Since these are world space points, then you would need to transform them into shadow map view space and feed them to your function that you are using to create the orthogonal projection matrix.

I have never used the function that you are describing, so I'm not sure if this is exactly what you want to do - but it seems reasonable to me.  You are essentially just extracting the world space bounds of your view frustrum, and then using that to construct an appropriately sized orthogonal projection matrix based around your light's position/orientation.

##### Share on other sites
L. Spiro    25620

I am not frustum culling

I didn’t say you were.

I am asking, have you performed frustum culling on the objects inside the perspective frustum?
If you are going about this correctly, the answer should be yes. If not, yes you need a hack involving points and homogenous coordinates, and your shadow-map will be of fairly poor quality even in the best case, and also in the best case you are creating the absolute largest performance penalty.

I can explain step-by-step what you should be doing…

L. Spiro

##### Share on other sites
Tispe    1468

By wrapping the perspective (scene view volume) frustum inside the lights orthogonal frustum (canonical view volume), everything that can cast a shadow into scene view volume will be rendered to the shadow map, using std::numeric_limits<float>::max() and std::numeric_limits<float>::min() for +z and -z.

It is then only a matter of culling based on the shadow map frustum.

I plan on using RTW shadow mapping, possibly cascading the shadow map frustum further if the RTW quality does not hold up.

##### Share on other sites
L. Spiro    25620
So, I would normally just let you carry on with that plan since it might technically work (except for your plan on capturing things that can cast shadows into the perspective frustum without actually being in it), but then later you will be posting about shadow flickering and blocky shadows (which might be reduced by the 2 methods you mentioned, but since you also implied a certain expectation on the resulting quality, I can just say now it won’t be up to your expectations whichever way you go), and you would end up dropping this method entirely and having to do it all over again anyway, and I’d have to explain all of this then instead of now, and you would have a mess of code after all the things you had to scrap.

Once again, I repeat: Scrap the idea of using points.  And if you already have frustum culling implemented or plan to implement it, I am not sure why you chose this plan.

Set-up:
• Create the perspective matrix.  I assume you already do this.
• Extract the player’s frustum from it.
• Perform culling using this frustum.  Gather the objects the player can see into a list.
• Since you have to perform frustum culling from the player’s perspective anyway, there is no point in trying to dodge this part.
Now you are done with the set-up.  You have an array of objects the player can see.  This is your primary input.
These objects can cast and receive shadows, but objects outside of the frustum are not added yet.

• Using the existing array of objects, create an open-ended frustum for the directional light.  This means creating a 5-sided orthogonal frustum with left, right, top, bottom, and far planes.
• Your directional light has a direction vector called a “forward vector”.
• Calculate a right vector:
Vector vRight = Vector( 0, 1, 0 ) × vFoward; // × = cross product.
• Calculate an up vector after that:
Vector vUp = vForward × vRight;
• Normalize:
vRight.Normalize();
vUp.Normalize();
// vForward assumed to be normalized already.
• You now have right, up, and forward vectors all orthogonal to the light’s direction.
• For each object in the previous array, perform a dot product with the right vector against its position and add the radius of its bounding sphere. Maintain the minimum and maximum values in the left and right directions. Do the same with the top/bottom values and the up vector, and with the far value and the forward vector (no near plane is calculated).
• You now have the distances for left, right, top, bottom, and far planes. Make the 5 planes by combining those distances with the right, -right, up, -up, and forward vectors respectively. I shouldn’t need to explain that making a plane out of this is simply a matter of taking the min/max distance values you’ve just calculated in each direction and the positive or negative normals in those directions.
• You now have a 5-sided frustum with no near plane (it extends into infinity). Perform frustum culling and gather those objects into a list of objects that cast shadows into the player’s frustum.
From here on we only work with the new list of objects.  This list includes the perspective list’s objects in addition to all objects outside the perspective which can cast shadows.

Determine the dimensions of the orthogonal projection for the shadow map:
• Repeat the previous step 1, except that this time you use the new array of objects.  And this time include a “near” distance.
• Optionally, you can tighten these values by (don don DON) calculating the 8 points in the perspective frustum and using dot products against those to determine max-left, max-right, max-top, max-bottom, max-far, and max-near.  And solving for 3 planes’ intersection is trivial.
static LSE_INLINE LSBOOL LSE_CALL ThreePlanes( const CPlane3 &_pP0, const CPlane3 &_pP1, const CPlane3 &_pP2, CVector3 &_vRet ) {
CVector3 vU = _pP1.n % _pP2.n;  // Cross product.

f32 fDenom = _pP0.n * vU;
if ( absf( fDenom ) <= static_cast<f32>(LSM_REAL_EPSILON) ) { return false; }  // LSM_REAL_EPSILON = 1.192092896e-07

_vRet = (vU * _pP0.dist + _pP0.n.Cross( _pP1.n * _pP2.dist - _pP2.n * _pP1.dist )) / fDenom;

return true;
}
• Instead of using these distances to create planes, simply plug them into D3DXMatrixOrthoOffCenterLH().
• Render the shadow map using the new array of objects.
Your plan always creates the absolute most inefficient shadow map possible.  Using corner points should not be used to determine the directional light’s shadow size, it should only be used as an optional limiter. It’s the maximum size there can be, and thus a smaller bound should always be used if possible.
Additionally, your plan creates near/far discrepancies so vast that I wouldn’t be surprised if all you ever saw was a single slice of a part of a shadow. You would be absolutely maximizing aliasing and flickering, not to mention numerical instability in the shaders.
You need to make your shadow map based off what is actually in the scene. You need to select a near plane and a far plane as close together as possible and only barely what is necessary to render what will actually be seen.

The above sounds complicated but it’s really simple to implement and it will be close to what you will need to do in the future anyway. You would otherwise be plagued with quality issues and have to all of this anyway.

L. Spiro

##### Share on other sites
JohnnyCode    1046

You now have a 5-sided frustum with no near plane (it extends into infinity). Perform frustum culling and gather those objects into a list of objects that cast shadows into the player’s frustum.

This is the core of it all, and since I didn't spot any further elaboration on this in L. Spiro post, I will add up.

1- cull object from view of observer

2- cull objects from view of light in very screen space, Meaning, use AABB points of an object in screen space, but do not examine them only for being on screen (thus in light frustum) but also for being any of them over projected observer frustum in the light's projection space.

My concern is that if any of AABB points of an object is in screen space of light projection, it casts a shadow, but if none of its point is over projected observer frustum (in the light's projection), it does not cast shadow to observer frustum.

You would test if an AABB is in observer frustum by comparing only x,y components towards projected observer frustum x,y components. If any of them is positive, you  still have a chance of it not casting shadow. But this chance is rather small, and I would render from there on, but you can still test it if you wish further, so you move to comparing the AABB point along with z component for being in or over the projected frustum (not behind it)- this is rather grewsome step and will not save you from many rander calls most of the time I believe.

##### Share on other sites
Tispe    1468

Your plan always creates the absolute most inefficient shadow map possible.  Using corner points should not be used to determine the directional light’s shadow size, it should only be used as an optional limiter. It’s the maximum size there can be, and thus a smaller bound should always be used if possible.

If I understand you correctly, you want to gather all Objects in the scene and all Objects that cast shadows into the scene, and from this list of Objects take the bounding box/spheres to determine the size of the shadow map frustum?

But how would you account for self-shadowing terrain which is not in the object list? It might just be that in the far depth of the viewing frustum there might be some self-shadowing cravases, or a mountain range casting shadows on the valley below.

Edited by Tispe

##### Share on other sites
L. Spiro    25620
The algorithm handles all cases, including self-shadowing.
If you have a special way of storing terrain such that it is not in any object lists you have the responsibility of handling that case.

L. Spiro Edited by L. Spiro

##### Share on other sites
Tispe    1468

The algorithm handles all cases, including self-shadowing.
If you have a special way of storing terrain such that it is not in any object lists you have the responsibility of handling that case.

L. Spiro

So the algorithm assumes that the terrain is partitioned into smaller objects which you can add to the drawing list if they pass culling?

##### Share on other sites
L. Spiro    25620
It makes no assumptions, but for the sake of your performance I would certainly hope your terrain is chunked in some way.
Otherwise you will be drawing the whole thing twice (though the second time much (perhaps) of it will be off-screen and pixel-culled).

The second purpose of culling by objects is to have the smallest number of draw calls when creating the shadow map.

L. Spiro