原文 译文

已翻译 视锥体剔除

2017-06-29 1 7400

翻译作者

版权所有,禁止匿名转载;禁止商业使用;禁止个人使用。

 译者: 张乾光(星际迷航)    审校:崔国军(飞扬971 

导论

视锥体剔除是丢弃在屏幕上那些不可见的物体的过程。因为我们没有看到这些物体- 我们不需要在计算机上花费资源来为这些看不见的物体准备渲染以及实现渲染出来。

在这篇文章中,我将介绍下面的主题:

l  剔除方法:边界球、轴对齐边界包围盒(AABB)、有向包围盒(OBB)。

l  大量对象的剔除。

l  使用SSE(单指令多数据流式扩展)。

l  多线程剔除。

l  图形处理器剔除。

l  方法效率、工作速度的比较。

我在这篇文章中不会覆盖的内容:

  • 使用分层结构、树。 我们可以根据世界位置来对对象进行分组,并首先检查整个组的可见性。
  • 对单个对象的优化,比如说使用上一次“成功”的剔除平面。
  • 考虑场景深度缓冲区的可见性测试。对象就算在视椎体的内部,但可以完全被另一个更接近于查看者的对象所阻挡。因此,我们也可能丢弃对这个对象的渲染。
  • 软剔除。我们可以在中央处理器这一侧判断一个对象是否被另一个对象所阻挡。

•阴影的剔除。


最简单的剔除

我们有可见性的区域,可见性的区域由视锥体所设置。不在此区域内的对象应该从渲染过程中丢弃。视锥体通常设置有6个平面。

视锥体剔除


我们在场景中有一些对象。每个对象可能使用简单的几何进行近似,比如说是球体或盒子。对象的所有几何体都在这个基元的内部。

视锥体剔除

这种简单几何体的可见性测试执行得非常快。我们的目的是了解这个物体在视锥体上是否可见。

考虑可见性的定义:球体和盒子。 存在不同种类的包围盒:

世界坐标空间中的轴对齐(也就是轴对齐边界包围盒)以及根据局部坐标空间中的物体轴对齐(也就是有向包围盒)。可以清楚地看到,有向包围盒更接近对象,但有向包围盒的可见性测试比轴对齐边界包围盒的可见性测试更难。

边界球与视锥体的碰撞检测

算法:我们找到从物体的中心到视锥体每个平面的距离。如果点在任何超过球体半径的平面之后(也就是说物体的中心到视锥体平面的距离超过了球体的半径),则球体不在视锥体之中。满足此条件的平面就是分割平面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
__forceinline bool SphereInFrustum(vec3 &pos, float &radius, vec4 *frustum_planes)
 
{
 
        bool res = true;
 
        \\测试视锥体的6个平面。
 
        for (int i = 0; i < 6; i++)
 
        {
 
               \\计算球体的中心到视锥体每个平面的距离。
 
               \\如果物体的中心到视锥体平面的距离超过了球体的半径 –那么球体就超出了视锥体。
 
               if (frustum_planes[i].x * pos.x + frustum_planes[i].y * pos.y + frustum_planes[i].z * pos.z + frustum_planes[i].w <= -radius)
 
                       res = false;
 
                       \\return false; \\with flag works faster
 
        }
 
        return res;
 
}

轴对齐边界包围盒与视锥体的碰撞检测

边界球有的时候并不是近似对象形状的一个很好的选择。对于更精确的测试,经常使用包围盒。轴对齐边界包围盒或是有向包围盒。

测试视锥体中包围盒可见性的基本思想是:如果包围盒的所有8个顶点落在视锥体平面之外的话,则包围盒不在视锥体之中。在下一个示例中我们将实现轴对齐边界包围盒与视锥体的碰撞检测。但是,如果我们将有向包围盒的世界空间坐标点放在方程之中-我们就可以得到有向包围盒与视锥体的碰撞检测结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
__forceinline bool RightParallelepipedInFrustum2(vec4 &Min, vec4 &Max, vec4 *frustum_planes)
 
{
 
\\这只是基本想法的一个简单的示例 – 示范了包围盒剔除是如何发生的,这里面的包围盒包括了轴对齐边界包围盒和是有向包围盒。
 
\\ Min和Max是2个世界空间中的包围盒的顶点。用于轴对齐边界包围盒与视锥体的碰撞检测。
 
\\我们可以使用变换(通过对象矩阵)来将包围盒的8个顶点变换到世界空间之中。替换方程中的Min和Max,我们就可以得到有向包围盒与视锥体的碰撞检测。
 
        \\测试视锥体的6个平面。
 
        for (int i = 0; i<6; i++)
 
        {
 
\\尝试找到这样的一个平面,包围盒的8个顶点都位于这个平面的后面。
 
\\对视椎体的平面测试包围盒的所有8个顶点。
 
\\计算从点到平面的距离
 
\\如果点在平面之前的话(也就是距离>0),那么这就不是分离平面。
 
               if (frustum_planes[i][0] * Min[0] + frustum_planes[i][1] * Max[1] + frustum_planes[i][2] * Min[2] + frustum_planes[i][3]>0)
 
                       continue;
 
               if (frustum_planes[i][0] * Min[0] + frustum_planes[i][1] * Max[1] + frustum_planes[i][2] * Max[2] + frustum_planes[i][3]>0)
 
                       continue;
 
               if (frustum_planes[i][0] * Max[0] + frustum_planes[i][1] * Max[1] + frustum_planes[i][2] * Max[2] + frustum_planes[i][3]>0)
 
                       continue;
 
               if (frustum_planes[i][0] * Max[0] + frustum_planes[i][1] * Max[1] + frustum_planes[i][2] * Min[2] + frustum_planes[i][3]>0)
 
                       continue;
 
               if (frustum_planes[i][0] * Max[0] + frustum_planes[i][1] * Min[1] + frustum_planes[i][2] * Min[2] + frustum_planes[i][3]>0)
 
                       continue;
 
               if (frustum_planes[i][0] * Max[0] + frustum_planes[i][1] * Min[1] + frustum_planes[i][2] * Max[2] + frustum_planes[i][3]>0)
 
                       continue;
 
               if (frustum_planes[i][0] * Min[0] + frustum_planes[i][1] * Min[1] + frustum_planes[i][2] * Max[2] + frustum_planes[i][3]>0)
 
                       continue;
 
               if (frustum_planes[i][0] * Min[0] + frustum_planes[i][1] * Min[1] + frustum_planes[i][2] * Min[2] + frustum_planes[i][3]>0)
 
                       continue;
 
               return false;
 
    }
 
    return true;
 
}

轴对齐边界包围盒与视锥体的碰撞检测可以做一些优化。

算法:从8点找到最靠近平面的那个点,然后测试它是否在平面之后。如果是的话-那么对象不在视锥体的内部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
__forceinline bool RightParallelepipedInFrustum(vec4 &Min, vec4 &Max, vec4 *frustum_planes)
 
{
 
        bool inside = true;
 
        \\测试视锥体的6个平面。
 
        for (int i = 0; i<6; i++)
 
        {
 
        \\从8点找到最靠近平面的那个点,然后测试它是否在平面之后。
 
        \\如果是的话-那么对象不在视锥体的内部。
 
               float d = max(Min.x * frustum_planes[i].x, Max.x * frustum_planes[i].x) +
 
                                 max(Min.y * frustum_planes[i].y, Max.y * frustum_planes[i].y) +
 
                                 max(Min.z * frustum_planes[i].z, Max.z * frustum_planes[i].z) +
 
                                 frustum_planes[i].w;
 
               inside &= d > 0;
 
               //return false; //with flag works faster
 
        }
 
        return inside;
 
}


有向包围盒与视锥体的碰撞检测

算法:将包围盒的8个顶点从局部空间变换到裁剪空间。把视锥体变为在单位立方体[-1..1]之后,(但是我们应该考虑到,如果是在DirectX,对于Z轴我们有另一个尺寸[0..1])在这样的空间中测试点是容易的。如果对于某个轴,所有8个顶点都小于-1或是都大于 1,则包围盒在视锥体之外。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
__forceinline bool OBBInFrustum(const vec3 &Min, const vec3 &Max, mat4 &obj_transform_mat, mat4 &cam_modelview_proj_mat)
 
{
 
        \\将包围盒的8个顶点从局部空间变换到裁剪空间。
 
        //clip space because we easily can test points outside required unit cube
 
        //NOTE: for DirectX we should test z coordinate from 0 to w (-w..w - for OpenGL), look for      transformations / clipping box differences
 
        //matrix to transfrom points to clip space
 
        mat4 to_clip_space_mat = cam_modelview_proj_mat * obj_transform_mat;
 
  
 
        \\将包围盒的8个顶点从局部空间变换到裁剪空间。
 
        vec4 obb_points[8];
 
        obb_points[0] = to_clip_space_mat * vec4(Min[0], Max[1], Min[2], 1.f);
 
        obb_points[1] = to_clip_space_mat * vec4(Min[0], Max[1], Max[2], 1.f);
 
        obb_points[2] = to_clip_space_mat * vec4(Max[0], Max[1], Max[2], 1.f);
 
        obb_points[3] = to_clip_space_mat * vec4(Max[0], Max[1], Min[2], 1.f);
 
        obb_points[4] = to_clip_space_mat * vec4(Max[0], Min[1], Min[2], 1.f);
 
        obb_points[5] = to_clip_space_mat * vec4(Max[0], Min[1], Max[2], 1.f);
 
        obb_points[6] = to_clip_space_mat * vec4(Min[0], Min[1], Max[2], 1.f);
 
        obb_points[7] = to_clip_space_mat * vec4(Min[0], Min[1], Min[2], 1.f);
 
  
 
        bool outside = false, outside_positive_plane, outside_negative_plane;
 
  
 
        //we have 6 frustum planes, which in clip space is unit cube (for GL) with -1..1 range
 
        for (int i = 0; i < 3; i++) //3 because we test positive & negative plane at once
 
        {
 
        //if all 8 points outside one of the plane
 
        //actually it is vertex normalization xyz / w, then compare if all 8points coordinates <      -1 or > 1
 
               outside_positive_plane =
 
                       obb_points[0][i] > obb_points[0].w &&
 
                       obb_points[1][i] > obb_points[1].w &&
 
                       obb_points[2][i] > obb_points[2].w &&
 
                       obb_points[3][i] > obb_points[3].w &&
 
                       obb_points[4][i] > obb_points[4].w &&
 
                       obb_points[5][i] > obb_points[5].w &&
 
                       obb_points[6][i] > obb_points[6].w &&
 
                       obb_points[7][i] > obb_points[7].w;
 
  
 
               outside_negative_plane =
 
                       obb_points[0][i] < -obb_points[0].w &&
 
                       obb_points[1][i] < -obb_points[1].w &&
 
                       obb_points[2][i] < -obb_points[2].w &&
 
                       obb_points[3][i] < -obb_points[3].w &&
 
                       obb_points[4][i] < -obb_points[4].w &&
 
                       obb_points[5][i] < -obb_points[5].w &&
 
                       obb_points[6][i] < -obb_points[6].w &&
 
                       obb_points[7][i] < -obb_points[7].w;
 
  
 
               outside = outside || outside_positive_plane || outside_negative_plane;
 
               //if (outside_positive_plane || outside_negative_plane)
 
                       //return false;
 
        }
 
        return !outside;
 
        //return true;
 
}

表格110万个物体的剔除测试结果。使用的是英特尔酷睿I5,在单线程的情况。

Simple Culling

Sphere

AABB

OBB

Just cullung

0,92

1,42

9,14

Whole frame

1,94

2,5

10,3


结果是非常明显的。计算越难速度就越慢。有向包围盒的测试比边界球或是轴对齐边界包围盒的测试要慢得多。但是我们可以用有向包围盒来得到更精确的剔除结果。

也许,最佳解决方案是将对象分组,对于每个组根据到相机的距离,我们使用适当的图元。对于离相机最近的组使用有向包围盒,对于中间的组使用轴对齐边界包围盒,对于剩下的组使用边界球。

还应该注意到整个帧时间大于只是剔除的时间。平均下来需要1毫秒。。 因为将可见对象的数据传输到图形处理器有成本,需要很多 API命令。但这些都是必须的。


单指令多数据流式扩展

SSE (单指令多数据流式扩展) – 有一个指令让我们可以操作数组执行计算。单指令多数据流式扩展在其架构中包括八个128位寄存器和一组指令,以对它们执行任何操作。

理论上,我们可以4倍加速代码执行,因为我们同时用4个操作数进行操作。由于单指令多数据流式扩展的弊端,实践性中并没有这么大的提升。

l  并非所有算法都可以在单指令多数据流式扩展中轻松重写。

l  数据应根据单指令多数据流式扩展要求在寄存器中进行打包以执行计算。

l  单指令多数据流式扩展对垂直操作(例如点积)有一些限制。

l  没有条件。当我们执行bot 2部分的条件的时候,只是使用一个所谓的静态分支,我们的结果只对一个感兴趣。

l  将数据加载到寄存器并将结果存回存储器。

l  不要忘记单指令多数据流式扩展中的数据跨越。

单指令多数据流式扩展版本的

 

单指令多数据流式扩展版本的边界球与视锥体的碰撞检测和轴对齐边界包围盒与视锥体的碰撞检测几乎与简单实现相同。除了我们同时对4个对象执行计算之外。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
void sse_culling_spheres(BSphere *sphere_data, int num_objects, int *culling_res, vec4 *frustum_planes)
 
{
 
        float *sphere_data_ptr = reinterpret_cast<float*>(&sphere_data[0]);
 
        int *culling_res_sse = &culling_res[0];
 
  
 
        //to optimize calculations we gather xyzw elements in separate vectors
 
        __m128 zero_v = _mm_setzero_ps();
 
        __m128 frustum_planes_x[6];
 
        __m128 frustum_planes_y[6];
 
        __m128 frustum_planes_z[6];
 
        __m128 frustum_planes_d[6];
 
  
 
        int i, j;
 
        for (i = 0; i < 6; i++)
 
        {
 
               frustum_planes_x[i] = _mm_set1_ps(frustum_planes[i].x);
 
               frustum_planes_y[i] = _mm_set1_ps(frustum_planes[i].y);
 
               frustum_planes_z[i] = _mm_set1_ps(frustum_planes[i].z);
 
               frustum_planes_d[i] = _mm_set1_ps(frustum_planes[i].w);
 
        }
 
  
 
        //we process 4 objects per step
 
        for (i = 0; i < num_objects; i += 4)
 
        {
 
        //load bounding sphere data
 
               __m128 spheres_pos_x = _mm_load_ps(sphere_data_ptr);
 
               __m128 spheres_pos_y = _mm_load_ps(sphere_data_ptr + 4);
 
               __m128 spheres_pos_z = _mm_load_ps(sphere_data_ptr + 8);
 
               __m128 spheres_radius = _mm_load_ps(sphere_data_ptr + 12);
 
               sphere_data_ptr += 16;
 
  
 
        //but for our calculations we need transpose data, to collect x, y, z and w coordinates in separate vectors
 
               _MM_TRANSPOSE4_PS(spheres_pos_x, spheres_pos_y, spheres_pos_z, spheres_radius);
 
               __m128 spheres_neg_radius = _mm_sub_ps(zero_v, spheres_radius); // negate all elements
 
  
 
               __m128 intersection_res = _mm_setzero_ps();
 
               for (j = 0; j < 6; j++) //plane index
 
               {
 
               //1. calc distance to plane dot(sphere_pos.xyz, plane.xyz) + plane.w
 
               //2. if distance < sphere radius, then sphere outside frustum
 
                       __m128 dot_x = _mm_mul_ps(spheres_pos_x, frustum_planes_x[j]);
 
                       __m128 dot_y = _mm_mul_ps(spheres_pos_y, frustum_planes_y[j]);
 
                       __m128 dot_z = _mm_mul_ps(spheres_pos_z, frustum_planes_z[j]);
 
  
 
                       __m128 sum_xy = _mm_add_ps(dot_x, dot_y);
 
                       __m128 sum_zw = _mm_add_ps(dot_z, frustum_planes_d[j]);
 
                       __m128 distance_to_plane = _mm_add_ps(sum_xy, sum_zw);
 
  
 
                       __m128 plane_res = _mm_cmple_ps(distance_to_plane, spheres_neg_radius); //dist < -sphere_r ?
 
                       intersection_res = _mm_or_ps(intersection_res, plane_res); //if yes - sphere behind the plane & outside frustum
 
               }
 
  
 
               //store result
 
               __m128i intersection_res_i = _mm_cvtps_epi32(intersection_res);
 
               _mm_store_si128((__m128i *)&culling_res_sse[i], intersection_res_i);
 
        }
 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
void sse_culling_aabb(AABB *aabb_data, int num_objects, int *culling_res, vec4 *frustum_planes)
 
{
 
        float *aabb_data_ptr = reinterpret_cast<float*>(&aabb_data[0]);
 
        int *culling_res_sse = &culling_res[0];
 
  
 
        //to optimize calculations we gather xyzw elements in separate vectors
 
        __m128 zero_v = _mm_setzero_ps();
 
        __m128 frustum_planes_x[6];
 
        __m128 frustum_planes_y[6];
 
        __m128 frustum_planes_z[6];
 
        __m128 frustum_planes_d[6];
 
  
 
        int i, j;
 
        for (i = 0; i < 6; i++)
 
        {
 
               frustum_planes_x[i] = _mm_set1_ps(frustum_planes[i].x);
 
               frustum_planes_y[i] = _mm_set1_ps(frustum_planes[i].y);
 
               frustum_planes_z[i] = _mm_set1_ps(frustum_planes[i].z);
 
               frustum_planes_d[i] = _mm_set1_ps(frustum_planes[i].w);
 
        }
 
  
 
        __m128 zero = _mm_setzero_ps();
 
        //we process 4 objects per step
 
        for (i = 0; i < num_objects; i += 4)
 
        {
 
        //load objects data
 
        //load aabb min
 
               __m128 aabb_min_x = _mm_load_ps(aabb_data_ptr);
 
               __m128 aabb_min_y = _mm_load_ps(aabb_data_ptr + 8);
 
               __m128 aabb_min_z = _mm_load_ps(aabb_data_ptr + 16);
 
               __m128 aabb_min_w = _mm_load_ps(aabb_data_ptr + 24);
 
  
 
        //load aabb max
 
               __m128 aabb_max_x = _mm_load_ps(aabb_data_ptr + 4);
 
               __m128 aabb_max_y = _mm_load_ps(aabb_data_ptr + 12);
 
               __m128 aabb_max_z = _mm_load_ps(aabb_data_ptr + 20);
 
               __m128 aabb_max_w = _mm_load_ps(aabb_data_ptr + 28);
 
               aabb_data_ptr += 32;
 
  
 
        //for now we have points in vectors aabb_min_x..w, but for calculations we need to xxxx yyyy zzzz vectors representation - just transpose data
 
               _MM_TRANSPOSE4_PS(aabb_min_x, aabb_min_y, aabb_min_z, aabb_min_w);
 
               _MM_TRANSPOSE4_PS(aabb_max_x, aabb_max_y, aabb_max_z, aabb_max_w);
 
  
 
               __m128 intersection_res = _mm_setzero_ps();
 
               for (j = 0; j < 6; j++) //plane index
 
               {
 
               //this code is similar to what we make in simple culling
 
               //pick closest point to plane and check if it begind the plane. if yes - object outside frustum
 
               //dot product, separate for each coordinate, for min & max aabb points
 
                       __m128 aabbMin_frustumPlane_x = _mm_mul_ps(aabb_min_x, frustum_planes_x[j]);
 
                       __m128 aabbMin_frustumPlane_y = _mm_mul_ps(aabb_min_y, frustum_planes_y[j]);
 
                       __m128 aabbMin_frustumPlane_z = _mm_mul_ps(aabb_min_z, frustum_planes_z[j]);
 
  
 
                       __m128 aabbMax_frustumPlane_x = _mm_mul_ps(aabb_max_x, frustum_planes_x[j]);
 
                       __m128 aabbMax_frustumPlane_y = _mm_mul_ps(aabb_max_y, frustum_planes_y[j]);
 
                       __m128 aabbMax_frustumPlane_z = _mm_mul_ps(aabb_max_z, frustum_planes_z[j]);
 
  
 
               //we have 8 box points, but we need pick closest point to plane. Just take max
 
                       __m128 res_x = _mm_max_ps(aabbMin_frustumPlane_x, aabbMax_frustumPlane_x);
 
                       __m128 res_y = _mm_max_ps(aabbMin_frustumPlane_y, aabbMax_frustumPlane_y);
 
                       __m128 res_z = _mm_max_ps(aabbMin_frustumPlane_z, aabbMax_frustumPlane_z);
 
  
 
               //dist to plane = dot(aabb_point.xyz, plane.xyz) + plane.w
 
                       __m128 sum_xy = _mm_add_ps(res_x, res_y);
 
                       __m128 sum_zw = _mm_add_ps(res_z, frustum_planes_d[j]);
 
                       __m128 distance_to_plane = _mm_add_ps(sum_xy, sum_zw);
 
  
 
                       __m128 plane_res = _mm_cmple_ps(distance_to_plane, zero); //dist from closest point to plane < 0 ?
 
                       intersection_res = _mm_or_ps(intersection_res, plane_res); //if yes - aabb behind the plane & outside frustum
 
               }
 
  
 
               //store result
 
               __m128i intersection_res_i = _mm_cvtps_epi32(intersection_res);
 
               _mm_store_si128((__m128i *)&culling_res_sse[i], intersection_res_i);
 
        }
 
}

有向包围盒的剔除有点困难。我们一次对一个对象执行计算。但是同时计算三个xyz轴。这不是最佳的方法,但它反映了算法的基本思想。此外,具有单指令多数据流式扩展指令的向量数学(矩阵乘法和点的变换)执行得更快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
void sse_culling_obb(int firs_processing_object, int num_objects, int *culling_res, mat4 &cam_modelview_proj_mat)
 
{
 
        mat4_sse sse_camera_mat(cam_modelview_proj_mat);
 
        mat4_sse sse_clip_space_mat;
 
  
 
        //box points in local space
 
        __m128 obb_points_sse[8];
 
        obb_points_sse[0] = _mm_set_ps(1.f, box_min[2], box_max[1], box_min[0]);
 
        obb_points_sse[1] = _mm_set_ps(1.f, box_max[2], box_max[1], box_min[0]);
 
        obb_points_sse[2] = _mm_set_ps(1.f, box_max[2], box_max[1], box_max[0]);
 
        obb_points_sse[3] = _mm_set_ps(1.f, box_min[2], box_max[1], box_max[0]);
 
        obb_points_sse[4] = _mm_set_ps(1.f, box_min[2], box_min[1], box_max[0]);
 
        obb_points_sse[5] = _mm_set_ps(1.f, box_max[2], box_min[1], box_max[0]);
 
        obb_points_sse[6] = _mm_set_ps(1.f, box_max[2], box_min[1], box_min[0]);
 
        obb_points_sse[7] = _mm_set_ps(1.f, box_min[2], box_min[1], box_min[0]);
 
  
 
        ALIGN_SSE int obj_culling_res[4];
 
        __m128 zero_v = _mm_setzero_ps();
 
  
 
        int i, j;
 
        //process one object per step
 
        for (i = firs_processing_object; i < firs_processing_object+num_objects; i++)
 
        {
 
        //clip space matrix = camera_view_proj * obj_mat
 
               sse_mat4_mul(sse_clip_space_mat, sse_camera_mat, sse_obj_mat[i]);
 
               __m128 outside_positive_plane = _mm_set1_ps(0xffffffff);
 
               __m128 outside_negative_plane = _mm_set1_ps(0xffffffff);
 
  
 
        //for all 8 box points
 
               for (j = 0; j < 8; j++)
 
               {
 
               //transform point to clip space
 
                       __m128 obb_transformed_point = sse_mat4_mul_vec4(sse_clip_space_mat, obb_points_sse[j]);
 
  
 
               //gather w & -w
 
                       __m128 wwww = _mm_shuffle_ps(obb_transformed_point, obb_transformed_point, _MM_SHUFFLE(3, 3, 3, 3)); //get w
 
                       __m128 wwww_neg = _mm_sub_ps(zero_v, wwww); // negate all elements
 
  
 
               //box_point.xyz > box_point.w || box_point.xyz < -box_point.w ?
 
               //similar to point normalization: point.xyz /= point.w; And compare: point.xyz > 1 && point.xyz < -1
 
                       __m128 outside_pos_plane = _mm_cmpge_ps(obb_transformed_point, wwww);
 
                       __m128 outside_neg_plane = _mm_cmple_ps(obb_transformed_point, wwww_neg);
 
  
 
               //if at least 1 of 8 points in front of the plane - we get 0 in outside_* flag
 
                       outside_positive_plane = _mm_and_ps(outside_positive_plane, outside_pos_plane);
 
                       outside_negative_plane = _mm_and_ps(outside_negative_plane, outside_neg_plane);
 
               }
 
  
 
               //all 8 points xyz < -1 or > 1 ?
 
               __m128 outside = _mm_or_ps(outside_positive_plane, outside_negative_plane);
 
  
 
               //store result
 
               __m128i outside_res_i = _mm_cvtps_epi32(outside);
 
               _mm_store_si128((__m128i *)&obj_culling_res[0], outside_res_i);
 
  
 
               //for now we have separate result separately for each axis
 
               //combine results. If outside any plane, then objects is outside frustum
 
               culling_res[i] = (obj_culling_res[0] != 0 || obj_culling_res[1] != 0 ||  obj_culling_res[2] != 0) ? 1 : 0;
 
        }
 
}

表格210万个物体的单指令多数据流式扩展版本剔除测试结果。使用的是英特尔酷睿I5,在单线程的情况。

SSE Culling

Sphere

AABB

OBB

Just culling

0,26

0,46

3,48

Whole frame

1,2

1,43

4,6

 

单指令多数据流式扩展版本的实现平均是C ++版本简单实现的3倍速度。

多线程

现在处理器有几个内核。可以在所有核上同时执行计算。

新的游戏架构应考虑多线程,即独立部件/任务的分离工作,这样能够同时解决它们,均匀加载到所有处理器核心。设计应该灵活。过多的小任务导致同步工作和任务之间切换的开销。太多的大任务导致核心的负载很重。这需要一个平衡。在当前的游戏中,每帧可能有几百到几千个任务。

在我们的视锥体剔除的情况下,每个对象独立于其余的对象。这就是为什么我们可以轻松地将工作分成相等的组,并用不同的处理器核心同时剔除它们。运行作业执行以后,我们需要等待线程来完成他们的工作并收集结果。

当然,我们不应该在执行开始后查询结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
Worker::Worker() : first_processing_oject(0), num_processing_ojects(0)
 
{
 
        //create 2 events: 1. to signal that we have a job 2.signal that we finished job
 
        has_jobs_event = CreateEvent(NULL, false, false, NULL);
 
        jobs_finished_event = CreateEvent(NULL, false, true, NULL);
 
}
 
  
 
void Worker::doJob()
 
{
 
        //make our part of work
 
        cull_objects(first_processing_oject, num_processing_ojects);
 
}
 
  
 
unsigned __stdcall thread_func(void* arguments)
 
{
 
        printf("In thread...\n");
 
        Worker *worker = static_cast<worker*>(arguments);
 
  
 
        //each worker has endless loop untill we signal to quit (stop_work flag)
 
        while (true)
 
        {
 
        //wait for starting jobs
 
        //if we have no job - just wait (has_jobs_event event). We do not wasting cpu work. Events designed for this.
 
               WaitForSingleObject(worker->has_jobs_event, INFINITE);
 
  
 
        //if we have signal to break - exit endless loop
 
               if (worker->stop_work)
 
                       break;
 
  
 
        //do job
 
               worker->doJob();
 
  
 
        //signal that we finished the job
 
               SetEvent(worker->jobs_finished_event);
 
        }
 
        _endthreadex(0);
 
        return 0;
 
}
 
  
 
void create_threads()
 
{
 
        //create the threads
 
        //split the work into parts between threads
 
        int worker_num_processing_ojects = MAX_SCENE_OBJECTS / num_workers;
 
        int first_processing_oject = 0;
 
  
 
        int i;
 
        for (i = 0; i < num_workers; i++)
 
        {
 
        //create threads
 
               workers[i].thread_handle = (HANDLE)_beginthreadex(NULL, 0, &thread_func, &workers[i], CREATE_SUSPENDED, &workers[i].thread_id);
 
               thread_handles[i] = workers[i].thread_handle;
 
  
 
        //set threads parameters
 
               workers[i].first_processing_oject = first_processing_oject;
 
               workers[i].num_processing_ojects = worker_num_processing_ojects;
 
               first_processing_oject += worker_num_processing_ojects;
 
        }
 
        //run workers to do their jobs
 
        for (int i = 0; i < num_workers; i++)
 
               ResumeThread(workers[i].thread_handle);
 
}
 
  
 
void process_multithreading_culling()
 
{
 
        //signal workers that they have the job
 
        for (int i = 0; i < num_workers; i++)
 
               SetEvent(workers[i].has_jobs_event);
 
}
 
  
 
void wate_multithreading_culling_done()
 
{
 
        //wait threads to do their jobs
 
        HANDLE wait_events[num_workers];
 
        for (int i = 0; i < num_workers; i++)
 
               wait_events[i] = workers[i].jobs_finished_event;
 
        WaitForMultipleObjects(num_workers, &wait_events[0], true, INFINITE);
 
}

表格210万个物体的剔除测试结果。使用的是英特尔酷睿I54核),括号中的数字恰好是相对于简单的c ++实现加速的效果。

Method

Sphere

AABB

OBB

Simple c++

0,92 (1)

1,42 (1)

9,14 (1)

SSE

0,26 (3,54)

0,46 (3,08)

3,48 (2,62)

Simple c++, Mulithreaded

0,25 (3,68)

0,4 (3,55)

2,5 (3,65)

SSE, Multithreaded

0,1 (9,2)

0,18 (7,89)

1 (9,14)

多线程版本比单线程平均快3.6倍。

使用单指令多数据流式扩展的话可以使我们的速度相对于简单的c ++实现提高了3倍。

使用单指令多数据流式扩展和多线程可以使我们的速度提高了8.7倍!

也就是说 我们优化了我们的计算近,提升了近9倍的速度,这也取决于使用的剔除基元的类型。


图形处理器的剔除

图形处理器设计为对大量数据执行相同的操作。图形处理器具有的并行线程数(数千个)多于中央处理器(在大多数桌面图形处理器的情况下并行线程数为2-8)。但是在图形处理器上进行剔除并不舒服:

l  这依赖了特殊的图形引擎架构。

l  我们评估在中央处理器一侧执行的dip指令的时候,会有一些令人不快的时刻。为此,我们需要知道图形处理器生成的基元(在我们的情况下能够在视锥体对象中可见)。这就是为什么我们需要从图形处理器中获得反馈。有特殊的指令做这个目的。

l  问题是如果我们想要在与剔除和渲染的同一帧中获得结果。我们会让图形处理器停止工作,因为我们需要等待结果。这对于性能来说是很糟糕的结果。如果从上一帧中读取结果-我们会得到一些错误信息。完全解决这个问题的方法是使用DrawIndirect命令并准备关于dip在图形处理器一侧执行的信息。从DirectX11Opengl 4之后这就是可用的。



图形处理器剔除的实现包括以下步骤:

1.     在顶点缓冲区中封装所有实例数据。假设一个顶点是用于进行剔除的一个对象。顶点的属性数量等于每个对象的数据量。

2.     启用变换反馈。在渲染器上发送准备的顶点缓冲区。所有结果重定向到具有可见实例数据的另一个顶点缓冲区。

3.     在顶点着色器检查对象的可见性。

4.     在几何着色器中丢弃对象/杀死顶点,如果实例在视椎体中不可见的话。

5.     因此,我们只用可见的实例数据形成了缓冲区。

6.     但是现在我们需要从图形处理器获得大量的可见对象的信息,以便在中央处理器一侧执行dip指令。在这种情况下,我们使用来自前一帧的变换反馈(仅仅是为了代码简单)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
void do_gpu_culling()
 
{
 
        culling_shader.bind();
 
  
 
        int cur_frame = frame_index % 2;
 
        int prev_frame = (frame_index + 1) % 2;
 
  
 
        //enable transform feedback & query
 
        glBindBufferBase(GL_TRANSFORM_FEEDBACK_BUFFER, 0, dips_texture_buffer);
 
        glBeginQuery(GL_TRANSFORM_FEEDBACK_PRIMITIVES_WRITTEN,                   
 
        num_visible_instances_query[cur_frame]);
 
        glBeginTransformFeedback(GL_POINTS);
 
  
 
        //render cloud of points which we interprent as objects data
 
        glBindVertexArray(all_instances_data_vao);
 
        glDrawArrays(GL_POINTS, 0, MAX_SCENE_OBJECTS);
 
        glBindVertexArray(0);
 
  
 
        //disable all
 
        glEndTransformFeedback();
 
        glEndQuery(GL_TRANSFORM_FEEDBACK_PRIMITIVES_WRITTEN);
 
        glBindBufferBase(GL_TRANSFORM_FEEDBACK_BUFFER, 0, 0);
 
        glDisable(GL_RASTERIZER_DISCARD);
 
  
 
        //get feedback from prev frame
 
        num_visible_instances = 0;
 
        glGetQueryObjectiv(num_visible_instances_query[prev_frame], GL_QUERY_RESULT,      &num_visible_instances);
 
  
 
        //next frame
 
        frame_index++;
 
}


从第3步开始的顶点着色器代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#version 330 core
 
in vec4 s_attribute_0;
 
in vec4 s_attribute_1;
 
  
 
out vec4 instance_data1;
 
out vec4 instance_data2;
 
out int visible;
 
  
 
uniform mat4 ModelViewProjectionMatrix;
 
uniform vec4 frustum_planes[6];
 
  
 
int InstanceCloudReduction()
 
{
 
        //sphere - frustum test
 
        bool inside = true;
 
        for (int i = 0; i < 6; i++)
 
        {
 
               if (dot(frustum_planes[i].xyz, s_attribute_0.xyz) + frustum_planes[i].w <= -s_attribute_0.w)
 
                       inside = false;
 
        }
 
        return inside ? 1 : 0;
 
}
 
  
 
void main()
 
{
 
//read instance data
 
        instance_data1 = s_attribute_0;
 
        instance_data2 = s_attribute_1;
 
  
 
//visibility
 
        visible = InstanceCloudReduction();
 
        gl_Position = ModelViewProjectionMatrix * vec4(s_attribute_0.xyz,1);
 
}

从第4步开始的几何着色器代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#version 400 core
 
layout (points) in;
 
layout (points, max_vertices = 1) out;
 
  
 
in vec4 instance_data1[];
 
in vec4 instance_data2[];
 
in int visible[];
 
  
 
out vec4 output_instance_data1;
 
out vec4 output_instance_data2;
 
  
 
void main( )
 
{
 
        //if primitive is not visible - discard it !
 
        //visible comes from vertex shader
 
        if (visible[0] == 1)
 
        {
 
        //just transfer data
 
               output_instance_data1 = instance_data1[0];
 
               output_instance_data2 = instance_data2[0];
 
               gl_Position = vec4(0.0, 0.0, 0.0, 1.0);
 
                EmitVertex();
 
               EndPrimitive();
 
        }
 
}

带有图形处理器剔除的整个帧时间约为1.19毫秒。几乎与最快的中央处理器方法变种相同,最快的中央处理器方法变种是使用单指令多数据流式扩展和多线程的边界球与视锥体的碰撞检测。


所有方法的性能比较

我们比较了中央处理器方法的剔除速度,但只提到了剔除时间。现在我们要测量的是整个帧的时间,所以测量结果将有所不同,因为我们需要考虑到数据传输和其他一些其他工作。

表格4:所有剔除方法的性能比较。比较的是整帧时间,以毫秒为单位。

Method

Sphere

AABB

OBB

Simple c++

1,94

2,46

10,3

SSE

1,2

1,45

4,63

Simple c++, multithreading

1,23

1,42

3,6

SSE, multithreading

1,18

1,2

2,02

GPU

1,19

-

-


测量结果可能有一些不准确。平均时间总是因帧而异。


结论

使用单指令多数据流式扩展和多线程使我们获得了与简单的c ++实现相比9倍的性能提升。如果可以使用Opengl 4的话(通过GL_MAP_PERSISTENT_BITGL_MAP_COHERENT_BIT标志映射缓冲区),那么数据传输到图形处理器变得真的很快。此外,我们能够使用层次结构和各种技巧,比如说记住最后一个剔除了对象的视锥体平面来优化剔除:

图形处理器的剔除与优化最好的中央处理器的方法一样快。并有这么几个优点:

·         无需将可见的实例数据传输到图形处理器。这些可见的实例数据已经在那里了。如果使用DrawIndirect(比如说是DX11 +OpenGL 4+还有一些新的APIDX12VulkanMetal)和在中央处理器一侧关于dip的常规信息,那么我们可以获得更好的性能。

·         可以相对容易地进行额外的剔除,同时考虑自阻塞/隐藏/内部可见性(基于层次Z的遮挡剔除)。

所以-什么时候使用中央处理器这一侧的剔除,而什么时候使用图形处理器这一侧的剔除呢?

这主要取决于这么几件事:

·         项目和需要进行多大的更改,来使图形处理器负责剔除。

·         我们能否使用DrawIndirect

·         什么是瓶颈:中央处理器还是图形处理器?

·         我们是否需要根据场景的深度复杂度进行额外的剔除。如果需要的话,在图形处理器这一侧,它会更容易和更快。

如果有这样的机会的话-应该使用图形处理器进行剔除。

相关的代码可以到这里进行下载:Source code of all examples.

相关的链接:

1.    Collision Detection FAQ

2.    View frustum culling

3.    View frustum culling optimization

4.    Efficient View Frustum Culling

5.    Optimized View Frustum Culling Algorithms for Bounding Boxes

6.    Hierarchical-Z map based occlusion culling

7.    Beyond Porting. How Modern OpenGL can Radically Reduce DriverOverhead

8.    Parallelizing the Naughty Dog engine using fibers

9.    Practical Occlusion Culling in Killzone 3

10.  Software Occlusion Culling

11.  Streaming SIMD Extensions (SSE)

 

GerlitsAnatoliy.
2017
2


【版权声明】

请见GDOL (Gamedev.net Open License)

http://www.gamedev.net/page/resources/_/gdnethelp/gamedevnet-open-license-r2956

根据授权文件,我们可以翻译这篇文章。

分类: 标签: FrustumC
举报 分享

想免费获取内部独家PPT资料库? 观看行业大牛直播?

立即扫码加群

评论(1)

1个评论

GAD译馆

更多