正文
前面有提到过之前做的Software Renderer是不包含裁剪的，因为裁剪的过程比较繁琐，无论是2D的还是3D的都有可能涉及。这次整理后的Software Renderer是要包含裁剪的过程的，因此这里就管线中的裁剪做一次说明。
3D空间下的三角形裁剪与剔除
背面剔除（背面消隐）
这个方法是最为简单有效的三角形剔除方法之一了：只需要知道三角形的法线朝向N以及相机的朝向L即可——只有当三角形是朝向观察者的时候，观察者才能看到它，否则三角形是不可见的，也就不会被绘制。
已知向量点乘结果的符号是向量投影的方向，那么点乘结果为负的两个向量，它们相互的投影必然是方向相反的。这个性质可以用来判定三角形可见与否：当Dot(N, L)的结果为负的时候，三角形朝向观察者，可以绘制；否则不予绘制。这样就完成了背面剔除。
至于三角形的法线方向是如何得到的，一般而言，我们以坐标系的标准环绕方向来计算。在本Software Renderer中是按照左手系，也就是顺时针方向为准。
视锥体裁剪/剔除
在前面介绍图形管线中的矩阵的时候有提到透视变换，透视变换实际上就是将一个3D空间中的视锥体规整为一个方体的过程。在这个过程中我们可以看到实际上我们最终在投影平面上看到场景的就是视锥体中包含的场景，那么很自然地，我们希望能够通过这个视锥体对3D空间中的物体进行剔除以及裁剪，以减小对管线的压力。
除上述目的外，视锥体裁剪的一个很重要的作用就是对穿过近裁剪平面的三角形进行裁剪，否则，这下在裁剪平面后端的点将会在投影之后产生一个小于0的深度值，从而影响深度排序的结果，造成错误的绘制（绘制一些不应该看到的东西）；远裁剪平面则可以选择不去裁剪，这并不影响投影结果，对于超过远裁剪平面的点，将会在投影后得到一个大于1.0的深度值。
这里简单提一下基于画家算法的深度排序：光栅化的过程中我们需要对投影屏幕上的每一个像素进行深度值的排序，以便距离视平面近的点能够覆盖掉视平面较远的的点。这可以采用两种方法来解决问题：第一：直接使用像素的Z值，很显然，Z值越大，表示距离越远；第二，使用像素的1/Z值，那么1/Z越小，表示越远。当前我们不去深究这个问题，只需要保有这个概念即可，后面的文章会谈到。
平面与三角形
平面在本Software Renderer中是采用的法线——距离的形式定义的，法线自然指平面的单位法向量，而距离则是指平面距离远点的距离，从而我们可以通过一个点乘计算来判断空间中一个点与平面之间的关系：1
2
3// 3D Plane ==> { N = [Px, Py, Pz] , d }
// 3D vertex ==> { [ V = (Vx, Vy, Vz) ] }
float result = Dot(N, V) + d
通过判断上面result与0之间的关系可以得到：result = 0，则说明点在平面上，result > 0，则说明点在平面前面，否则点在平面后面。
上面的的图片可以用来说明三角形裁剪的过程，这张图片的视角是贴着3D平面看过去的。让我们从点A开始，沿着顺时针方向来说明裁剪过程。
三角形的边AB与平面相交，这可以得到一个交点E；边BC不与平面相交，无交点；边CA与平面相交，得到另一个交点D；回到点A完成交点的计算过程。
几乎没什么难度是不是么？稍微麻烦一点的也就是要计算交点的纹理坐标、法向量、颜色之类的属性，但这都可以通过线性插值来完成——由于这是在3D空间中线性插值，因此不会产生任何不良影响（2D空间中插值产生的影响将会在后面透视纹理以及深度缓存部分说明）。
上面的过程推广到普通多边形就是Weiler-Atherton算法。经过上面的过程，我们可以讲一个三角形分为两个部分：ADE和CDEB。注意图中的虚线CE，如此将三角形分为三个新的三角形：DAE，CDE和EBC。
BSP(Binary Space Partition, 二元空间划分)
有了上面的平面与三角形的剪切过程，接下来我们就可以进入到另外一种绘制方式的介绍了——虽然这个方式只限于在静态场景之中使用，然而它的效益则是十分巨大的——它可以让我们抛弃Z缓存，但是同样能够得到正确的完美的绘制结果。这便是大名鼎鼎的BSP，二元空间划分。虽然在本Software Renderer中不准备去实现BSP，但是为了以后考虑，还是介绍一下吧。
至于Z缓存的具体情形将会在下一篇文章中进行介绍，届时将会看到Z缓存带来的好处以及相应的代价，这个代价说大不大说小不小，足以让DX与OpenGL的管线将其与Alpha混合、光照以及纹理采样平级，并设置一个状态开关来控制是否需要启用它。
借用《Michael Abrash’s Graphics Programming Black Book trees》, Chapter 59: The idea of BSP中的几张图，这些图是在2D情况下的BSP模拟，3D下的过程与之一致，以此为基础可以较为容易地理解3D情况。
创建
图中的实线段代表实际的多边形，虚线代表多边形所在的平面，箭头指向代表平面的法向量方向。途中左边是一个场景实例，右边就是该场景对应的BSP树。
可以看到BSP树实际上就是一个二叉树。一个节点的左右子树分别代表了它前后空间的多边形集合。回忆画家算法，它实际上要求我们在绘制场景的时候先绘制较远的多边形，然后绘制近处的多边形，使用了深度缓冲的画家算法实际上是将绘制的粒度细化到一个像素——而在多边形没有相交的情形下，以多边形为粒度的画家算法同样能正常工作，BSP就是利用了这一事实。
BSP树的创建过程实际上就是利用静态场景中的多边形来对场景进行自我划分的。例如图中的A和E是被B所在的平面分割后的结果。
在创建BSP的时候，一个要点就是尽量使得每次分割的节点将自己所在的“子空间”中的多边形平分两堆，使得最后得到的的BSP树尽量保持平衡（Balanced Binary Tree），以提高效率。由于BSP树适用于静态场景，那么也就意味着这个步骤可以离线进行，从而不至影响实时渲染的速率。常用的方式是对当前划分步骤中的所有多变形进行遍历并进行评估，最后选取评估结果最好的多边形所在的平面做划分平面进行场景分割。
遍历
假定相机位置位于图中的眼睛位置。
通过观察我们可以知道正确的多边形绘制顺序应为：A, E-> B -> C -> D，回顾上面的BSP树的形态，我们会发现这这个顺序正好与二叉树的“先右子树再左子树最后父节点”的后序遍历顺序相同。
当然这并不能完全避免像素重绘，事实上只要是以多边形为单位的绘制过程都不能完全避免像素重绘——绘制粒度太大了。BSP+扫描线渲染则可以完全避免重绘，这里不予介绍，详细情形可参见《3D游戏编程大师技巧》第13章。
由于BSP属于空间划分算法，而空间划分算法的一个重要作用就是将当前无用大部分多边形信息从流水线中剔除，因此BSP树结合视锥体剔除可以极大改善对静态场景的绘制效率。
一个简单的策略就是对于视点之后的空间直接完全剔除：注意这里的“视点之后”意指：划分平面与视向量垂直，该策略完全不考虑空间包围体，如图：
上面的策略不够完整，完整的剔除策略应当引入包围体：当一个子树的包围体完全被视锥体检测拒绝的时候，该子树可被完全剔除。
BSP的介绍就先到这里，不过既然开了剔除这个话题，那么下面再介绍几种常用方法来说明可见性集合的选择策略。BSP策略是针对静态场景，那么接下来将要介绍的策略不但适用于静态场景，也适用于动态场景。
四叉树（Quad-Tree）与八叉树（Oct-Tree）
四叉树与八叉树可以放在一起进行说明，他们只是维度数目上不不同而已——八叉树比四叉树多了一个维度。这里只对四叉树进行说明，八叉树可以由四叉树扩展得到。
上图中的黑色边框为第一层的子节点，红色划分得到的是第二层子节点，紫色划分的为第三层子节点；蓝色的两条线是视景范围，点A是视点位置。图中没有标识出远近裁剪面，不过这不影响我们的理解。
我们在创建四叉树的时候，每创建一个层级的节点，就要对应创建该节点对应的包围体（AABB或者OBB），每一个层级都将上一个层级分为四个子部分，这四个子部分的并集应当完全“覆盖”它对应的上层节点（图中是均分的，实际应用可用采用其他策略）；递归进行这一过程，直到达到一个预定的阈值结束递归。
在进行剔除的时候，我们需要遍历整个树，对每个节点的包围体进行视锥体检测。完全在视景体外部的节点及其对应的子树将会被剔除，例如图中的白色部分；完全在视景体内部的节点则可以直接将其包含的渲染对象组织给渲染列表；相交的节点进一步递归进行上面的过程（图中棕色的部分）。
八叉树的剔除过程与四叉树极为类似，不再赘述。
K-D树
K-D树，也就是多维树（K-dimension tree）。一般作为数据库数据的一种组织方式，实际上它是二叉树的一种形式，只不过在树的层次上附加了根据属性剔除的意义。在某种程度上，BSP树也可以视作K-D树的一种形式（非轴对齐，而是平面对齐）。我们这里说明的是轴对齐的K-D树。
图中所示就是轴对齐K-D树的结构——每一层都是上面一层在另一个轴上的划分，于是每次剔除都可以完全剔除当前的半个空间。
入口（Portal）
上图说明了Portal的工作过程：最初的视景体F1经过入口P1得到新的视景体F2，F2经过P2和P3得到F3和F4……这是一个递归的过程，该过程中最重要的部分是新的视景体的生成。
入口需要每一帧都需要重新进行计算，最终使用生成的一系列的视景体来对场景进行剔除。
遮挡剔除
遮挡剔除主要是为了消除一部分的重复绘制——在标准的3D绘制流程中，我们是由远及近对多边形进行绘制。设想两个物体，A距离投影平面的距离大于B，也就是A距离视距较远；并且投影之后A会被B完全覆盖掉，也就是视野中只能看到B。
在上面的情况下，采取由远及近的绘制方式会导致A一定被绘制一遍，而实际上我们只需要绘制B即可，此时便可以采用遮挡剔除来避免对A的绘制了。
遮挡剔除的一个关键是要处理好物体相应的遮挡关系——一般是以一个内接体和一个外接体来实现，通过求出遮挡体在投影之后的相互遮挡关系就可以了，或者对此类情况直接采用从前到后的绘制方式绘制（这种方式只是在光栅化部分消除了像素的重绘，但是坐标变换还是要做的）。
结语
3D空间中常用的剔除方式基本算是介绍完毕了，上面那些策略的理论基础都还是比较容易的，然而实际处理中就要考虑诸多情况了。由于个人经历以及能力所限，本人不能对这些策略结合实际应用做进一步的介绍，不能不说是一个遗憾（只是实现过松散OctTree）。这篇文章先将这些方法简要整理一下，以后有机会的话会对其中某一个话题进行进一步的探讨。