LiSPSM shadows [new demo/shadow tech comparison]

[LordSteiner]

As already stated in the developers' forum I'm currently implementing the light space perspective shadow maps (LiSPSM) for OGRE. The algorithm is done so I would like to present you some stats. You can try them yourself, just snatch the binaries. Everything needed is on board (press F1 for the key assignment). Sources will follow.

Download:
Binaries (16.2MB)
new binaries (18.8MB)
Patch submitted
Pics (6.4MB)

The performance was measured on a P4 3.20GHz with a sloooww GeForce 5200 (didn't I mention I need a new card? ) in 800x600 windowed mode. Camera position for the check was the original start position. The shadow cam viewports were of course disabled.
The underlying OGRE version is the CVS HEAD as it was on 07.11.

90.3 fps (82.3 fps) - (Shadows disabled)
35.7 fps (34.5 fps) - Uniform (Modulative)
33.6 fps (32.5 fps) - LiSPSM (Additive)
33.5 fps (32.4 fps) - Uniform Focused (Additive)
33.0 fps (31.9 fps) - Uniform (Additive)
32.4 fps (31.3 fps) - Plane Optimal (Additive; light types forced to spot)
22.6 fps (22.6 fps) - Stencil (Modulative)
20.5 fps (20.5 fps) - Stencil (Additive)

The interesting thing is that LiSPSM is a tiny bit faster than uniform focused (actually it's less than 0.1 fps difference), although uniform focused does not calculate the LiSPSM matrix but only has the intersection body procedure in common.
Another thing to mention are the values in brackets. Frame rates for texture based shadows drop about 1 fps in this example after the stencil shadow technique has been activated once.

Here are some comparison screenshots. Modulative were skipped as the resulting shadow shapes are the same. All screenshots, including the collage sources may be found here or in the pics-package above. Note that the newly added shadow techniques are LiSPSM and Uniform Focused.

Scene with enabled LiSPSM shadows


Shadow comparison (close)



Shadow comparison (normal)



Plane optimal and stencil shadows are unbeaten: Plane optimal does - as the name already reflects - a perfect mapping onto an arbitrary plane (here the floor plane). Stencil of course extrudes the visible edges of the meshes to infinity (well, at least as far the shadow is defined) and therefore also offers perfect shadows. The scene will be mostly common to you. The app recycles only the scene elements and is based on the example application, frame listener and loading bar headers.

Uniform shadow maps with a focus step produce very detailed shadows when the intersection body (the visible scene area and all shadow casters that affect this area) is small, however while moving the camera shadow swimming is extreme.


OGRE changes:
The LiSPSM technique uses a focus step (which is also applied for the uniform focused shadows) which requires additional functionality for the scene manager and scene node classes. The modified scene manager returns a shadow caster list for a specific light and a bounding box containing the currently visible objects.


Although some problems remain. I posted some of these into the 'LiSPSM shadows' thread (developer talk), however did not get any response - except for the point light issue which still do not work correctly under all circumstances.

Const scene manager
The scene manager does not offer const methods to retrieve the shadow casters and the visible objects. The functionality is already present in the form of the two methods SceneManager::findShadowCastersForLight(..) and SceneManager::_findVisibleObjects(..) as sinbad pointed out. At the moment I'm casting the const away, however this is bad style.
My proposition is to add another shadow texture type or a sub flag, so the scene manager caches the results for these two methods for each shadow casting light and cam before generating the shadow maps. The shadow map algorithm may now use const getters. The cached results may also be used by the renderer afterwards.

Shadow texture deletion
Normally, when a shadow texture is created the old will be erased first. However this is not done at the moment with the current CVS version. The warning given points the user to a potential use of two scene managers, but this is in my case not applicable. I also tested this with an untouched Ogre dll and a "naked" application that only switches the shadow textures. Each time the smart pointer count equals five instead of four which is the legal count for deletion (SceneManager::destroyShadowTextures(..)).

Shadow texture preparation
At the moment shadow cameras are updated in SceneManager::prepareShadowTextures(..) without considering whether the current light is casting shadows or not. Skipping non-casters may save some performance.

Octree scene manager
Just for info: The method SceneNode::_findVisibleObjects(..) always fails because the octree scene manager root node does not have a world bounding box (the octree scene manager has its own _findVisibleObjects(..) method). Therefore the check 'cam->isVisible(mWorldAABB)' is always negative. LiSPSM however does work with the octree scene manager.

Shadows texture fade (additive)
Uniform shadows with (in this case; see screenshot below) directional lights don't fade out in additive mode. When the shadow map is too small sized in regard to the area of coverage shadows disappear abruptly and, in case the outer shadow map pixel depth refers to a shadow texel the shadow is clamped all over the plane. Modulative texture fading works without any problems. However there are still some problems with point lights in some cases.

[Falagard]

Wow, you're my new hero! This looks amazing in action and runs very fast. Nice work!

I was definitely waiting to see what you came up with and it was worth the wait.

[dazKind]

Very nice work!

[sinbad]

Excellent, this will really help - thanks!

On the changes, most seem sensible although we'll have to see them first to judge. For the caching / non-caching I would personally favour abstracting this as much as possible. One option is to have ShadowCameraSetup have a getCacheShadowCasters method which then influences the SceneManager behaviour. Perhaps a more elegant option would be to have an option which causes the total bounds to be built up during the regular _findVisibleObjects, if that's all that's needed - that would eliminate the need for a second iteration over the objects perhaps and decouple the process further.

Re SceneManager::prepareShadowTextures - it only prepares for lights which have casting enabled because in the latest CVS (this changed recently) all of the lights which cast shadows are grouped at the start of the light list. I suppose if there were not enough shadow casting lights nearby it could be a waste but it is expected that the scene creator will optimise their scene to fit lights within the fixed number of shadow textures available, since their shaders will definitely need to be designed with this in mind anyway.

Re "Shadow texture deletion" - hmm, I wonder what happened here, perhaps I've added an additional reference somewhere. Will check.

Re "Octree scene manager" - yes, that's fine - the OSM works differently and doesn't use the SceneNode::_findVisibleObjects method. Really this method should probably be in a 'default SM' subclass instead.

Once you've made the source available, please can you submit it as a patch - we'll need you to agree to our licensing too. All the details are in the Developers section on the main site.

[sinbad]

Ah yes, it's because the TextureUnit is cacheing the texture pointer now instead of looking it up by name. I need to clear that down.

[CaseyB]

This is AWESOME! The Plane Optimal shadows looked amazing and ran like a dream on my computer! The only thing that I noticed is that the shadow volumes seem to be a little offset from the geometry.

Not sure what causes this. But, really, WOW!

[Vectrex]

amazing! Really fast and really good. One question, are they capable of self shadowing? Some other LiPSPM demos i've got seem to do it nicely (most of the time).

[LordSteiner]

@sinbad
Good thought, however the intersection body calculation needs both options, the casters in the light frustum and the visible objects in the camera frustum.

@CaseyB
Plane optimal shadows were implemented by peridexion as part of SoC 2006. I only implemented LiSPSM and uniform focused (actually uniform focused are an interstage product on the way to the LiSPSM). Have a look here and here. The plane optimal shadow mapping here is always done in such a way that the shadow samples are perfectly placed when casting shadow on an arbitrary plane. In case the shadow is not cast on the plane, the quality decreases. However I do not have any comparisons.
Btw. It would be nice if you could add some fps stats for the other shadow types and post them here, including your hardware info. 315 fps are really impressive.
The offset seems to be a depth bias to avoid self-shadowing. Maybe a member from the team could tell us how exactly this is done in OGRE.

@Vectrex
All texture based shadow techniques are capable of self shadowing. For OGRE you just need custom shaders. Peridexion wrote some custom shaders as part of his SoC project including a slope scale bias step that makes it possible to use self-shadowing. Unfortunately the scene parts flicker badly on my card and a bias is applied... Really strange. Sinbad already has a point "Resolve issues with depth shadow map merge" on his list. So maybe we're lucky and they'll work soon

[sinbad]

Ah ok, yes this is slightly more difficult due to the rendering sequence doing the shadows first. We could keep the bounds from the previous render on the assumption that frame coherence will be high (although it would have to be tied to a Camera to deal with multiple viewports). The only alternative apart from that is to interleave the shadow update after the main viewport findVisibleObjects() (but before rendering(, but this would require keeping a separate render queue for the shadows so they could both exist at once, and fundamentally changes the SceneManager sequence. I prefer the former even though it's not quite as accurate, but what are your thoughts?

[LordSteiner]

My thoughts were to cache the visible objects for each camera before the shadow cameras are set up. So there is no change in the rendering order, except from the visible object determination which is moved further to the front. But we could also try your version first and use the "old" visible data.
Instead using a list, a bounding box could also be built up on the fly as you already stated. My reply was a bit imprecise (sorry). Not the casters / visible objects are needed in first place but the goal is to get their total physical extension.
However I have not looked into the exact rendering details yet.

For the shadow casters in the light frustum the scene manager could also offer a bounding box or rather ShadowCameraSetup::getCacheShadowCasters fetches a list and outputs an ABB. The scene manager may prepare these lists for each camera - light combination in advance. In the developers forum I suggested to use a new SHADOWDETAILTYPE, e.g. TEXTURE_xx_CACHED, to trigger these things and so no performance is wasted for things that are not used. Maybe the shadow algorithm could "request" this from the scene manager, so there wouldn't be a need for further types. However doing this for all camera - light combinations might be too expensive. One thought is that the shadow algorithm may "register" a certain camera to receive the list/abb from the scene manager. The first reply would be a blank ABB (e.g. initiated in the ctor), the second a valid one. Though this might be a bit complicated...

[CaseyB]

The computer that I have here at work is an XPS 600 with a 3.6GHz P4 Dual Core with 2 Nvidia 7900's hooked up using SLI... Yeah it'll chew up pretty much anything!

[sinbad]

Well, my main concern here is that there is no need to do this twice - an AABB can be built up as part of the usual finding of visible objects. So yes, one way to do this would be to move the finding of visible camera objects to before the shadow texture updates, but this would need a separate render queue. I realise the rendering order isn't changed (my imprecise wording this time!), but my initial thought was to avoid that if possible because it's a pretty major change for people who assume there's only one render queue in existence (Scenemanager writers for example). I'm not completely against changing it, I'd just like to see if the simpler approach is good enough first since it will have less of an impact.

I don't really understand your second paragraph, unless you're talking about static lights / objects? I don't think it's worth trying to cache for that - anything that's completely static should be using precalculated lighting really.

[LordSteiner]

With the second paragraph I meant the determination of the shadow casters for a specific camera-light combination. If we only take the visible objects by the main cam into account the casters will probably be clipped during the focus process.

Here is what I've changed:
For the visible objects determination I introduced a map containing all the bounding boxes which are updated during the normal _findVisibleObjects step. So their processing by the shadow algorithm is one frame delayed.
The shadow casters AAB will be determined in prepareShadowTextures after the custom shadow camera setup and stored into a cascaded camera-light-aab map. At the moment this is always done, regardless of the specific custom shadow type's requirements.
Both AABs are available via const getters.

I uploaded the scene manager / scene node changes here in case you want to diff it. The base version is the today's cvs head.

[sinbad]

With the second paragraph I meant the determination of the shadow casters for a specific camera-light combination. If we only take the visible objects by the main cam into account the casters will probably be clipped during the focus process.

We already deal with that issue through findShadowCastersForLight of course - but I guess you're suggesting we try to cache the results from that? In most cases the camera is going to be mobile enough that I don't think this will be of huge benefit.

Thanks for the updated demo & source. I'm occupied getting 1.2.4 sorted out right now but will take a look asap.

BTW as described in the Developers section of the main site we'll need a contributor license agreement from you to accept this patch, whatever the final form is.

[LordSteiner]

The above link only contains the changes of the scene manager and the scene node classes to show the planned changes. Sources and agreement are still forthcoming.

You're right, caching may be a waste of time in most cases but maybe a general CHC approach (not only for the shadow stuff) is worth considering.
Furthermore the work is already done by _findVisibleObjects (I think this was your intention - I guess I was too much focused on this findShadowCastersForLight method). I removed the cascaded camera-light-aab map and added a map that enables the mapping between lights and shadow cameras which is all that's needed.
I updated the scene manager / scene node changes file accordingly.

[sinbad]

Please can you follow the procedure in the Developers section for generating a patch rather than posting whole changed files? We're making changes all the time and verbatim files are much harder to integrate / review. Thanks.

[LordSteiner]

Please can you follow the procedure in the Developers section for generating a patch rather than posting whole changed files? We're making changes all the time and verbatim files are much harder to integrate / review. Thanks.

Sorry, but the files were just intended to function as a preview for the discussion, not as a patch.
I will submit the full patch in the next few days, including the LiSPSM sources and some bugfixes. And of course the contributor's license agreement.

[sinbad]

The point was that it's a lot more practical to review changes in patch form, rather than reading through a 2000 line file, even if it's not an 'official' patch yet. I'll have to manually diff them anyway to see what I need to look over. I'll wait for the final patch and we'll have a full discussion then.

[LordSteiner]

@CaseyB
(...)
The offset seems to be a depth bias to avoid self-shadowing. Maybe a member from the team could tell us how exactly this is done in OGRE.

Bias is not correct. The column in the scene continues below the floor plane and is cast fully onto the plane (texture based shadows only), regardless if the taken samples lie above or below it.

[sinbad]

The slight offset is because the columns are slightly below the plane. One way of dealing with this would be to render non-transparent non-casters into the shadow texture with a white material when self-shadowing is turned off (with self-shadowing on, the required depth shadow mapping solves this). This solves 'through projection' of shadows for simple (non depth) texture shadows (although not back projection which needs a different approach). Providing solutions for back & through projection with texture shadows wihtout necessarily using shaders is definitely on my radar.

[LordSteiner]

Patch is submitted. If you want to take a peek in, here's the URL: http://sourceforge.net/tracker/index.ph ... tid=302997

New binaries with LiSPSM debug info (Keys 7 and 8) are also available (see first post) with the two different nopt routines simple and normal.

Patch info

1. Bugfixes
2. Changes to the OGRE core
3. Uniform Focused Shadow Mapping
4. Light Space Perspective Shadow Mapping
5. Shadow sample / new shadow demo
6. File overview (LiSPSM)

------------------------------------------------------------

1. Bugfixes

[SceneManager] Texture shadows not reappearing
Texture shadows currently aren't reactivated when switching back from stencil shadows or shadows disabled.
Problem: mShadowTextureConfigDirty flag not set when destroying shadow textures.
Solution: Dirty flag set to 'true' in SceneManager::destroyShadowTextures(void)

[SceneManager] Uniform shadow mapping applies custom shadow mapping accidentally
When switching from a custom shadow type to a non-custom shadow type (uniform shadow mapping) the custom camera is further applied. There is no way back to non-custom shadowing without deleting the shadow texture maps (and with the the cameras) once a custom shadow option has been applied.
Problem: Shadow texture cam custom view and projection matrices aren't reset.
Solution: Reset all texture cameras' custom view and projection matrices in SceneManager::setShadowTechnique(ShadowTechnique) when a texture shadow type is chosen.

[SceneManager] Shadow cast from the wrong light
In case a scene contains two activated lights and the second light is deactivated, then the first one will cast its shadows from the position of the second one and will also adapt the second light's type.
Problem: (unknown / not investigated)
Solution: Skip the shadow texture generation for lights that do not cast shadows in SceneManager::prepareShadowTextures(..).

[**** still open ****] Shadows texture fade (additive)
Uniform shadows with (in this case; see screenshot below) directional lights don't fade out in additive mode. When the shadow map is too small sized in regard to the area of coverage shadows disappear abruptly and, in case the outer shadow map pixel depth refers to a shadow texel the shadow is clamped all over the plane. Modulative texture fading works without any problems. However there are still some problems with point lights in some cases.


2. Changes to the OGRE core

Apart from the bugfixes as stated above, the following things were changed:

[SceneManager] Assemble shadow caster / visible bounding boxes
The SceneManager now has two new lists. CamVisibleObjectsMap stores an axis aligned bounding box for each camera which is assembled during the 'normal' _findVisibleObjects(..) call. For shadow cameras an additional light-camera mapping is needed (ShadowCamLightMapping). The assembled bounding boxes are made publicly available by the const getters getVisibilityABBForCam(const Camera*) and getShadowCastersAABForLight(const Light*).
CamVisibleObjectsMap in detail:
- Camera pointer inserted in SceneManager::createCamera(..)
- Camera entry removed in SceneManager::destroyCamera(..)
- AAB updated during _findVisibleObjects(..)
ShadowCamLightMapping in detail:
- Camera entry removed in SceneManager::destroyCamera(..)
- List cleared / assembled in SceneManager::ensureShadowTextureCreated(..) (dummy Light entry)
- Shadow camera to light mapping updated in SceneManager::prepareShadowTextures(..)
The following plugin scene managers were also adapted:
- BSP (couldn't test it - the test scene isn't even visible)
- Octree

[SceneManager] Shadow texture generation skipped when light doesn't cast
The shadow texture generation is skipped in SceneManager::prepareShadowTextures(..) when a light does not cast any shadows. Originally this was planned as a 'feature' but resulted in a bugfix (see above). The following stats were measured using the new shadows sample application with LiSPSM and one directional and one spot light (P4 3.20GHz, GeForce 5200, 800x600 windowed):

light status |(skipped) |(not skipped)
-------------------------------------------------
both lights enabled | 33.8 fps | 33.8 fps
only directional enabled | 41.6 fps | 34.4 fps
only spot enabled | 42.2 fps | 34.9 fps
no light enabled | 55.2 fps | 35.3 fps


3. Uniform Focused Shadow Mapping

The main difference to uniform shadow mapping is that uniform focused 'focuses' onto the visible scene including the shadow caster's that affect it (namely the intersection bodyB). As a result the shadows gain quality when the bodyB is small and converge to normal uniform shadow mapping for a bigger bodyB. The normal uniform shadow mapping however has a special treatment, so the shadows don't look so pixelated as uniform focused does.
The intersection body generation was introduced by Stamminger et al. for perspective shadow mapping (PSM). Wimmer et al. (LiSPSM) modified it slightly from (V + l) \cap S \cap L to ((V \cap S) + l) \cap S \cap L (\cap: convex intersection, +: convex hull operation). The modified procedure however leads in some cases to disappearing shadows (point/spot lights). Valid parts of the scene are clipped, so shadows are partly incomplete. The cause may be the transformation into light space that is only done for the corner points which may not contain the whole scene afterwards any more. This implementation falls back to the method of Stamminger et al. ((V + l) \cap S \cap L) which does not show these anomalies. This does not affect the bodyB generation for directional lights. The only necessary prerequisite is that the camera must be part of the scene bounding box or the shadows may be shortened.


4. Light Space Perspective Shadow Mapping

For the shadow demo application the calculated n_opt (see below) factor applied a too strong perspective warping which led to the introduction of a constant factor (LiSPSMShadowCameraSetup::const_nOptAdjustFactor) which further affects the applied n_opt. For the demo a factor of about 5 is suitable, however this may depend on the scene.
A second way to generate n_opt uses a very simple approach taking only a near view point and the camera's near and far clip distances into account.

* n_opt: LiSPSM automatically adjusts the shadow quality. This process is done by the n_opt value, which determines the distance between viewer and near clip plane for the LiSPSM projection. The perspective warp will be strong in case the value is small which leads to a better shadow sample distribution for near objects. Far away objects loose shadow quality. A large n_opt value leads to the opposite effect.


5. Shadow sample / new shadow demo

If you want to use this sample as another shadows demo you'll have to adapt it a bit. For development I used a LiSPSM dll. The needed media files are also present.
I wrote some shadow mapping shaders based partly Hamilton's shaders, however I get massively noise in the scene... (Hamilton's shaders also showed such things)


6. File overview (LiSPSM)

LiSPSMShadowCameraSetup: LiSPSM code
DefaultFocusedShadowCameraSetup: Uniform shadow mapping and bodyB/LVS generation
Body/Polygon: convex body based on polygons
PointListBody: point list helper
LiSPSM4OgreMain: some helper definitons, such as vector comparison with epsilon, ...

[sinbad]

Thanks, will look at this in detail in the next fw days.

[Yavin]

@sinbad: I followed the comments of the patch and checked out the current head of ogrenew to see the progress of the shadows demo. I couldn't compile the shadows demo because the project script seems to be corrupt.

[sinbad]

Eh? Which script? I'm only using VC8 and that works fine but other tools might need fixing up - I've done them the best I can without actually using the tools involved but am leaving it to other team members who use those tools to test.

[haffax]

Yavin, maybe you didn't update your OIS to version 1.0? It is now required and the dependency package hasn't been updated yet. You have to compile it yourself.