Soft Shadow Maps: Efficient Sampling of Light Source Visibility

Shadows, particularly soft shadows, play an important role in the visual perception of a scene by providing visual cues about the shape and position of objects. Several recent algorithms produce soft shadows at interactive rates, but they do not scale well with the number of polygons in the scene or only compute the outer penumbra. In this paper, we present a new algorithm for computing interactive soft shadows on the GPU. Our new approach provides both inner‐ and outer‐penumbra for a modest computational cost, providing interactive frame‐rates for models with hundreds of thousands of polygons. Our technique is based on a sampled image of the occluders, as in shadow map techniques. These shadow samples are used in a novel manner, computing their effect on a second projective shadow texture using fragment programs. In essence, the fraction of the light source area hidden by each sample is accumulated at each texel position of this Soft Shadow Map. We include an extensive study of the approximations caused by our algorithm, as well as its computational costs.     

融合阴影图和深度划分阴影体的阴影渲染算法

阴影图算法可以简单、快速地渲染硬阴影,但该算法渲染的硬阴影会在边缘区域出现锯齿状走样。受此影响,基于阴影图算法渲染的柔和阴影,在小尺寸半影区域依然可能会出现锯齿状走样。因此,要渲染无走样的柔和阴影,需要精确计算阴影边缘区域的着色点对点光源的可见性。深度划分阴影体算法可以精确地计算着色点对点光源的可见性,但其不仅在效率上不及阴影图算法,还无法实现柔和阴影渲染。针对上述问题,提出一种融合阴影图和深度划分阴影体的阴影渲染算法,对处于阴影边缘区域的着色点,使用深度划分阴影体算法精确计算该着色点对点光源的可见性;对其他着色点,使用阴影图算法快速计算该着色点对点光源的可见性。最后,将着色点的可见性值存储在可见性图中并滤波即可实现无走样柔和阴影的渲染。     

基于BSP树的启发式阴影生成算法

阴影的生成在虚拟现实领域一直是个难题,特别是针对动态光源的大规模场景,目前还没有较成熟的阴影算法。通过对现有阴影生成算法和场景组织算法的研究,该文提出了基于二维空间分割树(BSP树)的启发式阴影生成算法:首先创建场景BSP树,随着观察者视点的改变,选取视剪裁体内的节点创建以光源为视点的遮挡体BSP树,然后通过对该BSP树的遍历拣选出阴影启发区内的物体,经过处理后BSP树只留下一些生成阴影必要的多边形大大减少了计算量,最后能够快速生成阴影。     

利用反向投影实现的实时软阴影映射算法

基于阴影映射算法,提出一种利用反向投影实现的实时软阴影的新算法。算法对每个光源都产生对应的阴影图,使用阴影图作为对场景的离散化表示,引入可见因子来计算场景点的亮度信息,并采用GPU片元着色、层次阴影图、自适应精度等方法加速阴影渲染。实验表明,算法非常适合于实时渲染复杂、动态的场景,可以很好地处理遮挡物的融合,并且很容易在可编程图形硬件上实现。     

平面投射多分辨率软阴影绘制算法

阴影生成技术在计算机真实感图形应用中发挥着独特而重要的作用。基于模板缓存技术、图像融合技术及反走样技术等,提出一种多分辨率多平面投射软阴影绘制方法。该方法首先通过在光源上进行离散采样,获得一组硬阴影绘制图像;再通过颜色混合和模板缓存技术对这组图像进行平均化处理,合成得到软阴影图像;最后利用累加缓存对场景进行反走样处理,使软阴影绘制效果更加自然、柔和。该方法提供了绘制精度的参数控制手段,使用户可以交互地设定生成软阴影的分辨率。     

Conflict Neutralization on Binary Space Partitioning

The Binary Space Partitioning (BSP) tree achieves fast hidden surface removal for most practical applications where an observer can move through a scene of static objects. However, the BSP algorithm generally increases the number of polygons in a scene due to its splitting stage resulting in a detrimental effect on the priority ordering and more significantly, the display calculations (shading, lighting, shadows, etc.) of the rendering pipeline.
We present the Conflict Neutralization algorithm which attempts to reduce the number of splits more effectively than existing techniques whilst maintaining the 'standard' model of a BSP tree. Our idea is similar to Conflict Minimization proposed by Fuchs; the significant difference is that our algorithm recognizes that a polygon suitable for selection in the Minimization criterion may subsequently stop the remainder of polygons achieving some reductions in cuts—with Conflict Neutralization, such a polygon is demoted.
We compare the results of Conflict Neutralization against Conflict Minimization, the Least-crossed with Most-crossed tie-breaking criterion and our own, enhanced implementation of Conflict Minimization. We show how these techniques fall into different 'depths of analysis'.     

A General Version of Crow's Shadow Volumes

In 1977 Frank Crow introduced a new class of algorithm for the generation of shadows. His technique, based on the concept of shadow volumes, assumes a polygonal database and a constrained environment. For example, polyhedrons must be closed, and polygons must be planar. This article presents a new version of Crow's algorithm, developed at the Universite de Montreal, which attempts a less constrained environment. The method has allowed the handling of both open and closed models and nonplanar polygons with the viewpoint anywhere, including any shadow volume. It does not, however, sacrifice the essential features of Crow's original version: penetration between polygons is allowed and any number of light sources can be defined anywhere in 3D space, including the view volume and any shadow volume. The method has been used successfully in the film Tony de Peltrie and is easily incorporated into an existing scan-line, hidden-surface algorithm.     

Partitioned Shadow Volumes

Real‐time shadows remain a challenging problem in computer graphics. In this context, shadow algorithms generally rely either on shadow mapping or shadow volumes. This paper rediscovers an old class of algorithms that build a binary space partition over the shadow volumes. For almost 20 years, such methods have received little attention as they have been considered lacking of both robustness and efficiency. We show that these issues can be overcome, leading to a simple and robust shadow algorithm. Hence we demonstrate that this kind of approach can reach a high level of performance. Our algorithm uses a new partitioning strategy which avoids any polygon clipping. It relies on a Ternary Object Partitioning tree, a new data structure used to find if an image point is shadowed. Our method works on a triangle soup and its memory footprint is fixed. Our experiments show that it is efficient and robust, including for finely tessellated models.     

Shadow geometry maps for alias-free shadows

Shadow maps sample scene visibility in the light source space and offer an efficient solution to generate hard shadows.However,they suffer from aliasing artifacts because of discretization errors,inadequate resolution and projection distortion.In this paper,we propose the shadow geometry map method,where a shadow depth map is augmented by storing geometry information about scenes.This leads to a new shadowrendering algorithm that combines a supersampling filter,a geometry-aware reconstruction kernel and an irregular sampling filter.Our method produces high quality alias-free and subpixel supersampling shadow rendering and retains the simplicity and the efficiency of shadow maps.We show that the algorithm pipeline is efficiently parallelized using current programmable graphics hardware and that our method is capable of generating high quality hard shadows.     

双层SVM的阴影检测与基于窗口融合的阴影恢复

阴影的存在对于机器视觉的分析如区域的边缘提取,目标识别以及图像匹配等往往具有一定的干扰,而现如今提出的算法往往并不能很好地处理阴影区域的纹理和边缘。主要针对静态阴影图像提出了一种成对区域阴影检测和恢复的方法。阴影检测：通过提取阴影和非阴影区域之间边缘两侧颜色、纹理、方向和距离特征采用双层SVM训练器对阴影区域进行检测,不仅能检测出阴影区域,同时能够检测出与此阴影区域在同一表面的非阴影区域。阴影恢复：采用提出的自适应步长的窗口匹配方法获得阴影区域的采样窗口的最佳匹配窗口,采用窗口融合的方式初步恢复阴影区域,然后使用提出的迭代的方式对图像纹理进行增强,最后用快速修复方法（FMM）去除阴影与非阴影区域的微弱边缘。Opencv仿真证明,这样不仅可以提高阴影区域检测准确率,而且能够很好地保存纹理信息。     

A quadratic spline approximation using detail multi-layer for soft shadow generation in augmented reality

Implementation of shadows is crucial to enhancement of images in AR environments. Without shadows, virtual objects would look floating over the scene resulting in unrealistic rendering of AR environments. Casting hard shadows would provide only spatial information while soft shadows help improve realism of AR environments. Several algorithms have been proposed to render realistic shadows which often incurred high computational costs. Little attention has been directed towards the balanced trade-off between shadow quality and computational costs. In this study, two approaches are proposed: Quadratic Spline Interpolation (QSI) to soften the outline of the shadow and Detail Multi-Layer (DML) technique to optimize the volume of computations for the generation of soft shadows based on real light sources. QSI estimates boarder hard shadow samples while DML involves three main phases: real light sources estimation, soft shadow production and reduction of the complexity of 3-Dimensional objects’ shadows. To be more precise, a reflective hemisphere is used to capture real light and to create an environment map. The Median Cut algorithm is implemented to locate the direction of real light sources on the environment map. Subsequently, the original hard shadows are retrieved and a sample of multilayer hard shadows is produced where each layer has its unique size and colour. These layers overlap to produce soft shadows based on the real light sources’ directions. Finally, the Level of Details (LOD) algorithm is implemented to increase the efficiency of soft shadows by decreasing the complexity of vertex transformations. The proposed technique is tested using three samples of multilayer hard shadows with varying numbers of light sources generated from the Median Cut algorithm. The experimental results show that the proposed technique successfully produces realistic soft shadows at low computational costs.     

Compressed shadow maps

Shadow mapping has been subject to extensive investigation, but previous shadow map algorithms cannot usually generate high-quality shadows with a small memory footprint. In this paper, we present compressed shadow maps as a solution to this problem. A compressed shadow map reduces memory consumption by representing lit surfaces with endpoints of intermediate line segments as opposed to the conventional array-based pixel structures. Compressed shadow maps are only discretized in the vertical direction while the horizontal direction is represented by floating-point accuracy. The compression also helps with the shadow map self-shadowing problems. We compare our algorithm against all of the most popular shadow map algorithms and show, on average, order of magnitude improvements in storage requirements in our test scenes. The algorithm is simple to implement, can be added easily to existing software renderers, and lets us use graphics hardware for shadow visualization.     

Linear-Time Algorithms for Finding the Shadow Volumes from a Convex Area Light Source

An area light source in three-dimensional space shines past a scene polygon to generate two types of shadow volumes for each scene polygon, i.e., one with partial occlusion and the other with complete occlusion. These are called penumbra and umbra, respectively. In this paper we propose linear-time algorithms for computing the penumbra and the umbra of a scene polygon from an area light source, respectively. Received June 27, 1995; revised May 20, 1996.     

视频监控系统中运动目标检测的阴影去除方法

在分析了阴影产生的原因及视觉特性的基础上,针对固定场景的运动目标检测问题,提出了一种具有实际应用价值的阴影检测与去除方法。该方法通过背景建模和背景差分方法分割出运动目标及其可能存在的阴影,采用光照评估方法判断阴影是否存在,进而运用多梯度分析和二值图像的快速聚类算法检测出阴影,去除阴影并分割运动目标。实验验证了该方法的有效性。     

结合区域配对的室外阴影检测

目的 针对现有大多数阴影检测算法在检测细长阴影、自阴影、区分阴影与暗色像素等方面的不足,提出一种新的结合区域配对的阴影检测算法.方法 首先通过均值漂移算法和canny检测算法,分割图像得到每个独立的区域;然后从每个区域中提取纹理和亮度建立单个区域的阴影模型,再从区域对中提取纹理直方图的距离、颜色比(分别在RGB和Lab空间下)以及HSI空间下H和I两通道的比值等特征建立区域对的阴影模型;最后根据上述两个模型运用图割理论检测阴影.结果 实验结果表明,本文算法在阴影检测上的准确率高达85.2%,远高于其他算法,检测速度也比其他算法快34%左右.该算法不仅能有效地检测细长阴影和自阴影,还能较好地区分阴影与暗色像素.结论 提出了一种新的阴影检测算法,通过区域配对的方法实时处理单幅室外图像.实验结果表明,该算法在检测细长阴影、自阴影以及区分阴影与暗色像素等方面有良好的效果.     

Light Space Cascaded Shadow Maps Algorithm for Real Time Rendering

Owing to its generality and efficiency.Cascaded Shadow Maps(CSMs) has an important role in real-time shadow rendering in large scale and complex virtual environments.However,CSMs suffers from redundant rendering problem—objects are rendered undesirably to different shadow map textures when view direction and light direction are not perpendicular.In this paper,we present a light space cascaded shadow maps algorithm.The algorithm splits a scene into non-intersecting layers in light space,and generates one shadow map for each layer through irregular frustum clipping and scene organization,ensuring that any shadow sample point never appears in multiple shadow maps.A succinct shadow determination method is given to choose the optimal shadow map when rendering scenes.We also combine the algorithm with stable cascaded shadow maps and soft shadow algorithm to avoid shadow flicking and produce soft shadows.The results show that the algorithm effectively improves the efficiency and shadow quality of CSMs by avoiding redundant rendering. and can produce high-quality shadow rendering in large scale dynamic environments with real-time performance.     

格网划分的双策略跟踪多边形裁剪算法

论文提出了一种高效稳定的多边形裁剪算法,算法支持带内环的平面简单 多边形,同时也支持多边形的“并”和“差”等布尔运算。首先,设计了算法所需的数据结构; 其次,基于直线扫描转换Bresenham 算法原理提出了边网格划分的有效算法,并应用一个简 单的方法避免不同网格内边的重复求交;最后,将交点分类为普通交点和顶交点,并针对这 两类交点构造了不同的跟踪策略,在跟踪过程中交替、递归地应用这两个策略来确保算法处 理特殊情况时的稳定性。与其它同类算法的比较表明,新算法具有更高的效率。     

Rendering Soft Shadows using Multilayered Shadow Fins

Generating soft shadows in real time is difficult. Exact methods (such as ray tracing, and multiple light source simulation) are too slow, while approximate methods often overestimate the umbra regions. In this paper, we introduce a new algorithm based on the shadow map method to quickly and highly accurately render soft shadows produced by a light source. Our method builds inner and outer translucent fins on objects to represent the penumbra area inside and outside hard shadows, respectively. The fins are traced into multilayered light space maps to store illuminance adjustment to shadows. The viewing space illuminance buffer is then calculated using those maps. Finally, by blending illuminance and shading, a scene with highly accurate soft shadow effects is produced. Our method does not suffer from umbra overestimation. Physical relations between light, objects and shadows demonstrate the soundness of our approach.     

Concentric Spherical Representation for Omnidirectional Soft Shadow

Soft shadows play an important role in photo‐realistic rendering. Although there are many efficient soft shadow algorithms, most of them focus on the one‐side light source situation, where a planar light source is on the outside of the scene. In fact, in many situations, such as games, light sources are omnidirectional. They may be surrounded by a number of 3D objects. This paper proposes a soft shadow algorithm for the omnidirectional situation. We develop a concentric spherical representation to model the behaviour of omnidirectional light sources. To provide better rendering results, a novel summed area table based filtering scheme for spherical functions is proposed. In addition, we utilize unicube mapping, which samples the spherical space more uniformly, to further improve the filtering quality.     

基于Delaunay三角网的任意多边形三角剖分算法研究

文章通过分析现有多边形三角剖分算法,给出一种基于Delaunay三角网的任意复杂多边形三角剖分的改进算法。算法首先忽略多边形顶点与边线间的逻辑关系,将其看做散乱顶点的集合,然后采用Delaunay三角化方法对点集进行合理剖分,再依据多边形顶点及边线间的逻辑关系,逐一将那些不合理的三角网剔除,最终重新组合出符合要求的三角网格。