src/client/frustum.c

   1 #include "client/camera.h"
   2 #include "client/frustum.h"
   3 #include "client/window.h"
   4
   5 typedef enum {
   6         PLANE_LEFT,
   7         PLANE_RIGHT,
   8         PLANE_BOTTOM,
   9         PLANE_TOP,
  10         PLANE_NEAR,
  11         PLANE_FAR,
  12         PLANE_COUNT,
  13 } Plane;
  14
  15 mat4x4 frustum;
  16
  17 static vec3 points[8];
  18 static vec4 planes[PLANE_COUNT];
  19 static int cross_indices[PLANE_COUNT][PLANE_COUNT];
  20
  21 __attribute__((constructor)) static void frustum_init()
  22 {
  23         for (Plane a = 0; a < PLANE_COUNT; a++)
  24                 for (Plane b = 0; b < PLANE_COUNT; b++)
  25                         cross_indices[a][b] = a * (9 - a) / 2 + b - 1;
  26 }
  27
  28 void frustum_update()
  29 {
  30         mat4x4_mul(frustum, window.projection, camera.view);
  31
  32         mat4x4 m;
  33         mat4x4_transpose(m, frustum);
  34
  35         vec4_add(planes[PLANE_LEFT], m[3], m[0]);
  36         vec4_sub(planes[PLANE_RIGHT], m[3], m[0]);
  37         vec4_add(planes[PLANE_BOTTOM], m[3], m[1]);
  38         vec4_sub(planes[PLANE_TOP], m[3], m[1]);
  39         vec4_add(planes[PLANE_NEAR], m[3], m[2]);
  40         vec4_sub(planes[PLANE_FAR], m[3], m[2]);
  41
  42         int i = 0;
  43         vec3 crosses[PLANE_COUNT * (PLANE_COUNT - 1) / 2];
  44         for (Plane a = 0; a < PLANE_COUNT; a++)
  45                 for (Plane b = a + 1; b < PLANE_COUNT; b++)
  46                         vec3_mul_cross(crosses[i++], planes[a], planes[b]);
  47
  48         int j = 0;
  49         for (Plane c = PLANE_NEAR; c <= PLANE_FAR; c++) {
  50                 for (Plane a = PLANE_LEFT; a <= PLANE_RIGHT; a++) {
  51                         for (Plane b = PLANE_BOTTOM; b <= PLANE_TOP; b++) {
  52                                 float d = -1.0f / vec3_mul_inner(planes[a], crosses[cross_indices[b][c]]);
  53                                 vec3 w = {planes[a][3], planes[b][3], planes[c][3]};
  54                                 float *res = points[j++];
  55
  56                                 vec3 res_1_cross = {-crosses[cross_indices[a][c]][0], -crosses[cross_indices[a][c]][1], -crosses[cross_indices[a][c]][2]};
  57
  58                                 res[0] = vec3_mul_inner(crosses[cross_indices[b][c]], w) * d;
  59                                 res[1] = vec3_mul_inner(res_1_cross, w) * d;
  60                                 res[2] = vec3_mul_inner(crosses[cross_indices[a][b]], w) * d;
  61                         }
  62                 }
  63         }
  64 }
  65
  66 static bool outside_plane(Plane i, aabb3f32 box)
  67 {
  68         for (int x = 0; x <= 1; x++) {
  69                 for (int y = 0; y <= 1; y++) {
  70                         for (int z = 0; z <= 1; z++) {
  71                                 vec4 plane = {
  72                                         x ? box.max.x : box.min.x,
  73                                         y ? box.max.y : box.min.y,
  74                                         z ? box.max.z : box.min.z,
  75                                         1.0f,
  76                                 };
  77
  78                                 if (vec4_mul_inner(planes[i], plane) > 0.0)
  79                                         return false;
  80                         }
  81                 }
  82         }
  83
  84         return true;
  85 }
  86
  87 // http://iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm
  88 static bool box_visible(aabb3f32 box)
  89 {
  90         for (Plane i = 0; i < PLANE_COUNT; i++) {
  91                 if (outside_plane(i, box))
  92                         return false;
  93         }
  94
  95         int box_outside[6] = {0};
  96
  97         for (Plane i = 0; i < PLANE_COUNT; i++) {
  98                 int outside[6] = {
  99                         points[i][0] > box.max.x,
 100                         points[i][0] < box.min.x,
 101                         points[i][1] > box.max.y,
 102                         points[i][1] < box.min.y,
 103                         points[i][2] > box.max.z,
 104                         points[i][2] < box.min.z,
 105                 };
 106
 107                 for (int i = 0; i < 6; i++)
 108                         box_outside[i] += outside[i];
 109         }
 110
 111         for (int i = 0; i < 6; i++) {
 112                 if (box_outside[i] == 8)
 113                         return false;
 114         }
 115
 116         return true;
 117 }
 118
 119 bool frustum_cull(aabb3f32 box)
 120 {
 121         return !box_visible(box);
 122 }