Sign in to follow this  

Efficiently Extruding Shadow Volumes

This topic is 2483 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

Hi,

So I'm recreating shadow volume extrusion in my new C++ engine. Currently, it's slower than my Python implementation, which was slow to begin with.

Basic algorithm:
1. Generate a list<edge> of all edges in the mesh (each edge is a class storing two GLuints, which are vertex indices)
2. For each element in the list, loop through the other elements and determine if they're duplicates (check if the vertex indices are equal). If none are found, then extrude edge and add it as a quad.

In practice, I've found that 2. takes longest. It's mostly iterating through the edges that's slowest; removing the extrusion entirely doesn't help the speed significantly.

I don't think a list is the best way to be doing this; in the Python version, there was a dictionary (hash map?), so the lookup was very fast to determine if an edge was already in the array.

What's the best C++ way to do this?

Thanks,
-G

Share this post


Link to post
Share on other sites
[quote name='Slavik81' timestamp='1298416653' post='4777749']I think unordered_map would actually be more similar to the python dictionary.[/quote]In any case, I will have to be very fast indeed. linked lists should be O(n) for accessing. The std::map documentation said O(log(n)), which doesn't sound terribly much faster (although for large n, it definitely makes a difference). Is there any faster data structure for this purpose?

Given unordered list of numbers, if there a pair of numbers, remove both of them.

Thanks!

Share this post


Link to post
Share on other sites
[quote name='EngineCoder' timestamp='1298317203' post='4777173']
In C++, there is std::map. Also, you most likely will want to do the extrusion in a vertex shader.
[/quote]

Can you provide a link, or an example, as I've only worked on the CPU Shadow Volumes so far. Preferably dx9 compliant, but I understand if this is another DX10+ only technique. I assume that in dx10 vertices could be passed to the geometry shader for extrusion, but I've yet to really look under the hood of the DX10/DX11 APIs.

Share this post


Link to post
Share on other sites
[quote name='Burnt_Fyr' timestamp='1298425919' post='4777797']Can you provide a link, or an example, as I've only worked on the CPU Shadow Volumes so far. Preferably dx9 compliant, but I understand if this is another DX10+ only technique. I assume that in dx10 vertices could be passed to the geometry shader for extrusion, but I've yet to really look under the hood of the DX10/DX11 APIs.[/quote]The basic idea is to pass degenerate polygons for every edge, and then extrude them from the light's position in the vertex shader. If geometry shaders are available, the edges can dynamically generate new quads, if they're marked as silhouette edges. See [url="http://http.developer.nvidia.com/GPUGems/gpugems_ch09.html"]here[/url].

My issue is simply finding which edges are silhouettes fast enough.

-G

Share this post


Link to post
Share on other sites

This topic is 2483 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this