Thread: [Algorithms] Silhouette determination for the world's shadow volume
Brought to you by:
vexxed72
From: Damian C. <Dam...@m8...> - 2010-04-18 20:13:08
|
Morning, WRT shadow volumes, what's a common approach for determining the silhouette for the world mesh? Let's say it's an indoor only game. In this case the camera and lights are both "inside" the world mesh, and the world mesh is concave. For the other meshes that move around inside the world, silhouette determination is well documented - "The set of all edges that connect a toward-face to an away-face form the silhouette with respect to the light source. The edges forming the silhouette are extruded away from the light to construct the faces of the shadow volume". What about the world mesh though? My initial thoughts are to use all world mesh polygons that don't face the light source, and create individual shadow volumes for each polygon. This would get costly if the world mesh had many back facing polygons at any given time. How else is it done? ~Damian(); |
From: Jeff R. <je...@8m...> - 2010-04-18 21:19:01
|
Well, the shadow volume mesh topology rules really aren't any different for light sources inside a mesh vs outside - as long as your geometry faces inwards (and it will), the idea is the same (find and extrude edges that border lit & unlit faces). Sometimes world geometry is stored in funny ways depending on your game/engine (BSP trees or what have you), that might make finding edges trickier, but the algorithm is the same. A good optimization for fill rate if you are using local light sources is to make sure and only extrude shadow volumes for the areas of the world that intersect the light's attenuation radius. Jeff On Sun, Apr 18, 2010 at 3:12 PM, Damian Coventry < Dam...@m8...> wrote: > Morning, > > WRT shadow volumes, what's a common approach for determining the > silhouette for the world mesh? Let's say it's an indoor only game. In > this case the camera and lights are both "inside" the world mesh, and > the world mesh is concave. > > For the other meshes that move around inside the world, silhouette > determination is well documented - "The set of all edges that connect a > toward-face to an away-face form the silhouette with respect to the > light source. The edges forming the silhouette are extruded away from > the light to construct the faces of the shadow volume". > > What about the world mesh though? My initial thoughts are to use all > world mesh polygons that don't face the light source, and create > individual shadow volumes for each polygon. This would get costly if > the world mesh had many back facing polygons at any given time. How > else is it done? > > > ~Damian(); > > > > ------------------------------------------------------------------------------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > -- Jeff Russell Engineer, 8monkey Labs www.8monkeylabs.com |
From: Damian C. <Dam...@m8...> - 2010-04-18 21:46:14
|
Yup, some sort of "potentially shadowed set" scheme will have to be in place, as well as 2D scissoring in view space before constructing the volume. If the idea is the same for the world mesh, then how would one build the near and far caps for the shadow volume in order to make it a closed volume? The world is essentially self shadowing itself, so I guess you'd only need to cap far end of the volume, and ignore the near end. You'd have to cap it, otherwise you'd have holes in your shadows. Would one project every polygon in the potentially shadowed set to infinity? Or is there some other commonly used scheme to cap the far end of the volume? Damian Coventry Senior Software Developer M86 Security T: +64 9 984 5725 F: +64 9 984 5720 M: +64 21 539 839 From: Jeff Russell [mailto:je...@8m...] Sent: Monday, 19 April 2010 9:19 a.m. To: Game Development Algorithms Subject: Re: [Algorithms] Silhouette determination for the world's shadowvolume Well, the shadow volume mesh topology rules really aren't any different for light sources inside a mesh vs outside - as long as your geometry faces inwards (and it will), the idea is the same (find and extrude edges that border lit & unlit faces). Sometimes world geometry is stored in funny ways depending on your game/engine (BSP trees or what have you), that might make finding edges trickier, but the algorithm is the same. A good optimization for fill rate if you are using local light sources is to make sure and only extrude shadow volumes for the areas of the world that intersect the light's attenuation radius. Jeff On Sun, Apr 18, 2010 at 3:12 PM, Damian Coventry <Dam...@m8...> wrote: Morning, WRT shadow volumes, what's a common approach for determining the silhouette for the world mesh? Let's say it's an indoor only game. In this case the camera and lights are both "inside" the world mesh, and the world mesh is concave. For the other meshes that move around inside the world, silhouette determination is well documented - "The set of all edges that connect a toward-face to an away-face form the silhouette with respect to the light source. The edges forming the silhouette are extruded away from the light to construct the faces of the shadow volume". What about the world mesh though? My initial thoughts are to use all world mesh polygons that don't face the light source, and create individual shadow volumes for each polygon. This would get costly if the world mesh had many back facing polygons at any given time. How else is it done? ~Damian(); ------------------------------------------------------------------------ ------ Download Intel® Parallel Studio Eval Try the new software tools for yourself. Speed compiling, find bugs proactively, and fine-tune applications for parallel performance. See why Intel Parallel Studio got high marks during beta. http://p.sf.net/sfu/intel-sw-dev _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t -- Jeff Russell Engineer, 8monkey Labs www.8monkeylabs.com |
From: Matt J <mjo...@gm...> - 2010-04-18 21:59:17
|
A lot seem to forget finding edges on the CPU is 'optional'...and time consuming. So you have two options here..you could do the edge finding using a geometry shader. Another approach that works on earlier hardware is have a shadow mesh, simplified, and independent of the primary mesh. You can duplicate each edge (with opposite winding, and connected as quad to the first edge) except store the coordinates of the extra edge with a 0 w coordinate... and then all you have to do in the vertex shader is extrude out the edge with 0 w coordinate to infinity. At the cost of extra geometry (which can be simplified independently), you keep the processing on the GPU. This works fine as long as the geometry is solid. It doesn't need to be convex, nor really solid either (although you really want too, to avoid artifacts). You're extruding it as a preprocessing step, at the expense of greater geometry. However, you can use a simplified mesh so you just keep the core 'features' of the mesh, e.g. you can use a few AABB to represent a building mesh.Finally, you can hide the shadow artifacts on the backside using reverse extrusion. With modern shadow algorithms though you are going to get much nicer shadows using a shadow buffer. Thanks, Matthew Well, the shadow volume mesh topology rules really aren't any different for > light sources inside a mesh vs outside - as long as your geometry faces > inwards (and it will), the idea is the same (find and extrude edges that > border lit & unlit faces). Sometimes world geometry is stored in funny ways > depending on your game/engine (BSP trees or what have you), that might make > finding edges trickier, but the algorithm is the same. > > A good optimization for fill rate if you are using local light sources is > to make sure and only extrude shadow volumes for the areas of the world that > intersect the light's attenuation radius. > > Jeff > > > On Sun, Apr 18, 2010 at 3:12 PM, Damian Coventry < > Dam...@m8...> wrote: > >> Morning, >> >> WRT shadow volumes, what's a common approach for determining the >> silhouette for the world mesh? Let's say it's an indoor only game. In >> this case the camera and lights are both "inside" the world mesh, and >> the world mesh is concave. >> >> For the other meshes that move around inside the world, silhouette >> determination is well documented - "The set of all edges that connect a >> toward-face to an away-face form the silhouette with respect to the >> light source. The edges forming the silhouette are extruded away from >> the light to construct the faces of the shadow volume". >> >> What about the world mesh though? My initial thoughts are to use all >> world mesh polygons that don't face the light source, and create >> individual shadow volumes for each polygon. This would get costly if >> the world mesh had many back facing polygons at any given time. How >> else is it done? >> >> >> ~Damian(); >> >> >> >> ------------------------------------------------------------------------------ >> Download Intel® Parallel Studio Eval >> Try the new software tools for yourself. Speed compiling, find bugs >> proactively, and fine-tune applications for parallel performance. >> See why Intel Parallel Studio got high marks during beta. >> http://p.sf.net/sfu/intel-sw-dev >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDA...@li... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >> > > > > -- > Jeff Russell > Engineer, 8monkey Labs > www.8monkeylabs.com > > > ------------------------------------------------------------------------------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > -- ----- Matt Johnson http://otowngraphics.blogspot.com |
From: <der...@he...> - 2010-04-18 23:23:24
|
Remember also that the shadow volumes for static world geometry vs fixed-position lights are also static and can be created off-line. The static volumes need to be extruded a distance based on the maximum run-time intensity of the fixed position light sources. If fill rate proves to be a bottleneck then the CC shadow volumes paper (http://gamma.cs.unc.edu/CCSV/) would be worth a look. I've never tried to implement the algorithm but it promises impressive reductions in fill rate. Cheers Derek > Well, the shadow volume mesh topology rules really aren't any different > for > light sources inside a mesh vs outside - as long as your geometry faces > inwards (and it will), the idea is the same (find and extrude edges that > border lit & unlit faces). Sometimes world geometry is stored in funny > ways > depending on your game/engine (BSP trees or what have you), that might > make > finding edges trickier, but the algorithm is the same. > > A good optimization for fill rate if you are using local light sources is > to > make sure and only extrude shadow volumes for the areas of the world that > intersect the light's attenuation radius. > > Jeff > > On Sun, Apr 18, 2010 at 3:12 PM, Damian Coventry < > Dam...@m8...> wrote: > >> Morning, >> >> WRT shadow volumes, what's a common approach for determining the >> silhouette for the world mesh? Let's say it's an indoor only game. In >> this case the camera and lights are both "inside" the world mesh, and >> the world mesh is concave. >> >> For the other meshes that move around inside the world, silhouette >> determination is well documented - "The set of all edges that connect a >> toward-face to an away-face form the silhouette with respect to the >> light source. The edges forming the silhouette are extruded away from >> the light to construct the faces of the shadow volume". >> >> What about the world mesh though? My initial thoughts are to use all >> world mesh polygons that don't face the light source, and create >> individual shadow volumes for each polygon. This would get costly if >> the world mesh had many back facing polygons at any given time. How >> else is it done? >> >> >> ~Damian(); >> >> >> >> ------------------------------------------------------------------------------ >> Download Intel® Parallel Studio Eval >> Try the new software tools for yourself. Speed compiling, find bugs >> proactively, and fine-tune applications for parallel performance. >> See why Intel Parallel Studio got high marks during beta. >> http://p.sf.net/sfu/intel-sw-dev >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDA...@li... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >> > > > > -- > Jeff Russell > Engineer, 8monkey Labs > www.8monkeylabs.com > ------------------------------------------------------------------------------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev_______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |