Archived

This topic is now archived and is closed to further replies.

Faster Shadow Volume Found - Prove Me Wrong...

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I think I''ve found a speedup in the standard shadowvolume algorithm. This reduces the amount of triangles to be rendered for point-lightsources. The normal z-fail algo goes like: 1 - draw extruded silhouette edges 2 - draw dark cap at infinity 3 - draw light cap normal My speedup would be: 1 - draw extruded silhouette edges 2 - draw light cap inverted (back faced instead of front) at infinity 3 - draw light cap normal Imagine a sphere to be shadowed with a point lightsource. There are often (but not always) more dark faces than lighted ones. In any case there are never more lighted faces than dark faces. So using the light faces reduces the amount of faces to be rendered... Can you prove me wrong?...

Share this post


Link to post
Share on other sites
Another side effect of this is...

When a light is INSIDE an object. Parts or the whole object doesnt cast a shadow. When some faces of the object still face the light, this can result in a weird shadow (but still closed), and at the same time prevents a huge hit on the fillrate.

A weird shadow is not what we''re waiting for, I know.
But this weirdness could be a very small effect, especially for models constructed from an x amount of smaller meshes (head/arms/legs/...).
When a light accidently collides with an arm, wouldnt you rather have the rest of the world (exluding the arm) rendered with cool and fast shadow, than opt for the slow shadowing of the whole world (read: -no lighting at all-)!?!

Share this post


Link to post
Share on other sites
quote:
Original post by ApochPiQ
Concave objects.


Concave objects should be fine I think. The shadow volume remains closed.


I''m not an old-white-bearded-scientist, so I cant imagine I''m the invertor of this technique... but what am I missing???

Share this post


Link to post
Share on other sites
ChrisE, near the bottom of this page seems to suggest that Doom3 used that sort of inverse method in it''s stenciled shadows.

My expertise isn''t shadow volumes, so, even if I *had* seen it used, I probably wouldn''t notice to remember it.
-------
[shameless plug]
Hey, while you''re working on shadows, join my little group of peoples working on better terrain shadows :D
[/shameless plug]

I thought you were a busy game dev worker or something now, otherwise I might have bugged you earlier .

-Michael

Share this post


Link to post
Share on other sites
Explanation of the "concave objects" remark
Take a simple sphere mesh, and then CSG subtract it from a cube. The result I''m imagining would look something like the chalk used on billiards cues (i.e. a cube with most of one face turned into a spherical dent). If the light originates directly above the dent, each of the faces in the dent and on the surrounding edge is lit, while the 5 other faces of the object are unlit. You''d need more than 5 faces to nicely represent the dent, so you now have more lit than unlit faces. Your speedup no longer gains us any advantage. It doesn''t break the shadow volume algorithm at all, but it isn''t faster, either.

Share this post


Link to post
Share on other sites
quote:
Original post by ApochPiQ
Explanation of the "concave objects" remark
Take a simple sphere mesh, and then CSG subtract it from a cube. The result I'm imagining would look something like the chalk used on billiards cues (i.e. a cube with most of one face turned into a spherical dent). If the light originates directly above the dent, each of the faces in the dent and on the surrounding edge is lit, while the 5 other faces of the object are unlit. You'd need more than 5 faces to nicely represent the dent, so you now have more lit than unlit faces. Your speedup no longer gains us any advantage. It doesn't break the shadow volume algorithm at all, but it isn't faster, either.


You're right that it in this case more triangles need to be rendered... but the average amount of faces would still be lower.
Imagine your scene.. then rotate the LIGHT 360deg around the chalk-object. The average amount of faces lit is still lower than half of the total amount

[edited by - baskuenen on November 14, 2003 2:30:33 PM]

Share this post


Link to post
Share on other sites
quote:

Imagine a sphere to be shadowed with a point lightsource.

There are often (but not always) more dark faces than lighted ones. In any case there are never more lighted faces than dark faces.



If a sphere was to be shadowed by a point light source, i''d say in average 50% of its faces would be lit, and 50% would be shadowed, independantly of the view point.

In addition, i fail to see how you come up with your assertion that "there are never more lit faces than dark ones". Taking a standard scene with many viewpoints, i guess you''d find the ratio around 50% too. Or am i missing something obvious here..?

Y.

Share this post


Link to post
Share on other sites
quote:
Original post by Ysaneya

If a sphere was to be shadowed by a point light source, i''d say in average 50% of its faces would be lit, and 50% would be shadowed, independantly of the view point.



You''re right if we''d be talking about directional lights.

Imagine the light to be very close to the object...

Share this post


Link to post
Share on other sites
Yeah, if it''s very close to the sphere. But then in that case, it''d be far away from other objects. All in all, in average, i doubt you''ll see more than 50% of dark faces.

It''s like backface culling. In average, 50% of the faces are backface culled.

Y.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Do it yourself. If you want the respect, show me the STATS!


Thx for the comment, very much respect to you! You have clearly proven me wrong. This really helps me and everybody else very much....

Looks like I''m in the wrong forums
Bye

Share this post


Link to post
Share on other sites
I don't see why you take exception to AP's comments. You should keep an open mind and be willing to accept that maybe you didn't invent the magical solution to the world's shadow volume problems. It would be wise to first implement your idea and see how it compares to standard shadow volumes, and then we'll see if it merits more interest. If all you want is people to clap you on the back and say "you're so smart for figuring this out even if it doesn't work," then yes, you are in the wrong forums. If what you want is realism and a good solid look at your method's potential, I think you're getting plenty of good advice here.

Implement the code, and do a scientific comparison. If it really is better, then congratulations to you. If you aren't willing to do a comparison, however, I see no reason why you should expect praise. The world rewards results, not good ideas.


[afterthought] Actually, with regards to my concave-objects observation, rotating around the object doesn't do you any good. As long as the light stays directly above the dent, there will always be more lit faces than unlit, regardless of viewing position. If you take the infinite integral of lit faces vs. unlit faces over the sphere of all possible viewing angles, you'd find that the ratio is > 1, that is there is always a larger number of lit faces to render than unlit. So your algorithm isn't always a gain.

It may be possible to improve on the algorithm by adaptively using traditional z-fail or your modified method; I think if you seriously want to explore this idea that an adaptive solution is the way to go. I have no idea off the top of my head how you might implement it, but that's your job to think of

[edited by - ApochPiQ on November 13, 2003 4:55:05 PM]

Share this post


Link to post
Share on other sites
Oke my weekend just started, Im in a happy mood, so i''ll confront the non-tech posts...

Looks like I first need to clearify why I''m posting in this forum:
I''m in this forum to find people who care to discuss a possible algorithmic improvement of the current standard shadow volume algo. In other words; I want to have a theoretical discussion about this.
If I would give stats (like: from 30 to 31 FPS), that would not end the algorithmic discussion, only start it.
Things dont have to be done to be proven they are possible! If I would drive my car at 200km/hour towards a concrete wall, without braking, do you think by car will sustains any damage?
I''m not talking about a -solution-, but only a simple -improvement- for certain cases.
I also dont have an open mind for remarks like "do it yourself". If I wanted to talk to myself about this, I would not have posted.
I''m not looking for rewards. Only want to discuss the algo.
I hope this clears that up. Sigh


One important thing: I said "rotate the CAMERA 360degrees", but that should of course be "rotate the LIGHT 360 deg.". Or otherwise the shadow volume doesnt change.

Share this post


Link to post
Share on other sites
quote:
Original post by duke
One comment:

It is not up to the "world" to prove you wrong, it is up to you to prove yourself right.




Looks like I''m not explaining myself clear enough. I''ll try again...

when a point-light-source is very close to an object, there are less faces facing the light, and more faces facing away from the lightsource. There are situations where this is not the case, but when you would position the light at all possible locations, in the AVERAGE case this would be true. And because we''re looking a speed increase in as many cases as possible, the average case is what we''re interrested in.

When you place a light very far from an object, the average ratio light:dark faces would near 50%:50%.
When you place this light at infinity, you get a directional lightsource, and the average ratio would be 50:50 for any object.
But I''m not talking about directional lightsources, but about point-light-sources.


Is there someone that understands when extruding light-facing-triangles only into infinity (when the light is inside an object), not the entire would would be shadowed?
If you understand why I''m wrong, plz try and explain it to me.


If this is not the place for theoretical discussions, I''ll shut up, excuse myself, and will move away to a forum that does welcome it, and I''ll never bother you again.

Share this post


Link to post
Share on other sites
I''ve checked the sources of the NVidia demo (http://developer.nvidia.com/object/fast_shadow_volumes.html)

Only thing that needs to be changed in the sources is:
BasicModel.cpp, line 574 & 575, replace with:


if(!m_isBackfaceArray[g]) { // take lighted faces instead of dark
for (int w = 2; w >= 0; w--) { // flip face


I cannot test it right now because I''m on 56K dial-up, and the G3D download is 26Mb But it should work.

Share this post


Link to post
Share on other sites
I''m still not convinced that in average you''ll gain anything. Ok, so there might be a bit more lit faces than unlit ones, but unless your scene is made of thousands of spheres, i believe in a "game scene" this ratio will be very close to 50%; maybe 51 or 52% of lit faces.

I''ll try to modify one of my demos this week end and see, by putting a point light in the very center of the scene, what the ratio actually is.

Y.

Share this post


Link to post
Share on other sites
If you don''t want to offer concrete evidence of your method''s power, then offer us theoretical evidence. If you really want to talk in terms of theory, then talk in terms of theory - let''s see the formula that proves you will have more than a marginal drop in faces rendered.

Share this post


Link to post
Share on other sites
Repeat concrete evidence...

quote:
Original post by baskuenen
I''ve checked the sources of the NVidia demo (http://developer.nvidia.com/object/fast_shadow_volumes.html)

Only thing that needs to be changed in the sources is:
BasicModel.cpp, line 574 & 575, replace with:


if(!m_isBackfaceArray[g]) { // take lighted faces instead of dark
for (int w = 2; w >= 0; w--) { // flip face




You probably wont get a huge incease in fps, because the demo suffers from slow fillrate (like all shadowvolume demos, with current hardware).
In any case, what you should be able to notice, is the effect described above, when a light is inside a shadowcasting object.


If I would setup a formula describing the lighted area on a sphere, I''d be waisting time, on something fairly obvious
I could even write a pages long formula for lighted areas on triangles meshes, but those formulas have been around for years, and are missing the point. The point is; setting the link between the average lighted surface...etc... and the shadow volume... ...and the vertexrate.

Share this post


Link to post
Share on other sites
I think you''re the one missing the point. None of us cares to test your pet theory to prove you right, and none of us cares to take the trouble to definitively prove you wrong. If you want a discussion, implement it yourself and give us something worth discussing.

Ideas are worth nothing. The ability to act on ideas is worth everything. That''s a very important part of the programming industry to learn, and you need to learn it.

Share this post


Link to post
Share on other sites
Speak for yourself. We''re not speaking of a game idea here, but an algorithm. I welcome any idea for new algorithms (or to improve others).

Bas, in order to test the performance improvement, i''d suggest disabling rendering of the shadow volumes, or testing with a very small window. That way you will no longer be fillrate limited.

Y.

Share this post


Link to post
Share on other sites
Sigh. Why am I still posting on this forum
I guess its the respect there was a few years ago.
Some tough-ass moderators are urgently needed here.
I''ll try and ignore the kiddies for now

So thx Ysaneya. Atleast you noticed this IS the Graphics Programming and Theory forum

I''ve counted the faces rendered, and it''s less.
I''ve chosen to drop performance testing, because its marginal anyway. On another forum someone proposed to count the light/dark faces, and project the set with least amount. This is even faster. But then we lose the extra we get from projecting lighted faces only.

The extra is:
when a light is inside a shadowcasting object,
and we project lighted faces inverted to infinity,
the world doesnt fall into complete darkness,
but the shadowcasting object casts none or only a partial shadow,
and the rest of the world remains in the light.

This is because when a light is inside the shadowcasting object,
there are no (or almost no) lighted faces. Just like there are no (or almost no) silhouette edges.

Share this post


Link to post
Share on other sites