Shadow Mapping

最近在学习games101

会记录一些自认为比较重要的知识

Shadow Mapping 的作用

Shadow Mapping的作用是为了实现物体被光线照射的时候会出现阴影的现象

点光源的阴影

将一个摄像机放在点光源那里，做一个光栅化，此时会得到光源会看到什么，并且记录下来深度图(shadow map)

再将自己屏幕所代表的摄像机进行观察，做光栅化，得到片段之后，将这个片段投影回点光源代表的摄像机，就可以知道这个片段在电光源摄像机的深度，通过和深度图进行比较之后，就可以知道这个点是不是在阴影之中

硬阴影和软阴影

硬阴影就是强光照射的时候，阴影和非阴影之间的过度等于没有，发生了突变

软阴影则是，阴影和非阴影之间有较为平滑的过度，并且越接近物体根部的地方阴影越硬，而越原理物体根部的地方阴影越软

软阴影相对于硬阴影比较真实且更为常见

如下图

软阴影.png

能完全看到光源的点没有阴影，看到部分光源的点是半阴影，而完全看不到光源的点则是阴影，这就是软阴影的原因

所以点光源不会产生软阴影，如果产生了软阴影，一定说明这个光源有一定的大小

图形学之变换

最近在学习Games101的计算机图形学的课：Games101

学习过程中的知识会进行一些记录

2D变换

在图形学中可以将矩阵和2D变换联系起来

缩放

缩放变换有一个缩放矩阵：

[sx00sy]\begin{bmatrix} s_x & 0 \\ 0 & s_y \\ \end{bmatrix}

其中的sxs_x和sys_y是缩放的系数

下面是缩放矩阵的应用

缩放.png

反射

反射矩阵为：

[−1001]\begin{bmatrix} -1 & 0 \\ 0 & 1 \\ \end{bmatrix}

这个矩阵是关于y轴反射

反射矩阵的应用：

反射.png

切变

切变矩阵为：

[1a01]\begin{bmatrix} 1 & a \\ 0 & 1 \\ \end{bmatrix}

切变矩阵的应用：

切变.png

旋转

在讨论旋转的时候默认认为是原点、逆时针旋转

旋转矩阵为：

Rθ=[cosθ−sinθsinθcosθ]R_\theta = \begin{bmatrix} cos\theta & -sin\theta \\ sin\theta & cos\theta \\ \end{bmatrix}

旋转矩阵的应用：

旋转.png

线性变换

线性变换式子如下

[x′y′]=[abcd][xy]\begin{bmatrix} x^{'} \\ y^{'} \\ \end{bmatrix} = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix}

以上讨论的缩放、切变、旋转、反射都属于线性变换

齐次坐标

在各种变换之中，平移变换是比较特殊的，下面是平移变换的公式

[x′y′]=[abcd][xy]+[txty]\begin{bmatrix} x^{'} \\ y^{'} \\ \end{bmatrix} = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} + \begin{bmatrix} t_x \\ t_y \\ \end{bmatrix}

可以看出，平移的公式不属于线性变换

为了将平移也加入到一个统一的变换矩阵中，引入了齐次坐标的概念

将2D的点表示为(x, y, 1)
将2D的向量表示为(x, y, 0)

这样的话就有非常好的性质：
点-点=向量
向量+向量=向量
点+向量=点
点+点=两个点的中点

定义了：

[xyw]就相当于2D的一个点[xwyw1](w≠0)\begin{bmatrix} x \\ y \\ w \\ \end{bmatrix} 就相当于2D的一个点 \begin{bmatrix} \frac{x}{w} \\ \frac{y}{w} \\ 1 \\ \end{bmatrix}(w\neq0)

平移矩阵

[x′y′1]=[10tx01ty001][xy1]=[x+txy+ty1]\begin{bmatrix} x^{'} \\ y^{'} \\ 1 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ 1\\ \end{bmatrix} = \begin{bmatrix} x + t_x \\ y + t_y \\ 1 \\ \end{bmatrix}

仿射变换

仿射变换就相当于一个图形先进行线性变换再进行平移变换

齐次坐标的仿射变换矩阵

[x′y′1]=[abtxcdty001][xy1]\begin{bmatrix} x^{'} \\ y^{'} \\ 1 \\ \end{bmatrix} = \begin{bmatrix} a & b & t_x \\ c & d & t_y \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ 1\\ \end{bmatrix}

将线性变换带入即可

三维变换

三维变换和二维类似

3D点 = (x, y, z, 1)
3D向量 = (x, y, z ,0)

仿射变换矩阵

[x′y′z′1]=[abctxdeftyghitz0001][xyz1]\begin{bmatrix} x^{'} \\ y^{'} \\ z^{'} \\ 1 \\ \end{bmatrix} = \begin{bmatrix} a & b & c & t_x \\ d & e & f & t_y \\ g & h & i & t_z \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ z\\ 1\\ \end{bmatrix}

STL的空间配置器

最近在阅读《STL源码剖析》这本书，会将自己觉得比较有意思的东西写在博客中

这本书中最先介绍的就是空间配置器的使用，在SGI STL中，分为两级的空间配置器，下面依次介绍这两种空间配置器是如何进行STL的内存管理的

配置器的总体介绍

SGI STL使用的是malloc()和free()函数来进行内存分配和释放的，考虑到小型区块可能造成的内存破碎的问题，SGI设计了双层的空间配置器。第一级配置器直接使用malloc()和free()，比较简单，第二级配置器则采用了内存池的技术，来减少内存的破碎。

当然没看过这本书的人可能会疑惑，到底什么是空间配置器？这里可以稍微下个定义，你可以认为空间配置器(allocator)是每个容器底层的一个对象，里面包含了一堆函数，用于给容器来分配内存空间。

第一级空间配置器

第一级空间配置器较为简单，使用malloc(),free(),realloc()等C函数执行实际的内存配置、释放、重配置操作

第二级空间配置器

第二级配置器多了一些机制，用于避免太多小额区块造成的内存碎片，由于一块内存中包含有两部分：用于记录内存大小的cookie、内存，如果申请的内存过小，那么这个cookie相对来说占的比重会更大，从而造成不必要的浪费。

SGI第二级配置器的做法是，如果申请的内存区块够大（超过128字节），就直接移交给第一级配置器来处理，如果区块小于128字节，就用内存池（memory pool）来进行管理。

第二级配置器在申请内存的时候，会直接申请一大块内存，并用十六个自由链表(free-list)来维护这一块内存。下次需要申请内存的时候，就直接冲free-lists中挑出一块内存来使用，如果客端想要归还内存，配置器就会将这块内存回收到free-lists之中。

为了方便管理，SGI第二级配置器会将任何小额区块的内存上调至8的倍数，维护16个free-list，大小分别为8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128字节。free-lists的节点结构如下：

1
2
3
4
union obj{
    union obj * free_list_link;
    char client_data[1];
};

关于free-lists的解释

节点是union的结构，结构中free_list_link和client_data[1]公用一块内存，这是为了节省内存，当该节点的内存并没有被使用的时候，结构中存储的是指向下一个节点的地址，当该节点的内存被使用的时候，存储的即是内存的地址。这样就不用在节点中开两个地址的变量，从而节约了内存。

关于空间配置函数allocate()

在网上找到的关于这个函数的解释都十分的不清楚，这里给出代码的合理解释

首先需要注意的是，有许多个8个字节大小的内存空间，所有的8字节大小的内存空间都由一个链表管理，之后的许多个16个字节大小的内存空间、24个字节大小的内存空间也和这个类似，每种大小的内存空间都由一个链表来进行管理，所以说一共有16个free-list。

以96个字节大小的内存空间为例子，二级空间配置器中由一个数组free_list[16]，这个数组的每一个元素，存储一个内存空间的地址，这个地址指向的就是96字节大小的free-list的第一个结点，而这个节点世界上就是一个内存空间，只是这个内存空间的前面四个字节，存储的是指向下一个节点的地址。如果要取出这块内存空间，需要将free_list[11]这个元素更新成下一个节点的地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void * allocate(size_t n)
{
    obj * __VOLATILE * my_free_list;
    obj * __RESTRICT result;
    
    // 如果大于__MAX_BYTES就调用第一级配置器
    if (n > (size_t) __MAX_BYTES) {
        return (malloc_alloc::allocate(n));
    }

    // 找到free_list[11]（96字节大小）这个元素的地址，这个元素的内容也是一个地址，指的是一个内存空间
    my_free_list = free_list + FREELIST_INDEX(n);

    // 这里是取出了这块内存
    result = *my_free_list;
    if (result == 0) {
        void *r = refill(ROUND_UP(n));
        return r;
    }

    // 将free_list[11]的值改为下一个96字节大小的内存空间的地址
    *my_free_list = result -> free_list_link;
    return (result);
};