From fb670942b13d4426c07715385f254c5d92121202 Mon Sep 17 00:00:00 2001 From: Elias Fleckenstein Date: Fri, 1 Oct 2021 12:47:27 +0200 Subject: [PATCH] Implement frustum culling properly --- README.md | 4 +- src/CMakeLists.txt | 1 + src/client/blockmesh.c | 4 +- src/client/frustum.c | 119 +++++++++++++++++++++++++++++++++++++++++ src/client/frustum.h | 11 ++++ src/client/input.c | 4 +- src/client/object.c | 35 ++---------- src/client/scene.c | 3 ++ textures/player.png | Bin 1308 -> 6085 bytes 9 files changed, 143 insertions(+), 38 deletions(-) create mode 100644 src/client/frustum.c create mode 100644 src/client/frustum.h diff --git a/README.md b/README.md index c547242..e9effe3 100644 --- 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 242e83d..012b7a2 100644 --- 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 f822092..d06ef69 100644 --- 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 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 index 0000000..4dd7477 --- /dev/null +++ b/src/client/frustum.h @@ -0,0 +1,11 @@ +#ifndef _FRUSTUM_H_ +#define _FRUSTUM_H_ + +#include +#include +#include + +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 c59c541..763629d 100644 --- 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 6dd4871..5c39d26 100644 --- a/src/client/object.c +++ b/src/client/object.c @@ -1,5 +1,6 @@ #include #include +#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 979bdcc..cbacfea 100644 --- a/src/client/scene.c +++ b/src/client/scene.c @@ -2,6 +2,7 @@ #include #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 GIT binary patch literal 6085 zcmeHLc~}$I77wCq5^60dBG1Nv2-Qg@Lm-(nVG9vbi6BsfLdD5s5`ttgGmwB=UzozDy>@ums+=i7Wa)>^l1fou2=+pcLHL3&u5?C*M8so!{p0y&;6a>IrrRi z&dl7RxDioI7cUnEgTa(XN5+HSUi8Pw0epY>;5o)%*dNVHOs3*7Gs|c)sI^%Hi^??; zEW)ByGZ>bOJT8$CU8@w5d;Zv1%vZdD!O&y^-E(tI0gI8H`;ap%Ux4z68$s(l>~ z?LX*A)hR4TsdRN7>+vi5dXi)9Xy4h*ZIzdHOg?+;@&U+iw|Hplzysu6>+C5exB&-N`@ z*`v7d(o!t1IDeJ@;;G)7)|D_<8rMYveZmp5$y9bP!c*{M_H-NQl zKEw0!ps7zXJ?i?dnOTsOx4xiY{WX5ON0MbrarpswdShD zUs~mPVs^hvRZcA)iJ|rryv{lAD%@FCTLTYqD>+%Y^t||a!=mMpsf`cjjUPvDe%f+y z-ZaB|a8~#f=PZe1@JL_8XP(Pcq`xfXsDs1#@f#TdKV4+#IPR%b4%dbKvw-dh(l7vJa)jBk`Fj<)TMk z{I4@lFY`^I@Rf0MCj%rmGj6)axIlp1-~>^`a@f)qT_i=Rtj-jSU~2 zNva#i3`#2Bc=HG5#=5izbrG`^shPWc&h2j6@^nC6bkO)Ye|?~5SZlR{Sb!G#-0_;#JmKcu z8N0r(9Rnznn|3B}b7zxTX)cWcs-nw-+&rcZ^+%%NYu=fIzJbH$fU?}uLa z)vo=XukKP~njX?}lh%vo4rq-&y@Ppc<^EpYqzXVW$~=t||XpzG?m0 zkb>a(wU~cPW|NcevGl2tGs@DUTZg$ZeIL&D-o4@3>V?xi_gy=1*WBY+6a>j{hK=9% zP4qQw`^W9+8SV1h%QxpX6onjJG9LT;+{`;}e32`WTUPUNZ4iHV?7XHY6^m|ho%;=W z<}ei1gW6WTwy3p63a5)&GIJYqa+s_A)0k?fBAs2R+p&b&kz4l{#_xrWCvhI{O}}{d zv|ikUsTh^({Qm9wkz}ujpNxrL$XY^d+jBu?O7>{QmS1jiY_{twSUo6xB7b$*eK5@XaC+z(wnzBKg-+@X%ZC=u6lQwNj2l?zQZ6b=rgq0s0b{8KxCz&u|->e5io5@LYMh`L|RfBugAXl~)3JTW? zpydxj#^o>cEqJoba-ytf?@-g{Ils>)Php`o#h#@P#pCjm{d2ZnuHLNLa46x>NZA?x zYb&!;e%X6CrMxcr&Wg5zU-njRKasuUV6^i6;k^ci4Pz3CV+M}cG;C%OziF_zO*$vt zcX7-X#1rikSKxB=-n8e{&H9rE8uFLAk6?Vxt!(GHhZW{u(b3hkp7dtH-hZDt?+H=w~cXhBm?R>X*KgN}o#3`&Ay z(HTKvFc{)cixI=e5)?~GXta6>yLr!kHcP9Lutx3}iwF?t2nu6abXj^*WRb9~ydvX~ z2tm2F`e0U}=+f4colykwa^nfokZr;VSq`D6 zd~A&xv$9EBo7p5mi>!WUsnlHHl-07WPLx~`*QG;;QKQuvtr|4i7OBF!aK>y?mKCGI zxkMJB1CEe@nfD4F=yxf+b~#pZYoJ7t20WW)kw;3{v;!iQ0oSTT*1re}qeQS!01@V zvNkja2puW8Lgsj*yKC>k{l0Qcq|d|qQLbKOh0vK}Hh{!DwW2XKKBK^_l delta 1235 zcmV;^1T6c-FPsXHBYy($dQ@0+Qek%>aB^>EX>4U6ba`-PAZ2)IW&i+q+U=H0mfRo= zMdz#{OF$ArVmTPhIoUy$p9lVQRj2dMAcHb(g9Vo4cV()>{^j!spKwsg9Fm&nl5@n7 zN-A72@OT_$T`8t@J#XSQc(R9kf?*Q$a@<-y*H_r}?SU%>ZGX@9;O7kc>FDx&I+Pii zG3bv;!p?`C(&?z|#~>HC$5b~y`gSf{shsC%y!`2QOwIf7Xh;T?x+0J;??MvS)sGBh zo+K5$;W}rhg)vs~uuS>P1cE%h-YsB!6zEChYZTtAe~;dY&-Jv+J1z665e6SlkbW%w zlK3I8+!^ungny;W)dwPv?qlr7+trkzXg(_{hD)8L{^*cB$$BiK8BWF6Rx4;8YivN? zV~ZPFqe2YbN1#NVDh=9K->4zQ#5)^$<_1vH=3-p9ffz}ejRu<(>Ehtlcn=~l^PLN= zxMjs_{uC8FrJR>+HIU4J8uNp4=T3P5O_+;jJM*0OTuX~y0J5GonpmV;0Qtdtb>W64oNRYjAkW;OMo zMQfIvvVZ2BEzeD^npiTmY-Vo7s*5LA&u;EsycRBkJy1(7R=ku_D~F0e6}~FgS6DXQ zWJ{ZFd9%&8vekz2X{l+;&6>B;YUeH;+eFXZy7$uSPGQGRv8P@4yxZ=3+3P^94H;?Z z$is$@GU`q3r20+!4Qg~!<3(z&vzr>M!R&HDbALP0$qd9e5s2F)fP&`9EIOscliXw$ z3*)0uMv^+&giezf5T>122i@%6$o&$xp#DqT_-Ew8ME5Vq1)%$u+XvM8{GDry*zpxk zO{0wYLssz@Mrxx&#C3OB|DX?l>)_?+<>=+;<>=+;<>=+;e{eML??VY+0j{r}>c^|# zbdzQTAb(q>QYsE+5OK&*oh*oo6kN0lMW_&Jg;pI*F8zWgh9t$sQE)9d__0`ZaBKX$y-8M6+q?pUEh~Za+5rKdN zre$UsvyzmC@A$e$fUkFPp5=e;&(W(EECvKb;(r-tm^Se`@zkbmaNZ{tSXowy&xuD( zx*+i**A3|#4L|3(8ye3D*oYq2AsZyUI{ZfnXO zaJd5vJQ=bnyHbc|uvi4%&*+=-K>sZeS@n8r?c?+T$WmA78{ps&7%5Tqn$Np?I(z%~ zOsl^i=n`_)hTV<*00006VoOIv0RI6000sY`y{D6t_!b{N2MQEA5d-$=!T