3D渲染管线中的物体剔除

在执行背面消除之前，要先进行物体剔除（Object Removal）。
可以使用包围球测试来剔除物体，对每个物体，创建一个将其包围起来的球体，并判断球体是否位于视景体内。

通过找出离物体中心最远的顶点，可以算出该顶点与物体中心的距离，即为包围球的半径。
计算出包围球半径后，可以定义6个点，它们与球心的连线分别平行于±x轴，±y轴，±z轴，这些点定义了包围球。

先考虑2D的包围圆，下图是y=0y=0y=0平面的俯视图：

• p1是包围圆圆心，坐标为(x1,z1)(x_1,z_1)(x1​,z1​)
• p2是+z轴方向的最远端点，坐标为(x1,z1+r)(x_1,z_1+r)(x1​,z1​+r)
• p3是+z轴方向的最近端点，坐标为(x1,z1−r)(x_1,z_1-r)(x1​,z1​−r)
• p4是+x轴方向的最远端点，坐标为(x1+r,z1)(x_1+r,z_1)(x1​+r,z1​)
• p5是+x轴方向的最近端点，坐标为(x1−r,z1)(x_1-r,z_1)(x1​−r,z1​)

物体剔除原理：如果这些点都位于视景体外，则包围圆完全位于视景体外。
z轴方向的剔除条件：
(p2.z<far_z)∣∣(p3.z>near_z)(p2.z < far\_z) || (p3.z > near\_z)(p2.z<far_z)∣∣(p3.z>near_z)
即：(z1+r<far_z)∣∣(z1−r>near_z)(z_1+r < far\_z) || (z_1-r > near\_z)(z1​+r<far_z)∣∣(z1​−r>near_z)

x轴方向则需要通过平面方程和p4,p5两个端点的位置来判断。

根据上图可得，
视景体右平面的平面方程：x=w/2dzx=\frac{w/2}{d}zx=dw/2​z
视景体左平面的平面方程：x=−w/2dzx=-\frac{w/2}{d}zx=−dw/2​z
最终可得，
x轴方向的剔除条件：
(p5.x>w/2dp5.z)∣∣(p4.x<−w/2dp4.z)(p5.x > \frac{w/2}{d}p5.z) || (p4.x < -\frac{w/2}{d}p4.z)(p5.x>dw/2​p5.z)∣∣(p4.x<−dw/2​p4.z)
即：
(x1−r>w/2dz1)∣∣(x1+r<−w/2dz1)(x_1-r > \frac{w/2}{d}z_1) || (x_1+r < -\frac{w/2}{d}z_1)(x1​−r>dw/2​z1​)∣∣(x1​+r<−dw/2​z1​)

同理拓展到球心坐标为(x1,y1,z1)(x_1, y_1, z_1)(x1​,y1​,z1​)的3D包围球，可得y轴方向的剔除条件：

(y1−r>w/2dz1)∣∣(y1+r<−w/2dz1)(y_1-r > \frac{w/2}{d}z_1) || (y_1+r < -\frac{w/2}{d}z_1)(y1​−r>dw/2​z1​)∣∣(y1​+r<−dw/2​z1​)

只要满足任意一轴的剔除条件，即可判断包围球在视景体外，综上，给定物体包围球球心坐标(x1,y1,z1)(x_1, y_1, z_1)(x1​,y1​,z1​)、和相机参数（视平面宽度www，视距ddd，***面距离near_znear\_znear_z和远平面距离far_zfar\_zfar_z），物体被剔除的条件为：
(z1+r<far_z)∣∣(z1−r>near_z)∣∣(x1−r>w/2dz1)∣∣(x1+r<−w/2dz1)∣∣(y1−r>w/2dz1)∣∣(y1+r<−w/2dz1)
\begin{aligned}
&(z_1+r < far\_z) || (z_1-r > near\_z)\\
&||(x_1-r > \frac{w/2}{d}z_1) || (x_1+r < -\frac{w/2}{d}z_1)\\
&||(y_1-r > \frac{w/2}{d}z_1) || (y_1+r < -\frac{w/2}{d}z_1)
\end{aligned}
​(z1​+r<far_z)∣∣(z1​−r>near_z)∣∣(x1​−r>dw/2​z1​)∣∣(x1​+r<−dw/2​z1​)∣∣(y1​−r>dw/2​z1​)∣∣(y1​+r<−dw/2​z1​)​

物体剔除运行效果：

完整代码详见：https://github.com/maijiaquan/gdi-soft-render

参考资料：

1. 《3D游戏编程大师技巧》