Implement frustum culling properly

diff --git a/README.md b/README.md
index c5472422a082687abc972ebf3189dabab33f2f60..e9effe3be2ebdf864fe45ad17ec87e65feaae436 100644 (file)
--- a/README.md
+++ b/README.md
@@ -63,10 +63,10 @@ A PC with at least 4 CPU cores is recommended, but not necessarly required.
 
 ## Current Features
 - Multiplayer
-- Map generation with mountains, snow, temperature and humidity, dynamic grass color, oceans and beaches, vulcanos
+- Mountains, snow, temperature and humidity, dynamic grass color, oceans and beaches, vulcanos, boulders
 - Physics
 - FPS Camera
-- Mipmapping, Antialiasing, Face Culling, Diffuse Lighting, Skybox, Fog
+- Mipmapping, Antialiasing, Face Culling, Frustum Culling, Diffuse Lighting, Skybox, Fog
 - Taking screenshots
 - Daylight cycle
 - GUI

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 242e83dffb6b9d15f72dec7310242c0e88d4eaeb..012b7a2833829b13946f86e07089a05fae81c4a8 100644 (file)
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -57,6 +57,7 @@ add_executable(Dragonblocks
        client/debug_menu.c
        client/facecache.c
        client/font.c
+       client/frustum.c
        client/game.c
        client/gui.c
        client/input.c

diff --git a/src/client/blockmesh.c b/src/client/blockmesh.c
index f822092d7b71577812e4484ea139b4bcc7ef446c..d06ef6968c5c622b6e1383b0702eee5d588f87ad 100644 (file)
--- a/src/client/blockmesh.c
+++ b/src/client/blockmesh.c
@@ -85,8 +85,8 @@ void blockmesh_make(MapBlock *block)
 
        obj->pos = (v3f32) {block->pos.x * MAPBLOCK_SIZE + half_block_size + 0.5f, block->pos.y * MAPBLOCK_SIZE + half_block_size + 0.5f, block->pos.z * MAPBLOCK_SIZE + half_block_size + 0.5f};
        obj->scale = extra->obj ? extra->obj->scale : (v3f32) {0.1f, 0.1f, 0.1f};
-       obj->frustum_culling = false;
-       obj->box = (aabb3f32) {{-half_block_size, -half_block_size, -half_block_size}, {half_block_size, half_block_size, half_block_size}};
+       obj->frustum_culling = true;
+       obj->box = (aabb3f32) {{-half_block_size - 1.0f, -half_block_size - 1.0f, -half_block_size - 1.0f}, {half_block_size + 1.0f, half_block_size + 1.0f, half_block_size + 1.0f}};
        obj->on_render = (obj->scale.x == 1.0f) ? NULL : &animate_mapblock_mesh;
        obj->extra = block;
 

diff --git a/src/client/frustum.c b/src/client/frustum.c
new file mode 100644 (file)
index 0000000..ec96a4b
--- /dev/null
+++ b/src/client/frustum.c
@@ -0,0 +1,119 @@
+#include "frustum.h"
+
+typedef enum
+{
+       PLANE_LEFT,
+       PLANE_RIGHT,
+       PLANE_BOTTOM,
+       PLANE_TOP,
+       PLANE_NEAR,
+       PLANE_FAR,
+       PLANE_COUNT,
+} Plane;
+
+static struct
+{
+       vec3 points[8];
+       vec4 planes[PLANE_COUNT];
+       int cross_indices[PLANE_COUNT][PLANE_COUNT];
+} frustum;
+
+__attribute__((constructor)) static void init_frustum()
+{
+       for (Plane a = 0; a < PLANE_COUNT; a++)
+               for (Plane b = 0; b < PLANE_COUNT; b++)
+                       frustum.cross_indices[a][b] = a * (9 - a) / 2 + b - 1;
+}
+
+void frustum_update(mat4x4 view_proj)
+{
+       mat4x4 m;
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wpedantic"
+       mat4x4_transpose(m, view_proj);
+#pragma GCC diagnostic pop
+
+       vec4_add(frustum.planes[PLANE_LEFT], m[3], m[0]);
+       vec4_sub(frustum.planes[PLANE_RIGHT], m[3], m[0]);
+       vec4_add(frustum.planes[PLANE_BOTTOM], m[3], m[1]);
+       vec4_sub(frustum.planes[PLANE_TOP], m[3], m[1]);
+       vec4_add(frustum.planes[PLANE_NEAR], m[3], m[2]);
+       vec4_sub(frustum.planes[PLANE_FAR], m[3], m[2]);
+
+       int i = 0;
+       vec3 crosses[PLANE_COUNT * (PLANE_COUNT - 1) / 2];
+       for (Plane a = 0; a < PLANE_COUNT; a++)
+               for (Plane b = a + 1; b < PLANE_COUNT; b++)
+                       vec3_mul_cross(crosses[i++], frustum.planes[a], frustum.planes[b]);
+
+       int j = 0;
+       for (Plane c = PLANE_NEAR; c <= PLANE_FAR; c++) {
+               for (Plane a = PLANE_LEFT; a <= PLANE_RIGHT; a++) {
+                       for (Plane b = PLANE_BOTTOM; b <= PLANE_TOP; b++) {
+                               float d = -1.0f / vec3_mul_inner(frustum.planes[a], crosses[frustum.cross_indices[b][c]]);
+                               vec3 w = {frustum.planes[a][4], frustum.planes[b][4], frustum.planes[c][4]};
+                               float *res = frustum.points[j++];
+
+                               vec3 res_1_cross = {-crosses[frustum.cross_indices[a][c]][0], -crosses[frustum.cross_indices[a][c]][1], -crosses[frustum.cross_indices[a][c]][2]};
+
+                               res[0] = vec3_mul_inner(crosses[frustum.cross_indices[b][c]], w) * d;
+                               res[1] = vec3_mul_inner(res_1_cross, w) * d;
+                               res[2] = vec3_mul_inner(crosses[frustum.cross_indices[a][b]], w) * d;
+                       }
+               }
+       }
+}
+
+static bool outside_plane(Plane i, aabb3f32 box)
+{
+       for (int x = 0; x <= 1; x++) {
+               for (int y = 0; y <= 1; y++) {
+                       for (int z = 0; z <= 1; z++) {
+                               vec4 plane = {
+                                       x ? box.max.x : box.min.x,
+                                       y ? box.max.y : box.min.y,
+                                       z ? box.max.z : box.min.z,
+                                       1.0f,
+                               };
+
+                               if (vec4_mul_inner(frustum.planes[i], plane) > 0.0)
+                                       return false;
+                       }
+               }
+       }
+
+       return true;
+}
+
+// http://iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm
+bool frustum_is_visible(aabb3f32 box)
+{
+       for (Plane i = 0; i < PLANE_COUNT; i++) {
+               if (outside_plane(i, box))
+                       return false;
+       }
+
+       int box_outside[6] = {0};
+
+       for (Plane i = 0; i < PLANE_COUNT; i++) {
+               int outside[6] = {
+                       frustum.points[i][0] > box.max.x,
+                       frustum.points[i][0] < box.min.x,
+                       frustum.points[i][1] > box.max.y,
+                       frustum.points[i][1] < box.min.y,
+                       frustum.points[i][2] > box.max.z,
+                       frustum.points[i][2] < box.min.z,
+               };
+
+               for (int i = 0; i < 6; i++)
+                       box_outside[i] += outside[i];
+       }
+
+       for (int i = 0; i < 6; i++) {
+               if (box_outside[i] == 8)
+                       return false;
+       }
+
+       return true;
+}

diff --git a/src/client/frustum.h b/src/client/frustum.h
new file mode 100644 (file)
index 0000000..4dd7477
--- /dev/null
+++ b/src/client/frustum.h
@@ -0,0 +1,11 @@
+#ifndef _FRUSTUM_H_
+#define _FRUSTUM_H_
+
+#include <stdbool.h>
+#include <linmath.h/linmath.h>
+#include <dragontype/number.h>
+
+void frustum_update(mat4x4 view_proj);
+bool frustum_is_visible(aabb3f32 box);
+
+#endif

diff --git a/src/client/input.c b/src/client/input.c
index c59c541d8ff843b3f22a2446623019df6d2931e7..763629d3bb3cd28b115bfabdbae8e1be39584fdf 100644 (file)
--- a/src/client/input.c
+++ b/src/client/input.c
@@ -101,13 +101,13 @@ static KeyListener create_key_listener(int key)
 static void set_status_message(char *message)
 {
        gui_set_text(input.status_message, message);
-       input.status_message->def.text_color.w = 2.0f;
+       input.status_message->def.text_color.w = 1.01f;
 }
 
 void input_tick(f64 dtime)
 {
        if (input.status_message->def.text_color.w > 1.0f)
-               input.status_message->def.text_color.w -= dtime * 1.0f;
+               input.status_message->def.text_color.w = 1.0f;
        else if (input.status_message->def.text_color.w > 0.0f)
                input.status_message->def.text_color.w -= dtime * 1.0f;
 

diff --git a/src/client/object.c b/src/client/object.c
index 6dd487166ed9350a8ac1771d36957ebe8fac191f..5c39d267a943ec8d7809e63651dc9c89135d265d 100644 (file)
--- a/src/client/object.c
+++ b/src/client/object.c
@@ -1,5 +1,6 @@
 #include <stdio.h>
 #include <stdlib.h>
+#include "client/frustum.h"
 #include "client/object.h"
 #include "client/scene.h"
 #define OBJECT_VERTEX_ATTRIBUTES 5
@@ -180,31 +181,6 @@ void object_transform(Object *obj)
        mat4x4_scale_aniso(obj->transform, obj->transform, obj->scale.x, obj->scale.y, obj->scale.z);
 #pragma GCC diagnostic pop
 }
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wpedantic"
-static bool inside_frustum(aabb3f32 box, mat4x4 MVP)
-{
-       for (int x = 0; x <= 1; x++) {
-               for (int y = 0; y <= 1; y++) {
-                       for (int z = 0; z <= 1; z++) {
-                               vec4 point = {x ? box.min.x : box.max.x, y ? box.min.y : box.max.y, z ? box.min.z : box.max.z, 1.0};
-                               vec4 point_NDC;
-                               mat4x4_mul_vec4(point_NDC, MVP, point);
-
-                               for (int j = 0; j < 3; j++) {
-                                       float f = point_NDC[j];
-
-                                       if (f > -1.0f && f > 1.0f)
-                                               return true;
-                               }
-                       }
-               }
-       }
-
-       return false;
-}
-#pragma GCC diagnostic pop
-
 
 void object_render(Object *obj, f64 dtime)
 {
@@ -215,14 +191,9 @@ void object_render(Object *obj, f64 dtime)
                return;
 
        if (obj->frustum_culling) {
-               mat4x4 MVP;
-
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wpedantic"
-               mat4x4_mul(MVP, scene.VP, obj->transform);
-#pragma GCC diagnostic pop
+               aabb3f32 box = {v3f32_add(obj->box.min, obj->pos), v3f32_add(obj->box.max, obj->pos), };
 
-                if (! inside_frustum(obj->box, MVP))
+                if (! frustum_is_visible(box))
                        return;
        }
 

diff --git a/src/client/scene.c b/src/client/scene.c
index 979bdcca59e7b672ff61f575760b942155b99848..cbacfea737e1a5c5d28acf15ec9d8ed4e9bf88b7 100644 (file)
--- a/src/client/scene.c
+++ b/src/client/scene.c
@@ -2,6 +2,7 @@
 #include <stdio.h>
 #include "client/camera.h"
 #include "client/client.h"
+#include "client/frustum.h"
 #include "client/scene.h"
 #include "client/shader.h"
 #include "day.h"
@@ -75,6 +76,8 @@ void scene_render(f64 dtime)
        mat4x4_mul_vec4(sunlight_dir, sunlight_mat, base_sunlight_dir);
 #pragma GCC diagnostic pop
 
+       frustum_update(scene.VP);
+
        glUseProgram(scene.prog);
        glUniformMatrix4fv(scene.loc_VP, 1, GL_FALSE, scene.VP[0]);
        glUniform3f(scene.loc_lightDir, sunlight_dir[0], sunlight_dir[1], sunlight_dir[2]);

diff --git a/textures/player.png b/textures/player.png
index 677a77367fd3fc593b33abcc5b6cbdc57f3280e8..c04d569a6dadb82b2431bb6804493f5e3c9ef10b 100644 (file)
Binary files a/textures/player.png and b/textures/player.png differ