Jump to content
  • Advertisement
Sign in to follow this  
Geometrian

Efficiently Extruding Shadow Volumes

This topic is 2677 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
Advertisement
I think unordered_map would actually be more similar to the python dictionary.
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

In C++, there is std::map. Also, you most likely will want to do the extrusion in a vertex shader.


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
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.
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 here.

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

-G

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!